Skip to content

The Pattern-Matching Bug: a disabled-by-default warning on unexpectedly-partial matches#13341

Merged
gasche merged 5 commits intoocaml:trunkfrom
gasche:matching-bug-partiality-warning
Sep 12, 2024
Merged

The Pattern-Matching Bug: a disabled-by-default warning on unexpectedly-partial matches#13341
gasche merged 5 commits intoocaml:trunkfrom
gasche:matching-bug-partiality-warning

Conversation

@gasche
Copy link
Copy Markdown
Member

@gasche gasche commented Jul 30, 2024

This PR is part of the Pattern-Matching Bug Saga, see the summary comment in #7241 (comment) . It is in the context of #13152, the "main" PR that actually fixes the Pattern-Matching Bug, by intentionally pessimizing pattern-matching compilation in certain cases. (It is written on top of #13153, which is itself on top of #13152.)

In the discussion of #13152, @ncik-roberts and myself discussed whether there was a risk of this intentional pessimization affecting certain existing programs. (Either programs that are buggy because of The Pattern-Matching Bug, but their authors are confident that the bug scenario, which involves concurrent mutations of the scrutinees, will not occur in practice, so they would rather be fast than correct. Or programs that are not in fact buggy, but are still pessimized by the pattern-matching compiler because its analysis of when to pessimize over-approximates as always.)

@ncik-roberts proposed that we add a warning, disabled by default, that flags the situation where the code is pessimized by #13152 (or, it turns out, #13076). See the details of the discussion in #13152 (comment) .

The present PR implements such a warning, and documents it in the "Warning reference" section of the reference manual, which has description of the most subtle warnings -- to guide users on when to enable them or how to act when they are raised.

Detail: phrasing of the warning

The warning is raised whenever the pattern-matching compiler detects that the code produced is more partial than expected by the type-checker. The only known case of this situation is due to pattern-matching on mutable fields. Initially I phrased the warning in a rather directed way, saying explicitly that it was raised due to pattern-matching on mutable fields.

Warning 74 [degraded-partiality-on-mutable-match]: This pattern-matching
is not exhaustive as it contains mutable fields whose value may be
mutated concurrently while it is being matched.
(see manual section 13.5.5)

But then we found out (thanks to the warning) that the situation occurred more cases than we originally thought, due to a regression caused by #13076, which in fact degrades partiality in cases not involving mutable fields. I tracked this regression down yesterday and there is a PR open to fix it ( #13338 ), but this experience made me less certain about when this warning can occur -- it is possible that some situations remain (or appear in the future) where other features than mutable fields result in pessimization and this warning is raised. I tuned down the phrasing accordingly:

Warning 74 [unexpected-partial-match]: This pattern-matching appears
to be total, but is compiled as partial. It may generate a Match_failure
exception. This typically occurs due to complex matches on mutable fields.
(see manual section 13.5.5)

@ncik-roberts
Copy link
Copy Markdown
Contributor

ncik-roberts commented Jul 31, 2024

It is not possible to disable or enable this warning by attribute. [@warning "-74"] (and friends) do not disable the warning if the warning is enabled with -w +74.

I believe a similar problem existed for warning 68 while it still existed. (That's the "match-on-mutable-state-prevent-uncurry" warning that went away with syntactic function arity.)

I suspect we would need to store a Warnings.t field in the typedtree for Texp_match and Texp_function (and then use it in matching.ml) to do this properly.

It may well be that the cost-benefit analysis is in favor of merging this as-is — typedtree changes involve some churn.

Copy link
Copy Markdown
Contributor

@ncik-roberts ncik-roberts left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm in favor of this PR. Disabling the warning by default sounds like the right idea, but it is nice to give users the ability to gauge whether their code might get the unexpected Match_failure.

@gasche
Copy link
Copy Markdown
Member Author

gasche commented Jul 31, 2024

I looked at why the warning cannot be silenced with attributes. This is a general issue with warnings emitted during the typedtree->lambda phase. Currently we use Builtin_attributes.warning_scope to evolve the warning scope locally during the type-checking phase (parsetree->typedtree), but no such discipline is followed during the typedtree->lambda phase. I think we could fix this globally, but this is fairly orthogonal to this specific warning, and I agree that tackling the two issues separately is the best course of action -- so I consider it out of scope of the present PR.

@gasche gasche force-pushed the matching-bug-partiality-warning branch 4 times, most recently from b862830 to e72e125 Compare August 1, 2024 07:52
@gasche gasche added maintainer-approval-needed pattern-matching Performance PR or issues affecting runtime performance of the compiled programs labels Aug 1, 2024
@dra27
Copy link
Copy Markdown
Member

dra27 commented Aug 23, 2024

At a highlevel, this looks good to me - I have one very minor comment on the warning name. I agree with your rationale for changing the description (and removing the references to mutability, etc.) but the use of "unexpected" in the name implies to me that this warning is always some kind of potential bug. Especially as we now have correct test examples which we expect to emit an unexpected warning, "unexpected" feels wrong!

Couldn't degraded-[to-]partial-match be used instead of unexpected-partial-match?

@gasche gasche force-pushed the matching-bug-partiality-warning branch from 863ed3a to f9dbe4e Compare August 24, 2024 09:15
@gasche
Copy link
Copy Markdown
Member Author

gasche commented Aug 24, 2024

@dra27 I applied your suggestion so now the name is degraded-to-partial-match. But, come to think of it, I am thinking of changing to match-degraded-to-partial instead, I find that it reads better. Does your native-speaking self agree?

@gasche
Copy link
Copy Markdown
Member Author

gasche commented Aug 26, 2024

@Octachron, @dra27: this is a ping, in case one of you would be willing to revisit -- I applied all review suggestions so far.

@gasche
Copy link
Copy Markdown
Member Author

gasche commented Sep 4, 2024

(gentle ping again)

Copy link
Copy Markdown
Member

@Octachron Octachron left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The warning emission code looks good to me.

However, the warning description spends too much time trying to explain why it would rather avoid discussing the cause of the warning.
In particular, the description should not take 6 paragraphs to mention mutable fields.

I would propose to remove all this tiptoeing before merging the PR.

@gasche
Copy link
Copy Markdown
Member Author

gasche commented Sep 10, 2024

@Octachron the current wording of the documentation (which most people will never read, so maybe it's no big deal if there are two more paragraphs than you would have like) comes from my experience of writing a first version that clearly blamed mutable state for all instances of this warning, and then immediately finding counter-examples where polymorphic variants would result in this warning as well.

The counter-examples that we found were fixed, but structurally the compiler does not raise the warning when it degrades partiality under a mutable match, it raises the warning at toplevel for all situations where it generated a jump to the final handler -- without specific feedback on what caused these situations. To the best of my knowledge, this situation currently only arises due to mutable fields, but I am not 100% confident that this is the case today, and I am willing to bet that this will become wrong in the future again as we keep evolving the language and the pattern-matching compiler.

@Octachron
Copy link
Copy Markdown
Member

You can keep the information that the pessimization might happen in unknown cases, while mentioning earlier the single known case. But I do believe that the sentences about your reluctance to describe the pattern-matching compiler should be removed.

For instance, copy-editing a bit your text:

There are a few rare cases where this totality analysis is insufficient: the
type-checker believes the pattern-matching to be total, but certain values may
try clauses in order and fail to match any of them. In those cases, the
pattern-matching compiler conservatively compiles the pattern-matching as
partial, and emits this warning

(wrong sounds a bit scary in a documentation, situations conflict with the later This situation )

This situation happens rarely: the only known case requires matching on mutable
fields. Moreover, the vast majority of programs will see no performance
difference at all if it were to happen. For these reasons, the warning is
disabled by default: we believe that the right approach when this situation
occurs is to do nothing at all.

@gasche
Copy link
Copy Markdown
Member Author

gasche commented Sep 10, 2024

Thanks! I included your proposed modification.

@gasche gasche force-pushed the matching-bug-partiality-warning branch from 69a0867 to 731b397 Compare September 10, 2024 19:14
@dra27
Copy link
Copy Markdown
Member

dra27 commented Sep 12, 2024

A long time to agree with a name, but degraded-to-partial-match indeeds looks fine to me!

@gasche gasche force-pushed the matching-bug-partiality-warning branch from 731b397 to 2a3669b Compare September 12, 2024 14:17
@Octachron
Copy link
Copy Markdown
Member

My point of view is that this new warning should be cherry-picked to 5.3: the core pattern-matching change is in 5.3, and it doesn't make sense to introduce the warning one version later when it is already implemented.

@gasche
Copy link
Copy Markdown
Member Author

gasche commented Sep 12, 2024

I agree, and I think that it would be nice to also include #13154, which is a relatively minor improvement, has already been reviewed and approved, and whose existence we took into account when reasoning about the desiderability of #13152. On the other hand, no terrible harm would occur if we delay that one to 5.4, so feel free to ask for this.

@Octachron
Copy link
Copy Markdown
Member

Agreed for #13154 in 5.3, since this would decrease the number of versions of the pattern matching compiler present in released compilers.

@gasche
Copy link
Copy Markdown
Member Author

gasche commented Sep 12, 2024

I observe the following failure of the test memory-model/forbidden.ml (in bytecode) on MSVC 64 on this PR:

-Observation MP+PA Never
+Observation MP+PA Sometimes
+Invalid behaviour on test MP+PA

@gasche gasche merged commit 8ce3e6a into ocaml:trunk Sep 12, 2024
gasche added a commit that referenced this pull request Sep 12, 2024
The Pattern-Matching Bug: a disabled-by-default warning on unexpectedly-partial matches

(cherry picked from commit 8ce3e6a)
@hhugo
Copy link
Copy Markdown
Contributor

hhugo commented Feb 3, 2025

@gasche, the warning is not documented in the man page (man ocamlc)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

maintainer-approval-needed pattern-matching Performance PR or issues affecting runtime performance of the compiled programs

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants