View Issue Details

IDProjectCategoryView StatusLast Update
0038513FPCRTLpublic2021-02-22 08:09
Reporteravk Assigned ToFlorian  
PrioritynormalSeverityminorReproducibilityalways
Status closedResolutionfixed 
PlatformanyOSany 
Product Version3.3.1 
Fixed in Version3.3.1 
Summary0038513: Some flaw in the Boyer-Moore algorithm implementation in StrUtils.
DescriptionIt seems that FindMatchesBoyerMooreCaseSensitive (and of course FindMatchesBoyerMooreCaseInSensitive) cannot find all occurrences of a pattern in a given text if the pattern has some periodicity.

For example, for the pattern "abcab" and the text "abcabcabcabcabcabcab" it indicates matches at positions 1, 7, and 13, but it should be 1, 4, 7, 10, 13.

Hope that the attached patch fixes the problem.
TagsNo tags attached.
Fixed in Revision48752
FPCOldBugId
FPCTarget-
Attached Files

Activities

avk

2021-02-19 06:31

reporter  

strutils.patch (760 bytes)   
Index: strutils.pp
===================================================================
--- strutils.pp	(revision 48715)
+++ strutils.pp	(working copy)
@@ -429,8 +429,7 @@
       AddMatch(i+1);
       //Only first match ?
       if not aMatchAll then break;
-      inc(i,OldPatternSize);
-      inc(i,OldPatternSize);
+      inc(i,DeltaJumpTable2[0]);
     end else begin
       i:=i + Max(DeltaJumpTable1[ord(s[i])],DeltaJumpTable2[j]);
     end;
@@ -582,8 +581,7 @@
       AddMatch(i+1);
       //Only first match ?
       if not aMatchAll then break;
-      inc(i,OldPatternSize);
-      inc(i,OldPatternSize);
+      inc(i,DeltaJumpTable2[0]);
     end else begin
       i:=i + Max(DeltaJumpTable1[Ord(lCaseArray[Ord(s[i])])],DeltaJumpTable2[j]);
     end;
strutils.patch (760 bytes)   

avk

2021-02-19 07:25

reporter   ~0129009

Clarification: should be 1, 4, 7, 10, 13, 16.

Adriaan van Os

2021-02-19 08:06

developer   ~0129010

Good catch, something for a programming seminar.

ravi dion

2021-02-19 22:02

reporter   ~0129023

Aren't there any tests for the RTL which should have showed this problem?

Bart Broersma

2021-02-19 23:13

reporter   ~0129024

> Aren't there any tests for the RTL which should have showed this problem?
You have to come up with this scenario first.
If you'ld know at forehand, you'ld have adjusted the code now wouldn't you?

Given this report, you can now easily write a test for the fpc test suite and attach it here.
The fpc team wil appreciate that.

Issue History

Date Modified Username Field Change
2021-02-19 06:31 avk New Issue
2021-02-19 06:31 avk File Added: strutils.patch
2021-02-19 07:25 avk Note Added: 0129009
2021-02-19 08:06 Adriaan van Os Note Added: 0129010
2021-02-19 22:02 ravi dion Note Added: 0129023
2021-02-19 23:13 Bart Broersma Note Added: 0129024
2021-02-21 14:54 Florian Assigned To => Florian
2021-02-21 14:54 Florian Status new => resolved
2021-02-21 14:54 Florian Resolution open => fixed
2021-02-21 14:54 Florian Fixed in Version => 3.3.1
2021-02-21 14:54 Florian Fixed in Revision => 48752
2021-02-21 14:54 Florian FPCTarget => -
2021-02-22 08:09 avk Status resolved => closed