Interesting string.find hang with the hyphen operator

[Dan Tull <dtull@...>]

I originally just sent this to our internal Lua mailing list, but thought it was an amusing little tale that I'd pass along.

The Lightroom codebase uses these kinds of separator lines for headers and such:

--[[----------------------------------------------------------------------------

----------------------------------------------------------------------------]]--

I had invoked a search with one of the closing kind as part of the selection and our IDE (which has an option to search code using a Lua pattern) went into a tailspin.

A single call to string.find with such an argument can take many, many seconds when it encounters itself. Only 22 hyphens in a row takes over 25 seconds and it is worse than exponential*, so 76 hyphens be effectively infinite. It took me a bit to fully realize why this one was so ill performing, but it is doing (at great cost) exactly what I'd asked it to do. It's easy to forget these powerful little DSLs can be used to express very long running search programs (given the right, or rather wrong, input).

So be careful with your patterns (particularly with the non-greedy matching operator), I guess. ;o)

DT

* I'd have to spend a minute walking through the matching logic to work out the exact Big-O notation for it; it might be O(N!) or similar.

local function printf( ... )
        print( string.format( ... ) )
end

for n = 10, 22, 2 do
        local stringOfDeath = string.format( "%sY", string.rep( "-", n ) )

        local start = os.clock()
        local first = string.find( stringOfDeath, stringOfDeath )

        printf( "%02d  %2.3f  %s  %s", n, os.clock() - start, stringOfDeath:sub( first ), stringOfDeath )
end

--      10  0.000  -Y  ----------X-Y
--      12  0.002  -Y  ------------X-Y
--      14  0.015  -Y  --------------X-Y
--      16  0.095  -Y  ----------------X-Y
--      18  0.605  -Y  ------------------X-Y
--      20  3.956  -Y  --------------------X-Y
--      22  25.531  -Y  ----------------------X-Y