TextLooksBasicImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
written by Bill Paxton, February 1981
Bill Paxton, 7-Dec-81 11:33:25
Maxwell, January 5, 1983 3:55 pm
Russ Atkinson, July 25, 1983 3:41 pm
Doug Wyatt, March 3, 1985 2:56:07 pm PST
Michael Plass, April 8, 1985 3:33:49 pm PST
DIRECTORY
Basics USING [BITAND, BITNOT, BITOR],
PrincOpsUtils USING [LongCopy],
TextLooks USING [BaseRuns, CreateRun, FetchLooks, FlatMax, Looks, MaxOffset, noLooks, Offset, Replace, Run, Runs, RunsBody, Size, Tconcat, Treplace],
TextLooksSupport USING [CheckLongSub, CountRunsAfterChanges, ExtractRunsAfterChanges, MakeRun, Short, TbaseSize];
TextLooksBasicImpl:
CEDAR
PROGRAM
IMPORTS Basics, PrincOpsUtils, TextLooks, TextLooksSupport
EXPORTS TextLooks, TextLooksSupport
= {
RunsBody: TYPE ~ TextLooks.RunsBody;
ReplaceByRun:
PUBLIC
PROC [dest: TextLooks.Runs, start, len, runLen, destSize: TextLooks.Offset, inherit:
BOOL, looks: TextLooks.Looks]
RETURNS [TextLooks.Runs] = {
merge: BOOL ← FALSE;
mergeLooks: TextLooks.Looks;
split, numruns: NAT;
flat: TextLooks.BaseRuns;
c, numRuns, oldPos, size: TextLooks.Offset;
Count:
PROC [start, len: TextLooks.Offset]
RETURNS [TextLooks.Offset] = {
IF len=0 THEN RETURN[numRuns];
[c, merge, mergeLooks] ←
CountRuns[dest, start, len, TextLooks.FlatMax-numRuns, merge, mergeLooks];
RETURN [numRuns←numRuns+c];
};
AddIt:
PROC
RETURNS [TextLooks.Offset] = {
c ← IF merge AND mergeLooks=looks THEN 0 ELSE 1;
merge ← TRUE; mergeLooks ← looks;
RETURN [numRuns←numRuns+c];
};
Extract:
PROC [start, len: TextLooks.Offset] = {
IF len > 0 THEN split ← ExtractRuns[flat, dest, start, len, split];
};
TryFlatAppendRun:
PROC [base: TextLooks.Runs]
RETURNS [TextLooks.Runs] = {
flat: TextLooks.BaseRuns;
size: TextLooks.Offset;
[numRuns, merge, mergeLooks] ← CountRuns[base, 0, size←TextLooks.Size[base], TextLooks.FlatMax];
IF numRuns > TextLooks.FlatMax OR AddIt[] > TextLooks.FlatMax THEN RETURN [NIL];
flat ← NewBase[numruns←TextLooksSupport.Short[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 [TextLooks.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 ← TextLooks.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=TextLooks.noLooks THEN RETURN[NIL];
numRuns ← 0; oldPos ← start+len; size ← destSize-len+runLen;
IF Count[0, start] > TextLooks.FlatMax
OR AddIt[] > TextLooks.FlatMax
OR Count[oldPos, destSize-oldPos] > TextLooks.FlatMax
THEN {
newPos: TextLooks.Offset ← start+runLen;
replace, new: TextLooks.Runs;
WHILE dest #
NIL
DO
WITH dest
SELECT
FROM
x:
REF RunsBody.node.replace => {
xnewPos: TextLooks.Offset ← x.newPos;
xstart: TextLooks.Offset ← 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: TextLooks.Offset ← x.pos;
IF start=xpos AND len=0 AND
(new ← TryFlatAppendRun[x.base])#
NIL
THEN
RETURN [
NEW[TextLooks.Tconcat ← [node[concat
[size, new, x.rest, xpos+runLen]]]]];
};
ENDCASE;
EXIT;
ENDLOOP;
IF replace=NIL AND (replace ← TextLooks.CreateRun[runLen, looks])=NIL THEN
replace ← TextLooksSupport.MakeRun[runLen];
IF dest=NIL THEN dest ← TextLooksSupport.MakeRun[destSize];
RETURN [NEW[TextLooks.Treplace ← [node[replace[size, dest, replace, start, oldPos, newPos]]]]]
};
IF numRuns=0 THEN RETURN[NIL];
flat ← NewBase[numruns←TextLooksSupport.Short[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: TextLooks.Runs, start, len: TextLooks.Offset, limit: TextLooks.Offset ← TextLooks.MaxOffset,
merge: BOOL ← FALSE, firstLooks: TextLooks.Looks ← TextLooks.noLooks]
RETURNS [count: TextLooks.Offset, nonempty: BOOL, lastLooks: TextLooks.Looks] = {
stops counting when exceeds limit
if merge is true, then doesn't count first run if its looks=firstLooks
c: TextLooks.Offset;
count ← 0;
DO nonempty ← merge;
IF len=0 THEN { lastLooks ← firstLooks; RETURN };
IF runs=
NIL
THEN {
c ← IF merge AND firstLooks=TextLooks.noLooks THEN 0 ELSE 1;
RETURN [count+c, TRUE, TextLooks.noLooks]
};
WITH runs
SELECT
FROM
x:
REF RunsBody.base => {
first, last: NAT;
len ← MIN[len, TextLooksSupport.CheckLongSub[TextLooksSupport.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, TextLooksSupport.CheckLongSub[x.size, start]];
start ← start + x.start; runs ← x.base; LOOP
};
x:
REF RunsBody.node.concat => {
xpos: TextLooks.Offset ← x.pos;
len ← MIN[len, TextLooksSupport.CheckLongSub[x.size, start]];
IF start < xpos
THEN {
subLen: TextLooks.Offset ← 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: TextLooks.Offset ← x.start;
xnew: TextLooks.Offset ← x.newPos;
len ← MIN[len, TextLooksSupport.CheckLongSub[x.size, start]];
IF start < xstart
THEN {
subLen: TextLooks.Offset ← 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: TextLooks.Offset ← start - xstart;
subLen: TextLooks.Offset ← 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: TextLooks.Offset ← x.start;
xend, subLen: TextLooks.Offset;
len ← MIN[len, TextLooksSupport.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] ← TextLooksSupport.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: TextLooks.BaseRuns, ref: TextLooks.Runs, start, len: TextLooks.Offset, 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, TextLooks.noLooks, index]];
WITH ref
SELECT
FROM
x:
REF RunsBody.base => {
firstLen, lastLen, xloc, next, loc: TextLooks.Offset;
first, last: NAT;
len ← MIN[len, TextLooksSupport.CheckLongSub[TextLooksSupport.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, TextLooksSupport.CheckLongSub[x.size, start]];
start ← start + x.start; ref ← x.base; LOOP
};
x:
REF RunsBody.node.concat => {
xpos: TextLooks.Offset ← x.pos;
len ← MIN[len, TextLooksSupport.CheckLongSub[x.size, start]];
IF start < xpos
THEN {
subLen: TextLooks.Offset ← 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: TextLooks.Offset ← x.start;
xnew: TextLooks.Offset ← x.newPos;
len ← MIN[len, TextLooksSupport.CheckLongSub[x.size, start]];
IF start < xstart
THEN {
subLen: TextLooks.Offset ← 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: TextLooks.Offset ← start - xstart;
subLen: TextLooks.Offset ← 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: TextLooks.Offset ← x.start;
xend, subLen: TextLooks.Offset;
len ← MIN[len, TextLooksSupport.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 ← TextLooksSupport.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 [TextLooks.BaseRuns] = {
RETURN [NEW[base TextLooks.RunsBody[runs]]];
};
BaseRun: PUBLIC PROC
[x: TextLooks.BaseRuns, index: TextLooks.Offset, lower:
NAT ← 0, upper:
NAT ←
LAST[
NAT]]
RETURNS [NAT] = {
len: NAT;
size: TextLooks.Offset;
IF index = 0 THEN RETURN [0];
IF (len←x.length) <= 1 THEN RETURN [0];
IF index+1 >= (size←TextLooksSupport.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: TextLooks.BaseRuns, toLoc, fromLoc, nRuns:
NAT] =
TRUSTED {
RunsOffset: NAT = SIZE[base TextLooks.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[TextLooks.Run]+RunsOffset,
to: LOOPHOLE[to, LONG POINTER]+toLoc*SIZE[TextLooks.Run]+RunsOffset,
nwords: nLeft*SIZE[TextLooks.Run]]
};
InsertRun: PUBLIC PROC [base: TextLooks.BaseRuns, len: TextLooks.Offset, looks: TextLooks.Looks, index: NAT]
RETURNS [
NAT] = {
-- value is next index
IF index=0 THEN { base[0] ← [len, looks]; index ← 1 }
ELSE {
loc: TextLooks.Offset ← 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: TextLooks.BaseRuns, start, len: TextLooks.Offset]
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: TextLooks.BaseRuns, start, len: TextLooks.Offset, first, last: NAT]
RETURNS [firstLen, lastLen: TextLooks.Offset] = {
IF first=last THEN RETURN[len, len];
RETURN[x[first].after-start, start+len-x[last-1].after]
};
Lks: TYPE = ARRAY [0..1] OF CARDINAL;
ModifyLooks:
PUBLIC
PROC [old, remove, add: TextLooks.Looks]
RETURNS [TextLooks.Looks] = {
modified looks are == (old & ~remove) v add
oldlks: Lks ← LOOPHOLE[old];
addlks: Lks ← LOOPHOLE[add];
remlks: Lks ← LOOPHOLE[remove];
newlks: Lks;
newlks[0] ← Basics.BITOR[addlks[0], Basics.BITAND[Basics.BITNOT[remlks[0]], oldlks[0]]];
newlks[1] ← Basics.BITOR[addlks[1], Basics.BITAND[Basics.BITNOT[remlks[1]], oldlks[1]]];
RETURN [LOOPHOLE[newlks]];
};
MergeChanges: PUBLIC PROC [oldrem, oldadd, rem, add: TextLooks.Looks]
RETURNS [newrem, newadd: TextLooks.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
oldaddlks: Lks ← LOOPHOLE[oldadd];
oldremlks: Lks ← LOOPHOLE[oldrem];
remlks: Lks ← LOOPHOLE[rem];
addlks: Lks ← LOOPHOLE[add];
newremlks, newaddlks: Lks;
newremlks[0] ← Basics.BITOR[oldremlks[0], remlks[0]];
newremlks[1] ← Basics.BITOR[oldremlks[1], remlks[1]];
newaddlks[0] ← Basics.BITOR[addlks[0], Basics.BITAND[Basics.BITNOT[remlks[0]], oldaddlks[0]]];
newaddlks[1] ← Basics.BITOR[addlks[1], Basics.BITAND[Basics.BITNOT[remlks[1]], oldaddlks[1]]];
RETURN [LOOPHOLE[newremlks], LOOPHOLE[newaddlks]];
};
}.