/*
    * Copyright (C) 2017, 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.storage.reftable;
  
  import java.io.IOException;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Set;
  import java.util.TreeSet;
  import java.util.concurrent.locks.ReentrantLock;
  import java.util.stream.Collectors;
  
  import org.eclipse.jgit.annotations.Nullable;
  import org.eclipse.jgit.lib.ObjectId;
  import org.eclipse.jgit.lib.Ref;
  import org.eclipse.jgit.lib.RefDatabase;
  import org.eclipse.jgit.lib.ReflogReader;
  import org.eclipse.jgit.transport.ReceiveCommand;
  
  /**
   * Operations on {@link MergedReftable} that is common to various reftable-using
   * subclasses of {@link RefDatabase}. See
   * {@link org.eclipse.jgit.internal.storage.dfs.DfsReftableDatabase} for an
   * example.
   */
  public abstract class ReftableDatabase {
  	// Protects mergedTables.
  	private final ReentrantLock lock = new ReentrantLock(true);
  
  	private Reftable mergedTables;
  
  	/**
  	 * ReftableDatabase lazily initializes its merged reftable on the first read after
  	 * construction or clearCache() call. This function should always instantiate a new
  	 * MergedReftable based on the list of reftables specified by the underlying storage.
  	 *
  	 * @return the ReftableStack for this instance
  	 * @throws IOException
  	 *             on I/O problems.
  	 */
  	protected abstract MergedReftable openMergedReftable() throws IOException;
  
  	/**
  	 * @return the next available logical timestamp for an additional reftable
  	 *         in the stack.
  	 * @throws java.io.IOException
  	 *             on I/O problems.
  	 */
  	public long nextUpdateIndex() throws IOException {
  		lock.lock();
  		try {
  			return reader().maxUpdateIndex() + 1;
  		} finally {
  			lock.unlock();
  		}
  	}
  
  	/**
  	 * @return a ReflogReader for the given ref
  	 * @param refname
  	 *            the name of the ref.
  	 * @throws IOException
  	 *             on I/O problems
  	 */
  	public ReflogReader getReflogReader(String refname) throws IOException {
  		lock.lock();
  		try {
  			return new ReftableReflogReader(lock, reader(), refname);
  		} finally {
  			lock.unlock();
  		}
  	}
  
  	/**
  	 * @return a ReceiveCommand for the change from oldRef to newRef
  	 * @param oldRef
  	 *            a ref
  	 * @param newRef
  	 *            a ref
  	 */
  	public static ReceiveCommand toCommand(Ref oldRef, Ref newRef) {
  		ObjectId oldId = toId(oldRef);
  		ObjectId newId = toId(newRef);
  		String name = oldRef != null ? oldRef.getName() : newRef.getName();
  
  		if (oldRef != null && oldRef.isSymbolic()) {
  			if (newRef != null) {
  				if (newRef.isSymbolic()) {
 					return ReceiveCommand.link(oldRef.getTarget().getName(),
 							newRef.getTarget().getName(), name);
 				}
 				// This should pass in oldId for compat with
 				// RefDirectoryUpdate
 				return ReceiveCommand.unlink(oldRef.getTarget().getName(),
 						newId, name);
 			}
 			return ReceiveCommand.unlink(oldRef.getTarget().getName(),
 					ObjectId.zeroId(), name);
 		}
 
 		if (newRef != null && newRef.isSymbolic()) {
 			if (oldRef != null) {
 				if (oldRef.isSymbolic()) {
 					return ReceiveCommand.link(oldRef.getTarget().getName(),
 							newRef.getTarget().getName(), name);
 				}
 				return ReceiveCommand.link(oldId,
 						newRef.getTarget().getName(), name);
 			}
 			return ReceiveCommand.link(ObjectId.zeroId(),
 					newRef.getTarget().getName(), name);
 		}
 
 		return new ReceiveCommand(oldId, newId, name);
 	}
 
 	private static ObjectId toId(Ref ref) {
 		if (ref != null) {
 			ObjectId id = ref.getObjectId();
 			if (id != null) {
 				return id;
 			}
 		}
 		return ObjectId.zeroId();
 	}
 
 	/**
 	 * @return the lock protecting underlying ReftableReaders against concurrent
 	 *         reads.
 	 */
 	public ReentrantLock getLock() {
 		return lock;
 	}
 
 	/**
 	 * @return the merged reftable that is implemented by the stack of
 	 *         reftables. Return value must be accessed under lock.
 	 * @throws IOException
 	 *             on I/O problems
 	 */
 	private Reftable reader() throws IOException {
 		if (!lock.isLocked()) {
 			throw new IllegalStateException(
 					"must hold lock to access merged table"); //$NON-NLS-1$
 		}
 		if (mergedTables == null) {
 			mergedTables = openMergedReftable();
 		}
 		return mergedTables;
 	}
 
 	/**
 	 * @return whether the given refName would be illegal in a repository that
 	 *         uses loose refs.
 	 * @param refName
 	 *            the name to check
 	 * @param added
 	 *            a sorted set of refs we pretend have been added to the
 	 *            database.
 	 * @param deleted
 	 *            a set of refs we pretend have been removed from the database.
 	 * @throws IOException
 	 *             on I/O problems
 	 */
 	public boolean isNameConflicting(String refName, TreeSet<String> added,
 			Set<String> deleted) throws IOException {
 		lock.lock();
 		try {
 			Reftable table = reader();
 
 			// Cannot be nested within an existing reference.
 			int lastSlash = refName.lastIndexOf('/');
 			while (0 < lastSlash) {
 				String prefix = refName.substring(0, lastSlash);
 				if (!deleted.contains(prefix)
 						&& (table.hasRef(prefix) || added.contains(prefix))) {
 					return true;
 				}
 				lastSlash = refName.lastIndexOf('/', lastSlash - 1);
 			}
 
 			// Cannot be the container of an existing reference.
 			String prefix = refName + '/';
 			RefCursor c = table.seekRefsWithPrefix(prefix);
 			while (c.next()) {
 				if (!deleted.contains(c.getRef().getName())) {
 					return true;
 				}
 			}
 
 			String it = added.ceiling(refName + '/');
 			if (it != null && it.startsWith(prefix)) {
 				return true;
 			}
 			return false;
 		} finally {
 			lock.unlock();
 		}
 	}
 
 	/**
 	 * Read a single reference.
 	 * <p>
 	 * This method expects an unshortened reference name and does not search
 	 * using the standard search path.
 	 *
 	 * @param name
 	 *            the unabbreviated name of the reference.
 	 * @return the reference (if it exists); else {@code null}.
 	 * @throws java.io.IOException
 	 *             the reference space cannot be accessed.
 	 */
 	@Nullable
 	public Ref exactRef(String name) throws IOException {
 		lock.lock();
 		try {
 			Reftable table = reader();
 			Ref ref = table.exactRef(name);
 			if (ref != null && ref.isSymbolic()) {
 				return table.resolve(ref);
 			}
 			return ref;
 		} finally {
 			lock.unlock();
 		}
 	}
 
 	/**
 	 * Returns refs whose names start with a given prefix.
 	 *
 	 * @param prefix
 	 *            string that names of refs should start with; may be empty (to
 	 *            return all refs).
 	 * @return immutable list of refs whose names start with {@code prefix}.
 	 * @throws java.io.IOException
 	 *             the reference space cannot be accessed.
 	 */
 	public List<Ref> getRefsByPrefix(String prefix) throws IOException {
 		List<Ref> all = new ArrayList<>();
 		lock.lock();
 		try {
 			Reftable table = reader();
 			try (RefCursor rc = RefDatabase.ALL.equals(prefix) ? table.allRefs()
 					: table.seekRefsWithPrefix(prefix)) {
 				while (rc.next()) {
 					Ref ref = table.resolve(rc.getRef());
 					if (ref != null && ref.getObjectId() != null) {
 						all.add(ref);
 					}
 				}
 			}
 		} finally {
 			lock.unlock();
 		}
 
 		return Collections.unmodifiableList(all);
 	}
 
 	/**
 	 * Returns refs whose names start with a given prefix excluding all refs that
 	 * start with one of the given prefixes.
 	 *
 	 * @param include string that names of refs should start with; may be empty.
 	 * @param excludes strings that names of refs can't start with; may be empty.
 	 * @return immutable list of refs whose names start with {@code include} and
 	 *         none of the strings in {@code exclude}.
 	 * @throws java.io.IOException the reference space cannot be accessed.
 	 */
 	public List<Ref> getRefsByPrefixWithExclusions(String include, Set<String> excludes) throws IOException {
 		if (excludes.isEmpty()) {
 			return getRefsByPrefix(include);
 		}
 		List<Ref> results = new ArrayList<>();
 		lock.lock();
 		try {
 			Reftable table = reader();
 			Iterator<String> excludeIterator =
 					excludes.stream().sorted().collect(Collectors.toList()).iterator();
 			String currentExclusion = excludeIterator.hasNext() ? excludeIterator.next() : null;
 			try (RefCursor rc = RefDatabase.ALL.equals(include) ? table.allRefs() : table.seekRefsWithPrefix(include)) {
 				while (rc.next()) {
 					Ref ref = table.resolve(rc.getRef());
 					if (ref == null || ref.getObjectId() == null) {
 						continue;
 					}
 					// Skip prefixes that will never see since we are already further than those
 					// prefixes lexicographically.
 					while (excludeIterator.hasNext() && !ref.getName().startsWith(currentExclusion)
 							&& ref.getName().compareTo(currentExclusion) > 0) {
 						currentExclusion = excludeIterator.next();
 					}
 
 					if (currentExclusion != null && ref.getName().startsWith(currentExclusion)) {
 						rc.seekPastPrefix(currentExclusion);
 						continue;
 					}
 					results.add(ref);
 				}
 			}
 		} finally {
 			lock.unlock();
 		}
 
 		return Collections.unmodifiableList(results);
 	}
 
 	/**
 	 * @return whether there is a fast SHA1 to ref map.
 	 * @throws IOException in case of I/O problems.
 	 */
 	public boolean hasFastTipsWithSha1() throws IOException {
 		lock.lock();
 		try {
 			return reader().hasObjectMap();
 		} finally {
 			lock.unlock();
 		}
 	}
 
 	/**
 	 * Returns all refs that resolve directly to the given {@link ObjectId}.
 	 * Includes peeled {@link ObjectId}s.
 	 *
 	 * @param id
 	 *            {@link ObjectId} to resolve
 	 * @return a {@link Set} of {@link Ref}s whose tips point to the provided
 	 *         id.
 	 * @throws java.io.IOException
 	 *             on I/O errors.
 	 */
 	public Set<Ref> getTipsWithSha1(ObjectId id) throws IOException {
 		lock.lock();
 		try {
 			RefCursor cursor = reader().byObjectId(id);
 			Set<Ref> refs = new HashSet<>();
 			while (cursor.next()) {
 				refs.add(cursor.getRef());
 			}
 			return refs;
 		} finally {
 			lock.unlock();
 		}
 	}
 
 	/**
 	 * Drops all data that might be cached in memory.
 	 */
 	public void clearCache() {
 		lock.lock();
 		try {
 			mergedTables = null;
 		} finally {
 			lock.unlock();
 		}
 	}
 }