DIRECTORY
Atom USING [GetPName, MakeAtom],
Basics USING [BITAND, BITNOT, BITOR],
BasicTime USING [GMT, nullGMT],
DFPorter USING [DFContents, FullFileItem, LORA, ReadDFs],
DFUtilities USING [DirectoryItem, FileItem],
FS USING [Error, FileInfo],
MobConnection USING [Error, LORAFromMob, ModuleID],
MobOrder USING [BitVector, emptyBitVector, ExportItems, MobConnections, MobConnectionsRep],
RefTab USING [Create, Fetch, Insert, Ref],
RuntimeError USING [UNCAUGHT],
Rope USING [Cat, Concat, Equal, Fetch, Match, ROPE, Run, Size],
SymTab USING [Create, Fetch, Ref, Store];

MobOrderImpl: CEDAR PROGRAM
IMPORTS Atom, Basics, DFPorter, FS, MobConnection, RefTab, Rope, RuntimeError, SymTab
EXPORTS MobOrder
~ BEGIN OPEN MobOrder;

LORA: TYPE = LIST OF REF;

ROPE: TYPE = Rope.ROPE;

MakeLoadList: PUBLIC PROC [dfNames: LIST OF ROPE, goals: LIST OF ROPE] RETURNS [LIST OF LIST OF ATOM] = {
connections: LIST OF MobConnections = GetMobsViaDFs[dfNames];
withGoals: LIST OF MobConnections = MarkGoals[connections, goals];
sorted: LIST OF LIST OF MobConnections = TopoSortConnections[withGoals];
namesOnly: LIST OF LIST OF ATOM = ExtractNames[sorted];
RETURN [namesOnly]
};

DReverseAtomList: PROC [list: LIST OF ATOM] RETURNS [LIST OF ATOM] =  {
l1, l2, l3: LIST OF ATOM Ź NIL;
IF list = NIL THEN RETURN[NIL];
l3 Ź list;
UNTIL (l1 Ź l3) = NIL DO
l3 Ź l3.rest;
l1.rest Ź l2;
l2 Ź l1;
ENDLOOP;
RETURN[l2];
};

MakeDependentsList: PUBLIC PROC [dfNames: LIST OF ROPE, roots: LIST OF ROPE] RETURNS [modules: LIST OF ATOM, dependentDFNames: LIST OF ROPE Ź NIL] = {
AddDFName: PROC [dfName: ROPE] ~ {
FOR tail: LIST OF ROPE Ź dependentDFNames, tail.rest UNTIL tail = NIL DO
IF Rope.Equal[s1: dfName, s2: tail.first, case: FALSE] THEN RETURN;
ENDLOOP;
dependentDFNames Ź CONS[dfName, dependentDFNames];
};
connections: LIST OF MobConnections = GetMobsViaDFs[dfNames];
withGoals: LIST OF MobConnections = MarkGoals[connections, roots];
sorted: LIST OF LIST OF MobConnections = TopoSortConnections[connections: withGoals, topDown: FALSE];
modules Ź DReverseAtomList[FlatExtractNames[sorted]];
FOR tail: LIST OF LIST OF MobConnections Ź sorted, tail.rest UNTIL tail = NIL DO
FOR t: LIST OF MobConnections Ź tail.first, t.rest UNTIL t = NIL DO
AddDFName[t.first.dfName];
ENDLOOP;
ENDLOOP;
};

EnumerateFiles: PUBLIC PROC [action: PUBLIC PROC [dfName: ROPE, name: ROPE, fullFName: ROPE, created: BasicTime.GMT, goal: BOOL], dfs: LIST OF DFPorter.DFContents] = {
FOR tail: LIST OF DFPorter.DFContents Ź dfs, tail.rest UNTIL tail = NIL DO
df: DFPorter.DFContents ~ tail.first;
currentDir: REF DFUtilities.DirectoryItem Ź NIL;
FOR tail: LORA Ź df.contents, tail.rest UNTIL tail = NIL DO
WITH tail.first SELECT FROM
a: REF DFPorter.FullFileItem => {
action[df.name, a.file.name, Rope.Concat[a.directory.path1, a.file.name], IF a.file.date.format = explicit THEN a.file.date.gmt ELSE BasicTime.nullGMT, a.file.verifyRoot];
};
a: REF DFUtilities.DirectoryItem => {
currentDir Ź a;
};
a: REF DFUtilities.FileItem => {
action[df.name, a.name, Rope.Concat[currentDir.path1, a.name], IF a.date.format = explicit THEN a.date.gmt ELSE BasicTime.nullGMT, a.verifyRoot];
};
ENDCASE => NULL;
ENDLOOP;
ENDLOOP;
};

BitVectorRest: PUBLIC PROC [bitVector: BitVector] RETURNS [BitVector] = {
RETURN [IF bitVector.rest = NIL THEN emptyBitVector ELSE bitVector.rest­]
};

BitVectorRef: PUBLIC PROC [bitVector: BitVector, i: NAT] RETURNS [BOOL] = {
WHILE i >= BITS[WORD] DO
IF bitVector.rest = NIL THEN RETURN [FALSE];
bitVector Ź bitVector.rest­;
i Ź i - BITS[WORD];
ENDLOOP;
RETURN [bitVector.w0[i]]
};

BitVectorSet: PUBLIC PROC [bitVector: BitVector, i: NAT] RETURNS [BitVector] = {
IF i < BITS[WORD] THEN {bitVector.w0[i] Ź TRUE; RETURN [bitVector]};
IF bitVector.rest = NIL THEN bitVector.rest Ź NEW[BitVector Ź [ALL[FALSE], NIL]];
bitVector.rest­ Ź BitVectorSet[bitVector.rest­, i-BITS[WORD]];
RETURN [bitVector]
};

BitVectorOr: PUBLIC PROC [a, b: BitVector] RETURNS [BitVector] = {
w0: PACKED ARRAY [0..BITS[WORD]) OF BOOL = LOOPHOLE[Basics.BITOR[LOOPHOLE[a.w0], LOOPHOLE[b.w0]]];
RETURN [[w0, IF a.rest # NIL OR b.rest # NIL THEN NEW[BitVector Ź BitVectorOr[BitVectorRest[a], BitVectorRest[b]]] ELSE NIL]]
};

BitVectorImplies: PUBLIC PROC [a, b: BitVector] RETURNS [BOOL] = {
w0: PACKED ARRAY [0..BITS[WORD]) OF BOOL = LOOPHOLE[Basics.BITOR[Basics.BITNOT[LOOPHOLE[a.w0]], LOOPHOLE[b.w0]]];
IF w0 # ALL[TRUE] THEN RETURN [FALSE];
IF a.rest = NIL AND b.rest = NIL THEN RETURN [TRUE];
RETURN [BitVectorImplies[BitVectorRest[a], BitVectorRest[b]]]
};

BitVectorEmptyIntersection: PUBLIC PROC [a, b: BitVector] RETURNS [BOOL] = {
w0: PACKED ARRAY [0..BITS[WORD]) OF BOOL = LOOPHOLE[Basics.BITAND[LOOPHOLE[a.w0], LOOPHOLE[b.w0]]];
IF w0 # ALL[FALSE] THEN RETURN [FALSE];
IF a.rest = NIL AND b.rest = NIL THEN RETURN [TRUE];
RETURN [BitVectorEmptyIntersection[BitVectorRest[a], BitVectorRest[b]]]
};


cache: SymTab.Ref Ź SymTab.Create[case: FALSE];

CachedLORAFromMob: PUBLIC PROC [fileName: ROPE] RETURNS [mob: LORA] = {
WITH SymTab.Fetch[x: cache, key: fileName].val SELECT FROM
lora: LORA => RETURN [lora];
ENDCASE => NULL;
mob Ź MobConnection.LORAFromMob[fileName: fileName, filter: [versions: TRUE, directory: TRUE, using: FALSE, imports: TRUE, importedItems: TRUE, exports: TRUE, typeExports: FALSE, exportedItems: TRUE, modules: TRUE, configurations: FALSE]];
[] Ź SymTab.Store[x: cache, key: fileName, val: mob];
};

DecodeMob: PUBLIC PROC [fileName: ROPE] RETURNS [MobConnections] = {
mob: LORA = CachedLORAFromMob[fileName: fileName];
WITH mob.rest.first SELECT FROM
id: REF MobConnection.ModuleID => {
ans: MobConnections Ź NEW[MobConnectionsRep];
ans.kind Ź NARROW[mob.first];
ans.id Ź id­;
FOR tail: LORA Ź Lookup[$directory, mob.rest.rest], tail.rest UNTIL tail = NIL DO
WITH tail.first SELECT FROM
item: LORA => {
IF item.first = $item THEN WITH item.rest.first SELECT FROM
atom: ATOM => {
ans.directory Ź CONS[[identifier: atom, version: NIL], ans.directory]
};
ENDCASE => NULL;
};
ENDCASE => NULL;
ENDLOOP;
FOR tail: LORA Ź Lookup[$imports, mob.rest.rest], tail.rest UNTIL tail = NIL DO
WITH tail.first SELECT FROM
id: REF MobConnection.ModuleID => { ans.imports Ź CONS[id­, ans.imports] };
ENDCASE => NULL;
ENDLOOP;
FOR tail: LORA Ź Lookup[$exports, mob.rest.rest], tail.rest UNTIL tail = NIL DO
WITH tail.first SELECT FROM
exportInterface: LORA => {
IF exportInterface.first = $export THEN WITH exportInterface.rest.first SELECT FROM
id: REF MobConnection.ModuleID => {
exportItems: ExportItems Ź [id­, emptyBitVector];
IF ans.kind # $configuration THEN FOR tail: LORA Ź exportInterface.rest.rest, tail.rest UNTIL tail = NIL DO
WITH tail.first SELECT FROM
item: LORA => {
WITH item.rest.first SELECT FROM
refINT: REF INT => {
exportItems.items Ź BitVectorSet[exportItems.items, refINT­]
};
ENDCASE => NULL;
};
ENDCASE => NULL;
ENDLOOP;
ans.exports Ź CONS[exportItems, ans.exports]
};
ENDCASE => NULL;
};
ENDCASE => NULL;
ENDLOOP;
FOR tail: LORA Ź Lookup[$modules, mob.rest.rest], tail.rest UNTIL tail = NIL DO
WITH tail.first SELECT FROM
id: REF MobConnection.ModuleID => { ans.modules Ź CONS[id­, ans.modules] };
ENDCASE => NULL;
ENDLOOP;
RETURN [ans]
};
ENDCASE => RETURN [NIL];
};

Lookup: PROC [key: REF, list: LORA] RETURNS [LORA] = {
FOR tail: LORA Ź list, tail.rest UNTIL tail = NIL DO
WITH tail.first SELECT FROM
item: LORA => IF item.first = key THEN RETURN [item.rest];
ENDCASE => NULL;
ENDLOOP;
RETURN [NIL]
};

BogusMob: PUBLIC SIGNAL [msg: ROPE] = CODE;
paranoid: BOOL Ź TRUE; -- enables distrust of version numbers;
GetMobsViaDFs: PUBLIC PROC [dfNames: LIST OF ROPE] RETURNS [LIST OF MobConnections] = {
dfs: LIST OF DFPorter.DFContents = DFPorter.ReadDFs[dfNames: dfNames, followImports: FALSE];
connections: LIST OF MobConnections;
Inner: PROC [dfName: ROPE, name: ROPE, fullFName: ROPE, created: BasicTime.GMT, goal: BOOL] = {
Protected: PROC = {
SELECT TRUE FROM
Rope.Match[pattern: "*.mob!*", object: name, case: FALSE] => {
realName: ROPE = IF paranoid AND created # BasicTime.nullGMT THEN FS.FileInfo[name: fullFName, wantedCreatedTime: created, remoteCheck: TRUE].fullFName ELSE fullFName;
mobConnections: MobConnections Ź DecodeMob[realName];
IF NOT Rope.Equal[s1: realName, s2: fullFName, case: FALSE] THEN SIGNAL IncorrectVersionNumberInDF[fullFName, realName];
IF mobConnections # NIL THEN {
connections Ź CONS[mobConnections, connections];
mobConnections.fileName Ź realName;
mobConnections.dfName Ź dfName;
};
};
ENDCASE => NULL;
};
Protected[ !
RuntimeError.UNCAUGHT => { SIGNAL BogusMob[Rope.Cat["UNCAUGHT while trying ", fullFName, " in ", dfName]]; CONTINUE };
MobConnection.Error => { SIGNAL BogusMob[msg]; CONTINUE };
FS.Error => { SIGNAL BogusMob[error.explanation]; CONTINUE };
];
};
EnumerateFiles[Inner, dfs];
RETURN [connections]
};

MapIdIdentifier: PROC [c: LIST OF MobConnections] RETURNS [LIST OF ATOM] = {
RETURN [IF c = NIL THEN NIL ELSE CONS[c.first.id.identifier, MapIdIdentifier[c.rest]]]
};

ExtractNames: PUBLIC PROC [in: LIST OF LIST OF MobConnections] RETURNS [LIST OF LIST OF ATOM] = {
head: LIST OF LIST OF ATOM = LIST[NIL];
last: LIST OF LIST OF ATOM Ź head;
FOR tail: LIST OF LIST OF MobConnections Ź in, tail.rest UNTIL tail = NIL DO
last Ź last.rest Ź LIST[MapIdIdentifier[tail.first]];
ENDLOOP;
RETURN [head.rest]
};

FlatExtractNames: PROC [in: LIST OF LIST OF MobConnections] RETURNS [LIST OF ATOM] = {
head: LIST OF ATOM = LIST[NIL];
last: LIST OF ATOM Ź head;
FOR tail: LIST OF LIST OF MobConnections Ź in, tail.rest UNTIL tail = NIL DO
last.rest Ź MapIdIdentifier[tail.first];
UNTIL last.rest = NIL DO last Ź last.rest ENDLOOP;
ENDLOOP;
RETURN [head.rest]
};

IncorrectVersionNumberInDF: PUBLIC SIGNAL [fullFName, realName: ROPE] = CODE; 

GoalNotFound: PUBLIC SIGNAL [rope: ROPE] = CODE;

RopeListAppend: PROC [a, b: LIST OF ROPE] RETURNS [LIST OF ROPE] = {
RETURN [IF a = NIL THEN b ELSE CONS[a.first, RopeListAppend[a.rest, b]]]
};

FindImportGoals: PUBLIC PROC [connections: LIST OF MobConnections, importGoals: LIST OF ATOM] RETURNS [ans: LIST OF ROPE Ź NIL] = {
OnList: PROC [a: ATOM] RETURNS [BOOL] = INLINE {
FOR tail: LIST OF ATOM Ź importGoals, tail.rest UNTIL tail = NIL DO
IF a = tail.first THEN RETURN [TRUE]
ENDLOOP;
RETURN [FALSE]
};
FOR tail: LIST OF MobConnections Ź connections, tail.rest UNTIL tail.rest = NIL DO
c: MobConnections ~ tail.first;
FOR tail: LIST OF MobConnection.ModuleID Ź c.imports, tail.rest UNTIL tail = NIL DO
IF OnList[tail.first.identifier] THEN {
ans Ź CONS[Atom.GetPName[c.id.identifier], ans];
EXIT;
};
ENDLOOP;
ENDLOOP;
};

MarkGoals: PUBLIC PROC [connections: LIST OF MobConnections, goals: LIST OF ROPE] RETURNS [LIST OF MobConnections] = {
head: LIST OF MobConnections = LIST[NIL];
last: LIST OF MobConnections Ź head;
srcHead: LIST OF MobConnections = CONS[NIL, connections];
importGoals: LIST OF ATOM Ź NIL;
notGoals: LIST OF ROPE Ź NIL;
OnList: PROC [a: ATOM] RETURNS [BOOL] = {
FOR tail: LIST OF ATOM Ź importGoals, tail.rest UNTIL tail = NIL DO
IF a = tail.first THEN RETURN [TRUE]
ENDLOOP;
RETURN [FALSE]
};
UNTIL goals = NIL DO
SELECT TRUE FROM -- crock!! the switch detection does not really belong here.
Rope.Equal[goals.first, "-i", FALSE] => {
IF goals.rest # NIL THEN {
goals Ź goals.rest;
importGoals Ź CONS[Atom.MakeAtom[goals.first], importGoals];
};
};
Rope.Equal[goals.first, "-x", FALSE] => {
IF goals.rest # NIL THEN {
goals Ź goals.rest;
notGoals Ź CONS[goals.first, notGoals];
};
};
ENDCASE => {
goal: ROPE = goals.first;
goalSize: INT = Rope.Size[goal];
FOR prev: LIST OF MobConnections Ź srcHead, prev.rest UNTIL prev.rest = NIL DO
c: MobConnections ~ prev.rest.first;
target: ROPE ~ Atom.GetPName[c.id.identifier];
targetSize: INT = Rope.Size[target];
IF targetSize >= goalSize THEN {
run: INT = Rope.Run[s1: goal, s2: target, case: FALSE];
IF run = targetSize OR run < targetSize AND Rope.Fetch[target, run] = '. THEN {
next: LIST OF MobConnections Ź prev.rest.rest;
prev.rest.rest Ź NIL;
last Ź last.rest Ź prev.rest;
prev.rest Ź next;
c.goal Ź TRUE;
EXIT;
};
};
REPEAT FINISHED => {SIGNAL GoalNotFound[goal]}
ENDLOOP;
};
goals Ź goals.rest;
ENDLOOP;
last.rest Ź srcHead.rest;
IF importGoals # NIL THEN {
FOR tail: LIST OF MobConnections Ź head.rest, tail.rest UNTIL tail.rest = NIL DO
c: MobConnections ~ tail.first;
FOR tail: LIST OF MobConnection.ModuleID Ź c.imports, tail.rest UNTIL tail = NIL DO
IF OnList[tail.first.identifier] THEN {
c.goal Ź TRUE;
EXIT;
};
ENDLOOP;
ENDLOOP;
};
IF notGoals # NIL THEN {
NotAGoal: PROC [name: ROPE] RETURNS [BOOL] ~{
FOR tail: LIST OF ROPE Ź notGoals, tail.rest UNTIL tail = NIL DO
IF Rope.Match[pattern: tail.first, object: name, case: FALSE] THEN RETURN [TRUE];
ENDLOOP;
RETURN [FALSE]
};
FOR tail: LIST OF MobConnections Ź head.rest, tail.rest UNTIL tail.rest = NIL DO
c: MobConnections ~ tail.first;
IF NotAGoal[Atom.GetPName[c.id.identifier]] THEN c.goal Ź FALSE;
ENDLOOP;
};
RETURN [head.rest]
};

MobConnectionsListLength: PUBLIC PROC [connections: LIST OF MobConnections] RETURNS [n: INT Ź 0] = {
FOR tail: LIST OF MobConnections Ź connections, tail.rest UNTIL tail = NIL DO
n Ź n + 1;
ENDLOOP;
};

BoundProgramNotKnown: PUBLIC SIGNAL [configuration, program: MobConnection.ModuleID] = CODE;

DuplicateExports: PUBLIC SIGNAL [moduleID, interfaceID: MobConnection.ModuleID] = CODE;
Debug: SIGNAL = CODE;
stopper: ATOM Ź NIL;
TopoSortConnections: PUBLIC PROC [connections: LIST OF MobConnections, topDown: BOOL Ź TRUE] RETURNS [LIST OF LIST OF MobConnections] = {
Vertex: TYPE ~ REF VertexRep;
VertexRep: TYPE ~ RECORD [
data: MobConnections,
satisfiedItems: BitVector,
label: ATOM,
onStack: BOOL,
number: NAT,
needs: LIST OF NAT,
nNeedees: NAT,
rank: INT,
f: INT -- minimum rank branched to by desecendants
];
VertexSeqRep: TYPE ~ RECORD[SEQUENCE n: NAT OF Vertex];
labelToNumber: RefTab.Ref ~ RefTab.Create[];
identifierToNumber: RefTab.Ref ~ RefTab.Create[];
graph: REF VertexSeqRep ~ CreateGraph[];
CreateGraph: PROC RETURNS [REF VertexSeqRep] ~ {
v: REF VertexSeqRep Ź NEW[VertexSeqRep[MobConnectionsListLength[connections]]];
n: INT Ź 0;
Insert: PROC [c: MobConnections] = {
label: ATOM ~ c.id.version;
nRef: REF NAT = NEW[NAT Ź n];
v[n] Ź NEW[VertexRep Ź [
data: c,
satisfiedItems: emptyBitVector,
label: label,
onStack: FALSE,
number: n,
needs: NIL,
nNeedees: 0,
rank: 0,
f: LAST[INT]
]];
IF c.id.version = stopper OR c.id.identifier = stopper THEN SIGNAL Debug;
[] Ź RefTab.Insert[labelToNumber, label, nRef];
[] Ź RefTab.Insert[identifierToNumber, c.id.identifier, nRef];
n Ź  n + 1;
};
AddEdge: PROC [from, to: NAT] = {
v[from].needs Ź CONS[to, v[from].needs];
v[to].nNeedees Ź v[to].nNeedees + 1;
};
FOR tail: LIST OF MobConnections Ź connections, tail.rest UNTIL tail = NIL DO
IF tail.first.goal THEN Insert[tail.first];
ENDLOOP;
FOR tail: LIST OF MobConnections Ź connections, tail.rest UNTIL tail = NIL DO
IF tail.first.kind = $configuration AND NOT tail.first.goal THEN Insert[tail.first];
ENDLOOP;
FOR tail: LIST OF MobConnections Ź connections, tail.rest UNTIL tail = NIL DO
IF NOT (tail.first.kind = $configuration OR tail.first.goal) THEN Insert[tail.first];
ENDLOOP;
IF topDown
THEN {
FOR i: NAT IN [0..v.n) DO
mob: MobConnections ~ v[i].data;
IF mob.kind = $configuration THEN {
FOR tail: LIST OF MobConnection.ModuleID Ź mob.modules, tail.rest UNTIL tail = NIL DO
WITH RefTab.Fetch[labelToNumber, tail.first.version].val SELECT FROM
refNAT: REF NAT => {
module: MobConnections = v[refNAT­].data;
IF mob.goal AND module.goal THEN module.goal Ź FALSE;
FOR tail: LIST OF ExportItems Ź module.exports, tail.rest UNTIL tail = NIL DO
supplier: ExportItems ~ tail.first;
FOR tail: LIST OF ExportItems Ź mob.exports, tail.rest UNTIL tail = NIL DO
IF tail.first.id = supplier.id THEN {
tail.first.items Ź BitVectorOr[tail.first.items, supplier.items];
EXIT;
};
ENDLOOP;
ENDLOOP;
};
ENDCASE => {SIGNAL BoundProgramNotKnown[configuration: mob.id, program: tail.first]};
ENDLOOP;
};
ENDLOOP;
FOR i: NAT DECREASING IN [0..v.n) DO
mob: MobConnections ~ v[i].data;
FOR tail: LIST OF MobConnection.ModuleID Ź mob.imports, tail.rest UNTIL tail = NIL DO
WITH RefTab.Fetch[labelToNumber, tail.first.version].val SELECT FROM
refNAT: REF NAT => { AddEdge[from: i, to: refNAT­] };
ENDCASE => NULL;
ENDLOOP;
FOR tail: LIST OF ExportItems Ź mob.exports, tail.rest UNTIL tail = NIL DO
WITH RefTab.Fetch[labelToNumber, tail.first.id.version].val SELECT FROM
refNAT: REF NAT => { AddEdge[from: refNAT­, to: i] };
ENDCASE => NULL;
ENDLOOP;
ENDLOOP;
}
ELSE {-- NOT topDown
FOR i: NAT DECREASING IN [0..v.n) DO
mob: MobConnections ~ v[i].data;
FOR tail: LIST OF MobConnection.ModuleID Ź mob.directory, tail.rest UNTIL tail = NIL DO
WITH RefTab.Fetch[identifierToNumber, tail.first.identifier].val SELECT FROM
refNAT: REF NAT => { AddEdge[from: refNAT­, to: i] };
ENDCASE => NULL;
ENDLOOP;
FOR tail: LIST OF MobConnection.ModuleID Ź mob.modules, tail.rest UNTIL tail = NIL DO
WITH RefTab.Fetch[labelToNumber, tail.first.version].val SELECT FROM
refNAT: REF NAT => { AddEdge[from: refNAT­, to: i] };
ENDCASE => NULL;
ENDLOOP;
ENDLOOP;
};
RETURN [v]
};
ShadowedByPreviousModules: PROC [u: Vertex] RETURNS [BOOL] = {
mob: MobConnections ~ u.data;
IF mob.goal OR mob.kind = $definitions THEN RETURN [FALSE];
FOR tail: LIST OF ExportItems Ź mob.exports, tail.rest UNTIL tail = NIL DO
WITH RefTab.Fetch[labelToNumber, tail.first.id.version].val SELECT FROM
refNAT: REF NAT => {
j: NAT = refNAT­;
IF graph[j].nNeedees # 0 THEN {
IF NOT BitVectorImplies[tail.first.items, graph[j].satisfiedItems] THEN RETURN [FALSE];
};
};
ENDCASE => NULL;
ENDLOOP;
RETURN [TRUE]
};
HasDuplicateExports: PROC [u: Vertex] RETURNS [duplicates: BOOL Ź FALSE] = {
skip: BOOL Ź FALSE; -- set with debugger for early out.
mob: MobConnections ~ u.data;
IF mob.kind = $definitions THEN RETURN [FALSE];
FOR tail: LIST OF ExportItems Ź mob.exports, tail.rest UNTIL tail = NIL DO
WITH RefTab.Fetch[labelToNumber, tail.first.id.version].val SELECT FROM
refNAT: REF NAT => {
j: NAT = refNAT­;
IF NOT BitVectorEmptyIntersection[tail.first.items, graph[j].satisfiedItems] THEN {
duplicates Ź TRUE;
SIGNAL DuplicateExports[mob.id, graph[j].data.id];
IF skip THEN EXIT;
};
};
ENDCASE => NULL;
ENDLOOP;
};
RecordSatisfiedItems: PROC [u: Vertex] = {
mob: MobConnections ~ u.data;
FOR tail: LIST OF ExportItems Ź mob.exports, tail.rest UNTIL tail = NIL DO
WITH RefTab.Fetch[labelToNumber, tail.first.id.version].val SELECT FROM
refNAT: REF NAT => {
j: NAT = refNAT­;
graph[j].satisfiedItems Ź BitVectorOr[graph[j].satisfiedItems, tail.first.items];
};
ENDCASE => NULL;
ENDLOOP;
};
stack: LIST OF Vertex Ź NIL; -- the vertices examined but not yet output
k: NAT Ź 0; -- number of vertices examined so far;
Examine: PROC [u: Vertex] ~ {
min: INT Ź LAST[INT];
k Ź k + 1;
u.rank Ź k;
IF topDown AND ShadowedByPreviousModules[u] THEN RETURN;
IF topDown AND HasDuplicateExports[u] THEN RETURN;
stack Ź CONS[u, stack]; u.onStack Ź TRUE;
FOR tail: LIST OF NAT Ź u.needs, tail.rest UNTIL tail = NIL DO
v: Vertex ~ graph[tail.first];
IF v.rank = 0
THEN {
Examine[v];
IF v.f < min THEN min Ź v.f;
}
ELSE {
IF v.rank < min AND v.onStack THEN min Ź v.rank;
};
ENDLOOP;
u.f Ź min;
IF u.f >= u.rank THEN {
c: LIST OF MobConnections Ź NIL;
DO
w: Vertex Ź stack.first;
stack Ź stack.rest; w.onStack Ź FALSE;
IF topDown 
THEN {
IF w.data.kind # $definitions THEN {
RecordSatisfiedItems[w];
c Ź CONS[w.data, c];
};
}
ELSE {
c Ź CONS[w.data, c];
};
IF w = u THEN EXIT;
ENDLOOP;
Output[c];
};
};
head: LIST OF LIST OF MobConnections ~ LIST[NIL];
last: LIST OF LIST OF MobConnections Ź head;
Output: PROC [a: LIST OF MobConnections] = {
IF a # NIL THEN last Ź last.rest Ź LIST[a];
};
Find: PROC [identifier: ATOM] RETURNS [ans: LIST OF INT Ź NIL] = {
num: INT Ź -1;
FOR pass: [0..1] IN [0..1] UNTIL num >= 0 DO
FOR i: NAT IN [0..graph.n) DO
v: Vertex ~ graph[i];
IF v.data.id.identifier = identifier THEN {num Ź i; EXIT};
ENDLOOP;
identifier Ź Atom.MakeAtom[Atom.GetPName[identifier].Concat[".config"]];
ENDLOOP;
IF num >= 0 THEN {
FOR i: NAT DECREASING IN [0..graph.n) DO
v: Vertex ~ graph[i];
FOR tail: LIST OF NAT Ź v.needs, tail.rest UNTIL tail = NIL DO
IF num = tail.first THEN {
ans Ź CONS[i, ans];
EXIT;
};
ENDLOOP;
ENDLOOP;
ans Ź CONS[num, ans];
};
};
FOR i: NAT IN [0..graph.n) DO
v: Vertex ~ graph[i];
IF v.rank = 0 AND v.data.goal THEN Examine[v];
ENDLOOP;
RETURN [head.rest]
};

END.
    
MobOrderImpl.mesa
Copyright Ó 1989, 1991 by Xerox Corporation.  All rights reserved.
Michael Plass, September 28, 1989 9:17:51 pm PDT

TRUE iff a implies b.  (ALL a=>b), (ALL ((NOT a) OR b))
id: REF MobConnection.ModuleID => { ans.directory _ CONS[id^, ans.directory] };
Moves the goals to the front, in the order specified in the goals list.
<< Put all the goals first >>
<< Then configurations so that they get used in preference to program modules >>
<< finally everything else >>
<<This pass fixes up the export items for configs, which Cinder seems to have botched>>
<<Also kills goals within goals>>
<< DECREASING so that goals end up being explored first >>
<< DECREASING so that goals end up being explored first >>
At this point u.rank = 0
RecordSatisfiedItems[u];
A new strong component has been found
For debugging; call from breakpoint; returns list of node numbers of things that reference identifier.
Ę"[  NewlineDelimiter
(cedarcode) style codeK
Ďe7BK00K Ďk		K K	%K
K	9K,KK 3K	M[K*KK$?K)K ĎnK3UK	
K 
K K 	iK)=K0BK	1HK7KKK GK	K
K
KKKKKKK "		
"HKStartOfExpansion-[s1: ROPE, s2: ROPE, case: BOOL _ TRUE].CKK2KK)=K0BKGeK5$P%CKKKKK 

§&JK%K0	;!KJ'ŤK%KK K?"KKKKKK IK
IKK KK
,KKKKKK 
PKDKQK2>KKK BK	bK

>}KK 
BK7K		qK&K

4K7=KK 
LK	cK'K

4KAGKK K &[mod: NAT _ 17, case: BOOL _ TRUE](/K G[x: SymTab.Ref, key: ROPE]+:KKKG	ďK5KK 
	DK)2#K-KK	0QK-O	;KEKKKKK	.OK+KKK	.O	!S#K1(k K<KKKKKK,KKKKK	.OK+KKKKKKKK 6	4K	:KKKKK K
+K
Ďc'>WKI\K$
_	3>Kb[name: ROPE, wantedCreatedTime: GMT _ nullGMT, remoteCheck: BOOL _ TRUE, wDir: ROPE _ NIL]

D§K5K
/1xK0K#KKKKKKJvK:K=KKKKKK LK1VKK aK'K" LK5KKKK VKK LK(K2KKKK 
NK 
0K DK%HKK 0CK$KKK)RK/S'K&0KKKKKK 	vKGK	)K$K		9K	 K	

)CK$KKK	 <M)KK*<KK)KK'KKKK
 %NK$$KO[s1: ROPE, pos1: INT _ 0, s2: ROPE, pos2: INT _ 0, case: BOOL _ TRUE]".K$ K(7OK!.KKKK	KKKK.KKKKK'PK/S'K	KKKKK
-@K6[pattern: ROPE, object: ROPE, case: BOOL _ TRUE]
5QKKK'PKK*
@KKKKK 	d)MK
KKK 4\K K3WKK	KKKKK	KKK
K
K +2KK	7K,K1K(0K6OK$KK	KKKK	K
KKKKKKIK/K>KK!K(K$K)MKK+K)MKPK"TK)MKK#UK

KWK!!K #1U5DK)K
5)MK##&J%KAKKKKKKCUKKK
$K
-:K 1U5DK&5KK&J8GK&5KKKK 	

$K
-:K 3W=LK&5KK1U5DK&5KKKKK
K>KK

;&J8GKK
=WKKKKKK
LK #7KK/&J8GKGSKK,2KKKKKK*K&J8GKKQKKKKK
 +HK &2KKK
KK	8K	2K)K>KKKKK0KKK
K%%K KK &	$KKKKKKKKK
KKK1K	,,K+KBKffK
,KK#:KKHK
	
(K>K	KKKKKKKKK.KKKK K     O<  u1  