File: diff4.c

package info (click to toggle)
subversion 1.8.10-6+deb8u6
  • links: PTS, VCS
  • area: main
  • in suites: jessie
  • size: 62,080 kB
  • sloc: ansic: 795,684; python: 115,859; java: 17,742; sh: 13,590; ruby: 12,397; cpp: 11,206; lisp: 7,540; perl: 5,649; sql: 1,466; makefile: 1,110; xml: 577
file content (314 lines) | stat: -rw-r--r-- 11,117 bytes parent folder | download | duplicates (4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
/*
 * diff.c :  routines for doing diffs
 *
 * ====================================================================
 *    Licensed to the Apache Software Foundation (ASF) under one
 *    or more contributor license agreements.  See the NOTICE file
 *    distributed with this work for additional information
 *    regarding copyright ownership.  The ASF licenses this file
 *    to you under the Apache License, Version 2.0 (the
 *    "License"); you may not use this file except in compliance
 *    with the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *    Unless required by applicable law or agreed to in writing,
 *    software distributed under the License is distributed on an
 *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *    KIND, either express or implied.  See the License for the
 *    specific language governing permissions and limitations
 *    under the License.
 * ====================================================================
 */


#include <apr.h>
#include <apr_pools.h>
#include <apr_general.h>

#include "svn_pools.h"
#include "svn_error.h"
#include "svn_diff.h"
#include "svn_types.h"

#include "diff.h"

/*
 * Variance adjustment rules:
 *
 * See notes/variance-adjusted-patching.html
 *
 * ###: Expand this comment to contain the full set of adjustment
 * ###: rules instead of pointing to a webpage.
 */

/*
 * In the text below consider the following:
 *
 * O     = Original
 * M     = Modified
 * L     = Latest
 * A     = Ancestor
 * X:Y   = diff between X and Y
 * X:Y:Z = 3-way diff between X, Y and Z
 * P     = O:L, possibly adjusted
 *
 * diff4 -- Variance adjusted diff algorithm
 *
 * 1. Create a diff O:L and call that P.
 *
 * 2. Morph P into a 3-way diff by performing the following
 *    transformation: O:L -> O:O:L.
 *
 * 3. Create a diff A:O.
 *
 * 4. Using A:O...
 *
 * #. Using M:A...
 *
 * #. Resolve conflicts...
 *

   1. Out-range added line: decrement the line numbers in every hunk in P
      that comes after the addition. This undoes the effect of the add, since
      the add never happened in D.

   2. Out-range deleted line: increment the line numbers in every hunk in P
      that comes after the deletion. This undoes the effect of the deletion,
      since the deletion never happened in D.

   3. Out-range edited line: do nothing. Out-range edits are irrelevant to P.

   4. Added line in context range in P: remove the corresponding line from
      the context, optionally replacing it with new context based on that
      region in M, and adjust line numbers and mappings appropriately.

   5. Added line in affected text range in P: this is a dependency problem
      -- part of the change T:18-T:19 depends on changes introduced to T after
      B branched. There are several possible behaviors, depending on what the
      user wants. One is to generate an informative error, stating that
      T:18-T:19 depends on some other change (T:N-T:M, where N>=8, M<=18,
      and M-N == 1); the exact revisions can be discovered automatically using
      the same process as "cvs annotate", though it may take some time to do
      so. Another option is to include the change in P, as an insertion of the
      "after" version of the text, and adjust line numbers and mappings
      accordingly. (And if all this isn't sounding a lot like a directory
      merge algorithm, try drinking more of the Kool-Aid.) A third option is
      to include it as an insertion, but with metadata (such as CVS-style
      conflict markers) indicating that the line attempting to be patched
      does not exist in B.

   6. Deleted line that is in-range in P: request another universe -- this
      situation can't happen in ours.

   7. In-range edited line: reverse that edit in the "before" version of the
      corresponding line in the appropriate hunk in P, to obtain the version of
      the line that will be found in B when P is applied.
*/


static void
adjust_diff(svn_diff_t *diff, svn_diff_t *adjust)
{
  svn_diff_t *hunk;
  apr_off_t range_start;
  apr_off_t range_end;
  apr_off_t adjustment;

  for (; adjust; adjust = adjust->next)
    {
      range_start = adjust->modified_start;
      range_end = range_start + adjust->modified_length;
      adjustment = adjust->original_length - adjust->modified_length;

      /* No change in line count, so no modifications. [3, 7] */
      if (adjustment == 0)
        continue;

      for (hunk = diff; hunk; hunk = hunk->next)
        {
          /* Changes are in the range before this hunk.  Adjust the start
           * of the hunk. [1, 2]
           */
          if (hunk->modified_start >= range_end)
            {
              hunk->modified_start += adjustment;
              continue;
            }

          /* Changes are in the range beyond this hunk.  No adjustments
           * needed. [1, 2]
           */
          if (hunk->modified_start + hunk->modified_length <= range_start)
            continue;

          /* From here on changes are in the range of this hunk. */

          /* This is a context hunk.  Adjust the length. [4]
           */
          if (hunk->type == svn_diff__type_diff_modified)
            {
              hunk->modified_length += adjustment;
              continue;
            }

          /* Mark as conflicted. This happens in the reverse case when a line
           * is added in range and in the forward case when a line is deleted
           * in range. [5 (reverse), 6 (forward)]
           */
          if (adjustment < 0)
              hunk->type = svn_diff__type_conflict;

          /* Adjust the length of this hunk (reverse the change). [5, 6] */
          hunk->modified_length -= adjustment;
        }
    }
}

svn_error_t *
svn_diff_diff4_2(svn_diff_t **diff,
                 void *diff_baton,
                 const svn_diff_fns2_t *vtable,
                 apr_pool_t *pool)
{
  svn_diff__tree_t *tree;
  svn_diff__position_t *position_list[4];
  svn_diff__token_index_t num_tokens;
  svn_diff__token_index_t *token_counts[4];
  svn_diff_datasource_e datasource[] = {svn_diff_datasource_original,
                                        svn_diff_datasource_modified,
                                        svn_diff_datasource_latest,
                                        svn_diff_datasource_ancestor};
  svn_diff__lcs_t *lcs_ol;
  svn_diff__lcs_t *lcs_adjust;
  svn_diff_t *diff_ol;
  svn_diff_t *diff_adjust;
  svn_diff_t *hunk;
  apr_pool_t *subpool;
  apr_pool_t *subpool2;
  apr_pool_t *subpool3;
  apr_off_t prefix_lines = 0;
  apr_off_t suffix_lines = 0;

  *diff = NULL;

  subpool = svn_pool_create(pool);
  subpool2 = svn_pool_create(subpool);
  subpool3 = svn_pool_create(subpool2);

  svn_diff__tree_create(&tree, subpool3);

  SVN_ERR(vtable->datasources_open(diff_baton, &prefix_lines, &suffix_lines,
                                   datasource, 4));

  SVN_ERR(svn_diff__get_tokens(&position_list[0],
                               tree,
                               diff_baton, vtable,
                               svn_diff_datasource_original,
                               prefix_lines,
                               subpool2));

  SVN_ERR(svn_diff__get_tokens(&position_list[1],
                               tree,
                               diff_baton, vtable,
                               svn_diff_datasource_modified,
                               prefix_lines,
                               subpool));

  SVN_ERR(svn_diff__get_tokens(&position_list[2],
                               tree,
                               diff_baton, vtable,
                               svn_diff_datasource_latest,
                               prefix_lines,
                               subpool));

  SVN_ERR(svn_diff__get_tokens(&position_list[3],
                               tree,
                               diff_baton, vtable,
                               svn_diff_datasource_ancestor,
                               prefix_lines,
                               subpool2));

  num_tokens = svn_diff__get_node_count(tree);

  /* Get rid of the tokens, we don't need them to calc the diff */
  if (vtable->token_discard_all != NULL)
    vtable->token_discard_all(diff_baton);

  /* We don't need the nodes in the tree either anymore, nor the tree itself */
  svn_pool_clear(subpool3);

  token_counts[0] = svn_diff__get_token_counts(position_list[0], num_tokens,
                                               subpool);
  token_counts[1] = svn_diff__get_token_counts(position_list[1], num_tokens,
                                               subpool);
  token_counts[2] = svn_diff__get_token_counts(position_list[2], num_tokens,
                                               subpool);
  token_counts[3] = svn_diff__get_token_counts(position_list[3], num_tokens,
                                               subpool);

  /* Get the lcs for original - latest */
  lcs_ol = svn_diff__lcs(position_list[0], position_list[2],
                         token_counts[0], token_counts[2],
                         num_tokens, prefix_lines,
                         suffix_lines, subpool3);
  diff_ol = svn_diff__diff(lcs_ol, 1, 1, TRUE, pool);

  svn_pool_clear(subpool3);

  for (hunk = diff_ol; hunk; hunk = hunk->next)
    {
      hunk->latest_start = hunk->modified_start;
      hunk->latest_length = hunk->modified_length;
      hunk->modified_start = hunk->original_start;
      hunk->modified_length = hunk->original_length;

      if (hunk->type == svn_diff__type_diff_modified)
          hunk->type = svn_diff__type_diff_latest;
      else
          hunk->type = svn_diff__type_diff_modified;
    }

  /* Get the lcs for common ancestor - original
   * Do reverse adjustements
   */
  lcs_adjust = svn_diff__lcs(position_list[3], position_list[2],
                             token_counts[3], token_counts[2],
                             num_tokens, prefix_lines,
                             suffix_lines, subpool3);
  diff_adjust = svn_diff__diff(lcs_adjust, 1, 1, FALSE, subpool3);
  adjust_diff(diff_ol, diff_adjust);

  svn_pool_clear(subpool3);

  /* Get the lcs for modified - common ancestor
   * Do forward adjustments
   */
  lcs_adjust = svn_diff__lcs(position_list[1], position_list[3],
                             token_counts[1], token_counts[3],
                             num_tokens, prefix_lines,
                             suffix_lines, subpool3);
  diff_adjust = svn_diff__diff(lcs_adjust, 1, 1, FALSE, subpool3);
  adjust_diff(diff_ol, diff_adjust);

  /* Get rid of the position lists for original and ancestor, and delete
   * our scratchpool.
   */
  svn_pool_destroy(subpool2);

  /* Now we try and resolve the conflicts we encountered */
  for (hunk = diff_ol; hunk; hunk = hunk->next)
    {
      if (hunk->type == svn_diff__type_conflict)
        {
          svn_diff__resolve_conflict(hunk, &position_list[1],
                                     &position_list[2], num_tokens, pool);
        }
    }

  svn_pool_destroy(subpool);

  *diff = diff_ol;

  return SVN_NO_ERROR;
}