Add GN split_list function. This function splits a list into N sub-lists. The plan is to use this in a template to automatically split static libraries. Add a new class ParseNodeValueAdapter which allows getting a list out of a function call without having to copy it. This is used in the new code and is used in a cleanup of rebase_foreach (both of which can take large input lists). Review-Url: https://codereview.chromium.org/2095043005 Cr-Original-Commit-Position: refs/heads/master@{#402555} Cr-Mirrored-From: https://chromium.googlesource.com/chromium/src Cr-Mirrored-Commit: c0ff88647c120f24203e50f7886f8e01a163c511
diff --git a/tools/gn/BUILD.gn b/tools/gn/BUILD.gn index e136127..a0801a1 100644 --- a/tools/gn/BUILD.gn +++ b/tools/gn/BUILD.gn
@@ -138,6 +138,8 @@ "operators.h", "output_file.cc", "output_file.h", + "parse_node_value_adapter.cc", + "parse_node_value_adapter.h", "parse_tree.cc", "parse_tree.h", "parser.cc",
diff --git a/tools/gn/function_foreach.cc b/tools/gn/function_foreach.cc index b74fc18..d8fe87e 100644 --- a/tools/gn/function_foreach.cc +++ b/tools/gn/function_foreach.cc
@@ -4,6 +4,7 @@ #include "tools/gn/err.h" #include "tools/gn/functions.h" +#include "tools/gn/parse_node_value_adapter.h" #include "tools/gn/parse_tree.h" #include "tools/gn/scope.h" @@ -63,27 +64,11 @@ } base::StringPiece loop_var(identifier->value().value()); - // Extract the list, avoid a copy if it's an identifier (common case). - Value value_storage_for_exec; // Backing for list_value when we need to exec. - const Value* list_value = nullptr; - const IdentifierNode* list_identifier = args_vector[1]->AsIdentifier(); - if (list_identifier) { - list_value = scope->GetValue(list_identifier->value().value(), true); - if (!list_value) { - *err = Err(args_vector[1].get(), "Undefined identifier."); - return Value(); - } - } else { - // Not an identifier, evaluate the node to get the result. - Scope list_exec_scope(scope); - value_storage_for_exec = args_vector[1]->Execute(scope, err); - if (err->has_error()) - return Value(); - list_value = &value_storage_for_exec; - } - if (!list_value->VerifyTypeIs(Value::LIST, err)) + // Extract the list to iterate over. + ParseNodeValueAdapter list_adapter; + if (!list_adapter.InitForType(scope, args_vector[1].get(), Value::LIST, err)) return Value(); - const std::vector<Value>& list = list_value->list_value(); + const std::vector<Value>& list = list_adapter.get().list_value(); // Block to execute. const BlockNode* block = function->block();
diff --git a/tools/gn/functions.cc b/tools/gn/functions.cc index 9e8646f..0a00c9c 100644 --- a/tools/gn/functions.cc +++ b/tools/gn/functions.cc
@@ -14,6 +14,7 @@ #include "tools/gn/config_values_generator.h" #include "tools/gn/err.h" #include "tools/gn/input_file.h" +#include "tools/gn/parse_node_value_adapter.h" #include "tools/gn/parse_tree.h" #include "tools/gn/pool.h" #include "tools/gn/scheduler.h" @@ -811,6 +812,90 @@ return Value(); } +// split_list ------------------------------------------------------------------ + +const char kSplitList[] = "split_list"; +const char kSplitList_HelpShort[] = + "split_list: Splits a list into N different sub-lists."; +const char kSplitList_Help[] = + "split_list: Splits a list into N different sub-lists.\n" + "\n" + " result = split_list(input, n)\n" + "\n" + " Given a list and a number N, splits the list into N sub-lists of\n" + " approximately equal size. The return value is a list of the sub-lists.\n" + " The result will always be a list of size N. If N is greater than the\n" + " number of elements in the input, it will be padded with empty lists.\n" + "\n" + " The expected use is to divide source files into smaller uniform\n" + " chunks.\n" + "\n" + "Example\n" + "\n" + " The code:\n" + " mylist = [1, 2, 3, 4, 5, 6]\n" + " print(split_list(mylist, 3))\n" + "\n" + " Will print:\n" + " [[1, 2], [3, 4], [5, 6]\n"; +Value RunSplitList(Scope* scope, + const FunctionCallNode* function, + const ListNode* args_list, + Err* err) { + const auto& args_vector = args_list->contents(); + if (args_vector.size() != 2) { + *err = Err(function, "Wrong number of arguments to split_list().", + "Expecting exactly two."); + return Value(); + } + + ParseNodeValueAdapter list_adapter; + if (!list_adapter.InitForType(scope, args_vector[0].get(), Value::LIST, err)) + return Value(); + const std::vector<Value>& input = list_adapter.get().list_value(); + + ParseNodeValueAdapter count_adapter; + if (!count_adapter.InitForType(scope, args_vector[1].get(), Value::INTEGER, + err)) + return Value(); + int64_t count = count_adapter.get().int_value(); + if (count <= 0) { + *err = Err(function, "Requested result size is not positive."); + return Value(); + } + + Value result(function, Value::LIST); + result.list_value().resize(count); + + // Every result list gets at least this many items in it. + int64_t min_items_per_list = static_cast<int64_t>(input.size()) / count; + + // This many result lists get an extra item which is the remainder from above. + int64_t extra_items = static_cast<int64_t>(input.size()) % count; + + // Allocate all lists that have a remainder assigned to them (max items). + int64_t max_items_per_list = min_items_per_list + 1; + auto last_item_end = input.begin(); + for (int64_t i = 0; i < extra_items; i++) { + result.list_value()[i] = Value(function, Value::LIST); + + auto begin_add = last_item_end; + last_item_end += max_items_per_list; + result.list_value()[i].list_value().assign(begin_add, last_item_end); + } + + // Allocate all smaller items that don't have a remainder. + for (int64_t i = extra_items; i < count; i++) { + result.list_value()[i] = Value(function, Value::LIST); + + auto begin_add = last_item_end; + last_item_end += min_items_per_list; + result.list_value()[i].list_value().assign(begin_add, last_item_end); + } + + return result; +} + // ----------------------------------------------------------------------------- FunctionInfo::FunctionInfo() @@ -923,6 +1008,7 @@ INSERT_FUNCTION(SetDefaults, false) INSERT_FUNCTION(SetDefaultToolchain, false) INSERT_FUNCTION(SetSourcesAssignmentFilter, false) + INSERT_FUNCTION(SplitList, false) INSERT_FUNCTION(Template, false) INSERT_FUNCTION(Tool, false) INSERT_FUNCTION(Toolchain, false)
diff --git a/tools/gn/functions.h b/tools/gn/functions.h index aadc966..48e9302 100644 --- a/tools/gn/functions.h +++ b/tools/gn/functions.h
@@ -305,6 +305,14 @@ BlockNode* block, Err* err); +extern const char kSplitList[]; +extern const char kSplitList_HelpShort[]; +extern const char kSplitList_Help[]; +Value RunSplitList(Scope* scope, + const FunctionCallNode* function, + const ListNode* args_list, + Err* err); + extern const char kStaticLibrary[]; extern const char kStaticLibrary_HelpShort[]; extern const char kStaticLibrary_Help[];
diff --git a/tools/gn/functions_unittest.cc b/tools/gn/functions_unittest.cc index 2267071..c6681bf 100644 --- a/tools/gn/functions_unittest.cc +++ b/tools/gn/functions_unittest.cc
@@ -90,3 +90,39 @@ result = defined_with_scope.parsed()->Execute(setup.scope(), &err); EXPECT_TRUE(err.has_error()); } + +TEST(Functions, SplitList) { + TestWithScope setup; + + TestParseInput input( + // Empty input with varying result items. + "out1 = split_list([], 1)\n" + "out2 = split_list([], 3)\n" + "print(\"empty = $out1 $out2\")\n" + + // One item input. + "out3 = split_list([1], 1)\n" + "out4 = split_list([1], 2)\n" + "print(\"one = $out3 $out4\")\n" + + // Multiple items. + "out5 = split_list([1, 2, 3, 4, 5, 6, 7, 8, 9], 2)\n" + "print(\"many = $out5\")\n" + + // Rounding. + "out6 = split_list([1, 2, 3, 4, 5, 6], 4)\n" + "print(\"rounding = $out6\")\n" + ); + ASSERT_FALSE(input.has_error()); + + Err err; + input.parsed()->Execute(setup.scope(), &err); + ASSERT_FALSE(err.has_error()) << err.message(); + + EXPECT_EQ( + "empty = [[]] [[], [], []]\n" + "one = [[1]] [[1], []]\n" + "many = [[1, 2, 3, 4, 5], [6, 7, 8, 9]]\n" + "rounding = [[1, 2], [3, 4], [5], [6]]\n", + setup.print_output()); +}
diff --git a/tools/gn/gn.gyp b/tools/gn/gn.gyp index 352a332..a002323 100644 --- a/tools/gn/gn.gyp +++ b/tools/gn/gn.gyp
@@ -138,6 +138,8 @@ 'operators.h', 'output_file.cc', 'output_file.h', + 'parse_node_value_adapter.cc', + 'parse_node_value_adapter.h', 'parse_tree.cc', 'parse_tree.h', 'parser.cc',
diff --git a/tools/gn/parse_node_value_adapter.cc b/tools/gn/parse_node_value_adapter.cc new file mode 100644 index 0000000..82f6f79 --- /dev/null +++ b/tools/gn/parse_node_value_adapter.cc
@@ -0,0 +1,47 @@ +// Copyright 2016 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "tools/gn/parse_node_value_adapter.h" + +#include "tools/gn/parse_tree.h" +#include "tools/gn/scope.h" + +ParseNodeValueAdapter::ParseNodeValueAdapter() : ref_(nullptr) { +} + +ParseNodeValueAdapter::~ParseNodeValueAdapter() { +} + + +bool ParseNodeValueAdapter::Init(Scope* scope, + const ParseNode* node, + Err* err) { + const IdentifierNode* identifier = node->AsIdentifier(); + if (identifier) { + ref_ = scope->GetValue(identifier->value().value(), true); + if (!ref_) { + identifier->MakeErrorDescribing("Undefined identifier"); + return false; + } + return true; + } + + temporary_ = node->Execute(scope, err); + return !err->has_error(); +} + +bool ParseNodeValueAdapter::InitForType(Scope* scope, + const ParseNode* node, + Value::Type type, + Err* err) { + if (!Init(scope, node, err)) + return false; + if (get().VerifyTypeIs(type, err)) + return true; + + // Fix up the error range (see class comment in the header file) to be the + // identifier node rather than the original value. + *err = Err(node, err->message(), err->help_text()); + return false; +}
diff --git a/tools/gn/parse_node_value_adapter.h b/tools/gn/parse_node_value_adapter.h new file mode 100644 index 0000000..db34e24 --- /dev/null +++ b/tools/gn/parse_node_value_adapter.h
@@ -0,0 +1,55 @@ +// Copyright 2016 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef TOOLS_GN_PARSE_NODE_VALUE_ADAPTER_H_ +#define TOOLS_GN_PARSE_NODE_VALUE_ADAPTER_H_ + +#include "base/macros.h" +#include "tools/gn/value.h" + +class ParseNode; + +// Provides a means to convert a parse node to a value without causing a copy +// in the common case of an "Identifier" node. Normally to get a value from a +// parse node you have to call Execute(), and when an identifier is executed +// it just returns the current value of itself as a copy. But some variables +// are very large (lists of many strings for example). +// +// The reason you might not want to do this is that in the case of an +// identifier where the copy is optimized away, the origin will still be the +// original value. The result can be confusing because it will reference the +// original value rather than the place where the value was dereferenced, e.g. +// for a function call. The InitForType() function will verify type information +// and will fix up the origin so it's not confusing. +class ParseNodeValueAdapter { + public: + ParseNodeValueAdapter(); + ~ParseNodeValueAdapter(); + + const Value& get() { + if (ref_) + return *ref_; + return temporary_; + } + + // Initializes the adapter for the result of the given expression. Returns + // truen on success. + bool Init(Scope* scope, const ParseNode* node, Err* err); + + // Like Init() but additionally verifies that the type of the result matches. + bool InitForType(Scope* scope, + const ParseNode* node, + Value::Type type, + Err* err); + + private: + // Holds either a reference to an existing item, or a temporary as a copy. + // If ref is non-null, it's valid, otherwise the temporary is used. + const Value* ref_; + Value temporary_; + + DISALLOW_COPY_AND_ASSIGN(ParseNodeValueAdapter); +}; + +#endif // TOOLS_GN_PARSE_NODE_VALUE_ADAPTER_H_