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