]>
Commit | Line | Data |
---|---|---|
1eee94d3 GM |
1 | (* M2Graph.mod maintains the dependancy graph depth. |
2 | ||
83ffe9cd | 3 | Copyright (C) 2022-2023 Free Software Foundation, Inc. |
1eee94d3 GM |
4 | Contributed by Gaius Mulley <gaius.mulley@southwales.ac.uk>. |
5 | ||
6 | This file is part of GNU Modula-2. | |
7 | ||
8 | GNU Modula-2 is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GNU Modula-2 is distributed in the hope that it will be useful, but | |
14 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
16 | General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GNU Modula-2; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. *) | |
21 | ||
22 | IMPLEMENTATION MODULE M2Graph ; | |
23 | ||
24 | ||
25 | FROM Storage IMPORT ALLOCATE ; | |
26 | FROM StrLib IMPORT StrEqual, StrCopy ; | |
27 | FROM NumberIO IMPORT WriteCard ; | |
28 | FROM StrIO IMPORT WriteString, WriteLn ; | |
29 | FROM NameKey IMPORT Name, WriteKey ; | |
30 | FROM Lists IMPORT InitList, KillList, IncludeItemIntoList, RemoveItemFromList ; | |
31 | FROM Indexing IMPORT Index, HighIndice, IncludeIndiceIntoIndex, InitIndex, KillIndex, GetIndice ; | |
32 | FROM M2Printf IMPORT printf0, printf1, printf2 ; | |
33 | FROM SymbolTable IMPORT GetSymName, IsDefinitionForC, IsModule ; | |
34 | ||
35 | ||
36 | CONST | |
37 | Debugging = FALSE ; | |
38 | ||
39 | TYPE | |
40 | state = (initial, started, ordered) ; | |
41 | ||
42 | node = POINTER TO RECORD | |
43 | moduleSym: CARDINAL ; (* SymbolTable entry for module. *) | |
44 | deps : Index ; | |
45 | nstate : state ; | |
46 | END ; | |
47 | ||
48 | Graph = POINTER TO RECORD | |
49 | nodes: Index ; | |
50 | END ; | |
51 | ||
52 | ||
53 | (* | |
54 | InitGraph - creates and returns an empty graph. | |
55 | *) | |
56 | ||
57 | PROCEDURE InitGraph () : Graph ; | |
58 | VAR | |
59 | g: Graph ; | |
60 | BEGIN | |
61 | NEW (g) ; | |
62 | g^.nodes := InitIndex (1) ; | |
63 | RETURN g | |
64 | END InitGraph ; | |
65 | ||
66 | ||
67 | (* | |
68 | KillNode - deletes the dynamic storage associated with nptr. | |
69 | *) | |
70 | ||
71 | PROCEDURE KillNode (nptr: node) ; | |
72 | BEGIN | |
73 | nptr^.deps := KillIndex (nptr^.deps) | |
74 | END KillNode ; | |
75 | ||
76 | ||
77 | (* | |
78 | KillGraph - deletes graph and all nodes. | |
79 | *) | |
80 | ||
81 | PROCEDURE KillGraph (VAR g: Graph) ; | |
82 | VAR | |
83 | i, n: CARDINAL ; | |
84 | nptr: node ; | |
85 | BEGIN | |
86 | n := HighIndice (g^.nodes) ; | |
87 | i := 1 ; | |
88 | WHILE i <= n DO | |
89 | nptr := GetIndice (g^.nodes, i) ; | |
90 | KillNode (nptr) ; | |
91 | INC (i) | |
92 | END ; | |
93 | g := NIL | |
94 | END KillGraph ; | |
95 | ||
96 | ||
97 | (* | |
98 | initNode - create a new node in graph and return the node. | |
99 | *) | |
100 | ||
101 | PROCEDURE initNode (graph: Graph; moduleSym: CARDINAL) : node ; | |
102 | VAR | |
103 | nptr: node ; | |
104 | BEGIN | |
105 | NEW (nptr) ; | |
106 | nptr^.moduleSym := moduleSym ; | |
107 | nptr^.deps := InitIndex (1) ; | |
108 | nptr^.nstate := initial ; | |
109 | IncludeIndiceIntoIndex (graph^.nodes, nptr) ; | |
110 | RETURN nptr | |
111 | END initNode ; | |
112 | ||
113 | ||
114 | (* | |
115 | getNode - returns a node from graph representing moduleSym. | |
116 | If the node does not exist it is created. | |
117 | *) | |
118 | ||
119 | PROCEDURE getNode (graph: Graph; moduleSym: CARDINAL) : node ; | |
120 | VAR | |
121 | i, n: CARDINAL ; | |
122 | nptr: node ; | |
123 | BEGIN | |
124 | i := 1 ; | |
125 | n := HighIndice (graph^.nodes) ; | |
126 | WHILE i <= n DO | |
127 | nptr := GetIndice (graph^.nodes, i) ; | |
128 | IF nptr^.moduleSym = moduleSym | |
129 | THEN | |
130 | RETURN nptr | |
131 | END ; | |
132 | INC (i) | |
133 | END ; | |
134 | RETURN initNode (graph, moduleSym) | |
135 | END getNode ; | |
136 | ||
137 | ||
138 | (* | |
139 | createDependent - mptr imports from dptr. | |
140 | *) | |
141 | ||
142 | PROCEDURE createDependent (mptr, dptr: node) ; | |
143 | BEGIN | |
144 | IncludeIndiceIntoIndex (mptr^.deps, dptr) | |
145 | END createDependent ; | |
146 | ||
147 | ||
148 | (* | |
149 | AddDependent - adds moduleSym <- dependSym into the graph. | |
150 | *) | |
151 | ||
152 | PROCEDURE AddDependent (graph: Graph; moduleSym, dependSym: CARDINAL) ; | |
153 | VAR | |
154 | mptr, dptr: node ; | |
155 | BEGIN | |
156 | IF (IsModule (moduleSym) OR (NOT IsDefinitionForC (moduleSym))) AND | |
157 | (IsModule (dependSym) OR (NOT IsDefinitionForC (dependSym))) | |
158 | THEN | |
159 | mptr := getNode (graph, moduleSym) ; | |
160 | dptr := getNode (graph, dependSym) ; | |
161 | createDependent (mptr, dptr) | |
162 | END | |
163 | END AddDependent ; | |
164 | ||
165 | ||
166 | (* | |
167 | SortGraph - returns a List containing the sorted graph. | |
168 | *) | |
169 | ||
170 | PROCEDURE SortGraph (g: Graph; topModule: CARDINAL) : List ; | |
171 | VAR | |
172 | sorted: List ; | |
173 | nptr : node ; | |
174 | BEGIN | |
175 | InitList (sorted) ; | |
176 | setNodesInitial (g) ; | |
177 | nptr := getNode (g, topModule) ; | |
178 | resolveImports (sorted, nptr) ; | |
179 | RemoveItemFromList (sorted, topModule) ; | |
180 | IncludeItemIntoList (sorted, topModule) ; (* Ensure topModule is last. *) | |
181 | RETURN sorted | |
182 | END SortGraph ; | |
183 | ||
184 | ||
185 | (* | |
186 | resolveImports - recursively resolve imports using ISO Modula-2 | |
187 | rules for the order of module initialization. | |
188 | *) | |
189 | ||
190 | PROCEDURE resolveImports (sorted: List; nptr: node) ; | |
191 | VAR | |
192 | i, n: CARDINAL ; | |
193 | name: Name ; | |
194 | BEGIN | |
195 | IF nptr^.nstate = initial | |
196 | THEN | |
197 | nptr^.nstate := started ; | |
198 | name := GetSymName (nptr^.moduleSym) ; | |
199 | i := 1 ; | |
200 | n := HighIndice (nptr^.deps) ; | |
201 | IF Debugging | |
202 | THEN | |
203 | printf2 ("resolving %a %d dependents\n", name, n) | |
204 | END ; | |
205 | WHILE i <= n DO | |
206 | resolveImports (sorted, GetIndice (nptr^.deps, i)) ; | |
207 | INC (i) | |
208 | END ; | |
209 | nptr^.nstate := ordered ; | |
210 | IncludeItemIntoList (sorted, nptr^.moduleSym) | |
211 | END | |
212 | END resolveImports ; | |
213 | ||
214 | ||
215 | (* | |
216 | setNodesInitial - changes the state of all nodes in graph to initial. | |
217 | *) | |
218 | ||
219 | PROCEDURE setNodesInitial (g: Graph) ; | |
220 | VAR | |
221 | i, n: CARDINAL ; | |
222 | nptr: node ; | |
223 | BEGIN | |
224 | i := 1 ; | |
225 | n := HighIndice (g^.nodes) ; | |
226 | WHILE i <= n DO | |
227 | nptr := GetIndice (g^.nodes, i) ; | |
228 | nptr^.nstate := initial ; | |
229 | INC (i) | |
230 | END | |
231 | END setNodesInitial ; | |
232 | ||
233 | ||
234 | END M2Graph. |