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_
