xref: /aosp_15_r20/external/perfetto/src/trace_processor/db/compare.h (revision 6dbdd20afdafa5e3ca9b8809fa73465d530080dc)
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