[c++-concepts] code review

[c++-concepts] code review

[Jason Merrill]

It looks like things are coming together pretty well.  What's your 
feeling about readiness to merge into the trunk?  Is the branch down to 
no regressions?

See you on Monday!

> @@ -4146,21 +4146,21 @@ build_new_function_call (tree fn, vec<tree, va_gc> **args, bool koenig_p,
>        if (TREE_CODE (fn) == TEMPLATE_ID_EXPR)
>          {
>            /* If overload resolution selects a specialization of a
> +             function concept for non-dependent template arguments,
> +             the expression is true if the constraints are satisfied
> +             and false otherwise.
>
>               NOTE: This is an extension of Concepts Lite TS that
>               allows constraints to be used in expressions. */
> +          if (flag_concepts && !processing_template_decl)
>              {
>                tree tmpl = DECL_TI_TEMPLATE (cand->fn);
> +              tree targs = DECL_TI_ARGS (cand->fn);
>                tree decl = DECL_TEMPLATE_RESULT (tmpl);
> +              if (DECL_DECLARED_CONCEPT_P (decl)
> +                  && !uses_template_parms (targs)) {
> +                return evaluate_function_concept (decl, targs);

If processing_template_decl is false, uses_template_parms should always 
be false as well.

> +function_concept_check_p (tree t)

> +  tree fn = CALL_EXPR_FN (t);
> +  if (TREE_CODE (fn) == TEMPLATE_ID_EXPR
> +      && TREE_CODE (TREE_OPERAND (fn, 0)) == OVERLOAD)
> +    {
> +      tree f1 = OVL_FUNCTION (TREE_OPERAND (fn, 0));

I think you want get_first_fn here.

>    if (TEMPLATE_PARM_CONSTRAINTS (current_template_parms))
> -    TYPE_CANONICAL (type) = type;
> +    SET_TYPE_STRUCTURAL_EQUALITY (type);

This seems like papering over an underlying issue.  What was the 
testcase that motivated this change?

> @@ -11854,7 +11854,7 @@ tsubst_decl (tree t, tree args, tsubst_flags_t complain)
> -           if (!spec)
> +           if (!spec && DECL_LANG_SPECIFIC (t))
> -       if (!local_p)
> +       if (!local_p && DECL_LANG_SPECIFIC (r))

What motivated these changes?  From the testcase, it seems that you're 
getting here with the decl for "using TD = int", which shouldn't happen.

> @@ -1159,7 +1159,6 @@ check_noexcept_r (tree *tp, int * /*walk_subtrees*/, void * /*data*/)
> -      tree type = TREE_TYPE (TREE_TYPE (fn));
> -      if (!TYPE_NOTHROW_P (type))
> +      if (!TYPE_NOTHROW_P (TREE_TYPE (fn)))

The old code was incorrectly assuming that CALL_EXPR_FN is always a 
function pointer, but your new code seems to be incorrectly assuming 
that it's always a function or an expression taking the address of a 
function; I think this will break on a call to a function pointer variable.

> @@ -3481,13 +3481,27 @@ cxx_eval_constant_expression (const constexpr_ctx *ctx, tree t,
>      case REQUIRES_EXPR:
> +      if (!processing_template_decl)
> +        return evaluate_constraint_expression (t, NULL_TREE);
> +      else
> +        *non_constant_p = true;
> +        return t;

We shouldn't get here with a dependent REQUIRES_EXPR (or any dependent 
expression), so we shouldn't ever hit the else clause.

> @@ -18063,18 +18063,41 @@ cp_parser_declarator (cp_parser* parser,
> +  /* Function declarations may be followed by a trailing
> +     requires-clause. Declarators for function declartions
> +     are function declarators wrapping an id-declarator.
> +     If the inner declarator is anything else, it does not
> +     declare a function. These may also be reference or
> +     pointer declarators enclosing such a function declarator.
> +     In the declaration :
> +
> +        int *f(args)
> +
> +     the declarator is *f(args).
> +
> +     Abstract declarators cannot have a requires-clauses
> +     because they do not declare functions. Here:
>
>          void f() -> int& requires false
>
> +     The trailing return type contains an abstract declarator,
> +     and the requires-clause applies to the function
> +     declaration and not the abstract declarator.  */
> +  if (flag_concepts && dcl_kind != CP_PARSER_DECLARATOR_ABSTRACT)
>      {
> +      /* We could have things like *f(args) or &f(args).
> +         Look inside references and pointers.  */
> +      cp_declarator* p = declarator;
> +      if (p->kind == cdk_reference || p->kind == cdk_pointer)
> +        p = p->declarator;
> +
> +      /* Pointers or references with no name, or functions
> +         with no name cannot have constraints.  */
> +      if (!p || !p->declarator)
> +        return declarator;
> +
> +      /* Look for f(args) but not (*f)(args).  */
> +      if (p && p->kind == cdk_function && p->declarator->kind == cdk_id)

I think you can use function_declarator_p here.

> +static inline bool
> +pending_expansion_p (tree t)
> +{
> +  return (TREE_CODE (t) == PARM_DECL && CONSTRAINT_VAR_P (t)
> +          && PACK_EXPANSION_P (TREE_TYPE (t)));
> +}

What's the difference between this and function_parameter_pack_p?

> +  /* A sentinel class that ensures that deferred access checks
> +     are popped before a function returns.  */
> +  struct deferring_access_check_sentinel
> +  {
> +    deferring_access_check_sentinel ()
> +    {
> +      push_deferring_access_checks (dk_deferred);
> +    }
> +    ~ deferring_access_check_sentinel ()
> +    {
> +      pop_deferring_access_checks ();
> +    }
> +  }

Let's put this with the other RAII sentinels in cp-tree.h.

> +                       Lifting of concept definitions

Could we have a bit more description of what "lifting" means here?

> +/*---------------------------------------------------------------------------
> +                        Constraint normalization
> +---------------------------------------------------------------------------*/

You have two of these headers; I guess the first one should be 
"transformation" and could use more description.  On the second, I would 
retain the old comment

> -// Normalize a template requirement to a logical formula written in terms of
> -// atomic propositions, returing the new expression.  If the expression cannot
> -// be normalized, a NULL_TREE is returned.

> +check_implicit_conversion_constraint (tree t, tree args,
> +                                      tsubst_flags_t complain, tree in_decl)
> +{
> +  tree expr = ICONV_CONSTR_EXPR (t);
> +
> +  /* Don't tsubst as if we're processing a template. If we try
> +     to we can end up generating template-like expressions
> +     (e.g., modop-exprs) that aren't properly typed. */
> +  int saved_template_decl = processing_template_decl;
> +  processing_template_decl = 0;

Why are we checking constraints when processing_template_decl is true?

> +   Note that this is the only place that we instantiate the
> +   constraints. */
> +bool
> +check_constraints (tree ci, tree args)

Except for tsubst_constraint?

> +  ++processing_template_decl;
> +  tree constr = transform_expression (lift_function_definition (fn, args));
> +  --processing_template_decl;

Why do you need to set processing_template_decl here and in other calls 
to transform_expression?  I don't notice anything that would be helped, 
especially now that you're using separate tree codes for constraints, 
though there is this in check_logical_expr:

> +  /* Resolve the logical operator. Note that template processing is
> +     disabled so we get the actual call or target expression back.
> +     not_processing_template_sentinel sentinel.

I guess that isn't needed anymore?

> +   FIXME: This is defined in pt.c because it's garbage collection
> +   code is not being generated for constraint.cc. */
> +static GTY (()) hash_table<constr_hasher> *decl_constraints;

I think you need to add constraint.cc to the gtfiles variable in 
cp/config-lang.in.  It also looks like the GTFILES_H rule in 
gcc/Makefile.in assumes that all sources have the .c extension, so that 
may need adjustment.

> @@ -2454,6 +2454,8 @@ finish_call_expr (tree fn, vec<tree, va_gc> **args, bool d
>               next = OVL_CHAIN (fn);
> +              if (flag_concepts)
> +                remove_constraints (OVL_FUNCTION (fn));

I don't think we want to remove constraints here; this code is just 
discarding the OVERLOAD node, not the FUNCTION_DECL.

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

> It looks like things are coming together pretty well.  What's your feeling
> about readiness to merge into the trunk?  Is the branch down to no
> regressions?

They are coming together pretty well. We have one major unit test
failure involving template introductions (Braden is working on it),
one involving constraint equivalence that I plan to tackle next week.

Other than those issues, which I hope to clear up next week, I think it's ready.

> See you on Monday!

Unfortunately, I won't be attending.

Andrew

>
>> @@ -4146,21 +4146,21 @@ build_new_function_call (tree fn, vec<tree, va_gc>
>> **args, bool koenig_p,
>>        if (TREE_CODE (fn) == TEMPLATE_ID_EXPR)
>>          {
>>            /* If overload resolution selects a specialization of a
>> +             function concept for non-dependent template arguments,
>> +             the expression is true if the constraints are satisfied
>> +             and false otherwise.
>>
>>               NOTE: This is an extension of Concepts Lite TS that
>>               allows constraints to be used in expressions. */
>> +          if (flag_concepts && !processing_template_decl)
>>              {
>>                tree tmpl = DECL_TI_TEMPLATE (cand->fn);
>> +              tree targs = DECL_TI_ARGS (cand->fn);
>>                tree decl = DECL_TEMPLATE_RESULT (tmpl);
>> +              if (DECL_DECLARED_CONCEPT_P (decl)
>> +                  && !uses_template_parms (targs)) {
>> +                return evaluate_function_concept (decl, targs);
>
>
> If processing_template_decl is false, uses_template_parms should always be
> false as well.
>
>> +function_concept_check_p (tree t)
>
>
>> +  tree fn = CALL_EXPR_FN (t);
>> +  if (TREE_CODE (fn) == TEMPLATE_ID_EXPR
>> +      && TREE_CODE (TREE_OPERAND (fn, 0)) == OVERLOAD)
>> +    {
>> +      tree f1 = OVL_FUNCTION (TREE_OPERAND (fn, 0));
>
>
> I think you want get_first_fn here.
>
>>    if (TEMPLATE_PARM_CONSTRAINTS (current_template_parms))
>> -    TYPE_CANONICAL (type) = type;
>> +    SET_TYPE_STRUCTURAL_EQUALITY (type);
>
>
> This seems like papering over an underlying issue.  What was the testcase
> that motivated this change?
>
>> @@ -11854,7 +11854,7 @@ tsubst_decl (tree t, tree args, tsubst_flags_t
>> complain)
>> -           if (!spec)
>> +           if (!spec && DECL_LANG_SPECIFIC (t))
>> -       if (!local_p)
>> +       if (!local_p && DECL_LANG_SPECIFIC (r))
>
>
> What motivated these changes?  From the testcase, it seems that you're
> getting here with the decl for "using TD = int", which shouldn't happen.
>
>> @@ -1159,7 +1159,6 @@ check_noexcept_r (tree *tp, int * /*walk_subtrees*/,
>> void * /*data*/)
>> -      tree type = TREE_TYPE (TREE_TYPE (fn));
>> -      if (!TYPE_NOTHROW_P (type))
>> +      if (!TYPE_NOTHROW_P (TREE_TYPE (fn)))
>
>
> The old code was incorrectly assuming that CALL_EXPR_FN is always a function
> pointer, but your new code seems to be incorrectly assuming that it's always
> a function or an expression taking the address of a function; I think this
> will break on a call to a function pointer variable.
>
>> @@ -3481,13 +3481,27 @@ cxx_eval_constant_expression (const constexpr_ctx
>> *ctx, tree t,
>>      case REQUIRES_EXPR:
>> +      if (!processing_template_decl)
>> +        return evaluate_constraint_expression (t, NULL_TREE);
>> +      else
>> +        *non_constant_p = true;
>> +        return t;
>
>
> We shouldn't get here with a dependent REQUIRES_EXPR (or any dependent
> expression), so we shouldn't ever hit the else clause.
>
>> @@ -18063,18 +18063,41 @@ cp_parser_declarator (cp_parser* parser,
>> +  /* Function declarations may be followed by a trailing
>> +     requires-clause. Declarators for function declartions
>> +     are function declarators wrapping an id-declarator.
>> +     If the inner declarator is anything else, it does not
>> +     declare a function. These may also be reference or
>> +     pointer declarators enclosing such a function declarator.
>> +     In the declaration :
>> +
>> +        int *f(args)
>> +
>> +     the declarator is *f(args).
>> +
>> +     Abstract declarators cannot have a requires-clauses
>> +     because they do not declare functions. Here:
>>
>>          void f() -> int& requires false
>>
>> +     The trailing return type contains an abstract declarator,
>> +     and the requires-clause applies to the function
>> +     declaration and not the abstract declarator.  */
>> +  if (flag_concepts && dcl_kind != CP_PARSER_DECLARATOR_ABSTRACT)
>>      {
>> +      /* We could have things like *f(args) or &f(args).
>> +         Look inside references and pointers.  */
>> +      cp_declarator* p = declarator;
>> +      if (p->kind == cdk_reference || p->kind == cdk_pointer)
>> +        p = p->declarator;
>> +
>> +      /* Pointers or references with no name, or functions
>> +         with no name cannot have constraints.  */
>> +      if (!p || !p->declarator)
>> +        return declarator;
>> +
>> +      /* Look for f(args) but not (*f)(args).  */
>> +      if (p && p->kind == cdk_function && p->declarator->kind == cdk_id)
>
>
> I think you can use function_declarator_p here.
>
>> +static inline bool
>> +pending_expansion_p (tree t)
>> +{
>> +  return (TREE_CODE (t) == PARM_DECL && CONSTRAINT_VAR_P (t)
>> +          && PACK_EXPANSION_P (TREE_TYPE (t)));
>> +}
>
>
> What's the difference between this and function_parameter_pack_p?
>
>> +  /* A sentinel class that ensures that deferred access checks
>> +     are popped before a function returns.  */
>> +  struct deferring_access_check_sentinel
>> +  {
>> +    deferring_access_check_sentinel ()
>> +    {
>> +      push_deferring_access_checks (dk_deferred);
>> +    }
>> +    ~ deferring_access_check_sentinel ()
>> +    {
>> +      pop_deferring_access_checks ();
>> +    }
>> +  }
>
>
> Let's put this with the other RAII sentinels in cp-tree.h.
>
>> +                       Lifting of concept definitions
>
>
> Could we have a bit more description of what "lifting" means here?
>
>>
>> +/*---------------------------------------------------------------------------
>> +                        Constraint normalization
>>
>> +---------------------------------------------------------------------------*/
>
>
> You have two of these headers; I guess the first one should be
> "transformation" and could use more description.  On the second, I would
> retain the old comment
>
>> -// Normalize a template requirement to a logical formula written in terms
>> of
>> -// atomic propositions, returing the new expression.  If the expression
>> cannot
>> -// be normalized, a NULL_TREE is returned.
>
>
>> +check_implicit_conversion_constraint (tree t, tree args,
>> +                                      tsubst_flags_t complain, tree
>> in_decl)
>> +{
>> +  tree expr = ICONV_CONSTR_EXPR (t);
>> +
>> +  /* Don't tsubst as if we're processing a template. If we try
>> +     to we can end up generating template-like expressions
>> +     (e.g., modop-exprs) that aren't properly typed. */
>> +  int saved_template_decl = processing_template_decl;
>> +  processing_template_decl = 0;
>
>
> Why are we checking constraints when processing_template_decl is true?
>
>> +   Note that this is the only place that we instantiate the
>> +   constraints. */
>> +bool
>> +check_constraints (tree ci, tree args)
>
>
> Except for tsubst_constraint?
>
>> +  ++processing_template_decl;
>> +  tree constr = transform_expression (lift_function_definition (fn,
>> args));
>> +  --processing_template_decl;
>
>
> Why do you need to set processing_template_decl here and in other calls to
> transform_expression?  I don't notice anything that would be helped,
> especially now that you're using separate tree codes for constraints, though
> there is this in check_logical_expr:
>
>> +  /* Resolve the logical operator. Note that template processing is
>> +     disabled so we get the actual call or target expression back.
>> +     not_processing_template_sentinel sentinel.
>
>
> I guess that isn't needed anymore?
>
>> +   FIXME: This is defined in pt.c because it's garbage collection
>> +   code is not being generated for constraint.cc. */
>> +static GTY (()) hash_table<constr_hasher> *decl_constraints;
>
>
> I think you need to add constraint.cc to the gtfiles variable in
> cp/config-lang.in.  It also looks like the GTFILES_H rule in gcc/Makefile.in
> assumes that all sources have the .c extension, so that may need adjustment.
>
>> @@ -2454,6 +2454,8 @@ finish_call_expr (tree fn, vec<tree, va_gc> **args,
>> bool d
>>               next = OVL_CHAIN (fn);
>> +              if (flag_concepts)
>> +                remove_constraints (OVL_FUNCTION (fn));
>
>
> I don't think we want to remove constraints here; this code is just
> discarding the OVERLOAD node, not the FUNCTION_DECL.
>
> Jason
>

Re: [c++-concepts] code review

[Andrew Sutton]

Today is the first day I've had to look at these comments.


>>    if (TEMPLATE_PARM_CONSTRAINTS (current_template_parms))
>> -    TYPE_CANONICAL (type) = type;
>> +    SET_TYPE_STRUCTURAL_EQUALITY (type);
>
>
> This seems like papering over an underlying issue.  What was the testcase
> that motivated this change?


It almost certainly is, but I haven't been able to find or write a
minimal test case that reproduces the reason for failure. Basically,
we end up with multiple specializations having the same type but
different constraints (since constraints are attached to the
declaration and not the type itself).

I think that I'm running into the same problems with auto a
placeholder in recent commits.


>> @@ -11854,7 +11854,7 @@ tsubst_decl (tree t, tree args, tsubst_flags_t
>> complain)
>> -           if (!spec)
>> +           if (!spec && DECL_LANG_SPECIFIC (t))
>> -       if (!local_p)
>> +       if (!local_p && DECL_LANG_SPECIFIC (r))
>
>
> What motivated these changes?  From the testcase, it seems that you're
> getting here with the decl for "using TD = int", which shouldn't happen.


That's the pretty much it... I suppose we could guard against
substituting into these kinds of declarations from within
tsubst_type_requirement and satisfy_type_constraint. To me it seems
like tsubst should work, but just return the same thing.


>> @@ -1159,7 +1159,6 @@ check_noexcept_r (tree *tp, int * /*walk_subtrees*/,
>> void * /*data*/)
>> -      tree type = TREE_TYPE (TREE_TYPE (fn));
>> -      if (!TYPE_NOTHROW_P (type))
>> +      if (!TYPE_NOTHROW_P (TREE_TYPE (fn)))
>
>
> The old code was incorrectly assuming that CALL_EXPR_FN is always a function
> pointer, but your new code seems to be incorrectly assuming that it's always
> a function or an expression taking the address of a function; I think this
> will break on a call to a function pointer variable.


I will experiment.


>> @@ -3481,13 +3481,27 @@ cxx_eval_constant_expression (const constexpr_ctx
>> *ctx, tree t,
>>      case REQUIRES_EXPR:
>> +      if (!processing_template_decl)
>> +        return evaluate_constraint_expression (t, NULL_TREE);
>> +      else
>> +        *non_constant_p = true;
>> +        return t;
>
>
> We shouldn't get here with a dependent REQUIRES_EXPR (or any dependent
> expression), so we shouldn't ever hit the else clause.


IIRC we get here because of build_x_binary_op. It tries to build
non-dependent operands when the operands are not type-dependent.
requires-expressions have type bool, so they get run through the
constexpr evaluator even when processing_template_decl is true.

I've made requires-expressions instantiation dependent, but that
doesn't help in this case.


>> +static inline bool
>> +pending_expansion_p (tree t)
>> +{
>> +  return (TREE_CODE (t) == PARM_DECL && CONSTRAINT_VAR_P (t)
>> +          && PACK_EXPANSION_P (TREE_TYPE (t)));
>> +}
>
>
> What's the difference between this and function_parameter_pack_p?


Not a lot, except that replacing pending_expansion_p in one of the two
places that it's used causes ICEs :)  This function can almost
certainly be removed.


>> +check_implicit_conversion_constraint (tree t, tree args,
>> +                                      tsubst_flags_t complain, tree
>> in_decl)
>> +{
>> +  tree expr = ICONV_CONSTR_EXPR (t);
>> +
>> +  /* Don't tsubst as if we're processing a template. If we try
>> +     to we can end up generating template-like expressions
>> +     (e.g., modop-exprs) that aren't properly typed. */
>> +  int saved_template_decl = processing_template_decl;
>> +  processing_template_decl = 0;
>
>
> Why are we checking constraints when processing_template_decl is true?


IIRC I allow constraints to be evaluated in any context because it
lets us catch these kinds of errors:

template<typename T>
void f()
{
  vector<int&> v; // error: constraints not satisfied
}


>> +  ++processing_template_decl;
>> +  tree constr = transform_expression (lift_function_definition (fn,
>> args));
>> +  --processing_template_decl;
>
>
> Why do you need to set processing_template_decl here and in other calls to
> transform_expression?  I don't notice anything that would be helped,
> especially now that you're using separate tree codes for constraints, though
> there is this in check_logical_expr:
>
>> +  /* Resolve the logical operator. Note that template processing is
>> +     disabled so we get the actual call or target expression back.
>> +     not_processing_template_sentinel sentinel.
>
>
> I guess that isn't needed anymore?


I've had problems in the past where substitution tries a little too
eagerly to fold expressions into constants --- especially type traits.
Those need to be preserved in the text for ordering.

Although I think this really only matters when you're instantiating a
class template whose members are constraints.


Andrew

Re: [c++-concepts] code review

[Jason Merrill]

On 06/21/2013 08:46 AM, Andrew Sutton wrote:
> I can move those patches over to git and push the changes in separate
> branches in addition to the usual submission mechanism. Would that be
> appropriate? Can I create a bunch of different git branches for small
> feature sets?

Sure, that sounds fine.

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

I think I will continue to work from SVN branches, because I'm a lot
more familiar with that process. I'm also going to start working on a
couple of different checkouts of the c++-concepts branch
independently, so this should be a little easier for me.

I can move those patches over to git and push the changes in separate
branches in addition to the usual submission mechanism. Would that be
appropriate? Can I create a bunch of different git branches for small
feature sets?

Andrew

On Thu, Jun 20, 2013 at 1:33 PM, Jason Merrill <jason@redhat.com> wrote:
> On 06/20/2013 01:23 PM, Jason Merrill wrote:
>>
>> Since Gaby prefers SVN, let's keep using the SVN branch; it really isn't
>> much less convenient than a git-only branch.  The main difference is
>> 'git svn rebase'/'git svn dcommit' instead of 'git pull'/'git push'.
>
>
> The one caveat is that git-svn historically hasn't handled merges very well.
> I think git-svn v1.8.3 or newer can do the right thing, but I haven't tested
> it, so it's probably best to keep doing merges with the svn client for the
> time being.
>
> Jason
>



-- 
Andrew Sutton
andrew.n.sutton@gmail.com

Re: [c++-concepts] code review

[Jason Merrill]

On 06/20/2013 01:23 PM, Jason Merrill wrote:
> Since Gaby prefers SVN, let's keep using the SVN branch; it really isn't
> much less convenient than a git-only branch.  The main difference is
> 'git svn rebase'/'git svn dcommit' instead of 'git pull'/'git push'.

The one caveat is that git-svn historically hasn't handled merges very 
well.  I think git-svn v1.8.3 or newer can do the right thing, but I 
haven't tested it, so it's probably best to keep doing merges with the 
svn client for the time being.

Jason

Re: [c++-concepts] code review

[Jason Merrill]

On 06/20/2013 11:50 AM, Andrew Sutton wrote:
>> The c++-concepts SVN branch won't come in with a clone; you need to add it
>> to the fetch list with
>>
>> git config --add remote.origin.fetch
>> refs/remotes/c++-concepts:refs/remotes/origin/c++-concepts
>>
>> Then you can check out a local branch based on it.
>
> Already did that. I probably need to do this, right?
>
>    git checkout -b c++-concepts origin/c++-concepts

Right.

> I just setup using a git-only branch, so the latter. I set up to push
> changes to asutton/c++-concepts, so submitted should be visible there.

Since Gaby prefers SVN, let's keep using the SVN branch; it really isn't 
much less convenient than a git-only branch.  The main difference is 
'git svn rebase'/'git svn dcommit' instead of 'git pull'/'git push'.

> Out of curiosity, how will reviews work? Just walk through the most
> recently pushed changes on my branch?

That's what I was thinking, yes.

> I should be able to produce diffs to send to Gaby also. I should also
> be able to use those to patch an SVN checkout and commit from a
> different repo.

git-svn is much more convenient :)

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

> The c++-concepts SVN branch won't come in with a clone; you need to add it
> to the fetch list with
>
> git config --add remote.origin.fetch
> refs/remotes/c++-concepts:refs/remotes/origin/c++-concepts
>
> Then you can check out a local branch based on it.

Already did that. I probably need to do this, right?

  git checkout -b c++-concepts origin/c++-concepts



>> How will this change the workflow? What's the process for submitting
>> changes using git?
>
>
> That depends whether you want to keep it as an SVN branch or switch to a
> git-only branch.  Both processes are documented in the wiki page:
>
> http://gcc.gnu.org/wiki/GitMirror#Commit_upstream_.28git-svn.29
> http://gcc.gnu.org/wiki/GitMirror#Git-only_branches
>
> If it's unclear, please let me know so I can update the page.

I just setup using a git-only branch, so the latter. I set up to push
changes to asutton/c++-concepts, so submitted should be visible there.

Out of curiosity, how will reviews work? Just walk through the most
recently pushed changes on my branch?

I should be able to produce diffs to send to Gaby also. I should also
be able to use those to patch an SVN checkout and commit from a
different repo.

Andrew

Re: [c++-concepts] code review

[Gabriel Dos Reis]

Jason Merrill <jason@redhat.com> writes:

| On 06/20/2013 11:22 AM, Gabriel Dos Reis wrote:
| > Jason Merrill <jason@redhat.com> writes:
| >
| > | On 06/20/2013 10:17 AM, Andrew Sutton wrote:
| > | > It looks like I should be able to switch directly to the c++-concepts
| > | > branch. Or is there some configuration that has to happen on the
| > | > remote site?
| > |
| > | The c++-concepts SVN branch won't come in with a clone; you need to
| > | add it to the fetch list with
| > |
| > | git config --add remote.origin.fetch
| > | refs/remotes/c++-concepts:refs/remotes/origin/c++-concepts
| > |
| > | Then you can check out a local branch based on it.
| >
| > Does that mean I also need to switch to git in order to continue
| > maintaining the branch?  I would rather stay with SVN for now.
| 
| No, the above is just how you check out the SVN branch under git.

Great!  Thanks for the clarification.

-- Gaby

Re: [c++-concepts] code review

[Jason Merrill]

On 06/20/2013 11:22 AM, Gabriel Dos Reis wrote:
> Jason Merrill <jason@redhat.com> writes:
>
> | On 06/20/2013 10:17 AM, Andrew Sutton wrote:
> | > It looks like I should be able to switch directly to the c++-concepts
> | > branch. Or is there some configuration that has to happen on the
> | > remote site?
> |
> | The c++-concepts SVN branch won't come in with a clone; you need to
> | add it to the fetch list with
> |
> | git config --add remote.origin.fetch
> | refs/remotes/c++-concepts:refs/remotes/origin/c++-concepts
> |
> | Then you can check out a local branch based on it.
>
> Does that mean I also need to switch to git in order to continue
> maintaining the branch?  I would rather stay with SVN for now.

No, the above is just how you check out the SVN branch under git.

> I prefer an SVN branch for now.

OK.

Jason

Re: [c++-concepts] code review

[Gabriel Dos Reis]

Jason Merrill <jason@redhat.com> writes:

| On 06/20/2013 10:17 AM, Andrew Sutton wrote:
| > It looks like I should be able to switch directly to the c++-concepts
| > branch. Or is there some configuration that has to happen on the
| > remote site?
| 
| The c++-concepts SVN branch won't come in with a clone; you need to
| add it to the fetch list with
| 
| git config --add remote.origin.fetch
| refs/remotes/c++-concepts:refs/remotes/origin/c++-concepts
| 
| Then you can check out a local branch based on it.

Does that mean I also need to switch to git in order to continue
maintaining the branch?  I would rather stay with SVN for now.

| > How will this change the workflow? What's the process for submitting
| > changes using git?
| 
| That depends whether you want to keep it as an SVN branch or switch to
| a git-only branch.  Both processes are documented in the wiki page:

I prefer an SVN branch for now.
| 
| http://gcc.gnu.org/wiki/GitMirror#Commit_upstream_.28git-svn.29
| http://gcc.gnu.org/wiki/GitMirror#Git-only_branches
| 
| If it's unclear, please let me know so I can update the page.
| 
| Jason

-- Gaby

Re: [c++-concepts] code review

[Gabriel Dos Reis]

Andrew Sutton <andrew.n.sutton@gmail.com> writes:

| That works. I think the current patch addresses all of Jason's comments.

OK, that sounds good.

| I'll also create a github version of this branch, so can avoid email patches.

Well, actually I prefer the email patches because I can read them them
right away when I have only email connections (yes, I am one those
dinausors who still read emails with emacs remotely from a terminal.)
I wish I had the luxury of organizing everything around browsers, but I don't.

-- Gaby

Re: [c++-concepts] code review

[Jason Merrill]

On 06/20/2013 10:17 AM, Andrew Sutton wrote:
> It looks like I should be able to switch directly to the c++-concepts
> branch. Or is there some configuration that has to happen on the
> remote site?

The c++-concepts SVN branch won't come in with a clone; you need to add 
it to the fetch list with

git config --add remote.origin.fetch 
refs/remotes/c++-concepts:refs/remotes/origin/c++-concepts

Then you can check out a local branch based on it.

> How will this change the workflow? What's the process for submitting
> changes using git?

That depends whether you want to keep it as an SVN branch or switch to a 
git-only branch.  Both processes are documented in the wiki page:

http://gcc.gnu.org/wiki/GitMirror#Commit_upstream_.28git-svn.29
http://gcc.gnu.org/wiki/GitMirror#Git-only_branches

If it's unclear, please let me know so I can update the page.

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

I didn't know it existed! Even better. Except that I'm not a git
expert. I'm reading through the docs on that site while I clone the
repo.

It looks like I should be able to switch directly to the c++-concepts
branch. Or is there some configuration that has to happen on the
remote site?

How will this change the workflow? What's the process for submitting
changes using git?

Andrew

On Thu, Jun 20, 2013 at 8:57 AM, Jason Merrill <jason@redhat.com> wrote:
> On 06/20/2013 09:18 AM, Andrew Sutton wrote:
>>
>> I'll also create a github version of this branch, so can avoid email
>> patches.
>
>
> Why there rather than in the gcc.gnu.org git repository?
>
> http://gcc.gnu.org/wiki/GitMirror
>
> Jason
>



-- 
Andrew Sutton
andrew.n.sutton@gmail.com

Re: [c++-concepts] code review

[Jason Merrill]

On 06/20/2013 09:18 AM, Andrew Sutton wrote:
> I'll also create a github version of this branch, so can avoid email patches.

Why there rather than in the gcc.gnu.org git repository?

http://gcc.gnu.org/wiki/GitMirror

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

That works. I think the current patch addresses all of Jason's comments.

I'll also create a github version of this branch, so can avoid email patches.

On Thu, Jun 20, 2013 at 8:09 AM, Gabriel Dos Reis <gdr@axiomatics.org> wrote:
> Jason Merrill <jason@redhat.com> writes:
>
> | On 06/20/2013 01:30 AM, Gabriel Dos Reis wrote:
> | > As I discussed
> | > with Andrew a couple of weeks ago, I have been holding back the
> | > merge from trunk because he has these patch series in the queue.
> |
> | Incidentally, since the code is going onto a branch, we don't really
> | need to delay checkins based on code review; I'd actually rather
> | review the code from within git than from an email patch.
>
> Makes sense.  Andrew, you can check in what you have now, and refine
> based on all other comments.  I won't have network connection until
> tonight; at that point I will do the merge from trunk.  We don't want to
> have the branch too old compared to the trunk.
>
> -- Gaby



-- 
Andrew Sutton
andrew.n.sutton@gmail.com

Re: [c++-concepts] code review

[Gabriel Dos Reis]

Jason Merrill <jason@redhat.com> writes:

| On 06/20/2013 01:30 AM, Gabriel Dos Reis wrote:
| > As I discussed
| > with Andrew a couple of weeks ago, I have been holding back the
| > merge from trunk because he has these patch series in the queue.
| 
| Incidentally, since the code is going onto a branch, we don't really
| need to delay checkins based on code review; I'd actually rather
| review the code from within git than from an email patch.

Makes sense.  Andrew, you can check in what you have now, and refine
based on all other comments.  I won't have network connection until
tonight; at that point I will do the merge from trunk.  We don't want to
have the branch too old compared to the trunk.

-- Gaby

Re: [c++-concepts] code review

[Jason Merrill]

On 06/20/2013 01:30 AM, Gabriel Dos Reis wrote:
> As I discussed
> with Andrew a couple of weeks ago, I have been holding back the
> merge from trunk because he has these patch series in the queue.

Incidentally, since the code is going onto a branch, we don't really 
need to delay checkins based on code review; I'd actually rather review 
the code from within git than from an email patch.

Jason

Re: [c++-concepts] code review

[Gabriel Dos Reis]

On Wed, Jun 19, 2013 at 9:21 AM, Jason Merrill <jason@redhat.com> wrote:
> On 06/18/2013 12:27 PM, Andrew Sutton wrote:
>>
>> There was a bug in instantiation_dependent_expr_r that would cause
>> trait expressions like __is_class(int) to be marked as type dependent.
>> It was always testing the 2nd operand, even for unary traits
>> (NULL_TREE turns out to be type dependent).
>
>
> I fixed that last month:
>
> 2013-05-20  Jason Merrill  <jason@redhat.com>
>
>         PR c++/57016
>         * pt.c (instantiation_dependent_r) [TRAIT_EXPR]: Only check
>         type2 if there is one.

The last merge to c++-concepts was a little bit before
that (2013-06-16), so the fix wasn't on the branch.  As I discussed
with Andrew a couple of weeks ago, I have been holding back the
merge from trunk because he has these patch series in the queue.
That also means we don't get these sort of fixes before a while.

Maybe I should just go ahead with the merge so that we have
conflicts, and potentially less duplication of work in terms of fixing
the compiler.

-- Gaby

Re: [c++-concepts] code review

[Andrew Sutton]

>> +        // If the types of the underlying templates match, compare
>> +        // their constraints. The declarations could differ there.
>> +        if (types_match)
>> +          types_match = equivalent_constraints (get_constraints
>> (olddecl),
>> +                                                current_template_reqs);
>
>
> We can't assume that current_template_reqs will always apply to newdecl
> here, as decls_match is called in overload resolution as well.  What's the
> problem with attaching the requirements to the declaration before we get to
> duplicate_decls?

It's because newdecl doesn't have a template_info at the point at
which this is called, and the constraints are associated through that
information. This seems like another good reason for keeping
constraints with template decls.

Until I change that, I can just test to see if newdecl has template
info. If so, I'll use its constraints. If not, I'll use the current
requirements.

Andrew

Re: [c++-concepts] code review

[Jason Merrill]

On 06/18/2013 12:27 PM, Andrew Sutton wrote:
> There was a bug in instantiation_dependent_expr_r that would cause
> trait expressions like __is_class(int) to be marked as type dependent.
> It was always testing the 2nd operand, even for unary traits
> (NULL_TREE turns out to be type dependent).

I fixed that last month:

2013-05-20  Jason Merrill  <jason@redhat.com>

         PR c++/57016
         * pt.c (instantiation_dependent_r) [TRAIT_EXPR]: Only check
         type2 if there is one.

If you want to keep the is_binary_trait stuff, that's fine, except that

> +extern bool is_binary_trait                     (cp_trait_kind);
...
> +inline bool
> +is_binary_trait (cp_trait_kind k)

violates the rules for inline functions: an inline function must be 
declared as inline before any uses and defined in all translation units 
that use it.

> +// reduced terms in the constraints language. Note that conjoining with a
> +// non-null expression with  NULL_TREE is an identity operation. That is,

Drop the first "with".

> +        // If the types of the underlying templates match, compare
> +        // their constraints. The declarations could differ there.
> +        if (types_match)
> +          types_match = equivalent_constraints (get_constraints (olddecl),
> +                                                current_template_reqs);

We can't assume that current_template_reqs will always apply to newdecl 
here, as decls_match is called in overload resolution as well.  What's 
the problem with attaching the requirements to the declaration before we 
get to duplicate_decls?

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

[-- Attachment #1: Type: text/plain, Size: 8747 bytes --]

I've finished revising based on comments. All of the changes seemed
pretty smooth, except for the use of fold_non_dependent_expr.

There was a bug in instantiation_dependent_expr_r that would cause
trait expressions like __is_class(int) to be marked as type dependent.
It was always testing the 2nd operand, even for unary traits
(NULL_TREE turns out to be type dependent). I added is_unary_trait,
is_binary_trait to help test around those conditions.

I ended up removing <cstdlib>.

Updated Changelog.

2013-06-18  Andrew Sutton  <andrew.n.sutton@gmail.com>
        * gcc/cp/class.c (are_constrained_member_overloads): New.
        (add_method): Allow overloading of constrained member functions.
        * gcc/cp/call.c (rejection_reason_code): New rr_constraint_failure.
        (template_constraint_failure): New.
        (add_function_candidate): Check for viability as a precondition to use.
        (add_template_candidate_real): Integrate constraint diagnostics.
        Provide constraint info for new template instantiations.
        (print_z_candidate): Emit diagnostics for constraint failures.
        (template_decl_for_candidate): New.
        (joust): Allow non-member templates of class templates to be evaluated
        in more_specialized_fn if they are constrained.
        * gcc/cp/ptree.c (cxx_print_xnode): Dump constraint info.
        * gcc/cp/semantics.c (finish_template_template_parm): Build template
        info for template template parameters.
        (is_unary_trait): New.
        (is_binary_trait): New.
        (finish_trait_expr): Check for binary traits using new function.
        * gcc/cp/constraint.cc (join_requirements): New
        (conjoin_requirements): Join expressions correctly. Fixed docs.
        (disjoin_requirements): Removed.
        (is_constriant): Removed.
        (resolve_constraint_check): New. Replaces previous get_constraint
        check and related functions.
        (get_constraints): New, along with helper functions.
        (suppress_template_processing): New.
        (check_template_constraints): New, along with helper functions.
        (equivalent_constraints): New.
        (equivalently_constrained): New.
        (more_constraints): New.
        (more_constrianed): New.
        (diagnose_constraint_failure): New.
        * gcc/cp/decl.c (decls_match): Check for constraint equivalence if
        the types are the same.
        (check_concept_refinement): New.
        (are_constrained_overloads): New.
        (duplicate_decls): Handle constraints for ambigous declarations. Check
        and diagnose concept refinement.
        (check_concept_fn): Don't fail completely just because the concept
        isn't defined correctly. Allow analysis to continue as if declared
        constexpr. Concepts must return bool.
        * gcc/cp/tree.c (bind_template_template_parm): Provide empty
        constraints for bound template template parameters.
        * gcc/cp/logic.cc: Rewrite of proof state and related structures and
        decomposition logic. Removed right-decomposition logic, but retained
        right-logical rules.
        (match_terms): Renamed from entails.
        (subsumes_prop): Cleanup, added specific handlers for and/or cases.
        (subsumes_constraints): Update from interface change.
        * gcc/cp/cp-tree.h (check_constraint_info): Renamed and applied
        interface change.
        (check_template_info): Renamed and applied interface change.
        (cp_unevaluated): New
        (local_specialization_stack): New.
        (coerce_template_parms): New.
        (is_unary_trait): New.
        (is_binary_trait): New.
        (get_constraints): New.
        (check_constraints): New.
        (check_template_constraints): New.
        (subst_template_constraints): New.
        (equivalent_constraints): New.
        (equivalently_constrained): New.
        (more_constraints): New.
        (more_constrained): New.
        (diagnose_constraints_failure): New.
        * gcc/cp/cxx-pretty-print.c (pp_cxx_template_declaration): Print the
        template requirements.
        * gcc/cp/pt.c (local_specialization_stack): New.
        (build_template_info): Refactor into 3-argument version and
        incorporate template requirements.
        (check_explicit_specialization): Instantiate requirements for
        template info.
        (push_template_decl_real): Include constraints in template info.
        (redeclare_class_template): Diagnose redeclaration with different
        constraints.
        (is_compatible_template_arg): New.
        (convert_template_argument): Check constraints on template template
        arguments and diagnose errors.
        (lookup_template_class_1): Check constraints on alias templates.
        Keep constraints with instantiated types.
        (instantiate_class_template_1): Check constraints on class templates.
        (tsubst_decl): Instantiate and keep constraints with template info.
        Also, allow dependent pack arguments to produce neww parameter
        packs when instantiated.
        (coerce_template_parms): New overload.
        (tsubst_copy): Handle REAL_TYPE and BOOLEAN_TYPE.
        (tsubst_copy_and_build): PARM_DECLs can be instantiated as pack
        expansions (used with requires expression).
        (fn_type_unification): Check constraints for function templates.
        (more_specialized_fn): Determine which candidate is more constrained.
        (substitute_template_parameters): Removed.
        (tsubst_constraint): New.
        (substitute_requirements): New.
        * gcc/cp/parser.c: (cp_parser_optional) Removed along with helper
        functions, etc.
        (cp_unevaluated): New.
        (cp_parser_type_parameter): Check for requires kw explicitly, and
        save/clear template requirements before parsing the requires clause.
        (cp_parser_requires_clause): Removed.
        (cp_parser_template_declaration_after_exp): Check for requires kw
        explicitly.
        * gcc/system.h (cstdlib): Removed include.
        * gcc/c-family/c-common.h (D_CXX_CONCEPTS): New flag for disabling
        concept keywords.
        * gcc/c-family/c.opt (flag_concepts): Remove redundant declaration.
        * gcc/c-family/c-common.c (c_common_r): Concept-specific keywords
        are only enabled when concepts are enabled.

On Mon, Jun 17, 2013 at 2:20 PM, Jason Merrill <jason@redhat.com> wrote:
> On 06/17/2013 02:10 PM, Andrew Sutton wrote:
>>>
>>> You mean you don't need <algorithm> anymore in logic.cc?  I think we want
>>> the <cstdlib> include in general if we're going to support people using
>>> the
>>> C++ standard library.
>>
>>
>> I don't. Those decisions are above my pay grade, so I'm doing my best
>> not to make them.
>
>
> If you don't need the change for concepts any more, feel free to drop it.
>
>
>>> Can friend temploids be constrained?
>>
>>
>> I have not thought deeply about constrained friend declarations. What
>> would a friend temploid look like?
>
>
> I was thinking something like
>
> template <class T> struct A {
>   T t;
>  requires Addable<T>()
>   friend A operator+(const A& a1, const A& a2)
>   { return A(a1.t + a2.t); }
>
> };
>
>>> I'm not clear on the issue.  Perhaps leaving processing_template_decl
>>> alone
>>> and using fold_non_dependent_expr would accomplish what you want?
>>
>>
>> I don't think that will work. The problem comes from the instantiation
>> of traits (and some other expressions) during constraint checking.
>> When processing_template_decl is non-zero, finish_trait_expr will
>> create TRAIT_EXPR nodes, which aren't handled by the constexpr
>> evaluation engine.
>
>
> Sure, but fold_non_dependent_expr should turn the TRAIT_EXPR into a more
> useful form.
>
>
>>> Can explicit specializations have constraints, to indicate which template
>>> they are specializing?
>>
>>
>> Good question. I don't think so. I believe that it would be a
>> specialization of the most specialized function template whose
>> constraints were satisfied. So:
>
>
> Makes sense.
>
>
>>> Passing 'true' for require_all_args means no deduction will be done;
>>> rather,
>>> all arguments must either be specified or have default arguments.
>>
>>
>> I see. It seems like I should be passing false here, since I want to
>> ensure that the resulting argument list can be used to instantiate the
>> template.
>
>
> I think true is what you want, since there are no function arguments to do
> argument deduction from.  Passing true for require_all_args guarantees that
> the result can be used to instantiate the template; passing false can return
> an incomplete set of arguments that will be filled in later by
> fn_type_unification.
>
> Jason
>



-- 
Andrew Sutton
andrew.n.sutton@gmail.com

[-- Attachment #2: reqs-3.patch --]
[-- Type: application/octet-stream, Size: 77099 bytes --]

Index: cp/class.c
===================================================================
--- cp/class.c	(revision 199411)
+++ cp/class.c	(working copy)
@@ -934,6 +934,20 @@ modify_vtable_entry (tree t,
     }
 }
 
+// Returns true if NEW_FN and OLD_FN are non-template member functions
+// of a class template with with different constraints. The types of the 
+// functions are assumed to be equivalent.
+static inline bool
+are_constrained_member_overloads (tree new_fn, tree old_fn) 
+{
+  // Non-temploids cannot be constrained.
+  if (!DECL_TEMPLOID_INSTANTIATION (new_fn) 
+      && !DECL_TEMPLOID_INSTANTIATION (old_fn))
+    return false;
+  else 
+    return !equivalently_constrained (new_fn, old_fn);
+}
+
 \f
 /* Add method METHOD to class TYPE.  If USING_DECL is non-null, it is
    the USING_DECL naming METHOD.  Returns true if the method could be
@@ -1140,6 +1154,8 @@ add_method (tree type, tree method, tree
 		/* Defer to the local function.  */
 		return false;
 	    }
+          else if (are_constrained_member_overloads (fn, method))
+            continue;
 	  else
 	    {
 	      error ("%q+#D cannot be overloaded", method);
Index: cp/call.c
===================================================================
--- cp/call.c	(revision 199411)
+++ cp/call.c	(working copy)
@@ -449,7 +449,8 @@ enum rejection_reason_code {
   rr_arg_conversion,
   rr_bad_arg_conversion,
   rr_template_unification,
-  rr_invalid_copy
+  rr_invalid_copy,
+  rr_constraint_failure
 };
 
 struct conversion_info {
@@ -709,6 +710,15 @@ invalid_copy_with_fn_template_rejection
   return r;
 }
 
+static struct rejection_reason *
+template_constraint_failure (tree tmpl, tree targs)
+{
+  struct rejection_reason *r = alloc_rejection (rr_constraint_failure);
+  r->u.template_instantiation.tmpl = tmpl;
+  r->u.template_instantiation.targs = targs;
+  return r;
+}
+
 /* Dynamically allocate a conversion.  */
 
 static conversion *
@@ -1858,6 +1868,25 @@ add_function_candidate (struct z_candida
   len = vec_safe_length (args) - skip + (first_arg != NULL_TREE ? 1 : 0);
   convs = alloc_conversions (len);
 
+  // Viable functions
+  //
+  // Functions whose constraints are not satisfied are non-viable.
+  //
+  // This only happens with constrained non-template members, which
+  // we've currently disabled.
+  if (DECL_USE_TEMPLATE (fn))
+    {
+      tree cons = DECL_TEMPLATE_CONSTRAINT (fn);
+      if (!check_constraints (cons))
+        {
+          tree tmpl = DECL_TI_TEMPLATE (fn);
+          tree args = DECL_TI_ARGS (fn);
+          reason = template_constraint_failure (tmpl, args);
+          viable = false;
+          goto out;          
+        }
+    }
+
   /* 13.3.2 - Viable functions [over.match.viable]
      First, to be a viable function, a candidate function shall have enough
      parameters to agree in number with the arguments in the list.
@@ -2924,8 +2953,8 @@ add_template_candidate_real (struct z_ca
 
   if (fn == error_mark_node)
     {
-      /* Don't repeat unification later if it already resulted in errors.  */
       if (errorcount+sorrycount == errs)
+        /* Don't repeat unification later if it already resulted in errors.  */
 	reason = template_unification_rejection (tmpl, explicit_targs,
 						 targs, args_without_in_chrg,
 						 nargs_without_in_chrg,
@@ -2977,6 +3006,7 @@ add_template_candidate_real (struct z_ca
 				   first_arg, arglist, access_path,
 				   conversion_path, flags, complain);
   if (DECL_TI_TEMPLATE (fn) != tmpl)
+    {
     /* This situation can occur if a member template of a template
        class is specialized.  Then, instantiate_template might return
        an instantiation of the specialization, in which case the
@@ -2994,7 +3024,9 @@ add_template_candidate_real (struct z_ca
        for this will point at template <class T> template <> S<T>::f(int),
        so that we can find the definition.  For the purposes of
        overload resolution, however, we want the original TMPL.  */
-    cand->template_decl = build_template_info (tmpl, targs);
+      tree cons = tsubst_constraint (DECL_TEMPLATE_CONSTRAINT (fn), targs);
+      cand->template_decl = build_template_info (tmpl, targs, cons);
+    }
   else
     cand->template_decl = DECL_TEMPLATE_INFO (fn);
   cand->explicit_targs = explicit_targs;
@@ -3243,6 +3275,13 @@ print_z_candidate (location_t loc, const
 		  "  a constructor taking a single argument of its own "
 		  "class type is invalid");
 	  break;
+        case rr_constraint_failure:
+          {
+            tree tmpl = r->u.template_instantiation.tmpl;
+            tree args = r->u.template_instantiation.targs;
+            diagnose_constraint_failure (cloc, tmpl, args);
+          }
+          break;
 	case rr_none:
 	default:
 	  /* This candidate didn't have any issues or we failed to
@@ -8353,6 +8392,22 @@ add_warning (struct z_candidate *winner,
   winner->warnings = cw;
 }
 
+// Returns the template declaration associated with the candidate
+// function. For actual templates, this is directly associated
+// with the candidate. For temploids, we return the template
+// associated with the specialization.
+static inline tree
+template_decl_for_candidate (struct z_candidate *cand)
+{
+ tree r = cand->template_decl;
+  tree d = cand->fn;
+  if (!r && DECL_P (d) && DECL_USE_TEMPLATE (d))
+    r = DECL_TI_TEMPLATE (d);
+  if (r && TREE_CODE (r) == TEMPLATE_INFO)
+    r = TI_TEMPLATE (r);
+  return r;
+}
+
 /* Compare two candidates for overloading as described in
    [over.match.best].  Return values:
 
@@ -8369,6 +8424,10 @@ joust (struct z_candidate *cand1, struct
   size_t i;
   size_t len;
 
+  // Get the actual template decls associated with the candidates.
+  tree tmpl1 = template_decl_for_candidate (cand1);
+  tree tmpl2 = template_decl_for_candidate (cand2);
+
   /* Candidates that involve bad conversions are always worse than those
      that don't.  */
   if (cand1->viable > cand2->viable)
@@ -8571,16 +8630,14 @@ joust (struct z_candidate *cand1, struct
      more specialized than the template for F2 according to the partial
      ordering rules.  */
 
-  if (cand1->template_decl && cand2->template_decl)
+  if (tmpl1 && tmpl2)
     {
-      winner = more_specialized_fn
-	(TI_TEMPLATE (cand1->template_decl),
-	 TI_TEMPLATE (cand2->template_decl),
 	 /* [temp.func.order]: The presence of unused ellipsis and default
 	    arguments has no effect on the partial ordering of function
 	    templates.   add_function_candidate() will not have
 	    counted the "this" argument for constructors.  */
-	 cand1->num_convs + DECL_CONSTRUCTOR_P (cand1->fn));
+      int nparms = cand1->num_convs + DECL_CONSTRUCTOR_P (cand1->fn);
+      winner = more_specialized_fn (tmpl1, tmpl2, nparms);
       if (winner)
 	return winner;
     }
Index: cp/ptree.c
===================================================================
--- cp/ptree.c	(revision 199411)
+++ cp/ptree.c	(working copy)
@@ -223,6 +223,14 @@ cxx_print_xnode (FILE *file, tree node,
 	  fprintf (file, "pending_template");
 	}
       break;
+    case CONSTRAINT_INFO:
+      {
+        tree_constraint_info *cinfo = (tree_constraint_info *)node;
+        print_node (file, "requirements", cinfo->requirements, indent+4);
+        if (cinfo->assumptions)
+          print_node_brief (file, "assumptions", cinfo->assumptions, indent+4);
+        break;
+      }    
     case ARGUMENT_PACK_SELECT:
       print_node (file, "pack", ARGUMENT_PACK_SELECT_FROM_PACK (node),
 		  indent+4);
Index: cp/semantics.c
===================================================================
--- cp/semantics.c	(revision 199581)
+++ cp/semantics.c	(working copy)
@@ -2567,12 +2567,18 @@ finish_template_type_parm (tree aggr, tr
 tree
 finish_template_template_parm (tree aggr, tree identifier)
 {
-  tree decl = build_decl (input_location,
+  tree decl = build_lang_decl_loc (input_location,
 			  TYPE_DECL, identifier, NULL_TREE);
   tree tmpl = build_lang_decl (TEMPLATE_DECL, identifier, NULL_TREE);
   DECL_TEMPLATE_PARMS (tmpl) = current_template_parms;
   DECL_TEMPLATE_RESULT (tmpl) = decl;
   DECL_ARTIFICIAL (decl) = 1;
+
+  // Build template info and associate it with the parameter.
+  DECL_TEMPLATE_INFO (decl) = build_template_info (tmpl, 
+                                                   current_template_args (), 
+                                                   current_template_reqs);
+
   end_template_decl ();
 
   gcc_assert (DECL_TEMPLATE_PARMS (tmpl));
@@ -5517,6 +5523,22 @@ classtype_has_nothrow_assign_or_copy_p (
   return true;
 }
 
+// Returns true if K denotes a unary type trait.
+inline bool
+is_unary_trait (cp_trait_kind k)
+{
+  if (k == CPTK_IS_CONVERTIBLE_TO || k == CPTK_IS_BASE_OF)
+    return false;
+  return true;
+}
+
+// Returns true if K denotes a binary type trait.
+inline bool
+is_binary_trait (cp_trait_kind k)
+{
+  return !is_unary_trait (k);
+}
+
 /* Actually evaluates the trait.  */
 
 static bool
@@ -5678,8 +5700,7 @@ finish_trait_expr (cp_trait_kind kind, t
     }
 
   if (type1 == error_mark_node
-      || ((kind == CPTK_IS_BASE_OF || kind == CPTK_IS_CONVERTIBLE_TO)
-	  && type2 == error_mark_node))
+      || (is_binary_trait (kind) && type2 == error_mark_node))
     return error_mark_node;
 
   if (processing_template_decl)
Index: cp/constraint.cc
===================================================================
--- cp/constraint.cc	(revision 199581)
+++ cp/constraint.cc	(working copy)
@@ -18,7 +18,7 @@ You should have received a copy of the G
 along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
 
-// Components for process constraints and evaluating constraints.
+// Components for processing constraints and evaluating constraints.
 
 #include "config.h"
 #include "system.h"
@@ -47,31 +47,34 @@ along with GCC; see the file COPYING3.
 //
 // Facilities for building and manipulating template requirements. 
 //
-// TODO: Simply assinging boolean_type_node to the result type of the expression
-// seems right thing for constraints, but in the long-term we might want to be
-// more flexible (i.e., allow some form of overload resolution?).
-
+// TODO: Simply assigning boolean_type_node to the result type of the 
+// expression seems right for constraints, but in the long-term we might want
+// to be more flexible (i.e., allow some form of overload resolution?).
+
+// Create a new logical node joining the subexpressions a and b.
+static inline tree
+join_requirements (tree_code c, tree a, tree b)
+{
+  gcc_assert (a != NULL_TREE && b != NULL_TREE);
+  gcc_assert (c == TRUTH_ANDIF_EXPR || c == TRUTH_ORIF_EXPR);
+  return build_min (c, boolean_type_node, a, b);
+}
 
 // Returns the conjunction of two requirements A and B, where A and B are
-// reduced terms in the constraints languaage. Returns NULL_TREE if either A or
-// B are NULL_TREE.
+// reduced terms in the constraints language. Note that conjoining with a
+// non-null expression with  NULL_TREE is an identity operation. That is, 
+// for some non-null A,
+//
+//    conjoin_requirements(a, NULL_TREE) == a
+//
+// If both A and B are NULL_TREE, the result is also NULL_TREE.
 tree
 conjoin_requirements (tree a, tree b)
 {
-  if (a && b)
-    return build_min (TRUTH_ANDIF_EXPR, boolean_type_node, a, b);
-  else
-    return NULL_TREE;
-}
-
-// Returns the disjunction of two requirements A and B, where A and B are
-// reduced terms in the constraints languaage. Returns NULL_TREE if either A or
-// B are NULL_TREE.
-tree
-disjoin_requirements (tree a, tree b)
-{
-  if (a && b)
-    return build_min (TRUTH_ORIF_EXPR, boolean_type_node, a, b);
+  if (a)
+    return b ? join_requirements (TRUTH_ANDIF_EXPR, a, b) : a;
+  else if (b)
+    return b;
   else
     return NULL_TREE;
 }
@@ -81,9 +84,8 @@ disjoin_requirements (tree a, tree b)
 // Constraint Resolution
 //
 // This facility is used to resolve constraint checks from requirement
-// expressions. A constraint check is a call to a constraint predicate:
-// a constexpr, nullary function teplate whose result can be converted
-// to bool.
+// expressions. A constraint check is a call to a function template, declared
+// concept.
 //
 // The result of resolution is a pair (a list node) whose value is the
 // matched declaration, and whose purpose contains the coerced template
@@ -91,37 +93,10 @@ disjoin_requirements (tree a, tree b)
 
 namespace {
 
-// Returns true if the function decl F is a constraint predicate.
-// It must be a constexpr, nullary function with a boolean result
-// type.
-static bool
-is_constraint (tree f)
-{
-  gcc_assert (TREE_CODE (f) == FUNCTION_DECL);
-
-  // A constraint is nullary.
-  if (DECL_ARGUMENTS (f))
-    return false;
-
-  // A constraint is declared constexpr
-  if (!DECL_DECLARED_CONSTEXPR_P (f))
-    return false;
-
-  // Whose result must be convertible to bool.
-  if (!can_convert (TREE_TYPE (TREE_TYPE (f)), boolean_type_node, tf_none))
-    return false;
-
-  // A constraint can only be checked if it is defined.
-  if (!DECL_SAVED_TREE (f))
-    return false;
-
-  return true;
-}
-
-// Given an OVL set of constraint candidates, try to find a unique definition
-// satisfying the requirements of a constraint.
+// Given an overload set, try to find a unique definition that can be
+// instantiated by the template arguments.
 //
-// This function is not called for abitrary call expressions. In particul,
+// This function is not called for arbitrary call expressions. In particular,
 // the call expression must be written with explicit template arguments
 // and no function arguments. For example:
 //
@@ -142,50 +117,53 @@ resolve_constraint_check (tree ovl, tree
       tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl));
 
       // Remember the candidate if we can deduce a substitution.
-      if (tree subst = substitute_template_parameters (parms, args))
+      if (tree subst = coerce_template_parms (parms, args, tmpl))
         if (subst != error_mark_node)
           cands = tree_cons (subst, DECL_TEMPLATE_RESULT (tmpl), cands);
     }
 
-  // If there are multiple candidates, then we have not found
-  // a unique definition.
-  if (TREE_CHAIN (cands))
+  // If we didn't find a unique candidate, then this is
+  // not a constraint check.
+  if (!cands || TREE_CHAIN (cands))
     return NULL_TREE;
 
-  if (!is_constraint (TREE_VALUE (cands)))
+  // Constraints must be declared concepts.
+  tree decl = TREE_VALUE (cands);
+  if (!DECL_DECLARED_CONCEPT_P (decl))
     return NULL_TREE;
 
+  // Concept declarations must have a corresponding definition.
+  //
+  // TODO: This should be part of the up-front checking for 
+  // a concept declaration.
+  if (!DECL_SAVED_TREE (decl))
+    {
+      error_at (DECL_SOURCE_LOCATION (decl),
+                "concept %q#D has no definition", decl);
+      return NULL;
+    }
+
   return cands;
 }
 
-// If the call express T is a check expression, return a singleton tree
-// list whose VALUE is the checked constraint predicate, and whose
-// PURPOSE contains substitution arguments for the constraint. If the 
-// call does not denote a check, return NULL_TREE.
-//
-// Note that a call expression is a check expression if it refers to a
-// unique, nullary function template via lightweight overload resolution.
+// Determine if the the call expression CALL is a constraint check, and
+// return the concept declaration and arguments being checked. If CALL
+// does not denote a constraint check, return NULL.
 tree
-maybe_constraint_check (tree call)
+resolve_constraint_check (tree call)
 {
   gcc_assert (TREE_CODE (call) == CALL_EXPR);
 
-  // A constraint check must be a call to a function template with 
-  // arguments given explicitly.
-  tree f = CALL_EXPR_FN (call);
-  if (TREE_CODE (f) != TEMPLATE_ID_EXPR)
-    return NULL_TREE;
-
-  // Also, make sure that there are no arguments to the call expression.
-  // If there are, then we are guaranteed that this is a regular call.
-  if (call_expr_nargs (call))
-    return NULL_TREE;
-
-  // Determine which constraint is actually referred to by the
-  // call expression.
-  tree tmpl = TREE_OPERAND (f, 0);
-  tree args = TREE_OPERAND (f, 1);
-  return resolve_constraint_check (tmpl, args);
+  // A constraint check must be only be a template-id expression.
+  tree target = CALL_EXPR_FN (call);
+  if (TREE_CODE (target) != TEMPLATE_ID_EXPR)
+    return NULL_TREE;
+
+  // Get the overload set and template arguments and try to
+  // resolve the target.
+  tree ovl = TREE_OPERAND (target, 0);
+  tree args = TREE_OPERAND (target, 1);
+  return resolve_constraint_check (ovl, args);
 }
   
 } // end namespace
@@ -360,13 +338,13 @@ reduce_logical (tree t)
 
 // Reduction rules for the call expression T.
 //
-// If T is a call to a constraint instantiate it's definition and
+// If T is a call to a constraint instantiate its definition and
 // recursively reduce its returned expression.
 tree
 reduce_call (tree t)
 {
   // Is the function call actually a constraint check?
-  tree check = maybe_constraint_check (t);
+  tree check = resolve_constraint_check (t);
   if (!check)
     return t;
 
@@ -406,8 +384,8 @@ reduce_template_id (tree t)
 {
   vec<tree, va_gc>* args = NULL;
   tree c = finish_call_expr (t, &args, true, false, 0);
-  error ("invalid requirement");
-  inform (input_location, "did you mean %qE", c);
+  error_at (EXPR_LOC_OR_HERE (t), "invalid requirement");
+  inform (EXPR_LOC_OR_HERE (t), "did you mean %qE", c);
   return NULL_TREE;
 }
 
@@ -441,7 +419,7 @@ reduce_stmt_list (tree stmts)
 } // end namespace
 
 
-// Reduce the requirement T into a logical formula written in terms of
+// Reduce the requirement REQS into a logical formula written in terms of
 // atomic propositions.
 tree
 reduce_requirements (tree reqs)
@@ -472,3 +450,155 @@ make_constraints (tree reqs)
     
   return (tree)cinfo;
 }
+
+namespace {
+
+inline tree
+get_type_constraints (tree t)
+{
+  // Template template arguments may not have template info.
+  if (!TYPE_TEMPLATE_INFO (t))
+    return NULL_TREE;
+  return TYPE_TEMPLATE_CONSTRAINT (t);
+}
+
+inline tree
+get_decl_constraints (tree t)
+{
+  if (TREE_CODE (t) == TEMPLATE_DECL)
+    {
+      tree d = DECL_TEMPLATE_RESULT (t);
+      if (TREE_CODE (d) == TYPE_DECL)
+        return get_type_constraints (TREE_TYPE (t));
+      else
+        return get_decl_constraints (d);
+    }
+  return DECL_TEMPLATE_CONSTRAINT (t);
+}
+
+} // end namespace
+
+// Return constraint info for the node T, regardless of the
+// kind of node.
+tree
+get_constraints (tree t)
+{
+  if (TYPE_P (t))
+    return get_type_constraints (t);
+  else if (DECL_P (t))
+    return get_decl_constraints (t);
+  else
+    gcc_unreachable ();
+  return false;
+}
+
+// Returns true if the requirements expression REQS is satisfied, 
+// and false otherwise. The requirements are checked by simply 
+// evaluating REQS as a constant expression.
+static inline bool
+check_requirements (tree reqs)
+{
+  // Simplify the expression before evaluating it. This will
+  // cause TRAIT_EXPR nodes to be reduced before constexpr
+  // evaluation.
+  reqs = fold_non_dependent_expr (reqs);
+  
+  // Requirements are satisfied when REQS evaluates to true.
+  return cxx_constant_value (reqs) == boolean_true_node;
+}
+
+// Check the instantiated declaration constraints.
+bool
+check_constraints (tree cinfo)
+{
+  if (!cinfo)
+    return true;
+  return check_requirements (CI_REQUIREMENTS (cinfo));
+}
+
+// Check the constraints in CINFO against the given ARGS, returning
+// true when the constraints are satisfied and false otherwise.
+bool 
+check_constraints (tree cinfo, tree args)
+{
+  // No constraints? Satisfied.
+  if (!cinfo)
+    return true;
+
+  // Instantiate the requirements before checking.
+  tree reqs = instantiate_requirements (CI_REQUIREMENTS (cinfo), args);
+  if (reqs == error_mark_node)
+    return false;
+  return check_requirements (reqs);
+}
+
+static inline bool
+check_type_constraints (tree t, tree args)
+{
+  return check_constraints (CLASSTYPE_TEMPLATE_CONSTRAINT (t), args);
+}
+
+static inline bool
+check_decl_constraints (tree t, tree args)
+{
+  if (TREE_CODE (t) == TEMPLATE_DECL)
+    return check_decl_constraints (DECL_TEMPLATE_RESULT (t), args);
+  else
+    return check_constraints (DECL_TEMPLATE_CONSTRAINT (t), args);
+}
+
+// Check the constraints of the declaration or type T, against 
+// the specified arguments. Returns true if the constraints are 
+// satisfied and false otherwise.
+bool
+check_template_constraints (tree t, tree args)
+{
+  return check_constraints (get_constraints (t), args);
+}
+
+// Returns true when A and B are equivlent constraints.
+bool
+equivalent_constraints (tree a, tree b)
+{
+  return subsumes (a, b) && subsumes (b, a);
+}
+
+// Returns true if the template declarations A and B have equivalent
+// constraints. This is the case when A's constraints subsume B's and
+// when B's also constrain A's.
+bool 
+equivalently_constrained (tree a, tree b)
+{
+  gcc_assert (TREE_CODE (a) == TREE_CODE (b));
+  return equivalent_constraints (get_constraints (a), get_constraints (b));
+}
+
+// Returns true when the A contains more atomic properties than B.
+bool
+more_constraints (tree a, tree b)
+{
+  return subsumes (a, b);
+}
+
+// Returns true when the template declaration A's constraints subsume
+// those of the template declaration B.
+bool 
+more_constrained (tree a, tree b)
+{
+  gcc_assert (TREE_CODE (a) == TREE_CODE (b));
+  return more_constraints (get_constraints (a), get_constraints (b));
+}
+
+
+// -------------------------------------------------------------------------- //
+// Constraint Diagnostics
+
+// Emit diagnostics detailing the failure ARGS to satisfy the constraints
+// of the template declaration, TMPL.
+//
+// TODO: Implement actual diagnostics.
+void
+diagnose_constraint_failure (location_t loc, tree tmpl, tree args)
+{
+  inform (loc, "  constraints not satisfied:");
+}
Index: cp/decl.c
===================================================================
--- cp/decl.c	(revision 199581)
+++ cp/decl.c	(working copy)
@@ -1077,6 +1077,12 @@ decls_match (tree newdecl, tree olddecl)
       else
 	types_match = decls_match (DECL_TEMPLATE_RESULT (olddecl),
 				   DECL_TEMPLATE_RESULT (newdecl));
+
+        // If the types of the underlying templates match, compare
+        // their constraints. The declarations could differ there.
+        if (types_match)
+          types_match = equivalent_constraints (get_constraints (olddecl), 
+                                                current_template_reqs);
     }
   else
     {
@@ -1104,6 +1110,7 @@ decls_match (tree newdecl, tree olddecl)
 				 COMPARE_REDECLARATION);
     }
 
+
   return types_match;
 }
 
@@ -1215,6 +1222,39 @@ validate_constexpr_redeclaration (tree o
   return false;
 }
 
+// If OLDDECL and NEWDECL are concept declarations with the same type
+// (i.e., and template parameters), but different requirements,
+// emit diagnostics and return true. Otherwise, return false.
+static inline bool
+check_concept_refinement (tree olddecl, tree newdecl) 
+{
+  if (!DECL_DECLARED_CONCEPT_P (olddecl) || !DECL_DECLARED_CONCEPT_P (newdecl))
+    return false;
+
+  // TODO: This isn't currently possible, but it will almost certainly
+  // change with variable templates.
+  tree d1 = DECL_TEMPLATE_RESULT (olddecl);
+  tree d2 = DECL_TEMPLATE_RESULT (newdecl);
+  if (TREE_CODE (d1) != TREE_CODE (d2))
+    return false;
+
+  tree t1 = TREE_TYPE (d1);
+  tree t2 = TREE_TYPE (d2);
+  if (TREE_CODE (d1) == FUNCTION_DECL)
+    {
+      if (compparms (TYPE_ARG_TYPES (t1), TYPE_ARG_TYPES (t2))
+          && comp_template_parms (DECL_TEMPLATE_PARMS (olddecl),
+                                  DECL_TEMPLATE_PARMS (newdecl))
+          && !equivalently_constrained (olddecl, newdecl))
+        {
+          error ("cannot specialize concept %q#D", olddecl);
+          return true;
+        }
+    }
+  return false;
+}
+
+
 #define GNU_INLINE_P(fn) (DECL_DECLARED_INLINE_P (fn)			\
 			  && lookup_attribute ("gnu_inline",		\
 					       DECL_ATTRIBUTES (fn)))
@@ -1512,11 +1552,19 @@ duplicate_decls (tree newdecl, tree oldd
 		   /* Template functions can be disambiguated by
 		      return type.  */
 		   && same_type_p (TREE_TYPE (TREE_TYPE (newdecl)),
-				   TREE_TYPE (TREE_TYPE (olddecl))))
+				   TREE_TYPE (TREE_TYPE (olddecl)))
+                   // Template functions can also be disambiguated by
+                   // constraints.
+                   && equivalent_constraints (get_constraints (olddecl), 
+                                              current_template_reqs))
 	    {
 	      error ("new declaration %q#D", newdecl);
 	      error ("ambiguates old declaration %q+#D", olddecl);
 	    }
+          else if (check_concept_refinement (olddecl, newdecl))
+            {
+              return error_mark_node;
+            }
 	  return NULL_TREE;
 	}
       if (TREE_CODE (newdecl) == FUNCTION_DECL)
@@ -7316,24 +7364,16 @@ check_static_quals (tree decl, cp_cv_qua
 }
 
 // Check that FN takes no arguments and returns bool.
-static bool
+static void
 check_concept_fn (tree fn)
 {
   // A constraint is nullary.
   if (DECL_ARGUMENTS (fn))
-    {
-      error ("concept %q#D declared with function arguments", fn);
-      return false;
-    }
+    error ("concept %q#D declared with function parameters", fn);
 
   // The result type must be convertible to bool.
-  if (!can_convert (TREE_TYPE (TREE_TYPE (fn)), boolean_type_node, tf_none))
-    {
-      error ("concept %q#D result must be convertible to bool", fn);
-      return false;
-    }
-
-  return true;
+  if (!same_type_p (TREE_TYPE (TREE_TYPE (fn)), boolean_type_node))
+    error ("concept %q#D result must be bool", fn);
 }
 
 /* CTYPE is class type, or null if non-class.
@@ -7467,7 +7507,7 @@ grokfndecl (tree ctype,
 	      fns = TREE_OPERAND (fns, 1);
 	    }
 	  gcc_assert (identifier_p (fns) || TREE_CODE (fns) == OVERLOAD);
-	  DECL_TEMPLATE_INFO (decl) = build_template_info (fns, args);
+	  DECL_TEMPLATE_INFO (decl) = build_template_info (fns, args, NULL_TREE);
 
 	  for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t))
 	    if (TREE_PURPOSE (t)
@@ -7593,8 +7633,7 @@ grokfndecl (tree ctype,
   if (inlinep & 4)
     {
       DECL_DECLARED_CONCEPT_P (decl) = true;
-      if (!check_concept_fn (decl))
-        return NULL_TREE;
+      check_concept_fn (decl);
     }
 
   DECL_EXTERNAL (decl) = 1;
@@ -14394,6 +14433,7 @@ cp_tree_node_structure (union lang_tree_
     case TRAIT_EXPR:		return TS_CP_TRAIT_EXPR;
     case LAMBDA_EXPR:		return TS_CP_LAMBDA_EXPR;
     case TEMPLATE_INFO:		return TS_CP_TEMPLATE_INFO;
+    case CONSTRAINT_INFO:       return TS_CP_CONSTRAINT_INFO;
     case USERDEF_LITERAL:	return TS_CP_USERDEF_LITERAL;
     default:			return TS_CP_GENERIC;
     }
Index: cp/tree.c
===================================================================
--- cp/tree.c	(revision 199411)
+++ cp/tree.c	(working copy)
@@ -2026,7 +2026,8 @@ bind_template_template_parm (tree t, tre
   TEMPLATE_TYPE_PARM_INDEX (t2) = copy_node (TEMPLATE_TYPE_PARM_INDEX (t));
   TEMPLATE_PARM_DECL (TEMPLATE_TYPE_PARM_INDEX (t2)) = decl;
   TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t2)
-    = build_template_info (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t), newargs);
+    = build_template_info (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t), 
+                           newargs, NULL_TREE);
 
   TREE_TYPE (decl) = t2;
   TYPE_NAME (t2) = decl;
Index: cp/logic.cc
===================================================================
--- cp/logic.cc	(revision 199581)
+++ cp/logic.cc	(working copy)
@@ -42,7 +42,6 @@ along with GCC; see the file COPYING3.
 #include "gimple.h"
 #include "bitmap.h"
 
-#include <algorithm>
 #include <list>
   
 namespace {
@@ -74,45 +73,81 @@ struct term_list : std::list<tree>
   term_list (const term_list &x);
   term_list& operator= (const term_list &x);
 
-  iterator cur;
+  tree       current_term ()       { return *current; }
+  const_tree current_term () const { return *current; }
+
+
+  void insert (tree t);
+  tree erase ();
+
+  void start ();
+  void next ();
+  bool done() const;
+
+  iterator current;
 };
 
 inline
 term_list::term_list ()
-  : std::list<tree> (), cur (end ())
+  : std::list<tree> (), current (end ())
 { }
 
 inline
 term_list::term_list (const term_list &x)
-  : std::list<tree> (x), cur (::next_by_distance (begin (), x.begin (), x.cur))
+  : std::list<tree> (x)
+  , current (next_by_distance (begin (), x.begin (), x.current))
 { }
 
 inline term_list&
 term_list::operator= (const term_list &x)
 {
   std::list<tree>::operator=(x);
-  cur = next_by_distance (begin (), x.begin (), x.cur);
+  current = next_by_distance (begin (), x.begin (), x.current);
   return *this;
 }
 
-// Insert the term t into the list at the current position, making
+// Insert the term T into the list before the current position, making
 // this term current.
 inline void
-insert_term (term_list& l, tree t)
+term_list::insert (tree t)
 {
-  l.cur = l.insert (l.cur, t);
+  current = std::list<tree>::insert (current, t);
 }
 
-// Remove the current term form the list, repositioning the current
-// position at the next term in the list.
+// Remove the current term form the list, repositioning to the term
+// following the removed term. Note that the new position could be past 
+// the end of the list.
+//
+// The removed term is returned.
 inline tree
-remove_term (term_list& l)
+term_list::erase ()
 {
-  tree t = *l.cur;
-  l.cur = l.erase (l.cur);
+  tree t = *current;
+  current = std::list<tree>::erase (current);
   return t;
 }
 
+// Initialize the current term to the first in the list.
+inline void
+term_list::start ()
+{
+  current = begin ();
+}
+
+// Advance to the next term in the list.
+inline void
+term_list::next ()
+{
+  ++current;
+}
+
+// Returns true when the current position is past the end.
+inline bool
+term_list::done () const
+{
+  return current == end ();
+}
+
 
 // -------------------------------------------------------------------------- //
 // Proof Goal
@@ -122,24 +157,10 @@ remove_term (term_list& l)
 // constraint language (i.e., lists of trees).
 struct proof_goal
 {
-  term_list as; // Assumptions
-  term_list cs; // Conclusions   
+  term_list assumptions;
+  term_list conclusions;
 };
 
-// Return the list of assumed terms for the goal g.
-inline term_list &
-assumptions (proof_goal &g) { return g.as; }
-
-inline const term_list &
-assumptions (const proof_goal &g) { return g.as; }
-
-// Return the list of concluded terms for the goal g.
-inline term_list &
-conclusions (proof_goal &g) { return g.cs; }
-
-inline const term_list &
-conclusions (const proof_goal &g) { return g.cs; }
-
 
 // -------------------------------------------------------------------------- //
 // Proof State
@@ -151,145 +172,26 @@ struct proof_state : std::list<proof_goa
 {
   proof_state ();
 
-  iterator cur;
+  iterator branch (iterator i);
 };
 
-// Initialize the state with a single empty goal, and set
-// that goal as the current subgoal.
+// An alias for proof state iterators.
+typedef proof_state::iterator goal_iterator;
+
+// Initialize the state with a single empty goal, and set that goal as the
+// current subgoal.
 inline
 proof_state::proof_state ()
-  : std::list<proof_goal> (1), cur (begin ())
+  : std::list<proof_goal> (1)
 { }
 
 
-// Return the current goal. Provided for notational symmetry
-inline proof_goal &
-current_goal (proof_state &s) { return *s.cur; }
-
-inline const proof_goal &
-current_goal (const proof_state &s) { return *s.cur; }
-
-// Return the current list of assumed terms.
-inline term_list &
-assumptions (proof_state &s) { return assumptions (current_goal (s)); }
-
-inline const term_list &
-assumptions (const proof_state &s) { return assumptions (current_goal (s)); }
-
-// Return the current list of concluded terms.
-inline term_list &
-conclusions (proof_state &s) { return conclusions (current_goal (s)); }
-
-inline const term_list &
-conclusions (const proof_state &s) { return conclusions (current_goal (s)); }
-
-// Return the current assumption.
-inline tree
-assumption (const proof_state &s) { return *assumptions (s).cur; }
-
-// Return the current conclision.
-inline tree
-conclusion (const proof_state &s) { return *conclusions (s).cur; }
-
-// Move to the next goal.
-inline void
-next_goal (proof_state &s) { ++s.cur; }
-
-// Move to the next assumption.
-inline void
-next_assumption (proof_state &s) { ++assumptions (s).cur; }
-
-// Move to the next conclusion.
-inline void
-next_conclusion (proof_state &s) { ++conclusions (s).cur; }
-
-
-// -------------------------------------------------------------------------- //
-// Term List Manipulation
-//
-// The following functions are used to manage the insertation and removal
-// goals and terms in the proof state.
-
-// Assume the term e in the current goal. The current assumption is set to the
-// new term.
-inline void
-assume_term (proof_goal &g, tree e) { insert_term (assumptions (g), e); }
-
-inline void 
-assume_term (proof_state &s, tree e) { assume_term (current_goal (s), e); }
-
-// Forget the current assumption, removing it from the context of the current
-// goal. Returns the forgotten assumption.
-inline tree
-forget_term (proof_goal &g) { return remove_term (assumptions (g)); }
-
-inline tree
-forget_term (proof_state &s) { return forget_term (current_goal (s)); }
-
-// Conclude the term e in the current goal. The current conclusion is set to 
-// the new term.
-inline void
-conclude_term (proof_goal &g, tree e) { insert_term (conclusions (g), e); }
-
-inline void
-conclude_term (proof_state &s, tree e) { conclude_term (current_goal (s), e); }
-
-// Ignore the current conclusion, removing it from the conclusions
-// of the current goal. Returns the ignored conclusion.
-inline tree
-ignore_term (proof_goal &g) { return remove_term (conclusions (g)); }
-
-inline tree
-ignore_term (proof_state &s) { return ignore_term (current_goal (s)); }
-
 // Branch the current goal by creating a new subgoal, returning a reference to
-// the new objet. This does not update the current goal.
-inline proof_goal &
-branch_goal (proof_state &s)
-{
-  proof_state::iterator p = s.cur;
-  p = s.insert (++p, *s.cur);
-  return *p;
-}
-
-
-// -------------------------------------------------------------------------- //
-// Debugging
-//
-// Helper functions for debugging the proof state.
-
-void
-debug (term_list &l)
+// the new object. This does not update the current goal.
+inline proof_state::iterator
+proof_state::branch (iterator i)
 {
-  term_list::iterator i = l.begin ();
-  term_list::iterator last = --l.end ();
-  term_list::iterator end = l.end ();
-  for ( ; i != end; ++i)
-    {
-      debug (*i);
-      if (i != last)
-        fprintf (stderr, " ");
-    }
-}
-
-void
-debug (proof_goal &g)
-{
-  debug (g.as);
-  fprintf (stderr, " |- ");
-  debug (g.cs);
-}
-
-void
-debug (proof_state& s)
-{
-  proof_state::iterator i = s.begin ();
-  proof_state::iterator end = s.end ();
-  for ( ; i != end; ++i)
-    {
-      debug (*i);
-      fprintf (stderr, "\n");
-    }
+  return insert (++i, *i);
 }
 
 
@@ -299,63 +201,82 @@ debug (proof_state& s)
 // These functions modify the current state and goal by decomposing
 // logical expressions using the logical rules of sequent calculus for
 // first order logic.
+//
+// Note that in each decomposition rule, the term T has been erased
+// from term list before the specific rule is applied.
 
-
-// And left logical rule.
+// Left-and logical rule.
+//
+//  Gamma, P, Q |- Delta
+//  -------------------------
+//  Gamma, P and Q |- Delta
 inline void 
-and_left (proof_state &s)
+left_and (proof_state &, goal_iterator i, tree t)
 {
-  gcc_assert (TREE_CODE (assumption (s)) == TRUTH_ANDIF_EXPR);
-  tree t = forget_term (s);
-  assume_term (s, TREE_OPERAND (t, 1));
-  assume_term (s, TREE_OPERAND (t, 0));
-}
+  gcc_assert (TREE_CODE (t) == TRUTH_ANDIF_EXPR);
 
-// And right logical rule.
-inline void
-and_right (proof_state &s)
-{
-  gcc_assert (TREE_CODE (conclusion (s)) == TRUTH_ANDIF_EXPR);
-  tree t = ignore_term (s);
-  conclude_term (branch_goal (s), TREE_OPERAND (t, 1));
-  conclude_term (current_goal (s), TREE_OPERAND (t, 0));
+  // Insert the operands into the current branch. Note that the
+  // final order of insertion is left-to-right.
+  term_list &l = i->assumptions;
+  l.insert (TREE_OPERAND (t, 1));
+  l.insert (TREE_OPERAND (t, 0));
 }
 
-// Or left logical rule.
+// Left-or logical rule.
+//
+//  Gamma, P |- Delta    Gamma, Q |- Delta
+//  -----------------------------------------
+//  Gamma, P or Q |- Delta
 inline void
-or_left (proof_state& s)
+left_or (proof_state &s, goal_iterator i, tree t)
 {
-  gcc_assert (TREE_CODE (assumption (s)) == TRUTH_ORIF_EXPR);
-  tree t = forget_term (s);
-  assume_term (branch_goal (s), TREE_OPERAND (t, 1));
-  assume_term (current_goal (s), TREE_OPERAND (t, 0));
+  gcc_assert (TREE_CODE (t) == TRUTH_ORIF_EXPR);
+
+  // Branch the current subgoal.
+  goal_iterator j = s.branch (i);
+  term_list &l1 = i->assumptions;
+  term_list &l2 = j->assumptions;
+
+  // Insert operands into the different branches.
+  l1.insert (TREE_OPERAND (t, 0));
+  l2.insert (TREE_OPERAND (t, 1));
 }
 
-// Or right logical rule.
+// Right-and logical rule.
+//
+//  Gamma |- P, Delta    Gamma |- Q, Delta
+//  -----------------------------------------
+//  Gamma |- P and Q, Delta
 inline void
-or_right (proof_state &s)
+right_and (proof_state &s, goal_iterator i, tree t)
 {
-  gcc_assert (TREE_CODE (conclusion (s)) == TRUTH_ORIF_EXPR);
-  tree t = ignore_term (s);
-  conclude_term (s, TREE_OPERAND (t, 1));
-  conclude_term (s, TREE_OPERAND (t, 0));
-}
+  gcc_assert (TREE_CODE (t) == TRUTH_ORIF_EXPR);
 
+  // Branch the current subgoal.
+  goal_iterator j = s.branch (i);
+  term_list &l1 = i->conclusions;
+  term_list &l2 = j->conclusions;
 
-// -------------------------------------------------------------------------- //
-// Algorithms
+  // Insert operands into the different branches.
+  l1.insert (TREE_OPERAND (t, 0));
+  l2.insert (TREE_OPERAND (t, 1));
+}
+
+// Right-or logical rule.
 //
-// Generic algorithms for querying or manipulating a proof state.
+//  Gamma |- P, Q, Delta
+//  ------------------------
+//  Gamma |- P or Q, Delta
+inline void
+right_or (proof_state &, goal_iterator i, tree t)
+{
+  gcc_assert (TREE_CODE (t) == TRUTH_ANDIF_EXPR);
 
-// Apply fn for each goal and returns fn. The current goal is set prior to
-// calling fn.
-template<typename F>
-  inline F
-  for_each_goal (proof_state &s, F fn)
-  {
-    for (s.cur = s.begin (); s.cur != s.end (); ++s.cur)
-      fn (s);
-    return fn;
+  // Insert the operands into the current branch. Note that the
+  // final order of insertion is left-to-right.
+  term_list &l = i->conclusions;
+  l.insert (TREE_OPERAND (t, 1));
+  l.insert (TREE_OPERAND (t, 0));
   }
 
 
@@ -375,60 +296,40 @@ template<typename F>
 // subgoal that can be further decomposed.
 
 void
-decompose_left_term (proof_state &s)
-{
-  tree e = assumption (s);
-  if (TREE_CODE (e) == TRUTH_ANDIF_EXPR)
-    and_left (s);
-  else if (TREE_CODE (e) == TRUTH_ORIF_EXPR)
-    or_left (s);
-  else
-    next_assumption (s);
-}
-
-void 
-decompose_left_goal (proof_state &s)
+decompose_left_term (proof_state &s, goal_iterator i)
 {
-  term_list& l = assumptions (s);
-  for (l.cur = l.begin (); l.cur != l.end (); )
-    decompose_left_term (s);
-}
-
-inline void
-decompose_left (proof_state& s)
+  term_list &l = i->assumptions;
+  tree t = l.current_term ();
+  switch (TREE_CODE (t))
 {
-  for_each_goal (s, decompose_left_goal);
+    case TRUTH_ANDIF_EXPR:
+      left_and (s, i, l.erase ());
+      break;
+    case TRUTH_ORIF_EXPR:
+      left_or (s, i, l.erase ());
+      break;
+    default:
+      l.next ();
+      break;
 }
-
-// Right decomposition.
-// Continually decompose conclusions until there are no terms in any
-// subgoal that can be further decomposed.
-
-void
-decompose_right_term (proof_state &s)
-{
-  tree e = conclusion (s);
-  if (TREE_CODE (e) == TRUTH_ANDIF_EXPR)
-    and_right (s);
-  else if (TREE_CODE (e) == TRUTH_ORIF_EXPR)
-    or_right (s);
-  else
-    next_conclusion (s);
 }
 
 void
-decompose_right_goal (proof_state &s)
+decompose_left_goal (proof_state &s, goal_iterator i)
 {
-  term_list& l = conclusions (s);
-  for (l.cur = l.begin (); l.cur != l.end (); )
-    decompose_right_term (s);
+  term_list& l = i->assumptions;
+  l.start ();
+  while (!l.done ())
+    decompose_left_term (s, i);
 }
 
-
 inline void
-decompose_right (proof_state& s)
+decompose_left (proof_state& s)
 {
-  for_each_goal (s, decompose_right_goal);
+  goal_iterator iter = s.begin ();
+  goal_iterator end = s.end ();
+  for ( ; iter != end; ++iter)
+    decompose_left_goal (s, iter);
 }
 
 
@@ -436,32 +337,17 @@ decompose_right (proof_state& s)
 // Term Extraction
 //
 // Extract a list of term lists from a proof state, and return it as a
-// a tree (a vetor of vectors).
+// a tree (a vector of vectors).
 
 // Returns a vector of terms from the given term list.
 tree
 extract_terms (term_list& l)
 {
   tree result = make_tree_vec (l.size());
-  term_list::iterator i = l.begin();
-  term_list::iterator e = l.end();
-  for (int n = 0; i != e; ++i, ++n)
-    TREE_VEC_ELT (result, n) = *i;
-  return result;
-}
-
-// Extract a vector of term vectors from s. The selected set of terms is given
-// by the projection function proj. This is generally either assumptions or
-// conclusions.
-template<typename F>
-  tree
-  extract_goals (proof_state& s, F proj)
-  {
-    tree result = make_tree_vec (s.size ());
-    proof_state::iterator i = s.begin ();
-    proof_state::iterator e = s.end ();
-    for (int n = 0; i != e; ++i, ++n)
-      TREE_VEC_ELT (result, n) = extract_terms (proj (*i));
+  term_list::iterator iter = l.begin();
+  term_list::iterator end = l.end();
+  for (int n = 0; iter != end; ++iter, ++n)
+    TREE_VEC_ELT (result, n) = *iter;
     return result;
   }
 
@@ -469,43 +355,33 @@ template<typename F>
 inline tree
 extract_assumptions (proof_state& s)
 {
-  term_list& (*proj)(proof_goal&) = assumptions;
-  return extract_goals (s, proj);
-}
-
-// Extract the conclusion vector from the proof state s.
-inline tree
-extract_conclusions (proof_state& s)
-{
-  term_list& (*proj)(proof_goal&) = conclusions;
-  return extract_goals (s, proj);
+  tree result = make_tree_vec (s.size ());
+  goal_iterator iter = s.begin ();
+  goal_iterator end = s.end ();
+  for (int n = 0; iter != end; ++iter, ++n)
+    TREE_VEC_ELT (result, n) = extract_terms (iter->assumptions);
+  return result;
 }
 
 } // namespace
 
 
-// Decompose the requirement R into a set of assumptions, returing a
-// vector of vectors containing atomic propositions.
+// Decompose the required expression T into a constraint set: a
+// vector of vectors containing only atomic propositions.
 tree
-decompose_assumptions (tree r)
+decompose_assumptions (tree t)
 {
+  // Create a proof state, and insert T as the sole assumption.
   proof_state s;
-  assume_term (s, r);
+  term_list &l = s.begin ()->assumptions;
+  l.insert (t);
+  
+  // Decompose the expression into a constraint set, and then
+  // extract the terms for the AST.
   decompose_left (s);
   return extract_assumptions (s);
 }
 
-// Decompose the requirement R into a set of conclusionss, returning a
-// vector of vectors containing atomic propositions.
-tree
-decompose_conclusions (tree r)
-{
-  proof_state s;
-  conclude_term (s, r);
-  decompose_right (s);
-  return extract_conclusions (s);
-}
-
 
 // -------------------------------------------------------------------------- //
 // Subsumption and Entailment
@@ -515,11 +391,20 @@ decompose_conclusions (tree r)
 
 namespace {
 
-// Returns true if the assumed proposition A entails the conclusion C.
-// In general, this is the case when A has equivalent spelling to C,
-// although there will be some special cases.
+bool subsumes_prop(tree, tree);
+bool subsumes_atom(tree, tree);
+bool subsumes_and(tree, tree);
+bool subsumes_or(tree, tree);
+
+// Returns true if the assumption A matches the conclusion C. This
+// is generally the case when A and C have the same syntax.
+//
+// TODO: Implement special cases for:
+//    * __is_same_as |- __is_convertible_to
+//    * __is_same_as |- __is_derived_from
+//    * Any other built-in predicates?
 bool
-entails_atom (tree a, tree c)
+match_terms (tree a, tree c)
 {
   // TODO: Add special cases for __is_same, __is_convertible, 
   // and __is_base_of.
@@ -528,16 +413,33 @@ entails_atom (tree a, tree c)
 
 // Returns true if the list of assumptions AS subsume the atomic 
 // proposition C. This is the case when we can find a proposition in
-// HS that entails the conclusion C.
+// AS that entails the conclusion C.
 bool
 subsumes_atom (tree as, tree c)
 {
   for (int i = 0; i < TREE_VEC_LENGTH (as); ++i)
-    if (entails_atom (TREE_VEC_ELT (as, i), c))
+    if (match_terms (TREE_VEC_ELT (as, i), c))
       return true;
   return false;
 }
 
+// Returns true when both operands of C are subsumed by the assumptions AS.
+inline bool 
+subsumes_and (tree as, tree c)
+{
+  tree l = TREE_OPERAND (c, 0);
+  tree r = TREE_OPERAND (c, 1);
+  return subsumes_prop (as, l) && subsumes_prop (as, r);
+}
+
+// Returns true when either operand of C is subsumed by the assumptions AS.
+inline bool
+subsumes_or (tree as, tree c)
+{
+  tree l = TREE_OPERAND (c, 0);
+  tree r = TREE_OPERAND (c, 1);
+  return subsumes_prop (as, l) || subsumes_prop (as, r);
+}
 
 // Returns true when the list of assumptions AS subsumes the 
 // concluded proposition C.
@@ -550,11 +452,9 @@ subsumes_prop (tree as, tree c)
   switch (TREE_CODE (c))
     {
     case TRUTH_ANDIF_EXPR:
-      return subsumes_prop (as, TREE_OPERAND (c, 0)) 
-          && subsumes_prop (as, TREE_OPERAND (c, 1));
+      return subsumes_and (as, c);
     case TRUTH_ORIF_EXPR:
-      return subsumes_prop (as, TREE_OPERAND (c, 0)) 
-          || subsumes_prop (as, TREE_OPERAND (c, 1));
+      return subsumes_or (as, c);
     default:
       return subsumes_atom (as, c);
     }
@@ -566,11 +466,11 @@ subsumes_prop (tree as, tree c)
 bool
 subsumes_constraints (tree left, tree right)
 {
-  gcc_assert (constraint_info_p (left));
-  gcc_assert (constraint_info_p (right));
+  gcc_assert (check_constraint_info (left));
+  gcc_assert (check_constraint_info (right));
 
-  // Check that c is subsumed by each subproblem in h.
-  // If it is not, then h does not subsume c.
+  // Check that the required expression in RIGHT is subsumed by each
+  // subgoal in the assumptions of LEFT.
   tree as = CI_ASSUMPTIONS (left);
   tree c = reduce_requirements (CI_REQUIREMENTS (right));
   for (int i = 0; i < TREE_VEC_LENGTH (as); ++i)
@@ -583,7 +483,7 @@ subsumes_constraints (tree left, tree ri
 
 
 // Returns true the LEFT constraints subsume the RIGHT constraints. Note
-// that subsumption is a reflexive relation.
+// that subsumption is a reflexive relation (e.g., <=)
 bool
 subsumes (tree left, tree right)
 {
@@ -596,3 +496,4 @@ subsumes (tree left, tree right)
   return subsumes_constraints (left, right);
 }
 
+
Index: cp/cp-tree.h
===================================================================
--- cp/cp-tree.h	(revision 199581)
+++ cp/cp-tree.h	(working copy)
@@ -800,7 +800,7 @@ struct GTY(()) tree_constraint_info {
 
 // Returns true iff T is non-null and represents constraint info.
 inline tree_constraint_info *
-constraint_info_p (tree t)
+check_constraint_info (tree t)
 {
   if (t && TREE_CODE (t) == CONSTRAINT_INFO)
     return (tree_constraint_info *)t;
@@ -809,7 +809,7 @@ constraint_info_p (tree t)
 
 // Returns true iff T is non-null and is a template info object.
 inline tree_template_info *
-template_info_p (tree t)
+check_template_info (tree t)
 {
   if (t && TREE_CODE (t) == TEMPLATE_INFO)
     return (tree_template_info *)t;
@@ -818,34 +818,34 @@ template_info_p (tree t)
 
 // Get the spelling of the requirements
 #define CI_SPELLING(NODE) \
-  check_nonnull (constraint_info_p (NODE))->spelling
+  check_nonnull (check_constraint_info (NODE))->spelling
 
 // Get the reduced requirements associated with the constraint info node
 #define CI_REQUIREMENTS(NODE) \
-  check_nonnull (constraint_info_p (NODE))->requirements
+  check_nonnull (check_constraint_info (NODE))->requirements
 
 // Get the set of assumptions associated with the constraint info node
 #define CI_ASSUMPTIONS(NODE) \
-  check_nonnull (constraint_info_p (NODE))->assumptions
+  check_nonnull (check_constraint_info (NODE))->assumptions
 
 // Get the constraint associated with the template info NODE.
 #define TI_CONSTRAINT(NODE) \
-  check_nonnull (template_info_p (NODE))->constraint
+  check_nonnull (check_template_info (NODE))->constraint
 
 // Get the spelling of constraints associated
 #define TI_SPELLING(NODE) \
-  check_nonnull (constraint_info_p (TI_CONSTRAINT (NODE)))->spelling
+  check_nonnull (check_constraint_info (TI_CONSTRAINT (NODE)))->spelling
 
 // Get requirements associated with the template info NODE.
 #define TI_REQUIREMENTS(NODE) \
-  check_nonnull (constraint_info_p (TI_CONSTRAINT (NODE)))->requirements
+  check_nonnull (check_constraint_info (TI_CONSTRAINT (NODE)))->requirements
 
 // Get assumptions associated with the template info NODE.
 #define TI_ASSUMPTIONS(NODE) \
-  check_nonnull (constraint_info_p (TI_CONSTRAINT (NODE)))->assumptions
+  check_nonnull (check_constraint_info (TI_CONSTRAINT (NODE)))->assumptions
 
 // Access constraint information for C++ declarations. Note that
-// NODE must be a lang-decl.
+// NODE must have DECL_LANG_SPECIFIC.
 #define DECL_TEMPLATE_CONSTRAINT(NODE) \
   TI_CONSTRAINT (DECL_TEMPLATE_INFO (NODE))
 
@@ -4409,6 +4409,15 @@ extern int cp_unevaluated_operand;
 extern tree cp_convert_range_for (tree, tree, tree);
 extern bool parsing_nsdmi (void);
 
+// An RAII class used to inhibit the evaluation of operands during parsing
+// and template instantiation. Evaluation warnings are also inhibited.
+class cp_unevaluated
+{
+public:
+  cp_unevaluated ();
+  ~cp_unevaluated ();
+};
+
 /* in pt.c  */
 
 /* These values are used for the `STRICT' parameter to type_unification and
@@ -4421,6 +4430,18 @@ typedef enum unification_kind_t {
   DEDUCE_EXACT
 } unification_kind_t;
 
+// An RAII class used to create a new pointer map for local
+// specializations. When the stack goes out of scope, the
+// previous pointer map is restored.
+class local_specialization_stack
+{
+public:
+  local_specialization_stack ();
+  ~local_specialization_stack ();
+
+  struct pointer_map_t *saved;
+};
+
 /* in class.c */
 
 extern int current_class_depth;
@@ -5652,8 +5673,7 @@ extern tree get_template_argument_pack_e
 extern tree get_function_template_decl		(const_tree);
 extern tree resolve_nondeduced_context		(tree);
 extern hashval_t iterative_hash_template_arg (tree arg, hashval_t val);
-extern tree substitute_template_parameters      (tree, tree);
-extern tree substitute_requirements             (tree, tree);
+extern tree coerce_template_parms               (tree, tree, tree);
 extern tree instantiate_requirements            (tree, tree);
 extern tree tsubst_constraint                   (tree, tree);
 extern tree current_template_args               ();
@@ -5807,6 +5827,8 @@ extern bool is_sub_constant_expr (tree);
 extern bool reduced_constant_expression_p (tree);
 extern void explain_invalid_constexpr_fn (tree);
 extern vec<tree> cx_error_context (void);
+extern bool is_unary_trait                      (cp_trait_kind);
+extern bool is_binary_trait                     (cp_trait_kind);
 
 enum {
   BCS_NO_SCOPE = 1,
@@ -6250,6 +6272,16 @@ extern tree conjoin_requirements
 extern tree disjoin_requirements                (tree, tree);
 extern tree reduce_requirements                 (tree);
 extern tree make_constraints                    (tree);
+extern tree get_constraints                     (tree);
+extern bool check_constraints                   (tree);
+extern bool check_constraints                   (tree, tree);
+extern bool check_template_constraints          (tree, tree);
+extern tree subst_template_constraints          (tree, tree);
+extern bool equivalent_constraints              (tree, tree);
+extern bool equivalently_constrained            (tree, tree);
+extern bool more_constraints                    (tree, tree);
+extern bool more_constrained                    (tree, tree);
+extern void diagnose_constraint_failure         (location_t, tree, tree);
 
 /* in logic.cc */
 extern tree decompose_assumptions               (tree);
Index: cp/cxx-pretty-print.c
===================================================================
--- cp/cxx-pretty-print.c	(revision 199411)
+++ cp/cxx-pretty-print.c	(working copy)
@@ -2182,6 +2182,14 @@ pp_cxx_template_declaration (cxx_pretty_
       pp_cxx_end_template_argument_list (pp);
       pp_newline_and_indent (pp, 3);
     }
+
+  if (tree c = get_constraints (t))
+    {
+      pp_cxx_ws_string (pp, "requires");
+      pp_cxx_expression (pp, CI_REQUIREMENTS (c));
+      pp_newline_and_indent (pp, 6);
+    }
+
   if (TREE_CODE (t) == FUNCTION_DECL && DECL_SAVED_TREE (t))
     pp_cxx_function_definition (pp, t);
   else
Index: cp/pt.c
===================================================================
--- cp/pt.c	(revision 199581)
+++ cp/pt.c	(working copy)
@@ -77,6 +77,23 @@ static tree cur_stmt_expr;
    local variables.  */
 static struct pointer_map_t *local_specializations;
 
+// -------------------------------------------------------------------------- //
+// Local Specialization Stack
+//
+// Implementation of the RAII helper for creating new local
+// specializations.
+local_specialization_stack::local_specialization_stack ()
+  : saved (local_specializations)
+{
+  local_specializations = pointer_map_create ();
+}
+
+local_specialization_stack::~local_specialization_stack ()
+{
+  pointer_map_destroy (local_specializations);
+  local_specializations = saved;
+}
+
 /* True if we've recursed into fn_type_unification too many times.  */
 static bool excessive_deduction_depth;
 
@@ -301,9 +318,16 @@ finish_member_template_decl (tree decl)
 tree
 build_template_info (tree template_decl, tree template_args)
 {
+  return build_template_info (template_decl, template_args, NULL_TREE);
+}
+
+tree
+build_template_info (tree template_decl, tree template_args, tree template_reqs)
+{
   tree result = make_node (TEMPLATE_INFO);
   TI_TEMPLATE (result) = template_decl;
   TI_ARGS (result) = template_args;
+  TI_CONSTRAINT (result) = template_reqs;
   return result;
 }
 
@@ -1952,7 +1976,15 @@ determine_specialization (tree template_
 	       specialize TMPL will produce DECL.  */
 	    continue;
 
-	  /* Make sure that the deduced arguments actually work.  */
+	  // Make sure that the deduced arguments actually work. First,
+          // check that any template constraints are satisfied.
+          //
+          // TODO: Make sure that we get reasonable diagnostics for these
+          // kinds of failures.
+          if (!check_template_constraints (fn, targs))
+            continue;
+
+          // Then, try to form the new function type.
 	  insttype = tsubst (TREE_TYPE (fn), targs, tf_none, NULL_TREE);
 	  if (insttype == error_mark_node)
 	    continue;
@@ -2683,6 +2715,8 @@ check_explicit_specialization (tree decl
 	    }
 
 	  /* Set up the DECL_TEMPLATE_INFO for DECL.  */
+          tree fn = DECL_TEMPLATE_RESULT (tmpl);
+          tree cons = tsubst_constraint (DECL_TEMPLATE_CONSTRAINT (fn), targs);
 	  DECL_TEMPLATE_INFO (decl) = build_template_info (tmpl, targs);
 
 	  /* Inherit default function arguments from the template
@@ -4878,7 +4912,7 @@ template arguments to %qD do not match o
   if (DECL_TEMPLATE_INFO (tmpl))
     args = add_outermost_template_args (DECL_TI_ARGS (tmpl), args);
 
-  info = build_template_info (tmpl, args);
+  info = build_template_info (tmpl, args, current_template_reqs);
 
   if (DECL_IMPLICIT_TYPEDEF_P (decl))
     SET_TYPE_TEMPLATE_INFO (TREE_TYPE (tmpl), info);
@@ -5029,6 +5063,17 @@ redeclare_class_template (tree type, tre
 	TREE_PURPOSE (TREE_VEC_ELT (parms, i)) = tmpl_default;
     }
 
+  // Cannot redeclare a class template with a different set of constraints. 
+  tree tmpl_type = TREE_TYPE (tmpl);
+  if (!equivalent_constraints (TYPE_TEMPLATE_CONSTRAINT (tmpl_type), cons))
+    {
+      // FIXME: This points to the wrong line.
+      error_at (input_location, "redeclaration %q#D with different "
+                                "constraints", tmpl);
+      inform (DECL_SOURCE_LOCATION (tmpl), 
+              "original declaration appeared here");
+    }
+
     return true;
 }
 
@@ -6160,6 +6205,47 @@ canonicalize_type_argument (tree arg, ts
   return arg;
 }
 
+// A template declaration can be substituted for a constrained
+// template template parameter only when the argument is more 
+// constrained than the parameter.
+static bool
+is_compatible_template_arg (tree parm, tree arg)
+{
+  // TODO: The argument may not have a decl result. This seems to
+  // happen in some classes with nested template template
+  // parameters (e.g., a rebind struct in a class taking a template
+  // template parameter. If this is the case, just return true and
+  // allow things to happen as they always did.
+  if (TREE_CODE (arg) == TEMPLATE_DECL)
+    {
+      if (!DECL_TEMPLATE_RESULT (arg))
+        return true;
+    }
+
+  // If the template parameter is constrained, we need to rewrite its
+  // constraints in terms of the ARG's template parameters. This ensures
+  // that all of the template parameter types will have the same depth.
+  //
+  // Note that this is only valid when coerce_template_template_parm is
+  // true for the innermost template parameters of PARM and ARG. In other
+  // words, because coercion is successful, conversion will be valid.
+  tree parmcons = DECL_TEMPLATE_CONSTRAINT (DECL_TEMPLATE_RESULT (parm));
+  if (parmcons)
+    {
+      tree args = template_parms_to_args (DECL_TEMPLATE_PARMS (arg));
+      ++processing_template_decl;
+      tree reqs = instantiate_requirements (CI_REQUIREMENTS (parmcons), args);
+      --processing_template_decl;
+      if (reqs == error_mark_node)
+        return false;
+      parmcons = make_constraints (reqs);
+    }
+
+  tree argtype = TREE_TYPE (arg);
+  tree argcons = get_constraints (argtype);
+  return more_constraints (argcons, parmcons);
+}
+
 /* Convert the indicated template ARG as necessary to match the
    indicated template PARM.  Returns the converted ARG, or
    error_mark_node if the conversion was unsuccessful.  Error and
@@ -6304,9 +6390,7 @@ convert_template_argument (tree parm,
 	  else
 	    {
 	      tree parmparm = DECL_INNERMOST_TEMPLATE_PARMS (parm);
-	      tree argparm;
-
-              argparm = DECL_INNERMOST_TEMPLATE_PARMS (arg);
+	      tree argparm = DECL_INNERMOST_TEMPLATE_PARMS (arg);
 
 	      if (coerce_template_template_parms (parmparm, argparm,
 						  complain, in_decl,
@@ -6337,6 +6421,22 @@ convert_template_argument (tree parm,
 
 		  val = error_mark_node;
 		}
+
+              // Check that the constraints are compatible before allowing the
+              // substitution.
+              if (val != error_mark_node)
+                if (!is_compatible_template_arg (parm, arg))
+                  {
+                      if (in_decl && (complain & tf_error))
+                      {
+                        error ("constraint mismatch at argument %d in "
+                               "template parameter list for %qD",
+                               i + 1, in_decl);
+                        inform (input_location, "  expected %qD but got %qD",
+                                parm, arg);
+                      }                      
+                      val = error_mark_node;
+                  }
 	    }
 	}
       else
@@ -6543,7 +6643,6 @@ any_pack_expanson_args_p (tree args)
   return false;
 }
 
-
 /* Convert all template arguments to their appropriate types, and
    return a vector containing the innermost resulting template
    arguments.  If any error occurs, return error_mark_node. Error and
@@ -6741,6 +6840,19 @@ coerce_template_parms (tree parms,
   return new_inner_args;
 }
 
+// Convert all template arguments to their appropriate types, and
+// return a vector containing the innermost resulting template
+// arguments.  If any error occurs, return error_mark_node. Error and
+// warning messages are not issued.
+//
+// Note that no function argument deduction is performed, and default 
+// arguments are used to fill in unspecified arguments.
+tree
+coerce_template_parms (tree parms, tree args, tree in_decl)
+{
+  return coerce_template_parms (parms, args, in_decl, tf_none, true, true);
+}
+
 /* Like coerce_template_parms.  If PARMS represents all template
    parameters levels, this function returns a vector of vectors
    representing all the resulting argument levels.  Note that in this
@@ -7371,6 +7483,10 @@ lookup_template_class_1 (tree d1, tree a
 	}
       else if (DECL_ALIAS_TEMPLATE_P (gen_tmpl))
 	{
+          // Check the alias declaration's args. 
+          if (!check_template_constraints (gen_tmpl, arglist))
+            return error_mark_node;
+
 	  /* The user referred to a specialization of an alias
 	    template represented by GEN_TMPL.
 
@@ -7534,7 +7650,10 @@ lookup_template_class_1 (tree d1, tree a
 	    : CLASSTYPE_TI_TEMPLATE (found);
 	}
 
-      SET_TYPE_TEMPLATE_INFO (t, build_template_info (found, arglist));
+      // Build the constraints for this type. 
+      tree type = TREE_TYPE (found);
+      tree cons = tsubst_constraint (TYPE_TEMPLATE_CONSTRAINT (type), arglist);
+       SET_TYPE_TEMPLATE_INFO (t, build_template_info (found, arglist, cons));
 
       elt.spec = t;
       slot = htab_find_slot_with_hash (type_specializations,
@@ -8600,6 +8719,12 @@ instantiate_class_template_1 (tree type)
     {
       pattern = TREE_TYPE (templ);
       args = CLASSTYPE_TI_ARGS (type);
+
+      // Check class template requirements. Note that constraints will 
+      // already have been checked when trying to find a most specialized 
+      // class among multiple specializations.
+      if (!check_template_constraints (pattern, args))
+        return error_mark_node;
     }
 
   /* If the template we're instantiating is incomplete, then clearly
@@ -9981,6 +10106,7 @@ tsubst_decl (tree t, tree args, tsubst_f
 	/* We can get here when processing a member function template,
 	   member class template, or template template parameter.  */
 	tree decl = DECL_TEMPLATE_RESULT (t);
+  tree type = TREE_TYPE (t);
 	tree spec;
 	tree tmpl_args;
 	tree full_args;
@@ -9988,7 +10114,7 @@ tsubst_decl (tree t, tree args, tsubst_f
 	if (DECL_TEMPLATE_TEMPLATE_PARM_P (t))
 	  {
 	    /* Template template parameter is treated here.  */
-	    tree new_type = tsubst (TREE_TYPE (t), args, complain, in_decl);
+	    tree new_type = tsubst (type, args, complain, in_decl);
 	    if (new_type == error_mark_node)
 	      RETURN (error_mark_node);
 	    /* If we get a real template back, return it.  This can happen in
@@ -10049,7 +10175,13 @@ tsubst_decl (tree t, tree args, tsubst_f
 	gcc_assert (DECL_LANG_SPECIFIC (r) != 0);
 	DECL_CHAIN (r) = NULL_TREE;
 
-	DECL_TEMPLATE_INFO (r) = build_template_info (t, args);
+        // Rebuild the constraints on the original template.
+        tree cons = get_constraints (t);
+        cons = tsubst_constraint (cons, args);
+ 
+        // Build new template info linking to the original template
+        // decl, but having these args and constraints.
+        DECL_TEMPLATE_INFO (r) = build_template_info (t, args, cons);	
 
 	if (TREE_CODE (decl) == TYPE_DECL
 	    && !TYPE_DECL_ALIAS_P (decl))
@@ -10286,8 +10418,11 @@ tsubst_decl (tree t, tree args, tsubst_f
 	   GEN_TMPL is NULL.  */
 	if (gen_tmpl)
 	  {
+            // Rebuild the template constraint.
+            tree cons = tsubst_constraint (DECL_TEMPLATE_CONSTRAINT (t), args);
+	    
 	    DECL_TEMPLATE_INFO (r)
-	      = build_template_info (gen_tmpl, argvec);
+	      = build_template_info (gen_tmpl, argvec, cons);
 	    SET_DECL_IMPLICIT_INSTANTIATION (r);
 
 	    tree new_r
@@ -10426,13 +10561,15 @@ tsubst_decl (tree t, tree args, tsubst_f
               /* We're on the Ith parameter of the function parameter
                  pack.  */
               {
-		/* An argument of a function parameter pack is not a parameter
-		   pack.  */
-		FUNCTION_PARAMETER_PACK_P (r) = false;
-
                 /* Get the Ith type.  */
                 type = TREE_VEC_ELT (expanded_types, i);
 
+                // An argument of a function parameter pack is a function
+                // parameter pack if its type is also a pack. This can
+                // happen when instantiating templates with other template
+                // parameters.
+                FUNCTION_PARAMETER_PACK_P (r) = PACK_EXPANSION_P (type);
+
 		/* Rename the parameter to include the index.  */
 		DECL_NAME (r)
 		  = make_ith_pack_parameter_name (DECL_NAME (r), i);
@@ -10512,7 +10649,7 @@ tsubst_decl (tree t, tree args, tsubst_f
 	    DECL_INITIAL (r) = void_zero_node;
 	    gcc_assert (DECL_LANG_SPECIFIC (r) == NULL);
 	    retrofit_lang_decl (r);
-	    DECL_TEMPLATE_INFO (r) = build_template_info (t, args);
+	    DECL_TEMPLATE_INFO (r) = build_template_info (t, args, NULL_TREE);
 	  }
 	/* We don't have to set DECL_CONTEXT here; it is set by
 	   finish_member_declaration.  */
@@ -10743,7 +10880,9 @@ tsubst_decl (tree t, tree args, tsubst_f
 	    DECL_EXTERNAL (r) = 1;
 
 	    register_specialization (r, gen_tmpl, argvec, false, hash);
-	    DECL_TEMPLATE_INFO (r) = build_template_info (tmpl, argvec);
+
+	    DECL_TEMPLATE_INFO (r) = 
+                build_template_info (tmpl, argvec, NULL_TREE);
 	    SET_DECL_IMPLICIT_INSTANTIATION (r);
 	  }
 	else if (cp_unevaluated_operand)
@@ -12526,6 +12665,8 @@ tsubst_copy (tree t, tree args, tsubst_f
     case UNION_TYPE:
     case ENUMERAL_TYPE:
     case INTEGER_TYPE:
+    case REAL_TYPE:
+    case BOOLEAN_TYPE:
     case TEMPLATE_TYPE_PARM:
     case TEMPLATE_TEMPLATE_PARM:
     case BOUND_TEMPLATE_TEMPLATE_PARM:
@@ -14493,6 +14634,12 @@ tsubst_copy_and_build (tree t,
 	  /* If the original type was a reference, we'll be wrapped in
 	     the appropriate INDIRECT_REF.  */
 	  r = convert_from_reference (r);
+
+        // If the type of the argument is a pack expansion, then
+        // the parameter must also be expanded.
+        if (PACK_EXPANSION_P (TREE_TYPE (r)))
+          r = make_pack_expansion (r);
+
 	RETURN (r);
       }
 
@@ -15204,6 +15351,15 @@ fn_type_unification (tree fn,
       goto fail;
     }
 
+  // All is well so far. Now, check that the template constraints
+  // are satisfied.
+  if (!check_template_constraints (fn, targs)) 
+    {
+      if (explain_p)
+        diagnose_constraint_failure (DECL_SOURCE_LOCATION (fn), fn, targs);
+      return error_mark_node;
+    }
+
   /* All is well so far.  Now, check:
 
      [temp.deduct]
@@ -17709,6 +17865,13 @@ more_specialized_fn (tree pat1, tree pat
       lose2 = TREE_CODE (TREE_VALUE (args2)) == TYPE_PACK_EXPANSION;
     }
 
+  // All things still being equal, determine if one is more constrained.
+  if (lose1 == lose2)
+    {
+      lose1 = !more_constrained (pat1, pat2);
+      lose2 = !more_constrained (pat2, pat1);
+    }
+
   if (lose1 == lose2)
     return 0;
   else if (!lose1)
@@ -17736,12 +17899,11 @@ static int
 more_specialized_class (tree main_tmpl, tree pat1, tree pat2)
 {
   tree targs;
-  tree tmpl1, tmpl2;
   int winner = 0;
   bool any_deductions = false;
 
-  tmpl1 = TREE_TYPE (pat1);
-  tmpl2 = TREE_TYPE (pat2);
+  tree tmpl1 = TREE_TYPE (pat1);
+  tree tmpl2 = TREE_TYPE (pat2);
 
   /* Just like what happens for functions, if we are ordering between
      different class template specializations, we may encounter dependent
@@ -20179,11 +20341,15 @@ instantiation_dependent_r (tree *tp, int
       }
 
     case TRAIT_EXPR:
-      if (dependent_type_p (TRAIT_EXPR_TYPE1 (*tp))
-	  || dependent_type_p (TRAIT_EXPR_TYPE2 (*tp)))
+      {
+        bool l = dependent_type_p (TRAIT_EXPR_TYPE1 (*tp));
+        bool r = is_binary_trait (TRAIT_EXPR_KIND (*tp))
+                   ? dependent_type_p (TRAIT_EXPR_TYPE1 (*tp)) : false;
+        if (l || r)
 	return *tp;
       *walk_subtrees = false;
       return NULL_TREE;
+      }
 
     case COMPONENT_REF:
       if (identifier_p (TREE_OPERAND (*tp, 1)))
@@ -21101,16 +21267,6 @@ print_template_statistics (void)
 	   htab_collisions (type_specializations));
 }
 
-
-// Try to substitute ARGS into PARMS, returning the actual list of
-// arguments that have been substituted. If ARGS cannot be substituted,
-// return error_mark_node.
-tree
-substitute_template_parameters (tree parms, tree args)
-{
-  return coerce_template_parms (parms, args, NULL_TREE, tf_none, true, true);
-}
-
 // Substitute the template arguments ARGS into the requirement
 // expression REQS. Errors resulting from substitution are not
 // diagnosed.
@@ -21120,5 +21276,17 @@ instantiate_requirements (tree reqs, tre
   return tsubst_expr (reqs, args, tf_none, NULL_TREE, true);
 }
 
+// Create a new constraint info block by substituting ARGS into
+// the requirements of CONS.
+//
+// Note that this does not require evaluation.
+tree
+tsubst_constraint (tree cons, tree args)
+{
+  if (!cons)
+    return NULL_TREE;
+  tree reqs = instantiate_requirements (CI_REQUIREMENTS (cons), args);
+  return make_constraints (reqs);
+}
 
 #include "gt-cp-pt.h"
Index: cp/parser.c
===================================================================
--- cp/parser.c	(revision 199581)
+++ cp/parser.c	(working copy)
@@ -2210,8 +2210,6 @@ static void cp_parser_label_declaration
 
 /* Concept Extensions */
 
-static tree cp_parser_requires_clause
-  (cp_parser *);
 static tree cp_parser_requires_clause_opt
   (cp_parser *);
 
@@ -2418,52 +2416,21 @@ static cp_declarator * cp_parser_make_in
  (enum tree_code, tree, cp_cv_quals, cp_declarator *, tree);
 
 
-// A helper type for declaring rule pointers.
-typedef tree (*cp_rule)(cp_parser *);
-
 
 // -------------------------------------------------------------------------- //
-// Optional Parsing
+// Unevaluated Operand Guard
 //
-// The following functions will optionally parse a rule if the corresponding
-// criteria is satisfied. If not, the parser returns NULL indicating that
-// the optional parse taken.
-//
-// Note that an optional parse returning error_mark_node means that the
-// optional parse was taken, but failed due to some error in the following
-// token stream. 
-
-// Optionally parse RULE if the next token type matches TYPE.
-template<typename Rule>
-static inline tree
-cp_parser_optional_if_token (cp_parser *parser, Rule rule, cpp_ttype type)
-{
-  if (cp_lexer_next_token_is (parser->lexer, type))
-    return rule (parser);
-  else
-    return NULL_TREE;
-}
-
-// Optionally parse RULE if the next token type does not match TYPE.
-template<typename Rule>
-static inline tree
-cp_parser_optional_if_not_token (cp_parser *parser, Rule rule, cpp_ttype type)
+// Implementation of an RAII helper for unevaluated operand parsing.
+cp_unevaluated::cp_unevaluated ()
 {
-  if (cp_lexer_next_token_is_not (parser->lexer, type))
-    return rule (parser);
-  else
-    return NULL_TREE;
+  ++cp_unevaluated_operand;
+  ++c_inhibit_evaluation_warnings;
 }
 
-// Optionally parse RULE if the next token is the keyword KW.
-template<typename Rule>
-static inline tree
-cp_parser_optional_if_keyword (cp_parser *parser, Rule rule, rid kw)
+cp_unevaluated::~cp_unevaluated ()
 {
-  if (cp_lexer_next_token_is_keyword (parser->lexer, kw))
-    return rule (parser);
-  else
-    return NULL_TREE;
+  --c_inhibit_evaluation_warnings;
+  --cp_unevaluated_operand;
 }
 
 // -------------------------------------------------------------------------- //
@@ -12816,6 +12783,7 @@ cp_parser_type_parameter (cp_parser* par
 	/* Look for the `>'.  */
 	cp_parser_require (parser, CPP_GREATER, RT_GREATER);
 	
+
         // If template requirements are present, parse them.
         if (flag_concepts)
           {
@@ -19885,11 +19853,11 @@ cp_parser_member_declaration (cp_parser*
 
               // If we're looking at a function declaration, then a requires
               // clause may follow the declaration.
-              tree saved_template_reqs = current_template_reqs;
-              if (flag_concepts 
-                  && function_declarator_p (declarator)
-                  && cp_lexer_next_token_is_keyword (parser->lexer, RID_REQUIRES))
+              tree saved_template_reqs = release (current_template_reqs);
+              if (flag_concepts && function_declarator_p (declarator))
                 {
+                  // Because this is a non-template member, there are no
+                  // template requirements to conjoin.
                   if (tree r = cp_parser_requires_clause_opt (parser))
                     current_template_reqs = finish_template_requirements (r);
                 }
@@ -21423,39 +21391,27 @@ cp_parser_label_declaration (cp_parser*
   cp_parser_require (parser, CPP_SEMICOLON, RT_SEMICOLON);
 }
 
-// Parse a requires clause:
+// Optionally parse a requires clause:
 //
 //   requires-clause:
 //     'requires' constant-expression
 //
 // The constant expression is a logical-or-expression.
 static tree
-cp_parser_requires_clause (cp_parser *parser)
+cp_parser_requires_clause_opt (cp_parser *parser)
 {
-  gcc_assert (cp_lexer_next_token_is_keyword (parser->lexer, RID_REQUIRES));
+  if (!cp_lexer_next_token_is_keyword (parser->lexer, RID_REQUIRES))
+    return NULL_TREE;
   cp_lexer_consume_token (parser->lexer);
 
   // Parse a logical-or-expression as a constant expression.
   tree expr = 
     cp_parser_binary_expression (parser, false, false, PREC_NOT_OPERATOR, NULL);
-  if (!potential_rvalue_constant_expression (expr))
-    {
-      require_potential_rvalue_constant_expression (expr);
+  if (!require_potential_rvalue_constant_expression (expr))
       return error_mark_node;
-    }
   return expr;
 }
 
-// Parse an optional template requirement, returning NULL_TREE if no
-// 'requires' clause is found. The template requirement is required to
-// be a constant expression.
-static tree
-cp_parser_requires_clause_opt (cp_parser* parser)
-{
-  cp_rule p = cp_parser_requires_clause;
-  return cp_parser_optional_if_keyword (parser, p, RID_REQUIRES);
-}
-
 /* Support Functions */
 
 /* Looks up NAME in the current scope, as given by PARSER->SCOPE.
Index: system.h
===================================================================
--- system.h	(revision 199581)
+++ system.h	(working copy)
@@ -222,10 +222,6 @@ extern int errno;
 # endif
 #endif
 
-#ifdef __cplusplus
-# include <cstdlib>
-#endif
-
 #ifdef HAVE_STDLIB_H
 # include <stdlib.h>
 #endif
Index: c-family/c-common.h
===================================================================
--- c-family/c-common.h	(revision 199581)
+++ c-family/c-common.h	(working copy)
@@ -368,6 +368,9 @@ struct c_common_resword
 #define D_OBJC		0x080	/* In Objective C and neither C nor C++.  */
 #define D_CXX_OBJC	0x100	/* In Objective C, and C++, but not C.  */
 #define D_CXXWARN	0x200	/* In C warn with -Wcxx-compat.  */
+#define D_CXX_CONCEPTS  0x400   /* In C++, only with concepts. */
+
+#define D_CXX_CONCEPTS_FLAGS D_CXXONLY | D_CXX0X | D_CXX_CONCEPTS
 
 /* The reserved keyword table.  */
 extern const struct c_common_resword c_common_reswords[];
Index: c-family/c.opt
===================================================================
--- c-family/c.opt	(revision 199411)
+++ c-family/c.opt	(working copy)
@@ -21,10 +21,6 @@
 
 ; Please try to keep this file in ASCII collating order.
 
-; Activate C++ concepts support.
-Variable
-bool flag_concepts
-
 Language
 C
 
Index: c-family/c-common.c
===================================================================
--- c-family/c-common.c	(revision 199581)
+++ c-family/c-common.c	(working copy)
@@ -555,11 +555,11 @@ const struct c_common_resword c_common_r
   { "while",		RID_WHILE,	0 },
 
   /* Concepts-related keywords */
-  { "assume",		RID_ASSUME,	D_CXXONLY | D_CXX0X | D_CXXWARN },
-  { "axiom",		RID_AXIOM,	D_CXXONLY | D_CXX0X | D_CXXWARN },
-  { "concept",		RID_CONCEPT,	D_CXXONLY | D_CXX0X | D_CXXWARN },
-  { "forall", 		RID_FORALL,	D_CXXONLY | D_CXX0X | D_CXXWARN },
-  { "requires", 	RID_REQUIRES,	D_CXXONLY | D_CXX0X | D_CXXWARN },
+  { "assume",		RID_ASSUME,	D_CXX_CONCEPTS_FLAGS | D_CXXWARN },
+  { "axiom",		RID_AXIOM,	D_CXX_CONCEPTS_FLAGS | D_CXXWARN },
+  { "concept",		RID_CONCEPT,	D_CXX_CONCEPTS_FLAGS | D_CXXWARN },
+  { "forall", 		RID_FORALL,	D_CXX_CONCEPTS_FLAGS | D_CXXWARN },
+  { "requires", 	RID_REQUIRES,	D_CXX_CONCEPTS_FLAGS | D_CXXWARN },
 
   /* These Objective-C keywords are recognized only immediately after
      an '@'.  */

Re: [c++-concepts] code review

[Gabriel Dos Reis]

On Mon, Jun 17, 2013 at 2:20 PM, Jason Merrill <jason@redhat.com> wrote:

>> I have not thought deeply about constrained friend declarations. What
>> would a friend temploid look like?
>
>
> I was thinking something like
>
> template <class T> struct A {
>   T t;
>  requires Addable<T>()
>   friend A operator+(const A& a1, const A& a2)
>   { return A(a1.t + a2.t); }
>
> };

We agreed about a month ago to have something like this
for member functions.  It makes sense that it applies to friend
too (since it already applies to static member functions.)

One caveat in the design is that the nested requirement can
only add to the outer requirements.

-- Gaby

Re: [c++-concepts] code review

[Jason Merrill]

On 06/17/2013 02:10 PM, Andrew Sutton wrote:
>> You mean you don't need <algorithm> anymore in logic.cc?  I think we want
>> the <cstdlib> include in general if we're going to support people using the
>> C++ standard library.
>
> I don't. Those decisions are above my pay grade, so I'm doing my best
> not to make them.

If you don't need the change for concepts any more, feel free to drop it.

>> Can friend temploids be constrained?
>
> I have not thought deeply about constrained friend declarations. What
> would a friend temploid look like?

I was thinking something like

template <class T> struct A {
   T t;
  requires Addable<T>()
   friend A operator+(const A& a1, const A& a2)
   { return A(a1.t + a2.t); }
};

>> I'm not clear on the issue.  Perhaps leaving processing_template_decl alone
>> and using fold_non_dependent_expr would accomplish what you want?
>
> I don't think that will work. The problem comes from the instantiation
> of traits (and some other expressions) during constraint checking.
> When processing_template_decl is non-zero, finish_trait_expr will
> create TRAIT_EXPR nodes, which aren't handled by the constexpr
> evaluation engine.

Sure, but fold_non_dependent_expr should turn the TRAIT_EXPR into a more 
useful form.

>> Can explicit specializations have constraints, to indicate which template
>> they are specializing?
>
> Good question. I don't think so. I believe that it would be a
> specialization of the most specialized function template whose
> constraints were satisfied. So:

Makes sense.

>> Passing 'true' for require_all_args means no deduction will be done; rather,
>> all arguments must either be specified or have default arguments.
>
> I see. It seems like I should be passing false here, since I want to
> ensure that the resulting argument list can be used to instantiate the
> template.

I think true is what you want, since there are no function arguments to 
do argument deduction from.  Passing true for require_all_args 
guarantees that the result can be used to instantiate the template; 
passing false can return an incomplete set of arguments that will be 
filled in later by fn_type_unification.

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

>> 2. I left the <cstdlib> include in system.h, because removing it will
>> result in errors due to an inclusion of <algorithm>. It's probable
>> that both can be removed, but I didn't test it with this patch.
>
>
> You mean you don't need <algorithm> anymore in logic.cc?  I think we want
> the <cstdlib> include in general if we're going to support people using the
> C++ standard library.

I don't. Those decisions are above my pay grade, so I'm doing my best
not to make them.



>> +          reason = template_unification_error_rejection ();
>
>
> Can't you do
>
>   template_constraint_failure (DECL_TI_TEMPLATE (fn), DECL_TI_ARGS (fn))

I can indeed. Fixed.


>>    if (fn == error_mark_node)
>>      {
>> +      if (!check_template_constraints (tmpl, targs))
>> +          reason = template_constraint_failure (tmpl, targs);
>> +      else if (errorcount+sorrycount == errs)
>>        /* Don't repeat unification later if it already resulted in errors.
>> */
>
>
> A constraint failure is a form of unification failure, like SFINAE; let's
> handle it in that context rather than separately here, and reserve
> rr_constraint_failure for the case of a non-template member function.

And emit the diagnostics in fn_type_unification when explain_p is set?
Seems reasonable.


> The uses of "actual template" in the comment and function name seem to mean
> different things.  Maybe call the function template_decl_for_candidate?

Fixed.

> Can friend temploids be constrained?

I have not thought deeply about constrained friend declarations. What
would a friend temploid look like?


> Seems like the comment is no longer accurate; the function now only returns
> NULL_TREE if both a and b are NULL_TREE.

It's not. And I removed disjoin_requirements. I don't think it will
ever be used.

>> +static tree
>> +get_constraint_check (tree call)
>
> The comment needs updating.  And the function isn't used anywhere; it seems
> redundant with resolve_constraint_check.

I removed the function.


>> +// and other template nodes from generating new expressions
>> +// during instantiation.
>
> I'm not clear on the issue.  Perhaps leaving processing_template_decl alone
> and using fold_non_dependent_expr would accomplish what you want?

I don't think that will work. The problem comes from the instantiation
of traits (and some other expressions) during constraint checking.
When processing_template_decl is non-zero, finish_trait_expr will
create TRAIT_EXPR nodes, which aren't handled by the constexpr
evaluation engine.

I could updated constexpr to fix that, or changed finish_trait_expr
(and others? noexcept maybe) to evaluate for non-dependent arguments,
but I was trying to limit the scope of my changes.

I'd really like for this structure to go away. It's very fragile.


>> +// Check the template's constraints for the specified arguments,
>> +// returning true if the constraints are satisfied and false
>> +// otherwise.
>> +bool
>> +check_template_constraints (tree t, tree args)
>> +{
>> +  return check_constraints (get_constraints (t), args);
>> +}
>
>
> Seems like the last function would also work for types and non-template
> decls.

It should. Updated the comment to reflect the broader applicability of
the function.


>> +  error_at (loc, "constraints not satisfied");
>
>
> I assume you're planning to make this more verbose?  It could use a TODO to
> that effect.

Very much so. Added comments.


>> +  else if (are_constrained_overloads (newdecl, olddecl))
>> +    {
>> +      // If newdecl and olddecl are function templates with the
>> +      // same type but different constraints, then they cannot be
>> +      // duplicate declarations. However, if the olddecl is declared
>> +      // as a concept, then the program is ill-formed.
>> +      if (DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (olddecl)))
>> +        {
>> +          error ("cannot specialize concept %q#D", olddecl);
>> +          return error_mark_node;
>> +        }
>> +      return NULL;
>> +    }
>
>
> We should check for differing constraints in decls_match, and then this code
> should be in the !types_match section of duplicate_decls.

I'll get back to you on this. I need to work my way through that code.


>
>>        error ("concept %q#D result must be convertible to bool", fn);
>
>
> Why don't we require the result to actually be bool?  It seems difficult to
> decompose dependent requirements if the return type can be something else.

I'm probably sitting somewhere between two ideas. Requiring the result
to be exactly bool is fine.


>> +              cp_lexer_next_token_is_keyword (parser->lexer,
>> RID_REQUIRES))
>>            {
>>              tree reqs = release (current_template_reqs);
>> -            if (tree r = cp_parser_requires_clause_opt (parser))
>> +            if (tree r = cp_parser_requires_clause (parser))
>
>
> I was thinking to change the name of cp_requires_clause to
> cp_parser_requires_clause_opt and change the assert to a test for the
> keyword and return NULL_TREE if it isn't found.

I see. That is cleaner.


>> +          // FIXME: we should be checking the constraints, not just
>> +          // instantiating them.
>
>
> Let's check them in determine_specialization, along with the SFINAE check
> after the comment
>          /* Make sure that the deduced arguments actually work.  */

Okay. I'm not sure where the diagnostics for those failures fit in
yet. I've left a TODO note.


> Can explicit specializations have constraints, to indicate which template
> they are specializing?

Good question. I don't think so. I believe that it would be a
specialization of the most specialized function template whose
constraints were satisfied. So:

  template<Arithmetic T> void f(T x); // #1
  template<Integral T> void f(T x); // #2

  template<> void f(double); // Specializes #1
  template<> void f(int); // Specializes #2

I haven't tested this yet, but it seems like it would follow from the
usual overload resolution rules.


>> +// Argument deduction ios applied to all template arguments, and
>
>
> Passing 'true' for require_all_args means no deduction will be done; rather,
> all arguments must either be specified or have default arguments.

I see. It seems like I should be passing false here, since I want to
ensure that the resulting argument list can be used to instantiate the
template.


>> +      // Check class template requirements. Note that constraints will
>> +      // already have been checked when trying to find a most specialized
>> +      // class among multiple specializations.
>
>
> I don't see where that is; more_specialized_class doesn't seem to compare
> constraints yet.

It doesn't. I have to rethink some aspects of how partial
specialization work. I'm also waiting until specializations get
TEMPLATE_DECs.

Checking specializations will probably happen in get_class_bindings.
That doesn't seem to get called when there are no specializations.

>> +            // FIXME: Do we need to attach constraints?
>> +            // TODO: Is this actually necessary?
>
>
> I don't think you need to fill in TI_CONSTRAINT for anything but the main
> template patterns, here or other places.

Agreed.

>> +substitute_requirements (tree reqs, tree args)
>
> This seems redundant with instantiate_requirements.

It is. I'm using it for constraint diagnosis in a separate version,
but I may not need it. I've removed the function for now.


I'll look over the decls_match code and try to get a revised patch out tomorrow.

Andrew

Re: [c++-concepts] code review

[Gabriel Dos Reis]

On Fri, Jun 14, 2013 at 8:40 PM, Jason Merrill <jason@redhat.com> wrote:

>> +//  \Gamma, P |- Delta    \Gamma, Q |- \Delta
>
>
> Are the \ for TeX markup or something?  You're missing one on the left Delta
> here.

yes, I think the backslash was for LaTeX, but we get warnings about having
backslash in comments, so I think we can safely leave them out.

-- Gaby

Re: [c++-concepts] code review

[Jason Merrill]

> 1. tree_template_info still contains constraint_info. That will change
> in a subsequent patch. I'm kind of waiting for specializations to get
> TEMPLATE_DECLs.

Makes sense.

> 2. I left the <cstdlib> include in system.h, because removing it will
> result in errors due to an inclusion of <algorithm>. It's probable
> that both can be removed, but I didn't test it with this patch.

You mean you don't need <algorithm> anymore in logic.cc?  I think we 
want the <cstdlib> include in general if we're going to support people 
using the C++ standard library.

> +  if (DECL_USE_TEMPLATE (fn))
> +    {
> +      tree cons = DECL_TEMPLATE_CONSTRAINT (fn);
> +      if (!check_constraints (cons))
> +        {
> +          // TODO: Fail for the right reason.
> +          reason = template_unification_error_rejection ();

Can't you do

   template_constraint_failure (DECL_TI_TEMPLATE (fn), DECL_TI_ARGS (fn))

?

>    if (fn == error_mark_node)
>      {
> +      if (!check_template_constraints (tmpl, targs))
> +          reason = template_constraint_failure (tmpl, targs);
> +      else if (errorcount+sorrycount == errs)
>        /* Don't repeat unification later if it already resulted in errors.  */

A constraint failure is a form of unification failure, like SFINAE; 
let's handle it in that context rather than separately here, and reserve 
rr_constraint_failure for the case of a non-template member function.

> +// Returns the template declaration associated with the candidate
> +// function. For actual templates, this is directly associated
> +// with the candidate. For temploids, we return the template
> +// associated with the specialization.
> +static inline tree
> +get_actual_template (struct z_candidate *cand)

The uses of "actual template" in the comment and function name seem to 
mean different things.  Maybe call the function template_decl_for_candidate?

> +  // Non-temploids cannot be constrained.

Can friend temploids be constrained?

> +  if (!DECL_TEMPLOID_INSTANTIATION (new_fn) &&
> +      !DECL_TEMPLOID_INSTANTIATION (old_fn))

The && goes at the beginning of the second line.

> +// reduced terms in the constraints language. Returns NULL_TREE if either A or
>  // B are NULL_TREE.
>  tree
>  conjoin_requirements (tree a, tree b)
>  {
> -  if (a && b)
> -    return build_min (TRUTH_ANDIF_EXPR, boolean_type_node, a, b);
> +  if (a)
> +    return b ? join_requirements (TRUTH_ANDIF_EXPR, a, b) : a;
> +  else if (b)
> +    return b;
>    else
>      return NULL_TREE;

Seems like the comment is no longer accurate; the function now only 
returns NULL_TREE if both a and b are NULL_TREE.

> +// Returns true if the function decl F is a constraint predicate. It must be a
> +// constexpr, nullary function with a boolean result type.
> +static tree
> +get_constraint_check (tree call)

The comment needs updating.  And the function isn't used anywhere; it 
seems redundant with resolve_constraint_check.

> +// The raison d'entre of this class is to prevent traits

"d'etre"

> +// and other template nodes from generating new expressions
> +// during instantiation.

I'm not clear on the issue.  Perhaps leaving processing_template_decl 
alone and using fold_non_dependent_expr would accomplish what you want?

> +static inline bool
> +check_type_constraints (tree t, tree args)
> +{
> +  return check_constraints (CLASSTYPE_TEMPLATE_CONSTRAINT (t), args);
> +}
> +
> +static inline bool
> +check_decl_constraints (tree t, tree args)
> +{
> +  if (TREE_CODE (t) == TEMPLATE_DECL)
> +    return check_decl_constraints (DECL_TEMPLATE_RESULT (t), args);
> +  else
> +    return check_constraints (DECL_TEMPLATE_CONSTRAINT (t), args);
> +}
> +
> +// Check the template's constraints for the specified arguments,
> +// returning true if the constraints are satisfied and false
> +// otherwise.
> +bool
> +check_template_constraints (tree t, tree args)
> +{
> +  return check_constraints (get_constraints (t), args);
> +}

Seems like the last function would also work for types and non-template 
decls.

> +  error_at (loc, "constraints not satisfied");

I assume you're planning to make this more verbose?  It could use a TODO 
to that effect.

> +// and template isntantiation. Evaluation warnings are also inhibited.

"instantiation"

> +  else if (are_constrained_overloads (newdecl, olddecl))
> +    {
> +      // If newdecl and olddecl are function templates with the
> +      // same type but different constraints, then they cannot be
> +      // duplicate declarations. However, if the olddecl is declared
> +      // as a concept, then the program is ill-formed.
> +      if (DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (olddecl)))
> +        {
> +          error ("cannot specialize concept %q#D", olddecl);
> +          return error_mark_node;
> +        }
> +      return NULL;
> +    }

We should check for differing constraints in decls_match, and then this 
code should be in the !types_match section of duplicate_decls.

>        error ("concept %q#D result must be convertible to bool", fn);

Why don't we require the result to actually be bool?  It seems difficult 
to decompose dependent requirements if the return type can be something 
else.

> +// Remove the current term form the list, repositioning to the term

"from"

> +//  \Gamma, P |- Delta    \Gamma, Q |- \Delta

Are the \ for TeX markup or something?  You're missing one on the left 
Delta here.

BTW, thanks: I find the rewritten logic code more readable.

> +subsumes_constraints (tree left, tree right)
> +{
> +  gcc_assert (check_constraint_info (left));
> +  gcc_assert (check_constraint_info (right));
> +
> +  // Check that c is subsumed by each subproblem in h.
> +  // If it is not, then h does not subsume c.
> +  tree as = CI_ASSUMPTIONS (left);
> +  tree c = reduce_requirements (CI_REQUIREMENTS (right));
> +  for (int i = 0; i < TREE_VEC_LENGTH (as); ++i)
> +    if (!subsumes_prop (TREE_VEC_ELT (as, i), c))
> +      return false;
> +  return true;

"h" doesn't appear anywhere in the function; let's change the comment to 
refer to "left" and "right" instead.

> +              cp_lexer_next_token_is_keyword (parser->lexer, RID_REQUIRES))
>            {
>              tree reqs = release (current_template_reqs);
> -            if (tree r = cp_parser_requires_clause_opt (parser))
> +            if (tree r = cp_parser_requires_clause (parser))

I was thinking to change the name of cp_requires_clause to 
cp_parser_requires_clause_opt and change the assert to a test for the 
keyword and return NULL_TREE if it isn't found.

> -              if (flag_concepts
> -                  && function_declarator_p (declarator)
> +              if (flag_concepts &&
> +                  function_declarator_p (declarator) &&

The && was in the right place before this change.

> +  if (!potential_rvalue_constant_expression (expr))
> +    {
> +      require_potential_rvalue_constant_expression (expr);

This can just be if (!require_pot....

> +          // FIXME: we should be checking the constraints, not just
> +          // instantiating them.

Let's check them in determine_specialization, along with the SFINAE 
check after the comment
          /* Make sure that the deduced arguments actually work.  */
Can explicit specializations have constraints, to indicate which 
template they are specializing?

> +      // FIXME: This points to the wrong line.
> +      error_at (input_location, "redeclaration %q+D with different constraints", tmpl);

%q+D is telling the diagnostic code to use DECL_SOURCE_LOCATION (tmpl) 
as the location.  I think you want

error_at (input_location, "redeclaration of %q#D with different "
           "constraints", tmpl);
inform (DECL_SOURCE_LOCATION (tmpl),
         "original declaration appeared here");

> +  tree argcons = TREE_CODE (argtype) == TEMPLATE_TEMPLATE_PARM
> +    ? DECL_TEMPLATE_CONSTRAINT (DECL_TEMPLATE_RESULT (parm))
> +    : TYPE_TEMPLATE_CONSTRAINT (argtype);

Seems like get_constraints would be useful here.

> +                        error ("constraint mismatch at argument %d in "
> +                               "template parameter list for %qD",
> +                               i + 1, in_decl);

Let's also print the parameter and argument.

> +// Argument deduction ios applied to all template arguments, and

Passing 'true' for require_all_args means no deduction will be done; 
rather, all arguments must either be specified or have default arguments.

> +      // Check class template requirements. Note that constraints will
> +      // already have been checked when trying to find a most specialized
> +      // class among multiple specializations.

I don't see where that is; more_specialized_class doesn't seem to 
compare constraints yet.

> +        tree cons = DECL_CLASS_TEMPLATE_P (t)
> +          ? TYPE_TEMPLATE_CONSTRAINT (type)
> +          : DECL_TEMPLATE_CONSTRAINT (decl);

get_constraints would be useful here as well.

> +            // FIXME: Do we need to attach constraints?
> +            // TODO: Is this actually necessary?

I don't think you need to fill in TI_CONSTRAINT for anything but the 
main template patterns, here or other places.

> +substitute_requirements (tree reqs, tree args)

This seems redundant with instantiate_requirements.

> +  // Build template info and associate it with

Incomplete sentence.

> +  // TODO: Do we need to propagate constaints into bound template
> +  // template parameters? Probably not for interface checking.

"constraints"

But I agree probably not, for the same reason we don't need constraints 
on instantiated FIELD_DECLs.

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

[-- Attachment #1: Type: text/plain, Size: 5980 bytes --]

Attached is a resubmission of the previous patch with (I think) all
comments addressed.
I ended up rewriting logic.cc after some experimentation in a separate
branch. The optimizations didn't pan out like I'd hoped, but I think
the newer version is a bit cleaner (and smaller).

There are a couple of things I did not do:

1. tree_template_info still contains constraint_info. That will change
in a subsequent patch. I'm kind of waiting for specializations to get
TEMPLATE_DECLs.

2. I left the <cstdlib> include in system.h, because removing it will
result in errors due to an inclusion of <algorithm>. It's probable
that both can be removed, but I didn't test it with this patch.

Changelog.


2013-06-14  Andrew Sutton  <andrew.n.sutton@gmail.com>
        * gcc/c-family/c.opt (flag_concepts): Remove redundant declaration.
        * gcc/c-family/c-common.c (c_common_r): Concept-specific keywords
        are only enabled when concepts are enabled.
        * gcc/c-fawmilyc-common.h (D_CXX_CONCEPTS): New flag for disabling
        concept keywords.
        * gcc/cp/tree.c (bind_template_template_parm): Provide empty
        constraints for bound template template parameters.
        * gcc/cp/logic.cc: Rewrite of proof state and related structures and
        decomposition logic. Removed right-decomposition logic, but retained
        right-logical rules.
        (match_terms): Renamed from entails.
        (subsumes_prop): Cleanup, added specific handlers for and/or cases.
        (subsumes_constraints): Update from interface change.
        * gcc/cp/cxx-pretty-print.c (pp_cxx_template_declaration): Print the
        template requirements.
        * gcc/cp/pt.c (local_specialization_stack): New.
        (build_template_info): Refactor into 3-argument version and
        incorporate template requirements.
        (check_explicit_specialization): Instantiate requirements for
        template info.
        (push_template_decl_real): Include constraints in template info.
        (redeclare_class_template): Diagnose redeclaration with different
        constraints.
        (is_compatible_template_arg): New.
        (convert_template_argument): Check constraints on template template
        arguments.
        (lookup_template_class_1): Check constraints on alias templates.
        Keep constraints with instantiated types.
        (instantiate_class_template_1): Check constraints on class templates.
        (tsubst_decl): Instantiate and keep constraints with template info.
        Also, allow dependent pack arguments to produce neww parameter
        packs when instantiated.
        (tsubst_copy): Handle REAL_TYPE and BOOLEAN_TYPE.
        (tsubst_copy_and_build): PARM_DECLs can be instantiated as pack
        expansions (used with requires expression).
        (fn_type_unification): Check constraints for function templates.
        (more_specialized_fn): Determine which candidate is more constrained.
        (substitute_template_parameters): Removed.
        (tsubst_constraint): New.
        (substitute_requirements): New.
        * gcc/cp/semantics.c (finish_template_template_parm): Build template
        info for template template parameters.
        * gcc/cp/constraint.cc (join_requirements): New
        (conjoin_requirements): Join expressions correctly.
        (disjoin_requirements): Join expressions correctly.
        (resolve_constraint_check): New. Replaces previous get_constraint
        check and related functions.
        (get_constraints): New, along with helper functions.
        (suppress_template_processing): New.
        (check_template_constraints): New, along with helper functions.
        (equivalent_constraints): New.
        (equivalently_constrained): New.
        (more_constraints): New.
        (more_constrianed): New.
        (diagnose_constraint_failure): New.
        * gcc/cp/parser.c: (cp_parser_optional) Removed along with helper
        functions, etc.
        (cp_unevaluated): New.
        (cp_parser_type_parameter): Check for requires kw explicitly, and
        save/clear template requirements before parsing the requires clause.
        (cp_parser_requires_clause): Removed.
        (cp_parser_template_declaration_after_exp): Check for requires kw
        explicitly.
        * gcc/cp/call.c (rejection_reason_code): New rr_constraint_failure.
        (template_constraint_failure): New.
        (add_function_candidate): Check for viability as a precondition to use.
        (add_template_candidate_real): Integrate constraint diagnostics.
        Provide constraint info for new template instantiations.
        (print_z_candidate): Emit diagnostics for constraint failures.
        (get_actual_template): New.
        (joust): Allow non-member templates of class templates to be evaluated
        in more_specialized_fn if they are constrained.
        * gcc/cp/cp-tree.h (check_constraint_info): Renamed and applied
        interface change.
        (check_template_info): Renamed and applied interface change.
        (cp_unevaluated): New
        (local_specialization_stack): New.
        (coerce_template_parms): New.
        (get_constraints): New.
        (check_constraints): New.
        (check_template_constraints): New.
        (subst_template_constraints): New.
        (equivalent_constraints): New.
        (equivalently_constrained): New.
        (more_constraints): New.
        (more_constrained): New.
        (diagnose_constraints_failure): New.
        * gcc/cp/class.c (are_constrained_member_overloads): New.
        (add_method): Allow overloading of constrained member functions.
        * gcc/cp/decl.c (are_constrained_overloads): New.
        (duplicate_decls): Allow constrained overloads except for concepts.
        (check_concept_fn): Don't fail completely just because the concept
        isn't defined correctly. Allow analysis to continue as if declared
        constexpr.
        * gcc/cp/ptree.c (cxx_print_xnode): Dump constraint info.


Andrew

[-- Attachment #2: reqs-2.patch --]
[-- Type: application/octet-stream, Size: 74353 bytes --]

Index: c-family/c.opt
===================================================================
--- c-family/c.opt	(revision 199411)
+++ c-family/c.opt	(working copy)
@@ -21,10 +21,6 @@
 
 ; Please try to keep this file in ASCII collating order.
 
-; Activate C++ concepts support.
-Variable
-bool flag_concepts
-
 Language
 C
 
Index: c-family/c-common.c
===================================================================
--- c-family/c-common.c	(revision 199581)
+++ c-family/c-common.c	(working copy)
@@ -555,11 +555,11 @@ const struct c_common_resword c_common_r
   { "while",		RID_WHILE,	0 },
 
   /* Concepts-related keywords */
-  { "assume",		RID_ASSUME,	D_CXXONLY | D_CXX0X | D_CXXWARN },
-  { "axiom",		RID_AXIOM,	D_CXXONLY | D_CXX0X | D_CXXWARN },
-  { "concept",		RID_CONCEPT,	D_CXXONLY | D_CXX0X | D_CXXWARN },
-  { "forall", 		RID_FORALL,	D_CXXONLY | D_CXX0X | D_CXXWARN },
-  { "requires", 	RID_REQUIRES,	D_CXXONLY | D_CXX0X | D_CXXWARN },
+  { "assume",		RID_ASSUME,	D_CXX_CONCEPTS_FLAGS | D_CXXWARN },
+  { "axiom",		RID_AXIOM,	D_CXX_CONCEPTS_FLAGS | D_CXXWARN },
+  { "concept",		RID_CONCEPT,	D_CXX_CONCEPTS_FLAGS | D_CXXWARN },
+  { "forall", 		RID_FORALL,	D_CXX_CONCEPTS_FLAGS | D_CXXWARN },
+  { "requires", 	RID_REQUIRES,	D_CXX_CONCEPTS_FLAGS | D_CXXWARN },
 
   /* These Objective-C keywords are recognized only immediately after
      an '@'.  */
Index: c-family/c-common.h
===================================================================
--- c-family/c-common.h	(revision 199581)
+++ c-family/c-common.h	(working copy)
@@ -368,6 +368,9 @@ struct c_common_resword
 #define D_OBJC		0x080	/* In Objective C and neither C nor C++.  */
 #define D_CXX_OBJC	0x100	/* In Objective C, and C++, but not C.  */
 #define D_CXXWARN	0x200	/* In C warn with -Wcxx-compat.  */
+#define D_CXX_CONCEPTS  0x400   /* In C++, only with concepts. */
+
+#define D_CXX_CONCEPTS_FLAGS D_CXXONLY | D_CXX0X | D_CXX_CONCEPTS
 
 /* The reserved keyword table.  */
 extern const struct c_common_resword c_common_reswords[];
Index: cp/tree.c
===================================================================
--- cp/tree.c	(revision 199411)
+++ cp/tree.c	(working copy)
@@ -2025,8 +2025,12 @@ bind_template_template_parm (tree t, tre
      arguments.  */
   TEMPLATE_TYPE_PARM_INDEX (t2) = copy_node (TEMPLATE_TYPE_PARM_INDEX (t));
   TEMPLATE_PARM_DECL (TEMPLATE_TYPE_PARM_INDEX (t2)) = decl;
+
+  // TODO: Do we need to propagate constaints into bound template
+  // template parameters? Probably not for interface checking.
   TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t2)
-    = build_template_info (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t), newargs);
+    = build_template_info (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t), 
+                           newargs, NULL_TREE);
 
   TREE_TYPE (decl) = t2;
   TYPE_NAME (t2) = decl;
Index: cp/logic.cc
===================================================================
--- cp/logic.cc	(revision 199581)
+++ cp/logic.cc	(working copy)
@@ -74,45 +74,81 @@ struct term_list : std::list<tree>
   term_list (const term_list &x);
   term_list& operator= (const term_list &x);
 
-  iterator cur;
+  tree       current_term ()       { return *current; }
+  const_tree current_term () const { return *current; }
+
+
+  void insert (tree t);
+  tree erase ();
+
+  void start ();
+  void next ();
+  bool done() const;
+
+  iterator current;
 };
 
 inline
 term_list::term_list ()
-  : std::list<tree> (), cur (end ())
+  : std::list<tree> (), current (end ())
 { }
 
 inline
 term_list::term_list (const term_list &x)
-  : std::list<tree> (x), cur (::next_by_distance (begin (), x.begin (), x.cur))
+  : std::list<tree> (x)
+  , current (next_by_distance (begin (), x.begin (), x.current))
 { }
 
 inline term_list&
 term_list::operator= (const term_list &x)
 {
   std::list<tree>::operator=(x);
-  cur = next_by_distance (begin (), x.begin (), x.cur);
+  current = next_by_distance (begin (), x.begin (), x.current);
   return *this;
 }
 
-// Insert the term t into the list at the current position, making
+// Insert the term T into the list before the current position, making
 // this term current.
 inline void
-insert_term (term_list& l, tree t)
+term_list::insert (tree t)
 {
-  l.cur = l.insert (l.cur, t);
+  current = std::list<tree>::insert (current, t);
 }
 
-// Remove the current term form the list, repositioning the current
-// position at the next term in the list.
+// Remove the current term form the list, repositioning to the term
+// following the removed term. Note that the new position could be past 
+// the end of the list.
+//
+// The removed term is returned.
 inline tree
-remove_term (term_list& l)
+term_list::erase ()
 {
-  tree t = *l.cur;
-  l.cur = l.erase (l.cur);
+  tree t = *current;
+  current = std::list<tree>::erase (current);
   return t;
 }
 
+// Initialize the current term to the first in the list.
+inline void
+term_list::start ()
+{
+  current = begin ();
+}
+
+// Advance to the next term in the list.
+inline void
+term_list::next ()
+{
+  ++current;
+}
+
+// Returns true when the current position is past the end.
+inline bool
+term_list::done () const
+{
+  return current == end ();
+}
+
 
 // -------------------------------------------------------------------------- //
 // Proof Goal
@@ -122,24 +158,10 @@ remove_term (term_list& l)
 // constraint language (i.e., lists of trees).
 struct proof_goal
 {
-  term_list as; // Assumptions
-  term_list cs; // Conclusions   
+  term_list assumptions;
+  term_list conclusions;
 };
 
-// Return the list of assumed terms for the goal g.
-inline term_list &
-assumptions (proof_goal &g) { return g.as; }
-
-inline const term_list &
-assumptions (const proof_goal &g) { return g.as; }
-
-// Return the list of concluded terms for the goal g.
-inline term_list &
-conclusions (proof_goal &g) { return g.cs; }
-
-inline const term_list &
-conclusions (const proof_goal &g) { return g.cs; }
-
 
 // -------------------------------------------------------------------------- //
 // Proof State
@@ -151,145 +173,26 @@ struct proof_state : std::list<proof_goa
 {
   proof_state ();
 
-  iterator cur;
+  iterator branch (iterator i);
 };
 
-// Initialize the state with a single empty goal, and set
-// that goal as the current subgoal.
+// An alias for proof state iterators.
+typedef proof_state::iterator goal_iterator;
+
+// Initialize the state with a single empty goal, and set that goal as the
+// current subgoal.
 inline
 proof_state::proof_state ()
-  : std::list<proof_goal> (1), cur (begin ())
+  : std::list<proof_goal> (1)
 { }
 
 
-// Return the current goal. Provided for notational symmetry
-inline proof_goal &
-current_goal (proof_state &s) { return *s.cur; }
-
-inline const proof_goal &
-current_goal (const proof_state &s) { return *s.cur; }
-
-// Return the current list of assumed terms.
-inline term_list &
-assumptions (proof_state &s) { return assumptions (current_goal (s)); }
-
-inline const term_list &
-assumptions (const proof_state &s) { return assumptions (current_goal (s)); }
-
-// Return the current list of concluded terms.
-inline term_list &
-conclusions (proof_state &s) { return conclusions (current_goal (s)); }
-
-inline const term_list &
-conclusions (const proof_state &s) { return conclusions (current_goal (s)); }
-
-// Return the current assumption.
-inline tree
-assumption (const proof_state &s) { return *assumptions (s).cur; }
-
-// Return the current conclision.
-inline tree
-conclusion (const proof_state &s) { return *conclusions (s).cur; }
-
-// Move to the next goal.
-inline void
-next_goal (proof_state &s) { ++s.cur; }
-
-// Move to the next assumption.
-inline void
-next_assumption (proof_state &s) { ++assumptions (s).cur; }
-
-// Move to the next conclusion.
-inline void
-next_conclusion (proof_state &s) { ++conclusions (s).cur; }
-
-
-// -------------------------------------------------------------------------- //
-// Term List Manipulation
-//
-// The following functions are used to manage the insertation and removal
-// goals and terms in the proof state.
-
-// Assume the term e in the current goal. The current assumption is set to the
-// new term.
-inline void
-assume_term (proof_goal &g, tree e) { insert_term (assumptions (g), e); }
-
-inline void 
-assume_term (proof_state &s, tree e) { assume_term (current_goal (s), e); }
-
-// Forget the current assumption, removing it from the context of the current
-// goal. Returns the forgotten assumption.
-inline tree
-forget_term (proof_goal &g) { return remove_term (assumptions (g)); }
-
-inline tree
-forget_term (proof_state &s) { return forget_term (current_goal (s)); }
-
-// Conclude the term e in the current goal. The current conclusion is set to 
-// the new term.
-inline void
-conclude_term (proof_goal &g, tree e) { insert_term (conclusions (g), e); }
-
-inline void
-conclude_term (proof_state &s, tree e) { conclude_term (current_goal (s), e); }
-
-// Ignore the current conclusion, removing it from the conclusions
-// of the current goal. Returns the ignored conclusion.
-inline tree
-ignore_term (proof_goal &g) { return remove_term (conclusions (g)); }
-
-inline tree
-ignore_term (proof_state &s) { return ignore_term (current_goal (s)); }
-
 // Branch the current goal by creating a new subgoal, returning a reference to
-// the new objet. This does not update the current goal.
-inline proof_goal &
-branch_goal (proof_state &s)
-{
-  proof_state::iterator p = s.cur;
-  p = s.insert (++p, *s.cur);
-  return *p;
-}
-
-
-// -------------------------------------------------------------------------- //
-// Debugging
-//
-// Helper functions for debugging the proof state.
-
-void
-debug (term_list &l)
+// the new object. This does not update the current goal.
+inline proof_state::iterator
+proof_state::branch (iterator i)
 {
-  term_list::iterator i = l.begin ();
-  term_list::iterator last = --l.end ();
-  term_list::iterator end = l.end ();
-  for ( ; i != end; ++i)
-    {
-      debug (*i);
-      if (i != last)
-        fprintf (stderr, " ");
-    }
-}
-
-void
-debug (proof_goal &g)
-{
-  debug (g.as);
-  fprintf (stderr, " |- ");
-  debug (g.cs);
-}
-
-void
-debug (proof_state& s)
-{
-  proof_state::iterator i = s.begin ();
-  proof_state::iterator end = s.end ();
-  for ( ; i != end; ++i)
-    {
-      debug (*i);
-      fprintf (stderr, "\n");
-    }
+  return insert (++i, *i);
 }
 
 
@@ -299,63 +202,82 @@ debug (proof_state& s)
 // These functions modify the current state and goal by decomposing
 // logical expressions using the logical rules of sequent calculus for
 // first order logic.
+//
+// Note that in each decomposition rule, the term T has been erased
+// from term list before the specific rule is applied.
 
-
-// And left logical rule.
+// Left-and logical rule.
+//
+//  \Gamma, P, Q |- \Delta
+//  -------------------------
+//  \Gamma, P and Q |- \Delta
 inline void 
-and_left (proof_state &s)
+left_and (proof_state &, goal_iterator i, tree t)
 {
-  gcc_assert (TREE_CODE (assumption (s)) == TRUTH_ANDIF_EXPR);
-  tree t = forget_term (s);
-  assume_term (s, TREE_OPERAND (t, 1));
-  assume_term (s, TREE_OPERAND (t, 0));
-}
+  gcc_assert (TREE_CODE (t) == TRUTH_ANDIF_EXPR);
 
-// And right logical rule.
-inline void
-and_right (proof_state &s)
-{
-  gcc_assert (TREE_CODE (conclusion (s)) == TRUTH_ANDIF_EXPR);
-  tree t = ignore_term (s);
-  conclude_term (branch_goal (s), TREE_OPERAND (t, 1));
-  conclude_term (current_goal (s), TREE_OPERAND (t, 0));
+  // Insert the operands into the current branch. Note that the
+  // final order of insertion is left-to-right.
+  term_list &l = i->assumptions;
+  l.insert (TREE_OPERAND (t, 1));
+  l.insert (TREE_OPERAND (t, 0));
 }
 
-// Or left logical rule.
+// Left-or logical rule.
+//
+//  \Gamma, P |- Delta    \Gamma, Q |- \Delta
+//  -----------------------------------------
+//  \Gamma, P or Q |- \Delta
 inline void
-or_left (proof_state& s)
+left_or (proof_state &s, goal_iterator i, tree t)
 {
-  gcc_assert (TREE_CODE (assumption (s)) == TRUTH_ORIF_EXPR);
-  tree t = forget_term (s);
-  assume_term (branch_goal (s), TREE_OPERAND (t, 1));
-  assume_term (current_goal (s), TREE_OPERAND (t, 0));
+  gcc_assert (TREE_CODE (t) == TRUTH_ORIF_EXPR);
+
+  // Branch the current subgoal.
+  goal_iterator j = s.branch (i);
+  term_list &l1 = i->assumptions;
+  term_list &l2 = j->assumptions;
+
+  // Insert operands into the different branches.
+  l1.insert (TREE_OPERAND (t, 0));
+  l2.insert (TREE_OPERAND (t, 1));
 }
 
-// Or right logical rule.
+// Right-and logical rule.
+//
+//  \Gamma |- P, Delta    \Gamma |- Q, \Delta
+//  -----------------------------------------
+//  \Gamma |- P and Q, \Delta
 inline void
-or_right (proof_state &s)
+right_and (proof_state &s, goal_iterator i, tree t)
 {
-  gcc_assert (TREE_CODE (conclusion (s)) == TRUTH_ORIF_EXPR);
-  tree t = ignore_term (s);
-  conclude_term (s, TREE_OPERAND (t, 1));
-  conclude_term (s, TREE_OPERAND (t, 0));
-}
+  gcc_assert (TREE_CODE (t) == TRUTH_ORIF_EXPR);
 
+  // Branch the current subgoal.
+  goal_iterator j = s.branch (i);
+  term_list &l1 = i->conclusions;
+  term_list &l2 = j->conclusions;
 
-// -------------------------------------------------------------------------- //
-// Algorithms
+  // Insert operands into the different branches.
+  l1.insert (TREE_OPERAND (t, 0));
+  l2.insert (TREE_OPERAND (t, 1));
+}
+
+// Right-or logical rule.
 //
-// Generic algorithms for querying or manipulating a proof state.
+//  \Gamma |- P, Q, \Delta
+//  ------------------------
+//  \Gamma |- P or Q, \Delta
+inline void
+right_or (proof_state &, goal_iterator i, tree t)
+{
+  gcc_assert (TREE_CODE (t) == TRUTH_ANDIF_EXPR);
 
-// Apply fn for each goal and returns fn. The current goal is set prior to
-// calling fn.
-template<typename F>
-  inline F
-  for_each_goal (proof_state &s, F fn)
-  {
-    for (s.cur = s.begin (); s.cur != s.end (); ++s.cur)
-      fn (s);
-    return fn;
+  // Insert the operands into the current branch. Note that the
+  // final order of insertion is left-to-right.
+  term_list &l = i->conclusions;
+  l.insert (TREE_OPERAND (t, 1));
+  l.insert (TREE_OPERAND (t, 0));
   }
 
 
@@ -375,60 +297,40 @@ template<typename F>
 // subgoal that can be further decomposed.
 
 void
-decompose_left_term (proof_state &s)
-{
-  tree e = assumption (s);
-  if (TREE_CODE (e) == TRUTH_ANDIF_EXPR)
-    and_left (s);
-  else if (TREE_CODE (e) == TRUTH_ORIF_EXPR)
-    or_left (s);
-  else
-    next_assumption (s);
-}
-
-void 
-decompose_left_goal (proof_state &s)
+decompose_left_term (proof_state &s, goal_iterator i)
 {
-  term_list& l = assumptions (s);
-  for (l.cur = l.begin (); l.cur != l.end (); )
-    decompose_left_term (s);
-}
-
-inline void
-decompose_left (proof_state& s)
+  term_list &l = i->assumptions;
+  tree t = l.current_term ();
+  switch (TREE_CODE (t))
 {
-  for_each_goal (s, decompose_left_goal);
+    case TRUTH_ANDIF_EXPR:
+      left_and (s, i, l.erase ());
+      break;
+    case TRUTH_ORIF_EXPR:
+      left_or (s, i, l.erase ());
+      break;
+    default:
+      l.next ();
+      break;
 }
-
-// Right decomposition.
-// Continually decompose conclusions until there are no terms in any
-// subgoal that can be further decomposed.
-
-void
-decompose_right_term (proof_state &s)
-{
-  tree e = conclusion (s);
-  if (TREE_CODE (e) == TRUTH_ANDIF_EXPR)
-    and_right (s);
-  else if (TREE_CODE (e) == TRUTH_ORIF_EXPR)
-    or_right (s);
-  else
-    next_conclusion (s);
 }
 
 void
-decompose_right_goal (proof_state &s)
+decompose_left_goal (proof_state &s, goal_iterator i)
 {
-  term_list& l = conclusions (s);
-  for (l.cur = l.begin (); l.cur != l.end (); )
-    decompose_right_term (s);
+  term_list& l = i->assumptions;
+  l.start ();
+  while (!l.done ())
+    decompose_left_term (s, i);
 }
 
-
 inline void
-decompose_right (proof_state& s)
+decompose_left (proof_state& s)
 {
-  for_each_goal (s, decompose_right_goal);
+  goal_iterator iter = s.begin ();
+  goal_iterator end = s.end ();
+  for ( ; iter != end; ++iter)
+    decompose_left_goal (s, iter);
 }
 
 
@@ -436,32 +338,17 @@ decompose_right (proof_state& s)
 // Term Extraction
 //
 // Extract a list of term lists from a proof state, and return it as a
-// a tree (a vetor of vectors).
+// a tree (a vector of vectors).
 
 // Returns a vector of terms from the given term list.
 tree
 extract_terms (term_list& l)
 {
   tree result = make_tree_vec (l.size());
-  term_list::iterator i = l.begin();
-  term_list::iterator e = l.end();
-  for (int n = 0; i != e; ++i, ++n)
-    TREE_VEC_ELT (result, n) = *i;
-  return result;
-}
-
-// Extract a vector of term vectors from s. The selected set of terms is given
-// by the projection function proj. This is generally either assumptions or
-// conclusions.
-template<typename F>
-  tree
-  extract_goals (proof_state& s, F proj)
-  {
-    tree result = make_tree_vec (s.size ());
-    proof_state::iterator i = s.begin ();
-    proof_state::iterator e = s.end ();
-    for (int n = 0; i != e; ++i, ++n)
-      TREE_VEC_ELT (result, n) = extract_terms (proj (*i));
+  term_list::iterator iter = l.begin();
+  term_list::iterator end = l.end();
+  for (int n = 0; iter != end; ++iter, ++n)
+    TREE_VEC_ELT (result, n) = *iter;
     return result;
   }
 
@@ -469,43 +356,33 @@ template<typename F>
 inline tree
 extract_assumptions (proof_state& s)
 {
-  term_list& (*proj)(proof_goal&) = assumptions;
-  return extract_goals (s, proj);
-}
-
-// Extract the conclusion vector from the proof state s.
-inline tree
-extract_conclusions (proof_state& s)
-{
-  term_list& (*proj)(proof_goal&) = conclusions;
-  return extract_goals (s, proj);
+  tree result = make_tree_vec (s.size ());
+  goal_iterator iter = s.begin ();
+  goal_iterator end = s.end ();
+  for (int n = 0; iter != end; ++iter, ++n)
+    TREE_VEC_ELT (result, n) = extract_terms (iter->assumptions);
+  return result;
 }
 
 } // namespace
 
 
-// Decompose the requirement R into a set of assumptions, returing a
-// vector of vectors containing atomic propositions.
+// Decompose the required expression T into a constraint set: a
+// vector of vectors containing only atomic propositions.
 tree
-decompose_assumptions (tree r)
+decompose_assumptions (tree t)
 {
+  // Create a proof state, and insert T as the sole assumption.
   proof_state s;
-  assume_term (s, r);
+  term_list &l = s.begin ()->assumptions;
+  l.insert (t);
+  
+  // Decompose the expression into a constraint set, and then
+  // extract the terms for the AST.
   decompose_left (s);
   return extract_assumptions (s);
 }
 
-// Decompose the requirement R into a set of conclusionss, returning a
-// vector of vectors containing atomic propositions.
-tree
-decompose_conclusions (tree r)
-{
-  proof_state s;
-  conclude_term (s, r);
-  decompose_right (s);
-  return extract_conclusions (s);
-}
-
 
 // -------------------------------------------------------------------------- //
 // Subsumption and Entailment
@@ -515,11 +392,20 @@ decompose_conclusions (tree r)
 
 namespace {
 
-// Returns true if the assumed proposition A entails the conclusion C.
-// In general, this is the case when A has equivalent spelling to C,
-// although there will be some special cases.
+bool subsumes_prop(tree, tree);
+bool subsumes_atom(tree, tree);
+bool subsumes_and(tree, tree);
+bool subsumes_or(tree, tree);
+
+// Returns true if the assumption A matches the conclusion C. This
+// is generally the case when A and C have the same syntax.
+//
+// TODO: Implement special cases for:
+//    * __is_same_as |- __is_convertible_to
+//    * __is_same_as |- __is_derived_from
+//    * Any other built-in predicates?
 bool
-entails_atom (tree a, tree c)
+match_terms (tree a, tree c)
 {
   // TODO: Add special cases for __is_same, __is_convertible, 
   // and __is_base_of.
@@ -528,16 +414,33 @@ entails_atom (tree a, tree c)
 
 // Returns true if the list of assumptions AS subsume the atomic 
 // proposition C. This is the case when we can find a proposition in
-// HS that entails the conclusion C.
+// AS that entails the conclusion C.
 bool
 subsumes_atom (tree as, tree c)
 {
   for (int i = 0; i < TREE_VEC_LENGTH (as); ++i)
-    if (entails_atom (TREE_VEC_ELT (as, i), c))
+    if (match_terms (TREE_VEC_ELT (as, i), c))
       return true;
   return false;
 }
 
+// Returns true when both operands of C are subsumed by the assumptions AS.
+inline bool 
+subsumes_and (tree as, tree c)
+{
+  tree l = TREE_OPERAND (c, 0);
+  tree r = TREE_OPERAND (c, 1);
+  return subsumes_prop (as, l) && subsumes_prop (as, r);
+}
+
+// Returns true when either operand of C is subsumed by the assumptions AS.
+inline bool
+subsumes_or (tree as, tree c)
+{
+  tree l = TREE_OPERAND (c, 0);
+  tree r = TREE_OPERAND (c, 1);
+  return subsumes_prop (as, l) || subsumes_prop (as, r);
+}
 
 // Returns true when the list of assumptions AS subsumes the 
 // concluded proposition C.
@@ -550,11 +453,9 @@ subsumes_prop (tree as, tree c)
   switch (TREE_CODE (c))
     {
     case TRUTH_ANDIF_EXPR:
-      return subsumes_prop (as, TREE_OPERAND (c, 0)) 
-          && subsumes_prop (as, TREE_OPERAND (c, 1));
+      return subsumes_and (as, c);
     case TRUTH_ORIF_EXPR:
-      return subsumes_prop (as, TREE_OPERAND (c, 0)) 
-          || subsumes_prop (as, TREE_OPERAND (c, 1));
+      return subsumes_or (as, c);
     default:
       return subsumes_atom (as, c);
     }
@@ -566,8 +467,8 @@ subsumes_prop (tree as, tree c)
 bool
 subsumes_constraints (tree left, tree right)
 {
-  gcc_assert (constraint_info_p (left));
-  gcc_assert (constraint_info_p (right));
+  gcc_assert (check_constraint_info (left));
+  gcc_assert (check_constraint_info (right));
 
   // Check that c is subsumed by each subproblem in h.
   // If it is not, then h does not subsume c.
@@ -583,7 +484,7 @@ subsumes_constraints (tree left, tree ri
 
 
 // Returns true the LEFT constraints subsume the RIGHT constraints. Note
-// that subsumption is a reflexive relation.
+// that subsumption is a reflexive relation (e.g., <=)
 bool
 subsumes (tree left, tree right)
 {
@@ -596,3 +497,4 @@ subsumes (tree left, tree right)
   return subsumes_constraints (left, right);
 }
 
+
Index: cp/cxx-pretty-print.c
===================================================================
--- cp/cxx-pretty-print.c	(revision 199411)
+++ cp/cxx-pretty-print.c	(working copy)
@@ -2182,6 +2182,14 @@ pp_cxx_template_declaration (cxx_pretty_
       pp_cxx_end_template_argument_list (pp);
       pp_newline_and_indent (pp, 3);
     }
+
+  if (tree c = get_constraints (t))
+    {
+      pp_cxx_ws_string (pp, "requires");
+      pp_cxx_expression (pp, CI_REQUIREMENTS (c));
+      pp_newline_and_indent (pp, 6);
+    }
+
   if (TREE_CODE (t) == FUNCTION_DECL && DECL_SAVED_TREE (t))
     pp_cxx_function_definition (pp, t);
   else
Index: cp/pt.c
===================================================================
--- cp/pt.c	(revision 199581)
+++ cp/pt.c	(working copy)
@@ -77,6 +77,23 @@ static tree cur_stmt_expr;
    local variables.  */
 static struct pointer_map_t *local_specializations;
 
+// -------------------------------------------------------------------------- //
+// Local Specialization Stack
+//
+// Implementation of the RAII helper for creating new local
+// specializations.
+local_specialization_stack::local_specialization_stack ()
+  : saved (local_specializations)
+{
+  local_specializations = pointer_map_create ();
+}
+
+local_specialization_stack::~local_specialization_stack ()
+{
+  pointer_map_destroy (local_specializations);
+  local_specializations = saved;
+}
+
 /* True if we've recursed into fn_type_unification too many times.  */
 static bool excessive_deduction_depth;
 
@@ -301,9 +318,16 @@ finish_member_template_decl (tree decl)
 tree
 build_template_info (tree template_decl, tree template_args)
 {
+  return build_template_info (template_decl, template_args, NULL_TREE);
+}
+
+tree
+build_template_info (tree template_decl, tree template_args, tree template_reqs)
+{
   tree result = make_node (TEMPLATE_INFO);
   TI_TEMPLATE (result) = template_decl;
   TI_ARGS (result) = template_args;
+  TI_CONSTRAINT (result) = template_reqs;
   return result;
 }
 
@@ -2683,6 +2707,11 @@ check_explicit_specialization (tree decl
 	    }
 
 	  /* Set up the DECL_TEMPLATE_INFO for DECL.  */
+          
+          // FIXME: we should be checking the constraints, not just
+          // instantiating them.
+          tree fn = DECL_TEMPLATE_RESULT (tmpl);
+          tree cons = tsubst_constraint (DECL_TEMPLATE_CONSTRAINT (fn), targs);
 	  DECL_TEMPLATE_INFO (decl) = build_template_info (tmpl, targs);
 
 	  /* Inherit default function arguments from the template
@@ -4878,7 +4907,7 @@ template arguments to %qD do not match o
   if (DECL_TEMPLATE_INFO (tmpl))
     args = add_outermost_template_args (DECL_TI_ARGS (tmpl), args);
 
-  info = build_template_info (tmpl, args);
+  info = build_template_info (tmpl, args, current_template_reqs);
 
   if (DECL_IMPLICIT_TYPEDEF_P (decl))
     SET_TYPE_TEMPLATE_INFO (TREE_TYPE (tmpl), info);
@@ -5029,6 +5058,15 @@ redeclare_class_template (tree type, tre
 	TREE_PURPOSE (TREE_VEC_ELT (parms, i)) = tmpl_default;
     }
 
+  // Cannot redeclare a class template with a different set of constraints. 
+  tree tmpl_type = TREE_TYPE (tmpl);
+  if (!equivalent_constraints (TYPE_TEMPLATE_CONSTRAINT (tmpl_type), cons))
+    {
+      // FIXME: This points to the wrong line.
+      error_at (input_location, "redeclaration %q+D with different constraints", tmpl);
+      inform (input_location, "original declaration appeared here");
+    }
+
     return true;
 }
 
@@ -6160,6 +6198,50 @@ canonicalize_type_argument (tree arg, ts
   return arg;
 }
 
+// A template declaration can be substituted for a constrained
+// template template parameter only when the argument is more 
+// constrained than the parameter.
+static bool
+is_compatible_template_arg (tree parm, tree arg)
+{
+  // TODO: The argument may not have a decl result. This seems to
+  // happen in some classes with nested template template
+  // parameters (e.g., a rebind struct in a class taking a template
+  // template parameter. If this is the case, just return true and
+  // allow things to happen as they always did.
+  if (TREE_CODE (arg) == TEMPLATE_DECL)
+    {
+      if (!DECL_TEMPLATE_RESULT (arg))
+        return true;
+    }
+
+  // If the template parameter is constrained, we need to rewrite its
+  // constraints in terms of the ARG's template parameters. This ensures
+  // that all of the template parameter types will have the same depth.
+  //
+  // Note that this is only valid when coerce_template_template_parm is
+  // true for the innermost template parameters of parm and arg. In other
+  // words, because coercion is successful, conversion will be valid.
+  tree parmcons = DECL_TEMPLATE_CONSTRAINT (DECL_TEMPLATE_RESULT (parm));
+  if (parmcons)
+    {
+      tree args = template_parms_to_args (DECL_TEMPLATE_PARMS (arg));
+      ++processing_template_decl;
+      tree reqs = instantiate_requirements (CI_REQUIREMENTS (parmcons), args);
+      --processing_template_decl;
+      if (reqs == error_mark_node)
+        return false;
+      parmcons = make_constraints (reqs);
+    }
+
+  // Fish for constraints on the argument.
+  tree argtype = TREE_TYPE (arg);
+  tree argcons = TREE_CODE (argtype) == TEMPLATE_TEMPLATE_PARM
+    ? DECL_TEMPLATE_CONSTRAINT (DECL_TEMPLATE_RESULT (parm))
+    : TYPE_TEMPLATE_CONSTRAINT (argtype);
+  return more_constraints (argcons, parmcons);
+}
+
 /* Convert the indicated template ARG as necessary to match the
    indicated template PARM.  Returns the converted ARG, or
    error_mark_node if the conversion was unsuccessful.  Error and
@@ -6304,9 +6386,7 @@ convert_template_argument (tree parm,
 	  else
 	    {
 	      tree parmparm = DECL_INNERMOST_TEMPLATE_PARMS (parm);
-	      tree argparm;
-
-              argparm = DECL_INNERMOST_TEMPLATE_PARMS (arg);
+	      tree argparm = DECL_INNERMOST_TEMPLATE_PARMS (arg);
 
 	      if (coerce_template_template_parms (parmparm, argparm,
 						  complain, in_decl,
@@ -6337,6 +6417,20 @@ convert_template_argument (tree parm,
 
 		  val = error_mark_node;
 		}
+
+              // Check that the constraints are compatible before allowing the
+              // substitution.
+              if (val != error_mark_node)
+                if (!is_compatible_template_arg (parm, arg))
+                  {
+                      if (in_decl && (complain & tf_error))
+                      {
+                        error ("constraint mismatch at argument %d in "
+                               "template parameter list for %qD",
+                               i + 1, in_decl);
+                      }                      
+                      val = error_mark_node;
+                  }
 	    }
 	}
       else
@@ -6543,7 +6637,6 @@ any_pack_expanson_args_p (tree args)
   return false;
 }
 
-
 /* Convert all template arguments to their appropriate types, and
    return a vector containing the innermost resulting template
    arguments.  If any error occurs, return error_mark_node. Error and
@@ -6741,6 +6834,19 @@ coerce_template_parms (tree parms,
   return new_inner_args;
 }
 
+// Convert all template arguments to their appropriate types, and
+// return a vector containing the innermost resulting template
+// arguments.  If any error occurs, return error_mark_node. Error and
+// warning messages are not issued.
+
+// Argument deduction ios applied to all template arguments, and
+// default arguments are used to fill in unspecified arguments.
+tree
+coerce_template_parms (tree parms, tree args, tree in_decl)
+{
+  return coerce_template_parms (parms, args, in_decl, tf_none, true, true);
+}
+
 /* Like coerce_template_parms.  If PARMS represents all template
    parameters levels, this function returns a vector of vectors
    representing all the resulting argument levels.  Note that in this
@@ -7371,6 +7477,10 @@ lookup_template_class_1 (tree d1, tree a
 	}
       else if (DECL_ALIAS_TEMPLATE_P (gen_tmpl))
 	{
+          // Check the alias declaration's args. 
+          if (!check_template_constraints (gen_tmpl, arglist))
+            return error_mark_node;
+
 	  /* The user referred to a specialization of an alias
 	    template represented by GEN_TMPL.
 
@@ -7534,7 +7644,10 @@ lookup_template_class_1 (tree d1, tree a
 	    : CLASSTYPE_TI_TEMPLATE (found);
 	}
 
-      SET_TYPE_TEMPLATE_INFO (t, build_template_info (found, arglist));
+      // Build the constraints for this type. 
+      tree type = TREE_TYPE (found);
+      tree cons = tsubst_constraint (TYPE_TEMPLATE_CONSTRAINT (type), arglist);
+       SET_TYPE_TEMPLATE_INFO (t, build_template_info (found, arglist, cons));
 
       elt.spec = t;
       slot = htab_find_slot_with_hash (type_specializations,
@@ -8600,6 +8713,12 @@ instantiate_class_template_1 (tree type)
     {
       pattern = TREE_TYPE (templ);
       args = CLASSTYPE_TI_ARGS (type);
+
+      // Check class template requirements. Note that constraints will 
+      // already have been checked when trying to find a most specialized 
+      // class among multiple specializations.
+      if (!check_template_constraints (pattern, args))
+        return error_mark_node;
     }
 
   /* If the template we're instantiating is incomplete, then clearly
@@ -9981,6 +10100,7 @@ tsubst_decl (tree t, tree args, tsubst_f
 	/* We can get here when processing a member function template,
 	   member class template, or template template parameter.  */
 	tree decl = DECL_TEMPLATE_RESULT (t);
+  tree type = TREE_TYPE (t);
 	tree spec;
 	tree tmpl_args;
 	tree full_args;
@@ -9988,7 +10108,7 @@ tsubst_decl (tree t, tree args, tsubst_f
 	if (DECL_TEMPLATE_TEMPLATE_PARM_P (t))
 	  {
 	    /* Template template parameter is treated here.  */
-	    tree new_type = tsubst (TREE_TYPE (t), args, complain, in_decl);
+	    tree new_type = tsubst (type, args, complain, in_decl);
 	    if (new_type == error_mark_node)
 	      RETURN (error_mark_node);
 	    /* If we get a real template back, return it.  This can happen in
@@ -10049,7 +10169,15 @@ tsubst_decl (tree t, tree args, tsubst_f
 	gcc_assert (DECL_LANG_SPECIFIC (r) != 0);
 	DECL_CHAIN (r) = NULL_TREE;
 
-	DECL_TEMPLATE_INFO (r) = build_template_info (t, args);
+        // Rebuild the constraints on the original template.
+        tree cons = DECL_CLASS_TEMPLATE_P (t)
+          ? TYPE_TEMPLATE_CONSTRAINT (type)
+          : DECL_TEMPLATE_CONSTRAINT (decl);
+        cons = tsubst_constraint (cons, args);
+ 
+        // Build new template info linking to the original template
+        // decl, but having these args and constraints.
+        DECL_TEMPLATE_INFO (r) = build_template_info (t, args, cons);	
 
 	if (TREE_CODE (decl) == TYPE_DECL
 	    && !TYPE_DECL_ALIAS_P (decl))
@@ -10286,8 +10414,11 @@ tsubst_decl (tree t, tree args, tsubst_f
 	   GEN_TMPL is NULL.  */
 	if (gen_tmpl)
 	  {
+            // Rebuild the template constraint.
+            tree cons = tsubst_constraint (DECL_TEMPLATE_CONSTRAINT (t), args);
+	    
 	    DECL_TEMPLATE_INFO (r)
-	      = build_template_info (gen_tmpl, argvec);
+	      = build_template_info (gen_tmpl, argvec, cons);
 	    SET_DECL_IMPLICIT_INSTANTIATION (r);
 
 	    tree new_r
@@ -10426,13 +10557,15 @@ tsubst_decl (tree t, tree args, tsubst_f
               /* We're on the Ith parameter of the function parameter
                  pack.  */
               {
-		/* An argument of a function parameter pack is not a parameter
-		   pack.  */
-		FUNCTION_PARAMETER_PACK_P (r) = false;
-
                 /* Get the Ith type.  */
                 type = TREE_VEC_ELT (expanded_types, i);
 
+                // An argument of a function parameter pack is a function
+                // parameter pack if its type is also a pack. This can
+                // happen when instantiating templates with other template
+                // parameters.
+                FUNCTION_PARAMETER_PACK_P (r) = PACK_EXPANSION_P (type);
+
 		/* Rename the parameter to include the index.  */
 		DECL_NAME (r)
 		  = make_ith_pack_parameter_name (DECL_NAME (r), i);
@@ -10512,7 +10645,9 @@ tsubst_decl (tree t, tree args, tsubst_f
 	    DECL_INITIAL (r) = void_zero_node;
 	    gcc_assert (DECL_LANG_SPECIFIC (r) == NULL);
 	    retrofit_lang_decl (r);
-	    DECL_TEMPLATE_INFO (r) = build_template_info (t, args);
+
+            // FIXME: Do we need to attach constraints?
+	    DECL_TEMPLATE_INFO (r) = build_template_info (t, args, NULL_TREE);
 	  }
 	/* We don't have to set DECL_CONTEXT here; it is set by
 	   finish_member_declaration.  */
@@ -10743,7 +10878,12 @@ tsubst_decl (tree t, tree args, tsubst_f
 	    DECL_EXTERNAL (r) = 1;
 
 	    register_specialization (r, gen_tmpl, argvec, false, hash);
-	    DECL_TEMPLATE_INFO (r) = build_template_info (tmpl, argvec);
+
+            // Create new constraints for the result.
+            // TODO: Is this actually necessary?
+            tree cons = tsubst_constraint (DECL_TEMPLATE_CONSTRAINT (t), args);
+
+	    DECL_TEMPLATE_INFO (r) = build_template_info (tmpl, argvec, cons);
 	    SET_DECL_IMPLICIT_INSTANTIATION (r);
 	  }
 	else if (cp_unevaluated_operand)
@@ -12526,6 +12666,8 @@ tsubst_copy (tree t, tree args, tsubst_f
     case UNION_TYPE:
     case ENUMERAL_TYPE:
     case INTEGER_TYPE:
+    case REAL_TYPE:
+    case BOOLEAN_TYPE:
     case TEMPLATE_TYPE_PARM:
     case TEMPLATE_TEMPLATE_PARM:
     case BOUND_TEMPLATE_TEMPLATE_PARM:
@@ -14493,6 +14635,12 @@ tsubst_copy_and_build (tree t,
 	  /* If the original type was a reference, we'll be wrapped in
 	     the appropriate INDIRECT_REF.  */
 	  r = convert_from_reference (r);
+
+        // If the type of the argument is a pack expansion, then
+        // the parameter must also be expanded.
+        if (PACK_EXPANSION_P (TREE_TYPE (r)))
+          r = make_pack_expansion (r);
+
 	RETURN (r);
       }
 
@@ -15204,6 +15352,11 @@ fn_type_unification (tree fn,
       goto fail;
     }
 
+  // All is well so far. Now, check that the template constraints
+  // are satisfied.
+  if (!check_template_constraints (fn, targs))
+    return error_mark_node;
+
   /* All is well so far.  Now, check:
 
      [temp.deduct]
@@ -17709,6 +17862,13 @@ more_specialized_fn (tree pat1, tree pat
       lose2 = TREE_CODE (TREE_VALUE (args2)) == TYPE_PACK_EXPANSION;
     }
 
+  // All things still being equal, determine if one is more constrained.
+  if (lose1 == lose2)
+    {
+      lose1 = !more_constrained (pat1, pat2);
+      lose2 = !more_constrained (pat2, pat1);
+    }
+
   if (lose1 == lose2)
     return 0;
   else if (!lose1)
@@ -17736,12 +17896,11 @@ static int
 more_specialized_class (tree main_tmpl, tree pat1, tree pat2)
 {
   tree targs;
-  tree tmpl1, tmpl2;
   int winner = 0;
   bool any_deductions = false;
 
-  tmpl1 = TREE_TYPE (pat1);
-  tmpl2 = TREE_TYPE (pat2);
+  tree tmpl1 = TREE_TYPE (pat1);
+  tree tmpl2 = TREE_TYPE (pat2);
 
   /* Just like what happens for functions, if we are ordering between
      different class template specializations, we may encounter dependent
@@ -21101,16 +21260,6 @@ print_template_statistics (void)
 	   htab_collisions (type_specializations));
 }
 
-
-// Try to substitute ARGS into PARMS, returning the actual list of
-// arguments that have been substituted. If ARGS cannot be substituted,
-// return error_mark_node.
-tree
-substitute_template_parameters (tree parms, tree args)
-{
-  return coerce_template_parms (parms, args, NULL_TREE, tf_none, true, true);
-}
-
 // Substitute the template arguments ARGS into the requirement
 // expression REQS. Errors resulting from substitution are not
 // diagnosed.
@@ -21120,5 +21269,24 @@ instantiate_requirements (tree reqs, tre
   return tsubst_expr (reqs, args, tf_none, NULL_TREE, true);
 }
 
+// Create a new constraint info block by substituting ARGS into
+// the requirements of CONS.
+//
+// Note that this does not require evaluation.
+tree
+tsubst_constraint (tree cons, tree args)
+{
+  if (!cons)
+    return NULL_TREE;
+  tree reqs = instantiate_requirements (CI_REQUIREMENTS (cons), args);
+  return make_constraints (reqs);
+}
+
+// Substitute ARGS into REQS, creating a new expression.
+tree
+substitute_requirements (tree reqs, tree args)
+{
+  return tsubst_copy_and_build (reqs, args, tf_none, NULL_TREE, false, false);
+}
 
 #include "gt-cp-pt.h"
Index: cp/semantics.c
===================================================================
--- cp/semantics.c	(revision 199581)
+++ cp/semantics.c	(working copy)
@@ -2567,12 +2567,18 @@ finish_template_type_parm (tree aggr, tr
 tree
 finish_template_template_parm (tree aggr, tree identifier)
 {
-  tree decl = build_decl (input_location,
+  tree decl = build_lang_decl_loc (input_location,
 			  TYPE_DECL, identifier, NULL_TREE);
   tree tmpl = build_lang_decl (TEMPLATE_DECL, identifier, NULL_TREE);
   DECL_TEMPLATE_PARMS (tmpl) = current_template_parms;
   DECL_TEMPLATE_RESULT (tmpl) = decl;
   DECL_ARTIFICIAL (decl) = 1;
+
+  // Build template info and associate it with 
+  DECL_TEMPLATE_INFO (decl) = build_template_info (tmpl, 
+                                                   current_template_args (), 
+                                                   current_template_reqs);
+
   end_template_decl ();
 
   gcc_assert (DECL_TEMPLATE_PARMS (tmpl));
Index: cp/constraint.cc
===================================================================
--- cp/constraint.cc	(revision 199581)
+++ cp/constraint.cc	(working copy)
@@ -18,7 +18,7 @@ You should have received a copy of the G
 along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
 
-// Components for process constraints and evaluating constraints.
+// Components for processing constraints and evaluating constraints.
 
 #include "config.h"
 #include "system.h"
@@ -47,19 +47,29 @@ along with GCC; see the file COPYING3.
 //
 // Facilities for building and manipulating template requirements. 
 //
-// TODO: Simply assinging boolean_type_node to the result type of the expression
-// seems right thing for constraints, but in the long-term we might want to be
-// more flexible (i.e., allow some form of overload resolution?).
-
+// TODO: Simply assigning boolean_type_node to the result type of the 
+// expression seems right for constraints, but in the long-term we might want
+// to be more flexible (i.e., allow some form of overload resolution?).
+
+// Create a new logical node joining the subexpressions a and b.
+static inline tree
+join_requirements (tree_code c, tree a, tree b)
+{
+  gcc_assert (a != NULL_TREE && b != NULL_TREE);
+  gcc_assert (c == TRUTH_ANDIF_EXPR || c == TRUTH_ORIF_EXPR);
+  return build_min (c, boolean_type_node, a, b);
+}
 
 // Returns the conjunction of two requirements A and B, where A and B are
-// reduced terms in the constraints languaage. Returns NULL_TREE if either A or
+// reduced terms in the constraints language. Returns NULL_TREE if either A or
 // B are NULL_TREE.
 tree
 conjoin_requirements (tree a, tree b)
 {
-  if (a && b)
-    return build_min (TRUTH_ANDIF_EXPR, boolean_type_node, a, b);
+  if (a)
+    return b ? join_requirements (TRUTH_ANDIF_EXPR, a, b) : a;
+  else if (b)
+    return b;
   else
     return NULL_TREE;
 }
@@ -70,8 +80,10 @@ conjoin_requirements (tree a, tree b)
 tree
 disjoin_requirements (tree a, tree b)
 {
-  if (a && b)
-    return build_min (TRUTH_ORIF_EXPR, boolean_type_node, a, b);
+  if (a)
+    return b ? join_requirements (TRUTH_ORIF_EXPR, a, b) : a;
+  else if (b)
+    return b;
   else
     return NULL_TREE;
 }
@@ -82,7 +94,7 @@ disjoin_requirements (tree a, tree b)
 //
 // This facility is used to resolve constraint checks from requirement
 // expressions. A constraint check is a call to a constraint predicate:
-// a constexpr, nullary function teplate whose result can be converted
+// a constexpr, nullary function template whose result can be converted
 // to bool.
 //
 // The result of resolution is a pair (a list node) whose value is the
@@ -91,37 +103,39 @@ disjoin_requirements (tree a, tree b)
 
 namespace {
 
-// Returns true if the function decl F is a constraint predicate.
-// It must be a constexpr, nullary function with a boolean result
-// type.
-static bool
-is_constraint (tree f)
+
+// Returns true if the function decl F is a constraint predicate. It must be a
+// constexpr, nullary function with a boolean result type.
+static tree
+get_constraint_check (tree call)
 {
-  gcc_assert (TREE_CODE (f) == FUNCTION_DECL);
+  gcc_assert (TREE_CODE (call) == CALL_EXPR);
 
-  // A constraint is nullary.
-  if (DECL_ARGUMENTS (f))
-    return false;
+  // A constraint check can only be a template-id expression.
+  tree target = CALL_EXPR_FN (call);
+  if (TREE_CODE (target) != TEMPLATE_ID_EXPR)
+    return NULL_TREE;
 
-  // A constraint is declared constexpr
-  if (!DECL_DECLARED_CONSTEXPR_P (f))
-    return false;
+  // Get the constrant declaration. When the target is a template id, the first
+  // argument is always an overload containing a referenced function template.
+  tree decl = DECL_TEMPLATE_RESULT (OVL_FUNCTION (TREE_OPERAND (target, 0)));
 
-  // Whose result must be convertible to bool.
-  if (!can_convert (TREE_TYPE (TREE_TYPE (f)), boolean_type_node, tf_none))
-    return false;
+  // Fail if this is not a constraint.
+  if (!DECL_DECLARED_CONCEPT_P (decl))
+    return NULL_TREE;
 
-  // A constraint can only be checked if it is defined.
-  if (!DECL_SAVED_TREE (f))
-    return false;
+  // Get the arguments.
+  tree args = TREE_OPERAND (target, 1);
 
-  return true;
+  // Return the decl/args pair.
+  return tree_cons (args, DECL_TEMPLATE_RESULT (decl), NULL_TREE);
 }
 
-// Given an OVL set of constraint candidates, try to find a unique definition
-// satisfying the requirements of a constraint.
+
+// Given an overload set, try to find a unique definition that can be
+// instantiated by the template arguments.
 //
-// This function is not called for abitrary call expressions. In particul,
+// This function is not called for abitrary call expressions. In particular,
 // the call expression must be written with explicit template arguments
 // and no function arguments. For example:
 //
@@ -142,50 +156,52 @@ resolve_constraint_check (tree ovl, tree
       tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl));
 
       // Remember the candidate if we can deduce a substitution.
-      if (tree subst = substitute_template_parameters (parms, args))
+      if (tree subst = coerce_template_parms (parms, args, tmpl))
         if (subst != error_mark_node)
           cands = tree_cons (subst, DECL_TEMPLATE_RESULT (tmpl), cands);
     }
 
-  // If there are multiple candidates, then we have not found
-  // a unique definition.
-  if (TREE_CHAIN (cands))
+  // If we didn't find a unique candidate, then this is
+  // not a constraint check.
+  if (!cands || TREE_CHAIN (cands))
     return NULL_TREE;
 
-  if (!is_constraint (TREE_VALUE (cands)))
+  // Constraints must be declared concepts.
+  tree decl = TREE_VALUE (cands);
+  if (!DECL_DECLARED_CONCEPT_P (decl))
     return NULL_TREE;
 
+  // Concept declarations must have a corresponding definition.
+  //
+  // TODO: This should be part of the up-front checking for 
+  // a concept declaration.
+  if (!DECL_SAVED_TREE (decl))
+    {
+      error ("concept %q#D has no definition", decl);
+      return NULL;
+    }
+
   return cands;
 }
 
-// If the call express T is a check expression, return a singleton tree
-// list whose VALUE is the checked constraint predicate, and whose
-// PURPOSE contains substitution arguments for the constraint. If the 
-// call does not denote a check, return NULL_TREE.
-//
-// Note that a call expression is a check expression if it refers to a
-// unique, nullary function template via lightweight overload resolution.
+// Determine if the the call expression CALL is a constraint check, and
+// return the concept declaration and arguments being checked. If CALL
+// does not denote a constraint check, return NULL.
 tree
-maybe_constraint_check (tree call)
+resolve_constraint_check (tree call)
 {
   gcc_assert (TREE_CODE (call) == CALL_EXPR);
 
-  // A constraint check must be a call to a function template with 
-  // arguments given explicitly.
-  tree f = CALL_EXPR_FN (call);
-  if (TREE_CODE (f) != TEMPLATE_ID_EXPR)
-    return NULL_TREE;
-
-  // Also, make sure that there are no arguments to the call expression.
-  // If there are, then we are guaranteed that this is a regular call.
-  if (call_expr_nargs (call))
-    return NULL_TREE;
-
-  // Determine which constraint is actually referred to by the
-  // call expression.
-  tree tmpl = TREE_OPERAND (f, 0);
-  tree args = TREE_OPERAND (f, 1);
-  return resolve_constraint_check (tmpl, args);
+  // A constraint check must be only be a template-id expression.
+  tree target = CALL_EXPR_FN (call);
+  if (TREE_CODE (target) != TEMPLATE_ID_EXPR)
+    return NULL_TREE;
+
+  // Get the overload set and template arguments and try to
+  // resolve the target.
+  tree ovl = TREE_OPERAND (target, 0);
+  tree args = TREE_OPERAND (target, 1);
+  return resolve_constraint_check (ovl, args);
 }
   
 } // end namespace
@@ -360,13 +376,13 @@ reduce_logical (tree t)
 
 // Reduction rules for the call expression T.
 //
-// If T is a call to a constraint instantiate it's definition and
+// If T is a call to a constraint instantiate its definition and
 // recursively reduce its returned expression.
 tree
 reduce_call (tree t)
 {
   // Is the function call actually a constraint check?
-  tree check = maybe_constraint_check (t);
+  tree check = resolve_constraint_check (t);
   if (!check)
     return t;
 
@@ -406,8 +422,8 @@ reduce_template_id (tree t)
 {
   vec<tree, va_gc>* args = NULL;
   tree c = finish_call_expr (t, &args, true, false, 0);
-  error ("invalid requirement");
-  inform (input_location, "did you mean %qE", c);
+  error_at (EXPR_LOC_OR_HERE (t), "invalid requirement");
+  inform (EXPR_LOC_OR_HERE (t), "did you mean %qE", c);
   return NULL_TREE;
 }
 
@@ -441,7 +457,7 @@ reduce_stmt_list (tree stmts)
 } // end namespace
 
 
-// Reduce the requirement T into a logical formula written in terms of
+// Reduce the requirement REQS into a logical formula written in terms of
 // atomic propositions.
 tree
 reduce_requirements (tree reqs)
@@ -472,3 +488,182 @@ make_constraints (tree reqs)
     
   return (tree)cinfo;
 }
+
+namespace {
+
+inline tree
+get_type_constraints (tree t)
+{
+  return TYPE_TEMPLATE_CONSTRAINT (t);
+}
+
+inline tree
+get_decl_constraints (tree t)
+{
+  if (TREE_CODE (t) == TEMPLATE_DECL)
+    return get_decl_constraints (DECL_TEMPLATE_RESULT (t));
+  else
+    return DECL_TEMPLATE_CONSTRAINT (t);
+}
+
+} // end namespace
+
+// Return constraint info for the node T, regardless of the
+// kind of node.
+tree
+get_constraints (tree t)
+{
+  if (TYPE_P (t))
+    return get_type_constraints (t);
+  else if (DECL_P (t))
+    return get_decl_constraints (t);
+  else
+    gcc_unreachable ();
+  return false;
+}
+
+
+// Temporarily suppress template declaration processing for
+// the purpose of instantiating and evaluating constraints.
+//
+// The raison d'entre of this class is to prevent traits
+// and other template nodes from generating new expressions
+// during instantiation. 
+struct suppress_template_processing
+{
+  suppress_template_processing()
+    : pt (processing_template_decl)
+  { 
+    processing_template_decl = 0; 
+  }
+
+  ~suppress_template_processing()
+  {
+    processing_template_decl = pt;
+  }
+
+  int pt;
+};
+
+// Returns true if the non-dependent constraints are
+// satisfied, and false if not.
+static inline bool
+check_requirements (tree reqs)
+{
+  gcc_assert (!value_dependent_expression_p (reqs));
+
+  // TODO: Allow contextual conversion to bool.
+  return cxx_constant_value (reqs) == boolean_true_node;
+}
+
+// Instantiate and check the requirements.
+static inline bool
+check_dependent_requirements (tree reqs, tree args)
+{
+  // Get and instantiate the requirements. If substitution
+  // fails, then the constraints are not satisfied
+  reqs = instantiate_requirements (reqs, args);
+  if (reqs != error_mark_node)
+    return check_requirements (reqs);
+  else
+    return false;
+}
+
+// Check the instantiated declaration constraints.
+bool
+check_constraints (tree cinfo)
+{
+  if (!cinfo)
+    return true;
+  else
+    return check_requirements (CI_REQUIREMENTS (cinfo));
+}
+
+// Check the constraints in CINFO against the given ARGS, returning
+// true when the constraints are satisfied and false otherwise.
+bool 
+check_constraints (tree cinfo, tree args)
+{
+  suppress_template_processing guard;
+
+  // No constrants? Satisfied.
+  if (!cinfo)
+    return true;
+
+  // If we're inside a template, assume that constraints are
+  // satisfied.
+  //
+  // NOTE: This is a probably hook for separate checking.
+  if (uses_template_parms (args))
+    return true;
+
+  // Instantiate and check the requirements.
+  return check_dependent_requirements (CI_REQUIREMENTS (cinfo), args);
+}
+
+static inline bool
+check_type_constraints (tree t, tree args)
+{
+  return check_constraints (CLASSTYPE_TEMPLATE_CONSTRAINT (t), args);
+}
+
+static inline bool
+check_decl_constraints (tree t, tree args)
+{
+  if (TREE_CODE (t) == TEMPLATE_DECL)
+    return check_decl_constraints (DECL_TEMPLATE_RESULT (t), args);
+  else
+    return check_constraints (DECL_TEMPLATE_CONSTRAINT (t), args);
+}
+
+// Check the template's constraints for the specified arguments,
+// returning true if the constraints are satisfied and false
+// otherwise.
+bool
+check_template_constraints (tree t, tree args)
+{
+  return check_constraints (get_constraints (t), args);
+}
+
+// Returns true when A and B are equivlent constraints.
+bool
+equivalent_constraints (tree a, tree b)
+{
+  return subsumes (a, b) && subsumes (b, a);
+}
+
+// Returns true if the template declarations A and B have equivalent
+// constraints. This is the case when A's constraints subsume B's and
+// when B's also constrain A's.
+bool 
+equivalently_constrained (tree a, tree b)
+{
+  gcc_assert (TREE_CODE (a) == TREE_CODE (b));
+  return equivalent_constraints (get_constraints (a), get_constraints (b));
+}
+
+// Returns true when the A contains more atomic properties than B.
+bool
+more_constraints (tree a, tree b)
+{
+  return subsumes (a, b);
+}
+
+// Returns true when the template declaration A's constraints subsume
+// those of the template declaration B.
+bool 
+more_constrained (tree a, tree b)
+{
+  gcc_assert (TREE_CODE (a) == TREE_CODE (b));
+  return more_constraints (get_constraints (a), get_constraints (b));
+}
+
+
+// -------------------------------------------------------------------------- //
+// Constraint Diagnostics
+
+void
+diagnose_constraint_failure (location_t loc, tree tmpl, tree args)
+{
+  error_at (loc, "constraints not satisfied");
+}
Index: cp/parser.c
===================================================================
--- cp/parser.c	(revision 199581)
+++ cp/parser.c	(working copy)
@@ -2212,8 +2212,6 @@ static void cp_parser_label_declaration
 
 static tree cp_parser_requires_clause
   (cp_parser *);
-static tree cp_parser_requires_clause_opt
-  (cp_parser *);
 
 /* Transactional Memory Extensions */
 
@@ -2418,52 +2416,21 @@ static cp_declarator * cp_parser_make_in
  (enum tree_code, tree, cp_cv_quals, cp_declarator *, tree);
 
 
-// A helper type for declaring rule pointers.
-typedef tree (*cp_rule)(cp_parser *);
-
 
 // -------------------------------------------------------------------------- //
-// Optional Parsing
+// Unevaluated Operand Guard
 //
-// The following functions will optionally parse a rule if the corresponding
-// criteria is satisfied. If not, the parser returns NULL indicating that
-// the optional parse taken.
-//
-// Note that an optional parse returning error_mark_node means that the
-// optional parse was taken, but failed due to some error in the following
-// token stream. 
-
-// Optionally parse RULE if the next token type matches TYPE.
-template<typename Rule>
-static inline tree
-cp_parser_optional_if_token (cp_parser *parser, Rule rule, cpp_ttype type)
+// Implementation of an RAII helper for unevaluated operand parsing.
+cp_unevaluated::cp_unevaluated ()
 {
-  if (cp_lexer_next_token_is (parser->lexer, type))
-    return rule (parser);
-  else
-    return NULL_TREE;
-}
-
-// Optionally parse RULE if the next token type does not match TYPE.
-template<typename Rule>
-static inline tree
-cp_parser_optional_if_not_token (cp_parser *parser, Rule rule, cpp_ttype type)
-{
-  if (cp_lexer_next_token_is_not (parser->lexer, type))
-    return rule (parser);
-  else
-    return NULL_TREE;
+  ++cp_unevaluated_operand;
+  ++c_inhibit_evaluation_warnings;
 }
 
-// Optionally parse RULE if the next token is the keyword KW.
-template<typename Rule>
-static inline tree
-cp_parser_optional_if_keyword (cp_parser *parser, Rule rule, rid kw)
+cp_unevaluated::~cp_unevaluated ()
 {
-  if (cp_lexer_next_token_is_keyword (parser->lexer, kw))
-    return rule (parser);
-  else
-    return NULL_TREE;
+  --c_inhibit_evaluation_warnings;
+  --cp_unevaluated_operand;
 }
 
 // -------------------------------------------------------------------------- //
@@ -12817,10 +12784,11 @@ cp_parser_type_parameter (cp_parser* par
 	cp_parser_require (parser, CPP_GREATER, RT_GREATER);
 	
         // If template requirements are present, parse them.
-        if (flag_concepts)
+          if (flag_concepts && 
+              cp_lexer_next_token_is_keyword (parser->lexer, RID_REQUIRES))
           {
             tree reqs = release (current_template_reqs);
-            if (tree r = cp_parser_requires_clause_opt (parser))
+            if (tree r = cp_parser_requires_clause (parser))
               reqs = conjoin_requirements (reqs, r);
             current_template_reqs = finish_template_requirements (reqs);
           }
@@ -19885,12 +19853,14 @@ cp_parser_member_declaration (cp_parser*
 
               // If we're looking at a function declaration, then a requires
               // clause may follow the declaration.
-              tree saved_template_reqs = current_template_reqs;
-              if (flag_concepts 
-                  && function_declarator_p (declarator)
-                  && cp_lexer_next_token_is_keyword (parser->lexer, RID_REQUIRES))
-                {
-                  if (tree r = cp_parser_requires_clause_opt (parser))
+              tree saved_template_reqs = release (current_template_reqs);
+              if (flag_concepts && 
+                  function_declarator_p (declarator) &&
+                  cp_lexer_next_token_is_keyword (parser->lexer, RID_REQUIRES))
+                {
+                  // Because this is a non-template member, there are no
+                  // template requirements to conjoin.
+                  if (tree r = cp_parser_requires_clause (parser))
                     current_template_reqs = finish_template_requirements (r);
                 }
 
@@ -21446,16 +21416,6 @@ cp_parser_requires_clause (cp_parser *pa
   return expr;
 }
 
-// Parse an optional template requirement, returning NULL_TREE if no
-// 'requires' clause is found. The template requirement is required to
-// be a constant expression.
-static tree
-cp_parser_requires_clause_opt (cp_parser* parser)
-{
-  cp_rule p = cp_parser_requires_clause;
-  return cp_parser_optional_if_keyword (parser, p, RID_REQUIRES);
-}
-
 /* Support Functions */
 
 /* Looks up NAME in the current scope, as given by PARSER->SCOPE.
@@ -22320,10 +22280,11 @@ cp_parser_template_declaration_after_exp
   ++parser->num_template_parameter_lists;
 
   // Manage template requirements
-  if (flag_concepts)
+  if (flag_concepts &&
+      cp_lexer_next_token_is_keyword (parser->lexer, RID_REQUIRES))
     {
       tree reqs = release (current_template_reqs);
-      if (tree r = cp_parser_requires_clause_opt (parser))
+      if (tree r = cp_parser_requires_clause (parser))
         reqs = conjoin_requirements (reqs, r);
       current_template_reqs = finish_template_requirements (reqs);
     }
Index: cp/call.c
===================================================================
--- cp/call.c	(revision 199411)
+++ cp/call.c	(working copy)
@@ -449,7 +449,8 @@ enum rejection_reason_code {
   rr_arg_conversion,
   rr_bad_arg_conversion,
   rr_template_unification,
-  rr_invalid_copy
+  rr_invalid_copy,
+  rr_constraint_failure
 };
 
 struct conversion_info {
@@ -709,6 +710,15 @@ invalid_copy_with_fn_template_rejection
   return r;
 }
 
+static struct rejection_reason *
+template_constraint_failure (tree tmpl, tree targs)
+{
+  struct rejection_reason *r = alloc_rejection (rr_constraint_failure);
+  r->u.template_instantiation.tmpl = tmpl;
+  r->u.template_instantiation.targs = targs;
+  return r;
+}
+
 /* Dynamically allocate a conversion.  */
 
 static conversion *
@@ -1858,6 +1868,25 @@ add_function_candidate (struct z_candida
   len = vec_safe_length (args) - skip + (first_arg != NULL_TREE ? 1 : 0);
   convs = alloc_conversions (len);
 
+  // Viable functions
+  //
+  // Functions whose constraints are not satisfied are non-viable.
+  //
+  // This only happens with constrained non-template members, which
+  // we've currently disabled.
+  if (DECL_USE_TEMPLATE (fn))
+    {
+      tree cons = DECL_TEMPLATE_CONSTRAINT (fn);
+      if (!check_constraints (cons))
+        {
+          // TODO: Fail for the right reason.
+          reason = template_unification_error_rejection ();
+          viable = false;
+          goto out;          
+        }
+    }
+
+
   /* 13.3.2 - Viable functions [over.match.viable]
      First, to be a viable function, a candidate function shall have enough
      parameters to agree in number with the arguments in the list.
@@ -2924,8 +2953,10 @@ add_template_candidate_real (struct z_ca
 
   if (fn == error_mark_node)
     {
+      if (!check_template_constraints (tmpl, targs))
+          reason = template_constraint_failure (tmpl, targs);
+      else if (errorcount+sorrycount == errs)
       /* Don't repeat unification later if it already resulted in errors.  */
-      if (errorcount+sorrycount == errs)
 	reason = template_unification_rejection (tmpl, explicit_targs,
 						 targs, args_without_in_chrg,
 						 nargs_without_in_chrg,
@@ -2977,6 +3008,7 @@ add_template_candidate_real (struct z_ca
 				   first_arg, arglist, access_path,
 				   conversion_path, flags, complain);
   if (DECL_TI_TEMPLATE (fn) != tmpl)
+    {
     /* This situation can occur if a member template of a template
        class is specialized.  Then, instantiate_template might return
        an instantiation of the specialization, in which case the
@@ -2994,7 +3026,9 @@ add_template_candidate_real (struct z_ca
        for this will point at template <class T> template <> S<T>::f(int),
        so that we can find the definition.  For the purposes of
        overload resolution, however, we want the original TMPL.  */
-    cand->template_decl = build_template_info (tmpl, targs);
+      tree cons = tsubst_constraint (DECL_TEMPLATE_CONSTRAINT (fn), targs);
+      cand->template_decl = build_template_info (tmpl, targs, cons);
+    }
   else
     cand->template_decl = DECL_TEMPLATE_INFO (fn);
   cand->explicit_targs = explicit_targs;
@@ -3243,6 +3277,13 @@ print_z_candidate (location_t loc, const
 		  "  a constructor taking a single argument of its own "
 		  "class type is invalid");
 	  break;
+        case rr_constraint_failure:
+          {
+            tree tmpl = r->u.template_instantiation.tmpl;
+            tree args = r->u.template_instantiation.targs;
+            diagnose_constraint_failure (cloc, tmpl, args);
+          }
+          break;
 	case rr_none:
 	default:
 	  /* This candidate didn't have any issues or we failed to
@@ -8353,6 +8394,22 @@ add_warning (struct z_candidate *winner,
   winner->warnings = cw;
 }
 
+// Returns the template declaration associated with the candidate
+// function. For actual templates, this is directly associated
+// with the candidate. For temploids, we return the template
+// associated with the specialization.
+static inline tree
+get_actual_template (struct z_candidate *cand)
+{
+ tree r = cand->template_decl;
+  tree d = cand->fn;
+  if (!r && DECL_P (d) && DECL_USE_TEMPLATE (d))
+    r = DECL_TI_TEMPLATE (d);
+  if (r && TREE_CODE (r) == TEMPLATE_INFO)
+    r = TI_TEMPLATE (r);
+  return r;
+}
+
 /* Compare two candidates for overloading as described in
    [over.match.best].  Return values:
 
@@ -8369,6 +8426,10 @@ joust (struct z_candidate *cand1, struct
   size_t i;
   size_t len;
 
+  // Get the actual template decls associated with the candidates.
+  tree tmpl1 = get_actual_template (cand1);
+  tree tmpl2 = get_actual_template (cand2);
+
   /* Candidates that involve bad conversions are always worse than those
      that don't.  */
   if (cand1->viable > cand2->viable)
@@ -8571,16 +8632,14 @@ joust (struct z_candidate *cand1, struct
      more specialized than the template for F2 according to the partial
      ordering rules.  */
 
-  if (cand1->template_decl && cand2->template_decl)
+  if (tmpl1 && tmpl2)
     {
-      winner = more_specialized_fn
-	(TI_TEMPLATE (cand1->template_decl),
-	 TI_TEMPLATE (cand2->template_decl),
 	 /* [temp.func.order]: The presence of unused ellipsis and default
 	    arguments has no effect on the partial ordering of function
 	    templates.   add_function_candidate() will not have
 	    counted the "this" argument for constructors.  */
-	 cand1->num_convs + DECL_CONSTRUCTOR_P (cand1->fn));
+      int nparms = cand1->num_convs + DECL_CONSTRUCTOR_P (cand1->fn);
+      winner = more_specialized_fn (tmpl1, tmpl2, nparms);
       if (winner)
 	return winner;
     }
Index: cp/cp-tree.h
===================================================================
--- cp/cp-tree.h	(revision 199581)
+++ cp/cp-tree.h	(working copy)
@@ -800,7 +800,7 @@ struct GTY(()) tree_constraint_info {
 
 // Returns true iff T is non-null and represents constraint info.
 inline tree_constraint_info *
-constraint_info_p (tree t)
+check_constraint_info (tree t)
 {
   if (t && TREE_CODE (t) == CONSTRAINT_INFO)
     return (tree_constraint_info *)t;
@@ -809,7 +809,7 @@ constraint_info_p (tree t)
 
 // Returns true iff T is non-null and is a template info object.
 inline tree_template_info *
-template_info_p (tree t)
+check_template_info (tree t)
 {
   if (t && TREE_CODE (t) == TEMPLATE_INFO)
     return (tree_template_info *)t;
@@ -818,34 +818,34 @@ template_info_p (tree t)
 
 // Get the spelling of the requirements
 #define CI_SPELLING(NODE) \
-  check_nonnull (constraint_info_p (NODE))->spelling
+  check_nonnull (check_constraint_info (NODE))->spelling
 
 // Get the reduced requirements associated with the constraint info node
 #define CI_REQUIREMENTS(NODE) \
-  check_nonnull (constraint_info_p (NODE))->requirements
+  check_nonnull (check_constraint_info (NODE))->requirements
 
 // Get the set of assumptions associated with the constraint info node
 #define CI_ASSUMPTIONS(NODE) \
-  check_nonnull (constraint_info_p (NODE))->assumptions
+  check_nonnull (check_constraint_info (NODE))->assumptions
 
 // Get the constraint associated with the template info NODE.
 #define TI_CONSTRAINT(NODE) \
-  check_nonnull (template_info_p (NODE))->constraint
+  check_nonnull (check_template_info (NODE))->constraint
 
 // Get the spelling of constraints associated
 #define TI_SPELLING(NODE) \
-  check_nonnull (constraint_info_p (TI_CONSTRAINT (NODE)))->spelling
+  check_nonnull (check_constraint_info (TI_CONSTRAINT (NODE)))->spelling
 
 // Get requirements associated with the template info NODE.
 #define TI_REQUIREMENTS(NODE) \
-  check_nonnull (constraint_info_p (TI_CONSTRAINT (NODE)))->requirements
+  check_nonnull (check_constraint_info (TI_CONSTRAINT (NODE)))->requirements
 
 // Get assumptions associated with the template info NODE.
 #define TI_ASSUMPTIONS(NODE) \
-  check_nonnull (constraint_info_p (TI_CONSTRAINT (NODE)))->assumptions
+  check_nonnull (check_constraint_info (TI_CONSTRAINT (NODE)))->assumptions
 
 // Access constraint information for C++ declarations. Note that
-// NODE must be a lang-decl.
+// NODE must have DECL_LANG_SPECIFIC.
 #define DECL_TEMPLATE_CONSTRAINT(NODE) \
   TI_CONSTRAINT (DECL_TEMPLATE_INFO (NODE))
 
@@ -4409,6 +4409,15 @@ extern int cp_unevaluated_operand;
 extern tree cp_convert_range_for (tree, tree, tree);
 extern bool parsing_nsdmi (void);
 
+// An RAII class used to inhibit the evaluation of operands during parsing
+// and template isntantiation. Evaluation warnings are also inhibited.
+class cp_unevaluated
+{
+public:
+  cp_unevaluated ();
+  ~cp_unevaluated ();
+};
+
 /* in pt.c  */
 
 /* These values are used for the `STRICT' parameter to type_unification and
@@ -4421,6 +4430,18 @@ typedef enum unification_kind_t {
   DEDUCE_EXACT
 } unification_kind_t;
 
+// An RAII class used to create a new pointer map for local
+// specializations. When the stack goes out of scope, the
+// previous pointer map is restored.
+class local_specialization_stack
+{
+public:
+  local_specialization_stack ();
+  ~local_specialization_stack ();
+
+  struct pointer_map_t *saved;
+};
+
 /* in class.c */
 
 extern int current_class_depth;
@@ -5652,7 +5673,7 @@ extern tree get_template_argument_pack_e
 extern tree get_function_template_decl		(const_tree);
 extern tree resolve_nondeduced_context		(tree);
 extern hashval_t iterative_hash_template_arg (tree arg, hashval_t val);
-extern tree substitute_template_parameters      (tree, tree);
+extern tree coerce_template_parms               (tree, tree, tree);
 extern tree substitute_requirements             (tree, tree);
 extern tree instantiate_requirements            (tree, tree);
 extern tree tsubst_constraint                   (tree, tree);
@@ -6250,6 +6271,16 @@ extern tree conjoin_requirements
 extern tree disjoin_requirements                (tree, tree);
 extern tree reduce_requirements                 (tree);
 extern tree make_constraints                    (tree);
+extern tree get_constraints                     (tree);
+extern bool check_constraints                   (tree);
+extern bool check_constraints                   (tree, tree);
+extern bool check_template_constraints          (tree, tree);
+extern tree subst_template_constraints          (tree, tree);
+extern bool equivalent_constraints              (tree, tree);
+extern bool equivalently_constrained            (tree, tree);
+extern bool more_constraints                    (tree, tree);
+extern bool more_constrained                    (tree, tree);
+extern void diagnose_constraint_failure         (location_t, tree, tree);
 
 /* in logic.cc */
 extern tree decompose_assumptions               (tree);
Index: cp/class.c
===================================================================
--- cp/class.c	(revision 199411)
+++ cp/class.c	(working copy)
@@ -934,6 +934,20 @@ modify_vtable_entry (tree t,
     }
 }
 
+// Returns true if NEW_FN and OLD_FN are non-template member functions
+// of a class template with with different constraints. The types of the 
+// functions are assumed to be equivalent.
+static inline bool
+are_constrained_member_overloads (tree new_fn, tree old_fn) 
+{
+  // Non-temploids cannot be constrained.
+  if (!DECL_TEMPLOID_INSTANTIATION (new_fn) && 
+      !DECL_TEMPLOID_INSTANTIATION (old_fn))
+    return false;
+  else 
+    return !equivalently_constrained (new_fn, old_fn);
+}
+
 \f
 /* Add method METHOD to class TYPE.  If USING_DECL is non-null, it is
    the USING_DECL naming METHOD.  Returns true if the method could be
@@ -1140,6 +1154,8 @@ add_method (tree type, tree method, tree
 		/* Defer to the local function.  */
 		return false;
 	    }
+          else if (are_constrained_member_overloads (fn, method))
+            continue;
 	  else
 	    {
 	      error ("%q+#D cannot be overloaded", method);
Index: cp/decl.c
===================================================================
--- cp/decl.c	(revision 199581)
+++ cp/decl.c	(working copy)
@@ -1215,6 +1215,23 @@ validate_constexpr_redeclaration (tree o
   return false;
 }
 
+// Returns true when NEW_DECL is a function template declaration that 
+// is constrained differently from OLD_DECL.
+static inline bool
+are_constrained_overloads (tree new_tmpl, tree old_tmpl) 
+{
+  if (!DECL_FUNCTION_TEMPLATE_P (new_tmpl))
+    return false;
+  if (!DECL_FUNCTION_TEMPLATE_P (old_tmpl))
+    return false;
+
+  // Note that new_decl isn't fully formed at the point we
+  // compare, so we have to use the current requirements.
+  tree old_cons = get_constraints (old_tmpl);
+  return !equivalent_constraints (old_cons, current_template_reqs);
+}
+
+
 #define GNU_INLINE_P(fn) (DECL_DECLARED_INLINE_P (fn)			\
 			  && lookup_attribute ("gnu_inline",		\
 					       DECL_ATTRIBUTES (fn)))
@@ -1567,6 +1584,19 @@ duplicate_decls (tree newdecl, tree oldd
        specialize one of its methods.  This situation is valid, but
        the declarations must be merged in the usual way.  */
     return NULL_TREE;
+  else if (are_constrained_overloads (newdecl, olddecl))
+    {
+      // If newdecl and olddecl are function templates with the 
+      // same type but different constraints, then they cannot be 
+      // duplicate declarations. However, if the olddecl is declared
+      // as a concept, then the program is ill-formed.
+      if (DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (olddecl)))
+        {
+          error ("cannot specialize concept %q#D", olddecl);
+          return error_mark_node;
+        }
+      return NULL;
+    }
   else if (TREE_CODE (newdecl) == FUNCTION_DECL
 	   && ((DECL_TEMPLATE_INSTANTIATION (olddecl)
 		&& !DECL_USE_TEMPLATE (newdecl))
@@ -7316,24 +7346,16 @@ check_static_quals (tree decl, cp_cv_qua
 }
 
 // Check that FN takes no arguments and returns bool.
-static bool
+static void
 check_concept_fn (tree fn)
 {
   // A constraint is nullary.
   if (DECL_ARGUMENTS (fn))
-    {
-      error ("concept %q#D declared with function arguments", fn);
-      return false;
-    }
+    error ("concept %q#D declared with function parameters", fn);
 
   // The result type must be convertible to bool.
   if (!can_convert (TREE_TYPE (TREE_TYPE (fn)), boolean_type_node, tf_none))
-    {
       error ("concept %q#D result must be convertible to bool", fn);
-      return false;
-    }
-
-  return true;
 }
 
 /* CTYPE is class type, or null if non-class.
@@ -7467,7 +7489,7 @@ grokfndecl (tree ctype,
 	      fns = TREE_OPERAND (fns, 1);
 	    }
 	  gcc_assert (identifier_p (fns) || TREE_CODE (fns) == OVERLOAD);
-	  DECL_TEMPLATE_INFO (decl) = build_template_info (fns, args);
+	  DECL_TEMPLATE_INFO (decl) = build_template_info (fns, args, NULL_TREE);
 
 	  for (t = TYPE_ARG_TYPES (TREE_TYPE (decl)); t; t = TREE_CHAIN (t))
 	    if (TREE_PURPOSE (t)
@@ -7593,8 +7615,7 @@ grokfndecl (tree ctype,
   if (inlinep & 4)
     {
       DECL_DECLARED_CONCEPT_P (decl) = true;
-      if (!check_concept_fn (decl))
-        return NULL_TREE;
+      check_concept_fn (decl);
     }
 
   DECL_EXTERNAL (decl) = 1;
@@ -14394,6 +14415,7 @@ cp_tree_node_structure (union lang_tree_
     case TRAIT_EXPR:		return TS_CP_TRAIT_EXPR;
     case LAMBDA_EXPR:		return TS_CP_LAMBDA_EXPR;
     case TEMPLATE_INFO:		return TS_CP_TEMPLATE_INFO;
+    case CONSTRAINT_INFO:       return TS_CP_CONSTRAINT_INFO;
     case USERDEF_LITERAL:	return TS_CP_USERDEF_LITERAL;
     default:			return TS_CP_GENERIC;
     }
Index: cp/ptree.c
===================================================================
--- cp/ptree.c	(revision 199411)
+++ cp/ptree.c	(working copy)
@@ -223,6 +223,14 @@ cxx_print_xnode (FILE *file, tree node,
 	  fprintf (file, "pending_template");
 	}
       break;
+    case CONSTRAINT_INFO:
+      {
+        tree_constraint_info *cinfo = (tree_constraint_info *)node;
+        print_node (file, "requirements", cinfo->requirements, indent+4);
+        if (cinfo->assumptions)
+          print_node_brief (file, "assumptions", cinfo->assumptions, indent+4);
+        break;
+      }    
     case ARGUMENT_PACK_SELECT:
       print_node (file, "pack", ARGUMENT_PACK_SELECT_FROM_PACK (node),
 		  indent+4);

Re: [c++-concepts] code review

[Jason Merrill]

On 06/12/2013 11:53 AM, Gabriel Dos Reis wrote:
> I am still surprised though that we don't generate TEMPLATE_DECLs for
> partial instantiations (since they are still morally templates.)

Yes, we should.

Jason

Re: [c++-concepts] code review

[Gabriel Dos Reis]

On Mon, Jun 10, 2013 at 2:30 PM, Jason Merrill <jason@redhat.com> wrote:
> On 06/08/2013 09:34 AM, Andrew Sutton wrote:
>>
>> I think I previously put constraint_info in lang_decl_min, right next
>> to template_info no less. It was easy to manage there, and initialized
>> as part of build_template_decl. But this obviously doesn't work for
>> partial specializations unless they get template_decls.
>
>
> Right.  And we would want it to be specific to template_decls, not all decls
> that use lang_decl_min.

yes, exactly my feedback on the original implementation.

I am still surprised though that we don't generate TEMPLATE_DECLs for
partial instantiations (since they
are still morally templates.)

-- Gaby

Re: [c++-concepts] code review

[Jason Merrill]

On 06/11/2013 11:09 AM, Andrew Sutton wrote:
>> And you need to do this even when the call is type-dependent?
>
> Yes. Especially when the call is type-dependent. That's how I generate
> the constraint sets, which are used to determine the most constrained
> template during overload resolution.

Ah, that makes sense.  Then I guess what you're doing in 
resolve_constraint_check is what you want; since the function takes no 
parameters and returns bool, there's no substitution to do into the 
function type, so SFINAE doesn't matter.  I'd just ask again to rename 
substitute_template_parameters; perhaps just calling it 
coerce_template_parms makes sense.  And also please pass tmpl down to 
the is_decl parameter.

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

> And you need to do this even when the call is type-dependent?

Yes. Especially when the call is type-dependent. That's how I generate
the constraint sets, which are used to determine the most constrained
template during overload resolution.

Re: [c++-concepts] code review

[Jason Merrill]

On 06/11/2013 10:49 AM, Andrew Sutton wrote:
>>> After investigating, neither call_expr nor resolve_nondeduced_context
>>> do what I need. I need a resolution of a call expression that does not
>>> return overload sets, especially in the case where the initial call
>>> expression is already dependent.
>>
>> Does this have to do with restrictions on overloading of concept functions?
>
> Very much so. I need a single function because I'm inlining its body
> at the call site.

And you need to do this even when the call is type-dependent?

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

>> After investigating, neither call_expr nor resolve_nondeduced_context
>> do what I need. I need a resolution of a call expression that does not
>> return overload sets, especially in the case where the initial call
>> expression is already dependent.
>
>
> Does this have to do with restrictions on overloading of concept functions?


Very much so. I need a single function because I'm inlining its body
at the call site.

Andrew

Re: [c++-concepts] code review

[Jason Merrill]

On 06/11/2013 09:45 AM, Andrew Sutton wrote:
> After investigating, neither call_expr nor resolve_nondeduced_context
> do what I need. I need a resolution of a call expression that does not
> return overload sets, especially in the case where the initial call
> expression is already dependent.

Does this have to do with restrictions on overloading of concept functions?

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

>> I think I previously put constraint_info in lang_decl_min, right next
>> to template_info no less. It was easy to manage there, and initialized
>> as part of build_template_decl. But this obviously doesn't work for
>> partial specializations unless they get template_decls.
>
>
> Right.  And we would want it to be specific to template_decls, not all decls
> that use lang_decl_min.

I'll have to check. I can't remember off the top of my head if
non-template member functions have a corresponding template_decl. I
think they do.

auto declarations will also get constraints in the future.


>> On the topic of logic.cc, I'm plan on rewriting this module to use a
>> set instead of lists. There will be some pretty substantial changes to
>> the internal interfaces.
>>
>> Would it be reasonable to commit this now (since it works correctly),
>> and plan to rewrite it in the near future?
>
>
> OK.

I was experimenting with this over the weekend. I'm just going to
rewrite it now, but without the optimizations I alluded to earlier.
They didn't pan out the way I'd have liked.

>> I think I see where the problem is. cp_parser_requires_clause is
>> parsed non-optionally in a requires expression, but that's not
>> included in the patch. I factored out the explicit parsing (hence the
>> assertion) from the optional parsing.
>
>
> The two situations seem pretty similar; you don't decide you're parsing a
> requires expression until you see the keyword either, right?
>
> The usual pattern in the parser is for a function to try to parse a
> particular construct and then return NULL_TREE if we're looking at something
> else; it seems most straightforward to do that in this case as well.

Yes, but I wasn't testing for the keyword prior to the call to
cp_parser_requires_clause_opt. That's not quite true, I was in for
member functions, but that was an oversight.

Changing to test for requires won't be hard.

>> What is the main entry point to overload resolution?
>
>
> Perhaps finish_call_expr is what you want.

After investigating, neither call_expr nor resolve_nondeduced_context
do what I need. I need a resolution of a call expression that does not
return overload sets, especially in the case where the initial call
expression is already dependent.

resolve_nondeduced_context looks like a good candidate to extend, but
I hesitate to modify since it's used in a number of different places,
and winnowing the overload set may not be appropriate in those
contexts.

Re: [c++-concepts] code review

[Lawrence Crowl]

On 6/10/13, Diego Novillo <dnovillo@google.com> wrote:
> On 2013-06-09 20:34 , Gabriel Dos Reis wrote:
> > So, my advice is for GCC source code to forget about the <cxxx>
> > headers for the most part.  I can see an instance where <cmath>
> > or <cstring> would make a difference but given point (1) above,
> > no it doesn't.  Just use the traditional <xxx.h> headers and
> > be done with it.
> >
> > Maybe I should have included this in our C++ coding standards,
> > but I don't know how Benjamin, Lawrence, and Diego fee about it.
>
> Sounds reasonable to me.

Me too.  The split in headers always felt excessively artifical
to me.

-- 
Lawrence Crowl

Re: [c++-concepts] code review

[Jason Merrill]

On 06/08/2013 09:34 AM, Andrew Sutton wrote:
> I think I previously put constraint_info in lang_decl_min, right next
> to template_info no less. It was easy to manage there, and initialized
> as part of build_template_decl. But this obviously doesn't work for
> partial specializations unless they get template_decls.

Right.  And we would want it to be specific to template_decls, not all 
decls that use lang_decl_min.

> I'd be okay committing the current design with the caveat that it may
> need to be rewritten in the not-so-distant future. I've already
> written the other other way two or three times, so I'm familiar with
> those changes.

Yeah, that sounds fine.

> On the topic of logic.cc, I'm plan on rewriting this module to use a
> set instead of lists. There will be some pretty substantial changes to
> the internal interfaces.
>
> Would it be reasonable to commit this now (since it works correctly),
> and plan to rewrite it in the near future?

OK.

> I think I see where the problem is. cp_parser_requires_clause is
> parsed non-optionally in a requires expression, but that's not
> included in the patch. I factored out the explicit parsing (hence the
> assertion) from the optional parsing.

The two situations seem pretty similar; you don't decide you're parsing 
a requires expression until you see the keyword either, right?

The usual pattern in the parser is for a function to try to parse a 
particular construct and then return NULL_TREE if we're looking at 
something else; it seems most straightforward to do that in this case as 
well.

> What is the main entry point to overload resolution?

Perhaps finish_call_expr is what you want.

Jason

Re: [c++-concepts] code review

[Jason Merrill]

On 06/09/2013 08:49 PM, Gabriel Dos Reis wrote:
> If you put the function in an unnamed namespace
> you would expect GCC to treat is as if it was of internal
> linkage for many purposes including automatic inlining, but
> it doesn't:-(   For example, you lose the "defined but not used
> warning", and the "used but not defined" warnings :-((

Indeed, G++ currently only gives those warnings for things declared 
'static', but that's trivial to fix, and shouldn't affect other things 
in the compiler.

Jason

Re: [c++-concepts] code review

[Jason Merrill]

On 06/09/2013 08:34 PM, Gabriel Dos Reis wrote:
> I strongly suggest prefering <stdlib.h> over <cstdlib> for GCC source code
> base.

The problem is that including <stdlib.h> does not define 
_GLIBCXX_CSTDLIB, so if one of the C++ library headers includes 
<cstdlib> the contents are added then, but by that point e.g. "malloc" 
is poisoned, so the mentions of malloc in cstdlib cause errors.

Because we are poisoning these names, we need to #include *both* headers 
in system.h.

Jason

Re: [c++-concepts] code review

[Diego Novillo]

On 2013-06-09 20:34 , Gabriel Dos Reis wrote:
> So, my advice is for GCC source code to forget about the <cxxx>
> headers for the  most part.  I can see an instance where <cmath> or <cstring>
> would make a difference but given point (1) above, no it doesn't.
> Just use the traditional <xxx.h> headers and be done with it.
>
> Maybe I should have included this in our C++ coding standards, but
> I don't know how Benjamin, Lawrence, and Diego fee about it.

Sounds reasonable to me.


Diego.

Re: [c++-concepts] code review

[Gabriel Dos Reis]

On Sat, Jun 8, 2013 at 8:34 AM, Andrew Sutton <andrew.n.sutton@gmail.com> wrote:

>> template<term_list& (*proj)(proof_goal&)>
>> tree
>> extract_goals (proof_state& s)
>> ...
>>  return extract_goals<assumptions>(s);
>>
>> but I suppose STL style is OK, too.
>
>
> Huh. I didn't realize that could be inlined. Neat.

We do -- we have been doing so for quite some time
now, including devirtualization and inlining of functions
with internal linkage.

The reason why I tend to prefer the function argument
style over template argument-style is where I don't
want to specify everything, but rather prefer type deduction.
Which in my case is almost aways.

There is one thing though: C++03 does not allow using a
function with internal linkage or no linkage as template
arguments.  If you put the function in an unnamed namespace
you would expect GCC to treat is as if it was of internal
linkage for many purposes including automatic inlining, but
it doesn't :-(  For example, you lose the "defined but not used
warning", and the "used but not defined" warnings :-((

-- Gaby

Re: [c++-concepts] code review

[Gabriel Dos Reis]

On Sun, Jun 9, 2013 at 3:34 PM, Oleg Endo <oleg.endo@t-online.de> wrote:
> On Thu, 2013-06-06 at 16:29 -0400, Jason Merrill wrote:
>> On 06/06/2013 01:47 PM, Andrew Sutton wrote:
>> > I never did understand why this happens. Compiling with GCC-4.6, I get
>> > these errors originating in logic.cc from an include of <algorithm>.
>> > This is what I get:
>> >
>> > /usr/include/c++/4.6/cstdlib:76:8: error: attempt to use poisoned "calloc"
>>
>> Ah, I see: adding the include gets the mentions of malloc in before the
>> names are poisoned.  This change is OK.
>>
>
> I ran into the same issue when I started using C++ std:: stuff in the SH
> backend code last year.  I posted a patch, but somehow it didn't go
> anywhere...
>
> http://gcc.gnu.org/ml/gcc-patches/2012-09/msg00880.html
>
> The workaround was to include <cstdlib> as the first include in sh.c.
> Would it be possible to have the change above also in trunk?
>
> Cheers,
> Oleg
>

I strongly suggest prefering <stdlib.h> over <cstdlib> for GCC source code
base.  The reason is that it brings us very little:
    1. Not all compilers implement C++93/C++03 semantics on all platforms;
      in fact even GCC didn't on solaris platforms for example.  So, from
       bootstrapping purposes, we better be on the safer side.

    2. C++11 says that  the implementation is free to define names in
      both namespaces (global and std.)  If we ever accept C++11 in
      5-10 years, we better have something can withstand the evolution.

So, my advice is for GCC source code to forget about the <cxxx>
headers for the  most part.  I can see an instance where <cmath> or <cstring>
would make a difference but given point (1) above, no it doesn't.
Just use the traditional <xxx.h> headers and be done with it.

Maybe I should have included this in our C++ coding standards, but
I don't know how Benjamin, Lawrence, and Diego fee about it.

-- Gaby

Re: [c++-concepts] code review

[Oleg Endo]

On Thu, 2013-06-06 at 16:29 -0400, Jason Merrill wrote:
> On 06/06/2013 01:47 PM, Andrew Sutton wrote:
> > I never did understand why this happens. Compiling with GCC-4.6, I get
> > these errors originating in logic.cc from an include of <algorithm>.
> > This is what I get:
> >
> > /usr/include/c++/4.6/cstdlib:76:8: error: attempt to use poisoned "calloc"
> 
> Ah, I see: adding the include gets the mentions of malloc in before the 
> names are poisoned.  This change is OK.
> 

I ran into the same issue when I started using C++ std:: stuff in the SH
backend code last year.  I posted a patch, but somehow it didn't go
anywhere...

http://gcc.gnu.org/ml/gcc-patches/2012-09/msg00880.html

The workaround was to include <cstdlib> as the first include in sh.c.
Would it be possible to have the change above also in trunk?

Cheers,
Oleg

Re: [c++-concepts] code review

[Andrew Sutton]

>> +C++ ObjC++ Var(flag_concepts, true)
>
> This line declares flag_concepts implicitly.

Ah... I see. Fixed.


>> That's the long and short of it. Gaby suggested writing constraints
>> here so that, for any instantiation, you would have easy access to the
>> constraints for that declaration.
>
> I'm not sure why you would care about the constraints for a particular
> instantiation; constraints only apply to the template, right?

In concepts lite, yes. Moving forward... I'm less certain. In the
context of separate checking, instantiated requirements may carry
lookup information into the current instantiation. But that's just
speculation.

I think I previously put constraint_info in lang_decl_min, right next
to template_info no less. It was easy to manage there, and initialized
as part of build_template_decl. But this obviously doesn't work for
partial specializations unless they get template_decls.

I'd be okay committing the current design with the caveat that it may
need to be rewritten in the not-so-distant future. I've already
written the other other way two or three times, so I'm familiar with
those changes.


>> branch_goal queues a copy of the current sub-goal, returning a
>> reference to that new branch. The insertion of the operands are done
>> on different sub-goals, giving the expected results.
>
> Right, I suppose I should have paid more attention to "This does not update
> the current goal"...

On the topic of logic.cc, I'm plan on rewriting this module to use a
set instead of lists. There will be some pretty substantial changes to
the internal interfaces.

Would it be reasonable to commit this now (since it works correctly),
and plan to rewrite it in the near future?


> template<term_list& (*proj)(proof_goal&)>
> tree
> extract_goals (proof_state& s)
> ...
>  return extract_goals<assumptions>(s);
>
> but I suppose STL style is OK, too.


Huh. I didn't realize that could be inlined. Neat.


>> I was trying to write the parsing code a little more modularly so I
>> could keep my parse functions as small as possible. I use the facility
>> more heavily in the requires/validexpr code that's not included here.
>
>
> Hmm, to me it seems more modular to keep all of the code for handling e.g.
> "requires" in its own function rather than needing two different places to
> know how a requires clause starts.

I think I see where the problem is. cp_parser_requires_clause is
parsed non-optionally in a requires expression, but that's not
included in the patch. I factored out the explicit parsing (hence the
assertion) from the optional parsing.

I could remove the assertion. There's no path to that function that
does not first check that 'requires' has been found.


>>> Why don't you use 'release' and conjoin_requirements here?
>>
>>
>> Because there is no template parameter list that can provide
>> additional requirements in this declaration.
>
>
> OK, please add a comment to that effect.

On second thought, the absence of release() may actually have been a
bug. Comment added.


>>> The comment sounds more like tsubst_template_parms than
>>> coerce_template_parms.
>>
>>
>> It might be... I'll have to look. What I actually want to get is the
>> set of actual arguments that will be substituted for template
>> parameters given an initial set of arguments (lookup default
>> arguments, generate pack arguments, etc).
>
>
> Right, I think coerce_template_parms has the effect you want, I just don't
> think of it as doing substitution, so the comment and name could use a
> tweak.  If the function doesn't go away, that is.

Still looking at this.

What is the main entry point to overload resolution?

Andrew

Re: [c++-concepts] code review

[Jason Merrill]

On 06/06/2013 01:47 PM, Andrew Sutton wrote:
> I never did understand why this happens. Compiling with GCC-4.6, I get
> these errors originating in logic.cc from an include of <algorithm>.
> This is what I get:
>
> /usr/include/c++/4.6/cstdlib:76:8: error: attempt to use poisoned "calloc"

Ah, I see: adding the include gets the mentions of malloc in before the 
names are poisoned.  This change is OK.

>>> +; Activate C++ concepts support.
>>> +Variable
>>> +bool flag_concepts
>>
>> You don't need to declare this separately.
>
> I'm not quite sure what you mean. Separately from what?

Separately from

> +C++ ObjC++ Var(flag_concepts, true)

This line declares flag_concepts implicitly.

> That's the long and short of it. Gaby suggested writing constraints
> here so that, for any instantiation, you would have easy access to the
> constraints for that declaration.

I'm not sure why you would care about the constraints for a particular 
instantiation; constraints only apply to the template, right?

> branch_goal queues a copy of the current sub-goal, returning a
> reference to that new branch. The insertion of the operands are done
> on different sub-goals, giving the expected results.

Right, I suppose I should have paid more attention to "This does not 
update the current goal"...

>>> +template<typename F>
>>> +  tree
>>> +  extract_goals (proof_state& s, F proj)
>>
>> Why is proj a function argument rather than a template argument, which would
>> allow inlining?
>
> STL influence. Can you give an example of how this should look in
> order to take advantage of inlining?

I was thinking something like

template<term_list& (*proj)(proof_goal&)>
tree
extract_goals (proof_state& s)
...
  return extract_goals<assumptions>(s);

but I suppose STL style is OK, too.

> It was used in a previous version, and I suspect it might be useful in
> the future, but I'm not 100% sure. I felt it would be worthwhile to
> keep it in the patch just in case.

Makes sense.

>> And why do it this way
>> rather than check and possibly return at the top of the function, as
>> elsewhere in the parser?  You already have cp_parser_requires_clause
>> checking for RID_REQUIRES.
>
> I was trying to write the parsing code a little more modularly so I
> could keep my parse functions as small as possible. I use the facility
> more heavily in the requires/validexpr code that's not included here.

Hmm, to me it seems more modular to keep all of the code for handling 
e.g. "requires" in its own function rather than needing two different 
places to know how a requires clause starts.

>> Why don't you use 'release' and conjoin_requirements here?
>
> Because there is no template parameter list that can provide
> additional requirements in this declaration.

OK, please add a comment to that effect.

>>> +// Try to substitute ARGS into PARMS, returning the actual list of
>>> +// arguments that have been substituted. If ARGS cannot be substituted,
>>> +// return error_mark_node.
>>
>> The comment sounds more like tsubst_template_parms than
>> coerce_template_parms.
>
> It might be... I'll have to look. What I actually want to get is the
> set of actual arguments that will be substituted for template
> parameters given an initial set of arguments (lookup default
> arguments, generate pack arguments, etc).

Right, I think coerce_template_parms has the effect you want, I just 
don't think of it as doing substitution, so the comment and name could 
use a tweak.  If the function doesn't go away, that is.

Jason

Re: [c++-concepts] code review

[Andrew Sutton]

Hi Jason,

Thanks for the comments. I just went ahead and fixed all the editorial
issues. Comments and questions below:


>>         * gcc/system.h (cstdlib): Include <cstdlib> to avoid poisoned
>>         declaration errors.
>
> Poisoned declarations of what?  This seems redundant with the #include
> <stdlib.h> just below.

I never did understand why this happens. Compiling with GCC-4.6, I get
these errors originating in logic.cc from an include of <algorithm>.
This is what I get:

In file included from /usr/include/c++/4.6/bits/stl_algo.h:61:0,
                 from /usr/include/c++/4.6/algorithm:63,
                 from ../../c++-concepts/gcc/cp/logic.cc:45:
/usr/include/c++/4.6/cstdlib:76:8: error: attempt to use poisoned "calloc"
/usr/include/c++/4.6/cstdlib:83:8: error: attempt to use poisoned "malloc"
/usr/include/c++/4.6/cstdlib:89:8: error: attempt to use poisoned "realloc"
/usr/include/c++/4.6/cstdlib:112:11: error: attempt to use poisoned "calloc"
/usr/include/c++/4.6/cstdlib:119:11: error: attempt to use poisoned "malloc"
/usr/include/c++/4.6/cstdlib:127:11: error: attempt to use poisoned "realloc"


>> +  /* Concepts-related keywords */
>> +  { "assume",          RID_ASSUME,     D_CXXONLY | D_CXX0X | D_CXXWARN },
>> +  { "axiom",           RID_AXIOM,      D_CXXONLY | D_CXX0X | D_CXXWARN },
>> +  { "concept",         RID_CONCEPT,    D_CXXONLY | D_CXX0X | D_CXXWARN },
>> +  { "forall",          RID_FORALL,     D_CXXONLY | D_CXX0X | D_CXXWARN },
>> +  { "requires",        RID_REQUIRES,   D_CXXONLY | D_CXX0X | D_CXXWARN },
>
>
> I don't see anything that limits these keywords to when concepts are
> enabled.  You probably want to add an additional mask that applies to these.

Ok. I'll add D_CXX_CONCEPTS and set it for all of reserved words.


>> +; Activate C++ concepts support.
>> +Variable
>> +bool flag_concepts
>
> You don't need to declare this separately.

I'm not quite sure what you mean. Separately from what?


>> +static tree
>> +resolve_constraint_check (tree ovl, tree args)
>
> This function seems to be trying to model a subset of overload resolution,
> which seems fragile to me; better to use the actual overload resolution code
> to decide which function the constraint expression calls, or at least
> resolve_nondeduced_context which handles SFINAE.

It is. I was a little hesitant to use the actual overload resolution
facility because of the restrictions for concepts. I think I was also
doing something a little different in previous version.

I'll take another look and see if either will work instead of my
homebrew solution.


>
>> +    case CAST_EXPR:
>> +      return reduce_node (TREE_VALUE (TREE_OPERAND (t, 0)));
>
> Are we assuming that constraint expressions can't involve objects of literal
> class type?

For now, I think it's a reasonable restriction. We can relax this as
needed in the future.


>>  struct GTY(()) tree_template_info {
>>    struct tree_common common;
>> +  tree constraint;
>>    vec<qualified_typedef_usage_t, va_gc>
>> *typedefs_needing_access_checking;
>>  };
>
>
> Why do we need constraint information in template_info?  I suppose this is
> the issue you raised in your mail last month:
>
>> I had expected there to be a template decl associated with underlying
>> class, but after print-bombing most of the instantiation, lookup, and
>> specialization processing routines, I couldn't find that one was ever
>> created for the type decl.
>
> This does seem like a shortcoming, that also led to the typedefs vec getting
> stuck into the template_info inappropriately.  I guess we should start
> building TEMPLATE_DECLs for partial specializations.

That's the long and short of it. Gaby suggested writing constraints
here so that, for any instantiation, you would have easy access to the
constraints for that declaration.


>> +struct GTY(()) tree_constraint_info {
>> +  struct tree_base base;
>> +  tree spelling;
>> +  tree requirements;
>> +  tree assumptions;
>> +};
>
>
> I'm confused by the relationship between the comment and the field names
> here.  Where do the conclusions come in?  Is "requirements (as a constant
> expression)" in the spelling or requirements field?

I must have forgotten to update the comments. I probably need to
re-think this structure a bit. The requirements field is the complete
set of requirement (shorthand constraints + requires clause). The
assumptions field is the analyzed requirements.

I was using the "spelling" field specifically for diagnostics, so I
could print exactly what was written. I think it might be better to
hang that off the template parameter list rather than the constraint
info.

I don't think "spelling" is used in the current patch other than initialization.


>> +      DECL_DECLARED_CONCEPT_P (decl) = true;
>> +      if (!check_concept_fn (decl))
>> +        return NULL_TREE;
>> +    }
>
>
> I think I'd rather deal with an invalid concept by not marking it as a
> concept, but still declaring it as a constexpr function.

Sounds reasonable.


>> +// Return the current list of assumed terms.
>> +inline term_list &
>> +assumptions (proof_state &s) { return assumptions (current_goal (s)); }
>
>
> Just as a comment, this use of internal iterators and forwarding functions
> seems confusing; a reader is likely to think that assumptions (s) would
> produce a list of assumptions for the state as a whole, rather than for the
> current goal.  It's particularly surprising in functions like
> decompose_left_goal, where we look at the innermost iterator and then pass
> the outermost object to a subroutine.

I'll think about how to restructure this to make it more intuitive.


>> +// And right logical rule.
>> +inline void
>> +and_right (proof_state &s)
>> +{
>> +  gcc_assert (TREE_CODE (conclusion (s)) == TRUTH_ANDIF_EXPR);
>> +  tree t = ignore_term (s);
>> +  conclude_term (branch_goal (s), TREE_OPERAND (t, 1));
>> +  conclude_term (current_goal (s), TREE_OPERAND (t, 0));
>> +}
>
> A |- B
> A |- C
>
> right?  But since branch_goal updates the current sub-goal, I would expect
> the result to be
>
> A |-
> A |- C, B
>
> instead.  And likewise for or_left.

branch_goal queues a copy of the current sub-goal, returning a
reference to that new branch. The insertion of the operands are done
on different sub-goals, giving the expected results.

I have a long-term plan to rewrite these sub-goals as sets rather than
lists to improve performance. That would also let me worry less about
maintaining state, like I do in this iteration.


>> +template<typename F>
>> +  tree
>> +  extract_goals (proof_state& s, F proj)
>
>
> Why is proj a function argument rather than a template argument, which would
> allow inlining?

STL influence. Can you give an example of how this should look in
order to take advantage of inlining?


>> +decompose_conclusions (tree r)
>
> This function is currently never used; I assume that is planned for a later
> patch?

It was used in a previous version, and I suspect it might be useful in
the future, but I'm not 100% sure. I felt it would be worthwhile to
keep it in the patch just in case.


>> +// The following functions will optionally parse a rule if the
>> corresponding
>> +// criteria is satisfied. If not, the parser returns NULL indicating that
>> +// the optional parse taken.
>
> Missing a "was not".  And these functions should also take the rule as a
> template argument rather than a function argument.  And why do it this way
> rather than check and possibly return at the top of the function, as
> elsewhere in the parser?  You already have cp_parser_requires_clause
> checking for RID_REQUIRES.

I was trying to write the parsing code a little more modularly so I
could keep my parse functions as small as possible. I use the facility
more heavily in the requires/validexpr code that's not included here.

I ended up rewriting this based on Gaby's comments, but not to use
template arguments.


> There are a bunch of unnecessary whitespace changes in parser.c, including
> this one.

I'll re-generate the patch with -w after cleanups.

>
>>               else
>>                 initializer = NULL_TREE;
>>
>> +              // If we're looking at a function declaration, then a
>> requires
>> +              // clause may follow the declaration.
>> +              tree saved_template_reqs = current_template_reqs;
>
>
> Why don't you use 'release' and conjoin_requirements here?

Because there is no template parameter list that can provide
additional requirements in this declaration.

>> +// Try to substitute ARGS into PARMS, returning the actual list of
>> +// arguments that have been substituted. If ARGS cannot be substituted,
>> +// return error_mark_node.
>> +tree
>> +substitute_template_parameters (tree parms, tree args)
>
>
> The comment sounds more like tsubst_template_parms than
> coerce_template_parms.

It might be... I'll have to look. What I actually want to get is the
set of actual arguments that will be substituted for template
parameters given an initial set of arguments (lookup default
arguments, generate pack arguments, etc).

This is only used by my homebrew overload resolution for concepts, so
this could go away.

Andrew

[c++-concepts] code review

[Jason Merrill]

Hi, I'm finally going through the current code on the branch, sorry for 
the delay.

>         * gcc/system.h (cstdlib): Include <cstdlib> to avoid poisoned
>         declaration errors.

Poisoned declarations of what?  This seems redundant with the #include 
<stdlib.h> just below.

> +  /* Concepts-related keywords */
> +  { "assume",          RID_ASSUME,     D_CXXONLY | D_CXX0X | D_CXXWARN },
> +  { "axiom",           RID_AXIOM,      D_CXXONLY | D_CXX0X | D_CXXWARN },
> +  { "concept",         RID_CONCEPT,    D_CXXONLY | D_CXX0X | D_CXXWARN },
> +  { "forall",          RID_FORALL,     D_CXXONLY | D_CXX0X | D_CXXWARN },
> +  { "requires",        RID_REQUIRES,   D_CXXONLY | D_CXX0X | D_CXXWARN },

I don't see anything that limits these keywords to when concepts are 
enabled.  You probably want to add an additional mask that applies to these.

> +; Activate C++ concepts support.
> +Variable
> +bool flag_concepts

You don't need to declare this separately.

> Components for process constraints and evaluating constraints.

Should that be "processing"?

> +// TODO: Simply assinging boolean_type_node to the result type of the expression

"assigning"

> +// reduced terms in the constraints languaage. Returns NULL_TREE if either A or

"language"

> +// a constexpr, nullary function teplate whose result can be converted

"template"

> +  // A constraint is declared constexpr

Needs a period.

> +// This function is not called for abitrary call expressions. In particul,

"particular"

> +static tree
> +resolve_constraint_check (tree ovl, tree args)

This function seems to be trying to model a subset of overload 
resolution, which seems fragile to me; better to use the actual overload 
resolution code to decide which function the constraint expression 
calls, or at least resolve_nondeduced_context which handles SFINAE.

> +    case CAST_EXPR:
> +      return reduce_node (TREE_VALUE (TREE_OPERAND (t, 0)));

Are we assuming that constraint expressions can't involve objects of 
literal class type?

> +// If T is a call to a constraint instantiate it's definition and

"its"

> +  tree c = finish_call_expr (t, &args, true, false, 0);
> +  error ("invalid requirement");
> +  inform (input_location, "did you mean %qE", c);

For both of these diagnostics, let's use EXPR_LOC_OR_HERE (t) as the 
location.

> +// Reduce the requirement T into a logical formula written in terms of
> +// atomic propositions.
> +tree
> +reduce_requirements (tree reqs)

s/T/REQS/

>  struct GTY(()) tree_template_info {
>    struct tree_common common;
> +  tree constraint;
>    vec<qualified_typedef_usage_t, va_gc> *typedefs_needing_access_checking;
>  };

Why do we need constraint information in template_info?  I suppose this 
is the issue you raised in your mail last month:

> In general constraints are directly associated with a template decl. For example:
>
> template<Arithmetic T>
>   class complex;
>
> The Arithmetic constraint is associated with the template decl. However, this doesn't seem to work with partial specializations:
>
> template<Real T>
>   struct complex<T> { ... };
>
> I had expected there to be a template decl associated with underlying class, but after print-bombing most of the instantiation, lookup, and specialization processing routines, I couldn't find that one was ever created for the type decl.

This does seem like a shortcoming, that also led to the typedefs vec 
getting stuck into the template_info inappropriately.  I guess we should 
start building TEMPLATE_DECLs for partial specializations.

> +/* Constraint information for a C++ declaration. This includes the
> +   requirements (as a constant expression) and the decomposed assumptions
> +   and conclusions. The assumptions and conclusions are cached for the
> +   purposes of overlaod resolution and diagnostics. */
> +struct GTY(()) tree_constraint_info {
> +  struct tree_base base;
> +  tree spelling;
> +  tree requirements;
> +  tree assumptions;
> +};

I'm confused by the relationship between the comment and the field names 
here.  Where do the conclusions come in?  Is "requirements (as a 
constant expression)" in the spelling or requirements field?

Also, "overload".

> +constraint_info_p (tree t)
> +template_info_p (tree t)

Let's use check_* rather than *_p for these, too.

> +// NODE must be a lang-decl.

Let's say "NODE must have DECL_LANG_SPECIFIC" to avoid confusion with 
struct lang_decl.

> +      error ("concept %q#D declared with function arguments", fn);

s/arguments/parameters/.  Some of the gcc internals get this distinction 
wrong; but we don't need to expose that in diagnostics...

> +  // If the concept declaration specifier was found, check
> +  // that the declaration satisfies the necessary requirements.
> +  if (inlinep & 4)
> +    {
> +      DECL_DECLARED_CONCEPT_P (decl) = true;
> +      if (!check_concept_fn (decl))
> +        return NULL_TREE;
> +    }

I think I'd rather deal with an invalid concept by not marking it as a 
concept, but still declaring it as a constexpr function.

> +  flag_concepts = true;

This is redundant since c.opt specifies that it defaults to true.

> +// Return the current conclision.

"conclusion"

> +// Return the current list of assumed terms.
> +inline term_list &
> +assumptions (proof_state &s) { return assumptions (current_goal (s)); }

Just as a comment, this use of internal iterators and forwarding 
functions seems confusing; a reader is likely to think that assumptions 
(s) would produce a list of assumptions for the state as a whole, rather 
than for the current goal.  It's particularly surprising in functions 
like decompose_left_goal, where we look at the innermost iterator and 
then pass the outermost object to a subroutine.

> +// The following functions are used to manage the insertation and removal
> +// goals and terms in the proof state.

"insertion and removal of"

> +// the new objet. This does not update the current goal.

"object"

> +// And right logical rule.
> +inline void
> +and_right (proof_state &s)
> +{
> +  gcc_assert (TREE_CODE (conclusion (s)) == TRUTH_ANDIF_EXPR);
> +  tree t = ignore_term (s);
> +  conclude_term (branch_goal (s), TREE_OPERAND (t, 1));
> +  conclude_term (current_goal (s), TREE_OPERAND (t, 0));
> +}

I believe the intent here is to split a sequent

A |- B ^ C

into two,

A |- B
A |- C

right?  But since branch_goal updates the current sub-goal, I would 
expect the result to be

A |-
A |- C, B

instead.  And likewise for or_left.

> +// a tree (a vetor of vectors).

"vector"

> +// Extract a vector of term vectors from s. The selected set of terms is given
> +// by the projection function proj. This is generally either assumptions or
> +// conclusions.
> +template<typename F>
> +  tree
> +  extract_goals (proof_state& s, F proj)

Why is proj a function argument rather than a template argument, which 
would allow inlining?

> +// Decompose the requirement R into a set of conclusionss, returning a

"conclusions"

> +decompose_conclusions (tree r)

This function is currently never used; I assume that is planned for a 
later patch?

> +// Returns true if the list of assumptions AS subsume the atomic
> +// proposition C. This is the case when we can find a proposition in
> +// HS that entails the conclusion C.

s/HS/AS/

> +      return subsumes_prop (as, TREE_OPERAND (c, 0))
> +          && subsumes_prop (as, TREE_OPERAND (c, 1));
> +    case TRUTH_ORIF_EXPR:
> +      return subsumes_prop (as, TREE_OPERAND (c, 0))
> +          || subsumes_prop (as, TREE_OPERAND (c, 1));

Multi-line expressions need parentheses.

> +// The following functions will optionally parse a rule if the corresponding
> +// criteria is satisfied. If not, the parser returns NULL indicating that
> +// the optional parse taken.

Missing a "was not".  And these functions should also take the rule as a 
template argument rather than a function argument.  And why do it this 
way rather than check and possibly return at the top of the function, as 
elsewhere in the parser?  You already have cp_parser_requires_clause 
checking for RID_REQUIRES.

> -        expect the specialization handler to detect and report this.  */
> +         expect the specialization handler to detect and report this.  */

There are a bunch of unnecessary whitespace changes in parser.c, 
including this one.

> @@ -19773,6 +19883,17 @@ cp_parser_member_declaration (cp_parser* parser)
>               else
>                 initializer = NULL_TREE;
>
> +              // If we're looking at a function declaration, then a requires
> +              // clause may follow the declaration.
> +              tree saved_template_reqs = current_template_reqs;

Why don't you use 'release' and conjoin_requirements here?

> +// Try to substitute ARGS into PARMS, returning the actual list of
> +// arguments that have been substituted. If ARGS cannot be substituted,
> +// return error_mark_node.
> +tree
> +substitute_template_parameters (tree parms, tree args)

The comment sounds more like tsubst_template_parms than 
coerce_template_parms.

Jason