From patchwork Fri Jul 23 12:13:14 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Rodrigo Rivas X-Patchwork-Id: 59776 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 4A466B6EFE for ; Fri, 23 Jul 2010 22:13:37 +1000 (EST) Received: (qmail 11807 invoked by alias); 23 Jul 2010 12:13:32 -0000 Received: (qmail 11723 invoked by uid 22791); 23 Jul 2010 12:13:26 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, TW_CX, TW_FN, TW_TM, T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: sourceware.org Received: from mail-wy0-f175.google.com (HELO mail-wy0-f175.google.com) (74.125.82.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 23 Jul 2010 12:13:18 +0000 Received: by wyb38 with SMTP id 38so146085wyb.20 for ; Fri, 23 Jul 2010 05:13:14 -0700 (PDT) MIME-Version: 1.0 Received: by 10.216.93.16 with SMTP id k16mr3410915wef.78.1279887194161; Fri, 23 Jul 2010 05:13:14 -0700 (PDT) Received: by 10.216.169.138 with HTTP; Fri, 23 Jul 2010 05:13:14 -0700 (PDT) Date: Fri, 23 Jul 2010 14:13:14 +0200 Message-ID: Subject: [C++0x patch] implement range-based for loops From: Rodrigo Rivas To: gcc-patches@gcc.gnu.org Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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) + { + } +}