D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 7992 - std.algorithm.find breaks in certain circumstances
Summary: std.algorithm.find breaks in certain circumstances
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: All All
: P2 normal
Assignee: No Owner
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2012-04-26 14:57 UTC by William Moore
Modified: 2012-10-13 14:42 UTC (History)
2 users (show)

See Also:

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this issue.
Description William Moore 2012-04-26 14:57:31 UTC 
When std.algorithm.find is used with a type that forces it to use simpleMindedFind and the type in question supports the length attribute, simpleMindedFind will throw an assert if the string to be searched does not contain the search string.

For example:
struct omgstring {
        string data;
        // Start hasLength functions
        @property {
                size_t length() const {return data.length;}
                void length(size_t len) {data.length = len;}
        }
        // End hasLength functions

        // Start InputRange functions
        bool empty() const {return data.empty();}
        dchar front() const {return data.front();}
        void popFront() {data.popFront();}
        // End InputRange functions

        // Start ForwardRange functions (implies InputRange)
        mycustring save() {return this;}
        // End ForwardRange functions
}

// succeeds
simpleMindedFind!"a == b"("a","b");
// throws assert when it pops past the last element
simpleMindedFind!"a == b"(to!omgstring("a"),to!omgstring("b"));

Note that I'm not actually calling simpleMindedFind directly, but that is the function the code ends up in when throwing the assert.  The code executes correctly if the length property is removed.
Comment 1 William Moore 2012-04-26 15:00:48 UTC 
Note: the structure definition is incorrect, it should be:

struct omgstring {
        string data;
        // Start hasLength functions
        @property {
                size_t length() const {return data.length;}
                void length(size_t len) {data.length = len;}
        }
        // End hasLength functions

        // Start InputRange functions
        bool empty() const {return data.empty();}
        dchar front() const {return data.front();}
        void popFront() {data.popFront();}
        // End InputRange functions

        // Start ForwardRange functions (implies InputRange)
        omgstring save() {return this;}
        // End ForwardRange functions
}
Comment 2 hsteoh 2012-10-09 20:55:47 UTC 
OK, something is very broken in simpleMindedFind(). When both haystack and needle have the length property, estimateNeedleLength is set to false, and estimatedNeedleLength is set to 0. Therefore, haystackTooShort() is always false.

So in the searching loop, the if(haystackTooShort()) is skipped, and it falls straight through to the for(auto h=haystack.save;...) loop. But here, if h.empty is true, then because estimateNeedleLength is false, this goes straight to "continue searching", which calls popFront() on an empty range.