home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume23 / trn / part10 / search.c < prev    next >
C/C++ Source or Header  |  1991-08-22  |  13KB  |  610 lines
  1. /* $Header: search.c,v 4.3.2.2 90/03/22 23:05:31 sob Exp $
  2.  *
  3.  * $Log:    search.c,v $
  4.  * Revision 4.3.2.2  90/03/22  23:05:31  sob
  5.  * Fixes provided by Wayne Davison <drivax!davison>
  6.  * 
  7.  * Revision 4.3.2.1  90/03/17  17:46:29  sob
  8.  * Added changes to insure that null search strings won't result in core dumps
  9.  * on non-VAX computers.
  10.  * 
  11.  * Revision 4.3  85/05/01  11:50:16  lwall
  12.  * Baseline for release with 4.3bsd.
  13.  * 
  14.  */
  15.  
  16. /* string search routines */
  17.  
  18. /*        Copyright (c) 1981,1980 James Gosling        */
  19.  
  20. /* Modified Aug. 12, 1981 by Tom London to include regular expressions
  21.    as in ed.  RE stuff hacked over by jag to correct a few major problems,
  22.    mainly dealing with searching within the buffer rather than copying
  23.    each line to a separate array.  Newlines can now appear in RE's */
  24.  
  25. /* Ripped to shreds and glued back together to make a search package,
  26.  * July 6, 1984, by Larry Wall. (If it doesn't work, it's probably my fault.)
  27.  * Changes include:
  28.  *    Buffer, window, and mlisp stuff gone.
  29.  *    Translation tables reduced to 1 table.
  30.  *    Expression buffer is now dynamically allocated.
  31.  *    Character classes now implemented with a bitmap.
  32.  */
  33.  
  34. #include "EXTERN.h"
  35. #include "common.h"
  36. #include "util.h"
  37. #include "INTERN.h"
  38. #include "search.h"
  39.  
  40. #ifndef BITSPERBYTE
  41. #define BITSPERBYTE 8
  42. #endif
  43.  
  44. #define BMAPSIZ (127 / BITSPERBYTE + 1)
  45.  
  46. /* meta characters in the "compiled" form of a regular expression */
  47. #define    CBRA    2        /* \( -- begin bracket */
  48. #define    CCHR    4        /* a vanilla character */
  49. #define    CDOT    6        /* . -- match anything except a newline */
  50. #define    CCL    8        /* [...] -- character class */
  51. #define    NCCL    10        /* [^...] -- negated character class */
  52. #define    CDOL    12        /* $ -- matches the end of a line */
  53. #define    CEND    14        /* The end of the pattern */
  54. #define    CKET    16        /* \) -- close bracket */
  55. #define    CBACK    18        /* \N -- backreference to the Nth bracketed
  56.                    string */
  57. #define CIRC    20        /* ^ matches the beginning of a line */
  58.  
  59. #define WORD    32        /* matches word character \w */
  60. #define NWORD    34        /* matches non-word characer \W */
  61. #define WBOUND    36        /* matches word boundary \b */
  62. #define NWBOUND    38        /* matches non-(word boundary) \B */
  63.  
  64. #define    STAR    01        /* * -- Kleene star, repeats the previous
  65.                    REas many times as possible; the value
  66.                    ORs with the other operator types */
  67.  
  68. #define ASCSIZ 0200
  69. typedef char    TRANSTABLE[ASCSIZ];
  70.  
  71. static    TRANSTABLE trans = {
  72. 0000,0001,0002,0003,0004,0005,0006,0007,
  73. 0010,0011,0012,0013,0014,0015,0016,0017,
  74. 0020,0021,0022,0023,0024,0025,0026,0027,
  75. 0030,0031,0032,0033,0034,0035,0036,0037,
  76. 0040,0041,0042,0043,0044,0045,0046,0047,
  77. 0050,0051,0052,0053,0054,0055,0056,0057,
  78. 0060,0061,0062,0063,0064,0065,0066,0067,
  79. 0070,0071,0072,0073,0074,0075,0076,0077,
  80. 0100,0101,0102,0103,0104,0105,0106,0107,
  81. 0110,0111,0112,0113,0114,0115,0116,0117,
  82. 0120,0121,0122,0123,0124,0125,0126,0127,
  83. 0130,0131,0132,0133,0134,0135,0136,0137,
  84. 0140,0141,0142,0143,0144,0145,0146,0147,
  85. 0150,0151,0152,0153,0154,0155,0156,0157,
  86. 0160,0161,0162,0163,0164,0165,0166,0167,
  87. 0170,0171,0172,0173,0174,0175,0176,0177,
  88. };
  89. static bool folding = FALSE;
  90.  
  91. static int err;
  92. static char *FirstCharacter;
  93.  
  94. void
  95. search_init()
  96. {
  97. #ifdef UNDEF
  98.     register int    i;
  99.     
  100.     for (i = 0; i < ASCSIZ; i++)
  101.     trans[i] = i;
  102. #else
  103.     ;
  104. #endif
  105. }
  106.  
  107. void
  108. init_compex(compex)
  109. register COMPEX *compex;
  110. {
  111.     /* the following must start off zeroed */
  112.  
  113.     compex->eblen = 0;
  114.     compex->brastr = Nullch;
  115. }
  116.  
  117. void
  118. free_compex(compex)
  119. register COMPEX *compex;
  120. {
  121.     if (compex->eblen) {
  122.     free(compex->expbuf);
  123.     compex->eblen = 0;
  124.     }
  125.     if (compex->brastr) {
  126.     free(compex->brastr);
  127.     compex->brastr = Nullch;
  128.     }
  129. }
  130.  
  131. static char *gbr_str = Nullch;
  132. static int gbr_siz = 0;
  133.  
  134. char *
  135. getbracket(compex,n)
  136. register COMPEX *compex;
  137. int n;
  138. {
  139.     int length = compex->braelist[n] - compex->braslist[n];
  140.  
  141.     if (!compex->nbra || n > compex->nbra || !compex->braelist[n] || length<0)
  142.     return nullstr;
  143.     growstr(&gbr_str, &gbr_siz, length+1);
  144.     safecpy(gbr_str, compex->braslist[n], length+1);
  145.     return gbr_str;
  146. }
  147.  
  148. void
  149. case_fold(which)
  150. int which;
  151. {
  152.     register int i;
  153.  
  154.     if (which != folding) {
  155.     if (which) {
  156.         for (i = 'A'; i <= 'Z'; i++)
  157.         trans[i] = tolower(i);
  158.     }
  159.     else {
  160.         for (i = 'A'; i <= 'Z'; i++)
  161.         trans[i] = i;
  162.     }
  163.     folding = which;
  164.     }
  165. }
  166.  
  167. /* Compile the given regular expression into a [secret] internal format */
  168.  
  169. char *
  170. compile (compex, strp, RE, fold)
  171. register COMPEX *compex;
  172. register char   *strp;
  173. int RE;
  174. int fold;
  175. {
  176.     register int c;
  177.     register char  *ep;
  178.     char   *lastep;
  179.     char    bracket[NBRA],
  180.        *bracketp;
  181.     char **alt = compex->alternatives;
  182.     char *retmes = "Badly formed search string";
  183.  
  184.     case_fold(compex->do_folding = fold);
  185.     if (!compex->eblen) {
  186.     compex->expbuf = safemalloc(84);
  187.     compex->eblen = 80;
  188.     }
  189.     ep = compex->expbuf;        /* point at expression buffer */
  190.     *alt++ = ep;            /* first alternative starts here */
  191.     bracketp = bracket;            /* first bracket goes here */
  192.     if (*strp == 0) {            /* nothing to compile? */
  193.     if (*ep == 0)            /* nothing there yet? */
  194.         return "Null search string";
  195.     return Nullch;            /* just keep old expression */
  196.     }
  197.     compex->nbra = 0;            /* no brackets yet */
  198.     lastep = 0;
  199.     for (;;) {
  200.     if (ep - compex->expbuf >= compex->eblen)
  201.         grow_eb(compex);
  202.     c = *strp++;            /* fetch next char of pattern */
  203.     if (c == 0) {            /* end of pattern? */
  204.         if (bracketp != bracket) {    /* balanced brackets? */
  205. #ifdef VERBOSE
  206.         retmes = "Unbalanced parens";
  207. #endif
  208.         goto cerror;
  209.         }
  210.         *ep++ = CEND;        /* terminate expression */
  211.         *alt++ = 0;            /* terminal alternative list */
  212.         /*
  213.         compex->eblen = ep - compex->expbuf + 1;
  214.         compex->expbuf = saferealloc(compex->expbuf,compex->eblen+4); */
  215.         return Nullch;        /* return success */
  216.     }
  217.     if (c != '*')
  218.         lastep = ep;
  219.     if (!RE) {            /* just a normal search string? */
  220.         *ep++ = CCHR;        /* everything is a normal char */
  221.         *ep++ = c;
  222.     }
  223.     else                /* it is a regular expression */
  224.         switch (c) {
  225.  
  226.         case '\\':        /* meta something */
  227.             switch (c = *strp++) {
  228.             case '(':
  229.             if (compex->nbra >= NBRA) {
  230. #ifdef VERBOSE
  231.                 retmes = "Too many parens";
  232. #endif
  233.                 goto cerror;
  234.             }
  235.             *bracketp++ = ++compex->nbra;
  236.             *ep++ = CBRA;
  237.             *ep++ = compex->nbra;
  238.             break;
  239.             case '|':
  240.             if (bracketp>bracket) {
  241. #ifdef VERBOSE
  242.                 retmes = "No \\| in parens";    /* Alas! */
  243. #endif
  244.                 goto cerror;
  245.             }
  246.             *ep++ = CEND;
  247.             *alt++ = ep;
  248.             break;
  249.             case ')':
  250.             if (bracketp <= bracket) {
  251. #ifdef VERBOSE
  252.                 retmes = "Unmatched right paren";
  253. #endif
  254.                 goto cerror;
  255.             }
  256.             *ep++ = CKET;
  257.             *ep++ = *--bracketp;
  258.             break;
  259.             case 'w':
  260.             *ep++ = WORD;
  261.             break;
  262.             case 'W':
  263.             *ep++ = NWORD;
  264.             break;
  265.             case 'b':
  266.             *ep++ = WBOUND;
  267.             break;
  268.             case 'B':
  269.             *ep++ = NWBOUND;
  270.             break;
  271.             case '0': case '1': case '2': case '3': case '4':
  272.             case '5': case '6': case '7': case '8': case '9':
  273.             *ep++ = CBACK;
  274.             *ep++ = c - '0';
  275.             break;
  276.             default:
  277.             *ep++ = CCHR;
  278.             if (c == '\0')
  279.                 goto cerror;
  280.             *ep++ = c;
  281.             break;
  282.             }
  283.             break;
  284.         case '.':
  285.             *ep++ = CDOT;
  286.             continue;
  287.  
  288.         case '*':
  289.             if (lastep == 0 || *lastep == CBRA || *lastep == CKET
  290.             || *lastep == CIRC
  291.             || (*lastep&STAR)|| *lastep>NWORD)
  292.             goto defchar;
  293.             *lastep |= STAR;
  294.             continue;
  295.  
  296.         case '^':
  297.             if (ep != compex->expbuf && ep[-1] != CEND)
  298.             goto defchar;
  299.             *ep++ = CIRC;
  300.             continue;
  301.  
  302.         case '$':
  303.             if (*strp != 0 && (*strp != '\\' || strp[1] != '|'))
  304.             goto defchar;
  305.             *ep++ = CDOL;
  306.             continue;
  307.  
  308.         case '[': {        /* character class */
  309.             register int i;
  310.             
  311.             if (ep - compex->expbuf >= compex->eblen - BMAPSIZ)
  312.             grow_eb(compex);    /* reserve bitmap */
  313.             for (i = BMAPSIZ; i; --i)
  314.             ep[i] = 0;
  315.             
  316.             if ((c = *strp++) == '^') {
  317.             c = *strp++;
  318.             *ep++ = NCCL;    /* negated */
  319.             }
  320.             else
  321.             *ep++ = CCL;    /* normal */
  322.             
  323.             i = 0;        /* remember oldchar */
  324.             do {
  325.             if (c == '\0') {
  326. #ifdef VERBOSE
  327.                 retmes = "Missing ]";
  328. #endif
  329.                 goto cerror;
  330.             }
  331.             if (*strp == '-' && *(++strp))
  332.                 i = *strp++;
  333.             else
  334.                 i = c;
  335.             while (c <= i) {
  336.                 ep[c / BITSPERBYTE] |= 1 << (c % BITSPERBYTE);
  337.                 if (fold && isalpha(c))
  338.                 ep[(c ^ 32) / BITSPERBYTE] |=
  339.                     1 << ((c ^ 32) % BITSPERBYTE);
  340.                     /* set the other bit too */
  341.                 c++;
  342.             }
  343.             } while ((c = *strp++) != ']');
  344.             ep += BMAPSIZ;
  345.             continue;
  346.         }
  347.  
  348.         defchar:
  349.         default:
  350.             *ep++ = CCHR;
  351.             *ep++ = c;
  352.         }
  353.     }
  354. cerror:
  355.     compex->expbuf[0] = 0;
  356.     compex->nbra = 0;
  357.     return retmes;
  358. }
  359.  
  360. void
  361. grow_eb(compex)
  362. register COMPEX *compex;
  363. {
  364.     compex->eblen += 80;
  365.     compex->expbuf = saferealloc(compex->expbuf, (MEM_SIZE)compex->eblen + 4);
  366. }
  367.  
  368. char *
  369. execute (compex, addr)
  370. register COMPEX *compex;
  371. char *addr;
  372. {
  373.     register char *p1 = addr;
  374.     register char *trt = trans;
  375.     register int c;
  376.  
  377.     if (addr == Nullch || compex->expbuf == Nullch)
  378.     return Nullch;
  379.     if (compex->nbra) {            /* any brackets? */
  380.     for (c = 0; c <= compex->nbra; c++)
  381.         compex->braslist[c] = compex->braelist[c] = Nullch;
  382.     if (compex->brastr)
  383.         free(compex->brastr);
  384.     compex->brastr = savestr(p1);    /* in case p1 is not static */
  385.     p1 = compex->brastr;        /* ! */
  386.     }
  387.     case_fold(compex->do_folding);    /* make sure table is correct */
  388.     FirstCharacter = p1;        /* for ^ tests */
  389.     if (compex->expbuf[0] == CCHR && !compex->alternatives[1]) {
  390.     c = trt[compex->expbuf[1]];    /* fast check for first character */
  391.     do {
  392.         if (trt[*p1] == c && advance (compex, p1, compex->expbuf))
  393.         return p1;
  394.         p1++;
  395.     } while (*p1 && !err);
  396.     return Nullch;
  397.     }
  398.     else {            /* regular algorithm */
  399.     do {
  400.         register char **alt = compex->alternatives;
  401.         while (*alt) {
  402.         if (advance (compex, p1, *alt++))
  403.             return p1;
  404.         }
  405.         p1++;
  406.     } while (*p1 && !err);
  407.     return Nullch;
  408.     }
  409. }
  410.  
  411. /* advance the match of the regular expression starting at ep along the
  412.    string lp, simulates an NDFSA */
  413. bool
  414. advance (compex, lp, ep)
  415. register COMPEX *compex;
  416. register char *ep;
  417. register char *lp;
  418. {
  419.     register char *curlp;
  420.     register char *trt = trans;
  421.     register int i;
  422.  
  423.     while ((*ep & STAR) || *lp || *ep == CIRC || *ep == CKET)
  424.     switch (*ep++) {
  425.  
  426.         case CCHR:
  427.         if (trt[*ep++] != trt[*lp]) return FALSE;
  428.         lp++;
  429.         continue;
  430.  
  431.         case CDOT:
  432.         if (*lp == '\n') return FALSE;
  433.         lp++;
  434.         continue;
  435.  
  436.         case CDOL:
  437.         if (!*lp || *lp == '\n')
  438.             continue;
  439.         return FALSE;
  440.  
  441.         case CIRC:
  442.         if (lp == FirstCharacter || lp[-1]=='\n')
  443.             continue;
  444.         return FALSE;
  445.  
  446.         case WORD:
  447.         if (isalnum(*lp)) {
  448.             lp++;
  449.             continue;
  450.         }
  451.         return FALSE;
  452.  
  453.         case NWORD:
  454.         if (!isalnum(*lp)) {
  455.             lp++;
  456.             continue;
  457.         }
  458.         return FALSE;
  459.  
  460.         case WBOUND:
  461.         if ((lp == FirstCharacter || !isalnum(lp[-1])) !=
  462.             (!*lp || !isalnum(*lp)) )
  463.             continue;
  464.         return FALSE;
  465.  
  466.         case NWBOUND:
  467.         if ((lp == FirstCharacter || !isalnum(lp[-1])) ==
  468.             (!*lp || !isalnum(*lp)))
  469.             continue;
  470.         return FALSE;
  471.  
  472.         case CEND:
  473.         return TRUE;
  474.  
  475.         case CCL:
  476.         if (cclass (ep, *lp, 1)) {
  477.             ep += BMAPSIZ;
  478.             lp++;
  479.             continue;
  480.         }
  481.         return FALSE;
  482.  
  483.         case NCCL:
  484.         if (cclass (ep, *lp, 0)) {
  485.             ep += BMAPSIZ;
  486.             lp++;
  487.             continue;
  488.         }
  489.         return FALSE;
  490.  
  491.         case CBRA:
  492.         compex->braslist[*ep++] = lp;
  493.         continue;
  494.  
  495.         case CKET:
  496.         i = *ep++;
  497.         compex->braelist[i] = lp;
  498.         compex->braelist[0] = lp;
  499.         compex->braslist[0] = compex->braslist[i];
  500.         continue;
  501.  
  502.         case CBACK:
  503.         if (compex->braelist[i = *ep++] == 0) {
  504.             fputs("bad braces\n",stdout) FLUSH;
  505.             err = TRUE;
  506.             return FALSE;
  507.         }
  508.         if (backref (compex, i, lp)) {
  509.             lp += compex->braelist[i] - compex->braslist[i];
  510.             continue;
  511.         }
  512.         return FALSE;
  513.  
  514.         case CBACK | STAR:
  515.         if (compex->braelist[i = *ep++] == 0) {
  516.             fputs("bad braces\n",stdout) FLUSH;
  517.             err = TRUE;
  518.             return FALSE;
  519.         }
  520.         curlp = lp;
  521.         while (backref (compex, i, lp)) {
  522.             lp += compex->braelist[i] - compex->braslist[i];
  523.         }
  524.         while (lp >= curlp) {
  525.             if (advance (compex, lp, ep))
  526.             return TRUE;
  527.             lp -= compex->braelist[i] - compex->braslist[i];
  528.         }
  529.         continue;
  530.  
  531.         case CDOT | STAR:
  532.         curlp = lp;
  533.         while (*lp++ && lp[-1] != '\n');
  534.         goto star;
  535.  
  536.         case WORD | STAR:
  537.         curlp = lp;
  538.         while (*lp++ && isalnum(lp[-1]));
  539.         goto star;
  540.  
  541.         case NWORD | STAR:
  542.         curlp = lp;
  543.         while (*lp++ && !isalnum(lp[-1]));
  544.         goto star;
  545.  
  546.         case CCHR | STAR:
  547.         curlp = lp;
  548.         while (*lp++ && trt[lp[-1]] == trt[*ep]);
  549.         ep++;
  550.         goto star;
  551.  
  552.         case CCL | STAR:
  553.         case NCCL | STAR:
  554.         curlp = lp;
  555.         while (*lp++ && cclass (ep, lp[-1], ep[-1] == (CCL | STAR)));
  556.         ep += BMAPSIZ;
  557.         goto star;
  558.  
  559.     star:
  560.         do {
  561.             lp--;
  562.             if (advance (compex, lp, ep))
  563.             return TRUE;
  564.         } while (lp > curlp);
  565.         return FALSE;
  566.  
  567.         default:
  568.         fputs("Badly compiled pattern\n",stdout) FLUSH;
  569.         err = TRUE;
  570.         return -1;
  571.     }
  572.     if (*ep == CEND || *ep == CDOL) {
  573.         return TRUE;
  574.     }
  575.     return FALSE;
  576. }
  577.  
  578. bool
  579. backref (compex, i, lp)
  580. register COMPEX *compex;
  581. register int i;
  582. register char *lp;
  583. {
  584.     register char *bp;
  585.  
  586.     bp = compex->braslist[i];
  587.     while (*lp && *bp == *lp) {
  588.     bp++;
  589.     lp++;
  590.     if (bp >= compex->braelist[i])
  591.         return TRUE;
  592.     }
  593.     return FALSE;
  594. }
  595.  
  596. bool
  597. cclass (set, c, af)
  598. register char  *set;
  599. register int c;
  600. {
  601.     c &= 0177;
  602. #if BITSPERBYTE == 8
  603.     if (set[c >> 3] & 1 << (c & 7))
  604. #else
  605.     if (set[c / BITSPERBYTE] & 1 << (c % BITSPERBYTE))
  606. #endif
  607.     return af;
  608.     return !af;
  609. }
  610.