1 ------------------------------------------------------------------------------
3 -- GNAT COMPILER COMPONENTS --
9 -- Copyright (C) 1992-2014, 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. --
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. --
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/>. --
27 -- GNAT was originally developed by the GNAT team at New York University. --
28 -- Extensive contributions were provided by Ada Core Technologies Inc. --
30 ------------------------------------------------------------------------------
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).
39 with Types; use Types;
43 -- A node list is a list of nodes in a special format that means that
44 -- nodes can be on at most one such list. For each node list, a list
45 -- header is allocated in the lists table, and a List_Id value references
46 -- this header, which may be used to access the nodes in the list using
47 -- the set of routines that define this interface.
49 -- Note: node lists can contain either nodes or entities (extended nodes)
50 -- or a mixture of nodes and extended nodes.
52 function In_Same_List (N1, N2 : Node_Or_Entity_Id) return Boolean;
53 pragma Inline (In_Same_List);
54 -- Equivalent to List_Containing (N1) = List_Containing (N2)
56 function Last_List_Id return List_Id;
57 pragma Inline (Last_List_Id);
58 -- Returns Id of last allocated list header
60 function Lists_Address return System.Address;
61 pragma Inline (Lists_Address);
62 -- Return address of Lists table (used in Back_End for Gigi call)
64 function Num_Lists return Nat;
65 pragma Inline (Num_Lists);
66 -- Number of currently allocated lists
68 function New_List return List_Id;
69 -- Creates a new empty node list. Typically this is used to initialize
70 -- a field in some other node which points to a node list where the list
71 -- is then subsequently filled in using Append calls.
73 function Empty_List return List_Id renames New_List;
74 -- Used in contexts where an empty list (as opposed to an initially empty
75 -- list to be filled in) is required.
78 (Node : Node_Or_Entity_Id) return List_Id;
79 -- Build a new list initially containing the given node
82 (Node1 : Node_Or_Entity_Id;
83 Node2 : Node_Or_Entity_Id) return List_Id;
84 -- Build a new list initially containing the two given nodes
87 (Node1 : Node_Or_Entity_Id;
88 Node2 : Node_Or_Entity_Id;
89 Node3 : Node_Or_Entity_Id) return List_Id;
90 -- Build a new list initially containing the three given nodes
93 (Node1 : Node_Or_Entity_Id;
94 Node2 : Node_Or_Entity_Id;
95 Node3 : Node_Or_Entity_Id;
96 Node4 : Node_Or_Entity_Id) return List_Id;
99 (Node1 : Node_Or_Entity_Id;
100 Node2 : Node_Or_Entity_Id;
101 Node3 : Node_Or_Entity_Id;
102 Node4 : Node_Or_Entity_Id;
103 Node5 : Node_Or_Entity_Id) return List_Id;
104 -- Build a new list initially containing the five given nodes
107 (Node1 : Node_Or_Entity_Id;
108 Node2 : Node_Or_Entity_Id;
109 Node3 : Node_Or_Entity_Id;
110 Node4 : Node_Or_Entity_Id;
111 Node5 : Node_Or_Entity_Id;
112 Node6 : Node_Or_Entity_Id) return List_Id;
113 -- Build a new list initially containing the six given nodes
115 function New_Copy_List (List : List_Id) return List_Id;
116 -- Creates a new list containing copies (made with Atree.New_Copy) of every
117 -- node in the original list. If the argument is No_List, then the returned
118 -- result is No_List. If the argument is an empty list, then the returned
119 -- result is a new empty list.
121 function New_Copy_List_Original (List : List_Id) return List_Id;
122 -- Same as New_Copy_List but copies only nodes coming from source
124 function First (List : List_Id) return Node_Or_Entity_Id;
125 pragma Inline (First);
126 -- Obtains the first element of the given node list or, if the node list
127 -- has no items or is equal to No_List, then Empty is returned.
129 function First_Non_Pragma (List : List_Id) return Node_Or_Entity_Id;
130 -- Used when dealing with a list that can contain pragmas to skip past
131 -- any initial pragmas and return the first element that is not a pragma.
132 -- If the list is empty, or if it contains only pragmas, then Empty is
133 -- returned. It is an error to call First_Non_Pragma with a Node_Id value
134 -- or No_List (No_List is not considered to be the same as an empty list).
135 -- This function also skips N_Null nodes which can result from rewriting
136 -- unrecognized or incorrect pragmas.
138 function Last (List : List_Id) return Node_Or_Entity_Id;
139 pragma Inline (Last);
140 -- Obtains the last element of the given node list or, if the node list
141 -- has no items, then Empty is returned. It is an error to call Last with
142 -- a Node_Id or No_List. (No_List is not considered to be the same as an
145 function Last_Non_Pragma (List : List_Id) return Node_Or_Entity_Id;
146 -- Obtains the last element of a given node list that is not a pragma.
147 -- If the list is empty, or if it contains only pragmas, then Empty is
148 -- returned. It is an error to call Last_Non_Pragma with a Node_Id or
149 -- No_List. (No_List is not considered to be the same as an empty list).
151 function List_Length (List : List_Id) return Nat;
152 -- Returns number of items in the given list. It is an error to call
153 -- this function with No_List (No_List is not considered to be the same
154 -- as an empty list).
156 function Next (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
157 pragma Inline (Next);
158 -- This function returns the next node on a node list, or Empty if Node is
159 -- the last element of the node list. The argument must be a member of a
162 procedure Next (Node : in out Node_Or_Entity_Id);
163 pragma Inline (Next);
164 -- Equivalent to Node := Next (Node);
166 function Next_Non_Pragma
167 (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
168 -- This function returns the next node on a node list, skipping past any
169 -- pragmas, or Empty if there is no non-pragma entry left. The argument
170 -- must be a member of a node list. This function also skips N_Null nodes
171 -- which can result from rewriting unrecognized or incorrect pragmas.
173 procedure Next_Non_Pragma (Node : in out Node_Or_Entity_Id);
174 pragma Inline (Next_Non_Pragma);
175 -- Equivalent to Node := Next_Non_Pragma (Node);
177 function Prev (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
178 pragma Inline (Prev);
179 -- This function returns the previous node on a node list, or Empty
180 -- if Node is the first element of the node list. The argument must be
181 -- a member of a node list. Note: the implementation does maintain back
182 -- pointers, so this function executes quickly in constant time.
184 function Pick (List : List_Id; Index : Pos) return Node_Or_Entity_Id;
185 -- Given a list, picks out the Index'th entry (1 = first entry). The
186 -- caller must ensure that Index is in range.
188 procedure Prev (Node : in out Node_Or_Entity_Id);
189 pragma Inline (Prev);
190 -- Equivalent to Node := Prev (Node);
192 function Prev_Non_Pragma
193 (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
194 pragma Inline (Prev_Non_Pragma);
195 -- This function returns the previous node on a node list, skipping any
196 -- pragmas. If Node is the first element of the list, or if the only
197 -- elements preceding it are pragmas, then Empty is returned. The
198 -- argument must be a member of a node list. Note: the implementation
199 -- does maintain back pointers, so this function executes quickly in
202 procedure Prev_Non_Pragma (Node : in out Node_Or_Entity_Id);
203 pragma Inline (Prev_Non_Pragma);
204 -- Equivalent to Node := Prev_Non_Pragma (Node);
206 function Is_Empty_List (List : List_Id) return Boolean;
207 pragma Inline (Is_Empty_List);
208 -- This function determines if a given list id references a node list that
209 -- contains no items. No_List as an argument returns True.
211 function Is_Non_Empty_List (List : List_Id) return Boolean;
212 pragma Inline (Is_Non_Empty_List);
213 -- This function determines if a given list id references a node list that
214 -- contains at least one item. No_List as an argument returns False.
216 function Is_List_Member (Node : Node_Or_Entity_Id) return Boolean;
217 pragma Inline (Is_List_Member);
218 -- This function determines if a given node is a member of a node list.
219 -- It is an error for Node to be Empty, or to be a node list.
221 function List_Containing (Node : Node_Or_Entity_Id) return List_Id;
222 pragma Inline (List_Containing);
223 -- This function provides a pointer to the node list containing Node.
224 -- Node must be a member of a node list.
226 procedure Append (Node : Node_Or_Entity_Id; To : List_Id);
227 -- Appends Node at the end of node list To. Node must be a non-empty node
228 -- that is not already a member of a node list, and To must be a node list.
229 -- An attempt to append an error node is ignored without complaint and the
230 -- list is unchanged.
232 procedure Append_To (To : List_Id; Node : Node_Or_Entity_Id);
233 pragma Inline (Append_To);
234 -- Like Append, but arguments are the other way round
236 procedure Append_List (List : List_Id; To : List_Id);
237 -- Appends node list List to the end of node list To. On return,
238 -- List is reset to be empty.
240 procedure Append_List_To (To : List_Id; List : List_Id);
241 pragma Inline (Append_List_To);
242 -- Like Append_List, but arguments are the other way round
244 procedure Insert_After
245 (After : Node_Or_Entity_Id;
246 Node : Node_Or_Entity_Id);
247 -- Insert Node, which must be a non-empty node that is not already a
248 -- member of a node list, immediately past node After, which must be a
249 -- node that is currently a member of a node list. An attempt to insert
250 -- an error node is ignored without complaint (and the list is unchanged).
252 procedure Insert_List_After
253 (After : Node_Or_Entity_Id;
255 -- Inserts the entire contents of node list List immediately after node
256 -- After, which must be a member of a node list. On return, the node list
257 -- List is reset to be the empty node list.
259 procedure Insert_Before
260 (Before : Node_Or_Entity_Id;
261 Node : Node_Or_Entity_Id);
262 -- Insert Node, which must be a non-empty node that is not already a
263 -- member of a node list, immediately before Before, which must be a node
264 -- that is currently a member of a node list. An attempt to insert an
265 -- error node is ignored without complaint (and the list is unchanged).
267 procedure Insert_List_Before
268 (Before : Node_Or_Entity_Id;
270 -- Inserts the entire contents of node list List immediately before node
271 -- Before, which must be a member of a node list. On return, the node list
272 -- List is reset to be the empty node list.
275 (Node : Node_Or_Entity_Id;
277 -- Prepends Node at the start of node list To. Node must be a non-empty
278 -- node that is not already a member of a node list, and To must be a
279 -- node list. An attempt to prepend an error node is ignored without
280 -- complaint and the list is unchanged.
284 Node : Node_Or_Entity_Id);
285 pragma Inline (Prepend_To);
286 -- Like Prepend, but arguments are the other way round
288 procedure Prepend_List
291 -- Prepends node list List to the start of node list To. On return,
292 -- List is reset to be empty.
294 procedure Prepend_List_To
297 pragma Inline (Prepend_List_To);
298 -- Like Prepend_List, but arguments are the other way round
300 procedure Remove (Node : Node_Or_Entity_Id);
301 -- Removes Node, which must be a node that is a member of a node list,
302 -- from this node list. The contents of Node are not otherwise affected.
304 function Remove_Head (List : List_Id) return Node_Or_Entity_Id;
305 -- Removes the head element of a node list, and returns the node (whose
306 -- contents are not otherwise affected) as the result. If the node list
307 -- is empty, then Empty is returned.
309 function Remove_Next (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
310 -- Removes the item immediately following the given node, and returns it
311 -- as the result. If Node is the last element of the list, then Empty is
312 -- returned. Node must be a member of a list. Unlike Remove, Remove_Next
313 -- is fast and does not involve any list traversal.
315 procedure Initialize;
316 -- Called at the start of compilation of each new main source file to
317 -- initialize the allocation of the list table. Note that Initialize
318 -- must not be called if Tree_Read is used.
321 -- Called to lock tables before back end is called
324 -- Unlock tables, in cases where the back end needs to modify them
327 -- Initializes internal tables from current tree file using the relevant
328 -- Table.Tree_Read routines. Note that Initialize should not be called if
329 -- Tree_Read is used. Tree_Read includes all necessary initialization.
331 procedure Tree_Write;
332 -- Writes out internal tables to current tree file using the relevant
333 -- Table.Tree_Write routines.
335 function Parent (List : List_Id) return Node_Or_Entity_Id;
336 pragma Inline (Parent);
337 -- Node lists may have a parent in the same way as a node. The function
338 -- accesses the Parent value, which is either Empty when a list header
339 -- is first created, or the value that has been set by Set_Parent.
341 procedure Set_Parent (List : List_Id; Node : Node_Or_Entity_Id);
342 pragma Inline (Set_Parent);
343 -- Sets the parent field of the given list to reference the given node
345 function No (List : List_Id) return Boolean;
347 -- Tests given Id for equality with No_List. This allows notations like
348 -- "if No (Statements)" as opposed to "if Statements = No_List". Note that
349 -- an empty list gives False for this test, as opposed to Is_Empty_List
350 -- which gives True either for No_List or for an empty list.
352 function Present (List : List_Id) return Boolean;
353 pragma Inline (Present);
354 -- Tests given Id for inequality with No_List. This allows notations like
355 -- "if Present (Statements)" as opposed to "if Statements /= No_List".
357 procedure Allocate_List_Tables (N : Node_Or_Entity_Id);
358 -- Called when nodes table is expanded to include node N. This call
359 -- makes sure that list structures internal to Nlists are adjusted
360 -- appropriately to reflect this increase in the size of the nodes table.
362 function Next_Node_Address return System.Address;
363 function Prev_Node_Address return System.Address;
364 -- These functions return the addresses of the Next_Node and Prev_Node
365 -- tables (used in Back_End for Gigi).