Deleted Added
sdiff udiff text old ( 302408 ) new ( 362181 )
full compact
mergeinfo.c (302408) mergeinfo.c (362181)
1/*
2 * mergeinfo.c: Mergeinfo parsing and handling
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

--- 27 unchanged lines hidden (view full) ---

36#include "private/svn_mergeinfo_private.h"
37#include "private/svn_sorts_private.h"
38#include "private/svn_string_private.h"
39#include "private/svn_subr_private.h"
40#include "svn_private_config.h"
41#include "svn_hash.h"
42#include "private/svn_dep_compat.h"
43
1/*
2 * mergeinfo.c: Mergeinfo parsing and handling
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

--- 27 unchanged lines hidden (view full) ---

36#include "private/svn_mergeinfo_private.h"
37#include "private/svn_sorts_private.h"
38#include "private/svn_string_private.h"
39#include "private/svn_subr_private.h"
40#include "svn_private_config.h"
41#include "svn_hash.h"
42#include "private/svn_dep_compat.h"
43
44/* Return TRUE iff the forward revision range FIRST wholly contains the
45 * forward revision range SECOND and (if CONSIDER_INHERITANCE is TRUE) has
46 * the same inheritability. */
47static svn_error_t *
48range_contains(svn_boolean_t *result,
49 const svn_merge_range_t *first, const svn_merge_range_t *second,
50 svn_boolean_t consider_inheritance);
51
52
44/* Attempt to combine two ranges, IN1 and IN2. If they are adjacent or
45 overlapping, and their inheritability allows them to be combined, put
46 the result in OUTPUT and return TRUE, otherwise return FALSE.
47
48 CONSIDER_INHERITANCE determines how to account for the inheritability
49 of IN1 and IN2 when trying to combine ranges. If ranges with different
50 inheritability are combined (CONSIDER_INHERITANCE must be FALSE for this
51 to happen) the result is inheritable. If both ranges are inheritable the

--- 206 unchanged lines hidden (view full) ---

258 lastrange = NULL;
259
260 if (!lastrange)
261 {
262 /* No *LASTRANGE so push NEW_RANGE onto RANGELIST and we are done. */
263 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
264 svn_merge_range_dup(new_range, result_pool);
265 }
53/* Attempt to combine two ranges, IN1 and IN2. If they are adjacent or
54 overlapping, and their inheritability allows them to be combined, put
55 the result in OUTPUT and return TRUE, otherwise return FALSE.
56
57 CONSIDER_INHERITANCE determines how to account for the inheritability
58 of IN1 and IN2 when trying to combine ranges. If ranges with different
59 inheritability are combined (CONSIDER_INHERITANCE must be FALSE for this
60 to happen) the result is inheritable. If both ranges are inheritable the

--- 206 unchanged lines hidden (view full) ---

267 lastrange = NULL;
268
269 if (!lastrange)
270 {
271 /* No *LASTRANGE so push NEW_RANGE onto RANGELIST and we are done. */
272 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
273 svn_merge_range_dup(new_range, result_pool);
274 }
275 else if (combine_ranges(&combined_range, lastrange, new_range,
276 consider_inheritance))
277 {
278 *lastrange = combined_range;
279 }
266 else if (!consider_inheritance)
267 {
268 /* We are not considering inheritance so we can merge intersecting
269 ranges of different inheritability. Of course if the ranges
270 don't intersect at all we simply push NEW_RANGE onto RANGELIST. */
280 else if (!consider_inheritance)
281 {
282 /* We are not considering inheritance so we can merge intersecting
283 ranges of different inheritability. Of course if the ranges
284 don't intersect at all we simply push NEW_RANGE onto RANGELIST. */
271 if (combine_ranges(&combined_range, lastrange, new_range, FALSE))
272 {
273 *lastrange = combined_range;
274 }
275 else
276 {
277 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
285 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
278 svn_merge_range_dup(new_range, result_pool);
286 svn_merge_range_dup(new_range, result_pool);
279 }
280 }
281 else /* Considering inheritance */
282 {
287 }
288 else /* Considering inheritance */
289 {
283 if (combine_ranges(&combined_range, lastrange, new_range, TRUE))
290 /* If we are here then the ranges either don't intersect or do
291 intersect but have differing inheritability. Check for the
292 first case as that is easy to handle. */
293 intersection_type_t intersection_type;
294 svn_boolean_t sorted = FALSE;
295
296 SVN_ERR(get_type_of_intersection(new_range, lastrange,
297 &intersection_type));
298
299 switch (intersection_type)
284 {
300 {
285 /* Even when considering inheritance two intersection ranges
286 of the same inheritability can simply be combined. */
287 *lastrange = combined_range;
288 }
289 else
290 {
291 /* If we are here then the ranges either don't intersect or do
292 intersect but have differing inheritability. Check for the
293 first case as that is easy to handle. */
294 intersection_type_t intersection_type;
295 svn_boolean_t sorted = FALSE;
301 case svn__no_intersection:
302 /* NEW_RANGE and *LASTRANGE *really* don't intersect so
303 just push NEW_RANGE onto RANGELIST. */
304 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
305 svn_merge_range_dup(new_range, result_pool);
306 sorted = (svn_sort_compare_ranges(&lastrange,
307 &new_range) < 0);
308 break;
296
309
297 SVN_ERR(get_type_of_intersection(new_range, lastrange,
298 &intersection_type));
310 case svn__equal_intersection:
311 /* They range are equal so all we do is force the
312 inheritability of lastrange to true. */
313 lastrange->inheritable = TRUE;
314 sorted = TRUE;
315 break;
299
316
300 switch (intersection_type)
317 case svn__adjoining_intersection:
318 /* They adjoin but don't overlap so just push NEW_RANGE
319 onto RANGELIST. */
320 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
321 svn_merge_range_dup(new_range, result_pool);
322 sorted = (svn_sort_compare_ranges(&lastrange,
323 &new_range) < 0);
324 break;
325
326 case svn__overlapping_intersection:
327 /* They ranges overlap but neither is a proper subset of
328 the other. We'll end up pusing two new ranges onto
329 RANGELIST, the intersecting part and the part unique to
330 NEW_RANGE.*/
301 {
331 {
302 case svn__no_intersection:
303 /* NEW_RANGE and *LASTRANGE *really* don't intersect so
304 just push NEW_RANGE onto RANGELIST. */
305 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
306 svn_merge_range_dup(new_range, result_pool);
307 sorted = (svn_sort_compare_ranges(&lastrange,
308 &new_range) < 0);
309 break;
332 svn_merge_range_t *r1 = svn_merge_range_dup(lastrange,
333 result_pool);
334 svn_merge_range_t *r2 = svn_merge_range_dup(new_range,
335 result_pool);
310
336
311 case svn__equal_intersection:
312 /* They range are equal so all we do is force the
313 inheritability of lastrange to true. */
314 lastrange->inheritable = TRUE;
315 sorted = TRUE;
316 break;
337 /* Pop off *LASTRANGE to make our manipulations
338 easier. */
339 apr_array_pop(rangelist);
317
340
318 case svn__adjoining_intersection:
319 /* They adjoin but don't overlap so just push NEW_RANGE
320 onto RANGELIST. */
321 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
322 svn_merge_range_dup(new_range, result_pool);
323 sorted = (svn_sort_compare_ranges(&lastrange,
324 &new_range) < 0);
325 break;
326
327 case svn__overlapping_intersection:
328 /* They ranges overlap but neither is a proper subset of
329 the other. We'll end up pusing two new ranges onto
330 RANGELIST, the intersecting part and the part unique to
331 NEW_RANGE.*/
341 /* Ensure R1 is the older range. */
342 if (r2->start < r1->start)
332 {
343 {
333 svn_merge_range_t *r1 = svn_merge_range_dup(lastrange,
334 result_pool);
335 svn_merge_range_t *r2 = svn_merge_range_dup(new_range,
336 result_pool);
344 /* Swap R1 and R2. */
345 *r2 = *r1;
346 *r1 = *new_range;
347 }
337
348
338 /* Pop off *LASTRANGE to make our manipulations
339 easier. */
340 apr_array_pop(rangelist);
349 /* Absorb the intersecting ranges into the
350 inheritable range. */
351 if (r1->inheritable)
352 r2->start = r1->end;
353 else
354 r1->end = r2->start;
341
355
342 /* Ensure R1 is the older range. */
343 if (r2->start < r1->start)
344 {
345 /* Swap R1 and R2. */
346 *r2 = *r1;
347 *r1 = *new_range;
348 }
356 /* Push everything back onto RANGELIST. */
357 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r1;
358 sorted = (svn_sort_compare_ranges(&lastrange,
359 &r1) < 0);
360 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r2;
361 if (sorted)
362 sorted = (svn_sort_compare_ranges(&r1, &r2) < 0);
363 break;
364 }
349
365
350 /* Absorb the intersecting ranges into the
351 inheritable range. */
352 if (r1->inheritable)
353 r2->start = r1->end;
354 else
355 r1->end = r2->start;
366 default: /* svn__proper_subset_intersection */
367 {
368 /* One range is a proper subset of the other. */
369 svn_merge_range_t *r1 = svn_merge_range_dup(lastrange,
370 result_pool);
371 svn_merge_range_t *r2 = svn_merge_range_dup(new_range,
372 result_pool);
373 svn_merge_range_t *r3 = NULL;
356
374
357 /* Push everything back onto RANGELIST. */
358 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r1;
359 sorted = (svn_sort_compare_ranges(&lastrange,
360 &r1) < 0);
361 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r2;
362 if (sorted)
363 sorted = (svn_sort_compare_ranges(&r1, &r2) < 0);
364 break;
375 /* Pop off *LASTRANGE to make our manipulations
376 easier. */
377 apr_array_pop(rangelist);
378
379 /* Ensure R1 is the superset. */
380 if (r2->start < r1->start || r2->end > r1->end)
381 {
382 /* Swap R1 and R2. */
383 *r2 = *r1;
384 *r1 = *new_range;
365 }
366
385 }
386
367 default: /* svn__proper_subset_intersection */
387 if (r1->inheritable)
368 {
388 {
369 /* One range is a proper subset of the other. */
370 svn_merge_range_t *r1 = svn_merge_range_dup(lastrange,
371 result_pool);
372 svn_merge_range_t *r2 = svn_merge_range_dup(new_range,
373 result_pool);
374 svn_merge_range_t *r3 = NULL;
389 /* The simple case: The superset is inheritable, so
390 just combine r1 and r2. */
391 r1->start = MIN(r1->start, r2->start);
392 r1->end = MAX(r1->end, r2->end);
393 r2 = NULL;
394 }
395 else if (r1->start == r2->start)
396 {
397 svn_revnum_t tmp_revnum;
375
398
376 /* Pop off *LASTRANGE to make our manipulations
377 easier. */
378 apr_array_pop(rangelist);
399 /* *LASTRANGE and NEW_RANGE share an end point. */
400 tmp_revnum = r1->end;
401 r1->end = r2->end;
402 r2->inheritable = r1->inheritable;
403 r1->inheritable = TRUE;
404 r2->start = r1->end;
405 r2->end = tmp_revnum;
406 }
407 else if (r1->end == r2->end)
408 {
409 /* *LASTRANGE and NEW_RANGE share an end point. */
410 r1->end = r2->start;
411 r2->inheritable = TRUE;
412 }
413 else
414 {
415 /* NEW_RANGE and *LASTRANGE share neither start
416 nor end points. */
417 r3 = apr_pcalloc(result_pool, sizeof(*r3));
418 r3->start = r2->end;
419 r3->end = r1->end;
420 r3->inheritable = r1->inheritable;
421 r2->inheritable = TRUE;
422 r1->end = r2->start;
423 }
379
424
380 /* Ensure R1 is the superset. */
381 if (r2->start < r1->start || r2->end > r1->end)
425 /* Push everything back onto RANGELIST. */
426 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r1;
427 sorted = (svn_sort_compare_ranges(&lastrange, &r1) < 0);
428 if (r2)
429 {
430 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r2;
431 if (sorted)
432 sorted = (svn_sort_compare_ranges(&r1, &r2) < 0);
433 }
434 if (r3)
435 {
436 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r3;
437 if (sorted)
382 {
438 {
383 /* Swap R1 and R2. */
384 *r2 = *r1;
385 *r1 = *new_range;
439 if (r2)
440 sorted = (svn_sort_compare_ranges(&r2,
441 &r3) < 0);
442 else
443 sorted = (svn_sort_compare_ranges(&r1,
444 &r3) < 0);
386 }
445 }
387
388 if (r1->inheritable)
389 {
390 /* The simple case: The superset is inheritable, so
391 just combine r1 and r2. */
392 r1->start = MIN(r1->start, r2->start);
393 r1->end = MAX(r1->end, r2->end);
394 r2 = NULL;
395 }
396 else if (r1->start == r2->start)
397 {
398 svn_revnum_t tmp_revnum;
399
400 /* *LASTRANGE and NEW_RANGE share an end point. */
401 tmp_revnum = r1->end;
402 r1->end = r2->end;
403 r2->inheritable = r1->inheritable;
404 r1->inheritable = TRUE;
405 r2->start = r1->end;
406 r2->end = tmp_revnum;
407 }
408 else if (r1->end == r2->end)
409 {
410 /* *LASTRANGE and NEW_RANGE share an end point. */
411 r1->end = r2->start;
412 r2->inheritable = TRUE;
413 }
414 else
415 {
416 /* NEW_RANGE and *LASTRANGE share neither start
417 nor end points. */
418 r3 = apr_pcalloc(result_pool, sizeof(*r3));
419 r3->start = r2->end;
420 r3->end = r1->end;
421 r3->inheritable = r1->inheritable;
422 r2->inheritable = TRUE;
423 r1->end = r2->start;
424 }
425
426 /* Push everything back onto RANGELIST. */
427 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r1;
428 sorted = (svn_sort_compare_ranges(&lastrange, &r1) < 0);
429 if (r2)
430 {
431 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r2;
432 if (sorted)
433 sorted = (svn_sort_compare_ranges(&r1, &r2) < 0);
434 }
435 if (r3)
436 {
437 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r3;
438 if (sorted)
439 {
440 if (r2)
441 sorted = (svn_sort_compare_ranges(&r2,
442 &r3) < 0);
443 else
444 sorted = (svn_sort_compare_ranges(&r1,
445 &r3) < 0);
446 }
447 }
448 break;
449 }
446 }
447 break;
450 }
448 }
451
452 /* Some of the above cases might have put *RANGELIST out of
453 order, so re-sort.*/
454 if (!sorted)
455 svn_sort__array(rangelist, svn_sort_compare_ranges);
456 }
449 }
450
451 /* Some of the above cases might have put *RANGELIST out of
452 order, so re-sort.*/
453 if (!sorted)
454 svn_sort__array(rangelist, svn_sort_compare_ranges);
457 }
458
459 return SVN_NO_ERROR;
460}
461
462/* Convert a single svn_merge_range_t *RANGE back into a string. */
455 }
456
457 return SVN_NO_ERROR;
458}
459
460/* Convert a single svn_merge_range_t *RANGE back into a string. */
463static char *
464range_to_string(const svn_merge_range_t *range,
461static svn_error_t *
462range_to_string(char **s,
463 const svn_merge_range_t *range,
465 apr_pool_t *pool)
466{
467 const char *mark
468 = range->inheritable ? "" : SVN_MERGEINFO_NONINHERITABLE_STR;
469
470 if (range->start == range->end - 1)
464 apr_pool_t *pool)
465{
466 const char *mark
467 = range->inheritable ? "" : SVN_MERGEINFO_NONINHERITABLE_STR;
468
469 if (range->start == range->end - 1)
471 return apr_psprintf(pool, "%ld%s", range->end, mark);
470 *s = apr_psprintf(pool, "%ld%s", range->end, mark);
472 else if (range->start - 1 == range->end)
471 else if (range->start - 1 == range->end)
473 return apr_psprintf(pool, "-%ld%s", range->start, mark);
472 *s = apr_psprintf(pool, "-%ld%s", range->start, mark);
474 else if (range->start < range->end)
473 else if (range->start < range->end)
475 return apr_psprintf(pool, "%ld-%ld%s", range->start + 1, range->end, mark);
474 *s = apr_psprintf(pool, "%ld-%ld%s", range->start + 1, range->end, mark);
475 else if (range->start > range->end)
476 *s = apr_psprintf(pool, "%ld-%ld%s", range->start, range->end + 1, mark);
476 else
477 else
477 return apr_psprintf(pool, "%ld-%ld%s", range->start, range->end + 1, mark);
478 {
479 return svn_error_createf(SVN_ERR_ASSERTION_FAIL, NULL,
480 _("bad range {start=%ld,end=%ld,inheritable=%d}"),
481 range->start, range->end, range->inheritable);
482 }
483
484 return SVN_NO_ERROR;
478}
479
485}
486
487/* Convert a single svn_merge_range_t *RANGE back into a string. */
488static char *
489range_to_string_debug(const svn_merge_range_t *range,
490 apr_pool_t *pool)
491{
492 svn_error_t *err;
493 char *s;
494
495 err = range_to_string(&s, range, pool);
496 if (err)
497 {
498 svn_error_clear(err);
499 s = apr_psprintf(pool, _("bad range {start=%ld,end=%ld,inheritable=%d}"),
500 range->start, range->end, range->inheritable);
501 }
502 return s;
503}
504
480/* Helper for svn_mergeinfo_parse()
481 Append revision ranges onto the array RANGELIST to represent the range
482 descriptions found in the string *INPUT. Read only as far as a newline
483 or the position END, whichever comes first. Set *INPUT to the position
484 after the last character of INPUT that was used.
485
486 revisionlist -> (revisionelement)(COMMA revisionelement)*
487 revisionrange -> REVISION "-" REVISION("*")

--- 115 unchanged lines hidden (view full) ---

603{
604 const char *s = str;
605
606 *rangelist = apr_array_make(result_pool, 1, sizeof(svn_merge_range_t *));
607 SVN_ERR(parse_rangelist(&s, s + strlen(s), *rangelist, result_pool));
608 return SVN_NO_ERROR;
609}
610
505/* Helper for svn_mergeinfo_parse()
506 Append revision ranges onto the array RANGELIST to represent the range
507 descriptions found in the string *INPUT. Read only as far as a newline
508 or the position END, whichever comes first. Set *INPUT to the position
509 after the last character of INPUT that was used.
510
511 revisionlist -> (revisionelement)(COMMA revisionelement)*
512 revisionrange -> REVISION "-" REVISION("*")

--- 115 unchanged lines hidden (view full) ---

628{
629 const char *s = str;
630
631 *rangelist = apr_array_make(result_pool, 1, sizeof(svn_merge_range_t *));
632 SVN_ERR(parse_rangelist(&s, s + strlen(s), *rangelist, result_pool));
633 return SVN_NO_ERROR;
634}
635
611/* Return TRUE, if all ranges in RANGELIST are in ascending order and do
612 * not overlap and are not adjacent.
613 *
614 * ### Can yield false negatives: ranges of differing inheritance are
615 * allowed to be adjacent.
616 *
617 * If this returns FALSE, you probaly want to qsort() the
618 * ranges and then call svn_rangelist__combine_adjacent_ranges().
619 */
620static svn_boolean_t
621is_rangelist_normalized(svn_rangelist_t *rangelist)
636svn_boolean_t
637svn_rangelist__is_canonical(const svn_rangelist_t *rangelist)
622{
623 int i;
624 svn_merge_range_t **ranges = (svn_merge_range_t **)rangelist->elts;
625
638{
639 int i;
640 svn_merge_range_t **ranges = (svn_merge_range_t **)rangelist->elts;
641
626 for (i = 0; i < rangelist->nelts-1; ++i)
627 if (ranges[i]->end >= ranges[i+1]->start)
628 return FALSE;
642 /* Check for reversed and empty ranges */
643 for (i = 0; i < rangelist->nelts; ++i)
644 {
645 if (ranges[i]->start >= ranges[i]->end)
646 return FALSE;
647 }
629
648
649 /* Check for overlapping ranges */
650 for (i = 0; i < rangelist->nelts - 1; ++i)
651 {
652 if (ranges[i]->end > ranges[i + 1]->start)
653 return FALSE; /* Overlapping range */
654 else if (ranges[i]->end == ranges[i+1]->start
655 && ranges[i]->inheritable == ranges[i + 1]->inheritable)
656 {
657 return FALSE; /* Ranges should have been combined */
658 }
659 }
660
630 return TRUE;
631}
632
661 return TRUE;
662}
663
664/* In-place combines adjacent ranges in a rangelist.
665 SCRATCH_POOL is just used for providing error messages. */
633svn_error_t *
634svn_rangelist__canonicalize(svn_rangelist_t *rangelist,
635 apr_pool_t *scratch_pool)
636{
666svn_error_t *
667svn_rangelist__canonicalize(svn_rangelist_t *rangelist,
668 apr_pool_t *scratch_pool)
669{
637 if (! is_rangelist_normalized(rangelist))
638 {
639 svn_sort__array(rangelist, svn_sort_compare_ranges);
640
641 SVN_ERR(svn_rangelist__combine_adjacent_ranges(rangelist, scratch_pool));
642 }
643
644 return SVN_NO_ERROR;
645}
646
647svn_error_t *
648svn_rangelist__combine_adjacent_ranges(svn_rangelist_t *rangelist,
649 apr_pool_t *scratch_pool)
650{
651 int i;
652 svn_merge_range_t *range, *lastrange;
653
670 int i;
671 svn_merge_range_t *range, *lastrange;
672
673 if (svn_rangelist__is_canonical(rangelist))
674 return SVN_NO_ERROR; /* Nothing to do */
675
676 svn_sort__array(rangelist, svn_sort_compare_ranges);
677
654 lastrange = APR_ARRAY_IDX(rangelist, 0, svn_merge_range_t *);
655
656 for (i = 1; i < rangelist->nelts; i++)
657 {
658 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
659 if (lastrange->start <= range->end
660 && range->start <= lastrange->end)
661 {

--- 4 unchanged lines hidden (view full) ---

666 if (range->start < lastrange->end
667 && range->inheritable != lastrange->inheritable)
668 {
669 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
670 _("Unable to parse overlapping "
671 "revision ranges '%s' and '%s' "
672 "with different inheritance "
673 "types"),
678 lastrange = APR_ARRAY_IDX(rangelist, 0, svn_merge_range_t *);
679
680 for (i = 1; i < rangelist->nelts; i++)
681 {
682 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
683 if (lastrange->start <= range->end
684 && range->start <= lastrange->end)
685 {

--- 4 unchanged lines hidden (view full) ---

690 if (range->start < lastrange->end
691 && range->inheritable != lastrange->inheritable)
692 {
693 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
694 _("Unable to parse overlapping "
695 "revision ranges '%s' and '%s' "
696 "with different inheritance "
697 "types"),
674 range_to_string(lastrange,
675 scratch_pool),
676 range_to_string(range,
677 scratch_pool));
698 range_to_string_debug(lastrange,
699 scratch_pool),
700 range_to_string_debug(range,
701 scratch_pool));
678 }
679
680 /* Combine overlapping or adjacent ranges with the
681 same inheritability. */
682 if (lastrange->inheritable == range->inheritable)
683 {
684 lastrange->end = MAX(range->end, lastrange->end);
702 }
703
704 /* Combine overlapping or adjacent ranges with the
705 same inheritability. */
706 if (lastrange->inheritable == range->inheritable)
707 {
708 lastrange->end = MAX(range->end, lastrange->end);
685 svn_sort__array_delete(rangelist, i, 1);
709 SVN_ERR(svn_sort__array_delete2(rangelist, i, 1));
686 i--;
687 }
688 }
689 lastrange = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
690 }
691
692 return SVN_NO_ERROR;
693}

--- 93 unchanged lines hidden (view full) ---

787 /* Always return SVN_ERR_MERGEINFO_PARSE_ERROR as the topmost error. */
788 if (err && err->apr_err != SVN_ERR_MERGEINFO_PARSE_ERROR)
789 err = svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, err,
790 _("Could not parse mergeinfo string '%s'"),
791 input);
792 return err;
793}
794
710 i--;
711 }
712 }
713 lastrange = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
714 }
715
716 return SVN_NO_ERROR;
717}

--- 93 unchanged lines hidden (view full) ---

811 /* Always return SVN_ERR_MERGEINFO_PARSE_ERROR as the topmost error. */
812 if (err && err->apr_err != SVN_ERR_MERGEINFO_PARSE_ERROR)
813 err = svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, err,
814 _("Could not parse mergeinfo string '%s'"),
815 input);
816 return err;
817}
818
795/* Cleanup after svn_rangelist_merge2 when it modifies the ending range of
796 a single rangelist element in-place.
819static const char *
820rangelist_to_string_debug(const svn_rangelist_t *rl,
821 apr_pool_t *pool)
822{
823 svn_string_t *rls;
824 svn_error_t *err;
797
825
798 If *RANGE_INDEX is not a valid element in RANGELIST do nothing. Otherwise
799 ensure that RANGELIST[*RANGE_INDEX]->END does not adjoin or overlap any
800 subsequent ranges in RANGELIST.
826 err = svn_rangelist_to_string(&rls, rl, pool);
827 if (err)
828 {
829 char *s = apr_psprintf(pool, _("<bad rangelist [%d ranges]: %s>"),
830 rl->nelts, err->message);
831 svn_error_clear(err);
832 return s;
833 }
834 return rls->data;
835}
801
836
802 If overlap is found, then remove, modify, and/or add elements to RANGELIST
803 as per the invariants for rangelists documented in svn_mergeinfo.h. If
804 RANGELIST[*RANGE_INDEX]->END adjoins a subsequent element then combine the
805 elements if their inheritability permits -- The inheritance of intersecting
806 and adjoining ranges is handled as per svn_mergeinfo_merge2. Upon return
807 set *RANGE_INDEX to the index of the youngest element modified, added, or
808 adjoined to RANGELIST[*RANGE_INDEX].
837static svn_boolean_t
838rangelist_is_sorted(const svn_rangelist_t *rangelist)
839{
840 int i;
809
841
810 Note: Adjoining rangelist elements are those where the end rev of the older
811 element is equal to the start rev of the younger element.
842 for (i = 1; i < rangelist->nelts; i++)
843 {
844 const svn_merge_range_t *lastrange
845 = APR_ARRAY_IDX(rangelist, i-1, svn_merge_range_t *);
846 const svn_merge_range_t *thisrange
847 = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
812
848
813 Any new elements inserted into RANGELIST are allocated in RESULT_POOL.*/
814static void
815adjust_remaining_ranges(svn_rangelist_t *rangelist,
816 int *range_index,
817 apr_pool_t *result_pool)
849 if (svn_sort_compare_ranges(&lastrange, &thisrange) > 0)
850 return FALSE;
851 }
852 return TRUE;
853}
854
855/* Mergeinfo inheritance or absence in a rangelist interval */
856enum rangelist_interval_kind_t { MI_NONE, MI_NON_INHERITABLE, MI_INHERITABLE };
857
858/* A rangelist interval: like svn_merge_range_t but an interval can represent
859 * a gap in the rangelist (kind = MI_NONE). */
860typedef struct rangelist_interval_t
818{
861{
819 int i;
820 int starting_index;
821 int elements_to_delete = 0;
822 svn_merge_range_t *modified_range;
862 svn_revnum_t start, end;
863 enum rangelist_interval_kind_t kind;
864} rangelist_interval_t;
823
865
824 if (*range_index >= rangelist->nelts)
825 return;
866/* Iterator for intervals in a rangelist. */
867typedef struct rangelist_interval_iterator_t {
868 /* iteration state: */
869 const svn_rangelist_t *rl; /* input */
870 int i; /* current interval is this range in RL or the gap before it */
871 svn_boolean_t in_range; /* current interval is range RL[I], not a gap? */
826
872
827 starting_index = *range_index + 1;
828 modified_range = APR_ARRAY_IDX(rangelist, *range_index, svn_merge_range_t *);
873 /* current interval: */
874 rangelist_interval_t interval;
875} rangelist_interval_iterator_t;
829
876
830 for (i = *range_index + 1; i < rangelist->nelts; i++)
877/* Update IT->interval to match the current iteration state of IT.
878 * Return the iterator, or NULL if the iteration has reached its end.
879 */
880static rangelist_interval_iterator_t *
881rlii_update(rangelist_interval_iterator_t *it)
882{
883 const svn_merge_range_t *range
884 = (it->i < it->rl->nelts
885 ? APR_ARRAY_IDX(it->rl, it->i, void *) : NULL);
886
887 if (!range)
888 return NULL;
889
890 if (!it->in_range)
831 {
891 {
832 svn_merge_range_t *next_range = APR_ARRAY_IDX(rangelist, i,
833 svn_merge_range_t *);
892 it->interval.start
893 = (it->i > 0
894 ? APR_ARRAY_IDX(it->rl, it->i - 1, svn_merge_range_t *)->end
895 : 0);
896 it->interval.end = range->start;
897 it->interval.kind = MI_NONE;
898 }
899 else
900 {
901 it->interval.start = range->start;
902 it->interval.end = range->end;
903 it->interval.kind
904 = (range->inheritable ? MI_INHERITABLE : MI_NON_INHERITABLE);
905 }
906 return it;
907}
834
908
835 /* If MODIFIED_RANGE doesn't adjoin or overlap the next range in
836 RANGELIST then we are finished. */
837 if (modified_range->end < next_range->start)
838 break;
909/* Move to the next interval, which might be a zero-length interval.
910 * Return IT, or return NULL at the end of iteration. */
911static rangelist_interval_iterator_t *
912rlii_next_any_interval(rangelist_interval_iterator_t *it)
913{
914 /* Should be called before iteration is finished. */
915 if (it->i >= it->rl->nelts)
916 return NULL;
839
917
840 /* Does MODIFIED_RANGE adjoin NEXT_RANGE? */
841 if (modified_range->end == next_range->start)
842 {
843 if (modified_range->inheritable == next_range->inheritable)
844 {
845 /* Combine adjoining ranges with the same inheritability. */
846 modified_range->end = next_range->end;
847 elements_to_delete++;
848 }
849 else
850 {
851 /* Cannot join because inheritance differs. */
852 (*range_index)++;
853 }
854 break;
855 }
918 /* If we are in a range, move to the next pre-range gap;
919 * else, move from this pre-range gap into this range. */
920 if (it->in_range)
921 it->i++;
922 it->in_range = !it->in_range;
923 return it;
924}
856
925
857 /* Alright, we know MODIFIED_RANGE overlaps NEXT_RANGE, but how? */
858 if (modified_range->end > next_range->end)
859 {
860 /* NEXT_RANGE is a proper subset of MODIFIED_RANGE and the two
861 don't share the same end range. */
862 if (modified_range->inheritable
863 || (modified_range->inheritable == next_range->inheritable))
864 {
865 /* MODIFIED_RANGE absorbs NEXT_RANGE. */
866 elements_to_delete++;
867 }
868 else
869 {
870 /* NEXT_RANGE is a proper subset MODIFIED_RANGE but
871 MODIFIED_RANGE is non-inheritable and NEXT_RANGE is
872 inheritable. This means MODIFIED_RANGE is truncated,
873 NEXT_RANGE remains, and the portion of MODIFIED_RANGE
874 younger than NEXT_RANGE is added as a separate range:
875 ______________________________________________
876 | |
877 M MODIFIED_RANGE N
878 | (!inheritable) |
879 |______________________________________________|
880 | |
881 O NEXT_RANGE P
882 | (inheritable)|
883 |______________|
884 |
885 V
886 _______________________________________________
887 | | | |
888 M MODIFIED_RANGE O NEXT_RANGE P NEW_RANGE N
889 | (!inheritable) | (inheritable)| (!inheritable)|
890 |________________|______________|_______________|
891 */
892 svn_merge_range_t *new_modified_range =
893 apr_palloc(result_pool, sizeof(*new_modified_range));
894 new_modified_range->start = next_range->end;
895 new_modified_range->end = modified_range->end;
896 new_modified_range->inheritable = FALSE;
897 modified_range->end = next_range->start;
898 (*range_index)+=2;
899 svn_sort__array_insert(rangelist, &new_modified_range,
900 *range_index);
901 /* Recurse with the new range. */
902 adjust_remaining_ranges(rangelist, range_index, result_pool);
903 break;
904 }
905 }
906 else if (modified_range->end == next_range->end)
907 {
908 /* NEXT_RANGE is a proper subset MODIFIED_RANGE and share
909 the same end range. */
910 if (modified_range->inheritable
911 || (modified_range->inheritable == next_range->inheritable))
912 {
913 /* MODIFIED_RANGE absorbs NEXT_RANGE. */
914 elements_to_delete++;
915 }
916 else
917 {
918 /* The intersection between MODIFIED_RANGE and NEXT_RANGE is
919 absorbed by the latter. */
920 modified_range->end = next_range->start;
921 (*range_index)++;
922 }
923 break;
924 }
925 else
926 {
927 /* NEXT_RANGE and MODIFIED_RANGE intersect but NEXT_RANGE is not
928 a proper subset of MODIFIED_RANGE, nor do the two share the
929 same end revision, i.e. they overlap. */
930 if (modified_range->inheritable == next_range->inheritable)
931 {
932 /* Combine overlapping ranges with the same inheritability. */
933 modified_range->end = next_range->end;
934 elements_to_delete++;
935 }
936 else if (modified_range->inheritable)
937 {
938 /* MODIFIED_RANGE absorbs the portion of NEXT_RANGE it overlaps
939 and NEXT_RANGE is truncated. */
940 next_range->start = modified_range->end;
941 (*range_index)++;
942 }
943 else
944 {
945 /* NEXT_RANGE absorbs the portion of MODIFIED_RANGE it overlaps
946 and MODIFIED_RANGE is truncated. */
947 modified_range->end = next_range->start;
948 (*range_index)++;
949 }
950 break;
951 }
926/* Return an iterator pointing at the first non-zero-length interval in RL,
927 * or NULL if there are none. */
928static rangelist_interval_iterator_t *
929rlii_first(const svn_rangelist_t *rl,
930 apr_pool_t *pool)
931{
932 rangelist_interval_iterator_t *it = apr_palloc(pool, sizeof(*it));
933
934 it->rl = rl;
935 it->i = 0;
936 it->in_range = FALSE;
937
938 /* Update, and skip empty intervals */
939 while ((it = rlii_update(it)) && it->interval.start == it->interval.end)
940 {
941 it = rlii_next_any_interval(it);
952 }
942 }
943 return it;
944}
953
945
954 if (elements_to_delete)
955 svn_sort__array_delete(rangelist, starting_index, elements_to_delete);
946/* Move to the next non-empty interval.
947 * Intervals will be generated in this sequence:
948 * (0, MI_NONE, RL[0]->start), // i=0, !in_range
949 * (RL[0]->start, MI_* RL[0]->end), // i=0, in_range
950 * (RL[0]->end, MI_NONE, RL[1]->start),
951 * (RL[1]->start, MI_* RL[1]->end),
952 * ...
953 * (RL[n-2]->end, MI_NONE, RL[n-1]->start),
954 * (RL[n-1]->start, MI_* RL[n-1]->end),
955 * but excluding empty intervals.
956 * Return IT, or return NULL at the end of iteration. */
957static rangelist_interval_iterator_t *
958rlii_next(rangelist_interval_iterator_t *it)
959{
960 it = rlii_next_any_interval(it);
961
962 /* Update, and skip empty intervals */
963 while ((it = rlii_update(it)) && it->interval.start == it->interval.end)
964 {
965 it = rlii_next_any_interval(it);
966 }
967 return it;
956}
957
968}
969
970/* Rangelist builder. Accumulates consecutive intervals, combining them
971 * when possible. */
972typedef struct rangelist_builder_t {
973 svn_rangelist_t *rl; /* rangelist to build */
974 rangelist_interval_t accu_interval; /* current interval accumulator */
975 apr_pool_t *pool; /* from which to allocate ranges */
976} rangelist_builder_t;
977
978/* Return an initialized rangelist builder. */
979static rangelist_builder_t *
980rl_builder_new(svn_rangelist_t *rl,
981 apr_pool_t *pool)
982{
983 rangelist_builder_t *b = apr_pcalloc(pool, sizeof(*b));
984
985 b->rl = rl;
986 /* b->accu_interval = {0, 0, RL_NONE} */
987 b->pool = pool;
988 return b;
989}
990
991/* Flush the last accumulated interval in the rangelist builder B. */
992static void
993rl_builder_flush(rangelist_builder_t *b)
994{
995 if (b->accu_interval.kind > MI_NONE)
996 {
997 svn_merge_range_t *mrange = apr_pcalloc(b->pool, sizeof(*mrange));
998 mrange->start = b->accu_interval.start;
999 mrange->end = b->accu_interval.end;
1000 mrange->inheritable = (b->accu_interval.kind == MI_INHERITABLE);
1001 APR_ARRAY_PUSH(b->rl, svn_merge_range_t *) = mrange;
1002 }
1003}
1004
1005/* Add a new INTERVAL to the rangelist builder B. */
1006static void
1007rl_builder_add_interval(rangelist_builder_t *b,
1008 const rangelist_interval_t *interval)
1009{
1010 SVN_ERR_ASSERT_NO_RETURN(interval->start < interval->end);
1011 SVN_ERR_ASSERT_NO_RETURN(interval->start == b->accu_interval.end);
1012
1013 /* Extend the accumulating interval, or end it and start another? */
1014 if (interval->kind == b->accu_interval.kind)
1015 {
1016 b->accu_interval.end = interval->end;
1017 }
1018 else
1019 {
1020 /* Push the accumulated interval onto the building rangelist. */
1021 rl_builder_flush(b);
1022 /* Start accumulating a new interval */
1023 b->accu_interval = *interval;
1024 }
1025}
1026
1027/* Set RL_OUT to the union (merge) of RL1 and RL2.
1028 * On entry, RL_OUT must be an empty rangelist.
1029 *
1030 * Each range added to RL_OUT will be either shallow-copied from RL1 or
1031 * allocated from RESULT_POOL.
1032 */
1033static svn_error_t *
1034rangelist_merge(svn_rangelist_t *rl_out,
1035 const svn_rangelist_t *rl1,
1036 const svn_rangelist_t *rl2,
1037 apr_pool_t *result_pool,
1038 apr_pool_t *scratch_pool)
1039{
1040 rangelist_interval_iterator_t *it[2];
1041 rangelist_builder_t *rl_builder = rl_builder_new(rl_out, result_pool);
1042 svn_revnum_t r_last = 0;
1043
1044 /*SVN_ERR_ASSERT(svn_rangelist__is_canonical(rl1));*/
1045 /*SVN_ERR_ASSERT(svn_rangelist__is_canonical(rl2));*/
1046 SVN_ERR_ASSERT(rangelist_is_sorted(rl1));
1047 SVN_ERR_ASSERT(rangelist_is_sorted(rl2));
1048 SVN_ERR_ASSERT(rl_out->nelts == 0);
1049
1050 /* Initialize the input iterators and the output generator */
1051 it[0] = rlii_first(rl1, scratch_pool);
1052 it[1] = rlii_first(rl2, scratch_pool);
1053
1054 /* Keep choosing the next input revision (whether a start or end of a range)
1055 * at which to consider making an output transition. */
1056 while (it[0] || it[1])
1057 {
1058 svn_revnum_t r_next = !it[1] ? it[0]->interval.end
1059 : !it[0] ? it[1]->interval.end
1060 : MIN(it[0]->interval.end, it[1]->interval.end);
1061 rangelist_interval_t interval;
1062
1063 interval.start = r_last;
1064 interval.end = r_next;
1065 interval.kind = !it[1] ? it[0]->interval.kind
1066 : !it[0] ? it[1]->interval.kind
1067 : MAX(it[0]->interval.kind, it[1]->interval.kind);
1068
1069 /* Accumulate */
1070 SVN_ERR_ASSERT(interval.start < interval.end);
1071 rl_builder_add_interval(rl_builder, &interval);
1072
1073 /* if we have used up either or both input intervals, increment them */
1074 if (it[0] && it[0]->interval.end <= r_next)
1075 it[0] = rlii_next(it[0]);
1076 if (it[1] && it[1]->interval.end <= r_next)
1077 it[1] = rlii_next(it[1]);
1078
1079 r_last = interval.end;
1080 }
1081 rl_builder_flush(rl_builder);
1082 return SVN_NO_ERROR;
1083}
1084
958svn_error_t *
959svn_rangelist_merge2(svn_rangelist_t *rangelist,
1085svn_error_t *
1086svn_rangelist_merge2(svn_rangelist_t *rangelist,
960 const svn_rangelist_t *changes,
1087 const svn_rangelist_t *chg,
961 apr_pool_t *result_pool,
962 apr_pool_t *scratch_pool)
963{
1088 apr_pool_t *result_pool,
1089 apr_pool_t *scratch_pool)
1090{
964 int i = 0;
965 int j = 0;
1091 svn_error_t *err;
1092 svn_rangelist_t *rangelist_orig;
966
1093
967 /* We may modify CHANGES, so make a copy in SCRATCH_POOL. */
968 changes = svn_rangelist_dup(changes, scratch_pool);
1094#ifdef SVN_DEBUG
1095 SVN_ERR_ASSERT(rangelist_is_sorted(rangelist));
1096 SVN_ERR_ASSERT(rangelist_is_sorted(chg));
1097#endif
969
1098
970 while (i < rangelist->nelts && j < changes->nelts)
971 {
972 svn_merge_range_t *range =
973 APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
974 svn_merge_range_t *change =
975 APR_ARRAY_IDX(changes, j, svn_merge_range_t *);
976 int res = svn_sort_compare_ranges(&range, &change);
1099 /* Move the original rangelist aside. A shallow copy suffices,
1100 * as rangelist_merge() won't modify its inputs. */
1101 rangelist_orig = apr_array_copy(scratch_pool, rangelist);
1102 apr_array_clear(rangelist);
1103 err = svn_error_trace(rangelist_merge(rangelist, rangelist_orig, chg,
1104 result_pool, scratch_pool));
977
1105
978 if (res == 0)
979 {
980 /* Only when merging two non-inheritable ranges is the result also
981 non-inheritable. In all other cases ensure an inheritable
982 result. */
983 if (range->inheritable || change->inheritable)
984 range->inheritable = TRUE;
985 i++;
986 j++;
987 }
988 else if (res < 0) /* CHANGE is younger than RANGE */
989 {
990 if (range->end < change->start)
991 {
992 /* RANGE is older than CHANGE and the two do not
993 adjoin or overlap */
994 i++;
995 }
996 else if (range->end == change->start)
997 {
998 /* RANGE and CHANGE adjoin */
999 if (range->inheritable == change->inheritable)
1000 {
1001 /* RANGE and CHANGE have the same inheritability so
1002 RANGE expands to absord CHANGE. */
1003 range->end = change->end;
1004 adjust_remaining_ranges(rangelist, &i, result_pool);
1005 j++;
1006 }
1007 else
1008 {
1009 /* RANGE and CHANGE adjoin, but have different
1010 inheritability. Since RANGE is older, just
1011 move on to the next RANGE. */
1012 i++;
1013 }
1014 }
1015 else
1016 {
1017 /* RANGE and CHANGE overlap, but how? */
1018 if ((range->inheritable == change->inheritable)
1019 || range->inheritable)
1020 {
1021 /* If CHANGE is a proper subset of RANGE, it absorbs RANGE
1022 with no adjustment otherwise only the intersection is
1023 absorbed and CHANGE is truncated. */
1024 if (range->end >= change->end)
1025 j++;
1026 else
1027 change->start = range->end;
1028 }
1029 else
1030 {
1031 /* RANGE is non-inheritable and CHANGE is inheritable. */
1032 if (range->start < change->start)
1033 {
1034 /* CHANGE absorbs intersection with RANGE and RANGE
1035 is truncated. */
1036 svn_merge_range_t *range_copy =
1037 svn_merge_range_dup(range, result_pool);
1038 range_copy->end = change->start;
1039 range->start = change->start;
1040 svn_sort__array_insert(rangelist, &range_copy, i++);
1041 }
1042 else
1043 {
1044 /* CHANGE and RANGE share the same start rev, but
1045 RANGE is considered older because its end rev
1046 is older. */
1047 range->inheritable = TRUE;
1048 change->start = range->end;
1049 }
1050 }
1051 }
1052 }
1053 else /* res > 0, CHANGE is older than RANGE */
1054 {
1055 if (change->end < range->start)
1056 {
1057 /* CHANGE is older than RANGE and the two do not
1058 adjoin or overlap, so insert a copy of CHANGE
1059 into RANGELIST. */
1060 svn_merge_range_t *change_copy =
1061 svn_merge_range_dup(change, result_pool);
1062 svn_sort__array_insert(rangelist, &change_copy, i++);
1063 j++;
1064 }
1065 else if (change->end == range->start)
1066 {
1067 /* RANGE and CHANGE adjoin */
1068 if (range->inheritable == change->inheritable)
1069 {
1070 /* RANGE and CHANGE have the same inheritability so we
1071 can simply combine the two in place. */
1072 range->start = change->start;
1073 j++;
1074 }
1075 else
1076 {
1077 /* RANGE and CHANGE have different inheritability so insert
1078 a copy of CHANGE into RANGELIST. */
1079 svn_merge_range_t *change_copy =
1080 svn_merge_range_dup(change, result_pool);
1081 svn_sort__array_insert(rangelist, &change_copy, i);
1082 j++;
1083 }
1084 }
1085 else
1086 {
1087 /* RANGE and CHANGE overlap. */
1088 if (range->inheritable == change->inheritable)
1089 {
1090 /* RANGE and CHANGE have the same inheritability so we
1091 can simply combine the two in place... */
1092 range->start = change->start;
1093 if (range->end < change->end)
1094 {
1095 /* ...but if RANGE is expanded ensure that we don't
1096 violate any rangelist invariants. */
1097 range->end = change->end;
1098 adjust_remaining_ranges(rangelist, &i, result_pool);
1099 }
1100 j++;
1101 }
1102 else if (range->inheritable)
1103 {
1104 if (change->start < range->start)
1105 {
1106 /* RANGE is inheritable so absorbs any part of CHANGE
1107 it overlaps. CHANGE is truncated and the remainder
1108 inserted into RANGELIST. */
1109 svn_merge_range_t *change_copy =
1110 svn_merge_range_dup(change, result_pool);
1111 change_copy->end = range->start;
1112 change->start = range->start;
1113 svn_sort__array_insert(rangelist, &change_copy, i++);
1114 }
1115 else
1116 {
1117 /* CHANGE and RANGE share the same start rev, but
1118 CHANGE is considered older because CHANGE->END is
1119 older than RANGE->END. */
1120 j++;
1121 }
1122 }
1123 else
1124 {
1125 /* RANGE is non-inheritable and CHANGE is inheritable. */
1126 if (change->start < range->start)
1127 {
1128 if (change->end == range->end)
1129 {
1130 /* RANGE is a proper subset of CHANGE and share the
1131 same end revision, so set RANGE equal to CHANGE. */
1132 range->start = change->start;
1133 range->inheritable = TRUE;
1134 j++;
1135 }
1136 else if (change->end > range->end)
1137 {
1138 /* RANGE is a proper subset of CHANGE and CHANGE has
1139 a younger end revision, so set RANGE equal to its
1140 intersection with CHANGE and truncate CHANGE. */
1141 range->start = change->start;
1142 range->inheritable = TRUE;
1143 change->start = range->end;
1144 }
1145 else
1146 {
1147 /* CHANGE and RANGE overlap. Set RANGE equal to its
1148 intersection with CHANGE and take the remainder
1149 of RANGE and insert it into RANGELIST. */
1150 svn_merge_range_t *range_copy =
1151 svn_merge_range_dup(range, result_pool);
1152 range_copy->start = change->end;
1153 range->start = change->start;
1154 range->end = change->end;
1155 range->inheritable = TRUE;
1156 svn_sort__array_insert(rangelist, &range_copy, ++i);
1157 j++;
1158 }
1159 }
1160 else
1161 {
1162 /* CHANGE and RANGE share the same start rev, but
1163 CHANGE is considered older because its end rev
1164 is older.
1165
1166 Insert the intersection of RANGE and CHANGE into
1167 RANGELIST and then set RANGE to the non-intersecting
1168 portion of RANGE. */
1169 svn_merge_range_t *range_copy =
1170 svn_merge_range_dup(range, result_pool);
1171 range_copy->end = change->end;
1172 range_copy->inheritable = TRUE;
1173 range->start = change->end;
1174 svn_sort__array_insert(rangelist, &range_copy, i++);
1175 j++;
1176 }
1177 }
1178 }
1179 }
1106#ifdef SVN_DEBUG
1107 if (err)
1108 {
1109 err = svn_error_createf(SVN_ERR_ASSERTION_FAIL, err,
1110 "svn_rangelist_merge2( %s / %s ): internal error",
1111 rangelist_to_string_debug(rangelist_orig, scratch_pool),
1112 rangelist_to_string_debug(chg, scratch_pool));
1180 }
1113 }
1181
1182 /* Copy any remaining elements in CHANGES into RANGELIST. */
1183 for (; j < (changes)->nelts; j++)
1114 else if (! svn_rangelist__is_canonical(rangelist)
1115 && svn_rangelist__is_canonical(rangelist_orig)
1116 && svn_rangelist__is_canonical(chg))
1184 {
1117 {
1185 svn_merge_range_t *change =
1186 APR_ARRAY_IDX(changes, j, svn_merge_range_t *);
1187 svn_merge_range_t *change_copy = svn_merge_range_dup(change,
1188 result_pool);
1189 svn_sort__array_insert(rangelist, &change_copy, rangelist->nelts);
1118 err = svn_error_createf(SVN_ERR_ASSERTION_FAIL, NULL,
1119 "svn_rangelist_merge2( %s / %s ): canonical inputs, "
1120 "non-canonical result ( %s )",
1121 rangelist_to_string_debug(rangelist_orig, scratch_pool),
1122 rangelist_to_string_debug(chg, scratch_pool),
1123 rangelist_to_string_debug(rangelist, scratch_pool));
1190 }
1124 }
1125#endif
1191
1126
1192 return SVN_NO_ERROR;
1127 return err;
1193}
1194
1128}
1129
1195/* Return TRUE iff the forward revision ranges FIRST and SECOND overlap and
1196 * (if CONSIDER_INHERITANCE is TRUE) have the same inheritability. */
1197static svn_boolean_t
1198range_intersect(const svn_merge_range_t *first, const svn_merge_range_t *second,
1130/* Set *RESULT to TRUE iff the forward revision ranges FIRST and SECOND overlap
1131 * and (if CONSIDER_INHERITANCE is TRUE) have the same inheritability. */
1132static svn_error_t *
1133range_intersect(svn_boolean_t *result,
1134 const svn_merge_range_t *first, const svn_merge_range_t *second,
1199 svn_boolean_t consider_inheritance)
1200{
1135 svn_boolean_t consider_inheritance)
1136{
1201 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(first));
1202 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(second));
1137 SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(first));
1138 SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(second));
1203
1139
1204 return (first->start + 1 <= second->end)
1205 && (second->start + 1 <= first->end)
1206 && (!consider_inheritance
1207 || (!(first->inheritable) == !(second->inheritable)));
1140 *result = (first->start + 1 <= second->end)
1141 && (second->start + 1 <= first->end)
1142 && (!consider_inheritance
1143 || (!(first->inheritable) == !(second->inheritable)));
1144 return SVN_NO_ERROR;
1208}
1209
1145}
1146
1210/* Return TRUE iff the forward revision range FIRST wholly contains the
1147/* Set *RESULT to TRUE iff the forward revision range FIRST wholly contains the
1211 * forward revision range SECOND and (if CONSIDER_INHERITANCE is TRUE) has
1212 * the same inheritability. */
1148 * forward revision range SECOND and (if CONSIDER_INHERITANCE is TRUE) has
1149 * the same inheritability. */
1213static svn_boolean_t
1214range_contains(const svn_merge_range_t *first, const svn_merge_range_t *second,
1150static svn_error_t *
1151range_contains(svn_boolean_t *result,
1152 const svn_merge_range_t *first, const svn_merge_range_t *second,
1215 svn_boolean_t consider_inheritance)
1216{
1153 svn_boolean_t consider_inheritance)
1154{
1217 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(first));
1218 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(second));
1155 SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(first));
1156 SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(second));
1219
1157
1220 return (first->start <= second->start) && (second->end <= first->end)
1221 && (!consider_inheritance
1222 || (!(first->inheritable) == !(second->inheritable)));
1158 *result = (first->start <= second->start) && (second->end <= first->end)
1159 && (!consider_inheritance
1160 || (!(first->inheritable) == !(second->inheritable)));
1161 return SVN_NO_ERROR;
1223}
1224
1225/* Swap start and end fields of RANGE. */
1226static void
1227range_swap_endpoints(svn_merge_range_t *range)
1228{
1229 svn_revnum_t swap = range->start;
1230 range->start = range->end;

--- 102 unchanged lines hidden (view full) ---

1333
1334 i1 = 0;
1335 i2 = 0;
1336 lasti2 = -1; /* Initialized to a value that "i2" will never be. */
1337
1338 while (i1 < rangelist1->nelts && i2 < rangelist2->nelts)
1339 {
1340 svn_merge_range_t *elt1, *elt2;
1162}
1163
1164/* Swap start and end fields of RANGE. */
1165static void
1166range_swap_endpoints(svn_merge_range_t *range)
1167{
1168 svn_revnum_t swap = range->start;
1169 range->start = range->end;

--- 102 unchanged lines hidden (view full) ---

1272
1273 i1 = 0;
1274 i2 = 0;
1275 lasti2 = -1; /* Initialized to a value that "i2" will never be. */
1276
1277 while (i1 < rangelist1->nelts && i2 < rangelist2->nelts)
1278 {
1279 svn_merge_range_t *elt1, *elt2;
1280 svn_boolean_t elt1_contains_elt2, elt1_intersects_elt2;
1341
1342 elt1 = APR_ARRAY_IDX(rangelist1, i1, svn_merge_range_t *);
1343
1344 /* Instead of making a copy of the entire array of rangelist2
1345 elements, we just keep a copy of the current rangelist2 element
1346 that needs to be used, and modify our copy if necessary. */
1347 if (i2 != lasti2)
1348 {
1349 working_elt2 =
1350 *(APR_ARRAY_IDX(rangelist2, i2, svn_merge_range_t *));
1351 lasti2 = i2;
1352 }
1353
1354 elt2 = &working_elt2;
1355
1281
1282 elt1 = APR_ARRAY_IDX(rangelist1, i1, svn_merge_range_t *);
1283
1284 /* Instead of making a copy of the entire array of rangelist2
1285 elements, we just keep a copy of the current rangelist2 element
1286 that needs to be used, and modify our copy if necessary. */
1287 if (i2 != lasti2)
1288 {
1289 working_elt2 =
1290 *(APR_ARRAY_IDX(rangelist2, i2, svn_merge_range_t *));
1291 lasti2 = i2;
1292 }
1293
1294 elt2 = &working_elt2;
1295
1296 SVN_ERR(range_contains(&elt1_contains_elt2,
1297 elt1, elt2, consider_inheritance));
1298 SVN_ERR(range_intersect(&elt1_intersects_elt2,
1299 elt1, elt2, consider_inheritance));
1356 /* If the rangelist2 range is contained completely in the
1357 rangelist1, we increment the rangelist2.
1358 If the ranges intersect, and match exactly, we increment both
1359 rangelist1 and rangelist2.
1360 Otherwise, we have to generate a range for the left part of
1361 the removal of rangelist1 from rangelist2, and possibly change
1362 the rangelist2 to the remaining portion of the right part of
1363 the removal, to test against. */
1300 /* If the rangelist2 range is contained completely in the
1301 rangelist1, we increment the rangelist2.
1302 If the ranges intersect, and match exactly, we increment both
1303 rangelist1 and rangelist2.
1304 Otherwise, we have to generate a range for the left part of
1305 the removal of rangelist1 from rangelist2, and possibly change
1306 the rangelist2 to the remaining portion of the right part of
1307 the removal, to test against. */
1364 if (range_contains(elt1, elt2, consider_inheritance))
1308 if (elt1_contains_elt2)
1365 {
1366 if (!do_remove)
1367 {
1368 svn_merge_range_t tmp_range;
1369 tmp_range.start = elt2->start;
1370 tmp_range.end = elt2->end;
1371 /* The intersection of two ranges is non-inheritable only
1372 if both ranges are non-inheritable. */

--- 4 unchanged lines hidden (view full) ---

1377 pool));
1378 }
1379
1380 i2++;
1381
1382 if (elt2->start == elt1->start && elt2->end == elt1->end)
1383 i1++;
1384 }
1309 {
1310 if (!do_remove)
1311 {
1312 svn_merge_range_t tmp_range;
1313 tmp_range.start = elt2->start;
1314 tmp_range.end = elt2->end;
1315 /* The intersection of two ranges is non-inheritable only
1316 if both ranges are non-inheritable. */

--- 4 unchanged lines hidden (view full) ---

1321 pool));
1322 }
1323
1324 i2++;
1325
1326 if (elt2->start == elt1->start && elt2->end == elt1->end)
1327 i1++;
1328 }
1385 else if (range_intersect(elt1, elt2, consider_inheritance))
1329 else if (elt1_intersects_elt2)
1386 {
1387 if (elt2->start < elt1->start)
1388 {
1389 /* The rangelist2 range starts before the rangelist1 range. */
1390 svn_merge_range_t tmp_range;
1391 if (do_remove)
1392 {
1393 /* Retain the range that falls before the rangelist1

--- 526 unchanged lines hidden (view full) ---

1920 apr_pool_t *pool)
1921{
1922 svn_stringbuf_t *buf = svn_stringbuf_create_empty(pool);
1923
1924 if (rangelist->nelts > 0)
1925 {
1926 int i;
1927 svn_merge_range_t *range;
1330 {
1331 if (elt2->start < elt1->start)
1332 {
1333 /* The rangelist2 range starts before the rangelist1 range. */
1334 svn_merge_range_t tmp_range;
1335 if (do_remove)
1336 {
1337 /* Retain the range that falls before the rangelist1

--- 526 unchanged lines hidden (view full) ---

1864 apr_pool_t *pool)
1865{
1866 svn_stringbuf_t *buf = svn_stringbuf_create_empty(pool);
1867
1868 if (rangelist->nelts > 0)
1869 {
1870 int i;
1871 svn_merge_range_t *range;
1872 char *s;
1928
1929 /* Handle the elements that need commas at the end. */
1930 for (i = 0; i < rangelist->nelts - 1; i++)
1931 {
1932 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
1873
1874 /* Handle the elements that need commas at the end. */
1875 for (i = 0; i < rangelist->nelts - 1; i++)
1876 {
1877 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
1933 svn_stringbuf_appendcstr(buf, range_to_string(range, pool));
1878 SVN_ERR(range_to_string(&s, range, pool));
1879 svn_stringbuf_appendcstr(buf, s);
1934 svn_stringbuf_appendcstr(buf, ",");
1935 }
1936
1937 /* Now handle the last element, which needs no comma. */
1938 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
1880 svn_stringbuf_appendcstr(buf, ",");
1881 }
1882
1883 /* Now handle the last element, which needs no comma. */
1884 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
1939 svn_stringbuf_appendcstr(buf, range_to_string(range, pool));
1885 SVN_ERR(range_to_string(&s, range, pool));
1886 svn_stringbuf_appendcstr(buf, s);
1940 }
1941
1942 *output = svn_stringbuf__morph_into_string(buf);
1943
1944 return SVN_NO_ERROR;
1945}
1946
1947/* Converts a mergeinfo INPUT to an unparsed mergeinfo in OUTPUT. If PREFIX

--- 353 unchanged lines hidden (view full) ---

2301svn_rangelist_dup(const svn_rangelist_t *rangelist, apr_pool_t *pool)
2302{
2303 return ptr_array_dup(rangelist, sizeof(svn_merge_range_t), pool);
2304}
2305
2306svn_merge_range_t *
2307svn_merge_range_dup(const svn_merge_range_t *range, apr_pool_t *pool)
2308{
1887 }
1888
1889 *output = svn_stringbuf__morph_into_string(buf);
1890
1891 return SVN_NO_ERROR;
1892}
1893
1894/* Converts a mergeinfo INPUT to an unparsed mergeinfo in OUTPUT. If PREFIX

--- 353 unchanged lines hidden (view full) ---

2248svn_rangelist_dup(const svn_rangelist_t *rangelist, apr_pool_t *pool)
2249{
2250 return ptr_array_dup(rangelist, sizeof(svn_merge_range_t), pool);
2251}
2252
2253svn_merge_range_t *
2254svn_merge_range_dup(const svn_merge_range_t *range, apr_pool_t *pool)
2255{
2309 svn_merge_range_t *new_range = apr_palloc(pool, sizeof(*new_range));
2310 memcpy(new_range, range, sizeof(*new_range));
2256 svn_merge_range_t *new_range = apr_pmemdup(pool, range, sizeof(*new_range));
2311 return new_range;
2312}
2313
2314svn_boolean_t
2315svn_merge_range_contains_rev(const svn_merge_range_t *range, svn_revnum_t rev)
2316{
2317 assert(SVN_IS_VALID_REVNUM(range->start));
2318 assert(SVN_IS_VALID_REVNUM(range->end));

--- 36 unchanged lines hidden (view full) ---

2355 svn_stringbuf_appendcstr(output_buf, path1);
2356 svn_stringbuf_appendcstr(output_buf, "\n");
2357 SVN_ERR(mergeinfo_to_stringbuf(&mergeinfo_output_buf, mergeinfo,
2358 val_prefix ? val_prefix : "", pool));
2359 svn_stringbuf_appendstr(output_buf, mergeinfo_output_buf);
2360 svn_stringbuf_appendcstr(output_buf, "\n");
2361 }
2362 }
2257 return new_range;
2258}
2259
2260svn_boolean_t
2261svn_merge_range_contains_rev(const svn_merge_range_t *range, svn_revnum_t rev)
2262{
2263 assert(SVN_IS_VALID_REVNUM(range->start));
2264 assert(SVN_IS_VALID_REVNUM(range->end));

--- 36 unchanged lines hidden (view full) ---

2301 svn_stringbuf_appendcstr(output_buf, path1);
2302 svn_stringbuf_appendcstr(output_buf, "\n");
2303 SVN_ERR(mergeinfo_to_stringbuf(&mergeinfo_output_buf, mergeinfo,
2304 val_prefix ? val_prefix : "", pool));
2305 svn_stringbuf_appendstr(output_buf, mergeinfo_output_buf);
2306 svn_stringbuf_appendcstr(output_buf, "\n");
2307 }
2308 }
2363#if SVN_DEBUG
2309#ifdef SVN_DEBUG
2364 else if (!catalog)
2365 {
2366 output_buf = svn_stringbuf_create(key_prefix ? key_prefix : "", pool);
2367 svn_stringbuf_appendcstr(output_buf, _("NULL mergeinfo catalog\n"));
2368 }
2369 else if (apr_hash_count(catalog) == 0)
2370 {
2371 output_buf = svn_stringbuf_create(key_prefix ? key_prefix : "", pool);

--- 319 unchanged lines hidden --- 		2310 else if (!catalog)
2311 {
2312 output_buf = svn_stringbuf_create(key_prefix ? key_prefix : "", pool);
2313 svn_stringbuf_appendcstr(output_buf, _("NULL mergeinfo catalog\n"));
2314 }
2315 else if (apr_hash_count(catalog) == 0)
2316 {
2317 output_buf = svn_stringbuf_create(key_prefix ? key_prefix : "", pool);

--- 319 unchanged lines hidden ---