Opened 10 years ago

Closed 9 years ago

#1828 closed Bug (fixed)

Problem with Find/Replace

Reported by: sketly Owned by: Martin Kou
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 Martin Kou 10 years ago.
1828_2.patch (2.8 KB) - added by Martin Kou 9 years ago.

Download all attachments as: .zip

Change History (15)

comment:1 Changed 10 years ago by Wojciech Olchawa

Keywords: Confirmed added

Confirmed on IE, IE7 and FF2.

comment:2 Changed 10 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 10 years ago by Frederico Caldeira Knabben

Keywords: HasPatch added
Milestone: FCKeditor 2.6

comment:4 Changed 10 years ago by Martin Kou

Owner: set to Martin Kou
Status: newassigned

comment:5 Changed 10 years ago by Martin Kou

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 10 years ago by Martin Kou

Attachment: 1828.patch added

comment:6 Changed 10 years ago by Martin Kou

Keywords: Review? added

comment:7 Changed 10 years ago by Frederico Caldeira Knabben

Keywords: Review+ added; Review? removed

comment:8 Changed 9 years ago by Martin Kou

Resolution: fixed
Status: assignedclosed

Fixed with [1541].

Click here for more info about our SVN system.

comment:9 Changed 9 years ago by sketly

Resolution: fixed
Status: closedreopened

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 Martin Kou

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 Martin Kou

Attachment: 1828_2.patch added

comment:11 Changed 9 years ago by Martin Kou

Keywords: Review? added; Review+ removed

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

comment:12 Changed 9 years ago by Frederico Caldeira Knabben

Keywords: Review+ added; Review? removed

comment:13 Changed 9 years ago by Martin Kou

Resolution: fixed
Status: reopenedclosed

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 – 2017 CKSource – Frederico Knabben. All rights reserved. | Terms of use | Privacy policy