[c++-concepts] Semantic handling of requirements

[c++-concepts] Semantic handling of requirements

[Andrew Sutton]

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

Adding initial support for the semantic analysis of template
requirements. This patch adds features for reducing requires clauses
into logical formulas comprised only of atomic propositions and
logical connectives.

The next patch will add inlining for constraint predicates.

I had hoped to add the file as constraint.cc, but the build system in
this version doesn't seem to have to build support for .cc files (kept
getting "no such file: cp/constraint.o", but adding the file as .c
worked just fine.


2013-03-11  Andrew Sutton  <andrew.n.sutton@gmail.com>
        * gcc/cp/Make-lang.in: Add constraint.c
        * gcc/cp/constraint.c: New
        (conjoin_requirements): New
        (disjoin_requirements): New
        (requirement_reduction): New class
        (reduce_requirements): New
        * gcc/cp/cp-tree.h (reduce_requrements): New
        (conjoin_requirements): New
        (disjoin_requirements): New
        * gcc/cp/cp-tree.h (finish_template_template_parm) Comments.
        * gcc/cp/semantics.c (finish_template_requirements) Start
        working with requirements.

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

Index: gcc/cp/Make-lang.in
===================================================================
--- gcc/cp/Make-lang.in	(revision 196581)
+++ gcc/cp/Make-lang.in	(working copy)
@@ -80,7 +80,7 @@ CXX_AND_OBJCXX_OBJS = cp/call.o cp/decl.
  cp/typeck.o cp/cvt.o cp/except.o cp/friend.o cp/init.o cp/method.o \
  cp/search.o cp/semantics.o cp/tree.o cp/repo.o cp/dump.o cp/optimize.o \
  cp/mangle.o cp/cp-objcp-common.o cp/name-lookup.o cp/cxx-pretty-print.o \
- cp/cp-gimplify.o $(CXX_C_OBJS)
+ cp/constraint.o cp/cp-gimplify.o $(CXX_C_OBJS)
 
 # Language-specific object files for C++.
 CXX_OBJS = cp/cp-lang.o c-family/stub-objc.o $(CXX_AND_OBJCXX_OBJS)
@@ -343,5 +343,9 @@ cp/name-lookup.o: cp/name-lookup.c $(CON
 	$(TM_H) $(CXX_TREE_H) $(TIMEVAR_H) gt-cp-name-lookup.h $(PARAMS_H) \
 	$(DIAGNOSTIC_CORE_H) $(FLAGS_H) debug.h pointer-set.h
 
+cp/constraint.o: cp/constraint.c $(CXX_TREE_H) $(TM_H) $(FLAGS_H) toplev.h \
+  $(DIAGNOSTIC_CORE_H) intl.h $(TARGET_H) langhooks.h $(TIMEVAR_H) \
+  c-family/c-objc.h
+
 cp/cxx-pretty-print.o: cp/cxx-pretty-print.c $(CXX_PRETTY_PRINT_H) \
   $(CONFIG_H) $(SYSTEM_H) $(TM_H) coretypes.h $(CXX_TREE_H) tree-pretty-print.h
Index: gcc/cp/constraint.c
===================================================================
--- gcc/cp/constraint.c	(revision 0)
+++ gcc/cp/constraint.c	(revision 0)
@@ -0,0 +1,316 @@
+/* Process declarations and variables for C++ compiler.
+   Copyright (C) 1988-2013 Free Software Foundation, Inc.
+   Contributed by Michael Tiemann (tiemann@cygnus.com)
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+// Components for process constraints and evaluating constraints.
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "cp-tree.h"
+#include "c-family/c-common.h"
+#include "c-family/c-objc.h"
+#include "tree-inline.h"
+#include "intl.h"
+#include "toplev.h"
+#include "flags.h"
+#include "timevar.h"
+#include "diagnostic.h"
+#include "cgraph.h"
+#include "tree-iterator.h"
+#include "vec.h"
+#include "target.h"
+#include "gimple.h"
+#include "bitmap.h"
+
+
+// -------------------------------------------------------------------------- //
+// Requirement Construction
+//
+// Facilities for building and manipulating template requirements. 
+//
+// TODO: Simply assinging boolean_type_node to the result type of the expression
+// seems right thing for constraints, but in the long-term we might want to be
+// more flexible (i.e., allow some form of overload resolution?).
+
+
+// Returns the conjunction of two requirements A and B, where A and B are
+// reduced terms in the constraints languaage. Returns NULL_TREE if either A or
+// B are NULL_TREE.
+tree
+conjoin_requirements (tree a, tree b)
+{
+  if (a && b)
+    return build_min (TRUTH_ANDIF_EXPR, boolean_type_node, a, b);
+  else
+    return NULL_TREE;
+}
+
+// Returns the disjunction of two requirements A and B, where A and B are
+// reduced terms in the constraints languaage. Returns NULL_TREE if either A or
+// B are NULL_TREE.
+tree
+disjoin_requirements (tree a, tree b)
+{
+  if (a && b)
+    return build_min (TRUTH_ORIF_EXPR, boolean_type_node, a, b);
+  else
+    return NULL_TREE;
+}
+
+
+// -------------------------------------------------------------------------- //
+// Requirement Reduction
+//
+// Reduces a template requirement to a logical formula written in terms of
+// atomic propositions, returing the new expression.  If the expression cannot
+// be reduced, a NULL_TREE is returned, indicating failure to reduce the
+// original requirment. 
+
+// Encapsulates the reduction rules for the constraint language.
+struct requirement_reduction
+{
+  // Reductions for general classes of nodes.
+  tree node (tree);
+  tree expr (tree);
+  tree stmt (tree);
+  tree decl (tree);
+  tree misc (tree);
+
+  // Reductions for specific kinds of nodes.
+  tree logical_expr (tree);
+  tree call_expr    (tree);
+  tree template_id  (tree);
+  tree stmt_list    (tree);
+};
+
+
+// Reduce the requirement T into a logical formula written in terms of
+// atomic propositions.
+tree 
+requirement_reduction::node (tree t)
+{
+  switch (TREE_CODE_CLASS (TREE_CODE (t))) 
+    {
+    case tcc_unary:
+    case tcc_binary:
+    case tcc_expression:
+    case tcc_vl_exp:
+      return expr (t);
+    
+    case tcc_statement:   
+      return stmt (t);
+    
+    case tcc_declaration: 
+      return decl (t);
+    
+    case tcc_exceptional: 
+      return misc (t);
+    
+    // These kinds of expressions are atomic.
+    case tcc_constant:
+    case tcc_reference:
+    case tcc_comparison:
+      return t;
+
+    default:
+      gcc_unreachable ();
+    }
+  return NULL_TREE;
+}
+
+// Reduction rules for the expression node T.
+tree
+requirement_reduction::expr (tree t)
+{
+  switch (TREE_CODE (t))
+    {
+    case TRUTH_ANDIF_EXPR:
+    case TRUTH_ORIF_EXPR:  
+      return logical_expr (t);
+
+    case CALL_EXPR:        
+      return call_expr (t);
+
+    case TEMPLATE_ID_EXPR: 
+      return template_id (t);
+
+    case CAST_EXPR:        
+      return node (TREE_VALUE (TREE_OPERAND (t, 0)));
+    
+    case BIND_EXPR:        
+      return node (BIND_EXPR_BODY (t));
+
+    // Do not recurse.
+    case TAG_DEFN:         
+      return NULL_TREE;
+
+    // Everything else is atomic.
+    default:
+      return t;
+    }
+}
+
+
+// Reduction rules for the statement T.
+tree
+requirement_reduction::stmt (tree t)
+{
+  switch (TREE_CODE (t))
+    {
+    // Reduce the returned expression.
+    case RETURN_EXPR:
+      return node (TREE_OPERAND (t, 0));
+
+    // These statements do not introduce propositions
+    // in the constraints language. Do not recurse.
+    case DECL_EXPR:
+    case USING_STMT:
+      return NULL_TREE;
+    
+    default:
+      gcc_unreachable ();
+    }
+  return NULL_TREE;
+}
+
+// Reduction rules for the declaration T.
+tree
+requirement_reduction::decl (tree t)
+{
+  switch (TREE_CODE (t))
+    {
+    // References to var decls are atomic.
+    case VAR_DECL:
+      return t;
+    
+    default:
+      gcc_unreachable ();
+    }
+  return NULL_TREE;
+}
+
+// Reduction rules for the node T.
+tree
+requirement_reduction::misc (tree t)
+{
+  switch (TREE_CODE (t))
+    {
+    // Errors and traits are atomic.
+    case ERROR_MARK:
+    case TRAIT_EXPR:
+      return t;
+
+    case STATEMENT_LIST:
+      return stmt_list (t);
+    
+    default:
+      gcc_unreachable ();
+    }
+  return NULL_TREE;
+}
+
+// Reduction rules for the binary logical expression T (&& and ||).
+//
+// Generate a new expression from the reduced operands. If either operand
+// cannot be reduced, then the resulting expression is null.
+tree
+requirement_reduction::logical_expr (tree t)
+{
+  tree l = expr (TREE_OPERAND (t, 0));
+  tree r = expr (TREE_OPERAND (t, 1));
+  if (l && r)
+    {
+      t = copy_node (t);
+      TREE_OPERAND (t, 0) = l;
+      TREE_OPERAND (t, 1) = r;
+      return t;
+    }
+  else
+    return NULL_TREE;
+}
+
+// Reduction rules for the call expression T.
+//
+// If T is a call to a constraint instantiate it's definition and
+// recursively reduce its returned expression.
+tree
+requirement_reduction::call_expr (tree t)
+{
+  // TODO: Recursively reduce the call expression t if it is a constraint.
+  return t;
+}
+
+// Reduction rules for the template-id T.
+//
+// It turns out that we often get requirements being written like this:
+//
+//    template<typename T>
+//      requires Foo<T>
+//    void f()
+//
+// Where Foo<T> should actually be written as Foo<T>(). Generate an
+// error and suggest the improved writing.
+tree
+requirement_reduction::template_id (tree t)
+{
+  vec<tree, va_gc>* args = NULL;
+  tree c = finish_call_expr (t, &args, true, false, 0);
+  error ("invalid requirement");
+  inform (input_location, "did you mean %qE", c);
+  return NULL_TREE;
+}
+
+// Reduction rules for the statement list STMTS.
+//
+// Recursively reduce each statement in the list, concatenating each
+// reduced result into a conjunction of requirements. 
+//
+// A constexpr function may include statements other than a return
+// statement. The primary purpose of these rules is to filter those
+// non-return statements from the constraints language.
+tree
+requirement_reduction::stmt_list (tree stmts)
+{
+  tree lhs = NULL_TREE;
+  tree_stmt_iterator i = tsi_start (stmts);
+  while (!tsi_end_p (i))
+    {
+      if (tree rhs = node (tsi_stmt (i)))
+        {
+          if (!lhs)
+            lhs = rhs;
+          else
+            lhs = conjoin_requirements (lhs, rhs);
+        }
+      tsi_next (&i);
+    }
+  return lhs;
+}
+
+// Reduce the requirement T into a logical formula written in terms of
+// atomic propositions.
+tree
+reduce_requirements (tree t)
+{
+  requirement_reduction reduce;
+  return reduce.node (t);
+}
Index: gcc/cp/parser.c
===================================================================
--- gcc/cp/parser.c	(revision 196581)
+++ gcc/cp/parser.c	(working copy)
@@ -12502,6 +12502,7 @@ cp_parser_type_parameter (cp_parser* par
 	parameter = finish_template_template_parm (class_type_node,
 						   identifier);
 
+        // Restore the saved constraints.
         current_template_reqs = saved_template_reqs;
 
 	/* If the next token is an `=', then there is a
Index: gcc/cp/cp-tree.h
===================================================================
--- gcc/cp/cp-tree.h	(revision 196581)
+++ gcc/cp/cp-tree.h	(working copy)
@@ -6049,6 +6049,12 @@ extern bool cxx_omp_privatize_by_referen
 extern void suggest_alternatives_for            (location_t, tree);
 extern tree strip_using_decl                    (tree);
 
+/* in constraint.c */
+extern tree conjoin_requirements                (tree, tree);
+extern tree disjoin_requirements                (tree, tree);
+extern tree reduce_requirements                 (tree);
+
+
 /* -- end of C++ */
 
 #endif /* ! GCC_CP_TREE_H */
Index: gcc/cp/semantics.c
===================================================================
--- gcc/cp/semantics.c	(revision 196581)
+++ gcc/cp/semantics.c	(working copy)
@@ -9561,14 +9561,24 @@ is_lambda_ignored_entity (tree val)
   return false;
 }
 
-// Decompose the template requirements, given by EXPRESSION, into a set of
-// assumptions for the local scope.
+
+// Semantics for constraints.
+
+
+// Finish the template requirement, EXPRESSION, by first reducing it into
+// a logical formula written in terms of atomic propositions, and then
+// decomposing it into sets of those propositions.
 tree
 finish_template_requirements (tree expression)
 {
   if (expression == error_mark_node)
     return NULL_TREE;
 
+  // tree reduced = reduce_requirements (expression);
+  
+  // TODO: Perform an initial left/right decomposition on the
+  // reduced requirements.
+
   sorry ("no template requirements yet");
   return NULL_TREE;
 }