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-2010, 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
  38 with System;
  39 with Types; use Types;
  40
  41 package 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    pragma Inline (List_Length);
 153    --  Returns number of items in the given list. It is an error to call
 154    --  this function with No_List (No_List is not considered to be the same
 155    --  as an empty list).
 156
 157    function Next (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
 158    pragma Inline (Next);
 159    --  This function returns the next node on a node list, or Empty if Node is
 160    --  the last element of the node list. The argument must be a member of a
 161    --  node list.
 162
 163    procedure Next (Node : in out Node_Or_Entity_Id);
 164    pragma Inline (Next);
 165    --  Equivalent to Node := Next (Node);
 166
 167    function Next_Non_Pragma
 168      (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
 169    --  This function returns the next node on a node list, skipping past any
 170    --  pragmas, or Empty if there is no non-pragma entry left. The argument
 171    --  must be a member of a node list. This function also skips N_Null nodes
 172    --  which can result from rewriting unrecognized or incorrect pragmas.
 173
 174    procedure Next_Non_Pragma (Node : in out Node_Or_Entity_Id);
 175    pragma Inline (Next_Non_Pragma);
 176    --  Equivalent to Node := Next_Non_Pragma (Node);
 177
 178    function Prev (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
 179    pragma Inline (Prev);
 180    --  This function returns the previous node on a node list, or Empty
 181    --  if Node is the first element of the node list. The argument must be
 182    --  a member of a node list. Note: the implementation does maintain back
 183    --  pointers, so this function executes quickly in constant time.
 184
 185    function Pick (List : List_Id; Index : Pos) return Node_Or_Entity_Id;
 186    --  Given a list, picks out the Index'th entry (1 = first entry). The
 187    --  caller must ensure that Index is in range.
 188
 189    procedure Prev (Node : in out Node_Or_Entity_Id);
 190    pragma Inline (Prev);
 191    --  Equivalent to Node := Prev (Node);
 192
 193    function Prev_Non_Pragma
 194      (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
 195    pragma Inline (Prev_Non_Pragma);
 196    --  This function returns the previous node on a node list, skipping any
 197    --  pragmas. If Node is the first element of the list, or if the only
 198    --  elements preceding it are pragmas, then Empty is returned. The
 199    --  argument must be a member of a node list. Note: the implementation
 200    --  does maintain back pointers, so this function executes quickly in
 201    --  constant time.
 202
 203    procedure Prev_Non_Pragma (Node : in out Node_Or_Entity_Id);
 204    pragma Inline (Prev_Non_Pragma);
 205    --  Equivalent to Node := Prev_Non_Pragma (Node);
 206
 207    function Is_Empty_List (List : List_Id) return Boolean;
 208    pragma Inline (Is_Empty_List);
 209    --  This function determines if a given list id references a node list that
 210    --  contains no items. No_List as an argument returns True.
 211
 212    function Is_Non_Empty_List (List : List_Id) return Boolean;
 213    pragma Inline (Is_Non_Empty_List);
 214    --  This function determines if a given list id references a node list that
 215    --  contains at least one item. No_List as an argument returns False.
 216
 217    function Is_List_Member (Node : Node_Or_Entity_Id) return Boolean;
 218    pragma Inline (Is_List_Member);
 219    --  This function determines if a given node is a member of a node list.
 220    --  It is an error for Node to be Empty, or to be a node list.
 221
 222    function List_Containing (Node : Node_Or_Entity_Id) return List_Id;
 223    pragma Inline (List_Containing);
 224    --  This function provides a pointer to the node list containing Node.
 225    --  Node must be a member of a node list.
 226
 227    procedure Append (Node : Node_Or_Entity_Id; To : List_Id);
 228    --  Appends Node at the end of node list To. Node must be a non-empty node
 229    --  that is not already a member of a node list, and To must be a
 230    --  node list. An attempt to append an error node is ignored without
 231    --  complaint and the list is unchanged.
 232
 233    procedure Append_To (To : List_Id; Node : Node_Or_Entity_Id);
 234    pragma Inline (Append_To);
 235    --  Like Append, but arguments are the other way round
 236
 237    procedure Append_List (List : List_Id; To : List_Id);
 238    --  Appends node list List to the end of node list To. On return,
 239    --  List is reset to be empty.
 240
 241    procedure Append_List_To (To : List_Id; List : List_Id);
 242    pragma Inline (Append_List_To);
 243    --  Like Append_List, but arguments are the other way round
 244
 245    procedure Insert_After
 246      (After : Node_Or_Entity_Id;
 247       Node  : Node_Or_Entity_Id);
 248    --  Insert Node, which must be a non-empty node that is not already a
 249    --  member of a node list, immediately past node After, which must be a
 250    --  node that is currently a member of a node list. An attempt to insert
 251    --  an error node is ignored without complaint (and the list is unchanged).
 252
 253    procedure Insert_List_After
 254      (After : Node_Or_Entity_Id;
 255       List  : List_Id);
 256    --  Inserts the entire contents of node list List immediately after node
 257    --  After, which must be a member of a node list. On return, the node list
 258    --  List is reset to be the empty node list.
 259
 260    procedure Insert_Before
 261      (Before : Node_Or_Entity_Id;
 262       Node   : Node_Or_Entity_Id);
 263    --  Insert Node, which must be a non-empty node that is not already a
 264    --  member of a node list, immediately before Before, which must be a node
 265    --  that is currently a member of a node list. An attempt to insert an
 266    --  error node is ignored without complaint (and the list is unchanged).
 267
 268    procedure Insert_List_Before
 269      (Before : Node_Or_Entity_Id;
 270       List   : List_Id);
 271    --  Inserts the entire contents of node list List immediately before node
 272    --  Before, which must be a member of a node list. On return, the node list
 273    --  List is reset to be the empty node list.
 274
 275    procedure Prepend
 276      (Node : Node_Or_Entity_Id;
 277       To   : List_Id);
 278    --  Prepends Node at the start of node list To. Node must be a non-empty
 279    --  node that is not already a member of a node list, and To must be a
 280    --  node list. An attempt to prepend an error node is ignored without
 281    --  complaint and the list is unchanged.
 282
 283    procedure Prepend_To
 284      (To   : List_Id;
 285       Node : Node_Or_Entity_Id);
 286    pragma Inline (Prepend_To);
 287    --  Like Prepend, but arguments are the other way round
 288
 289    procedure Prepend_List
 290      (List : List_Id;
 291       To   : List_Id);
 292    --  Prepends node list List to the start of node list To. On return,
 293    --  List is reset to be empty.
 294
 295    procedure Prepend_List_To
 296      (To   : List_Id;
 297       List : List_Id);
 298    pragma Inline (Prepend_List_To);
 299    --  Like Prepend_List, but arguments are the other way round
 300
 301    procedure Remove (Node : Node_Or_Entity_Id);
 302    --  Removes Node, which must be a node that is a member of a node list,
 303    --  from this node list. The contents of Node are not otherwise affected.
 304
 305    function Remove_Head (List : List_Id) return Node_Or_Entity_Id;
 306    --  Removes the head element of a node list, and returns the node (whose
 307    --  contents are not otherwise affected) as the result. If the node list
 308    --  is empty, then Empty is returned.
 309
 310    function Remove_Next (Node : Node_Or_Entity_Id) return Node_Or_Entity_Id;
 311    --  Removes the item immediately following the given node, and returns it
 312    --  as the result. If Node is the last element of the list, then Empty is
 313    --  returned. Node must be a member of a list. Unlike Remove, Remove_Next
 314    --  is fast and does not involve any list traversal.
 315
 316    procedure Initialize;
 317    --  Called at the start of compilation of each new main source file to
 318    --  initialize the allocation of the list table. Note that Initialize
 319    --  must not be called if Tree_Read is used.
 320
 321    procedure Lock;
 322    --  Called to lock tables before back end is called
 323
 324    procedure Unlock;
 325    --  Unlock tables, in cases where the back end needs to modify them
 326
 327    procedure Tree_Read;
 328    --  Initializes internal tables from current tree file using the relevant
 329    --  Table.Tree_Read routines. Note that Initialize should not be called if
 330    --  Tree_Read is used. Tree_Read includes all necessary initialization.
 331
 332    procedure Tree_Write;
 333    --  Writes out internal tables to current tree file using the relevant
 334    --  Table.Tree_Write routines.
 335
 336    function Parent (List : List_Id) return Node_Or_Entity_Id;
 337    pragma Inline (Parent);
 338    --  Node lists may have a parent in the same way as a node. The function
 339    --  accesses the Parent value, which is either Empty when a list header
 340    --  is first created, or the value that has been set by Set_Parent.
 341
 342    procedure Set_Parent (List : List_Id; Node : Node_Or_Entity_Id);
 343    pragma Inline (Set_Parent);
 344    --  Sets the parent field of the given list to reference the given node
 345
 346    function No (List : List_Id) return Boolean;
 347    pragma Inline (No);
 348    --  Tests given Id for equality with No_List. This allows notations like
 349    --  "if No (Statements)" as opposed to "if Statements = No_List".
 350
 351    function Present (List : List_Id) return Boolean;
 352    pragma Inline (Present);
 353    --  Tests given Id for inequality with No_List. This allows notations like
 354    --  "if Present (Statements)" as opposed to "if Statements /= No_List".
 355
 356    procedure Allocate_List_Tables (N : Node_Or_Entity_Id);
 357    --  Called when nodes table is expanded to include node N. This call
 358    --  makes sure that list structures internal to Nlists are adjusted
 359    --  appropriately to reflect this increase in the size of the nodes table.
 360
 361    function Next_Node_Address return System.Address;
 362    function Prev_Node_Address return System.Address;
 363    --  These functions return the addresses of the Next_Node and Prev_Node
 364    --  tables (used in Back_End for Gigi).
 365
 366    function p (U : Union_Id) return Node_Or_Entity_Id;
 367    --  This function is intended for use from the debugger, it determines
 368    --  whether U is a Node_Id or List_Id, and calls the appropriate Parent
 369    --  function and returns the parent Node in either case. This is shorter
 370    --  to type, and avoids the overloading problem of using Parent. It
 371    --  should NEVER be used except from the debugger. If p is called with
 372    --  other than a node or list id value, it returns 99_999_999.
 373
 374 end Nlists;