| // 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 |