1 ------------------------------------------------------------------------------
3 -- GNAT COMPILER COMPONENTS --
9 -- Copyright (C) 1996-2007, Free Software Foundation, Inc. --
11 -- GNAT is free software; you can redistribute it and/or modify it under --
12 -- terms of the GNU General Public License as published by the Free Soft- --
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
16 -- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --
17 -- for more details. You should have received a copy of the GNU General --
18 -- Public License distributed with GNAT; see file COPYING3. If not, go to --
19 -- http://www.gnu.org/licenses for a complete copy of the license. --
21 -- GNAT was originally developed by the GNAT team at New York University. --
22 -- Extensive contributions were provided by Ada Core Technologies Inc. --
24 ------------------------------------------------------------------------------
26 with Atree
; use Atree
;
27 with Einfo
; use Einfo
;
28 with Namet
; use Namet
;
29 with Output
; use Output
;
30 with Sinfo
; use Sinfo
;
31 with Uintp
; use Uintp
;
33 package body Sem_Maps
is
35 -----------------------
36 -- Local Subprograms --
37 -----------------------
39 function Find_Assoc
(M
: Map
; E
: Entity_Id
) return Assoc_Index
;
40 -- Standard hash table search. M is the map to be searched, E is the
41 -- entity to be searched for, and Assoc_Index is the resulting
42 -- association, or is set to No_Assoc if there is no association.
44 function Find_Header_Size
(N
: Int
) return Header_Index
;
45 -- Find largest power of two smaller than the number of entries in
46 -- the table. This load factor of 2 may be adjusted later if needed.
48 procedure Write_Map
(E
: Entity_Id
);
49 pragma Warnings
(Off
, Write_Map
);
50 -- For debugging purposes
56 procedure Add_Association
60 Kind
: Scope_Kind
:= S_Local
)
62 Info
: constant Map_Info
:= Maps_Table
.Table
(M
);
63 Offh
: constant Header_Index
:= Info
.Header_Offset
;
64 Offs
: constant Header_Index
:= Info
.Header_Num
;
65 J
: constant Header_Index
:= Header_Index
(O_Id
) mod Offs
;
66 K
: constant Assoc_Index
:= Info
.Assoc_Next
;
69 Associations_Table
.Table
(K
) := (O_Id
, N_Id
, Kind
, No_Assoc
);
70 Maps_Table
.Table
(M
).Assoc_Next
:= K
+ 1;
72 if Headers_Table
.Table
(Offh
+ J
) /= No_Assoc
then
74 -- Place new association at head of chain
76 Associations_Table
.Table
(K
).Next
:= Headers_Table
.Table
(Offh
+ J
);
79 Headers_Table
.Table
(Offh
+ J
) := K
;
82 ------------------------
83 -- Build_Instance_Map --
84 ------------------------
86 function Build_Instance_Map
(M
: Map
) return Map
is
87 Info
: constant Map_Info
:= Maps_Table
.Table
(M
);
88 Res
: constant Map
:= New_Map
(Int
(Info
.Assoc_Num
));
89 Offh1
: constant Header_Index
:= Info
.Header_Offset
;
90 Offa1
: constant Assoc_Index
:= Info
.Assoc_Offset
;
91 Offh2
: constant Header_Index
:= Maps_Table
.Table
(Res
).Header_Offset
;
92 Offa2
: constant Assoc_Index
:= Maps_Table
.Table
(Res
).Assoc_Offset
;
94 A_Index
: Assoc_Index
;
97 for J
in 0 .. Info
.Header_Num
- 1 loop
98 A_Index
:= Headers_Table
.Table
(Offh1
+ J
);
100 if A_Index
/= No_Assoc
then
101 Headers_Table
.Table
(Offh2
+ J
) := A_Index
+ (Offa2
- Offa1
);
105 for J
in 0 .. Info
.Assoc_Num
- 1 loop
106 A
:= Associations_Table
.Table
(Offa1
+ J
);
108 -- For local entities that come from source, create the
109 -- corresponding local entities in the instance. Entities that
110 -- do not come from source are etypes, and new ones will be
111 -- generated when analyzing the instance.
114 and then A
.Kind
= S_Local
115 and then Comes_From_Source
(A
.Old_Id
)
117 A
.New_Id
:= New_Copy
(A
.Old_Id
);
118 A
.New_Id
:= New_Entity
(Nkind
(A
.Old_Id
), Sloc
(A
.Old_Id
));
119 Set_Chars
(A
.New_Id
, Chars
(A
.Old_Id
));
122 if A
.Next
/= No_Assoc
then
123 A
.Next
:= A
.Next
+ (Offa2
- Offa1
);
126 Associations_Table
.Table
(Offa2
+ J
) := A
;
129 Maps_Table
.Table
(Res
).Assoc_Next
:= Associations_Table
.Last
;
131 end Build_Instance_Map
;
137 function Compose
(Orig_Map
: Map
; New_Map
: Map
) return Map
is
138 Res
: constant Map
:= Copy
(Orig_Map
);
139 Off
: constant Assoc_Index
:= Maps_Table
.Table
(Res
).Assoc_Offset
;
144 -- Iterate over the contents of Orig_Map, looking for entities
145 -- that are further mapped under New_Map.
147 for J
in 0 .. Maps_Table
.Table
(Res
).Assoc_Num
- 1 loop
148 A
:= Associations_Table
.Table
(Off
+ J
);
149 K
:= Find_Assoc
(New_Map
, A
.New_Id
);
151 if K
/= No_Assoc
then
152 Associations_Table
.Table
(Off
+ J
).New_Id
153 := Associations_Table
.Table
(K
).New_Id
;
164 function Copy
(M
: Map
) return Map
is
165 Info
: constant Map_Info
:= Maps_Table
.Table
(M
);
166 Res
: constant Map
:= New_Map
(Int
(Info
.Assoc_Num
));
167 Offh1
: constant Header_Index
:= Info
.Header_Offset
;
168 Offa1
: constant Assoc_Index
:= Info
.Assoc_Offset
;
169 Offh2
: constant Header_Index
:= Maps_Table
.Table
(Res
).Header_Offset
;
170 Offa2
: constant Assoc_Index
:= Maps_Table
.Table
(Res
).Assoc_Offset
;
172 A_Index
: Assoc_Index
;
175 for J
in 0 .. Info
.Header_Num
- 1 loop
176 A_Index
:= Headers_Table
.Table
(Offh1
+ J
) + (Offa2
- Offa1
);
178 if A_Index
/= No_Assoc
then
179 Headers_Table
.Table
(Offh2
+ J
) := A_Index
+ (Offa2
- Offa1
);
183 for J
in 0 .. Info
.Assoc_Num
- 1 loop
184 A
:= Associations_Table
.Table
(Offa1
+ J
);
185 A
.Next
:= A
.Next
+ (Offa2
- Offa1
);
186 Associations_Table
.Table
(Offa2
+ J
) := A
;
189 Maps_Table
.Table
(Res
).Assoc_Next
:= Associations_Table
.Last
;
197 function Find_Assoc
(M
: Map
; E
: Entity_Id
) return Assoc_Index
is
198 Offh
: constant Header_Index
:= Maps_Table
.Table
(M
).Header_Offset
;
199 Offs
: constant Header_Index
:= Maps_Table
.Table
(M
).Header_Num
;
200 J
: constant Header_Index
:= Header_Index
(E
) mod Offs
;
202 A_Index
: Assoc_Index
;
205 A_Index
:= Headers_Table
.Table
(Offh
+ J
);
207 if A_Index
= No_Assoc
then
211 A
:= Associations_Table
.Table
(A_Index
);
213 while Present
(A
.Old_Id
) loop
218 elsif A
.Next
= No_Assoc
then
223 A
:= Associations_Table
.Table
(A
.Next
);
231 ----------------------
232 -- Find_Header_Size --
233 ----------------------
235 function Find_Header_Size
(N
: Int
) return Header_Index
is
240 while 2 * Siz
< Header_Index
(N
) loop
245 end Find_Header_Size
;
251 function Lookup
(M
: Map
; E
: Entity_Id
) return Entity_Id
is
252 Offh
: constant Header_Index
:= Maps_Table
.Table
(M
).Header_Offset
;
253 Offs
: constant Header_Index
:= Maps_Table
.Table
(M
).Header_Num
;
254 J
: constant Header_Index
:= Header_Index
(E
) mod Offs
;
258 if Headers_Table
.Table
(Offh
+ J
) = No_Assoc
then
262 A
:= Associations_Table
.Table
(Headers_Table
.Table
(Offh
+ J
));
264 while Present
(A
.Old_Id
) loop
269 elsif A
.Next
= No_Assoc
then
273 A
:= Associations_Table
.Table
(A
.Next
);
285 function New_Map
(Num_Assoc
: Int
) return Map
is
286 Header_Size
: constant Header_Index
:= Find_Header_Size
(Num_Assoc
);
290 -- Allocate the tables for the new map at the current end of the
293 Associations_Table
.Increment_Last
;
294 Headers_Table
.Increment_Last
;
295 Maps_Table
.Increment_Last
;
297 Res
.Header_Offset
:= Headers_Table
.Last
;
298 Res
.Header_Num
:= Header_Size
;
299 Res
.Assoc_Offset
:= Associations_Table
.Last
;
300 Res
.Assoc_Next
:= Associations_Table
.Last
;
301 Res
.Assoc_Num
:= Assoc_Index
(Num_Assoc
);
303 Headers_Table
.Set_Last
(Headers_Table
.Last
+ Header_Size
);
304 Associations_Table
.Set_Last
305 (Associations_Table
.Last
+ Assoc_Index
(Num_Assoc
));
306 Maps_Table
.Table
(Maps_Table
.Last
) := Res
;
308 for J
in 1 .. Header_Size
loop
309 Headers_Table
.Table
(Headers_Table
.Last
- J
) := No_Assoc
;
312 return Maps_Table
.Last
;
315 ------------------------
316 -- Update_Association --
317 ------------------------
319 procedure Update_Association
323 Kind
: Scope_Kind
:= S_Local
)
325 J
: constant Assoc_Index
:= Find_Assoc
(M
, O_Id
);
328 Associations_Table
.Table
(J
).New_Id
:= N_Id
;
329 Associations_Table
.Table
(J
).Kind
:= Kind
;
330 end Update_Association
;
336 procedure Write_Map
(E
: Entity_Id
) is
337 M
: constant Map
:= Map
(UI_To_Int
(Renaming_Map
(E
)));
338 Info
: constant Map_Info
:= Maps_Table
.Table
(M
);
339 Offh
: constant Header_Index
:= Info
.Header_Offset
;
340 Offa
: constant Assoc_Index
:= Info
.Assoc_Offset
;
344 Write_Str
("Size : ");
345 Write_Int
(Int
(Info
.Assoc_Num
));
348 Write_Str
("Headers");
351 for J
in 0 .. Info
.Header_Num
- 1 loop
352 Write_Int
(Int
(Offh
+ J
));
354 Write_Int
(Int
(Headers_Table
.Table
(Offh
+ J
)));
358 for J
in 0 .. Info
.Assoc_Num
- 1 loop
359 A
:= Associations_Table
.Table
(Offa
+ J
);
360 Write_Int
(Int
(Offa
+ J
));
362 Write_Name
(Chars
(A
.Old_Id
));
364 Write_Int
(Int
(A
.Old_Id
));
366 Write_Int
(Int
(A
.New_Id
));
367 Write_Str
(" next = ");
368 Write_Int
(Int
(A
.Next
));