[Zucchini]: Remove IndirectReference.

IndirectReference brings complexity conceptually.
The purpose of IndirectReference was to speed-up look-ups.
Turns out that there is no significant impact on patching time
when using direct references.
Furthermore, this reduces coupling between TargetPool and ReferenceSet.

Change-Id: Ic50dbf59e483a7fa1480c8eb37f4b1d01a53401a
Reviewed-on: https://chromium-review.googlesource.com/1136578
Commit-Queue: Etienne Pierre-Doray <etiennep@chromium.org>
Reviewed-by: Samuel Huang <huangs@chromium.org>
Cr-Commit-Position: refs/heads/master@{#582653}
NOKEYCHECK=True
GitOrigin-RevId: 0434f5b4a564c6295e62a3996826f8627b8aa617

8 files changed, 43 insertions, 63 deletions

diff --git a/encoded_view.cc b/encoded_view.cc
index 5b55b51..90eeba9 100644
--- a/encoded_view.cc
+++ b/encoded_view.cc
@@ -29,7 +29,7 @@ EncodedView::value_type EncodedView::Projection(offset_t location) const {
 
   // |location| points into a Reference.
   const ReferenceSet& ref_set = image_index_.refs(type);
-  IndirectReference ref = ref_set.at(location);
+  Reference ref = ref_set.at(location);
   DCHECK_GE(location, ref.location);
   DCHECK_LT(location, ref.location + ref_set.width());
 
@@ -40,11 +40,12 @@ EncodedView::value_type EncodedView::Projection(offset_t location) const {
   }
 
   PoolTag pool_tag = ref_set.pool_tag();
+  const auto& target_pool = ref_set.target_pool();
 
   // Targets with an associated Label will use its Label index in projection.
-  DCHECK_EQ(image_index_.pool(pool_tag).size(),
-            pool_infos_[pool_tag.value()].labels.size());
-  uint32_t label = pool_infos_[pool_tag.value()].labels[ref.target_key];
+  DCHECK_EQ(target_pool.size(), pool_infos_[pool_tag.value()].labels.size());
+  uint32_t label = pool_infos_[pool_tag.value()]
+                       .labels[target_pool.KeyForOffset(ref.target)];
 
   // Projection is done on (|target|, |type|), shifted by
   // kBaseReferenceProjection to avoid collisions with raw content.
diff --git a/equivalence_map.cc b/equivalence_map.cc
index 77551ec..b85fe9f 100644
--- a/equivalence_map.cc
+++ b/equivalence_map.cc
@@ -59,12 +59,13 @@ double GetTokenSimilarity(
 
   const ReferenceSet& old_ref_set = old_image_index.refs(old_type);
   const ReferenceSet& new_ref_set = new_image_index.refs(new_type);
-  IndirectReference old_reference = old_ref_set.at(src);
-  IndirectReference new_reference = new_ref_set.at(dst);
+  Reference old_reference = old_ref_set.at(src);
+  Reference new_reference = new_ref_set.at(dst);
   PoolTag pool_tag = old_ref_set.pool_tag();
 
   double affinity = targets_affinities[pool_tag.value()].AffinityBetween(
-      old_reference.target_key, new_reference.target_key);
+      old_ref_set.target_pool().KeyForOffset(old_reference.target),
+      new_ref_set.target_pool().KeyForOffset(new_reference.target));
 
   // Both targets are not associated, which implies a weak match.
   if (affinity == 0.0)
diff --git a/image_index.cc b/image_index.cc
index 6c7a28b..1efe5d8 100644
--- a/image_index.cc
+++ b/image_index.cc
@@ -47,7 +47,7 @@ bool ImageIndex::IsToken(offset_t location) const {
     return true;
 
   // |location| points into a Reference.
-  IndirectReference reference = refs(type).at(location);
+  Reference reference = refs(type).at(location);
   // Only the first byte of a reference is a token.
   return location == reference.location;
 }
diff --git a/image_utils.h b/image_utils.h
index 9aba0a6..b34b9dc 100644
--- a/image_utils.h
+++ b/image_utils.h
@@ -85,15 +85,6 @@ inline bool operator==(const Reference& a, const Reference& b) {
   return a.location == b.location && a.target == b.target;
 }
 
-struct IndirectReference {
-  offset_t location;
-  key_t target_key;  // Key within a pool of references with same semantics.
-};
-
-inline bool operator==(const IndirectReference& a, const IndirectReference& b) {
-  return a.location == b.location && a.target_key == b.target_key;
-}
-
 // Interface for extracting References through member function GetNext().
 // This is used by Disassemblers to extract references from an image file.
 // Typically, a Reader lazily extracts values and does not hold any storage.
diff --git a/reference_set.cc b/reference_set.cc
index 963e814..0179a51 100644
--- a/reference_set.cc
+++ b/reference_set.cc
@@ -16,12 +16,11 @@ namespace zucchini {
 namespace {
 
 // Returns true if |refs| is sorted by location.
-bool IsReferenceListSorted(const std::vector<IndirectReference>& refs) {
-  return std::is_sorted(
-      refs.begin(), refs.end(),
-      [](const IndirectReference& a, const IndirectReference& b) {
-        return a.location < b.location;
-      });
+bool IsReferenceListSorted(const std::vector<Reference>& refs) {
+  return std::is_sorted(refs.begin(), refs.end(),
+                        [](const Reference& a, const Reference& b) {
+                          return a.location < b.location;
+                        });
 }
 
 }  // namespace
@@ -36,28 +35,22 @@ void ReferenceSet::InitReferences(ReferenceReader&& ref_reader) {
   DCHECK(references_.empty());
   for (auto ref = ref_reader.GetNext(); ref.has_value();
        ref = ref_reader.GetNext()) {
-    references_.push_back(
-        {ref->location, target_pool_.KeyForOffset(ref->target)});
+    references_.push_back(*ref);
   }
   DCHECK(IsReferenceListSorted(references_));
 }
 
 void ReferenceSet::InitReferences(const std::vector<Reference>& refs) {
   DCHECK(references_.empty());
-  references_.reserve(refs.size());
-  std::transform(refs.begin(), refs.end(), std::back_inserter(references_),
-                 [&](const Reference& ref) -> IndirectReference {
-                   return {ref.location, target_pool_.KeyForOffset(ref.target)};
-                 });
   DCHECK(IsReferenceListSorted(references_));
+  references_.assign(refs.begin(), refs.end());
 }
 
-IndirectReference ReferenceSet::at(offset_t offset) const {
-  auto pos =
-      std::upper_bound(references_.begin(), references_.end(), offset,
-                       [](offset_t offset, const IndirectReference& ref) {
-                         return offset < ref.location;
-                       });
+Reference ReferenceSet::at(offset_t offset) const {
+  auto pos = std::upper_bound(references_.begin(), references_.end(), offset,
+                              [](offset_t offset, const Reference& ref) {
+                                return offset < ref.location;
+                              });
 
   DCHECK(pos != references_.begin());  // Iterators.
   --pos;
diff --git a/reference_set.h b/reference_set.h
index 2ca7202..07940f0 100644
--- a/reference_set.h
+++ b/reference_set.h
@@ -15,11 +15,11 @@ namespace zucchini {
 
 class TargetPool;
 
-// Container of distinct indirect references of one type, along with traits,
-// only used during patch generation.
+// Container of distinct references of one type, along with traits, only used
+// during patch generation.
 class ReferenceSet {
  public:
-  using const_iterator = std::vector<IndirectReference>::const_iterator;
+  using const_iterator = std::vector<Reference>::const_iterator;
 
   // |traits| specifies the reference represented. |target_pool| specifies
   // common targets shared by all reference represented, and mediates target
@@ -36,19 +36,17 @@ class ReferenceSet {
   void InitReferences(ReferenceReader&& ref_reader);
   void InitReferences(const std::vector<Reference>& refs);
 
-  const std::vector<IndirectReference>& references() const {
-    return references_;
-  }
+  const std::vector<Reference>& references() const { return references_; }
   const ReferenceTypeTraits& traits() const { return traits_; }
   const TargetPool& target_pool() const { return target_pool_; }
   TypeTag type_tag() const { return traits_.type_tag; }
   PoolTag pool_tag() const { return traits_.pool_tag; }
   offset_t width() const { return traits_.width; }
 
-  // Looks up the IndirectReference by an |offset| that it spans. |offset| is
-  // assumed to be valid, i.e., |offset| must be spanned by some
-  // IndirectReference in |references_|.
-  IndirectReference at(offset_t offset) const;
+  // Looks up the Reference by an |offset| that it spans. |offset| is assumed to
+  // be valid, i.e., |offset| must be spanned by some Reference in
+  // |references_|.
+  Reference at(offset_t offset) const;
 
   size_t size() const { return references_.size(); }
   const_iterator begin() const { return references_.begin(); }
@@ -57,8 +55,8 @@ class ReferenceSet {
  private:
   ReferenceTypeTraits traits_;
   const TargetPool& target_pool_;
-  // List of distinct IndirectReference instances sorted by location.
-  std::vector<IndirectReference> references_;
+  // List of distinct Reference instances sorted by location.
+  std::vector<Reference> references_;
 };
 
 }  // namespace zucchini
diff --git a/reference_set_unittest.cc b/reference_set_unittest.cc
index b4ccceb..0bf869e 100644
--- a/reference_set_unittest.cc
+++ b/reference_set_unittest.cc
@@ -28,24 +28,22 @@ class ReferenceSetTest : public testing::Test {
 };
 
 TEST_F(ReferenceSetTest, InitReferencesFromReader) {
-  EXPECT_EQ(std::vector<IndirectReference>(), reference_set_.references());
+  EXPECT_EQ(std::vector<Reference>(), reference_set_.references());
   EXPECT_EQ(0U, reference_set_.size());
   std::vector<Reference> references = {{10, 0}, {12, 2}, {14, 5}};
   reference_set_.InitReferences(TestReferenceReader(references));
-  EXPECT_EQ(std::vector<IndirectReference>({{10, 0}, {12, 1}, {14, 3}}),
-            reference_set_.references());
-  EXPECT_EQ(3U, reference_set_.size());
+  EXPECT_EQ(references, reference_set_.references());
 }
 
 TEST_F(ReferenceSetTest, At) {
   reference_set_.InitReferences({{10, 0}, {12, 2}, {15, 5}});
   // Each references has kWidth = 2, so check all bytes covered.
-  EXPECT_EQ(IndirectReference({10, 0}), reference_set_.at(10));
-  EXPECT_EQ(IndirectReference({10, 0}), reference_set_.at(11));
-  EXPECT_EQ(IndirectReference({12, 1}), reference_set_.at(12));
-  EXPECT_EQ(IndirectReference({12, 1}), reference_set_.at(13));
-  EXPECT_EQ(IndirectReference({15, 3}), reference_set_.at(15));
-  EXPECT_EQ(IndirectReference({15, 3}), reference_set_.at(16));
+  EXPECT_EQ(Reference({10, 0}), reference_set_.at(10));
+  EXPECT_EQ(Reference({10, 0}), reference_set_.at(11));
+  EXPECT_EQ(Reference({12, 2}), reference_set_.at(12));
+  EXPECT_EQ(Reference({12, 2}), reference_set_.at(13));
+  EXPECT_EQ(Reference({15, 5}), reference_set_.at(15));
+  EXPECT_EQ(Reference({15, 5}), reference_set_.at(16));
 }
 
 }  // namespace zucchini
diff --git a/zucchini_gen.cc b/zucchini_gen.cc
index 0bb4658..38bd8b1 100644
--- a/zucchini_gen.cc
+++ b/zucchini_gen.cc
@@ -202,21 +202,19 @@ bool GenerateReferencesDelta(const ReferenceSet& src_refs,
         equiv.src_offset + (dst_ref->location - equiv.dst_offset);
     auto src_ref = std::lower_bound(
         src_refs.begin(), src_refs.end(), src_loc,
-        [](const IndirectReference& a, offset_t b) { return a.location < b; });
+        [](const Reference& a, offset_t b) { return a.location < b; });
     for (; dst_ref != dst_refs.end() &&
            dst_ref->location + ref_width <= equiv.dst_end();
          ++dst_ref, ++src_ref) {
       // Local offset of |src_ref| should match that of |dst_ref|.
       DCHECK_EQ(src_ref->location - equiv.src_offset,
                 dst_ref->location - equiv.dst_offset);
-      offset_t old_offset =
-          src_refs.target_pool().OffsetForKey(src_ref->target_key);
+      offset_t old_offset = src_ref->target;
       offset_t new_estimated_offset =
           offset_mapper.ExtendedForwardProject(old_offset);
       offset_t new_estimated_key =
           projected_target_pool.KeyForNearestOffset(new_estimated_offset);
-      offset_t new_offset =
-          dst_refs.target_pool().OffsetForKey(dst_ref->target_key);
+      offset_t new_offset = dst_ref->target;
       offset_t new_key = projected_target_pool.KeyForOffset(new_offset);
 
       reference_delta_sink->PutNext(