DIRECTORY Basics USING [BITAND], LooksReader USING [FreeLooksReader, Get, GetLooksReader, InlineGet, SetPosition, Ref], Rope USING [Fetch, ROPE, Size], RopeEdit USING [CharProperty, GetCharProp, LowerCase, MaxLen, UpperCase], RopeReader USING [Get, Ref, SetIndex, SetPosition], TextEdit USING [GetRope, GetRuns], TextFind, TextFindPrivate, TextLooks USING [Looks, noLooks, Runs], TextLooksSupport USING [LooksAND], TextNode USING [Ref]; TextFind2Impl: CEDAR PROGRAM IMPORTS TextFindPrivate, RopeReader, TextEdit, TextLooksSupport, LooksReader, RopeEdit, Rope, Basics EXPORTS TextFind, TextFindPrivate = BEGIN OPEN TextFind; ROPE: TYPE = Rope.ROPE; SearchRope: PUBLIC PROC [finder: Finder, rope: Rope.ROPE, start: INT _ 0, len: INT _ RopeEdit.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] }; Try: PUBLIC PROC [finder: Finder, text: TextNode.Ref, start: INT _ 0, len: INT _ RopeEdit.MaxLen, looksExact: BOOL _ FALSE, interrupt: REF BOOL _ NIL] RETURNS [found: BOOL, at, atEnd, before, after: INT] = { [found, at, atEnd, before, after] _ Search[ finder, TextEdit.GetRope[text], TextEdit.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]; 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 _ RopeEdit.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: TextLooks.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: TextLooks.Looks; IF (patlks _ patternLooks[ppos]) = TextLooks.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 TextLooksSupport.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] # TextLooks.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: TextLooks.Looks _ LooksReader.InlineGet[looksReader]; IF NOT looksExact THEN lks _ TextLooksSupport.LooksAND[lks, looks]; IF lks = looks THEN EXIT; -- have found a match 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 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; 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] # TextLooks.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] # TextLooks.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 -- CharBits: PROC [c: CHAR] RETURNS [CHAR] = INLINE { RETURN [LOOPHOLE[Basics.BITAND[LOOPHOLE[TextFindPrivate.CharMask],LOOPHOLE[c]], CHAR]]; }; END. ŒTextFind2Impl.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Paxton, February 24, 1983 9:54 am Russ Atkinson, July 25, 1983 3:23 pm Doug Wyatt, March 3, 1985 2:53:22 pm PST Michael Plass, September 3, 1985 9:23:45 am PDT ***** Operations ***** RopeReader.SetPosition[ropeReader,rope,txtpos+1]; first char(s) of * segment there was a * with no looks, so can advance it Κ q˜šœ™Jšœ Οmœ1™J˜:J˜7Jšžœžœ˜—J˜+J˜'J˜J˜—Jšžœ‘!˜.Jšœ žœžœ˜Jšžœ žœžœ˜9šžœ˜J˜,Jšžœ4žœ žœ˜KJšœ˜—Jšžœžœ žœ.ž˜Dšœžœžœ!žœ˜=šžœžœžœ˜7Jšœ™J˜;J˜—J˜3J˜—šžœ˜š žœžœ žœžœ ž˜,Jšœžœ‘/˜=J˜PJ˜MJ˜IJ˜FJšœ"žœ‘*˜SJšœ‘"˜Ašžœ%ž˜/Jšžœ4˜6Jšžœ5˜7Jšžœ˜—Jšžœžœ˜—Jšžœžœžœ ˜8šžœ‘œ˜J˜3J˜—šžœ‘;˜Bšžœž˜Jšœžœ˜%Jšœžœ˜%Jš žœ žœžœ žœžœžœ˜2šžœ žœ‘#˜8Jšœžœ˜ Jšœ žœ˜šžœžœžœ˜ Jšœ1˜1Jšœ˜—šžœ˜Jšœ ž˜Jšœ˜—Jšžœžœ ž˜šœžœCž˜NJ˜:J˜7J˜3J˜0Jšœ žœ˜%Jšžœžœ˜—šžœžœžœžœ˜8J˜J˜.Jšžœ˜J˜—J˜—šžœžœ žœ‘"˜