org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java

   1 /*
   2  * Copyright (C) 2008, Google Inc.
   3  *
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or
   7  * without modification, are permitted provided that the following
   8  * conditions are met:
   9  *
  10  * - Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  *
  13  * - Redistributions in binary form must reproduce the above
  14  *   copyright notice, this list of conditions and the following
  15  *   disclaimer in the documentation and/or other materials provided
  16  *   with the distribution.
  17  *
  18  * - Neither the name of the Git Development Community nor the
  19  *   names of its contributors may be used to endorse or promote
  20  *   products derived from this software without specific prior
  21  *   written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  24  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  25  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  26  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  28  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  29  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  30  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  32  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  33  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  35  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 package org.spearce.jgit.treewalk;
  39
  40 import org.spearce.jgit.dircache.DirCacheBuilder;
  41 import org.spearce.jgit.errors.CorruptObjectException;
  42 import org.spearce.jgit.lib.FileMode;
  43 import org.spearce.jgit.lib.Repository;
  44
  45 /**
  46  * Specialized TreeWalk to detect directory-file (D/F) name conflicts.
  47  * <p>
  48  * Due to the way a Git tree is organized the standard {@link TreeWalk} won't
  49  * easily find a D/F conflict when merging two or more trees together. In the
  50  * standard TreeWalk the file will be returned first, and then much later the
  51  * directory will be returned. This makes it impossible for the application to
  52  * efficiently detect and handle the conflict.
  53  * <p>
  54  * Using this walk implementation causes the directory to report earlier than
  55  * usual, at the same time as the non-directory entry. This permits the
  56  * application to handle the D/F conflict in a single step. The directory is
  57  * returned only once, so it does not get returned later in the iteration.
  58  * <p>
  59  * When a D/F conflict is detected {@link TreeWalk#isSubtree()} will return true
  60  * and {@link TreeWalk#enterSubtree()} will recurse into the subtree, no matter
  61  * which iterator originally supplied the subtree.
  62  * <p>
  63  * Because conflicted directories report early, using this walk implementation
  64  * to populate a {@link DirCacheBuilder} may cause the automatic resorting to
  65  * run and fix the entry ordering.
  66  * <p>
  67  * This walk implementation requires more CPU to implement a look-ahead and a
  68  * look-behind to merge a D/F pair together, or to skip a previously reported
  69  * directory. In typical Git repositories the look-ahead cost is 0 and the
  70  * look-behind doesn't trigger, as users tend not to create trees which contain
  71  * both "foo" as a directory and "foo.c" as a file.
  72  * <p>
  73  * In the worst-case however several thousand look-ahead steps per walk step may
  74  * be necessary, making the overhead quite significant. Since this worst-case
  75  * should never happen this walk implementation has made the time/space tradeoff
  76  * in favor of more-time/less-space, as that better suits the typical case.
  77  */
  78 public class NameConflictTreeWalk extends TreeWalk {
  79         private static final int TREE_MODE = FileMode.TREE.getBits();
  80
  81         private boolean fastMinHasMatch;
  82
  83         /**
  84          * Create a new tree walker for a given repository.
  85          *
  86          * @param repo
  87          *            the repository the walker will obtain data from.
  88          */
  89         public NameConflictTreeWalk(final Repository repo) {
  90                 super(repo);
  91         }
  92
  93         @Override
  94         AbstractTreeIterator min() throws CorruptObjectException {
  95                 for (;;) {
  96                         final AbstractTreeIterator minRef = fastMin();
  97                         if (fastMinHasMatch)
  98                                 return minRef;
  99
 100                         if (isTree(minRef)) {
 101                                 if (skipEntry(minRef)) {
 102                                         for (final AbstractTreeIterator t : trees) {
 103                                                 if (t.matches == minRef) {
 104                                                         t.next(1);
 105                                                         t.matches = null;
 106                                                 }
 107                                         }
 108                                         continue;
 109                                 }
 110                                 return minRef;
 111                         }
 112
 113                         return combineDF(minRef);
 114                 }
 115         }
 116
 117         private AbstractTreeIterator fastMin() {
 118                 fastMinHasMatch = true;
 119
 120                 int i = 0;
 121                 AbstractTreeIterator minRef = trees[i];
 122                 while (minRef.eof() && ++i < trees.length)
 123                         minRef = trees[i];
 124                 if (minRef.eof())
 125                         return minRef;
 126
 127                 minRef.matches = minRef;
 128                 while (++i < trees.length) {
 129                         final AbstractTreeIterator t = trees[i];
 130                         if (t.eof())
 131                                 continue;
 132
 133                         final int cmp = t.pathCompare(minRef);
 134                         if (cmp < 0) {
 135                                 if (fastMinHasMatch && isTree(minRef) && !isTree(t)
 136                                                 && nameEqual(minRef, t)) {
 137                                         // We used to be at a tree, but now we are at a file
 138                                         // with the same name. Allow the file to match the
 139                                         // tree anyway.
 140                                         //
 141                                         t.matches = minRef;
 142                                 } else {
 143                                         fastMinHasMatch = false;
 144                                         t.matches = t;
 145                                         minRef = t;
 146                                 }
 147                         } else if (cmp == 0) {
 148                                 // Exact name/mode match is best.
 149                                 //
 150                                 t.matches = minRef;
 151                         } else if (fastMinHasMatch && isTree(t) && !isTree(minRef)
 152                                         && nameEqual(t, minRef)) {
 153                                 // The minimum is a file (non-tree) but the next entry
 154                                 // of this iterator is a tree whose name matches our file.
 155                                 // This is a classic D/F conflict and commonly occurs like
 156                                 // this, with no gaps in between the file and directory.
 157                                 //
 158                                 // Use the tree as the minimum instead (see combineDF).
 159                                 //
 160
 161                                 for (int k = 0; k < i; k++) {
 162                                         final AbstractTreeIterator p = trees[k];
 163                                         if (p.matches == minRef)
 164                                                 p.matches = t;
 165                                 }
 166                                 t.matches = t;
 167                                 minRef = t;
 168                         } else
 169                                 fastMinHasMatch = false;
 170                 }
 171
 172                 return minRef;
 173         }
 174
 175         private static boolean nameEqual(final AbstractTreeIterator a,
 176                         final AbstractTreeIterator b) {
 177                 return a.pathCompare(b, TREE_MODE) == 0;
 178         }
 179
 180         private static boolean isTree(final AbstractTreeIterator p) {
 181                 return FileMode.TREE.equals(p.mode);
 182         }
 183
 184         private boolean skipEntry(final AbstractTreeIterator minRef)
 185                         throws CorruptObjectException {
 186                 // A tree D/F may have been handled earlier. We need to
 187                 // not report this path if it has already been reported.
 188                 //
 189                 for (final AbstractTreeIterator t : trees) {
 190                         if (t.matches == minRef || t.first())
 191                                 continue;
 192
 193                         int stepsBack = 0;
 194                         for (;;) {
 195                                 stepsBack++;
 196                                 t.back(1);
 197
 198                                 final int cmp = t.pathCompare(minRef, 0);
 199                                 if (cmp == 0) {
 200                                         // We have already seen this "$path" before. Skip it.
 201                                         //
 202                                         t.next(stepsBack);
 203                                         return true;
 204                                 } else if (cmp < 0 || t.first()) {
 205                                         // We cannot find "$path" in t; it will never appear.
 206                                         //
 207                                         t.next(stepsBack);
 208                                         break;
 209                                 }
 210                         }
 211                 }
 212
 213                 // We have never seen the current path before.
 214                 //
 215                 return false;
 216         }
 217
 218         private AbstractTreeIterator combineDF(final AbstractTreeIterator minRef)
 219                         throws CorruptObjectException {
 220                 // Look for a possible D/F conflict forward in the tree(s)
 221                 // as there may be a "$path/" which matches "$path". Make
 222                 // such entries match this entry.
 223                 //
 224                 AbstractTreeIterator treeMatch = null;
 225                 for (final AbstractTreeIterator t : trees) {
 226                         if (t.matches == minRef || t.eof())
 227                                 continue;
 228
 229                         for (;;) {
 230                                 final int cmp = t.pathCompare(minRef, TREE_MODE);
 231                                 if (cmp < 0) {
 232                                         // The "$path/" may still appear later.
 233                                         //
 234                                         t.matchShift++;
 235                                         t.next(1);
 236                                         if (t.eof()) {
 237                                                 t.back(t.matchShift);
 238                                                 t.matchShift = 0;
 239                                                 break;
 240                                         }
 241                                 } else if (cmp == 0) {
 242                                         // We have a conflict match here.
 243                                         //
 244                                         t.matches = minRef;
 245                                         treeMatch = t;
 246                                         break;
 247                                 } else {
 248                                         // A conflict match is not possible.
 249                                         //
 250                                         if (t.matchShift != 0) {
 251                                                 t.back(t.matchShift);
 252                                                 t.matchShift = 0;
 253                                         }
 254                                         break;
 255                                 }
 256                         }
 257                 }
 258
 259                 if (treeMatch != null) {
 260                         // If we do have a conflict use one of the directory
 261                         // matching iterators instead of the file iterator.
 262                         // This way isSubtree is true and isRecursive works.
 263                         //
 264                         for (final AbstractTreeIterator t : trees)
 265                                 if (t.matches == minRef)
 266                                         t.matches = treeMatch;
 267                         return treeMatch;
 268                 }
 269
 270                 return minRef;
 271         }
 272
 273         @Override
 274         void popEntriesEqual() throws CorruptObjectException {
 275                 final AbstractTreeIterator ch = currentHead;
 276                 for (int i = 0; i < trees.length; i++) {
 277                         final AbstractTreeIterator t = trees[i];
 278                         if (t.matches == ch) {
 279                                 if (t.matchShift == 0)
 280                                         t.next(1);
 281                                 else {
 282                                         t.back(t.matchShift);
 283                                         t.matchShift = 0;
 284                                 }
 285                                 t.matches = null;
 286                         }
 287                 }
 288         }
 289
 290         @Override
 291         void skipEntriesEqual() throws CorruptObjectException {
 292                 final AbstractTreeIterator ch = currentHead;
 293                 for (int i = 0; i < trees.length; i++) {
 294                         final AbstractTreeIterator t = trees[i];
 295                         if (t.matches == ch) {
 296                                 if (t.matchShift == 0)
 297                                         t.skip();
 298                                 else {
 299                                         t.back(t.matchShift);
 300                                         t.matchShift = 0;
 301                                 }
 302                                 t.matches = null;
 303                         }
 304                 }
 305         }
 306 }