1------------------------------------------------------------------------------
2--                                                                          --
3--                         GNAT COMPILER COMPONENTS                         --
4--                                                                          --
5--                               E L I S T S                                --
6--                                                                          --
7--                                 S p e c                                  --
8--                                                                          --
9--          Copyright (C) 1992-2021, 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). Separate list
28--  elements are allocated to represent elements of these lists, so it is
29--  possible for a given node to be on more than one element list at a time.
30--  See also package Nlists, which provides another form that is threaded
31--  through the nodes themselves (using the Link field), which is more time
32--  and space efficient, but a node can be only one such list.
33
34--  WARNING: There is a C version of this package. Any changes to this
35--  source file must be properly reflected in the C header file elists.h
36
37with Types;  use Types;
38with System;
39
40package Elists is
41
42   --  An element list is represented by a header that is allocated in the
43   --  Elist header table. This header contains pointers to the first and
44   --  last elements in the list, or to No_Elmt if the list is empty.
45
46   --  The elements in the list each contain a pointer to the next element
47   --  and a pointer to the referenced node. Putting a node into an element
48   --  list causes no change at all to the node itself, so a node may be
49   --  included in multiple element lists, and the nodes thus included may
50   --  or may not be elements of node lists (see package Nlists).
51
52   procedure Initialize;
53   --  Initialize allocation of element list tables. Called at the start of
54   --  compiling each new main source file.
55
56   procedure Lock;
57   --  Lock tables used for element lists before calling backend
58
59   procedure Unlock;
60   --  Unlock list tables, in cases where the back end needs to modify them
61
62   function Last_Elist_Id return Elist_Id;
63   --  Returns Id of last allocated element list header
64
65   function Elists_Address return System.Address;
66   --  Return address of Elists table (used in Back_End for Gigi call)
67
68   function Num_Elists return Nat;
69   --  Number of currently allocated element lists
70
71   function Last_Elmt_Id return Elmt_Id;
72   --  Returns Id of last allocated list element
73
74   function Elmts_Address return System.Address;
75   --  Return address of Elmts table (used in Back_End for Gigi call)
76
77   function Node (Elmt : Elmt_Id) return Node_Or_Entity_Id;
78   pragma Inline (Node);
79   --  Returns the value of a given list element. Returns Empty if Elmt
80   --  is set to No_Elmt.
81
82   function New_Elmt_List return Elist_Id;
83   --  Creates a new empty element list. Typically this is used to initialize
84   --  a field in some other node which points to an element list where the
85   --  list is then subsequently filled in using Append calls.
86
87   function New_Elmt_List (Elmt1 : Node_Or_Entity_Id) return Elist_Id;
88   function New_Elmt_List
89     (Elmt1 : Node_Or_Entity_Id;
90      Elmt2 : Node_Or_Entity_Id) return Elist_Id;
91   function New_Elmt_List
92     (Elmt1 : Node_Or_Entity_Id;
93      Elmt2 : Node_Or_Entity_Id;
94      Elmt3 : Node_Or_Entity_Id) return Elist_Id;
95   function New_Elmt_List
96     (Elmt1 : Node_Or_Entity_Id;
97      Elmt2 : Node_Or_Entity_Id;
98      Elmt3 : Node_Or_Entity_Id;
99      Elmt4 : Node_Or_Entity_Id) return Elist_Id;
100   --  Create a new element list containing the given arguments.
101
102   function First_Elmt (List : Elist_Id) return Elmt_Id;
103   pragma Inline (First_Elmt);
104   --  Obtains the first element of the given element list or, if the list has
105   --  no items, then No_Elmt is returned.
106
107   function Last_Elmt (List : Elist_Id) return Elmt_Id;
108   pragma Inline (Last_Elmt);
109   --  Obtains the last element of the given element list or, if the list has
110   --  no items, then No_Elmt is returned.
111
112   function List_Length (List : Elist_Id) return Nat;
113   --  Returns number of elements in given List (zero if List = No_Elist)
114
115   function Next_Elmt (Elmt : Elmt_Id) return Elmt_Id;
116   pragma Inline (Next_Elmt);
117   --  This function returns the next element on an element list. The argument
118   --  must be a list element other than No_Elmt. Returns No_Elmt if the given
119   --  element is the last element of the list.
120
121   procedure Next_Elmt (Elmt : in out Elmt_Id);
122   pragma Inline (Next_Elmt);
123   --  Next_Elmt (Elmt) is equivalent to Elmt := Next_Elmt (Elmt)
124
125   function Is_Empty_Elmt_List (List : Elist_Id) return Boolean;
126   pragma Inline (Is_Empty_Elmt_List);
127   --  This function determines if a given tree id references an element list
128   --  that contains no items.
129
130   procedure Append_Elmt (N : Node_Or_Entity_Id; To : Elist_Id);
131   --  Appends N at the end of To, allocating a new element. N must be a
132   --  non-empty node or entity Id, and To must be an Elist (not No_Elist).
133
134   procedure Append_New_Elmt (N : Node_Or_Entity_Id; To : in out Elist_Id);
135   pragma Inline (Append_New_Elmt);
136   --  Like Append_Elmt if Elist_Id is not No_List, but if Elist_Id is No_List,
137   --  then first assigns it an empty element list and then does the append.
138
139   procedure Append_Unique_Elmt (N : Node_Or_Entity_Id; To : Elist_Id);
140   --  Like Append_Elmt, except that a check is made to see if To already
141   --  contains N and if so the call has no effect.
142
143   procedure Prepend_Elmt (N : Node_Or_Entity_Id; To : Elist_Id);
144   --  Appends N at the beginning of To, allocating a new element
145
146   procedure Prepend_Unique_Elmt (N : Node_Or_Entity_Id; To : Elist_Id);
147   --  Like Prepend_Elmt, except that a check is made to see if To already
148   --  contains N and if so the call has no effect.
149
150   procedure Insert_Elmt_After (N : Node_Or_Entity_Id; Elmt : Elmt_Id);
151   --  Add a new element (N) right after the pre-existing element Elmt
152   --  It is invalid to call this subprogram with Elmt = No_Elmt.
153
154   function New_Copy_Elist (List : Elist_Id) return Elist_Id;
155   --  Replicate the contents of a list. Internal list nodes are not shared and
156   --  order of elements is preserved.
157
158   procedure Replace_Elmt (Elmt : Elmt_Id; New_Node : Node_Or_Entity_Id);
159   pragma Inline (Replace_Elmt);
160   --  Causes the given element of the list to refer to New_Node, the node
161   --  which was previously referred to by Elmt is effectively removed from
162   --  the list and replaced by New_Node.
163
164   procedure Remove (List : Elist_Id; N : Node_Or_Entity_Id);
165   --  Remove a node or an entity from a list. If the list does not contain the
166   --  item in question, the routine has no effect.
167
168   procedure Remove_Elmt (List : Elist_Id; Elmt : Elmt_Id);
169   --  Removes Elmt from the given list. The node itself is not affected,
170   --  but the space used by the list element may be (but is not required
171   --  to be) freed for reuse in a subsequent Append_Elmt call.
172
173   procedure Remove_Last_Elmt (List : Elist_Id);
174   --  Removes the last element of the given list. The node itself is not
175   --  affected, but the space used by the list element may be (but is not
176   --  required to be) freed for reuse in a subsequent Append_Elmt call.
177
178   function Contains (List : Elist_Id; N : Node_Or_Entity_Id) return Boolean;
179   --  Perform a sequential search to determine whether the given list contains
180   --  a node or an entity.
181
182   function No (List : Elist_Id) return Boolean;
183   pragma Inline (No);
184   --  Tests given Id for equality with No_Elist. This allows notations like
185   --  "if No (Statements)" as opposed to "if Statements = No_Elist".
186
187   function Present (List : Elist_Id) return Boolean;
188   pragma Inline (Present);
189   --  Tests given Id for inequality with No_Elist. This allows notations like
190   --  "if Present (Statements)" as opposed to "if Statements /= No_Elist".
191
192   function No (Elmt : Elmt_Id) return Boolean;
193   pragma Inline (No);
194   --  Tests given Id for equality with No_Elmt. This allows notations like
195   --  "if No (Operation)" as opposed to "if Operation = No_Elmt".
196
197   function Present (Elmt : Elmt_Id) return Boolean;
198   pragma Inline (Present);
199   --  Tests given Id for inequality with No_Elmt. This allows notations like
200   --  "if Present (Operation)" as opposed to "if Operation /= No_Elmt".
201
202end Elists;
203