gcc/ada/nlists.ads

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