home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / less3292.zip / search.c < prev    next >
C/C++ Source or Header  |  1996-10-10  |  26KB  |  1,224 lines
  1. /*
  2.  * Copyright (c) 1984,1985,1989,1994,1995,1996  Mark Nudelman
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice in the documentation and/or other materials provided with 
  12.  *    the distribution.
  13.  *
  14.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY
  15.  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 
  17.  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE
  18.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
  19.  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
  20.  * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 
  21.  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 
  22.  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE 
  23.  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN 
  24.  * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25.  */
  26.  
  27.  
  28. /*
  29.  * Routines to search a file for a pattern.
  30.  */
  31.  
  32. #include "less.h"
  33. #include "position.h"
  34.  
  35. #define    MINPOS(a,b)    (((a) < (b)) ? (a) : (b))
  36. #define    MAXPOS(a,b)    (((a) > (b)) ? (a) : (b))
  37.  
  38. #if HAVE_POSIX_REGCOMP
  39. #include <regex.h>
  40. #ifdef REG_EXTENDED
  41. #define    REGCOMP_FLAG    REG_EXTENDED
  42. #else
  43. #define    REGCOMP_FLAG    0
  44. #endif
  45. #endif
  46. #if HAVE_RE_COMP
  47. char *re_comp();
  48. int re_exec();
  49. #endif
  50. #if HAVE_REGCMP
  51. char *regcmp();
  52. char *regex();
  53. extern char *__loc1;
  54. #endif
  55. #if HAVE_V8_REGCOMP
  56. #include "regexp.h"
  57. #endif
  58.  
  59. static int match();
  60.  
  61. extern int sigs;
  62. extern int how_search;
  63. extern int caseless;
  64. extern int linenums;
  65. extern int sc_height;
  66. extern int jump_sline;
  67. extern int bs_mode;
  68. #if HILITE_SEARCH
  69. extern int hilite_search;
  70. extern int screen_trashed;
  71. extern int size_linebuf;
  72. extern int squished;
  73. static int hide_hilite;
  74. static POSITION prep_startpos;
  75. static POSITION prep_endpos;
  76.  
  77. struct hilite
  78. {
  79.     struct hilite *hl_next;
  80.     POSITION hl_startpos;
  81.     POSITION hl_endpos;
  82. };
  83. static struct hilite hilite_anchor = { NULL };
  84. #define    hl_first    hl_next
  85. #endif
  86.  
  87. /*
  88.  * These are the static variables that represent the "remembered"
  89.  * search pattern.  
  90.  */
  91. #if HAVE_POSIX_REGCOMP
  92. static regex_t *regpattern = NULL;
  93. #endif
  94. #if HAVE_RE_COMP
  95. int re_pattern = 0;
  96. #endif
  97. #if HAVE_REGCMP
  98. static char *cpattern = NULL;
  99. #endif
  100. #if HAVE_V8_REGCOMP
  101. static struct regexp *regpattern = NULL;
  102. #endif
  103.  
  104. static int is_caseless;
  105. static int is_ucase_pattern;
  106. static int last_search_type;
  107. static char *last_pattern = NULL;
  108.  
  109. /*
  110.  * Convert text.  Perform one or more of these transformations:
  111.  */
  112. #define    CVT_TO_LC    01    /* Convert upper-case to lower-case */
  113. #define    CVT_BS        02    /* Do backspace processing */
  114.  
  115.     static void
  116. cvt_text(odst, osrc, ops)
  117.     char *odst;
  118.     char *osrc;
  119.     int ops;
  120. {
  121.     register char *dst;
  122.     register char *src;
  123.  
  124.     for (src = osrc, dst = odst;  *src != '\0';  src++, dst++)
  125.     {
  126.         if ((ops & CVT_TO_LC) && isupper((unsigned char) *src))
  127.             /* Convert uppercase to lowercase. */
  128.             *dst = tolower((unsigned char) *src);
  129.         else if ((ops & CVT_BS) && *src == '\b' && dst > odst)
  130.             /* Delete BS and preceding char. */
  131.             dst -= 2;
  132.         else 
  133.             /* Just copy. */
  134.             *dst = *src;
  135.     }
  136.     *dst = '\0';
  137. }
  138.  
  139. /*
  140.  * Are there any uppercase letters in this string?
  141.  */
  142.     static int
  143. is_ucase(s)
  144.     char *s;
  145. {
  146.     register char *p;
  147.  
  148.     for (p = s;  *p != '\0';  p++)
  149.         if (isupper((unsigned char) *p))
  150.             return (1);
  151.     return (0);
  152. }
  153.  
  154. /*
  155.  * Is there a previous (remembered) search pattern?
  156.  */
  157.     static int
  158. prev_pattern()
  159. {
  160.     if (last_search_type & SRCH_NO_REGEX)
  161.         return (last_pattern != NULL);
  162. #if HAVE_POSIX_REGCOMP
  163.     return (regpattern != NULL);
  164. #endif
  165. #if HAVE_RE_COMP
  166.     return (re_pattern != 0);
  167. #endif
  168. #if HAVE_REGCMP
  169.     return (cpattern != NULL);
  170. #endif
  171. #if HAVE_V8_REGCOMP
  172.     return (regpattern != NULL);
  173. #endif
  174. #if NO_REGEX
  175.     return (last_pattern != NULL);
  176. #endif
  177. }
  178.  
  179. #if HILITE_SEARCH
  180. /*
  181.  * Repaint the hilites currently displayed on the screen.
  182.  * Repaint each line which contains highlighted text.
  183.  * If on==0, force all hilites off.
  184.  */
  185.     public void
  186. repaint_hilite(on)
  187.     int on;
  188. {
  189.     int slinenum;
  190.     POSITION pos;
  191.     POSITION epos;
  192.     int save_hide_hilite;
  193.     extern int can_goto_line;
  194.  
  195.     if (squished)
  196.         repaint();
  197.  
  198.     save_hide_hilite = hide_hilite;
  199.     if (!on)
  200.     {
  201.         if (hide_hilite)
  202.             return;
  203.         hide_hilite = 1;
  204.     }
  205.  
  206.     if (!can_goto_line)
  207.     {
  208.         repaint();
  209.         hide_hilite = save_hide_hilite;
  210.         return;
  211.     }
  212.  
  213.     for (slinenum = TOP;  slinenum < TOP + sc_height-1;  slinenum++)
  214.     {
  215.         pos = position(slinenum);
  216.         if (pos == NULL_POSITION)
  217.             continue;
  218.         epos = position(slinenum+1);
  219.         /*
  220.          * If any character in the line is highlighted, 
  221.          * repaint the line.
  222.          */
  223.         if (is_hilited(pos, epos, 1))
  224.         {
  225.             (void) forw_line(pos);
  226.             goto_line(slinenum);
  227.             put_line();
  228.         }
  229.     }
  230.     hide_hilite = save_hide_hilite;
  231. }
  232. #endif
  233.  
  234. /*
  235.  * Hide search string highlighting.
  236.  */
  237.     public void
  238. undo_search()
  239. {
  240.     if (!prev_pattern())
  241.     {
  242.         error("No previous regular expression", NULL_PARG);
  243.         return;
  244.     }
  245. #if HILITE_SEARCH
  246.     hide_hilite = !hide_hilite;
  247.     repaint_hilite(1);
  248. #endif
  249. }
  250.  
  251. /*
  252.  * Compile a search pattern, for future use by match_pattern.
  253.  */
  254.     static int
  255. compile_pattern(pattern, search_type)
  256.     char *pattern;
  257.     int search_type;
  258. {
  259.     if ((search_type & SRCH_NO_REGEX) == 0)
  260.     {
  261. #if HAVE_POSIX_REGCOMP
  262.         regex_t *s = (regex_t *) ecalloc(1, sizeof(regex_t));
  263.         if (regcomp(s, pattern, REGCOMP_FLAG))
  264.         {
  265.             free(s);
  266.             error("Invalid pattern", NULL_PARG);
  267.             return (-1);
  268.         }
  269.         if (regpattern != NULL)
  270.             regfree(regpattern);
  271.         regpattern = s;
  272. #endif
  273. #if HAVE_RE_COMP
  274.         PARG parg;
  275.         if ((parg.p_string = re_comp(pattern)) != NULL)
  276.         {
  277.             error("%s", &parg);
  278.             return (-1);
  279.         }
  280.         re_pattern = 1;
  281. #endif
  282. #if HAVE_REGCMP
  283.         char *s;
  284.         if ((s = regcmp(pattern, 0)) == NULL)
  285.         {
  286.             error("Invalid pattern", NULL_PARG);
  287.             return (-1);
  288.         }
  289.         if (cpattern != NULL)
  290.             free(cpattern);
  291.         cpattern = s;
  292. #endif
  293. #if HAVE_V8_REGCOMP
  294.         struct regexp *s;
  295.         if ((s = regcomp(pattern)) == NULL)
  296.         {
  297.             /*
  298.              * regcomp has already printed an error message 
  299.              * via regerror().
  300.              */
  301.             return (-1);
  302.         }
  303.         if (regpattern != NULL)
  304.             free(regpattern);
  305.         regpattern = s;
  306. #endif
  307.     }
  308.  
  309.     if (last_pattern != NULL)
  310.         free(last_pattern);
  311.     last_pattern = (char *) calloc(1, strlen(pattern)+1);
  312.     if (last_pattern != NULL)
  313.         strcpy(last_pattern, pattern);
  314.  
  315.     last_search_type = search_type;
  316.     return (0);
  317. }
  318.  
  319. /*
  320.  * Forget that we have a compiled pattern.
  321.  */
  322.     static void
  323. uncompile_pattern()
  324. {
  325. #if HAVE_POSIX_REGCOMP
  326.     if (regpattern != NULL)
  327.         regfree(regpattern);
  328.     regpattern = NULL;
  329. #endif
  330. #if HAVE_RE_COMP
  331.     re_pattern = 0;
  332. #endif
  333. #if HAVE_REGCMP
  334.     if (cpattern != NULL)
  335.         free(cpattern);
  336.     cpattern = NULL;
  337. #endif
  338. #if HAVE_V8_REGCOMP
  339.     if (regpattern != NULL)
  340.         free(regpattern);
  341.     regpattern = NULL;
  342. #endif
  343.     last_pattern = NULL;
  344. }
  345.  
  346. /*
  347.  * Perform a pattern match with the previously compiled pattern.
  348.  * Set sp and ep to the start and end of the matched string.
  349.  */
  350.     static int
  351. match_pattern(line, sp, ep)
  352.     char *line;
  353.     char **sp;
  354.     char **ep;
  355. {
  356.     int matched;
  357.  
  358.     if (last_search_type & SRCH_NO_REGEX)
  359.         return (match(last_pattern, line, sp, ep));
  360.  
  361. #if HAVE_POSIX_REGCOMP
  362.     {
  363.         regmatch_t rm;
  364.         matched = !regexec(regpattern, line, 1, &rm, 0);
  365.         if (!matched)
  366.             return (0);
  367.         *sp = line + rm.rm_so;
  368.         *ep = line + rm.rm_eo;
  369.     }
  370. #endif
  371. #if HAVE_RE_COMP
  372.     matched = (re_exec(line) == 1);
  373.     /*
  374.      * re_exec doesn't seem to provide a way to get the matched string.
  375.      */
  376.     *sp = *ep = NULL;
  377. #endif
  378. #if HAVE_REGCMP
  379.     *ep = regex(cpattern, line);
  380.     matched = (*ep != NULL);
  381.     if (!matched)
  382.         return (0);
  383.     *sp = __loc1;
  384. #endif
  385. #if HAVE_V8_REGCOMP
  386.     matched = regexec(regpattern, line);
  387.     if (!matched)
  388.         return (0);
  389.     *sp = regpattern->startp[0];
  390.     *ep = regpattern->endp[0];
  391. #endif
  392. #if NO_REGEX
  393.     matched = match(last_pattern, line, sp, ep);
  394. #endif
  395.     return (matched);
  396. }
  397.  
  398. #if HILITE_SEARCH
  399. /*
  400.  * Clear the hilite list.
  401.  */
  402.     public void
  403. clr_hilite()
  404. {
  405.     struct hilite *hl;
  406.     struct hilite *nexthl;
  407.  
  408.     for (hl = hilite_anchor.hl_first;  hl != NULL;  hl = nexthl)
  409.     {
  410.         nexthl = hl->hl_next;
  411.         free((void*)hl);
  412.     }
  413.     hilite_anchor.hl_first = NULL;
  414.     prep_startpos = prep_endpos = NULL_POSITION;
  415. }
  416.  
  417. /*
  418.  * Should any characters in a specified range be highlighted?
  419.  * If nohide is nonzero, don't consider hide_hilite.
  420.  */
  421.     public int
  422. is_hilited(pos, epos, nohide)
  423.     POSITION pos;
  424.     POSITION epos;
  425.     int nohide;
  426. {
  427.     struct hilite *hl;
  428.  
  429.     if (hilite_search == 0)
  430.         /*
  431.          * Not doing highlighting.
  432.          */
  433.         return (0);
  434.  
  435.     if (!nohide && hide_hilite)
  436.         /*
  437.          * Highlighting is hidden.
  438.          */
  439.         return (0);
  440.  
  441.     /*
  442.      * Look at each highlight and see if any part of it falls in the range.
  443.      */
  444.     for (hl = hilite_anchor.hl_first;  hl != NULL;  hl = hl->hl_next)
  445.     {
  446.         if (hl->hl_endpos > pos &&
  447.             (epos == NULL_POSITION || epos > hl->hl_startpos))
  448.             return (1);
  449.     }
  450.     return (0);
  451. }
  452.  
  453. /*
  454.  * Add a new hilite to a hilite list.
  455.  */
  456.     static void
  457. add_hilite(anchor, hl)
  458.     struct hilite *anchor;
  459.     struct hilite *hl;
  460. {
  461.     struct hilite *ihl;
  462.  
  463.     /*
  464.      * Hilites are sorted in the list; find where new one belongs.
  465.      * Insert new one after ihl.
  466.      */
  467.     for (ihl = anchor;  ihl->hl_next != NULL;  ihl = ihl->hl_next)
  468.     {
  469.         if (ihl->hl_next->hl_startpos > hl->hl_startpos)
  470.             break;
  471.     }
  472.  
  473.     /*
  474.      * Truncate hilite so it doesn't overlap any existing ones
  475.      * above and below it.
  476.      */
  477.     if (ihl != anchor)
  478.         hl->hl_startpos = MAXPOS(hl->hl_startpos, ihl->hl_endpos);
  479.     if (ihl->hl_next != NULL)
  480.         hl->hl_endpos = MINPOS(hl->hl_endpos, ihl->hl_next->hl_startpos);
  481.     if (hl->hl_startpos >= hl->hl_endpos)
  482.     {
  483.         /*
  484.          * Hilite was truncated out of existence.
  485.          */
  486.         free(hl);
  487.         return;
  488.     }
  489.     hl->hl_next = ihl->hl_next;
  490.     ihl->hl_next = hl;
  491. }
  492.  
  493. /*
  494.  * Adjust hl_startpos & hl_endpos to account for backspace processing.
  495.  */
  496.     static void
  497. adj_hilite(anchor, linepos)
  498.     struct hilite *anchor;
  499.     POSITION linepos;
  500. {
  501.     char *line;
  502.     struct hilite *hl;
  503.     int checkstart;
  504.     POSITION opos;
  505.     POSITION npos;
  506.  
  507.     /*
  508.      * The line was already scanned and hilites were added (in hilite_line).
  509.      * But it was assumed that each char position in the line 
  510.      * correponds to one char position in the file.
  511.      * This may not be true if there are backspaces in the line.
  512.      * Get the raw line again.  Look at each character.
  513.      */
  514.     (void) forw_raw_line(linepos, &line);
  515.     opos = npos = linepos;
  516.     hl = anchor->hl_first;
  517.     checkstart = TRUE;
  518.     while (hl != NULL)
  519.     {
  520.         /*
  521.          * See if we need to adjust the current hl_startpos or 
  522.          * hl_endpos.  After adjusting startpos[i], move to endpos[i].
  523.          * After adjusting endpos[i], move to startpos[i+1].
  524.          * The hilite list must be sorted thus: 
  525.          * startpos[0] < endpos[0] <= startpos[1] < endpos[1] <= etc.
  526.          */
  527.         if (checkstart && hl->hl_startpos == opos)
  528.         {
  529.             hl->hl_startpos = npos;
  530.             checkstart = FALSE;
  531.             continue; /* {{ not really necessary }} */
  532.         } else if (!checkstart && hl->hl_endpos == opos)
  533.         {
  534.             hl->hl_endpos = npos;
  535.             checkstart = TRUE;
  536.             hl = hl->hl_next;
  537.             continue; /* {{ necessary }} */
  538.         }
  539.         if (*line == '\0')
  540.             break;
  541.         opos++;
  542.         npos++;
  543.         line++;
  544.         while (line[0] == '\b' && line[1] != '\0')
  545.         {
  546.             /*
  547.              * Found a backspace.  The file position moves
  548.              * forward by 2 relative to the processed line
  549.              * which was searched in hilite_line.
  550.              */
  551.             npos += 2;
  552.             line += 2;
  553.         }
  554.     }
  555. }
  556.  
  557. /*
  558.  * Make a hilite for each string in a physical line which matches 
  559.  * the current pattern.
  560.  * sp,ep delimit the first match already found.
  561.  */
  562.     static void
  563. hilite_line(linepos, line, sp, ep)
  564.     POSITION linepos;
  565.     char *line;
  566.     char *sp;
  567.     char *ep;
  568. {
  569.     char *searchp;
  570.     struct hilite *hl;
  571.     struct hilite hilites;
  572.  
  573.     if (sp == NULL || ep == NULL)
  574.         return;
  575.     /*
  576.      * sp and ep delimit the first match in the line.
  577.      * Mark the corresponding file positions, then
  578.      * look for further matches and mark them.
  579.      * {{ This technique, of calling match_pattern on subsequent
  580.      *    substrings of the line, may mark more than is correct
  581.      *    if, for example, the pattern starts with "^". }}
  582.      */
  583.     searchp = line;
  584.     /*
  585.      * Put the hilites into a temporary list until they're adjusted.
  586.      */
  587.     hilites.hl_first = NULL;
  588.     do {
  589.         if (ep > sp)
  590.         {
  591.             /*
  592.              * Assume that each char position in the "line"
  593.              * buffer corresponds to one char position in the file.
  594.              * This is not quite true; we need to adjust later.
  595.              */
  596.             hl = (struct hilite *) ecalloc(1, sizeof(struct hilite));
  597.             hl->hl_startpos = linepos + (sp-line);
  598.             hl->hl_endpos = linepos + (ep-line);
  599.             add_hilite(&hilites, hl);
  600.         }
  601.         /*
  602.          * If we matched more than zero characters,
  603.          * move to the first char after the string we matched.
  604.          * If we matched zero, just move to the next char.
  605.          */
  606.         if (ep > searchp)
  607.             searchp = ep;
  608.         else if (*searchp != '\0')
  609.             searchp++;
  610.         else /* end of line */
  611.             break;
  612.     } while (match_pattern(searchp, &sp, &ep));
  613.  
  614.     if (bs_mode == BS_SPECIAL) 
  615.     {
  616.         /*
  617.          * If there were backspaces in the original line, they
  618.          * were removed, and hl_startpos/hl_endpos are not correct.
  619.          * {{ This is very ugly. }}
  620.          */
  621.         adj_hilite(&hilites, linepos);
  622.     }
  623.     /*
  624.      * Now put the hilites into the real list.
  625.      */
  626.     while ((hl = hilites.hl_next) != NULL)
  627.     {
  628.         hilites.hl_next = hl->hl_next;
  629.         add_hilite(&hilite_anchor, hl);
  630.     }
  631. }
  632. #endif
  633.  
  634. /*
  635.  * Change the caseless-ness of searches.  
  636.  * Updates the internal search state to reflect a change in the -i flag.
  637.  */
  638.     public void
  639. chg_caseless()
  640. {
  641.     if (!is_ucase_pattern)
  642.         /*
  643.          * Pattern did not have uppercase.
  644.          * Just set the search caselessness to the global caselessness.
  645.          */
  646.         is_caseless = caseless;
  647.     else
  648.         /*
  649.          * Pattern did have uppercase.
  650.          * Discard the pattern; we can't change search caselessness now.
  651.          */
  652.         uncompile_pattern();
  653. }
  654.  
  655. #if HILITE_SEARCH
  656. /*
  657.  * Find matching text which is currently on screen and highlight it.
  658.  */
  659.     static void
  660. hilite_screen()
  661. {
  662.     struct scrpos scrpos;
  663.  
  664.     get_scrpos(&scrpos);
  665.     if (scrpos.pos == NULL_POSITION)
  666.         return;
  667.     prep_hilite(scrpos.pos, position(BOTTOM_PLUS_ONE), -1);
  668.     repaint_hilite(1);
  669. }
  670.  
  671. /*
  672.  * Change highlighting parameters.
  673.  */
  674.     public void
  675. chg_hilite()
  676. {
  677.     /*
  678.      * Erase any highlights currently on screen.
  679.      */
  680.     clr_hilite();
  681.     hide_hilite = 0;
  682.  
  683.     if (hilite_search == OPT_ONPLUS)
  684.         /*
  685.          * Display highlights.
  686.          */
  687.         hilite_screen();
  688. }
  689. #endif
  690.  
  691. /*
  692.  * Figure out where to start a search.
  693.  */
  694.     static POSITION
  695. search_pos(search_type)
  696.     int search_type;
  697. {
  698.     POSITION pos;
  699.     int linenum;
  700.  
  701.     if (empty_screen())
  702.     {
  703.         /*
  704.          * Start at the beginning (or end) of the file.
  705.          * The empty_screen() case is mainly for 
  706.          * command line initiated searches;
  707.          * for example, "+/xyz" on the command line.
  708.          * Also for multi-file (SRCH_PAST_EOF) searches.
  709.          */
  710.         if (search_type & SRCH_FORW)
  711.         {
  712.             return (ch_zero());
  713.         } else
  714.         {
  715.             pos = ch_length();
  716.             if (pos == NULL_POSITION)
  717.             {
  718.                 (void) ch_end_seek();
  719.                 pos = ch_length();
  720.             }
  721.             return (pos);
  722.         }
  723.     }
  724.     if (how_search)
  725.     {
  726.         /*
  727.          * Search does not include current screen.
  728.          */
  729.         if (search_type & SRCH_FORW)
  730.             linenum = BOTTOM_PLUS_ONE;
  731.         else
  732.             linenum = TOP;
  733.         pos = position(linenum);
  734.     } else
  735.     {
  736.         /*
  737.          * Search includes current screen.
  738.          * It starts at the jump target (if searching backwards),
  739.          * or at the jump target plus one (if forwards).
  740.          */
  741.         linenum = adjsline(jump_sline);
  742.         pos = position(linenum);
  743.         if (search_type & SRCH_FORW)
  744.             pos = forw_raw_line(pos, (char **)NULL);
  745.     }
  746.     return (pos);
  747. }
  748.  
  749. /*
  750.  * Search a subset of the file, specified by start/end position.
  751.  */
  752.     static int
  753. search_range(pos, endpos, search_type, matches, maxlines, plinepos, pendpos)
  754.     POSITION pos;
  755.     POSITION endpos;
  756.     int search_type;
  757.     int matches;
  758.     int maxlines;
  759.     POSITION *plinepos;
  760.     POSITION *pendpos;
  761. {
  762.     char *line;
  763.     int linenum;
  764.     char *sp, *ep;
  765.     int line_match;
  766.     POSITION linepos, oldpos;
  767.  
  768.     linenum = find_linenum(pos);
  769.     oldpos = pos;
  770.     for (;;)
  771.     {
  772.         /*
  773.          * Get lines until we find a matching one or until
  774.          * we hit end-of-file (or beginning-of-file if we're 
  775.          * going backwards), or until we hit the end position.
  776.          */
  777.         if (ABORT_SIGS())
  778.         {
  779.             /*
  780.              * A signal aborts the search.
  781.              */
  782.             return (-1);
  783.         }
  784.  
  785.         if ((endpos != NULL_POSITION && pos >= endpos) || maxlines == 0)
  786.         {
  787.             /*
  788.              * Reached end position without a match.
  789.              */
  790.             if (pendpos != NULL)
  791.                 *pendpos = pos;
  792.             return (matches);
  793.         }
  794.         if (maxlines > 0)
  795.             maxlines--;
  796.  
  797.         if (search_type & SRCH_FORW)
  798.         {
  799.             /*
  800.              * Read the next line, and save the 
  801.              * starting position of that line in linepos.
  802.              */
  803.             linepos = pos;
  804.             pos = forw_raw_line(pos, &line);
  805.             if (linenum != 0)
  806.                 linenum++;
  807.         } else
  808.         {
  809.             /*
  810.              * Read the previous line and save the
  811.              * starting position of that line in linepos.
  812.              */
  813.             pos = back_raw_line(pos, &line);
  814.             linepos = pos;
  815.             if (linenum != 0)
  816.                 linenum--;
  817.         }
  818.  
  819.         if (pos == NULL_POSITION)
  820.         {
  821.             /*
  822.              * Reached EOF/BOF without a match.
  823.              */
  824.             if (pendpos != NULL)
  825.                 *pendpos = oldpos;
  826.             return (matches);
  827.         }
  828.  
  829.         /*
  830.          * If we're using line numbers, we might as well
  831.          * remember the information we have now (the position
  832.          * and line number of the current line).
  833.          * Don't do it for every line because it slows down
  834.          * the search.  Remember the line number only if
  835.          * we're "far" from the last place we remembered it.
  836.          */
  837.         if (linenums && abs((int)(pos - oldpos)) > 1024)
  838.             add_lnum(linenum, pos);
  839.         oldpos = pos;
  840.  
  841.         /*
  842.          * If it's a caseless search, convert the line to lowercase.
  843.          * If we're doing backspace processing, delete backspaces.
  844.          */
  845.         if (is_caseless || bs_mode == BS_SPECIAL)
  846.         {
  847.             int ops = 0;
  848.             if (is_caseless) 
  849.                 ops |= CVT_TO_LC;
  850.             if (bs_mode == BS_SPECIAL)
  851.                 ops |= CVT_BS;
  852.             cvt_text(line, line, ops);
  853.         }
  854.  
  855.         /*
  856.          * Test the next line to see if we have a match.
  857.          * We are successful if we either want a match and got one,
  858.          * or if we want a non-match and got one.
  859.          */
  860.         line_match = match_pattern(line, &sp, &ep);
  861.         line_match = (!(search_type & SRCH_NO_MATCH) && line_match) ||
  862.                 ((search_type & SRCH_NO_MATCH) && !line_match);
  863.         if (!line_match)
  864.             continue;
  865.         /*
  866.          * Got a match.
  867.          */
  868.         if (search_type & SRCH_FIND_ALL)
  869.         {
  870. #if HILITE_SEARCH
  871.             /*
  872.              * We are supposed to find all matches in the range.
  873.              * Just add the matches in this line to the 
  874.              * hilite list and keep searching.
  875.              */
  876.             if (line_match)
  877.                 hilite_line(linepos, line, sp, ep);
  878. #endif
  879.         } else if (--matches <= 0)
  880.         {
  881.             /*
  882.              * Found the one match we're looking for.
  883.              * Return it.
  884.              */
  885. #if HILITE_SEARCH
  886.             if (hilite_search == 1)
  887.             {
  888.                 /*
  889.                  * Clear the hilite list and add only
  890.                  * the matches in this one line.
  891.                  */
  892.                 clr_hilite();
  893.                 if (line_match)
  894.                     hilite_line(linepos, line, sp, ep);
  895.             }
  896. #endif
  897.             if (plinepos != NULL)
  898.                 *plinepos = linepos;
  899.             return (0);
  900.         }
  901.     }
  902. }
  903.  
  904. /*
  905.  * Search for the n-th occurrence of a specified pattern, 
  906.  * either forward or backward.
  907.  * Return the number of matches not yet found in this file
  908.  * (that is, n minus the number of matches found).
  909.  * Return -1 if the search should be aborted.
  910.  * Caller may continue the search in another file 
  911.  * if less than n matches are found in this file.
  912.  */
  913.     public int
  914. search(search_type, pattern, n)
  915.     int search_type;
  916.     char *pattern;
  917.     int n;
  918. {
  919.     POSITION pos;
  920.     int ucase;
  921.  
  922.     if (pattern == NULL || *pattern == '\0')
  923.     {
  924.         /*
  925.          * A null pattern means use the previously compiled pattern.
  926.          */
  927.         if (!prev_pattern())
  928.         {
  929.             error("No previous regular expression", NULL_PARG);
  930.             return (-1);
  931.         }
  932.         if ((search_type & SRCH_NO_REGEX) != 
  933.             (last_search_type & SRCH_NO_REGEX))
  934.         {
  935.             error("Please re-enter search pattern", NULL_PARG);
  936.             return -1;
  937.         }
  938. #if HILITE_SEARCH
  939.         if (hilite_search == OPT_ON)
  940.         {
  941.             /*
  942.              * Erase the highlights currently on screen.
  943.              * If the search fails, we'll redisplay them later.
  944.              */
  945.             repaint_hilite(0);
  946.         }
  947.         if (hilite_search == OPT_ONPLUS && hide_hilite)
  948.         {
  949.             /*
  950.              * Highlight any matches currently on screen,
  951.              * before we actually start the search.
  952.              */
  953.             hide_hilite = 0;
  954.             hilite_screen();
  955.         }
  956.         hide_hilite = 0;
  957. #endif
  958.     } else
  959.     {
  960.         /*
  961.          * Compile the pattern.
  962.          */
  963.         ucase = is_ucase(pattern);
  964.         if (caseless == OPT_ONPLUS)
  965.             cvt_text(pattern, pattern, CVT_TO_LC);
  966.         if (compile_pattern(pattern, search_type) < 0)
  967.             return (-1);
  968.         /*
  969.          * Ignore case if -I is set OR
  970.          * -i is set AND the pattern is all lowercase.
  971.          */
  972.         is_ucase_pattern = ucase;
  973.         if (is_ucase_pattern && caseless != OPT_ONPLUS)
  974.             is_caseless = 0;
  975.         else
  976.             is_caseless = caseless;
  977. #if HILITE_SEARCH
  978.         if (hilite_search)
  979.         {
  980.             /*
  981.              * Erase the highlights currently on screen.
  982.              * Also permanently delete them from the hilite list.
  983.              */
  984.             repaint_hilite(0);
  985.             hide_hilite = 0;
  986.             clr_hilite();
  987.         }
  988.         if (hilite_search == OPT_ONPLUS)
  989.         {
  990.             /*
  991.              * Highlight any matches currently on screen,
  992.              * before we actually start the search.
  993.              */
  994.             hilite_screen();
  995.         }
  996. #endif
  997.     }
  998.  
  999.     /*
  1000.      * Figure out where to start the search.
  1001.      */
  1002.     pos = search_pos(search_type);
  1003.     if (pos == NULL_POSITION)
  1004.     {
  1005.         /*
  1006.          * Can't find anyplace to start searching from.
  1007.          */
  1008.         if (search_type & SRCH_PAST_EOF)
  1009.             return (n);
  1010.         /* repaint(); -- why was this here? */
  1011.         error("Nothing to search", NULL_PARG);
  1012.         return (-1);
  1013.     }
  1014.  
  1015.     n = search_range(pos, NULL_POSITION, search_type, n, -1,
  1016.             &pos, (POSITION*)NULL);
  1017.     if (n != 0)
  1018.     {
  1019.         /*
  1020.          * Search was unsuccessful.
  1021.          */
  1022. #if HILITE_SEARCH
  1023.         if (hilite_search == OPT_ON && n > 0)
  1024.             /*
  1025.              * Redisplay old hilites.
  1026.              */
  1027.             repaint_hilite(1);
  1028. #endif
  1029.         return (n);
  1030.     }
  1031.  
  1032.     if (!(search_type & SRCH_NO_MOVE))
  1033.     {
  1034.         /*
  1035.          * Go to the matching line.
  1036.          */
  1037.         jump_loc(pos, jump_sline);
  1038.     }
  1039.  
  1040. #if HILITE_SEARCH
  1041.     if (hilite_search == OPT_ON)
  1042.         /*
  1043.          * Display new hilites in the matching line.
  1044.          */
  1045.         repaint_hilite(1);
  1046. #endif
  1047.     return (0);
  1048. }
  1049.  
  1050.  
  1051. #if HILITE_SEARCH
  1052. /*
  1053.  * Prepare hilites in a given range of the file.
  1054.  *
  1055.  * The pair (prep_startpos,prep_endpos) delimits a contiguous region
  1056.  *  of the file that has been "prepared"; that is, scanned for matches for
  1057.  * the current search pattern, and hilites have been created for such matches.
  1058.  * If prep_startpos == NULL_POSITION, the prep region is empty.
  1059.  * If prep_endpos == NULL_POSITION, the prep region extends to EOF.
  1060.  * prep_hilite asks that the range (spos,epos) be covered by the prep region.
  1061.  */
  1062.     public void
  1063. prep_hilite(spos, epos, maxlines)
  1064.     POSITION spos;
  1065.     POSITION epos;
  1066.     int maxlines;
  1067. {
  1068.     POSITION nprep_startpos = prep_startpos;
  1069.     POSITION nprep_endpos = prep_endpos;
  1070.     POSITION new_epos;
  1071.     int result;
  1072. /*
  1073.  * Search beyond where we're asked to search, so the prep region covers
  1074.  * more than we need.  Do one big search instead of a bunch of small ones.
  1075.  */
  1076. #define    SEARCH_MORE (3*size_linebuf)
  1077.  
  1078.     if (!prev_pattern())
  1079.         return;
  1080.     /*
  1081.      * Find two ranges:
  1082.      * The range that we need to search (spos,epos); and the range that
  1083.      * the "prep" region will then cover (nprep_startpos,nprep_endpos).
  1084.      */
  1085.  
  1086.     if (prep_startpos == NULL_POSITION ||
  1087.         (epos != NULL_POSITION && epos < prep_startpos) ||
  1088.         spos > prep_endpos)
  1089.     {
  1090.         /*
  1091.          * New range is not contiguous with old prep region.
  1092.          * Discard the old prep region and start a new one.
  1093.          */
  1094.         clr_hilite();
  1095.         if (epos != NULL_POSITION)
  1096.             epos += SEARCH_MORE;
  1097.         nprep_startpos = spos;
  1098.     } else
  1099.     {
  1100.         /*
  1101.          * New range partially or completely overlaps old prep region.
  1102.          */
  1103.         if (epos == NULL_POSITION)
  1104.         {
  1105.             /*
  1106.              * New range goes to end of file.
  1107.              */
  1108.             ;
  1109.         } else if (epos > prep_endpos)
  1110.         {
  1111.             /*
  1112.              * New range ends after old prep region.
  1113.              * Extend prep region to end at end of new range.
  1114.              */
  1115.             epos += SEARCH_MORE;
  1116.         } else /* (epos <= prep_endpos) */
  1117.         {
  1118.             /*
  1119.              * New range ends within old prep region.
  1120.              * Truncate search to end at start of old prep region.
  1121.              */
  1122.             epos = prep_startpos;
  1123.         }
  1124.  
  1125.         if (spos < prep_startpos)
  1126.         {
  1127.             /*
  1128.              * New range starts before old prep region.
  1129.              * Extend old prep region backwards to start at 
  1130.              * start of new range.
  1131.              */
  1132.             if (spos < SEARCH_MORE)
  1133.                 spos = 0;
  1134.             else
  1135.                 spos -= SEARCH_MORE;
  1136.             nprep_startpos = spos;
  1137.         } else /* (spos >= prep_startpos) */
  1138.         {
  1139.             /*
  1140.              * New range starts within or after old prep region.
  1141.              * Trim search to start at end of old prep region.
  1142.              */
  1143.             spos = prep_endpos;
  1144.         }
  1145.     }
  1146.  
  1147.     if (epos == NULL_POSITION || epos > spos)
  1148.     {
  1149.         result = search_range(spos, epos, SRCH_FORW|SRCH_FIND_ALL, 0,
  1150.                 maxlines, (POSITION*)NULL, &new_epos);
  1151.         if (result < 0)
  1152.             return;
  1153.         if (prep_endpos == NULL_POSITION || new_epos > prep_endpos)
  1154.             nprep_endpos = new_epos;
  1155.     }
  1156.     prep_startpos = nprep_startpos;
  1157.     prep_endpos = nprep_endpos;
  1158. }
  1159. #endif
  1160.  
  1161. /*
  1162.  * We have no pattern matching function from the library.
  1163.  * We use this function to do simple pattern matching.
  1164.  * It supports no metacharacters like *, etc.
  1165.  */
  1166.     static int
  1167. match(pattern, buf, pfound, pend)
  1168.     char *pattern, *buf;
  1169.     char **pfound, **pend;
  1170. {
  1171.     register char *pp, *lp;
  1172.  
  1173.     for ( ;  *buf != '\0';  buf++)
  1174.     {
  1175.         for (pp = pattern, lp = buf;  *pp == *lp;  pp++, lp++)
  1176.             if (*pp == '\0' || *lp == '\0')
  1177.                 break;
  1178.         if (*pp == '\0')
  1179.         {
  1180.             if (pfound != NULL)
  1181.                 *pfound = buf;
  1182.             if (pend != NULL)
  1183.                 *pend = lp;
  1184.             return (1);
  1185.         }
  1186.     }
  1187.     return (0);
  1188. }
  1189.  
  1190. #if HAVE_V8_REGCOMP
  1191. /*
  1192.  * This function is called by the V8 regcomp to report 
  1193.  * errors in regular expressions.
  1194.  */
  1195.     void 
  1196. regerror(s) 
  1197.     char *s; 
  1198. {
  1199.     PARG parg;
  1200.  
  1201.     parg.p_string = s;
  1202.     error("%s", &parg);
  1203. }
  1204. #endif
  1205.  
  1206. #if !HAVE_STRCHR
  1207. /*
  1208.  * strchr is used by regexp.c.
  1209.  */
  1210.     char *
  1211. strchr(s, c)
  1212.     char *s;
  1213.     int c;
  1214. {
  1215.     for ( ;  *s != '\0';  s++)
  1216.         if (*s == c)
  1217.             return (s);
  1218.     if (c == '\0')
  1219.         return (s);
  1220.     return (NULL);
  1221. }
  1222. #endif
  1223.  
  1224.