-- RopeFindImpl.Mesa
-- derived from EditorFind.Mesa of Laurel 6
-- last writen by Paxton, 3-Jun-81 12:39:07
DIRECTORY
RopeFind,
RopeEdit,
Rope,
RopeReader,
Inline;
RopeFindImpl: PROGRAM
IMPORTS RopeEdit, RopeReader, Rope, Inline
EXPORTS RopeFind, RopeEdit =
BEGIN
OPEN ropeI:Rope, RopeFind, RopeEdit, rdrI:RopeReader;
MalformedPattern: PUBLIC ERROR = CODE;
LineBreakValue: Char = 200C;
CharMask: Char = 177C;
LegalCharacters: TYPE = Char[0C .. 177C];
TextStackArray: TYPE = RECORD[stack: SEQUENCE length: NAT OF Int];
PatternStackArray: TYPE = RECORD[stack: SEQUENCE length: NAT OF NAT];
anyStringPattern: Char = LineBreakValue;
oneCharPattern: Char = LineBreakValue + 1;
oneAlphaPattern: Char = LineBreakValue + 2;
oneNonAlphaPattern: Char = LineBreakValue + 3;
anyAlphaPattern: Char = LineBreakValue + 4;
anyNonAlphaPattern: Char = LineBreakValue + 5;
leftBracketPattern: Char = LineBreakValue + 6;
rightBracketPattern: Char = LineBreakValue + 7;
MaxPatternLength: NAT = 1024;
Finder: TYPE = REF FinderRec;
FinderRec: PUBLIC TYPE = RECORD [
stackSize: NAT ← 0,
patternPosStack: REF PatternStackArray,
textPosStack: REF TextStackArray,
patternString: REF TEXT,
firstPatChar1, firstPatChar2: Char ← 377C,
reader: rdrI.Ref,
leftBracketSeen, rightBracketSeen: BOOLEAN ← FALSE,
firstPatternCharIsNormal: BOOLEAN ← FALSE
];
Create: PUBLIC PROC [pattern: Rope] RETURNS [finder: Finder] =
BEGIN
psIndex: NAT ← 0;
char, patternChar: Char ← 377C;
pLen: Int;
patternLength: NAT;
IF (pLen ← ropeI.Size[pattern]) > MaxPatternLength THEN ERROR MalformedPattern;
patternLength ← LOOPHOLE[Inline.LowHalf[pLen]];
finder ← NEW[FinderRec];
-- normalize search string; process special characters.
BEGIN OPEN finder;
i: CARDINAL;
patternString ← NEW[TEXT[patternLength]];
reader ← rdrI.Create[];
rdrI.SetPosition[reader,pattern];
FOR i ← 0, i + 1 UNTIL i >= patternLength DO -- unpack the pattern
SELECT (char ← rdrI.Get[reader]) FROM
'' =>
BEGIN
IF i + 1 < patternLength THEN i ← i + 1 ELSE ERROR MalformedPattern;
patternString[psIndex] ← rdrI.Get[reader];
IF psIndex = 0 THEN {firstPatternCharIsNormal ← TRUE; firstPatChar1 ← patternString[0]};
END;
IN ['A .. 'Z], IN ['a .. 'z] =>
BEGIN
patternString[psIndex] ← Inline.BITOR[char, LineBreakValue];
IF psIndex = 0 THEN
BEGIN
firstPatternCharIsNormal ← TRUE;
firstPatChar1 ← UpperCase[char];
firstPatChar2 ← LowerCase[char];
END;
END;
'# => patternString[psIndex] ← oneCharPattern;
'* => patternString[psIndex] ← anyStringPattern;
'@ => patternString[psIndex] ← oneAlphaPattern;
'! => patternString[psIndex] ← oneNonAlphaPattern;
'& => { patternString[psIndex] ← anyAlphaPattern; stackSize ← stackSize+1 };
'~ => { patternString[psIndex] ← anyNonAlphaPattern; stackSize ← stackSize+1 };
'{ => {
IF leftBracketSeen THEN ERROR MalformedPattern ELSE leftBracketSeen ← TRUE;
patternString[psIndex] ← leftBracketPattern};
'} => {
IF rightBracketSeen THEN ERROR MalformedPattern ELSE rightBracketSeen ← TRUE;
patternString[psIndex] ← rightBracketPattern};
ENDCASE =>
BEGIN
patternString[psIndex] ← char;
IF psIndex = 0 THEN {firstPatternCharIsNormal ← TRUE; firstPatChar1 ← char};
END;
psIndex ← psIndex + 1;
ENDLOOP;
FOR psIndex ← psIndex, psIndex - 1 UNTIL psIndex = 0 DO -- discard trailing "any's"
SELECT patternString[psIndex - 1] FROM
anyStringPattern, anyAlphaPattern, anyNonAlphaPattern => NULL;
ENDCASE => EXIT;
ENDLOOP;
IF (patternString.length ← psIndex) = 0 THEN ERROR MalformedPattern;
IF stackSize > 0 THEN {
textPosStack ← NEW[TextStackArray[stackSize]];
patternPosStack ← NEW[PatternStackArray[stackSize]] };
END; -- of OPEN
END; -- of Create
Try: PUBLIC PROC [finder: Finder, rope: Rope, start: Int ← 0, len: Int ← MaxLen]
RETURNS [found: BOOLEAN, at, atEnd, patternEnd: Int] =
BEGIN OPEN finder;
stackPtr, patternPos, patternAnchor: NAT ← 0;
char, patternChar: Char ← 377C;
charType: CharProperty;
beginPos, endPos, textPos, textAnchor, end, size: Int;
size ← ropeI.Size[rope];
start ← MIN[start,size];
len ← MIN[len,size-start];
end ← start+len;
found ← FALSE;
at ← start;
UNTIL at = end DO -- text loop
IF firstPatternCharIsNormal THEN -- search for next instance of first pattern char
BEGIN
rdrI.SetPosition[reader,rope,at];
UNTIL at = end DO
SELECT rdrI.Get[reader] FROM
firstPatChar1, firstPatChar2 => EXIT;
ENDCASE;
at ← at+1;
ENDLOOP;
IF at=end THEN EXIT;
patternPos ← 1;
textPos ← at + 1;
END
ELSE {patternPos ← 0; textPos ← at};
-- save where name began matching non-* seg of pattern
patternAnchor ← 0;
beginPos ← textAnchor ← at;
DO -- pattern loop
IF patternPos >= patternString.length THEN
BEGIN
found ← TRUE;
at ← beginPos;
atEnd ← IF rightBracketSeen THEN endPos ELSE textPos;
patternEnd ← textPos;
GO TO Return;
END;
SELECT (patternChar ← patternString[patternPos]) FROM
anyStringPattern =>
{patternAnchor ← patternPos ← patternPos + 1; textAnchor ← textPos; stackPtr ← 0};
leftBracketPattern =>
{beginPos ← textPos; patternPos ← patternPos +1};
rightBracketPattern =>
{endPos ← textPos; patternPos ← patternPos +1};
anyNonAlphaPattern, anyAlphaPattern =>
BEGIN
stackPtr ← stackPtr + 1;
textPosStack[stackPtr] ← textPos;
patternPosStack[stackPtr] ← patternPos;
patternPos ← patternPos + 1;
END;
ENDCASE =>
BEGIN
IF textPos >= end THEN GO TO Return; -- failure return
IF patternChar = oneCharPattern THEN
BEGIN
rdrI.SetPosition[reader,rope,textPos];
[] ← rdrI.Get[reader];
IF patternPos # 0 AND patternPos = patternAnchor THEN
-- first char(s) of * segment
{patternAnchor ← patternAnchor + 1; textAnchor ← textPos + 1};
patternPos ← patternPos + 1;
textPos ← textPos + 1;
END
ELSE BEGIN
rdrI.SetPosition[reader,rope,textPos];
charType ← GetCharProp[char ← rdrI.Get[reader]];
IF SELECT patternChar FROM
oneNonAlphaPattern => charType # alphaNumeric,
oneAlphaPattern => charType = alphaNumeric,
char => TRUE,
> LineBreakValue =>
SELECT patternChar ← Inline.BITAND[CharMask,patternChar] FROM
IN ['A..'Z] => patternChar = UpperCase[char],
IN ['a .. 'z] => patternChar = LowerCase[char],
ENDCASE => FALSE,
ENDCASE => FALSE
THEN -- chars match -- {patternPos ← patternPos + 1; textPos ← textPos + 1}
ELSE BEGIN -- chars don't match; try to increment some wild card position
WHILE stackPtr # 0 DO
rdrI.SetPosition[reader,rope,textPosStack[stackPtr]];
charType ← GetCharProp[rdrI.Get[reader]];
IF SELECT patternString[patternPosStack[stackPtr]] FROM
anyNonAlphaPattern => charType # alphaNumeric,
anyAlphaPattern => charType = alphaNumeric,
ENDCASE => FALSE THEN
BEGIN
patternPos ← patternPosStack[stackPtr] + 1;
textPos ← textPosStack[stackPtr] ← textPosStack[stackPtr] + 1;
EXIT
END;
stackPtr ← stackPtr - 1;
ENDLOOP;
IF stackPtr = 0 THEN -- implicit AND patternAnchor # 0 (there was a *)
BEGIN
patternPos ← patternAnchor;
textPos ← textAnchor ← textAnchor + 1;
END;
IF patternAnchor = 0 AND stackPtr = 0 THEN EXIT;
END;
END;
END;
ENDLOOP; -- end of pattern loop
at ← at+1; -- start over with next character
ENDLOOP; -- end of text loop
GO TO Return;
EXITS
Return => NULL;
END; -- of Try --
charPropertyTable: PUBLIC REF READONLY CharPropertyTable;
StartRopeFind: 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;
FOR i IN [0 .. punctuationString.length) DO cpt[punctuationString[i]] ← punctuation; ENDLOOP;
};
END.