<> <> <> <> <> <> <> <> <<>> DIRECTORY Basics, LooksReader, Rope, RopeEdit, RopeReader, RunReader, TextFindPrivate, TextLooks, Tioga; TextFindImpl: CEDAR PROGRAM IMPORTS Basics, LooksReader, Rope, RopeEdit, RopeReader, RunReader, TextFindPrivate, TextLooks, Tioga EXPORTS Tioga = BEGIN OPEN Tioga; ROPE: TYPE ~ Rope.ROPE; Looks: TYPE ~ TextLooks.Looks; noLooks: Looks ~ TextLooks.noLooks; Finder: TYPE ~ REF FinderRec; FinderRec: PUBLIC TYPE ~ TextFindPrivate.FinderRecord; <> MalformedPattern: PUBLIC ERROR [ec: PatternErrorCode] = CODE; <<>> 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 [Looks _ 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] = { finder: Finder ~ FinderFromNode[pattern, literal, word, ignoreLooks, ignoreCase, addBounds, patternStart, patternLen]; [found, at, atEnd, before, after] _ TryFind[finder, text, textStart, textLen, looksExact, interrupt]; }; FindBackwards: 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] _ TryFindBackwards[ FinderFromNode[pattern,literal,word,ignoreLooks,ignoreCase,addBounds,patternStart,patternLen], text,textStart,textLen,looksExact,interrupt] }; FinderFromNode: PUBLIC PROC [pattern: Node, literal, word, ignoreLooks, ignoreCase, addBounds: BOOL _ FALSE, patternStart: INT _ 0, patternLen: INT _ LAST[INT]] RETURNS [finder: Finder] = { patternRope: ROPE _ GetRope[pattern]; patternRuns: TextLooks.Runs _ GetRuns[pattern]; RETURN [FinderFromParts[patternRope, patternRuns, literal, word, ignoreLooks, ignoreCase, addBounds, patternStart, patternLen]] }; FinderFromRope: PUBLIC PROC [pattern: ROPE, literal, word, ignoreCase, addBounds: BOOL _ FALSE, patternStart: INT _ 0, patternLen: INT _ LAST[INT]] RETURNS [finder: Finder] = { RETURN [FinderFromParts[pattern, NIL, literal, word, TRUE, ignoreCase, addBounds, patternStart, patternLen]] }; FinderFromParts: 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] _ 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 Looks; nameLooks: 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: Looks, ignoreCase: BOOL]; patProc: PatternProc = IF literal THEN LitChar ELSE PatChar; GetLooks: PROC RETURNS [lks: Looks] = { RETURN [IF finder.lksReader = NIL THEN noLooks ELSE LooksReader.Get[finder.lksReader ! RunReader.NoMoreRuns => { lks _ noLooks; CONTINUE }]] }; LitChar: PatternProc = { IF looks # 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 # 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 # 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 # 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 <> 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 }; <> CharBits: PROC [c: CHAR] RETURNS [CHAR] = INLINE { RETURN [LOOPHOLE[Basics.BITAND[LOOPHOLE[TextFindPrivate.CharMask],LOOPHOLE[c]], CHAR]]; }; SearchRope: PUBLIC PROC [finder: Finder, rope: Rope.ROPE, start: INT _ 0, len: INT _ maxLen, interrupt: REF BOOL _ NIL] RETURNS [found: BOOL, at, atEnd, before, after: INT] = { [found, at, atEnd, before, after] _ Search[finder, rope, NIL, start, len, FALSE, interrupt] }; TryFind: PUBLIC PROC [finder: Finder, text: Node, start: INT _ 0, len: INT _ maxLen, looksExact: BOOL _ FALSE, interrupt: REF BOOL _ NIL] RETURNS [found: BOOL, at, atEnd, before, after: INT] = { [found, at, atEnd, before, after] _ Search[ finder, GetRope[text], GetRuns[text], start, len, looksExact, interrupt] }; Search: PROC [finder: Finder, rope: ROPE, runs: TextLooks.Runs, start: INT, len: INT, looksExact: BOOL, interrupt: REF BOOL _ NIL] RETURNS [found: BOOL, at, atEnd, before, after: INT] = { IF finder.wordSearch THEN DO -- repeat search until find a word [found, at, atEnd, before, after] _ TryToFind[finder, rope, runs, start, len, looksExact, interrupt]; IF NOT found OR (interrupt#NIL AND interrupt^) THEN RETURN; -- failed IF IsWord[rope, at, atEnd] THEN RETURN; -- got it start _ after; -- try again ENDLOOP; [found, at, atEnd, before, after] _ TryToFind[finder, rope, runs, start, len, looksExact, interrupt] }; IsWord: PUBLIC PROC [rope: ROPE, at, atEnd: INT] RETURNS [BOOL] = { IF at > 0 AND RopeEdit.GetCharProp[Rope.Fetch[rope,at-1]] = alphaNumeric THEN RETURN [FALSE]; IF atEnd < Rope.Size[rope] AND RopeEdit.GetCharProp[Rope.Fetch[rope,atEnd]] = alphaNumeric THEN RETURN [FALSE]; RETURN [TRUE]; }; TryToFind: PROC [finder: Finder, rope: ROPE, runs: TextLooks.Runs, start: INT _ 0, len: INT _ maxLen, looksExact: BOOL _ FALSE, interrupt: REF BOOL _ NIL] RETURNS [found: BOOL, at, atEnd, before, after: INT] = { patternPosStack: REF TextFindPrivate.PatternStackArray ~ finder.patternPosStack; textPosStack: REF TextFindPrivate.TextStackArray ~ finder.textPosStack; textLenStack: REF TextFindPrivate.TextStackArray ~ finder.textLenStack; patternArray: REF TextFindPrivate.PatternArray ~ finder.patternArray; length: NAT ~ finder.length; patternLooks: REF TextFindPrivate.LooksArray ~ finder.patternLooks; nameArray: REF TextFindPrivate.NameArray ~ finder.nameArray; firstPatChar1: CHAR ~ finder.firstPatChar1; firstPatChar2: CHAR ~ finder.firstPatChar2; ropeReader: RopeReader.Ref ~ finder.ropeReader; lksReader: LooksReader.Ref ~ finder.lksReader; looks: Looks ~ finder.looks; looksOnly: BOOL ~ finder.looksOnly; rightBracketSeen: BOOL _ finder.rightBracketSeen; firstPatternCharIsNormal: BOOL ~ finder.firstPatternCharIsNormal; stackPtr, patternPos, patternAnchor: NAT _ 0; char, patternChar: CHAR _ 377C; charType: RopeEdit.CharProperty; beginPos, endPos, textPos, textAnchor, end, size: INT; psLength: NAT; LooksMatch: PROC [txtpos: INT, ppos: NAT] RETURNS [BOOL] = { patlks, sourcelks: Looks; IF (patlks _ patternLooks[ppos]) = noLooks THEN RETURN [TRUE]; IF runs=NIL THEN RETURN [FALSE]; -- pattern has looks and text doesn't IF txtpos NOT IN [start..end) THEN RETURN [FALSE]; -- boundary char has no looks LooksReader.SetPosition[lksReader,runs,txtpos]; sourcelks _ LooksReader.Get[lksReader]; RETURN [patlks=(IF looksExact THEN sourcelks ELSE TextLooks.LooksAND[sourcelks,patlks])] }; GetChar: PROC [txtpos: INT] RETURNS [char: CHAR] = { SELECT txtpos FROM IN [start..end) => { -- read the character from the rope char _ Rope.Fetch[rope, txtpos]; <> }; ENDCASE => ERROR; }; PropTest: TYPE = { eq, ne, any }; MaxCount: PROC [propTest: PropTest, property: RopeEdit.CharProperty _ illegal] RETURNS [count: INT] = { count _ 0; DO IF textPos+count NOT IN [start..end) THEN EXIT; char _ GetChar[textPos+count]; IF propTest=eq THEN IF RopeEdit.GetCharProp[char] # property THEN EXIT ELSE NULL ELSE IF propTest=ne AND RopeEdit.GetCharProp[char]=property THEN EXIT ELSE NULL; IF patternLooks # NIL AND patternLooks[patternPos] # noLooks AND NOT LooksMatch[textPos+count, patternPos] THEN EXIT; count _ count+1; ENDLOOP; }; size _ Rope.Size[rope]; start _ MIN[MAX[0,start],size]; len _ MIN[MAX[0,len],size-start]; end _ start+len; found _ FALSE; IF looksOnly THEN { looksReader: LooksReader.Ref ~ LooksReader.GetLooksReader[]; LooksReader.SetPosition[looksReader, runs, start]; at _ start; WHILE at < end DO lks: Looks _ LooksReader.InlineGet[looksReader]; IF NOT looksExact THEN lks _ TextLooks.LooksAND[lks, looks]; IF lks = looks THEN EXIT; -- have found a match IF interrupt#NIL AND interrupt^ THEN at _ end ELSE at _ at+1; ENDLOOP; LooksReader.FreeLooksReader[looksReader]; IF at >= end THEN RETURN; -- failed to find a match RETURN [TRUE, at, at+1, at, at+1] }; psLength _ length; UNTIL psLength = 0 DO -- discard trailing "any's" SELECT TextFindPrivate.Pat[patternArray[psLength-1]] FROM TextFindPrivate.anyStringPat, TextFindPrivate.anyAlphaPat, TextFindPrivate.anyNonAlphaPat, TextFindPrivate.anyBlankPat, TextFindPrivate.anyNonBlankPat => NULL; ENDCASE => EXIT; psLength _ psLength-1; ENDLOOP; IF psLength=0 THEN RETURN [TRUE,start,start,start,start]; -- null pattern at _ start; RopeReader.SetPosition[ropeReader, rope, at]; DO -- text loop IF firstPatternCharIsNormal THEN { IF firstPatChar1 = TextFindPrivate.leftBoundaryPattern THEN { IF at > 0 THEN GOTO Return; -- failure since not at left boundary patternPos _ 1; textPos _ 0 } ELSE { -- search for next instance of first pattern char at _ MAX[start,at]; RopeReader.SetIndex[ropeReader, at]; UNTIL at >= end DO SELECT RopeReader.Get[ropeReader] FROM firstPatChar1, firstPatChar2 => IF patternLooks=NIL OR LooksMatch[at,0] THEN EXIT; ENDCASE; IF interrupt#NIL AND interrupt^ THEN GOTO Return; at _ at+1; ENDLOOP; patternPos _ 1; textPos _ at + 1 } } ELSE { patternPos _ 0; textPos _ at }; IF at >= end THEN EXIT; stackPtr _ patternAnchor _ 0; before _ beginPos _ textAnchor _ at; DO -- pattern loop IF patternPos >= psLength THEN { -- have finished pattern found _ TRUE; textPos _ MIN[end,textPos]; -- in case used final boundary char in making the match at _ MAX[start,beginPos]; -- in case used initial boundary char in making the match before _ MAX[before,start]; -- in case used initial boundary char in making the match atEnd _ IF rightBracketSeen THEN endPos ELSE textPos; after _ textPos; GO TO Return }; IF interrupt#NIL AND interrupt^ THEN GO TO Return; WITH p:patternArray[patternPos] SELECT FROM startname => { nameArray[p.index].at _ textPos; patternPos _ patternPos+1 }; endname => { nameArray[p.index].atEnd _ textPos; patternPos _ patternPos+1 }; not => { -- check that next character is not the one in this pattern element IF textPos NOT IN [start..end) THEN EXIT; char _ GetChar[textPos]; SELECT patternChar _ p.char FROM char => IF patternLooks=NIL OR LooksMatch[textPos,patternPos] THEN EXIT; >= TextFindPrivate.EightBit => { -- check both upper and lower case IF (SELECT patternChar _ CharBits[patternChar] FROM IN ['A..'Z] => patternChar = RopeEdit.UpperCase[char], IN ['a ..'z] => patternChar = RopeEdit.LowerCase[char], ENDCASE => patternChar = char) AND (patternLooks=NIL OR LooksMatch[textPos,patternPos]) THEN EXIT }; -- chars match ENDCASE; patternPos _ patternPos+1; textPos _ textPos + 1 }; pattern => { SELECT patternChar _ p.char FROM TextFindPrivate.leftBracketPattern => { beginPos _ textPos; patternPos _ patternPos+1 }; TextFindPrivate.rightBracketPattern => { endPos _ textPos; patternPos _ patternPos+1 }; TextFindPrivate.nopPattern => patternPos _ patternPos+1; TextFindPrivate.anyStringPattern => { IF patternLooks # NIL AND patternLooks[patternPos] # noLooks THEN { stackPtr _ stackPtr + 1; textPosStack[stackPtr] _ textPos; textLenStack[stackPtr] _ -1; patternPosStack[stackPtr] _ patternPos } ELSE { textAnchor _ textPos; patternAnchor _ patternPos + 1; stackPtr _ 0 }; patternPos _ patternPos + 1 }; TextFindPrivate.anyNonAlphaPattern, TextFindPrivate.anyAlphaPattern, TextFindPrivate.anyNonBlankPattern, TextFindPrivate.anyBlankPattern => { stackPtr _ stackPtr + 1; textPosStack[stackPtr] _ textPos; textLenStack[stackPtr] _ -1; patternPosStack[stackPtr] _ patternPos; patternPos _ patternPos + 1 }; TextFindPrivate.maxStringPattern => { IF patternLooks # NIL AND patternLooks[patternPos] # noLooks THEN { stackPtr _ stackPtr + 1; textPosStack[stackPtr] _ textPos; textLenStack[stackPtr] _ MaxCount[any]; patternPosStack[stackPtr] _ patternPos } ELSE { stackPtr _ 1; textPosStack[stackPtr] _ textPos; textLenStack[stackPtr] _ end-textPos; patternPosStack[stackPtr] _ patternPos }; textPos _ textPos + textLenStack[stackPtr]; patternPos _ patternPos + 1 }; TextFindPrivate.maxNonAlphaPattern, TextFindPrivate.maxAlphaPattern, TextFindPrivate.maxNonBlankPattern, TextFindPrivate.maxBlankPattern => { stackPtr _ stackPtr + 1; textPosStack[stackPtr] _ textPos; textLenStack[stackPtr] _ SELECT patternChar FROM TextFindPrivate.maxNonAlphaPattern => MaxCount[ne, alphaNumeric], TextFindPrivate.maxAlphaPattern => MaxCount[eq, alphaNumeric], TextFindPrivate.maxNonBlankPattern => MaxCount[ne, white], TextFindPrivate.maxBlankPattern => MaxCount[eq, white], ENDCASE => ERROR; textPos _ textPos + textLenStack[stackPtr]; patternPosStack[stackPtr] _ patternPos; patternPos _ patternPos + 1 }; ENDCASE => { -- check next character from text boundary: BOOL _ FALSE; IF textPos IN [start..end) THEN {char _ GetChar[textPos]} ELSE { char _ TextFindPrivate.rightBoundaryPattern; IF patternChar # TextFindPrivate.rightBoundaryPattern THEN boundary _ TRUE; }; IF NOT boundary AND patternChar = TextFindPrivate.oneCharPattern AND (patternLooks = NIL OR LooksMatch[textPos,patternPos]) THEN { IF patternPos # 0 AND patternPos = patternAnchor THEN { <> patternAnchor _ patternAnchor + 1; textAnchor _ textPos + 1 }; patternPos _ patternPos + 1; textPos _ textPos + 1 } ELSE { IF NOT boundary AND (SELECT patternChar FROM char => TRUE, -- this also takes care of rightBoundaryPattern TextFindPrivate.oneNonAlphaPattern => RopeEdit.GetCharProp[char] # alphaNumeric, TextFindPrivate.oneAlphaPattern => RopeEdit.GetCharProp[char] = alphaNumeric, TextFindPrivate.oneNonBlankPattern => RopeEdit.GetCharProp[char] # white, TextFindPrivate.oneBlankPattern => RopeEdit.GetCharProp[char] = white, TextFindPrivate.oneCharPattern => FALSE, -- known from above that looks don't match >= TextFindPrivate.EightBit => -- check both upper and lower case SELECT patternChar _ CharBits[patternChar] FROM IN ['A..'Z] => patternChar = RopeEdit.UpperCase[char], IN ['a ..'z] => patternChar = RopeEdit.LowerCase[char], ENDCASE => patternChar = char, ENDCASE => FALSE) AND (patternLooks=NIL OR LooksMatch[textPos,patternPos]) THEN -- chars match -- { patternPos _ patternPos + 1; textPos _ textPos + 1 } ELSE { -- chars don't match; try to change some wild card position WHILE stackPtr # 0 DO txtpos: INT _ textPosStack[stackPtr]; txtlen: INT _ textLenStack[stackPtr]; IF interrupt#NIL AND interrupt^ THEN GO TO Return; IF txtlen < 0 THEN { -- this is an incrementing wildcard ppos: NAT; boundary _ FALSE; IF txtpos IN [start..end) THEN { charType _ RopeEdit.GetCharProp[GetChar[txtpos]]; } ELSE { boundary _ TRUE }; IF NOT boundary AND (SELECT TextFindPrivate.Pat[patternArray[ppos_patternPosStack[stackPtr]]] FROM TextFindPrivate.anyNonAlphaPat => charType # alphaNumeric, TextFindPrivate.anyAlphaPat => charType = alphaNumeric, TextFindPrivate.anyNonBlankPat => charType # white, TextFindPrivate.anyBlankPat => charType = white, TextFindPrivate.anyStringPat => TRUE, ENDCASE => ERROR) AND (patternLooks=NIL OR LooksMatch[txtpos,ppos]) THEN { patternPos _ ppos + 1; textPos _ textPosStack[stackPtr] _ txtpos + 1; EXIT } } ELSE IF txtlen > 0 THEN { -- this is a decrementing wildcard patternPos _ patternPosStack[stackPtr] + 1; textPos _ textPosStack[stackPtr] + txtlen - 1; textLenStack[stackPtr] _ txtlen - 1; EXIT } ELSE NULL; -- decrementing wildcard with no place left to go stackPtr _ stackPtr - 1; ENDLOOP; IF stackPtr = 0 THEN -- failed to match a stacked wild card IF patternAnchor > 0 AND textAnchor < end THEN { <> patternPos _ patternAnchor; textPos _ textAnchor _ textAnchor + 1 } ELSE EXIT --start matching over at next text location-- } } } }; ENDCASE; ENDLOOP; -- end of pattern loop at _ at+1; -- start over with next character ENDLOOP; -- end of text loop EXITS Return => NULL; }; -- of Try -- <> SearchRopeBackwards: PUBLIC PROC [finder: Finder, rope: ROPE, start: INT _ 0, len: INT _ maxLen, interrupt: REF BOOL _ NIL] RETURNS [found: BOOL, at, atEnd, before, after: INT] = { [found, at, atEnd, before, after] _ SearchBackwards[finder, rope, NIL, start, len, FALSE, interrupt] }; TryFindBackwards: PUBLIC PROC [finder: Finder, text: Node, start: INT _ 0, len: INT _ maxLen, looksExact: BOOL _ FALSE, interrupt: REF BOOL _ NIL] RETURNS [found: BOOL, at, atEnd, before, after: INT] = { [found, at, atEnd, before, after] _ SearchBackwards[finder, GetRope[text], GetRuns[text], start, len, looksExact, interrupt] }; SearchBackwards: PROC [finder: Finder, rope: ROPE, runs: TextLooks.Runs, start: INT, len: INT, looksExact: BOOL, interrupt: REF BOOL _ NIL] RETURNS [found: BOOL, at, atEnd, before, after: INT] = { IF finder.wordSearch THEN DO -- repeat search until find a word [found, at, atEnd, before, after] _ TryToFindBackwards[finder, rope, runs, start, len, looksExact]; IF NOT found OR (interrupt#NIL AND interrupt^) THEN RETURN; -- failed IF TextFindPrivate.IsWord[rope, at, atEnd] THEN RETURN; -- got it len _ before-start; -- try again ENDLOOP; [found, at, atEnd, before, after] _ TryToFindBackwards[finder, rope, runs, start, len, looksExact, interrupt] }; TryToFindBackwards: PROC [finder: Finder, rope: ROPE, runs: TextLooks.Runs, start: INT _ 0, len: INT _ maxLen, looksExact: BOOL _ FALSE, interrupt: REF BOOL _ NIL] RETURNS [found: BOOL, at, atEnd, before, after: INT] = { patternPosStack: REF TextFindPrivate.PatternStackArray ~ finder.patternPosStack; textPosStack: REF TextFindPrivate.TextStackArray ~ finder.textPosStack; textLenStack: REF TextFindPrivate.TextStackArray ~ finder.textLenStack; patternArray: REF TextFindPrivate.PatternArray ~ finder.patternArray; length: NAT ~ finder.length; patternLooks: REF TextFindPrivate.LooksArray ~ finder.patternLooks; nameArray: REF TextFindPrivate.NameArray ~ finder.nameArray; lastPatChar1: CHAR ~ finder.lastPatChar1; lastPatChar2: CHAR ~ finder.lastPatChar2; ropeReader: RopeReader.Ref ~ finder.ropeReader; lksReader: LooksReader.Ref ~ finder.lksReader; looks: Looks ~ finder.looks; looksOnly: BOOL ~ finder.looksOnly; leftBracketSeen: BOOL _ finder.leftBracketSeen; lastPatternCharIsNormal: BOOL ~ finder.lastPatternCharIsNormal; stackPtr, patternPos, patternAnchor, patternFirst: NAT _ 0; char, patternChar: CHAR _ 377C; charType: RopeEdit.CharProperty; beginPos, endPos, textPos, textAnchor, end, size: INT; psLength: NAT; LooksMatch: PROC [txtpos: INT, ppos: NAT] RETURNS [BOOL] = { patlks, sourcelks: Looks; IF (patlks _ patternLooks[ppos-1]) = noLooks THEN RETURN [TRUE]; IF runs=NIL THEN RETURN [FALSE]; -- pattern has looks and text doesn't IF txtpos NOT IN (start..end] THEN RETURN [FALSE]; -- boundary char has no looks LooksReader.SetPosition[lksReader,runs,txtpos]; sourcelks _ LooksReader.Backwards[lksReader]; RETURN[patlks=(IF looksExact THEN sourcelks ELSE TextLooks.LooksAND[sourcelks,patlks])] }; GetChar: PROC [txtpos: INT] RETURNS [char: CHAR] = { SELECT txtpos FROM IN (start..end] => { -- read the character from the rope char _ Rope.Fetch[rope, txtpos-1]; }; ENDCASE => ERROR; }; PropTest: TYPE = { eq, ne, any }; MaxCount: PROC [propTest: PropTest, property: RopeEdit.CharProperty _ illegal] RETURNS [count: INT] = { count _ 0; DO IF textPos-count NOT IN (start..end] THEN EXIT; char _ GetChar[textPos-count]; IF propTest=eq THEN IF RopeEdit.GetCharProp[char] # property THEN EXIT ELSE NULL ELSE IF propTest=ne AND RopeEdit.GetCharProp[char]=property THEN EXIT ELSE NULL; IF patternLooks # NIL AND patternLooks[patternPos] # noLooks AND NOT LooksMatch[textPos-count, patternPos] THEN EXIT; count _ count+1; ENDLOOP; }; size _ Rope.Size[rope]; start _ MIN[MAX[0,start],size]; len _ MIN[MAX[0,len],size-start]; end _ start+len; found _ FALSE; atEnd _ end; IF looksOnly THEN { looksReader: LooksReader.Ref ~ LooksReader.GetLooksReader[]; LooksReader.SetPosition[looksReader, runs, end]; atEnd _ end; WHILE atEnd > start DO lks: Looks _ LooksReader.Backwards[looksReader]; IF NOT looksExact THEN lks _ TextLooks.LooksAND[lks, looks]; IF lks = looks THEN EXIT; -- have found a match atEnd _ atEnd-1; ENDLOOP; LooksReader.FreeLooksReader[looksReader]; IF atEnd <= start THEN RETURN; -- failed to find a match RETURN [TRUE, atEnd-1, atEnd, atEnd-1, atEnd] }; psLength _ length; UNTIL patternFirst = psLength DO -- discard leading "any's" SELECT TextFindPrivate.Pat[patternArray[patternFirst]] FROM TextFindPrivate.anyStringPat, TextFindPrivate.anyAlphaPat, TextFindPrivate.anyNonAlphaPat, TextFindPrivate.anyBlankPat, TextFindPrivate.anyNonBlankPat => NULL; ENDCASE => EXIT; patternFirst _ patternFirst+1; ENDLOOP; IF patternFirst = psLength THEN RETURN [TRUE, end, end, end, end]; -- null pattern DO -- text loop IF lastPatternCharIsNormal THEN { IF lastPatChar1 = TextFindPrivate.rightBoundaryPattern THEN { IF atEnd < size THEN RETURN; -- failed since not at end of node patternPos _ psLength-1; textPos _ atEnd } ELSE { -- search for next instance of last pattern char atEnd _ MIN[end,atEnd]; RopeReader.SetPosition[ropeReader, rope, atEnd]; UNTIL atEnd <= start DO SELECT RopeReader.Backwards[ropeReader] FROM lastPatChar1, lastPatChar2 => IF patternLooks=NIL OR LooksMatch[atEnd, psLength] THEN EXIT; ENDCASE; atEnd _ atEnd-1; ENDLOOP; patternPos _ psLength-1; textPos _ atEnd - 1 } } ELSE { patternPos _ psLength; textPos _ atEnd }; IF atEnd <= start THEN EXIT; stackPtr _ 0; patternAnchor _ psLength; after _ endPos _ textAnchor _ atEnd; DO -- pattern loop IF patternPos <= patternFirst THEN { -- have finished pattern found _ TRUE; textPos _ MAX[start,textPos]; -- in case used initial boundary char in making the match atEnd _ MIN[end,endPos]; -- in case used final boundary char in making the match after _ MIN[after,end]; -- in case used final boundary char in making the match at _ IF leftBracketSeen THEN beginPos ELSE textPos; before _ textPos; GO TO Return }; IF interrupt#NIL AND interrupt^ THEN GO TO Return; WITH p:patternArray[patternPos-1] SELECT FROM startname => { nameArray[p.index].at _ textPos; patternPos _ patternPos-1 }; endname => { nameArray[p.index].atEnd _ textPos; patternPos _ patternPos-1 }; not => { -- check that next character is not the one in this pattern element IF textPos NOT IN (start..end] THEN EXIT; char _ GetChar[textPos]; SELECT patternChar _ p.char FROM char => IF patternLooks=NIL OR LooksMatch[textPos,patternPos] THEN EXIT; >= TextFindPrivate.EightBit => { -- check both upper and lower case IF (SELECT patternChar _ CharBits[patternChar] FROM IN ['A..'Z] => patternChar = RopeEdit.UpperCase[char], IN ['a ..'z] => patternChar = RopeEdit.LowerCase[char], ENDCASE => patternChar = char) AND (patternLooks=NIL OR LooksMatch[textPos,patternPos]) THEN EXIT }; -- chars match ENDCASE; patternPos _ patternPos-1; textPos _ textPos - 1 }; pattern => { SELECT patternChar _ p.char FROM TextFindPrivate.leftBracketPattern => { beginPos _ textPos; patternPos _ patternPos-1 }; TextFindPrivate.rightBracketPattern => { endPos _ textPos; patternPos _ patternPos-1 }; TextFindPrivate.nopPattern => patternPos _ patternPos-1; TextFindPrivate.anyStringPattern => { IF patternLooks # NIL AND patternLooks[patternPos-1] # noLooks THEN { stackPtr _ stackPtr + 1; textPosStack[stackPtr] _ textPos; patternPosStack[stackPtr] _ patternPos } ELSE { textAnchor _ textPos; patternAnchor _ patternPos - 1; stackPtr _ 0 }; patternPos _ patternPos - 1 }; TextFindPrivate.anyNonAlphaPattern, TextFindPrivate.anyAlphaPattern, TextFindPrivate.anyNonBlankPattern, TextFindPrivate.anyBlankPattern => { stackPtr _ stackPtr + 1; textPosStack[stackPtr] _ textPos; patternPosStack[stackPtr] _ patternPos; patternPos _ patternPos - 1 }; TextFindPrivate.maxStringPattern => { IF patternLooks # NIL AND patternLooks[patternPos] # noLooks THEN { stackPtr _ stackPtr + 1; textPosStack[stackPtr] _ textPos; textLenStack[stackPtr] _ MaxCount[any]; patternPosStack[stackPtr] _ patternPos } ELSE { stackPtr _ 1; textPosStack[stackPtr] _ textPos; textLenStack[stackPtr] _ textPos-start; patternPosStack[stackPtr] _ patternPos }; textPos _ textPos - textLenStack[stackPtr]; patternPos _ patternPos - 1 }; TextFindPrivate.maxNonAlphaPattern, TextFindPrivate.maxAlphaPattern, TextFindPrivate.maxNonBlankPattern, TextFindPrivate.maxBlankPattern => { stackPtr _ stackPtr + 1; textPosStack[stackPtr] _ textPos; textLenStack[stackPtr] _ SELECT patternChar FROM TextFindPrivate.maxNonAlphaPattern => MaxCount[ne, alphaNumeric], TextFindPrivate.maxAlphaPattern => MaxCount[eq, alphaNumeric], TextFindPrivate.maxNonBlankPattern => MaxCount[ne, white], TextFindPrivate.maxBlankPattern => MaxCount[eq, white], ENDCASE => ERROR; textPos _ textPos - textLenStack[stackPtr]; patternPosStack[stackPtr] _ patternPos; patternPos _ patternPos - 1 }; ENDCASE => { -- check next character from text boundary: BOOL _ FALSE; IF textPos IN (start..end] THEN {char _ GetChar[textPos]} ELSE { char _ TextFindPrivate.leftBoundaryPattern; IF patternChar # TextFindPrivate.leftBoundaryPattern THEN boundary _ TRUE; }; IF NOT boundary AND patternChar = TextFindPrivate.oneCharPattern AND (patternLooks = NIL OR LooksMatch[textPos,patternPos]) THEN { IF patternPos # psLength AND patternPos = patternAnchor THEN { -- first char(s) of * segment patternAnchor _ patternAnchor - 1; textAnchor _ textPos - 1 }; patternPos _ patternPos - 1; textPos _ textPos - 1 } ELSE { IF NOT boundary AND (SELECT patternChar FROM char => TRUE, -- this also takes care of leftBoundaryPattern TextFindPrivate.oneNonAlphaPattern => RopeEdit.GetCharProp[char] # alphaNumeric, TextFindPrivate.oneAlphaPattern => RopeEdit.GetCharProp[char] = alphaNumeric, TextFindPrivate.oneNonBlankPattern => RopeEdit.GetCharProp[char] # white, TextFindPrivate.oneBlankPattern => RopeEdit.GetCharProp[char] = white, TextFindPrivate.oneCharPattern => FALSE, -- known from above that looks don't match >= TextFindPrivate.EightBit => -- check both upper and lower case SELECT patternChar _ CharBits[patternChar] FROM IN ['A..'Z] => patternChar = RopeEdit.UpperCase[char], IN ['a ..'z] => patternChar = RopeEdit.LowerCase[char], ENDCASE => patternChar = char, ENDCASE => FALSE) AND (patternLooks=NIL OR LooksMatch[textPos,patternPos]) THEN -- chars match -- { patternPos _ patternPos - 1; textPos _ textPos - 1 } ELSE { -- chars don't match; try to increment some wild card position WHILE stackPtr # 0 DO txtpos: INT _ textPosStack[stackPtr]; txtlen: INT _ textLenStack[stackPtr]; IF interrupt#NIL AND interrupt^ THEN GO TO Return; IF txtlen < 0 THEN { -- this is an incrementing wildcard boundary: BOOL _ FALSE; ppos: NAT; IF txtpos IN (start..end] THEN { charType _ RopeEdit.GetCharProp[GetChar[txtpos]] } ELSE { boundary _ TRUE; }; IF NOT boundary AND (SELECT TextFindPrivate.Pat[patternArray[(ppos_patternPosStack[stackPtr])-1]] FROM TextFindPrivate.anyNonAlphaPat => charType # alphaNumeric, TextFindPrivate.anyAlphaPat => charType = alphaNumeric, TextFindPrivate.anyNonBlankPat => charType # white, TextFindPrivate.anyBlankPat => charType = white, TextFindPrivate.anyStringPat => TRUE, ENDCASE => ERROR) AND (patternLooks=NIL OR LooksMatch[txtpos,ppos]) THEN { patternPos _ ppos - 1; textPos _ textPosStack[stackPtr] _ txtpos - 1; EXIT } } ELSE IF txtlen > 0 THEN { -- this is a decrementing wildcard patternPos _ patternPosStack[stackPtr] - 1; textPos _ textPosStack[stackPtr] - txtlen + 1; textLenStack[stackPtr] _ txtlen - 1; EXIT } ELSE NULL; -- decrementing wildcard with no place left to go stackPtr _ stackPtr - 1; ENDLOOP; IF stackPtr = 0 THEN -- failed to match a stacked wild card IF patternAnchor < psLength AND textAnchor > start THEN { <> patternPos _ patternAnchor; textPos _ textAnchor _ textAnchor - 1 } ELSE EXIT --start matching over at next text location-- } } } }; ENDCASE; ENDLOOP; -- end of pattern loop atEnd _ atEnd-1; -- start over with next character ENDLOOP; -- end of text loop EXITS Return => NULL; }; END.