commit 5946e0026988259a71992e3a653556b76460919c
Author: Jason Merrill <jason@redhat.com>
Date:   Wed Sep 16 15:27:10 2015 -0400

    	Implement N4295 fold-expressions.
    
    	* cp-tree.def: Add UNARY_LEFT_FOLD_EXPR, UNARY_RIGHT_FOLD_EXPR,
    	BINARY_LEFT_FOLD_EXPR, BINARY_RIGHT_FOLD_EXPR.
    	* cp-objcp-common.c (cp_common_init_ts): Handle them.
    	* cp-tree.h (FOLD_EXPR_CHECK, BINARY_FOLD_EXPR_CHECK, FOLD_EXPR_P)
    	(FOLD_EXPR_MODIFY_P, FOLD_EXPR_OP, FOLD_EXPR_PACK, FOLD_EXPR_INIT): New.
    	* parser.c (cp_parser_skip_to_closing_parenthesis): Split out...
    	(cp_parser_skip_to_closing_parenthesis_1): This function.  Change
    	or_comma parameter to or_ttype.
    	(cp_parser_fold_operator, cp_parser_fold_expr_p)
    	(cp_parser_fold_expression): New.
    	(cp_parser_primary_expression): Use them.
    	* pt.c (expand_empty_fold, fold_expression, tsubst_fold_expr_pack)
    	(tsubst_fold_expr_init, expand_left_fold, tsubst_unary_left_fold)
    	(tsubst_binary_left_fold, expand_right_fold)
    	(tsubst_unary_right_fold, tsubst_binary_right_fold): New.
    	(tsubst_copy): Use them.
    	(type_dependent_expression_p): Handle fold-expressions.
    	* semantics.c (finish_unary_fold_expr)
    	(finish_left_unary_fold_expr, finish_right_unary_fold_expr)
    	(finish_binary_fold_expr): New.

diff --git a/gcc/cp/cp-objcp-common.c b/gcc/cp/cp-objcp-common.c
index 808defd..22f063b 100644
--- a/gcc/cp/cp-objcp-common.c
+++ b/gcc/cp/cp-objcp-common.c
@@ -311,6 +311,10 @@ cp_common_init_ts (void)
   MARK_TS_TYPED (CTOR_INITIALIZER);
   MARK_TS_TYPED (ARRAY_NOTATION_REF);
   MARK_TS_TYPED (REQUIRES_EXPR);
+  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 61acf27..7df72c5 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 8643e08..80d6c4e 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -80,6 +80,7 @@ c-common.h, not after.
       COMPOUND_REQ_NOEXCEPT_P (in COMPOUND_REQ)
       WILDCARD_PACK_P (in WILDCARD_DECL)
       BLOCK_OUTER_CURLY_BRACE_P (in BLOCK)
+      FOLD_EXPR_MODOP_P (*_FOLD_EXPR)
    1: IDENTIFIER_VIRTUAL_P (in IDENTIFIER_NODE)
       TI_PENDING_TEMPLATE_FLAG.
       TEMPLATE_PARMS_FOR_INLINE.
@@ -3249,6 +3250,37 @@ 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))	\
@@ -6567,6 +6599,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 3a68dd7..4f424b6 100644
--- a/gcc/cp/parser.c
+++ b/gcc/cp/parser.c
@@ -3175,20 +3175,20 @@ cp_parser_parse_and_diagnose_invalid_type_name (cp_parser *parser)
 
 /* Consume tokens up to, and including, the next non-nested closing `)'.
    Returns 1 iff we found a closing `)'.  RECOVERING is true, if we
-   are doing error recovery. Returns -1 if OR_COMMA is true and we
-   found an unnested comma.  */
+   are doing error recovery. Returns -1 if OR_TTYPE is not CPP_EOF and we
+   found an unnested token of that type.  */
 
 static int
-cp_parser_skip_to_closing_parenthesis (cp_parser *parser,
-				       bool recovering,
-				       bool or_comma,
-				       bool consume_paren)
+cp_parser_skip_to_closing_parenthesis_1 (cp_parser *parser,
+					 bool recovering,
+					 cpp_ttype or_ttype,
+					 bool consume_paren)
 {
   unsigned paren_depth = 0;
   unsigned brace_depth = 0;
   unsigned square_depth = 0;
 
-  if (recovering && !or_comma
+  if (recovering && or_ttype == CPP_EOF
       && cp_parser_uncommitted_to_tentative_parse_p (parser))
     return 0;
 
@@ -3196,6 +3196,11 @@ cp_parser_skip_to_closing_parenthesis (cp_parser *parser,
     {
       cp_token * token = cp_lexer_peek_token (parser->lexer);
 
+      /* Have we found what we're looking for before the closing paren?  */
+      if (token->type == or_ttype && or_ttype != CPP_EOF
+	  && !brace_depth && !paren_depth && !square_depth)
+	return -1;
+
       switch (token->type)
 	{
 	case CPP_EOF:
@@ -3226,12 +3231,6 @@ cp_parser_skip_to_closing_parenthesis (cp_parser *parser,
 	    return 0;
 	  break;
 
-	case CPP_COMMA:
-	  if (recovering && or_comma && !brace_depth && !paren_depth
-	      && !square_depth)
-	    return -1;
-	  break;
-
 	case CPP_OPEN_PAREN:
 	  if (!brace_depth)
 	    ++paren_depth;
@@ -3255,6 +3254,22 @@ cp_parser_skip_to_closing_parenthesis (cp_parser *parser,
     }
 }
 
+/* Consume tokens up to, and including, the next non-nested closing `)'.
+   Returns 1 iff we found a closing `)'.  RECOVERING is true, if we
+   are doing error recovery. Returns -1 if OR_COMMA is true and we
+   found an unnested token of that type.  */
+
+static int
+cp_parser_skip_to_closing_parenthesis (cp_parser *parser,
+				       bool recovering,
+				       bool or_comma,
+				       bool consume_paren)
+{
+  cpp_ttype ttype = or_comma ? CPP_COMMA : CPP_EOF;
+  return cp_parser_skip_to_closing_parenthesis_1 (parser, recovering,
+						  ttype, consume_paren);
+}
+
 /* Consume tokens until we reach the end of the current statement.
    Normally, that will be just before consuming a `;'.  However, if a
    non-nested `}' comes first, then we stop before consuming that.  */
@@ -4260,6 +4275,186 @@ cp_parser_statement_expr (cp_parser *parser)
 
 /* Expressions [gram.expr] */
 
+/* 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_token *token)
+{
+  switch (token->type)
+    {
+    case CPP_PLUS: return PLUS_EXPR;
+    case CPP_MINUS: return MINUS_EXPR;
+    case CPP_MULT: return MULT_EXPR;
+    case CPP_DIV: return TRUNC_DIV_EXPR;
+    case CPP_MOD: return TRUNC_MOD_EXPR;
+    case CPP_XOR: return BIT_XOR_EXPR;
+    case CPP_AND: return BIT_AND_EXPR;
+    case CPP_OR: return BIT_IOR_EXPR;
+    case CPP_LSHIFT: return LSHIFT_EXPR;
+    case CPP_RSHIFT: return RSHIFT_EXPR;
+
+    case CPP_EQ: return -NOP_EXPR;
+    case CPP_PLUS_EQ: return -PLUS_EXPR;
+    case CPP_MINUS_EQ: return -MINUS_EXPR;
+    case CPP_MULT_EQ: return -MULT_EXPR;
+    case CPP_DIV_EQ: return -TRUNC_DIV_EXPR;
+    case CPP_MOD_EQ: return -TRUNC_MOD_EXPR;
+    case CPP_XOR_EQ: return -BIT_XOR_EXPR;
+    case CPP_AND_EQ: return -BIT_AND_EXPR;
+    case CPP_OR_EQ: return -BIT_IOR_EXPR;
+    case CPP_LSHIFT_EQ: return -LSHIFT_EXPR;
+    case CPP_RSHIFT_EQ: return -RSHIFT_EXPR;
+
+    case CPP_EQ_EQ: return EQ_EXPR;
+    case CPP_NOT_EQ: return NE_EXPR;
+    case CPP_LESS: return LT_EXPR;
+    case CPP_GREATER: return GT_EXPR;
+    case CPP_LESS_EQ: return LE_EXPR;
+    case CPP_GREATER_EQ: return GE_EXPR;
+
+    case CPP_AND_AND: return TRUTH_ANDIF_EXPR;
+    case CPP_OR_OR: return TRUTH_ORIF_EXPR;
+
+    case CPP_COMMA: return COMPOUND_EXPR;
+
+    case CPP_DOT_STAR: return DOTSTAR_EXPR;
+    case CPP_DEREF_STAR: return MEMBER_REF;
+
+    default: return ERROR_MARK;
+    }
+}
+
+/* If the next token is a suitable fold operator, consume it and return as
+   the function above.  */
+
+static int
+cp_parser_fold_operator (cp_parser *parser)
+{
+  cp_token* token = cp_lexer_peek_token (parser->lexer);
+  int code = cp_parser_fold_operator (token);
+  if (code != ERROR_MARK)
+    cp_lexer_consume_token (parser->lexer);
+  return code;
+}
+
+/* Returns true iff we're at the beginning of an N4191 fold-expression, after
+   the left parenthesis.  Rather than do tentative parsing, we scan the tokens
+   up to the matching right paren for an ellipsis next to a binary
+   operator.  */
+
+static bool
+cp_parser_fold_expr_p (cp_parser *parser)
+{
+  /* An ellipsis right after the left paren always indicates a
+     fold-expression.  */
+  if (cp_lexer_next_token_is (parser->lexer, CPP_ELLIPSIS))
+    {
+      /* But if there isn't a fold operator after the ellipsis,
+         give a different error.  */
+      cp_token *token = cp_lexer_peek_nth_token (parser->lexer, 2);
+      return (cp_parser_fold_operator (token) != ERROR_MARK);
+    }
+
+  /* Otherwise, look for an ellipsis.  */
+  cp_lexer_save_tokens (parser->lexer);
+  int ret = cp_parser_skip_to_closing_parenthesis_1 (parser, false,
+						     CPP_ELLIPSIS, false);
+  bool found = (ret == -1);
+  if (found)
+    {
+      /* We found an ellipsis, is the previous token an operator?  */
+      cp_token *token = cp_lexer_peek_token (parser->lexer);
+      --token;
+      if (cp_parser_fold_operator (token) == ERROR_MARK)
+	found = false;
+    }
+  cp_lexer_rollback_tokens (parser->lexer);
+  return found;
+}
+
+/* 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;
+
+  if (cxx_dialect < cxx1z && !in_system_header_at (input_location))
+    pedwarn (input_location, 0, "fold-expressions only available with "
+	     "-std=c++1z or -std=gnu++1z");
+
+  // 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 binary operator");
+          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 binary operator");
+      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))
+    {
+      cp_parser_error (parser, "mismatched operator in fold-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;
+  return finish_binary_fold_expr (expr1, expr2, op);
+}
+
 /* Parse a primary-expression.
 
    primary-expression:
@@ -4468,6 +4663,14 @@ cp_parser_primary_expression (cp_parser *parser,
 	  = parser->greater_than_is_operator_p;
 	parser->greater_than_is_operator_p = true;
 
+	// Handle a fold-expression.
+	if (cp_parser_fold_expr_p (parser))
+	  {
+	    tree fold = cp_parser_fold_expression (parser);
+	    cp_parser_require (parser, CPP_CLOSE_PAREN, RT_CLOSE_PAREN);
+	    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 05e6d83..10a12ea 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -10506,6 +10506,208 @@ gen_elem_of_pack_expansion_instantiation (tree pattern,
   return t;
 }
 
+/* When the unexpanded parameter pack in a fold expression expands to an empty
+   sequence, the value of the expression is as follows; the program is
+   ill-formed if the operator is not listed in this table.
+
+   *	1
+   +	0
+   &	-1
+   |	0
+   &&	true
+   ||	false
+   ,	void()  */
+
+tree
+expand_empty_fold (tree t, tsubst_flags_t complain)
+{
+  tree_code code = (tree_code)TREE_INT_CST_LOW (TREE_OPERAND (t, 0));
+  if (!FOLD_EXPR_MODIFY_P (t))
+    switch (code)
+      {
+      case MULT_EXPR:
+	return integer_one_node;
+      case PLUS_EXPR:
+	return integer_zero_node;
+      case BIT_AND_EXPR:
+	return integer_minus_one_node;
+      case BIT_IOR_EXPR:
+	return integer_zero_node;
+      case TRUTH_ANDIF_EXPR:
+	return boolean_true_node;
+      case TRUTH_ORIF_EXPR:
+	return boolean_false_node;
+      case COMPOUND_EXPR:
+	return void_node;
+      default:
+	break;
+      }
+
+  if (complain & tf_error)
+    error_at (location_of (t),
+	      "fold of empty expansion over %O", code);
+  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;
+}
+
+/* Substitute 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
@@ -14050,6 +14252,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);
@@ -22052,6 +22263,13 @@ type_dependent_expression_p (tree expression)
       || TREE_CODE (expression) == WILDCARD_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 7215dc6..f5bb0c1 100644
--- a/gcc/cp/semantics.c
+++ b/gcc/cp/semantics.c
@@ -7763,4 +7763,73 @@ 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 (!uses_parameter_packs (expr))
+    {
+      error_at (location_of (expr), "operand of fold expression has no "
+		"unexpanded parameter packs");
+      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 by 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.
+  bool pack1 = uses_parameter_packs (expr1);
+  bool pack2 = uses_parameter_packs (expr2);
+  if (pack1 && !pack2)
+    return finish_binary_fold_expr (expr1, expr2, op, BINARY_RIGHT_FOLD_EXPR);
+  else if (pack2 && !pack1)
+    return finish_binary_fold_expr (expr2, expr1, op, BINARY_LEFT_FOLD_EXPR);
+  else
+    {
+      if (pack1)
+        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 0000000..3c33651
--- /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 0000000..e42a39d
--- /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 0000000..307818f
--- /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(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();			// { dg-message "required from here" }
+  div();			// { dg-message "required from here" }
+  mod();			// { dg-message "required from here" }
+  lsh();			// { dg-message "required from here" }
+  rsh();			// { dg-message "required from here" }
+  assign();			// { dg-message "required from here" }
+  addi();			// { dg-message "required from here" }
+  subi();			// { dg-message "required from here" }
+  muli();			// { dg-message "required from here" }
+  divi();			// { dg-message "required from here" }
+  modi();			// { dg-message "required from here" }
+  bxor();			// { dg-message "required from here" }
+  bxori();			// { dg-message "required from here" }
+  bori();			// { dg-message "required from here" }
+  bandi();			// { dg-message "required from here" }
+  lshi();			// { dg-message "required from here" }
+  rshi();			// { dg-message "required from here" }
+  eq();				// { dg-message "required from here" }
+  ne();				// { dg-message "required from here" }
+  lt();				// { dg-message "required from here" }
+  gt();				// { dg-message "required from here" }
+  le();				// { dg-message "required from here" }
+  ge();				// { dg-message "required from here" }
+  dot_star();			// { dg-message "required from here" }
+  arrow_star();			// { dg-message "required from here" }
+}
diff --git a/gcc/testsuite/g++.dg/cpp1z/fold4.C b/gcc/testsuite/g++.dg/cpp1z/fold4.C
new file mode 100644
index 0000000..fbe6720
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1z/fold4.C
@@ -0,0 +1,10 @@
+// { dg-options -std=c++1z }
+
+template <class...T>
+constexpr auto f(T... t)
+{
+  return (... + *t);
+}
+
+const int i = 42, j = 24;
+static_assert (f(&i,&j) == i+j);
diff --git a/gcc/testsuite/g++.dg/cpp1z/fold5.C b/gcc/testsuite/g++.dg/cpp1z/fold5.C
new file mode 100644
index 0000000..0721419
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp1z/fold5.C
@@ -0,0 +1,8 @@
+// Test that we complain about fold-expressions in C++11 and C++14.
+// { dg-do compile { target c++11 } }
+
+template <class...T>
+constexpr int f(T... t)
+{
+  return (... + t);		// { dg-error "fold" }
+}
