home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 35 Internet / 35-Internet.zip / trn_12.zip / src / search.c < prev    next >
C/C++ Source or Header  |  1993-12-04  |  14KB  |  611 lines
  1. /* $Id: search.c,v 4.4.3.1 1992/02/01 03:09:32 sob PATCH_3 sob $
  2.  *
  3.  * $Log: search.c,v $
  4.  * Revision 4.4.3.1  1992/02/01  03:09:32  sob
  5.  * Release 4.4 Patchlevel 3
  6.  *
  7.  * Revision 4.4  1991/09/09  20:27:37  sob
  8.  * release 4.4
  9.  *
  10.  *
  11.  */
  12.  
  13. /* string search routines */
  14.  
  15. /*        Copyright (c) 1981,1980 James Gosling        */
  16.  
  17. /* Modified Aug. 12, 1981 by Tom London to include regular expressions
  18.    as in ed.  RE stuff hacked over by jag to correct a few major problems,
  19.    mainly dealing with searching within the buffer rather than copying
  20.    each line to a separate array.  Newlines can now appear in RE's */
  21.  
  22. /* Ripped to shreds and glued back together to make a search package,
  23.  * July 6, 1984, by Larry Wall. (If it doesn't work, it's probably my fault.)
  24.  * Changes include:
  25.  *    Buffer, window, and mlisp stuff gone.
  26.  *    Translation tables reduced to 1 table.
  27.  *    Expression buffer is now dynamically allocated.
  28.  *    Character classes now implemented with a bitmap.
  29.  */
  30.  
  31. #include "EXTERN.h"
  32. #include "common.h"
  33. #include "util.h"
  34. #include "INTERN.h"
  35. #include "search.h"
  36.  
  37. #ifndef BITSPERBYTE
  38. #define BITSPERBYTE 8
  39. #endif
  40.  
  41. #define BMAPSIZ (127 / BITSPERBYTE + 1)
  42.  
  43. /* meta characters in the "compiled" form of a regular expression */
  44. #define    CBRA    2        /* \( -- begin bracket */
  45. #define    CCHR    4        /* a vanilla character */
  46. #define    CDOT    6        /* . -- match anything except a newline */
  47. #define    CCL    8        /* [...] -- character class */
  48. #define    NCCL    10        /* [^...] -- negated character class */
  49. #define    CDOL    12        /* $ -- matches the end of a line */
  50. #define    CEND    14        /* The end of the pattern */
  51. #define    CKET    16        /* \) -- close bracket */
  52. #define    CBACK    18        /* \N -- backreference to the Nth bracketed
  53.                    string */
  54. #define CIRC    20        /* ^ matches the beginning of a line */
  55.  
  56. #define WORD    32        /* matches word character \w */
  57. #define NWORD    34        /* matches non-word characer \W */
  58. #define WBOUND    36        /* matches word boundary \b */
  59. #define NWBOUND    38        /* matches non-(word boundary) \B */
  60.  
  61. #define    STAR    01        /* * -- Kleene star, repeats the previous
  62.                    REas many times as possible; the value
  63.                    ORs with the other operator types */
  64.  
  65. #define ASCSIZ 0200
  66. typedef char    TRANSTABLE[ASCSIZ];
  67.  
  68. static    TRANSTABLE trans = {
  69. 0000,0001,0002,0003,0004,0005,0006,0007,
  70. 0010,0011,0012,0013,0014,0015,0016,0017,
  71. 0020,0021,0022,0023,0024,0025,0026,0027,
  72. 0030,0031,0032,0033,0034,0035,0036,0037,
  73. 0040,0041,0042,0043,0044,0045,0046,0047,
  74. 0050,0051,0052,0053,0054,0055,0056,0057,
  75. 0060,0061,0062,0063,0064,0065,0066,0067,
  76. 0070,0071,0072,0073,0074,0075,0076,0077,
  77. 0100,0101,0102,0103,0104,0105,0106,0107,
  78. 0110,0111,0112,0113,0114,0115,0116,0117,
  79. 0120,0121,0122,0123,0124,0125,0126,0127,
  80. 0130,0131,0132,0133,0134,0135,0136,0137,
  81. 0140,0141,0142,0143,0144,0145,0146,0147,
  82. 0150,0151,0152,0153,0154,0155,0156,0157,
  83. 0160,0161,0162,0163,0164,0165,0166,0167,
  84. 0170,0171,0172,0173,0174,0175,0176,0177,
  85. };
  86. static bool folding = FALSE;
  87.  
  88. static int err;
  89. static char *FirstCharacter;
  90.  
  91. void
  92. search_init()
  93. {
  94. #ifdef UNDEF
  95.     register int    i;
  96.     
  97.     for (i = 0; i < ASCSIZ; i++)
  98.     trans[i] = i;
  99. #else
  100.     ;
  101. #endif
  102. }
  103.  
  104. void
  105. init_compex(compex)
  106. register COMPEX *compex;
  107. {
  108.     /* the following must start off zeroed */
  109.  
  110.     compex->eblen = 0;
  111.     compex->brastr = Nullch;
  112. }
  113.  
  114. void
  115. free_compex(compex)
  116. register COMPEX *compex;
  117. {
  118.     if (compex->eblen) {
  119.     free(compex->expbuf);
  120.     compex->eblen = 0;
  121.     }
  122.     if (compex->brastr) {
  123.     free(compex->brastr);
  124.     compex->brastr = Nullch;
  125.     }
  126. }
  127.  
  128. static char *gbr_str = Nullch;
  129. static int gbr_siz = 0;
  130.  
  131. char *
  132. getbracket(compex,n)
  133. register COMPEX *compex;
  134. int n;
  135. {
  136.     int length = compex->braelist[n] - compex->braslist[n];
  137.  
  138.     if (!compex->nbra || n > compex->nbra || !compex->braelist[n] || length<0)
  139.     return nullstr;
  140.     growstr(&gbr_str, &gbr_siz, length+1);
  141.     safecpy(gbr_str, compex->braslist[n], length+1);
  142.     return gbr_str;
  143. }
  144.  
  145. void
  146. case_fold(which)
  147. int which;
  148. {
  149.     register int i;
  150.  
  151.     if (which != folding) {
  152.     if (which) {
  153.         for (i = 'A'; i <= 'Z'; i++)
  154.         trans[i] = tolower(i);
  155.     }
  156.     else {
  157.         for (i = 'A'; i <= 'Z'; i++)
  158.         trans[i] = i;
  159.     }
  160.     folding = which;
  161.     }
  162. }
  163.  
  164. /* Compile the given regular expression into a [secret] internal format */
  165.  
  166. char *
  167. compile (compex, strp, RE, fold)
  168. register COMPEX *compex;
  169. register char   *strp;
  170. int RE;
  171. int fold;
  172. {
  173.     register int c;
  174.     register char  *ep;
  175.     char   *lastep;
  176.     char    bracket[NBRA],
  177.        *bracketp;
  178.     char **alt = compex->alternatives;
  179.     char *retmes = "Badly formed search string";
  180.  
  181.     case_fold(compex->do_folding = fold);
  182.     if (!compex->eblen) {
  183.     compex->expbuf = safemalloc(84);
  184.     compex->eblen = 80;
  185.     }
  186.     ep = compex->expbuf;        /* point at expression buffer */
  187.     *alt++ = ep;            /* first alternative starts here */
  188.     bracketp = bracket;            /* first bracket goes here */
  189.     if (*strp == 0) {            /* nothing to compile? */
  190.     if (*ep == 0)            /* nothing there yet? */
  191.         return "Null search string";
  192.     return Nullch;            /* just keep old expression */
  193.     }
  194.     compex->nbra = 0;            /* no brackets yet */
  195.     lastep = 0;
  196.     for (;;) {
  197.     if (ep - compex->expbuf >= compex->eblen)
  198.         grow_eb(compex);
  199.     c = *strp++;            /* fetch next char of pattern */
  200.     if (c == 0) {            /* end of pattern? */
  201.         if (bracketp != bracket) {    /* balanced brackets? */
  202. #ifdef VERBOSE
  203.         retmes = "Unbalanced parens";
  204. #endif
  205.         goto cerror;
  206.         }
  207.         *ep++ = CEND;        /* terminate expression */
  208.         *alt++ = 0;            /* terminal alternative list */
  209.         /*
  210.         compex->eblen = ep - compex->expbuf + 1;
  211.         compex->expbuf = saferealloc(compex->expbuf,compex->eblen+4); */
  212.         return Nullch;        /* return success */
  213.     }
  214.     if (c != '*')
  215.         lastep = ep;
  216.     if (!RE) {            /* just a normal search string? */
  217.         *ep++ = CCHR;        /* everything is a normal char */
  218.         *ep++ = c;
  219.     }
  220.     else                /* it is a regular expression */
  221.         switch (c) {
  222.  
  223.         case '\\':        /* meta something */
  224.             switch (c = *strp++) {
  225.             case '(':
  226.             if (compex->nbra >= NBRA) {
  227. #ifdef VERBOSE
  228.                 retmes = "Too many parens";
  229. #endif
  230.                 goto cerror;
  231.             }
  232.             *bracketp++ = ++compex->nbra;
  233.             *ep++ = CBRA;
  234.             *ep++ = compex->nbra;
  235.             break;
  236.             case '|':
  237.             if (bracketp>bracket) {
  238. #ifdef VERBOSE
  239.                 retmes = "No \\| in parens";    /* Alas! */
  240. #endif
  241.                 goto cerror;
  242.             }
  243.             *ep++ = CEND;
  244.             *alt++ = ep;
  245.             break;
  246.             case ')':
  247.             if (bracketp <= bracket) {
  248. #ifdef VERBOSE
  249.                 retmes = "Unmatched right paren";
  250. #endif
  251.                 goto cerror;
  252.             }
  253.             *ep++ = CKET;
  254.             *ep++ = *--bracketp;
  255.             break;
  256.             case 'w':
  257.             *ep++ = WORD;
  258.             break;
  259.             case 'W':
  260.             *ep++ = NWORD;
  261.             break;
  262.             case 'b':
  263.             *ep++ = WBOUND;
  264.             break;
  265.             case 'B':
  266.             *ep++ = NWBOUND;
  267.             break;
  268.             case '0': case '1': case '2': case '3': case '4':
  269.             case '5': case '6': case '7': case '8': case '9':
  270.             *ep++ = CBACK;
  271.             *ep++ = c - '0';
  272.             break;
  273.             default:
  274.             *ep++ = CCHR;
  275.             if (c == '\0')
  276.                 goto cerror;
  277.             *ep++ = c;
  278.             break;
  279.             }
  280.             break;
  281.         case '.':
  282.             *ep++ = CDOT;
  283.             continue;
  284.  
  285.         case '*':
  286.             if (lastep == 0 || *lastep == CBRA || *lastep == CKET
  287.             || *lastep == CIRC
  288.             || (*lastep&STAR)|| *lastep>NWORD)
  289.             goto defchar;
  290.             *lastep |= STAR;
  291.             continue;
  292.  
  293.         case '^':
  294.             if (ep != compex->expbuf && ep[-1] != CEND)
  295.             goto defchar;
  296.             *ep++ = CIRC;
  297.             continue;
  298.  
  299.         case '$':
  300.             if (*strp != 0 && (*strp != '\\' || strp[1] != '|'))
  301.             goto defchar;
  302.             *ep++ = CDOL;
  303.             continue;
  304.  
  305.         case '[': {        /* character class */
  306.             register int i;
  307.             
  308.             if (ep - compex->expbuf >= compex->eblen - BMAPSIZ)
  309.             grow_eb(compex);    /* reserve bitmap */
  310.             for (i = BMAPSIZ; i; --i)
  311.             ep[i] = 0;
  312.             
  313.             if ((c = *strp++) == '^') {
  314.             c = *strp++;
  315.             *ep++ = NCCL;    /* negated */
  316.             }
  317.             else
  318.             *ep++ = CCL;    /* normal */
  319.             
  320.             i = 0;        /* remember oldchar */
  321.             do {
  322.             if (c == '\0') {
  323. #ifdef VERBOSE
  324.                 retmes = "Missing ]";
  325. #endif
  326.                 goto cerror;
  327.             }
  328.             if (*strp == '-' && *(++strp))
  329.                 i = *strp++;
  330.             else
  331.                 i = c;
  332.             while (c <= i) {
  333.                 ep[c / BITSPERBYTE] |= 1 << (c % BITSPERBYTE);
  334.                 if (fold && isalpha(c))
  335.                 ep[(c ^ 32) / BITSPERBYTE] |=
  336.                     1 << ((c ^ 32) % BITSPERBYTE);
  337.                     /* set the other bit too */
  338.                 c++;
  339.             }
  340.             } while ((c = *strp++) != ']');
  341.             ep += BMAPSIZ;
  342.             continue;
  343.         }
  344.  
  345.         defchar:
  346.         default:
  347.             *ep++ = CCHR;
  348.             *ep++ = c;
  349.         }
  350.     }
  351. cerror:
  352.     compex->expbuf[0] = 0;
  353.     compex->nbra = 0;
  354.     return retmes;
  355. }
  356.  
  357. void
  358. grow_eb(compex)
  359. register COMPEX *compex;
  360. {
  361.     compex->eblen += 80;
  362.     compex->expbuf = saferealloc(compex->expbuf, (MEM_SIZE)compex->eblen + 4);
  363. }
  364.  
  365. char *
  366. execute (compex, addr)
  367. register COMPEX *compex;
  368. char *addr;
  369. {
  370.     register char *p1 = addr;
  371.     register char *trt = trans;
  372.     register int c;
  373.  
  374.     if (addr == Nullch || compex->expbuf == Nullch)
  375.     return Nullch;
  376.     if (compex->nbra) {            /* any brackets? */
  377.     for (c = 0; c <= compex->nbra; c++)
  378.         compex->braslist[c] = compex->braelist[c] = Nullch;
  379.     if (compex->brastr)
  380.         free(compex->brastr);
  381.     compex->brastr = savestr(p1);    /* in case p1 is not static */
  382.     p1 = compex->brastr;        /* ! */
  383.     }
  384.     case_fold(compex->do_folding);    /* make sure table is correct */
  385.     FirstCharacter = p1;        /* for ^ tests */
  386.     if (compex->expbuf[0] == CCHR && !compex->alternatives[1]) {
  387.     c = trt[compex->expbuf[1]];    /* fast check for first character */
  388.     do {
  389.         if (trt[*p1] == c && advance (compex, p1, compex->expbuf))
  390.         return p1;
  391.         p1++;
  392.     } while (*p1 && !err);
  393.     if (err) err = 0;
  394.     return Nullch;
  395.     }
  396.     else {            /* regular algorithm */
  397.     do {
  398.         register char **alt = compex->alternatives;
  399.         while (*alt) {
  400.         if (advance (compex, p1, *alt++))
  401.             return p1;
  402.         }
  403.         p1++;
  404.     } while (*p1 && !err);
  405.     if (err) err = 0;
  406.     return Nullch;
  407.     }
  408.    /*NOTREACHED*/
  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. int af;
  601. {
  602.     c &= 0177;
  603. #if BITSPERBYTE == 8
  604.     if (set[c >> 3] & 1 << (c & 7))
  605. #else
  606.     if (set[c / BITSPERBYTE] & 1 << (c % BITSPERBYTE))
  607. #endif
  608.     return af;
  609.     return !af;
  610. }
  611.