Bug 7992 – std.algorithm.find breaks in certain circumstances

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.

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 }

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.

Commits pushed to master at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/01a690654afa50aeb1101abc734de86afbc1b552 Add unittest for issue 7992. https://github.com/D-Programming-Language/phobos/commit/350d960f879a773296c7e553a88b0cdcf1e7a886 Merge pull request #852 from quickfur/issue7992 FIx issue 7992