home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 277.lha / PatternLibrary / Pattern / match.d < prev    next >
Encoding:
Text File  |  1989-08-08  |  5.5 KB  |  209 lines
  1. #patternInternal.g
  2.  
  3. /*
  4.  * addState - add the given state to the set of active states.
  5.  */
  6.  
  7. proc addState(register *PatternState_t ps; register ulong state)void:
  8.     register *ulong pState;
  9.     register ulong i, count;
  10.  
  11.     if state = 0 then
  12.  
  13.     /* state 0 is the special end-of-pattern state. If we see it, then
  14.        we mark the match as being successful, and if we have run out
  15.        of subject string, all has gone well */
  16.  
  17.     ps*.ps_matched := true;
  18.     else
  19.  
  20.     /* check for duplicates of this state in the set of active states */
  21.  
  22.     pState := &ps*.ps_activeStates*[0];
  23.     count := ps*.ps_stateCount;
  24.     i := 0;
  25.     while i ~= count and pState* ~= state do
  26.         pState := pState + sizeof(ulong);
  27.         i := i + 1;
  28.     od;
  29.     if i = count then
  30.  
  31.         /* this state not already in the set - add it */
  32.  
  33.         pState := pState + sizeof(ulong);
  34.         pState* := state;
  35.         i := i + 1;
  36.         ps*.ps_stateCount := i;
  37.     fi;
  38.     fi;
  39. corp;
  40.  
  41. /*
  42.  * Match - match the compiled pattern against a subject string. Return 'true'
  43.  *    if the subject matches the pattern.
  44.  */
  45.  
  46. proc Match(/* register *PatternState_t ps;
  47.           register *char subject; ulong subjectLength */)bool:
  48.     uint
  49.     R_A0 = 0,
  50.     R_A1 = 1,
  51.     R_D0 = 0,
  52.     R_FP = 6,
  53.     OP_MOVEL = 0x2000,
  54.     M_DDIR = 0,
  55.     M_ADIR = 1,
  56.     M_DISP = 5;
  57.     register *PatternState_t ps;
  58.     register *[2]ulong comp;
  59.     register *char subject;
  60.     *PatternState_t patternState;
  61.     *char subjectPointer, subjectEnd;
  62.     register ulong stateNum, state, compValue, temp;
  63.     ulong subjectLength, stateCount;
  64.     register char patternChar @ temp, subjectChar @ compValue;
  65.  
  66.     /* Inline code to access the parameters passed in registers. See the
  67.        comment in 'compile.d'. */
  68.  
  69.     code(
  70.     OP_MOVEL | R_FP << 9 | M_DISP << 6 | M_ADIR << 3 | R_A0,
  71.     patternState,
  72.     OP_MOVEL | R_FP << 9 | M_DISP << 6 | M_ADIR << 3 | R_A1,
  73.     subjectPointer,
  74.     OP_MOVEL | R_FP << 9 | M_DISP << 6 | M_DDIR << 3 | R_D0,
  75.     subjectLength
  76.     );
  77.     ps := patternState;
  78.     comp := ps*.ps_compiled;
  79.     subject := subjectPointer;
  80.     ps*.ps_stateCount := 0;    /* no active states yet */
  81.     subjectEnd := subject + subjectLength * sizeof(char);
  82.     ps*.ps_matched := false;
  83.  
  84.     /* for the first subject character, the only active state is that
  85.        associated with the first pattern character */
  86.  
  87.     addState(ps, 1);
  88.  
  89.     /* if the pattern has top-level alternation, add the head of that
  90.        alternation list to the set of active states */
  91.  
  92.     if comp*[0] ~= 0 then
  93.     addState(ps, comp*[0]);
  94.     fi;
  95.  
  96.     /* loop until we have matched the entire subject string, or we have no
  97.        active states */
  98.  
  99.     while
  100.  
  101.     /* each time around, we must first add in all of those states that
  102.        are the successors to the set of states we have now. In the
  103.        following loop, note that the value of ps*.ps_stateCount can
  104.        change inside the loop, so a Draco 'for' will not work. */
  105.  
  106.     stateNum := 1;
  107.     while stateNum <= ps*.ps_stateCount do
  108.         state := ps*.ps_activeStates*[stateNum];
  109.         compValue := comp*[state];
  110.         case ps*.ps_pattern*[state - 1]
  111.         incase '\#':
  112.  
  113.         /* since '#' allows 0 or more, both the '#'ed item and
  114.            the thing after it are OK now */
  115.  
  116.         addState(ps, state + 1);
  117.         addState(ps, compValue);
  118.         incase '%':
  119.  
  120.         /* if a match-nothing is OK now, then so is whatever comes
  121.            after it in the pattern */
  122.  
  123.         addState(ps, compValue);
  124.         incase '(':
  125.         incase '|':
  126.  
  127.         /* part of an alternative chain - this alternative is OK */
  128.  
  129.         addState(ps, state + 1);
  130.         if compValue ~= 0 then
  131.  
  132.             /* this is chaining down a list of alternatives */
  133.  
  134.             addState(ps, compValue);
  135.         fi;
  136.         esac;
  137.         stateNum := stateNum + 1;
  138.     od;
  139.  
  140.     subject < subjectEnd and ps*.ps_stateCount ~= 0
  141.     do
  142.  
  143.     subjectChar := subject*;
  144.     subject := subject + sizeof(char);
  145.     if ps*.ps_ignoreCase and subjectChar >= 'a' and subjectChar <= 'z' then
  146.         subjectChar := subjectChar - 32;
  147.     fi;
  148.  
  149.     /* go through the built-up set of active states, and see which ones
  150.        are successful, i.e. describe the current subject character. For
  151.        those that do, add the resulting state to the set of active states.
  152.        Note: we are re-using the active state vector when we do this. The
  153.        new set will be no larger than the old in this phase - it is in
  154.        the previous expansion phase, for the next time around, that it
  155.        might grow. */
  156.  
  157.     temp := ps*.ps_stateCount;
  158.     ps*.ps_stateCount := 0;
  159.     ps*.ps_matched := false;
  160.     for stateNum from 1 upto temp do
  161.         state := ps*.ps_activeStates*[stateNum];
  162.         patternChar := ps*.ps_pattern*[state - 1];
  163.         case patternChar
  164.         incase '\#':
  165.         incase '|':
  166.         incase '%':
  167.         incase '(':
  168.         /* just ignore these characters - their effect is handled
  169.            by the compiled vector */
  170.         ;
  171.         incase '?':
  172.         /* match any character, so just unconditionally add the
  173.            successor state */
  174.         addState(ps, comp*[state]);
  175.         incase '\'':
  176.         /* quote - get the quoted character, then handle it just
  177.            like we do for normal characters */
  178.         patternChar := ps*.ps_pattern*[state];
  179.         if ps*.ps_ignoreCase and
  180.             patternChar >= 'a' and patternChar <= 'z'
  181.         then
  182.             patternChar := patternChar - 32;
  183.         fi;
  184.         if subjectChar = patternChar then
  185.             addState(ps, comp*[state]);
  186.         fi;
  187.         default:
  188.         /* a normal character - if it is the same as the subject
  189.            character, then add the successor state, otherwise this
  190.            state is failing and we do nothing for it */
  191.         if ps*.ps_ignoreCase and
  192.             patternChar >= 'a' and patternChar <= 'z'
  193.         then
  194.             patternChar := patternChar - 32;
  195.         fi;
  196.         if subjectChar = patternChar then
  197.             addState(ps, comp*[state]);
  198.         fi;
  199.         esac;
  200.     od;
  201.     od;
  202.  
  203.     if subject = subjectEnd then
  204.     ps*.ps_matched
  205.     else
  206.     false
  207.     fi
  208. corp;
  209.