home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gwm18a.zip / wl_string.c < prev    next >
C/C++ Source or Header  |  1995-07-03  |  14KB  |  652 lines
  1. /* Copyright 1989 GROUPE BULL -- See license conditions in file COPYRIGHT
  2.  * Copyright 1989 Massachusetts Institute of Technology
  3.  */
  4. /***********************\
  5. *                 *
  6. *  WOOL_OBJECT  String  *
  7. *  BODY                *
  8. *                 *
  9. \***********************/
  10.  
  11. #include "EXTERN.h"
  12. #include <stdio.h>
  13. #include "wool.h"
  14. #include "wl_number.h"
  15. #include "wl_atom.h"
  16. #include "wl_active.h"
  17. #include "wl_pointer.h"
  18. #include "wl_name.h"
  19. #include "wl_list.h"
  20. #include "INTERN.h"
  21. #include "wl_string.h"
  22.  
  23. char * re_comp();
  24.  
  25. /*
  26.  * Constructor:
  27.  * WLString_make
  28.  * argument 1: the string, which will be COPIED.
  29.  */
  30.  
  31. WOOL_String 
  32. WLString_make(s)
  33. char           *s;        /* the string itself */
  34. {
  35.     WOOL_String     object;
  36.  
  37.     if (s[0] == '\0')
  38.     return NIL_STRING;
  39.     object = (WOOL_String)
  40.     Malloc(sizeof(struct _WOOL_String) + strlen(s));
  41.     zrt_put(object);
  42.     object -> type = WLString;
  43.     strcpy(object -> string, s);
  44.     return object;
  45. }
  46.  
  47. WOOL_String 
  48. WLString_n_make(n)
  49. int    n;
  50. {
  51.     WOOL_String     object = (WOOL_String)
  52.     Malloc(sizeof(struct _WOOL_String) + n);
  53.  
  54.     zrt_put(object);
  55.     object -> type = WLString;
  56.     return object;
  57. }
  58.  
  59. NIL_STRING_make()
  60. {
  61.     NIL_STRING = (WOOL_String) Malloc(sizeof(struct _WOOL_String));
  62.     zrt_put(NIL_STRING);
  63.     NIL_STRING -> type = WLString;
  64.     NIL_STRING -> string[0] = '\0';
  65.     increase_reference(NIL_STRING);
  66. }
  67.  
  68. /*
  69.  * WLString_print:
  70.  * We print strings surrounded by double quotes.
  71.  */
  72.  
  73. WOOL_OBJECT 
  74. WLString_print(obj)
  75. WOOL_String     obj;
  76. {
  77.     wool_puts(obj -> string);
  78.     return (WOOL_OBJECT) obj;
  79. }
  80.  
  81. /*
  82.  * WLString_free
  83.  * just frees the structure, so we use WLNumber_free.
  84.  */
  85.  
  86. /* 
  87.  * WLString_execute
  88.  * just the same error as with atoms, let's use it.
  89.  */
  90.  
  91. /*
  92.  * WLString_equal
  93.  * tests 2 strings for equality (returns it if true)
  94.  */
  95.  
  96. WOOL_OBJECT
  97. WLString_equal(s1, s2)
  98. WOOL_String s1, s2;
  99. {
  100.     if (!is_a_string(s2) || strcmp(s1 -> string, s2 -> string))
  101.     return NIL;
  102.     else
  103.     return (WOOL_OBJECT) s1;
  104. }
  105.  
  106. /*
  107.  * string manipulation routines
  108.  */
  109.  
  110. static char *strings_temp_buffer;
  111. static int strings_temp_buffer_size = 256;
  112.  
  113. WOOL_OBJECT
  114. add_strings(argc,argv)
  115. int             argc;
  116. WOOL_String     argv[];
  117. {
  118.     int             required_length = 0, i;
  119.  
  120.     for (i = 0; i < argc; i++) {
  121.     must_be_string(argv[i], i);
  122.     if (argv[i] != (WOOL_String) NIL)
  123.         required_length += strlen(argv[i] -> string);
  124.     }
  125.     if (!strings_temp_buffer)
  126.     strings_temp_buffer = (char *) Malloc(strings_temp_buffer_size);
  127.     if (required_length >= strings_temp_buffer_size) {
  128.     strings_temp_buffer_size = Max(2 * strings_temp_buffer_size,
  129.                        required_length+1);
  130.     strings_temp_buffer = (char *)
  131.         Realloc(strings_temp_buffer, strings_temp_buffer_size);
  132.     }
  133.     strings_temp_buffer[0] = '\0';
  134.     for (i = 0; i < argc; i++)
  135.     if (argv[i] != (WOOL_String) NIL)
  136.         strcat(strings_temp_buffer, argv[i] -> string);
  137.     return (WOOL_OBJECT) WLString_make(strings_temp_buffer);
  138. }
  139.  
  140. /*
  141.  * To know if an object can be used as a string (atom, pointer or active)
  142.  */
  143.  
  144. int 
  145. must_be_string(obj, n)
  146. WOOL_OBJECT    obj;
  147. int        n;
  148. {
  149.     if (obj -> type != WLString
  150.     && obj -> type != WLAtom
  151.     && obj -> type != WLActive
  152.     && obj -> type != WLPointer
  153.     && obj -> type != WLName
  154.     && obj != NIL)
  155.     bad_argument(obj, n, WOOL_TYPE_P_NAME(WLString));
  156. }
  157.  
  158. int 
  159. is_a_string(obj)
  160. WOOL_OBJECT    obj;
  161. {
  162.     if (obj -> type != WLString
  163.         && obj -> type != WLAtom
  164.         && obj -> type != WLActive
  165.         && obj -> type != WLPointer
  166.         && obj -> type != WLName
  167.         && obj != NIL)
  168.      return 0;
  169.     else
  170.     return 1;
  171.  }
  172.  
  173.  
  174. /**************************************************************************\
  175. *                                        *
  176. * the general  match package                           *
  177. * (match regular-expression string [level])                   *
  178. * returns the sub-string in the levelth enclosing \( and \) or NIL_STRING  *
  179. * or string or NIL if no level given                       *
  180. *                                        *
  181. \**************************************************************************/
  182.  
  183. WOOL_String
  184. WLString_match(argc, argv)
  185. int    argc;
  186. WOOL_String    argv[];
  187. {
  188.     int             result, i;
  189.     char           *subst, *s, *comp_error;
  190.     WOOL_String     wl_subst;
  191.     WOOL_List        wl_list;
  192.     
  193.     if (argc < 2)
  194.       wool_error(BAD_NUMBER_OF_ARGS, argc);
  195.     must_be_string(argv[0], 0);
  196.     must_be_string(argv[1], 1);
  197.     if ((comp_error = re_comp(argv[0] -> string)) ||
  198.     ((result = re_exec(argv[1] -> string)) == -1)) {
  199.     if (comp_error)
  200.       wool_printf("%\n", comp_error);
  201.     wool_error("match: Bad regular expression, %s", argv[0] -> string);
  202.     }
  203.     if (result) {
  204.         switch (argc) {
  205.      case 2:
  206.         return argv[1];
  207.      case 3:
  208.         must_be_number(argv[2], 2);
  209.         if (result =
  210.         re_subst(((WOOL_Number) argv[2]) -> number, &subst)) {
  211.         wl_subst = WLString_n_make(result + 1);
  212.         strncpy(wl_subst -> string, subst, result);
  213.         wl_subst -> string[result] = '\0';
  214.         return wl_subst;
  215.         } else {
  216.         return NIL_STRING;
  217.         }
  218.      default:
  219.         wl_list = wool_list_make(argc - 2);
  220.         bzero(wl_list -> list, wl_list -> size * sizeof (WOOL_OBJECT));
  221.         for (i = 2; i< argc; i++) {
  222.         must_be_number(argv[i], i);
  223.         if (result =
  224.             re_subst(((WOOL_Number) argv[i]) -> number, &subst)) {
  225.             wl_subst = WLString_n_make(result + 1);
  226.             strncpy(wl_subst -> string, subst, result);
  227.             wl_subst -> string[result] = '\0';
  228.             increase_reference(wl_list -> list[i - 2] =
  229.                        (WOOL_OBJECT) wl_subst);
  230.         } else {
  231.             increase_reference(wl_list -> list[i - 2] =
  232.                        (WOOL_OBJECT) NIL_STRING);
  233.         }
  234.         }
  235.         return (WOOL_String) wl_list;
  236.         }
  237.     } else {
  238.     return (argc == 2 ? (WOOL_String) NIL : NIL_STRING);
  239.     }
  240. }
  241.  
  242. /*
  243.  * routines to do regular expression matching
  244.  *
  245.  * Entry points:
  246.  *
  247.  *    re_comp(s)
  248.  *        char *s;
  249.  *     ... returns 0 if the string s was compiled successfully,
  250.  *             a pointer to an error message otherwise.
  251.  *         If passed 0 or a null string returns without changing
  252.  *           the currently compiled re (see note 11 below).
  253.  *
  254.  *    re_exec(s)
  255.  *        char *s;
  256.  *     ... returns 1 if the string s matches the last compiled regular
  257.  *               expression, 
  258.  *             0 if the string s failed to match the last compiled
  259.  *               regular expression, and
  260.  *            -1 if the compiled regular expression was invalid 
  261.  *               (indicating an internal error).
  262.  *
  263.  *    re_subst(n, &p)
  264.  *        int n;
  265.  *        char *p;
  266.  *     ... returns in p the string matching the nth \(, returns the
  267.  *            number of chars matching
  268.  *
  269.  * The strings passed to both re_comp and re_exec may have trailing or
  270.  * embedded newline characters; they are terminated by nulls.
  271.  *
  272.  * The regular expressions recognized are described below. This description
  273.  * is essentially the same as that for ed.
  274.  *
  275.  *    A regular expression specifies a set of strings of characters.
  276.  *    A member of this set of strings is said to be matched by
  277.  *    the regular expression.  In the following specification for
  278.  *    regular expressions the word `character' means any character but NUL.
  279.  *
  280.  *    1.  Any character except a special character matches itself.
  281.  *        Special characters are the regular expression delimiter plus
  282.  *        \ [ . and sometimes ^ * $.
  283.  *    2.  A . matches any character.
  284.  *    3.  A \ followed by any character except a digit or ( )
  285.  *        matches that character.
  286.  *    4.  A nonempty string s bracketed [s] (or [^s]) matches any
  287.  *        character in (or not in) s. In s, \ has no special meaning,
  288.  *        and ] may only appear as the first letter. A substring 
  289.  *        a-b, with a and b in ascending ASCII order, stands for
  290.  *        the inclusive range of ASCII characters.
  291.  *    5.  A regular expression of form 1-4 followed by * matches a
  292.  *        sequence of 0 or more matches of the regular expression.
  293.  *    6.  A regular expression, x, of form 1-8, bracketed \(x\)
  294.  *        matches what x matches.
  295.  *    7.  A \ followed by a digit n matches a copy of the string that the
  296.  *        bracketed regular expression beginning with the nth \( matched.
  297.  *    8.  A regular expression of form 1-8, x, followed by a regular
  298.  *        expression of form 1-7, y matches a match for x followed by
  299.  *        a match for y, with the x match being as long as possible
  300.  *        while still permitting a y match.
  301.  *    9.  A regular expression of form 1-8 preceded by ^ (or followed
  302.  *        by $), is constrained to matches that begin at the left
  303.  *        (or end at the right) end of a line.
  304.  *    10. A regular expression of form 1-9 picks out the longest among
  305.  *        the leftmost matches in a line.
  306.  *    11. An empty regular expression stands for a copy of the last
  307.  *        regular expression encountered.
  308.  */
  309.  
  310. /*
  311.  * constants for re's
  312.  */
  313. #define    CBRA    1
  314. #define    CCHR    2
  315. #define    CDOT    4
  316. #define    CCL    6
  317. #define    NCCL    8
  318. #define    CDOL    10
  319. #define    CEOF    11
  320. #define    CKET    12
  321. #define    CBACK    18
  322.  
  323. #define    CSTAR    01
  324.  
  325. #define    ESIZE    512
  326. #define    NBRA    9
  327. #define    comerr(msg) {expbuf[0] = 0; numbra = 0; return(msg); }
  328.  
  329. static    char    expbuf[ESIZE], *braslist[NBRA], *braelist[NBRA];
  330. static    char    circf;
  331. static     int    numbra;
  332. static  int    advance();
  333.  
  334. /*
  335.  * compile the regular expression argument into a dfa
  336.  */
  337.  
  338. char *
  339. re_comp(sp)
  340. char    *sp;
  341. {
  342.     int    c;
  343.     char  *ep = expbuf;
  344.     int             cclcnt;
  345.     char           *lastep = 0;
  346.     char            bracket[NBRA];
  347.     char           *bracketp = &bracket[0];
  348.     static char    *retoolong = "Regular expression too long";
  349.  
  350.     numbra = 0;
  351.     if (sp == 0 || *sp == '\0') {
  352.     if (*ep == 0)
  353.         return ("No previous regular expression");
  354.     return (0);
  355.     }
  356.     if (*sp == '^') {
  357.     circf = 1;
  358.     sp++;
  359.     } else
  360.     circf = 0;
  361.     for (;;) {
  362.     if (ep >= &expbuf[ESIZE])
  363.         comerr(retoolong);
  364.     if ((c = *sp++) == '\0') {
  365.         if (bracketp != bracket)
  366.         comerr("unmatched \\(");
  367.         *ep++ = CEOF;
  368.         *ep++ = 0;
  369.         return (0);
  370.     }
  371.     if (c != '*')
  372.         lastep = ep;
  373.     switch (c) {
  374.  
  375.     case '.':
  376.         *ep++ = CDOT;
  377.         continue;
  378.  
  379.     case '*':
  380.         if (lastep == 0 || *lastep == CBRA || *lastep == CKET)
  381.         goto defchar;
  382.         *lastep |= CSTAR;
  383.         continue;
  384.  
  385.     case '$':
  386.         if (*sp != '\0')
  387.         goto defchar;
  388.         *ep++ = CDOL;
  389.         continue;
  390.  
  391.     case '[':
  392.         *ep++ = CCL;
  393.         *ep++ = 0;
  394.         cclcnt = 1;
  395.         if ((c = *sp++) == '^') {
  396.         c = *sp++;
  397.         ep[-2] = NCCL;
  398.         }
  399.         do {
  400.         if (c == '\0')
  401.             comerr("missing ]");
  402.         if (c == '-' && ep[-1] != 0) {
  403.             if ((c = *sp++) == ']') {
  404.             *ep++ = '-';
  405.             cclcnt++;
  406.             break;
  407.             }
  408.             while (ep[-1] < c) {
  409.             *ep = ep[-1] + 1;
  410.             ep++;
  411.             cclcnt++;
  412.             if (ep >= &expbuf[ESIZE])
  413.                 comerr(retoolong);
  414.             }
  415.         }
  416.         *ep++ = c;
  417.         cclcnt++;
  418.         if (ep >= &expbuf[ESIZE])
  419.             comerr(retoolong);
  420.         } while ((c = *sp++) != ']');
  421.         lastep[1] = cclcnt;
  422.         continue;
  423.  
  424.     case '\\':
  425.         if ((c = *sp++) == '(') {
  426.         if (numbra >= NBRA)
  427.             comerr("too many \\(\\) pairs");
  428.         *bracketp++ = numbra;
  429.         *ep++ = CBRA;
  430.         *ep++ = numbra++;
  431.         continue;
  432.         }
  433.         if (c == ')') {
  434.         if (bracketp <= bracket)
  435.             comerr("unmatched \\)");
  436.         *ep++ = CKET;
  437.         *ep++ = *--bracketp;
  438.         continue;
  439.         }
  440.         if (c >= '1' && c < ('1' + NBRA)) {
  441.         *ep++ = CBACK;
  442.         *ep++ = c - '1';
  443.         continue;
  444.         }
  445.         *ep++ = CCHR;
  446.         *ep++ = c;
  447.         continue;
  448.  
  449.     defchar:
  450.     default:
  451.         *ep++ = CCHR;
  452.         *ep++ = c;
  453.     }
  454.     }
  455. }
  456.  
  457. /* 
  458.  * match the argument string against the compiled re
  459.  */
  460.  
  461. int
  462. re_exec(p1)
  463. char    *p1;
  464. {
  465.     char  *p2 = expbuf;
  466.     int    c;
  467.     int             rv;
  468.  
  469.     for (c = 0; c < NBRA; c++) {
  470.     braslist[c] = 0;
  471.     braelist[c] = 0;
  472.     }
  473.     if (circf)
  474.     return ((advance(p1, p2)));
  475.  
  476.     /*
  477.      * fast check for first character 
  478.      */
  479.     if (*p2 == CCHR) {
  480.     c = p2[1];
  481.     do {
  482.         if (*p1 != c)
  483.         continue;
  484.         if (rv = advance(p1, p2))
  485.         return (rv);
  486.     } while (*p1++);
  487.     return (0);
  488.     }
  489.  
  490.     /*
  491.      * regular algorithm 
  492.      */
  493.     do
  494.     if (rv = advance(p1, p2))
  495.         return (rv);
  496.     while (*p1++);
  497.     return (0);
  498. }
  499.  
  500. /* 
  501.  * try to match the next thing in the dfa
  502.  */
  503.  
  504. static    int
  505. advance(lp, ep)
  506. char    *lp, *ep;
  507. {
  508.     char  *curlp;
  509.     int             ct, i;
  510.     int             rv;
  511.  
  512.     for (;;)
  513.     switch (*ep++) {
  514.  
  515.     case CCHR:
  516.         if (*ep++ == *lp++)
  517.         continue;
  518.         return (0);
  519.  
  520.     case CDOT:
  521.         if (*lp++)
  522.         continue;
  523.         return (0);
  524.  
  525.     case CDOL:
  526.         if (*lp == '\0')
  527.         continue;
  528.         return (0);
  529.  
  530.     case CEOF:
  531.         return (1);
  532.  
  533.     case CCL:
  534.         if (cclass(ep, *lp++, 1)) {
  535.         ep += *ep;
  536.         continue;
  537.         }
  538.         return (0);
  539.  
  540.     case NCCL:
  541.         if (cclass(ep, *lp++, 0)) {
  542.         ep += *ep;
  543.         continue;
  544.         }
  545.         return (0);
  546.  
  547.     case CBRA:
  548.         braslist[*ep++] = lp;
  549.         continue;
  550.  
  551.     case CKET:
  552.         braelist[*ep++] = lp;
  553.         continue;
  554.  
  555.     case CBACK:
  556.         if (braelist[i = *ep++] == 0)
  557.         return (-1);
  558.         if (backref(i, lp)) {
  559.         lp += braelist[i] - braslist[i];
  560.         continue;
  561.         }
  562.         return (0);
  563.  
  564.     case CBACK | CSTAR:
  565.         if (braelist[i = *ep++] == 0)
  566.         return (-1);
  567.         curlp = lp;
  568.         ct = braelist[i] - braslist[i];
  569.         while (backref(i, lp))
  570.         lp += ct;
  571.         while (lp >= curlp) {
  572.         if (rv = advance(lp, ep))
  573.             return (rv);
  574.         lp -= ct;
  575.         }
  576.         continue;
  577.  
  578.     case CDOT | CSTAR:
  579.         curlp = lp;
  580.         while (*lp++);
  581.         goto star;
  582.  
  583.     case CCHR | CSTAR:
  584.         curlp = lp;
  585.         while (*lp++ == *ep);
  586.         ep++;
  587.         goto star;
  588.  
  589.     case CCL | CSTAR:
  590.     case NCCL | CSTAR:
  591.         curlp = lp;
  592.         while (cclass(ep, *lp++, ep[-1] == (CCL | CSTAR)));
  593.         ep += *ep;
  594.         goto star;
  595.  
  596.     star:
  597.         do {
  598.         lp--;
  599.         if (rv = advance(lp, ep))
  600.             return (rv);
  601.         } while (lp > curlp);
  602.         return (0);
  603.  
  604.     default:
  605.         return (-1);
  606.     }
  607. }
  608.  
  609. backref(i, lp)
  610. int    i;
  611. char    *lp;
  612. {
  613.     char  *bp;
  614.  
  615.     bp = braslist[i];
  616.     while (*bp++ == *lp++)
  617.     if (bp >= braelist[i])
  618.         return (1);
  619.     return (0);
  620. }
  621.  
  622. int
  623. cclass(set, c, af)
  624. char    *set, c;
  625. int    af;
  626. {
  627.     int    n;
  628.  
  629.     if (c == 0)
  630.     return (0);
  631.     n = *set++;
  632.     while (--n)
  633.     if (*set++ == c)
  634.         return (af);
  635.     return (!af);
  636. }
  637.  
  638. int
  639. re_subst(n, pp)
  640. int     n;
  641. char    **pp;
  642. {
  643.     int length;
  644.  
  645.     if(n > numbra) {
  646.     return (int) wool_error("match: Too many \"(\" asked (%d) ", n);
  647.     }
  648.     *pp = braslist[n-1];
  649.     length = braelist[n-1] - *pp;
  650.     return length;
  651. }
  652.