/*
 * Copyright (C) 2011, Google Inc.
 * and other copyright owners as documented in the project's IP log.
 *
 * This program and the accompanying materials are made available
 * under the terms of the Eclipse Distribution License v1.0 which
 * accompanies this distribution, is reproduced below, and is
 * available at http://www.eclipse.org/org/documents/edl-v10.php
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following
 * conditions are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * - Redistributions in binary form must reproduce the above
 *   copyright notice, this list of conditions and the following
 *   disclaimer in the documentation and/or other materials provided
 *   with the distribution.
 *
 * - Neither the name of the Eclipse Foundation, Inc. nor the
 *   names of its contributors may be used to endorse or promote
 *   products derived from this software without specific prior
 *   written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package org.eclipse.jgit.blame;

import java.io.IOException;

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.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.
 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 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 takeBlame(EditList, Candidate) to accept responsibility for sections of the result. /**
 * 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. /** Next candidate in the candidate queue. */
	Candidate queueNext;

	
Commit being considered (or blamed, depending on state). /** Commit being considered (or blamed, depending on state). */
	RevCommit sourceCommit;

	
Path of the candidate file in sourceCommit. /** Path of the candidate file in {@link #sourceCommit}. */
	PathFilter sourcePath;

	
Unique name of the candidate blob in sourceCommit. /** Unique name of the candidate blob in {@link #sourceCommit}. */
	ObjectId sourceBlob;

	
Complete contents of the file in sourceCommit. /** Complete contents of the file in {@link #sourceCommit}. */
	RawText sourceText;

	
Chain of regions this candidate may be blamed for.

This list is always kept sorted by resultStart order, making it simple to
merge-join with the sorted EditList during blame assignment.
/**
	 * 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.

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.
/**
	 * 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 /** 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} /** {@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.
 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 ReverseCommit which keeps children pointers, allowing reverse navigation of history. /**
	 * 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$
		}
	}

	
Candidate loaded from a file source, and not a commit.
 The Candidate.sourceCommit field is always null on this type of candidate. Instead history traversal follows the single parent field to discover the next Candidate. Often this is a normal Candidate type that has a valid sourceCommit. /**
	 * 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.

When computing the differences that this candidate introduced to the
file content, the parent's sourceText is used as the base.
/**
		 * 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. /** 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$
		}
	}
}