Implement fold expressions.asutton/fold

9 files changed, 742 insertions, 0 deletions

diff --git a/gcc/cp/cp-objcp-common.c b/gcc/cp/cp-objcp-common.c
index 12df4c2667f..6f73c091ee2 100644
--- a/gcc/cp/cp-objcp-common.c
+++ b/gcc/cp/cp-objcp-common.c
@@ -314,6 +314,10 @@ cp_common_init_ts (void)
   MARK_TS_TYPED (LAMBDA_EXPR);
   MARK_TS_TYPED (CTOR_INITIALIZER);
   MARK_TS_TYPED (ARRAY_NOTATION_REF);
+  MARK_TS_TYPED (UNARY_LEFT_FOLD_EXPR);
+  MARK_TS_TYPED (UNARY_RIGHT_FOLD_EXPR);
+  MARK_TS_TYPED (BINARY_LEFT_FOLD_EXPR);
+  MARK_TS_TYPED (BINARY_RIGHT_FOLD_EXPR);
 }
 
 #include "gt-cp-cp-objcp-common.h"
diff --git a/gcc/cp/cp-tree.def b/gcc/cp/cp-tree.def
index e6e90f76c02..b01bcb1214e 100644
--- a/gcc/cp/cp-tree.def
+++ b/gcc/cp/cp-tree.def
@@ -432,6 +432,26 @@ DEFTREECODE (EXPR_PACK_EXPANSION, "expr_pack_expansion", tcc_expression, 3)
    index is a machine integer.  */
 DEFTREECODE (ARGUMENT_PACK_SELECT, "argument_pack_select", tcc_exceptional, 0)
 
+/* Fold expressions allow the expansion of a template argument pack
+   over a binary operator. 
+
+   FOLD_EXPR_MOD_P is true when the fold operation is a compound assignment
+   operator.
+
+   FOLD_EXPR_OP is an INTEGER_CST storing the tree code for the folded
+   expression. Note that when FOLDEXPR_MOD_P is true, the operator is
+   a compound assignment operator for that kind of expression. 
+
+   FOLD_EXPR_PACK is an expression containing an unexpanded parameter pack;
+   when expanded, each term becomes an argument of the folded expression.
+
+   In a BINARY_FOLD_EXPRESSION, FOLD_EXPR_INIT is the non-pack argument. */
+DEFTREECODE (UNARY_LEFT_FOLD_EXPR, "unary_left_fold_expr", tcc_expression, 2)
+DEFTREECODE (UNARY_RIGHT_FOLD_EXPR, "unary_right_fold_expr", tcc_expression, 2)
+DEFTREECODE (BINARY_LEFT_FOLD_EXPR, "binary_left_fold_expr", tcc_expression, 3)
+DEFTREECODE (BINARY_RIGHT_FOLD_EXPR, "binary_right_fold_expr", tcc_expression, 3)
+
+
 /** C++ extensions. */
 
 /* Represents a trait expression during template expansion.  */
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 74636dfbf8f..3e059451e2a 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -84,6 +84,7 @@ c-common.h, not after.
       PACK_EXPANSION_LOCAL_P (in *_PACK_EXPANSION)
       TINFO_RECHECK_ACCESS_P (in TEMPLATE_INFO)
       SIZEOF_EXPR_TYPE_P (in SIZEOF_EXPR)
+      FOLD_EXPR_MODOP_P (*_FOLD_EXPR)
    1: IDENTIFIER_VIRTUAL_P (in IDENTIFIER_NODE)
       TI_PENDING_TEMPLATE_FLAG.
       TEMPLATE_PARMS_FOR_INLINE.
@@ -3033,6 +3034,36 @@ extern void decl_shadowed_for_var_insert (tree, tree);
   TREE_VEC_ELT (ARGUMENT_PACK_ARGS (ARGUMENT_PACK_SELECT_FROM_PACK (NODE)), \
 	        ARGUMENT_PACK_SELECT_INDEX (NODE));
 
+#define FOLD_EXPR_CHECK(NODE) \
+  TREE_CHECK4(NODE, UNARY_LEFT_FOLD_EXPR,UNARY_RIGHT_FOLD_EXPR,BINARY_LEFT_FOLD_EXPR,BINARY_RIGHT_FOLD_EXPR)
+
+#define BINARY_FOLD_EXPR_CHECK(NODE) \
+  TREE_CHECK2 (NODE, BINARY_LEFT_FOLD_EXPR, BINARY_RIGHT_FOLD_EXPR)
+
+/* True if NODE is UNARY_FOLD_EXPR or a BINARY_FOLD_EXPR */
+#define FOLD_EXPR_P(NODE) \
+  TREE_CODE (NODE) == UNARY_LEFT_FOLD_EXPR \
+    || TREE_CODE (NODE) == UNARY_RIGHT_FOLD_EXPR \
+    || TREE_CODE (NODE) == BINARY_LEFT_FOLD_EXPR \
+    || TREE_CODE (NODE) == BINARY_RIGHT_FOLD_EXPR
+
+/* True when NODE is a fold over a compound assignment operator. */
+#define FOLD_EXPR_MODIFY_P(NODE) \
+  TREE_LANG_FLAG_0 (FOLD_EXPR_CHECK (NODE))
+
+/* An INTEGER_CST containing the tree code of the folded operator. */
+#define FOLD_EXPR_OP(NODE) \
+  TREE_OPERAND (FOLD_EXPR_CHECK (NODE), 0)
+
+/* The expression containing an unexpanded parameter pack. */
+#define FOLD_EXPR_PACK(NODE) \
+  TREE_OPERAND (FOLD_EXPR_CHECK (NODE), 1)
+
+/* In a binary fold expression, the argument with no unexpanded 
+   parameter packs. */
+#define FOLD_EXPR_INIT(NODE) \
+  TREE_OPERAND (BINARY_FOLD_EXPR_CHECK (NODE), 2)
+
 /* In a FUNCTION_DECL, the saved language-specific per-function data.  */
 #define DECL_SAVED_FUNCTION_DATA(NODE)			\
   (LANG_DECL_FN_CHECK (FUNCTION_DECL_CHECK (NODE))	\
@@ -6226,6 +6257,10 @@ extern bool check_literal_operator_args		(const_tree, bool *, bool *);
 extern void maybe_warn_about_useless_cast       (tree, tree, tsubst_flags_t);
 extern tree cp_perform_integral_promotions      (tree, tsubst_flags_t);
 
+extern tree finish_left_unary_fold_expr      (tree, int);
+extern tree finish_right_unary_fold_expr     (tree, int);
+extern tree finish_binary_fold_expr          (tree, tree, int);
+
 /* in typeck2.c */
 extern void require_complete_eh_spec_types	(tree, tree);
 extern void cxx_incomplete_type_diagnostic	(const_tree, const_tree, diagnostic_t);
diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c
index e1b320ab1ab..d437cc5e623 100644
--- a/gcc/cp/parser.c
+++ b/gcc/cp/parser.c
@@ -4207,6 +4207,144 @@ cp_parser_statement_expr (cp_parser *parser)
 
 /* Expressions [gram.expr] */
 
+
+/* A helper function for cp_parser_fold_operator. Consume the token
+   and return the matched tree CODE. */
+static inline int
+cp_parser_match_fold_op (cp_parser *parser, int code) 
+{
+  cp_lexer_consume_token (parser->lexer);
+  return code;
+}
+
+/* Parse a fold-operator.
+
+    fold-operator:
+        -  *  /  %  ^  &  |  =  <  >  <<  >>
+      =  -=  *=  /=  %=  ^=  &=  |=  <<=  >>=
+      ==  !=  <=  >=  &&  ||  ,  .*  ->* 
+
+   This returns the tree code corresponding to the matched operator
+   as an int. When the current token matches a compound assignment
+   opertor, the resulting tree code is the negative value of the
+   non-assignment operator. */
+
+static int
+cp_parser_fold_operator (cp_parser *parser) 
+{
+  cp_token* token = cp_lexer_peek_token (parser->lexer);
+  switch (token->type) 
+    {
+    case CPP_PLUS: return cp_parser_match_fold_op (parser, PLUS_EXPR);
+    case CPP_MINUS: return cp_parser_match_fold_op (parser, MINUS_EXPR);
+    case CPP_MULT: return cp_parser_match_fold_op (parser, MULT_EXPR);
+    case CPP_DIV: return cp_parser_match_fold_op (parser, TRUNC_DIV_EXPR);
+    case CPP_MOD: return cp_parser_match_fold_op (parser, TRUNC_MOD_EXPR);
+    case CPP_XOR: return cp_parser_match_fold_op (parser, BIT_XOR_EXPR);
+    case CPP_AND: return cp_parser_match_fold_op (parser, BIT_AND_EXPR);
+    case CPP_OR: return cp_parser_match_fold_op (parser, BIT_IOR_EXPR);
+    case CPP_LSHIFT: return cp_parser_match_fold_op (parser, LSHIFT_EXPR);
+    case CPP_RSHIFT: return cp_parser_match_fold_op (parser, RSHIFT_EXPR);
+
+    case CPP_EQ: return cp_parser_match_fold_op (parser, -NOP_EXPR);
+    case CPP_PLUS_EQ: return cp_parser_match_fold_op (parser, -PLUS_EXPR);
+    case CPP_MINUS_EQ: return cp_parser_match_fold_op (parser, -MINUS_EXPR);
+    case CPP_MULT_EQ: return cp_parser_match_fold_op (parser, -MULT_EXPR);
+    case CPP_DIV_EQ: return cp_parser_match_fold_op (parser, -TRUNC_DIV_EXPR);
+    case CPP_MOD_EQ: return cp_parser_match_fold_op (parser, -TRUNC_MOD_EXPR);
+    case CPP_XOR_EQ: return cp_parser_match_fold_op (parser, -BIT_XOR_EXPR);
+    case CPP_AND_EQ: return cp_parser_match_fold_op (parser, -BIT_AND_EXPR);
+    case CPP_OR_EQ: return cp_parser_match_fold_op (parser, -BIT_IOR_EXPR);
+    case CPP_LSHIFT_EQ: return cp_parser_match_fold_op (parser, -LSHIFT_EXPR);
+    case CPP_RSHIFT_EQ: return cp_parser_match_fold_op (parser, -RSHIFT_EXPR);
+
+    case CPP_EQ_EQ: return cp_parser_match_fold_op (parser, EQ_EXPR);
+    case CPP_NOT_EQ: return cp_parser_match_fold_op (parser, NE_EXPR);
+    case CPP_LESS: return cp_parser_match_fold_op (parser, LT_EXPR);
+    case CPP_GREATER: return cp_parser_match_fold_op (parser, GT_EXPR);
+    case CPP_LESS_EQ: return cp_parser_match_fold_op (parser, LE_EXPR);
+    case CPP_GREATER_EQ: return cp_parser_match_fold_op (parser, GE_EXPR);
+
+    case CPP_AND_AND: return cp_parser_match_fold_op (parser, TRUTH_ANDIF_EXPR);
+    case CPP_OR_OR: return cp_parser_match_fold_op (parser, TRUTH_ORIF_EXPR);
+    
+    case CPP_COMMA: return cp_parser_match_fold_op (parser, COMPOUND_EXPR);
+    
+    case CPP_DOT_STAR: return cp_parser_match_fold_op (parser, DOTSTAR_EXPR);
+    case CPP_DEREF_STAR: return cp_parser_match_fold_op (parser, MEMBER_REF);
+    
+    default: return ERROR_MARK;
+    }
+}
+
+/* Parse a fold-expression.
+
+     fold-expression:
+       ( ... folding-operator cast-expression)
+       ( cast-expression folding-operator ... )
+       ( cast-expression folding operator ... folding-operator cast-expression)
+
+   Note that the '(' and ')' are matched in primary expression. */
+
+static tree
+cp_parser_fold_expression (cp_parser *parser) {
+  cp_id_kind pidk;
+
+  // Left fold
+  if (cp_lexer_next_token_is (parser->lexer, CPP_ELLIPSIS)) 
+    {
+      cp_lexer_consume_token (parser->lexer);
+      int op = cp_parser_fold_operator (parser);
+      if (op == ERROR_MARK) 
+        {
+          cp_parser_error (parser, "expected cast-expression");
+          return error_mark_node;
+        }
+      
+      tree expr = cp_parser_cast_expression (parser, false, false, false, &pidk);
+      if (expr == error_mark_node)
+        return error_mark_node;
+      return finish_left_unary_fold_expr (expr, op);
+    }
+
+  tree expr1 = cp_parser_cast_expression (parser, false, false, false, &pidk);
+  if (expr1 == error_mark_node)
+    return error_mark_node;
+
+  const cp_token* token = cp_lexer_peek_token (parser->lexer);
+  int op = cp_parser_fold_operator (parser);
+  if (op == ERROR_MARK) 
+    {
+      cp_parser_error (parser, "expected cast-expression");
+      return error_mark_node;
+    }
+  
+  if (cp_lexer_next_token_is_not (parser->lexer, CPP_ELLIPSIS)) 
+    {
+      cp_parser_error (parser, "expected ...");
+      return error_mark_node;
+    }
+  cp_lexer_consume_token (parser->lexer);
+
+  // Right fold
+  if (cp_lexer_next_token_is (parser->lexer, CPP_CLOSE_PAREN))
+    return finish_right_unary_fold_expr (expr1, op);
+
+  if (cp_lexer_next_token_is_not (parser->lexer, token->type)) 
+    {
+      error ("mismatched fold-operator in cast expression");
+      return error_mark_node;
+    }
+  cp_lexer_consume_token (parser->lexer);
+
+  // Binary left or right fold
+  tree expr2 = cp_parser_cast_expression (parser, false, false, false, &pidk);
+  if (expr2 == error_mark_node)
+    return error_mark_node;
+  tree t = finish_binary_fold_expr (expr1, expr2, op);
+  return t;
+}
+
 /* Parse a primary-expression.
 
    primary-expression:
@@ -4413,6 +4551,16 @@ cp_parser_primary_expression (cp_parser *parser,
 	  = parser->greater_than_is_operator_p;
 	parser->greater_than_is_operator_p = true;
 
+        // Try to parse a fold-expression.
+        cp_parser_parse_tentatively (parser);
+        tree fold = cp_parser_fold_expression (parser);
+        if (cp_parser_parse_definitely (parser)) 
+          {
+            if (!cp_parser_require (parser, CPP_CLOSE_PAREN, RT_CLOSE_PAREN))
+              cp_parser_skip_to_end_of_statement (parser);
+            return fold;
+          }
+
 	/* Parse the parenthesized expression.  */
 	expr = cp_parser_expression (parser, idk, cast_p, decltype_p);
 	/* Let the front end know that this expression was
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 21d4039b623..db5eac54ad4 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -29,6 +29,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "coretypes.h"
 #include "tm.h"
 #include "tree.h"
+#include "print-tree.h"
 #include "stringpool.h"
 #include "varasm.h"
 #include "attribs.h"
@@ -9823,6 +9824,197 @@ gen_elem_of_pack_expansion_instantiation (tree pattern,
   return t;
 }
 
+tree
+expand_empty_fold (tree t, tsubst_flags_t complain) 
+{
+  tree_code code = (tree_code)TREE_INT_CST_LOW (TREE_OPERAND (t, 0));
+  switch (code)
+    {
+    case PLUS_EXPR: 
+      return build_value_init (integer_type_node, complain);
+    case MULT_EXPR:
+      return build_one_cst (integer_type_node);
+    case BIT_AND_EXPR:
+      return build_minus_one_cst (integer_type_node);
+    case BIT_IOR_EXPR:
+      return build_value_init (integer_type_node, complain);
+    case BIT_XOR_EXPR:
+      return build_value_init (integer_type_node, complain);
+    case TRUTH_ANDIF_EXPR:
+      return boolean_true_node;
+    case TRUTH_ORIF_EXPR:
+      return boolean_false_node;
+    case COMPOUND_EXPR:
+      return void_node;
+    default: 
+      break;
+    }
+  
+  // TODO: Improve diagnostics.
+  if (complain & tf_error)
+    error ("fold of empty expansion");
+  return error_mark_node;
+}
+
+/* Given a fold-expression T and a current LEFT and RIGHT operand,
+   form an expression that combines the two terms using the 
+   operator of T. */
+
+static tree
+fold_expression (tree t, tree left, tree right, tsubst_flags_t complain)
+{
+  tree op = FOLD_EXPR_OP (t);
+  tree_code code = (tree_code)TREE_INT_CST_LOW (op);
+
+  // Handle compound assignment operators.
+  if (FOLD_EXPR_MODIFY_P (t))
+    return build_x_modify_expr (input_location, left, code, right, complain);
+
+  switch (code)
+    {
+    case COMPOUND_EXPR:
+      return build_x_compound_expr (input_location, left, right, complain);
+    case DOTSTAR_EXPR:
+      return build_m_component_ref (left, right, complain);
+    default:
+      return build_x_binary_op (input_location, code, 
+                                left, TREE_CODE (left), 
+                                right, TREE_CODE (right),
+                                /*overload=*/NULL,
+                                complain);
+    }
+}
+
+/* Substitute ARGS into the pack of a fold expression T. */
+
+static inline tree
+tsubst_fold_expr_pack (tree t, tree args, tsubst_flags_t complain, tree in_decl)
+{
+  return tsubst_pack_expansion (FOLD_EXPR_PACK (t), args, complain, in_decl);
+}
+
+/* Substitute ARGS into the pack of a fold expression T. */
+
+static inline tree
+tsubst_fold_expr_init (tree t, tree args, tsubst_flags_t complain, tree in_decl)
+{
+  return tsubst_expr (FOLD_EXPR_INIT (t), args, complain, in_decl, false);
+}
+
+/* Expand a PACK of arguments into a grouped as left fold. 
+   Given a pack containing elements A0, A1, ..., An and an
+   operator @, this builds the expression:
+
+      ((A0 @ A1) @ A2) ... @ An
+
+   Note that PACK must not be empty.
+
+   The operator is defined by the original fold expression T. */
+
+static tree
+expand_left_fold (tree t, tree pack, tsubst_flags_t complain)
+{
+  tree left = TREE_VEC_ELT (pack, 0);
+  for (int i = 1; i < TREE_VEC_LENGTH (pack); ++i) 
+    {
+      tree right = TREE_VEC_ELT (pack, i);
+      left = fold_expression (t, left, right, complain);
+    }
+  return left;
+}
+
+/* Sbustitute into a unary left fold expression. */
+
+static tree
+tsubst_unary_left_fold (tree t, tree args, tsubst_flags_t complain, 
+                        tree in_decl)
+{
+  tree pack = tsubst_fold_expr_pack (t, args, complain, in_decl);
+  if (TREE_VEC_LENGTH (pack) == 0)
+    return expand_empty_fold (t, complain);
+  else
+    return expand_left_fold (t, pack, complain);
+}
+
+/* Substitute into a binary left fold expression.
+
+   Do ths by building a single (non-empty) vector of argumnts and
+   building the expression from those elements. */
+
+static tree
+tsubst_binary_left_fold (tree t, tree args, tsubst_flags_t complain, 
+                         tree in_decl)
+{
+  tree pack = tsubst_fold_expr_pack (t, args, complain, in_decl);
+  tree init = tsubst_fold_expr_init (t, args, complain, in_decl);
+
+  tree vec = make_tree_vec (TREE_VEC_LENGTH (pack) + 1);
+  TREE_VEC_ELT (vec, 0) = init;
+  for (int i = 0; i < TREE_VEC_LENGTH (pack); ++i)
+    TREE_VEC_ELT (vec, i + 1) = TREE_VEC_ELT (pack, i);
+
+  return expand_left_fold (t, vec, complain);
+}
+
+/* Expand a PACK of arguments into a grouped as right fold. 
+   Given a pack containing elementns A0, A1, ..., and an 
+   operator @, this builds the expression:
+
+      A0@ ... (An-2 @ (An-1 @ An))
+
+   Note that PACK must not be empty.
+
+   The operator is defined by the original fold expression T. */
+
+tree
+expand_right_fold (tree t, tree pack, tsubst_flags_t complain)
+{
+  // Build the expression.
+  int n = TREE_VEC_LENGTH (pack);
+  tree right = TREE_VEC_ELT (pack, n - 1);
+  for (--n; n != 0; --n)
+    {
+      tree left = TREE_VEC_ELT (pack, n - 1);
+      right = fold_expression (t, left, right, complain);
+    }
+  return right;
+}
+
+/* Substitute into a unary right fold expression. */
+
+static tree
+tsubst_unary_right_fold (tree t, tree args, tsubst_flags_t complain, 
+                         tree in_decl)
+{
+  tree pack = tsubst_fold_expr_pack (t, args, complain, in_decl);
+  if (TREE_VEC_LENGTH (pack) == 0)
+    return expand_empty_fold (t, complain);
+  else
+    return expand_right_fold (t, pack, complain);
+}
+
+/* Substitute into a binary right fold expression.
+
+   Do ths by building a single (non-empty) vector of arguments and
+   building the expression from those elements. */
+
+static tree
+tsubst_binary_right_fold (tree t, tree args, tsubst_flags_t complain, 
+                         tree in_decl)
+{
+  tree pack = tsubst_fold_expr_pack (t, args, complain, in_decl);
+  tree init = tsubst_fold_expr_init (t, args, complain, in_decl);
+
+  int n = TREE_VEC_LENGTH (pack);
+  tree vec = make_tree_vec (n + 1);
+  for (int i = 0; i < n; ++i)
+    TREE_VEC_ELT (vec, i) = TREE_VEC_ELT (pack, i);
+  TREE_VEC_ELT (vec, n) = init;
+
+  return expand_right_fold (t, vec, complain);
+}
+
+
 /* Substitute ARGS into T, which is an pack expansion
    (i.e. TYPE_PACK_EXPANSION or EXPR_PACK_EXPANSION). Returns a
    TREE_VEC with the substituted arguments, a PACK_EXPANSION_* node
@@ -13344,6 +13536,15 @@ tsubst_copy (tree t, tree args, tsubst_flags_t complain, tree in_decl)
       gcc_assert (!uses_template_parms (t));
       return t;
 
+    case UNARY_LEFT_FOLD_EXPR:
+      return tsubst_unary_left_fold (t, args, complain, in_decl);
+    case UNARY_RIGHT_FOLD_EXPR:
+      return tsubst_unary_right_fold (t, args, complain, in_decl);
+    case BINARY_LEFT_FOLD_EXPR:
+      return tsubst_binary_left_fold (t, args, complain, in_decl);
+    case BINARY_RIGHT_FOLD_EXPR:
+      return tsubst_binary_right_fold (t, args, complain, in_decl);
+
     default:
       /* We shouldn't get here, but keep going if !ENABLE_CHECKING.  */
       gcc_checking_assert (false);
@@ -21169,6 +21370,13 @@ type_dependent_expression_p (tree expression)
   if (identifier_p (expression) || TREE_CODE (expression) == USING_DECL)
     return true;
 
+  /* A fold expression is type-dependent. */
+  if (TREE_CODE (expression) == UNARY_LEFT_FOLD_EXPR
+      || TREE_CODE (expression) == UNARY_RIGHT_FOLD_EXPR
+      || TREE_CODE (expression) == BINARY_LEFT_FOLD_EXPR
+      || TREE_CODE (expression) == BINARY_RIGHT_FOLD_EXPR)
+    return true;
+
   /* Some expression forms are never type-dependent.  */
   if (TREE_CODE (expression) == PSEUDO_DTOR_EXPR
       || TREE_CODE (expression) == SIZEOF_EXPR
diff --git a/gcc/cp/semantics.c b/gcc/cp/semantics.c
index ebd9a43b949..0d0b736115c 100644
--- a/gcc/cp/semantics.c
+++ b/gcc/cp/semantics.c
@@ -7645,4 +7645,72 @@ capture_decltype (tree decl)
   return type;
 }
 
+/* Build a unary fold expression of EXPR over OP. If IS_RIGHT is true,
+   this is a right unary fold. Otherwise it is a left unary fold. */
+
+static tree 
+finish_unary_fold_expr (tree expr, int op, tree_code dir) 
+{
+  // Build a pack expansion (assuming expr has pack type).
+  if (!PACK_EXPANSION_P (TREE_TYPE (expr)))
+    {
+      error ("argument %qE is not a pack expansion", expr);
+      return error_mark_node;
+    }
+  tree pack = make_pack_expansion (expr);
+
+  // Build the fold expression.
+  tree code = build_int_cstu (integer_type_node, abs (op));
+  tree fold = build_min (dir, unknown_type_node, code, pack);
+  FOLD_EXPR_MODIFY_P (fold) = (op < 0);
+  return fold;
+}
+
+tree 
+finish_left_unary_fold_expr (tree expr, int op) 
+{
+  return finish_unary_fold_expr(expr, op, UNARY_LEFT_FOLD_EXPR);
+}
+
+tree 
+finish_right_unary_fold_expr (tree expr, int op) 
+{
+  return finish_unary_fold_expr(expr, op, UNARY_RIGHT_FOLD_EXPR);
+}
+
+
+/* Build a binary fold expression over EXPR1 and EXPR2. The
+   associativity of the fold is determined EXPR1 and EXPR2 (whichever
+   has an unexpanded parameter pack). */
+
+tree
+finish_binary_fold_expr (tree pack, tree init, int op, tree_code dir) {
+  pack = make_pack_expansion (pack);
+  tree code = build_int_cstu (integer_type_node, abs (op));
+  tree fold = build_min (dir, unknown_type_node, code, pack, init);
+  FOLD_EXPR_MODIFY_P (fold) = (op < 0);
+  return fold;
+}
+
+tree 
+finish_binary_fold_expr (tree expr1, tree expr2, int op) 
+{
+  // Determine which expr has an unexpanded parameter pack and
+  // set the pack and initial term. 
+  tree type1 = TREE_TYPE (expr1);
+  tree type2 = TREE_TYPE (expr2);
+  if (PACK_EXPANSION_P (type1) && !PACK_EXPANSION_P (type2))
+    return finish_binary_fold_expr (expr1, expr2, op, BINARY_RIGHT_FOLD_EXPR);
+  else if (PACK_EXPANSION_P (type2) && !PACK_EXPANSION_P (type1))
+    return finish_binary_fold_expr (expr2, expr1, op, BINARY_LEFT_FOLD_EXPR);
+  else
+    {
+      if (PACK_EXPANSION_P (type1))
+        error ("both arguments in binary fold have unexpanded parameter packs");
+      else
+        error ("no unexpanded parameter packs in binary fold");
+    }
+  return error_mark_node;
+}
+
 #include "gt-cp-semantics.h"
diff --git a/gcc/testsuite/g++.dg/cpp1z/fold1.C b/gcc/testsuite/g++.dg/cpp1z/fold1.C
new file mode 100644
index 00000000000..8d08eeb239e
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1z/fold1.C
@@ -0,0 +1,56 @@
+// { dg-do run }
+// { dg-options "-std=c++1z" }
+
+#include <cassert>
+
+// Check the semantics of a couple of operations to make sure
+// that the expressions are formed correctly.
+
+#define COMMA ,
+
+#define MAKE_FNS(name, op) \
+  template<typename... Ts> \
+    auto unary_left_ ## name (Ts... ts) { return (... op ts); } \
+  template<typename... Ts> \
+    auto unary_right_ ## name (Ts... ts) { return (ts op ...); } \
+  template<typename T, typename... Ts> \
+    auto binary_left_ ## name (T x, Ts... ts) { return (x op ... op ts); } \
+  template<typename T, typename... Ts> \
+    auto binary_right_ ## name (T x, Ts... ts) { return (ts op ... op x); }
+
+MAKE_FNS (add, +);
+MAKE_FNS (sub, -);
+
+int main() { 
+  assert(unary_left_add() == 0);
+  assert(unary_left_add(1) == 1);
+  assert(unary_left_add(1, 2, 3) == 6);
+  
+  assert(unary_right_add() == 0);
+  assert(unary_right_add(1) == 1);
+  assert(unary_right_add(1, 2, 3) == 6);
+
+  assert(binary_left_add(1) == 1);
+  assert(binary_left_add(1, 1) == 2);
+  assert(binary_left_add(1, 1, 2, 3) == 7);
+
+  assert(binary_right_add(1) == 1);
+  assert(binary_right_add(1, 1) == 2);
+  assert(binary_right_add(1, 1, 2, 3) == 7);
+
+  // unary_left_sub(); // { dg-error "empty"}
+  assert(unary_left_sub(1) == 1);
+  assert(unary_left_sub(1, 2, 3) == -4);
+  
+  // unary_right_sub(); // { dg-error "empty"}
+  assert(unary_right_sub(1) == 1);
+  assert(unary_right_sub(1, 2, 3) == 2);
+
+  assert(binary_left_sub(1) == 1);
+  assert(binary_left_sub(1, 1) == 0);
+  assert(binary_left_sub(1, 1, 2, 3) == -5);
+
+  assert(binary_right_sub(1) == 1);
+  assert(binary_right_sub(1, 1) == 0);
+  assert(binary_right_sub(1, 1, 2, 3) == 1);
+}
diff --git a/gcc/testsuite/g++.dg/cpp1z/fold2.C b/gcc/testsuite/g++.dg/cpp1z/fold2.C
new file mode 100644
index 00000000000..304e993f812
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1z/fold2.C
@@ -0,0 +1,118 @@
+// { dg-do compile }
+// { dg-options "-std=c++1z" }
+
+// Check that we can fold over all of the operators required
+// by the standard in every possible way.
+
+#define COMMA ,
+
+#define MAKE_FNS(name, op) \
+  template<typename... Ts> \
+    auto unary_left_ ## name (Ts... ts) { return (... op ts); } \
+  template<typename... Ts> \
+    auto unary_right_ ## name (Ts... ts) { return (ts op ...); } \
+  template<typename T, typename... Ts> \
+    auto binary_left_ ## name (T x, Ts... ts) { return (x op ... op ts); } \
+  template<typename T, typename... Ts> \
+    auto binary_right_ ## name (T x, Ts... ts) { return (ts op ... op x); }
+
+// TODO: These are compile-only tests...
+#define CHECK_FN(name) \
+  unary_left_ ## name (a); \
+  unary_left_ ## name (a, b, c); \
+  unary_right_ ## name (a); \
+  unary_right_ ## name (a, b, c); \
+  binary_left_ ## name (a); \
+  binary_left_ ## name (a, b, c, d); \
+  binary_right_ ## name (d); \
+  binary_right_ ## name (d, a, b, c);
+
+MAKE_FNS (add, +);
+MAKE_FNS (sub, -);
+MAKE_FNS (mul, *);
+MAKE_FNS (div, /);
+MAKE_FNS (mod, %);
+MAKE_FNS (bxor, ^);
+MAKE_FNS (bor, |);
+MAKE_FNS (band, &);
+MAKE_FNS (lsh, <<);
+MAKE_FNS (rsh, >>);
+
+MAKE_FNS (assign, =);
+MAKE_FNS (addi, +=);
+MAKE_FNS (subi, -=);
+MAKE_FNS (muli, *=);
+MAKE_FNS (divi, /=);
+MAKE_FNS (modi, %=);
+MAKE_FNS (bxori, ^=);
+MAKE_FNS (bori, |=);
+MAKE_FNS (bandi, &=);
+MAKE_FNS (lshi, <<=);
+MAKE_FNS (rshi, >>=);
+
+MAKE_FNS (eq, ==);
+MAKE_FNS (ne, !=);
+MAKE_FNS (lt, <);
+MAKE_FNS (gt, >);
+MAKE_FNS (le, <);
+MAKE_FNS (ge, >);
+
+MAKE_FNS (land, &&);
+MAKE_FNS (lor, ||);
+
+MAKE_FNS (comma, COMMA);
+MAKE_FNS (dot_star, .*);
+MAKE_FNS (arrow_star, ->*);
+
+int main() { 
+  int a = 0, b = 0, c = 0, d = 0;
+
+  CHECK_FN (add);
+  CHECK_FN (sub);
+  CHECK_FN (mul);
+  CHECK_FN (div);
+  CHECK_FN (mod);
+  CHECK_FN (bxor);
+  CHECK_FN (bor);
+  CHECK_FN (band);
+  CHECK_FN (lsh);
+  CHECK_FN (rsh);
+
+  // CHECK_FN (assign);
+  CHECK_FN (addi);
+  CHECK_FN (subi);
+  CHECK_FN (muli);
+  CHECK_FN (divi);
+  CHECK_FN (modi);
+  CHECK_FN (bxori);
+  CHECK_FN (bori);
+  CHECK_FN (bandi);
+  CHECK_FN (lshi);
+  CHECK_FN (rshi);
+  
+  CHECK_FN (eq);
+  CHECK_FN (ne);
+  CHECK_FN (lt);
+  CHECK_FN (gt);
+  CHECK_FN (le);
+  CHECK_FN (ge);
+  CHECK_FN (eq);
+  CHECK_FN (ne);
+  
+  CHECK_FN (comma);
+
+  struct X {
+    int a;
+  } x, *px = &x;
+
+  int X::* pm = &X::a;
+  unary_left_arrow_star (px, pm); // px ->* pm
+  unary_right_arrow_star (px, pm); // px ->* pm
+  binary_left_arrow_star (px, pm); // px ->* pm
+  binary_right_arrow_star (pm, px); // px ->* pm
+
+  unary_left_dot_star (x, pm); // x ->* pm
+  unary_right_dot_star (x, pm); // x ->* pm
+  binary_left_dot_star (x, pm); // x ->* pm
+  binary_right_dot_star (pm, x); // x ->* pm
+}
diff --git a/gcc/testsuite/g++.dg/cpp1z/fold3.C b/gcc/testsuite/g++.dg/cpp1z/fold3.C
new file mode 100644
index 00000000000..587d7cb7f2a
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1z/fold3.C
@@ -0,0 +1,85 @@
+// { dg-do compile }
+// { dg-options "-std=c++1z" }
+
+// Check that empty expansions and required failures.
+
+#define COMMA ,
+
+#define MAKE_FN(name, op) \
+  template<typename... Ts> \
+    constexpr auto name (Ts... ts) { return (... op ts); } // { dg-error "empty" }
+
+MAKE_FN (add, +);
+MAKE_FN (sub, -);
+MAKE_FN (mul, *);
+MAKE_FN (div, /);
+MAKE_FN (mod, %);
+MAKE_FN (bxor, ^);
+MAKE_FN (bor, |);
+MAKE_FN (band, &);
+MAKE_FN (lsh, <<);
+MAKE_FN (rsh, >>);
+
+MAKE_FN (assign, =);
+MAKE_FN (addi, +=);
+MAKE_FN (subi, -=);
+MAKE_FN (muli, *=);
+MAKE_FN (divi, /=);
+MAKE_FN (modi, %=);
+MAKE_FN (bxori, ^=);
+MAKE_FN (bori, |=);
+MAKE_FN (bandi, &=);
+MAKE_FN (lshi, <<=);
+MAKE_FN (rshi, >>=);
+
+MAKE_FN (eq, ==);
+MAKE_FN (ne, !=);
+MAKE_FN (lt, <);
+MAKE_FN (gt, >);
+MAKE_FN (le, <);
+MAKE_FN (ge, >);
+
+MAKE_FN (land, &&);
+MAKE_FN (lor, ||);
+
+MAKE_FN (comma, COMMA);
+MAKE_FN (dot_star, .*);
+MAKE_FN (arrow_star, ->*);
+
+int main() { 
+  static_assert(add() == int(), "");
+  static_assert(mul() == 1, "");
+  static_assert(bxor() == int(), "");
+  static_assert(bor() == int(), "");
+  static_assert(band() == -1, "");
+  static_assert(land() == true, "");
+  static_assert(lor() == false, "");
+  comma(); // No value to theck
+
+  // These are all errors, but the error is emitted at the point
+  // of instantiation (line 10).
+  sub();
+  div();
+  mod();
+  lsh();
+  rsh();
+  assign();
+  addi();
+  subi();
+  muli();
+  divi();
+  modi();
+  bxori();
+  bori();
+  bandi();
+  lshi();
+  rshi();
+  eq();
+  ne();
+  lt();
+  gt();
+  le();
+  ge();
+  dot_star();
+  arrow_star();
+}