Skip to content
Success

Changes

Summary

  1. parmatch: make 'exhaust' lazy by returning a Seq.t (commit: 8f71174) (details)
  2. add regression tests for fragile-matching stack overflows (commit: a8adec1) (details)
  3. Changes entry (commit: f8e24bd) (details)
  4. parmatch: ensure specialized submatrices are in source order (commit: d8acfa9) (details)
Commit 8f71174eb22b837efab890aade8b85daf141e5a4 by gabriel.scherer
parmatch: make 'exhaust' lazy by returning a Seq.t

This solves exponential-blowup issue with the strict traversal and/or
strict witness computation in cases where an exponential number of
counter-examples is generated. This fixes Stack Overflow and
exponential-time issues on examples using or-patterns heavily,
including one that naturally found its way in real-world user
code (see the following testsuite commit).

We now systematically keep only one counter-example, instead of
letting the type-checker decide whether to discard
counter-examples (in Backtrack_or mode) or to preserve
them (in Refine_or mode).

Note: in the exhaustivity warning, there are sub-messages printed to
indicate that:

- the exhaustivity counter-example is related to an extensible type, or
- that a when-guarded clause does match the counter-example

In both cases the warning is there to explain the counter-example(s)
shown (not a property of all counter-examples); keeping at most one
valid counter-example means that they will be printed less often, but
it is the correct/intended behavior in that case.
(commit: 8f71174)
The file was modifiedtestsuite/tests/basic-more/morematch.compilers.reference (diff)
The file was modifiedtyping/parmatch.ml (diff)
The file was modifiedtestsuite/tests/typing-warnings/exhaustiveness.ml (diff)
Commit a8adec16f1e23e664d66dc03b4e8ca8f8485987b by gabriel.scherer
add regression tests for fragile-matching stack overflows
(commit: a8adec1)
The file was addedtestsuite/tests/typing-warnings/fragile_matching.ml
The file was modifiedChanges (diff)
Commit d8acfa92e4c25703d90de0675942c6ba74b11a4a by gabriel.scherer
parmatch: ensure specialized submatrices are in source order

We produce exhaustivity counter-example in the order of the
specialized submatrices. Having submatrices in source order gives the
nice behavior that the clause that would naturally been inserted first
in the source is given first as a counter-example.

Consider for example:

    function
    | true, true -> true
    | false, false -> false

The two counter-examples are (true, false) and (false, true).

Before this patch, (false, true) would be shown first.
After this patch, (true, false) is shown first.
This corresponds to the following natural completion order:

    function
    | true, true -> true
    | true, false -> ?
    | false, false -> false
    | false, true -> ?

On the other hand, the ordering of the default submatrix, with respect
to the specialized submatrices, is not preserved -- it is always
ordered last.
One could intuitively expect the default submatrix to appear in the
position of the first omega row in the source. We tried this, and
it is not a good idea:
- the change is much more invasive as the interface of
  `build_specialized_submatrices` has to change
- the behavior of the result is in fact unpleasant; it is not
  intuitive to order counter-examples in this way.

For example, consider:

    function
    | _, None -> false
    | true, Some true -> false

The two exhaustivity counter-examples are (true, Some false)
and (false, Some _). The second comes from the default submatrix:
morally it is (_, Some _), with "some other constructor missing from
the column" instead of the first _. There is no reason to suppose that
the user would want to place this (_, Some _) or (false, Some _)
counter-example first in the completed code; indeed, this intuition
would suggest writing an exhaustive covering of patterns of the
form (_, foo), inserted after the first clause, but then the other
clauses below become unnecessary!

When an omega patterns appears high in the column like this, it is
usually because there is a very specific matching condition to the
rest of its row, that justifies some shortcutting behavior. The
program is typically *not* completed by adding more specific matching
conditions.
(commit: d8acfa9)
The file was modifiedtestsuite/tests/typing-gadts/test.ml (diff)
The file was modifiedtestsuite/tests/typing-warnings/exhaustiveness.ml (diff)
The file was modifiedtestsuite/tests/typing-gadts/pr5785.ml (diff)
The file was modifiedtyping/parmatch.ml (diff)
The file was modifiedtestsuite/tests/typing-gadts/yallop_bugs.ml (diff)