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

login
register
mail settings
Submitter Rodrigo Rivas
Date Aug. 23, 2010, 2:22 p.m.
Message ID <AANLkTimYRJ1sj+55CncoqCu4XfhZehJ8YdVQY=EmRov-@mail.gmail.com>
Download mbox | patch
Permalink /patch/62487/
State New
Headers show

Comments

Rodrigo Rivas - Aug. 23, 2010, 2:22 p.m.
Hello.
I've been on vacations and disconnected for a few days, but here I am
again, with the range-for patch, round two.

> It would be shorter to array_type_nelts_top (TREE_TYPE (range_expr)) here.
Right, done.

> Also, a number of the lines in your patch go past 80 columns...
Yet getting used to these formatting rules, but I think I've corrected all.

> I believe this will get the wrong type if the begin/end functions have a
> return type of const Class; the iterator should have the cv-unqualified
> version.
Right! I've changed it to:
      iter_type = cv_unqualified (TREE_TYPE (begin_expr));


> You don't need to test for NULL before calling pop_scope anymore; I fixed it
> to accept a NULL argument recently.
I've just copied that from some code nearby... changed.

> I'm guessing this doesn't work with templates yet?  You don't have any
> template testcases.
With templates it crashes badly. I've been working on it without success (yet),
but I've added a temporary warning.
My problem was that the koenig lookup of the "begin" function does not
work if the
argument is a template dependent name. It would be nice to be able to do:
    begin = create_temporary_var (make_auto ());
But that does not work.
Anyway, that would be wrong because the behavior should be different
if the range
is an array, and we don't know that until instantiation.
I'd bet that I need to modify the "tsubst_expr()" function, but any
hint is welcome.

Thank you for your comments!
Rodrigo.
Jason Merrill - Aug. 24, 2010, 5:56 a.m.
On 08/23/2010 07:22 AM, Rodrigo Rivas wrote:
> With templates it crashes badly. I've been working on it without success (yet),
> but I've added a temporary warning.
> My problem was that the koenig lookup of the "begin" function does not
> work if the argument is a template dependent name. It would be nice to be able to do:
>      begin = create_temporary_var (make_auto ());
> But that does not work.
> Anyway, that would be wrong because the behavior should be different
> if the range is an array, and we don't know that until instantiation.
> I'd bet that I need to modify the "tsubst_expr()" function, but any
> hint is welcome.

Right.  In a template, rather than call cp_finish_range_based_for, you 
should just build up a RANGE_FOR_STMT with the decl and expr as 
operands; then in tsubst_expr you handle RANGE_FOR_STMT by substituting 
the template arguments into those operands as appropriate and calling 
cp_finish_range_based_for then.

You probably also want to refactor the code a bit so that for a 
range-based for you don't pass the FOR_STMT into 
cp_finish_range_based_for, you call begin_for_stmt inside that function.

Jason

Patch

Index: ../gcc/cp/pt.c
===================================================================
--- ../gcc/cp/pt.c	(revision 163449)
+++ ../gcc/cp/pt.c	(working copy)
@@ -12523,7 +12523,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 163449)
+++ ../gcc/cp/semantics.c	(working copy)
@@ -1839,11 +1839,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;
@@ -1879,7 +1880,7 @@  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 163449)
+++ ../gcc/cp/parser.c	(working copy)
@@ -1825,6 +1825,10 @@  static tree cp_parser_iteration_statement
   (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
@@ -5167,7 +5171,7 @@  cp_parser_postfix_expression (cp_parser *parser, b
 			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
@@ -5191,7 +5195,7 @@  cp_parser_postfix_expression (cp_parser *parser, b
 			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);
 		      }
 		  }
 	      }
@@ -8576,6 +8580,192 @@  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);
+  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 (dependent_type_p (TREE_TYPE (range_expr)))
+    {
+      warning (0, "range-based for not implemented with template arguments");
+    }
+  else if (TREE_CODE (TREE_TYPE (range_expr)) == ARRAY_TYPE)
+    {
+      /* If RANGE_EXPR is an array we will use pointer arithmetic */
+      iter_type = build_pointer_type (TREE_TYPE (TREE_TYPE (range_expr)));
+      begin_expr = range_expr;
+      end_expr = build_binary_op (input_location, PLUS_EXPR, range_expr,
+				  array_type_nelts_top (TREE_TYPE (range_expr)), 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 unqualified type of the __begin and __end temporaries should
+      * be the same as required by the multiple auto declaration */
+      iter_type = cv_unqualified (TREE_TYPE (begin_expr));
+      if (!same_type_p (iter_type, cv_unqualified (TREE_TYPE (end_expr))))
+      {
+	error ("inconsistent begin/end types in range-based for: %qT and %qT",
+	       TREE_TYPE (begin_expr), TREE_TYPE (end_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:
@@ -8657,28 +8847,39 @@  cp_parser_iteration_statement (cp_parser* 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 (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;
 
-	/* 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);
+	  /* 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);
 
@@ -13246,6 +13447,9 @@  cp_parser_namespace_definition (cp_parser* parser)
 
   if (cp_lexer_next_token_is_keyword (parser->lexer, RID_INLINE))
     {
+      if (cxx_dialect < cxx0x && !in_system_header)
+	pedwarn (input_location, OPT_pedantic, 
+		   "ISO C++98 does not allow inline namespaces");
       is_inline = true;
       cp_lexer_consume_token (parser->lexer);
     }
Index: ../gcc/cp/cp-tree.h
===================================================================
--- ../gcc/cp/cp-tree.h	(revision 163449)
+++ ../gcc/cp/cp-tree.h	(working copy)
@@ -5229,7 +5229,7 @@  extern tree finish_stmt_expr_expr		(tree, 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 163449)
+++ ../gcc/cp/name-lookup.c	(working copy)
@@ -4389,7 +4389,7 @@  lookup_function_nonclass (tree name, VEC(tree,gc)
     lookup_arg_dependent (name,
 			  lookup_name_real (name, 0, 1, block_p, 0,
 					    LOOKUP_COMPLAIN),
-			  args);
+			  args, false);
 }
 
 tree
@@ -5063,7 +5063,8 @@  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;
 
@@ -5086,6 +5087,8 @@  tree
      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 163449)
+++ ../gcc/cp/name-lookup.h	(working copy)
@@ -342,7 +342,7 @@  extern void do_toplevel_using_decl (tree, tree, tr
 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)
+    {
+    }
+}