DIRECTORY
TextFind,
RegExpFindPrivate USING [FinderRecord, PatternOpCodeArray, PatternLooksArray, PatternDataArray, PatternNextArray, PatternStackArray, TextStackArray, ReturnCodeArray, ReturnCode, ClassArray, CharClass, Index, OpCode],
TextLooks USING [Looks, noLooks, Runs],
TextEdit USING [GetRope, GetRuns],
TextNode USING [RefTextNode, Offset],
Rope USING [ROPE, Fetch, Size],
Ascii USING [Upper],
Basics USING [LongNumber, HighHalf, LowHalf],
RopeEdit USING [GetCharProp],
RopeReader USING [SetPosition, Get, GetIndex, Ref],
RunReader USING [Ref],
LooksReader USING [Get, SetPosition, Ref];

RegExpFind2Impl: CEDAR PROGRAM
IMPORTS TextEdit, RopeReader, RunReader, LooksReader, RopeEdit, Rope, Ascii, Basics
EXPORTS TextFind, RegExpFindPrivate = {
OPEN RegExpFindPrivate;

Finder: TYPE = REF FinderRec;
FinderRec: PUBLIC TYPE = FinderRecord;
ROPE: TYPE = Rope.ROPE;
Offset: TYPE = TextNode.Offset;
RefTextNode: TYPE = TextNode.RefTextNode;

SearchRope: PUBLIC PROC [finder: Finder, rope: ROPE, start: Offset, len: Offset, interrupt: REF BOOL] RETURNS [found: BOOL, at, atEnd, before, after: Offset] = {
[found, at, atEnd, before, after] _ Search[finder, rope, NIL, start, len, FALSE, interrupt]
};


Try: PUBLIC PROC [finder: Finder, text: RefTextNode, start: Offset, len: Offset, looksExact: BOOL, interrupt: REF BOOL] RETURNS [found: BOOL, at, atEnd, before, after: Offset] = {
[found, at, atEnd, before, after] _ 
Search[finder, TextEdit.GetRope[text], TextEdit.GetRuns[text], start, len, looksExact, interrupt];
};

Search: PUBLIC PROC [finder: Finder, rope: ROPE, runs: TextLooks.Runs, start: Offset, len: Offset, looksExact: BOOLEAN, interrupt: REF BOOL _ NIL] RETURNS [found: BOOLEAN, at, atEnd, before, after: Offset] = {
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 ~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: Offset] RETURNS [BOOLEAN] = {
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: Offset, len: Offset, looksExact: BOOLEAN, interrupt: REF BOOL] RETURNS [found: BOOLEAN, at, atEnd, before, after: Offset] = {
Character: TYPE = Index;
currentChar: Character;
currentCHAR: CHAR;
end: Offset _ start+MIN[len, Rope.Size[rope]-start];
nextPos: Offset _ start;
NoMoreChars: Character = 666;
NoNodeBreakBound: Index = 32177;
pc: Index _ 0;
nodeBreakBound: Index _ NoNodeBreakBound;
opCode: REF PatternOpCodeArray _ finder.forwardProgram.opCodes;
looks: REF PatternLooksArray _ finder.forwardProgram.looks;
data: REF PatternDataArray _ finder.forwardProgram.data;
next: REF PatternNextArray _ finder.forwardProgram.next;
pcStack: REF PatternStackArray _ finder.stack.pc;
nextPosStack: REF TextStackArray _ finder.stack.nextPos;
returnCodeStack: REF ReturnCodeArray _ finder.stack.returnCode;
charClass: REF ClassArray _ finder.classes;
stackPos: Index _ 0;
ropeReader: RopeReader.Ref _ finder.ropeReader;
lksReader: LooksReader.Ref _ finder.lksReader;
runReader: RunReader.Ref _ finder.runReader;
AdvanceChar: PROC [] = INLINE {
IF nextPos < end THEN {
currentChar _ (currentCHAR _ RopeReader.Get[ropeReader]) - 0C;
nextPos _ nextPos + 1;
}
ELSE {
currentChar _ NoMoreChars;
currentCHAR _ '\000;
nextPos _ end + 1;
};
};
PushPos: PROC [returnCode: ReturnCode] = INLINE {
pcStack[stackPos] _ pc;
nextPosStack[stackPos] _ nextPos;
returnCodeStack[stackPos] _ returnCode;
stackPos _ stackPos + 1;
};
TestLooks: PROC [] RETURNS [BOOL] = {
sourcelks: TextLooks.Looks;
IF runs=NIL THEN RETURN [FALSE]; -- pattern has looks and text doesn't
IF nextPos NOT IN (start..end] THEN RETURN [FALSE]; -- boundary char has no looks
LooksReader.SetPosition[lksReader, runs, nextPos-1];
sourcelks _ LooksReader.Get[lksReader];
RETURN[
looks[pc]=(IF looksExact THEN sourcelks ELSE TextLooksSupport.LooksAND[sourcelks, looks[pc]])]; 
};
Begin: PROC [] = {
IF start < end THEN 
RopeReader.SetPosition[ropeReader, rope, start];
AdvanceChar[];
};
DoFieldEquals: PROC [ignoreCase: BOOL] RETURNS [BOOL] = {
pos: Offset _ finder.nameArray[data[pc]].at;
WHILE pos < finder.nameArray[data[pc]].atEnd DO
c: CHAR _ rope.Fetch[pos];
IF ignoreCase THEN {
IF Ascii.Upper[c] # Ascii.Upper[currentCHAR] THEN RETURN [FALSE];
}
ELSE
IF c # currentCHAR THEN RETURN [FALSE];
pos _ pos + 1;
AdvanceChar[];
ENDLOOP;
RETURN[TRUE];
};
DoFieldEqualsLooks: PROC [ignoreCase: BOOL] RETURNS [BOOL] = {
pos: Offset _ finder.nameArray[data[pc]].at;
IF runs=NIL THEN RETURN [FALSE]; -- pattern has looks and text doesn't
WHILE pos < finder.nameArray[data[pc]].atEnd DO
c: CHAR _ rope.Fetch[pos];
fieldLooks, nextLooks: TextLooks.Looks;
IF ignoreCase THEN {
IF Ascii.Upper[c] # Ascii.Upper[currentCHAR] THEN RETURN [FALSE];
}
ELSE
IF c # currentCHAR THEN RETURN [FALSE];
IF nextPos NOT IN (start..end] THEN RETURN [FALSE];
LooksReader.SetPosition[lksReader, runs, pos];
fieldLooks _ LooksReader.Get[lksReader];
LooksReader.SetPosition[lksReader, runs, nextPos-1];
nextLooks _ LooksReader.Get[lksReader];
IF fieldLooks # (IF looksExact THEN nextLooks ELSE TextLooksSupport.LooksAND[fieldLooks, nextLooks]) THEN RETURN[FALSE];
pos _ pos + 1;
AdvanceChar[];
ENDLOOP;
RETURN[TRUE];
};
DoCarefulGreedyClosureEnd: PROC [] RETURNS [BOOL] = {
lastCarefulNextPos: Basics.LongNumber;
lastCarefulNextPos.lowbits _ data[next[data[pc]]+1];
lastCarefulNextPos.highbits _ next[next[data[pc]]+1];
TRUSTED {
RETURN[lastCarefulNextPos # LOOPHOLE[nextPos]];
};
};
Begin[];
DO
DO
SELECT opCode[pc] FROM
matchChar => 
IF currentChar = data[pc] THEN
AdvanceChar[]
ELSE
GOTO Failure;
matchCharIC =>
IF Ascii.Upper[currentCHAR] = VAL[data[pc]] THEN
AdvanceChar[]
ELSE
GOTO Failure;
matchCharLooks =>
IF currentChar = data[pc] AND TestLooks[] THEN
AdvanceChar[]
ELSE
GOTO Failure;
matchCharLooksIC =>
IF Ascii.Upper[currentCHAR] = VAL[data[pc]] AND TestLooks[] THEN
AdvanceChar[]
ELSE
GOTO Failure;
matchClass => 
IF charClass[data[pc]][currentCHAR] THEN
AdvanceChar[]
ELSE
GOTO Failure;
matchClassLooks =>
IF charClass[data[pc]][currentCHAR] AND TestLooks[] THEN
AdvanceChar[]
ELSE
GOTO Failure;
matchAnyChar => 
IF currentChar # NoMoreChars THEN
AdvanceChar[]
ELSE
GOTO Failure;
matchAnyCharLooks =>
IF currentChar # NoMoreChars AND TestLooks[] THEN
AdvanceChar[]
ELSE
GOTO Failure;
matchNodeBreak =>
IF ~(nextPos=Rope.Size[rope]+1 AND currentChar=NoMoreChars) THEN GOTO Failure;
skipToNodeBreak => {
IF end < Rope.Size[rope] THEN GOTO Failure;
nextPos _ end;
RopeReader.SetPosition[ropeReader, rope, nextPos];
AdvanceChar[];
};
skipToNodeBreakLooks => {
IF end < Rope.Size[rope] THEN GOTO Failure;
WHILE currentChar # NoMoreChars DO
IF ~TestLooks[] THEN GOTO Failure;
AdvanceChar[];
ENDLOOP;
};
matchBeginNode =>
IF nextPos # 1 THEN GOTO Failure;
fail => 
GOTO Failure;
succeed => 
GOTO AbsoluteSuccess;
noOp => 
NULL;
skipOverClass => {
ccl: CharClass _ charClass[data[pc]];
WHILE ccl[currentCHAR] DO
AdvanceChar[];
ENDLOOP;
IF currentChar = NoMoreChars THEN GOTO Failure;
};
skipOverClassLooks => { 
ccl: CharClass _ charClass[data[pc]];
WHILE ccl[currentCHAR] AND TestLooks[] DO
AdvanceChar[];
ENDLOOP;
IF currentChar = NoMoreChars THEN GOTO Failure;
};
skipOverChar => {
c: CHAR _ VAL[data[pc]];
WHILE currentCHAR = c DO
AdvanceChar[];
ENDLOOP;
IF currentChar = NoMoreChars THEN GOTO Failure;
};
skipOverCharLooks => {
c: CHAR _ VAL[data[pc]];
WHILE currentCHAR = c AND TestLooks[] DO
AdvanceChar[];
ENDLOOP;
IF currentChar = NoMoreChars THEN GOTO Failure;
};
skipOverCharIC => {
c: CHAR _ VAL[data[pc]];
WHILE Ascii.Upper[currentCHAR] = c DO
AdvanceChar[];
ENDLOOP;
IF currentChar = NoMoreChars THEN GOTO Failure;
};
skipOverCharLooksIC => {
c: CHAR _ VAL[data[pc]];
WHILE Ascii.Upper[currentCHAR] = c AND TestLooks[] DO
AdvanceChar[];
ENDLOOP;
IF currentChar = NoMoreChars THEN GOTO Failure;
};
skipToChar => {
c: CHAR _ VAL[data[pc]];
UNTIL currentCHAR = c DO
IF currentChar = NoMoreChars THEN GOTO Failure;
AdvanceChar[];
ENDLOOP;
};
skipToCharLooks => {
c: CHAR _ VAL[data[pc]];
UNTIL currentCHAR = c AND TestLooks[] DO
IF currentChar = NoMoreChars THEN GOTO Failure;
AdvanceChar[];
ENDLOOP;
};
skipToCharIC => {
c: CHAR _ VAL[data[pc]];
UNTIL Ascii.Upper[currentCHAR] = c DO
IF currentChar = NoMoreChars THEN GOTO Failure;
AdvanceChar[];
ENDLOOP;
};
skipToCharLooksIC => {
c: CHAR _ VAL[data[pc]];
UNTIL Ascii.Upper[currentCHAR] = c AND TestLooks[] DO
IF currentChar = NoMoreChars THEN GOTO Failure;
AdvanceChar[];
ENDLOOP;
};
skipToString => {
PushPos[skipToStringRet];
};
endOfSkipToString => {
stackPos _ stackPos-1;
nextPos _ nextPosStack[stackPos]-1;
RopeReader.SetPosition[ropeReader, rope, nextPos];
AdvanceChar[];
};
skipToEnd => {
nextPos _ end;
AdvanceChar[];
};
skipToBeginning => { 
nextPos _ start;
AdvanceChar[];
};
closure, greedyClosure, alt =>
PushPos[closureRet];
carefulClosure => {
PushPos[closureRet];
data[data[pc]+1] _ Basics.LowHalf[nextPos];
next[data[pc]+1] _ Basics.HighHalf[nextPos];
};
carefulClosure, carefulGreedyClosure => {
PushPos[closureRet];
data[next[pc]+1] _ Basics.LowHalf[nextPos];
next[next[pc]+1] _ Basics.HighHalf[nextPos];
};
carefulClosureEnd => {
lastCarefulNextPos: Basics.LongNumber;
lastCarefulNextPos.lowbits _ data[data[data[pc]]+1];
lastCarefulNextPos.highbits _ next[data[data[pc]]+1];
TRUSTED {
IF lastCarefulNextPos = LOOPHOLE[nextPos] THEN
GOTO Failure;
};
};
carefulGreedyClosureEnd => 
IF ~DoCarefulGreedyClosureEnd[] THEN GOTO Failure;
fieldStart =>
finder.nameArray[data[pc]].at _ nextPos-1;
fieldEnd =>
finder.nameArray[data[pc]].atEnd _ 
MAX[nextPos-1, finder.nameArray[data[pc]].at];
boundNodeBreaks =>
nodeBreakBound _ data[pc];
fieldEquals => IF ~DoFieldEquals[FALSE] THEN GOTO Failure;
fieldEqualsLooks => IF ~DoFieldEqualsLooks[FALSE] THEN GOTO Failure;
fieldEqualsIC => IF ~DoFieldEquals[TRUE] THEN GOTO Failure;
fieldEqualsLooksIC => IF ~DoFieldEqualsLooks[TRUE] THEN GOTO Failure;
beginAll => {
before _ nextPos-1;
};
endAll => {
after _ MAX[nextPos-1, before];
GOTO AbsoluteSuccess;
};
ENDCASE => ERROR;
pc _ next[pc];
REPEAT
Failure => {
IF interrupt # NIL AND interrupt^ THEN GOTO AbsoluteFailure;
IF stackPos = 0 THEN GOTO AbsoluteFailure;
stackPos _ stackPos - 1;
SELECT returnCodeStack[stackPos] FROM
skipToStringRet => {
pc _ pcStack[stackPos];
nextPos _ nextPosStack[stackPos];
};
closureRet, greedyClosureRet, altRet, carefulClosureRet, carefulGreedyClosureRet => {
pc _ data[pcStack[stackPos]];
nextPos _ nextPosStack[stackPos]-1;
};
ENDCASE => ERROR;
RopeReader.SetPosition[ropeReader, rope, nextPos];
AdvanceChar[];
};
ENDLOOP;
REPEAT
AbsoluteFailure => {
found _ FALSE;
};
AbsoluteSuccess => {
found _ TRUE;
at _ finder.nameArray[0].at;
atEnd _ finder.nameArray[0].atEnd;
};
ENDLOOP;

}; 



}.
æRegExpFind2Impl.mesa
Last Edited by: Nix, December 21, 1983 12:45 pm
This is not INLINE because we're up against the compiler's code size limits.
This is not INLINE because we're up against the compiler's code size limits.
�Ê
ÿ˜Jš
œ™J™/J˜š
Ïk	˜	Jš
œ	˜	Icodešœ�œÁ
˜Ø
Kšœ
�œ˜'Kšœ	�œ˜"Kšœ	�œ˜%Kšœ�œ�œ˜Kšœ�œ	˜Kšœ�œ!˜-Kšœ	�œ˜Kšœ�œ#˜3Kšœ
�œ˜Kšœ�œ˜*K˜—KšÏbœ�œ
�˜Kš�œL˜SKš�œ ˜'Kš�œ˜K˜Jšœ�œ�œ˜Jšœ�œ
�œ˜&Kš�œ�œ�œ
˜Kšœ�œ˜Kšœ
�œ˜)K˜šÏn
œ�œ
�œ�œ)�œ
�œ�œ	�œ'˜¡
Jšœ9�œ�œ˜[Jš
œ˜J˜J˜—šŸœ�œ
�œM�œ
�œ
�œ�œ	�œ'˜³
š
œ$˜$Kš
œb˜b—Jš
œ˜—K˜šŸœ�œ
�œ�œ@�œ
�œ
�œ�œ�œ	�œ'˜Ñ
š�œ�œ
�œ
Ïc"˜?J˜eJš
�œ�œ�œ
�œ
�œ
�œ 	˜BJš�œ�œ
�œ 	˜1Jšœ ˜Jš�œ
˜—š
œ#˜#Jš
œA˜A—Jš
œ˜—J˜šŸœ�œ
�œ�œ�œ�œ˜Iš�œ�˜
Jšœ;�œ
�œ�œ˜O—š�œ�˜Jšœ<�œ
�œ�œ˜P—Jš�œ�œ˜J˜J˜—šŸ	œ�œ�œ@�œ
�œ
�œ�œ	�œ'˜Ç
Kšœ�œ	˜Kš
œ˜Kšœ
�œ
˜Kšœ�œ˜4K˜K˜K˜ K˜Kš
œ)˜)Kšœ�œ4˜?Kšœ�œ1˜;Kšœ�œ/˜8Kšœ�œ/˜8Kšœ	�œ%˜1Kšœ�œ'˜8Kšœ�œ+˜?Kšœ�œ˜+K˜K˜/K˜.K˜,šŸœ�œ�œ˜š�œ�œ˜Kš
œ>˜>Kš
œ˜K˜
—š�œ˜Kš
œ˜K˜K˜K˜—K˜—šŸœ�œ�œ˜1K˜K˜!K˜'K˜K˜—šŸ	œ�œ�œ�œ˜%J˜Jš�œ�œ
�œ
�œ�œ %˜FJš
�œ	�œ
�œ�œ
�œ�œ ˜QJš
œ4˜4J˜'š�œ
˜Kšœ�œ�œ�œ4˜`—Jš
œ˜—šŸœ�œ˜š�œ
�œ
˜Kš
œ0˜0—Kš
œ˜K˜—š
Ÿ
œ�œ�œ�œ�œ˜9Kš
œL™LK˜,š�œ(�˜/Kšœ�œ˜š�œ�œ˜Kš�œ+�œ
�œ�œ˜AK˜
—š
�˜Kš�œ�œ
�œ�œ˜'—K˜K˜Kš�œ
˜—Kš�œ
�œ˜
K˜—š
Ÿœ�œ�œ�œ�œ˜>Kš
œL™LK˜,Jš�œ�œ
�œ
�œ�œ %˜Fš�œ(�˜/Kšœ�œ˜J˜'š�œ�œ˜Kš�œ+�œ
�œ�œ˜AK˜
—š
�˜Kš�œ�œ
�œ�œ˜'—Jš�œ	�œ
�œ�œ
�œ�œ˜3Jš
œ.˜.J˜(Jš
œ4˜4J˜'Jš�œ�œ�œ�œ3�œ
�œ
�œ˜xK˜K˜Kš�œ
˜—Kš�œ
�œ˜
K˜—šŸœ�œ�œ�œ˜5Kš
œ&˜&Kš
œ4˜4Kš
œ5˜5š�œ˜	Kš�œ�œ˜/K˜—K˜—K˜š
�˜š
�˜š�œ�˜š
œ
˜
š�œ�˜K˜
—š
�˜Kš�œ	˜
——š
œ˜š�œ�œ�˜0K˜
—š
�˜Kš�œ	˜
——š
œ˜š�œ�œ
�˜.K˜
—š
�˜Kš�œ	˜
——š
œ˜š�œ�œ�œ
�˜@K˜
—š
�˜Kš�œ	˜
——š
œ˜š�œ"�˜(K˜
—š
�˜Kš�œ	˜
——š
œ˜š�œ"�œ
�˜8K˜
—š
�˜Kš�œ	˜
——˜š�œ�˜!K˜
—š
�˜Kš�œ	˜
——˜š�œ�œ
�˜1K˜
—š
�˜Kš�œ	˜
——˜Kš�œ�œ�œ
�œ	˜N—š
œ˜Kš�œ�œ
�œ	˜+Kš
œ˜K˜2K˜K˜—š
œ˜Kš�œ�œ
�œ	˜+š�œ�˜"Kš�œ�œ
�œ	˜"Kš
œ˜Kš�œ
˜—K˜—˜Kš�œ
�œ
�œ	˜!—˜Kš�œ	˜
—š
œ˜Kš�œ˜—˜Kš�œ
˜—š
œ˜K˜%š�œ�˜K˜Kš�œ
˜—Kš�œ�œ
�œ	˜/K˜—š
œ˜K˜%š�œ�œ
�˜)K˜Kš�œ
˜—Kš�œ�œ
�œ	˜/Kš
œ˜—š
œ˜Kšœ�œ�œ˜š�œ�˜K˜Kš�œ
˜—Kš�œ�œ
�œ	˜/K˜—š
œ˜Kšœ�œ�œ˜š�œ�œ
�˜(K˜Kš�œ
˜—Kš�œ�œ
�œ	˜/K˜—š
œ˜Kšœ�œ�œ˜š�œ�˜%K˜Kš�œ
˜—Kš�œ�œ
�œ	˜/K˜—š
œ˜Kšœ�œ�œ˜š�œ�œ
�˜5K˜Kš�œ
˜—Kš�œ�œ
�œ	˜/K˜—š
œ˜Kšœ�œ�œ˜š�œ�˜Kš�œ�œ
�œ	˜/K˜Kš�œ
˜—K˜—š
œ˜Kšœ�œ�œ˜š�œ�œ
�˜(Kš�œ�œ
�œ	˜/K˜Kš�œ
˜—K˜—š
œ˜Kšœ�œ�œ˜š�œ�˜%Kš�œ�œ
�œ	˜/K˜Kš�œ
˜—K˜—š
œ˜Kšœ�œ�œ˜š�œ�œ
�˜5Kš�œ�œ
�œ	˜/K˜Kš�œ
˜—K˜—˜K˜K˜—˜K˜Kš
œ#˜#K˜2K˜K˜—˜K˜K˜K˜—˜K˜K˜K˜—š
œ˜K˜—š
œ˜K˜K˜+K˜,K˜—š
œ)˜)K˜K˜+K˜,K˜—š
œ˜Kš
œ&˜&Kš
œ4˜4Kš
œ5˜5š�œ˜	š�œ�œ
�˜.Kš�œ	˜
—K˜—K˜—š
œ˜Kš�œ�œ
�œ	˜2—š
œ
˜
K˜*—š
œ˜š
œ#˜#Kš�œ+˜.——š
œ˜K˜—Kš	œ�œ�œ�œ
�œ	˜:Kš	œ�œ�œ�œ
�œ	˜DKš	œ�œ�œ�œ
�œ	˜;Kš	œ�œ�œ�œ
�œ	˜Eš
œ
˜
K˜K˜—š
œ˜Kšœ�œ˜Kš�œ˜K˜—Kš�œ�œ
˜—K˜š
�˜˜Kš
�œ
�œ
�œ�œ
�œ˜<Kš�œ�œ
�œ˜*K˜š�œ�˜%˜Kš
œ˜Kš
œ!˜!K˜—š
œU˜UKš
œ˜Kš
œ#˜#K˜—Kš�œ�œ
˜—K˜2K˜K˜——Kš�œ
˜—š
�˜š
œ˜Kšœ�œ
˜K˜—š
œ˜Kšœ�œ
˜
Kš
œ˜Kš
œ"˜"K˜——Kš�œ
˜—J˜Jš
œ˜—J˜K˜K˜K˜—…—+˜:}