Squashed 'third_party/marl/' changes from d29553a3730..f1c446ccdc0
f1c446ccdc0 Fix instances of bugprone-move-forwarding-reference
8719a54cbe0 Kokoro: Get tar directories around the right way!
3a21f30c54e Kokoro: Package build artifacts into a .tar
57da063f48f Kokoro: Fix line continuation in release.bat
ecaa2602da1 Kokoro: Rename release script names
787cf0686d2 Kokoro: Add release configs
3ce8637191a Kokoro: Test ucontext fibers on linux.
62f0a0f9e39 osfiber_ucontext: Fix memory leak & warning
20dc482b9a0 CMake: Add flag for ucontext fibers
3815666523e Kokoro: Fix define_artifacts.regex
f51513856b6 Kokoro: Add define_artifacts action
d2d77650ec1 CMake: Put marl-benchmarks in a named FOLDER
95e505a3071 Fix markdown lint warnings in README.md
71d86a2bc04 Kokoro: Add config for continuous + so builds
5f897319c18 Reduce scheduler fiber stack size for tests
bc65ef5ebe5 Scheduler: Make the fiber stack size configurable
b61e279881c Remove deprecated scheduler [gs]etters
1a28daf0d89 Add license checker config and kokoro presubmit
3448974c1b0 Add marl::DAG - a AoT declarative task graph
9e77dcdd5a4 Kokoro: Migrate to new Windows VM instance
ac517aa6784 Fix schedule() with function arguments
834e558a138 Add missing include to export.h
1e8acb5695e MSVC build fixes.
84f047c114c Migrate from VERSION to CHANGES.md
0a1012317ab Annotate all public API inlines with MARL_NO_EXPORT
3689793cb1d Only notify one fiber in ConditionVariable::notify_one()
596e172322d CMake: Use -fvisibility=hidden by default
1d51df92c71 Disable by default deprecated scheduler [gs]etters
45be9b24830 README: Add FreeBSD and iOS to the list of OSes
4d68ade048a Export DLL public symbols for building marl as dll
1efb1e70228 Kokoro: Add configs for Android
git-subtree-dir: third_party/marl
git-subtree-split: f1c446ccdc0c611d1aeec4a6266a77693ae48c92
diff --git a/src/dag_test.cpp b/src/dag_test.cpp
new file mode 100644
index 0000000..2596041
--- /dev/null
+++ b/src/dag_test.cpp
@@ -0,0 +1,175 @@
+// Copyright 2020 The Marl Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// https://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "marl/dag.h"
+
+#include "marl_test.h"
+
+using namespace testing;
+
+namespace {
+
+struct Data {
+ std::mutex mutex;
+ std::vector<std::string> order;
+
+ void push(std::string&& s) {
+ std::unique_lock<std::mutex> lock(mutex);
+ order.emplace_back(std::move(s));
+ }
+};
+
+template <typename T>
+std::vector<T> slice(const std::vector<T>& in, size_t from, size_t to) {
+ return {in.begin() + from, in.begin() + to};
+}
+
+} // namespace
+
+// [A] --> [B] --> [C] |
+TEST_P(WithBoundScheduler, DAGChainNoArg) {
+ marl::DAG<>::Builder builder;
+
+ Data data;
+ builder.root()
+ .then([&] { data.push("A"); })
+ .then([&] { data.push("B"); })
+ .then([&] { data.push("C"); });
+
+ auto dag = builder.build();
+ dag->run();
+
+ ASSERT_THAT(data.order, ElementsAre("A", "B", "C"));
+}
+
+// [A] --> [B] --> [C] |
+TEST_P(WithBoundScheduler, DAGChain) {
+ marl::DAG<Data&>::Builder builder;
+
+ builder.root()
+ .then([](Data& data) { data.push("A"); })
+ .then([](Data& data) { data.push("B"); })
+ .then([](Data& data) { data.push("C"); });
+
+ auto dag = builder.build();
+
+ Data data;
+ dag->run(data);
+
+ ASSERT_THAT(data.order, ElementsAre("A", "B", "C"));
+}
+
+// [A] --> [B] --> [C] |
+TEST_P(WithBoundScheduler, DAGRunRepeat) {
+ marl::DAG<Data&>::Builder builder;
+
+ builder.root()
+ .then([](Data& data) { data.push("A"); })
+ .then([](Data& data) { data.push("B"); })
+ .then([](Data& data) { data.push("C"); });
+
+ auto dag = builder.build();
+
+ Data dataA, dataB;
+ dag->run(dataA);
+ dag->run(dataB);
+ dag->run(dataA);
+
+ ASSERT_THAT(dataA.order, ElementsAre("A", "B", "C", "A", "B", "C"));
+ ASSERT_THAT(dataB.order, ElementsAre("A", "B", "C"));
+}
+
+// /--> [A] |
+// [root] --|--> [B] |
+// \--> [C] |
+TEST_P(WithBoundScheduler, DAGFanOutFromRoot) {
+ marl::DAG<Data&>::Builder builder;
+
+ auto root = builder.root();
+ root.then([](Data& data) { data.push("A"); });
+ root.then([](Data& data) { data.push("B"); });
+ root.then([](Data& data) { data.push("C"); });
+
+ auto dag = builder.build();
+
+ Data data;
+ dag->run(data);
+
+ ASSERT_THAT(data.order, UnorderedElementsAre("A", "B", "C"));
+}
+
+// /--> [A] |
+// [root] -->[N]--|--> [B] |
+// \--> [C] |
+TEST_P(WithBoundScheduler, DAGFanOutFromNonRoot) {
+ marl::DAG<Data&>::Builder builder;
+
+ auto root = builder.root();
+ auto node = root.then([](Data& data) { data.push("N"); });
+ node.then([](Data& data) { data.push("A"); });
+ node.then([](Data& data) { data.push("B"); });
+ node.then([](Data& data) { data.push("C"); });
+
+ auto dag = builder.build();
+
+ Data data;
+ dag->run(data);
+
+ ASSERT_THAT(data.order, UnorderedElementsAre("N", "A", "B", "C"));
+ ASSERT_EQ(data.order[0], "N");
+ ASSERT_THAT(slice(data.order, 1, 4), UnorderedElementsAre("A", "B", "C"));
+}
+
+// /--> [A0] --\ /--> [C0] --\ /--> [E0] --\ |
+// [root] --|--> [A1] --|-->[B]--|--> [C1] --|-->[D]--|--> [E1] --|-->[F] |
+// \--> [C2] --/ |--> [E2] --| |
+// \--> [E3] --/ |
+TEST_P(WithBoundScheduler, DAGFanOutFanIn) {
+ marl::DAG<Data&>::Builder builder;
+
+ auto root = builder.root();
+ auto a0 = root.then([](Data& data) { data.push("A0"); });
+ auto a1 = root.then([](Data& data) { data.push("A1"); });
+
+ auto b = builder.node([](Data& data) { data.push("B"); }, {a0, a1});
+
+ auto c0 = b.then([](Data& data) { data.push("C0"); });
+ auto c1 = b.then([](Data& data) { data.push("C1"); });
+ auto c2 = b.then([](Data& data) { data.push("C2"); });
+
+ auto d = builder.node([](Data& data) { data.push("D"); }, {c0, c1, c2});
+
+ auto e0 = d.then([](Data& data) { data.push("E0"); });
+ auto e1 = d.then([](Data& data) { data.push("E1"); });
+ auto e2 = d.then([](Data& data) { data.push("E2"); });
+ auto e3 = d.then([](Data& data) { data.push("E3"); });
+
+ builder.node([](Data& data) { data.push("F"); }, {e0, e1, e2, e3});
+
+ auto dag = builder.build();
+
+ Data data;
+ dag->run(data);
+
+ ASSERT_THAT(data.order,
+ UnorderedElementsAre("A0", "A1", "B", "C0", "C1", "C2", "D", "E0",
+ "E1", "E2", "E3", "F"));
+ ASSERT_THAT(slice(data.order, 0, 2), UnorderedElementsAre("A0", "A1"));
+ ASSERT_THAT(data.order[2], "B");
+ ASSERT_THAT(slice(data.order, 3, 6), UnorderedElementsAre("C0", "C1", "C2"));
+ ASSERT_THAT(data.order[6], "D");
+ ASSERT_THAT(slice(data.order, 7, 11),
+ UnorderedElementsAre("E0", "E1", "E2", "E3"));
+ ASSERT_THAT(data.order[11], "F");
+}
