1. 25 Feb, 2016 1 commit
    • Georgios Karachalias's avatar
      (Alternative way to) address #8710 · 67393977
      Georgios Karachalias authored and Ben Gamari's avatar Ben Gamari committed
      Issue a separate warning per redundant (or inaccessible) clause.
      This way each warning can have more precice location information
      (the location of the clause under consideration and not the whole
      match).
      
      I thought that this could be too much but actually the number of
      such warnings is bound by the number of cases matched against (in
      contrast to the non-exhaustive warnings which may be exponentially
      more).
      
      Test Plan: validate
      
      Reviewers: simonpj, austin, bgamari
      
      Reviewed By: bgamari
      
      Subscribers: thomie
      
      Differential Revision: https://phabricator.haskell.org/D1920
      
      GHC Trac Issues: #8710
      67393977
  2. 17 Feb, 2016 1 commit
  3. 16 Feb, 2016 1 commit
  4. 04 Feb, 2016 1 commit
    • Georgios Karachalias's avatar
      Overhaul the Overhauled Pattern Match Checker · 28f951ed
      Georgios Karachalias authored and Ben Gamari's avatar Ben Gamari committed
      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
      28f951ed
  5. 04 Jan, 2016 1 commit
  6. 31 Dec, 2015 1 commit
  7. 30 Dec, 2015 1 commit
  8. 29 Dec, 2015 1 commit
  9. 18 Dec, 2015 1 commit
    • Simon Peyton Jones's avatar
      tcCheckSatisfiability: less aggressive superclass expansion · ff752a1a
      Simon Peyton Jones authored
      In the pattern-match check we are looking for a proof of
      *unsatisfiablity* among a bunch of givens.  The unsat-ness might be
      hidden in the superclasses, so we must expand them.  But in the common
      case where the constraints are satisfiable, we don't want to expand
      a recursive superclass forever.
      
      This is all a bit arbitrary, but then the whole question is
      undecidable anyway.
      
      The bug in Trac #10592 comment:12 was that I expanded superclasses
      forever.  This patch fixes it.
      ff752a1a
  10. 15 Dec, 2015 1 commit
    • Simon Peyton Jones's avatar
      Allow recursive (undecidable) superclasses · 6eabb6dd
      Simon Peyton Jones authored
      This patch fulfils the request in Trac #11067, #10318, and #10592,
      by lifting the conservative restrictions on superclass constraints.
      
      These restrictions are there (and have been since Haskell was born) to
      ensure that the transitive superclasses of a class constraint is a finite
      set.  However (a) this restriction is conservative, and can be annoying
      when there really is no recursion, and (b) sometimes genuinely recursive
      superclasses are useful (see the tickets).
      
      Dimitrios and I worked out that there is actually a relatively simple way
      to do the job. It’s described in some detail in
      
         Note [The superclass story] in TcCanonical
         Note [Expanding superclasses] in TcType
      
      In brief, the idea is to expand superclasses only finitely, but to
      iterate (using a loop that already existed) if there are more
      superclasses to explore.
      
      Other small things
      
      - I improved grouping of error messages a bit in TcErrors
      
      - I re-centred the haddock.compiler test, which was at 9.8%
        above the norm, and which this patch pushed slightly over
      6eabb6dd
  11. 12 Dec, 2015 1 commit
    • Eric Seidel's avatar
      Rework the Implicit CallStack solver to handle local lets. · 3ec8288a
      Eric Seidel authored and Ben Gamari's avatar Ben Gamari committed
      We can't just solve CallStack constraints indiscriminately when they
      occur in the RHS of a let-binder. The top-level given CallStack (if
      any) will not be in scope, so I've re-worked the CallStack solver as
      follows:
      
      1. CallStacks are treated like regular IPs unless one of the following
         two rules apply.
      
      2. In a function call, we push the call-site onto a NEW wanted
         CallStack, which GHC will solve as a regular IP (either directly from a
         given, or by quantifying over it in a local let).
      
      3. If, after the constraint solver is done, any wanted CallStacks
         remain, we default them to the empty CallStack. This rule exists mainly
         to clean up after rule 2 in a top-level binder with no given CallStack.
      
      In rule (2) we have to be careful to emit the new wanted with an
      IPOccOrigin instead of an OccurrenceOf origin, so rule (2) doesn't fire
      again. This is a bit shady but I've updated the Note to explain the
      trick.
      
      Test Plan: validate
      
      Reviewers: simonpj, austin, bgamari, hvr
      
      Reviewed By: simonpj, bgamari
      
      Subscribers: thomie
      
      Differential Revision: https://phabricator.haskell.org/D1422
      
      GHC Trac Issues: #10845
      3ec8288a
  12. 04 Dec, 2015 1 commit
  13. 03 Dec, 2015 1 commit
    • Georgios Karachalias's avatar
      Major Overhaul of Pattern Match Checking (Fixes #595) · 8a506104
      Georgios Karachalias authored
      This patch adresses several problems concerned with exhaustiveness and
      redundancy checking of pattern matching. The list of improvements includes:
      
      * Making the check type-aware (handles GADTs, Type Families, DataKinds, etc.).
        This fixes #4139, #3927, #8970 and other related tickets.
      
      * Making the check laziness-aware. Cases that are overlapped but affect
        evaluation are issued now with "Patterns have inaccessible right hand side".
        Additionally, "Patterns are overlapped" is now replaced by "Patterns are
        redundant".
      
      * Improved messages for literals. This addresses tickets #5724, #2204, etc.
      
      * Improved reasoning concerning cases where simple and overloaded
        patterns are matched (See #322).
      
      * Substantially improved reasoning for pattern guards. Addresses #3078.
      
      * OverloadedLists extension does not break exhaustiveness checking anymore
        (addresses #9951). Note that in general this cannot be handled but if we know
        that an argument has type '[a]', we treat it as a list since, the instance of
        'IsList' gives the identity for both 'fromList' and 'toList'. If the type is
        not clear or is not the list type, then the check cannot do much still. I am
        a bit concerned about OverlappingInstances though, since one may override the
        '[a]' instance with e.g. an '[Int]' instance that is not the identity.
      
      * Improved reasoning for nested pattern matching (partial solution). Now we
        propagate type and (some) term constraints deeper when checking, so we can
        detect more inconsistencies. For example, this is needed for #4139.
      
      I am still not satisfied with several things but I would like to address at
      least the following before the next release:
          Term constraints are too many and not printed for non-exhaustive matches
      (with the exception of literals). This sometimes results in two identical (in
      appearance) uncovered warnings. Unless we actually show their difference, I
      would like to have a single warning.
      8a506104