RopePartsImpl.mesa
Copyright Ó 1990 by Xerox Corporation. All rights reserved.
Last tweaked by Mike Spreitzer on March 30, 1992 4:11 pm PST
Some of the impls are not yet as smart as they could be.
DIRECTORY Basics, RefText, Rope, RopeHash, RopeParts;
RopePartsImpl: CEDAR PROGRAM
IMPORTS RefText, Rope, RopeHash, RopeParts
EXPORTS RopeParts
= BEGIN OPEN RopeParts;
Part 1: Basic operations and definitions
FromChar: PUBLIC PROC [c: CHAR] RETURNS [RopePart]
~ {RETURN InlineMake[Rope.FromChar[c]]};
Make: PUBLIC PROC [base: ROPE, start: INT ← 0, len: INT ← MaxLen] RETURNS [RopePart]
~ {limit: INT ~ base.InlineLength[];
IF start>limit THEN RETURN [nil];
RETURN [[base, start, MIN[len, limit-start]]]};
ToRope: PUBLIC PROC [rp: RopePart] RETURNS [ROPE]
~ {RETURN rp.base.Substr[start: rp.start, len: rp.len]};
Simplify: PUBLIC PROC [rp: RopePart, start, end: BOOL ← TRUE] RETURNS [RopePart] ~ {
IF
((NOT start) OR rp.start=0) AND
((NOT end) OR rp.start+rp.len = rp.base.Length)
THEN RETURN [rp]
ELSE RETURN InlineMake[InlineToRope[rp]]};
Cat: PUBLIC PROC [r1, r2, r3, r4, r5: RopePart ← nil] RETURNS [RopePart] ~ {
IF r2#nil THEN r1 ← Concat[r1, r2];
IF r3#nil THEN r1 ← Concat[r1, r3];
IF r4#nil THEN r1 ← Concat[r1, r4];
IF r5#nil THEN r1 ← Concat[r1, r5];
RETURN [r1]};
Concat: PUBLIC PROC [base, rest: RopePart ← nil] RETURNS [ans: RopePart] ~ {
easy: BOOL;
[easy, ans] ← EasyConcat[base, rest];
IF NOT easy THEN ans ← InlineMake[InlineToRope[base].Concat[InlineToRope[rest]]];
RETURN};
EasyConcat: PUBLIC PROC [base, rest: RopePart ← nil] RETURNS [BOOL, RopePart] ~ {
IF Rope.EqualSubstrs[base.base, base.start+base.len, rest.len, rest.base, rest.start, rest.len] THEN RETURN [TRUE, [base.base, base.start, base.len+rest.len]];
IF rest.start>=base.len AND Rope.EqualSubstrs[base.base, base.start, base.len, rest.base, rest.start-base.len, base.len] THEN RETURN [TRUE, [rest.base, rest.start-base.len, rest.len+base.len]];
RETURN [FALSE, nil]};
Compare: PUBLIC PROC [s1, s2: RopePart, case: BOOL ← TRUE] RETURNS [Basics.Comparison]
~ {RETURN Rope.CompareSubstrs[s1.base, s1.start, s1.len, s2.base, s2.start, s2.len, case]};
Equal: PUBLIC PROC [s1, s2: RopePart, case: BOOL ← TRUE] RETURNS [BOOL]
~ {RETURN Rope.EqualSubstrs[s1.base, s1.start, s1.len, s2.base, s2.start, s2.len, case]};
EqualToRope: PUBLIC PROC [s1: RopePart, s2: ROPE, case: BOOL ← TRUE] RETURNS [BOOL]
~ {RETURN Rope.EqualSubstrs[s1.base, s1.start, s1.len, s2, 0, MaxLen, case]};
Fetch: PUBLIC PROC [base: RopePart, index: INT ← 0] RETURNS [c: CHAR]
~ {RETURN base.base.InlineFetch[base.start+index]};
Index: PUBLIC PROC [s1, s2: RopePart, pos1: INT ← 0, case: BOOL ← TRUE, clipBeforeSeek: BOOL ← FALSE] RETURNS [INT] ~ {
r2: ROPE ~ InlineToRope[s2];
IF clipBeforeSeek THEN RETURN InlineToRope[s1].Index[pos1, r2, case];
{ans: INT ← s1.base.Index[s2: r2, pos1: s1.start+pos1, case: case] - s1.start;
IF ans > s1.len - s2.len THEN RETURN [s1.len];
RETURN [ans]}};
Find: PUBLIC PROC [s1, s2: RopePart, pos1: INT ← 0, case: BOOL ← TRUE, clipBeforeSeek: BOOL ← FALSE] RETURNS [INT] ~ {
r2: ROPE ~ InlineToRope[s2];
IF clipBeforeSeek THEN RETURN InlineToRope[s1].Find[r2, pos1, case];
{ans: INT ← s1.base.Find[s2: r2, pos1: s1.start+pos1, case: case];
IF ans = -1 THEN RETURN [ans];
ans ← ans-s1.start;
IF ans > s1.len - s2.len THEN RETURN [-1];
RETURN [ans]}};
FindBackward: PUBLIC PROC [s1, s2: RopePart, pos1: INT ← MaxLen, case: BOOL ← TRUE, clipBeforeSeek: BOOL ← FALSE] RETURNS [INT] ~ {
r2: ROPE ~ InlineToRope[s2];
IF clipBeforeSeek THEN RETURN InlineToRope[s1].FindBackward[r2, pos1, case];
pos1 ← MIN[pos1, MaxLen-s1.start];
{ans: INT ← s1.base.FindBackward[s2: r2, pos1: s1.start+pos1, case: case];
RETURN [MAX[ans-s1.start, -1]]}};
IsEmpty: PUBLIC PROC [r: RopePart] RETURNS [BOOL]
~ {RETURN [r.len = 0]};
Length: PUBLIC PROC [base: RopePart] RETURNS [INT]
~ {RETURN [base.len]};
Size: PUBLIC PROC [base: RopePart] RETURNS [INT]
~ {RETURN [base.len]};
Substr: PUBLIC PROC [base: RopePart, start: INT ← 0, len: INT ← MaxLen] RETURNS [RopePart] ~ {
IF start >= base.len THEN RETURN [nil];
RETURN [[base.base, base.start+start, MIN[len, base.len-start]]]};
Replace: PUBLIC PROC [base: RopePart, start: INT ← 0, len: INT ← MaxLen, with: RopePart ← nil] RETURNS [RopePart]
~ {RETURN Make[InlineToRope[base].Replace[start, len, InlineToRope[with]]]};
ReplaceElt: PUBLIC PROC [base: RopePart, index: INT, with: CHAR] RETURNS [RopePart]
~ {RETURN Replace[base, index, 1, FromChar[with]]};
Part 2: Extended operations and definitions
Run: PUBLIC PROC [s1: RopePart, pos1: INT ← 0, s2: RopePart, pos2: INT ← 0, case: BOOL ← TRUE] RETURNS [INT] = {
RETURN [RopeRun[s1.base, s2.base, s1.start+pos1, s2.start+pos2, MIN[s1.InlineLength, s2.InlineLength], case]]};
RopeRun: PUBLIC PROC [s1, s2: ROPE, pos1, pos2, limit: INT, case: BOOL] RETURNS [result: INT ← 0] = {
len1: INT ← Rope.InlineLength[s1];
IF NonNeg[pos1] < len1 THEN {
len2: INT ← Rope.InlineLength[s2];
IF NonNeg[pos2] < len2 THEN {
r1,r2: ROPE ← NIL;
st1,sz1,lm1: INT ← 0;
st2,sz2,lm2: INT ← 0;
WHILE result<limit DO
IF st1 = lm1 THEN {
need a new piece from s1
[r1, st1, sz1] ← Rope.ContainingPiece[s1, pos1 ← pos1 + sz1];
IF sz1 = 0 THEN RETURN;
lm1 ← st1 + sz1;
};
IF st2 = lm2 THEN {
need a new piece from s2
[r2, st2, sz2] ← Rope.ContainingPiece[s2, pos2 ← pos2 + sz2];
IF sz2 = 0 THEN RETURN;
lm2 ← st2 + sz2;
};
{
c1: CHAR ← Rope.InlineFetch[r1, st1];
c2: CHAR ← Rope.InlineFetch[r2, st2];
IF c1 # c2 THEN {
IF NOT case THEN {
IF c1 <= 'Z AND c1 >= 'A THEN c1 ← c1 + ('a-'A);
IF c2 <= 'Z AND c2 >= 'A THEN c2 ← c2 + ('a-'A);
IF c1 = c2 THEN GO TO equal;
};
RETURN;
EXITS equal => {};
};
};
result ← result + 1;
st1 ← st1 + 1; st2 ← st2 + 1;
ENDLOOP;
};
};
};
IsPrefix: PUBLIC PROC [prefix, subject: RopePart, case: BOOL ← TRUE] RETURNS [BOOL]
~ {RETURN Rope.EqualSubstrs[prefix.base, prefix.start, prefix.len, subject.base, subject.start, MIN[subject.len, prefix.len]]};
IsSuffix: PUBLIC PROC [suffix, subject: RopePart, case: BOOL ← TRUE] RETURNS [BOOL]
~ {IF subject.len < suffix.len THEN RETURN [FALSE];
RETURN Rope.EqualSubstrs[suffix.base, suffix.start, suffix.len, subject.base, subject.start+subject.len-subject.len, suffix.len]};
Match: PUBLIC PROC [pattern, object: RopePart, case: BOOL ← TRUE] RETURNS [BOOL]
~ {RETURN MatchSubstrs[pattern.base, pattern.start, pattern.len, object.base, object.start, object.len, case]};
MatchSubstrs: PROC [pattern: ROPE, start1: INT ← 0, len1: INT ← INT.LAST, object: ROPE, start2: INT ← 0, len2: INT ← INT.LAST, case: BOOL ← TRUE] RETURNS [BOOL] ~ {
submatch: PROC [i1: INT, len1: INT, i2: INT, len2: INT] RETURNS [BOOL] = TRUSTED {
WHILE len1 > 0 DO
c1: CHAR ← pattern.InlineFetch[i1];
IF c1 = '* THEN {
quick kill for * at end of pattern
IF len1 = 1 THEN RETURN [TRUE];
else must take all combinations
{-- 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];
at this point demand an exact match in both strings
{c2: CHAR ← object.InlineFetch[i2];
IF NOT case THEN {
IF c1 <= 'Z AND c1 >= 'A THEN c1 ← c1 + ('a-'A);
IF c2 <= 'Z AND c2 >= 'A THEN c2 ← c2 + ('a-'A);
};
IF c1 # c2 THEN RETURN [FALSE];
};
i1 ← i1 + 1;
len1 ← len1 - 1;
i2 ← i2 + 1;
len2 ← len2 - 1;
ENDLOOP;
RETURN [len2 = 0];
};
after1: INT ← start1+MIN[pattern.InlineSize[]-start1, len1];
after2: INT ← start2+MIN[object.InlineSize[]-start2, len2];
First, strip off the common tails until they differ (quick kill false), or the pattern has a * at the tail. This strip is easy, because we just decrement the lengths.
WHILE after1 > start1 DO
n: INT ← after1 - 1;
c1: CHAR ← pattern.InlineFetch[n];
c2: CHAR;
IF c1 = '* THEN EXIT;
IF after2 = 0 THEN RETURN [FALSE];
after1 ← n;
after2 ← after2 - 1;
c2 ← object.InlineFetch[after2];
IF NOT case THEN {
IF c1 <= 'Z AND c1 >= 'A THEN c1 ← c1 + ('a-'A);
IF c2 <= 'Z AND c2 >= 'A THEN c2 ← c2 + ('a-'A);
};
IF c1 # c2 THEN RETURN [FALSE];
ENDLOOP;
RETURN [submatch [start1, after1-start1, start2, after2-start2]];
};
SkipTo: PUBLIC PROC [s: RopePart, pos: INT ← 0, skip: RopePart] RETURNS [INT]
~ {RETURN InlineToRope[s].SkipTo[pos, InlineToRope[skip]]};
SkipOver: PUBLIC PROC [s: RopePart, pos: INT ← 0, skip: RopePart] RETURNS [INT]
~ {RETURN InlineToRope[s].SkipOver[pos, InlineToRope[skip]]};
Map: PUBLIC PROC [base: RopePart, action: ActionType] RETURNS [BOOL]
~ {RETURN base.base.Map[base.start, base.len, action]};
Translate: PUBLIC PROC [base: RopePart, translator: TranslatorType ← NIL] RETURNS [RopePart]
~ {RETURN InlineMake[base.base.Translate[base.start, base.len, translator]]};
ToRefText: PUBLIC PROC [base: RopePart] RETURNS [REF TEXT] ~ {
rt: REF TEXT ~ RefText.New[base.len];
IF AppendChars[rt, base] # base.len THEN ERROR;
RETURN [rt]};
AppendChars: PUBLIC PROC [to: REF TEXT, from: RopePart] RETURNS [charsMoved: NAT]
~ {RETURN Rope.AppendChars[to, from.base, from.start, from.len]};
UnsafeMoveChars: PUBLIC UNSAFE PROC [to: Basics.UnsafeBlock, from: RopePart] RETURNS [charsMoved: INT]
~ UNCHECKED {to.count ← MIN[to.count, from.len];
RETURN Rope.UnsafeMoveChars[to, from.base, from.start]};
Hash: PUBLIC PROC [base: RopePart, case: BOOL ← TRUE, seed: CARDINAL ← defaultSeed] RETURNS [CARDINAL]
~ {RETURN RopeHash.FromRope[base.base, case, base.start, base.len, seed]};
NonNeg: PROC [x: INT] RETURNS [NAT] = INLINE {RETURN [x]};
This routine is used to check that the argument is not negative. This version depends on the compiler for the bounds checking.
END.