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;

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] ]};
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};
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;
DO
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]];
DO
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]};

FixFetch: PROC [path: Name, i: INT] RETURNS [PFSNames.Component]
~ {RETURN path.Fetch[i]--assume PFS returns decent rope parts--};

END.
º
VersionMap2Impl.Mesa
Copyright Ó 1990 by Xerox Corporation.  All rights reserved.
Last tweaked by Mike Spreitzer on April 10, 1992 9:52 am PDT
Basics
Using Maps
Generators
Helper
�Ê$•NewlineDelimiter

–

"cedar" style™
code™K™<K™<—K˜KšÏk	œ.�œf˜ 
K˜šÏnœ�œ
�˜Kš�œ"�œD˜pKš�œ$˜+K˜
—K˜Kš�œ
�œ žœ�œ˜KK˜Ihead™Kšœ
�œ�œ
˜Kšœ�œ�œ
�œ˜'K˜Kš
žœ�œ
�œ	�œ�œ˜7K˜š
ž	œ�œ
�œ�œ�œ˜6Kš�œ�œ
�œ�œ˜!Kš�Ïcœ
˜Kš�œ%�œ
�œ�œ˜;Kšœ�œ˜&Kšœ�œ˜%Kš�œ	�œ
�œ�œ˜Kš�œ�œ
�œ˜Kš�œE˜K—K˜š
ž
œ�œ:�œ�œ�œ˜dš�œ
˜Kš
�œ�œ�œ
�œ�œ˜FKš�œ�œ�œ�œ
�œ�œ
�œ�œ˜MKšœ�œ�œE˜TKš�œ�œ�œi�œ�œ
�œ�œ
�œ�œ˜°
Kš�œ�œ
�œc�œ�œ
�œ�œ˜Ž
Kš
œm˜mš�œ
Ïg
œ�œ
�
œ
�œ�œ
ŸÐcg
Ÿ˜PKš�œ$ 
œ 
œ�œ
�œ�œ˜TKš�œ
˜—Kš�œtŸ˜“
K˜š�œ˜Kšœ�œ
˜
Kšœ�œ
˜
Kš�œ�œ
�œ	˜K˜K˜Kš
œ˜—Kšœ
�œ˜
——K˜šžœ�œ
�œ�œ˜GK˜šžœ�œ
�œ�œ˜Aš�œ
�œ
�˜Kšœ�œ�œ˜Kšœ�œ�œ
˜Kš�œ�œ
˜—Kš�œ˜K˜—Kš
œ˜Kš
œ˜Kš�œ:�œ
�œ˜KKšœ	�œ˜#Kšœ�œ˜"š	�œ�œ
�œ�œ�˜)Kš�œ?�œ
�œ˜PKš�œ
˜—š�œ
�œ
�˜Kšœ�œ˜ Kšœ�œ
˜#Kš�œ�œ
˜—Kš�œ
�œA�œ
�œ˜_Kš�œ2˜8—K˜šžœ�œ�œ˜Tš�œk�œ�˜|Kšœ�œ˜Kšœ�œ
˜Kš�œ�œ
˜—Kš�œ*˜0Kš
œ˜—K˜šžœ�œ�œ˜Pš�œ�˜šœ�œ�˜%šœ�œ
�œ
�œ
˜Kšœ�œ˜&Kšœ�œ
˜)Kš�œ�œ˜—Kšœ�œ˜Kšœ�œ5˜XKš�œ�œ
˜—šœ�œ�˜"Kšœ�œ˜Kšœ�œ	˜Kšœ�œ5˜XKš�œ�œ
˜—Kšœ�œ5˜XKš�œ�œ˜——K˜šžœ�œ
�œ�œ
�œ�œ�œŸœ˜VKšœ�œ˜Kšœ�œ˜Kš�œ˜—K˜šž
œ�œ
�œ�œ
�œ�œ�œŸœ˜QKšœ
�œ˜Kšœ�œ˜Kšœ�œ˜š�œ�œ
�œ	�˜K˜#Kšœ&�œg�œ
˜–
Kš�œ
˜—Kš�œ	˜—K˜š
žœ�œ
�œ�œ�œ˜?š�œ�œ
�œ�˜*K˜#š�œ�˜!Kšœ�œ
˜Kšœ�œ�œ˜Kšœ�œ5˜SKš�œ�œ
˜—Kš
�œ3�œ�œ
�œ�œ˜fKš�œ
˜—Kš�œ�œ˜—K˜šžœ�œ
�œ�œ˜Pš�œ6�˜@Kšœ�œ˜Kšœ�œ
˜Kšœ�œ˜Kš�œ�œ
˜—Kš�œ@�œ
�œ
˜NKš�œ8�œ
�œ
˜FKš
œ-˜-Kš�œ˜—K˜šžœ�œ
�œ�œ˜SKš�œ0�œ
�œ
˜>Kš
œ%˜%Kš�œ˜—K˜š
žœ�œ
�œ�œ�œ˜CKš�œ%�œ*�œ#˜~—K˜š
žœ�œ
�œ�œ�œ˜=Kš�œ�œ�œ˜V—K˜šžœ�œ
�œ�œ˜SKš�œ-�œ
�œ
˜;Kš�œ6�œ
�œ
˜DKš
œ%˜%Kš�œ˜—K˜š
œ$˜$šœ�œ
˜Kš
œ(˜(Kš
œ(˜(—Kšœ
�œ
�œ˜"—K˜š
žœ�œ
�œ	�œ�œ˜HKš�œF˜L—K˜šžœ�œ
�œ�œ˜WKš�œ ˜&—K˜š
žœ�œ
�œ�œ�œ˜CKš�œ�œ�œ"˜Y—Lš
œ
™
šžœ�œ
�œ�œ
�œ�œ	˜5Kšœ�œ�œ˜—K˜Kšœ
�œ
�œ˜(K˜š
žœ�œ
�œ%�œ�œ˜Kš�œ!�œ	�œ
�˜8Kš
�œ
�œ�œ
�œ�œ˜0Kš�œ
˜—Kš�œ�œ˜—K˜š
žœ�œ
�œ%�œ�œ˜Jš�œ!�œ	�œ
�˜8Kš�œ�œ
�œ�œ˜+Kš�œ
˜—Kš�œ�œ˜—K˜š
žœ�œ
�œ1�œ�œ˜WKš�œ�œ
�œ�œ
�œ�œ˜PKš�œ�œ
�œ
�œ�œ
�œ�œ˜KKš�œ�œ
�œ
�œ�œ
�œ�œ˜IKš�œ�œ˜—K˜šžœ�œ
�œ�œ˜Cšž
œ�œ�œ�œ˜5Kš�œ
�œ
�œ�œ˜Kšœ�œ�œ�œ˜ —Kš
œ
˜
Kš�œ�œ�œ
�œ˜;Kš�œ˜—K˜šžœ�œ
�œ�œ˜9Kš
œ%˜%Kš�œ
�œ
�œ
�œ˜7Kš�œ	˜—K˜šžœ�œ
�œ�œ˜6Kš�œ�œ˜&—K˜Kšžœ�œ�œ�œ˜5K˜šžœ�œ
�œ!�œ˜QKš�œ�œ
�œ˜+Kš�œ�œ˜=—K˜šž
œ�œ
�œ�œ˜PKš�œ�œ
�œ˜/Kš�œ�œ˜A—K˜š
žœ�œ
�œ�œ�œ˜QKš�œ�œ
�œ˜2Kš�œ�œ"˜L—K˜šžœ�œ
�œ�œ˜TKš�œ�œ
�œ
�œ˜Kš�œ6˜<—K˜šž
œ�œ
�œ*�œ˜eKš�œ�œ
�œ˜0Kš
œ2˜2Kšžœ�œ
�œ
�œ˜+Kš�œ ˜&—K˜šž
œ�œ
�œ9žœ�œ
�œŸœ�œ˜¥
Kšœ
�œ�œ
˜Kš�œ�œ�œ
�œ˜Vš�œ
�œ
�˜Kšœ(�œ
˜-Kšœ�œ
˜$K˜GKš�œ�œ˜-—š�œ
�œ
�˜Kšœ,�œ
˜1Kšœ#�œ
˜(Kš
œO˜OKš�œ�œ˜-—š�œ
�œ
�˜Kšœ&�œ
˜+Kšœ�œ
˜"Kš
œC˜CKšœ2�œ
˜7Kš	œ,�œ
�œ0�œ
�œ˜‰
Kš	œ+�œ0�œ&�œ
�œ˜®
š�œ�œ˜0Kš
œV˜VKš�œ
�œ
�œ˜3š�œ%˜'Kš�œ#˜&—Kš�œ�˜š�œ˜Kšœ�œ(˜<Kš
œ˜—Kš
œ˜——š�œ
�œ˜š�œ�œ˜4Kš�œ�œ˜1Kš�œ�œ˜0—Kš�œ	˜—Kš�œ�œ�œ˜MKš�œ�œ
�œ˜IKš�œ	˜—K˜Kšœ�œ˜!K˜šžœ�œ
�œ�œ�œ�œ˜jKš�œ�œ
�œ�œ˜.Kš�œ�œ
�œ�œ˜.Kšœ�œ˜!Kšœ�œ˜ Kšœ�œ�œ˜Kšœ�œ˜Kšœ�œ˜Kšœ�œ�œ
˜%š
žœ�œ
�œ�œ�œ˜Fš�œ˜
Kš�œ
�œ�œ˜Kš�œ
�œ�œ
˜——š�œ�œ
�˜ K˜&K˜&Kš
œ'˜'Kš
œ'˜'Kšœ�œ�œ˜9Kšœ�œ�œ˜3Kš
œ�œ�œ�œ�œ
�œ
�œ˜,Kš
œ�œ�œ�œ�œ
�œ
�œ˜,Kšœ�œ�œ˜2Kšœ�œ�œ˜2Kšœ�œ�œ	˜Kšœ�œ
˜š�œ�œ�œ˜Kš�œ
�œ�œ�œ
�œ�œ˜.—š�œ
�œ�œ�œ
�œ�œ˜*Kš�œ
�œ
�œ&�œ�œ
�œ�œ˜IKš
œ5˜5—š�œ
�œ�œ�œ
�œ�œ˜*Kš�œ
�œ
�œ&�œ�œ
�œ�œ˜IKš
œ5˜5—š�œ˜Kš
�œ
�œ.�œ
�œ�œ˜H—š�œ�œ�œ˜Kš
�œ	�œ
�œ	�œ�œ˜FKš�œ˜—Kš�œ �œ �œ'�œ
�œ�œ˜‚
Kš�œ�œ�œ
�œ
˜Kš
�œ	�œ
�œ	�œ�œ˜FKšœ4�œ˜:Kšœ4�œ˜:Kšœ�œ	˜Kš
�œ
�œ.�œ
�œ�œ˜GKšœ�œ�œ�œ
�œ
�œ˜'Kšœ�œ�œ�œ
�œ
�œ˜'Kš�œ	�œ˜!Kš
�˜Kš�œ�œ�œ
�œ�œ�œ
�œ˜?Kš�œ
˜—K˜š�œ�œ
�˜#K˜*K˜*Kš
œ'˜'Kš
œ'˜'Kšœ�œ�œ˜9Kšœ�œ2�œ˜?Kšœ�œ2�œ˜?Kš
œ�œ�œ�œ�œ
�œ
�œ˜,Kš
œ�œ�œ�œ�œ
�œ
�œ˜,Kšœ�œ�œ˜7Kšœ�œ�œ˜7Kšœ�œ�œ	˜Kšœ�œ
˜Kš�œ �œ �œ'�œ
�œ�œ˜‚
š�œ�œ�œ˜Kš�œ
�œ�œ�œ
�œ�œ˜.—š�œ
�œ�œ�œ
�œ�œ˜*Kš�œ
�œ
�œ&�œ�œ
�œ�œ˜IKš
œ9˜9—š�œ
�œ�œ�œ
�œ�œ˜*Kš�œ
�œ
�œ&�œ�œ
�œ�œ˜IKš
œ9˜9—š�œ˜Kš
�œ
�œ.�œ
�œ�œ˜GKš
�œ	�œ
�œ	�œ�œ˜FKš�œ�œ�œ
�œ˜$Kšœ1�œ	˜=Kš
�œ
�œ.�œ
�œ�œ˜H—Kš
�˜Kš�œ�ŸYœ
˜kKš�œ
˜—K˜—K˜šžœ�œ
�œ �œ˜\K˜š
�œ�œ
�œ�œ
�œ�œ
�˜AKšœ�œ˜#Kš
œ#˜#Kš�œ
˜—Kš�œ�œ�œ"˜JKš�œ˜—Lš
œ
™
š
žœ�œ
�œ�œ�œ˜SKšœ�œ@˜XKš�œ�œ�œ
˜*Kš�œ�œ�œ
˜*Kš�œ�œ0˜;—K˜Kšœ�œ�œ˜1šœ�œ�œ˜&K˜Kš
œ˜Kšœ�œ
˜Kšœ�œ�œ
˜Kšœ�œ�œ˜$—K˜šž	œ�œ�œ˜;Kšœ�œ˜&Kš�œ�œ
�œ<˜Sš�œ	�œ˜š�œ
�œ˜Kšœ�œ
˜Kš�œ'�œ
�œ˜U—š�œ
�œ˜Kšœ�œ
˜Kš�œ'�œ
�œ˜U—Kš�œ
�œ
�œ
�œ
˜1Kš�œ
�œ
�œ�œ
˜3Kš�œ
�œ
�œ�œ
˜3š�œ�˜&Kšœ�œ�œ
˜*Kšœ	�œ(�œ�œ˜PKšœ�œ�œ
˜-Kš�œ�œ
˜—K˜
—š�œ˜š�œ
�œ˜Kšœ�œ
˜Kš�œ'�œ
�œ˜U—Kš
�œ
�œ
�œ
�œ�œ
˜7š�œ
�œ˜Kšœ�œ
˜Kš�œ'�œ
�œ˜U—Kš
�œ
�œ
�œ
�œ�œ
˜7Kš�œ˜—K˜—K˜šž
œ�œ˜%Kšœ�œ˜&Kš�œ�œ
�œG˜^Kšœ�œ
˜Kš�œ
�œ
�œ˜(Kš�œ
�œ
�œ˜(Kš�œ˜—K˜šž
œ�œ
�œ�œ˜Cš
ž	œ�œžœ�œ �œ˜xKš�œ	�œ
�œ
˜Kš�œ
�œ
�œ
˜š
�˜Kš
œ ˜ Kš�œ
�œ
�œ
˜Kš
�œ	�œ
�œ�œ
�œ
˜.Kš�œ�œ
�œ�œ˜&Kš
œ˜Kš�œ
˜—Kš�œ˜—Kšœ�œ˜"K˜šž
œ�œ�œ�œ˜5Kšœ�œ˜K˜Kš�œ�œ˜—Kš�œ4�œ
�œ
˜AK˜Kš�œ�œ0˜;—K˜šžœ�œ�œ˜=Kšœ�œ˜#Kš�œ�œ
�œ
�œ
˜)K˜K˜Kš�œ˜—K˜šžœ�œ
�œ$�œ˜WKšœ�œ%˜8Kš�œ�œ2˜=—K˜Kšœ�œ�œ˜'Kš	œ�œ�œ,�œ�œ˜YK˜šž
œ�œ�œ˜<Kšœ�œ˜!Kš�œ�œ
�œ<˜Sš
�˜Kš
œ&˜&Kš�œ
�œ�œ
�œ˜9Kš�œ˜	——K˜šžœ�œ˜&Kšœ�œ˜!Kš�œ�œ
�œG˜^Kš
œ˜—K˜L™šžœ�œ�œ�œ˜@Kšœ�œŸ(œ˜A—K˜Kš�œ
˜—…—MgÞ