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;
  15. import static org.eclipse.jgit.storage.pack.PackConfig.DEFAULT_BIG_FILE_THRESHOLD;

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

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

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

  43.     private static final Comparator<DiffEntry> DIFF_COMPARATOR = new Comparator<>() {

  45.         @Override
  46.         public int compare(DiffEntry a, DiffEntry b) {
  47.             int cmp = nameOf(a).compareTo(nameOf(b));
  48.             if (cmp == 0)
  49.                 cmp = sortOf(a.getChangeType()) - sortOf(b.getChangeType());
  50.             return cmp;
  51.         }

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

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

  79.     private List<DiffEntry> entries;

  81.     private List<DiffEntry> deleted;

  83.     private List<DiffEntry> added;

  85.     private boolean done;

  87.     private final ObjectReader objectReader;

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

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

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

  102.     /**
  103.      * File size threshold (in bytes) for detecting renames. Files larger
  104.      * than this size will not be processed for renames.
  105.      */
  106.     private int bigFileThreshold = DEFAULT_BIG_FILE_THRESHOLD;

  108.     /**
  109.      * Skip detecting content renames for binary files. Content renames are
  110.      * those that are not exact, that is with a slight content modification
  111.      * between the two files.
  112.      */
  113.     private boolean skipContentRenamesForBinaryFiles = false;

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

  118.     /**
  119.      * Create a new rename detector for the given repository
  120.      *
  121.      * @param repo
  122.      *            the repository to use for rename detection
  123.      */
  124.     public RenameDetector(Repository repo) {
  125.         this(repo.newObjectReader(), repo.getConfig().get(DiffConfig.KEY));
  126.     }

  128.     /**
  129.      * Create a new rename detector with a specified reader and diff config.
  130.      *
  131.      * @param reader
  132.      *            reader to obtain objects from the repository with.
  133.      * @param cfg
  134.      *            diff config specifying rename detection options.
  135.      * @since 3.0
  136.      */
  137.     public RenameDetector(ObjectReader reader, DiffConfig cfg) {
  138.         objectReader = reader.newReader();
  139.         renameLimit = cfg.getRenameLimit();
  140.         reset();
  141.     }

  143.     /**
  144.      * Get rename score
  145.      *
  146.      * @return minimum score required to pair an add/delete as a rename. The
  147.      *         score ranges are within the bounds of (0, 100).
  148.      */
  149.     public int getRenameScore() {
  150.         return renameScore;
  151.     }

  153.     /**
  154.      * Set the minimum score required to pair an add/delete as a rename.
  155.      * <p>
  156.      * When comparing two files together their score must be greater than or
  157.      * equal to the rename score for them to be considered a rename match. The
  158.      * score is computed based on content similarity, so a score of 60 implies
  159.      * that approximately 60% of the bytes in the files are identical.
  160.      *
  161.      * @param score
  162.      *            new rename score, must be within [0, 100].
  163.      * @throws java.lang.IllegalArgumentException
  164.      *             the score was not within [0, 100].
  165.      */
  166.     public void setRenameScore(int score) {
  167.         if (score < 0 || score > 100)
  168.             throw new IllegalArgumentException(
  169.                     JGitText.get().similarityScoreMustBeWithinBounds);
  170.         renameScore = score;
  171.     }

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

  186.     /**
  187.      * Set break score
  188.      *
  189.      * @param breakScore
  190.      *            the similarity score required to keep modified file pairs
  191.      *            together. Any modify pairs that score below this will be
  192.      *            broken apart into separate add/deletes. Values less than or
  193.      *            equal to zero indicate that no modifies will be broken apart.
  194.      *            Values over 100 cause all modify pairs to be broken.
  195.      */
  196.     public void setBreakScore(int breakScore) {
  197.         this.breakScore = breakScore;
  198.     }

  200.     /**
  201.      * Get rename limit
  202.      *
  203.      * @return limit on number of paths to perform inexact rename detection
  204.      */
  205.     public int getRenameLimit() {
  206.         return renameLimit;
  207.     }

  209.     /**
  210.      * Set the limit on the number of files to perform inexact rename detection.
  211.      * <p>
  212.      * The rename detector has to build a square matrix of the rename limit on
  213.      * each side, then perform that many file compares to determine similarity.
  214.      * If 1000 files are added, and 1000 files are deleted, a 1000*1000 matrix
  215.      * must be allocated, and 1,000,000 file compares may need to be performed.
  216.      *
  217.      * @param limit
  218.      *            new file limit. 0 means no limit; a negative number means no
  219.      *            inexact rename detection will be performed, only exact rename
  220.      *            detection.
  221.      */
  222.     public void setRenameLimit(int limit) {
  223.         renameLimit = limit;
  224.     }

  226.     /**
  227.      * Get file size threshold for detecting renames. Files larger
  228.      * than this size will not be processed for rename detection.
  229.      *
  230.      * @return threshold in bytes of the file size.
  231.      * @since 5.12
  232.      */
  233.     public int getBigFileThreshold() { return bigFileThreshold; }

  235.     /**
  236.      * Set the file size threshold for detecting renames. Files larger than this
  237.      * threshold will be skipped during rename detection computation.
  238.      *
  239.      * @param threshold file size threshold in bytes.
  240.      * @since 5.12
  241.      */
  242.     public void setBigFileThreshold(int threshold) {
  243.         this.bigFileThreshold = threshold;
  244.     }

  246.     /**
  247.      * Get skipping detecting content renames for binary files.
  248.      *
  249.      * @return true if content renames should be skipped for binary files, false otherwise.
  250.      * @since 5.12
  251.      */
  252.     public boolean getSkipContentRenamesForBinaryFiles() {
  253.         return skipContentRenamesForBinaryFiles;
  254.     }

  256.     /**
  257.      * Sets skipping detecting content renames for binary files.
  258.      *
  259.      * @param value true if content renames should be skipped for binary files, false otherwise.
  260.      * @since 5.12
  261.      */
  262.     public void setSkipContentRenamesForBinaryFiles(boolean value) {
  263.         this.skipContentRenamesForBinaryFiles = value;
  264.     }

  266.     /**
  267.      * Check if the detector is over the rename limit.
  268.      * <p>
  269.      * This method can be invoked either before or after {@code getEntries} has
  270.      * been used to perform rename detection.
  271.      *
  272.      * @return true if the detector has more file additions or removals than the
  273.      *         rename limit is currently set to. In such configurations the
  274.      *         detector will skip expensive computation.
  275.      */
  276.     public boolean isOverRenameLimit() {
  277.         if (done)
  278.             return overRenameLimit;
  279.         int cnt = Math.max(added.size(), deleted.size());
  280.         return getRenameLimit() != 0 && getRenameLimit() < cnt;
  281.     }

  283.     /**
  284.      * Add entries to be considered for rename detection.
  285.      *
  286.      * @param entriesToAdd
  287.      *            one or more entries to add.
  288.      * @throws java.lang.IllegalStateException
  289.      *             if {@code getEntries} was already invoked.
  290.      */
  291.     public void addAll(Collection<DiffEntry> entriesToAdd) {
  292.         if (done)
  293.             throw new IllegalStateException(JGitText.get().renamesAlreadyFound);

  295.         for (DiffEntry entry : entriesToAdd) {
  296.             switch (entry.getChangeType()) {
  297.             case ADD:
  298.                 added.add(entry);
  299.                 break;

  301.             case DELETE:
  302.                 deleted.add(entry);
  303.                 break;

  305.             case MODIFY:
  306.                 if (sameType(entry.getOldMode(), entry.getNewMode())) {
  307.                     entries.add(entry);
  308.                 } else {
  309.                     List<DiffEntry> tmp = DiffEntry.breakModify(entry);
  310.                     deleted.add(tmp.get(0));
  311.                     added.add(tmp.get(1));
  312.                 }
  313.                 break;

  315.             case COPY:
  316.             case RENAME:
  317.             default:
  318.                 entries.add(entry);
  319.             }
  320.         }
  321.     }

  323.     /**
  324.      * Add an entry to be considered for rename detection.
  325.      *
  326.      * @param entry
  327.      *            to add.
  328.      * @throws java.lang.IllegalStateException
  329.      *             if {@code getEntries} was already invoked.
  330.      */
  331.     public void add(DiffEntry entry) {
  332.         addAll(Collections.singletonList(entry));
  333.     }

  335.     /**
  336.      * Detect renames in the current file set.
  337.      * <p>
  338.      * This convenience function runs without a progress monitor.
  339.      * </p>
  340.      *
  341.      * @return an unmodifiable list of {@link org.eclipse.jgit.diff.DiffEntry}s
  342.      *         representing all files that have been changed.
  343.      * @throws java.io.IOException
  344.      *             file contents cannot be read from the repository.
  345.      */
  346.     public List<DiffEntry> compute() throws IOException {
  347.         try {
  348.             return compute(NullProgressMonitor.INSTANCE);
  349.         } catch (CanceledException e) {
  350.             // Won't happen with a NullProgressMonitor
  351.             return Collections.emptyList();
  352.         }
  353.     }

  355.     /**
  356.      * Detect renames in the current file set.
  357.      *
  358.      * @param pm
  359.      *            report progress during the detection phases.
  360.      * @return an unmodifiable list of {@link org.eclipse.jgit.diff.DiffEntry}s
  361.      *         representing all files that have been changed.
  362.      * @throws java.io.IOException
  363.      *             file contents cannot be read from the repository.
  364.      * @throws CanceledException
  365.      *             if rename detection was cancelled
  366.      */
  367.     public List<DiffEntry> compute(ProgressMonitor pm)
  368.             throws IOException, CanceledException {
  369.         if (!done) {
  370.             try {
  371.                 return compute(objectReader, pm);
  372.             } finally {
  373.                 objectReader.close();
  374.             }
  375.         }
  376.         return Collections.unmodifiableList(entries);
  377.     }

  379.     /**
  380.      * Detect renames in the current file set.
  381.      *
  382.      * @param reader
  383.      *            reader to obtain objects from the repository with.
  384.      * @param pm
  385.      *            report progress during the detection phases.
  386.      * @return an unmodifiable list of {@link org.eclipse.jgit.diff.DiffEntry}s
  387.      *         representing all files that have been changed.
  388.      * @throws java.io.IOException
  389.      *             file contents cannot be read from the repository.
  390.      * @throws CanceledException
  391.      *             if rename detection was cancelled
  392.      */
  393.     public List<DiffEntry> compute(ObjectReader reader, ProgressMonitor pm)
  394.             throws IOException, CanceledException {
  395.         final ContentSource cs = ContentSource.create(reader);
  396.         return compute(new ContentSource.Pair(cs, cs), pm);
  397.     }

  399.     /**
  400.      * Detect renames in the current file set.
  401.      *
  402.      * @param reader
  403.      *            reader to obtain objects from the repository with.
  404.      * @param pm
  405.      *            report progress during the detection phases.
  406.      * @return an unmodifiable list of {@link org.eclipse.jgit.diff.DiffEntry}s
  407.      *         representing all files that have been changed.
  408.      * @throws java.io.IOException
  409.      *             file contents cannot be read from the repository.
  410.      * @throws CanceledException
  411.      *             if rename detection was cancelled
  412.      */
  413.     public List<DiffEntry> compute(ContentSource.Pair reader, ProgressMonitor pm)
  414.             throws IOException, CanceledException {
  415.         if (!done) {
  416.             done = true;

  418.             if (pm == null)
  419.                 pm = NullProgressMonitor.INSTANCE;

  421.             if (0 < breakScore)
  422.                 breakModifies(reader, pm);

  424.             if (!added.isEmpty() && !deleted.isEmpty())
  425.                 findExactRenames(pm);

  427.             if (!added.isEmpty() && !deleted.isEmpty())
  428.                 findContentRenames(reader, pm);

  430.             if (0 < breakScore && !added.isEmpty() && !deleted.isEmpty())
  431.                 rejoinModifies(pm);

  433.             entries.addAll(added);
  434.             added = null;

  436.             entries.addAll(deleted);
  437.             deleted = null;

  439.             Collections.sort(entries, DIFF_COMPARATOR);
  440.         }
  441.         return Collections.unmodifiableList(entries);
  442.     }

  444.     /**
  445.      * Reset this rename detector for another rename detection pass.
  446.      */
  447.     public void reset() {
  448.         entries = new ArrayList<>();
  449.         deleted = new ArrayList<>();
  450.         added = new ArrayList<>();
  451.         done = false;
  452.     }

  454.     private void advanceOrCancel(ProgressMonitor pm) throws CanceledException {
  455.         if (pm.isCancelled()) {
  456.             throw new CanceledException(JGitText.get().renameCancelled);
  457.         }
  458.         pm.update(1);
  459.     }

  461.     private void breakModifies(ContentSource.Pair reader, ProgressMonitor pm)
  462.             throws IOException, CanceledException {
  463.         ArrayList<DiffEntry> newEntries = new ArrayList<>(entries.size());

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

  467.         for (int i = 0; i < entries.size(); i++) {
  468.             DiffEntry e = entries.get(i);
  469.             if (e.getChangeType() == ChangeType.MODIFY) {
  470.                 int score = calculateModifyScore(reader, e);
  471.                 if (score < breakScore) {
  472.                     List<DiffEntry> tmp = DiffEntry.breakModify(e);
  473.                     DiffEntry del = tmp.get(0);
  474.                     del.score = score;
  475.                     deleted.add(del);
  476.                     added.add(tmp.get(1));
  477.                 } else {
  478.                     newEntries.add(e);
  479.                 }
  480.             } else {
  481.                 newEntries.add(e);
  482.             }
  483.             advanceOrCancel(pm);
  484.         }

  486.         entries = newEntries;
  487.     }

  489.     private void rejoinModifies(ProgressMonitor pm) throws CanceledException {
  490.         HashMap<String, DiffEntry> nameMap = new HashMap<>();
  491.         ArrayList<DiffEntry> newAdded = new ArrayList<>(added.size());

  493.         pm.beginTask(JGitText.get().renamesRejoiningModifies, added.size()
  494.                 + deleted.size());

  496.         for (DiffEntry src : deleted) {
  497.             nameMap.put(src.oldPath, src);
  498.             advanceOrCancel(pm);
  499.         }

  501.         for (DiffEntry dst : added) {
  502.             DiffEntry src = nameMap.remove(dst.newPath);
  503.             if (src != null) {
  504.                 if (sameType(src.oldMode, dst.newMode)) {
  505.                     entries.add(DiffEntry.pair(ChangeType.MODIFY, src, dst,
  506.                             src.score));
  507.                 } else {
  508.                     nameMap.put(src.oldPath, src);
  509.                     newAdded.add(dst);
  510.                 }
  511.             } else {
  512.                 newAdded.add(dst);
  513.             }
  514.             advanceOrCancel(pm);
  515.         }

  517.         added = newAdded;
  518.         deleted = new ArrayList<>(nameMap.values());
  519.     }

  521.     private int calculateModifyScore(ContentSource.Pair reader, DiffEntry d)
  522.             throws IOException {
  523.         try {
  524.             SimilarityIndex src = new SimilarityIndex();
  525.             src.hash(reader.open(OLD, d));
  526.             src.sort();

  528.             SimilarityIndex dst = new SimilarityIndex();
  529.             dst.hash(reader.open(NEW, d));
  530.             dst.sort();
  531.             return src.score(dst, 100);
  532.         } catch (TableFullException tableFull) {
  533.             // If either table overflowed while being constructed, don't allow
  534.             // the pair to be broken. Returning 1 higher than breakScore will
  535.             // ensure its not similar, but not quite dissimilar enough to break.
  536.             //
  537.             overRenameLimit = true;
  538.             return breakScore + 1;
  539.         }
  540.     }

  542.     private void findContentRenames(ContentSource.Pair reader,
  543.             ProgressMonitor pm)
  544.             throws IOException, CanceledException {
  545.         int cnt = Math.max(added.size(), deleted.size());
  546.         if (getRenameLimit() == 0 || cnt <= getRenameLimit()) {
  547.             SimilarityRenameDetector d;

  549.             d = new SimilarityRenameDetector(reader, deleted, added);
  550.             d.setRenameScore(getRenameScore());
  551.             d.setBigFileThreshold(getBigFileThreshold());
  552.             d.setSkipBinaryFiles(getSkipContentRenamesForBinaryFiles());
  553.             d.compute(pm);
  554.             overRenameLimit |= d.isTableOverflow();
  555.             deleted = d.getLeftOverSources();
  556.             added = d.getLeftOverDestinations();
  557.             entries.addAll(d.getMatches());
  558.         } else {
  559.             overRenameLimit = true;
  560.         }
  561.     }

  563.     @SuppressWarnings("unchecked")
  564.     private void findExactRenames(ProgressMonitor pm)
  565.             throws CanceledException {
  566.         pm.beginTask(JGitText.get().renamesFindingExact, //
  567.                 added.size() + added.size() + deleted.size()
  568.                         + added.size() * deleted.size());

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

  573.         ArrayList<DiffEntry> uniqueAdds = new ArrayList<>(added.size());
  574.         ArrayList<List<DiffEntry>> nonUniqueAdds = new ArrayList<>();

  576.         for (Object o : addedMap.values()) {
  577.             if (o instanceof DiffEntry)
  578.                 uniqueAdds.add((DiffEntry) o);
  579.             else
  580.                 nonUniqueAdds.add((List<DiffEntry>) o);
  581.         }

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

  585.         for (DiffEntry a : uniqueAdds) {
  586.             Object del = deletedMap.get(a.newId);
  587.             if (del instanceof DiffEntry) {
  588.                 // We have one add to one delete: pair them if they are the same
  589.                 // type
  590.                 DiffEntry e = (DiffEntry) del;
  591.                 if (sameType(e.oldMode, a.newMode)) {
  592.                     e.changeType = ChangeType.RENAME;
  593.                     entries.add(exactRename(e, a));
  594.                 } else {
  595.                     left.add(a);
  596.                 }
  597.             } else if (del != null) {
  598.                 // We have one add to many deletes: find the delete with the
  599.                 // same type and closest name to the add, then pair them
  600.                 List<DiffEntry> list = (List<DiffEntry>) del;
  601.                 DiffEntry best = bestPathMatch(a, list);
  602.                 if (best != null) {
  603.                     best.changeType = ChangeType.RENAME;
  604.                     entries.add(exactRename(best, a));
  605.                 } else {
  606.                     left.add(a);
  607.                 }
  608.             } else {
  609.                 left.add(a);
  610.             }
  611.             advanceOrCancel(pm);
  612.         }

  614.         for (List<DiffEntry> adds : nonUniqueAdds) {
  615.             Object o = deletedMap.get(adds.get(0).newId);
  616.             if (o instanceof DiffEntry) {
  617.                 // We have many adds to one delete: find the add with the same
  618.                 // type and closest name to the delete, then pair them. Mark the
  619.                 // rest as copies of the delete.
  620.                 DiffEntry d = (DiffEntry) o;
  621.                 DiffEntry best = bestPathMatch(d, adds);
  622.                 if (best != null) {
  623.                     d.changeType = ChangeType.RENAME;
  624.                     entries.add(exactRename(d, best));
  625.                     for (DiffEntry a : adds) {
  626.                         if (a != best) {
  627.                             if (sameType(d.oldMode, a.newMode)) {
  628.                                 entries.add(exactCopy(d, a));
  629.                             } else {
  630.                                 left.add(a);
  631.                             }
  632.                         }
  633.                     }
  634.                 } else {
  635.                     left.addAll(adds);
  636.                 }
  637.             } else if (o != null) {
  638.                 // We have many adds to many deletes: score all the adds against
  639.                 // all the deletes by path name, take the best matches, pair
  640.                 // them as renames, then call the rest copies
  641.                 List<DiffEntry> dels = (List<DiffEntry>) o;
  642.                 long[] matrix = new long[dels.size() * adds.size()];
  643.                 int mNext = 0;
  644.                 for (int delIdx = 0; delIdx < dels.size(); delIdx++) {
  645.                     String deletedName = dels.get(delIdx).oldPath;

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

  650.                         int score = SimilarityRenameDetector.nameScore(addedName, deletedName);
  651.                         matrix[mNext] = SimilarityRenameDetector.encode(score, delIdx, addIdx);
  652.                         mNext++;
  653.                         if (pm.isCancelled()) {
  654.                             throw new CanceledException(
  655.                                     JGitText.get().renameCancelled);
  656.                         }
  657.                     }
  658.                 }

  660.                 Arrays.sort(matrix);

  662.                 for (--mNext; mNext >= 0; mNext--) {
  663.                     long ent = matrix[mNext];
  664.                     int delIdx = SimilarityRenameDetector.srcFile(ent);
  665.                     int addIdx = SimilarityRenameDetector.dstFile(ent);
  666.                     DiffEntry d = dels.get(delIdx);
  667.                     DiffEntry a = adds.get(addIdx);

  669.                     if (a == null) {
  670.                         advanceOrCancel(pm);
  671.                         continue; // was already matched earlier
  672.                     }

  674.                     ChangeType type;
  675.                     if (d.changeType == ChangeType.DELETE) {
  676.                         // First use of this source file. Tag it as a rename so we
  677.                         // later know it is already been used as a rename, other
  678.                         // matches (if any) will claim themselves as copies instead.
  679.                         //
  680.                         d.changeType = ChangeType.RENAME;
  681.                         type = ChangeType.RENAME;
  682.                     } else {
  683.                         type = ChangeType.COPY;
  684.                     }

  686.                     entries.add(DiffEntry.pair(type, d, a, 100));
  687.                     adds.set(addIdx, null); // Claim the destination was matched.
  688.                     advanceOrCancel(pm);
  689.                 }
  690.             } else {
  691.                 left.addAll(adds);
  692.             }
  693.             advanceOrCancel(pm);
  694.         }
  695.         added = left;

  697.         deleted = new ArrayList<>(deletedMap.size());
  698.         for (Object o : deletedMap.values()) {
  699.             if (o instanceof DiffEntry) {
  700.                 DiffEntry e = (DiffEntry) o;
  701.                 if (e.changeType == ChangeType.DELETE)
  702.                     deleted.add(e);
  703.             } else {
  704.                 List<DiffEntry> list = (List<DiffEntry>) o;
  705.                 for (DiffEntry e : list) {
  706.                     if (e.changeType == ChangeType.DELETE)
  707.                         deleted.add(e);
  708.                 }
  709.             }
  710.         }
  711.         pm.endTask();
  712.     }

  714.     /**
  715.      * Find the best match by file path for a given DiffEntry from a list of
  716.      * DiffEntrys. The returned DiffEntry will be of the same type as <src>. If
  717.      * no DiffEntry can be found that has the same type, this method will return
  718.      * null.
  719.      *
  720.      * @param src
  721.      *            the DiffEntry to try to find a match for
  722.      * @param list
  723.      *            a list of DiffEntrys to search through
  724.      * @return the DiffEntry from <list> who's file path best matches <src>
  725.      */
  726.     private static DiffEntry bestPathMatch(DiffEntry src, List<DiffEntry> list) {
  727.         DiffEntry best = null;
  728.         int score = -1;

  730.         for (DiffEntry d : list) {
  731.             if (sameType(mode(d), mode(src))) {
  732.                 int tmp = SimilarityRenameDetector
  733.                         .nameScore(path(d), path(src));
  734.                 if (tmp > score) {
  735.                     best = d;
  736.                     score = tmp;
  737.                 }
  738.             }
  739.         }

  741.         return best;
  742.     }

  744.     @SuppressWarnings("unchecked")
  745.     private HashMap<AbbreviatedObjectId, Object> populateMap(
  746.             List<DiffEntry> diffEntries, ProgressMonitor pm)
  747.             throws CanceledException {
  748.         HashMap<AbbreviatedObjectId, Object> map = new HashMap<>();
  749.         for (DiffEntry de : diffEntries) {
  750.             Object old = map.put(id(de), de);
  751.             if (old instanceof DiffEntry) {
  752.                 ArrayList<DiffEntry> list = new ArrayList<>(2);
  753.                 list.add((DiffEntry) old);
  754.                 list.add(de);
  755.                 map.put(id(de), list);
  756.             } else if (old != null) {
  757.                 // Must be a list of DiffEntries
  758.                 ((List<DiffEntry>) old).add(de);
  759.                 map.put(id(de), old);
  760.             }
  761.             advanceOrCancel(pm);
  762.         }
  763.         return map;
  764.     }

  766.     private static String path(DiffEntry de) {
  767.         return de.changeType == ChangeType.DELETE ? de.oldPath : de.newPath;
  768.     }

  770.     private static FileMode mode(DiffEntry de) {
  771.         return de.changeType == ChangeType.DELETE ? de.oldMode : de.newMode;
  772.     }

  774.     private static AbbreviatedObjectId id(DiffEntry de) {
  775.         return de.changeType == ChangeType.DELETE ? de.oldId : de.newId;
  776.     }

  778.     static boolean sameType(FileMode a, FileMode b) {
  779.         // Files have to be of the same type in order to rename them.
  780.         // We would never want to rename a file to a gitlink, or a
  781.         // symlink to a file.
  782.         //
  783.         int aType = a.getBits() & FileMode.TYPE_MASK;
  784.         int bType = b.getBits() & FileMode.TYPE_MASK;
  785.         return aType == bType;
  786.     }

  788.     private static DiffEntry exactRename(DiffEntry src, DiffEntry dst) {
  789.         return DiffEntry.pair(ChangeType.RENAME, src, dst, EXACT_RENAME_SCORE);
  790.     }

  792.     private static DiffEntry exactCopy(DiffEntry src, DiffEntry dst) {
  793.         return DiffEntry.pair(ChangeType.COPY, src, dst, EXACT_RENAME_SCORE);
  794.     }
  795. }
Created with JaCoCo 0.8.7.202105040129