1/*
2 * compose_delta.c:  Delta window composition.
3 *
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
12 *
13 *      http://www.apache.org/licenses/LICENSE-2.0
14 *
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
20 *    under the License.
21 * ====================================================================
22 */
23
24
25#include <assert.h>
26
27#include <apr_general.h>        /* For APR_INLINE */
28
29#include "svn_delta.h"
30#include "svn_pools.h"
31#include "delta.h"
32
33/* Define a MIN macro if this platform doesn't already have one. */
34#ifndef MIN
35#define MIN(a, b) ((a) < (b) ? (a) : (b))
36#endif
37
38
39/* ==================================================================== */
40/* Support for efficient small-block allocation from pools. */
41
42/* The following structs will be allocated and freed often: */
43
44/* A node in the range index tree. */
45typedef struct range_index_node_t range_index_node_t;
46struct range_index_node_t
47{
48  /* 'offset' and 'limit' define the range in the source window. */
49  apr_size_t offset;
50  apr_size_t limit;
51
52  /* 'target_offset' is where that range is represented in the target. */
53  apr_size_t target_offset;
54
55  /* 'left' and 'right' link the node into a splay tree. */
56  range_index_node_t *left, *right;
57
58  /* 'prev' and 'next' link it into an ordered, doubly-linked list. */
59  range_index_node_t *prev, *next;
60};
61
62/* A node in a list of ranges for source and target op copies. */
63enum range_kind
64  {
65    range_from_source,
66    range_from_target
67  };
68
69typedef struct range_list_node_t range_list_node_t;
70struct range_list_node_t
71{
72  /* Where does the range come from?
73     'offset' and 'limit' always refer to the "virtual" source data
74     for the second delta window. For a target range, the actual
75     offset to use for generating the target op is 'target_offset';
76     that field isn't used by source ranges. */
77  enum range_kind kind;
78
79  /* 'offset' and 'limit' define the range. */
80  apr_size_t offset;
81  apr_size_t limit;
82
83  /* 'target_offset' is the start of the range in the target. */
84  apr_size_t target_offset;
85
86  /* 'prev' and 'next' link the node into an ordered, doubly-linked list. */
87  range_list_node_t *prev, *next;
88};
89
90
91/* This is what will be allocated: */
92typedef union alloc_block_t alloc_block_t;
93union alloc_block_t
94{
95  range_index_node_t index_node;
96  range_list_node_t list_node;
97
98  /* Links free blocks into a freelist. */
99  alloc_block_t *next_free;
100};
101
102
103/* Allocate a block. */
104static APR_INLINE void *
105alloc_block(apr_pool_t *pool, alloc_block_t **free_list)
106{
107  alloc_block_t *block;
108  if (*free_list == NULL)
109    block = apr_palloc(pool, sizeof(*block));
110  else
111    {
112      block = *free_list;
113      *free_list = block->next_free;
114    }
115  return block;
116}
117
118/* Return the block back to the free list. */
119static APR_INLINE void
120free_block(void *ptr, alloc_block_t **free_list)
121{
122  /* Wrapper functions take care of type safety. */
123  alloc_block_t *const block = ptr;
124  block->next_free = *free_list;
125  *free_list = block;
126}
127
128
129
130/* ==================================================================== */
131/* Mapping offsets in the target streem to txdelta ops. */
132
133typedef struct offset_index_t
134{
135  int length;
136  apr_size_t *offs;
137} offset_index_t;
138
139/* Create an index mapping target stream offsets to delta ops in
140   WINDOW. Allocate from POOL. */
141
142static offset_index_t *
143create_offset_index(const svn_txdelta_window_t *window, apr_pool_t *pool)
144{
145  offset_index_t *ndx = apr_palloc(pool, sizeof(*ndx));
146  apr_size_t offset = 0;
147  int i;
148
149  ndx->length = window->num_ops;
150  ndx->offs = apr_palloc(pool, (ndx->length + 1) * sizeof(*ndx->offs));
151
152  for (i = 0; i < ndx->length; ++i)
153    {
154      ndx->offs[i] = offset;
155      offset += window->ops[i].length;
156    }
157  ndx->offs[ndx->length] = offset;
158
159  return ndx;
160}
161
162/* Find the index of the delta op thet defines that data at OFFSET in
163   NDX. HINT is an arbitrary positin within NDX and doesn't even need
164   to be valid. To effectively speed up the search, use the last result
165   as hint because most lookups come as a sequence of decreasing values
166   for OFFSET and they concentrate on the lower end of the array. */
167
168static apr_size_t
169search_offset_index(const offset_index_t *ndx,
170                    apr_size_t offset,
171                    apr_size_t hint)
172{
173  apr_size_t lo, hi, op;
174
175  assert(offset < ndx->offs[ndx->length]);
176
177  lo = 0;
178  hi = ndx->length;
179
180  /* If we got a valid hint, use it to reduce the range to cover.
181     Note that this will only be useful if either the hint is a
182     hit (i.e. equals the desired result) or narrows the range
183     length by a factor larger than 2. */
184
185  if (hint < hi)
186    {
187      if (offset < ndx->offs[hint])
188        hi = hint;
189      else if (offset < ndx->offs[hint+1])
190        return hint;
191      else
192        lo = hint+1;
193    }
194
195  /* ordinary binary search */
196
197  for (op = (lo + hi)/2; lo != hi; op = (lo + hi)/2)
198    {
199      if (offset < ndx->offs[op])
200        hi = op;
201      else
202        lo = ++op;
203    }
204
205  --lo;
206  assert(ndx->offs[lo] <= offset && offset < ndx->offs[lo + 1]);
207  return lo;
208}
209
210
211
212/* ==================================================================== */
213/* Mapping ranges in the source stream to ranges in the composed delta. */
214
215/* The range index tree. */
216typedef struct range_index_t
217{
218  range_index_node_t *tree;
219  alloc_block_t *free_list;
220  apr_pool_t *pool;
221} range_index_t;
222
223/* Create a range index tree. Allocate from POOL. */
224static range_index_t *
225create_range_index(apr_pool_t *pool)
226{
227  range_index_t *ndx = apr_palloc(pool, sizeof(*ndx));
228  ndx->tree = NULL;
229  ndx->pool = pool;
230  ndx->free_list = NULL;
231  return ndx;
232}
233
234/* Allocate a node for the range index tree. */
235static range_index_node_t *
236alloc_range_index_node(range_index_t *ndx,
237                       apr_size_t offset,
238                       apr_size_t limit,
239                       apr_size_t target_offset)
240{
241  range_index_node_t *const node = alloc_block(ndx->pool, &ndx->free_list);
242  node->offset = offset;
243  node->limit = limit;
244  node->target_offset = target_offset;
245  node->left = node->right = NULL;
246  node->prev = node->next = NULL;
247  return node;
248}
249
250/* Free a node from the range index tree. */
251static void
252free_range_index_node(range_index_t *ndx, range_index_node_t *node)
253{
254  if (node->next)
255    node->next->prev = node->prev;
256  if (node->prev)
257    node->prev->next = node->next;
258  free_block(node, &ndx->free_list);
259}
260
261
262/* Splay the index tree, using OFFSET as the key. */
263
264static void
265splay_range_index(apr_size_t offset, range_index_t *ndx)
266{
267  range_index_node_t *tree = ndx->tree;
268  range_index_node_t scratch_node;
269  range_index_node_t *left, *right;
270
271  if (tree == NULL)
272    return;
273
274  scratch_node.left = scratch_node.right = NULL;
275  left = right = &scratch_node;
276
277  for (;;)
278    {
279      if (offset < tree->offset)
280        {
281          if (tree->left != NULL
282              && offset < tree->left->offset)
283            {
284              /* Right rotation */
285              range_index_node_t *const node = tree->left;
286              tree->left = node->right;
287              node->right = tree;
288              tree = node;
289            }
290          if (tree->left == NULL)
291            break;
292
293          /* Remember the right subtree */
294          right->left = tree;
295          right = tree;
296          tree = tree->left;
297        }
298      else if (offset > tree->offset)
299        {
300          if (tree->right != NULL
301              && offset > tree->right->offset)
302            {
303              /* Left rotation */
304              range_index_node_t *const node = tree->right;
305              tree->right = node->left;
306              node->left = tree;
307              tree = node;
308            }
309          if (tree->right == NULL)
310            break;
311
312          /* Remember the left subtree */
313          left->right = tree;
314          left = tree;
315          tree = tree->right;
316        }
317      else
318        break;
319    }
320
321  /* Link in the left and right subtrees */
322  left->right = tree->left;
323  right->left = tree->right;
324  tree->left  = scratch_node.right;
325  tree->right = scratch_node.left;
326
327  /* The basic top-down splay is finished, but we may still need to
328     turn the tree around. What we want is to put the node with the
329     largest offset where node->offset <= offset at the top of the
330     tree, so that we can insert the new data (or search for existing
331     ranges) to the right of the root. This makes cleaning up the
332     tree after an insert much simpler, and -- incidentally -- makes
333     the whole range index magic work. */
334  if (offset < tree->offset && tree->left != NULL)
335    {
336      if (tree->left->right == NULL)
337        {
338          /* A single right rotation is enough. */
339          range_index_node_t *const node = tree->left;
340          tree->left = node->right; /* Which is always NULL. */
341          node->right = tree;
342          tree = node;
343        }
344      else
345        {
346          /* Slide down to the rightmost node in the left subtree. */
347          range_index_node_t **nodep = &tree->left;
348          while ((*nodep)->right != NULL)
349            nodep = &(*nodep)->right;
350
351          /* Now move this node to root in one giant promotion. */
352          right = tree;
353          left = tree->left;
354          tree = *nodep;
355          *nodep = tree->left;
356          right->left = tree->right; /* Which is always NULL, too. */
357          tree->left = left;
358          tree->right = right;
359        }
360    }
361
362  /* Sanity check ... */
363  assert((offset >= tree->offset)
364         || ((tree->left == NULL)
365             && (tree->prev == NULL)));
366  ndx->tree = tree;
367}
368
369
370/* Remove all ranges from NDX that fall into the root's range.  To
371   keep the range index as small as possible, we must also remove
372   nodes that don't fall into the new range, but have become redundant
373   because the new range overlaps the beginning of the next range.
374   Like this:
375
376       new-range: |-----------------|
377         range-1:         |-----------------|
378         range-2:                |--------------------|
379
380   Before new-range was inserted, range-1 and range-2 were both
381   necessary. Now the union of new-range and range-2 completely covers
382   range-1, which has become redundant now.
383
384   FIXME: But, of course, there's a catch. range-1 must still remain
385   in the tree if we want to optimize the number of target copy ops in
386   the case were a copy falls within range-1, but starts before
387   range-2 and ends after new-range. */
388
389static void
390delete_subtree(range_index_t *ndx, range_index_node_t *node)
391{
392  if (node != NULL)
393    {
394      delete_subtree(ndx, node->left);
395      delete_subtree(ndx, node->right);
396      free_range_index_node(ndx, node);
397    }
398}
399
400static void
401clean_tree(range_index_t *ndx, apr_size_t limit)
402{
403  apr_size_t top_offset = limit + 1;
404  range_index_node_t **nodep = &ndx->tree->right;
405  while (*nodep != NULL)
406    {
407      range_index_node_t *const node = *nodep;
408      apr_size_t const offset =
409        (node->right != NULL && node->right->offset < top_offset
410         ? node->right->offset
411         : top_offset);
412
413      if (node->limit <= limit
414          || (node->offset < limit && offset < limit))
415        {
416          *nodep = node->right;
417          node->right = NULL;
418          delete_subtree(ndx, node);
419        }
420      else
421        {
422          top_offset = node->offset;
423          nodep = &node->left;
424        }
425    }
426}
427
428
429/* Add a range [OFFSET, LIMIT) into NDX. If NDX already contains a
430   range that encloses [OFFSET, LIMIT), do nothing. Otherwise, remove
431   all ranges from NDX that are superseded by the new range.
432   NOTE: The range index must be splayed to OFFSET! */
433
434static void
435insert_range(apr_size_t offset, apr_size_t limit, apr_size_t target_offset,
436             range_index_t *ndx)
437{
438  range_index_node_t *node = NULL;
439
440  if (ndx->tree == NULL)
441    {
442      node = alloc_range_index_node(ndx, offset, limit, target_offset);
443      ndx->tree = node;
444    }
445  else
446    {
447      if (offset == ndx->tree->offset
448          && limit > ndx->tree->limit)
449        {
450          ndx->tree->limit = limit;
451          ndx->tree->target_offset = target_offset;
452          clean_tree(ndx, limit);
453        }
454      else if (offset > ndx->tree->offset
455               && limit > ndx->tree->limit)
456        {
457          /* We have to make the same sort of checks as clean_tree()
458             does for superseded ranges. Have to merge these someday. */
459
460          const svn_boolean_t insert_range_p =
461            (!ndx->tree->next
462             || ndx->tree->limit < ndx->tree->next->offset
463             || limit > ndx->tree->next->limit);
464
465          if (insert_range_p)
466            {
467              /* Again, we have to check if the new node and the one
468                 to the left of the root override root's range. */
469              if (ndx->tree->prev && ndx->tree->prev->limit > offset)
470                {
471                  /* Replace the data in the splayed node. */
472                  ndx->tree->offset = offset;
473                  ndx->tree->limit = limit;
474                  ndx->tree->target_offset = target_offset;
475                }
476              else
477                {
478                  /* Insert the range to the right of the splayed node. */
479                  node = alloc_range_index_node(ndx, offset, limit,
480                                                target_offset);
481                  if ((node->next = ndx->tree->next) != NULL)
482                    node->next->prev = node;
483                  ndx->tree->next = node;
484                  node->prev = ndx->tree;
485
486                  node->right = ndx->tree->right;
487                  ndx->tree->right = NULL;
488                  node->left = ndx->tree;
489                  ndx->tree = node;
490                }
491              clean_tree(ndx, limit);
492            }
493          else
494            /* Ignore the range */;
495        }
496      else if (offset < ndx->tree->offset)
497        {
498          assert(ndx->tree->left == NULL);
499
500          /* Insert the range left of the splayed node */
501          node = alloc_range_index_node(ndx, offset, limit, target_offset);
502          node->left = node->prev = NULL;
503          node->right = node->next = ndx->tree;
504          ndx->tree = node->next->prev = node;
505          clean_tree(ndx, limit);
506        }
507      else
508        /* Ignore the range */;
509    }
510}
511
512
513
514/* ==================================================================== */
515/* Juggling with lists of ranges. */
516
517/* Allocate a node and add it to the range list. LIST is the head of
518   the range list, TAIL is the last node in the list. NDX holds the
519   freelist; OFFSET, LIMIT and KIND are node data. */
520static range_list_node_t *
521alloc_range_list(range_list_node_t **list,
522                 range_list_node_t **tail,
523                 range_index_t *ndx,
524                 enum range_kind kind,
525                 apr_size_t offset,
526                 apr_size_t limit,
527                 apr_size_t target_offset)
528{
529  range_list_node_t *const node = alloc_block(ndx->pool, &ndx->free_list);
530  node->kind = kind;
531  node->offset = offset;
532  node->limit = limit;
533  node->target_offset = target_offset;
534  if (*list == NULL)
535    {
536      node->prev = node->next = NULL;
537      *list = *tail = node;
538    }
539  else
540    {
541      node->prev = *tail;
542      node->next = NULL;
543      (*tail)->next = node;
544      *tail = node;
545    }
546  return *list;
547}
548
549/* Free a range list. LIST is the head of the list, NDX holds the freelist. */
550static void
551free_range_list(range_list_node_t *list, range_index_t *ndx)
552{
553  while (list)
554    {
555      range_list_node_t *const node = list;
556      list = node->next;
557      free_block(node, &ndx->free_list);
558    }
559}
560
561
562/* Based on the data in NDX, build a list of ranges that cover
563   [OFFSET, LIMIT) in the "virtual" source data.
564   NOTE: The range index must be splayed to OFFSET! */
565
566static range_list_node_t *
567build_range_list(apr_size_t offset, apr_size_t limit, range_index_t *ndx)
568{
569  range_list_node_t *range_list = NULL;
570  range_list_node_t *last_range = NULL;
571  range_index_node_t *node = ndx->tree;
572
573  while (offset < limit)
574    {
575      if (node == NULL)
576        return alloc_range_list(&range_list, &last_range, ndx,
577                                range_from_source,
578                                offset, limit, 0);
579
580      if (offset < node->offset)
581        {
582          if (limit <= node->offset)
583            return alloc_range_list(&range_list, &last_range, ndx,
584                                    range_from_source,
585                                    offset, limit, 0);
586          else
587            {
588              alloc_range_list(&range_list, &last_range, ndx,
589                               range_from_source,
590                               offset, node->offset, 0);
591              offset = node->offset;
592            }
593        }
594      else
595        {
596          /* TODO: (Potential optimization) Investigate if it would
597             make sense to forbid short range_from_target lengths
598             (this comment originally said "shorter than, say,
599             VD_KEY_SIZE (see vdelta.c)", but Subversion no longer
600             uses vdelta). */
601
602          if (offset >= node->limit)
603            node = node->next;
604          else
605            {
606              const apr_size_t target_offset =
607                offset - node->offset + node->target_offset;
608
609              if (limit <= node->limit)
610                return alloc_range_list(&range_list, &last_range, ndx,
611                                        range_from_target,
612                                        offset, limit, target_offset);
613              else
614                {
615                  alloc_range_list(&range_list, &last_range, ndx,
616                                   range_from_target,
617                                   offset, node->limit, target_offset);
618                  offset = node->limit;
619                  node = node->next;
620                }
621            }
622        }
623    }
624
625  /* A range's offset isn't smaller than its limit? Impossible! */
626  SVN_ERR_MALFUNCTION_NO_RETURN();
627}
628
629
630/* Copy the instructions from WINDOW that define the range [OFFSET,
631   LIMIT) in WINDOW's target stream to TARGET_OFFSET in the window
632   represented by BUILD_BATON. HINT is a position in the instructions
633   array that helps finding the position for OFFSET. A safe default
634   is 0. Use NDX to find the instructions in WINDOW. Allocate space
635   in BUILD_BATON from POOL. */
636
637static void
638copy_source_ops(apr_size_t offset, apr_size_t limit,
639                apr_size_t target_offset,
640                apr_size_t hint,
641                svn_txdelta__ops_baton_t *build_baton,
642                const svn_txdelta_window_t *window,
643                const offset_index_t *ndx,
644                apr_pool_t *pool)
645{
646  apr_size_t op_ndx = search_offset_index(ndx, offset, hint);
647  for (;; ++op_ndx)
648    {
649      const svn_txdelta_op_t *const op = &window->ops[op_ndx];
650      const apr_size_t *const off = &ndx->offs[op_ndx];
651      apr_size_t fix_offset;
652      apr_size_t fix_limit;
653
654      if (off[0] >= limit)
655          break;
656
657      fix_offset = (offset > off[0] ? offset - off[0] : 0);
658      fix_limit = (off[1] > limit ? off[1] - limit : 0);
659
660      /* It would be extremely weird if the fixed-up op had zero length. */
661      assert(fix_offset + fix_limit < op->length);
662
663      if (op->action_code != svn_txdelta_target)
664        {
665          /* Delta ops that don't depend on the virtual target can be
666             copied to the composite unchanged. */
667          const char *const new_data = (op->action_code == svn_txdelta_new
668                                        ? (window->new_data->data
669                                           + op->offset + fix_offset)
670                                        : NULL);
671
672          svn_txdelta__insert_op(build_baton, op->action_code,
673                                 op->offset + fix_offset,
674                                 op->length - fix_offset - fix_limit,
675                                 new_data, pool);
676        }
677      else
678        {
679          /* The source of a target copy must start before the current
680             offset in the (virtual) target stream. */
681          assert(op->offset < off[0]);
682
683          if (op->offset + op->length - fix_limit <= off[0])
684            {
685              /* The recursion _must_ end, otherwise the delta has
686                 circular references, and that is not possible. */
687              copy_source_ops(op->offset + fix_offset,
688                              op->offset + op->length - fix_limit,
689                              target_offset,
690                              op_ndx,
691                              build_baton, window, ndx, pool);
692            }
693          else
694            {
695              /* This is an overlapping target copy.
696                 The idea here is to transpose the pattern, then generate
697                 another overlapping copy. */
698              const apr_size_t ptn_length = off[0] - op->offset;
699              const apr_size_t ptn_overlap = fix_offset % ptn_length;
700              apr_size_t fix_off = fix_offset;
701              apr_size_t tgt_off = target_offset;
702              assert(ptn_length > ptn_overlap);
703
704              /* ### FIXME: ptn_overlap is unsigned, so the if() condition
705                 below is always true!  Either it should be '> 0', or the
706                 code block should be unconditional.  See also r842362. */
707              if (ptn_overlap >= 0)
708                {
709                  /* Issue second subrange in the pattern. */
710                  const apr_size_t length =
711                    MIN(op->length - fix_off - fix_limit,
712                        ptn_length - ptn_overlap);
713                  copy_source_ops(op->offset + ptn_overlap,
714                                  op->offset + ptn_overlap + length,
715                                  tgt_off,
716                                  op_ndx,
717                                  build_baton, window, ndx, pool);
718                  fix_off += length;
719                  tgt_off += length;
720                }
721
722              assert(fix_off + fix_limit <= op->length);
723              if (ptn_overlap > 0
724                  && fix_off + fix_limit < op->length)
725                {
726                  /* Issue the first subrange in the pattern. */
727                  const apr_size_t length =
728                    MIN(op->length - fix_off - fix_limit, ptn_overlap);
729                  copy_source_ops(op->offset,
730                                  op->offset + length,
731                                  tgt_off,
732                                  op_ndx,
733                                  build_baton, window, ndx, pool);
734                  fix_off += length;
735                  tgt_off += length;
736                }
737
738              assert(fix_off + fix_limit <= op->length);
739              if (fix_off + fix_limit < op->length)
740                {
741                  /* Now multiply the pattern */
742                  svn_txdelta__insert_op(build_baton, svn_txdelta_target,
743                                         tgt_off - ptn_length,
744                                         op->length - fix_off - fix_limit,
745                                         NULL, pool);
746                }
747            }
748        }
749
750      /* Adjust the target offset for the next op in the list. */
751      target_offset += op->length - fix_offset - fix_limit;
752    }
753}
754
755
756
757/* ==================================================================== */
758/* Bringing it all together. */
759
760
761svn_txdelta_window_t *
762svn_txdelta_compose_windows(const svn_txdelta_window_t *window_A,
763                            const svn_txdelta_window_t *window_B,
764                            apr_pool_t *pool)
765{
766  svn_txdelta__ops_baton_t build_baton = { 0 };
767  svn_txdelta_window_t *composite;
768  apr_pool_t *subpool = svn_pool_create(pool);
769  offset_index_t *offset_index = create_offset_index(window_A, subpool);
770  range_index_t *range_index = create_range_index(subpool);
771  apr_size_t target_offset = 0;
772  int i;
773
774  /* Read the description of the delta composition algorithm in
775     notes/fs-improvements.txt before going any further.
776     You have been warned. */
777  build_baton.new_data = svn_stringbuf_create_empty(pool);
778  for (i = 0; i < window_B->num_ops; ++i)
779    {
780      const svn_txdelta_op_t *const op = &window_B->ops[i];
781      if (op->action_code != svn_txdelta_source)
782        {
783          /* Delta ops that don't depend on the source can be copied
784             to the composite unchanged. */
785          const char *const new_data =
786            (op->action_code == svn_txdelta_new
787             ? window_B->new_data->data + op->offset
788             : NULL);
789          svn_txdelta__insert_op(&build_baton, op->action_code,
790                                 op->offset, op->length,
791                                 new_data, pool);
792        }
793      else
794        {
795          /* NOTE: Remember that `offset' and `limit' refer to
796             positions in window_B's _source_ stream, which is the
797             same as window_A's _target_ stream! */
798          const apr_size_t offset = op->offset;
799          const apr_size_t limit = op->offset + op->length;
800          range_list_node_t *range_list, *range;
801          apr_size_t tgt_off = target_offset;
802
803          splay_range_index(offset, range_index);
804          range_list = build_range_list(offset, limit, range_index);
805
806          for (range = range_list; range; range = range->next)
807            {
808              if (range->kind == range_from_target)
809                svn_txdelta__insert_op(&build_baton, svn_txdelta_target,
810                                       range->target_offset,
811                                       range->limit - range->offset,
812                                       NULL, pool);
813              else
814                copy_source_ops(range->offset, range->limit, tgt_off, 0,
815                                &build_baton, window_A, offset_index,
816                                pool);
817
818              tgt_off += range->limit - range->offset;
819            }
820          assert(tgt_off == target_offset + op->length);
821
822          free_range_list(range_list, range_index);
823          insert_range(offset, limit, target_offset, range_index);
824        }
825
826      /* Remember the new offset in the would-be target stream. */
827      target_offset += op->length;
828    }
829
830  svn_pool_destroy(subpool);
831
832  composite = svn_txdelta__make_window(&build_baton, pool);
833  composite->sview_offset = window_A->sview_offset;
834  composite->sview_len = window_A->sview_len;
835  composite->tview_len = window_B->tview_len;
836  return composite;
837}
838