1 /*
2 * Copyright (C) 2019 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 #ifndef SRC_TRACE_PROCESSOR_DB_COMPARE_H_
18 #define SRC_TRACE_PROCESSOR_DB_COMPARE_H_
19
20 #include <stdint.h>
21
22 #include <algorithm>
23 #include <optional>
24
25 #include "perfetto/ext/base/string_view.h"
26 #include "perfetto/trace_processor/basic_types.h"
27
28 namespace perfetto {
29 namespace trace_processor {
30 namespace compare {
31
32 // This file contains the de-facto impleemntation of all comparisions used by
33 // trace processor in every setting. All of this is centralised in one file to
34 // ensure both internal consistency with SQLite and consistency with SQLite.
35
36 // Compare a non-null numeric to a double; returns:
37 // * <0 if i < d,
38 // * >0 if i > d.
39 // * 0 otherwise
40 // This code matches the behaviour of sqlite3IntFloatCompare.
LongToDouble(int64_t i,double d)41 inline int LongToDouble(int64_t i, double d) {
42 // First check if we are out of range for a int64_t. We use the constants
43 // directly instead of using numeric_limits as the casts introduces rounding
44 // in the doubles as a double cannot exactly represent int64::max().
45 if (d >= 9223372036854775808.0)
46 return -1;
47 if (d < -9223372036854775808.0)
48 return 1;
49
50 // Then, try to compare in int64 space to try and keep as much precision as
51 // possible.
52 int64_t d_i = static_cast<int64_t>(d);
53 if (i < d_i)
54 return -1;
55 if (i > d_i)
56 return 1;
57
58 // Finally, try and compare in double space, sacrificing precision if
59 // necessary.
60 double i_d = static_cast<double>(i);
61 return (i_d < d) ? -1 : (i_d > d ? 1 : 0);
62 }
63
64 // Compares two non-null numeric values; returns:
65 // * <0 if a < b,
66 // * >0 if a > b.
67 // * 0 otherwise
68 // This code matches the behaviour of the inline code in the comparision path of
69 // sqlite3VdbeExec (for ints) and the behaviour of sqlite3MemCompare (for
70 // doubles).
71 template <typename T>
Numeric(T a,T b)72 inline int Numeric(T a, T b) {
73 static_assert(std::is_arithmetic<T>::value,
74 "Numeric comparision performed with non-numeric type");
75 return a < b ? -1 : (a > b ? 1 : 0);
76 }
77
78 // Compares two non-null bytes values; returns:
79 // * <0 if a < b,
80 // * >0 if a > b.
81 // * 0 otherwise
82 // This code matches the behaviour of sqlite3BlobCompare.
Bytes(const void * a,size_t a_n,const void * b,size_t b_n)83 inline int Bytes(const void* a, size_t a_n, const void* b, size_t b_n) {
84 int res = memcmp(a, b, std::min(a_n, b_n));
85 return res != 0 ? res
86 : static_cast<int>(static_cast<int64_t>(a_n) -
87 static_cast<int64_t>(b_n));
88 }
89
90 // Compares two non-null string values; returns:
91 // * <0 if a < b,
92 // * >0 if a > b.
93 // * 0 otherwise
94 // This code matches the behaviour of sqlite3BlobCompare which is called when
95 // there is no collation sequence defined in sqlite3MemCompare.
String(base::StringView a,base::StringView b)96 inline int String(base::StringView a, base::StringView b) {
97 PERFETTO_DCHECK(a.data() != nullptr);
98 PERFETTO_DCHECK(b.data() != nullptr);
99 return Bytes(a.data(), a.size(), b.data(), b.size());
100 }
101
102 // Compares two nullable numeric values; returns:
103 // * 0 if both a and b are null
104 // * <0 if a is null and b is non null
105 // * >0 if a is non null and b is null
106 // * <0 if a < b (a and b both non null)
107 // * >0 if a > b (a and b both non null)
108 // * 0 otherwise
109 // Should only be used for defining an ordering on value of type T. For filter
110 // functions, compare::Numeric should be used above after checking if the value
111 // is null.
112 // This method was defined from observing the behaviour of SQLite when sorting
113 // on columns containing nulls.
114 template <typename T>
NullableNumeric(std::optional<T> a,std::optional<T> b)115 inline int NullableNumeric(std::optional<T> a, std::optional<T> b) {
116 if (!a)
117 return b ? -1 : 0;
118
119 if (!b)
120 return 1;
121
122 return compare::Numeric(*a, *b);
123 }
124
125 // Compares two strings, either of which can be null; returns:
126 // * 0 if both a and b are null
127 // * <0 if a is null and b is non null
128 // * >0 if a is non null and b is null
129 // * <0 if a < b (a and b both non null)
130 // * >0 if a > b (a and b both non null)
131 // * 0 otherwise
132 // Should only be used for defining an ordering on value of type T. For filter
133 // functions, compare::String should be used above after checking if the value
134 // is null.
135 // This method was defined from observing the behaviour of SQLite when sorting
136 // on columns containing nulls.
NullableString(base::StringView a,base::StringView b)137 inline int NullableString(base::StringView a, base::StringView b) {
138 if (!a.data())
139 return b.data() ? -1 : 0;
140
141 if (!b.data())
142 return 1;
143
144 return compare::String(a, b);
145 }
146
147 // Compares two SqlValue; returns:
148 // * <0 if a.type < b.type and a and b are not both numeric
149 // * >0 if a.type > b.type and a and b are not both numeric
150 // * <0 if a < b (a and b both non null and either of same type or numeric)
151 // * >0 if a > b (a and b both non null and either of same type or numeric)
152 // * 0 otherwise
153 // This code roughly matches the behaviour of the code in the comparision path
154 // of sqlite3VdbeExec except we are intentionally more strict than SQLite when
155 // it comes to casting between strings and numerics - we disallow moving between
156 // the two. We do allow comparing between doubles and longs however as doubles
157 // can easily appear by using constants in SQL even when intending to use longs.
SqlValue(const SqlValue & a,const SqlValue & b)158 inline int SqlValue(const SqlValue& a, const SqlValue& b) {
159 if (a.type != b.type) {
160 if (a.type == SqlValue::kLong && b.type == SqlValue::kDouble)
161 return compare::LongToDouble(a.long_value, b.double_value);
162
163 if (a.type == SqlValue::kDouble && b.type == SqlValue::kLong)
164 return -compare::LongToDouble(b.long_value, a.double_value);
165
166 return a.type - b.type;
167 }
168
169 switch (a.type) {
170 case SqlValue::Type::kLong:
171 return compare::Numeric(a.long_value, b.long_value);
172 case SqlValue::Type::kDouble:
173 return compare::Numeric(a.double_value, b.double_value);
174 case SqlValue::Type::kString:
175 return compare::String(a.string_value, b.string_value);
176 case SqlValue::Type::kBytes:
177 return compare::Bytes(a.bytes_value, a.bytes_count, b.bytes_value,
178 b.bytes_count);
179 case SqlValue::Type::kNull:
180 return 0;
181 }
182 PERFETTO_FATAL("For GCC");
183 }
184
185 // Implements a comparator for SqlValues to use for std algorithms.
186 // See documentation of compare::SqlValue for details of how this function
187 // works.
SqlValueComparator(const trace_processor::SqlValue & a,const trace_processor::SqlValue & b)188 inline int SqlValueComparator(const trace_processor::SqlValue& a,
189 const trace_processor::SqlValue& b) {
190 return compare::SqlValue(a, b) < 0;
191 }
192
193 } // namespace compare
194 } // namespace trace_processor
195 } // namespace perfetto
196
197 #endif // SRC_TRACE_PROCESSOR_DB_COMPARE_H_
198