<> <> <> <> <> <> <> <> <> 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] = { <> 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] ~ { <> <> IF RopePrivate.InlineDepth[base] >= INTEGER[RopePrivate.MaxDepth]-1 THEN base _ Balance[base]; RETURN [base]; }; Part: TYPE ~ RECORD [base: ROPE, start: INT, end: INT]; <> 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 <> <> 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] ~ { <> 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_0, 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_accel.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] ~ { <> 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. <> <> <> <<>> <> <> <> <<>> <> <> <<>> <> <> <<>>