-- RunReaderImpl.mesa
-- written by Bill Paxton, March 1981
-- last edit by Bill Paxton, October 18, 1982 11:32 am
Last Edited by: Maxwell, January 5, 1983 1:08 pm
DIRECTORY
RunReader,
TextLooks,
TextLooksSupport,
TextNode;
RunReaderImpl: CEDAR MONITOR
IMPORTS TextLooks, TextLooksSupport, RunReader, TextNode
EXPORTS RunReader
SHARES RunReader, TextLooks =
BEGIN OPEN RunReader, TextLooks, TextLooksSupport;
Create: PUBLIC PROC RETURNS [Ref] = { RETURN [TextNode.pZone.NEW[Body]] };
GetIndex: PUBLIC PROC [reader: Ref] RETURNS [index: Offset] = {
base: Base;
offset: Offset;
IF reader.after = reader.current THEN RETURN [reader.index];
base ← reader.base;
offset ← IF reader.current=0 THEN base[reader.after-1].after
ELSE base[reader.after-1].after-base[reader.current-1].after;
RETURN [reader.index - offset] };
NoMoreRuns: PUBLIC ERROR = CODE;
ReadRun: PUBLIC PROC [reader: Ref, mode: Mode]
RETURNS [count: Offset, looks: Looks] = {
runs: Runs ← reader.runs;
index, current: Offset ← GetIndex[reader];
after: Offset ← TextLooks.Size[runs];
first: Offset ← 0;
remove, add: Looks ← noLooks;
SetIndx: PROC [index: Offset] = { reader.index ← index };
SetBaseInfo: PROC [current, first, after: NAT, base: Base] = {
reader.current ← current; reader.first ← first;
reader.after ← after; reader.base ← base };
ClearBaseInfo: PROC = { SetBaseInfo[0,0,0,NIL] };
SetLooksInfo: PROC = {
reader.remove ← remove; reader.add ← add;
reader.changeLooks ← remove # noLooks OR add # noLooks };
Modify: PROC [lks: Looks] RETURNS [Looks] = INLINE {
RETURN [TextLooksSupport.ModifyLooks[lks, remove, add]] };
SingleRun: PROC = {
ClearBaseInfo;
SELECT mode FROM
get => SetIndx[index + (count ← after-current)];
peek => count ← after-current;
backwards => SetIndx[index - (count ← current-first+1)];
peekbackwards => count ← current-first+1;
ENDCASE => ERROR};
IF runs=NIL THEN RETURN [LAST[NAT],noLooks];
SELECT mode FROM -- adjust current depending on direction
backwards, peekbackwards =>
IF current=0 THEN ERROR NoMoreRuns ELSE current ← current-1;
get, peek => NULL;
ENDCASE => ERROR;
IF current >= after THEN ERROR NoMoreRuns;
WHILE runs # NIL DO
TRUSTED {WITH x:runs SELECT FROM
base => {
len: Offset ← after-first;
firstRun, lastRun, afterRun, curRun: NAT; -- indexes into runs
startRuns, afterRuns, startCur: Offset;
[firstRun, lastRun] ← TextLooksSupport.FindBaseRuns[@x, first, len];
IF firstRun=lastRun THEN { -- treat as special case
SingleRun; RETURN [count, Modify[x[firstRun].looks]] };
IF (firstRun=0 AND first=0) OR
(firstRun>0 AND x[firstRun-1].after=first) THEN startRuns ← first
ELSE -- only included part of firstRun
IF current >= (startRuns ← x[firstRun].after) THEN
firstRun ← firstRun+1 -- current not in first run
ELSE { -- current is in the first run. must special case it.
IF x[lastRun].after=after THEN { -- include all of lastRun
afterRuns ← after; afterRun ← lastRun+1 }
ELSE { afterRuns ← x[lastRun-1].after; afterRun ← lastRun };
SELECT mode FROM
get => {
count ← startRuns-current;
IF afterRun > firstRun THEN {
SetBaseInfo[firstRun+1, firstRun+1, afterRun, @x];
SetIndx[index+afterRuns-current]; SetLooksInfo; }
ELSE { ClearBaseInfo; SetIndx[index+count] }};
peek => {
count ← startRuns-current;
ClearBaseInfo; SetIndx[index] };
backwards => {
count ← current-first+1;
ClearBaseInfo; SetIndx[index-count] };
peekbackwards => {
count ← current-first+1;
ClearBaseInfo; SetIndx[index] };
ENDCASE => ERROR;
RETURN [count, Modify[x[firstRun].looks]] };
IF x[lastRun].after=after THEN { -- included all of lastRun
afterRuns ← after; afterRun ← lastRun+1 }
ELSE { -- only included part of lastRun
-- know lastRun>0 since lastRun>firstRun
IF current >= (afterRuns ← x[lastRun-1].after) THEN {
-- current is in the lastRun. must special case it.
SELECT mode FROM
get => {
count ← after-current;
ClearBaseInfo; SetIndx[index+count] };
peek => {
count ← after-current;
ClearBaseInfo; SetIndx[index] };
backwards => {
count ← current-afterRuns+1;
IF lastRun > firstRun THEN {
SetBaseInfo[lastRun-1, firstRun, lastRun, @x];
SetIndx[index-count]; SetLooksInfo; }
ELSE { ClearBaseInfo; SetIndx[index-count] }};
peekbackwards => {
count ← current-afterRuns+1;
ClearBaseInfo; SetIndx[index] };
ENDCASE => ERROR;
RETURN [count, Modify[x[lastRun].looks]] };
afterRun ← lastRun };
curRun ← TextLooksSupport.BaseRun[@x, current, firstRun, lastRun];
startCur ← IF curRun=0 THEN 0 ELSE x[curRun-1].after;
SELECT mode FROM
get => {
count ← x[curRun].after-current;
SetBaseInfo[curRun+1, firstRun, afterRun, @x];
SetIndx[index+afterRuns-current]; SetLooksInfo; };
peek => {
count ← x[curRun].after-current;
IF current = startCur THEN {
SetBaseInfo[curRun, firstRun, afterRun, @x];
SetIndx[index+afterRuns-current]; SetLooksInfo; }
ELSE { ClearBaseInfo; SetIndx[index] }};
backwards => { -- recall that current has been decremented
count ← current-startCur+1;
SetBaseInfo[curRun, firstRun, afterRun, @x];
SetIndx[index+afterRuns-current-1]; SetLooksInfo; };
peekbackwards => {
count ← current-startCur+1;
IF current = x[curRun].after-1 THEN {
SetBaseInfo[curRun+1, firstRun, afterRun, @x];
SetIndx[index+afterRuns-current-1]; SetLooksInfo; }
ELSE { ClearBaseInfo; SetIndx[index] }};
ENDCASE => ERROR;
RETURN [count, Modify[x[curRun].looks]]};
node => WITH x:x SELECT FROM
substr => IF current < x.size THEN {
offset: Offset;
current ← current + (offset ← x.start);
first ← first + offset; after ← after + offset;
runs ← x.base; LOOP };
concat => IF current < x.size THEN {
xpos: Offset;
IF current >= (xpos ← x.pos) THEN {
current ← current - xpos; after ← after - xpos;
first ← IF first <= xpos THEN 0 ELSE first - xpos;
runs ← x.rest; LOOP };
IF after > xpos THEN after ← xpos;
runs ← x.base; LOOP };
replace => IF current < x.size THEN {
xstart: Offset ← x.start;
newPos, oldPos: Offset;
IF current < xstart THEN {
IF after > xstart THEN after ← xstart;
runs ← x.base; LOOP };
IF current < (newPos ← x.newPos) THEN {
current ← current - xstart;
after ← MIN[after, newPos] - xstart;
first ← IF first <= xstart THEN 0 ELSE first-xstart;
runs ← x.replace; LOOP };
current ← current - newPos + (oldPos ← x.oldPos);
after ← after - newPos + oldPos;
first ← IF first >= newPos THEN first - newPos + oldPos ELSE oldPos;
runs ← x.base; LOOP };
change => {
xstart: Offset ← x.start;
xend: Offset;
IF current < xstart THEN {
after ← MIN[after, xstart]; runs ← x.base; LOOP };
IF current < (xend ← xstart+x.len) THEN {
after ← MIN[after, xend]; first ← MAX[first, xstart];
[remove, add] ← TextLooksSupport.MergeChanges[x.remove,x.add,remove,add];
IF remove=TextLooks.allLooks THEN { SingleRun; RETURN[count,add] };
runs ← x.base; LOOP };
first ← MAX[first,xend]; runs ← x.base; LOOP };
ENDCASE => ERROR;
ENDCASE => ERROR};
EXIT;
ENDLOOP;
ERROR NoMoreRuns};
MergedGet: PUBLIC ReaderProc = {
-- merges adjacent runs with same looks
-- regular Get may give same looks on successive calls
-- e.g., if Concat[A,B] produces in a concat-node
-- and the last run in A has the same looks as the first in B
-- Get will first return last run from A, then first from B
-- MergedGet will combine these into a single result1
[count,looks] ← Get[reader];
WHILE reader.current=reader.after OR reader.changeLooks DO
nxtCount: Offset;
nxtLooks: Looks;
[nxtCount,nxtLooks] ← Peek[reader ! NoMoreRuns => EXIT];
IF nxtLooks#looks THEN RETURN;
count ← count+nxtCount;
[,] ← Get[reader];
ENDLOOP };
EqSubstrs: PUBLIC PROC [r1,r2: Runs, start1,start2,len: Offset, rdr1,rdr2: Ref]
RETURNS [BOOLEAN] = {
-- uses readers rdr1 and rdr2 to read runs r1 and r2 to test for equality
-- returns TRUE if r1 is same as len looks of r2 starting at start
NoLooks: PROC [r: Runs, start, len: Offset, rdr: Ref] RETURNS [BOOLEAN] = {
looks: Looks;
runLen: Offset;
size: Offset ← TextLooks.Size[r];
len ← IF start > size THEN 0 ELSE MIN[len,size-start];
SetPosition[rdr,r,start];
[runLen,looks] ← Get[rdr];
IF looks # noLooks OR runLen < len THEN RETURN [FALSE];
RETURN [TRUE] };
size1, size2: Offset;
IF len=0 THEN RETURN[TRUE];
IF r1=NIL THEN {
IF r2=NIL THEN RETURN [TRUE];
RETURN [NoLooks[r2,start2,len,rdr2]] };
IF r2=NIL THEN RETURN [NoLooks[r1,start1,len,rdr1]];
size1 ← TextLooks.Size[r1];
size2 ← TextLooks.Size[r2];
IF len=LAST[Offset] THEN { IF (len ← size1-start1) # size2-start2 THEN RETURN [FALSE] }
ELSE IF start1+len > size1 THEN RETURN [FALSE]
ELSE IF start2+len > size2 THEN RETURN [FALSE];
SetPosition[rdr1, r1, start1];
SetPosition[rdr2, r2, start2];
DO -- check the runs in the specified sections
looks1,looks2: Looks;
runLen1,runLen2: Offset;
[runLen1,looks1] ← MergedGet[rdr1];
[runLen2,looks2] ← MergedGet[rdr2];
IF looks1 # looks2 THEN RETURN [FALSE];
IF runLen1 >= len THEN { IF runLen2 < len THEN RETURN [FALSE]; EXIT };
IF runLen2 # runLen1 THEN RETURN [FALSE];
len ← len-runLen1;
ENDLOOP;
RETURN [TRUE] };
-- ***** Shared readers
runrdr1, runrdr2, runrdr3: Ref; -- shared run readers
GetRunReader: PUBLIC ENTRY PROC RETURNS [reader: Ref] = {
ENABLE UNWIND => NULL;
IF runrdr3 # NIL THEN { reader ← runrdr3; runrdr3 ← NIL }
ELSE IF runrdr2 # NIL THEN { reader ← runrdr2; runrdr2 ← NIL }
ELSE IF runrdr1 # NIL THEN { reader ← runrdr1; runrdr1 ← NIL }
ELSE reader ← Create[] };
FreeRunReader: PUBLIC ENTRY PROC [reader: Ref] = {
ENABLE UNWIND => NULL;
SetPosition[reader, NIL];
IF runrdr3 = reader OR runrdr2 = reader OR runrdr1 = reader THEN ERROR;
IF runrdr3 = NIL THEN runrdr3 ← reader
ELSE IF runrdr2 = NIL THEN runrdr2 ← reader
ELSE IF runrdr1 = NIL THEN runrdr1 ← reader };
-- ***** Initialization
Start: PUBLIC PROC = {
};
END.