LiteralPack.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Satterthwaite, April 17, 1986 11:02:35 am PST
Paul Rovner, September 7, 1983 6:04 pm
Russ Atkinson (RRA) March 6, 1985 10:25:13 pm PST
DIRECTORY
Alloc: TYPE USING [AddNotify, Bounds, DropNotify, Failure, Handle, Notifier, OrderedIndex, Top, Words],
ConvertUnsafe: TYPE USING [AppendRope, EqualSubStrings, SubString],
Literals: TYPE,
LiteralOps: TYPE USING [],
Symbols: TYPE USING [Type];
LiteralPack:
PROGRAM
IMPORTS Alloc, ConvertUnsafe
EXPORTS LiteralOps = {
OPEN Literals;
table: Alloc.Handle;
ltb: Literals.Base; -- literal table base
stb: Literals.Base; -- string table base
UpdateBases: Alloc.Notifier = {
called whenever the main symbol table is repacked
ltb ← base[ltType]; stb ← base[stType]; RETURN};
ltMax: Alloc.OrderedIndex = Alloc.OrderedIndex.FIRST + (LTIndex.LAST-LTIndex.FIRST);
stMax: Alloc.OrderedIndex = Alloc.OrderedIndex.FIRST + (STIndex.LAST-STIndex.FIRST);
initialized: BOOL ← FALSE;
Initialize:
PUBLIC
PROC[ownTable: Alloc.Handle] = {
called to set up the compiler's literal table
IF initialized THEN Finalize[];
hashVec ← NEW[ARRAY LitHVIndex OF LTIndex];
sHashVec ← NEW[ARRAY SLitHVIndex OF MSTIndex];
table ← ownTable; table.AddNotify[UpdateBases];
[] ← ForgetEntries[]; sHashVec^ ← ALL[MSTNull];
stLimit ← localStart ← STIndex.FIRST; locals ← markBit ← FALSE;
initialized ← TRUE};
Finalize:
PUBLIC
PROC = {
table.DropNotify[UpdateBases]; table ← NIL;
sHashVec ← NIL; hashVec ← NIL;
initialized ← FALSE};
literal table management
litHVLength: INTEGER = 53;
LitHVIndex: TYPE = [0..litHVLength);
hashVec: REF ARRAY LitHVIndex OF LTIndex;
Find:
PUBLIC
PROC[v:
WORD]
RETURNS[LitIndex.word] = {
hvi: LitHVIndex = v MOD litHVLength;
lti: LTIndex;
FOR lti ← hashVec[hvi], ltb[lti].link
UNTIL lti = LTNull
DO
WITH entry: ltb[lti]
SELECT
FROM
short => IF entry.value = v THEN EXIT;
ENDCASE;
REPEAT
FINISHED => {
ti: Alloc.OrderedIndex = table.Words[ltType, LTRecord.short.SIZE];
IF ti >= ltMax THEN ERROR table.Failure[ltType];
lti ← ti; ltb[lti] ← LTRecord[datum: short[value: v], link: hashVec[hvi]];
hashVec[hvi] ← lti};
ENDLOOP;
RETURN[[word[lti]]]};
FindMultiWord:
PROC[baseP: Literals.Finger, desc: LitDescriptor]
RETURNS[LitIndex.word] = {
v: WORD ← 0;
hvi: LitHVIndex;
lti: LTIndex;
lLti: Literals.Base RELATIVE POINTER[0..Literals.Limit) TO LTRecord.long;
FOR i: CARDINAL IN [0 .. desc.length) DO v ← v + baseP^[desc.offset][i] ENDLOOP;
hvi ← v MOD litHVLength;
FOR lti ← hashVec[hvi], ltb[lti].link
UNTIL lti = LTNull
DO
WITH entry: ltb[lti]
SELECT
FROM
long =>
IF desc.length = entry.length
THEN
FOR i:
CARDINAL
IN [0 .. desc.length)
DO
IF entry.value[i] # baseP^[desc.offset][i] THEN EXIT;
REPEAT
FINISHED => GO TO found;
ENDLOOP;
ENDCASE;
REPEAT
found => NULL;
FINISHED => {
ti: Alloc.OrderedIndex = table.Words[ltType, LTRecord.long.SIZE + desc.length];
IF ti >= ltMax THEN ERROR table.Failure[ltType];
lLti ← ti;
ltb[lLti] ← LTRecord[
link: hashVec[hvi],
datum: long[codeIndex: 0, length: desc.length, value: ]];
FOR i:
CARDINAL
IN [0 .. desc.length)
DO
ltb[lLti].value[i] ← baseP^[desc.offset][i] ENDLOOP;
hashVec[hvi] ← lti ← lLti};
ENDLOOP;
RETURN[[word[lti]]]};
Value:
PUBLIC
PROC[lti: LTIndex]
RETURNS[
WORD] = {
WITH entry: ltb[lti]
SELECT
FROM
short => RETURN[entry.value];
long => IF entry.length = 1 THEN RETURN[entry.value[0]];
ENDCASE;
ERROR};
FindDescriptor:
PUBLIC
PROC[desc:
LONG DESCRIPTOR
FOR
ARRAY
OF
WORD]
RETURNS[LitIndex.word] = {
base: Literals.Base ← LOOPHOLE[desc.BASE];
RETURN[
IF desc.
LENGTH = 1
THEN Find[desc[0]]
ELSE FindMultiWord[@base, [offset:LOOPHOLE[0], length:desc.LENGTH]]]};
LTShortPtr: TYPE = POINTER TO LTRecord.short;
LTLongPtr: TYPE = POINTER TO LTRecord.long;
deltaShort: CARDINAL = LOOPHOLE[@(LTShortPtr.NIL).value];
deltaLong: CARDINAL = LOOPHOLE[@(LTLongPtr.NIL).value];
DescriptorValue:
PUBLIC
PROC[lti: LTIndex]
RETURNS[LitDescriptor] = {
RETURN[
WITH entry: ltb[lti]
SELECT
FROM
short => [offset: LOOPHOLE[lti + deltaShort], length: 1],
long => [offset: LOOPHOLE[lti + deltaLong], length: entry.length],
ENDCASE => ERROR]};
CopyLiteral:
PUBLIC
PROC[literal: LTId]
RETURNS[lti: LitIndex.word] = {
desc: LitDescriptor;
WITH entry: literal.baseP^[literal.index.lti]
SELECT
FROM
short => lti ← Find[entry.value];
long => {
desc ← [offset: LOOPHOLE[literal.index.lti + deltaLong], length: entry.length];
lti ← FindMultiWord[literal.baseP, desc]};
ENDCASE => ERROR;
RETURN};
ForgetEntries:
PUBLIC
PROC
RETURNS[currentSize:
CARDINAL] = {
hashVec^ ← ALL[LTNull]; RETURN[table.Bounds[ltType].size]};
string literal table management
MSTNull: MSTIndex = LOOPHOLE[STNull];
SLitHVLength: INTEGER = 23;
SLitHVIndex: TYPE = [0..SLitHVLength);
sHashVec: REF ARRAY SLitHVIndex OF MSTIndex;
stLimit, localStart: STIndex;
locals: BOOL;
markBit: BOOL;
sizeSTPrefix: NAT = STRecord.master.SIZE - StringBody[0].SIZE;
FindString:
PUBLIC
PROC[s: ConvertUnsafe.SubString]
RETURNS[LitIndex.string] = {
CpW: CARDINAL = 2; -- String.CharsPerWord
hash: WORD ← 0;
hvi: SLitHVIndex;
sti: MSTIndex;
FOR i:
CARDINAL
IN [s.offset .. s.offset+s.length)
DO
hash ← hash + LOOPHOLE[s.base[i], CARDINAL] ENDLOOP;
hvi ← hash MOD SLitHVLength;
FOR sti ← sHashVec[hvi], stb[sti].link
UNTIL sti = MSTNull
DO
v: LONG STRING = StringValue[sti];
vs: ConvertUnsafe.SubString ← [base:v, offset:0, length:v.length];
IF s.EqualSubStrings[vs] THEN EXIT;
REPEAT
FINISHED => {
nw: CARDINAL = StringBody[s.length].SIZE;
ti: Alloc.OrderedIndex = table.Words[stType, sizeSTPrefix + nw];
IF ti >= stMax THEN ERROR table.Failure[stType];
sti ← ti;
stb[sti] ← STRecord[master[
info: 0,
codeIndex: 0,
local: FALSE,
link: sHashVec[hvi],
string: [
length: 0,
maxlength: ((s.length + (CpW-1))/CpW) * CpW,
text: ]]];
FOR i:
CARDINAL
IN [0 .. s.length)
DO
stb[sti].string[i] ← s.base[s.offset+i] ENDLOOP;
FOR i:
CARDINAL
IN [s.length .. stb[sti].string.maxlength)
DO
stb[sti].string[i] ← '\000 ENDLOOP;
stb[sti].string.length ← s.length;
stLimit ← stLimit + (sizeSTPrefix + nw);
sHashVec[hvi] ← sti};
ENDLOOP;
RETURN[[string[sti]]]};
MasterString:
PUBLIC
PROC[sti: STIndex]
RETURNS[MSTIndex] = {
RETURN[
WITH s: stb[sti]
SELECT
FROM
master => LOOPHOLE[sti],
copy => s.link,
heap => s.link,
ENDCASE => MSTNull]};
StringReference:
PUBLIC
PROC[sti: STIndex] = {
WITH s: stb[sti]
SELECT
FROM
master => s.info ← s.info + 1;
ENDCASE => NULL};
StringValue:
PUBLIC
PROC[sti: STIndex]
RETURNS[
LONG
STRING] = {
RETURN[@stb[MasterString[sti]].string]};
TextType:
PUBLIC
PROC[sti: STIndex]
RETURNS[Symbols.Type] = {
RETURN[WITH s: stb[sti] SELECT FROM heap => s.type, ENDCASE => ERROR]};
ResetLocalStrings:
PUBLIC
PROC RETURNS[key: STIndex] = {
IF ~locals THEN key ← STNull
ELSE {key ← localStart; markBit ← ~markBit};
locals ← FALSE; localStart ← table.Top[stType];
RETURN};
FindHeapString:
PUBLIC
PROC[key: STIndex, type: Symbols.Type]
RETURNS[sti: STIndex] = {
next: STIndex;
master: MSTIndex = MasterString[key];
FOR sti ← STIndex.
FIRST, next
UNTIL sti = stLimit
DO
WITH s: stb[sti]
SELECT
FROM
master => next ← sti + sizeSTPrefix + StringBody[s.string.maxlength].SIZE;
copy => next ← sti + STRecord.copy.SIZE;
heap => {
IF s.type = type AND s.link = master THEN EXIT;
next ← sti + STRecord.heap.SIZE};
ENDCASE;
REPEAT
FINISHED => {
ti: Alloc.OrderedIndex = table.Words[stType, STRecord.heap.SIZE];
IF ti >= stMax THEN ERROR table.Failure[stType];
sti ← ti;
stb[sti] ← STRecord[heap[type: type, info: 0, link: master]];
stLimit ← stLimit + STRecord.heap.SIZE};
ENDLOOP;
RETURN};
FindLocalString:
PUBLIC
PROC[key: STIndex]
RETURNS[sti: STIndex] = {
next: STIndex;
master: MSTIndex = MasterString[key];
FOR sti ← localStart, next
UNTIL sti = stLimit
DO
WITH s: stb[sti]
SELECT
FROM
master =>
next ← sti + sizeSTPrefix + StringBody[s.string.maxlength].SIZE;
copy => {
IF s.link = master THEN EXIT;
next ← sti + STRecord.copy.SIZE};
heap => next ← sti + STRecord.heap.SIZE;
ENDCASE;
REPEAT
FINISHED => {
ti: Alloc.OrderedIndex = table.Words[stType, STRecord.copy.SIZE];
IF ti >= stMax THEN ERROR table.Failure[stType];
sti ← ti; stb[sti] ← STRecord[copy[mark: markBit, link: master]];
stLimit ← stLimit + STRecord.copy.SIZE;
locals ← TRUE};
ENDLOOP;
RETURN};
EnumerateHeapStrings:
PUBLIC
PROC[proc:
PROC[STIndex]] = {
next: STIndex;
FOR sti: STIndex ← STIndex.
FIRST, next
UNTIL sti = stLimit
DO
WITH s: stb[sti]
SELECT
FROM
master => next ← sti + sizeSTPrefix + StringBody[s.string.maxlength].SIZE;
copy => next ← sti + STRecord.copy.SIZE;
heap => {proc[sti]; next ← sti + STRecord.heap.SIZE};
ENDCASE => ERROR;
ENDLOOP};
EnumerateLocalStrings:
PUBLIC
PROC[key: STIndex, proc:
PROC[MSTIndex]] = {
next: STIndex;
started, mark: BOOL;
IF key = STNull THEN RETURN;
started ← FALSE;
FOR sti: STIndex ← key, next
UNTIL sti = stLimit
DO
WITH s: stb[sti]
SELECT
FROM
master => next ← sti + sizeSTPrefix + StringBody[s.string.maxlength].SIZE;
copy => {
IF ~started THEN {mark ← s.mark; started ← TRUE};
IF s.mark # mark THEN EXIT;
proc[s.link];
next ← sti + STRecord.copy.SIZE};
heap => next ← sti + STRecord.heap.SIZE;
ENDCASE => ERROR;
ENDLOOP};
EnumerateMasterStrings:
PUBLIC
PROC[proc:
PROC[MSTIndex]] = {
next: STIndex;
FOR sti: STIndex ← STIndex.
FIRST, next
UNTIL sti = stLimit
DO
WITH s: stb[sti]
SELECT
FROM
master => {
proc[LOOPHOLE[sti]];
next ← sti + sizeSTPrefix + StringBody[s.string.maxlength].SIZE};
copy => next ← sti + STRecord.copy.SIZE;
heap => next ← sti + STRecord.heap.SIZE;
ENDCASE => ERROR;
ENDLOOP};
}.