label_manager_unittest.cc

// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "courgette/label_manager.h"

#include <stddef.h>
#include <stdint.h>

#include <iterator>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>

#include "base/logging.h"
#include "base/macros.h"
#include "testing/gtest/include/gtest/gtest.h"

namespace courgette {

namespace {

// Test version of RvaVisitor: Just wrap std::vector<RVA>.
class TestRvaVisitor : public LabelManagerImpl::RvaVisitor {
 public:
  explicit TestRvaVisitor(std::vector<RVA>::const_iterator rva_begin,
                          std::vector<RVA>::const_iterator rva_end)
      : rva_it_(rva_begin), rva_end_(rva_end) {}

  ~TestRvaVisitor() override {}

  size_t Remaining() const override { return std::distance(rva_it_, rva_end_); }

  RVA Get() const override { return *rva_it_; }

  void Next() override { ++rva_it_; }

 private:
  std::vector<RVA>::const_iterator rva_it_;
  std::vector<RVA>::const_iterator rva_end_;
};

void CheckLabelManagerContent(LabelManager* label_manager,
                              const std::map<RVA, int32_t>& expected) {
  EXPECT_EQ(expected.size(), label_manager->Size());
  for (const auto& rva_and_count : expected) {
    Label* label = label_manager->Find(rva_and_count.first);
    EXPECT_TRUE(label != nullptr);
    EXPECT_EQ(rva_and_count.first, label->rva_);
    EXPECT_EQ(rva_and_count.second, label->count_);
  }
}

// Instantiates a LabelVector with |n| instances. The |rva_| fields are assigned
// 0, ..., |n| - 1. The other fields are uninitialized.
LabelVector CreateLabelVectorBasic(size_t n) {
  LabelVector labels;
  labels.reserve(n);
  for (size_t i = 0; i < n; ++i)
    labels.push_back(Label(i));
  return labels;
}

// Instantiates a list of Labels, one per character |ch| in |encoded_index|.
// - |rva_| is assigned 0, 1, 2, ...
// - |count_| is assigned 1.
// - |index_| depends on |ch|: '.' => kNoIndex, 'A' => 0, ..., 'Z' => 25.
// Each letter (except '.') can appear at most once in |encoded_index|.
// For example, |encoded_index| = "A.E" initializes 3 Labels:
//   [{rva_: 0, count_: 1, index_: 0},
//    {rva_: 1, count_: 1, index_: kNoIndex},
//    {rva_: 2, count_: 1, index_: 4}].
LabelVector CreateLabelVectorWithIndexes(const std::string& encoded_index) {
  LabelVector labels;
  size_t n = encoded_index.size();
  labels.reserve(n);
  std::set<char> used_ch;
  for (size_t i = 0; i < n; ++i) {
    int index = Label::kNoIndex;
    char ch = encoded_index[i];
    if (ch != '.') {
      // Sanity check for test case.
      if (ch < 'A' || ch > 'Z' || used_ch.find(ch) != used_ch.end())
        NOTREACHED() << "Malformed test case: " << encoded_index;
      used_ch.insert(ch);
      index = ch - 'A';
    }
    labels.push_back(Label(i, index, 1));
  }
  return labels;
}

// Returns a string encoding for |index_| assignments for |label_| instances,
// with kNoIndex => '.', 0 => 'A', ..., '25' => 'Z'. Fails if any |index_|
// does not fit the above.
std::string EncodeLabelIndexes(const LabelVector& labels) {
  std::string encoded;
  encoded.reserve(labels.size());
  for (const Label& label : labels) {
    if (label.index_ == Label::kNoIndex)
      encoded += '.';
    else if (label.index_ >= 0 && label.index_ <= 'Z' - 'A')
      encoded += static_cast<char>(label.index_ + 'A');
    else
      NOTREACHED();
  }
  return encoded;
}

}  // namespace

TEST(LabelManagerTest, GetIndexBound_LabelVector) {
  LabelVector labels0;
  EXPECT_EQ(0, LabelManager::GetIndexBound(labels0));

  LabelVector labels1_uninit = CreateLabelVectorBasic(1);
  ASSERT_EQ(1U, labels1_uninit.size());
  EXPECT_EQ(0, LabelManager::GetIndexBound(labels1_uninit));

  LabelVector labels1_init = CreateLabelVectorBasic(1);
  ASSERT_EQ(1U, labels1_init.size());
  labels1_init[0].index_ = 99;
  EXPECT_EQ(100, LabelManager::GetIndexBound(labels1_init));

  LabelVector labels6_mixed = CreateLabelVectorBasic(6);
  ASSERT_EQ(6U, labels6_mixed.size());
  labels6_mixed[1].index_ = 5;
  labels6_mixed[2].index_ = 2;
  labels6_mixed[4].index_ = 15;
  labels6_mixed[5].index_ = 7;
  EXPECT_EQ(16, LabelManager::GetIndexBound(labels6_mixed));
}

TEST(LabelManagerTest, GetIndexBound_RVAToLabel) {
  RVAToLabel labels_map0;
  EXPECT_EQ(0, LabelManager::GetIndexBound(labels_map0));

  RVAToLabel labels1_map_init;
  Label label1(static_cast<RVA>(0), 99, 1);
  labels1_map_init[label1.rva_] = &label1;
  EXPECT_EQ(100, LabelManager::GetIndexBound(labels1_map_init));

  RVAToLabel labels_map6_mixed;
  Label labels6[] = {
    Label(static_cast<RVA>(1), 5, 1),
    Label(static_cast<RVA>(2), 2, 1),
    Label(static_cast<RVA>(4), 15, 1),
    Label(static_cast<RVA>(5), 7, 1)
  };
  for (Label& label : labels6)
    labels_map6_mixed[label.rva_] = &label;
  EXPECT_EQ(16, LabelManager::GetIndexBound(labels_map6_mixed));
}

TEST(LabelManagerTest, Basic) {
  static const RVA kTestTargetsRaw[] = {
    0x04000010,
    0x04000030,
    0x04000020,
    0x04000010,  // Redundant.
    0xFEEDF00D,
    0x04000030,  // Redundant.
    0xFEEDF00D,  // Redundant.
    0x00000110,
    0x04000010,  // Redundant.
    0xABCD1234
  };
  std::vector<RVA> test_targets(std::begin(kTestTargetsRaw),
                                std::end(kTestTargetsRaw));
  TestRvaVisitor visitor(test_targets.begin(), test_targets.end());

  // Preallocate targets, then populate.
  LabelManagerImpl label_manager;
  label_manager.Read(&visitor);

  static const std::pair<RVA, int32_t> kExpected1Raw[] = {
      {0x00000110, 1}, {0x04000010, 3}, {0x04000020, 1},
      {0x04000030, 2}, {0xABCD1234, 1}, {0xFEEDF00D, 2}};
  std::map<RVA, int32_t> expected1(std::begin(kExpected1Raw),
                                   std::end(kExpected1Raw));

  CheckLabelManagerContent(&label_manager, expected1);

  // Expect to *not* find labels for various RVAs that were never added.
  EXPECT_EQ(nullptr, label_manager.Find(RVA(0x00000000)));
  EXPECT_EQ(nullptr, label_manager.Find(RVA(0x0400000F)));
  EXPECT_EQ(nullptr, label_manager.Find(RVA(0x04000011)));
  EXPECT_EQ(nullptr, label_manager.Find(RVA(0x5F3759DF)));
  EXPECT_EQ(nullptr, label_manager.Find(RVA(0xFEEDFFF0)));
  EXPECT_EQ(nullptr, label_manager.Find(RVA(0xFFFFFFFF)));

  // Remove Labels with |count_| < 2.
  label_manager.RemoveUnderusedLabels(2);
  static const std::pair<RVA, int32_t> kExpected2Raw[] = {
      {0x04000010, 3}, {0x04000030, 2}, {0xFEEDF00D, 2}};
  std::map<RVA, int32_t> expected2(std::begin(kExpected2Raw),
                                   std::end(kExpected2Raw));
  CheckLabelManagerContent(&label_manager, expected2);
}

TEST(LabelManagerTest, Single) {
  const RVA kRva = 12U;
  for (int dup = 1; dup < 8; ++dup) {
    // Test data: |dup| copies of kRva.
    std::vector<RVA> test_targets(dup, kRva);
    TestRvaVisitor visitor(test_targets.begin(), test_targets.end());
    LabelManagerImpl label_manager;
    label_manager.Read(&visitor);
    EXPECT_EQ(1U, label_manager.Size());  // Deduped to 1 Label.

    Label* label = label_manager.Find(kRva);
    EXPECT_NE(nullptr, label);
    EXPECT_EQ(kRva, label->rva_);
    EXPECT_EQ(dup, label->count_);

    for (RVA rva = 0U; rva < 16U; ++rva) {
      if (rva != kRva)
        EXPECT_EQ(nullptr, label_manager.Find(rva));
    }
  }
}

TEST(LabelManagerTest, Empty) {
  std::vector<RVA> empty_test_targets;
  TestRvaVisitor visitor(empty_test_targets.begin(), empty_test_targets.end());
  LabelManagerImpl label_manager;
  label_manager.Read(&visitor);
  EXPECT_EQ(0U, label_manager.Size());
  for (RVA rva = 0U; rva < 16U; ++rva)
    EXPECT_EQ(nullptr, label_manager.Find(rva));
}

TEST(LabelManagerTest, EmptyAssign) {
  LabelManagerImpl label_manager_empty;
  label_manager_empty.DefaultAssignIndexes();
  label_manager_empty.UnassignIndexes();
  label_manager_empty.AssignRemainingIndexes();
}

TEST(LabelManagerTest, TrivialAssign) {
  for (size_t size = 0; size < 20; ++size) {
    LabelManagerImpl label_manager;
    label_manager.SetLabels(CreateLabelVectorBasic(size));

    // Sanity check.
    for (size_t i = 0; i < size; ++i)
      EXPECT_EQ(Label::kNoIndex, label_manager.Labels()[i].index_);

    // Default assign.
    label_manager.DefaultAssignIndexes();
    for (size_t i = 0; i < size; ++i)
      EXPECT_EQ(static_cast<int>(i), label_manager.Labels()[i].index_);

    // Heuristic assign, but since everything's assigned, so no change.
    label_manager.AssignRemainingIndexes();
    for (size_t i = 0; i < size; ++i)
      EXPECT_EQ(static_cast<int>(i), label_manager.Labels()[i].index_);

    // Unassign.
    label_manager.UnassignIndexes();
    for (size_t i = 0; i < size; ++i)
      EXPECT_EQ(Label::kNoIndex, label_manager.Labels()[i].index_);
  }
}

// Tests SimpleIndexAssigner fill strategies independently.
TEST(LabelManagerTest, SimpleIndexAssigner) {
  using SimpleIndexAssigner = LabelManagerImpl::SimpleIndexAssigner;
  // See CreateLabelVectorWithIndexes() explanation on how we encode LabelVector
  // |index_| values as a string.
  const struct TestCase {
    const char* input;
    const char* expect_forward;
    const char* expect_backward;
    const char* expect_in;
  } kTestCases[] = {
    {"", "", "", ""},
    {".", "A", "A", "A"},
    {"....", "ABCD", "ABCD", "ABCD"},
    {"A...", "ABCD", "ABCD", "ABCD"},
    {".A..", ".ABC", ".ACD", "BACD"},
    {"...A", "...A", "...A", "BCDA"},
    {"C...", "CD.A", "C..D", "CABD"},
    {".C..", "ACD.", "BC.D", "ACBD"},
    {"...C", "AB.C", ".ABC", "ABDC"},
    {"D...", "D.AB", "D...", "DABC"},
    {".D..", "AD..", "CD..", "ADBC"},
    {"...D", "ABCD", "ABCD", "ABCD"},
    {"Z...", "Z.AB", "Z...", "ZABC"},
    {".Z..", "AZ..", "YZ..", "AZBC"},
    {"...Z", "ABCZ", "WXYZ", "ABCZ"},
    {"..AZ..", "..AZ..", "..AZ..", "BCAZDE"},
    {"..ZA..", "..ZABC", "XYZA..", "BCZADE"},
    {"A....Z", "ABCDEZ", "AVWXYZ", "ABCDEZ"},
    {"Z....A", "Z....A", "Z....A", "ZBCDEA"},
    {"..CD..", "ABCDEF", "ABCDEF", "ABCDEF"},
    {"..DC..", "ABDC..", "..DCEF", "ABDCEF"},
    {"..MN..", "ABMN..", "KLMN..", "ABMNCD"},
    {"..NM..", "ABNM..", "..NM..", "ABNMCD"},
    {".B.D.F.", "ABCDEFG", "ABCDEFG", "ABCDEFG"},
    {".D.G.J.", "ADEGHJ.", "CDFGIJ.", "ADBGCJE"},
    {".D.Z.J.", "ADEZ.JK", "CDYZIJ.", "ADBZCJE"},
    {".B..E..", "ABCDEFG", "ABCDEFG", "ABCDEFG"},
    {".B..D..", "ABC.DEF", "AB.CDFG", "ABCEDFG"},
  };
  const int kNumFuns = 3;
  // TestCase member variable pointers to enable iteration.
  const char* TestCase::*expect_ptr[kNumFuns] = {
    &TestCase::expect_forward,
    &TestCase::expect_backward,
    &TestCase::expect_in
  };
  // SimpleIndexAssigner member function pointers to enable iteration.
  void (SimpleIndexAssigner::*fun_ptrs[kNumFuns])() = {
    &SimpleIndexAssigner::DoForwardFill,
    &SimpleIndexAssigner::DoBackwardFill,
    &SimpleIndexAssigner::DoInFill
  };
  for (const auto& test_case : kTestCases) {
    // Loop over {forward fill, backward fill, infill}.
    for (int i = 0; i < kNumFuns; ++i) {
      std::string expect = test_case.*(expect_ptr[i]);
      LabelVector labels = CreateLabelVectorWithIndexes(test_case.input);
      SimpleIndexAssigner assigner(&labels);
      (assigner.*(fun_ptrs[i]))();
      std::string result = EncodeLabelIndexes(labels);
      EXPECT_EQ(expect, result);
    }
  }
}

// Tests integrated AssignRemainingIndexes().
TEST(LabelManagerTest, AssignRemainingIndexes) {
  const struct {
    const char* input;
    const char* expect;
  } kTestCases[] = {
    // Trivial.
    {"", ""},
    {"M", "M"},
    {"ABCDEFG", "ABCDEFG"},
    {"THEQUICKBROWNFXJMPSVLAZYDG", "THEQUICKBROWNFXJMPSVLAZYDG"},
    // Forward fill only.
    {".", "A"},
    {".......", "ABCDEFG"},
    {"....E..", "ABCDEFG"},  // "E" is at right place.
    {".D.B.H.F.", "ADEBCHIFG"},
    {"ZN....", "ZNOPQR"},  // "Z" exists, so 'OPQR" are defined.
    {"H.D...A..", "HIDEFGABC"},
    {"...K.DE..H..Z", "ABCKLDEFGHIJZ"},  // "Z" exists, so "L" defined.
    // Infill only.
    {"E.", "EA"},
    {"...A", "BCDA"},
    {"Z...A", "ZBCDA"},
    {"AN...", "ANBCD"},
    {"...AZ", "BCDAZ"},
    {"....AC", "BDEFAC"},
    {"ED...C...B....A", "EDFGHCIJKBLMNOA"},
    // Forward fill and infill.
    {"E..", "EBA"},  // Forward: "A"; in: "B".
    {"Z....", "ZDABC"},  // Forward: "ABC"; in: "D".
    {".E.....", "AEFGBCD"},  // Forward: "A", "FG"; in: "BCD".
    {"....C..", "ABFGCDE"},  // Forward: "AB", "DE"; in: "FG".
    {"...Z...", "ABCZDEF"},  // Forward: "ABC"; in: "DEF".
    {"...A...", "EFGABCD"},  // Forward: "BCD"; in: "EFG".
    // Backward fill only.
    {".CA", "BCA"},
    {"...ZA", "WXYZA"},
    {"BA...Z", "BAWXYZ"},
    {"ANM..Z....L...T", "ANMXYZHIJKLQRST"},
    {"....G..Z...LAH", "CDEFGXYZIJKLAH"},
    // Forward fill and backward fill.
    {"..ZA..", "XYZABC"},  // Forward: "BC"; backward: "XY".
    {".....ZD", "ABCXYZD"},  // Forward: "ABC"; backward: "XY".
    {"DA.....", "DABCEFG"},  // Forward: "BC"; backward: "EFG".
    // Backward fill and infill.
    {"G....DA", "GEFBCDA"},  // Backward: "BC"; in: "EF".
    {"..ZBA..", "XYZBACD"},  // Backward: "XY"; in: "CD".
    // All.
    {".....ZED.", "ABCXYZEDF"},  // Forward: "ABC"; backward: "XY"; in: "F".
    {".....GD.", "ABCHFGDE"},  // Forward: "ABC", "E"; backward: "F"; in: "H".
    {"..FE..GD..", "ABFECHGDIJ"}, // Forward: "AB"; backward: "IJ"; in: "CH".
  };
  for (const auto& test_case : kTestCases) {
    LabelManagerImpl label_manager;
    label_manager.SetLabels(CreateLabelVectorWithIndexes(test_case.input));

    label_manager.AssignRemainingIndexes();
    std::string result = EncodeLabelIndexes(label_manager.Labels());
    EXPECT_EQ(test_case.expect, result);
  }
}

}  // namespace courgette