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 --                                                                          --
  10 --          Copyright (C) 1992-2000 Free Software Foundation, Inc.          --
  11 --                                                                          --
  12 -- GNAT is free software;  you can  redistribute it  and/or modify it under --
  13 -- terms of the  GNU General Public License as published  by the Free Soft- --
  14 -- ware  Foundation;  either version 2,  or (at your option) any later ver- --
  15 -- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
  16 -- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
  17 -- or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License --
  18 -- for  more details.  You should have  received  a copy of the GNU General --
  19 -- Public License  distributed with GNAT;  see file COPYING.  If not, write --
  20 -- to  the Free Software Foundation,  59 Temple Place - Suite 330,  Boston, --
  21 -- MA 02111-1307, USA.                                                      --
  22 --                                                                          --
  23 -- As a special exception,  if other files  instantiate  generics from this --
  24 -- unit, or you link  this unit with other files  to produce an executable, --
  25 -- this  unit  does not  by itself cause  the resulting  executable  to  be --
  26 -- covered  by the  GNU  General  Public  License.  This exception does not --
  27 -- however invalidate  any other reasons why  the executable file  might be --
  28 -- covered by the  GNU Public License.                                      --
  29 --                                                                          --
  30 -- GNAT was originally developed  by the GNAT team at  New York University. --
  31 -- Extensive contributions were provided by Ada Core Technologies Inc.      --
  32 --                                                                          --
  33 ------------------------------------------------------------------------------
  34
  35 --  This package provides facilities for manipulating lists of nodes (see
  36 --  package Atree for format and implementation of tree nodes). The Link field
  37 --  of the nodes is used as the forward pointer for these lists. See also
  38 --  package Elists which provides another form of lists that are not threaded
  39 --  through the nodes (and therefore allow nodes to be on multiple lists).
  40
  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 Last_List_Id return List_Id;
  56    pragma Inline (Last_List_Id);
  57    --  Returns Id of last allocated list header
  58
  59    function Lists_Address return System.Address;
  60    pragma Inline (Lists_Address);
  61    --  Return address of Lists table (used in Back_End for Gigi call)
  62
  63    function Num_Lists return Nat;
  64    pragma Inline (Num_Lists);
  65    --  Number of currently allocated lists
  66
  67    function New_List return List_Id;
  68    --  Creates a new empty node list. Typically this is used to initialize
  69    --  a field in some other node which points to a node list where the list
  70    --  is then subsequently filled in using Append calls.
  71
  72    function Empty_List return List_Id renames New_List;
  73    --  Used in contexts where an empty list (as opposed to an initially empty
  74    --  list to be filled in) is required.
  75
  76    function New_List (Node : Node_Id) return List_Id;
  77    --  Build a new list initially containing the given node
  78
  79    function New_List (Node1, Node2 : Node_Id) return List_Id;
  80    --  Build a new list initially containing the two given nodes
  81
  82    function New_List (Node1, Node2, Node3 : Node_Id) return List_Id;
  83    --  Build a new list initially containing the three given nodes
  84
  85    function New_List (Node1, Node2, Node3, Node4 : Node_Id) return List_Id;
  86    --  Build a new list initially containing the four given nodes
  87
  88    function New_List
  89      (Node1 : Node_Id;
  90       Node2 : Node_Id;
  91       Node3 : Node_Id;
  92       Node4 : Node_Id;
  93       Node5 : Node_Id)
  94       return  List_Id;
  95    --  Build a new list initially containing the five given nodes
  96
  97    function New_List
  98      (Node1 : Node_Id;
  99       Node2 : Node_Id;
 100       Node3 : Node_Id;
 101       Node4 : Node_Id;
 102       Node5 : Node_Id;
 103       Node6 : Node_Id)
 104       return  List_Id;
 105    --  Build a new list initially containing the five given nodes
 106
 107    function New_Copy_List (List : List_Id) return List_Id;
 108    --  Creates a new list containing copies (made with Atree.New_Copy) of every
 109    --  node in the original list. If the argument is No_List, then the returned
 110    --  result is No_List. If the argument is an empty list, then the returned
 111    --  result is a new empty list.
 112
 113    function New_Copy_List_Original (List : List_Id) return List_Id;
 114    --  Same as New_Copy_List but copies only nodes coming from source
 115
 116    function New_Copy_List_Tree (List : List_Id) return List_Id;
 117    --  Similar to New_Copy_List, except that the copies are done using the
 118    --  Atree.New_Copy_Tree function, which means that a full recursive copy
 119    --  of the subtrees in the list is performed, setting proper parents. As
 120    --  for New_Copy_Tree, it is illegal to attempt to copy extended nodes
 121    --  (entities) either directly or indirectly using this function.
 122
 123    function First (List : List_Id) return Node_Id;
 124    pragma Inline (First);
 125    --  Obtains the first element of the given node list or, if the node list
 126    --  has no items or is equal to No_List, then Empty is returned.
 127
 128    function First_Non_Pragma (List : List_Id) return Node_Id;
 129    --  Used when dealing with a list that can contain pragmas to skip past
 130    --  any initial pragmas and return the first element that is not a pragma.
 131    --  If the list is empty, or if it contains only pragmas, then Empty is
 132    --  returned. It is an error to call First_Non_Pragma with a Node_Id value
 133    --  or No_List (No_List is not considered to be the same as an empty list).
 134    --  This function also skips N_Null nodes which can result from rewriting
 135    --  unrecognized or incorrrect pragmas.
 136
 137    function Last (List : List_Id) return Node_Id;
 138    pragma Inline (Last);
 139    --  Obtains the last element of the given node list or, if the node list
 140    --  has no items, then Empty is returned. It is an error to call Last with
 141    --  a Node_Id or No_List. (No_List is not considered to be the same as an
 142    --  empty node list).
 143
 144    function Last_Non_Pragma (List : List_Id) return Node_Id;
 145    --  Obtains the last element of a given node list that is not a pragma.
 146    --  If the list is empty, or if it contains only pragmas, then Empty is
 147    --  returned. It is an error to call Last_Non_Pragma with a Node_Id or
 148    --  No_List. (No_List is not considered to be the same as an empty list).
 149
 150    function List_Length (List : List_Id) return Nat;
 151    pragma Inline (List_Length);
 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_Id) return Node_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_Id);
 163    pragma Inline (Next);
 164    --  Equivalent to Node := Next (Node);
 165
 166    function Next_Non_Pragma (Node : Node_Id) return Node_Id;
 167    --  This function returns the next node on a node list, skipping past any
 168    --  pragmas, or Empty if there is no non-pragma entry left. The argument
 169    --  must be a member of a node list. This function also skips N_Null nodes
 170    --  which can result from rewriting unrecognized or incorrect pragmas.
 171
 172    procedure Next_Non_Pragma (Node : in out Node_Id);
 173    pragma Inline (Next_Non_Pragma);
 174    --  Equivalent to Node := Next_Non_Pragma (Node);
 175
 176    function Prev (Node : Node_Id) return Node_Id;
 177    pragma Inline (Prev);
 178    --  This function returns the previous node on a node list list, or Empty if
 179    --  Node is the first element of the node list. The argument must be a
 180    --  member of a node list. Note that the implementation does not maintain
 181    --  back pointers, so this function potentially requires traversal of the
 182    --  entire list, or more accurately of the part of the list preceding Node.
 183
 184    function Pick (List : List_Id; Index : Pos) return Node_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_Id);
 189    pragma Inline (Prev);
 190    --  Equivalent to Node := Prev (Node);
 191
 192    function Prev_Non_Pragma (Node : Node_Id) return Node_Id;
 193    pragma Inline (Prev_Non_Pragma);
 194    --  This function returns the previous node on a node list, skipping any
 195    --  pragmas. If Node is the first element of the list, or if the only
 196    --  elements preceding it are pragmas, then Empty is returned. The
 197    --  argument must be a member of a node list. Like Prev, this function
 198    --  may require expensive traversal of the head section of the list.
 199
 200    procedure Prev_Non_Pragma (Node : in out Node_Id);
 201    pragma Inline (Prev_Non_Pragma);
 202    --  Equivalent to Node := Prev_Non_Pragma (Node);
 203
 204    function Is_Empty_List (List : List_Id) return Boolean;
 205    pragma Inline (Is_Empty_List);
 206    --  This function determines if a given list id references a node list that
 207    --  contains no items. No_List is a not a legitimate argument.
 208
 209    function Is_Non_Empty_List (List : List_Id) return Boolean;
 210    pragma Inline (Is_Non_Empty_List);
 211    --  This function determines if a given list id references a node list that
 212    --  contains at least one item. No_List as an argument returns False.
 213
 214    function Is_List_Member (Node : Node_Id) return Boolean;
 215    pragma Inline (Is_List_Member);
 216    --  This function determines if a given node is a member of a node list.
 217    --  It is an error for Node to be Empty, or to be a node list.
 218
 219    function List_Containing (Node : Node_Id) return List_Id;
 220    pragma Inline (List_Containing);
 221    --  This function provides a pointer to the node list containing Node.
 222    --  Node must be a member of a node list.
 223
 224    procedure Append (Node : Node_Id; To : List_Id);
 225    --  Appends Node at the end of node list To. Node must be a non-empty node
 226    --  that is not already a member of a node list, and To must be a
 227    --  node list. An attempt to append an error node is ignored without
 228    --  complaint and the list is unchanged.
 229
 230    procedure Append_To (To : List_Id; Node : Node_Id);
 231    pragma Inline (Append_To);
 232    --  Like Append, but arguments are the other way round
 233
 234    procedure Append_List (List : List_Id; To : List_Id);
 235    --  Appends node list List to the end of node list To. On return,
 236    --  List is reset to be empty.
 237
 238    procedure Append_List_To (To : List_Id; List : List_Id);
 239    pragma Inline (Append_List_To);
 240    --  Like Append_List, but arguments are the other way round
 241
 242    procedure Insert_After (After : Node_Id; Node : Node_Id);
 243    --  Insert Node, which must be a non-empty node that is not already a
 244    --  member of a node list, immediately past node After, which must be a
 245    --  node that is currently a member of a node list. An attempt to insert
 246    --  an error node is ignored without complaint (and the list is unchanged).
 247
 248    procedure Insert_List_After (After : Node_Id; List : List_Id);
 249    --  Inserts the entire contents of node list List immediately after node
 250    --  After, which must be a member of a node list. On return, the node list
 251    --  List is reset to be the empty node list.
 252
 253    procedure Insert_Before (Before : Node_Id; Node : Node_Id);
 254    --  Insert Node, which must be a non-empty node that is not already a
 255    --  member of a node list, immediately before Before, which must be a node
 256    --  that is currently a member of a node list. An attempt to insert an
 257    --  error node is ignored without complaint (and the list is unchanged).
 258
 259    procedure Insert_List_Before (Before : Node_Id; List : List_Id);
 260    --  Inserts the entire contents of node list List immediately before node
 261    --  Before, which must be a member of a node list. On return, the node list
 262    --  List is reset to be the empty node list.
 263
 264    procedure Prepend (Node : Node_Id; To : List_Id);
 265    pragma Inline (Prepend);
 266    --  Prepends Node at the start of node list To. Node must be a non-empty
 267    --  node that is not already a member of a node list, and To must be a
 268    --  node list. An attempt to prepend an error node is ignored without
 269    --  complaint and the list is unchanged.
 270
 271    procedure Prepend_To (To : List_Id; Node : Node_Id);
 272    pragma Inline (Prepend_To);
 273    --  Like Prepend, but arguments are the other way round
 274
 275    procedure Remove (Node : Node_Id);
 276    --  Removes Node, which must be a node that is a member of a node list,
 277    --  from this node list. The contents of Node are not otherwise affected.
 278
 279    function Remove_Head (List : List_Id) return Node_Id;
 280    --  Removes the head element of a node list, and returns the node (whose
 281    --  contents are not otherwise affected) as the result. If the node list
 282    --  is empty, then Empty is returned.
 283
 284    function Remove_Next (Node : Node_Id) return Node_Id;
 285    pragma Inline (Remove_Next);
 286    --  Removes the item immediately following the given node, and returns it
 287    --  as the result. If Node is the last element of the list, then Empty is
 288    --  returned. Node must be a member of a list. Unlike Remove, Remove_Next
 289    --  is fast and does not involve any list traversal.
 290
 291    procedure Initialize;
 292    --  Called at the start of compilation of each new main source file to
 293    --  initialize the allocation of the list table. Note that Initialize
 294    --  must not be called if Tree_Read is used.
 295
 296    procedure Lock;
 297    --  Called to lock tables before back end is called
 298
 299    procedure Tree_Read;
 300    --  Initializes internal tables from current tree file using Tree_Read.
 301    --  Note that Initialize should not be called if Tree_Read is used.
 302    --  Tree_Read includes all necessary initialization.
 303
 304    procedure Tree_Write;
 305    --  Writes out internal tables to current tree file using Tree_Write
 306
 307    function Parent (List : List_Id) return Node_Id;
 308    pragma Inline (Parent);
 309    --  Node lists may have a parent in the same way as a node. The function
 310    --  accesses the Parent value, which is either Empty when a list header
 311    --  is first created, or the value that has been set by Set_Parent.
 312
 313    procedure Set_Parent (List : List_Id; Node : Node_Id);
 314    pragma Inline (Set_Parent);
 315    --  Sets the parent field of the given list to reference the given node
 316
 317    function No (List : List_Id) return Boolean;
 318    pragma Inline (No);
 319    --  Tests given Id for equality with No_List. This allows notations like
 320    --  "if No (Statements)" as opposed to "if Statements = No_List".
 321
 322    function Present (List : List_Id) return Boolean;
 323    pragma Inline (Present);
 324    --  Tests given Id for inequality with No_List. This allows notations like
 325    --  "if Present (Statements)" as opposed to "if Statements /= No_List".
 326
 327    procedure Allocate_List_Tables (N : Node_Id);
 328    --  Called when nodes table is expanded to include node N. This call
 329    --  makes sure that list structures internal to Nlists are adjusted
 330    --  appropriately to reflect this increase in the size of the nodes table.
 331
 332    function Next_Node_Address return System.Address;
 333    function Prev_Node_Address return System.Address;
 334    --  These functions return the addresses of the Next_Node and Prev_Node
 335    --  tables (used in Back_End for Gigi).
 336
 337    procedure Delete_List (L : List_Id);
 338    --  Removes all elements of the given list, and calls Delete_Tree on each
 339
 340    function p (U : Union_Id) return Node_Id;
 341    --  This function is intended for use from the debugger, it determines
 342    --  whether U is a Node_Id or List_Id, and calls the appropriate Parent
 343    --  function and returns the parent Node in either case. This is shorter
 344    --  to type, and avoids the overloading problem of using Parent. It
 345    --  should NEVER be used except from the debugger. If p is called with
 346    --  other than a node or list id value, it returns 99_999_999.
 347
 348 end Nlists;