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.

Co-Authored-By: Jason Merrill <jason@redhat.com>

From-SVN: r238558

1 files changed, 170 insertions, 23 deletions

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, "<unsatisfied-constrained-placeholder>");
+      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, "<valid-expression ");
+  pp_cxx_left_paren (pp);
   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, "<valid-type ");
   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, "<implicitly-conversion ");
+  pp_cxx_left_paren (pp);
   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, "<argument-deduction ");
+  pp_cxx_left_paren (pp);
   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, "<requires ");
   if (tree parms = PARM_CONSTR_PARMS (t))
     {
-      if (parms)
 	pp_cxx_parameter_declaration_clause (pp, parms);
       pp_cxx_whitespace (pp);
     }
   pp_cxx_constraint (pp, PARM_CONSTR_OPERAND (t));
-  pp_right_paren (pp);
+  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 ();
     }