contrib/subversion/subversion/libsvn_diff/diff_memory.c

   1 /*
   2  * diff_memory.c :  routines for doing diffs on in-memory data
   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 #define WANT_MEMFUNC
  25 #define WANT_STRFUNC
  26 #include <apr.h>
  27 #include <apr_want.h>
  28 #include <apr_tables.h>
  29
  30 #include <assert.h>
  31
  32 #include "svn_diff.h"
  33 #include "svn_pools.h"
  34 #include "svn_types.h"
  35 #include "svn_string.h"
  36 #include "svn_utf.h"
  37 #include "diff.h"
  38 #include "svn_private_config.h"
  39 #include "private/svn_adler32.h"
  40 #include "private/svn_diff_private.h"
  41
  42 typedef struct source_tokens_t
  43 {
  44   /* A token simply is an svn_string_t pointing to
  45      the data of the in-memory data source, containing
  46      the raw token text, with length stored in the string */
  47   apr_array_header_t *tokens;
  48
  49   /* Next token to be consumed */
  50   apr_size_t next_token;
  51
  52   /* The source, containing the in-memory data to be diffed */
  53   const svn_string_t *source;
  54
  55   /* The last token ends with a newline character (sequence) */
  56   svn_boolean_t ends_without_eol;
  57 } source_tokens_t;
  58
  59 typedef struct diff_mem_baton_t
  60 {
  61   /* The tokens for each of the sources */
  62   source_tokens_t sources[4];
  63
  64   /* Normalization buffer; we only ever compare 2 tokens at the same time */
  65   char *normalization_buf[2];
  66
  67   /* Options for normalized comparison of the data sources */
  68   const svn_diff_file_options_t *normalization_options;
  69 } diff_mem_baton_t;
  70
  71
  72 static int
  73 datasource_to_index(svn_diff_datasource_e datasource)
  74 {
  75   switch (datasource)
  76     {
  77     case svn_diff_datasource_original:
  78       return 0;
  79
  80     case svn_diff_datasource_modified:
  81       return 1;
  82
  83     case svn_diff_datasource_latest:
  84       return 2;
  85
  86     case svn_diff_datasource_ancestor:
  87       return 3;
  88     }
  89
  90   return -1;
  91 }
  92
  93
  94 /* Implements svn_diff_fns2_t::datasources_open */
  95 static svn_error_t *
  96 datasources_open(void *baton,
  97                  apr_off_t *prefix_lines,
  98                  apr_off_t *suffix_lines,
  99                  const svn_diff_datasource_e *datasources,
 100                  apr_size_t datasources_len)
 101 {
 102   /* Do nothing: everything is already there and initialized to 0 */
 103   *prefix_lines = 0;
 104   *suffix_lines = 0;
 105   return SVN_NO_ERROR;
 106 }
 107
 108
 109 /* Implements svn_diff_fns2_t::datasource_close */
 110 static svn_error_t *
 111 datasource_close(void *baton, svn_diff_datasource_e datasource)
 112 {
 113   /* Do nothing.  The compare_token function needs previous datasources
 114    * to stay available until all datasources are processed.
 115    */
 116
 117   return SVN_NO_ERROR;
 118 }
 119
 120
 121 /* Implements svn_diff_fns2_t::datasource_get_next_token */
 122 static svn_error_t *
 123 datasource_get_next_token(apr_uint32_t *hash, void **token, void *baton,
 124                           svn_diff_datasource_e datasource)
 125 {
 126   diff_mem_baton_t *mem_baton = baton;
 127   source_tokens_t *src = &(mem_baton->sources[datasource_to_index(datasource)]);
 128
 129   if ((apr_size_t)src->tokens->nelts > src->next_token)
 130     {
 131       /* There are actually tokens to be returned */
 132       char *buf = mem_baton->normalization_buf[0];
 133       svn_string_t *tok = (*token)
 134         = APR_ARRAY_IDX(src->tokens, src->next_token, svn_string_t *);
 135       apr_off_t len = tok->len;
 136       svn_diff__normalize_state_t state
 137         = svn_diff__normalize_state_normal;
 138
 139       svn_diff__normalize_buffer(&buf, &len, &state, tok->data,
 140                                  mem_baton->normalization_options);
 141       *hash = svn__adler32(0, buf, len);
 142       src->next_token++;
 143     }
 144   else
 145     *token = NULL;
 146
 147   return SVN_NO_ERROR;
 148 }
 149
 150 /* Implements svn_diff_fns2_t::token_compare */
 151 static svn_error_t *
 152 token_compare(void *baton, void *token1, void *token2, int *result)
 153 {
 154   /* Implement the same behaviour as diff_file.c:token_compare(),
 155      but be simpler, because we know we'll have all data in memory */
 156   diff_mem_baton_t *btn = baton;
 157   svn_string_t *t1 = token1;
 158   svn_string_t *t2 = token2;
 159   char *buf1 = btn->normalization_buf[0];
 160   char *buf2 = btn->normalization_buf[1];
 161   apr_off_t len1 = t1->len;
 162   apr_off_t len2 = t2->len;
 163   svn_diff__normalize_state_t state = svn_diff__normalize_state_normal;
 164
 165   svn_diff__normalize_buffer(&buf1, &len1, &state, t1->data,
 166                              btn->normalization_options);
 167   state = svn_diff__normalize_state_normal;
 168   svn_diff__normalize_buffer(&buf2, &len2, &state, t2->data,
 169                              btn->normalization_options);
 170
 171   if (len1 != len2)
 172     *result = (len1 < len2) ? -1 : 1;
 173   else
 174     *result = (len1 == 0) ? 0 : memcmp(buf1, buf2, (size_t) len1);
 175
 176   return SVN_NO_ERROR;
 177 }
 178
 179 /* Implements svn_diff_fns2_t::token_discard */
 180 static void
 181 token_discard(void *baton, void *token)
 182 {
 183   /* No-op, we have no use for discarded tokens... */
 184 }
 185
 186
 187 /* Implements svn_diff_fns2_t::token_discard_all */
 188 static void
 189 token_discard_all(void *baton)
 190 {
 191   /* Do nothing.
 192      Note that in the file case, this function discards all
 193      tokens allocated, but we're geared toward small in-memory diffs.
 194      Meaning that there's no special pool to clear.
 195   */
 196 }
 197
 198
 199 static const svn_diff_fns2_t svn_diff__mem_vtable =
 200 {
 201   datasources_open,
 202   datasource_close,
 203   datasource_get_next_token,
 204   token_compare,
 205   token_discard,
 206   token_discard_all
 207 };
 208
 209 /* Fill SRC with the diff tokens (e.g. lines).
 210
 211    TEXT is assumed to live long enough for the tokens to
 212    stay valid during their lifetime: no data is copied,
 213    instead, svn_string_t's are allocated pointing straight
 214    into TEXT.
 215 */
 216 static void
 217 fill_source_tokens(source_tokens_t *src,
 218                    const svn_string_t *text,
 219                    apr_pool_t *pool)
 220 {
 221   const char *curp;
 222   const char *endp;
 223   const char *startp;
 224
 225   src->tokens = apr_array_make(pool, 0, sizeof(svn_string_t *));
 226   src->next_token = 0;
 227   src->source = text;
 228
 229   for (startp = curp = text->data, endp = curp + text->len;
 230        curp != endp; curp++)
 231     {
 232       if (curp != endp && *curp == '\r' && *(curp + 1) == '\n')
 233         curp++;
 234
 235       if (*curp == '\r' || *curp == '\n')
 236         {
 237           APR_ARRAY_PUSH(src->tokens, svn_string_t *) =
 238             svn_string_ncreate(startp, curp - startp + 1, pool);
 239
 240           startp = curp + 1;
 241         }
 242     }
 243
 244   /* If there's anything remaining (ie last line doesn't have a newline) */
 245   if (startp != endp)
 246     {
 247       APR_ARRAY_PUSH(src->tokens, svn_string_t *) =
 248         svn_string_ncreate(startp, endp - startp, pool);
 249       src->ends_without_eol = TRUE;
 250     }
 251   else
 252     src->ends_without_eol = FALSE;
 253 }
 254
 255
 256 static void
 257 alloc_normalization_bufs(diff_mem_baton_t *btn,
 258                          int sources,
 259                          apr_pool_t *pool)
 260 {
 261   apr_size_t max_len = 0;
 262   apr_off_t idx;
 263   int i;
 264
 265   for (i = 0; i < sources; i++)
 266     {
 267       apr_array_header_t *tokens = btn->sources[i].tokens;
 268       if (tokens->nelts > 0)
 269         for (idx = 0; idx < tokens->nelts; idx++)
 270           {
 271             apr_size_t token_len
 272               = APR_ARRAY_IDX(tokens, idx, svn_string_t *)->len;
 273             max_len = (max_len < token_len) ? token_len : max_len;
 274           }
 275     }
 276
 277   btn->normalization_buf[0] = apr_palloc(pool, max_len);
 278   btn->normalization_buf[1] = apr_palloc(pool, max_len);
 279 }
 280
 281 svn_error_t *
 282 svn_diff_mem_string_diff(svn_diff_t **diff,
 283                          const svn_string_t *original,
 284                          const svn_string_t *modified,
 285                          const svn_diff_file_options_t *options,
 286                          apr_pool_t *pool)
 287 {
 288   diff_mem_baton_t baton;
 289
 290   fill_source_tokens(&(baton.sources[0]), original, pool);
 291   fill_source_tokens(&(baton.sources[1]), modified, pool);
 292   alloc_normalization_bufs(&baton, 2, pool);
 293
 294   baton.normalization_options = options;
 295
 296   return svn_diff_diff_2(diff, &baton, &svn_diff__mem_vtable, pool);
 297 }
 298
 299 svn_error_t *
 300 svn_diff_mem_string_diff3(svn_diff_t **diff,
 301                           const svn_string_t *original,
 302                           const svn_string_t *modified,
 303                           const svn_string_t *latest,
 304                           const svn_diff_file_options_t *options,
 305                           apr_pool_t *pool)
 306 {
 307   diff_mem_baton_t baton;
 308
 309   fill_source_tokens(&(baton.sources[0]), original, pool);
 310   fill_source_tokens(&(baton.sources[1]), modified, pool);
 311   fill_source_tokens(&(baton.sources[2]), latest, pool);
 312   alloc_normalization_bufs(&baton, 3, pool);
 313
 314   baton.normalization_options = options;
 315
 316   return svn_diff_diff3_2(diff, &baton, &svn_diff__mem_vtable, pool);
 317 }
 318
 319
 320 svn_error_t *
 321 svn_diff_mem_string_diff4(svn_diff_t **diff,
 322                           const svn_string_t *original,
 323                           const svn_string_t *modified,
 324                           const svn_string_t *latest,
 325                           const svn_string_t *ancestor,
 326                           const svn_diff_file_options_t *options,
 327                           apr_pool_t *pool)
 328 {
 329   diff_mem_baton_t baton;
 330
 331   fill_source_tokens(&(baton.sources[0]), original, pool);
 332   fill_source_tokens(&(baton.sources[1]), modified, pool);
 333   fill_source_tokens(&(baton.sources[2]), latest, pool);
 334   fill_source_tokens(&(baton.sources[3]), ancestor, pool);
 335   alloc_normalization_bufs(&baton, 4, pool);
 336
 337   baton.normalization_options = options;
 338
 339   return svn_diff_diff4_2(diff, &baton, &svn_diff__mem_vtable, pool);
 340 }
 341
 342
 343 typedef enum unified_output_e
 344 {
 345   unified_output_context = 0,
 346   unified_output_delete,
 347   unified_output_insert,
 348   unified_output_skip
 349 } unified_output_e;
 350
 351 /* Baton for generating unified diffs */
 352 typedef struct unified_output_baton_t
 353 {
 354   svn_stream_t *output_stream;
 355   const char *header_encoding;
 356   source_tokens_t sources[2]; /* 0 == original; 1 == modified */
 357   apr_off_t current_token[2]; /* current token per source */
 358
 359   int context_size;
 360
 361   /* Cached markers, in header_encoding,
 362      indexed using unified_output_e */
 363   const char *prefix_str[3];
 364
 365   svn_stringbuf_t *hunk;    /* in-progress hunk data */
 366   apr_off_t hunk_length[2]; /* 0 == original; 1 == modified */
 367   apr_off_t hunk_start[2];  /* 0 == original; 1 == modified */
 368
 369   /* The delimiters of the hunk header, '@@' for text hunks and '##' for
 370    * property hunks. */
 371   const char *hunk_delimiter;
 372   /* The string to print after a line that does not end with a newline.
 373    * It must start with a '\'.  Typically "\ No newline at end of file". */
 374   const char *no_newline_string;
 375
 376   /* Pool for allocation of temporary memory in the callbacks
 377      Should be cleared on entry of each iteration of a callback */
 378   apr_pool_t *pool;
 379 } output_baton_t;
 380
 381
 382 /* Append tokens (lines) FIRST up to PAST_LAST
 383    from token-source index TOKENS with change-type TYPE
 384    to the current hunk.
 385 */
 386 static svn_error_t *
 387 output_unified_token_range(output_baton_t *btn,
 388                            int tokens,
 389                            unified_output_e type,
 390                            apr_off_t until)
 391 {
 392   source_tokens_t *source = &btn->sources[tokens];
 393
 394   if (until > source->tokens->nelts)
 395     until = source->tokens->nelts;
 396
 397   if (until <= btn->current_token[tokens])
 398     return SVN_NO_ERROR;
 399
 400   /* Do the loop with prefix and token */
 401   while (TRUE)
 402     {
 403       svn_string_t *token =
 404         APR_ARRAY_IDX(source->tokens, btn->current_token[tokens],
 405                       svn_string_t *);
 406
 407       if (type != unified_output_skip)
 408         {
 409           svn_stringbuf_appendcstr(btn->hunk, btn->prefix_str[type]);
 410           svn_stringbuf_appendbytes(btn->hunk, token->data, token->len);
 411         }
 412
 413       if (type == unified_output_context)
 414         {
 415           btn->hunk_length[0]++;
 416           btn->hunk_length[1]++;
 417         }
 418       else if (type == unified_output_delete)
 419         btn->hunk_length[0]++;
 420       else if (type == unified_output_insert)
 421         btn->hunk_length[1]++;
 422
 423       /* ### TODO: Add skip processing for -p handling? */
 424
 425       btn->current_token[tokens]++;
 426       if (btn->current_token[tokens] == until)
 427         break;
 428     }
 429
 430   if (btn->current_token[tokens] == source->tokens->nelts
 431       && source->ends_without_eol)
 432     {
 433       const char *out_str;
 434
 435       SVN_ERR(svn_utf_cstring_from_utf8_ex2(
 436                 &out_str, btn->no_newline_string,
 437                 btn->header_encoding, btn->pool));
 438       svn_stringbuf_appendcstr(btn->hunk, out_str);
 439     }
 440
 441
 442
 443   return SVN_NO_ERROR;
 444 }
 445
 446 /* Flush the hunk currently built up in BATON
 447    into the BATON's output_stream.
 448    Use the specified HUNK_DELIMITER.
 449    If HUNK_DELIMITER is NULL, fall back to the default delimiter. */
 450 static svn_error_t *
 451 output_unified_flush_hunk(output_baton_t *baton,
 452                           const char *hunk_delimiter)
 453 {
 454   apr_off_t target_token;
 455   apr_size_t hunk_len;
 456   apr_off_t old_start;
 457   apr_off_t new_start;
 458
 459   if (svn_stringbuf_isempty(baton->hunk))
 460     return SVN_NO_ERROR;
 461
 462   svn_pool_clear(baton->pool);
 463
 464   /* Write the trailing context */
 465   target_token = baton->hunk_start[0] + baton->hunk_length[0]
 466                  + baton->context_size;
 467   SVN_ERR(output_unified_token_range(baton, 0 /*original*/,
 468                                      unified_output_context,
 469                                      target_token));
 470   if (hunk_delimiter == NULL)
 471     hunk_delimiter = "@@";
 472
 473   old_start = baton->hunk_start[0];
 474   new_start = baton->hunk_start[1];
 475
 476   /* If the file is non-empty, convert the line indexes from
 477      zero based to one based */
 478   if (baton->hunk_length[0])
 479     old_start++;
 480   if (baton->hunk_length[1])
 481     new_start++;
 482
 483   /* Write the hunk header */
 484   SVN_ERR(svn_diff__unified_write_hunk_header(
 485             baton->output_stream, baton->header_encoding, hunk_delimiter,
 486             old_start, baton->hunk_length[0],
 487             new_start, baton->hunk_length[1],
 488             NULL /* hunk_extra_context */,
 489             baton->pool));
 490
 491   hunk_len = baton->hunk->len;
 492   SVN_ERR(svn_stream_write(baton->output_stream,
 493                            baton->hunk->data, &hunk_len));
 494
 495   /* Prepare for the next hunk */
 496   baton->hunk_length[0] = 0;
 497   baton->hunk_length[1] = 0;
 498   baton->hunk_start[0] = 0;
 499   baton->hunk_start[1] = 0;
 500   svn_stringbuf_setempty(baton->hunk);
 501
 502   return SVN_NO_ERROR;
 503 }
 504
 505 /* Implements svn_diff_output_fns_t::output_diff_modified */
 506 static svn_error_t *
 507 output_unified_diff_modified(void *baton,
 508                              apr_off_t original_start,
 509                              apr_off_t original_length,
 510                              apr_off_t modified_start,
 511                              apr_off_t modified_length,
 512                              apr_off_t latest_start,
 513                              apr_off_t latest_length)
 514 {
 515   output_baton_t *output_baton = baton;
 516   apr_off_t context_prefix_length;
 517   apr_off_t prev_context_end;
 518   svn_boolean_t init_hunk = FALSE;
 519
 520   if (original_start > output_baton->context_size)
 521     context_prefix_length = output_baton->context_size;
 522   else
 523     context_prefix_length = original_start;
 524
 525   /* Calculate where the previous hunk will end if we would write it now
 526      (including the necessary context at the end) */
 527   if (output_baton->hunk_length[0] > 0 || output_baton->hunk_length[1] > 0)
 528     {
 529       prev_context_end = output_baton->hunk_start[0]
 530                          + output_baton->hunk_length[0]
 531                          + output_baton->context_size;
 532     }
 533   else
 534     {
 535       prev_context_end = -1;
 536
 537       if (output_baton->hunk_start[0] == 0
 538           && (original_length > 0 || modified_length > 0))
 539         init_hunk = TRUE;
 540     }
 541
 542   /* If the changed range is far enough from the previous range, flush the current
 543      hunk. */
 544   {
 545     apr_off_t new_hunk_start = (original_start - context_prefix_length);
 546
 547     if (output_baton->current_token[0] < new_hunk_start
 548           && prev_context_end <= new_hunk_start)
 549       {
 550         SVN_ERR(output_unified_flush_hunk(output_baton,
 551                                           output_baton->hunk_delimiter));
 552         init_hunk = TRUE;
 553       }
 554     else if (output_baton->hunk_length[0] > 0
 555              || output_baton->hunk_length[1] > 0)
 556       {
 557         /* We extend the current hunk */
 558
 559         /* Original: Output the context preceding the changed range */
 560         SVN_ERR(output_unified_token_range(output_baton, 0 /* original */,
 561                                            unified_output_context,
 562                                            original_start));
 563       }
 564   }
 565
 566   /* Original: Skip lines until we are at the beginning of the context we want
 567      to display */
 568   SVN_ERR(output_unified_token_range(output_baton, 0 /* original */,
 569                                      unified_output_skip,
 570                                      original_start - context_prefix_length));
 571
 572   if (init_hunk)
 573     {
 574       SVN_ERR_ASSERT(output_baton->hunk_length[0] == 0
 575                      && output_baton->hunk_length[1] == 0);
 576
 577       output_baton->hunk_start[0] = original_start - context_prefix_length;
 578       output_baton->hunk_start[1] = modified_start - context_prefix_length;
 579     }
 580
 581   /* Modified: Skip lines until we are at the start of the changed range */
 582   SVN_ERR(output_unified_token_range(output_baton, 1 /* modified */,
 583                                      unified_output_skip,
 584                                      modified_start));
 585
 586   /* Original: Output the context preceding the changed range */
 587   SVN_ERR(output_unified_token_range(output_baton, 0 /* original */,
 588                                     unified_output_context,
 589                                     original_start));
 590
 591   /* Both: Output the changed range */
 592   SVN_ERR(output_unified_token_range(output_baton, 0 /* original */,
 593                                      unified_output_delete,
 594                                      original_start + original_length));
 595   SVN_ERR(output_unified_token_range(output_baton, 1 /* modified */,
 596                                      unified_output_insert,
 597                                      modified_start + modified_length));
 598
 599   return SVN_NO_ERROR;
 600 }
 601
 602 static const svn_diff_output_fns_t mem_output_unified_vtable =
 603 {
 604   NULL, /* output_common */
 605   output_unified_diff_modified,
 606   NULL, /* output_diff_latest */
 607   NULL, /* output_diff_common */
 608   NULL  /* output_conflict */
 609 };
 610
 611
 612 svn_error_t *
 613 svn_diff_mem_string_output_unified3(svn_stream_t *output_stream,
 614                                     svn_diff_t *diff,
 615                                     svn_boolean_t with_diff_header,
 616                                     const char *hunk_delimiter,
 617                                     const char *original_header,
 618                                     const char *modified_header,
 619                                     const char *header_encoding,
 620                                     const svn_string_t *original,
 621                                     const svn_string_t *modified,
 622                                     int context_size,
 623                                     svn_cancel_func_t cancel_func,
 624                                     void *cancel_baton,
 625                                     apr_pool_t *scratch_pool)
 626 {
 627
 628   if (svn_diff_contains_diffs(diff))
 629     {
 630       output_baton_t baton;
 631
 632       memset(&baton, 0, sizeof(baton));
 633       baton.output_stream = output_stream;
 634       baton.pool = svn_pool_create(scratch_pool);
 635       baton.header_encoding = header_encoding;
 636       baton.hunk = svn_stringbuf_create_empty(scratch_pool);
 637       baton.hunk_delimiter = hunk_delimiter;
 638       baton.no_newline_string
 639         = (hunk_delimiter == NULL || strcmp(hunk_delimiter, "##") != 0)
 640           ? APR_EOL_STR SVN_DIFF__NO_NEWLINE_AT_END_OF_FILE APR_EOL_STR
 641           : APR_EOL_STR SVN_DIFF__NO_NEWLINE_AT_END_OF_PROPERTY APR_EOL_STR;
 642       baton.context_size = context_size >= 0 ? context_size
 643                                              : SVN_DIFF__UNIFIED_CONTEXT_SIZE;
 644
 645       SVN_ERR(svn_utf_cstring_from_utf8_ex2
 646               (&(baton.prefix_str[unified_output_context]), " ",
 647                header_encoding, scratch_pool));
 648       SVN_ERR(svn_utf_cstring_from_utf8_ex2
 649               (&(baton.prefix_str[unified_output_delete]), "-",
 650                header_encoding, scratch_pool));
 651       SVN_ERR(svn_utf_cstring_from_utf8_ex2
 652               (&(baton.prefix_str[unified_output_insert]), "+",
 653                header_encoding, scratch_pool));
 654
 655       fill_source_tokens(&baton.sources[0], original, scratch_pool);
 656       fill_source_tokens(&baton.sources[1], modified, scratch_pool);
 657
 658       if (with_diff_header)
 659         {
 660           SVN_ERR(svn_diff__unidiff_write_header(
 661                     output_stream, header_encoding,
 662                     original_header, modified_header, scratch_pool));
 663         }
 664
 665       SVN_ERR(svn_diff_output2(diff, &baton,
 666                               &mem_output_unified_vtable,
 667                               cancel_func, cancel_baton));
 668
 669       SVN_ERR(output_unified_flush_hunk(&baton, hunk_delimiter));
 670
 671       svn_pool_destroy(baton.pool);
 672     }
 673
 674   return SVN_NO_ERROR;
 675 }
 676
 677
 678
 679 \f
 680 /* diff3 merge output */
 681
 682 /* A stream to remember *leading* context.  Note that this stream does
 683    *not* copy the data that it is remembering; it just saves
 684    *pointers! */
 685 typedef struct context_saver_t {
 686   svn_stream_t *stream;
 687   int context_size;
 688   const char **data; /* const char *data[context_size] */
 689   apr_size_t *len;   /* apr_size_t len[context_size] */
 690   apr_size_t next_slot;
 691   apr_size_t total_written;
 692 } context_saver_t;
 693
 694
 695 static svn_error_t *
 696 context_saver_stream_write(void *baton,
 697                            const char *data,
 698                            apr_size_t *len)
 699 {
 700   context_saver_t *cs = baton;
 701   cs->data[cs->next_slot] = data;
 702   cs->len[cs->next_slot] = *len;
 703   cs->next_slot = (cs->next_slot + 1) % cs->context_size;
 704   cs->total_written++;
 705   return SVN_NO_ERROR;
 706 }
 707
 708
 709 typedef struct merge_output_baton_t
 710 {
 711   svn_stream_t *output_stream;
 712
 713   /* Tokenized source text */
 714   source_tokens_t sources[3];
 715   apr_off_t next_token[3];
 716
 717   /* Markers for marking conflicted sections */
 718   const char *markers[4]; /* 0 = original, 1 = modified,
 719                              2 = separator, 3 = latest (end) */
 720   const char *marker_eol;
 721
 722   svn_diff_conflict_display_style_t conflict_style;
 723   int context_size;
 724
 725   /* cancel support */
 726   svn_cancel_func_t cancel_func;
 727   void *cancel_baton;
 728
 729   /* The rest of the fields are for
 730      svn_diff_conflict_display_only_conflicts only.  Note that for
 731      these batons, OUTPUT_STREAM is either CONTEXT_SAVER->STREAM or
 732      (soon after a conflict) a "trailing context stream", never the
 733      actual output stream.*/
 734   /* The actual output stream. */
 735   svn_stream_t *real_output_stream;
 736   context_saver_t *context_saver;
 737   /* Used to allocate context_saver and trailing context streams, and
 738      for some printfs. */
 739   apr_pool_t *pool;
 740 } merge_output_baton_t;
 741
 742
 743 static svn_error_t *
 744 flush_context_saver(context_saver_t *cs,
 745                     svn_stream_t *output_stream)
 746 {
 747   int i;
 748   for (i = 0; i < cs->context_size; i++)
 749     {
 750       apr_size_t slot = (i + cs->next_slot) % cs->context_size;
 751       if (cs->data[slot])
 752         {
 753           apr_size_t len = cs->len[slot];
 754           SVN_ERR(svn_stream_write(output_stream, cs->data[slot], &len));
 755         }
 756     }
 757   return SVN_NO_ERROR;
 758 }
 759
 760
 761 static void
 762 make_context_saver(merge_output_baton_t *mob)
 763 {
 764   context_saver_t *cs;
 765
 766   assert(mob->context_size > 0); /* Or nothing to save */
 767
 768   svn_pool_clear(mob->pool);
 769   cs = apr_pcalloc(mob->pool, sizeof(*cs));
 770   cs->stream = svn_stream_empty(mob->pool);
 771   svn_stream_set_baton(cs->stream, cs);
 772   svn_stream_set_write(cs->stream, context_saver_stream_write);
 773   mob->context_saver = cs;
 774   mob->output_stream = cs->stream;
 775   cs->context_size = mob->context_size;
 776   cs->data = apr_pcalloc(mob->pool, sizeof(*cs->data) * cs->context_size);
 777   cs->len = apr_pcalloc(mob->pool, sizeof(*cs->len) * cs->context_size);
 778 }
 779
 780
 781 /* A stream which prints LINES_TO_PRINT (based on context_size) lines to
 782    BATON->REAL_OUTPUT_STREAM, and then changes BATON->OUTPUT_STREAM to
 783    a context_saver; used for *trailing* context. */
 784
 785 struct trailing_context_printer {
 786   apr_size_t lines_to_print;
 787   merge_output_baton_t *mob;
 788 };
 789
 790
 791 static svn_error_t *
 792 trailing_context_printer_write(void *baton,
 793                                const char *data,
 794                                apr_size_t *len)
 795 {
 796   struct trailing_context_printer *tcp = baton;
 797   SVN_ERR_ASSERT(tcp->lines_to_print > 0);
 798   SVN_ERR(svn_stream_write(tcp->mob->real_output_stream, data, len));
 799   tcp->lines_to_print--;
 800   if (tcp->lines_to_print == 0)
 801     make_context_saver(tcp->mob);
 802   return SVN_NO_ERROR;
 803 }
 804
 805
 806 static void
 807 make_trailing_context_printer(merge_output_baton_t *btn)
 808 {
 809   struct trailing_context_printer *tcp;
 810   svn_stream_t *s;
 811
 812   svn_pool_clear(btn->pool);
 813
 814   tcp = apr_pcalloc(btn->pool, sizeof(*tcp));
 815   tcp->lines_to_print = btn->context_size;
 816   tcp->mob = btn;
 817   s = svn_stream_empty(btn->pool);
 818   svn_stream_set_baton(s, tcp);
 819   svn_stream_set_write(s, trailing_context_printer_write);
 820   btn->output_stream = s;
 821 }
 822
 823
 824 static svn_error_t *
 825 output_merge_token_range(apr_size_t *lines_printed_p,
 826                          merge_output_baton_t *btn,
 827                          int idx, apr_off_t first,
 828                          apr_off_t length)
 829 {
 830   apr_array_header_t *tokens = btn->sources[idx].tokens;
 831   apr_size_t lines_printed = 0;
 832
 833   for (; length > 0 && first < tokens->nelts; length--, first++)
 834     {
 835       svn_string_t *token = APR_ARRAY_IDX(tokens, first, svn_string_t *);
 836       apr_size_t len = token->len;
 837
 838       /* Note that the trailing context printer assumes that
 839          svn_stream_write is called exactly once per line. */
 840       SVN_ERR(svn_stream_write(btn->output_stream, token->data, &len));
 841       lines_printed++;
 842     }
 843
 844   if (lines_printed_p)
 845     *lines_printed_p = lines_printed;
 846
 847   return SVN_NO_ERROR;
 848 }
 849
 850 static svn_error_t *
 851 output_marker_eol(merge_output_baton_t *btn)
 852 {
 853   return svn_stream_puts(btn->output_stream, btn->marker_eol);
 854 }
 855
 856 static svn_error_t *
 857 output_merge_marker(merge_output_baton_t *btn, int idx)
 858 {
 859   SVN_ERR(svn_stream_puts(btn->output_stream, btn->markers[idx]));
 860   return output_marker_eol(btn);
 861 }
 862
 863 static svn_error_t *
 864 output_common_modified(void *baton,
 865                        apr_off_t original_start, apr_off_t original_length,
 866                        apr_off_t modified_start, apr_off_t modified_length,
 867                        apr_off_t latest_start, apr_off_t latest_length)
 868 {
 869   return output_merge_token_range(NULL, baton, 1/*modified*/,
 870                                   modified_start, modified_length);
 871 }
 872
 873 static svn_error_t *
 874 output_latest(void *baton,
 875               apr_off_t original_start, apr_off_t original_length,
 876               apr_off_t modified_start, apr_off_t modified_length,
 877               apr_off_t latest_start, apr_off_t latest_length)
 878 {
 879   return output_merge_token_range(NULL, baton, 2/*latest*/,
 880                                   latest_start, latest_length);
 881 }
 882
 883 static svn_error_t *
 884 output_conflict(void *baton,
 885                 apr_off_t original_start, apr_off_t original_length,
 886                 apr_off_t modified_start, apr_off_t modified_length,
 887                 apr_off_t latest_start, apr_off_t latest_length,
 888                 svn_diff_t *diff);
 889
 890 static const svn_diff_output_fns_t merge_output_vtable =
 891 {
 892   output_common_modified, /* common */
 893   output_common_modified, /* modified */
 894   output_latest,
 895   output_common_modified, /* output_diff_common */
 896   output_conflict
 897 };
 898
 899 static svn_error_t *
 900 output_conflict(void *baton,
 901                 apr_off_t original_start, apr_off_t original_length,
 902                 apr_off_t modified_start, apr_off_t modified_length,
 903                 apr_off_t latest_start, apr_off_t latest_length,
 904                 svn_diff_t *diff)
 905 {
 906   merge_output_baton_t *btn = baton;
 907
 908   svn_diff_conflict_display_style_t style = btn->conflict_style;
 909
 910   if (style == svn_diff_conflict_display_resolved_modified_latest)
 911     {
 912       if (diff)
 913         return svn_diff_output2(diff, baton, &merge_output_vtable,
 914                                 btn->cancel_func, btn->cancel_baton);
 915       else
 916         style = svn_diff_conflict_display_modified_latest;
 917     }
 918
 919   if (style == svn_diff_conflict_display_modified_latest ||
 920       style == svn_diff_conflict_display_modified_original_latest)
 921     {
 922       SVN_ERR(output_merge_marker(btn, 1/*modified*/));
 923       SVN_ERR(output_merge_token_range(NULL, btn, 1/*modified*/,
 924                                        modified_start, modified_length));
 925
 926       if (style == svn_diff_conflict_display_modified_original_latest)
 927         {
 928           SVN_ERR(output_merge_marker(btn, 0/*original*/));
 929           SVN_ERR(output_merge_token_range(NULL, btn, 0/*original*/,
 930                                            original_start, original_length));
 931         }
 932
 933       SVN_ERR(output_merge_marker(btn, 2/*separator*/));
 934       SVN_ERR(output_merge_token_range(NULL, btn, 2/*latest*/,
 935                                        latest_start, latest_length));
 936       SVN_ERR(output_merge_marker(btn, 3/*latest (end)*/));
 937     }
 938   else if (style == svn_diff_conflict_display_modified)
 939       SVN_ERR(output_merge_token_range(NULL, btn, 1/*modified*/,
 940                                        modified_start, modified_length));
 941   else if (style == svn_diff_conflict_display_latest)
 942       SVN_ERR(output_merge_token_range(NULL, btn, 2/*latest*/,
 943                                        latest_start, latest_length));
 944   else /* unknown style */
 945     SVN_ERR_MALFUNCTION();
 946
 947   return SVN_NO_ERROR;
 948 }
 949
 950 static svn_error_t *
 951 output_conflict_with_context_marker(merge_output_baton_t *btn,
 952                                     const char *label,
 953                                     apr_off_t start,
 954                                     apr_off_t length)
 955 {
 956   if (length == 1)
 957     SVN_ERR(svn_stream_printf(btn->output_stream, btn->pool,
 958                               "%s (%" APR_OFF_T_FMT ")",
 959                               label, start + 1));
 960   else
 961     SVN_ERR(svn_stream_printf(btn->output_stream, btn->pool,
 962                               "%s (%" APR_OFF_T_FMT ",%" APR_OFF_T_FMT ")",
 963                               label, start + 1, length));
 964
 965   SVN_ERR(output_marker_eol(btn));
 966
 967   return SVN_NO_ERROR;
 968 }
 969
 970 static svn_error_t *
 971 output_conflict_with_context(void *baton,
 972                              apr_off_t original_start,
 973                              apr_off_t original_length,
 974                              apr_off_t modified_start,
 975                              apr_off_t modified_length,
 976                              apr_off_t latest_start,
 977                              apr_off_t latest_length,
 978                              svn_diff_t *diff)
 979 {
 980   merge_output_baton_t *btn = baton;
 981
 982   /* Are we currently saving starting context (as opposed to printing
 983      trailing context)?  If so, flush it. */
 984   if (btn->output_stream == btn->context_saver->stream)
 985     {
 986       if (btn->context_saver->total_written > btn->context_size)
 987         SVN_ERR(svn_stream_puts(btn->real_output_stream, "@@\n"));
 988       SVN_ERR(flush_context_saver(btn->context_saver, btn->real_output_stream));
 989     }
 990
 991   /* Print to the real output stream. */
 992   btn->output_stream = btn->real_output_stream;
 993
 994   /* Output the conflict itself. */
 995   SVN_ERR(output_conflict_with_context_marker(btn, btn->markers[1],
 996                                               modified_start,
 997                                               modified_length));
 998   SVN_ERR(output_merge_token_range(NULL, btn, 1/*modified*/,
 999                                    modified_start, modified_length));
1000
1001   SVN_ERR(output_conflict_with_context_marker(btn, btn->markers[0],
1002                                               original_start,
1003                                               original_length));
1004   SVN_ERR(output_merge_token_range(NULL, btn, 0/*original*/,
1005                                    original_start, original_length));
1006
1007   SVN_ERR(output_merge_marker(btn, 2/*separator*/));
1008   SVN_ERR(output_merge_token_range(NULL, btn, 2/*latest*/,
1009                                    latest_start, latest_length));
1010   SVN_ERR(output_conflict_with_context_marker(btn, btn->markers[3],
1011                                               latest_start,
1012                                               latest_length));
1013
1014   /* Go into print-trailing-context mode instead. */
1015   make_trailing_context_printer(btn);
1016
1017   return SVN_NO_ERROR;
1018 }
1019
1020
1021 static const svn_diff_output_fns_t merge_only_conflicts_output_vtable =
1022 {
1023   output_common_modified,
1024   output_common_modified,
1025   output_latest,
1026   output_common_modified,
1027   output_conflict_with_context
1028 };
1029
1030
1031 /* TOKEN is the first token in the modified file.
1032    Return its line-ending, if any. */
1033 static const char *
1034 detect_eol(svn_string_t *token)
1035 {
1036   const char *curp;
1037
1038   if (token->len == 0)
1039     return NULL;
1040
1041   curp = token->data + token->len - 1;
1042   if (*curp == '\r')
1043     return "\r";
1044   else if (*curp != '\n')
1045     return NULL;
1046   else
1047     {
1048       if (token->len == 1
1049           || *(--curp) != '\r')
1050         return "\n";
1051       else
1052         return "\r\n";
1053     }
1054 }
1055
1056 svn_error_t *
1057 svn_diff_mem_string_output_merge3(svn_stream_t *output_stream,
1058                                   svn_diff_t *diff,
1059                                   const svn_string_t *original,
1060                                   const svn_string_t *modified,
1061                                   const svn_string_t *latest,
1062                                   const char *conflict_original,
1063                                   const char *conflict_modified,
1064                                   const char *conflict_latest,
1065                                   const char *conflict_separator,
1066                                   svn_diff_conflict_display_style_t style,
1067                                   svn_cancel_func_t cancel_func,
1068                                   void *cancel_baton,
1069                                   apr_pool_t *scratch_pool)
1070 {
1071   merge_output_baton_t btn;
1072   const char *eol;
1073   svn_boolean_t conflicts_only =
1074     (style == svn_diff_conflict_display_only_conflicts);
1075   const svn_diff_output_fns_t *vtable = conflicts_only
1076      ? &merge_only_conflicts_output_vtable : &merge_output_vtable;
1077
1078   memset(&btn, 0, sizeof(btn));
1079   btn.context_size = SVN_DIFF__UNIFIED_CONTEXT_SIZE;
1080
1081   if (conflicts_only)
1082     {
1083       btn.pool = svn_pool_create(scratch_pool);
1084       make_context_saver(&btn);
1085       btn.real_output_stream = output_stream;
1086     }
1087   else
1088     btn.output_stream = output_stream;
1089
1090   fill_source_tokens(&(btn.sources[0]), original, scratch_pool);
1091   fill_source_tokens(&(btn.sources[1]), modified, scratch_pool);
1092   fill_source_tokens(&(btn.sources[2]), latest, scratch_pool);
1093
1094   btn.conflict_style = style;
1095
1096   if (btn.sources[1].tokens->nelts > 0)
1097     {
1098       eol = detect_eol(APR_ARRAY_IDX(btn.sources[1].tokens, 0, svn_string_t *));
1099       if (!eol)
1100         eol = APR_EOL_STR;  /* use the platform default */
1101     }
1102   else
1103     eol = APR_EOL_STR;  /* use the platform default */
1104
1105   btn.marker_eol = eol;
1106   btn.cancel_func = cancel_func;
1107   btn.cancel_baton = cancel_baton;
1108
1109   SVN_ERR(svn_utf_cstring_from_utf8(&btn.markers[1],
1110                                     conflict_modified
1111                                     ? conflict_modified
1112                                     : "<<<<<<< (modified)",
1113                                     scratch_pool));
1114   SVN_ERR(svn_utf_cstring_from_utf8(&btn.markers[0],
1115                                     conflict_original
1116                                     ? conflict_original
1117                                     : "||||||| (original)",
1118                                     scratch_pool));
1119   SVN_ERR(svn_utf_cstring_from_utf8(&btn.markers[2],
1120                                     conflict_separator
1121                                     ? conflict_separator
1122                                     : "=======",
1123                                     scratch_pool));
1124   SVN_ERR(svn_utf_cstring_from_utf8(&btn.markers[3],
1125                                     conflict_latest
1126                                     ? conflict_latest
1127                                     : ">>>>>>> (latest)",
1128                                     scratch_pool));
1129
1130   SVN_ERR(svn_diff_output2(diff, &btn, vtable, cancel_func, cancel_baton));
1131   if (conflicts_only)
1132     svn_pool_destroy(btn.pool);
1133
1134   return SVN_NO_ERROR;
1135 }