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
LORA:
TYPE =
LIST
OF
REF;
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] = {
TRUE iff a implies b. (ALL a=>b), (ALL ((NOT a) OR b))
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
id: REF MobConnection.ModuleID => { ans.directory ← CONS[id^, ans.directory] };
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] = {
Moves the goals to the front, in the order specified in the goals list.
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
<< Put all the goals first >>
IF tail.first.goal THEN Insert[tail.first];
ENDLOOP;
FOR tail:
LIST
OF MobConnections ¬ connections, tail.rest
UNTIL tail =
NIL
DO
<< Then configurations so that they get used in preference to program modules >>
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
<< finally everything else >>
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
<<This pass fixes up the export items for configs, which Cinder seems to have botched>>
<<Also kills goals within goals>>
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
<< DECREASING so that goals end up being explored first >>
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
<< DECREASING so that goals end up being explored first >>
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] ~ {
At this point u.rank = 0
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;
RecordSatisfiedItems[u];
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 {
A new strong component has been found
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] = {
For debugging; call from breakpoint; returns list of node numbers of things that reference identifier.
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.