RopeEditImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
written by Bill Paxton, February 1981
edited by Paxton, October 29, 1982 8:45 am
edited by Maxwell, January 5, 1983 11:57 am
Russ Atkinson, September 23, 1983 7:02 pm
Paul Rovner, August 10, 1983 4:20 pm
Doug Wyatt, January 17, 1984 4:50:45 pm PST
Michael Plass, February 26, 1985 3:36:02 pm PST
DIRECTORY
FS USING [Open, OpenFile, StreamFromOpenFile, StreamOpen],
IO USING [Close, PutRope, SetIndex, SetLength, STREAM],
Rope,
RopeEdit USING [CharPropertyTable, CR, MaxLen, Offset, SP, TAB],
RopeFrom USING [File, MaxLen, Offset, Stream],
RopeIO USING [],
RopePrivate USING [InlineDepth, MaxDepth];
RopeEditImpl: CEDAR MONITOR
IMPORTS FS, IO, Rope, RopePrivate, RopeFrom
EXPORTS RopeEdit, RopeIO
SHARES Rope
= BEGIN OPEN RopeEdit;
ROPE: TYPE = Rope.ROPE;
Depth: PUBLIC PROC [rope: ROPE] RETURNS [depth: INTEGER] = {
RETURN [RopePrivate.InlineDepth[rope]]
};
-- Edit
TraceRec: TYPE ~ RECORD [
action: ATOM,
start: INT,
len: INT,
size: INT,
depth: INT,
rope: ROPE,
with: ROPE
];
traceTable: ARRAY [0..32) OF TraceRec;
traceTableIndex: NAT ← 0;
Trace: PROC [action: ATOM, base: ROPE, start: INT, len: INT, with: ROPE ← NIL] = {
traceTable[traceTableIndex ← (traceTableIndex + 1) MOD 32] ← [action, start, len, Rope.Size[base], Depth[base], base, with];
};
GetTrace: PROC RETURNS [t: ARRAY [0..25) OF TraceRec] = {
k: INTEGER ← traceTableIndex;
FOR i: NAT DECREASING IN [0..25) DO
t[i] ← traceTable[k];
k ← k - 1;
IF k < 0 THEN k ← k + 32;
ENDLOOP;
};
Substr: PUBLIC PROC [base: ROPE, start: Offset ← 0, len: Offset ← MaxLen] RETURNS [ROPE] = {
RETURN [CheckBalance[Rope.Substr[base: base, start: start, len: len]]];
};
Concat: PUBLIC PROC [base, rest: ROPE, baseLen, restLen: Offset ← MaxLen]
RETURNS [new: ROPE] = {
IF Rope.Size[rest] > restLen THEN rest ← Rope.Substr[base: rest, start: 0, len: restLen];
IF Rope.Size[base] > baseLen THEN rest ← Rope.Substr[base: base, start: 0, len: baseLen];
RETURN [CheckBalance[Rope.Concat[base, rest]]];
};
Copy: PUBLIC PROC [dest: ROPE, destLoc: INT, source: ROPE, start: INT, len: INT, destSize: INT] RETURNS [ROPE] = {
IF destLoc > destSize THEN destLoc ← destSize;
RETURN [
Replace[base: dest, start: destLoc, len: 0, replace: Substr[source, start, len], baseSize: destSize, repSize: len]
]
};
SemiFlatten: PUBLIC PROC [base: ROPE] RETURNS [flattened: ROPE] = {
flattened ← Balance[base];
};
RopeStats: PUBLIC PROC [base: ROPE, start: Offset ← 0, len: Offset ← MaxLen]
RETURNS [size, pieces, depth: Offset] = {
RETURN [0,0,0];
};
-- **** IO Operations ****
PutRope: PUBLIC PROC [stream: IO.STREAM, rope: ROPE] = {
IO.PutRope[stream, rope];
};
GetRope: PUBLIC PROC [stream: IO.STREAM, len: Offset ← MaxLen] RETURNS [ROPE] = {
RETURN [RopeFrom.Stream[stream, len]];
};
-- **** Filing Operations ****
ToFile: PUBLIC PROC [fileName, rope: ROPE, start: Offset ← 0] = {
WriteFile[FS.StreamOpen[fileName, $create], rope, start];
};
ToFileC: PUBLIC PROC [openFile: FS.OpenFile, rope: ROPE, start: Offset ← 0] = {
WriteFile[FS.StreamFromOpenFile[openFile, $write], rope, start];
};
WriteFile: PROC [stream: IO.STREAM, rope: ROPE, start: Offset] = {
IO.SetLength[stream, start];
IO.SetIndex[stream, start];
PutRope[stream, rope];
IO.Close[stream];
};
FromFile: PUBLIC PROC [fileName: ROPE,
start: Offset ← 0, len: Offset ← MaxLen] RETURNS [ROPE] = {
openFile: FS.OpenFile ~ FS.Open[fileName, $read];
RETURN[FromFileC[openFile, start, len]];
};
FromFileC: PUBLIC PROC [openFile: FS.OpenFile,
start: Offset ← 0, len: Offset ← MaxLen] RETURNS [ROPE] = {
RETURN [RopeFrom.File[openFile, start, len, FALSE, MaxLen]];
};
***** Replace Operations
ReplaceByChar: PUBLIC PROC [base: ROPE, char: CHAR, start: INT, len: INT, baseSize: INT] RETURNS [new: ROPE] = {
This one is, in fact, not called very often, so no optimization is needed.
new ← Replace[base: base, start: start, len: len, replace: Rope.FromChar[char], baseSize: baseSize, repSize: MaxLen];
};
ReplaceByString: PUBLIC PROC [base: ROPE, string: REF READONLY TEXT, stringStart: NAT, stringNum: NAT, start: INT, len: INT, baseSize: INT] RETURNS [new: ROPE ← NIL] = {
Chars: PROC RETURNS [CHAR] ~ {c: CHAR ← string[i]; i ← i + 1; RETURN [c]};
i: NAT ← stringStart ← MIN[string.length, stringStart];
stringNum ← MIN[string.length-stringStart, stringNum];
IF baseSize < Rope.InlineSize[base] THEN base ← Rope.Substr[base, 0, baseSize];
new ← Rope.Replace[base, start, len, Rope.FromProc[stringNum, Chars]];
new ← CheckBalance[new];
};
Replace: PUBLIC PROC [base: ROPE, start: INT, len: INT, replace: ROPE, baseSize: INT, repSize: INT] RETURNS [new: ROPE ← NIL] = {
IF baseSize < Rope.Size[base] THEN base ← Rope.Substr[base: base, start: 0, len: baseSize];
IF repSize < Rope.Size[replace] THEN replace ← Rope.Substr[replace, 0, repSize];
new ← Rope.Replace[base: base, start: start, len: len, with: replace];
new ← CheckBalance[new];
};
***** New Balance implementation
CheckBalance: PROC [base: ROPE] RETURNS [ROPE] ~ {
Balances the rope, if necessary.
Tests against RopePrivate.MaxDepth-1 to get control before Rope.Balance does.
IF RopePrivate.InlineDepth[base] >= INTEGER[RopePrivate.MaxDepth]-1 THEN base ← Balance[base];
RETURN [base];
};
Part: TYPE ~ RECORD [base: ROPE, start: INT, end: INT];
Must have 0 <= start <= end <= Size[base];
minSizeForHeight: ARRAY [0..RopePrivate.MaxDepth] OF INT ~ InitMinSizeForHeight[];
InitMinSizeForHeight: PROC RETURNS [h: ARRAY [0..RopePrivate.MaxDepth] OF INT] ~ {
h[0] ← 0; -- A flat rope is always balanced.
h[1] ← Rope.FlatMax+1; -- Must be at least this big to warrant any structure at all.
FOR i: NAT IN [2..RopePrivate.MaxDepth) DO
Use Fibonacci recurrence to compute rest.
Be careful about overflow here...
IF INT.LAST - h[i-1] < h[i-2] THEN h[i] ← INT.LAST
ELSE h[i] ← h[i-1] + h[i-2];
ENDLOOP;
};
PartIsBalanced: PROC [part: Part] RETURNS [BOOL] ~ {
Examines only the root.
size: INT ~ Rope.InlineSize[part.base];
height: INT ~ RopePrivate.InlineDepth[part.base];
IF part.start # 0
OR part.end # size
OR height > RopePrivate.MaxDepth
OR size < minSizeForHeight[height]
THEN RETURN [FALSE];
WITH part.base SELECT FROM
substr: REF Rope.RopeRep.node.substr => RETURN [height<=1];
concat: REF Rope.RopeRep.node.concat => RETURN [TRUE];
replace: REF Rope.RopeRep.node.replace => RETURN [FALSE];
ENDCASE => RETURN [TRUE];
};
Balance: PROC [rope: ROPE] RETURNS [ROPE] ~ {
a: ARep; -- An extensible array that is very cheap if it is small.
aN: INT ← 0;
AElement: TYPE ~ RECORD [base: ROPE, size: INT];
d: NAT ~ 40;
ARep: TYPE
~ RECORD[index: INT𡤀, sub: ARRAY [0..d) OF AElement, rest: REF ARep←NIL];
accel: REF ARep ← NIL;
StoreA: PROC [i: INT, e: AElement] ~ {
IF i-a.index < d THEN a.sub[i-a.index] ← e
ELSE {
IF a.rest = NIL THEN {a.rest ← accel ← NEW[ARep]; accel.index ← d};
IF i < accel.index THEN accel ← a.rest;
WHILE i-accel.index >= d DO
IF accel.rest = NIL THEN {accel.rest ← NEW[ARep]; accel.rest.index�l.index+d};
accel ← accel.rest;
ENDLOOP;
accel.sub[i-accel.index] ← e;
};
};
ASub: PROC [i: INT] RETURNS [e: AElement] ~ {
IF i-a.index < d THEN e ← a.sub[i-a.index]
ELSE {
IF i < accel.index THEN accel ← a.rest;
WHILE i-accel.index >= d DO accel ← accel.rest ENDLOOP;
e ← accel.sub[i-accel.index];
};
};
SavePart: PROC [part: Part] ~ {
IF part.end > part.start THEN {
rope: ROPE ← Rope.Substr[part.base, part.start, part.end-part.start];
StoreA[aN, [rope, Rope.InlineSize[rope]]];
aN ← aN + 1;
};
};
BalanceRange: PROC [first: INT, end: INT, size: INT] RETURNS [ROPE] ~ {
Balances pieces [first..end), whose sizes must sum to size.
IF first = end THEN RETURN[NIL]
ELSE IF end-first = 1 THEN RETURN[ASub[first].base]
ELSE {
i: INT ← first+1;
sizetoi: INT ← ASub[first].size;
FOR sizei: INT ← ASub[i].size, ASub[i].size
WHILE i < end-1
AND ((sizetoi+sizei)*2 < size OR ABS[sizetoi*2-size] > ABS[(sizetoi+sizei)*2-size]) DO
sizetoi ← sizetoi + sizei;
i ← i + 1;
ENDLOOP;
RETURN[Rope.Concat[BalanceRange[first, i, sizetoi], BalanceRange[i, end, size-sizetoi]]];
};
};
part: Part ~ [rope, 0, Rope.Size[rope]];
MapParts[part, SavePart, PartIsBalanced];
RETURN [BalanceRange[0, aN, part.end-part.start]]
};
BadPart: SIGNAL ~ CODE;
MapParts: PROC[part: Part, action: PROC[Part], stopDescent: PROC[Part]RETURNS[BOOL]←NIL] ~{
IF stopDescent#NIL AND stopDescent[part] THEN action[part]
ELSE {
size: INT ~ Rope.InlineSize[part.base];
IF part.start < 0 OR part.end NOT IN [part.start..part.start+size] THEN ERROR BadPart;
WITH part.base SELECT FROM
substr: REF Rope.RopeRep.node.substr => {
MapParts[[substr.base, substr.start+part.start, substr.start+part.end], action, stopDescent];
};
concat: REF Rope.RopeRep.node.concat => {
IF part.start < concat.pos THEN {
MapParts[[concat.base, part.start, MIN[part.end, concat.pos]], action, stopDescent];
};
IF part.end > concat.pos THEN {
newStart: INT ← MAX[part.start-concat.pos, 0];
newEnd: INT ← part.end-concat.pos;
MapParts[[concat.rest, newStart, newEnd], action, stopDescent];
};
};
replace: REF Rope.RopeRep.node.replace => {
len1: INT ~ replace.start;
len2: INT ~ replace.newPos-replace.start;
len3: INT ~ replace.size-replace.newPos;
offset3: INT ~ replace.oldPos;
IF part.start < len1 THEN {
MapParts[[replace.base, part.start, MIN[part.end, len1]], action, stopDescent];
};
IF part.start < len1+len2 AND part.end > len1 THEN {
newStart: INT ~ MAX[part.start-len1, 0];
newEnd: INT ~ MIN[part.end-len1, len2];
MapParts[[replace.replace, newStart, newEnd], action, stopDescent];
};
IF part.end > len1+len2 THEN {
newStart: INT ← MAX[part.start-(len1+len2), 0]+offset3;
newEnd: INT ← MIN[part.end-(len1+len2), len3]+offset3;
MapParts[[replace.base, newStart, newEnd], action, stopDescent];
};
};
ENDCASE => action[part];
};
};
-- ***** Initialization
charPropertyTable: PUBLIC REF READONLY CharPropertyTable ← InitCharPropertyTable[];
LegalCharacters: TYPE = CHAR[0C..177C];
InitCharPropertyTable: PROC RETURNS[REF CharPropertyTable] = {
cpt: REF CharPropertyTable ← NEW[CharPropertyTable];
ch: CHAR;
i: CARDINAL;
punctuationString: STRING = "!@#$%~&*()-—`=+[{]};:'"",.<>/?\\|←^"L;
charPropertyTable ← cpt;
FOR ch IN CHAR DO cpt[ch] ← illegal; ENDLOOP;
FOR ch IN LegalCharacters DO cpt[ch] ← alphaNumeric; ENDLOOP;
cpt[TAB] ← white; cpt[SP] ← white; cpt[CR] ← white;
cpt[140C] ← punctuation;
TRUSTED {
FOR i IN [0 .. punctuationString.length) DO
cpt[punctuationString[i]] ← punctuation;
ENDLOOP
};
RETURN[cpt];
};
Start: PUBLIC PROC = {};
END.
Plass, February 14, 1985 5:16:16 pm PST
Simplified RopeEditReplaceImpl ruthlessly, pending evidence that the old mess was needed.
changes to: ReplaceByChar, ReplaceByString, Replace
Plass, February 14, 1985 3:31:52 pm PST
Replaced procedure bodies with simple ones, pending evidence that the complicated stuff is really needed
changes to: Depth, Substr, Concat, Copy, SemiFlatten, RopeStats, PutRope, punctuationString(added "—"), END
Plass, February 15, 1985 4:08:45 pm PST
Merged in RopeEditReplaceImpl
Plass, February 26, 1985 3:00:44 pm PST
Added new Balance implementation.