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_COLUMN_H_ 18 #define SRC_TRACE_PROCESSOR_DB_COLUMN_H_ 19 20 #include <stdint.h> 21 #include <optional> 22 23 #include "perfetto/base/logging.h" 24 #include "perfetto/trace_processor/basic_types.h" 25 #include "src/trace_processor/containers/row_map.h" 26 #include "src/trace_processor/containers/string_pool.h" 27 #include "src/trace_processor/db/column/types.h" 28 #include "src/trace_processor/db/column_storage.h" 29 #include "src/trace_processor/db/column_storage_overlay.h" 30 #include "src/trace_processor/db/compare.h" 31 #include "src/trace_processor/db/typed_column_internal.h" 32 33 namespace perfetto::trace_processor { 34 35 // Helper class for converting a type to a ColumnType. 36 template <typename T> 37 struct ColumnTypeHelper; 38 template <> 39 struct ColumnTypeHelper<int32_t> { 40 static constexpr ColumnType ToColumnType() { return ColumnType::kInt32; } 41 }; 42 template <> 43 struct ColumnTypeHelper<uint32_t> { 44 static constexpr ColumnType ToColumnType() { return ColumnType::kUint32; } 45 }; 46 template <> 47 struct ColumnTypeHelper<int64_t> { 48 static constexpr ColumnType ToColumnType() { return ColumnType::kInt64; } 49 }; 50 template <> 51 struct ColumnTypeHelper<double> { 52 static constexpr ColumnType ToColumnType() { return ColumnType::kDouble; } 53 }; 54 template <> 55 struct ColumnTypeHelper<StringPool::Id> { 56 static constexpr ColumnType ToColumnType() { return ColumnType::kString; } 57 }; 58 template <typename T> 59 struct ColumnTypeHelper<std::optional<T>> : public ColumnTypeHelper<T> {}; 60 61 class Table; 62 63 // Represents a named, strongly typed list of data. 64 class ColumnLegacy { 65 public: 66 // Flags which indicate properties of the data in the column. These features 67 // are used to speed up column methods like filtering/sorting. 68 enum Flag : uint32_t { 69 // Indicates that this column has no special properties. 70 kNoFlag = 0, 71 72 // Indicates the data in the column is sorted. This can be used to speed 73 // up filtering and skip sorting. 74 kSorted = 1 << 0, 75 76 // Indicates the data in the column is non-null. That is, the NullableVector 77 // passed in will never have any null entries. This is only used for 78 // numeric columns (string columns and id columns both have special 79 // handling which ignores this flag). 80 // 81 // This is used to speed up filters as we can safely index NullableVector 82 // directly if this flag is set. 83 kNonNull = 1 << 1, 84 85 // Indicates that the data in the column is "hidden". This can by used to 86 // hint to users of Table and Column that this column should not be 87 // displayed to the user as it is part of the internal implementation 88 // details of the table. 89 kHidden = 1 << 2, 90 91 // Indicates that the data in this column is stored densely. This 92 // allows for fast Set calls to change the data in the column. 93 // 94 // This flag is only meaningful for nullable columns has no effect for 95 // non-null columns. 96 kDense = 1 << 3, 97 98 // Indicates that the sorted numeric data in the column is laid out such 99 // that at row i, we will always have col[i] <= i and the first element, j 100 // of each group happens at the index j. 101 // 102 // This is a common pattern in trace processor and columns with this 103 // property are suffixed with "set_id" hence the name of this flag. 104 // 105 // To make this clear, here are some valid and invalid uses of this flag. 106 // 107 // Valid: 108 // [] 109 // [0] 110 // [0, 1, 2] 111 // [0, 0, 2] 112 // [0, 0, 0, 3, 3, 5, 6, 6, 7] 113 // 114 // Invalid: 115 // [1] 116 // [0, 0, 1] 117 // [0, 0, 2, 5] 118 // [0, 0, 2, 1] 119 // 120 // If this flag is set, kSorted and kNonNull should be set. Moreover, this 121 // flag can only be set when the type is ColumnType::kUint32; other types 122 // are not supported. 123 kSetId = 1 << 4, 124 }; 125 126 // Iterator over a column which conforms to std iterator interface 127 // to allow using std algorithms (e.g. upper_bound, lower_bound etc.). 128 class Iterator { 129 public: 130 using iterator_category = std::random_access_iterator_tag; 131 using value_type = SqlValue; 132 using difference_type = uint32_t; 133 using pointer = uint32_t*; 134 using reference = uint32_t&; 135 136 Iterator(const ColumnLegacy* col, uint32_t row) : col_(col), row_(row) {} 137 138 Iterator(const Iterator&) = default; 139 Iterator& operator=(const Iterator&) = default; 140 141 bool operator==(const Iterator& other) const { return other.row_ == row_; } 142 bool operator!=(const Iterator& other) const { return !(*this == other); } 143 bool operator<(const Iterator& other) const { return row_ < other.row_; } 144 bool operator>(const Iterator& other) const { return other < *this; } 145 bool operator<=(const Iterator& other) const { return !(other < *this); } 146 bool operator>=(const Iterator& other) const { return !(*this < other); } 147 148 SqlValue operator*() const { return col_->Get(row_); } 149 Iterator& operator++() { 150 row_++; 151 return *this; 152 } 153 Iterator& operator--() { 154 row_--; 155 return *this; 156 } 157 158 Iterator& operator+=(uint32_t diff) { 159 row_ += diff; 160 return *this; 161 } 162 uint32_t operator-(const Iterator& other) const { 163 return row_ - other.row_; 164 } 165 166 uint32_t row() const { return row_; } 167 168 private: 169 const ColumnLegacy* col_ = nullptr; 170 uint32_t row_ = 0; 171 }; 172 173 // Flags specified for an id column. 174 static constexpr uint32_t kIdFlags = Flag::kSorted | Flag::kNonNull; 175 176 // Flags which should *not* be inherited implicitly when a column is 177 // assocaited to another table. 178 static constexpr uint32_t kNoCrossTableInheritFlags = 179 ColumnLegacy::Flag::kSetId; 180 181 template <typename T> 182 ColumnLegacy(const char* name, 183 ColumnStorage<T>* storage, 184 /* Flag */ uint32_t flags, 185 uint32_t col_idx_in_table, 186 uint32_t row_map_idx) 187 : ColumnLegacy(name, 188 ColumnTypeHelper<stored_type<T>>::ToColumnType(), 189 flags, 190 col_idx_in_table, 191 row_map_idx, 192 storage) {} 193 194 // Create a Column backed by the same data as |column| but is associated to a 195 // different table and, optionally, having a different name. 196 ColumnLegacy(const ColumnLegacy& column, 197 uint32_t col_idx_in_table, 198 uint32_t row_map_idx, 199 const char* name = nullptr); 200 201 // Columns are movable but not copyable. 202 ColumnLegacy(ColumnLegacy&&) noexcept = default; 203 ColumnLegacy& operator=(ColumnLegacy&&) = default; 204 205 // Creates a Column which does not have any data backing it. 206 static ColumnLegacy DummyColumn(const char* name, uint32_t col_idx_in_table); 207 208 // Creates a Column which returns the index as the value of the row. 209 static ColumnLegacy IdColumn(uint32_t col_idx_in_table, 210 uint32_t overlay_idx, 211 const char* name = "id", 212 uint32_t flags = kIdFlags); 213 214 // Gets the value of the Column at the given |row|. 215 SqlValue Get(uint32_t row) const { return GetAtIdx(overlay().Get(row)); } 216 217 // Returns the backing RowMap for this Column. 218 // This function is defined out of line because of a circular dependency 219 // between |Table| and |Column|. 220 const ColumnStorageOverlay& overlay() const; 221 222 // Returns the name of the column. 223 const char* name() const { return name_; } 224 225 // Returns the type of this Column in terms of ColumnType. 226 ColumnType col_type() const { return type_; } 227 228 // Test the type of this Column. 229 template <typename T> 230 bool IsColumnType() const { 231 return ColumnTypeHelper<T>::ToColumnType() == type_; 232 } 233 234 // Returns true if this column is considered an id column. 235 bool IsId() const { return type_ == ColumnType::kId; } 236 237 // Returns true if this column is a nullable column. 238 bool IsNullable() const { return IsNullable(flags_); } 239 240 // Returns true if this column is a sorted column. 241 bool IsSorted() const { return IsSorted(flags_); } 242 243 // Returns true if this column is a dense column. 244 bool IsDense() const { return IsDense(flags_); } 245 246 // Returns true if this column is a set id column. 247 // Public for testing. 248 bool IsSetId() const { return IsSetId(flags_); } 249 250 // Returns true if this column is a dummy column. 251 // Public for testing. 252 bool IsDummy() const { return type_ == ColumnType::kDummy; } 253 254 // Returns true if this column is a hidden column. 255 bool IsHidden() const { return (flags_ & Flag::kHidden) != 0; } 256 257 // Returns the index of the RowMap in the containing table. 258 uint32_t overlay_index() const { return overlay_index_; } 259 260 // Returns the index of the current column in the containing table. 261 uint32_t index_in_table() const { return index_in_table_; } 262 263 // Returns a Constraint for each type of filter operation for this Column. 264 Constraint eq_value(SqlValue value) const { 265 return Constraint{index_in_table_, FilterOp::kEq, value}; 266 } 267 Constraint gt_value(SqlValue value) const { 268 return Constraint{index_in_table_, FilterOp::kGt, value}; 269 } 270 Constraint lt_value(SqlValue value) const { 271 return Constraint{index_in_table_, FilterOp::kLt, value}; 272 } 273 Constraint ne_value(SqlValue value) const { 274 return Constraint{index_in_table_, FilterOp::kNe, value}; 275 } 276 Constraint ge_value(SqlValue value) const { 277 return Constraint{index_in_table_, FilterOp::kGe, value}; 278 } 279 Constraint le_value(SqlValue value) const { 280 return Constraint{index_in_table_, FilterOp::kLe, value}; 281 } 282 Constraint is_not_null() const { 283 return Constraint{index_in_table_, FilterOp::kIsNotNull, SqlValue()}; 284 } 285 Constraint is_null() const { 286 return Constraint{index_in_table_, FilterOp::kIsNull, SqlValue()}; 287 } 288 Constraint glob_value(SqlValue value) const { 289 return Constraint{index_in_table_, FilterOp::kGlob, value}; 290 } 291 292 Constraint regex_value(SqlValue value) const { 293 return Constraint{index_in_table_, FilterOp::kRegex, value}; 294 } 295 296 // Returns an Order for each Order type for this Column. 297 Order ascending() const { return Order{index_in_table_, false}; } 298 Order descending() const { return Order{index_in_table_, true}; } 299 300 // Returns an iterator to the first entry in this column. 301 Iterator begin() const { return Iterator(this, 0); } 302 303 // Returns an iterator pointing beyond the last entry in this column. 304 Iterator end() const { return Iterator(this, overlay().size()); } 305 306 // Returns whether the given combination of flags when the column has the 307 // given type is valid. 308 template <typename T> 309 static constexpr bool IsFlagsAndTypeValid(uint32_t flags) { 310 return IsFlagsAndTypeValid(flags, ColumnTypeHelper<T>::ToColumnType()); 311 } 312 313 template <typename T> 314 using stored_type = typename tc_internal::TypeHandler<T>::stored_type; 315 316 // Returns the backing sparse vector cast to contain data of type T. 317 // Should only be called when |type_| == ToColumnType<T>(). 318 template <typename T> 319 const ColumnStorage<stored_type<T>>& storage() const { 320 PERFETTO_DCHECK(ColumnTypeHelper<T>::ToColumnType() == type_); 321 PERFETTO_DCHECK(tc_internal::TypeHandler<T>::is_optional == IsNullable()); 322 return *static_cast<ColumnStorage<stored_type<T>>*>(storage_); 323 } 324 325 const ColumnStorageBase& storage_base() const { return *storage_; } 326 327 static SqlValue::Type ToSqlValueType(ColumnType type) { 328 switch (type) { 329 case ColumnType::kInt32: 330 case ColumnType::kUint32: 331 case ColumnType::kInt64: 332 case ColumnType::kId: 333 return SqlValue::Type::kLong; 334 case ColumnType::kDouble: 335 return SqlValue::Type::kDouble; 336 case ColumnType::kString: 337 return SqlValue::Type::kString; 338 case ColumnType::kDummy: 339 PERFETTO_FATAL("ToSqlValueType not allowed on dummy column"); 340 } 341 PERFETTO_FATAL("For GCC"); 342 } 343 344 protected: 345 // Returns the backing sparse vector cast to contain data of type T. 346 // Should only be called when |type_| == ToColumnType<T>(). 347 template <typename T> 348 ColumnStorage<stored_type<T>>* mutable_storage() { 349 PERFETTO_DCHECK(ColumnTypeHelper<T>::ToColumnType() == type_); 350 PERFETTO_DCHECK(tc_internal::TypeHandler<T>::is_optional == IsNullable()); 351 return static_cast<ColumnStorage<stored_type<T>>*>(storage_); 352 } 353 354 const StringPool& string_pool() const { return *string_pool_; } 355 356 // Returns the type of this Column in terms of SqlValue::Type. 357 template <typename T> 358 static SqlValue::Type ToSqlValueType() { 359 return ToSqlValueType(ColumnTypeHelper<T>::ToColumnType()); 360 } 361 362 static SqlValue ToSqlValue(double value) { return SqlValue::Double(value); } 363 static SqlValue ToSqlValue(int32_t value) { return SqlValue::Long(value); } 364 static SqlValue ToSqlValue(uint32_t value) { return SqlValue::Long(value); } 365 static SqlValue ToSqlValue(int64_t value) { return SqlValue::Long(value); } 366 static SqlValue ToSqlValue(NullTermStringView value) { 367 return SqlValue::String(value.c_str()); 368 } 369 370 private: 371 friend class Table; 372 friend class View; 373 374 // Base constructor for this class which all other constructors call into. 375 ColumnLegacy(const char* name, 376 ColumnType type, 377 uint32_t flags, 378 uint32_t col_idx_in_table, 379 uint32_t overlay_index, 380 ColumnStorageBase* nullable_vector); 381 382 ColumnLegacy(const ColumnLegacy&) = delete; 383 ColumnLegacy& operator=(const ColumnLegacy&) = delete; 384 385 // Gets the value of the Column at the given |idx|. 386 SqlValue GetAtIdx(uint32_t idx) const { 387 switch (type_) { 388 case ColumnType::kInt32: 389 return GetAtIdxTyped<int32_t>(idx); 390 case ColumnType::kUint32: 391 return GetAtIdxTyped<uint32_t>(idx); 392 case ColumnType::kInt64: 393 return GetAtIdxTyped<int64_t>(idx); 394 case ColumnType::kDouble: 395 return GetAtIdxTyped<double>(idx); 396 case ColumnType::kString: { 397 auto str = GetStringPoolStringAtIdx(idx).c_str(); 398 return str == nullptr ? SqlValue() : SqlValue::String(str); 399 } 400 case ColumnType::kId: 401 return SqlValue::Long(idx); 402 case ColumnType::kDummy: 403 PERFETTO_FATAL("GetAtIdx not allowed on dummy column"); 404 } 405 PERFETTO_FATAL("For GCC"); 406 } 407 408 template <typename T> 409 SqlValue GetAtIdxTyped(uint32_t idx) const { 410 if (IsNullable()) { 411 auto opt_value = storage<std::optional<T>>().Get(idx); 412 return opt_value ? ToSqlValue(*opt_value) : SqlValue(); 413 } 414 return ToSqlValue(storage<T>().Get(idx)); 415 } 416 417 static constexpr bool IsDense(uint32_t flags) { 418 return (flags & Flag::kDense) != 0; 419 } 420 static constexpr bool IsNullable(uint32_t flags) { 421 return (flags & Flag::kNonNull) == 0; 422 } 423 static constexpr bool IsSetId(uint32_t flags) { 424 return (flags & Flag::kSetId) != 0; 425 } 426 static constexpr bool IsSorted(uint32_t flags) { 427 return (flags & Flag::kSorted) != 0; 428 } 429 430 static constexpr bool IsFlagsAndTypeValid(uint32_t flags, ColumnType type) { 431 return (!IsDense(flags) || IsFlagsForDenseValid(flags)) && 432 (!IsSetId(flags) || IsFlagsAndTypeForSetIdValid(flags, type)); 433 } 434 435 static constexpr bool IsFlagsForDenseValid(uint32_t flags) { 436 // The dense flag should only be set when the column is nullable. 437 return IsNullable(flags); 438 } 439 440 static constexpr bool IsFlagsAndTypeForSetIdValid(uint32_t flags, 441 ColumnType type) { 442 // The sorted flag should always be set for set id columns. 443 // The non-null flag should always be set for set id columns. 444 // The column type should always be kUint32. 445 return IsSorted(flags) && !IsNullable(flags) && type == ColumnType::kUint32; 446 } 447 448 // Returns the string at the index |idx|. 449 // Should only be called when |type_| == ColumnType::kString. 450 NullTermStringView GetStringPoolStringAtIdx(uint32_t idx) const { 451 PERFETTO_DCHECK(type_ == ColumnType::kString); 452 return string_pool_->Get(storage<StringPool::Id>().Get(idx)); 453 } 454 455 void BindToTable(Table* table, StringPool* string_pool) { 456 PERFETTO_DCHECK(!table_); 457 table_ = table; 458 string_pool_ = string_pool; 459 460 // Check that the dense-ness of the column and the nullable vector match. 461 if (IsNullable() && !IsDummy()) { 462 bool is_storage_dense; 463 switch (type_) { 464 case ColumnType::kInt32: 465 is_storage_dense = storage<std::optional<int32_t>>().IsDense(); 466 break; 467 case ColumnType::kUint32: 468 is_storage_dense = storage<std::optional<uint32_t>>().IsDense(); 469 break; 470 case ColumnType::kInt64: 471 is_storage_dense = storage<std::optional<int64_t>>().IsDense(); 472 break; 473 case ColumnType::kDouble: 474 is_storage_dense = storage<std::optional<double>>().IsDense(); 475 break; 476 case ColumnType::kString: 477 PERFETTO_FATAL("String column should not be nullable"); 478 case ColumnType::kId: 479 PERFETTO_FATAL("Id column should not be nullable"); 480 case ColumnType::kDummy: 481 PERFETTO_FATAL("Dummy column excluded above"); 482 } 483 PERFETTO_DCHECK(is_storage_dense == IsDense()); 484 } 485 PERFETTO_DCHECK(IsFlagsAndTypeValid(flags_, type_)); 486 } 487 488 // type_ is used to cast nullable_vector_ to the correct type. 489 ColumnType type_ = ColumnType::kInt64; 490 ColumnStorageBase* storage_ = nullptr; 491 492 const char* name_ = nullptr; 493 uint32_t flags_ = Flag::kNoFlag; 494 const Table* table_ = nullptr; 495 uint32_t index_in_table_ = 0; 496 uint32_t overlay_index_ = 0; 497 const StringPool* string_pool_ = nullptr; 498 }; 499 500 } // namespace perfetto::trace_processor 501 502 #endif // SRC_TRACE_PROCESSOR_DB_COLUMN_H_ 503