/*
 * Copyright (C) 2008-2009, Google Inc.
 * 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.dircache;

import static org.eclipse.jgit.dircache.DirCache.cmp;
import static org.eclipse.jgit.dircache.DirCacheTree.peq;
import static org.eclipse.jgit.lib.FileMode.TYPE_TREE;

import java.io.IOException;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.util.Paths;

Updates a DirCache by supplying discrete edit commands. 
 An editor updates a DirCache by taking a list of PathEdit commands and executing them against the entries of the destination cache to produce a new cache. This edit style allows applications to insert a few commands and then have the editor compute the proper entry indexes necessary to perform an efficient in-order update of the index records. This can be easier to use than DirCacheBuilder. 

See Also:
DirCacheBuilder/**
 * Updates a {@link org.eclipse.jgit.dircache.DirCache} by supplying discrete
 * edit commands.
 * <p>
 * An editor updates a DirCache by taking a list of
 * {@link org.eclipse.jgit.dircache.DirCacheEditor.PathEdit} commands and
 * executing them against the entries of the destination cache to produce a new
 * cache. This edit style allows applications to insert a few commands and then
 * have the editor compute the proper entry indexes necessary to perform an
 * efficient in-order update of the index records. This can be easier to use
 * than {@link org.eclipse.jgit.dircache.DirCacheBuilder}.
 * <p>
 *
 * @see DirCacheBuilder
 */
public class DirCacheEditor extends BaseDirCacheEditor {
	private static final Comparator<PathEdit> EDIT_CMP = (PathEdit o1,
			PathEdit o2) -> {
		final byte[] a = o1.path;
		final byte[] b = o2.path;
		return cmp(a, a.length, b, b.length);
	};

	private final List<PathEdit> edits;
	private int editIdx;

	
Construct a new editor.
Params:
dc – 
           the cache this editor will eventually update.
ecnt – 
           estimated number of entries the editor will have upon
           completion. This sizes the initial entry table./**
	 * Construct a new editor.
	 *
	 * @param dc
	 *            the cache this editor will eventually update.
	 * @param ecnt
	 *            estimated number of entries the editor will have upon
	 *            completion. This sizes the initial entry table.
	 */
	protected DirCacheEditor(DirCache dc, int ecnt) {
		super(dc, ecnt);
		edits = new ArrayList<>();
	}

	
Append one edit command to the list of commands to be applied.

Edit commands may be added in any order chosen by the application. They
are automatically rearranged by the builder to provide the most efficient
update possible.
Params:
edit – 
           another edit command./**
	 * Append one edit command to the list of commands to be applied.
	 * <p>
	 * Edit commands may be added in any order chosen by the application. They
	 * are automatically rearranged by the builder to provide the most efficient
	 * update possible.
	 *
	 * @param edit
	 *            another edit command.
	 */
	public void add(PathEdit edit) {
		edits.add(edit);
	}

	
{@inheritDoc} /** {@inheritDoc} */
	@Override
	public boolean commit() throws IOException {
		if (edits.isEmpty()) {
			// No changes? Don't rewrite the index.
			//
			cache.unlock();
			return true;
		}
		return super.commit();
	}

	
{@inheritDoc} /** {@inheritDoc} */
	@Override
	public void finish() {
		if (!edits.isEmpty()) {
			applyEdits();
			replace();
		}
	}

	private void applyEdits() {
		Collections.sort(edits, EDIT_CMP);
		editIdx = 0;

		final int maxIdx = cache.getEntryCount();
		int lastIdx = 0;
		while (editIdx < edits.size()) {
			PathEdit e = edits.get(editIdx++);
			int eIdx = cache.findEntry(lastIdx, e.path, e.path.length);
			final boolean missing = eIdx < 0;
			if (eIdx < 0)
				eIdx = -(eIdx + 1);
			final int cnt = Math.min(eIdx, maxIdx) - lastIdx;
			if (cnt > 0)
				fastKeep(lastIdx, cnt);

			if (e instanceof DeletePath) {
				lastIdx = missing ? eIdx : cache.nextEntry(eIdx);
				continue;
			}
			if (e instanceof DeleteTree) {
				lastIdx = cache.nextEntry(e.path, e.path.length, eIdx);
				continue;
			}

			if (missing) {
				DirCacheEntry ent = new DirCacheEntry(e.path);
				e.apply(ent);
				if (ent.getRawMode() == 0) {
					throw new IllegalArgumentException(MessageFormat.format(
							JGitText.get().fileModeNotSetForPath,
							ent.getPathString()));
				}
				lastIdx = e.replace
					? deleteOverlappingSubtree(ent, eIdx)
					: eIdx;
				fastAdd(ent);
			} else {
				// Apply to all entries of the current path (different stages)
				lastIdx = cache.nextEntry(eIdx);
				for (int i = eIdx; i < lastIdx; i++) {
					final DirCacheEntry ent = cache.getEntry(i);
					e.apply(ent);
					fastAdd(ent);
				}
			}
		}

		final int cnt = maxIdx - lastIdx;
		if (cnt > 0)
			fastKeep(lastIdx, cnt);
	}

	private int deleteOverlappingSubtree(DirCacheEntry ent, int eIdx) {
		byte[] entPath = ent.path;
		int entLen = entPath.length;

		// Delete any file that was previously processed and overlaps
		// the parent directory for the new entry. Since the editor
		// always processes entries in path order, binary search back
		// for the overlap for each parent directory.
		for (int p = pdir(entPath, entLen); p > 0; p = pdir(entPath, p)) {
			int i = findEntry(entPath, p);
			if (i >= 0) {
				// A file does overlap, delete the file from the array.
				// No other parents can have overlaps as the file should
				// have taken care of that itself.
				int n = --entryCnt - i;
				System.arraycopy(entries, i + 1, entries, i, n);
				break;
			}

			// If at least one other entry already exists in this parent
			// directory there is no need to continue searching up the tree.
			i = -(i + 1);
			if (i < entryCnt && inDir(entries[i], entPath, p)) {
				break;
			}
		}

		int maxEnt = cache.getEntryCount();
		if (eIdx >= maxEnt) {
			return maxEnt;
		}

		DirCacheEntry next = cache.getEntry(eIdx);
		if (Paths.compare(next.path, 0, next.path.length, 0,
				entPath, 0, entLen, TYPE_TREE) < 0) {
			// Next DirCacheEntry sorts before new entry as tree. Defer a
			// DeleteTree command to delete any entries if they exist. This
			// case only happens for A, A.c, A/c type of conflicts (rare).
			insertEdit(new DeleteTree(entPath));
			return eIdx;
		}

		// Next entry may be contained by the entry-as-tree, skip if so.
		while (eIdx < maxEnt && inDir(cache.getEntry(eIdx), entPath, entLen)) {
			eIdx++;
		}
		return eIdx;
	}

	private int findEntry(byte[] p, int pLen) {
		int low = 0;
		int high = entryCnt;
		while (low < high) {
			int mid = (low + high) >>> 1;
			int cmp = cmp(p, pLen, entries[mid]);
			if (cmp < 0) {
				high = mid;
			} else if (cmp == 0) {
				while (mid > 0 && cmp(p, pLen, entries[mid - 1]) == 0) {
					mid--;
				}
				return mid;
			} else {
				low = mid + 1;
			}
		}
		return -(low + 1);
	}

	private void insertEdit(DeleteTree d) {
		for (int i = editIdx; i < edits.size(); i++) {
			int cmp = EDIT_CMP.compare(d, edits.get(i));
			if (cmp < 0) {
				edits.add(i, d);
				return;
			} else if (cmp == 0) {
				return;
			}
		}
		edits.add(d);
	}

	private static boolean inDir(DirCacheEntry e, byte[] path, int pLen) {
		return e.path.length > pLen && e.path[pLen] == '/'
				&& peq(path, e.path, pLen);
	}

	private static int pdir(byte[] path, int e) {
		for (e--; e > 0; e--) {
			if (path[e] == '/') {
				return e;
			}
		}
		return 0;
	}

	
Any index record update.
 Applications should subclass and provide their own implementation for the apply(DirCacheEntry) method. The editor will invoke apply once for each record in the index which matches the path name. If there are multiple records (for example in stages 1, 2 and 3), the edit instance will be called multiple times, once for each stage. /**
	 * Any index record update.
	 * <p>
	 * Applications should subclass and provide their own implementation for the
	 * {@link #apply(DirCacheEntry)} method. The editor will invoke apply once
	 * for each record in the index which matches the path name. If there are
	 * multiple records (for example in stages 1, 2 and 3), the edit instance
	 * will be called multiple times, once for each stage.
	 */
	public abstract static class PathEdit {
		final byte[] path;
		boolean replace = true;

		
Create a new update command by path name.
Params:
entryPath – 
           path of the file within the repository./**
		 * Create a new update command by path name.
		 *
		 * @param entryPath
		 *            path of the file within the repository.
		 */
		public PathEdit(String entryPath) {
			path = Constants.encode(entryPath);
		}

		PathEdit(byte[] path) {
			this.path = path;
		}

		
Create a new update command for an existing entry instance.
Params:
ent – 
           entry instance to match path of. Only the path of this
           entry is actually considered during command evaluation./**
		 * Create a new update command for an existing entry instance.
		 *
		 * @param ent
		 *            entry instance to match path of. Only the path of this
		 *            entry is actually considered during command evaluation.
		 */
		public PathEdit(DirCacheEntry ent) {
			path = ent.path;
		}

		
Configure if a file can replace a directory (or vice versa).
 Default is true as this is usually the desired behavior. 
Params:
ok – 
           if true a file can replace a directory, or a directory can
           replace a file.
Returns:
this
Since:
4.2/**
		 * Configure if a file can replace a directory (or vice versa).
		 * <p>
		 * Default is {@code true} as this is usually the desired behavior.
		 *
		 * @param ok
		 *            if true a file can replace a directory, or a directory can
		 *            replace a file.
		 * @return {@code this}
		 * @since 4.2
		 */
		public PathEdit setReplace(boolean ok) {
			replace = ok;
			return this;
		}

		
Apply the update to a single cache entry matching the path.

After apply is invoked the entry is added to the output table, and
will be included in the new index.
Params:
ent – 
           the entry being processed. All fields are zeroed out if
           the path is a new path in the index./**
		 * Apply the update to a single cache entry matching the path.
		 * <p>
		 * After apply is invoked the entry is added to the output table, and
		 * will be included in the new index.
		 *
		 * @param ent
		 *            the entry being processed. All fields are zeroed out if
		 *            the path is a new path in the index.
		 */
		public abstract void apply(DirCacheEntry ent);

		@Override
		public String toString() {
			String p = DirCacheEntry.toString(path);
			return getClass().getSimpleName() + '[' + p + ']';
		}
	}

	
Deletes a single file entry from the index.
 This deletion command removes only a single file at the given location, but removes multiple stages (if present) for that path. To remove a complete subtree use DeleteTree instead. 
See Also:
DeleteTree/**
	 * Deletes a single file entry from the index.
	 * <p>
	 * This deletion command removes only a single file at the given location,
	 * but removes multiple stages (if present) for that path. To remove a
	 * complete subtree use {@link DeleteTree} instead.
	 *
	 * @see DeleteTree
	 */
	public static final class DeletePath extends PathEdit {
		
Create a new deletion command by path name.
Params:
entryPath – 
           path of the file within the repository./**
		 * Create a new deletion command by path name.
		 *
		 * @param entryPath
		 *            path of the file within the repository.
		 */
		public DeletePath(String entryPath) {
			super(entryPath);
		}

		
Create a new deletion command for an existing entry instance.
Params:
ent – 
           entry instance to remove. Only the path of this entry is
           actually considered during command evaluation./**
		 * Create a new deletion command for an existing entry instance.
		 *
		 * @param ent
		 *            entry instance to remove. Only the path of this entry is
		 *            actually considered during command evaluation.
		 */
		public DeletePath(DirCacheEntry ent) {
			super(ent);
		}

		@Override
		public void apply(DirCacheEntry ent) {
			throw new UnsupportedOperationException(JGitText.get().noApplyInDelete);
		}
	}

	
Recursively deletes all paths under a subtree.
 This deletion command is more generic than DeletePath as it can remove all records which appear recursively under the same subtree. Multiple stages are removed (if present) for any deleted entry. 
 This command will not remove a single file entry. To remove a single file use DeletePath. 
See Also:
DeletePath/**
	 * Recursively deletes all paths under a subtree.
	 * <p>
	 * This deletion command is more generic than {@link DeletePath} as it can
	 * remove all records which appear recursively under the same subtree.
	 * Multiple stages are removed (if present) for any deleted entry.
	 * <p>
	 * This command will not remove a single file entry. To remove a single file
	 * use {@link DeletePath}.
	 *
	 * @see DeletePath
	 */
	public static final class DeleteTree extends PathEdit {
		
Create a new tree deletion command by path name.
Params:
entryPath – 
           path of the subtree within the repository. If the path
           does not end with "/" a "/" is implicitly added to ensure
           only the subtree's contents are matched by the command.
           The special case "" (not "/"!) deletes all entries./**
		 * Create a new tree deletion command by path name.
		 *
		 * @param entryPath
		 *            path of the subtree within the repository. If the path
		 *            does not end with "/" a "/" is implicitly added to ensure
		 *            only the subtree's contents are matched by the command.
		 *            The special case "" (not "/"!) deletes all entries.
		 */
		public DeleteTree(String entryPath) {
			super(entryPath.isEmpty()
					|| entryPath.charAt(entryPath.length() - 1) == '/'
					? entryPath
					: entryPath + '/');
		}

		DeleteTree(byte[] path) {
			super(appendSlash(path));
		}

		private static byte[] appendSlash(byte[] path) {
			int n = path.length;
			if (n > 0 && path[n - 1] != '/') {
				byte[] r = new byte[n + 1];
				System.arraycopy(path, 0, r, 0, n);
				r[n] = '/';
				return r;
			}
			return path;
		}

		@Override
		public void apply(DirCacheEntry ent) {
			throw new UnsupportedOperationException(JGitText.get().noApplyInDelete);
		}
	}
}