/*
    * Copyright (C) 2020, Google LLC 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.internal.revwalk;
  
  import java.io.IOException;
  import java.io.InvalidObjectException;
  import java.util.Collection;
  import java.util.Iterator;
  import java.util.Optional;
  import java.util.stream.Stream;
  
  import org.eclipse.jgit.errors.MissingObjectException;
  import org.eclipse.jgit.revwalk.ObjectReachabilityChecker;
  import org.eclipse.jgit.revwalk.ObjectWalk;
  import org.eclipse.jgit.revwalk.RevCommit;
  import org.eclipse.jgit.revwalk.RevObject;
  import org.eclipse.jgit.revwalk.RevSort;
  
  /**
   * Checks if all objects are reachable from certain starting points doing a
   * walk.
   */
  public class PedestrianObjectReachabilityChecker
  		implements ObjectReachabilityChecker {
  	private final ObjectWalk walk;
  
  	/**
  	 * New instance of the reachability checker using a existing walk.
  	 *
  	 * @param walk
  	 *            ObjectWalk instance to reuse. Caller retains ownership.
  	 */
  	public PedestrianObjectReachabilityChecker(ObjectWalk walk) {
  		this.walk = walk;
  	}
  
  	/**
  	 * {@inheritDoc}
  	 */
  	@Override
  	public Optional<RevObject> areAllReachable(Collection<RevObject> targets,
  			Stream<RevObject> starters) throws IOException {
  		try {
  			walk.reset();
  			walk.sort(RevSort.TOPO);
  			for (RevObject target : targets) {
  				walk.markStart(target);
  			}
  
  			Iterator<RevObject> iterator = starters.iterator();
  			while (iterator.hasNext()) {
  				RevObject o = iterator.next();
  				walk.markUninteresting(o);
  
  				RevObject peeled = walk.peel(o);
  				if (peeled instanceof RevCommit) {
  					// By default, for performance reasons, ObjectWalk does not
  					// mark
  					// a tree as uninteresting when we mark a commit. Mark it
  					// ourselves so that we can determine reachability exactly.
  					walk.markUninteresting(((RevCommit) peeled).getTree());
  				}
  			}
  
  			RevCommit commit = walk.next();
  			if (commit != null) {
  				return Optional.of(commit);
  			}
  
  			RevObject object = walk.nextObject();
  			if (object != null) {
  				return Optional.of(object);
  			}
  
  			return Optional.empty();
  		} catch (MissingObjectException | InvalidObjectException e) {
  			throw new IllegalStateException(e);
  		}
  	}
  }