Problem with Find/Replace

[sketly]

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.

[w.olchawa]

Confirmed on IE, IE7 and FF2.

[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( [] ) ;

[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.

[martinkou]

Fixed with [1541].

Click here for more info about our SVN system.

[sketly]

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

[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.

[martinkou]

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

[martinkou]

Fixed with [1687].

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