org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTree.java

/*
 * Copyright (C) 2016, Google Inc.
 * 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.internal.storage.reftree;

import static org.eclipse.jgit.lib.Constants.HEAD;
import static org.eclipse.jgit.lib.Constants.OBJ_BLOB;
import static org.eclipse.jgit.lib.Constants.R_REFS;
import static org.eclipse.jgit.lib.Constants.encode;
import static org.eclipse.jgit.lib.FileMode.GITLINK;
import static org.eclipse.jgit.lib.FileMode.SYMLINK;
import static org.eclipse.jgit.lib.FileMode.TYPE_GITLINK;
import static org.eclipse.jgit.lib.FileMode.TYPE_SYMLINK;
import static org.eclipse.jgit.lib.Ref.Storage.NEW;
import static org.eclipse.jgit.lib.Ref.Storage.PACKED;
import static org.eclipse.jgit.lib.RefDatabase.MAX_SYMBOLIC_REF_DEPTH;
import static org.eclipse.jgit.transport.ReceiveCommand.Result.LOCK_FAILURE;
import static org.eclipse.jgit.transport.ReceiveCommand.Result.REJECTED_OTHER_REASON;

import java.io.IOException;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;

import org.eclipse.jgit.annotations.Nullable;
import org.eclipse.jgit.dircache.DirCache;
import org.eclipse.jgit.dircache.DirCacheBuilder;
import org.eclipse.jgit.dircache.DirCacheEditor;
import org.eclipse.jgit.dircache.DirCacheEditor.DeletePath;
import org.eclipse.jgit.dircache.DirCacheEditor.PathEdit;
import org.eclipse.jgit.dircache.DirCacheEntry;
import org.eclipse.jgit.errors.CorruptObjectException;
import org.eclipse.jgit.errors.DirCacheNameConflictException;
import org.eclipse.jgit.errors.IncorrectObjectTypeException;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.ObjectIdRef;
import org.eclipse.jgit.lib.ObjectInserter;
import org.eclipse.jgit.lib.ObjectReader;
import org.eclipse.jgit.lib.Ref;
import org.eclipse.jgit.lib.Repository;
import org.eclipse.jgit.lib.SymbolicRef;
import org.eclipse.jgit.revwalk.RevTree;
import org.eclipse.jgit.util.RawParseUtils;

/**
 * Tree of references in the reference graph.
 * <p>
 * The root corresponds to the {@code "refs/"} subdirectory, for example the
 * default reference {@code "refs/heads/master"} is stored at path
 * {@code "heads/master"} in a {@code RefTree}.
 * <p>
 * Normal references are stored as {@link org.eclipse.jgit.lib.FileMode#GITLINK}
 * tree entries. The ObjectId in the tree entry is the ObjectId the reference
 * refers to.
 * <p>
 * Symbolic references are stored as
 * {@link org.eclipse.jgit.lib.FileMode#SYMLINK} entries, with the blob storing
 * the name of the target reference.
 * <p>
 * Annotated tags also store the peeled object using a {@code GITLINK} entry
 * with the suffix <code>" ^"</code> (space carrot), for example
 * {@code "tags/v1.0"} stores the annotated tag object, while
 * <code>"tags/v1.0 ^"</code> stores the commit the tag annotates.
 * <p>
 * {@code HEAD} is a special case and stored as {@code "..HEAD"}.
 */
public class RefTree {
	/** Suffix applied to GITLINK to indicate its the peeled value of a tag. */
	public static final String PEELED_SUFFIX = " ^"; //$NON-NLS-1$
	static final String ROOT_DOTDOT = ".."; //$NON-NLS-1$

	/**
	 * Create an empty reference tree.
	 *
	 * @return a new empty reference tree.
	 */
	public static RefTree newEmptyTree() {
		return new RefTree(DirCache.newInCore());
	}

	/**
	 * Load a reference tree.
	 *
	 * @param reader
	 *            reader to scan the reference tree with.
	 * @param tree
	 *            the tree to read.
	 * @return the ref tree read from the commit.
	 * @throws java.io.IOException
	 *             the repository cannot be accessed through the reader.
	 * @throws org.eclipse.jgit.errors.CorruptObjectException
	 *             a tree object is corrupt and cannot be read.
	 * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException
	 *             a tree object wasn't actually a tree.
	 * @throws org.eclipse.jgit.errors.MissingObjectException
	 *             a reference tree object doesn't exist.
	 */
	public static RefTree read(ObjectReader reader, RevTree tree)
			throws MissingObjectException, IncorrectObjectTypeException,
			CorruptObjectException, IOException {
		return new RefTree(DirCache.read(reader, tree));
	}

	private DirCache contents;
	private Map<ObjectId, String> pendingBlobs;

	private RefTree(DirCache dc) {
		this.contents = dc;
	}

	/**
	 * Read one reference.
	 * <p>
	 * References are always returned peeled
	 * ({@link org.eclipse.jgit.lib.Ref#isPeeled()} is true). If the reference
	 * points to an annotated tag, the returned reference will be peeled and
	 * contain {@link org.eclipse.jgit.lib.Ref#getPeeledObjectId()}.
	 * <p>
	 * If the reference is a symbolic reference and the chain depth is less than
	 * {@link org.eclipse.jgit.lib.RefDatabase#MAX_SYMBOLIC_REF_DEPTH} the
	 * returned reference is resolved. If the chain depth is longer, the
	 * symbolic reference is returned without resolving.
	 *
	 * @param reader
	 *            to access objects necessary to read the requested reference.
	 * @param name
	 *            name of the reference to read.
	 * @return the reference; null if it does not exist.
	 * @throws java.io.IOException
	 *             cannot read a symbolic reference target.
	 */
	@Nullable
	public Ref exactRef(ObjectReader reader, String name) throws IOException {
		Ref r = readRef(reader, name);
		if (r == null) {
			return null;
		} else if (r.isSymbolic()) {
			return resolve(reader, r, 0);
		}

		DirCacheEntry p = contents.getEntry(peeledPath(name));
		if (p != null && p.getRawMode() == TYPE_GITLINK) {
			return new ObjectIdRef.PeeledTag(PACKED, r.getName(),
					r.getObjectId(), p.getObjectId());
		}
		return r;
	}

	private Ref readRef(ObjectReader reader, String name) throws IOException {
		DirCacheEntry e = contents.getEntry(refPath(name));
		return e != null ? toRef(reader, e, name) : null;
	}

	private Ref toRef(ObjectReader reader, DirCacheEntry e, String name)
			throws IOException {
		int mode = e.getRawMode();
		if (mode == TYPE_GITLINK) {
			ObjectId id = e.getObjectId();
			return new ObjectIdRef.PeeledNonTag(PACKED, name, id);
		}

		if (mode == TYPE_SYMLINK) {
			ObjectId id = e.getObjectId();
			String n = pendingBlobs != null ? pendingBlobs.get(id) : null;
			if (n == null) {
				byte[] bin = reader.open(id, OBJ_BLOB).getCachedBytes();
				n = RawParseUtils.decode(bin);
			}
			Ref dst = new ObjectIdRef.Unpeeled(NEW, n, null);
			return new SymbolicRef(name, dst);
		}

		return null; // garbage file or something; not a reference.
	}

	private Ref resolve(ObjectReader reader, Ref ref, int depth)
			throws IOException {
		if (ref.isSymbolic() && depth < MAX_SYMBOLIC_REF_DEPTH) {
			Ref r = readRef(reader, ref.getTarget().getName());
			if (r == null) {
				return ref;
			}
			Ref dst = resolve(reader, r, depth + 1);
			return new SymbolicRef(ref.getName(), dst);
		}
		return ref;
	}

	/**
	 * Attempt a batch of commands against this RefTree.
	 * <p>
	 * The batch is applied atomically, either all commands apply at once, or
	 * they all reject and the RefTree is left unmodified.
	 * <p>
	 * On success (when this method returns {@code true}) the command results
	 * are left as-is (probably {@code NOT_ATTEMPTED}). Result fields are set
	 * only when this method returns {@code false} to indicate failure.
	 *
	 * @param cmdList
	 *            to apply. All commands should still have result NOT_ATTEMPTED.
	 * @return true if the commands applied; false if they were rejected.
	 */
	public boolean apply(Collection<Command> cmdList) {
		try {
			DirCacheEditor ed = contents.editor();
			for (Command cmd : cmdList) {
				if (!isValidRef(cmd)) {
					cmd.setResult(REJECTED_OTHER_REASON,
							JGitText.get().funnyRefname);
					Command.abort(cmdList, null);
					return false;
				}
				apply(ed, cmd);
			}
			ed.finish();
			return true;
		} catch (DirCacheNameConflictException e) {
			String r1 = refName(e.getPath1());
			String r2 = refName(e.getPath2());
			for (Command cmd : cmdList) {
				if (r1.equals(cmd.getRefName())
						|| r2.equals(cmd.getRefName())) {
					cmd.setResult(LOCK_FAILURE);
					break;
				}
			}
			Command.abort(cmdList, null);
			return false;
		} catch (LockFailureException e) {
			Command.abort(cmdList, null);
			return false;
		}
	}

	private static boolean isValidRef(Command cmd) {
		String n = cmd.getRefName();
		return HEAD.equals(n) || Repository.isValidRefName(n);
	}

	private void apply(DirCacheEditor ed, Command cmd) {
		String path = refPath(cmd.getRefName());
		Ref oldRef = cmd.getOldRef();
		final Ref newRef = cmd.getNewRef();

		if (newRef == null) {
			checkRef(contents.getEntry(path), cmd);
			ed.add(new DeletePath(path));
			cleanupPeeledRef(ed, oldRef);
			return;
		}

		if (newRef.isSymbolic()) {
			final String dst = newRef.getTarget().getName();
			ed.add(new PathEdit(path) {
				@Override
				public void apply(DirCacheEntry ent) {
					checkRef(ent, cmd);
					ObjectId id = Command.symref(dst);
					ent.setFileMode(SYMLINK);
					ent.setObjectId(id);
					if (pendingBlobs == null) {
						pendingBlobs = new HashMap<>(4);
					}
					pendingBlobs.put(id, dst);
				}
			}.setReplace(false));
			cleanupPeeledRef(ed, oldRef);
			return;
		}

		ed.add(new PathEdit(path) {
			@Override
			public void apply(DirCacheEntry ent) {
				checkRef(ent, cmd);
				ent.setFileMode(GITLINK);
				ent.setObjectId(newRef.getObjectId());
			}
		}.setReplace(false));

		if (newRef.getPeeledObjectId() != null) {
			ed.add(new PathEdit(peeledPath(newRef.getName())) {
				@Override
				public void apply(DirCacheEntry ent) {
					ent.setFileMode(GITLINK);
					ent.setObjectId(newRef.getPeeledObjectId());
				}
			}.setReplace(false));
		} else {
			cleanupPeeledRef(ed, oldRef);
		}
	}

	private static void checkRef(@Nullable DirCacheEntry ent, Command cmd) {
		if (!cmd.checkRef(ent)) {
			cmd.setResult(LOCK_FAILURE);
			throw new LockFailureException();
		}
	}

	private static void cleanupPeeledRef(DirCacheEditor ed, Ref ref) {
		if (ref != null && !ref.isSymbolic()
				&& (!ref.isPeeled() || ref.getPeeledObjectId() != null)) {
			ed.add(new DeletePath(peeledPath(ref.getName())));
		}
	}

	/**
	 * Convert a path name in a RefTree to the reference name known by Git.
	 *
	 * @param path
	 *            name read from the RefTree structure, for example
	 *            {@code "heads/master"}.
	 * @return reference name for the path, {@code "refs/heads/master"}.
	 */
	public static String refName(String path) {
		if (path.startsWith(ROOT_DOTDOT)) {
			return path.substring(2);
		}
		return R_REFS + path;
	}

	static String refPath(String name) {
		if (name.startsWith(R_REFS)) {
			return name.substring(R_REFS.length());
		}
		return ROOT_DOTDOT + name;
	}

	private static String peeledPath(String name) {
		return refPath(name) + PEELED_SUFFIX;
	}

	/**
	 * Write this reference tree.
	 *
	 * @param inserter
	 *            inserter to use when writing trees to the object database.
	 *            Caller is responsible for flushing the inserter before trying
	 *            to read the objects, or exposing them through a reference.
	 * @return the top level tree.
	 * @throws java.io.IOException
	 *             a tree could not be written.
	 */
	public ObjectId writeTree(ObjectInserter inserter) throws IOException {
		if (pendingBlobs != null) {
			for (String s : pendingBlobs.values()) {
				inserter.insert(OBJ_BLOB, encode(s));
			}
			pendingBlobs = null;
		}
		return contents.writeTree(inserter);
	}

	/**
	 * Create a deep copy of this RefTree.
	 *
	 * @return a deep copy of this RefTree.
	 */
	public RefTree copy() {
		RefTree r = new RefTree(DirCache.newInCore());
		DirCacheBuilder b = r.contents.builder();
		for (int i = 0; i < contents.getEntryCount(); i++) {
			b.add(new DirCacheEntry(contents.getEntry(i)));
		}
		b.finish();
		if (pendingBlobs != null) {
			r.pendingBlobs = new HashMap<>(pendingBlobs);
		}
		return r;
	}

	private static class LockFailureException extends RuntimeException {
		private static final long serialVersionUID = 1L;
	}
}