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