← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/monodevelop/oneiric

« back to all changes in this revision

Viewing changes to contrib/NGit/NGit.Diff/RawTextComparator.cs

  • Committer: Bazaar Package Importer
  • Author(s): Jo Shields
  • Date: 2011-06-27 17:03:13 UTC
  • mto: (1.8.1 upstream)
  • mto: This revision was merged to the branch mainline in revision 54.
  • Revision ID: james.westby@ubuntu.com-20110627170313-6cvz3s19x6e9hqe9
Import upstream version 2.5.92+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/NGit/NGit.Diff/RawTextComparator.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 System;
 
45
using NGit.Diff;
 
46
using NGit.Util;
 
47
using Sharpen;
 
48
 
 
49
namespace NGit.Diff
 
50
{
 
51
        /// <summary>
 
52
        /// Equivalence function for
 
53
        /// <see cref="RawText">RawText</see>
 
54
        /// .
 
55
        /// </summary>
 
56
        public abstract class RawTextComparator : SequenceComparator<RawText>
 
57
        {
 
58
                private sealed class _RawTextComparator_56 : RawTextComparator
 
59
                {
 
60
                        public _RawTextComparator_56()
 
61
                        {
 
62
                        }
 
63
 
 
64
                        public override bool Equals(RawText a, int ai, RawText b, int bi)
 
65
                        {
 
66
                                ai++;
 
67
                                bi++;
 
68
                                int @as = a.lines.Get(ai);
 
69
                                int bs = b.lines.Get(bi);
 
70
                                int ae = a.lines.Get(ai + 1);
 
71
                                int be = b.lines.Get(bi + 1);
 
72
                                if (ae - @as != be - bs)
 
73
                                {
 
74
                                        return false;
 
75
                                }
 
76
                                while (@as < ae)
 
77
                                {
 
78
                                        if (a.content[@as++] != b.content[bs++])
 
79
                                        {
 
80
                                                return false;
 
81
                                        }
 
82
                                }
 
83
                                return true;
 
84
                        }
 
85
 
 
86
                        protected internal override int HashRegion(byte[] raw, int ptr, int end)
 
87
                        {
 
88
                                int hash = 5381;
 
89
                                for (; ptr < end; ptr++)
 
90
                                {
 
91
                                        hash = ((hash << 5) + hash) + (raw[ptr] & unchecked((int)(0xff)));
 
92
                                }
 
93
                                return hash;
 
94
                        }
 
95
                }
 
96
 
 
97
                /// <summary>No special treatment.</summary>
 
98
                /// <remarks>No special treatment.</remarks>
 
99
                public static readonly RawTextComparator DEFAULT = new _RawTextComparator_56();
 
100
 
 
101
                private sealed class _RawTextComparator_87 : RawTextComparator
 
102
                {
 
103
                        public _RawTextComparator_87()
 
104
                        {
 
105
                        }
 
106
 
 
107
                        public override bool Equals(RawText a, int ai, RawText b, int bi)
 
108
                        {
 
109
                                ai++;
 
110
                                bi++;
 
111
                                int @as = a.lines.Get(ai);
 
112
                                int bs = b.lines.Get(bi);
 
113
                                int ae = a.lines.Get(ai + 1);
 
114
                                int be = b.lines.Get(bi + 1);
 
115
                                ae = RawCharUtil.TrimTrailingWhitespace(a.content, @as, ae);
 
116
                                be = RawCharUtil.TrimTrailingWhitespace(b.content, bs, be);
 
117
                                while (@as < ae && bs < be)
 
118
                                {
 
119
                                        byte ac = a.content[@as];
 
120
                                        byte bc = b.content[bs];
 
121
                                        while (@as < ae - 1 && RawCharUtil.IsWhitespace(ac))
 
122
                                        {
 
123
                                                @as++;
 
124
                                                ac = a.content[@as];
 
125
                                        }
 
126
                                        while (bs < be - 1 && RawCharUtil.IsWhitespace(bc))
 
127
                                        {
 
128
                                                bs++;
 
129
                                                bc = b.content[bs];
 
130
                                        }
 
131
                                        if (ac != bc)
 
132
                                        {
 
133
                                                return false;
 
134
                                        }
 
135
                                        @as++;
 
136
                                        bs++;
 
137
                                }
 
138
                                return @as == ae && bs == be;
 
139
                        }
 
140
 
 
141
                        protected internal override int HashRegion(byte[] raw, int ptr, int end)
 
142
                        {
 
143
                                int hash = 5381;
 
144
                                for (; ptr < end; ptr++)
 
145
                                {
 
146
                                        byte c = raw[ptr];
 
147
                                        if (!RawCharUtil.IsWhitespace(c))
 
148
                                        {
 
149
                                                hash = ((hash << 5) + hash) + (c & unchecked((int)(0xff)));
 
150
                                        }
 
151
                                }
 
152
                                return hash;
 
153
                        }
 
154
                }
 
155
 
 
156
                /// <summary>Ignores all whitespace.</summary>
 
157
                /// <remarks>Ignores all whitespace.</remarks>
 
158
                public static readonly RawTextComparator WS_IGNORE_ALL = new _RawTextComparator_87
 
159
                        ();
 
160
 
 
161
                private sealed class _RawTextComparator_138 : RawTextComparator
 
162
                {
 
163
                        public _RawTextComparator_138()
 
164
                        {
 
165
                        }
 
166
 
 
167
                        public override bool Equals(RawText a, int ai, RawText b, int bi)
 
168
                        {
 
169
                                ai++;
 
170
                                bi++;
 
171
                                int @as = a.lines.Get(ai);
 
172
                                int bs = b.lines.Get(bi);
 
173
                                int ae = a.lines.Get(ai + 1);
 
174
                                int be = b.lines.Get(bi + 1);
 
175
                                @as = RawCharUtil.TrimLeadingWhitespace(a.content, @as, ae);
 
176
                                bs = RawCharUtil.TrimLeadingWhitespace(b.content, bs, be);
 
177
                                if (ae - @as != be - bs)
 
178
                                {
 
179
                                        return false;
 
180
                                }
 
181
                                while (@as < ae)
 
182
                                {
 
183
                                        if (a.content[@as++] != b.content[bs++])
 
184
                                        {
 
185
                                                return false;
 
186
                                        }
 
187
                                }
 
188
                                return true;
 
189
                        }
 
190
 
 
191
                        protected internal override int HashRegion(byte[] raw, int ptr, int end)
 
192
                        {
 
193
                                int hash = 5381;
 
194
                                ptr = RawCharUtil.TrimLeadingWhitespace(raw, ptr, end);
 
195
                                for (; ptr < end; ptr++)
 
196
                                {
 
197
                                        hash = ((hash << 5) + hash) + (raw[ptr] & unchecked((int)(0xff)));
 
198
                                }
 
199
                                return hash;
 
200
                        }
 
201
                }
 
202
 
 
203
                /// <summary>Ignores leading whitespace.</summary>
 
204
                /// <remarks>Ignores leading whitespace.</remarks>
 
205
                public static readonly RawTextComparator WS_IGNORE_LEADING = new _RawTextComparator_138
 
206
                        ();
 
207
 
 
208
                private sealed class _RawTextComparator_173 : RawTextComparator
 
209
                {
 
210
                        public _RawTextComparator_173()
 
211
                        {
 
212
                        }
 
213
 
 
214
                        public override bool Equals(RawText a, int ai, RawText b, int bi)
 
215
                        {
 
216
                                ai++;
 
217
                                bi++;
 
218
                                int @as = a.lines.Get(ai);
 
219
                                int bs = b.lines.Get(bi);
 
220
                                int ae = a.lines.Get(ai + 1);
 
221
                                int be = b.lines.Get(bi + 1);
 
222
                                ae = RawCharUtil.TrimTrailingWhitespace(a.content, @as, ae);
 
223
                                be = RawCharUtil.TrimTrailingWhitespace(b.content, bs, be);
 
224
                                if (ae - @as != be - bs)
 
225
                                {
 
226
                                        return false;
 
227
                                }
 
228
                                while (@as < ae)
 
229
                                {
 
230
                                        if (a.content[@as++] != b.content[bs++])
 
231
                                        {
 
232
                                                return false;
 
233
                                        }
 
234
                                }
 
235
                                return true;
 
236
                        }
 
237
 
 
238
                        protected internal override int HashRegion(byte[] raw, int ptr, int end)
 
239
                        {
 
240
                                int hash = 5381;
 
241
                                end = RawCharUtil.TrimTrailingWhitespace(raw, ptr, end);
 
242
                                for (; ptr < end; ptr++)
 
243
                                {
 
244
                                        hash = ((hash << 5) + hash) + (raw[ptr] & unchecked((int)(0xff)));
 
245
                                }
 
246
                                return hash;
 
247
                        }
 
248
                }
 
249
 
 
250
                /// <summary>Ignores trailing whitespace.</summary>
 
251
                /// <remarks>Ignores trailing whitespace.</remarks>
 
252
                public static readonly RawTextComparator WS_IGNORE_TRAILING = new _RawTextComparator_173
 
253
                        ();
 
254
 
 
255
                private sealed class _RawTextComparator_208 : RawTextComparator
 
256
                {
 
257
                        public _RawTextComparator_208()
 
258
                        {
 
259
                        }
 
260
 
 
261
                        public override bool Equals(RawText a, int ai, RawText b, int bi)
 
262
                        {
 
263
                                ai++;
 
264
                                bi++;
 
265
                                int @as = a.lines.Get(ai);
 
266
                                int bs = b.lines.Get(bi);
 
267
                                int ae = a.lines.Get(ai + 1);
 
268
                                int be = b.lines.Get(bi + 1);
 
269
                                ae = RawCharUtil.TrimTrailingWhitespace(a.content, @as, ae);
 
270
                                be = RawCharUtil.TrimTrailingWhitespace(b.content, bs, be);
 
271
                                while (@as < ae && bs < be)
 
272
                                {
 
273
                                        byte ac = a.content[@as];
 
274
                                        byte bc = b.content[bs];
 
275
                                        if (ac != bc)
 
276
                                        {
 
277
                                                return false;
 
278
                                        }
 
279
                                        if (RawCharUtil.IsWhitespace(ac))
 
280
                                        {
 
281
                                                @as = RawCharUtil.TrimLeadingWhitespace(a.content, @as, ae);
 
282
                                        }
 
283
                                        else
 
284
                                        {
 
285
                                                @as++;
 
286
                                        }
 
287
                                        if (RawCharUtil.IsWhitespace(bc))
 
288
                                        {
 
289
                                                bs = RawCharUtil.TrimLeadingWhitespace(b.content, bs, be);
 
290
                                        }
 
291
                                        else
 
292
                                        {
 
293
                                                bs++;
 
294
                                        }
 
295
                                }
 
296
                                return @as == ae && bs == be;
 
297
                        }
 
298
 
 
299
                        protected internal override int HashRegion(byte[] raw, int ptr, int end)
 
300
                        {
 
301
                                int hash = 5381;
 
302
                                end = RawCharUtil.TrimTrailingWhitespace(raw, ptr, end);
 
303
                                while (ptr < end)
 
304
                                {
 
305
                                        byte c = raw[ptr];
 
306
                                        hash = ((hash << 5) + hash) + (c & unchecked((int)(0xff)));
 
307
                                        if (RawCharUtil.IsWhitespace(c))
 
308
                                        {
 
309
                                                ptr = RawCharUtil.TrimLeadingWhitespace(raw, ptr, end);
 
310
                                        }
 
311
                                        else
 
312
                                        {
 
313
                                                ptr++;
 
314
                                        }
 
315
                                }
 
316
                                return hash;
 
317
                        }
 
318
                }
 
319
 
 
320
                /// <summary>Ignores whitespace occurring between non-whitespace characters.</summary>
 
321
                /// <remarks>Ignores whitespace occurring between non-whitespace characters.</remarks>
 
322
                public static readonly RawTextComparator WS_IGNORE_CHANGE = new _RawTextComparator_208
 
323
                        ();
 
324
 
 
325
                public override int Hash(RawText seq, int lno)
 
326
                {
 
327
                        int begin = seq.lines.Get(lno + 1);
 
328
                        int end = seq.lines.Get(lno + 2);
 
329
                        return HashRegion(seq.content, begin, end);
 
330
                }
 
331
 
 
332
                public override Edit ReduceCommonStartEnd(RawText a, RawText b, Edit e)
 
333
                {
 
334
                        // This is a faster exact match based form that tries to improve
 
335
                        // performance for the common case of the header and trailer of
 
336
                        // a text file not changing at all. After this fast path we use
 
337
                        // the slower path based on the super class' using equals() to
 
338
                        // allow for whitespace ignore modes to still work.
 
339
                        if (e.beginA == e.endA || e.beginB == e.endB)
 
340
                        {
 
341
                                return e;
 
342
                        }
 
343
                        byte[] aRaw = a.content;
 
344
                        byte[] bRaw = b.content;
 
345
                        int aPtr = a.lines.Get(e.beginA + 1);
 
346
                        int bPtr = a.lines.Get(e.beginB + 1);
 
347
                        int aEnd = a.lines.Get(e.endA + 1);
 
348
                        int bEnd = b.lines.Get(e.endB + 1);
 
349
                        // This can never happen, but the JIT doesn't know that. If we
 
350
                        // define this assertion before the tight while loops below it
 
351
                        // should be able to skip the array bound checks on access.
 
352
                        //
 
353
                        if (aPtr < 0 || bPtr < 0 || aEnd > aRaw.Length || bEnd > bRaw.Length)
 
354
                        {
 
355
                                throw new IndexOutOfRangeException();
 
356
                        }
 
357
                        while (aPtr < aEnd && bPtr < bEnd && aRaw[aPtr] == bRaw[bPtr])
 
358
                        {
 
359
                                aPtr++;
 
360
                                bPtr++;
 
361
                        }
 
362
                        while (aPtr < aEnd && bPtr < bEnd && aRaw[aEnd - 1] == bRaw[bEnd - 1])
 
363
                        {
 
364
                                aEnd--;
 
365
                                bEnd--;
 
366
                        }
 
367
                        e.beginA = FindForwardLine(a.lines, e.beginA, aPtr);
 
368
                        e.beginB = FindForwardLine(b.lines, e.beginB, bPtr);
 
369
                        e.endA = FindReverseLine(a.lines, e.endA, aEnd);
 
370
                        bool partialA = aEnd < a.lines.Get(e.endA + 1);
 
371
                        if (partialA)
 
372
                        {
 
373
                                bEnd += a.lines.Get(e.endA + 1) - aEnd;
 
374
                        }
 
375
                        e.endB = FindReverseLine(b.lines, e.endB, bEnd);
 
376
                        if (!partialA && bEnd < b.lines.Get(e.endB + 1))
 
377
                        {
 
378
                                e.endA++;
 
379
                        }
 
380
                        return base.ReduceCommonStartEnd(a, b, e);
 
381
                }
 
382
 
 
383
                private static int FindForwardLine(IntList lines, int idx, int ptr)
 
384
                {
 
385
                        int end = lines.Size() - 2;
 
386
                        while (idx < end && lines.Get(idx + 2) <= ptr)
 
387
                        {
 
388
                                idx++;
 
389
                        }
 
390
                        return idx;
 
391
                }
 
392
 
 
393
                private static int FindReverseLine(IntList lines, int idx, int ptr)
 
394
                {
 
395
                        while (0 < idx && ptr <= lines.Get(idx))
 
396
                        {
 
397
                                idx--;
 
398
                        }
 
399
                        return idx;
 
400
                }
 
401
 
 
402
                /// <summary>Compute a hash code for a region.</summary>
 
403
                /// <remarks>Compute a hash code for a region.</remarks>
 
404
                /// <param name="raw">the raw file content.</param>
 
405
                /// <param name="ptr">first byte of the region to hash.</param>
 
406
                /// <param name="end">1 past the last byte of the region.</param>
 
407
                /// <returns>hash code for the region <code>[ptr, end)</code> of raw.</returns>
 
408
                protected internal abstract int HashRegion(byte[] raw, int ptr, int end);
 
409
        }
 
410
}