tp: order tree rows child first Folding up a tree needs every child before its parent, and needs the order to be a depth first post-order so the fold can carry a stack of the current path instead of an array indexed by node. No source should have that order imposed on it. TreeChildFirst is a breaker, because the first row out has to be a leaf and no row is known to be a leaf until the input ends. Rows which arrived child first come back as they arrived, rows which arrived parent first are reversed, and rows in neither order are sorted. Which of the three happens is found out from the rows, so the planner only has to leave the breaker out when it knows the input is already child first. The breaker reports a node which is its own parent, a node with two rows, a parent which is never a row, and a cycle.
diff --git a/Android.bp b/Android.bp index 6e554a5..e2ac7c7 100644 --- a/Android.bp +++ b/Android.bp
@@ -17714,6 +17714,7 @@ "src/trace_processor/core/exec/row_cursor.cc", "src/trace_processor/core/exec/row_store.cc", "src/trace_processor/core/exec/tree_number_nodes.cc", + "src/trace_processor/core/exec/tree_order.cc", ], } @@ -17732,6 +17733,7 @@ "src/trace_processor/core/exec/row_batch_unittest.cc", "src/trace_processor/core/exec/row_store_unittest.cc", "src/trace_processor/core/exec/tree_number_nodes_unittest.cc", + "src/trace_processor/core/exec/tree_order_unittest.cc", "src/trace_processor/core/exec/variant_unittest.cc", ], }
diff --git a/src/trace_processor/core/exec/BUILD.gn b/src/trace_processor/core/exec/BUILD.gn index 6f4b8ae..a08ef54 100644 --- a/src/trace_processor/core/exec/BUILD.gn +++ b/src/trace_processor/core/exec/BUILD.gn
@@ -37,6 +37,8 @@ "row_store.h", "tree_number_nodes.cc", "tree_number_nodes.h", + "tree_order.cc", + "tree_order.h", "variant.h", ] deps = [ @@ -64,6 +66,7 @@ "row_batch_unittest.cc", "row_store_unittest.cc", "tree_number_nodes_unittest.cc", + "tree_order_unittest.cc", "variant_unittest.cc", ] deps = [
diff --git a/src/trace_processor/core/exec/tree_order.cc b/src/trace_processor/core/exec/tree_order.cc new file mode 100644 index 0000000..a9ae8af --- /dev/null +++ b/src/trace_processor/core/exec/tree_order.cc
@@ -0,0 +1,243 @@ +/* + * Copyright (C) 2026 The Android Open Source Project + * + * 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 + * + * http://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 "src/trace_processor/core/exec/tree_order.h" + +#include <algorithm> +#include <cstdint> +#include <memory> + +#include "perfetto/base/status.h" +#include "src/trace_processor/core/common/storage_types.h" +#include "src/trace_processor/core/exec/column_view.h" +#include "src/trace_processor/core/exec/operator.h" +#include "src/trace_processor/core/exec/row_batch.h" +#include "src/trace_processor/core/exec/row_store.h" +#include "src/trace_processor/core/exec/tree_number_nodes.h" +#include "src/trace_processor/core/util/bit_vector.h" +#include "src/trace_processor/core/util/flex_vector.h" +#include "src/trace_processor/core/util/span.h" + +namespace perfetto::trace_processor::core::exec { +namespace { + +constexpr char kChildFirst[] = "TREE ORDER CHILD FIRST"; + +bool IsNodeColumn(const ColumnView& column) { + return column.kind() == ColumnView::Kind::kFlat && column.type().Is<Uint32>(); +} + +// Points `node` and `parent` at the batch's node number columns, or fails if +// that is not what they are. +base::Status NodeColumns(const RowBatch& batch, + uint32_t node_column, + uint32_t parent_column, + const char* name, + const ColumnView** node, + const ColumnView** parent) { + *node = &batch.column(node_column); + *parent = &batch.column(parent_column); + if (!IsNodeColumn(**node) || !IsNodeColumn(**parent)) { + return base::ErrStatus( + "%s: expected node numbers, which TREE NUMBER NODES makes", name); + } + return base::OkStatus(); +} + +} // namespace + +TreeChildFirst::TreeChildFirst(const Source& input, + uint32_t node_column, + uint32_t parent_column) + : Breaker(input), + node_column_(node_column), + parent_column_(parent_column) {} + +TreeChildFirst::~TreeChildFirst() = default; +TreeChildFirst::State::~State() = default; + +std::unique_ptr<Breaker::State> TreeChildFirst::CreateState() const { + return std::make_unique<State>(); +} + +bool TreeChildFirst::Consume(const RowBatch& in, Breaker::State& state) const { + State& s = state.Cast<State>(); + uint32_t count = in.size(); + if (count == 0) { + return true; + } + const ColumnView* node_column; + const ColumnView* parent_column; + s.status = NodeColumns(in, node_column_, parent_column_, kChildFirst, + &node_column, &parent_column); + if (!s.status.ok()) { + return false; + } + + auto base = static_cast<uint32_t>(s.nodes.size()); + for (uint32_t i = 0; i < count; ++i) { + uint32_t node = node_column->Value<uint32_t>(i); + uint32_t parent = parent_column->Value<uint32_t>(i); + s.nodes.push_back(node); + s.parents.push_back(parent); + if (node == parent) { + s.status = base::ErrStatus("%s: a node is its own parent", kChildFirst); + return false; + } + s.nodes_seen = std::max(s.nodes_seen, node + 1); + if (parent != kNoNode) { + s.nodes_seen = std::max(s.nodes_seen, parent + 1); + } + if (s.has_row.size() < s.nodes_seen) { + // Grown geometrically, as resize allocates exactly what it is asked for. + auto size = std::max<uint64_t>(s.nodes_seen, s.has_row.size() * 2); + s.has_row.resize(size); + s.row_of_node.resize(size); + } + if (s.has_row.is_set(node)) { + s.status = base::ErrStatus("%s: more than one row has the same node", + kChildFirst); + return false; + } + if (parent != kNoNode) { + // Having already seen the parent rules out child first; not having + // seen it rules out parent first. + if (s.has_row.is_set(parent)) { + s.child_first = false; + } else { + s.parent_first = false; + } + } + s.has_row.set(node); + s.row_of_node[node] = base + i; + } + s.status = s.rows.Append(in); + return s.status.ok(); +} + +bool TreeChildFirst::Sort(State& s) const { + uint32_t nodes = s.nodes_seen; + uint32_t rows = s.rows.size(); + // The children of every node, laid out end to end: a tree has as many + // entries as it has non-roots. + auto begin = FlexVector<uint32_t>::CreateFilled(nodes + 1, 0); + for (uint32_t row = 0; row < rows; ++row) { + if (s.parents[row] != kNoNode) { + ++begin[s.parents[row] + 1]; + } + } + for (uint32_t node = 0; node < nodes; ++node) { + begin[node + 1] += begin[node]; + } + // Filling walks `begin` forward and then restores it, saving a second + // array. + auto children = FlexVector<uint32_t>::CreateWithSize(begin[nodes]); + for (uint32_t row = 0; row < rows; ++row) { + if (s.parents[row] != kNoNode) { + children[begin[s.parents[row]]++] = s.nodes[row]; + } + } + for (uint32_t node = nodes; node-- > 0;) { + begin[node + 1] = begin[node]; + } + begin[0] = 0; + + // A node is only reached through its parent, so this comes out parent + // first; reversing it makes the post-order wanted. + s.order.clear(); + s.order.reserve(rows); + FlexVector<uint32_t> pending; + for (uint32_t row = 0; row < rows; ++row) { + if (s.parents[row] == kNoNode) { + pending.push_back(s.nodes[row]); + } + } + while (!pending.empty()) { + uint32_t node = pending.back(); + pending.pop_back(); + s.order.push_back(s.row_of_node[node]); + for (uint32_t i = begin[node]; i < begin[node + 1]; ++i) { + pending.push_back(children[i]); + } + } + if (s.order.size() != rows) { + s.status = base::ErrStatus( + "%s: the rows are not a tree, because %u of them are in a cycle", + kChildFirst, rows - static_cast<uint32_t>(s.order.size())); + s.order.clear(); + return false; + } + std::reverse(s.order.begin(), s.order.end()); + return true; +} + +bool TreeChildFirst::Finish(Breaker::State& state) const { + State& s = state.Cast<State>(); + if (s.has_row.CountSetBits() != s.nodes_seen) { + s.status = base::ErrStatus( + "%s: a row names a parent which is not itself a row in the input", + kChildFirst); + return false; + } + if (s.child_first) { + // Already in the requested order, so no reordering is needed. + s.order.clear(); + return true; + } + if (s.parent_first) { + // Reversing is all it takes to turn one tree order into the other. + uint32_t rows = s.rows.size(); + s.order.resize(rows); + for (uint32_t row = 0; row < rows; ++row) { + s.order[row] = rows - 1 - row; + } + return true; + } + return Sort(s); +} + +bool TreeChildFirst::Serve(RowBatch& out, Breaker::State& state) const { + State& s = state.Cast<State>(); + if (s.emitted == s.rows.size()) { + return false; + } + uint32_t count = std::min(kMaxBatchRows, s.rows.size() - s.emitted); + if (s.order.empty()) { + // A run never spans two chunks, so the store says how much it served. + count = s.rows.View(&out, s.emitted, count); + } else { + const uint32_t* begin = s.order.data() + s.emitted; + s.rows.View(&out, Span<const uint32_t>(begin, begin + count)); + } + s.emitted += count; + return true; +} + +void TreeChildFirst::Reset(Breaker::State& state) const { + State& s = state.Cast<State>(); + s.has_row.clear(); + s.nodes_seen = 0; + s.parent_first = true; + s.child_first = true; + s.nodes.clear(); + s.parents.clear(); + s.row_of_node.clear(); + s.rows.Clear(); + s.order.clear(); + s.emitted = 0; +} + +} // namespace perfetto::trace_processor::core::exec
diff --git a/src/trace_processor/core/exec/tree_order.h b/src/trace_processor/core/exec/tree_order.h new file mode 100644 index 0000000..ca2ed97 --- /dev/null +++ b/src/trace_processor/core/exec/tree_order.h
@@ -0,0 +1,90 @@ +/* + * Copyright (C) 2026 The Android Open Source Project + * + * 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 + * + * http://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. + */ + +#ifndef SRC_TRACE_PROCESSOR_CORE_EXEC_TREE_ORDER_H_ +#define SRC_TRACE_PROCESSOR_CORE_EXEC_TREE_ORDER_H_ + +#include <cstdint> +#include <memory> + +#include "perfetto/base/status.h" +#include "src/trace_processor/core/exec/operator.h" +#include "src/trace_processor/core/exec/row_batch.h" +#include "src/trace_processor/core/exec/row_store.h" +#include "src/trace_processor/core/util/bit_vector.h" +#include "src/trace_processor/core/util/flex_vector.h" + +namespace perfetto::trace_processor::core::exec { + +// TREE ORDER CHILD FIRST: puts tree rows into a depth first post-order, so +// every child precedes its parent. A fold up a tree runs over this order. +// +// A breaker: the first row out has to be a leaf, and no row is known to be a +// leaf until the input ends. Rows which arrived child first come back as they +// arrived; rows which arrived parent first are reversed; rows in neither +// order are sorted. Which of the three happens is found out from the rows, +// so the planner only needs to leave this out when it knows the input is +// already child first. +// +// The input columns are node numbers, which TreeNumberNodes produces. No +// column is added. +class TreeChildFirst : public Breaker { + public: + TreeChildFirst(const Source& input, + uint32_t node_column, + uint32_t parent_column); + TreeChildFirst(Source&&, uint32_t, uint32_t) = delete; + ~TreeChildFirst() override; + + bool Consume(const RowBatch& in, Breaker::State& state) const override; + bool Finish(Breaker::State& state) const override; + + private: + struct State : Breaker::State { + ~State() override; + + // By node number. + BitVector has_row; + uint32_t nodes_seen = 0; + // Which orders the rows so far are still consistent with. + bool parent_first = true; + bool child_first = true; + + // The node and parent of each row in order of arrival, and each node's + // row: what a sort needs. + FlexVector<uint32_t> nodes; + FlexVector<uint32_t> parents; + FlexVector<uint32_t> row_of_node; + + RowStore rows; + // The order to emit the rows in. Empty means in arrival order. + FlexVector<uint32_t> order; + uint32_t emitted = 0; + }; + + std::unique_ptr<Breaker::State> CreateState() const override; + bool Serve(RowBatch& out, Breaker::State& state) const override; + void Reset(Breaker::State& state) const override; + + bool Sort(State&) const; + + uint32_t node_column_; + uint32_t parent_column_; +}; + +} // namespace perfetto::trace_processor::core::exec + +#endif // SRC_TRACE_PROCESSOR_CORE_EXEC_TREE_ORDER_H_
diff --git a/src/trace_processor/core/exec/tree_order_unittest.cc b/src/trace_processor/core/exec/tree_order_unittest.cc new file mode 100644 index 0000000..1b0b23a --- /dev/null +++ b/src/trace_processor/core/exec/tree_order_unittest.cc
@@ -0,0 +1,429 @@ +/* + * Copyright (C) 2026 The Android Open Source Project + * + * 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 + * + * http://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 "src/trace_processor/core/exec/tree_order.h" + +#include <algorithm> +#include <cstdint> +#include <memory> +#include <optional> +#include <random> +#include <utility> +#include <vector> + +#include "src/trace_processor/core/common/storage_types.h" +#include "src/trace_processor/core/exec/column_view.h" +#include "src/trace_processor/core/exec/operator.h" +#include "src/trace_processor/core/exec/pipeline.h" +#include "src/trace_processor/core/exec/row_batch.h" +#include "src/trace_processor/core/exec/row_selection.h" +#include "src/trace_processor/core/exec/test_utils.h" +#include "src/trace_processor/core/exec/tree_number_nodes.h" +#include "src/trace_processor/core/util/bit_vector.h" +#include "test/gtest_and_gmock.h" + +namespace perfetto::trace_processor::core::exec { +namespace { + +using testing::ElementsAre; + +// A row as the tests write one: an id, a parent id or none, and a payload +// proving the row itself came back out alongside its number. +struct Row { + int64_t id; + std::optional<int64_t> parent; + int64_t payload; +}; + +// Emits the rows in batches, refilling a single batch each time. +class RowSource final : public Source { + public: + RowSource(std::vector<Row> rows, uint32_t chunk_rows) + : rows_(std::move(rows)), chunk_rows_(chunk_rows) {} + + void SetRows(std::vector<Row> rows) { rows_ = std::move(rows); } + + std::unique_ptr<OperatorState> MakeState() const override { + return std::make_unique<State>(); + } + void Rewind(OperatorState& state) const override { + state.Cast<State>().offset = 0; + } + + bool GetData(RowBatch& out, OperatorState& state) const override { + State& s = state.Cast<State>(); + auto total = static_cast<uint32_t>(rows_.size()); + if (s.offset == total) { + return false; + } + uint32_t count = std::min(chunk_rows_, total - s.offset); + s.ids.resize(count); + s.parents.resize(count); + s.payloads.resize(count); + s.validity = BitVector::CreateWithSize(count); + for (uint32_t i = 0; i < count; ++i) { + const Row& row = rows_[s.offset + i]; + s.ids[i] = row.id; + s.payloads[i] = row.payload; + s.parents[i] = row.parent.value_or(0); + if (row.parent) { + s.validity.set(i); + } + } + out.Reset(); + out.AddColumn(ColumnView::Reference(StorageType{Int64{}}, s.ids.data())); + out.AddColumn(ColumnView::Reference(StorageType{Int64{}}, s.parents.data(), + &s.validity)); + out.AddColumn( + ColumnView::Reference(StorageType{Int64{}}, s.payloads.data())); + out.Compose(RowSelection::Range(0), count); + out.SetCardinality(count); + s.offset += count; + return true; + } + + private: + struct State : OperatorState { + ~State() override; + uint32_t offset = 0; + std::vector<int64_t> ids; + std::vector<int64_t> parents; + std::vector<int64_t> payloads; + BitVector validity; + }; + + std::vector<Row> rows_; + uint32_t chunk_rows_; +}; + +RowSource::State::~State() = default; + +class NumberedSource final : public Source { + public: + NumberedSource(std::vector<uint32_t> nodes, + std::vector<uint32_t> parents, + std::vector<int64_t> payloads) + : nodes_(std::move(nodes)), + parents_(std::move(parents)), + payloads_(std::move(payloads)) {} + + std::unique_ptr<OperatorState> MakeState() const override { + return std::make_unique<State>(); + } + void Rewind(OperatorState& state) const override { + state.Cast<State>().emitted = false; + } + bool GetData(RowBatch& out, OperatorState& state) const override { + State& s = state.Cast<State>(); + if (s.emitted) { + return false; + } + out.Reset(); + out.AddColumn(ColumnView::Reference(StorageType{Uint32{}}, nodes_.data())); + out.AddColumn( + ColumnView::Reference(StorageType{Uint32{}}, parents_.data())); + out.AddColumn( + ColumnView::Reference(StorageType{Int64{}}, payloads_.data())); + out.SetCardinality(static_cast<uint32_t>(nodes_.size())); + s.emitted = true; + return true; + } + + private: + struct State : OperatorState { + bool emitted = false; + }; + + std::vector<uint32_t> nodes_; + std::vector<uint32_t> parents_; + std::vector<int64_t> payloads_; +}; + +// Drives a plan the way an executor does: it creates the state and owns the +// batch, leaving the plan const. +class Execution { + public: + explicit Execution(const Source& source) + : source_(source), state_(source.MakeState()) {} + + RowBatch* Next() { + return source_.GetData(batch_, *state_) ? &batch_ : nullptr; + } + base::Status status() const { return source_.status(*state_); } + void Rewind() { source_.Rewind(*state_); } + + private: + const Source& source_; + std::unique_ptr<OperatorState> state_; + RowBatch batch_; +}; + +// The output: each row's payload, node number and parent node number, in the +// order the rows came out. +struct Output { + std::vector<int64_t> payload; + std::vector<int64_t> node; + std::vector<int64_t> parent; + // Returned with the rows, because how a run ended belongs to the run rather + // than to the plan. + base::Status status = base::OkStatus(); +}; + +Output Drain(Execution* run) { + Output out; + while (RowBatch* batch = run->Next()) { + std::vector<int64_t> payload = test::ReadColumn<int64_t>(*batch, 2); + std::vector<uint32_t> nodes = test::ReadColumn<uint32_t>(*batch, 3); + std::vector<uint32_t> parents = test::ReadColumn<uint32_t>(*batch, 4); + out.payload.insert(out.payload.end(), payload.begin(), payload.end()); + for (uint32_t node : nodes) { + out.node.push_back(node == kNoNode ? -1 : static_cast<int64_t>(node)); + } + for (uint32_t parent : parents) { + out.parent.push_back(parent == kNoNode ? -1 + : static_cast<int64_t>(parent)); + } + } + out.status = run->status(); + return out; +} + +// Most tests only want the rows back, so they get one execution and drain it. +Output Drain(const Source& source) { + Execution run(source); + return Drain(&run); +} + +std::vector<std::unique_ptr<Operator>> Number() { + std::vector<std::unique_ptr<Operator>> ops; + ops.push_back(std::make_unique<TreeNumberNodes>(0, 1)); + return ops; +} + +// A root, its two children and a grandchild, written parent first. +std::vector<Row> ParentFirstRows() { + return {{0, std::nullopt, 100}, {1, 0, 101}, {2, 0, 102}, {3, 1, 103}}; +} + +// The same tree, written child first. +std::vector<Row> ChildFirstRows() { + return {{3, 1, 103}, {2, 0, 102}, {1, 0, 101}, {0, std::nullopt, 100}}; +} + +// Every child appears before its parent. +void ExpectChildFirst(const Output& out) { + std::vector<int64_t> seen; + for (uint32_t i = 0; i < out.node.size(); ++i) { + if (out.parent[i] >= 0) { + EXPECT_EQ(std::find(seen.begin(), seen.end(), out.parent[i]), seen.end()) + << "row " << i << " came after its parent"; + } + seen.push_back(out.node[i]); + } +} + +TEST(TreeChildFirstTest, RowsAlreadyInOrderComeBackAsTheyArrived) { + RowSource source(ChildFirstRows(), 2); + Pipeline numbered(source, Number()); + TreeChildFirst order(numbered, 3, 4); + + Output out = Drain(order); + ASSERT_TRUE(out.status.ok()) << out.status.message(); + EXPECT_THAT(out.payload, ElementsAre(103, 102, 101, 100)); + EXPECT_THAT(out.node, ElementsAre(0, 2, 1, 3)); + EXPECT_THAT(out.parent, ElementsAre(1, 3, 3, -1)); +} + +TEST(TreeChildFirstTest, RowsInTheOtherOrderAreTurnedRound) { + RowSource source(ParentFirstRows(), 2); + Pipeline numbered(source, Number()); + TreeChildFirst order(numbered, 3, 4); + + Output out = Drain(order); + ASSERT_TRUE(out.status.ok()) << out.status.message(); + EXPECT_THAT(out.payload, ElementsAre(103, 102, 101, 100)); + ExpectChildFirst(out); +} + +// Rows in neither order can be neither passed through nor reversed: they have +// to be sorted into an order the input did not have. +TEST(TreeChildFirstTest, RowsInNeitherOrderAreSorted) { + // 1 before its parent 0, then 3 after its parent 2. + std::vector<Row> rows = { + {1, 0, 101}, {0, std::nullopt, 100}, {2, 0, 102}, {3, 2, 103}}; + RowSource source(rows, 4); + Pipeline numbered(source, Number()); + TreeChildFirst order(numbered, 3, 4); + + Output out = Drain(order); + ASSERT_TRUE(out.status.ok()) << out.status.message(); + ExpectChildFirst(out); + std::vector<int64_t> payload = out.payload; + std::sort(payload.begin(), payload.end()); + EXPECT_THAT(payload, ElementsAre(100, 101, 102, 103)); +} + +// Scattered ids, such as those of a filtered relation, are numbered densely, +// so anything indexed by node number is the size of the input rather than of +// the table it was filtered from. +TEST(TreeChildFirstTest, AScatteringOfIdsIsNumberedDensely) { + std::vector<Row> rows = {{123, 900, 103}, + {700, 500, 102}, + {900, 500, 101}, + {500, std::nullopt, 100}}; + RowSource source(rows, 3); + Pipeline numbered(source, Number()); + TreeChildFirst order(numbered, 3, 4); + + Output out = Drain(order); + ASSERT_TRUE(out.status.ok()) << out.status.message(); + EXPECT_THAT(out.node, ElementsAre(0, 2, 1, 3)); + EXPECT_THAT(out.parent, ElementsAre(1, 3, 3, -1)); +} + +TEST(TreeChildFirstTest, AParentWhichIsNotARowIsReported) { + std::vector<Row> rows = {{0, std::nullopt, 100}, {1, 42, 101}}; + RowSource source(rows, 2); + Pipeline numbered(source, Number()); + TreeChildFirst order(numbered, 3, 4); + + Output out = Drain(order); + EXPECT_FALSE(out.status.ok()); + EXPECT_THAT(out.status.message(), testing::HasSubstr("not itself a row")); +} + +TEST(TreeChildFirstTest, ACycleIsReported) { + std::vector<Row> rows = {{0, 1, 100}, {1, 0, 101}}; + RowSource source(rows, 2); + Pipeline numbered(source, Number()); + TreeChildFirst order(numbered, 3, 4); + + Output out = Drain(order); + EXPECT_FALSE(out.status.ok()); + EXPECT_THAT(out.status.message(), testing::HasSubstr("cycle")); +} + +TEST(TreeChildFirstTest, ASelfParentIsReported) { + RowSource source({{0, 0, 100}}, 1); + Pipeline numbered(source, Number()); + TreeChildFirst order(numbered, 3, 4); + + Output out = Drain(order); + EXPECT_FALSE(out.status.ok()); + EXPECT_THAT(out.status.message(), testing::HasSubstr("own parent")); +} + +TEST(TreeChildFirstTest, DuplicateNumberedNodesAreReported) { + NumberedSource source({0, 1, 0}, {1, kNoNode, 1}, {100, 101, 102}); + TreeChildFirst order(source, 0, 1); + Execution run(order); + while (run.Next()) { + } + EXPECT_FALSE(run.status().ok()); + EXPECT_THAT(run.status().message(), testing::HasSubstr("same node")); +} + +TEST(TreeChildFirstTest, RewindReadsTheInputAgain) { + RowSource source(ChildFirstRows(), 2); + Pipeline numbered(source, Number()); + TreeChildFirst order(numbered, 3, 4); + Execution run(order); + Output first = Drain(&run); + ASSERT_TRUE(first.status.ok()) << first.status.message(); + + source.SetRows( + {{3, 1, 203}, {2, 0, 202}, {1, 0, 201}, {0, std::nullopt, 200}}); + run.Rewind(); + Output second = Drain(&run); + ASSERT_TRUE(second.status.ok()) << second.status.message(); + EXPECT_THAT(second.payload, ElementsAre(203, 202, 201, 200)); +} + +TEST(TreeChildFirstTest, RewindDiscardsAFailedFill) { + RowSource source({{0, 1, 100}, {1, 0, 101}}, 2); + Pipeline numbered(source, Number()); + TreeChildFirst order(numbered, 3, 4); + Execution run(order); + Output failed = Drain(&run); + ASSERT_FALSE(failed.status.ok()); + + source.SetRows(ChildFirstRows()); + run.Rewind(); + Output recovered = Drain(&run); + ASSERT_TRUE(recovered.status.ok()) << recovered.status.message(); + EXPECT_THAT(recovered.payload, ElementsAre(103, 102, 101, 100)); +} + +// Child first is not merely "every child before its parent": it is a depth +// first post-order, so a node's descendants are the block of rows immediately +// before it. A fold up the tree can therefore carry a stack of the current +// path rather than an array indexed by node. +TEST(TreeChildFirstTest, IsADepthFirstPostOrder) { + std::mt19937 rng(29); + std::vector<Row> rows; + rows.push_back({0, std::nullopt, 0}); + for (int64_t id = 1; id < 3000; ++id) { + int64_t parent = std::uniform_int_distribution<int64_t>(0, id - 1)(rng); + rows.push_back({id, parent, id}); + } + std::shuffle(rows.begin(), rows.end(), rng); + + RowSource source(rows, 256); + Pipeline numbered(source, Number()); + TreeChildFirst order(numbered, 3, 4); + Output out = Drain(order); + ASSERT_TRUE(out.status.ok()) << out.status.message(); + ASSERT_EQ(out.node.size(), rows.size()); + + // Fold the tree up carrying only the current path, which is correct exactly + // when the order is a post-order. + std::vector<std::pair<int64_t, int64_t>> path; + std::vector<int64_t> totals(rows.size(), 0); + for (uint32_t i = 0; i < out.node.size(); ++i) { + int64_t below = 0; + if (!path.empty() && path.back().first == out.node[i]) { + below = path.back().second; + path.pop_back(); + } + int64_t total = 1 + below; + totals[static_cast<size_t>(out.payload[i])] = total; + if (out.parent[i] >= 0) { + if (path.empty() || path.back().first != out.parent[i]) { + path.push_back({out.parent[i], 0}); + } + path.back().second += total; + } + } + EXPECT_TRUE(path.empty()) << "the path did not unwind"; + + // Every node's total is the size of its subtree. + std::vector<int64_t> expected(rows.size(), 1); + std::vector<int64_t> parent_of(rows.size(), -1); + for (const Row& row : rows) { + parent_of[static_cast<size_t>(row.id)] = + row.parent ? *row.parent : int64_t{-1}; + } + for (size_t id = 0; id < rows.size(); ++id) { + for (int64_t p = parent_of[id]; p >= 0; + p = parent_of[static_cast<size_t>(p)]) { + ++expected[static_cast<size_t>(p)]; + } + } + EXPECT_EQ(totals, expected); +} + +} // namespace +} // namespace perfetto::trace_processor::core::exec