|
111
|
1 ------------------------------------------------------------------------------
|
|
|
2 -- --
|
|
|
3 -- GNAT COMPILER COMPONENTS --
|
|
|
4 -- --
|
|
|
5 -- N L I S T S --
|
|
|
6 -- --
|
|
|
7 -- S p e c --
|
|
|
8 -- --
|
|
145
|
9 -- Copyright (C) 1992-2019, Free Software Foundation, Inc. --
|
|
111
|
10 -- --
|
|
|
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. --
|
|
|
17 -- --
|
|
|
18 -- As a special exception under Section 7 of GPL version 3, you are granted --
|
|
|
19 -- additional permissions described in the GCC Runtime Library Exception, --
|
|
|
20 -- version 3.1, as published by the Free Software Foundation. --
|
|
|
21 -- --
|
|
|
22 -- You should have received a copy of the GNU General Public License and --
|
|
|
23 -- a copy of the GCC Runtime Library Exception along with this program; --
|
|
|
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
|
|
|
25 -- <http://www.gnu.org/licenses/>. --
|
|
|
26 -- --
|
|
|
27 -- GNAT was originally developed by the GNAT team at New York University. --
|
|
|
28 -- Extensive contributions were provided by Ada Core Technologies Inc. --
|
|
|
29 -- --
|
|
|
30 ------------------------------------------------------------------------------
|
|
|
31
|
|
|
32 -- This package provides facilities for manipulating lists of nodes (see
|
|
|
33 -- package Atree for format and implementation of tree nodes). The Link field
|
|
|
34 -- of the nodes is used as the forward pointer for these lists. See also
|
|
|
35 -- package Elists which provides another form of lists that are not threaded
|
|
|
36 -- through the nodes (and therefore allow nodes to be on multiple lists).
|
|
|
37
|
|
145
|
38 -- WARNING: There is a C version of this package. Any changes to this
|
|
|
39 -- source file must be properly reflected in the C header file nlists.h
|
|
|
40
|
|
111
|
41 with System;
|
|
|
42 with Types; use Types;
|
|
|
43
|
|
|
44 package Nlists is
|
|
|
45
|
|
|
46 -- A node list is a list of nodes in a special format that means that
|
|
|
47 -- nodes can be on at most one such list. For each node list, a list
|
|
|
48 -- header is allocated in the lists table, and a List_Id value references
|
|
|
49 -- this header, which may be used to access the nodes in the list using
|
|
|
50 -- the set of routines that define this interface.
|
|
|
51
|
|
|
52 -- Note: node lists can contain either nodes or entities (extended nodes)
|
|
|
53 -- or a mixture of nodes and extended nodes.
|
|
|
54
|
|
|
55 function In_Same_List (N1, N2 : Node_Or_Entity_Id) return Boolean;
|
|
|
56 pragma Inline (In_Same_List);
|
|
|
57 -- Equivalent to List_Containing (N1) = List_Containing (N2)
|
|
|
58
|
|
|
59 function Last_List_Id return List_Id;
|
|
|
60 pragma Inline (Last_List_Id);
|
|
|
61 -- Returns Id of last allocated list header
|
|
|
62
|
|
|
63 function Lists_Address return System.Address;
|
|
|
64 pragma Inline (Lists_Address);
|
|
|
65 -- Return address of Lists table (used in Back_End for Gigi call)
|
|
|
66
|
|
|
67 function Num_Lists return Nat;
|
|
|
68 pragma Inline (Num_Lists);
|
|
|
69 -- Number of currently allocated lists
|
|
|
70
|
|
|
71 function New_List return List_Id;
|
|
|
72 -- Creates a new empty node list. Typically this is used to initialize
|
|
|
73 -- a field in some other node which points to a node list where the list
|
|
|
74 -- is then subsequently filled in using Append calls.
|
|
|
75
|
|
|
76 function Empty_List return List_Id renames New_List;
|
|
|
77 -- Used in contexts where an empty list (as opposed to an initially empty
|
|
|
78 -- list to be filled in) is required.
|
|
|
79
|
|
|
80 function New_List
|
|
|
81 (Node : Node_Or_Entity_Id) return List_Id;
|
|
|
82 -- Build a new list initially containing the given node
|
|
|
83
|
|
|
84 function New_List
|
|
|
85 (Node1 : Node_Or_Entity_Id;
|
|
|
86 Node2 : Node_Or_Entity_Id) return List_Id;
|
|
|
87 -- Build a new list initially containing the two given nodes
|
|
|
88
|
|
|
89 function New_List
|
|
|
90 (Node1 : Node_Or_Entity_Id;
|
|
|
91 Node2 : Node_Or_Entity_Id;
|
|
|
92 Node3 : Node_Or_Entity_Id) return List_Id;
|
|
|
93 -- Build a new list initially containing the three given nodes
|
|
|
94
|
|
|
95 function New_List
|
|
|
96 (Node1 : Node_Or_Entity_Id;
|
|
|
97 Node2 : Node_Or_Entity_Id;
|
|
|
98 Node3 : Node_Or_Entity_Id;
|
|
|
99 Node4 : Node_Or_Entity_Id) return List_Id;
|
|
|
100
|
|
|
101 function New_List
|
|
|
102 (Node1 : Node_Or_Entity_Id;
|
|
|
103 Node2 : Node_Or_Entity_Id;
|
|
|
104 Node3 : Node_Or_Entity_Id;
|
|
|
105 Node4 : Node_Or_Entity_Id;
|
|
|
106 Node5 : Node_Or_Entity_Id) return List_Id;
|
|
|
107 -- Build a new list initially containing the five given nodes
|
|
|
108
|
|
|
109 function New_List
|
|
|
110 (Node1 : Node_Or_Entity_Id;
|
|
|
111 Node2 : Node_Or_Entity_Id;
|
|
|
112 Node3 : Node_Or_Entity_Id;
|
|
|
113 Node4 : Node_Or_Entity_Id;
|
|
|
114 Node5 : Node_Or_Entity_Id;
|
|
|
115 Node6 : Node_Or_Entity_Id) return List_Id;
|
|
|
116 -- Build a new list initially containing the six given nodes
|
|
|
117
|
|
|
118 function New_Copy_List (List : List_Id) return List_Id;
|
|
|
119 -- Creates a new list containing copies (made with Atree.New_Copy) of every
|
|
|
120 -- node in the original list. If the argument is No_List, then the returned
|
|
|
121 -- result is No_List. If the argument is an empty list, then the returned
|
|
|
122 -- result is a new empty list.
|
|
|
123
|
|
|
124 function New_Copy_List_Original (List : List_Id) return List_Id;
|
|
|
125 -- Same as New_Copy_List but copies only nodes coming from source
|
|
|
126
|
|
|
127 function First (List : List_Id) return Node_Or_Entity_Id;
|
|
|
128 pragma Inline (First);
|
|
|
129 -- Obtains the first element of the given node list or, if the node list
|
|
|
130 -- has no items or is equal to No_List, then Empty is returned.
|
|
|
131
|
|
|
132 function First_Non_Pragma (List : List_Id) return Node_Or_Entity_Id;
|
|
|
133 -- Used when dealing with a list that can contain pragmas to skip past
|
|
|
134 -- any initial pragmas and return the first element that is not a pragma.
|
|
|
135 -- If the list is empty, or if it contains only pragmas, then Empty is
|
|
|
136 -- returned. It is an error to call First_Non_Pragma with a Node_Id value
|
|
|
137 -- or No_List (No_List is not considered to be the same as an empty list).
|
|
|
138 -- This function also skips N_Null nodes which can result from rewriting
|
|
|
139 -- unrecognized or incorrect pragmas.
|
|
|
140
|
|
|
141 function Last (List : List_Id) return Node_Or_Entity_Id;
|
|
|
142 pragma Inline (Last);
|
|
|
143 -- Obtains the last element of the given node list or, if the node list
|
|
|
144 -- has no items, then Empty is returned. It is an error to call Last with
|
|
|
145 -- a Node_Id or No_List. (No_List is not considered to be the same as an
|
|
|
146 -- empty node list).
|
|
|
147
|
|
|
148 function Last_Non_Pragma (List : List_Id) return Node_Or_Entity_Id;
|
|
|
149 -- Obtains the last element of a given node list that is not a pragma.
|
|
|
150 -- If the list is empty, or if it contains only pragmas, then Empty is
|
|
|
151 -- returned. It is an error to call Last_Non_Pragma with a Node_Id or
|
|
|
152 -- No_List. (No_List is not considered to be the same as an empty list).
|
|
|
153
|
|
|
154 function List_Length (List : List_Id) return Nat;
|
|
|
155 -- Returns number of items in the given list. It is an error to call
|
|
|
156 -- this function with No_List (No_List is not considered to be the same
|
|
|
157 -- as an empty list).
|
|
|
158
|
|
|
159 function Next (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
|
|
|
160 pragma Inline (Next);
|
|
|
161 -- This function returns the next node on a node list, or Empty if Node is
|
|
|
162 -- the last element of the node list. The argument must be a member of a
|
|
|
163 -- node list.
|
|
|
164
|
|
|
165 procedure Next (Node : in out Node_Or_Entity_Id);
|
|
|
166 pragma Inline (Next);
|
|
|
167 -- Equivalent to Node := Next (Node);
|
|
|
168
|
|
|
169 function Next_Non_Pragma
|
|
|
170 (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
|
|
|
171 -- This function returns the next node on a node list, skipping past any
|
|
|
172 -- pragmas, or Empty if there is no non-pragma entry left. The argument
|
|
|
173 -- must be a member of a node list. This function also skips N_Null nodes
|
|
|
174 -- which can result from rewriting unrecognized or incorrect pragmas.
|
|
|
175
|
|
|
176 procedure Next_Non_Pragma (Node : in out Node_Or_Entity_Id);
|
|
|
177 pragma Inline (Next_Non_Pragma);
|
|
|
178 -- Equivalent to Node := Next_Non_Pragma (Node);
|
|
|
179
|
|
|
180 function Prev (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
|
|
|
181 pragma Inline (Prev);
|
|
|
182 -- This function returns the previous node on a node list, or Empty
|
|
|
183 -- if Node is the first element of the node list. The argument must be
|
|
|
184 -- a member of a node list. Note: the implementation does maintain back
|
|
|
185 -- pointers, so this function executes quickly in constant time.
|
|
|
186
|
|
|
187 function Pick (List : List_Id; Index : Pos) return Node_Or_Entity_Id;
|
|
|
188 -- Given a list, picks out the Index'th entry (1 = first entry). The
|
|
|
189 -- caller must ensure that Index is in range.
|
|
|
190
|
|
|
191 procedure Prev (Node : in out Node_Or_Entity_Id);
|
|
|
192 pragma Inline (Prev);
|
|
|
193 -- Equivalent to Node := Prev (Node);
|
|
|
194
|
|
|
195 function Prev_Non_Pragma
|
|
|
196 (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
|
|
|
197 pragma Inline (Prev_Non_Pragma);
|
|
|
198 -- This function returns the previous node on a node list, skipping any
|
|
|
199 -- pragmas. If Node is the first element of the list, or if the only
|
|
|
200 -- elements preceding it are pragmas, then Empty is returned. The
|
|
|
201 -- argument must be a member of a node list. Note: the implementation
|
|
|
202 -- does maintain back pointers, so this function executes quickly in
|
|
|
203 -- constant time.
|
|
|
204
|
|
|
205 procedure Prev_Non_Pragma (Node : in out Node_Or_Entity_Id);
|
|
|
206 pragma Inline (Prev_Non_Pragma);
|
|
|
207 -- Equivalent to Node := Prev_Non_Pragma (Node);
|
|
|
208
|
|
|
209 function Is_Empty_List (List : List_Id) return Boolean;
|
|
|
210 pragma Inline (Is_Empty_List);
|
|
|
211 -- This function determines if a given list id references a node list that
|
|
|
212 -- contains no items. No_List as an argument returns True.
|
|
|
213
|
|
|
214 function Is_Non_Empty_List (List : List_Id) return Boolean;
|
|
|
215 pragma Inline (Is_Non_Empty_List);
|
|
|
216 -- This function determines if a given list id references a node list that
|
|
|
217 -- contains at least one item. No_List as an argument returns False.
|
|
|
218
|
|
|
219 function Is_List_Member (Node : Node_Or_Entity_Id) return Boolean;
|
|
|
220 pragma Inline (Is_List_Member);
|
|
|
221 -- This function determines if a given node is a member of a node list.
|
|
|
222 -- It is an error for Node to be Empty, or to be a node list.
|
|
|
223
|
|
|
224 function List_Containing (Node : Node_Or_Entity_Id) return List_Id;
|
|
|
225 pragma Inline (List_Containing);
|
|
|
226 -- This function provides a pointer to the node list containing Node.
|
|
|
227 -- Node must be a member of a node list.
|
|
|
228
|
|
|
229 procedure Append (Node : Node_Or_Entity_Id; To : List_Id);
|
|
|
230 -- Appends Node at the end of node list To. Node must be a non-empty node
|
|
|
231 -- that is not already a member of a node list, and To must be a node list.
|
|
|
232 -- An attempt to append an error node is ignored without complaint and the
|
|
|
233 -- list is unchanged.
|
|
|
234
|
|
|
235 procedure Append_New (Node : Node_Or_Entity_Id; To : in out List_Id);
|
|
|
236 pragma Inline (Append_New);
|
|
|
237 -- Appends Node at the end of node list To. If To is non-existent list, a
|
|
|
238 -- list is created. Node must be a non-empty node that is not already a
|
|
|
239 -- member of a node list, and To must be a node list.
|
|
|
240
|
|
|
241 procedure Append_New_To (To : in out List_Id; Node : Node_Or_Entity_Id);
|
|
|
242 pragma Inline (Append_New_To);
|
|
|
243 -- Like Append_New, but the arguments are in reverse order
|
|
|
244
|
|
|
245 procedure Append_To (To : List_Id; Node : Node_Or_Entity_Id);
|
|
|
246 pragma Inline (Append_To);
|
|
|
247 -- Like Append, but arguments are the other way round
|
|
|
248
|
|
|
249 procedure Append_List (List : List_Id; To : List_Id);
|
|
|
250 -- Appends node list List to the end of node list To. On return,
|
|
|
251 -- List is reset to be empty.
|
|
|
252
|
|
|
253 procedure Append_List_To (To : List_Id; List : List_Id);
|
|
|
254 pragma Inline (Append_List_To);
|
|
|
255 -- Like Append_List, but arguments are the other way round
|
|
|
256
|
|
|
257 procedure Insert_After
|
|
|
258 (After : Node_Or_Entity_Id;
|
|
|
259 Node : Node_Or_Entity_Id);
|
|
|
260 -- Insert Node, which must be a non-empty node that is not already a
|
|
|
261 -- member of a node list, immediately past node After, which must be a
|
|
|
262 -- node that is currently a member of a node list. An attempt to insert
|
|
|
263 -- an error node is ignored without complaint (and the list is unchanged).
|
|
|
264
|
|
|
265 procedure Insert_List_After
|
|
|
266 (After : Node_Or_Entity_Id;
|
|
|
267 List : List_Id);
|
|
|
268 -- Inserts the entire contents of node list List immediately after node
|
|
|
269 -- After, which must be a member of a node list. On return, the node list
|
|
|
270 -- List is reset to be the empty node list.
|
|
|
271
|
|
|
272 procedure Insert_Before
|
|
|
273 (Before : Node_Or_Entity_Id;
|
|
|
274 Node : Node_Or_Entity_Id);
|
|
|
275 -- Insert Node, which must be a non-empty node that is not already a
|
|
|
276 -- member of a node list, immediately before Before, which must be a node
|
|
|
277 -- that is currently a member of a node list. An attempt to insert an
|
|
|
278 -- error node is ignored without complaint (and the list is unchanged).
|
|
|
279
|
|
|
280 procedure Insert_List_Before
|
|
|
281 (Before : Node_Or_Entity_Id;
|
|
|
282 List : List_Id);
|
|
|
283 -- Inserts the entire contents of node list List immediately before node
|
|
|
284 -- Before, which must be a member of a node list. On return, the node list
|
|
|
285 -- List is reset to be the empty node list.
|
|
|
286
|
|
|
287 procedure Prepend
|
|
|
288 (Node : Node_Or_Entity_Id;
|
|
|
289 To : List_Id);
|
|
|
290 -- Prepends Node at the start of node list To. Node must be a non-empty
|
|
|
291 -- node that is not already a member of a node list, and To must be a
|
|
|
292 -- node list. An attempt to prepend an error node is ignored without
|
|
|
293 -- complaint and the list is unchanged.
|
|
|
294
|
|
|
295 procedure Prepend_List
|
|
|
296 (List : List_Id;
|
|
|
297 To : List_Id);
|
|
|
298 -- Prepends node list List to the start of node list To. On return,
|
|
|
299 -- List is reset to be empty.
|
|
|
300
|
|
|
301 procedure Prepend_List_To
|
|
|
302 (To : List_Id;
|
|
|
303 List : List_Id);
|
|
|
304 pragma Inline (Prepend_List_To);
|
|
|
305 -- Like Prepend_List, but arguments are the other way round
|
|
|
306
|
|
|
307 procedure Prepend_New (Node : Node_Or_Entity_Id; To : in out List_Id);
|
|
|
308 pragma Inline (Prepend_New);
|
|
|
309 -- Prepends Node at the end of node list To. If To is non-existent list, a
|
|
|
310 -- list is created. Node must be a non-empty node that is not already a
|
|
|
311 -- member of a node list, and To must be a node list.
|
|
|
312
|
|
|
313 procedure Prepend_New_To (To : in out List_Id; Node : Node_Or_Entity_Id);
|
|
|
314 pragma Inline (Prepend_New_To);
|
|
|
315 -- Like Prepend_New, but the arguments are in reverse order
|
|
|
316
|
|
|
317 procedure Prepend_To
|
|
|
318 (To : List_Id;
|
|
|
319 Node : Node_Or_Entity_Id);
|
|
|
320 pragma Inline (Prepend_To);
|
|
|
321 -- Like Prepend, but arguments are the other way round
|
|
|
322
|
|
|
323 procedure Remove (Node : Node_Or_Entity_Id);
|
|
|
324 -- Removes Node, which must be a node that is a member of a node list,
|
|
|
325 -- from this node list. The contents of Node are not otherwise affected.
|
|
|
326
|
|
|
327 function Remove_Head (List : List_Id) return Node_Or_Entity_Id;
|
|
|
328 -- Removes the head element of a node list, and returns the node (whose
|
|
|
329 -- contents are not otherwise affected) as the result. If the node list
|
|
|
330 -- is empty, then Empty is returned.
|
|
|
331
|
|
|
332 function Remove_Next (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
|
|
|
333 -- Removes the item immediately following the given node, and returns it
|
|
|
334 -- as the result. If Node is the last element of the list, then Empty is
|
|
|
335 -- returned. Node must be a member of a list. Unlike Remove, Remove_Next
|
|
|
336 -- is fast and does not involve any list traversal.
|
|
|
337
|
|
|
338 procedure Initialize;
|
|
|
339 -- Called at the start of compilation of each new main source file to
|
|
|
340 -- initialize the allocation of the list table. Note that Initialize
|
|
|
341 -- must not be called if Tree_Read is used.
|
|
|
342
|
|
|
343 procedure Lock;
|
|
|
344 -- Called to lock tables before back end is called
|
|
|
345
|
|
|
346 procedure Lock_Lists;
|
|
|
347 -- Called to lock list contents when assertions are enabled. Without
|
|
|
348 -- assertions calling this subprogram has no effect. The initial state
|
|
|
349 -- of the lock is unlocked.
|
|
|
350
|
|
|
351 procedure Unlock;
|
|
|
352 -- Unlock tables, in cases where the back end needs to modify them
|
|
|
353
|
|
|
354 procedure Unlock_Lists;
|
|
|
355 -- Called to unlock list contents when assertions are enabled; if
|
|
|
356 -- assertions are not enabled calling this subprogram has no effect.
|
|
|
357
|
|
|
358 procedure Tree_Read;
|
|
|
359 -- Initializes internal tables from current tree file using the relevant
|
|
|
360 -- Table.Tree_Read routines. Note that Initialize should not be called if
|
|
|
361 -- Tree_Read is used. Tree_Read includes all necessary initialization.
|
|
|
362
|
|
|
363 procedure Tree_Write;
|
|
|
364 -- Writes out internal tables to current tree file using the relevant
|
|
|
365 -- Table.Tree_Write routines.
|
|
|
366
|
|
|
367 function Parent (List : List_Id) return Node_Or_Entity_Id;
|
|
|
368 pragma Inline (Parent);
|
|
|
369 -- Node lists may have a parent in the same way as a node. The function
|
|
|
370 -- accesses the Parent value, which is either Empty when a list header
|
|
|
371 -- is first created, or the value that has been set by Set_Parent.
|
|
|
372
|
|
|
373 procedure Set_Parent (List : List_Id; Node : Node_Or_Entity_Id);
|
|
|
374 pragma Inline (Set_Parent);
|
|
|
375 -- Sets the parent field of the given list to reference the given node
|
|
|
376
|
|
|
377 function No (List : List_Id) return Boolean;
|
|
|
378 pragma Inline (No);
|
|
|
379 -- Tests given Id for equality with No_List. This allows notations like
|
|
|
380 -- "if No (Statements)" as opposed to "if Statements = No_List". Note that
|
|
|
381 -- an empty list gives False for this test, as opposed to Is_Empty_List
|
|
|
382 -- which gives True either for No_List or for an empty list.
|
|
|
383
|
|
|
384 function Present (List : List_Id) return Boolean;
|
|
|
385 pragma Inline (Present);
|
|
|
386 -- Tests given Id for inequality with No_List. This allows notations like
|
|
|
387 -- "if Present (Statements)" as opposed to "if Statements /= No_List".
|
|
|
388
|
|
|
389 procedure Allocate_List_Tables (N : Node_Or_Entity_Id);
|
|
|
390 -- Called when nodes table is expanded to include node N. This call
|
|
|
391 -- makes sure that list structures internal to Nlists are adjusted
|
|
|
392 -- appropriately to reflect this increase in the size of the nodes table.
|
|
|
393
|
|
|
394 function Next_Node_Address return System.Address;
|
|
|
395 function Prev_Node_Address return System.Address;
|
|
|
396 -- These functions return the addresses of the Next_Node and Prev_Node
|
|
|
397 -- tables (used in Back_End for Gigi).
|
|
|
398
|
|
|
399 end Nlists;
|
