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