-- DFSubrImpl.Mesa, last edit February 28, 1983 5:05 pm
-- 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],
  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],
  String: TYPE USING [StringToDecimal],
  Subr: TYPE USING [AbortMyself, 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, String, 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: STRING ← [100];
directory: STRING ← [100];
shortname: STRING ← [100];
newstart: CARDINAL ← dfseq.size;

vers ← StripLongName[dffilename, host, directory, shortname, FALSE];
IF NOT Subr.EndsIn[shortname, ".df"L] THEN {
	CWF.WF1["Error - %s must be a DF file name.\n"L, dffilename];
	RETURN;
	};
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];
}};

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: STRING, 
	outputStream: Stream.Handle, print, altoCompatibility, wrapUsingLists: BOOL] = {
curhost: STRING ← [40];
curdir: STRING ← [100];
curreleaseDirectory: STRING ← [100];
curreleaseHost: STRING ← [40];
curreadonly, curpublic, p: BOOL ← FALSE;
sfn: STRING ← [100];
df: DFSubr.DF;

	wp: PROC[ch: CHAR] = {
	IF print THEN CWF.WFC[ch];
	IF outputStream ~= NIL THEN Stream.PutChar[outputStream, ch];
	};

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

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

-- msy raise String.InvalidNumber
StripLongName: PUBLIC PROC[fullname, host, directory, short: LONG STRING, 
	mustbedir: BOOL] RETURNS[version: CARDINAL] = {
last, bot: CARDINAL;
first: INTEGER;
stemp: STRING ←  [100];
long: STRING ← [100];	-- 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[0];
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];
		RETURN[0];		-- 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 ← String.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];
		};
	};
};

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;
curhost: STRING ← [40];
curdir: STRING ← [40];
crline: STRING ← [2];
crline[0] ← '\n;
crline.length ← 1;
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];
};

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