Feedback request on how best to handle recursion in concept satisfaction

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Feedback request on how best to handle recursion in concept satisfaction

Jeff Chapman
Hello,

I'm seeking feedback on how best to handle deep or infinite recursion in
concept satisfaction. Please let me know if there's a better place to ask.

Recursion in satisfaction can occur a few ways, some of which has been fixed by
moving the point of declaration of a concept to prevent directly referencing
itself. However, there's still an issue where overload resolution requires a
concept satisfaction check which depends on the initial overload, etc:

template<typename T>
concept Fooable = requires(T t) { foo(t); };

template<Fooable T>
void foo(T t) { }

Here foo is enabled if it's enabled. PR c++/67934 is an example of this in the
wild, where a default impl of op== depends on op!= and a vice-versa.

I have a patch that addresses this form of recursion -- where the same
requirements are being satisfied with the same arguments -- with an explicit
error message, but it's also possible to get into deep recursion with unique
arguments:

template<int N, typename T>
concept Foo = requires(T t) { foo<N - 1>(t); };

template<int N = 1024 * 1024, typename T = int>
  requires Foo<N, T>
int foo(T t) { return foo<N - 1>(t); }

Similar cases without concepts are handled with
-ftemplate-depth/max_tinst_depth but satisfaction on trunk does not currently
pass through anything that increments tinst_depth.


Is a patch that errors on direct recursion wanted, should it be handled by some
generic depth marker, or is there a better fix?

If a depth marker should be used, should max_tinst_depth be reused, or should a
separate (configurable?) value be used?

Related to the above, should pt.c be reworked or does this seem like something
that should be handled directly in constraint.cc?


Any feedback would be appreciated.

Thank you,
Jeff Chapman II
Reply | Threaded
Open this post in threaded view
|

Re: Feedback request on how best to handle recursion in concept satisfaction

Nathan Sidwell-2
On 10/29/19 4:46 PM, Jeff Chapman wrote:
> Hello,

>
> template<int N, typename T>
> concept Foo = requires(T t) { foo<N - 1>(t); };
>
> template<int N = 1024 * 1024, typename T = int>
>    requires Foo<N, T>
> int foo(T t) { return foo<N - 1>(t); }
>
> Similar cases without concepts are handled with
> -ftemplate-depth/max_tinst_depth but satisfaction on trunk does not currently
> pass through anything that increments tinst_depth.

Why doesn't the std specify the satisfaction nesting limit in the same
way as template instantiation? (at least that's what I infer from your
question).

nathan

--
Nathan Sidwell
Reply | Threaded
Open this post in threaded view
|

Re: Feedback request on how best to handle recursion in concept satisfaction

Jeff Chapman
On Thu, Oct 31, 2019 at 8:03 AM Nathan Sidwell wrote:
> Why doesn't the std specify the satisfaction nesting limit in the same
> way as template instantiation? (at least that's what I infer from your
> question).

I'm not sure why it's not explicitly listed along with the template
instantiation limit ([implimits]/2.41). Perhaps it's something that
should be added? It does seem like a distinct limit since satisfaction
can occur recursively without having more than one template
instantiation in the call stack at any given time. To give an example:

template<int N = 1, typename T = int>
  requires requires(T t) { foo<N + 1>(t); }
void foo(T t) { }

A call to foo<1>(1) results in unbounded call stack like:

resolve foo<1>(int)
  instantiate the decl of foo<1>(int)
  check if foo<1>(int) satisfies its constraints
    resolve foo<2>(int)
      instantiate the decl of foo<2>(int)
      check if foo<2>(int) satisfies its constraints
        ...

Per [temp.inst]/17 "the type-constraints and requires-clause of a
template specialization or member function are not instantiated along
with the specialization or function itself" so instantiating the decl
of foo<1>(int) does not depend on the instantiation of any other
template and the template instantiation depth is only incremented once
before decremented when control flow returns to overload resolution.

This needs to be resolved someway, but reusing the template
instantiation depth limit would be an odd choice since there are no
recursive template instantiations in the process. A parallel
-fsatisfaction-depth= limit and associated diagnostics seems like a
better way to resolve this issue.

Does this seem like a good way forward?


Thanks,
Reply | Threaded
Open this post in threaded view
|

Re: Feedback request on how best to handle recursion in concept satisfaction

Jason Merrill
On Tue, Nov 5, 2019 at 2:42 PM Jeff Chapman <[hidden email]> wrote:

>
> On Thu, Oct 31, 2019 at 8:03 AM Nathan Sidwell wrote:
> > Why doesn't the std specify the satisfaction nesting limit in the same
> > way as template instantiation? (at least that's what I infer from your
> > question).
>
> I'm not sure why it's not explicitly listed along with the template
> instantiation limit ([implimits]/2.41). Perhaps it's something that
> should be added? It does seem like a distinct limit since satisfaction
> can occur recursively without having more than one template
> instantiation in the call stack at any given time. To give an example:
>
> template<int N = 1, typename T = int>
>   requires requires(T t) { foo<N + 1>(t); }
> void foo(T t) { }
>
> A call to foo<1>(1) results in unbounded call stack like:
>
> resolve foo<1>(int)
>   instantiate the decl of foo<1>(int)
>   check if foo<1>(int) satisfies its constraints
>     resolve foo<2>(int)
>       instantiate the decl of foo<2>(int)
>       check if foo<2>(int) satisfies its constraints
>         ...
>
> Per [temp.inst]/17 "the type-constraints and requires-clause of a
> template specialization or member function are not instantiated along
> with the specialization or function itself" so instantiating the decl
> of foo<1>(int) does not depend on the instantiation of any other
> template and the template instantiation depth is only incremented once
> before decremented when control flow returns to overload resolution.
>
> This needs to be resolved someway, but reusing the template
> instantiation depth limit would be an odd choice since there are no
> recursive template instantiations in the process. A parallel
> -fsatisfaction-depth= limit and associated diagnostics seems like a
> better way to resolve this issue.

We track other substitution cases as part of the template
instantiation depth limit, notably instantiating the
noexcept-specifier.  This seems like a similar situation.

Jason