TextLooksBasicImpl.mesa
Copyright © 1985, 1986 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
Michael Plass, April 8, 1985 3:33:49 pm PST
Doug Wyatt, September 3, 1986 1:08:08 pm PDT
DIRECTORY
Basics USING [DoubleAnd, DoubleNot, DoubleOr],
PrincOpsUtils USING [LongCopy],
TextLooks USING [BaseRuns, CreateRun, FetchLooks, FlatMax, Looks, MaxLen, noLooks, 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
= BEGIN
Looks: TYPE ~ TextLooks.Looks;
Runs: TYPE ~ TextLooks.Runs;
RunsBody: TYPE ~ TextLooks.RunsBody;
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: TextLooks.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, TextLooks.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: TextLooks.BaseRuns;
size: INT;
[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: 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[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: Runs, start, len:
INT, limit:
INT ← TextLooks.MaxLen, merge:
BOOL ←
FALSE, firstLooks: Looks ← TextLooks.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=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: INT ← x.pos;
len ← MIN[len, TextLooksSupport.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, TextLooksSupport.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, 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: 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, TextLooks.noLooks, index]];
WITH ref
SELECT
FROM
x:
REF RunsBody.base => {
firstLen, lastLen, xloc, next, loc: INT;
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: INT ← x.pos;
len ← MIN[len, TextLooksSupport.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, TextLooksSupport.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, 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:
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←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:
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: TextLooks.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: TextLooks.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]];
};
END.