home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / x / xvisrc.zoo / search.c < prev    next >
C/C++ Source or Header  |  1992-07-28  |  27KB  |  1,234 lines

  1. /* Copyright (c) 1990,1991,1992 Chris and John Downey */
  2. #ifndef lint
  3. static char *sccsid = "@(#)search.c    2.1 (Chris & John Downey) 7/29/92";
  4. #endif
  5.  
  6. /***
  7.  
  8. * program name:
  9.     xvi
  10. * function:
  11.     PD version of UNIX "vi" editor, with extensions.
  12. * module name:
  13.     search.c
  14. * module function:
  15.     Regular expression searching, including global command.
  16. * history:
  17.     STEVIE - ST Editor for VI Enthusiasts, Version 3.10
  18.     Originally by Tim Thompson (twitch!tjt)
  19.     Extensive modifications by Tony Andrews (onecom!wldrdg!tony)
  20.     Heavily modified by Chris & John Downey
  21.  
  22. ***/
  23.  
  24. #include "xvi.h"
  25. #include "regexp.h"    /* Henry Spencer's regular expression routines */
  26. #include "regmagic.h"    /* Henry Spencer's regular expression routines */
  27.  
  28. #ifdef    MEGAMAX
  29. overlay "search"
  30. #endif
  31.  
  32. /*
  33.  * String searches
  34.  *
  35.  * The actual searches are done using Henry Spencer's regular expression
  36.  * library.
  37.  */
  38.  
  39. /*
  40.  * Names of values for the P_regextype enumerated parameter.
  41.  */
  42. char    *rt_strings[] =
  43. {
  44.     "tags",
  45.     "grep",
  46.     "egrep",
  47.     NULL
  48. };
  49.  
  50. /*
  51.  * Used by g/re/p to remember where we are and what we are doing.
  52.  */
  53. static    Line    *curline;
  54. static    Line    *lastline;
  55. static    long    curnum;
  56. static    bool_t    greptype;
  57.  
  58. static    Posn    *bcksearch P((Xviwin *, Line *, int, bool_t));
  59. static    Posn    *fwdsearch P((Xviwin *, Line *, int, bool_t));
  60. static    char    *mapstring P((char **, int));
  61. static    char    *compile P((char *, int, bool_t));
  62. static    char    *grep_line P((void));
  63. static    long    substitute P((Xviwin *, Line *, Line *, char *, char *));
  64.  
  65. /*
  66.  * Convert a regular expression to egrep syntax: the source string can
  67.  * be either tags compatible (only ^ and $ are significant), vi
  68.  * compatible or egrep compatible (but also using \< and \>)
  69.  *
  70.  * Our first parameter here is the address of a pointer, which we
  71.  * point to the closing delimiter character if we found one, otherwise
  72.  * the closing '\0'.
  73.  */
  74. static char *
  75. mapstring(sp, delim)
  76. char    **sp;        /* pointer to pointer to pattern string */
  77. int    delim;        /* delimiter character */
  78. {
  79.     static Flexbuf    ns;
  80.     int            rxtype;    /* can be rt_TAGS, rt_GREP or rt_EGREP */
  81.     register enum {
  82.     m_normal,    /* nothing special */
  83.     m_startccl,    /* just after [ */
  84.     m_negccl,    /* just after [^ */
  85.     m_ccl,        /* between [... or [^... and ] */
  86.     m_escape    /* just after \ */
  87.     }    state = m_normal;
  88.     register char    *s;
  89.  
  90.     rxtype = Pn(P_regextype);
  91.  
  92.     flexclear(&ns);
  93.     for (s = *sp; *s != '\0' && (*s != delim || state != m_normal); s++) {
  94.     switch (state) {
  95.     case m_normal:
  96.         switch (*s) {
  97.         case '\\':
  98.         state = m_escape;
  99.         break;
  100.  
  101.         case '(': case ')': case '+': case '?': case '|':
  102.         /* egrep metacharacters */
  103.         if (rxtype != rt_EGREP)
  104.             (void) flexaddch(&ns, '\\');
  105.         (void) flexaddch(&ns, *s);
  106.         break;
  107.  
  108.         case '*': case '.': case '[':
  109.         /* grep metacharacters */
  110.         if (rxtype == rt_TAGS) {
  111.             (void) flexaddch(&ns, '\\');
  112.         } else if (*s == '[') {
  113.             /* start of character class */
  114.             state = m_startccl;
  115.         }
  116.          /* fall through ... */
  117.  
  118.         default:
  119.         (void) flexaddch(&ns, *s);
  120.         }
  121.         break;
  122.  
  123.     case m_startccl:
  124.     case m_negccl:
  125.         (void) flexaddch(&ns, *s);
  126.         state = (*s == '^' && state == m_startccl) ? m_negccl : m_ccl;
  127.         break;
  128.  
  129.     case m_ccl:
  130.         (void) flexaddch(&ns, *s);
  131.         if (*s == ']')
  132.         state = m_normal;
  133.         break;
  134.  
  135.     case m_escape:
  136.         switch (*s) {
  137.         case '(':        /* bracket conversion */
  138.         case ')':
  139.         if (rxtype != rt_GREP)
  140.             (void) flexaddch(&ns, '\\');
  141.         (void) flexaddch(&ns, *s);
  142.         break;
  143.  
  144.         case '.':        /* egrep metacharacters */
  145.         case '\\':
  146.         case '[':
  147.         case '*':
  148.         case '?':
  149.         case '+':
  150.         case '^':
  151.         case '$':
  152.         case '|':
  153.         (void) lformat(&ns, "\\%c", *s);
  154.         break;
  155.  
  156.         default:        /* a normal character */
  157.         if (*s != delim)
  158.             (void) flexaddch(&ns, '\\');
  159.         (void) flexaddch(&ns, *s);
  160.         }
  161.         state = m_normal;
  162.     }
  163.     }
  164.  
  165.     *sp = s;
  166.  
  167.     /*
  168.      * This is horrible, but the real vi does it, so ...
  169.      */
  170.     if (state == m_escape) {
  171.     (void) lformat(&ns, "\\\\");
  172.     }
  173.     return flexgetstr(&ns);
  174. }
  175.  
  176. /**********************************************************
  177.  *                              *
  178.  * Abstract type definition.                  *
  179.  *                              *
  180.  * Regular expression node, with pointer reference count. *
  181.  *                              *
  182.  * We need this for global substitute commands.          *
  183.  *                              *
  184.  **********************************************************/
  185.  
  186. typedef struct {
  187.     regexp    *rn_ptr;
  188.     int        rn_count;
  189. } Rnode;
  190.  
  191. /*
  192.  * Node for last successfully compiled regular expression.
  193.  */
  194. static Rnode    *lastprogp = NULL;
  195.  
  196. /*
  197.  * Last regular expression used in a substitution.
  198.  */
  199. static    Rnode    *last_lhs = NULL;
  200.  
  201. /*
  202.  * Last rhs for a substitution.
  203.  */
  204. static    char    *last_rhs = NULL;
  205.  
  206. /*
  207.  * rn_new(), rn_delete() & rn_duplicate() perform operations on Rnodes
  208.  * which are respectively analogous to open(), close() & dup() for
  209.  * Unix file descriptors.
  210.  */
  211.  
  212. /*
  213.  * Make a new Rnode, given a pattern string.
  214.  */
  215. static Rnode *
  216. rn_new(str)
  217.     char    *str;
  218. {
  219.     Rnode    *retp;
  220.  
  221.     if ((retp = (Rnode *) alloc(sizeof (Rnode))) == NULL)
  222.     return NULL;
  223.     if ((retp->rn_ptr = regcomp(str)) == NULL) {
  224.     free ((char *) retp);
  225.     return NULL;
  226.     }
  227.     retp->rn_count = 1;
  228.     return retp;
  229. }
  230.  
  231. /*
  232.  * Make a copy of an Rnode pointer & increment the Rnode's reference
  233.  * count.
  234.  */
  235. #define rn_duplicate(s)    ((s) ? ((s)->rn_count++, (s)) : NULL)
  236.  
  237. /*
  238.  * Decrement an Rnode's reference count, freeing it if there are no
  239.  * more pointers pointing to it.
  240.  *
  241.  * In C++, this would be a destructor for an Rnode.
  242.  */
  243. static void
  244. rn_delete(rp)
  245. Rnode    *rp;
  246. {
  247.     if (rp != NULL && --rp->rn_count <= 0) {
  248.     free((char *) rp->rn_ptr);
  249.     free((char *) rp);
  250.     }
  251. }
  252.  
  253. #if 0
  254. /*
  255.  * Increment the reference count for the current prog,
  256.  * and return it to the caller.
  257.  */
  258. static Rnode *
  259. inccount()
  260. {
  261.     if (lastprogp != NULL) {
  262.     lastprogp->rn_count++;
  263.     }
  264.     return(lastprogp);
  265. }
  266.  
  267. #endif
  268.  
  269. #define    cur_prog()    (lastprogp->rn_ptr)
  270.  
  271. /*
  272.  * Compile given regular expression from string.
  273.  *
  274.  * The opening delimiter for the regular expression is supplied; the
  275.  * end of it is marked by an unescaped matching delimiter or, if
  276.  * delim_only is FALSE, by a '\0' character. We return a pointer to
  277.  * the terminating '\0' or to the character following the closing
  278.  * delimiter, or NULL if we failed.
  279.  *
  280.  * If, after we've found a delimiter, we have an empty pattern string,
  281.  * we use the last compiled expression if there is one.
  282.  *
  283.  * The regular expression is converted to egrep syntax by mapstring(),
  284.  * which also finds the closing delimiter. The actual compilation is
  285.  * done by regcomp(), from Henry Spencer's regexp routines.
  286.  *
  287.  * If we're successful, the compiled regular expression will be
  288.  * pointed to by lastprogp->rn_ptr, & lastprogp->rn_count will be > 0.
  289.  */
  290. static char *
  291. compile(pat, delimiter, delim_only)
  292. char    *pat;
  293. int    delimiter;
  294. bool_t    delim_only;
  295. {
  296.     Rnode    *progp;
  297.  
  298.     if (pat == NULL) {
  299.     return(NULL);
  300.     }
  301.  
  302.     /*
  303.      * If we get an empty regular expression, we just use the last
  304.      * one we compiled (if there was one).
  305.      */
  306.     if (*pat == '\0') {
  307.     return((delim_only || lastprogp == NULL) ? NULL : pat);
  308.     }
  309.     if (*pat == delimiter) {
  310.     return((lastprogp == NULL) ? NULL : &pat[1]);
  311.     }
  312.  
  313.     progp = rn_new(mapstring(&pat, delimiter));
  314.     if (progp == NULL) {
  315.     return(NULL);
  316.     }
  317.  
  318.     if (*pat == '\0') {
  319.     if (delim_only) {
  320.         rn_delete(progp);
  321.         return(NULL);
  322.     }
  323.     } else {
  324.     pat++;
  325.     }
  326.     rn_delete(lastprogp);
  327.     lastprogp = progp;
  328.     return(pat);
  329. }
  330.  
  331. Posn *
  332. search(window, startline, startindex, dir, strp)
  333. Xviwin        *window;
  334. Line        *startline;
  335. int        startindex;
  336. int        dir;        /* FORWARD or BACKWARD */
  337. char        **strp;
  338. {
  339.     Posn    *pos;
  340.     Posn    *(*sfunc) P((Xviwin *, Line *, int, bool_t));
  341.     char    *str;
  342.  
  343.     str = compile(*strp, (dir == FORWARD) ? '/' : '?', FALSE);
  344.     if (str == NULL) {
  345.     return(NULL);
  346.     }
  347.     *strp = str;
  348.  
  349.     if (dir == BACKWARD) {
  350.     sfunc = bcksearch;
  351.     } else {
  352.     sfunc = fwdsearch;
  353.     }
  354.     pos = (*sfunc)(window, startline, startindex, Pb(P_wrapscan));
  355.  
  356.     return(pos);
  357. }
  358.  
  359. /*
  360.  * Search for the given expression, ignoring regextype, without
  361.  * wrapscan & and without using the compiled regular expression for
  362.  * anything else (so 'n', 'N', etc., aren't affected). We do, however,
  363.  * cache the compiled form for the last string we were given.
  364.  */
  365. Posn *
  366. nsearch(window, startline, startindex, dir, str)
  367. Xviwin        *window;
  368. Line        *startline;
  369. int        startindex;
  370. int        dir;
  371. char        *str;
  372. {
  373.     static Rnode    *progp = NULL;
  374.     static char        *last_str = NULL;
  375.     Rnode        *old_progp;
  376.     Posn        *pos;
  377.     Posn        *(*sfunc) P((Xviwin *, Line *, int, bool_t));
  378.  
  379.     if (str == NULL) {
  380.     return(NULL);
  381.     }
  382.     if (str != last_str &&
  383.     (last_str == NULL || strcmp(str, last_str) != 0)) {
  384.     if (progp) {
  385.         rn_delete(progp);
  386.     }
  387.     progp = rn_new(str);
  388.     last_str = str;
  389.     }
  390.     if (progp == NULL) {
  391.     last_str = NULL;
  392.     return(NULL);
  393.     }
  394.  
  395.     if (dir == BACKWARD) {
  396.     sfunc = bcksearch;
  397.     } else {
  398.     sfunc = fwdsearch;
  399.     }
  400.  
  401.     old_progp = lastprogp;
  402.  
  403.     lastprogp = progp;
  404.     pos = (*sfunc)(window, startline, startindex, FALSE);
  405.  
  406.     lastprogp = old_progp;
  407.  
  408.     return(pos);
  409. }
  410.  
  411. /*
  412.  * Perform line-based search, returning a pointer to the first line
  413.  * (forwards or backwards) on which a match is found, or NULL if there
  414.  * is none in the buffer specified.
  415.  */
  416. Line *
  417. linesearch(window, dir, strp)
  418. Xviwin    *window;
  419. int    dir;
  420. char    **strp;
  421. {
  422.     Posn    pos;
  423.     Posn    *newpos;
  424.  
  425.     pos = *(window->w_cursor);
  426.     if (dir == FORWARD) {
  427.     /*
  428.      * We don't want a match to occur on the current line,
  429.      * but setting the starting position to the next line
  430.      * is wrong because we will not match a pattern at the
  431.      * start of the line. So go to the end of this line.
  432.      */
  433.     if (gchar(&pos) != '\0') {
  434.         while (inc(&pos) == mv_SAMELINE) {
  435.         ;
  436.         }
  437.     }
  438.     } else {
  439.     pos.p_index = 0;
  440.     }
  441.  
  442.     newpos = search(window, pos.p_line, pos.p_index, dir, strp);
  443.     return((newpos != NULL) ? newpos->p_line : NULL);
  444. }
  445.  
  446. /*
  447.  * regerror - called by regexp routines when errors are detected.
  448.  */
  449. void
  450. regerror(s)
  451. char    *s;
  452. {
  453.     if (echo & e_REGERR) {
  454.     show_error(curwin, "%s", s);
  455.     }
  456.     echo &= ~(e_REGERR | e_NOMATCH);
  457. }
  458.  
  459. /*
  460.  * Find a match at or after "ind" on the given "line"; return
  461.  * pointer to Posn of match, or NULL if no match was found.
  462.  */
  463. static Posn *
  464. match(line, ind)
  465. Line    *line;
  466. int    ind;
  467. {
  468.     static Posn    matchposn;
  469.     char    *s;
  470.     regexp    *prog;
  471.  
  472.     s = line->l_text + ind;
  473.     prog = cur_prog();
  474.  
  475.     if (regexec(prog, s, (ind == 0))) {
  476.     matchposn.p_line = line;
  477.     matchposn.p_index = (int) (prog->startp[0] - line->l_text);
  478.  
  479.     /*
  480.      * If the match is after the end of the line,
  481.      * move it to the last character of the line,
  482.      * unless the line has no characters at all.
  483.      */
  484.     if (line->l_text[matchposn.p_index] == '\0' &&
  485.                     matchposn.p_index > 0) {
  486.         matchposn.p_index -= 1;
  487.     }
  488.  
  489.     return(&matchposn);
  490.     } else {
  491.     return(NULL);
  492.     }
  493. }
  494.  
  495. /*
  496.  * Like match(), but returns the last available match on the given
  497.  * line which is before the index given in maxindex.
  498.  */
  499. static Posn *
  500. rmatch(line, ind, maxindex)
  501. Line        *line;
  502. register int    ind;
  503. int        maxindex;
  504. {
  505.     register int    lastindex = -1;
  506.     Posn        *pos;
  507.     register char    *ltp;
  508.  
  509.     ltp = line->l_text;
  510.     for (; (pos = match(line, ind)) != NULL; ind++) {
  511.     ind = pos->p_index;
  512.     if (ind >= maxindex)
  513.         break;
  514.     /*
  515.      * If we've found a match on the last
  516.      * character of the line, return it here or
  517.      * we could get into an infinite loop.
  518.      */
  519.     if (ltp[lastindex = ind] == '\0' || ltp[ind + 1] == '\0')
  520.         break;
  521.     }
  522.  
  523.     if (lastindex >= 0) {
  524.     static Posn    lastmatch;
  525.  
  526.     lastmatch.p_index = lastindex;
  527.     lastmatch.p_line = line;
  528.     return &lastmatch;
  529.     } else {
  530.     return NULL;
  531.     }
  532. }
  533.  
  534. /*
  535.  * Search forwards through the buffer for a match of the last
  536.  * pattern compiled.
  537.  */
  538. static Posn *
  539. fwdsearch(window, startline, startindex, wrapscan)
  540. Xviwin        *window;
  541. Line        *startline;
  542. int        startindex;
  543. bool_t        wrapscan;
  544. {
  545.     static Posn    *pos;        /* location of found string */
  546.     Line    *lp;        /* current line */
  547.     Line    *last;
  548.  
  549.     last = window->w_buffer->b_lastline;
  550.  
  551.     /*
  552.      * First, search for a match on the current line
  553.      * after the cursor position.
  554.      */
  555.     pos = match(startline, startindex + 1);
  556.     if (pos != NULL) {
  557.     return(pos);
  558.     }
  559.  
  560.     /*
  561.      * Now search all the lines from here to the end of the file,
  562.      * and from the start of the file back to here if (wrapscan).
  563.      */
  564.     for (lp = startline->l_next; lp != startline; lp = lp->l_next) {
  565.     /*
  566.      * Wrap around to the start of the file.
  567.      */
  568.     if (lp == last) {
  569.         if (wrapscan) {
  570.         lp = window->w_buffer->b_line0;
  571.         continue;
  572.         }
  573.          /* else */
  574.         return(NULL);
  575.     }
  576.  
  577.     pos = match(lp, 0);
  578.     if (pos != NULL) {
  579.         return(pos);
  580.     }
  581.     }
  582.  
  583.     /*
  584.      * Finally, search from the start of the cursor line
  585.      * up to the cursor position. (Wrapscan was set if
  586.      * we got here.)
  587.      */
  588.     pos = match(startline, 0);
  589.     if (pos != NULL) {
  590.     if (pos->p_index <= startindex) {
  591.         return(pos);
  592.     }
  593.     }
  594.  
  595.     return(NULL);
  596. }
  597.  
  598. /*
  599.  * Search backwards through the buffer for a match of the last
  600.  * pattern compiled.
  601.  *
  602.  * Because we're searching backwards, we have to return the
  603.  * last match on a line if there is more than one, so we call
  604.  * rmatch() instead of match().
  605.  */
  606. static Posn *
  607. bcksearch(window, startline, startindex, wrapscan)
  608. Xviwin        *window;
  609. Line        *startline;
  610. int        startindex;
  611. bool_t        wrapscan;
  612. {
  613.     Posn    *pos;        /* location of found string */
  614.     Line    *lp;        /* current line */
  615.     Line    *line0;
  616.  
  617.     /*
  618.      * First, search for a match on the current line before the
  619.      * current cursor position; if "begword" is set, it must be
  620.      * before the current cursor position minus one.
  621.      */
  622.     pos = rmatch(startline, 0, startindex);
  623.     if (pos != NULL) {
  624.     return(pos);
  625.     }
  626.  
  627.     /*
  628.      * Search all lines back to the start of the buffer,
  629.      * and then from the end of the buffer back to the
  630.      * line after the cursor line if wrapscan is set.
  631.      */
  632.     line0 = window->w_buffer->b_line0;
  633.     for (lp = startline->l_prev; lp != startline; lp = lp->l_prev) {
  634.  
  635.     if (lp == line0) {
  636.         if (wrapscan) {
  637.         /*
  638.          * Note we do a continue here so that
  639.          * the loop control works properly.
  640.          */
  641.         lp = window->w_buffer->b_lastline;
  642.         continue;
  643.         } else {
  644.         return(NULL);
  645.         }
  646.     }
  647.     pos = rmatch(lp, 0, INT_MAX);
  648.     if (pos != NULL)
  649.         return pos;
  650.     }
  651.  
  652.     /*
  653.      * Finally, try for a match on the cursor line
  654.      * after (or at) the cursor position.
  655.      */
  656.     pos = rmatch(startline, startindex, INT_MAX);
  657.     if (pos != NULL) {
  658.     return(pos);
  659.     }
  660.  
  661.     return(NULL);
  662. }
  663.  
  664. /*
  665.  * Execute a global command of the form:
  666.  *
  667.  * g/pattern/X
  668.  *
  669.  * where 'x' is a command character, currently one of the following:
  670.  *
  671.  * d    Delete all matching lines
  672.  * l    List all matching lines
  673.  * p    Print all matching lines
  674.  * s    Perform substitution
  675.  * &    Repeat last substitution
  676.  * ~    Apply last right-hand side used in a substitution to last
  677.  *    regular expression used
  678.  *
  679.  * The command character (as well as the trailing slash) is optional, and
  680.  * is assumed to be 'p' if missing.
  681.  *
  682.  * The "lp" and "up" parameters are the first line to be considered, and
  683.  * the last line to be considered. If these are NULL, the whole buffer is
  684.  * considered; if only up is NULL, we consider the single line "lp".
  685.  *
  686.  * The "matchtype" parameter says whether we are doing 'g' or 'v'.
  687.  */
  688. void
  689. do_global(window, lp, up, cmd, matchtype)
  690. Xviwin        *window;
  691. Line        *lp, *up;
  692. char        *cmd;
  693. bool_t        matchtype;
  694. {
  695.     Rnode        *globprogp;
  696.     regexp        *prog;        /* compiled pattern */
  697.     long        ndone;        /* number of matches */
  698.     register char    cmdchar = '\0';    /* what to do with matching lines */
  699.  
  700.     /*
  701.      * compile() compiles the pattern up to the first unescaped
  702.      * delimiter: we place the character after the delimiter in
  703.      * cmdchar. If there is no such character, we default to 'p'.
  704.      */
  705.     if (*cmd == '\0' || (cmd = compile(&cmd[1], *cmd, FALSE)) == NULL) {
  706.     regerror(matchtype ?
  707.         "Usage: :g/search pattern/command" :
  708.         "Usage: :v/search pattern/command");
  709.     return;
  710.     }
  711.     /*
  712.      * Check we can do the command before starting.
  713.      */
  714.     switch (cmdchar = *cmd) {
  715.     case '\0':
  716.     cmdchar = 'p';
  717.      /* fall through ... */
  718.     case 'l':
  719.     case 'p':
  720.     break;
  721.     case 's':
  722.     case '&':
  723.     case '~':
  724.     cmd++;    /* cmd points at char after modifier */
  725.      /* fall through ... */
  726.     case 'd':
  727.     if (!start_command(window)) {
  728.         return;
  729.     }
  730.     break;
  731.     default:
  732.     regerror("Invalid command character");
  733.     return;
  734.     }
  735.  
  736.     ndone = 0;
  737.  
  738.     /*
  739.      * If no range was given, do every line.
  740.      * If only one line was given, just do that one.
  741.      * Ensure that "up" points at the line after the
  742.      * last one in the range, to make the loop easier.
  743.      */
  744.     if (lp == NULL) {
  745.     lp = window->w_buffer->b_file;
  746.     up = window->w_buffer->b_lastline;
  747.     } else if (up == NULL) {
  748.     up = lp->l_next;
  749.     } else {
  750.     up = up->l_next;
  751.     }
  752.  
  753.     /*
  754.      * If we are going to print lines, it is sensible
  755.      * to find out the line number of the first line in
  756.      * the range before we start, and increment it as
  757.      * we go rather than finding out the line number
  758.      * for each line as it is printed.
  759.      */
  760.     switch (cmdchar) {
  761.     case 'p':
  762.     case 'l':
  763.     curnum = lineno(window->w_buffer, lp);
  764.     curline = lp;
  765.     lastline = up;
  766.     greptype = matchtype;
  767.     disp_init(window, grep_line, (int) Columns,
  768.           (cmdchar == 'l'));
  769.     return;
  770.     }
  771.  
  772.     /*
  773.      * This is tricky. do_substitute() might default to
  774.      * using cur_prog(), if the command is of the form
  775.      *
  776.      *    :g/pattern/s//.../
  777.      *
  778.      * so cur_prog() must still reference the expression we
  779.      * compiled. On the other hand, it may compile a
  780.      * different regular expression, so we have to be able
  781.      * to maintain a separate one (which is what globprogp
  782.      * is for). Moreover, if it does compile a different
  783.      * expression, one of them has to be freed afterwards.
  784.      *
  785.      * This is why we use Rnodes, which contain
  786.      * reference counts. An Rnode, & the compiled
  787.      * expression it points to, are only freed when its
  788.      * reference count is decremented to 0.
  789.      */
  790.     globprogp = rn_duplicate(lastprogp);
  791.     prog = cur_prog();
  792.  
  793.     /*
  794.      * Place the cursor at bottom left of the window,
  795.      * so the user knows what we are doing.
  796.      * It is safe not to put the cursor back, because
  797.      * we are going to produce some more output anyway.
  798.      */
  799.     gotocmd(window, FALSE);
  800.     flush_output();
  801.  
  802.     /*
  803.      * Try every line from lp up to (but not including) up.
  804.      */
  805.     ndone = 0;
  806.     while (lp != up) {
  807.     if (matchtype == regexec(prog, lp->l_text, TRUE)) {
  808.         Line    *thisline;
  809.  
  810.         /*
  811.          * Move the cursor to the line before
  812.          * doing anything. Also move the line
  813.          * pointer on one before calling any
  814.          * functions which might alter or delete
  815.          * the line.
  816.          */
  817.         move_cursor(window, lp, 0);
  818.  
  819.         thisline = lp;
  820.         lp = lp->l_next;
  821.  
  822.         switch (cmdchar) {
  823.         case 'd':    /* delete the line */
  824.         repllines(window, thisline, 1L,
  825.             (Line *) NULL);
  826.         ndone++;
  827.         break;
  828.         case 's':    /* perform substitution */
  829.         case '&':
  830.         case '~':
  831.         {
  832.         register long    (*func) P((Xviwin *, Line *, Line *, char *));
  833.         unsigned    savecho;
  834.  
  835.         switch (cmdchar) {
  836.         case 's':
  837.             func = do_substitute;
  838.             break;
  839.         case '&':
  840.             func = do_ampersand;
  841.             break;
  842.         case '~':
  843.             func = do_tilde;
  844.         }
  845.  
  846.         savecho = echo;
  847.  
  848.         echo &= ~e_NOMATCH;
  849.         ndone += (*func)
  850.         (window, thisline, thisline, cmd);
  851.  
  852.         echo = savecho;
  853.         break;
  854.         }
  855.         }
  856.     } else {
  857.         lp = lp->l_next;
  858.     }
  859.     }
  860.  
  861.     /*
  862.      * If globprogp is still the current prog, this should just
  863.      * decrement its reference count to 1: otherwise, if
  864.      * do_substitute() has compiled a different pattern, then that
  865.      * counts as the last compiled pattern, globprogp's reference
  866.      * count should be decremented to 0, & it should be freed.
  867.      */
  868.     rn_delete(globprogp);
  869.  
  870.     switch (cmdchar) {
  871.     case 'd':
  872.     case 's':
  873.     case '&':
  874.     case '~':
  875.     end_command(window);
  876.     if (ndone) {
  877.         update_buffer(window->w_buffer);
  878.         cursupdate(window);
  879.         begin_line(window, TRUE);
  880.         if (ndone >= Pn(P_report)) {
  881.         show_message(window,
  882.              (cmdchar == 'd') ?
  883.              "%ld fewer line%c" :
  884.              "%ld substitution%c",
  885.              ndone,
  886.              (ndone > 1) ?
  887.              's' : ' ');
  888.         }
  889.     }
  890.     }
  891.  
  892.     if (ndone == 0 && (echo & e_NOMATCH)) {
  893.     regerror("No match");
  894.     }
  895. }
  896.  
  897. static char *
  898. grep_line()
  899. {
  900.     static Flexbuf    b;
  901.     regexp        *prog;
  902.  
  903.     prog = cur_prog();
  904.     for ( ; curline != lastline; curline = curline->l_next, curnum++) {
  905.  
  906.     if (greptype == regexec(prog, curline->l_text, TRUE)) {
  907.  
  908.         flexclear(&b);
  909.         if (Pb(P_number)) {
  910.         (void) lformat(&b, NUM_FMT, curnum);
  911.         }
  912.         (void) lformat(&b, "%s", curline->l_text);
  913.         break;
  914.     }
  915.     }
  916.  
  917.     if (curline == lastline) {
  918.     return(NULL);
  919.     } else {
  920.     curline = curline->l_next;
  921.     curnum++;
  922.     return(flexgetstr(&b));
  923.     }
  924. }
  925.  
  926. /*
  927.  * regsubst - perform substitutions after a regexp match
  928.  *
  929.  * Adapted from a routine from Henry Spencer's regexp package. The
  930.  * original copyright notice for all these routines is in regexp.c,
  931.  * which is distributed herewith.
  932.  */
  933.  
  934. #ifndef CHARBITS
  935. #    define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  936. #else
  937. #    define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  938. #endif
  939.  
  940. static void
  941. regsubst(prog, src, dest)
  942. register regexp    *prog;
  943. register char    *src;
  944. Flexbuf        *dest;
  945. {
  946.     register int    c;
  947.  
  948.     if (prog == NULL || src == NULL || dest == NULL) {
  949.     regerror("NULL parameter to regsubst");
  950.     return;
  951.     }
  952.  
  953.     if (UCHARAT(prog->program) != MAGIC) {
  954.     regerror("Damaged regexp fed to regsubst");
  955.     return;
  956.     }
  957.  
  958.     while ((c = *src++) != '\0') {
  959.     register int no;
  960.  
  961.     /*
  962.      * First check for metacharacters.
  963.      */
  964.     if (c == '&') {
  965.         no = 0;
  966.     } else if (c == '\\' && '0' <= *src && *src <= '9') {
  967.         no = *src++ - '0';
  968.     } else {
  969.         no = -1;
  970.     }
  971.  
  972.     if (no < 0) {
  973.         /*
  974.          * It's an ordinary character.
  975.          */
  976.         if (c == '\\' && *src != '\0')
  977.         c = *src++;
  978.  
  979.         (void) flexaddch(dest, c);
  980.  
  981.     } else if (prog->startp[no] != NULL && prog->endp[no] != NULL) {
  982.         register char *bracketp;
  983.  
  984.         /*
  985.          * It isn't an ordinary character, but a reference
  986.          * to a string matched on the lhs. Notice that we
  987.          * just do nothing if we find a reference to a null
  988.          * match, or one that doesn't exist; we can't tell
  989.          * the difference at this stage.
  990.          */
  991.  
  992.         for (bracketp = prog->startp[no]; bracketp < prog->endp[no];
  993.                                  bracketp++) {
  994.         if (*bracketp == '\0') {
  995.             regerror("Damaged match string");
  996.             return;
  997.         } else {
  998.             (void) flexaddch(dest, *bracketp);
  999.         }
  1000.         }
  1001.     }
  1002.     }
  1003. }
  1004.  
  1005. /*
  1006.  * do_substitute(window, lp, up, cmd)
  1007.  *
  1008.  * Perform a substitution from line 'lp' up to (but not including)
  1009.  * line 'up' using the command pointed to by 'cmd' which should be
  1010.  * of the form:
  1011.  *
  1012.  * /pattern/substitution/g
  1013.  *
  1014.  * The trailing 'g' is optional and, if present, indicates that multiple
  1015.  * substitutions should be performed on each line, if applicable.
  1016.  * The usual escapes are supported as described in the regexp docs.
  1017.  */
  1018. long
  1019. do_substitute(window, lp, up, command)
  1020. Xviwin    *window;
  1021. Line    *lp, *up;
  1022. char    *command;
  1023. {
  1024.     char    *copy;        /* for copy of command */
  1025.     regexp    *prog;
  1026.     char    *sub;
  1027.     char    *cp;
  1028.     char    delimiter;
  1029.     long    nsubs;
  1030.  
  1031.     copy = alloc((unsigned) strlen(command) + 1);
  1032.     if (copy == NULL) {
  1033.     return(0);
  1034.     }
  1035.     (void) strcpy(copy, command);
  1036.  
  1037.     delimiter = *copy;
  1038.     if (delimiter == '\0' ||
  1039.                 (cp = compile(©[1], delimiter, TRUE)) == NULL) {
  1040.     regerror("Usage: :s/search pattern/replacement/");
  1041.     free(copy);
  1042.     return(0);
  1043.     }
  1044.     sub = cp;
  1045.     prog = cur_prog();
  1046.  
  1047.     /*
  1048.      * Scan past the rhs to the flags, if any.
  1049.      */
  1050.     for (; *cp != '\0'; cp++) {
  1051.     if (*cp == '\\') {
  1052.         if (*++cp == '\0') {
  1053.         break;
  1054.         }
  1055.     } else if (*cp == delimiter) {
  1056.         *cp++ = '\0';
  1057.         break;
  1058.     }
  1059.     }
  1060.  
  1061.     /*
  1062.      * Save the regular expression for do_ampersand().
  1063.      */
  1064.     if (last_lhs) {
  1065.     rn_delete(last_lhs);
  1066.     }
  1067.     last_lhs = rn_duplicate(lastprogp);
  1068.  
  1069.     /*
  1070.      * Save the rhs.
  1071.      */
  1072.     if (last_rhs != NULL) {
  1073.     free(last_rhs);
  1074.     }
  1075.     last_rhs = strsave(sub);
  1076.  
  1077.     nsubs = substitute(window, lp, up, sub, cp);
  1078.  
  1079.     free(copy);
  1080.  
  1081.     return(nsubs);
  1082. }
  1083.  
  1084. /*
  1085.  * Repeat last substitution.
  1086.  *
  1087.  * For vi compatibility, this also changes the value of the last
  1088.  * regular expression used.
  1089.  */
  1090. long
  1091. do_ampersand(window, lp, up, flags)
  1092. Xviwin    *window;
  1093. Line    *lp, *up;
  1094. char    *flags;
  1095. {
  1096.     long    nsubs;
  1097.  
  1098.     if (last_lhs == NULL || last_rhs == NULL) {
  1099.     show_error(window, "No substitute to repeat!");
  1100.     return(0);
  1101.     }
  1102.     rn_delete(lastprogp);
  1103.     lastprogp = rn_duplicate(last_lhs);
  1104.     nsubs = substitute(window, lp, up, last_rhs, flags);
  1105.     return(nsubs);
  1106. }
  1107.  
  1108. /*
  1109.  * Apply last right-hand side used in a substitution to last regular
  1110.  * expression used.
  1111.  *
  1112.  * For vi compatibility, this also changes the value of the last
  1113.  * substitution.
  1114.  */
  1115. long
  1116. do_tilde(window, lp, up, flags)
  1117. Xviwin    *window;
  1118. Line    *lp, *up;
  1119. char    *flags;
  1120. {
  1121.     long    nsubs;
  1122.  
  1123.     if (lastprogp == NULL || last_rhs == NULL) {
  1124.     show_error(window, "No substitute to repeat!");
  1125.     return(0);
  1126.     }
  1127.     if (last_lhs) {
  1128.     rn_delete(last_lhs);
  1129.     }
  1130.     last_lhs = rn_duplicate(lastprogp);
  1131.     nsubs = substitute(window, lp, up, last_rhs, flags);
  1132.     return(nsubs);
  1133. }
  1134.  
  1135. static long
  1136. substitute(window, lp, up, sub, flags)
  1137. Xviwin    *window;
  1138. Line    *lp, *up;
  1139. char    *sub;
  1140. char    *flags;
  1141. {
  1142.     long    nsubs;
  1143.     Flexbuf    ns;
  1144.     regexp    *prog;
  1145.     bool_t    do_all;        /* true if 'g' was specified */
  1146.  
  1147.     if (!start_command(window)) {
  1148.     return(0);
  1149.     }
  1150.  
  1151.     prog = cur_prog();
  1152.  
  1153.     do_all = (*flags == 'g');
  1154.  
  1155.     nsubs = 0;
  1156.  
  1157.     /*
  1158.      * If no range was given, do the current line.
  1159.      * If only one line was given, just do that one.
  1160.      * Ensure that "up" points at the line after the
  1161.      * last one in the range, to make the loop easier.
  1162.      */
  1163.     if (lp == NULL) {
  1164.     lp = window->w_cursor->p_line;
  1165.     }
  1166.     if (up == NULL) {
  1167.     up = lp->l_next;
  1168.     } else {
  1169.     up = up->l_next;
  1170.     }
  1171.     flexnew(&ns);
  1172.     for (; lp != up; lp = lp->l_next) {
  1173.     if (regexec(prog, lp->l_text, TRUE)) {
  1174.         char    *p, *matchp;
  1175.  
  1176.         /*
  1177.          * Save the line that was last changed for the final
  1178.          * cursor position (just like the real vi).
  1179.          */
  1180.         move_cursor(window, lp, 0);
  1181.  
  1182.         flexclear(&ns);
  1183.         p = lp->l_text;
  1184.  
  1185.         do {
  1186.         /*
  1187.          * Copy up to the part that matched.
  1188.          */
  1189.         while (p < prog->startp[0]) {
  1190.             (void) flexaddch(&ns, *p);
  1191.             p++;
  1192.         }
  1193.  
  1194.         regsubst(prog, sub, &ns);
  1195.  
  1196.         /*
  1197.          * Continue searching after the match.
  1198.          *
  1199.          * Watch out for null matches - we
  1200.          * don't want to go into an endless
  1201.          * loop here.
  1202.          */
  1203.         matchp = p = prog->endp[0];
  1204.         if (prog->startp[0] >= p) {
  1205.             if (*p == '\0') {
  1206.             /*
  1207.              * End of the line.
  1208.              */
  1209.             break;
  1210.             } else {
  1211.             matchp++;
  1212.             }
  1213.         }
  1214.  
  1215.         } while (do_all && regexec(prog, matchp, FALSE));
  1216.  
  1217.         /*
  1218.          * Copy the rest of the line, that didn't match.
  1219.          */
  1220.         (void) lformat(&ns, "%s", p);
  1221.         replchars(window, lp, 0, strlen(lp->l_text),
  1222.           flexgetstr(&ns));
  1223.         nsubs++;
  1224.     }
  1225.     }
  1226.     flexdelete(&ns);            /* free the temp buffer */
  1227.     end_command(window);
  1228.  
  1229.     if (!nsubs && (echo & e_NOMATCH)) {
  1230.     regerror("No match");
  1231.     }
  1232.     return(nsubs);
  1233. }
  1234.