/*
    * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> 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.revwalk;
  
  import java.io.IOException;
  
  import org.eclipse.jgit.errors.IncorrectObjectTypeException;
  import org.eclipse.jgit.errors.MissingObjectException;
  
  /**
   * Replaces a RevCommit's parents until not colored with REWRITE.
   * <p>
   * Before a RevCommit is returned to the caller its parents are updated to
   * create a dense DAG. Instead of reporting the actual parents as recorded when
   * the commit was created the returned commit will reflect the next closest
   * commit that matched the revision walker's filters.
   * <p>
   * This generator is the second phase of a path limited revision walk and
   * assumes it is receiving RevCommits from {@link TreeRevFilter}.
   *
   * @see TreeRevFilter
   */
  class RewriteGenerator extends Generator {
  	private static final int REWRITE = RevWalk.REWRITE;
  
  	/** For {@link #cleanup(RevCommit[])} to remove duplicate parents. */
  	private static final int DUPLICATE = RevWalk.TEMP_MARK;
  
  	private final Generator source;
  
  	private final FIFORevQueue pending;
  
  	RewriteGenerator(Generator s) {
  		super(s.firstParent);
  		source = s;
  		pending = new FIFORevQueue(s.firstParent);
  	}
  
  	@Override
  	void shareFreeList(BlockRevQueue q) {
  		source.shareFreeList(q);
  	}
  
  	@Override
  	int outputType() {
  		return source.outputType() & ~NEEDS_REWRITE;
  	}
  
  	@SuppressWarnings("ReferenceEquality")
  	@Override
  	RevCommit next() throws MissingObjectException,
  			IncorrectObjectTypeException, IOException {
  		RevCommit c = pending.next();
  
  		if (c == null) {
  			c = source.next();
  			if (c == null) {
  				// We are done: Both the source generator and our internal list
  				// are completely exhausted.
  				return null;
  			}
  		}
  
  		applyFilterToParents(c);
  
  		boolean rewrote = false;
  		final RevCommit[] pList = c.getParents();
  		final int nParents = pList.length;
  		for (int i = 0; i < nParents; i++) {
  			final RevCommit oldp = pList[i];
  			final RevCommit newp = rewrite(oldp);
  			if (firstParent) {
  				if (newp == null) {
  					c.parents = RevCommit.NO_PARENTS;
  				} else {
  					c.parents = new RevCommit[] { newp };
  				}
  				return c;
  			}
  			if (oldp != newp) {
  				pList[i] = newp;
  				rewrote = true;
  			}
  		}
  		if (rewrote) {
  			c.parents = cleanup(pList);
  		}
  		return c;
  	}
  
  	/**
 	 * Makes sure that the {@link TreeRevFilter} has been applied to all parents
 	 * of this commit by the previous {@link PendingGenerator}.
 	 *
 	 * @param c
 	 * @throws MissingObjectException
 	 * @throws IncorrectObjectTypeException
 	 * @throws IOException
 	 */
 	private void applyFilterToParents(RevCommit c)
 			throws MissingObjectException, IncorrectObjectTypeException,
 			IOException {
 		for (RevCommit parent : c.getParents()) {
 			while ((parent.flags & RevWalk.TREE_REV_FILTER_APPLIED) == 0) {
 
 				RevCommit n = source.next();
 
 				if (n != null) {
 					pending.add(n);
 				} else {
 					// Source generator is exhausted; filter has been applied to
 					// all commits
 					return;
 				}
 
 			}
 
 		}
 	}
 
 	private RevCommit rewrite(RevCommit p) throws MissingObjectException,
 			IncorrectObjectTypeException, IOException {
 		for (;;) {
 
 			if (p.getParentCount() > 1) {
 				// This parent is a merge, so keep it.
 				//
 				return p;
 			}
 
 			if ((p.flags & RevWalk.UNINTERESTING) != 0) {
 				// Retain uninteresting parents. They show where the
 				// DAG was cut off because it wasn't interesting.
 				//
 				return p;
 			}
 
 			if ((p.flags & REWRITE) == 0) {
 				// This parent was not eligible for rewriting. We
 				// need to keep it in the DAG.
 				//
 				return p;
 			}
 
 			if (p.getParentCount() == 0) {
 				// We can't go back any further, other than to
 				// just delete the parent entirely.
 				//
 				return null;
 			}
 
 			applyFilterToParents(p.getParent(0));
 			p = p.getParent(0);
 
 		}
 	}
 
 	private RevCommit[] cleanup(RevCommit[] oldList) {
 		// Remove any duplicate parents caused due to rewrites (e.g. a merge
 		// with two sides that both simplified back into the merge base).
 		// We also may have deleted a parent by marking it null.
 		//
 		int newCnt = 0;
 		for (int o = 0; o < oldList.length; o++) {
 			final RevCommit p = oldList[o];
 			if (p == null)
 				continue;
 			if ((p.flags & DUPLICATE) != 0) {
 				oldList[o] = null;
 				continue;
 			}
 			p.flags |= DUPLICATE;
 			newCnt++;
 		}
 
 		if (newCnt == oldList.length) {
 			for (RevCommit p : oldList)
 				p.flags &= ~DUPLICATE;
 			return oldList;
 		}
 
 		final RevCommit[] newList = new RevCommit[newCnt];
 		newCnt = 0;
 		for (RevCommit p : oldList) {
 			if (p != null) {
 				newList[newCnt++] = p;
 				p.flags &= ~DUPLICATE;
 			}
 		}
 
 		return newList;
 	}
 }