src/trace_processor/db/runtime_table.cc - 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.
  */

 #include "src/trace_processor/db/runtime_table.h"

 #include <algorithm>
 #include <cinttypes>
 #include <cstddef>
 #include <cstdint>
 #include <limits>
 #include <memory>
 #include <optional>
 #include <string>
 #include <utility>
 #include <variant>
 #include <vector>

 #include "perfetto/base/logging.h"
 #include "perfetto/base/status.h"
 #include "perfetto/ext/base/status_or.h"
 #include "perfetto/trace_processor/basic_types.h"
 #include "perfetto/trace_processor/ref_counted.h"
 #include "src/trace_processor/containers/bit_vector.h"
 #include "src/trace_processor/containers/string_pool.h"
 #include "src/trace_processor/db/column.h"
 #include "src/trace_processor/db/column/data_layer.h"
 #include "src/trace_processor/db/column/id_storage.h"
 #include "src/trace_processor/db/column/null_overlay.h"
 #include "src/trace_processor/db/column/numeric_storage.h"
 #include "src/trace_processor/db/column/overlay_layer.h"
 #include "src/trace_processor/db/column/selector_overlay.h"
 #include "src/trace_processor/db/column/storage_layer.h"
 #include "src/trace_processor/db/column/string_storage.h"
 #include "src/trace_processor/db/column/types.h"
 #include "src/trace_processor/db/column_storage.h"
 #include "src/trace_processor/db/column_storage_overlay.h"

 namespace perfetto::trace_processor {
 namespace {

 template <typename T, typename U>
 T Fill(uint32_t leading_nulls, U value) {
   T res;
   for (uint32_t i = 0; i < leading_nulls; ++i) {
     res.Append(value);
   }
   return res;
 }

 bool IsPerfectlyRepresentableAsDouble(int64_t res) {
   static constexpr int64_t kMaxDoubleRepresentible = 1ull << 53;
   return res >= -kMaxDoubleRepresentible && res <= kMaxDoubleRepresentible;
 }

 void CreateNonNullableIntsColumn(
     uint32_t col_idx,
     const char* col_name,
     ColumnStorage<int64_t>* ints_storage,
     std::vector<RefPtr<column::StorageLayer>>& storage_layers,
     std::vector<RefPtr<column::OverlayLayer>>& overlay_layers,
     std::vector<ColumnLegacy>& legacy_columns,
     std::vector<ColumnStorageOverlay>& legacy_overlays) {
   const std::vector<int64_t>& values = ints_storage->vector();

   // Looking for the iterator to the first value that is less or equal to the
   // previous value. The values before are therefore strictly monotonic - each
   // is greater than the previous one.
   bool is_monotonic = true;
   bool is_sorted = true;
   for (uint32_t i = 1; i < values.size() && is_sorted; i++) {
     is_monotonic = is_monotonic && values[i - 1] < values[i];
     is_sorted = values[i - 1] <= values[i];
   }

   // The special treatement for Id columns makes no sense for empty or
   // single element indices. Those should be treated as standard int
   // column.

   // We expect id column to:
   // - be strictly monotonic.
   bool is_id = is_monotonic;
   // - have more than 1 element.
   is_id = is_id && values.size() > 1;
   // - have first elements smaller then 2^20, mostly to prevent timestamps
   // columns from becoming Id columns.
   is_id = is_id && values.front() < 1 << 20;
   // - have `uint32_t` values.
   is_id = is_id && values.front() >= std::numeric_limits<uint32_t>::min() &&
           values.back() < std::numeric_limits<uint32_t>::max();
   // - have on average more than 1 set bit per int64_t (over 1/64 density)
   is_id = is_id && static_cast<uint32_t>(values.back()) < 64 * values.size();

   if (is_id) {
     // The column is an Id column.
     storage_layers[col_idx].reset(new column::IdStorage());

     // If the id is dense (i.e. the start is zero and the size equals the last
     // value) then there's no need for an overlay.
     bool is_dense = values.front() == 0 &&
                     static_cast<uint32_t>(values.back()) == values.size() - 1;
     if (is_dense) {
       legacy_columns.push_back(
           ColumnLegacy::IdColumn(col_idx, 0, col_name, ColumnLegacy::kIdFlags));
     } else {
       legacy_overlays.emplace_back(BitVector::FromSortedIndexVector(values));
       overlay_layers.emplace_back().reset(new column::SelectorOverlay(
           legacy_overlays.back().row_map().GetIfBitVector()));
       legacy_columns.push_back(ColumnLegacy::IdColumn(
           col_idx, static_cast<uint32_t>(legacy_overlays.size() - 1), col_name,
           ColumnLegacy::kIdFlags));
     }
     return;
   }

   uint32_t flags =
       is_sorted ? ColumnLegacy::Flag::kNonNull | ColumnLegacy::Flag::kSorted
                 : ColumnLegacy::Flag::kNonNull;

   legacy_columns.emplace_back(col_name, ints_storage, flags, col_idx, 0);
   storage_layers[col_idx].reset(new column::NumericStorage<int64_t>(
       &values, ColumnType::kInt64, is_sorted));
 }

 }  // namespace

 RuntimeTable::RuntimeTable(
     StringPool* pool,
     uint32_t row_count,
     std::vector<ColumnLegacy> columns,
     std::vector<ColumnStorageOverlay> overlays,
     std::vector<RefPtr<column::StorageLayer>> storage_layers,
     std::vector<RefPtr<column::OverlayLayer>> null_layers,
     std::vector<RefPtr<column::OverlayLayer>> overlay_layers)
     : Table(pool, row_count, std::move(columns), std::move(overlays)) {
   OnConstructionCompleted(std::move(storage_layers), std::move(null_layers),
                           std::move(overlay_layers));
 }

 RuntimeTable::~RuntimeTable() = default;

 RuntimeTable::Builder::Builder(StringPool* pool,
                                const std::vector<std::string>& col_names)
     : Builder(pool,
               col_names,
               std::vector<BuilderColumnType>(col_names.size(), kNull)) {}

 RuntimeTable::Builder::Builder(StringPool* pool,
                                const std::vector<std::string>& col_names,
                                const std::vector<BuilderColumnType>& col_types)
     : string_pool_(pool), col_names_(col_names) {
   for (BuilderColumnType type : col_types) {
     switch (type) {
       case kNull:
         storage_.emplace_back(std::make_unique<VariantStorage>());
         break;
       case kInt:
         storage_.emplace_back(std::make_unique<VariantStorage>(IntStorage()));
         break;
       case kNullInt:
         storage_.emplace_back(
             std::make_unique<VariantStorage>(NullIntStorage()));
         break;
       case kDouble:
         storage_.emplace_back(
             std::make_unique<VariantStorage>(DoubleStorage()));
         break;
       case kNullDouble:
         storage_.emplace_back(
             std::make_unique<VariantStorage>(NullDoubleStorage()));
         break;
       case kString:
         storage_.emplace_back(
             std::make_unique<VariantStorage>(StringStorage()));
         break;
     }
   }
 }

 base::Status RuntimeTable::Builder::AddNull(uint32_t idx) {
   auto* col = storage_[idx].get();
   if (auto* leading_nulls = std::get_if<uint32_t>(col)) {
     (*leading_nulls)++;
   } else if (auto* ints = std::get_if<NullIntStorage>(col)) {
     ints->Append(std::nullopt);
   } else if (auto* strings = std::get_if<StringStorage>(col)) {
     strings->Append(StringPool::Id::Null());
   } else if (auto* doubles = std::get_if<NullDoubleStorage>(col)) {
     doubles->Append(std::nullopt);
   } else {
     PERFETTO_FATAL("Unexpected column type");
   }
   return base::OkStatus();
 }

 base::Status RuntimeTable::Builder::AddInteger(uint32_t idx, int64_t res) {
   auto* col = storage_[idx].get();
   if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
     *col = Fill<NullIntStorage>(*leading_nulls_ptr, std::nullopt);
   }
   if (auto* doubles = std::get_if<NullDoubleStorage>(col)) {
     if (!IsPerfectlyRepresentableAsDouble(res)) {
       return base::ErrStatus("Column %s contains %" PRId64
                              " which cannot be represented as a double",
                              col_names_[idx].c_str(), res);
     }
     doubles->Append(static_cast<double>(res));
     return base::OkStatus();
   }
   auto* ints = std::get_if<NullIntStorage>(col);
   if (!ints) {
     return base::ErrStatus("Column %s does not have consistent types",
                            col_names_[idx].c_str());
   }
   ints->Append(res);
   return base::OkStatus();
 }

 base::Status RuntimeTable::Builder::AddFloat(uint32_t idx, double res) {
   auto* col = storage_[idx].get();
   if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
     *col = Fill<NullDoubleStorage>(*leading_nulls_ptr, std::nullopt);
   }
   if (auto* ints = std::get_if<NullIntStorage>(col)) {
     NullDoubleStorage storage;
     for (uint32_t i = 0; i < ints->size(); ++i) {
       std::optional<int64_t> int_val = ints->Get(i);
       if (!int_val) {
         storage.Append(std::nullopt);
         continue;
       }
       if (int_val && !IsPerfectlyRepresentableAsDouble(*int_val)) {
         return base::ErrStatus("Column %s contains %" PRId64
                                " which cannot be represented as a double",
                                col_names_[idx].c_str(), *int_val);
       }
       storage.Append(static_cast<double>(*int_val));
     }
     *col = std::move(storage);
   }
   auto* doubles = std::get_if<NullDoubleStorage>(col);
   if (!doubles) {
     return base::ErrStatus("Column %s does not have consistent types",
                            col_names_[idx].c_str());
   }
   doubles->Append(res);
   return base::OkStatus();
 }

 base::Status RuntimeTable::Builder::AddText(uint32_t idx, const char* ptr) {
   auto* col = storage_[idx].get();
   if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
     *col = Fill<StringStorage>(*leading_nulls_ptr, StringPool::Id::Null());
   }
   auto* strings = std::get_if<StringStorage>(col);
   if (!strings) {
     return base::ErrStatus("Column %s does not have consistent types",
                            col_names_[idx].c_str());
   }
   strings->Append(string_pool_->InternString(ptr));
   return base::OkStatus();
 }

 base::Status RuntimeTable::Builder::AddIntegers(uint32_t idx,
                                                 int64_t val,
                                                 uint32_t count) {
   auto* col = storage_[idx].get();
   if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
     *col = Fill<NullIntStorage>(*leading_nulls_ptr, std::nullopt);
   }
   if (auto* doubles = std::get_if<NullDoubleStorage>(col)) {
     if (!IsPerfectlyRepresentableAsDouble(val)) {
       return base::ErrStatus("Column %s contains %" PRId64
                              " which cannot be represented as a double",
                              col_names_[idx].c_str(), val);
     }
     doubles->AppendMultiple(static_cast<double>(val), count);
     return base::OkStatus();
   }
   if (auto* null_ints = std::get_if<NullIntStorage>(col)) {
     null_ints->AppendMultiple(val, count);
     return base::OkStatus();
   }
   auto* ints = std::get_if<IntStorage>(col);
   if (!ints) {
     return base::ErrStatus("Column %s does not have consistent types",
                            col_names_[idx].c_str());
   }
   ints->AppendMultiple(val, count);
   return base::OkStatus();
 }

 base::Status RuntimeTable::Builder::AddFloats(uint32_t idx,
                                               double res,
                                               uint32_t count) {
   auto* col = storage_[idx].get();
   if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
     *col = Fill<NullDoubleStorage>(*leading_nulls_ptr, std::nullopt);
   }
   if (auto* ints = std::get_if<NullIntStorage>(col)) {
     NullDoubleStorage storage;
     for (uint32_t i = 0; i < ints->size(); ++i) {
       std::optional<int64_t> int_val = ints->Get(i);
       if (!int_val) {
         storage.AppendMultipleNulls(count);
         continue;
       }
       if (int_val && !IsPerfectlyRepresentableAsDouble(*int_val)) {
         return base::ErrStatus("Column %s contains %" PRId64
                                " which cannot be represented as a double",
                                col_names_[idx].c_str(), *int_val);
       }
       storage.AppendMultiple(static_cast<double>(*int_val), count);
     }
     *col = std::move(storage);
   }
   auto* doubles = std::get_if<NullDoubleStorage>(col);
   if (!doubles) {
     return base::ErrStatus("Column %s does not have consistent types",
                            col_names_[idx].c_str());
   }
   doubles->AppendMultiple(res, count);
   return base::OkStatus();
 }

 base::Status RuntimeTable::Builder::AddTexts(uint32_t idx,
                                              const char* ptr,
                                              uint32_t count) {
   auto* col = storage_[idx].get();
   if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
     *col = Fill<StringStorage>(*leading_nulls_ptr, StringPool::Id::Null());
   }
   auto* strings = std::get_if<StringStorage>(col);
   if (!strings) {
     return base::ErrStatus("Column %s does not have consistent types",
                            col_names_[idx].c_str());
   }
   strings->AppendMultiple(string_pool_->InternString(ptr), count);
   return base::OkStatus();
 }

 base::Status RuntimeTable::Builder::AddNulls(uint32_t idx, uint32_t count) {
   auto* col = storage_[idx].get();
   if (auto* leading_nulls = std::get_if<uint32_t>(col)) {
     (*leading_nulls)++;
   } else if (auto* ints = std::get_if<NullIntStorage>(col)) {
     ints->AppendMultipleNulls(count);
   } else if (auto* strings = std::get_if<StringStorage>(col)) {
     strings->AppendMultiple(StringPool::Id::Null(), count);
   } else if (auto* doubles = std::get_if<NullDoubleStorage>(col)) {
     doubles->AppendMultipleNulls(count);
   } else {
     PERFETTO_FATAL("Unexpected column type");
   }
   return base::OkStatus();
 }

 void RuntimeTable::Builder::AddNonNullIntegersUnchecked(
     uint32_t idx,
     const std::vector<int64_t>& res) {
   std::get<IntStorage>(*storage_[idx]).Append(res);
 }

 void RuntimeTable::Builder::AddNullIntegersUnchecked(
     uint32_t idx,
     const std::vector<int64_t>& res) {
   std::get<NullIntStorage>(*storage_[idx]).Append(res);
 }

 void RuntimeTable::Builder::AddNonNullDoublesUnchecked(
     uint32_t idx,
     const std::vector<double>& vals) {
   std::get<DoubleStorage>(*storage_[idx]).Append(vals);
 }

 void RuntimeTable::Builder::AddNullDoublesUnchecked(
     uint32_t idx,
     const std::vector<double>& vals) {
   std::get<NullDoubleStorage>(*storage_[idx]).Append(vals);
 }

 base::StatusOr<std::unique_ptr<RuntimeTable>> RuntimeTable::Builder::Build(
     uint32_t rows) && {
   std::vector<RefPtr<column::StorageLayer>> storage_layers(col_names_.size() +
                                                            1);
   std::vector<RefPtr<column::OverlayLayer>> null_layers(col_names_.size() + 1);

   std::vector<ColumnLegacy> legacy_columns;
   std::vector<ColumnStorageOverlay> legacy_overlays;

   // |overlay_layers| might use the RowMaps used by |legacy_overlays| and access
   // them by fetching the pointer to the RowMap inside overlay. We need to make
   // sure that those pointers will not change, hence we need to make sure that
   // the vector will not resize. In the current implementation there is at most
   // one overlay per column.
   legacy_overlays.reserve(col_names_.size() + 1);
   legacy_overlays.emplace_back(rows);
   std::vector<RefPtr<column::OverlayLayer>> overlay_layers(1);

   for (uint32_t i = 0; i < col_names_.size(); ++i) {
     auto* col = storage_[i].get();
     std::unique_ptr<column::DataLayerChain> chain;
     if (auto* leading_nulls = std::get_if<uint32_t>(col)) {
       PERFETTO_CHECK(*leading_nulls == rows);
       *col = Fill<NullIntStorage>(*leading_nulls, std::nullopt);
     }

     if (auto* null_ints = std::get_if<NullIntStorage>(col)) {
       // The `ints` column
       PERFETTO_CHECK(null_ints->size() == rows);

       if (null_ints->non_null_size() == null_ints->size()) {
         // The column doesn't have any nulls so we construct a new nonnullable
         // column.
         *col = IntStorage::CreateFromAssertNonNull(std::move(*null_ints));
         CreateNonNullableIntsColumn(
             i, col_names_[i].c_str(), std::get_if<IntStorage>(col),
             storage_layers, overlay_layers, legacy_columns, legacy_overlays);
       } else {
         // Nullable ints column.
         legacy_columns.emplace_back(col_names_[i].c_str(), null_ints,
                                     ColumnLegacy::Flag::kNoFlag, i, 0);
         storage_layers[i].reset(new column::NumericStorage<int64_t>(
             &null_ints->non_null_vector(), ColumnType::kInt64, false));
         null_layers[i].reset(
             new column::NullOverlay(&null_ints->non_null_bit_vector()));
       }

     } else if (auto* ints = std::get_if<IntStorage>(col)) {
       // The `ints` column for tables where column types was provided before.
       PERFETTO_CHECK(ints->size() == rows);
       CreateNonNullableIntsColumn(
           i, col_names_[i].c_str(), std::get_if<IntStorage>(col),
           storage_layers, overlay_layers, legacy_columns, legacy_overlays);

     } else if (auto* doubles = std::get_if<DoubleStorage>(col)) {
       // The `doubles` column for tables where column types was provided before.
       PERFETTO_CHECK(doubles->size() == rows);
       bool is_sorted =
           std::is_sorted(doubles->vector().begin(), doubles->vector().end());
       uint32_t flags =
           is_sorted ? ColumnLegacy::Flag::kNonNull | ColumnLegacy::Flag::kSorted
                     : ColumnLegacy::Flag::kNonNull;
       legacy_columns.emplace_back(col_names_[i].c_str(), doubles, flags, i, 0);
       storage_layers[i].reset(new column::NumericStorage<double>(
           &doubles->vector(), ColumnType::kDouble, is_sorted));

     } else if (auto* null_doubles = std::get_if<NullDoubleStorage>(col)) {
       // The doubles column.
       PERFETTO_CHECK(null_doubles->size() == rows);
       if (null_doubles->non_null_size() == null_doubles->size()) {
         // The column is not nullable.
         *col = DoubleStorage::CreateFromAssertNonNull(std::move(*null_doubles));

         auto* non_null_doubles = std::get_if<DoubleStorage>(col);
         bool is_sorted = std::is_sorted(non_null_doubles->vector().begin(),
                                         non_null_doubles->vector().end());
         uint32_t flags = is_sorted ? ColumnLegacy::Flag::kNonNull |
                                          ColumnLegacy::Flag::kSorted
                                    : ColumnLegacy::Flag::kNonNull;
         legacy_columns.emplace_back(col_names_[i].c_str(), non_null_doubles,
                                     flags, i, 0);
         storage_layers[i].reset(new column::NumericStorage<double>(
             &non_null_doubles->vector(), ColumnType::kDouble, is_sorted));
       } else {
         // The column is nullable.
         legacy_columns.emplace_back(col_names_[i].c_str(), null_doubles,
                                     ColumnLegacy::Flag::kNoFlag, i, 0);
         storage_layers[i].reset(new column::NumericStorage<double>(
             &null_doubles->non_null_vector(), ColumnType::kDouble, false));
         null_layers[i].reset(
             new column::NullOverlay(&null_doubles->non_null_bit_vector()));
       }

     } else if (auto* strings = std::get_if<StringStorage>(col)) {
       // The `strings` column.
       PERFETTO_CHECK(strings->size() == rows);
       legacy_columns.emplace_back(col_names_[i].c_str(), strings,
                                   ColumnLegacy::Flag::kNonNull, i, 0);
       storage_layers[i].reset(
           new column::StringStorage(string_pool_, &strings->vector()));
     } else {
       PERFETTO_FATAL("Unexpected column type");
     }
   }

   legacy_columns.push_back(ColumnLegacy::IdColumn(
       static_cast<uint32_t>(legacy_columns.size()), 0, "_auto_id",
       ColumnLegacy::kIdFlags | ColumnLegacy::Flag::kHidden));
   storage_layers.back().reset(new column::IdStorage());

   auto table = std::make_unique<RuntimeTable>(
       string_pool_, rows, std::move(legacy_columns), std::move(legacy_overlays),
       std::move(storage_layers), std::move(null_layers),
       std::move(overlay_layers));
   table->storage_ = std::move(storage_);
   table->col_names_ = std::move(col_names_);

   table->schema_.columns.reserve(table->columns().size());
   for (size_t i = 0; i < table->columns().size(); ++i) {
     const auto& col = table->columns()[i];
     SqlValue::Type column_type =
         col.col_type() != ColumnType::kId &&
                 col.storage_base().non_null_size() == 0
             ? SqlValue::kNull
             : ColumnLegacy::ToSqlValueType(col.col_type());
     table->schema_.columns.emplace_back(
         Schema::Column{col.name(), column_type, col.IsId(), col.IsSorted(),
                        col.IsHidden(), col.IsSetId()});
   }
   return {std::move(table)};
 }

 }  // namespace perfetto::trace_processor
	/*
	* 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.
	*/

	#include "src/trace_processor/db/runtime_table.h"

	#include <algorithm>
	#include <cinttypes>
	#include <cstddef>
	#include <cstdint>
	#include <limits>
	#include <memory>
	#include <optional>
	#include <string>
	#include <utility>
	#include <variant>
	#include <vector>

	#include "perfetto/base/logging.h"
	#include "perfetto/base/status.h"
	#include "perfetto/ext/base/status_or.h"
	#include "perfetto/trace_processor/basic_types.h"
	#include "perfetto/trace_processor/ref_counted.h"
	#include "src/trace_processor/containers/bit_vector.h"
	#include "src/trace_processor/containers/string_pool.h"
	#include "src/trace_processor/db/column.h"
	#include "src/trace_processor/db/column/data_layer.h"
	#include "src/trace_processor/db/column/id_storage.h"
	#include "src/trace_processor/db/column/null_overlay.h"
	#include "src/trace_processor/db/column/numeric_storage.h"
	#include "src/trace_processor/db/column/overlay_layer.h"
	#include "src/trace_processor/db/column/selector_overlay.h"
	#include "src/trace_processor/db/column/storage_layer.h"
	#include "src/trace_processor/db/column/string_storage.h"
	#include "src/trace_processor/db/column/types.h"
	#include "src/trace_processor/db/column_storage.h"
	#include "src/trace_processor/db/column_storage_overlay.h"

	namespace perfetto::trace_processor {
	namespace {

	template <typename T, typename U>
	T Fill(uint32_t leading_nulls, U value) {
	T res;
	for (uint32_t i = 0; i < leading_nulls; ++i) {
	res.Append(value);
	}
	return res;
	}

	bool IsPerfectlyRepresentableAsDouble(int64_t res) {
	static constexpr int64_t kMaxDoubleRepresentible = 1ull << 53;
	return res >= -kMaxDoubleRepresentible && res <= kMaxDoubleRepresentible;
	}

	void CreateNonNullableIntsColumn(
	uint32_t col_idx,
	const char* col_name,
	ColumnStorage<int64_t>* ints_storage,
	std::vector<RefPtr<column::StorageLayer>>& storage_layers,
	std::vector<RefPtr<column::OverlayLayer>>& overlay_layers,
	std::vector<ColumnLegacy>& legacy_columns,
	std::vector<ColumnStorageOverlay>& legacy_overlays) {
	const std::vector<int64_t>& values = ints_storage->vector();

	// Looking for the iterator to the first value that is less or equal to the
	// previous value. The values before are therefore strictly monotonic - each
	// is greater than the previous one.
	bool is_monotonic = true;
	bool is_sorted = true;
	for (uint32_t i = 1; i < values.size() && is_sorted; i++) {
	is_monotonic = is_monotonic && values[i - 1] < values[i];
	is_sorted = values[i - 1] <= values[i];
	}

	// The special treatement for Id columns makes no sense for empty or
	// single element indices. Those should be treated as standard int
	// column.

	// We expect id column to:
	// - be strictly monotonic.
	bool is_id = is_monotonic;
	// - have more than 1 element.
	is_id = is_id && values.size() > 1;
	// - have first elements smaller then 2^20, mostly to prevent timestamps
	// columns from becoming Id columns.
	is_id = is_id && values.front() < 1 << 20;
	// - have `uint32_t` values.
	is_id = is_id && values.front() >= std::numeric_limits<uint32_t>::min() &&
	values.back() < std::numeric_limits<uint32_t>::max();
	// - have on average more than 1 set bit per int64_t (over 1/64 density)
	is_id = is_id && static_cast<uint32_t>(values.back()) < 64 * values.size();

	if (is_id) {
	// The column is an Id column.
	storage_layers[col_idx].reset(new column::IdStorage());

	// If the id is dense (i.e. the start is zero and the size equals the last
	// value) then there's no need for an overlay.
	bool is_dense = values.front() == 0 &&
	static_cast<uint32_t>(values.back()) == values.size() - 1;
	if (is_dense) {
	legacy_columns.push_back(
	ColumnLegacy::IdColumn(col_idx, 0, col_name, ColumnLegacy::kIdFlags));
	} else {
	legacy_overlays.emplace_back(BitVector::FromSortedIndexVector(values));
	overlay_layers.emplace_back().reset(new column::SelectorOverlay(
	legacy_overlays.back().row_map().GetIfBitVector()));
	legacy_columns.push_back(ColumnLegacy::IdColumn(
	col_idx, static_cast<uint32_t>(legacy_overlays.size() - 1), col_name,
	ColumnLegacy::kIdFlags));
	}
	return;
	}

	uint32_t flags =
	is_sorted ? ColumnLegacy::Flag::kNonNull \| ColumnLegacy::Flag::kSorted
	: ColumnLegacy::Flag::kNonNull;

	legacy_columns.emplace_back(col_name, ints_storage, flags, col_idx, 0);
	storage_layers[col_idx].reset(new column::NumericStorage<int64_t>(
	&values, ColumnType::kInt64, is_sorted));
	}

	} // namespace

	RuntimeTable::RuntimeTable(
	StringPool* pool,
	uint32_t row_count,
	std::vector<ColumnLegacy> columns,
	std::vector<ColumnStorageOverlay> overlays,
	std::vector<RefPtr<column::StorageLayer>> storage_layers,
	std::vector<RefPtr<column::OverlayLayer>> null_layers,
	std::vector<RefPtr<column::OverlayLayer>> overlay_layers)
	: Table(pool, row_count, std::move(columns), std::move(overlays)) {
	OnConstructionCompleted(std::move(storage_layers), std::move(null_layers),
	std::move(overlay_layers));
	}

	RuntimeTable::~RuntimeTable() = default;

	RuntimeTable::Builder::Builder(StringPool* pool,
	const std::vector<std::string>& col_names)
	: Builder(pool,
	col_names,
	std::vector<BuilderColumnType>(col_names.size(), kNull)) {}

	RuntimeTable::Builder::Builder(StringPool* pool,
	const std::vector<std::string>& col_names,
	const std::vector<BuilderColumnType>& col_types)
	: string_pool_(pool), col_names_(col_names) {
	for (BuilderColumnType type : col_types) {
	switch (type) {
	case kNull:
	storage_.emplace_back(std::make_unique<VariantStorage>());
	break;
	case kInt:
	storage_.emplace_back(std::make_unique<VariantStorage>(IntStorage()));
	break;
	case kNullInt:
	storage_.emplace_back(
	std::make_unique<VariantStorage>(NullIntStorage()));
	break;
	case kDouble:
	storage_.emplace_back(
	std::make_unique<VariantStorage>(DoubleStorage()));
	break;
	case kNullDouble:
	storage_.emplace_back(
	std::make_unique<VariantStorage>(NullDoubleStorage()));
	break;
	case kString:
	storage_.emplace_back(
	std::make_unique<VariantStorage>(StringStorage()));
	break;
	}
	}
	}

	base::Status RuntimeTable::Builder::AddNull(uint32_t idx) {
	auto* col = storage_[idx].get();
	if (auto* leading_nulls = std::get_if<uint32_t>(col)) {
	(*leading_nulls)++;
	} else if (auto* ints = std::get_if<NullIntStorage>(col)) {
	ints->Append(std::nullopt);
	} else if (auto* strings = std::get_if<StringStorage>(col)) {
	strings->Append(StringPool::Id::Null());
	} else if (auto* doubles = std::get_if<NullDoubleStorage>(col)) {
	doubles->Append(std::nullopt);
	} else {
	PERFETTO_FATAL("Unexpected column type");
	}
	return base::OkStatus();
	}

	base::Status RuntimeTable::Builder::AddInteger(uint32_t idx, int64_t res) {
	auto* col = storage_[idx].get();
	if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
	col = Fill<NullIntStorage>(leading_nulls_ptr, std::nullopt);
	}
	if (auto* doubles = std::get_if<NullDoubleStorage>(col)) {
	if (!IsPerfectlyRepresentableAsDouble(res)) {
	return base::ErrStatus("Column %s contains %" PRId64
	" which cannot be represented as a double",
	col_names_[idx].c_str(), res);
	}
	doubles->Append(static_cast<double>(res));
	return base::OkStatus();
	}
	auto* ints = std::get_if<NullIntStorage>(col);
	if (!ints) {
	return base::ErrStatus("Column %s does not have consistent types",
	col_names_[idx].c_str());
	}
	ints->Append(res);
	return base::OkStatus();
	}

	base::Status RuntimeTable::Builder::AddFloat(uint32_t idx, double res) {
	auto* col = storage_[idx].get();
	if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
	col = Fill<NullDoubleStorage>(leading_nulls_ptr, std::nullopt);
	}
	if (auto* ints = std::get_if<NullIntStorage>(col)) {
	NullDoubleStorage storage;
	for (uint32_t i = 0; i < ints->size(); ++i) {
	std::optional<int64_t> int_val = ints->Get(i);
	if (!int_val) {
	storage.Append(std::nullopt);
	continue;
	}
	if (int_val && !IsPerfectlyRepresentableAsDouble(*int_val)) {
	return base::ErrStatus("Column %s contains %" PRId64
	" which cannot be represented as a double",
	col_names_[idx].c_str(), *int_val);
	}
	storage.Append(static_cast<double>(*int_val));
	}
	*col = std::move(storage);
	}
	auto* doubles = std::get_if<NullDoubleStorage>(col);
	if (!doubles) {
	return base::ErrStatus("Column %s does not have consistent types",
	col_names_[idx].c_str());
	}
	doubles->Append(res);
	return base::OkStatus();
	}

	base::Status RuntimeTable::Builder::AddText(uint32_t idx, const char* ptr) {
	auto* col = storage_[idx].get();
	if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
	col = Fill<StringStorage>(leading_nulls_ptr, StringPool::Id::Null());
	}
	auto* strings = std::get_if<StringStorage>(col);
	if (!strings) {
	return base::ErrStatus("Column %s does not have consistent types",
	col_names_[idx].c_str());
	}
	strings->Append(string_pool_->InternString(ptr));
	return base::OkStatus();
	}

	base::Status RuntimeTable::Builder::AddIntegers(uint32_t idx,
	int64_t val,
	uint32_t count) {
	auto* col = storage_[idx].get();
	if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
	col = Fill<NullIntStorage>(leading_nulls_ptr, std::nullopt);
	}
	if (auto* doubles = std::get_if<NullDoubleStorage>(col)) {
	if (!IsPerfectlyRepresentableAsDouble(val)) {
	return base::ErrStatus("Column %s contains %" PRId64
	" which cannot be represented as a double",
	col_names_[idx].c_str(), val);
	}
	doubles->AppendMultiple(static_cast<double>(val), count);
	return base::OkStatus();
	}
	if (auto* null_ints = std::get_if<NullIntStorage>(col)) {
	null_ints->AppendMultiple(val, count);
	return base::OkStatus();
	}
	auto* ints = std::get_if<IntStorage>(col);
	if (!ints) {
	return base::ErrStatus("Column %s does not have consistent types",
	col_names_[idx].c_str());
	}
	ints->AppendMultiple(val, count);
	return base::OkStatus();
	}

	base::Status RuntimeTable::Builder::AddFloats(uint32_t idx,
	double res,
	uint32_t count) {
	auto* col = storage_[idx].get();
	if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
	col = Fill<NullDoubleStorage>(leading_nulls_ptr, std::nullopt);
	}
	if (auto* ints = std::get_if<NullIntStorage>(col)) {
	NullDoubleStorage storage;
	for (uint32_t i = 0; i < ints->size(); ++i) {
	std::optional<int64_t> int_val = ints->Get(i);
	if (!int_val) {
	storage.AppendMultipleNulls(count);
	continue;
	}
	if (int_val && !IsPerfectlyRepresentableAsDouble(*int_val)) {
	return base::ErrStatus("Column %s contains %" PRId64
	" which cannot be represented as a double",
	col_names_[idx].c_str(), *int_val);
	}
	storage.AppendMultiple(static_cast<double>(*int_val), count);
	}
	*col = std::move(storage);
	}
	auto* doubles = std::get_if<NullDoubleStorage>(col);
	if (!doubles) {
	return base::ErrStatus("Column %s does not have consistent types",
	col_names_[idx].c_str());
	}
	doubles->AppendMultiple(res, count);
	return base::OkStatus();
	}

	base::Status RuntimeTable::Builder::AddTexts(uint32_t idx,
	const char* ptr,
	uint32_t count) {
	auto* col = storage_[idx].get();
	if (auto* leading_nulls_ptr = std::get_if<uint32_t>(col)) {
	col = Fill<StringStorage>(leading_nulls_ptr, StringPool::Id::Null());
	}
	auto* strings = std::get_if<StringStorage>(col);
	if (!strings) {
	return base::ErrStatus("Column %s does not have consistent types",
	col_names_[idx].c_str());
	}
	strings->AppendMultiple(string_pool_->InternString(ptr), count);
	return base::OkStatus();
	}

	base::Status RuntimeTable::Builder::AddNulls(uint32_t idx, uint32_t count) {
	auto* col = storage_[idx].get();
	if (auto* leading_nulls = std::get_if<uint32_t>(col)) {
	(*leading_nulls)++;
	} else if (auto* ints = std::get_if<NullIntStorage>(col)) {
	ints->AppendMultipleNulls(count);
	} else if (auto* strings = std::get_if<StringStorage>(col)) {
	strings->AppendMultiple(StringPool::Id::Null(), count);
	} else if (auto* doubles = std::get_if<NullDoubleStorage>(col)) {
	doubles->AppendMultipleNulls(count);
	} else {
	PERFETTO_FATAL("Unexpected column type");
	}
	return base::OkStatus();
	}

	void RuntimeTable::Builder::AddNonNullIntegersUnchecked(
	uint32_t idx,
	const std::vector<int64_t>& res) {
	std::get<IntStorage>(*storage_[idx]).Append(res);
	}

	void RuntimeTable::Builder::AddNullIntegersUnchecked(
	uint32_t idx,
	const std::vector<int64_t>& res) {
	std::get<NullIntStorage>(*storage_[idx]).Append(res);
	}

	void RuntimeTable::Builder::AddNonNullDoublesUnchecked(
	uint32_t idx,
	const std::vector<double>& vals) {
	std::get<DoubleStorage>(*storage_[idx]).Append(vals);
	}

	void RuntimeTable::Builder::AddNullDoublesUnchecked(
	uint32_t idx,
	const std::vector<double>& vals) {
	std::get<NullDoubleStorage>(*storage_[idx]).Append(vals);
	}

	base::StatusOr<std::unique_ptr<RuntimeTable>> RuntimeTable::Builder::Build(
	uint32_t rows) && {
	std::vector<RefPtr<column::StorageLayer>> storage_layers(col_names_.size() +
	1);
	std::vector<RefPtr<column::OverlayLayer>> null_layers(col_names_.size() + 1);

	std::vector<ColumnLegacy> legacy_columns;
	std::vector<ColumnStorageOverlay> legacy_overlays;

	// \|overlay_layers\| might use the RowMaps used by \|legacy_overlays\| and access
	// them by fetching the pointer to the RowMap inside overlay. We need to make
	// sure that those pointers will not change, hence we need to make sure that
	// the vector will not resize. In the current implementation there is at most
	// one overlay per column.
	legacy_overlays.reserve(col_names_.size() + 1);
	legacy_overlays.emplace_back(rows);
	std::vector<RefPtr<column::OverlayLayer>> overlay_layers(1);

	for (uint32_t i = 0; i < col_names_.size(); ++i) {
	auto* col = storage_[i].get();
	std::unique_ptr<column::DataLayerChain> chain;
	if (auto* leading_nulls = std::get_if<uint32_t>(col)) {
	PERFETTO_CHECK(*leading_nulls == rows);
	col = Fill<NullIntStorage>(leading_nulls, std::nullopt);
	}

	if (auto* null_ints = std::get_if<NullIntStorage>(col)) {
	// The `ints` column
	PERFETTO_CHECK(null_ints->size() == rows);

	if (null_ints->non_null_size() == null_ints->size()) {
	// The column doesn't have any nulls so we construct a new nonnullable
	// column.
	col = IntStorage::CreateFromAssertNonNull(std::move(null_ints));
	CreateNonNullableIntsColumn(
	i, col_names_[i].c_str(), std::get_if<IntStorage>(col),
	storage_layers, overlay_layers, legacy_columns, legacy_overlays);
	} else {
	// Nullable ints column.
	legacy_columns.emplace_back(col_names_[i].c_str(), null_ints,
	ColumnLegacy::Flag::kNoFlag, i, 0);
	storage_layers[i].reset(new column::NumericStorage<int64_t>(
	&null_ints->non_null_vector(), ColumnType::kInt64, false));
	null_layers[i].reset(
	new column::NullOverlay(&null_ints->non_null_bit_vector()));
	}

	} else if (auto* ints = std::get_if<IntStorage>(col)) {
	// The `ints` column for tables where column types was provided before.
	PERFETTO_CHECK(ints->size() == rows);
	CreateNonNullableIntsColumn(
	i, col_names_[i].c_str(), std::get_if<IntStorage>(col),
	storage_layers, overlay_layers, legacy_columns, legacy_overlays);

	} else if (auto* doubles = std::get_if<DoubleStorage>(col)) {
	// The `doubles` column for tables where column types was provided before.
	PERFETTO_CHECK(doubles->size() == rows);
	bool is_sorted =
	std::is_sorted(doubles->vector().begin(), doubles->vector().end());
	uint32_t flags =
	is_sorted ? ColumnLegacy::Flag::kNonNull \| ColumnLegacy::Flag::kSorted
	: ColumnLegacy::Flag::kNonNull;
	legacy_columns.emplace_back(col_names_[i].c_str(), doubles, flags, i, 0);
	storage_layers[i].reset(new column::NumericStorage<double>(
	&doubles->vector(), ColumnType::kDouble, is_sorted));

	} else if (auto* null_doubles = std::get_if<NullDoubleStorage>(col)) {
	// The doubles column.
	PERFETTO_CHECK(null_doubles->size() == rows);
	if (null_doubles->non_null_size() == null_doubles->size()) {
	// The column is not nullable.
	col = DoubleStorage::CreateFromAssertNonNull(std::move(null_doubles));

	auto* non_null_doubles = std::get_if<DoubleStorage>(col);
	bool is_sorted = std::is_sorted(non_null_doubles->vector().begin(),
	non_null_doubles->vector().end());
	uint32_t flags = is_sorted ? ColumnLegacy::Flag::kNonNull \|
	ColumnLegacy::Flag::kSorted
	: ColumnLegacy::Flag::kNonNull;
	legacy_columns.emplace_back(col_names_[i].c_str(), non_null_doubles,
	flags, i, 0);
	storage_layers[i].reset(new column::NumericStorage<double>(
	&non_null_doubles->vector(), ColumnType::kDouble, is_sorted));
	} else {
	// The column is nullable.
	legacy_columns.emplace_back(col_names_[i].c_str(), null_doubles,
	ColumnLegacy::Flag::kNoFlag, i, 0);
	storage_layers[i].reset(new column::NumericStorage<double>(
	&null_doubles->non_null_vector(), ColumnType::kDouble, false));
	null_layers[i].reset(
	new column::NullOverlay(&null_doubles->non_null_bit_vector()));
	}

	} else if (auto* strings = std::get_if<StringStorage>(col)) {
	// The `strings` column.
	PERFETTO_CHECK(strings->size() == rows);
	legacy_columns.emplace_back(col_names_[i].c_str(), strings,
	ColumnLegacy::Flag::kNonNull, i, 0);
	storage_layers[i].reset(
	new column::StringStorage(string_pool_, &strings->vector()));
	} else {
	PERFETTO_FATAL("Unexpected column type");
	}
	}

	legacy_columns.push_back(ColumnLegacy::IdColumn(
	static_cast<uint32_t>(legacy_columns.size()), 0, "_auto_id",
	ColumnLegacy::kIdFlags \| ColumnLegacy::Flag::kHidden));
	storage_layers.back().reset(new column::IdStorage());

	auto table = std::make_unique<RuntimeTable>(
	string_pool_, rows, std::move(legacy_columns), std::move(legacy_overlays),
	std::move(storage_layers), std::move(null_layers),
	std::move(overlay_layers));
	table->storage_ = std::move(storage_);
	table->col_names_ = std::move(col_names_);

	table->schema_.columns.reserve(table->columns().size());
	for (size_t i = 0; i < table->columns().size(); ++i) {
	const auto& col = table->columns()[i];
	SqlValue::Type column_type =
	col.col_type() != ColumnType::kId &&
	col.storage_base().non_null_size() == 0
	? SqlValue::kNull
	: ColumnLegacy::ToSqlValueType(col.col_type());
	table->schema_.columns.emplace_back(
	Schema::Column{col.name(), column_type, col.IsId(), col.IsSorted(),
	col.IsHidden(), col.IsSetId()});
	}
	return {std::move(table)};
	}

	} // namespace perfetto::trace_processor