home *** CD-ROM | disk | FTP | other *** search
/ The Fred Fish Collection 1.5 / ffcollection-1-5-1992-11.iso / ff_disks / 001-099 / ff093.lzh / MicroEmacs / source / src.arc / search.c < prev    next >
C/C++ Source or Header  |  1987-08-16  |  32KB  |  1,416 lines
  1. /*
  2.  * The functions in this file implement commands that search in the forward
  3.  * and backward directions.  There are no special characters in the search
  4.  * strings.  Probably should have a regular expression search, or something
  5.  * like that.
  6.  *
  7.  * Aug. 1986 John M. Gamble:
  8.  *    Made forward and reverse search use the same scan routine.
  9.  *
  10.  *    Added a limited number of regular expressions - 'any',
  11.  *    'character class', 'closure', 'beginning of line', and
  12.  *    'end of line'.
  13.  *
  14.  *    Replacement metacharacters will have to wait for a re-write of
  15.  *    the replaces function, and a new variation of ldelete().
  16.  *
  17.  *    For those curious as to my references, i made use of
  18.  *    Kernighan & Plauger's "Software Tools."
  19.  *    I deliberately did not look at any published grep or editor
  20.  *    source (aside from this one) for inspiration.  I did make use of
  21.  *    Allen Hollub's bitmap routines as published in Doctor Dobb's Journal,
  22.  *    June, 1985 and modified them for the limited needs of character class
  23.  *    matching.  Any inefficiences, bugs, stupid coding examples, etc.,
  24.  *    are therefore my own responsibility.
  25.  *
  26.  * April 1987: John M. Gamble
  27.  *    Deleted the "if (n == 0) n = 1;" statements in front of the
  28.  *    search/hunt routines.  Since we now use a do loop, these
  29.  *    checks are unnecessary.  Consolidated common code into the
  30.  *    function delins().  Renamed global mclen matchlen,
  31.  *    and added the globals matchline, matchoff, patmatch, and
  32.  *    mlenold.
  33.  *    This gave us the ability to unreplace regular expression searches,
  34.  *    and to put the matched string into an evironment variable.
  35.  *    SOON TO COME: Meta-replacement characters!
  36.  *
  37.  *    25-apr-87    DML
  38.  *    - cleaned up an unneccessary if/else in forwsearch() and
  39.  *      backsearch()
  40.  *    - savematch() failed to malloc room for the terminating byte
  41.  *      of the match string (stomp...stomp...). It does now. Also
  42.  *      it now returns gracefully if malloc fails
  43.  */
  44.  
  45. #include        <stdio.h>
  46. #include    "estruct.h"
  47. #include        "edef.h"
  48.  
  49.  
  50. /*
  51.  * forwsearch -- Search forward.  Get a search string from the user, and
  52.  *    search for the string.  If found, reset the "." to be just after
  53.  *    the match string, and (perhaps) repaint the display.
  54.  */
  55.  
  56. forwsearch(f, n)
  57.  
  58. int f, n;    /* default flag / numeric argument */
  59.  
  60. {
  61.     register int status = TRUE;
  62.  
  63.     /* If n is negative, search backwards.
  64.      * Otherwise proceed by asking for the search string.
  65.      */
  66.     if (n < 0)
  67.         return(backsearch(f, -n));
  68.  
  69.     /* Ask the user for the text of a pattern.  If the
  70.      * response is TRUE (responses other than FALSE are
  71.      * possible), search for the pattern for as long as
  72.      * n is positive (n == 0 will go through once, which
  73.      * is just fine).
  74.      */
  75.     if ((status = readpattern("Search", &pat[0], TRUE)) == TRUE) {
  76.         do {
  77. #if    MAGIC
  78.             if ((magical && curwp->w_bufp->b_mode & MDMAGIC) != 0)
  79.                 status = mcscanner(&mcpat[0], FORWARD, PTEND);
  80.             else
  81. #endif
  82.                 status = scanner(&pat[0], FORWARD, PTEND);
  83.         } while ((--n > 0) && status);
  84.  
  85.         /* Save away the match, or complain
  86.          * if not there.
  87.          */
  88.         if (status == TRUE)
  89.             savematch();
  90.         else
  91.             mlwrite("Not found");
  92.     }
  93.     return(status);
  94. }
  95.  
  96. /*
  97.  * forwhunt -- Search forward for a previously acquired search string.
  98.  *    If found, reset the "." to be just after the match string,
  99.  *    and (perhaps) repaint the display.
  100.  */
  101.  
  102. forwhunt(f, n)
  103.  
  104. int f, n;    /* default flag / numeric argument */
  105.  
  106. {
  107.     register int status = TRUE;
  108.  
  109.     if (n < 0)        /* search backwards */
  110.         return(backhunt(f, -n));
  111.  
  112.     /* Make sure a pattern exists, or that we didn't switch
  113.      * into MAGIC mode until after we entered the pattern.
  114.      */
  115.     if (pat[0] == '\0')
  116.     {
  117.         mlwrite("No pattern set");
  118.         return FALSE;
  119.     }
  120. #if    MAGIC
  121.     if ((curwp->w_bufp->b_mode & MDMAGIC) != 0 &&
  122.          mcpat[0].mc_type == MCNIL)
  123.     {
  124.         if (!mcstr())
  125.             return FALSE;
  126.     }
  127. #endif
  128.  
  129.     /* Search for the pattern for as long as
  130.      * n is positive (n == 0 will go through once, which
  131.      * is just fine).
  132.      */
  133.     do
  134.     {
  135. #if    MAGIC
  136.         if ((magical && curwp->w_bufp->b_mode & MDMAGIC) != 0)
  137.             status = mcscanner(&mcpat[0], FORWARD, PTEND);
  138.         else
  139. #endif
  140.             status = scanner(&pat[0], FORWARD, PTEND);
  141.     } while ((--n > 0) && status);
  142.  
  143.     /* Save away the match, or complain
  144.      * if not there.
  145.      */
  146.     if (status == TRUE)
  147.         savematch();
  148.     else
  149.         mlwrite("Not found");
  150.  
  151.     return(status);
  152. }
  153.  
  154. /*
  155.  * backsearch -- Reverse search.  Get a search string from the user, and
  156.  *    search, starting at "." and proceeding toward the front of the buffer.
  157.  *    If found "." is left pointing at the first character of the pattern
  158.  *    (the last character that was matched).
  159.  */
  160. backsearch(f, n)
  161.  
  162. int f, n;    /* default flag / numeric argument */
  163.  
  164. {
  165.     register int status = TRUE;
  166.  
  167.     /* If n is negative, search forwards.
  168.      * Otherwise proceed by asking for the search string.
  169.      */
  170.     if (n < 0)
  171.         return(forwsearch(f, -n));
  172.  
  173.     /* Ask the user for the text of a pattern.  If the
  174.      * response is TRUE (responses other than FALSE are
  175.      * possible), search for the pattern for as long as
  176.      * n is positive (n == 0 will go through once, which
  177.      * is just fine).
  178.      */
  179.     if ((status = readpattern("Reverse search", &pat[0], TRUE)) == TRUE) {
  180.         do {
  181. #if    MAGIC
  182.             if ((magical && curwp->w_bufp->b_mode & MDMAGIC) != 0)
  183.                 status = mcscanner(&tapcm[0], REVERSE, PTBEG);
  184.             else
  185. #endif
  186.                 status = scanner(&tap[0], REVERSE, PTBEG);
  187.         } while ((--n > 0) && status);
  188.  
  189.         /* Save away the match, or complain
  190.          * if not there.
  191.          */
  192.         if (status == TRUE)
  193.             savematch();
  194.         else
  195.             mlwrite("Not found");
  196.     }
  197.     return(status);
  198. }
  199.  
  200. /*
  201.  * backhunt -- Reverse search for a previously acquired search string,
  202.  *    starting at "." and proceeding toward the front of the buffer.
  203.  *    If found "." is left pointing at the first character of the pattern
  204.  *    (the last character that was matched).
  205.  */
  206. backhunt(f, n)
  207.  
  208. int f, n;    /* default flag / numeric argument */
  209.  
  210. {
  211.     register int    status = TRUE;
  212.  
  213.     if (n < 0)
  214.         return(forwhunt(f, -n));
  215.  
  216.     /* Make sure a pattern exists, or that we didn't switch
  217.      * into MAGIC mode until after we entered the pattern.
  218.      */
  219.     if (tap[0] == '\0')
  220.     {
  221.         mlwrite("No pattern set");
  222.         return FALSE;
  223.     }
  224. #if    MAGIC
  225.     if ((curwp->w_bufp->b_mode & MDMAGIC) != 0 &&
  226.          tapcm[0].mc_type == MCNIL)
  227.     {
  228.         if (!mcstr())
  229.             return FALSE;
  230.     }
  231. #endif
  232.  
  233.     /* Go search for it for as long as
  234.      * n is positive (n == 0 will go through once, which
  235.      * is just fine).
  236.      */
  237.     do
  238.     {
  239. #if    MAGIC
  240.         if ((magical && curwp->w_bufp->b_mode & MDMAGIC) != 0)
  241.             status = mcscanner(&tapcm[0], REVERSE, PTBEG);
  242.         else
  243. #endif
  244.             status = scanner(&tap[0], REVERSE, PTBEG);
  245.     } while ((--n > 0) && status);
  246.  
  247.     /* Save away the match, or complain
  248.      * if not there.
  249.      */
  250.     if (status == TRUE)
  251.         savematch();
  252.     else
  253.         mlwrite("Not found");
  254.  
  255.     return(status);
  256. }
  257.  
  258. #if    MAGIC
  259. /*
  260.  * mcscanner -- Search for a meta-pattern in either direction.  If found,
  261.  *    reset the "." to be at the start or just after the match string,
  262.  *    and (perhaps) repaint the display.
  263.  */
  264. int    mcscanner(mcpatrn, direct, beg_or_end)
  265. MC    *mcpatrn;        /* pointer into pattern */
  266. int    direct;        /* which way to go.*/
  267. int    beg_or_end;    /* put point at beginning or end of pattern.*/
  268. {
  269.     LINE *curline;            /* current line during scan */
  270.     int curoff;            /* position within current line */
  271.     int c;                /* (dummy) char at current position */
  272.  
  273.     /* If we are going in reverse, then the 'end' is actually
  274.      * the beginning of the pattern.  Toggle it.
  275.      */
  276.     beg_or_end ^= direct;
  277.  
  278.     /*
  279.      * Save the old matchlen length, in case it is
  280.      * horribly different (closure) from the old length.
  281.      * This is terribly important for query-replace undo
  282.      * command.
  283.      */
  284.     mlenold = matchlen;
  285.  
  286.     /* Setup local scan pointers to global ".".
  287.      */
  288.     curline = curwp->w_dotp;
  289.     curoff  = curwp->w_doto;
  290.  
  291.     /* Scan each character until we hit the head link record.
  292.      */
  293.     while (!boundry(curline, curoff, direct))
  294.     {
  295.         /* Save the current position in case we need to
  296.          * restore it on a match, and initialize matchlen to
  297.          * zero in case we are doing a search for replacement.
  298.          */
  299.         matchline = curline;
  300.         matchoff = curoff;
  301.         matchlen = 0;
  302.  
  303.         if (amatch(mcpatrn, direct, &curline, &curoff))
  304.         {
  305.             /* A SUCCESSFULL MATCH!!!
  306.              * reset the global "." pointers.
  307.              */
  308.             if (beg_or_end == PTEND)    /* at end of string */
  309.             {
  310.                 curwp->w_dotp = curline;
  311.                 curwp->w_doto = curoff;
  312.             }
  313.             else        /* at beginning of string */
  314.             {
  315.                 curwp->w_dotp = matchline;
  316.                 curwp->w_doto = matchoff;
  317.             }
  318.  
  319.             curwp->w_flag |= WFMOVE; /* flag that we have moved */
  320.             return TRUE;
  321.         }
  322.  
  323.         /* Advance the cursor.
  324.          */
  325.         c = nextch(&curline, &curoff, direct);
  326.     }
  327.  
  328.     return FALSE;    /* We could not find a match.*/
  329. }
  330.  
  331. /*
  332.  * amatch -- Search for a meta-pattern in either direction.  Based on the
  333.  *    recursive routine amatch() (for "anchored match") in
  334.  *    Kernighan & Plauger's "Software Tools".
  335.  */
  336. static int    amatch(mcptr, direct, pcwline, pcwoff)
  337. register MC    *mcptr;    /* string to scan for */
  338. int        direct;        /* which way to go.*/
  339. LINE        **pcwline;    /* current line during scan */
  340. int        *pcwoff;    /* position within current line */
  341. {
  342.     register int c;            /* character at current position */
  343.     LINE *curline;            /* current line during scan */
  344.     int curoff;            /* position within current line */
  345.     int nchars;
  346.  
  347.     /* Set up local scan pointers to ".", and get
  348.      * the current character.  Then loop around
  349.      * the pattern pointer until success or failure.
  350.      */
  351.     curline = *pcwline;
  352.     curoff = *pcwoff;
  353.  
  354.     /* The beginning-of-line and end-of-line metacharacters
  355.      * do not compare against characters, they compare
  356.      * against positions.
  357.      * BOL is guaranteed to be at the start of the pattern
  358.      * for forward searches, and at the end of the pattern
  359.      * for reverse searches.  The reverse is true for EOL.
  360.      * So, for a start, we check for them on entry.
  361.      */
  362.     if (mcptr->mc_type == BOL)
  363.     {
  364.         if (curoff != 0)
  365.             return FALSE;
  366.         mcptr++;
  367.     }
  368.  
  369.     if (mcptr->mc_type == EOL)
  370.     {
  371.         if (curoff != llength(curline))
  372.             return FALSE;
  373.         mcptr++;
  374.     }
  375.  
  376.     while (mcptr->mc_type != MCNIL)
  377.     {
  378.         c = nextch(&curline, &curoff, direct);
  379.  
  380.         if (mcptr->mc_type & CLOSURE)
  381.         {
  382.             /* Try to match as many characters as possible
  383.              * against the current meta-character.  A
  384.              * newline never matches a closure.
  385.              */
  386.             nchars = 0;
  387.             while (c != '\n' && mceq(c, mcptr))
  388.             {
  389.                 c = nextch(&curline, &curoff, direct);
  390.                 nchars++;
  391.             }
  392.  
  393.             /* We are now at the character that made us
  394.              * fail.  Try to match the rest of the pattern.
  395.              * Shrink the closure by one for each failure.
  396.              * Since closure matches *zero* or more occurences
  397.              * of a pattern, a match may start even if the
  398.              * previous loop matched no characters.
  399.              */
  400.             mcptr++;
  401.  
  402.             for (;;)
  403.             {
  404.                 c = nextch(&curline, &curoff, direct ^ REVERSE);
  405.  
  406.                 if (amatch(mcptr, direct, &curline, &curoff))
  407.                 {
  408.                     matchlen += nchars;
  409.                     goto success;
  410.                 }
  411.  
  412.                 if (nchars-- == 0)
  413.                     return FALSE;
  414.             }
  415.         }
  416.         else            /* Not closure.*/
  417.         {
  418.             /* The only way we'd get a BOL metacharacter
  419.              * at this point is at the end of the reversed pattern.
  420.              * The only way we'd get an EOL metacharacter
  421.              * here is at the end of a regular pattern.
  422.              * So if we match one or the other, and are at
  423.              * the appropriate position, we are guaranteed success
  424.              * (since the next pattern character has to be MCNIL).
  425.              * Before we report success, however, we back up by
  426.              * one character, so as to leave the cursor in the
  427.              * correct position.  For example, a search for ")$"
  428.              * will leave the cursor at the end of the line, while
  429.              * a search for ")<NL>" will leave the cursor at the
  430.              * beginning of the next line.  This follows the
  431.              * notion that the meta-character '$' (and likewise
  432.              * '^') match positions, not characters.
  433.              */
  434.             if (mcptr->mc_type == BOL)
  435.                 if (curoff == llength(curline))
  436.                 {
  437.                     c = nextch(&curline, &curoff,
  438.                            direct ^ REVERSE);
  439.                     goto success;
  440.                 }
  441.                 else
  442.                     return FALSE;
  443.  
  444.             if (mcptr->mc_type == EOL)
  445.                 if (curoff == 0)
  446.                 {
  447.                     c = nextch(&curline, &curoff,
  448.                            direct ^ REVERSE);
  449.                     goto success;
  450.                 }
  451.                 else
  452.                     return FALSE;
  453.  
  454.             /* Neither BOL nor EOL, so go through
  455.              * the meta-character equal function.
  456.              */
  457.             if (!mceq(c, mcptr))
  458.                 return FALSE;
  459.         }
  460.  
  461.         /* Increment the length counter and
  462.          * advance the pattern pointer.
  463.          */
  464.         matchlen++;
  465.         mcptr++;
  466.     }            /* End of mcptr loop.*/
  467.  
  468.     /* A SUCCESSFULL MATCH!!!
  469.      * Reset the "." pointers.
  470.      */
  471. success:
  472.     *pcwline = curline;
  473.     *pcwoff  = curoff;
  474.  
  475.     return TRUE;
  476. }
  477. #endif
  478.  
  479. /*
  480.  * scanner -- Search for a pattern in either direction.  If found,
  481.  *    reset the "." to be at the start or just after the match string,
  482.  *    and (perhaps) repaint the display.
  483.  */
  484. int    scanner(patrn, direct, beg_or_end)
  485. char    *patrn;        /* string to scan for */
  486. int    direct;        /* which way to go.*/
  487. int    beg_or_end;    /* put point at beginning or end of pattern.*/
  488. {
  489.     register int    c;        /* character at current position */
  490.     register char    *patptr;    /* pointer into pattern */
  491.     LINE    *curline;        /* current line during scan */
  492.     int    curoff;            /* position within current line */
  493.     LINE    *scanline;        /* current line during scanning */
  494.     int    scanoff;        /* position in scanned line */
  495.  
  496.     /* If we are going in reverse, then the 'end' is actually
  497.      * the beginning of the pattern.  Toggle it.
  498.      */
  499.     beg_or_end ^= direct;
  500.  
  501.     /* Set up local pointers to global ".".
  502.      */
  503.     curline = curwp->w_dotp;
  504.     curoff = curwp->w_doto;
  505.  
  506.     /* Scan each character until we hit the head link record.
  507.      */
  508.     while (!boundry(curline, curoff, direct))
  509.     {
  510.         /* Save the current position in case we match
  511.          * the search string at this point.
  512.          */
  513.         matchline = curline;
  514.         matchoff = curoff;
  515.  
  516.         /* Get the character resolving newlines, and
  517.          * test it against first char in pattern.
  518.          */
  519.         c = nextch(&curline, &curoff, direct);
  520.  
  521.         if (eq(c, patrn[0]))    /* if we find it..*/
  522.         {
  523.             /* Setup scanning pointers.
  524.              */
  525.             scanline = curline;
  526.             scanoff = curoff;
  527.             patptr = &patrn[0];
  528.  
  529.             /* Scan through the pattern for a match.
  530.              */
  531.             while (*++patptr != '\0')
  532.             {
  533.                 c = nextch(&scanline, &scanoff, direct);
  534.  
  535.                 if (!eq(c, *patptr))
  536.                     goto fail;
  537.             }
  538.  
  539.             /* A SUCCESSFULL MATCH!!!
  540.              * reset the global "." pointers
  541.              */
  542.             if (beg_or_end == PTEND)    /* at end of string */
  543.             {
  544.                 curwp->w_dotp = scanline;
  545.                 curwp->w_doto = scanoff;
  546.             }
  547.             else        /* at beginning of string */
  548.             {
  549.                 curwp->w_dotp = matchline;
  550.                 curwp->w_doto = matchoff;
  551.             }
  552.  
  553.             curwp->w_flag |= WFMOVE; /* Flag that we have moved.*/
  554.             return TRUE;
  555.  
  556.         }
  557. fail:;            /* continue to search */
  558.     }
  559.  
  560.     return FALSE;    /* We could not find a match */
  561. }
  562.  
  563. /*
  564.  * eq -- Compare two characters.  The "bc" comes from the buffer, "pc"
  565.  *    from the pattern.  If we are not in EXACT mode, fold out the case.
  566.  */
  567. int    eq(bc, pc)
  568. register int    bc;
  569. register int    pc;
  570. {
  571.     if ((curwp->w_bufp->b_mode & MDEXACT) == 0)
  572.     {
  573.         if (islower(bc))
  574.             bc ^= DIFCASE;
  575.  
  576.         if (islower(pc))
  577.             pc ^= DIFCASE;
  578.     }
  579.  
  580.     return (bc == pc);
  581. }
  582.  
  583. /*
  584.  * readpattern -- Read a pattern.  Stash it in apat.  If it is the
  585.  *    search string, create the reverse pattern and the magic
  586.  *    pattern, assuming we are in MAGIC mode (and defined that way).
  587.  *    Apat is not updated if the user types in an empty line.  If
  588.  *    the user typed an empty line, and there is no old pattern, it is
  589.  *    an error.  Display the old pattern, in the style of Jeff Lomicka.
  590.  *    There is some do-it-yourself control expansion.  Change to using
  591.  *    <META> to delimit the end-of-pattern to allow <NL>s in the search
  592.  *    string. 
  593.  */
  594. static int    readpattern(prompt, apat, srch)
  595. char    *prompt;
  596. char    apat[];
  597. int    srch;
  598. {
  599.     int status;
  600.     char tpat[NPAT+20];
  601.  
  602.     strcpy(tpat, prompt);    /* copy prompt to output string */
  603.     strcat(tpat, " [");    /* build new prompt string */
  604.     expandp(&apat[0], &tpat[strlen(tpat)], NPAT/2);    /* add old pattern */
  605.     strcat(tpat, "]<META>: ");
  606.  
  607.     /* Read a pattern.  Either we get one,
  608.      * or we just get the META charater, and use the previous pattern.
  609.      * Then, if it's the search string, make a reversed pattern.
  610.      * *Then*, make the meta-pattern, if we are defined that way.
  611.      */
  612.     if ((status = mlreplyt(tpat, tpat, NPAT, metac)) == TRUE)
  613.     {
  614.         strcpy(apat, tpat);
  615.         if (srch)    /* If we are doing the search string.*/
  616.         {
  617.             matchlen = strlen(apat);
  618.             /* Reverse string copy.
  619.              */
  620.             rvstrcpy(tap, apat);
  621. #if    MAGIC
  622.             /* Only make the meta-pattern if in magic mode,
  623.              * since the pattern in question might have an
  624.              * invalid meta combination.
  625.              */
  626.             if ((curwp->w_bufp->b_mode & MDMAGIC) == 0)
  627.                 mcclear();
  628.             else
  629.                 status = mcstr();
  630. #endif
  631.         }
  632.     }
  633.     else if (status == FALSE && apat[0] != 0)    /* Old one */
  634.         status = TRUE;
  635.  
  636.     return(status);
  637. }
  638.  
  639. /*
  640.  * savematch -- We found the pattern?  Let's save it away.
  641.  */
  642.  
  643. savematch()
  644.  
  645. {
  646.     register char *ptr;    /* ptr into malloced last match string */
  647.     register int j;        /* index */
  648.     LINE *curline;        /* line of last match */
  649.     int curoff;        /* offset "      "    */
  650.  
  651.     /* free any existing match string */
  652.     if (patmatch != NULL)
  653.         free(patmatch);
  654.  
  655.     /* attempt to allocate a new one */
  656.     ptr = patmatch = malloc(matchlen + 1);
  657.     if (ptr == NULL)
  658.         return;
  659.  
  660.     /* save the match! */
  661.     curoff = matchoff;
  662.     curline = matchline;
  663.  
  664.     for (j = 0; j < matchlen; j++)
  665.         *ptr++ = nextch(&curline, &curoff, FORWARD);
  666.  
  667.     /* null terminate the match string */
  668.     *ptr = '\0';
  669. }
  670.  
  671. /*
  672.  * rvstrcpy -- Reverse string copy.
  673.  */
  674. rvstrcpy(rvstr, str)
  675. register char    *rvstr, *str;
  676. {
  677.     register int i;
  678.  
  679.     str += (i = strlen(str));
  680.  
  681.     while (i-- > 0)
  682.         *rvstr++ = *--str;
  683.  
  684.     *rvstr = '\0';
  685. }
  686.  
  687. /*
  688.  * sreplace -- Search and replace.
  689.  */
  690. sreplace(f, n)
  691.  
  692. int f;        /* default flag */
  693. int n;        /* # of repetitions wanted */
  694.  
  695. {
  696.     return(replaces(FALSE, f, n));
  697. }
  698.  
  699. /*
  700.  * qreplace -- search and replace with query.
  701.  */
  702. qreplace(f, n)
  703. int f;        /* default flag */
  704. int n;        /* # of repetitions wanted */
  705. {
  706.     return(replaces(TRUE, f, n));
  707. }
  708.  
  709. /*
  710.  * replaces -- Search for a string and replace it with another
  711.  *    string.  Query might be enabled (according to kind).
  712.  */
  713. static int    replaces(kind, f, n)
  714. int    kind;    /* Query enabled flag */
  715. int    f;    /* default flag */
  716. int    n;    /* # of repetitions wanted */
  717. {
  718.     register int status;    /* success flag on pattern inputs */
  719.     register int rlength;    /* length of replacement string */
  720.     register int numsub;    /* number of substitutions */
  721.     register int nummatch;    /* number of found matches */
  722.     int nlflag;        /* last char of search string a <NL>? */
  723.     int nlrepl;        /* was a replace done on the last line? */
  724.     char c;            /* input char for query */
  725.     char tpat[NPAT];    /* temporary to hold search pattern */
  726.     LINE *origline;        /* original "." position */
  727.     int origoff;        /* and offset (for . query option) */
  728.     LINE *lastline;        /* position of last replace and */
  729.     int lastoff;        /* offset (for 'u' query option) */
  730.  
  731.     if (curbp->b_mode & MDVIEW)    /* don't allow this command if    */
  732.         return(rdonly());    /* we are in read only mode    */
  733.  
  734.     /* Check for negative repetitions.
  735.      */
  736.     if (f && n < 0)
  737.         return(FALSE);
  738.  
  739.     /* Ask the user for the text of a pattern.
  740.      */
  741.     if ((status = readpattern(
  742.         (kind == FALSE ? "Replace" : "Query replace"), &pat[0], TRUE))
  743.                                 != TRUE)
  744.         return(status);
  745.  
  746.     /* Ask for the replacement string.
  747.      */
  748.     if ((status = readpattern("with", &rpat[0], FALSE)) == ABORT)
  749.         return(status);
  750.  
  751.     /* Find the length of the replacement string.
  752.      */
  753.     rlength = strlen(&rpat[0]);
  754.  
  755.     /* Set up flags so we can make sure not to do a recursive
  756.      * replace on the last line.
  757.      */
  758.     nlflag = (pat[matchlen - 1] == '\n');
  759.     nlrepl = FALSE;
  760.  
  761.     if (kind)
  762.     {
  763.         /* Build query replace question string.
  764.          */
  765.         strcpy(tpat, "Replace '");
  766.         expandp(&pat[0], &tpat[strlen(tpat)], NPAT/3);
  767.         strcat(tpat, "' with '");
  768.         expandp(&rpat[0], &tpat[strlen(tpat)], NPAT/3);
  769.         strcat(tpat, "'? ");
  770.  
  771.         /* Initialize last replaced pointers.
  772.          */
  773.         lastline = NULL;
  774.         lastoff = 0;
  775.     }
  776.  
  777.     /* Save original . position, init the number of matches and
  778.      * substitutions, and scan through the file.
  779.      */
  780.     origline = curwp->w_dotp;
  781.     origoff = curwp->w_doto;
  782.     numsub = 0;
  783.     nummatch = 0;
  784.  
  785.     while ( (f == FALSE || n > nummatch) &&
  786.         (nlflag == FALSE || nlrepl == FALSE) )
  787.     {
  788.         /* Search for the pattern.
  789.          * If we search with a regular expression,
  790.          * matchlen is reset to the true length of
  791.          * the matched string.
  792.          */
  793. #if    MAGIC
  794.         if ((magical && curwp->w_bufp->b_mode & MDMAGIC) != 0)
  795.         {
  796.             if (!mcscanner(&mcpat[0], FORWARD, PTBEG))
  797.                 break;
  798.         }
  799.         else
  800. #endif
  801.             if (!scanner(&pat[0], FORWARD, PTBEG))
  802.                 break;        /* all done */
  803.  
  804.         ++nummatch;    /* Increment # of matches */
  805.  
  806.         /* Check if we are on the last line.
  807.          */
  808.         nlrepl = (lforw(curwp->w_dotp) == curwp->w_bufp->b_linep);
  809.  
  810.         /* Check for query.
  811.          */
  812.         if (kind)
  813.         {
  814.             /* Get the query.
  815.              */
  816. pprompt:        mlwrite(&tpat[0], &pat[0], &rpat[0]);
  817. qprompt:
  818.             update(TRUE);  /* show the proposed place to change */
  819.             c = tgetc();            /* and input */
  820.             mlwrite("");            /* and clear it */
  821.  
  822.             /* And respond appropriately.
  823.              */
  824.             switch (c)
  825.             {
  826.                 case 'y':    /* yes, substitute */
  827.                 case ' ':
  828.                     savematch();
  829.                     break;
  830.  
  831.                 case 'n':    /* no, onword */
  832.                     forwchar(FALSE, 1);
  833.                     continue;
  834.  
  835.                 case '!':    /* yes/stop asking */
  836.                     kind = FALSE;
  837.                     break;
  838.  
  839.                 case 'u':    /* undo last and re-prompt */
  840.  
  841.                     /* Restore old position.
  842.                      */
  843.                     if (lastline == NULL)
  844.                     {
  845.                         /* There is nothing to undo.
  846.                          */
  847.                         TTbeep();
  848.                         goto pprompt;
  849.                     }
  850.                     curwp->w_dotp = lastline;
  851.                     curwp->w_doto = lastoff;
  852.                     lastline = NULL;
  853.                     lastoff = 0;
  854.  
  855.                     /* Delete the new string.
  856.                      */
  857.                     backchar(FALSE, rlength);
  858.                     status = delins(rlength, patmatch);
  859.                     if (status != TRUE)
  860.                         return (status);
  861.  
  862.                     /* Record one less substitution,
  863.                      * backup, and reprompt.
  864.                      */
  865.                     --numsub;
  866.                     backchar(FALSE, mlenold);
  867.                     goto pprompt;
  868.  
  869.                 case '.':    /* abort! and return */
  870.                     /* restore old position */
  871.                     curwp->w_dotp = origline;
  872.                     curwp->w_doto = origoff;
  873.                     curwp->w_flag |= WFMOVE;
  874.  
  875.                 case BELL:    /* abort! and stay */
  876.                     mlwrite("Aborted!");
  877.                     return(FALSE);
  878.  
  879.                 default:    /* bitch and beep */
  880.                     TTbeep();
  881.  
  882.                 case '?':    /* help me */
  883.                     mlwrite(
  884. "(Y)es, (N)o, (!)Do rest, (U)ndo last, (^G)Abort, (.)Abort back, (?)Help: ");
  885.                     goto qprompt;
  886.  
  887.             }    /* end of switch */
  888.         }    /* end of "if kind" */
  889.  
  890.         /*
  891.          * Delete the sucker, and insert its
  892.          * replacement.
  893.          */
  894.         status = delins(matchlen, &rpat[0]);
  895.         if (status != TRUE)
  896.             return (status);
  897.  
  898.         /* Save where we are if we might undo this....
  899.          */
  900.         if (kind)
  901.         {
  902.             lastline = curwp->w_dotp;
  903.             lastoff = curwp->w_doto;
  904.         }
  905.  
  906.         numsub++;    /* increment # of substitutions */
  907.     }
  908.  
  909.     /* And report the results.
  910.      */
  911.     mlwrite("%d substitutions", numsub);
  912.     return(TRUE);
  913. }
  914.  
  915. /*
  916.  * delins -- Delete a specified length from the current
  917.  *    point, then insert the string.
  918.  */
  919. delins(dlength, instr)
  920. int    dlength;
  921. char    *instr;
  922. {
  923.     int    status;
  924.     char    tmpc;
  925.  
  926.     /* Zap what we gotta,
  927.      * and insert its replacement.
  928.      */
  929.     if (!(status = ldelete((long) dlength, FALSE)))
  930.     {
  931.         mlwrite("%%ERROR while deleting");
  932.         return(FALSE);
  933.     }
  934.     else
  935.         while (tmpc = *instr)
  936.         {
  937.             status = (tmpc == '\n'? lnewline(): linsert(1, tmpc));
  938.  
  939.             /* Insertion error?
  940.              */
  941.             if (!status)
  942.             {
  943.                 mlwrite("%%Out of memory while inserting");
  944.                 break;
  945.             }
  946.             instr++;
  947.         }
  948.     return (status);
  949. }
  950.  
  951. /*
  952.  * expandp -- Expand control key sequences for output.
  953.  */
  954. expandp(srcstr, deststr, maxlength)
  955. char *srcstr;    /* string to expand */
  956. char *deststr;    /* destination of expanded string */
  957. int maxlength;    /* maximum chars in destination */
  958. {
  959.     char c;        /* current char to translate */
  960.  
  961.     /* Scan through the string.
  962.      */
  963.     while ((c = *srcstr++) != 0)
  964.     {
  965.         if (c == '\n')        /* it's a newline */
  966.         {
  967.             *deststr++ = '<';
  968.             *deststr++ = 'N';
  969.             *deststr++ = 'L';
  970.             *deststr++ = '>';
  971.             maxlength -= 4;
  972.         }
  973.         else if (c < 0x20 || c == 0x7f)    /* control character */
  974.         {
  975.             *deststr++ = '^';
  976.             *deststr++ = c ^ 0x40;
  977.             maxlength -= 2;
  978.         }
  979.         else if (c == '%')
  980.         {
  981.             *deststr++ = '%';
  982.             *deststr++ = '%';
  983.             maxlength -= 2;
  984.         }
  985.         else            /* any other character */
  986.         {
  987.             *deststr++ = c;
  988.             maxlength--;
  989.         }
  990.  
  991.         /* check for maxlength */
  992.         if (maxlength < 4)
  993.         {
  994.             *deststr++ = '$';
  995.             *deststr = '\0';
  996.             return(FALSE);
  997.         }
  998.     }
  999.     *deststr = '\0';
  1000.     return(TRUE);
  1001. }
  1002.  
  1003. /*
  1004.  * boundry -- Return information depending on whether we may search no
  1005.  *    further.  Beginning of file and end of file are the obvious
  1006.  *    cases, but we may want to add further optional boundry restrictions
  1007.  *    in future, a' la VMS EDT.  At the moment, just return TRUE or
  1008.  *    FALSE depending on if a boundry is hit (ouch).
  1009.  */
  1010. int    boundry(curline, curoff, dir)
  1011. LINE    *curline;
  1012. int    curoff, dir;
  1013. {
  1014.     register int    border;
  1015.  
  1016.     if (dir == FORWARD)
  1017.     {
  1018.         border = (curoff == llength(curline)) &&
  1019.              (lforw(curline) == curbp->b_linep);
  1020.     }
  1021.     else
  1022.     {
  1023.         border = (curoff == 0) &&
  1024.              (lback(curline) == curbp->b_linep);
  1025.     }
  1026.     return (border);
  1027. }
  1028.  
  1029. /*
  1030.  * nextch -- retrieve the next/previous character in the buffer,
  1031.  *    and advance/retreat the point.
  1032.  *    The order in which this is done is significant, and depends
  1033.  *    upon the direction of the search.  Forward searches look at
  1034.  *    the current character and move, reverse searches move and
  1035.  *    look at the character.
  1036.  */
  1037. static int    nextch(pcurline, pcuroff, dir)
  1038. LINE    **pcurline;
  1039. int    *pcuroff;
  1040. int    dir;
  1041. {
  1042.     register LINE    *curline;
  1043.     register int    curoff;
  1044.     register int    c;
  1045.  
  1046.     curline = *pcurline;
  1047.     curoff = *pcuroff;
  1048.  
  1049.     if (dir == FORWARD)
  1050.     {
  1051.         if (curoff == llength(curline))        /* if at EOL */
  1052.         {
  1053.             curline = lforw(curline);    /* skip to next line */
  1054.             curoff = 0;
  1055.             c = '\n';            /* and return a <NL> */
  1056.         }
  1057.         else
  1058.             c = lgetc(curline, curoff++);    /* get the char */
  1059.     }
  1060.     else            /* Reverse.*/
  1061.     {
  1062.         if (curoff == 0)
  1063.         {
  1064.             curline = lback(curline);
  1065.             curoff = llength(curline);
  1066.             c = '\n';
  1067.         }
  1068.         else
  1069.             c = lgetc(curline, --curoff);
  1070.  
  1071.     }
  1072.     *pcurline = curline;
  1073.     *pcuroff = curoff;
  1074.  
  1075.     return (c);
  1076. }
  1077.  
  1078. #if    MAGIC
  1079. /*
  1080.  * mcstr -- Set up the 'magic' array.  The closure symbol is taken as
  1081.  *    a literal character when (1) it is the first character in the
  1082.  *    pattern, and (2) when preceded by a symbol that does not allow
  1083.  *    closure, such as a newline, beginning of line symbol, or another
  1084.  *    closure symbol.
  1085.  *
  1086.  *    Coding comment (jmg):  yes, i know i have gotos that are, strictly
  1087.  *    speaking, unnecessary.  But right now we are so cramped for
  1088.  *    code space that i will grab what i can in order to remain
  1089.  *    within the 64K limit.  C compilers actually do very little
  1090.  *    in the way of optimizing - they expect you to do that.
  1091.  */
  1092. int    mcstr()
  1093. {
  1094.     MC    *mcptr, *rtpcm;
  1095.     char    *patptr;
  1096.      int    mj;
  1097.      int    pchr;
  1098.      int    status = TRUE;
  1099.      int    does_closure = FALSE;
  1100.  
  1101.     /* If we had metacharacters in the MC array previously,
  1102.      * free up any bitmaps that may have been allocated.
  1103.      */
  1104.     if (magical)
  1105.         mcclear();
  1106.  
  1107.     magical = FALSE;
  1108.     mj = 0;
  1109.     mcptr = &mcpat[0];
  1110.     patptr = &pat[0];
  1111.  
  1112.     while ((pchr = *patptr) && status)
  1113.     {
  1114.         switch (pchr)
  1115.         {
  1116.             case MC_CCL:
  1117.                 status = cclmake(&patptr, mcptr);
  1118.                 magical = TRUE;
  1119.                 does_closure = TRUE;
  1120.                 break;
  1121.             case MC_BOL:
  1122.                 if (mj != 0)
  1123.                     goto litcase;
  1124.  
  1125.                 mcptr->mc_type = BOL;
  1126.                 magical = TRUE;
  1127.                 does_closure = FALSE;
  1128.                 break;
  1129.             case MC_EOL:
  1130.                 if (*(patptr + 1) != '\0')
  1131.                     goto litcase;
  1132.  
  1133.                 mcptr->mc_type = EOL;
  1134.                 magical = TRUE;
  1135.                 does_closure = FALSE;
  1136.                 break;
  1137.             case MC_ANY:
  1138.                 mcptr->mc_type = ANY;
  1139.                 magical = TRUE;
  1140.                 does_closure = TRUE;
  1141.                 break;
  1142.             case MC_CLOSURE:
  1143.                 /* Does the closure symbol mean closure here?
  1144.                  * If so, back up to the previous element
  1145.                  * and indicate it is enclosed.
  1146.                  */
  1147.                 if (!does_closure)
  1148.                     goto litcase;
  1149.                 mj--;
  1150.                 mcptr--;
  1151.                 mcptr->mc_type |= CLOSURE;
  1152.                 magical = TRUE;
  1153.                 does_closure = FALSE;
  1154.                 break;
  1155.  
  1156.             /* Note: no break between MC_ESC case and the default.
  1157.              */
  1158.             case MC_ESC:
  1159.                 if (*(patptr + 1) != '\0')
  1160.                 {
  1161.                     pchr = *++patptr;
  1162.                     magical = TRUE;
  1163.                 }
  1164.             default:
  1165. litcase:            mcptr->mc_type = LITCHAR;
  1166.                 mcptr->u.lchar = pchr;
  1167.                 does_closure = (pchr != '\n');
  1168.                 break;
  1169.         }        /* End of switch.*/
  1170.         mcptr++;
  1171.         patptr++;
  1172.         mj++;
  1173.     }        /* End of while.*/
  1174.  
  1175.     /* Close off the meta-string.
  1176.      */
  1177.     mcptr->mc_type = MCNIL;
  1178.  
  1179.     /* Set up the reverse array, if the status is good.  Please note the
  1180.      * structure assignment - your compiler may not like that.
  1181.      * If the status is not good, nil out the meta-pattern.
  1182.      * The only way the status would be bad is from the cclmake()
  1183.      * routine, and the bitmap for that member is guarenteed to be
  1184.      * freed.  So we stomp a MCNIL value there, and call mcclear()
  1185.      * to free any other bitmaps.
  1186.      */
  1187.     if (status)
  1188.     {
  1189.         rtpcm = &tapcm[0];
  1190.         while (--mj >= 0)
  1191.         {
  1192. #if    LATTICE
  1193.             movmem(--mcptr, rtpcm++, sizeof (MC));
  1194. #endif
  1195.  
  1196. #if    MWC86 | AZTEC | MSC | VMS | USG | BSD | V7
  1197.             *rtpcm++ = *--mcptr;
  1198. #endif
  1199.         }
  1200.         rtpcm->mc_type = MCNIL;
  1201.     }
  1202.     else
  1203.     {
  1204.         (--mcptr)->mc_type = MCNIL;
  1205.         mcclear();
  1206.     }
  1207.  
  1208.     return(status);
  1209. }
  1210.  
  1211. /*
  1212.  * mcclear -- Free up any CCL bitmaps, and MCNIL the MC arrays.
  1213.  */
  1214. mcclear()
  1215. {
  1216.     register MC    *mcptr;
  1217.  
  1218.     mcptr = &mcpat[0];
  1219.  
  1220.     while (mcptr->mc_type != MCNIL)
  1221.     {
  1222.         if ((mcptr->mc_type & MASKCL) == CCL ||
  1223.             (mcptr->mc_type & MASKCL) == NCCL)
  1224.             free(mcptr->u.cclmap);
  1225.         mcptr++;
  1226.     }
  1227.     mcpat[0].mc_type = tapcm[0].mc_type = MCNIL;
  1228. }
  1229.  
  1230. /*
  1231.  * mceq -- meta-character equality with a character.  In Kernighan & Plauger's
  1232.  *    Software Tools, this is the function omatch(), but i felt there
  1233.  *    were too many functions with the 'match' name already.
  1234.  */
  1235. static int    mceq(bc, mt)
  1236. int    bc;
  1237. MC    *mt;
  1238. {
  1239.     register int result;
  1240.  
  1241.     switch (mt->mc_type & MASKCL)
  1242.     {
  1243.         case LITCHAR:
  1244.             result = eq(bc, mt->u.lchar);
  1245.             break;
  1246.  
  1247.         case ANY:
  1248.             result = (bc != '\n');
  1249.             break;
  1250.  
  1251.         case CCL:
  1252.             if (!(result = biteq(bc, mt->u.cclmap)))
  1253.             {
  1254.                 if ((curwp->w_bufp->b_mode & MDEXACT) == 0 &&
  1255.                     (isletter(bc)))
  1256.                 {
  1257.                     result = biteq(CHCASE(bc), mt->u.cclmap);
  1258.                 }
  1259.             }
  1260.             break;
  1261.  
  1262.         case NCCL:
  1263.             result = !biteq(bc, mt->u.cclmap);
  1264.  
  1265.             if ((curwp->w_bufp->b_mode & MDEXACT) == 0 &&
  1266.                 (isletter(bc)))
  1267.             {
  1268.                 result &= !biteq(CHCASE(bc), mt->u.cclmap);
  1269.             }
  1270.             break;
  1271.  
  1272.         default:
  1273.             mlwrite("mceq: what is %d?", mt->mc_type);
  1274.             result = FALSE;
  1275.             break;
  1276.  
  1277.     }    /* End of switch.*/
  1278.  
  1279.     return (result);
  1280. }
  1281.  
  1282. /*
  1283.  * cclmake -- create the bitmap for the character class.
  1284.  *    ppatptr is left pointing to the end-of-character-class character,
  1285.  *    so that a loop may automatically increment with safety.
  1286.  */
  1287. static int    cclmake(ppatptr, mcptr)
  1288. char    **ppatptr;
  1289. MC    *mcptr;
  1290. {
  1291.     BITMAP        clearbits();
  1292.     BITMAP        bmap;
  1293.     register char    *patptr;
  1294.     register int    pchr, ochr;
  1295.  
  1296.     if ((bmap = clearbits()) == NULL)
  1297.     {
  1298.         mlwrite("%%Out of memory");
  1299.         return FALSE;
  1300.     }
  1301.  
  1302.     mcptr->u.cclmap = bmap;
  1303.     patptr = *ppatptr;
  1304.  
  1305.     /*
  1306.      * Test the initial character(s) in ccl for
  1307.      * special cases - negate ccl, or an end ccl
  1308.      * character as a first character.  Anything
  1309.      * else gets set in the bitmap.
  1310.      */
  1311.     if (*++patptr == MC_NCCL)
  1312.     {
  1313.         patptr++;
  1314.         mcptr->mc_type = NCCL;
  1315.     }
  1316.     else
  1317.         mcptr->mc_type = CCL;
  1318.  
  1319.     if ((ochr = *patptr) == MC_ECCL)
  1320.     {
  1321.         mlwrite("%%No characters in character class");
  1322.         return (FALSE);
  1323.     }
  1324.     else
  1325.     {
  1326.         if (ochr == MC_ESC)
  1327.             ochr = *++patptr;
  1328.  
  1329.         setbit(ochr, bmap);
  1330.         patptr++;
  1331.     }
  1332.  
  1333.     while (ochr != '\0' && (pchr = *patptr) != MC_ECCL)
  1334.     {
  1335.         switch (pchr)
  1336.         {
  1337.             /* Range character loses its meaning
  1338.              * if it is the last character in
  1339.              * the class.
  1340.              */
  1341.             case MC_RCCL:
  1342.                 if (*(patptr + 1) == MC_ECCL)
  1343.                     setbit(pchr, bmap);
  1344.                 else
  1345.                 {
  1346.                     pchr = *++patptr;
  1347.                     while (++ochr <= pchr)
  1348.                         setbit(ochr, bmap);
  1349.                 }
  1350.                 break;
  1351.  
  1352.             /* Note: no break between case MC_ESC and the default.
  1353.              */
  1354.             case MC_ESC:
  1355.                 pchr = *++patptr;
  1356.             default:
  1357.                 setbit(pchr, bmap);
  1358.                 break;
  1359.         }
  1360.         patptr++;
  1361.         ochr = pchr;
  1362.     }
  1363.  
  1364.     *ppatptr = patptr;
  1365.  
  1366.     if (ochr == '\0')
  1367.     {
  1368.         mlwrite("%%Character class not ended");
  1369.         free(bmap);
  1370.         return FALSE;
  1371.     }
  1372.     return TRUE;
  1373. }
  1374.  
  1375. /*
  1376.  * biteq -- is the character in the bitmap?
  1377.  */
  1378. static int    biteq(bc, cclmap)
  1379. int    bc;
  1380. BITMAP    cclmap;
  1381. {
  1382.     if (bc >= HICHAR)
  1383.         return FALSE;
  1384.  
  1385.     return( (*(cclmap + (bc >> 3)) & BIT(bc & 7))? TRUE: FALSE );
  1386. }
  1387.  
  1388. /*
  1389.  * clearbits -- Allocate and zero out a CCL bitmap.
  1390.  */
  1391. static    BITMAP clearbits()
  1392. {
  1393.     char        *malloc();
  1394.  
  1395.     BITMAP        cclstart, cclmap;
  1396.     register int    j;
  1397.  
  1398.     if ((cclmap = cclstart = (BITMAP) malloc(HIBYTE)) != NULL)
  1399.         for (j = 0; j < HIBYTE; j++)
  1400.             *cclmap++ = 0;
  1401.  
  1402.     return (cclstart);
  1403. }
  1404.  
  1405. /*
  1406.  * setbit -- Set a bit (ON only) in the bitmap.
  1407.  */
  1408. static    setbit(bc, cclmap)
  1409. int    bc;
  1410. BITMAP    cclmap;
  1411. {
  1412.     if (bc < HICHAR)
  1413.         *(cclmap + (bc >> 3)) |= BIT(bc & 7);
  1414. }
  1415. #endif
  1416.