substring search api

[Duncan Coutts]

I want to start a discussion about a string searching api, especially with
respect to ByteStrings.

I'm concerned that we're about to release a bytestring package along with
ghc-6.8 that will freeze a less than ideal string search api in stone. We have
an opportunity to make that better since at the moment I think there are few
serious users of that api since the current implementation is very slow. However
in this release cycle we're going to get optimised string searching algorithms
and then I expect the number of users to pick up. I'd be a shame if that forces
us to keep a not very nice api.

That said, here is the current api.

-- | Find the indexes of all (possibly overlapping) occurances of a
-- substring in a string.
findSubstrings :: ByteString -- ^ String to search for.
               -> ByteString -- ^ String to seach in.
               -> [Int]

-- | Get the first index of a substring in another string,
--   or 'Nothing' if the string is not found.
findSubstring :: ByteString -- ^ String to search for.
              -> ByteString -- ^ String to seach in.
              -> Maybe Int
findSubstring p s = listToMaybe (findSubstrings p s)

-- | Check whether one string is a substring of another.
isSubstringOf :: ByteString -- ^ String to search for.
              -> ByteString -- ^ String to search in.
              -> Bool
isSubstringOf p s = not (null (findSubstrings p s))

We only have it implemented for strict ByteStrings at the moment. This api isn't
too bad for the strict ByteString implementation since we can use indexes to
select substrings in O(1) time. However for lazy bytestrings index are much less
good since we have to traverse the list of chunks to use the indexes.

A more compelling argument is that it's not very Haskelly to use indexes. We
normally deal in spans rather than offsets and lengths.

One possible alternative that I think is more Haskelly and would suit the strict
and lazy (and indeed ordinary list []) implementation is:

findSubstring :: ByteString -- ^ String to search for.
              -> ByteString -- ^ String to seach in.
              -> (ByteString,  -- span before search string
                  ByteString)  -- span beginning search string, or empty

compare this to our standard List.break function.

> break isSpace "foo bar" = ("foo", " bar")
> break isSpace "foobar"  = ("foo bar", "")

So for findSubstring we'd have:

> findSubstring "bar" "foo bar baz"      = ("foo ","bar baz")
> findSubstring "notfound" "foo bar baz" = ("foo bar baz", "")

I quite like this as the primitive.

isSubstringOf is easily definable in terms of that.

I should note that there is really no performance penalty for working in terms
of spans rather than indexes. Indeed for the lazy case it'd be faster.

findSubstrings is much less clear. What's not clear is what the result type and
content should be. The current impl that gives us a list of indexes of
possibly-overlapping occurrences seems straightforward. What is the break/span
style equivalent?

A couple possibilities:

findSubstrings :: ByteString -> ByteString -> [ByteString]

where each result begins an occurrence and includes the trailing text before the
next occurrence. Of course that means we loose any initial span. So we could have:

findSubstrings :: ByteString -> ByteString -> (ByteString, [ByteString])

that includes the initial span.

Then there's the issue of overlapping spans or not. Overlapping seems more
general but also seems confusing when done in terms of spans.

Or we could just side-step the issue and not provide a findSubstrings at all and
let people implement the behavior they want in terms of findSubstring. Afterall
there is no 'many' tokenising variant of List.span or List.break, probably
because of the wide variation in requirements.

I'd very much appreciate peoples opinions on this. Though bear in mind that I'm
not looking for a large string searching framework, I want to pick a supportable
primitive for strict and lazy bytestring searching that can go into the
bytestring library now so we can avoid freezing a worse api.

Duncan