1------------------------------------------------------------------------------ 2-- -- 3-- GNAT COMPILER COMPONENTS -- 4-- -- 5-- N L I S T S -- 6-- -- 7-- S p e c -- 8-- -- 9-- Copyright (C) 1992-2019, Free Software Foundation, Inc. -- 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 38with System; 39with Types; use Types; 40 41package Nlists is 42 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. 48 49 -- Note: node lists can contain either nodes or entities (extended nodes) 50 -- or a mixture of nodes and extended nodes. 51 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) 55 56 function Last_List_Id return List_Id; 57 pragma Inline (Last_List_Id); 58 -- Returns Id of last allocated list header 59 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) 63 64 function Num_Lists return Nat; 65 pragma Inline (Num_Lists); 66 -- Number of currently allocated lists 67 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. 72 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. 76 77 function New_List 78 (Node : Node_Or_Entity_Id) return List_Id; 79 -- Build a new list initially containing the given node 80 81 function New_List 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 85 86 function New_List 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 91 92 function New_List 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; 97 98 function New_List 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 105 106 function New_List 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 114 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. 120 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 123 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. 128 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. 137 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 143 -- empty node list). 144 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). 150 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). 155 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 160 -- node list. 161 162 procedure Next (Node : in out Node_Or_Entity_Id); 163 pragma Inline (Next); 164 -- Equivalent to Node := Next (Node); 165 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. 172 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); 176 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. 183 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. 187 188 procedure Prev (Node : in out Node_Or_Entity_Id); 189 pragma Inline (Prev); 190 -- Equivalent to Node := Prev (Node); 191 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 200 -- constant time. 201 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); 205 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. 210 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. 215 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. 220 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. 225 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. 231 232 procedure Append_New (Node : Node_Or_Entity_Id; To : in out List_Id); 233 pragma Inline (Append_New); 234 -- Appends Node at the end of node list To. If To is non-existent list, a 235 -- list is created. Node must be a non-empty node that is not already a 236 -- member of a node list, and To must be a node list. 237 238 procedure Append_New_To (To : in out List_Id; Node : Node_Or_Entity_Id); 239 pragma Inline (Append_New_To); 240 -- Like Append_New, but the arguments are in reverse order 241 242 procedure Append_To (To : List_Id; Node : Node_Or_Entity_Id); 243 pragma Inline (Append_To); 244 -- Like Append, but arguments are the other way round 245 246 procedure Append_List (List : List_Id; To : List_Id); 247 -- Appends node list List to the end of node list To. On return, 248 -- List is reset to be empty. 249 250 procedure Append_List_To (To : List_Id; List : List_Id); 251 pragma Inline (Append_List_To); 252 -- Like Append_List, but arguments are the other way round 253 254 procedure Insert_After 255 (After : Node_Or_Entity_Id; 256 Node : Node_Or_Entity_Id); 257 -- Insert Node, which must be a non-empty node that is not already a 258 -- member of a node list, immediately past node After, which must be a 259 -- node that is currently a member of a node list. An attempt to insert 260 -- an error node is ignored without complaint (and the list is unchanged). 261 262 procedure Insert_List_After 263 (After : Node_Or_Entity_Id; 264 List : List_Id); 265 -- Inserts the entire contents of node list List immediately after node 266 -- After, which must be a member of a node list. On return, the node list 267 -- List is reset to be the empty node list. 268 269 procedure Insert_Before 270 (Before : Node_Or_Entity_Id; 271 Node : Node_Or_Entity_Id); 272 -- Insert Node, which must be a non-empty node that is not already a 273 -- member of a node list, immediately before Before, which must be a node 274 -- that is currently a member of a node list. An attempt to insert an 275 -- error node is ignored without complaint (and the list is unchanged). 276 277 procedure Insert_List_Before 278 (Before : Node_Or_Entity_Id; 279 List : List_Id); 280 -- Inserts the entire contents of node list List immediately before node 281 -- Before, which must be a member of a node list. On return, the node list 282 -- List is reset to be the empty node list. 283 284 procedure Prepend 285 (Node : Node_Or_Entity_Id; 286 To : List_Id); 287 -- Prepends Node at the start of node list To. Node must be a non-empty 288 -- node that is not already a member of a node list, and To must be a 289 -- node list. An attempt to prepend an error node is ignored without 290 -- complaint and the list is unchanged. 291 292 procedure Prepend_List 293 (List : List_Id; 294 To : List_Id); 295 -- Prepends node list List to the start of node list To. On return, 296 -- List is reset to be empty. 297 298 procedure Prepend_List_To 299 (To : List_Id; 300 List : List_Id); 301 pragma Inline (Prepend_List_To); 302 -- Like Prepend_List, but arguments are the other way round 303 304 procedure Prepend_New (Node : Node_Or_Entity_Id; To : in out List_Id); 305 pragma Inline (Prepend_New); 306 -- Prepends Node at the end of node list To. If To is non-existent list, a 307 -- list is created. Node must be a non-empty node that is not already a 308 -- member of a node list, and To must be a node list. 309 310 procedure Prepend_New_To (To : in out List_Id; Node : Node_Or_Entity_Id); 311 pragma Inline (Prepend_New_To); 312 -- Like Prepend_New, but the arguments are in reverse order 313 314 procedure Prepend_To 315 (To : List_Id; 316 Node : Node_Or_Entity_Id); 317 pragma Inline (Prepend_To); 318 -- Like Prepend, but arguments are the other way round 319 320 procedure Remove (Node : Node_Or_Entity_Id); 321 -- Removes Node, which must be a node that is a member of a node list, 322 -- from this node list. The contents of Node are not otherwise affected. 323 324 function Remove_Head (List : List_Id) return Node_Or_Entity_Id; 325 -- Removes the head element of a node list, and returns the node (whose 326 -- contents are not otherwise affected) as the result. If the node list 327 -- is empty, then Empty is returned. 328 329 function Remove_Next (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id; 330 -- Removes the item immediately following the given node, and returns it 331 -- as the result. If Node is the last element of the list, then Empty is 332 -- returned. Node must be a member of a list. Unlike Remove, Remove_Next 333 -- is fast and does not involve any list traversal. 334 335 procedure Initialize; 336 -- Called at the start of compilation of each new main source file to 337 -- initialize the allocation of the list table. Note that Initialize 338 -- must not be called if Tree_Read is used. 339 340 procedure Lock; 341 -- Called to lock tables before back end is called 342 343 procedure Lock_Lists; 344 -- Called to lock list contents when assertions are enabled. Without 345 -- assertions calling this subprogram has no effect. The initial state 346 -- of the lock is unlocked. 347 348 procedure Unlock; 349 -- Unlock tables, in cases where the back end needs to modify them 350 351 procedure Unlock_Lists; 352 -- Called to unlock list contents when assertions are enabled; if 353 -- assertions are not enabled calling this subprogram has no effect. 354 355 procedure Tree_Read; 356 -- Initializes internal tables from current tree file using the relevant 357 -- Table.Tree_Read routines. Note that Initialize should not be called if 358 -- Tree_Read is used. Tree_Read includes all necessary initialization. 359 360 procedure Tree_Write; 361 -- Writes out internal tables to current tree file using the relevant 362 -- Table.Tree_Write routines. 363 364 function Parent (List : List_Id) return Node_Or_Entity_Id; 365 pragma Inline (Parent); 366 -- Node lists may have a parent in the same way as a node. The function 367 -- accesses the Parent value, which is either Empty when a list header 368 -- is first created, or the value that has been set by Set_Parent. 369 370 procedure Set_Parent (List : List_Id; Node : Node_Or_Entity_Id); 371 pragma Inline (Set_Parent); 372 -- Sets the parent field of the given list to reference the given node 373 374 function No (List : List_Id) return Boolean; 375 pragma Inline (No); 376 -- Tests given Id for equality with No_List. This allows notations like 377 -- "if No (Statements)" as opposed to "if Statements = No_List". Note that 378 -- an empty list gives False for this test, as opposed to Is_Empty_List 379 -- which gives True either for No_List or for an empty list. 380 381 function Present (List : List_Id) return Boolean; 382 pragma Inline (Present); 383 -- Tests given Id for inequality with No_List. This allows notations like 384 -- "if Present (Statements)" as opposed to "if Statements /= No_List". 385 386 procedure Allocate_List_Tables (N : Node_Or_Entity_Id); 387 -- Called when nodes table is expanded to include node N. This call 388 -- makes sure that list structures internal to Nlists are adjusted 389 -- appropriately to reflect this increase in the size of the nodes table. 390 391 function Next_Node_Address return System.Address; 392 function Prev_Node_Address return System.Address; 393 -- These functions return the addresses of the Next_Node and Prev_Node 394 -- tables (used in Back_End for Gigi). 395 396end Nlists; 397