[Courgette] Make LabelManager an interface; move code to LabelManagerImpl.

LabelManager aims to reduce Courgette peak memory, and we still need to
use it in production. To reduce transition risk and pain, the plan is:
1. Make LabelManager an interface, move the implementation to
   LabelMangerImpl.
2. More cleanup of Label-related code in production.
3. Add LabelManagerLegacy implementation of LabelManager and move active
  Label-related code there. Update callers to call the LabelManager
  interfaces. No change in behavior.
4. After extensive testing, switch to using LabelManagerImpl with
   relatively little code change.
5. Remove LabelManagerLegacy.

This CL implements step #1.

Review URL: https://codereview.chromium.org/1567133002

Cr-Commit-Position: refs/heads/master@{#368378}

3 files changed, 108 insertions, 70 deletions

diff --git a/courgette/label_manager.cc b/courgette/label_manager.cc
index 06f3558..268bda2 100644
--- a/courgette/label_manager.cc
+++ b/courgette/label_manager.cc
@@ -16,9 +16,13 @@
 
 namespace courgette {
 
-LabelManager::RvaVisitor::~RvaVisitor() {}
+LabelManager::LabelManager() {}
+
+LabelManager::~LabelManager() {}
 
-LabelManager::SimpleIndexAssigner::SimpleIndexAssigner(LabelVector* labels)
+LabelManagerImpl::RvaVisitor::~RvaVisitor() {}
+
+LabelManagerImpl::SimpleIndexAssigner::SimpleIndexAssigner(LabelVector* labels)
     : labels_(labels) {
   // Find the maximum assigned index. Not bounded by |labels_| size.
   int max_index = -1;
@@ -42,9 +46,9 @@ LabelManager::SimpleIndexAssigner::SimpleIndexAssigner(LabelVector* labels)
   VLOG(1) << used << " of " << labels_->size() << " labels pre-assigned.";
 }
 
-LabelManager::SimpleIndexAssigner::~SimpleIndexAssigner() {}
+LabelManagerImpl::SimpleIndexAssigner::~SimpleIndexAssigner() {}
 
-void LabelManager::SimpleIndexAssigner::DoForwardFill() {
+void LabelManagerImpl::SimpleIndexAssigner::DoForwardFill() {
   size_t count = 0;
   // Inside the loop, if |prev_index| == |kNoIndex| then we try to assign 0.
   // This allows 0 (if unused) to be assigned in middle of |labels_|.
@@ -63,7 +67,7 @@ void LabelManager::SimpleIndexAssigner::DoForwardFill() {
   VLOG(1) << "  fill forward " << count;
 }
 
-void LabelManager::SimpleIndexAssigner::DoBackwardFill() {
+void LabelManagerImpl::SimpleIndexAssigner::DoBackwardFill() {
   size_t count = 0;
   // This is asymmetric from DoForwardFill(), to preserve old behavior.
   // Inside the loop, if |prev_index| == |kNoIndex| then we skip assignment.
@@ -85,7 +89,7 @@ void LabelManager::SimpleIndexAssigner::DoBackwardFill() {
   VLOG(1) << "  fill backward " << count;
 }
 
-void LabelManager::SimpleIndexAssigner::DoInFill() {
+void LabelManagerImpl::SimpleIndexAssigner::DoInFill() {
   size_t count = 0;
   int index = 0;
   for (Label& label : *labels_) {
@@ -101,9 +105,9 @@ void LabelManager::SimpleIndexAssigner::DoInFill() {
   VLOG(1) << "  infill " << count;
 }
 
-LabelManager::LabelManager() {}
+LabelManagerImpl::LabelManagerImpl() {}
 
-LabelManager::~LabelManager() {}
+LabelManagerImpl::~LabelManagerImpl() {}
 
 // We wish to minimize peak memory usage here. Analysis: Let
 //   m = number of (RVA) elements in |rva_visitor|,
@@ -115,7 +119,7 @@ LabelManager::~LabelManager() {}
 // For our typical usage (i.e. Chrome) we see m = ~4n, so we use 16 * n bytes of
 // extra contiguous memory during computation. Assuming memory fragmentation
 // would not be an issue, this is much better than using std::map.
-void LabelManager::Read(RvaVisitor* rva_visitor) {
+void LabelManagerImpl::Read(RvaVisitor* rva_visitor) {
   // Write all values in |rva_visitor| to |rvas|.
   size_t num_rva = rva_visitor->Remaining();
   std::vector<RVA> rvas(num_rva);
@@ -139,7 +143,19 @@ void LabelManager::Read(RvaVisitor* rva_visitor) {
   }
 }
 
-void LabelManager::RemoveUnderusedLabels(int32_t count_threshold) {
+size_t LabelManagerImpl::Size() const {
+  return labels_.size();
+}
+
+// Uses binary search to find |rva|.
+Label* LabelManagerImpl::Find(RVA rva) {
+  auto it = std::lower_bound(
+      labels_.begin(), labels_.end(), Label(rva),
+      [](const Label& l1, const Label& l2) { return l1.rva_ < l2.rva_; });
+  return it == labels_.end() || it->rva_ != rva ? nullptr : &(*it);
+}
+
+void LabelManagerImpl::RemoveUnderusedLabels(int32_t count_threshold) {
   if (count_threshold <= 0)
     return;
   labels_.erase(std::remove_if(labels_.begin(), labels_.end(),
@@ -150,20 +166,12 @@ void LabelManager::RemoveUnderusedLabels(int32_t count_threshold) {
   // Not shrinking |labels_|, since this may cause reallocation.
 }
 
-// Uses binary search to find |rva|.
-Label* LabelManager::Find(RVA rva) {
-  auto it = std::lower_bound(
-      labels_.begin(), labels_.end(), Label(rva),
-      [](const Label& l1, const Label& l2) { return l1.rva_ < l2.rva_; });
-  return it == labels_.end() || it->rva_ != rva ? nullptr : &(*it);
-}
-
-void LabelManager::UnassignIndexes() {
+void LabelManagerImpl::UnassignIndexes() {
   for (Label& label : labels_)
     label.index_ = Label::kNoIndex;
 }
 
-void LabelManager::DefaultAssignIndexes() {
+void LabelManagerImpl::DefaultAssignIndexes() {
   int cur_index = 0;
   for (Label& label : labels_) {
     CHECK_EQ(Label::kNoIndex, label.index_);
@@ -171,7 +179,7 @@ void LabelManager::DefaultAssignIndexes() {
   }
 }
 
-void LabelManager::AssignRemainingIndexes() {
+void LabelManagerImpl::AssignRemainingIndexes() {
   // This adds some memory overhead, about 1 bit per Label (more if indexes >=
   // |labels_.size()| get used).
   SimpleIndexAssigner assigner(&labels_);
@@ -180,4 +188,8 @@ void LabelManager::AssignRemainingIndexes() {
   assigner.DoInFill();
 }
 
+void LabelManagerImpl::SetLabels(const LabelVector& labels) {
+  labels_ = labels;
+}
+
 }  // namespace courgette
diff --git a/courgette/label_manager.h b/courgette/label_manager.h
index 1b88024..3034ebf 100644
--- a/courgette/label_manager.h
+++ b/courgette/label_manager.h
@@ -10,6 +10,7 @@
 
 #include <vector>
 
+#include "base/gtest_prod_util.h"
 #include "base/macros.h"
 #include "courgette/image_utils.h"
 
@@ -17,11 +18,43 @@ namespace courgette {
 
 using LabelVector = std::vector<Label>;
 
-// A container to store and manage Label instances. A key consideration is peak
-// memory usage reduction. To this end we preallocate Label instances in bulk,
-// and carefully control transient memory usage when initializing Labels.
+// A container to store and manage Label instances.
 class LabelManager {
  public:
+  virtual ~LabelManager();
+
+  // Returns the number of Label instances stored.
+  virtual size_t Size() const = 0;
+
+  // Efficiently searches for a Label that targets |rva|. Returns the pointer to
+  // the stored Label instance if found, or null otherwise. Non-const to support
+  // implementations that allocate-on-read.
+  virtual Label* Find(RVA rva) = 0;
+
+  // Removes Label instances whose |count_| is less than |count_threshold|.
+  virtual void RemoveUnderusedLabels(int32_t count_threshold) = 0;
+
+  // Resets all indexes to an unassigned state.
+  virtual void UnassignIndexes() = 0;
+
+  // Assigns indexes to successive integers from 0, ordered by RVA.
+  virtual void DefaultAssignIndexes() = 0;
+
+  // Assigns indexes to any Label instances that don't have one yet.
+  virtual void AssignRemainingIndexes() = 0;
+
+ protected:
+  LabelManager();
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(LabelManager);
+};
+
+// An implementation of LabelManager dedicated to reducing peak memory usage.
+// To this end we preallocate Label instances in bulk, and carefully control
+// transient memory usage when initializing Labels.
+class LabelManagerImpl : public LabelManager {
+ public:
   // An adaptor to sequentially traverse multiple RVAs. This is useful for RVA
   // translation without extra storage. For example, we might have a stored list
   // of RVA locations, but we want to traverse the matching RVA targets.
@@ -91,36 +124,37 @@ class LabelManager {
     DISALLOW_COPY_AND_ASSIGN(SimpleIndexAssigner);
   };
 
-  LabelManager();
-  virtual ~LabelManager();
+  LabelManagerImpl();
+  ~LabelManagerImpl() override;
 
-  // Initializes |labels_| using RVAs from |rva_visitor|. Each distinct RVA from
+  // LabelManager interfaces.
+  size_t Size() const override;
+  Label* Find(RVA rva) override;
+  void RemoveUnderusedLabels(int32_t count_threshold) override;
+  void UnassignIndexes() override;
+  void DefaultAssignIndexes() override;
+  void AssignRemainingIndexes() override;
+
+  // Populates |labels_| using RVAs from |rva_visitor|. Each distinct RVA from
   // |rva_visitor| yields a Label with |rva_| assigned as the RVA, and |count_|
   // assigned as the repeat.
   void Read(RvaVisitor* rva_visitor);
 
-  // Removes |labels_| elements whose |count_| is less than |count_threshold|.
-  void RemoveUnderusedLabels(int32_t count_threshold);
-
-  // Efficiently searches for a Label that targets |rva|. Returns the pointer to
-  // the stored Label instance if found, or null otherwise.
-  Label* Find(RVA rva);
-
-  // Resets all indexes to an unassigend state.
-  void UnassignIndexes();
-
-  // Assigns indexes to successive integers from 0, ordered by RVA.
-  void DefaultAssignIndexes();
-
-  // Assigns indexes to any Label elements that don't have one yet.
-  void AssignRemainingIndexes();
-
  protected:
   // The main list of Label instances, sorted by the |rva_| member.
   LabelVector labels_;
 
  private:
-  DISALLOW_COPY_AND_ASSIGN(LabelManager);
+  FRIEND_TEST_ALL_PREFIXES(LabelManagerTest, TrivialAssign);
+  FRIEND_TEST_ALL_PREFIXES(LabelManagerTest, AssignRemainingIndexes);
+
+  // Accessor to stored Label instances. For testing only.
+  const LabelVector& Labels() const { return labels_; }
+
+  // Directly assign |labels_|. For testing only.
+  void SetLabels(const LabelVector& labels);
+
+  DISALLOW_COPY_AND_ASSIGN(LabelManagerImpl);
 };
 
 }  // namespace courgette
diff --git a/courgette/label_manager_unittest.cc b/courgette/label_manager_unittest.cc
index cc112a8..b66f563 100644
--- a/courgette/label_manager_unittest.cc
+++ b/courgette/label_manager_unittest.cc
@@ -23,7 +23,7 @@ namespace courgette {
 namespace {
 
 // Test version of RvaVisitor: Just wrap std::vector<RVA>.
-class TestRvaVisitor : public LabelManager::RvaVisitor {
+class TestRvaVisitor : public LabelManagerImpl::RvaVisitor {
  public:
   explicit TestRvaVisitor(std::vector<RVA>::const_iterator rva_begin,
                           std::vector<RVA>::const_iterator rva_end)
@@ -42,20 +42,9 @@ class TestRvaVisitor : public LabelManager::RvaVisitor {
   std::vector<RVA>::const_iterator rva_end_;
 };
 
-// Test version of LabelManager: Expose data to test implementation.
-class TestLabelManager : public LabelManager {
- public:
-  TestLabelManager() {}
-
-  // Using move semantics to optimize injection of test LabelVector.
-  explicit TestLabelManager(LabelVector&& labels) { labels_ = labels; }
-
-  const LabelVector& Labels() const { return labels_; }
-};
-
-void CheckLabelManagerContent(TestLabelManager* label_manager,
+void CheckLabelManagerContent(LabelManager* label_manager,
                               const std::map<RVA, int32_t>& expected) {
-  EXPECT_EQ(expected.size(), label_manager->Labels().size());
+  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);
@@ -64,7 +53,7 @@ void CheckLabelManagerContent(TestLabelManager* label_manager,
   }
 }
 
-// Instantiates a LabelVector with |n| elements. The |rva_| fields are assigned
+// 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;
@@ -106,7 +95,7 @@ LabelVector CreateLabelVectorWithIndexes(const std::string& encoded_index) {
   return labels;
 }
 
-// Returns a string encoding for |index_| assignments for |label_| elements,
+// 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) {
@@ -143,7 +132,7 @@ TEST(LabelManagerTest, Basic) {
   TestRvaVisitor visitor(test_targets.begin(), test_targets.end());
 
   // Preallocate targets, then populate.
-  TestLabelManager label_manager;
+  LabelManagerImpl label_manager;
   label_manager.Read(&visitor);
 
   static const std::pair<RVA, int32_t> kExpected1Raw[] = {
@@ -177,9 +166,9 @@ TEST(LabelManagerTest, Single) {
     // Test data: |dup| copies of kRva.
     std::vector<RVA> test_targets(dup, kRva);
     TestRvaVisitor visitor(test_targets.begin(), test_targets.end());
-    TestLabelManager label_manager;
+    LabelManagerImpl label_manager;
     label_manager.Read(&visitor);
-    EXPECT_EQ(1U, label_manager.Labels().size());  // Deduped to 1 Label.
+    EXPECT_EQ(1U, label_manager.Size());  // Deduped to 1 Label.
 
     Label* label = label_manager.Find(kRva);
     EXPECT_NE(nullptr, label);
@@ -196,15 +185,15 @@ TEST(LabelManagerTest, Single) {
 TEST(LabelManagerTest, Empty) {
   std::vector<RVA> empty_test_targets;
   TestRvaVisitor visitor(empty_test_targets.begin(), empty_test_targets.end());
-  TestLabelManager label_manager;
+  LabelManagerImpl label_manager;
   label_manager.Read(&visitor);
-  EXPECT_EQ(0U, label_manager.Labels().size());
+  EXPECT_EQ(0U, label_manager.Size());
   for (RVA rva = 0U; rva < 16U; ++rva)
     EXPECT_EQ(nullptr, label_manager.Find(rva));
 }
 
 TEST(LabelManagerTest, EmptyAssign) {
-  TestLabelManager label_manager_empty;
+  LabelManagerImpl label_manager_empty;
   label_manager_empty.DefaultAssignIndexes();
   label_manager_empty.UnassignIndexes();
   label_manager_empty.AssignRemainingIndexes();
@@ -212,7 +201,9 @@ TEST(LabelManagerTest, EmptyAssign) {
 
 TEST(LabelManagerTest, TrivialAssign) {
   for (size_t size = 0; size < 20; ++size) {
-    TestLabelManager label_manager(CreateLabelVectorBasic(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_);
@@ -236,7 +227,7 @@ TEST(LabelManagerTest, TrivialAssign) {
 
 // Tests SimpleIndexAssigner fill strategies independently.
 TEST(LabelManagerTest, SimpleIndexAssigner) {
-  using SimpleIndexAssigner = LabelManager::SimpleIndexAssigner;
+  using SimpleIndexAssigner = LabelManagerImpl::SimpleIndexAssigner;
   // See CreateLabelVectorWithIndexes() explanation on how we encode LabelVector
   // |index_| values as a string.
   const struct TestCase {
@@ -353,8 +344,9 @@ TEST(LabelManagerTest, AssignRemainingIndexes) {
     {"..FE..GD..", "ABFECHGDIJ"}, // Forward: "AB"; backward: "IJ"; in: "CH".
   };
   for (const auto& test_case : kTestCases) {
-    TestLabelManager label_manager(
-        CreateLabelVectorWithIndexes(test_case.input));
+    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);