commit f59602ada5cb864a78e24e53b3ba2e67b5d26bf8 Author: jason Date: Thu Jul 21 06:05:24 2016 +0000 Improving concepts performance and diagnostics. PR c++/67565 PR c++/67579 PR c++/71843 gcc/ * timevar.def (TV_CONSTRAINT_SAT, TV_CONSTRAINT_SUB): New time vars for constraint satisfaction and subsumption. * timevar.h (auto_timevar): New constructor that matches the push/pop pattern of usage in pt.c. gcc/cp/ * cp-tree.def (CHECK_CONSTR): New. * cp-tree.h (CHECK_CONSTR_CONCEPT): New. (CHECK_CONSTR_ARGS): New. * constraint.cc (make_predicate_constraint): Remove in favor of normalize_expression. (resolve_constraint_check): Actually return error_mark_node when resolution fails. (resolve_variable_concept_check): Perform coercion as if processing a template. Also return errors on resolution failure. (lift_*): Remove all of these functions. Don't unnecessarily inline concepts. (learn_*): Add facilities to memoize implications for subsumption during normalization. (expanding_concept): New. (expand_concept): New. Return the inlined and normalized definition of a concept when needed. (transform_*, xform_*): Rename to normalize_* to better reflect the responsibility of those functions. (normalize_template_id_expression): Check for non-boolean operands when possible. Generate check constraints instead of normal variable references. (normalize_call_expression): Report errors when resolution fails. (check_for_logical_overloads): Rewrite this check to more accurately report the error. (normalize_atom): Check for overloaded calls and invalid types before determining if the expression refers to a concept. (build_constraints): Don't cache normalized constraints or decmposed assumptions. (finish_shorthand_constraint): Return a normalized expression instead of a predicate constraint. (finish_template_introduction): Same. (placeholder_extract_concept_and_args): Rewrite this since we only ever get check constraints here. (equivalent_placeholder_constraints): Rewrite in terms of check constraints, and handle error_mark_nodes correctly. (tsubst_check_constraint, tsubst_expr_constr, tsubst_type_constr) (tsubst_implicit_conversion_constr) (tsubst_argument_deduction_constr, tsubst_exception_constr) (tsubst_parameterized_constraint, tsubst_constraint): New. (tsbust_conjunection): Replace with tsubst_logical_operator and actually generate the right kind of constraint. (tsubst_requirement_body): Reverse the order of substituted arguments so that they appear in the order written (helps diagnostics). (satisfy_check_constraint): New. (satisfy_conjunction): Simplify. (satisfy_disjunction): Same. (satisfy_constraint_1): Handle check constraints. (eval_constr): New (private) global state. (evaluating_constraints_sentinel): New. Manages eval_constr. (satisfy_constraint): Add timing variables. (satisfy_associated_constraints): Add hooks for memoization. (evaluate_function_concept): Build a check constraint instead of normalizing its definition. (evaluate_variable_concept): Same. (evaluate_constraint_expression): Normalize, but in the current declaration processing context. (evaluating_constraints_p): New. (elide_constraint_failure_p): Actually emit constraint_thresh errors. (diagnose_*): Remove artificial indentation. Add a new parameter to each that tracks the current (complete) constraint prior to any substitutions. (diagnose_expression): Removed. (diagnose_call_expression): Same. (diagnose_template_id): Same. (diagnose_template_id): New. (diagnose_logical_constraint): New. (diagnose_expression_constraint): Show the original expression. (diagnose_type_constraint): Show the original type. (diagnose_implicit_conversion_constraint): Be specific about failures, don't re-diagnose a known-to-be-failed substitutions, and manage elisions properly. (diagnose_argument_deduction_constraint): Same. (diagnose_exception_constraint): Same. (diagnose_parameterized_constraint): Same. (constraint_p): Allow EXPR_PACK_EXPANSION. * logic.cc (next_by_distance): Removed. No longer used. (any_p): Renamed from any_of. (term_entry, term_hasher): New. (term_list): Rewrite to include a hash table for quick lookup. Also, make less stateful. (proof_state): Extend to allow goals to be discharged once satisfied. (non_atomic_constraint_p): New. (any_non_atomic_constraints_p): New. (...rest...): Previous implementation completely replaced with an iterative algorithm that opportunistically prunes the search space before committing to using more memory. * parser.c: (cp_parser_type_parameter): Normalize constraints. (cp_parser_explicit_template_declaration): Same. * pt.c: (finish_template_variable): Be less redundant with this error message. (template_args_equal): No longer static. (tsubst_decl): Don't try to find specializations of variables that have already been instantiated. (build_non_dependent_expr): Avoid infinite recursion during concept expansion. (make_constrained_auto): Normalize constraints. (do_auto_deduction): When doing auto deduction from a partial-concept-id, be sure to include the explicit args checking the constraints. (constraint_sat_*): New. Memoize satisfied constraints. (concept_spec_*): New. Memoize expressions associated with a concept specialization. (constraint_memos, concept_memos): New. (lookup_constraint_satisfaction, memoize_constraint_satisfaction): New. (lookup_concept_satisfaction, memoize_concept_satisfaction): New. (get_concept_expansion, save_concept_expansion): New. (hash_subsumption_args): New. (comp_subsumption_args): New. (subsumption_*): New. Memoize parts of the subsumption relation. (lookup_subsumption_result, save_subsumption_result): New. (init_constraint_processing): Initialize memo tables. (get_constraints): Shortcut if !flag_concepts. * decl.c (grokfndecl): Normalize constraints. * error.c (dump_simple_decl): Print "concept" when appropriate. (dump_function_decl): Same. (dump_template_decl): Don't write requirements when we're not printing the header. (dump_expr): Handle fold expressions. * cxx-pretty-print.c (cxx_pretty_printer::expression): Handle fold expressions. (get_fold_operator): New. (pp_cxx_unary_left_fold_expression): New. (pp_cxx_unary_right_fold_expression): New. (pp_cxx_binary_fold_expression): New. (pp_cxx_check_constraint): New. (pp_cxx_*_constraint): Rewrite the grammar of internal constraints to make them easier to read when debugging. * search.c (accessible_p): Don't shortcut when evaluating constraints. * tree.c (cp_tree_equal): Handle CHECK_CONSTR. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@238558 138bc75d-0d04-0410-961f-82ee72b054a4 diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc index af7a593..311d025 100644 --- a/gcc/cp/constraint.cc +++ b/gcc/cp/constraint.cc @@ -22,6 +22,7 @@ along with GCC; see the file COPYING3. If not see #include "system.h" #include "coretypes.h" #include "tm.h" +#include "timevar.h" #include "hash-set.h" #include "machmode.h" #include "vec.h" @@ -55,7 +56,9 @@ along with GCC; see the file COPYING3. If not see static inline bool constraint_p (tree_code c) { - return (PRED_CONSTR <= c && c <= DISJ_CONSTR) || c == ERROR_MARK; + return ((PRED_CONSTR <= c && c <= DISJ_CONSTR) + || c == EXPR_PACK_EXPANSION + || c == ERROR_MARK); } /* Returns true if T is a constraint. Note that error_mark_node @@ -67,14 +70,6 @@ constraint_p (tree t) return constraint_p (TREE_CODE (t)); } -/* Make a predicate constraint from the given expression. */ - -tree -make_predicate_constraint (tree expr) -{ - return build_nt (PRED_CONSTR, expr); -} - /* Returns the conjunction of two constraints A and B. Note that conjoining a non-null constraint with NULL_TREE is an identity operation. That is, for non-null A, @@ -132,6 +127,53 @@ function_concept_check_p (tree t) return false; } +/* Returns true if any of the arguments in the template + argument list is a wildcard or wildcard pack. */ + +bool +contains_wildcard_p (tree args) +{ + for (int i = 0; i < TREE_VEC_LENGTH (args); ++i) + { + tree arg = TREE_VEC_ELT (args, i); + if (TREE_CODE (arg) == WILDCARD_DECL) + return true; + } + return false; +} + +/* Build a new call expression, but don't actually generate a + new function call. We just want the tree, not the semantics. */ + +inline tree +build_call_check (tree id) +{ + ++processing_template_decl; + vec *fargs = make_tree_vector(); + tree call = finish_call_expr (id, &fargs, false, false, tf_none); + release_tree_vector (fargs); + --processing_template_decl; + return call; +} + +/* Build an expression that will check a variable concept. If any + argument contains a wildcard, don't try to finish the variable + template because we can't substitute into a non-existent + declaration. */ + +tree +build_variable_check (tree id) +{ + gcc_assert (TREE_CODE (id) == TEMPLATE_ID_EXPR); + if (contains_wildcard_p (TREE_OPERAND (id, 1))) + return id; + + ++processing_template_decl; + tree var = finish_template_variable (id); + --processing_template_decl; + return var; +} + /*--------------------------------------------------------------------------- Resolution of qualified concept names ---------------------------------------------------------------------------*/ @@ -160,6 +202,7 @@ function_concept_check_p (tree t) static tree resolve_constraint_check (tree ovl, tree args) { + int nerrs = 0; tree cands = NULL_TREE; for (tree p = ovl; p != NULL_TREE; p = OVL_NEXT (p)) { @@ -185,15 +228,21 @@ resolve_constraint_check (tree ovl, tree args) ++processing_template_decl; tree parms = TREE_VALUE (DECL_TEMPLATE_PARMS (tmpl)); if (tree subst = coerce_template_parms (parms, args, tmpl)) - if (subst != error_mark_node) - cands = tree_cons (subst, fn, cands); + { + if (subst == error_mark_node) + ++nerrs; + else + cands = tree_cons (subst, fn, cands); + } --processing_template_decl; } - // If we didn't find a unique candidate, then this is - // not a constraint check. - if (!cands || TREE_CHAIN (cands)) - return NULL_TREE; + if (!cands) + /* We either had no candidates or failed deductions. */ + return nerrs ? error_mark_node : NULL_TREE; + else if (TREE_CHAIN (cands)) + /* There are multiple candidates. */ + return error_mark_node; return cands; } @@ -250,14 +299,16 @@ resolve_variable_concept_check (tree id) assuming that it works. Note that failing to deduce will result in diagnostics. */ tree parms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (tmpl)); + ++processing_template_decl; tree result = coerce_template_parms (parms, args, tmpl); + --processing_template_decl; if (result != error_mark_node) { tree decl = DECL_TEMPLATE_RESULT (tmpl); return build_tree_list (result, decl); } else - return NULL_TREE; + return error_mark_node; } @@ -315,45 +366,119 @@ deduce_concept_introduction (tree expr) namespace { /*--------------------------------------------------------------------------- - Lifting of concept definitions + Constraint implication learning ---------------------------------------------------------------------------*/ -/* Part of constraint normalization. Whenever we find a reference to - a variable concept or a call to a function concept, we lift or - inline that concept's definition into the constraint. This ensures - that constraints are always checked in the immediate instantiation - context. */ +/* The implication context determines how we memoize concept checks. + Given two checks C1 and C2, the direction of implication depends + on whether we are learning implications of a conjunction or disjunction. + For example: -tree lift_expression (tree); + template concept bool C = ...; + template concept bool D = C && true; -/* If the tree T has operands, then lift any concepts out of them. */ -tree -lift_operands (tree t) + From this, we can learn that D implies C. We cannot learn, + without further testing, that C does not imply D. If, for + example, C were defined as true, then these constraints would + be logically equivalent. + + In rare cases, we may start with a logical equivalence. For example: + + template concept bool C = ...; + template concept bool D = C; + + Here, we learn that C implies D and vice versa. */ + +enum implication_context { - if (int n = tree_operand_length (t)) + conjunction_cxt, /* C1 implies C2. */ + disjunction_cxt, /* C2 implies C1. */ + equivalence_cxt /* C1 implies C2, C2 implies C1. */ +}; + +void learn_implications(tree, tree, implication_context); + +void +learn_implication (tree parent, tree child, implication_context cxt) +{ + switch (cxt) { - t = copy_node (t); - for (int i = 0; i < n; ++i) - TREE_OPERAND (t, i) = lift_expression (TREE_OPERAND (t, i)); + case conjunction_cxt: + save_subsumption_result (parent, child, true); + break; + case disjunction_cxt: + save_subsumption_result (child, parent, true); + break; + case equivalence_cxt: + save_subsumption_result (parent, child, true); + save_subsumption_result (child, parent, true); + break; } - return t; } -/* Recursively lift all operands of the function call. Also, check - that the call target is not accidentally a variable concept - since that's ill-formed. */ -tree -lift_function_call (tree t) +void +learn_logical_operation (tree parent, tree constr, implication_context cxt) +{ + learn_implications (parent, TREE_OPERAND (constr, 0), cxt); + learn_implications (parent, TREE_OPERAND (constr, 1), cxt); +} + +void +learn_implications (tree parent, tree constr, implication_context cxt) +{ + switch (TREE_CODE (constr)) + { + case CHECK_CONSTR: + return learn_implication (parent, constr, cxt); + + case CONJ_CONSTR: + if (cxt == disjunction_cxt) + return; + return learn_logical_operation (parent, constr, cxt); + + case DISJ_CONSTR: + if (cxt == conjunction_cxt) + return; + return learn_logical_operation (parent, constr, cxt); + + default: + break; + } +} + +/* Quickly scan the top-level constraints of CONSTR to learn and + cache logical relations between concepts. The search does not + include conjunctions of disjunctions or vice versa. */ + +void +learn_implications (tree tmpl, tree args, tree constr) { - gcc_assert (TREE_CODE (t) == CALL_EXPR); - gcc_assert (!VAR_P (CALL_EXPR_FN (t))); - return lift_operands (t); + /* Don't memoize relations between non-dependent arguemnts. It's not + helpful. */ + if (!uses_template_parms (args)) + return; + + /* Build a check constraint for the purpose of caching. */ + tree parent = build_nt (CHECK_CONSTR, tmpl, args); + + /* Start learning based on the kind of the top-level contraint. */ + if (TREE_CODE (constr) == CONJ_CONSTR) + return learn_logical_operation (parent, constr, conjunction_cxt); + else if (TREE_CODE (constr) == DISJ_CONSTR) + return learn_logical_operation (parent, constr, disjunction_cxt); + else if (TREE_CODE (constr) == CHECK_CONSTR) + /* This is the rare concept alias case. */ + return learn_implication (parent, constr, equivalence_cxt); } -/* Inline a function (concept) definition by substituting - ARGS into its body. */ +/*--------------------------------------------------------------------------- + Expansion of concept definitions +---------------------------------------------------------------------------*/ + +/* Returns the expression of a function concept. */ + tree -lift_function_definition (tree fn, tree args) +get_returned_expression (tree fn) { /* Extract the body of the function minus the return expression. */ tree body = DECL_SAVED_TREE (fn); @@ -364,202 +489,107 @@ lift_function_definition (tree fn, tree args) if (TREE_CODE (body) != RETURN_EXPR) return error_mark_node; - body = TREE_OPERAND (body, 0); - - /* Substitute template arguments to produce our inline expression. */ - tree result = tsubst_expr (body, args, tf_none, NULL_TREE, false); - if (result == error_mark_node) - return error_mark_node; - - return lift_expression (result); + return TREE_OPERAND (body, 0); } -/* Inline a reference to a function concept. */ -tree -lift_call_expression (tree t) -{ - /* Try to resolve this function call as a concept. If not, then - it can be returned as-is. */ - tree check = resolve_constraint_check (t); - if (!check) - return lift_function_call (t); - if (check == error_mark_node) - return error_mark_node; - - tree fn = TREE_VALUE (check); - tree args = TREE_PURPOSE (check); - return lift_function_definition (fn, args); -} +/* Returns the initializer of a variable concept. */ tree -lift_variable_initializer (tree var, tree args) +get_variable_initializer (tree var) { - /* Extract the body from the variable initializer. */ tree init = DECL_INITIAL (var); if (!init) return error_mark_node; + return init; +} - /* Substitute the arguments to form our new inline expression. */ - tree result = tsubst_expr (init, args, tf_none, NULL_TREE, false); +/* Returns the definition of a variable or function concept. */ + +tree +get_concept_definition (tree decl) +{ + if (TREE_CODE (decl) == VAR_DECL) + return get_variable_initializer (decl); + else if (TREE_CODE (decl) == FUNCTION_DECL) + return get_returned_expression (decl); + gcc_unreachable (); +} + +int expansion_level = 0; + +struct expanding_concept_sentinel +{ + expanding_concept_sentinel () + { + ++expansion_level; + } + + ~expanding_concept_sentinel() + { + --expansion_level; + } +}; + + +} /* namespace */ + +/* Returns true when a concept is being expanded. */ + +bool +expanding_concept() +{ + return expansion_level > 0; +} + +/* Expand a concept declaration (not a template) and its arguments to + a constraint defined by the concept's initializer or definition. */ + +tree +expand_concept (tree decl, tree args) +{ + expanding_concept_sentinel sentinel; + + if (TREE_CODE (decl) == TEMPLATE_DECL) + decl = DECL_TEMPLATE_RESULT (decl); + tree tmpl = DECL_TI_TEMPLATE (decl); + + /* Check for a previous specialization. */ + if (tree spec = get_concept_expansion (tmpl, args)) + return spec; + + /* Substitute the arguments to form a new definition expression. */ + tree def = get_concept_definition (decl); + + ++processing_template_decl; + tree result = tsubst_expr (def, args, tf_none, NULL_TREE, true); + --processing_template_decl; if (result == error_mark_node) return error_mark_node; - return lift_expression (result); + /* And lastly, normalize it, check for implications, and save + the specialization for later. */ + tree norm = normalize_expression (result); + learn_implications (tmpl, args, norm); + return save_concept_expansion (tmpl, args, norm); } -/* Determine if a template-id is a variable concept and inline. */ - -tree -lift_template_id (tree t) -{ - if (tree info = resolve_variable_concept_check (t)) - { - tree decl = TREE_VALUE (info); - tree args = TREE_PURPOSE (info); - return lift_variable_initializer (decl, args); - } - - /* Check that we didn't refer to a function concept like - a variable. - - TODO: Add a note on how to fix this. */ - tree tmpl = TREE_OPERAND (t, 0); - if (TREE_CODE (tmpl) == OVERLOAD) - { - tree fn = OVL_FUNCTION (tmpl); - if (TREE_CODE (fn) == TEMPLATE_DECL - && DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (fn))) - { - error_at (location_of (t), - "invalid reference to function concept %qD", fn); - return error_mark_node; - } - } - - return t; -} - -/* Lift any constraints appearing in a nested requirement of - a requires-expression. */ -tree -lift_requires_expression (tree t) -{ - tree parms = TREE_OPERAND (t, 0); - tree reqs = TREE_OPERAND (t, 1); - tree result = NULL_TREE; - for (; reqs != NULL_TREE; reqs = TREE_CHAIN (reqs)) - { - tree req = TREE_VALUE (reqs); - if (TREE_CODE (req) == NESTED_REQ) - { - tree expr = lift_expression (TREE_OPERAND (req, 0)); - req = finish_nested_requirement (expr); - } - result = tree_cons (NULL_TREE, req, result); - } - return finish_requires_expr (parms, result); -} - -/* Inline references to specializations of concepts. */ -tree -lift_expression (tree t) -{ - if (t == NULL_TREE) - return NULL_TREE; - - if (t == error_mark_node) - return error_mark_node; - - /* Concepts can be referred to by call or variable. All other - nodes are preserved. */ - switch (TREE_CODE (t)) - { - case CALL_EXPR: - return lift_call_expression (t); - - case TEMPLATE_ID_EXPR: - return lift_template_id (t); - - case REQUIRES_EXPR: - return lift_requires_expression (t); - - case EXPR_PACK_EXPANSION: - /* Use copy_node rather than make_pack_expansion so that - PACK_EXPANSION_PARAMETER_PACKS stays the same. */ - t = copy_node (t); - SET_PACK_EXPANSION_PATTERN - (t, lift_expression (PACK_EXPANSION_PATTERN (t))); - return t; - - case TREE_LIST: - { - t = copy_node (t); - TREE_VALUE (t) = lift_expression (TREE_VALUE (t)); - TREE_CHAIN (t) = lift_expression (TREE_CHAIN (t)); - return t; - } - - default: - return lift_operands (t); - } -} /*--------------------------------------------------------------------------- - Transformation of expressions into constraints + Stepwise normalization of expressions + +This set of functions will transform an expression into a constraint +in a sequence of steps. Normalization does not not look into concept +definitions. ---------------------------------------------------------------------------*/ -/* Part of constraint normalization. The following functions rewrite - expressions as constraints. */ - -tree transform_expression (tree); - -/* Check that the logical-or or logical-and expression does - not result in a call to a user-defined user-defined operator - (temp.constr.op). Returns true if the logical operator is - admissible and false otherwise. */ - -bool -check_logical_expr (tree t) -{ - /* We can't do much for type dependent expressions. */ - if (type_dependent_expression_p (t)) - return true; - - /* 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. - - TODO: This check is actually subsumed by the requirement that - constraint operands have type bool. I'm not sure we need it - unless we allow conversions. */ - tree arg1 = TREE_OPERAND (t, 0); - tree arg2 = TREE_OPERAND (t, 1); - tree ovl = NULL_TREE; - tree expr = build_x_binary_op (EXPR_LOC_OR_LOC (arg2, input_location), - TREE_CODE (t), - arg1, TREE_CODE (arg1), - arg2, TREE_CODE (arg2), - &ovl, - tf_none); - if (TREE_CODE (expr) != TREE_CODE (t)) - { - error ("user-defined operator %qs in constraint %q+E", - operator_name_info[TREE_CODE (t)].name, t); - return false; - } - return true; -} - /* Transform a logical-or or logical-and expression into either a conjunction or disjunction. */ tree -xform_logical (tree t, tree_code c) +normalize_logical_operation (tree t, tree_code c) { - if (!check_logical_expr (t)) - return error_mark_node; - tree t0 = transform_expression (TREE_OPERAND (t, 0)); - tree t1 = transform_expression (TREE_OPERAND (t, 1)); + tree t0 = normalize_expression (TREE_OPERAND (t, 0)); + tree t1 = normalize_expression (TREE_OPERAND (t, 1)); return build_nt (c, t0, t1); } @@ -567,7 +597,7 @@ xform_logical (tree t, tree_code c) for its expression. */ inline tree -xform_simple_requirement (tree t) +normalize_simple_requirement (tree t) { return build_nt (EXPR_CONSTR, TREE_OPERAND (t, 0)); } @@ -575,7 +605,7 @@ xform_simple_requirement (tree t) /* A type requirement T introduce a type constraint for its type. */ inline tree -xform_type_requirement (tree t) +normalize_type_requirement (tree t) { return build_nt (TYPE_CONSTR, TREE_OPERAND (t, 0)); } @@ -589,7 +619,7 @@ xform_type_requirement (tree t) includes an exception constraint. */ tree -xform_compound_requirement (tree t) +normalize_compound_requirement (tree t) { tree expr = TREE_OPERAND (t, 0); tree constr = build_nt (EXPR_CONSTR, TREE_OPERAND (t, 0)); @@ -627,29 +657,29 @@ xform_compound_requirement (tree t) will guarantee that the constraint is never satisfied. */ inline tree -xform_nested_requirement (tree t) +normalize_nested_requirement (tree t) { - return transform_expression (TREE_OPERAND (t, 0)); + return normalize_expression (TREE_OPERAND (t, 0)); } /* Transform a requirement T into one or more constraints. */ tree -xform_requirement (tree t) +normalize_requirement (tree t) { switch (TREE_CODE (t)) { case SIMPLE_REQ: - return xform_simple_requirement (t); + return normalize_simple_requirement (t); case TYPE_REQ: - return xform_type_requirement (t); + return normalize_type_requirement (t); case COMPOUND_REQ: - return xform_compound_requirement (t); + return normalize_compound_requirement (t); case NESTED_REQ: - return xform_nested_requirement (t); + return normalize_nested_requirement (t); default: gcc_unreachable (); @@ -661,46 +691,165 @@ xform_requirement (tree t) constraints. */ tree -xform_requirements (tree t) +normalize_requirements (tree t) { tree result = NULL_TREE; for (; t; t = TREE_CHAIN (t)) { - tree constr = xform_requirement (TREE_VALUE (t)); + tree constr = normalize_requirement (TREE_VALUE (t)); result = conjoin_constraints (result, constr); } return result; } -/* Transform a requires-expression into a parameterized constraint. */ +/* The normal form of a requires-expression is a parameterized + constraint having the same parameters and a conjunction of + constraints representing the normal form of requirements. */ tree -xform_requires_expr (tree t) +normalize_requires_expression (tree t) { - tree operand = xform_requirements (TREE_OPERAND (t, 1)); + tree operand = normalize_requirements (TREE_OPERAND (t, 1)); if (tree parms = TREE_OPERAND (t, 0)) return build_nt (PARM_CONSTR, parms, operand); else return operand; } -/* Transform an expression into an atomic predicate constraint. - After substitution, the expression of a predicate constraint - shall have type bool (temp.constr.pred). For non-type-dependent - expressions, we can check that now. */ +/* For a template-id referring to a variable concept, returns + a check constraint. Otherwise, returns a predicate constraint. */ tree -xform_atomic (tree t) -{ - if (TREE_TYPE (t) && !type_dependent_expression_p (t)) - { - tree type = cv_unqualified (TREE_TYPE (t)); - if (!same_type_p (type, boolean_type_node)) - { - error ("predicate constraint %q+E does not have type %", t); +normalize_template_id_expression (tree t) +{ + if (tree info = resolve_variable_concept_check (t)) + { + if (info == error_mark_node) + { + /* We get this when the template arguments don't match + the variable concept. */ + error ("invalid reference to concept %qE", t); + return error_mark_node; + } + + tree decl = TREE_VALUE (info); + tree args = TREE_PURPOSE (info); + return build_nt (CHECK_CONSTR, decl, args); + } + + /* Check that we didn't refer to a function concept like a variable. */ + tree tmpl = TREE_OPERAND (t, 0); + if (TREE_CODE (tmpl) == OVERLOAD) + { + tree fn = OVL_FUNCTION (tmpl); + if (TREE_CODE (fn) == TEMPLATE_DECL + && DECL_DECLARED_CONCEPT_P (DECL_TEMPLATE_RESULT (fn))) + { + error_at (location_of (t), + "invalid reference to function concept %qD", fn); + return error_mark_node; + } + } + + return build_nt (PRED_CONSTR, t); +} + +/* For a call expression to a function concept, returns a check + constraint. Otherwise, returns a predicate constraint. */ + +tree +normalize_call_expression (tree t) +{ + /* Try to resolve this function call as a concept. If not, then + it can be returned as a predicate constraint. */ + tree check = resolve_constraint_check (t); + if (!check) + return build_nt (PRED_CONSTR, t); + if (check == error_mark_node) + { + /* TODO: Improve diagnostics. We could report why the reference + is invalid. */ + error ("invalid reference to concept %qE", t); + return error_mark_node; + } + + tree fn = TREE_VALUE (check); + tree args = TREE_PURPOSE (check); + return build_nt (CHECK_CONSTR, fn, args); +} + +/* If T is a call to an overloaded && or || operator, diagnose that + as a non-SFINAEable error. Returns true if an error is emitted. + + TODO: It would be better to diagnose this at the point of definition, + if possible. Perhaps we should immediately do a first-pass normalization + of a concept definition to catch obvious non-dependent errors like + this. */ + +bool +check_for_logical_overloads (tree t) +{ + if (TREE_CODE (t) != CALL_EXPR) + return false; + + tree fn = CALL_EXPR_FN (t); + + /* For member calls, try extracting the function from the + component ref. */ + if (TREE_CODE (fn) == COMPONENT_REF) + { + fn = TREE_OPERAND (fn, 1); + if (TREE_CODE (fn) == BASELINK) + fn = BASELINK_FUNCTIONS (fn); + } + + if (TREE_CODE (fn) != FUNCTION_DECL) + return false; + + if (DECL_OVERLOADED_OPERATOR_P (fn)) + { + location_t loc = EXPR_LOC_OR_LOC (t, input_location); + error_at (loc, "constraint %qE, uses overloaded operator", t); + return true; + } + + return false; +} + +/* The normal form of an atom depends on the expression. The normal + form of a function call to a function concept is a check constraint + for that concept. The normal form of a reference to a variable + concept is a check constraint for that concept. Otherwise, the + constraint is a predicate constraint. */ + +tree +normalize_atom (tree t) +{ + /* We can get constraints pushed down through pack expansions, so + just return them. */ + if (constraint_p (t)) + return t; + + tree type = TREE_TYPE (t); + if (!type || type_unknown_p (t) || TREE_CODE (type) == TEMPLATE_TYPE_PARM) + ; + else if (!dependent_type_p (type)) + { + if (check_for_logical_overloads (t)) return error_mark_node; - } - } + + type = cv_unqualified (type); + if (!same_type_p (type, boolean_type_node)) + { + error ("predicate constraint %q+E does not have type %", t); + return error_mark_node; + } + } + + if (TREE_CODE (t) == TEMPLATE_ID_EXPR) + return normalize_template_id_expression (t); + if (TREE_CODE (t) == CALL_EXPR) + return normalize_call_expression (t); return build_nt (PRED_CONSTR, t); } @@ -735,49 +884,48 @@ push_down_pack_expansion (tree exp, tree pat) leaves of the constraint so that partial ordering will work. */ tree -xform_pack_expansion (tree t) +normalize_pack_expansion (tree t) { - tree pat = transform_expression (PACK_EXPANSION_PATTERN (t)); + tree pat = normalize_expression (PACK_EXPANSION_PATTERN (t)); return push_down_pack_expansion (t, pat); } /* Transform an expression into a constraint. */ tree -xform_expr (tree t) +normalize_any_expression (tree t) { switch (TREE_CODE (t)) { case TRUTH_ANDIF_EXPR: - return xform_logical (t, CONJ_CONSTR); + return normalize_logical_operation (t, CONJ_CONSTR); case TRUTH_ORIF_EXPR: - return xform_logical (t, DISJ_CONSTR); + return normalize_logical_operation (t, DISJ_CONSTR); case REQUIRES_EXPR: - return xform_requires_expr (t); + return normalize_requires_expression (t); case BIND_EXPR: - return transform_expression (BIND_EXPR_BODY (t)); + return normalize_expression (BIND_EXPR_BODY (t)); case EXPR_PACK_EXPANSION: - return xform_pack_expansion (t); + return normalize_pack_expansion (t); default: /* All other constraints are atomic. */ - return xform_atomic (t); + return normalize_atom (t); } } /* Transform a statement into an expression. */ - tree -xform_stmt (tree t) +normalize_any_statement (tree t) { switch (TREE_CODE (t)) { case RETURN_EXPR: - return transform_expression (TREE_OPERAND (t, 0)); + return normalize_expression (TREE_OPERAND (t, 0)); default: gcc_unreachable (); } @@ -787,24 +935,22 @@ xform_stmt (tree t) /* Reduction rules for the declaration T. */ tree -xform_decl (tree t) +normalize_any_declaration (tree t) { switch (TREE_CODE (t)) { case VAR_DECL: - return xform_atomic (t); + return normalize_atom (t); default: gcc_unreachable (); } return error_mark_node; } -/* Transform a lifted expression into a constraint. This either - returns a constraint, or it returns error_mark_node when - a constraint cannot be formed. */ +/* Returns the normal form of a constraint expression. */ tree -transform_expression (tree t) +normalize_expression (tree t) { if (!t) return NULL_TREE; @@ -818,20 +964,20 @@ transform_expression (tree t) case tcc_binary: case tcc_expression: case tcc_vl_exp: - return xform_expr (t); + return normalize_any_expression (t); case tcc_statement: - return xform_stmt (t); + return normalize_any_statement (t); case tcc_declaration: - return xform_decl (t); + return normalize_any_declaration (t); case tcc_exceptional: case tcc_constant: case tcc_reference: case tcc_comparison: /* These are all atomic predicate constraints. */ - return xform_atomic (t); + return normalize_atom (t); default: /* Unhandled node kind. */ @@ -840,6 +986,7 @@ transform_expression (tree t) return error_mark_node; } + /*--------------------------------------------------------------------------- Constraint normalization ---------------------------------------------------------------------------*/ @@ -879,8 +1026,7 @@ normalize_predicate_constraint (tree t) { ++processing_template_decl; tree expr = PRED_CONSTR_EXPR (t); - tree lifted = lift_expression (expr); - tree constr = transform_expression (lifted); + tree constr = normalize_expression (expr); --processing_template_decl; return constr; } @@ -938,7 +1084,6 @@ normalize_constraint (tree t) return error_mark_node; } -} /* namespace */ // -------------------------------------------------------------------------- // @@ -1028,61 +1173,11 @@ build_constraints (tree tmpl_reqs, tree decl_reqs) ci->declarator_reqs = decl_reqs; ci->associated_constr = conjoin_constraints (tmpl_reqs, decl_reqs); - ++processing_template_decl; - ci->normalized_constr = normalize_constraint (ci->associated_constr); - --processing_template_decl; - - ci->assumptions = decompose_assumptions (ci->normalized_constr); return (tree)ci; } namespace { -/* Returns true if any of the arguments in the template - argument list is a wildcard or wildcard pack. */ -bool -contains_wildcard_p (tree args) -{ - for (int i = 0; i < TREE_VEC_LENGTH (args); ++i) - { - tree arg = TREE_VEC_ELT (args, i); - if (TREE_CODE (arg) == WILDCARD_DECL) - return true; - } - return false; -} - -/* Build a new call expression, but don't actually generate - a new function call. We just want the tree, not the - semantics. */ -inline tree -build_call_check (tree id) -{ - ++processing_template_decl; - vec *fargs = make_tree_vector(); - tree call = finish_call_expr (id, &fargs, false, false, tf_none); - release_tree_vector (fargs); - --processing_template_decl; - return call; -} - -/* Build an expression that will check a variable concept. If any - argument contains a wildcard, don't try to finish the variable - template because we can't substitute into a non-existent - declaration. */ -tree -build_variable_check (tree id) -{ - gcc_assert (TREE_CODE (id) == TEMPLATE_ID_EXPR); - if (contains_wildcard_p (TREE_OPERAND (id, 1))) - return id; - - ++processing_template_decl; - tree var = finish_template_variable (id); - --processing_template_decl; - return var; -} - /* Construct a sequence of template arguments by prepending ARG to REST. Either ARG or REST may be null. */ tree @@ -1158,7 +1253,9 @@ build_constrained_parameter (tree cnc, tree proto, tree args) Note that the constraints are neither reduced nor decomposed. That is done only after the requires clause has been parsed - (or not). */ + (or not). + + This will always return a CHECK_CONSTR. */ tree finish_shorthand_constraint (tree decl, tree constr) { @@ -1207,7 +1304,7 @@ finish_shorthand_constraint (tree decl, tree constr) TREE_TYPE (check) = boolean_type_node; } - return make_predicate_constraint (check); + return normalize_expression (check); } /* Returns a conjunction of shorthand requirements for the template @@ -1346,7 +1443,7 @@ finish_template_introduction (tree tmpl_decl, tree intro_list) /* Associate the constraint. */ tree check = build_concept_check (tmpl_decl, NULL_TREE, check_args); - tree constr = make_predicate_constraint (check); + tree constr = normalize_expression (check); TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = constr; return parm_list; @@ -1362,41 +1459,28 @@ placeholder_extract_concept_and_args (tree t, tree &tmpl, tree &args) { if (TREE_CODE (t) == TYPE_DECL) { - /* A constrained parameter. */ - tmpl = DECL_TI_TEMPLATE (CONSTRAINED_PARM_CONCEPT (t)); - args = CONSTRAINED_PARM_EXTRA_ARGS (t); + /* A constrained parameter. Build a constraint check + based on the prototype parameter and then extract the + arguments from that. */ + tree proto = CONSTRAINED_PARM_PROTOTYPE (t); + tree check = finish_shorthand_constraint (proto, t); + placeholder_extract_concept_and_args (check, tmpl, args); return; } - gcc_assert (TREE_CODE (t) == PRED_CONSTR); - t = PRED_CONSTR_EXPR (t); - gcc_assert (TREE_CODE (t) == CALL_EXPR - || TREE_CODE (t) == TEMPLATE_ID_EXPR - || VAR_P (t)); - - if (TREE_CODE (t) == CALL_EXPR) - t = CALL_EXPR_FN (t); - if (TREE_CODE (t) == TEMPLATE_ID_EXPR) - { - tmpl = TREE_OPERAND (t, 0); - if (TREE_CODE (tmpl) == OVERLOAD) - { - gcc_assert (OVL_CHAIN (tmpl) == NULL_TREE); - tmpl = OVL_FUNCTION (tmpl); - } - args = TREE_OPERAND (t, 1); - } - else if (DECL_P (t)) + if (TREE_CODE (t) == CHECK_CONSTR) { - tmpl = DECL_TI_TEMPLATE (t); - args = DECL_TI_ARGS (t); + tree decl = CHECK_CONSTR_CONCEPT (t); + tmpl = DECL_TI_TEMPLATE (decl); + args = CHECK_CONSTR_ARGS (t); + return; } - else + gcc_unreachable (); } /* Returns true iff the placeholders C1 and C2 are equivalent. C1 - and C2 can be either PRED_CONSTR_EXPR or TEMPLATE_TYPE_PARM. */ + and C2 can be either CHECK_CONSTR or TEMPLATE_TYPE_PARM. */ bool equivalent_placeholder_constraints (tree c1, tree c2) @@ -1411,6 +1495,11 @@ equivalent_placeholder_constraints (tree c1, tree c2) return true; if (!c1 || !c2) return false; + if (c1 == error_mark_node || c2 == error_mark_node) + /* We get here during satisfaction; when a deduction constraint + fails, substitution can produce an error_mark_node for the + placeholder constraints. */ + return false; tree t1, t2, a1, a2; placeholder_extract_concept_and_args (c1, t1, a1); @@ -1419,21 +1508,20 @@ equivalent_placeholder_constraints (tree c1, tree c2) if (t1 != t2) return false; - /* Skip the first argument to avoid infinite recursion on the - placeholder auto itself. */ - bool skip1 = (TREE_CODE (c1) == PRED_CONSTR); - bool skip2 = (TREE_CODE (c2) == PRED_CONSTR); - - int len1 = (a1 ? TREE_VEC_LENGTH (a1) : 0) - skip1; - int len2 = (a2 ? TREE_VEC_LENGTH (a2) : 0) - skip2; - + int len1 = TREE_VEC_LENGTH (a1); + int len2 = TREE_VEC_LENGTH (a2); if (len1 != len2) return false; - for (int i = 0; i < len1; ++i) - if (!cp_tree_equal (TREE_VEC_ELT (a1, i + skip1), - TREE_VEC_ELT (a2, i + skip2))) + /* Skip the first argument so we don't infinitely recurse. + Also, they may differ in template parameter index. */ + for (int i = 1; i < len1; ++i) + { + tree t1 = TREE_VEC_ELT (a1, i); + tree t2 = TREE_VEC_ELT (a2, i); + if (!template_args_equal (t1, t2)) return false; + } return true; } @@ -1492,40 +1580,139 @@ tsubst_predicate_constraint (tree t, tree args, return build_nt (PRED_CONSTR, result); } +/* Substitute into a check constraint. */ + +tree +tsubst_check_constraint (tree t, tree args, + tsubst_flags_t complain, tree in_decl) +{ + tree decl = CHECK_CONSTR_CONCEPT (t); + tree tmpl = DECL_TI_TEMPLATE (decl); + tree targs = CHECK_CONSTR_ARGS (t); + + /* Substitute through by building an template-id expression + and then substituting into that. */ + tree expr = build_nt(TEMPLATE_ID_EXPR, tmpl, targs); + ++processing_template_decl; + tree result = tsubst_expr (expr, args, complain, in_decl, false); + --processing_template_decl; + + if (result == error_mark_node) + return error_mark_node; + + /* Extract the results and rebuild the check constraint. */ + decl = DECL_TEMPLATE_RESULT (TREE_OPERAND (result, 0)); + args = TREE_OPERAND (result, 1); + + return build_nt (CHECK_CONSTR, decl, args); +} + /* Substitute into the conjunction of constraints. Returns error_mark_node if substitution into either operand fails. */ + tree -tsubst_conjunction (tree t, tree args, - tsubst_flags_t complain, tree in_decl) +tsubst_logical_operator (tree t, tree args, + tsubst_flags_t complain, tree in_decl) { tree t0 = TREE_OPERAND (t, 0); tree r0 = tsubst_constraint (t0, args, complain, in_decl); + if (r0 == error_mark_node) + return error_mark_node; tree t1 = TREE_OPERAND (t, 1); tree r1 = tsubst_constraint (t1, args, complain, in_decl); - return build_nt (CONJ_CONSTR, r0, r1); -} - -/* Substitute ARGS into the constraint T. */ -tree -tsubst_constraint (tree t, tree args, tsubst_flags_t complain, tree in_decl) -{ - if (t == NULL_TREE) - return t; - if (TREE_CODE (t) == CONJ_CONSTR) - return tsubst_conjunction (t, args, complain, in_decl); - else if (TREE_CODE (t) == PRED_CONSTR) - return tsubst_predicate_constraint (t, args, complain, in_decl); - else - gcc_unreachable (); - return error_mark_node; + if (r1 == error_mark_node) + return error_mark_node; + return build_nt (TREE_CODE (t), r0, r1); } namespace { +/* Substitute ARGS into the expression constraint T. */ + +tree +tsubst_expr_constr (tree t, tree args, tsubst_flags_t complain, tree in_decl) +{ + cp_unevaluated guard; + tree expr = EXPR_CONSTR_EXPR (t); + tree ret = tsubst_expr (expr, args, complain, in_decl, false); + if (ret == error_mark_node) + return error_mark_node; + return build_nt (EXPR_CONSTR, ret); +} + +/* Substitute ARGS into the type constraint T. */ + +tree +tsubst_type_constr (tree t, tree args, tsubst_flags_t complain, tree in_decl) +{ + tree type = TYPE_CONSTR_TYPE (t); + tree ret = tsubst (type, args, complain, in_decl); + if (ret == error_mark_node) + return error_mark_node; + return build_nt (TYPE_CONSTR, ret); +} + +/* Substitute ARGS into the implicit conversion constraint T. */ + +tree +tsubst_implicit_conversion_constr (tree t, tree args, tsubst_flags_t complain, + tree in_decl) +{ + cp_unevaluated guard; + tree expr = ICONV_CONSTR_EXPR (t); + tree type = ICONV_CONSTR_TYPE (t); + tree new_expr = tsubst_expr (expr, args, complain, in_decl, false); + if (new_expr == error_mark_node) + return error_mark_node; + tree new_type = tsubst (type, args, complain, in_decl); + if (new_type == error_mark_node) + return error_mark_node; + return build_nt (ICONV_CONSTR, new_expr, new_type); +} + +/* Substitute ARGS into the argument deduction constraint T. */ + +tree +tsubst_argument_deduction_constr (tree t, tree args, tsubst_flags_t complain, + tree in_decl) +{ + cp_unevaluated guard; + tree expr = DEDUCT_CONSTR_EXPR (t); + tree pattern = DEDUCT_CONSTR_PATTERN (t); + tree autos = DEDUCT_CONSTR_PLACEHOLDER(t); + tree new_expr = tsubst_expr (expr, args, complain, in_decl, false); + if (new_expr == error_mark_node) + return error_mark_node; + /* It seems like substituting through the pattern will not affect the + placeholders. We should (?) be able to reuse the existing list + without any problems. If not, then we probably want to create a + new list of placeholders and then instantiate the pattern using + those. */ + tree new_pattern = tsubst (pattern, args, complain, in_decl); + if (new_pattern == error_mark_node) + return error_mark_node; + return build_nt (DEDUCT_CONSTR, new_expr, new_pattern, autos); +} + +/* Substitute ARGS into the exception constraint T. */ + +tree +tsubst_exception_constr (tree t, tree args, tsubst_flags_t complain, + tree in_decl) +{ + cp_unevaluated guard; + tree expr = EXCEPT_CONSTR_EXPR (t); + tree ret = tsubst_expr (expr, args, complain, in_decl, false); + if (ret == error_mark_node) + return error_mark_node; + return build_nt (EXCEPT_CONSTR, ret); +} + /* A subroutine of tsubst_constraint_variables. Register local specializations for each of parameter in PARMS and its corresponding substituted constraint variable in VARS. Returns VARS. */ + tree declare_constraint_vars (tree parms, tree vars) { @@ -1553,6 +1740,7 @@ declare_constraint_vars (tree parms, tree vars) Note that the caller must establish a local specialization stack prior to calling this function since this substitution will declare the substituted parameters. */ + tree tsubst_constraint_variables (tree t, tree args, tsubst_flags_t complain, tree in_decl) @@ -1568,10 +1756,29 @@ tsubst_constraint_variables (tree t, tree args, return declare_constraint_vars (t, vars); } +/* Substitute ARGS into the parameterized constraint T. */ + +tree +tsubst_parameterized_constraint (tree t, tree args, + tsubst_flags_t complain, tree in_decl) +{ + local_specialization_stack stack; + tree vars = tsubst_constraint_variables (PARM_CONSTR_PARMS (t), + args, complain, in_decl); + if (vars == error_mark_node) + return error_mark_node; + tree expr = tsubst_constraint (PARM_CONSTR_OPERAND (t), args, + complain, in_decl); + if (expr == error_mark_node) + return error_mark_node; + return build_nt (PARM_CONSTR, vars, expr); +} + /* Substitute ARGS into the simple requirement T. Note that substitution may result in an ill-formed expression without causing the program to be ill-formed. In such cases, the requirement wraps an error_mark_node. */ + inline tree tsubst_simple_requirement (tree t, tree args, tsubst_flags_t complain, tree in_decl) @@ -1627,6 +1834,8 @@ tsubst_nested_requirement (tree t, tree args, return finish_nested_requirement (expr); } +/* Substitute ARGS into the requirement T. */ + inline tree tsubst_requirement (tree t, tree args, tsubst_flags_t complain, tree in_decl) { @@ -1662,7 +1871,8 @@ tsubst_requirement_body (tree t, tree args, r = tree_cons (NULL_TREE, e, r); t = TREE_CHAIN (t); } - return r; + /* Ensure that the order of constraints is the same as the original. */ + return nreverse (r); } } /* namespace */ @@ -1696,6 +1906,7 @@ tsubst_requires_expr (tree t, tree args, /* Substitute ARGS into the constraint information CI, producing a new constraint record. */ + tree tsubst_constraint_info (tree t, tree args, tsubst_flags_t complain, tree in_decl) @@ -1714,6 +1925,39 @@ tsubst_constraint_info (tree t, tree args, return build_constraints (tmpl_constr, decl_constr); } +/* Substitute ARGS into the constraint T. */ + +tree +tsubst_constraint (tree t, tree args, tsubst_flags_t complain, tree in_decl) +{ + if (t == NULL_TREE) + return t; + switch (TREE_CODE (t)) + { + case PRED_CONSTR: + return tsubst_predicate_constraint (t, args, complain, in_decl); + case CHECK_CONSTR: + return tsubst_check_constraint (t, args, complain, in_decl); + case CONJ_CONSTR: + case DISJ_CONSTR: + return tsubst_logical_operator (t, args, complain, in_decl); + case PARM_CONSTR: + return tsubst_parameterized_constraint (t, args, complain, in_decl); + case EXPR_CONSTR: + return tsubst_expr_constr (t, args, complain, in_decl); + case TYPE_CONSTR: + return tsubst_type_constr (t, args, complain, in_decl); + case ICONV_CONSTR: + return tsubst_implicit_conversion_constr (t, args, complain, in_decl); + case DEDUCT_CONSTR: + return tsubst_argument_deduction_constr (t, args, complain, in_decl); + case EXCEPT_CONSTR: + return tsubst_exception_constr (t, args, complain, in_decl); + default: + gcc_unreachable (); + } + return error_mark_node; +} /*--------------------------------------------------------------------------- Constraint satisfaction @@ -1738,11 +1982,14 @@ satisfy_pack_expansion (tree t, tree args, gen_elem_of_pack_expansion_instantiation will check that each element of the expansion is satisfied. */ tree exprs = tsubst_pack_expansion (t, args, complain, in_decl); + if (exprs == error_mark_node) return boolean_false_node; - int n = TREE_VEC_LENGTH (exprs); - for (int i = 0; i < n; ++i) + /* TODO: It might be better to normalize each expanded term + and evaluate them separately. That would provide better + opportunities for diagnostics. */ + for (int i = 0; i < TREE_VEC_LENGTH (exprs); ++i) if (TREE_VEC_ELT (exprs, i) != boolean_true_node) return boolean_false_node; return boolean_true_node; @@ -1760,12 +2007,14 @@ tree satisfy_predicate_constraint (tree t, tree args, tsubst_flags_t complain, tree in_decl) { - tree original = TREE_OPERAND (t, 0); + tree expr = TREE_OPERAND (t, 0); /* We should never have a naked pack expansion in a predicate constraint. */ - gcc_assert (TREE_CODE (original) != EXPR_PACK_EXPANSION); + gcc_assert (TREE_CODE (expr) != EXPR_PACK_EXPANSION); - tree expr = tsubst_expr (original, args, complain, in_decl, false); + /* If substitution into the expression fails, the constraint + is not satisfied. */ + expr = tsubst_expr (expr, args, complain, in_decl, false); if (expr == error_mark_node) return boolean_false_node; @@ -1781,8 +2030,37 @@ satisfy_predicate_constraint (tree t, tree args, return boolean_false_node; } - tree value = cxx_constant_value (expr); - return value; + return cxx_constant_value (expr); +} + +/* A concept check constraint like C is satisfied if substituting ARGS + into CARGS succeeds and C is satisfied for the resulting arguments. */ + +tree +satisfy_check_constraint (tree t, tree args, + tsubst_flags_t complain, tree in_decl) +{ + tree decl = CHECK_CONSTR_CONCEPT (t); + tree tmpl = DECL_TI_TEMPLATE (decl); + tree cargs = CHECK_CONSTR_ARGS (t); + + /* Instantiate the concept check arguments. */ + tree targs = tsubst (cargs, args, tf_none, NULL_TREE); + if (targs == error_mark_node) + return boolean_false_node; + + /* Search for a previous value. */ + if (tree prev = lookup_concept_satisfaction (tmpl, targs)) + return prev; + + /* Expand the concept; failure here implies non-satisfaction. */ + tree def = expand_concept (decl, targs); + if (def == error_mark_node) + return memoize_concept_satisfaction (tmpl, args, boolean_false_node); + + /* Recursively satisfy the constraint. */ + tree result = satisfy_constraint_1 (def, targs, complain, in_decl); + return memoize_concept_satisfaction (tmpl, targs, result); } /* Check an expression constraint. The constraint is satisfied if @@ -1803,7 +2081,6 @@ satisfy_expression_constraint (tree t, tree args, return boolean_false_node; if (!perform_deferred_access_checks (tf_none)) return boolean_false_node; - return boolean_true_node; } @@ -1822,7 +2099,6 @@ satisfy_type_constraint (tree t, tree args, return boolean_false_node; if (!perform_deferred_access_checks (complain)) return boolean_false_node; - return boolean_true_node; } @@ -1932,11 +2208,8 @@ satisfy_conjunction (tree t, tree args, tsubst_flags_t complain, tree in_decl) { tree t0 = satisfy_constraint_1 (TREE_OPERAND (t, 0), args, complain, in_decl); if (t0 == boolean_false_node) - return t0; - tree t1 = satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl); - if (t1 == boolean_false_node) - return t1; - return boolean_true_node; + return boolean_false_node; + return satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl); } /* Check that the disjunction of constraints is satisfied. Note @@ -1949,10 +2222,7 @@ satisfy_disjunction (tree t, tree args, tsubst_flags_t complain, tree in_decl) tree t0 = satisfy_constraint_1 (TREE_OPERAND (t, 0), args, complain, in_decl); if (t0 == boolean_true_node) return boolean_true_node; - tree t1 = satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl); - if (t1 == boolean_true_node) - return boolean_true_node; - return boolean_false_node; + return satisfy_constraint_1 (TREE_OPERAND (t, 1), args, complain, in_decl); } /* Dispatch to an appropriate satisfaction routine depending on the @@ -1974,6 +2244,9 @@ satisfy_constraint_1 (tree t, tree args, tsubst_flags_t complain, tree in_decl) case PRED_CONSTR: return satisfy_predicate_constraint (t, args, complain, in_decl); + case CHECK_CONSTR: + return satisfy_check_constraint (t, args, complain, in_decl); + case EXPR_CONSTR: return satisfy_expression_constraint (t, args, complain, in_decl); @@ -2014,15 +2287,19 @@ satisfy_constraint_1 (tree t, tree args, tsubst_flags_t complain, tree in_decl) tree satisfy_constraint (tree t, tree args) { + auto_timevar time (TV_CONSTRAINT_SAT); + /* Turn off template processing. Constraint satisfaction only applies - to non-dependent terms, so we want full checking here. */ - processing_template_decl_sentinel sentinel (true); + to non-dependent terms, so we want to ensure full checking here. */ + processing_template_decl_sentinel proc (true); + /* Avoid early exit in tsubst and tsubst_copy from null args; since earlier substitution was done with processing_template_decl forced on, there will be expressions that still need semantic processing, possibly buried in decltype or a template argument. */ if (args == NULL_TREE) args = make_tree_vec (1); + return satisfy_constraint_1 (t, args, tf_none, NULL_TREE); } @@ -2042,11 +2319,13 @@ satisfy_associated_constraints (tree ci, tree args) if (args && uses_template_parms (args)) return boolean_true_node; - /* Invalid requirements cannot be satisfied. */ - if (!valid_constraints_p (ci)) - return boolean_false_node; + /* Check if we've seen a previous result. */ + if (tree prev = lookup_constraint_satisfaction (ci, args)) + return prev; - return satisfy_constraint (CI_NORMALIZED_CONSTRAINTS (ci), args); + /* Actually test for satisfaction. */ + tree result = satisfy_constraint (CI_ASSOCIATED_CONSTRAINTS (ci), args); + return memoize_constraint_satisfaction (ci, args, result); } } /* namespace */ @@ -2059,7 +2338,7 @@ tree evaluate_constraints (tree constr, tree args) { gcc_assert (constraint_p (constr)); - return satisfy_constraint (normalize_constraint (constr), args); + return satisfy_constraint (constr, args); } /* Evaluate the function concept FN by substituting its own args @@ -2070,14 +2349,7 @@ evaluate_constraints (tree constr, tree args) tree evaluate_function_concept (tree fn, tree args) { - ++processing_template_decl; - /* We lift using DECL_TI_ARGS because we want to delay producing - non-dependent expressions until we're doing satisfaction. We can't just - go without any substitution because we need to lower the level of 'auto's - in type deduction constraints. */ - tree constr = transform_expression (lift_function_definition - (fn, DECL_TI_ARGS (fn))); - --processing_template_decl; + tree constr = build_nt (CHECK_CONSTR, fn, args); return satisfy_constraint (constr, args); } @@ -2087,12 +2359,9 @@ evaluate_function_concept (tree fn, tree args) boolean_false_node otherwise. */ tree -evaluate_variable_concept (tree decl, tree args) +evaluate_variable_concept (tree var, tree args) { - ++processing_template_decl; - tree constr = transform_expression (lift_variable_initializer - (decl, DECL_TI_ARGS (decl))); - --processing_template_decl; + tree constr = build_nt (CHECK_CONSTR, var, args); return satisfy_constraint (constr, args); } @@ -2103,9 +2372,7 @@ evaluate_variable_concept (tree decl, tree args) tree evaluate_constraint_expression (tree expr, tree args) { - ++processing_template_decl; - tree constr = transform_expression (lift_expression (expr)); - --processing_template_decl; + tree constr = normalize_expression (expr); return satisfy_constraint (constr, args); } @@ -2167,7 +2434,6 @@ constraint_expression_satisfied_p (tree expr, tree args) } /* namespace */ - /*--------------------------------------------------------------------------- Semantic analysis of requires-expressions ---------------------------------------------------------------------------*/ @@ -2311,6 +2577,7 @@ equivalently_constrained (tree d1, tree d2) ---------------------------------------------------------------------------*/ /* Returns true when the the constraints in A subsume those in B. */ + bool subsumes_constraints (tree a, tree b) { @@ -2334,6 +2601,7 @@ strictly_subsumes (tree a, tree b) Returns 1 if A is more constrained than B, -1 if B is more constrained than A, and 0 otherwise. */ + int more_constrained (tree d1, tree d2) { @@ -2350,6 +2618,7 @@ more_constrained (tree d1, tree d2) /* Returns true if D1 is at least as constrained as D2. That is, the associated constraints of D1 subsume those of D2, or both declarations are unconstrained. */ + bool at_least_as_constrained (tree d1, tree d2) { @@ -2361,49 +2630,71 @@ at_least_as_constrained (tree d1, tree d2) /*--------------------------------------------------------------------------- Constraint diagnostics + +FIXME: Normalize expressions into constraints before evaluating them. +This should be the general pattern for all such diagnostics. ---------------------------------------------------------------------------*/ -/* The diagnosis of constraints performs a combination of - normalization and satisfaction testing. We recursively - walk through the conjunction (or disjunctions) of associated - constraints, testing each sub-expression in turn. +/* The number of detailed constraint failures. */ - We currently restrict diagnostics to just the top-level - conjunctions within the associated constraints. A fully - recursive walk is possible, but it can generate a lot - of errors. */ +int constraint_errors = 0; +/* Do not generate errors after diagnosing this number of constraint + failures. + + FIXME: This is a really arbitrary number. Provide better control of + constraint diagnostics with a command line option. */ + +int constraint_thresh = 20; + + +/* Returns true if we should elide the diagnostic for a constraint failure. + This is the case when the number of errors has exceeded the pre-configured + threshold. */ + +inline bool +elide_constraint_failure_p () +{ + bool ret = constraint_thresh <= constraint_errors; + ++constraint_errors; + return ret; +} + +/* Returns the number of undiagnosed errors. */ + +inline int +undiagnosed_constraint_failures () +{ + return constraint_errors - constraint_thresh; +} + +/* The diagnosis of constraints performs a combination of normalization + and satisfaction testing. We recursively walk through the conjunction or + disjunction of associated constraints, testing each sub-constraint in + turn. */ namespace { -void diagnose_expression (location_t, tree, tree); -void diagnose_constraint (location_t, tree, tree); +void diagnose_constraint (location_t, tree, tree, tree); -/* Diagnose a conjunction of constraints. */ -void -diagnose_logical_operation (location_t loc, tree t, tree args) -{ - diagnose_expression (loc, TREE_OPERAND (t, 0), args); - diagnose_expression (loc, TREE_OPERAND (t, 0), args); -} +/* Emit a specific diagnostics for a failed trait. */ -/* Determine if the trait expression T is satisfied by ARGS. - Emit a precise diagnostic if it is not. */ void -diagnose_trait_expression (location_t loc, tree t, tree args) +diagnose_trait_expression (location_t loc, tree, tree cur, tree args) { - if (constraint_expression_satisfied_p (t, args)) + if (constraint_expression_satisfied_p (cur, args)) + return; + if (elide_constraint_failure_p()) return; - /* Rebuild the trait expression so we can diagnose the - specific failure. */ + tree expr = PRED_CONSTR_EXPR (cur); ++processing_template_decl; - tree expr = tsubst_expr (t, args, tf_none, NULL_TREE, false); + expr = tsubst_expr (expr, args, tf_none, NULL_TREE, false); --processing_template_decl; tree t1 = TRAIT_EXPR_TYPE1 (expr); tree t2 = TRAIT_EXPR_TYPE2 (expr); - switch (TRAIT_EXPR_KIND (t)) + switch (TRAIT_EXPR_KIND (expr)) { case CPTK_HAS_NOTHROW_ASSIGN: inform (loc, " %qT is not nothrow copy assignable", t1); @@ -2473,93 +2764,52 @@ diagnose_trait_expression (location_t loc, tree t, tree args) } } -/* Determine if the call expression T, when normalized as a constraint, - is satisfied by ARGS. +/* Diagnose the expression of a predicate constraint. */ - TODO: If T is refers to a concept, We could recursively analyze - its definition to identify the exact failure, but that could - emit a *lot* of error messages (defeating the purpose of - improved diagnostics). Consider adding a flag to control the - depth of diagnostics. */ void -diagnose_call_expression (location_t loc, tree t, tree args) +diagnose_other_expression (location_t loc, tree, tree cur, tree args) { - if (constraint_expression_satisfied_p (t, args)) + if (constraint_expression_satisfied_p (cur, args)) return; - - /* Rebuild the expression for the purpose of diagnostics. */ - ++processing_template_decl; - tree expr = tsubst_expr (t, args, tf_none, NULL_TREE, false); - --processing_template_decl; - - /* If the function call is known to be a concept check, then - diagnose it differently (i.e., we may recurse). */ - if (resolve_constraint_check (t)) - inform (loc, " concept %qE was not satisfied", expr); - else - inform (loc, " %qE evaluated to false", expr); -} - -/* Determine if the template-id T, when normalized as a constraint - is satisfied by ARGS. */ -void -diagnose_template_id (location_t loc, tree t, tree args) -{ - /* Check for invalid template-ids. */ - if (!variable_template_p (TREE_OPERAND (t, 0))) - { - inform (loc, " invalid constraint %qE", t); - return; - } - - if (constraint_expression_satisfied_p (t, args)) + if (elide_constraint_failure_p()) return; + inform (loc, "%qE evaluated to false", cur); +} - /* Rebuild the expression for the purpose of diagnostics. */ - ++processing_template_decl; - tree expr = tsubst_expr (t, args, tf_none, NULL_TREE, false); - --processing_template_decl; +/* Do our best to infer meaning from predicates. */ - tree var = DECL_TEMPLATE_RESULT (TREE_OPERAND (t, 0)); - if (DECL_DECLARED_CONCEPT_P (var)) - inform (loc, " concept %qE was not satisfied", expr); +inline void +diagnose_predicate_constraint (location_t loc, tree orig, tree cur, tree args) +{ + if (TREE_CODE (PRED_CONSTR_EXPR (cur)) == TRAIT_EXPR) + diagnose_trait_expression (loc, orig, cur, args); else - inform (loc, " %qE evaluated to false", expr); + diagnose_other_expression (loc, orig, cur, args); } -/* Determine if the requires-expression, when normalized as a - constraint is satisfied by ARGS. +/* Diagnose a failed pack expansion, possibly containing constraints. */ - TODO: Build sets of expressions, types, and constraints - based on the requirements in T and emit specific diagnostics - for those. */ void -diagnose_requires_expression (location_t loc, tree t, tree args) +diagnose_pack_expansion (location_t loc, tree, tree cur, tree args) { - if (constraint_expression_satisfied_p (t, args)) + if (constraint_expression_satisfied_p (cur, args)) return; - inform (loc, "requirements not satisfied"); -} - -void -diagnose_pack_expansion (location_t loc, tree t, tree args) -{ - if (constraint_expression_satisfied_p (t, args)) + if (elide_constraint_failure_p()) return; /* Make sure that we don't have naked packs that we don't expect. */ - if (!same_type_p (TREE_TYPE (t), boolean_type_node)) + if (!same_type_p (TREE_TYPE (cur), boolean_type_node)) { - inform (loc, "invalid pack expansion in constraint %qE", t); + inform (loc, "invalid pack expansion in constraint %qE", cur); return; } - inform (loc, " in the expansion of %qE", t); + inform (loc, "in the expansion of %qE", cur); /* Get the vector of expanded arguments. Note that n must not be 0 since this constraint is not satisfied. */ ++processing_template_decl; - tree exprs = tsubst_pack_expansion (t, args, tf_none, NULL_TREE); + tree exprs = tsubst_pack_expansion (cur, args, tf_none, NULL_TREE); --processing_template_decl; if (exprs == error_mark_node) { @@ -2578,82 +2828,276 @@ diagnose_pack_expansion (location_t loc, tree t, tree args) } } -/* Diagnose an expression that would be characterized as - a predicate constraint. */ +/* Diagnose a potentially unsatisfied concept check constraint DECL. + Parameters are as for diagnose_constraint. */ + void -diagnose_other_expression (location_t loc, tree t, tree args) +diagnose_check_constraint (location_t loc, tree orig, tree cur, tree args) { - if (constraint_expression_satisfied_p (t, args)) + if (constraints_satisfied_p (cur, args)) return; - inform (loc, " %qE evaluated to false", t); + + tree decl = CHECK_CONSTR_CONCEPT (cur); + tree cargs = CHECK_CONSTR_ARGS (cur); + tree tmpl = DECL_TI_TEMPLATE (decl); + tree check = build_nt (CHECK_CONSTR, decl, cargs); + + /* Instantiate the concept check arguments. */ + tree targs = tsubst (cargs, args, tf_none, NULL_TREE); + if (targs == error_mark_node) + { + if (elide_constraint_failure_p ()) + return; + inform (loc, "invalid use of the concept %qE", check); + tsubst (cargs, args, tf_warning_or_error, NULL_TREE); + return; + } + + tree sub = build_tree_list (tmpl, targs); + /* Update to the expanded definitions. */ + cur = expand_concept (decl, targs); + if (cur == error_mark_node) + { + if (elide_constraint_failure_p ()) + return; + inform (loc, "in the expansion of concept %qE %S", check, sub); + cur = get_concept_definition (decl); + tsubst_expr (cur, targs, tf_warning_or_error, NULL_TREE, false); + return; + } + + orig = get_concept_definition (CHECK_CONSTR_CONCEPT (orig)); + orig = normalize_expression (orig); + + location_t dloc = DECL_SOURCE_LOCATION (decl); + inform (dloc, "within %qS", sub); + diagnose_constraint (dloc, orig, cur, targs); } +/* Diagnose a potentially unsatisfied conjunction or disjunction. Parameters + are as for diagnose_constraint. */ + void -diagnose_expression (location_t loc, tree t, tree args) +diagnose_logical_constraint (location_t loc, tree orig, tree cur, tree args) { - switch (TREE_CODE (t)) - { - case TRUTH_ANDIF_EXPR: - diagnose_logical_operation (loc, t, args); - break; + tree t0 = TREE_OPERAND (cur, 0); + tree t1 = TREE_OPERAND (cur, 1); + if (!constraints_satisfied_p (t0, args)) + diagnose_constraint (loc, TREE_OPERAND (orig, 0), t0, args); + else if (TREE_CODE (orig) == TRUTH_ORIF_EXPR) + return; + if (!constraints_satisfied_p (t1, args)) + diagnose_constraint (loc, TREE_OPERAND (orig, 1), t1, args); +} - case TRUTH_ORIF_EXPR: - diagnose_logical_operation (loc, t, args); - break; +/* Diagnose a potential expression constraint failure. */ - case CALL_EXPR: - diagnose_call_expression (loc, t, args); - break; +void +diagnose_expression_constraint (location_t loc, tree orig, tree cur, tree args) +{ + if (constraints_satisfied_p (cur, args)) + return; + if (elide_constraint_failure_p()) + return; - case TEMPLATE_ID_EXPR: - diagnose_template_id (loc, t, args); - break; + tree expr = EXPR_CONSTR_EXPR (orig); + inform (loc, "the required expression %qE would be ill-formed", expr); - case REQUIRES_EXPR: - diagnose_requires_expression (loc, t, args); - break; + // TODO: We should have a flag that controls this substitution. + // I'm finding it very useful for resolving concept check errors. - case TRAIT_EXPR: - diagnose_trait_expression (loc, t, args); - break; + // inform (input_location, "==== BEGIN DUMP ===="); + // tsubst_expr (EXPR_CONSTR_EXPR (orig), args, tf_warning_or_error, NULL_TREE, false); + // inform (input_location, "==== END DUMP ===="); +} - case EXPR_PACK_EXPANSION: - diagnose_pack_expansion (loc, t, args); - break; +/* Diagnose a potentially failed type constraint. */ - default: - diagnose_other_expression (loc, t, args); - break; +void +diagnose_type_constraint (location_t loc, tree orig, tree cur, tree args) +{ + if (constraints_satisfied_p (cur, args)) + return; + if (elide_constraint_failure_p()) + return; + + tree type = TYPE_CONSTR_TYPE (orig); + inform (loc, "the required type %qT would be ill-formed", type); +} + +/* Diagnose a potentially unsatisfied conversion constraint. */ + +void +diagnose_implicit_conversion_constraint (location_t loc, tree orig, tree cur, + tree args) +{ + if (constraints_satisfied_p (cur, args)) + return; + + /* The expression and type will previously have been substituted into, + and therefore may already be an error. Also, we will have already + diagnosed substitution failures into an expression since this must be + part of a compound requirement. */ + tree expr = ICONV_CONSTR_EXPR (cur); + if (error_operand_p (expr)) + return; + + /* Don't elide a previously diagnosed failure. */ + if (elide_constraint_failure_p()) + return; + + tree type = ICONV_CONSTR_TYPE (cur); + if (error_operand_p (type)) + { + inform (loc, "substitution into type %qT failed", + ICONV_CONSTR_TYPE (orig)); + return; } + + inform(loc, "%qE is not implicitly convertible to %qT", expr, type); } -inline void -diagnose_predicate_constraint (location_t loc, tree t, tree args) +/* Diagnose an argument deduction constraint. */ + +void +diagnose_argument_deduction_constraint (location_t loc, tree orig, tree cur, + tree args) { - diagnose_expression (loc, PRED_CONSTR_EXPR (t), args); + if (constraints_satisfied_p (cur, args)) + return; + + /* The expression and type will previously have been substituted into, + and therefore may already be an error. Also, we will have already + diagnosed substution failures into an expression since this must be + part of a compound requirement. */ + tree expr = DEDUCT_CONSTR_EXPR (cur); + if (error_operand_p (expr)) + return; + + /* Don't elide a previously diagnosed failure. */ + if (elide_constraint_failure_p ()) + return; + + tree pattern = DEDUCT_CONSTR_PATTERN (cur); + if (error_operand_p (pattern)) + { + inform (loc, "substitution into type %qT failed", + DEDUCT_CONSTR_PATTERN (orig)); + return; + } + + inform (loc, "unable to deduce placeholder type %qT from %qE", + pattern, expr); } -inline void -diagnose_conjunction (location_t loc, tree t, tree args) +/* Diagnose an exception constraint. */ + +void +diagnose_exception_constraint (location_t loc, tree orig, tree cur, tree args) { - diagnose_constraint (loc, TREE_OPERAND (t, 0), args); - diagnose_constraint (loc, TREE_OPERAND (t, 1), args); + if (constraints_satisfied_p (cur, args)) + return; + if (elide_constraint_failure_p ()) + return; + + /* Rebuild a noexcept expression. */ + tree expr = EXCEPT_CONSTR_EXPR (cur); + if (error_operand_p (expr)) + return; + + inform (loc, "%qE evaluated to false", EXCEPT_CONSTR_EXPR (orig)); } -/* Diagnose the constraint T for the given ARGS. This is only - ever invoked on the associated constraints, so we can - only have conjunctions of predicate constraints. */ +/* Diagnose a potentially unsatisfied parameterized constraint. */ + void -diagnose_constraint (location_t loc, tree t, tree args) +diagnose_parameterized_constraint (location_t loc, tree orig, tree cur, + tree args) { - switch (TREE_CODE (t)) + if (constraints_satisfied_p (cur, args)) + return; + + local_specialization_stack stack; + tree parms = PARM_CONSTR_PARMS (cur); + tree vars = tsubst_constraint_variables (parms, args, tf_warning_or_error, + NULL_TREE); + if (vars == error_mark_node) { + if (elide_constraint_failure_p ()) + return; + + /* TODO: Check which variable failed and use orig to diagnose + that substitution error. */ + inform (loc, "failed to instantiate constraint variables"); + return; + } + + /* TODO: It would be better write these in a list. */ + while (vars) + { + inform (loc, " with %q#D", vars); + vars = TREE_CHAIN (vars); + } + orig = PARM_CONSTR_OPERAND (orig); + cur = PARM_CONSTR_OPERAND (cur); + return diagnose_constraint (loc, orig, cur, args); +} + +/* Diagnose the constraint CUR for the given ARGS. This is only ever invoked + on the associated constraints, so we can only have conjunctions of + predicate constraints. The ORIGinal (dependent) constructs follow + the current constraints to enable better diagnostics. Note that ORIG + and CUR must be the same kinds of node, except when CUR is an error. */ + +void +diagnose_constraint (location_t loc, tree orig, tree cur, tree args) +{ + switch (TREE_CODE (cur)) + { + case EXPR_CONSTR: + diagnose_expression_constraint (loc, orig, cur, args); + break; + + case TYPE_CONSTR: + diagnose_type_constraint (loc, orig, cur, args); + break; + + case ICONV_CONSTR: + diagnose_implicit_conversion_constraint (loc, orig, cur, args); + break; + + case DEDUCT_CONSTR: + diagnose_argument_deduction_constraint (loc, orig, cur, args); + break; + + case EXCEPT_CONSTR: + diagnose_exception_constraint (loc, orig, cur, args); + break; + case CONJ_CONSTR: - diagnose_conjunction (loc, t, args); + case DISJ_CONSTR: + diagnose_logical_constraint (loc, orig, cur, args); break; case PRED_CONSTR: - diagnose_predicate_constraint (loc, t, args); + diagnose_predicate_constraint (loc, orig, cur, args); + break; + + case PARM_CONSTR: + diagnose_parameterized_constraint (loc, orig, cur, args); + break; + + case CHECK_CONSTR: + diagnose_check_constraint (loc, orig, cur, args); + break; + + case EXPR_PACK_EXPANSION: + diagnose_pack_expansion (loc, orig, cur, args); + break; + + case ERROR_MARK: + /* TODO: Can we improve the diagnostic with the original? */ + inform (input_location, "ill-formed constraint"); break; default: @@ -2678,16 +3122,10 @@ diagnose_declaration_constraints (location_t loc, tree decl, tree args) args = TI_ARGS (ti); } - /* Check that the constraints are actually valid. */ - tree ci = get_constraints (decl); - if (!valid_constraints_p (ci)) - { - inform (loc, " invalid constraints"); - return; - } - /* Recursively diagnose the associated constraints. */ - diagnose_constraint (loc, CI_ASSOCIATED_CONSTRAINTS (ci), args); + tree ci = get_constraints (decl); + tree t = CI_ASSOCIATED_CONSTRAINTS (ci); + diagnose_constraint (loc, t, t, args); } } // namespace @@ -2699,8 +3137,17 @@ diagnose_declaration_constraints (location_t loc, tree decl, tree args) void diagnose_constraints (location_t loc, tree t, tree args) { + constraint_errors = 0; + if (constraint_p (t)) - diagnose_constraint (loc, t, args); - else + diagnose_constraint (loc, t, t, args); + else if (DECL_P (t)) diagnose_declaration_constraints (loc, t, args); + else + gcc_unreachable (); + + /* Note the number of elided failures. */ + int n = undiagnosed_constraint_failures (); + if (n > 0) + inform (loc, "... and %d more constraint errors not shown", n); } diff --git a/gcc/cp/cp-tree.def b/gcc/cp/cp-tree.def index e6e5139..6cb5a69 100644 --- a/gcc/cp/cp-tree.def +++ b/gcc/cp/cp-tree.def @@ -536,6 +536,14 @@ DEFTREECODE (NESTED_REQ, "nested_req", tcc_expression, 1) PRED_CONSTR_EXPR has the expression to be evaluated. */ DEFTREECODE (PRED_CONSTR, "pred_constr", tcc_expression, 1) +/* A check constraint represents the checking of a concept + C. It has two operands: the template defining the concept + and a sequence of template arguments. + + CHECK_CONSTR_CONCEPT has the concept definition + CHECK_CONSTR_ARGUMENTS are the template arguments */ +DEFTREECODE (CHECK_CONSTR, "check_constr", tcc_expression, 2) + /* An expression constraint determines the validity of a expression E. EXPR_CONST_EXPR has the expression being validated. */ @@ -560,7 +568,7 @@ DEFTREECODE (ICONV_CONSTR, "iconv_constr", tcc_expression, 2) T must contain at least one place holder. DEDUCT_CONSTR_EXPR has the expression E - DEDUCT_CONSTR_PATTERN has the type patter T. + DEDUCT_CONSTR_PATTERN has the type pattern T. DEDUCT_CONSTR_PLACEHOLDERS has the list of placeholder nodes in T. */ DEFTREECODE (DEDUCT_CONSTR, "deduct_constr", tcc_expression, 3) diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h index 7e84036..76616c6 100644 --- a/gcc/cp/cp-tree.h +++ b/gcc/cp/cp-tree.h @@ -893,10 +893,6 @@ struct GTY(()) tree_template_info { // - a constraint expression introduced by a function declarator // - the associated constraints, which are the conjunction of those, // and used for declaration matching -// - the cached normalized associated constraints which are used -// to support satisfaction and subsumption. -// - assumptions which is the result of decomposing the normalized -// constraints. // // The template and declarator requirements are kept to support pretty // printing constrained declarations. @@ -905,8 +901,6 @@ struct GTY(()) tree_constraint_info { tree template_reqs; tree declarator_reqs; tree associated_constr; - tree normalized_constr; - tree assumptions; }; // Require that pointer P is non-null before returning. @@ -945,14 +939,6 @@ check_constraint_info (tree t) #define CI_ASSOCIATED_CONSTRAINTS(NODE) \ check_constraint_info (check_nonnull(NODE))->associated_constr -// The normalized associated constraints. -#define CI_NORMALIZED_CONSTRAINTS(NODE) \ - check_constraint_info (check_nonnull(NODE))->normalized_constr - -// Get the set of assumptions associated with the constraint info node. -#define CI_ASSUMPTIONS(NODE) \ - check_constraint_info (check_nonnull(NODE))->assumptions - // Access the logical constraints on the template parameters introduced // at a given template parameter list level indicated by NODE. #define TEMPLATE_PARMS_CONSTRAINTS(NODE) \ @@ -976,6 +962,14 @@ check_constraint_info (tree t) #define PRED_CONSTR_EXPR(NODE) \ TREE_OPERAND (TREE_CHECK (NODE, PRED_CONSTR), 0) +/* The concept of a concept check. */ +#define CHECK_CONSTR_CONCEPT(NODE) \ + TREE_OPERAND (TREE_CHECK (NODE, CHECK_CONSTR), 0) + +/* The template arguments of a concept check. */ +#define CHECK_CONSTR_ARGS(NODE) \ + TREE_OPERAND (TREE_CHECK (NODE, CHECK_CONSTR), 1) + /* The expression validated by the predicate constraint. */ #define EXPR_CONSTR_EXPR(NODE) \ TREE_OPERAND (TREE_CHECK (NODE, EXPR_CONSTR), 0) @@ -6118,6 +6112,7 @@ extern bool is_specialization_of_friend (tree, tree); extern tree get_pattern_parm (tree, tree); extern int comp_template_args (tree, tree, tree * = NULL, tree * = NULL); +extern int template_args_equal (tree, tree); extern tree maybe_process_partial_specialization (tree); extern tree most_specialized_instantiation (tree); extern void print_candidates (tree); @@ -6848,10 +6843,8 @@ extern tree strip_using_decl (tree); /* in constraint.cc */ extern void init_constraint_processing (); extern bool constraint_p (tree); -extern tree make_predicate_constraint (tree); extern tree conjoin_constraints (tree, tree); extern tree conjoin_constraints (tree); -extern bool valid_constraints_p (tree); extern tree get_constraints (tree); extern void set_constraints (tree, tree); extern void remove_constraints (tree); @@ -6882,13 +6875,23 @@ extern tree tsubst_requires_expr (tree, tree, tsubst_flags_t, tre extern tree tsubst_constraint (tree, tree, tsubst_flags_t, tree); extern tree tsubst_constraint_info (tree, tree, tsubst_flags_t, tree); extern bool function_concept_check_p (tree); - +extern tree normalize_expression (tree); +extern tree expand_concept (tree, tree); +extern bool expanding_concept (); extern tree evaluate_constraints (tree, tree); extern tree evaluate_function_concept (tree, tree); extern tree evaluate_variable_concept (tree, tree); extern tree evaluate_constraint_expression (tree, tree); extern bool constraints_satisfied_p (tree); extern bool constraints_satisfied_p (tree, tree); +extern tree lookup_constraint_satisfaction (tree, tree); +extern tree memoize_constraint_satisfaction (tree, tree, tree); +extern tree lookup_concept_satisfaction (tree, tree); +extern tree memoize_concept_satisfaction (tree, tree, tree); +extern tree get_concept_expansion (tree, tree); +extern tree save_concept_expansion (tree, tree, tree); +extern bool* lookup_subsumption_result (tree, tree); +extern bool save_subsumption_result (tree, tree, bool); extern bool equivalent_constraints (tree, tree); extern bool equivalently_constrained (tree, tree); @@ -6899,7 +6902,6 @@ extern int more_constrained (tree, tree); extern void diagnose_constraints (location_t, tree, tree); /* in logic.cc */ -extern tree decompose_assumptions (tree); extern tree decompose_conclusions (tree); extern bool subsumes (tree, tree); diff --git a/gcc/cp/cxx-pretty-print.c b/gcc/cp/cxx-pretty-print.c index 3b52a35..192b26c 100644 --- a/gcc/cp/cxx-pretty-print.c +++ b/gcc/cp/cxx-pretty-print.c @@ -35,6 +35,9 @@ static void pp_cxx_parameter_declaration_clause (cxx_pretty_printer *, tree); static void pp_cxx_template_parameter (cxx_pretty_printer *, tree); static void pp_cxx_cast_expression (cxx_pretty_printer *, tree); static void pp_cxx_typeid_expression (cxx_pretty_printer *, tree); +static void pp_cxx_unary_left_fold_expression (cxx_pretty_printer *, tree); +static void pp_cxx_unary_right_fold_expression (cxx_pretty_printer *, tree); +static void pp_cxx_binary_fold_expression (cxx_pretty_printer *, tree); static inline void @@ -1139,6 +1142,19 @@ cxx_pretty_printer::expression (tree t) pp_cxx_ws_string (this, "..."); break; + case UNARY_LEFT_FOLD_EXPR: + pp_cxx_unary_left_fold_expression (this, t); + break; + + case UNARY_RIGHT_FOLD_EXPR: + pp_cxx_unary_right_fold_expression (this, t); + break; + + case BINARY_LEFT_FOLD_EXPR: + case BINARY_RIGHT_FOLD_EXPR: + pp_cxx_binary_fold_expression (this, t); + break; + case TEMPLATE_ID_EXPR: pp_cxx_template_id (this, t); break; @@ -1165,6 +1181,7 @@ cxx_pretty_printer::expression (tree t) break; case PRED_CONSTR: + case CHECK_CONSTR: case EXPR_CONSTR: case TYPE_CONSTR: case ICONV_CONSTR: @@ -2198,6 +2215,11 @@ void pp_cxx_constrained_type_spec (cxx_pretty_printer *pp, tree c) { tree t, a; + if (c == error_mark_node) + { + pp_cxx_ws_string(pp, ""); + return; + } placeholder_extract_concept_and_args (c, t, a); pp->id_expression (t); if (TREE_VEC_LENGTH (a) > 1) @@ -2407,6 +2429,102 @@ pp_cxx_offsetof_expression (cxx_pretty_printer *pp, tree t) pp_cxx_right_paren (pp); } +static char const* +get_fold_operator (tree t) +{ + int op = int_cst_value (FOLD_EXPR_OP (t)); + if (FOLD_EXPR_MODIFY_P (t)) + { + switch (op) + { + case NOP_EXPR: return "="; + case PLUS_EXPR: return "+="; + case MINUS_EXPR: return "-="; + case MULT_EXPR: return "*="; + case TRUNC_DIV_EXPR: return "/="; + case TRUNC_MOD_EXPR: return "%="; + case BIT_XOR_EXPR: return "^="; + case BIT_AND_EXPR: return "&="; + case BIT_IOR_EXPR: return "|="; + case LSHIFT_EXPR: return "<<="; + case RSHIFT_EXPR: return ">>="; + default: gcc_unreachable (); + } + } + else + { + switch (op) + { + case PLUS_EXPR: return "+"; + case MINUS_EXPR: return "-"; + case MULT_EXPR: return "*"; + case TRUNC_DIV_EXPR: return "/"; + case TRUNC_MOD_EXPR: return "%"; + case BIT_XOR_EXPR: return "^"; + case BIT_AND_EXPR: return "&"; + case BIT_IOR_EXPR: return "|"; + case LSHIFT_EXPR: return "<<"; + case RSHIFT_EXPR: return ">>"; + case EQ_EXPR: return "=="; + case NE_EXPR: return "!="; + case LT_EXPR: return "<"; + case GT_EXPR: return ">"; + case LE_EXPR: return "<="; + case GE_EXPR: return ">="; + case TRUTH_ANDIF_EXPR: return "&&"; + case TRUTH_ORIF_EXPR: return "||"; + case MEMBER_REF: return "->*"; + case DOTSTAR_EXPR: return ".*"; + case OFFSET_REF: return ".*"; + default: return ","; /* FIXME: Not the right default. */ + } + } +} + +void +pp_cxx_unary_left_fold_expression (cxx_pretty_printer *pp, tree t) +{ + char const* op = get_fold_operator (t); + tree expr = PACK_EXPANSION_PATTERN (FOLD_EXPR_PACK (t)); + pp_cxx_left_paren (pp); + pp_cxx_ws_string (pp, "..."); + pp_cxx_ws_string (pp, op); + pp->expression (expr); + pp_cxx_right_paren (pp); +} + +void +pp_cxx_unary_right_fold_expression (cxx_pretty_printer *pp, tree t) +{ + char const* op = get_fold_operator (t); + tree expr = PACK_EXPANSION_PATTERN (FOLD_EXPR_PACK (t)); + pp_cxx_left_paren (pp); + pp->expression (expr); + pp_space (pp); + pp_cxx_ws_string (pp, op); + pp_cxx_ws_string (pp, "..."); + pp_cxx_right_paren (pp); +} + +void +pp_cxx_binary_fold_expression (cxx_pretty_printer *pp, tree t) +{ + char const* op = get_fold_operator (t); + tree t1 = TREE_OPERAND (t, 1); + tree t2 = TREE_OPERAND (t, 2); + if (t1 == FOLD_EXPR_PACK (t)) + t1 = PACK_EXPANSION_PATTERN (t1); + else + t2 = PACK_EXPANSION_PATTERN (t2); + pp_cxx_left_paren (pp); + pp->expression (t1); + pp_cxx_ws_string (pp, op); + pp_cxx_ws_string (pp, "..."); + pp_cxx_ws_string (pp, op); + pp->expression (t2); + pp_cxx_right_paren (pp); +} + void pp_cxx_trait_expression (cxx_pretty_printer *pp, tree t) { @@ -2617,6 +2735,7 @@ pp_cxx_compound_requirement (cxx_pretty_printer *pp, tree t) pp_cxx_ws_string (pp, "->"); pp->type_id (type); } + pp_cxx_semicolon (pp); } /* nested requirement: @@ -2632,74 +2751,94 @@ pp_cxx_nested_requirement (cxx_pretty_printer *pp, tree t) void pp_cxx_predicate_constraint (cxx_pretty_printer *pp, tree t) { - pp_string (pp, "predicate"); - pp_left_paren (pp); pp->expression (TREE_OPERAND (t, 0)); - pp_right_paren (pp); +} + +void +pp_cxx_check_constraint (cxx_pretty_printer *pp, tree t) +{ + tree decl = CHECK_CONSTR_CONCEPT (t); + tree tmpl = DECL_TI_TEMPLATE (decl); + tree args = CHECK_CONSTR_ARGS (t); + tree id = build_nt (TEMPLATE_ID_EXPR, tmpl, args); + + if (TREE_CODE (decl) == VAR_DECL) + pp->expression (id); + else if (TREE_CODE (decl) == FUNCTION_DECL) + { + tree call = build_vl_exp (CALL_EXPR, 2); + TREE_OPERAND (call, 0) = integer_two_node; + TREE_OPERAND (call, 1) = id; + pp->expression (call); + } + else + gcc_unreachable (); } void pp_cxx_expression_constraint (cxx_pretty_printer *pp, tree t) { - pp_string (pp, "valid_expr"); - pp_left_paren (pp); + pp_string (pp, "expression (TREE_OPERAND (t, 0)); - pp_right_paren (pp); + pp_cxx_right_paren (pp); + pp_string (pp, ">"); } void pp_cxx_type_constraint (cxx_pretty_printer *pp, tree t) { - pp_string (pp, "valid_type"); - pp_left_paren (pp); + pp_string (pp, "type_id (TREE_OPERAND (t, 0)); - pp_right_paren (pp); + pp_string (pp, ">"); } void pp_cxx_implicit_conversion_constraint (cxx_pretty_printer *pp, tree t) { - pp_string (pp, "convertible"); - pp_left_paren (pp); + pp_string (pp, "expression (ICONV_CONSTR_EXPR (t)); - pp_cxx_separate_with (pp, ','); - pp->expression (ICONV_CONSTR_TYPE (t)); - pp_right_paren (pp); + pp_cxx_right_paren (pp); + pp_cxx_ws_string (pp, "to"); + pp->type_id (ICONV_CONSTR_TYPE (t)); + pp_string (pp, ">"); } void pp_cxx_argument_deduction_constraint (cxx_pretty_printer *pp, tree t) { - pp_string (pp, "deducible"); - pp_left_paren (pp); + pp_string (pp, "expression (DEDUCT_CONSTR_EXPR (t)); - pp_cxx_separate_with (pp, ','); + pp_cxx_right_paren (pp); + pp_cxx_ws_string (pp, "as"); pp->expression (DEDUCT_CONSTR_PATTERN (t)); - pp_right_paren (pp); + pp_string (pp, ">"); } void pp_cxx_exception_constraint (cxx_pretty_printer *pp, tree t) { pp_cxx_ws_string (pp, "noexcept"); - pp_left_paren (pp); + pp_cxx_whitespace (pp); + pp_cxx_left_paren (pp); pp->expression (TREE_OPERAND (t, 0)); - pp_right_paren (pp); + pp_cxx_right_paren (pp); } void pp_cxx_parameterized_constraint (cxx_pretty_printer *pp, tree t) { pp_left_paren (pp); - pp_string (pp, "forall"); + pp_string (pp, ""); } void @@ -2730,6 +2869,10 @@ pp_cxx_constraint (cxx_pretty_printer *pp, tree t) pp_cxx_predicate_constraint (pp, t); break; + case CHECK_CONSTR: + pp_cxx_check_constraint (pp, t); + break; + case EXPR_CONSTR: pp_cxx_expression_constraint (pp, t); break; @@ -2762,6 +2905,10 @@ pp_cxx_constraint (cxx_pretty_printer *pp, tree t) pp_cxx_disjunction (pp, t); break; + case EXPR_PACK_EXPANSION: + pp->expression (TREE_OPERAND (t, 0)); + break; + default: gcc_unreachable (); } diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c index 09bb767..e5e1121 100644 --- a/gcc/cp/decl.c +++ b/gcc/cp/decl.c @@ -7921,7 +7921,7 @@ grokfndecl (tree ctype, /* Adjust the required expression into a constraint. */ if (decl_reqs) - decl_reqs = make_predicate_constraint (decl_reqs); + decl_reqs = normalize_expression (decl_reqs); tree ci = build_constraints (tmpl_reqs, decl_reqs); set_constraints (decl, ci); diff --git a/gcc/cp/error.c b/gcc/cp/error.c index d5a7d0f..69a40cc 100644 --- a/gcc/cp/error.c +++ b/gcc/cp/error.c @@ -961,7 +961,12 @@ dump_simple_decl (cxx_pretty_printer *pp, tree t, tree type, int flags) { if (VAR_P (t) && DECL_DECLARED_CONSTEXPR_P (t)) - pp_cxx_ws_string (pp, "constexpr"); + { + if (DECL_DECLARED_CONCEPT_P (t)) + pp_cxx_ws_string (pp, "concept"); + else + pp_cxx_ws_string (pp, "constexpr"); + } dump_type_prefix (pp, type, flags & ~TFF_UNQUALIFIED_NAME); pp_maybe_space (pp); } @@ -1334,16 +1339,19 @@ dump_template_decl (cxx_pretty_printer *pp, tree t, int flags) if (TEMPLATE_TYPE_PARAMETER_PACK (TREE_TYPE (t))) pp_cxx_ws_string (pp, "..."); } + + /* Only print the requirements if we're also printing + the template header. */ + if (flag_concepts) + if (tree ci = get_constraints (t)) + if (check_constraint_info (ci)) + if (tree reqs = CI_TEMPLATE_REQS (ci)) + { + pp_cxx_requires_clause (pp, reqs); + pp_cxx_whitespace (pp); + } } - if (flag_concepts) - if (tree ci = get_constraints (t)) - if (check_constraint_info (ci)) - if (tree reqs = CI_TEMPLATE_REQS (ci)) - { - pp_cxx_requires_clause (pp, reqs); - pp_cxx_whitespace (pp); - } if (DECL_CLASS_TEMPLATE_P (t)) dump_type (pp, TREE_TYPE (t), @@ -1534,7 +1542,12 @@ dump_function_decl (cxx_pretty_printer *pp, tree t, int flags) pp_cxx_ws_string (pp, "virtual"); if (constexpr_p) - pp_cxx_ws_string (pp, "constexpr"); + { + if (DECL_DECLARED_CONCEPT_P (t)) + pp_cxx_ws_string (pp, "concept"); + else + pp_cxx_ws_string (pp, "constexpr"); + } } /* Print the return type? */ @@ -2665,6 +2678,10 @@ dump_expr (cxx_pretty_printer *pp, tree t, int flags) break; case EXPR_PACK_EXPANSION: + case UNARY_LEFT_FOLD_EXPR: + case UNARY_RIGHT_FOLD_EXPR: + case BINARY_LEFT_FOLD_EXPR: + case BINARY_RIGHT_FOLD_EXPR: case TYPEID_EXPR: case MEMBER_REF: case DOTSTAR_EXPR: @@ -2737,6 +2754,7 @@ dump_expr (cxx_pretty_printer *pp, tree t, int flags) break; case PRED_CONSTR: + case CHECK_CONSTR: case EXPR_CONSTR: case TYPE_CONSTR: case ICONV_CONSTR: diff --git a/gcc/cp/logic.cc b/gcc/cp/logic.cc index c12c381..dda98df 100644 --- a/gcc/cp/logic.cc +++ b/gcc/cp/logic.cc @@ -23,6 +23,7 @@ along with GCC; see the file COPYING3. If not see #include "system.h" #include "coretypes.h" #include "tm.h" +#include "timevar.h" #include "hash-set.h" #include "machmode.h" #include "vec.h" @@ -50,19 +51,52 @@ namespace { // Helper algorithms -// Increment iter distance(first, last) times. -template - I1 next_by_distance (I1 iter, I2 first, I3 last) - { - for ( ; first != last; ++first, ++iter) - ; - return iter; - } +template +inline I +next (I iter) +{ + return ++iter; +} + +template +inline bool +any_p (I first, I last, P pred) +{ + while (first != last) + { + if (pred(*first)) + return true; + ++first; + } + return false; +} + +bool prove_implication (tree, tree); /*--------------------------------------------------------------------------- Proof state ---------------------------------------------------------------------------*/ +struct term_entry +{ + tree t; +}; + +/* Hashing function and equality for constraint entries. */ + +struct term_hasher : ggc_ptr_hash +{ + static hashval_t hash (term_entry *e) + { + return iterative_hash_template_arg (e->t, 0); + } + + static bool equal (term_entry *e1, term_entry *e2) + { + return cp_tree_equal (e1->t, e2->t); + } +}; + /* A term list is a list of atomic constraints. It is used to maintain the lists of assumptions and conclusions in a proof goal. @@ -70,109 +104,122 @@ template Each term list maintains an iterator that refers to the current term. This can be used by various tactics to support iteration and stateful manipulation of the list. */ -struct term_list : std::list +struct term_list { + typedef std::list::iterator iterator; + term_list (); - term_list (const term_list &x); - term_list& operator= (const term_list &x); + term_list (tree); - tree current_term () { return *current; } - const_tree current_term () const { return *current; } + bool includes (tree); + iterator insert (iterator, tree); + iterator push_back (tree); + iterator erase (iterator); + iterator replace (iterator, tree); + iterator replace (iterator, tree, tree); + iterator begin() { return seq.begin(); } + iterator end() { return seq.end(); } - void insert (tree t); - tree erase (); - - void start (); - void next (); - bool done() const; - - iterator current; + std::list seq; + hash_table tab; }; inline term_list::term_list () - : std::list (), current (end ()) -{ } + : seq(), tab (11) +{ +} + +/* Initialize a term list with an initial term. */ inline -term_list::term_list (const term_list &x) - : std::list (x) - , current (next_by_distance (begin (), x.begin (), x.current)) -{ } - -inline term_list& -term_list::operator= (const term_list &x) -{ - std::list::operator=(x); - current = next_by_distance (begin (), x.begin (), x.current); - return *this; -} - -/* Try saving the term T into the list of terms. If - T is already in the list of terms, then no action is - performed. Otherwise, insert T before the current - position, making this term current. - - Note that not inserting terms is an optimization - that corresponds to the structural rule of - contraction. - - NOTE: With the contraction rule, this data structure - would be more efficiently represented as an ordered set - or hash set. */ -void -term_list::insert (tree t) -{ - /* Search the current term list. If there is already - a matching term, do not add the new one. */ - for (iterator i = begin(); i != end(); ++i) - if (cp_tree_equal (*i, t)) - return; - - current = std::list::insert (current, t); -} - -/* Remove the current term from 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 -term_list::erase () -{ - tree t = *current; - current = std::list::erase (current); - return t; -} - -/* Initialize the current term to the first in the list. */ -inline void -term_list::start () +term_list::term_list (tree t) + : seq (), tab (11) { - current = begin (); + push_back (t); } -/* Advance to the next term in the list. */ -inline void -term_list::next () -{ - ++current; -} +/* Returns true if T is the in the tree. */ -/* Returns true when the current position is past the end. */ inline bool -term_list::done () const +term_list::includes (tree t) { - return current == end (); + term_entry ent = {t}; + return tab.find (&ent); } +/* Append a term to the list. */ +inline term_list::iterator +term_list::push_back (tree t) +{ + return insert (end(), t); +} + +/* Insert a new (unseen) term T into the list before the proposition + indicated by ITER. Returns the iterator to the newly inserted + element. */ + +term_list::iterator +term_list::insert (iterator iter, tree t) +{ + gcc_assert (!includes (t)); + iter = seq.insert (iter, t); + term_entry ent = {t}; + term_entry** slot = tab.find_slot (&ent, INSERT); + term_entry* ptr = ggc_alloc (); + *ptr = ent; + *slot = ptr; + return iter; +} + +/* Remove an existing term from the list. Returns an iterator referring + to the element after the removed term. This may be end(). */ + +term_list::iterator +term_list::erase (iterator iter) +{ + gcc_assert (includes (*iter)); + term_entry ent = {*iter}; + tab.remove_elt (&ent); + iter = seq.erase (iter); + return iter; +} + +/* Replace the given term with that specified. If the term has + been previously seen, do not insert the term. Returns the + first iterator past the current term. */ + +term_list::iterator +term_list::replace (iterator iter, tree t) +{ + iter = erase (iter); + if (!includes (t)) + insert (iter, t); + return iter; +} + + +/* Replace the term at the given position by the supplied T1 + followed by t2. This is used in certain logical operators to + load a list of assumptions or conclusions. */ + +term_list::iterator +term_list::replace (iterator iter, tree t1, tree t2) +{ + iter = erase (iter); + if (!includes (t1)) + insert (iter, t1); + if (!includes (t2)) + insert (iter, t2); + return iter; +} /* A goal (or subgoal) models a sequent of the form 'A |- C' where A and C are lists of assumptions and conclusions written as propositions in the constraint - language (i.e., lists of trees). -*/ + language (i.e., lists of trees). */ + struct proof_goal { term_list assumptions; @@ -182,27 +229,27 @@ struct proof_goal /* A proof state owns a list of goals and tracks the current sub-goal. The class also provides facilities for managing subgoals and constructing term lists. */ + struct proof_state : std::list { proof_state (); iterator branch (iterator i); + iterator discharge (iterator i); }; -/* 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. */ -/* Initialize the state with a single empty goal, - and set that goal as the current subgoal. */ inline proof_state::proof_state () : std::list (1) { } -/* Branch the current goal by creating a new subgoal, - returning a reference to // the new object. This does - not update the current goal. */ +/* Branch the current goal by creating a new subgoal, returning a + reference to the new object. This does not update the current goal. */ + inline proof_state::iterator proof_state::branch (iterator i) { @@ -211,278 +258,536 @@ proof_state::branch (iterator i) return insert (++i, g); } -/*--------------------------------------------------------------------------- - Logical rules ----------------------------------------------------------------------------*/ - -/*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. */ +/* Discharge the current goal, setting it equal to the + next non-satisfied goal. */ -/* The left logical rule for conjunction adds both operands - to the current set of constraints. */ -void -left_conjunction (proof_state &, goal_iterator i, tree t) +inline proof_state::iterator +proof_state::discharge (iterator i) { - gcc_assert (TREE_CODE (t) == CONJ_CONSTR); - - /* 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)); + gcc_assert (i != end()); + return erase (i); } -/* The left logical rule for disjunction creates a new goal, - adding the first operand to the original set of - constraints and the second operand to the new set - of constraints. */ -void -left_disjunction (proof_state &s, goal_iterator i, tree t) -{ - gcc_assert (TREE_CODE (t) == DISJ_CONSTR); - - /* 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)); -} +/*--------------------------------------------------------------------------- + Debugging +---------------------------------------------------------------------------*/ -/* The left logical rules for parameterized constraints - adds its operand to the current goal. The list of - parameters are effectively discarded. */ -void -left_parameterized_constraint (proof_state &, goal_iterator i, tree t) -{ - gcc_assert (TREE_CODE (t) == PARM_CONSTR); - term_list &l = i->assumptions; - l.insert (PARM_CONSTR_OPERAND (t)); -} +// void +// debug (term_list& ts) +// { +// for (term_list::iterator i = ts.begin(); i != ts.end(); ++i) +// verbatim (" # %E", *i); +// } +// +// void +// debug (proof_goal& g) +// { +// debug (g.assumptions); +// verbatim (" |-"); +// debug (g.conclusions); +// } /*--------------------------------------------------------------------------- - Decomposition + Atomicity of constraints ---------------------------------------------------------------------------*/ -/* The following algorithms decompose expressions into sets of - atomic propositions. In terms of the sequent calculus, these - functions exercise the logical rules only. - - This is equivalent, for the purpose of determining subsumption, - to rewriting a constraint in disjunctive normal form. It also - allows the resulting assumptions to be used as declarations - for the purpose of separate checking. */ +/* Returns true if T is not an atomic constraint. */ -/* Apply the left logical rules to the proof state. */ -void -decompose_left_term (proof_state &s, goal_iterator i) +bool +non_atomic_constraint_p (tree t) { - term_list &l = i->assumptions; - tree t = l.current_term (); switch (TREE_CODE (t)) { + case PRED_CONSTR: + case EXPR_CONSTR: + case TYPE_CONSTR: + case ICONV_CONSTR: + case DEDUCT_CONSTR: + case EXCEPT_CONSTR: + return false; + case CHECK_CONSTR: + case PARM_CONSTR: case CONJ_CONSTR: - left_conjunction (s, i, l.erase ()); - break; case DISJ_CONSTR: - left_disjunction (s, i, l.erase ()); - break; - case PARM_CONSTR: - left_parameterized_constraint (s, i, l.erase ()); - break; - default: - l.next (); - break; - } -} - -/* Apply the left logical rules of the sequent calculus - until the current goal is fully decomposed into atomic - constraints. */ -void -decompose_left_goal (proof_state &s, goal_iterator i) -{ - term_list& l = i->assumptions; - l.start (); - while (!l.done ()) - decompose_left_term (s, i); -} - -/* Apply the left logical rules of the sequent calculus - until the antecedents are fully decomposed into atomic - constraints. */ -void -decompose_left (proof_state& s) -{ - goal_iterator iter = s.begin (); - goal_iterator end = s.end (); - for ( ; iter != end; ++iter) - decompose_left_goal (s, iter); -} - -/* Returns a vector of terms from the term list L. */ -tree -extract_terms (term_list& l) -{ - tree result = make_tree_vec (l.size()); - 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; -} - -/* Extract the assumptions from the proof state S - as a vector of vectors of atomic constraints. */ -inline tree -extract_assumptions (proof_state& s) -{ - 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 required expression T into a constraint set: a - vector of vectors containing only atomic propositions. If T is - invalid, return an error. */ -tree -decompose_assumptions (tree t) -{ - if (!t || t == error_mark_node) - return t; - - /* Create a proof state, and insert T as the sole assumption. */ - proof_state s; - 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); -} - - -/*--------------------------------------------------------------------------- - Subsumption Rules ----------------------------------------------------------------------------*/ - -namespace { - -bool subsumes_constraint (tree, tree); -bool subsumes_conjunction (tree, tree); -bool subsumes_disjunction (tree, tree); -bool subsumes_parameterized_constraint (tree, tree); -bool subsumes_atomic_constraint (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. - - NOTE: There will be specialized matching rules to accommodate - type equivalence, conversion, inheritance, etc. But this is not - in the current concepts draft. */ -inline bool -match_terms (tree a, tree c) -{ - return cp_tree_equal (a, c); -} - -/* Returns true if the list of assumptions AS subsumes the atomic - proposition C. This is the case when we can find a proposition - in AS that entails the conclusion C. */ -bool -subsumes_atomic_constraint (tree as, tree c) -{ - for (int i = 0; i < TREE_VEC_LENGTH (as); ++i) - if (match_terms (TREE_VEC_ELT (as, i), c)) return true; - return false; + default: + gcc_unreachable (); + } } -/* Returns true when both operands of C are subsumed by the - assumptions AS. */ -inline bool -subsumes_conjunction (tree as, tree c) +/* Returns true if any constraints in T are not atomic. */ + +bool +any_non_atomic_constraints_p (term_list& t) { - tree l = TREE_OPERAND (c, 0); - tree r = TREE_OPERAND (c, 1); - return subsumes_constraint (as, l) && subsumes_constraint (as, r); + return any_p (t.begin(), t.end(), non_atomic_constraint_p); } -/* Returns true when either operand of C is subsumed by the - assumptions AS. */ -inline bool -subsumes_disjunction (tree as, tree c) +/*--------------------------------------------------------------------------- + Proof validations +---------------------------------------------------------------------------*/ + +enum proof_result { - tree l = TREE_OPERAND (c, 0); - tree r = TREE_OPERAND (c, 1); - return subsumes_constraint (as, l) || subsumes_constraint (as, r); + invalid, + valid, + undecided +}; + +proof_result check_term (term_list&, tree); + + +proof_result +analyze_atom (term_list& ts, tree t) +{ + /* FIXME: Hook into special cases, if any. */ + /* + term_list::iterator iter = ts.begin(); + term_list::iterator end = ts.end(); + while (iter != end) + { + ++iter; + } + */ + + if (non_atomic_constraint_p (t)) + return undecided; + if (any_non_atomic_constraints_p (ts)) + return undecided; + return invalid; } -/* Returns true when the operand of C is subsumed by the - assumptions in AS. The parameters are not considered in - the subsumption rules. */ -bool -subsumes_parameterized_constraint (tree as, tree c) +/* Search for a pack expansion in the list of assumptions that would + make this expansion valid. */ + +proof_result +analyze_pack (term_list& ts, tree t) { - tree t = PARM_CONSTR_OPERAND (c); - return subsumes_constraint (as, t); + tree c1 = normalize_expression (PACK_EXPANSION_PATTERN (t)); + term_list::iterator iter = ts.begin(); + term_list::iterator end = ts.end(); + while (iter != end) + { + if (TREE_CODE (*iter) == TREE_CODE (t)) + { + tree c2 = normalize_expression (PACK_EXPANSION_PATTERN (*iter)); + if (prove_implication (c2, c1)) + return valid; + else + return invalid; + } + ++iter; + } + return invalid; } +/* Search for concept checks in TS that we know subsume T. */ -/* Returns true when the list of assumptions AS subsumes the - concluded proposition C. This is a simple recursive descent - on C, matching against propositions in the assumption list AS. */ -bool -subsumes_constraint (tree as, tree c) +proof_result +search_known_subsumptions (term_list& ts, tree t) +{ + for (term_list::iterator i = ts.begin(); i != ts.end(); ++i) + if (TREE_CODE (*i) == CHECK_CONSTR) + { + if (bool* b = lookup_subsumption_result (*i, t)) + return *b ? valid : invalid; + } + return undecided; +} + +/* Determine if the terms in TS provide sufficient support for proving + the proposition T. If any term in TS is a concept check that is known + to subsume T, then the proof is valid. Otherwise, we have to expand T + and continue searching for support. */ + +proof_result +analyze_check (term_list& ts, tree t) { - switch (TREE_CODE (c)) + proof_result r = search_known_subsumptions (ts, t); + if (r != undecided) + return r; + + tree tmpl = CHECK_CONSTR_CONCEPT (t); + tree args = CHECK_CONSTR_ARGS (t); + tree c = expand_concept (tmpl, args); + return check_term (ts, c); +} + +/* Recursively check constraints of the parameterized constraint. */ + +proof_result +analyze_parameterized (term_list& ts, tree t) +{ + return check_term (ts, PARM_CONSTR_OPERAND (t)); +} + +proof_result +analyze_conjunction (term_list& ts, tree t) +{ + proof_result r = check_term (ts, TREE_OPERAND (t, 0)); + if (r == invalid || r == undecided) + return r; + return check_term (ts, TREE_OPERAND (t, 1)); +} + +proof_result +analyze_disjunction (term_list& ts, tree t) +{ + proof_result r = check_term (ts, TREE_OPERAND (t, 0)); + if (r == valid) + return r; + return check_term (ts, TREE_OPERAND (t, 1)); +} + +proof_result +analyze_term (term_list& ts, tree t) +{ + switch (TREE_CODE (t)) { + case CHECK_CONSTR: + return analyze_check (ts, t); + + case PARM_CONSTR: + return analyze_parameterized (ts, t); + case CONJ_CONSTR: - return subsumes_conjunction (as, c); + return analyze_conjunction (ts, t); case DISJ_CONSTR: - return subsumes_disjunction (as, c); - case PARM_CONSTR: - return subsumes_parameterized_constraint (as, c); + return analyze_disjunction (ts, t); + + case PRED_CONSTR: + case EXPR_CONSTR: + case TYPE_CONSTR: + case ICONV_CONSTR: + case DEDUCT_CONSTR: + case EXCEPT_CONSTR: + return analyze_atom (ts, t); + + case EXPR_PACK_EXPANSION: + return analyze_pack (ts, t); + + case ERROR_MARK: + /* Encountering an error anywhere in a constraint invalidates + the proof, since the constraint is ill-formed. */ + return invalid; default: - return subsumes_atomic_constraint (as, c); + gcc_unreachable (); } } -/* Returns true if the LEFT constraints subsume the RIGHT constraints. - This is done by checking that the RIGHT requirements follow from - each of the LEFT subgoals. */ +/* Check if a single term can be proven from a set of assumptions. + If the proof is not valid, then it is incomplete when either + the given term is non-atomic or any term in the list of assumptions + is not-atomic. */ + +proof_result +check_term (term_list& ts, tree t) +{ + /* Try the easy way; search for an equivalent term. */ + if (ts.includes (t)) + return valid; + + /* The hard way; actually consider what the term means. */ + return analyze_term (ts, t); +} + +/* Check to see if any term is proven by the assumptions in the + proof goal. The proof is valid if the proof of any term is valid. + If validity cannot be determined, but any particular + check was undecided, then this goal is undecided. */ + +proof_result +check_goal (proof_goal& g) +{ + term_list::iterator iter = g.conclusions.begin (); + term_list::iterator end = g.conclusions.end (); + bool incomplete = false; + while (iter != end) + { + proof_result r = check_term (g.assumptions, *iter); + if (r == valid) + return r; + if (r == undecided) + incomplete = true; + ++iter; + } + + /* Was the proof complete? */ + if (incomplete) + return undecided; + else + return invalid; +} + +/* Check if the the proof is valid. This is the case when all + goals can be discharged. If any goal is invalid, then the + entire proof is invalid. Otherwise, the proof is undecided. */ + +proof_result +check_proof (proof_state& p) +{ + proof_state::iterator iter = p.begin(); + proof_state::iterator end = p.end(); + while (iter != end) + { + proof_result r = check_goal (*iter); + if (r == invalid) + return r; + if (r == valid) + iter = p.discharge (iter); + else + ++iter; + } + + /* If all goals are discharged, then the proof is valid. */ + if (p.empty()) + return valid; + else + return undecided; +} + +/*--------------------------------------------------------------------------- + Left logical rules +---------------------------------------------------------------------------*/ + +term_list::iterator +load_check_assumption (term_list& ts, term_list::iterator i) +{ + tree decl = CHECK_CONSTR_CONCEPT (*i); + tree tmpl = DECL_TI_TEMPLATE (decl); + tree args = CHECK_CONSTR_ARGS (*i); + return ts.replace(i, expand_concept (tmpl, args)); +} + +term_list::iterator +load_parameterized_assumption (term_list& ts, term_list::iterator i) +{ + return ts.replace(i, PARM_CONSTR_OPERAND(*i)); +} + +term_list::iterator +load_conjunction_assumption (term_list& ts, term_list::iterator i) +{ + tree t1 = TREE_OPERAND (*i, 0); + tree t2 = TREE_OPERAND (*i, 1); + return ts.replace(i, t1, t2); +} + +/* Examine the terms in the list, and apply left-logical rules to move + terms into the set of assumptions. */ + +void +load_assumptions (proof_goal& g) +{ + term_list::iterator iter = g.assumptions.begin(); + term_list::iterator end = g.assumptions.end(); + while (iter != end) + { + switch (TREE_CODE (*iter)) + { + case CHECK_CONSTR: + iter = load_check_assumption (g.assumptions, iter); + break; + case PARM_CONSTR: + iter = load_parameterized_assumption (g.assumptions, iter); + break; + case CONJ_CONSTR: + iter = load_conjunction_assumption (g.assumptions, iter); + break; + default: + ++iter; + break; + } + } +} + +/* In each subgoal, load constraints into the assumption set. */ + +void +load_assumptions(proof_state& p) +{ + proof_state::iterator iter = p.begin(); + while (iter != p.end()) + { + load_assumptions (*iter); + ++iter; + } +} + +void +explode_disjunction (proof_state& p, proof_state::iterator gi, term_list::iterator ti1) +{ + tree t1 = TREE_OPERAND (*ti1, 0); + tree t2 = TREE_OPERAND (*ti1, 1); + + /* Erase the current term from the goal. */ + proof_goal& g1 = *gi; + proof_goal& g2 = *p.branch (gi); + + /* Get an iterator to the equivalent position in th enew goal. */ + int n = std::distance (g1.assumptions.begin (), ti1); + term_list::iterator ti2 = g2.assumptions.begin (); + std::advance (ti2, n); + + /* Replace the disjunction in both branches. */ + g1.assumptions.replace (ti1, t1); + g2.assumptions.replace (ti2, t2); +} + + +/* Search the assumptions of the goal for the first disjunction. */ + +bool +explode_goal (proof_state& p, proof_state::iterator gi) +{ + term_list& ts = gi->assumptions; + term_list::iterator ti = ts.begin(); + term_list::iterator end = ts.end(); + while (ti != end) + { + if (TREE_CODE (*ti) == DISJ_CONSTR) + { + explode_disjunction (p, gi, ti); + return true; + } + else ++ti; + } + return false; +} + +/* Search for the first goal with a disjunction, and then branch + creating a clone of that subgoal. */ + +void +explode_assumptions (proof_state& p) +{ + proof_state::iterator iter = p.begin(); + proof_state::iterator end = p.end(); + while (iter != end) + { + if (explode_goal (p, iter)) + return; + ++iter; + } +} + + +/*--------------------------------------------------------------------------- + Right logical rules +---------------------------------------------------------------------------*/ + +term_list::iterator +load_disjunction_conclusion (term_list& g, term_list::iterator i) +{ + tree t1 = TREE_OPERAND (*i, 0); + tree t2 = TREE_OPERAND (*i, 1); + return g.replace(i, t1, t2); +} + +/* Apply logical rules to the right hand side. This will load the + conclusion set with all tpp-level disjunctions. */ + +void +load_conclusions (proof_goal& g) +{ + term_list::iterator iter = g.conclusions.begin(); + term_list::iterator end = g.conclusions.end(); + while (iter != end) + { + if (TREE_CODE (*iter) == DISJ_CONSTR) + iter = load_disjunction_conclusion (g.conclusions, iter); + else + ++iter; + } +} + +void +load_conclusions (proof_state& p) +{ + proof_state::iterator iter = p.begin(); + while (iter != p.end()) + { + load_conclusions (*iter); + ++iter; + } +} + + +/*--------------------------------------------------------------------------- + High-level proof tactics +---------------------------------------------------------------------------*/ + +/* Given two constraints A and C, try to derive a proof that + A implies C. */ + +bool +prove_implication (tree a, tree c) +{ + /* Quick accept. */ + if (cp_tree_equal (a, c)) + return true; + + /* Build the initial proof state. */ + proof_state proof; + proof_goal& goal = proof.front(); + goal.assumptions.push_back(a); + goal.conclusions.push_back(c); + + /* Perform an initial right-expansion in the off-chance that the right + hand side contains disjunctions. */ + load_conclusions (proof); + + int step_max = 1 << 10; + int step_count = 0; /* FIXME: We shouldn't have this. */ + std::size_t branch_limit = 1024; /* FIXME: This needs to be configurable. */ + while (step_count < step_max && proof.size() < branch_limit) + { + /* Determine if we can prove that the assumptions entail the + conclusions. If so, we're done. */ + load_assumptions (proof); + + /* Can we solve the proof based on this? */ + proof_result r = check_proof (proof); + if (r != undecided) + return r == valid; + + /* If not, then we need to dig into disjunctions. */ + explode_assumptions (proof); + + ++step_count; + } + + if (step_count == step_max) + error ("subsumption failed to resolve"); + + if (proof.size() == branch_limit) + error ("exceeded maximum number of branches"); + + return false; +} + +/* Returns true if the LEFT constraint subsume the RIGHT constraints. + This is done by deriving a proof of the conclusions on the RIGHT + from the assumptions on the LEFT assumptions. */ + bool subsumes_constraints_nonnull (tree left, tree right) { gcc_assert (check_constraint_info (left)); gcc_assert (check_constraint_info (right)); - /* Check that the required expression in RIGHT is subsumed by each - subgoal in the assumptions of LEFT. */ - tree as = CI_ASSUMPTIONS (left); - tree c = CI_NORMALIZED_CONSTRAINTS (right); - for (int i = 0; i < TREE_VEC_LENGTH (as); ++i) - if (!subsumes_constraint (TREE_VEC_ELT (as, i), c)) - return false; - return true; + auto_timevar time (TV_CONSTRAINT_SUB); + tree a = CI_ASSOCIATED_CONSTRAINTS (left); + tree c = CI_ASSOCIATED_CONSTRAINTS (right); + return prove_implication (a, c); } } /* namespace */ /* Returns true if the LEFT constraints subsume the RIGHT - constraints. */ + constraints. */ + bool subsumes (tree left, tree right) { diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c index 8fceaed..9bdb108 100644 --- a/gcc/cp/parser.c +++ b/gcc/cp/parser.c @@ -14728,10 +14728,13 @@ cp_parser_type_parameter (cp_parser* parser, bool *is_parameter_pack) cp_parser_require (parser, CPP_GREATER, RT_GREATER); // If template requirements are present, parse them. - tree reqs = get_shorthand_constraints (current_template_parms); - if (tree r = cp_parser_requires_clause_opt (parser)) - reqs = conjoin_constraints (reqs, make_predicate_constraint (r)); - TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = reqs; + if (flag_concepts) + { + tree reqs = get_shorthand_constraints (current_template_parms); + if (tree r = cp_parser_requires_clause_opt (parser)) + reqs = conjoin_constraints (reqs, normalize_expression (r)); + TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = reqs; + } /* Look for the `class' or 'typename' keywords. */ cp_parser_type_parameter_key (parser); @@ -25754,10 +25757,13 @@ cp_parser_explicit_template_declaration (cp_parser* parser, bool member_p) cp_parser_skip_to_end_of_template_parameter_list (parser); /* Manage template requirements */ - tree reqs = get_shorthand_constraints (current_template_parms); - if (tree r = cp_parser_requires_clause_opt (parser)) - reqs = conjoin_constraints (reqs, make_predicate_constraint (r)); - TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = reqs; + if (flag_concepts) + { + tree reqs = get_shorthand_constraints (current_template_parms); + if (tree r = cp_parser_requires_clause_opt (parser)) + reqs = conjoin_constraints (reqs, normalize_expression (r)); + TEMPLATE_PARMS_CONSTRAINTS (current_template_parms) = reqs; + } cp_parser_template_declaration_after_parameters (parser, parameter_list, member_p); @@ -37916,7 +37922,13 @@ synthesize_implicit_template_parm (cp_parser *parser, tree constr) implicit template scope, and we're trying to synthesize a constrained parameter, try to find a previous parameter with the same name. This is the same-type rule for abbreviated - function templates. */ + function templates. + + NOTE: We can generate implicit parameters when tentatively + parsing a nested name specifier, only to reject that parse + later. However, matching the same template-id as part of a + direct-declarator should generate an identical template + parameter, so this rule will merge them. */ if (parser->implicit_template_scope && constr) { tree t = parser->implicit_template_parms; diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c index 7c7024c..d7f3808 100644 --- a/gcc/cp/pt.c +++ b/gcc/cp/pt.c @@ -195,7 +195,6 @@ static tree try_class_unification (tree, tree, tree, tree, bool); static int coerce_template_template_parms (tree, tree, tsubst_flags_t, tree, tree); static bool template_template_parm_bindings_ok_p (tree, tree); -static int template_args_equal (tree, tree); static void tsubst_default_arguments (tree, tsubst_flags_t); static tree for_each_template_parm_r (tree *, int *, void *); static tree copy_default_args_to_explicit_spec_1 (tree, tree); @@ -7855,7 +7854,7 @@ coerce_innermost_template_parms (tree parms, /* Returns 1 if template args OT and NT are equivalent. */ -static int +int template_args_equal (tree ot, tree nt) { if (nt == ot) @@ -8702,7 +8701,7 @@ finish_template_variable (tree var, tsubst_flags_t complain) { if (complain & tf_error) { - error ("constraints for %qD not satisfied", templ); + error ("use of invalid variable template %qE", var); diagnose_constraints (location_of (var), templ, arglist); } return error_mark_node; @@ -9058,7 +9057,7 @@ uses_outer_template_parms (tree decl) return true; tree ci = get_constraints (decl); if (ci) - ci = CI_NORMALIZED_CONSTRAINTS (ci); + ci = CI_ASSOCIATED_CONSTRAINTS (ci); if (ci && for_each_template_parm (ci, template_parm_outer_level, &depth, NULL, /*nondeduced*/true)) return true; @@ -23764,7 +23763,10 @@ build_non_dependent_expr (tree expr) && cxx_dialect >= cxx11 /* Don't do this during nsdmi parsing as it can lead to unexpected recursive instantiations. */ - && !parsing_nsdmi ()) + && !parsing_nsdmi () + /* Don't do this during concept expansion either and for + the same reason. */ + && !expanding_concept ()) fold_non_dependent_expr (expr); /* Preserve OVERLOADs; the functions must be available to resolve @@ -23902,7 +23904,7 @@ make_constrained_auto (tree con, tree args) else expr = build_concept_check (build_overload (tmpl, NULL_TREE), type, args); - tree constr = make_predicate_constraint (expr); + tree constr = normalize_expression (expr); PLACEHOLDER_TYPE_CONSTRAINTS (type) = constr; /* Our canonical type depends on the constraint. */ @@ -24054,7 +24056,10 @@ do_auto_deduction (tree type, tree init, tree auto_node) /* Replace occurrences of 'auto' in TYPE with the appropriate type deduced from INIT. AUTO_NODE is the TEMPLATE_TYPE_PARM used for 'auto' in TYPE. The CONTEXT determines the context in which auto deduction is performed - and is used to control error diagnostics. */ + and is used to control error diagnostics. + + For partial-concept-ids, extra args may be appended to the list of deduced + template arguments prior to determining constraint satisfaction. */ tree do_auto_deduction (tree type, tree init, tree auto_node, @@ -24161,8 +24166,19 @@ do_auto_deduction (tree type, tree init, tree auto_node, if (flag_concepts && !processing_template_decl) if (tree constr = PLACEHOLDER_TYPE_CONSTRAINTS (auto_node)) { - /* Use the deduced type to check the associated constraints. */ - if (!constraints_satisfied_p (constr, targs)) + /* Use the deduced type to check the associated constraints. If we + have a partial-concept-id, rebuild the argument list so that + we check using the extra arguments. */ + gcc_assert (TREE_CODE (constr) == CHECK_CONSTR); + tree cargs = CHECK_CONSTR_ARGS (constr); + if (TREE_VEC_LENGTH (cargs) > 1) + { + cargs = copy_node (cargs); + TREE_VEC_ELT (cargs, 0) = TREE_VEC_ELT (targs, 0); + } + else + cargs = targs; + if (!constraints_satisfied_p (constr, cargs)) { if (complain & tf_warning_or_error) { @@ -24482,24 +24498,15 @@ struct constr_hasher : ggc_ptr_hash static GTY (()) hash_table *decl_constraints; -/* Returns true iff cinfo contains a valid set of constraints. - This is the case when the associated requirements have been - successfully decomposed into lists of atomic constraints. - That is, when the saved assumptions are not error_mark_node. */ - -bool -valid_constraints_p (tree cinfo) -{ - gcc_assert (cinfo); - return CI_ASSUMPTIONS (cinfo) != error_mark_node; -} - /* Returns the template constraints of declaration T. If T is not constrained, return NULL_TREE. Note that T must be non-null. */ tree get_constraints (tree t) { + if (!flag_concepts) + return NULL_TREE; + gcc_assert (DECL_P (t)); if (TREE_CODE (t) == TEMPLATE_DECL) t = DECL_TEMPLATE_RESULT (t); @@ -24521,7 +24528,7 @@ set_constraints (tree t, tree ci) { if (!ci) return; - gcc_assert (t); + gcc_assert (t && flag_concepts); if (TREE_CODE (t) == TEMPLATE_DECL) t = DECL_TEMPLATE_RESULT (t); gcc_assert (!get_constraints (t)); @@ -24547,12 +24554,244 @@ remove_constraints (tree t) decl_constraints->clear_slot (slot); } +/* Memoized satisfaction results for declarations. This + maps the pair (constraint_info, arguments) to the result computed + by constraints_satisfied_p. */ + +struct GTY((for_user)) constraint_sat_entry +{ + tree ci; + tree args; + tree result; +}; + +/* Hashing function and equality for constraint entries. */ + +struct constraint_sat_hasher : ggc_ptr_hash +{ + static hashval_t hash (constraint_sat_entry *e) + { + hashval_t val = iterative_hash_object(e->ci, 0); + return iterative_hash_template_arg (e->args, val); + } + + static bool equal (constraint_sat_entry *e1, constraint_sat_entry *e2) + { + return e1->ci == e2->ci && comp_template_args (e1->args, e2->args); + } +}; + +/* Memoized satisfaction results for concept checks. */ + +struct GTY((for_user)) concept_spec_entry +{ + tree tmpl; + tree args; + tree result; +}; + +/* Hashing function and equality for constraint entries. */ + +struct concept_spec_hasher : ggc_ptr_hash +{ + static hashval_t hash (concept_spec_entry *e) + { + return hash_tmpl_and_args (e->tmpl, e->args); + } + + static bool equal (concept_spec_entry *e1, concept_spec_entry *e2) + { + ++comparing_specializations; + bool eq = e1->tmpl == e2->tmpl && comp_template_args (e1->args, e2->args); + --comparing_specializations; + return eq; + } +}; + +static GTY (()) hash_table *constraint_memos; +static GTY (()) hash_table *concept_memos; + +/* Search for a memoized satisfaction result. Returns one of the + truth value nodes if previously memoized, or NULL_TREE otherwise. */ + +tree +lookup_constraint_satisfaction (tree ci, tree args) +{ + constraint_sat_entry elt = { ci, args, NULL_TREE }; + constraint_sat_entry* found = constraint_memos->find (&elt); + if (found) + return found->result; + else + return NULL_TREE; +} + +/* Memoize the result of a satisfication test. Returns the saved result. */ + +tree +memoize_constraint_satisfaction (tree ci, tree args, tree result) +{ + constraint_sat_entry elt = {ci, args, result}; + constraint_sat_entry** slot = constraint_memos->find_slot (&elt, INSERT); + constraint_sat_entry* entry = ggc_alloc (); + *entry = elt; + *slot = entry; + return result; +} + +/* Search for a memoized satisfaction result for a concept. */ + +tree +lookup_concept_satisfaction (tree tmpl, tree args) +{ + concept_spec_entry elt = { tmpl, args, NULL_TREE }; + concept_spec_entry* found = concept_memos->find (&elt); + if (found) + return found->result; + else + return NULL_TREE; +} + +/* Memoize the result of a concept check. Returns the saved result. */ + +tree +memoize_concept_satisfaction (tree tmpl, tree args, tree result) +{ + concept_spec_entry elt = {tmpl, args, result}; + concept_spec_entry** slot = concept_memos->find_slot (&elt, INSERT); + concept_spec_entry* entry = ggc_alloc (); + *entry = elt; + *slot = entry; + return result; +} + +static GTY (()) hash_table *concept_expansions; + +/* Returns a prior concept specialization. This returns the substituted + and normalized constraints defined by the concept. */ + +tree +get_concept_expansion (tree tmpl, tree args) +{ + concept_spec_entry elt = { tmpl, args, NULL_TREE }; + concept_spec_entry* found = concept_expansions->find (&elt); + if (found) + return found->result; + else + return NULL_TREE; +} + +/* Save a concept expansion for later. */ + +tree +save_concept_expansion (tree tmpl, tree args, tree def) +{ + concept_spec_entry elt = {tmpl, args, def}; + concept_spec_entry** slot = concept_expansions->find_slot (&elt, INSERT); + concept_spec_entry* entry = ggc_alloc (); + *entry = elt; + *slot = entry; + return def; +} + +static hashval_t +hash_subsumption_args (tree t1, tree t2) +{ + gcc_assert (TREE_CODE (t1) == CHECK_CONSTR); + gcc_assert (TREE_CODE (t2) == CHECK_CONSTR); + int val = 0; + val = iterative_hash_object (CHECK_CONSTR_CONCEPT (t1), val); + val = iterative_hash_template_arg (CHECK_CONSTR_ARGS (t1), val); + val = iterative_hash_object (CHECK_CONSTR_CONCEPT (t2), val); + val = iterative_hash_template_arg (CHECK_CONSTR_ARGS (t2), val); + return val; +} + +/* Compare the constraints of two subsumption entries. The LEFT1 and + LEFT2 arguments comprise the first subsumption pair and the RIGHT1 + and RIGHT2 arguments comprise the second. These are all CHECK_CONSTRs. */ + +static bool +comp_subsumption_args (tree left1, tree left2, tree right1, tree right2) +{ + if (CHECK_CONSTR_CONCEPT (left1) == CHECK_CONSTR_CONCEPT (right1)) + if (CHECK_CONSTR_CONCEPT (left2) == CHECK_CONSTR_CONCEPT (right2)) + if (comp_template_args (CHECK_CONSTR_ARGS (left1), + CHECK_CONSTR_ARGS (right1))) + return comp_template_args (CHECK_CONSTR_ARGS (left2), + CHECK_CONSTR_ARGS (right2)); + return false; +} + +/* Key/value pair for learning and memoizing subsumption results. This + associates a pair of check constraints (including arguments) with + a boolean value indicating the result. */ + +struct GTY((for_user)) subsumption_entry +{ + tree t1; + tree t2; + bool result; +}; + +/* Hashing function and equality for constraint entries. */ + +struct subsumption_hasher : ggc_ptr_hash +{ + static hashval_t hash (subsumption_entry *e) + { + return hash_subsumption_args (e->t1, e->t2); + } + + static bool equal (subsumption_entry *e1, subsumption_entry *e2) + { + ++comparing_specializations; + bool eq = comp_subsumption_args(e1->t1, e1->t2, e2->t1, e2->t2); + --comparing_specializations; + return eq; + } +}; + +static GTY (()) hash_table *subsumption_table; + +/* Search for a previously cached subsumption result. */ + +bool* +lookup_subsumption_result (tree t1, tree t2) +{ + subsumption_entry elt = { t1, t2, false }; + subsumption_entry* found = subsumption_table->find (&elt); + if (found) + return &found->result; + else + return 0; +} + +/* Save a subsumption result. */ + +bool +save_subsumption_result (tree t1, tree t2, bool result) +{ + subsumption_entry elt = {t1, t2, result}; + subsumption_entry** slot = subsumption_table->find_slot (&elt, INSERT); + subsumption_entry* entry = ggc_alloc (); + *entry = elt; + *slot = entry; + return result; +} + /* Set up the hash table for constraint association. */ void init_constraint_processing (void) { + if (!flag_concepts) + return; + decl_constraints = hash_table::create_ggc(37); + constraint_memos = hash_table::create_ggc(37); + concept_memos = hash_table::create_ggc(37); + concept_expansions = hash_table::create_ggc(37); + subsumption_table = hash_table::create_ggc(37); } /* Set up the hash tables for template instantiations. */ diff --git a/gcc/cp/ptree.c b/gcc/cp/ptree.c index 8266e83..5726f96 100644 --- a/gcc/cp/ptree.c +++ b/gcc/cp/ptree.c @@ -260,7 +260,6 @@ cxx_print_xnode (FILE *file, tree node, int indent) indent+4); print_node (file, "associated_constr", cinfo->associated_constr, indent+4); - print_node_brief (file, "assumptions", cinfo->assumptions, indent+4); break; } case ARGUMENT_PACK_SELECT: diff --git a/gcc/cp/search.c b/gcc/cp/search.c index 8b5f329..325ef98 100644 --- a/gcc/cp/search.c +++ b/gcc/cp/search.c @@ -947,6 +947,7 @@ accessible_p (tree type, tree decl, bool consider_local_p) in default arguments for template parameters), and access checking should be performed in the outermost parameter list. */ if (processing_template_decl + && !expanding_concept () && (!processing_template_parmlist || processing_template_decl > 1)) return 1; diff --git a/gcc/cp/tree.c b/gcc/cp/tree.c index faf096c..6adeb63 100644 --- a/gcc/cp/tree.c +++ b/gcc/cp/tree.c @@ -3182,6 +3182,11 @@ cp_tree_equal (tree t1, tree t2) return cp_tree_equal (CI_ASSOCIATED_CONSTRAINTS (t1), CI_ASSOCIATED_CONSTRAINTS (t2)); + case CHECK_CONSTR: + return (CHECK_CONSTR_CONCEPT (t1) == CHECK_CONSTR_CONCEPT (t2) + && comp_template_args (CHECK_CONSTR_ARGS (t1), + CHECK_CONSTR_ARGS (t2))); + case TREE_VEC: { unsigned ix; diff --git a/gcc/testsuite/g++.dg/concepts/diagnostic1.C b/gcc/testsuite/g++.dg/concepts/diagnostic1.C index aa98ffa..0552c4b 100644 --- a/gcc/testsuite/g++.dg/concepts/diagnostic1.C +++ b/gcc/testsuite/g++.dg/concepts/diagnostic1.C @@ -1,16 +1,30 @@ // PR c++/67159 // { dg-options "-std=c++1z -fconcepts" } +template +concept bool SameAs = __is_same_as(T, U); + template -concept bool R = requires (T& t) { +concept bool R1 = requires (T& t) { { t.begin() } -> T + { t.end() } -> SameAs; +}; + +template +concept bool R2 = requires (T& t) { + { t.end() } -> SameAs; }; struct foo { int* begin(); + int* end(); }; -R{T} +R1{T} constexpr bool f() { return true; } +R2{T} +constexpr bool g() { return true; } + static_assert(f()); // { dg-error "" } +static_assert(g()); // { dg-error "" } diff --git a/gcc/testsuite/g++.dg/concepts/dr1430.C b/gcc/testsuite/g++.dg/concepts/dr1430.C index 3a7ba03..178467a 100644 --- a/gcc/testsuite/g++.dg/concepts/dr1430.C +++ b/gcc/testsuite/g++.dg/concepts/dr1430.C @@ -24,11 +24,19 @@ template return decltype(check())::value; } +template + concept bool Similar = true; + template -requires Same() // { dg-error "concept" } +requires Same() // { dg-error "invalid reference" } void foo( Args... args ) {} +template +requires Similar // { dg-error "invalid reference" } + void bar( Args... args ) {} + int main() { - foo(1, 2, 3); // { dg-error "" } + foo(1, 2, 3); // { dg-error "cannot call" } + bar(1, 2, 3); // { dg-error "cannot call" } } diff --git a/gcc/testsuite/g++.dg/concepts/expression2.C b/gcc/testsuite/g++.dg/concepts/expression2.C index ebdadc2..32b79c8 100644 --- a/gcc/testsuite/g++.dg/concepts/expression2.C +++ b/gcc/testsuite/g++.dg/concepts/expression2.C @@ -31,12 +31,12 @@ class S int main() { f1(s); // { dg-error "cannot call" } - f2(s); // { dg-error "cannot call" } + f2(s); // { dg-error "" } // When used in non-SFINAE contexts, make sure that we fail // the constraint check before emitting the access check // failures. The context is being presented constistently // in both cases. static_assert(C1(), ""); // { dg-error "failed" } - static_assert(C2(), ""); // { dg-error "failed" } + static_assert(C2(), ""); // { dg-error "" } } diff --git a/gcc/testsuite/g++.dg/concepts/req19.C b/gcc/testsuite/g++.dg/concepts/req19.C new file mode 100644 index 0000000..0564b0c --- /dev/null +++ b/gcc/testsuite/g++.dg/concepts/req19.C @@ -0,0 +1,13 @@ +// { dg-options "-std=c++1z -fconcepts" } + +struct B +{ + template void f(T t) + requires requires (T tt) { tt; } + { } +}; + +int main() +{ + B().f(42); +} diff --git a/gcc/testsuite/g++.dg/concepts/req20.C b/gcc/testsuite/g++.dg/concepts/req20.C new file mode 100644 index 0000000..e89e905 --- /dev/null +++ b/gcc/testsuite/g++.dg/concepts/req20.C @@ -0,0 +1,20 @@ +// { dg-options "-std=c++1z -fconcepts" } + +template concept bool C = true; + +template +requires C +void f(T t) { } + +void f(...); + +template +requires C +void g(T t) { } + +int main() +{ + f(42); + g(42); +} + diff --git a/gcc/testsuite/g++.dg/concepts/req4.C b/gcc/testsuite/g++.dg/concepts/req4.C index e7e71a4..2bd5f15 100644 --- a/gcc/testsuite/g++.dg/concepts/req4.C +++ b/gcc/testsuite/g++.dg/concepts/req4.C @@ -9,10 +9,10 @@ template constexpr fool p1() { return {}; } template constexpr fool p2() { return {}; } template - concept bool C() { return p1() && p2(); } // { dg-error "does not have type" } + concept bool C() { return p1() && p2(); } template void f(T x) { } int main() { - f(0); // { dg-error "cannot call" } + f(0); // { dg-error "cannot call|uses overloaded operator" } } diff --git a/gcc/testsuite/g++.dg/concepts/req5.C b/gcc/testsuite/g++.dg/concepts/req5.C index 17db0dd..7953869 100644 --- a/gcc/testsuite/g++.dg/concepts/req5.C +++ b/gcc/testsuite/g++.dg/concepts/req5.C @@ -9,10 +9,10 @@ template constexpr fool p1() { return {}; } template constexpr fool p2() { return {}; } template - concept bool C() { return p1() && p2(); } // { dg-error "does not have type" } + concept bool C() { return p1() && p2(); } template void f(T x) { } int main() { - f(0); // { dg-error "cannot call" } + f(0); // { dg-error "cannot call|uses overloaded operator" } } diff --git a/gcc/testsuite/g++.dg/concepts/req6.C b/gcc/testsuite/g++.dg/concepts/req6.C index e8e94c0..6e111b2 100644 --- a/gcc/testsuite/g++.dg/concepts/req6.C +++ b/gcc/testsuite/g++.dg/concepts/req6.C @@ -7,7 +7,12 @@ template concept bool C1() { return X(); } template - void h(T) { } // { dg-error "not|bool" } + void h(T) { } // OK until used. + +void f() +{ + h(0); // { dg-error "does not have|cannot call" } +} template concept bool C2() { return X() == X(); } // OK diff --git a/gcc/testsuite/g++.dg/concepts/var-templ1.C b/gcc/testsuite/g++.dg/concepts/var-templ1.C index 7dfa240..99ffdc0 100644 --- a/gcc/testsuite/g++.dg/concepts/var-templ1.C +++ b/gcc/testsuite/g++.dg/concepts/var-templ1.C @@ -13,4 +13,4 @@ template constexpr bool f() { return false; } static_assert(f()); -static_assert(v); // { dg-error "constraints" } +static_assert(v); // { dg-error "invalid" } diff --git a/gcc/testsuite/g++.dg/concepts/variadic2.C b/gcc/testsuite/g++.dg/concepts/variadic2.C index f7aa710..e60e9ff 100644 --- a/gcc/testsuite/g++.dg/concepts/variadic2.C +++ b/gcc/testsuite/g++.dg/concepts/variadic2.C @@ -4,10 +4,13 @@ template concept bool Copyable = requires (T t) { T(t); }; template concept bool Constructable = requires { T(); }; template concept bool Both = Copyable && Constructable; -template void f(Ts...) { } -template void f(Ts...) { } +template +constexpr int f(Ts...) { return 0; } // #1 + +template +constexpr int f(Ts...) { return 1; } // #2 int main() { - f(42); + static_assert(f(42) == 1); } diff --git a/gcc/timevar.def b/gcc/timevar.def index 362aa6e..5f12118 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -137,6 +137,8 @@ DEFTIMEVAR (TV_PARSE_FUNC , "parser function body") DEFTIMEVAR (TV_PARSE_INLINE , "parser inl. func. body") DEFTIMEVAR (TV_PARSE_INMETH , "parser inl. meth. body") DEFTIMEVAR (TV_TEMPLATE_INST , "template instantiation") +DEFTIMEVAR (TV_CONSTRAINT_SAT , "constraint satisfaction") +DEFTIMEVAR (TV_CONSTRAINT_SUB , "constraint subsumption") DEFTIMEVAR (TV_FLATTEN_INLINING , "flatten inlining") DEFTIMEVAR (TV_EARLY_INLINING , "early inlining heuristics") DEFTIMEVAR (TV_INLINE_PARAMETERS , "inline parameters") diff --git a/gcc/timevar.h b/gcc/timevar.h index 7097700..3465304 100644 --- a/gcc/timevar.h +++ b/gcc/timevar.h @@ -229,6 +229,14 @@ class auto_timevar m_timer->push (m_tv); } + explicit auto_timevar (timevar_id_t tv) + : m_timer (g_timer) + , m_tv (tv) + { + if (m_timer) + m_timer->push (m_tv); + } + ~auto_timevar () { if (m_timer)