This is the mail archive of the gdb-patches@sourceware.cygnus.com mailing list for the GDB project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

RFC: correctly search for strings in monitor output



Comments?  Misgivings?  Raspberries?

1999-05-08  Jim Blandy  <jimb@zwingli.cygnus.com>

	* monitor.c (monitor_expect): When we receive a character that
	isn't part of the string we were expecting, don't just start
	matching again at the beginning of the string --- some shorter
	suffix of the input might be a prefix of the string too.

Index: monitor.c
===================================================================
RCS file: /cvs/cvsfiles/devo/gdb/monitor.c,v
retrieving revision 1.98
diff -c -r1.98 monitor.c
*** monitor.c	1999/05/19 00:36:54	1.98
--- monitor.c	1999/06/23 18:33:04
***************
*** 581,589 ****
  	}
        else
  	{
! 	  p = string;
! 	  if (c == *p)
! 	    p++;
  	}
      }
  }
--- 581,629 ----
  	}
        else
  	{
! 	  /* We got a character that doesn't match STRING.  We need to back
! 	     up p, but how far?  Suppose we're looking for "..howdy" and the
! 	     monitor sends "...howdy".  We certainly ought to find a match
! 	     there.
! 
! 	     The first two characters match, so we'll march p up to 'h'.
! 	     When we receive the third '.', we can't simply set p back to
! 	     the beginning of STRING again --- then we'll be looking for the
! 	     full string, "..howdy", in ".howdy", and miss the match.  We
! 	     backed up p too far.
! 	     
! 	     This is a Boyer-Moore kind of situation.  We want to reset P to
! 	     the end of the longest prefix of STRING that is a suffix of
! 	     what we've read so far --- the biggest overlap possible.  In
! 	     the example above, after recieving the third '.', that would be
! 	     ".." --- the longest prefix of "..howdy" that is a suffix of
! 	     "...".  This longest prefix could be the empty string, if the
! 	     character we just read is nowhere to be found in STRING.
! 
! 	     If this longest prefix is not the empty string, it must contain
! 	     C, so let's search from the end of STRING for instances of C,
! 	     and see if the portion of STRING before that is a suffix of
! 	     what we read before C.  Actually, we can search backwards from
! 	     p, since we know no prefix can be longer than that.
! 
! 	     Note that we can use STRING itself, along with C, as a record
! 	     of what we've received so far.  :) */
! 	  int i;
! 
! 	  for (i = (p - string) - 1; i >= 0; i--)
! 	    if (string[i] == c)
! 	      {
! 		/* Is this prefix a suffix of what we've read so far?
! 		   In other words, does
!                      string[0 .. i-1] == string[p - i, p - 1]? */
! 		if (! memcmp (string, p - i, i))
! 		  {
! 		    p = string + i + 1;
! 		    break;
! 		  }
! 	      }
! 	  if (i < 0)
! 	    p = string;
  	}
      }
  }

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]