findrep.c

THOMSON-DAVIS用C语言开发的编缉器,简单,易懂.

/*******************  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.
 *
 * 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.
 *
 * 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.
 *
 * 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
 *
 * 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"


/*
 * Name:    get_replacement_flags
 * Purpose: To input find and replace flags.
 * Date:    June 5, 1991
 * Passed:  line:  prompt line
 * Returns: OK if flags were entered, ERROR if user wanted to abort
 */
int  get_replacement_flags( int line )
{
char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
register int c;
int  func;
int  rc;

   save_screen_line( 0, line, line_buff );
   eol_clear( 0, line, g_display.text_color );
   /*
    * options: prompt or no prompt (p/n)?
    */
   s_output( find1, line, 0, g_display.message_color );
   xygoto( strlen( find1 ) + 2, line );
   do {
      c = getkey( );
      func = getfunc( c );
   } while (c != 'P'  &&  c != 'p'  &&  c != 'N'  &&  c != 'n'  &&
            c != RTURN  &&  c != ESC  &&  func != AbortCommand);
   restore_screen_line( 0, line, line_buff );
   switch (c) {
      case 'P' :
      case 'p' :
      case RTURN :
         g_status.replace_flag = PROMPT;
         rc = OK;
         break;
      case 'N' :
      case 'n' :
         g_status.replace_flag = NOPROMPT;
         rc = OK;
         break;
      default :
         rc = ERROR;
   }
   bm.search_defined = rc;
   return( rc );
}


/*
 * Name:    ask_replace
 * Purpose: Ask user if he wants to (r)place, (s)kip, or (e)xit.
 * Date:    June 5, 1991
 * Returns: TRUE if user wants to replace, ERROR otherwise.
 * Passed:  window:   pointer to current window
 *          finished: TRUE if user pressed ESC or (e)xit.
 */
int  ask_replace( WINDOW *window, int *finished )
{
char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
register int c;
int  func;
int  prompt_line;
int  rc;

   prompt_line = window->cline - 1;
   c = 39 - (strlen( find2 ) >> 1);
   save_screen_line( 0, prompt_line, line_buff );
   /*
    * replace skip exit (r/s/e)?
    */
   s_output( find2, prompt_line, c, g_display.message_color );
   do {
      c = getkey( );
      func = getfunc( c );
   } while (c != 'R' && c != 'r' && c != 'S' && c != 's' && c != 'E' && c != 'e'
          && c != ESC  &&  func != AbortCommand);
   restore_screen_line( 0, prompt_line, line_buff );
   switch (c) {
      case 'R' :
      case 'r' :
         rc = OK;
         break;
      case 'E' :
      case 'e' :
         *finished = TRUE;
      case 'S' :
      case 's' :
         rc = ERROR;
         break;
      default :
         *finished = TRUE;
         rc = ERROR;
         break;
   }
   return( rc );
}


/*
 * Name:    ask_wrap_replace
 * Purpose: After a wrap, ask user if he wants to (q)uit or (c)ontine.
 * Date:    June 5, 1991
 * Returns: TRUE if user wants to continue, ERROR otherwise.
 * Passed:  window:   pointer to current window
 *          finished: TRUE if user pressed ESC or (q)uit.
 */
int  ask_wrap_replace( WINDOW *window, int *finished )
{
char line_buff[(MAX_COLS+1)*2]; /* buffer for char and attribute  */
register int c;
int  func;
int  prompt_line;
int  rc;

   prompt_line = window->bottom_line;
   save_screen_line( 0, prompt_line, line_buff );
   /*
    * search has wrapped. continue or quit (c/q)?
    */
   set_prompt( find3, prompt_line );
   do {
      c = getkey( );
      func = getfunc( c );
   } while (c != 'Q'  &&  c != 'q'  &&  c != 'C'  &&  c != 'c' &&
          c != ESC  &&  func != AbortCommand);
   restore_screen_line( 0, prompt_line, line_buff );
   switch (c) {
      case 'C' :
      case 'c' :
         rc = OK;
         break;
      case 'Q' :
      case 'q' :
      default :
         *finished = TRUE;
         rc = ERROR;
         break;
   }
   return( rc );
}


/*
 * 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
 */
void do_replace( WINDOW *window, int direction )
{
int  old_len;           /* length of original text */
int  new_len;           /* length of replacement text */
int  rcol;
register int net_change;
char *source;           /* source of block move */
char *dest;             /* destination of block move */

   old_len = strlen( g_status.pattern );
   new_len = strlen( g_status.subst );
   net_change = new_len - old_len;
   rcol = window->rcol;

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

   g_status.copied = FALSE;
   copy_line( window->ll );
   detab_linebuff( );

   if (net_change != 0) {
      assert( rcol + old_len >= 0);
      assert( net_change <= rcol + old_len );

      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 );

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

   /*
    * insert the replacement text
    */

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

   for (dest=g_status.line_buff+rcol, source=g_status.subst; *source;)
      *dest++ = *source++;

   entab_linebuff( );
   window->file_info->modified = TRUE;
   un_copy_line( window->ll, window, TRUE );
   window->ll->dirty = TRUE;

   if (direction == FORWARD)
      window->rcol += (new_len - 1);

   assert( window->rcol >= 0 );
   show_avail_mem( );
}


/*
 * Name:    find_string
 * Purpose: To set up and perform a find operation.
 * Date:    June 5, 1991
 * Passed:  window:  pointer to current window
 * Notes:   Keep the search string and boyer-moore stuff until changed.
 */
int  find_string( WINDOW *window )
{
int  direction;
int  new_string;
char pattern[MAX_COLS];  /* text to be found */
long found_line;
long bin_offset;
line_list_ptr ll;
register WINDOW *win;  /* put window pointer in a register */
int  rc;
int  old_rcol;
int  rcol;

   switch (g_status.command) {
      case FindForward :
         direction = FORWARD;
         new_string = TRUE;
         break;
      case FindBackward :
         direction = BACKWARD;
         new_string = TRUE;
         break;
      case RepeatFindForward1 :
      case RepeatFindForward2 :
         direction = FORWARD;
         new_string = FALSE;
         break;
      case RepeatFindBackward1 :
      case RepeatFindBackward2 :
         direction = BACKWARD;
         new_string = FALSE;
         break;
      default :
         direction = 0;
         new_string = 0;
         assert( FALSE );
         break;
   }
   win = window;
   entab_linebuff( );
   if (un_copy_line( win->ll, win, TRUE ) == ERROR)
      return( ERROR );

   /*
    * get search text, using previous as default
    */
   if (new_string == TRUE) {
      *pattern = '\0';
      if (bm.search_defined == OK) {

         assert( strlen( (char *)bm.pattern ) < MAX_COLS );

         strcpy( pattern, (char *)bm.pattern );
      }

      /*
       * string to find:
       */
      if (get_name( find4, win->bottom_line, pattern,
                    g_display.message_color ) != OK  ||  *pattern == '\0')
         return( ERROR );
      bm.search_defined = OK;

      assert( strlen( pattern ) < MAX_COLS );

      strcpy( (char *)bm.pattern, pattern );
      build_boyer_array( );
   }