[C++0x patch] implement range-based for loops

[Rodrigo Rivas <rodrigorivascosta at gmail dot com>]

Hello.

This patch implements the range-based for statements as defined in
[stmt.ranged]. A few testcases are also included.

In order for the range-based for loops to be fully useful the standard
library should add the std::begin() / std::end() from
[iterator.range].

This is my first gcc patch ever, so please don't be too harsh...

Regards.
Rodrigo.

ChangeLog

2010-07-23  Rodrigo Rivas

	* cp/parser.c (cp_parser_iteration_statement): Add support for
	range-based for statements.
	Add functions cp_parser_for_range() and cp_finish_range_based_for.
	* cp/semantics.c (perform_koenig_lookup): Add a parameter to
	automatically include 'std' as an associated namespace.
	* cp/name-lookup.c (lookup_arg_dependent): Ditto.

Index: gcc/cp/pt.c
===================================================================
--- gcc/cp/pt.c	(revision: 162417)
+++ gcc/cp/pt.c	(workcopy)
@@ -12515,7 +12515,7 @@ tsubst_copy_and_build (tree t,
 	       into a non-dependent call.  */
 	    && type_dependent_expression_p_push (t)
 	    && !any_type_dependent_arguments_p (call_args))
-	  function = perform_koenig_lookup (function, call_args);
+	  function = perform_koenig_lookup (function, call_args, false);

 	if (TREE_CODE (function) == IDENTIFIER_NODE)
 	  {
Index: gcc/cp/semantics.c
===================================================================
--- gcc/cp/semantics.c	(revision: 162417)
+++ gcc/cp/semantics.c	(workcopy)
@@ -1845,11 +1845,12 @@ empty_expr_stmt_p (tree expr_stmt)

 /* Perform Koenig lookup.  FN is the postfix-expression representing
    the function (or functions) to call; ARGS are the arguments to the
-   call.  Returns the functions to be considered by overload
-   resolution.  */
+   call; if INCLUDE_STD then the `std' namespace is automatically
+   considered an associated namespace (used in range-based for loops).
+   Returns the functions to be considered by overload resolution.  */

 tree
-perform_koenig_lookup (tree fn, VEC(tree,gc) *args)
+perform_koenig_lookup (tree fn, VEC(tree,gc) *args, bool include_std)
 {
   tree identifier = NULL_TREE;
   tree functions = NULL_TREE;
@@ -1885,7 +1886,7 @@ perform_koenig_lookup (tree fn, VEC(tree
   if (!any_type_dependent_arguments_p (args)
       && !any_dependent_template_arguments_p (tmpl_args))
     {
-      fn = lookup_arg_dependent (identifier, functions, args);
+      fn = lookup_arg_dependent (identifier, functions, args, include_std);
       if (!fn)
 	/* The unqualified name could not be resolved.  */
 	fn = unqualified_fn_lookup_error (identifier);
Index: gcc/cp/parser.c
===================================================================
--- gcc/cp/parser.c	(revision: 162417)
+++ gcc/cp/parser.c	(workcopy)
@@ -1785,6 +1785,10 @@ static tree cp_parser_iteration_statemen
   (cp_parser *);
 static void cp_parser_for_init_statement
   (cp_parser *);
+static bool cp_parser_for_range
+  (cp_parser *, tree *, tree *);
+static void cp_finish_range_based_for
+  (tree, tree, tree);
 static tree cp_parser_jump_statement
   (cp_parser *);
 static void cp_parser_declaration_statement
@@ -5127,7 +5131,7 @@ cp_parser_postfix_expression (cp_parser
 			koenig_p = true;
 			if (!any_type_dependent_arguments_p (args))
 			  postfix_expression
-			    = perform_koenig_lookup (postfix_expression, args);
+			    = perform_koenig_lookup (postfix_expression, args, false);
 		      }
 		    else
 		      postfix_expression
@@ -5151,7 +5155,7 @@ cp_parser_postfix_expression (cp_parser
 			koenig_p = true;
 			if (!any_type_dependent_arguments_p (args))
 			  postfix_expression
-			    = perform_koenig_lookup (postfix_expression, args);
+			    = perform_koenig_lookup (postfix_expression, args, false);
 		      }
 		  }
 	      }
@@ -8536,6 +8540,186 @@ cp_parser_condition (cp_parser* parser)
   return cp_parser_expression (parser, /*cast_p=*/false, NULL);
 }

+/* Tries to parse a range-based for:
+
+  range-based-for:
+    type-specifier-seq declarator : expression
+
+  If succesful, assigns to *DECL the DECLARATOR and to *EXPR the
+  expression. Note that the *DECL is returned unfinished, so
+  later it should call cp_finish_decl().
+
+  Returns TRUE iff a range-based for is parsed. */
+
+static bool
+cp_parser_for_range(cp_parser *parser, tree *decl, tree *expr)
+{
+  cp_decl_specifier_seq type_specifiers;
+  const char *saved_message;
+  cp_declarator *declarator;
+  tree attributes, pushed_scope;
+
+  cp_parser_parse_tentatively (parser);
+  /* New types are not allowed in the type-specifier-seq for a
+     range-based for loop.  */
+  saved_message = parser->type_definition_forbidden_message;
+  parser->type_definition_forbidden_message
+    = G_("types may not be defined in range-based for loops");
+  /* Parse the type-specifier-seq.  */
+  cp_parser_type_specifier_seq (parser, /*is_declaration==*/true,
+				/*is_trailing_return=*/false,
+				&type_specifiers);
+  /* Restore the saved message.  */
+  parser->type_definition_forbidden_message = saved_message;
+  /* If all is well, we might be looking at a declaration.  */
+  if (cp_parser_error_occurred (parser))
+  {
+    cp_parser_abort_tentative_parse (parser);
+    return false;
+  }
+  /* Parse the declarator.  */
+  declarator = cp_parser_declarator (parser, CP_PARSER_DECLARATOR_NAMED,
+          /*ctor_dtor_or_conv_p=*/NULL,
+          /*parenthesized_p=*/NULL,
+          /*member_p=*/false);
+  /* Parse the attributes.  */
+  attributes = cp_parser_attributes_opt (parser);
+  /* The next token should be `:'. */
+  if (cp_lexer_next_token_is_not (parser->lexer, CPP_COLON))
+      cp_parser_simulate_error (parser);
+
+  /* Check if it is a range-based for */
+  if (!cp_parser_parse_definitely (parser))
+      return false;
+
+  cp_parser_require (parser, CPP_COLON, RT_COLON);
+  *expr = cp_parser_expression (parser, /*cast_p=*/false, NULL);
+
+  /* Create the declaration.  */
+  *decl = start_decl (declarator, &type_specifiers,
+          /*initialized_p=*/SD_INITIALIZED,
+          attributes, /*prefix_attributes=*/NULL_TREE,
+          &pushed_scope);
+  if (pushed_scope) /* No scopes allowed here */
+      pop_scope(pushed_scope);
+  return true;
+}
+
+/* Builds a range-based for loop.
+   The parameters RANGE_DECL and RANGE_EXPR are as returned
+   from the cp_parser_for_range() function.
+
+      for (RANGE_DECL : RANGE_EXPR)
+  	BLOCK
+
+   should be built as:
+      {
+  	auto &&__range = RANGE_EXPR;
+  	for (auto __begin = BEGIN_EXPR, end = END_EXPR;
+  	      __begin != __end;
+  	      ++__begin)
+  	{
+  	    RANGE_DECL = *__begin;
+  	    BLOCK
+  	}
+      }
+   If RANGE_EXPR is an array:
+       BEGIN_EXPR = __range
+       END_EXPR = __range + countof(__range)
+   Else:
+  	BEGIN_EXPR = begin(__range)
+  	END_EXPR = end(__range);
+
+   When calling begin()/end() we must use argument dependent
+   lookup, but always considering 'std' as an associated namespace.
+*/
+static void
+cp_finish_range_based_for (tree statement, tree range_decl, tree range_expr)
+{
+  tree range_type, range_temp;
+  tree begin, end;
+  tree iter_type, begin_expr, end_expr;
+  tree condition, expression;
+
+  /* Find out the type deduced by the declaration `auto &&__range =
range_expr' */
+  range_type = cp_build_reference_type (make_auto (), true);
+  range_type = do_auto_deduction (range_type, range_expr,
type_uses_auto (range_type));
+
+  /* Create the __range variable */
+  range_temp = create_temporary_var (range_type);
+  add_decl_expr (range_temp);
+  finish_expr_stmt (cp_build_modify_expr (range_temp, INIT_EXPR, range_expr,
+	tf_warning_or_error)); /* tf_none */
+
+  if (TREE_CODE (TREE_TYPE (range_expr)) == ARRAY_TYPE)
+  {
+    /* If RANGE_EXPR is an array we will use pointer arithmetic */
+    tree max = TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (range_expr)));
+
+    iter_type = build_pointer_type (TREE_TYPE (TREE_TYPE (range_expr)));
+    begin_expr = range_expr;
+    end_expr = build_binary_op (UNKNOWN_LOCATION, PLUS_EXPR, range_expr,
+		build_binary_op (UNKNOWN_LOCATION, PLUS_EXPR, max, build_one_cst
(integer_type_node), 0), 0);
+  }
+  else
+  {
+    /* If it is not an array, we must call begin(__range)/end__range() */
+    VEC(tree,gc) *vec;
+
+    begin_expr = get_identifier ("begin");
+    vec = make_tree_vector ();
+    VEC_safe_push (tree, gc, vec, range_expr);
+    begin_expr = perform_koenig_lookup (begin_expr, vec, /*include_std=*/true);
+    begin_expr = finish_call_expr (begin_expr, &vec, false, true,
tf_warning_or_error);
+    release_tree_vector (vec);
+
+    end_expr = get_identifier ("end");
+    vec = make_tree_vector ();
+    VEC_safe_push (tree, gc, vec, range_expr);
+    end_expr = perform_koenig_lookup (end_expr, vec, /*include_std=*/true);
+    end_expr = finish_call_expr (end_expr, &vec, false, true,
tf_warning_or_error);
+    release_tree_vector (vec);
+
+    /* The type of the __begin and __end temporaries should be the same
+     * as required by the multiple auto declaration */
+    if (!same_type_p (TREE_TYPE (begin_expr), TREE_TYPE (end_expr)))
+    {
+      error ("inconsistent begin/end types in range-based for: %qT and %qT",
+	  TREE_TYPE (begin_expr), TREE_TYPE (end_expr));
+    }
+    iter_type = TREE_TYPE (begin_expr);
+  }
+
+  /* The new for initialization statement */
+  begin = create_temporary_var (iter_type);
+  add_decl_expr (begin);
+  finish_expr_stmt (cp_build_modify_expr (begin, INIT_EXPR, begin_expr,
+	tf_warning_or_error));
+  end = create_temporary_var (iter_type);
+  add_decl_expr (end);
+  finish_expr_stmt (cp_build_modify_expr (end, INIT_EXPR, end_expr,
+	tf_warning_or_error));
+  finish_for_init_stmt (statement);
+
+/* The new for condition */
+  condition = build_x_binary_op (NE_EXPR,
+      begin, ERROR_MARK,
+      end, ERROR_MARK,
+      NULL, tf_warning_or_error);
+  finish_for_cond (condition, statement);
+
+  /* The new increment expression */
+  expression = finish_unary_op_expr (PREINCREMENT_EXPR, begin);
+  finish_for_expr (expression, statement);
+
+  /* The declaration is initialized with *__begin inside the loop body */
+  cp_finish_decl (range_decl,
+      build_x_indirect_ref (begin, RO_NULL, tf_warning_or_error),
+      /*is_constant_init*/false, NULL_TREE,
+      LOOKUP_ONLYCONVERTING);
+}
+
+
 /* Parse an iteration-statement.

    iteration-statement:
@@ -8617,30 +8801,40 @@ cp_parser_iteration_statement (cp_parser

     case RID_FOR:
       {
-	tree condition = NULL_TREE;
-	tree expression = NULL_TREE;
+        tree range_decl, range_expr;

 	/* Begin the for-statement.  */
 	statement = begin_for_stmt ();
 	/* Look for the `('.  */
 	cp_parser_require (parser, CPP_OPEN_PAREN, RT_OPEN_PAREN);
-	/* Parse the initialization.  */
-	cp_parser_for_init_statement (parser);
-	finish_for_init_stmt (statement);
-
-	/* If there's a condition, process it.  */
-	if (cp_lexer_next_token_is_not (parser->lexer, CPP_SEMICOLON))
-	  condition = cp_parser_condition (parser);
-	finish_for_cond (condition, statement);
-	/* Look for the `;'.  */
-	cp_parser_require (parser, CPP_SEMICOLON, RT_SEMICOLON);

-	/* If there's an expression, process it.  */
-	if (cp_lexer_next_token_is_not (parser->lexer, CPP_CLOSE_PAREN))
-	  expression = cp_parser_expression (parser, /*cast_p=*/false, NULL);
-	finish_for_expr (expression, statement);
-	/* Look for the `)'.  */
-	cp_parser_require (parser, CPP_CLOSE_PAREN, RT_CLOSE_PAREN);
+	if (cxx_dialect == cxx0x && cp_parser_for_range (parser,
&range_decl, &range_expr))
+	{
+	  cp_finish_range_based_for (statement, range_decl, range_expr);
+	}
+	else
+	{
+	  tree condition = NULL_TREE;
+	  tree expression = NULL_TREE;
+
+	  /* Parse the initialization.  */
+	  cp_parser_for_init_statement (parser);
+	  finish_for_init_stmt (statement);
+
+	  /* If there's a condition, process it.  */
+	  if (cp_lexer_next_token_is_not (parser->lexer, CPP_SEMICOLON))
+	    condition = cp_parser_condition (parser);
+	  finish_for_cond (condition, statement);
+	  /* Look for the `;'.  */
+	  cp_parser_require (parser, CPP_SEMICOLON, RT_SEMICOLON);
+
+	  /* If there's an expression, process it.  */
+	  if (cp_lexer_next_token_is_not (parser->lexer, CPP_CLOSE_PAREN))
+	    expression = cp_parser_expression (parser, /*cast_p=*/false, NULL);
+	  finish_for_expr (expression, statement);
+	}
+        /* Look for the `)'.  */
+        cp_parser_require (parser, CPP_CLOSE_PAREN, RT_CLOSE_PAREN);

 	/* Parse the body of the for-statement.  */
 	parser->in_statement = IN_ITERATION_STMT;
Index: gcc/cp/cp-tree.h
===================================================================
--- gcc/cp/cp-tree.h	(revision: 162417)
+++ gcc/cp/cp-tree.h	(workcopy)
@@ -5228,7 +5228,7 @@ extern tree finish_stmt_expr_expr		(tree
 extern tree finish_stmt_expr			(tree, bool);
 extern tree stmt_expr_value_expr		(tree);
 bool empty_expr_stmt_p				(tree);
-extern tree perform_koenig_lookup		(tree, VEC(tree,gc) *);
+extern tree perform_koenig_lookup		(tree, VEC(tree,gc) *, bool);
 extern tree finish_call_expr			(tree, VEC(tree,gc) **, bool,
 						 bool, tsubst_flags_t);
 extern tree finish_increment_expr		(tree, enum tree_code);
Index: gcc/cp/name-lookup.c
===================================================================
--- gcc/cp/name-lookup.c	(revision: 162417)
+++ gcc/cp/name-lookup.c	(workcopy)
@@ -4395,7 +4395,7 @@ lookup_function_nonclass (tree name, VEC
     lookup_arg_dependent (name,
 			  lookup_name_real (name, 0, 1, block_p, 0,
 					    LOOKUP_COMPLAIN),
-			  args);
+			  args, false);
 }

 tree
@@ -5056,7 +5056,7 @@ arg_assoc (struct arg_lookup *k, tree n)
    are the functions found in normal lookup.  */

 tree
-lookup_arg_dependent (tree name, tree fns, VEC(tree,gc) *args)
+lookup_arg_dependent (tree name, tree fns, VEC(tree,gc) *args, bool
include_std)
 {
   struct arg_lookup k;

@@ -5079,6 +5079,8 @@ lookup_arg_dependent (tree name, tree fn
      picking up later definitions) in the second stage. */
   k.namespaces = make_tree_vector ();

+  if (include_std)
+      arg_assoc_namespace(&k, std_node);
   arg_assoc_args_vec (&k, args);

   fns = k.functions;
Index: gcc/cp/name-lookup.h
===================================================================
--- gcc/cp/name-lookup.h	(revision: 162417)
+++ gcc/cp/name-lookup.h	(workcopy)
@@ -334,7 +334,7 @@ extern void do_toplevel_using_decl (tree
 extern void do_local_using_decl (tree, tree, tree);
 extern tree do_class_using_decl (tree, tree);
 extern void do_using_directive (tree);
-extern tree lookup_arg_dependent (tree, tree, VEC(tree,gc) *);
+extern tree lookup_arg_dependent (tree, tree, VEC(tree,gc) *, bool);
 extern bool is_associated_namespace (tree, tree);
 extern void parse_using_directive (tree, tree);
 extern tree innermost_non_namespace_value (tree);
Index: gcc/testsuite/g++.dg/cpp0x/range-for1.C
===================================================================
--- gcc/testsuite/g++.dg/cpp0x/range-for1.C	(revision: 0)
+++ gcc/testsuite/g++.dg/cpp0x/range-for1.C	(revision: 0)
@@ -0,0 +1,17 @@
+// Test for range-based for loop
+// Test the loop with an array
+
+// { dg-do run }
+// { dg-options "-std=c++0x" }
+
+extern "C" void abort();
+
+int main()
+{
+    int a[] = {1,2,3,4};
+    int sum = 0;
+    for (int x : a)
+        sum += x;
+    if (sum != 10)
+        abort();
+}
Index: gcc/testsuite/g++.dg/cpp0x/range-for2.C
===================================================================
--- gcc/testsuite/g++.dg/cpp0x/range-for2.C	(revision: 0)
+++ gcc/testsuite/g++.dg/cpp0x/range-for2.C	(revision: 0)
@@ -0,0 +1,41 @@
+// Test for range-based for loop
+// Test the loop with a custom iterator
+// with begin/end in an associated namespace
+
+// { dg-do compile }
+// { dg-options "-std=c++0x" }
+
+struct iterator
+{
+    int x;
+    iterator(int v) :x(v) {}
+    iterator &operator ++() { ++x; return *this; }
+    int operator *() { return x; }
+    bool operator != (const iterator &o) { return x != o.x; }
+};
+
+namespace foo
+{
+    struct container
+    {
+        int min, max;
+        container(int a, int b) :min(a), max(b) {}
+    };
+
+    iterator begin(container &c)
+    {
+        return iterator(c.min);
+    }
+
+    iterator end(container &c)
+    {
+        return iterator(c.max + 1);
+    }
+}
+
+int main()
+{
+    foo::container c(1,4);
+    for (iterator it : c)
+        ;
+}
Index: gcc/testsuite/g++.dg/cpp0x/range-for3.C
===================================================================
--- gcc/testsuite/g++.dg/cpp0x/range-for3.C	(revision: 0)
+++ gcc/testsuite/g++.dg/cpp0x/range-for3.C	(revision: 0)
@@ -0,0 +1,42 @@
+// Test for range-based for loop
+// Test the loop with a custom iterator
+// with begin/end in std
+
+// { dg-do compile }
+// { dg-options "-std=c++0x" }
+
+struct iterator
+{
+    int x;
+    iterator(int v) :x(v) {}
+    iterator &operator ++() { ++x; return *this; }
+    int operator *() { return x; }
+    bool operator != (const iterator &o) { return x != o.x; }
+};
+
+struct container
+{
+    int min, max;
+    container(int a, int b) :min(a), max(b) {}
+};
+
+namespace std
+{
+    iterator begin(container &c)
+    {
+        return iterator(c.min);
+    }
+
+    iterator end(container &c)
+    {
+        return iterator(c.max + 1);
+    }
+}
+
+int main()
+{
+    container c(1,4);
+    for (iterator it : c)
+    {
+    }
+}