Merge "tp: Implement interval intersect prototype" into main
diff --git a/Android.bp b/Android.bp
index e9d7c45..d9971c4 100644
--- a/Android.bp
+++ b/Android.bp
@@ -11939,6 +11939,7 @@
"src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_sched_upid.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_slice_layout.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/flamegraph_construction_algorithms.cc",
+ "src/trace_processor/perfetto_sql/intrinsics/table_functions/interval_intersect.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/table_info.cc",
],
}
@@ -12065,6 +12066,7 @@
"src/trace_processor/perfetto_sql/stdlib/deprecated/v42/common/timestamps.sql",
"src/trace_processor/perfetto_sql/stdlib/graphs/dominator_tree.sql",
"src/trace_processor/perfetto_sql/stdlib/graphs/search.sql",
+ "src/trace_processor/perfetto_sql/stdlib/intervals/intersect.sql",
"src/trace_processor/perfetto_sql/stdlib/intervals/overlap.sql",
"src/trace_processor/perfetto_sql/stdlib/linux/cpu_idle.sql",
"src/trace_processor/perfetto_sql/stdlib/memory/heap_graph_dominator_tree.sql",
diff --git a/BUILD b/BUILD
index 84baca4..3496afc 100644
--- a/BUILD
+++ b/BUILD
@@ -2314,6 +2314,8 @@
"src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_slice_layout.h",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/flamegraph_construction_algorithms.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/flamegraph_construction_algorithms.h",
+ "src/trace_processor/perfetto_sql/intrinsics/table_functions/interval_intersect.cc",
+ "src/trace_processor/perfetto_sql/intrinsics/table_functions/interval_intersect.h",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/table_info.cc",
"src/trace_processor/perfetto_sql/intrinsics/table_functions/table_info.h",
],
@@ -2461,6 +2463,7 @@
perfetto_filegroup(
name = "src_trace_processor_perfetto_sql_stdlib_intervals_intervals",
srcs = [
+ "src/trace_processor/perfetto_sql/stdlib/intervals/intersect.sql",
"src/trace_processor/perfetto_sql/stdlib/intervals/overlap.sql",
],
)
diff --git a/python/generators/sql_processing/utils.py b/python/generators/sql_processing/utils.py
index 539115e..1a76e1f 100644
--- a/python/generators/sql_processing/utils.py
+++ b/python/generators/sql_processing/utils.py
@@ -110,6 +110,7 @@
ALLOWED_PREFIXES = {
'counters': 'counter',
'chrome/util': 'cr',
+ 'intervals': 'interval',
'graphs': 'graph',
'slices': 'slice'
}
diff --git a/src/trace_processor/perfetto_sql/intrinsics/table_functions/BUILD.gn b/src/trace_processor/perfetto_sql/intrinsics/table_functions/BUILD.gn
index 631942d..6edd50b 100644
--- a/src/trace_processor/perfetto_sql/intrinsics/table_functions/BUILD.gn
+++ b/src/trace_processor/perfetto_sql/intrinsics/table_functions/BUILD.gn
@@ -43,6 +43,8 @@
"experimental_slice_layout.h",
"flamegraph_construction_algorithms.cc",
"flamegraph_construction_algorithms.h",
+ "interval_intersect.cc",
+ "interval_intersect.h",
"table_info.cc",
"table_info.h",
]
diff --git a/src/trace_processor/perfetto_sql/intrinsics/table_functions/interval_intersect.cc b/src/trace_processor/perfetto_sql/intrinsics/table_functions/interval_intersect.cc
new file mode 100644
index 0000000..db83694
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/intrinsics/table_functions/interval_intersect.cc
@@ -0,0 +1,218 @@
+/*
+ * Copyright (C) 2024 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/table_functions/interval_intersect.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <optional>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "perfetto/base/compiler.h"
+#include "perfetto/base/logging.h"
+#include "perfetto/base/status.h"
+#include "perfetto/ext/base/status_or.h"
+#include "perfetto/protozero/proto_decoder.h"
+#include "perfetto/protozero/proto_utils.h"
+#include "perfetto/trace_processor/basic_types.h"
+#include "perfetto/trace_processor/status.h"
+#include "protos/perfetto/trace_processor/metrics_impl.pbzero.h"
+#include "src/trace_processor/containers/string_pool.h"
+#include "src/trace_processor/db/column.h"
+#include "src/trace_processor/db/table.h"
+#include "src/trace_processor/perfetto_sql/intrinsics/table_functions/tables_py.h"
+#include "src/trace_processor/util/status_macros.h"
+
+namespace perfetto::trace_processor {
+namespace tables {
+IntervalIntersectTable::~IntervalIntersectTable() = default;
+} // namespace tables
+
+namespace {
+
+using RepeatedDecoder = protos::pbzero::RepeatedBuilderResult::Decoder;
+using RepeatedIter = ::protozero::PackedRepeatedFieldIterator<
+ ::protozero::proto_utils::ProtoWireType::kFixed64,
+ int64_t>;
+
+base::StatusOr<RepeatedIter> DecodeArgument(const SqlValue& raw_arg,
+ const char* debug_name,
+ bool& parse_error) {
+ if (raw_arg.type != SqlValue::kBytes) {
+ return base::ErrStatus(
+ "interval_intersect: '%s' should be a repeated field", debug_name);
+ }
+ protos::pbzero::ProtoBuilderResult::Decoder proto_arg(
+ static_cast<const uint8_t*>(raw_arg.AsBytes()), raw_arg.bytes_count);
+ if (!proto_arg.is_repeated()) {
+ return base::ErrStatus(
+ "interval_intersect: '%s' is not generated by RepeatedField "
+ "function",
+ debug_name);
+ }
+
+ auto iter =
+ protos::pbzero::RepeatedBuilderResult::Decoder(proto_arg.repeated())
+ .int_values(&parse_error);
+ if (parse_error) {
+ return base::ErrStatus(
+ "interval_intersect: error when parsing '%s' values.", debug_name);
+ }
+
+ return iter;
+}
+
+struct Interval {
+ int64_t id;
+ int64_t ts;
+ int64_t dur;
+
+ int64_t end() { return ts + dur; }
+};
+
+struct IntervalsIterator {
+ RepeatedIter ids;
+ RepeatedIter tses;
+ RepeatedIter durs;
+
+ static base::StatusOr<IntervalsIterator> Create(
+ const SqlValue& raw_ids,
+ const SqlValue& raw_timestamps,
+ const SqlValue& raw_durs,
+ bool& parse_error) {
+ ASSIGN_OR_RETURN(RepeatedIter ids,
+ DecodeArgument(raw_ids, "ids", parse_error));
+ ASSIGN_OR_RETURN(RepeatedIter tses,
+ DecodeArgument(raw_timestamps, "timestamps", parse_error));
+ ASSIGN_OR_RETURN(RepeatedIter durs,
+ DecodeArgument(raw_durs, "durations", parse_error));
+
+ return IntervalsIterator{ids, tses, durs};
+ }
+
+ void operator++() {
+ PERFETTO_DCHECK(ids && tses && durs);
+ ids++;
+ tses++;
+ durs++;
+ }
+
+ Interval operator*() const { return Interval{*ids, *tses, *durs}; }
+
+ explicit operator bool() const { return bool(ids); }
+};
+
+} // namespace
+IntervalIntersect::IntervalIntersect(StringPool* pool) : pool_(pool) {}
+IntervalIntersect::~IntervalIntersect() = default;
+
+Table::Schema IntervalIntersect::CreateSchema() {
+ return tables::IntervalIntersectTable::ComputeStaticSchema();
+}
+
+std::string IntervalIntersect::TableName() {
+ return tables::IntervalIntersectTable::Name();
+}
+
+uint32_t IntervalIntersect::EstimateRowCount() {
+ // TODO(mayzner): Give proper estimate.
+ return 1024;
+}
+
+base::StatusOr<std::unique_ptr<Table>> IntervalIntersect::ComputeTable(
+ const std::vector<SqlValue>& arguments) {
+ PERFETTO_DCHECK(arguments.size() == 6);
+
+ bool parse_error = false;
+ ASSIGN_OR_RETURN(IntervalsIterator l_it,
+ IntervalsIterator::Create(arguments[0], arguments[1],
+ arguments[2], parse_error));
+ ASSIGN_OR_RETURN(IntervalsIterator r_it,
+ IntervalsIterator::Create(arguments[3], arguments[4],
+ arguments[5], parse_error));
+
+ // If there are no intervals in one of the tables then there are no intervals
+ // returned.
+ if (!l_it || !r_it) {
+ return std::unique_ptr<Table>(
+ std::make_unique<tables::IntervalIntersectTable>(pool_));
+ }
+
+ // We copy |l_it| and |r_it| for the second for loop.
+ IntervalsIterator l_it_2 = l_it;
+ IntervalsIterator r_it_2 = r_it;
+
+ auto table = std::make_unique<tables::IntervalIntersectTable>(pool_);
+
+ // Find all intersections where interval from right table started duringan
+ // interval from left table.
+ for (Interval l_i = *l_it; l_it && r_it && !parse_error;
+ ++l_it, l_i = *l_it) {
+ // If the next |r_i| starts after |l_i| ends, that means that we need to
+ // go the the next |l_i|, so we need to exit the loop.
+ for (Interval r_i = *r_it; r_it && r_i.ts < l_i.end() && !parse_error;
+ ++r_it, r_i = *r_it) {
+ // We already know (because we are in the loop) that |r_i| started before
+ // |l_i| ended, we should not intersect only if |r_i| started before
+ // |l_i|.
+ if (r_i.ts < l_i.ts) {
+ continue;
+ }
+
+ tables::IntervalIntersectTable::Row row;
+ row.ts = static_cast<uint32_t>(std::max(r_i.ts, l_i.ts));
+ row.dur = static_cast<uint32_t>(std::min(r_i.end(), l_i.end())) - row.ts;
+ row.left_id = static_cast<uint32_t>(l_i.id);
+ row.right_id = static_cast<uint32_t>(r_i.id);
+ table->Insert(row);
+ }
+ }
+
+ // Find all intersections where interval from the left table started during an
+ // interval from right table.
+ for (Interval r_i = *r_it_2; r_it_2 && l_it_2 && !parse_error;
+ ++r_it_2, r_i = *r_it_2) {
+ for (Interval l_i = *l_it_2; l_it_2 && l_i.ts < r_i.end() && !parse_error;
+ ++l_it_2, l_i = *l_it_2) {
+ // The only difference between this and above algorithm is not
+ // intersecting if the intervals started at the same time. We do this to
+ // prevent double counting intervals.
+ if (l_i.ts <= r_i.ts) {
+ continue;
+ }
+
+ tables::IntervalIntersectTable::Row row;
+ row.ts = static_cast<uint32_t>(std::max(r_i.ts, l_i.ts));
+ row.dur = static_cast<uint32_t>(std::min(r_i.end(), l_i.end())) - row.ts;
+ row.left_id = static_cast<uint32_t>(l_i.id);
+ row.right_id = static_cast<uint32_t>(r_i.id);
+ table->Insert(row);
+ }
+ }
+
+ if (parse_error) {
+ return base::ErrStatus(
+ "interval_intersect: Error in parsing of one of the arguments.");
+ }
+
+ return std::unique_ptr<Table>(std::move(table));
+}
+
+} // namespace perfetto::trace_processor
diff --git a/src/trace_processor/perfetto_sql/intrinsics/table_functions/interval_intersect.h b/src/trace_processor/perfetto_sql/intrinsics/table_functions/interval_intersect.h
new file mode 100644
index 0000000..ec8ccdf
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/intrinsics/table_functions/interval_intersect.h
@@ -0,0 +1,83 @@
+/*
+ * Copyright (C) 2024 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_TABLE_FUNCTIONS_INTERVAL_INTERSECT_H_
+#define SRC_TRACE_PROCESSOR_PERFETTO_SQL_INTRINSICS_TABLE_FUNCTIONS_INTERVAL_INTERSECT_H_
+
+#include <cstdint>
+#include <memory>
+#include <string>
+#include <vector>
+
+#include "perfetto/ext/base/status_or.h"
+#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/string_pool.h"
+#include "src/trace_processor/db/table.h"
+#include "src/trace_processor/perfetto_sql/intrinsics/table_functions/static_table_function.h"
+
+namespace perfetto::trace_processor {
+
+// An SQL table-function which computes the intersection of intervals from two
+// tables.
+//
+// Given two sets of sorted non-overlapping intervals (with id, timestamp and
+// duration) returns intervals that are intersections between those two sets,
+// with ids to state what intervals are intersected.
+//
+// LEFT . - - - - - - .
+// RIGHT - - . - - . - -
+// Intersection . - . - - . - .
+//
+// Arguments are RepeatedBuilderResult protos containing a column of
+// numerics values:
+// 1) |in_left_ids|(uint32_t): Ids from the left table.
+// 2) |in_left_tses|(uint64_t): Timestamps (starts) of intervals from
+// the left table.
+// 3) |in_left_durs|(uint64_t): Durations of intervals
+// from the left table.
+// 4) |in_right_ids|(uint32_t): Ids from the right table.
+// 5) |in_right_tses|(uint64_t): Timestamps (starts) of intervals
+// from the right table.
+// 6) |in_right_durs|(uint64_t): Durations of intervals from the right table.
+//
+// NOTES:
+// - The first 3 arguments have to have the same number of values.
+// - Timestamps in left and right columns have to be sorted.
+//
+// Returns:
+// 1) |ts|: Start of the intersection.
+// 2) |dur|: Duration of the intersection.
+// 3) |left_id|: Id of the slice that was intersected in the first table.
+// 4) |right_id|: Id of the slice that was intersected in the second table.
+class IntervalIntersect : public StaticTableFunction {
+ public:
+ explicit IntervalIntersect(StringPool*);
+ virtual ~IntervalIntersect() override;
+
+ // StaticTableFunction implementation.
+ Table::Schema CreateSchema() override;
+ std::string TableName() override;
+ uint32_t EstimateRowCount() override;
+ base::StatusOr<std::unique_ptr<Table>> ComputeTable(
+ const std::vector<SqlValue>& arguments) override;
+
+ private:
+ StringPool* pool_;
+};
+
+} // namespace perfetto::trace_processor
+
+#endif // SRC_TRACE_PROCESSOR_PERFETTO_SQL_INTRINSICS_TABLE_FUNCTIONS_INTERVAL_INTERSECT_H_
diff --git a/src/trace_processor/perfetto_sql/intrinsics/table_functions/tables.py b/src/trace_processor/perfetto_sql/intrinsics/table_functions/tables.py
index f71ab9c..3c86e50 100644
--- a/src/trace_processor/perfetto_sql/intrinsics/table_functions/tables.py
+++ b/src/trace_processor/perfetto_sql/intrinsics/table_functions/tables.py
@@ -170,6 +170,23 @@
flags=ColumnFlag.HIDDEN),
])
+INTERVAL_INTERSECT_TABLE = Table(
+ python_module=__file__,
+ class_name="IntervalIntersectTable",
+ sql_name="__intrinsic_interval_intersect",
+ columns=[
+ C("ts", CppInt64()),
+ C("dur", CppInt64()),
+ C("left_id", CppUint32()),
+ C("right_id", CppUint32()),
+ C("in_left_ids", CppOptional(CppString()), flags=ColumnFlag.HIDDEN),
+ C("in_left_tses", CppOptional(CppString()), flags=ColumnFlag.HIDDEN),
+ C("in_left_durs", CppOptional(CppString()), flags=ColumnFlag.HIDDEN),
+ C("in_right_ids", CppOptional(CppString()), flags=ColumnFlag.HIDDEN),
+ C("in_right_tses", CppOptional(CppString()), flags=ColumnFlag.HIDDEN),
+ C("in_right_durs", CppOptional(CppString()), flags=ColumnFlag.HIDDEN),
+ ])
+
# Keep this list sorted.
ALL_TABLES = [
ANCESTOR_SLICE_BY_STACK_TABLE,
@@ -184,5 +201,6 @@
EXPERIMENTAL_COUNTER_DUR_TABLE,
EXPERIMENTAL_SCHED_UPID_TABLE,
EXPERIMENTAL_SLICE_LAYOUT_TABLE,
+ INTERVAL_INTERSECT_TABLE,
TABLE_INFO_TABLE,
]
diff --git a/src/trace_processor/perfetto_sql/stdlib/intervals/BUILD.gn b/src/trace_processor/perfetto_sql/stdlib/intervals/BUILD.gn
index dcac571..e9e22e9 100644
--- a/src/trace_processor/perfetto_sql/stdlib/intervals/BUILD.gn
+++ b/src/trace_processor/perfetto_sql/stdlib/intervals/BUILD.gn
@@ -15,5 +15,8 @@
import("../../../../../gn/perfetto_sql.gni")
perfetto_sql_source_set("intervals") {
- sources = [ "overlap.sql" ]
+ sources = [
+ "intersect.sql",
+ "overlap.sql",
+ ]
}
diff --git a/src/trace_processor/perfetto_sql/stdlib/intervals/intersect.sql b/src/trace_processor/perfetto_sql/stdlib/intervals/intersect.sql
new file mode 100644
index 0000000..b48aec6
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/stdlib/intervals/intersect.sql
@@ -0,0 +1,34 @@
+--
+-- Copyright 2024 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.
+
+CREATE PERFETTO MACRO _interval_intersect(
+ left_table TableOrSubquery,
+ right_table TableOrSubquery
+)
+RETURNS TableOrSubquery AS
+(
+ WITH
+ __temp_left_table AS (SELECT * FROM $left_table ORDER BY ts),
+ __temp_right_table AS (SELECT * FROM $right_table ORDER BY ts)
+ SELECT ii.ts, ii.dur, ii.left_id, ii.right_id
+ FROM __intrinsic_interval_intersect(
+ (SELECT RepeatedField(id) FROM __temp_left_table),
+ (SELECT RepeatedField(ts) FROM __temp_left_table),
+ (SELECT RepeatedField(dur) FROM __temp_left_table),
+ (SELECT RepeatedField(id) FROM __temp_right_table),
+ (SELECT RepeatedField(ts) FROM __temp_right_table),
+ (SELECT RepeatedField(dur) FROM __temp_right_table)
+ ) ii
+);
diff --git a/src/trace_processor/perfetto_sql/stdlib/prelude/slices.sql b/src/trace_processor/perfetto_sql/stdlib/prelude/slices.sql
index 24f470a..6c58c60 100644
--- a/src/trace_processor/perfetto_sql/stdlib/prelude/slices.sql
+++ b/src/trace_processor/perfetto_sql/stdlib/prelude/slices.sql
@@ -29,39 +29,4 @@
FROM slice ancestor
JOIN slice descendant
WHERE ancestor.id = $ancestor_id
- AND descendant.id = $descendant_id;
-
-CREATE PERFETTO MACRO _interval_intersect(
- left_table TableOrSubquery,
- right_table TableOrSubquery
-)
-RETURNS TableOrSubquery AS
-(
- WITH on_left AS (
- SELECT
- B.ts,
- IIF(
- A.ts + A.dur <= B.ts + B.dur,
- A.ts + A.dur - B.ts, B.dur) AS dur,
- A.id AS left_id,
- B.id as right_id
- FROM $left_table A
- JOIN $right_table B ON (A.ts <= B.ts AND A.ts + A.dur > B.ts)
- ), on_right AS (
- SELECT
- B.ts,
- IIF(
- A.ts + A.dur <= B.ts + B.dur,
- A.ts + A.dur - B.ts, B.dur) AS dur,
- B.id as left_id,
- A.id AS right_id
- FROM $right_table A
- -- The difference between this table and on_left is the lack of equality on
- -- A.ts <= B.ts. This is to remove the issue of double accounting
- -- timestamps that start at the same time.
- JOIN $left_table B ON (A.ts < B.ts AND A.ts + A.dur > B.ts)
- )
- SELECT * FROM on_left
- UNION ALL
- SELECT * FROM on_right
-);
\ No newline at end of file
+ AND descendant.id = $descendant_id;
\ No newline at end of file
diff --git a/src/trace_processor/trace_processor_impl.cc b/src/trace_processor/trace_processor_impl.cc
index 02bc3ae..08ec0d3 100644
--- a/src/trace_processor/trace_processor_impl.cc
+++ b/src/trace_processor/trace_processor_impl.cc
@@ -78,6 +78,7 @@
#include "src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_flat_slice.h"
#include "src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_sched_upid.h"
#include "src/trace_processor/perfetto_sql/intrinsics/table_functions/experimental_slice_layout.h"
+#include "src/trace_processor/perfetto_sql/intrinsics/table_functions/interval_intersect.h"
#include "src/trace_processor/perfetto_sql/intrinsics/table_functions/table_info.h"
#include "src/trace_processor/perfetto_sql/prelude/tables_views.h"
#include "src/trace_processor/perfetto_sql/stdlib/stdlib.h"
@@ -883,6 +884,8 @@
new ExperimentalFlatSlice(&context_)));
engine_->RegisterStaticTableFunction(
std::make_unique<DominatorTree>(context_.storage->mutable_string_pool()));
+ engine_->RegisterStaticTableFunction(std::make_unique<IntervalIntersect>(
+ context_.storage->mutable_string_pool()));
engine_->RegisterStaticTableFunction(
std::make_unique<Dfs>(context_.storage->mutable_string_pool()));
diff --git a/test/trace_processor/diff_tests/include_index.py b/test/trace_processor/diff_tests/include_index.py
index a5347cf..7da78d7 100644
--- a/test/trace_processor/diff_tests/include_index.py
+++ b/test/trace_processor/diff_tests/include_index.py
@@ -99,6 +99,7 @@
from diff_tests.stdlib.counters.tests import StdlibCounterIntervals
from diff_tests.stdlib.dynamic_tables.tests import DynamicTables
from diff_tests.stdlib.intervals.tests import StdlibIntervals
+from diff_tests.stdlib.intervals.intersect_tests import IntervalsIntersect
from diff_tests.stdlib.graphs.dominator_tree_tests import DominatorTree
from diff_tests.stdlib.graphs.search_tests import GraphSearchTests
from diff_tests.stdlib.linux.tests import LinuxStdlib
@@ -274,7 +275,9 @@
*SpanJoinSmoke(index_path, 'stdlib/span_join', 'SpanJoinSmoke').fetch(),
*StdlibCommon(index_path, 'stdlib/common', 'StdlibCommon').fetch(),
*StdlibIntervals(index_path, 'stdlib/intervals',
- 'StdlibIntervals').fetch(),
+ 'StdlibIntervalsIntersect').fetch(),
+ *IntervalsIntersect(index_path, 'stdlib/intervals',
+ 'StdlibIntervals').fetch(),
*Timestamps(index_path, 'stdlib/timestamps', 'Timestamps').fetch(),
] + chrome_stdlib_tests
diff --git a/test/trace_processor/diff_tests/stdlib/intervals/intersect_tests.py b/test/trace_processor/diff_tests/stdlib/intervals/intersect_tests.py
new file mode 100644
index 0000000..b6e1500
--- /dev/null
+++ b/test/trace_processor/diff_tests/stdlib/intervals/intersect_tests.py
@@ -0,0 +1,220 @@
+#!/usr/bin/env python3
+# Copyright (C) 2024 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 a
+#
+# 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 Path, DataPath, Metric
+from python.generators.diff_tests.testing import Csv, Json, TextProto
+from python.generators.diff_tests.testing import DiffTestBlueprint
+from python.generators.diff_tests.testing import TestSuite
+
+
+class IntervalsIntersect(TestSuite):
+
+ def test_simple_inteval_intersect(self):
+ return DiffTestBlueprint(
+ trace=TextProto(""),
+ # 0 1 2 3 4 5 6 7
+ # A: _ - - - - - - _
+ # B: - - _ - - _ - -
+ # res: _ - _ - - _ - _
+ query="""
+ INCLUDE PERFETTO MODULE intervals.intersect;
+
+ CREATE PERFETTO TABLE A AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 1, 6)
+ )
+ SELECT * FROM data;
+
+ CREATE PERFETTO TABLE B AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 0, 2),
+ (1, 3, 2),
+ (2, 6, 2)
+ )
+ SELECT * FROM data;
+
+ SELECT ts, dur, left_id, right_id
+ FROM _interval_intersect!(A, B)
+ ORDER BY ts;
+ """,
+ out=Csv("""
+ "ts","dur","left_id","right_id"
+ 1,1,0,0
+ 3,2,0,1
+ 6,1,0,2
+ """))
+
+ def test_simple_inteval_intersect_rev(self):
+ return DiffTestBlueprint(
+ trace=TextProto(""),
+ # 0 1 2 3 4 5 6 7
+ # A: _ - - - - - - _
+ # B: - - _ - - _ - -
+ # res: _ - _ - - _ - _
+ query="""
+ INCLUDE PERFETTO MODULE intervals.intersect;
+
+ CREATE PERFETTO TABLE A AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 1, 6)
+ )
+ SELECT * FROM data;
+
+ CREATE PERFETTO TABLE B AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 0, 2),
+ (1, 3, 2),
+ (2, 6, 2)
+ )
+ SELECT * FROM data;
+
+ SELECT ts, dur, left_id, right_id
+ FROM _interval_intersect!(B, A)
+ ORDER BY ts;
+ """,
+ out=Csv("""
+ "ts","dur","left_id","right_id"
+ 1,1,0,0
+ 3,2,1,0
+ 6,1,2,0
+ """))
+
+ def test_no_overlap(self):
+ return DiffTestBlueprint(
+ trace=TextProto(""),
+ # A: __-
+ # B: -__
+ # res: ___
+ query="""
+ INCLUDE PERFETTO MODULE intervals.intersect;
+
+ CREATE PERFETTO TABLE A AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 2, 1)
+ )
+ SELECT * FROM data;
+
+ CREATE PERFETTO TABLE B AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 0, 1)
+ )
+ SELECT * FROM data;
+
+ SELECT ts, dur, left_id, right_id
+ FROM _interval_intersect!(A, B)
+ ORDER BY ts;
+ """,
+ out=Csv("""
+ "ts","dur","left_id","right_id"
+ """))
+
+ def test_no_overlap_rev(self):
+ return DiffTestBlueprint(
+ trace=TextProto(""),
+ # A: __-
+ # B: -__
+ # res: ___
+ query="""
+ INCLUDE PERFETTO MODULE intervals.intersect;
+
+ CREATE PERFETTO TABLE A AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 2, 1)
+ )
+ SELECT * FROM data;
+
+ CREATE PERFETTO TABLE B AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 0, 1)
+ )
+ SELECT * FROM data;
+
+ SELECT ts, dur, left_id, right_id
+ FROM _interval_intersect!(B, A)
+ ORDER BY ts;
+ """,
+ out=Csv("""
+ "ts","dur","left_id","right_id"
+ """))
+
+ def test_single_point_overlap(self):
+ return DiffTestBlueprint(
+ trace=TextProto(""),
+ # A: _-
+ # B: -_
+ # res: __
+ query="""
+ INCLUDE PERFETTO MODULE intervals.intersect;
+
+ CREATE PERFETTO TABLE A AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 1, 1)
+ )
+ SELECT * FROM data;
+
+ CREATE PERFETTO TABLE B AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 0, 1)
+ )
+ SELECT * FROM data;
+
+ SELECT ts, dur, left_id, right_id
+ FROM _interval_intersect!(A, B)
+ ORDER BY ts;
+ """,
+ out=Csv("""
+ "ts","dur","left_id","right_id"
+ """))
+
+ def test_single_point_overlap_rev(self):
+ return DiffTestBlueprint(
+ trace=TextProto(""),
+ # A: _-
+ # B: -_
+ # res: __
+ query="""
+ INCLUDE PERFETTO MODULE intervals.intersect;
+
+ CREATE PERFETTO TABLE A AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 1, 1)
+ )
+ SELECT * FROM data;
+
+ CREATE PERFETTO TABLE B AS
+ WITH data(id, ts, dur) AS (
+ VALUES
+ (0, 0, 1)
+ )
+ SELECT * FROM data;
+
+ SELECT ts, dur, left_id, right_id
+ FROM _interval_intersect!(B, A)
+ ORDER BY ts;
+ """,
+ out=Csv("""
+ "ts","dur","left_id","right_id"
+ """))
\ No newline at end of file
