GitLab

Posting this for completeness, in case it exposes something more generally suboptimal: I'm not suggesting that such very long module names are likely ever to occur in the real world (and indeed Hugs has a 4k identifier length limit).

In short: parsing "module Module where ..." takes O(length(Module)²) time.

test program (NB: overwrites "./test.hs" without hesitation):

module Main (main) where

import Control.Monad (forM_)
import Data.List (genericReplicate)
import Data.Time.Clock (getCurrentTime, diffUTCTime)
import System.Environment (getArgs)
import System.IO (stdout, hSetBuffering, BufferMode(NoBuffering))
import System.Process (system)

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

test :: Integer -> String
test n = "module M" ++ genericReplicate n 'm' ++ " (main) where main :: IO () ; main = return ()\n"

main :: IO ()
main = do
  [count] <- getArgs
  hSetBuffering stdout NoBuffering
  forM_ (take (read count) fibs) $ \n -> do
    writeFile "test.hs" (test n)
    t0 <- getCurrentTime
    _ <- system "ghci </dev/null >/dev/null test.hs"
    t1 <- getCurrentTime
    putStrLn $ unwords [show n, show (diffUTCTime t1 t0)]

output:

0 0.287553s
1 0.28064s
1 0.294821s
2 0.262876s
3 0.27628s
5 0.27605s
8 0.279612s
13 0.276299s
21 0.267666s
34 0.26738s
55 0.295614s
89 0.270626s
144 0.264852s
233 0.297883s
377 0.295505s
610 0.259852s
987 0.260083s
1597 0.294578s
2584 0.297104s
4181 0.312192s
6765 0.305412s
10946 0.364343s
17711 0.415955s
28657 0.562181s
46368 0.708429s
75025 1.093678s
121393 1.975239s
196418 3.702828s
317811 8.17462s
514229 19.291228s
832040 45.603124s
1346269 116.74497s
2178309 308.660996s

Trac metadata

Trac field	Value
Version	7.4.1
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler (Parser)
Test case
Differential revisions
BlockedBy
Related
Blocking
CC	claudiusmaximus@goto10.org
Operating system
Architecture