org.spearce.jgit/src/org/spearce/jgit/revwalk/RewriteTreeFilter.java

   1 /*
   2  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   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.revwalk;
  39
  40 import java.io.IOException;
  41
  42 import org.spearce.jgit.errors.IncorrectObjectTypeException;
  43 import org.spearce.jgit.errors.MissingObjectException;
  44 import org.spearce.jgit.errors.StopWalkException;
  45 import org.spearce.jgit.lib.ObjectId;
  46 import org.spearce.jgit.revwalk.filter.RevFilter;
  47 import org.spearce.jgit.treewalk.TreeWalk;
  48 import org.spearce.jgit.treewalk.filter.TreeFilter;
  49
  50 /**
  51  * First phase of a path limited revision walk.
  52  * <p>
  53  * This filter is ANDed to evaluate after all other filters and ties the
  54  * configured {@link TreeFilter} into the revision walking process.
  55  * <p>
  56  * Each commit is differenced concurrently against all of its parents to look
  57  * for tree entries that are interesting to the TreeFilter. If none are found
  58  * the commit is colored with {@link RevWalk#REWRITE}, allowing a later pass
  59  * implemented by {@link RewriteGenerator} to remove those colored commits from
  60  * the DAG.
  61  *
  62  * @see RewriteGenerator
  63  */
  64 class RewriteTreeFilter extends RevFilter {
  65         private static final int PARSED = RevWalk.PARSED;
  66
  67         private static final int UNINTERESTING = RevWalk.UNINTERESTING;
  68
  69         private static final int REWRITE = RevWalk.REWRITE;
  70
  71         private final TreeWalk pathFilter;
  72
  73         RewriteTreeFilter(final RevWalk walker, final TreeFilter t) {
  74                 pathFilter = new TreeWalk(walker.db);
  75                 pathFilter.setFilter(t);
  76                 pathFilter.setRecursive(t.shouldBeRecursive());
  77         }
  78
  79         @Override
  80         public RevFilter clone() {
  81                 throw new UnsupportedOperationException();
  82         }
  83
  84         @Override
  85         public boolean include(final RevWalk walker, final RevCommit c)
  86                         throws StopWalkException, MissingObjectException,
  87                         IncorrectObjectTypeException, IOException {
  88                 // Reset the tree filter to scan this commit and parents.
  89                 //
  90                 final RevCommit[] pList = c.parents;
  91                 final int nParents = pList.length;
  92                 final TreeWalk tw = pathFilter;
  93                 final ObjectId[] trees = new ObjectId[nParents + 1];
  94                 for (int i = 0; i < nParents; i++) {
  95                         final RevCommit p = c.parents[i];
  96                         if ((p.flags & PARSED) == 0)
  97                                 p.parse(walker);
  98                         trees[i] = p.getTree();
  99                 }
 100                 trees[nParents] = c.getTree();
 101                 tw.reset(trees);
 102
 103                 if (nParents == 1) {
 104                         // We have exactly one parent. This is a very common case.
 105                         //
 106                         int chgs = 0, adds = 0;
 107                         while (tw.next()) {
 108                                 chgs++;
 109                                 if (tw.getRawMode(0) == 0 && tw.getRawMode(1) != 0)
 110                                         adds++;
 111                                 else
 112                                         break; // no point in looking at this further.
 113                         }
 114
 115                         if (chgs == 0) {
 116                                 // No changes, so our tree is effectively the same as
 117                                 // our parent tree. We pass the buck to our parent.
 118                                 //
 119                                 c.flags |= REWRITE;
 120                                 return false;
 121                         } else {
 122                                 // We have interesting items, but neither of the special
 123                                 // cases denoted above.
 124                                 //
 125                                 return true;
 126                         }
 127                 } else if (nParents == 0) {
 128                         // We have no parents to compare against. Consider us to be
 129                         // REWRITE only if we have no paths matching our filter.
 130                         //
 131                         if (tw.next())
 132                                 return true;
 133                         c.flags |= REWRITE;
 134                         return false;
 135                 }
 136
 137                 // We are a merge commit. We can only be REWRITE if we are same
 138                 // to _all_ parents. We may also be able to eliminate a parent if
 139                 // it does not contribute changes to us. Such a parent may be an
 140                 // uninteresting side branch.
 141                 //
 142                 final int[] chgs = new int[nParents];
 143                 final int[] adds = new int[nParents];
 144                 while (tw.next()) {
 145                         final int myMode = tw.getRawMode(nParents);
 146                         for (int i = 0; i < nParents; i++) {
 147                                 final int pMode = tw.getRawMode(i);
 148                                 if (myMode == pMode && tw.idEqual(i, nParents))
 149                                         continue;
 150
 151                                 chgs[i]++;
 152                                 if (pMode == 0 && myMode != 0)
 153                                         adds[i]++;
 154                         }
 155                 }
 156
 157                 boolean same = false;
 158                 boolean diff = false;
 159                 for (int i = 0; i < nParents; i++) {
 160                         if (chgs[i] == 0) {
 161                                 // No changes, so our tree is effectively the same as
 162                                 // this parent tree. We pass the buck to only this one
 163                                 // parent commit.
 164                                 //
 165
 166                                 final RevCommit p = pList[i];
 167                                 if ((p.flags & UNINTERESTING) != 0) {
 168                                         // This parent was marked as not interesting by the
 169                                         // application. We should look for another parent
 170                                         // that is interesting.
 171                                         //
 172                                         same = true;
 173                                         continue;
 174                                 }
 175
 176                                 c.flags |= REWRITE;
 177                                 c.parents = new RevCommit[] { p };
 178                                 return false;
 179                         }
 180
 181                         if (chgs[i] == adds[i]) {
 182                                 // All of the differences from this parent were because we
 183                                 // added files that they did not have. This parent is our
 184                                 // "empty tree root" and thus their history is not relevant.
 185                                 // Cut our grandparents to be an empty list.
 186                                 //
 187                                 pList[i].parents = RevCommit.NO_PARENTS;
 188                         }
 189
 190                         // We have an interesting difference relative to this parent.
 191                         //
 192                         diff = true;
 193                 }
 194
 195                 if (diff && !same) {
 196                         // We did not abort above, so we are different in at least one
 197                         // way from all of our parents. We have to take the blame for
 198                         // that difference.
 199                         //
 200                         return true;
 201                 }
 202
 203                 // We are the same as all of our parents. We must keep them
 204                 // as they are and allow those parents to flow into pending
 205                 // for further scanning.
 206                 //
 207                 c.flags |= REWRITE;
 208                 return false;
 209         }
 210 }