/*
    * 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.revwalk.RevCommit;
  import org.eclipse.jgit.revwalk.RevFlag;
  import org.eclipse.jgit.revwalk.RevWalk;
  import org.eclipse.jgit.treewalk.filter.PathFilter;
  
  /**
   * 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;
 
 	Candidate(RevCommit commit, PathFilter path) {
 		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(RevCommit commit, PathFilter path) {
 		return new Candidate(commit, path);
 	}
 
 	Candidate copy(RevCommit commit) {
 		Candidate r = create(commit, sourcePath);
 		r.sourceBlob = sourceBlob;
 		r.sourceText = sourceText;
 		r.regionList = regionList;
 		r.renameScore = renameScore;
 		return r;
 	}
 
 	void loadText(ObjectReader reader) throws IOException {
 		ObjectLoader ldr = reader.open(sourceBlob, Constants.OBJ_BLOB);
 		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;
 		}
 	}
 
 	@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(ReverseCommit commit, PathFilter path) {
 			super(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(RevCommit commit, PathFilter path) {
 			return new ReverseCandidate((ReverseCommit) commit, path);
 		}
 
 		@Override
 		public String toString() {
 			return "Reverse" + super.toString(); //$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(String name, PathFilter path) {
 			super(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$
 		}
 	}
 }