← Back to branch summary

~ubuntu-branches/ubuntu/quantal/monodevelop/quantal

« back to all changes in this revision

Viewing changes to contrib/NGit/NGit.Treewalk/NameConflictTreeWalk.cs

  • Committer: Bazaar Package Importer
  • Author(s): Andrew Mitchell
  • Date: 2011-06-29 06:56:25 UTC
  • mfrom: (1.8.1 upstream) (1.3.11 experimental)
  • Revision ID: james.westby@ubuntu.com-20110629065625-7xx19c4vb95j65pl
Tags: 2.5.92+dfsg-1ubuntu1
* Merge from Debian experimental:
 - Dropped patches & changes to debian/control for Moonlight
   + debian/patches/remove_support_for_moonlight.patch,
   + debian/patches/dont_add_moonlight_to_core_addins.patch,
 - Remaining patches:
   + debian/patches/no_appmenu:

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/NGit/NGit.Treewalk/NameConflictTreeWalk.cs
 
1
/*
 
2
This code is derived from jgit (http://eclipse.org/jgit).
 
3
Copyright owners are documented in jgit's IP log.
 
4
 
 
5
This program and the accompanying materials are made available
 
6
under the terms of the Eclipse Distribution License v1.0 which
 
7
accompanies this distribution, is reproduced below, and is
 
8
available at http://www.eclipse.org/org/documents/edl-v10.php
 
9
 
 
10
All rights reserved.
 
11
 
 
12
Redistribution and use in source and binary forms, with or
 
13
without modification, are permitted provided that the following
 
14
conditions are met:
 
15
 
 
16
- Redistributions of source code must retain the above copyright
 
17
  notice, this list of conditions and the following disclaimer.
 
18
 
 
19
- Redistributions in binary form must reproduce the above
 
20
  copyright notice, this list of conditions and the following
 
21
  disclaimer in the documentation and/or other materials provided
 
22
  with the distribution.
 
23
 
 
24
- Neither the name of the Eclipse Foundation, Inc. nor the
 
25
  names of its contributors may be used to endorse or promote
 
26
  products derived from this software without specific prior
 
27
  written permission.
 
28
 
 
29
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 
30
CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 
31
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 
32
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
33
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 
34
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 
35
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
36
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 
37
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 
38
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 
39
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 
40
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 
41
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
42
*/
 
43
 
 
44
using NGit;
 
45
using NGit.Treewalk;
 
46
using Sharpen;
 
47
 
 
48
namespace NGit.Treewalk
 
49
{
 
50
        /// <summary>Specialized TreeWalk to detect directory-file (D/F) name conflicts.</summary>
 
51
        /// <remarks>
 
52
        /// Specialized TreeWalk to detect directory-file (D/F) name conflicts.
 
53
        /// <p>
 
54
        /// Due to the way a Git tree is organized the standard
 
55
        /// <see cref="TreeWalk">TreeWalk</see>
 
56
        /// won't
 
57
        /// easily find a D/F conflict when merging two or more trees together. In the
 
58
        /// standard TreeWalk the file will be returned first, and then much later the
 
59
        /// directory will be returned. This makes it impossible for the application to
 
60
        /// efficiently detect and handle the conflict.
 
61
        /// <p>
 
62
        /// Using this walk implementation causes the directory to report earlier than
 
63
        /// usual, at the same time as the non-directory entry. This permits the
 
64
        /// application to handle the D/F conflict in a single step. The directory is
 
65
        /// returned only once, so it does not get returned later in the iteration.
 
66
        /// <p>
 
67
        /// When a D/F conflict is detected
 
68
        /// <see cref="TreeWalk.IsSubtree()">TreeWalk.IsSubtree()</see>
 
69
        /// will return true
 
70
        /// and
 
71
        /// <see cref="TreeWalk.EnterSubtree()">TreeWalk.EnterSubtree()</see>
 
72
        /// will recurse into the subtree, no matter
 
73
        /// which iterator originally supplied the subtree.
 
74
        /// <p>
 
75
        /// Because conflicted directories report early, using this walk implementation
 
76
        /// to populate a
 
77
        /// <see cref="NGit.Dircache.DirCacheBuilder">NGit.Dircache.DirCacheBuilder</see>
 
78
        /// may cause the automatic resorting to
 
79
        /// run and fix the entry ordering.
 
80
        /// <p>
 
81
        /// This walk implementation requires more CPU to implement a look-ahead and a
 
82
        /// look-behind to merge a D/F pair together, or to skip a previously reported
 
83
        /// directory. In typical Git repositories the look-ahead cost is 0 and the
 
84
        /// look-behind doesn't trigger, as users tend not to create trees which contain
 
85
        /// both "foo" as a directory and "foo.c" as a file.
 
86
        /// <p>
 
87
        /// In the worst-case however several thousand look-ahead steps per walk step may
 
88
        /// be necessary, making the overhead quite significant. Since this worst-case
 
89
        /// should never happen this walk implementation has made the time/space tradeoff
 
90
        /// in favor of more-time/less-space, as that better suits the typical case.
 
91
        /// </remarks>
 
92
        public class NameConflictTreeWalk : TreeWalk
 
93
        {
 
94
                private static readonly int TREE_MODE = FileMode.TREE.GetBits();
 
95
 
 
96
                private bool fastMinHasMatch;
 
97
 
 
98
                private AbstractTreeIterator dfConflict;
 
99
 
 
100
                /// <summary>Create a new tree walker for a given repository.</summary>
 
101
                /// <remarks>Create a new tree walker for a given repository.</remarks>
 
102
                /// <param name="repo">the repository the walker will obtain data from.</param>
 
103
                public NameConflictTreeWalk(Repository repo) : this(repo.NewObjectReader())
 
104
                {
 
105
                }
 
106
 
 
107
                /// <summary>Create a new tree walker for a given repository.</summary>
 
108
                /// <remarks>Create a new tree walker for a given repository.</remarks>
 
109
                /// <param name="or">the reader the walker will obtain tree data from.</param>
 
110
                public NameConflictTreeWalk(ObjectReader or) : base(or)
 
111
                {
 
112
                }
 
113
 
 
114
                /// <exception cref="NGit.Errors.CorruptObjectException"></exception>
 
115
                internal override AbstractTreeIterator Min()
 
116
                {
 
117
                        for (; ; )
 
118
                        {
 
119
                                AbstractTreeIterator minRef = FastMin();
 
120
                                if (fastMinHasMatch)
 
121
                                {
 
122
                                        return minRef;
 
123
                                }
 
124
                                if (IsTree(minRef))
 
125
                                {
 
126
                                        if (SkipEntry(minRef))
 
127
                                        {
 
128
                                                foreach (AbstractTreeIterator t in trees)
 
129
                                                {
 
130
                                                        if (t.matches == minRef)
 
131
                                                        {
 
132
                                                                t.Next(1);
 
133
                                                                t.matches = null;
 
134
                                                        }
 
135
                                                }
 
136
                                                continue;
 
137
                                        }
 
138
                                        return minRef;
 
139
                                }
 
140
                                return CombineDF(minRef);
 
141
                        }
 
142
                }
 
143
 
 
144
                private AbstractTreeIterator FastMin()
 
145
                {
 
146
                        fastMinHasMatch = true;
 
147
                        int i = 0;
 
148
                        AbstractTreeIterator minRef = trees[i];
 
149
                        while (minRef.Eof && ++i < trees.Length)
 
150
                        {
 
151
                                minRef = trees[i];
 
152
                        }
 
153
                        if (minRef.Eof)
 
154
                        {
 
155
                                return minRef;
 
156
                        }
 
157
                        bool hasConflict = false;
 
158
                        minRef.matches = minRef;
 
159
                        while (++i < trees.Length)
 
160
                        {
 
161
                                AbstractTreeIterator t = trees[i];
 
162
                                if (t.Eof)
 
163
                                {
 
164
                                        continue;
 
165
                                }
 
166
                                int cmp = t.PathCompare(minRef);
 
167
                                if (cmp < 0)
 
168
                                {
 
169
                                        if (fastMinHasMatch && IsTree(minRef) && !IsTree(t) && NameEqual(minRef, t))
 
170
                                        {
 
171
                                                // We used to be at a tree, but now we are at a file
 
172
                                                // with the same name. Allow the file to match the
 
173
                                                // tree anyway.
 
174
                                                //
 
175
                                                t.matches = minRef;
 
176
                                                hasConflict = true;
 
177
                                        }
 
178
                                        else
 
179
                                        {
 
180
                                                fastMinHasMatch = false;
 
181
                                                t.matches = t;
 
182
                                                minRef = t;
 
183
                                        }
 
184
                                }
 
185
                                else
 
186
                                {
 
187
                                        if (cmp == 0)
 
188
                                        {
 
189
                                                // Exact name/mode match is best.
 
190
                                                //
 
191
                                                t.matches = minRef;
 
192
                                        }
 
193
                                        else
 
194
                                        {
 
195
                                                if (fastMinHasMatch && IsTree(t) && !IsTree(minRef) && NameEqual(t, minRef))
 
196
                                                {
 
197
                                                        // The minimum is a file (non-tree) but the next entry
 
198
                                                        // of this iterator is a tree whose name matches our file.
 
199
                                                        // This is a classic D/F conflict and commonly occurs like
 
200
                                                        // this, with no gaps in between the file and directory.
 
201
                                                        //
 
202
                                                        // Use the tree as the minimum instead (see combineDF).
 
203
                                                        //
 
204
                                                        for (int k = 0; k < i; k++)
 
205
                                                        {
 
206
                                                                AbstractTreeIterator p = trees[k];
 
207
                                                                if (p.matches == minRef)
 
208
                                                                {
 
209
                                                                        p.matches = t;
 
210
                                                                }
 
211
                                                        }
 
212
                                                        t.matches = t;
 
213
                                                        minRef = t;
 
214
                                                        hasConflict = true;
 
215
                                                }
 
216
                                                else
 
217
                                                {
 
218
                                                        fastMinHasMatch = false;
 
219
                                                }
 
220
                                        }
 
221
                                }
 
222
                        }
 
223
                        if (hasConflict && fastMinHasMatch && dfConflict == null)
 
224
                        {
 
225
                                dfConflict = minRef;
 
226
                        }
 
227
                        return minRef;
 
228
                }
 
229
 
 
230
                private static bool NameEqual(AbstractTreeIterator a, AbstractTreeIterator b)
 
231
                {
 
232
                        return a.PathCompare(b, TREE_MODE) == 0;
 
233
                }
 
234
 
 
235
                private static bool IsTree(AbstractTreeIterator p)
 
236
                {
 
237
                        return FileMode.TREE.Equals(p.mode);
 
238
                }
 
239
 
 
240
                /// <exception cref="NGit.Errors.CorruptObjectException"></exception>
 
241
                private bool SkipEntry(AbstractTreeIterator minRef)
 
242
                {
 
243
                        // A tree D/F may have been handled earlier. We need to
 
244
                        // not report this path if it has already been reported.
 
245
                        //
 
246
                        foreach (AbstractTreeIterator t in trees)
 
247
                        {
 
248
                                if (t.matches == minRef || t.First)
 
249
                                {
 
250
                                        continue;
 
251
                                }
 
252
                                int stepsBack = 0;
 
253
                                for (; ; )
 
254
                                {
 
255
                                        stepsBack++;
 
256
                                        t.Back(1);
 
257
                                        int cmp = t.PathCompare(minRef, 0);
 
258
                                        if (cmp == 0)
 
259
                                        {
 
260
                                                // We have already seen this "$path" before. Skip it.
 
261
                                                //
 
262
                                                t.Next(stepsBack);
 
263
                                                return true;
 
264
                                        }
 
265
                                        else
 
266
                                        {
 
267
                                                if (cmp < 0 || t.First)
 
268
                                                {
 
269
                                                        // We cannot find "$path" in t; it will never appear.
 
270
                                                        //
 
271
                                                        t.Next(stepsBack);
 
272
                                                        break;
 
273
                                                }
 
274
                                        }
 
275
                                }
 
276
                        }
 
277
                        // We have never seen the current path before.
 
278
                        //
 
279
                        return false;
 
280
                }
 
281
 
 
282
                /// <exception cref="NGit.Errors.CorruptObjectException"></exception>
 
283
                private AbstractTreeIterator CombineDF(AbstractTreeIterator minRef)
 
284
                {
 
285
                        // Look for a possible D/F conflict forward in the tree(s)
 
286
                        // as there may be a "$path/" which matches "$path". Make
 
287
                        // such entries match this entry.
 
288
                        //
 
289
                        AbstractTreeIterator treeMatch = null;
 
290
                        foreach (AbstractTreeIterator t in trees)
 
291
                        {
 
292
                                if (t.matches == minRef || t.Eof)
 
293
                                {
 
294
                                        continue;
 
295
                                }
 
296
                                for (; ; )
 
297
                                {
 
298
                                        int cmp = t.PathCompare(minRef, TREE_MODE);
 
299
                                        if (cmp < 0)
 
300
                                        {
 
301
                                                // The "$path/" may still appear later.
 
302
                                                //
 
303
                                                t.matchShift++;
 
304
                                                t.Next(1);
 
305
                                                if (t.Eof)
 
306
                                                {
 
307
                                                        t.Back(t.matchShift);
 
308
                                                        t.matchShift = 0;
 
309
                                                        break;
 
310
                                                }
 
311
                                        }
 
312
                                        else
 
313
                                        {
 
314
                                                if (cmp == 0)
 
315
                                                {
 
316
                                                        // We have a conflict match here.
 
317
                                                        //
 
318
                                                        t.matches = minRef;
 
319
                                                        treeMatch = t;
 
320
                                                        break;
 
321
                                                }
 
322
                                                else
 
323
                                                {
 
324
                                                        // A conflict match is not possible.
 
325
                                                        //
 
326
                                                        if (t.matchShift != 0)
 
327
                                                        {
 
328
                                                                t.Back(t.matchShift);
 
329
                                                                t.matchShift = 0;
 
330
                                                        }
 
331
                                                        break;
 
332
                                                }
 
333
                                        }
 
334
                                }
 
335
                        }
 
336
                        if (treeMatch != null)
 
337
                        {
 
338
                                // If we do have a conflict use one of the directory
 
339
                                // matching iterators instead of the file iterator.
 
340
                                // This way isSubtree is true and isRecursive works.
 
341
                                //
 
342
                                foreach (AbstractTreeIterator t_1 in trees)
 
343
                                {
 
344
                                        if (t_1.matches == minRef)
 
345
                                        {
 
346
                                                t_1.matches = treeMatch;
 
347
                                        }
 
348
                                }
 
349
                                if (dfConflict == null)
 
350
                                {
 
351
                                        dfConflict = treeMatch;
 
352
                                }
 
353
                                return treeMatch;
 
354
                        }
 
355
                        return minRef;
 
356
                }
 
357
 
 
358
                /// <exception cref="NGit.Errors.CorruptObjectException"></exception>
 
359
                internal override void PopEntriesEqual()
 
360
                {
 
361
                        AbstractTreeIterator ch = currentHead;
 
362
                        for (int i = 0; i < trees.Length; i++)
 
363
                        {
 
364
                                AbstractTreeIterator t = trees[i];
 
365
                                if (t.matches == ch)
 
366
                                {
 
367
                                        if (t.matchShift == 0)
 
368
                                        {
 
369
                                                t.Next(1);
 
370
                                        }
 
371
                                        else
 
372
                                        {
 
373
                                                t.Back(t.matchShift);
 
374
                                                t.matchShift = 0;
 
375
                                        }
 
376
                                        t.matches = null;
 
377
                                }
 
378
                        }
 
379
                        if (ch == dfConflict)
 
380
                        {
 
381
                                dfConflict = null;
 
382
                        }
 
383
                }
 
384
 
 
385
                /// <exception cref="NGit.Errors.CorruptObjectException"></exception>
 
386
                internal override void SkipEntriesEqual()
 
387
                {
 
388
                        AbstractTreeIterator ch = currentHead;
 
389
                        for (int i = 0; i < trees.Length; i++)
 
390
                        {
 
391
                                AbstractTreeIterator t = trees[i];
 
392
                                if (t.matches == ch)
 
393
                                {
 
394
                                        if (t.matchShift == 0)
 
395
                                        {
 
396
                                                t.Skip();
 
397
                                        }
 
398
                                        else
 
399
                                        {
 
400
                                                t.Back(t.matchShift);
 
401
                                                t.matchShift = 0;
 
402
                                        }
 
403
                                        t.matches = null;
 
404
                                }
 
405
                        }
 
406
                        if (ch == dfConflict)
 
407
                        {
 
408
                                dfConflict = null;
 
409
                        }
 
410
                }
 
411
 
 
412
                /// <summary>True if the current entry is covered by a directory/file conflict.</summary>
 
413
                /// <remarks>
 
414
                /// True if the current entry is covered by a directory/file conflict.
 
415
                /// This means that for some prefix of the current entry's path, this walk
 
416
                /// has detected a directory/file conflict. Also true if the current entry
 
417
                /// itself is a directory/file conflict.
 
418
                /// Example: If this TreeWalk points to foo/bar/a.txt and this method returns
 
419
                /// true then you know that either for path foo or for path foo/bar files and
 
420
                /// folders were detected.
 
421
                /// </remarks>
 
422
                /// <returns>
 
423
                /// <code>true</code> if the current entry is covered by a
 
424
                /// directory/file conflict, <code>false</code> otherwise
 
425
                /// </returns>
 
426
                public virtual bool IsDirectoryFileConflict()
 
427
                {
 
428
                        return dfConflict != null;
 
429
                }
 
430
        }
 
431
}