Branch data Line data Source code
1 : : /* do not edit automatically generated by mc from M2Graph. */
2 : : /* M2Graph.mod maintains the dependancy graph depth.
3 : :
4 : : Copyright (C) 2022-2024 Free Software Foundation, Inc.
5 : : Contributed by Gaius Mulley <gaius.mulley@southwales.ac.uk>.
6 : :
7 : : This file is part of GNU Modula-2.
8 : :
9 : : GNU Modula-2 is free software; you can redistribute it and/or modify
10 : : it under the terms of the GNU General Public License as published by
11 : : the Free Software Foundation; either version 3, or (at your option)
12 : : any later version.
13 : :
14 : : GNU Modula-2 is distributed in the hope that it will be useful, but
15 : : WITHOUT ANY WARRANTY; without even the implied warranty of
16 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 : : General Public License for more details.
18 : :
19 : : You should have received a copy of the GNU General Public License
20 : : along with GNU Modula-2; see the file COPYING3. If not see
21 : : <http://www.gnu.org/licenses/>. */
22 : :
23 : : #include "config.h"
24 : : #include "system.h"
25 : : #include <stdbool.h>
26 : : # if !defined (PROC_D)
27 : : # define PROC_D
28 : : typedef void (*PROC_t) (void);
29 : : typedef struct { PROC_t proc; } PROC;
30 : : # endif
31 : :
32 : : # if !defined (FALSE)
33 : : # define FALSE (1==0)
34 : : # endif
35 : :
36 : : # include "GStorage.h"
37 : : #if defined(__cplusplus)
38 : : # undef NULL
39 : : # define NULL 0
40 : : #endif
41 : : #define _M2Graph_H
42 : : #define _M2Graph_C
43 : :
44 : : # include "GStorage.h"
45 : : # include "GStrLib.h"
46 : : # include "GNumberIO.h"
47 : : # include "GStrIO.h"
48 : : # include "GNameKey.h"
49 : : # include "GLists.h"
50 : : # include "GIndexing.h"
51 : : # include "GM2Printf.h"
52 : : # include "GSymbolTable.h"
53 : :
54 : : # define Debugging false
55 : : typedef struct M2Graph__T1_r M2Graph__T1;
56 : :
57 : : typedef struct M2Graph__T2_r M2Graph__T2;
58 : :
59 : : typedef M2Graph__T2 *M2Graph_node;
60 : :
61 : : typedef enum {M2Graph_initial, M2Graph_started, M2Graph_ordered} M2Graph_state;
62 : :
63 : : typedef M2Graph__T1 *M2Graph_Graph;
64 : :
65 : : struct M2Graph__T1_r {
66 : : Indexing_Index nodes;
67 : : };
68 : :
69 : : struct M2Graph__T2_r {
70 : : unsigned int moduleSym;
71 : : Indexing_Index deps;
72 : : M2Graph_state nstate;
73 : : };
74 : :
75 : :
76 : : /*
77 : : InitGraph - creates and returns an empty graph.
78 : : */
79 : :
80 : : extern "C" M2Graph_Graph M2Graph_InitGraph (void);
81 : :
82 : : /*
83 : : KillGraph - deletes graph and all nodes.
84 : : */
85 : :
86 : : extern "C" void M2Graph_KillGraph (M2Graph_Graph *g);
87 : :
88 : : /*
89 : : AddDependent - adds moduleSym <- dependSym into the graph.
90 : : */
91 : :
92 : : extern "C" void M2Graph_AddDependent (M2Graph_Graph graph, unsigned int moduleSym, unsigned int dependSym);
93 : :
94 : : /*
95 : : SortGraph - returns a List containing the sorted graph.
96 : : */
97 : :
98 : : extern "C" Lists_List M2Graph_SortGraph (M2Graph_Graph g, unsigned int topModule);
99 : :
100 : : /*
101 : : KillNode - deletes the dynamic storage associated with nptr.
102 : : */
103 : :
104 : : static void KillNode (M2Graph_node nptr);
105 : :
106 : : /*
107 : : initNode - create a new node in graph and return the node.
108 : : */
109 : :
110 : : static M2Graph_node initNode (M2Graph_Graph graph, unsigned int moduleSym);
111 : :
112 : : /*
113 : : getNode - returns a node from graph representing moduleSym.
114 : : If the node does not exist it is created.
115 : : */
116 : :
117 : : static M2Graph_node getNode (M2Graph_Graph graph, unsigned int moduleSym);
118 : :
119 : : /*
120 : : createDependent - mptr imports from dptr.
121 : : */
122 : :
123 : : static void createDependent (M2Graph_node mptr, M2Graph_node dptr);
124 : :
125 : : /*
126 : : resolveImports - recursively resolve imports using ISO Modula-2
127 : : rules for the order of module initialization.
128 : : */
129 : :
130 : : static void resolveImports (Lists_List sorted, M2Graph_node nptr);
131 : :
132 : : /*
133 : : setNodesInitial - changes the state of all nodes in graph to initial.
134 : : */
135 : :
136 : : static void setNodesInitial (M2Graph_Graph g);
137 : :
138 : :
139 : : /*
140 : : KillNode - deletes the dynamic storage associated with nptr.
141 : : */
142 : :
143 : 0 : static void KillNode (M2Graph_node nptr)
144 : : {
145 : 0 : nptr->deps = Indexing_KillIndex (nptr->deps);
146 : 0 : }
147 : :
148 : :
149 : : /*
150 : : initNode - create a new node in graph and return the node.
151 : : */
152 : :
153 : 57246 : static M2Graph_node initNode (M2Graph_Graph graph, unsigned int moduleSym)
154 : : {
155 : 57246 : M2Graph_node nptr;
156 : :
157 : 57246 : Storage_ALLOCATE ((void **) &nptr, sizeof (M2Graph__T2));
158 : 57246 : nptr->moduleSym = moduleSym;
159 : 57246 : nptr->deps = Indexing_InitIndex (1);
160 : 57246 : nptr->nstate = M2Graph_initial;
161 : 57246 : Indexing_IncludeIndiceIntoIndex (graph->nodes, reinterpret_cast<void *> (nptr));
162 : 57246 : return nptr;
163 : : /* static analysis guarentees a RETURN statement will be used before here. */
164 : : __builtin_unreachable ();
165 : : }
166 : :
167 : :
168 : : /*
169 : : getNode - returns a node from graph representing moduleSym.
170 : : If the node does not exist it is created.
171 : : */
172 : :
173 : 365462 : static M2Graph_node getNode (M2Graph_Graph graph, unsigned int moduleSym)
174 : : {
175 : 365462 : unsigned int i;
176 : 365462 : unsigned int n;
177 : 365462 : M2Graph_node nptr;
178 : :
179 : 365462 : i = 1;
180 : 365462 : n = Indexing_HighIndice (graph->nodes);
181 : 4658822 : while (i <= n)
182 : : {
183 : 4236114 : nptr = static_cast<M2Graph_node> (Indexing_GetIndice (graph->nodes, i));
184 : 4236114 : if (nptr->moduleSym == moduleSym)
185 : : {
186 : 308216 : return nptr;
187 : : }
188 : 3927898 : i += 1;
189 : : }
190 : 57246 : return initNode (graph, moduleSym);
191 : : /* static analysis guarentees a RETURN statement will be used before here. */
192 : : __builtin_unreachable ();
193 : : }
194 : :
195 : :
196 : : /*
197 : : createDependent - mptr imports from dptr.
198 : : */
199 : :
200 : 181536 : static void createDependent (M2Graph_node mptr, M2Graph_node dptr)
201 : : {
202 : 0 : Indexing_IncludeIndiceIntoIndex (mptr->deps, reinterpret_cast<void *> (dptr));
203 : 181536 : }
204 : :
205 : :
206 : : /*
207 : : resolveImports - recursively resolve imports using ISO Modula-2
208 : : rules for the order of module initialization.
209 : : */
210 : :
211 : 67490 : static void resolveImports (Lists_List sorted, M2Graph_node nptr)
212 : : {
213 : 67490 : unsigned int i;
214 : 67490 : unsigned int n;
215 : 67490 : NameKey_Name libname;
216 : 67490 : NameKey_Name name;
217 : :
218 : 67490 : if (nptr->nstate == M2Graph_initial)
219 : : {
220 : 23360 : nptr->nstate = M2Graph_started;
221 : 23360 : name = SymbolTable_GetSymName (nptr->moduleSym);
222 : 23360 : libname = SymbolTable_GetLibName (nptr->moduleSym);
223 : 23360 : i = 1;
224 : 23360 : n = Indexing_HighIndice (nptr->deps);
225 : 23360 : if (Debugging)
226 : : {
227 : : M2Printf_printf3 ((const char *) "resolving %a [%a] %d dependents\\n", 33, (const unsigned char *) &name, (sizeof (name)-1), (const unsigned char *) &libname, (sizeof (libname)-1), (const unsigned char *) &n, (sizeof (n)-1));
228 : : }
229 : 111820 : while (i <= n)
230 : : {
231 : 65100 : resolveImports (sorted, reinterpret_cast<M2Graph_node> (Indexing_GetIndice (nptr->deps, i)));
232 : 65100 : i += 1;
233 : : }
234 : 23360 : nptr->nstate = M2Graph_ordered;
235 : 23360 : Lists_IncludeItemIntoList (sorted, nptr->moduleSym);
236 : : }
237 : 67490 : }
238 : :
239 : :
240 : : /*
241 : : setNodesInitial - changes the state of all nodes in graph to initial.
242 : : */
243 : :
244 : 2390 : static void setNodesInitial (M2Graph_Graph g)
245 : : {
246 : 2390 : unsigned int i;
247 : 2390 : unsigned int n;
248 : 2390 : M2Graph_node nptr;
249 : :
250 : 2390 : i = 1;
251 : 2390 : n = Indexing_HighIndice (g->nodes);
252 : 61226 : while (i <= n)
253 : : {
254 : 56446 : nptr = static_cast<M2Graph_node> (Indexing_GetIndice (g->nodes, i));
255 : 56446 : nptr->nstate = M2Graph_initial;
256 : 56446 : i += 1;
257 : : }
258 : 2390 : }
259 : :
260 : :
261 : : /*
262 : : InitGraph - creates and returns an empty graph.
263 : : */
264 : :
265 : 2390 : extern "C" M2Graph_Graph M2Graph_InitGraph (void)
266 : : {
267 : 2390 : M2Graph_Graph g;
268 : :
269 : 2390 : Storage_ALLOCATE ((void **) &g, sizeof (M2Graph__T1));
270 : 2390 : g->nodes = Indexing_InitIndex (1);
271 : 2390 : return g;
272 : : /* static analysis guarentees a RETURN statement will be used before here. */
273 : : __builtin_unreachable ();
274 : : }
275 : :
276 : :
277 : : /*
278 : : KillGraph - deletes graph and all nodes.
279 : : */
280 : :
281 : 0 : extern "C" void M2Graph_KillGraph (M2Graph_Graph *g)
282 : : {
283 : 0 : unsigned int i;
284 : 0 : unsigned int n;
285 : 0 : M2Graph_node nptr;
286 : :
287 : 0 : n = Indexing_HighIndice ((*g)->nodes);
288 : 0 : i = 1;
289 : 0 : while (i <= n)
290 : : {
291 : 0 : nptr = static_cast<M2Graph_node> (Indexing_GetIndice ((*g)->nodes, i));
292 : 0 : KillNode (nptr);
293 : 0 : i += 1;
294 : : }
295 : 0 : (*g) = NULL;
296 : 0 : }
297 : :
298 : :
299 : : /*
300 : : AddDependent - adds moduleSym <- dependSym into the graph.
301 : : */
302 : :
303 : 211852 : extern "C" void M2Graph_AddDependent (M2Graph_Graph graph, unsigned int moduleSym, unsigned int dependSym)
304 : : {
305 : 211852 : M2Graph_node mptr;
306 : 211852 : M2Graph_node dptr;
307 : :
308 : 211852 : if (((SymbolTable_IsModule (moduleSym)) || (! (SymbolTable_IsDefinitionForC (moduleSym)))) && ((SymbolTable_IsModule (dependSym)) || (! (SymbolTable_IsDefinitionForC (dependSym)))))
309 : : {
310 : 181536 : mptr = getNode (graph, moduleSym);
311 : 181536 : dptr = getNode (graph, dependSym);
312 : 181536 : createDependent (mptr, dptr);
313 : : }
314 : 211852 : }
315 : :
316 : :
317 : : /*
318 : : SortGraph - returns a List containing the sorted graph.
319 : : */
320 : :
321 : 2390 : extern "C" Lists_List M2Graph_SortGraph (M2Graph_Graph g, unsigned int topModule)
322 : : {
323 : 2390 : Lists_List sorted;
324 : 2390 : M2Graph_node nptr;
325 : :
326 : 2390 : Lists_InitList (&sorted);
327 : 2390 : setNodesInitial (g);
328 : 2390 : nptr = getNode (g, topModule);
329 : 2390 : resolveImports (sorted, nptr);
330 : 2390 : Lists_RemoveItemFromList (sorted, topModule);
331 : 2390 : Lists_IncludeItemIntoList (sorted, topModule); /* Ensure topModule is last. */
332 : 2390 : return sorted; /* Ensure topModule is last. */
333 : : /* static analysis guarentees a RETURN statement will be used before here. */
334 : : __builtin_unreachable ();
335 : : }
336 : :
337 : 0 : extern "C" void _M2_M2Graph_init (__attribute__((unused)) int argc,__attribute__((unused)) char *argv[],__attribute__((unused)) char *envp[])
338 : : {
339 : 0 : }
340 : :
341 : 0 : extern "C" void _M2_M2Graph_fini (__attribute__((unused)) int argc,__attribute__((unused)) char *argv[],__attribute__((unused)) char *envp[])
342 : : {
343 : 0 : }
|
