private void findExactRenames()

in org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java [564:712]
121 lines of code
26 McCabe index (conditional complexity)

	private void findExactRenames(ProgressMonitor pm)
			throws CanceledException {
		pm.beginTask(JGitText.get().renamesFindingExact, //
				added.size() + added.size() + deleted.size()
						+ added.size() * deleted.size());

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

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

		for (Object o : addedMap.values()) {
			if (o instanceof DiffEntry)
				uniqueAdds.add((DiffEntry) o);
			else
				nonUniqueAdds.add((List<DiffEntry>) o);
		}

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

		for (DiffEntry a : uniqueAdds) {
			Object del = deletedMap.get(a.newId);
			if (del instanceof DiffEntry) {
				// We have one add to one delete: pair them if they are the same
				// type
				DiffEntry e = (DiffEntry) del;
				if (sameType(e.oldMode, a.newMode)) {
					e.changeType = ChangeType.RENAME;
					entries.add(exactRename(e, a));
				} else {
					left.add(a);
				}
			} else if (del != null) {
				// We have one add to many deletes: find the delete with the
				// same type and closest name to the add, then pair them
				List<DiffEntry> list = (List<DiffEntry>) del;
				DiffEntry best = bestPathMatch(a, list);
				if (best != null) {
					best.changeType = ChangeType.RENAME;
					entries.add(exactRename(best, a));
				} else {
					left.add(a);
				}
			} else {
				left.add(a);
			}
			advanceOrCancel(pm);
		}

		for (List<DiffEntry> adds : nonUniqueAdds) {
			Object o = deletedMap.get(adds.get(0).newId);
			if (o instanceof DiffEntry) {
				// We have many adds to one delete: find the add with the same
				// type and closest name to the delete, then pair them. Mark the
				// rest as copies of the delete.
				DiffEntry d = (DiffEntry) o;
				DiffEntry best = bestPathMatch(d, adds);
				if (best != null) {
					d.changeType = ChangeType.RENAME;
					entries.add(exactRename(d, best));
					for (DiffEntry a : adds) {
						if (a != best) {
							if (sameType(d.oldMode, a.newMode)) {
								entries.add(exactCopy(d, a));
							} else {
								left.add(a);
							}
						}
					}
				} else {
					left.addAll(adds);
				}
			} else if (o != null) {
				// We have many adds to many deletes: score all the adds against
				// all the deletes by path name, take the best matches, pair
				// them as renames, then call the rest copies
				List<DiffEntry> dels = (List<DiffEntry>) o;
				long[] matrix = new long[dels.size() * adds.size()];
				int mNext = 0;
				for (int delIdx = 0; delIdx < dels.size(); delIdx++) {
					String deletedName = dels.get(delIdx).oldPath;

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

						int score = SimilarityRenameDetector.nameScore(addedName, deletedName);
						matrix[mNext] = SimilarityRenameDetector.encode(score, delIdx, addIdx);
						mNext++;
						if (pm.isCancelled()) {
							throw new CanceledException(
									JGitText.get().renameCancelled);
						}
					}
				}

				Arrays.sort(matrix);

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

					if (a == null) {
						advanceOrCancel(pm);
						continue; // was already matched earlier
					}

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

					entries.add(DiffEntry.pair(type, d, a, 100));
					adds.set(addIdx, null); // Claim the destination was matched.
					advanceOrCancel(pm);
				}
			} else {
				left.addAll(adds);
			}
			advanceOrCancel(pm);
		}
		added = left;

		deleted = new ArrayList<>(deletedMap.size());
		for (Object o : deletedMap.values()) {
			if (o instanceof DiffEntry) {
				DiffEntry e = (DiffEntry) o;
				if (e.changeType == ChangeType.DELETE)
					deleted.add(e);
			} else {
				List<DiffEntry> list = (List<DiffEntry>) o;
				for (DiffEntry e : list) {
					if (e.changeType == ChangeType.DELETE)
						deleted.add(e);
				}
			}
		}
		pm.endTask();
	}