org.spearce.jgit/src/org/spearce/jgit/lib/IndexTreeWalker.java

   1 /*
   2  * Copyright (C) 2007, Dave Watson <dwatson@mimvista.com>
   3  * Copyright (C) 2008, Robin Rosenberg <robin.rosenberg@dewire.com>
   4  * Copyright (C) 2006, Shawn O. Pearce <spearce@spearce.org>
   5  *
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or
   9  * without modification, are permitted provided that the following
  10  * conditions are met:
  11  *
  12  * - Redistributions of source code must retain the above copyright
  13  *   notice, this list of conditions and the following disclaimer.
  14  *
  15  * - Redistributions in binary form must reproduce the above
  16  *   copyright notice, this list of conditions and the following
  17  *   disclaimer in the documentation and/or other materials provided
  18  *   with the distribution.
  19  *
  20  * - Neither the name of the Git Development Community nor the
  21  *   names of its contributors may be used to endorse or promote
  22  *   products derived from this software without specific prior
  23  *   written permission.
  24  *
  25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  26  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  27  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  28  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  30  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  31  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  32  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  33  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  34  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  35  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  36  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  37  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  38  */
  39
  40 package org.spearce.jgit.lib;
  41
  42 import java.io.File;
  43 import java.io.IOException;
  44
  45 import org.spearce.jgit.lib.GitIndex.Entry;
  46
  47 /**
  48  * A class for traversing the index and one or two trees.
  49  *
  50  * A visitor is invoked for executing actions, like figuring out how to merge.
  51  */
  52 public class IndexTreeWalker {
  53         private final Tree mainTree;
  54         private final Tree newTree;
  55         private final File root;
  56         private final IndexTreeVisitor visitor;
  57         private boolean threeTrees;
  58
  59         /**
  60          * Construct a walker for the index and one tree.
  61          *
  62          * @param index
  63          * @param tree
  64          * @param root
  65          * @param visitor
  66          */
  67         public IndexTreeWalker(GitIndex index, Tree tree, File root, IndexTreeVisitor visitor) {
  68                 this.mainTree = tree;
  69                 this.root = root;
  70                 this.visitor = visitor;
  71                 this.newTree = null;
  72
  73                 threeTrees = false;
  74
  75                 indexMembers = index.getMembers();
  76         }
  77
  78         /**
  79          * Construct a walker for the index and two trees.
  80          *
  81          * @param index
  82          * @param mainTree
  83          * @param newTree
  84          * @param root
  85          * @param visitor
  86          */
  87         public IndexTreeWalker(GitIndex index, Tree mainTree, Tree newTree, File root, IndexTreeVisitor visitor) {
  88                 this.mainTree = mainTree;
  89                 this.newTree = newTree;
  90                 this.root = root;
  91                 this.visitor = visitor;
  92
  93                 threeTrees = true;
  94
  95                 indexMembers = index.getMembers();
  96         }
  97
  98         Entry[] indexMembers;
  99         int indexCounter = 0;
 100
 101         /**
 102          * Actually walk the index tree
 103          *
 104          * @throws IOException
 105          */
 106         public void walk() throws IOException {
 107                 walk(mainTree, newTree);
 108         }
 109
 110         private void walk(Tree tree, Tree auxTree) throws IOException {
 111                 TreeIterator mi = new TreeIterator(tree, TreeIterator.Order.POSTORDER);
 112                 TreeIterator ai = new TreeIterator(auxTree, TreeIterator.Order.POSTORDER);
 113                 TreeEntry m = mi.hasNext() ? mi.next() : null;
 114                 TreeEntry a = ai.hasNext() ? ai.next() : null;
 115                 int curIndexPos = indexCounter;
 116                 Entry i = indexCounter < indexMembers.length ? indexMembers[indexCounter++] : null;
 117                 while (m != null || a != null || i != null) {
 118                         int cmpma = compare(m, a);
 119                         int cmpmi = compare(m, i);
 120                         int cmpai = compare(a, i);
 121
 122                         TreeEntry pm = cmpma <= 0 && cmpmi <= 0 ? m : null;
 123                         TreeEntry pa = cmpma >= 0 && cmpai <= 0 ? a : null;
 124                         Entry     pi = cmpmi >= 0 && cmpai >= 0 ? i : null;
 125
 126                         if (pi != null)
 127                                 visitEntry(pm, pa, pi);
 128                         else
 129                                 finishVisitTree(pm, pa, curIndexPos);
 130
 131                         if (pm != null) m = mi.hasNext() ? mi.next() : null;
 132                         if (pa != null) a = ai.hasNext() ? ai.next() : null;
 133                         if (pi != null) i = indexCounter < indexMembers.length ? indexMembers[indexCounter++] : null;
 134                 }
 135         }
 136
 137         private void visitEntry(TreeEntry t1, TreeEntry t2,
 138                         Entry i) throws IOException {
 139
 140                 assert t1 != null || t2 != null || i != null : "Needs at least one entry";
 141                 assert root != null : "Needs workdir";
 142
 143                 if (t1 != null && t1.getParent() == null)
 144                         t1 = null;
 145                 if (t2 != null && t2.getParent() == null)
 146                         t2 = null;
 147
 148                 File f = null;
 149                 if (i != null)
 150                         f = new File(root, i.getName());
 151                 else if (t1 != null)
 152                         f = new File(root, t1.getFullName());
 153                 else if (t2 != null)
 154                         f = new File(root, t2.getFullName());
 155
 156                 if (t1 != null || t2 != null || i != null)
 157                         if (threeTrees)
 158                                 visitor.visitEntry(t1, t2, i, f);
 159                         else
 160                                 visitor.visitEntry(t1, i, f);
 161         }
 162
 163         private void finishVisitTree(TreeEntry t1, TreeEntry t2, int curIndexPos)
 164                         throws IOException {
 165
 166                 assert t1 != null || t2 != null : "Needs at least one entry";
 167                 assert root != null : "Needs workdir";
 168
 169                 if (t1 != null && t1.getParent() == null)
 170                         t1 = null;
 171                 if (t2 != null && t2.getParent() == null)
 172                         t2 = null;
 173
 174                 File f = null;
 175                 String c= null;
 176                 if (t1 != null) {
 177                         c = t1.getFullName();
 178                         f = new File(root, c);
 179                 } else if (t2 != null) {
 180                         c = t2.getFullName();
 181                         f = new File(root, c);
 182                 }
 183                 if (t1 instanceof Tree || t2 instanceof Tree)
 184                         if (threeTrees)
 185                                 visitor.finishVisitTree((Tree)t1, (Tree)t2, c);
 186                         else
 187                                 visitor.finishVisitTree((Tree)t1, indexCounter - curIndexPos, c);
 188                 else if (t1 != null || t2 != null)
 189                         if (threeTrees)
 190                                 visitor.visitEntry(t1, t2, null, f);
 191                         else
 192                                 visitor.visitEntry(t1, null, f);
 193         }
 194
 195         static boolean lt(TreeEntry h, Entry i) {
 196                 return compare(h, i) < 0;
 197         }
 198
 199         static boolean lt(Entry i, TreeEntry t) {
 200                 return compare(t, i) > 0;
 201         }
 202
 203         static boolean lt(TreeEntry h, TreeEntry m) {
 204                 return compare(h, m) < 0;
 205         }
 206
 207         static boolean eq(TreeEntry t1, TreeEntry t2) {
 208                 return compare(t1, t2) == 0;
 209         }
 210
 211         static boolean eq(TreeEntry t1, Entry e) {
 212                 return compare(t1, e) == 0;
 213         }
 214
 215         static int compare(TreeEntry t, Entry i) {
 216                 if (t == null && i == null)
 217                         return 0;
 218                 if (t == null)
 219                         return 1;
 220                 if (i == null)
 221                         return -1;
 222                 return Tree.compareNames(t.getFullNameUTF8(), i.getNameUTF8(), TreeEntry.lastChar(t), TreeEntry.lastChar(i));
 223         }
 224
 225         static int compare(TreeEntry t1, TreeEntry t2) {
 226                 if (t1 != null && t1.getParent() == null && t2 != null && t2.getParent() == null)
 227                         return 0;
 228                 if (t1 != null && t1.getParent() == null)
 229                         return -1;
 230                 if (t2 != null && t2.getParent() == null)
 231                         return 1;
 232
 233                 if (t1 == null && t2 == null)
 234                         return 0;
 235                 if (t1 == null)
 236                         return 1;
 237                 if (t2 == null)
 238                         return -1;
 239                 return Tree.compareNames(t1.getFullNameUTF8(), t2.getFullNameUTF8(), TreeEntry.lastChar(t1), TreeEntry.lastChar(t2));
 240         }
 241
 242 }