[Indigo]<Cedar>VersionMap>VersionMapBuilderImpl.mesa!4

VersionMapBuilderImpl.mesa

Russ Atkinson, February 18, 1983 5:07 pm

DIRECTORY

BcdDefs USING [BCD],

Convert USING [MapValue, Parse, Value, ValueToRope],

ConvertUnsafe USING [AppendRope, ToRope],

DFUser USING

[CleanupEnumerate, EnumerateEntries, EnumerateProcType, TooManyEntries],

Environment USING [bytesPerWord],

FileIO USING [Open],

Heap USING [systemZone],

IFSFile USING

[Close, Completer, FileHandle, Finalize, FSInstance, Initialize, Login, Logout, Open, StartRead],

IO USING

[Close, GetChar, GetIndex, GetLength, GetSequence, PutChar, SetIndex, SetLength, STREAM],

MessageWindow USING [Append],

PriorityQueue USING [Insert, Predict, Ref, Remove, SortPred],

Process USING [Detach, SecondsToTicks, SetTimeout],

Rope USING

[Cat, Concat, Equal, Fetch, FetchType, Flatten, FromProc, Index, MakeRope, Match, Replace, ROPE, Run, Size, SkipTo, Substr],

SafeStorage USING [NewZone],

SymTab USING [Create, Fetch, Insert, Ref],

System USING [GetClockPulses, Microseconds, PulsesToMicroseconds],

Time USING [Current, defaultTime],

TimeStamp USING [Stamp],

UnsafeSTP USING

[Close, Create, DesiredProperties, Enumerate, FileInfo, GetFileInfo, Handle, Login, NoteFileProcType, Open, SetDesiredProperties],

UserCredentials USING [GetUserCredentials],

UserExec USING [AskUser, ExecHandle, GetExecHandle, GetStreams],

VersionMap USING

[Fetch, FetchName, GetPrefix, Length, Map, MapRep, MapEntry, NameMapIndex, MyStamp],

VersionMapBuilder USING [EachProc, FilterProc];

VersionMapBuilderImpl: CEDAR MONITOR

IMPORTS Convert, ConvertUnsafe, DFUser, FileIO, Heap, IFSFile, IO, MessageWindow, PriorityQueue, Process, Rope, SafeStorage, UnsafeSTP, SymTab, System, Time, UserCredentials, UserExec, VersionMap

EXPORTS VersionMapBuilder

SHARES VersionMap

= BEGIN OPEN Rope, VersionMap, VersionMapBuilder;

Types & stuff

XMyStamp: TYPE = MACHINE DEPENDENT RECORD [lo,num,hi: CARDINAL];

must be as long as TimeStamp.Stamp

we extract num to use as uniformly distributed bits

num should be the low bits of the time

NullStamp: MyStamp ← [0, 0, 0];

MyStampAsHex: TYPE = PACKED ARRAY [0..12) OF [0..16);

XMap: TYPE = REF MapRep;

XMapList: TYPE = LIST OF Map;

XMapRep: PUBLIC TYPE = RECORD [

names: ROPE ← NIL,

prefix: NameMapIndex ← 0, -- place to find factored prefix

entries: SEQUENCE len: CARDINAL OF MapEntry];

the full names follow the entries, sans prefix, follow the index

each full name ends in a CR (15C)

XMapEntry: TYPE = RECORD

[stamp: MyStamp, index: NameMapIndex];

XNameMapIndex: TYPE = INT; -- byte index of name in map

NullNameIndex: NameMapIndex = LAST[NameMapIndex];

EntryIndex: TYPE = CARDINAL;

NullEntryIndex: EntryIndex = LAST[CARDINAL];

EntryRef: TYPE = REF EntryRep;

EntryRep: TYPE = RECORD [next: EntryRef, name: ROPE, version: MyStamp];

GenerateData: TYPE = REF GenerateDataRep;

GenerateDataRep: TYPE = RECORD [

host,directory: ROPE ← NIL,

pq: PriorityQueue.Ref ← NIL,

list: EntryRef ← NIL,

countGoing: NAT ← 0,

errors: NAT ← 0,

done: CONDITION];

pz: ZONE ← SafeStorage.NewZone[prefixed];

qz: ZONE ← SafeStorage.NewZone[quantized];

alarmClock: CONDITION;

reportTime: CONDITION;

reportInterval: NAT ← 0;

reportProcess: PROCESS ← NIL;

report: ROPE ← NIL;

fileCount: INT ← 0;

outstandingRequests: INT ← 2; -- # of processes to have looking at version pages

lastMap: Map ← NIL; -- last map produced (useful for debugging)

maxPiece: INT ← 8000;

**** BEGIN EXPORTED PROCEDURES ****

VersionNotAvailable: PUBLIC ERROR = CODE;

NameError: PUBLIC ERROR = CODE;

DuplicateVersionSignal: PUBLIC SIGNAL = CODE;

WriteMapToFile: PUBLIC PROC

[map: Map, name: ROPE, checkForDuplicateVersions: BOOL ← FALSE] = {

lagStamp: MyStamp ← NullStamp;

prefix: ROPE ← NIL;

st: IO.STREAM ← FileIO.Open[name, write];

names: ROPE ← map.names;

firstCR: INT ← names.Index[0, "\n"];

prefix ← names.Flatten[0, firstCR];

MyPut[st, prefix];

MyPut[st, "\n"];

FOR i: NAT IN [0..map.len) DO

Display the entry.

entry: MapEntry ← map[i];

index: INT ← entry.index;

stamp: MyStamp ← entry.stamp;

IF stamp = lagStamp AND checkForDuplicateVersions THEN {

Examine short names for equality.

r1: ROPE ← IndexToShortName[map, map[i-1].index];

r2: ROPE ← IndexToShortName[map, index];

IF r1.Equal[r2, FALSE]

THEN LOOP

ELSE SIGNAL DuplicateVersionSignal};

lagStamp ← stamp;

PutStampAsHex[st, stamp];

MyPut[st, " "];

c: CHAR ← names.Fetch[index];

index ← index + 1;

IO.PutChar[st, c];

IF c = '\n THEN EXIT;

ENDLOOP;

MyPut[st, "\n"];

IO.SetLength[st, IO.GetIndex[st]]; -- force goddamm truncation already!!!

IO.Close[st];

};

ParseMapFromFile: PUBLIC PROC [name: ROPE] RETURNS [map: Map ← NIL] = {

the 1st line must have the prefix for the map

the rest of the lines have version # followed by the mid name

(full name sans prefix)

st: IO.STREAM ← FileIO.Open[name, read];

bytes: INT ← IO.GetLength[st];

getNext: PROC RETURNS [CHAR] = {

RETURN [st.GetChar[]];

};

rope: ROPE ← Rope.FromProc[bytes, getNext, maxPiece];

pos: INT ← 0;

head,list: EntryRef ← NIL;

prefix: ROPE ← IO.GetSequence[st];

IO.Close[st];

prefix ← rope.Flatten[0, pos ← rope.Index[0, "\n"]];

pos ← pos + 1;

WHILE pos < bytes DO

c: CHAR ← rope.Fetch[pos];

start: INT ← 0;

hex: MyStampAsHex ← ALL[0];

pos ← pos + 1;

IF c <= 40C THEN LOOP;

grab the hex stamp

FOR i: NAT IN [0..12) WHILE pos <= bytes DO

x: INTEGER ← 0;

SELECT c FROM

IN ['0..'9] => x ← c - '0;

IN ['A..'F] => x ← (c - 'A) + 10;

IN ['a..'f] => x ← (c - 'a) + 10;

ENDCASE => EXIT;

hex[i] ← x;

c ← rope.Fetch[pos];

pos ← pos + 1;

ENDLOOP;

skip over separators

WHILE pos <= bytes DO

IF c > 40C THEN {start ← pos - 1; EXIT};

c ← rope.Fetch[pos];

pos ← pos + 1;

ENDLOOP;

grab the name

WHILE pos <= bytes DO

IF c <= 40C THEN {

name ← rope.Substr[start, pos-start-1]; EXIT};

c ← rope.Fetch[pos];

pos ← pos + 1;

ENDLOOP;

IF head = NIL

THEN head ← list ← NewEntryRef[name]

ELSE {list.next ← NewEntryRef[name]; list ← list.next};

list.version ← LOOPHOLE[hex];

count ← count + 1;

ENDLOOP;

lastMap ← map ← GenerateMapFromEntryList[head, prefix, count];

};

SetReportInterval: PUBLIC PROC [seconds: NAT ← 0] = TRUSTED {

SetReportInterval sets the interval between reports of progress to the message window. These reports are made by GenerateMapFromRemote and other long-winded procedures. If the interval is 0, then no reporting is performed.

temp: NAT ← IF seconds = 0 THEN 10 ELSE seconds;

forkIt: ENTRY PROC = TRUSTED {

ENABLE UNWIND => NULL;

reportInterval ← seconds;

IF reportProcess = NIL AND seconds # 0 THEN

Process.Detach[reportProcess ← FORK ClarkKent[]];

BROADCAST reportTime;

};

Process.SetTimeout[@reportTime, Process.SecondsToTicks[temp]];

forkIt[];

};

GenerateMapFromRemote: PUBLIC PROC

[host: ROPE ← NIL, directory: ROPE ← NIL, oldMap: Map ← NIL, filter: FilterProc ← NIL]

RETURNS [map: Map] = TRUSTED {

head: EntryRef ← NIL;

prefix: ROPE ← NIL;

IF host = NIL THEN host ← "Ivy";

IF directory = NIL THEN {

user: ROPE ← UserCredentials.GetUserCredentials[].name;

user ← user.Flatten[0, user.Index[0, "."]]; -- remove registry

directory ← Rope.Cat["<", user, ">*.bcd"]};

IF directory.Index[0, "*"] = directory.Size[] THEN {

directory ← directory.Concat["*.bcd"]};

[head, prefix, count] ← GenerateEntryListFromRemote[host, directory, oldMap, filter];

lastMap ← map ← GenerateMapFromEntryList[head, prefix, count];

};

GenerateMapFromDFFile: PUBLIC PROC

[name: ROPE ← NIL, pattern: ROPE ← NIL, oldMap: Map ← NIL, filter: FilterProc ← NIL]

RETURNS [map: Map] = TRUSTED {

generates a map from a DF file

requires export of DFUser to run

flat: ROPE ← name.Flatten[];

string: LONG STRING ← LOOPHOLE[flat];

head: EntryRef ← NIL;

prefix: ROPE ← NIL;

guess: NAT ← 8000;

tab: SymTab.Ref ← NIL;

eachProc: DFUser.EnumerateProcType = TRUSTED {

PROC [host, directory, shortName: LONG STRING, version: CARDINAL, createTime: LONG CARDINAL, includedDFFile, importedDFFile, readOnly: BOOL, immediateParentDF: LONG STRING]

localName: STRING ← [120];

eachName: ROPE ← NIL;

new: EntryRef ← NIL;

Add1: PROC [c: CHAR] = TRUSTED {

k: NAT ← localName.length;

localName[k] ← c;

localName.length ← k+1};

Add: PROC [s1,s2,s3,s4: LONG STRING ← NIL] = TRUSTED {

as: ARRAY [0..4) OF LONG STRING ← [s1, s2, s3, s4];

k: NAT ← localName.length;

FOR i: NAT IN [0..4) DO

s: LONG STRING ← as[i];

IF s # NIL THEN

FOR j: NAT IN [0..s.length) DO

localName[k] ← s[j];

k ← k + 1;

ENDLOOP;

localName.length ← k;

};

eachName ← ConvertUnsafe.ToRope[shortName];

IF NOT Rope.Match[pattern, eachName, FALSE] THEN RETURN; -- no match

Accumulate the long file name

IF host # NIL THEN Add["[", host, "]"];

IF directory # NIL THEN Add["<", directory, ">", shortName];

IF version # 0 THEN {Add1['!]; Convert.MapValue[Add1, [signed[version]]]};

eachName ← ConvertUnsafe.ToRope[localName];

IF LookupName[tab, eachName] THEN RETURN; -- name already here

IF filter # NIL AND NOT filter[eachName] THEN RETURN; -- user does not want this one

new ← NewEntryRef[eachName];

IF eachName.Index[0, ".bcd", FALSE] = eachName.Size[] THEN {

we use the create date as the version stamp

new.version ← LOOPHOLE[TimeStamp.Stamp[0, 0, createTime]]};

count ← count + 1;

new.next ← head;

head ← new;

StoreName[tab, eachName];

};

IF pattern = NIL THEN pattern ← "*";

[head, prefix, count] ← GenerateEntryListFromMap[oldMap];

tab ← GenSymTabFromVersionMap[oldMap];

FOR try: NAT IN [0..4) DO

err: BOOL ← FALSE;

{ENABLE UNWIND => DFUser.CleanupEnumerate[];

exec: UserExec.ExecHandle ← UserExec.GetExecHandle[];

in,out: IO.STREAM ← NIL;

[in: in, out: out] ← UserExec.GetStreams[exec];

DFUser.EnumerateEntries [

dfFileName: string, procToCall: eachProc, nEntriesInDFFiles: guess,

in: in, out: out, confirmData: NIL, Confirm: Confirm

! DFUser.TooManyEntries => {err ← TRUE; CONTINUE}];

DFUser.CleanupEnumerate[]};

guess ← guess + guess;

IF err OR count = 0 THEN LOOP;

lastMap ← map ← GenerateMapFromEntryList[head, NIL, count];

RETURN

ENDLOOP;

ERROR DFUser.TooManyEntries;

};

KeyList: LIST OF ATOM = LIST[$Y, $N, $A, $Q];

Confirm: PROC

[in, out: IO.STREAM, data: REF, msg: ROPE, dch: CHAR] RETURNS [CHAR] = TRUSTED {

exec: UserExec.ExecHandle ← UserExec.GetExecHandle[];

answer: ATOM ← UserExec.AskUser

[msg: " OK? ", defaultKey: $Y, exec: exec, keyList: KeyList];

SELECT answer FROM

$Y => RETURN ['Y];

$N => RETURN ['N];

$A => RETURN ['A];

$Q => RETURN ['Q];

ENDCASE => RETURN ['?];

};

GenerateMapFromProc: PUBLIC PROC

[each: EachProc, data: REF ← NIL, prefix: ROPE ← NIL] RETURNS [map: Map] = {

generates a map from user-supplied entries

head: EntryRef ← NIL;

stamp: TimeStamp.Stamp;

new: EntryRef ← NIL;

generate the next entry

[stamp, name] ← each[data];

IF name.Size[] = 0 THEN EXIT;

new ← NewEntryRef[name];

new.version ← LOOPHOLE[stamp];

count ← count + 1;

new.next ← head;

head ← new;

ENDLOOP;

lastMap ← map ← GenerateMapFromEntryList[head, prefix, count];

};

FilterProc: TYPE = PROC [name: ROPE] RETURNS [ok: BOOL];

type of user-supplied filter on file names

return TRUE to use name, FALSE to skip it

bcdList: LIST OF ROPE ← LIST["bcd", "symbols"];

NonBCDFilter: PUBLIC FilterProc = {

filters out BCDs

RETURN[NOT TestExtension[name, bcdList]]

};

OnlyBCDFilter: PUBLIC FilterProc = {

filters in BCDs only

RETURN[TestExtension[name, bcdList]]

};

MergeMaps: PUBLIC PROC

[map1,map2: VersionMap.Map] RETURNS [map: VersionMap.Map] = {

implicit1: INT ← map1.len - CountExplicitPrefixes[map1];

prefix1: ROPE ← map1.GetPrefix[];

implicit2: INT ← map2.len - CountExplicitPrefixes[map2];

prefix2: ROPE ← map2.GetPrefix[];

prefix: ROPE ← prefix1;

IF map1.Length[] = 0 THEN RETURN [map2];

IF map2.Length[] = 0 THEN RETURN [map1];

IF implicit1*prefix1.Size[] < implicit2*prefix2.Size[] THEN {

We save more characters by using map2's prefix, so swap the maps

tempMap: VersionMap.Map ← map1;

map1 ← map2;

map2 ← tempMap;

};

IF NOT Rope.Equal[prefix1, prefix2, FALSE] THEN

The prefixes are not equal, so we must expand map2

map2 ← DistributePrefix[map2];

Now we have to merge the maps.

prefix1 ← map1.GetPrefix[];

prefix2 ← map2.GetPrefix[];

map ← pz.NEW[VersionMap.MapRep[map1.len + map2.len]];

map.names ← Rope.Replace[map2.names, 0, prefix2.Size[]+1, map1.names];

map.prefix ← map1.prefix;

{-- now merge the index set

index1: NAT ← 0;

index2: NAT ← 0;

valid1, valid2: BOOL ← TRUE;

offset: INT ← map1.names.Size[] - prefix2.Size[] - 1; -- offset of start of map2 names

entry1: VersionMap.MapEntry ← map1[index1];

entry2: VersionMap.MapEntry ← map2[index2];

FOR i: NAT IN [0..map.len) DO

SELECT TRUE FROM

NOT valid2 OR (valid1 AND VersionPred[entry1.stamp, entry2.stamp]) => {

map1 has the better entry

map[i] ← entry1;

index1 ← index1 + 1;

valid1 ← index1 < map1.len;

IF valid1 THEN entry1 ← map1[index1];

};

valid2 => {

map2 has the better entry

entry2.index ← entry2.index + offset;

map[i] ← entry2;

index2 ← index2 + 1;

valid2 ← index2 < map2.len;

IF valid2 THEN entry2 ← map2[index2];

};

ENDCASE => ERROR; -- we blew it somewhere

ENDLOOP;

};

DistributePrefix: PUBLIC PROC

[map: VersionMap.Map] RETURNS [newMap: VersionMap.Map ← NIL] = {

DistributePrefix[map] takes a version map and expands all of the prefixes in it. This is good preparation for merging version maps, of course. The resulting map will be the initial map if all of the entries have explicit prefixes. The resulting map will have a prefix stored in the names, incidentally.

IF map # NIL THEN {

names: ROPE ← map.names;

explicit: INT ← CountExplicitPrefixes[map];

implicit: INT ← map.len - explicit;

prefix: ROPE ← map.GetPrefix[];

prefixSize: INT ← prefix.Size[];

newNamesLen: INT ← names.Size[] + implicit * prefixSize;

delta: INT ← 0;

prefixPos: INT ← 0;

inName: BOOL ← TRUE;

namePos: INT ← prefixSize;

nextIndex: NAT ← 0;

getChar: PROC RETURNS [c: CHAR] = {

IF prefixPos < prefixSize THEN {

We are expanding the prefix

c ← prefix.Fetch[prefixPos];

prefixPos ← prefixPos + 1;

RETURN};

IF inName THEN {

We are expanding the file name

c ← names.Fetch[namePos];

namePos ← namePos + 1;

inName ← c # '\n;

RETURN};

We need another entry

namePos ← map[nextIndex].index;

nextIndex ← nextIndex + 1;

inName ← TRUE;

c ← names.Fetch[namePos];

SELECT c FROM

'/, '[ => prefixPos ← prefixSize;

ENDCASE => prefixPos ← 0;

ENDLOOP;

};

IF implicit <= 0 OR names.Fetch[map.prefix] = '\n THEN

RETURN [map]; -- no prefix to distribute

newMap ← pz.NEW[VersionMap.MapRep[map.len]];

Oddly enough, first we build the index

FOR i: CARDINAL IN [0..map.len) DO

entry: VersionMap.MapEntry ← map[i];

char: CHAR ← names.Fetch[entry.index];

entry.index ← entry.index + delta;

newMap[i] ← entry;

SELECT char FROM

'/, '[ => {};

ENDCASE => delta ← delta + prefixSize;

ENDLOOP;

newMap.prefix ← 0; -- we retain the prefix, even though it is distributed

newMap.names ← Rope.FromProc[newNamesLen, getChar, maxPiece];

};

SplitMap: PUBLIC PROC

[map: VersionMap.Map] RETURNS [symbols,source: VersionMap.Map ← NIL] = {

SplitMap[map] splits a version map into maps for symbols and source. The names rope is shared between both the input map and the two resulting maps, which is much more efficient, but may hold on to some rather large ropes.

IF map # NIL THEN {

count1,count2: INT ← 0;

chars1,chars2: INT ← 0;

index1,index2: INT ← 0;

names: ROPE ← map.names;

Determine the size of the symbols and source maps

FOR i: NAT IN [0..map.len) DO

entry: VersionMap.MapEntry ← map[i];

pos: INT ← Rope.SkipTo[names, entry.index, ".\n"]+1;

len: INT ← Rope.SkipTo[names, pos, "!\n"] - pos;

IF len > 0 THEN {

chars: INT ← Rope.SkipTo[names, pos, "\n"] - entry.index;

SELECT len FROM

Rope.Run[names, pos, "bcd", 0, FALSE] =>

{count1 ← count1 + 1; chars1 ← chars1 + chars};

Rope.Run[names, pos, "symbols", 0, FALSE] =>

{count1 ← count1 + 1; chars1 ← chars1 + chars};

ENDCASE =>

{count2 ← count2 + 1; chars2 ← chars2 + chars};

};

ENDLOOP;

Conditionally create the symbols map

IF count1 > 0 THEN {

symbols ← pz.NEW[VersionMap.MapRep[count1]];

symbols.prefix ← map.prefix;

symbols.names ← map.names};

Conditionally create the source map

IF count2 > 0 THEN {

source ← pz.NEW[VersionMap.MapRep[count2]];

source.prefix ← map.prefix;

source.names ← map.names};

Now, actually copy the entries to the new map(s)

FOR i: NAT IN [0..map.len) DO

entry: VersionMap.MapEntry ← map[i];

pos: INT ← Rope.SkipTo[names, entry.index, ".\n"]+1;

len: INT ← Rope.SkipTo[names, pos, "!\n"] - pos;

IF len > 0 THEN {

SELECT len FROM

Rope.Run[names, pos, "bcd", 0, FALSE] =>

{symbols[index1] ← entry; index1 ← index1 + 1};

Rope.Run[names, pos, "symbols", 0, FALSE] =>

{symbols[index1] ← entry; index1 ← index1 + 1};

ENDCASE =>

{source[index2] ← entry; index2 ← index2 + 1};

};

ENDLOOP;

};

CompressMap: PUBLIC PROC

[map: VersionMap.Map] RETURNS [newMap: VersionMap.Map ← NIL] = {

CompressMap[map] compresses a version map, discarding unused portions from the names. We also make a half-hearted attempt to factor out the first prefix we see from the rest of the names (we should be able to do better).

names: ROPE ← map.names;

newLen: INT ← 0;

inName: BOOL ← FALSE;

inPrefix: BOOL ← TRUE;

nextIndex: NAT ← 0;

ropePos: INT ← 0;

namePos: INT ← 0;

prefix: ROPE ← names.Flatten[namePos, names.SkipTo[namePos, "\n"]];

prefixLen: INT ← prefix.Size[];

getChar: PROC RETURNS [c: CHAR] = {

IF inPrefix THEN {

We are expanding the prefix

IF namePos < prefixLen

THEN {c ← prefix.Fetch[namePos]; namePos ← namePos + 1}

ELSE {c ← '\n; inPrefix ← FALSE};

ropePos ← ropePos + 1;

RETURN};

IF inName THEN {

We are expanding the file name

c ← names.Fetch[namePos];

namePos ← namePos + 1;

inName ← c # '\n;

ropePos ← ropePos + 1;

RETURN};

We need another entry

namePos ← newMap[nextIndex].index;

newMap[nextIndex].index ← ropePos;

nextIndex ← nextIndex + 1;

inName ← TRUE;

ENDLOOP;

};

newMap ← pz.NEW[MapRep[map.len]];

newMap.prefix ← 0;

IF prefixLen = 0 THEN

Find some suitable prefix

FOR i: CARDINAL IN [0..map.len) DO

entry: VersionMap.MapEntry ← map[i];

char: CHAR ← names.Fetch[entry.index];

SELECT char FROM

'[ => {

end: INT ← Rope.SkipTo[names, entry.index, ">\n"];

IF names.Fetch[end] = '> THEN {

prefixLen ← end - entry.index + 1;

prefix ← names.Flatten[entry.index, prefixLen];

EXIT}};

ENDCASE;

ENDLOOP;

Calculate the eventual size of the rope & adjust the new map indexes

newLen ← prefixLen+1;

FOR i: CARDINAL IN [0..map.len) DO

entry: VersionMap.MapEntry ← map[i];

pos: INT ← entry.index;

char: CHAR ← names.Fetch[pos];

len: INT ← Rope.SkipTo[names, pos, "\n"] - pos + 1;

SELECT char FROM

'[ =>

IF Rope.Run[names, pos, prefix, 0, FALSE] = prefixLen

THEN {

Factor out this prefix (including from the new map)

newLen ← newLen + len - prefixLen;

entry.index ← pos + prefixLen}

ELSE newLen ← newLen + len;

ENDCASE => newLen ← newLen + len;

newMap[i] ← entry;

ENDLOOP;

Finally make the new names

newMap.names ← Rope.FromProc[newLen, getChar, maxPiece];

};

**** END EXPORTED PROCEDURES ****

TestExtension: PROC [name: ROPE, extList: LIST OF ROPE] RETURNS [BOOL] = {

exclPos: INT ← name.Size[];

pos: INT ← exclPos;

WHILE pos > 0 DO

c: CHAR ← name.Fetch[pos ← pos - 1];

SELECT c FROM

'. => {

len: INT ← exclPos-(pos ← pos + 1);

FOR xl: LIST OF ROPE ← extList, xl.rest WHILE xl # NIL DO

ext: ROPE ← xl.first;

IF Rope.Run[name, pos, ext, 0, FALSE] = len

THEN RETURN [TRUE];

ENDLOOP;

RETURN [FALSE]};

'! => exclPos ← pos;

ENDCASE;

ENDLOOP;

RETURN [FALSE];

};

CurrentTime: PROC RETURNS [ROPE] = TRUSTED {

RETURN [Convert.ValueToRope[[time[Time.Current[]]]]];

};

MyStampToHex: PROC [stamp: MyStamp] RETURNS [ROPE] = {

index: NAT ← 0;

each: PROC RETURNS [c: CHAR] = {

x: CARDINAL [0..15] ← hex[index];

IF x IN [0..9] THEN c ← '0 + x ELSE c ← 'A + (x-10);

index ← index + 1;

};

hex: MyStampAsHex ← LOOPHOLE[stamp];

RETURN [Rope.FromProc[12, each]];

};

PutStampAsHex: PROC [st: IO.STREAM, stamp: MyStamp] = {

hex: MyStampAsHex ← LOOPHOLE[stamp];

FOR index: CARDINAL IN [0..12) DO

x: CARDINAL [0..15] ← hex[index];

c: CHAR ← IF x IN [0..9] THEN '0 + x ELSE 'A + (x-10);

st.PutChar[c];

ENDLOOP;

};

IndexToShortName: PROC [map: Map, index: NameMapIndex] RETURNS [ROPE] = {

Return the name without the prefix or version

names: ROPE ← map.names;

end: INT ← names.SkipTo[index, "!\n"];

pos: INT ← end;

WHILE pos > index DO

SELECT names.Fetch[pos] FROM

'/, '], '> => EXIT;

ENDCASE;

pos ← pos - 1;

ENDLOOP;

RETURN [names.Substr[pos, end-pos]];

};

Snooze: ENTRY PROC [lp: LONG POINTER TO BOOL] = TRUSTED {

ENABLE UNWIND => NULL;

UNTIL lp^ DO WAIT alarmClock; ENDLOOP;

};

Awake: ENTRY PROC [lp: LONG POINTER TO BOOL] = TRUSTED {

ENABLE UNWIND => NULL;

lp^ ← TRUE;

BROADCAST alarmClock;

};

ClarkKent: PROC = TRUSTED {

Superman: ENTRY PROC RETURNS [ok: BOOL ← TRUE] = TRUSTED {

ENABLE UNWIND => NULL;

IF reportInterval = 0

THEN {ok ← FALSE; reportProcess ← NIL}

ELSE WAIT reportTime;

};

last: ROPE ← NIL;

lastTime: System.Microseconds ← System.PulsesToMicroseconds[System.GetClockPulses[]];

lastCount: INT ← fileCount ← 0;

WHILE Superman[] DO

IF last # report THEN {

thisTime: System.Microseconds ← System.PulsesToMicroseconds[System.GetClockPulses[]];

currentFiles: INT ← fileCount;

deltaFiles: INT ← currentFiles - lastCount;

deltaMicros: System.Microseconds ← thisTime - lastTime;

MessageWindow.Append[last ← report, TRUE];

IF deltaMicros > 1000 THEN {

invSecs: REAL ← 1E6/deltaMicros;

filesPerSec: REAL ← deltaFiles * invSecs;

MessageWindow.Append[" (files: ", FALSE];

MessageWindow.Append[Convert.ValueToRope[[signed[currentFiles]]], FALSE];

MessageWindow.Append[", rate: ", FALSE];

MessageWindow.Append[Convert.ValueToRope[[real[filesPerSec, 2]]], FALSE];

MessageWindow.Append[")", FALSE];

lastTime ← thisTime;

lastCount ← currentFiles;

};

ENDLOOP;

MessageWindow.Append[report ← NIL, TRUE];

};

BytesForEntries: PROC [n: INT] RETURNS [INT] = {

words: INT ← SIZE[MapEntry]*n + SIZE[MapRep[0]] - SIZE[ROPE];

RETURN [words+words]};

EntrySortPred: PriorityQueue.SortPred = {

[x: Item, y: Item, data: REF ← NIL] RETURNS [BOOL]

xx: EntryRef ← NARROW[x];

yy: EntryRef ← NARROW[y];

IF xx.version.num # yy.version.num THEN RETURN [xx.version.num < yy.version.num];

IF xx.version.hi # yy.version.hi THEN RETURN [xx.version.hi < yy.version.hi];

RETURN [xx.version.lo < yy.version.lo];

};

VersionPred: PROC [version1,version2: VersionMap.MyStamp] RETURNS [BOOL] = {

IF version1.num # version2.num THEN RETURN [version1.num < version2.num];

IF version1.hi # version2.hi THEN RETURN [version1.hi < version2.hi];

RETURN [version1.lo < version2.lo];

};

NewEntryRef: PROC [name: ROPE] RETURNS [EntryRef] = {

report ← name;

fileCount ← fileCount + 1;

RETURN [qz.NEW[EntryRep ← [next: NIL, name: name, version: NullStamp]]]};

GenerateEntryListFromMap: PROC

[map: Map] RETURNS [head: EntryRef, prefix: ROPE, count: NAT] = {

GenerateEntryListFromMap[map] generates a SORTED entry list.

count ← VersionMap.Length[map];

prefix ← NIL;

head ← NIL;

IF count > 0 THEN {

stamp: TimeStamp.Stamp;

ent, tail: EntryRef;

[stamp, name] ← map.Fetch[0];

head ← tail ← NewEntryRef[name];

tail.version ← LOOPHOLE[stamp];

FOR i: NAT IN [1..count) DO

[stamp, name] ← map.Fetch[i];

ent ← NewEntryRef[name];

ent.version ← LOOPHOLE[stamp];

tail.next ← ent;

tail ← ent;

ENDLOOP;

};

EntryListSize: PROC [elist: EntryRef] RETURNS [count: INT ← 0] = {

FOR list: EntryRef ← elist, list.next UNTIL list = NIL DO

count ← count + 1;

ENDLOOP;

};

CopyEntryList: PROC [elist: EntryRef] RETURNS [copy: EntryRef ← NIL] = {

tail: EntryRef ← NIL;

FOR list: EntryRef ← elist, list.next UNTIL list = NIL DO

new: EntryRef ← NewEntryRef[list.name];

new.version ← list.version;

IF tail = NIL

THEN copy ← new

ELSE tail.next ← new;

tail ← new;

ENDLOOP;

};

MergeEntryLists: PROC

[elist1,elist2: EntryRef, prefix1,prefix2: ROPE ← NIL]

RETURNS [head: EntryRef ← NIL, prefix: ROPE ← NIL, count: NAT] = {

MergeEntryLists[elist1,elist2] performs a destructive merge on elist1 and elist2, which must both be initially sorted. No elements are discarded and no checking for duplicate versions is performed.

count1: INT ← EntryListSize[elist1];

count2: INT ← EntryListSize[elist2];

tail, rem: EntryRef ← NIL;

count ← count1 + count2;

WHILE elist1 # NIL AND elist2 # NIL DO

better: EntryRef ← NIL;

IF VersionPred[elist1.version, elist2.version]

THEN {

elist1 has the better entry

better ← elist1;

elist1 ← elist1.next;

}

ELSE {

elist2 has the better entry

better ← elist2;

elist2 ← elist2.next;

};

IF tail = NIL THEN head ← better ELSE tail.next ← better;

tail ← better;

ENDLOOP;

assert elist1 = NIL OR elist2 = NIL

IF prefix1 # NIL AND (count1 > count2 OR prefix2 = NIL)

THEN prefix ← prefix1

ELSE prefix ← prefix2;

IF elist1 = NIL THEN rem ← elist1 ELSE rem ← elist2;

IF tail = NIL THEN head ← rem ELSE tail.next ← rem;

};

CountExplicitPrefixes: PROC [map: VersionMap.Map] RETURNS [count: INT ← 0] = {

IF map # NIL THEN {

names: ROPE ← map.names;

FOR i: NAT IN [0..map.len) DO

entry: VersionMap.MapEntry ← map[i];

c: CHAR ← names.Fetch[entry.index];

SELECT c FROM

'/, '[ => count ← count + 1;

ENDCASE;

ENDLOOP;

};

GenerateEntryListFromRemote: PROC

[host,match: ROPE ← NIL, oldMap: Map ← NIL, filter: FilterProc ← NIL]

RETURNS [head: EntryRef ← NIL, prefix: ROPE ← NIL, count: NAT ← 0] = TRUSTED {

declarations of local variables

stringMatch: STRING ← [80];

stp: UnsafeSTP.Handle ← NIL;

tab: SymTab.Ref ← NIL;

prefixLen: INT ← 0; -- length of common prefix, including server

skipLen: INT ← 0; -- length of common prefix, excluding server

bracketedHost: ROPE ← Rope.Cat["[", host, "]"];

tail: EntryRef ← NIL;

EachFile: UnsafeSTP.NoteFileProcType = TRUSTED {

PROC [file: STRING] RETURNS [continue: Continue]

rname: ROPE ← ConvertUnsafe.ToRope[file];

new: EntryRef ← NIL;

usePrefix: BOOL ← Rope.Run[rname, 0, match, 0, FALSE] = skipLen;

continue ← yes;

IF filter # NIL AND NOT filter[rname] THEN RETURN; -- user does not want this one

IF usePrefix AND prefix # NIL

THEN rname ← rname.Substr[skipLen]

ELSE rname ← bracketedHost.Concat[rname];

IF LookupName[tab, rname] THEN RETURN; -- already seen

new ← NewEntryRef[rname];

IF tail = NIL THEN head ← new ELSE tail.next ← new;

tail ← new;

count ← count + 1;

SELECT TRUE FROM

Rope.Match["*.bcd!*", rname, FALSE], Rope.Match["*.symbols!*", rname, FALSE] => {

-- we will get the date later by accessing the first page of the bcd

};

ENDCASE => {

get the time from the create date only

info: UnsafeSTP.FileInfo ← UnsafeSTP.GetFileInfo[stp];

IF info # NIL AND info.create # NIL THEN {

s: LONG STRING ← info.create;

len: NAT ← s.length;

get: PROC [i: INT] RETURNS [CHAR] = TRUSTED {

IF i IN [0..len) THEN RETURN [s[i]];

RETURN [0C]};

value: Convert.Value ←

Convert.Parse

[[get[get]],

[time[Time.defaultTime]],

0, len].value;

WITH v: value SELECT FROM

time =>

new.version ← LOOPHOLE[TimeStamp.Stamp[0, 0, v.time], MyStamp]

ENDCASE;

};

[head, prefix, count] ← GenerateEntryListFromMap[oldMap];

tab ← GenSymTabFromVersionMap[oldMap];

skipLen ← match.Index[0, "*"];

IF oldMap = NIL THEN {

prefix ← Rope.Cat[bracketedHost, match.Substr[0, skipLen]];

prefixLen ← prefix.Size[];

};

ConvertUnsafe.AppendRope[stringMatch, match];

login using our default credentials

stp ← STPInit[host];

build the name list

UnsafeSTP.Enumerate[stp, stringMatch, EachFile];

clean up the STP connection

UnsafeSTP.Close[stp ! ANY => CONTINUE];

};

GenSymTabFromVersionMap: PROC [map: Map] RETURNS [tab: SymTab.Ref ← NIL] = {

tab ← SymTab.Create[MAX[53, (count+5)/2], FALSE];

IF count > 0 THEN {

FOR i: NAT IN [0..count) DO

StoreName[tab, VersionMap.FetchName[map, i]];

ENDLOOP;

};

StoreName: PROC [tab: SymTab.Ref, name: ROPE] = {

[] ← SymTab.Insert[tab, name, name];

};

LookupName: PROC [tab: SymTab.Ref, name: ROPE] RETURNS [BOOL] = {

x: REF ← SymTab.Fetch[tab, name].val;

RETURN [x # NIL];

};

GetNextFromList: ENTRY PROC [gen: GenerateData] RETURNS [ent: EntryRef] = {

IF gen.list # NIL AND gen.errors = 0 THEN {

ent ← gen.list;

gen.list ← ent.next;

RETURN};

gen.countGoing ← gen.countGoing - 1;

BROADCAST gen.done;

};

WaitForGenDone: ENTRY PROC [gen: GenerateData] = {

UNTIL gen.countGoing = 0 DO WAIT gen.done; ENDLOOP;

};

GenerateMapFromEntryList: PROC

[head: EntryRef, prefix: ROPE, count: NAT] RETURNS [map: Map] = TRUSTED {

prefixLen: INT ← prefix.Size[];

skipPos: INT ← prefix.Index[0, "]"] + 1;

skipLen: INT ← prefixLen - skipPos;

host: ROPE ← IF prefixLen = 0 THEN NIL ELSE prefix.Flatten[1, skipPos-2];

directory: ROPE ← IF skipPos >= prefixLen THEN NIL ELSE prefix.Substr[skipPos];

list: EntryRef ← head;

offset: INT ← 0;

pq: PriorityQueue.Ref ← PriorityQueue.Predict[count, EntrySortPred];

gen: GenerateData ← pz.NEW[GenerateDataRep];

gen.host ← host;

gen.directory ← directory;

gen.list ← head;

gen.pq ← pq;

gen.countGoing ← outstandingRequests;

its leaf time, folks!

IFSFile.Initialize[];

FOR i: NAT IN [0..outstandingRequests) DO

Process.Detach[FORK VersionFromName[prefix, gen]];

ENDLOOP;

map ← pz.NEW[MapRep[count]];

wait for the dust to settle (otherwise there is TROUBLE!)

WaitForGenDone[gen];

close up the leafy world

FlushServerCache[];

IFSFile.Finalize[! ANY => CONTINUE];

IF gen.errors # 0 THEN RETURN [NIL];

calculate the entries in the map

map.prefix ← offset ← 0; -- offset of prefix start

offset ← prefixLen + 1; -- byte offset of first name

head ← list ← NIL;

FOR i: NAT IN [0..count) DO

each: EntryRef ← NARROW[pq.Remove[]];

each.next ← NIL;

map[i] ← [each.version, offset];

IF head = NIL

THEN head ← each

ELSE list.next ← each;

list ← each;

offset ← offset + each.name.Size[] + 1;

ENDLOOP;

{-- make up the names string

EachChar: PROC RETURNS [c: CHAR] = TRUSTED {

IF thisIndex = thisLen THEN {

we need the next name

c ← '\n;

IF list = NIL THEN RETURN;

thisRope ← list.name;

thisIndex ← 0;

thisLen ← thisRope.Size[];

list ← list.next;

RETURN

};

c ← thisRope.Fetch[thisIndex];

thisIndex ← thisIndex + 1;

};

thisRope: ROPE ← prefix;

thisIndex: INT ← 0;

thisLen: INT ← prefixLen;

list ← head;

map.names ← Rope.FromProc[offset, EachChar, maxPiece]};

};

STPInit: PROC [server: ROPE] RETURNS [stp: UnsafeSTP.Handle] = TRUSTED {

nameRope,passRope: ROPE ← NIL;

nameString: STRING ← [80];

passString: STRING ← [80];

hostString: STRING ← [40];

herald: LONG STRING ← NIL;

props: UnsafeSTP.DesiredProperties ← ALL[FALSE];

stp ← UnsafeSTP.Create[];

[nameRope,passRope] ← UserCredentials.GetUserCredentials[];

ConvertUnsafe.AppendRope[nameString, nameRope];

ConvertUnsafe.AppendRope[passString, passRope];

ConvertUnsafe.AppendRope[hostString, server];

UnsafeSTP.Login[stp, nameString, passString];

herald ← UnsafeSTP.Open[stp, hostString];

Heap.systemZone.FREE[@herald];

props[directory] ← TRUE;

props[nameBody] ← TRUE;

props[version] ← TRUE;

props[createDate] ← TRUE;

UnsafeSTP.SetDesiredProperties[stp, props];

};

IFSInit: ENTRY PROC [server: ROPE] RETURNS [ifs: IFSFile.FSInstance] = TRUSTED {

ENABLE UNWIND => NULL;

nameRope,passRope: ROPE ← NIL;

nameString: STRING ← [80];

passString: STRING ← [80];

serverString: STRING ← [80];

FOR list: OpenServerList ← serverCache, list.rest UNTIL list = NIL DO

IF Rope.Equal[list.first.name, server, FALSE] THEN {

list.first.count ← list.first.count + 1;

RETURN [list.first.ifs]};

ENDLOOP;

[nameRope,passRope] ← UserCredentials.GetUserCredentials[];

ConvertUnsafe.AppendRope[serverString, server];

ConvertUnsafe.AppendRope[nameString, nameRope];

ConvertUnsafe.AppendRope[passString, passRope];

ifs ← IFSFile.Login

[serverString, nameString, passString, nameString, passString];

serverCache ← CONS[[server, ifs, 1], serverCache];

};

IFSFinis: ENTRY PROC [ifs: IFSFile.FSInstance] = TRUSTED {

ENABLE UNWIND => NULL;

FOR list: OpenServerList ← serverCache, list.rest UNTIL list = NIL DO

IF ifs = list.first.ifs THEN

list.first.count ← list.first.count - 1;

ENDLOOP;

};

FlushServerCache: PROC = TRUSTED {

lag: OpenServerList ← NIL;

FOR list: OpenServerList ← serverCache, list.rest UNTIL list = NIL DO

IF list.first.count <= 0 THEN {

IFSFile.Logout[list.first.ifs ! ANY => CONTINUE];

IF lag = NIL

THEN serverCache ← list.rest

ELSE lag.rest ← list.rest};

ENDLOOP;

};

OpenServerList: TYPE = LIST OF OpenServerRecord;

OpenServerRecord: TYPE = RECORD

[name: ROPE, ifs: IFSFile.FSInstance, count: INTEGER];

serverCache: OpenServerList ← NIL;

WhenCompleted: IFSFile.Completer = TRUSTED {

[arg: CompleterArg, outcome: Problem]

called on completion of Leaf transfer

IF outcome # ok THEN ERROR VersionNotAvailable;

Awake[LOOPHOLE[arg, LONG POINTER TO BOOL]];

};

VersionFromName: PROC

[prefix: ROPE, gen: GenerateData] = TRUSTED {

this proc is the base of a process that fills in version stamps for an entry

names in the entries will have the prefix (if any) removed

ent: EntryRef ← NIL;

WHILE (ent ← GetNextFromList[gen]) # NIL DO

ENABLE ABORTED => {gen.errors ← gen.errors + 1; EXIT};

len: INT ← prefix.Size[];

IF len > 0 AND Rope.Run[prefix, 0, ent.name, 0, FALSE] = len THEN {

-- now we can strip off the prefix!

ent.name ← Rope.Substr[ent.name, len];

};

IF ent.version = NullStamp THEN {

-- must fill in the version

FillInBcdVersion[gen, ent]};

PQInsert[gen.pq, ent];

ENDLOOP;

};

FillInBcdVersion: PROC

[gen: GenerateData, ent: EntryRef] = TRUSTED {

bcd: BcdDefs.BCD;

ifs: IFSFile.FSInstance ← NIL;

fh: IFSFile.FileHandle ← NIL;

string: STRING ← [132];

ready: BOOL ← FALSE;

lp: LONG POINTER TO BOOL ← @ready;

fname: ROPE ← ent.name;

fnSize: INT ← fname.Size[];

rbPos: INT ← fname.Index[0, "]"];

host: ROPE ← gen.host;

{ENABLE UNWIND => {

IF fh # NIL THEN IFSFile.Close[fh];

IF ifs # NIL THEN IFSFinis[ifs]};

IF rbPos < fnSize THEN {

host ← fname.Substr[1, rbPos-1];

fname ← fname.Substr[rbPos+1]};

ifs ← IFSInit[host];

ConvertUnsafe.AppendRope[string, gen.directory];

ConvertUnsafe.AppendRope[string, fname];

fh ← IFSFile.Open[ifs, string ! ABORTED => GO TO abort; ANY => GO TO none];

IFSFile.StartRead [

fh, 0, Environment.bytesPerWord*SIZE[BcdDefs.BCD], @bcd,

WhenCompleted, LOOPHOLE[lp, LONG UNSPECIFIED]];

report ← fname;

fileCount ← fileCount + 1;

Snooze[lp];

IFSFile.Close[fh ! ABORTED => GO TO abort; ANY => CONTINUE];

IFSFinis[ifs]};

ent.version ← LOOPHOLE[bcd.version, MyStamp];

EXITS

none => {};

abort => ERROR ABORTED;

};

RopeFromFileData: TYPE = RECORD

[st: IO.STREAM, size: INT, offset: INT ← 0];

RopeFromFile: PROC [st: IO.STREAM, size: INT, offset: INT ← 0] RETURNS [ROPE] = {

data: REF ← qz.NEW[RopeFromFileData ← [st, size, offset]];

RETURN [Rope.MakeRope[data, size, FetchFromFile]];

};

FetchFromFile: ENTRY Rope.FetchType = {

unfortunately this must be an entry proc to avoid races

ENABLE UNWIND => NULL;

mine: REF RopeFromFileData ← NARROW[data];

IO.SetIndex[mine.st, index+mine.offset];

RETURN [IO.GetChar[mine.st]];

};

PQInsert: ENTRY PROC [pq: PriorityQueue.Ref, entry: EntryRef] = {

monitorized to prevent scrambling the priority queue

pq.Insert[entry];

};

MyPut: PROC [st: IO.STREAM, r: ROPE] = {

FOR i: INT IN [0..r.Size[]) DO

IO.PutChar[st, r.Fetch[i]];

ENDLOOP;

};

END.