[_CDCSL_93-16_]<1>Cedar>release>VersionMap2>VersionMap2Impl.mesa

VersionMap2Impl.Mesa

Last tweaked by Mike Spreitzer on April 10, 1992 9:52 am PDT

DIRECTORY Atom, Basics, BasicTime, List, MorePfsNames, PFS, PFSNames, Process, Rope, RopeHash, RopeParts, VersionMap2, VersionMap2FromPattern, VersionMap2Implr;

VersionMap2Impl: CEDAR MONITOR

IMPORTS Basics, BasicTime, MorePfsNames, PFS, PFSNames, Rope, RopeHash, RopeParts, VersionMap2, VersionMap2Implr

EXPORTS VersionMap2, VersionMap2FromPattern

BEGIN OPEN VersionMap2, VersionMap2Implr, MPfsN:MorePfsNames, RP:RopeParts;

Basics

RopePart: TYPE ~ RP.RopePart;

TupleList: TYPE ~ LIST OF VersionTuple;

Error: PUBLIC ERROR [error: PFS.ErrorDesc] ~ PFS.Error;

NameMatch: PUBLIC PROC [x, p: Name] RETURNS [BOOL] ~ {

IF p=nullName THEN RETURN [TRUE];

NULL--all Names are absolute--;

IF x.IsADirectory[] # p.IsADirectory[] THEN RETURN [FALSE];

{nx: INT ~ PFSNames.ComponentCount[x];

np: INT ~ PFSNames.ComponentCount[p];

IF np > nx THEN RETURN [FALSE];

IF np=0 THEN RETURN [nx=0];

RETURN NameMatchFrom[x, p, FixFetch[x, 0], FixFetch[p, 0], nx, np, 0, 0]}};

NameMatchFrom: PROC [x, p: Name, cx, cp: PFSNames.Component, nx, np, ix, ip: INT] RETURNS [BOOL] ~ {

DO{

IF cp.version # [all] AND cp.version # cx.version THEN RETURN [FALSE];

IF cp.name.len=0 THEN {IF cx.name.len=0 THEN GOTO NextC ELSE RETURN [FALSE]};

{s2j: INT ~ MIN[cp.name.base.Index[cp.name.start, "**"]-cp.name.start, cp.name.len];

IF s2j=cp.name.len THEN {IF RopeParts.Match[[cp.name.base, cp.name.start, cp.name.len], [cx.name.base, cx.name.start, cx.name.len], FALSE] THEN GOTO NextC ELSE RETURN [FALSE]};

IF s2j>0 AND NOT RopeParts.Match[[cp.name.base, cp.name.start, s2j+1], [cx.name.base, cx.name.start, cx.name.len], FALSE] THEN RETURN [FALSE];

{cp1: PFSNames.Component ~ MPfsN.ConsComponent[RopeParts.Substr[MPfsN.ComponentName[cp], s2j+1], cp.version];

FOR d: INT DECREASING IN [1 .. (nx-ix) - (np-ip)] DO --try skipping d boundaries

IF NameMatchFrom[x, p, FixFetch[x, ix+d], cp1, nx, np, ix+d, ip] THEN RETURN [TRUE];

ENDLOOP;

RETURN NameMatchFrom[x, p, cx, MPfsN.ConsComponent[MPfsN.ComponentName[cp].Replace[s2j, 1], cp.version], nx, np, ix, ip]; --try replacing ** with *

}};

EXITS NextC => {

ix ← ix.SUCC;

ip ← ip.SUCC;

IF ip=np THEN RETURN [ix=nx];

cp ← FixFetch[p, ip];

cx ← FixFetch[x, ix];

};

}ENDLOOP};

NameCompare: PUBLIC PROC [n1, n2: Name] RETURNS [Basics.Comparison] ~ {

c: Basics.Comparison;

CompareBools: PROC [b1, b2: BOOL] RETURNS [Basics.Comparison] ~ {

SELECT TRUE FROM

~b1 AND b2 => RETURN[less];

b1 AND ~b2 => RETURN[greater];

ENDCASE => NULL;

RETURN[equal];

};

n1 ← n1.NonNIL[];

n2 ← n2.NonNIL[];

IF (c ← CompareBools[n1.IsAbsolute, n2.IsAbsolute]) # equal THEN RETURN[c];

{count1: INT ~ n1.ComponentCount[];

count2: INT ~ n2.ComponentCount[];

FOR p: INT IN (0..MIN[count1, count2]) DO

IF (c ← CompareComponents[n1.Fetch[p-1], n2.Fetch[p-1]]) # equal THEN RETURN[c];

ENDLOOP;

SELECT TRUE FROM

count1 < count2 => RETURN[less];

count1 > count2 => RETURN[greater];

ENDCASE => NULL;

IF count1>0 AND (c ← CompareComponents[n1.ShortName[], n2.ShortName[]]) # equal THEN RETURN[c];

RETURN CompareBools[n1.IsADirectory, n2.IsADirectory]}};

CompareComponents: PROC [c1, c2: PFSNames.Component] RETURNS [Basics.Comparison] ~ {

SELECT Rope.CompareSubstrs[
c1.name.base, c1.name.start, c1.name.len,
c2.name.base, c2.name.start, c2.name.len, FALSE] FROM

less => RETURN[less];

greater => RETURN[greater];

ENDCASE => NULL;

RETURN[CompareVersions[c1.version, c2.version]];

};

CompareVersions: PROC [v1, v2: PFSNames.Version] RETURNS [Basics.Comparison] ~ {

SELECT v1.versionKind FROM

numeric => SELECT v2.versionKind FROM

numeric => SELECT TRUE FROM

v1.version<v2.version => RETURN[less];

v1.version>v2.version => RETURN[greater];

ENDCASE => RETURN[equal];

none => RETURN [greater];

lowest, highest, next, all => ERROR Error[[user, $invalidName, "invalid version part"]];

ENDCASE => ERROR;

none => SELECT v2.versionKind FROM

numeric => RETURN [less];

none => RETURN [equal];

lowest, highest, next, all => ERROR Error[[user, $invalidName, "invalid version part"]];

ENDCASE => ERROR;

lowest, highest, next, all => ERROR Error[[user, $invalidName, "invalid version part"]];

ENDCASE => ERROR};

RtNameEqual: PUBLIC PROC [key1, key2: REF ANY] RETURNS [BOOL] --RefTab.EqualProc-- ~ {

n1: Name ~ NARROW[key1];

n2: Name ~ NARROW[key2];

RETURN NameEqual[n1, n2]};

RtNameHash: PUBLIC PROC [key: REF ANY] RETURNS [CARDINAL] --RefTab.HashProc-- ~ {

n: Name ~ NARROW[key];

cc: INT ~ n.ComponentCount[];

hash: CARDINAL ← cc;

FOR i: INT IN [0..cc) DO

c: PFSNames.Component ~ n.Fetch[i];

hash ← hash + RopeHash.FromRope[case: FALSE, rope: c.name.base, start: c.name.start, len: c.name.len] + c.version.version + c.version.versionKind.ORD;

ENDLOOP;

RETURN [hash]};

NamePatternIsConstant: PUBLIC PROC [p: Name] RETURNS [BOOL] ~ {

FOR i: INT IN [0 .. p.ComponentCount[]) DO

c: PFSNames.Component ~ p.Fetch[i];

SELECT c.version.versionKind FROM

numeric, none => NULL;

all => RETURN [FALSE];

lowest, highest, next => ERROR Error[[user, $invalidName, "invalid version part"]];

ENDCASE => ERROR;

IF c.name.base.Index[s2: "*", pos1: c.name.start] >= INT[c.name.start+c.name.len] THEN RETURN [FALSE];

ENDLOOP;

RETURN [TRUE]};

CreatedCompare: PUBLIC PROC [c1, c2: Created] RETURNS [c: Basics.Comparison] ~ {

SELECT BasicTime.Period[from: c1.egmt.gmt, to: c2.egmt.gmt] FROM

<0 => RETURN [greater];

=0 => NULL;

>0 => RETURN [less];

ENDCASE => ERROR;

IF (c ← Basics.CompareCard[c1.egmt.usecs, c1.egmt.usecs]) # equal THEN RETURN;

IF (c ← Basics.CompareCard[c1.host.a, c1.host.a]) # equal THEN RETURN;

c ← Basics.CompareCard[c1.host.b, c1.host.b];

RETURN};

StampCompare: PUBLIC PROC [s1, s2: VersionStamp] RETURNS [c: Basics.Comparison] ~ {

IF (c ← Basics.CompareCard[s1[0], s2[0]]) # equal THEN RETURN;

c ← Basics.CompareCard[s1[1], s2[1]];

RETURN};

TMatches: PUBLIC PROC [t, pattern: VersionTuple] RETURNS [BOOL] ~ {

RETURN [StampMatch[t.stamp, pattern.stamp] AND CreatedMatch[t.created, pattern.created] AND NameMatch[t.name, pattern.name]]};

TEqual: PUBLIC PROC [t1, t2: VersionTuple] RETURNS [BOOL] ~ {

RETURN [t1.stamp=t2.stamp AND t1.created=t2.created AND NameEqual[t1.name, t2.name]]};

TupleCompare: PUBLIC PROC [t1, t2: VersionTuple] RETURNS [c: Basics.Comparison] ~ {

IF (c ← NameCompare[t1.name, t2.name]) # equal THEN RETURN;

IF (c ← CreatedCompare[t1.created, t2.created]) # equal THEN RETURN;

c ← StampCompare[t1.stamp, t2.stamp];

RETURN};

all2: Name ~ PFSNames.ConstructName[

components: LIST[

MPfsN.ConstructComponent[["**"], [all]],

MPfsN.ConstructComponent[["*"], [all]]],

absolute: TRUE, directory: FALSE];

ShortNameToPattern: PUBLIC PROC [short: ROPE] RETURNS [VersionTuple] ~ {

RETURN [[all2.ReplaceShortName[MPfsN.ConstructComponent[[short], [all]]]]]};

LastComponentToPattern: PUBLIC PROC [lc: PFSNames.Component] RETURNS [VersionTuple] ~ {

RETURN [[all2.ReplaceShortName[lc]]]};

PatternIsConstant: PUBLIC PROC [p: VersionTuple] RETURNS [BOOL] ~ {

RETURN [p.created#nullCreated AND p.stamp#nullStamp AND NamePatternIsConstant[p.name] ]};

Using Maps

DeRefify: PUBLIC PROC [arg: REF ANY] RETURNS [RefMap]

~ {RETURN [NARROW[arg]]};

cantCode: PUBLIC ATOM ← $NotImplemented;

AllHave: PUBLIC PROC [maplist: MapList, t: VersionTuple] RETURNS [BOOL] ~ {

FOR maplist ← maplist, maplist.rest WHILE maplist#NIL DO

IF NOT maplist.first.Has[t] THEN RETURN [FALSE];

ENDLOOP;

RETURN [TRUE]};

OneHas: PUBLIC PROC [maplist: MapList, t: VersionTuple] RETURNS [BOOL] ~ {

FOR maplist ← maplist, maplist.rest WHILE maplist#NIL DO

IF maplist.first.Has[t] THEN RETURN [TRUE];

ENDLOOP;

RETURN [FALSE]};

PfmlHas: PUBLIC PROC [pfml: PatternFactoredMapList, t: VersionTuple] RETURNS [BOOL] ~ {

IF pfml.pattern#nullTuple AND NOT TMatches[t, pfml.pattern] THEN RETURN [FALSE];

IF pfml.stampInd#NIL AND NOT AllHave[pfml.stampInd, t] THEN RETURN [FALSE];

IF pfml.general#NIL AND NOT AllHave[pfml.general, t] THEN RETURN [FALSE];

RETURN [TRUE]};

MapIsSingleton: PUBLIC PROC [map: Map] RETURNS [mt: MaybeTuple] ~ {

NoteTheElt: PROC [t: VersionTuple] RETURNS [BOOL] ~ {

IF mt.found THEN RETURN [TRUE];

mt ← [TRUE, t]; RETURN [FALSE]};

mt ← noMaybe;

IF map.Scan[NoteTheElt, FALSE].found THEN RETURN [noMaybe];

RETURN};

TheElt: PUBLIC PROC [map: Map] RETURNS [VersionTuple] ~ {

mt: MaybeTuple ~ MapIsSingleton[map];

IF NOT mt.found THEN ERROR Error[[client, $NotUnique]];

RETURN [mt.it]};

AnElt: PUBLIC PROC [map: Map] RETURNS [MaybeTuple] ~ {

RETURN map.Scan[AlwaysAccept, FALSE]};

AlwaysAccept: PUBLIC TupleConsumer ~ {RETURN [TRUE]};

LookupStamp: PUBLIC PROC [map: Map, stamp: VersionStamp] RETURNS [MaybeTuple] ~ {

IF stamp = nullStamp THEN RETURN [noMaybe];

RETURN map.ScanMatches[AlwaysAccept, FALSE, [stamp: stamp]]};

LookupCreated: PUBLIC PROC [map: Map, created: Created] RETURNS [MaybeTuple] ~ {

IF created = nullCreated THEN RETURN [noMaybe];

RETURN map.ScanMatches[AlwaysAccept, FALSE, [created: created]]};

LookupShortName: PUBLIC PROC [map: Map, shortName: ROPE] RETURNS [MaybeTuple] ~ {

IF shortName.Find["*"] >= 0 THEN RETURN [noMaybe];

RETURN map.ScanMatches[AlwaysAccept, FALSE, ShortNameToPattern[shortName]]};

PatternFactorMapList: PUBLIC PROC [ml: MapList] RETURNS [PatternFactoredMapList] ~ {

IF ml=NIL THEN RETURN [[]];

RETURN PfmlAddMap[PatternFactorMapList[ml.rest], ml.first]};

PfmlAddMap: PUBLIC PROC [pfml: PatternFactoredMapList, map: Map] RETURNS [PatternFactoredMapList] ~ {

IF pfml.stampInd=listOfEmpty THEN RETURN [pfml];

{pfm: PatternFactoredMap ~ map.PatternFactorMap[];

AsMap: PROC RETURNS [Map] ~ {RETURN [map]};

RETURN PfmlAddPfm[pfml, pfm, AsMap]}};

PfmlAddPfm: PUBLIC PROC [pfml: PatternFactoredMapList, pfm: PatternFactoredMap, AsMap: PROC RETURNS [Map--equivalent to pfm--] ] RETURNS [PatternFactoredMapList] ~ {

conflict: BOOL ← FALSE;

IF pfm.stampInd=anEmpty OR pfm.general=anEmpty THEN RETURN [[nullTuple, listOfEmpty]];

SELECT TRUE FROM

pfml.pattern.stamp=pfm.pattern.stamp => NULL;

pfm.pattern.stamp=nullStamp => NULL;

pfml.pattern.stamp=nullStamp => pfml.pattern.stamp ← pfm.pattern.stamp;

ENDCASE => RETURN [[nullTuple, listOfEmpty]];

SELECT TRUE FROM

pfml.pattern.created=pfm.pattern.created => NULL;

pfm.pattern.created=nullCreated => NULL;

pfml.pattern.created=nullCreated => pfml.pattern.created ← pfm.pattern.created;

ENDCASE => RETURN [[nullTuple, listOfEmpty]];

SELECT TRUE FROM

pfml.pattern.name=pfm.pattern.name => NULL;

pfm.pattern.name=nullName => NULL;

pfml.pattern.name=nullName => pfml.pattern.name ← pfm.pattern.name;

NameEqual[pfml.pattern.name, pfm.pattern.name] => NULL;

NamePatternIsConstant[pfml.pattern.name] => IF NOT NameMatch[pfml.pattern.name, pfm.pattern.name] THEN RETURN [[nullTuple, listOfEmpty]];

NamePatternIsConstant[pfm.pattern.name] => IF NameMatch[pfm.pattern.name, pfml.pattern.name] THEN pfml.pattern.name ← pfm.pattern.name ELSE RETURN [[nullTuple, listOfEmpty]];

ENDCASE => {mismatch: BOOL; better, worse: Name;

[mismatch, better, worse] ← NamePatternSortMerge[pfml.pattern.name, pfm.pattern.name];

IF mismatch THEN RETURN [[nullTuple, listOfEmpty]];

IF NameEqual[better, pfml.pattern.name]

AND NameEqual[worse, pfm.pattern.name]

THEN conflict ← TRUE

ELSE {

pfml.stampInd ← CONS[CreateMatcher[[worse]], pfml.stampInd];

pfml.pattern.name ← better}

};

IF conflict THEN {

IF pfm.general=aFull AND pfm.pattern.stamp=nullStamp

THEN pfml.stampInd ← CONS[AsMap[], pfml.stampInd]

ELSE pfml.general ← CONS[AsMap[], pfml.general];

RETURN [pfml]};

IF pfm.stampInd#aFull THEN pfml.stampInd ← CONS[pfm.stampInd, pfml.stampInd];

IF pfm.general#aFull THEN pfml.general ← CONS[pfm.general, pfml.general];

RETURN [pfml]};

star: RopePart ~ RP.FromChar['*];

NamePatternSortMerge: PUBLIC PROC [np1, np2: Name] RETURNS [mismatch: BOOL, better, worse: Name ← NIL] ~ {

IF np2=nullName THEN RETURN [FALSE, np1, np2];

IF np1=nullName THEN RETURN [FALSE, np2, np1];

{nl1: INT ~ np1.ComponentCount[];

nl2: INT ~ np2.ComponentCount[];

minlen: INT ~ MIN[nl1, nl2];

i, j: INT ← 0;

diflen: BOOL ~ nl1#nl2;

defined, reverse, brev: BOOL ← FALSE;

Results: PROC RETURNS [mismatch: BOOL, better, worse: Name] ~ INLINE {

IF reverse

THEN RETURN [FALSE, np2, np1]

ELSE RETURN [FALSE, np1, np2]};

FOR i ← 0, i+1 WHILE i<minlen DO

c1: PFSNames.Component ~ np1.Fetch[i];

c2: PFSNames.Component ~ np2.Fetch[i];

r1: RopePart ~ MPfsN.ComponentName[c1];

r2: RopePart ~ MPfsN.ComponentName[c2];

l1: INT ~ r1.InlineLength[]; l2: INT ~ r2.InlineLength[];

s1: INT ~ r1.Index[star]; s2: INT ~ r2.Index[star];

s1p: INT ~ (IF s1<l1 THEN s1 ELSE INT.LAST);

s2p: INT ~ (IF s2<l2 THEN s2 ELSE INT.LAST);

s1d: BOOL ~ (s1+1<l1 AND r1.InlineFetch[s1+1]='*);

s2d: BOOL ~ (s2+1<l2 AND r2.InlineFetch[s2+1]='*);

smin: INT ~ MIN[s1, s2];

t1, t2, tmin, t1p, t2p: INT;

IF s1=l1 AND s2=l2 THEN {

IF NOT r1.Equal[r2, FALSE] THEN RETURN [TRUE]}

ELSE IF s1<l1 AND s2=l2 AND NOT s1d THEN {

IF NOT RP.Match[pattern: r1, object: r2, case: FALSE] THEN RETURN [TRUE];

np1 ← np1.ReplaceComponent[i, [c2.name, c1.version]]}

ELSE IF s1=l1 AND s2<l2 AND NOT s2d THEN {

IF NOT RP.Match[pattern: r2, object: r1, case: FALSE] THEN RETURN [TRUE];

np2 ← np2.ReplaceComponent[i, [c1.name, c2.version]]}

ELSE {

IF NOT r1.Substr[0, smin].Equal[r2.Substr[0, smin]] THEN RETURN [TRUE]};

IF s1d OR s2d THEN {

IF s1p#s2p AND NOT defined THEN {defined ← TRUE; reverse ← s2p > s1p};

EXIT};

IF c1.version.versionKind=numeric AND c2.version.versionKind=numeric AND c1.version.version#c2.version.version THEN RETURN [TRUE];

IF s1=l1 OR s2=l2 THEN LOOP;

IF s1p#s2p AND NOT defined THEN {defined ← TRUE; reverse ← s2p > s1p};

t1 ← l1-1-r1.FindBackward[s2: star, clipBeforeSeek: TRUE];

t2 ← l2-1-r2.FindBackward[s2: star, clipBeforeSeek: TRUE];

tmin ← MIN[t1, t2];

IF NOT r1.Substr[l1-tmin].Equal[r2.Substr[l2-tmin]] THEN RETURN [TRUE];

t1p ← (IF t1<l1 THEN t1 ELSE INT.LAST);

t2p ← (IF t2<l2 THEN t2 ELSE INT.LAST);

IF t1p#t2p THEN brev ← t2p > t1p;

REPEAT

FINISHED => IF diflen THEN RETURN [TRUE] ELSE RETURN Results[];

ENDLOOP;

j ← 1;

FOR j ← 1, j+1 WHILE minlen-j>=i DO

c1: PFSNames.Component ~ np1.Fetch[nl1-j];

c2: PFSNames.Component ~ np2.Fetch[nl2-j];

r1: RopePart ~ MPfsN.ComponentName[c1];

r2: RopePart ~ MPfsN.ComponentName[c2];

l1: INT ~ r1.InlineLength[]; l2: INT ~ r2.InlineLength[];

t1: INT ~ l1-1-r1.FindBackward[s2: star, clipBeforeSeek: TRUE];

t2: INT ~ l2-1-r2.FindBackward[s2: star, clipBeforeSeek: TRUE];

t1p: INT ~ (IF t1<l1 THEN t1 ELSE INT.LAST);

t2p: INT ~ (IF t2<l2 THEN t2 ELSE INT.LAST);

t1d: BOOL ~ (t1+1<l1 AND r1.InlineFetch[l1-(t1+2)]='*);

t2d: BOOL ~ (t2+1<l2 AND r2.InlineFetch[l2-(t2+2)]='*);

tmin: INT ~ MIN[t1, t2];

s1, s2, smin: INT;

IF c1.version.versionKind=numeric AND c2.version.versionKind=numeric AND c1.version.version#c2.version.version THEN RETURN [TRUE];

IF t1=l1 AND t2=l2 THEN {

IF NOT r1.Equal[r2, FALSE] THEN RETURN [TRUE]}

ELSE IF t1<l1 AND t2=l2 AND NOT t1d THEN {

IF NOT RP.Match[pattern: r1, object: r2, case: FALSE] THEN RETURN [TRUE];

np1 ← np1.ReplaceComponent[nl1-j, [c2.name, c1.version]]}

ELSE IF t1=l1 AND t2<l2 AND NOT t2d THEN {

IF NOT RP.Match[pattern: r2, object: r1, case: FALSE] THEN RETURN [TRUE];

np2 ← np2.ReplaceComponent[nl2-j, [c1.name, c2.version]]}

ELSE {

IF NOT r1.Substr[l1-tmin].Equal[r2.Substr[l2-tmin]] THEN RETURN [TRUE];

IF t1p#t2p AND NOT defined THEN {defined ← TRUE; reverse ← t2p > t1p};

IF t1d OR t2d THEN RETURN Results[];

s1 ← r1.Index[star]; s2 ← r2.Index[star]; smin ← MIN[s1, s2];

IF NOT r1.Substr[0, smin].Equal[r2.Substr[0, smin]] THEN RETURN [TRUE]};

REPEAT

FINISHED => ERROR--we should be at minlen-j=i and have found the double-star that stopped the first loop--;

ENDLOOP;

}};

PatternUnfactorMapList: PUBLIC PROC [pfml: PatternFactoredMapList] RETURNS [ml: MapList] ~ {

ml ← pfml.general;

IF ml=NIL THEN ml ← pfml.stampInd ELSE WHILE pfml.stampInd#NIL DO

ml ← CONS[pfml.stampInd.first, ml];

pfml.stampInd ← pfml.stampInd.rest;

ENDLOOP;

IF pfml.pattern#nullTuple THEN ml ← CONS[CreateMatcher[pfml.pattern], ml];

RETURN};

Generators

GeneratorUnion: PUBLIC PROC [g1, g2: Generator, sort: BOOL] RETURNS [Generator] ~ {

ug: UnionGenerator ~ NEW [UnionGeneratorPrivate ← [g1, g2, nullTuple, nullTuple, sort]];

IF ug.t1 = nullTuple THEN ug.done1 ← TRUE;

IF ug.t2 = nullTuple THEN ug.done2 ← TRUE;

RETURN [NEW [GeneratorRep ← [UnionNext, UnionClose, ug]]]};

UnionGenerator: TYPE ~ REF UnionGeneratorPrivate;

UnionGeneratorPrivate: TYPE ~ RECORD [

g1, g2: Generator,

t1, t2: VersionTuple,

sort: BOOL,

need1, need2: BOOL ← TRUE,

done1, done2, closed: BOOL ← FALSE];

UnionNext: PROC [gen: Generator] RETURNS [VersionTuple] ~ {

ug: UnionGenerator ~ NARROW[gen.data];

IF ug.closed THEN ERROR Error[[client, $GeneratorClosed, "generator closed", gen]];

IF ug.sort THEN {

IF ug.need1 THEN {

ug.need1 ← FALSE;

IF (ug.t1 ← ug.g1.Next[ug.g1])=nullTuple THEN {ug.done1 ← TRUE; ug.g1.Close[ug.g1]}};

IF ug.need2 THEN {

ug.need2 ← FALSE;

IF (ug.t2 ← ug.g2.Next[ug.g2])=nullTuple THEN {ug.done2 ← TRUE; ug.g2.Close[ug.g2]}};

IF ug.done1 AND ug.done2 THEN RETURN [nullTuple];

IF ug.done1 THEN {ug.need2 ← TRUE; RETURN [ug.t2]};

IF ug.done2 THEN {ug.need1 ← TRUE; RETURN [ug.t1]};

SELECT TupleCompare[ug.t1, ug.t2] FROM

less => {ug.need1 ← TRUE; RETURN [ug.t1]};

equal => ERROR Error[[client, $GeneratorsNotDisjoint, NIL, LIST[ug.g1, ug.g2]]];

greater => {ug.need2 ← TRUE; RETURN [ug.t2]};

ENDCASE => ERROR;

}

ELSE {

IF ug.need1 THEN {

ug.need1 ← FALSE;

IF (ug.t1 ← ug.g1.Next[ug.g1])=nullTuple THEN {ug.done1 ← TRUE; ug.g1.Close[ug.g1]}};

IF NOT ug.done1 THEN {ug.need1 ← TRUE; RETURN [ug.t1]};

IF ug.need2 THEN {

ug.need2 ← FALSE;

IF (ug.t2 ← ug.g2.Next[ug.g2])=nullTuple THEN {ug.done2 ← TRUE; ug.g2.Close[ug.g2]}};

IF NOT ug.done2 THEN {ug.need2 ← TRUE; RETURN [ug.t2]};

RETURN [nullTuple]};

};

UnionClose: PROC [gen: Generator] ~ {

ug: UnionGenerator ~ NARROW[gen.data];

IF ug.closed THEN ERROR Error[[client, $GeneratorClosedTwice, "generator closed twice", gen]];

ug.closed ← TRUE;

IF NOT ug.done1 THEN ug.g1.Close[ug.g1];

IF NOT ug.done2 THEN ug.g2.Close[ug.g2];

RETURN};

GeneratorSort: PUBLIC PROC [gen: Generator] RETURNS [Generator] ~ {

ScanGiven: PROC [map: Map, Consume: TupleConsumer, inOrder: BOOL, pfml: PatternFactoredMapList] RETURNS [MaybeTuple] ~ {

IF inOrder THEN ERROR;

IF map#nullMap THEN ERROR;

t: VersionTuple ~ gen.Next[gen];

IF t=nullTuple THEN EXIT;

IF pfml#[] AND NOT PfmlHas[pfml, t] THEN LOOP;

IF Consume[t] THEN RETURN [[TRUE, t]];

inOrder ← inOrder;

ENDLOOP;

RETURN [noMaybe]};

head: TupleList ← LIST[nullTuple];

tail: TupleList ← head;

NoteSorted: PROC [t: VersionTuple] RETURNS [BOOL] ~ {

this: TupleList ~ LIST[t];

tail ← tail.rest ← this;

RETURN [FALSE]};

IF SortScan[nullMap, ScanGiven, NoteSorted, []].found THEN ERROR;

gen.Close[gen];

RETURN [NEW [GeneratorRep ← [ListNext, DullClose, head]]]};

ListNext: PROC [gen: Generator] RETURNS [t: VersionTuple] ~ {

head: TupleList ~ NARROW[gen.data];

IF head.rest=NIL THEN RETURN [nullTuple];

t ← head.rest.first;

head.rest ← head.rest.rest;

RETURN};

FilterGenerator: PUBLIC PROC [gen: Generator, filters: MapList] RETURNS [Generator] ~ {

fg: FilterGen ~ NEW [FilterGenPrivate ← [gen, filters]];

RETURN [NEW [GeneratorRep ← [FilterNext, FilterClose, fg]]]};

FilterGen: TYPE ~ REF FilterGenPrivate;

FilterGenPrivate: TYPE ~ RECORD [gen: Generator, filters: MapList, closed: BOOL ← FALSE];

FilterNext: PROC [gen: Generator] RETURNS [VersionTuple] ~ {

fg: FilterGen ~ NARROW[gen.data];

IF fg.closed THEN ERROR Error[[client, $GeneratorClosed, "generator closed", gen]];

t: VersionTuple ~ fg.gen.Next[fg.gen];

IF t=nullTuple OR AllHave[fg.filters, t] THEN RETURN [t];

ENDLOOP};

FilterClose: PROC [gen: Generator] ~ {

fg: FilterGen ~ NARROW[gen.data];

IF fg.closed THEN ERROR Error[[client, $GeneratorClosedTwice, "generator closed twice", gen]];

fg.gen.Close[fg.gen]};

Helper

FixFetch: PROC [path: Name, i: INT] RETURNS [PFSNames.Component]

~ {RETURN path.Fetch[i]--assume PFS returns decent rope parts--};

END.