<story><title>On bananas and string matching algorithms</title><url>http://www.wabbo.org/blog/2014/22aug_on_bananas.html</url></story><parent_chain><item><author>StefanKarpinski</author><text>Really interesting post and good debugging work. A couple of take-aways:&lt;p&gt;1. This is one reason it&amp;#x27;s a good idea to use signed ints for lengths even though they can never be negative. Signed 64-bit ints have plenty of range for any array you&amp;#x27;re actually going to encounter. It may also be evidence that it&amp;#x27;s a good idea for mixed signed&amp;#x2F;unsigned arithmetic to produce signed results rather than unsigned: signed tends to be value-correct for &amp;quot;small&amp;quot; values (less than 2^63), including negative results; unsigned sacrifices value-correctness on all negative values to be correct for &lt;i&gt;very&lt;/i&gt; large values, which is a less common case – here it will never happen since there just aren&amp;#x27;t strings that large.&lt;p&gt;2. If you&amp;#x27;re going to use a fancy algorithm like two-way search, you really ought to have a lot of test cases, especially ones that exercise corner cases of the algorithm. 100% coverage of all non-error code paths would be ideal.</text></item></parent_chain><comment><author>haberman</author><text>I&amp;#x27;m not sure I agree with #1. While it&amp;#x27;s true that using signed integers for lengths would have solved this problem, a negative length doesn&amp;#x27;t generally make sense or have any defined meaning.  So if you have any logic that is doing case analysis on lengths, you basically have no reasonable action in the case of a negative length: all you can do is complain that the length got corrupted at some point.&lt;p&gt;For example, imagine that instead of testing whether the strings differed by more than 20, you were just testing whether the needle was &amp;gt;= 20 in length:&lt;p&gt;&lt;pre&gt;&lt;code&gt;    impl Searcher {
        fn new(haystack: &amp;amp;[u8], needle: &amp;amp;[u8]) -&amp;gt; Searcher {
            match needle.len() {
                0..20 =&amp;gt; Naive(NaiveSearcher::New)
                20..uint::MAX =&amp;gt; TwoWay(TwoWaySearcher::New(needle))
                _ =&amp;gt; fail!(&amp;quot;Negative length, shouldn&amp;#x27;t happen!&amp;quot;)
            }
        }
    }
&lt;/code&gt;&lt;/pre&gt;
Part of the feature of an unsigned type IMO is that it cannot have an out-of-domain value by definition.</text></comment>
<story><title>On bananas and string matching algorithms</title><url>http://www.wabbo.org/blog/2014/22aug_on_bananas.html</url></story><parent_chain><item><author>StefanKarpinski</author><text>Really interesting post and good debugging work. A couple of take-aways:&lt;p&gt;1. This is one reason it&amp;#x27;s a good idea to use signed ints for lengths even though they can never be negative. Signed 64-bit ints have plenty of range for any array you&amp;#x27;re actually going to encounter. It may also be evidence that it&amp;#x27;s a good idea for mixed signed&amp;#x2F;unsigned arithmetic to produce signed results rather than unsigned: signed tends to be value-correct for &amp;quot;small&amp;quot; values (less than 2^63), including negative results; unsigned sacrifices value-correctness on all negative values to be correct for &lt;i&gt;very&lt;/i&gt; large values, which is a less common case – here it will never happen since there just aren&amp;#x27;t strings that large.&lt;p&gt;2. If you&amp;#x27;re going to use a fancy algorithm like two-way search, you really ought to have a lot of test cases, especially ones that exercise corner cases of the algorithm. 100% coverage of all non-error code paths would be ideal.</text></item></parent_chain><comment><author>QuantumChaos</author><text>Regarding 2., I&amp;#x27;m going to assume they have at least some unit tests.&lt;p&gt;It&amp;#x27;s not clear that even 100% coverage would have picked up this bug, since it doesn&amp;#x27;t automatically appear as a result of taking a particular code path.&lt;p&gt;I think that comparing to a naive algorithm on a large number of strings, or using a fuzzing tool, might be helpful, but this might also slow down the test suite excessively.&lt;p&gt;I find unit tests are a bit like good form at the gym.  Whenever someone gets injured, they think back to the last exercise they did and find some imperfection in their form.  They then attribute their injury to not using perfect form.  Similarly, whenever a bug appears, there is a tendency to find a unit test that would have caught the bug, and therefore attribute it to insufficient testing.&lt;p&gt;The real value of testing (and good form) can only be demonstrated by having a criteria for good testing and seeing if following this reduces the number of bugs.</text></comment>