RefTreeDatabase: Ref database using refs/txn/committed

Instead of storing references in the local filesystem rely on the
RefTree rooted at refs/txn/committed.  This avoids needing to store
references in the packed-refs file by keeping all data rooted under
a single refs/txn/committed ref.

Performance to scan all references from a well packed RefTree is very
close to reading the packed-refs file from local disk.

Storing a packed RefTree is smaller due to pack file compression,
about 49.39 bytes/ref (on average) compared to packed-refs using
~65.49 bytes/ref.

Change-Id: I75caa631162dc127a780095066195cbacc746d49

10 files changed, 1937 insertions, 4 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftree/RefTreeDatabaseTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftree/RefTreeDatabaseTest.java
new file mode 100644
index 0000000000..020d1b1b51
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/reftree/RefTreeDatabaseTest.java
@@ -0,0 +1,685 @@
+/*
+ * Copyright (C) 2010, 2013, 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.R_HEADS;
+import static org.eclipse.jgit.lib.Constants.R_TAGS;
+import static org.eclipse.jgit.lib.Ref.Storage.LOOSE;
+import static org.eclipse.jgit.lib.Ref.Storage.PACKED;
+import static org.eclipse.jgit.lib.RefDatabase.ALL;
+import static org.eclipse.jgit.transport.ReceiveCommand.Result.LOCK_FAILURE;
+import static org.eclipse.jgit.transport.ReceiveCommand.Result.OK;
+import static org.eclipse.jgit.transport.ReceiveCommand.Result.REJECTED_NONFASTFORWARD;
+import static org.eclipse.jgit.transport.ReceiveCommand.Result.REJECTED_OTHER_REASON;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.io.IOException;
+import java.text.MessageFormat;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+
+import org.eclipse.jgit.internal.JGitText;
+import org.eclipse.jgit.internal.storage.dfs.DfsRepositoryDescription;
+import org.eclipse.jgit.internal.storage.dfs.InMemoryRepository;
+import org.eclipse.jgit.junit.TestRepository;
+import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.BatchRefUpdate;
+import org.eclipse.jgit.lib.CommitBuilder;
+import org.eclipse.jgit.lib.NullProgressMonitor;
+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.RefDatabase;
+import org.eclipse.jgit.lib.RefUpdate;
+import org.eclipse.jgit.lib.SymbolicRef;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevTag;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.eclipse.jgit.transport.ReceiveCommand;
+import org.junit.Before;
+import org.junit.Test;
+
+public class RefTreeDatabaseTest {
+	private InMemRefTreeRepo repo;
+	private RefTreeDatabase refdb;
+	private RefDatabase bootstrap;
+
+	private TestRepository<InMemRefTreeRepo> testRepo;
+	private RevCommit A;
+	private RevCommit B;
+	private RevTag v1_0;
+
+	@Before
+	public void setUp() throws Exception {
+		repo = new InMemRefTreeRepo(new DfsRepositoryDescription("test"));
+		bootstrap = refdb.getBootstrap();
+
+		testRepo = new TestRepository<>(repo);
+		A = testRepo.commit().create();
+		B = testRepo.commit(testRepo.getRevWalk().parseCommit(A));
+		v1_0 = testRepo.tag("v1_0", B);
+		testRepo.getRevWalk().parseBody(v1_0);
+	}
+
+	@Test
+	public void testSupportsAtomic() {
+		assertTrue(refdb.performsAtomicTransactions());
+	}
+
+	@Test
+	public void testGetRefs_EmptyDatabase() throws IOException {
+		assertTrue("no references", refdb.getRefs(ALL).isEmpty());
+		assertTrue("no references", refdb.getRefs(R_HEADS).isEmpty());
+		assertTrue("no references", refdb.getRefs(R_TAGS).isEmpty());
+	}
+
+	@Test
+	public void testGetRefs_HeadOnOneBranch() throws IOException {
+		symref(HEAD, "refs/heads/master");
+		update("refs/heads/master", A);
+
+		Map<String, Ref> all = refdb.getRefs(ALL);
+		assertEquals(2, all.size());
+		assertTrue("has HEAD", all.containsKey(HEAD));
+		assertTrue("has master", all.containsKey("refs/heads/master"));
+
+		Ref head = all.get(HEAD);
+		Ref master = all.get("refs/heads/master");
+
+		assertEquals(HEAD, head.getName());
+		assertTrue(head.isSymbolic());
+		assertSame(LOOSE, head.getStorage());
+		assertSame("uses same ref as target", master, head.getTarget());
+
+		assertEquals("refs/heads/master", master.getName());
+		assertFalse(master.isSymbolic());
+		assertSame(PACKED, master.getStorage());
+		assertEquals(A, master.getObjectId());
+	}
+
+	@Test
+	public void testGetRefs_DetachedHead() throws IOException {
+		update(HEAD, A);
+
+		Map<String, Ref> all = refdb.getRefs(ALL);
+		assertEquals(1, all.size());
+		assertTrue("has HEAD", all.containsKey(HEAD));
+
+		Ref head = all.get(HEAD);
+		assertEquals(HEAD, head.getName());
+		assertFalse(head.isSymbolic());
+		assertSame(PACKED, head.getStorage());
+		assertEquals(A, head.getObjectId());
+	}
+
+	@Test
+	public void testGetRefs_DeeplyNestedBranch() throws IOException {
+		String name = "refs/heads/a/b/c/d/e/f/g/h/i/j/k";
+		update(name, A);
+
+		Map<String, Ref> all = refdb.getRefs(ALL);
+		assertEquals(1, all.size());
+
+		Ref r = all.get(name);
+		assertEquals(name, r.getName());
+		assertFalse(r.isSymbolic());
+		assertSame(PACKED, r.getStorage());
+		assertEquals(A, r.getObjectId());
+	}
+
+	@Test
+	public void testGetRefs_HeadBranchNotBorn() throws IOException {
+		update("refs/heads/A", A);
+		update("refs/heads/B", B);
+
+		Map<String, Ref> all = refdb.getRefs(ALL);
+		assertEquals(2, all.size());
+		assertFalse("no HEAD", all.containsKey(HEAD));
+
+		Ref a = all.get("refs/heads/A");
+		Ref b = all.get("refs/heads/B");
+
+		assertEquals(A, a.getObjectId());
+		assertEquals(B, b.getObjectId());
+
+		assertEquals("refs/heads/A", a.getName());
+		assertEquals("refs/heads/B", b.getName());
+	}
+
+	@Test
+	public void testGetRefs_HeadsOnly() throws IOException {
+		update("refs/heads/A", A);
+		update("refs/heads/B", B);
+		update("refs/tags/v1.0", v1_0);
+
+		Map<String, Ref> heads = refdb.getRefs(R_HEADS);
+		assertEquals(2, heads.size());
+
+		Ref a = heads.get("A");
+		Ref b = heads.get("B");
+
+		assertEquals("refs/heads/A", a.getName());
+		assertEquals("refs/heads/B", b.getName());
+
+		assertEquals(A, a.getObjectId());
+		assertEquals(B, b.getObjectId());
+	}
+
+	@Test
+	public void testGetRefs_TagsOnly() throws IOException {
+		update("refs/heads/A", A);
+		update("refs/heads/B", B);
+		update("refs/tags/v1.0", v1_0);
+
+		Map<String, Ref> tags = refdb.getRefs(R_TAGS);
+		assertEquals(1, tags.size());
+
+		Ref a = tags.get("v1.0");
+		assertEquals("refs/tags/v1.0", a.getName());
+		assertEquals(v1_0, a.getObjectId());
+		assertTrue(a.isPeeled());
+		assertEquals(v1_0.getObject(), a.getPeeledObjectId());
+	}
+
+	@Test
+	public void testGetRefs_HeadsSymref() throws IOException {
+		symref("refs/heads/other", "refs/heads/master");
+		update("refs/heads/master", A);
+
+		Map<String, Ref> heads = refdb.getRefs(R_HEADS);
+		assertEquals(2, heads.size());
+
+		Ref master = heads.get("master");
+		Ref other = heads.get("other");
+
+		assertEquals("refs/heads/master", master.getName());
+		assertEquals(A, master.getObjectId());
+
+		assertEquals("refs/heads/other", other.getName());
+		assertEquals(A, other.getObjectId());
+		assertSame(master, other.getTarget());
+	}
+
+	@Test
+	public void testGetRefs_InvalidPrefixes() throws IOException {
+		update("refs/heads/A", A);
+
+		assertTrue("empty refs/heads", refdb.getRefs("refs/heads").isEmpty());
+		assertTrue("empty objects", refdb.getRefs("objects").isEmpty());
+		assertTrue("empty objects/", refdb.getRefs("objects/").isEmpty());
+	}
+
+	@Test
+	public void testGetRefs_DiscoversNew() throws IOException {
+		update("refs/heads/master", A);
+		Map<String, Ref> orig = refdb.getRefs(ALL);
+
+		update("refs/heads/next", B);
+		Map<String, Ref> next = refdb.getRefs(ALL);
+
+		assertEquals(1, orig.size());
+		assertEquals(2, next.size());
+
+		assertFalse(orig.containsKey("refs/heads/next"));
+		assertTrue(next.containsKey("refs/heads/next"));
+
+		assertEquals(A, next.get("refs/heads/master").getObjectId());
+		assertEquals(B, next.get("refs/heads/next").getObjectId());
+	}
+
+	@Test
+	public void testGetRefs_DiscoversModified() throws IOException {
+		symref(HEAD, "refs/heads/master");
+		update("refs/heads/master", A);
+
+		Map<String, Ref> all = refdb.getRefs(ALL);
+		assertEquals(A, all.get(HEAD).getObjectId());
+
+		update("refs/heads/master", B);
+		all = refdb.getRefs(ALL);
+		assertEquals(B, all.get(HEAD).getObjectId());
+		assertEquals(B, refdb.exactRef(HEAD).getObjectId());
+	}
+
+	@Test
+	public void testGetRefs_CycleInSymbolicRef() throws IOException {
+		symref("refs/1", "refs/2");
+		symref("refs/2", "refs/3");
+		symref("refs/3", "refs/4");
+		symref("refs/4", "refs/5");
+		symref("refs/5", "refs/end");
+		update("refs/end", A);
+
+		Map<String, Ref> all = refdb.getRefs(ALL);
+		Ref r = all.get("refs/1");
+		assertNotNull("has 1", r);
+
+		assertEquals("refs/1", r.getName());
+		assertEquals(A, r.getObjectId());
+		assertTrue(r.isSymbolic());
+
+		r = r.getTarget();
+		assertEquals("refs/2", r.getName());
+		assertEquals(A, r.getObjectId());
+		assertTrue(r.isSymbolic());
+
+		r = r.getTarget();
+		assertEquals("refs/3", r.getName());
+		assertEquals(A, r.getObjectId());
+		assertTrue(r.isSymbolic());
+
+		r = r.getTarget();
+		assertEquals("refs/4", r.getName());
+		assertEquals(A, r.getObjectId());
+		assertTrue(r.isSymbolic());
+
+		r = r.getTarget();
+		assertEquals("refs/5", r.getName());
+		assertEquals(A, r.getObjectId());
+		assertTrue(r.isSymbolic());
+
+		r = r.getTarget();
+		assertEquals("refs/end", r.getName());
+		assertEquals(A, r.getObjectId());
+		assertFalse(r.isSymbolic());
+
+		symref("refs/5", "refs/6");
+		symref("refs/6", "refs/end");
+		all = refdb.getRefs(ALL);
+		assertNull("mising 1 due to cycle", all.get("refs/1"));
+		assertEquals(A, all.get("refs/2").getObjectId());
+		assertEquals(A, all.get("refs/3").getObjectId());
+		assertEquals(A, all.get("refs/4").getObjectId());
+		assertEquals(A, all.get("refs/5").getObjectId());
+		assertEquals(A, all.get("refs/6").getObjectId());
+		assertEquals(A, all.get("refs/end").getObjectId());
+	}
+
+	@Test
+	public void testGetRef_NonExistingBranchConfig() throws IOException {
+		assertNull("find branch config", refdb.getRef("config"));
+		assertNull("find branch config", refdb.getRef("refs/heads/config"));
+	}
+
+	@Test
+	public void testGetRef_FindBranchConfig() throws IOException {
+		update("refs/heads/config", A);
+
+		for (String t : new String[] { "config", "refs/heads/config" }) {
+			Ref r = refdb.getRef(t);
+			assertNotNull("find branch config (" + t + ")", r);
+			assertEquals("for " + t, "refs/heads/config", r.getName());
+			assertEquals("for " + t, A, r.getObjectId());
+		}
+	}
+
+	@Test
+	public void testFirstExactRef() throws IOException {
+		update("refs/heads/A", A);
+		update("refs/tags/v1.0", v1_0);
+
+		Ref a = refdb.firstExactRef("refs/heads/A", "refs/tags/v1.0");
+		Ref one = refdb.firstExactRef("refs/tags/v1.0", "refs/heads/A");
+
+		assertEquals("refs/heads/A", a.getName());
+		assertEquals("refs/tags/v1.0", one.getName());
+
+		assertEquals(A, a.getObjectId());
+		assertEquals(v1_0, one.getObjectId());
+	}
+
+	@Test
+	public void testExactRef_DiscoversModified() throws IOException {
+		symref(HEAD, "refs/heads/master");
+		update("refs/heads/master", A);
+		assertEquals(A, refdb.exactRef(HEAD).getObjectId());
+
+		update("refs/heads/master", B);
+		assertEquals(B, refdb.exactRef(HEAD).getObjectId());
+	}
+
+	@Test
+	public void testIsNameConflicting() throws IOException {
+		update("refs/heads/a/b", A);
+		update("refs/heads/q", B);
+
+		// new references cannot replace an existing container
+		assertTrue(refdb.isNameConflicting("refs"));
+		assertTrue(refdb.isNameConflicting("refs/heads"));
+		assertTrue(refdb.isNameConflicting("refs/heads/a"));
+
+		// existing reference is not conflicting
+		assertFalse(refdb.isNameConflicting("refs/heads/a/b"));
+
+		// new references are not conflicting
+		assertFalse(refdb.isNameConflicting("refs/heads/a/d"));
+		assertFalse(refdb.isNameConflicting("refs/heads/master"));
+
+		// existing reference must not be used as a container
+		assertTrue(refdb.isNameConflicting("refs/heads/a/b/c"));
+		assertTrue(refdb.isNameConflicting("refs/heads/q/master"));
+
+		// refs/txn/ names always conflict.
+		assertTrue(refdb.isNameConflicting(refdb.getTxnCommitted()));
+		assertTrue(refdb.isNameConflicting("refs/txn/foo"));
+	}
+
+	@Test
+	public void testUpdate_RefusesRefsTxnNamespace() throws IOException {
+		ObjectId txnId = getTxnCommitted();
+
+		RefUpdate u = refdb.newUpdate("refs/txn/tmp", false);
+		u.setNewObjectId(B);
+		assertEquals(RefUpdate.Result.LOCK_FAILURE, u.update());
+		assertEquals(txnId, getTxnCommitted());
+
+		ReceiveCommand cmd = command(null, B, "refs/txn/tmp");
+		BatchRefUpdate batch = refdb.newBatchUpdate();
+		batch.addCommand(cmd);
+		batch.execute(new RevWalk(repo), NullProgressMonitor.INSTANCE);
+
+		assertEquals(REJECTED_OTHER_REASON, cmd.getResult());
+		assertEquals(MessageFormat.format(JGitText.get().invalidRefName,
+				"refs/txn/tmp"), cmd.getMessage());
+		assertEquals(txnId, getTxnCommitted());
+	}
+
+	@Test
+	public void testUpdate_RefusesDotLockInRefName() throws IOException {
+		ObjectId txnId = getTxnCommitted();
+
+		RefUpdate u = refdb.newUpdate("refs/heads/pu.lock", false);
+		u.setNewObjectId(B);
+		assertEquals(RefUpdate.Result.REJECTED, u.update());
+		assertEquals(txnId, getTxnCommitted());
+
+		ReceiveCommand cmd = command(null, B, "refs/heads/pu.lock");
+		BatchRefUpdate batch = refdb.newBatchUpdate();
+		batch.addCommand(cmd);
+		batch.execute(new RevWalk(repo), NullProgressMonitor.INSTANCE);
+
+		assertEquals(REJECTED_OTHER_REASON, cmd.getResult());
+		assertEquals(JGitText.get().funnyRefname, cmd.getMessage());
+		assertEquals(txnId, getTxnCommitted());
+	}
+
+	@Test
+	public void testBatchRefUpdate_NonFastForwardAborts() throws IOException {
+		update("refs/heads/master", A);
+		update("refs/heads/masters", B);
+		ObjectId txnId = getTxnCommitted();
+
+		List<ReceiveCommand> commands = Arrays.asList(
+				command(A, B, "refs/heads/master"),
+				command(B, A, "refs/heads/masters"));
+		BatchRefUpdate batchUpdate = refdb.newBatchUpdate();
+		batchUpdate.addCommand(commands);
+		batchUpdate.execute(new RevWalk(repo), NullProgressMonitor.INSTANCE);
+		assertEquals(txnId, getTxnCommitted());
+
+		assertEquals(REJECTED_NONFASTFORWARD,
+				commands.get(1).getResult());
+		assertEquals(REJECTED_OTHER_REASON,
+				commands.get(0).getResult());
+		assertEquals(JGitText.get().transactionAborted,
+				commands.get(0).getMessage());
+	}
+
+	@Test
+	public void testBatchRefUpdate_ForceUpdate() throws IOException {
+		update("refs/heads/master", A);
+		update("refs/heads/masters", B);
+		ObjectId txnId = getTxnCommitted();
+
+		List<ReceiveCommand> commands = Arrays.asList(
+				command(A, B, "refs/heads/master"),
+				command(B, A, "refs/heads/masters"));
+		BatchRefUpdate batchUpdate = refdb.newBatchUpdate();
+		batchUpdate.setAllowNonFastForwards(true);
+		batchUpdate.addCommand(commands);
+		batchUpdate.execute(new RevWalk(repo), NullProgressMonitor.INSTANCE);
+		assertNotEquals(txnId, getTxnCommitted());
+
+		Map<String, Ref> refs = refdb.getRefs(ALL);
+		assertEquals(OK, commands.get(0).getResult());
+		assertEquals(OK, commands.get(1).getResult());
+		assertEquals(
+				"[refs/heads/master, refs/heads/masters]",
+				refs.keySet().toString());
+		assertEquals(B.getId(), refs.get("refs/heads/master").getObjectId());
+		assertEquals(A.getId(), refs.get("refs/heads/masters").getObjectId());
+	}
+
+	@Test
+	public void testBatchRefUpdate_NonFastForwardDoesNotDoExpensiveMergeCheck()
+			throws IOException {
+		update("refs/heads/master", B);
+		ObjectId txnId = getTxnCommitted();
+
+		List<ReceiveCommand> commands = Arrays.asList(
+				command(B, A, "refs/heads/master"));
+		BatchRefUpdate batchUpdate = refdb.newBatchUpdate();
+		batchUpdate.setAllowNonFastForwards(true);
+		batchUpdate.addCommand(commands);
+		batchUpdate.execute(new RevWalk(repo) {
+			@Override
+			public boolean isMergedInto(RevCommit base, RevCommit tip) {
+				fail("isMergedInto() should not be called");
+				return false;
+			}
+		}, NullProgressMonitor.INSTANCE);
+		assertNotEquals(txnId, getTxnCommitted());
+
+		Map<String, Ref> refs = refdb.getRefs(ALL);
+		assertEquals(OK, commands.get(0).getResult());
+		assertEquals(A.getId(), refs.get("refs/heads/master").getObjectId());
+	}
+
+	@Test
+	public void testBatchRefUpdate_ConflictCausesAbort() throws IOException {
+		update("refs/heads/master", A);
+		update("refs/heads/masters", B);
+		ObjectId txnId = getTxnCommitted();
+
+		List<ReceiveCommand> commands = Arrays.asList(
+				command(A, B, "refs/heads/master"),
+				command(null, A, "refs/heads/master/x"),
+				command(null, A, "refs/heads"));
+		BatchRefUpdate batchUpdate = refdb.newBatchUpdate();
+		batchUpdate.setAllowNonFastForwards(true);
+		batchUpdate.addCommand(commands);
+		batchUpdate.execute(new RevWalk(repo), NullProgressMonitor.INSTANCE);
+		assertEquals(txnId, getTxnCommitted());
+
+		assertEquals(LOCK_FAILURE, commands.get(0).getResult());
+
+		assertEquals(REJECTED_OTHER_REASON, commands.get(1).getResult());
+		assertEquals(JGitText.get().transactionAborted,
+				commands.get(1).getMessage());
+
+		assertEquals(REJECTED_OTHER_REASON, commands.get(2).getResult());
+		assertEquals(JGitText.get().transactionAborted,
+				commands.get(2).getMessage());
+	}
+
+	@Test
+	public void testBatchRefUpdate_NoConflictIfDeleted() throws IOException {
+		update("refs/heads/master", A);
+		update("refs/heads/masters", B);
+		ObjectId txnId = getTxnCommitted();
+
+		List<ReceiveCommand> commands = Arrays.asList(
+				command(A, B, "refs/heads/master"),
+				command(null, A, "refs/heads/masters/x"),
+				command(B, null, "refs/heads/masters"));
+		BatchRefUpdate batchUpdate = refdb.newBatchUpdate();
+		batchUpdate.setAllowNonFastForwards(true);
+		batchUpdate.addCommand(commands);
+		batchUpdate.execute(new RevWalk(repo), NullProgressMonitor.INSTANCE);
+		assertNotEquals(txnId, getTxnCommitted());
+
+		assertEquals(OK, commands.get(0).getResult());
+		assertEquals(OK, commands.get(1).getResult());
+		assertEquals(OK, commands.get(2).getResult());
+
+		Map<String, Ref> refs = refdb.getRefs(ALL);
+		assertEquals(
+				"[refs/heads/master, refs/heads/masters/x]",
+				refs.keySet().toString());
+		assertEquals(A.getId(), refs.get("refs/heads/masters/x").getObjectId());
+	}
+
+	private ObjectId getTxnCommitted() throws IOException {
+		Ref r = bootstrap.exactRef(refdb.getTxnCommitted());
+		if (r != null && r.getObjectId() != null) {
+			return r.getObjectId();
+		}
+		return ObjectId.zeroId();
+	}
+
+	private static ReceiveCommand command(AnyObjectId a, AnyObjectId b,
+			String name) {
+		return new ReceiveCommand(
+				a != null ? a.copy() : ObjectId.zeroId(),
+				b != null ? b.copy() : ObjectId.zeroId(),
+				name);
+	}
+
+	private void symref(final String name, final String dst)
+			throws IOException {
+		commit(new Function() {
+			@Override
+			public boolean apply(ObjectReader reader, RefTree tree)
+					throws IOException {
+				Ref old = tree.exactRef(reader, name);
+				Command n = new Command(
+					old,
+					new SymbolicRef(
+						name,
+						new ObjectIdRef.Unpeeled(Ref.Storage.NEW, dst, null)));
+				return tree.apply(Collections.singleton(n));
+			}
+		});
+	}
+
+	private void update(final String name, final ObjectId id)
+			throws IOException {
+		commit(new Function() {
+			@Override
+			public boolean apply(ObjectReader reader, RefTree tree)
+					throws IOException {
+				Ref old = tree.exactRef(reader, name);
+				Command n;
+				try (RevWalk rw = new RevWalk(repo)) {
+					n = new Command(old, Command.toRef(rw, id, name, true));
+				}
+				return tree.apply(Collections.singleton(n));
+			}
+		});
+	}
+
+	interface Function {
+		boolean apply(ObjectReader reader, RefTree tree) throws IOException;
+	}
+
+	private void commit(Function fun) throws IOException {
+		try (ObjectReader reader = repo.newObjectReader();
+				ObjectInserter inserter = repo.newObjectInserter();
+				RevWalk rw = new RevWalk(reader)) {
+			RefUpdate u = bootstrap.newUpdate(refdb.getTxnCommitted(), false);
+			CommitBuilder cb = new CommitBuilder();
+			testRepo.setAuthorAndCommitter(cb);
+
+			Ref ref = bootstrap.exactRef(refdb.getTxnCommitted());
+			RefTree tree;
+			if (ref != null && ref.getObjectId() != null) {
+				tree = RefTree.read(reader, rw.parseTree(ref.getObjectId()));
+				cb.setParentId(ref.getObjectId());
+				u.setExpectedOldObjectId(ref.getObjectId());
+			} else {
+				tree = RefTree.newEmptyTree();
+				u.setExpectedOldObjectId(ObjectId.zeroId());
+			}
+
+			assertTrue(fun.apply(reader, tree));
+			cb.setTreeId(tree.writeTree(inserter));
+			u.setNewObjectId(inserter.insert(cb));
+			inserter.flush();
+			switch (u.update(rw)) {
+			case NEW:
+			case FAST_FORWARD:
+				break;
+			default:
+				fail("Expected " + u.getName() + " to update");
+			}
+		}
+	}
+
+	private class InMemRefTreeRepo extends InMemoryRepository {
+		private final RefTreeDatabase refs;
+
+		InMemRefTreeRepo(DfsRepositoryDescription repoDesc) {
+			super(repoDesc);
+			refs = new RefTreeDatabase(this, super.getRefDatabase(),
+					"refs/txn/committed");
+			RefTreeDatabaseTest.this.refdb = refs;
+		}
+
+		public RefDatabase getRefDatabase() {
+			return refs;
+		}
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java
index 205d3c7f8a..a050e1a5bd 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/dfs/InMemoryRepository.java
@@ -24,6 +24,7 @@ import org.eclipse.jgit.lib.ObjectIdRef;
 import org.eclipse.jgit.lib.ProgressMonitor;
 import org.eclipse.jgit.lib.Ref;
 import org.eclipse.jgit.lib.Ref.Storage;
+import org.eclipse.jgit.lib.RefDatabase;
 import org.eclipse.jgit.lib.SymbolicRef;
 import org.eclipse.jgit.revwalk.RevObject;
 import org.eclipse.jgit.revwalk.RevTag;
@@ -54,7 +55,7 @@ public class InMemoryRepository extends DfsRepository {
 	static final AtomicInteger packId = new AtomicInteger();
 
 	private final DfsObjDatabase objdb;
-	private final DfsRefDatabase refdb;
+	private final RefDatabase refdb;
 	private boolean performsAtomicTransactions = true;
 
 	/**
@@ -80,7 +81,7 @@ public class InMemoryRepository extends DfsRepository {
 	}
 
 	@Override
-	public DfsRefDatabase getRefDatabase() {
+	public RefDatabase getRefDatabase() {
 		return refdb;
 	}
 
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/AlwaysFailUpdate.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/AlwaysFailUpdate.java
new file mode 100644
index 0000000000..12ef8734c4
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/AlwaysFailUpdate.java
@@ -0,0 +1,98 @@
+/*
+ * 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 java.io.IOException;
+
+import org.eclipse.jgit.lib.ObjectIdRef;
+import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.RefDatabase;
+import org.eclipse.jgit.lib.RefUpdate;
+import org.eclipse.jgit.lib.Repository;
+
+/** Update that always rejects with {@code LOCK_FAILURE}. */
+class AlwaysFailUpdate extends RefUpdate {
+	private final RefTreeDatabase refdb;
+
+	AlwaysFailUpdate(RefTreeDatabase refdb, String name) {
+		super(new ObjectIdRef.Unpeeled(Ref.Storage.NEW, name, null));
+		this.refdb = refdb;
+		setCheckConflicting(false);
+	}
+
+	@Override
+	protected RefDatabase getRefDatabase() {
+		return refdb;
+	}
+
+	@Override
+	protected Repository getRepository() {
+		return refdb.getRepository();
+	}
+
+	@Override
+	protected boolean tryLock(boolean deref) throws IOException {
+		return false;
+	}
+
+	@Override
+	protected void unlock() {
+		// No locks are held here.
+	}
+
+	@Override
+	protected Result doUpdate(Result desiredResult) {
+		return Result.LOCK_FAILURE;
+	}
+
+	@Override
+	protected Result doDelete(Result desiredResult) {
+		return Result.LOCK_FAILURE;
+	}
+
+	@Override
+	protected Result doLink(String target) {
+		return Result.LOCK_FAILURE;
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/Command.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/Command.java
index 9ac375f168..540c4384a7 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/Command.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/Command.java
@@ -132,7 +132,7 @@ public class Command {
 		this.cmd = cmd;
 	}
 
-	private static Ref toRef(RevWalk rw, ObjectId id, String name,
+	static Ref toRef(RevWalk rw, ObjectId id, String name,
 			boolean mustExist) throws MissingObjectException, IOException {
 		if (ObjectId.zeroId().equals(id)) {
 			return null;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTree.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTree.java
index 237f7e9958..66c0be6764 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTree.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTree.java
@@ -43,6 +43,7 @@
 
 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;
@@ -80,6 +81,7 @@ 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;
@@ -243,6 +245,11 @@ public class RefTree {
 		try {
 			DirCacheEditor ed = contents.editor();
 			for (Command cmd : cmdList) {
+				if (!isValidRef(cmd)) {
+					cmd.setResult(REJECTED_OTHER_REASON,
+							JGitText.get().funnyRefname);
+					return abort(cmdList);
+				}
 				apply(ed, cmd);
 			}
 			ed.finish();
@@ -263,6 +270,11 @@ public class RefTree {
 		}
 	}
 
+	private static boolean isValidRef(Command cmd) {
+		String n = cmd.getRefName();
+		return HEAD.equals(n) || Repository.isValidRefName(n);
+	}
+
 	private void apply(DirCacheEditor ed, final Command cmd) {
 		String path = refPath(cmd.getRefName());
 		Ref oldRef = cmd.getOldRef();
@@ -358,7 +370,7 @@ public class RefTree {
 		return R_REFS + path;
 	}
 
-	private static String refPath(String name) {
+	static String refPath(String name) {
 		if (name.startsWith(R_REFS)) {
 			return name.substring(R_REFS.length());
 		}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeBatch.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeBatch.java
new file mode 100644
index 0000000000..0cedea94d0
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeBatch.java
@@ -0,0 +1,240 @@
+/*
+ * 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.OBJ_TREE;
+import static org.eclipse.jgit.transport.ReceiveCommand.Result.NOT_ATTEMPTED;
+import static org.eclipse.jgit.transport.ReceiveCommand.Result.OK;
+import static org.eclipse.jgit.transport.ReceiveCommand.Result.REJECTED_NONFASTFORWARD;
+import static org.eclipse.jgit.transport.ReceiveCommand.Result.REJECTED_OTHER_REASON;
+import static org.eclipse.jgit.transport.ReceiveCommand.Type.UPDATE;
+import static org.eclipse.jgit.transport.ReceiveCommand.Type.UPDATE_NONFASTFORWARD;
+
+import java.io.IOException;
+import java.text.MessageFormat;
+import java.util.ArrayList;
+import java.util.List;
+
+import org.eclipse.jgit.annotations.Nullable;
+import org.eclipse.jgit.internal.JGitText;
+import org.eclipse.jgit.lib.BatchRefUpdate;
+import org.eclipse.jgit.lib.CommitBuilder;
+import org.eclipse.jgit.lib.NullProgressMonitor;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
+import org.eclipse.jgit.lib.ObjectReader;
+import org.eclipse.jgit.lib.PersonIdent;
+import org.eclipse.jgit.lib.ProgressMonitor;
+import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.eclipse.jgit.transport.ReceiveCommand;
+
+/** Batch update a {@link RefTreeDatabase}. */
+class RefTreeBatch extends BatchRefUpdate {
+	private final RefTreeDatabase refdb;
+	private Ref src;
+	private ObjectId parentCommitId;
+	private ObjectId parentTreeId;
+	private RefTree tree;
+	private PersonIdent author;
+	private ObjectId newCommitId;
+
+	RefTreeBatch(RefTreeDatabase refdb) {
+		super(refdb);
+		this.refdb = refdb;
+	}
+
+	@Override
+	public void execute(RevWalk rw, ProgressMonitor monitor)
+			throws IOException {
+		List<Command> todo = new ArrayList<>(getCommands().size());
+		for (ReceiveCommand c : getCommands()) {
+			if (!isAllowNonFastForwards()) {
+				if (c.getType() == UPDATE) {
+					c.updateType(rw);
+				}
+				if (c.getType() == UPDATE_NONFASTFORWARD) {
+					c.setResult(REJECTED_NONFASTFORWARD);
+					reject();
+					return;
+				}
+			}
+			todo.add(new Command(rw, c));
+		}
+		init(rw);
+		execute(rw, todo);
+	}
+
+	private void reject() {
+		String aborted = JGitText.get().transactionAborted;
+		for (ReceiveCommand c : getCommands()) {
+			if (c.getResult() == NOT_ATTEMPTED) {
+				c.setResult(REJECTED_OTHER_REASON, aborted);
+			}
+		}
+	}
+
+	void init(RevWalk rw) throws IOException {
+		src = refdb.getBootstrap().exactRef(refdb.getTxnCommitted());
+		if (src != null && src.getObjectId() != null) {
+			RevCommit c = rw.parseCommit(src.getObjectId());
+			parentCommitId = c;
+			parentTreeId = c.getTree();
+			tree = RefTree.read(rw.getObjectReader(), c.getTree());
+		} else {
+			parentCommitId = ObjectId.zeroId();
+			parentTreeId = new ObjectInserter.Formatter()
+					.idFor(OBJ_TREE, new byte[] {});
+			tree = RefTree.newEmptyTree();
+		}
+	}
+
+	@Nullable
+	Ref exactRef(ObjectReader reader, String name) throws IOException {
+		return tree.exactRef(reader, name);
+	}
+
+	/**
+	 * Execute an update from {@link RefTreeUpdate} or {@link RefTreeRename}.
+	 *
+	 * @param rw
+	 *            current RevWalk handling the update or rename.
+	 * @param todo
+	 *            commands to execute. Must never be a bootstrap reference name.
+	 * @throws IOException
+	 *             the storage system is unable to read or write data.
+	 */
+	void execute(RevWalk rw, List<Command> todo) throws IOException {
+		for (Command c : todo) {
+			if (c.getResult() != NOT_ATTEMPTED) {
+				reject(todo, JGitText.get().transactionAborted);
+				return;
+			}
+			if (refdb.conflictsWithBootstrap(c.getRefName())) {
+				c.setResult(REJECTED_OTHER_REASON, MessageFormat
+						.format(JGitText.get().invalidRefName, c.getRefName()));
+				reject(todo, JGitText.get().transactionAborted);
+				return;
+			}
+		}
+
+		if (apply(todo) && newCommitId != null) {
+			commit(rw, todo);
+		}
+	}
+
+	private boolean apply(List<Command> todo) throws IOException {
+		if (!tree.apply(todo)) {
+			// apply set rejection information on commands.
+			return false;
+		}
+
+		Repository repo = refdb.getRepository();
+		try (ObjectInserter ins = repo.newObjectInserter()) {
+			CommitBuilder b = new CommitBuilder();
+			b.setTreeId(tree.writeTree(ins));
+			if (parentTreeId.equals(b.getTreeId())) {
+				for (Command c : todo) {
+					c.setResult(OK);
+				}
+				return true;
+			}
+			if (!parentCommitId.equals(ObjectId.zeroId())) {
+				b.setParentId(parentCommitId);
+			}
+
+			author = getRefLogIdent();
+			if (author == null) {
+				author = new PersonIdent(repo);
+			}
+			b.setAuthor(author);
+			b.setCommitter(author);
+			b.setMessage(getRefLogMessage());
+			newCommitId = ins.insert(b);
+			ins.flush();
+		}
+		return true;
+	}
+
+	private void commit(RevWalk rw, List<Command> todo) throws IOException {
+		ReceiveCommand commit = new ReceiveCommand(
+				parentCommitId, newCommitId,
+				refdb.getTxnCommitted());
+		updateBootstrap(rw, commit);
+
+		if (commit.getResult() == OK) {
+			for (Command c : todo) {
+				c.setResult(OK);
+			}
+		} else {
+			reject(todo, commit.getResult().name());
+		}
+	}
+
+	private void updateBootstrap(RevWalk rw, ReceiveCommand commit)
+			throws IOException {
+		BatchRefUpdate u = refdb.getBootstrap().newBatchUpdate();
+		u.setAllowNonFastForwards(true);
+		u.setPushCertificate(getPushCertificate());
+		if (isRefLogDisabled()) {
+			u.disableRefLog();
+		} else {
+			u.setRefLogIdent(author);
+			u.setRefLogMessage(getRefLogMessage(), false);
+		}
+		u.addCommand(commit);
+		u.execute(rw, NullProgressMonitor.INSTANCE);
+	}
+
+	private static void reject(List<Command> todo, String msg) {
+		for (Command c : todo) {
+			if (c.getResult() == NOT_ATTEMPTED) {
+				c.setResult(REJECTED_OTHER_REASON, msg);
+				msg = JGitText.get().transactionAborted;
+			}
+		}
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeDatabase.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeDatabase.java
new file mode 100644
index 0000000000..983216e304
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeDatabase.java
@@ -0,0 +1,314 @@
+/*
+ * 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.Ref.Storage.LOOSE;
+import static org.eclipse.jgit.lib.Ref.Storage.PACKED;
+
+import java.io.IOException;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.eclipse.jgit.annotations.Nullable;
+import org.eclipse.jgit.lib.BatchRefUpdate;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectIdRef;
+import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.Ref.Storage;
+import org.eclipse.jgit.lib.RefDatabase;
+import org.eclipse.jgit.lib.RefRename;
+import org.eclipse.jgit.lib.RefUpdate;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.lib.SymbolicRef;
+import org.eclipse.jgit.revwalk.RevObject;
+import org.eclipse.jgit.revwalk.RevTag;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.eclipse.jgit.util.RefList;
+import org.eclipse.jgit.util.RefMap;
+
+/**
+ * Reference database backed by a {@link RefTree}.
+ * <p>
+ * The storage for RefTreeDatabase has two parts. The main part is a native Git
+ * tree object stored under the {@code refs/txn} namespace. To avoid cycles,
+ * references to {@code refs/txn} are not stored in that tree object, but
+ * instead in a "bootstrap" layer, which is a separate {@link RefDatabase} such
+ * as {@link org.eclipse.jgit.internal.storage.file.RefDirectory} using local
+ * reference files inside of {@code $GIT_DIR/refs}.
+ */
+public class RefTreeDatabase extends RefDatabase {
+	private final Repository repo;
+	private final RefDatabase bootstrap;
+	private final String txnCommitted;
+
+	@Nullable
+	private final String txnNamespace;
+	private volatile Scanner.Result refs;
+
+	/**
+	 * Create a RefTreeDb for a repository.
+	 *
+	 * @param repo
+	 *            the repository using references in this database.
+	 * @param bootstrap
+	 *            bootstrap reference database storing the references that
+	 *            anchor the {@link RefTree}.
+	 * @param txnCommitted
+	 *            name of the bootstrap reference holding the committed RefTree.
+	 */
+	public RefTreeDatabase(Repository repo, RefDatabase bootstrap,
+			String txnCommitted) {
+		this.repo = repo;
+		this.bootstrap = bootstrap;
+		this.txnNamespace = initNamespace(txnCommitted);
+		this.txnCommitted = txnCommitted;
+	}
+
+	private static String initNamespace(String committed) {
+		int s = committed.lastIndexOf('/');
+		if (s < 0) {
+			return null;
+		}
+		return committed.substring(0, s + 1); // Keep trailing '/'.
+	}
+
+	Repository getRepository() {
+		return repo;
+	}
+
+	/**
+	 * @return the bootstrap reference database, which must be used to access
+	 *         {@link #getTxnCommitted()}, {@link #getTxnNamespace()}.
+	 */
+	public RefDatabase getBootstrap() {
+		return bootstrap;
+	}
+
+	/** @return name of bootstrap reference anchoring committed RefTree. */
+	public String getTxnCommitted() {
+		return txnCommitted;
+	}
+
+	/**
+	 * @return namespace used by bootstrap layer, e.g. {@code refs/txn/}.
+	 *         Always ends in {@code '/'}.
+	 */
+	@Nullable
+	public String getTxnNamespace() {
+		return txnNamespace;
+	}
+
+	@Override
+	public void create() throws IOException {
+		bootstrap.create();
+	}
+
+	@Override
+	public boolean performsAtomicTransactions() {
+		return true;
+	}
+
+	@Override
+	public void refresh() {
+		bootstrap.refresh();
+	}
+
+	@Override
+	public void close() {
+		refs = null;
+		bootstrap.close();
+	}
+
+	@Override
+	public Ref getRef(String name) throws IOException {
+		return findRef(getRefs(ALL), name);
+	}
+
+	@Override
+	public Ref exactRef(String name) throws IOException {
+		if (conflictsWithBootstrap(name)) {
+			return null;
+		}
+
+		boolean partial = false;
+		Ref src = bootstrap.exactRef(txnCommitted);
+		Scanner.Result c = refs;
+		if (c == null || !c.refTreeId.equals(idOf(src))) {
+			c = Scanner.scanRefTree(repo, src, prefixOf(name), false);
+			partial = true;
+		}
+
+		Ref r = c.all.get(name);
+		if (r != null && r.isSymbolic()) {
+			r = c.sym.get(name);
+			if (partial && r.getObjectId() == null) {
+				// Attempting exactRef("HEAD") with partial scan will leave
+				// an unresolved symref as its target e.g. refs/heads/master
+				// was not read by the partial scan. Scan everything instead.
+				return getRefs(ALL).get(name);
+			}
+		}
+		return r;
+	}
+
+	private static String prefixOf(String name) {
+		int s = name.lastIndexOf('/');
+		if (s >= 0) {
+			return name.substring(0, s);
+		}
+		return ""; //$NON-NLS-1$
+	}
+
+	@Override
+	public Map<String, Ref> getRefs(String prefix) throws IOException {
+		if (!prefix.isEmpty() && prefix.charAt(prefix.length() - 1) != '/') {
+			return new HashMap<>(0);
+		}
+
+		Ref src = bootstrap.exactRef(txnCommitted);
+		Scanner.Result c = refs;
+		if (c == null || !c.refTreeId.equals(idOf(src))) {
+			c = Scanner.scanRefTree(repo, src, prefix, true);
+			if (prefix.isEmpty()) {
+				refs = c;
+			}
+		}
+		return new RefMap(prefix, RefList.<Ref> emptyList(), c.all, c.sym);
+	}
+
+	private static ObjectId idOf(@Nullable Ref src) {
+		return src != null && src.getObjectId() != null
+				? src.getObjectId()
+				: ObjectId.zeroId();
+	}
+
+	@Override
+	public List<Ref> getAdditionalRefs() throws IOException {
+		return Collections.emptyList();
+	}
+
+	@Override
+	public Ref peel(Ref ref) throws IOException {
+		Ref i = ref.getLeaf();
+		ObjectId id = i.getObjectId();
+		if (i.isPeeled() || id == null) {
+			return ref;
+		}
+		try (RevWalk rw = new RevWalk(repo)) {
+			RevObject obj = rw.parseAny(id);
+			if (obj instanceof RevTag) {
+				ObjectId p = rw.peel(obj).copy();
+				i = new ObjectIdRef.PeeledTag(PACKED, i.getName(), id, p);
+			} else {
+				i = new ObjectIdRef.PeeledNonTag(PACKED, i.getName(), id);
+			}
+		}
+		return recreate(ref, i);
+	}
+
+	private static Ref recreate(Ref old, Ref leaf) {
+		if (old.isSymbolic()) {
+			Ref dst = recreate(old.getTarget(), leaf);
+			return new SymbolicRef(old.getName(), dst);
+		}
+		return leaf;
+	}
+
+	@Override
+	public boolean isNameConflicting(String name) throws IOException {
+		return conflictsWithBootstrap(name)
+				|| !getConflictingNames(name).isEmpty();
+	}
+
+	@Override
+	public BatchRefUpdate newBatchUpdate() {
+		return new RefTreeBatch(this);
+	}
+
+	@Override
+	public RefUpdate newUpdate(String name, boolean detach) throws IOException {
+		if (conflictsWithBootstrap(name)) {
+			return new AlwaysFailUpdate(this, name);
+		}
+
+		Ref r = exactRef(name);
+		if (r == null) {
+			r = new ObjectIdRef.Unpeeled(Storage.NEW, name, null);
+		}
+
+		boolean detaching = detach && r.isSymbolic();
+		if (detaching) {
+			r = new ObjectIdRef.Unpeeled(LOOSE, name, r.getObjectId());
+		}
+
+		RefTreeUpdate u = new RefTreeUpdate(this, r);
+		if (detaching) {
+			u.setDetachingSymbolicRef();
+		}
+		return u;
+	}
+
+	@Override
+	public RefRename newRename(String fromName, String toName)
+			throws IOException {
+		RefUpdate from = newUpdate(fromName, true);
+		RefUpdate to = newUpdate(toName, true);
+		return new RefTreeRename(this, from, to);
+	}
+
+	boolean conflictsWithBootstrap(String name) {
+		if (txnNamespace != null && name.startsWith(txnNamespace)) {
+			return true;
+		} else if (txnCommitted.equals(name)) {
+			return true;
+		} else if (name.length() > txnCommitted.length()
+				&& name.charAt(txnCommitted.length()) == '/'
+				&& name.startsWith(txnCommitted)) {
+			return true;
+		}
+		return false;
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeRename.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeRename.java
new file mode 100644
index 0000000000..5fd7ecdd79
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeRename.java
@@ -0,0 +1,121 @@
+/*
+ * 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.RefUpdate.Result.REJECTED;
+import static org.eclipse.jgit.lib.RefUpdate.Result.RENAMED;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectIdRef;
+import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.RefRename;
+import org.eclipse.jgit.lib.RefUpdate;
+import org.eclipse.jgit.lib.RefUpdate.Result;
+import org.eclipse.jgit.lib.SymbolicRef;
+import org.eclipse.jgit.revwalk.RevWalk;
+
+/** Single reference rename to {@link RefTreeDatabase}. */
+class RefTreeRename extends RefRename {
+	private final RefTreeDatabase refdb;
+
+	RefTreeRename(RefTreeDatabase refdb, RefUpdate src, RefUpdate dst) {
+		super(src, dst);
+		this.refdb = refdb;
+	}
+
+	@Override
+	protected Result doRename() throws IOException {
+		try (RevWalk rw = new RevWalk(refdb.getRepository())) {
+			RefTreeBatch batch = new RefTreeBatch(refdb);
+			batch.setRefLogIdent(getRefLogIdent());
+			batch.setRefLogMessage(getRefLogMessage(), false);
+			batch.init(rw);
+
+			Ref head = batch.exactRef(rw.getObjectReader(), HEAD);
+			Ref oldRef = batch.exactRef(rw.getObjectReader(), source.getName());
+			if (oldRef == null) {
+				return REJECTED;
+			}
+
+			Ref newRef = asNew(oldRef);
+			List<Command> mv = new ArrayList<>(3);
+			mv.add(new Command(oldRef, null));
+			mv.add(new Command(null, newRef));
+			if (head != null && head.isSymbolic()
+					&& head.getTarget().getName().equals(oldRef.getName())) {
+				mv.add(new Command(
+					head,
+					new SymbolicRef(head.getName(), newRef)));
+			}
+			batch.execute(rw, mv);
+			return RefTreeUpdate.translate(mv.get(1).getResult(), RENAMED);
+		}
+	}
+
+	private Ref asNew(Ref src) {
+		String name = destination.getName();
+		if (src.isSymbolic()) {
+			return new SymbolicRef(name, src.getTarget());
+		}
+
+		ObjectId peeled = src.getPeeledObjectId();
+		if (peeled != null) {
+			return new ObjectIdRef.PeeledTag(
+					src.getStorage(),
+					name,
+					src.getObjectId(),
+					peeled);
+		}
+
+		return new ObjectIdRef.PeeledNonTag(
+				src.getStorage(),
+				name,
+				src.getObjectId());
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeUpdate.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeUpdate.java
new file mode 100644
index 0000000000..8829c1156a
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/RefTreeUpdate.java
@@ -0,0 +1,176 @@
+/*
+ * 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.Ref.Storage.LOOSE;
+import static org.eclipse.jgit.lib.Ref.Storage.NEW;
+
+import java.io.IOException;
+import java.util.Collections;
+
+import org.eclipse.jgit.annotations.Nullable;
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectIdRef;
+import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.RefDatabase;
+import org.eclipse.jgit.lib.RefUpdate;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.lib.SymbolicRef;
+import org.eclipse.jgit.revwalk.RevObject;
+import org.eclipse.jgit.revwalk.RevTag;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.eclipse.jgit.transport.ReceiveCommand;
+
+/** Single reference update to {@link RefTreeDatabase}. */
+class RefTreeUpdate extends RefUpdate {
+	private final RefTreeDatabase refdb;
+	private RevWalk rw;
+	private RefTreeBatch batch;
+	private Ref oldRef;
+
+	RefTreeUpdate(RefTreeDatabase refdb, Ref ref) {
+		super(ref);
+		this.refdb = refdb;
+		setCheckConflicting(false); // Done automatically by doUpdate.
+	}
+
+	@Override
+	protected RefDatabase getRefDatabase() {
+		return refdb;
+	}
+
+	@Override
+	protected Repository getRepository() {
+		return refdb.getRepository();
+	}
+
+	@Override
+	protected boolean tryLock(boolean deref) throws IOException {
+		rw = new RevWalk(getRepository());
+		batch = new RefTreeBatch(refdb);
+		batch.init(rw);
+		oldRef = batch.exactRef(rw.getObjectReader(), getName());
+		if (oldRef != null && oldRef.getObjectId() != null) {
+			setOldObjectId(oldRef.getObjectId());
+		} else if (oldRef == null && getExpectedOldObjectId() != null) {
+			setOldObjectId(ObjectId.zeroId());
+		}
+		return true;
+	}
+
+	@Override
+	protected void unlock() {
+		batch = null;
+		if (rw != null) {
+			rw.close();
+			rw = null;
+		}
+	}
+
+	@Override
+	protected Result doUpdate(Result desiredResult) throws IOException {
+		return run(newRef(getName(), getNewObjectId()), desiredResult);
+	}
+
+	private Ref newRef(String name, ObjectId id)
+			throws MissingObjectException, IOException {
+		RevObject o = rw.parseAny(id);
+		if (o instanceof RevTag) {
+			RevObject p = rw.peel(o);
+			return new ObjectIdRef.PeeledTag(LOOSE, name, id, p.copy());
+		}
+		return new ObjectIdRef.PeeledNonTag(LOOSE, name, id);
+	}
+
+	@Override
+	protected Result doDelete(Result desiredResult) throws IOException {
+		return run(null, desiredResult);
+	}
+
+	@Override
+	protected Result doLink(String target) throws IOException {
+		Ref dst = new ObjectIdRef.Unpeeled(NEW, target, null);
+		SymbolicRef n = new SymbolicRef(getName(), dst);
+		Result desiredResult = getRef().getStorage() == NEW
+			? Result.NEW
+			: Result.FORCED;
+		return run(n, desiredResult);
+	}
+
+	private Result run(@Nullable Ref newRef, Result desiredResult)
+			throws IOException {
+		Command c = new Command(oldRef, newRef);
+		batch.setRefLogIdent(getRefLogIdent());
+		batch.setRefLogMessage(getRefLogMessage(), isRefLogIncludingResult());
+		batch.execute(rw, Collections.singletonList(c));
+		return translate(c.getResult(), desiredResult);
+	}
+
+	static Result translate(ReceiveCommand.Result r, Result desiredResult) {
+		switch (r) {
+		case OK:
+			return desiredResult;
+
+		case LOCK_FAILURE:
+			return Result.LOCK_FAILURE;
+
+		case NOT_ATTEMPTED:
+			return Result.NOT_ATTEMPTED;
+
+		case REJECTED_MISSING_OBJECT:
+			return Result.IO_FAILURE;
+
+		case REJECTED_CURRENT_BRANCH:
+			return Result.REJECTED_CURRENT_BRANCH;
+
+		case REJECTED_OTHER_REASON:
+		case REJECTED_NOCREATE:
+		case REJECTED_NODELETE:
+		case REJECTED_NONFASTFORWARD:
+		default:
+			return Result.REJECTED;
+		}
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/Scanner.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/Scanner.java
new file mode 100644
index 0000000000..b3aeed0df3
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftree/Scanner.java
@@ -0,0 +1,286 @@
+/*
+ * 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.RefDatabase.MAX_SYMBOLIC_REF_DEPTH;
+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.TYPE_GITLINK;
+import static org.eclipse.jgit.lib.FileMode.TYPE_SYMLINK;
+import static org.eclipse.jgit.lib.FileMode.TYPE_TREE;
+import static org.eclipse.jgit.lib.Ref.Storage.NEW;
+import static org.eclipse.jgit.lib.Ref.Storage.PACKED;
+
+import java.io.IOException;
+
+import org.eclipse.jgit.annotations.Nullable;
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectIdRef;
+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.revwalk.RevWalk;
+import org.eclipse.jgit.treewalk.AbstractTreeIterator;
+import org.eclipse.jgit.treewalk.CanonicalTreeParser;
+import org.eclipse.jgit.treewalk.TreeWalk;
+import org.eclipse.jgit.util.Paths;
+import org.eclipse.jgit.util.RawParseUtils;
+import org.eclipse.jgit.util.RefList;
+
+/** A tree parser that extracts references from a {@link RefTree}. */
+class Scanner {
+	private static final int MAX_SYMLINK_BYTES = 10 << 10;
+	private static final byte[] BINARY_R_REFS = encode(R_REFS);
+	private static final byte[] REFS_DOT_DOT = encode("refs/.."); //$NON-NLS-1$
+
+	static class Result {
+		final ObjectId refTreeId;
+		final RefList<Ref> all;
+		final RefList<Ref> sym;
+
+		Result(ObjectId id, RefList<Ref> all, RefList<Ref> sym) {
+			this.refTreeId = id;
+			this.all = all;
+			this.sym = sym;
+		}
+	}
+
+	/**
+	 * Scan a {@link RefTree} and parse entries into {@link Ref} instances.
+	 *
+	 * @param repo
+	 *            source repository containing the commit and tree objects that
+	 *            make up the RefTree.
+	 * @param src
+	 *            bootstrap reference such as {@code refs/txn/committed} to read
+	 *            the reference tree tip from. The current ObjectId will be
+	 *            included in {@link Result#refTreeId}.
+	 * @param prefix
+	 *            if non-empty a reference prefix to scan only a subdirectory.
+	 *            For example {@code prefix = "refs/heads/"} will limit the scan
+	 *            to only the {@code "heads"} directory of the RefTree, avoiding
+	 *            other directories like {@code "tags"}. Empty string reads all
+	 *            entries in the RefTree.
+	 * @param recursive
+	 *            if true recurse into subdirectories of the reference tree;
+	 *            false to read only one level. Callers may use false during an
+	 *            implementation of {@code exactRef(String)} where only one
+	 *            reference is needed out of a specific subtree.
+	 * @return sorted list of references after parsing.
+	 * @throws IOException
+	 *             tree cannot be accessed from the repository.
+	 */
+	static Result scanRefTree(Repository repo, @Nullable Ref src, String prefix,
+			boolean recursive) throws IOException {
+		RefList.Builder<Ref> all = new RefList.Builder<>();
+		RefList.Builder<Ref> sym = new RefList.Builder<>();
+
+		ObjectId srcId;
+		if (src != null && src.getObjectId() != null) {
+			try (ObjectReader reader = repo.newObjectReader()) {
+				srcId = src.getObjectId();
+				scan(reader, srcId, prefix, recursive, all, sym);
+			}
+		} else {
+			srcId = ObjectId.zeroId();
+		}
+
+		RefList<Ref> aList = all.toRefList();
+		for (int idx = 0; idx < sym.size();) {
+			Ref s = sym.get(idx);
+			Ref r = resolve(s, 0, aList);
+			if (r != null) {
+				sym.set(idx++, r);
+			} else {
+				// Remove broken symbolic reference, they don't exist.
+				sym.remove(idx);
+				int rm = aList.find(s.getName());
+				if (0 <= rm) {
+					aList = aList.remove(rm);
+				}
+			}
+		}
+		return new Result(srcId, aList, sym.toRefList());
+	}
+
+	private static void scan(ObjectReader reader, AnyObjectId srcId,
+			String prefix, boolean recursive,
+			RefList.Builder<Ref> all, RefList.Builder<Ref> sym)
+					throws IncorrectObjectTypeException, IOException {
+		CanonicalTreeParser p = createParserAtPath(reader, srcId, prefix);
+		if (p == null) {
+			return;
+		}
+
+		while (!p.eof()) {
+			int mode = p.getEntryRawMode();
+			if (mode == TYPE_TREE) {
+				if (recursive) {
+					p = p.createSubtreeIterator(reader);
+				} else {
+					p = p.next();
+				}
+				continue;
+			}
+
+			if (!curElementHasPeelSuffix(p)) {
+				Ref r = toRef(reader, mode, p);
+				if (r != null) {
+					all.add(r);
+					if (r.isSymbolic()) {
+						sym.add(r);
+					}
+				}
+			} else if (mode == TYPE_GITLINK) {
+				peel(all, p);
+			}
+			p = p.next();
+		}
+	}
+
+	private static CanonicalTreeParser createParserAtPath(ObjectReader reader,
+			AnyObjectId srcId, String prefix) throws IOException {
+		ObjectId root = toTree(reader, srcId);
+		if (prefix.isEmpty()) {
+			return new CanonicalTreeParser(BINARY_R_REFS, reader, root);
+		}
+
+		String dir = RefTree.refPath(Paths.stripTrailingSeparator(prefix));
+		TreeWalk tw = TreeWalk.forPath(reader, dir, root);
+		if (tw == null || !tw.isSubtree()) {
+			return null;
+		}
+
+		ObjectId id = tw.getObjectId(0);
+		return new CanonicalTreeParser(encode(prefix), reader, id);
+	}
+
+	private static Ref resolve(Ref ref, int depth, RefList<Ref> refs)
+			throws IOException {
+		if (!ref.isSymbolic()) {
+			return ref;
+		} else if (MAX_SYMBOLIC_REF_DEPTH <= depth) {
+			return null;
+		}
+
+		Ref r = refs.get(ref.getTarget().getName());
+		if (r == null) {
+			return ref;
+		}
+
+		Ref dst = resolve(r, depth + 1, refs);
+		if (dst == null) {
+			return null;
+		}
+		return new SymbolicRef(ref.getName(), dst);
+	}
+
+	@SuppressWarnings("resource")
+	private static RevTree toTree(ObjectReader reader, AnyObjectId id)
+			throws IOException {
+		return new RevWalk(reader).parseTree(id);
+	}
+
+	private static boolean curElementHasPeelSuffix(AbstractTreeIterator itr) {
+		int n = itr.getEntryPathLength();
+		byte[] c = itr.getEntryPathBuffer();
+		return n > 3 && c[n - 3] == '^' && c[n - 2] == '{' && c[n - 1] == '}';
+	}
+
+	private static void peel(RefList.Builder<Ref> all, CanonicalTreeParser p) {
+		String name = refName(p, true);
+		for (int idx = all.size() - 1; 0 <= idx; idx--) {
+			Ref r = all.get(idx);
+			int cmp = r.getName().compareTo(name);
+			if (cmp == 0) {
+				all.set(idx, new ObjectIdRef.PeeledTag(PACKED, r.getName(),
+						r.getObjectId(), p.getEntryObjectId()));
+				break;
+			} else if (cmp < 0) {
+				// Stray peeled name without matching base name; skip entry.
+				break;
+			}
+		}
+	}
+
+	private static Ref toRef(ObjectReader reader, int mode,
+			CanonicalTreeParser p) throws IOException {
+		if (mode == TYPE_GITLINK) {
+			String name = refName(p, false);
+			ObjectId id = p.getEntryObjectId();
+			return new ObjectIdRef.PeeledNonTag(PACKED, name, id);
+
+		} else if (mode == TYPE_SYMLINK) {
+			ObjectId id = p.getEntryObjectId();
+			byte[] bin = reader.open(id, OBJ_BLOB)
+					.getCachedBytes(MAX_SYMLINK_BYTES);
+			String dst = RawParseUtils.decode(bin);
+			Ref trg = new ObjectIdRef.Unpeeled(NEW, dst, null);
+			String name = refName(p, false);
+			return new SymbolicRef(name, trg);
+		}
+		return null;
+	}
+
+	private static String refName(CanonicalTreeParser p, boolean peel) {
+		byte[] buf = p.getEntryPathBuffer();
+		int len = p.getEntryPathLength();
+		if (peel) {
+			len -= 3;
+		}
+		int ptr = 0;
+		if (RawParseUtils.match(buf, ptr, REFS_DOT_DOT) > 0) {
+			ptr = 7;
+		}
+		return RawParseUtils.decode(buf, ptr, len);
+	}
+
+	private Scanner() {
+	}
+}