Opened 4 years ago

Closed 4 years ago

#11374 closed bug (fixed)

`-Woverlapping-patterns` induced memory-blowup

Reported by: hvr Owned by: gkaracha
Priority: highest Milestone: 8.0.1
Component: Compiler Version: 8.1
Keywords: pattern checker, PatternMatchWarnings Cc: bgamari
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

I'm afraid I've found yet another case that still let's the pattern checker go crazy (courtesy of hackage:cryptol-2.2.5):

{-# LANGUAGE Haskell2010 #-}

{-# OPTIONS_GHC -Woverlapping-patterns #-}
module Bug where

data Type   = TCon TCon [Type]
            | TUser String [Type] Type
            | TRec [(String,Type)]
            deriving (Show,Eq,Ord)

data TCon   = TC TC
            | TF TFun
            deriving (Show,Eq,Ord)

data TC     = TCNum Integer
            | TCInf
            | TCBit
            | TCSeq
            | TCFun
            | TCTuple Int
            deriving (Show,Eq,Ord)

data TFun   = TCAdd
            | TCSub
            | TCMul
            | TCDiv
            | TCMod
            | TCLg2
            | TCExp
            | TCWidth
            | TCMin
            | TCMax
            | TCLenFromThen
            | TCLenFromThenTo
            deriving (Show, Eq, Ord, Bounded, Enum)

simpFinTy :: Type -> Maybe [Type]
simpFinTy ty = case ty of
    TCon (TC (TCNum _)) _ -> Just []

    TCon (TF tf) [t1]
      | TCLg2    <- tf -> Just [t1]
      | TCWidth  <- tf -> Just [t1]

    TCon (TF tf) [t1,t2]
      | TCAdd <- tf -> Just [t1, t2]
      | TCSub <- tf -> Just [t1]
      | TCMul <- tf -> Just [t1, t2]
      | TCDiv <- tf -> Just [t1]
      | TCMod <- tf -> Just []
      | TCExp <- tf -> Just [t1, t2]
      | TCMin <- tf -> Nothing
      | TCMax <- tf -> Just [t1, t2]

    TCon (TF tf) [_,_,_]
      | TCLenFromThen   <- tf -> Just []
      | TCLenFromThenTo <- tf -> Just []

    _ -> Nothing

Change History (6)

comment:1 Changed 4 years ago by bgamari

Keywords: pattern checker added

comment:2 Changed 4 years ago by simonpj

Keywords: PatternMatchWarnings added

comment:3 Changed 4 years ago by bgamari

George, does Phab:D1795 address this as well?

comment:4 Changed 4 years ago by Ben Gamari <ben@…>

In 28f951e/ghc:

Overhaul the Overhauled Pattern Match Checker

Overhaul the Overhauled Pattern Match Checker

* Changed the representation of Value Set Abstractions. Instead of
using a prefix tree, we now use a list of Value Vector Abstractions.
The set of constraints Delta for every Value Vector Abstraction is the
oracle state so that we solve everything only once.

* Instead of doing everything lazily, we prune at once (and in general
everything is much stricter). Hence, an example written with pattern
guards is checked in almost the same time as the equivalent with
pattern matching.

* Do not store the covered and the divergent sets at all. Since what we
only need is a yes/no (does this clause cover anything? Does it force
any thunk?) We just keep a boolean for each.

* Removed flags `-Wtoo-many-guards` and `-ffull-guard-reasoning`.
Replaced with `fmax-pmcheck-iterations=n`. Still debatable what should
the default `n` be.

* When a guard is for sure not going to contribute anything, we treat
it as such: The oracle is not called and cases `CGuard`, `UGuard` and
`DGuard` from the paper are not happening at all (the generation of a
fresh variable, the unfolding of the pattern list etc.). his combined
with the above seems to be enough to drop the memory increase for test
T783 down to 18.7%.

* Do not export function `dsPmWarn` (it is now called directly from
within `checkSingle` and `checkMatches`).

* Make `PmExprVar` hold a `Name` instead of an `Id`. The term oracle
does not handle type information so using `Id` was a waste of
time/space.

* Added testcases T11195, T11303b (data families) and T11374

The patch addresses at least the following:
Trac #11195, #11276, #11303, #11374, #11162

Test Plan: validate

Reviewers: goldfire, bgamari, hvr, austin

Subscribers: simonpj, thomie

Differential Revision: https://phabricator.haskell.org/D1795

comment:5 Changed 4 years ago by bgamari

comment:6 Changed 4 years ago by bgamari

Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.