-- RopeEditImpl.mesa; written by Bill Paxton, February 1981
-- edited by Paxton, October 29, 1982 8:45 am
Last Edited by: Maxwell, January 5, 1983 11:57 am
DIRECTORY
RopeEdit,
RopeIO,
RopeEditingAlloc,
Rope,
RopeFrom,
RopeReader,
RopeInline,
CIFS,
File,
IO,
FileIO;
RopeEditImpl:
CEDAR PROGRAM
IMPORTS RopeEdit, RopeReader, RopeInline, RopeFrom, Rope,
CIFS,
IO, FileIO, RopeEditingAlloc
EXPORTS RopeEdit, RopeIO
SHARES Rope =
BEGIN
OPEN RopeEdit, RopeInline;
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 RopeFrom.qZone.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 ← RopeInline.InlineSize[base];
IF restLen=MaxLen THEN restLen ← RopeInline.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 [RopeFrom.qZone.
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 [RopeFrom.qZone.
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 [RopeFrom.qZone.
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 [RopeFrom.qZone.
NEW[Tconcat ← [node[concat[size,x.base,new,x.pos,
1+MAX[Depth[new],Depth[x.base]]]]]]]};
ENDCASE;
ENDCASE;
RETURN [RopeFrom.qZone.
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 ← RopeInline.InlineSize[source];
IF start >= sourceSize THEN RETURN [dest];
len ← MIN[len,sourceSize-start] };
IF destSize=MaxLen THEN destSize ← RopeInline.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 ← RopeFrom.qZone.CONS[newChunk,list];
listLen ← listLen+1;
end ← loc };
Map:
SAFE
PROC [base:
ROPE, start:
INT, len:
INT]
RETURNS [quit:
BOOL ←
FALSE] =
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 ← RopeInline.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.Handle, rope:
ROPE] = {
reader: RopeReader.Ref ← RopeReader.GetRopeReader[];
size: Offset ← RopeInline.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.Handle, len: Offset ← MaxLen]
RETURNS [ROPE] = { RETURN [RopeFrom.Stream[stream,len]] };
-- **** Filing Operations ****
ToFile:
PUBLIC
PROC [fileName, rope:
ROPE, start: Offset ← 0] = {
WriteFile[FileIO.Open[fileName,overwrite], rope, start] };
ToFileC:
PUBLIC
PROC [capability: File.Capability, rope:
ROPE, start: Offset ← 0] = {
WriteFile[FileIO.StreamFromCapability[capability,overwrite], rope, start] };
WriteFile:
PROC [stream:
IO.Handle, 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: ROPE] = {
fh: CIFS.OpenFile = CIFS.Open[fileName, CIFS.read];
rope ← RopeFrom.File[CIFS.GetFC[fh], start, len, FALSE, MaxLen, FALSE];
CIFS.Close[fh] };
FromFileC:
PUBLIC
PROC [capability: File.Capability, start: Offset ← 0, len: Offset ← MaxLen]
RETURNS [ROPE] = {
RETURN [RopeFrom.File[capability, start, len, FALSE, MaxLen, FALSE]] };
-- ***** 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.