Cross option seems to cause duplicate warnings

[iustin]

I've been running with --cross for a long while, but since a recent update (testing with 3.1.3 now), it seems to cause two things

• very slow run
• shows a given single warning in a file once for ~every other module

On a given codebase, non-cross takes ~3.5s, while cross takes ~1m10s, so it kind of looks like it does a cartesian product of all the module pairs?

Running on a minimal example, I have two files, each one function:

• first file (x.hs):

f x y = case x of
 Nothing -> y
 Just x -> x

• second file (y.hs):

g x y = y x

Standard run:

$ hlint .
x.hs:(1,9)-(3,12): Suggestion: Replace case with fromMaybe
Found:
  case x of
    Nothing -> y
    Just x -> x
Perhaps:
  Data.Maybe.fromMaybe y x

1 hint

This is as expected. Run with --cross:

$ hlint --cross .
x.hs:(1,9)-(3,12): Suggestion: Replace case with fromMaybe
Found:
  case x of
    Nothing -> y
    Just x -> x
Perhaps:
  Data.Maybe.fromMaybe y x

x.hs:(1,9)-(3,12): Suggestion: Replace case with fromMaybe
Found:
  case x of
    Nothing -> y
    Just x -> x
Perhaps:
  Data.Maybe.fromMaybe y x

2 hints

Copying y.hs to z.hs results in 3 times the same warning, etc.

Note the same files when checked with hlint 2.1.11 from Debian unstable seems to work fine:

$ /usr/bin/hlint --version
HLint v2.1.11, (C) Neil Mitchell 2006-2018
$ /usr/bin/hlint --cross .
./x.hs:1:9: Suggestion: Use fromMaybe
Found:
  case x of
      Nothing -> y
      Just x -> x
Perhaps:
  fromMaybe y x

1 hint

Help?

[ndmitchell]

The only hint that gets enabled by --cross is the duplicate check, and I'm yet to be convinced that the duplicate checking in HLint is very valuable. Have you found --cross to be valuable? I'm tempted to remove duplicate checking and suggest that people use something dedicated to the task. What are your thoughts?

(I'll look into whether its easy to fix this evening - it may be we're doing something stupid, and O(n^2) would definitely be a problem)

[iustin]

To be fair, I don't know what --cross does, I was assuming it can do suggestion based on the (exhaustive) usage of functions, not just on their declaration. So I don't need it, I just thought cross-module analysis can be smarter for exported symbols (whereas for non-exported ones, inside module is enough).

If it's just duplication… hmm, yes, I have used duplication checks, and found them somewhat useful. But I'd definitely prefer not having that if it makes hlint N times slower, or I could easily use something else if available.

[ndmitchell]

Running HLint on HLint

• Before: 6s normal, gave up after a few minutes with --cross.
• After: 6s normal, 6s with --cross.

There was totally an O(n^2) bug in there! We had a list comp and did for each module, and then again a few lines later, did the same again. At one point one of those was for each haskell-src-exts module and one was for each GHC module - which is how the bug got introduced. That function is only called with singletons apart from the rare case where you pass --cross.

Fantastic spot!

[ndmitchell]

Fixed in 3.1.4 and I wrote a post since its a fun bug: https://neilmitchell.blogspot.com/2020/05/hlint-cross-was-accidentally-quadratic.html