/*
 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
 * 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.revwalk;

import java.io.IOException;
import java.text.MessageFormat;
import java.util.LinkedList;

import org.eclipse.jgit.errors.IncorrectObjectTypeException;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.internal.JGitText;

Computes the merge base(s) of the starting commits.
 This generator is selected if the RevFilter is only RevFilter.MERGE_BASE. 

To compute the merge base we assign a temporary flag to each of the starting
commits. The maximum number of starting commits is bounded by the number of
free flags available in the RevWalk when the generator is initialized. These
flags will be automatically released on the next reset of the RevWalk, but
not until then, as they are assigned to commits throughout the history.

Several internal flags are reused here for a different purpose, but this
should not have any impact as this generator should be run alone, and without
any other generators wrapped around it.
/**
 * Computes the merge base(s) of the starting commits.
 * <p>
 * This generator is selected if the RevFilter is only
 * {@link org.eclipse.jgit.revwalk.filter.RevFilter#MERGE_BASE}.
 * <p>
 * To compute the merge base we assign a temporary flag to each of the starting
 * commits. The maximum number of starting commits is bounded by the number of
 * free flags available in the RevWalk when the generator is initialized. These
 * flags will be automatically released on the next reset of the RevWalk, but
 * not until then, as they are assigned to commits throughout the history.
 * <p>
 * Several internal flags are reused here for a different purpose, but this
 * should not have any impact as this generator should be run alone, and without
 * any other generators wrapped around it.
 */
class MergeBaseGenerator extends Generator {
	private static final int PARSED = RevWalk.PARSED;
	private static final int IN_PENDING = RevWalk.SEEN;
	private static final int POPPED = RevWalk.TEMP_MARK;
	private static final int MERGE_BASE = RevWalk.REWRITE;

	private final RevWalk walker;
	private final DateRevQueue pending;

	private int branchMask;
	private int recarryTest;
	private int recarryMask;
	private int mergeBaseAncestor = -1;
	private LinkedList<RevCommit> ret = new LinkedList<>();

	private CarryStack stack;

	MergeBaseGenerator(RevWalk w) {
		super(w.isFirstParent());
		walker = w;
		pending = new DateRevQueue(firstParent);
	}

	void init(AbstractRevQueue p) throws IOException {
		try {
			for (;;) {
				final RevCommit c = p.next();
				if (c == null)
					break;
				add(c);
			}
			// Setup the condition used by carryOntoOne to detect a late
			// merge base and produce it on the next round.
			//
			recarryTest = branchMask | POPPED;
			recarryMask = branchMask | POPPED | MERGE_BASE;
			mergeBaseAncestor = walker.allocFlag();

			for (;;) {
				RevCommit c = _next();
				if (c == null) {
					break;
				}
				ret.add(c);
			}
		} finally {
			// Always free the flags immediately. This ensures the flags
			// will be available for reuse when the walk resets.
			//
			walker.freeFlag(branchMask | mergeBaseAncestor);
		}
	}

	private void add(RevCommit c) {
		final int flag = walker.allocFlag();
		branchMask |= flag;
		if ((c.flags & branchMask) != 0) {
			// This should never happen. RevWalk ensures we get a
			// commit admitted to the initial queue only once. If
			// we see this marks aren't correctly erased.
			//
			throw new IllegalStateException(MessageFormat.format(JGitText.get().staleRevFlagsOn, c.name()));
		}
		c.flags |= flag;
		pending.add(c);
	}

	@Override
	int outputType() {
		return 0;
	}

	private RevCommit _next() throws MissingObjectException,
			IncorrectObjectTypeException, IOException {
		for (;;) {
			final RevCommit c = pending.next();
			if (c == null) {
				return null;
			}

			for (RevCommit p : c.parents) {
				if ((p.flags & IN_PENDING) != 0)
					continue;
				if ((p.flags & PARSED) == 0)
					p.parseHeaders(walker);
				p.flags |= IN_PENDING;
				pending.add(p);
			}

			int carry = c.flags & branchMask;
			boolean mb = carry == branchMask;
			if (mb) {
				// If we are a merge base make sure our ancestors are
				// also flagged as being popped, so that they do not
				// generate to the caller.
				//
				carry |= MERGE_BASE | mergeBaseAncestor;
			}
			carryOntoHistory(c, carry);

			if ((c.flags & MERGE_BASE) != 0) {
				// This commit is an ancestor of a merge base we already
				// popped back to the caller. If everyone in pending is
				// that way we are done traversing; if not we just need
				// to move to the next available commit and try again.
				//
				if (pending.everbodyHasFlag(MERGE_BASE))
					return null;
				continue;
			}
			c.flags |= POPPED;

			if (mb) {
				c.flags |= MERGE_BASE;
				return c;
			}
		}
	}

	@Override
	RevCommit next() throws MissingObjectException,
			IncorrectObjectTypeException, IOException {
		while (!ret.isEmpty()) {
			RevCommit commit = ret.remove();
			if ((commit.flags & mergeBaseAncestor) == 0) {
				return commit;
			}
		}
		return null;
	}

	private void carryOntoHistory(RevCommit c, int carry) {
		stack = null;
		for (;;) {
			carryOntoHistoryInnerLoop(c, carry);
			if (stack == null) {
				break;
			}
			c = stack.c;
			carry = stack.carry;
			stack = stack.prev;
		}
	}

	private void carryOntoHistoryInnerLoop(RevCommit c, int carry) {
		for (;;) {
			RevCommit[] parents = c.parents;
			if (parents == null || parents.length == 0) {
				break;
			}

			int e = parents.length - 1;
			for (int i = 0; i < e; i++) {
				RevCommit p = parents[i];
				if (carryOntoOne(p, carry) == CONTINUE) {
					// Walking p will be required, buffer p on stack.
					stack = new CarryStack(stack, p, carry);
				}
				// For other results from carryOntoOne:
				// HAVE_ALL: p has all bits, do nothing to skip that path.
				// CONTINUE_ON_STACK: callee pushed StackElement for p.
			}

			c = parents[e];
			if (carryOntoOne(c, carry) != CONTINUE) {
				break;
			}
		}
	}

	private static final int CONTINUE = 0;
	private static final int HAVE_ALL = 1;
	private static final int CONTINUE_ON_STACK = 2;

	private int carryOntoOne(RevCommit p, int carry) {
		// If we already had all carried flags, our parents do too.
		// Return HAVE_ALL to stop caller from running down this leg
		// of the revision graph any further.
		//
		// Otherwise return CONTINUE to ask the caller to walk history.
		int rc = (p.flags & carry) == carry ? HAVE_ALL : CONTINUE;
		p.flags |= carry;

		if ((p.flags & recarryMask) == recarryTest) {
			// We were popped without being a merge base, but we just got
			// voted to be one. Inject ourselves back at the front of the
			// pending queue and tell all of our ancestors they are within
			// the merge base now.
			p.flags &= ~POPPED;
			pending.add(p);
			stack = new CarryStack(stack, p, branchMask | MERGE_BASE);
			return CONTINUE_ON_STACK;
		}
		return rc;
	}

	private static class CarryStack {
		final CarryStack prev;
		final RevCommit c;
		final int carry;

		CarryStack(CarryStack prev, RevCommit c, int carry) {
			this.prev = prev;
			this.c = c;
			this.carry = carry;
		}
	}
}