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