RopeEditImpl.mesa
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, December 16, 1983 12:23 pm
DIRECTORY
FS,
IO,
RopeEdit,
RopeIO,
RopeEditingAlloc,
Rope,
RopeFrom,
RopeReader,
RopePrivate;
RopeEditImpl: CEDAR PROGRAM
IMPORTS
FS, IO, Rope, RopeEdit, RopeReader, RopePrivate, RopeFrom, RopeEditingAlloc
EXPORTS
RopeEdit, RopeIO
SHARES Rope
= BEGIN OPEN RopeEdit, RopePrivate;
FlatMax: Offset = 30; -- if shorter, copy to flat rope
Depth: PUBLIC PROC [rope: ROPE] RETURNS [depth: INTEGER] = TRUSTED {
IF rope=NIL THEN RETURN [0];
WITH x: rope SELECT FROM
text => depth ← 0;
node => WITH x:x SELECT FROM
substr => depth ← x.depth;
concat => depth ← x.depth;
replace => depth ← x.depth;
object => depth ← 0;
ENDCASE => ERROR Rope.NoRope;
ENDCASE => ERROR Rope.NoRope;
};
-- Edit
Substr: PUBLIC PROC
[base: ROPE, start: Offset ← 0, len: Offset ← MaxLen]
RETURNS [ROPE] = TRUSTED {
IF start < 0 THEN ERROR;
DO
IF base=NIL OR len<=0 THEN RETURN[NIL];
WITH x:base SELECT FROM
text => {
rem: Offset;
IF (rem ← NonNeg[x.length-start]) <= len THEN
IF start = 0 THEN RETURN [base] ELSE len ← rem};
node => WITH x:x SELECT FROM
substr => {
rem: Offset;
IF (rem ← NonNeg[x.size-start]) <= len THEN
IF start = 0 THEN RETURN [base] ELSE len ← rem;
start ← start + x.start; base ← x.base; LOOP};
concat => {
xpos, rem: Offset;
IF (rem ← NonNeg[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}};
replace => {
xstart, xnew, rem: Offset;
IF (rem ← NonNeg[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}};
object => {
rem: Offset;
IF (rem ← x.size-start) <= len THEN
IF start = 0 THEN RETURN [base] ELSE len ← rem};
ENDCASE => ERROR Rope.NoRope;
ENDCASE => ERROR Rope.NoRope;
EXIT;
ENDLOOP;
RETURN [
IF len <= FlatMax
THEN RopeFrom.FlatSubstr[base,start,len]
ELSE NEW[Tsubstr ← [node[substr[len,base,start,Depth[base]+1]]]]];
};
Concat: PUBLIC PROC [base, rest: ROPE, baseLen, restLen: Offset ← MaxLen]
RETURNS [new: ROPE] = TRUSTED {
size: Offset;
IF baseLen=MaxLen THEN baseLen ← Rope.InlineSize[base];
IF restLen=MaxLen THEN restLen ← Rope.InlineSize[rest];
IF restLen <= FlatMax AND
(new ← RopeFrom.TryAppendConcat[base,rest,baseLen,restLen]) # NIL
THEN RETURN [new];
IF (size ← baseLen+restLen) <= FlatMax THEN
RETURN [RopeFrom.FlatConcat[base,rest,baseLen,restLen,FALSE]];
IF rest=NIL THEN RETURN [base];
IF base=NIL THEN RETURN [rest];
IF baseLen < FlatMax THEN WITH x:rest SELECT FROM
node => WITH x:x SELECT FROM
concat => -- try ((base & rest.base) & rest.rest)
IF x.pos <= FlatMax AND
(new ← RopeFrom.TryAppendConcat[base, x.base, baseLen, x.pos]) # NIL
THEN RETURN [NEW[Tconcat ←
[node[concat[size, new, x.rest, baseLen+x.pos,
1+MAX[Depth[new],Depth[x.rest]]]]]]]
ELSE IF baseLen+x.pos <= FlatMax THEN {
new ← RopeFrom.FlatConcat[base, x.base, baseLen, x.pos, FALSE];
RETURN [NEW[Tconcat ← [node[concat[size,
new, x.rest, baseLen+x.pos,
1+MAX[Depth[new],Depth[x.rest]]]]]]] };
ENDCASE;
ENDCASE;
IF restLen <= FlatMax THEN WITH x:base SELECT FROM
node => WITH x:x SELECT FROM
concat => -- try (base.base & (base.rest & rest))
IF (new ← RopeFrom.TryAppendConcat[x.rest, rest, x.size-x.pos, restLen]) # NIL
THEN RETURN [NEW[Tconcat ←
[node[concat[size,x.base,new,x.pos,
1+MAX[Depth[new],Depth[x.base]]]]]]]
ELSE IF restLen+x.size-x.pos <= FlatMax THEN {
new ← RopeFrom.FlatConcat[x.rest, rest, x.size-x.pos, restLen, FALSE];
RETURN [NEW[Tconcat ← [node[concat[size,x.base,new,x.pos,
1+MAX[Depth[new],Depth[x.base]]]]]]]};
ENDCASE;
ENDCASE;
RETURN [NEW[Tconcat ← [node[concat[size,base,rest,baseLen,
1+MAX[Depth[base],Depth[rest]]]]]]] };
Copy: PUBLIC PROC [
dest: ROPE, destLoc: Offset ← 0,
source: ROPE, start: Offset ← 0, len: Offset ← MaxLen,
destSize: Offset ← MaxLen]
RETURNS [ROPE] = {
size: Offset;
IF len=MaxLen THEN {
sourceSize: Offset ← Rope.InlineSize[source];
IF start >= sourceSize THEN RETURN [dest];
len ← MIN[len,sourceSize-start] };
IF destSize=MaxLen THEN destSize ← Rope.InlineSize[dest];
IF destLoc > destSize THEN destLoc ← destSize;
IF (size�stSize+len) <= FlatMax THEN RETURN [
RopeFrom.FlatCopy[dest,destLoc,source,start,len,destSize]];
RETURN [Insert[dest,destLoc,Substr[source,start,len],destSize,len]]};
SemiFlatten: PUBLIC PROC [base: ROPE] RETURNS [flattened: ROPE] = {
lastStart, lastLen: Offset;
lastPiece: ROPE;
list: LIST OF ROPE;
listLen: INT ← 0;
loc: Offset ← 0; -- where we are in reading base
end: Offset ← 0; -- everything up to here has been flattened and put on list
Flush: PROC = {
size: INT ← loc-end;
newChunk: ROPE;
IF size=0 THEN RETURN;
newChunk ←
IF size=lastLen THEN Substr[base,end,size] -- will find the last piece, so won't allocate
ELSE RopeFrom.FlatSubstr[base,end,size];
list ← CONS[newChunk,list];
listLen ← listLen+1;
end ← loc };
Map: SAFE PROC [base: ROPE, start: INT, len: INT] RETURNS [quit: BOOLFALSE] = TRUSTED {
next: INT;
IF (next ← loc+len)-end > 300 THEN Flush; -- flatten the pieces ahead of this one
loc ← next; lastPiece ← base; lastStart ← start; lastLen ← len;
RETURN [FALSE] };
Nth: PROC [n: INT] RETURNS [ROPE] = INLINE {
IF n NOT IN [0..listLen) THEN ERROR;
FOR l: LIST OF ROPE ← list, l.rest DO
IF (n ← n+1)=listLen THEN RETURN [l.first];
ENDLOOP };
Balance: PROC [first, num: INT] RETURNS [ROPE] = { -- concat num ropes starting at first
half: INT;
IF num=1 THEN RETURN [Nth[first]];
half ← num/2;
RETURN [Concat[Balance[first,half],Balance[first+half,num-half]]];
};
[] ← Rope.PieceMap[base: base, action: Map];
IF loc # Size[base] THEN ERROR;
Flush[];
IF listLen = 0 THEN RETURN [NIL];
flattened ← Balance[0,listLen]; -- concat the ropes on the list
};
RopeStats: PUBLIC PROC [base: ROPE, start: Offset ← 0, len: Offset ← MaxLen]
RETURNS [size, pieces, depth: Offset] = TRUSTED {
rem, altDepth, subDepth, subPieces: Offset;
size ← Rope.InlineSize[base];
rem ← NonNeg[size - NonNeg[start]];
altDepth ← 0;
IF len > rem THEN len ← rem;
pieces ← depth ← 0;
WHILE len > 0 DO
x: ROPE ← base;
WITH x: x SELECT FROM
text => RETURN [size,pieces+1,MAX[depth,altDepth]];
node => {
depth ← depth+1;
WITH x: x SELECT FROM
substr => {
base ← x.base; start ← start + x.start; LOOP};
concat => {
subLen: Offset ← x.pos - start;
IF subLen > 0 THEN
{IF len <= subLen THEN {base ← x.base; LOOP};
[,subPieces,subDepth] ← RopeStats[x.base, start, subLen];
pieces ← pieces+subPieces;
altDepth ← MAX[altDepth,depth+subDepth];
len ← len - subLen; start ← 0}
ELSE start ← -subLen;
base ← x.rest; LOOP};
replace => {
three pieces to consider (first, middle, last)
xstart: Offset ← x.start;
len1: Offset ← xstart - start;
base ← x.base;
IF len1 > 0 THEN {
a piece in first section of rope
IF len1 >= len THEN LOOP; -- only in first section
[,subPieces,subDepth] ← RopeStats[base, start, len1];
pieces ← pieces+subPieces;
altDepth ← MAX[altDepth,depth+subDepth];
start ← xstart; len ← len - len1; len1 ← 0};
{xpos: Offset ← x.newPos;
len2: Offset ← 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
[,subPieces,subDepth] ← RopeStats[base, start, len2];
pieces ← pieces+subPieces;
altDepth ← MAX[altDepth,depth+subDepth];
base ← x.base; start ← x.oldPos; len ← len - len2;
}};
object => RETURN [size,pieces+1,MAX[depth,altDepth]];
ENDCASE => ERROR Rope.NoRope };
ENDCASE => ERROR Rope.NoRope;
ENDLOOP;
RETURN [0,0,0];
};
-- **** IO Operations ****
PutRope: PUBLIC PROC [stream: IO.STREAM, rope: ROPE] = {
reader: RopeReader.Ref ← RopeReader.GetRopeReader[];
size: Offset ← Rope.InlineSize[rope];
cnt: NAT;
blockSize: NAT = 512;
block: REF TEXT ← RopeEditingAlloc.GetBlock[];
RopeReader.SetPosition[reader,rope];
block.length ← 0;
UNTIL size=0 DO
IF block.length >= blockSize THEN { -- buffer is full
IO.PutBlock[stream,block];
block.length ← 0 };
cnt ← RopeReader.GetString[reader:reader, str:block];
size ← size-cnt;
ENDLOOP;
IF block.length > 0 THEN IO.PutBlock[stream,block];
RopeEditingAlloc.FreeBlock[block];
RopeReader.FreeRopeReader[reader] };
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]];
};
-- ***** Initialization
charPropertyTable: PUBLIC REF READONLY CharPropertyTable;
LegalCharacters: TYPE = CHAR[0C..177C];
Start: PUBLIC PROC = {
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};
};
END.