From b71ba69410db5e50dd10c5c40e96699c9de7e5e8 Mon Sep 17 00:00:00 2001 From: Shawn Pearce Date: Mon, 28 Dec 2015 11:43:07 -0800 Subject: [PATCH] DirCacheEditor: Replace file-with-tree and tree-with-file If a PathEdit tries to store a file where a subtree was, or a subtree where a file was, replace the entry in the DirCache with the new name(s). This supports switching between file and tree entry types using a DirCacheEditor. Add new unit tests to cover the conditions where these can happen. Change-Id: Ie843d9388825f9e3d918a5666aa04e47cd6306e7 --- .../jgit/dircache/DirCachePathEditTest.java | 58 +++++++ .../jgit/lib/DirCacheCheckoutTest.java | 6 +- .../jgit/dircache/BaseDirCacheEditor.java | 24 +++ .../org/eclipse/jgit/dircache/DirCache.java | 7 +- .../eclipse/jgit/dircache/DirCacheEditor.java | 162 +++++++++++++++++- .../eclipse/jgit/dircache/DirCacheEntry.java | 2 +- 6 files changed, 246 insertions(+), 13 deletions(-) diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCachePathEditTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCachePathEditTest.java index 63ec85861d..3988f6a4c4 100644 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCachePathEditTest.java +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCachePathEditTest.java @@ -154,6 +154,64 @@ public class DirCachePathEditTest { assertEquals(DirCacheEntry.STAGE_3, entries.get(2).getStage()); } + @Test + public void testFileReplacesTree() throws Exception { + DirCache dc = DirCache.newInCore(); + DirCacheEditor editor = dc.editor(); + editor.add(new AddEdit("a")); + editor.add(new AddEdit("b/c")); + editor.add(new AddEdit("b/d")); + editor.add(new AddEdit("e")); + editor.finish(); + + editor = dc.editor(); + editor.add(new AddEdit("b")); + editor.finish(); + + assertEquals(3, dc.getEntryCount()); + assertEquals("a", dc.getEntry(0).getPathString()); + assertEquals("b", dc.getEntry(1).getPathString()); + assertEquals("e", dc.getEntry(2).getPathString()); + + dc.clear(); + editor = dc.editor(); + editor.add(new AddEdit("A.c")); + editor.add(new AddEdit("A/c")); + editor.add(new AddEdit("A0c")); + editor.finish(); + + editor = dc.editor(); + editor.add(new AddEdit("A")); + editor.finish(); + assertEquals(3, dc.getEntryCount()); + assertEquals("A", dc.getEntry(0).getPathString()); + assertEquals("A.c", dc.getEntry(1).getPathString()); + assertEquals("A0c", dc.getEntry(2).getPathString()); + } + + @Test + public void testTreeReplacesFile() throws Exception { + DirCache dc = DirCache.newInCore(); + DirCacheEditor editor = dc.editor(); + editor.add(new AddEdit("a")); + editor.add(new AddEdit("ab")); + editor.add(new AddEdit("b")); + editor.add(new AddEdit("e")); + editor.finish(); + + editor = dc.editor(); + editor.add(new AddEdit("b/c/d/f")); + editor.add(new AddEdit("b/g/h/i")); + editor.finish(); + + assertEquals(5, dc.getEntryCount()); + assertEquals("a", dc.getEntry(0).getPathString()); + assertEquals("ab", dc.getEntry(1).getPathString()); + assertEquals("b/c/d/f", dc.getEntry(2).getPathString()); + assertEquals("b/g/h/i", dc.getEntry(3).getPathString()); + assertEquals("e", dc.getEntry(4).getPathString()); + } + private static DirCacheEntry createEntry(String path, int stage) { DirCacheEntry entry = new DirCacheEntry(path, stage); entry.setFileMode(FileMode.REGULAR_FILE); diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/lib/DirCacheCheckoutTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/lib/DirCacheCheckoutTest.java index d768e0fa0b..92901f826b 100644 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/lib/DirCacheCheckoutTest.java +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/lib/DirCacheCheckoutTest.java @@ -1084,7 +1084,7 @@ public class DirCacheCheckoutTest extends RepositoryTestCase { assertWorkDir(mkmap(linkName, "a", fname, "a")); Status st = git.status().call(); - assertFalse(st.isClean()); + assertTrue(st.isClean()); } @Test @@ -1213,9 +1213,7 @@ public class DirCacheCheckoutTest extends RepositoryTestCase { assertWorkDir(mkmap(fname, "a")); Status st = git.status().call(); - assertFalse(st.isClean()); - assertEquals(1, st.getAdded().size()); - assertTrue(st.getAdded().contains(fname + "/dir/file1")); + assertTrue(st.isClean()); } @Test diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/BaseDirCacheEditor.java b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/BaseDirCacheEditor.java index 70f80aeb7a..c5c1b0d775 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/BaseDirCacheEditor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/BaseDirCacheEditor.java @@ -44,6 +44,8 @@ package org.eclipse.jgit.dircache; +import static org.eclipse.jgit.lib.FileMode.TREE; + import java.io.IOException; /** @@ -176,6 +178,28 @@ abstract class BaseDirCacheEditor { cache.replace(entries, entryCnt); } + static int pathCompare(byte[] aPath, int aPos, int aEnd, int aMode, + byte[] bPath, int bPos, int bEnd, int bMode) { + while (aPos < aEnd && bPos < bEnd) { + int cmp = (aPath[aPos++] & 0xff) - (bPath[bPos++] & 0xff); + if (cmp != 0) { + return cmp; + } + } + + if (aPos < aEnd) { + return (aPath[aPos] & 0xff) - lastPathChar(bMode); + } + if (bPos < bEnd) { + return lastPathChar(aMode) - (bPath[bPos] & 0xff); + } + return 0; + } + + private static int lastPathChar(int mode) { + return TREE.equals(mode) ? '/' : '\0'; + } + /** * Finish, write, commit this change, and release the index lock. *

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCache.java b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCache.java index fa0339544f..ecdfe823a8 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCache.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCache.java @@ -800,8 +800,11 @@ public class DirCache { * information. If < 0 the entry does not exist in the index. * @since 3.4 */ - public int findEntry(final byte[] p, final int pLen) { - int low = 0; + public int findEntry(byte[] p, int pLen) { + return findEntry(0, p, pLen); + } + + int findEntry(int low, byte[] p, int pLen) { int high = entryCnt; while (low < high) { int mid = (low + high) >>> 1; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java index 932ef94db0..889e194224 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java @@ -44,6 +44,10 @@ 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; @@ -72,11 +76,12 @@ public class DirCacheEditor extends BaseDirCacheEditor { public int compare(final PathEdit o1, final PathEdit o2) { final byte[] a = o1.path; final byte[] b = o2.path; - return DirCache.cmp(a, a.length, b, b.length); + return cmp(a, a.length, b, b.length); } }; private final List edits; + private int editIdx; /** * Construct a new editor. @@ -126,37 +131,44 @@ public class DirCacheEditor extends BaseDirCacheEditor { private void applyEdits() { Collections.sort(edits, EDIT_CMP); + editIdx = 0; final int maxIdx = cache.getEntryCount(); int lastIdx = 0; - for (final PathEdit e : edits) { - int eIdx = cache.findEntry(e.path, e.path.length); + 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); - lastIdx = missing ? eIdx : cache.nextEntry(eIdx); - if (e instanceof DeletePath) + 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) { - final DirCacheEntry ent = new DirCacheEntry(e.path); + 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); @@ -170,6 +182,102 @@ public class DirCacheEditor extends BaseDirCacheEditor { 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 (pathCompare(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. *

@@ -181,6 +289,7 @@ public class DirCacheEditor extends BaseDirCacheEditor { */ public abstract static class PathEdit { final byte[] path; + boolean replace = true; /** * Create a new update command by path name. @@ -192,6 +301,10 @@ public class DirCacheEditor extends BaseDirCacheEditor { path = Constants.encode(entryPath); } + PathEdit(byte[] path) { + this.path = path; + } + /** * Create a new update command for an existing entry instance. * @@ -203,6 +316,22 @@ public class DirCacheEditor extends BaseDirCacheEditor { path = ent.path; } + /** + * Configure if a file can replace a directory (or vice versa). + *

+ * 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. *

@@ -214,6 +343,12 @@ public class DirCacheEditor extends BaseDirCacheEditor { * 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 + ']'; + } } /** @@ -281,6 +416,21 @@ public class DirCacheEditor extends BaseDirCacheEditor { : 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; + } + public void apply(final DirCacheEntry ent) { throw new UnsupportedOperationException(JGitText.get().noApplyInDelete); } diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEntry.java b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEntry.java index c8bc0960f4..5df9e0b4df 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEntry.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEntry.java @@ -745,7 +745,7 @@ public class DirCacheEntry { } } - private static String toString(final byte[] path) { + static String toString(final byte[] path) { return Constants.CHARSET.decode(ByteBuffer.wrap(path)).toString(); } -- 2.39.5