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. */