home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / x / volume17 / tcl-editor / part09 / regex.c < prev   
Encoding:
C/C++ Source or Header  |  1992-03-18  |  22.4 KB  |  1,031 lines
  1. #ifdef uts
  2. #include <ctype.h>
  3. #endif /* uts */
  4. #include "pt.h"
  5. /*
  6.  * These routines are BSD regex(3)/ed(1) compatible regular-expression
  7.  * routines written by Ozan S. Yigit, Computer Science, York University.
  8.  * Parts of the code that are not needed by Prospero have been removed,
  9.  * but most of the accompanying information has been left intact. 
  10.  * This file is to be included on those operating systems that do not
  11.  * support re_comp and re_exec.
  12.  */
  13.  
  14. /*
  15.  * regex - Regular expression pattern matching
  16.  *         and replacement
  17.  *
  18.  * by:  Ozan S. Yigit (oz@nexus.yorku.ca)
  19.  *      York University
  20.  *
  21.  * These routines are the PUBLIC DOMAIN equivalents 
  22.  * of regex routines as found in 4.nBSD UN*X, with minor
  23.  * extensions.
  24.  *
  25.  * Modification history:
  26.  *
  27.  * $Log: regex.c,v $
  28.  * Revision 1.3  1992/03/04  17:07:18  crowley
  29.  * Backup
  30.  *
  31.  * Revision 1.2  1992/02/19  19:56:49  crowley
  32.  * Backup
  33.  *
  34.  * Revision 1.1  1992/02/19  16:43:42  crowley
  35.  * Backup
  36.  *
  37.  * Revision 1.3  89/04/01  14:18:09  oz
  38.  * Change all references to a dfa: this is actually an nfa.
  39.  * 
  40.  * Revision 1.2  88/08/28  15:36:04  oz
  41.  * Use a complement bitmap to represent NCL.
  42.  * This removes the need to have seperate 
  43.  * code in the pmatch case block - it is 
  44.  * just CCL code now.
  45.  * 
  46.  * Use the actual CCL code in the CLO
  47.  * section of pmatch. No need for a recursive
  48.  * pmatch call.
  49.  * 
  50.  * Use a bitmap table to set char bits in an
  51.  * 8-bit chunk.
  52.  * 
  53.  * Routines:
  54.  *      re_comp:        compile a regular expression into
  55.  *                      a NFA.
  56.  *
  57.  *            char *re_comp(s)
  58.  *            char *s;
  59.  *
  60.  *      re_exec:        execute the NFA to match a pattern.
  61.  *
  62.  *            int re_exec(s)
  63.  *            char *s;
  64.  *
  65.  * Regular Expressions:
  66.  *
  67.  *      [1]     char    matches itself, unless it is a special
  68.  *                      character (metachar): . \ [ ] * + ^ $
  69.  *
  70.  *      [2]     .       matches any character.
  71.  *
  72.  *      [3]     \       matches the character following it, except
  73.  *            when followed by a left or right round bracket,
  74.  *            a digit 1 to 9 or a left or right angle bracket. 
  75.  *            (see [7], [8] and [9])
  76.  *            It is used as an escape character for all 
  77.  *            other meta-characters, and itself. When used
  78.  *            in a set ([4]), it is treated as an ordinary
  79.  *            character.
  80.  *
  81.  *      [4]     [set]   matches one of the characters in the set.
  82.  *                      If the first character in the set is "^",
  83.  *                      it matches a character NOT in the set, i.e. 
  84.  *            complements the set. A shorthand S-E is 
  85.  *            used to specify a set of characters S upto 
  86.  *            E, inclusive. The special characters "]" and 
  87.  *            "-" have no special meaning if they appear 
  88.  *            as the first chars in the set.
  89.  *                      examples:        match:
  90.  *
  91.  *                              [a-z]    any lowercase alpha
  92.  *
  93.  *                              [^]-]    any char except ] and -
  94.  *
  95.  *                              [^A-Z]   any char except uppercase
  96.  *                                       alpha
  97.  *
  98.  *                              [a-zA-Z] any alpha
  99.  *
  100.  *      [5]     *       any regular expression form [1] to [4], followed by
  101.  *                      closure char (*) matches zero or more matches of
  102.  *                      that form.
  103.  *
  104.  *      [6]     +       same as [5], except it matches one or more.
  105.  *
  106.  *      [7]             a regular expression in the form [1] to [10], enclosed
  107.  *                      as \(form\) matches what form matches. The enclosure
  108.  *                      creates a set of tags, used for [8] and for
  109.  *                      pattern substution. The tagged forms are numbered
  110.  *            starting from 1.
  111.  *
  112.  *      [8]             a \ followed by a digit 1 to 9 matches whatever a
  113.  *                      previously tagged regular expression ([7]) matched.
  114.  *
  115.  *    [9]    \<    a regular expression starting with a \< construct
  116.  *        \>    and/or ending with a \> construct, restricts the
  117.  *            pattern matching to the beginning of a word, and/or
  118.  *            the end of a word. A word is defined to be a character
  119.  *            string beginning and/or ending with the characters
  120.  *            A-Z a-z 0-9 and _. It must also be preceded and/or
  121.  *            followed by any character outside those mentioned.
  122.  *
  123.  *      [10]            a composite regular expression xy where x and y
  124.  *                      are in the form [1] to [10] matches the longest
  125.  *                      match of x followed by a match for y.
  126.  *
  127.  *      [11]    ^    a regular expression starting with a ^ character
  128.  *        $    and/or ending with a $ character, restricts the
  129.  *                      pattern matching to the beginning of the line,
  130.  *                      or the end of line. [anchors] Elsewhere in the
  131.  *            pattern, ^ and $ are treated as ordinary characters.
  132.  *
  133.  *
  134.  * Acknowledgements:
  135.  *
  136.  *    HCR's Hugh Redelmeier has been most helpful in various
  137.  *    stages of development. He convinced me to include BOW
  138.  *    and EOW constructs, originally invented by Rob Pike at
  139.  *    the University of Toronto.
  140.  *
  141.  * References:
  142.  *              Software tools            Kernighan & Plauger
  143.  *              Software tools in Pascal        Kernighan & Plauger
  144.  *              Grep [rsx-11 C dist]            David Conroy
  145.  *        ed - text editor        Un*x Programmer's Manual
  146.  *        Advanced editing on Un*x    B. W. Kernighan
  147.  *        regexp routines            Henry Spencer
  148.  *
  149.  * Notes:
  150.  *
  151.  *    This implementation uses a bit-set representation for character
  152.  *    classes for speed and compactness. Each character is represented 
  153.  *    by one bit in a 128-bit block. Thus, CCL always takes a 
  154.  *    constant 16 bytes in the internal nfa, and re_exec does a single
  155.  *    bit comparison to locate the character in the set.
  156.  *
  157.  * Examples:
  158.  *
  159.  *    pattern:    foo*.*
  160.  *    compile:    CHR f CHR o CLO CHR o END CLO ANY END END
  161.  *    matches:    fo foo fooo foobar fobar foxx ...
  162.  *
  163.  *    pattern:    fo[ob]a[rz]    
  164.  *    compile:    CHR f CHR o CCL bitset CHR a CCL bitset END
  165.  *    matches:    fobar fooar fobaz fooaz
  166.  *
  167.  *    pattern:    foo\\+
  168.  *    compile:    CHR f CHR o CHR o CHR \ CLO CHR \ END END
  169.  *    matches:    foo\ foo\\ foo\\\  ...
  170.  *
  171.  *    pattern:    \(foo\)[1-3]\1    (same as foo[1-3]foo)
  172.  *    compile:    BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
  173.  *    matches:    foo1foo foo2foo foo3foo
  174.  *
  175.  *    pattern:    \(fo.*\)-\1
  176.  *    compile:    BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
  177.  *    matches:    foo-foo fo-fo fob-fob foobar-foobar ...
  178.  * 
  179.  */
  180.  
  181. #define MAXNFA  1024
  182. #define MAXTAG  10
  183.  
  184. #define OKP     1
  185. #define NOP     0
  186.  
  187. #define CHR     1
  188. #define ANY     2
  189. #define CCL     3
  190. #define BOL     4
  191. #define EOL     5
  192. #define BOT     6
  193. #define EOT     7
  194. #define BOW    8
  195. #define EOW    9
  196. #define REF     10
  197. #define CLO     11
  198. #define CHR2    12
  199.     /* two characters (for case insensitive search) */
  200.  
  201. #define END     0
  202.  
  203. /*
  204.  * The following defines are not meant
  205.  * to be changeable. They are for readability
  206.  * only.
  207.  *
  208.  */
  209. #define MAXCHR    128
  210. #define CHRBIT    8
  211. #define BITBLK    MAXCHR/CHRBIT
  212. #define BLKIND    0170
  213. #define BITIND    07
  214.  
  215. #define ASCIIB    0177
  216.  
  217. typedef /*unsigned*/ char CHAR;
  218.  
  219. static int  tagstk[MAXTAG];             /* subpat tag stack..*/
  220. static CHAR nfa[MAXNFA];        /* automaton..       */
  221. static int  sta = NOP;                   /* status of lastpat */
  222.  
  223. static CHAR bittab[BITBLK];        /* bit table for CCL */
  224.                     /* pre-set bits...   */
  225. static CHAR bitarr[] = {1,2,4,8,16,32,64,128};
  226.  
  227. static int internal_error;
  228.  
  229. static void
  230. chset(c)
  231. register CHAR c;
  232. {
  233.     bittab[((c) & BLKIND) >> 3] |= bitarr[(c) & BITIND];
  234. }
  235.  
  236. #define badpat(x)    return (*nfa = END, x)
  237. #define store(x)    *mp++ = x
  238.  
  239. char *     
  240. re_comp(pat)
  241. char *pat;
  242. {
  243.     extern int ignoreCase;
  244.     register char *p;               /* pattern pointer   */
  245.     register CHAR *mp = nfa;        /* nfa pointer       */
  246.     register CHAR *lp;              /* saved pointer..   */
  247.     register CHAR *sp = nfa;        /* another one..     */
  248.  
  249.     register int tagi = 0;          /* tag stack index   */
  250.     register int tagc = 1;          /* actual tag count  */
  251.  
  252.     register int n;
  253.     register CHAR mask;        /* xor mask -CCL/NCL */
  254.     int c1, c2;
  255.     char ch;
  256.         
  257.     if (!pat || !*pat)
  258.         if (sta)
  259.             return 0;
  260.         else
  261.             badpat("No previous regular expression");
  262.     sta = NOP;
  263.  
  264.     for (p = pat; *p; p++) {
  265.         lp = mp;
  266.         switch(*p) {
  267.  
  268.         case '.':               /* match any char..  */
  269.             store(ANY);
  270.             break;
  271.  
  272.         case '^':               /* match beginning.. */
  273.             store(BOL);
  274.             break;
  275.  
  276.         case '$':               /* match endofline.. */
  277.             store(EOL);
  278.             break;
  279.  
  280.         case '[':               /* match char class..*/
  281.             store(CCL);
  282.  
  283.             if (*++p == '^') {
  284.                 mask = 0377;    
  285.                 p++;
  286.             }
  287.             else
  288.                 mask = 0;
  289.  
  290.             if (*p == '-')        /* real dash */
  291.                 chset(*p++);
  292.             if (*p == ']')        /* real brac */
  293.                 chset(*p++);
  294.             while (*p && *p != ']') {
  295.                 if (*p == '-' && *(p+1) && *(p+1) != ']') {
  296.                     p++;
  297.                     c1 = *(p-2) + 1;
  298.                     c2 = *p++;
  299.                     while (c1 <= c2) {
  300.                         if(isalpha(c1) && ignoreCase) {
  301.                             chset(toupper(c1));
  302.                             chset(tolower(c1));
  303.                         } else
  304.                             chset(c1);
  305.                         ++c1;
  306.                     }
  307.                 }
  308. #ifdef EXTEND
  309.                 else if (*p == '\\' && *(p+1)) {
  310.                     p++;
  311.                     chset(*p++);
  312.                 }
  313. #endif
  314.                 else {
  315.                     ch = *p++;
  316.                     if( isalpha(ch) && ignoreCase ) {
  317.                         chset(toupper(ch));
  318.                         chset(tolower(ch));
  319.                     } else
  320.                         chset(ch);
  321.                 }
  322.             }
  323.             if (!*p)
  324.                 badpat("Missing ]");
  325.  
  326.             for (n = 0; n < BITBLK; bittab[n++] = (char) 0)
  327.                 store(mask ^ bittab[n]);
  328.     
  329.             break;
  330.  
  331.         case '*':               /* match 0 or more.. */
  332.         case '+':               /* match 1 or more.. */
  333.             if (p == pat)
  334.                 badpat("Empty closure");
  335.             lp = sp;        /* previous opcode */
  336.             if (*lp == CLO)        /* equivalence..   */
  337.                 break;
  338.             switch(*lp) {
  339.  
  340.             case BOL:
  341.             case BOT:
  342.             case EOT:
  343.             case BOW:
  344.             case EOW:
  345.             case REF:
  346.                 badpat("Illegal closure");
  347.             default:
  348.                 break;
  349.             }
  350.  
  351.             if (*p == '+')
  352.                 for (sp = mp; lp < sp; lp++)
  353.                     store(*lp);
  354.  
  355.             store(END);
  356.             store(END);
  357.             sp = mp;
  358.             while (--mp > lp)
  359.                 *mp = mp[-1];
  360.             store(CLO);
  361.             mp = sp;
  362.             break;
  363.  
  364.         case '\\':              /* tags, backrefs .. */
  365.             switch(*++p) {
  366.  
  367.             case '(':
  368.                 if (tagc < MAXTAG) {
  369.                     tagstk[++tagi] = tagc;
  370.                     store(BOT);
  371.                     store(tagc++);
  372.                 }
  373.                 else
  374.                     badpat("Too many \\(\\) pairs");
  375.                 break;
  376.             case ')':
  377.                 if (*sp == BOT)
  378.                     badpat("Null pattern inside \\(\\)");
  379.                 if (tagi > 0) {
  380.                     store(EOT);
  381.                     store(tagstk[tagi--]);
  382.                 }
  383.                 else
  384.                     badpat("Unmatched \\)");
  385.                 break;
  386.             case '<':
  387.                 store(BOW);
  388.                 break;
  389.             case '>':
  390.                 if (*sp == BOW)
  391.                     badpat("Null pattern inside \\<\\>");
  392.                 store(EOW);
  393.                 break;
  394.             case '1':
  395.             case '2':
  396.             case '3':
  397.             case '4':
  398.             case '5':
  399.             case '6':
  400.             case '7':
  401.             case '8':
  402.             case '9':
  403.                 n = *p-'0';
  404.                 if (tagi > 0 && tagstk[tagi] == n)
  405.                     badpat("Cyclical reference");
  406.                 if (tagc > n) {
  407.                     store(REF);
  408.                     store(n);
  409.                 }
  410.                 else
  411.                     badpat("Undetermined reference");
  412.                 break;
  413.             case 'b':
  414.                 store(CHR);
  415.                 store('\b');
  416.                 break;
  417.             case 'n':
  418.                 store(CHR);
  419.                 store('\n');
  420.                 break;
  421.             case 'f':
  422.                 store(CHR);
  423.                 store('\f');
  424.                 break;
  425.             case 'r':
  426.                 store(CHR);
  427.                 store('\r');
  428.                 break;
  429.             case 't':
  430.                 store(CHR);
  431.                 store('\t');
  432.                 break;
  433.             default:
  434.                 store(CHR);
  435.                 store(*p);
  436.             }
  437.             break;
  438.  
  439.         default :               /* an ordinary char  */
  440.             ch = *p;
  441.             if( isalpha(ch) && ignoreCase ) {
  442.                 store(CHR2);
  443.                 store(toupper(ch));
  444.                 store(tolower(ch));
  445.             } else {
  446.                 store(CHR);
  447.                 store(ch);
  448.             }
  449.             break;
  450.         }
  451.         sp = lp;
  452.     }
  453.     if (tagi > 0)
  454.         badpat("Unmatched \\(");
  455.     store(END);
  456.     sta = OKP;
  457.     return 0;
  458. }
  459.  
  460. static char * bol;
  461. int regex_bopat[MAXTAG];
  462. int regex_eopat[MAXTAG];
  463. int regex_pmatch();
  464.  
  465. static int line_count;
  466.  
  467. /*
  468.  * re_exec:
  469.  *     execute nfa to find a match.
  470.  *
  471.  *    special cases: (nfa[0])    
  472.  *        BOL
  473.  *            Match only once, starting from the
  474.  *            beginning.
  475.  *        CHR
  476.  *            First locate the character without
  477.  *            calling pmatch, and if found, call
  478.  *            pmatch for the remaining string.
  479.  *        END
  480.  *            re_comp failed, poor luser did not
  481.  *            check for it. Fail fast.
  482.  *
  483.  *    If a match is found, regex_bopat[0] and regex_eopat[0] are set
  484.  *    to the beginning and the end of the matched fragment,
  485.  *    respectively.
  486.  *
  487.  */
  488.  
  489. static void
  490. re_exec_init()
  491. {
  492.     line_count = 0;
  493.  
  494.     regex_bopat[0] = 0;
  495.     regex_bopat[1] = 0;
  496.     regex_bopat[2] = 0;
  497.     regex_bopat[3] = 0;
  498.     regex_bopat[4] = 0;
  499.     regex_bopat[5] = 0;
  500.     regex_bopat[6] = 0;
  501.     regex_bopat[7] = 0;
  502.     regex_bopat[8] = 0;
  503.     regex_bopat[9] = 0;
  504.     
  505.     ClearByteCache();
  506. }
  507.  
  508. int
  509. re_exec( fid, cp, end_cp, lines_passed)
  510.     int fid;
  511.     register int cp;
  512.     int end_cp;
  513.     int *lines_passed;
  514. {
  515.     char c, c2;
  516.     int ep = 0;
  517.     CHAR *ap = nfa;
  518.     char ch;
  519.  
  520.     re_exec_init();
  521.  
  522.     switch(*ap) {
  523.  
  524.     case CHR2:            /* ordinary char: locate it fast */
  525.         c = *(ap+1);
  526.         c2 = *(ap+2);
  527.         ch = getCachedFileByte( fid, cp );
  528.         if( ch == '\n' )
  529.             ++line_count;
  530.         while( (cp<=end_cp) && (ch != c) && (ch != c2) ) {
  531.             ch = getCachedFileByte( fid, ++cp );
  532.             if( ch == '\n' )
  533.                 ++line_count;
  534.         }
  535.         if( cp > end_cp )    /* if EOS, fail, else fall thru. */
  536.             return 0;
  537.         goto normalCase;
  538.  
  539.     case CHR:            /* ordinary char: locate it fast */
  540.         c = *(ap+1);
  541.         ch = getCachedFileByte( fid, cp );
  542.         if( ch == '\n' )
  543.             ++line_count;
  544.         while( (cp<=end_cp) && (ch != c) ) {
  545.             ch = getCachedFileByte( fid, ++cp );
  546.             if( ch == '\n' )
  547.                 ++line_count;
  548.         }
  549.         if( cp > end_cp )    /* if EOS, fail, else fall thru. */
  550.             return 0;
  551.     default:            /* regular matching all the way. */
  552.     normalCase:
  553.         while( cp<=end_cp ) {
  554.             /*SUPPRESS 560*/
  555.             if ((ep = pmatch(fid,cp,end_cp,ap)))
  556.                 break;
  557.             ++cp;
  558.         }
  559.         break;
  560.     case END:            /* munged automaton. fail always */
  561.         return 0;
  562.     }
  563.     if (!ep)
  564.         return 0;
  565.  
  566.     if (internal_error)
  567.         return -1;
  568.  
  569.     regex_bopat[0] = cp;
  570.     regex_eopat[0] = ep;
  571.     *lines_passed = line_count;
  572.     return 1;
  573. }
  574.  
  575. int
  576. re_exec_reversed( fid, cp, end_cp, lines_passed)
  577.     int fid;
  578.     register int cp;
  579.     int end_cp;
  580.     int *lines_passed;
  581. {
  582.     char c, c2;
  583.     int ep = 0;
  584.     CHAR *ap = nfa;
  585.     char ch;
  586.     int end_file = fileSize(fid) - 1;
  587.  
  588.     re_exec_init();
  589.  
  590.     switch(*ap) {
  591.  
  592.     case CHR2:            /* ordinary char: locate it fast */
  593.         c = *(ap+1);
  594.         c2 = *(ap+2);
  595.         ch = getCachedFileByte( fid, end_cp );
  596.         if( ch == '\n' )
  597.             ++line_count;
  598.         while( (cp<=end_cp) && (ch != c) && (ch != c2) ) {
  599.             ch = getCachedFileByte( fid, --end_cp );
  600.             if( ch == '\n' )
  601.                 ++line_count;
  602.         }
  603.         if( cp > end_cp )    /* if EOS, fail, else fall thru. */
  604.             return 0;
  605.         goto normalCase;
  606.  
  607.     case CHR:            /* ordinary char: locate it fast */
  608.         c = *(ap+1);
  609.         ch = getCachedFileByte( fid, end_cp );
  610.         if( ch == '\n' )
  611.             ++line_count;
  612.         while( (cp<=end_cp) && (ch != c) ) {
  613.             ch = getCachedFileByte( fid, --end_cp );
  614.             if( ch == '\n' )
  615.                 ++line_count;
  616.         }
  617.         if( cp > end_cp )    /* if EOS, fail, else fall thru. */
  618.             return 0;
  619.     default:            /* regular matching all the way. */
  620.     normalCase:
  621.         while( cp<=end_cp ) {
  622.             /*SUPPRESS 560*/
  623.             if ((ep = pmatch(fid,end_cp,end_file,ap)))
  624.                 break;
  625.             --end_cp;
  626.         }
  627.         break;
  628.     case END:            /* munged automaton. fail always */
  629.         return 0;
  630.     }
  631.     if (!ep)
  632.         return 0;
  633.  
  634.     if (internal_error)
  635.         return -1;
  636.  
  637.     regex_bopat[0] = end_cp;
  638.     regex_eopat[0] = ep;
  639.     *lines_passed = line_count;
  640.     return 1;
  641. }
  642.  
  643.  
  644. /* 
  645.  * pmatch: 
  646.  *    internal routine for the hard part
  647.  *
  648.  *     This code is mostly snarfed from an early
  649.  *     grep written by David Conroy. The backref and
  650.  *     tag stuff, and various other mods are by oZ.
  651.  *
  652.  *    special cases: (nfa[n], nfa[n+1])
  653.  *        CLO ANY
  654.  *            We KNOW ".*" will match ANYTHING
  655.  *            upto the end of line. Thus, go to
  656.  *            the end of line straight, without
  657.  *            calling pmatch recursively. As in
  658.  *            the other closure cases, the remaining
  659.  *            pattern must be matched by moving
  660.  *            backwards on the string recursively,
  661.  *            to find a match for xy (x is ".*" and 
  662.  *            y is the remaining pattern) where
  663.  *            the match satisfies the LONGEST match
  664.  *            for x followed by a match for y.
  665.  *        CLO CHR
  666.  *            We can again scan the string forward
  667.  *            for the single char without recursion, 
  668.  *            and at the point of failure, we execute 
  669.  *            the remaining nfa recursively, as
  670.  *            described above.
  671.  *
  672.  *    At the end of a successful match, regex_bopat[n] and regex_eopat[n]
  673.  *    are set to the beginning and end of subpatterns matched
  674.  *    by tagged expressions (n = 1 to 9).    
  675.  *
  676.  */
  677.  
  678. /*
  679.  * character classification table for word boundary
  680.  * operators BOW and EOW. the reason for not using 
  681.  * ctype macros is that we can let the user add into 
  682.  * our own table. see re_modw. This table is not in
  683.  * the bitset form, since we may wish to extend it
  684.  * in the future for other character classifications. 
  685.  *
  686.  *    TRUE for 0-9 A-Z a-z _
  687.  */
  688. static char chrtyp[MAXCHR] = {
  689.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  690.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  691.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  692.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  693.     0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 
  694.     1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 
  695.     0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 
  696.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  697.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  698.     1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 
  699.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  700.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  701.     1, 1, 1, 0, 0, 0, 0, 0
  702.     };
  703.  
  704. #define inascii(x)    (0177&(x))
  705. #define iswordc(x)     chrtyp[inascii(x)]
  706. #define isinset(x,y)     ((x)[((y)&BLKIND)>>3] & bitarr[(y)&BITIND])
  707.  
  708. /*
  709.  * skip values for CLO XXX to skip past the closure
  710.  *
  711.  */
  712.  
  713. #define ANYSKIP    2     /* [CLO] ANY END ...         */
  714. #define CHRSKIP    3    /* [CLO] CHR chr END ...     */
  715. #define CHR2SKIP 4    /* [CLO] CHR chr END ...     */
  716. #define CCLSKIP 18    /* [CLO] CCL 16bytes END ... */
  717.  
  718. static int
  719. pmatch( fid, cp, end_cp, ap )
  720.     int fid;
  721.     register int cp;
  722.     register int end_cp;
  723.     register CHAR *ap;
  724. {
  725.     register int op, c, n;
  726.     register int e;        /* extra pointer for CLO */
  727.     register int bp;        /* beginning of subpat.. */
  728.     register int ep;        /* ending of subpat..     */
  729.     int are;            /* to save the line ptr. */
  730.     char ch, c2;
  731.  
  732.     while ((op = *ap++) != END) {
  733.         ch = getCachedFileByte( fid, cp );
  734.         if( ch == '\n' )
  735.             ++line_count;
  736.         switch(op) {
  737.  
  738.         case CHR:
  739.             ++cp;
  740.             if( ch != *ap++ )
  741.                 return 0;
  742.             break;
  743.         case CHR2:
  744.             ++cp;
  745.             /* first check against the upper case letter */
  746.             if( ch != *ap++ ) {
  747.                 /* check against the lower case letter */
  748.                 if( ch != *ap++ )
  749.                     /* if neither, then no match */
  750.                     return 0;
  751.             } else
  752.                 ++ap; /* skip the lower case character */
  753.             break;
  754.         case ANY:
  755.             ++cp;
  756.             /* the ANY wildcard does not match newlines */
  757.             if( (ch == '\n') || (cp > end_cp) )
  758.                 return 0;
  759.             break;
  760.         case CCL:
  761.             ++cp;
  762.             if( !isinset(ap,ch) )
  763.                 return 0;
  764.             ap += BITBLK;
  765.             break;
  766.         case BOL:
  767.             if( cp > 0 && '\n' != getCachedFileByte(fid,cp-1) )
  768.                 return 0;
  769.             break;
  770.         case EOL:
  771.             if( getCachedFileByte(fid,cp+1) != '\n' )
  772.                 return 0;
  773.             break;
  774.         case BOT:
  775.             regex_bopat[*ap++] = cp;
  776.             break;
  777.         case EOT:
  778.             regex_eopat[*ap++] = cp;
  779.             break;
  780.          case BOW:
  781.             if(
  782.                 (cp > 0 && iswordc( getCachedFileByte(fid,cp-1) ))
  783.                 || !iswordc(ch)
  784.              )
  785.                 return 0;
  786.             break;
  787.         case EOW:
  788.             if( !iswordc(getCachedFileByte(fid,cp-1)) || iswordc(ch) )
  789.                 return 0;
  790.             break;
  791.         case REF:
  792.             n = *ap++;
  793.             bp = regex_bopat[n];
  794.             ep = regex_eopat[n];
  795.             while( bp < ep ) {
  796.                 if( getCachedFileByte(fid,bp++)
  797.                         != getCachedFileByte(fid,cp++) )
  798.                     return 0;
  799.             }
  800.             break;
  801.         case CLO:
  802. /************************************
  803. Handle line counts in closures correctly
  804. ***************************************/
  805.             are = cp;
  806.             switch( *ap ) {
  807.  
  808.             case ANY:
  809.                 /* the ANY wildcard does not match newlines */
  810.                 while( (ch != '\n') && (cp <= end_cp) )
  811.                     ch = getCachedFileByte( fid, ++cp );
  812.                 n = ANYSKIP;
  813.                 break;
  814.             case CHR:
  815.                 c = *(ap+1);
  816.                 while( (cp<=end_cp) && c == ch )
  817.                     ch = getCachedFileByte( fid, ++cp );
  818.                 n = CHRSKIP;
  819.                 break;
  820.             case CHR2:
  821.                 c = *(ap+1);
  822.                 c2 = *(ap+2);
  823.                 while( (cp<=end_cp) && (c == ch || c2 == ch) )
  824.                     ch = getCachedFileByte( fid, ++cp );
  825.                 n = CHR2SKIP;
  826.                 break;
  827.             case CCL:
  828.                 while( (cp <= end_cp) && isinset(ap+1,ch) )
  829.                     ch = getCachedFileByte( fid, ++cp );
  830.                 n = CCLSKIP;
  831.                 break;
  832.             default:
  833.                 internal_error++;
  834.                 return 0;
  835.             }
  836.  
  837.             ap += n;
  838.  
  839.             while( cp >= are ) {
  840.                 /*SUPPRESS 560*/
  841.                 if( e = pmatch(fid,cp,end_cp,ap) )
  842.                     return e;
  843.                 --cp;
  844.             }
  845.             return 0;
  846.         default:
  847.             internal_error++;
  848.             return 0;
  849.         }
  850.     }
  851.     return cp;
  852. }
  853.  
  854. char * pmatch2();
  855.  
  856. int
  857. re_match( lp )
  858.     CHAR *lp;
  859. {
  860.     char * ep;
  861.     
  862.     bol = lp;
  863.  
  864.     ep = pmatch2( lp, nfa );
  865.  
  866.     if( ep == 0 )
  867.         return 0;
  868.     else
  869.         return 1;
  870. }
  871.  
  872. static char *
  873. pmatch2( lp, ap )
  874.     register CHAR *lp;
  875.     register CHAR *ap;
  876. {
  877.     register int op, c, n;
  878.     register char * e;        /* extra pointer for CLO */
  879.     char * are;            /* to save the line ptr. */
  880.  
  881.     while ((op = *ap++) != END) {
  882.         switch(op) {
  883.  
  884.         case CHR:
  885.             if( *lp++ != *ap++ )
  886.                 return 0;
  887.             break;
  888.         case ANY:
  889.             if( !*lp++ )
  890.                 return 0;
  891.             break;
  892.         case CCL:
  893.             c = *lp++;
  894.             if( !isinset(ap,c) )
  895.                 return 0;
  896.             ap += BITBLK;
  897.             break;
  898.         case BOL:
  899.             if( lp != bol )
  900.                 return 0;
  901.             break;
  902.         case EOL:
  903.             if( *lp )
  904.                 return 0;
  905.             break;
  906.         case CLO:
  907.             are = lp;
  908.             switch( *ap ) {
  909.  
  910.             case ANY:
  911.                 while( *lp )
  912.                     lp++;
  913.                 n = ANYSKIP;
  914.                 break;
  915.             case CHR:
  916.                 c = *(ap+1);
  917.                 while( *lp && c == *lp )
  918.                     lp++;
  919.                 n = CHRSKIP;
  920.                 break;
  921.             case CCL:
  922.                 while( (c = *lp) && isinset(ap+1,c) )
  923.                     lp++;
  924.                 n = CCLSKIP;
  925.                 break;
  926.             default:
  927.                 internal_error++;
  928.                 return 0;
  929.             }
  930.  
  931.             ap += n;
  932.  
  933.             while( lp >= are ) {
  934.                 /*SUPPRESS 560*/
  935.                 if( e = pmatch2( lp, ap ) )
  936.                     return e;
  937.                 --lp;
  938.             }
  939.             return 0;
  940.         default:
  941.             internal_error++;
  942.             return 0;
  943.         }
  944.     }
  945.     return lp;
  946. }
  947.  
  948. /*ARGSUSED*/
  949. void
  950. RegexReplaceAll( w, searchFor, replaceWith, inSelection )
  951.     struct window * w;
  952.     char * searchFor;
  953.     char * replaceWith;
  954.     int inSelection;
  955. {
  956.     printf("RegexReplaceAll: not implemented yet\n");
  957. }
  958.  
  959. #define BUFFER_LENGTH    1024
  960.  
  961. /*ARGSUSED*/
  962. int
  963. RegexReplaceOne( w, searchFor, replaceWith )
  964.     struct window * w;
  965.     char * searchFor;
  966.     char * replaceWith;
  967. {
  968.     extern Offset selBegin, selEnd;
  969.     extern char msgBuffer[];
  970.     extern struct window *selWindow;
  971.  
  972.     int cp, cp_limit, diff_lengths;
  973.     char buffer[BUFFER_LENGTH];
  974.     char * to = buffer;
  975.     char * to_limit = to + BUFFER_LENGTH;
  976.     char * from = replaceWith;
  977.  
  978.     while( *from != '\0' ) {
  979.         char ch = *from++;
  980.         switch( ch ) {
  981.         default:
  982.             *to++ = ch;
  983.             break;
  984.         case '&':
  985.             cp = regex_bopat[0];
  986.             cp_limit = regex_eopat[0];
  987.             while( cp < cp_limit ) {
  988.                 *to++ = getFileByte(w->fileId, cp++);
  989.                 if( to >= to_limit )
  990.                     --to;
  991.             }
  992.             break;
  993.         case '\\':
  994.             ch = *from++;
  995.             switch( ch ) {
  996.             default:
  997.                 *to++ = ch;
  998.                 break;
  999.             case '\\':
  1000.                 *to++ = '\\';
  1001.                 break;
  1002.             case '1': case '2': case '3': case '4': case '5':
  1003.             case '6': case '7': case '8': case '9': 
  1004.                 cp = regex_bopat[ch-'0'];
  1005.                 cp_limit = regex_eopat[ch-'0'];
  1006.                 while( cp < cp_limit ) {
  1007.                     *to++ = getFileByte(w->fileId, cp++);
  1008.                     if( to >= to_limit )
  1009.                         --to;
  1010.                 }
  1011.                 break;
  1012.             }
  1013.         }
  1014.         if( to >= to_limit )
  1015.             --to;
  1016.     }
  1017.     *to = '\0';
  1018.     selBegin = regex_bopat[0];
  1019.     selEnd = regex_eopat[0] - 1;
  1020.     diff_lengths = strlen(buffer) - (selEnd-selBegin);
  1021.     if( selBegin <= selEnd )
  1022.         deleteChars( w->fileId, UPDATEWINDOWS, 1 );
  1023.     else
  1024.         selEnd = selBegin;
  1025.     for( from = buffer; *from != '\0'; ++from )
  1026.         insertChar( *from );
  1027.     drawWindow( selWindow );
  1028.     return diff_lengths;
  1029. }
  1030.  
  1031.