diff options
Diffstat (limited to 'subversion/libsvn_subr/mergeinfo.c')
-rw-r--r-- | subversion/libsvn_subr/mergeinfo.c | 803 |
1 files changed, 349 insertions, 454 deletions
diff --git a/subversion/libsvn_subr/mergeinfo.c b/subversion/libsvn_subr/mergeinfo.c index 21fa212..721dc4b 100644 --- a/subversion/libsvn_subr/mergeinfo.c +++ b/subversion/libsvn_subr/mergeinfo.c @@ -44,8 +44,9 @@ /* Return TRUE iff the forward revision range FIRST wholly contains the * forward revision range SECOND and (if CONSIDER_INHERITANCE is TRUE) has * the same inheritability. */ -static svn_boolean_t -range_contains(const svn_merge_range_t *first, const svn_merge_range_t *second, +static svn_error_t * +range_contains(svn_boolean_t *result, + const svn_merge_range_t *first, const svn_merge_range_t *second, svn_boolean_t consider_inheritance); @@ -457,21 +458,48 @@ combine_with_lastrange(const svn_merge_range_t *new_range, } /* Convert a single svn_merge_range_t *RANGE back into a string. */ -static char * -range_to_string(const svn_merge_range_t *range, +static svn_error_t * +range_to_string(char **s, + const svn_merge_range_t *range, apr_pool_t *pool) { const char *mark = range->inheritable ? "" : SVN_MERGEINFO_NONINHERITABLE_STR; if (range->start == range->end - 1) - return apr_psprintf(pool, "%ld%s", range->end, mark); + *s = apr_psprintf(pool, "%ld%s", range->end, mark); else if (range->start - 1 == range->end) - return apr_psprintf(pool, "-%ld%s", range->start, mark); + *s = apr_psprintf(pool, "-%ld%s", range->start, mark); else if (range->start < range->end) - return apr_psprintf(pool, "%ld-%ld%s", range->start + 1, range->end, mark); + *s = apr_psprintf(pool, "%ld-%ld%s", range->start + 1, range->end, mark); + else if (range->start > range->end) + *s = apr_psprintf(pool, "%ld-%ld%s", range->start, range->end + 1, mark); else - return apr_psprintf(pool, "%ld-%ld%s", range->start, range->end + 1, mark); + { + return svn_error_createf(SVN_ERR_ASSERTION_FAIL, NULL, + _("bad range {start=%ld,end=%ld,inheritable=%d}"), + range->start, range->end, range->inheritable); + } + + return SVN_NO_ERROR; +} + +/* Convert a single svn_merge_range_t *RANGE back into a string. */ +static char * +range_to_string_debug(const svn_merge_range_t *range, + apr_pool_t *pool) +{ + svn_error_t *err; + char *s; + + err = range_to_string(&s, range, pool); + if (err) + { + svn_error_clear(err); + s = apr_psprintf(pool, _("bad range {start=%ld,end=%ld,inheritable=%d}"), + range->start, range->end, range->inheritable); + } + return s; } /* Helper for svn_mergeinfo_parse() @@ -667,10 +695,10 @@ svn_rangelist__canonicalize(svn_rangelist_t *rangelist, "revision ranges '%s' and '%s' " "with different inheritance " "types"), - range_to_string(lastrange, - scratch_pool), - range_to_string(range, - scratch_pool)); + range_to_string_debug(lastrange, + scratch_pool), + range_to_string_debug(range, + scratch_pool)); } /* Combine overlapping or adjacent ranges with the @@ -678,7 +706,7 @@ svn_rangelist__canonicalize(svn_rangelist_t *rangelist, if (lastrange->inheritable == range->inheritable) { lastrange->end = MAX(range->end, lastrange->end); - svn_sort__array_delete(rangelist, i, 1); + SVN_ERR(svn_sort__array_delete2(rangelist, i, 1)); i--; } } @@ -788,490 +816,349 @@ svn_mergeinfo_parse(svn_mergeinfo_t *mergeinfo, return err; } -/* Cleanup after svn_rangelist_merge2 when it modifies the ending range of - a single rangelist element in-place. - - If *RANGE_INDEX is not a valid element in RANGELIST do nothing. Otherwise - ensure that RANGELIST[*RANGE_INDEX]->END does not adjoin or overlap any - subsequent ranges in RANGELIST. - - If overlap is found, then remove, modify, and/or add elements to RANGELIST - as per the invariants for rangelists documented in svn_mergeinfo.h. If - RANGELIST[*RANGE_INDEX]->END adjoins a subsequent element then combine the - elements if their inheritability permits -- The inheritance of intersecting - and adjoining ranges is handled as per svn_mergeinfo_merge2. Upon return - set *RANGE_INDEX to the index of the youngest element modified, added, or - adjoined to RANGELIST[*RANGE_INDEX]. +static const char * +rangelist_to_string_debug(const svn_rangelist_t *rl, + apr_pool_t *pool) +{ + svn_string_t *rls; + svn_error_t *err; - Note: Adjoining rangelist elements are those where the end rev of the older - element is equal to the start rev of the younger element. + err = svn_rangelist_to_string(&rls, rl, pool); + if (err) + { + char *s = apr_psprintf(pool, _("<bad rangelist [%d ranges]: %s>"), + rl->nelts, err->message); + svn_error_clear(err); + return s; + } + return rls->data; +} - Any new elements inserted into RANGELIST are allocated in RESULT_POOL.*/ -static void -adjust_remaining_ranges(svn_rangelist_t *rangelist, - int *range_index, - apr_pool_t *result_pool) +static svn_boolean_t +rangelist_is_sorted(const svn_rangelist_t *rangelist) { int i; - int starting_index; - int elements_to_delete = 0; - svn_merge_range_t *modified_range; - if (*range_index >= rangelist->nelts) - return; + for (i = 1; i < rangelist->nelts; i++) + { + const svn_merge_range_t *lastrange + = APR_ARRAY_IDX(rangelist, i-1, svn_merge_range_t *); + const svn_merge_range_t *thisrange + = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *); - starting_index = *range_index + 1; - modified_range = APR_ARRAY_IDX(rangelist, *range_index, svn_merge_range_t *); + if (svn_sort_compare_ranges(&lastrange, &thisrange) > 0) + return FALSE; + } + return TRUE; +} - for (i = *range_index + 1; i < rangelist->nelts; i++) - { - svn_merge_range_t *next_range = APR_ARRAY_IDX(rangelist, i, - svn_merge_range_t *); +/* Mergeinfo inheritance or absence in a rangelist interval */ +enum rangelist_interval_kind_t { MI_NONE, MI_NON_INHERITABLE, MI_INHERITABLE }; - /* If MODIFIED_RANGE doesn't adjoin or overlap the next range in - RANGELIST then we are finished. */ - if (modified_range->end < next_range->start) - break; +/* A rangelist interval: like svn_merge_range_t but an interval can represent + * a gap in the rangelist (kind = MI_NONE). */ +typedef struct rangelist_interval_t +{ + svn_revnum_t start, end; + enum rangelist_interval_kind_t kind; +} rangelist_interval_t; + +/* Iterator for intervals in a rangelist. */ +typedef struct rangelist_interval_iterator_t { + /* iteration state: */ + const svn_rangelist_t *rl; /* input */ + int i; /* current interval is this range in RL or the gap before it */ + svn_boolean_t in_range; /* current interval is range RL[I], not a gap? */ + + /* current interval: */ + rangelist_interval_t interval; +} rangelist_interval_iterator_t; + +/* Update IT->interval to match the current iteration state of IT. + * Return the iterator, or NULL if the iteration has reached its end. + */ +static rangelist_interval_iterator_t * +rlii_update(rangelist_interval_iterator_t *it) +{ + const svn_merge_range_t *range + = (it->i < it->rl->nelts + ? APR_ARRAY_IDX(it->rl, it->i, void *) : NULL); - /* Does MODIFIED_RANGE adjoin NEXT_RANGE? */ - if (modified_range->end == next_range->start) - { - if (modified_range->inheritable == next_range->inheritable) - { - /* Combine adjoining ranges with the same inheritability. */ - modified_range->end = next_range->end; - elements_to_delete++; - } - else - { - /* Cannot join because inheritance differs. */ - (*range_index)++; - } - break; - } + if (!range) + return NULL; - /* Alright, we know MODIFIED_RANGE overlaps NEXT_RANGE, but how? */ - if (modified_range->end > next_range->end) - { - /* NEXT_RANGE is a proper subset of MODIFIED_RANGE and the two - don't share the same end range. */ - if (modified_range->inheritable - || (modified_range->inheritable == next_range->inheritable)) - { - /* MODIFIED_RANGE absorbs NEXT_RANGE. */ - elements_to_delete++; - } - else - { - /* NEXT_RANGE is a proper subset MODIFIED_RANGE but - MODIFIED_RANGE is non-inheritable and NEXT_RANGE is - inheritable. This means MODIFIED_RANGE is truncated, - NEXT_RANGE remains, and the portion of MODIFIED_RANGE - younger than NEXT_RANGE is added as a separate range: - ______________________________________________ - | | - M MODIFIED_RANGE N - | (!inheritable) | - |______________________________________________| - | | - O NEXT_RANGE P - | (inheritable)| - |______________| - | - V - _______________________________________________ - | | | | - M MODIFIED_RANGE O NEXT_RANGE P NEW_RANGE N - | (!inheritable) | (inheritable)| (!inheritable)| - |________________|______________|_______________| - */ - svn_merge_range_t *new_modified_range = - apr_palloc(result_pool, sizeof(*new_modified_range)); - new_modified_range->start = next_range->end; - new_modified_range->end = modified_range->end; - new_modified_range->inheritable = FALSE; - modified_range->end = next_range->start; - (*range_index) += 2 + elements_to_delete; - svn_sort__array_insert(rangelist, &new_modified_range, - *range_index); - /* Recurse with the new range. */ - adjust_remaining_ranges(rangelist, range_index, result_pool); - break; - } - } - else if (modified_range->end == next_range->end) - { - /* NEXT_RANGE is a proper subset MODIFIED_RANGE and share - the same end range. */ - if (modified_range->inheritable - || (modified_range->inheritable == next_range->inheritable)) - { - /* MODIFIED_RANGE absorbs NEXT_RANGE. */ - elements_to_delete++; - } - else - { - /* The intersection between MODIFIED_RANGE and NEXT_RANGE is - absorbed by the latter. */ - modified_range->end = next_range->start; - (*range_index)++; - } - break; - } - else - { - /* NEXT_RANGE and MODIFIED_RANGE intersect but NEXT_RANGE is not - a proper subset of MODIFIED_RANGE, nor do the two share the - same end revision, i.e. they overlap. */ - if (modified_range->inheritable == next_range->inheritable) - { - /* Combine overlapping ranges with the same inheritability. */ - modified_range->end = next_range->end; - elements_to_delete++; - } - else if (modified_range->inheritable) - { - /* MODIFIED_RANGE absorbs the portion of NEXT_RANGE it overlaps - and NEXT_RANGE is truncated. */ - next_range->start = modified_range->end; - (*range_index)++; - } - else - { - /* NEXT_RANGE absorbs the portion of MODIFIED_RANGE it overlaps - and MODIFIED_RANGE is truncated. */ - modified_range->end = next_range->start; - (*range_index)++; - } - break; - } + if (!it->in_range) + { + it->interval.start + = (it->i > 0 + ? APR_ARRAY_IDX(it->rl, it->i - 1, svn_merge_range_t *)->end + : 0); + it->interval.end = range->start; + it->interval.kind = MI_NONE; } + else + { + it->interval.start = range->start; + it->interval.end = range->end; + it->interval.kind + = (range->inheritable ? MI_INHERITABLE : MI_NON_INHERITABLE); + } + return it; +} - if (elements_to_delete) - svn_sort__array_delete(rangelist, starting_index, elements_to_delete); +/* Move to the next interval, which might be a zero-length interval. + * Return IT, or return NULL at the end of iteration. */ +static rangelist_interval_iterator_t * +rlii_next_any_interval(rangelist_interval_iterator_t *it) +{ + /* Should be called before iteration is finished. */ + if (it->i >= it->rl->nelts) + return NULL; + + /* If we are in a range, move to the next pre-range gap; + * else, move from this pre-range gap into this range. */ + if (it->in_range) + it->i++; + it->in_range = !it->in_range; + return it; } -#if 0 /* Temporary debug helper code */ -static svn_error_t * -dual_dump(const char *prefix, - const svn_rangelist_t *rangelist, - const svn_rangelist_t *changes, - apr_pool_t *scratch_pool) +/* Return an iterator pointing at the first non-zero-length interval in RL, + * or NULL if there are none. */ +static rangelist_interval_iterator_t * +rlii_first(const svn_rangelist_t *rl, + apr_pool_t *pool) { - svn_string_t *rls, *chg; + rangelist_interval_iterator_t *it = apr_palloc(pool, sizeof(*it)); - SVN_ERR(svn_rangelist_to_string(&rls, rangelist, scratch_pool)); - SVN_ERR(svn_rangelist_to_string(&chg, changes, scratch_pool)); + it->rl = rl; + it->i = 0; + it->in_range = FALSE; - SVN_DBG(("%s: %s / %s", prefix, rls->data, chg->data)); - return SVN_NO_ERROR; + /* Update, and skip empty intervals */ + while ((it = rlii_update(it)) && it->interval.start == it->interval.end) + { + it = rlii_next_any_interval(it); + } + return it; } -#endif -svn_error_t * -svn_rangelist_merge2(svn_rangelist_t *rangelist, - const svn_rangelist_t *chg, - apr_pool_t *result_pool, - apr_pool_t *scratch_pool) +/* Move to the next non-empty interval. + * Intervals will be generated in this sequence: + * (0, MI_NONE, RL[0]->start), // i=0, !in_range + * (RL[0]->start, MI_* RL[0]->end), // i=0, in_range + * (RL[0]->end, MI_NONE, RL[1]->start), + * (RL[1]->start, MI_* RL[1]->end), + * ... + * (RL[n-2]->end, MI_NONE, RL[n-1]->start), + * (RL[n-1]->start, MI_* RL[n-1]->end), + * but excluding empty intervals. + * Return IT, or return NULL at the end of iteration. */ +static rangelist_interval_iterator_t * +rlii_next(rangelist_interval_iterator_t *it) { - svn_rangelist_t *changes; - int i = 0; - int j; - - SVN_ERR(svn_rangelist__canonicalize(rangelist, scratch_pool)); + it = rlii_next_any_interval(it); - /* We may modify CHANGES, so make a copy in SCRATCH_POOL. */ - changes = svn_rangelist_dup(chg, scratch_pool); - SVN_ERR(svn_rangelist__canonicalize(changes, scratch_pool)); - - for (j = 0; j < changes->nelts; j++) + /* Update, and skip empty intervals */ + while ((it = rlii_update(it)) && it->interval.start == it->interval.end) { - svn_merge_range_t *range; - svn_merge_range_t *change = - APR_ARRAY_IDX(changes, j, svn_merge_range_t *); - int res; - - range = (i < rangelist->nelts) - ? APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *) - : NULL; + it = rlii_next_any_interval(it); + } + return it; +} - if (!range || change->end < range->start) - { - /* No overlap, nor adjoin, copy change to result range */ - svn_merge_range_t *chg_copy = svn_merge_range_dup(change, - result_pool); - svn_sort__array_insert(rangelist, &chg_copy, i++); - continue; - } - else if ((change->start > range->end) - || (change->start == range->end - && change->inheritable != range->inheritable)) - { - /* No overlap, nor adjoin. Check next range item against change */ - i++; - j--; - continue; - } +/* Rangelist builder. Accumulates consecutive intervals, combining them + * when possible. */ +typedef struct rangelist_builder_t { + svn_rangelist_t *rl; /* rangelist to build */ + rangelist_interval_t accu_interval; /* current interval accumulator */ + apr_pool_t *pool; /* from which to allocate ranges */ +} rangelist_builder_t; + +/* Return an initialized rangelist builder. */ +static rangelist_builder_t * +rl_builder_new(svn_rangelist_t *rl, + apr_pool_t *pool) +{ + rangelist_builder_t *b = apr_pcalloc(pool, sizeof(*b)); - if (change->start < range->start - && range->inheritable != change->inheritable - && ! (change->inheritable && range_contains(change, range, FALSE)) - && ! (range->inheritable && range_contains(range, change, FALSE))) - { - /* Can't fold change into existing range. - Insert new range before range */ + b->rl = rl; + /* b->accu_interval = {0, 0, RL_NONE} */ + b->pool = pool; + return b; +} - svn_merge_range_t *chg_copy = svn_merge_range_dup(change, - result_pool); +/* Flush the last accumulated interval in the rangelist builder B. */ +static void +rl_builder_flush(rangelist_builder_t *b) +{ + if (b->accu_interval.kind > MI_NONE) + { + svn_merge_range_t *mrange = apr_pcalloc(b->pool, sizeof(*mrange)); + mrange->start = b->accu_interval.start; + mrange->end = b->accu_interval.end; + mrange->inheritable = (b->accu_interval.kind == MI_INHERITABLE); + APR_ARRAY_PUSH(b->rl, svn_merge_range_t *) = mrange; + } +} - chg_copy->start = MIN(change->start, range->start); - if (! change->inheritable) - chg_copy->end = range->start; - else - range->start = change->end; +/* Add a new INTERVAL to the rangelist builder B. */ +static void +rl_builder_add_interval(rangelist_builder_t *b, + const rangelist_interval_t *interval) +{ + SVN_ERR_ASSERT_NO_RETURN(interval->start < interval->end); + SVN_ERR_ASSERT_NO_RETURN(interval->start == b->accu_interval.end); - svn_sort__array_insert(rangelist, &chg_copy, i++); + /* Extend the accumulating interval, or end it and start another? */ + if (interval->kind == b->accu_interval.kind) + { + b->accu_interval.end = interval->end; + } + else + { + /* Push the accumulated interval onto the building rangelist. */ + rl_builder_flush(b); + /* Start accumulating a new interval */ + b->accu_interval = *interval; + } +} - change->start = chg_copy->end; - if (change->start >= change->end) - continue; /* No overlap with range left */ - } - else - { - range->start = MIN(range->start, change->start); - } +/* Set RL_OUT to the union (merge) of RL1 and RL2. + * On entry, RL_OUT must be an empty rangelist. + * + * Each range added to RL_OUT will be either shallow-copied from RL1 or + * allocated from RESULT_POOL. + */ +static svn_error_t * +rangelist_merge(svn_rangelist_t *rl_out, + const svn_rangelist_t *rl1, + const svn_rangelist_t *rl2, + apr_pool_t *result_pool, + apr_pool_t *scratch_pool) +{ + rangelist_interval_iterator_t *it[2]; + rangelist_builder_t *rl_builder = rl_builder_new(rl_out, result_pool); + svn_revnum_t r_last = 0; + + /*SVN_ERR_ASSERT(svn_rangelist__is_canonical(rl1));*/ + /*SVN_ERR_ASSERT(svn_rangelist__is_canonical(rl2));*/ + SVN_ERR_ASSERT(rangelist_is_sorted(rl1)); + SVN_ERR_ASSERT(rangelist_is_sorted(rl2)); + SVN_ERR_ASSERT(rl_out->nelts == 0); + + /* Initialize the input iterators and the output generator */ + it[0] = rlii_first(rl1, scratch_pool); + it[1] = rlii_first(rl2, scratch_pool); + + /* Keep choosing the next input revision (whether a start or end of a range) + * at which to consider making an output transition. */ + while (it[0] || it[1]) + { + svn_revnum_t r_next = !it[1] ? it[0]->interval.end + : !it[0] ? it[1]->interval.end + : MIN(it[0]->interval.end, it[1]->interval.end); + rangelist_interval_t interval; + + interval.start = r_last; + interval.end = r_next; + interval.kind = !it[1] ? it[0]->interval.kind + : !it[0] ? it[1]->interval.kind + : MAX(it[0]->interval.kind, it[1]->interval.kind); + + /* Accumulate */ + SVN_ERR_ASSERT(interval.start < interval.end); + rl_builder_add_interval(rl_builder, &interval); + + /* if we have used up either or both input intervals, increment them */ + if (it[0] && it[0]->interval.end <= r_next) + it[0] = rlii_next(it[0]); + if (it[1] && it[1]->interval.end <= r_next) + it[1] = rlii_next(it[1]); + + r_last = interval.end; + } + rl_builder_flush(rl_builder); + return SVN_NO_ERROR; +} - SVN_ERR_ASSERT(change->start >= range->start); +svn_error_t * +svn_rangelist_merge2(svn_rangelist_t *rangelist, + const svn_rangelist_t *chg, + apr_pool_t *result_pool, + apr_pool_t *scratch_pool) +{ + svn_error_t *err; + svn_rangelist_t *rangelist_orig; - res = svn_sort_compare_ranges(&range, &change); +#ifdef SVN_DEBUG + SVN_ERR_ASSERT(rangelist_is_sorted(rangelist)); + SVN_ERR_ASSERT(rangelist_is_sorted(chg)); +#endif - if (res == 0) - { - /* Only when merging two non-inheritable ranges is the result also - non-inheritable. In all other cases ensure an inheritable - result. */ - if (range->inheritable || change->inheritable) - range->inheritable = TRUE; - i++; - continue; - } - else if (res < 0) /* CHANGE is younger than RANGE */ - { - if (range->end == change->start) - { - /* RANGE and CHANGE adjoin */ - if (range->inheritable == change->inheritable) - { - /* RANGE and CHANGE have the same inheritability so - RANGE expands to absord CHANGE. */ - range->end = change->end; - adjust_remaining_ranges(rangelist, &i, result_pool); - continue; - } - else - { - /* RANGE and CHANGE adjoin, but have different - inheritability. Since RANGE is older, just - move on to the next RANGE. */ - SVN_ERR_MALFUNCTION(); - } - } - else - { - /* RANGE and CHANGE overlap, but how? */ - if ((range->inheritable == change->inheritable) - || range->inheritable) - { - /* If CHANGE is a proper subset of RANGE, it absorbs RANGE - with no adjustment otherwise only the intersection is - absorbed and CHANGE is truncated. */ - if (range->end >= change->end) - continue; - else - { - change->start = range->end; - j--; - continue; - } - } - else - { - /* RANGE is non-inheritable and CHANGE is inheritable. */ - if (range->start < change->start) - { - /* CHANGE absorbs intersection with RANGE and RANGE - is truncated. */ - svn_merge_range_t *range_copy = - svn_merge_range_dup(range, result_pool); - range_copy->end = change->start; - range->start = change->start; - svn_sort__array_insert(rangelist, &range_copy, i++); - j--; - continue; - } - else - { - /* CHANGE and RANGE share the same start rev, but - RANGE is considered older because its end rev - is older. */ - range->inheritable = TRUE; - change->start = range->end; - j--; - continue; - } - } - } - } - else /* res > 0, CHANGE is older than RANGE */ - { - if (change->end == range->start) - { - /* RANGE and CHANGE adjoin */ - if (range->inheritable == change->inheritable) - { - /* RANGE and CHANGE have the same inheritability so we - can simply combine the two in place. */ - range->start = change->start; - continue; - } - else - { - /* RANGE and CHANGE have different inheritability so insert - a copy of CHANGE into RANGELIST. */ - SVN_ERR_MALFUNCTION(); /* Already handled */ - } - } - else - { - /* RANGE and CHANGE overlap. */ - if (range->inheritable == change->inheritable) - { - /* RANGE and CHANGE have the same inheritability so we - can simply combine the two in place... */ - range->start = change->start; - if (range->end < change->end) - { - /* ...but if RANGE is expanded ensure that we don't - violate any rangelist invariants. */ - range->end = change->end; - adjust_remaining_ranges(rangelist, &i, result_pool); - } - continue; - } - else if (range->inheritable) - { - if (change->start < range->start) - { - /* RANGE is inheritable so absorbs any part of CHANGE - it overlaps. CHANGE is truncated and the remainder - inserted into RANGELIST. */ - SVN_ERR_MALFUNCTION(); /* Already handled */ - } - else - { - /* CHANGE and RANGE share the same start rev, but - CHANGE is considered older because CHANGE->END is - older than RANGE->END. */ - continue; - } - } - else - { - /* RANGE is non-inheritable and CHANGE is inheritable. */ - if (change->start < range->start) - { - if (change->end == range->end) - { - /* RANGE is a proper subset of CHANGE and share the - same end revision, so set RANGE equal to CHANGE. */ - range->start = change->start; - range->inheritable = TRUE; - continue; - } - else if (change->end > range->end) - { - /* RANGE is a proper subset of CHANGE and CHANGE has - a younger end revision, so set RANGE equal to its - intersection with CHANGE and truncate CHANGE. */ - range->start = change->start; - range->inheritable = TRUE; - change->start = range->end; - j--; - continue; - } - else - { - /* CHANGE and RANGE overlap. Set RANGE equal to its - intersection with CHANGE and take the remainder - of RANGE and insert it into RANGELIST. */ - svn_merge_range_t *range_copy = - svn_merge_range_dup(range, result_pool); - range_copy->start = change->end; - range->start = change->start; - range->end = change->end; - range->inheritable = TRUE; - svn_sort__array_insert(rangelist, &range_copy, ++i); - continue; - } - } - else - { - /* CHANGE and RANGE share the same start rev, but - CHANGE is considered older because its end rev - is older. - - Insert the intersection of RANGE and CHANGE into - RANGELIST and then set RANGE to the non-intersecting - portion of RANGE. */ - svn_merge_range_t *range_copy = - svn_merge_range_dup(range, result_pool); - range_copy->end = change->end; - range_copy->inheritable = TRUE; - range->start = change->end; - svn_sort__array_insert(rangelist, &range_copy, i++); - continue; - } - } - } - } - SVN_ERR_MALFUNCTION(); /* Unreachable */ - } + /* Move the original rangelist aside. A shallow copy suffices, + * as rangelist_merge() won't modify its inputs. */ + rangelist_orig = apr_array_copy(scratch_pool, rangelist); + apr_array_clear(rangelist); + err = svn_error_trace(rangelist_merge(rangelist, rangelist_orig, chg, + result_pool, scratch_pool)); #ifdef SVN_DEBUG - SVN_ERR_ASSERT(svn_rangelist__is_canonical(rangelist)); + if (err) + { + err = svn_error_createf(SVN_ERR_ASSERTION_FAIL, err, + "svn_rangelist_merge2( %s / %s ): internal error", + rangelist_to_string_debug(rangelist_orig, scratch_pool), + rangelist_to_string_debug(chg, scratch_pool)); + } + else if (! svn_rangelist__is_canonical(rangelist) + && svn_rangelist__is_canonical(rangelist_orig) + && svn_rangelist__is_canonical(chg)) + { + err = svn_error_createf(SVN_ERR_ASSERTION_FAIL, NULL, + "svn_rangelist_merge2( %s / %s ): canonical inputs, " + "non-canonical result ( %s )", + rangelist_to_string_debug(rangelist_orig, scratch_pool), + rangelist_to_string_debug(chg, scratch_pool), + rangelist_to_string_debug(rangelist, scratch_pool)); + } #endif - return SVN_NO_ERROR; + return err; } -/* Return TRUE iff the forward revision ranges FIRST and SECOND overlap and - * (if CONSIDER_INHERITANCE is TRUE) have the same inheritability. */ -static svn_boolean_t -range_intersect(const svn_merge_range_t *first, const svn_merge_range_t *second, +/* Set *RESULT to TRUE iff the forward revision ranges FIRST and SECOND overlap + * and (if CONSIDER_INHERITANCE is TRUE) have the same inheritability. */ +static svn_error_t * +range_intersect(svn_boolean_t *result, + const svn_merge_range_t *first, const svn_merge_range_t *second, svn_boolean_t consider_inheritance) { - SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(first)); - SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(second)); + SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(first)); + SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(second)); - return (first->start + 1 <= second->end) - && (second->start + 1 <= first->end) - && (!consider_inheritance - || (!(first->inheritable) == !(second->inheritable))); + *result = (first->start + 1 <= second->end) + && (second->start + 1 <= first->end) + && (!consider_inheritance + || (!(first->inheritable) == !(second->inheritable))); + return SVN_NO_ERROR; } -/* Return TRUE iff the forward revision range FIRST wholly contains the +/* Set *RESULT to TRUE iff the forward revision range FIRST wholly contains the * forward revision range SECOND and (if CONSIDER_INHERITANCE is TRUE) has * the same inheritability. */ -static svn_boolean_t -range_contains(const svn_merge_range_t *first, const svn_merge_range_t *second, +static svn_error_t * +range_contains(svn_boolean_t *result, + const svn_merge_range_t *first, const svn_merge_range_t *second, svn_boolean_t consider_inheritance) { - SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(first)); - SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(second)); + SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(first)); + SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(second)); - return (first->start <= second->start) && (second->end <= first->end) - && (!consider_inheritance - || (!(first->inheritable) == !(second->inheritable))); + *result = (first->start <= second->start) && (second->end <= first->end) + && (!consider_inheritance + || (!(first->inheritable) == !(second->inheritable))); + return SVN_NO_ERROR; } /* Swap start and end fields of RANGE. */ @@ -1390,6 +1277,7 @@ rangelist_intersect_or_remove(svn_rangelist_t **output, while (i1 < rangelist1->nelts && i2 < rangelist2->nelts) { svn_merge_range_t *elt1, *elt2; + svn_boolean_t elt1_contains_elt2, elt1_intersects_elt2; elt1 = APR_ARRAY_IDX(rangelist1, i1, svn_merge_range_t *); @@ -1405,6 +1293,10 @@ rangelist_intersect_or_remove(svn_rangelist_t **output, elt2 = &working_elt2; + SVN_ERR(range_contains(&elt1_contains_elt2, + elt1, elt2, consider_inheritance)); + SVN_ERR(range_intersect(&elt1_intersects_elt2, + elt1, elt2, consider_inheritance)); /* If the rangelist2 range is contained completely in the rangelist1, we increment the rangelist2. If the ranges intersect, and match exactly, we increment both @@ -1413,7 +1305,7 @@ rangelist_intersect_or_remove(svn_rangelist_t **output, the removal of rangelist1 from rangelist2, and possibly change the rangelist2 to the remaining portion of the right part of the removal, to test against. */ - if (range_contains(elt1, elt2, consider_inheritance)) + if (elt1_contains_elt2) { if (!do_remove) { @@ -1434,7 +1326,7 @@ rangelist_intersect_or_remove(svn_rangelist_t **output, if (elt2->start == elt1->start && elt2->end == elt1->end) i1++; } - else if (range_intersect(elt1, elt2, consider_inheritance)) + else if (elt1_intersects_elt2) { if (elt2->start < elt1->start) { @@ -1977,18 +1869,21 @@ svn_rangelist_to_string(svn_string_t **output, { int i; svn_merge_range_t *range; + char *s; /* Handle the elements that need commas at the end. */ for (i = 0; i < rangelist->nelts - 1; i++) { range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *); - svn_stringbuf_appendcstr(buf, range_to_string(range, pool)); + SVN_ERR(range_to_string(&s, range, pool)); + svn_stringbuf_appendcstr(buf, s); svn_stringbuf_appendcstr(buf, ","); } /* Now handle the last element, which needs no comma. */ range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *); - svn_stringbuf_appendcstr(buf, range_to_string(range, pool)); + SVN_ERR(range_to_string(&s, range, pool)); + svn_stringbuf_appendcstr(buf, s); } *output = svn_stringbuf__morph_into_string(buf); |