Ticket #1828 (closed Bug: fixed)

Opened 3 months ago

Last modified 2 months ago

Problem with Find/Replace

Reported by: sketly Assigned to: martinkou
Priority: Normal Milestone: FCKeditor 2.6
Component: General Version: FCKeditor 2.5.1
Keywords: Confirmed HasPatch Review+ Cc:

Description

Step to reproduce:
1. Enter into FCKEditor text: "212221"
2. Call dialog "Find/Replace"
3. Enter search string: "21"
4. Click button "Find" - we get selection 212221 - right
5. Click button "Find" - we get selection 212221 - wrong

Thanks.

Attachments

1828.patch (3.7 kB) - added by martinkou on 02/14/08 11:39:10.
1828_2.patch (2.8 kB) - added by martinkou on 03/06/08 06:51:50.

Change History

02/07/08 10:22:11 changed by w.olchawa

  • keywords set to Confirmed.

Confirmed on IE, IE7 and FF2.

02/08/08 09:56:46 changed by sketly

I fixed it as follows (seems like it works for me):

--- fck_replace.html	old
+++ fck_replace.html	new
@@ -264,6 +264,7 @@
 	var cursor = GetSelection().End ;
 	var matchState = KMP_NOMATCH ;
 	var matchBookmark = null ;
+	var matchBookmarkStart = [] ;
 
 	// Match finding.
 	while ( true )
@@ -286,11 +287,24 @@
 				matchState = matcher.FeedCharacter(data) ;
 
 				if ( matchState == KMP_NOMATCH )
+				{
 					matchBookmark = null ;
-				else if ( matchState == KMP_ADVANCED && matchBookmark == null )
-					matchBookmark = { Start : cursor.concat( [] ) } ;
+					matchBookmarkStart = [];
+				}
+				//else if ( matchState == KMP_ADVANCED && matchBookmark == null )
+				//	matchBookmark = { Start : cursor.concat( [] ) } ;
+				else if ( matchState == KMP_ADVANCED )
+				{
+					matchBookmarkStart.push({ Start : cursor.concat( [] ) });
+					while(matchBookmarkStart.length > matcher._State)
+					{
+						matchBookmarkStart.shift();
+					}
+				}
 				else if ( matchState == KMP_MATCHED )
 				{
+					if ( matchBookmarkStart.length >0 )
+						matchBookmark = matchBookmarkStart.shift();
 					if ( matchBookmark == null )
 						matchBookmark = { Start : cursor.concat( [] ) } ;
 					matchBookmark.End = cursor.concat( [] ) ;

02/08/08 14:23:07 changed by fredck

  • keywords changed from Confirmed to Confirmed HasPatch.
  • milestone set to FCKeditor 2.6.

02/14/08 10:51:20 changed by martinkou

  • owner set to martinkou.
  • status changed from new to assigned.

02/14/08 11:38:34 changed by martinkou

Thanks for pointing out, I was careless when considering semantics of the state changes implied by the KMP algorithm - the textbook algorithm is correct at finding out where a match is found, but the code I added to interpret the state transitions from the KMP code was flawed.

Since the problem lies in how I interpreted the state transitions in the KmpMatch class, it is the class's code that should be corrected, rather than adding more hacks to bookmark housekeeping logic later to compensate for the mistake. So I'm attaching another patch to this ticket that's different to the reporter's approach.

Also, I've added some comments in the code to make it clearer to what it is doing, and simplified the other parts of the dialog code a bit.

02/14/08 11:39:10 changed by martinkou

  • attachment 1828.patch added.

02/14/08 11:41:53 changed by martinkou

  • keywords changed from Confirmed HasPatch to Confirmed HasPatch Review?.

02/15/08 11:33:45 changed by fredck

  • keywords changed from Confirmed HasPatch Review? to Confirmed HasPatch Review+.

02/18/08 04:15:01 changed by martinkou

  • status changed from assigned to closed.
  • resolution set to fixed.

Fixed with [1541].

Click here for more info about our SVN system.

03/05/08 11:32:03 changed by sketly

  • status changed from closed to reopened.
  • resolution deleted.

Patch does not work correctly.
It was tested on version 2.6b

Step to reproduce:
1. Enter into FCKEditor text: "212221"
2. Call dialog "Find/Replace"
3. Enter search string: "221"
4. Click button "Find" - we get selection 212221 - wrong

03/06/08 06:50:16 changed by martinkou

Ok, so I've still not considered all the possibilities in the last patch. Turns out it is not possible to predict the starting position before a complete match is found in the KMP matching algorithm because the state transitions can go like 0->1->2->2->2->..., and so just marking down the position of state-1s is not a good way to determine where the matched pattern started.

So let's do it like how KMP is usually used in simple string matching - we have the correct ending position, and we have the pattern length, so we can get the starting position by "subtracting" character positions by the length of the pattern. Our find/replace dialog isn't doing a match against a plain string though, it's doing it against text nodes in a DOM tree (e.g. l<b>o<a href="www.abcdefg.com">o</a>k for m</b>e!), so we can't just do a pointer subtraction like what C programmers can do - but we can still backtrack the previously matched positions. In this view, the approach of your patch would be the correct approach.

03/06/08 06:51:50 changed by martinkou

  • attachment 1828_2.patch added.

03/06/08 06:53:14 changed by martinkou

  • keywords changed from Confirmed HasPatch Review+ to Confirmed HasPatch Review?.

I've created a patch based on sketly's fix.

03/07/08 09:55:45 changed by fredck

  • keywords changed from Confirmed HasPatch Review? to Confirmed HasPatch Review+.

03/10/08 03:34:34 changed by martinkou

  • status changed from reopened to closed.
  • resolution set to fixed.

Fixed with [1687].

Thanks again for reporting these bugs, it isn't easy to spot such details. :)