diff options
Diffstat (limited to 'org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java')
| -rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java | 298 |
1 files changed, 221 insertions, 77 deletions
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 13885d370c..b1f4e7db21 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java @@ -1,49 +1,20 @@ /* - * Copyright (C) 2008-2009, Google Inc. - * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> - * and other copyright owners as documented in the project's IP log. + * Copyright (C) 2008, 2009, Google Inc. + * Copyright (C) 2008, 2020 Shawn O. Pearce <spearce@spearce.org> and others * - * 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 + * This program and the accompanying materials are made available under the + * terms of the Eclipse Distribution License v. 1.0 which is available at + * https://www.eclipse.org/org/documents/edl-v10.php. * - * 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. + * SPDX-License-Identifier: BSD-3-Clause */ 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; @@ -53,30 +24,32 @@ import java.util.List; import org.eclipse.jgit.internal.JGitText; import org.eclipse.jgit.lib.Constants; +import org.eclipse.jgit.util.Paths; /** - * Updates a {@link DirCache} by supplying discrete edit commands. + * Updates a {@link org.eclipse.jgit.dircache.DirCache} by supplying discrete + * edit commands. * <p> - * An editor updates a DirCache by taking a list of {@link PathEdit} commands - * and executing them against the entries of the destination cache to produce a - * new cache. This edit style allows applications to insert a few commands and - * then have the editor compute the proper entry indexes necessary to perform an + * An editor updates a DirCache by taking a list of + * {@link org.eclipse.jgit.dircache.DirCacheEditor.PathEdit} commands and + * executing them against the entries of the destination cache to produce a new + * cache. This edit style allows applications to insert a few commands and then + * have the editor compute the proper entry indexes necessary to perform an * efficient in-order update of the index records. This can be easier to use - * than {@link DirCacheBuilder}. - * <p> + * than {@link org.eclipse.jgit.dircache.DirCacheBuilder}. * * @see DirCacheBuilder */ public class DirCacheEditor extends BaseDirCacheEditor { - private static final Comparator<PathEdit> EDIT_CMP = new Comparator<PathEdit>() { - 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); - } + private static final Comparator<PathEdit> EDIT_CMP = (PathEdit o1, + PathEdit o2) -> { + final byte[] a = o1.path; + final byte[] b = o2.path; + return cmp(a, a.length, b, b.length); }; private final List<PathEdit> edits; + private int editIdx; /** * Construct a new editor. @@ -87,9 +60,9 @@ public class DirCacheEditor extends BaseDirCacheEditor { * estimated number of entries the editor will have upon * completion. This sizes the initial entry table. */ - protected DirCacheEditor(final DirCache dc, final int ecnt) { + protected DirCacheEditor(DirCache dc, int ecnt) { super(dc, ecnt); - edits = new ArrayList<PathEdit>(); + edits = new ArrayList<>(); } /** @@ -102,7 +75,7 @@ public class DirCacheEditor extends BaseDirCacheEditor { * @param edit * another edit command. */ - public void add(final PathEdit edit) { + public void add(PathEdit edit) { edits.add(edit); } @@ -117,6 +90,7 @@ public class DirCacheEditor extends BaseDirCacheEditor { return super.commit(); } + @Override public void finish() { if (!edits.isEmpty()) { applyEdits(); @@ -126,37 +100,64 @@ 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())); + 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) - for (int i = eIdx; i < lastIdx; i++) { - final DirCacheEntry ent = cache.getEntry(i); + lastIdx = cache.nextEntry(eIdx); + if (lastIdx > eIdx + 1) { + // Apply to all entries of the current path (different + // stages). If any apply() resets the stage to STAGE_0, take + // only that entry and omit all others. + DirCacheEntry[] tmp = new DirCacheEntry[lastIdx - eIdx]; + int n = 0; + for (int i = eIdx; i < lastIdx; i++) { + DirCacheEntry ent = cache.getEntry(i); + e.apply(ent); + if (ent.getStage() == DirCacheEntry.STAGE_0) { + fastAdd(ent); + n = 0; + break; + } + tmp[n++] = ent; + } + for (int i = 0; i < n; i++) { + fastAdd(tmp[i]); + } + } else { + DirCacheEntry ent = cache.getEntry(eIdx); e.apply(ent); fastAdd(ent); } @@ -168,6 +169,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 (Paths.compare(next.path, 0, next.path.length, 0, + entPath, 0, entLen, TYPE_TREE) < 0) { + // Next DirCacheEntry sorts before new entry as tree. Defer a + // DeleteTree command to delete any entries if they exist. This + // case only happens for A, A.c, A/c type of conflicts (rare). + insertEdit(new DeleteTree(entPath)); + return eIdx; + } + + // Next entry may be contained by the entry-as-tree, skip if so. + while (eIdx < maxEnt && inDir(cache.getEntry(eIdx), entPath, entLen)) { + eIdx++; + } + return eIdx; + } + + private int findEntry(byte[] p, int pLen) { + int low = 0; + int high = entryCnt; + while (low < high) { + int mid = (low + high) >>> 1; + int cmp = cmp(p, pLen, entries[mid]); + if (cmp < 0) { + high = mid; + } else if (cmp == 0) { + while (mid > 0 && cmp(p, pLen, entries[mid - 1]) == 0) { + mid--; + } + return mid; + } else { + low = mid + 1; + } + } + return -(low + 1); + } + + private void insertEdit(DeleteTree d) { + for (int i = editIdx; i < edits.size(); i++) { + int cmp = EDIT_CMP.compare(d, edits.get(i)); + if (cmp < 0) { + edits.add(i, d); + return; + } else if (cmp == 0) { + return; + } + } + edits.add(d); + } + + private static boolean inDir(DirCacheEntry e, byte[] path, int pLen) { + return e.path.length > pLen && e.path[pLen] == '/' + && peq(path, e.path, pLen); + } + + private static int pdir(byte[] path, int e) { + for (e--; e > 0; e--) { + if (path[e] == '/') { + return e; + } + } + return 0; + } + /** * Any index record update. * <p> @@ -175,10 +272,13 @@ public class DirCacheEditor extends BaseDirCacheEditor { * {@link #apply(DirCacheEntry)} method. The editor will invoke apply once * for each record in the index which matches the path name. If there are * multiple records (for example in stages 1, 2 and 3), the edit instance - * will be called multiple times, once for each stage. + * will be called multiple times, once for each stage. If any of these calls + * resets the stage to 0, only this entry will be taken and entries for + * other stages are discarded. */ public abstract static class PathEdit { final byte[] path; + boolean replace = true; /** * Create a new update command by path name. @@ -186,10 +286,14 @@ public class DirCacheEditor extends BaseDirCacheEditor { * @param entryPath * path of the file within the repository. */ - public PathEdit(final String entryPath) { + public PathEdit(String entryPath) { path = Constants.encode(entryPath); } + PathEdit(byte[] path) { + this.path = path; + } + /** * Create a new update command for an existing entry instance. * @@ -197,11 +301,27 @@ public class DirCacheEditor extends BaseDirCacheEditor { * entry instance to match path of. Only the path of this * entry is actually considered during command evaluation. */ - public PathEdit(final DirCacheEntry ent) { + public PathEdit(DirCacheEntry ent) { path = ent.path; } /** + * Configure if a file can replace a directory (or vice versa). + * <p> + * Default is {@code true} as this is usually the desired behavior. + * + * @param ok + * if true a file can replace a directory, or a directory can + * replace a file. + * @return {@code this} + * @since 4.2 + */ + public PathEdit setReplace(boolean ok) { + replace = ok; + return this; + } + + /** * Apply the update to a single cache entry matching the path. * <p> * After apply is invoked the entry is added to the output table, and @@ -212,6 +332,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 + ']'; + } } /** @@ -230,7 +356,7 @@ public class DirCacheEditor extends BaseDirCacheEditor { * @param entryPath * path of the file within the repository. */ - public DeletePath(final String entryPath) { + public DeletePath(String entryPath) { super(entryPath); } @@ -241,11 +367,12 @@ public class DirCacheEditor extends BaseDirCacheEditor { * entry instance to remove. Only the path of this entry is * actually considered during command evaluation. */ - public DeletePath(final DirCacheEntry ent) { + public DeletePath(DirCacheEntry ent) { super(ent); } - public void apply(final DirCacheEntry ent) { + @Override + public void apply(DirCacheEntry ent) { throw new UnsupportedOperationException(JGitText.get().noApplyInDelete); } } @@ -272,13 +399,30 @@ public class DirCacheEditor extends BaseDirCacheEditor { * only the subtree's contents are matched by the command. * The special case "" (not "/"!) deletes all entries. */ - public DeleteTree(final String entryPath) { - super( - (entryPath.endsWith("/") || entryPath.length() == 0) ? entryPath //$NON-NLS-1$ - : entryPath + "/"); //$NON-NLS-1$ + public DeleteTree(String entryPath) { + super(entryPath.isEmpty() + || entryPath.charAt(entryPath.length() - 1) == '/' + ? entryPath + : entryPath + '/'); + } + + DeleteTree(byte[] path) { + super(appendSlash(path)); + } + + private static byte[] appendSlash(byte[] path) { + int n = path.length; + if (n > 0 && path[n - 1] != '/') { + byte[] r = new byte[n + 1]; + System.arraycopy(path, 0, r, 0, n); + r[n] = '/'; + return r; + } + return path; } - public void apply(final DirCacheEntry ent) { + @Override + public void apply(DirCacheEntry ent) { throw new UnsupportedOperationException(JGitText.get().noApplyInDelete); } } |