Opened 8 years ago

Closed 8 years ago

Last modified 8 years ago

#5783 closed bug (invalid)

Data.Text.isPrefixOf fails to terminate

Reported by: reinerp Owned by:
Priority: highest Milestone: 7.4.1
Component: Compiler Version: 7.4.1-rc1
Keywords: Cc: leon.p.smith@…
Operating System: MacOS X Architecture: x86_64 (amd64)
Type of failure: Incorrect result at runtime Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

The function Data.Text.isPrefixOf fails to terminate with GHC 7.4-rc1, although it terminates with GHC-7.2. Reproduction instructions:

$ cd ghc-7.4.0.20111219
$ sudo make install
$ cabal -V
cabal-install version 0.10.2
using version 1.10.1.0 of the Cabal library 
$ cabal install text-0.11.1.12
$ cd /tmp
$ cat >Test.hs
import Data.Text
main = print (pack "A" `isPrefixOf` pack "AB")
$ runghc Test.hs
<program hangs on 100% CPU use, without producing any output>

Unfortunately, it appears to be rather difficult to create a reduced test case; the problem disappears when I make any attempt to minimize it.

I have verified this on Mac OS X 10.7.2 and 64-bit Ubuntu 10.10.

Change History (4)

comment:1 Changed 8 years ago by lpsmith

Cc: leon.p.smith@… added

I can confirm this on ghc-7.4.0.2012011 on 64-bit Ubuntu 11.10. Also see #5796.

comment:2 Changed 8 years ago by simonmar

difficulty: Unknown
Milestone: 7.4.1
Priority: normalhighest

Sounds rather serious, let's look into it.

comment:3 Changed 8 years ago by simonmar

Resolution: invalid
Status: newclosed

In Data.Text there is this:

-- | /O(n)/ The 'isPrefixOf' function takes two 'Text's and returns
-- 'True' iff the first is a prefix of the second.  Subject to fusion.
isPrefixOf :: Text -> Text -> Bool
isPrefixOf a@(Text _ _ alen) b@(Text _ _ blen) =
    alen <= blen && S.isPrefixOf (stream a) (stream b)
{-# INLINE [1] isPrefixOf #-}

{-# RULES
"TEXT isPrefixOf -> fused" [~1] forall s t.
    isPrefixOf s t = S.isPrefixOf (stream s) (stream t)
"TEXT isPrefixOf -> unfused" [1] forall s t.
    S.isPrefixOf (stream s) (stream t) = isPrefixOf s t
  #-}

It looks to me like GHC has applied the second rewrite rule to end up with

isPrefixOf a@(Text _ _ alen) b@(Text _ _ blen) =
    alen <= blen && isPrefixOf a b

which is an infinite loop when alen <= blen.

So I don't think this is a bug, but the text package will need to be fixed. Maybe this is going wroing now because we're optimising INLINE functions after capturing their definitions, whereas we weren't before.

comment:4 Changed 8 years ago by bos

Thanks for the diagnosis!

Note: See TracTickets for help on using tickets.