findrep.c

一个开源著名的TDE编辑器源代码

/*******************  start of original comments  ********************/
/*
 * Written by Douglas Thomson (1989/1990)
 *
 * This source code is released into the public domain.
 */

/*
 * Name:    dte - Doug's Text Editor program - find/replace module
 * Purpose: This file contains the functions relating to finding text
 *           and replacing text.
 *          It also contains the code for moving the cursor to various
 *           other positions in the file.
 * File:    findrep.c
 * Author:  Douglas Thomson
 * System:  this file is intended to be system-independent
 * Date:    October 1, 1989
 */
/*********************  end of original comments   ********************/

/*
 * The search and replace routines have been EXTENSIVELY rewritten.  The
 * "brute force" search algorithm has been replaced by the Boyer-Moore
 * string search algorithm.  This search algorithm really speeds up search
 * and replace operations.
 *
 *                  Sketch of the BM pattern matching algorithm:
 *
 *    while (not found) {
 *       fast skip loop;    <===  does most of the work and should be FAST
 *       slow match loop;   <===  standard "brute force" string compare
 *       if (found) then
 *          break;
 *       shift function;    <===  mismatch, shift and go to fast skip loop
 *    }
 *
 * See:
 *
 *   Robert S. Boyer and J Strother Moore, "A fast string searching
 *     algorithm."  _Communications of the ACM_ 20 (No. 10): 762-772, 1977.
 *
 * See also:
 *
 *   Zvi Galil, "On Improving the Worst Case Running Time of the Boyer-
 *    Moore String Matching Algorithm."  _Communications of the ACM_
 *    22 (No. 9): 505-508, 1979.
 *
 *   R. Nigel Horspool, "Practical fast searching in strings." _Software-
 *    Practice and Experience_  10 (No. 3): 501-506, 1980.
 *
 *   Alberto Apostolico and Raffaele Giancarlo, "The Boyer-Moore-Galil
 *    String Searching Strategies Revisited."  _SIAM Journal on Computing_
 *    15 (No. 1): 98-105, 1986.
 *
 *   Andrew Hume and Daniel Sunday, "Fast String Searching."  _Software-
 *    Practice and Experience_ 21 (No. 11): 1221-1248, November 1991.
 *
 *   Timo Raita, "Tuning the Boyer-Moore-Horspool String Searching Algorithm."
 *    _Software-Practice and Experience_ 22 (No. 10): 879-884, October 1992.
 *
 *
 *                            Boyer-Moore in TDE
 *
 * Hume and Sunday demonstrated in their paper that using a simple shift
 * function after a mismatch gives one of the fastest search times with the
 * Boyer-Moore algorithm.  When searching normal text for small patterns
 * (patterns less than 30 characters or so), Hume and Sunday found that the
 * faster the algorithm can get back into the fast skip loop with the
 * largest shift value then the faster the search.  Some algorithms can
 * generate a large shift value, but they can't get back into the skip loop
 * very fast.  Hume and Sunday give a simple method for computing a shift
 * constant that, more often than not, is equal to the length of the search
 * pattern.  They refer to the constant as mini-Sunday delta2 or md2.  From
 * the end of the string, md2 is the first leftmost occurrence of the
 * rightmost character.  Hume and Sunday also found that using a simple string
 * compare as the match function gave better performance than using the C
 * library memcmp( ) function.  The average number of compares in the slow
 * loop was slightly above 1.  Calling the memcmp( ) function to compare 1
 * character slows down the algorithm.  See the Hume and Sunday paper for an
 * excellent discussion on fast string searching.  Incidentally, Hume and
 * Sunday describe an even faster, tuned Boyer-Moore search function.
 *
 * The Boyer-Moore search algorithm in TDE was rearranged so that it is now
 * almost identical to the original version Boyer-Moore described in CACM.
 * The simple shift function in TDE was replaced by the mini-delta2 shift
 * function in the Hume and Sunday paper.
 *
 * I am not very fond of WordStar/TURBO x style search and replace prompting,
 * which is used in the DTE 5.1 editor.  Once the search pattern has been
 * defined, one only needs to press a key to search forwards or backwards.
 * The forward or backward search key may be pressed at any time in any file
 * once the pattern has been entered.  Also, the search case may be toggled
 * at any time in any file once the pattern has been entered.
 *
 * Thanks to Tom Waters, [e-mail], for finding a bug when
 * building the ignore skip index array in TDE 1.3 and previous versions.
 * BTW, I added assertions to those functions that build the skip index
 * array to make certain that everything is everything.
 *
 * Thanks also to David Merrill, [e-mail], for recommending a
 * change and the source code for the solution to what can be an annoying
 * feature in the find function.  Pressing <FindForward> before defining
 * the pattern would cause TDE to display an error message.  Since we already
 * know that the search pattern is undefined, we can easily prompt for
 * the search pattern.  I usually tolerate such features until I get tired
 * of being annoyed with error messages and finally write a solution.
 * Dave, thanks for the solution and the easy-to-implement code.  Although
 * such changes are small, they really make for a more comfortable editor.
 *
 *
 *                         Incremental Searching
 *
 * Incremental (or interactive) searching finds the search string as you type
 * it in. TDE's isearch is based on Emacs (as described to me by David J
 * Hughes). The default keys are Shift+Ctrl+S for forward searching and
 * Shift+Ctrl+R for backward; however, within isearch, Ctrl+S and Ctrl+R can
 * be used. Pressing these keys again will immediately start a search with the
 * previous find string (not necessarily isearch); otherwise they will
 * continue the search with the current string. LineUp and LineDown will cycle
 * through the find history. BackSpace can be used to remove entered
 * characters, returning to the previous position. CopyWord (ie. NextLine),
 * WordRight, WordEndRight and Ctrl+W will append the remainder of the word to
 * the search string; likewise with the String functions and Shift+Ctrl+W. If
 * no search string has been entered, the complete word or string will be
 * entered. ToggleSearchCase will do the obvious. Escape will stop the search
 * at the current position; AbortCommand and Ctrl+G will restore the original
 * position before the search was started. Enter/Rturn will stop the search
 * when entering characters or using the ISearch functions to continue it;
 * otherwise the search will be continued. The previous position is set to the
 * original position, not to the last matching instance; if aborted, it is set
 * to the aborted position.
 *
 *
 * New editor name:  TDE, the Thomson-Davis Editor.
 * Author:           Frank Davis
 * Date:             June 5, 1991, version 1.0
 * Date:             July 29, 1991, version 1.1
 * Date:             October 5, 1991, version 1.2
 * Date:             January 20, 1992, version 1.3
 * Date:             February 17, 1992, version 1.4
 * Date:             April 1, 1992, version 1.5
 * Date:             June 5, 1992, version 2.0
 * Date:             October 31, 1992, version 2.1
 * Date:             April 1, 1993, version 2.2
 * Date:             June 5, 1993, version 3.0
 * Date:             August 29, 1993, version 3.1
 * Date:             November 13, 1993, version 3.2
 * Date:             June 5, 1994, version 4.0
 * Date:             December 5, 1998, version 5.0 (jmh)
 *
 * This modification of Douglas Thomson's code is released into the
 * public domain, Frank Davis.   You may distribute it freely.
 */

#include "tdestr.h"
#include "common.h"
#include "tdefunc.h"
#include "define.h"


/*
 * jmh 991009: when text is replaced in a forward BOX replace, need to
 *             adjust the end of the block to reflect the change.
 */
       int  block_replace_offset = 0;
       long last_replace_line = 0;

extern int  nfa_status;                 /* regx.c */

       int  search_type = ERROR;        /* the search being repeated */
static file_infos *first_file;          /* first file when searching all */
static TDE_WIN    *first_win;           /* first win when searching all */

       TDE_WIN    *results_window = NULL;/* search results window,   */
       file_infos *results_file;         /*  file                    */
       file_infos *search_file;          /*  and file being searched */

       long found_rline;                /* for highlighting */
       int  found_rcol;
       int  found_len;
       int  found_vlen;                 /* virtual length, for tabs */

static text_ptr subst_text;             /* for regx substitution */
static int  subst_len;
static int  subst_max;
extern int  subs_pos[10];
extern int  subs_len[10];


#define CopyWord   NextLine
#define CopyString BegNextLine

static int  icopy_word( TDE_WIN *, int, int );

int  add_search_line( line_list_ptr, long, int );


/*
 * Name:     ask_replace
 * Purpose:  Ask user if he wants to (r)eplace, (s)kip, or (e)xit.
 * Date:     June 5, 1991
 * Modified: November 13, 1993, Frank Davis per Byrial Jensen
 * Returns:  TRUE if user wants to replace, ERROR otherwise.
 * Passed:   window:   pointer to current window
 *           finished: TRUE if user pressed ESC or (e)xit.
 *
 * jmh 980813: center prompt column above cursor, rather than screen.
 */
int  ask_replace( TDE_WIN *window, int *finished )
{
int  prompt_line;
int  c;
int  rc;
DISPLAY_BUFF;

   prompt_line = window->cline - 1;
   rc = strlen( find2 );
   c  = window->ccol - (rc >> 1);
   if (c < 0)
      c = 0;
   else if (c > g_display.ncols - rc)
      c = g_display.ncols - rc;

   SAVE_LINE( prompt_line );
   /*
    * (R)eplace  (S)kip  (E)xit - default replace
    */
   s_output( find2, prompt_line, c, Color( Message ) );

#if defined( __UNIX__ )
   xygoto( window->ccol, window->cline );
   refresh( );
#endif

   rc = get_response( NULL, 0, R_DEFAULT | R_ABORT,
                      3, L_REPLACE, OK, L_SKIP, ERROR, L_EXIT, L_EXIT );
   RESTORE_LINE( prompt_line );
   if (rc == L_EXIT) {
      *finished = TRUE;
      rc = ERROR;
   }
   return( rc );
}


/*
 * Name:     ask_wrap_replace
 * Purpose:  After a wrap, ask user if he wants to (q)uit or (c)ontinue.
 * Date:     June 5, 1991
 * Modified: November 13, 1993, Frank Davis per Byrial Jensen
 * Returns:  TRUE if user wants to continue, ERROR otherwise.
 * Passed:   window:   pointer to current window
 *           finished: ERROR if user pressed ESC or (q)uit.
 *
 * jmh 991026: allow response from a macro.
 * jmh 050709: check macro flag.
 */
int  ask_wrap_replace( TDE_WIN *window, int *finished )
{
int  rc = -2;

   if (g_status.search & SEARCH_ALL)
      window = first_win;

   if (g_status.macro_executing) {
      if (g_status.current_macro->flag & WRAP)
         rc = OK;
      else if (g_status.current_macro->flag & NOWRAP)
         rc = ERROR;
   }
   if (rc == -2) {
      /*
       * search has wrapped. continue or quit? - default continue
       */
      rc = get_response( find3, window->bottom_line, R_ALL,
                         2, L_CONTINUE, OK, L_QUIT, ERROR );
   }
   if (rc == ERROR)
      *finished = ERROR;
   return( rc );
}


/*
 * Name:    subst_add
 * Purpose: add a string to the regx substitution
 * Author:  Jason Hood
 * Date:    July 29, 2005
 * Passed:  line:  character(s) to add
 *          len:   length of above
 * Returns: TRUE if string added, FALSE if no memory
 */
int  subst_add( text_ptr line, int len )
{
int  new_len;
text_ptr temp;
int  add;
int  rc = OK;

   new_len = subst_len + len;
   if (new_len > subst_max) {
      temp = my_realloc( subst_text, new_len + (add = 40), &rc );
      if (rc == ERROR) {
         rc = OK;
         temp = my_realloc( subst_text, new_len, &rc );
         if (rc == ERROR)
            return FALSE;
         add = 0;
      }
      subst_text = temp;
      subst_max = new_len + add;
   }
   memcpy( subst_text + subst_len, line, len );
   subst_len = new_len;
   return TRUE;
}


/*
 * Name:    do_replace
 * Purpose: To replace text once match has been found.
 * Date:    June 5, 1991
 * Passed:  window:     pointer to current window
 *          direction:  direction of search
 *
 * jmh 051018: don't deflate tabs (long-standing bug - inflate mode could
 *              never replace a tab)
 */
void do_replace( TDE_WIN *window, int direction )
{
int  old_len;           /* length of original text */
int  new_len;           /* length of replacement text */
int  rcol;
register int net_change;
text_ptr source;        /* source of block move */
text_ptr dest;          /* destination of block move */
file_infos *file;
int  tabs;
int  i;
int  rc;

   file = window->file_info;
   tabs = file->inflate_tabs;
   rcol = (tabs) ? entab_adjust_rcol( window->ll->line, window->ll->len,
                                      window->rcol, file->ptab_size )
                 : window->rcol;
   g_status.copied = FALSE;
   copy_line( window->ll, window, FALSE );

   old_len = found_len;
   new_len = strlen( (char *)g_status.subst );
   if (g_status.search & SEARCH_REGX) {
      subst_len = 0;
      for (i = 0; i < new_len; ++i) {
         if (g_status.subst[i] != '\\'  ||  i == new_len-1)
            rc = subst_add( g_status.subst + i, 1 );
         else {
            text_t c = g_status.subst[i+1];
            if ((c == '+' || c == '-' || c == '^')  &&  i+2 < new_len)
               c = g_status.subst[i+2];
            if (c == '&'  ||  (c >= '1' && c <= '9')) {
               int s = (c == '&') ? 0 : c - '0';
               rc = TRUE;
               if (subs_len[s]) {
                  net_change = subst_len;
                  rc = subst_add( g_status.line_buff + rcol + subs_pos[s],
                                  subs_len[s] );
                  if (rc) {
                     source = subst_text + net_change;
                     switch (g_status.subst[i+1]) {
                        case '+': upper_case( source, subs_len[s] ); ++i; break;
                        case '-': lower_case( source, subs_len[s] ); ++i; break;
                        case '^': capitalise( source, subs_len[s] ); ++i; break;
                     }
                  }
               }
            } else {
               c = escape_char( g_status.subst[i+1] );
               rc = subst_add( &c, 1 );
            }
            ++i;
         }
         if (!rc) {
            /*
             * out of memory
             */
            error( WARNING, window->bottom_line, main4 );
            g_status.copied = FALSE;
            return;
         }
      }
      new_len = subst_len;
   }
   net_change = new_len - old_len;

   /*
    * move the text to either make room for the extra replacement text
    *  or to close up the gap left
    */

   if (net_change != 0) {
      source = g_status.line_buff + rcol + old_len;
      dest  = source + net_change;

      assert( g_status.line_buff_len - rcol - old_len >= 0 );
      assert( g_status.line_buff_len - rcol - old_len < MAX_LINE_LENGTH );

      shift_tabbed_block( file );

      memmove( dest, source, g_status.line_buff_len - rcol - old_len );
      g_status.line_buff_len += net_change;

      shift_block( file, window->rline, rcol + old_len, net_change );

      if ((g_status.search & SEARCH_BLOCK) && direction == FORWARD  &&
          file->block_type == BOX && file->block_br != file->block_er) {
         block_replace_offset = net_change;
         last_replace_line = window->rline;
      }
   }

   /*
    * insert the replacement text