<> <> <> <> <> <> DIRECTORY Basics USING [BITAND], LooksReader USING [FreeLooksReader, GetLooksReader, Backwards, SetPosition, Ref], Rope USING [Fetch, ROPE, Size], RopeEdit USING [CharProperty, GetCharProp, LowerCase, MaxLen, UpperCase], RopeReader USING [SetPosition, Backwards, Ref], TextEdit USING [GetRope, GetRuns], TextFind, TextFindPrivate, TextLooks USING [Looks, Runs, noLooks], TextLooksSupport USING [LooksAND], TextNode USING [Ref]; TextFind3Impl: CEDAR PROGRAM IMPORTS TextFindPrivate, RopeReader, TextEdit, TextLooksSupport, LooksReader, RopeEdit, Rope, Basics EXPORTS TextFind = BEGIN OPEN TextFind; ROPE: TYPE ~ Rope.ROPE; <<>> <<***** Operations *****>> noLooks: TextLooks.Looks ~ TextLooks.noLooks; SearchRopeBackwards: 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] _ SearchBackwards[finder, rope, NIL, start, len, FALSE, interrupt] }; TryBackwards: 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] _ SearchBackwards[finder, TextEdit.GetRope[text], TextEdit.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 _ 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; lastPatChar1: CHAR ~ finder.lastPatChar1; lastPatChar2: CHAR ~ finder.lastPatChar2; ropeReader: RopeReader.Ref ~ finder.ropeReader; lksReader: LooksReader.Ref ~ finder.lksReader; looks: TextLooks.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: TextLooks.Looks; IF (patlks _ patternLooks[ppos-1]) = 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.Backwards[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-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] # 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; atEnd _ end; IF looksOnly THEN { looksReader: LooksReader.Ref ~ LooksReader.GetLooksReader[]; LooksReader.SetPosition[looksReader, runs, end]; atEnd _ end; WHILE atEnd > start DO lks: TextLooks.Looks _ LooksReader.Backwards[looksReader]; IF NOT looksExact THEN lks _ TextLooksSupport.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; }; CharBits: PROC [c: CHAR] RETURNS [CHAR] = INLINE { RETURN [LOOPHOLE[Basics.BITAND[LOOPHOLE[TextFindPrivate.CharMask],LOOPHOLE[c]], CHAR]]; }; END.