<<>> <> <> <> <> <> <> <> <> <> <<>> DIRECTORY Atom, Basics USING [CompareCard, Comparison, LongNumber, RawBytes, UnsafeBlock], BasicTime USING [GMT, nullGMT, Period], Commander USING [CommandProc, Register], CommanderOps USING [NextArgument], FileNames USING [ConvertToSlashFormat, StripVersionNumber], FS, IO, PFS, PFSNames, PriorityQueue, Process, Rope, SymTab, UserProfile USING [Boolean, CallWhenProfileChanges, ListOfTokens, ProfileChangedProc], VersionMap USING [Map, MapAndName, MapAndNameList, MapEntry, MapList, MapRep, MyStamp, nullStamp, Range, RangeList, ShortNameSeq, ShortNameSeqRep, VersionStamp], VersionMapExtended, VersionMapBackdoor USING [], VersionMapBuilding, VersionMapDefaults USING [], VersionMapPrivate, VersionMapUtils USING [SourceFileEntry, SourceFileList]; VersionMapImpl: CEDAR MONITOR IMPORTS Atom, Basics, BasicTime, Commander, CommanderOps, FileNames, FS, IO, PFS, PFSNames, PriorityQueue, Process, Rope, SymTab, UserProfile EXPORTS VersionMap, VersionMapBackdoor, VersionMapBuilding, VersionMapDefaults, VersionMapExtended, VersionMapUtils <> = BEGIN OPEN BasicTime, VersionMap, VersionMapBuilding; ShortKey: INT = 19850206; LongKey: INT = 19900710; <> <<>> Comparison: TYPE = Basics.Comparison; ROPE: TYPE = Rope.ROPE; NullStamp: MyStamp Ź [0, 0, 0, 0]; MyStampAsHex: TYPE = PACKED ARRAY [0..hexDigitsInStamp) OF HexDigit; HexDigit: TYPE = [0..16); hexDigitsInStamp: NAT = BITS[MyStamp] / BITS[HexDigit]; EntryIndex: TYPE = CARDINAL; NullEntryIndex: EntryIndex = LAST[CARDINAL]; EntryRef: TYPE = REF EntryRep; EntryRep: TYPE = RECORD [next: EntryRef, name: ROPE, version: MyStamp]; WhichMapList: TYPE = ATOM; <<$Source => the source symbol version map list (initially from CedarSource.VersionMap)>> <<$Intermediate => the intermediate version map list (initially from CedarIntermediate.VersionMap)>> <<$Executable => the executables version map list (initially from CedarSparcExecutable.VersionMap & CedarSparcOptExecutable.VersionMap)>> < a user-defined version map variety (initially empty)>> MapUnderConstruction: TYPE ~ REF MapUnderConstructionPrivate; MapUnderConstructionPrivate: PUBLIC TYPE ~ VersionMapPrivate.MapUnderConstructionPrivate; FileEntry: TYPE = REF FileEntryRep; FileEntryRep: TYPE = RECORD [ name: ROPE, created: BasicTime.GMT, myStamp: MyStamp, from: ROPE]; NameSeq: TYPE = REF NameSeqRep; NameSeqRep: TYPE = RECORD [ SEQUENCE len: NAT OF NameEntry]; NameEntry: TYPE = RECORD [hasPrefix: BOOL, name: ROPE]; SourceFileList: TYPE = VersionMapUtils.SourceFileList; SourceFileEntry: TYPE = VersionMapUtils.SourceFileEntry; DMapEntry: TYPE = PACKED ARRAY [0..7) OF CARD16; <> BytesInWord: TYPE ~ PACKED ARRAY [0 .. 3] OF BYTE; bwTest: BytesInWord ~ [1, 2, 3, 4]; memoryLayoutLikeFileLayout: BOOL[TRUE..TRUE] ~ LOOPHOLE[bwTest, CARD32] = ((1*256+2)*256 + 3)*256 + 4; <
>
<>
    assumeImmutableGlobal: BOOL Ź TRUE;

    root: EntryList Ź NIL;
        EntryList: TYPE = LIST OF Entry;
        Entry: TYPE = RECORD [key: ATOM Ź NIL, mapList: MapList Ź NIL];

    versionMapDir: ROPE ~ "/Cedar/CedarVersionMap/"; -- SystemNames.CedarDir won't work
    versionMapDirPath: PFS.PATH ~ PFS.PathFromRope[versionMapDir];
    defaultSourceNameList: LIST OF ROPE Ź LIST["CedarSource.VersionMap"];
    defaultIntermediateNameList: LIST OF ROPE Ź LIST["CedarIntermediate.VersionMap"];
    defaultExecutableNameList: LIST OF ROPE Ź LIST["CedarSparcExecutable.VersionMap", "CedarSparcOptExecutable.VersionMap"];
    defaultSymbolsNameList: LIST OF ROPE Ź LIST["CedarIntermediate.VersionMap"];

    stats: REF Stats = NEW[Stats Ź []];
    Stats: TYPE = RECORD [
        remoteTries: INT Ź 0,
        localTries: INT Ź 0,
        localWins: INT Ź 0
        ];
<>
    VersionToName: PUBLIC PROC [list: MapList, stamp: VersionStamp]
    RETURNS [result: MapAndName] = {
        <<... returns a full path name (FS format) for the given version stamp.  The list of maps is searched in order.  For convenience on 
        a match, the containing map is also returned.  If the stamp is not found, [NIL, NIL] is returned.>>
        result Ź [NIL, NIL, nullGMT];
        FOR each: MapList Ź list, each.rest WHILE each # NIL DO
            map: Map Ź each.first;
            nx: EntryIndex Ź FindIndex[map, stamp];
            IF nx # NullEntryIndex THEN {
                entry: MapEntry Ź map[nx];
                result.name Ź IndexToFullName[map, entry.index];
                result.map Ź map;
                result.created Ź entry.created;
                RETURN};
            ENDLOOP;
        };

    VersionToAllNames: PUBLIC PROC [list: MapList, stamp: VersionStamp]
    RETURNS [result: MapAndNameList] = {
        <<... returns all of the full path names (FS format) for the given version stamp.  The list of maps is searched in order.  For 
        convenience on a match, the containing map is also returned.  If the stamp is not found, [NIL, NIL] is returned.>>
        tail: MapAndNameList Ź NIL;
        result Ź NIL;
        FOR each: MapList Ź list, each.rest WHILE each # NIL DO
            map: Map Ź each.first;
            lo,hi: EntryIndex;
            [lo,hi] Ź FindIndexRange[map, stamp];
            FOR x: EntryIndex IN [lo..hi] DO
                entry: MapEntry Ź map[x];
                name: ROPE Ź  IndexToFullName[map, entry.index];
                new: MapAndNameList Ź LIST[[map, name, entry.created]];
                IF tail = NIL THEN result Ź new ELSE tail.rest Ź new;
                tail Ź new;
                ENDLOOP;
            ENDLOOP;
        };

    ShortName: PUBLIC PROC [longName: ROPE] RETURNS [ROPE] = {
        <<... returns the short name for the given long name.  This simply involves stripping off the directory and version information.>>
        lim: INT Ź Rope.Length[longName];
        pos: INT Ź lim;
        WHILE pos > 0 DO
            c: CHAR Ź Rope.Fetch[longName, pos Ź pos - 1];
            SELECT c FROM
                '! => lim Ź pos;
                '], '>, '/ => {pos Ź pos + 1; EXIT};
                ENDCASE;
            ENDLOOP;
        RETURN [Rope.Flatten[longName, pos, lim-pos]];
        };

    ShortNameToNames: PUBLIC PROC [list: MapList, shortName: ROPE]
    RETURNS [MapAndNameList] = {
        <<... returns all of the full path names (FS format) for the given short name.  The list of maps is searched in order.  For 
        convenience on a match, the containing map is also returned.  If the stamp is not found, [NIL, NIL] is returned.>>
        rangeList: RangeList Ź ShortNameToRanges[list, shortName Ź ShortName[shortName]];
        head,tail: MapAndNameList Ź NIL;
        WHILE rangeList # NIL DO
            range: Range Ź rangeList.first;
            map: Map Ź range.map;
            rangeList Ź rangeList.rest;
            FOR index: CARDINAL IN [range.first..range.first+range.len) DO
                mx: CARDINAL Ź map.shortNameSeq[index];
                entry: MapEntry Ź map[mx];
                name: ROPE Ź IndexToFullName[map, entry.index];
                new: MapAndNameList Ź LIST[[map, name, entry.created]];
                IF tail = NIL THEN head Ź new ELSE tail.rest Ź new;
                tail Ź new;
                ENDLOOP;
            ENDLOOP;
        RETURN [head];
        };

    ShortNameToRanges: PUBLIC PROC [list: MapList, shortName: ROPE]
    RETURNS [RangeList] = {
        <<... returns all of the ranges that correspond to the given short name (see the comments for Range).>>
        head,tail: RangeList Ź NIL;
        shortName Ź ShortName[shortName];
        WHILE list # NIL DO
            map: Map Ź list.first;
            shorts: ShortNameSeq Ź map.shortNameSeq;
            list Ź list.rest;
            IF map # NIL THEN {
                found: BOOL;
                index: CARDINAL;
                range: Range Ź [map: map, first: 0, len: 0];
                new: RangeList;
                [index, found] Ź ShortNameFind[map, shortName];
                IF found
                    THEN {
                        <>
                        x,y: CARDINAL Ź index;
                        WHILE x > 0 DO
                            IF ShortNameFindPred[shortName, shorts[x-1], map] # equal THEN EXIT;
                            x Ź x - 1;
                            ENDLOOP;
                        WHILE y+1 < map.len DO
                            IF ShortNameFindPred[shortName, shorts[y+1], map] # equal THEN EXIT;
                            y Ź y + 1;
                            ENDLOOP;
                        range.first Ź x;
                        range.len Ź y+1 - x;
                        }
                    ELSE {
                        <>
                        range.first Ź index;
                        WHILE range.first < map.len DO
                            SELECT ShortNameFindPred[shortName, shorts[range.first], map] FROM
                                less => EXIT;
                                equal => ERROR;  -- the shortNameSeq was not properly sorted!
                                greater => range.first Ź range.first + 1;
                                ENDCASE;
                            ENDLOOP;
                        };
                new Ź LIST [range];
                IF tail = NIL THEN head Ź new ELSE tail.rest Ź new;
                tail Ź new;
                };
            ENDLOOP;
        RETURN [head];
        };

    GetPrefix: PUBLIC PROC [map: Map] RETURNS [ROPE] = {
        <>
        RETURN [IndexToShortName[map, 0]];
        };

    StampToHex: PUBLIC PROC [stamp: VersionStamp] RETURNS [ROPE] = {
        <>
        RETURN [MyStampToHex[VsToMs[stamp]]];
        };

    SaveMapToFile: PUBLIC PROC [map: Map, name: PFS.PATH]
        = {GeneralSaveMapToFile[map, name, FALSE]};

    GeneralSaveMapToFile: PUBLIC PROC [map: Map, name: PFS.PATH, long: BOOL]
        = {LimitedSave[[map, Length[map]], name, long]};

    LimitedSave: PUBLIC PROC [lm: LimitedMap, name: PFS.PATH, long: BOOL] = TRUSTED {
        map: Map ~ lm.map;
        st: IO.STREAM Ź PFS.StreamOpen[name, $create];
        names: ROPE Ź map.names;
        namesChars: INT Ź names.Size[];
        len: NAT Ź lm.limit;
        myVersion: INT Ź ShortKey;

        IF NOT memoryLayoutLikeFileLayout THEN ERROR;

        <>
        st.PutF["%g %g %g\r", [integer[IF long THEN LongKey ELSE ShortKey]], [integer[len]], [integer[namesChars]] ];
        <<>>
        <>
            <<[LOOPHOLE[LONG[@myVersion]], 0, BYTES[INT]]];>>
            <>

        <>
        <>
        <>
            <<[LOOPHOLE[LONG[@len]], 0, BYTES[NAT]]];>>
            <>
        <>
            <<[LOOPHOLE[@map.entries[0]], 0, len*(BYTES[MapEntry])]];>>
            <>
        IF long 
            THEN IO.UnsafePutBlock[st, [LOOPHOLE[@map.entries[0]], 0, len*(BYTES[MapEntry])]]
            ELSE FOR i: INT IN [0..len) DO
                dMapEntry: DMapEntry;
                dMapEntry[0] Ź map.entries[i].stamp.lo;
                dMapEntry[1] Ź map.entries[i].stamp.num;
                dMapEntry[2] Ź map.entries[i].stamp.hi;
                dMapEntry[3] Ź LOOPHOLE[map.entries[i].created, Basics.LongNumber].lo;
                dMapEntry[4] Ź LOOPHOLE[map.entries[i].created, Basics.LongNumber].hi;
                dMapEntry[5] Ź LOOPHOLE[map.entries[i].index, Basics.LongNumber].lo;
                dMapEntry[6] Ź LOOPHOLE[map.entries[i].index, Basics.LongNumber].hi;
                IO.UnsafePutBlock[st, [LOOPHOLE[@dMapEntry], 0, BYTES[DMapEntry]] ];
                ENDLOOP;

        <>
            <<[LOOPHOLE[@map.shortNameSeq[0]], 0, len*(BYTES[CARD16])]];>>
            <>
        IF long
            THEN IO.UnsafePutBlock[st, [LOOPHOLE[@map.shortNameSeq[0]], 0, len*(BYTES[CARD32])]]
            ELSE FOR i: INT IN [0..len) DO
                foo: Basics.LongNumber ~ [card[map.shortNameSeq[i]]];
                st.PutChar[VAL[foo.lh]];
                st.PutChar[VAL[foo.ll]];
                ENDLOOP;
        <>
            <<[LOOPHOLE[LONG[@namesChars]], 0, (BYTES[INT])]];>>
            <>
        IO.PutRope[st, names];
            <>
        IO.PutRope[st, "\000\000\000"];
            <>
        IO.SetLength[st, IO.GetIndex[st]]; -- force goddamm truncation already!!!
        IO.Close[st];
        };

    RestoreMapFromFile: PUBLIC PROC [name: PFS.PATH, askedForUID: PFS.UniqueID, assumeImmutable: BOOL Ź TRUE]
        RETURNS [map: Map Ź NIL] =
        { RETURN[VerboseRestoreMapFromFile[name, askedForUID, assumeImmutable, NIL]] };

    VerboseRestoreMapFromFile: PUBLIC PROC
    [name: PFS.PATH, askedForUID: PFS.UniqueID, assumeImmutable: BOOL, out: IO.STREAM]
        RETURNS [map: Map Ź NIL] = {
        <>
        <>
        <<(this avoids copying the file names from the save file) >>
        long: BOOL;
        namesChars: INT Ź 0;
        bytes: INT Ź 0;
        len: NAT15 Ź 0;
        pos: INT Ź 0;
        st: IO.STREAM Ź NIL;
        dMapEntry: DMapEntry;
        contents: ROPE Ź NIL;
        fullName: PFS.PATH Ź NIL;
        actualUID: PFS.UniqueID Ź PFS.nullUniqueID;
        Try: PROC [name: PFS.PATH, try: NAT] = {
            ENABLE PFS.Error => {
                IF out # NIL THEN out.PutF["\t**%g - %g\n", [integer[try]], [rope[error.explanation]] ];
                IF try < 3 THEN CONTINUE
                };
            [rope: contents, fullFName: fullName, uniqueID: actualUID] Ź PFS.RopeOpen[fileName: name, wantedUniqueID: askedForUID, 
            includeFormatting: TRUE, checkMutability: FALSE];
            };

        stats.remoteTries Ź stats.remoteTries + 1;
        IF NOT memoryLayoutLikeFileLayout THEN ERROR;
        IF out = NIL THEN out _ vMapDebuggingStrm;

        IF out # NIL THEN out.PutF1["Opening %g using PFS\n", [rope[PFS.RopeFromPath[name]]] ];
        Try[name, 1]; -- try local first - this is the previous behavior and is used for merging version maps (needed for those other than 
        the Cedar version maps itself)
        IF fullName = NIL THEN Try[PFSNames.ExpandName[name, versionMapDirPath], 2];
        IF fullName = NIL THEN {
            <>
            stats.localTries Ź stats.localTries + 1;
            askedForUID Ź PFS.nullUniqueID;
            Try[PFSNames.ExpandName[name, versionMapDirPath], 3];
            stats.localWins Ź stats.localWins + 1;
            };
        <>
            map Ź CheckFileCache[fullName, actualUID];
            IF map # NIL THEN {
                IF out # NIL THEN out.PutRope["\t **4 - file found in cache\n"];
                RETURN
                };

        st Ź IO.RIS[contents];

        {
            ENABLE IO.EndOfStream, IO.Error => {
                map Ź NIL;
                IF out # NIL THEN out.PutF1["IO Error or EndOfStream at pos %g\n", [integer[st.GetIndex[]]] ] ;
                GO TO noGot
                };
            val: INT;
            val Ź IO.GetInt[st ! IO.Error => GO TO noGot];

            IF (val # ShortKey) AND (val # LongKey) THEN { IF out # NIL THEN out.PutF1[" Bad version %g\n", [integer[val]] ]; GO TO noGot};
                <>
            long Ź val = LongKey;
            IF out # NIL THEN out.PutF["\nOpened %g (%g format)\n", [rope[PFS.RopeFromPath[name]]], [rope[IF long THEN "long" ELSE "short"]] ];
            len Ź IO.GetInt[st ! IO.Error => GO TO noGot];
            namesChars Ź IO.GetInt[st ! IO.Error => GO TO noGot];
            [] Ź st.GetChar[];    -- trailing \n
            IF out # NIL THEN {
                out.PutF["len: %g, nameChars: %g\n", [integer[len]], [integer[namesChars]] ];
                out.Flush[];
                }; 
            map Ź NEW[MapRep[len]];
            map.fileName Ź fullName;
            map.uid Ź actualUID;
            map.askedForUID Ź askedForUID;
            map.assumeImmutable Ź assumeImmutable;
            map.shortNameSeq Ź NEW[ShortNameSeqRep[len]];

            TRUSTED {
                IF long
                    THEN [] Ź IO.UnsafeGetBlock[st, [LOOPHOLE[@map.entries[0]], 0, len*(BYTES[MapEntry])]]
                    ELSE FOR i: INT IN [0..len) DO
                        [] Ź IO.UnsafeGetBlock[st,
                        [LOOPHOLE[@dMapEntry], 0, BYTES[DMapEntry] ] ];
                        map.entries[i].stamp.lo Ź dMapEntry[0];
                        map.entries[i].stamp.num Ź dMapEntry[1];
                        map.entries[i].stamp.hi Ź dMapEntry[2];
                        map.entries[i].stamp.extra Ź 0;
                        LOOPHOLE[map.entries[i].created, Basics.LongNumber].lo Ź LOOPHOLE[dMapEntry[3]];
                        LOOPHOLE[map.entries[i].created, Basics.LongNumber].hi Ź LOOPHOLE[dMapEntry[4]];
                        LOOPHOLE[map.entries[i].index, Basics.LongNumber].lo Ź LOOPHOLE[dMapEntry[5]];
                        LOOPHOLE[map.entries[i].index, Basics.LongNumber].hi Ź LOOPHOLE[dMapEntry[6]];
                        ENDLOOP;
                    <>
                IF long
                    THEN [] Ź IO.UnsafeGetBlock[st, [LOOPHOLE[@map.shortNameSeq[0]], 0, len*(BYTES[CARD32])]]
                    ELSE FOR i: INT IN [0..len) DO
                        foo: Basics.LongNumber Ź LOOPHOLE[0];
                        foo.lh Ź LOOPHOLE[st.GetChar[]];
                        foo.ll Ź LOOPHOLE[st.GetChar[]];
                        map.shortNameSeq[i] Ź LOOPHOLE[foo];
                        ENDLOOP;
                    <>
                };

            pos Ź IO.GetIndex[st];
            IF out # NIL THEN out.PutF1["current index: %g\n", [integer[pos]] ];
            IF assumeImmutable
                THEN {
                    <>
                    <>
                    map.names Ź Rope.Substr[contents, pos, namesChars];
                    }
                ELSE {
                    eachChar: PROC RETURNS [c: CHAR] = TRUSTED {c Ź IO.GetChar[st]};
                    <>
                    <>
                    map.names Ź Rope.FromProc[namesChars, eachChar];
                    };
            EXITS noGot => {};
            };
        IO.Close[st];
        [] Ź SymTab.Store[fileCache, PFS.RopeFromPath[map.fileName], map];  -- save in cache
        };

    fileCache: SymTab.Ref ~ SymTab.Create[case: FALSE];

    CheckFileCache:  PROC[name: PFS.PATH, uid: PFS.UniqueID] RETURNS[Map] ~ {
        key: ROPE ~ PFS.RopeFromPath[name];
        val: SymTab.Val;
        found: BOOL;
        map: Map;
        [found, val] Ź SymTab.Fetch[fileCache, key];
        IF NOT found THEN RETURN[NIL];
        map _ NARROW[val];
        IF map.uid = uid THEN RETURN[map];
        RETURN[NIL];
        };

    Length: PUBLIC PROC [map: Map] RETURNS [INT] = {
        <>
        RETURN [IF map = NIL THEN 0 ELSE map.len];
        };

    Fetch: PUBLIC PROC [map: Map, index: CARDINAL] RETURNS [stamp: VersionStamp, name: ROPE, created: GMT] = {
        <>
        <>
        stamp Ź MsToVs[nullStamp];
        name Ź NIL;
        IF map # NIL AND index IN [0..map.len) THEN {
            entry: MapEntry Ź map[index];
            stamp Ź MsToVs[entry.stamp];
            name Ź IndexToFullName[map, entry.index];
            created Ź entry.created;
            };
        };

    FetchCreated: PUBLIC PROC [map: Map, index: CARDINAL] RETURNS [created: GMT Ź nullGMT] = {
        <>
            <>
        IF map # NIL AND index IN [0..map.len) THEN {
            entry: MapEntry Ź map[index];
            created Ź entry.created;
            };
        };

    FetchStamp: PUBLIC PROC [map: Map, index: CARDINAL] RETURNS [stamp: VersionStamp] = {
        <>
        <>
        stamp Ź MsToVs[nullStamp];
        IF map # NIL AND index IN [0..map.len) THEN {
            entry: MapEntry Ź map[index];
            stamp Ź MsToVs[entry.stamp];
            };
        };

    FetchName: PUBLIC PROC [map: Map, index: CARDINAL] RETURNS [name: ROPE] = {
        <>
        <>
        name Ź NIL;
        IF map # NIL AND index IN [0..map.len) THEN {
            entry: MapEntry Ź map[index];
            name Ź IndexToFullName[map, entry.index];
            };
        };

    RangeToEntry: PUBLIC PROC [range: Range] RETURNS [name: ROPE, stamp: VersionStamp, created: GMT, next: Range] = {
        <<... returns the name and stamp for the first entry in the range, also returning the next range.  If an empty range is given, the 
        name returned will be NIL, and the range returned will be empty.>>
        IF range.len = 0
            THEN {name Ź NIL; next Ź [range.map, 0, 0]; created Ź nullGMT}
            ELSE {
                index: CARDINAL Ź range.map.shortNameSeq[range.first];
                map: Map Ź range.map;
                entry: MapEntry Ź map[index];
                next Ź [map, range.first+1, range.len-1];
                name Ź IndexToFullName[map, entry.index];
                stamp Ź MsToVs[entry.stamp];
                created Ź entry.created;
                };
        };

    FillInShortNames: PUBLIC PROC [map: Map]
        = {FillInLimitedShortNames[[map, map.len]]};

    FillInLimitedShortNames: PROC [lm: LimitedMap] = {
        map: Map ~ lm.map;
        names: ROPE = map.names;
        len: CARDINAL = lm.limit;
        subLen: CARDINAL = len/32;
        pqa: REF ArrayOfQueue Ź NEW[ArrayOfQueue Ź ALL[NIL]];
        dstx: CARDINAL Ź 0;
        new: ShortNameSeq Ź NEW[ShortNameSeqRep[len]];
        map.shortNameSeq Ź new;
        FOR i: CARDINAL IN [0..len) DO
            c: CHAR Ź Rope.Fetch[names, GetFirstShortNameIndex[map, i]];
            pq: Cvt Ź NIL;
            SELECT TRUE FROM
                LOOPHOLE[c-'A, CARDINAL] <= ('Z-'A) => c Ź c + ('a-'A);
                c NOT IN GoodChars => c Ź FIRST[GoodChars];
                ENDCASE;
            pq Ź pqa[c];
            IF pq = NIL THEN pqa[c] Ź pq Ź CreatePQ[map, subLen];
            Insert[pq, i];
            ENDLOOP;
        FOR c: CHAR IN GoodChars DO
            pq: Cvt = pqa[c];
            IF pq # NIL THEN {
                FOR i: CARDINAL IN [0..pq.size) DO
                    new[dstx] Ź Remove[pq];
                    dstx Ź dstx + 1;
                    ENDLOOP;
                };
            ENDLOOP;
        pqa Ź ALL[NIL];  -- I deserve a good citizenship award for this!
        };

    LookupByExtension: PUBLIC PROC [mapList: MapList, base: ROPE, extensions: LIST OF ROPE] RETURNS [ROPE] = {
        key: ROPE ~ Rope.Concat[base, "."];
        keySize: INT ~ Rope.Size[key];
        ranges: RangeList ~ ShortNameToRanges[mapList, key];
        winningExtNum: NAT Ź NAT.LAST;
        winningFullFName: ROPE Ź NIL;
        FOR tail: RangeList Ź ranges, tail.rest UNTIL tail=NIL DO
            range: Range ~ tail.first;
            mapLength: CARDINAL ~ Length[range.map];
            FOR index: CARDINAL Ź range.first, index + 1 WHILE index < mapLength DO
                fullUName: ROPE ~ RangeToEntry[[range.map, index, 1]].name;
                entryName: ROPE ~ ShortName[fullUName];
                IF Rope.Run[s1: key, s2: entryName, case: FALSE] = keySize
                    THEN {
                        extNum: INT ~ FindExt[Rope.Substr[entryName, keySize], extensions];
                        IF extNum < winningExtNum THEN {
                            winningExtNum Ź extNum;
                            winningFullFName Ź fullUName;
                            IF extNum = 0 THEN RETURN [winningFullFName]; -- can't get better than this!
                            };
                        }
                    ELSE EXIT;
                ENDLOOP;
            ENDLOOP;
        RETURN [winningFullFName];
        };

<>

    FindExt: PROC [ext: ROPE, extensions: LIST OF ROPE] RETURNS [NAT] ~ {
        <>
        FOR i: NAT Ź 0, i+1 DO
            IF extensions = NIL THEN RETURN [NAT.LAST];
            IF Rope.Match[pattern: extensions.first, object: ext, case: FALSE] THEN RETURN [i];
            extensions Ź extensions.rest;
            ENDLOOP;
        };

    MyStampToHex: PROC [stamp: MyStamp] RETURNS [ROPE] = {
        index: NAT Ź 0;
        each: PROC RETURNS [c: CHAR] = {
            x: HexDigit Ź hex[index];
            IF x IN [0..9] THEN c Ź 'a + hex[index];
            index Ź index + 1;
            };
        hex: MyStampAsHex Ź LOOPHOLE[stamp];
        RETURN [Rope.FromProc[12, each]];
        };

    VsToMs: PROC [vs: VersionStamp] RETURNS [MyStamp] = {
        l0: Basics.LongNumber ~ [card[vs[0]]];
        l1: Basics.LongNumber ~ [card[vs[1]]];
        RETURN [[lo: l1.hi, num: l0.lo, hi: l0.hi, extra: l1.lo]]};

    MsToVs: PROC [ms: MyStamp] RETURNS [VersionStamp] = {
        l0: Basics.LongNumber ~ [pair[lo: ms.num, hi: ms.hi]];
        l1: Basics.LongNumber ~ [pair[lo: ms.extra, hi: ms.lo]];
        RETURN [[l0.card, l1.card]]};

    IndexToShortName: PROC [map: Map, index: INT] RETURNS [ROPE] = {
        <>
        names: ROPE Ź map.names;
        pos: INT Ź names.SkipTo[index, "!\l\r"];
        RETURN [names.Substr[index, pos-index]];
        };

    IndexToMidName: PROC [map: Map, index: INT] RETURNS [ROPE] = {
        <>
        names: ROPE Ź map.names;
        pos: INT Ź names.SkipTo[index, "\r\l"];
        RETURN [names.Substr[index, pos-index]];
        };

    IndexToFullName: PROC [map: Map, index: INT] RETURNS [ROPE] = {
        <>
        names: ROPE Ź map.names;
        pos: INT Ź names.SkipTo[index, "\r\l"];
        name: ROPE Ź names.Substr[index, pos-index];
        IF NOT Rope.Match["[*", name] THEN {
            prepos: INT Ź names.SkipTo[0, "\r\l"];
            prefix: ROPE Ź names.Substr[0, prepos];
            name Ź prefix.Concat[name]};
        RETURN [name];
        };

    FindIndex: PROC [vmap: Map, t: VersionStamp] RETURNS [index: EntryIndex] = {
        mt: MyStamp Ź VsToMs[t];
        mn: CARDINAL Ź mt.num;
        i,k: CARDINAL Ź 0;
        j: CARDINAL Ź vmap.len-1;
        lo,mid: CARDINAL Ź vmap[i].stamp.num;
        hi: CARDINAL Ź vmap[j].stamp.num;
        probes: NAT Ź 0;
        DO
            SELECT mn FROM
                < lo, > hi => EXIT; -- can never find it!
                = lo => k Ź i; -- found it at the low point!
                = hi => k Ź j; -- found it at the high point!
                ENDCASE =>
                    {-- use interpolation for speed!
                        dh: CARDINAL = hi-lo;
                        dt: CARDINAL = mn-lo;
                        <>
                        --TRUSTED {k Ź Basics.LongDiv[Basics.LongMult[j-i, dt], dh] + i};
                        k Ź (((j-i) * dt)/ dh) + i;
                        mid Ź vmap[k].stamp.num;
                        probes Ź probes + 1;
                        SELECT mid FROM
                            < mn => {lo Ź vmap[i Ź k + 1].stamp.num; LOOP};
                            > mn => {hi Ź vmap[j Ź k - 1].stamp.num; LOOP};
                                ENDCASE};
            {-- at this point, we are in a range of stamps that have equal mid-values; also, vmap[k].stamp.num = mt; a sequential search will 
            do just fine
                km: CARDINAL Ź k;
                m: MyStamp Ź vmap[k].stamp;
                <>
                IF m = mt THEN GO TO found;
                <>
                WHILE km > i DO
                    km Ź km-1;
                    m Ź vmap[km].stamp;
                    IF m = mt THEN {k Ź km; GO TO found};
                    IF m.num # mn THEN EXIT;
                    ENDLOOP;
                <>
                WHILE k < j DO
                    k Ź k+1;
                    m Ź vmap[k].stamp;
                    IF m = mt THEN GO TO found;
                    IF m.num # mn THEN EXIT;
                    ENDLOOP;
                EXIT; -- not found
            EXITS
                found =>  {
                    RETURN [k]}};
            ENDLOOP;
        RETURN [NullEntryIndex];
        };

    FindIndexRange: PROC [vmap: Map, t: VersionStamp] RETURNS [lo,hi: EntryIndex] = {
        stamp: MyStamp Ź VsToMs[t];
        lim: EntryIndex Ź vmap.len - 1;
        hi Ź 0;
        lo Ź FindIndex[vmap, t];
        IF lo = NullEntryIndex THEN RETURN;
        hi Ź lo;
        WHILE lo > 0 DO
            IF vmap[lo-1].stamp # stamp THEN EXIT;
            lo Ź lo-1;
            ENDLOOP;
        WHILE hi < lim DO
            IF vmap[hi+1].stamp # stamp THEN EXIT;
            hi Ź hi + 1;
            ENDLOOP;
        };

    GetFirstShortNameIndex: PROC [map: Map, index: CARDINAL] RETURNS [INT] = {
        len: CARDINAL = map.len;
        names: ROPE = map.names;
        pos: INT Ź (IF index+1 >= len THEN Rope.Length[names] ELSE map[index+1].index)-1;
        DO
            <>
            c: CHAR = Rope.Fetch[names, pos Ź pos - 1];
            SELECT c FROM
                '\l, '\r, '/, '>, '] => RETURN [pos+1];
                ENDCASE;
            ENDLOOP;
        };
        <<>>
    ShortNameFind: PROC [map: Map, name: ROPE]
    RETURNS [index: CARDINAL, found: BOOL Ź TRUE] = {
        <<... finds the given short name in the index, using the given predicate, which must be consistent with the predicate used to build 
        the index.>>
        mapIndex: ShortNameSeq = map.shortNameSeq;
        lo: CARDINAL Ź 0;
        hi: CARDINAL Ź mapIndex.len-1;
        name Ź Rope.Flatten[name];  -- to speed comparisons
        WHILE lo <= hi DO
            index Ź (lo+hi)/2;
            SELECT ShortNameFindPred[name, mapIndex[index], map] FROM
                less => {
                    IF lo = index THEN EXIT;
                    hi Ź index - 1;
                    };
                greater => {
                    IF hi = index THEN EXIT;
                    lo Ź index + 1;
                    };
                equal => RETURN;
                ENDCASE => ERROR;
            ENDLOOP;
        found Ź FALSE;
        };

    ShortNameFindPred: PROC [name: ROPE, index: CARDINAL, map: Map]
    RETURNS [Comparison] = {
        <>
        len: CARDINAL = map.len;
        names: ROPE = map.names;
        pos1: INT Ź 0;
        lim1: INT = Rope.Length[name];
        pos2: INT Ź GetFirstShortNameIndex[map, index];
        DO
            <>
            c1: CHAR Ź IF pos1 = lim1 THEN '\r ELSE Rope.Fetch[name, pos1];
            c2: CHAR Ź Rope.Fetch[names, pos2];
            IF LOOPHOLE[c1-'A, CARDINAL] <= ('Z-'A) THEN c1 Ź c1 + ('a-'A);
            SELECT TRUE FROM
                c2 = '! => c2 Ź '\r;
                LOOPHOLE[c2-'A, CARDINAL] <= ('Z-'A) => c2 Ź c2 + ('a-'A);
                ENDCASE;
            IF c1 # c2 THEN RETURN [
                Basics.CompareCard[LOOPHOLE[c1, CARDINAL], LOOPHOLE[c2, CARDINAL]]];
            IF c1 = '\r THEN RETURN [equal];
            pos1 Ź pos1 + 1;
            pos2 Ź pos2 + 1;
            ENDLOOP;
        };

<>
    GoodChars: TYPE = CHAR[40C..'z];
    ArrayOfQueue: TYPE = ARRAY CHAR OF Cvt;

    ShortNameSortPred: PROC [x1,x2: CARDINAL, map: Map] RETURNS [Comparison] = {
        <>
        len: CARDINAL = map.len;
        names: ROPE = map.names;
        pos1: INT Ź GetFirstShortNameIndex[map, x1];
        pos2: INT Ź GetFirstShortNameIndex[map, x2];
        DO
            <>
            c1: CHAR Ź Rope.Fetch[names, pos1];
            c2: CHAR Ź Rope.Fetch[names, pos2];
            IF LOOPHOLE[c1-'A, CARDINAL] <= ('Z-'A) THEN c1 Ź c1 + ('a-'A);
            IF LOOPHOLE[c2-'A, CARDINAL] <= ('Z-'A) THEN c2 Ź c2 + ('a-'A);
            IF c1 # c2 THEN RETURN [
                Basics.CompareCard[LOOPHOLE[c1, CARDINAL], LOOPHOLE[c2, CARDINAL]]];
            SELECT c1 FROM '!, '\r, '\l => RETURN [equal]; ENDCASE;
            pos1 Ź pos1 + 1;
            pos2 Ź pos2 + 1;
            ENDLOOP;
        };
<>

    PQempty: PUBLIC ERROR = CODE;
    PQover: PUBLIC ERROR = CODE;

    --MaxSize: INT = LAST[CARDINAL];
    MaxSize: CARDINAL = LAST[CARDINAL];
    Seq: TYPE = REF SeqRep;
    SeqRep: TYPE = RECORD [elements: SEQUENCE space: CARDINAL OF CARDINAL];
    Cvt: TYPE = REF Rep;
    Rep: TYPE = RECORD [
        map: Map,
        size: CARDINAL,
        seq: Seq];

    CreatePQ: PROC [map: Map, size: CARD Ź 0] RETURNS [pq: Cvt] = {
        <>
        IF size > MaxSize THEN ERROR PQover;
        IF size <= 0 THEN size Ź 4 ELSE size Ź size + 1;
        pq Ź NEW[Rep Ź [map, 0, NEW[SeqRep[size]]]];
        };

    Insert: PROC [pq: Cvt, item: CARDINAL] = {
        <>
        size: CARDINAL Ź pq.size;  -- figure out new size
        a: Seq Ź pq.seq;             -- grab the descriptor
        space: CARDINAL Ź IF a = NIL THEN 0 ELSE a.space;
        maxCard: CARDINAL = MaxSize;  -- to aid the poor little compiler

        <>
        IF size = MaxSize THEN RETURN WITH ERROR PQover;
        size Ź size + 1;

        <>
        IF size >= space THEN {
            seq: Seq Ź NIL;
            IF space = 0 THEN space Ź 1;
            SELECT space FROM
                < 2048 => space Ź space + space;
                < maxCard-1024 => space Ź space + 1024;
                ENDCASE => space Ź MaxSize; 
            seq Ź NEW[SeqRep[space]];
            FOR i: CARDINAL IN [1..size) DO
                seq[i] Ź a[i];
                ENDLOOP;
            pq.seq Ź a Ź seq;
            };

        IF size = 1
            THEN a[1] Ź item
            ELSE {
                <>
                son: CARDINAL Ź size;
                dad: CARDINAL Ź son/2;
                map: Map = pq.map;
                dadItem: CARDINAL;
                WHILE dad > 0 AND ShortNameSortPred[item, dadItem Ź a[dad], map] = less DO
                    <>
                    a[son] Ź dadItem;
                    son Ź dad;
                    dad Ź son/2;
                    ENDLOOP;
                a[son] Ź item;    -- finally insert the new item
                };
        pq.size Ź size;  -- also update the size
        };

    Remove: PROC [pq: Cvt] RETURNS [CARDINAL] = {
        <>
        size: CARDINAL Ź pq.size;    -- current size of pq
        a: Seq Ź pq.seq;           -- desc to real stuff
        best: CARDINAL;            -- holder for best item
        item: CARDINAL;            -- holder for moving item
        IF size = 0 THEN ERROR PQempty;

        <>
        best Ź a[1];           -- remember best item
        item Ź a[size];        -- get moving item
        size Ź size - 1;       -- new size of pq
        pq.size Ź size;        -- also update size in pq
        IF size # 0 THEN {
            <>
            <<(better items move up)>>
            dad: CARDINAL Ź 1;             -- current index for moving item
            maxdad: CARDINAL Ź size / 2;   -- highest index for father item
            map: Map = pq.map;
            WHILE dad <= maxdad DO
                son: CARDINAL Ź dad + dad;
                sonItem: CARDINAL Ź a[son];
                IF son < size THEN {
                    <>
                    nson: CARDINAL Ź son + 1;
                    nsonItem: CARDINAL Ź a[nson];
                    IF ShortNameSortPred[nsonItem, sonItem, map] = less THEN {
                        son Ź nson;
                        sonItem Ź nsonItem;
                        };
                    };
                IF ShortNameSortPred[item, sonItem, map] = less THEN EXIT;
                a[dad] Ź sonItem;
                dad Ź son;
                ENDLOOP;
            a[dad] Ź item;
            };

        <>
        RETURN [best];
        };

<>
    <<>>
    <>
    <>
        <>
        <>
        <<[lo,hi] _ FindIndexRange[map, MsToVs[map[i].stamp]];>>
        <>
        <<};>>
        <<>>
    <>
        <>
        <>
        <>
            <<[] _ SingleTestFindIndex[map, i];>>
            <>
        <<};>>
        <<>>
<>

    FileNameFromVersion: PUBLIC PROC [which: ATOM, version: VersionStamp]
    RETURNS [name: ROPE Ź NIL, created: BasicTime.GMT] = {
        <<... returns a name corresponding to the given version stamp in the indicated map list (does not check for multiple names, since 
        that is the responsibility of the version map creator).>>
        mapList: MapList Ź GetMapList[which];
        IF mapList # NIL THEN {
            mapAndName: MapAndName Ź VersionToName[mapList, version];
            name Ź mapAndName.name;
            created Ź mapAndName.created;
            };
        };

    GetMapList: PUBLIC PROC [which: ATOM] RETURNS [list: MapList Ź NIL] = {
        <<... gets the requested version map list.  Map lists are defined either by user profile entries, or by someone making explicit 
        calls on AddToMapList or SetMapList.>>
        name: ROPE = Atom.GetPName[which];
        --useCachedMaps: BOOL ~ UserProfile.Boolean["VersionMap.UseCachedMaps", FALSE];
        useCachedMaps: BOOL ~ FALSE;
        Try: ENTRY PROC RETURNS [BOOL] = {
            ENABLE UNWIND => NULL;
            mapFileNameList: LIST OF ROPE Ź NIL;
            FOR eList: EntryList Ź root, eList.rest WHILE eList # NIL DO
                IF eList.first.key = which THEN {
                    list Ź eList.first.mapList;
                    RETURN [TRUE]};
                ENDLOOP;
            SELECT which FROM
                $Source => mapFileNameList Ź defaultSourceNameList;
                $Intermediate => mapFileNameList Ź defaultIntermediateNameList;
                $Executable => mapFileNameList Ź defaultExecutableNameList;
                $Symbols => mapFileNameList Ź defaultSymbolsNameList;
                ENDCASE => RETURN [FALSE];
            FOR vL: LIST OF ROPE Ź mapFileNameList, vL.rest UNTIL vL = NIL DO
                nl: Map Ź VerboseRestoreMapFromFile[PFS.PathFromRope[vL.first], PFS.nullUniqueID, assumeImmutableGlobal, NIL];
                AddToMapListInternal[which, nl];
                ENDLOOP;
            RETURN [TRUE]};
        IF Try[] THEN RETURN;
        ProcessUserProfileList[
            class: which,
            key: Rope.Cat["VersionMap.", name, "Maps"],
            alwaysList: LIST[Rope.Cat["Cedar", name, ".VersionMap"]],
            useCached: useCachedMaps
            ];
        [] Ź Try[];
        RETURN};

    AddToMapList: PUBLIC ENTRY PROC [which: ATOM, map: Map] = {
        ENABLE UNWIND => NULL;
        AddToMapListInternal[which, map];
        };

    AddToMapListInternal: INTERNAL PROC[which: ATOM, map: Map] = {
        <<... adds a new map to the lookup list.  Use this proc for adding personal version maps.>>
        mapList: MapList Ź LIST[map];
        IF map = NIL THEN RETURN;
        FOR eList: EntryList Ź root, eList.rest WHILE eList # NIL DO
            IF eList.first.key = which THEN {
                mapList.rest Ź eList.first.mapList;
                eList.first.mapList Ź mapList;
                RETURN};
            ENDLOOP;
        <>
        root Ź CONS[Entry[which, mapList], root];
        };

    SetMapList: PUBLIC ENTRY PROC [which: ATOM, list: MapList Ź NIL] = {
        <<.. sets the current version map for source files.  Since there can be a race between GetMapList and SetMapList, this operation 
        should not be casually used!>>
        ENABLE UNWIND => NULL;
        FOR eList: EntryList Ź root, eList.rest WHILE eList # NIL DO
            IF eList.first.key = which THEN {
                eList.first.mapList Ź list;
                RETURN};
            ENDLOOP;
        <>
        root Ź CONS[Entry[which, list], root];
        };

    ProcessUserProfile: UserProfile.ProfileChangedProc = {
        fork: BOOL ~ UserProfile.Boolean["VersionMap.Fork", FALSE];
        useCachedMaps: BOOL ~ UserProfile.Boolean["VersionMap.UseCachedMaps", FALSE];
        -- forking not yet implemented
        --IF fork THEN TRUSTED { Process.Detach[FORK DoIt[useCachedMaps]] } ELSE DoIt[useCachedMaps]; 
        DoIt[FALSE];
        };

    DoVersionMapsNow: PUBLIC PROC = {
        fork: BOOL ~ UserProfile.Boolean["VersionMap.Fork", FALSE];
        --IF fork THEN TRUSTED { Process.Detach[FORK DoIt[FALSE]] } ELSE DoIt[FALSE];
        -- forking not yet implemented
        DoIt[FALSE];
        };

    DoIt: PROC [useCached: BOOL] ~ {
        absent: LIST OF ROPE = LIST["it's missing!"];
        FOR eList: EntryList Ź root, eList.rest WHILE eList # NIL DO
            IF eList.first.key = $Source OR eList.first.key = $Symbols THEN LOOP;
            {name: ROPE = Atom.GetPName[eList.first.key];
            key: ROPE ~ Rope.Cat["VersionMap.", name, "Maps"];
            IF UserProfile.ListOfTokens[key, absent] # absent THEN ProcessUserProfileList[
                class: eList.first.key,
                key: key,
                alwaysList: LIST[Rope.Cat["Cedar", name, ".VersionMap"]],
                useCached: useCached];
            }ENDLOOP;
        ProcessUserProfileList[
        $Symbols, "VersionMap.SymbolsMaps", defaultSymbolsNameList, useCached];
        ProcessUserProfileList[
        $Source, "VersionMap.SourceMaps", defaultSourceNameList, useCached];
        ProcessUserProfileList[
        $Intermediate, "VersionMap.IntermediateMaps", defaultIntermediateNameList, useCached];
        ProcessUserProfileList[
        $Executable, "VersionMap.ExecutableMaps", defaultExecutableNameList, useCached];
        };

    ProcessUserProfileList: PROC [
    class: ATOM, key: ROPE, alwaysList: LIST OF ROPE, useCached: BOOL] = {
        list: LIST OF ROPE Ź UserProfile.ListOfTokens[key, NIL];
        aList: LIST OF ROPE Ź alwaysList;
        FOR each: LIST OF ROPE Ź list, each.rest WHILE each # NIL DO
            each.first Ź FS.ExpandName[each.first ! FS.Error => CONTINUE].fullFName;
                <>
            ENDLOOP;
        FOR ll: LIST OF ROPE Ź aList, ll.rest UNTIL ll = NIL DO
            ll.first Ź FS.ExpandName[name: ll.first, wDir: versionMapDir ! FS.Error => CONTINUE].fullFName;
            IF ll.first # NIL THEN list Ź RemoveRope[list, ll.first];
            ENDLOOP;
        SetMapList[class, NIL];
        FOR aa: LIST OF ROPE Ź aList, aa.rest UNTIL aa = NIL DO
            ProcessAName[class, aa.first, useCached];
            ENDLOOP;
        WHILE list # NIL DO
            name: ROPE = list.first;
            list Ź RemoveRope[list, name];
            ProcessAName[class, name, useCached];
            ENDLOOP;
        };

    ProcessAName: PROC [class: ATOM, name: ROPE, useCached: BOOL] = {
        map: Map Ź NIL;
        prevName: ROPE Ź NIL;
        nameCount: INT Ź 0;
        map Ź VerboseRestoreMapFromFile[PFS.PathFromRope[name], PFS.nullUniqueID, assumeImmutableGlobal, NIL ! PFS.Error => CONTINUE];
        IF map # NIL THEN AddToMapList[class, map];
        };

    RemoveRope: PROC [list: LIST OF ROPE, item: ROPE] RETURNS [LIST OF ROPE] = {
        lag: LIST OF ROPE Ź NIL;
        FOR each: LIST OF ROPE Ź list, each.rest WHILE each # NIL DO
            IF Rope.Equal[each.first, item, FALSE] THEN {
                IF lag = NIL THEN list Ź each.rest ELSE lag.rest Ź each.rest;
                LOOP;
                };
            lag Ź each;
            ENDLOOP;
        RETURN [list];
        };

<>
    FindSource: PUBLIC PROC [short: ROPE, removeDuplDates: BOOL Ź TRUE, which: ATOM Ź NIL] RETURNS [SourceFileList Ź NIL] = TRUSTED {
        size: INT Ź Rope.Length[short];
        starPos: INT Ź short.Index[0, "*"];
        match: BOOL Ź starPos # size;
        hasDot: BOOL Ź short.Index[0, "."] # size;
        rangeList: VersionMap.RangeList Ź NIL;
        head: SourceFileList Ź NIL;
        tail: SourceFileList Ź NIL;
        shortShort: ROPE Ź Rope.Flatten[short, 0, starPos];
        shortShortLen: INT Ź Rope.Length[shortShort];
        mapList: VersionMap.MapList Ź NIL;
        IF size = 0 THEN RETURN;
        IF which = NIL THEN which Ź $Source;
        IF mapList = NIL THEN mapList Ź GetMapList[which];
        rangeList Ź ShortNameToRanges[mapList, short];
        WHILE rangeList # NIL DO
            range: VersionMap.Range Ź rangeList.first;
            map: VersionMap.Map = range.map;
            rangeList Ź rangeList.rest;
            Process.CheckForAbort[];
            IF match
                THEN {
                    entries: CARDINAL = Length[map];
                    IF range.first >= entries THEN LOOP;
                    range.len Ź entries - range.first;
                    WHILE range.len # 0 DO
                        fullName: ROPE;
                        stamp: VersionStamp;
                        thisShort: ROPE;
                        created: BasicTime.GMT;
                        [fullName, stamp, created, range] Ź RangeToEntry[range];
                        thisShort Ź ShortName[fullName];
                        IF Rope.Run[shortShort, 0, thisShort, 0, FALSE] # shortShortLen THEN EXIT;
                        IF Rope.Match[short, thisShort, FALSE] THEN {
                            new: SourceFileList
                                Ź LIST[[map: range.map, name: fullName, created: created, stamp: stamp]];
                            IF tail = NIL THEN head Ź new ELSE tail.rest Ź new;
                            tail Ź new;
                            };
                        ENDLOOP;
                    }
                ELSE {
                    WHILE range.len # 0 DO
                        new: SourceFileList;
                        fullName: ROPE;
                        stamp: VersionStamp;
                        created: BasicTime.GMT;
                        [fullName, stamp, created, range] Ź RangeToEntry[range];
                        new Ź LIST[[map: range.map, name: fullName, created: created, stamp: stamp]];
                        IF tail = NIL THEN head Ź new ELSE tail.rest Ź new;
                        tail Ź new;
                        ENDLOOP;
                    };
            ENDLOOP;
        RemoveDuplicates[head, removeDuplDates];
        RETURN [head];
        };

    RemoveDuplicates: PROC [sfl: SourceFileList, removeDuplDates: BOOL] = {
        <>
        WHILE sfl # NIL DO
            entry: SourceFileEntry Ź sfl.first;
            thisStamp: VersionStamp Ź entry.stamp;
            each: SourceFileList Ź sfl.rest;
            lag: SourceFileList Ź sfl;
            WHILE each # NIL DO
                next: SourceFileList Ź each.rest;
                SELECT TRUE FROM
                    Rope.Equal[each.first.name, entry.name, FALSE] => lag.rest Ź next;
                    removeDuplDates AND each.first.stamp = thisStamp => lag.rest Ź next;
                    ENDCASE => lag Ź each;
                each Ź next;
                ENDLOOP;
            sfl Ź sfl.rest;
            ENDLOOP;
        };

    MaplistDesc: PUBLIC PROC [which: ATOM] RETURNS [ROPE] ~ {
        IF which=$Symbols OR which=$Source THEN RETURN ["current Cedar release"];
        RETURN Rope.Concat[Atom.GetPName[which], " version map"]
        };

    MapListForName: PUBLIC PROC [fileName: ROPE] RETURNS[MapList] =
        { RETURN[GetMapList[MapAtomForName[fileName].which]] };

    MapAtomForName: PUBLIC PROC[fileName: ROPE] RETURNS[which, other: ATOM] = {
        <>
        woVersion: ROPE ~ FileNames.ConvertToSlashFormat[FileNames.StripVersionNumber[fileName]];
        SELECT TRUE FROM
            Rope.Match["*.mob", woVersion, FALSE] => which _ $Intermediate;
            Rope.Match["*.c2c.c", woVersion, FALSE] => which _ $Intermediate;
            Rope.Match["*/debug/*.o", woVersion, FALSE] => which _ $Executable;
            Rope.Match["*/sun4-debug/*.o", woVersion, FALSE] => which _ $Executable;
            Rope.Match["*/sun4/*.o", woVersion, FALSE] => which _ $Executable;
            Rope.Match["*/sun4-o3/*.o", woVersion, FALSE] => {
                which _ $Executable;
                other _ $opt;
                };
            Rope.Match["*/optimized/*.o", woVersion, FALSE] => {
                which _ $Executable;
                other _ $opt;
                };
            Rope.Match["*/sun4O3/*.o", woVersion, FALSE] => {
                which _ $Executable;
                other _ $opt;
                };
            Rope.Match["*.o", woVersion, FALSE] => which _ $Executable;
            ENDCASE => which _ $Source;
        };

    GetMapAtomList: PUBLIC PROC RETURNS[LIST OF ATOM] = {
        la: LIST OF ATOM Ź NIL;
        FOR eList: EntryList Ź root, eList.rest WHILE eList # NIL DO
            la Ź CONS[eList.first.key, la];
            ENDLOOP;
        RETURN[la];
        };

<>
    StartConstruction: PUBLIC PROC [size: NAT Ź 0] RETURNS [muc: MapUnderConstruction] ~ {
        muc Ź NEW [MapUnderConstructionPrivate Ź [
            pq: IF size>0 THEN PriorityQueue.Predict[size, EntrySortPred] ELSE PriorityQueue.Create[EntrySortPred]
            ]];
        };

    AddFile: PUBLIC PROC [muc: MapUnderConstruction, t: VersionMapBuilding.ConsTuple] ~ {
        entry: FileEntry Ź NEW[FileEntryRep Ź [
            name: t.name, created: t.created, myStamp: VsToMs[t.stamp], from: t.from]];
        PriorityQueue.Insert[muc.pq, entry];
        RETURN};

    FinishConstruction: PUBLIC PROC [muc: MapUnderConstruction, prefix: ROPE, PerDuplicate: PROC [a, b: VersionMapBuilding.ConsTuple]] 
    RETURNS [map: Map] ~ {
        [[map,]] Ź FinishLimitedConstruction[muc, prefix, PerDuplicate, FALSE];
        RETURN};

    FinishLimitedConstruction: PUBLIC PROC [muc: MapUnderConstruction, prefix: ROPE, PerDuplicate: PROC [a, b: 
    VersionMapBuilding.ConsTuple], suppressDuplicates: BOOL] RETURNS [LimitedMap] ~ {
        pq: PriorityQueue.Ref ~ muc.pq;
        prefixLen: NAT = Rope.Size[prefix];
        entries: NAT = PriorityQueue.Size[pq];
        currentName: ROPE Ź prefix Ź Rope.Flatten[prefix];
        pos: INT Ź prefixLen+1;
        seq: NameSeq Ź NEW[NameSeqRep[entries]];
        entryIndex: NAT Ź 0;
        subPos: NAT Ź 0;
        subLim: NAT Ź prefixLen;
        lastPos: INT Ź 0;
        lag: FileEntry Ź NIL;
        getChar: PROC [] RETURNS [c: CHAR] = {
            IF subPos < subLim THEN {
                c Ź currentName.Fetch[subPos];
                subPos Ź subPos + 1;
                RETURN;
                };
            c Ź '\r;
            IF entryIndex < entries THEN {
                nameEntry: NameEntry Ź seq[entryIndex];
                currentName Ź nameEntry.name;
                subLim Ź Rope.Length[currentName];
                IF nameEntry.hasPrefix THEN subPos Ź prefixLen ELSE subPos Ź 0;
                entryIndex Ź entryIndex + 1;
                };
            };
        map: Map Ź NEW[MapRep[entries]];
        limit: NAT Ź entries;
        i: NAT Ź 0;
        WHILE NOT PriorityQueue.Empty[pq] DO
            entry: FileEntry = NARROW[PriorityQueue.Remove[pq]];
            name: ROPE = entry.name;
            hasPrefix: BOOL = Rope.Run[name, 0, prefix, 0, FALSE] = prefixLen;
            IF lag=NIL OR lag.myStamp#entry.myStamp THEN pos Ź pos
            ELSE IF suppressDuplicates AND lag.created=entry.created AND lag.name.Equal[entry.name, FALSE] THEN {limit Ź limit.PRED; LOOP}
            ELSE PerDuplicate[
                <>
                a: [lag.name, lag.from, lag.created, MsToVs[lag.myStamp]],
                b: [entry.name, entry.from, entry.created, MsToVs[entry.myStamp]]
                ];
            seq[i] Ź [hasPrefix, name];
            map[i] Ź [stamp: entry.myStamp, created: entry.created, index: pos];
            pos Ź pos + Rope.Length[name] + 1;
            IF hasPrefix THEN pos Ź pos - prefixLen;
            lag Ź entry;
            i Ź i.SUCC;
            ENDLOOP;
        IF i#limit THEN ERROR;
        IF limit < entries THEN map[limit] Ź [stamp: NullStamp, created: BasicTime.nullGMT, index: pos];
        map.names Ź Rope.FromProc[pos, getChar, 4040];
        FillInLimitedShortNames[[map, limit]];
        RETURN [[map, limit]]};

    ClassifyDifference: PUBLIC PROC [a, b: VersionMapBuilding.ConsTuple] RETURNS [VersionMapBuilding.DifferenceClass] ~ {
        IF a.created=b.created AND a.name.Equal[b.name, FALSE] THEN RETURN [identical];
        {aCp, bCp: FS.ComponentPositions;
        aFull, bFull, aBase, bBase: ROPE;
        [aFull, aCp, ] Ź FS.ExpandName[a.name];
        [bFull, bCp, ] Ź FS.ExpandName[b.name];
        aBase Ź aFull.Substr[start: aCp.base.start, len: aCp.base.length];
        bBase Ź bFull.Substr[start: bCp.base.start, len: bCp.base.length];
        aBase Ź aBase.Substr[len: aBase.Index[s2: "."]];
        bBase Ź bBase.Substr[len: bBase.Index[s2: "."]];
        IF aBase.Equal[bBase, FALSE] THEN RETURN [identicalModExtensionAndCreated];
        RETURN [veryDifferent]}};

    EntrySortPred: PROC [x, y, data: REF ANY] RETURNS [BOOL] --PriorityQueue.SortPred-- = {
        xe: FileEntry ~ NARROW[x];
        ye: FileEntry ~ NARROW[y];
        xx: MyStamp = xe.myStamp;
        yy: MyStamp = ye.myStamp;
        IF xx.num # yy.num THEN RETURN [xx.num < yy.num];
        IF xx.hi # yy.hi THEN RETURN [xx.hi < yy.hi];
        IF xx.lo # yy.lo THEN RETURN [xx.lo < yy.lo];
        IF xx.extra # yy.extra THEN RETURN [xx.extra < yy.extra];
        SELECT BasicTime.Period[from: xe.created, to: ye.created] FROM
            <0 => RETURN [FALSE];
            >0 => RETURN [TRUE];
            =0 => RETURN [xe.name.Compare[ye.name, FALSE] < equal]
            ENDCASE => ERROR};
<>
    DoVersionMapsNowCommand: Commander.CommandProc = { DoVersionMapsNow[] };

    FindCommand: Commander.CommandProc = {
        <<[cmd: Handle] RETURNS [result: REF _ NIL, msg: ROPE _ NIL]>>
            <>
        st: IO.STREAM Ź cmd.out;
        inStream: IO.STREAM Ź IO.RIS[cmd.commandLine];
        which: ATOM Ź NARROW[cmd.procData.clientData];
        slashNotation: BOOL Ź TRUE;
        EachFile: PROC = {
            sfl: SourceFileList Ź NIL;
            r: ROPE Ź IO.GetTokenRope[inStream, IO.IDProc].token;
            IF Rope.Length[r] = 0 THEN RETURN;
            IF r.Equal["-maplist"] THEN {
                name: ROPE = IO.GetTokenRope[inStream, IO.IDProc].token;
                which Ź Atom.MakeAtom[Rope.Concat[name, Atom.GetPName[which]]];
                RETURN
                };
            IF r.Equal["-b", FALSE] THEN { slashNotation Ź FALSE; RETURN };
            IF r.Equal["-~b", FALSE] THEN { slashNotation Ź TRUE; RETURN };
            sfl Ź FindSource[r, FALSE, which];    -- try name as it is
            <>
            IF sfl = NIL THEN {
                IF NOT Rope.Match["*.*", r] THEN {
                    r Ź Rope.Concat[r, ".*"];
                    sfl Ź FindSource[r, FALSE, which];
                    };
                <>
                IF sfl = NIL THEN {
                    IO.PutF[st, "Sorry, '%g' is not in the %g.\n", [rope[r]], [rope[MaplistDesc[which]]] ];
                    RETURN;
                    };
                };
            IO.PutF1[st, "%g =>\n", [rope[r]] ];
            WHILE sfl # NIL DO
                IO.PutF[st, "  %g\n      %g\n",
                    [rope[IF slashNotation THEN FileNames.ConvertToSlashFormat[sfl.first.name] ELSE sfl.first.name]],
                    [time[sfl.first.created]]
                    ];
                sfl Ź sfl.rest;
                ENDLOOP;
            };
        DO
            EachFile[
                ! FS.Error => {msg Ź error.explanation; result Ź $Failed; EXIT};
                    IO.EndOfStream => EXIT;
                ];
            ENDLOOP;
        };

    AddToDefaultVersionMapCmd: Commander.CommandProc = {
        AddVMap[cmd.out, NIL, CommanderOps.NextArgument[cmd], NIL];
        };

    AddVersionMapCmd: Commander.CommandProc = {
        root: ROPE Ź CommanderOps.NextArgument[cmd];
        baseName, wDir: ROPE;
        IF root = NIL THEN {
            cmd.out.PutRope["\n No root for VersionMap given - quitting\n"];
            RETURN;
            };
        baseName Ź CommanderOps.NextArgument[cmd];
        IF Rope.Equal[baseName, "-base", FALSE] THEN baseName Ź CommanderOps.NextArgument[cmd];
        wDir Ź CommanderOps.NextArgument[cmd];
        IF Rope.Equal[root, "$Default"] THEN root Ź NIL;
        AddVMap[cmd.out, root, wDir, baseName];
        };

    AddVMap: PROC[out: IO.STREAM, root, wDir, baseName: ROPE] = {
        <>
        intMapList, srcMapList, execMapList: LIST OF ROPE;
        fileList: LIST OF ROPE;
        FileNameProc: FS.NameProc = {
            <>
            SELECT TRUE FROM
                Rope.Match["*Intermediate.VersionMap*", fullFName] => intMapList Ź CONS[fullFName, intMapList];
                Rope.Match["*Source.VersionMap*", fullFName] => srcMapList Ź CONS[fullFName, srcMapList];
                Rope.Match["*Executable.VersionMap*", fullFName] => execMapList Ź CONS[fullFName, execMapList];
                ENDCASE => srcMapList Ź CONS[fullFName, srcMapList];
            RETURN[TRUE];
            };
        IF wDir # NIL THEN {
            char: CHAR ~ Rope.Fetch[wDir, Rope.Length[wDir]-1];
            IF ( char # '/ ) AND ( char # '* ) THEN wDir Ź Rope.Concat[wDir, "/"];
            };
        FS.EnumerateForNames[Rope.Cat[wDir, IF baseName # NIL THEN baseName ELSE root, "*", ".VersionMap!H"], FileNameProc];
        IF root = NIL THEN {
            FOR each: LIST OF ROPE Ź srcMapList, each.rest WHILE each # NIL DO 
                ProcessAName[$Source, each.first, FALSE];
                ENDLOOP;
            FOR each: LIST OF ROPE Ź intMapList, each.rest WHILE each # NIL DO 
                ProcessAName[$Intermediate, each.first, FALSE];
                ENDLOOP;
            FOR each: LIST OF ROPE Ź execMapList, each.rest WHILE each # NIL DO 
                ProcessAName[$Executable, each.first, FALSE];
                ENDLOOP;
            }
            ELSE {
                IF srcMapList # NIL THEN {
                    class: ATOM ~ Atom.MakeAtom[Rope.Concat[root, "Source"]];
                    FOR each: LIST OF ROPE Ź srcMapList, each.rest WHILE each # NIL DO 
                        ProcessAName[class, each.first, FALSE];
                        ENDLOOP;
                    };
                IF intMapList # NIL THEN {
                    class: ATOM ~ Atom.MakeAtom[Rope.Concat[root, "Intermediate"]];
                    FOR each: LIST OF ROPE Ź intMapList, each.rest WHILE each # NIL DO 
                        ProcessAName[class, each.first, FALSE];
                        ENDLOOP;
                    };
                IF execMapList # NIL THEN {
                    class: ATOM ~ Atom.MakeAtom[Rope.Concat[root, "Executable"]];
                    FOR each: LIST OF ROPE Ź execMapList, each.rest WHILE each # NIL DO 
                        ProcessAName[class, each.first, FALSE];
                        ENDLOOP;
                    };
                };
        };

    vMapDebuggingStrm: IO.STREAM Ź NIL;

    VersionMapDebuggingOn: Commander.CommandProc ~ { vMapDebuggingStrm Ź cmd.out };

    VersionMapDebuggingOff: Commander.CommandProc ~ { vMapDebuggingStrm Ź NIL };

    Commander.Register[key: "DoVersionMapsNow", proc: DoVersionMapsNowCommand, doc: "Get new version maps (if there are any)"];
    Commander.Register[key: "AddVersionMaps", proc: AddVersionMapCmd, doc: "Usage: AddVersionMaps root { -base baseName } {wDir} - 
    where root is the name of the map, such as MyMaps, baseName is the name of the map files if different from root"];
    Commander.Register[key: "AddToDefaultVersionMaps", proc: AddToDefaultVersionMapCmd, doc: "Usage: AddToDefaultVersionMaps {wDir}"];
    Commander.Register [
        "FindR", FindCommand,
        "FindR [-maplist name] [-b] fileName - Finds Cedar release (or name if given) source file names given the short names (.mesa 
        extension is the default)",
        $Source];
    Commander.Register [
        "FindRBin", FindCommand,
        "FindRBin [-maplist name] [-b] fileName - Finds Cedar release binary file names given the short names.",
        $Symbols];
    Commander.Register [
        "FindRInt", FindCommand,
        "FindRInt [-maplist name] [-b] fileName - Finds Cedar release intermediate file names given the short names.",
        $Intermediate];
    Commander.Register [
        "FindREx", FindCommand,
        "FindREx [-maplist name] [-b] fileName - Finds Cedar release executable file names given the short names.",
        $Executable];
    Commander.Register [
        "FindP", FindCommand,
        "FindP [-maplist name] [-b] fileName - Finds PCedar release source file names given the short names.",
        $PSource];
    Commander.Register [
        "FindD", FindCommand,
        "FindD [-maplist name] [-b] fileName - Finds DCedar release source file names given the short names.",
        $DSource];
    Commander.Register [
        "FindDBin", FindCommand,
        "FindDBin [-maplist name] [-b] fileName - Finds Dedar release binary file names given the short names.",
        $DSymbols];

    Commander.Register ["VersionMapDebuggingOn", VersionMapDebuggingOn];
    Commander.Register ["VersionMapDebuggingOff", VersionMapDebuggingOff];
<>
    UserProfile.CallWhenProfileChanges[ProcessUserProfile];

    END.