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