contrib/subversion/subversion/libsvn_diff/diff.c

   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
  37 svn_diff__token_index_t*
  38 svn_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
  65 svn_diff_t *
  66 svn_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
 128 svn_error_t *
 129 svn_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 }