Details
- Reviewers
ilya-biryukov ychen erichkeane
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
I'm open to other suggestions if this doesn't seem like the right approach. The problem is the concept evaluation code is fairly separated in the call stack from this Sema code, so it's hard to think of a minimal change to the Sema code that doesn't break other parts of the language standard.
Like mentioned in https://stackoverflow.com/questions/68853472/is-this-a-bug-in-clangs-c20-concepts-implementation-unnecessary-checking-of, could we not go down the path of considering conversion candidates? It seems that's blessed by the standard.
If I'm understanding the code correctly, the intent of this patch is to definitely consider conversion candidates, only to exclude those conversion candidates that are templated methods where the From type is the same as the To type, which to me mean they are possibly redundant?
Excluding them is basically saying "because it may be a redundant conversion, we should not consider it as the best via function." which doesn't seem correct to me.
I think the straightforward approach would be to check if we're in the ConstraintCheck instantiation context, and if so check if any template parameter is constrained by the same concept. However, I'm worried about the overhead. So I'd prefer to skip this add-conv-candicates-for-copy-elision path (https://github.com/llvm/llvm-project/blob/main/clang/lib/Sema/SemaInit.cpp#L4012-L4053) during the concept check. The compiler guarantees copy elision under certain conditions (C++17) but I could not think of any situation that users want to or could check copy elision inside the concept. So I think we're safe.
Thanks for your suggestion, I didn't know about the context member in Sema. I agree I think this is a much better approach than my original. While looping the code is in the RequirementInstantiation context, so that's the one I've keyed off here. Please let me know if this is what you had in mind.
LGTM. Thanks. That's what I have in mind. The patch needs a rebase though.
For future reference, I want to mention that the infinite recursion could happen in many other ways inside require expression. I'm not sure it is possible or worthwhile to check them all. I think we should do this check for the copy elision path because making conv-functions candidates are merely Clang's implementation detail about copy elision, the standard does not dictate *how* to perform copy elision. So avoiding infinite recursion in this path is better for user experiences.
| clang/lib/Sema/SemaInit.cpp | ||
|---|---|---|
| 4012 | Would be better to check this lazily (inside the if statement below). | |
Oh, one more thing, we probably need to handle nested levels too, for example, foo(a); might be triggered by a template which may be in turn triggered by the concept check. So only checking S.CodeSynthesisContexts.back() seems not enough. We need to check if we're in concept check context regardless of instantiation levels.
I'll defer to your expertise on this one, but wanted to raise two concerns about this approach before proceeding:
a) The documentation around CodeSynthesisContexts asserts it should be treated as a stack (see https://github.com/llvm/llvm-project/blob/a5880b5f9c4a7ee543fbc38d528d2830fc27753e/clang/include/clang/Sema/Sema.h#L9131-L9132)
b) Given this is a heuristic fix, does it make sense to keep it as narrow as possible, to avoid unintended consequences? I share your confidence we will encounter other infinite template expansion bugs, but if we're not going to solve the general problem I would think that each individual fix should be conservative in its coverage.
Thanks
It seems wrong to change semantics of initialization when instantiating concept requirements. It implies that semantic checking may behave differently inside requires expressions, this is a red flag.
Clang has a mechanism to prevent recursion when considering user-defined conversion for copy initialization.
Currently the intention of the Clang code path that handles this case is to:
- Deduce TO to be Deferred
- Try to check Numeric<Deferred>,
- Check conversions during overload resolution for foo(a). Go to step 1, <infinite recursion, so we never get to the next step>
- <never reached> Check that conversion operator converts the type to itself and mark the candidate as failed.
If move the check in step 4 to happen before step 3 (even if we need to duplicate the check), we will get the desired semantics.
Does that look reasonable?
I also agree there is a more general issue with recursive concept instantiations at play here, e.g. for code like
template <class T> concept A = requires (T a) { foo(a); };
template <class T> concept B = requires (T a) { bar(a); };
struct X {};
template <A T> void bar(T);
template <B T> void foo(T);
void test() {
foo(X());
}Clang will currently cut this out because the template instantiation depth is too high, whereas GCC will provide a useful diagnostics that says concept satisfaction computation is recursive.
We probably want a more informative error message too. Probably worth investigating separately from that particular change.
I think the direction we sould go is not to keep this "semantics" (I'm not sure it should be regarded as semantics because the standard wording does not describe any language-level behavior, instead, just say the constructor should not be called in certain cases). Because the bug report and user experience are that this behavior is surprising and no references in the language require it so it is hard to reason about. I guess that's the reason the original implementation describe it as a "workaround". I'd only consider this workaround (i.e, hoist an certain overload resolution rule to avoid recursion) if you're blocked by this and needs a quick fix.
Ideally, I think we should implement this copy elision elsewhere like CodGen to avoid this unexpected semantic (conversion functions become candidate).
Clang will currently cut this out because the template instantiation depth is too high, whereas GCC will provide a useful diagnostics that says concept satisfaction computation is recursive.
We probably want a more informative error message too. Probably worth investigating separately from that particular change.
Agreed. That requires either walking or maintaining extra states in the template instantiation stack and detects cycle, which would make this patch unnecessary.
Not sure if this has come up already but this would still crash on
template <typename T>
concept C = requires(T a) { foo(a); };
struct D1 {
template <C TO> D1(TO);
};
struct D2 {
friend void foo(D1);
};
static_assert(C<D2>);as we only consider conversion to itself (and derived to base) and not user defined conversions.
My suggestion would be to properly handle cycles in CheckConstraintSatisfaction. This problem goes beyond cycles introduced by conversion. See #53213, #44304 and #45736 https://godbolt.org/z/hzM6f3qnW. Most of the bugs are due to an assertion failure while inserting entry into SatisfactionCache.
IIUC, failing on cycles would solve all of these issues.
My suggestion would be detect cycles in CheckConstraintSatisfaction. We already have a way to check "whether we have seen this evaluation before ?" in SatisfactionCache using FoldingSet for ConstraintSatisfaction. We could use a similar set to track the constraints being evaluated. Stop evaluation when we detect a cycle. Attach appropriate details to the Satisfaction and fail the constraint.
Coincidentally 2 of the bugs were just fixed in b9a77b56d8. I do not completely agree with the approach there though. We should be fixing the root cause instead of circumventing the assert in InsertNode by insert-if-not-present. This is why we have 44304 and 50891 still persistent.
We cant use the SatisfactionCache 'just yet', we have to have a different stack, but we should fail there. We should NOT fail the constraint, it needs to be a hard-error based on discussion on the reflector. I'm intending to commit a patch to that effect today/monday.
So the problem that I solved was forming a recovery expression during evaluation, this wasn't a 'circumventing' the assert, this was making sure we dont try to double-cache a legitimate recursive-lookup.
Interestingly, just doing it in CheckConstraintSatisfaction (~SemaConcept.cpp:385) doesn't seem right, we end up catching the failure 'too early', since a FunctionDecl itself goes through there and has its constraints checked. I suspect we actually need to check at the constraint-expr level instead (so down a few levels).
Because of the change to InsertNode to not assert on already cached concepts this patch now works. If I try to catch the recursive expansion on a higher level the test in concepts.cpp for 2-level concept expansion fails. There are some finite recursive use cases for template expansion.
Note that I'm still working on the recursive concept-check (see https://reviews.llvm.org/D136975), and will probably get this part fixed in the next day or two.
I don't know that we can really use the Sema::InstantiatingTemplate bit, as that doesn't really work in cases where we are forming a recovery expression, or the concept caused us to instantiate the same concepts separately somewhere else (like when evaluating the constexprness of a move constructor is the other good example).
Additionally, I think any such check needs to happen at the 'expression' level itself, rather than here at the function.
My biggest problem at the moment is making sure it fails overlaod resolution entirely, rather than just the single candidate (which this has the same problem I believe).
I think the 'this results in a hard error, not failed lookup' is a necessity here based on discussions on the core reflector. Also see: https://reviews.llvm.org/D133052
Would be better to check this lazily (inside the if statement below).