1/* tree.c : tree-like filesystem, built on DAG filesystem
2 *
3 * ====================================================================
4 *    Licensed to the Apache Software Foundation (ASF) under one
5 *    or more contributor license agreements.  See the NOTICE file
6 *    distributed with this work for additional information
7 *    regarding copyright ownership.  The ASF licenses this file
8 *    to you under the Apache License, Version 2.0 (the
9 *    "License"); you may not use this file except in compliance
10 *    with the License.  You may obtain a copy of the License at
11 *
12 *      http://www.apache.org/licenses/LICENSE-2.0
13 *
14 *    Unless required by applicable law or agreed to in writing,
15 *    software distributed under the License is distributed on an
16 *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17 *    KIND, either express or implied.  See the License for the
18 *    specific language governing permissions and limitations
19 *    under the License.
20 * ====================================================================
21 */
22
23
24/* The job of this layer is to take a filesystem with lots of node
25   sharing going on --- the real DAG filesystem as it appears in the
26   database --- and make it look and act like an ordinary tree
27   filesystem, with no sharing.
28
29   We do just-in-time cloning: you can walk from some unfinished
30   transaction's root down into directories and files shared with
31   committed revisions; as soon as you try to change something, the
32   appropriate nodes get cloned (and parent directory entries updated)
33   invisibly, behind your back.  Any other references you have to
34   nodes that have been cloned by other changes, even made by other
35   processes, are automatically updated to point to the right clones.  */
36
37
38#include <stdlib.h>
39#include <string.h>
40#include <assert.h>
41#include <apr_pools.h>
42#include <apr_hash.h>
43
44#include "svn_hash.h"
45#include "svn_private_config.h"
46#include "svn_pools.h"
47#include "svn_error.h"
48#include "svn_path.h"
49#include "svn_mergeinfo.h"
50#include "svn_fs.h"
51#include "svn_props.h"
52#include "svn_sorts.h"
53
54#include "fs.h"
55#include "dag.h"
56#include "dag_cache.h"
57#include "lock.h"
58#include "tree.h"
59#include "fs_x.h"
60#include "fs_id.h"
61#include "temp_serializer.h"
62#include "cached_data.h"
63#include "transaction.h"
64#include "pack.h"
65#include "util.h"
66
67#include "private/svn_mergeinfo_private.h"
68#include "private/svn_subr_private.h"
69#include "private/svn_fs_util.h"
70#include "private/svn_fspath.h"
71#include "../libsvn_fs/fs-loader.h"
72
73
74
75/* The root structures.
76
77   Why do they contain different data?  Well, transactions are mutable
78   enough that it isn't safe to cache the DAG node for the root
79   directory or the hash of copyfrom data: somebody else might modify
80   them concurrently on disk!  (Why is the DAG node cache safer than
81   the root DAG node?  When cloning transaction DAG nodes in and out
82   of the cache, all of the possibly-mutable data from the
83   svn_fs_x__noderev_t inside the dag_node_t is dropped.)  Additionally,
84   revisions are immutable enough that their DAG node cache can be
85   kept in the FS object and shared among multiple revision root
86   objects.
87*/
88typedef dag_node_t fs_rev_root_data_t;
89
90typedef struct fs_txn_root_data_t
91{
92  /* TXN_ID value from the main struct but as a struct instead of a string */
93  svn_fs_x__txn_id_t txn_id;
94} fs_txn_root_data_t;
95
96static svn_fs_root_t *
97make_revision_root(svn_fs_t *fs,
98                   svn_revnum_t rev,
99                   apr_pool_t *result_pool);
100
101static svn_error_t *
102make_txn_root(svn_fs_root_t **root_p,
103              svn_fs_t *fs,
104              svn_fs_x__txn_id_t txn_id,
105              svn_revnum_t base_rev,
106              apr_uint32_t flags,
107              apr_pool_t *result_pool);
108
109static svn_error_t *
110x_closest_copy(svn_fs_root_t **root_p,
111               const char **path_p,
112               svn_fs_root_t *root,
113               const char *path,
114               apr_pool_t *pool);
115
116
117/* Creating transaction and revision root nodes.  */
118
119svn_error_t *
120svn_fs_x__txn_root(svn_fs_root_t **root_p,
121                   svn_fs_txn_t *txn,
122                   apr_pool_t *pool)
123{
124  apr_uint32_t flags = 0;
125  apr_hash_t *txnprops;
126
127  /* Look for the temporary txn props representing 'flags'. */
128  SVN_ERR(svn_fs_x__txn_proplist(&txnprops, txn, pool));
129  if (txnprops)
130    {
131      if (svn_hash_gets(txnprops, SVN_FS__PROP_TXN_CHECK_OOD))
132        flags |= SVN_FS_TXN_CHECK_OOD;
133
134      if (svn_hash_gets(txnprops, SVN_FS__PROP_TXN_CHECK_LOCKS))
135        flags |= SVN_FS_TXN_CHECK_LOCKS;
136    }
137
138  return make_txn_root(root_p, txn->fs, svn_fs_x__txn_get_id(txn),
139                       txn->base_rev, flags, pool);
140}
141
142
143svn_error_t *
144svn_fs_x__revision_root(svn_fs_root_t **root_p,
145                        svn_fs_t *fs,
146                        svn_revnum_t rev,
147                        apr_pool_t *pool)
148{
149  SVN_ERR(svn_fs__check_fs(fs, TRUE));
150  SVN_ERR(svn_fs_x__ensure_revision_exists(rev, fs, pool));
151
152  *root_p = make_revision_root(fs, rev, pool);
153
154  return SVN_NO_ERROR;
155}
156
157
158
159/* Getting dag nodes for roots.  */
160
161/* Return the transaction ID to a given transaction ROOT. */
162svn_fs_x__txn_id_t
163svn_fs_x__root_txn_id(svn_fs_root_t *root)
164{
165  fs_txn_root_data_t *frd = root->fsap_data;
166  assert(root->is_txn_root);
167
168  return frd->txn_id;
169}
170
171/* Return the change set to a given ROOT. */
172svn_fs_x__change_set_t
173svn_fs_x__root_change_set(svn_fs_root_t *root)
174{
175  if (root->is_txn_root)
176    return svn_fs_x__change_set_by_txn(svn_fs_x__root_txn_id(root));
177
178  return svn_fs_x__change_set_by_rev(root->rev);
179}
180
181
182
183
184/* Traversing directory paths.  */
185
186/* Return a text string describing the absolute path of parent path
187   DAG_PATH.  It will be allocated in POOL. */
188static const char *
189parent_path_path(svn_fs_x__dag_path_t *dag_path,
190                 apr_pool_t *pool)
191{
192  const char *path_so_far = "/";
193  if (dag_path->parent)
194    path_so_far = parent_path_path(dag_path->parent, pool);
195  return dag_path->entry
196    ? svn_fspath__join(path_so_far, dag_path->entry, pool)
197    : path_so_far;
198}
199
200
201/* Return the FS path for the parent path chain object CHILD relative
202   to its ANCESTOR in the same chain, allocated in POOL.  */
203static const char *
204parent_path_relpath(svn_fs_x__dag_path_t *child,
205                    svn_fs_x__dag_path_t *ancestor,
206                    apr_pool_t *pool)
207{
208  const char *path_so_far = "";
209  svn_fs_x__dag_path_t *this_node = child;
210  while (this_node != ancestor)
211    {
212      assert(this_node != NULL);
213      path_so_far = svn_relpath_join(this_node->entry, path_so_far, pool);
214      this_node = this_node->parent;
215    }
216  return path_so_far;
217}
218
219
220
221
222
223/* Populating the `changes' table. */
224
225/* Add a change to the changes table in FS, keyed on transaction id
226   TXN_ID, and indicated that a change of kind CHANGE_KIND occurred on
227   PATH, and optionally that TEXT_MODs, PROP_MODs or MERGEINFO_MODs
228   occurred.  If the change resulted from a copy, COPYFROM_REV and
229   COPYFROM_PATH specify under which revision and path the node was
230   copied from.  If this was not part of a copy, COPYFROM_REV should
231   be SVN_INVALID_REVNUM.  Use SCRATCH_POOL for temporary allocations.
232 */
233static svn_error_t *
234add_change(svn_fs_t *fs,
235           svn_fs_x__txn_id_t txn_id,
236           const char *path,
237           svn_fs_path_change_kind_t change_kind,
238           svn_boolean_t text_mod,
239           svn_boolean_t prop_mod,
240           svn_boolean_t mergeinfo_mod,
241           svn_node_kind_t node_kind,
242           svn_revnum_t copyfrom_rev,
243           const char *copyfrom_path,
244           apr_pool_t *scratch_pool)
245{
246  return svn_fs_x__add_change(fs, txn_id,
247                              svn_fs__canonicalize_abspath(path,
248                                                           scratch_pool),
249                              change_kind, text_mod, prop_mod, mergeinfo_mod,
250                              node_kind, copyfrom_rev, copyfrom_path,
251                              scratch_pool);
252}
253
254
255
256/* Generic node operations.  */
257
258/* Get the id of a node referenced by path PATH in ROOT.  Return the
259   id in *ID_P allocated in POOL. */
260static svn_error_t *
261x_node_id(const svn_fs_id_t **id_p,
262          svn_fs_root_t *root,
263          const char *path,
264          apr_pool_t *pool)
265{
266  svn_fs_x__id_t noderev_id;
267
268  if ((! root->is_txn_root)
269      && (path[0] == '\0' || ((path[0] == '/') && (path[1] == '\0'))))
270    {
271      /* Optimize the case where we don't need any db access at all.
272         The root directory ("" or "/") node is stored in the
273         svn_fs_root_t object, and never changes when it's a revision
274         root, so we can just reach in and grab it directly. */
275      svn_fs_x__init_rev_root(&noderev_id, root->rev);
276    }
277  else
278    {
279      apr_pool_t *scratch_pool = svn_pool_create(pool);
280      dag_node_t *node;
281
282      SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root, path, scratch_pool));
283      noderev_id = *svn_fs_x__dag_get_id(node);
284      svn_pool_destroy(scratch_pool);
285    }
286
287  *id_p = svn_fs_x__id_create(svn_fs_x__id_create_context(root->fs, pool),
288                              &noderev_id, pool);
289
290  return SVN_NO_ERROR;
291}
292
293static svn_error_t *
294x_node_relation(svn_fs_node_relation_t *relation,
295                svn_fs_root_t *root_a,
296                const char *path_a,
297                svn_fs_root_t *root_b,
298                const char *path_b,
299                apr_pool_t *scratch_pool)
300{
301  dag_node_t *node;
302  svn_fs_x__id_t noderev_id_a, noderev_id_b, node_id_a, node_id_b;
303
304  /* Root paths are a common special case. */
305  svn_boolean_t a_is_root_dir
306    = (path_a[0] == '\0') || ((path_a[0] == '/') && (path_a[1] == '\0'));
307  svn_boolean_t b_is_root_dir
308    = (path_b[0] == '\0') || ((path_b[0] == '/') && (path_b[1] == '\0'));
309
310  /* Path from different repository are always unrelated. */
311  if (root_a->fs != root_b->fs)
312    {
313      *relation = svn_fs_node_unrelated;
314      return SVN_NO_ERROR;
315    }
316
317  /* Are both (!) root paths? Then, they are related and we only test how
318   * direct the relation is. */
319  if (a_is_root_dir && b_is_root_dir)
320    {
321      svn_boolean_t different_txn
322        = root_a->is_txn_root && root_b->is_txn_root
323            && strcmp(root_a->txn, root_b->txn);
324
325      /* For txn roots, root->REV is the base revision of that TXN. */
326      *relation = (   (root_a->rev == root_b->rev)
327                   && (root_a->is_txn_root == root_b->is_txn_root)
328                   && !different_txn)
329                ? svn_fs_node_unchanged
330                : svn_fs_node_common_ancestor;
331      return SVN_NO_ERROR;
332    }
333
334  /* We checked for all separations between ID spaces (repos, txn).
335   * Now, we can simply test for the ID values themselves. */
336  SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root_a, path_a, scratch_pool));
337  noderev_id_a = *svn_fs_x__dag_get_id(node);
338  node_id_a = *svn_fs_x__dag_get_node_id(node);
339
340  SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root_b, path_b, scratch_pool));
341  noderev_id_b = *svn_fs_x__dag_get_id(node);
342  node_id_b = *svn_fs_x__dag_get_node_id(node);
343
344  /* In FSX, even in-txn IDs are globally unique.
345   * So, we can simply compare them. */
346  if (svn_fs_x__id_eq(&noderev_id_a, &noderev_id_b))
347    *relation = svn_fs_node_unchanged;
348  else if (svn_fs_x__id_eq(&node_id_a, &node_id_b))
349    *relation = svn_fs_node_common_ancestor;
350  else
351    *relation = svn_fs_node_unrelated;
352
353  return SVN_NO_ERROR;
354}
355
356svn_error_t *
357svn_fs_x__node_created_rev(svn_revnum_t *revision,
358                           svn_fs_root_t *root,
359                           const char *path,
360                           apr_pool_t *scratch_pool)
361{
362  dag_node_t *node;
363
364  SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root, path, scratch_pool));
365  *revision = svn_fs_x__dag_get_revision(node);
366
367  return SVN_NO_ERROR;
368}
369
370
371/* Set *CREATED_PATH to the path at which PATH under ROOT was created.
372   Return a string allocated in POOL. */
373static svn_error_t *
374x_node_created_path(const char **created_path,
375                    svn_fs_root_t *root,
376                    const char *path,
377                    apr_pool_t *pool)
378{
379  dag_node_t *node;
380
381  SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root, path, pool));
382  *created_path = apr_pstrdup(pool, svn_fs_x__dag_get_created_path(node));
383
384  return SVN_NO_ERROR;
385}
386
387
388/* Set *KIND_P to the type of node present at PATH under ROOT.  If
389   PATH does not exist under ROOT, set *KIND_P to svn_node_none.  Use
390   SCRATCH_POOL for temporary allocation. */
391svn_error_t *
392svn_fs_x__check_path(svn_node_kind_t *kind_p,
393                     svn_fs_root_t *root,
394                     const char *path,
395                     apr_pool_t *scratch_pool)
396{
397  dag_node_t *node;
398
399  /* Get the node id. */
400  svn_error_t *err = svn_fs_x__get_temp_dag_node(&node, root, path,
401                                                 scratch_pool);
402
403  /* Use the node id to get the real kind. */
404  if (!err)
405    *kind_p = svn_fs_x__dag_node_kind(node);
406
407  if (err &&
408      ((err->apr_err == SVN_ERR_FS_NOT_FOUND)
409       || (err->apr_err == SVN_ERR_FS_NOT_DIRECTORY)))
410    {
411      svn_error_clear(err);
412      err = SVN_NO_ERROR;
413      *kind_p = svn_node_none;
414    }
415
416  return svn_error_trace(err);
417}
418
419/* Set *VALUE_P to the value of the property named PROPNAME of PATH in
420   ROOT.  If the node has no property by that name, set *VALUE_P to
421   zero.  Allocate the result in POOL. */
422static svn_error_t *
423x_node_prop(svn_string_t **value_p,
424            svn_fs_root_t *root,
425            const char *path,
426            const char *propname,
427            apr_pool_t *pool)
428{
429  dag_node_t *node;
430  apr_hash_t *proplist;
431  apr_pool_t *scratch_pool = svn_pool_create(pool);
432
433  SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root, path, scratch_pool));
434  SVN_ERR(svn_fs_x__dag_get_proplist(&proplist, node, scratch_pool,
435                                     scratch_pool));
436  *value_p = NULL;
437  if (proplist)
438    *value_p = svn_string_dup(svn_hash_gets(proplist, propname), pool);
439
440  svn_pool_destroy(scratch_pool);
441  return SVN_NO_ERROR;
442}
443
444
445/* Set *TABLE_P to the entire property list of PATH under ROOT, as an
446   APR hash table allocated in POOL.  The resulting property table
447   maps property names to pointers to svn_string_t objects containing
448   the property value. */
449static svn_error_t *
450x_node_proplist(apr_hash_t **table_p,
451                svn_fs_root_t *root,
452                const char *path,
453                apr_pool_t *pool)
454{
455  dag_node_t *node;
456  apr_pool_t *scratch_pool = svn_pool_create(pool);
457
458  SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root, path, scratch_pool));
459  SVN_ERR(svn_fs_x__dag_get_proplist(table_p, node, pool, scratch_pool));
460
461  svn_pool_destroy(scratch_pool);
462  return SVN_NO_ERROR;
463}
464
465static svn_error_t *
466x_node_has_props(svn_boolean_t *has_props,
467                 svn_fs_root_t *root,
468                 const char *path,
469                 apr_pool_t *scratch_pool)
470{
471  apr_hash_t *props;
472
473  SVN_ERR(x_node_proplist(&props, root, path, scratch_pool));
474
475  *has_props = (0 < apr_hash_count(props));
476
477  return SVN_NO_ERROR;
478}
479
480static svn_error_t *
481increment_mergeinfo_up_tree(svn_fs_x__dag_path_t *pp,
482                            apr_int64_t increment,
483                            apr_pool_t *scratch_pool)
484{
485  apr_pool_t *iterpool = svn_pool_create(scratch_pool);
486
487  for (; pp; pp = pp->parent)
488    {
489      svn_pool_clear(iterpool);
490      SVN_ERR(svn_fs_x__dag_increment_mergeinfo_count(pp->node,
491                                                      increment,
492                                                      iterpool));
493    }
494
495  svn_pool_destroy(iterpool);
496  return SVN_NO_ERROR;
497}
498
499/* Change, add, or delete a node's property value.  The affected node
500   is PATH under ROOT, the property value to modify is NAME, and VALUE
501   points to either a string value to set the new contents to, or NULL
502   if the property should be deleted.  Perform temporary allocations
503   in SCRATCH_POOL. */
504static svn_error_t *
505x_change_node_prop(svn_fs_root_t *root,
506                   const char *path,
507                   const char *name,
508                   const svn_string_t *value,
509                   apr_pool_t *scratch_pool)
510{
511  svn_fs_x__dag_path_t *dag_path;
512  apr_hash_t *proplist;
513  svn_fs_x__txn_id_t txn_id;
514  svn_boolean_t mergeinfo_mod = FALSE;
515  apr_pool_t *subpool = svn_pool_create(scratch_pool);
516
517  if (! root->is_txn_root)
518    return SVN_FS__NOT_TXN(root);
519  txn_id = svn_fs_x__root_txn_id(root);
520
521  SVN_ERR(svn_fs_x__get_dag_path(&dag_path, root, path, 0, TRUE, subpool,
522                                 subpool));
523
524  /* Check (non-recursively) to see if path is locked; if so, check
525     that we can use it. */
526  if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
527    SVN_ERR(svn_fs_x__allow_locked_operation(path, root->fs, FALSE, FALSE,
528                                             subpool));
529
530  SVN_ERR(svn_fs_x__make_path_mutable(root, dag_path, path, subpool,
531                                      subpool));
532  SVN_ERR(svn_fs_x__dag_get_proplist(&proplist, dag_path->node, subpool,
533                                     subpool));
534
535  /* If there's no proplist, but we're just deleting a property, exit now. */
536  if ((! proplist) && (! value))
537    return SVN_NO_ERROR;
538
539  /* Now, if there's no proplist, we know we need to make one. */
540  if (! proplist)
541    proplist = apr_hash_make(subpool);
542
543  if (strcmp(name, SVN_PROP_MERGEINFO) == 0)
544    {
545      apr_int64_t increment = 0;
546      svn_boolean_t had_mergeinfo
547        = svn_fs_x__dag_has_mergeinfo(dag_path->node);
548
549      if (value && !had_mergeinfo)
550        increment = 1;
551      else if (!value && had_mergeinfo)
552        increment = -1;
553
554      if (increment != 0)
555        {
556          SVN_ERR(increment_mergeinfo_up_tree(dag_path, increment, subpool));
557          SVN_ERR(svn_fs_x__dag_set_has_mergeinfo(dag_path->node,
558                                                  (value != NULL), subpool));
559        }
560
561      mergeinfo_mod = TRUE;
562    }
563
564  /* Set the property. */
565  svn_hash_sets(proplist, name, value);
566
567  /* Overwrite the node's proplist. */
568  SVN_ERR(svn_fs_x__dag_set_proplist(dag_path->node, proplist,
569                                     subpool));
570
571  /* Make a record of this modification in the changes table. */
572  SVN_ERR(add_change(root->fs, txn_id, path,
573                     svn_fs_path_change_modify, FALSE, TRUE, mergeinfo_mod,
574                     svn_fs_x__dag_node_kind(dag_path->node),
575                     SVN_INVALID_REVNUM, NULL, subpool));
576
577  svn_pool_destroy(subpool);
578  return SVN_NO_ERROR;
579}
580
581
582/* Determine if the properties of two path/root combinations are
583   different.  Set *CHANGED_P to TRUE if the properties at PATH1 under
584   ROOT1 differ from those at PATH2 under ROOT2, or FALSE otherwise.
585   Both roots must be in the same filesystem. */
586static svn_error_t *
587x_props_changed(svn_boolean_t *changed_p,
588                svn_fs_root_t *root1,
589                const char *path1,
590                svn_fs_root_t *root2,
591                const char *path2,
592                svn_boolean_t strict,
593                apr_pool_t *scratch_pool)
594{
595  dag_node_t *node1, *node2;
596  apr_pool_t *subpool = svn_pool_create(scratch_pool);
597
598  /* Check that roots are in the same fs. */
599  if (root1->fs != root2->fs)
600    return svn_error_create
601      (SVN_ERR_FS_GENERAL, NULL,
602       _("Cannot compare property value between two different filesystems"));
603
604  SVN_ERR(svn_fs_x__get_dag_node(&node1, root1, path1, subpool, subpool));
605  SVN_ERR(svn_fs_x__get_temp_dag_node(&node2, root2, path2, subpool));
606  SVN_ERR(svn_fs_x__dag_things_different(changed_p, NULL, node1, node2,
607                                         strict, subpool));
608  svn_pool_destroy(subpool);
609
610  return SVN_NO_ERROR;
611}
612
613
614
615/* Merges and commits. */
616
617/* Set *NODE to the root node of ROOT.  */
618static svn_error_t *
619get_root(dag_node_t **node,
620         svn_fs_root_t *root,
621         apr_pool_t *result_pool,
622         apr_pool_t *scratch_pool)
623{
624  return svn_fs_x__get_dag_node(node, root, "/", result_pool, scratch_pool);
625}
626
627
628/* Set the contents of CONFLICT_PATH to PATH, and return an
629   SVN_ERR_FS_CONFLICT error that indicates that there was a conflict
630   at PATH.  Perform all allocations in POOL (except the allocation of
631   CONFLICT_PATH, which should be handled outside this function).  */
632static svn_error_t *
633conflict_err(svn_stringbuf_t *conflict_path,
634             const char *path)
635{
636  svn_stringbuf_set(conflict_path, path);
637  return svn_error_createf(SVN_ERR_FS_CONFLICT, NULL,
638                           _("Conflict at '%s'"), path);
639}
640
641/* Compare the directory representations at nodes LHS and RHS in FS and set
642 * *CHANGED to TRUE, if at least one entry has been added or removed them.
643 * Use SCRATCH_POOL for temporary allocations.
644 */
645static svn_error_t *
646compare_dir_structure(svn_boolean_t *changed,
647                      svn_fs_t *fs,
648                      dag_node_t *lhs,
649                      dag_node_t *rhs,
650                      apr_pool_t *scratch_pool)
651{
652  apr_array_header_t *lhs_entries;
653  apr_array_header_t *rhs_entries;
654  int i;
655  apr_pool_t *iterpool = svn_pool_create(scratch_pool);
656
657  SVN_ERR(svn_fs_x__dag_dir_entries(&lhs_entries, lhs, scratch_pool,
658                                    iterpool));
659  SVN_ERR(svn_fs_x__dag_dir_entries(&rhs_entries, rhs, scratch_pool,
660                                    iterpool));
661
662  /* different number of entries -> some addition / removal */
663  if (lhs_entries->nelts != rhs_entries->nelts)
664    {
665      svn_pool_destroy(iterpool);
666      *changed = TRUE;
667
668      return SVN_NO_ERROR;
669    }
670
671  /* Since directories are sorted by name, we can simply compare their
672     entries one-by-one without binary lookup etc. */
673  for (i = 0; i < lhs_entries->nelts; ++i)
674    {
675      svn_fs_x__dirent_t *lhs_entry
676        = APR_ARRAY_IDX(lhs_entries, i, svn_fs_x__dirent_t *);
677      svn_fs_x__dirent_t *rhs_entry
678        = APR_ARRAY_IDX(rhs_entries, i, svn_fs_x__dirent_t *);
679
680      if (strcmp(lhs_entry->name, rhs_entry->name) == 0)
681        {
682          dag_node_t *lhs_node, *rhs_node;
683
684          /* Unchanged entry? */
685          if (!svn_fs_x__id_eq(&lhs_entry->id, &rhs_entry->id))
686            continue;
687
688          /* We get here rarely. */
689          svn_pool_clear(iterpool);
690
691          /* Modified but not copied / replaced or anything? */
692          SVN_ERR(svn_fs_x__dag_get_node(&lhs_node, fs, &lhs_entry->id,
693                                         iterpool, iterpool));
694          SVN_ERR(svn_fs_x__dag_get_node(&rhs_node, fs, &rhs_entry->id,
695                                         iterpool, iterpool));
696          if (svn_fs_x__dag_same_line_of_history(lhs_node, rhs_node))
697            continue;
698        }
699
700      /* This is a different entry. */
701      *changed = TRUE;
702      svn_pool_destroy(iterpool);
703
704      return SVN_NO_ERROR;
705    }
706
707  svn_pool_destroy(iterpool);
708  *changed = FALSE;
709
710  return SVN_NO_ERROR;
711}
712
713/* Merge changes between ANCESTOR and SOURCE into TARGET.  ANCESTOR
714 * and TARGET must be distinct node revisions.  TARGET_PATH should
715 * correspond to TARGET's full path in its filesystem, and is used for
716 * reporting conflict location.
717 *
718 * SOURCE, TARGET, and ANCESTOR are generally directories; this
719 * function recursively merges the directories' contents.  If any are
720 * files, this function simply returns an error whenever SOURCE,
721 * TARGET, and ANCESTOR are all distinct node revisions.
722 *
723 * If there are differences between ANCESTOR and SOURCE that conflict
724 * with changes between ANCESTOR and TARGET, this function returns an
725 * SVN_ERR_FS_CONFLICT error, and updates CONFLICT_P to the name of the
726 * conflicting node in TARGET, with TARGET_PATH prepended as a path.
727 *
728 * If there are no conflicting differences, CONFLICT_P is updated to
729 * the empty string.
730 *
731 * CONFLICT_P must point to a valid svn_stringbuf_t.
732 *
733 * Do any necessary temporary allocation in POOL.
734 */
735static svn_error_t *
736merge(svn_stringbuf_t *conflict_p,
737      const char *target_path,
738      dag_node_t *target,
739      dag_node_t *source,
740      dag_node_t *ancestor,
741      svn_fs_x__txn_id_t txn_id,
742      apr_int64_t *mergeinfo_increment_out,
743      apr_pool_t *pool)
744{
745  const svn_fs_x__id_t *source_id, *target_id, *ancestor_id;
746  apr_array_header_t *s_entries, *t_entries, *a_entries;
747  int i, s_idx = -1, t_idx = -1;
748  svn_fs_t *fs;
749  apr_pool_t *iterpool;
750  apr_int64_t mergeinfo_increment = 0;
751
752  /* Make sure everyone comes from the same filesystem. */
753  fs = svn_fs_x__dag_get_fs(ancestor);
754  if ((fs != svn_fs_x__dag_get_fs(source))
755      || (fs != svn_fs_x__dag_get_fs(target)))
756    {
757      return svn_error_create
758        (SVN_ERR_FS_CORRUPT, NULL,
759         _("Bad merge; ancestor, source, and target not all in same fs"));
760    }
761
762  /* We have the same fs, now check it. */
763  SVN_ERR(svn_fs__check_fs(fs, TRUE));
764
765  source_id   = svn_fs_x__dag_get_id(source);
766  target_id   = svn_fs_x__dag_get_id(target);
767  ancestor_id = svn_fs_x__dag_get_id(ancestor);
768
769  /* It's improper to call this function with ancestor == target. */
770  if (svn_fs_x__id_eq(ancestor_id, target_id))
771    {
772      svn_string_t *id_str = svn_fs_x__id_unparse(target_id, pool);
773      return svn_error_createf
774        (SVN_ERR_FS_GENERAL, NULL,
775         _("Bad merge; target '%s' has id '%s', same as ancestor"),
776         target_path, id_str->data);
777    }
778
779  svn_stringbuf_setempty(conflict_p);
780
781  /* Base cases:
782   * Either no change made in source, or same change as made in target.
783   * Both mean nothing to merge here.
784   */
785  if (svn_fs_x__id_eq(ancestor_id, source_id)
786      || (svn_fs_x__id_eq(source_id, target_id)))
787    return SVN_NO_ERROR;
788
789  /* Else proceed, knowing all three are distinct node revisions.
790   *
791   * How to merge from this point:
792   *
793   * if (not all 3 are directories)
794   *   {
795   *     early exit with conflict;
796   *   }
797   *
798   * // Property changes may only be made to up-to-date
799   * // directories, because once the client commits the prop
800   * // change, it bumps the directory's revision, and therefore
801   * // must be able to depend on there being no other changes to
802   * // that directory in the repository.
803   * if (target's property list differs from ancestor's)
804   *    conflict;
805   *
806   * For each entry NAME in the directory ANCESTOR:
807   *
808   *   Let ANCESTOR-ENTRY, SOURCE-ENTRY, and TARGET-ENTRY be the IDs of
809   *   the name within ANCESTOR, SOURCE, and TARGET respectively.
810   *   (Possibly null if NAME does not exist in SOURCE or TARGET.)
811   *
812   *   If ANCESTOR-ENTRY == SOURCE-ENTRY, then:
813   *     No changes were made to this entry while the transaction was in
814   *     progress, so do nothing to the target.
815   *
816   *   Else if ANCESTOR-ENTRY == TARGET-ENTRY, then:
817   *     A change was made to this entry while the transaction was in
818   *     process, but the transaction did not touch this entry.  Replace
819   *     TARGET-ENTRY with SOURCE-ENTRY.
820   *
821   *   Else:
822   *     Changes were made to this entry both within the transaction and
823   *     to the repository while the transaction was in progress.  They
824   *     must be merged or declared to be in conflict.
825   *
826   *     If SOURCE-ENTRY and TARGET-ENTRY are both null, that's a
827   *     double delete; flag a conflict.
828   *
829   *     If any of the three entries is of type file, declare a conflict.
830   *
831   *     If either SOURCE-ENTRY or TARGET-ENTRY is not a direct
832   *     modification of ANCESTOR-ENTRY (determine by comparing the
833   *     node-id fields), declare a conflict.  A replacement is
834   *     incompatible with a modification or other replacement--even
835   *     an identical replacement.
836   *
837   *     Direct modifications were made to the directory ANCESTOR-ENTRY
838   *     in both SOURCE and TARGET.  Recursively merge these
839   *     modifications.
840   *
841   * For each leftover entry NAME in the directory SOURCE:
842   *
843   *   If NAME exists in TARGET, declare a conflict.  Even if SOURCE and
844   *   TARGET are adding exactly the same thing, two additions are not
845   *   auto-mergeable with each other.
846   *
847   *   Add NAME to TARGET with the entry from SOURCE.
848   *
849   * Now that we are done merging the changes from SOURCE into the
850   * directory TARGET, update TARGET's predecessor to be SOURCE.
851   */
852
853  if ((svn_fs_x__dag_node_kind(source) != svn_node_dir)
854      || (svn_fs_x__dag_node_kind(target) != svn_node_dir)
855      || (svn_fs_x__dag_node_kind(ancestor) != svn_node_dir))
856    {
857      return conflict_err(conflict_p, target_path);
858    }
859
860
861  /* Possible early merge failure: if target and ancestor have
862     different property lists, then the merge should fail.
863     Propchanges can *only* be committed on an up-to-date directory.
864     ### TODO: see issue #418 about the inelegance of this.
865
866     Another possible, similar, early merge failure: if source and
867     ancestor have different property lists (meaning someone else
868     changed directory properties while our commit transaction was
869     happening), the merge should fail.  See issue #2751.
870  */
871  {
872    svn_fs_x__noderev_t *tgt_nr, *anc_nr, *src_nr;
873    svn_boolean_t same;
874    apr_pool_t *scratch_pool;
875
876    /* Get node revisions for our id's. */
877    scratch_pool = svn_pool_create(pool);
878    SVN_ERR(svn_fs_x__get_node_revision(&tgt_nr, fs, target_id,
879                                        pool, scratch_pool));
880    svn_pool_clear(scratch_pool);
881    SVN_ERR(svn_fs_x__get_node_revision(&anc_nr, fs, ancestor_id,
882                                        pool, scratch_pool));
883    svn_pool_clear(scratch_pool);
884    SVN_ERR(svn_fs_x__get_node_revision(&src_nr, fs, source_id,
885                                        pool, scratch_pool));
886    svn_pool_destroy(scratch_pool);
887
888    /* Now compare the prop-keys of the skels.  Note that just because
889       the keys are different -doesn't- mean the proplists have
890       different contents. */
891    SVN_ERR(svn_fs_x__prop_rep_equal(&same, fs, src_nr, anc_nr, TRUE, pool));
892    if (! same)
893      return conflict_err(conflict_p, target_path);
894
895    /* The directory entries got changed in the repository but the directory
896       properties did not. */
897    SVN_ERR(svn_fs_x__prop_rep_equal(&same, fs, tgt_nr, anc_nr, TRUE, pool));
898    if (! same)
899      {
900        /* There is an incoming prop change for this directory.
901           We will accept it only if the directory changes were mere updates
902           to its entries, i.e. there were no additions or removals.
903           Those could cause update problems to the working copy. */
904        svn_boolean_t changed;
905        SVN_ERR(compare_dir_structure(&changed, fs, source, ancestor, pool));
906
907        if (changed)
908          return conflict_err(conflict_p, target_path);
909      }
910  }
911
912  /* ### todo: it would be more efficient to simply check for a NULL
913     entries hash where necessary below than to allocate an empty hash
914     here, but another day, another day... */
915  iterpool = svn_pool_create(pool);
916  SVN_ERR(svn_fs_x__dag_dir_entries(&s_entries, source, pool, iterpool));
917  SVN_ERR(svn_fs_x__dag_dir_entries(&t_entries, target, pool, iterpool));
918  SVN_ERR(svn_fs_x__dag_dir_entries(&a_entries, ancestor, pool, iterpool));
919
920  /* for each entry E in a_entries... */
921  for (i = 0; i < a_entries->nelts; ++i)
922    {
923      svn_fs_x__dirent_t *s_entry, *t_entry, *a_entry;
924      svn_pool_clear(iterpool);
925
926      a_entry = APR_ARRAY_IDX(a_entries, i, svn_fs_x__dirent_t *);
927      s_entry = svn_fs_x__find_dir_entry(s_entries, a_entry->name, &s_idx);
928      t_entry = svn_fs_x__find_dir_entry(t_entries, a_entry->name, &t_idx);
929
930      /* No changes were made to this entry while the transaction was
931         in progress, so do nothing to the target. */
932      if (s_entry && svn_fs_x__id_eq(&a_entry->id, &s_entry->id))
933        continue;
934
935      /* A change was made to this entry while the transaction was in
936         process, but the transaction did not touch this entry. */
937      else if (t_entry && svn_fs_x__id_eq(&a_entry->id, &t_entry->id))
938        {
939          dag_node_t *t_ent_node;
940          SVN_ERR(svn_fs_x__dag_get_node(&t_ent_node, fs, &t_entry->id,
941                                         iterpool, iterpool));
942          mergeinfo_increment
943            -= svn_fs_x__dag_get_mergeinfo_count(t_ent_node);
944
945          if (s_entry)
946            {
947              dag_node_t *s_ent_node;
948              SVN_ERR(svn_fs_x__dag_get_node(&s_ent_node, fs, &s_entry->id,
949                                             iterpool, iterpool));
950
951              mergeinfo_increment
952                += svn_fs_x__dag_get_mergeinfo_count(s_ent_node);
953
954              SVN_ERR(svn_fs_x__dag_set_entry(target, a_entry->name,
955                                              &s_entry->id,
956                                              s_entry->kind,
957                                              txn_id,
958                                              iterpool));
959            }
960          else
961            {
962              SVN_ERR(svn_fs_x__dag_delete(target, a_entry->name, txn_id,
963                                           iterpool));
964            }
965        }
966
967      /* Changes were made to this entry both within the transaction
968         and to the repository while the transaction was in progress.
969         They must be merged or declared to be in conflict. */
970      else
971        {
972          dag_node_t *s_ent_node, *t_ent_node, *a_ent_node;
973          const char *new_tpath;
974          apr_int64_t sub_mergeinfo_increment;
975
976          /* If SOURCE-ENTRY and TARGET-ENTRY are both null, that's a
977             double delete; if one of them is null, that's a delete versus
978             a modification. In any of these cases, flag a conflict. */
979          if (s_entry == NULL || t_entry == NULL)
980            return conflict_err(conflict_p,
981                                svn_fspath__join(target_path,
982                                                 a_entry->name,
983                                                 iterpool));
984
985          /* If any of the three entries is of type file, flag a conflict. */
986          if (s_entry->kind == svn_node_file
987              || t_entry->kind == svn_node_file
988              || a_entry->kind == svn_node_file)
989            return conflict_err(conflict_p,
990                                svn_fspath__join(target_path,
991                                                 a_entry->name,
992                                                 iterpool));
993
994          /* Fetch DAG nodes to efficiently access ID parts. */
995          SVN_ERR(svn_fs_x__dag_get_node(&s_ent_node, fs, &s_entry->id,
996                                         iterpool, iterpool));
997          SVN_ERR(svn_fs_x__dag_get_node(&t_ent_node, fs, &t_entry->id,
998                                         iterpool, iterpool));
999          SVN_ERR(svn_fs_x__dag_get_node(&a_ent_node, fs, &a_entry->id,
1000                                         iterpool, iterpool));
1001
1002          /* If either SOURCE-ENTRY or TARGET-ENTRY is not a direct
1003             modification of ANCESTOR-ENTRY, declare a conflict. */
1004          if (   !svn_fs_x__dag_same_line_of_history(s_ent_node, a_ent_node)
1005              || !svn_fs_x__dag_same_line_of_history(t_ent_node, a_ent_node))
1006            return conflict_err(conflict_p,
1007                                svn_fspath__join(target_path,
1008                                                 a_entry->name,
1009                                                 iterpool));
1010
1011          /* Direct modifications were made to the directory
1012             ANCESTOR-ENTRY in both SOURCE and TARGET.  Recursively
1013             merge these modifications. */
1014          new_tpath = svn_fspath__join(target_path, t_entry->name, iterpool);
1015          SVN_ERR(merge(conflict_p, new_tpath,
1016                        t_ent_node, s_ent_node, a_ent_node,
1017                        txn_id,
1018                        &sub_mergeinfo_increment,
1019                        iterpool));
1020          mergeinfo_increment += sub_mergeinfo_increment;
1021        }
1022    }
1023
1024  /* For each entry E in source but not in ancestor */
1025  for (i = 0; i < s_entries->nelts; ++i)
1026    {
1027      svn_fs_x__dirent_t *a_entry, *s_entry, *t_entry;
1028      dag_node_t *s_ent_node;
1029
1030      svn_pool_clear(iterpool);
1031
1032      s_entry = APR_ARRAY_IDX(s_entries, i, svn_fs_x__dirent_t *);
1033      a_entry = svn_fs_x__find_dir_entry(a_entries, s_entry->name, &s_idx);
1034      t_entry = svn_fs_x__find_dir_entry(t_entries, s_entry->name, &t_idx);
1035
1036      /* Process only entries in source that are NOT in ancestor. */
1037      if (a_entry)
1038        continue;
1039
1040      /* If NAME exists in TARGET, declare a conflict. */
1041      if (t_entry)
1042        return conflict_err(conflict_p,
1043                            svn_fspath__join(target_path,
1044                                             t_entry->name,
1045                                             iterpool));
1046
1047      SVN_ERR(svn_fs_x__dag_get_node(&s_ent_node, fs, &s_entry->id,
1048                                     iterpool, iterpool));
1049      mergeinfo_increment += svn_fs_x__dag_get_mergeinfo_count(s_ent_node);
1050
1051      SVN_ERR(svn_fs_x__dag_set_entry
1052              (target, s_entry->name, &s_entry->id, s_entry->kind,
1053               txn_id, iterpool));
1054    }
1055  svn_pool_destroy(iterpool);
1056
1057  SVN_ERR(svn_fs_x__dag_update_ancestry(target, source, pool));
1058
1059  SVN_ERR(svn_fs_x__dag_increment_mergeinfo_count(target,
1060                                                  mergeinfo_increment,
1061                                                  pool));
1062
1063  if (mergeinfo_increment_out)
1064    *mergeinfo_increment_out = mergeinfo_increment;
1065
1066  return SVN_NO_ERROR;
1067}
1068
1069/* Merge changes between an ancestor and SOURCE_NODE into
1070   TXN.  The ancestor is either ANCESTOR_NODE, or if
1071   that is null, TXN's base node.
1072
1073   If the merge is successful, TXN's base will become
1074   SOURCE_NODE, and its root node will have a new ID, a
1075   successor of SOURCE_NODE.
1076
1077   If a conflict results, update *CONFLICT to the path in the txn that
1078   conflicted; see the CONFLICT_P parameter of merge() for details. */
1079static svn_error_t *
1080merge_changes(dag_node_t *ancestor_node,
1081              dag_node_t *source_node,
1082              svn_fs_txn_t *txn,
1083              svn_stringbuf_t *conflict,
1084              apr_pool_t *scratch_pool)
1085{
1086  dag_node_t *txn_root_node;
1087  svn_fs_t *fs = txn->fs;
1088  svn_fs_x__txn_id_t txn_id = svn_fs_x__txn_get_id(txn);
1089
1090  SVN_ERR(svn_fs_x__dag_root(&txn_root_node, fs,
1091                             svn_fs_x__change_set_by_txn(txn_id),
1092                             scratch_pool, scratch_pool));
1093
1094  if (ancestor_node == NULL)
1095    {
1096      svn_revnum_t base_rev;
1097      SVN_ERR(svn_fs_x__get_base_rev(&base_rev, fs, txn_id, scratch_pool));
1098      SVN_ERR(svn_fs_x__dag_root(&ancestor_node, fs,
1099                                 svn_fs_x__change_set_by_rev(base_rev),
1100                                 scratch_pool, scratch_pool));
1101    }
1102
1103  if (!svn_fs_x__dag_related_node(ancestor_node, txn_root_node))
1104    {
1105      /* If no changes have been made in TXN since its current base,
1106         then it can't conflict with any changes since that base.
1107         The caller isn't supposed to call us in that case. */
1108      SVN_ERR_MALFUNCTION();
1109    }
1110  else
1111    SVN_ERR(merge(conflict, "/", txn_root_node,
1112                  source_node, ancestor_node, txn_id, NULL, scratch_pool));
1113
1114  return SVN_NO_ERROR;
1115}
1116
1117
1118svn_error_t *
1119svn_fs_x__commit_txn(const char **conflict_p,
1120                     svn_revnum_t *new_rev,
1121                     svn_fs_txn_t *txn,
1122                     apr_pool_t *pool)
1123{
1124  /* How do commits work in Subversion?
1125   *
1126   * When you're ready to commit, here's what you have:
1127   *
1128   *    1. A transaction, with a mutable tree hanging off it.
1129   *    2. A base revision, against which TXN_TREE was made.
1130   *    3. A latest revision, which may be newer than the base rev.
1131   *
1132   * The problem is that if latest != base, then one can't simply
1133   * attach the txn root as the root of the new revision, because that
1134   * would lose all the changes between base and latest.  It is also
1135   * not acceptable to insist that base == latest; in a busy
1136   * repository, commits happen too fast to insist that everyone keep
1137   * their entire tree up-to-date at all times.  Non-overlapping
1138   * changes should not interfere with each other.
1139   *
1140   * The solution is to merge the changes between base and latest into
1141   * the txn tree [see the function merge()].  The txn tree is the
1142   * only one of the three trees that is mutable, so it has to be the
1143   * one to adjust.
1144   *
1145   * You might have to adjust it more than once, if a new latest
1146   * revision gets committed while you were merging in the previous
1147   * one.  For example:
1148   *
1149   *    1. Jane starts txn T, based at revision 6.
1150   *    2. Someone commits (or already committed) revision 7.
1151   *    3. Jane's starts merging the changes between 6 and 7 into T.
1152   *    4. Meanwhile, someone commits revision 8.
1153   *    5. Jane finishes the 6-->7 merge.  T could now be committed
1154   *       against a latest revision of 7, if only that were still the
1155   *       latest.  Unfortunately, 8 is now the latest, so...
1156   *    6. Jane starts merging the changes between 7 and 8 into T.
1157   *    7. Meanwhile, no one commits any new revisions.  Whew.
1158   *    8. Jane commits T, creating revision 9, whose tree is exactly
1159   *       T's tree, except immutable now.
1160   *
1161   * Lather, rinse, repeat.
1162   */
1163
1164  svn_error_t *err = SVN_NO_ERROR;
1165  svn_stringbuf_t *conflict = svn_stringbuf_create_empty(pool);
1166  svn_fs_t *fs = txn->fs;
1167  svn_fs_x__data_t *ffd = fs->fsap_data;
1168
1169  /* Limit memory usage when the repository has a high commit rate and
1170     needs to run the following while loop multiple times.  The memory
1171     growth without an iteration pool is very noticeable when the
1172     transaction modifies a node that has 20,000 sibling nodes. */
1173  apr_pool_t *iterpool = svn_pool_create(pool);
1174
1175  /* Initialize output params. */
1176  *new_rev = SVN_INVALID_REVNUM;
1177  if (conflict_p)
1178    *conflict_p = NULL;
1179
1180  while (1729)
1181    {
1182      svn_revnum_t youngish_rev;
1183      svn_fs_root_t *youngish_root;
1184      dag_node_t *youngish_root_node;
1185
1186      svn_pool_clear(iterpool);
1187
1188      /* Get the *current* youngest revision.  We call it "youngish"
1189         because new revisions might get committed after we've
1190         obtained it. */
1191
1192      SVN_ERR(svn_fs_x__youngest_rev(&youngish_rev, fs, iterpool));
1193      SVN_ERR(svn_fs_x__revision_root(&youngish_root, fs, youngish_rev,
1194                                      iterpool));
1195
1196      /* Get the dag node for the youngest revision.  Later we'll use
1197         it as the SOURCE argument to a merge, and if the merge
1198         succeeds, this youngest root node will become the new base
1199         root for the svn txn that was the target of the merge (but
1200         note that the youngest rev may have changed by then -- that's
1201         why we're careful to get this root in its own bdb txn
1202         here). */
1203      SVN_ERR(get_root(&youngish_root_node, youngish_root, iterpool,
1204                       iterpool));
1205
1206      /* Try to merge.  If the merge succeeds, the base root node of
1207         TARGET's txn will become the same as youngish_root_node, so
1208         any future merges will only be between that node and whatever
1209         the root node of the youngest rev is by then. */
1210      err = merge_changes(NULL, youngish_root_node, txn, conflict, iterpool);
1211      if (err)
1212        {
1213          if ((err->apr_err == SVN_ERR_FS_CONFLICT) && conflict_p)
1214            *conflict_p = conflict->data;
1215          goto cleanup;
1216        }
1217      txn->base_rev = youngish_rev;
1218
1219      /* Try to commit. */
1220      err = svn_fs_x__commit(new_rev, fs, txn, iterpool);
1221      if (err && (err->apr_err == SVN_ERR_FS_TXN_OUT_OF_DATE))
1222        {
1223          /* Did someone else finish committing a new revision while we
1224             were in mid-merge or mid-commit?  If so, we'll need to
1225             loop again to merge the new changes in, then try to
1226             commit again.  Or if that's not what happened, then just
1227             return the error. */
1228          svn_revnum_t youngest_rev;
1229          SVN_ERR(svn_fs_x__youngest_rev(&youngest_rev, fs, iterpool));
1230          if (youngest_rev == youngish_rev)
1231            goto cleanup;
1232          else
1233            svn_error_clear(err);
1234        }
1235      else if (err)
1236        {
1237          goto cleanup;
1238        }
1239      else
1240        {
1241          err = SVN_NO_ERROR;
1242          goto cleanup;
1243        }
1244    }
1245
1246 cleanup:
1247
1248  svn_pool_destroy(iterpool);
1249
1250  SVN_ERR(err);
1251
1252  if (ffd->pack_after_commit)
1253    {
1254      SVN_ERR(svn_fs_x__pack(fs, 0, NULL, NULL, NULL, NULL, pool));
1255    }
1256
1257  return SVN_NO_ERROR;
1258}
1259
1260
1261/* Merge changes between two nodes into a third node.  Given nodes
1262   SOURCE_PATH under SOURCE_ROOT, TARGET_PATH under TARGET_ROOT and
1263   ANCESTOR_PATH under ANCESTOR_ROOT, modify target to contain all the
1264   changes between the ancestor and source.  If there are conflicts,
1265   return SVN_ERR_FS_CONFLICT and set *CONFLICT_P to a textual
1266   description of the offending changes.  Perform any temporary
1267   allocations in POOL. */
1268static svn_error_t *
1269x_merge(const char **conflict_p,
1270        svn_fs_root_t *source_root,
1271        const char *source_path,
1272        svn_fs_root_t *target_root,
1273        const char *target_path,
1274        svn_fs_root_t *ancestor_root,
1275        const char *ancestor_path,
1276        apr_pool_t *pool)
1277{
1278  dag_node_t *source, *ancestor;
1279  svn_fs_txn_t *txn;
1280  svn_error_t *err;
1281  svn_stringbuf_t *conflict = svn_stringbuf_create_empty(pool);
1282
1283  if (! target_root->is_txn_root)
1284    return SVN_FS__NOT_TXN(target_root);
1285
1286  /* Paranoia. */
1287  if ((source_root->fs != ancestor_root->fs)
1288      || (target_root->fs != ancestor_root->fs))
1289    {
1290      return svn_error_create
1291        (SVN_ERR_FS_CORRUPT, NULL,
1292         _("Bad merge; ancestor, source, and target not all in same fs"));
1293    }
1294
1295  /* ### kff todo: is there any compelling reason to get the nodes in
1296     one db transaction?  Right now we don't; txn_body_get_root() gets
1297     one node at a time.  This will probably need to change:
1298
1299     Jim Blandy <jimb@zwingli.cygnus.com> writes:
1300     > svn_fs_merge needs to be a single transaction, to protect it against
1301     > people deleting parents of nodes it's working on, etc.
1302  */
1303
1304  /* Get the ancestor node. */
1305  SVN_ERR(get_root(&ancestor, ancestor_root, pool, pool));
1306
1307  /* Get the source node. */
1308  SVN_ERR(get_root(&source, source_root, pool, pool));
1309
1310  /* Open a txn for the txn root into which we're merging. */
1311  SVN_ERR(svn_fs_x__open_txn(&txn, ancestor_root->fs, target_root->txn,
1312                             pool));
1313
1314  /* Merge changes between ANCESTOR and SOURCE into TXN. */
1315  err = merge_changes(ancestor, source, txn, conflict, pool);
1316  if (err)
1317    {
1318      if ((err->apr_err == SVN_ERR_FS_CONFLICT) && conflict_p)
1319        *conflict_p = conflict->data;
1320      return svn_error_trace(err);
1321    }
1322
1323  return SVN_NO_ERROR;
1324}
1325
1326svn_error_t *
1327svn_fs_x__deltify(svn_fs_t *fs,
1328                  svn_revnum_t revision,
1329                  apr_pool_t *scratch_pool)
1330{
1331  /* Deltify is a no-op for fs_x. */
1332
1333  return SVN_NO_ERROR;
1334}
1335
1336
1337
1338/* Directories.  */
1339
1340/* Set *TABLE_P to a newly allocated APR hash table containing the
1341   entries of the directory at PATH in ROOT.  The keys of the table
1342   are entry names, as byte strings, excluding the final null
1343   character; the table's values are pointers to svn_fs_svn_fs_x__dirent_t
1344   structures.  Allocate the table and its contents in POOL. */
1345static svn_error_t *
1346x_dir_entries(apr_hash_t **table_p,
1347              svn_fs_root_t *root,
1348              const char *path,
1349              apr_pool_t *pool)
1350{
1351  dag_node_t *node;
1352  apr_hash_t *hash = svn_hash__make(pool);
1353  apr_array_header_t *table;
1354  int i;
1355  svn_fs_x__id_context_t *context = NULL;
1356  apr_pool_t *scratch_pool = svn_pool_create(pool);
1357
1358  /* Get the entries for this path in the caller's pool. */
1359  SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root, path, scratch_pool));
1360  SVN_ERR(svn_fs_x__dag_dir_entries(&table, node, scratch_pool,
1361                                    scratch_pool));
1362
1363  if (table->nelts)
1364    context = svn_fs_x__id_create_context(root->fs, pool);
1365
1366  /* Convert directory array to hash. */
1367  for (i = 0; i < table->nelts; ++i)
1368    {
1369      svn_fs_x__dirent_t *entry
1370        = APR_ARRAY_IDX(table, i, svn_fs_x__dirent_t *);
1371      apr_size_t len = strlen(entry->name);
1372
1373      svn_fs_dirent_t *api_dirent = apr_pcalloc(pool, sizeof(*api_dirent));
1374      api_dirent->name = apr_pstrmemdup(pool, entry->name, len);
1375      api_dirent->kind = entry->kind;
1376      api_dirent->id = svn_fs_x__id_create(context, &entry->id, pool);
1377
1378      apr_hash_set(hash, api_dirent->name, len, api_dirent);
1379    }
1380
1381  *table_p = hash;
1382  svn_pool_destroy(scratch_pool);
1383
1384  return SVN_NO_ERROR;
1385}
1386
1387static svn_error_t *
1388x_dir_optimal_order(apr_array_header_t **ordered_p,
1389                    svn_fs_root_t *root,
1390                    apr_hash_t *entries,
1391                    apr_pool_t *result_pool,
1392                    apr_pool_t *scratch_pool)
1393{
1394  *ordered_p = svn_fs_x__order_dir_entries(root->fs, entries, result_pool,
1395                                           scratch_pool);
1396
1397  return SVN_NO_ERROR;
1398}
1399
1400/* Create a new directory named PATH in ROOT.  The new directory has
1401   no entries, and no properties.  ROOT must be the root of a
1402   transaction, not a revision.  Do any necessary temporary allocation
1403   in SCRATCH_POOL.  */
1404static svn_error_t *
1405x_make_dir(svn_fs_root_t *root,
1406           const char *path,
1407           apr_pool_t *scratch_pool)
1408{
1409  svn_fs_x__dag_path_t *dag_path;
1410  dag_node_t *sub_dir;
1411  svn_fs_x__txn_id_t txn_id = svn_fs_x__root_txn_id(root);
1412  apr_pool_t *subpool = svn_pool_create(scratch_pool);
1413
1414  SVN_ERR(svn_fs_x__get_dag_path(&dag_path, root, path,
1415                                 svn_fs_x__dag_path_last_optional,
1416                                 TRUE, subpool, subpool));
1417
1418  /* Check (recursively) to see if some lock is 'reserving' a path at
1419     that location, or even some child-path; if so, check that we can
1420     use it. */
1421  if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
1422    SVN_ERR(svn_fs_x__allow_locked_operation(path, root->fs, TRUE, FALSE,
1423                                             subpool));
1424
1425  /* If there's already a sub-directory by that name, complain.  This
1426     also catches the case of trying to make a subdirectory named `/'.  */
1427  if (dag_path->node)
1428    return SVN_FS__ALREADY_EXISTS(root, path);
1429
1430  /* Create the subdirectory.  */
1431  SVN_ERR(svn_fs_x__make_path_mutable(root, dag_path->parent, path, subpool,
1432                                      subpool));
1433  SVN_ERR(svn_fs_x__dag_make_dir(&sub_dir,
1434                                 dag_path->parent->node,
1435                                 parent_path_path(dag_path->parent,
1436                                                  subpool),
1437                                 dag_path->entry,
1438                                 txn_id,
1439                                 subpool, subpool));
1440
1441  /* Add this directory to the path cache. */
1442  svn_fs_x__update_dag_cache(sub_dir);
1443
1444  /* Make a record of this modification in the changes table. */
1445  SVN_ERR(add_change(root->fs, txn_id, path,
1446                     svn_fs_path_change_add, FALSE, FALSE, FALSE,
1447                     svn_node_dir, SVN_INVALID_REVNUM, NULL, subpool));
1448
1449  svn_pool_destroy(subpool);
1450  return SVN_NO_ERROR;
1451}
1452
1453
1454/* Delete the node at PATH under ROOT.  ROOT must be a transaction
1455   root.  Perform temporary allocations in SCRATCH_POOL. */
1456static svn_error_t *
1457x_delete_node(svn_fs_root_t *root,
1458              const char *path,
1459              apr_pool_t *scratch_pool)
1460{
1461  svn_fs_x__dag_path_t *dag_path;
1462  svn_fs_x__txn_id_t txn_id;
1463  apr_int64_t mergeinfo_count = 0;
1464  svn_node_kind_t kind;
1465  apr_pool_t *subpool = svn_pool_create(scratch_pool);
1466
1467  if (! root->is_txn_root)
1468    return SVN_FS__NOT_TXN(root);
1469
1470  txn_id = svn_fs_x__root_txn_id(root);
1471  SVN_ERR(svn_fs_x__get_dag_path(&dag_path, root, path, 0, TRUE, subpool,
1472                                 subpool));
1473  kind = svn_fs_x__dag_node_kind(dag_path->node);
1474
1475  /* We can't remove the root of the filesystem.  */
1476  if (! dag_path->parent)
1477    return svn_error_create(SVN_ERR_FS_ROOT_DIR, NULL,
1478                            _("The root directory cannot be deleted"));
1479
1480  /* Check to see if path (or any child thereof) is locked; if so,
1481     check that we can use the existing lock(s). */
1482  if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
1483    SVN_ERR(svn_fs_x__allow_locked_operation(path, root->fs, TRUE, FALSE,
1484                                             subpool));
1485
1486  /* Make the parent directory mutable, and do the deletion.  */
1487  SVN_ERR(svn_fs_x__make_path_mutable(root, dag_path->parent, path, subpool,
1488                                      subpool));
1489  mergeinfo_count = svn_fs_x__dag_get_mergeinfo_count(dag_path->node);
1490  SVN_ERR(svn_fs_x__dag_delete(dag_path->parent->node,
1491                               dag_path->entry,
1492                               txn_id, subpool));
1493
1494  /* Remove this node and any children from the path cache. */
1495  svn_fs_x__invalidate_dag_cache(root, parent_path_path(dag_path, subpool));
1496
1497  /* Update mergeinfo counts for parents */
1498  if (mergeinfo_count > 0)
1499    SVN_ERR(increment_mergeinfo_up_tree(dag_path->parent,
1500                                        -mergeinfo_count,
1501                                        subpool));
1502
1503  /* Make a record of this modification in the changes table. */
1504  SVN_ERR(add_change(root->fs, txn_id, path,
1505                     svn_fs_path_change_delete, FALSE, FALSE, FALSE, kind,
1506                     SVN_INVALID_REVNUM, NULL, subpool));
1507
1508  svn_pool_destroy(subpool);
1509  return SVN_NO_ERROR;
1510}
1511
1512
1513/* Set *SAME_P to TRUE if FS1 and FS2 have the same UUID, else set to FALSE.
1514   Use SCRATCH_POOL for temporary allocation only.
1515   Note: this code is duplicated between libsvn_fs_x and libsvn_fs_base. */
1516static svn_error_t *
1517x_same_p(svn_boolean_t *same_p,
1518         svn_fs_t *fs1,
1519         svn_fs_t *fs2,
1520         apr_pool_t *scratch_pool)
1521{
1522  *same_p = ! strcmp(fs1->uuid, fs2->uuid);
1523  return SVN_NO_ERROR;
1524}
1525
1526/* Copy the node at FROM_PATH under FROM_ROOT to TO_PATH under
1527   TO_ROOT.  If PRESERVE_HISTORY is set, then the copy is recorded in
1528   the copies table.  Perform temporary allocations in SCRATCH_POOL. */
1529static svn_error_t *
1530copy_helper(svn_fs_root_t *from_root,
1531            const char *from_path,
1532            svn_fs_root_t *to_root,
1533            const char *to_path,
1534            svn_boolean_t preserve_history,
1535            apr_pool_t *scratch_pool)
1536{
1537  dag_node_t *from_node;
1538  svn_fs_x__dag_path_t *to_dag_path;
1539  svn_fs_x__txn_id_t txn_id = svn_fs_x__root_txn_id(to_root);
1540  svn_boolean_t same_p;
1541
1542  /* Use an error check, not an assert, because even the caller cannot
1543     guarantee that a filesystem's UUID has not changed "on the fly". */
1544  SVN_ERR(x_same_p(&same_p, from_root->fs, to_root->fs, scratch_pool));
1545  if (! same_p)
1546    return svn_error_createf
1547      (SVN_ERR_UNSUPPORTED_FEATURE, NULL,
1548       _("Cannot copy between two different filesystems ('%s' and '%s')"),
1549       from_root->fs->path, to_root->fs->path);
1550
1551  /* more things that we can't do ATM */
1552  if (from_root->is_txn_root)
1553    return svn_error_create
1554      (SVN_ERR_UNSUPPORTED_FEATURE, NULL,
1555       _("Copy from mutable tree not currently supported"));
1556
1557  if (! to_root->is_txn_root)
1558    return svn_error_create
1559      (SVN_ERR_UNSUPPORTED_FEATURE, NULL,
1560       _("Copy immutable tree not supported"));
1561
1562  /* Get the NODE for FROM_PATH in FROM_ROOT.*/
1563  SVN_ERR(svn_fs_x__get_dag_node(&from_node, from_root, from_path,
1564                                 scratch_pool, scratch_pool));
1565
1566  /* Build up the parent path from TO_PATH in TO_ROOT.  If the last
1567     component does not exist, it's not that big a deal.  We'll just
1568     make one there. */
1569  SVN_ERR(svn_fs_x__get_dag_path(&to_dag_path, to_root, to_path,
1570                                 svn_fs_x__dag_path_last_optional, TRUE,
1571                                 scratch_pool, scratch_pool));
1572
1573  /* Check to see if path (or any child thereof) is locked; if so,
1574     check that we can use the existing lock(s). */
1575  if (to_root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
1576    SVN_ERR(svn_fs_x__allow_locked_operation(to_path, to_root->fs,
1577                                             TRUE, FALSE, scratch_pool));
1578
1579  /* If the destination node already exists as the same node as the
1580     source (in other words, this operation would result in nothing
1581     happening at all), just do nothing an return successfully,
1582     proud that you saved yourself from a tiresome task. */
1583  if (to_dag_path->node &&
1584      svn_fs_x__id_eq(svn_fs_x__dag_get_id(from_node),
1585                      svn_fs_x__dag_get_id(to_dag_path->node)))
1586    return SVN_NO_ERROR;
1587
1588  if (! from_root->is_txn_root)
1589    {
1590      svn_fs_path_change_kind_t kind;
1591      dag_node_t *new_node;
1592      const char *from_canonpath;
1593      apr_int64_t mergeinfo_start;
1594      apr_int64_t mergeinfo_end;
1595
1596      /* If TO_PATH already existed prior to the copy, note that this
1597         operation is a replacement, not an addition. */
1598      if (to_dag_path->node)
1599        {
1600          kind = svn_fs_path_change_replace;
1601          mergeinfo_start
1602            = svn_fs_x__dag_get_mergeinfo_count(to_dag_path->node);
1603        }
1604      else
1605        {
1606          kind = svn_fs_path_change_add;
1607          mergeinfo_start = 0;
1608        }
1609
1610      mergeinfo_end = svn_fs_x__dag_get_mergeinfo_count(from_node);
1611
1612      /* Make sure the target node's parents are mutable.  */
1613      SVN_ERR(svn_fs_x__make_path_mutable(to_root, to_dag_path->parent,
1614                                          to_path, scratch_pool,
1615                                          scratch_pool));
1616
1617      /* Canonicalize the copyfrom path. */
1618      from_canonpath = svn_fs__canonicalize_abspath(from_path, scratch_pool);
1619
1620      SVN_ERR(svn_fs_x__dag_copy(to_dag_path->parent->node,
1621                                 to_dag_path->entry,
1622                                 from_node,
1623                                 preserve_history,
1624                                 from_root->rev,
1625                                 from_canonpath,
1626                                 txn_id, scratch_pool));
1627
1628      if (kind != svn_fs_path_change_add)
1629        svn_fs_x__invalidate_dag_cache(to_root,
1630                                       parent_path_path(to_dag_path,
1631                                                        scratch_pool));
1632
1633      if (mergeinfo_start != mergeinfo_end)
1634        SVN_ERR(increment_mergeinfo_up_tree(to_dag_path->parent,
1635                                            mergeinfo_end - mergeinfo_start,
1636                                            scratch_pool));
1637
1638      /* Make a record of this modification in the changes table. */
1639      SVN_ERR(svn_fs_x__get_dag_node(&new_node, to_root, to_path,
1640                                     scratch_pool, scratch_pool));
1641      SVN_ERR(add_change(to_root->fs, txn_id, to_path, kind, FALSE,
1642                         FALSE, FALSE, svn_fs_x__dag_node_kind(from_node),
1643                         from_root->rev, from_canonpath, scratch_pool));
1644    }
1645  else
1646    {
1647      /* See IZ Issue #436 */
1648      /* Copying from transaction roots not currently available.
1649
1650         ### cmpilato todo someday: make this not so. :-) Note that
1651         when copying from mutable trees, you have to make sure that
1652         you aren't creating a cyclic graph filesystem, and a simple
1653         referencing operation won't cut it.  Currently, we should not
1654         be able to reach this clause, and the interface reports that
1655         this only works from immutable trees anyway, but JimB has
1656         stated that this requirement need not be necessary in the
1657         future. */
1658
1659      SVN_ERR_MALFUNCTION();
1660    }
1661
1662  return SVN_NO_ERROR;
1663}
1664
1665
1666/* Create a copy of FROM_PATH in FROM_ROOT named TO_PATH in TO_ROOT.
1667   If FROM_PATH is a directory, copy it recursively.  Temporary
1668   allocations are from SCRATCH_POOL.*/
1669static svn_error_t *
1670x_copy(svn_fs_root_t *from_root,
1671       const char *from_path,
1672       svn_fs_root_t *to_root,
1673       const char *to_path,
1674       apr_pool_t *scratch_pool)
1675{
1676  apr_pool_t *subpool = svn_pool_create(scratch_pool);
1677
1678  SVN_ERR(copy_helper(from_root,
1679                      svn_fs__canonicalize_abspath(from_path, subpool),
1680                      to_root,
1681                      svn_fs__canonicalize_abspath(to_path, subpool),
1682                      TRUE, subpool));
1683
1684  svn_pool_destroy(subpool);
1685
1686  return SVN_NO_ERROR;
1687}
1688
1689
1690/* Create a copy of FROM_PATH in FROM_ROOT named TO_PATH in TO_ROOT.
1691   If FROM_PATH is a directory, copy it recursively.  No history is
1692   preserved.  Temporary allocations are from SCRATCH_POOL. */
1693static svn_error_t *
1694x_revision_link(svn_fs_root_t *from_root,
1695                svn_fs_root_t *to_root,
1696                const char *path,
1697                apr_pool_t *scratch_pool)
1698{
1699  apr_pool_t *subpool;
1700
1701  if (! to_root->is_txn_root)
1702    return SVN_FS__NOT_TXN(to_root);
1703
1704  subpool = svn_pool_create(scratch_pool);
1705
1706  path = svn_fs__canonicalize_abspath(path, subpool);
1707  SVN_ERR(copy_helper(from_root, path, to_root, path, FALSE, subpool));
1708
1709  svn_pool_destroy(subpool);
1710
1711  return SVN_NO_ERROR;
1712}
1713
1714
1715/* Discover the copy ancestry of PATH under ROOT.  Return a relevant
1716   ancestor/revision combination in *PATH_P and *REV_P.  Temporary
1717   allocations are in POOL. */
1718static svn_error_t *
1719x_copied_from(svn_revnum_t *rev_p,
1720              const char **path_p,
1721              svn_fs_root_t *root,
1722              const char *path,
1723              apr_pool_t *pool)
1724{
1725  dag_node_t *node;
1726
1727  /* There is no cached entry, look it up the old-fashioned way. */
1728  SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root, path, pool));
1729  *rev_p = svn_fs_x__dag_get_copyfrom_rev(node);
1730  *path_p = svn_fs_x__dag_get_copyfrom_path(node);
1731
1732  return SVN_NO_ERROR;
1733}
1734
1735
1736
1737/* Files.  */
1738
1739/* Create the empty file PATH under ROOT.  Temporary allocations are
1740   in SCRATCH_POOL. */
1741static svn_error_t *
1742x_make_file(svn_fs_root_t *root,
1743            const char *path,
1744            apr_pool_t *scratch_pool)
1745{
1746  svn_fs_x__dag_path_t *dag_path;
1747  dag_node_t *child;
1748  svn_fs_x__txn_id_t txn_id = svn_fs_x__root_txn_id(root);
1749  apr_pool_t *subpool = svn_pool_create(scratch_pool);
1750
1751  SVN_ERR(svn_fs_x__get_dag_path(&dag_path, root, path,
1752                                 svn_fs_x__dag_path_last_optional,
1753                                 TRUE, subpool, subpool));
1754
1755  /* If there's already a file by that name, complain.
1756     This also catches the case of trying to make a file named `/'.  */
1757  if (dag_path->node)
1758    return SVN_FS__ALREADY_EXISTS(root, path);
1759
1760  /* Check (non-recursively) to see if path is locked;  if so, check
1761     that we can use it. */
1762  if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
1763    SVN_ERR(svn_fs_x__allow_locked_operation(path, root->fs, FALSE, FALSE,
1764                                             subpool));
1765
1766  /* Create the file.  */
1767  SVN_ERR(svn_fs_x__make_path_mutable(root, dag_path->parent, path, subpool,
1768                                      subpool));
1769  SVN_ERR(svn_fs_x__dag_make_file(&child,
1770                                  dag_path->parent->node,
1771                                  parent_path_path(dag_path->parent,
1772                                                   subpool),
1773                                  dag_path->entry,
1774                                  txn_id,
1775                                  subpool, subpool));
1776
1777  /* Add this file to the path cache. */
1778  svn_fs_x__update_dag_cache(child);
1779
1780  /* Make a record of this modification in the changes table. */
1781  SVN_ERR(add_change(root->fs, txn_id, path,
1782                     svn_fs_path_change_add, TRUE, FALSE, FALSE,
1783                     svn_node_file, SVN_INVALID_REVNUM, NULL, subpool));
1784
1785  svn_pool_destroy(subpool);
1786  return SVN_NO_ERROR;
1787}
1788
1789
1790/* Set *LENGTH_P to the size of the file PATH under ROOT.  Temporary
1791   allocations are in SCRATCH_POOL. */
1792static svn_error_t *
1793x_file_length(svn_filesize_t *length_p,
1794              svn_fs_root_t *root,
1795              const char *path,
1796              apr_pool_t *scratch_pool)
1797{
1798  dag_node_t *file;
1799
1800  /* First create a dag_node_t from the root/path pair. */
1801  SVN_ERR(svn_fs_x__get_temp_dag_node(&file, root, path, scratch_pool));
1802
1803  /* Now fetch its length */
1804  return svn_fs_x__dag_file_length(length_p, file);
1805}
1806
1807
1808/* Set *CHECKSUM to the checksum of type KIND for PATH under ROOT, or
1809   NULL if that information isn't available.  Temporary allocations
1810   are from POOL. */
1811static svn_error_t *
1812x_file_checksum(svn_checksum_t **checksum,
1813                svn_checksum_kind_t kind,
1814                svn_fs_root_t *root,
1815                const char *path,
1816                apr_pool_t *pool)
1817{
1818  dag_node_t *file;
1819
1820  SVN_ERR(svn_fs_x__get_temp_dag_node(&file, root, path, pool));
1821  return svn_fs_x__dag_file_checksum(checksum, file, kind, pool);
1822}
1823
1824
1825/* --- Machinery for svn_fs_file_contents() ---  */
1826
1827/* Set *CONTENTS to a readable stream that will return the contents of
1828   PATH under ROOT.  The stream is allocated in POOL. */
1829static svn_error_t *
1830x_file_contents(svn_stream_t **contents,
1831                svn_fs_root_t *root,
1832                const char *path,
1833                apr_pool_t *pool)
1834{
1835  dag_node_t *node;
1836  svn_stream_t *file_stream;
1837
1838  /* First create a dag_node_t from the root/path pair. */
1839  SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root, path, pool));
1840
1841  /* Then create a readable stream from the dag_node_t. */
1842  SVN_ERR(svn_fs_x__dag_get_contents(&file_stream, node, pool));
1843
1844  *contents = file_stream;
1845  return SVN_NO_ERROR;
1846}
1847
1848/* --- End machinery for svn_fs_file_contents() ---  */
1849
1850
1851/* --- Machinery for svn_fs_try_process_file_contents() ---  */
1852
1853static svn_error_t *
1854x_try_process_file_contents(svn_boolean_t *success,
1855                            svn_fs_root_t *root,
1856                            const char *path,
1857                            svn_fs_process_contents_func_t processor,
1858                            void* baton,
1859                            apr_pool_t *pool)
1860{
1861  dag_node_t *node;
1862  SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root, path, pool));
1863
1864  return svn_fs_x__dag_try_process_file_contents(success, node,
1865                                                 processor, baton, pool);
1866}
1867
1868/* --- End machinery for svn_fs_try_process_file_contents() ---  */
1869
1870
1871/* --- Machinery for svn_fs_apply_textdelta() ---  */
1872
1873
1874/* Local baton type for all the helper functions below. */
1875typedef struct txdelta_baton_t
1876{
1877  /* This is the custom-built window consumer given to us by the delta
1878     library;  it uniquely knows how to read data from our designated
1879     "source" stream, interpret the window, and write data to our
1880     designated "target" stream (in this case, our repos file.) */
1881  svn_txdelta_window_handler_t interpreter;
1882  void *interpreter_baton;
1883
1884  /* The original file info */
1885  svn_fs_root_t *root;
1886  const char *path;
1887
1888  /* Derived from the file info */
1889  dag_node_t *node;
1890
1891  svn_stream_t *source_stream;
1892  svn_stream_t *target_stream;
1893
1894  /* MD5 digest for the base text against which a delta is to be
1895     applied, and for the resultant fulltext, respectively.  Either or
1896     both may be null, in which case ignored. */
1897  svn_checksum_t *base_checksum;
1898  svn_checksum_t *result_checksum;
1899
1900  /* Pool used by db txns */
1901  apr_pool_t *pool;
1902
1903} txdelta_baton_t;
1904
1905
1906/* The main window handler returned by svn_fs_apply_textdelta. */
1907static svn_error_t *
1908window_consumer(svn_txdelta_window_t *window, void *baton)
1909{
1910  txdelta_baton_t *tb = (txdelta_baton_t *) baton;
1911
1912  /* Send the window right through to the custom window interpreter.
1913     In theory, the interpreter will then write more data to
1914     cb->target_string. */
1915  SVN_ERR(tb->interpreter(window, tb->interpreter_baton));
1916
1917  /* Is the window NULL?  If so, we're done.  The stream has already been
1918     closed by the interpreter. */
1919  if (! window)
1920    SVN_ERR(svn_fs_x__dag_finalize_edits(tb->node, tb->result_checksum,
1921                                         tb->pool));
1922
1923  return SVN_NO_ERROR;
1924}
1925
1926/* Helper function for fs_apply_textdelta.  BATON is of type
1927   txdelta_baton_t. */
1928static svn_error_t *
1929apply_textdelta(void *baton,
1930                apr_pool_t *scratch_pool)
1931{
1932  txdelta_baton_t *tb = (txdelta_baton_t *) baton;
1933  svn_fs_x__dag_path_t *dag_path;
1934  svn_fs_x__txn_id_t txn_id = svn_fs_x__root_txn_id(tb->root);
1935
1936  /* Call open_path with no flags, as we want this to return an error
1937     if the node for which we are searching doesn't exist. */
1938  SVN_ERR(svn_fs_x__get_dag_path(&dag_path, tb->root, tb->path, 0, TRUE,
1939                                 scratch_pool, scratch_pool));
1940
1941  /* Check (non-recursively) to see if path is locked; if so, check
1942     that we can use it. */
1943  if (tb->root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
1944    SVN_ERR(svn_fs_x__allow_locked_operation(tb->path, tb->root->fs,
1945                                             FALSE, FALSE, scratch_pool));
1946
1947  /* Now, make sure this path is mutable. */
1948  SVN_ERR(svn_fs_x__make_path_mutable(tb->root, dag_path, tb->path,
1949                                      scratch_pool, scratch_pool));
1950  tb->node = svn_fs_x__dag_dup(dag_path->node, tb->pool);
1951
1952  if (tb->base_checksum)
1953    {
1954      svn_checksum_t *checksum;
1955
1956      /* Until we finalize the node, its data_key points to the old
1957         contents, in other words, the base text. */
1958      SVN_ERR(svn_fs_x__dag_file_checksum(&checksum, tb->node,
1959                                          tb->base_checksum->kind,
1960                                          scratch_pool));
1961      if (!svn_checksum_match(tb->base_checksum, checksum))
1962        return svn_checksum_mismatch_err(tb->base_checksum, checksum,
1963                                         scratch_pool,
1964                                         _("Base checksum mismatch on '%s'"),
1965                                         tb->path);
1966    }
1967
1968  /* Make a readable "source" stream out of the current contents of
1969     ROOT/PATH; obviously, this must done in the context of a db_txn.
1970     The stream is returned in tb->source_stream. */
1971  SVN_ERR(svn_fs_x__dag_get_contents(&(tb->source_stream),
1972                                     tb->node, tb->pool));
1973
1974  /* Make a writable "target" stream */
1975  SVN_ERR(svn_fs_x__dag_get_edit_stream(&(tb->target_stream), tb->node,
1976                                        tb->pool));
1977
1978  /* Now, create a custom window handler that uses our two streams. */
1979  svn_txdelta_apply(tb->source_stream,
1980                    tb->target_stream,
1981                    NULL,
1982                    tb->path,
1983                    tb->pool,
1984                    &(tb->interpreter),
1985                    &(tb->interpreter_baton));
1986
1987  /* Make a record of this modification in the changes table. */
1988  return add_change(tb->root->fs, txn_id, tb->path,
1989                    svn_fs_path_change_modify, TRUE, FALSE, FALSE,
1990                    svn_node_file, SVN_INVALID_REVNUM, NULL, scratch_pool);
1991}
1992
1993
1994/* Set *CONTENTS_P and *CONTENTS_BATON_P to a window handler and baton
1995   that will accept text delta windows to modify the contents of PATH
1996   under ROOT.  Allocations are in POOL. */
1997static svn_error_t *
1998x_apply_textdelta(svn_txdelta_window_handler_t *contents_p,
1999                  void **contents_baton_p,
2000                  svn_fs_root_t *root,
2001                  const char *path,
2002                  svn_checksum_t *base_checksum,
2003                  svn_checksum_t *result_checksum,
2004                  apr_pool_t *pool)
2005{
2006  apr_pool_t *scratch_pool = svn_pool_create(pool);
2007  txdelta_baton_t *tb = apr_pcalloc(pool, sizeof(*tb));
2008
2009  tb->root = root;
2010  tb->path = svn_fs__canonicalize_abspath(path, pool);
2011  tb->pool = pool;
2012  tb->base_checksum = svn_checksum_dup(base_checksum, pool);
2013  tb->result_checksum = svn_checksum_dup(result_checksum, pool);
2014
2015  SVN_ERR(apply_textdelta(tb, scratch_pool));
2016
2017  *contents_p = window_consumer;
2018  *contents_baton_p = tb;
2019
2020  svn_pool_destroy(scratch_pool);
2021  return SVN_NO_ERROR;
2022}
2023
2024/* --- End machinery for svn_fs_apply_textdelta() ---  */
2025
2026/* --- Machinery for svn_fs_apply_text() ---  */
2027
2028/* Baton for svn_fs_apply_text(). */
2029typedef struct text_baton_t
2030{
2031  /* The original file info */
2032  svn_fs_root_t *root;
2033  const char *path;
2034
2035  /* Derived from the file info */
2036  dag_node_t *node;
2037
2038  /* The returned stream that will accept the file's new contents. */
2039  svn_stream_t *stream;
2040
2041  /* The actual fs stream that the returned stream will write to. */
2042  svn_stream_t *file_stream;
2043
2044  /* MD5 digest for the final fulltext written to the file.  May
2045     be null, in which case ignored. */
2046  svn_checksum_t *result_checksum;
2047
2048  /* Pool used by db txns */
2049  apr_pool_t *pool;
2050} text_baton_t;
2051
2052
2053/* A wrapper around svn_fs_x__dag_finalize_edits, but for
2054 * fulltext data, not text deltas.  Closes BATON->file_stream.
2055 *
2056 * Note: If you're confused about how this function relates to another
2057 * of similar name, think of it this way:
2058 *
2059 * svn_fs_apply_textdelta() ==> ... ==> txn_body_txdelta_finalize_edits()
2060 * svn_fs_apply_text()      ==> ... ==> txn_body_fulltext_finalize_edits()
2061 */
2062
2063/* Write function for the publicly returned stream. */
2064static svn_error_t *
2065text_stream_writer(void *baton,
2066                   const char *data,
2067                   apr_size_t *len)
2068{
2069  text_baton_t *tb = baton;
2070
2071  /* Psst, here's some data.  Pass it on to the -real- file stream. */
2072  return svn_stream_write(tb->file_stream, data, len);
2073}
2074
2075/* Close function for the publically returned stream. */
2076static svn_error_t *
2077text_stream_closer(void *baton)
2078{
2079  text_baton_t *tb = baton;
2080
2081  /* Close the internal-use stream.  ### This used to be inside of
2082     txn_body_fulltext_finalize_edits(), but that invoked a nested
2083     Berkeley DB transaction -- scandalous! */
2084  SVN_ERR(svn_stream_close(tb->file_stream));
2085
2086  /* Need to tell fs that we're done sending text */
2087  return svn_fs_x__dag_finalize_edits(tb->node, tb->result_checksum,
2088                                       tb->pool);
2089}
2090
2091
2092/* Helper function for fs_apply_text.  BATON is of type
2093   text_baton_t. */
2094static svn_error_t *
2095apply_text(void *baton,
2096           apr_pool_t *scratch_pool)
2097{
2098  text_baton_t *tb = baton;
2099  svn_fs_x__dag_path_t *dag_path;
2100  svn_fs_x__txn_id_t txn_id = svn_fs_x__root_txn_id(tb->root);
2101
2102  /* Call open_path with no flags, as we want this to return an error
2103     if the node for which we are searching doesn't exist. */
2104  SVN_ERR(svn_fs_x__get_dag_path(&dag_path, tb->root, tb->path, 0, TRUE,
2105                                 scratch_pool, scratch_pool));
2106
2107  /* Check (non-recursively) to see if path is locked; if so, check
2108     that we can use it. */
2109  if (tb->root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
2110    SVN_ERR(svn_fs_x__allow_locked_operation(tb->path, tb->root->fs,
2111                                             FALSE, FALSE, scratch_pool));
2112
2113  /* Now, make sure this path is mutable. */
2114  SVN_ERR(svn_fs_x__make_path_mutable(tb->root, dag_path, tb->path,
2115                                      scratch_pool, scratch_pool));
2116  tb->node = svn_fs_x__dag_dup(dag_path->node, tb->pool);
2117
2118  /* Make a writable stream for replacing the file's text. */
2119  SVN_ERR(svn_fs_x__dag_get_edit_stream(&(tb->file_stream), tb->node,
2120                                        tb->pool));
2121
2122  /* Create a 'returnable' stream which writes to the file_stream. */
2123  tb->stream = svn_stream_create(tb, tb->pool);
2124  svn_stream_set_write(tb->stream, text_stream_writer);
2125  svn_stream_set_close(tb->stream, text_stream_closer);
2126
2127  /* Make a record of this modification in the changes table. */
2128  return add_change(tb->root->fs, txn_id, tb->path,
2129                    svn_fs_path_change_modify, TRUE, FALSE, FALSE,
2130                    svn_node_file, SVN_INVALID_REVNUM, NULL, scratch_pool);
2131}
2132
2133
2134/* Return a writable stream that will set the contents of PATH under
2135   ROOT.  RESULT_CHECKSUM is the MD5 checksum of the final result.
2136   Temporary allocations are in POOL. */
2137static svn_error_t *
2138x_apply_text(svn_stream_t **contents_p,
2139             svn_fs_root_t *root,
2140             const char *path,
2141             svn_checksum_t *result_checksum,
2142             apr_pool_t *pool)
2143{
2144  apr_pool_t *scratch_pool = svn_pool_create(pool);
2145  text_baton_t *tb = apr_pcalloc(pool, sizeof(*tb));
2146
2147  tb->root = root;
2148  tb->path = svn_fs__canonicalize_abspath(path, pool);
2149  tb->pool = pool;
2150  tb->result_checksum = svn_checksum_dup(result_checksum, pool);
2151
2152  SVN_ERR(apply_text(tb, scratch_pool));
2153
2154  *contents_p = tb->stream;
2155
2156  svn_pool_destroy(scratch_pool);
2157  return SVN_NO_ERROR;
2158}
2159
2160/* --- End machinery for svn_fs_apply_text() ---  */
2161
2162
2163/* Check if the contents of PATH1 under ROOT1 are different from the
2164   contents of PATH2 under ROOT2.  If they are different set
2165   *CHANGED_P to TRUE, otherwise set it to FALSE. */
2166static svn_error_t *
2167x_contents_changed(svn_boolean_t *changed_p,
2168                   svn_fs_root_t *root1,
2169                   const char *path1,
2170                   svn_fs_root_t *root2,
2171                   const char *path2,
2172                   svn_boolean_t strict,
2173                   apr_pool_t *scratch_pool)
2174{
2175  dag_node_t *node1, *node2;
2176  apr_pool_t *subpool = svn_pool_create(scratch_pool);
2177
2178  /* Check that roots are in the same fs. */
2179  if (root1->fs != root2->fs)
2180    return svn_error_create
2181      (SVN_ERR_FS_GENERAL, NULL,
2182       _("Cannot compare file contents between two different filesystems"));
2183
2184  SVN_ERR(svn_fs_x__get_dag_node(&node1, root1, path1, subpool, subpool));
2185  /* Make sure that path is file. */
2186  if (svn_fs_x__dag_node_kind(node1) != svn_node_file)
2187    return svn_error_createf
2188      (SVN_ERR_FS_GENERAL, NULL, _("'%s' is not a file"), path1);
2189
2190  SVN_ERR(svn_fs_x__get_temp_dag_node(&node2, root2, path2, subpool));
2191  /* Make sure that path is file. */
2192  if (svn_fs_x__dag_node_kind(node2) != svn_node_file)
2193    return svn_error_createf
2194      (SVN_ERR_FS_GENERAL, NULL, _("'%s' is not a file"), path2);
2195
2196  SVN_ERR(svn_fs_x__dag_things_different(NULL, changed_p, node1, node2,
2197                                         strict, subpool));
2198
2199  svn_pool_destroy(subpool);
2200  return SVN_NO_ERROR;
2201}
2202
2203
2204
2205/* Public interface to computing file text deltas.  */
2206
2207static svn_error_t *
2208x_get_file_delta_stream(svn_txdelta_stream_t **stream_p,
2209                        svn_fs_root_t *source_root,
2210                        const char *source_path,
2211                        svn_fs_root_t *target_root,
2212                        const char *target_path,
2213                        apr_pool_t *pool)
2214{
2215  dag_node_t *source_node, *target_node;
2216  apr_pool_t *scratch_pool = svn_pool_create(pool);
2217
2218  if (source_root && source_path)
2219    SVN_ERR(svn_fs_x__get_dag_node(&source_node, source_root, source_path,
2220                                   scratch_pool, scratch_pool));
2221  else
2222    source_node = NULL;
2223  SVN_ERR(svn_fs_x__get_temp_dag_node(&target_node, target_root, target_path,
2224                                      scratch_pool));
2225
2226  /* Create a delta stream that turns the source into the target.  */
2227  SVN_ERR(svn_fs_x__dag_get_file_delta_stream(stream_p, source_node,
2228                                              target_node, pool,
2229                                              scratch_pool));
2230
2231  svn_pool_destroy(scratch_pool);
2232  return SVN_NO_ERROR;
2233}
2234
2235
2236
2237/* Finding Changes */
2238
2239/* Implement changes_iterator_vtable_t.get for in-txn change lists.
2240   There is no specific FSAP data type, a simple APR hash iterator
2241   to the underlying collection is sufficient. */
2242static svn_error_t *
2243x_txn_changes_iterator_get(svn_fs_path_change3_t **change,
2244                           svn_fs_path_change_iterator_t *iterator)
2245{
2246  apr_hash_index_t *hi = iterator->fsap_data;
2247
2248  if (hi)
2249    {
2250      *change = apr_hash_this_val(hi);
2251      iterator->fsap_data = apr_hash_next(hi);
2252    }
2253  else
2254    {
2255      *change = NULL;
2256    }
2257
2258  return SVN_NO_ERROR;
2259}
2260
2261static changes_iterator_vtable_t txn_changes_iterator_vtable =
2262{
2263  x_txn_changes_iterator_get
2264};
2265
2266/* FSAP data structure for in-revision changes list iterators. */
2267typedef struct fs_revision_changes_iterator_data_t
2268{
2269  /* Context that tells the lower layers from where to fetch the next
2270     block of changes. */
2271  svn_fs_x__changes_context_t *context;
2272
2273  /* Changes to send. */
2274  apr_array_header_t *changes;
2275
2276  /* Current indexes within CHANGES. */
2277  int idx;
2278
2279  /* A cleanable scratch pool in case we need one.
2280     No further sub-pool creation necessary. */
2281  apr_pool_t *scratch_pool;
2282} fs_revision_changes_iterator_data_t;
2283
2284static svn_error_t *
2285x_revision_changes_iterator_get(svn_fs_path_change3_t **change,
2286                                svn_fs_path_change_iterator_t *iterator)
2287{
2288  fs_revision_changes_iterator_data_t *data = iterator->fsap_data;
2289
2290  /* If we exhausted our block of changes and did not reach the end of the
2291     list, yet, fetch the next block.  Note that that block may be empty. */
2292  if ((data->idx >= data->changes->nelts) && !data->context->eol)
2293    {
2294      apr_pool_t *changes_pool = data->changes->pool;
2295
2296      /* Drop old changes block, read new block. */
2297      svn_pool_clear(changes_pool);
2298      SVN_ERR(svn_fs_x__get_changes(&data->changes, data->context,
2299                                    changes_pool, data->scratch_pool));
2300      data->idx = 0;
2301
2302      /* Immediately release any temporary data. */
2303      svn_pool_clear(data->scratch_pool);
2304    }
2305
2306  if (data->idx < data->changes->nelts)
2307    {
2308      *change = APR_ARRAY_IDX(data->changes, data->idx,
2309                              svn_fs_x__change_t *);
2310      ++data->idx;
2311    }
2312  else
2313    {
2314      *change = NULL;
2315    }
2316
2317  return SVN_NO_ERROR;
2318}
2319
2320static changes_iterator_vtable_t rev_changes_iterator_vtable =
2321{
2322  x_revision_changes_iterator_get
2323};
2324
2325static svn_error_t *
2326x_report_changes(svn_fs_path_change_iterator_t **iterator,
2327                 svn_fs_root_t *root,
2328                 apr_pool_t *result_pool,
2329                 apr_pool_t *scratch_pool)
2330{
2331  svn_fs_path_change_iterator_t *result = apr_pcalloc(result_pool,
2332                                                      sizeof(*result));
2333  if (root->is_txn_root)
2334    {
2335      apr_hash_t *changed_paths;
2336      SVN_ERR(svn_fs_x__txn_changes_fetch(&changed_paths, root->fs,
2337                                          svn_fs_x__root_txn_id(root),
2338                                          result_pool));
2339
2340      result->fsap_data = apr_hash_first(result_pool, changed_paths);
2341      result->vtable = &txn_changes_iterator_vtable;
2342    }
2343  else
2344    {
2345      /* The block of changes that we retrieve need to live in a separately
2346         cleanable pool. */
2347      apr_pool_t *changes_pool = svn_pool_create(result_pool);
2348
2349      /* Our iteration context info. */
2350      fs_revision_changes_iterator_data_t *data = apr_pcalloc(result_pool,
2351                                                              sizeof(*data));
2352
2353      /* This pool must remain valid as long as ITERATOR lives but will
2354         be used only for temporary allocations and will be cleaned up
2355         frequently.  So, this must be a sub-pool of RESULT_POOL. */
2356      data->scratch_pool = svn_pool_create(result_pool);
2357
2358      /* Fetch the first block of data. */
2359      SVN_ERR(svn_fs_x__create_changes_context(&data->context,
2360                                               root->fs, root->rev,
2361                                               result_pool, scratch_pool));
2362      SVN_ERR(svn_fs_x__get_changes(&data->changes, data->context,
2363                                    changes_pool, scratch_pool));
2364
2365      /* Return the fully initialized object. */
2366      result->fsap_data = data;
2367      result->vtable = &rev_changes_iterator_vtable;
2368    }
2369
2370  *iterator = result;
2371
2372  return SVN_NO_ERROR;
2373}
2374
2375
2376/* Our coolio opaque history object. */
2377typedef struct fs_history_data_t
2378{
2379  /* filesystem object */
2380  svn_fs_t *fs;
2381
2382  /* path and revision of historical location */
2383  const char *path;
2384  svn_revnum_t revision;
2385
2386  /* internal-use hints about where to resume the history search. */
2387  const char *path_hint;
2388  svn_revnum_t rev_hint;
2389
2390  /* FALSE until the first call to svn_fs_history_prev(). */
2391  svn_boolean_t is_interesting;
2392
2393  /* If not SVN_INVALID_REVISION, we know that the next copy operation
2394     is at this revision. */
2395  svn_revnum_t next_copy;
2396
2397  /* If used, see svn_fs_x__id_used, this is the noderev ID of
2398     PATH@REVISION. */
2399  svn_fs_x__id_t current_id;
2400
2401} fs_history_data_t;
2402
2403static svn_fs_history_t *
2404assemble_history(svn_fs_t *fs,
2405                 const char *path,
2406                 svn_revnum_t revision,
2407                 svn_boolean_t is_interesting,
2408                 const char *path_hint,
2409                 svn_revnum_t rev_hint,
2410                 svn_revnum_t next_copy,
2411                 const svn_fs_x__id_t *current_id,
2412                 apr_pool_t *result_pool);
2413
2414
2415/* Set *HISTORY_P to an opaque node history object which represents
2416   PATH under ROOT.  ROOT must be a revision root.  Use POOL for all
2417   allocations. */
2418static svn_error_t *
2419x_node_history(svn_fs_history_t **history_p,
2420               svn_fs_root_t *root,
2421               const char *path,
2422               apr_pool_t *result_pool,
2423               apr_pool_t *scratch_pool)
2424{
2425  svn_node_kind_t kind;
2426
2427  /* We require a revision root. */
2428  if (root->is_txn_root)
2429    return svn_error_create(SVN_ERR_FS_NOT_REVISION_ROOT, NULL, NULL);
2430
2431  /* And we require that the path exist in the root. */
2432  SVN_ERR(svn_fs_x__check_path(&kind, root, path, scratch_pool));
2433  if (kind == svn_node_none)
2434    return SVN_FS__NOT_FOUND(root, path);
2435
2436  /* Okay, all seems well.  Build our history object and return it. */
2437  *history_p = assemble_history(root->fs, path, root->rev, FALSE, NULL,
2438                                SVN_INVALID_REVNUM, SVN_INVALID_REVNUM,
2439                                NULL, result_pool);
2440  return SVN_NO_ERROR;
2441}
2442
2443/* Find the youngest copyroot for path DAG_PATH or its parents in
2444   filesystem FS, and store the copyroot in *REV_P and *PATH_P. */
2445static svn_error_t *
2446find_youngest_copyroot(svn_revnum_t *rev_p,
2447                       const char **path_p,
2448                       svn_fs_t *fs,
2449                       svn_fs_x__dag_path_t *dag_path)
2450{
2451  svn_revnum_t rev_mine;
2452  svn_revnum_t rev_parent = SVN_INVALID_REVNUM;
2453  const char *path_mine;
2454  const char *path_parent = NULL;
2455
2456  /* First find our parent's youngest copyroot. */
2457  if (dag_path->parent)
2458    SVN_ERR(find_youngest_copyroot(&rev_parent, &path_parent, fs,
2459                                   dag_path->parent));
2460
2461  /* Find our copyroot. */
2462  svn_fs_x__dag_get_copyroot(&rev_mine, &path_mine, dag_path->node);
2463
2464  /* If a parent and child were copied to in the same revision, prefer
2465     the child copy target, since it is the copy relevant to the
2466     history of the child. */
2467  if (rev_mine >= rev_parent)
2468    {
2469      *rev_p = rev_mine;
2470      *path_p = path_mine;
2471    }
2472  else
2473    {
2474      *rev_p = rev_parent;
2475      *path_p = path_parent;
2476    }
2477
2478  return SVN_NO_ERROR;
2479}
2480
2481
2482static svn_error_t *
2483x_closest_copy(svn_fs_root_t **root_p,
2484               const char **path_p,
2485               svn_fs_root_t *root,
2486               const char *path,
2487               apr_pool_t *pool)
2488{
2489  svn_fs_t *fs = root->fs;
2490  svn_fs_x__dag_path_t *dag_path, *copy_dst_dag_path;
2491  svn_revnum_t copy_dst_rev, created_rev;
2492  const char *copy_dst_path;
2493  svn_fs_root_t *copy_dst_root;
2494  dag_node_t *copy_dst_node;
2495  apr_pool_t *scratch_pool = svn_pool_create(pool);
2496
2497  /* Initialize return values. */
2498  *root_p = NULL;
2499  *path_p = NULL;
2500
2501  SVN_ERR(svn_fs_x__get_dag_path(&dag_path, root, path, 0, FALSE,
2502                                 scratch_pool, scratch_pool));
2503
2504  /* Find the youngest copyroot in the path of this node-rev, which
2505     will indicate the target of the innermost copy affecting the
2506     node-rev. */
2507  SVN_ERR(find_youngest_copyroot(&copy_dst_rev, &copy_dst_path,
2508                                 fs, dag_path));
2509  if (copy_dst_rev == 0)  /* There are no copies affecting this node-rev. */
2510    {
2511      svn_pool_destroy(scratch_pool);
2512      return SVN_NO_ERROR;
2513    }
2514
2515  /* It is possible that this node was created from scratch at some
2516     revision between COPY_DST_REV and REV.  Make sure that PATH
2517     exists as of COPY_DST_REV and is related to this node-rev. */
2518  SVN_ERR(svn_fs_x__revision_root(&copy_dst_root, fs, copy_dst_rev, pool));
2519  SVN_ERR(svn_fs_x__get_dag_path(&copy_dst_dag_path, copy_dst_root, path,
2520                                 svn_fs_x__dag_path_allow_null, FALSE,
2521                                 scratch_pool, scratch_pool));
2522  if (copy_dst_dag_path == NULL)
2523    {
2524      svn_pool_destroy(scratch_pool);
2525      return SVN_NO_ERROR;
2526    }
2527
2528  copy_dst_node = copy_dst_dag_path->node;
2529  if (!svn_fs_x__dag_related_node(copy_dst_node, dag_path->node))
2530    {
2531      svn_pool_destroy(scratch_pool);
2532      return SVN_NO_ERROR;
2533    }
2534
2535  /* One final check must be done here.  If you copy a directory and
2536     create a new entity somewhere beneath that directory in the same
2537     txn, then we can't claim that the copy affected the new entity.
2538     For example, if you do:
2539
2540        copy dir1 dir2
2541        create dir2/new-thing
2542        commit
2543
2544     then dir2/new-thing was not affected by the copy of dir1 to dir2.
2545     We detect this situation by asking if PATH@COPY_DST_REV's
2546     created-rev is COPY_DST_REV, and that node-revision has no
2547     predecessors, then there is no relevant closest copy.
2548  */
2549  created_rev = svn_fs_x__dag_get_revision(copy_dst_node);
2550  if (created_rev == copy_dst_rev)
2551    if (!svn_fs_x__id_used(svn_fs_x__dag_get_predecessor_id(copy_dst_node)))
2552      {
2553        svn_pool_destroy(scratch_pool);
2554        return SVN_NO_ERROR;
2555      }
2556
2557  /* The copy destination checks out.  Return it. */
2558  *root_p = copy_dst_root;
2559  *path_p = apr_pstrdup(pool, copy_dst_path);
2560
2561  svn_pool_destroy(scratch_pool);
2562  return SVN_NO_ERROR;
2563}
2564
2565
2566static svn_error_t *
2567x_node_origin_rev(svn_revnum_t *revision,
2568                  svn_fs_root_t *root,
2569                  const char *path,
2570                  apr_pool_t *scratch_pool)
2571{
2572  svn_fs_x__id_t node_id;
2573  dag_node_t *node;
2574
2575  SVN_ERR(svn_fs_x__get_temp_dag_node(&node, root, path, scratch_pool));
2576  node_id = *svn_fs_x__dag_get_node_id(node);
2577
2578  *revision = svn_fs_x__get_revnum(node_id.change_set);
2579
2580  return SVN_NO_ERROR;
2581}
2582
2583
2584static svn_error_t *
2585history_prev(svn_fs_history_t **prev_history,
2586             svn_fs_history_t *history,
2587             svn_boolean_t cross_copies,
2588             apr_pool_t *result_pool,
2589             apr_pool_t *scratch_pool)
2590{
2591  fs_history_data_t *fhd = history->fsap_data;
2592  const char *commit_path, *src_path, *path = fhd->path;
2593  svn_revnum_t commit_rev, src_rev, dst_rev;
2594  svn_revnum_t revision = fhd->revision;
2595  svn_fs_t *fs = fhd->fs;
2596  svn_fs_x__dag_path_t *dag_path;
2597  dag_node_t *node;
2598  svn_fs_root_t *root;
2599  svn_boolean_t reported = fhd->is_interesting;
2600  svn_revnum_t copyroot_rev;
2601  const char *copyroot_path;
2602  svn_fs_x__id_t pred_id;
2603
2604  /* Initialize our return value. */
2605  *prev_history = NULL;
2606
2607  /* When following history, there tend to be long sections of linear
2608     history where there are no copies at PATH or its parents.  Within
2609     these sections, we only need to follow the node history. */
2610  if (   SVN_IS_VALID_REVNUM(fhd->next_copy)
2611      && revision > fhd->next_copy
2612      && svn_fs_x__id_used(&fhd->current_id))
2613    {
2614      /* We know the last reported node (CURRENT_ID) and the NEXT_COPY
2615         revision is somewhat further in the past. */
2616      svn_fs_x__noderev_t *noderev;
2617      assert(reported);
2618
2619      /* Get the previous node change.  If there is none, then we already
2620         reported the initial addition and this history traversal is done. */
2621      SVN_ERR(svn_fs_x__get_node_revision(&noderev, fs, &fhd->current_id,
2622                                          scratch_pool, scratch_pool));
2623      if (! svn_fs_x__id_used(&noderev->predecessor_id))
2624        return SVN_NO_ERROR;
2625
2626      /* If the previous node change is younger than the next copy, it is
2627         part of the linear history section. */
2628      commit_rev = svn_fs_x__get_revnum(noderev->predecessor_id.change_set);
2629      if (commit_rev > fhd->next_copy)
2630        {
2631          /* Within the linear history, simply report all node changes and
2632             continue with the respective predecessor. */
2633          *prev_history = assemble_history(fs, noderev->created_path,
2634                                           commit_rev, TRUE, NULL,
2635                                           SVN_INVALID_REVNUM,
2636                                           fhd->next_copy,
2637                                           &noderev->predecessor_id,
2638                                           result_pool);
2639
2640          return SVN_NO_ERROR;
2641        }
2642
2643     /* We hit a copy. Fall back to the standard code path. */
2644    }
2645
2646  /* If our last history report left us hints about where to pickup
2647     the chase, then our last report was on the destination of a
2648     copy.  If we are crossing copies, start from those locations,
2649     otherwise, we're all done here.  */
2650  if (fhd->path_hint && SVN_IS_VALID_REVNUM(fhd->rev_hint))
2651    {
2652      reported = FALSE;
2653      if (! cross_copies)
2654        return SVN_NO_ERROR;
2655      path = fhd->path_hint;
2656      revision = fhd->rev_hint;
2657    }
2658
2659  /* Construct a ROOT for the current revision. */
2660  SVN_ERR(svn_fs_x__revision_root(&root, fs, revision, scratch_pool));
2661
2662  /* Open PATH/REVISION, and get its node and a bunch of other
2663     goodies.  */
2664  SVN_ERR(svn_fs_x__get_dag_path(&dag_path, root, path, 0, FALSE,
2665                                 scratch_pool, scratch_pool));
2666  node = dag_path->node;
2667  commit_path = svn_fs_x__dag_get_created_path(node);
2668  commit_rev = svn_fs_x__dag_get_revision(node);
2669  svn_fs_x__id_reset(&pred_id);
2670
2671  /* The Subversion filesystem is written in such a way that a given
2672     line of history may have at most one interesting history point
2673     per filesystem revision.  Either that node was edited (and
2674     possibly copied), or it was copied but not edited.  And a copy
2675     source cannot be from the same revision as its destination.  So,
2676     if our history revision matches its node's commit revision, we
2677     know that ... */
2678  if (revision == commit_rev)
2679    {
2680      if (! reported)
2681        {
2682          /* ... we either have not yet reported on this revision (and
2683             need now to do so) ... */
2684          *prev_history = assemble_history(fs, commit_path,
2685                                           commit_rev, TRUE, NULL,
2686                                           SVN_INVALID_REVNUM,
2687                                           SVN_INVALID_REVNUM, NULL,
2688                                           result_pool);
2689          return SVN_NO_ERROR;
2690        }
2691      else
2692        {
2693          /* ... or we *have* reported on this revision, and must now
2694             progress toward this node's predecessor (unless there is
2695             no predecessor, in which case we're all done!). */
2696          pred_id = *svn_fs_x__dag_get_predecessor_id(node);
2697          if (!svn_fs_x__id_used(&pred_id))
2698            return SVN_NO_ERROR;
2699
2700          /* Replace NODE and friends with the information from its
2701             predecessor. */
2702          SVN_ERR(svn_fs_x__dag_get_node(&node, fs, &pred_id, scratch_pool,
2703                                         scratch_pool));
2704          commit_path = svn_fs_x__dag_get_created_path(node);
2705          commit_rev = svn_fs_x__dag_get_revision(node);
2706        }
2707    }
2708
2709  /* Find the youngest copyroot in the path of this node, including
2710     itself. */
2711  SVN_ERR(find_youngest_copyroot(&copyroot_rev, &copyroot_path, fs,
2712                                 dag_path));
2713
2714  /* Initialize some state variables. */
2715  src_path = NULL;
2716  src_rev = SVN_INVALID_REVNUM;
2717  dst_rev = SVN_INVALID_REVNUM;
2718
2719  if (copyroot_rev > commit_rev)
2720    {
2721      const char *remainder_path;
2722      const char *copy_dst, *copy_src;
2723      svn_fs_root_t *copyroot_root;
2724
2725      SVN_ERR(svn_fs_x__revision_root(&copyroot_root, fs, copyroot_rev,
2726                                       scratch_pool));
2727      SVN_ERR(svn_fs_x__get_temp_dag_node(&node, copyroot_root,
2728                                          copyroot_path, scratch_pool));
2729      copy_dst = svn_fs_x__dag_get_created_path(node);
2730
2731      /* If our current path was the very destination of the copy,
2732         then our new current path will be the copy source.  If our
2733         current path was instead the *child* of the destination of
2734         the copy, then figure out its previous location by taking its
2735         path relative to the copy destination and appending that to
2736         the copy source.  Finally, if our current path doesn't meet
2737         one of these other criteria ... ### for now just fallback to
2738         the old copy hunt algorithm. */
2739      remainder_path = svn_fspath__skip_ancestor(copy_dst, path);
2740
2741      if (remainder_path)
2742        {
2743          /* If we get here, then our current path is the destination
2744             of, or the child of the destination of, a copy.  Fill
2745             in the return values and get outta here.  */
2746          src_rev = svn_fs_x__dag_get_copyfrom_rev(node);
2747          copy_src = svn_fs_x__dag_get_copyfrom_path(node);
2748
2749          dst_rev = copyroot_rev;
2750          src_path = svn_fspath__join(copy_src, remainder_path, scratch_pool);
2751        }
2752    }
2753
2754  /* If we calculated a copy source path and revision, we'll make a
2755     'copy-style' history object. */
2756  if (src_path && SVN_IS_VALID_REVNUM(src_rev))
2757    {
2758      svn_boolean_t retry = FALSE;
2759
2760      /* It's possible for us to find a copy location that is the same
2761         as the history point we've just reported.  If that happens,
2762         we simply need to take another trip through this history
2763         search. */
2764      if ((dst_rev == revision) && reported)
2765        retry = TRUE;
2766
2767      *prev_history = assemble_history(fs, path, dst_rev, ! retry,
2768                                       src_path, src_rev,
2769                                       SVN_INVALID_REVNUM, NULL,
2770                                       result_pool);
2771    }
2772  else
2773    {
2774      /* We know the next copy revision.  If we are not at the copy rev
2775         itself, we will also know the predecessor node ID and the next
2776         invocation will use the optimized "linear history" code path. */
2777      *prev_history = assemble_history(fs, commit_path, commit_rev, TRUE,
2778                                       NULL, SVN_INVALID_REVNUM,
2779                                       copyroot_rev, &pred_id, result_pool);
2780    }
2781
2782  return SVN_NO_ERROR;
2783}
2784
2785
2786/* Implement svn_fs_history_prev, set *PREV_HISTORY_P to a new
2787   svn_fs_history_t object that represents the predecessory of
2788   HISTORY.  If CROSS_COPIES is true, *PREV_HISTORY_P may be related
2789   only through a copy operation.  Perform all allocations in POOL. */
2790static svn_error_t *
2791fs_history_prev(svn_fs_history_t **prev_history_p,
2792                svn_fs_history_t *history,
2793                svn_boolean_t cross_copies,
2794                apr_pool_t *result_pool,
2795                apr_pool_t *scratch_pool)
2796{
2797  svn_fs_history_t *prev_history = NULL;
2798  fs_history_data_t *fhd = history->fsap_data;
2799  svn_fs_t *fs = fhd->fs;
2800
2801  /* Special case: the root directory changes in every single
2802     revision, no exceptions.  And, the root can't be the target (or
2803     child of a target -- duh) of a copy.  So, if that's our path,
2804     then we need only decrement our revision by 1, and there you go. */
2805  if (strcmp(fhd->path, "/") == 0)
2806    {
2807      if (! fhd->is_interesting)
2808        prev_history = assemble_history(fs, "/", fhd->revision,
2809                                        1, NULL, SVN_INVALID_REVNUM,
2810                                        SVN_INVALID_REVNUM, NULL,
2811                                        result_pool);
2812      else if (fhd->revision > 0)
2813        prev_history = assemble_history(fs, "/", fhd->revision - 1,
2814                                        1, NULL, SVN_INVALID_REVNUM,
2815                                        SVN_INVALID_REVNUM, NULL,
2816                                        result_pool);
2817    }
2818  else
2819    {
2820      apr_pool_t *iterpool = svn_pool_create(scratch_pool);
2821      prev_history = history;
2822
2823      while (1)
2824        {
2825          svn_pool_clear(iterpool);
2826          SVN_ERR(history_prev(&prev_history, prev_history, cross_copies,
2827                               result_pool, iterpool));
2828
2829          if (! prev_history)
2830            break;
2831          fhd = prev_history->fsap_data;
2832          if (fhd->is_interesting)
2833            break;
2834        }
2835
2836      svn_pool_destroy(iterpool);
2837    }
2838
2839  *prev_history_p = prev_history;
2840  return SVN_NO_ERROR;
2841}
2842
2843
2844/* Set *PATH and *REVISION to the path and revision for the HISTORY
2845   object.  Allocate *PATH in RESULT_POOL. */
2846static svn_error_t *
2847fs_history_location(const char **path,
2848                    svn_revnum_t *revision,
2849                    svn_fs_history_t *history,
2850                    apr_pool_t *result_pool)
2851{
2852  fs_history_data_t *fhd = history->fsap_data;
2853
2854  *path = apr_pstrdup(result_pool, fhd->path);
2855  *revision = fhd->revision;
2856  return SVN_NO_ERROR;
2857}
2858
2859static history_vtable_t history_vtable = {
2860  fs_history_prev,
2861  fs_history_location
2862};
2863
2864/* Return a new history object (marked as "interesting") for PATH and
2865   REVISION, allocated in RESULT_POOL, and with its members set to the
2866   values of the parameters provided.  Note that PATH and PATH_HINT get
2867   normalized and duplicated in RESULT_POOL. */
2868static svn_fs_history_t *
2869assemble_history(svn_fs_t *fs,
2870                 const char *path,
2871                 svn_revnum_t revision,
2872                 svn_boolean_t is_interesting,
2873                 const char *path_hint,
2874                 svn_revnum_t rev_hint,
2875                 svn_revnum_t next_copy,
2876                 const svn_fs_x__id_t *current_id,
2877                 apr_pool_t *result_pool)
2878{
2879  svn_fs_history_t *history = apr_pcalloc(result_pool, sizeof(*history));
2880  fs_history_data_t *fhd = apr_pcalloc(result_pool, sizeof(*fhd));
2881  fhd->path = svn_fs__canonicalize_abspath(path, result_pool);
2882  fhd->revision = revision;
2883  fhd->is_interesting = is_interesting;
2884  fhd->path_hint = path_hint
2885                 ? svn_fs__canonicalize_abspath(path_hint, result_pool)
2886                 : NULL;
2887  fhd->rev_hint = rev_hint;
2888  fhd->next_copy = next_copy;
2889  fhd->fs = fs;
2890
2891  if (current_id)
2892    fhd->current_id = *current_id;
2893  else
2894    svn_fs_x__id_reset(&fhd->current_id);
2895
2896  history->vtable = &history_vtable;
2897  history->fsap_data = fhd;
2898  return history;
2899}
2900
2901
2902/* mergeinfo queries */
2903
2904
2905/* DIR_DAG is a directory DAG node which has mergeinfo in its
2906   descendants.  This function iterates over its children.  For each
2907   child with immediate mergeinfo, call RECEIVER with it and BATON.
2908   For each child with descendants with mergeinfo, it recurses.  Note
2909   that it does *not* call the action on the path for DIR_DAG itself.
2910
2911   SCRATCH_POOL is used for temporary allocations, including the mergeinfo
2912   hashes passed to actions.
2913 */
2914static svn_error_t *
2915crawl_directory_dag_for_mergeinfo(svn_fs_root_t *root,
2916                                  const char *this_path,
2917                                  dag_node_t *dir_dag,
2918                                  svn_fs_mergeinfo_receiver_t receiver,
2919                                  void *baton,
2920                                  apr_pool_t *scratch_pool)
2921{
2922  apr_array_header_t *entries;
2923  int i;
2924  apr_pool_t *iterpool = svn_pool_create(scratch_pool);
2925
2926  SVN_ERR(svn_fs_x__dag_dir_entries(&entries, dir_dag, scratch_pool,
2927                                    iterpool));
2928  for (i = 0; i < entries->nelts; ++i)
2929    {
2930      svn_fs_x__dirent_t *dirent
2931        = APR_ARRAY_IDX(entries, i, svn_fs_x__dirent_t *);
2932      const char *kid_path;
2933      dag_node_t *kid_dag;
2934
2935      svn_pool_clear(iterpool);
2936
2937      kid_path = svn_fspath__join(this_path, dirent->name, iterpool);
2938      SVN_ERR(svn_fs_x__get_temp_dag_node(&kid_dag, root, kid_path,
2939                                          iterpool));
2940
2941      if (svn_fs_x__dag_has_mergeinfo(kid_dag))
2942        {
2943          /* Save this particular node's mergeinfo. */
2944          apr_hash_t *proplist;
2945          svn_mergeinfo_t kid_mergeinfo;
2946          svn_string_t *mergeinfo_string;
2947          svn_error_t *err;
2948
2949          SVN_ERR(svn_fs_x__dag_get_proplist(&proplist, kid_dag, iterpool,
2950                                             iterpool));
2951          mergeinfo_string = svn_hash_gets(proplist, SVN_PROP_MERGEINFO);
2952          if (!mergeinfo_string)
2953            {
2954              svn_string_t *idstr
2955                = svn_fs_x__id_unparse(&dirent->id, iterpool);
2956              return svn_error_createf
2957                (SVN_ERR_FS_CORRUPT, NULL,
2958                 _("Node-revision #'%s' claims to have mergeinfo but doesn't"),
2959                 idstr->data);
2960            }
2961
2962          /* Issue #3896: If a node has syntactically invalid mergeinfo, then
2963             treat it as if no mergeinfo is present rather than raising a parse
2964             error. */
2965          err = svn_mergeinfo_parse(&kid_mergeinfo,
2966                                    mergeinfo_string->data,
2967                                    iterpool);
2968          if (err)
2969            {
2970              if (err->apr_err == SVN_ERR_MERGEINFO_PARSE_ERROR)
2971                svn_error_clear(err);
2972              else
2973                return svn_error_trace(err);
2974              }
2975          else
2976            {
2977              SVN_ERR(receiver(kid_path, kid_mergeinfo, baton, iterpool));
2978            }
2979        }
2980
2981      if (svn_fs_x__dag_has_descendants_with_mergeinfo(kid_dag))
2982        SVN_ERR(crawl_directory_dag_for_mergeinfo(root,
2983                                                  kid_path,
2984                                                  kid_dag,
2985                                                  receiver,
2986                                                  baton,
2987                                                  iterpool));
2988    }
2989
2990  svn_pool_destroy(iterpool);
2991  return SVN_NO_ERROR;
2992}
2993
2994/* Calculates the mergeinfo for PATH under REV_ROOT using inheritance
2995   type INHERIT.  Returns it in *MERGEINFO, or NULL if there is none.
2996   The result is allocated in RESULT_POOL; SCRATCH_POOL is
2997   used for temporary allocations.
2998 */
2999static svn_error_t *
3000get_mergeinfo_for_path(svn_mergeinfo_t *mergeinfo,
3001                       svn_fs_root_t *rev_root,
3002                       const char *path,
3003                       svn_mergeinfo_inheritance_t inherit,
3004                       svn_boolean_t adjust_inherited_mergeinfo,
3005                       apr_pool_t *result_pool,
3006                       apr_pool_t *scratch_pool)
3007{
3008  svn_fs_x__dag_path_t *dag_path, *nearest_ancestor;
3009  apr_hash_t *proplist;
3010  svn_string_t *mergeinfo_string;
3011
3012  *mergeinfo = NULL;
3013  SVN_ERR(svn_fs_x__get_dag_path(&dag_path, rev_root, path, 0, FALSE,
3014                                 scratch_pool, scratch_pool));
3015
3016  if (inherit == svn_mergeinfo_nearest_ancestor && ! dag_path->parent)
3017    return SVN_NO_ERROR;
3018
3019  if (inherit == svn_mergeinfo_nearest_ancestor)
3020    nearest_ancestor = dag_path->parent;
3021  else
3022    nearest_ancestor = dag_path;
3023
3024  while (TRUE)
3025    {
3026      if (svn_fs_x__dag_has_mergeinfo(nearest_ancestor->node))
3027        break;
3028
3029      /* No need to loop if we're looking for explicit mergeinfo. */
3030      if (inherit == svn_mergeinfo_explicit)
3031        {
3032          return SVN_NO_ERROR;
3033        }
3034
3035      nearest_ancestor = nearest_ancestor->parent;
3036
3037      /* Run out?  There's no mergeinfo. */
3038      if (!nearest_ancestor)
3039        {
3040          return SVN_NO_ERROR;
3041        }
3042    }
3043
3044  SVN_ERR(svn_fs_x__dag_get_proplist(&proplist, nearest_ancestor->node,
3045                                     scratch_pool, scratch_pool));
3046  mergeinfo_string = svn_hash_gets(proplist, SVN_PROP_MERGEINFO);
3047  if (!mergeinfo_string)
3048    return svn_error_createf
3049      (SVN_ERR_FS_CORRUPT, NULL,
3050       _("Node-revision '%s@%ld' claims to have mergeinfo but doesn't"),
3051       parent_path_path(nearest_ancestor, scratch_pool), rev_root->rev);
3052
3053  /* Parse the mergeinfo; store the result in *MERGEINFO. */
3054  {
3055    /* Issue #3896: If a node has syntactically invalid mergeinfo, then
3056       treat it as if no mergeinfo is present rather than raising a parse
3057       error. */
3058    svn_error_t *err = svn_mergeinfo_parse(mergeinfo,
3059                                           mergeinfo_string->data,
3060                                           result_pool);
3061    if (err)
3062      {
3063        if (err->apr_err == SVN_ERR_MERGEINFO_PARSE_ERROR)
3064          {
3065            svn_error_clear(err);
3066            err = NULL;
3067            *mergeinfo = NULL;
3068          }
3069        return svn_error_trace(err);
3070      }
3071  }
3072
3073  /* If our nearest ancestor is the very path we inquired about, we
3074     can return the mergeinfo results directly.  Otherwise, we're
3075     inheriting the mergeinfo, so we need to a) remove non-inheritable
3076     ranges and b) telescope the merged-from paths. */
3077  if (adjust_inherited_mergeinfo && (nearest_ancestor != dag_path))
3078    {
3079      svn_mergeinfo_t tmp_mergeinfo;
3080
3081      SVN_ERR(svn_mergeinfo_inheritable2(&tmp_mergeinfo, *mergeinfo,
3082                                         NULL, SVN_INVALID_REVNUM,
3083                                         SVN_INVALID_REVNUM, TRUE,
3084                                         scratch_pool, scratch_pool));
3085      SVN_ERR(svn_fs__append_to_merged_froms(mergeinfo, tmp_mergeinfo,
3086                                             parent_path_relpath(
3087                                               dag_path, nearest_ancestor,
3088                                               scratch_pool),
3089                                             result_pool));
3090    }
3091
3092  return SVN_NO_ERROR;
3093}
3094
3095/* Invoke RECEIVER with BATON for each mergeinfo found on descendants of
3096   PATH (but not PATH itself).  Use SCRATCH_POOL for temporary values. */
3097static svn_error_t *
3098add_descendant_mergeinfo(svn_fs_root_t *root,
3099                         const char *path,
3100                         svn_fs_mergeinfo_receiver_t receiver,
3101                         void *baton,
3102                         apr_pool_t *scratch_pool)
3103{
3104  dag_node_t *this_dag;
3105
3106  SVN_ERR(svn_fs_x__get_temp_dag_node(&this_dag, root, path, scratch_pool));
3107  if (svn_fs_x__dag_has_descendants_with_mergeinfo(this_dag))
3108    SVN_ERR(crawl_directory_dag_for_mergeinfo(root,
3109                                              path,
3110                                              this_dag,
3111                                              receiver,
3112                                              baton,
3113                                              scratch_pool));
3114  return SVN_NO_ERROR;
3115}
3116
3117
3118/* Find all the mergeinfo for a set of PATHS under ROOT and report it
3119   through RECEIVER with BATON.  INHERITED, INCLUDE_DESCENDANTS and
3120   ADJUST_INHERITED_MERGEINFO are the same as in the FS API.
3121
3122   Allocate temporary values are allocated in SCRATCH_POOL. */
3123static svn_error_t *
3124get_mergeinfos_for_paths(svn_fs_root_t *root,
3125                         const apr_array_header_t *paths,
3126                         svn_mergeinfo_inheritance_t inherit,
3127                         svn_boolean_t include_descendants,
3128                         svn_boolean_t adjust_inherited_mergeinfo,
3129                         svn_fs_mergeinfo_receiver_t receiver,
3130                         void *baton,
3131                         apr_pool_t *scratch_pool)
3132{
3133  apr_pool_t *iterpool = svn_pool_create(scratch_pool);
3134  int i;
3135
3136  for (i = 0; i < paths->nelts; i++)
3137    {
3138      svn_error_t *err;
3139      svn_mergeinfo_t path_mergeinfo;
3140      const char *path = APR_ARRAY_IDX(paths, i, const char *);
3141
3142      svn_pool_clear(iterpool);
3143
3144      err = get_mergeinfo_for_path(&path_mergeinfo, root, path,
3145                                   inherit, adjust_inherited_mergeinfo,
3146                                   iterpool, iterpool);
3147      if (err)
3148        {
3149          if (err->apr_err == SVN_ERR_MERGEINFO_PARSE_ERROR)
3150            {
3151              svn_error_clear(err);
3152              err = NULL;
3153              path_mergeinfo = NULL;
3154            }
3155          else
3156            {
3157              return svn_error_trace(err);
3158            }
3159        }
3160
3161      if (path_mergeinfo)
3162        SVN_ERR(receiver(path, path_mergeinfo, baton, iterpool));
3163      if (include_descendants)
3164        SVN_ERR(add_descendant_mergeinfo(root, path, receiver, baton,
3165                                         iterpool));
3166    }
3167  svn_pool_destroy(iterpool);
3168
3169  return SVN_NO_ERROR;
3170}
3171
3172
3173/* Implements svn_fs_get_mergeinfo. */
3174static svn_error_t *
3175x_get_mergeinfo(svn_fs_root_t *root,
3176                const apr_array_header_t *paths,
3177                svn_mergeinfo_inheritance_t inherit,
3178                svn_boolean_t include_descendants,
3179                svn_boolean_t adjust_inherited_mergeinfo,
3180                svn_fs_mergeinfo_receiver_t receiver,
3181                void *baton,
3182                apr_pool_t *scratch_pool)
3183{
3184  /* We require a revision root. */
3185  if (root->is_txn_root)
3186    return svn_error_create(SVN_ERR_FS_NOT_REVISION_ROOT, NULL, NULL);
3187
3188  /* Retrieve a path -> mergeinfo hash mapping. */
3189  return get_mergeinfos_for_paths(root, paths, inherit,
3190                                  include_descendants,
3191                                  adjust_inherited_mergeinfo,
3192                                  receiver, baton,
3193                                  scratch_pool);
3194}
3195
3196
3197/* The vtable associated with root objects. */
3198static root_vtable_t root_vtable = {
3199  NULL,
3200  x_report_changes,
3201  svn_fs_x__check_path,
3202  x_node_history,
3203  x_node_id,
3204  x_node_relation,
3205  svn_fs_x__node_created_rev,
3206  x_node_origin_rev,
3207  x_node_created_path,
3208  x_delete_node,
3209  x_copy,
3210  x_revision_link,
3211  x_copied_from,
3212  x_closest_copy,
3213  x_node_prop,
3214  x_node_proplist,
3215  x_node_has_props,
3216  x_change_node_prop,
3217  x_props_changed,
3218  x_dir_entries,
3219  x_dir_optimal_order,
3220  x_make_dir,
3221  x_file_length,
3222  x_file_checksum,
3223  x_file_contents,
3224  x_try_process_file_contents,
3225  x_make_file,
3226  x_apply_textdelta,
3227  x_apply_text,
3228  x_contents_changed,
3229  x_get_file_delta_stream,
3230  x_merge,
3231  x_get_mergeinfo,
3232};
3233
3234/* Construct a new root object in FS, allocated from RESULT_POOL.  */
3235static svn_fs_root_t *
3236make_root(svn_fs_t *fs,
3237          apr_pool_t *result_pool)
3238{
3239  svn_fs_root_t *root = apr_pcalloc(result_pool, sizeof(*root));
3240
3241  root->fs = fs;
3242  root->pool = result_pool;
3243  root->vtable = &root_vtable;
3244
3245  return root;
3246}
3247
3248
3249/* Construct a root object referring to the root of revision REV in FS.
3250   Create the new root in RESULT_POOL.  */
3251static svn_fs_root_t *
3252make_revision_root(svn_fs_t *fs,
3253                   svn_revnum_t rev,
3254                   apr_pool_t *result_pool)
3255{
3256  svn_fs_root_t *root = make_root(fs, result_pool);
3257
3258  root->is_txn_root = FALSE;
3259  root->rev = rev;
3260
3261  return root;
3262}
3263
3264
3265/* Construct a root object referring to the root of the transaction
3266   named TXN and based on revision BASE_REV in FS, with FLAGS to
3267   describe transaction's behavior.  Create the new root in RESULT_POOL.  */
3268static svn_error_t *
3269make_txn_root(svn_fs_root_t **root_p,
3270              svn_fs_t *fs,
3271              svn_fs_x__txn_id_t txn_id,
3272              svn_revnum_t base_rev,
3273              apr_uint32_t flags,
3274              apr_pool_t *result_pool)
3275{
3276  svn_fs_root_t *root = make_root(fs, result_pool);
3277  fs_txn_root_data_t *frd = apr_pcalloc(root->pool, sizeof(*frd));
3278  frd->txn_id = txn_id;
3279
3280  root->is_txn_root = TRUE;
3281  root->txn = svn_fs_x__txn_name(txn_id, root->pool);
3282  root->txn_flags = flags;
3283  root->rev = base_rev;
3284  root->fsap_data = frd;
3285
3286  *root_p = root;
3287  return SVN_NO_ERROR;
3288}
3289
3290
3291
3292/* Verify. */
3293static const char *
3294stringify_node(dag_node_t *node,
3295               apr_pool_t *result_pool)
3296{
3297  /* ### TODO: print some PATH@REV to it, too. */
3298  return svn_fs_x__id_unparse(svn_fs_x__dag_get_id(node), result_pool)->data;
3299}
3300
3301/* Check metadata sanity on NODE, and on its children.  Manually verify
3302   information for DAG nodes in revision REV, and trust the metadata
3303   accuracy for nodes belonging to older revisions.  To detect cycles,
3304   provide all parent dag_node_t * in PARENT_NODES. */
3305static svn_error_t *
3306verify_node(dag_node_t *node,
3307            svn_revnum_t rev,
3308            apr_array_header_t *parent_nodes,
3309            apr_pool_t *scratch_pool)
3310{
3311  svn_boolean_t has_mergeinfo;
3312  apr_int64_t mergeinfo_count;
3313  svn_fs_x__id_t pred_id;
3314  svn_fs_t *fs = svn_fs_x__dag_get_fs(node);
3315  int pred_count;
3316  svn_node_kind_t kind;
3317  apr_pool_t *iterpool = svn_pool_create(scratch_pool);
3318  int i;
3319
3320  /* Detect (non-)DAG cycles. */
3321  for (i = 0; i < parent_nodes->nelts; ++i)
3322    {
3323      dag_node_t *parent = APR_ARRAY_IDX(parent_nodes, i, dag_node_t *);
3324      if (svn_fs_x__id_eq(svn_fs_x__dag_get_id(parent),
3325                          svn_fs_x__dag_get_id(node)))
3326        return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
3327                                "Node is its own direct or indirect parent '%s'",
3328                                stringify_node(node, iterpool));
3329    }
3330
3331  /* Fetch some data. */
3332  has_mergeinfo = svn_fs_x__dag_has_mergeinfo(node);
3333  mergeinfo_count = svn_fs_x__dag_get_mergeinfo_count(node);
3334  pred_id = *svn_fs_x__dag_get_predecessor_id(node);
3335  pred_count = svn_fs_x__dag_get_predecessor_count(node);
3336  kind = svn_fs_x__dag_node_kind(node);
3337
3338  /* Sanity check. */
3339  if (mergeinfo_count < 0)
3340    return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
3341                             "Negative mergeinfo-count %" APR_INT64_T_FMT
3342                             " on node '%s'",
3343                             mergeinfo_count, stringify_node(node, iterpool));
3344
3345  /* Issue #4129. (This check will explicitly catch non-root instances too.) */
3346  if (svn_fs_x__id_used(&pred_id))
3347    {
3348      dag_node_t *pred;
3349      int pred_pred_count;
3350      SVN_ERR(svn_fs_x__dag_get_node(&pred, fs, &pred_id, iterpool,
3351                                     iterpool));
3352      pred_pred_count = svn_fs_x__dag_get_predecessor_count(pred);
3353      if (pred_pred_count+1 != pred_count)
3354        return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
3355                                 "Predecessor count mismatch: "
3356                                 "%s has %d, but %s has %d",
3357                                 stringify_node(node, iterpool), pred_count,
3358                                 stringify_node(pred, iterpool),
3359                                 pred_pred_count);
3360    }
3361
3362  /* Kind-dependent verifications. */
3363  if (kind == svn_node_none)
3364    {
3365      return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
3366                               "Node '%s' has kind 'none'",
3367                               stringify_node(node, iterpool));
3368    }
3369  if (kind == svn_node_file)
3370    {
3371      if (has_mergeinfo != mergeinfo_count) /* comparing int to bool */
3372        return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
3373                                 "File node '%s' has inconsistent mergeinfo: "
3374                                 "has_mergeinfo=%d, "
3375                                 "mergeinfo_count=%" APR_INT64_T_FMT,
3376                                 stringify_node(node, iterpool),
3377                                 has_mergeinfo, mergeinfo_count);
3378    }
3379  if (kind == svn_node_dir)
3380    {
3381      apr_array_header_t *entries;
3382      apr_int64_t children_mergeinfo = 0;
3383      APR_ARRAY_PUSH(parent_nodes, dag_node_t*) = node;
3384
3385      SVN_ERR(svn_fs_x__dag_dir_entries(&entries, node, scratch_pool,
3386                                        iterpool));
3387
3388      /* Compute CHILDREN_MERGEINFO. */
3389      for (i = 0; i < entries->nelts; ++i)
3390        {
3391          svn_fs_x__dirent_t *dirent
3392            = APR_ARRAY_IDX(entries, i, svn_fs_x__dirent_t *);
3393          dag_node_t *child;
3394          apr_int64_t child_mergeinfo;
3395
3396          svn_pool_clear(iterpool);
3397
3398          /* Compute CHILD_REV. */
3399          if (svn_fs_x__get_revnum(dirent->id.change_set) == rev)
3400            {
3401              SVN_ERR(svn_fs_x__dag_get_node(&child, fs, &dirent->id,
3402                                             iterpool, iterpool));
3403              SVN_ERR(verify_node(child, rev, parent_nodes, iterpool));
3404              child_mergeinfo = svn_fs_x__dag_get_mergeinfo_count(child);
3405            }
3406          else
3407            {
3408              SVN_ERR(svn_fs_x__get_mergeinfo_count(&child_mergeinfo, fs,
3409                                                    &dirent->id, iterpool));
3410            }
3411
3412          children_mergeinfo += child_mergeinfo;
3413        }
3414
3415      /* Side-effect of issue #4129. */
3416      if (children_mergeinfo+has_mergeinfo != mergeinfo_count)
3417        return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
3418                                 "Mergeinfo-count discrepancy on '%s': "
3419                                 "expected %" APR_INT64_T_FMT "+%d, "
3420                                 "counted %" APR_INT64_T_FMT,
3421                                 stringify_node(node, iterpool),
3422                                 mergeinfo_count, has_mergeinfo,
3423                                 children_mergeinfo);
3424
3425      /* If we don't make it here, there was an error / corruption.
3426       * In that case, nobody will need PARENT_NODES anymore. */
3427      apr_array_pop(parent_nodes);
3428    }
3429
3430  svn_pool_destroy(iterpool);
3431  return SVN_NO_ERROR;
3432}
3433
3434svn_error_t *
3435svn_fs_x__verify_root(svn_fs_root_t *root,
3436                      apr_pool_t *scratch_pool)
3437{
3438  dag_node_t *root_dir;
3439  apr_array_header_t *parent_nodes;
3440
3441  /* Issue #4129: bogus pred-counts and minfo-cnt's on the root node-rev
3442     (and elsewhere).  This code makes more thorough checks than the
3443     commit-time checks in validate_root_noderev(). */
3444
3445  /* Callers should disable caches by setting SVN_FS_CONFIG_FSX_CACHE_NS;
3446     see r1462436.
3447
3448     When this code is called in the library, we want to ensure we
3449     use the on-disk data --- rather than some data that was read
3450     in the possibly-distance past and cached since. */
3451  SVN_ERR(svn_fs_x__dag_root(&root_dir, root->fs,
3452                             svn_fs_x__root_change_set(root),
3453                             scratch_pool, scratch_pool));
3454
3455  /* Recursively verify ROOT_DIR. */
3456  parent_nodes = apr_array_make(scratch_pool, 16, sizeof(dag_node_t *));
3457  SVN_ERR(verify_node(root_dir, root->rev, parent_nodes, scratch_pool));
3458
3459  /* Verify explicitly the predecessor of the root. */
3460  {
3461    svn_fs_x__id_t pred_id;
3462    svn_boolean_t has_predecessor;
3463
3464    /* Only r0 should have no predecessor. */
3465    pred_id = *svn_fs_x__dag_get_predecessor_id(root_dir);
3466    has_predecessor = svn_fs_x__id_used(&pred_id);
3467    if (!root->is_txn_root && has_predecessor != !!root->rev)
3468      return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
3469                               "r%ld's root node's predecessor is "
3470                               "unexpectedly '%s'",
3471                               root->rev,
3472                               (has_predecessor
3473                                 ? svn_fs_x__id_unparse(&pred_id,
3474                                                        scratch_pool)->data
3475                                 : "(null)"));
3476    if (root->is_txn_root && !has_predecessor)
3477      return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
3478                               "Transaction '%s''s root node's predecessor is "
3479                               "unexpectedly NULL",
3480                               root->txn);
3481
3482    /* Check the predecessor's revision. */
3483    if (has_predecessor)
3484      {
3485        svn_revnum_t pred_rev = svn_fs_x__get_revnum(pred_id.change_set);
3486        if (! root->is_txn_root && pred_rev+1 != root->rev)
3487          /* Issue #4129. */
3488          return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
3489                                   "r%ld's root node's predecessor is r%ld"
3490                                   " but should be r%ld",
3491                                   root->rev, pred_rev, root->rev - 1);
3492        if (root->is_txn_root && pred_rev != root->rev)
3493          return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
3494                                   "Transaction '%s''s root node's predecessor"
3495                                   " is r%ld"
3496                                   " but should be r%ld",
3497                                   root->txn, pred_rev, root->rev);
3498      }
3499  }
3500
3501  return SVN_NO_ERROR;
3502}
3503