[_CDCSL_93-16_]<1>Cedar>release>MorePfsNames>RopePartsImpl.mesa

RopePartsImpl.mesa

Last tweaked by Mike Spreitzer on April 14, 1992 12:50 pm PDT

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.Length[];

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] ~ {

((NOT start) OR rp.start=0) AND

((NOT end) OR rp.start+rp.len = NAT[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.Fetch[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 Rope.Run[s1.base, s1.start+pos1, s2.base, s2.start+pos2, case, MIN[s1.InlineLength, s2.InlineLength]]};

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.Fetch[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.Fetch[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.Length[]-start1, len1];

after2: INT ← start2+MIN[object.Length[]-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.Fetch[n];

c2: CHAR;

IF c1 = '* THEN EXIT;

IF after2 = 0 THEN RETURN [FALSE];

after1 ← n;

after2 ← after2 - 1;

c2 ← object.Fetch[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.