-- DFSubrImpl.Mesa
-- last edit February 28, 1983 5:05 pm
-- last edit May 22, 1983 1:13 pm, Russ Atkinson
    -- changed STRING to LONG STRING in various places
-- Pilot 6.0/ Mesa 7.0

-- exports DFSubr and also to DFUser for clients

                
DIRECTORY
  CWF: TYPE USING [FWF0, FWF1, FWF2, FWF3, FWFCR, SetWriteProcedure, 
      SWF2, WF0, WF1, WF2, WF3, WF4, WFC],
  DFSubr: TYPE USING [Criterion, DF, DFFileRecord, DFSeq, DFSeqRecord, 
      InterestingNestedDFProcType, ParseStream, UsingSeq, UsingSeqRecord, ZoneType],
  DFUser: TYPE USING[EnumerateProcType, SortOption],
  Directory: TYPE USING [Error, Handle, ignore, Lookup],
  Environment: TYPE USING [wordsPerPage],
  Heap: TYPE USING [Create, Delete, Error, GetAttributes],
  Inline: TYPE USING [BITXOR, BytePair, LowHalf],
  IO: TYPE USING[Handle, PutChar, UserAbort],
  LongString: TYPE USING [AppendChar, CompareStrings, EquivalentString, StringToDecimal],
  Rope: TYPE USING[Lower, ROPE],
  Space: TYPE USING [Create, CreateUniformSwapUnits, Delete, Error, Handle, LongPointer, 
      Map, virtualMemory],
  STPSubr: TYPE USING [CachedOpen, StopSTP, StpStateRecord],
  Stream: TYPE USING [Delete, Handle, PutChar],
  Subr: TYPE USING [AbortMyself, AllocateString, CopyString, EndsIn, errorflg, 
      FileError, FreeString, HugeZone, LongZone, MakeTTYProcs,
      SpaceZone, strcpy, 
        SubrStop, SubStrCopy, TTYProcs, WordsFromHugeZone],
  SystemInternal: TYPE USING [UniversalID];

DFSubrImpl: PROGRAM
IMPORTS CWF, DFSubr, Directory, Heap, Inline, IO, LongString, Rope, Space, 
    STPSubr, Stream, Subr
EXPORTS DFSubr, DFUser = {

-- MDS usage
stdout: IO.Handle;    -- for DFUser
nLook, nScan: CARDINAL _ 0;
-- end of MDS


TooManyEntries: PUBLIC ERROR = CODE;    -- exported to DFSubr and DFUser
RecursiveLoop: ERROR [errorDFFile: LONG STRING] = CODE;
CheckThisFile: SIGNAL [candidateDF: LONG STRING] = CODE;

FlattenDF: PUBLIC PROC[dfseq: DFSubr.DFSeq, dffilename: LONG STRING, 
    h: Subr.TTYProcs, checkForOverwrite, allowForceReadOnly, 
    setRecorder, printStatus, skipCameFrom, tryDollars: BOOL] = {
ENABLE {
    CheckThisFile => RESUME;
    RecursiveLoop => {
        CWF.WF1["Error - you have an infinite dependency chain in your DF files.  One of the DF files involved is %s.\n"L,
            errorDFFile];
        SIGNAL Subr.AbortMyself;
        };
    };
    stpStateRecord: STPSubr.StpStateRecord _ [checkForOverwrite: checkForOverwrite];
    hashTable: HashTable;
    
    InterestingNestedDF: DFSubr.InterestingNestedDFProcType = {
    dfIndex: CARDINAL _ GetDFIndex[dfseq, dfEntry];
    newUsing: DFSubr.UsingSeq _ NIL;
    sh: Stream.Handle;
    newstart: CARDINAL;
    -- using list processing
    IF driverUsingSeq ~= NIL AND innerUsingSeq ~= NIL THEN {
        -- must do intersection
        newUsing _ IntersectUsing[driverUsingSeq, innerUsingSeq];
        IF newUsing = NIL THEN RETURN;    -- no intersection
        -- newUsing should be freed
        }
    ELSE IF innerUsingSeq ~= NIL THEN {    -- driverUsingSeq = NIL
        -- this is an imported DF file with a using list
        newUsing _ CopyUsing[innerUsingSeq];
        -- allows top level Df file to be treated with
        -- a Using but without PublicOnly
        publicOnly _ FALSE;
        -- newUsing should be freed
        }
    ELSE IF driverUsingSeq ~= NIL THEN {    -- innerUsingSeq = NIL
        IF UsingEmpty[driverUsingSeq] THEN RETURN;    -- already empty
        newUsing _ driverUsingSeq;
        -- newUsing should NOT be freed
        };
    SIGNAL CheckThisFile[shortname];
    IF h.in.UserAbort[] THEN SIGNAL Subr.AbortMyself;
    -- if skipCameFrom...
    IF dfEntry ~= NIL AND skipCameFrom AND dfEntry.cameFrom THEN RETURN;    -- skip it
    IF printStatus THEN CWF.WF2["(%u#,L%u) "L, @dfIndex, @nLevel];
    -- Imports only, without using lists
    IF dfEntry ~= NIL AND dfEntry.readonly 
    AND dfEntry.publicOnly AND AlreadyAnalyzed[dfseq, dfEntry, printStatus, 
        IF ancestor = NIL THEN ""L ELSE ancestor, immediateParent,
        dfEntry.using ~= NIL, hashTable] THEN 
            RETURN;
    IF dfseq.size >= dfseq.maxsize THEN ERROR TooManyEntries;
    IF dfEntry ~= NIL THEN UpdateHashTable[hashTable, dfEntry, dfseq];
     IF printStatus THEN {
        CWF.WF4["Reading [%s]<%s>%s, ref by (%s,"L, 
            host, directory, shortname, immediateParent];
        CWF.WF1["%s).\n"L, IF ancestor = NIL THEN ""L ELSE ancestor];
        };
    [sh] _ STPSubr.CachedOpen[host: host, directory: directory, shortname: shortname, 
        version: version, wantcreatetime: createtime, h: h, 
        wantExplicitVersion: (createtime = 0 AND version > 0 AND criterion = none), 
        onlyOne: FALSE, stpState: @stpStateRecord,
        tryDollars: tryDollars
        ! Subr.FileError => {
            IF host ~= NIL THEN 
                CWF.WF3["Error - can't open [%s]<%s>%s"L,
                host, directory, shortname]
            ELSE CWF.WF1["Error - can't open %s"L, shortname];
                IF error = wrongVersion THEN 
                    CWF.WF1[" of %lt"L, @createtime];
                CWF.WF0[".\n"L];
                GOTO notfound2;
                }
            ];
    IF sh = NIL THEN {
        CWF.WF1["Warning - cannot read contents of %s.\n"L, shortname];
        RETURN;
        };
    -- allowForceReadOnly: if DF file is in ReadOnly directory, then
    -- all its contents will be ReadOnly
    -- also, only read in Public stuff if entry was {PublicOnly}
    newstart _ dfseq.size;
    DFSubr.ParseStream[sh: sh, dfseq: dfseq, dffilename: shortname, 
        using: newUsing, 
        noremoteerrors: FALSE, 
        forceReadonly: entryIsReadonly AND allowForceReadOnly, 
        omitNonPublic: publicOnly, 
        h: h,
        interestingNestedDF: InterestingNestedDF,
        nLevel: nLevel + 1, 
        ancestor: IF ancestor = NIL THEN shortname ELSE ancestor
        ! CheckThisFile =>
            IF LongString.EquivalentString[shortname, candidateDF] THEN
                ERROR RecursiveLoop[candidateDF]
        ];
    Stream.Delete[sh];
    IF setRecorder THEN 
        AssignRecorder[dfseq, newstart, shortname, 
            IF dfEntry = NIL THEN FALSE
            ELSE dfEntry.cameFrom OR dfEntry.parentCameFrom];
    IF dfEntry ~= NIL AND newUsing = NIL THEN {
        dfEntry.exportsAnalyzed _ TRUE;
        -- if Include without public only and without using list
        -- then entire contents are already analyzed
        IF NOT publicOnly AND NOT entryIsReadonly THEN
            dfEntry.includeAnalyzed _ TRUE;
        };
    IF newUsing ~= NIL AND innerUsingSeq ~= NIL THEN {
        IF NOT UsingEmpty[newUsing] THEN {
            CWF.WF0["Error - cannot find "L];
            FOR i: CARDINAL IN [0 .. newUsing.size) DO
                IF newUsing[i] = NIL THEN LOOP;
                CWF.WF1["%s "L, newUsing[i]];
                ENDLOOP;
            CWF.WF1["in any DF file nested in %s.\n"L, shortname];
            };
        FreeUsingSeq[newUsing];
        };
    EXITS
    notfound2 => CWF.WF3["Error - can't open [%s]<%s>%s.\n"L,
             host, directory, shortname];
    };
    

{
sh: Stream.Handle _ NIL;
vers: CARDINAL;
host: LONG STRING _ Subr.AllocateString[100];
directory: LONG STRING _ Subr.AllocateString[100];
shortname: LONG STRING _ Subr.AllocateString[100];
newstart: CARDINAL _ dfseq.size;
{ENABLE UNWIND => {
    Subr.FreeString[host]; Subr.FreeString[directory]; Subr.FreeString[shortname]};
vers _ StripLongName[dffilename, host, directory, shortname, FALSE];
IF NOT Subr.EndsIn[shortname, ".df"L] THEN GO TO notDF;
IF host.length = 0 AND directory.length ~= 0 THEN 
    Subr.strcpy[host, "Indigo"L];    -- defaults to Indigo
[sh] _ STPSubr.CachedOpen[host: host, directory: directory, shortname: shortname, 
    version: vers, wantcreatetime: 0, h: h, wantExplicitVersion: TRUE,
    onlyOne: FALSE, stpState: @stpStateRecord
        ! Subr.FileError => GOTO notfound1];
nScan _ nLook _ 0;    -- not properly shared
hashTable _ NEW[HashTableArray[dfseq.maxsize]];
FOR i: CARDINAL IN [0 .. hashTable.size) DO 
    hashTable[i] _ emptyHash;
    ENDLOOP;
DFSubr.ParseStream[sh: sh, dfseq: dfseq, dffilename: dffilename, using: NIL, 
    noremoteerrors: TRUE, forceReadonly: FALSE, omitNonPublic: FALSE, 
    h: h, interestingNestedDF: InterestingNestedDF, ancestor: NIL, nLevel: 0
    ! CheckThisFile => IF LongString.EquivalentString[shortname, candidateDF] THEN
    ERROR RecursiveLoop[candidateDF]
    ];
Stream.Delete[sh];
STPSubr.StopSTP[];
IF h.in.UserAbort[] THEN SIGNAL Subr.AbortMyself;
IF setRecorder THEN 
    AssignRecorder[dfseq, newstart, shortname, FALSE];
EXITS
notfound1 => CWF.WF1["Error - can't open %s.\n"L, dffilename];
notDF => CWF.WF1["Error - %s must be a DF file name.\n"L, dffilename];
}; -- of ENABLE UNWIND
Subr.FreeString[host]; Subr.FreeString[directory]; Subr.FreeString[shortname]
}};

emptyHash: CARDINAL = 64444;

HashTable: TYPE = REF HashTableArray;
HashTableArray: TYPE = RECORD[
    body: SEQUENCE size: CARDINAL OF CARDINAL
    ];
    
-- df.exportsAnalyzed means that the DF file was Imported without a Using list, and all
--    the Exports in the DF file have been analyzed already
-- df.includeAnalyzed means that the DF file was Included (w/o Using List),
--      and all the entries in the Df file have been analyzed already


-- importsWUsing must be FALSE in order to match with exportsAnalyzed
-- if importsWUsing is TRUE, then includeAnalyzed must be TRUE for success
--   (stronger condition)

AlreadyAnalyzed: PROC[dfseq: DFSubr.DFSeq, dftop: DFSubr.DF, 
    printStatus: BOOL, ancestor, immediateParent: LONG STRING, importsWUsing: BOOL,
    hashTable: HashTable] 
    RETURNS[already: BOOL] = {
    
        FoundIt: PROC[ind: CARDINAL] RETURNS[BOOL] = {
        df: DFSubr.DF _ @dfseq[ind];
        IF df.atsign 
        AND dftop.createtime = df.createtime
        AND ((df.exportsAnalyzed AND NOT importsWUsing) OR df.includeAnalyzed)
        AND LongString.EquivalentString[dftop.shortname, df.shortname]
        AND LongString.EquivalentString[dftop.directory, df.directory]
        AND LongString.EquivalentString[dftop.host, df.host]
        THEN {
            IF printStatus THEN {
                CWF.WF4["Skip [%s]<%s>%s, ref by (%s"L, 
                    dftop.host, dftop.directory,
                    dftop.shortname, immediateParent];
                CWF.WF1[",%s).\n"L, ancestor];
                };
            RETURN[TRUE];
            };
        RETURN[FALSE];
        };
        
    {
    index: CARDINAL;
    hv: CARDINAL _ Hash[dftop.shortname, hashTable.size]; -- hv IN [0 .. size[])
    FOR i: CARDINAL IN [hv .. hashTable.size) DO
        nScan _ nScan + 1;
        index _ hashTable[i];
        IF index = emptyHash THEN RETURN[FALSE];
        IF FoundIt[index] THEN RETURN[TRUE];
        ENDLOOP;
    FOR i: CARDINAL IN [0 .. hv) DO
        nScan _ nScan + 1;
        index _ hashTable[i];
        IF index = emptyHash THEN RETURN[FALSE];
        IF FoundIt[index] THEN RETURN[TRUE];
        ENDLOOP;
    ERROR;    -- hash table full, can't happen
    }};
    
Hash: PROC[shortname: LONG STRING, modulo: CARDINAL] RETURNS[hv: CARDINAL] = {
    h, i: CARDINAL _ 0;
    v: Inline.BytePair;
    IF shortname.length = 0 THEN ERROR;
    DO
        v.low _ LOOPHOLE[Rope.Lower[shortname[i]], CARDINAL];
        i _ i + 1;
        v.high _ IF i >= shortname.length THEN 0 
            ELSE LOOPHOLE[Rope.Lower[shortname[i]], CARDINAL];
        i _ i + 1;
        h _ Inline.BITXOR[h, v];
        IF i >= shortname.length THEN EXIT;
        ENDLOOP;
    hv _ h MOD modulo;
    -- debugging CWF.WF1["%d\n"L, @hv];
    };

UpdateHashTable: PROC[hashTable: HashTable, df: DFSubr.DF, dfseq: DFSubr.DFSeq] = {
    hv: CARDINAL _ Hash[df.shortname, hashTable.size];
    dfIndex: CARDINAL _ GetDFIndex[dfseq, df];
    FOR i: CARDINAL IN [hv .. hashTable.size) DO
        IF hashTable[i] = emptyHash THEN {
            hashTable[i] _ dfIndex;
            RETURN;
            };
        ENDLOOP;
    FOR i: CARDINAL IN [0 .. hv) DO
        IF hashTable[i] = emptyHash THEN {
            hashTable[i] _ dfIndex;
            RETURN;
            };
        ENDLOOP;
    ERROR;    -- full hash table (can't happen)
    };
    
-- carefully designed to work with interestingNestedDF!
AssignRecorder: PROC[dfseq: DFSubr.DFSeq, start: CARDINAL, 
    recorder: LONG STRING, parentCameFrom: BOOL] = {
df: DFSubr.DF;
FOR i: CARDINAL IN [start .. dfseq.size) DO
    df _ @dfseq[i];
    IF df.recorder = NIL THEN {
        df.recorder _ Subr.CopyString[recorder, dfseq.dfzone];
        df.parentCameFrom _ parentCameFrom;
        };
    ENDLOOP;
};


GetDFIndex: PROC[dfseq: DFSubr.DFSeq, df: DFSubr.DF] RETURNS[dfIndex: CARDINAL] = {
-- unsafe computation
dfIndex _ IF df = NIL THEN 0
    ELSE Inline.LowHalf[(df - @dfseq[0])/SIZE[DFSubr.DFFileRecord]];
};

NextDF: PUBLIC PROC[dfseq: DFSubr.DFSeq] RETURNS[df: DFSubr.DF] = {
IF dfseq.size >= dfseq.maxsize THEN {
    CWF.WF0["Error - too many files listed.\n"L];
    Subr.errorflg _ TRUE;
    df _ NIL;
    }
ELSE {
    df _ @dfseq[dfseq.size];
    df^ _ [];
    dfseq.size _ dfseq.size + 1;
    };
};

-- exported to DFUser
EnumerateEntries: PUBLIC PROC[dfFileName: LONG STRING,
    procToCall: DFUser.EnumerateProcType, nEntriesInDFFiles: CARDINAL, 
    confirmBeforeOverwriting, printProgressMessages: BOOL,
    sortOption: DFUser.SortOption, tryDollars: BOOL,
    in, out: IO.Handle, 
    confirmData: REF ANY,
    Confirm: PROC[in, out: IO.Handle, data: REF ANY, msg: Rope.ROPE, dch: CHAR]
        RETURNS[CHAR]] = {
OP: PROC[CHAR] _ NIL;
dfseq: DFSubr.DFSeq _ NIL;
df: DFSubr.DF;
includedDFFile, importedDFFile: BOOL;
h: Subr.TTYProcs _ Subr.MakeTTYProcs[in, out, confirmData, Confirm];

    {
ENABLE UNWIND => {
    STPSubr.StopSTP[];
    IF OP ~= NIL THEN [] _ CWF.SetWriteProcedure[OP];
    OP _ NIL;
    };
stdout _ out;
OP _ CWF.SetWriteProcedure[MyPutChar];
dfseq _ AllocateDFSeq[maxEntries: nEntriesInDFFiles, zoneType: huge];
-- may raise TooManyEntries
FlattenDF[dfseq: dfseq, dffilename: dfFileName, h: h, 
    checkForOverwrite: confirmBeforeOverwriting, printStatus: printProgressMessages, 
    setRecorder: TRUE, allowForceReadOnly: FALSE, skipCameFrom: FALSE,
    tryDollars: tryDollars];
IF sortOption = byShortName THEN 
    SortByFileName[dfseq, 0, dfseq.size-1, TRUE]
ELSE IF sortOption = byLongName THEN
    SortByFileName[dfseq, 0, dfseq.size-1, FALSE];
FOR i: CARDINAL IN [0 .. dfseq.size) DO
    df _ @dfseq[i];
    includedDFFile _ df.atsign AND Subr.EndsIn[df.shortname, ".df"L] 
        AND NOT df.readonly AND NOT df.publicOnly;
    importedDFFile _ df.atsign AND Subr.EndsIn[df.shortname, ".df"L] 
        AND df.readonly AND df.publicOnly;
    procToCall[df.host, df.directory, df.shortname, df.version, df.createtime, 
        includedDFFile, importedDFFile, df.readonly, df.recorder, dfseq];
    ENDLOOP;
STPSubr.StopSTP[];
IF OP ~= NIL THEN [] _ CWF.SetWriteProcedure[OP];
OP _ NIL;
}};

MyPutChar: PROC[ch: CHAR] = {
    stdout.PutChar[ch];
    };
    
-- exported to DFUser
CleanupEnumerate: PUBLIC PROC = {
Subr.SubrStop[];
};

ReadInDir: PUBLIC PROC[dfseq: DFSubr.DFSeq] = {
df: DFSubr.DF;
-- p: LONG CARDINAL;
-- p _ System.PulsesToMicroseconds[System.GetClockPulses[]];
FOR i:CARDINAL IN [0..dfseq.size) DO
    df _ @dfseq[i];
    df.presentonlocaldisk _ TRUE;
    df.cap _ Directory.Lookup[fileName: df.shortname, permissions: Directory.ignore
        ! Directory.Error => {
            df.presentonlocaldisk _ FALSE;
            CONTINUE;
            }
        ];
    ENDLOOP;
-- p _ System.PulsesToMicroseconds[System.GetClockPulses[]] - p;
-- CWF.WF1["New MicroSeconds: %lu.\n"L, @p];
-- OldReadInDir[dfseq];
};


-- if shout is ~= NIL, then this is written out to shout
-- if toplevelfile is ~= NIL, then descendents is printed out 
WriteOut: PUBLIC PROC[dfseq: DFSubr.DFSeq, topLevelFile: LONG STRING, 
    outputStream: Stream.Handle, print, altoCompatibility, wrapUsingLists: BOOL] = {
curreadonly, curpublic, p: BOOL _ FALSE;
df: DFSubr.DF;
curhost: LONG STRING _ Subr.AllocateString[40];
curdir: LONG STRING _ Subr.AllocateString[100];
curreleaseHost: LONG STRING _ Subr.AllocateString[40];
curreleaseDirectory: LONG STRING _ Subr.AllocateString[100];
sfn: LONG STRING _ Subr.AllocateString[100];
wp: PROC[ch: CHAR] = {
    IF print THEN CWF.WFC[ch];
    IF outputStream ~= NIL THEN Stream.PutChar[outputStream, ch];
    };

{ENABLE UNWIND => {
    Subr.FreeString[curhost]; Subr.FreeString[curdir];
    Subr.FreeString[curreleaseHost]; Subr.FreeString[curreleaseDirectory];
    Subr.FreeString[sfn]};

IF topLevelFile ~= NIL THEN  
    CWF.FWF1[wp,"// Mesa User Files (descendents of %s):\n"L,topLevelFile];
FOR i: CARDINAL IN [0..dfseq.size) DO
    df _ @dfseq[i];
    IF NOT p AND df.systemfile THEN {
        CWF.FWF0[wp, "// Mesa System Files:\n"L];
        p _ TRUE;
        };
    IF df.comment ~= NIL THEN CWF.FWF1[wp, "%s"L, df.comment];
    IF df.atsign THEN {
        IF df.readonly AND df.publicOnly THEN {
            PrintImports[df, wp, wrapUsingLists];
            curhost.length _ 0;
            LOOP;
            }
        ELSE IF NOT df.readonly AND NOT df.publicOnly THEN {
            PrintInclude[df, wp];
            curhost.length _ 0;
            LOOP;
            };
        };
    IF df.host ~= NIL 
    AND df.directory ~= NIL 
    AND (NOT LongString.EquivalentString[curhost, df.host]
         OR NOT LongString.EquivalentString[curdir, df.directory]
         OR curreadonly ~= df.readonly
         OR curpublic ~= df.public
         OR (df.releaseDirectory ~= NIL 
             AND NOT LongString.EquivalentString[curreleaseDirectory,
                 df.releaseDirectory])
         OR (df.releaseHost ~= NIL 
             AND NOT LongString.EquivalentString[curreleaseHost, df.releaseHost]))
     THEN {
        IF df.public THEN CWF.FWF0[wp, "Exports "L];
        IF df.readonly THEN CWF.FWF0[wp, "ReadOnly "L];
        IF altoCompatibility THEN {
            IF NOT LongString.EquivalentString[curhost, df.host] THEN
                CWF.FWF1[wp, "Host %s\n"L, df.host];
            CWF.FWF1[wp, "Directory %s"L, df.directory];
            }
        ELSE {
            IF NOT df.public AND NOT df.readonly THEN
                CWF.FWF0[wp, "Directory "L];
            CWF.FWF2[wp, "[%s]<%s>"L, df.host, df.directory];
            };
        Subr.strcpy[curhost, df.host];
        Subr.strcpy[curdir, df.directory];
        IF df.releaseDirectory ~= NIL THEN {
            CWF.FWF3[wp, "     %s [%s]<%s>"L, 
                IF df.cameFrom THEN "CameFrom"L ELSE "ReleaseAs"L,
                df.releaseHost, df.releaseDirectory];
            Subr.strcpy[curreleaseDirectory, df.releaseDirectory];
            Subr.strcpy[curreleaseHost, df.releaseHost];
            }
        ELSE {
            curreleaseDirectory.length _ 0;
            curreleaseHost.length _ 0;
            };
        CWF.FWF0[wp, "\n\n"L];
        curreadonly _ df.readonly; 
        curpublic _ df.public; 
        };
    IF df.version > 0 THEN 
        CWF.SWF2[sfn, "%s!%u"L, df.shortname, @df.version]
    ELSE Subr.strcpy[sfn, df.shortname];
    CWF.FWF0[wp, "  "L];
    IF df.topmark THEN CWF.FWF0[wp, "+"L];
    IF df.newOnly THEN CWF.FWF0[wp, "~"L];
    IF df.atsign THEN CWF.FWF0[wp, "@"L];
    IF df.publicOnly THEN CWF.FWF0[wp, "{PublicOnly}"L];
    IF sfn.length > 40 THEN CWF.FWF1[wp, "%s  "L, sfn]
    ELSE CWF.FWF1[wp, "%-40s  "L, sfn];
    IF df.createtime > 0 THEN CWF.FWF1[wp, "%lt"L, @df.createtime]
    ELSE IF df.criterion = update THEN CWF.FWF0[wp, ">"L]
    ELSE IF df.criterion = notequal THEN CWF.FWF0[wp, "~="L];
    CWF.FWFCR[wp];
    ENDLOOP;
IF dfseq.trailingcomment ~= NIL THEN 
    CWF.FWF1[wp, "%s"L, dfseq.trailingcomment];
}; -- of ENABLE UNWIND
Subr.FreeString[curhost]; Subr.FreeString[curdir];
Subr.FreeString[curreleaseHost]; Subr.FreeString[curreleaseDirectory];
Subr.FreeString[sfn];
};

PrintInclude: PROC[df: DFSubr.DF, wp: PROC[CHAR]] = {
CWF.FWF0[wp, "Include "L];
IF df.host ~= NIL AND df.host.length > 0 THEN CWF.FWF1[wp, "[%s]"L, df.host];
IF df.directory ~= NIL AND df.directory.length > 0 THEN CWF.FWF1[wp, "<%s>"L, df.directory];
CWF.FWF1[wp, "%s"L, df.shortname];
IF df.version > 0 THEN CWF.FWF1[wp, "!%u"L, @df.version];
IF df.createtime > 0 THEN CWF.FWF1[wp, "  Of %lt "L, @df.createtime]
ELSE IF df.criterion = notequal THEN CWF.FWF0[wp, " Of ~="L]
ELSE IF df.criterion = update THEN CWF.FWF0[wp, " Of >"L];
IF df.releaseHost ~= NIL THEN 
    CWF.FWF3[wp, "\n    %s [%s]<%s>"L,
        IF df.cameFrom THEN "CameFrom"L ELSE "ReleaseAs"L,
        df.releaseHost, df.releaseDirectory];
CWF.FWF0[wp, "\n"L];
-- no extra trailing \n is supplied
};

PrintImports: PROC[df: DFSubr.DF, wp: PROC[CHAR], wrapUsingLists: BOOL] = {
IF df.public THEN CWF.FWF0[wp, "Exports "L];
CWF.FWF0[wp, "Imports "L];
IF df.host ~= NIL AND df.host.length > 0 THEN CWF.FWF1[wp, "[%s]"L, df.host];
IF df.directory ~= NIL AND df.directory.length > 0 THEN CWF.FWF1[wp, "<%s>"L, df.directory];
CWF.FWF1[wp, "%s"L, df.shortname];
IF df.version > 0 THEN CWF.FWF1[wp, "!%u"L, @df.version];
IF df.createtime > 0 THEN CWF.FWF1[wp, "  Of %lt "L, @df.createtime]
ELSE IF df.criterion = notequal THEN CWF.FWF0[wp, " Of ~="L]
ELSE IF df.criterion = update THEN CWF.FWF0[wp, " Of >"L];
IF df.releaseHost ~= NIL THEN 
    CWF.FWF3[wp, "\n    %s [%s]<%s>"L,
        IF df.cameFrom THEN "CameFrom"L ELSE "ReleaseAs"L,
        df.releaseHost, df.releaseDirectory];
CWF.FWF0[wp, "\n"L];
IF df.using ~= NIL THEN PrintUsing[df.using, wp, wrapUsingLists];
-- no extra trailing \n is supplied
};

MAXLINE: CARDINAL = 65;

PrintUsing: PROC[usingseq: DFSubr.UsingSeq, wp: PROC[CHAR], wrapUsingLists: BOOL] = {
lineposn: CARDINAL _ 0;
prefix: STRING _ "\n       "L;
p: BOOL _ FALSE;
CWF.FWF0[wp, "    Using ["L];
lineposn _ 10;
FOR i: CARDINAL IN [0 .. usingseq.size) DO
    IF p THEN {
        lineposn _ lineposn + 2;
        CWF.FWF0[wp, ", "L];
        IF lineposn > MAXLINE AND wrapUsingLists THEN {
            CWF.FWF0[wp, prefix];
            lineposn _ prefix.length;
            };
        };
    p _ TRUE;
    CWF.FWF1[wp, "%s"L, usingseq[i]];
    lineposn _ lineposn + usingseq[i].length;
    ENDLOOP;
CWF.FWF0[wp, "]\n"L];
};

AppendToUsingSeq: PUBLIC PROC[oldusing: DFSubr.UsingSeq, shortname: LONG STRING,
    zone: UNCOUNTED ZONE] RETURNS[newusing: DFSubr.UsingSeq] = {
IF oldusing = NIL THEN {
    newusing _ zone.NEW[DFSubr.UsingSeqRecord[20]];
    newusing.zone _ zone;
    }
ELSE IF oldusing.size >= oldusing.maxsize THEN {
    oldzone: UNCOUNTED ZONE;
    newusing _ zone.NEW[DFSubr.UsingSeqRecord[oldusing.size+20]];
    newusing.zone _ zone;
    newusing.size _ oldusing.size;
    FOR i: CARDINAL IN [0 .. oldusing.size) DO
        newusing[i] _ oldusing[i];
        ENDLOOP;
    oldzone _ oldusing.zone;
    oldzone.FREE[@oldusing];
    }
ELSE newusing _ oldusing;
newusing[newusing.size] _ Subr.CopyString[shortname, newusing.zone];
newusing.size _ newusing.size + 1;
};

-- limiter is never changed
-- driver has entry removed for each that is added to newusing
IntersectUsing: PUBLIC PROC[driver, limiter: DFSubr.UsingSeq] RETURNS[newusing: DFSubr.UsingSeq] = {
newusing _ NIL;
FOR i: CARDINAL IN [0 .. driver.size) DO
    IF driver[i] = NIL THEN LOOP;
    FOR j: CARDINAL IN [0 .. limiter.size) DO
        IF LongString.EquivalentString[driver[i], limiter[j]] THEN {
            newusing _ AppendToUsingSeq[newusing, driver[i], driver.zone];
            Subr.FreeString[driver[i], driver.zone];
            driver[i] _ NIL;
            EXIT;
            };
        ENDLOOP;
    ENDLOOP;
};

UsingEmpty: PUBLIC PROC[usingseq: DFSubr.UsingSeq] RETURNS[empty: BOOL] = {
IF usingseq = NIL THEN RETURN[TRUE];
FOR i: CARDINAL IN [0 .. usingseq.size) DO
    IF usingseq[i] ~= NIL THEN RETURN[FALSE];
    ENDLOOP;
RETURN[TRUE];
};

-- may return NIL if limiter is empty
CopyUsing: PUBLIC PROC[limiter: DFSubr.UsingSeq] RETURNS[newusing: DFSubr.UsingSeq] = {
newusing _ NIL;
FOR i: CARDINAL IN [0 .. limiter.size) DO
    newusing _ AppendToUsingSeq[newusing, limiter[i], limiter.zone];
    ENDLOOP;
};

-- allocation/ deallocation

AllocateDFSeq: PUBLIC PROC[maxEntries: CARDINAL, zoneType: DFSubr.ZoneType] 
    RETURNS[dfseq: DFSubr.DFSeq] =
    {
    zone: UNCOUNTED ZONE;
    IF zoneType = huge THEN 
        zone _ Subr.HugeZone[]
    ELSE IF zoneType = single THEN {
        space: Space.Handle _ Space.Create[size: 256, parent: Space.virtualMemory];
        zone _ Heap.Create[initial: 30, increment: 20, parent: space];
        }
    ELSE
        zone _ Subr.LongZone[];
    dfseq _ AllocSpecialSeq[maxEntries, zoneType, zone];
    };

AllocSpecialSeq: PROC[maxEntries: CARDINAL, zoneType: DFSubr.ZoneType, zone: UNCOUNTED ZONE] 
    RETURNS[dfseq: DFSubr.DFSeq] = {
nwords: LONG CARDINAL;
nwords _ (LONG[SIZE[DFSubr.DFFileRecord]] * maxEntries + SIZE[DFSubr.DFSeqRecord[0]]);
IF zoneType = huge THEN 
    dfseq _ Subr.WordsFromHugeZone[zone, nwords]
ELSE {
    space: Space.Handle;
    npages: CARDINAL _ Inline.LowHalf[nwords/Environment.wordsPerPage + 1];
    space _ Space.Create[size: npages, parent: Space.virtualMemory];
    IF npages >= 200 THEN {
        -- creation of subspaces helps Pilot get unused swap units out faster
        FOR i: CARDINAL IN [0 .. npages/100] DO
            subSpace: Space.Handle _ Space.Create[size: MIN[100, npages - i*100],
                parent: space, base: i*100];
            Space.CreateUniformSwapUnits[10, subSpace];
            ENDLOOP;
        }
    ELSE {
        Space.Map[space];
        IF npages > 20 THEN Space.CreateUniformSwapUnits[10, space];
        };
    dfseq _ Space.LongPointer[space];
    };
-- assign to the MAX SIZE !!!!
(LOOPHOLE[dfseq, LONG POINTER] + SIZE[DFSubr.DFSeqRecord[0]] - 1)^ _ maxEntries;
dfseq.dfzone _ zone;
dfseq.zoneType _ zoneType;
dfseq.size _ 0;
dfseq.trailingcomment _ NIL;
IF zoneType = huge THEN {
    dfseq.ivyHost _ Subr.CopyString["Ivy"L, zone];
    dfseq.indigoHost _ Subr.CopyString["Indigo"L, zone];
    }
ELSE dfseq.ivyHost _ dfseq.indigoHost _ NIL;
};


FreeDFSeq: PUBLIC PROC[pdfseq: POINTER TO DFSubr.DFSeq] = {
df: DFSubr.DF;
zone: UNCOUNTED ZONE;
IF pdfseq^ = NIL THEN RETURN;
IF pdfseq.zoneType = huge THEN {
    pdfseq^ _ NIL;    -- can't free anything
    RETURN;
    };
zone _ pdfseq.dfzone;
FOR i: CARDINAL IN [0.. pdfseq.size) DO
    df _ @pdfseq[i];
    IF df.directory ~= NIL THEN
        Subr.FreeString[df.directory, zone];
    IF df.shortname ~= NIL THEN
        Subr.FreeString[df.shortname, zone];
    IF df.host ~= NIL THEN 
        Subr.FreeString[df.host, zone];
    IF df.releaseHost ~= NIL THEN 
        Subr.FreeString[df.releaseHost, zone];
    IF df.releaseDirectory ~= NIL THEN 
        Subr.FreeString[df.releaseDirectory, zone];
    IF df.comment ~= NIL THEN 
        Subr.FreeString[df.comment, zone];
    IF df.recorder ~= NIL THEN 
        Subr.FreeString[df.recorder, zone];
    IF df.using ~= NIL THEN FreeUsingSeq[df.using];
    ENDLOOP;
IF pdfseq.trailingcomment ~= NIL THEN 
    Subr.FreeString[pdfseq.trailingcomment, zone];
IF pdfseq.zoneType = single THEN {
    -- must free the heap too!
    deleteAgain: BOOL _ FALSE;
    space: Space.Handle;
    [parent: space] _ Heap.GetAttributes[pdfseq.dfzone ! Heap.Error => CONTINUE];
    Heap.Delete[z: pdfseq.dfzone, checkEmpty: TRUE
         ! Heap.Error => {
             IF type = invalidHeap THEN {
                deleteAgain _ TRUE;
                CWF.WF0["Schmidt's debugging: Single Heap not empty.\n"L];
                };
            CONTINUE
            }
        ];
    IF deleteAgain THEN 
        Heap.Delete[z: pdfseq.dfzone, checkEmpty: FALSE
            ! Heap.Error => CONTINUE];
    Space.Delete[space: space ! Space.Error => CONTINUE];
    };
Subr.SpaceZone[].FREE[pdfseq];
};

FreeUsingSeq: PUBLIC PROC[using: DFSubr.UsingSeq] = {
zone: UNCOUNTED ZONE;
IF using = NIL THEN RETURN;
zone _ using.zone;
FOR i: CARDINAL IN [0 .. using.size) DO
    Subr.FreeString[using[i], zone];
    ENDLOOP;
zone.FREE[@using];
};


-- fullname is readonly
-- any of host, directory, short may be NIL
-- if mustbedir is TRUE then if long does not end in a '>
-- the tail is assumed to be part of the directory, not the short,
-- e.g. "schmidt>pilot" is all a directory if mustbedir is TRUE

StripLongName: PUBLIC PROC[fullname, host, directory, short: LONG STRING, 
    mustbedir: BOOL] RETURNS[version: CARDINAL _ 0] = {
last, bot: CARDINAL;
first: INTEGER;
stemp, long: LONG STRING _ NIL;    -- long has host name stripped off

IF host ~= NIL THEN host.length _ 0;
IF directory ~= NIL THEN directory.length _ 0;
IF short ~= NIL THEN short.length _ 0;
IF fullname.length = 0 THEN RETURN;
stemp _ Subr.AllocateString[100];
long _ Subr.AllocateString[100];    -- long has host name stripped off
{ENABLE UNWIND =>
    {Subr.FreeString[stemp]; Subr.FreeString[long]};
    Subr.strcpy[long, fullname];
IF host ~= NIL AND long[0] = '[ THEN {
    i: CARDINAL _ 1;
    WHILE i < long.length AND long[i] ~= '] AND i < host.maxlength DO
        LongString.AppendChar[host, long[i]];    -- host is actually indexed by -1
        i _ i + 1;
        ENDLOOP;
    IF i >= long.length OR i >= host.maxlength THEN {
        CWF.WF1["Error - missing ']': %s.\n"L, long];
        version _ 0;
        GO TO return;        -- this will leave short.length = 0
        };
    Subr.SubStrCopy[long, long, i + 1];
    };
last _ long.length - 1;
WHILE last > 0 AND long[last] IN ['0 .. '9] DO
    last _ last  - 1;
    ENDLOOP;
-- last points to '!, '; or the end of the file name (= long.length - 1)
IF last < long.length - 1 AND (long[last] = '! OR long[last] = ';)  THEN {
    Subr.SubStrCopy[stemp, long, last+1];
    version _ LongString.StringToDecimal[stemp];
    last _ last - 1;
    }
ELSE {
    last _ long.length - 1;    -- in case the filename ended in a number
    version _ 0;
    };
-- last is now char before !, ;, or end of filename
first _ last;
WHILE first >= 0 AND (long[first] ~= '> AND long[first] ~= '<) DO
    first _ first - 1;
    ENDLOOP;
IF first > 0 THEN first _ first + 1;
IF first < 0 THEN first _ 0;
bot _ IF mustbedir THEN last+1 ELSE first;
-- bot is the first char of the short name
IF short ~= NIL THEN {
    FOR i: CARDINAL IN [bot .. last] DO
        LongString.AppendChar[short, long[i]];
        ENDLOOP;
    };
IF directory ~= NIL THEN {
    Subr.strcpy[directory, long];
    directory.length _ bot;
    IF bot > 0 THEN {
        IF directory[bot-1] = '> THEN 
            directory.length _ directory.length - 1;
        IF directory[0] = '< THEN 
            Subr.SubStrCopy[directory, directory, 1];
        };
    };
EXITS return => {};
}; -- of ENABLE UNWIND
Subr.FreeString[stemp]; Subr.FreeString[long];
}; -- of StripLongName

LookupDF: PUBLIC PROC[dfseq: DFSubr.DFSeq, shortname: LONG STRING] RETURNS[df: DFSubr.DF] ={
FOR i: CARDINAL IN [0.. dfseq.size) DO
    df _ @dfseq[i];
    IF df.shortname ~= NIL
    AND LongString.EquivalentString[df.shortname, shortname] THEN
        RETURN[df];
    ENDLOOP;
RETURN[NIL];
};

InsertCRs: PUBLIC PROC[dfseq: DFSubr.DFSeq] = {
df: DFSubr.DF;
crline: STRING _ "\n";
curhost: LONG STRING _ Subr.AllocateString[40];
curdir: LONG STRING _ Subr.AllocateString[100];
{ENABLE UNWIND =>
    {Subr.FreeString[curhost]; Subr.FreeString[curdir]};
FOR i: CARDINAL IN [0 .. dfseq.size) DO
    df _ @dfseq[i];
    IF df.host ~= NIL 
    AND NOT LongString.EquivalentString[curhost, df.host] THEN {
        Subr.strcpy[curhost, df.host];
        IF df.comment = NIL THEN df.comment _ Subr.CopyString[crline, dfseq.dfzone];
        };
    IF df.directory ~= NIL 
    AND NOT LongString.EquivalentString[curdir, df.directory] THEN {
        Subr.strcpy[curdir, df.directory];
        IF df.comment = NIL THEN df.comment _ Subr.CopyString[crline, dfseq.dfzone];
        };
    ENDLOOP;
IF dfseq.trailingcomment = NIL THEN 
    dfseq.trailingcomment _ Subr.CopyString[crline, dfseq.dfzone];
}; -- of ENABLE UNWIND
Subr.FreeString[curhost]; Subr.FreeString[curdir];
}; -- of InsertCRs

-- ignorehostanddir means that shortname has highest precedence
CompareDFs: PUBLIC PROC[dfleft, dfright: DFSubr.DF, 
    ignorehostanddir: BOOL] RETURNS[res: INTEGER] = {
    res _ 0;
    IF dfleft.shortname = NIL OR dfright.shortname = NIL THEN RETURN[0];
    IF ignorehostanddir THEN {-- shortname, then directory, then host
        res _ LongString.CompareStrings[dfleft.shortname,dfright.shortname, TRUE];
        IF res ~= 0 THEN RETURN[res];
        IF dfleft.directory ~= NIL AND dfright.directory ~= NIL THEN
            res _ LongString.CompareStrings[dfleft.directory, 
                dfright.directory, TRUE];
        IF res ~= 0 THEN RETURN[res];
        IF dfleft.host ~= NIL AND dfright.host ~= NIL THEN
            res _ LongString.CompareStrings[dfleft.host, dfright.host, TRUE];
        RETURN[res];
        }
    ELSE {    -- host first, then directory, then shortname
        IF dfleft.host ~= NIL AND dfright.host ~= NIL THEN
            res _ LongString.CompareStrings[dfleft.host, dfright.host, TRUE];
        IF res ~= 0 THEN RETURN[res];
        IF dfleft.directory ~= NIL AND dfright.directory ~= NIL THEN
            res _ LongString.CompareStrings[dfleft.directory, 
                dfright.directory, TRUE];
        IF res ~= 0 THEN RETURN[res];
        RETURN[LongString.CompareStrings[dfleft.shortname,dfright.shortname, TRUE]];
        };
    };

SortByCap: PUBLIC PROC[dfseq: DFSubr.DFSeq, min, max: CARDINAL, 
    ignorehostanddir: BOOL]={

    CapLessThan: PROC[left, right: CARDINAL] RETURNS [BOOL] = {
    l,r: LONG POINTER TO SystemInternal.UniversalID;
    l _ LOOPHOLE[@dfseq[left].cap];
    r _ LOOPHOLE[@dfseq[right].cap];
    RETURN[l.sequence < r.sequence];
    };

IF min = 0 THEN 
    TreeSort[dfseq, min, max, CapLessThan]
ELSE     -- because of bugs in TreeSort
    BubbleSort[dfseq, min, max, CapLessThan];
};

SortByFileName: PUBLIC PROC[dfseq: DFSubr.DFSeq, min, max: CARDINAL, 
    ignorehostanddir: BOOL]={

    FileNameLessThan: PROC[left, right: CARDINAL] RETURNS [BOOL] = {
    RETURN[CompareDFs[@dfseq[left], @dfseq[right], ignorehostanddir] < 0];
    };

IF min = 0 THEN 
    TreeSort[dfseq, min, max, FileNameLessThan]
ELSE     -- because of bugs in TreeSort
    BubbleSort[dfseq, min, max, FileNameLessThan];
};

BubbleSort: PROC[dfseq: DFSubr.DFSeq, min, max: INTEGER, 
    LessThan: PROC[CARDINAL, CARDINAL] RETURNS[BOOL]] = {
FOR i: INTEGER IN [min .. max) DO
    FOR j: INTEGER IN [i+1 .. max] DO
        IF LessThan[j,i] THEN Exch[dfseq, i, j];
        ENDLOOP;
    ENDLOOP;
};

TreeSort: PROC[dfseq: DFSubr.DFSeq, min, max: INTEGER, 
    LessThan: PROC[CARDINAL, CARDINAL] RETURNS[BOOL]] = {
left, right: CARDINAL;
i: INTEGER;

    siftUp: PROC[low, high: INTEGER] ={
    k, son: INTEGER;
    left, right: INTEGER;
    k _ low;
    DO
        IF 2*k>high THEN EXIT;
        left _ 2*k+1-1;
        right _ 2*k-1;
        IF 2*k+1>high OR LessThan[left, right] THEN
            son _ 2*k
        ELSE
            son _ 2*k+1;
        left _ son-1;
        right _ k-1;
        IF LessThan[left, right] THEN EXIT;
        Exch[dfseq, left, right];
        k _ son;
        ENDLOOP;
    };

FOR i DECREASING IN [min+1..(max+1)/2] DO
    siftUp[i,max+1]
    ENDLOOP;
FOR i DECREASING IN [min+1..max] DO
    left _ min;
    right _ i;
    Exch[dfseq, left, right];
    siftUp[min+1,i]
    ENDLOOP;
};

-- exchange i and j
Exch: PROC[dfseq: DFSubr.DFSeq, i, j: CARDINAL] = {
df1, df2, df3: DFSubr.DF;
dft: DFSubr.DFFileRecord;
df1 _ @dfseq[i];
df2 _ @dfseq[j];
df3 _ @dft;
df3^ _ df1^;
df1^ _ df2^;
df2^ _ df3^;
};

}.



AlreadyAnalyzed: PROC[dfseq: DFSubr.DFSeq, dftop: DFSubr.DF, dfIndex: CARDINAL,
    printStatus: BOOL, ancestor, immediateParent: LONG STRING, importsWUsing: BOOL] 
    RETURNS[already: BOOL] = {
df: DFSubr.DF;
FOR i: CARDINAL IN [0 .. dfIndex) DO
    df _ @dfseq[i];
    IF df.atsign 
    AND dftop.createtime = df.createtime
    AND ((df.exportsAnalyzed AND NOT importsWUsing) OR df.includeAnalyzed)
    AND LongString.EquivalentString[dftop.shortname, df.shortname]
    AND LongString.EquivalentString[dftop.directory, df.directory]
    AND LongString.EquivalentString[dftop.host, df.host]
    THEN {
        IF printStatus THEN {
            CWF.WF4["Skip [%s]<%s>%s, ref by (%s"L, 
                dftop.host, dftop.directory,
                dftop.shortname, immediateParent];
            CWF.WF1[",%s).\n"L, ancestor];
            };
        RETURN[TRUE];
        };
    ENDLOOP;
RETURN[FALSE];
};