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_sorts_private.h"
38 #include "private/svn_string_private.h"
39 #include "private/svn_subr_private.h"
40 #include "svn_private_config.h"
42 #include "private/svn_dep_compat.h"
44 /* Attempt to combine two ranges, IN1 and IN2. If they are adjacent or
45 overlapping, and their inheritability allows them to be combined, put
46 the result in OUTPUT and return TRUE, otherwise return FALSE.
48 CONSIDER_INHERITANCE determines how to account for the inheritability
49 of IN1 and IN2 when trying to combine ranges. If ranges with different
50 inheritability are combined (CONSIDER_INHERITANCE must be FALSE for this
51 to happen) the result is inheritable. If both ranges are inheritable the
52 result is inheritable. And only if both ranges are non-inheritable
53 the result is non-inheritable.
55 Range overlapping detection algorithm from
56 http://c2.com/cgi-bin/wiki/fullSearch?TestIfDateRangesOverlap
59 combine_ranges(svn_merge_range_t *output,
60 const svn_merge_range_t *in1,
61 const svn_merge_range_t *in2,
62 svn_boolean_t consider_inheritance)
64 if (in1->start <= in2->end && in2->start <= in1->end)
66 if (!consider_inheritance
67 || (consider_inheritance
68 && (in1->inheritable == in2->inheritable)))
70 output->start = MIN(in1->start, in2->start);
71 output->end = MAX(in1->end, in2->end);
72 output->inheritable = (in1->inheritable || in2->inheritable);
79 /* pathname -> PATHNAME */
81 parse_pathname(const char **input,
83 const char **pathname,
86 const char *curr = *input;
87 const char *last_colon = NULL;
89 /* A pathname may contain colons, so find the last colon before END
90 or newline. We'll consider this the divider between the pathname
91 and the revisionlist. */
92 while (curr < end && *curr != '\n')
100 return svn_error_create(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
101 _("Pathname not terminated by ':'"));
103 /* Tolerate relative repository paths, but convert them to absolute.
104 ### Efficiency? 1 string duplication here, 2 in canonicalize. */
105 *pathname = svn_fspath__canonicalize(apr_pstrndup(pool, *input,
106 last_colon - *input),
114 /* Return TRUE iff (svn_merge_range_t *) RANGE describes a valid, forward
117 * Note: The smallest valid value of RANGE->start is 0 because it is an
118 * exclusive endpoint, being one less than the revision number of the first
119 * change described by the range, and the oldest possible change is "r1" as
120 * there cannot be a change "r0". */
121 #define IS_VALID_FORWARD_RANGE(range) \
122 (SVN_IS_VALID_REVNUM((range)->start) && ((range)->start < (range)->end))
124 /* Ways in which two svn_merge_range_t can intersect or adjoin, if at all. */
125 typedef enum intersection_type_t
127 /* Ranges don't intersect and don't adjoin. */
128 svn__no_intersection,
130 /* Ranges are equal. */
131 svn__equal_intersection,
133 /* Ranges adjoin but don't overlap. */
134 svn__adjoining_intersection,
136 /* Ranges overlap but neither is a subset of the other. */
137 svn__overlapping_intersection,
139 /* One range is a proper subset of the other. */
140 svn__proper_subset_intersection
141 } intersection_type_t;
143 /* Given ranges R1 and R2, both of which must be forward merge ranges,
144 set *INTERSECTION_TYPE to describe how the ranges intersect, if they
145 do at all. The inheritance type of the ranges is not considered. */
147 get_type_of_intersection(const svn_merge_range_t *r1,
148 const svn_merge_range_t *r2,
149 intersection_type_t *intersection_type)
153 SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(r1));
154 SVN_ERR_ASSERT(IS_VALID_FORWARD_RANGE(r2));
156 if (!(r1->start <= r2->end && r2->start <= r1->end))
157 *intersection_type = svn__no_intersection;
158 else if (r1->start == r2->start && r1->end == r2->end)
159 *intersection_type = svn__equal_intersection;
160 else if (r1->end == r2->start || r2->end == r1->start)
161 *intersection_type = svn__adjoining_intersection;
162 else if (r1->start <= r2->start && r1->end >= r2->end)
163 *intersection_type = svn__proper_subset_intersection;
164 else if (r2->start <= r1->start && r2->end >= r1->end)
165 *intersection_type = svn__proper_subset_intersection;
167 *intersection_type = svn__overlapping_intersection;
172 /* Modify or extend RANGELIST (a list of merge ranges) to incorporate
173 NEW_RANGE. RANGELIST is a "rangelist" as defined in svn_mergeinfo.h.
177 Determine the minimal set of non-overlapping merge ranges required to
178 represent the combination of RANGELIST and NEW_RANGE. The result depends
179 on whether and how NEW_RANGE overlaps any merge range[*] in RANGELIST,
180 and also on any differences in the inheritability of each range,
181 according to the rules described below. Modify RANGELIST to represent
182 this result, by adjusting the last range in it and/or appending one or
185 ([*] Due to the simplifying assumption below, only the last range in
186 RANGELIST is considered.)
190 If RANGELIST is not empty assume NEW_RANGE does not intersect with any
191 range before the last one in RANGELIST.
193 If RANGELIST is empty or NEW_RANGE does not intersect with the lastrange
194 in RANGELIST, then append a copy of NEW_RANGE, allocated in RESULT_POOL,
197 If NEW_RANGE intersects with the last range in RANGELIST then combine
198 these two ranges as described below:
200 If the intersecting ranges have the same inheritability then simply
201 combine the ranges in place. Otherwise, if the ranges intersect but
202 differ in inheritability, then merge the ranges as dictated by
203 CONSIDER_INHERITANCE:
205 If CONSIDER_INHERITANCE is false then intersecting ranges are combined
206 into a single range. The inheritability of the resulting range is
207 non-inheritable *only* if both ranges are non-inheritable, otherwise the
208 combined range is inheritable, e.g.:
210 Last range in NEW_RANGE RESULTING RANGES
212 ------------- --------- ----------------
217 If CONSIDER_INHERITANCE is true, then only the intersection between the
218 two ranges is combined, with the inheritability of the resulting range
219 non-inheritable only if both ranges were non-inheritable. The
220 non-intersecting portions are added as separate ranges allocated in
223 Last range in NEW_RANGE RESULTING RANGES
225 ------------- --------- ----------------
226 4-10* 6 4-5*, 6, 7-10*
227 4-10* 6-12 4-5*, 6-12
229 Note that the standard rules for rangelists still apply and overlapping
230 ranges are not allowed. So if the above would result in overlapping
231 ranges of the same inheritance, the overlapping ranges are merged into a
234 Last range in NEW_RANGE RESULTING RANGES
236 ------------- --------- ----------------
237 4-10 6* 4-10 (Not 4-5, 6, 7-10)
239 When replacing the last range in RANGELIST, either allocate a new range in
240 RESULT_POOL or modify the existing range in place. Any new ranges added
241 to RANGELIST are allocated in RESULT_POOL.
244 combine_with_lastrange(const svn_merge_range_t *new_range,
245 svn_rangelist_t *rangelist,
246 svn_boolean_t consider_inheritance,
247 apr_pool_t *result_pool)
249 svn_merge_range_t *lastrange;
250 svn_merge_range_t combined_range;
252 /* We don't accept a NULL RANGELIST. */
253 SVN_ERR_ASSERT(rangelist);
255 if (rangelist->nelts > 0)
256 lastrange = APR_ARRAY_IDX(rangelist, rangelist->nelts - 1, svn_merge_range_t *);
262 /* No *LASTRANGE so push NEW_RANGE onto RANGELIST and we are done. */
263 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
264 svn_merge_range_dup(new_range, result_pool);
266 else if (!consider_inheritance)
268 /* We are not considering inheritance so we can merge intersecting
269 ranges of different inheritability. Of course if the ranges
270 don't intersect at all we simply push NEW_RANGE onto RANGELIST. */
271 if (combine_ranges(&combined_range, lastrange, new_range, FALSE))
273 *lastrange = combined_range;
277 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
278 svn_merge_range_dup(new_range, result_pool);
281 else /* Considering inheritance */
283 if (combine_ranges(&combined_range, lastrange, new_range, TRUE))
285 /* Even when considering inheritance two intersection ranges
286 of the same inheritability can simply be combined. */
287 *lastrange = combined_range;
291 /* If we are here then the ranges either don't intersect or do
292 intersect but have differing inheritability. Check for the
293 first case as that is easy to handle. */
294 intersection_type_t intersection_type;
295 svn_boolean_t sorted = FALSE;
297 SVN_ERR(get_type_of_intersection(new_range, lastrange,
298 &intersection_type));
300 switch (intersection_type)
302 case svn__no_intersection:
303 /* NEW_RANGE and *LASTRANGE *really* don't intersect so
304 just push NEW_RANGE onto RANGELIST. */
305 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
306 svn_merge_range_dup(new_range, result_pool);
307 sorted = (svn_sort_compare_ranges(&lastrange,
311 case svn__equal_intersection:
312 /* They range are equal so all we do is force the
313 inheritability of lastrange to true. */
314 lastrange->inheritable = TRUE;
318 case svn__adjoining_intersection:
319 /* They adjoin but don't overlap so just push NEW_RANGE
321 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) =
322 svn_merge_range_dup(new_range, result_pool);
323 sorted = (svn_sort_compare_ranges(&lastrange,
327 case svn__overlapping_intersection:
328 /* They ranges overlap but neither is a proper subset of
329 the other. We'll end up pusing two new ranges onto
330 RANGELIST, the intersecting part and the part unique to
333 svn_merge_range_t *r1 = svn_merge_range_dup(lastrange,
335 svn_merge_range_t *r2 = svn_merge_range_dup(new_range,
338 /* Pop off *LASTRANGE to make our manipulations
340 apr_array_pop(rangelist);
342 /* Ensure R1 is the older range. */
343 if (r2->start < r1->start)
345 /* Swap R1 and R2. */
350 /* Absorb the intersecting ranges into the
351 inheritable range. */
357 /* Push everything back onto RANGELIST. */
358 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r1;
359 sorted = (svn_sort_compare_ranges(&lastrange,
361 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r2;
363 sorted = (svn_sort_compare_ranges(&r1, &r2) < 0);
367 default: /* svn__proper_subset_intersection */
369 /* One range is a proper subset of the other. */
370 svn_merge_range_t *r1 = svn_merge_range_dup(lastrange,
372 svn_merge_range_t *r2 = svn_merge_range_dup(new_range,
374 svn_merge_range_t *r3 = NULL;
376 /* Pop off *LASTRANGE to make our manipulations
378 apr_array_pop(rangelist);
380 /* Ensure R1 is the superset. */
381 if (r2->start < r1->start || r2->end > r1->end)
383 /* Swap R1 and R2. */
390 /* The simple case: The superset is inheritable, so
391 just combine r1 and r2. */
392 r1->start = MIN(r1->start, r2->start);
393 r1->end = MAX(r1->end, r2->end);
396 else if (r1->start == r2->start)
398 svn_revnum_t tmp_revnum;
400 /* *LASTRANGE and NEW_RANGE share an end point. */
401 tmp_revnum = r1->end;
403 r2->inheritable = r1->inheritable;
404 r1->inheritable = TRUE;
406 r2->end = tmp_revnum;
408 else if (r1->end == r2->end)
410 /* *LASTRANGE and NEW_RANGE share an end point. */
412 r2->inheritable = TRUE;
416 /* NEW_RANGE and *LASTRANGE share neither start
418 r3 = apr_pcalloc(result_pool, sizeof(*r3));
421 r3->inheritable = r1->inheritable;
422 r2->inheritable = TRUE;
426 /* Push everything back onto RANGELIST. */
427 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r1;
428 sorted = (svn_sort_compare_ranges(&lastrange, &r1) < 0);
431 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r2;
433 sorted = (svn_sort_compare_ranges(&r1, &r2) < 0);
437 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = r3;
441 sorted = (svn_sort_compare_ranges(&r2,
444 sorted = (svn_sort_compare_ranges(&r1,
452 /* Some of the above cases might have put *RANGELIST out of
455 svn_sort__array(rangelist, svn_sort_compare_ranges);
462 /* Convert a single svn_merge_range_t *RANGE back into a string. */
464 range_to_string(const svn_merge_range_t *range,
468 = range->inheritable ? "" : SVN_MERGEINFO_NONINHERITABLE_STR;
470 if (range->start == range->end - 1)
471 return apr_psprintf(pool, "%ld%s", range->end, mark);
472 else if (range->start - 1 == range->end)
473 return apr_psprintf(pool, "-%ld%s", range->start, mark);
474 else if (range->start < range->end)
475 return apr_psprintf(pool, "%ld-%ld%s", range->start + 1, range->end, mark);
477 return apr_psprintf(pool, "%ld-%ld%s", range->start, range->end + 1, mark);
480 /* Helper for svn_mergeinfo_parse()
481 Append revision ranges onto the array RANGELIST to represent the range
482 descriptions found in the string *INPUT. Read only as far as a newline
483 or the position END, whichever comes first. Set *INPUT to the position
484 after the last character of INPUT that was used.
486 revisionlist -> (revisionelement)(COMMA revisionelement)*
487 revisionrange -> REVISION "-" REVISION("*")
488 revisionelement -> revisionrange | REVISION("*")
491 parse_rangelist(const char **input, const char *end,
492 svn_rangelist_t *rangelist,
495 const char *curr = *input;
497 /* Eat any leading horizontal white-space before the rangelist. */
498 while (curr < end && *curr != '\n' && isspace(*curr))
501 if (*curr == '\n' || curr == end)
503 /* Empty range list. */
508 while (curr < end && *curr != '\n')
510 /* Parse individual revisions or revision ranges. */
511 svn_merge_range_t *mrange = apr_pcalloc(pool, sizeof(*mrange));
512 svn_revnum_t firstrev;
514 SVN_ERR(svn_revnum_parse(&firstrev, curr, &curr));
515 if (*curr != '-' && *curr != '\n' && *curr != ',' && *curr != '*'
517 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
518 _("Invalid character '%c' found in revision "
520 mrange->start = firstrev - 1;
521 mrange->end = firstrev;
522 mrange->inheritable = TRUE;
525 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
526 _("Invalid revision number '0' found in "
531 svn_revnum_t secondrev;
534 SVN_ERR(svn_revnum_parse(&secondrev, curr, &curr));
535 if (firstrev > secondrev)
536 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
537 _("Unable to parse reversed revision "
539 firstrev, secondrev);
540 else if (firstrev == secondrev)
541 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
542 _("Unable to parse revision range "
543 "'%ld-%ld' with same start and end "
544 "revisions"), firstrev, secondrev);
545 mrange->end = secondrev;
548 if (*curr == '\n' || curr == end)
550 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = mrange;
554 else if (*curr == ',')
556 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = mrange;
559 else if (*curr == '*')
561 mrange->inheritable = FALSE;
563 if (*curr == ',' || *curr == '\n' || curr == end)
565 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = mrange;
578 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
579 _("Invalid character '%c' found in "
580 "range list"), *curr);
585 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
586 _("Invalid character '%c' found in "
587 "range list"), *curr);
592 return svn_error_create(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
593 _("Range list parsing ended before hitting "
600 svn_rangelist__parse(svn_rangelist_t **rangelist,
602 apr_pool_t *result_pool)
606 *rangelist = apr_array_make(result_pool, 1, sizeof(svn_merge_range_t *));
607 SVN_ERR(parse_rangelist(&s, s + strlen(s), *rangelist, result_pool));
611 /* Return TRUE, if all ranges in RANGELIST are in ascending order and do
612 * not overlap and are not adjacent.
614 * ### Can yield false negatives: ranges of differing inheritance are
615 * allowed to be adjacent.
617 * If this returns FALSE, you probaly want to qsort() the
618 * ranges and then call svn_rangelist__combine_adjacent_ranges().
621 is_rangelist_normalized(svn_rangelist_t *rangelist)
624 svn_merge_range_t **ranges = (svn_merge_range_t **)rangelist->elts;
626 for (i = 0; i < rangelist->nelts-1; ++i)
627 if (ranges[i]->end >= ranges[i+1]->start)
634 svn_rangelist__canonicalize(svn_rangelist_t *rangelist,
635 apr_pool_t *scratch_pool)
637 if (! is_rangelist_normalized(rangelist))
639 svn_sort__array(rangelist, svn_sort_compare_ranges);
641 SVN_ERR(svn_rangelist__combine_adjacent_ranges(rangelist, scratch_pool));
648 svn_rangelist__combine_adjacent_ranges(svn_rangelist_t *rangelist,
649 apr_pool_t *scratch_pool)
652 svn_merge_range_t *range, *lastrange;
654 lastrange = APR_ARRAY_IDX(rangelist, 0, svn_merge_range_t *);
656 for (i = 1; i < rangelist->nelts; i++)
658 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
659 if (lastrange->start <= range->end
660 && range->start <= lastrange->end)
662 /* The ranges are adjacent or intersect. */
664 /* svn_mergeinfo_parse promises to combine overlapping
665 ranges as long as their inheritability is the same. */
666 if (range->start < lastrange->end
667 && range->inheritable != lastrange->inheritable)
669 return svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, NULL,
670 _("Unable to parse overlapping "
671 "revision ranges '%s' and '%s' "
672 "with different inheritance "
674 range_to_string(lastrange,
676 range_to_string(range,
680 /* Combine overlapping or adjacent ranges with the
681 same inheritability. */
682 if (lastrange->inheritable == range->inheritable)
684 lastrange->end = MAX(range->end, lastrange->end);
685 svn_sort__array_delete(rangelist, i, 1);
689 lastrange = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
695 /* revisionline -> PATHNAME COLON revisionlist
697 * Parse one line of mergeinfo starting at INPUT, not reading beyond END,
698 * into HASH. Allocate the new entry in HASH deeply from HASH's pool.
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 mergeinfo starting at INPUT, not reading beyond END, into HASH.
759 * Allocate all the new entries in HASH deeply from HASH's pool.
762 parse_top(const char **input, const char *end, svn_mergeinfo_t hash,
763 apr_pool_t *scratch_pool)
765 apr_pool_t *iterpool = svn_pool_create(scratch_pool);
769 svn_pool_clear(iterpool);
770 SVN_ERR(parse_revision_line(input, end, hash, iterpool));
772 svn_pool_destroy(iterpool);
778 svn_mergeinfo_parse(svn_mergeinfo_t *mergeinfo,
784 *mergeinfo = svn_hash__make(pool);
785 err = parse_top(&input, input + strlen(input), *mergeinfo, pool);
787 /* Always return SVN_ERR_MERGEINFO_PARSE_ERROR as the topmost error. */
788 if (err && err->apr_err != SVN_ERR_MERGEINFO_PARSE_ERROR)
789 err = svn_error_createf(SVN_ERR_MERGEINFO_PARSE_ERROR, err,
790 _("Could not parse mergeinfo string '%s'"),
795 /* Cleanup after svn_rangelist_merge2 when it modifies the ending range of
796 a single rangelist element in-place.
798 If *RANGE_INDEX is not a valid element in RANGELIST do nothing. Otherwise
799 ensure that RANGELIST[*RANGE_INDEX]->END does not adjoin or overlap any
800 subsequent ranges in RANGELIST.
802 If overlap is found, then remove, modify, and/or add elements to RANGELIST
803 as per the invariants for rangelists documented in svn_mergeinfo.h. If
804 RANGELIST[*RANGE_INDEX]->END adjoins a subsequent element then combine the
805 elements if their inheritability permits -- The inheritance of intersecting
806 and adjoining ranges is handled as per svn_mergeinfo_merge2. Upon return
807 set *RANGE_INDEX to the index of the youngest element modified, added, or
808 adjoined to RANGELIST[*RANGE_INDEX].
810 Note: Adjoining rangelist elements are those where the end rev of the older
811 element is equal to the start rev of the younger element.
813 Any new elements inserted into RANGELIST are allocated in RESULT_POOL.*/
815 adjust_remaining_ranges(svn_rangelist_t *rangelist,
817 apr_pool_t *result_pool)
821 int elements_to_delete = 0;
822 svn_merge_range_t *modified_range;
824 if (*range_index >= rangelist->nelts)
827 starting_index = *range_index + 1;
828 modified_range = APR_ARRAY_IDX(rangelist, *range_index, svn_merge_range_t *);
830 for (i = *range_index + 1; i < rangelist->nelts; i++)
832 svn_merge_range_t *next_range = APR_ARRAY_IDX(rangelist, i,
833 svn_merge_range_t *);
835 /* If MODIFIED_RANGE doesn't adjoin or overlap the next range in
836 RANGELIST then we are finished. */
837 if (modified_range->end < next_range->start)
840 /* Does MODIFIED_RANGE adjoin NEXT_RANGE? */
841 if (modified_range->end == next_range->start)
843 if (modified_range->inheritable == next_range->inheritable)
845 /* Combine adjoining ranges with the same inheritability. */
846 modified_range->end = next_range->end;
847 elements_to_delete++;
851 /* Cannot join because inheritance differs. */
857 /* Alright, we know MODIFIED_RANGE overlaps NEXT_RANGE, but how? */
858 if (modified_range->end > next_range->end)
860 /* NEXT_RANGE is a proper subset of MODIFIED_RANGE and the two
861 don't share the same end range. */
862 if (modified_range->inheritable
863 || (modified_range->inheritable == next_range->inheritable))
865 /* MODIFIED_RANGE absorbs NEXT_RANGE. */
866 elements_to_delete++;
870 /* NEXT_RANGE is a proper subset MODIFIED_RANGE but
871 MODIFIED_RANGE is non-inheritable and NEXT_RANGE is
872 inheritable. This means MODIFIED_RANGE is truncated,
873 NEXT_RANGE remains, and the portion of MODIFIED_RANGE
874 younger than NEXT_RANGE is added as a separate range:
875 ______________________________________________
879 |______________________________________________|
886 _______________________________________________
888 M MODIFIED_RANGE O NEXT_RANGE P NEW_RANGE N
889 | (!inheritable) | (inheritable)| (!inheritable)|
890 |________________|______________|_______________|
892 svn_merge_range_t *new_modified_range =
893 apr_palloc(result_pool, sizeof(*new_modified_range));
894 new_modified_range->start = next_range->end;
895 new_modified_range->end = modified_range->end;
896 new_modified_range->inheritable = FALSE;
897 modified_range->end = next_range->start;
899 svn_sort__array_insert(rangelist, &new_modified_range,
901 /* Recurse with the new range. */
902 adjust_remaining_ranges(rangelist, range_index, result_pool);
906 else if (modified_range->end == next_range->end)
908 /* NEXT_RANGE is a proper subset MODIFIED_RANGE and share
909 the same end range. */
910 if (modified_range->inheritable
911 || (modified_range->inheritable == next_range->inheritable))
913 /* MODIFIED_RANGE absorbs NEXT_RANGE. */
914 elements_to_delete++;
918 /* The intersection between MODIFIED_RANGE and NEXT_RANGE is
919 absorbed by the latter. */
920 modified_range->end = next_range->start;
927 /* NEXT_RANGE and MODIFIED_RANGE intersect but NEXT_RANGE is not
928 a proper subset of MODIFIED_RANGE, nor do the two share the
929 same end revision, i.e. they overlap. */
930 if (modified_range->inheritable == next_range->inheritable)
932 /* Combine overlapping ranges with the same inheritability. */
933 modified_range->end = next_range->end;
934 elements_to_delete++;
936 else if (modified_range->inheritable)
938 /* MODIFIED_RANGE absorbs the portion of NEXT_RANGE it overlaps
939 and NEXT_RANGE is truncated. */
940 next_range->start = modified_range->end;
945 /* NEXT_RANGE absorbs the portion of MODIFIED_RANGE it overlaps
946 and MODIFIED_RANGE is truncated. */
947 modified_range->end = next_range->start;
954 if (elements_to_delete)
955 svn_sort__array_delete(rangelist, starting_index, elements_to_delete);
959 svn_rangelist_merge2(svn_rangelist_t *rangelist,
960 const svn_rangelist_t *changes,
961 apr_pool_t *result_pool,
962 apr_pool_t *scratch_pool)
967 /* We may modify CHANGES, so make a copy in SCRATCH_POOL. */
968 changes = svn_rangelist_dup(changes, scratch_pool);
970 while (i < rangelist->nelts && j < changes->nelts)
972 svn_merge_range_t *range =
973 APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
974 svn_merge_range_t *change =
975 APR_ARRAY_IDX(changes, j, svn_merge_range_t *);
976 int res = svn_sort_compare_ranges(&range, &change);
980 /* Only when merging two non-inheritable ranges is the result also
981 non-inheritable. In all other cases ensure an inheritable
983 if (range->inheritable || change->inheritable)
984 range->inheritable = TRUE;
988 else if (res < 0) /* CHANGE is younger than RANGE */
990 if (range->end < change->start)
992 /* RANGE is older than CHANGE and the two do not
996 else if (range->end == change->start)
998 /* RANGE and CHANGE adjoin */
999 if (range->inheritable == change->inheritable)
1001 /* RANGE and CHANGE have the same inheritability so
1002 RANGE expands to absord CHANGE. */
1003 range->end = change->end;
1004 adjust_remaining_ranges(rangelist, &i, result_pool);
1009 /* RANGE and CHANGE adjoin, but have different
1010 inheritability. Since RANGE is older, just
1011 move on to the next RANGE. */
1017 /* RANGE and CHANGE overlap, but how? */
1018 if ((range->inheritable == change->inheritable)
1019 || range->inheritable)
1021 /* If CHANGE is a proper subset of RANGE, it absorbs RANGE
1022 with no adjustment otherwise only the intersection is
1023 absorbed and CHANGE is truncated. */
1024 if (range->end >= change->end)
1027 change->start = range->end;
1031 /* RANGE is non-inheritable and CHANGE is inheritable. */
1032 if (range->start < change->start)
1034 /* CHANGE absorbs intersection with RANGE and RANGE
1036 svn_merge_range_t *range_copy =
1037 svn_merge_range_dup(range, result_pool);
1038 range_copy->end = change->start;
1039 range->start = change->start;
1040 svn_sort__array_insert(rangelist, &range_copy, i++);
1044 /* CHANGE and RANGE share the same start rev, but
1045 RANGE is considered older because its end rev
1047 range->inheritable = TRUE;
1048 change->start = range->end;
1053 else /* res > 0, CHANGE is older than RANGE */
1055 if (change->end < range->start)
1057 /* CHANGE is older than RANGE and the two do not
1058 adjoin or overlap, so insert a copy of CHANGE
1060 svn_merge_range_t *change_copy =
1061 svn_merge_range_dup(change, result_pool);
1062 svn_sort__array_insert(rangelist, &change_copy, i++);
1065 else if (change->end == range->start)
1067 /* RANGE and CHANGE adjoin */
1068 if (range->inheritable == change->inheritable)
1070 /* RANGE and CHANGE have the same inheritability so we
1071 can simply combine the two in place. */
1072 range->start = change->start;
1077 /* RANGE and CHANGE have different inheritability so insert
1078 a copy of CHANGE into RANGELIST. */
1079 svn_merge_range_t *change_copy =
1080 svn_merge_range_dup(change, result_pool);
1081 svn_sort__array_insert(rangelist, &change_copy, i);
1087 /* RANGE and CHANGE overlap. */
1088 if (range->inheritable == change->inheritable)
1090 /* RANGE and CHANGE have the same inheritability so we
1091 can simply combine the two in place... */
1092 range->start = change->start;
1093 if (range->end < change->end)
1095 /* ...but if RANGE is expanded ensure that we don't
1096 violate any rangelist invariants. */
1097 range->end = change->end;
1098 adjust_remaining_ranges(rangelist, &i, result_pool);
1102 else if (range->inheritable)
1104 if (change->start < range->start)
1106 /* RANGE is inheritable so absorbs any part of CHANGE
1107 it overlaps. CHANGE is truncated and the remainder
1108 inserted into RANGELIST. */
1109 svn_merge_range_t *change_copy =
1110 svn_merge_range_dup(change, result_pool);
1111 change_copy->end = range->start;
1112 change->start = range->start;
1113 svn_sort__array_insert(rangelist, &change_copy, i++);
1117 /* CHANGE and RANGE share the same start rev, but
1118 CHANGE is considered older because CHANGE->END is
1119 older than RANGE->END. */
1125 /* RANGE is non-inheritable and CHANGE is inheritable. */
1126 if (change->start < range->start)
1128 if (change->end == range->end)
1130 /* RANGE is a proper subset of CHANGE and share the
1131 same end revision, so set RANGE equal to CHANGE. */
1132 range->start = change->start;
1133 range->inheritable = TRUE;
1136 else if (change->end > range->end)
1138 /* RANGE is a proper subset of CHANGE and CHANGE has
1139 a younger end revision, so set RANGE equal to its
1140 intersection with CHANGE and truncate CHANGE. */
1141 range->start = change->start;
1142 range->inheritable = TRUE;
1143 change->start = range->end;
1147 /* CHANGE and RANGE overlap. Set RANGE equal to its
1148 intersection with CHANGE and take the remainder
1149 of RANGE and insert it into RANGELIST. */
1150 svn_merge_range_t *range_copy =
1151 svn_merge_range_dup(range, result_pool);
1152 range_copy->start = change->end;
1153 range->start = change->start;
1154 range->end = change->end;
1155 range->inheritable = TRUE;
1156 svn_sort__array_insert(rangelist, &range_copy, ++i);
1162 /* CHANGE and RANGE share the same start rev, but
1163 CHANGE is considered older because its end rev
1166 Insert the intersection of RANGE and CHANGE into
1167 RANGELIST and then set RANGE to the non-intersecting
1168 portion of RANGE. */
1169 svn_merge_range_t *range_copy =
1170 svn_merge_range_dup(range, result_pool);
1171 range_copy->end = change->end;
1172 range_copy->inheritable = TRUE;
1173 range->start = change->end;
1174 svn_sort__array_insert(rangelist, &range_copy, i++);
1182 /* Copy any remaining elements in CHANGES into RANGELIST. */
1183 for (; j < (changes)->nelts; j++)
1185 svn_merge_range_t *change =
1186 APR_ARRAY_IDX(changes, j, svn_merge_range_t *);
1187 svn_merge_range_t *change_copy = svn_merge_range_dup(change,
1189 svn_sort__array_insert(rangelist, &change_copy, rangelist->nelts);
1192 return SVN_NO_ERROR;
1195 /* Return TRUE iff the forward revision ranges FIRST and SECOND overlap and
1196 * (if CONSIDER_INHERITANCE is TRUE) have the same inheritability. */
1197 static svn_boolean_t
1198 range_intersect(const svn_merge_range_t *first, const svn_merge_range_t *second,
1199 svn_boolean_t consider_inheritance)
1201 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(first));
1202 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(second));
1204 return (first->start + 1 <= second->end)
1205 && (second->start + 1 <= first->end)
1206 && (!consider_inheritance
1207 || (!(first->inheritable) == !(second->inheritable)));
1210 /* Return TRUE iff the forward revision range FIRST wholly contains the
1211 * forward revision range SECOND and (if CONSIDER_INHERITANCE is TRUE) has
1212 * the same inheritability. */
1213 static svn_boolean_t
1214 range_contains(const svn_merge_range_t *first, const svn_merge_range_t *second,
1215 svn_boolean_t consider_inheritance)
1217 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(first));
1218 SVN_ERR_ASSERT_NO_RETURN(IS_VALID_FORWARD_RANGE(second));
1220 return (first->start <= second->start) && (second->end <= first->end)
1221 && (!consider_inheritance
1222 || (!(first->inheritable) == !(second->inheritable)));
1225 /* Swap start and end fields of RANGE. */
1227 range_swap_endpoints(svn_merge_range_t *range)
1229 svn_revnum_t swap = range->start;
1230 range->start = range->end;
1235 svn_rangelist_reverse(svn_rangelist_t *rangelist, apr_pool_t *pool)
1239 svn_sort__array_reverse(rangelist, pool);
1241 for (i = 0; i < rangelist->nelts; i++)
1243 range_swap_endpoints(APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *));
1246 return SVN_NO_ERROR;
1250 svn_rangelist__set_inheritance(svn_rangelist_t *rangelist,
1251 svn_boolean_t inheritable)
1256 svn_merge_range_t *range;
1258 for (i = 0; i < rangelist->nelts; i++)
1260 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
1261 range->inheritable = inheritable;
1268 svn_mergeinfo__set_inheritance(svn_mergeinfo_t mergeinfo,
1269 svn_boolean_t inheritable,
1270 apr_pool_t *scratch_pool)
1274 apr_hash_index_t *hi;
1276 for (hi = apr_hash_first(scratch_pool, mergeinfo);
1278 hi = apr_hash_next(hi))
1280 svn_rangelist_t *rangelist = apr_hash_this_val(hi);
1283 svn_rangelist__set_inheritance(rangelist, inheritable);
1289 /* If DO_REMOVE is true, then remove any overlapping ranges described by
1290 RANGELIST1 from RANGELIST2 and place the results in *OUTPUT. When
1291 DO_REMOVE is true, RANGELIST1 is effectively the "eraser" and RANGELIST2
1294 If DO_REMOVE is false, then capture the intersection between RANGELIST1
1295 and RANGELIST2 and place the results in *OUTPUT. The ordering of
1296 RANGELIST1 and RANGELIST2 doesn't matter when DO_REMOVE is false.
1298 If CONSIDER_INHERITANCE is true, then take the inheritance of the
1299 ranges in RANGELIST1 and RANGELIST2 into account when comparing them
1300 for intersection, see the doc string for svn_rangelist_intersect().
1302 If CONSIDER_INHERITANCE is false, then ranges with differing inheritance
1303 may intersect, but the resulting intersection is non-inheritable only
1304 if both ranges were non-inheritable, e.g.:
1306 RANGELIST1 RANGELIST2 CONSIDER DO_REMOVE *OUTPUT
1308 ---------- ------ ----------- --------- -------
1310 90-420* 1-100 TRUE FALSE Empty Rangelist
1311 90-420 1-100* TRUE FALSE Empty Rangelist
1312 90-420 1-100 TRUE FALSE 90-100
1313 90-420* 1-100* TRUE FALSE 90-100*
1315 90-420* 1-100 FALSE FALSE 90-100
1316 90-420 1-100* FALSE FALSE 90-100
1317 90-420 1-100 FALSE FALSE 90-100
1318 90-420* 1-100* FALSE FALSE 90-100*
1320 Allocate the contents of *OUTPUT in POOL. */
1321 static svn_error_t *
1322 rangelist_intersect_or_remove(svn_rangelist_t **output,
1323 const svn_rangelist_t *rangelist1,
1324 const svn_rangelist_t *rangelist2,
1325 svn_boolean_t do_remove,
1326 svn_boolean_t consider_inheritance,
1330 svn_merge_range_t working_elt2;
1332 *output = apr_array_make(pool, 1, sizeof(svn_merge_range_t *));
1336 lasti2 = -1; /* Initialized to a value that "i2" will never be. */
1338 while (i1 < rangelist1->nelts && i2 < rangelist2->nelts)
1340 svn_merge_range_t *elt1, *elt2;
1342 elt1 = APR_ARRAY_IDX(rangelist1, i1, svn_merge_range_t *);
1344 /* Instead of making a copy of the entire array of rangelist2
1345 elements, we just keep a copy of the current rangelist2 element
1346 that needs to be used, and modify our copy if necessary. */
1350 *(APR_ARRAY_IDX(rangelist2, i2, svn_merge_range_t *));
1354 elt2 = &working_elt2;
1356 /* If the rangelist2 range is contained completely in the
1357 rangelist1, we increment the rangelist2.
1358 If the ranges intersect, and match exactly, we increment both
1359 rangelist1 and rangelist2.
1360 Otherwise, we have to generate a range for the left part of
1361 the removal of rangelist1 from rangelist2, and possibly change
1362 the rangelist2 to the remaining portion of the right part of
1363 the removal, to test against. */
1364 if (range_contains(elt1, elt2, consider_inheritance))
1368 svn_merge_range_t tmp_range;
1369 tmp_range.start = elt2->start;
1370 tmp_range.end = elt2->end;
1371 /* The intersection of two ranges is non-inheritable only
1372 if both ranges are non-inheritable. */
1373 tmp_range.inheritable =
1374 (elt2->inheritable || elt1->inheritable);
1375 SVN_ERR(combine_with_lastrange(&tmp_range, *output,
1376 consider_inheritance,
1382 if (elt2->start == elt1->start && elt2->end == elt1->end)
1385 else if (range_intersect(elt1, elt2, consider_inheritance))
1387 if (elt2->start < elt1->start)
1389 /* The rangelist2 range starts before the rangelist1 range. */
1390 svn_merge_range_t tmp_range;
1393 /* Retain the range that falls before the rangelist1
1395 tmp_range.start = elt2->start;
1396 tmp_range.end = elt1->start;
1397 tmp_range.inheritable = elt2->inheritable;
1401 /* Retain the range that falls between the rangelist1
1402 start and rangelist2 end. */
1403 tmp_range.start = elt1->start;
1404 tmp_range.end = MIN(elt2->end, elt1->end);
1405 /* The intersection of two ranges is non-inheritable only
1406 if both ranges are non-inheritable. */
1407 tmp_range.inheritable =
1408 (elt2->inheritable || elt1->inheritable);
1411 SVN_ERR(combine_with_lastrange(&tmp_range,
1412 *output, consider_inheritance,
1416 /* Set up the rest of the rangelist2 range for further
1418 if (elt2->end > elt1->end)
1420 /* The rangelist2 range ends after the rangelist1 range. */
1423 /* Partial overlap. */
1424 svn_merge_range_t tmp_range;
1425 tmp_range.start = MAX(elt2->start, elt1->start);
1426 tmp_range.end = elt1->end;
1427 /* The intersection of two ranges is non-inheritable only
1428 if both ranges are non-inheritable. */
1429 tmp_range.inheritable =
1430 (elt2->inheritable || elt1->inheritable);
1431 SVN_ERR(combine_with_lastrange(&tmp_range,
1433 consider_inheritance,
1437 working_elt2.start = elt1->end;
1438 working_elt2.end = elt2->end;
1443 else /* ranges don't intersect */
1445 /* See which side of the rangelist2 the rangelist1 is on. If it
1446 is on the left side, we need to move the rangelist1.
1448 If it is on past the rangelist2 on the right side, we
1449 need to output the rangelist2 and increment the
1451 if (svn_sort_compare_ranges(&elt1, &elt2) < 0)
1455 svn_merge_range_t *lastrange;
1457 if ((*output)->nelts > 0)
1458 lastrange = APR_ARRAY_IDX(*output, (*output)->nelts - 1,
1459 svn_merge_range_t *);
1463 if (do_remove && !(lastrange &&
1464 combine_ranges(lastrange, lastrange, elt2,
1465 consider_inheritance)))
1467 lastrange = svn_merge_range_dup(elt2, pool);
1468 APR_ARRAY_PUSH(*output, svn_merge_range_t *) = lastrange;
1477 /* Copy the current rangelist2 element if we didn't hit the end
1478 of the rangelist2, and we still had it around. This element
1479 may have been touched, so we can't just walk the rangelist2
1480 array, we have to use our copy. This case only happens when
1481 we ran out of rangelist1 before rangelist2, *and* we had changed
1482 the rangelist2 element. */
1483 if (i2 == lasti2 && i2 < rangelist2->nelts)
1485 SVN_ERR(combine_with_lastrange(&working_elt2, *output,
1486 consider_inheritance, pool));
1490 /* Copy any other remaining untouched rangelist2 elements. */
1491 for (; i2 < rangelist2->nelts; i2++)
1493 svn_merge_range_t *elt = APR_ARRAY_IDX(rangelist2, i2,
1494 svn_merge_range_t *);
1496 SVN_ERR(combine_with_lastrange(elt, *output,
1497 consider_inheritance, pool));
1501 return SVN_NO_ERROR;
1506 svn_rangelist_intersect(svn_rangelist_t **output,
1507 const svn_rangelist_t *rangelist1,
1508 const svn_rangelist_t *rangelist2,
1509 svn_boolean_t consider_inheritance,
1512 return rangelist_intersect_or_remove(output, rangelist1, rangelist2, FALSE,
1513 consider_inheritance, pool);
1517 svn_rangelist_remove(svn_rangelist_t **output,
1518 const svn_rangelist_t *eraser,
1519 const svn_rangelist_t *whiteboard,
1520 svn_boolean_t consider_inheritance,
1523 return rangelist_intersect_or_remove(output, eraser, whiteboard, TRUE,
1524 consider_inheritance, pool);
1528 svn_rangelist_diff(svn_rangelist_t **deleted, svn_rangelist_t **added,
1529 const svn_rangelist_t *from, const svn_rangelist_t *to,
1530 svn_boolean_t consider_inheritance,
1533 /* The following diagrams illustrate some common range delta scenarios:
1536 r0 <===========(=========)============[=========]===========> rHEAD
1539 (from) deleted deleted
1540 r0 <===========(=========[============]=========)===========> rHEAD
1544 r0 <===========(=========[============)=========]===========> rHEAD
1548 r0 <===========[=========(============]=========)===========> rHEAD
1552 r0 <===========[=========(============)=========]===========> rHEAD
1556 r0 <===(=[=)=]=[==]=[=(=)=]=[=]=[=(===|===(=)==|=|==[=(=]=)=> rHEAD
1560 /* The items that are present in from, but not in to, must have been
1562 SVN_ERR(svn_rangelist_remove(deleted, to, from, consider_inheritance,
1564 /* The items that are present in to, but not in from, must have been
1566 return svn_rangelist_remove(added, from, to, consider_inheritance, pool);
1569 struct mergeinfo_diff_baton
1571 svn_mergeinfo_t from;
1573 svn_mergeinfo_t deleted;
1574 svn_mergeinfo_t added;
1575 svn_boolean_t consider_inheritance;
1579 /* This implements the 'svn_hash_diff_func_t' interface.
1580 BATON is of type 'struct mergeinfo_diff_baton *'.
1582 static svn_error_t *
1583 mergeinfo_hash_diff_cb(const void *key, apr_ssize_t klen,
1584 enum svn_hash_diff_key_status status,
1587 /* hash_a is FROM mergeinfo,
1588 hash_b is TO mergeinfo. */
1589 struct mergeinfo_diff_baton *cb = baton;
1590 svn_rangelist_t *from_rangelist, *to_rangelist;
1591 const char *path = key;
1592 if (status == svn_hash_diff_key_both)
1594 /* Record any deltas (additions or deletions). */
1595 svn_rangelist_t *deleted_rangelist, *added_rangelist;
1596 from_rangelist = apr_hash_get(cb->from, path, klen);
1597 to_rangelist = apr_hash_get(cb->to, path, klen);
1598 SVN_ERR(svn_rangelist_diff(&deleted_rangelist, &added_rangelist,
1599 from_rangelist, to_rangelist,
1600 cb->consider_inheritance, cb->pool));
1601 if (cb->deleted && deleted_rangelist->nelts > 0)
1602 apr_hash_set(cb->deleted, apr_pstrmemdup(cb->pool, path, klen),
1603 klen, deleted_rangelist);
1604 if (cb->added && added_rangelist->nelts > 0)
1605 apr_hash_set(cb->added, apr_pstrmemdup(cb->pool, path, klen),
1606 klen, added_rangelist);
1608 else if ((status == svn_hash_diff_key_a) && cb->deleted)
1610 from_rangelist = apr_hash_get(cb->from, path, klen);
1611 apr_hash_set(cb->deleted, apr_pstrmemdup(cb->pool, path, klen), klen,
1612 svn_rangelist_dup(from_rangelist, cb->pool));
1614 else if ((status == svn_hash_diff_key_b) && cb->added)
1616 to_rangelist = apr_hash_get(cb->to, path, klen);
1617 apr_hash_set(cb->added, apr_pstrmemdup(cb->pool, path, klen), klen,
1618 svn_rangelist_dup(to_rangelist, cb->pool));
1620 return SVN_NO_ERROR;
1623 /* Record deletions and additions of entire range lists (by path
1624 presence), and delegate to svn_rangelist_diff() for delta
1625 calculations on a specific path. */
1626 static svn_error_t *
1627 walk_mergeinfo_hash_for_diff(svn_mergeinfo_t from, svn_mergeinfo_t to,
1628 svn_mergeinfo_t deleted, svn_mergeinfo_t added,
1629 svn_boolean_t consider_inheritance,
1630 apr_pool_t *result_pool,
1631 apr_pool_t *scratch_pool)
1633 struct mergeinfo_diff_baton mdb;
1636 mdb.deleted = deleted;
1638 mdb.consider_inheritance = consider_inheritance;
1639 mdb.pool = result_pool;
1641 return svn_hash_diff(from, to, mergeinfo_hash_diff_cb, &mdb, scratch_pool);
1645 svn_mergeinfo_diff2(svn_mergeinfo_t *deleted, svn_mergeinfo_t *added,
1646 svn_mergeinfo_t from, svn_mergeinfo_t to,
1647 svn_boolean_t consider_inheritance,
1648 apr_pool_t *result_pool,
1649 apr_pool_t *scratch_pool)
1651 if (from && to == NULL)
1653 *deleted = svn_mergeinfo_dup(from, result_pool);
1654 *added = svn_hash__make(result_pool);
1656 else if (from == NULL && to)
1658 *deleted = svn_hash__make(result_pool);
1659 *added = svn_mergeinfo_dup(to, result_pool);
1663 *deleted = svn_hash__make(result_pool);
1664 *added = svn_hash__make(result_pool);
1668 SVN_ERR(walk_mergeinfo_hash_for_diff(from, to, *deleted, *added,
1669 consider_inheritance,
1670 result_pool, scratch_pool));
1674 return SVN_NO_ERROR;
1678 svn_mergeinfo__equals(svn_boolean_t *is_equal,
1679 svn_mergeinfo_t info1,
1680 svn_mergeinfo_t info2,
1681 svn_boolean_t consider_inheritance,
1684 apr_hash_index_t *hi;
1688 /* special cases: at least one side has no merge info */
1689 if (info1 == NULL && info2 == NULL)
1692 return SVN_NO_ERROR;
1695 if (info1 == NULL || info2 == NULL)
1696 return SVN_NO_ERROR;
1698 /* trivial case: different number of paths -> unequal */
1699 if (apr_hash_count(info1) != apr_hash_count(info2))
1700 return SVN_NO_ERROR;
1702 /* compare range lists for all paths */
1703 for (hi = apr_hash_first(pool, info1); hi; hi = apr_hash_next(hi))
1706 apr_ssize_t key_length;
1707 svn_rangelist_t *lhs, *rhs;
1709 svn_rangelist_t *deleted, *added;
1711 /* get both path lists */
1712 apr_hash_this(hi, (const void**)&key, &key_length, (void **)&lhs);
1713 rhs = apr_hash_get(info2, key, key_length);
1715 /* missing on one side? */
1717 return SVN_NO_ERROR;
1719 /* quick compare: the range lists will often be a perfect match */
1720 if (lhs->nelts == rhs->nelts)
1722 for (i = 0; i < lhs->nelts; ++i)
1724 svn_merge_range_t *lrange
1725 = APR_ARRAY_IDX(lhs, i, svn_merge_range_t *);
1726 svn_merge_range_t *rrange
1727 = APR_ARRAY_IDX(rhs, i, svn_merge_range_t *);
1729 /* range mismatch? -> needs detailed comparison */
1730 if ( lrange->start != rrange->start
1731 || lrange->end != rrange->end)
1734 /* inheritance mismatch? -> merge info differs */
1735 if ( consider_inheritance
1736 && lrange->inheritable != rrange->inheritable)
1737 return SVN_NO_ERROR;
1740 /* all ranges found to match -> next path */
1741 if (i == lhs->nelts)
1745 /* range lists differ but there are many ways to sort and aggregate
1746 revisions into ranges. Do a full diff on them. */
1747 SVN_ERR(svn_rangelist_diff(&deleted, &added, lhs, rhs,
1748 consider_inheritance, pool));
1749 if (deleted->nelts || added->nelts)
1750 return SVN_NO_ERROR;
1753 /* no mismatch found */
1755 return SVN_NO_ERROR;
1759 svn_mergeinfo_merge2(svn_mergeinfo_t mergeinfo,
1760 svn_mergeinfo_t changes,
1761 apr_pool_t *result_pool,
1762 apr_pool_t *scratch_pool)
1764 apr_hash_index_t *hi;
1765 apr_pool_t *iterpool;
1767 if (!apr_hash_count(changes))
1768 return SVN_NO_ERROR;
1770 iterpool = svn_pool_create(scratch_pool);
1771 for (hi = apr_hash_first(scratch_pool, changes); hi; hi = apr_hash_next(hi))
1775 svn_rangelist_t *to_insert;
1776 svn_rangelist_t *target;
1778 /* get ranges to insert and the target ranges list of that insertion */
1779 apr_hash_this(hi, (const void**)&key, &klen, (void*)&to_insert);
1780 target = apr_hash_get(mergeinfo, key, klen);
1782 /* if range list exists, just expand on it.
1783 * Otherwise, add new hash entry. */
1786 SVN_ERR(svn_rangelist_merge2(target, to_insert, result_pool,
1788 svn_pool_clear(iterpool);
1791 apr_hash_set(mergeinfo, key, klen, to_insert);
1794 svn_pool_destroy(iterpool);
1796 return SVN_NO_ERROR;
1800 svn_mergeinfo_catalog_merge(svn_mergeinfo_catalog_t mergeinfo_cat,
1801 svn_mergeinfo_catalog_t changes_cat,
1802 apr_pool_t *result_pool,
1803 apr_pool_t *scratch_pool)
1807 apr_array_header_t *sorted_cat =
1808 svn_sort__hash(mergeinfo_cat, svn_sort_compare_items_as_paths,
1810 apr_array_header_t *sorted_changes =
1811 svn_sort__hash(changes_cat, svn_sort_compare_items_as_paths,
1814 while (i < sorted_cat->nelts && j < sorted_changes->nelts)
1816 svn_sort__item_t cat_elt, change_elt;
1819 cat_elt = APR_ARRAY_IDX(sorted_cat, i, svn_sort__item_t);
1820 change_elt = APR_ARRAY_IDX(sorted_changes, j, svn_sort__item_t);
1821 res = svn_sort_compare_items_as_paths(&cat_elt, &change_elt);
1823 if (res == 0) /* Both catalogs have mergeinfo for a given path. */
1825 svn_mergeinfo_t mergeinfo = cat_elt.value;
1826 svn_mergeinfo_t changes_mergeinfo = change_elt.value;
1828 SVN_ERR(svn_mergeinfo_merge2(mergeinfo, changes_mergeinfo,
1829 result_pool, scratch_pool));
1830 apr_hash_set(mergeinfo_cat, cat_elt.key, cat_elt.klen, mergeinfo);
1834 else if (res < 0) /* Only MERGEINFO_CAT has mergeinfo for this path. */
1838 else /* Only CHANGES_CAT has mergeinfo for this path. */
1840 apr_hash_set(mergeinfo_cat,
1841 apr_pstrdup(result_pool, change_elt.key),
1843 svn_mergeinfo_dup(change_elt.value, result_pool));
1848 /* Copy back any remaining elements from the CHANGES_CAT catalog. */
1849 for (; j < sorted_changes->nelts; j++)
1851 svn_sort__item_t elt = APR_ARRAY_IDX(sorted_changes, j,
1853 apr_hash_set(mergeinfo_cat,
1854 apr_pstrdup(result_pool, elt.key),
1856 svn_mergeinfo_dup(elt.value, result_pool));
1859 return SVN_NO_ERROR;
1863 svn_mergeinfo_intersect2(svn_mergeinfo_t *mergeinfo,
1864 svn_mergeinfo_t mergeinfo1,
1865 svn_mergeinfo_t mergeinfo2,
1866 svn_boolean_t consider_inheritance,
1867 apr_pool_t *result_pool,
1868 apr_pool_t *scratch_pool)
1870 apr_hash_index_t *hi;
1871 apr_pool_t *iterpool;
1873 *mergeinfo = apr_hash_make(result_pool);
1874 iterpool = svn_pool_create(scratch_pool);
1876 /* ### TODO(reint): Do we care about the case when a path in one
1877 ### mergeinfo hash has inheritable mergeinfo, and in the other
1878 ### has non-inheritable mergeinfo? It seems like that path
1879 ### itself should really be an intersection, while child paths
1880 ### should not be... */
1881 for (hi = apr_hash_first(scratch_pool, mergeinfo1);
1882 hi; hi = apr_hash_next(hi))
1884 const char *path = apr_hash_this_key(hi);
1885 svn_rangelist_t *rangelist1 = apr_hash_this_val(hi);
1886 svn_rangelist_t *rangelist2;
1888 svn_pool_clear(iterpool);
1889 rangelist2 = svn_hash_gets(mergeinfo2, path);
1892 SVN_ERR(svn_rangelist_intersect(&rangelist2, rangelist1, rangelist2,
1893 consider_inheritance, iterpool));
1894 if (rangelist2->nelts > 0)
1895 svn_hash_sets(*mergeinfo, apr_pstrdup(result_pool, path),
1896 svn_rangelist_dup(rangelist2, result_pool));
1899 svn_pool_destroy(iterpool);
1900 return SVN_NO_ERROR;
1904 svn_mergeinfo_remove2(svn_mergeinfo_t *mergeinfo,
1905 svn_mergeinfo_t eraser,
1906 svn_mergeinfo_t whiteboard,
1907 svn_boolean_t consider_inheritance,
1908 apr_pool_t *result_pool,
1909 apr_pool_t *scratch_pool)
1911 *mergeinfo = apr_hash_make(result_pool);
1912 return walk_mergeinfo_hash_for_diff(whiteboard, eraser, *mergeinfo, NULL,
1913 consider_inheritance, result_pool,
1918 svn_rangelist_to_string(svn_string_t **output,
1919 const svn_rangelist_t *rangelist,
1922 svn_stringbuf_t *buf = svn_stringbuf_create_empty(pool);
1924 if (rangelist->nelts > 0)
1927 svn_merge_range_t *range;
1929 /* Handle the elements that need commas at the end. */
1930 for (i = 0; i < rangelist->nelts - 1; i++)
1932 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
1933 svn_stringbuf_appendcstr(buf, range_to_string(range, pool));
1934 svn_stringbuf_appendcstr(buf, ",");
1937 /* Now handle the last element, which needs no comma. */
1938 range = APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
1939 svn_stringbuf_appendcstr(buf, range_to_string(range, pool));
1942 *output = svn_stringbuf__morph_into_string(buf);
1944 return SVN_NO_ERROR;
1947 /* Converts a mergeinfo INPUT to an unparsed mergeinfo in OUTPUT. If PREFIX
1948 is not NULL then prepend PREFIX to each line in OUTPUT. If INPUT contains
1949 no elements, return the empty string. If INPUT contains any merge source
1950 path keys that are relative then convert these to absolute paths in
1953 static svn_error_t *
1954 mergeinfo_to_stringbuf(svn_stringbuf_t **output,
1955 svn_mergeinfo_t input,
1959 *output = svn_stringbuf_create_empty(pool);
1961 if (apr_hash_count(input) > 0)
1963 apr_array_header_t *sorted =
1964 svn_sort__hash(input, svn_sort_compare_items_as_paths, pool);
1967 for (i = 0; i < sorted->nelts; i++)
1969 svn_sort__item_t elt = APR_ARRAY_IDX(sorted, i, svn_sort__item_t);
1970 svn_string_t *revlist;
1972 SVN_ERR(svn_rangelist_to_string(&revlist, elt.value, pool));
1973 svn_stringbuf_appendcstr(
1975 apr_psprintf(pool, "%s%s%s:%s",
1976 prefix ? prefix : "",
1977 *((const char *) elt.key) == '/' ? "" : "/",
1978 (const char *) elt.key,
1980 if (i < sorted->nelts - 1)
1981 svn_stringbuf_appendcstr(*output, "\n");
1985 return SVN_NO_ERROR;
1989 svn_mergeinfo_to_string(svn_string_t **output, svn_mergeinfo_t input,
1992 svn_stringbuf_t *mergeinfo_buf;
1994 SVN_ERR(mergeinfo_to_stringbuf(&mergeinfo_buf, input, NULL, pool));
1995 *output = svn_stringbuf__morph_into_string(mergeinfo_buf);
1996 return SVN_NO_ERROR;
2000 svn_mergeinfo_sort(svn_mergeinfo_t input, apr_pool_t *pool)
2002 apr_hash_index_t *hi;
2004 for (hi = apr_hash_first(pool, input); hi; hi = apr_hash_next(hi))
2006 apr_array_header_t *rl = apr_hash_this_val(hi);
2008 svn_sort__array(rl, svn_sort_compare_ranges);
2010 return SVN_NO_ERROR;
2014 svn_mergeinfo__canonicalize_ranges(svn_mergeinfo_t mergeinfo,
2015 apr_pool_t *scratch_pool)
2017 apr_hash_index_t *hi;
2019 for (hi = apr_hash_first(scratch_pool, mergeinfo); hi; hi = apr_hash_next(hi))
2021 apr_array_header_t *rl = apr_hash_this_val(hi);
2023 SVN_ERR(svn_rangelist__canonicalize(rl, scratch_pool));
2026 return SVN_NO_ERROR;
2029 svn_mergeinfo_catalog_t
2030 svn_mergeinfo_catalog_dup(svn_mergeinfo_catalog_t mergeinfo_catalog,
2033 svn_mergeinfo_t new_mergeinfo_catalog = apr_hash_make(pool);
2034 apr_hash_index_t *hi;
2036 for (hi = apr_hash_first(pool, mergeinfo_catalog);
2038 hi = apr_hash_next(hi))
2040 const char *key = apr_hash_this_key(hi);
2041 svn_mergeinfo_t val = apr_hash_this_val(hi);
2043 svn_hash_sets(new_mergeinfo_catalog, apr_pstrdup(pool, key),
2044 svn_mergeinfo_dup(val, pool));
2047 return new_mergeinfo_catalog;
2051 svn_mergeinfo_dup(svn_mergeinfo_t mergeinfo, apr_pool_t *pool)
2053 svn_mergeinfo_t new_mergeinfo = svn_hash__make(pool);
2054 apr_hash_index_t *hi;
2056 for (hi = apr_hash_first(pool, mergeinfo); hi; hi = apr_hash_next(hi))
2058 const char *path = apr_hash_this_key(hi);
2059 apr_ssize_t pathlen = apr_hash_this_key_len(hi);
2060 svn_rangelist_t *rangelist = apr_hash_this_val(hi);
2062 apr_hash_set(new_mergeinfo, apr_pstrmemdup(pool, path, pathlen), pathlen,
2063 svn_rangelist_dup(rangelist, pool));
2066 return new_mergeinfo;
2070 svn_mergeinfo_inheritable2(svn_mergeinfo_t *output,
2071 svn_mergeinfo_t mergeinfo,
2075 svn_boolean_t inheritable,
2076 apr_pool_t *result_pool,
2077 apr_pool_t *scratch_pool)
2079 apr_hash_index_t *hi;
2080 svn_mergeinfo_t inheritable_mergeinfo = apr_hash_make(result_pool);
2082 for (hi = apr_hash_first(scratch_pool, mergeinfo);
2084 hi = apr_hash_next(hi))
2086 const char *key = apr_hash_this_key(hi);
2087 apr_ssize_t keylen = apr_hash_this_key_len(hi);
2088 svn_rangelist_t *rangelist = apr_hash_this_val(hi);
2089 svn_rangelist_t *inheritable_rangelist;
2091 if (!path || svn_path_compare_paths(path, key) == 0)
2092 SVN_ERR(svn_rangelist_inheritable2(&inheritable_rangelist, rangelist,
2093 start, end, inheritable,
2094 result_pool, scratch_pool));
2096 inheritable_rangelist = svn_rangelist_dup(rangelist, result_pool);
2098 /* Only add this rangelist if some ranges remain. A rangelist with
2099 a path mapped to an empty rangelist is not syntactically valid */
2100 if (inheritable_rangelist->nelts)
2101 apr_hash_set(inheritable_mergeinfo,
2102 apr_pstrmemdup(result_pool, key, keylen), keylen,
2103 inheritable_rangelist);
2105 *output = inheritable_mergeinfo;
2106 return SVN_NO_ERROR;
2111 svn_rangelist_inheritable2(svn_rangelist_t **inheritable_rangelist,
2112 const svn_rangelist_t *rangelist,
2115 svn_boolean_t inheritable,
2116 apr_pool_t *result_pool,
2117 apr_pool_t *scratch_pool)
2119 *inheritable_rangelist = apr_array_make(result_pool, 1,
2120 sizeof(svn_merge_range_t *));
2121 if (rangelist->nelts)
2123 if (!SVN_IS_VALID_REVNUM(start)
2124 || !SVN_IS_VALID_REVNUM(end)
2127 /* We want all (non-inheritable or inheritable) ranges removed. */
2130 for (i = 0; i < rangelist->nelts; i++)
2132 svn_merge_range_t *range = APR_ARRAY_IDX(rangelist, i,
2133 svn_merge_range_t *);
2134 if (range->inheritable == inheritable)
2136 APR_ARRAY_PUSH(*inheritable_rangelist, svn_merge_range_t *)
2137 = svn_merge_range_dup(range, result_pool);
2143 /* We want only the (non-inheritable or inheritable) ranges
2144 bound by START and END removed. */
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,
2161 apr_pool_t *scratch_pool)
2163 apr_hash_index_t *hi;
2164 svn_boolean_t removed_some_ranges = FALSE;
2168 for (hi = apr_hash_first(scratch_pool, mergeinfo); hi;
2169 hi = apr_hash_next(hi))
2171 const char *path = apr_hash_this_key(hi);
2172 svn_rangelist_t *rangelist = apr_hash_this_val(hi);
2174 if (rangelist->nelts == 0)
2176 svn_hash_sets(mergeinfo, path, NULL);
2177 removed_some_ranges = TRUE;
2181 return removed_some_ranges;
2185 svn_mergeinfo__remove_prefix_from_catalog(svn_mergeinfo_catalog_t *out_catalog,
2186 svn_mergeinfo_catalog_t in_catalog,
2187 const char *prefix_path,
2190 apr_hash_index_t *hi;
2192 SVN_ERR_ASSERT(prefix_path[0] == '/');
2194 *out_catalog = apr_hash_make(pool);
2196 for (hi = apr_hash_first(pool, in_catalog); hi; hi = apr_hash_next(hi))
2198 const char *original_path = apr_hash_this_key(hi);
2199 svn_mergeinfo_t value = apr_hash_this_val(hi);
2200 const char *new_path;
2202 new_path = svn_fspath__skip_ancestor(prefix_path, original_path);
2203 SVN_ERR_ASSERT(new_path);
2205 svn_hash_sets(*out_catalog, new_path, value);
2208 return SVN_NO_ERROR;
2212 svn_mergeinfo__add_prefix_to_catalog(svn_mergeinfo_catalog_t *out_catalog,
2213 svn_mergeinfo_catalog_t in_catalog,
2214 const char *prefix_path,
2215 apr_pool_t *result_pool,
2216 apr_pool_t *scratch_pool)
2218 apr_hash_index_t *hi;
2220 *out_catalog = apr_hash_make(result_pool);
2222 for (hi = apr_hash_first(scratch_pool, in_catalog);
2224 hi = apr_hash_next(hi))
2226 const char *original_path = apr_hash_this_key(hi);
2227 svn_mergeinfo_t value = apr_hash_this_val(hi);
2229 if (original_path[0] == '/')
2232 svn_hash_sets(*out_catalog,
2233 svn_dirent_join(prefix_path, original_path, result_pool),
2237 return SVN_NO_ERROR;
2241 svn_mergeinfo__add_suffix_to_mergeinfo(svn_mergeinfo_t *out_mergeinfo,
2242 svn_mergeinfo_t mergeinfo,
2243 const char *suffix_relpath,
2244 apr_pool_t *result_pool,
2245 apr_pool_t *scratch_pool)
2247 apr_hash_index_t *hi;
2249 SVN_ERR_ASSERT(suffix_relpath && svn_relpath_is_canonical(suffix_relpath));
2251 *out_mergeinfo = apr_hash_make(result_pool);
2253 for (hi = apr_hash_first(scratch_pool, mergeinfo);
2255 hi = apr_hash_next(hi))
2257 const char *fspath = apr_hash_this_key(hi);
2258 svn_rangelist_t *rangelist = apr_hash_this_val(hi);
2260 svn_hash_sets(*out_mergeinfo,
2261 svn_fspath__join(fspath, suffix_relpath, result_pool),
2265 return SVN_NO_ERROR;
2268 /* Deep-copy an array of pointers to simple objects.
2270 * Return a duplicate in POOL of the array ARRAY of pointers to objects
2271 * of size OBJECT_SIZE bytes. Duplicate each object bytewise.
2273 static apr_array_header_t *
2274 ptr_array_dup(const apr_array_header_t *array,
2278 apr_array_header_t *new_array = apr_array_make(pool, array->nelts,
2281 /* allocate target range buffer with a single operation */
2282 char *copy = apr_palloc(pool, object_size * array->nelts);
2284 /* for efficiency, directly address source and target reference buffers */
2285 void **source = (void **)(array->elts);
2286 void **target = (void **)(new_array->elts);
2289 /* copy ranges iteratively and link them into the target range list */
2290 for (i = 0; i < array->nelts; i++)
2292 target[i] = ©[i * object_size];
2293 memcpy(target[i], source[i], object_size);
2295 new_array->nelts = array->nelts;
2301 svn_rangelist_dup(const svn_rangelist_t *rangelist, apr_pool_t *pool)
2303 return ptr_array_dup(rangelist, sizeof(svn_merge_range_t), pool);
2307 svn_merge_range_dup(const svn_merge_range_t *range, apr_pool_t *pool)
2309 svn_merge_range_t *new_range = apr_palloc(pool, sizeof(*new_range));
2310 memcpy(new_range, range, sizeof(*new_range));
2315 svn_merge_range_contains_rev(const svn_merge_range_t *range, svn_revnum_t rev)
2317 assert(SVN_IS_VALID_REVNUM(range->start));
2318 assert(SVN_IS_VALID_REVNUM(range->end));
2319 assert(range->start != range->end);
2321 if (range->start < range->end)
2322 return rev > range->start && rev <= range->end;
2324 return rev > range->end && rev <= range->start;
2328 svn_mergeinfo__catalog_to_formatted_string(svn_string_t **output,
2329 svn_mergeinfo_catalog_t catalog,
2330 const char *key_prefix,
2331 const char *val_prefix,
2334 svn_stringbuf_t *output_buf = NULL;
2336 if (catalog && apr_hash_count(catalog))
2339 apr_array_header_t *sorted_catalog =
2340 svn_sort__hash(catalog, svn_sort_compare_items_as_paths, pool);
2342 output_buf = svn_stringbuf_create_empty(pool);
2343 for (i = 0; i < sorted_catalog->nelts; i++)
2345 svn_sort__item_t elt =
2346 APR_ARRAY_IDX(sorted_catalog, i, svn_sort__item_t);
2348 svn_mergeinfo_t mergeinfo;
2349 svn_stringbuf_t *mergeinfo_output_buf;
2352 mergeinfo = elt.value;
2354 svn_stringbuf_appendcstr(output_buf, key_prefix);
2355 svn_stringbuf_appendcstr(output_buf, path1);
2356 svn_stringbuf_appendcstr(output_buf, "\n");
2357 SVN_ERR(mergeinfo_to_stringbuf(&mergeinfo_output_buf, mergeinfo,
2358 val_prefix ? val_prefix : "", pool));
2359 svn_stringbuf_appendstr(output_buf, mergeinfo_output_buf);
2360 svn_stringbuf_appendcstr(output_buf, "\n");
2366 output_buf = svn_stringbuf_create(key_prefix ? key_prefix : "", pool);
2367 svn_stringbuf_appendcstr(output_buf, _("NULL mergeinfo catalog\n"));
2369 else if (apr_hash_count(catalog) == 0)
2371 output_buf = svn_stringbuf_create(key_prefix ? key_prefix : "", pool);
2372 svn_stringbuf_appendcstr(output_buf, _("empty mergeinfo catalog\n"));
2376 /* If we have an output_buf, convert it to an svn_string_t;
2377 otherwise, return a new string containing only a newline
2380 *output = svn_stringbuf__morph_into_string(output_buf);
2382 *output = svn_string_create("\n", pool);
2384 return SVN_NO_ERROR;
2388 svn_mergeinfo__get_range_endpoints(svn_revnum_t *youngest_rev,
2389 svn_revnum_t *oldest_rev,
2390 svn_mergeinfo_t mergeinfo,
2393 *youngest_rev = *oldest_rev = SVN_INVALID_REVNUM;
2396 apr_hash_index_t *hi;
2398 for (hi = apr_hash_first(pool, mergeinfo); hi; hi = apr_hash_next(hi))
2400 svn_rangelist_t *rangelist = apr_hash_this_val(hi);
2402 if (rangelist->nelts)
2404 svn_merge_range_t *range = APR_ARRAY_IDX(rangelist,
2405 rangelist->nelts - 1,
2406 svn_merge_range_t *);
2407 if (!SVN_IS_VALID_REVNUM(*youngest_rev)
2408 || (range->end > *youngest_rev))
2409 *youngest_rev = range->end;
2411 range = APR_ARRAY_IDX(rangelist, 0, svn_merge_range_t *);
2412 if (!SVN_IS_VALID_REVNUM(*oldest_rev)
2413 || (range->start < *oldest_rev))
2414 *oldest_rev = range->start;
2418 return SVN_NO_ERROR;
2422 svn_mergeinfo__filter_catalog_by_ranges(svn_mergeinfo_catalog_t *filtered_cat,
2423 svn_mergeinfo_catalog_t catalog,
2424 svn_revnum_t youngest_rev,
2425 svn_revnum_t oldest_rev,
2426 svn_boolean_t include_range,
2427 apr_pool_t *result_pool,
2428 apr_pool_t *scratch_pool)
2430 apr_hash_index_t *hi;
2432 *filtered_cat = apr_hash_make(result_pool);
2433 for (hi = apr_hash_first(scratch_pool, catalog);
2435 hi = apr_hash_next(hi))
2437 const char *path = apr_hash_this_key(hi);
2438 svn_mergeinfo_t mergeinfo = apr_hash_this_val(hi);
2439 svn_mergeinfo_t filtered_mergeinfo;
2441 SVN_ERR(svn_mergeinfo__filter_mergeinfo_by_ranges(&filtered_mergeinfo,
2448 if (apr_hash_count(filtered_mergeinfo))
2449 svn_hash_sets(*filtered_cat,
2450 apr_pstrdup(result_pool, path), filtered_mergeinfo);
2453 return SVN_NO_ERROR;
2457 svn_mergeinfo__filter_mergeinfo_by_ranges(svn_mergeinfo_t *filtered_mergeinfo,
2458 svn_mergeinfo_t mergeinfo,
2459 svn_revnum_t youngest_rev,
2460 svn_revnum_t oldest_rev,
2461 svn_boolean_t include_range,
2462 apr_pool_t *result_pool,
2463 apr_pool_t *scratch_pool)
2465 SVN_ERR_ASSERT(SVN_IS_VALID_REVNUM(youngest_rev));
2466 SVN_ERR_ASSERT(SVN_IS_VALID_REVNUM(oldest_rev));
2467 SVN_ERR_ASSERT(oldest_rev < youngest_rev);
2469 *filtered_mergeinfo = apr_hash_make(result_pool);
2473 apr_hash_index_t *hi;
2474 svn_rangelist_t *filter_rangelist =
2475 svn_rangelist__initialize(oldest_rev, youngest_rev, TRUE,
2478 for (hi = apr_hash_first(scratch_pool, mergeinfo);
2480 hi = apr_hash_next(hi))
2482 const char *path = apr_hash_this_key(hi);
2483 svn_rangelist_t *rangelist = apr_hash_this_val(hi);
2485 if (rangelist->nelts)
2487 svn_rangelist_t *new_rangelist;
2489 SVN_ERR(rangelist_intersect_or_remove(
2490 &new_rangelist, filter_rangelist, rangelist,
2491 ! include_range, FALSE, result_pool));
2493 if (new_rangelist->nelts)
2494 svn_hash_sets(*filtered_mergeinfo,
2495 apr_pstrdup(result_pool, path), new_rangelist);
2499 return SVN_NO_ERROR;
2503 svn_mergeinfo__adjust_mergeinfo_rangelists(svn_mergeinfo_t *adjusted_mergeinfo,
2504 svn_mergeinfo_t mergeinfo,
2505 svn_revnum_t offset,
2506 apr_pool_t *result_pool,
2507 apr_pool_t *scratch_pool)
2509 apr_hash_index_t *hi;
2510 *adjusted_mergeinfo = apr_hash_make(result_pool);
2514 for (hi = apr_hash_first(scratch_pool, mergeinfo);
2516 hi = apr_hash_next(hi))
2519 const char *path = apr_hash_this_key(hi);
2520 svn_rangelist_t *rangelist = apr_hash_this_val(hi);
2521 svn_rangelist_t *adjusted_rangelist =
2522 apr_array_make(result_pool, rangelist->nelts,
2523 sizeof(svn_merge_range_t *));
2525 for (i = 0; i < rangelist->nelts; i++)
2527 svn_merge_range_t *range =
2528 APR_ARRAY_IDX(rangelist, i, svn_merge_range_t *);
2530 if (range->start + offset > 0 && range->end + offset > 0)
2532 range->start = range->start + offset;
2533 range->end = range->end + offset;
2534 APR_ARRAY_PUSH(adjusted_rangelist, svn_merge_range_t *) =
2539 if (adjusted_rangelist->nelts)
2540 svn_hash_sets(*adjusted_mergeinfo, apr_pstrdup(result_pool, path),
2541 adjusted_rangelist);
2544 return SVN_NO_ERROR;
2548 svn_mergeinfo__is_noninheritable(svn_mergeinfo_t mergeinfo,
2549 apr_pool_t *scratch_pool)
2553 apr_hash_index_t *hi;
2555 for (hi = apr_hash_first(scratch_pool, mergeinfo);
2557 hi = apr_hash_next(hi))
2559 svn_rangelist_t *rangelist = apr_hash_this_val(hi);
2562 for (i = 0; i < rangelist->nelts; i++)
2564 svn_merge_range_t *range = APR_ARRAY_IDX(rangelist, i,
2565 svn_merge_range_t *);
2566 if (!range->inheritable)
2575 svn_rangelist__initialize(svn_revnum_t start,
2577 svn_boolean_t inheritable,
2578 apr_pool_t *result_pool)
2580 svn_rangelist_t *rangelist =
2581 apr_array_make(result_pool, 1, sizeof(svn_merge_range_t *));
2582 svn_merge_range_t *range = apr_pcalloc(result_pool, sizeof(*range));
2584 range->start = start;
2586 range->inheritable = inheritable;
2587 APR_ARRAY_PUSH(rangelist, svn_merge_range_t *) = range;
2592 svn_mergeinfo__mergeinfo_from_segments(svn_mergeinfo_t *mergeinfo_p,
2593 const apr_array_header_t *segments,
2596 svn_mergeinfo_t mergeinfo = apr_hash_make(pool);
2599 /* Translate location segments into merge sources and ranges. */
2600 for (i = 0; i < segments->nelts; i++)
2602 svn_location_segment_t *segment =
2603 APR_ARRAY_IDX(segments, i, svn_location_segment_t *);
2604 svn_rangelist_t *path_ranges;
2605 svn_merge_range_t *range;
2606 const char *source_path;
2608 /* No path segment? Skip it. */
2609 if (! segment->path)
2612 /* Prepend a leading slash to our path. */
2613 source_path = apr_pstrcat(pool, "/", segment->path, SVN_VA_NULL);
2615 /* See if we already stored ranges for this path. If not, make
2617 path_ranges = svn_hash_gets(mergeinfo, source_path);
2619 path_ranges = apr_array_make(pool, 1, sizeof(range));
2621 /* A svn_location_segment_t may have legitimately describe only
2622 revision 0, but there is no corresponding representation for
2623 this in a svn_merge_range_t. */
2624 if (segment->range_start == 0 && segment->range_end == 0)
2627 /* Build a merge range, push it onto the list of ranges, and for
2628 good measure, (re)store it in the hash. */
2629 range = apr_pcalloc(pool, sizeof(*range));
2630 range->start = MAX(segment->range_start - 1, 0);
2631 range->end = segment->range_end;
2632 range->inheritable = TRUE;
2633 APR_ARRAY_PUSH(path_ranges, svn_merge_range_t *) = range;
2634 svn_hash_sets(mergeinfo, source_path, path_ranges);
2637 *mergeinfo_p = mergeinfo;
2638 return SVN_NO_ERROR;
2642 svn_rangelist__merge_many(svn_rangelist_t *merged_rangelist,
2643 svn_mergeinfo_t merge_history,
2644 apr_pool_t *result_pool,
2645 apr_pool_t *scratch_pool)
2647 if (apr_hash_count(merge_history))
2649 apr_pool_t *iterpool = svn_pool_create(scratch_pool);
2650 apr_hash_index_t *hi;
2652 for (hi = apr_hash_first(scratch_pool, merge_history);
2654 hi = apr_hash_next(hi))
2656 svn_rangelist_t *subtree_rangelist = apr_hash_this_val(hi);
2658 svn_pool_clear(iterpool);
2659 SVN_ERR(svn_rangelist_merge2(merged_rangelist, subtree_rangelist,
2660 result_pool, iterpool));
2662 svn_pool_destroy(iterpool);
2664 return SVN_NO_ERROR;
2669 svn_inheritance_to_word(svn_mergeinfo_inheritance_t inherit)
2673 case svn_mergeinfo_inherited:
2675 case svn_mergeinfo_nearest_ancestor:
2676 return "nearest-ancestor";
2682 svn_mergeinfo_inheritance_t
2683 svn_inheritance_from_word(const char *word)
2685 if (strcmp(word, "inherited") == 0)
2686 return svn_mergeinfo_inherited;
2687 if (strcmp(word, "nearest-ancestor") == 0)
2688 return svn_mergeinfo_nearest_ancestor;
2689 return svn_mergeinfo_explicit;