RenameDetector.java

  1. /*
  2.  * Copyright (C) 2010, Google Inc. and others
  3.  *
  4.  * This program and the accompanying materials are made available under the
  5.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  6.  * https://www.eclipse.org/org/documents/edl-v10.php.
  7.  *
  8.  * SPDX-License-Identifier: BSD-3-Clause
  9.  */

  11. package org.eclipse.jgit.diff;

  13. import static org.eclipse.jgit.diff.DiffEntry.Side.NEW;
  14. import static org.eclipse.jgit.diff.DiffEntry.Side.OLD;

  16. import java.io.IOException;
  17. import java.util.ArrayList;
  18. import java.util.Arrays;
  19. import java.util.Collection;
  20. import java.util.Collections;
  21. import java.util.Comparator;
  22. import java.util.HashMap;
  23. import java.util.List;

  25. import org.eclipse.jgit.diff.DiffEntry.ChangeType;
  26. import org.eclipse.jgit.diff.SimilarityIndex.TableFullException;
  27. import org.eclipse.jgit.errors.CancelledException;
  28. import org.eclipse.jgit.internal.JGitText;
  29. import org.eclipse.jgit.lib.AbbreviatedObjectId;
  30. import org.eclipse.jgit.lib.FileMode;
  31. import org.eclipse.jgit.lib.NullProgressMonitor;
  32. import org.eclipse.jgit.lib.ObjectReader;
  33. import org.eclipse.jgit.lib.ProgressMonitor;
  34. import org.eclipse.jgit.lib.Repository;

  36. /**
  37.  * Detect and resolve object renames.
  38.  */
  39. public class RenameDetector {
  40.     private static final int EXACT_RENAME_SCORE = 100;

  42.     private static final Comparator<DiffEntry> DIFF_COMPARATOR = new Comparator<DiffEntry>() {
  43.         @Override
  44.         public int compare(DiffEntry a, DiffEntry b) {
  45.             int cmp = nameOf(a).compareTo(nameOf(b));
  46.             if (cmp == 0)
  47.                 cmp = sortOf(a.getChangeType()) - sortOf(b.getChangeType());
  48.             return cmp;
  49.         }

  51.         private String nameOf(DiffEntry ent) {
  52.             // Sort by the new name, unless the change is a delete. On
  53.             // deletes the new name is /dev/null, so we sort instead by
  54.             // the old name.
  55.             //
  56.             if (ent.changeType == ChangeType.DELETE)
  57.                 return ent.oldPath;
  58.             return ent.newPath;
  59.         }

  61.         private int sortOf(ChangeType changeType) {
  62.             // Sort deletes before adds so that a major type change for
  63.             // a file path (such as symlink to regular file) will first
  64.             // remove the path, then add it back with the new type.
  65.             //
  66.             switch (changeType) {
  67.             case DELETE:
  68.                 return 1;
  69.             case ADD:
  70.                 return 2;
  71.             default:
  72.                 return 10;
  73.             }
  74.         }
  75.     };

  77.     private List<DiffEntry> entries;

  79.     private List<DiffEntry> deleted;

  81.     private List<DiffEntry> added;

  83.     private boolean done;

  85.     private final ObjectReader objectReader;

  87.     /** Similarity score required to pair an add/delete as a rename. */
  88.     private int renameScore = 60;

  90.     /**
  91.      * Similarity score required to keep modified file pairs together. Any
  92.      * modified file pairs with a similarity score below this will be broken
  93.      * apart.
  94.      */
  95.     private int breakScore = -1;

  97.     /** Limit in the number of files to consider for renames. */
  98.     private int renameLimit;

  100.     /** Set if the number of adds or deletes was over the limit. */
  101.     private boolean overRenameLimit;

  103.     /**
  104.      * Create a new rename detector for the given repository
  105.      *
  106.      * @param repo
  107.      *            the repository to use for rename detection
  108.      */
  109.     public RenameDetector(Repository repo) {
  110.         this(repo.newObjectReader(), repo.getConfig().get(DiffConfig.KEY));
  111.     }

  113.     /**
  114.      * Create a new rename detector with a specified reader and diff config.
  115.      *
  116.      * @param reader
  117.      *            reader to obtain objects from the repository with.
  118.      * @param cfg
  119.      *            diff config specifying rename detection options.
  120.      * @since 3.0
  121.      */
  122.     public RenameDetector(ObjectReader reader, DiffConfig cfg) {
  123.         objectReader = reader.newReader();
  124.         renameLimit = cfg.getRenameLimit();
  125.         reset();
  126.     }

  128.     /**
  129.      * Get rename score
  130.      *
  131.      * @return minimum score required to pair an add/delete as a rename. The
  132.      *         score ranges are within the bounds of (0, 100).
  133.      */
  134.     public int getRenameScore() {
  135.         return renameScore;
  136.     }

  138.     /**
  139.      * Set the minimum score required to pair an add/delete as a rename.
  140.      * <p>
  141.      * When comparing two files together their score must be greater than or
  142.      * equal to the rename score for them to be considered a rename match. The
  143.      * score is computed based on content similarity, so a score of 60 implies
  144.      * that approximately 60% of the bytes in the files are identical.
  145.      *
  146.      * @param score
  147.      *            new rename score, must be within [0, 100].
  148.      * @throws java.lang.IllegalArgumentException
  149.      *             the score was not within [0, 100].
  150.      */
  151.     public void setRenameScore(int score) {
  152.         if (score < 0 || score > 100)
  153.             throw new IllegalArgumentException(
  154.                     JGitText.get().similarityScoreMustBeWithinBounds);
  155.         renameScore = score;
  156.     }

  158.     /**
  159.      * Get break score
  160.      *
  161.      * @return the similarity score required to keep modified file pairs
  162.      *         together. Any modify pairs that score below this will be broken
  163.      *         apart into separate add/deletes. Values less than or equal to
  164.      *         zero indicate that no modifies will be broken apart. Values over
  165.      *         100 cause all modify pairs to be broken.
  166.      */
  167.     public int getBreakScore() {
  168.         return breakScore;
  169.     }

  171.     /**
  172.      * Set break score
  173.      *
  174.      * @param breakScore
  175.      *            the similarity score required to keep modified file pairs
  176.      *            together. Any modify pairs that score below this will be
  177.      *            broken apart into separate add/deletes. Values less than or
  178.      *            equal to zero indicate that no modifies will be broken apart.
  179.      *            Values over 100 cause all modify pairs to be broken.
  180.      */
  181.     public void setBreakScore(int breakScore) {
  182.         this.breakScore = breakScore;
  183.     }

  185.     /**
  186.      * Get rename limit
  187.      *
  188.      * @return limit on number of paths to perform inexact rename detection
  189.      */
  190.     public int getRenameLimit() {
  191.         return renameLimit;
  192.     }

  194.     /**
  195.      * Set the limit on the number of files to perform inexact rename detection.
  196.      * <p>
  197.      * The rename detector has to build a square matrix of the rename limit on
  198.      * each side, then perform that many file compares to determine similarity.
  199.      * If 1000 files are added, and 1000 files are deleted, a 1000*1000 matrix
  200.      * must be allocated, and 1,000,000 file compares may need to be performed.
  201.      *
  202.      * @param limit
  203.      *            new file limit. 0 means no limit; a negative number means no
  204.      *            inexact rename detection will be performed, only exact rename
  205.      *            detection.
  206.      */
  207.     public void setRenameLimit(int limit) {
  208.         renameLimit = limit;
  209.     }

  211.     /**
  212.      * Check if the detector is over the rename limit.
  213.      * <p>
  214.      * This method can be invoked either before or after {@code getEntries} has
  215.      * been used to perform rename detection.
  216.      *
  217.      * @return true if the detector has more file additions or removals than the
  218.      *         rename limit is currently set to. In such configurations the
  219.      *         detector will skip expensive computation.
  220.      */
  221.     public boolean isOverRenameLimit() {
  222.         if (done)
  223.             return overRenameLimit;
  224.         int cnt = Math.max(added.size(), deleted.size());
  225.         return getRenameLimit() != 0 && getRenameLimit() < cnt;
  226.     }

  228.     /**
  229.      * Add entries to be considered for rename detection.
  230.      *
  231.      * @param entriesToAdd
  232.      *            one or more entries to add.
  233.      * @throws java.lang.IllegalStateException
  234.      *             if {@code getEntries} was already invoked.
  235.      */
  236.     public void addAll(Collection<DiffEntry> entriesToAdd) {
  237.         if (done)
  238.             throw new IllegalStateException(JGitText.get().renamesAlreadyFound);

  240.         for (DiffEntry entry : entriesToAdd) {
  241.             switch (entry.getChangeType()) {
  242.             case ADD:
  243.                 added.add(entry);
  244.                 break;

  246.             case DELETE:
  247.                 deleted.add(entry);
  248.                 break;

  250.             case MODIFY:
  251.                 if (sameType(entry.getOldMode(), entry.getNewMode())) {
  252.                     entries.add(entry);
  253.                 } else {
  254.                     List<DiffEntry> tmp = DiffEntry.breakModify(entry);
  255.                     deleted.add(tmp.get(0));
  256.                     added.add(tmp.get(1));
  257.                 }
  258.                 break;

  260.             case COPY:
  261.             case RENAME:
  262.             default:
  263.                 entries.add(entry);
  264.             }
  265.         }
  266.     }

  268.     /**
  269.      * Add an entry to be considered for rename detection.
  270.      *
  271.      * @param entry
  272.      *            to add.
  273.      * @throws java.lang.IllegalStateException
  274.      *             if {@code getEntries} was already invoked.
  275.      */
  276.     public void add(DiffEntry entry) {
  277.         addAll(Collections.singletonList(entry));
  278.     }

  280.     /**
  281.      * Detect renames in the current file set.
  282.      * <p>
  283.      * This convenience function runs without a progress monitor.
  284.      *
  285.      * @return an unmodifiable list of {@link org.eclipse.jgit.diff.DiffEntry}s
  286.      *         representing all files that have been changed.
  287.      * @throws java.io.IOException
  288.      *             file contents cannot be read from the repository.
  289.      */
  290.     public List<DiffEntry> compute() throws IOException {
  291.         return compute(NullProgressMonitor.INSTANCE);
  292.     }

  294.     /**
  295.      * Detect renames in the current file set.
  296.      *
  297.      * @param pm
  298.      *            report progress during the detection phases.
  299.      * @return an unmodifiable list of {@link org.eclipse.jgit.diff.DiffEntry}s
  300.      *         representing all files that have been changed.
  301.      * @throws java.io.IOException
  302.      *             file contents cannot be read from the repository.
  303.      * @throws CancelledException
  304.      *             if rename detection was cancelled
  305.      */
  306.     // TODO(ms): use org.eclipse.jgit.api.errors.CanceledException in next major
  307.     // version
  308.     public List<DiffEntry> compute(ProgressMonitor pm)
  309.             throws IOException, CancelledException {
  310.         if (!done) {
  311.             try {
  312.                 return compute(objectReader, pm);
  313.             } finally {
  314.                 objectReader.close();
  315.             }
  316.         }
  317.         return Collections.unmodifiableList(entries);
  318.     }

  320.     /**
  321.      * Detect renames in the current file set.
  322.      *
  323.      * @param reader
  324.      *            reader to obtain objects from the repository with.
  325.      * @param pm
  326.      *            report progress during the detection phases.
  327.      * @return an unmodifiable list of {@link org.eclipse.jgit.diff.DiffEntry}s
  328.      *         representing all files that have been changed.
  329.      * @throws java.io.IOException
  330.      *             file contents cannot be read from the repository.
  331.      * @throws CancelledException
  332.      *             if rename detection was cancelled
  333.      */
  334.     // TODO(ms): use org.eclipse.jgit.api.errors.CanceledException in next major
  335.     // version
  336.     public List<DiffEntry> compute(ObjectReader reader, ProgressMonitor pm)
  337.             throws IOException, CancelledException {
  338.         final ContentSource cs = ContentSource.create(reader);
  339.         return compute(new ContentSource.Pair(cs, cs), pm);
  340.     }

  342.     /**
  343.      * Detect renames in the current file set.
  344.      *
  345.      * @param reader
  346.      *            reader to obtain objects from the repository with.
  347.      * @param pm
  348.      *            report progress during the detection phases.
  349.      * @return an unmodifiable list of {@link org.eclipse.jgit.diff.DiffEntry}s
  350.      *         representing all files that have been changed.
  351.      * @throws java.io.IOException
  352.      *             file contents cannot be read from the repository.
  353.      * @throws CancelledException
  354.      *             if rename detection was cancelled
  355.      */
  356.     // TODO(ms): use org.eclipse.jgit.api.errors.CanceledException in next major
  357.     // version
  358.     public List<DiffEntry> compute(ContentSource.Pair reader, ProgressMonitor pm)
  359.             throws IOException, CancelledException {
  360.         if (!done) {
  361.             done = true;

  363.             if (pm == null)
  364.                 pm = NullProgressMonitor.INSTANCE;

  366.             if (0 < breakScore)
  367.                 breakModifies(reader, pm);

  369.             if (!added.isEmpty() && !deleted.isEmpty())
  370.                 findExactRenames(pm);

  372.             if (!added.isEmpty() && !deleted.isEmpty())
  373.                 findContentRenames(reader, pm);

  375.             if (0 < breakScore && !added.isEmpty() && !deleted.isEmpty())
  376.                 rejoinModifies(pm);

  378.             entries.addAll(added);
  379.             added = null;

  381.             entries.addAll(deleted);
  382.             deleted = null;

  384.             Collections.sort(entries, DIFF_COMPARATOR);
  385.         }
  386.         return Collections.unmodifiableList(entries);
  387.     }

  389.     /**
  390.      * Reset this rename detector for another rename detection pass.
  391.      */
  392.     public void reset() {
  393.         entries = new ArrayList<>();
  394.         deleted = new ArrayList<>();
  395.         added = new ArrayList<>();
  396.         done = false;
  397.     }

  399.     private void advanceOrCancel(ProgressMonitor pm) throws CancelledException {
  400.         if (pm.isCancelled()) {
  401.             throw new CancelledException(JGitText.get().renameCancelled);
  402.         }
  403.         pm.update(1);
  404.     }

  406.     private void breakModifies(ContentSource.Pair reader, ProgressMonitor pm)
  407.             throws IOException, CancelledException {
  408.         ArrayList<DiffEntry> newEntries = new ArrayList<>(entries.size());

  410.         pm.beginTask(JGitText.get().renamesBreakingModifies, entries.size());

  412.         for (int i = 0; i < entries.size(); i++) {
  413.             DiffEntry e = entries.get(i);
  414.             if (e.getChangeType() == ChangeType.MODIFY) {
  415.                 int score = calculateModifyScore(reader, e);
  416.                 if (score < breakScore) {
  417.                     List<DiffEntry> tmp = DiffEntry.breakModify(e);
  418.                     DiffEntry del = tmp.get(0);
  419.                     del.score = score;
  420.                     deleted.add(del);
  421.                     added.add(tmp.get(1));
  422.                 } else {
  423.                     newEntries.add(e);
  424.                 }
  425.             } else {
  426.                 newEntries.add(e);
  427.             }
  428.             advanceOrCancel(pm);
  429.         }

  431.         entries = newEntries;
  432.     }

  434.     private void rejoinModifies(ProgressMonitor pm) throws CancelledException {
  435.         HashMap<String, DiffEntry> nameMap = new HashMap<>();
  436.         ArrayList<DiffEntry> newAdded = new ArrayList<>(added.size());

  438.         pm.beginTask(JGitText.get().renamesRejoiningModifies, added.size()
  439.                 + deleted.size());

  441.         for (DiffEntry src : deleted) {
  442.             nameMap.put(src.oldPath, src);
  443.             advanceOrCancel(pm);
  444.         }

  446.         for (DiffEntry dst : added) {
  447.             DiffEntry src = nameMap.remove(dst.newPath);
  448.             if (src != null) {
  449.                 if (sameType(src.oldMode, dst.newMode)) {
  450.                     entries.add(DiffEntry.pair(ChangeType.MODIFY, src, dst,
  451.                             src.score));
  452.                 } else {
  453.                     nameMap.put(src.oldPath, src);
  454.                     newAdded.add(dst);
  455.                 }
  456.             } else {
  457.                 newAdded.add(dst);
  458.             }
  459.             advanceOrCancel(pm);
  460.         }

  462.         added = newAdded;
  463.         deleted = new ArrayList<>(nameMap.values());
  464.     }

  466.     private int calculateModifyScore(ContentSource.Pair reader, DiffEntry d)
  467.             throws IOException {
  468.         try {
  469.             SimilarityIndex src = new SimilarityIndex();
  470.             src.hash(reader.open(OLD, d));
  471.             src.sort();

  473.             SimilarityIndex dst = new SimilarityIndex();
  474.             dst.hash(reader.open(NEW, d));
  475.             dst.sort();
  476.             return src.score(dst, 100);
  477.         } catch (TableFullException tableFull) {
  478.             // If either table overflowed while being constructed, don't allow
  479.             // the pair to be broken. Returning 1 higher than breakScore will
  480.             // ensure its not similar, but not quite dissimilar enough to break.
  481.             //
  482.             overRenameLimit = true;
  483.             return breakScore + 1;
  484.         }
  485.     }

  487.     private void findContentRenames(ContentSource.Pair reader,
  488.             ProgressMonitor pm)
  489.             throws IOException, CancelledException {
  490.         int cnt = Math.max(added.size(), deleted.size());
  491.         if (getRenameLimit() == 0 || cnt <= getRenameLimit()) {
  492.             SimilarityRenameDetector d;

  494.             d = new SimilarityRenameDetector(reader, deleted, added);
  495.             d.setRenameScore(getRenameScore());
  496.             d.compute(pm);
  497.             overRenameLimit |= d.isTableOverflow();
  498.             deleted = d.getLeftOverSources();
  499.             added = d.getLeftOverDestinations();
  500.             entries.addAll(d.getMatches());
  501.         } else {
  502.             overRenameLimit = true;
  503.         }
  504.     }

  506.     @SuppressWarnings("unchecked")
  507.     private void findExactRenames(ProgressMonitor pm)
  508.             throws CancelledException {
  509.         pm.beginTask(JGitText.get().renamesFindingExact, //
  510.                 added.size() + added.size() + deleted.size()
  511.                         + added.size() * deleted.size());

  513.         HashMap<AbbreviatedObjectId, Object> deletedMap = populateMap(deleted, pm);
  514.         HashMap<AbbreviatedObjectId, Object> addedMap = populateMap(added, pm);

  516.         ArrayList<DiffEntry> uniqueAdds = new ArrayList<>(added.size());
  517.         ArrayList<List<DiffEntry>> nonUniqueAdds = new ArrayList<>();

  519.         for (Object o : addedMap.values()) {
  520.             if (o instanceof DiffEntry)
  521.                 uniqueAdds.add((DiffEntry) o);
  522.             else
  523.                 nonUniqueAdds.add((List<DiffEntry>) o);
  524.         }

  526.         ArrayList<DiffEntry> left = new ArrayList<>(added.size());

  528.         for (DiffEntry a : uniqueAdds) {
  529.             Object del = deletedMap.get(a.newId);
  530.             if (del instanceof DiffEntry) {
  531.                 // We have one add to one delete: pair them if they are the same
  532.                 // type
  533.                 DiffEntry e = (DiffEntry) del;
  534.                 if (sameType(e.oldMode, a.newMode)) {
  535.                     e.changeType = ChangeType.RENAME;
  536.                     entries.add(exactRename(e, a));
  537.                 } else {
  538.                     left.add(a);
  539.                 }
  540.             } else if (del != null) {
  541.                 // We have one add to many deletes: find the delete with the
  542.                 // same type and closest name to the add, then pair them
  543.                 List<DiffEntry> list = (List<DiffEntry>) del;
  544.                 DiffEntry best = bestPathMatch(a, list);
  545.                 if (best != null) {
  546.                     best.changeType = ChangeType.RENAME;
  547.                     entries.add(exactRename(best, a));
  548.                 } else {
  549.                     left.add(a);
  550.                 }
  551.             } else {
  552.                 left.add(a);
  553.             }
  554.             advanceOrCancel(pm);
  555.         }

  557.         for (List<DiffEntry> adds : nonUniqueAdds) {
  558.             Object o = deletedMap.get(adds.get(0).newId);
  559.             if (o instanceof DiffEntry) {
  560.                 // We have many adds to one delete: find the add with the same
  561.                 // type and closest name to the delete, then pair them. Mark the
  562.                 // rest as copies of the delete.
  563.                 DiffEntry d = (DiffEntry) o;
  564.                 DiffEntry best = bestPathMatch(d, adds);
  565.                 if (best != null) {
  566.                     d.changeType = ChangeType.RENAME;
  567.                     entries.add(exactRename(d, best));
  568.                     for (DiffEntry a : adds) {
  569.                         if (a != best) {
  570.                             if (sameType(d.oldMode, a.newMode)) {
  571.                                 entries.add(exactCopy(d, a));
  572.                             } else {
  573.                                 left.add(a);
  574.                             }
  575.                         }
  576.                     }
  577.                 } else {
  578.                     left.addAll(adds);
  579.                 }
  580.             } else if (o != null) {
  581.                 // We have many adds to many deletes: score all the adds against
  582.                 // all the deletes by path name, take the best matches, pair
  583.                 // them as renames, then call the rest copies
  584.                 List<DiffEntry> dels = (List<DiffEntry>) o;
  585.                 long[] matrix = new long[dels.size() * adds.size()];
  586.                 int mNext = 0;
  587.                 for (int delIdx = 0; delIdx < dels.size(); delIdx++) {
  588.                     String deletedName = dels.get(delIdx).oldPath;

  590.                     for (int addIdx = 0; addIdx < adds.size(); addIdx++) {
  591.                         String addedName = adds.get(addIdx).newPath;

  593.                         int score = SimilarityRenameDetector.nameScore(addedName, deletedName);
  594.                         matrix[mNext] = SimilarityRenameDetector.encode(score, delIdx, addIdx);
  595.                         mNext++;
  596.                         if (pm.isCancelled()) {
  597.                             throw new CancelledException(
  598.                                     JGitText.get().renameCancelled);
  599.                         }
  600.                     }
  601.                 }

  603.                 Arrays.sort(matrix);

  605.                 for (--mNext; mNext >= 0; mNext--) {
  606.                     long ent = matrix[mNext];
  607.                     int delIdx = SimilarityRenameDetector.srcFile(ent);
  608.                     int addIdx = SimilarityRenameDetector.dstFile(ent);
  609.                     DiffEntry d = dels.get(delIdx);
  610.                     DiffEntry a = adds.get(addIdx);

  612.                     if (a == null) {
  613.                         advanceOrCancel(pm);
  614.                         continue; // was already matched earlier
  615.                     }

  617.                     ChangeType type;
  618.                     if (d.changeType == ChangeType.DELETE) {
  619.                         // First use of this source file. Tag it as a rename so we
  620.                         // later know it is already been used as a rename, other
  621.                         // matches (if any) will claim themselves as copies instead.
  622.                         //
  623.                         d.changeType = ChangeType.RENAME;
  624.                         type = ChangeType.RENAME;
  625.                     } else {
  626.                         type = ChangeType.COPY;
  627.                     }

  629.                     entries.add(DiffEntry.pair(type, d, a, 100));
  630.                     adds.set(addIdx, null); // Claim the destination was matched.
  631.                     advanceOrCancel(pm);
  632.                 }
  633.             } else {
  634.                 left.addAll(adds);
  635.             }
  636.             advanceOrCancel(pm);
  637.         }
  638.         added = left;

  640.         deleted = new ArrayList<>(deletedMap.size());
  641.         for (Object o : deletedMap.values()) {
  642.             if (o instanceof DiffEntry) {
  643.                 DiffEntry e = (DiffEntry) o;
  644.                 if (e.changeType == ChangeType.DELETE)
  645.                     deleted.add(e);
  646.             } else {
  647.                 List<DiffEntry> list = (List<DiffEntry>) o;
  648.                 for (DiffEntry e : list) {
  649.                     if (e.changeType == ChangeType.DELETE)
  650.                         deleted.add(e);
  651.                 }
  652.             }
  653.         }
  654.         pm.endTask();
  655.     }

  657.     /**
  658.      * Find the best match by file path for a given DiffEntry from a list of
  659.      * DiffEntrys. The returned DiffEntry will be of the same type as <src>. If
  660.      * no DiffEntry can be found that has the same type, this method will return
  661.      * null.
  662.      *
  663.      * @param src
  664.      *            the DiffEntry to try to find a match for
  665.      * @param list
  666.      *            a list of DiffEntrys to search through
  667.      * @return the DiffEntry from <list> who's file path best matches <src>
  668.      */
  669.     private static DiffEntry bestPathMatch(DiffEntry src, List<DiffEntry> list) {
  670.         DiffEntry best = null;
  671.         int score = -1;

  673.         for (DiffEntry d : list) {
  674.             if (sameType(mode(d), mode(src))) {
  675.                 int tmp = SimilarityRenameDetector
  676.                         .nameScore(path(d), path(src));
  677.                 if (tmp > score) {
  678.                     best = d;
  679.                     score = tmp;
  680.                 }
  681.             }
  682.         }

  684.         return best;
  685.     }

  687.     @SuppressWarnings("unchecked")
  688.     private HashMap<AbbreviatedObjectId, Object> populateMap(
  689.             List<DiffEntry> diffEntries, ProgressMonitor pm)
  690.             throws CancelledException {
  691.         HashMap<AbbreviatedObjectId, Object> map = new HashMap<>();
  692.         for (DiffEntry de : diffEntries) {
  693.             Object old = map.put(id(de), de);
  694.             if (old instanceof DiffEntry) {
  695.                 ArrayList<DiffEntry> list = new ArrayList<>(2);
  696.                 list.add((DiffEntry) old);
  697.                 list.add(de);
  698.                 map.put(id(de), list);
  699.             } else if (old != null) {
  700.                 // Must be a list of DiffEntries
  701.                 ((List<DiffEntry>) old).add(de);
  702.                 map.put(id(de), old);
  703.             }
  704.             advanceOrCancel(pm);
  705.         }
  706.         return map;
  707.     }

  709.     private static String path(DiffEntry de) {
  710.         return de.changeType == ChangeType.DELETE ? de.oldPath : de.newPath;
  711.     }

  713.     private static FileMode mode(DiffEntry de) {
  714.         return de.changeType == ChangeType.DELETE ? de.oldMode : de.newMode;
  715.     }

  717.     private static AbbreviatedObjectId id(DiffEntry de) {
  718.         return de.changeType == ChangeType.DELETE ? de.oldId : de.newId;
  719.     }

  721.     static boolean sameType(FileMode a, FileMode b) {
  722.         // Files have to be of the same type in order to rename them.
  723.         // We would never want to rename a file to a gitlink, or a
  724.         // symlink to a file.
  725.         //
  726.         int aType = a.getBits() & FileMode.TYPE_MASK;
  727.         int bType = b.getBits() & FileMode.TYPE_MASK;
  728.         return aType == bType;
  729.     }

  731.     private static DiffEntry exactRename(DiffEntry src, DiffEntry dst) {
  732.         return DiffEntry.pair(ChangeType.RENAME, src, dst, EXACT_RENAME_SCORE);
  733.     }

  735.     private static DiffEntry exactCopy(DiffEntry src, DiffEntry dst) {
  736.         return DiffEntry.pair(ChangeType.COPY, src, dst, EXACT_RENAME_SCORE);
  737.     }
  738. }
Created with JaCoCo 0.8.6.202009150832