home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / elvis184.zip / src / regexp.c < prev    next >
C/C++ Source or Header  |  1995-05-26  |  21KB  |  1,020 lines
  1. /* regexp.c */
  2.  
  3. /* This file contains the code that compiles regular expressions and executes
  4.  * them.  It supports the same syntax and features as vi's regular expression
  5.  * code.  Specifically, the meta characters are:
  6.  *    ^    matches the beginning of a line
  7.  *    $    matches the end of a line
  8.  *    \<    matches the beginning of a word
  9.  *    \>    matches the end of a word
  10.  *    .    matches any single character
  11.  *    []    matches any character in a character class
  12.  *    \@    matches the word at the cursor, if any
  13.  *    \=    if searching, leaves the cursor here
  14.  *    \(    delimits the start of a subexpression
  15.  *    \)    delimits the end of a subexpression
  16.  *    *    repeats the preceding 0 or more times 
  17.  *    \+    repeats the preceding 1 or more times
  18.  *    \?    repeats the preceding 0 or 1 times
  19.  *    \{m\}    repeats the preceding m times
  20.  *    \{m,\}    repeats the preceding m or more times
  21.  *    \{m,n\}    repeats the preceding between m and n times
  22.  * NOTE: You cannot follow a \) with a closure operator such as *
  23.  *
  24.  * The physical structure of a compiled RE is as follows:
  25.  *    - First, there is a one-byte value that says how many character classes
  26.  *      are used in this regular expression
  27.  *    - Next, each character class is stored as a bitmap that is 256 bits
  28.  *      (32 bytes) long.
  29.  *    - A mixture of literal characters and compiled meta characters follows.
  30.  *      This begins with M_BEGIN(0) and ends with M_END(0).  All meta chars
  31.  *      are stored as a \n followed by a one-byte code, so they take up two
  32.  *      bytes apiece.  Literal characters take up one byte apiece.  \n can't
  33.  *      be used as a literal character.
  34.  *
  35.  * If NO_MAGIC is defined, then a different set of functions is used instead.
  36.  * That right, this file contains TWO versions of the code.
  37.  */
  38.  
  39. #include <setjmp.h>
  40. #include "config.h"
  41. #include "ctype.h"
  42. #include "vi.h"
  43. #include "regexp.h"
  44.  
  45.  
  46.  
  47. static char    *previous;    /* the previous regexp, used when null regexp is given */
  48.  
  49.  
  50. #ifndef NO_MAGIC
  51. /* THE REAL REGEXP PACKAGE IS USED UNLESS "NO_MAGIC" IS DEFINED */
  52.  
  53. /* These are used to classify or recognize meta-characters */
  54. #define META        '\0'
  55. #define BASE_META(m)    ((m) - 256)
  56. #define INT_META(c)    ((c) + 256)
  57. #define IS_META(m)    ((m) >= 256)
  58. #define IS_CLASS(m)    ((m) >= M_CLASS(0) && (m) <= M_CLASS(9))
  59. #define IS_START(m)    ((m) >= M_START(0) && (m) <= M_START(9))
  60. #define IS_END(m)    ((m) >= M_END(0) && (m) <= M_END(9))
  61. #define IS_CLOSURE(m)    ((m) >= M_SPLAT && (m) <= M_RANGE)
  62. #define ADD_META(s,m)    (*(s)++ = META, *(s)++ = BASE_META(m))
  63. #define GET_META(s)    (*(s) == META ? INT_META(*++(s)) : *s)
  64.  
  65. /* These are the internal codes used for each type of meta-character */
  66. #define M_BEGLINE    256        /* internal code for ^ */
  67. #define M_ENDLINE    257        /* internal code for $ */
  68. #define M_BEGWORD    258        /* internal code for \< */
  69. #define M_ENDWORD    259        /* internal code for \> */
  70. #define M_ANY        260        /* internal code for . */
  71. #define M_LEAVECURSOR    261        /* internal code for \= */
  72. #define M_ATCURSOR    262        /* internal code for \@ */
  73. #define M_SPLAT        263        /* internal code for * */
  74. #define M_PLUS        264        /* internal code for \+ */
  75. #define M_QMARK        265        /* internal code for \? */
  76. #define M_RANGE        266        /* internal code for \{ */
  77. #define M_CLASS(n)    (267+(n))    /* internal code for [] */
  78. #define M_START(n)    (277+(n))    /* internal code for \( */
  79. #define M_END(n)    (287+(n))    /* internal code for \) */
  80.  
  81. /* These are used during compilation */
  82. static int    class_cnt;    /* used to assign class IDs */
  83. static int    start_cnt;    /* used to assign start IDs */
  84. static int    end_stk[NSUBEXP];/* used to assign end IDs */
  85. static int    end_sp;
  86. static char    *retext;    /* points to the text being compiled */
  87.  
  88. /* error-handling stuff */
  89. jmp_buf    errorhandler;
  90. #define FAIL(why)    regerror(why); longjmp(errorhandler, 1)
  91.  
  92.  
  93.  
  94.  
  95.  
  96. /* This function builds a bitmap for a particular class */
  97. static char *makeclass(text, bmap)
  98.     REG char    *text;    /* start of the class */
  99.     REG char    *bmap;    /* the bitmap */
  100. {
  101.     REG int        i;
  102.     int        complement = 0;
  103.  
  104.  
  105.     checkmem();
  106.  
  107.     /* zero the bitmap */
  108.     for (i = 0; bmap && i < 32; i++)
  109.     {
  110.         bmap[i] = 0;
  111.     }
  112.  
  113.     /* see if we're going to complement this class */
  114.     if (*text == '^')
  115.     {
  116.         text++;
  117.         complement = 1;
  118.     }
  119.  
  120.     /* add in the characters */
  121.     while (*text && *text != ']')
  122.     {
  123.         /* is this a span of characters? */
  124.         if (text[1] == '-' && text[2])
  125.         {
  126.             /* spans can't be backwards */
  127.             if (text[0] > text[2])
  128.             {
  129.                 FAIL("Backwards span in []");
  130.             }
  131.  
  132.             /* add each character in the span to the bitmap */
  133.             for (i = UCHAR(text[0]); bmap && (unsigned)i <= UCHAR(text[2]); i++)
  134.             {
  135.                 bmap[i >> 3] |= (1 << (i & 7));
  136.             }
  137.  
  138.             /* move past this span */
  139.             text += 3;
  140.         }
  141.         else
  142.         {
  143.             /* add this single character to the span */
  144.             i = *text++;
  145.             if (bmap)
  146.             {
  147.                 bmap[UCHAR(i) >> 3] |= (1 << (UCHAR(i) & 7));
  148.             }
  149.         }
  150.     }
  151.  
  152.     /* make sure the closing ] is missing */
  153.     if (*text++ != ']')
  154.     {
  155.         FAIL("] missing");
  156.     }
  157.  
  158.     /* if we're supposed to complement this class, then do so */
  159.     if (complement && bmap)
  160.     {
  161.         for (i = 0; i < 32; i++)
  162.         {
  163.             bmap[i] = ~bmap[i];
  164.         }
  165.     }
  166.  
  167.     checkmem();
  168.  
  169.     return text;
  170. }
  171.  
  172.  
  173.  
  174.  
  175. /* This function gets the next character or meta character from a string.
  176.  * The pointer is incremented by 1, or by 2 for \-quoted characters.  For [],
  177.  * a bitmap is generated via makeclass() (if re is given), and the
  178.  * character-class text is skipped.
  179.  */
  180. static int gettoken(sptr, re)
  181.     char    **sptr;
  182.     regexp    *re;
  183. {
  184.     int    c;
  185.  
  186.     c = **sptr;
  187.     if (!c)
  188.     {
  189.         return c;
  190.     }
  191.     ++*sptr;
  192.     if (c == '\\')
  193.     {
  194.         c = **sptr;
  195.         ++*sptr;
  196.         switch (c)
  197.         {
  198.           case '<':
  199.             return M_BEGWORD;
  200.  
  201.           case '>':
  202.             return M_ENDWORD;
  203.  
  204.           case '(':
  205.             if (start_cnt >= NSUBEXP)
  206.             {
  207.                 FAIL("Too many \\(s");
  208.             }
  209.             end_stk[end_sp++] = start_cnt;
  210.             return M_START(start_cnt++);
  211.  
  212.           case ')':
  213.             if (end_sp <= 0)
  214.             {
  215.                 FAIL("Mismatched \\)");
  216.             }
  217.             return M_END(end_stk[--end_sp]);
  218.  
  219.           case '*':
  220.             return (*o_magic ? c : M_SPLAT);
  221.  
  222.           case '.':
  223.             return (*o_magic ? c : M_ANY);
  224.  
  225.           case '+':
  226.             return M_PLUS;
  227.  
  228.           case '?':
  229.             return M_QMARK;
  230. #ifndef CRUNCH
  231.           case '=':
  232.             return M_LEAVECURSOR;
  233.  
  234.           case '@':
  235.             return M_ATCURSOR;
  236.  
  237.           case '{':
  238.             return M_RANGE;
  239. #endif
  240.           default:
  241.             return c;
  242.         }
  243.     }
  244.     else if (*o_magic)
  245.     {
  246.         switch (c)
  247.         {
  248.           case '^':
  249.             if (*sptr == retext + 1)
  250.             {
  251.                 return M_BEGLINE;
  252.             }
  253.             return c;
  254.  
  255.           case '$':
  256.             if (!**sptr)
  257.             {
  258.                 return M_ENDLINE;
  259.             }
  260.             return c;
  261.  
  262.           case '.':
  263.             return M_ANY;
  264.  
  265.           case '*':
  266.             return M_SPLAT;
  267.  
  268.           case '[':
  269.             /* make sure we don't have too many classes */
  270.             if (class_cnt >= 10)
  271.             {
  272.                 FAIL("Too many []s");
  273.             }
  274.  
  275.             /* process the character list for this class */
  276.             if (re)
  277.             {
  278.                 /* generate the bitmap for this class */
  279.                 *sptr = makeclass(*sptr, re->program + 1 + 32 * class_cnt);
  280.             }
  281.             else
  282.             {
  283.                 /* skip to end of the class */
  284.                 *sptr = makeclass(*sptr, (char *)0);
  285.             }
  286.             return M_CLASS(class_cnt++);
  287.  
  288.           default:
  289.             return c;
  290.         }
  291.     }
  292.     else    /* unquoted nomagic */
  293.     {
  294.         switch (c)
  295.         {
  296.           case '^':
  297.             if (*sptr == retext + 1)
  298.             {
  299.                 return M_BEGLINE;
  300.             }
  301.             return c;
  302.  
  303.           case '$':
  304.             if (!**sptr)
  305.             {
  306.                 return M_ENDLINE;
  307.             }
  308.             return c;
  309.  
  310.           default:
  311.             return c;
  312.         }
  313.     }
  314.     /*NOTREACHED*/
  315. }
  316.  
  317.  
  318.  
  319.  
  320. /* This function calculates the number of bytes that will be needed for a
  321.  * compiled RE.  Its argument is the uncompiled version.  It is not clever
  322.  * about catching syntax errors; that is done in a later pass.
  323.  */
  324. static unsigned calcsize(text)
  325.     char        *text;
  326. {
  327.     unsigned    size;
  328.     int        token;
  329.     char        *tmp;
  330.  
  331.     retext = text;
  332.     class_cnt = 0;
  333.     start_cnt = 1;
  334.     end_sp = 0;
  335.     size = 5;
  336.     while ((token = gettoken(&text, (regexp *)0)) != 0)
  337.     {
  338.         if (IS_CLASS(token))
  339.         {
  340.             size += 34;
  341.         }
  342. #ifndef CRUNCH
  343.         else if (token == M_RANGE)
  344.         {
  345.             size += 4;
  346.             while ((token = gettoken(&text, (regexp *)0)) != 0
  347.                 && token != '}')
  348.             {
  349.             }
  350.             if (!token)
  351.             {
  352.                 return size;
  353.             }
  354.         }
  355.         else if (token == M_ATCURSOR)
  356.         {
  357.             tmp = get_cursor_word(cursor);
  358.             if (tmp)
  359.             {
  360.                 size += strlen(tmp);
  361.             }
  362.         }
  363. #endif
  364.         else if (IS_META(token))
  365.         {
  366.             size += 2;
  367.         }
  368.         else
  369.         {
  370.             size++;
  371.         }
  372.     }
  373.  
  374.     return size;
  375. }
  376.  
  377.  
  378.  
  379. /* This function compiles a regexp. */
  380. regexp *regcomp(exp)
  381.     char        *exp;
  382. {
  383.     int        needfirst;
  384.     unsigned    size;
  385.     int        token;
  386.     int        peek;
  387.     char        *build;
  388. #if __STDC__
  389. # ifndef linux
  390.     volatile
  391. # endif
  392. #endif
  393.     regexp        *re;
  394. #ifndef CRUNCH
  395.     int        from;
  396.     int        to;
  397.     int        digit;
  398.     char        *tmp;
  399. #endif
  400. #ifdef DEBUG
  401.     int        calced;
  402. #endif
  403.  
  404.  
  405.     checkmem();
  406.  
  407.     /* prepare for error handling */
  408.     re = (regexp *)0;
  409.     if (setjmp(errorhandler))
  410.     {
  411.         checkmem();
  412.         if (re)
  413.         {
  414.             _free_(re);
  415.         }
  416.         return (regexp *)0;
  417.     }
  418.  
  419.     /* if an empty regexp string was given, use the previous one */
  420.     if (*exp == 0)
  421.     {
  422.         if (!previous)
  423.         {
  424.             FAIL("No previous RE");
  425.         }
  426.         exp = previous;
  427.     }
  428.     else /* non-empty regexp given, so remember it */
  429.     {
  430.         if (previous)
  431.             _free_(previous);
  432.         previous = (char *)malloc((unsigned)(strlen(exp) + 1));
  433.         if (previous)
  434.             strcpy(previous, exp);
  435.     }
  436.  
  437.     /* allocate memory */
  438.     checkmem();
  439.     class_cnt = 0;
  440.     start_cnt = 1;
  441.     end_sp = 0;
  442.     retext = exp;
  443. #ifdef DEBUG
  444.     calced = calcsize(exp);
  445.     size = calced + sizeof(regexp);
  446. #else
  447.     size = calcsize(exp) + sizeof(regexp) + 10; /* !!! 10 bytes for slop */
  448. #endif
  449. #ifdef lint
  450.     re = (regexp *)0;
  451. #else
  452.     re = (regexp *)malloc((unsigned)size);
  453. #endif
  454.     if (!re)
  455.     {
  456.         FAIL("Not enough memory for this RE");
  457.     }
  458.     checkmem();
  459.  
  460.     /* compile it */
  461.     build = &re->program[1 + 32 * class_cnt];
  462.     re->program[0] = class_cnt;
  463.     for (token = 0; token < NSUBEXP; token++)
  464.     {
  465.         re->startp[token] = re->endp[token] = (char *)0;
  466.     }
  467.     re->leavep = (char *)0;
  468.     re->first = 0;
  469.     re->bol = 0;
  470.     re->minlen = 0;
  471.     needfirst = 1;
  472.     class_cnt = 0;
  473.     start_cnt = 1;
  474.     end_sp = 0;
  475.     retext = exp;
  476.     for (token = M_START(0), peek = gettoken(&exp, re);
  477.          token;
  478.          token = peek, peek = gettoken(&exp, re))
  479.     {
  480.         /* special processing for the closure operator */
  481.         if (IS_CLOSURE(peek))
  482.         {
  483.             /* detect misuse of closure operator */
  484.             if (IS_START(token))
  485.             {
  486.                 FAIL("Closure operator follows nothing");
  487.             }
  488.             else if (IS_META(token) && token != M_ANY && !IS_CLASS(token))
  489.             {
  490.                 FAIL("Closure operators can only follow a normal character or . or []");
  491.             }
  492.  
  493. #ifndef CRUNCH
  494.             /* if \{ \} then read the range */
  495.             if (peek == M_RANGE)
  496.             {
  497.                 from = 0;
  498.                 for (digit = gettoken(&exp, re);
  499.                      !IS_META(digit) && isdigit(digit);
  500.                      digit = gettoken(&exp, re))
  501.                 {
  502.                     from = from * 10 + digit - '0';
  503.                 }
  504.                 if (digit == '}')
  505.                 {
  506.                     to = from;
  507.                 }
  508.                 else if (digit == ',')
  509.                 {
  510.                     to = 0;
  511.                     for (digit = gettoken(&exp, re);
  512.                          !IS_META(digit) && isdigit(digit);
  513.                          digit = gettoken(&exp, re))
  514.                     {
  515.                         to = to * 10 + digit - '0';
  516.                     }
  517.                     if (to == 0)
  518.                     {
  519.                         to = 255;
  520.                     }
  521.                 }
  522.                 if (digit != '}')
  523.                 {
  524.                     FAIL("Bad characters after \\{");
  525.                 }
  526.                 else if (to < from || to == 0 || from >= 255)
  527.                 {
  528.                     FAIL("Invalid range for \\{ \\}");
  529.                 }
  530.                 re->minlen += from;
  531.             }
  532.             else
  533. #endif
  534.             if (peek != M_SPLAT)
  535.             {
  536.                 re->minlen++;
  537.             }
  538.  
  539.             /* it is okay -- make it prefix instead of postfix */
  540.             ADD_META(build, peek);
  541. #ifndef CRUNCH
  542.             if (peek == M_RANGE)
  543.             {
  544.                 *build++ = from;
  545.                 *build++ = (to < 255 ? to : 255);
  546.             }
  547. #endif
  548.             
  549.  
  550.             /* take care of "needfirst" - is this the first char? */
  551.             if (needfirst && peek == M_PLUS && !IS_META(token))
  552.             {
  553.                 re->first = token;
  554.             }
  555.             needfirst = 0;
  556.  
  557.             /* we used "peek" -- need to refill it */
  558.             peek = gettoken(&exp, re);
  559.             if (IS_CLOSURE(peek))
  560.             {
  561.                 FAIL("* or \\+ or \\? doubled up");
  562.             }
  563.         }
  564.         else if (!IS_META(token))
  565.         {
  566.             /* normal char is NOT argument of closure */
  567.             if (needfirst)
  568.             {
  569.                 re->first = token;
  570.                 needfirst = 0;
  571.             }
  572.             re->minlen++;
  573.         }
  574.         else if (token == M_ANY || IS_CLASS(token))
  575.         {
  576.             /* . or [] is NOT argument of closure */
  577.             needfirst = 0;
  578.             re->minlen++;
  579.         }
  580.  
  581.         /* the "token" character is not closure -- process it normally */
  582.         if (token == M_BEGLINE)
  583.         {
  584.             /* set the BOL flag instead of storing M_BEGLINE */
  585.             re->bol = 1;
  586.         }
  587. #ifndef CRUNCH
  588.         else if (token == M_ATCURSOR)
  589.         {
  590.             tmp = get_cursor_word(cursor);
  591.             if (!tmp)
  592.             {
  593.                 FAIL("cursor not on word");
  594.             }
  595.             while (*tmp)
  596.             {
  597.                 *build++ = *tmp++;
  598.             }
  599.         }
  600. #endif
  601.         else if (IS_META(token))
  602.         {
  603.             ADD_META(build, token);
  604.         }
  605.         else
  606.         {
  607.             *build++ = token;
  608.         }
  609.     }
  610.     checkmem();
  611.  
  612.     /* end it with a \) which MUST MATCH the opening \( */
  613.     ADD_META(build, M_END(0));
  614.     if (end_sp > 0)
  615.     {
  616.         FAIL("Not enough \\)s");
  617.     }
  618.  
  619. #ifdef DEBUG
  620.     if ((int)(build - re->program) != calced)
  621.     {
  622.         msg("regcomp error: calced=%d, actual=%d", calced, (int)(build - re->program));
  623.         getkey(0);
  624.     }
  625. #endif
  626.  
  627.     checkmem();
  628.     return (regexp *)re; /* type cast is just to discard "volatile" */
  629. }
  630.  
  631.  
  632.  
  633. /*---------------------------------------------------------------------------*/
  634.  
  635.  
  636. /* This function checks for a match between a character and a token which is
  637.  * known to represent a single character.  It returns 0 if they match, or
  638.  * 1 if they don't.
  639.  */
  640. int match1(re, ch, token)
  641.     regexp        *re;
  642.     REG char    ch;
  643.     REG int        token;
  644. {
  645.     if (!ch)
  646.     {
  647.         /* the end of a line can't match any RE of width 1 */
  648.         return 1;
  649.     }
  650.     if (token == M_ANY)
  651.     {
  652.         return 0;
  653.     }
  654.     else if (IS_CLASS(token))
  655.     {
  656.         if (re->program[1 + 32 * (token - M_CLASS(0)) + (UCHAR(ch) >> 3)] & (1 << (UCHAR(ch) & 7)))
  657.             return 0;
  658.     }
  659.     else if (ch == token || *o_ignorecase && tolower(ch) == tolower(token))
  660.     {
  661.         return 0;
  662.     }
  663.     return 1;
  664. }
  665.  
  666.  
  667.  
  668. /* This function checks characters up to and including the next closure, at
  669.  * which point it does a recursive call to check the rest of it.  This function
  670.  * returns 0 if everything matches, or 1 if something doesn't match.
  671.  */
  672. int match(re, str, prog, here, bol)
  673.     regexp        *re;    /* the regular expression */
  674.     char        *str;    /* the string */
  675.     REG char    *prog;    /* a portion of re->program, an compiled RE */
  676.     REG char    *here;    /* a portion of str, the string to compare it to */
  677.     int        bol;    /* boolean: is "str" the beginning of the line? */
  678. {
  679.     REG int        token;    /* the roken pointed to by prog */
  680.     REG int        nmatched;/* counter, used during closure matching */ 
  681.     REG int        closure;/* the token denoting the type of closure */
  682.     int        from;    /* minimum number of matches in closure */
  683.     int        to;    /* maximum number of matches in closure */
  684.  
  685.     for (token = GET_META(prog); !IS_CLOSURE(token); prog++, token = GET_META(prog))
  686.     {
  687.         switch (token)
  688.         {
  689.         /*case M_BEGLINE: can't happen; re->bol is used instead */
  690.           case M_ENDLINE:
  691.             if (*here)
  692.                 return 1;
  693.             break;
  694.  
  695.           case M_BEGWORD:
  696.             if ((!bol || here != str) &&
  697.                (here[-1] == '_' || isalnum(here[-1])))
  698.                 return 1;
  699.             break;
  700.  
  701.           case M_ENDWORD:
  702.             if (here[0] == '_' || isalnum(here[0]))
  703.                 return 1;
  704.             break;
  705.  
  706.           case M_LEAVECURSOR:
  707.             re->leavep = (char *)here;
  708.             break;
  709.  
  710.           case M_START(0):
  711.           case M_START(1):
  712.           case M_START(2):
  713.           case M_START(3):
  714.           case M_START(4):
  715.           case M_START(5):
  716.           case M_START(6):
  717.           case M_START(7):
  718.           case M_START(8):
  719.           case M_START(9):
  720.             re->startp[token - M_START(0)] = (char *)here;
  721.             break;
  722.  
  723.           case M_END(0):
  724.           case M_END(1):
  725.           case M_END(2):
  726.           case M_END(3):
  727.           case M_END(4):
  728.           case M_END(5):
  729.           case M_END(6):
  730.           case M_END(7):
  731.           case M_END(8):
  732.           case M_END(9):
  733.             re->endp[token - M_END(0)] = (char *)here;
  734.             if (token == M_END(0))
  735.             {
  736.                 return 0;
  737.             }
  738.             break;
  739.  
  740.           default: /* literal, M_CLASS(n), or M_ANY */
  741.             if (match1(re, *here, token) != 0)
  742.                 return 1;
  743.             here++;
  744.         }
  745.     }
  746.  
  747.     /* C L O S U R E */
  748.  
  749.     /* step 1: see what we have to match against, and move "prog" to point
  750.      * to the remainder of the compiled RE.
  751.      */
  752.     closure = token;
  753.     prog++;
  754.     switch (closure)
  755.     {
  756.       case M_SPLAT:
  757.         from = 0;
  758.         to = strlen(str);    /* infinity */
  759.         break;
  760.  
  761.       case M_PLUS:
  762.         from = 1;
  763.         to = strlen(str);    /* infinity */
  764.         break;
  765.  
  766.       case M_QMARK:
  767.         from = 0;
  768.         to = 1;
  769.         break;
  770.  
  771. #ifndef CRUNCH
  772.       case M_RANGE:
  773.         from = UCHAR(*prog++);
  774.         to = UCHAR(*prog++);
  775.         if (to == 255)
  776.         {
  777.             to = strlen(str); /* infinity */
  778.         }
  779.         break;
  780. #endif
  781.     }
  782.     token = GET_META(prog);
  783.     prog++;
  784.  
  785.     /* step 2: see how many times we can match that token against the string */
  786.     for (nmatched = 0;
  787.          nmatched < to && *here && match1(re, *here, token) == 0;
  788.          nmatched++, here++)
  789.     {
  790.     }
  791.  
  792.     /* step 3: try to match the remainder, and back off if it doesn't */
  793.     while (nmatched >= from && match(re, str, prog, here, FALSE) != 0)
  794.     {
  795.         nmatched--;
  796.         here--;
  797.     }
  798.  
  799.     /* so how did it work out? */
  800.     if (nmatched >= from)
  801.         return 0;
  802.     return 1;
  803. }
  804.  
  805.  
  806.  
  807. /* This function searches through a string for text that matches an RE. */
  808. int regexec(re, str, bol)
  809.     regexp    *re;    /* the compiled regexp to search for */
  810.     char    *str;    /* the string to search through */
  811.     int    bol;    /* boolean: does str start at the beginning of a line? */
  812. {
  813.     char    *prog;    /* the entry point of re->program */
  814.     int    len;    /* length of the string */
  815.     REG char    *here;
  816.  
  817.     checkmem();
  818.  
  819.     /* if must start at the beginning of a line, and this isn't, then fail */
  820.     if (re->bol && !bol)
  821.     {
  822.         return 0;
  823.     }
  824.  
  825.     len = strlen(str);
  826.     prog = re->program + 1 + 32 * re->program[0];
  827.  
  828.     /* search for the RE in the string */
  829.     if (re->bol)
  830.     {
  831.         /* must occur at BOL */
  832.         if ((re->first
  833.             && match1(re, *(char *)str, re->first))/* wrong first letter? */
  834.          || len < re->minlen            /* not long enough? */
  835.          || match(re, (char *)str, prog, str, bol))    /* doesn't match? */
  836.             return 0;            /* THEN FAIL! */
  837.     }
  838. #ifndef CRUNCH
  839.     else if (!*o_ignorecase)
  840.     {
  841.         /* can occur anywhere in the line, noignorecase */
  842.         for (here = (char *)str;
  843.              (re->first && re->first != *here)
  844.             || match(re, (char *)str, prog, here, bol);
  845.              here++, len--, bol = FALSE)
  846.         {
  847.             if (len < re->minlen)
  848.                 return 0;
  849.         }
  850.     }
  851. #endif
  852.     else
  853.     {
  854.         /* can occur anywhere in the line, ignorecase */
  855.         for (here = (char *)str;
  856.              (re->first && match1(re, *here, (int)re->first))
  857.             || match(re, (char *)str, prog, here, bol);
  858.              here++, len--, bol = FALSE)
  859.         {
  860.             if (len < re->minlen)
  861.                 return 0;
  862.         }
  863.     }
  864.  
  865.     /* if we didn't fail, then we must have succeeded */
  866.     checkmem();
  867.     return 1;
  868. }
  869.  
  870. /*============================================================================*/
  871. #else /* NO_MAGIC */
  872.  
  873. regexp *regcomp(exp)
  874.     char    *exp;
  875. {
  876.     char    *src;
  877.     char    *dest;
  878.     regexp    *re;
  879.     int    i;
  880.  
  881.     /* allocate a big enough regexp structure */
  882. #ifdef lint
  883.     re = (regexp *)0;
  884. #else
  885.     re = (regexp *)malloc((unsigned)(strlen(exp) + 1 + sizeof(struct regexp)));
  886. #endif
  887.     if (!re)
  888.     {
  889.         regerror("Could not malloc a regexp structure");
  890.         return (regexp *)0;
  891.     }
  892.  
  893.     /* initialize all fields of the structure */
  894.     for (i = 0; i < NSUBEXP; i++)
  895.     {
  896.         re->startp[i] = re->endp[i] = (char *)0;
  897.     }
  898.     re->leavep = (char *)0;
  899.     re->minlen = 0;
  900.     re->first = 0;
  901.     re->bol = 0;
  902.  
  903.     /* copy the string into it, translating ^ and $ as needed */
  904.     for (src = exp, dest = re->program + 1; *src; src++)
  905.     {
  906.         switch (*src)
  907.         {
  908.           case '^':
  909.             if (src == exp)
  910.             {
  911.                 re->bol += 1;
  912.             }
  913.             else
  914.             {
  915.                 *dest++ = '^';
  916.                 re->minlen++;
  917.             }
  918.             break;
  919.  
  920.           case '$':
  921.             if (!src[1])
  922.             {
  923.                 re->bol += 2;
  924.             }
  925.             else
  926.             {
  927.                 *dest++ = '$';
  928.                 re->minlen++;
  929.             }
  930.             break;
  931.  
  932.           case '\\':
  933.             if (src[1])
  934.             {
  935.                 *dest++ = *++src;
  936.                 re->minlen++;
  937.             }
  938.             else
  939.             {
  940.                 regerror("extra \\ at end of regular expression");
  941.             }
  942.             break;
  943.  
  944.           default:
  945.             *dest++ = *src;
  946.             re->minlen++;
  947.         }
  948.     }
  949.     *dest = '\0';
  950.  
  951.     return re;
  952. }
  953.  
  954.  
  955. /* This "helper" function checks for a match at a given location.  It returns
  956.  * 1 if it matches, 0 if it doesn't match here but might match later on in the
  957.  * string, or -1 if it could not possibly match
  958.  */
  959. static int reghelp(prog, string, bolflag)
  960.     struct regexp    *prog;
  961.     char        *string;
  962.     int        bolflag;
  963. {
  964.     char        *scan;
  965.     char        *str;
  966.  
  967.     /* if ^, then require bolflag */
  968.     if ((prog->bol & 1) && !bolflag)
  969.     {
  970.         return -1;
  971.     }
  972.  
  973.     /* if it matches, then it will start here */
  974.     prog->startp[0] = string;
  975.  
  976.     /* compare, possibly ignoring case */
  977.     if (*o_ignorecase)
  978.     {
  979.         for (scan = &prog->program[1]; *scan; scan++, string++)
  980.             if (tolower(*scan) != tolower(*string))
  981.                 return *string ? 0 : -1;
  982.     }
  983.     else
  984.     {
  985.         for (scan = &prog->program[1]; *scan; scan++, string++)
  986.             if (*scan != *string)
  987.                 return *string ? 0 : -1;
  988.     }
  989.  
  990.     /* if $, then require string to end here, too */
  991.     if ((prog->bol & 2) && *string)
  992.     {
  993.         return 0;
  994.     }
  995.  
  996.     /* if we get to here, it matches */
  997.     prog->endp[0] = string;
  998.     return 1;
  999. }
  1000.  
  1001.  
  1002.  
  1003. int regexec(prog, string, bolflag)
  1004.     struct regexp    *prog;
  1005.     char        *string;
  1006.     int        bolflag;
  1007. {
  1008.     int        rc;
  1009.  
  1010.     /* keep trying to match it */
  1011.     for (rc = reghelp(prog, string, bolflag); rc == 0; rc = reghelp(prog, string, 0))
  1012.     {
  1013.         string++;
  1014.     }
  1015.  
  1016.     /* did we match? */
  1017.     return rc == 1;
  1018. }
  1019. #endif
  1020.