Merge "tp: Unittest fake storage" into main

5 files changed, 248 insertions, 32 deletions

diff --git a/Android.bp b/Android.bp
index 04d53c273..94b84ff36 100644
--- a/Android.bp
+++ b/Android.bp
@@ -11348,6 +11348,7 @@ filegroup {
     srcs: [
         "src/trace_processor/db/column/arrangement_overlay_unittest.cc",
         "src/trace_processor/db/column/dense_null_overlay_unittest.cc",
+        "src/trace_processor/db/column/fake_storage_unittest.cc",
         "src/trace_processor/db/column/id_storage_unittest.cc",
         "src/trace_processor/db/column/null_overlay_unittest.cc",
         "src/trace_processor/db/column/numeric_storage_unittest.cc",
diff --git a/src/trace_processor/db/column/BUILD.gn b/src/trace_processor/db/column/BUILD.gn
index 74d16110f..d53e7ae23 100644
--- a/src/trace_processor/db/column/BUILD.gn
+++ b/src/trace_processor/db/column/BUILD.gn
@@ -75,6 +75,7 @@ perfetto_unittest_source_set("unittests") {
   sources = [
     "arrangement_overlay_unittest.cc",
     "dense_null_overlay_unittest.cc",
+    "fake_storage_unittest.cc",
     "id_storage_unittest.cc",
     "null_overlay_unittest.cc",
     "numeric_storage_unittest.cc",
diff --git a/src/trace_processor/db/column/fake_storage.cc b/src/trace_processor/db/column/fake_storage.cc
index f587c7787..babfb7c4d 100644
--- a/src/trace_processor/db/column/fake_storage.cc
+++ b/src/trace_processor/db/column/fake_storage.cc
@@ -41,6 +41,7 @@ FakeStorageChain::FakeStorageChain(uint32_t size,
 SingleSearchResult FakeStorageChain::SingleSearch(FilterOp,
                                                   SqlValue,
                                                   uint32_t i) const {
+  PERFETTO_CHECK(i < size_);
   switch (strategy_) {
     case kAll:
       return SingleSearchResult::kMatch;
@@ -115,37 +116,37 @@ Range FakeStorageChain::OrderedIndexSearchValidated(
     FilterOp,
     SqlValue,
     const OrderedIndices& indices) const {
-  if (strategy_ == kAll) {
-    return {0, indices.size};
-  }
-
-  if (strategy_ == kNone) {
-    return {};
-  }
-
-  if (strategy_ == kRange) {
-    // We are looking at intersection of |range_| and |indices_|.
-    const uint32_t* first_in_range = std::partition_point(
-        indices.data, indices.data + indices.size,
-        [this](uint32_t i) { return !range_.Contains(i); });
-    const uint32_t* first_outside_range =
-        std::partition_point(first_in_range, indices.data + indices.size,
-                             [this](uint32_t i) { return range_.Contains(i); });
-    return {static_cast<uint32_t>(std::distance(indices.data, first_in_range)),
-            static_cast<uint32_t>(
-                std::distance(indices.data, first_outside_range))};
-  }
-
-  PERFETTO_DCHECK(strategy_ == kBitVector);
-  // We are looking at intersection of |range_| and |bit_vector_|.
-  const uint32_t* first_set = std::partition_point(
-      indices.data, indices.data + indices.size,
-      [this](uint32_t i) { return !bit_vector_.IsSet(i); });
-  const uint32_t* first_non_set =
-      std::partition_point(first_set, indices.data + indices.size,
-                           [this](uint32_t i) { return bit_vector_.IsSet(i); });
-  return {static_cast<uint32_t>(std::distance(indices.data, first_set)),
+  switch (strategy_) {
+    case kAll:
+      return {0, indices.size};
+    case kNone:
+      return {};
+    case kRange: {
+      // We are looking at intersection of |range_| and |indices_|.
+      const uint32_t* first_in_range = std::partition_point(
+          indices.data, indices.data + indices.size,
+          [this](uint32_t i) { return !range_.Contains(i); });
+      const uint32_t* first_outside_range = std::partition_point(
+          first_in_range, indices.data + indices.size,
+          [this](uint32_t i) { return range_.Contains(i); });
+      return {
+          static_cast<uint32_t>(std::distance(indices.data, first_in_range)),
+          static_cast<uint32_t>(
+              std::distance(indices.data, first_outside_range))};
+    }
+    case kBitVector:
+      // We are looking at intersection of |range_| and |bit_vector_|.
+      const uint32_t* first_set = std::partition_point(
+          indices.data, indices.data + indices.size,
+          [this](uint32_t i) { return !bit_vector_.IsSet(i); });
+      const uint32_t* first_non_set = std::partition_point(
+          first_set, indices.data + indices.size,
+          [this](uint32_t i) { return bit_vector_.IsSet(i); });
+      return {
+          static_cast<uint32_t>(std::distance(indices.data, first_set)),
           static_cast<uint32_t>(std::distance(indices.data, first_non_set))};
+  }
+  PERFETTO_FATAL("For GCC");
 }
 
 void FakeStorageChain::StableSort(SortToken*, SortToken*, SortDirection) const {
diff --git a/src/trace_processor/db/column/fake_storage_unittest.cc b/src/trace_processor/db/column/fake_storage_unittest.cc
new file mode 100644
index 000000000..0bc02119e
--- /dev/null
+++ b/src/trace_processor/db/column/fake_storage_unittest.cc
@@ -0,0 +1,210 @@
+/*
+ * Copyright (C) 2024 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/column/fake_storage.h"
+
+#include <cstdint>
+#include <limits>
+#include <vector>
+
+#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/db/column/data_layer.h"
+#include "src/trace_processor/db/column/types.h"
+#include "src/trace_processor/db/column/utils.h"
+#include "test/gtest_and_gmock.h"
+
+namespace perfetto::trace_processor {
+
+inline bool operator==(const Range& a, const Range& b) {
+  return std::tie(a.start, a.end) == std::tie(b.start, b.end);
+}
+
+inline bool operator==(const BitVector& a, const BitVector& b) {
+  return a.size() == b.size() && a.CountSetBits() == b.CountSetBits();
+}
+
+namespace column {
+namespace {
+
+using testing::ElementsAre;
+using testing::IsEmpty;
+
+using Indices = DataLayerChain::Indices;
+using OrderedIndices = DataLayerChain::OrderedIndices;
+
+TEST(FakeStorage, ValidateSearchConstraints) {
+  {
+    // All passes
+    auto fake = FakeStorageChain::SearchAll(10);
+    EXPECT_EQ(fake->ValidateSearchConstraints(FilterOp::kEq, SqlValue()),
+              SearchValidationResult::kOk);
+  }
+  {
+    // None passes
+    auto fake = FakeStorageChain::SearchNone(10);
+    EXPECT_EQ(fake->ValidateSearchConstraints(FilterOp::kEq, SqlValue()),
+              SearchValidationResult::kOk);
+  }
+  {
+    // Index vector
+    auto fake =
+        FakeStorageChain::SearchSubset(5, std::vector<uint32_t>{1, 2, 3, 4, 5});
+    EXPECT_EQ(fake->ValidateSearchConstraints(FilterOp::kEq, SqlValue()),
+              SearchValidationResult::kOk);
+  }
+  {
+    // BitVector
+    auto fake = FakeStorageChain::SearchSubset(5, BitVector{0, 1, 0, 1, 0});
+    EXPECT_EQ(fake->ValidateSearchConstraints(FilterOp::kEq, SqlValue()),
+              SearchValidationResult::kOk);
+  }
+  {
+    // Range
+    auto fake = FakeStorageChain::SearchSubset(5, Range(1, 4));
+    EXPECT_EQ(fake->ValidateSearchConstraints(FilterOp::kEq, SqlValue()),
+              SearchValidationResult::kOk);
+  }
+}
+
+TEST(FakeStorage, SingleSearch) {
+  {
+    // All passes
+    auto fake = FakeStorageChain::SearchAll(10);
+    EXPECT_EQ(fake->SingleSearch(FilterOp::kEq, SqlValue(), 5u),
+              SingleSearchResult::kMatch);
+  }
+  {
+    // None passes
+    auto fake = FakeStorageChain::SearchNone(10);
+    EXPECT_EQ(fake->SingleSearch(FilterOp::kEq, SqlValue(), 5u),
+              SingleSearchResult::kNoMatch);
+  }
+  {
+    // Index vector
+    auto fake =
+        FakeStorageChain::SearchSubset(5, std::vector<uint32_t>{1, 2, 3, 4, 5});
+    EXPECT_EQ(fake->SingleSearch(FilterOp::kEq, SqlValue(), 0u),
+              SingleSearchResult::kNoMatch);
+    EXPECT_EQ(fake->SingleSearch(FilterOp::kEq, SqlValue(), 1u),
+              SingleSearchResult::kMatch);
+  }
+  {
+    // BitVector
+    auto fake = FakeStorageChain::SearchSubset(5, BitVector{0, 1, 0, 1, 0});
+    EXPECT_EQ(fake->SingleSearch(FilterOp::kEq, SqlValue(), 0),
+              SingleSearchResult::kNoMatch);
+    EXPECT_EQ(fake->SingleSearch(FilterOp::kEq, SqlValue(), 1u),
+              SingleSearchResult::kMatch);
+  }
+  {
+    // Range
+    auto fake = FakeStorageChain::SearchSubset(5, Range(1, 4));
+    EXPECT_EQ(fake->SingleSearch(FilterOp::kEq, SqlValue(), 0),
+              SingleSearchResult::kNoMatch);
+    EXPECT_EQ(fake->SingleSearch(FilterOp::kEq, SqlValue(), 1u),
+              SingleSearchResult::kMatch);
+  }
+}
+
+TEST(FakeStorage, IndexSearchValidated) {
+  {
+    // All passes
+    Indices indices = Indices::CreateWithIndexPayloadForTesting(
+        {1u, 0u, 3u}, Indices::State::kNonmonotonic);
+    auto fake = FakeStorageChain::SearchAll(5);
+    fake->IndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+    ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
+  }
+  {
+    // None passes
+    Indices indices = Indices::CreateWithIndexPayloadForTesting(
+        {1u, 0u, 3u}, Indices::State::kNonmonotonic);
+    auto fake = FakeStorageChain::SearchNone(5);
+    fake->IndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+    EXPECT_TRUE(utils::ExtractPayloadForTesting(indices).empty());
+  }
+  {
+    // BitVector
+    Indices indices = Indices::CreateWithIndexPayloadForTesting(
+        {1u, 0u, 3u}, Indices::State::kNonmonotonic);
+    auto fake = FakeStorageChain::SearchSubset(5, BitVector{0, 1, 0, 1, 0});
+    fake->IndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+    ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2));
+  }
+  {
+    // Index vector
+    Indices indices = Indices::CreateWithIndexPayloadForTesting(
+        {1u, 0u, 3u}, Indices::State::kNonmonotonic);
+    auto fake =
+        FakeStorageChain::SearchSubset(5, std::vector<uint32_t>{1, 2, 3});
+    fake->IndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+    ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2));
+  }
+  {
+    // Range
+    Indices indices = Indices::CreateWithIndexPayloadForTesting(
+        {1u, 0u, 3u}, Indices::State::kNonmonotonic);
+    auto fake = FakeStorageChain::SearchSubset(5, Range(1, 4));
+    fake->IndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+    ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2));
+  }
+}
+
+TEST(FakeStorage, OrderedIndexSearchValidated) {
+  std::vector<uint32_t> table_idx{4, 3, 2, 1};
+  OrderedIndices indices{table_idx.data(), uint32_t(table_idx.size()),
+                         Indices::State::kNonmonotonic};
+  {
+    // All passes
+    auto fake = FakeStorageChain::SearchAll(5);
+    Range ret =
+        fake->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+    EXPECT_EQ(ret, Range(0, 4));
+  }
+  {
+    // None passes
+    auto fake = FakeStorageChain::SearchNone(5);
+    Range ret =
+        fake->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+    EXPECT_EQ(ret, Range(0, 0));
+  }
+  {
+    // BitVector
+    auto fake = FakeStorageChain::SearchSubset(5, BitVector{0, 0, 1, 1, 1});
+    Range ret =
+        fake->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+    EXPECT_EQ(ret, Range(0, 3));
+  }
+  {
+    // Index vector
+    auto fake =
+        FakeStorageChain::SearchSubset(5, std::vector<uint32_t>{1, 2, 3});
+    Range ret =
+        fake->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+    EXPECT_EQ(ret, Range(1, 4));
+  }
+  {
+    // Range
+    auto fake = FakeStorageChain::SearchSubset(5, Range(1, 4));
+    Range ret =
+        fake->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+    EXPECT_EQ(ret, Range(1, 4));
+  }
+}
+
+}  // namespace
+}  // namespace column
+}  // namespace perfetto::trace_processor
diff --git a/src/trace_processor/db/column/range_overlay_unittest.cc b/src/trace_processor/db/column/range_overlay_unittest.cc
index a965be36c..240e998ce 100644
--- a/src/trace_processor/db/column/range_overlay_unittest.cc
+++ b/src/trace_processor/db/column/range_overlay_unittest.cc
@@ -95,14 +95,17 @@ TEST(RangeOverlay, SearchBitVector) {
 TEST(RangeOverlay, IndexSearch) {
   auto fake =
       FakeStorageChain::SearchSubset(8, BitVector({0, 1, 0, 1, 0, 1, 0, 0}));
+
+  // {true, false}
   Range range(3, 5);
   RangeOverlay storage(&range);
   auto chain = storage.MakeChain(std::move(fake));
 
+  // {true, false, true}
   Indices indices = Indices::CreateWithIndexPayloadForTesting(
-      {1u, 0u, 3u}, Indices::State::kNonmonotonic);
+      {0, 1, 0}, Indices::State::kNonmonotonic);
   chain->IndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
-  ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1u));
+  ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2));
 }
 
 TEST(RangeOverlay, StableSort) {