1/*
2 * diff.c :  routines for doing diffs
3 *
4 * ====================================================================
5 *    Licensed to the Apache Software Foundation (ASF) under one
6 *    or more contributor license agreements.  See the NOTICE file
7 *    distributed with this work for additional information
8 *    regarding copyright ownership.  The ASF licenses this file
9 *    to you under the Apache License, Version 2.0 (the
10 *    "License"); you may not use this file except in compliance
11 *    with the License.  You may obtain a copy of the License at
12 *
13 *      http://www.apache.org/licenses/LICENSE-2.0
14 *
15 *    Unless required by applicable law or agreed to in writing,
16 *    software distributed under the License is distributed on an
17 *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 *    KIND, either express or implied.  See the License for the
19 *    specific language governing permissions and limitations
20 *    under the License.
21 * ====================================================================
22 */
23
24
25#include <apr.h>
26#include <apr_pools.h>
27#include <apr_general.h>
28
29#include "svn_pools.h"
30#include "svn_error.h"
31#include "svn_diff.h"
32#include "svn_types.h"
33
34#include "diff.h"
35
36
37svn_diff__token_index_t*
38svn_diff__get_token_counts(svn_diff__position_t *loop_start,
39                           svn_diff__token_index_t num_tokens,
40                           apr_pool_t *pool)
41{
42  svn_diff__token_index_t *token_counts;
43  svn_diff__token_index_t token_index;
44  svn_diff__position_t *current;
45
46  token_counts = apr_palloc(pool, num_tokens * sizeof(*token_counts));
47  for (token_index = 0; token_index < num_tokens; token_index++)
48    token_counts[token_index] = 0;
49
50  current = loop_start;
51  if (current != NULL)
52    {
53      do
54        {
55          token_counts[current->token_index]++;
56          current = current->next;
57        }
58      while (current != loop_start);
59    }
60
61  return token_counts;
62}
63
64
65svn_diff_t *
66svn_diff__diff(svn_diff__lcs_t *lcs,
67               apr_off_t original_start, apr_off_t modified_start,
68               svn_boolean_t want_common,
69               apr_pool_t *pool)
70{
71  svn_diff_t *diff;
72  svn_diff_t **diff_ref = &diff;
73
74  while (1)
75    {
76      if (original_start < lcs->position[0]->offset
77          || modified_start < lcs->position[1]->offset)
78      {
79          (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref));
80
81          (*diff_ref)->type = svn_diff__type_diff_modified;
82          (*diff_ref)->original_start = original_start - 1;
83          (*diff_ref)->original_length =
84            lcs->position[0]->offset - original_start;
85          (*diff_ref)->modified_start = modified_start - 1;
86          (*diff_ref)->modified_length =
87            lcs->position[1]->offset - modified_start;
88          (*diff_ref)->latest_start = 0;
89          (*diff_ref)->latest_length = 0;
90
91          diff_ref = &(*diff_ref)->next;
92      }
93
94      /* Detect the EOF */
95      if (lcs->length == 0)
96          break;
97
98      original_start = lcs->position[0]->offset;
99      modified_start = lcs->position[1]->offset;
100
101      if (want_common)
102        {
103          (*diff_ref) = apr_palloc(pool, sizeof(**diff_ref));
104
105          (*diff_ref)->type = svn_diff__type_common;
106          (*diff_ref)->original_start = original_start - 1;
107          (*diff_ref)->original_length = lcs->length;
108          (*diff_ref)->modified_start = modified_start - 1;
109          (*diff_ref)->modified_length = lcs->length;
110          (*diff_ref)->latest_start = 0;
111          (*diff_ref)->latest_length = 0;
112
113          diff_ref = &(*diff_ref)->next;
114        }
115
116      original_start += lcs->length;
117      modified_start += lcs->length;
118
119      lcs = lcs->next;
120    }
121
122  *diff_ref = NULL;
123
124  return diff;
125}
126
127
128svn_error_t *
129svn_diff_diff_2(svn_diff_t **diff,
130                void *diff_baton,
131                const svn_diff_fns2_t *vtable,
132                apr_pool_t *pool)
133{
134  svn_diff__tree_t *tree;
135  svn_diff__position_t *position_list[2];
136  svn_diff__token_index_t num_tokens;
137  svn_diff__token_index_t *token_counts[2];
138  svn_diff_datasource_e datasource[] = {svn_diff_datasource_original,
139                                        svn_diff_datasource_modified};
140  svn_diff__lcs_t *lcs;
141  apr_pool_t *subpool;
142  apr_pool_t *treepool;
143  apr_off_t prefix_lines = 0;
144  apr_off_t suffix_lines = 0;
145
146  *diff = NULL;
147
148  subpool = svn_pool_create(pool);
149  treepool = svn_pool_create(pool);
150
151  svn_diff__tree_create(&tree, treepool);
152
153  SVN_ERR(vtable->datasources_open(diff_baton, &prefix_lines, &suffix_lines,
154                                   datasource, 2));
155
156  /* Insert the data into the tree */
157  SVN_ERR(svn_diff__get_tokens(&position_list[0],
158                               tree,
159                               diff_baton, vtable,
160                               svn_diff_datasource_original,
161                               prefix_lines,
162                               subpool));
163
164  SVN_ERR(svn_diff__get_tokens(&position_list[1],
165                               tree,
166                               diff_baton, vtable,
167                               svn_diff_datasource_modified,
168                               prefix_lines,
169                               subpool));
170
171  num_tokens = svn_diff__get_node_count(tree);
172
173  /* The cool part is that we don't need the tokens anymore.
174   * Allow the app to clean them up if it wants to.
175   */
176  if (vtable->token_discard_all != NULL)
177    vtable->token_discard_all(diff_baton);
178
179  /* We don't need the nodes in the tree either anymore, nor the tree itself */
180  svn_pool_destroy(treepool);
181
182  token_counts[0] = svn_diff__get_token_counts(position_list[0], num_tokens,
183                                               subpool);
184  token_counts[1] = svn_diff__get_token_counts(position_list[1], num_tokens,
185                                               subpool);
186
187  /* Get the lcs */
188  lcs = svn_diff__lcs(position_list[0], position_list[1], token_counts[0],
189                      token_counts[1], num_tokens, prefix_lines,
190                      suffix_lines, subpool);
191
192  /* Produce the diff */
193  *diff = svn_diff__diff(lcs, 1, 1, TRUE, pool);
194
195  /* Get rid of all the data we don't have a use for anymore */
196  svn_pool_destroy(subpool);
197
198  return SVN_NO_ERROR;
199}
200