TextLooksImpl.mesa
Copyright © 1985, 1986 by Xerox Corporation. All rights reserved.
written by Bill Paxton, February 1981
Bill Paxton, December 13, 1982 1:17 pm
Maxwell, January 5, 1983 3:54 pm
Russ Atkinson, July 25, 1983 3:36 pm
Michael Plass, March 29, 1985 5:24:46 pm PST
Doug Wyatt, September 4, 1986 6:09:19 pm PDT
DIRECTORY
Basics USING [DoubleAnd, DoubleNot, DoubleOr, NonNegative],
PrincOpsUtils USING [LongCopy],
Rope USING [Cat, Fetch, FromChar, ROPE, Size],
RunReader USING [FreeRunReader, Get, GetRunReader, Ref, SetPosition],
TextLooks USING [allLooks, BaseRuns, FlatMax, Look, Looks, MaxLen, noLooks, Run, Runs, RunsBody, Tchange, Tconcat, Treplace, Tsubstr],
TextLooksSupport USING [];
TextLooksImpl: CEDAR PROGRAM
IMPORTS Basics, PrincOpsUtils, Rope, RunReader
EXPORTS TextLooks, TextLooksSupport
SHARES TextLooks
= BEGIN OPEN TextLooks;
OutOfBounds: PUBLIC ERROR = CODE;
NonNeg: PROC [x: INT] RETURNS [INT] = INLINE { RETURN[Basics.NonNegative[x]] };
CheckLongSub: PROC [x, y: INT] RETURNS [INT] = INLINE { RETURN[NonNeg[x-y]] };
TextLooksBasicImpl
ReplaceByRun: PUBLIC PROC [dest: Runs, start, len, runLen, destSize: INT, inherit: BOOL, looks: Looks] RETURNS [Runs] = {
merge: BOOL ← FALSE;
mergeLooks: Looks;
split, numruns: NAT;
flat: BaseRuns;
c, numRuns, oldPos, size: INT;
Count: PROC [start, len: INT] RETURNS [INT] = {
IF len=0 THEN RETURN[numRuns];
[c, merge, mergeLooks] ←
CountRuns[dest, start, len, FlatMax-numRuns, merge, mergeLooks];
RETURN [numRuns←numRuns+c];
};
AddIt: PROC RETURNS [INT] = {
c ← IF merge AND mergeLooks=looks THEN 0 ELSE 1;
merge ← TRUE; mergeLooks ← looks;
RETURN [numRuns←numRuns+c];
};
Extract: PROC [start, len: INT] = {
IF len > 0 THEN split ← ExtractRuns[flat, dest, start, len, split];
};
TryFlatAppendRun: PROC [base: Runs] RETURNS [Runs] = {
flat: BaseRuns;
size: INT;
[numRuns, merge, mergeLooks] ← CountRuns[base, 0, size←Size[base], FlatMax];
IF numRuns > FlatMax OR AddIt[] > FlatMax THEN RETURN [NIL];
flat ← NewBase[numruns←numRuns];
split ← ExtractRuns[flat, base, 0, size, 0];
split ← InsertRun[flat, runLen, looks, split];
IF split # numruns THEN ERROR;
IF flat[numruns-1].after # size+runLen THEN ERROR;
RETURN [flat];
};
IF runLen=0 THEN RETURN [Replace[base: dest, start: start, len: len, replace: NIL, baseSize: destSize, repSize: 0, tryFlat: TRUE]];
IF inherit THEN {-- get looks from destination
IF destSize = 0 THEN NULL -- take from arg list
ELSE looks ← FetchLooks[dest,
IF start > 0 THEN start-1 -- take from before replacement
ELSE IF len=destSize THEN 0 -- replacing everything
ELSE len]; -- take from after replacement
};
IF dest=NIL AND looks=noLooks THEN RETURN[NIL];
numRuns ← 0; oldPos ← start+len; size ← destSize-len+runLen;
IF Count[0, start] > FlatMax OR AddIt[] > FlatMax OR Count[oldPos, destSize-oldPos] > FlatMax THEN {
newPos: INT ← start+runLen;
replace, new: Runs;
WHILE dest # NIL DO
WITH dest SELECT FROM
x: REF RunsBody.node.replace => {
xnewPos: INT ← x.newPos;
xstart: INT ← x.start;
IF start <= xstart AND oldPos >= xnewPos THEN {
replacing the replacement
oldPos ← x.oldPos+(oldPos-xnewPos); dest ← x.base; len ← oldPos-start; LOOP;
}
ELSE IF start = xnewPos -- appending to the replacement
AND (new ← TryFlatAppendRun[x.replace])#NIL THEN {
start ← xstart; oldPos ← x.oldPos+len;
dest ← x.base; replace ← new;
Exit the loop from here; len and runLen are not needed anymore, so don't upate the values.
}
};
x: REF RunsBody.node.concat => { -- try to append to first part of the concat
xpos: INT ← x.pos;
IF start=xpos AND len=0 AND
(new ← TryFlatAppendRun[x.base])#NIL THEN RETURN [
NEW[Tconcat ← [node[concat
[size, new, x.rest, xpos+runLen]]]]];
};
ENDCASE;
EXIT;
ENDLOOP;
IF replace=NIL AND (replace ← CreateRun[runLen, looks])=NIL THEN
replace ← MakeRun[runLen];
IF dest=NIL THEN dest ← MakeRun[destSize];
RETURN [NEW[Treplace ← [node[replace[size, dest, replace, start, oldPos, newPos]]]]]
};
IF numRuns=0 THEN RETURN[NIL];
flat ← NewBase[numruns←numRuns]; split ← 0;
Extract[0, start];
split ← InsertRun[flat, runLen, looks, split];
Extract[oldPos, destSize-oldPos];
IF split # numruns THEN ERROR;
IF flat[numruns-1].after # size THEN ERROR;
RETURN [flat]
};
CountRuns: PUBLIC PROC [runs: Runs, start, len: INT, limit: INT ← MaxLen, merge: BOOL ← FALSE, firstLooks: Looks ← noLooks] RETURNS [count: INT, nonempty: BOOL, lastLooks: Looks] = {
stops counting when exceeds limit
if merge is true, then doesn't count first run if its looks=firstLooks
c: INT;
count ← 0;
DO nonempty ← merge;
IF len=0 THEN { lastLooks ← firstLooks; RETURN };
IF runs=NIL THEN {
c ← IF merge AND firstLooks=noLooks THEN 0 ELSE 1;
RETURN [count+c, TRUE, noLooks]
};
WITH runs SELECT FROM
x: REF RunsBody.base => {
first, last: NAT;
len ← MIN[len, CheckLongSub[TbaseSize[x], start]];
[first, last] ← FindBaseRuns[x, start, len];
c ← last-first+1;
IF merge AND firstLooks=x[first].looks THEN c ← c-1;
RETURN [count+c, TRUE, x[last].looks]
};
x: REF RunsBody.node.substr => {
len ← MIN[len, CheckLongSub[x.size, start]];
start ← start + x.start; runs ← x.base; LOOP
};
x: REF RunsBody.node.concat => {
xpos: INT ← x.pos;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xpos THEN {
subLen: INT ← xpos - start;
IF len <= subLen THEN { runs ← x.base; LOOP };
[c, merge, firstLooks] ← CountRuns[
x.base, start, subLen, limit, merge, firstLooks];
count ← count+c; IF c > limit THEN RETURN;
limit ← limit-c; start ← xpos; len ← len-subLen;
};
start ← start-xpos; runs ← x.rest; LOOP
};
x: REF RunsBody.node.replace => {
xstart: INT ← x.start;
xnew: INT ← x.newPos;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xstart THEN {
subLen: INT ← xstart - start;
IF len <= subLen THEN {runs ← x.base; LOOP};
[c, merge, firstLooks] ← CountRuns[
x.base, start, subLen, limit, merge, firstLooks];
count ← count+c; IF c > limit THEN RETURN;
limit ← limit-c;
start ← xstart; len ← len-subLen;
};
IF start < xnew THEN {
st: INT ← start - xstart;
subLen: INT ← xnew - start;
IF len <= subLen THEN {
start ← st; runs ← x.replace; LOOP
};
[c, merge, firstLooks] ← CountRuns[
x.replace, st, subLen, limit, merge, firstLooks];
count ← count+c; IF c > limit THEN RETURN;
limit ← limit-c; start ← xnew; len ← len-subLen
};
start ← start - xnew + x.oldPos; runs ← x.base; LOOP
};
x: REF RunsBody.node.change => {
xstart: INT ← x.start;
xend, subLen: INT;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xstart THEN {
IF len <= (subLen ← xstart-start) THEN {runs ← x.base; LOOP};
[c, merge, firstLooks] ← CountRuns[
x.base, start, subLen, limit, merge, firstLooks];
count ← count+c; IF c > limit THEN RETURN;
limit ← limit-c;
start ← xstart; len ← len-subLen;
};
IF start < (xend ← xstart+x.len) THEN {
subLen ← MIN[xend-start, len];
[c, merge, firstLooks] ← CountRunsAfterChanges[
x.base, start, subLen, limit,
x.remove, x.add, merge, firstLooks];
count ← count+c; IF c > limit THEN RETURN;
limit ← limit-c; start ← xend; len ← len-subLen;
};
runs ← x.base; LOOP
};
ENDCASE => ERROR;
ENDLOOP;
};
ExtractRuns: PUBLIC PROC [base: BaseRuns, ref: Runs, start, len: INT, index: NAT ← 0] RETURNS [NAT] = TRUSTED { -- value is next index
DO
IF len=0 THEN RETURN [index];
IF ref=NIL THEN -- treat as noLooks
RETURN [InsertRun[base, len, noLooks, index]];
WITH ref SELECT FROM
x: REF RunsBody.base => {
firstLen, lastLen, xloc, next, loc: INT;
first, last: NAT;
len ← MIN[len, CheckLongSub[TbaseSize[x], start]];
[first, last] ← FindBaseRuns[x, start, len];
[firstLen, lastLen] ← BaseRunLengths[x, start, len, first, last];
now extract the runs
IF index=0 THEN { -- this is the first run to be extracted
loc ← firstLen; base[0] ← [loc, x[first].looks]; index ← 1;
}
ELSE {
loc ← base[index-1].after + firstLen;
IF base[index-1].looks=x[first].looks -- merge runs
THEN base[index-1].after ← loc
ELSE { base[index] ← [loc, x[first].looks]; index ← index+1 }
};
IF first=last THEN RETURN [index];
IF (xloc ← x[first].after) = loc THEN { -- can simply copy runs
numRuns: NAT;
IF (numRuns ← last-first-1) > 0 THEN {
CopyRuns[to:base, toLoc:index,
from:x, fromLoc:first+1, nRuns: numRuns];
index ← index+numRuns; loc ← base[index-1].after
}
}
ELSE FOR i: NAT IN (first..last) DO
loc ← loc + (next ← x[i].after) - xloc; xloc ← next;
base[index] ← [loc, x[i].looks];
index ← index+1; ENDLOOP;
base[index] ← [loc+lastLen, x[last].looks];
RETURN [index+1]
};
x: REF RunsBody.node.substr => {
len ← MIN[len, CheckLongSub[x.size, start]];
start ← start + x.start; ref ← x.base; LOOP
};
x: REF RunsBody.node.concat => {
xpos: INT ← x.pos;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xpos THEN {
subLen: INT ← xpos - start;
IF len <= subLen THEN { ref ← x.base; LOOP };
index ← ExtractRuns[base, x.base, start, subLen, index];
start ← xpos; len ← len-subLen
};
start ← start-xpos; ref ← x.rest; LOOP
};
x: REF RunsBody.node.replace => {
xstart: INT ← x.start;
xnew: INT ← x.newPos;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xstart THEN {
subLen: INT ← xstart - start;
IF len <= subLen THEN {ref ← x.base; LOOP};
index ← ExtractRuns[base, x.base, start, subLen, index];
start ← xstart; len ← len-subLen
};
IF start < xnew THEN {
st: INT ← start - xstart;
subLen: INT ← xnew - start;
IF len <= subLen THEN {
start ← st; ref ← x.replace; LOOP
};
index ← ExtractRuns[base, x.replace, st, subLen, index];
start ← xnew; len ← len-subLen
};
start ← start - xnew + x.oldPos; ref ← x.base; LOOP
};
x: REF RunsBody.node.change => {
xstart: INT ← x.start;
xend, subLen: INT;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xstart THEN {
IF len <= (subLen ← xstart-start) THEN {ref ← x.base; LOOP};
index ← ExtractRuns[base, x.base, start, subLen, index];
start ← xstart; len ← len-subLen
};
IF start < (xend ← xstart+x.len) THEN {
subLen ← MIN[xend-start, len];
index ← ExtractRunsAfterChanges[
base, x.base, x.remove, x.add, start, subLen, index];
start ← xend; len ← len-subLen
};
ref ← x.base; LOOP
};
ENDCASE => ERROR;
ENDLOOP
};
NewBase: PUBLIC PROC [runs: NAT] RETURNS [BaseRuns] = {
RETURN [NEW[base RunsBody[runs]]];
};
BaseRun: PUBLIC PROC [x: BaseRuns, index: INT, lower: NAT ← 0, upper: NAT ← LAST[NAT]] RETURNS [NAT] = {
len: NAT;
size: INT;
IF index = 0 THEN RETURN [0];
IF (len←x.length) <= 1 THEN RETURN [0];
IF index+1 >= (size←TbaseSize[x]) THEN RETURN[len-1];
IF upper >= len THEN upper ← len-1;
IF lower > 0 AND x[lower-1].after > index THEN lower ← 0;
DO -- always know index is in run between lower and upper inclusive
run: NAT ← (upper+lower)/2;
IF index < x[run].after THEN upper ← run ELSE lower ← run+1;
IF upper=lower THEN RETURN[upper];
ENDLOOP
};
CopyRuns: PUBLIC PROC [to, from: BaseRuns, toLoc, fromLoc, nRuns: NAT] = TRUSTED {
RunsOffset: NAT = SIZE[base RunsBody[0]];
nLeft: NAT;
IF nRuns=0 THEN RETURN;
IF fromLoc >= from.length OR toLoc >= to.length THEN ERROR;
nLeft ← nRuns-1;
to[toLoc+nLeft] ← from[fromLoc+nLeft]; -- bounds check
PrincOpsUtils.LongCopy[
from: LOOPHOLE[from, LONG POINTER]+fromLoc*SIZE[Run]+RunsOffset,
to: LOOPHOLE[to, LONG POINTER]+toLoc*SIZE[Run]+RunsOffset,
nwords: nLeft*SIZE[Run]]
};
InsertRun: PUBLIC PROC [base: BaseRuns, len: INT, looks: Looks, index: NAT] RETURNS [NAT] = { -- value is next index
IF index=0 THEN { base[0] ← [len, looks]; index ← 1 }
ELSE {
loc: INT ← base[index-1].after + len;
IF base[index-1].looks=looks -- merge runs
THEN base[index-1].after ← loc
ELSE { base[index] ← [loc, looks]; index ← index+1 }
};
RETURN [index]
};
FindBaseRuns: PUBLIC PROC [x: BaseRuns, start, len: INT] RETURNS [first, last: NAT] = {
first ← BaseRun[x, start];
last ← IF len>1 THEN BaseRun[x, start+len-1, first] ELSE first
};
BaseRunLengths: PUBLIC PROC [x: BaseRuns, start, len: INT, first, last: NAT] RETURNS [firstLen, lastLen: INT] = {
IF first=last THEN RETURN[len, len];
RETURN[x[first].after-start, start+len-x[last-1].after]
};
And: PROC [a, b: Looks] RETURNS [Looks] ~ INLINE {
RETURN[LOOPHOLE[Basics.DoubleAnd[LOOPHOLE[a], LOOPHOLE[b]]]];
};
Or: PROC [a, b: Looks] RETURNS [Looks] ~ INLINE {
RETURN[LOOPHOLE[Basics.DoubleOr[LOOPHOLE[a], LOOPHOLE[b]]]];
};
Not: PROC [a: Looks] RETURNS [Looks] ~ INLINE {
RETURN[LOOPHOLE[Basics.DoubleNot[LOOPHOLE[a]]]];
};
LooksAND: PUBLIC PROC [looks1, looks2: Looks] RETURNS [Looks] ~ {
RETURN[And[looks1, looks2]];
};
LooksOR: PUBLIC PROC [looks1, looks2: Looks] RETURNS [Looks] ~ {
RETURN[Or[looks1, looks2]];
};
LooksNOT: PUBLIC PROC [looks: Looks] RETURNS [Looks] ~ {
RETURN[Not[looks]];
};
ModifyLooks: PUBLIC PROC [old, remove, add: Looks] RETURNS [Looks] = {
modified looks are == (old & ~remove) v add
RETURN[Or[And[old, Not[remove]], add]];
};
MergeChanges: PUBLIC PROC [oldrem, oldadd, rem, add: Looks] RETURNS [newrem, newadd: Looks] = {
((lks & ~oldrem) v oldadd) & ~rem) v add ==
lks & ~(oldrem v rem)) v ((oldadd & ~rem) v add
thus, newrem ← oldrem v rem, newadd ← (oldadd & ~rem) v add
RETURN[newrem: Or[oldrem, rem], newadd: Or[And[oldadd, Not[rem]], add]];
};
TextLooksSupportImpl
CountRunsAfterChanges: PUBLIC PROC
[ref: Runs, start, len: INT, limit: INT ← MaxLen,
remove, add: Looks, merge: BOOL ← FALSE, firstLooks: Looks ← noLooks]
RETURNS [count: NAT, nonempty: BOOL, lastLooks: Looks] = {
-- stops counting when exceeds limit
-- if firstSize is > 0, then tries to merge with first run
ChangedBaseRuns: PROC
[x: BaseRuns, start, len, size: INT,
remove, add: Looks, limit: INT ← MaxLen]
RETURNS [count: NAT, firstLooks, lastLooks: Looks] = {
-- find the runs in x in [start..start+len)
-- modify looks according to remove&add
-- return count of distinct runs after modify
-- and looks of first & last runs after modify
first, last: NAT;
IF remove=allLooks THEN RETURN [1, add, add];
[first, last] ← FindBaseRuns[x, start, len];
count ← 1;
firstLooks ← lastLooks ← ModifyLooks[x[first].looks, remove, add];
FOR i: NAT IN (first..last] DO
newLooks: Looks ← ModifyLooks[x[i].looks, remove, add];
IF newLooks # lastLooks THEN {
IF (count ← count+1) > limit THEN RETURN;
lastLooks ← newLooks };
ENDLOOP };
c: NAT;
IF len=0 THEN RETURN [0, merge, firstLooks];
IF remove=allLooks THEN RETURN [
IF merge AND firstLooks=add THEN 0 ELSE 1, TRUE, add];
count ← 0;
DO
nonempty ← merge;
IF len=0 THEN { lastLooks ← firstLooks; RETURN };
IF ref=NIL THEN {
c ← IF merge AND firstLooks=add THEN 0 ELSE 1;
RETURN [count+c, TRUE, add] };
WITH ref SELECT FROM
x: REF RunsBody.base => {
size: INT;
firstLks, lastLks: Looks;
len ← MIN[len, CheckLongSub[size←TbaseSize[x], start]];
[c,firstLks,lastLks] ← ChangedBaseRuns[
x,start,len,size,remove,add,limit];
-- now compute count, lastLooks, and lastSize
IF c > limit THEN { count ← count+c; RETURN };
IF merge AND firstLooks=firstLks THEN c ← c-1;
RETURN [count+c, TRUE, lastLks] };
x: REF RunsBody.node.substr => {
len ← MIN[len, CheckLongSub[x.size, start]];
start ← start + x.start; ref ← x.base; LOOP};
x: REF RunsBody.node.concat => {
xpos: INT ← x.pos;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xpos THEN {
subLen: INT ← xpos - start;
IF len <= subLen THEN { ref ← x.base; LOOP };
[c, merge, firstLooks] ← CountRunsAfterChanges[
x.base,start,subLen,
limit,remove,add,merge,firstLooks];
count ← count+c; IF c > limit THEN RETURN;
limit ← limit-c;
start ← xpos; len ← len-subLen };
start ← start-xpos; ref ← x.rest; LOOP };
x: REF RunsBody.node.replace => {
xstart: INT ← x.start;
xnew: INT ← x.newPos;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xstart THEN {
subLen: INT ← xstart - start;
IF len <= subLen THEN {ref ← x.base; LOOP};
[c, merge, firstLooks] ← CountRunsAfterChanges[
x.base,start,subLen,
limit,remove,add,merge,firstLooks];
count ← count+c; IF c > limit THEN RETURN;
limit ← limit-c; start ← xstart; len ← len-subLen};
IF start < xnew THEN {
st: INT ← start - xstart;
subLen: INT ← xnew - start;
IF len <= subLen THEN {
start ← st; ref ← x.replace; LOOP};
[c, merge, firstLooks] ← CountRunsAfterChanges[
x.replace,st,subLen,limit,remove,add,merge,firstLooks];
count ← count+c; IF c > limit THEN RETURN;
limit ← limit-c; start ← xnew; len ← len-subLen};
start ← start - xnew + x.oldPos; ref ← x.base; LOOP};
x: REF RunsBody.node.change => {
xstart: INT ← x.start;
xend, subLen: INT;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xstart THEN {
IF len <= (subLen ← xstart-start) THEN {ref ← x.base; LOOP};
[c, merge, firstLooks] ← CountRunsAfterChanges[
x.base,start,subLen,limit,remove,add,merge,firstLooks];
count ← count+c; IF c > limit THEN RETURN;
limit ← limit-c; start ← xstart; len ← len-subLen};
IF start < (xend ← xstart+x.len) THEN {
newRemove, newAdd: Looks;
[newRemove, newAdd] ←
MergeChanges[x.remove, x.add, remove, add];
subLen ← MIN[xend-start,len];
[c, merge, firstLooks] ← CountRunsAfterChanges[
x.base,start,subLen,
limit,newRemove,newAdd,merge,firstLooks];
count ← count+c; IF c > limit THEN RETURN;
limit ← limit-c; start ← xend; len ← len-subLen};
ref ← x.base; LOOP};
ENDCASE => ERROR;
ENDLOOP};
ExtractRunsAfterChanges: PUBLIC PROC
[base: BaseRuns, ref: Runs, remove, add: Looks,
start: INT, len: INT, index: NAT ← 0]
RETURNS [NAT] = { -- value is next index
IF len>0 AND remove=allLooks THEN
RETURN [InsertRun[base, len, add, index]];
DO
IF len=0 THEN RETURN [index];
IF ref=NIL THEN -- treat as noLooks
RETURN [InsertRun[base, len, add, index]];
WITH ref SELECT FROM
x: REF RunsBody.base => {
first, last: NAT;
firstLen, lastLen, xloc, next, loc, size: INT;
newLooks, oldLooks: Looks;
len ← IF (size←TbaseSize[x]) < start THEN 0 ELSE MIN[len,size-start];
[first, last] ← FindBaseRuns[x, start, len];
[firstLen, lastLen] ← BaseRunLengths[x,start,len,first,last];
oldLooks ← ModifyLooks[x[first].looks, remove, add];
IF index=0 THEN { -- this is the first run to be extracted
loc ← firstLen; base[0] ← [loc, oldLooks]; index ← 1 }
ELSE {
loc ← base[index-1].after + firstLen;
IF base[index-1].looks=oldLooks -- merge runs
THEN base[index-1].after ← loc
ELSE { base[index] ← [loc, oldLooks]; index ← index+1 }};
xloc ← x[first].after;
FOR i: NAT IN (first..last] DO
newLooks ← ModifyLooks[x[i].looks, remove, add];
next ← IF i=last THEN xloc+lastLen ELSE x[i].after;
loc ← loc+next-xloc; xloc ← next;
IF newLooks # oldLooks THEN {
base[index] ← [loc, newLooks];
oldLooks ← newLooks; index ← index+1 }
ELSE base[index-1].after ← loc;
ENDLOOP;
RETURN [index] };
x: REF RunsBody.node.substr => {
len ← MIN[len, CheckLongSub[x.size, start]];
start ← start + x.start; ref ← x.base; LOOP};
x: REF RunsBody.node.concat => {
xpos: INT ← x.pos;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xpos THEN {
subLen: INT ← xpos - start;
IF len <= subLen THEN { ref ← x.base; LOOP };
index ← ExtractRunsAfterChanges[
base,x.base,remove,add,start,subLen,index];
start ← xpos; len ← len-subLen };
start ← start-xpos; ref ← x.rest; LOOP };
x: REF RunsBody.node.replace => {
xstart: INT ← x.start;
xnew: INT ← x.newPos;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xstart THEN {
subLen: INT ← xstart - start;
IF len <= subLen THEN {ref ← x.base; LOOP};
index ← ExtractRunsAfterChanges[
base,x.base,remove,add,start,subLen,index];
start ← xstart; len ← len-subLen};
IF start < xnew THEN {
st: INT ← start - xstart;
subLen: INT ← xnew - start;
IF len <= subLen THEN {
start ← st; ref ← x.replace; LOOP};
index ← ExtractRunsAfterChanges[
base,x.replace,remove,add,st,subLen,index];
start ← xnew; len ← len-subLen};
start ← start - xnew + x.oldPos; ref ← x.base; LOOP};
x: REF RunsBody.node.change => {
xstart: INT ← x.start;
xend, subLen: INT;
len ← MIN[len, CheckLongSub[x.size, start]];
IF start < xstart THEN {
IF len <= (subLen ← xstart-start) THEN {ref ← x.base; LOOP};
index ← ExtractRunsAfterChanges[
base,x.base,remove,add,start,subLen,index];
start ← xstart; len ← len-subLen};
IF start < (xend ← xstart+x.len) THEN {
newRemove, newAdd: Looks;
[newRemove,newAdd] ←
MergeChanges[x.remove,x.add,remove,add];
subLen ← MIN[xend-start,len];
index ← ExtractRunsAfterChanges[
base,x.base,newRemove,newAdd,start,subLen,index];
start ← xend; len ← len-subLen};
ref ← x.base; LOOP};
ENDCASE => ERROR;
ENDLOOP;
};
LooksStats: PUBLIC PROC [base: Runs, start: INT ← 0, len: INT ← MaxLen]
RETURNS [size, pieces, depth: INT] = {
rem, altDepth, subSize, subDepth, subPieces: INT;
size ← 0;
rem ← Size[base] - start;
altDepth ← 0;
IF len > rem THEN len ← rem;
pieces ← depth ← 0;
WHILE len > 0 DO
x: Runs ← base;
WITH base SELECT FROM
x: REF RunsBody.base => {
first, last: NAT;
[first,last] ← FindBaseRuns[x,start,len];
RETURN [size+last-first+1,pieces+1,MAX[depth,altDepth]] };
xNode: REF RunsBody.node => {
depth ← depth+1;
WITH xNode SELECT FROM
x: REF RunsBody.node.substr =>
{base ← x.base; start ← start + x.start; LOOP};
x: REF RunsBody.node.concat =>
{subLen: INT ← x.pos - start;
IF subLen > 0 THEN
{IF len <= subLen THEN {base ← x.base; LOOP};
[subSize,subPieces,subDepth] ← LooksStats[x.base, start, subLen];
pieces ← pieces+subPieces;
size ← size+subSize;
altDepth ← MAX[altDepth,depth+subDepth];
len ← len - subLen; start ← 0}
ELSE start ← -subLen;
base ← x.rest; LOOP};
x: REF RunsBody.node.replace =>
-- three pieces to consider (first, middle, last)
{xstart: INT ← x.start;
len1: INT ← xstart - start;
base ← x.base;
IF len1 > 0 THEN
{-- a piece in first section
IF len1 >= len THEN LOOP; -- only in first section
[subSize,subPieces,subDepth] ← LooksStats[base, start, len1];
pieces ← pieces+subPieces;
size ← size+subSize;
altDepth ← MAX[altDepth,depth+subDepth];
start ← xstart; len ← len - len1; len1 ← 0};
{xpos: INT ← x.newPos;
len2: INT ← xpos - start;
IF len2 <= 0 THEN
{-- no piece in middle section
start ← x.oldPos - len2; LOOP};
-- a piece in middle section of replace node
base ← x.replace; start ← -len1;
IF len2 >= len THEN LOOP; -- only in middle section
[subSize,subPieces,subDepth] ← LooksStats[base, start, len2];
pieces ← pieces+subPieces;
size ← size+subSize;
altDepth ← MAX[altDepth,depth+subDepth];
base ← x.base; start ← x.oldPos; len ← len - len2;
}};
x: REF RunsBody.node.change => {base ← x.base; LOOP};
ENDCASE => ERROR };
ENDCASE => ERROR;
ENDLOOP;
RETURN [0,0,0];
};
TbaseSize: PUBLIC PROC [x: BaseRuns] RETURNS [INT]
= { RETURN [IF x.length=0 THEN 0 ELSE x[x.length-1].after] };
Rope conversion
LooksToRope: PUBLIC PROC [looks: Looks] RETURNS [rope: Rope.ROPE] = {
FOR lk: Look IN Look DO
IF looks[lk] THEN rope ← Rope.Cat[rope, Rope.FromChar[lk]];
ENDLOOP;
};
RopeToLooks: PUBLIC PROC [rope: Rope.ROPE] RETURNS [looks: Looks] = {
looks ← noLooks;
FOR i: INT IN [0..Rope.Size[rope]) DO
char: CHAR ← Rope.Fetch[rope, i];
IF char IN Look THEN looks[char] ← TRUE;
ENDLOOP;
};
Edit operations
Size: PUBLIC PROC [base: Runs] RETURNS [size: INT] = {
RETURN [IF base = NIL THEN 0 ELSE WITH base SELECT FROM
x: REF RunsBody.base => IF x.length=0 THEN 0 ELSE x[x.length-1].after,
x: REF RunsBody.node.substr => x.size,
x: REF RunsBody.node.concat => x.size,
x: REF RunsBody.node.replace => x.size,
x: REF RunsBody.node.change => x.size,
ENDCASE => ERROR
]
};
Substr: PUBLIC PROC [base: Runs, start: INT, len: INT]
RETURNS [new: Runs] = {
DO
IF base=NIL OR len=0 THEN RETURN[NIL];
WITH base SELECT FROM
x: REF RunsBody.base => {
rem: INT;
IF (rem ← TbaseSize[x]-start) <= len THEN
IF start = 0 THEN RETURN [base] ELSE len ← rem;
};
x: REF RunsBody.node.substr => {
rem: INT;
IF (rem ← CheckLongSub[x.size, start]) <= len THEN
IF start = 0 THEN RETURN [base] ELSE len ← rem;
start ← start + x.start; base ← x.base; LOOP;
};
x: REF RunsBody.node.concat => {
xpos, rem: INT;
IF (rem ← CheckLongSub[x.size, start]) <= len THEN
IF start = 0 THEN RETURN [base] ELSE len ← rem;
IF start >= (xpos ← x.pos) THEN {
start ← start - xpos; base ← x.rest; LOOP
};
IF xpos >= start+len THEN {base ← x.base; LOOP};
};
x: REF RunsBody.node.replace => {
xstart, xnew, rem: INT;
IF (rem ← CheckLongSub[x.size, start]) <= len THEN
IF start = 0 THEN RETURN [base] ELSE len ← rem;
IF start >= (xnew ← x.newPos) THEN {
start ← start - xnew + x.oldPos; base ← x.base; LOOP
};
IF (rem ← start+len) <= (xstart ← x.start) THEN {
base ← x.base; LOOP
};
IF start >= xstart AND rem <= xnew THEN {
start ← start - xstart; base ← x.replace; LOOP
};
};
x: REF RunsBody.node.change => {
xstart: INT ← x.start;
xend: INT ← xstart+x.len;
IF start >= xend OR start+len <= xstart THEN {
base ← x.base; LOOP
};
};
ENDCASE => ERROR;
IF (new ← TryFlatSubstr[base, start, len]) # NIL THEN RETURN;
EXIT;
ENDLOOP;
IF base=NIL THEN ERROR;
RETURN [NEW[Tsubstr ← [node[substr[len, base, start]]]]];
};
TryFlatSubstr: PUBLIC PROC
[base: Runs, start, len: INT, limit: INT ← FlatMax]
RETURNS [BaseRuns] = { -- return NIL if couldn't flatten
count: INT;
numruns: NAT;
flat: BaseRuns;
[count, , ] ← CountRuns[base, start, len, limit];
IF count > limit THEN RETURN [NIL];
flat ← NewBase[numruns𡤌ount];
IF ExtractRuns[flat, base, start, len] # numruns THEN ERROR;
IF flat[numruns-1].after # len THEN ERROR;
RETURN [flat];
};
Flatten: PUBLIC PROC [base: Runs] RETURNS [new: Runs] = {
size, half: INT;
IF base=NIL THEN RETURN [NIL];
WITH base SELECT FROM
x: REF RunsBody.base => RETURN [x]; -- already flat
ENDCASE => NULL;
new ← TryFlatSubstr[base, 0, Size[base], 8000];
IF new#NIL THEN RETURN; -- else was too big to flatten in one piece
half ← (size ← Size[base])/2; -- flatten the halves
RETURN [Concat[
Flatten[Substr[base, 0, half]],
Flatten[Substr[base, half, size]],
half,
size-half]];
};
Concat: PUBLIC PROC
[base, rest: Runs, baseLen, restLen: INT] RETURNS [new: Runs] = TRUSTED {
c, numRuns, size, flatLen: INT;
split: NAT;
merge: BOOL;
looks: Looks;
IF base=NIL AND rest=NIL THEN RETURN[NIL];
IF restLen=0 THEN RETURN [base];
IF baseLen=0 THEN RETURN [rest];
size ← baseLen+restLen;
[numRuns, merge, looks] ← CountRuns[base, 0, baseLen, FlatMax];
IF numRuns <= FlatMax THEN { -- try flattening base
IF (new ← TryFlatConcatRest[base, rest, baseLen, restLen,
numRuns, merge, looks]) # NIL THEN RETURN;
otherwise try to break up rest
IF rest # NIL THEN WITH rest SELECT FROM
x: REF RunsBody.node.concat => { -- try to combine base & rest.base
[c, , ] ← CountRuns[x.base, 0, x.pos, FlatMax-numRuns, merge, looks];
IF (numRuns ← numRuns+c) <= FlatMax THEN { -- flatten
numruns: NAT;
flat: BaseRuns ← NewBase[numruns←numRuns];
split ← ExtractRuns[flat, base, 0, baseLen];
IF ExtractRuns[flat, x.base, 0, x.pos, split] # numruns
THEN ERROR;
flatLen ← baseLen+x.pos;
IF flat[numruns-1].after # flatLen THEN ERROR;
RETURN[NEW[Tconcat ← [node[concat
[size, flat, x.rest, flatLen]]]]]
}
};
ENDCASE => NULL;
};
IF base # NIL THEN WITH base SELECT FROM
x: REF RunsBody.node.concat => { -- try to combine base.rest & rest
baseRestLen: INT ← baseLen-x.pos;
[numRuns, merge, looks] ← CountRuns[x.rest, 0, baseRestLen, FlatMax];
IF numRuns <= FlatMax THEN {
[c, , ] ← CountRuns[rest, 0, restLen, FlatMax-numRuns, merge, looks];
IF (numRuns ← numRuns+c) <= FlatMax THEN { -- flatten
numruns: NAT;
flat: BaseRuns ← NewBase[numruns←numRuns];
split ← ExtractRuns[flat, x.rest, 0, baseRestLen];
IF ExtractRuns[flat, rest, 0, restLen, split] # numruns
THEN ERROR;
IF flat[numruns-1].after # baseRestLen+restLen THEN ERROR;
RETURN[NEW[Tconcat ← [node[concat
[size, x.base, flat, x.pos]]]]]
}
}
};
x: REF RunsBody.node.substr => {
see if doing concat of adjacent substr's
WITH rest SELECT FROM
y: REF RunsBody.node.substr => {
see if adjacent to x
IF x.base = y.base AND x.start+x.size = y.start THEN -- join them
RETURN[NEW[Tsubstr ←
[node[substr[size, x.base, x.start]]]]];
};
ENDCASE => NULL;
};
ENDCASE => NULL;
IF base=NIL THEN base ← MakeRun[baseLen];
IF rest=NIL THEN rest ← MakeRun[restLen];
RETURN[NEW[Tconcat ← [node[concat[size, base, rest, baseLen]]]]];
};
TryFlatConcat: PUBLIC PROC
[base, rest: Runs, baseLen, restLen: INT]
RETURNS [new: BaseRuns] = { -- returns NIL if too big to flatten
numRuns: INT;
merge: BOOL;
looks: Looks;
[numRuns, merge, looks] ← CountRuns[base, 0, baseLen, FlatMax];
IF numRuns > FlatMax THEN RETURN [NIL];
RETURN [TryFlatConcatRest[base, rest, baseLen, restLen, numRuns, merge, looks]];
};
TryFlatConcatRest: PUBLIC PROC
[base, rest: Runs, baseLen, restLen, numRuns: INT,
merge: BOOL, looks: Looks]
RETURNS [BaseRuns] = { -- returns NIL if too big to flatten
c: INT;
split, numruns: NAT;
flat: BaseRuns;
[c, , ] ← CountRuns[rest, 0, restLen, FlatMax-numRuns, merge, looks];
IF (numRuns ← numRuns+c) > FlatMax THEN RETURN [NIL];
flat ← NewBase[numruns←numRuns];
split ← ExtractRuns[flat, base, 0, baseLen];
IF ExtractRuns[flat, rest, 0, restLen, split] # numruns THEN
ERROR;
IF flat[numruns-1].after # baseLen+restLen THEN ERROR;
RETURN [flat];
};
Replace: PUBLIC PROC [
base: Runs, start, len: INT, replace: Runs,
baseSize, repSize: INT, tryFlat: BOOL ← TRUE]
RETURNS [new: Runs] = {
oldPos, newPos, size: INT;
IF base=NIL AND replace=NIL THEN RETURN [NIL];
oldPos ← start+len;
newPos ← start+repSize;
size ← baseSize-len+repSize;
IF repSize=0 THEN -- deleting
IF base=NIL OR (start=0 AND len=baseSize) THEN RETURN[NIL]
ELSE IF len=0 THEN RETURN[base];
IF tryFlat THEN {
merge: BOOL ← FALSE;
flat: BaseRuns;
looks: Looks;
c, numRuns: INT;
split, numruns: NAT;
Count: PROC [r: Runs, start, len: INT] RETURNS [INT] = TRUSTED {
IF len=0 THEN RETURN[numRuns];
[c, merge, looks] ← CountRuns[r, start, len, FlatMax-numRuns, merge, looks];
RETURN [numRuns←numRuns+c]
};
Extract: PROC [r: Runs, start, len: INT] = TRUSTED {
IF len > 0 THEN split ← ExtractRuns[flat, r, start, len, split]
};
numRuns ← 0;
IF Count[base, 0, start] <= FlatMax AND
Count[replace, 0, repSize] <= FlatMax AND
Count[base, oldPos, baseSize-oldPos] <= FlatMax THEN {
flat ← NewBase[numruns←numRuns]; split ← 0;
Extract[base, 0, start]; Extract[replace, 0, repSize];
Extract[base, oldPos, baseSize-oldPos];
IF split # numruns THEN ERROR;
IF flat[numruns-1].after # size THEN ERROR;
RETURN [flat]
}
};
WHILE base # NIL DO WITH base SELECT FROM
x: REF RunsBody.node.replace => {
xnewPos: INT ← x.newPos;
xstart: INT ← x.start;
xsize: INT;
IF start <= xstart AND oldPos >= xnewPos THEN {
replacing the replacement
oldPos ← x.oldPos+(oldPos-xnewPos); len ← oldPos-start;
base ← x.base; LOOP
}
ELSE IF repSize = 0 AND start > xstart AND
oldPos = xnewPos AND -- deleting end of prior replacement
(new ← TryFlatSubstr[x.replace, 0, start-xstart])#NIL THEN {
newPos ← start; oldPos ← x.oldPos; start ← xstart;
replace ← new; base ← x.base
}
ELSE IF repSize = 0 AND start = xstart AND
oldPos < xnewPos AND -- deleting start of prior replacement
(new ← TryFlatSubstr[x.replace, len, xnewPos-oldPos])#NIL THEN {
newPos ← start+xnewPos-oldPos; oldPos ← x.oldPos;
replace ← new; base ← x.base
}
ELSE IF start = xnewPos AND -- replacing just after prior replacement
(new ← TryFlatConcat[x.replace, replace, xsize←xnewPos-xstart, repSize])#NIL
THEN {
start ← xstart;
len ← len+x.oldPos-xstart; oldPos ← start+len;
repSize ← xsize+repSize; newPos ← start+repSize;
replace ← new; base ← x.base; LOOP
}
ELSE IF start+len = xstart AND -- replacing just before prior replacement
(new ← TryFlatConcat[replace, x.replace, repSize, xsize←xnewPos-xstart])#NIL
THEN {
len ← len+x.oldPos-xstart; oldPos ← start+len;
repSize ← xsize+repSize; newPos ← start+repSize;
replace ← new; base ← x.base; LOOP
}
};
x: REF RunsBody.node.concat => {
xpos: INT ← x.pos;
IF start=xpos AND len=0 THEN { -- insert between base&rest
first try concat of x.base&replacement
IF (new ← TryFlatConcat[x.base, replace, xpos, repSize])#NIL
THEN RETURN [NEW[Tconcat ←
[node[concat[size, new, x.rest, xpos+repSize]]]]];
otherwise try concat of replacement&x.rest
IF (new ← TryFlatConcat[replace, x.rest, repSize, x.size-xpos])#NIL
THEN RETURN [NEW[Tconcat ←
[node[concat[size, x.base, new, x.pos]]]]]
}
};
ENDCASE => NULL;
EXIT;
ENDLOOP;
IF base=NIL THEN base ← MakeRun[baseSize];
IF replace=NIL THEN replace ← MakeRun[repSize];
RETURN [NEW[Treplace ← [node[replace[size, base, replace, start, oldPos, newPos]]]]];
};
Copy: PUBLIC PROC [
dest: Runs, destLoc: INT, source: Runs,
start, len, destSize: INT]
RETURNS [Runs] = {
merge: BOOL ← FALSE;
flat: BaseRuns;
looks: Looks;
c, numRuns: INT;
split, numruns: NAT;
Count: PROC [base: Runs, start, len: INT] RETURNS [INT] = {
IF len=0 THEN RETURN[numRuns];
[c, merge, looks] ← CountRuns[base, start, len, FlatMax-numRuns, merge, looks];
RETURN [numRuns←numRuns+c]
};
Extract: PROC [base: Runs, start, len: INT] = {
IF len > 0 THEN split ← ExtractRuns[flat, base, start, len, split]
};
IF dest=NIL AND source=NIL THEN RETURN[NIL];
numRuns ← 0;
IF Count[dest, 0, destLoc] > FlatMax OR
Count[source, start, len] > FlatMax OR
Count[dest, destLoc, destSize-destLoc] > FlatMax THEN RETURN [
Replace[dest, destLoc, 0, Substr[source, start, len], destSize, len, FALSE]];
IF numRuns=0 THEN RETURN [NIL];
flat ← NewBase[numruns←numRuns]; split ← 0;
Extract[dest, 0, destLoc]; Extract[source, start, len];
Extract[dest, destLoc, destSize-destLoc];
IF split # numruns THEN ERROR;
IF flat[numruns-1].after # destSize+len THEN ERROR;
RETURN [flat];
};
General operations
CreateRun: PUBLIC PROC [len: INT, looks: Looks ← noLooks]
RETURNS [new: Runs] = {
base: BaseRuns;
IF looks=noLooks OR len=0 THEN RETURN [NIL];
base ← NewBase[1];
base[0] ← [len, looks];
RETURN [base];
};
MakeRun: PUBLIC PROC [len: INT] RETURNS [new: Runs] = {
base: BaseRuns;
IF len=0 THEN RETURN [NIL];
base ← NewBase[1];
base[0] ← [len, noLooks];
RETURN [base];
};
FetchLooks: PUBLIC PROC
[runs: Runs, index: INT] RETURNS [Looks] = {
returns the looks for the character at the given location
remove, add: Looks ← noLooks;
changeLooks: BOOL ← FALSE;
DO IF runs=NIL THEN RETURN [noLooks];
WITH runs SELECT FROM
x: REF RunsBody.base => {
looks: Looks ← x[BaseRun[x, index]].looks;
IF changeLooks THEN looks ← ModifyLooks[looks, remove, add];
RETURN [looks]
};
x: REF RunsBody.node.substr =>
IF index < x.size THEN {
index ← index + x.start; runs ← x.base; LOOP
};
x: REF RunsBody.node.concat => {
IF index < x.size THEN {
IF index < x.pos
THEN {runs ← x.base; LOOP}
ELSE {index ← index - x.pos; runs ← x.rest; LOOP};
};
};
x: REF RunsBody.node.replace => IF index < x.size THEN {
IF index < x.start THEN {runs ← x.base; LOOP};
IF index < x.newPos THEN {
index ← index - x.start; runs ← x.replace; LOOP
};
index ← index - x.newPos + x.oldPos; runs ← x.base; LOOP
};
x: REF RunsBody.node.change => {
IF index IN [x.start..x.start+x.len) THEN {
[remove, add] ← MergeChanges[x.remove, x.add, remove, add];
IF remove=allLooks THEN RETURN [add];
changeLooks ← TRUE
};
runs ← x.base; LOOP
};
ENDCASE => ERROR;
ERROR OutOfBounds;
ENDLOOP;
};
Operation to change looks
ChangeLooks: PUBLIC PROC [
runs: Runs, size: INT, remove, add: Looks,
start: INT ← 0, len: INT ← MaxLen]
RETURNS [new: Runs] = {
c, numRuns, end: INT;
merge: BOOL;
looks: Looks;
IF runs=NIL AND add=noLooks THEN RETURN [NIL];
IF start >= size OR len=0 THEN RETURN [runs];
end ← start + (len ← MIN[len, size-start]);
IF runs # NIL THEN { -- see if not really changing anything
changed: BOOL ← FALSE;
loc, runLen: INT ← start;
runrdr: RunReader.Ref ← RunReader.GetRunReader[];
RunReader.SetPosition[runrdr, runs, start];
UNTIL loc >= end DO -- check the runs in the section to be changed
lks: Looks;
[runLen, lks] ← RunReader.Get[runrdr];
IF And[lks, add]#add OR And[lks, remove]#noLooks THEN { changed ← TRUE; EXIT };
loc ← loc+runLen;
ENDLOOP;
RunReader.FreeRunReader[runrdr];
IF NOT changed THEN RETURN [runs];
};
[numRuns, merge, looks] ← CountRuns[runs, 0, start, FlatMax];
IF numRuns <= FlatMax THEN {
[c, merge, looks] ← CountRunsAfterChanges[
runs, start, len, FlatMax-numRuns, remove, add, merge, looks];
IF (numRuns ← numRuns+c) <= FlatMax THEN {
[c, , ] ← CountRuns[runs, end, size-end, FlatMax-numRuns, merge, looks];
IF (numRuns ← numRuns+c) <= FlatMax THEN {
split, numruns: NAT;
flat: BaseRuns ← NewBase[numruns←numRuns];
split ← ExtractRuns[flat, runs, 0, start];
split ← ExtractRunsAfterChanges[flat, runs, remove, add, start, len, split];
IF ExtractRuns[flat, runs, end, size-end, split] # numruns THEN ERROR;
IF flat[numruns-1].after # size THEN ERROR;
RETURN [flat]
}
}
};
IF runs # NIL THEN WITH runs SELECT FROM
x: REF RunsBody.node.change => IF x.start=start AND x.len=len THEN {
[remove, add] ← MergeChanges[x.remove, x.add, remove, add];
runs ← x.base
};
ENDCASE => NULL;
IF runs = NIL THEN runs ← MakeRun[size];
RETURN[NEW[Tchange ← [node[change[size, runs, remove, add, start, len]]]]];
};
END.