InternalRCMapBuilderImpl.mesa
Copyright © 1984, 1985 by Xerox Corporation. All rights reserved.
Satterthwaite On May 21, 1986 10:28:50 am PDT
Levin, August 8, 1983 4:06 pm
Paul Rovner On September 19, 1983 9:31 pm
Russ Atkinson On February 19, 1985 6:05:17 pm PST
Willie-Sue, July 15, 1986 1:17:48 pm PDT
DIRECTORY
Basics: TYPE USING [bitsPerWord],
Symbols: TYPE USING [Base, Limit, SERecord, Type, TypeClass, CSEIndex, ArraySEIndex, RecordSEIndex, ISEIndex, CSENull, ISENull, CTXRecord, CTXIndex, CTXNull, nullName, BitAddress, MDIndex],
SymbolTable: TYPE USING [Base],
PrincOpsUtils: TYPE USING [LongCopy],
RCMap: TYPE,
RCMapOps: TYPE USING [MapMapItem, MapMapObj, MapMap, OuterProc],
VM: TYPE USING [wordsPerPage, Allocate, Free, PageNumberForAddress, AddressForPageNumber];
InternalRCMapBuilderImpl: PROGRAM
IMPORTS PrincOpsUtils, VM
EXPORTS RCMapOps = {
OPEN Symbols, RCMap;
bitsPerWord: NAT = Basics.bitsPerWord;
Types
No: TYPE = BOOL←FALSE;  -- for enumerators
UnionSEIndex: TYPE = Symbols.Base RELATIVE POINTER [0..Symbols.Limit)
TO SERecord.cons.union;
SequenceSEIndex: TYPE = Symbols.Base RELATIVE POINTER [0..Symbols.Limit)
TO SERecord.cons.sequence;
RCMapTable: PUBLIC TYPE = RECORD[
basic state
base: Base←NIL,
x: INT𡤀,   -- number of words in use
outer: OuterProc←NIL,
expansion information
expandable: BOOL←FALSE,
limit: INT𡤀,  -- number of words allocated (= pages*wordsPerPage)
pages: INT𡤀,
zone: UNCOUNTED ZONE←
];
RCMT: TYPE = LONG POINTER TO RCMapTable;
Handle: TYPE = RECORD[base: Base, index: Index];
MapMapItem: TYPE = RCMapOps.MapMapItem;
MapMapObj: TYPE = RCMapOps.MapMapObj;
MapMap: TYPE = RCMapOps.MapMap;
OuterProc: TYPE = RCMapOps.OuterProc;
Errors
TooManyRCMaps: ERROR = CODE;
NIY: ERROR[kind: {packedComponent, computedTag, nakedSeq}] = CODE;
GetOuter: SIGNAL RETURNS[OuterProc];
PUBLIC PROCS
Create: PUBLIC PROC[
zone: UNCOUNTED ZONE,
ptr: Base, nPages: CARDINAL, outerProc: OuterProc←NIL,
expansionOK: BOOL←FALSE]
RETURNS[rcmt: RCMT] = {
rcmt ← zone.NEW[RCMapTable ← [
base: ptr, --ASSUME allocated by VM.Allocate--
x: 0,
outer: outerProc,
expandable: expansionOK,
pages: nPages,
limit: nPages*VM.wordsPerPage,
zone: zone]];
IF rcmt.limit < 3 THEN ExpandRCMSpace[rcmt];
make standard entries
rcmt.base[nullIndex] ← [null[]];
rcmt.base[refIndex] ← [ref[]];
rcmt.base[controlLinkIndex] ← [controlLink[]];
rcmt.x ← 3};
Destroy: PUBLIC PROC[rcmt: RCMT] RETURNS[RCMT] = {
zone: UNCOUNTED ZONE = rcmt.zone;
IF rcmt.base # NIL THEN
VM.Free[[page: VM.PageNumberForAddress[rcmt.base], count: rcmt.pages]];
zone.FREE[@rcmt];
RETURN[NIL]};
GetSpan: PUBLIC PROC[rcmt: RCMT] RETURNS[base: Base, size: CARDINAL] = {
RETURN[rcmt.base, rcmt.x]};
Acquire: PUBLIC PROC[rcmt: RCMT, stb: SymbolTable.Base, type: Type] RETURNS[Index] = {
RETURN[DoAcquire[rcmt, stb, type ! GetOuter => {RESUME[rcmt.outer]}]]};
DoAcquire: PROC[rcmt: RCMT, stb: SymbolTable.Base, type: Type] RETURNS[Index] = {
csei: CSEIndex = stb.UnderType[type];
RETURN[WITH cse~~stb.seb[csei] SELECT FROM
record => RCMapForRecord[rcmt, stb, LOOPHOLE[csei, RecordSEIndex]],
array => RCMapForArray[rcmt, stb, LOOPHOLE[csei, ArraySEIndex]],
sequence => RCMapForSequence[rcmt, stb, LOOPHOLE[csei, SequenceSEIndex]],
union => RCMapForUnion[rcmt, stb, LOOPHOLE[csei, UnionSEIndex]],
zone => (IF cse.counted THEN refIndex ELSE nullIndex),
long => DoAcquire[rcmt, stb, cse.rangeType],
ref => (IF cse.counted THEN refIndex ELSE nullIndex),
ENDCASE => nullIndex]
};
Include: PUBLIC PROC[
rcmt: RCMT, rcmb: Base, size: CARDINAL, zone: UNCOUNTED ZONE←NIL]
RETURNS[mm: MapMap ← NIL] = {
ENABLE GetOuter => {RESUME[rcmt.outer]};
mmEntries, mmNext: CARDINAL ← 0;
Count: PROC[Index] RETURNS[stop: No] = {mmEntries ← mmEntries + 1};
Include: PROC[index: Index] RETURNS[stop: No] = {
mmi: MapMapItem = [old: index, new: MapRCMIndex[rcmt, [rcmb, index]]];
IF mm # NIL THEN mm[mmNext] ← mmi;
mmNext ← mmNext + 1};
IF zone # NIL THEN {
[] ← DoEnumerate[rcmb, size, Count];
mm ← zone.NEW[MapMapObj[mmEntries]]};
[] ← DoEnumerate[rcmb, size, Include]};
FindMapMapEntry: PUBLIC PROC[mapMap: MapMap, oldIndex: Index] RETURNS[Index] = {
FOR i: CARDINAL IN [0..mapMap.length) DO
IF mapMap[i].old = oldIndex THEN RETURN[mapMap[i].new]
ENDLOOP;
RETURN[invalidIndex]};
Enumerate: PUBLIC PROC[
base: RCMap.Base, limit: CARDINAL, proc: PROC[Index] RETURNS[stop: BOOL]]
RETURNS[stopped: BOOL] =
DoEnumerate;
DoEnumerate: PROC[
base: RCMap.Base, limit: CARDINAL, proc: PROC[Index] RETURNS[stop: BOOL]]
RETURNS[stopped: BOOL ← FALSE] = {
FOR rcmi: Index ← Index.FIRST, rcmi + InlineSize[[base, rcmi]]
UNTIL LOOPHOLE[rcmi, CARDINAL] >= limit DO
IF Complete[[base, rcmi]] AND proc[rcmi] THEN RETURN[TRUE];
ENDLOOP
};
FOR DEBUGGING
NextRCMap: SIGNAL = CODE;
ListRCMaps: PROC[rcmt: RCMT] = {
p: PROC[index: Index] RETURNS[stop: No] = {SIGNAL NextRCMap};
[] ← DoEnumerate[rcmt.base, rcmt.x, p]};
Complete: PROC[h: Handle] RETURNS[BOOL] = INLINE {
RETURN[WITH rcmr~~h.base[h.index] SELECT FROM
null => TRUE,
ref => TRUE,
controlLink => TRUE,
oneRef => TRUE,
simple => TRUE,
nonVariant => rcmr.complete,
variant => rcmr.complete,
array => TRUE,
sequence => TRUE,
ENDCASE => ERROR]
};
first level utility PROCs for constructing RCMap Objects
NewSeqRCM: PROC[rcmt: RCMT] RETURNS[ans: SeqIndex] = {
ans ← LOOPHOLE[AllocRCMap[rcmt, Object.sequence.SIZE]];
rcmt.base[ans] ← [sequence[]]};
SimpleRCM: TYPE = UNSPECIFIED;
any of Object.null, Object.ref, Object.simple, Object.oneRef (Object.SIZE = 1)
InstallSimpleRCM: PROC[rcmt: RCMT, srcm: SimpleRCM] RETURNS[ans: Index] = {
proc: PROC[rcmi: Index] RETURNS[stop: BOOL] = {
stop ← (WITH rcm~~rcmt.base[rcmi] SELECT FROM
simple => (srcm = rcm),
oneRef => (srcm = rcm),
ENDCASE => FALSE);
IF stop THEN ans ← rcmi};
IF LOOPHOLE[srcm, Object.null].type = $null THEN RETURN[nullIndex];
IF LOOPHOLE[srcm, Object.ref].type = $ref THEN RETURN[refIndex];
IF DoEnumerate[rcmt.base, rcmt.x, proc].stopped THEN RETURN[ans];
ans ← AllocRCMap[rcmt, Object.simple.SIZE]; -- or any variant with size = 1
rcmt.base[LOOPHOLE[ans, SimpIndex]] ← srcm};
RCMapForRecord: PROC[rcmt: RCMT, stb: SymbolTable.Base, rsei: RecordSEIndex]
RETURNS[Index] = {
RETURN[SELECT TRUE FROM
~stb.seb[rsei].hints.refField => nullIndex,
stb.seb[rsei].hints.variant => RCMapForVRecord[rcmt, stb, rsei],
ENDCASE => RCMapForNVRecord[rcmt, stb, rsei]]
};
RCMapForArray: PROC[rcmt: RCMT, stb: SymbolTable.Base, asei: ArraySEIndex]
RETURNS[Index] = {
componentType: Type = stb.seb[asei].componentType;
IF IsRC[stb, componentType] THEN {
oldx: CARDINAL = rcmt.x;
ercmi: Index = DoAcquire[rcmt, stb, componentType];
NewARCM: PROC RETURNS[ans: AIndex] = INLINE {
ans ← LOOPHOLE[AllocRCMap[rcmt, Object.array.SIZE]];
rcmt.base[ans] ← [array[]]};
arcmi: AIndex = NewARCM[];
simpRCM: SimpleRCM;
simplified: BOOL;
IF stb.seb[asei].packed THEN ERROR NIY[$packedComponent];
rcmt.base[arcmi] ← [array[
wordsPerElement: stb.WordsForType[componentType],
nElements: stb.Cardinality[stb.seb[asei].indexType],
rcmi: ercmi]];
[simpRCM, simplified] ← SimplifyRCM[[rcmt.base, arcmi]];
IF simplified THEN {rcmt.x ← oldx; RETURN[InstallSimpleRCM[rcmt, simpRCM]]}
ELSE {
found: BOOL; x: Index;
[found, x] ← FindRCMap[rcmt.base, [rcmt.base, arcmi], oldx];
IF found THEN {rcmt.x ← oldx; RETURN[x]} ELSE RETURN[arcmi]}}
ELSE RETURN[nullIndex]};
RCMapForSequence: PROC[rcmt: RCMT, stb: SymbolTable.Base, seqsei: SequenceSEIndex]
RETURNS[Index] = {
componentType: Type = stb.seb[seqsei].componentType;
NOTE unlike unions, there is no way to get back to the enclosing record type
IF TRUE THEN ERROR NIY[$nakedSeq];
IF IsRC[stb, componentType] THEN {
oldx: CARDINAL = rcmt.x;
tagSei: ISEIndex = stb.seb[seqsei].tagSei;
ercmi: Index = DoAcquire[rcmt, stb, componentType];
seqrcmi: SeqIndex = NewSeqRCM[rcmt];
found: BOOL; x: Index;
IF ~stb.seb[seqsei].controlled THEN ERROR NIY[$computedTag];
IF stb.seb[seqsei].packed THEN ERROR NIY[$packedComponent];
rcmt.base[seqrcmi] ← [sequence[
wordsPerElement: stb.WordsForType[componentType],
fdLength: [
wordOffset: 0,
bitFirst: stb.seb[tagSei].idValue MOD bitsPerWord,
bitCount: stb.seb[tagSei].idInfo],
commonPart: nullIndex,
dataOffset: (stb.seb[tagSei].idValue + stb.seb[tagSei].idInfo)/bitsPerWord,
rcmi: ercmi]];
[found, x] ← FindRCMap[rcmt.base, [rcmt.base, seqrcmi], oldx];
IF found THEN {rcmt.x ← oldx; RETURN[x]} ELSE RETURN[seqrcmi]}
ELSE RETURN[nullIndex]};
RCMapForUnion: PROC[rcmt: RCMT, stb: SymbolTable.Base, usei: UnionSEIndex]
RETURNS[rcmi: Index ← invalidIndex] = {
IF stb.seb[usei].hints.refField THEN {
GetRCMX: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL] = {
get the rcmi for the enclosing record
rcsei: CSEIndex = stb.UnderType[stb.TypeLink[isei]];
NOTE offset, inclusion of common parts
rcmi ← RCMapForRecord[rcmt, stb, LOOPHOLE[rcsei, RecordSEIndex]];
RETURN[TRUE]}; -- stop the enumeration
nVariants: CARDINAL = stb.Cardinality[stb.seb[stb.seb[usei].tagSei].idType];
caseCtx: CTXIndex = stb.seb[usei].caseCtx;
[] ← EnumerateCtxIseis[stb, caseCtx, GetRCMX, (nVariants=stb.CtxEntries[caseCtx])];
IF rcmi = invalidIndex THEN ERROR}
ELSE rcmi ← nullIndex;
RETURN};
RCMapForNVRecord: PROC[rcmt: RCMT, stb: SymbolTable.Base, rsei: RecordSEIndex]
RETURNS[Index] = {
nc: CARDINAL = CountRCCommonComponents[stb, rsei];
IF nc # 0 THEN {
oldx: CARDINAL = rcmt.x;
NewNVRCM: PROC[nComponents: [0..componentMaxIndex]]
RETURNS[ans: NVIndex] = INLINE {
ans ← LOOPHOLE[AllocRCMap[rcmt, Object.nonVariant.SIZE + nComponents*RCField.SIZE]];
rcmt.base[ans] ← [nonVariant[nComponents: nComponents, components: TRASH]];
FOR i: CARDINAL IN [0..nComponents) DO
rcmt.base[ans].components[i] ← []; ENDLOOP; -- LOOPHOLE
};
nvrcmi: NVIndex = NewNVRCM[nc];
argrec: BOOL = stb.seb[rsei].argument;
n: CARDINAL ← 0;
Stuff: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: No] = {
type: Type = stb.seb[isei].idType;
FieldOffset: PROC[isei: ISEIndex] RETURNS[BitAddress] = INLINE {
RETURN[IF argrec THEN stb.FnField[isei].offset ELSE stb.seb[isei].idValue]};
SELECT stb.TypeForm[type] FROM
$union, $sequence => NULL; -- skip any variant part
ENDCASE =>
IF (~stb.seb[isei].constant) AND IsRC[stb, type] THEN {
rcmt.base[nvrcmi].components[n] ← [
wordOffset: FieldOffset[isei].wd,
rcmi: DoAcquire[rcmt, stb, type]];
n ← n + 1};
};
simpRCM: SimpleRCM;
simplified: BOOL;
[] ← EnumerateRecordIseis[stb, rsei, Stuff];
IF n # nc THEN ERROR;
[simpRCM, simplified] ← SimplifyRCM[[rcmt.base, nvrcmi]];
IF simplified THEN {rcmt.x ← oldx; RETURN[InstallSimpleRCM[rcmt, simpRCM]]}
ELSE {
found: BOOL; x: Index;
rcmt.base[nvrcmi].complete ← TRUE;
[found, x] ← FindRCMap[rcmt.base, [rcmt.base, nvrcmi], oldx];
IF found THEN {rcmt.x ← oldx; RETURN[x]} ELSE RETURN[nvrcmi]}
}
ELSE RETURN[nullIndex]};
RCMapForVRecord: PROC[rcmt: RCMT, stb: SymbolTable.Base, rsei: RecordSEIndex]
RETURNS[ans: Index] = { -- maybe a sequence-containing record
oldx: CARDINAL = rcmt.x;
nvrcmi: Index = RCMapForNVRecord[rcmt, stb, rsei];
TagFd: PROC[stb: SymbolTable.Base, tag: ISEIndex] RETURNS[FieldDescriptor] = {
offset: BitAddress = stb.seb[tag].idValue;
RETURN[[
wordOffset: offset.wd,
bitFirst: offset.bd,
bitCount: stb.seb[tag].idInfo]]
};
DoUnion: PROC[ucstb: SymbolTable.Base, ucsei: UnionSEIndex] = { -- called once
nvc: CARDINAL = CountRCVariants[ucstb, ucsei];
IF nvc # 0 THEN {
tagSei: ISEIndex = ucstb.seb[ucsei].tagSei;
nVariants: CARDINAL = ucstb.Cardinality[ucstb.seb[tagSei].idType];
caseCtx: CTXIndex = stb.seb[ucsei].caseCtx;
NewVRCM: PROC[
nVariants: [0..componentMaxIndex], fdTag: FieldDescriptor, default: Index]
RETURNS[ans: VIndex] = INLINE {
ans ← LOOPHOLE[AllocRCMap[rcmt, Object.variant.SIZE + nVariants*Index.SIZE]];
rcmt.base[ans] ← [variant[fdTag: fdTag, nVariants: nVariants, variants: TRASH]];
FOR i: CARDINAL IN [0..nVariants) DO
rcmt.base[ans].variants[i] ← default ENDLOOP -- NOTE LOOPHOLE
};
vrcmi: VIndex = NewVRCM[
nVariants: nVariants, fdTag: TagFd[ucstb, tagSei], default: nvrcmi];
n: CARDINAL ← 0;
Stuff: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: No] = {
IF IsRC[stb, isei, FALSE] THEN {
rcmt.base[vrcmi].variants[stb.seb[isei].idValue] ← DoAcquire[rcmt, stb, isei];
n ← n + 1};
};
found: BOOL; x: Index;
[] ← EnumerateCtxIseis[stb, caseCtx, Stuff, (nVariants=stb.CtxEntries[caseCtx])];
IF n # nvc THEN ERROR;
rcmt.base[vrcmi].complete ← TRUE;
[found, x] ← FindRCMap[rcmt.base, [rcmt.base, vrcmi], oldx];
IF found THEN {rcmt.x ← oldx; ans ← x} ELSE ans ← vrcmi}
ELSE ans ← nvrcmi};
DoSeq: PROC[scstb: SymbolTable.Base, scsei: SequenceSEIndex] = { -- called once
componentType: Type = scstb.seb[scsei].componentType;
IF IsRC[scstb, componentType] THEN {
ercmi: Index = DoAcquire[rcmt, scstb, componentType];
tagSei: ISEIndex = scstb.seb[scsei].tagSei;
seqrcmi: SeqIndex;
found: BOOL; x: Index;
IF ~scstb.seb[scsei].controlled THEN ERROR NIY[$computedTag];
IF scstb.seb[scsei].packed THEN ERROR NIY[$packedComponent];
seqrcmi ← NewSeqRCM[rcmt];
rcmt.base[seqrcmi] ← [sequence[
wordsPerElement: scstb.WordsForType[componentType],
fdLength: TagFd[scstb, tagSei],
commonPart: nvrcmi,
dataOffset: (scstb.seb[tagSei].idValue + scstb.seb[tagSei].idInfo)/bitsPerWord,
rcmi: ercmi]];
[found, x] ← FindRCMap[rcmt.base, [rcmt.base, seqrcmi], oldx];
IF found THEN {rcmt.x ← oldx; ans ← x} ELSE ans ← seqrcmi}
ELSE ans ← nvrcmi};
DoVariant: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL] = {
csei: CSEIndex = stb.UnderType[stb.seb[isei].idType];
WITH c~~stb.seb[csei] SELECT FROM
union => DoUnion[stb, LOOPHOLE[csei]];
sequence => DoSeq[stb, LOOPHOLE[csei]]
ENDCASE => RETURN[FALSE];
RETURN[TRUE]};
IF ~EnumerateCtxIseis[stb, stb.seb[rsei].fieldCtx, DoVariant] THEN ERROR};
second level utility PROCs for constructing RCMap Objects
SimplifyRCM: PROC[h: Handle] RETURNS[rcmr: SimpleRCM, simplified: BOOL] = {
srcmr: Object.simple ← [simple[refs: ALL[FALSE]]];
rrcmr: Object.oneRef ← [oneRef[]];
nRefOffsets: CARDINAL ← 0;
nSimpleVecEntries: CARDINAL ← 0;
Enumerate: PROC[index: Index, offset: CARDINAL] RETURNS[stopped: BOOL] = {
WITH rcm~~h.base[index] SELECT FROM
null => RETURN[FALSE];
ref => RETURN[Test[offset]];
controlLink => RETURN[TRUE];
oneRef => RETURN[Test[offset+rcm.offset]];
simple => {
FOR i: CARDINAL IN [0..rcm.length) DO
IF rcm.refs[i] AND Test[offset+i].stop THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE]};
nonVariant => {
FOR i: CARDINAL IN [0 .. rcm.nComponents) DO
IF Enumerate[rcm.components[i].rcmi, offset+rcm.components[i].wordOffset
].stopped THEN
RETURN[TRUE];
ENDLOOP;
RETURN[FALSE]};
array => {
FOR i: CARDINAL IN [0 .. rcm.nElements) DO
IF Enumerate[rcm.rcmi, offset+i*rcm.wordsPerElement].stopped THEN
RETURN[TRUE];
ENDLOOP;
RETURN[FALSE]};
variant, sequence => RETURN[TRUE];
ENDCASE => ERROR
};
Test: PROC[refOffset: CARDINAL] RETURNS[stop: No] = {
nRefOffsets ← nRefOffsets+1;
IF ((nRefOffsets # 1) OR (refOffset > componentMaxIndex))
AND (refOffset > simpleMaxIndex) THEN RETURN[TRUE]; -- can't simplify
IF nRefOffsets = 1 AND refOffset <= componentMaxIndex THEN
rrcmr.offset ← refOffset;
IF refOffset <= simpleMaxIndex THEN {
nSimpleVecEntries ← nSimpleVecEntries + 1;
IF nSimpleVecEntries # nRefOffsets THEN RETURN[TRUE]; -- can't simplify
srcmr.refs[refOffset] ← TRUE;
srcmr.length ← MAX[srcmr.length, refOffset + 1]};
};
simplified ← ~Enumerate[h.index, 0].stopped;
IF simplified THEN {
IF nRefOffsets = 0 THEN rcmr ← Object[null[]]
ELSE IF nRefOffsets = 1 THEN {
IF rrcmr.offset = 0 THEN rcmr ← Object[ref[]]
ELSE rcmr ← rrcmr}
ELSE rcmr ← srcmr}
ELSE rcmr ← Object[null[]]};
PROCS for poking around in the symbol table
copied (GROAN) from RTWalkSymbolsImpl
EnumerateRecordIseis: PROC[
stb: SymbolTable.Base,
rsei: RecordSEIndex,
p: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL],
level: CARDINAL𡤀]
RETURNS[stopped: BOOL] = {
Filter: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL] = {
form: TypeClass = stb.TypeForm[stb.seb[isei].idType];
IF ~(form = $union OR form = $sequence) OR level = 0 THEN RETURN[p[stb, isei]];
RETURN[FALSE]};
IF rsei = CSENull THEN RETURN[FALSE];
SELECT stb.seb[rsei].linkTag FROM
$linked =>
IF EnumerateRecordIseis[stb, stb.RecordLink[rsei], p, level+1] THEN RETURN[TRUE];
ENDCASE;
RETURN[EnumerateCtxIseis[stb, stb.seb[rsei].fieldCtx, Filter]]};
copied (GROAN) from RTWalkSymbolsImpl
EnumerateCtxIseis: PROC [
stb: SymbolTable.Base, ctx: CTXIndex,
proc: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL],
reallyComplete: BOOL←FALSE]
RETURNS[stopped: BOOL] = {
isei: ISEIndex;
IF ctx = CTXNull THEN RETURN[FALSE];
IF ~reallyComplete THEN
WITH c~~stb.ctxb[ctx] SELECT FROM
included =>
IF ~c.complete THEN {
p: PROC[base: SymbolTable.Base] = { -- called once
stopped ← EnumerateCtxIseis[base, c.map, proc]};
outer: OuterProc = SIGNAL GetOuter[];
IF outer = NIL THEN ERROR ELSE outer[stb, c.module, p];
RETURN[stopped]};
simple => NULL;
ENDCASE => ERROR;
FOR isei ← stb.FirstCtxSe[ctx], stb.NextSe[isei] UNTIL isei = ISENull DO
IF stb.seb[isei].hash = nullName AND stb.seb[isei].idCtx = CTXNull THEN NULL -- padding
ELSE IF proc[stb, isei] THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE]};
CountRCVariants: PROC[stb: SymbolTable.Base, usei: UnionSEIndex]
RETURNS[n: CARDINAL ← 0] = {
Count: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: No] = {
IF IsRC[stb, isei, FALSE] THEN n ← n+1};
caseCtx: CTXIndex = stb.seb[usei].caseCtx;
tagCardinality: CARDINAL = stb.Cardinality[stb.seb[stb.seb[usei].tagSei].idType];
[] ← EnumerateCtxIseis[stb, caseCtx, Count, (tagCardinality=stb.CtxEntries[caseCtx])]};
CountRCCommonComponents: PROC[stb: SymbolTable.Base, rsei: RecordSEIndex]
RETURNS[n: CARDINAL ← 0] = {
Count: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: No] = {
type: Type = stb.seb[isei].idType;
SELECT stb.TypeForm[type] FROM
$union, $sequence => NULL; -- don't count the variant part
ENDCASE => IF (~stb.seb[isei].constant) AND IsRC[stb, type] THEN n ← n+1
};
[] ← EnumerateRecordIseis[stb, rsei, Count]};
copied (GROAN) from RTWalkSymbolsImpl
IsRC: PROC[stb: SymbolTable.Base, seIndex: Type, checkCommon: BOOL←TRUE]
RETURNS[BOOL] = {
csei: CSEIndex = stb.UnderType[seIndex];
WITH cr~~stb.seb[csei] SELECT FROM
record => {
rcP: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL] = {
csei1: CSEIndex = stb.UnderType[stb.seb[isei].idType];
WITH cse1~~stb.seb[csei1] SELECT FROM
union => {
urcP: PROC[stb: SymbolTable.Base, isei: ISEIndex] RETURNS[stop: BOOL] = {
RETURN[IsRC[stb, isei, FALSE]]};
tagCardinality: CARDINAL = stb.Cardinality[stb.seb[cse1.tagSei].idType];
RETURN[EnumerateCtxIseis[stb, cse1.caseCtx, urcP,
(tagCardinality=stb.CtxEntries[cse1.caseCtx])]];
};
sequence => RETURN[IsRC[stb, cse1.componentType]];
ENDCASE => RETURN[IsRC[stb, csei1]];
};
RETURN[
IF checkCommon THEN cr.hints.refField -- easy if the common parts count
ELSE -- look individually at the fields of the variant part (unless none possible)
(cr.hints.refField AND EnumerateCtxIseis[stb, cr.fieldCtx, rcP])];
};
ref => RETURN[cr.counted];
array => RETURN[IsRC[stb, cr.componentType]];
transfer => RETURN[FALSE]; -- NOTE for now
union, sequence => ERROR;
relative => RETURN[FALSE]; -- NOTE for now
long => RETURN[IsRC[stb, cr.rangeType]];
zone => RETURN[cr.counted];
ENDCASE => RETURN[FALSE]
};
PROCs for managing RCMap Bases
InlineSize: PROC[h: Handle] RETURNS[CARDINAL] = INLINE {
RETURN[WITH rcm~~h.base[h.index] SELECT FROM
null => Object.null.SIZE, --NOTE better be 1
ref => Object.ref.SIZE, --NOTE better be 1
controlLink => Object.controlLink.SIZE, --NOTE better be 1
oneRef => Object.oneRef.SIZE, --NOTE better be 1
simple => Object.simple.SIZE, --NOTE better be 1
nonVariant => Object.nonVariant.SIZE + rcm.nComponents*RCField.SIZE,
variant => Object.variant.SIZE + rcm.nVariants*Index.SIZE,
array => Object.array.SIZE,
sequence => Object.sequence.SIZE,
ENDCASE => ERROR]
};
EqualMaps: PROC[h1, h2: Handle] RETURNS[BOOL] = {
WITH m1~~h1.base[h1.index] SELECT FROM
null, ref, controlLink => RETURN[h1.index = h2.index]; -- StandardRCMap's
oneRef => RETURN[m1 = h2.base[h2.index]];
simple => RETURN[m1 = h2.base[h2.index]];
nonVariant =>
WITH m2~~h2.base[h2.index] SELECT FROM
nonVariant => {
matched: BOOL ←
(m1.complete AND m2.complete) AND (m1.nComponents = m2.nComponents);
FOR i: NAT IN [0 .. m1.nComponents) WHILE matched DO
matched ← (m1.components[i].wordOffset = m2.components[i].wordOffset)
AND EqualMaps[[h1.base, m1.components[i].rcmi],
[h2.base, m2.components[i].rcmi]];
ENDLOOP;
RETURN[matched]};
ENDCASE => RETURN[FALSE];
variant =>
WITH m2~~h2.base[h2.index] SELECT FROM
variant => {
matched: BOOL ← (m1.complete AND m2.complete)
AND (m1.nVariants = m2.nVariants) AND (m1.fdTag = m2.fdTag);
FOR i: NAT IN [0 .. m1.nVariants) WHILE matched DO
matched ← EqualMaps[[h1.base, m1.variants[i]], [h2.base, m2.variants[i]]];
ENDLOOP;
RETURN[matched]};
ENDCASE => RETURN[FALSE];
array =>
WITH m2~~h2.base[h2.index] SELECT FROM
array =>
RETURN[
(m1.wordsPerElement = m2.wordsPerElement)
AND (m1.nElements = m2.nElements)
AND EqualMaps[[h1.base, m1.rcmi], [h2.base, m2.rcmi]]
];
ENDCASE => RETURN[FALSE];
sequence =>
WITH m2~~h2.base[h2.index] SELECT FROM
sequence =>
RETURN[
(m1.wordsPerElement = m2.wordsPerElement)
AND (m1.fdLength = m2.fdLength)
AND (m1.dataOffset = m2.dataOffset)
AND EqualMaps[[h1.base, m1.commonPart], [h2.base, m2.commonPart]]
AND EqualMaps[[h1.base, m1.rcmi], [h2.base, m2.rcmi]]
];
ENDCASE => RETURN[FALSE];
ENDCASE => ERROR;
};
FindRCMap: PROC[rcmb: Base, h: Handle, limit: CARDINAL]
RETURNS[found: BOOL, index: Index] = {
WITH rcm~~h.base[h.index] SELECT FROM
null, ref, controlLink => {found ← TRUE; index ← h.index}; -- standard entries
ENDCASE => {
Frequent case of DoEnumerate is placed INLINE and specialized!
Note that EqualMaps itself tests for completeness
FOR rcmi: Index ← controlLinkIndex+Object.controlLink.SIZE,
rcmi + InlineSize[[rcmb, rcmi]] UNTIL LOOPHOLE[rcmi, CARDINAL] >= limit DO
IF EqualMaps[h, [rcmb, rcmi]] THEN RETURN[TRUE, rcmi];
ENDLOOP;
found ← FALSE};
RETURN};
EnterRCMap: PROC[rcmt: RCMT, h: Handle] RETURNS[new: Index] = {
nw: CARDINAL = InlineSize[h];
new ← AllocRCMap[rcmt, nw];
WITH m~~h.base[h.index] SELECT FROM
null, ref, controlLink, oneRef, simple => {
PrincOpsUtils.LongCopy[from: @h.base[h.index], to: @rcmt.base[new], nwords: nw]};
array => {
cRcmi: Index = MapRCMIndex[rcmt, [h.base, m.rcmi]];
rcmt.base[new] ← [array[
wordsPerElement: m.wordsPerElement, nElements: m.nElements, rcmi: cRcmi]];
};
nonVariant => {
nvRcmi: RCMap.NVIndex = LOOPHOLE[new];
rcmt.base[nvRcmi] ← [nonVariant[
nComponents: m.nComponents, components: TRASH, complete: FALSE]];
FOR i: NAT IN [0..m.nComponents) DO
rcmt.base[nvRcmi].components[i] ← [
m.components[i].wordOffset, MapRCMIndex[rcmt, [h.base, m.components[i].rcmi]]];
ENDLOOP;
rcmt.base[nvRcmi].complete ← TRUE};
variant => {
vRcmi: RCMap.VIndex = LOOPHOLE[new];
rcmt.base[vRcmi] ← [variant[
nVariants: m.nVariants, fdTag: m.fdTag, variants: TRASH, complete: FALSE]];
FOR i: NAT IN [0..m.nVariants) DO
rcmt.base[vRcmi].variants[i] ← MapRCMIndex[rcmt, [h.base, m.variants[i]]];
ENDLOOP;
rcmt.base[vRcmi].complete ← TRUE};
sequence => {
commonRcmi: Index = MapRCMIndex[rcmt, [h.base, m.commonPart]];
cRcmi: Index = MapRCMIndex[rcmt, [h.base, m.rcmi]];
rcmt.base[new] ← [sequence[
wordsPerElement: m.wordsPerElement, fdLength: m.fdLength,
commonPart: commonRcmi, dataOffset: m.dataOffset, rcmi: cRcmi]];
};
ENDCASE => ERROR;
RETURN};
MapRCMIndex: PROC[rcmt: RCMT, old: Handle] RETURNS[new: Index] = {
found: BOOL;
[found, new] ← FindRCMap[rcmt.base, old, rcmt.x];
IF ~found THEN new ← EnterRCMap[rcmt, old];
RETURN};
AllocRCMap: PROC[rcmt: RCMT, nw: CARDINAL] RETURNS[Index] = {
short: CARDINAL ← rcmt.x;
new: Index ← LOOPHOLE[short];
IF new = invalidIndex THEN ERROR TooManyRCMaps;
rcmt.x ← rcmt.x + nw;
the assignement following will try to write as many words as in the largest RCMap.Object
IF rcmt.x >= ( rcmt.limit-SIZE[RCMap.Object] ) THEN ExpandRCMSpace[rcmt];
rcmt.base[new] ← [null[]];
IF nw > 1 THEN
Ensure valid initialization for this map entry to avoid finding crap!
PrincOpsUtils.LongCopy[from: @rcmt.base[new], to: @rcmt.base[new+1], nwords: nw-1];
RETURN[LOOPHOLE[new]]};
ExpandRCMSpace: PROC[rcmt: RCMT] = {
newBase: RCMap.Base;
newPages: INT = rcmt.pages+4;
IF ~rcmt.expandable THEN ERROR TooManyRCMaps;
newBase ←
LOOPHOLE[VM.AddressForPageNumber[VM.Allocate[count: newPages].page], RCMap.Base];
IF rcmt.base # NIL THEN {
PrincOpsUtils.LongCopy[from: rcmt.base, to: newBase, nwords: rcmt.limit];
VM.Free[[page: VM.PageNumberForAddress[rcmt.base], count: rcmt.pages]]};
rcmt.base ← newBase;
rcmt.pages ← newPages;
rcmt.limit ← newPages*VM.wordsPerPage};
START HERE
static check of size assumptions
check: BOOL[FALSE ..
Object.null.SIZE = 1
AND Object.ref.SIZE = 1
AND Object.oneRef.SIZE = 1
AND Object.simple.SIZE = 1
AND Object.controlLink.SIZE = 1
] = TRUE;
}.