1 /*
2 * Copyright (C) 2024 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "src/trace_processor/perfetto_sql/intrinsics/table_functions/interval_intersect.h"
18
19 #include <algorithm>
20 #include <cstddef>
21 #include <cstdint>
22 #include <memory>
23 #include <optional>
24 #include <string>
25 #include <utility>
26 #include <vector>
27
28 #include "perfetto/base/compiler.h"
29 #include "perfetto/base/logging.h"
30 #include "perfetto/base/status.h"
31 #include "perfetto/ext/base/status_or.h"
32 #include "perfetto/protozero/proto_decoder.h"
33 #include "perfetto/protozero/proto_utils.h"
34 #include "perfetto/trace_processor/basic_types.h"
35 #include "perfetto/trace_processor/status.h"
36 #include "protos/perfetto/trace_processor/metrics_impl.pbzero.h"
37 #include "src/trace_processor/containers/string_pool.h"
38 #include "src/trace_processor/db/column.h"
39 #include "src/trace_processor/db/table.h"
40 #include "src/trace_processor/perfetto_sql/intrinsics/table_functions/tables_py.h"
41 #include "src/trace_processor/util/status_macros.h"
42
43 namespace perfetto::trace_processor {
44 namespace tables {
45 IntervalIntersectTable::~IntervalIntersectTable() = default;
46 } // namespace tables
47
48 namespace {
49
50 using RepeatedDecoder = protos::pbzero::RepeatedBuilderResult::Decoder;
51 using RepeatedIter = ::protozero::PackedRepeatedFieldIterator<
52 ::protozero::proto_utils::ProtoWireType::kFixed64,
53 int64_t>;
54
DecodeArgument(const SqlValue & raw_arg,const char * debug_name,bool & parse_error)55 base::StatusOr<RepeatedIter> DecodeArgument(const SqlValue& raw_arg,
56 const char* debug_name,
57 bool& parse_error) {
58 if (raw_arg.type != SqlValue::kBytes) {
59 return base::ErrStatus(
60 "interval_intersect: '%s' should be a repeated field", debug_name);
61 }
62 protos::pbzero::ProtoBuilderResult::Decoder proto_arg(
63 static_cast<const uint8_t*>(raw_arg.AsBytes()), raw_arg.bytes_count);
64 if (!proto_arg.is_repeated()) {
65 return base::ErrStatus(
66 "interval_intersect: '%s' is not generated by RepeatedField "
67 "function",
68 debug_name);
69 }
70
71 auto iter =
72 protos::pbzero::RepeatedBuilderResult::Decoder(proto_arg.repeated())
73 .int_values(&parse_error);
74 if (parse_error) {
75 return base::ErrStatus(
76 "interval_intersect: error when parsing '%s' values.", debug_name);
77 }
78
79 return iter;
80 }
81
82 struct Interval {
83 int64_t id;
84 int64_t ts;
85 int64_t dur;
86
endperfetto::trace_processor::__anon51ccfb050111::Interval87 int64_t end() { return ts + dur; }
88 };
89
90 struct IntervalsIterator {
91 RepeatedIter ids;
92 RepeatedIter tses;
93 RepeatedIter durs;
94
Createperfetto::trace_processor::__anon51ccfb050111::IntervalsIterator95 static base::StatusOr<IntervalsIterator> Create(
96 const SqlValue& raw_ids,
97 const SqlValue& raw_timestamps,
98 const SqlValue& raw_durs,
99 bool& parse_error) {
100 ASSIGN_OR_RETURN(RepeatedIter ids,
101 DecodeArgument(raw_ids, "ids", parse_error));
102 ASSIGN_OR_RETURN(RepeatedIter tses,
103 DecodeArgument(raw_timestamps, "timestamps", parse_error));
104 ASSIGN_OR_RETURN(RepeatedIter durs,
105 DecodeArgument(raw_durs, "durations", parse_error));
106
107 return IntervalsIterator{ids, tses, durs};
108 }
109
operator ++perfetto::trace_processor::__anon51ccfb050111::IntervalsIterator110 void operator++() {
111 PERFETTO_DCHECK(ids && tses && durs);
112 ids++;
113 tses++;
114 durs++;
115 }
116
operator *perfetto::trace_processor::__anon51ccfb050111::IntervalsIterator117 Interval operator*() const { return Interval{*ids, *tses, *durs}; }
118
operator boolperfetto::trace_processor::__anon51ccfb050111::IntervalsIterator119 explicit operator bool() const { return bool(ids); }
120 };
121
122 } // namespace
IntervalIntersect(StringPool * pool)123 IntervalIntersect::IntervalIntersect(StringPool* pool) : pool_(pool) {}
124 IntervalIntersect::~IntervalIntersect() = default;
125
CreateSchema()126 Table::Schema IntervalIntersect::CreateSchema() {
127 return tables::IntervalIntersectTable::ComputeStaticSchema();
128 }
129
TableName()130 std::string IntervalIntersect::TableName() {
131 return tables::IntervalIntersectTable::Name();
132 }
133
EstimateRowCount()134 uint32_t IntervalIntersect::EstimateRowCount() {
135 // TODO(mayzner): Give proper estimate.
136 return 1024;
137 }
138
ComputeTable(const std::vector<SqlValue> & args)139 base::StatusOr<std::unique_ptr<Table>> IntervalIntersect::ComputeTable(
140 const std::vector<SqlValue>& args) {
141 PERFETTO_DCHECK(args.size() == 6);
142
143 // If either of the provided sets of columns is empty return.
144 auto pred = [](const SqlValue& val) { return val.is_null(); };
145 if (std::any_of(args.begin(), args.end(), pred)) {
146 // We expect that either all left table values are empty or all right table
147 // values are empty.
148 if (std::all_of(args.begin(), args.begin() + 3, pred) ||
149 std::all_of(args.begin() + 3, args.begin() + 6, pred)) {
150 return std::unique_ptr<Table>(
151 std::make_unique<tables::IntervalIntersectTable>(pool_));
152 }
153 return base::ErrStatus(
154 "interval_intersect: not all of the arguments of one of the tables are "
155 "null");
156 }
157
158 bool parse_error = false;
159 ASSIGN_OR_RETURN(
160 IntervalsIterator l_it,
161 IntervalsIterator::Create(args[0], args[1], args[2], parse_error));
162 ASSIGN_OR_RETURN(
163 IntervalsIterator r_it,
164 IntervalsIterator::Create(args[3], args[4], args[5], parse_error));
165
166 // If there are no intervals in one of the tables then there are no intervals
167 // returned.
168 if (!l_it || !r_it) {
169 return std::unique_ptr<Table>(
170 std::make_unique<tables::IntervalIntersectTable>(pool_));
171 }
172
173 // We copy |l_it| and |r_it| for the second for loop.
174 IntervalsIterator l_it_2 = l_it;
175 IntervalsIterator r_it_2 = r_it;
176
177 auto table = std::make_unique<tables::IntervalIntersectTable>(pool_);
178
179 // Find all intersections where interval from right table started duringan
180 // interval from left table.
181 for (Interval l_i = *l_it; l_it && r_it && !parse_error;
182 ++l_it, l_i = *l_it) {
183 // If the next |r_i| starts after |l_i| ends, that means that we need to
184 // go the the next |l_i|, so we need to exit the loop.
185 for (Interval r_i = *r_it; r_it && r_i.ts < l_i.end() && !parse_error;
186 ++r_it, r_i = *r_it) {
187 // We already know (because we are in the loop) that |r_i| started before
188 // |l_i| ended, we should not intersect only if |r_i| started before
189 // |l_i|.
190 if (r_i.ts < l_i.ts) {
191 continue;
192 }
193
194 tables::IntervalIntersectTable::Row row;
195 row.ts = std::max(r_i.ts, l_i.ts);
196 row.dur = std::min(r_i.end(), l_i.end()) - row.ts;
197 row.left_id = static_cast<uint32_t>(l_i.id);
198 row.right_id = static_cast<uint32_t>(r_i.id);
199 table->Insert(row);
200 }
201 }
202
203 // Find all intersections where interval from the left table started during an
204 // interval from right table.
205 for (Interval r_i = *r_it_2; r_it_2 && l_it_2 && !parse_error;
206 ++r_it_2, r_i = *r_it_2) {
207 for (Interval l_i = *l_it_2; l_it_2 && l_i.ts < r_i.end() && !parse_error;
208 ++l_it_2, l_i = *l_it_2) {
209 // The only difference between this and above algorithm is not
210 // intersecting if the intervals started at the same time. We do this to
211 // prevent double counting intervals.
212 if (l_i.ts <= r_i.ts) {
213 continue;
214 }
215
216 tables::IntervalIntersectTable::Row row;
217 row.ts = std::max(r_i.ts, l_i.ts);
218 row.dur = std::min(r_i.end(), l_i.end()) - row.ts;
219 row.left_id = static_cast<uint32_t>(l_i.id);
220 row.right_id = static_cast<uint32_t>(r_i.id);
221 table->Insert(row);
222 }
223 }
224
225 if (parse_error) {
226 return base::ErrStatus(
227 "interval_intersect: Error in parsing of one of the arguments.");
228 }
229
230 return std::unique_ptr<Table>(std::move(table));
231 }
232
233 } // namespace perfetto::trace_processor
234