TextFindImpl.mesa
Copyright © 1985, 1986 by Xerox Corporation. All rights reserved.
derived from EditorFind.Mesa of Laurel 6
Paxton, February 23, 1983 4:13 pm
Maxwell, January 5, 1983 4:03 pm
Russ Atkinson, July 25, 1983 3:21 pm
Michael Plass, March 21, 1985 2:41:13 pm PST
Doug Wyatt, August 28, 1986 6:32:15 pm PDT
DIRECTORY
LooksReader USING [Create, Get, SetPosition],
Rope USING [Cat, Equal, Fetch, FromChar, Map, ROPE, Size, Substr],
RopeEdit USING [AlphaNumericChar, BlankChar, LowerCase, UpperCase],
RopeReader USING [Create, Get, GetIndex, GetRope, Peek, ReadOffEnd, SetPosition],
RunReader USING [Create, NoMoreRuns],
TextEdit USING [GetRope, GetRuns],
TextFind USING [Finder, FinderRec, Node, PatternErrorCode, Try, TryBackwards],
TextFindPrivate USING [anyAlphaPattern, anyBlankPattern, anyNonAlphaPattern, anyNonBlankPattern, anyStringPattern, leftBoundaryPattern, leftBracketPattern, LooksArray, maxAlphaPattern, maxBlankPattern, maxNonAlphaPattern, maxNonBlankPattern, MaxPatternLength, maxStringPattern, NameArray, nopPattern, oneAlphaPattern, oneBlankPattern, oneCharPattern, oneNonAlphaPattern, oneNonBlankPattern, PatternArray, PatternStackArray, rightBoundaryPattern, rightBracketPattern, TextStackArray],
TextLooks USING [FetchLooks, Looks, noLooks, Runs];
TextFindImpl: CEDAR PROGRAM
IMPORTS TextEdit, TextLooks, LooksReader, Rope, RopeEdit, RopeReader, RunReader, TextFind
EXPORTS TextFind
= BEGIN OPEN TextFind;
ROPE: TYPE ~ Rope.ROPE;
MalformedPattern: PUBLIC ERROR [ec:PatternErrorCode] = CODE;
***** Operations *****
NameLoc:
PUBLIC
PROC [finder: Finder, name:
ROPE]
RETURNS [at, atEnd:
INT ← 0] = {
IF finder #
NIL
THEN {
nameArray: REF TextFindPrivate.NameArray ~ finder.nameArray;
IF nameArray = NIL THEN RETURN;
FOR i:
NAT
IN [0..nameArray.length)
DO
IF Rope.Equal[nameArray[i].name, name] THEN
RETURN [nameArray[i].at, nameArray[i].atEnd];
ENDLOOP;
};
};
NameLooks:
PUBLIC
PROC [finder: Finder, name:
ROPE]
RETURNS [TextLooks.Looks ← TextLooks.noLooks] = {
IF finder #
NIL
THEN {
nameArray: REF TextFindPrivate.NameArray ~ finder.nameArray;
IF nameArray = NIL THEN RETURN;
FOR i:
NAT
IN [0..nameArray.length)
DO
IF Rope.Equal[nameArray[i].name, name] THEN RETURN [nameArray[i].looks];
ENDLOOP;
};
};
Find:
PUBLIC
PROC [pattern, text: Node,
literal, word, ignoreLooks, ignoreCase, looksExact, addBounds:
BOOL ←
FALSE,
patternStart: INT ← 0, patternLen: INT ← LAST[INT],
textStart: INT ← 0, textLen: INT ← LAST[INT],
interrupt: REF BOOL ← NIL] RETURNS [found: BOOL, at, atEnd, before, after: INT]
= { [found,at,atEnd,before,after] ←
TextFind.Try[Create[pattern,literal,word,ignoreLooks,ignoreCase,addBounds,patternStart,patternLen],
text,textStart,textLen,looksExact,interrupt]
};
BackwardsFind:
PUBLIC
PROC [pattern, text: Node,
literal, word, ignoreLooks, ignoreCase, looksExact, addBounds:
BOOL ←
FALSE,
patternStart: INT ← 0, patternLen: INT ← LAST[INT],
textStart: INT ← 0, textLen: INT ← LAST[INT],
interrupt: REF BOOL ← NIL] RETURNS [found: BOOL, at, atEnd, before, after: INT]
= {
[found,at,atEnd,before,after] ← TextFind.TryBackwards[
Create[pattern,literal,word,ignoreLooks,ignoreCase,addBounds,patternStart,patternLen],
text,textStart,textLen,looksExact,interrupt]
};
Create:
PUBLIC
PROC [pattern: Node, literal, word, ignoreLooks, ignoreCase, addBounds:
BOOL ←
FALSE, patternStart:
INT ← 0, patternLen:
INT ←
LAST[
INT]]
RETURNS [finder: Finder] = {
patternRope: ROPE ← TextEdit.GetRope[pattern];
patternRuns: TextLooks.Runs ← TextEdit.GetRuns[pattern];
RETURN [CreateFromParts[patternRope, patternRuns, literal, word, ignoreLooks, ignoreCase, addBounds, patternStart, patternLen]]
};
CreateFromRope:
PUBLIC
PROC [pattern:
ROPE, literal, word, ignoreCase, addBounds:
BOOL ←
FALSE, patternStart:
INT ← 0, patternLen:
INT ←
LAST[
INT]]
RETURNS [finder: Finder] = {
RETURN [CreateFromParts[pattern, NIL, literal, word, TRUE, ignoreCase, addBounds, patternStart, patternLen]]
};
CreateFromParts:
PROC [patternRope:
ROPE, patternRuns: TextLooks.Runs, literal, word, ignoreLooks, ignoreCase, addBounds:
BOOL ←
FALSE, patternStart:
INT ← 0, patternLen:
INT ←
LAST[
INT]]
RETURNS [finder: Finder] = {
NewLooks:
PROC [num:
NAT]
RETURNS [array:
REF TextFindPrivate.LooksArray] = {
array ← NEW[TextFindPrivate.LooksArray[num]];
FOR i:NAT IN [0..num) DO array[i] ← TextLooks.noLooks; ENDLOOP
};
char, patternChar: CHAR ← 377C;
pLen: INT;
patternLength, plen, psIndex, nameCount: NAT ← 0;
nameList: LIST OF ROPE; -- in reverse order of appearance
nameLooksList: LIST OF TextLooks.Looks;
nameLooks: TextLooks.Looks;
insideNamedPat: BOOL ← FALSE;
IF addBounds
THEN {
-- add |'s to both ends of pattern
IF literal
THEN {
-- put quotes before special chars in the pattern
new: Rope.ROPE;
AddQuotes:
PROC [c:
CHAR]
RETURNS [stop:
BOOL] = {
IF ~RopeEdit.BlankChar[c] AND ~RopeEdit.AlphaNumericChar[c] THEN
new ← Rope.Cat[new, "'"]; -- quote chars that are not blank or alpha or digit
new ← Rope.Cat[new, Rope.FromChar[c]];
RETURN [FALSE]
};
[] ← Rope.Map[base: patternRope, action: AddQuotes];
patternRope ← new; literal ← FALSE;
};
patternRope ← Rope.Cat["|", Rope.Cat[patternRope, "|"]];
};
pLen ← Rope.Size[patternRope];
patternStart ← MIN[patternStart, pLen];
IF (patternLen ← MIN[patternLen, pLen-patternStart]) > TextFindPrivate.MaxPatternLength THEN ERROR MalformedPattern[toobig];
patternLength ← plen ← patternLen;
finder ←
NEW[FinderRec]; {
-- body of Create;
PatternProc: TYPE = PROC [char: CHAR, looks: TextLooks.Looks, ignoreCase: BOOL];
patProc: PatternProc = IF literal THEN LitChar ELSE PatChar;
GetLooks:
PROC
RETURNS [lks: TextLooks.Looks] = {
RETURN [
IF finder.lksReader =
NIL
THEN TextLooks.noLooks
ELSE
LooksReader.Get[finder.lksReader ! RunReader.NoMoreRuns => {
lks ← TextLooks.noLooks; CONTINUE
}]]
};
LitChar: PatternProc = {
IF looks # TextLooks.noLooks
THEN {
IF finder.patternLooks = NIL THEN finder.patternLooks ← NewLooks[patternLength];
finder.patternLooks[psIndex] ← looks;
};
IF ignoreCase
AND (char
IN ['A..'Z]
OR char
IN ['a..'z])
THEN {
TRUSTED {finder.patternArray[psIndex] ← [pattern[char+200B]]};
200B tells matcher to check both upper and lower
IF psIndex = 0
THEN {
finder.firstPatternCharIsNormal ← TRUE;
finder.firstPatChar1 ← RopeEdit.UpperCase[char];
finder.firstPatChar2 ← RopeEdit.LowerCase[char];
};
IF psIndex = patternLength-1
THEN {
finder.lastPatternCharIsNormal ← TRUE;
finder.lastPatChar1 ← RopeEdit.UpperCase[char];
finder.lastPatChar2 ← RopeEdit.LowerCase[char];
}
}
ELSE {
TRUSTED {finder.patternArray[psIndex] ← [pattern[char]]};
IF psIndex = patternLength-1
THEN {
finder.lastPatternCharIsNormal ← TRUE;
finder.lastPatChar1 ← char;
finder.lastPatChar2 ← 0C;
};
IF psIndex = 0
THEN {
finder.firstPatternCharIsNormal ← TRUE;
finder.firstPatChar1 ← char;
finder.firstPatChar2 ← 0C;
}
}
};
NotChar: PatternProc = {
IF looks # TextLooks.noLooks
THEN {
IF finder.patternLooks = NIL THEN finder.patternLooks ← NewLooks[patternLength];
finder.patternLooks[psIndex] ← looks;
};
IF ignoreCase THEN TRUSTED {finder.patternArray[psIndex] ← [not[char+200B]]}
ELSE TRUSTED {finder.patternArray[psIndex] ← [not[char]]};
};
PatChar: PatternProc = {
IF looks # TextLooks.noLooks AND finder.patternLooks = NIL THEN
finder.patternLooks ← NewLooks[patternLength];
IF finder.patternLooks # NIL THEN finder.patternLooks[psIndex] ← looks;
SELECT char
FROM
'' => {
IF RopeReader.GetIndex[finder.ropeReader] >= plen THEN ERROR MalformedPattern[endquote];
patternLength ← patternLength-1;
LitChar[RopeReader.Get[finder.ropeReader], GetLooks[], FALSE]
};
IN ['A .. 'Z], IN ['a .. 'z] => LitChar[char, looks, ignoreCase];
'~ => {
IF RopeReader.GetIndex[finder.ropeReader] >= plen THEN ERROR MalformedPattern[endtilda];
patternLength ← patternLength-1;
char ← RopeReader.Get[finder.ropeReader];
looks ← GetLooks[];
SELECT char
FROM
'' => {
IF RopeReader.GetIndex[finder.ropeReader] >= plen THEN
ERROR MalformedPattern[endquote];
patternLength ← patternLength-1;
NotChar[RopeReader.Get[finder.ropeReader], GetLooks[], FALSE]
};
IN ['A .. 'Z], IN ['a .. 'z] => NotChar[char, looks, ignoreCase];
'% => TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.oneNonBlankPattern]]};
'$ =>
IF psIndex > 0 AND finder.patternArray[psIndex-1]=[pattern[TextFindPrivate.anyNonBlankPattern]] AND
(finder.patternLooks=
NIL
OR finder.patternLooks[psIndex-1]=looks)
THEN {
-- change to max
patternLength ← patternLength-1;
psIndex ← psIndex-1;
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.maxNonBlankPattern]]};
}
ELSE {
-- new entry
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.anyNonBlankPattern]]};
finder.stackSize ← finder.stackSize+1;
};
'@ => TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.oneNonAlphaPattern]]};
'& =>
IF psIndex > 0 AND finder.patternArray[psIndex-1]=[pattern[TextFindPrivate.anyNonAlphaPattern]] AND
(finder.patternLooks=
NIL
OR finder.patternLooks[psIndex-1]=looks)
THEN {
-- change to max
patternLength ← patternLength-1;
psIndex ← psIndex-1;
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.maxNonAlphaPattern]]}
}
ELSE {
-- new entry
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.anyNonAlphaPattern]]};
finder.stackSize ← finder.stackSize+1;
};
ENDCASE => TRUSTED {finder.patternArray[psIndex] ← [not[char]]};
};
'# => TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.oneCharPattern]]};
'* =>
IF psIndex > 0 AND finder.patternArray[psIndex-1]=[pattern[TextFindPrivate.anyStringPattern]] AND
(finder.patternLooks=
NIL
OR finder.patternLooks[psIndex-1]=looks)
THEN {
-- change to max
psIndex ← psIndex-1;
patternLength ← patternLength-1;
finder.stackSize ← MAX[1, finder.stackSize];
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.maxStringPattern]]};
}
ELSE {
-- new entry
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.anyStringPattern]]};
IF looks # TextLooks.noLooks THEN finder.stackSize ← finder.stackSize+1;
};
'% => TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.oneBlankPattern]]};
'$ =>
IF psIndex > 0 AND finder.patternArray[psIndex-1]=[pattern[TextFindPrivate.anyBlankPattern]] AND
(finder.patternLooks=
NIL
OR finder.patternLooks[psIndex-1]=looks)
THEN {
-- change to max
patternLength ← patternLength-1;
psIndex ← psIndex-1;
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.maxBlankPattern]]};
}
ELSE {
-- new entry
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.anyBlankPattern]]};
finder.stackSize ← finder.stackSize+1;
};
'@ => TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.oneAlphaPattern]]};
'& =>
IF psIndex > 0 AND finder.patternArray[psIndex-1]=[pattern[TextFindPrivate.anyAlphaPattern]] AND
(finder.patternLooks=
NIL
OR finder.patternLooks[psIndex-1]=looks)
THEN {
-- change to max
patternLength ← patternLength-1;
psIndex ← psIndex-1;
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.maxAlphaPattern]]};
}
ELSE {
-- new entry
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.anyAlphaPattern]]};
finder.stackSize ← finder.stackSize+1;
};
'| => {
TRUSTED {finder.patternArray[psIndex] ←
[pattern[IF psIndex = 0 THEN TextFindPrivate.leftBoundaryPattern ELSE TextFindPrivate.rightBoundaryPattern]]
};
IF psIndex # 0 AND psIndex # patternLength-1 THEN
ERROR MalformedPattern[boundary];
IF psIndex = patternLength-1
THEN {
-- right boundary
finder.lastPatternCharIsNormal ← TRUE; finder.lastPatChar1 ← TextFindPrivate.rightBoundaryPattern;
};
IF psIndex = 0
THEN {
--left boundary
finder.firstPatternCharIsNormal ← TRUE; finder.firstPatChar1 ← TextFindPrivate.leftBoundaryPattern;
}
};
'< => {
nameStart: INT ← RopeReader.GetIndex[finder.ropeReader]; -- index of char after the <
nameLen: INT ← 0;
IF insideNamedPat THEN ERROR MalformedPattern[missingNameEnd];
insideNamedPat ← TRUE;
nameLooks ← looks; -- remember the looks of the <
TRUSTED {finder.patternArray[psIndex] ← [startname[nameCount]]};
DO
SELECT RopeReader.Peek[finder.ropeReader !
RopeReader.ReadOffEnd => GOTO BadName] FROM -- scan to end of name
': => {
-- pattern follows
[] ← RopeReader.Get[finder.ropeReader];
[] ← GetLooks[];
patternLength ← patternLength-(nameLen+1);
EXIT;
};
'> => {
-- no pattern given, so insert a phony *
psIndex ← psIndex + 1;
PatChar['*, looks, ignoreCase]; -- use looks from the '<
patternLength ← patternLength-nameLen+1;
EXIT;
};
ENDCASE => { -- part of the name
nameLen ← nameLen+1;
[] ← RopeReader.Get[finder.ropeReader];
[] ← GetLooks[];
};
ENDLOOP;
nameList ← CONS[Rope.Substr[patternRope, nameStart, nameLen], nameList];
nameLooksList ← CONS[nameLooks, nameLooksList];
EXITS BadName => ERROR MalformedPattern[missingNameEnd]
};
'> => {
IF ~insideNamedPat THEN ERROR MalformedPattern[unmatchedNameEnd];
insideNamedPat ← FALSE;
TRUSTED {finder.patternArray[psIndex] ← [endname[nameCount]]};
nameCount ← nameCount+1;
};
'{ => {
finder.leftBracketSeen ← TRUE;
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.leftBracketPattern]]};
};
'} => {
IF finder.rightBracketSeen THEN
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.nopPattern]]} -- use first right Bracket in pattern
ELSE {
finder.rightBracketSeen ← TRUE;
TRUSTED {finder.patternArray[psIndex] ← [pattern[TextFindPrivate.rightBracketPattern]]};
}
};
ENDCASE => {
TRUSTED {finder.patternArray[psIndex] ← [pattern[char]]};
IF psIndex = patternLength-1
THEN {
finder.lastPatternCharIsNormal ← TRUE;
finder.lastPatChar1 ← char;
finder.lastPatChar2 ← 0C;
};
IF psIndex = 0
THEN {
finder.firstPatternCharIsNormal ← TRUE;
finder.firstPatChar1 ← char;
finder.firstPatChar2 ← 0C;
}
}
}; -- end of PatChar
IF word
THEN finder.wordSearch ←
TRUE
so Try will know to make sure don't have adjacent alphanumerics
ELSE IF patternLength=2 AND ~literal AND ~ignoreLooks AND Rope.Fetch[patternRope, patternStart]='# AND Rope.Fetch[patternRope, patternStart+1]='* THEN { -- for looks-only searches
finder.looks ← TextLooks.FetchLooks[patternRuns, patternStart];
finder.looksOnly ← TRUE;
finder.runReader ← RunReader.Create[];
RETURN;
};
finder.patternArray ← NEW[TextFindPrivate.PatternArray[patternLength]];
finder.ropeReader ← RopeReader.Create[];
RopeReader.SetPosition[finder.ropeReader, patternRope, patternStart];
IF patternRuns #
NIL
AND ~ignoreLooks
THEN {
finder.lksReader ← LooksReader.Create[];
LooksReader.SetPosition[finder.lksReader, patternRuns, patternStart];
};
psIndex ← 0;
DO
-- unpack the pattern
char: CHAR ← RopeReader.Get[finder.ropeReader ! RopeReader.ReadOffEnd => EXIT];
patProc[char, GetLooks[], ignoreCase];
psIndex ← psIndex + 1;
ENDLOOP;
IF insideNamedPat THEN ERROR MalformedPattern[missingNameEnd]; -- mfp
finder.length ← patternLength;
IF finder.stackSize > 0
THEN {
finder.stackSize ← finder.stackSize+1;
finder.textPosStack ← NEW[TextFindPrivate.TextStackArray[finder.stackSize]];
finder.textLenStack ← NEW[TextFindPrivate.TextStackArray[finder.stackSize]];
finder.patternPosStack ← NEW[TextFindPrivate.PatternStackArray[finder.stackSize]];
};
IF nameList #
NIL
THEN {
finder.nameArray ← NEW[TextFindPrivate.NameArray[nameCount]];
FOR i:
NAT
DECREASING
IN [0..nameCount)
DO
finder.nameArray[i].name ← nameList.first;
finder.nameArray[i].looks ← nameLooksList.first;
nameList ← nameList.rest;
nameLooksList ← nameLooksList.rest;
ENDLOOP;
};
}; --of body of Create
};
END.