2 * mergeinfo.c: Mergeinfo parsing and handling
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
13 * http://www.apache.org/licenses/LICENSE-2.0
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
21 * ====================================================================
27 #include "svn_types.h"
28 #include "svn_ctype.h"
29 #include "svn_pools.h"
30 #include "svn_sorts.h"
31 #include "svn_error.h"
32 #include "svn_error_codes.h"
33 #include "svn_string.h"
34 #include "svn_mergeinfo.h"
35 #include "private/svn_fspath.h"
36 #include "private/svn_mergeinfo_private.h"
37 #include "private/svn_string_private.h"
38 #include "private/svn_subr_private.h"
39 #include "svn_private_config.h"
41 #include "private/svn_dep_compat.h"
43 /* Attempt to combine two ranges, IN1 and IN2. If they are adjacent or
44 overlapping, and their inheritability allows them to be combined, put
45 the result in OUTPUT and return TRUE, otherwise return FALSE.
47 CONSIDER_INHERITANCE determines how to account for the inheritability
48 of IN1 and IN2 when trying to combine ranges. If ranges with different
49 inheritability are combined (CONSIDER_INHERITANCE must be FALSE for this
50 to happen) the result is inheritable. If both ranges are inheritable the
51 result is inheritable. Only and if both ranges are non-inheritable is
52 the result is non-inheritable.
54 Range overlapping detection algorithm from
55 http://c2.com/cgi-bin/wiki/fullSearch?TestIfDateRangesOverlap
58 combine_ranges(svn_merge_range_t *output,
59 const svn_merge_range_t *in1,
60 const svn_merge_range_t *in2,
61 svn_boolean_t consider_inheritance)
63 if (in1->start <= in2->end && in2->start <= in1->end)
65 if (!consider_inheritance
66 || (consider_inheritance
67 && (in1->inheritable == in2->inheritable)))
69 output->start = MIN(in1->start, in2->start);
70 output->end = MAX(in1->end, in2->end);
71 output->inheritable = (in1->inheritable || in2->inheritable);
78 /* pathname -> PATHNAME */
80 parse_pathname(const char **input,
82 const char **pathname,
85 const char *curr = *input;
86 const char *last_colon = NULL;
88 /* A pathname may contain colons, so find the last colon before END
89 or newline. We'll consider this the divider between the pathname
90 and the revisionlist. */
91 while (curr < end && *curr != '\n')
99 return svn_error_create(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
100 _("Pathname not terminated by ':'"));
101 if (last_colon == *input)
102 return svn_error_create(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
103 _("No pathname preceding ':'"));
105 /* Tolerate relative repository paths, but convert them to absolute.
106 ### Efficiency? 1 string duplication here, 2 in canonicalize. */
107 *pathname = svn_fspath__canonicalize(apr_pstrndup(pool, *input,
108 last_colon - *input),
116 /* Return TRUE iff (svn_merge_range_t *) RANGE describes a valid, forward
119 * Note: The smallest valid value of RANGE->start is 0 because it is an
120 * exclusive endpoint, being one less than the revision number of the first
121 * change described by the range, and the oldest possible change is "r1" as
122 * there cannot be a change "r0". */
123 #define IS_VALID_FORWARD_RANGE(range) \
124 (SVN_IS_VALID_REVNUM((range)->start) && ((range)->start < (range)->end))
126 /* Ways in which two svn_merge_range_t can intersect or adjoin, if at all. */
127 typedef enum intersection_type_t
129 /* Ranges don't intersect and don't adjoin. */
130 svn__no_intersection,
132 /* Ranges are equal. */
133 svn__equal_intersection,
135 /* Ranges adjoin but don't overlap. */
136 svn__adjoining_intersection,
138 /* Ranges overlap but neither is a subset of the other. */
139 svn__overlapping_intersection,
141 /* One range is a proper subset of the other. */
142 svn__proper_subset_intersection
143 } intersection_type_t;
145 /* Given ranges R1 and R2, both of which must be forward merge ranges,
146 set *INTERSECTION_TYPE to describe how the ranges intersect, if they
147 do at all. The inheritance type of the ranges is not considered. */
149 get_type_of_intersection(const svn_merge_range_t *r1,
150 const svn_merge_range_t *r2,
151 intersection_type_t *intersection_type)
155 SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(r1));
156 SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(r2));
158 if (!(r1->start <= r2->end && r2->start <= r1->end))
159 *intersection_type = svn__no_intersection;
160 else if (r1->start == r2->start && r1->end == r2->end)
161 *intersection_type = svn__equal_intersection;
162 else if (r1->end == r2->start || r2->end == r1->start)
163 *intersection_type = svn__adjoining_intersection;
164 else if (r1->start <= r2->start && r1->end >= r2->end)
165 *intersection_type = svn__proper_subset_intersection;
166 else if (r2->start <= r1->start && r2->end >= r1->end)
167 *intersection_type = svn__proper_subset_intersection;
169 *intersection_type = svn__overlapping_intersection;
174 /* Modify or extend RANGELIST (a list of merge ranges) to incorporate
175 NEW_RANGE. RANGELIST is a "rangelist" as defined in svn_mergeinfo.h.
179 Determine the minimal set of non-overlapping merge ranges required to
180 represent the combination of RANGELIST and NEW_RANGE. The result depends
181 on whether and how NEW_RANGE overlaps any merge range[*] in RANGELIST,
182 and also on any differences in the inheritability of each range,
183 according to the rules described below. Modify RANGELIST to represent
184 this result, by adjusting the last range in it and/or appending one or
187 ([*] Due to the simplifying assumption below, only the last range in
188 RANGELIST is considered.)
192 If RANGELIST is not empty assume NEW_RANGE does not intersect with any
193 range before the last one in RANGELIST.
195 If RANGELIST is empty or NEW_RANGE does not intersect with the lastrange
196 in RANGELIST, then append a copy of NEW_RANGE, allocated in RESULT_POOL,
199 If NEW_RANGE intersects with the last range in RANGELIST then combine
200 these two ranges as described below:
202 If the intersecting ranges have the same inheritability then simply
203 combine the ranges in place. Otherwise, if the ranges intersect but
204 differ in inheritability, then merge the ranges as dictated by
205 CONSIDER_INHERITANCE:
207 If CONSIDER_INHERITANCE is false then intersecting ranges are combined
208 into a single range. The inheritability of the resulting range is
209 non-inheritable *only* if both ranges are non-inheritable, otherwise the
210 combined range is inheritable, e.g.:
212 Last range in NEW_RANGE RESULTING RANGES
214 ------------- --------- ----------------
219 If CONSIDER_INHERITANCE is true, then only the intersection between the
220 two ranges is combined, with the inheritability of the resulting range
221 non-inheritable only if both ranges were non-inheritable. The
222 non-intersecting portions are added as separate ranges allocated in
225 Last range in NEW_RANGE RESULTING RANGES
227 ------------- --------- ----------------
228 4-10* 6 4-5*, 6, 7-10*
229 4-10* 6-12 4-5*, 6-12
231 Note that the standard rules for rangelists still apply and overlapping
232 ranges are not allowed. So if the above would result in overlapping
233 ranges of the same inheritance, the overlapping ranges are merged into a
236 Last range in NEW_RANGE RESULTING RANGES
238 ------------- --------- ----------------
239 4-10 6* 4-10 (Not 4-5, 6, 7-10)
241 When replacing the last range in RANGELIST, either allocate a new range in
242 RESULT_POOL or modify the existing range in place. Any new ranges added
243 to RANGELIST are allocated in RESULT_POOL.
246 combine_with_lastrange(const svn_merge_range_t *new_range,
247 svn_rangelist_t *rangelist,
248 svn_boolean_t consider_inheritance,
249 apr_pool_t *result_pool)
251 svn_merge_range_t *lastrange;
252 svn_merge_range_t combined_range;
254 /* We don't accept a NULL RANGELIST. */
255 SVN_ERR_ASSERT(rangelist);
257 if (rangelist->nelts > 0)
258 lastrange = APR_ARRAY_IDX(rangelist, rangelist->nelts - 1, svn_merge_range_t *);
264 /* No *LASTRANGE so push NEW_RANGE onto RANGELIST and we are done. */
265 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
266 svn_merge_range_dup(new_range, result_pool);
268 else if (!consider_inheritance)
270 /* We are not considering inheritance so we can merge intersecting
271 ranges of different inheritability. Of course if the ranges
272 don't intersect at all we simply push NEW_RANGE only RANGELIST. */
273 if (combine_ranges(&combined_range, lastrange, new_range, FALSE))
275 *lastrange = combined_range;
279 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
280 svn_merge_range_dup(new_range, result_pool);
283 else /* Considering inheritance */
285 if (combine_ranges(&combined_range, lastrange, new_range, TRUE))
287 /* Even when considering inheritance two intersection ranges
288 of the same inheritability can simply be combined. */
289 *lastrange = combined_range;
293 /* If we are here then the ranges either don't intersect or do
294 intersect but have differing inheritability. Check for the
295 first case as that is easy to handle. */
296 intersection_type_t intersection_type;
297 svn_boolean_t sorted = FALSE;
299 SVN_ERR(get_type_of_intersection(new_range, lastrange,
300 &intersection_type));
302 switch (intersection_type)
304 case svn__no_intersection:
305 /* NEW_RANGE and *LASTRANGE *really* don't intersect so
306 just push NEW_RANGE only RANGELIST. */
307 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
308 svn_merge_range_dup(new_range, result_pool);
309 sorted = (svn_sort_compare_ranges(&lastrange,
313 case svn__equal_intersection:
314 /* They range are equal so all we do is force the
315 inheritability of lastrange to true. */
316 lastrange->inheritable = TRUE;
320 case svn__adjoining_intersection:
321 /* They adjoin but don't overlap so just push NEW_RANGE
323 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
324 svn_merge_range_dup(new_range, result_pool);
325 sorted = (svn_sort_compare_ranges(&lastrange,
329 case svn__overlapping_intersection:
330 /* They ranges overlap but neither is a proper subset of
331 the other. We'll end up pusing two new ranges onto
332 RANGELIST, the intersecting part and the part unique to
335 svn_merge_range_t *r1 = svn_merge_range_dup(lastrange,
337 svn_merge_range_t *r2 = svn_merge_range_dup(new_range,
340 /* Pop off *LASTRANGE to make our manipulations
342 apr_array_pop(rangelist);
344 /* Ensure R1 is the older range. */
345 if (r2->start < r1->start)
347 /* Swap R1 and R2. */
352 /* Absorb the intersecting ranges into the
353 inheritable range. */
359 /* Push everything back onto RANGELIST. */
360 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r1;
361 sorted = (svn_sort_compare_ranges(&lastrange,
363 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r2;
365 sorted = (svn_sort_compare_ranges(&r1, &r2) < 0);
369 default: /* svn__proper_subset_intersection */
371 /* One range is a proper subset of the other. */
372 svn_merge_range_t *r1 = svn_merge_range_dup(lastrange,
374 svn_merge_range_t *r2 = svn_merge_range_dup(new_range,
376 svn_merge_range_t *r3 = NULL;
378 /* Pop off *LASTRANGE to make our manipulations
380 apr_array_pop(rangelist);
382 /* Ensure R1 is the superset. */
383 if (r2->start < r1->start || r2->end > r1->end)
385 /* Swap R1 and R2. */
392 /* The simple case: The superset is inheritable, so
393 just combine r1 and r2. */
394 r1->start = MIN(r1->start, r2->start);
395 r1->end = MAX(r1->end, r2->end);
398 else if (r1->start == r2->start)
400 svn_revnum_t tmp_revnum;
402 /* *LASTRANGE and NEW_RANGE share an end point. */
403 tmp_revnum = r1->end;
405 r2->inheritable = r1->inheritable;
406 r1->inheritable = TRUE;
408 r2->end = tmp_revnum;
410 else if (r1->end == r2->end)
412 /* *LASTRANGE and NEW_RANGE share an end point. */
414 r2->inheritable = TRUE;
418 /* NEW_RANGE and *LASTRANGE share neither start
420 r3 = apr_pcalloc(result_pool, sizeof(*r3));
423 r3->inheritable = r1->inheritable;
424 r2->inheritable = TRUE;
428 /* Push everything back onto RANGELIST. */
429 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r1;
430 sorted = (svn_sort_compare_ranges(&lastrange, &r1) < 0);
433 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r2;
435 sorted = (svn_sort_compare_ranges(&r1, &r2) < 0);
439 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r3;
443 sorted = (svn_sort_compare_ranges(&r2,
446 sorted = (svn_sort_compare_ranges(&r1,
454 /* Some of the above cases might have put *RANGELIST out of
457 qsort(rangelist->elts, rangelist->nelts, rangelist->elt_size,
458 svn_sort_compare_ranges);
465 /* Convert a single svn_merge_range_t *RANGE back into a string. */
467 range_to_string(const svn_merge_range_t *range,
471 = range->inheritable ? "" : SVN_MERGEINFO_NONINHERITABLE_STR;
473 if (range->start == range->end - 1)
474 return apr_psprintf(pool, "%ld%s", range->end, mark);
475 else if (range->start - 1 == range->end)
476 return apr_psprintf(pool, "-%ld%s", range->start, mark);
477 else if (range->start < range->end)
478 return apr_psprintf(pool, "%ld-%ld%s", range->start + 1, range->end, mark);
480 return apr_psprintf(pool, "%ld-%ld%s", range->start, range->end + 1, mark);
483 /* Helper for svn_mergeinfo_parse()
484 Append revision ranges onto the array RANGELIST to represent the range
485 descriptions found in the string *INPUT. Read only as far as a newline
486 or the position END, whichever comes first. Set *INPUT to the position
487 after the last character of INPUT that was used.
489 revisionlist -> (revisionelement)(COMMA revisionelement)*
490 revisionrange -> REVISION "-" REVISION("*")
491 revisionelement -> revisionrange | REVISION("*")
494 parse_rangelist(const char **input, const char *end,
495 svn_rangelist_t *rangelist,
498 const char *curr = *input;
500 /* Eat any leading horizontal white-space before the rangelist. */
501 while (curr < end && *curr != '\n' && isspace(*curr))
504 if (*curr == '\n' || curr == end)
506 /* Empty range list. */
511 while (curr < end && *curr != '\n')
513 /* Parse individual revisions or revision ranges. */
514 svn_merge_range_t *mrange = apr_pcalloc(pool, sizeof(*mrange));
515 svn_revnum_t firstrev;
517 SVN_ERR(svn_revnum_parse(&firstrev, curr, &curr));
518 if (*curr != '-' && *curr != '\n' && *curr != ',' && *curr != '*'
520 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
521 _("Invalid character '%c' found in revision "
523 mrange->start = firstrev - 1;
524 mrange->end = firstrev;
525 mrange->inheritable = TRUE;
528 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
529 _("Invalid revision number '0' found in "
534 svn_revnum_t secondrev;
537 SVN_ERR(svn_revnum_parse(&secondrev, curr, &curr));
538 if (firstrev > secondrev)
539 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
540 _("Unable to parse reversed revision "
542 firstrev, secondrev);
543 else if (firstrev == secondrev)
544 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
545 _("Unable to parse revision range "
546 "'%ld-%ld' with same start and end "
547 "revisions"), firstrev, secondrev);
548 mrange->end = secondrev;
551 if (*curr == '\n' || curr == end)
553 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = mrange;
557 else if (*curr == ',')
559 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = mrange;
562 else if (*curr == '*')
564 mrange->inheritable = FALSE;
566 if (*curr == ',' || *curr == '\n' || curr == end)
568 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = mrange;
581 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
582 _("Invalid character '%c' found in "
583 "range list"), *curr);
588 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
589 _("Invalid character '%c' found in "
590 "range list"), *curr);
595 return svn_error_create(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
596 _("Range list parsing ended before hitting "
603 svn_rangelist__parse(svn_rangelist_t **rangelist,
605 apr_pool_t *result_pool)
609 *rangelist = apr_array_make(result_pool, 1, sizeof(svn_merge_range_t *));
610 SVN_ERR(parse_rangelist(&s, s + strlen(s), *rangelist, result_pool));
614 /* Return TRUE, if all ranges in RANGELIST are in ascending order and do
615 * not overlap and are not adjacent.
617 * ### Can yield false negatives: ranges of differing inheritance are
618 * allowed to be adjacent.
620 * If this returns FALSE, you probaly want to qsort() the
621 * ranges and then call svn_rangelist__combine_adjacent_ranges().
624 is_rangelist_normalized(svn_rangelist_t *rangelist)
627 svn_merge_range_t **ranges = (svn_merge_range_t **)rangelist->elts;
629 for (i = 0; i < rangelist->nelts-1; ++i)
630 if (ranges[i]->end >= ranges[i+1]->start)
637 svn_rangelist__canonicalize(svn_rangelist_t *rangelist,
638 apr_pool_t *scratch_pool)
640 if (! is_rangelist_normalized(rangelist))
642 qsort(rangelist->elts, rangelist->nelts, rangelist->elt_size,
643 svn_sort_compare_ranges);
645 SVN_ERR(svn_rangelist__combine_adjacent_ranges(rangelist, scratch_pool));
652 svn_rangelist__combine_adjacent_ranges(svn_rangelist_t *rangelist,
653 apr_pool_t *scratch_pool)
656 svn_merge_range_t *range, *lastrange;
658 lastrange = APR_ARRAY_IDX(rangelist, 0, svn_merge_range_t *);
660 for (i = 1; i < rangelist->nelts; i++)
662 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
663 if (lastrange->start <= range->end
664 && range->start <= lastrange->end)
666 /* The ranges are adjacent or intersect. */
668 /* svn_mergeinfo_parse promises to combine overlapping
669 ranges as long as their inheritability is the same. */
670 if (range->start < lastrange->end
671 && range->inheritable != lastrange->inheritable)
673 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
674 _("Unable to parse overlapping "
675 "revision ranges '%s' and '%s' "
676 "with different inheritance "
678 range_to_string(lastrange,
680 range_to_string(range,
684 /* Combine overlapping or adjacent ranges with the
685 same inheritability. */
686 if (lastrange->inheritable == range->inheritable)
688 lastrange->end = MAX(range->end, lastrange->end);
689 svn_sort__array_delete(rangelist, i, 1);
693 lastrange = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
699 /* revisionline -> PATHNAME COLON revisionlist */
701 parse_revision_line(const char **input, const char *end, svn_mergeinfo_t hash,
702 apr_pool_t *scratch_pool)
704 const char *pathname = "";
706 svn_rangelist_t *existing_rangelist;
707 svn_rangelist_t *rangelist = apr_array_make(scratch_pool, 1,
708 sizeof(svn_merge_range_t *));
710 SVN_ERR(parse_pathname(input, end, &pathname, scratch_pool));
712 if (*(*input) != ':')
713 return svn_error_create(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
714 _("Pathname not terminated by ':'"));
718 SVN_ERR(parse_rangelist(input, end, rangelist, scratch_pool));
720 if (rangelist->nelts == 0)
721 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
722 _("Mergeinfo for '%s' maps to an "
723 "empty revision range"), pathname);
724 if (*input != end && *(*input) != '\n')
725 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
726 _("Could not find end of line in range list line "
732 /* Sort the rangelist, combine adjacent ranges into single ranges, and
733 make sure there are no overlapping ranges. Luckily, most data in
734 svn:mergeinfo will already be in normalized form and this will be quick.
736 SVN_ERR(svn_rangelist__canonicalize(rangelist, scratch_pool));
738 /* Handle any funky mergeinfo with relative merge source paths that
739 might exist due to issue #3547. It's possible that this issue allowed
740 the creation of mergeinfo with path keys that differ only by a
741 leading slash, e.g. "trunk:4033\n/trunk:4039-4995". In the event
742 we encounter this we merge the rangelists together under a single
743 absolute path key. */
744 klen = strlen(pathname);
745 existing_rangelist = apr_hash_get(hash, pathname, klen);
746 if (existing_rangelist)
747 SVN_ERR(svn_rangelist_merge2(rangelist, existing_rangelist,
748 scratch_pool, scratch_pool));
750 apr_hash_set(hash, apr_pstrmemdup(apr_hash_pool_get(hash), pathname, klen),
751 klen, svn_rangelist_dup(rangelist, apr_hash_pool_get(hash)));
756 /* top -> revisionline (NEWLINE revisionline)* */
758 parse_top(const char **input, const char *end, svn_mergeinfo_t hash,
761 apr_pool_t *iterpool = svn_pool_create(pool);
765 svn_pool_clear(iterpool);
766 SVN_ERR(parse_revision_line(input, end, hash, iterpool));
768 svn_pool_destroy(iterpool);
774 svn_mergeinfo_parse(svn_mergeinfo_t *mergeinfo,
780 *mergeinfo = svn_hash__make(pool);
781 err = parse_top(&input, input + strlen(input), *mergeinfo, pool);
783 /* Always return SVN_ERR_MERGEINFO_PARSE_ERROR as the topmost error. */
784 if (err && err->apr_err != SVN_ERR_MERGEINFO_PARSE_ERROR)
785 err = svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, err,
786 _("Could not parse mergeinfo string '%s'"),
791 /* Cleanup after svn_rangelist_merge2 when it modifies the ending range of
792 a single rangelist element in-place.
794 If *RANGE_INDEX is not a valid element in RANGELIST do nothing. Otherwise
795 ensure that RANGELIST[*RANGE_INDEX]->END does not adjoin or overlap any
796 subsequent ranges in RANGELIST.
798 If overlap is found, then remove, modify, and/or add elements to RANGELIST
799 as per the invariants for rangelists documented in svn_mergeinfo.h. If
800 RANGELIST[*RANGE_INDEX]->END adjoins a subsequent element then combine the
801 elements if their inheritability permits -- The inheritance of intersecting
802 and adjoining ranges is handled as per svn_mergeinfo_merge2. Upon return
803 set *RANGE_INDEX to the index of the youngest element modified, added, or
804 adjoined to RANGELIST[*RANGE_INDEX].
806 Note: Adjoining rangelist elements are those where the end rev of the older
807 element is equal to the start rev of the younger element.
809 Any new elements inserted into RANGELIST are allocated in RESULT_POOL.*/
811 adjust_remaining_ranges(svn_rangelist_t *rangelist,
813 apr_pool_t *result_pool)
817 int elements_to_delete = 0;
818 svn_merge_range_t *modified_range;
820 if (*range_index >= rangelist->nelts)
823 starting_index = *range_index + 1;
824 modified_range = APR_ARRAY_IDX(rangelist, *range_index, svn_merge_range_t *);
826 for (i = *range_index + 1; i < rangelist->nelts; i++)
828 svn_merge_range_t *next_range = APR_ARRAY_IDX(rangelist, i,
829 svn_merge_range_t *);
831 /* If MODIFIED_RANGE doesn't adjoin or overlap the next range in
832 RANGELIST then we are finished. */
833 if (modified_range->end < next_range->start)
836 /* Does MODIFIED_RANGE adjoin NEXT_RANGE? */
837 if (modified_range->end == next_range->start)
839 if (modified_range->inheritable == next_range->inheritable)
841 /* Combine adjoining ranges with the same inheritability. */
842 modified_range->end = next_range->end;
843 elements_to_delete++;
847 /* Cannot join because inheritance differs. */
853 /* Alright, we know MODIFIED_RANGE overlaps NEXT_RANGE, but how? */
854 if (modified_range->end > next_range->end)
856 /* NEXT_RANGE is a proper subset of MODIFIED_RANGE and the two
857 don't share the same end range. */
858 if (modified_range->inheritable
859 || (modified_range->inheritable == next_range->inheritable))
861 /* MODIFIED_RANGE absorbs NEXT_RANGE. */
862 elements_to_delete++;
866 /* NEXT_RANGE is a proper subset MODIFIED_RANGE but
867 MODIFIED_RANGE is non-inheritable and NEXT_RANGE is
868 inheritable. This means MODIFIED_RANGE is truncated,
869 NEXT_RANGE remains, and the portion of MODIFIED_RANGE
870 younger than NEXT_RANGE is added as a separate range:
871 ______________________________________________
875 |______________________________________________|
882 _______________________________________________
884 M MODIFIED_RANGE O NEXT_RANGE P NEW_RANGE N
885 | (!inhertiable) | (inheritable)| (!inheritable)|
886 |________________|______________|_______________|
888 svn_merge_range_t *new_modified_range =
889 apr_palloc(result_pool, sizeof(*new_modified_range));
890 new_modified_range->start = next_range->end;
891 new_modified_range->end = modified_range->end;
892 new_modified_range->inheritable = FALSE;
893 modified_range->end = next_range->start;
895 svn_sort__array_insert(&new_modified_range, rangelist,
897 /* Recurse with the new range. */
898 adjust_remaining_ranges(rangelist, range_index, result_pool);
902 else if (modified_range->end == next_range->end)
904 /* NEXT_RANGE is a proper subset MODIFIED_RANGE and share
905 the same end range. */
906 if (modified_range->inheritable
907 || (modified_range->inheritable == next_range->inheritable))
909 /* MODIFIED_RANGE absorbs NEXT_RANGE. */
910 elements_to_delete++;
914 /* The intersection between MODIFIED_RANGE and NEXT_RANGE is
915 absorbed by the latter. */
916 modified_range->end = next_range->start;
923 /* NEXT_RANGE and MODIFIED_RANGE intersect but NEXT_RANGE is not
924 a proper subset of MODIFIED_RANGE, nor do the two share the
925 same end revision, i.e. they overlap. */
926 if (modified_range->inheritable == next_range->inheritable)
928 /* Combine overlapping ranges with the same inheritability. */
929 modified_range->end = next_range->end;
930 elements_to_delete++;
932 else if (modified_range->inheritable)
934 /* MODIFIED_RANGE absorbs the portion of NEXT_RANGE it overlaps
935 and NEXT_RANGE is truncated. */
936 next_range->start = modified_range->end;
941 /* NEXT_RANGE absorbs the portion of MODIFIED_RANGE it overlaps
942 and MODIFIED_RANGE is truncated. */
943 modified_range->end = next_range->start;
950 if (elements_to_delete)
951 svn_sort__array_delete(rangelist, starting_index, elements_to_delete);
955 svn_rangelist_merge2(svn_rangelist_t *rangelist,
956 const svn_rangelist_t *changes,
957 apr_pool_t *result_pool,
958 apr_pool_t *scratch_pool)
963 /* We may modify CHANGES, so make a copy in SCRATCH_POOL. */
964 changes = svn_rangelist_dup(changes, scratch_pool);
966 while (i < rangelist->nelts && j < changes->nelts)
968 svn_merge_range_t *range =
969 APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
970 svn_merge_range_t *change =
971 APR_ARRAY_IDX(changes, j, svn_merge_range_t *);
972 int res = svn_sort_compare_ranges(&range, &change);
976 /* Only when merging two non-inheritable ranges is the result also
977 non-inheritable. In all other cases ensure an inheritiable
979 if (range->inheritable || change->inheritable)
980 range->inheritable = TRUE;
984 else if (res < 0) /* CHANGE is younger than RANGE */
986 if (range->end < change->start)
988 /* RANGE is older than CHANGE and the two do not
992 else if (range->end == change->start)
994 /* RANGE and CHANGE adjoin */
995 if (range->inheritable == change->inheritable)
997 /* RANGE and CHANGE have the same inheritability so
998 RANGE expands to absord CHANGE. */
999 range->end = change->end;
1000 adjust_remaining_ranges(rangelist, &i, result_pool);
1005 /* RANGE and CHANGE adjoin, but have different
1006 inheritability. Since RANGE is older, just
1007 move on to the next RANGE. */
1013 /* RANGE and CHANGE overlap, but how? */
1014 if ((range->inheritable == change->inheritable)
1015 || range->inheritable)
1017 /* If CHANGE is a proper subset of RANGE, it absorbs RANGE
1018 with no adjustment otherwise only the intersection is
1019 absorbed and CHANGE is truncated. */
1020 if (range->end >= change->end)
1023 change->start = range->end;
1027 /* RANGE is non-inheritable and CHANGE is inheritable. */
1028 if (range->start < change->start)
1030 /* CHANGE absorbs intersection with RANGE and RANGE
1032 svn_merge_range_t *range_copy =
1033 svn_merge_range_dup(range, result_pool);
1034 range_copy->end = change->start;
1035 range->start = change->start;
1036 svn_sort__array_insert(&range_copy, rangelist, i++);
1040 /* CHANGE and RANGE share the same start rev, but
1041 RANGE is considered older because its end rev
1043 range->inheritable = TRUE;
1044 change->start = range->end;
1049 else /* res > 0, CHANGE is older than RANGE */
1051 if (change->end < range->start)
1053 /* CHANGE is older than RANGE and the two do not
1054 adjoin or overlap, so insert a copy of CHANGE
1056 svn_merge_range_t *change_copy =
1057 svn_merge_range_dup(change, result_pool);
1058 svn_sort__array_insert(&change_copy, rangelist, i++);
1061 else if (change->end == range->start)
1063 /* RANGE and CHANGE adjoin */
1064 if (range->inheritable == change->inheritable)
1066 /* RANGE and CHANGE have the same inheritability so we
1067 can simply combine the two in place. */
1068 range->start = change->start;
1073 /* RANGE and CHANGE have different inheritability so insert
1074 a copy of CHANGE into RANGELIST. */
1075 svn_merge_range_t *change_copy =
1076 svn_merge_range_dup(change, result_pool);
1077 svn_sort__array_insert(&change_copy, rangelist, i);
1083 /* RANGE and CHANGE overlap. */
1084 if (range->inheritable == change->inheritable)
1086 /* RANGE and CHANGE have the same inheritability so we
1087 can simply combine the two in place... */
1088 range->start = change->start;
1089 if (range->end < change->end)
1091 /* ...but if RANGE is expanded ensure that we don't
1092 violate any rangelist invariants. */
1093 range->end = change->end;
1094 adjust_remaining_ranges(rangelist, &i, result_pool);
1098 else if (range->inheritable)
1100 if (change->start < range->start)
1102 /* RANGE is inheritable so absorbs any part of CHANGE
1103 it overlaps. CHANGE is truncated and the remainder
1104 inserted into RANGELIST. */
1105 svn_merge_range_t *change_copy =
1106 svn_merge_range_dup(change, result_pool);
1107 change_copy->end = range->start;
1108 change->start = range->start;
1109 svn_sort__array_insert(&change_copy, rangelist, i++);
1113 /* CHANGE and RANGE share the same start rev, but
1114 CHANGE is considered older because CHANGE->END is
1115 older than RANGE->END. */
1121 /* RANGE is non-inheritable and CHANGE is inheritable. */
1122 if (change->start < range->start)
1124 if (change->end == range->end)
1126 /* RANGE is a proper subset of CHANGE and share the
1127 same end revision, so set RANGE equal to CHANGE. */
1128 range->start = change->start;
1129 range->inheritable = TRUE;
1132 else if (change->end > range->end)
1134 /* RANGE is a proper subset of CHANGE and CHANGE has
1135 a younger end revision, so set RANGE equal to its
1136 intersection with CHANGE and truncate CHANGE. */
1137 range->start = change->start;
1138 range->inheritable = TRUE;
1139 change->start = range->end;
1143 /* CHANGE and RANGE overlap. Set RANGE equal to its
1144 intersection with CHANGE and take the remainder
1145 of RANGE and insert it into RANGELIST. */
1146 svn_merge_range_t *range_copy =
1147 svn_merge_range_dup(range, result_pool);
1148 range_copy->start = change->end;
1149 range->start = change->start;
1150 range->end = change->end;
1151 range->inheritable = TRUE;
1152 svn_sort__array_insert(&range_copy, rangelist, ++i);
1158 /* CHANGE and RANGE share the same start rev, but
1159 CHANGE is considered older because its end rev
1162 Insert the intersection of RANGE and CHANGE into
1163 RANGELIST and then set RANGE to the non-intersecting
1164 portion of RANGE. */
1165 svn_merge_range_t *range_copy =
1166 svn_merge_range_dup(range, result_pool);
1167 range_copy->end = change->end;
1168 range_copy->inheritable = TRUE;
1169 range->start = change->end;
1170 svn_sort__array_insert(&range_copy, rangelist, i++);
1178 /* Copy any remaining elements in CHANGES into RANGELIST. */
1179 for (; j < (changes)->nelts; j++)
1181 svn_merge_range_t *change =
1182 APR_ARRAY_IDX(changes, j, svn_merge_range_t *);
1183 svn_merge_range_t *change_copy = svn_merge_range_dup(change,
1185 svn_sort__array_insert(&change_copy, rangelist, rangelist->nelts);
1188 return SVN_NO_ERROR;
1191 /* Return TRUE iff the forward revision ranges FIRST and SECOND overlap and
1192 * (if CONSIDER_INHERITANCE is TRUE) have the same inheritability. */
1193 static svn_boolean_t
1194 range_intersect(const svn_merge_range_t *first, const svn_merge_range_t *second,
1195 svn_boolean_t consider_inheritance)
1197 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(first));
1198 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(second));
1200 return (first->start + 1 <= second->end)
1201 && (second->start + 1 <= first->end)
1202 && (!consider_inheritance
1203 || (!(first->inheritable) == !(second->inheritable)));
1206 /* Return TRUE iff the forward revision range FIRST wholly contains the
1207 * forward revision range SECOND and (if CONSIDER_INHERITANCE is TRUE) has
1208 * the same inheritability. */
1209 static svn_boolean_t
1210 range_contains(const svn_merge_range_t *first, const svn_merge_range_t *second,
1211 svn_boolean_t consider_inheritance)
1213 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(first));
1214 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(second));
1216 return (first->start <= second->start) && (second->end <= first->end)
1217 && (!consider_inheritance
1218 || (!(first->inheritable) == !(second->inheritable)));
1221 /* Swap start and end fields of RANGE. */
1223 range_swap_endpoints(svn_merge_range_t *range)
1225 svn_revnum_t swap = range->start;
1226 range->start = range->end;
1231 svn_rangelist_reverse(svn_rangelist_t *rangelist, apr_pool_t *pool)
1235 svn_sort__array_reverse(rangelist, pool);
1237 for (i = 0; i < rangelist->nelts; i++)
1239 range_swap_endpoints(APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *));
1242 return SVN_NO_ERROR;
1246 svn_rangelist__set_inheritance(svn_rangelist_t *rangelist,
1247 svn_boolean_t inheritable)
1252 svn_merge_range_t *range;
1254 for (i = 0; i < rangelist->nelts; i++)
1256 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
1257 range->inheritable = inheritable;
1264 svn_mergeinfo__set_inheritance(svn_mergeinfo_t mergeinfo,
1265 svn_boolean_t inheritable,
1266 apr_pool_t *scratch_pool)
1270 apr_hash_index_t *hi;
1272 for (hi = apr_hash_first(scratch_pool, mergeinfo);
1274 hi = apr_hash_next(hi))
1276 svn_rangelist_t *rangelist = svn__apr_hash_index_val(hi);
1279 svn_rangelist__set_inheritance(rangelist, inheritable);
1285 /* If DO_REMOVE is true, then remove any overlapping ranges described by
1286 RANGELIST1 from RANGELIST2 and place the results in *OUTPUT. When
1287 DO_REMOVE is true, RANGELIST1 is effectively the "eraser" and RANGELIST2
1290 If DO_REMOVE is false, then capture the intersection between RANGELIST1
1291 and RANGELIST2 and place the results in *OUTPUT. The ordering of
1292 RANGELIST1 and RANGELIST2 doesn't matter when DO_REMOVE is false.
1294 If CONSIDER_INHERITANCE is true, then take the inheritance of the
1295 ranges in RANGELIST1 and RANGELIST2 into account when comparing them
1296 for intersection, see the doc string for svn_rangelist_intersect().
1298 If CONSIDER_INHERITANCE is false, then ranges with differing inheritance
1299 may intersect, but the resulting intersection is non-inheritable only
1300 if both ranges were non-inheritable, e.g.:
1302 RANGELIST1 RANGELIST2 CONSIDER DO_REMOVE *OUTPUT
1304 ---------- ------ ----------- --------- -------
1306 90-420* 1-100 TRUE FALSE Empty Rangelist
1307 90-420 1-100* TRUE FALSE Empty Rangelist
1308 90-420 1-100 TRUE FALSE 90-100
1309 90-420* 1-100* TRUE FALSE 90-100*
1311 90-420* 1-100 FALSE FALSE 90-100
1312 90-420 1-100* FALSE FALSE 90-100
1313 90-420 1-100 FALSE FALSE 90-100
1314 90-420* 1-100* FALSE FALSE 90-100*
1316 Allocate the contents of *OUTPUT in POOL. */
1317 static svn_error_t *
1318 rangelist_intersect_or_remove(svn_rangelist_t **output,
1319 const svn_rangelist_t *rangelist1,
1320 const svn_rangelist_t *rangelist2,
1321 svn_boolean_t do_remove,
1322 svn_boolean_t consider_inheritance,
1326 svn_merge_range_t working_elt2;
1328 *output = apr_array_make(pool, 1, sizeof(svn_merge_range_t *));
1332 lasti2 = -1; /* Initialized to a value that "i2" will never be. */
1334 while (i1 < rangelist1->nelts && i2 < rangelist2->nelts)
1336 svn_merge_range_t *elt1, *elt2;
1338 elt1 = APR_ARRAY_IDX(rangelist1, i1, svn_merge_range_t *);
1340 /* Instead of making a copy of the entire array of rangelist2
1341 elements, we just keep a copy of the current rangelist2 element
1342 that needs to be used, and modify our copy if necessary. */
1346 *(APR_ARRAY_IDX(rangelist2, i2, svn_merge_range_t *));
1350 elt2 = &working_elt2;
1352 /* If the rangelist2 range is contained completely in the
1353 rangelist1, we increment the rangelist2.
1354 If the ranges intersect, and match exactly, we increment both
1355 rangelist1 and rangelist2.
1356 Otherwise, we have to generate a range for the left part of
1357 the removal of rangelist1 from rangelist2, and possibly change
1358 the rangelist2 to the remaining portion of the right part of
1359 the removal, to test against. */
1360 if (range_contains(elt1, elt2, consider_inheritance))
1364 svn_merge_range_t tmp_range;
1365 tmp_range.start = elt2->start;
1366 tmp_range.end = elt2->end;
1367 /* The intersection of two ranges is non-inheritable only
1368 if both ranges are non-inheritable. */
1369 tmp_range.inheritable =
1370 (elt2->inheritable || elt1->inheritable);
1371 SVN_ERR(combine_with_lastrange(&tmp_range, *output,
1372 consider_inheritance,
1378 if (elt2->start == elt1->start && elt2->end == elt1->end)
1381 else if (range_intersect(elt1, elt2, consider_inheritance))
1383 if (elt2->start < elt1->start)
1385 /* The rangelist2 range starts before the rangelist1 range. */
1386 svn_merge_range_t tmp_range;
1389 /* Retain the range that falls before the rangelist1
1391 tmp_range.start = elt2->start;
1392 tmp_range.end = elt1->start;
1393 tmp_range.inheritable = elt2->inheritable;
1397 /* Retain the range that falls between the rangelist1
1398 start and rangelist2 end. */
1399 tmp_range.start = elt1->start;
1400 tmp_range.end = MIN(elt2->end, elt1->end);
1401 /* The intersection of two ranges is non-inheritable only
1402 if both ranges are non-inheritable. */
1403 tmp_range.inheritable =
1404 (elt2->inheritable || elt1->inheritable);
1407 SVN_ERR(combine_with_lastrange(&tmp_range,
1408 *output, consider_inheritance,
1412 /* Set up the rest of the rangelist2 range for further
1414 if (elt2->end > elt1->end)
1416 /* The rangelist2 range ends after the rangelist1 range. */
1419 /* Partial overlap. */
1420 svn_merge_range_t tmp_range;
1421 tmp_range.start = MAX(elt2->start, elt1->start);
1422 tmp_range.end = elt1->end;
1423 /* The intersection of two ranges is non-inheritable only
1424 if both ranges are non-inheritable. */
1425 tmp_range.inheritable =
1426 (elt2->inheritable || elt1->inheritable);
1427 SVN_ERR(combine_with_lastrange(&tmp_range,
1429 consider_inheritance,
1433 working_elt2.start = elt1->end;
1434 working_elt2.end = elt2->end;
1439 else /* ranges don't intersect */
1441 /* See which side of the rangelist2 the rangelist1 is on. If it
1442 is on the left side, we need to move the rangelist1.
1444 If it is on past the rangelist2 on the right side, we
1445 need to output the rangelist2 and increment the
1447 if (svn_sort_compare_ranges(&elt1, &elt2) < 0)
1451 svn_merge_range_t *lastrange;
1453 if ((*output)->nelts > 0)
1454 lastrange = APR_ARRAY_IDX(*output, (*output)->nelts - 1,
1455 svn_merge_range_t *);
1459 if (do_remove && !(lastrange &&
1460 combine_ranges(lastrange, lastrange, elt2,
1461 consider_inheritance)))
1463 lastrange = svn_merge_range_dup(elt2, pool);
1464 APR_ARRAY_PUSH(*output, svn_merge_range_t *) = lastrange;
1473 /* Copy the current rangelist2 element if we didn't hit the end
1474 of the rangelist2, and we still had it around. This element
1475 may have been touched, so we can't just walk the rangelist2
1476 array, we have to use our copy. This case only happens when
1477 we ran out of rangelist1 before rangelist2, *and* we had changed
1478 the rangelist2 element. */
1479 if (i2 == lasti2 && i2 < rangelist2->nelts)
1481 SVN_ERR(combine_with_lastrange(&working_elt2, *output,
1482 consider_inheritance, pool));
1486 /* Copy any other remaining untouched rangelist2 elements. */
1487 for (; i2 < rangelist2->nelts; i2++)
1489 svn_merge_range_t *elt = APR_ARRAY_IDX(rangelist2, i2,
1490 svn_merge_range_t *);
1492 SVN_ERR(combine_with_lastrange(elt, *output,
1493 consider_inheritance, pool));
1497 return SVN_NO_ERROR;
1502 svn_rangelist_intersect(svn_rangelist_t **output,
1503 const svn_rangelist_t *rangelist1,
1504 const svn_rangelist_t *rangelist2,
1505 svn_boolean_t consider_inheritance,
1508 return rangelist_intersect_or_remove(output, rangelist1, rangelist2, FALSE,
1509 consider_inheritance, pool);
1513 svn_rangelist_remove(svn_rangelist_t **output,
1514 const svn_rangelist_t *eraser,
1515 const svn_rangelist_t *whiteboard,
1516 svn_boolean_t consider_inheritance,
1519 return rangelist_intersect_or_remove(output, eraser, whiteboard, TRUE,
1520 consider_inheritance, pool);
1524 svn_rangelist_diff(svn_rangelist_t **deleted, svn_rangelist_t **added,
1525 const svn_rangelist_t *from, const svn_rangelist_t *to,
1526 svn_boolean_t consider_inheritance,
1529 /* The following diagrams illustrate some common range delta scenarios:
1532 r0 <===========(=========)============[=========]===========> rHEAD
1535 (from) deleted deleted
1536 r0 <===========(=========[============]=========)===========> rHEAD
1540 r0 <===========(=========[============)=========]===========> rHEAD
1544 r0 <===========[=========(============]=========)===========> rHEAD
1548 r0 <===========[=========(============)=========]===========> rHEAD
1552 r0 <===(=[=)=]=[==]=[=(=)=]=[=]=[=(===|===(=)==|=|==[=(=]=)=> rHEAD
1556 /* The items that are present in from, but not in to, must have been
1558 SVN_ERR(svn_rangelist_remove(deleted, to, from, consider_inheritance,
1560 /* The items that are present in to, but not in from, must have been
1562 return svn_rangelist_remove(added, from, to, consider_inheritance, pool);
1565 struct mergeinfo_diff_baton
1567 svn_mergeinfo_t from;
1569 svn_mergeinfo_t deleted;
1570 svn_mergeinfo_t added;
1571 svn_boolean_t consider_inheritance;
1575 /* This implements the 'svn_hash_diff_func_t' interface.
1576 BATON is of type 'struct mergeinfo_diff_baton *'.
1578 static svn_error_t *
1579 mergeinfo_hash_diff_cb(const void *key, apr_ssize_t klen,
1580 enum svn_hash_diff_key_status status,
1583 /* hash_a is FROM mergeinfo,
1584 hash_b is TO mergeinfo. */
1585 struct mergeinfo_diff_baton *cb = baton;
1586 svn_rangelist_t *from_rangelist, *to_rangelist;
1587 const char *path = key;
1588 if (status == svn_hash_diff_key_both)
1590 /* Record any deltas (additions or deletions). */
1591 svn_rangelist_t *deleted_rangelist, *added_rangelist;
1592 from_rangelist = apr_hash_get(cb->from, path, klen);
1593 to_rangelist = apr_hash_get(cb->to, path, klen);
1594 SVN_ERR(svn_rangelist_diff(&deleted_rangelist, &added_rangelist,
1595 from_rangelist, to_rangelist,
1596 cb->consider_inheritance, cb->pool));
1597 if (cb->deleted && deleted_rangelist->nelts > 0)
1598 apr_hash_set(cb->deleted, apr_pstrmemdup(cb->pool, path, klen),
1599 klen, deleted_rangelist);
1600 if (cb->added && added_rangelist->nelts > 0)
1601 apr_hash_set(cb->added, apr_pstrmemdup(cb->pool, path, klen),
1602 klen, added_rangelist);
1604 else if ((status == svn_hash_diff_key_a) && cb->deleted)
1606 from_rangelist = apr_hash_get(cb->from, path, klen);
1607 apr_hash_set(cb->deleted, apr_pstrmemdup(cb->pool, path, klen), klen,
1608 svn_rangelist_dup(from_rangelist, cb->pool));
1610 else if ((status == svn_hash_diff_key_b) && cb->added)
1612 to_rangelist = apr_hash_get(cb->to, path, klen);
1613 apr_hash_set(cb->added, apr_pstrmemdup(cb->pool, path, klen), klen,
1614 svn_rangelist_dup(to_rangelist, cb->pool));
1616 return SVN_NO_ERROR;
1619 /* Record deletions and additions of entire range lists (by path
1620 presence), and delegate to svn_rangelist_diff() for delta
1621 calculations on a specific path. */
1622 static svn_error_t *
1623 walk_mergeinfo_hash_for_diff(svn_mergeinfo_t from, svn_mergeinfo_t to,
1624 svn_mergeinfo_t deleted, svn_mergeinfo_t added,
1625 svn_boolean_t consider_inheritance,
1626 apr_pool_t *result_pool,
1627 apr_pool_t *scratch_pool)
1629 struct mergeinfo_diff_baton mdb;
1632 mdb.deleted = deleted;
1634 mdb.consider_inheritance = consider_inheritance;
1635 mdb.pool = result_pool;
1637 return svn_hash_diff(from, to, mergeinfo_hash_diff_cb, &mdb, scratch_pool);
1641 svn_mergeinfo_diff2(svn_mergeinfo_t *deleted, svn_mergeinfo_t *added,
1642 svn_mergeinfo_t from, svn_mergeinfo_t to,
1643 svn_boolean_t consider_inheritance,
1644 apr_pool_t *result_pool,
1645 apr_pool_t *scratch_pool)
1647 if (from && to == NULL)
1649 *deleted = svn_mergeinfo_dup(from, result_pool);
1650 *added = svn_hash__make(result_pool);
1652 else if (from == NULL && to)
1654 *deleted = svn_hash__make(result_pool);
1655 *added = svn_mergeinfo_dup(to, result_pool);
1659 *deleted = svn_hash__make(result_pool);
1660 *added = svn_hash__make(result_pool);
1664 SVN_ERR(walk_mergeinfo_hash_for_diff(from, to, *deleted, *added,
1665 consider_inheritance,
1666 result_pool, scratch_pool));
1670 return SVN_NO_ERROR;
1674 svn_mergeinfo__equals(svn_boolean_t *is_equal,
1675 svn_mergeinfo_t info1,
1676 svn_mergeinfo_t info2,
1677 svn_boolean_t consider_inheritance,
1680 apr_hash_index_t *hi;
1684 /* special cases: at least one side has no merge info */
1685 if (info1 == NULL && info2 == NULL)
1688 return SVN_NO_ERROR;
1691 if (info1 == NULL || info2 == NULL)
1692 return SVN_NO_ERROR;
1694 /* trivial case: different number of paths -> unequal */
1695 if (apr_hash_count(info1) != apr_hash_count(info2))
1696 return SVN_NO_ERROR;
1698 /* compare range lists for all paths */
1699 for (hi = apr_hash_first(pool, info1); hi; hi = apr_hash_next(hi))
1702 apr_ssize_t key_length;
1703 svn_rangelist_t *lhs, *rhs;
1705 svn_rangelist_t *deleted, *added;
1707 /* get both path lists */
1708 apr_hash_this(hi, (const void**)&key, &key_length, (void **)&lhs);
1709 rhs = apr_hash_get(info2, key, key_length);
1711 /* missing on one side? */
1713 return SVN_NO_ERROR;
1715 /* quick compare: the range lists will often be a perfect match */
1716 if (lhs->nelts == rhs->nelts)
1718 for (i = 0; i < lhs->nelts; ++i)
1720 svn_merge_range_t *lrange
1721 = APR_ARRAY_IDX(lhs, i, svn_merge_range_t *);
1722 svn_merge_range_t *rrange
1723 = APR_ARRAY_IDX(rhs, i, svn_merge_range_t *);
1725 /* range mismatch? -> needs detailed comparison */
1726 if ( lrange->start != rrange->start
1727 || lrange->end != rrange->end)
1730 /* inheritance mismatch? -> merge info differs */
1731 if ( consider_inheritance
1732 && lrange->inheritable != rrange->inheritable)
1733 return SVN_NO_ERROR;
1736 /* all ranges found to match -> next path */
1737 if (i == lhs->nelts)
1741 /* range lists differ but there are many ways to sort and aggregate
1742 revisions into ranges. Do a full diff on them. */
1743 SVN_ERR(svn_rangelist_diff(&deleted, &added, lhs, rhs,
1744 consider_inheritance, pool));
1745 if (deleted->nelts || added->nelts)
1746 return SVN_NO_ERROR;
1749 /* no mismatch found */
1751 return SVN_NO_ERROR;
1755 svn_mergeinfo_merge2(svn_mergeinfo_t mergeinfo,
1756 svn_mergeinfo_t changes,
1757 apr_pool_t *result_pool,
1758 apr_pool_t *scratch_pool)
1760 apr_hash_index_t *hi;
1761 apr_pool_t *iterpool;
1763 if (!apr_hash_count(changes))
1764 return SVN_NO_ERROR;
1766 iterpool = svn_pool_create(scratch_pool);
1767 for (hi = apr_hash_first(scratch_pool, changes); hi; hi = apr_hash_next(hi))
1771 svn_rangelist_t *to_insert;
1772 svn_rangelist_t *target;
1774 /* get ranges to insert and the target ranges list of that insertion */
1775 apr_hash_this(hi, (const void**)&key, &klen, (void*)&to_insert);
1776 target = apr_hash_get(mergeinfo, key, klen);
1778 /* if range list exists, just expand on it.
1779 * Otherwise, add new hash entry. */
1782 SVN_ERR(svn_rangelist_merge2(target, to_insert, result_pool,
1784 svn_pool_clear(iterpool);
1787 apr_hash_set(mergeinfo, key, klen, to_insert);
1790 svn_pool_destroy(iterpool);
1792 return SVN_NO_ERROR;
1796 svn_mergeinfo_catalog_merge(svn_mergeinfo_catalog_t mergeinfo_cat,
1797 svn_mergeinfo_catalog_t changes_cat,
1798 apr_pool_t *result_pool,
1799 apr_pool_t *scratch_pool)
1803 apr_array_header_t *sorted_cat =
1804 svn_sort__hash(mergeinfo_cat, svn_sort_compare_items_as_paths,
1806 apr_array_header_t *sorted_changes =
1807 svn_sort__hash(changes_cat, svn_sort_compare_items_as_paths,
1810 while (i < sorted_cat->nelts && j < sorted_changes->nelts)
1812 svn_sort__item_t cat_elt, change_elt;
1815 cat_elt = APR_ARRAY_IDX(sorted_cat, i, svn_sort__item_t);
1816 change_elt = APR_ARRAY_IDX(sorted_changes, j, svn_sort__item_t);
1817 res = svn_sort_compare_items_as_paths(&cat_elt, &change_elt);
1819 if (res == 0) /* Both catalogs have mergeinfo for a given path. */
1821 svn_mergeinfo_t mergeinfo = cat_elt.value;
1822 svn_mergeinfo_t changes_mergeinfo = change_elt.value;
1824 SVN_ERR(svn_mergeinfo_merge2(mergeinfo, changes_mergeinfo,
1825 result_pool, scratch_pool));
1826 apr_hash_set(mergeinfo_cat, cat_elt.key, cat_elt.klen, mergeinfo);
1830 else if (res < 0) /* Only MERGEINFO_CAT has mergeinfo for this path. */
1834 else /* Only CHANGES_CAT has mergeinfo for this path. */
1836 apr_hash_set(mergeinfo_cat,
1837 apr_pstrdup(result_pool, change_elt.key),
1839 svn_mergeinfo_dup(change_elt.value, result_pool));
1844 /* Copy back any remaining elements from the CHANGES_CAT catalog. */
1845 for (; j < sorted_changes->nelts; j++)
1847 svn_sort__item_t elt = APR_ARRAY_IDX(sorted_changes, j,
1849 apr_hash_set(mergeinfo_cat,
1850 apr_pstrdup(result_pool, elt.key),
1852 svn_mergeinfo_dup(elt.value, result_pool));
1855 return SVN_NO_ERROR;
1859 svn_mergeinfo_intersect2(svn_mergeinfo_t *mergeinfo,
1860 svn_mergeinfo_t mergeinfo1,
1861 svn_mergeinfo_t mergeinfo2,
1862 svn_boolean_t consider_inheritance,
1863 apr_pool_t *result_pool,
1864 apr_pool_t *scratch_pool)
1866 apr_hash_index_t *hi;
1867 apr_pool_t *iterpool;
1869 *mergeinfo = apr_hash_make(result_pool);
1870 iterpool = svn_pool_create(scratch_pool);
1872 /* ### TODO(reint): Do we care about the case when a path in one
1873 ### mergeinfo hash has inheritable mergeinfo, and in the other
1874 ### has non-inhertiable mergeinfo? It seems like that path
1875 ### itself should really be an intersection, while child paths
1876 ### should not be... */
1877 for (hi = apr_hash_first(scratch_pool, mergeinfo1);
1878 hi; hi = apr_hash_next(hi))
1880 const char *path = svn__apr_hash_index_key(hi);
1881 svn_rangelist_t *rangelist1 = svn__apr_hash_index_val(hi);
1882 svn_rangelist_t *rangelist2;
1884 svn_pool_clear(iterpool);
1885 rangelist2 = svn_hash_gets(mergeinfo2, path);
1888 SVN_ERR(svn_rangelist_intersect(&rangelist2, rangelist1, rangelist2,
1889 consider_inheritance, iterpool));
1890 if (rangelist2->nelts > 0)
1891 svn_hash_sets(*mergeinfo, apr_pstrdup(result_pool, path),
1892 svn_rangelist_dup(rangelist2, result_pool));
1895 svn_pool_destroy(iterpool);
1896 return SVN_NO_ERROR;
1900 svn_mergeinfo_remove2(svn_mergeinfo_t *mergeinfo,
1901 svn_mergeinfo_t eraser,
1902 svn_mergeinfo_t whiteboard,
1903 svn_boolean_t consider_inheritance,
1904 apr_pool_t *result_pool,
1905 apr_pool_t *scratch_pool)
1907 *mergeinfo = apr_hash_make(result_pool);
1908 return walk_mergeinfo_hash_for_diff(whiteboard, eraser, *mergeinfo, NULL,
1909 consider_inheritance, result_pool,
1914 svn_rangelist_to_string(svn_string_t **output,
1915 const svn_rangelist_t *rangelist,
1918 svn_stringbuf_t *buf = svn_stringbuf_create_empty(pool);
1920 if (rangelist->nelts > 0)
1923 svn_merge_range_t *range;
1925 /* Handle the elements that need commas at the end. */
1926 for (i = 0; i < rangelist->nelts - 1; i++)
1928 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
1929 svn_stringbuf_appendcstr(buf, range_to_string(range, pool));
1930 svn_stringbuf_appendcstr(buf, ",");
1933 /* Now handle the last element, which needs no comma. */
1934 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
1935 svn_stringbuf_appendcstr(buf, range_to_string(range, pool));
1938 *output = svn_stringbuf__morph_into_string(buf);
1940 return SVN_NO_ERROR;
1943 /* Converts a mergeinfo INPUT to an unparsed mergeinfo in OUTPUT. If PREFIX
1944 is not NULL then prepend PREFIX to each line in OUTPUT. If INPUT contains
1945 no elements, return the empty string. If INPUT contains any merge source
1946 path keys that are relative then convert these to absolute paths in
1949 static svn_error_t *
1950 mergeinfo_to_stringbuf(svn_stringbuf_t **output,
1951 svn_mergeinfo_t input,
1955 *output = svn_stringbuf_create_empty(pool);
1957 if (apr_hash_count(input) > 0)
1959 apr_array_header_t *sorted =
1960 svn_sort__hash(input, svn_sort_compare_items_as_paths, pool);
1963 for (i = 0; i < sorted->nelts; i++)
1965 svn_sort__item_t elt = APR_ARRAY_IDX(sorted, i, svn_sort__item_t);
1966 svn_string_t *revlist;
1968 SVN_ERR(svn_rangelist_to_string(&revlist, elt.value, pool));
1969 svn_stringbuf_appendcstr(
1971 apr_psprintf(pool, "%s%s%s:%s",
1972 prefix ? prefix : "",
1973 *((const char *) elt.key) == '/' ? "" : "/",
1974 (const char *) elt.key,
1976 if (i < sorted->nelts - 1)
1977 svn_stringbuf_appendcstr(*output, "\n");
1981 return SVN_NO_ERROR;
1985 svn_mergeinfo_to_string(svn_string_t **output, svn_mergeinfo_t input,
1988 svn_stringbuf_t *mergeinfo_buf;
1990 SVN_ERR(mergeinfo_to_stringbuf(&mergeinfo_buf, input, NULL, pool));
1991 *output = svn_stringbuf__morph_into_string(mergeinfo_buf);
1992 return SVN_NO_ERROR;
1996 svn_mergeinfo_sort(svn_mergeinfo_t input, apr_pool_t *pool)
1998 apr_hash_index_t *hi;
2000 for (hi = apr_hash_first(pool, input); hi; hi = apr_hash_next(hi))
2002 apr_array_header_t *rl = svn__apr_hash_index_val(hi);
2004 qsort(rl->elts, rl->nelts, rl->elt_size, svn_sort_compare_ranges);
2006 return SVN_NO_ERROR;
2010 svn_mergeinfo__canonicalize_ranges(svn_mergeinfo_t mergeinfo,
2011 apr_pool_t *scratch_pool)
2013 apr_hash_index_t *hi;
2015 for (hi = apr_hash_first(scratch_pool, mergeinfo); hi; hi = apr_hash_next(hi))
2017 apr_array_header_t *rl = svn__apr_hash_index_val(hi);
2019 SVN_ERR(svn_rangelist__canonicalize(rl, scratch_pool));
2022 return SVN_NO_ERROR;
2025 svn_mergeinfo_catalog_t
2026 svn_mergeinfo_catalog_dup(svn_mergeinfo_catalog_t mergeinfo_catalog,
2029 svn_mergeinfo_t new_mergeinfo_catalog = apr_hash_make(pool);
2030 apr_hash_index_t *hi;
2032 for (hi = apr_hash_first(pool, mergeinfo_catalog);
2034 hi = apr_hash_next(hi))
2036 const char *key = svn__apr_hash_index_key(hi);
2037 svn_mergeinfo_t val = svn__apr_hash_index_val(hi);
2039 svn_hash_sets(new_mergeinfo_catalog, apr_pstrdup(pool, key),
2040 svn_mergeinfo_dup(val, pool));
2043 return new_mergeinfo_catalog;
2047 svn_mergeinfo_dup(svn_mergeinfo_t mergeinfo, apr_pool_t *pool)
2049 svn_mergeinfo_t new_mergeinfo = svn_hash__make(pool);
2050 apr_hash_index_t *hi;
2052 for (hi = apr_hash_first(pool, mergeinfo); hi; hi = apr_hash_next(hi))
2054 const char *path = svn__apr_hash_index_key(hi);
2055 apr_ssize_t pathlen = svn__apr_hash_index_klen(hi);
2056 svn_rangelist_t *rangelist = svn__apr_hash_index_val(hi);
2058 apr_hash_set(new_mergeinfo, apr_pstrmemdup(pool, path, pathlen), pathlen,
2059 svn_rangelist_dup(rangelist, pool));
2062 return new_mergeinfo;
2066 svn_mergeinfo_inheritable2(svn_mergeinfo_t *output,
2067 svn_mergeinfo_t mergeinfo,
2071 svn_boolean_t inheritable,
2072 apr_pool_t *result_pool,
2073 apr_pool_t *scratch_pool)
2075 apr_hash_index_t *hi;
2076 svn_mergeinfo_t inheritable_mergeinfo = apr_hash_make(result_pool);
2078 for (hi = apr_hash_first(scratch_pool, mergeinfo);
2080 hi = apr_hash_next(hi))
2082 const char *key = svn__apr_hash_index_key(hi);
2083 apr_ssize_t keylen = svn__apr_hash_index_klen(hi);
2084 svn_rangelist_t *rangelist = svn__apr_hash_index_val(hi);
2085 svn_rangelist_t *inheritable_rangelist;
2087 if (!path || svn_path_compare_paths(path, key) == 0)
2088 SVN_ERR(svn_rangelist_inheritable2(&inheritable_rangelist, rangelist,
2089 start, end, inheritable,
2090 result_pool, scratch_pool));
2092 inheritable_rangelist = svn_rangelist_dup(rangelist, result_pool);
2094 /* Only add this rangelist if some ranges remain. A rangelist with
2095 a path mapped to an empty rangelist is not syntactically valid */
2096 if (inheritable_rangelist->nelts)
2097 apr_hash_set(inheritable_mergeinfo,
2098 apr_pstrmemdup(result_pool, key, keylen), keylen,
2099 inheritable_rangelist);
2101 *output = inheritable_mergeinfo;
2102 return SVN_NO_ERROR;
2107 svn_rangelist_inheritable2(svn_rangelist_t **inheritable_rangelist,
2108 const svn_rangelist_t *rangelist,
2111 svn_boolean_t inheritable,
2112 apr_pool_t *result_pool,
2113 apr_pool_t *scratch_pool)
2115 *inheritable_rangelist = apr_array_make(result_pool, 1,
2116 sizeof(svn_merge_range_t *));
2117 if (rangelist->nelts)
2119 if (!SVN_IS_VALID_REVNUM(start)
2120 || !SVN_IS_VALID_REVNUM(end)
2124 /* We want all non-inheritable ranges removed. */
2125 for (i = 0; i < rangelist->nelts; i++)
2127 svn_merge_range_t *range = APR_ARRAY_IDX(rangelist, i,
2128 svn_merge_range_t *);
2129 if (range->inheritable == inheritable)
2131 svn_merge_range_t *inheritable_range =
2132 apr_palloc(result_pool, sizeof(*inheritable_range));
2133 inheritable_range->start = range->start;
2134 inheritable_range->end = range->end;
2135 inheritable_range->inheritable = TRUE;
2136 APR_ARRAY_PUSH(*inheritable_rangelist,
2137 svn_merge_range_t *) = range;
2143 /* We want only the non-inheritable ranges bound by START
2145 svn_rangelist_t *ranges_inheritable =
2146 svn_rangelist__initialize(start, end, inheritable, scratch_pool);
2148 if (rangelist->nelts)
2149 SVN_ERR(svn_rangelist_remove(inheritable_rangelist,
2156 return SVN_NO_ERROR;
2160 svn_mergeinfo__remove_empty_rangelists(svn_mergeinfo_t mergeinfo,
2163 apr_hash_index_t *hi;
2164 svn_boolean_t removed_some_ranges = FALSE;
2168 for (hi = apr_hash_first(pool, mergeinfo); hi; hi = apr_hash_next(hi))
2170 const char *path = svn__apr_hash_index_key(hi);
2171 svn_rangelist_t *rangelist = svn__apr_hash_index_val(hi);
2173 if (rangelist->nelts == 0)
2175 svn_hash_sets(mergeinfo, path, NULL);
2176 removed_some_ranges = TRUE;
2180 return removed_some_ranges;
2184 svn_mergeinfo__remove_prefix_from_catalog(svn_mergeinfo_catalog_t *out_catalog,
2185 svn_mergeinfo_catalog_t in_catalog,
2186 const char *prefix_path,
2189 apr_hash_index_t *hi;
2191 SVN_ERR_ASSERT(prefix_path[0] == '/');
2193 *out_catalog = apr_hash_make(pool);
2195 for (hi = apr_hash_first(pool, in_catalog); hi; hi = apr_hash_next(hi))
2197 const char *original_path = svn__apr_hash_index_key(hi);
2198 svn_mergeinfo_t value = svn__apr_hash_index_val(hi);
2199 const char *new_path;
2201 new_path = svn_fspath__skip_ancestor(prefix_path, original_path);
2202 SVN_ERR_ASSERT(new_path);
2204 svn_hash_sets(*out_catalog, new_path, value);
2207 return SVN_NO_ERROR;
2211 svn_mergeinfo__add_prefix_to_catalog(svn_mergeinfo_catalog_t *out_catalog,
2212 svn_mergeinfo_catalog_t in_catalog,
2213 const char *prefix_path,
2214 apr_pool_t *result_pool,
2215 apr_pool_t *scratch_pool)
2217 apr_hash_index_t *hi;
2219 *out_catalog = apr_hash_make(result_pool);
2221 for (hi = apr_hash_first(scratch_pool, in_catalog);
2223 hi = apr_hash_next(hi))
2225 const char *original_path = svn__apr_hash_index_key(hi);
2226 svn_mergeinfo_t value = svn__apr_hash_index_val(hi);
2228 if (original_path[0] == '/')
2231 svn_hash_sets(*out_catalog,
2232 svn_dirent_join(prefix_path, original_path, result_pool),
2236 return SVN_NO_ERROR;
2240 svn_mergeinfo__add_suffix_to_mergeinfo(svn_mergeinfo_t *out_mergeinfo,
2241 svn_mergeinfo_t mergeinfo,
2242 const char *suffix_relpath,
2243 apr_pool_t *result_pool,
2244 apr_pool_t *scratch_pool)
2246 apr_hash_index_t *hi;
2248 SVN_ERR_ASSERT(suffix_relpath && svn_relpath_is_canonical(suffix_relpath));
2250 *out_mergeinfo = apr_hash_make(result_pool);
2252 for (hi = apr_hash_first(scratch_pool, mergeinfo);
2254 hi = apr_hash_next(hi))
2256 const char *fspath = svn__apr_hash_index_key(hi);
2257 svn_rangelist_t *rangelist = svn__apr_hash_index_val(hi);
2259 svn_hash_sets(*out_mergeinfo,
2260 svn_fspath__join(fspath, suffix_relpath, result_pool),
2264 return SVN_NO_ERROR;
2268 svn_rangelist_dup(const svn_rangelist_t *rangelist, apr_pool_t *pool)
2270 svn_rangelist_t *new_rl = apr_array_make(pool, rangelist->nelts,
2271 sizeof(svn_merge_range_t *));
2273 /* allocate target range buffer with a single operation */
2274 svn_merge_range_t *copy = apr_palloc(pool, sizeof(*copy) * rangelist->nelts);
2277 /* fill it iteratively and link it into the range list */
2278 for (i = 0; i < rangelist->nelts; i++)
2281 APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *),
2283 APR_ARRAY_PUSH(new_rl, svn_merge_range_t *) = copy + i;
2290 svn_merge_range_dup(const svn_merge_range_t *range, apr_pool_t *pool)
2292 svn_merge_range_t *new_range = apr_palloc(pool, sizeof(*new_range));
2293 memcpy(new_range, range, sizeof(*new_range));
2298 svn_merge_range_contains_rev(const svn_merge_range_t *range, svn_revnum_t rev)
2300 assert(SVN_IS_VALID_REVNUM(range->start));
2301 assert(SVN_IS_VALID_REVNUM(range->end));
2302 assert(range->start != range->end);
2304 if (range->start < range->end)
2305 return rev > range->start && rev <= range->end;
2307 return rev > range->end && rev <= range->start;
2311 svn_mergeinfo__catalog_to_formatted_string(svn_string_t **output,
2312 svn_mergeinfo_catalog_t catalog,
2313 const char *key_prefix,
2314 const char *val_prefix,
2317 svn_stringbuf_t *output_buf = NULL;
2319 if (catalog && apr_hash_count(catalog))
2322 apr_array_header_t *sorted_catalog =
2323 svn_sort__hash(catalog, svn_sort_compare_items_as_paths, pool);
2325 output_buf = svn_stringbuf_create_empty(pool);
2326 for (i = 0; i < sorted_catalog->nelts; i++)
2328 svn_sort__item_t elt =
2329 APR_ARRAY_IDX(sorted_catalog, i, svn_sort__item_t);
2331 svn_mergeinfo_t mergeinfo;
2332 svn_stringbuf_t *mergeinfo_output_buf;
2335 mergeinfo = elt.value;
2337 svn_stringbuf_appendcstr(output_buf, key_prefix);
2338 svn_stringbuf_appendcstr(output_buf, path1);
2339 svn_stringbuf_appendcstr(output_buf, "\n");
2340 SVN_ERR(mergeinfo_to_stringbuf(&mergeinfo_output_buf, mergeinfo,
2341 val_prefix ? val_prefix : "", pool));
2342 svn_stringbuf_appendstr(output_buf, mergeinfo_output_buf);
2343 svn_stringbuf_appendcstr(output_buf, "\n");
2349 output_buf = svn_stringbuf_create(key_prefix ? key_prefix : "", pool);
2350 svn_stringbuf_appendcstr(output_buf, _("NULL mergeinfo catalog\n"));
2352 else if (apr_hash_count(catalog) == 0)
2354 output_buf = svn_stringbuf_create(key_prefix ? key_prefix : "", pool);
2355 svn_stringbuf_appendcstr(output_buf, _("empty mergeinfo catalog\n"));
2359 /* If we have an output_buf, convert it to an svn_string_t;
2360 otherwise, return a new string containing only a newline
2363 *output = svn_stringbuf__morph_into_string(output_buf);
2365 *output = svn_string_create("\n", pool);
2367 return SVN_NO_ERROR;
2371 svn_mergeinfo__get_range_endpoints(svn_revnum_t *youngest_rev,
2372 svn_revnum_t *oldest_rev,
2373 svn_mergeinfo_t mergeinfo,
2376 *youngest_rev = *oldest_rev = SVN_INVALID_REVNUM;
2379 apr_hash_index_t *hi;
2381 for (hi = apr_hash_first(pool, mergeinfo); hi; hi = apr_hash_next(hi))
2383 svn_rangelist_t *rangelist = svn__apr_hash_index_val(hi);
2385 if (rangelist->nelts)
2387 svn_merge_range_t *range = APR_ARRAY_IDX(rangelist,
2388 rangelist->nelts - 1,
2389 svn_merge_range_t *);
2390 if (!SVN_IS_VALID_REVNUM(*youngest_rev)
2391 || (range->end > *youngest_rev))
2392 *youngest_rev = range->end;
2394 range = APR_ARRAY_IDX(rangelist, 0, svn_merge_range_t *);
2395 if (!SVN_IS_VALID_REVNUM(*oldest_rev)
2396 || (range->start < *oldest_rev))
2397 *oldest_rev = range->start;
2401 return SVN_NO_ERROR;
2405 svn_mergeinfo__filter_catalog_by_ranges(svn_mergeinfo_catalog_t *filtered_cat,
2406 svn_mergeinfo_catalog_t catalog,
2407 svn_revnum_t youngest_rev,
2408 svn_revnum_t oldest_rev,
2409 svn_boolean_t include_range,
2410 apr_pool_t *result_pool,
2411 apr_pool_t *scratch_pool)
2413 apr_hash_index_t *hi;
2415 *filtered_cat = apr_hash_make(result_pool);
2416 for (hi = apr_hash_first(scratch_pool, catalog);
2418 hi = apr_hash_next(hi))
2420 const char *path = svn__apr_hash_index_key(hi);
2421 svn_mergeinfo_t mergeinfo = svn__apr_hash_index_val(hi);
2422 svn_mergeinfo_t filtered_mergeinfo;
2424 SVN_ERR(svn_mergeinfo__filter_mergeinfo_by_ranges(&filtered_mergeinfo,
2431 if (apr_hash_count(filtered_mergeinfo))
2432 svn_hash_sets(*filtered_cat,
2433 apr_pstrdup(result_pool, path), filtered_mergeinfo);
2436 return SVN_NO_ERROR;
2440 svn_mergeinfo__filter_mergeinfo_by_ranges(svn_mergeinfo_t *filtered_mergeinfo,
2441 svn_mergeinfo_t mergeinfo,
2442 svn_revnum_t youngest_rev,
2443 svn_revnum_t oldest_rev,
2444 svn_boolean_t include_range,
2445 apr_pool_t *result_pool,
2446 apr_pool_t *scratch_pool)
2448 SVN_ERR_ASSERT(SVN_IS_VALID_REVNUM(youngest_rev));
2449 SVN_ERR_ASSERT(SVN_IS_VALID_REVNUM(oldest_rev));
2450 SVN_ERR_ASSERT(oldest_rev < youngest_rev);
2452 *filtered_mergeinfo = apr_hash_make(result_pool);
2456 apr_hash_index_t *hi;
2457 svn_rangelist_t *filter_rangelist =
2458 svn_rangelist__initialize(oldest_rev, youngest_rev, TRUE,
2461 for (hi = apr_hash_first(scratch_pool, mergeinfo);
2463 hi = apr_hash_next(hi))
2465 const char *path = svn__apr_hash_index_key(hi);
2466 svn_rangelist_t *rangelist = svn__apr_hash_index_val(hi);
2468 if (rangelist->nelts)
2470 svn_rangelist_t *new_rangelist;
2472 SVN_ERR(rangelist_intersect_or_remove(
2473 &new_rangelist, filter_rangelist, rangelist,
2474 ! include_range, FALSE, result_pool));
2476 if (new_rangelist->nelts)
2477 svn_hash_sets(*filtered_mergeinfo,
2478 apr_pstrdup(result_pool, path), new_rangelist);
2482 return SVN_NO_ERROR;
2486 svn_mergeinfo__adjust_mergeinfo_rangelists(svn_mergeinfo_t *adjusted_mergeinfo,
2487 svn_mergeinfo_t mergeinfo,
2488 svn_revnum_t offset,
2489 apr_pool_t *result_pool,
2490 apr_pool_t *scratch_pool)
2492 apr_hash_index_t *hi;
2493 *adjusted_mergeinfo = apr_hash_make(result_pool);
2497 for (hi = apr_hash_first(scratch_pool, mergeinfo);
2499 hi = apr_hash_next(hi))
2502 const char *path = svn__apr_hash_index_key(hi);
2503 svn_rangelist_t *rangelist = svn__apr_hash_index_val(hi);
2504 svn_rangelist_t *adjusted_rangelist =
2505 apr_array_make(result_pool, rangelist->nelts,
2506 sizeof(svn_merge_range_t *));
2508 for (i = 0; i < rangelist->nelts; i++)
2510 svn_merge_range_t *range =
2511 APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
2513 if (range->start + offset > 0 && range->end + offset > 0)
2515 if (range->start + offset < 0)
2518 range->start = range->start + offset;
2520 if (range->end + offset < 0)
2523 range->end = range->end + offset;
2524 APR_ARRAY_PUSH(adjusted_rangelist, svn_merge_range_t *) =
2529 if (adjusted_rangelist->nelts)
2530 svn_hash_sets(*adjusted_mergeinfo, apr_pstrdup(result_pool, path),
2531 adjusted_rangelist);
2534 return SVN_NO_ERROR;
2538 svn_mergeinfo__is_noninheritable(svn_mergeinfo_t mergeinfo,
2539 apr_pool_t *scratch_pool)
2543 apr_hash_index_t *hi;
2545 for (hi = apr_hash_first(scratch_pool, mergeinfo);
2547 hi = apr_hash_next(hi))
2549 svn_rangelist_t *rangelist = svn__apr_hash_index_val(hi);
2552 for (i = 0; i < rangelist->nelts; i++)
2554 svn_merge_range_t *range = APR_ARRAY_IDX(rangelist, i,
2555 svn_merge_range_t *);
2556 if (!range->inheritable)
2565 svn_rangelist__initialize(svn_revnum_t start,
2567 svn_boolean_t inheritable,
2568 apr_pool_t *result_pool)
2570 svn_rangelist_t *rangelist =
2571 apr_array_make(result_pool, 1, sizeof(svn_merge_range_t *));
2572 svn_merge_range_t *range = apr_pcalloc(result_pool, sizeof(*range));
2574 range->start = start;
2576 range->inheritable = inheritable;
2577 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = range;
2582 svn_mergeinfo__mergeinfo_from_segments(svn_mergeinfo_t *mergeinfo_p,
2583 const apr_array_header_t *segments,
2586 svn_mergeinfo_t mergeinfo = apr_hash_make(pool);
2589 /* Translate location segments into merge sources and ranges. */
2590 for (i = 0; i < segments->nelts; i++)
2592 svn_location_segment_t *segment =
2593 APR_ARRAY_IDX(segments, i, svn_location_segment_t *);
2594 svn_rangelist_t *path_ranges;
2595 svn_merge_range_t *range;
2596 const char *source_path;
2598 /* No path segment? Skip it. */
2599 if (! segment->path)
2602 /* Prepend a leading slash to our path. */
2603 source_path = apr_pstrcat(pool, "/", segment->path, (char *)NULL);
2605 /* See if we already stored ranges for this path. If not, make
2607 path_ranges = svn_hash_gets(mergeinfo, source_path);
2609 path_ranges = apr_array_make(pool, 1, sizeof(range));
2611 /* A svn_location_segment_t may have legitimately describe only
2612 revision 0, but there is no corresponding representation for
2613 this in a svn_merge_range_t. */
2614 if (segment->range_start == 0 && segment->range_end == 0)
2617 /* Build a merge range, push it onto the list of ranges, and for
2618 good measure, (re)store it in the hash. */
2619 range = apr_pcalloc(pool, sizeof(*range));
2620 range->start = MAX(segment->range_start - 1, 0);
2621 range->end = segment->range_end;
2622 range->inheritable = TRUE;
2623 APR_ARRAY_PUSH(path_ranges, svn_merge_range_t *) = range;
2624 svn_hash_sets(mergeinfo, source_path, path_ranges);
2627 *mergeinfo_p = mergeinfo;
2628 return SVN_NO_ERROR;
2632 svn_rangelist__merge_many(svn_rangelist_t *merged_rangelist,
2633 svn_mergeinfo_t merge_history,
2634 apr_pool_t *result_pool,
2635 apr_pool_t *scratch_pool)
2637 if (apr_hash_count(merge_history))
2639 apr_pool_t *iterpool = svn_pool_create(scratch_pool);
2640 apr_hash_index_t *hi;
2642 for (hi = apr_hash_first(scratch_pool, merge_history);
2644 hi = apr_hash_next(hi))
2646 svn_rangelist_t *subtree_rangelist = svn__apr_hash_index_val(hi);
2648 svn_pool_clear(iterpool);
2649 SVN_ERR(svn_rangelist_merge2(merged_rangelist, subtree_rangelist,
2650 result_pool, iterpool));
2652 svn_pool_destroy(iterpool);
2654 return SVN_NO_ERROR;
2659 svn_inheritance_to_word(svn_mergeinfo_inheritance_t inherit)
2663 case svn_mergeinfo_inherited:
2665 case svn_mergeinfo_nearest_ancestor:
2666 return "nearest-ancestor";
2672 svn_mergeinfo_inheritance_t
2673 svn_inheritance_from_word(const char *word)
2675 if (strcmp(word, "inherited") == 0)
2676 return svn_mergeinfo_inherited;
2677 if (strcmp(word, "nearest-ancestor") == 0)
2678 return svn_mergeinfo_nearest_ancestor;
2679 return svn_mergeinfo_explicit;