-- 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.