home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / mitsch75.zip / scheme-7_5_17-src.zip / scheme-7.5.17 / src / microcode / regex.c < prev    next >
C/C++ Source or Header  |  2000-12-05  |  33KB  |  1,170 lines
  1. /* -*-C-*-
  2.  
  3. $Id: regex.c,v 1.20 2000/12/05 21:23:48 cph Exp $
  4.  
  5. Copyright (c) 1987-2000 Massachusetts Institute of Technology
  6.  
  7. This program is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 2 of the License, or (at
  10. your option) any later version.
  11.  
  12. This program is distributed in the hope that it will be useful, but
  13. WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15. General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with this program; if not, write to the Free Software
  19. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20. */
  21.  
  22. /* Regular expression matching and search. */
  23.  
  24. /* NOTE: This program was created by translation from the regular
  25. expression code of GNU Emacs; it was translated from the original C to
  26. 68000 assembly language (in 1986), and then translated back from 68000
  27. assembly language to C (in 1987).  Users should be aware that the GNU
  28. GENERAL PUBLIC LICENSE may apply to this code.  A copy of that license
  29. should have been included along with this file. */
  30.  
  31. #include "scheme.h"
  32. #include "syntax.h"
  33. #include "regex.h"
  34.  
  35. #ifdef STDC_HEADERS
  36. #  include <stdlib.h>
  37. #else
  38.    extern char * malloc ();
  39.    extern char * realloc ();
  40.    extern void free ();
  41. #endif
  42.  
  43. #if defined(__IRIX__) || defined(_AIX)
  44. #define SIGN_EXTEND_CHAR(x) ((((int) (x)) >= 0x80)            \
  45.                  ? (((int) (x)) - 0x100)            \
  46.                  : ((int) (x)))
  47. #endif
  48.  
  49. #ifndef SIGN_EXTEND_CHAR
  50. #define SIGN_EXTEND_CHAR(x) (x)
  51. #endif /* not SIGN_EXTEND_CHAR */
  52.  
  53. #ifndef SWITCH_ENUM
  54. #define SWITCH_ENUM(enum_type, expression)                \
  55.   switch ((enum enum_type) (expression))
  56. #endif /* not SWITCH_ENUM */
  57.  
  58. #ifndef RE_NFAILURES
  59. #define RE_NFAILURES 512
  60. #endif
  61.  
  62. #define FOR_INDEX_RANGE(index, start, end)                \
  63.   for (index = (start); (index < (end)); index += 1)
  64.  
  65. #define FOR_INDEX_BELOW(index, limit)                    \
  66.   FOR_INDEX_RANGE (index, 0, (limit))
  67.  
  68. #define FOR_ALL_ASCII(index)                        \
  69.   FOR_INDEX_BELOW (index, MAX_ASCII)
  70.  
  71. #define FOR_ALL_ASCII_SUCH_THAT(index, expression)            \
  72.   FOR_ALL_ASCII (index)                            \
  73.     if (expression)
  74.  
  75. #define TRANSLATE_CHAR(ascii)                        \
  76.   ((translation == NULL) ? (ascii) : (translation [(ascii)]))
  77.  
  78. #define WORD_CONSTITUENT_P(ascii)                    \
  79.   (SYNTAX_CONSTITUENT_P (syntaxcode_word, (ascii)))
  80.  
  81. #define SYNTAX_CONSTITUENT_P(code, ascii)                \
  82.   ((SYNTAX_ENTRY_CODE (SYNTAX_TABLE_REF (syntax_table, (ascii)))) == (code))
  83.  
  84. #define CHAR_SET_MEMBER_P(length, char_set, ascii)            \
  85.   (((ascii) < ((length) * ASCII_LENGTH)) &&                \
  86.    (CHAR_SET_MEMBER_P_INTERNAL (char_set, ascii)))
  87.  
  88. #define CHAR_SET_MEMBER_P_INTERNAL(char_set, ascii)            \
  89.   ((((char_set) [((ascii) / ASCII_LENGTH)]) &                \
  90.     (1 << ((ascii) % ASCII_LENGTH)))                    \
  91.    != 0)
  92.  
  93. #define READ_PATTERN_CHAR(target) do                    \
  94. {                                    \
  95.   if (pattern_pc >= pattern_end)                    \
  96.     BAD_PATTERN ();                            \
  97.   (target) = (*pattern_pc++);                        \
  98. } while (0)
  99.  
  100. #define READ_PATTERN_OFFSET(target) do                    \
  101. {                                    \
  102.   SIGNED char _fetched;                            \
  103.   if ((pattern_pc + 1) >= pattern_end)                    \
  104.     BAD_PATTERN ();                            \
  105.   (target) = (*pattern_pc++);                        \
  106.   _fetched = (* ((SIGNED char *) (pattern_pc++)));            \
  107.   (target) += ((SIGN_EXTEND_CHAR (_fetched)) << ASCII_LENGTH);        \
  108.   if (((pattern_pc + (target)) < pattern_start) ||            \
  109.       ((pattern_pc + (target)) > pattern_end))                \
  110.     BAD_PATTERN ();                            \
  111. } while (0)
  112.  
  113. #define READ_PATTERN_LENGTH(target) do                    \
  114. {                                    \
  115.   int _len;                                \
  116.                                     \
  117.   if (pattern_pc >= pattern_end)                    \
  118.     BAD_PATTERN ();                            \
  119.   _len = ((int) (*pattern_pc++));                    \
  120.   if ((pattern_pc + _len) > pattern_end)                \
  121.     BAD_PATTERN ();                            \
  122.   (target) = _len;                            \
  123. } while (0)
  124.  
  125. #define READ_PATTERN_REGISTER(target) do                \
  126. {                                    \
  127.   if ((pattern_pc >= pattern_end) ||                    \
  128.       (((target) = (*pattern_pc++)) >= RE_NREGS))            \
  129.     BAD_PATTERN ();                            \
  130. } while (0)
  131.  
  132. #define READ_PATTERN_SYNTAXCODE(target) do                \
  133. {                                    \
  134.   if ((pattern_pc >= pattern_end) ||                    \
  135.       (((int) ((target) = ((enum syntaxcode) (*pattern_pc++))))        \
  136.        >= ((int) syntaxcode_max)))                    \
  137.     BAD_PATTERN ();                            \
  138. } while (0)
  139.  
  140. #define BAD_PATTERN() RE_RETURN (-2)
  141.  
  142. #define PUSH_FAILURE_POINT(pattern_pc, match_pc) do            \
  143. {                                    \
  144.   if (stack_pointer == stack_end)                    \
  145.     {                                    \
  146.       long stack_length;                        \
  147.       unsigned char **stack_temporary;                    \
  148.                                     \
  149.       stack_length = ((stack_end - stack_start) * 2);            \
  150.       if (stack_length > (re_max_failures * 2))                \
  151.     RE_RETURN (-4);                            \
  152.       stack_temporary =                            \
  153.     ((unsigned char **)                        \
  154.      (realloc                            \
  155.       (stack_start, (stack_length * (sizeof (unsigned char *))))));    \
  156.       if (stack_temporary == NULL)                    \
  157.     RE_RETURN (-3);                            \
  158.       stack_end = (& (stack_temporary [stack_length]));            \
  159.       stack_pointer =                            \
  160.     (& (stack_temporary [(stack_pointer - stack_start)]));        \
  161.       stack_start = stack_temporary;                    \
  162.     }                                    \
  163.   (*stack_pointer++) = (pattern_pc);                    \
  164.   (*stack_pointer++) = (match_pc);                    \
  165. } while (0)
  166.  
  167. #define RE_RETURN(value)                        \
  168. {                                    \
  169.   return_value = (value);                        \
  170.   goto return_point;                            \
  171. }
  172.  
  173. void
  174. DEFUN (re_buffer_initialize,
  175.        (buffer, translation, syntax_table, text,
  176.     text_start_index, text_end_index,
  177.     gap_start_index, gap_end_index),
  178.        struct re_buffer * buffer
  179.        AND unsigned char * translation
  180.        AND SYNTAX_TABLE_TYPE syntax_table
  181.        AND unsigned char * text
  182.        AND unsigned long text_start_index
  183.        AND unsigned long text_end_index
  184.        AND unsigned long gap_start_index
  185.        AND unsigned long gap_end_index)
  186. {
  187.   unsigned char *text_start, *text_end, *gap_start, *gap_end;
  188.  
  189.   /* Assumes that
  190.      ((text_start_index <= gap_start_index) &&
  191.       (gap_start_index <= gap_end_index) &&
  192.       (gap_end_index <= text_end_index)) */
  193.  
  194.   text_start = (text + text_start_index);
  195.   text_end = (text + text_end_index);
  196.   gap_start = (text + gap_start_index);
  197.   gap_end = (text + gap_end_index);
  198.  
  199.   (buffer -> translation) = translation;
  200.   (buffer -> syntax_table) = syntax_table;
  201.   (buffer -> text) = text;
  202.   (buffer -> text_start) = ((text_start == gap_start) ? gap_end : text_start);
  203.   (buffer -> text_end) = ((text_end == gap_end) ? gap_start : text_end);
  204.   (buffer -> gap_start) = gap_start;
  205.   (buffer -> gap_end) = gap_end;
  206.   return;
  207. }
  208.  
  209. /* Given a compiled pattern between `pattern_start' and `pattern_end',
  210.    generate a character set which is true of all characters which can
  211.    be the first character of a match.
  212.  
  213.    See the documentation of `struct re_buffer' for a description of
  214.    `translation' and `syntax_table'.
  215.  
  216.    `fastmap' is the resulting character set.  It is a character array
  217.    whose elements are either `FASTMAP_FALSE' or `FASTMAP_TRUE'.
  218.  
  219.    Return values:
  220.    0 => pattern cannot match the null string.
  221.    1 => pattern can match the null string.
  222.    2 => pattern can match the null string, but only at end of match
  223.      text or to left of a character in `fastmap'.
  224.    -2 => the pattern is improperly formed.
  225.    else => undefined. */
  226.  
  227. #define FASTMAP_FALSE '\0'
  228. #define FASTMAP_TRUE '\1'
  229.  
  230. int
  231. DEFUN (re_compile_fastmap,
  232.        (pattern_start, pattern_end, translation, syntax_table, fastmap),
  233.        unsigned char * pattern_start
  234.        AND fast unsigned char * pattern_end
  235.        AND unsigned char * translation
  236.        AND SYNTAX_TABLE_TYPE syntax_table
  237.        AND fast unsigned char * fastmap)
  238. {
  239.   fast unsigned char *pattern_pc;
  240.   unsigned char *stack_start[RE_NFAILURES];
  241.   unsigned char **stack_pointer;
  242.   int return_value;
  243.  
  244.   pattern_pc = pattern_start;
  245.   return_value = 0;
  246.   stack_pointer = stack_start;
  247.  
  248.   {
  249.     fast int i;
  250.  
  251.     FOR_ALL_ASCII (i)
  252.       (fastmap [i]) = FASTMAP_FALSE;
  253.   }
  254.  
  255.  loop:
  256.   if (pattern_pc >= pattern_end)
  257.     RE_RETURN (1);
  258.  
  259.   SWITCH_ENUM (regexpcode, (*pattern_pc++))
  260.     {
  261.     case regexpcode_unused:
  262.     case regexpcode_line_start:
  263.     case regexpcode_buffer_start:
  264.     case regexpcode_buffer_end:
  265.     case regexpcode_word_start:
  266.     case regexpcode_word_end:
  267.     case regexpcode_word_bound:
  268.     case regexpcode_not_word_bound:
  269.       goto loop;
  270.  
  271.     case regexpcode_line_end:
  272.       {
  273.     (fastmap [(TRANSLATE_CHAR ('\n'))]) = FASTMAP_TRUE;
  274.     if (return_value == 0)
  275.       return_value = 2;
  276.     goto next;
  277.       }
  278.  
  279.     case regexpcode_exact_1:
  280.       {
  281.     fast int ascii;
  282.  
  283.     READ_PATTERN_CHAR (ascii);
  284.     (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  285.     goto next;
  286.       }
  287.  
  288.     case regexpcode_exact_n:
  289.       {
  290.     fast int length;
  291.  
  292.     READ_PATTERN_LENGTH (length);
  293.     if (length == 0)
  294.       goto loop;
  295.     (fastmap [(TRANSLATE_CHAR (pattern_pc [0]))]) = FASTMAP_TRUE;
  296.     goto next;
  297.       }
  298.  
  299.     case regexpcode_any_char:
  300.       {
  301.     fast int ascii;
  302.  
  303.     FOR_ALL_ASCII_SUCH_THAT (ascii, (ascii != '\n'))
  304.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  305.     if (return_value != 0)
  306.       goto return_point;
  307.     goto next;
  308.       }
  309.  
  310.     case regexpcode_char_set:
  311.       {
  312.     fast int length;
  313.     fast int ascii;
  314.  
  315.     READ_PATTERN_LENGTH (length);
  316.     length = (length * ASCII_LENGTH);
  317.     FOR_INDEX_BELOW (ascii, length)
  318.       if (CHAR_SET_MEMBER_P_INTERNAL (pattern_pc, ascii))
  319.         (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  320.     goto next;
  321.       }
  322.  
  323.     case regexpcode_not_char_set:
  324.       {
  325.     fast int length;
  326.     fast int ascii;
  327.  
  328.     READ_PATTERN_LENGTH (length);
  329.     length = (length * ASCII_LENGTH);
  330.     FOR_INDEX_BELOW (ascii, length)
  331.       if (! (CHAR_SET_MEMBER_P_INTERNAL (pattern_pc, ascii)))
  332.         (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  333.     FOR_INDEX_RANGE (ascii, length, MAX_ASCII)
  334.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  335.     goto next;
  336.       }
  337.  
  338.     case regexpcode_word_char:
  339.       {
  340.     fast int ascii;
  341.  
  342.     FOR_ALL_ASCII_SUCH_THAT (ascii, (WORD_CONSTITUENT_P (ascii)))
  343.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  344.     goto next;
  345.       }
  346.  
  347.     case regexpcode_not_word_char:
  348.       {
  349.     fast int ascii;
  350.  
  351.     FOR_ALL_ASCII_SUCH_THAT (ascii, (! (WORD_CONSTITUENT_P (ascii))))
  352.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  353.     goto next;
  354.       }
  355.  
  356.     case regexpcode_syntax_spec:
  357.       {
  358.     fast enum syntaxcode code;
  359.     fast int ascii;
  360.  
  361.     READ_PATTERN_SYNTAXCODE (code);
  362.     FOR_ALL_ASCII_SUCH_THAT (ascii, (SYNTAX_CONSTITUENT_P (code, ascii)))
  363.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  364.     goto next;
  365.       }
  366.  
  367.     case regexpcode_not_syntax_spec:
  368.       {
  369.     fast enum syntaxcode code;
  370.     fast int ascii;
  371.  
  372.     READ_PATTERN_SYNTAXCODE (code);
  373.     FOR_ALL_ASCII_SUCH_THAT (ascii,
  374.                  (! (SYNTAX_CONSTITUENT_P (code, ascii))))
  375.       (fastmap [(TRANSLATE_CHAR (ascii))]) = FASTMAP_TRUE;
  376.     goto next;
  377.       }
  378.  
  379.     case regexpcode_start_memory:
  380.     case regexpcode_stop_memory:
  381.       {
  382.     fast int register_number;
  383.  
  384.     READ_PATTERN_REGISTER (register_number);
  385.     goto loop;
  386.       }
  387.  
  388.     case regexpcode_duplicate:
  389.       {
  390.     fast int register_number;
  391.     fast int ascii;
  392.  
  393.     READ_PATTERN_REGISTER (register_number);
  394.     FOR_ALL_ASCII (ascii)
  395.       (fastmap [ascii]) = FASTMAP_TRUE;
  396.     RE_RETURN (1);
  397.       }
  398.  
  399.     case regexpcode_jump:
  400.     case regexpcode_finalize_jump:
  401.     case regexpcode_maybe_finalize_jump:
  402.     case regexpcode_dummy_failure_jump:
  403.       {
  404.     fast int offset;
  405.  
  406.     return_value = 1;
  407.     READ_PATTERN_OFFSET (offset);
  408.     pattern_pc += offset;
  409.     if (offset > 0)
  410.       goto loop;
  411.  
  412.     /* Jump backward reached implies we just went through the
  413.        body of a loop and matched nothing.  Opcode jumped to
  414.        should be an on_failure_jump.  Just treat it like an
  415.        ordinary jump.  For a * loop, it has pushed its failure
  416.        point already; if so, discard that as redundant. */
  417.     if (pattern_pc >= pattern_end)
  418.       BAD_PATTERN ();
  419.     if (((enum regexpcode) (pattern_pc [0])) !=
  420.         regexpcode_on_failure_jump)
  421.       goto loop;
  422.     READ_PATTERN_OFFSET (offset);
  423.     pattern_pc += offset;
  424.     if ((stack_pointer != stack_start) &&
  425.         ((stack_pointer [-1]) == pattern_pc))
  426.       stack_pointer -= 1;
  427.     goto loop;
  428.       }
  429.  
  430.     case regexpcode_on_failure_jump:
  431.       {
  432.     fast int offset;
  433.  
  434.     READ_PATTERN_OFFSET (offset);
  435.     (*stack_pointer++) = (pattern_pc + offset);
  436.     goto loop;
  437.       }
  438.  
  439.     default:
  440.       BAD_PATTERN ();
  441.     }
  442.  
  443.  next:
  444.   if (stack_pointer != stack_start)
  445.     {
  446.       pattern_pc = (*--stack_pointer);
  447.       goto loop;
  448.     }
  449.  
  450.  return_point:
  451.   return (return_value);
  452. }
  453.  
  454. /* Match the compiled pattern described by `pattern_start' and
  455.    `pattern_end' against the characters in `buffer' between
  456.    `match_start' and `match_end'.
  457.  
  458.    `registers', if not NULL, will be filled with the start and end
  459.    indices of the match registers if the match succeeds.
  460.  
  461.    It is assumed that the following is true:
  462.  
  463.    (! ((gap_start < gap_end) &&
  464.        (match_start < match_end) &&
  465.        ((match_start == gap_start) || (match_end == gap_end))))
  466.  
  467.    Return values:
  468.  
  469.    non-negative => the end index (exclusive) of the match.
  470.    -1 => no match.
  471.    -2 => the pattern is badly formed.
  472.    -3 => memory allocation error.
  473.    -4 => match stack overflow.
  474.    other => undefined. */
  475.  
  476. #define RE_MATCH_FAILED (-1)
  477.  
  478. /* This macro is used by search procedures to decide when a match at a
  479.    particular place has failed.  If true, the search continues by
  480.    advancing to the next match point.  */
  481. #define RE_MATCH_FAILURE_RESULT(result)                    \
  482.   (((result) == RE_MATCH_FAILED) || ((result) == (-4)))
  483.  
  484. #define ADDRESS_TO_INDEX(address)                    \
  485.   ((((address) > gap_start) ? ((address) - gap_length) : (address))    \
  486.    - (buffer -> text))
  487.  
  488. #define READ_MATCH_CHAR(target) do                    \
  489. {                                    \
  490.   if (match_pc >= match_end)                        \
  491.     goto re_match_fail;                            \
  492.   (target) = (TRANSLATE_CHAR (*match_pc++));                \
  493.   if (match_pc == gap_start)                        \
  494.     match_pc = gap_end;                            \
  495. } while (0)
  496.  
  497. static Boolean
  498. DEFUN (beq_translate, (scan1, scan2, length, translation),
  499.        unsigned char * scan1 AND
  500.        unsigned char * scan2 AND
  501.        long length AND
  502.        unsigned char * translation)
  503. {
  504.   while ((length--) > 0)
  505.     if ((TRANSLATE_CHAR (*scan1++)) != (TRANSLATE_CHAR (*scan2++)))
  506.       return (false);
  507.   return (true);
  508. }
  509.  
  510. int re_max_failures = 1000;
  511.  
  512. int
  513. DEFUN (re_match,
  514.        (pattern_start, pattern_end, buffer, registers, match_start, match_end),
  515.        unsigned char * pattern_start
  516.        AND unsigned char * pattern_end
  517.        AND struct re_buffer * buffer
  518.        AND struct re_registers * registers
  519.        AND unsigned char * match_start
  520.        AND unsigned char * match_end)
  521. {
  522.   fast unsigned char *pattern_pc, *match_pc;
  523.   unsigned char *gap_start, *gap_end;
  524.   unsigned char *translation;
  525.   SYNTAX_TABLE_TYPE syntax_table;
  526.   long gap_length;
  527.   int return_value;
  528.  
  529.   /* Failure point stack.  Each place that can handle a failure
  530.      further down the line pushes a failure point on this stack.  It
  531.      consists of two char *'s.  The first one pushed is where to
  532.      resume scanning the pattern; the second pushed is where to resume
  533.      scanning the match text.  If the latter is NULL, the failure
  534.      point is a "dummy".  If a failure happens and the innermost
  535.      failure point is dormant, it discards that failure point and
  536.      tries the next one. */
  537.  
  538.   unsigned char **stack_start, **stack_end, **stack_pointer;
  539.  
  540.   /* Information on the "contents" of registers.  These are pointers
  541.      into the match text; they record just what was matched (on this
  542.      attempt) by some part of the pattern.  The start_memory command
  543.      stores the start of a register's contents and the stop_memory
  544.      command stores the end.
  545.  
  546.      At that point, (register_start [regnum]) points to the first
  547.      character in the register, and (register_end [regnum]) points to
  548.      the first character beyond the end of the register. */
  549.  
  550.   unsigned char *register_start[RE_NREGS];
  551.   unsigned char *register_end[RE_NREGS];
  552.  
  553.   pattern_pc = pattern_start;
  554.   match_pc = match_start;
  555.   gap_start = (buffer -> gap_start);
  556.   gap_end = (buffer -> gap_end);
  557.   gap_length = (gap_end - gap_start);
  558.   translation = (buffer -> translation);
  559.   syntax_table = (buffer -> syntax_table);
  560.  
  561.   stack_start =
  562.     ((unsigned char **) (malloc ((2 * RE_NFAILURES) * (sizeof (char *)))));
  563.   if (stack_start == NULL)
  564.     RE_RETURN (-3);
  565.  
  566.   stack_end = (& (stack_start [(2 * RE_NFAILURES)]));
  567.   stack_pointer = stack_start;
  568.  
  569.   {
  570.     fast int i;
  571.  
  572.     FOR_INDEX_BELOW (i, RE_NREGS)
  573.       {
  574.     (register_start [i]) = NULL;
  575.     (register_end [i]) = NULL;
  576.       }
  577.   }
  578.  
  579.  re_match_loop:
  580.   if (pattern_pc >= pattern_end)
  581.     {
  582.       /* Reaching here indicates that match was successful. */
  583.       if (registers != NULL)
  584.     {
  585.       fast int i;
  586.  
  587.       (register_start [0]) = match_start;
  588.       (register_end [0]) = match_pc;
  589.       FOR_INDEX_BELOW (i, RE_NREGS)
  590.         {
  591.           ((registers -> start) [i]) =
  592.         (((register_start [i]) == NULL)
  593.          ? -1
  594.          : (ADDRESS_TO_INDEX (register_start [i])));
  595.           ((registers -> end) [i]) =
  596.         (((register_end [i]) == NULL)
  597.          ? -1
  598.          : (ADDRESS_TO_INDEX (register_end [i])));
  599.         }
  600.     }
  601.       RE_RETURN (ADDRESS_TO_INDEX (match_pc));
  602.     }
  603.  
  604.   SWITCH_ENUM (regexpcode, (*pattern_pc++))
  605.     {
  606.     case regexpcode_unused:
  607.       goto re_match_loop;
  608.  
  609.     case regexpcode_exact_1:
  610.       {
  611.     fast int ascii;
  612.     fast int ascii_p;
  613.  
  614.     READ_MATCH_CHAR (ascii);
  615.     READ_PATTERN_CHAR (ascii_p);
  616.     if (ascii == ascii_p)
  617.       goto re_match_loop;
  618.     goto re_match_fail;
  619.       }
  620.  
  621.     case regexpcode_exact_n:
  622.       {
  623.     fast int length;
  624.     fast int ascii;
  625.  
  626.     READ_PATTERN_LENGTH (length);
  627.     while ((length--) > 0)
  628.       {
  629.         READ_MATCH_CHAR (ascii);
  630.         if (ascii != (*pattern_pc++))
  631.           goto re_match_fail;
  632.       }
  633.     goto re_match_loop;
  634.       }
  635.  
  636.     case regexpcode_any_char:
  637.       {
  638.     fast int ascii;
  639.  
  640.     READ_MATCH_CHAR (ascii);
  641.     if (ascii == '\n')
  642.       goto re_match_fail;
  643.     goto re_match_loop;
  644.       }
  645.  
  646. #define RE_MATCH_CHAR_SET(winning_label, losing_label)            \
  647.       {                                    \
  648.     fast int ascii;                            \
  649.     fast int length;                        \
  650.                                     \
  651.     READ_MATCH_CHAR (ascii);                    \
  652.     READ_PATTERN_LENGTH (length);                    \
  653.     if (CHAR_SET_MEMBER_P (length, pattern_pc, ascii))        \
  654.       {                                \
  655.         pattern_pc += length;                    \
  656.         goto winning_label;                        \
  657.       }                                \
  658.     else                                \
  659.       {                                \
  660.         pattern_pc += length;                    \
  661.         goto losing_label;                        \
  662.       }                                \
  663.       }
  664.  
  665.     case regexpcode_char_set:
  666.       RE_MATCH_CHAR_SET (re_match_loop, re_match_fail);
  667.  
  668.     case regexpcode_not_char_set:
  669.       RE_MATCH_CHAR_SET (re_match_fail, re_match_loop);
  670.  
  671. #undef RE_MATCH_CHAR_SET
  672.  
  673.     /* \( is represented by a start_memory, \) by a stop_memory.  Both
  674.        of those commands contain a "register number" argument.  The
  675.        text matched within the \( and \) is recorded under that
  676.        number.  Then, \<digit> turns into a `duplicate' command which
  677.        is followed by the numeric value of <digit> as the register
  678.        number. */
  679.  
  680.     case regexpcode_start_memory:
  681.       {
  682.     fast int register_number;
  683.  
  684.     READ_PATTERN_REGISTER (register_number);
  685.     (register_start [register_number]) = match_pc;
  686.     goto re_match_loop;
  687.       }
  688.  
  689.     case regexpcode_stop_memory:
  690.       {
  691.     fast int register_number;
  692.  
  693.     READ_PATTERN_REGISTER (register_number);
  694.     (register_end [register_number]) =
  695.       ((match_pc == gap_end) ? gap_start : match_pc);
  696.     goto re_match_loop;
  697.       }
  698.  
  699.     case regexpcode_duplicate:
  700.       {
  701.     fast int register_number;
  702.     unsigned char *start, *end, *new_end;
  703.     long length;
  704.  
  705.     READ_PATTERN_REGISTER (register_number);
  706.     start = (register_start [register_number]);
  707.     end = (register_end [register_number]);
  708.     length = (end - start);
  709.     if (length <= 0)
  710.       goto re_match_loop;
  711.     new_end = (match_pc + length);
  712.     if (new_end > match_end)
  713.       goto re_match_fail;
  714.     if ((match_pc <= gap_start) && (new_end > gap_start))
  715.       {
  716.         long length1, length2;
  717.  
  718.         new_end += gap_length;
  719.         if (new_end > match_end)
  720.           goto re_match_fail;
  721.         length1 = (gap_start - match_pc);
  722.         length2 = (length - length1);
  723.         if (!
  724.         ((beq_translate (match_pc, start, length1, translation)) &&
  725.          (beq_translate (gap_end, (start + length1), length2,
  726.                  translation))))
  727.           goto re_match_fail;
  728.       }
  729.     else if ((start <= gap_start) && (end > gap_start))
  730.       {
  731.         long length1, length2;
  732.  
  733.         length1 = (gap_start - start);
  734.         length2 = (end - gap_end);
  735.         if (!
  736.         ((beq_translate (match_pc, start, length1, translation)) &&
  737.          (beq_translate ((match_pc + length1), gap_end, length2,
  738.                  translation))))
  739.           goto re_match_fail;
  740.       }
  741.     else
  742.       {
  743.         if (! (beq_translate (match_pc, start, length, translation)))
  744.           goto re_match_fail;
  745.       }
  746.     match_pc = ((new_end == gap_start) ? gap_end : new_end);
  747.     goto re_match_loop;
  748.       }
  749.  
  750.     case regexpcode_buffer_start:
  751.       {
  752.     if ((ADDRESS_TO_INDEX (match_pc))
  753.         == (ADDRESS_TO_INDEX (buffer -> text_start)))
  754.       goto re_match_loop;
  755.     goto re_match_fail;
  756.       }
  757.  
  758.     case regexpcode_buffer_end:
  759.       {
  760.     if ((ADDRESS_TO_INDEX (match_pc))
  761.         == (ADDRESS_TO_INDEX (buffer -> text_end)))
  762.       goto re_match_loop;
  763.     goto re_match_fail;
  764.       }
  765.  
  766.     case regexpcode_line_start:
  767.       {
  768.     if ((ADDRESS_TO_INDEX (match_pc))
  769.         == (ADDRESS_TO_INDEX (buffer -> text_start)))
  770.       goto re_match_loop;
  771.     if ((TRANSLATE_CHAR
  772.          (((match_pc == gap_end) ? gap_start : match_pc) [-1]))
  773.         == '\n')
  774.       goto re_match_loop;
  775.     goto re_match_fail;
  776.       }
  777.  
  778.     case regexpcode_line_end:
  779.       {
  780.     if (((ADDRESS_TO_INDEX (match_pc))
  781.          == (ADDRESS_TO_INDEX (buffer -> text_end)))
  782.         || ((TRANSLATE_CHAR (match_pc [0])) == '\n'))
  783.       goto re_match_loop;
  784.     goto re_match_fail;
  785.       }
  786.  
  787. #define RE_MATCH_WORD_BOUND(word_bound_p)                \
  788.   if ((match_pc == gap_end)                        \
  789.       ? (word_bound_p                            \
  790.      (((gap_start != (buffer -> text_start))            \
  791.        && (WORD_CONSTITUENT_P (TRANSLATE_CHAR (gap_start[-1])))),    \
  792.       ((gap_end != (buffer -> text_end))                \
  793.        && (WORD_CONSTITUENT_P (TRANSLATE_CHAR (gap_end[0]))))))    \
  794.       : (word_bound_p                            \
  795.      (((match_pc != (buffer -> text_start))                \
  796.        && (WORD_CONSTITUENT_P (TRANSLATE_CHAR (match_pc[-1])))),    \
  797.       ((match_pc != (buffer -> text_end))                \
  798.        && (WORD_CONSTITUENT_P (TRANSLATE_CHAR (match_pc[0])))))))    \
  799.       goto re_match_loop;                        \
  800.     goto re_match_fail
  801.  
  802.     case regexpcode_word_bound:
  803. #define WORD_BOUND_P(left_p, right_p) ((left_p) != (right_p))
  804.       RE_MATCH_WORD_BOUND (WORD_BOUND_P);
  805. #undef WORD_BOUND_P
  806.  
  807.     case regexpcode_not_word_bound:
  808. #define NOT_WORD_BOUND_P(left_p, right_p) ((left_p) == (right_p))
  809.       RE_MATCH_WORD_BOUND (NOT_WORD_BOUND_P);
  810. #undef NOT_WORD_BOUND_P
  811.  
  812.     case regexpcode_word_start:
  813. #define WORD_START_P(left_p, right_p) ((! (left_p)) && (right_p))
  814.       RE_MATCH_WORD_BOUND (WORD_START_P);
  815. #undef WORD_START_P
  816.  
  817.     case regexpcode_word_end:
  818. #define WORD_END_P(left_p, right_p) ((left_p) && (! (right_p)))
  819.       RE_MATCH_WORD_BOUND (WORD_END_P);
  820. #undef WORD_END_P
  821.  
  822. #undef RE_MATCH_WORD_BOUND
  823.  
  824.     case regexpcode_syntax_spec:
  825.       {
  826.     fast int ascii;
  827.     fast enum syntaxcode code;
  828.  
  829.     READ_MATCH_CHAR (ascii);
  830.     READ_PATTERN_SYNTAXCODE (code);
  831.     if (SYNTAX_CONSTITUENT_P (code, ascii))
  832.       goto re_match_loop;
  833.     goto re_match_fail;
  834.       }
  835.  
  836.     case regexpcode_not_syntax_spec:
  837.       {
  838.     fast int ascii;
  839.     fast enum syntaxcode code;
  840.  
  841.     READ_MATCH_CHAR (ascii);
  842.     READ_PATTERN_SYNTAXCODE (code);
  843.     if (! (SYNTAX_CONSTITUENT_P (code, ascii)))
  844.       goto re_match_loop;
  845.     goto re_match_fail;
  846.       }
  847.  
  848.     case regexpcode_word_char:
  849.       {
  850.     fast int ascii;
  851.  
  852.     READ_MATCH_CHAR (ascii);
  853.     if (WORD_CONSTITUENT_P (ascii))
  854.       goto re_match_loop;
  855.     goto re_match_fail;
  856.       }
  857.  
  858.     case regexpcode_not_word_char:
  859.       {
  860.     fast int ascii;
  861.  
  862.     READ_MATCH_CHAR (ascii);
  863.     if (! (WORD_CONSTITUENT_P (ascii)))
  864.       goto re_match_loop;
  865.     goto re_match_fail;
  866.       }
  867.  
  868.     /* "or" constructs ("|") are handled by starting each alternative
  869.        with an on_failure_jump that points to the start of the next
  870.        alternative.  Each alternative except the last ends with a jump
  871.        to the joining point.  (Actually, each jump except for the last
  872.        one really jumps to the following jump, because tensioning the
  873.        jumps is a hassle.)
  874.  
  875.        The start of a stupid repeat has an on_failure_jump that points
  876.        past the end of the repeat text.  This makes a failure point so
  877.        that, on failure to match a repetition, matching restarts past
  878.        as many repetitions have been found with no way to fail and
  879.        look for another one.
  880.  
  881.        A smart repeat is similar but loops back to the on_failure_jump
  882.        so that each repetition makes another failure point. */
  883.  
  884.     case regexpcode_on_failure_jump:
  885.       {
  886.     fast long offset;
  887.  
  888.     READ_PATTERN_OFFSET (offset);
  889.     PUSH_FAILURE_POINT ((pattern_pc + offset), match_pc);
  890.     goto re_match_loop;
  891.       }
  892.  
  893.     /* The end of a smart repeat has a maybe_finalize_jump back.
  894.        Change it either to a finalize_jump or an ordinary jump. */
  895.  
  896.     case regexpcode_maybe_finalize_jump:
  897.       {
  898.     fast long offset;
  899.     fast long ascii;
  900.  
  901.     READ_PATTERN_OFFSET (offset);
  902.     if (pattern_pc == pattern_end)
  903.       goto finalize_jump;
  904.  
  905.     /* Compare what follows with the beginning of the repeat.
  906.        If we can establish that there is nothing that they
  907.        would both match, we can change to `finalize_jump'. */
  908.  
  909.     SWITCH_ENUM (regexpcode, (pattern_pc [0]))
  910.       {
  911.       case regexpcode_exact_1:
  912.         ascii = (pattern_pc [1]);
  913.         break;
  914.  
  915.       case regexpcode_exact_n:
  916.         ascii = (pattern_pc [2]);
  917.         break;
  918.  
  919.       case regexpcode_line_end:
  920.         ascii = ('\n');
  921.         break;
  922.  
  923.       default:
  924.         goto dont_finalize_jump;
  925.       }
  926.  
  927.     /* (pattern_pc [(offset - 3)]) is an `on_failure_jump'.
  928.        Examine what follows that. */
  929.     SWITCH_ENUM (regexpcode, (pattern_pc [offset]))
  930.       {
  931.       case regexpcode_exact_1:
  932.         {
  933.           if (ascii != (pattern_pc [(offset + 1)]))
  934.         goto finalize_jump;
  935.           goto dont_finalize_jump;
  936.         }
  937.  
  938.       case regexpcode_exact_n:
  939.         {
  940.           if (ascii != (pattern_pc [(offset + 2)]))
  941.         goto finalize_jump;
  942.           goto dont_finalize_jump;
  943.         }
  944.  
  945.       case regexpcode_char_set:
  946.         {
  947.           if (CHAR_SET_MEMBER_P ((pattern_pc [(offset + 1)]),
  948.                      (& (pattern_pc [(offset + 2)])),
  949.                      ascii))
  950.         goto dont_finalize_jump;
  951.           goto finalize_jump;
  952.         }
  953.  
  954.       case regexpcode_not_char_set:
  955.         {
  956.           if (CHAR_SET_MEMBER_P ((pattern_pc [(offset + 1)]),
  957.                      (& (pattern_pc [(offset + 2)])),
  958.                      ascii))
  959.         goto finalize_jump;
  960.           goto dont_finalize_jump;
  961.         }
  962.  
  963.       default:
  964.         goto dont_finalize_jump;
  965.       }
  966.  
  967.       finalize_jump:
  968.     pattern_pc -= 2;
  969.     (pattern_pc [-1]) = ((unsigned char) regexpcode_finalize_jump);
  970.     goto re_match_finalize_jump;
  971.  
  972.       dont_finalize_jump:
  973.     pattern_pc -= 2;
  974.     (pattern_pc [-1]) = ((unsigned char) regexpcode_jump);
  975.     goto re_match_jump;
  976.       }
  977.  
  978.     case regexpcode_finalize_jump:
  979.     re_match_finalize_jump:
  980.       {
  981.     stack_pointer -= 2;
  982.     goto re_match_jump;
  983.       }
  984.  
  985.     case regexpcode_jump:
  986.     re_match_jump:
  987.       {
  988.     fast long offset;
  989.  
  990.     READ_PATTERN_OFFSET (offset);
  991.     pattern_pc += offset;
  992.     goto re_match_loop;
  993.       }
  994.  
  995.     case regexpcode_dummy_failure_jump:
  996.       {
  997.     PUSH_FAILURE_POINT (NULL, NULL);
  998.     goto re_match_jump;
  999.       }
  1000.  
  1001.     default:
  1002.       {
  1003.     BAD_PATTERN ();
  1004.       }
  1005.     }
  1006.  
  1007.  re_match_fail:
  1008.   if (stack_pointer == stack_start)
  1009.     RE_RETURN (RE_MATCH_FAILED);
  1010.   match_pc = (*--stack_pointer);
  1011.   pattern_pc = (*--stack_pointer);
  1012.   if (pattern_pc != NULL)
  1013.     goto re_match_loop;
  1014.   goto re_match_fail;
  1015.  
  1016.  return_point:
  1017.   if (stack_start != NULL)
  1018.     free (stack_start);
  1019.   return (return_value);
  1020. }
  1021.  
  1022. #define DEFINE_RE_SEARCH(name)                        \
  1023. int                                    \
  1024. DEFUN (name,                                \
  1025.        (pattern_start, pattern_end, buffer, registers,            \
  1026.     match_start, match_end),                    \
  1027.        unsigned char * pattern_start                    \
  1028.        AND unsigned char * pattern_end                    \
  1029.        AND struct re_buffer * buffer                    \
  1030.        AND struct re_registers * registers                \
  1031.        AND unsigned char * match_start                    \
  1032.        AND unsigned char * match_end)
  1033.  
  1034. #define INITIALIZE_RE_SEARCH(pc, limit, gap_limit)            \
  1035.   int can_be_null;                            \
  1036.   unsigned char *translation;                        \
  1037.   int match_result;                            \
  1038.                                     \
  1039.   fast unsigned char *match_pc;                        \
  1040.   fast unsigned char *match_limit;                    \
  1041.   fast unsigned char *gap_limit;                    \
  1042.   fast unsigned char *fastmap;                        \
  1043.   unsigned char fastmap_array[MAX_ASCII];                \
  1044.                                     \
  1045.   fastmap = &fastmap_array[0];                        \
  1046.   translation = (buffer -> translation);                \
  1047.   can_be_null =                                \
  1048.     (re_compile_fastmap                            \
  1049.      (pattern_start, pattern_end, translation,                \
  1050.       (buffer -> syntax_table), fastmap));                \
  1051.   if (can_be_null < 0)                            \
  1052.     return (can_be_null);                        \
  1053.                                     \
  1054.   match_pc = (pc);                            \
  1055.   match_limit = (limit);                        \
  1056.   gap_limit = (buffer -> gap_limit)
  1057.  
  1058. #define RE_SEARCH_TEST(start)                        \
  1059.   (re_match                                \
  1060.    (pattern_start, pattern_end, buffer, registers, (start), match_end))
  1061.  
  1062. #define RE_SEARCH_FORWARD_FAST(limit) do                \
  1063. {                                    \
  1064.   while (true)                                \
  1065.     {                                    \
  1066.       if (match_pc >= (limit))                        \
  1067.     break;                                \
  1068.                                     \
  1069.       if ((fastmap [(TRANSLATE_CHAR (*match_pc++))]) == FASTMAP_FALSE)    \
  1070.     continue;                            \
  1071.                                     \
  1072.       match_result = (RE_SEARCH_TEST (match_pc - 1));            \
  1073.       if (RE_MATCH_FAILURE_RESULT (match_result))            \
  1074.     continue;                            \
  1075.                                     \
  1076.       return (match_result);                        \
  1077.     }                                    \
  1078. } while (0)
  1079.  
  1080. DEFINE_RE_SEARCH (re_search_forward)
  1081. {
  1082.   INITIALIZE_RE_SEARCH (match_start, match_end, gap_start);
  1083.  
  1084.   if (can_be_null != 1)
  1085.     {
  1086.       if ((match_pc < gap_start) && (gap_start < match_limit))
  1087.     RE_SEARCH_FORWARD_FAST (gap_start);
  1088.       if (match_pc == gap_start)
  1089.     match_pc = (buffer -> gap_end);
  1090.       RE_SEARCH_FORWARD_FAST (match_limit);
  1091.       return
  1092.     ((can_be_null == 0)
  1093.      ? RE_MATCH_FAILED
  1094.      : (RE_SEARCH_TEST (match_limit)));
  1095.     }
  1096.   else
  1097.     {
  1098.       while (true)
  1099.     {
  1100.       match_result = (RE_SEARCH_TEST (match_pc));
  1101.       if (! (RE_MATCH_FAILURE_RESULT (match_result)))
  1102.         return (match_result);
  1103.       match_pc += 1;
  1104.       if (match_pc == gap_start)
  1105.         match_pc = (buffer -> gap_end);
  1106.       if (match_pc > match_limit)
  1107.         return (match_result);
  1108.     }
  1109.     }
  1110. }
  1111.  
  1112. #define RE_SEARCH_BACKWARD_FAST(limit) do                \
  1113. {                                    \
  1114.   while (true)                                \
  1115.     {                                    \
  1116.       if (match_pc <= (limit))                        \
  1117.     break;                                \
  1118.                                     \
  1119.       if ((fastmap [(TRANSLATE_CHAR (*--match_pc))]) == FASTMAP_FALSE)    \
  1120.     continue;                            \
  1121.                                     \
  1122.       match_result = (RE_SEARCH_TEST (match_pc));            \
  1123.       if (RE_MATCH_FAILURE_RESULT (match_result))            \
  1124.     continue;                            \
  1125.                                     \
  1126.       RE_SEARCH_BACKWARD_RETURN (match_pc);                \
  1127.     }                                    \
  1128. } while (0)
  1129.  
  1130. #define RE_SEARCH_BACKWARD_RETURN(start)                \
  1131.   return                                \
  1132.     ((match_result < 0)                            \
  1133.      ? match_result                            \
  1134.      : ((((start) > (buffer -> gap_start))                \
  1135.      ? ((start) - (gap_end - (buffer -> gap_start)))        \
  1136.      : (start))                            \
  1137.     - (buffer -> text)))
  1138.  
  1139. DEFINE_RE_SEARCH (re_search_backward)
  1140. {
  1141.   INITIALIZE_RE_SEARCH (match_end, match_start, gap_end);
  1142.  
  1143.   if (can_be_null != 1)
  1144.     {
  1145.       if ((match_pc > gap_end) && (gap_end > match_limit))
  1146.     RE_SEARCH_BACKWARD_FAST (gap_end);
  1147.       if (match_pc == gap_end)
  1148.     match_pc = (buffer -> gap_start);
  1149.       RE_SEARCH_BACKWARD_FAST (match_limit);
  1150.       if (can_be_null == 0)
  1151.     return (RE_MATCH_FAILED);
  1152.       match_result = (RE_SEARCH_TEST (match_limit));
  1153.       RE_SEARCH_BACKWARD_RETURN (match_limit);
  1154.     }
  1155.   else
  1156.     {
  1157.       while (true)
  1158.     {
  1159.       match_result = (RE_SEARCH_TEST (match_pc));
  1160.       if (! (RE_MATCH_FAILURE_RESULT (match_result)))
  1161.         RE_SEARCH_BACKWARD_RETURN (match_pc);
  1162.       if (match_pc == gap_end)
  1163.         match_pc = (buffer -> gap_start);
  1164.       match_pc -= 1;
  1165.       if (match_pc < match_limit)
  1166.         RE_SEARCH_BACKWARD_RETURN (match_pc);
  1167.     }
  1168.     }
  1169. }
  1170.