tp: add tree_propagate_down operator for tree transformations (#5257)
## Summary
- Add `PropagateDown()` method to TreeTransformer for root-to-leaf BFS
propagation
- Support SUM, MIN, MAX, FIRST, LAST aggregate operations
- Propagated columns become real columns enabling
filter→propagate→filter chains
- PropagateTreeDown bytecode takes spec_start/spec_count with separate
source/dest columns
## Stack
- #5262 tp: introduce TreeColumns and refactor TreeTransformer to use it
- **#5257 tp: add tree_propagate_down operator for tree
transformations** (this PR)
## Test plan
- 13 new propagate diff tests including chained propagation and
filter→propagate→filter
- All 23 tree tests pass
diff --git a/Android.bp b/Android.bp
index ff488f4..7493b53 100644
--- a/Android.bp
+++ b/Android.bp
@@ -15270,6 +15270,7 @@
filegroup {
name: "perfetto_src_trace_processor_core_tree_tree",
srcs: [
+ "src/trace_processor/core/tree/propagate_spec.cc",
"src/trace_processor/core/tree/tree_columns_builder.cc",
"src/trace_processor/core/tree/tree_transformer.cc",
],
@@ -16433,6 +16434,7 @@
"src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_conversion.cc",
"src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_filter.cc",
"src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_functions.cc",
+ "src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_propagate.cc",
],
}
@@ -16773,6 +16775,7 @@
"src/trace_processor/perfetto_sql/stdlib/std/traceinfo/metadata_for_primary_scope.sql",
"src/trace_processor/perfetto_sql/stdlib/std/traceinfo/trace.sql",
"src/trace_processor/perfetto_sql/stdlib/std/trees/filter.sql",
+ "src/trace_processor/perfetto_sql/stdlib/std/trees/propagate.sql",
"src/trace_processor/perfetto_sql/stdlib/std/trees/table_conversion.sql",
"src/trace_processor/perfetto_sql/stdlib/time/conversion.sql",
"src/trace_processor/perfetto_sql/stdlib/traced/stats.sql",
diff --git a/BUILD b/BUILD
index 9f593d0..aa15dee 100644
--- a/BUILD
+++ b/BUILD
@@ -2183,6 +2183,8 @@
perfetto_filegroup(
name = "src_trace_processor_core_tree_tree",
srcs = [
+ "src/trace_processor/core/tree/propagate_spec.cc",
+ "src/trace_processor/core/tree/propagate_spec.h",
"src/trace_processor/core/tree/tree_columns.h",
"src/trace_processor/core/tree/tree_columns_builder.cc",
"src/trace_processor/core/tree/tree_columns_builder.h",
@@ -3331,6 +3333,8 @@
"src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_filter.h",
"src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_functions.cc",
"src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_functions.h",
+ "src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_propagate.cc",
+ "src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_propagate.h",
],
)
@@ -3956,6 +3960,7 @@
name = "src_trace_processor_perfetto_sql_stdlib_std_trees_trees",
srcs = [
"src/trace_processor/perfetto_sql/stdlib/std/trees/filter.sql",
+ "src/trace_processor/perfetto_sql/stdlib/std/trees/propagate.sql",
"src/trace_processor/perfetto_sql/stdlib/std/trees/table_conversion.sql",
],
)
diff --git a/src/trace_processor/core/common/tree_types.h b/src/trace_processor/core/common/tree_types.h
index 5a0622d..5bd9b0c 100644
--- a/src/trace_processor/core/common/tree_types.h
+++ b/src/trace_processor/core/common/tree_types.h
@@ -26,6 +26,15 @@
// Root nodes have this value as their parent.
inline constexpr uint32_t kNullParent = std::numeric_limits<uint32_t>::max();
+// Aggregation operation for tree propagation (propagate-down).
+enum class PropagateAggOp : uint8_t {
+ kSum,
+ kMin,
+ kMax,
+ kFirst,
+ kLast,
+};
+
} // namespace perfetto::trace_processor::core
#endif // SRC_TRACE_PROCESSOR_CORE_COMMON_TREE_TYPES_H_
diff --git a/src/trace_processor/core/interpreter/bytecode_instructions.h b/src/trace_processor/core/interpreter/bytecode_instructions.h
index e57b667..5014364 100644
--- a/src/trace_processor/core/interpreter/bytecode_instructions.h
+++ b/src/trace_processor/core/interpreter/bytecode_instructions.h
@@ -637,6 +637,22 @@
indices_register);
};
+// Propagates values from root toward leaves using BFS. For each spec in the
+// range [spec_start, spec_start + spec_count), copies source column data to
+// the dest column, then applies the aggregate operation downward via BFS.
+//
+// Requires the P2C CSR cache to be rebuilt if stale.
+struct PropagateTreeDown : Bytecode {
+ static constexpr Cost kCost = LinearPerRowCost{20};
+
+ PERFETTO_DATAFRAME_BYTECODE_IMPL_3(RwHandle<std::unique_ptr<TreeState>>,
+ tree_state_register,
+ uint32_t,
+ spec_start,
+ uint32_t,
+ spec_count);
+};
+
// Bytecode ops that require FilterValueFetcher access.
#define PERFETTO_DATAFRAME_BYTECODE_FVF_LIST(X) \
X(CastFilterValue<Id>) \
@@ -799,7 +815,8 @@
X(FinalizeRanksInMap) \
X(SortRowLayout) \
X(Reverse) \
- X(FilterTreeState)
+ X(FilterTreeState) \
+ X(PropagateTreeDown)
// Combined list of all bytecode instruction types.
#define PERFETTO_DATAFRAME_BYTECODE_LIST(X) \
diff --git a/src/trace_processor/core/interpreter/bytecode_interpreter_impl.cc b/src/trace_processor/core/interpreter/bytecode_interpreter_impl.cc
index 4095fdc..10da636 100644
--- a/src/trace_processor/core/interpreter/bytecode_interpreter_impl.cc
+++ b/src/trace_processor/core/interpreter/bytecode_interpreter_impl.cc
@@ -453,6 +453,78 @@
ts->p2c_valid = true;
}
+// Runs a single propagate-down pass over the BFS order for one column.
+// |Combine| is a lambda (parent_val, child_val) -> new_child_val.
+template <typename T, typename Combine>
+void PropagateDownBfs(T* d,
+ Combine combine,
+ const uint32_t* queue,
+ uint32_t queue_end,
+ const uint32_t* parent_arr) {
+ for (uint32_t qi = 0; qi < queue_end; ++qi) {
+ uint32_t node = queue[qi];
+ uint32_t p = parent_arr[node];
+ if (p != kNullParent) {
+ d[node] = combine(d[p], d[node]);
+ }
+ }
+}
+
+// Dispatches on storage type then agg_op for a single propagate-down spec.
+template <typename T>
+void PropagateDownColumnTyped(T* d,
+ PropagateAggOp agg_op,
+ const uint32_t* queue,
+ uint32_t queue_end,
+ const uint32_t* parent_arr) {
+ switch (agg_op) {
+ case PropagateAggOp::kSum:
+ PropagateDownBfs(
+ d, [](auto p, auto c) { return p + c; }, queue, queue_end,
+ parent_arr);
+ break;
+ case PropagateAggOp::kMin:
+ PropagateDownBfs(
+ d, [](auto p, auto c) { return std::min(p, c); }, queue, queue_end,
+ parent_arr);
+ break;
+ case PropagateAggOp::kMax:
+ PropagateDownBfs(
+ d, [](auto p, auto c) { return std::max(p, c); }, queue, queue_end,
+ parent_arr);
+ break;
+ case PropagateAggOp::kFirst:
+ PropagateDownBfs(
+ d, [](auto p, auto) { return p; }, queue, queue_end, parent_arr);
+ break;
+ case PropagateAggOp::kLast:
+ break;
+ }
+}
+
+void PropagateDownColumn(uint8_t* data,
+ StorageType storage_type,
+ PropagateAggOp agg_op,
+ const uint32_t* queue,
+ uint32_t queue_end,
+ const uint32_t* parent_arr) {
+ if (storage_type.Is<Uint32>()) {
+ PropagateDownColumnTyped(reinterpret_cast<uint32_t*>(data), agg_op, queue,
+ queue_end, parent_arr);
+ } else if (storage_type.Is<Int32>()) {
+ PropagateDownColumnTyped(reinterpret_cast<int32_t*>(data), agg_op, queue,
+ queue_end, parent_arr);
+ } else if (storage_type.Is<Int64>()) {
+ PropagateDownColumnTyped(reinterpret_cast<int64_t*>(data), agg_op, queue,
+ queue_end, parent_arr);
+ } else if (storage_type.Is<Double>()) {
+ PropagateDownColumnTyped(reinterpret_cast<double*>(data), agg_op, queue,
+ queue_end, parent_arr);
+ } else {
+ PERFETTO_FATAL("Unsupported storage type for propagate down");
+ }
+}
+
} // namespace
void FilterTreeState(InterpreterState& state,
@@ -569,4 +641,50 @@
indices.e = indices.b + new_count;
}
+void PropagateTreeDown(InterpreterState& state,
+ const struct PropagateTreeDown& bc) {
+ using B = struct PropagateTreeDown;
+ auto& ts = state.ReadFromRegister(bc.arg<B::tree_state_register>());
+ uint32_t spec_start = bc.arg<B::spec_start>();
+ uint32_t spec_count = bc.arg<B::spec_count>();
+
+ if (ts->row_count == 0 || spec_count == 0) {
+ return;
+ }
+
+ BuildP2CFromTreeState(ts.get());
+
+ // BFS from roots, building a topological order in scratch1.
+ uint32_t* queue = ts->scratch1.begin();
+ uint32_t queue_end = 0;
+ for (uint32_t i = 0; i < ts->p2c_root_count; ++i) {
+ queue[queue_end++] = ts->p2c_roots[i];
+ }
+ for (uint32_t qi = 0; qi < queue_end; ++qi) {
+ uint32_t cs = ts->p2c_offsets[queue[qi]];
+ uint32_t ce = ts->p2c_offsets[queue[qi] + 1];
+ for (uint32_t ci = cs; ci < ce; ++ci) {
+ queue[queue_end++] = ts->p2c_children[ci];
+ }
+ }
+
+ // Process only the specs in [spec_start, spec_start + spec_count).
+ // For each: copy source → dest, then BFS propagation on dest.
+ const uint32_t* parent_arr = ts->parent.begin();
+ uint32_t n = ts->row_count;
+ for (uint32_t si = spec_start; si < spec_start + spec_count; ++si) {
+ const auto& spec = ts->propagate_down_specs[si];
+ uint8_t* src_data = ts->columns[spec.source_ts_col].data.begin();
+ uint8_t* dst_data = ts->columns[spec.dest_ts_col].data.begin();
+ uint32_t byte_count = n * ts->columns[spec.dest_ts_col].elem_size;
+
+ // Copy source data into dest column.
+ memcpy(dst_data, src_data, byte_count);
+
+ // BFS propagation on dest data.
+ PropagateDownColumn(dst_data, spec.storage_type, spec.agg_op, queue,
+ queue_end, parent_arr);
+ }
+}
+
} // namespace perfetto::trace_processor::core::interpreter::ops
diff --git a/src/trace_processor/core/interpreter/bytecode_interpreter_impl.h b/src/trace_processor/core/interpreter/bytecode_interpreter_impl.h
index 863a341..efb8bb1 100644
--- a/src/trace_processor/core/interpreter/bytecode_interpreter_impl.h
+++ b/src/trace_processor/core/interpreter/bytecode_interpreter_impl.h
@@ -1726,6 +1726,12 @@
// the TreeState, and resets the indices span to [0..new_row_count-1].
void FilterTreeState(InterpreterState& state, const struct FilterTreeState& bc);
+// Propagates column values from roots toward leaves using BFS.
+// For each parent→child edge, applies the aggregate operation from
+// TreeState::propagate_down_specs.
+void PropagateTreeDown(InterpreterState& state,
+ const struct PropagateTreeDown& bc);
+
} // namespace ops
// Macros for generating case statements that dispatch to ops:: free functions.
diff --git a/src/trace_processor/core/interpreter/interpreter_types.h b/src/trace_processor/core/interpreter/interpreter_types.h
index 8b7ec73..500298e 100644
--- a/src/trace_processor/core/interpreter/interpreter_types.h
+++ b/src/trace_processor/core/interpreter/interpreter_types.h
@@ -29,6 +29,7 @@
#include "src/trace_processor/core/common/null_types.h"
#include "src/trace_processor/core/common/op_types.h"
#include "src/trace_processor/core/common/storage_types.h"
+#include "src/trace_processor/core/common/tree_types.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/slab.h"
@@ -267,6 +268,16 @@
// Scratch buffers (allocated once at max size, reused).
Slab<uint32_t> scratch1; // initial_row_count * 2
Slab<uint32_t> scratch2; // initial_row_count
+
+ // Propagation specs: set by TreeTransformer, consumed by PropagateTreeDown.
+ // Each PropagateTreeDown bytecode processes a contiguous range of specs.
+ struct PropagateDownSpec {
+ PropagateAggOp agg_op;
+ uint32_t source_ts_col; // index into |columns| to copy FROM
+ uint32_t dest_ts_col; // index into |columns| to propagate INTO
+ StorageType storage_type;
+ };
+ std::vector<PropagateDownSpec> propagate_down_specs;
};
} // namespace perfetto::trace_processor::core::interpreter
diff --git a/src/trace_processor/core/tree/BUILD.gn b/src/trace_processor/core/tree/BUILD.gn
index af7fb37..676b16c 100644
--- a/src/trace_processor/core/tree/BUILD.gn
+++ b/src/trace_processor/core/tree/BUILD.gn
@@ -16,6 +16,8 @@
source_set("tree") {
sources = [
+ "propagate_spec.cc",
+ "propagate_spec.h",
"tree_columns.h",
"tree_columns_builder.cc",
"tree_columns_builder.h",
diff --git a/src/trace_processor/core/tree/propagate_spec.cc b/src/trace_processor/core/tree/propagate_spec.cc
new file mode 100644
index 0000000..dd9208d
--- /dev/null
+++ b/src/trace_processor/core/tree/propagate_spec.cc
@@ -0,0 +1,108 @@
+/*
+ * 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/tree/propagate_spec.h"
+
+#include <string>
+
+#include "perfetto/base/status.h"
+#include "perfetto/ext/base/status_or.h"
+#include "perfetto/ext/base/string_utils.h"
+
+namespace perfetto::trace_processor::core::tree {
+
+base::StatusOr<PropagateSpec> ParsePropagateSpec(const std::string& spec) {
+ std::string trimmed = base::TrimWhitespace(spec);
+ if (trimmed.empty()) {
+ return base::ErrStatus("propagate spec: empty string");
+ }
+
+ // Find '(' to extract agg function name.
+ auto lparen = trimmed.find('(');
+ if (lparen == std::string::npos) {
+ return base::ErrStatus("propagate spec: expected '(' in '%s'",
+ trimmed.c_str());
+ }
+ std::string agg_str =
+ base::ToUpper(base::TrimWhitespace(trimmed.substr(0, lparen)));
+
+ PropagateAggOp agg_op;
+ if (agg_str == "SUM") {
+ agg_op = PropagateAggOp::kSum;
+ } else if (agg_str == "MIN") {
+ agg_op = PropagateAggOp::kMin;
+ } else if (agg_str == "MAX") {
+ agg_op = PropagateAggOp::kMax;
+ } else if (agg_str == "FIRST") {
+ agg_op = PropagateAggOp::kFirst;
+ } else if (agg_str == "LAST") {
+ agg_op = PropagateAggOp::kLast;
+ } else {
+ return base::ErrStatus("propagate spec: unknown aggregate '%s'",
+ agg_str.c_str());
+ }
+
+ // Find ')' to extract source column name.
+ auto rparen = trimmed.find(')', lparen + 1);
+ if (rparen == std::string::npos) {
+ return base::ErrStatus("propagate spec: expected ')' in '%s'",
+ trimmed.c_str());
+ }
+ std::string source_col =
+ base::TrimWhitespace(trimmed.substr(lparen + 1, rparen - lparen - 1));
+ if (source_col.empty()) {
+ return base::ErrStatus("propagate spec: empty source column in '%s'",
+ trimmed.c_str());
+ }
+
+ // Find 'AS' (case-insensitive) after ')'.
+ std::string remainder = trimmed.substr(rparen + 1);
+ std::string remainder_upper = base::ToUpper(remainder);
+ auto as_pos = remainder_upper.find("AS");
+ if (as_pos == std::string::npos) {
+ return base::ErrStatus("propagate spec: expected 'AS' in '%s'",
+ trimmed.c_str());
+ }
+
+ // Verify that 'AS' is preceded and followed by whitespace or is at the
+ // boundary.
+ if (as_pos > 0 && remainder[as_pos - 1] != ' ' &&
+ remainder[as_pos - 1] != '\t') {
+ return base::ErrStatus(
+ "propagate spec: expected whitespace before 'AS' in '%s'",
+ trimmed.c_str());
+ }
+ if (as_pos + 2 < remainder.size() && remainder[as_pos + 2] != ' ' &&
+ remainder[as_pos + 2] != '\t') {
+ return base::ErrStatus(
+ "propagate spec: expected whitespace after 'AS' in '%s'",
+ trimmed.c_str());
+ }
+
+ std::string output_col = base::TrimWhitespace(remainder.substr(as_pos + 2));
+ if (output_col.empty()) {
+ return base::ErrStatus("propagate spec: empty output column in '%s'",
+ trimmed.c_str());
+ }
+
+ PropagateSpec result;
+ result.agg_op = agg_op;
+ result.source_col_name = std::move(source_col);
+ result.output_col_name = std::move(output_col);
+ return result;
+}
+
+} // namespace perfetto::trace_processor::core::tree
diff --git a/src/trace_processor/core/tree/propagate_spec.h b/src/trace_processor/core/tree/propagate_spec.h
new file mode 100644
index 0000000..f6bdec9
--- /dev/null
+++ b/src/trace_processor/core/tree/propagate_spec.h
@@ -0,0 +1,44 @@
+/*
+ * 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_TREE_PROPAGATE_SPEC_H_
+#define SRC_TRACE_PROCESSOR_CORE_TREE_PROPAGATE_SPEC_H_
+
+#include <string>
+
+#include "perfetto/ext/base/status_or.h"
+#include "src/trace_processor/core/common/tree_types.h"
+
+namespace perfetto::trace_processor::core::tree {
+
+struct PropagateSpec {
+ PropagateAggOp agg_op;
+ std::string source_col_name;
+ std::string output_col_name;
+};
+
+// Parses a propagate spec string of the form 'AGG(source_col) AS output_col'.
+// Case-insensitive for the aggregate function name and AS keyword.
+// Whitespace-resilient.
+base::StatusOr<PropagateSpec> ParsePropagateSpec(const std::string& spec);
+
+} // namespace perfetto::trace_processor::core::tree
+
+namespace perfetto::trace_processor {
+namespace tree = core::tree;
+} // namespace perfetto::trace_processor
+
+#endif // SRC_TRACE_PROCESSOR_CORE_TREE_PROPAGATE_SPEC_H_
diff --git a/src/trace_processor/core/tree/tree_transformer.cc b/src/trace_processor/core/tree/tree_transformer.cc
index 393b61d..faac5cc 100644
--- a/src/trace_processor/core/tree/tree_transformer.cc
+++ b/src/trace_processor/core/tree/tree_transformer.cc
@@ -44,6 +44,7 @@
#include "src/trace_processor/core/interpreter/bytecode_interpreter_impl.h" // IWYU pragma: keep
#include "src/trace_processor/core/interpreter/bytecode_registers.h"
#include "src/trace_processor/core/interpreter/interpreter_types.h"
+#include "src/trace_processor/core/tree/propagate_spec.h"
#include "src/trace_processor/core/tree/tree_columns.h"
#include "src/trace_processor/core/util/bit_vector.h"
#include "src/trace_processor/core/util/range.h"
@@ -289,6 +290,78 @@
return base::OkStatus();
}
+// Returns the size in bytes of one element for the given storage type.
+static uint32_t ElementSize(StorageType type) {
+ switch (type.index()) {
+ case StorageType::GetTypeIndex<Uint32>():
+ return sizeof(uint32_t);
+ case StorageType::GetTypeIndex<Int32>():
+ return sizeof(int32_t);
+ case StorageType::GetTypeIndex<Int64>():
+ return sizeof(int64_t);
+ case StorageType::GetTypeIndex<Double>():
+ return sizeof(double);
+ case StorageType::GetTypeIndex<String>():
+ return sizeof(StringPool::Id);
+ default:
+ PERFETTO_FATAL("Unsupported storage type");
+ }
+}
+
+base::Status TreeTransformer::PropagateDown(std::vector<PropagateSpec> specs) {
+ if (cols_.row_count == 0 || specs.empty()) {
+ return base::OkStatus();
+ }
+
+ uint32_t spec_start = static_cast<uint32_t>(propagate_specs_.size());
+
+ for (auto& spec : specs) {
+ auto src = ResolveColumn(spec.source_col_name);
+ if (!src) {
+ return base::ErrStatus("propagate_down: source column '%s' not found",
+ spec.source_col_name.c_str());
+ }
+ StorageType st = cols_.columns[*src].type;
+ if (st.Is<String>()) {
+ return base::ErrStatus(
+ "propagate_down: string columns are not supported (column '%s')",
+ spec.source_col_name.c_str());
+ }
+ if (st.Is<Id>()) {
+ return base::ErrStatus(
+ "propagate_down: Id columns are not supported (column '%s')",
+ spec.source_col_name.c_str());
+ }
+
+ // Add a new column.
+ uint32_t dest = static_cast<uint32_t>(cols_.names.size());
+ cols_.names.push_back(std::move(spec.output_col_name));
+
+ TreeColumns::Column oc;
+ oc.type = st;
+ oc.elem_size = ElementSize(st);
+ oc.data = Slab<uint8_t>::Alloc(static_cast<uint64_t>(cols_.row_count) *
+ oc.elem_size);
+ cols_.columns.push_back(std::move(oc));
+
+ propagate_specs_.push_back({*src, dest, spec.agg_op});
+ }
+
+ // Emit PropagateTreeDown bytecode with the spec range.
+ has_operations_ = true;
+ i::RwHandle<std::unique_ptr<i::TreeState>> ts_reg(tree_state_reg_index_);
+ {
+ using P = i::PropagateTreeDown;
+ auto& op = builder_->AddOpcode<P>(i::Index<P>());
+ op.arg<P::tree_state_register>() = ts_reg;
+ op.arg<P::spec_start>() = spec_start;
+ op.arg<P::spec_count>() =
+ static_cast<uint32_t>(propagate_specs_.size()) - spec_start;
+ }
+
+ return base::OkStatus();
+}
+
base::StatusOr<dataframe::Dataframe> TreeTransformer::ToDataframe() && {
uint32_t n = cols_.row_count;
@@ -338,6 +411,17 @@
ts->null_bitvectors.push_back(std::move(col.null_bv));
}
+ // Populate propagate_down_specs (column indices map 1:1).
+ for (const auto& pi : propagate_specs_) {
+ using PDS = interpreter::TreeState::PropagateDownSpec;
+ ts->propagate_down_specs.push_back(PDS{
+ pi.agg_op,
+ pi.source_col,
+ pi.dest_col,
+ cols_.columns[pi.dest_col].type,
+ });
+ }
+
ts->p2c_offsets = Slab<uint32_t>::Alloc(n + 1);
ts->p2c_children = Slab<uint32_t>::Alloc(n);
ts->p2c_roots = Slab<uint32_t>::Alloc(n);
diff --git a/src/trace_processor/core/tree/tree_transformer.h b/src/trace_processor/core/tree/tree_transformer.h
index a4db801..9f9ce85 100644
--- a/src/trace_processor/core/tree/tree_transformer.h
+++ b/src/trace_processor/core/tree/tree_transformer.h
@@ -30,6 +30,7 @@
#include "src/trace_processor/core/common/storage_types.h"
#include "src/trace_processor/core/dataframe/dataframe.h"
#include "src/trace_processor/core/dataframe/specs.h"
+#include "src/trace_processor/core/tree/propagate_spec.h"
#include "src/trace_processor/core/tree/tree_columns.h"
namespace perfetto::trace_processor::core::interpreter {
@@ -48,7 +49,9 @@
// Usage:
// TreeTransformer t(std::move(cols), pool);
// RETURN_IF_ERROR(t.FilterTree(specs, values));
-// ASSIGN_OR_RETURN(auto result, std::move(t).ToDataframe());
+// RETURN_IF_ERROR(t.PropagateDown(propagate_specs));
+// RETURN_IF_ERROR(t.FilterTree(specs2, values2)); // can filter on
+// propagated ASSIGN_OR_RETURN(auto result, std::move(t).ToDataframe());
class TreeTransformer {
public:
TreeTransformer(TreeColumns cols, StringPool* pool);
@@ -72,6 +75,14 @@
base::Status FilterTree(std::vector<dataframe::FilterSpec> specs,
std::vector<SqlValue> values);
+ // Propagates column values from root toward leaves. For each spec, a new
+ // output column is created and filled by copying the source column and
+ // then applying the aggregate operation downward through the tree via BFS.
+ //
+ // After this call, the new columns can be referenced by name in subsequent
+ // FilterTree() calls.
+ base::Status PropagateDown(std::vector<PropagateSpec> specs);
+
// Finalizes bytecode, executes it, and returns the resulting dataframe.
base::StatusOr<dataframe::Dataframe> ToDataframe() &&;
@@ -83,6 +94,12 @@
uint32_t col; // index into cols_.columns
};
+ struct PropagateInfo {
+ uint32_t source_col; // cols_.columns index
+ uint32_t dest_col; // cols_.columns index
+ PropagateAggOp agg_op;
+ };
+
TreeColumns cols_;
StringPool* pool_;
@@ -100,6 +117,9 @@
std::vector<SqlValue> filter_values_;
uint32_t filter_value_count_ = 0;
+ // Propagation specs accumulated across PropagateDown calls.
+ std::vector<PropagateInfo> propagate_specs_;
+
// Whether any bytecodes have been emitted.
bool has_operations_ = false;
};
diff --git a/src/trace_processor/perfetto_sql/intrinsics/functions/trees/BUILD.gn b/src/trace_processor/perfetto_sql/intrinsics/functions/trees/BUILD.gn
index 18ef2e2..b733f6d 100644
--- a/src/trace_processor/perfetto_sql/intrinsics/functions/trees/BUILD.gn
+++ b/src/trace_processor/perfetto_sql/intrinsics/functions/trees/BUILD.gn
@@ -20,6 +20,8 @@
"tree_filter.h",
"tree_functions.cc",
"tree_functions.h",
+ "tree_propagate.cc",
+ "tree_propagate.h",
]
deps = [
"../../../../../../gn:default_deps",
diff --git a/src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_functions.cc b/src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_functions.cc
index 305a70d..6f8d1eb 100644
--- a/src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_functions.cc
+++ b/src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_functions.cc
@@ -22,6 +22,7 @@
#include "src/trace_processor/perfetto_sql/engine/perfetto_sql_engine.h"
#include "src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_conversion.h"
#include "src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_filter.h"
+#include "src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_propagate.h"
namespace perfetto::trace_processor {
@@ -32,6 +33,7 @@
RETURN_IF_ERROR(engine.RegisterFunction<TreeConstraint>(nullptr));
RETURN_IF_ERROR(engine.RegisterFunction<TreeWhereAnd>(nullptr));
RETURN_IF_ERROR(engine.RegisterFunction<TreeFilter>(nullptr));
+ RETURN_IF_ERROR(engine.RegisterFunction<TreePropagateDown>(nullptr));
return base::OkStatus();
}
diff --git a/src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_propagate.cc b/src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_propagate.cc
new file mode 100644
index 0000000..e0d112c
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_propagate.cc
@@ -0,0 +1,78 @@
+/*
+ * 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/perfetto_sql/intrinsics/functions/trees/tree_propagate.h"
+
+#include <memory>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "src/trace_processor/core/tree/propagate_spec.h"
+#include "src/trace_processor/core/tree/tree_transformer.h"
+#include "src/trace_processor/sqlite/bindings/sqlite_result.h"
+#include "src/trace_processor/sqlite/bindings/sqlite_value.h"
+#include "src/trace_processor/sqlite/sqlite_utils.h"
+
+namespace perfetto::trace_processor {
+
+void TreePropagateDown::Step(sqlite3_context* ctx,
+ int argc,
+ sqlite3_value** argv) {
+ if (argc < 2) {
+ return sqlite::result::Error(
+ ctx,
+ "tree_propagate_down: expected at least 2 arguments "
+ "(tree_ptr, 'AGG(col) AS alias', ...)");
+ }
+
+ // Extract tree pointer.
+ auto* tree_ptr =
+ sqlite::value::Pointer<sqlite::utils::MovePointer<tree::TreeTransformer>>(
+ argv[0], "TREE_TRANSFORMER");
+ if (!tree_ptr) {
+ return sqlite::result::Error(
+ ctx, "tree_propagate_down: expected TREE_TRANSFORMER");
+ }
+ if (tree_ptr->taken()) {
+ return sqlite::result::Error(
+ ctx, "tree_propagate_down: tree has already been consumed");
+ }
+
+ // Parse each spec string.
+ std::vector<tree::PropagateSpec> specs;
+ for (int i = 1; i < argc; ++i) {
+ if (sqlite::value::Type(argv[i]) != sqlite::Type::kText) {
+ return sqlite::result::Error(
+ ctx, "tree_propagate_down: spec arguments must be strings");
+ }
+ std::string spec_str = sqlite::value::Text(argv[i]);
+ SQLITE_ASSIGN_OR_RETURN(ctx, auto spec, tree::ParsePropagateSpec(spec_str));
+ specs.push_back(std::move(spec));
+ }
+
+ auto transformer = tree_ptr->Take();
+ auto status = transformer.PropagateDown(std::move(specs));
+ SQLITE_RETURN_IF_ERROR(ctx, status);
+
+ return sqlite::result::UniquePointer(
+ ctx,
+ std::make_unique<sqlite::utils::MovePointer<tree::TreeTransformer>>(
+ std::move(transformer)),
+ "TREE_TRANSFORMER");
+}
+
+} // namespace perfetto::trace_processor
diff --git a/src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_propagate.h b/src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_propagate.h
new file mode 100644
index 0000000..6726f4d
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/intrinsics/functions/trees/tree_propagate.h
@@ -0,0 +1,36 @@
+/*
+ * 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_PERFETTO_SQL_INTRINSICS_FUNCTIONS_TREES_TREE_PROPAGATE_H_
+#define SRC_TRACE_PROCESSOR_PERFETTO_SQL_INTRINSICS_FUNCTIONS_TREES_TREE_PROPAGATE_H_
+
+#include "src/trace_processor/sqlite/bindings/sqlite_function.h"
+
+namespace perfetto::trace_processor {
+
+// Variadic scalar function that propagates column values from root toward
+// leaves using BFS. Takes a tree pointer followed by one or more spec strings
+// of the form 'AGG(source_col) AS output_col'.
+struct TreePropagateDown : public sqlite::Function<TreePropagateDown> {
+ static constexpr char kName[] = "__intrinsic_tree_propagate_down";
+ static constexpr int kArgCount = -1;
+
+ static void Step(sqlite3_context* ctx, int argc, sqlite3_value** argv);
+};
+
+} // namespace perfetto::trace_processor
+
+#endif // SRC_TRACE_PROCESSOR_PERFETTO_SQL_INTRINSICS_FUNCTIONS_TREES_TREE_PROPAGATE_H_
diff --git a/src/trace_processor/perfetto_sql/stdlib/std/trees/BUILD.gn b/src/trace_processor/perfetto_sql/stdlib/std/trees/BUILD.gn
index f40448f..882d6d1 100644
--- a/src/trace_processor/perfetto_sql/stdlib/std/trees/BUILD.gn
+++ b/src/trace_processor/perfetto_sql/stdlib/std/trees/BUILD.gn
@@ -17,6 +17,7 @@
perfetto_sql_source_set("trees") {
sources = [
"filter.sql",
+ "propagate.sql",
"table_conversion.sql",
]
}
diff --git a/src/trace_processor/perfetto_sql/stdlib/std/trees/propagate.sql b/src/trace_processor/perfetto_sql/stdlib/std/trees/propagate.sql
new file mode 100644
index 0000000..d0d5cae
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/stdlib/std/trees/propagate.sql
@@ -0,0 +1,45 @@
+--
+-- Copyright 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
+--
+-- 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.
+
+-- sqlformat file off
+
+-- Propagates column values from root toward leaves using BFS.
+--
+-- For each spec, a new output column is created by copying the source column
+-- and then applying the aggregate operation downward through the tree.
+-- For each parent→child edge: output[child] = agg(output[parent], output[child]).
+--
+-- Each spec is a string of the form 'AGG(source_col) AS output_col' where AGG
+-- is one of SUM, MIN, MAX, FIRST, LAST. Case-insensitive.
+--
+-- Example usage:
+-- ```
+-- SELECT * FROM _tree_to_table!(
+-- _tree_propagate_down(
+-- _tree_from_table!((SELECT * FROM calls), (fn, ones)),
+-- 'SUM(ones) AS depth'
+-- ),
+-- (fn, depth)
+-- );
+-- ```
+CREATE PERFETTO FUNCTION _tree_propagate_down(
+ -- A TREE pointer from _tree_from_table or another tree operation.
+ tree_ptr ANY,
+ -- Propagation specs: 'AGG(source_col) AS output_col' (variadic)
+ specs ANY...
+)
+-- Returns a TREE pointer with the propagated columns added.
+RETURNS ANY
+DELEGATES TO __intrinsic_tree_propagate_down;
diff --git a/test/trace_processor/diff_tests/include_index.py b/test/trace_processor/diff_tests/include_index.py
index 4d7d45a..094de96 100644
--- a/test/trace_processor/diff_tests/include_index.py
+++ b/test/trace_processor/diff_tests/include_index.py
@@ -177,6 +177,7 @@
from diff_tests.stdlib.traced.stats import TracedStats
from diff_tests.stdlib.trees.table_conversion_tests import TreeRoundtrip
from diff_tests.stdlib.trees.tree_filter_tests import TreeFilter
+from diff_tests.stdlib.trees.tree_propagate_tests import TreePropagate
from diff_tests.stdlib.viz.tests import Viz
from diff_tests.stdlib.wattson.tests import WattsonStdlib
from diff_tests.syntax.filtering_tests import PerfettoFiltering
@@ -321,6 +322,7 @@
GraphScanTests,
TreeRoundtrip,
TreeFilter,
+ TreePropagate,
ExportTests,
Frames,
GraphSearchTests,
diff --git a/test/trace_processor/diff_tests/stdlib/trees/tree_propagate_tests.py b/test/trace_processor/diff_tests/stdlib/trees/tree_propagate_tests.py
new file mode 100644
index 0000000..8cf908b
--- /dev/null
+++ b/test/trace_processor/diff_tests/stdlib/trees/tree_propagate_tests.py
@@ -0,0 +1,354 @@
+#!/usr/bin/env python3
+# 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.
+
+from python.generators.diff_tests.testing import DataPath
+from python.generators.diff_tests.testing import Csv
+from python.generators.diff_tests.testing import DiffTestBlueprint
+from python.generators.diff_tests.testing import TestSuite
+
+
+class TreePropagate(TestSuite):
+ """Tests for tree propagate_down operations."""
+
+ def test_propagate_down_depth_sum(self):
+ """SUM(ones) AS depth computes depth: root=1, children=2, etc."""
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE std.trees.table_conversion;
+ INCLUDE PERFETTO MODULE std.trees.propagate;
+
+ CREATE PERFETTO TABLE calls AS
+ SELECT 1 AS id, NULL AS parent_id, 'main' AS fn, 1 AS ones
+ UNION ALL SELECT 2, 1, 'parse', 1
+ UNION ALL SELECT 3, 2, 'lex', 1
+ UNION ALL SELECT 4, 1, 'emit', 1
+ UNION ALL SELECT 5, 4, 'write', 1;
+
+ SELECT fn, depth
+ FROM _tree_to_table!(
+ _tree_propagate_down(
+ _tree_from_table!((SELECT * FROM calls), (fn, ones)),
+ 'SUM(ones) AS depth'
+ ),
+ (fn, depth)
+ )
+ ORDER BY fn;
+ """,
+ out=Csv("""
+ "fn","depth"
+ "emit",2
+ "lex",3
+ "main",1
+ "parse",2
+ "write",3
+ """))
+
+ def test_propagate_down_multiple_columns(self):
+ """Multiple specs in one call: SUM + MAX."""
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE std.trees.table_conversion;
+ INCLUDE PERFETTO MODULE std.trees.propagate;
+
+ CREATE PERFETTO TABLE calls AS
+ SELECT 1 AS id, NULL AS parent_id, 'main' AS fn, 1 AS ones, 10 AS prio
+ UNION ALL SELECT 2, 1, 'parse', 1, 5
+ UNION ALL SELECT 3, 2, 'lex', 1, 8
+ UNION ALL SELECT 4, 1, 'emit', 1, 3;
+
+ SELECT fn, depth, max_prio
+ FROM _tree_to_table!(
+ _tree_propagate_down(
+ _tree_from_table!((SELECT * FROM calls), (fn, ones, prio)),
+ 'SUM(ones) AS depth',
+ 'MAX(prio) AS max_prio'
+ ),
+ (fn, depth, max_prio)
+ )
+ ORDER BY fn;
+ """,
+ out=Csv("""
+ "fn","depth","max_prio"
+ "emit",2,10
+ "lex",3,10
+ "main",1,10
+ "parse",2,10
+ """))
+
+ def test_propagate_down_min(self):
+ """MIN propagation: each node gets min of its value and parent's propagated value."""
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE std.trees.table_conversion;
+ INCLUDE PERFETTO MODULE std.trees.propagate;
+
+ CREATE PERFETTO TABLE calls AS
+ SELECT 1 AS id, NULL AS parent_id, 'root' AS fn, 5 AS val
+ UNION ALL SELECT 2, 1, 'a', 10
+ UNION ALL SELECT 3, 2, 'b', 3
+ UNION ALL SELECT 4, 1, 'c', 2;
+
+ SELECT fn, min_val
+ FROM _tree_to_table!(
+ _tree_propagate_down(
+ _tree_from_table!((SELECT * FROM calls), (fn, val)),
+ 'MIN(val) AS min_val'
+ ),
+ (fn, min_val)
+ )
+ ORDER BY fn;
+ """,
+ out=Csv("""
+ "fn","min_val"
+ "a",5
+ "b",3
+ "c",2
+ "root",5
+ """))
+
+ def test_propagate_down_first(self):
+ """FIRST propagation: each node gets the root's value."""
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE std.trees.table_conversion;
+ INCLUDE PERFETTO MODULE std.trees.propagate;
+
+ CREATE PERFETTO TABLE calls AS
+ SELECT 1 AS id, NULL AS parent_id, 'root' AS fn, 100 AS val
+ UNION ALL SELECT 2, 1, 'a', 50
+ UNION ALL SELECT 3, 2, 'b', 25;
+
+ SELECT fn, first_val
+ FROM _tree_to_table!(
+ _tree_propagate_down(
+ _tree_from_table!((SELECT * FROM calls), (fn, val)),
+ 'FIRST(val) AS first_val'
+ ),
+ (fn, first_val)
+ )
+ ORDER BY fn;
+ """,
+ out=Csv("""
+ "fn","first_val"
+ "a",100
+ "b",100
+ "root",100
+ """))
+
+ def test_propagate_down_last(self):
+ """LAST propagation: each node keeps its own value (no-op)."""
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE std.trees.table_conversion;
+ INCLUDE PERFETTO MODULE std.trees.propagate;
+
+ CREATE PERFETTO TABLE calls AS
+ SELECT 1 AS id, NULL AS parent_id, 'root' AS fn, 100 AS val
+ UNION ALL SELECT 2, 1, 'a', 50
+ UNION ALL SELECT 3, 2, 'b', 25;
+
+ SELECT fn, last_val
+ FROM _tree_to_table!(
+ _tree_propagate_down(
+ _tree_from_table!((SELECT * FROM calls), (fn, val)),
+ 'LAST(val) AS last_val'
+ ),
+ (fn, last_val)
+ )
+ ORDER BY fn;
+ """,
+ out=Csv("""
+ "fn","last_val"
+ "a",50
+ "b",25
+ "root",100
+ """))
+
+ def test_propagate_down_after_filter(self):
+ """Propagation after filtering: filter first, then propagate depth."""
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE std.trees.table_conversion;
+ INCLUDE PERFETTO MODULE std.trees.filter;
+ INCLUDE PERFETTO MODULE std.trees.propagate;
+
+ CREATE PERFETTO TABLE calls AS
+ SELECT 1 AS id, NULL AS parent_id, 'main' AS fn, 100 AS dur, 1 AS ones
+ UNION ALL SELECT 2, 1, 'parse', 60, 1
+ UNION ALL SELECT 3, 2, 'lex', 30, 1
+ UNION ALL SELECT 4, 1, 'alloc', 5, 1
+ UNION ALL SELECT 5, 1, 'emit', 35, 1;
+
+ SELECT fn, depth
+ FROM _tree_to_table!(
+ _tree_propagate_down(
+ _tree_filter(
+ _tree_from_table!((SELECT * FROM calls), (fn, dur, ones)),
+ _tree_where(_tree_constraint('dur', '>=', 10))
+ ),
+ 'SUM(ones) AS depth'
+ ),
+ (fn, depth)
+ )
+ ORDER BY fn;
+ """,
+ out=Csv("""
+ "fn","depth"
+ "emit",2
+ "lex",3
+ "main",1
+ "parse",2
+ """))
+
+ def test_propagate_down_multiple_roots(self):
+ """Propagation with a forest (multiple roots)."""
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE std.trees.table_conversion;
+ INCLUDE PERFETTO MODULE std.trees.propagate;
+
+ CREATE PERFETTO TABLE calls AS
+ SELECT 1 AS id, NULL AS parent_id, 'tree1' AS fn, 1 AS ones
+ UNION ALL SELECT 2, 1, 'a', 1
+ UNION ALL SELECT 3, NULL, 'tree2', 1
+ UNION ALL SELECT 4, 3, 'b', 1;
+
+ SELECT fn, depth
+ FROM _tree_to_table!(
+ _tree_propagate_down(
+ _tree_from_table!((SELECT * FROM calls), (fn, ones)),
+ 'SUM(ones) AS depth'
+ ),
+ (fn, depth)
+ )
+ ORDER BY fn;
+ """,
+ out=Csv("""
+ "fn","depth"
+ "a",2
+ "b",2
+ "tree1",1
+ "tree2",1
+ """))
+
+ def test_propagate_down_single_node(self):
+ """Edge case: single-node tree."""
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE std.trees.table_conversion;
+ INCLUDE PERFETTO MODULE std.trees.propagate;
+
+ CREATE PERFETTO TABLE calls AS
+ SELECT 1 AS id, NULL AS parent_id, 'root' AS fn, 42 AS val;
+
+ SELECT fn, s
+ FROM _tree_to_table!(
+ _tree_propagate_down(
+ _tree_from_table!((SELECT * FROM calls), (fn, val)),
+ 'SUM(val) AS s'
+ ),
+ (fn, s)
+ )
+ ORDER BY fn;
+ """,
+ out=Csv("""
+ "fn","s"
+ "root",42
+ """))
+
+ def test_propagate_down_filter_then_propagate_then_filter(self):
+ """filter → propagate → filter(propagated_col) chain."""
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE std.trees.table_conversion;
+ INCLUDE PERFETTO MODULE std.trees.filter;
+ INCLUDE PERFETTO MODULE std.trees.propagate;
+
+ CREATE PERFETTO TABLE calls AS
+ SELECT 1 AS id, NULL AS parent_id, 'main' AS fn, 100 AS dur, 1 AS ones
+ UNION ALL SELECT 2, 1, 'parse', 60, 1
+ UNION ALL SELECT 3, 2, 'lex', 30, 1
+ UNION ALL SELECT 4, 1, 'alloc', 5, 1
+ UNION ALL SELECT 5, 1, 'emit', 35, 1;
+
+ -- Filter short calls, propagate depth, then filter depth >= 2.
+ SELECT fn, depth
+ FROM _tree_to_table!(
+ _tree_filter(
+ _tree_propagate_down(
+ _tree_filter(
+ _tree_from_table!((SELECT * FROM calls), (fn, dur, ones)),
+ _tree_where(_tree_constraint('dur', '>=', 10))
+ ),
+ 'SUM(ones) AS depth'
+ ),
+ _tree_where(_tree_constraint('depth', '>=', 2))
+ ),
+ (fn, depth)
+ )
+ ORDER BY fn;
+ """,
+ out=Csv("""
+ "fn","depth"
+ "emit",2
+ "lex",3
+ "parse",2
+ """))
+
+ def test_propagate_down_chained(self):
+ """Chained propagation: use output of first propagation as source."""
+ return DiffTestBlueprint(
+ trace=DataPath('counters.json'),
+ query="""
+ INCLUDE PERFETTO MODULE std.trees.table_conversion;
+ INCLUDE PERFETTO MODULE std.trees.propagate;
+
+ CREATE PERFETTO TABLE calls AS
+ SELECT 1 AS id, NULL AS parent_id, 'main' AS fn, 1 AS ones
+ UNION ALL SELECT 2, 1, 'parse', 1
+ UNION ALL SELECT 3, 2, 'lex', 1
+ UNION ALL SELECT 4, 1, 'emit', 1;
+
+ -- First propagation: SUM(ones) AS depth -> 1,2,3,2
+ -- Second propagation: SUM(depth) AS cumulative_depth -> 1,3,6,3
+ SELECT fn, depth, cumulative_depth
+ FROM _tree_to_table!(
+ _tree_propagate_down(
+ _tree_propagate_down(
+ _tree_from_table!((SELECT * FROM calls), (fn, ones)),
+ 'SUM(ones) AS depth'
+ ),
+ 'SUM(depth) AS cumulative_depth'
+ ),
+ (fn, depth, cumulative_depth)
+ )
+ ORDER BY fn;
+ """,
+ out=Csv("""
+ "fn","depth","cumulative_depth"
+ "emit",2,3
+ "lex",3,6
+ "main",1,1
+ "parse",2,3
+ """))
