Opened 9 years ago

Closed 9 years ago

#1828 closed Bug (fixed)

Problem with Find/Replace

Reported by: sketly Owned by: 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 (2)

1828.patch (3.7 KB) - added by martinkou 9 years ago.
1828_2.patch (2.8 KB) - added by martinkou 9 years ago.

Download all attachments as: .zip

Change History (15)

comment:1 Changed 9 years ago by w.olchawa

  • Keywords Confirmed added

Confirmed on IE, IE7 and FF2.

comment:2 Changed 9 years ago 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( [] ) ;

comment:3 Changed 9 years ago by fredck

  • Keywords HasPatch added
  • Milestone set to FCKeditor 2.6

comment:4 Changed 9 years ago by martinkou

  • Owner set to martinkou
  • Status changed from new to assigned

comment:5 Changed 9 years ago 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.

Changed 9 years ago by martinkou

comment:6 Changed 9 years ago by martinkou

  • Keywords Review? added

comment:7 Changed 9 years ago by fredck

  • Keywords Review+ added; Review? removed

comment:8 Changed 9 years ago by martinkou

  • Resolution set to fixed
  • Status changed from assigned to closed

Fixed with [1541].

Click here for more info about our SVN system.

comment:9 Changed 9 years ago by sketly

  • Resolution fixed deleted
  • Status changed from closed to reopened

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

comment:10 Changed 9 years ago 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.

Changed 9 years ago by martinkou

comment:11 Changed 9 years ago by martinkou

  • Keywords Review? added; Review+ removed

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

comment:12 Changed 9 years ago by fredck

  • Keywords Review+ added; Review? removed

comment:13 Changed 9 years ago by martinkou

  • Resolution set to fixed
  • Status changed from reopened to closed

Fixed with [1687].

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

Note: See TracTickets for help on using tickets.
© 2003 – 2016 CKSource – Frederico Knabben. All rights reserved. | Terms of use | Privacy policy