src/trace_processor/db/column/data_layer.h - third_party/perfetto - Git at Google

 /*
  * Copyright (C) 2023 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #ifndef SRC_TRACE_PROCESSOR_DB_COLUMN_DATA_LAYER_H_
 #define SRC_TRACE_PROCESSOR_DB_COLUMN_DATA_LAYER_H_

 #include <cstdint>
 #include <memory>
 #include <optional>
 #include <string>
 #include <utility>
 #include <vector>

 #include "perfetto/base/compiler.h"
 #include "perfetto/base/logging.h"
 #include "perfetto/trace_processor/basic_types.h"
 #include "perfetto/trace_processor/ref_counted.h"
 #include "src/trace_processor/db/column/types.h"

 namespace perfetto::protos::pbzero {
 class SerializedColumn_Storage;
 }

 namespace perfetto::trace_processor::column {
 class DataLayerChain;

 // Data structure which either directly or indirectly (i.e. by transforming
 // the contents of another DataLayer) provides the data of a column of a
 // table.
 class DataLayer : public RefCounted {
  public:
   // Arguments for MakeChain on how the inner chain should be interpreted.
   struct ChainCreationArgs {
     constexpr explicit ChainCreationArgs(
         bool _does_layer_order_chain_contents = false)
         : does_layer_order_chain_contents(_does_layer_order_chain_contents) {}

     // Indicates whether the current data layer orders the inner chain.
     // Currently used by ArrangementOverlay to decide whether the arrangement
     // orders a given chain.
     bool does_layer_order_chain_contents;
   };
   virtual ~DataLayer();

   // Creates a DataLayerChain for a terminal DataLayer. This means the
   // DataLayer directly should return the data it contains inside.
   std::unique_ptr<DataLayerChain> MakeChain();

   // Creates a DataLayerChain for a non-terminal DataLayer. This means
   // the DataLayer should transform the contents of the inner chain.
   std::unique_ptr<DataLayerChain> MakeChain(
       std::unique_ptr<DataLayerChain>,
       ChainCreationArgs = ChainCreationArgs());

  protected:
   // TODO(b/325583551): remove this when possible.
   enum class Impl {
     kArrangement,
     kDenseNull,
     kDummy,
     kId,
     kNull,
     kNumericDouble,
     kNumericUint32,
     kNumericInt32,
     kNumericInt64,
     kRange,
     kSelector,
     kSetId,
     kString,
   };
   explicit DataLayer(Impl impl) : impl_(impl) {}

  private:
   Impl impl_;
 };

 // Corresponds to a series of DataLayer chained together. Provides
 // functionality for querying the transformed data of the entire chain.
 class DataLayerChain {
  public:
   // Indicates the direction of the sort on a single chain.
   enum class SortDirection {
     kAscending,
     kDescending,
   };
   // Struct wrapping indices to elements of this chain. Passed to sorting
   // functions.
   struct SortToken {
     // An index pointing to an element in this chain. Indicates the element
     // at this index should be compared.
     uint32_t index;

     // An opaque value which can be set to some value meaningful to the
     // caller. Implementations *should not* read at this value.
     uint32_t payload;
   };
   using StorageProto = protos::pbzero::SerializedColumn_Storage;

   // Index vector related data required to Filter using IndexSearch.
   struct Indices {
     enum class State {
       // We can't guarantee that data is in monotonic order.
       kNonmonotonic,
       // Data is in monotonic order.
       kMonotonic,
     };
     static Indices Create(const std::vector<uint32_t>& raw, State state) {
       std::vector<Token> tokens;
       tokens.reserve(raw.size());
       for (auto r : raw) {
         tokens.push_back({r, r});
       }
       return Indices{std::move(tokens), state};
     }
     static Indices CreateWithIndexPayloadForTesting(
         const std::vector<uint32_t>& raw,
         State state) {
       std::vector<Token> tokens;
       tokens.reserve(raw.size());
       for (uint32_t i = 0; i < raw.size(); ++i) {
         tokens.push_back(Token{raw[i], i});
       }
       return Indices{std::move(tokens), state};
     }
     std::vector<Token> tokens;
     State state = State::kNonmonotonic;
   };

   // Index vector related data required to Filter using IndexSearch.
   struct OrderedIndices {
     const uint32_t* data = nullptr;
     uint32_t size = 0;
     Indices::State state = Indices::State::kNonmonotonic;
   };

   virtual ~DataLayerChain();

   // Start of public API.

   // Checks whether element at the provided index match |op| and |value|.
   //
   // Returns true if the element matches, false otherwise.
   virtual SingleSearchResult SingleSearch(FilterOp op,
                                           SqlValue value,
                                           uint32_t row) const = 0;

   // Searches for elements which match |op| and |value| between |range.start|
   // and |range.end|.
   //
   // Returns either a range or BitVector which indicate the positions in
   // |range| which match the constraint. If a BitVector is returned, it will
   // be *precisely* as large as |range.end|.
   //
   // Notes for callers:
   //  * Callers should note that the return value of this function corresponds
   //    to positions in the storage.
   //
   // Notes for implementors:
   //  * Implementations should ensure that the return value is empty or *only*
   //    includes positions in |range|. Callers are free to assume this and can
   //    optimize based on it.
   //  * Implementations should ensure that, if they return a BitVector, it is
   //    precisely of size |range.end|.
   PERFETTO_ALWAYS_INLINE RangeOrBitVector Search(FilterOp op,
                                                  SqlValue value,
                                                  Range range) const {
     PERFETTO_DCHECK(range.end <= size());
     switch (ValidateSearchConstraints(op, value)) {
       case SearchValidationResult::kAllData:
         return RangeOrBitVector(range);
       case SearchValidationResult::kNoData:
         return RangeOrBitVector(Range());
       case SearchValidationResult::kOk:
         return SearchValidated(op, value, range);
     }
     PERFETTO_FATAL("For GCC");
   }

   // Searches for elements which match |op| and |value| at the positions given
   // by |indices| array.
   //
   // Returns either a range of BitVector which indicate the positions in
   // |indices| which match the constraint. If a BitVector is returned, it will
   // be *precisely* as large as |indices_count|.
   //
   // Notes for callers:
   //  * Callers should note that the return value of this function corresponds
   //    to positions in |indices| *not* positions in the storage.
   //
   // Notes for implementors:
   //  * Implementations should ensure that, if they return a BitVector, it is
   //    precisely of size |indices_count|.
   PERFETTO_ALWAYS_INLINE void IndexSearch(FilterOp op,
                                           SqlValue value,
                                           Indices& indices) const {
     switch (ValidateSearchConstraints(op, value)) {
       case SearchValidationResult::kAllData:
         return;
       case SearchValidationResult::kNoData:
         indices.tokens.clear();
         return;
       case SearchValidationResult::kOk:
         IndexSearchValidated(op, value, indices);
         return;
     }
     PERFETTO_FATAL("For GCC");
   }

   // Searches for elements which match |op| and |value| at the positions given
   // by OrderedIndicesdata.
   //
   // Returns a Range into OrderedIndicesdata of OrderedIndicesthat pass the
   // constraint.
   //
   // Notes for callers:
   //  * Should not be called on:
   //    - kGlob and kRegex as those operations can't use the sorted state
   //      hence they can't return a Range.
   //    - kNe as this is inherently unsorted. Use kEq and then reverse the
   //      result.
   //  * Callers should note that the return value of this function corresponds
   //    to positions in |indices| *not* positions in the storage.
   PERFETTO_ALWAYS_INLINE Range
   OrderedIndexSearch(FilterOp op,
                      SqlValue value,
                      const OrderedIndices& indices) const {
     switch (ValidateSearchConstraints(op, value)) {
       case SearchValidationResult::kAllData:
         return {0, indices.size};
       case SearchValidationResult::kNoData:
         return {};
       case SearchValidationResult::kOk:
         return OrderedIndexSearchValidated(op, value, indices);
     }
     PERFETTO_FATAL("For GCC");
   }

   // Stable sorts an array of SortToken elements between |start| and |end|
   // using a comparator defined by looking up the elements in this chain using
   // the index given by SortToken::index. |direction| indicates the direction of
   // the sort (ascending or descending).
   //
   // In simple terms the expectation is for implementations do something like:
   // ```
   // std::stable_sort(start, index, [](const SortToken& a, const SortToken& b) {
   //  return Get(a.index) < Get(b.index);
   // });
   // ```
   // with |Get| being a function to lookup the element in this chain.
   virtual void StableSort(SortToken* start,
                           SortToken* end,
                           SortDirection direction) const = 0;

   // Removes all indices pointing to values that are duplicates, as a result the
   // indices will only point to distinct (not duplicated) values.
   //
   // Notes for implementors:
   // * Each layer that might introduce duplicates is responsible for removing
   // them.
   virtual void Distinct(Indices&) const = 0;

   // After calling this function Indices will have at most one element. If
   // present it will point to the first index with the largest value in the
   // chain.
   virtual std::optional<Token> MaxElement(Indices&) const = 0;

   // After calling this function Indices will have at most one element. If
   // present it will point to the first index with the smallest value in the
   // chain.
   virtual std::optional<Token> MinElement(Indices&) const = 0;

   // Serializes storage data to proto format.
   virtual void Serialize(StorageProto*) const = 0;

   // Returns a string which represents the column for debugging purposes.
   //
   // Warning: the format of the string returned by this class is *not* stable
   // and should be relied upon for anything except printing for debugging
   // purposes.
   virtual std::string DebugString() const = 0;

   // Number of elements in stored data.
   virtual uint32_t size() const = 0;

   // End of public API.
   // The below methods might be public but are only intended for implementations
   // of DataLayerChain.

   // Verifies whether any further filtering is needed and if not, whether the
   // search would return all values or none of them. This allows for skipping
   // the |Search| and |IndexSearch| in special cases.
   //
   // Notes for callers:
   // * The SqlValue and FilterOp have to be valid in Sqlite: it will crash if
   //   either: value is NULL and operation is different than "IS NULL" and "IS
   //   NOT NULL" or the operation is "IS NULL" or "IS NOT NULL" and value is
   //   different than NULL.
   virtual SearchValidationResult ValidateSearchConstraints(FilterOp,
                                                            SqlValue) const = 0;

   // Post-validated implementation of |Search|. See |Search|'s documentation.
   virtual RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const = 0;

   // Post-validated implementation of |IndexSearch|. See |IndexSearch|'s
   // documentation.
   virtual void IndexSearchValidated(FilterOp, SqlValue, Indices&) const = 0;

   // Post-validated implementation of |OrderedIndexSearch|. See
   // |OrderedIndexSearch|'s documentation.
   Range OrderedIndexSearchValidated(FilterOp op,
                                     SqlValue value,
                                     const OrderedIndices& indices) const;

   // Returns the SqlValue representing the value at a given index.
   //
   // This function might be very tempting to use as it appears cheap on the
   // surface but because of how DataLayerChains might be layered on top of each
   // other, this might require *several* virtual function calls per index.
   // If you're tempted to use this, please consider instead create a new
   // "vectorized" function instead and only using this as a last resort.
   //
   // The correct "class" of algorithms to use this function are cases where you
   // have a set of indices you want to lookup and based on the value returned
   // you will only use a fraction of them. In this case, it might be worth
   // paying the non-vectorized lookup to vastly reduce how many indices need
   // to be translated.
   //
   // An example of such an algorithm is binary search on indices.
   virtual SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const = 0;
 };

 }  // namespace perfetto::trace_processor::column

 #endif  // SRC_TRACE_PROCESSOR_DB_COLUMN_DATA_LAYER_H_
	/*
	* Copyright (C) 2023 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#ifndef SRC_TRACE_PROCESSOR_DB_COLUMN_DATA_LAYER_H_
	#define SRC_TRACE_PROCESSOR_DB_COLUMN_DATA_LAYER_H_

	#include <cstdint>
	#include <memory>
	#include <optional>
	#include <string>
	#include <utility>
	#include <vector>

	#include "perfetto/base/compiler.h"
	#include "perfetto/base/logging.h"
	#include "perfetto/trace_processor/basic_types.h"
	#include "perfetto/trace_processor/ref_counted.h"
	#include "src/trace_processor/db/column/types.h"

	namespace perfetto::protos::pbzero {
	class SerializedColumn_Storage;
	}

	namespace perfetto::trace_processor::column {
	class DataLayerChain;

	// Data structure which either directly or indirectly (i.e. by transforming
	// the contents of another DataLayer) provides the data of a column of a
	// table.
	class DataLayer : public RefCounted {
	public:
	// Arguments for MakeChain on how the inner chain should be interpreted.
	struct ChainCreationArgs {
	constexpr explicit ChainCreationArgs(
	bool _does_layer_order_chain_contents = false)
	: does_layer_order_chain_contents(_does_layer_order_chain_contents) {}

	// Indicates whether the current data layer orders the inner chain.
	// Currently used by ArrangementOverlay to decide whether the arrangement
	// orders a given chain.
	bool does_layer_order_chain_contents;
	};
	virtual ~DataLayer();

	// Creates a DataLayerChain for a terminal DataLayer. This means the
	// DataLayer directly should return the data it contains inside.
	std::unique_ptr<DataLayerChain> MakeChain();

	// Creates a DataLayerChain for a non-terminal DataLayer. This means
	// the DataLayer should transform the contents of the inner chain.
	std::unique_ptr<DataLayerChain> MakeChain(
	std::unique_ptr<DataLayerChain>,
	ChainCreationArgs = ChainCreationArgs());

	protected:
	// TODO(b/325583551): remove this when possible.
	enum class Impl {
	kArrangement,
	kDenseNull,
	kDummy,
	kId,
	kNull,
	kNumericDouble,
	kNumericUint32,
	kNumericInt32,
	kNumericInt64,
	kRange,
	kSelector,
	kSetId,
	kString,
	};
	explicit DataLayer(Impl impl) : impl_(impl) {}

	private:
	Impl impl_;
	};

	// Corresponds to a series of DataLayer chained together. Provides
	// functionality for querying the transformed data of the entire chain.
	class DataLayerChain {
	public:
	// Indicates the direction of the sort on a single chain.
	enum class SortDirection {
	kAscending,
	kDescending,
	};
	// Struct wrapping indices to elements of this chain. Passed to sorting
	// functions.
	struct SortToken {
	// An index pointing to an element in this chain. Indicates the element
	// at this index should be compared.
	uint32_t index;

	// An opaque value which can be set to some value meaningful to the
	// caller. Implementations should not read at this value.
	uint32_t payload;
	};
	using StorageProto = protos::pbzero::SerializedColumn_Storage;

	// Index vector related data required to Filter using IndexSearch.
	struct Indices {
	enum class State {
	// We can't guarantee that data is in monotonic order.
	kNonmonotonic,
	// Data is in monotonic order.
	kMonotonic,
	};
	static Indices Create(const std::vector<uint32_t>& raw, State state) {
	std::vector<Token> tokens;
	tokens.reserve(raw.size());
	for (auto r : raw) {
	tokens.push_back({r, r});
	}
	return Indices{std::move(tokens), state};
	}
	static Indices CreateWithIndexPayloadForTesting(
	const std::vector<uint32_t>& raw,
	State state) {
	std::vector<Token> tokens;
	tokens.reserve(raw.size());
	for (uint32_t i = 0; i < raw.size(); ++i) {
	tokens.push_back(Token{raw[i], i});
	}
	return Indices{std::move(tokens), state};
	}
	std::vector<Token> tokens;
	State state = State::kNonmonotonic;
	};

	// Index vector related data required to Filter using IndexSearch.
	struct OrderedIndices {
	const uint32_t* data = nullptr;
	uint32_t size = 0;
	Indices::State state = Indices::State::kNonmonotonic;
	};

	virtual ~DataLayerChain();

	// Start of public API.

	// Checks whether element at the provided index match \|op\| and \|value\|.
	//
	// Returns true if the element matches, false otherwise.
	virtual SingleSearchResult SingleSearch(FilterOp op,
	SqlValue value,
	uint32_t row) const = 0;

	// Searches for elements which match \|op\| and \|value\| between \|range.start\|
	// and \|range.end\|.
	//
	// Returns either a range or BitVector which indicate the positions in
	// \|range\| which match the constraint. If a BitVector is returned, it will
	// be precisely as large as \|range.end\|.
	//
	// Notes for callers:
	// * Callers should note that the return value of this function corresponds
	// to positions in the storage.
	//
	// Notes for implementors:
	// * Implementations should ensure that the return value is empty or only
	// includes positions in \|range\|. Callers are free to assume this and can
	// optimize based on it.
	// * Implementations should ensure that, if they return a BitVector, it is
	// precisely of size \|range.end\|.
	PERFETTO_ALWAYS_INLINE RangeOrBitVector Search(FilterOp op,
	SqlValue value,
	Range range) const {
	PERFETTO_DCHECK(range.end <= size());
	switch (ValidateSearchConstraints(op, value)) {
	case SearchValidationResult::kAllData:
	return RangeOrBitVector(range);
	case SearchValidationResult::kNoData:
	return RangeOrBitVector(Range());
	case SearchValidationResult::kOk:
	return SearchValidated(op, value, range);
	}
	PERFETTO_FATAL("For GCC");
	}

	// Searches for elements which match \|op\| and \|value\| at the positions given
	// by \|indices\| array.
	//
	// Returns either a range of BitVector which indicate the positions in
	// \|indices\| which match the constraint. If a BitVector is returned, it will
	// be precisely as large as \|indices_count\|.
	//
	// Notes for callers:
	// * Callers should note that the return value of this function corresponds
	// to positions in \|indices\| not positions in the storage.
	//
	// Notes for implementors:
	// * Implementations should ensure that, if they return a BitVector, it is
	// precisely of size \|indices_count\|.
	PERFETTO_ALWAYS_INLINE void IndexSearch(FilterOp op,
	SqlValue value,
	Indices& indices) const {
	switch (ValidateSearchConstraints(op, value)) {
	case SearchValidationResult::kAllData:
	return;
	case SearchValidationResult::kNoData:
	indices.tokens.clear();
	return;
	case SearchValidationResult::kOk:
	IndexSearchValidated(op, value, indices);
	return;
	}
	PERFETTO_FATAL("For GCC");
	}

	// Searches for elements which match \|op\| and \|value\| at the positions given
	// by OrderedIndicesdata.
	//
	// Returns a Range into OrderedIndicesdata of OrderedIndicesthat pass the
	// constraint.
	//
	// Notes for callers:
	// * Should not be called on:
	// - kGlob and kRegex as those operations can't use the sorted state
	// hence they can't return a Range.
	// - kNe as this is inherently unsorted. Use kEq and then reverse the
	// result.
	// * Callers should note that the return value of this function corresponds
	// to positions in \|indices\| not positions in the storage.
	PERFETTO_ALWAYS_INLINE Range
	OrderedIndexSearch(FilterOp op,
	SqlValue value,
	const OrderedIndices& indices) const {
	switch (ValidateSearchConstraints(op, value)) {
	case SearchValidationResult::kAllData:
	return {0, indices.size};
	case SearchValidationResult::kNoData:
	return {};
	case SearchValidationResult::kOk:
	return OrderedIndexSearchValidated(op, value, indices);
	}
	PERFETTO_FATAL("For GCC");
	}

	// Stable sorts an array of SortToken elements between \|start\| and \|end\|
	// using a comparator defined by looking up the elements in this chain using
	// the index given by SortToken::index. \|direction\| indicates the direction of
	// the sort (ascending or descending).
	//
	// In simple terms the expectation is for implementations do something like:
	// ```
	// std::stable_sort(start, index, [](const SortToken& a, const SortToken& b) {
	// return Get(a.index) < Get(b.index);
	// });
	// ```
	// with \|Get\| being a function to lookup the element in this chain.
	virtual void StableSort(SortToken* start,
	SortToken* end,
	SortDirection direction) const = 0;

	// Removes all indices pointing to values that are duplicates, as a result the
	// indices will only point to distinct (not duplicated) values.
	//
	// Notes for implementors:
	// * Each layer that might introduce duplicates is responsible for removing
	// them.
	virtual void Distinct(Indices&) const = 0;

	// After calling this function Indices will have at most one element. If
	// present it will point to the first index with the largest value in the
	// chain.
	virtual std::optional<Token> MaxElement(Indices&) const = 0;

	// After calling this function Indices will have at most one element. If
	// present it will point to the first index with the smallest value in the
	// chain.
	virtual std::optional<Token> MinElement(Indices&) const = 0;

	// Serializes storage data to proto format.
	virtual void Serialize(StorageProto*) const = 0;

	// Returns a string which represents the column for debugging purposes.
	//
	// Warning: the format of the string returned by this class is not stable
	// and should be relied upon for anything except printing for debugging
	// purposes.
	virtual std::string DebugString() const = 0;

	// Number of elements in stored data.
	virtual uint32_t size() const = 0;

	// End of public API.
	// The below methods might be public but are only intended for implementations
	// of DataLayerChain.

	// Verifies whether any further filtering is needed and if not, whether the
	// search would return all values or none of them. This allows for skipping
	// the \|Search\| and \|IndexSearch\| in special cases.
	//
	// Notes for callers:
	// * The SqlValue and FilterOp have to be valid in Sqlite: it will crash if
	// either: value is NULL and operation is different than "IS NULL" and "IS
	// NOT NULL" or the operation is "IS NULL" or "IS NOT NULL" and value is
	// different than NULL.
	virtual SearchValidationResult ValidateSearchConstraints(FilterOp,
	SqlValue) const = 0;

	// Post-validated implementation of \|Search\|. See \|Search\|'s documentation.
	virtual RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const = 0;

	// Post-validated implementation of \|IndexSearch\|. See \|IndexSearch\|'s
	// documentation.
	virtual void IndexSearchValidated(FilterOp, SqlValue, Indices&) const = 0;

	// Post-validated implementation of \|OrderedIndexSearch\|. See
	// \|OrderedIndexSearch\|'s documentation.
	Range OrderedIndexSearchValidated(FilterOp op,
	SqlValue value,
	const OrderedIndices& indices) const;

	// Returns the SqlValue representing the value at a given index.
	//
	// This function might be very tempting to use as it appears cheap on the
	// surface but because of how DataLayerChains might be layered on top of each
	// other, this might require several virtual function calls per index.
	// If you're tempted to use this, please consider instead create a new
	// "vectorized" function instead and only using this as a last resort.
	//
	// The correct "class" of algorithms to use this function are cases where you
	// have a set of indices you want to lookup and based on the value returned
	// you will only use a fraction of them. In this case, it might be worth
	// paying the non-vectorized lookup to vastly reduce how many indices need
	// to be translated.
	//
	// An example of such an algorithm is binary search on indices.
	virtual SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const = 0;
	};

	} // namespace perfetto::trace_processor::column

	#endif // SRC_TRACE_PROCESSOR_DB_COLUMN_DATA_LAYER_H_