Index: subversion/include/svn_mergeinfo.h
===================================================================
--- subversion/include/svn_mergeinfo.h (revision 19977)
+++ subversion/include/svn_mergeinfo.h (working copy)
@@ -72,6 +72,18 @@
svn_mergeinfo_remove(apr_hash_t **output, apr_hash_t *eraser,
apr_hash_t *whiteboard, apr_pool_t *pool);
+/** Calculate the delta between two rangelists consisting of @c
+ * svn_merge_range_t * elements, @a from and @a to, and place the
+ * result in @a deleted and @a added (neither output argument will
+ * ever be @c NULL).
+ *
+ * @since New in 1.5.
+ */
+svn_error_t *
+svn_rangelist_diff(apr_array_header_t **deleted, apr_array_header_t **added,
+ apr_array_header_t *from, apr_array_header_t *to,
+ apr_pool_t *pool);
+
/** Merge two rangelists consisting of @c svn_merge_range_t *
* elements, @a in1 and @a in2, and place the result in @a output.
*
Index: subversion/libsvn_subr/mergeinfo.c
===================================================================
--- subversion/libsvn_subr/mergeinfo.c (revision 19977)
+++ subversion/libsvn_subr/mergeinfo.c (working copy)
@@ -375,6 +375,190 @@
}
+/* The state necessary for traversing a range list. */
+struct rangelist_iterator
+{
+ /* The list of svn_merge_range_t *'s being traversed. */
+ apr_array_header_t *rangelist;
+
+ /* How far we traveled along RANGELIST. */
+ int index;
+};
+
+/* Return the next range in the list (and increment ITER->INDEX), or
+ return NULL if none remain. */
+static svn_merge_range_t *
+next_range(struct rangelist_iterator *iter)
+{
+ if (iter->index < iter->rangelist->nelts)
+ return APR_ARRAY_IDX(iter->rangelist, iter->index++,
+ svn_merge_range_t *);
+ else
+ return NULL;
+}
+
+/* The state necessary for traversing FROM and TO range lists in
+ search of differences. */
+struct rangelist_delta_explorer
+{
+ /* The lists of svn_merge_range_t *'s being compared for deltas. */
+ struct rangelist_iterator *from_iter;
+ struct rangelist_iterator *to_iter;
+
+ /* Any differences we've detected between FROM_ITER and TO_ITER. */
+ apr_array_header_t *deletions;
+ apr_array_header_t *additions;
+};
+
+static struct rangelist_delta_explorer *
+rangelist_delta_explorer_create(apr_array_header_t *from,
+ apr_array_header_t *to, apr_pool_t *pool)
+{
+ struct rangelist_delta_explorer *delta_explorer =
+ apr_pcalloc(pool, sizeof(*delta_explorer));
+
+ delta_explorer->from_iter =
+ apr_pcalloc(pool, sizeof(*delta_explorer->from_iter));
+ delta_explorer->from_iter->rangelist = from;
+ delta_explorer->to_iter =
+ apr_pcalloc(pool, sizeof(*delta_explorer->to_iter));
+ delta_explorer->to_iter->rangelist = to;
+
+ delta_explorer->deletions =
+ apr_array_make(pool, 0, sizeof(*delta_explorer->deletions));
+ delta_explorer->additions =
+ apr_array_make(pool, 0, sizeof(*delta_explorer->additions));
+
+ return delta_explorer;
+}
+
+/* Return whether FROM and TO overlap at all. */
+static svn_boolean_t
+ranges_overlap_p(svn_merge_range_t *from, svn_merge_range_t *to)
+{
+ /* from range: 1-4, to range: 3-3 */
+ return (from != NULL && to != NULL) &&
+ ((to->start <= from->start && from->start <= to->end) ||
+ (to->start <= from->end && from->end <= to->end) ||
+ (from->start <= to->start && to->end <= from->end));
+}
+
+/* Walk all ranges in DELTA_EXPLORER, recording any deltas
+ encountered. */
+static void
+walk_rangelists(struct rangelist_delta_explorer *delta_explorer,
+ svn_merge_range_t *from, svn_merge_range_t *to,
+ apr_pool_t *pool)
+{
+ /* Walk forward along each rangelist as necessary. */
+ if (from == NULL)
+ from = next_range(delta_explorer->from_iter);
+ if (to == NULL)
+ to = next_range(delta_explorer->to_iter);
+
+ if (from == NULL && to == NULL)
+ /* No ranges remain, we're done. */
+ return;
+ if (from != NULL && to != NULL)
+ printf("'from' range: %d-%d, 'to' range: %d-%d\n",
+ from->start, from->end, to->start, to->end);
+
+ printf("checking whether ranges overlap\n");
+ if (ranges_overlap_p(from, to))
+ {
+ printf("ranges do overlap\n");
+ if (from->start != to->start && from->end != to->end)
+ {
+ /* When the overlapping ranges aren't an exact match,
+ discover and record the delta. */
+ svn_merge_range_t *range = apr_pcalloc(pool, sizeof(*range));
+ printf("no exact match\n");
+
+ /* Handle any delta between left edges of the ranges. */
+ if (from->start < to->start)
+ {
+ /* Lost revs from the left edge of the FROM range. */
+ range->start = from->start;
+ range->end = to->start - 1;
+ APR_ARRAY_PUSH(delta_explorer->deletions,
+ svn_merge_range_t *) = range;
+ printf("recorded range del: %d-%d\n", range->start, range->end);
+ range = NULL;
+ }
+ else /* from->start > to->start */
+ {
+ /* Gained revs from the left edge of the TO range. */
+ range->start = to->start;
+ range->end = from->start - 1;
+ APR_ARRAY_PUSH(delta_explorer->additions,
+ svn_merge_range_t *) = range;
+ printf("recorded range add: %d-%d\n", range->start, range->end);
+ range = NULL;
+ }
+
+ /* Handle any delta between right edges of the ranges. */
+ if (from->end > to->end)
+ {
+ /* Lost revs from the right edge of the FROM range. */
+ if (range == NULL)
+ range = apr_pcalloc(pool, sizeof(*range));
+ range->start = to->end + 1;
+ range->end = from->end;
+ APR_ARRAY_PUSH(delta_explorer->deletions,
+ svn_merge_range_t *) = range;
+ printf("recorded range del: %d-%d\n", range->start, range->end);
+ }
+ else /* from->end < to->end */
+ {
+ /* Gained revs from the right edge of the TO range. */
+ if (range == NULL)
+ range = apr_pcalloc(pool, sizeof(*range));
+ range->start = from->end + 1;
+ range->end = to->end;
+ APR_ARRAY_PUSH(delta_explorer->additions,
+ svn_merge_range_t *) = range;
+ printf("recorded range add: %d-%d\n", range->start, range->end);
+ }
+ }
+ /* else no delta to record */
+
+ /* We'll want new FROM and TO ranges for our next iteration. */
+ from = to = NULL;
+ }
+ else
+ {
+ printf("ranges don't overlap\n");
+ /* A FROM and TO range with no overlap between them indicates a
+ complete removal or addition (respectively) of the first
+ range encountered. */
+ if (from != NULL && (to == NULL || from->end < to->start))
+ {
+ /* FROM range encountered first (a delete). */
+ APR_ARRAY_PUSH(delta_explorer->deletions,
+ svn_merge_range_t *) = from;
+ printf("recorded range del: %d-%d\n", from->start, from->end);
+
+ /* We'll re-use our TO range, and see if it overlaps with
+ the next FROM range. */
+ from = NULL;
+ }
+ else
+ {
+ /* TO range encountered first (an add). */
+ APR_ARRAY_PUSH(delta_explorer->additions, svn_merge_range_t *) = to;
+ printf("recorded range add: %d-%d\n", to->start, to->end);
+
+ /* We'll re-use our FROM range, and see if it overlaps with
+ the next TO range. */
+ to = NULL;
+ }
+ printf("done dealing with non-overlapping ranges\n");
+ }
+
+ /* ### FIXME: Avoid recursion, which could be very deep. */
+ walk_rangelists(delta_explorer, from, to, pool);
+}
+
/* Output deltas via *DELETED and *ADDED, which will never be @c NULL.
The following diagrams illustrate some common range delta scenarios:
@@ -384,7 +568,7 @@
[to] added
(from) deleted deleted
- 0 <===========(=========[============]=========)===========> rHEAD
+ r0 <===========(=========[============]=========)===========> rHEAD
[to]
(from) deleted
@@ -398,22 +582,31 @@
(from)
r0 <===========[=========(============)=========]===========> rHEAD
[to] added added
+
+ (from) d d d
+ r0 <===(=[=)=]=[==]=[=(=)=]=[=]=[=(===|===(=)==|=|==[=(=]=)=> rHEAD
+ [to] a a a a a a a
*/
-static svn_error_t *
+svn_error_t *
svn_rangelist_diff(apr_array_header_t **deleted, apr_array_header_t **added,
apr_array_header_t *from, apr_array_header_t *to,
apr_pool_t *pool)
{
- int i;
+ /* ### Avoid having memory for delta_explorer stick around
+ ### (e.g. thru use of sub-pool)? */
+ struct rangelist_delta_explorer *delta_explorer =
+ rangelist_delta_explorer_create(from, to, pool);
- *deleted = apr_array_make(pool, 0, sizeof(svn_merge_range_t *));
- *added = apr_array_make(pool, 0, sizeof(svn_merge_range_t *));
+ walk_rangelists(delta_explorer, NULL, NULL, pool);
- /* ### TODO */
-
+ *deleted = delta_explorer->deletions;
+ *added = delta_explorer->additions;
return SVN_NO_ERROR;
}
+/* Record deletions and additions of entire range lists (by path
+ presence), and delegate to svn_rangelist_diff() for delta
+ calculations on a specific path. */
/* ### TODO: Merge implementation with
### libsvn_subr/sorts.c:svn_prop_diffs(). Factor out a generic
### hash diffing function for addition to APR's apr_hash.h API. */