Bug Summary

File:src/gf_seq.c
Warning:line 993, column 10
Value stored to 'deps' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name gf_seq.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/home/kfp/aldor/aldor/aldor/src -fcoverage-compilation-dir=/home/kfp/aldor/aldor/aldor/src -resource-dir /usr/local/lib/clang/18 -D PACKAGE_NAME="aldor" -D PACKAGE_TARNAME="aldor" -D PACKAGE_VERSION="1.4.0" -D PACKAGE_STRING="aldor 1.4.0" -D PACKAGE_BUGREPORT="aldor@xinutec.org" -D PACKAGE_URL="" -D PACKAGE="aldor" -D VERSION="1.4.0" -D YYTEXT_POINTER=1 -D HAVE_STDIO_H=1 -D HAVE_STDLIB_H=1 -D HAVE_STRING_H=1 -D HAVE_INTTYPES_H=1 -D HAVE_STDINT_H=1 -D HAVE_STRINGS_H=1 -D HAVE_SYS_STAT_H=1 -D HAVE_SYS_TYPES_H=1 -D HAVE_UNISTD_H=1 -D STDC_HEADERS=1 -D HAVE_LIBREADLINE=1 -D HAVE_READLINE_READLINE_H=1 -D HAVE_READLINE_HISTORY=1 -D HAVE_READLINE_HISTORY_H=1 -D USE_GLOOP_SHELL=1 -D GENERATOR_COROUTINES=0 -D HAVE_DLFCN_H=1 -D LT_OBJDIR=".libs/" -I . -D VCSVERSION="2c53e759f1e00e345f8b172e7139debda72fda13" -internal-isystem /usr/local/lib/clang/18/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O0 -Wno-empty-body -Wno-enum-compare -Wno-missing-field-initializers -Wno-unused -Wno-unused-parameter -Wno-error=format -Wno-error=type-limits -Wno-error=strict-aliasing -Wno-sign-compare -Wno-error=shift-negative-value -Wno-error=clobbered -std=c99 -ferror-limit 19 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2026-01-15-223856-845667-1 -x c gf_seq.c
1/*****************************************************************************
2 *
3 * gf_seq.c: Generating code for add/default definition levels
4 *
5 * Copyright (c) 1990-2007 Aldor Software Organization Ltd (Aldor.org).
6 *
7 ****************************************************************************/
8
9#include "debug.h"
10#include "depdag.h"
11#include "format.h"
12#include "gf_add.h"
13#include "gf_implicit.h"
14#include "gf_prog.h"
15#include "gf_seq.h"
16#include "gf_util.h"
17#include "stab.h"
18#include "store.h"
19#include "sefo.h"
20#include "lib.h"
21#include "tfsat.h"
22#include "ablogic.h"
23#include "abpretty.h"
24#include "comsg.h"
25#include "table.h"
26#include "strops.h"
27#include "symbol.h"
28
29extern Bool genfExportDebug; /* gf_add.c */
30Bool genfImplicitDebug = false((int) 0);
31
32#define genfExportDEBUGif (!genfExportDebug) { } else afprintf DEBUG_IF(genfExport)if (!genfExportDebug) { } else afprintf
33#define genfImplicitDEBUGif (!genfImplicitDebug) { } else afprintf DEBUG_IF(genfImplicit)if (!genfImplicitDebug) { } else afprintf
34
35typedef enum {
36 DG_Const,
37 DG_Lambda,
38 DG_Cond,
39 DG_Fix,
40 DG_Type,
41 DG_NonDefn
42} DefGroupTag;
43
44typedef struct defGroup *DefGroup;
45typedef struct defSet *DefSet;
46
47DECLARE_LIST(DefGroup)typedef struct DefGroupListCons { DefGroup first; struct DefGroupListCons
*rest; } *DefGroupList; struct DefGroup_listOpsStruct { DefGroupList
(*Cons) (DefGroup, DefGroupList); DefGroupList (*Singleton) (
DefGroup); DefGroupList (*List) (int n, ...); DefGroupList (*
Listv) (va_list argp); DefGroupList (*ListNull) (DefGroup, ...
); Bool (*Equal) (DefGroupList, DefGroupList, Bool (*f) (DefGroup
, DefGroup)); DefGroup (*Find) (DefGroupList, DefGroup, Bool(
*eq)(DefGroup,DefGroup) , int *); DefGroup (*Match) (DefGroupList
, void *, Bool(*match)(DefGroup, void *), int *); DefGroupList
(*MatchAll) (DefGroupList, void *, Bool(*match)(DefGroup, void
*)); DefGroupList (*FreeCons) (DefGroupList); void (*Free) (
DefGroupList); DefGroupList (*FreeTo) (DefGroupList, DefGroupList
); void (*FreeDeeply) (DefGroupList, void (*f)(DefGroup)); DefGroupList
(*FreeDeeplyTo) (DefGroupList, DefGroupList, void (*f) (DefGroup
) ); DefGroupList (*FreeIfSat) (DefGroupList, void (*f)(DefGroup
), Bool (*s)(DefGroup)); DefGroup (*Elt) (DefGroupList, Length
); DefGroupList (*Drop) (DefGroupList, Length); DefGroupList (
*LastCons) (DefGroupList); Length (*_Length) (DefGroupList); Bool
(*IsLength) (DefGroupList, Length); Bool (*IsShorter) (DefGroupList
, Length); Bool (*IsLonger) (DefGroupList, Length); DefGroupList
(*Copy) (DefGroupList); DefGroupList (*CopyTo) (DefGroupList
, DefGroupList); DefGroupList (*CopyDeeply) (DefGroupList, DefGroup
(*)(DefGroup)); DefGroupList (*CopyDeeplyTo) (DefGroupList, DefGroupList
, DefGroup (*)(DefGroup)); DefGroupList (*Map) (DefGroup (*f)
(DefGroup), DefGroupList); DefGroupList (*NMap) (DefGroup (*f
)(DefGroup), DefGroupList); DefGroupList (*Reverse) (DefGroupList
); DefGroupList (*NReverse) (DefGroupList); DefGroupList (*Concat
) (DefGroupList, DefGroupList); DefGroupList (*NConcat) (DefGroupList
, DefGroupList); Bool (*Memq) (DefGroupList, DefGroup); Bool (
*Member) (DefGroupList, DefGroup, Bool(*eq)(DefGroup,DefGroup
) ); Bool (*ContainsAllq) (DefGroupList, DefGroupList); Bool (
*ContainsAnyq) (DefGroupList, DefGroupList); Bool (*ContainsAll
) (DefGroupList, DefGroupList, Bool (*eq)(DefGroup, DefGroup)
); Bool (*ContainsAny) (DefGroupList, DefGroupList, Bool (*eq
)(DefGroup, DefGroup)); int (*Posq) (DefGroupList, DefGroup);
int (*Position) (DefGroupList, DefGroup, Bool(*eq)(DefGroup,
DefGroup) ); DefGroupList (*NRemove) (DefGroupList, DefGroup,
Bool(*eq)(DefGroup,DefGroup) ); void (*FillVector) (DefGroup
*, DefGroupList); int (*Print) (FILE *, DefGroupList, int (*
pr)(FILE *, DefGroup) ); int (*GPrint) (FILE *, DefGroupList,
int (*pr)(FILE *, DefGroup), char *l,char *m,char *r); int (
*Format) (OStream, CString, DefGroupList); }; extern struct DefGroup_listOpsStruct
const *DefGroup_listPointer;
48
49struct defGroup {
50 DefGroupTag tag;
51 AbSyn ab;
52 int ordinal;
53 SymeList defines;
54 SymeList usedSymes;
55 DefGroupList usedDefs;
56};
57
58struct defSet {
59 int argc;
60 DefGroupList defs;
61 SymeList defines;
62 SymeList exports;
63};
64
65#define dgTag(dg)((dg)->tag) ((dg)->tag)
66#define dgUses(dg)((dg)->usedSymes) ((dg)->usedSymes)
67#define dgDefines(dg)((dg)->defines) ((dg)->defines)
68#define dgStmt(dg)((dg)->ab) ((dg)->ab)
69
70#define dgSetDefs(ds)((ds)->defs) ((ds)->defs)
71
72localstatic void gen0EnsureUsedSymes (DefSet, DefGroup);
73localstatic void gen0Fix (AbSyn, SymeList);
74localstatic void gen0DefTypeCond (AbSyn, SymeList);
75
76localstatic void dgSortDefs (DefSet);
77localstatic int dgSortClassify (DefGroup);
78localstatic DefSet dgSeqToDefSet (AbSyn, SymeList);
79localstatic DefGroup dgMakeFixGroup (DefGroupList);
80localstatic DefGroup dgStmtToDef (AbSyn, int);
81localstatic void dgAbGetUsedSymes (AbSyn, DefGroup, Bool);
82localstatic DefGroupTag dgGetTag (AbSyn);
83localstatic Bool dgSymeIsLocal (Syme);
84localstatic DefGroup dgNewGroup (DefGroupTag, AbSyn);
85localstatic void dgFreeGroup (DefGroup);
86localstatic DefGroupList dgProcessDependencies (DefGroupList, Bool);
87localstatic Syme dgSymeImportToExport (Syme);
88localstatic DefGroupList dgSortDependencies (DepDag, DepDagList, Bool);
89localstatic void dgCycleError (DepDag, DepDagList);
90localstatic void dgOrderError (DepDag, DepDagList);
91localstatic String dgPretty (DefGroup);
92localstatic Syme dgGetAbMeaning (AbSyn);
93localstatic SymeList dgFindDependencies (AbSyn);
94
95
96/******************************************************************************
97 *
98 * :: Generating sequences
99 *
100 *****************************************************************************/
101
102void
103gen0DefTypeSequence(AbSyn ab, SymeList exports)
104{
105 DefSet set;
106 DefGroupList lst;
107 SymeList symes, isymes;
108
109 if (DEBUG(genfImplicit)genfImplicitDebug) {
110 (void)fprintf(dbOut, "gen0DefTypeSequence():");
111 fnewline(dbOut);
112 for (symes = exports;symes;symes = cdr(symes)((symes)->rest)) {
113 Syme sy = car(symes)((symes)->first);
114 Bool im = symeIsImplicit(sy)(((AInt) (SYFI_ExtraBits < (8 * sizeof(int)) && !(
((((sy)->kind == SYME_Trigger ? libGetAllSymes((sy)->lib
) : ((void*)0)), (sy))->hasmask) & (1 << (SYFI_ExtraBits
))) ? (symeFieldInfo[SYFI_ExtraBits].def) : (((((sy)->kind
== SYME_Trigger ? libGetAllSymes((sy)->lib) : ((void*)0))
, (sy))->locmask) & (1 << (SYFI_ExtraBits))) ? (
(((((sy)->kind == SYME_Trigger ? libGetAllSymes((sy)->lib
) : ((void*)0)), (sy))->locmask) & (1 << (SYFI_ExtraBits
))) ? ((sy)->fieldv)[symeIndex(sy,SYFI_ExtraBits)] : (symeFieldInfo
[SYFI_ExtraBits].def)) : symeGetFieldFn(sy,SYFI_ExtraBits))) &
(0x0001));
115 String s = symePretty(sy);
116
117 (void)fprintf(dbOut," [%c] %s",(im ? '*' : ' '),s);
118 fnewline(dbOut);
119 }
120 fnewline(dbOut);
121 }
122
123
124 if (abTag(ab)((ab)->abHdr.tag) == AB_Nothing)
125 return;
126
127 set = dgSeqToDefSet(ab, exports);
128
129 dgSortDefs(set);
130
131 lst = dgSetDefs(set)((set)->defs);
132
133 while (lst) {
134 DefGroup dg = car(lst)((lst)->first);
135 if (DEBUG(genfExport)genfExportDebug) {
136 fprintf(dbOut, "looking at:\n");
137 abWrSExpr(dbOut, dgStmt(dg)((dg)->ab),int0((int) 0));
138 fprintf(dbOut, "defines:\n");
139 symeListPrintDb(dg->defines);
140 fprintf(dbOut, "uses:\n");
141 symeListPrintDb(dgUses(dg)((dg)->usedSymes));
142 }
143 gen0EnsureUsedSymes(set, dg);
144
145 switch (dg->tag) {
146 case DG_Fix:
147 gen0Fix(dgStmt(dg)((dg)->ab), dg->defines);
148 break;
149 case DG_Cond:
150 gen0DefTypeCond(dgStmt(dg)((dg)->ab), exports);
151 break;
152 default:
153 genFoamStmt(dgStmt(dg)((dg)->ab));
154 break;
155 }
156 for (symes = dg->defines; symes; symes = cdr(symes)((symes)->rest))
157 if (symeIsExport(car(symes))(((((((symes)->first))->kind == SYME_Trigger ? libGetAllSymes
((((symes)->first))->lib) : ((void*)0)), (((symes)->
first)))->kind) == SYME_Export))
158 gen0TypeAddExportSlot(car(symes)((symes)->first));
159 dgFreeGroup(dg);
160 lst = cdr(lst)((lst)->rest);
161 }
162
163
164 /* Collect implicit exports */
165 isymes = listNil(Syme)((SymeList) 0);
166 for (symes = exports;symes;symes = cdr(symes)((symes)->rest))
167 {
168 Syme syme = car(symes)((symes)->first);
169
170 if (symeIsImplicit(syme)(((AInt) (SYFI_ExtraBits < (8 * sizeof(int)) && !(
((((syme)->kind == SYME_Trigger ? libGetAllSymes((syme)->
lib) : ((void*)0)), (syme))->hasmask) & (1 << (SYFI_ExtraBits
))) ? (symeFieldInfo[SYFI_ExtraBits].def) : (((((syme)->kind
== SYME_Trigger ? libGetAllSymes((syme)->lib) : ((void*)0
)), (syme))->locmask) & (1 << (SYFI_ExtraBits)))
? ((((((syme)->kind == SYME_Trigger ? libGetAllSymes((syme
)->lib) : ((void*)0)), (syme))->locmask) & (1 <<
(SYFI_ExtraBits))) ? ((syme)->fieldv)[symeIndex(syme,SYFI_ExtraBits
)] : (symeFieldInfo[SYFI_ExtraBits].def)) : symeGetFieldFn(syme
,SYFI_ExtraBits))) & (0x0001)) && symeIsExport(syme)(((((syme)->kind == SYME_Trigger ? libGetAllSymes((syme)->
lib) : ((void*)0)), (syme))->kind) == SYME_Export)) {
171 /* Assume unconditional */
172 symeSetUnconditional(syme)(((((syme)->kind == SYME_Trigger ? libGetAllSymes((syme)->
lib) : ((void*)0)), (syme))->bits) |= (0x0020));
173
174
175 /* Add to the list */
176 isymes = listCons(Syme)(Syme_listPointer->Cons)(syme, isymes);
177 }
178 }
179
180
181 /* Do we have any implicit symes? */
182 if (isymes == listNil(Syme)((SymeList) 0)) return;
183
184
185 /* Create definitions for these exports */
186 for (symes = isymes;symes;symes = cdr(symes)((symes)->rest))
187 {
188 Syme syme = car(symes)((symes)->first);
189
190 gen0ImplicitExport(syme, exports, ab);
191 gen0TypeAddExportSlot(syme);
192 }
193}
194
195/*!! Should be expanded to allow imports and inheritance
196 * from conditional symes
197 */
198localstatic void
199gen0DefTypeCond(AbSyn ab, SymeList exports)
200{
201 FoamList topLines;
202 int l1 = gen0State->labelNo++, l2 = gen0State->labelNo++;
203 Bool flag;
204
205 /* COND-DEF */
206 AbLogic saveCond;
207 AbSyn nTest;
208 Stab stab = abStab(ab)((ab)->abHdr.seman ? (ab)->abHdr.seman->stab : 0) ? abStab(ab)((ab)->abHdr.seman ? (ab)->abHdr.seman->stab : 0) : stabFile();
209
210 flag = gen0AddImportPlace(&topLines);
211
212 nTest = abExpandDefs(stab, (ab->abIf.test)); /* COND-DEF */
213
214 gen0AddStmt(foamNewIf(genFoamBit(ab->abIf.test), l1)foamNew(FOAM_If, 2, genFoamBit(ab->abIf.test), l1), ab);
215 ablogAndPush(&gfCondKnown, &saveCond, nTest, false((int) 0)); /* COND-DEF */
216 gen0DefTypeSequence(ab->abIf.elseAlt, exports);
217 ablogAndPop (&gfCondKnown, &saveCond); /* COND-DEF */
218 gen0AddStmt(foamNewGoto(l2)foamNew(FOAM_Goto, 1, (AInt)(l2)), ab);
219
220 gen0AddStmt(foamNewLabel(l1)foamNew(FOAM_Label, 1, (AInt)(l1)), ab);
221 ablogAndPush(&gfCondKnown, &saveCond, nTest, true1); /* COND-DEF */
222 gen0DefTypeSequence(ab->abIf.thenAlt, exports);
223 ablogAndPop (&gfCondKnown, &saveCond); /* COND-DEF */
224 gen0AddStmt(foamNewLabel(l2)foamNew(FOAM_Label, 1, (AInt)(l2)), ab);
225
226 if (flag) gen0ResetImportPlace(topLines);
227}
228
229
230localstatic void
231gen0EnsureUsedSymes(DefSet set, DefGroup dg)
232{
233 SymeList symes = dgUses(dg)((dg)->usedSymes);
234
235 while (symes) {
236 Syme syme = car(symes)((symes)->first);
237 if (symeIsExport(syme)(((((syme)->kind == SYME_Trigger ? libGetAllSymes((syme)->
lib) : ((void*)0)), (syme))->kind) == SYME_Export) && gen0SymeInit(syme) == NULL((void*)0)) {
238 gen0InitExport(syme);
239 gen0AddInit(foamNewSet(gen0ExpMapRef(syme),foamNew(FOAM_Set, 2, gen0ExpMapRef(syme), foamNew(FOAM_Bool, 1
, (AInt)(((int) 0))))
240 foamNewBool(false))foamNew(FOAM_Set, 2, gen0ExpMapRef(syme), foamNew(FOAM_Bool, 1
, (AInt)(((int) 0)))));
241 gen0AddStmt(foamNewSet(gen0ExpMapRef(syme),foamNew(FOAM_Set, 2, gen0ExpMapRef(syme), foamNew(FOAM_Bool, 1
, (AInt)(1)))
242 foamNewBool(true))foamNew(FOAM_Set, 2, gen0ExpMapRef(syme), foamNew(FOAM_Bool, 1
, (AInt)(1))), NULL((void*)0));
243 set->defines = listCons(Syme)(Syme_listPointer->Cons)(syme, set->defines);
244 gen0SymeSetInit(syme, gen0Syme(syme));
245 }
246 symes = cdr(symes)((symes)->rest);
247 }
248}
249
250/******************************************************************************
251 *
252 * :: Fix-Pointing expressions...
253 *
254 *****************************************************************************/
255
256typedef struct {
257 FoamList inits;
258 FoamList finis;
259} FixInfoStruct, *FixInfo;
260
261localstatic void gen0FixDummy (Syme, AbSyn, FixInfo);
262localstatic Foam gen0FixMakeDummyCat (void);
263localstatic Foam gen0FixMakeDummyDom (void);
264localstatic Foam gen0FixFillDom (Foam, Foam);
265localstatic Foam gen0FixFillCat (Foam, Foam);
266localstatic void gen0FixGenStmts (FoamList, AbSyn);
267
268localstatic void
269gen0Fix(AbSyn ab, SymeList dsymes )
270{
271 SymeList symes;
272 FixInfoStruct info_s;
273 FixInfo info = &info_s;
274 int i;
275
276 info->inits = listNil(Foam)((FoamList) 0);
277 info->finis = listNil(Foam)((FoamList) 0);
278 for (symes = dsymes; symes ; symes = cdr(symes)((symes)->rest))
279 gen0FixDummy(car(symes)((symes)->first), ab, info);
280
281 info->inits = listNReverse(Foam)(Foam_listPointer->NReverse)(info->inits);
282 info->finis = listNReverse(Foam)(Foam_listPointer->NReverse)(info->finis);
283
284 gen0FixGenStmts(info->inits, ab);
285
286 for (i = 0; i< abArgc(ab)((ab)->abHdr.argc) ; i++)
287 genFoamStmt(abArgv(ab)((ab)->abGen.data.argv)[i]);
288
289 gen0FixGenStmts(info->finis, ab);
290
291 listFree(Foam)(Foam_listPointer->Free)(info->inits);
292 listFree(Foam)(Foam_listPointer->Free)(info->finis);
293 return ;
294}
295
296localstatic void
297gen0FixDummy(Syme syme, AbSyn pos, FixInfo info)
298{
299 TForm tf = symeType(syme);
300 Foam self = gen0Syme(syme);
301 Foam new;
302
303 /* Record the initialisation, if necessary */
304 if (symeIsExport(syme)(((((syme)->kind == SYME_Trigger ? libGetAllSymes((syme)->
lib) : ((void*)0)), (syme))->kind) == SYME_Export) && !gen0SymeInit(syme))
305 gen0SymeSetInit(syme, foamCopy(self));
306
307 if (tfSatDom(tf)) {
308 new = gen0Temp(FOAM_Word)gen0Temp0(FOAM_Word, 4);
309 info->inits = listCons(Foam)(Foam_listPointer->Cons)
310 (foamNewSet(foamCopy(self), gen0FixMakeDummyDom())foamNew(FOAM_Set, 2, foamCopy(self), gen0FixMakeDummyDom()),
311 info->inits);
312 info->finis = listCons(Foam)(Foam_listPointer->Cons)
313 (gen0FixFillDom(foamCopy(new), foamCopy(self)),
314 info->finis);
315
316 }
317 else if (tfSatCat(tf)) {
318 new = gen0Temp(FOAM_Word)gen0Temp0(FOAM_Word, 4);
319 info->inits = listCons(Foam)(Foam_listPointer->Cons)
320 (foamNewSet(foamCopy(self), gen0FixMakeDummyCat())foamNew(FOAM_Set, 2, foamCopy(self), gen0FixMakeDummyCat()),
321 info->inits);
322 info->finis = listCons(Foam)(Foam_listPointer->Cons)
323 (gen0FixFillCat(foamCopy(new), foamCopy(self)),
324 info->finis);
325
326 }
327 else {
328 foamFree(self);
329 return;
330 }
331 info->inits = listCons(Foam)(Foam_listPointer->Cons)(foamNewDef(foamCopy(new),foamNew(FOAM_Def, 2, foamCopy(new), foamCopy(self))
332 foamCopy(self))foamNew(FOAM_Def, 2, foamCopy(new), foamCopy(self)), info->inits);
333 info->finis = listCons(Foam)(Foam_listPointer->Cons)(foamNewSet(foamCopy(self),foamNew(FOAM_Set, 2, foamCopy(self), foamCopy(new))
334 foamCopy(new))foamNew(FOAM_Set, 2, foamCopy(self), foamCopy(new)), info->finis);
335
336 foamFree(new);
337 foamFree(self);
338}
339
340localstatic Foam
341gen0FixMakeDummyCat()
342{
343 return gen0BuiltinCCall(FOAM_Word, "categoryMakeDummy", "runtime", int0((int) 0));
344}
345
346localstatic Foam
347gen0FixFillCat(Foam new, Foam self)
348{
349 return gen0BuiltinCCall(FOAM_NOp, "categoryFill!", "runtime", 2, new, self);
350}
351
352localstatic Foam
353gen0FixMakeDummyDom()
354{
355 return gen0BuiltinCCall(FOAM_Word, "domainMakeDummy", "runtime", int0((int) 0));
356}
357
358localstatic Foam
359gen0FixFillDom(Foam new, Foam self)
360{
361 return gen0BuiltinCCall(FOAM_NOp, "domainFill!", "runtime", 2, new, self);
362}
363
364
365localstatic void
366gen0FixGenStmts(FoamList lst, AbSyn pos)
367{
368 while (lst) {
369 gen0AddStmt(car(lst)((lst)->first), pos);
370 lst = cdr(lst)((lst)->rest);
371 }
372}
373
374/******************************************************************************
375 *
376 * :: DefGroup/Set manipulation
377 *
378 *****************************************************************************/
379
380/*
381 * Two stages in defining a top level export
382 * 1. Defining
383 * 2. Exporting
384 *
385 * Defining is safe providing all the symes used by the definition
386 * have either been defined or imported, or the defn is a with, add or lambda
387 *
388 * Exporting is safe providing all the symes used in the type of the
389 * definition have been defined.
390 *
391 * 'Used' here is a closure over the textual definition ignoring lambda-inducing
392 * constructs. [NB this is not sufficient for absolute safety]
393 *
394 * We also must try to spot mutual recursion in definitions of types.
395 * In this situation an AB_Fix node is created, which can then be dealt with by
396 * gf_add.c
397 *
398 * Sort process:
399 * 1) Find dependencies
400 * 2) Compute dependencies, NB subsumption
401 * 3) Sort
402 * 4) transform to linear format
403 *
404 * We sort into the following groups:
405 * Tough maps (list[0]) (domain/category DG_Const -> DG_Fix)
406 * Simple maps (list[1]) (DG_Lambda)
407 * Types (list[2]) (DG_Type)
408 * Other junk (list[3]) (DG_Const, DG_Cond)
409 * Non-definitions (list[4]) (DG_NonDefn)
410 *
411 * Locals used to be lumped together with "other junk" as DG_Const nodes.
412 * Then local lambda's were split into a group of their own after DG_Type.
413 * Simple locals (just one local being defined) are now placed in their
414 * proper group (local lambdas go in DG_Lambda, local consts in "other junk"
415 * etc); complicated locals stay in "other junk" unless they are DG_NonDefn.
416 *
417 * It would be nice if we could use dgProcessDependencies() to re-order
418 * the non-lazy constants so that their values are correctly computed.
419 * Unfortunately some people write code in add bodies in which non-lazy
420 * constants depend on the values of local variables. Thus re-ordering
421 * is not viable.
422 *
423 * Instead, we now place all members of "other junk" in with "non-defns"
424 * for the overall sorting operation. We also take a separate copy of
425 * "other junk" and perform dependency analysis to check for user bugs.
426 */
427CREATE_LIST(DefGroup)struct DefGroup_listOpsStruct const *DefGroup_listPointer = (
struct DefGroup_listOpsStruct const *) &ptrlistOps;
428
429#define DG_GROUP_TOUGH_MAP(0) (0)
430#define DG_GROUP_SIMPLE_MAP(1) (1)
431#define DG_GROUP_TYPE(2) (2)
432#define DG_GROUP_OTHER_JUNK(3) (3)
433#define DG_GROUP_NON_DEFN(4) (4)
434
435#define DG_MAX((4)+1) (DG_GROUP_NON_DEFN(4)+1)
436
437static SymeList dgExports;
438
439localstatic void
440dgSortDefs(DefSet set)
441{
442 int i;
443 DefGroupList otherJunk = listNil(DefGroup)((DefGroupList) 0);
444 DefGroupList lists[DG_MAX((4)+1)];
445 DefGroupList lst = dgSetDefs(set)((set)->defs);
446 DefGroup types;
447
448 for (i=0; i<DG_MAX((4)+1); i++)
449 lists[i]=listNil(DefGroup)((DefGroupList) 0);
450
451
452#if SORT_NON_LAZY_CONSTANTS
453 /*
454 * This code separates non-lazy constants from other
455 * non-definitions in an add-body before sorting them
456 * so that their dependencies will be satisfied when
457 * code generation takes place. Note that this causes
458 * severe problems when people write code in which
459 * non-lazy constants depend on the value of variables.
460 */
461 while (lst) {
462 DefGroup dg = car(lst)((lst)->first);
463
464
465 /* Classify into one of the sets */
466 i = dgSortClassify(dg);
467
468
469 /* Add to the chosen set */
470 lists[i] = listCons(DefGroup)(DefGroup_listPointer->Cons)(dg, lists[i]);
471
472
473 /* Get the next group */
474 lst = cdr(lst)((lst)->rest);
475 }
476
477
478 /* The "other junk" group needs special care */
479 tmp = lists[DG_GROUP_OTHER_JUNK(3)];
480 tmp = dgProcessDependencies(tmp, true1);
481 lists[DG_GROUP_OTHER_JUNK(3)] = tmp;
482#else
483 /*
484 * This code keeps non-lazy constants in the same
485 * set as other non-definitions in an add-body and
486 * does not sort them. However, these constants
487 * are recorded separately and analysed for bad
488 * dependencies.
489 */
490 while (lst) {
491 DefGroup dg = car(lst)((lst)->first);
492
493
494 /* Classify into one of the sets */
495 i = dgSortClassify(dg);
496
497
498 /* DG_GROUP_OTHER_JUNK is treated differently */
499 if (i == DG_GROUP_OTHER_JUNK(3)) {
500 /* Record DG_GROUP_OTHER_JUNK separately */
501 otherJunk = listCons(DefGroup)(DefGroup_listPointer->Cons)(dg, otherJunk);
502
503
504 /* But also place them with DG_GROUP_NON_DEFN */
505 i = DG_GROUP_NON_DEFN(4);
506 }
507
508
509 /* Add to the relevent set */
510 lists[i] = listCons(DefGroup)(DefGroup_listPointer->Cons)(dg, lists[i]);
511
512
513 /* Get the next group */
514 lst = cdr(lst)((lst)->rest);
515 }
516
517
518 /* Check for bad dependencies */
519 assert(!lists[DG_GROUP_OTHER_JUNK])do { if (!(!lists[(3)])) _do_assert(("!lists[DG_GROUP_OTHER_JUNK]"
),"gf_seq.c",519); } while (0);
520 otherJunk = dgProcessDependencies(otherJunk, false((int) 0));
521 listFree(DefGroup)(DefGroup_listPointer->Free)(otherJunk);
522#endif
523
524
525 /* Concatenate the simple groups (assume !DG_GROUP_TOUGH_MAP) */
526 assert(!lst)do { if (!(!lst)) _do_assert(("!lst"),"gf_seq.c",526); } while
(0);
527 for (i = DG_MAX((4)+1) - 1; i; i--) {
528 DefGroupList tmp = listNReverse(DefGroup)(DefGroup_listPointer->NReverse)(lists[i]);
529 lst = listNConcat(DefGroup)(DefGroup_listPointer->NConcat)(tmp, lst);
530 }
531
532
533 /* Tough maps require special care */
534 if (lists[DG_GROUP_TOUGH_MAP(0)]) {
535 types = dgMakeFixGroup(lists[DG_GROUP_TOUGH_MAP(0)]);
536 lst = listCons(DefGroup)(DefGroup_listPointer->Cons)(types, lst);
537 listFreeDeeply(DefGroup)(DefGroup_listPointer->FreeDeeply)(lists[DG_GROUP_TOUGH_MAP(0)],dgFreeGroup);
538 }
539
540 dgSetDefs(set)((set)->defs) = lst;
541}
542
543
544localstatic int
545dgSortClassify(DefGroup dg)
546{
547 SymeList lst;
548 TForm tf;
549 int class;
550
551 if (dgTag(dg)((dg)->tag) == DG_Lambda)
552 return DG_GROUP_SIMPLE_MAP(1);
553 else if (dgTag(dg)((dg)->tag) == DG_Type)
554 return DG_GROUP_TYPE(2);
555 else if (dgTag(dg)((dg)->tag) == DG_NonDefn)
556 return DG_GROUP_NON_DEFN(4);
557
558
559 lst = dg->defines;
560 class = DG_GROUP_OTHER_JUNK(3);
561
562 while (lst) {
563 tf = tfDefineeType(symeType(car(lst)((lst)->first)));
564 if (tfSatDom(tf) || tfSatCat(tf))
565 class = DG_GROUP_TOUGH_MAP(0);
566 lst = cdr(lst)((lst)->rest);
567 }
568 return class;
569}
570
571localstatic DefGroupList
572dgSeqToDefs(AbSyn ab)
573{
574 DefGroupList lst = listNil(DefGroup)((DefGroupList) 0);
575 int i;
576
577 switch(abTag(ab)((ab)->abHdr.tag)) {
578 case AB_Sequence:
579 case AB_Default:
580 for (i = 0; i < abArgc(ab)((ab)->abHdr.argc); i++) {
581 AbSyn sub = ab->abSequence.argv[i];
582 lst = listNConcat(DefGroup)(DefGroup_listPointer->NConcat)(dgSeqToDefs(sub), lst);
583 }
584 break;
585 default:
586 lst = listCons(DefGroup)(DefGroup_listPointer->Cons)(dgStmtToDef(ab, int0((int) 0)), lst);
587 }
588
589
590 /*
591 * This function may be applied to nested sequences. To
592 * ensure that all the definitions stay in the same order
593 * as in the source code, it is essential that the list
594 * is not reversed during recursive calls. Instead the
595 * result of the top-level call must be reversed.
596 */
597 return lst;
598}
599
600localstatic DefSet
601dgSeqToDefSet(AbSyn ab, SymeList exports)
602{
603 DefSet new = (DefSet) stoAlloc(OB_Other0, sizeof(*new));
604
605 dgExports = exports;
606 new->argc = 0;
607 new->defs = listNReverse(DefGroup)(DefGroup_listPointer->NReverse)(dgSeqToDefs(ab));
608 new->exports = exports;
609 dgExports = NULL((void*)0);
610
611 return new;
612}
613
614
615localstatic DefGroup
616dgMakeFixGroup(DefGroupList dlst)
617{
618 AbSynList stmts = listNil(AbSyn)((AbSynList) 0);
619 SymeList defines = listNil(Syme)((SymeList) 0);
620 SymeList uses = listNil(Syme)((SymeList) 0);
621 SymeList lst;
622 DefGroup new;
623 int ordinal = 0;
624
625 while (dlst) {
626 DefGroup dg = car(dlst)((dlst)->first);
627 stmts = listCons(AbSyn)(AbSyn_listPointer->Cons)(dg->ab, stmts);
628 defines = listConcat(Syme)(Syme_listPointer->Concat)(dg->defines, defines);
629 uses = listConcat(Syme)(Syme_listPointer->Concat)(dg->usedSymes, uses);
630 ordinal = ordinal < dg->ordinal ? dg->ordinal : ordinal;
631
632 dlst = cdr(dlst)((dlst)->rest);
633 }
634 new = dgNewGroup(DG_Fix, abNewOfList(AB_Fix, sposNone,
635 listNReverse(AbSyn)(AbSyn_listPointer->NReverse)(stmts)));
636
637 lst = uses;
638 uses = listNil(Syme)((SymeList) 0);
639 while (lst) {
640 if (!listMemq(Syme)(Syme_listPointer->Memq)(defines, car(lst)((lst)->first)))
641 uses = listCons(Syme)(Syme_listPointer->Cons)(car(lst)((lst)->first), uses);
642 lst = cdr(lst)((lst)->rest);
643 }
644 new->defines = defines;
645 new->usedSymes = uses;
646 new->ordinal = ordinal;
647
648 return new;
649}
650
651localstatic DefGroup
652dgStmtToDef(AbSyn absyn, int i)
653{
654 DefGroup dg = dgNewGroup(dgGetTag(absyn), absyn);
655
656 dgAbGetUsedSymes(absyn, dg, true1);
657 if (dg->tag == DG_Cond) {
658 listFree(Syme)(Syme_listPointer->Free)(dg->defines);
659 dg->defines = listNil(Syme)((SymeList) 0);
660 }
661 dg->ordinal = i;
662 return dg;
663}
664
665
666localstatic Bool dgAbIsTopLevel(AbSyn ab);
667
668localstatic void
669dgAbGetUsedSymes(AbSyn ab, DefGroup dg, Bool topLevel)
670{
671 Syme syme;
672 int i, argc;
673 AbSyn *argv;
674
675 switch(abTag(ab)((ab)->abHdr.tag)) {
676 case AB_Add:
677 case AB_With:
678 case AB_Generate:
679 case AB_Lambda:
680 case AB_PLambda:
681 return;
682
683 case AB_Define:
684 /* Treat all definitions as a multi */
685 argc = abArgcAs(AB_Comma, ab->abDefine.lhs)(((ab->abDefine.lhs)->abHdr.tag == (AB_Comma)) ? ((ab->
abDefine.lhs)->abHdr.argc) : 1);
686 argv = abArgvAs(AB_Comma, ab->abDefine.lhs)(((ab->abDefine.lhs)->abHdr.tag == (AB_Comma)) ? ((ab->
abDefine.lhs)->abGen.data.argv) : &(ab->abDefine.lhs
));
687
688
689 /* Find out all the things being defined */
690 for (i = 0; i < argc; i++) {
691 syme = abSyme(abDefineeId(argv[i]))((abDefineeId(argv[i]))->abHdr.seman ? (abDefineeId(argv[i
]))->abHdr.seman->syme : 0);
692 if (!syme) continue;
693 if (topLevel)
694 dg->defines = listCons(Syme)(Syme_listPointer->Cons)(syme, dg->defines);
695 }
696
697
698 /* Now find all the symes used from the rhs */
699 dgAbGetUsedSymes(ab->abDefine.rhs, dg, topLevel);
700 break;
701
702 case AB_LitInteger:
703 case AB_LitString:
704 case AB_LitFloat:
705 case AB_Id:
706 if ((syme = abSyme(ab)((ab)->abHdr.seman ? (ab)->abHdr.seman->syme : 0)) != NULL((void*)0) && dgSymeIsLocal(syme)) {
707 dg->usedSymes = listCons(Syme)(Syme_listPointer->Cons)(syme, dgUses(dg)((dg)->usedSymes));
708 }
709 break;
710 case AB_CoerceTo:
711 case AB_Test:
712 case AB_For:
713 if ( (syme = abImplicitSyme(ab)(((ab)->abHdr.seman ? (ab)->abHdr.seman->implicit : 0
) ? ((((ab)->abHdr.seman ? (ab)->abHdr.seman->implicit
: 0))->abHdr.seman ? (((ab)->abHdr.seman ? (ab)->abHdr
.seman->implicit : 0))->abHdr.seman->syme : 0) : 0)) != NULL((void*)0) && dgSymeIsLocal(syme))
714 dg->usedSymes = listCons(Syme)(Syme_listPointer->Cons)(syme, dgUses(dg)((dg)->usedSymes));
715 for (i=0; i<abArgc(ab)((ab)->abHdr.argc); i++)
716 dgAbGetUsedSymes(abArgv(ab)((ab)->abGen.data.argv)[i], dg, topLevel);
717 break;
718 default:
719 if ((syme = abSyme(ab)((ab)->abHdr.seman ? (ab)->abHdr.seman->syme : 0)) != NULL((void*)0) && dgSymeIsLocal(syme)) {
720 dg->usedSymes = listCons(Syme)(Syme_listPointer->Cons)(syme, dgUses(dg)((dg)->usedSymes));
721 }
722 for (i=0; i<abArgc(ab)((ab)->abHdr.argc); i++)
723 dgAbGetUsedSymes(abArgv(ab)((ab)->abGen.data.argv)[i], dg, topLevel && dgAbIsTopLevel(ab));
724 break;
725 }
726}
727
728localstatic Bool
729dgAbIsTopLevel(AbSyn ab)
730{
731 switch (abTag(ab)((ab)->abHdr.tag)) {
732 case AB_Apply:
733 case AB_Where:
734 return false((int) 0);
735 default:
736 return true1;
737 }
738}
739
740localstatic DefGroupTag
741dgGetTag(AbSyn absyn)
742{
743 switch(abTag(absyn)((absyn)->abHdr.tag)) {
744 case AB_Fix:
745 return DG_Fix;
746 case AB_Define:
747 switch (abTag(absyn->abDefine.rhs)((absyn->abDefine.rhs)->abHdr.tag)) {
748 case AB_Lambda:
749 case AB_PLambda:
750 return DG_Lambda;
751 case AB_Add:
752 case AB_With:
753 return DG_Type;
754 default:
755 return DG_Const;
756 }
757 case AB_If:
758 return DG_Cond;
759 case AB_Local: {
760 /* Can only handle simple locals */
761 if (abArgc(absyn)((absyn)->abHdr.argc) != 1)
762 return DG_Const; /* can do better than this ... */
763
764 /* Return the tag of the local object */
765 return dgGetTag(absyn->abLocal.argv[0]);
766 }
767 default:
768 return DG_NonDefn;
769 }
770}
771
772localstatic Bool
773dgSymeIsLocal(Syme syme)
774{
775 if (symeIsParam(syme)(((((syme)->kind == SYME_Trigger ? libGetAllSymes((syme)->
lib) : ((void*)0)), (syme))->kind) == SYME_Param) || symeIsImport(syme)(((((syme)->kind == SYME_Trigger ? libGetAllSymes((syme)->
lib) : ((void*)0)), (syme))->kind) == SYME_Import))
776 return false((int) 0);
777 if (symeIsExport(syme)(((((syme)->kind == SYME_Trigger ? libGetAllSymes((syme)->
lib) : ((void*)0)), (syme))->kind) == SYME_Export) && !listMemq(Syme)(Syme_listPointer->Memq)(dgExports, syme))
778 return false((int) 0);
779
780 return true1;
781
782}
783
784localstatic DefGroup
785dgNewGroup(DefGroupTag tag, AbSyn ab)
786{
787 DefGroup new;
788
789 new = (DefGroup) stoAlloc(OB_Other0, sizeof(*new));
790
791 new->tag = tag;
792 new->ab = ab;
793 new->usedSymes = NULL((void*)0);
794 new->defines = NULL((void*)0);
795 new->ordinal = -1;
796
797 return new;
798}
799
800localstatic void
801dgFreeGroup(DefGroup dg)
802{
803 listFree(Syme)(Syme_listPointer->Free)(dg->defines);
804 listFree(Syme)(Syme_listPointer->Free)(dg->usedSymes);
805
806 stoFree(dg);
807}
808
809
810/******************************************************************************
811 *
812 * :: Dependency analysis
813 *
814 *****************************************************************************/
815
816
817/*
818 * Analyse the dependencies between a set of DG_Const and DG_Cond
819 * groups and return them correctly sorted. If `reOrder' is false
820 * then it is an error if a defgroup depends on one that has a
821 * higher ordinal (was defined later in the code).
822 */
823localstatic DefGroupList
824dgProcessDependencies(DefGroupList defs, Bool reOrder)
825{
826 int ord = -10;
827 DepDag root;
828 Table symeToDegDag;
829 DefGroupList result = listNil(DefGroup)((DefGroupList) 0);
830
831
832 /* Create a new mapping table */
833 symeToDegDag = tblNew((TblHashFun)symeHashFn, (TblEqFun)symeEqual);
834
835
836 /* Root dag node with no dependencies */
837 root = depdagNewLeaf((void *)NULL((void*)0));
838
839
840 /*
841 * Phase 1: compute the mapping from symes to defgroups
842 * and add the dependencies of the root node. Each group
843 * is numbered such that the first defgroup in the source
844 * has the lowest number.
845 */
846 listIter(DefGroup, dg, defs, {{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
847 AbSyn absyn = dgStmt(dg);{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
848 Syme syme = dgGetAbMeaning(absyn);{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
849 DepDag node = depdagNewLeaf((void *)dg);{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
850
851
852 /* Number the defgroup */{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
853 dg->ordinal = --ord;{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
854
855
856 /* Add root dependency */{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
857 root = depdagAddDependency(root, node);{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
858
859
860 /*{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
861 * Only index meaningful dgs. The side-effect of this{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
862 * is that we only find dependencies between dgs that{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
863 * have meaning.{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
864 */{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
865 if (syme) tblSetElt(symeToDegDag, (TblKey)syme, (TblElt)node);{ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; }
866 }){ { DefGroupList _l0; DefGroup dg; for (_l0 = (defs); _l0; _l0
= ((_l0)->rest)) { dg = ((_l0)->first); { { AbSyn absyn
= ((dg)->ab); Syme syme = dgGetAbMeaning(absyn); DepDag node
= depdagNewLeaf((void *)dg); dg->ordinal = --ord; root = depdagAddDependency
(root, node); if (syme) tblSetElt(symeToDegDag, (TblKey)syme,
(TblElt)node); }; }; } }; };
867
868
869 /* Phase 2: compute dependencies */
870 listIter(DepDag, dd, depdagDependsOn(root), {{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
871 DefGroup dg = (DefGroup)depdagLabel(dd);{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
872 AbSyn absyn = dgStmt(dg);{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
873 SymeList deps = dgFindDependencies(absyn);{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
874
875
876 /* Skip if no dependencies found */{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
877 if (!deps) continue;{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
878
879
880 /* Add each dependency */{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
881 listIter(Syme, syme, deps, {{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
882 DepDag dag;{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
883
884
885 /* Search for the defgroup */{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
886 dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)NULL);{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
887
888
889 /* Skip if not found */{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
890 if (!dag) continue;{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
891
892
893 /* Add the dependency */{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
894 dd = depdagAddDependency(dd, dag);{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
895 });{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
896
897
898 /* Release storage */{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
899 listFree(Syme)(deps);{ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; }
900 }){ { DepDagList _l0; DepDag dd; for (_l0 = (((root)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { dd = ((_l0)->first); { {
DefGroup dg = (DefGroup)((dd)->label); AbSyn absyn = ((dg
)->ab); SymeList deps = dgFindDependencies(absyn); if (!deps
) continue; { { SymeList _l0; Syme syme; for (_l0 = (deps); _l0
; _l0 = ((_l0)->rest)) { syme = ((_l0)->first); { { DepDag
dag; dag = tblElt(symeToDegDag, (TblKey)syme, (TblElt)((void
*)0)); if (!dag) continue; dd = depdagAddDependency(dd, dag);
}; }; } }; }; (Syme_listPointer->Free)(deps); }; }; } }; };
901
902
903 /* Phase 3: sort */
904 result = dgSortDependencies(root, listNil(DepDag)((DepDagList) 0), reOrder);
905
906
907 /*
908 * Phase 4: clean up. Note that the peculiar nature of
909 * this dependency graph is that all nodes are children
910 * of the root node. We don't have to walk the graph
911 * to find nodes to free.
912 */
913 listFree(DepDag)(DepDag_listPointer->Free)(depdagDependsOn(root)((root)->dependsOn));
914 depdagFree(root);
915 tblFree(symeToDegDag);
916
917
918 /* Return the sorted list */
919 return listNReverse(DefGroup)(DefGroup_listPointer->NReverse)(result);
920}
921
922
923/*
924 * dgSortDependencies(dag, deps, reOrder) produces a sorted list of
925 * def-groups from the dependency DAG "dag". If the caller doesn't
926 * want dependencies re-ordered then "reOrder" must be false and this
927 * function generates an error if a valid sort cannot be computed
928 * without re-ordering definitions. The "deps" parameter is a list
929 * of dependencies which are pending and is used simply for telling
930 * the user which nodes occur in a cycle in the graph if one is found.
931 */
932localstatic DefGroupList
933dgSortDependencies(DepDag dag, DepDagList depends, Bool reOrder)
934{
935 DefGroupList tmp;
936 DefGroupList result = listNil(DefGroup)((DefGroupList) 0);
937 DefGroup us = (DefGroup)depdagLabel(dag)((dag)->label);
938 DepDagList deps = depends;
939 DepDagList orders = listNil(DepDag)((DepDagList) 0);
940
941
942 /* Have we been here before and finished? */
943 if (depdagIsFinished(dag)((dag)->finished)) return result;
944
945
946 /* Have we been here before and not finished? */
947 if (depdagIsPending(dag)((dag)->pending)) {
948 /* Cycle in dependency graph: report the error */
949 dgCycleError(dag, depends);
950
951
952 /* Ignore this dependency */
953 return result;
954 }
955
956
957 /* Add ourselves to the dependency chain (if not the root) */
958 if (us) deps = listCons(DepDag)(DepDag_listPointer->Cons)(dag, deps);
959
960
961 /* Indicate that we are processing this node */
962 depdagSetPending(dag, true)(((dag)->pending) = 1);
963
964
965 /* Process our dependencies first */
966 listIter(DepDag, d, depdagDependsOn(dag), {{ { DepDagList _l0; DepDag d; for (_l0 = (((dag)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { d = ((_l0)->first); { {
DefGroup dg = (DefGroup)((d)->label); if (!reOrder &&
us && (dg->ordinal > us->ordinal)) orders =
(DepDag_listPointer->Cons)(d, orders); tmp = dgSortDependencies
(d, deps, reOrder); if (tmp) result = (DefGroup_listPointer->
NConcat)(result, tmp); }; }; } }; }
967 /* Convert into a defgroup */{ { DepDagList _l0; DepDag d; for (_l0 = (((dag)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { d = ((_l0)->first); { {
DefGroup dg = (DefGroup)((d)->label); if (!reOrder &&
us && (dg->ordinal > us->ordinal)) orders =
(DepDag_listPointer->Cons)(d, orders); tmp = dgSortDependencies
(d, deps, reOrder); if (tmp) result = (DefGroup_listPointer->
NConcat)(result, tmp); }; }; } }; }
968 DefGroup dg = (DefGroup)depdagLabel(d);{ { DepDagList _l0; DepDag d; for (_l0 = (((dag)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { d = ((_l0)->first); { {
DefGroup dg = (DefGroup)((d)->label); if (!reOrder &&
us && (dg->ordinal > us->ordinal)) orders =
(DepDag_listPointer->Cons)(d, orders); tmp = dgSortDependencies
(d, deps, reOrder); if (tmp) result = (DefGroup_listPointer->
NConcat)(result, tmp); }; }; } }; }
969
970
971 /* Check for dependency ordering errors */{ { DepDagList _l0; DepDag d; for (_l0 = (((dag)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { d = ((_l0)->first); { {
DefGroup dg = (DefGroup)((d)->label); if (!reOrder &&
us && (dg->ordinal > us->ordinal)) orders =
(DepDag_listPointer->Cons)(d, orders); tmp = dgSortDependencies
(d, deps, reOrder); if (tmp) result = (DefGroup_listPointer->
NConcat)(result, tmp); }; }; } }; }
972 if (!reOrder && us && (dg->ordinal > us->ordinal)){ { DepDagList _l0; DepDag d; for (_l0 = (((dag)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { d = ((_l0)->first); { {
DefGroup dg = (DefGroup)((d)->label); if (!reOrder &&
us && (dg->ordinal > us->ordinal)) orders =
(DepDag_listPointer->Cons)(d, orders); tmp = dgSortDependencies
(d, deps, reOrder); if (tmp) result = (DefGroup_listPointer->
NConcat)(result, tmp); }; }; } }; }
973 orders = listCons(DepDag)(d, orders);{ { DepDagList _l0; DepDag d; for (_l0 = (((dag)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { d = ((_l0)->first); { {
DefGroup dg = (DefGroup)((d)->label); if (!reOrder &&
us && (dg->ordinal > us->ordinal)) orders =
(DepDag_listPointer->Cons)(d, orders); tmp = dgSortDependencies
(d, deps, reOrder); if (tmp) result = (DefGroup_listPointer->
NConcat)(result, tmp); }; }; } }; }
974
975
976 /* Sort the dependencies */{ { DepDagList _l0; DepDag d; for (_l0 = (((dag)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { d = ((_l0)->first); { {
DefGroup dg = (DefGroup)((d)->label); if (!reOrder &&
us && (dg->ordinal > us->ordinal)) orders =
(DepDag_listPointer->Cons)(d, orders); tmp = dgSortDependencies
(d, deps, reOrder); if (tmp) result = (DefGroup_listPointer->
NConcat)(result, tmp); }; }; } }; }
977 tmp = dgSortDependencies(d, deps, reOrder);{ { DepDagList _l0; DepDag d; for (_l0 = (((dag)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { d = ((_l0)->first); { {
DefGroup dg = (DefGroup)((d)->label); if (!reOrder &&
us && (dg->ordinal > us->ordinal)) orders =
(DepDag_listPointer->Cons)(d, orders); tmp = dgSortDependencies
(d, deps, reOrder); if (tmp) result = (DefGroup_listPointer->
NConcat)(result, tmp); }; }; } }; }
978
979
980 /* Add to the result list if found */{ { DepDagList _l0; DepDag d; for (_l0 = (((dag)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { d = ((_l0)->first); { {
DefGroup dg = (DefGroup)((d)->label); if (!reOrder &&
us && (dg->ordinal > us->ordinal)) orders =
(DepDag_listPointer->Cons)(d, orders); tmp = dgSortDependencies
(d, deps, reOrder); if (tmp) result = (DefGroup_listPointer->
NConcat)(result, tmp); }; }; } }; }
981 if (tmp) result = listNConcat(DefGroup)(result, tmp);{ { DepDagList _l0; DepDag d; for (_l0 = (((dag)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { d = ((_l0)->first); { {
DefGroup dg = (DefGroup)((d)->label); if (!reOrder &&
us && (dg->ordinal > us->ordinal)) orders =
(DepDag_listPointer->Cons)(d, orders); tmp = dgSortDependencies
(d, deps, reOrder); if (tmp) result = (DefGroup_listPointer->
NConcat)(result, tmp); }; }; } }; }
982 }){ { DepDagList _l0; DepDag d; for (_l0 = (((dag)->dependsOn
)); _l0; _l0 = ((_l0)->rest)) { d = ((_l0)->first); { {
DefGroup dg = (DefGroup)((d)->label); if (!reOrder &&
us && (dg->ordinal > us->ordinal)) orders =
(DepDag_listPointer->Cons)(d, orders); tmp = dgSortDependencies
(d, deps, reOrder); if (tmp) result = (DefGroup_listPointer->
NConcat)(result, tmp); }; }; } }; };
983
984
985 /* Emit ordering errors in one go */
986 if (orders) {
987 dgOrderError(dag, orders);
988 listFree(DepDag)(DepDag_listPointer->Free)(orders);
989 }
990
991
992 /* Remove ourselves from the dependency chain (if not the root) */
993 if (us) deps = listFreeCons(DepDag)(DepDag_listPointer->FreeCons)(deps);
Value stored to 'deps' is never read
994
995
996 /* Add ourselves to the list (if not the root) */
997 us = (DefGroup)depdagLabel(dag)((dag)->label);
998 if (us) {
999 tmp = listSingleton(DefGroup)(DefGroup_listPointer->Singleton)(us);
1000 result = listNConcat(DefGroup)(DefGroup_listPointer->NConcat)(result, tmp);
1001 }
1002
1003
1004 /*
1005 * Indicate that we have finished processing this node. We
1006 * clear the pending flag for tidiness but don't have to.
1007 */
1008 depdagSetFinished(dag, true)(((dag)->finished) = 1);
1009 depdagSetPending(dag, false)(((dag)->pending) = ((int) 0));
1010
1011
1012 /* Return the sorted list */
1013 return result;
1014}
1015
1016
1017localstatic void
1018dgCycleError(DepDag dag, DepDagList deps)
1019{
1020 Buffer buf = bufNew();
1021 String pretty;
1022 DefGroup dg = (DefGroup)depdagLabel(dag)((dag)->label);
1023 DepDagList ptr, cycle = listSingleton(DepDag)(DepDag_listPointer->Singleton)(dag);
1024
1025
1026 /* Root cannot be pending */
1027 assert(deps)do { if (!(deps)) _do_assert(("deps"),"gf_seq.c",1027); } while
(0);
1028 assert(dg)do { if (!(dg)) _do_assert(("dg"),"gf_seq.c",1028); } while (
0);
1029
1030
1031 /* Compute the dependency cycle */
1032 for (;deps && (car(deps)((deps)->first) != dag);deps = cdr(deps)((deps)->rest)) {
1033 DepDag d = car(deps)((deps)->first);
1034 cycle = listCons(DepDag)(DepDag_listPointer->Cons)(d, cycle);
1035 }
1036
1037
1038 /* Start with the bad dependency source/target */
1039 pretty = dgPretty(dg);
1040 bufPrintf(buf, "<%s, ", pretty);
1041 strFree(pretty);
1042
1043
1044 /* Display the dependency cycle */
1045 for (ptr = cycle; ptr; ptr = cdr(ptr)((ptr)->rest)) {
1046 DepDag d = car(ptr)((ptr)->first);
1047 DefGroup dg = (DefGroup)depdagLabel(d)((d)->label);
1048
1049
1050 /* Format this node */
1051 pretty = dgPretty(dg);
1052 bufPrintf(buf, "%s", pretty);
1053 strFree(pretty);
1054
1055
1056 /* Any more nodes in this cycle? */
1057 if (cdr(ptr)((ptr)->rest)) bufPrintf(buf, ", ");
1058 }
1059 bufPrintf(buf, ">");
1060
1061
1062 /* Release storage used */
1063 listFree(DepDag)(DepDag_listPointer->Free)(cycle);
1064
1065
1066 /* Report the error */
1067 comsgWarning(dgStmt(dg)((dg)->ab), ALDOR_W_GenBadDefCycle240, bufChars(buf));
1068
1069
1070 /* Free the buffer */
1071 bufLiberate(buf);
1072}
1073
1074
1075localstatic void
1076dgOrderError(DepDag dag, DepDagList deps)
1077{
1078 Buffer buf = bufNew();
1079 String pretty, s;
1080 DefGroup dg = (DefGroup)depdagLabel(dag)((dag)->label);
1081 DepDagList ptr, order = listNil(DepDag)((DepDagList) 0);
1082
1083
1084 /* Root cannot be pending */
1085 assert(deps)do { if (!(deps)) _do_assert(("deps"),"gf_seq.c",1085); } while
(0);
1086 assert(dg)do { if (!(dg)) _do_assert(("dg"),"gf_seq.c",1086); } while (
0);
1087
1088
1089 /* Re-order the dependency list */
1090 for (;deps;deps = cdr(deps)((deps)->rest)) {
1091 DepDag d = car(deps)((deps)->first);
1092 order = listCons(DepDag)(DepDag_listPointer->Cons)(d, order);
1093 }
1094
1095
1096 /* Display the dependencies */
1097 for (ptr = order; ptr; ptr = cdr(ptr)((ptr)->rest)) {
1098 DepDag d = car(ptr)((ptr)->first);
1099 DefGroup dg = (DefGroup)depdagLabel(d)((d)->label);
1100
1101
1102 /* Format this node */
1103 pretty = dgPretty(dg);
1104 bufPrintf(buf, "`%s'", pretty);
1105 strFree(pretty);
1106
1107
1108 /* Any more nodes in this cycle? */
1109 if (cdr(ptr)((ptr)->rest)) {
1110 if (cdr(cdr(ptr))((((ptr)->rest))->rest))
1111 bufPrintf(buf, ", ");
1112 else
1113 bufPrintf(buf, " and ");
1114 }
1115 }
1116
1117
1118 /* Release storage used */
1119 listFree(DepDag)(DepDag_listPointer->Free)(order);
1120
1121
1122 /* Name of the problem definition */
1123 s = dgPretty(dg);
1124
1125
1126 /* Report the error */
1127 comsgWarning(dgStmt(dg)((dg)->ab), ALDOR_W_GenBadDefOrder241, s, bufChars(buf), s);
1128
1129
1130 /* Free the buffer and other storage */
1131 bufLiberate(buf);
1132 strFree(s);
1133}
1134
1135
1136/*
1137 * Pretty-print the symbol associated with a def-group for use in
1138 * error messages about cyclic dependencies. We assume that this
1139 * node has meaning: if it didn't we would not have been able to
1140 * work out that there is a cycle involved.
1141 */
1142localstatic String
1143dgPretty(DefGroup dg)
1144{
1145 /* name: type */
1146 AbSyn absyn;
1147 Syme syme;
1148 String name, type, result;
1149
1150
1151 /* Extract the syme for this definition */
1152 absyn = dgStmt(dg)((dg)->ab);
1153 syme = dgGetAbMeaning(absyn);
1154
1155
1156 /* Paranoia */
1157 assert(syme)do { if (!(syme)) _do_assert(("syme"),"gf_seq.c",1157); } while
(0);
1158
1159
1160 /* Create the text "name:Type" */
1161 name = symString(symeId(syme))((((syme)->id))->str);
1162 type = tfPretty(symeType(syme));
1163 result = strlConcat(name, ":", type, (String)NULL((void*)0));
1164
1165
1166 /* Free the text associated with the type */
1167 strFree(type);
1168
1169
1170 /* Return the pretty text */
1171 return result;
1172
1173}
1174
1175
1176/*
1177 * Try to find the meaning of a piece of absyn. The absyn
1178 * will probably be associated with a def-group and will
1179 * most likely be a constant definition. We want the syme
1180 * for the symbol being defined or NULL if not found.
1181 */
1182localstatic Syme
1183dgGetAbMeaning(AbSyn absyn)
1184{
1185 AbSyn id;
1186
1187 /* Search for the identifier in this absyn */
1188 id = abDefineeIdOrElse(absyn, (AbSyn)NULL((void*)0));
1189
1190
1191 /* Return the meaning of the absyn, if known */
1192 return id ? abSyme(id)((id)->abHdr.seman ? (id)->abHdr.seman->syme : 0) : (Syme)NULL((void*)0);
1193}
1194
1195
1196/*
1197 * Convert an import syme into the corresponding export
1198 * syme used as indices into the dependency graph.
1199 */
1200localstatic Syme
1201dgSymeImportToExport(Syme syme)
1202{
1203 SymeList symes;
1204 TForm exporter, tf = symeType(syme);
1205
1206
1207 /* Get the exporter of this syme */
1208 exporter = symeExporter(syme);
1209
1210
1211 /* If can't find exporter, return untouched */
1212 if (!exporter) return syme;
1213
1214
1215 /* Get the constants defined in the exporter */
1216 symes = tfGetDomConstants(exporter);
1217
1218
1219 /* If no constants, return untouched */
1220 if (!symes) return syme;
1221
1222
1223 /* Search constants for this import */
1224 for (;symes;symes = cdr(symes)((symes)->rest)) {
1225 Syme esyme = car(symes)((symes)->first);
1226
1227
1228 /* Do the symbols match? */
1229 if (symeId(esyme)((esyme)->id) != symeId(syme)((syme)->id)) continue;
1230
1231
1232 /* Check the types match */
1233 if (!tfEqual(symeType(esyme), tf)) continue;
1234
1235
1236 /* Return the matching syme */
1237 return esyme;
1238 }
1239
1240
1241 /* Not found: return untouched */
1242 return syme;
1243}
1244
1245
1246localstatic SymeList
1247dgFindDependencies(AbSyn absyn)
1248{
1249 SymeList result = listNil(Syme)((SymeList) 0);
1250
1251 /*
1252 * Check the absyn: we want to find all dependencies
1253 * but don't want to find false ones. For example, we
1254 * need to examine the type of a declaration but we
1255 * don't want to examine the thing being declared: it
1256 * might be the node whose dependency is being checked!
1257 */
1258 if (abIsId(absyn)((absyn)->abHdr.tag == (AB_Id))) {
1259 Syme syme = dgGetAbMeaning(absyn);
1260
1261 if (syme) {
1262 /* Imports need to be converted to exports */
1263 if (symeIsImport(syme)(((((syme)->kind == SYME_Trigger ? libGetAllSymes((syme)->
lib) : ((void*)0)), (syme))->kind) == SYME_Import))
1264 syme = dgSymeImportToExport(syme);
1265
1266
1267 /*
1268 * Add to the dependency list: at the moment
1269 * we add all symes to the list. Ideally we
1270 * ought to filter out those which aren't
1271 * nodes of the dependency graph. They get
1272 * filtered out later but if we remove them
1273 * down here then there are fewer store
1274 * operations via listCons/listNConcat.
1275 */
1276 result = listCons(Syme)(Syme_listPointer->Cons)(syme, result);
1277 }
1278 return result;
1279 }
1280 else if (abTag(absyn)((absyn)->abHdr.tag) < AB_NODE_START)
1281 return result;
1282
1283
1284 /* Most cases are not very special */
1285 switch (abTag(absyn)((absyn)->abHdr.tag)) {
1286 /* Some nodes must not be fully checked */
1287 case AB_Add:
1288 result = dgFindDependencies(absyn->abAdd.base);
1289 break;
1290
1291 case AB_With:
1292 result = dgFindDependencies(absyn->abWith.base);
1293 break;
1294
1295 case AB_Declare:
1296 result = dgFindDependencies(absyn->abDeclare.type);
1297 break;
1298
1299 case AB_Define:
1300 result = dgFindDependencies(absyn->abDefine.rhs);
1301 break;
1302
1303 case AB_PLambda: /* Fall through */
1304 case AB_Lambda: {
1305 SymeList plst, rlst;
1306
1307 /* Dependencies in types */
1308 plst = dgFindDependencies(absyn->abLambda.param);
1309 rlst = dgFindDependencies(absyn->abLambda.rtype);
1310
1311 result = listNConcat(Syme)(Syme_listPointer->NConcat)(plst, rlst);
1312 break;
1313 }
1314
1315 /* Check everything else completely */
1316 default: {
1317 int i;
1318
1319 for (i = 0; i < abArgc(absyn)((absyn)->abHdr.argc); i++) {
1320 SymeList tmp;
1321
1322 tmp = dgFindDependencies(abArgv(absyn)((absyn)->abGen.data.argv)[i]);
1323 if (tmp)
1324 result = listNConcat(Syme)(Syme_listPointer->NConcat)(result, tmp);
1325 }
1326
1327 break;
1328 }
1329 }
1330
1331
1332 /* Return the list of dependencies */
1333 return result;
1334}
1335
1336