Candidate.java
/*
* Copyright (C) 2011, 2019 Google Inc. and others
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Distribution License v. 1.0 which is available at
* https://www.eclipse.org/org/documents/edl-v10.php.
*
* SPDX-License-Identifier: BSD-3-Clause
*/
package org.eclipse.jgit.blame;
import java.io.IOException;
import java.util.List;
import org.eclipse.jgit.blame.ReverseWalk.ReverseCommit;
import org.eclipse.jgit.diff.Edit;
import org.eclipse.jgit.diff.EditList;
import org.eclipse.jgit.diff.RawText;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.ObjectLoader;
import org.eclipse.jgit.lib.ObjectReader;
import org.eclipse.jgit.lib.PersonIdent;
import org.eclipse.jgit.lib.Repository;
import org.eclipse.jgit.revwalk.RevCommit;
import org.eclipse.jgit.revwalk.RevFlag;
import org.eclipse.jgit.revwalk.RevWalk;
import org.eclipse.jgit.treewalk.filter.PathFilter;
import org.eclipse.jgit.util.LfsFactory;
/**
* A source that may have supplied some (or all) of the result file.
* <p>
* Candidates are kept in a queue by BlameGenerator, allowing the generator to
* perform a parallel search down the parents of any merges that are discovered
* during the history traversal. Each candidate retains a {@link #regionList}
* describing sections of the result file the candidate has taken responsibility
* for either directly or indirectly through its history. Actual blame from this
* region list will be assigned to the candidate when its ancestor commit(s) are
* themselves converted into Candidate objects and the ancestor's candidate uses
* {@link #takeBlame(EditList, Candidate)} to accept responsibility for sections
* of the result.
*/
class Candidate {
/** Next candidate in the candidate queue. */
Candidate queueNext;
/** Commit being considered (or blamed, depending on state). */
RevCommit sourceCommit;
/** Path of the candidate file in {@link #sourceCommit}. */
PathFilter sourcePath;
/** Unique name of the candidate blob in {@link #sourceCommit}. */
ObjectId sourceBlob;
/** Complete contents of the file in {@link #sourceCommit}. */
RawText sourceText;
/**
* Chain of regions this candidate may be blamed for.
* <p>
* This list is always kept sorted by resultStart order, making it simple to
* merge-join with the sorted EditList during blame assignment.
*/
Region regionList;
/**
* Score assigned to the rename to this candidate.
* <p>
* Consider the history "A<-B<-C". If the result file S in C was
* renamed to R in B, the rename score for this rename will be held in this
* field by the candidate object for B. By storing the score with B, the
* application can see what the rename score was as it makes the transition
* from C/S to B/R. This may seem backwards since it was C that performed
* the rename, but the application doesn't learn about path R until B.
*/
int renameScore;
/** repository used for LFS blob handling */
private Repository sourceRepository;
Candidate(Repository repo, RevCommit commit, PathFilter path) {
sourceRepository = repo;
sourceCommit = commit;
sourcePath = path;
}
void beginResult(RevWalk rw) throws MissingObjectException, IOException {
rw.parseBody(sourceCommit);
}
int getParentCount() {
return sourceCommit.getParentCount();
}
RevCommit getParent(int idx) {
return sourceCommit.getParent(idx);
}
Candidate getNextCandidate(@SuppressWarnings("unused") int idx) {
return null;
}
boolean has(RevFlag flag) {
return sourceCommit.has(flag);
}
void add(RevFlag flag) {
sourceCommit.add(flag);
}
void remove(RevFlag flag) {
sourceCommit.remove(flag);
}
int getTime() {
return sourceCommit.getCommitTime();
}
PersonIdent getAuthor() {
return sourceCommit.getAuthorIdent();
}
Candidate create(Repository repo, RevCommit commit, PathFilter path) {
return new Candidate(repo, commit, path);
}
Candidate copy(RevCommit commit) {
Candidate r = create(sourceRepository, commit, sourcePath);
r.sourceBlob = sourceBlob;
r.sourceText = sourceText;
r.regionList = regionList;
r.renameScore = renameScore;
return r;
}
void loadText(ObjectReader reader) throws IOException {
ObjectLoader ldr = LfsFactory.getInstance().applySmudgeFilter(sourceRepository,
reader.open(sourceBlob, Constants.OBJ_BLOB),
LfsFactory.getAttributesForPath(sourceRepository,
sourcePath.getPath(), sourceCommit)
.get(Constants.ATTR_DIFF));
sourceText = new RawText(ldr.getCachedBytes(Integer.MAX_VALUE));
}
void takeBlame(EditList editList, Candidate child) {
blame(editList, this, child);
}
private static void blame(EditList editList, Candidate a, Candidate b) {
Region r = b.clearRegionList();
Region aTail = null;
Region bTail = null;
for (int eIdx = 0; eIdx < editList.size();) {
// If there are no more regions left, neither side has any
// more responsibility for the result. Remaining edits can
// be safely ignored.
if (r == null)
return;
Edit e = editList.get(eIdx);
// Edit ends before the next candidate region. Skip the edit.
if (e.getEndB() <= r.sourceStart) {
eIdx++;
continue;
}
// Next candidate region starts before the edit. Assign some
// of the blame onto A, but possibly split and also on B.
if (r.sourceStart < e.getBeginB()) {
int d = e.getBeginB() - r.sourceStart;
if (r.length <= d) {
// Pass the blame for this region onto A.
Region next = r.next;
r.sourceStart = e.getBeginA() - d;
aTail = add(aTail, a, r);
r = next;
continue;
}
// Split the region and assign some to A, some to B.
aTail = add(aTail, a, r.splitFirst(e.getBeginA() - d, d));
r.slideAndShrink(d);
}
// At this point e.getBeginB() <= r.sourceStart.
// An empty edit on the B side isn't relevant to this split,
// as it does not overlap any candidate region.
if (e.getLengthB() == 0) {
eIdx++;
continue;
}
// If the region ends before the edit, blame on B.
int rEnd = r.sourceStart + r.length;
if (rEnd <= e.getEndB()) {
Region next = r.next;
bTail = add(bTail, b, r);
r = next;
if (rEnd == e.getEndB())
eIdx++;
continue;
}
// This region extends beyond the edit. Blame the first
// half of the region on B, and process the rest after.
int len = e.getEndB() - r.sourceStart;
bTail = add(bTail, b, r.splitFirst(r.sourceStart, len));
r.slideAndShrink(len);
eIdx++;
}
if (r == null)
return;
// For any remaining region, pass the blame onto A after shifting
// the source start to account for the difference between the two.
Edit e = editList.get(editList.size() - 1);
int endB = e.getEndB();
int d = endB - e.getEndA();
if (aTail == null)
a.regionList = r;
else
aTail.next = r;
do {
if (endB <= r.sourceStart)
r.sourceStart -= d;
r = r.next;
} while (r != null);
}
private static Region add(Region aTail, Candidate a, Region n) {
// If there is no region on the list, use only this one.
if (aTail == null) {
a.regionList = n;
n.next = null;
return n;
}
// If the prior region ends exactly where the new region begins
// in both the result and the source, combine these together into
// one contiguous region. This occurs when intermediate commits
// have inserted and deleted lines in the middle of a region. Try
// to report this region as a single region to the application,
// rather than in fragments.
if (aTail.resultStart + aTail.length == n.resultStart
&& aTail.sourceStart + aTail.length == n.sourceStart) {
aTail.length += n.length;
return aTail;
}
// Append the region onto the end of the list.
aTail.next = n;
n.next = null;
return n;
}
private Region clearRegionList() {
Region r = regionList;
regionList = null;
return r;
}
boolean canMergeRegions(Candidate other) {
return sourceCommit == other.sourceCommit
&& sourcePath.getPath().equals(other.sourcePath.getPath());
}
void mergeRegions(Candidate other) {
// regionList is always sorted by resultStart. Merge join two
// linked lists, preserving the ordering. Combine neighboring
// regions to reduce the number of results seen by callers.
Region a = clearRegionList();
Region b = other.clearRegionList();
Region t = null;
while (a != null && b != null) {
if (a.resultStart < b.resultStart) {
Region n = a.next;
t = add(t, this, a);
a = n;
} else {
Region n = b.next;
t = add(t, this, b);
b = n;
}
}
if (a != null) {
Region n = a.next;
t = add(t, this, a);
t.next = n;
} else /* b != null */{
Region n = b.next;
t = add(t, this, b);
t.next = n;
}
}
/** {@inheritDoc} */
@SuppressWarnings("nls")
@Override
public String toString() {
StringBuilder r = new StringBuilder();
r.append("Candidate[");
r.append(sourcePath.getPath());
if (sourceCommit != null)
r.append(" @ ").append(sourceCommit.abbreviate(6).name());
if (regionList != null)
r.append(" regions:").append(regionList);
r.append("]");
return r.toString();
}
/**
* Special candidate type used for reverse blame.
* <p>
* Reverse blame inverts the commit history graph to follow from a commit to
* its descendant children, rather than the normal history direction of
* child to parent. These types require a {@link ReverseCommit} which keeps
* children pointers, allowing reverse navigation of history.
*/
static final class ReverseCandidate extends Candidate {
ReverseCandidate(Repository repo, ReverseCommit commit,
PathFilter path) {
super(repo, commit, path);
}
@Override
int getParentCount() {
return ((ReverseCommit) sourceCommit).getChildCount();
}
@Override
RevCommit getParent(int idx) {
return ((ReverseCommit) sourceCommit).getChild(idx);
}
@Override
int getTime() {
// Invert the timestamp so newer dates sort older.
return -sourceCommit.getCommitTime();
}
@Override
Candidate create(Repository repo, RevCommit commit, PathFilter path) {
return new ReverseCandidate(repo, (ReverseCommit) commit, path);
}
@Override
public String toString() {
return "Reverse" + super.toString(); //$NON-NLS-1$
}
}
/**
* A {@link Candidate} to blame a working tree file in conflict state.
* <p>
* Contrary to {@link BlobCandidate}, it expects to be given the parent
* commits (typically HEAD and the MERGE_HEADs) and behaves like a merge
* commit during blame. It does <em>not</em> consider a previously pushed
* Candidate as its parent.
* </p>
*/
static final class HeadCandidate extends Candidate {
private List<RevCommit> parents;
HeadCandidate(Repository repo, PathFilter path,
List<RevCommit> parents) {
super(repo, null, path);
this.parents = parents;
}
@Override
void beginResult(RevWalk rw) {
// Blob candidates have nothing to prepare.
}
@Override
int getParentCount() {
return parents.size();
}
@Override
RevCommit getParent(int idx) {
return parents.get(idx);
}
@Override
boolean has(RevFlag flag) {
return true; // Pretend flag was added; sourceCommit is null.
}
@Override
void add(RevFlag flag) {
// Do nothing, sourceCommit is null.
}
@Override
void remove(RevFlag flag) {
// Do nothing, sourceCommit is null.
}
@Override
int getTime() {
return Integer.MAX_VALUE;
}
@Override
PersonIdent getAuthor() {
return new PersonIdent(JGitText.get().blameNotCommittedYet, ""); //$NON-NLS-1$
}
}
/**
* Candidate loaded from a file source, and not a commit.
* <p>
* The {@link Candidate#sourceCommit} field is always null on this type of
* candidate. Instead history traversal follows the single {@link #parent}
* field to discover the next Candidate. Often this is a normal Candidate
* type that has a valid sourceCommit.
*/
static final class BlobCandidate extends Candidate {
/**
* Next candidate to pass blame onto.
* <p>
* When computing the differences that this candidate introduced to the
* file content, the parent's sourceText is used as the base.
*/
Candidate parent;
/** Author name to refer to this blob with. */
String description;
BlobCandidate(Repository repo, String name, PathFilter path) {
super(repo, null, path);
description = name;
}
@Override
void beginResult(RevWalk rw) {
// Blob candidates have nothing to prepare.
}
@Override
int getParentCount() {
return parent != null ? 1 : 0;
}
@Override
RevCommit getParent(int idx) {
return null;
}
@Override
Candidate getNextCandidate(int idx) {
return parent;
}
@Override
boolean has(RevFlag flag) {
return true; // Pretend flag was added; sourceCommit is null.
}
@Override
void add(RevFlag flag) {
// Do nothing, sourceCommit is null.
}
@Override
void remove(RevFlag flag) {
// Do nothing, sourceCommit is null.
}
@Override
int getTime() {
return Integer.MAX_VALUE;
}
@Override
PersonIdent getAuthor() {
return new PersonIdent(description, ""); //$NON-NLS-1$
}
}
}