regx.c

C语言实战105例 随书光盘 王为青 张圣亮编著 中国邮电出版社出版

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


/*
 * types of nodes in the NFA.
 *
 * let's use the node naming convention in Ken Thompson's reg ex paper.
 */
#define CNODE           0
#define NNODE           1

#define SCAN            -1

/*
 * types of terminals in NNODEs.
 *
 * starting with simple ASCII terminals, it's easy to build in other types of
 *  terminals, e.g. wild chars, BOL, EOL, and character classes.  actually,
 *  we can easily build ANSI C ctype library function NNODEs.
 */
#define STRAIGHT_ASCII  0
#define IGNORE_ASCII    1
#define WILD            2
#define BOL             3
#define EOL             4
#define CLASS           5
#define NOTCLASS        6
#define WHITESPACE      7
#define ALPHA           8
#define UPPER           9
#define LOWER           10
#define ALPHANUM        11
#define DECIMAL         12
#define HEX             13
#define BOW             14
#define EOW             15


/*
 * types of terminals in CNODEs.
 */
#define START           0
#define ACCEPT          1
#define OR_NODE         2
#define JUXTA           3
#define CLOSURE         4
#define ZERO_OR_ONE     5


int  lookahead;
int  regx_rc;
int  reg_len;
int  parser_state;
char class_bits[32];
int  bit[8] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
int  c1;
int  c2;
int  ttype;
int  regx_error_line;

NFA_TYPE  *nfa_pointer;

int  nfa_status;
int  search_len;
int  search_col;
text_ptr search_string;

int  queued_states[REGX_SIZE+2];
int  deque[REGX_SIZE*2];
int  dq_head;
int  dq_tail;
int  stacked_node_count;
int  reset_count;


/*
 * Name:    find_regx
 * Purpose: To set up and find a regular expression.
 * Date:    June 5, 1993
 * Passed:  window:  pointer to current window
 * Notes:   Keep the regular expression until changed.
 */
int  find_regx( 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 FindRegX :
         new_string = TRUE;
         direction  = FORWARD;
         break;
      case RepeatFindRegX :
         new_string =  regx.search_defined != OK ? TRUE : FALSE;
         direction  = FORWARD;
         break;
      case RepeatFindRegXBackward :
         new_string =  regx.search_defined != OK ? TRUE : FALSE;
         direction  = BACKWARD;
         break;
      default :
         new_string = 0;
         direction  = 0;
         assert( FALSE );
         break;
   }

   win = window;
   entab_linebuff( );
   if (un_copy_line( win->ll, win, TRUE ) == ERROR)
      return( ERROR );

   regx_error_line = win->bottom_line;

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

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

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

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

      assert( strlen( pattern ) < MAX_COLS );

      strcpy( (char *)regx.pattern, pattern );
      rc = build_nfa( );
      if (rc == ERROR)
         regx.search_defined = ERROR;
   }

   if (regx.search_defined == OK) {
      old_rcol = win->rcol;
      if (mode.inflate_tabs)
         win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol);
      update_line( win );
      show_search_message( SEARCHING, g_display.diag_color );
      bin_offset = win->bin_offset;
      if (direction == FORWARD) {
         if ((ll = forward_regx_search( win, &found_line, &rcol )) != NULL) {
            if (g_status.wrapped && g_status.macro_executing)
               rc = ask_wrap_replace( win, &new_string );
            if (rc == OK)
               find_adjust( win, ll, found_line, rcol );
            else
               win->bin_offset = bin_offset;
         }
      } else {
         if ((ll = backward_regx_search( win, &found_line, &rcol )) != NULL) {
            if (g_status.wrapped && g_status.macro_executing)
               rc = ask_wrap_replace( win, &new_string );
            if (rc == OK)
               find_adjust( win, ll, found_line, rcol );
            else
               win->bin_offset = bin_offset;
         }
      }
      if (g_status.wrapped)
         show_search_message( WRAPPED, g_display.diag_color );
      else {
         if (nfa_status == OK)
            show_search_message( CLR_SEARCH, g_display.mode_color );
         else
            g_status.wrapped = TRUE;
      }
      if (ll == NULL) {
         /*
          * string not found
          */
         if (mode.inflate_tabs)
            win->rcol = old_rcol;
         combine_strings( pattern, find5a, (char *)regx.pattern, find5b );
         error( WARNING, win->bottom_line, pattern );
         rc = ERROR;
      }
      show_curl_line( win );
      make_ruler( win );
      show_ruler( win );
   } else {
      /*
       * find pattern not defined
       */
      error( WARNING, win->bottom_line, find6 );
      rc = ERROR;
   }
   return( rc );
}


/*
 * Name:    forward_regx_search
 * Purpose: search forward for regular expression
 * Date:    June 5, 1993
 * Passed:  window:  pointer to current window
 *          rline:   pointer to real line counter
 *          rcol:    pointer to real column variable
 * Returns: position in file if found or NULL if not found
 * Notes:   Start searching from cursor position to end of file.  If we hit
 *           end of file without a match, start searching from the beginning
 *           of file to cursor position.  (do wrapped searches)
 */
line_list_ptr forward_regx_search( WINDOW *window, long *rline, int *rcol )
{
register int len;
int  i;
int  end;
register WINDOW *win;  /* put window pointer in a register */
line_list_ptr ll;

   /*
    * if cursor is beyond end of line then start at end of line
    */
   win  = window;
   *rline = win->rline;
   i = win->rcol + 1;
   ll = win->ll;
   len = ll->len;
   if (i > len  &&  len != EOF) {
      ll = ll->next;
      ++*rline;
      i = 0;
   }
   if (i < 0)
      i = 0;

   *rcol = i;
   ll = regx_search_forward( ll, rline, rcol );

   if (ll == NULL) {

      end = 0;
      if (win->ll->next != NULL) {
         end = win->ll->next->len;
         win->ll->next->len = EOF;
      }

      /*
       * haven't found pattern yet - now search from beginning of file
       */
      g_status.wrapped = TRUE;

      *rcol = 0;
      *rline = 1L;
      ll = regx_search_forward( win->file_info->line_list, rline, rcol );

      if (ll == win->ll  &&  *rcol >= win->rcol)
         ll = NULL;

      if (win->ll->next != NULL)
         win->ll->next->len = end;
   }
   flush_keyboard( );

   if (ll != NULL)
      bin_offset_adjust( win, *rline );
   return( ll );
}


/*
 * Name:    regx_search_forward
 * Purpose: search forward for pattern using nfa
 * Date:    June 5, 1993
 * Passed:  ll:     pointer to current node in linked list
 *          rline:  pointer to real line counter
 *          col:    column in ll->line to begin search
 * Returns: position in file if found or NULL if not found
 * Notes:   run the nfa machine on each character in each line
 */
line_list_ptr regx_search_forward( line_list_ptr ll, long *rline, int  *col )
{
   if (ll->len == EOF)
      return( NULL );
   else {
      switch (g_status.command) {
         case DefineRegXGrep  :
         case RepeatGrep :
            nfa_pointer = &sas_nfa;
            stacked_node_count = sas_regx.node_count;
            break;
         case FindRegX  :
         case RepeatFindRegX :
            nfa_pointer = &nfa;
            stacked_node_count = regx.node_count;
            break;
         default :
            assert( FALSE );
            break;
      }
      nfa_status = OK;
      search_string = ll->line;
      search_len = ll->len;
      search_col = *col;
      reset_count = stacked_node_count * sizeof(int);
      for (; !g_status.control_break;) {
         for (; search_col <= search_len; search_col++) {
            if (nfa_match( ) != ERROR) {
               *col = search_col;
               return( ll );
            }
         }
         ++*rline;
         ll = ll->next;
         search_string = ll->line;
         if (ll->len == EOF)
            return( NULL );
         search_len = ll->len;
         search_col = 0;
      }
      return( NULL );
   }
}


/*
 * Name:    backward_regx_search
 * Purpose: search backward for regular expression
 * Date:    June 5, 1993
 * Passed:  window:  pointer to current window
 *          rline:   pointer to real line counter
 *          rcol:    pointer to real column variable
 * Returns: position in file if found or NULL if not found
 * Notes:   Start searching from cursor position to end of file.  If we hit
 *           end of file without a match, start searching from the beginning
 *           of file to cursor position.  (do wrapped searches)
 */
line_list_ptr backward_regx_search( WINDOW *window, long *rline, int *rcol )
{
int  i;
int  len;
int  end;
register WINDOW *win;  /* put window pointer in a register */
line_list_ptr ll;

   win  = window;
   *rline = win->rline;

   /*
    * see if cursor is on EOF line.  if so, move search start to previous node.
    */
   if (win->ll->len != EOF) {
      ll = win->ll;
      i  = win->rcol - 1;
      len = ll->len;
      if (i >= len)
         i = len - 1;
   } else {
      ll = win->ll->prev;
      --*rline;
      i = 0;
      if (ll != NULL)
         i = ll->len - 1;
   }
   *rcol = i;
   ll = regx_search_backward( ll, rline, rcol );

   if (ll == NULL  &&  win->rline <= win->file_info->length) {

      end = 0;
      if (win->ll->prev != NULL) {
         end = win->ll->prev->len;
         win->ll->prev->len = EOF;
      }

      /*
       * haven't found pattern yet - now search from end of file
       */
      g_status.wrapped = TRUE;
      ll = win->file_info->line_list_end;
      if (ll->prev != NULL)
         *rcol = ll->prev->len;
      else
        *rcol = 0;
      *rline = win->file_info->length;
      ll = regx_search_backward( ll->prev, rline, rcol );

      if (ll == win->ll  &&  *rcol <= win->rcol)
         ll = NULL;

      if (win->ll->prev != NULL)
         win->ll->prev->len = end;