[Zucchini] Move Zucchini from /chrome/installer/ to /components/.

(Use "git log --follow" to see older revisions of files).

/components/ is the most logical place to put Zucchini, which only
depends on /base and /testing/gtest. This move also enables Zucchini to
be used by the Component Updater. Details:
- Move all files; run the following to change deps and guards:
  sed 's/chrome\/installer/components/' *.cc *.h -i
  sed 's/CHROME_INSTALLER/COMPONENTS/' *.cc *.h -i
  - Sorting works out pretty well!
- Change all 'chrome/installer/zucchini' to 'components/zucchini'
  throughout other parts of the repo; sort if necessary.
- Fix 6 'git cl lint' errors.
- Change 1 Bind() usage to BindRepeated().
- Update OWNER.

Bug: 729154
Change-Id: I50c5a7d411ea85f707b5994ab319dfb2a1acccf7
Reviewed-on: https://chromium-review.googlesource.com/954923
Reviewed-by: Greg Thompson <grt@chromium.org>
Reviewed-by: Jochen Eisinger <jochen@chromium.org>
Reviewed-by: Samuel Huang <huangs@chromium.org>
Commit-Queue: Samuel Huang <huangs@chromium.org>
Cr-Commit-Position: refs/heads/master@{#542857}
NOKEYCHECK=True
GitOrigin-RevId: 577ef6c435e8d43be6e3e60ccbcbd1881780f4ec

1 files changed, 108 insertions, 0 deletions

diff --git a/targets_affinity.cc b/targets_affinity.cc
new file mode 100644
index 0000000..11903a9
--- /dev/null
+++ b/targets_affinity.cc
@@ -0,0 +1,108 @@
+// Copyright 2016 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 "components/zucchini/targets_affinity.h"
+
+#include <algorithm>
+
+#include "base/logging.h"
+#include "components/zucchini/equivalence_map.h"
+
+namespace zucchini {
+
+namespace {
+
+constexpr uint32_t kNoLabel = 0;
+}
+
+TargetsAffinity::TargetsAffinity() = default;
+TargetsAffinity::~TargetsAffinity() = default;
+
+void TargetsAffinity::InferFromSimilarities(
+    const EquivalenceMap& equivalences,
+    const std::vector<offset_t>& old_targets,
+    const std::vector<offset_t>& new_targets) {
+  forward_association_.assign(old_targets.size(), {});
+  backward_association_.assign(new_targets.size(), {});
+
+  if (old_targets.empty() || new_targets.empty())
+    return;
+
+  key_t new_key = 0;
+  for (auto candidate : equivalences) {  // Sorted by |dst_offset|.
+    DCHECK_GT(candidate.similarity, 0.0);
+    while (new_key < new_targets.size() &&
+           new_targets[new_key] < candidate.eq.dst_offset) {
+      ++new_key;
+    }
+
+    // Visit each new target covered by |candidate.eq| and find / update its
+    // associated old target.
+    for (; new_key < new_targets.size() &&
+           new_targets[new_key] < candidate.eq.dst_end();
+         ++new_key) {
+      if (backward_association_[new_key].affinity >= candidate.similarity)
+        continue;
+
+      DCHECK_GE(new_targets[new_key], candidate.eq.dst_offset);
+      offset_t old_target = new_targets[new_key] - candidate.eq.dst_offset +
+                            candidate.eq.src_offset;
+      auto old_it =
+          std::lower_bound(old_targets.begin(), old_targets.end(), old_target);
+      // If new target can be mapped via |candidate.eq| to an old target, then
+      // attempt to associate them. Multiple new targets can compete for the
+      // same old target. The heuristic here makes selections to maximize
+      // |candidate.similarity|, and if a tie occurs, minimize new target offset
+      // (by first-come, first-served).
+      if (old_it != old_targets.end() && *old_it == old_target) {
+        key_t old_key = static_cast<key_t>(old_it - old_targets.begin());
+        if (candidate.similarity > forward_association_[old_key].affinity) {
+          // Reset other associations.
+          if (forward_association_[old_key].affinity > 0.0)
+            backward_association_[forward_association_[old_key].other] = {};
+          if (backward_association_[new_key].affinity > 0.0)
+            forward_association_[backward_association_[new_key].other] = {};
+          // Assign new association.
+          forward_association_[old_key] = {new_key, candidate.similarity};
+          backward_association_[new_key] = {old_key, candidate.similarity};
+        }
+      }
+    }
+  }
+}
+
+uint32_t TargetsAffinity::AssignLabels(double min_affinity,
+                                       std::vector<uint32_t>* old_labels,
+                                       std::vector<uint32_t>* new_labels) {
+  old_labels->assign(forward_association_.size(), kNoLabel);
+  new_labels->assign(backward_association_.size(), kNoLabel);
+
+  uint32_t label = kNoLabel + 1;
+  for (key_t old_key = 0; old_key < forward_association_.size(); ++old_key) {
+    Association association = forward_association_[old_key];
+    if (association.affinity >= min_affinity) {
+      (*old_labels)[old_key] = label;
+      DCHECK_EQ(0U, (*new_labels)[association.other]);
+      (*new_labels)[association.other] = label;
+      ++label;
+    }
+  }
+  return label;
+}
+
+double TargetsAffinity::AffinityBetween(key_t old_key, key_t new_key) const {
+  DCHECK_LT(old_key, forward_association_.size());
+  DCHECK_LT(new_key, backward_association_.size());
+  if (forward_association_[old_key].affinity > 0.0 &&
+      forward_association_[old_key].other == new_key) {
+    DCHECK_EQ(backward_association_[new_key].other, old_key);
+    DCHECK_EQ(forward_association_[old_key].affinity,
+              backward_association_[new_key].affinity);
+    return forward_association_[old_key].affinity;
+  }
+  return -std::max(forward_association_[old_key].affinity,
+                   backward_association_[new_key].affinity);
+}
+
+}  // namespace zucchini