From:	MERC::"uunet!WKUVX1.BITNET!FILESERV-Mgr" 12-JUN-1992 15:52:38.37
To:	galaxy::gleeve
CC:	
Subj:	GREP.09_OF_12

-+-+-+-+-+-+-+-+ START OF PART 9 -+-+-+-+-+-+-+-+
X`09      else
X`09`09`7B
X`09`09  PATUNFETCH;
X`09`09  break;
X`09`09`7D
X`09    `7D
X
X`09  /* Star, etc. applied to an empty pattern is equivalent
X`09     to an empty pattern.  */
X`09  if (!laststart)
X`09    break;
X
X`09  /* Now we know whether 0 matches is allowed,
X`09     and whether 2 or more matches is allowed.  */
X`09  if (many_times_ok)
X`09    `7B
X`09      /* If more than one repetition is allowed,
X`09`09 put in a backward jump at the end.  */
X`09      store_jump (b, maybe_finalize_jump, laststart - 3);
X`09      b += 3;
X`09    `7D
X`09  insert_jump (on_failure_jump, laststart, b + 3, b);
X`09  pending_exact = 0;
X`09  b += 3;
X`09  if (!zero_times_ok)
X`09    `7B
X`09      /* At least one repetition required: insert before the loop
X`09`09 a skip over the initial on-failure-jump instruction */
X`09      insert_jump (dummy_failure_jump, laststart, laststart + 6, b);
X`09      b += 3;
X`09    `7D
X`09  break;
X
X`09case '.':
X`09  laststart = b;
X`09  PATPUSH (anychar);
X`09  break;
X
X`09case '`5B':
X`09  while (b - bufp->buffer
X`09`09 > bufp->allocated - 3 - (1 << BYTEWIDTH) / BYTEWIDTH)
X`09    /* Note that EXTEND_BUFFER clobbers c */
X`09    EXTEND_BUFFER;
X
X`09  laststart = b;
X`09  if (*p == '`5E')
X`09    PATPUSH (charset_not), p++;
X`09  else
X`09    PATPUSH (charset);
X`09  p1 = p;
X
X`09  PATPUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
X`09  /* Clear the whole map */
X`09  bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
X`09  /* Read in characters and ranges, setting map bits */
X`09  while (1)
X`09    `7B
X`09      PATFETCH (c);
X`09      if (c == '`5D' && p != p1 + 1) break;
X`09      if (*p == '-' && p`5B1`5D != '`5D')
X`09`09`7B
X`09`09  PATFETCH (c1);
X`09`09  PATFETCH (c1);
X`09`09  while (c <= c1)
X`09`09    b`5Bc / BYTEWIDTH`5D `7C= 1 << (c % BYTEWIDTH), c++;
X`09`09`7D
X`09      else
X`09`09`7B
X`09`09  b`5Bc / BYTEWIDTH`5D `7C= 1 << (c % BYTEWIDTH);
X`09`09`7D
X`09    `7D
X`09  /* Discard any bitmap bytes that are all 0 at the end of the map.
X`09     Decrement the map-length byte too. */
X`09  while ((int) b`5B-1`5D > 0 && b`5Bb`5B-1`5D - 1`5D == 0)
X`09    b`5B-1`5D--;
X`09  b += b`5B-1`5D;
X`09  break;
X
X`09case '(':
X`09  if (! (obscure_syntax & RE_NO_BK_PARENS))
X`09    goto normal_char;
X`09  else
X`09    goto handle_open;
X
X`09case ')':
X`09  if (! (obscure_syntax & RE_NO_BK_PARENS))
X`09    goto normal_char;
X`09  else
X`09    goto handle_close;
X
X`09case '\n':
X`09  if (! (obscure_syntax & RE_NEWLINE_OR))
X`09    goto normal_char;
X`09  else
X`09    goto handle_bar;
X
X`09case '`7C':
X`09  if (! (obscure_syntax & RE_NO_BK_VBAR))
X`09    goto normal_char;
X`09  else
X`09    goto handle_bar;
X
X        case '\\':
X`09  if (p == pend) goto invalid_pattern;
X`09  PATFETCH_RAW (c);
X`09  switch (c)
X`09    `7B
X`09    case '(':
X`09      if (obscure_syntax & RE_NO_BK_PARENS)
X`09`09goto normal_backsl;
X`09    handle_open:
X`09      if (stackp == stacke) goto nesting_too_deep;
X`09      if (regnum < RE_NREGS)
X`09        `7B
X`09`09  PATPUSH (start_memory);
X`09`09  PATPUSH (regnum);
X`09        `7D
X`09      *stackp++ = b - bufp->buffer;
X`09      *stackp++ = fixup_jump ? fixup_jump - bufp->buffer + 1 : 0;
X`09      *stackp++ = regnum++;
X`09      *stackp++ = begalt - bufp->buffer;
X`09      fixup_jump = 0;
X`09      laststart = 0;
X`09      begalt = b;
X`09      break;
X
X`09    case ')':
X`09      if (obscure_syntax & RE_NO_BK_PARENS)
X`09`09goto normal_backsl;
X`09    handle_close:
X`09      if (stackp == stackb) goto unmatched_close;
X`09      begalt = *--stackp + bufp->buffer;
X`09      if (fixup_jump)
X`09`09store_jump (fixup_jump, jump, b);
X`09      if (stackp`5B-1`5D < RE_NREGS)
X`09`09`7B
X`09`09  PATPUSH (stop_memory);
X`09`09  PATPUSH (stackp`5B-1`5D);
X`09`09`7D
X`09      stackp -= 2;
X`09      fixup_jump = 0;
X`09      if (*stackp)
X`09`09fixup_jump = *stackp + bufp->buffer - 1;
X`09      laststart = *--stackp + bufp->buffer;
X`09      break;
X
X`09    case '`7C':
X`09      if (obscure_syntax & RE_NO_BK_VBAR)
X`09`09goto normal_backsl;
X`09    handle_bar:
X`09      insert_jump (on_failure_jump, begalt, b + 6, b);
X`09      pending_exact = 0;
X`09      b += 3;
X`09      if (fixup_jump)
X`09`09store_jump (fixup_jump, jump, b);
X`09      fixup_jump = b;
X`09      b += 3;
X`09      laststart = 0;
X`09      begalt = b;
X`09      break;
X
X#ifdef emacs
X`09    case '=':
X`09      PATPUSH (at_dot);
X`09      break;
X
X`09    case 's':`09
X`09      laststart = b;
X`09      PATPUSH (syntaxspec);
X`09      PATFETCH (c);
X`09      PATPUSH (syntax_spec_code`5Bc`5D);
X`09      break;
X
X`09    case 'S':
X`09      laststart = b;
X`09      PATPUSH (notsyntaxspec);
X`09      PATFETCH (c);
X`09      PATPUSH (syntax_spec_code`5Bc`5D);
X`09      break;
X#endif /* emacs */
X
X`09    case 'w':
X`09      laststart = b;
X`09      PATPUSH (wordchar);
X`09      break;
X
X`09    case 'W':
X`09      laststart = b;
X`09      PATPUSH (notwordchar);
X`09      break;
X
X`09    case '<':
X`09      PATPUSH (wordbeg);
X`09      break;
X
X`09    case '>':
X`09      PATPUSH (wordend);
X`09      break;
X
X`09    case 'b':
X`09      PATPUSH (wordbound);
X`09      break;
X
X`09    case 'B':
X`09      PATPUSH (notwordbound);
X`09      break;
X
X`09    case '`60':
X`09      PATPUSH (begbuf);
X`09      break;
X
X`09    case '\'':
X`09      PATPUSH (endbuf);
X`09      break;
X
X`09    case '1':
X`09    case '2':
X`09    case '3':
X`09    case '4':
X`09    case '5':
X`09    case '6':
X`09    case '7':
X`09    case '8':
X`09    case '9':
X`09      c1 = c - '0';
X`09      if (c1 >= regnum)
X`09`09goto normal_char;
X`09      for (stackt = stackp - 2;  stackt > stackb;  stackt -= 4)
X `09`09if (*stackt == c1)
X`09`09  goto normal_char;
X`09      laststart = b;
X`09      PATPUSH (duplicate);
X`09      PATPUSH (c1);
X`09      break;
X
X`09    case '+':
X`09    case '?':
X`09      if (obscure_syntax & RE_BK_PLUS_QM)
X`09`09goto handle_plus;
X
X`09    default:
X`09    normal_backsl:
X`09      /* You might think it would be useful for \ to mean
X`09`09 not to translate; but if we don't translate it
X`09`09 it will never match anything.  */
X`09      if (translate) c = translate`5Bc`5D;
X`09      goto normal_char;
X`09    `7D
X`09  break;
X
X`09default:
X`09normal_char:
X`09  if (!pending_exact `7C`7C pending_exact + *pending_exact + 1 != b
X`09      `7C`7C *pending_exact == 0177 `7C`7C *p == '*' `7C`7C *p == '`5E'
X`09      `7C`7C ((obscure_syntax & RE_BK_PLUS_QM)
X`09`09  ? *p == '\\' && (p`5B1`5D == '+' `7C`7C p`5B1`5D == '?')
X`09`09  : (*p == '+' `7C`7C *p == '?')))
X`09    `7B
X`09      laststart = b;
X`09      PATPUSH (exactn);
X`09      pending_exact = b;
X`09      PATPUSH (0);
X`09    `7D
X`09  PATPUSH (c);
X`09  (*pending_exact)++;
X`09`7D
X    `7D
X
X  if (fixup_jump)
X    store_jump (fixup_jump, jump, b);
X
X  if (stackp != stackb) goto unmatched_open;
X
X  bufp->used = b - bufp->buffer;
X  return 0;
X
X invalid_pattern:
X  return "Invalid regular expression";
X
X unmatched_open:
X  return "Unmatched \\(";
X
X unmatched_close:
X  return "Unmatched \\)";
X
X end_of_pattern:
X  return "Premature end of regular expression";
X
X nesting_too_deep:
X  return "Nesting too deep";
X
X too_big:
X  return "Regular expression too big";
X
X memory_exhausted:
X  return "Memory exhausted";
X`7D
X
X/* Store where `60from' points a jump operation to jump to where `60to' poin
Vts.
X  `60opcode' is the opcode to store. */
X
Xstatic void
Xstore_jump (from, opcode, to)
X     char *from, *to;
X     char opcode;
X`7B
X  from`5B0`5D = opcode;
X  from`5B1`5D = (to - (from + 3)) & 0377;
X  from`5B2`5D = (to - (from + 3)) >> 8;
X`7D
X
X/* Open up space at char FROM, and insert there a jump to TO.
X   CURRENT_END gives te end of the storage no in use,
X   so we know how much data to copy up.
X   OP is the opcode of the jump to insert.
X
X   If you call this function, you must zero out pending_exact.  */
X
Xstatic void
Xinsert_jump (op, from, to, current_end)
X     char op;
X     char *from, *to, *current_end;
X`7B
X  register char *pto = current_end + 3;
X  register char *pfrom = current_end;
X  while (pfrom != from)
X    *--pto = *--pfrom;
X  store_jump (from, op, to);
X`7D
X`0C
X/* Given a pattern, compute a fastmap from it.
X The fastmap records which of the (1 << BYTEWIDTH) possible characters
X can start a string that matches the pattern.
X This fastmap is used by re_search to skip quickly over totally implausible
V text.
X
X The caller must supply the address of a (1 << BYTEWIDTH)-byte data area
X as bufp->fastmap.
X The other components of bufp describe the pattern to be used.  */
X
Xvoid
Xre_compile_fastmap (bufp)
X     struct re_pattern_buffer *bufp;
X`7B
X  unsigned char *pattern = (unsigned char *) bufp->buffer;
X  int size = bufp->used;
X  register char *fastmap = bufp->fastmap;
X  register unsigned char *p = pattern;
X  register unsigned char *pend = pattern + size;
X  register int j, k;
X  unsigned char *translate = (unsigned char *) bufp->translate;
X
X  unsigned char *stackb`5BNFAILURES`5D;
X  unsigned char **stackp = stackb;
X
X  bzero (fastmap, (1 << BYTEWIDTH));
X  bufp->fastmap_accurate = 1;
X  bufp->can_be_null = 0;
X     `20
X  while (p)
X    `7B
X      if (p == pend)
X`09`7B
X`09  bufp->can_be_null = 1;
X`09  break;
X`09`7D
X#ifdef SWITCH_ENUM_BUG
X      switch ((int) ((enum regexpcode) *p++))
X#else
X      switch ((enum regexpcode) *p++)
X#endif
X`09`7B
X`09case exactn:
X`09  if (translate)
X`09    fastmap`5Btranslate`5Bp`5B1`5D`5D`5D = 1;
X`09  else
X`09    fastmap`5Bp`5B1`5D`5D = 1;
X`09  break;
X
X        case begline:
X        case before_dot:
X`09case at_dot:
X`09case after_dot:
X`09case begbuf:
X`09case endbuf:
X`09case wordbound:
X`09case notwordbound:
X`09case wordbeg:
X`09case wordend:
X`09  continue;
X
X`09case endline:
X`09  if (translate)
X`09    fastmap`5Btranslate`5B'\n'`5D`5D = 1;
X`09  else
X`09    fastmap`5B'\n'`5D = 1;
X`09  if (bufp->can_be_null != 1)
X`09    bufp->can_be_null = 2;
X`09  break;
X
X`09case finalize_jump:
X`09case maybe_finalize_jump:
X`09case jump:
X`09case dummy_failure_jump:
X`09  bufp->can_be_null = 1;
X`09  j = *p++ & 0377;
X`09  j += SIGN_EXTEND_CHAR (*(char *)p) << 8;
X`09  p += j + 1;`09`09/* The 1 compensates for missing ++ above */
X`09  if (j > 0)
X`09    continue;
X`09  /* Jump backward reached implies we just went through
X`09     the body of a loop and matched nothing.
X`09     Opcode jumped to should be an on_failure_jump.
X`09     Just treat it like an ordinary jump.
X`09     For a * loop, it has pushed its failure point already;
X`09     if so, discard that as redundant.  */
X`09  if ((enum regexpcode) *p != on_failure_jump)
X`09    continue;
X`09  p++;
X`09  j = *p++ & 0377;
X`09  j += SIGN_EXTEND_CHAR (*(char *)p) << 8;
X`09  p += j + 1;`09`09/* The 1 compensates for missing ++ above */
X`09  if (stackp != stackb && *stackp == p)
X`09    stackp--;
X`09  continue;
X`09 `20
X`09case on_failure_jump:
X`09  j = *p++ & 0377;
X`09  j += SIGN_EXTEND_CHAR (*(char *)p) << 8;
X`09  p++;
X`09  *++stackp = p + j;
X`09  continue;
X
X`09case start_memory:
X`09case stop_memory:
X`09  p++;
X`09  continue;
X
X`09case duplicate:
X`09  bufp->can_be_null = 1;
X`09  fastmap`5B'\n'`5D = 1;
X`09case anychar:
X`09  for (j = 0; j < (1 << BYTEWIDTH); j++)
X`09    if (j != '\n')
X`09      fastmap`5Bj`5D = 1;
X`09  if (bufp->can_be_null)
X`09    return;
X`09  /* Don't return; check the alternative paths
X`09     so we can set can_be_null if appropriate.  */
X`09  break;
X
X`09case wordchar:
X`09  for (j = 0; j < (1 << BYTEWIDTH); j++)
X`09    if (SYNTAX (j) == Sword)
X`09      fastmap`5Bj`5D = 1;
X`09  break;
X
X`09case notwordchar:
X`09  for (j = 0; j < (1 << BYTEWIDTH); j++)
X`09    if (SYNTAX (j) != Sword)
X`09      fastmap`5Bj`5D = 1;
X`09  break;
X
X#ifdef emacs
X`09case syntaxspec:
X`09  k = *p++;
X`09  for (j = 0; j < (1 << BYTEWIDTH); j++)
X`09    if (SYNTAX (j) == (enum syntaxcode) k)
X`09      fastmap`5Bj`5D = 1;
X`09  break;
X
X`09case notsyntaxspec:
X`09  k = *p++;
X`09  for (j = 0; j < (1 << BYTEWIDTH); j++)
X`09    if (SYNTAX (j) != (enum syntaxcode) k)
X`09      fastmap`5Bj`5D = 1;
X`09  break;
X#endif /* emacs */
X
X`09case charset:
X`09  for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
X`09    if (p`5Bj / BYTEWIDTH`5D & (1 << (j % BYTEWIDTH)))
X`09      `7B
X`09`09if (translate)
X`09`09  fastmap`5Btranslate`5Bj`5D`5D = 1;
X`09`09else
X`09`09  fastmap`5Bj`5D = 1;
X`09      `7D
X`09  break;
X
X`09case charset_not:
X`09  /* Chars beyond end of map must be allowed */
X`09  for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
X`09    if (translate)
X`09      fastmap`5Btranslate`5Bj`5D`5D = 1;
X`09    else
X`09      fastmap`5Bj`5D = 1;
X
X`09  for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
X`09    if (!(p`5Bj / BYTEWIDTH`5D & (1 << (j % BYTEWIDTH))))
X`09      `7B
X`09`09if (translate)
X`09`09  fastmap`5Btranslate`5Bj`5D`5D = 1;
X`09`09else
X`09`09  fastmap`5Bj`5D = 1;
X`09      `7D
X`09  break;
X
X`09default:
X`09  break;
X`09`7D
X
X      /* Get here means we have successfully found the possible starting cha
Vracters
X`09 of one path of the pattern.  We need not follow this path any farther.
X`09 Instead, look at the next alternative remembered in the stack. */
X      if (stackp != stackb)
X`09p = *stackp--;
X      else
X`09break;
X    `7D
X`7D
X`0C
X/* Like re_search_2, below, but only one string is specified. */
X
Xint
Xre_search (pbufp, string, size, startpos, range, regs)
X     struct re_pattern_buffer *pbufp;
X     char *string;
X     int size, startpos, range;
X     struct re_registers *regs;
X`7B
X  return re_search_2 (pbufp, 0, 0, string, size, startpos, range, regs, size
V);
X`7D
X
X/* Like re_match_2 but tries first a match starting at index STARTPOS,
X   then at STARTPOS + 1, and so on.
X   RANGE is the number of places to try before giving up.
X   If RANGE is negative, the starting positions tried are
X    STARTPOS, STARTPOS - 1, etc.
X   It is up to the caller to make sure that range is not so large
X   as to take the starting position outside of the input strings.
X
XThe value returned is the position at which the match was found,
X or -1 if no match was found,
X or -2 if error (such as failure stack overflow).  */
X
Xint
Xre_search_2 (pbufp, string1, size1, string2, size2, startpos, range, regs, m
Vstop)
X     struct re_pattern_buffer *pbufp;
X     char *string1, *string2;
X     int size1, size2;
X     int startpos;
X     register int range;
X     struct re_registers *regs;
X     int mstop;
X`7B
X  register char *fastmap = pbufp->fastmap;
X  register unsigned char *translate = (unsigned char *) pbufp->translate;
X  int total = size1 + size2;
X  int val;
X
X  /* Update the fastmap now if not correct already */
X  if (fastmap && !pbufp->fastmap_accurate)
X    re_compile_fastmap (pbufp);
X `20
X  /* Don't waste time in a long search for a pattern
X     that says it is anchored.  */
X  if (pbufp->used > 0 && (enum regexpcode) pbufp->buffer`5B0`5D == begbuf
X      && range > 0)
X    `7B
X      if (startpos > 0)
X`09return -1;
X      else
X`09range = 1;
X    `7D
X
X  while (1)
X    `7B
X      /* If a fastmap is supplied, skip quickly over characters
X`09 that cannot possibly be the start of a match.
X`09 Note, however, that if the pattern can possibly match
X`09 the null string, we must test it at each starting point
X`09 so that we take the first null string we get.  */
X
X      if (fastmap && startpos < total && pbufp->can_be_null != 1)
X`09`7B
X`09  if (range > 0)
X`09    `7B
X`09      register int lim = 0;
X`09      register unsigned char *p;
X`09      int irange = range;
X`09      if (startpos < size1 && startpos + range >= size1)
X`09`09lim = range - (size1 - startpos);
X
X`09      p = ((unsigned char *)
X`09`09   &(startpos >= size1 ? string2 - size1 : string1)`5Bstartpos`5D);
X
X`09      if (translate)
X`09`09`7B
X`09`09  while (range > lim && !fastmap`5Btranslate`5B*p++`5D`5D)
X`09`09    range--;
X`09`09`7D
X`09      else
X`09`09`7B
X`09`09  while (range > lim && !fastmap`5B*p++`5D)
X`09`09    range--;
X`09`09`7D
X`09      startpos += irange - range;
X`09    `7D
X`09  else
X`09    `7B
X`09      register unsigned char c;
X`09      if (startpos >= size1)
X`09`09c = string2`5Bstartpos - size1`5D;
X`09      else
X`09`09c = string1`5Bstartpos`5D;
X`09      c &= 0xff;
X`09      if (translate ? !fastmap`5Btranslate`5Bc`5D`5D : !fastmap`5Bc`5D)
X`09`09goto advance;
X`09    `7D
X`09`7D
X
X      if (range >= 0 && startpos == total
X`09  && fastmap && pbufp->can_be_null == 0)
X`09return -1;
X
X      val = re_match_2 (pbufp, string1, size1, string2, size2, startpos, reg
Vs, mstop);
X      if (0 <= val)
X`09`7B
X`09  if (val == -2)
X`09    return -2;
X`09  return startpos;
X`09`7D
X
X#ifdef C_ALLOCA
X      alloca (0);
X#endif /* C_ALLOCA */
X
X    advance:
X      if (!range) break;
X      if (range > 0) range--, startpos++; else range++, startpos--;
X    `7D
X  return -1;
X`7D
X`0C
X#ifndef emacs   /* emacs never uses this */
Xint
Xre_match (pbufp, string, size, pos, regs)
X     struct re_pattern_buffer *pbufp;
X     char *string;
X     int size, pos;
X     struct re_registers *regs;
X`7B
X  return re_match_2 (pbufp, 0, 0, string, size, pos, regs, size);
X`7D
X#endif /* emacs */
X
X/* Maximum size of failure stack.  Beyond this, overflow is an error.  */
X
Xint re_max_failures = 2000;
X
Xstatic int bcmp_translate();
X/* Match the pattern described by PBUFP
X   against data which is the virtual concatenation of STRING1 and STRING2.
X   SIZE1 and SIZE2 are the sizes of the two data strings.
X   Start the match at position POS.
X   Do not consider matching past the position MSTOP.
X
X   If pbufp->fastmap is nonzero, then it had better be up to date.
X
X   The reason that the data to match are specified as two components
X   which are to be regarded as concatenated
X   is so this function can be used directly on the contents of an Emacs buff
Ver.
X
X   -1 is returned if there is no match.  -2 is returned if there is
X   an error (such as match stack overflow).  Otherwise the value is the leng
Vth
X   of the substring which was matched.  */
X
Xint
Xre_match_2 (pbufp, string1, size1, string2, size2, pos, regs, mstop)
X     struct re_pattern_buffer *pbufp;
X     unsigned char *string1, *string2;
X     int size1, size2;
X     int pos;
X     struct re_registers *regs;
X     int mstop;
X`7B
X  register unsigned char *p = (unsigned char *) pbufp->buffer;
X  register unsigned char *pend = p + pbufp->used;
X  /* End of first string */
X  unsigned char *end1;
X  /* End of second string */
X  unsigned char *end2;
X  /* Pointer just past last char to consider matching */
X  unsigned char *end_match_1, *end_match_2;
X  register unsigned char *d, *dend;
X  register int mcnt;
X  unsigned char *translate = (unsigned char *) pbufp->translate;
X
X /* Failure point stack.  Each place that can handle a failure further down
V the line
X    pushes a failure point on this stack.  It consists of two char *'s.
X    The first one pushed is where to resume scanning the pattern;
X    the second pushed is where to resume scanning the strings.
X    If the latter is zero, the failure point is a "dummy".
X    If a failure happens and the innermost failure point is dormant,
X    it discards that failure point and tries the next one. */
X
X  unsigned char *initial_stack`5B2 * NFAILURES`5D;
X  unsigned char **stackb = initial_stack;
X  unsigned char **stackp = stackb, **stacke = &stackb`5B2 * NFAILURES`5D;
X
X  /* Information on the "contents" of registers.
X     These are pointers into the input strings; they record
X     just what was matched (on this attempt) by some part of the pattern.
X     The start_memory command stores the start of a register's contents
X     and the stop_memory command stores the end.
X
X     At that point, regstart`5Bregnum`5D points to the first character in th
Ve register,
X     regend`5Bregnum`5D points to the first character beyond the end of the
V register,
X     regstart_seg1`5Bregnum`5D is true iff regstart`5Bregnum`5D points into
V string1,
X     and regend_seg1`5Bregnum`5D is true iff regend`5Bregnum`5D points into
V string1.  */
X
X  unsigned char *regstart`5BRE_NREGS`5D;
X  unsigned char *regend`5BRE_NREGS`5D;
X  unsigned char regstart_seg1`5BRE_NREGS`5D, regend_seg1`5BRE_NREGS`5D;
X
X  /* Set up pointers to ends of strings.
X     Don't allow the second string to be empty unless both are empty.  */
X  if (!size2)
X    `7B
X      string2 = string1;
X      size2 = size1;
X      string1 = 0;
X      size1 = 0;
X    `7D
X  end1 = string1 + size1;
X  end2 = string2 + size2;
X
X  /* Compute where to stop matching, within the two strings */
X  if (mstop <= size1)
X    `7B
X      end_match_1 = string1 + mstop;
X      end_match_2 = string2;
X    `7D
X  else
X    `7B
X      end_match_1 = end1;
X      end_match_2 = string2 + mstop - size1;
X    `7D
X
X  /* Initialize \) text positions to -1
X     to mark ones that no \( or \) has been seen for.  */
X
X  for (mcnt = 0; mcnt < sizeof (regend) / sizeof (*regend); mcnt++)
X    regend`5Bmcnt`5D = (unsigned char *) -1;
X
X  /* `60p' scans through the pattern as `60d' scans through the data.
X     `60dend' is the end of the input string that `60d' points within.
X     `60d' is advanced into the following input string whenever necessary,
X     but this happens before fetching;
X     therefore, at the beginning of the loop,
X     `60d' can be pointing at the end of a string,
X     but it cannot equal string2.  */
X
X  if (pos <= size1)
X    d = string1 + pos, dend = end_match_1;
X  else
X    d = string2 + pos - size1, dend = end_match_2;
X
X/* Write PREFETCH; just before fetching a character with *d.  */
X#define PREFETCH \
X while (d == dend)`09`09`09`09`09`09    \
X  `7B if (dend == end_match_2) goto fail;  /* end of string2 => failure */
V   \
X    d = string2;  /* end of string1 => advance to string2. */       \
X    dend = end_match_2; `7D
X
X  /* This loop loops over pattern commands.
X     It exits by returning from the function if match is complete,
X     or it drops through if match fails at this starting point in the input
V data. */
X
X  while (1)
X    `7B
X      if (p == pend)
X`09/* End of pattern means we have succeeded! */
X`09`7B
X`09  /* If caller wants register contents data back, convert it to indices *
V/
X`09  if (regs)
X`09    `7B
X `09      regs->start`5B0`5D = pos;
X `09      if (dend == end_match_1)
X `09`09regs->end`5B0`5D = d - string1;
X `09      else
X `09`09regs->end`5B0`5D = d - string2 + size1;
X `09      for (mcnt = 1; mcnt < RE_NREGS; mcnt++)
X`09`09`7B
X`09`09  if (regend`5Bmcnt`5D == (unsigned char *) -1)
X`09`09    `7B
X`09`09      regs->start`5Bmcnt`5D = -1;
X`09`09      regs->end`5Bmcnt`5D = -1;
X`09`09      continue;
X`09`09    `7D
X `09`09  if (regstart_seg1`5Bmcnt`5D)
X`09`09    regs->start`5Bmcnt`5D = regstart`5Bmcnt`5D - string1;
X`09`09  else
X`09`09    regs->start`5Bmcnt`5D = regstart`5Bmcnt`5D - string2 + size1;
X `09`09  if (regend_seg1`5Bmcnt`5D)
X`09`09    regs->end`5Bmcnt`5D = regend`5Bmcnt`5D - string1;
X`09`09  else
X`09`09    regs->end`5Bmcnt`5D = regend`5Bmcnt`5D - string2 + size1;
X`09`09`7D
X`09    `7D
X `09  if (dend == end_match_1)
X`09    return (d - string1 - pos);
X`09  else
X`09    return d - string2 + size1 - pos;
X`09`7D
X
X      /* Otherwise match next pattern command */
X#ifdef SWITCH_ENUM_BUG
X      switch ((int) ((enum regexpcode) *p++))
X#else
X      switch ((enum regexpcode) *p++)
X#endif
X`09`7B
X
X`09/* \( is represented by a start_memory, \) by a stop_memory.
X`09    Both of those commands contain a "register number" argument.
X`09    The text matched within the \( and \) is recorded under that number.
X`09    Then, \<digit> turns into a `60duplicate' command which
X`09    is followed by the numeric value of <digit> as the register number. *
V/
X
X`09case start_memory:
X`09  regstart`5B*p`5D = d;
X `09  regstart_seg1`5B*p++`5D = (dend == end_match_1);
X`09  break;
X
X`09case stop_memory:
X`09  regend`5B*p`5D = d;
X `09  regend_seg1`5B*p++`5D = (dend == end_match_1);
X`09  break;
X
X`09case duplicate:
X`09  `7B
X`09    int regno = *p++;   /* Get which register to match against */
X`09    register unsigned char *d2, *dend2;
X
X`09    d2 = regstart`5Bregno`5D;
X `09    dend2 = ((regstart_seg1`5Bregno`5D == regend_seg1`5Bregno`5D)
X`09`09     ? regend`5Bregno`5D : end_match_1);
X`09    while (1)
X`09      `7B
X`09`09/* Advance to next segment in register contents, if necessary */
X`09`09while (d2 == dend2)
X`09`09  `7B
X`09`09    if (dend2 == end_match_2) break;
X`09`09    if (dend2 == regend`5Bregno`5D) break;
X`09`09    d2 = string2, dend2 = regend`5Bregno`5D;  /* end of string1 => adv
Vance to string2. */
X`09`09  `7D
X`09`09/* At end of register contents => success */
X`09`09if (d2 == dend2) break;
X
X`09`09/* Advance to next segment in data being matched, if necessary */
X`09`09PREFETCH;
X
X`09`09/* mcnt gets # consecutive chars to compare */
X`09`09mcnt = dend - d;
X`09`09if (mcnt > dend2 - d2)
X`09`09  mcnt = dend2 - d2;
X`09`09/* Compare that many; failure if mismatch, else skip them. */
X`09`09if (translate ? bcmp_translate (d, d2, mcnt, translate) : bcmp (d, d2,
V mcnt))
X`09`09  goto fail;
X`09`09d += mcnt, d2 += mcnt;
X`09      `7D
X`09  `7D
X`09  break;
X
X`09case anychar:
X`09  /* fetch a data character */
X`09  PREFETCH;
X`09  /* Match anything but a newline.  */
X`09  if ((translate ? translate`5B*d++`5D : *d++) == '\n')
X`09    goto fail;
X`09  break;
X
X`09case charset:
X`09case charset_not:
X`09  `7B
X`09    /* Nonzero for charset_not */
X`09    int not = 0;
X`09    register int c;
X`09    if (*(p - 1) == (unsigned char) charset_not)
X`09      not = 1;
X
X`09    /* fetch a data character */
X`09    PREFETCH;
X
X`09    if (translate)
X`09      c = translate `5B*d`5D;
X`09    else
X`09      c = *d;
X
X`09    if (c < *p * BYTEWIDTH
X`09`09&& p`5B1 + c / BYTEWIDTH`5D & (1 << (c % BYTEWIDTH)))
X`09      not = !not;
X
X`09    p += 1 + *p;
X
X`09    if (!not) goto fail;
X`09    d++;
X`09    break;
X`09  `7D
X
X`09case begline:
X`09  if (d == string1 `7C`7C d`5B-1`5D == '\n')
X`09    break;
X`09  goto fail;
X
X`09case endline:
X`09  if (d == end2
X`09      `7C`7C (d == end1 ? (size2 == 0 `7C`7C *string2 == '\n') : *d == '\
Vn'))
X`09    break;
X`09  goto fail;
X
X`09/* "or" constructs ("`7C") are handled by starting each alternative
X`09    with an on_failure_jump that points to the start of the next alternat
Vive.
X`09    Each alternative except the last ends with a jump to the joining poin
Vt.
X`09    (Actually, each jump except for the last one really jumps
X`09     to the following jump, because tensioning the jumps is a hassle.) */
X
X`09/* The start of a stupid repeat has an on_failure_jump that points
X`09   past the end of the repeat text.
X`09   This makes a failure point so that, on failure to match a repetition,
X`09   matching restarts past as many repetitions have been found
X`09   with no way to fail and look for another one.  */
X
X`09/* A smart repeat is similar but loops back to the on_failure_jump
X`09   so that each repetition makes another failure point. */
X
X`09case on_failure_jump:
X`09  if (stackp == stacke)
X`09    `7B
X`09      unsigned char **stackx;
X`09      if (stacke - stackb > re_max_failures * 2)
X`09`09return -2;
X`09      stackx = (unsigned char **) alloca (2 * (stacke - stackb)
X`09`09`09`09`09 * sizeof (char *));
X`09      bcopy (stackb, stackx, (stacke - stackb) * sizeof (char *));
X`09      stackp = stackx + (stackp - stackb);
X`09      stacke = stackx + 2 * (stacke - stackb);
X`09      stackb = stackx;
X`09    `7D
X`09  mcnt = *p++ & 0377;
X`09  mcnt += SIGN_EXTEND_CHAR (*(char *)p) << 8;
X`09  p++;
X`09  *stackp++ = mcnt + p;
X`09  *stackp++ = d;
X`09  break;
X
X`09/* The end of a smart repeat has an maybe_finalize_jump back.
X`09   Change it either to a finalize_jump or an ordinary jump. */
X
X`09case maybe_finalize_jump:
X`09  mcnt = *p++ & 0377;
X`09  mcnt += SIGN_EXTEND_CHAR (*(char *)p) << 8;
X`09  p++;
X`09  `7B
X`09    register unsigned char *p2 = p;
X`09    /* Compare what follows with the begining of the repeat.
X`09       If we can establish that there is nothing that they would
X`09       both match, we can change to finalize_jump */
X`09    while (p2 != pend
X`09`09   && (*p2 == (unsigned char) stop_memory
X`09`09       `7C`7C *p2 == (unsigned char) start_memory))
X`09      p2++;
X`09    if (p2 == pend)
X`09      p`5B-3`5D = (unsigned char) finalize_jump;
X`09    else if (*p2 == (unsigned char) exactn
+-+-+-+-+-+-+-+-  END  OF PART 9 +-+-+-+-+-+-+-+-
