+/* If the operation is a match against one or more chars,
+ return a pointer to the next operation, else return NULL. */
+static unsigned char *
+skip_one_char (p)
+ unsigned char *p;
+{
+ switch (SWITCH_ENUM_CAST (*p++))
+ {
+ case anychar:
+ break;
+
+ case exactn:
+ p += *p + 1;
+ break;
+
+ case charset_not:
+ case charset:
+ if (CHARSET_RANGE_TABLE_EXISTS_P (p - 1))
+ {
+ int mcnt;
+ p = CHARSET_RANGE_TABLE (p - 1);
+ EXTRACT_NUMBER_AND_INCR (mcnt, p);
+ p = CHARSET_RANGE_TABLE_END (p, mcnt);
+ }
+ else
+ p += 1 + CHARSET_BITMAP_SIZE (p - 1);
+ break;
+
+ case syntaxspec:
+ case notsyntaxspec:
+#ifdef emacs
+ case categoryspec:
+ case notcategoryspec:
+#endif /* emacs */
+ p++;
+ break;
+
+ default:
+ p = NULL;
+ }
+ return p;
+}
+
+
+/* Jump over non-matching operations. */
+static unsigned char *
+skip_noops (p, pend)
+ unsigned char *p, *pend;
+{
+ int mcnt;
+ while (p < pend)
+ {
+ switch (SWITCH_ENUM_CAST ((re_opcode_t) *p))
+ {
+ case start_memory:
+ case stop_memory:
+ p += 2; break;
+ case no_op:
+ p += 1; break;
+ case jump:
+ p += 1;
+ EXTRACT_NUMBER_AND_INCR (mcnt, p);
+ p += mcnt;
+ break;
+ default:
+ return p;
+ }
+ }
+ assert (p == pend);
+ return p;
+}
+
+/* Non-zero if "p1 matches something" implies "p2 fails". */
+static int
+mutually_exclusive_p (bufp, p1, p2)
+ struct re_pattern_buffer *bufp;
+ unsigned char *p1, *p2;
+{
+ re_opcode_t op2;
+ const boolean multibyte = RE_MULTIBYTE_P (bufp);
+ unsigned char *pend = bufp->buffer + bufp->used;
+
+ assert (p1 >= bufp->buffer && p1 < pend
+ && p2 >= bufp->buffer && p2 <= pend);
+
+ /* Skip over open/close-group commands.
+ If what follows this loop is a ...+ construct,
+ look at what begins its body, since we will have to
+ match at least one of that. */
+ p2 = skip_noops (p2, pend);
+ /* The same skip can be done for p1, except that this function
+ is only used in the case where p1 is a simple match operator. */
+ /* p1 = skip_noops (p1, pend); */
+
+ assert (p1 >= bufp->buffer && p1 < pend
+ && p2 >= bufp->buffer && p2 <= pend);
+
+ op2 = p2 == pend ? succeed : *p2;
+
+ switch (SWITCH_ENUM_CAST (op2))
+ {
+ case succeed:
+ case endbuf:
+ /* If we're at the end of the pattern, we can change. */
+ if (skip_one_char (p1))
+ {
+ DEBUG_PRINT1 (" End of pattern: fast loop.\n");
+ return 1;
+ }
+ break;
+
+ case endline:
+ if (!bufp->newline_anchor)
+ break;
+ /* Fallthrough */
+ case exactn:
+ {
+ register unsigned int c
+ = (re_opcode_t) *p2 == endline ? '\n'
+ : RE_STRING_CHAR(p2 + 2, pend - p2 - 2);
+
+ if ((re_opcode_t) *p1 == exactn)
+ {
+ if (c != RE_STRING_CHAR (p1 + 2, pend - p1 - 2))
+ {
+ DEBUG_PRINT3 (" '%c' != '%c' => fast loop.\n", c, p1[2]);
+ return 1;
+ }
+ }
+
+ else if ((re_opcode_t) *p1 == charset
+ || (re_opcode_t) *p1 == charset_not)
+ {
+ int not = (re_opcode_t) *p1 == charset_not;
+
+ /* Test if C is listed in charset (or charset_not)
+ at `p1'. */
+ if (SINGLE_BYTE_CHAR_P (c))
+ {
+ if (c < CHARSET_BITMAP_SIZE (p1) * BYTEWIDTH
+ && p1[2 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
+ not = !not;
+ }
+ else if (CHARSET_RANGE_TABLE_EXISTS_P (p1))
+ CHARSET_LOOKUP_RANGE_TABLE (not, c, p1);
+
+ /* `not' is equal to 1 if c would match, which means
+ that we can't change to pop_failure_jump. */
+ if (!not)
+ {
+ DEBUG_PRINT1 (" No match => fast loop.\n");
+ return 1;
+ }
+ }
+ else if ((re_opcode_t) *p1 == anychar
+ && c == '\n')
+ {
+ DEBUG_PRINT1 (" . != \\n => fast loop.\n");
+ return 1;
+ }
+ }
+ break;
+
+ case charset:
+ case charset_not:
+ {
+ if ((re_opcode_t) *p1 == exactn)
+ /* Reuse the code above. */
+ return mutually_exclusive_p (bufp, p2, p1);
+
+
+ /* It is hard to list up all the character in charset
+ P2 if it includes multibyte character. Give up in
+ such case. */
+ else if (!multibyte || !CHARSET_RANGE_TABLE_EXISTS_P (p2))
+ {
+ /* Now, we are sure that P2 has no range table.
+ So, for the size of bitmap in P2, `p2[1]' is
+ enough. But P1 may have range table, so the
+ size of bitmap table of P1 is extracted by
+ using macro `CHARSET_BITMAP_SIZE'.
+
+ Since we know that all the character listed in
+ P2 is ASCII, it is enough to test only bitmap
+ table of P1. */
+
+ if (*p1 == *p2)
+ {
+ int idx;
+ /* We win if the charset inside the loop
+ has no overlap with the one after the loop. */
+ for (idx = 0;
+ (idx < (int) p2[1]
+ && idx < CHARSET_BITMAP_SIZE (p1));
+ idx++)
+ if ((p2[2 + idx] & p1[2 + idx]) != 0)
+ break;
+
+ if (idx == p2[1]
+ || idx == CHARSET_BITMAP_SIZE (p1))
+ {
+ DEBUG_PRINT1 (" No match => fast loop.\n");
+ return 1;
+ }
+ }
+ else if ((re_opcode_t) *p1 == charset
+ || (re_opcode_t) *p1 == charset_not)
+ {
+ int idx;
+ /* We win if the charset_not inside the loop lists
+ every character listed in the charset after. */
+ for (idx = 0; idx < (int) p2[1]; idx++)
+ if (! (p2[2 + idx] == 0
+ || (idx < CHARSET_BITMAP_SIZE (p1)
+ && ((p2[2 + idx] & ~ p1[2 + idx]) == 0))))
+ break;
+
+ if (idx == p2[1])
+ {
+ DEBUG_PRINT1 (" No match => fast loop.\n");
+ return 1;
+ }
+ }
+ }
+ }
+
+ case wordend:
+ case notsyntaxspec:
+ return ((re_opcode_t) *p1 == syntaxspec
+ && p1[1] == (op2 == wordend ? Sword : p2[1]));
+
+ case wordbeg:
+ case syntaxspec:
+ return ((re_opcode_t) *p1 == notsyntaxspec
+ && p1[1] == (op2 == wordend ? Sword : p2[1]));
+
+ case wordbound:
+ return (((re_opcode_t) *p1 == notsyntaxspec
+ || (re_opcode_t) *p1 == syntaxspec)
+ && p1[1] == Sword);
+
+#ifdef emacs
+ case categoryspec:
+ return ((re_opcode_t) *p1 == notcategoryspec && p1[1] == p2[1]);
+ case notcategoryspec:
+ return ((re_opcode_t) *p1 == categoryspec && p1[1] == p2[1]);
+#endif /* emacs */
+
+ default:
+ ;
+ }
+
+ /* Safe default. */
+ return 0;
+}
+
+\f
+/* Matching routines. */
+
+#ifndef emacs /* Emacs never uses this. */