DIRECTORY Ascii USING [Lower], Rope USING [InlineFetch, InlineSize, ContainingPiece, Map, NoRope, ROPE, Size, Text], RopePrivate USING [InlineDepth, SingleSize, NonNeg, DoubleSize]; RopeImplExt: CEDAR PROGRAM IMPORTS Ascii, Rope, RopePrivate EXPORTS Rope SHARES Rope = BEGIN OPEN Rope, RopePrivate; Run: PUBLIC PROC [s1: ROPE, pos1: INT, s2: ROPE, pos2: INT, case: BOOL _ TRUE] RETURNS [result: INT] = TRUSTED { len1,len2: INT; str1, str2: Text; [len1, str1] _ SingleSize[s1]; [len2, str2] _ SingleSize[s2]; result _ 0; IF NonNeg[pos1] >= len1 OR NonNeg[pos2] >= len2 THEN RETURN; {r1,r2: ROPE _ NIL; st1,sz1,lm1: INT _ 0; st2,sz2,lm2: INT _ 0; c1,c2: CHAR; DO IF st1 = lm1 THEN { [r1, st1, sz1] _ ContainingPiece[s1, pos1 _ pos1 + sz1]; IF sz1 = 0 THEN RETURN; lm1 _ st1 + sz1}; IF st2 = lm2 THEN { [r2, st2, sz2] _ ContainingPiece[s2, pos2 _ pos2 + sz2]; IF sz2 = 0 THEN RETURN; lm2 _ st2 + sz2}; c1 _ InlineFetch[r1, st1]; c2 _ InlineFetch[r2, st2]; IF case THEN {IF c1 # c2 THEN RETURN} ELSE {IF Ascii.Lower[c1] # Ascii.Lower[c2] THEN RETURN}; result _ result + 1; st1 _ st1 + 1; st2 _ st2 + 1; ENDLOOP; }}; Find: PUBLIC PROC [s1, s2: ROPE, pos1: INT _ 0, case: BOOL _ TRUE] RETURNS [INT] = TRUSTED { index: INT _ Index[s1, pos1, s2, case]; IF index = InlineSize[s1] THEN RETURN [-1]; RETURN [index]; }; Index: PUBLIC PROC [s1: ROPE, pos1: INT, s2: ROPE, case: BOOL _ TRUE] RETURNS [INT] = TRUSTED { len1,len2, rem: INT; both: BOOL; [len1,len2,both] _ DoubleSize[s1, s2]; rem _ IF pos1 >= len1 THEN 0 ELSE len1 - NonNeg[pos1]; IF rem < len2 THEN RETURN [len1]; IF len2 = 0 THEN RETURN [pos1]; {c: CHAR _ InlineFetch[s2, 0]; Cmp: PROC [cc: CHAR] RETURNS [BOOL] = TRUSTED { IF c = cc AND Run[s1, pos1+1, s2, 1, case]+1 = len2 THEN RETURN [TRUE]; pos1 _ pos1 + 1; RETURN [FALSE]; }; LCmp: PROC [cc: CHAR] RETURNS [BOOL] = TRUSTED { IF c = Ascii.Lower[cc] AND Run[s1, pos1+1, s2, 1, case]+1 = len2 THEN RETURN [TRUE]; pos1 _ pos1 + 1; RETURN [FALSE]; }; rem _ rem - len2 + 1; IF case THEN {IF Map[s1, pos1, rem, Cmp] THEN RETURN [pos1]} ELSE {c _ Ascii.Lower[c]; IF Map[s1, pos1, rem, LCmp] THEN RETURN [pos1]}; }; RETURN [len1]; }; Match: PUBLIC PROC [pattern, object: ROPE, case: BOOL _ TRUE] RETURNS [BOOL] = TRUSTED { submatch: PROC [i1: INT, len1: INT, i2: INT, len2: INT] RETURNS [BOOL] = TRUSTED { WHILE len1 > 0 DO c1: CHAR _ InlineFetch[pattern, i1]; IF c1 = '* THEN {-- quick kill for * at end of pattern IF len1 = 1 THEN RETURN [TRUE]; {-- first, accept the * j1: INT _ i1 + 1; nlen1: INT _ len1 - 1; j2: INT _ i2; nlen2: INT _ len2; WHILE nlen2 >= 0 DO IF submatch[j1, nlen1, j2, nlen2] THEN RETURN [TRUE]; j2 _ j2 + 1; nlen2 _ nlen2 - 1; ENDLOOP; }; RETURN [FALSE]; }; IF len2 <= 0 THEN RETURN [FALSE]; {c2: CHAR _ InlineFetch[object, i2]; IF c1 # c2 THEN IF case OR (Ascii.Lower[c1] # Ascii.Lower[c2]) THEN RETURN [FALSE]; }; i1 _ i1 + 1; len1 _ len1 - 1; i2 _ i2 + 1; len2 _ len2 - 1; ENDLOOP; RETURN [len2 = 0]; }; len1: INT _ InlineSize[pattern]; len2: INT _ InlineSize[object]; RETURN [submatch [0, len1, 0, len2]]; }; SkipTo: PUBLIC PROC [s: ROPE, pos: INT, skip: ROPE] RETURNS [INT] = TRUSTED { len: INT _ InlineSize[s]; skiplen: INT _ InlineSize[skip]; CharMatch: PROC [c: CHAR] RETURNS [BOOL] = TRUSTED { SubMatch: PROC [cc: CHAR] RETURNS [BOOL] = TRUSTED {RETURN [c = cc]}; IF Map[skip, 0, skiplen, SubMatch] THEN RETURN [TRUE]; pos _ pos + 1; RETURN [FALSE]}; IF pos < len AND Map[s, pos, len - pos, CharMatch] THEN RETURN [pos]; RETURN [len]; }; SkipOver: PUBLIC PROC [s: ROPE, pos: INT, skip: ROPE] RETURNS [INT] = TRUSTED { len: INT _ InlineSize[s]; skiplen: INT _ InlineSize[skip]; CharMatch: PROC [c: CHAR] RETURNS [BOOL] = TRUSTED { SubMatch: PROC [cc: CHAR] RETURNS [BOOL] = TRUSTED {RETURN [c = cc]}; IF NOT Map[skip, 0, skiplen, SubMatch] THEN RETURN [TRUE]; pos _ pos + 1; RETURN [FALSE]}; IF pos < len AND Map[s, pos, len - pos, CharMatch] THEN RETURN [pos]; RETURN [len]; }; VerifyStructure: PUBLIC PROC [s: ROPE] RETURNS [leaves,nodes,maxDepth: INT] = TRUSTED { leaves _ 0; maxDepth _ 0; nodes _ 0; IF s = NIL THEN RETURN; WITH x: s SELECT FROM text => {leaves _ 1; IF x.length > x.max THEN ERROR VerifyFailed}; node => WITH x: x SELECT FROM substr => { ref: ROPE _ x.base; len1: INT _ Size[x.base]; IF x.start < 0 OR x.size <= 0 THEN ERROR VerifyFailed; IF len1 < x.start + x.size THEN ERROR VerifyFailed; [leaves, nodes, maxDepth] _ VerifyStructure[ref]; nodes _ nodes + 1}; concat => { leaves1,nodes1,maxDepth1: INT; left: ROPE _ x.base; lSize: INT _ Size[left]; right: ROPE _ x.rest; rSize: INT _ Size[right]; [leaves1, nodes1, maxDepth1] _ VerifyStructure[left]; [leaves, nodes, maxDepth] _ VerifyStructure[right]; leaves _ leaves + leaves1; nodes _ nodes + nodes1 + 1; IF maxDepth1 > maxDepth THEN maxDepth _ maxDepth1; IF x.size # lSize + rSize THEN ERROR VerifyFailed; IF x.pos # lSize THEN ERROR VerifyFailed; }; replace => { leaves1,nodes1,maxDepth1: INT; old: ROPE _ x.base; oldSize: INT _ Size[old]; repl: ROPE _ x.replace; replSize: INT _ Size[repl]; [leaves, nodes, maxDepth] _ VerifyStructure[old]; [leaves1, nodes1, maxDepth1] _ VerifyStructure[repl]; leaves _ leaves + leaves1; nodes _ nodes + nodes1 + 1; IF maxDepth < maxDepth1 THEN maxDepth _ maxDepth1; IF x.start > x.oldPos OR x.start > x.newPos THEN ERROR VerifyFailed; IF x.newPos - x.start # replSize THEN ERROR VerifyFailed; IF x.start < 0 OR x.start > x.size THEN ERROR VerifyFailed; IF x.oldPos > oldSize THEN ERROR VerifyFailed; }; object => { leaves _ 1; IF x.size < 0 OR x.fetch = NIL THEN ERROR VerifyFailed; }; ENDCASE => ERROR NoRope; ENDCASE => ERROR NoRope; maxDepth _ maxDepth + 1; IF maxDepth # InlineDepth[s] THEN ERROR VerifyFailed; }; VerifyFailed: PUBLIC ERROR = CODE; END. ¾RopeImplExt.mesa, "Thick" string implementation extension Russ Atkinson, June 7, 1982 4:04 pm Paul Rovner, August 8, 1983 11:39 am This implementation supports "lazy evaluation" for Substr, Concat, and Replace operations. It also allows the user to create arbitrary implementations for compatible Rope objects by supplying procedures for the defining operations. The remaining operations provide for Rope scanning and matching Returns the largest number of characters N such that s1 starting at pos1 is equal to s2 starting at pos2 for N characters. More formally: FOR i IN [0..N): s1[pos1+i] = s2[pos2+i] If case is true, then case matters, otherwise upper and lower case characters are considered equal. need a new piece from s1 need a new piece from s2 Returns the smallest character position N such that s2 occurs in s1 at N and N >= pos1. If s2 does not occur in s1 at or after pos1, s1.length is returned. pos1 <= N < s1.length => FOR i IN [0..s2.length): s1[N+i] = s2[i] N = s1.length => s2 does not occur in s1 If case is true, then case matters, otherwise upper and lower case characters are considered equal. Returns TRUE if the object matches the pattern, where the pattern may contain * to indicate that 0 or more characters will match. Returns FALSE otherwise. For example, using a*b as a pattern: some matching objects are: ab, a#b, a###b some not matching objects: abc, cde, bb, a, Ab If case is true, then case matters, otherwise upper and lower case characters are considered equal. else must take all combinations at this point demand an exact match in both strings return the lowest position N in s such that s[N] is in the skip string and N >= pos. If no such character occurs in s, then return s.length. return the lowest position N in s such that s[N] is NOT in the skip string and N >= pos. If no such character occurs in s, then return s.length. traverse the structure of the given rope object extra checking is performed to verify invariants Ê n˜J˜Jšœ9™9Jšœ#™#Jšœ$™$J˜JšœB™BJšœD™DJšœC™CJšœ™J˜šÏk ˜ Jšœœ ˜Jšœœ9œ˜UJšœ œ/˜@J˜—šœ œ˜Jšœ˜ Jšœ˜ Jšœ˜ Jšœœœ˜J˜Jšœ?™?šÏnœœœœœœœ˜;Jš œœœœ œœ˜4Jšœ4™4Jšœ3™3Jšœ!™!Jšœ(™(Jšœ-™-Jšœ6™6Jšœ œ˜J˜J˜J˜J˜ Jšœœœœ˜<šœœœ˜Jšœ œ˜Jšœ œ˜Jšœœ˜ š˜šœ œ˜Jšœ™J˜8Jšœ œœ˜J˜—šœ œ˜Jšœ™J˜8Jšœ œœ˜J˜—J˜J˜šœ˜Jšœœ œœ˜Jšœœ#œœ˜8—J˜J˜Jšœ˜—J˜J˜——šžœœ˜Jš œ œœ œœ˜0Jšœœœ˜Jšœœ˜'Jšœœœ˜+Jšœ ˜J˜J˜—šžœœ˜Jš œœœœœœ˜2Jšœœœ˜Jšœ3™3Jšœ3™3Jšœ4™4šœ™Jšœ(™(—Jšœ(™(Jšœ-™-Jšœ5™5Jšœœœ˜ J˜&Jšœœœœ˜6Jšœ œœ˜!Jšœ œœ˜šœœ˜š žœœœœœœ˜/šœœ&˜3Jšœœœ˜—Jšœœœ˜ J˜—š žœœœœœœ˜0šœœ&˜@Jšœœœ˜—Jšœœœ˜ J˜—J˜šœ˜Jšœœœœ˜4Jšœœœœ ˜J—J˜—Jšœ˜J˜J˜—š žœœœœœœ˜=Jšœœœ˜Jšœ/™/Jšœ0™0Jšœ/™/Jšœ0™0Jšœ)™)Jšœ.™.Jšœ-™-Jšœ5™5š œ œœœœœ˜7Jšœœœ˜šœ ˜Jšœœ˜$šœ ˜šœÏc%˜&Jšœ œœœ˜Jšœ™šœŸ˜Jšœœ ˜Jšœœ ˜Jšœœ˜ Jšœœ˜šœ ˜Jšœ œœœ˜5J˜ J˜Jšœ˜—J˜——Jšœœ˜J˜—Jšœ œœœ˜!Jšœ3™3šœœ˜$šœ ˜Jš œœ%œœœ˜C—J˜—J˜ J˜J˜ J˜Jšœ˜—Jšœ ˜J˜—Jšœœ˜ Jšœœ˜Jšœ˜%J˜J˜—šžœœœœœœœœœ˜MJšœ6™6Jšœ:™:Jšœ™Jšœœ˜Jšœ œ˜ š ž œœœœœœ˜4Jšžœœœœœœœ ˜EJšœ!œœœ˜6Jšœœœ˜—Jšœ œ#œœ˜EJšœ ˜J˜J˜—šžœœœœœœœœœ˜OJšœ:™:Jšœ:™:Jšœ™Jšœœ˜Jšœ œ˜ š ž œœœœœœ˜4Jšžœœœœœœœ ˜Ešœœ ˜&Jšœœœ˜—Jšœœœ˜—Jšœ œ#œœ˜EJšœ ˜J˜J˜—šžœœ˜Jš œœœœœ˜:Jšœ/™/Jšœ0™0J˜ J˜ J˜ Jšœœœœ˜šœœ˜˜˜ Jšœœœ˜-——˜šœœ˜˜ Jšœœ ˜Jšœœ˜Jšœ œ œœ˜6Jšœœœ˜3J˜1J˜—˜ Jšœœ˜Jšœœ ˜Jšœœ˜Jšœœ ˜Jšœœ˜J˜5J˜3J˜J˜Jšœœ˜2Jšœœœ˜2Jšœœœ˜)J˜—˜ Jšœœ˜Jšœœ ˜Jšœ œ ˜Jšœœ ˜Jšœ œ˜J˜1J˜5J˜J˜Jšœœ˜2Jšœœœœ˜DJšœœœ˜9Jšœ œœœ˜;Jšœœœ˜.J˜—˜ Jš œ œ œ œœœ˜CJ˜—Jšœœ˜——Jšœœ˜—J˜Jšœœœ˜5J˜J˜—Jšœœœœ˜"J˜Jšœ˜J˜J˜J˜J˜——…—b(Ž