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 "cached_data.h"
56#include "dag.h"
57#include "lock.h"
58#include "tree.h"
59#include "fs_fs.h"
60#include "id.h"
61#include "pack.h"
62#include "temp_serializer.h"
63#include "transaction.h"
64#include "util.h"
65
66#include "private/svn_mergeinfo_private.h"
67#include "private/svn_subr_private.h"
68#include "private/svn_fs_util.h"
69#include "private/svn_fspath.h"
70#include "../libsvn_fs/fs-loader.h"
71
72
73
74/* The root structures.
75
76   Why do they contain different data?  Well, transactions are mutable
77   enough that it isn't safe to cache the DAG node for the root
78   directory or the hash of copyfrom data: somebody else might modify
79   them concurrently on disk!  (Why is the DAG node cache safer than
80   the root DAG node?  When cloning transaction DAG nodes in and out
81   of the cache, all of the possibly-mutable data from the
82   node_revision_t inside the dag_node_t is dropped.)  Additionally,
83   revisions are immutable enough that their DAG node cache can be
84   kept in the FS object and shared among multiple revision root
85   objects.
86*/
87typedef dag_node_t fs_rev_root_data_t;
88
89typedef struct fs_txn_root_data_t
90{
91  /* TXN_ID value from the main struct but as a struct instead of a string */
92  svn_fs_fs__id_part_t txn_id;
93
94  /* Cache of txn DAG nodes (without their nested noderevs, because
95   * it's mutable). Same keys/values as ffd->rev_node_cache. */
96  svn_cache__t *txn_node_cache;
97} fs_txn_root_data_t;
98
99/* Declared here to resolve the circular dependencies. */
100static svn_error_t * get_dag(dag_node_t **dag_node_p,
101                             svn_fs_root_t *root,
102                             const char *path,
103                             apr_pool_t *pool);
104
105static svn_fs_root_t *make_revision_root(svn_fs_t *fs, svn_revnum_t rev,
106                                         dag_node_t *root_dir,
107                                         apr_pool_t *pool);
108
109static svn_error_t *make_txn_root(svn_fs_root_t **root_p,
110                                  svn_fs_t *fs,
111                                  const svn_fs_fs__id_part_t *txn,
112                                  svn_revnum_t base_rev,
113                                  apr_uint32_t flags,
114                                  apr_pool_t *pool);
115
116static svn_error_t *fs_closest_copy(svn_fs_root_t **root_p,
117                                    const char **path_p,
118                                    svn_fs_root_t *root,
119                                    const char *path,
120                                    apr_pool_t *pool);
121
122
123/*** Node Caching ***/
124
125/* 1st level cache */
126
127/* An entry in the first-level cache.  REVISION and PATH form the key that
128   will ultimately be matched.
129 */
130typedef struct cache_entry_t
131{
132  /* hash value derived from PATH, REVISION.
133     Used to short-circuit failed lookups. */
134  apr_uint32_t hash_value;
135
136  /* revision to which the NODE belongs */
137  svn_revnum_t revision;
138
139  /* path of the NODE */
140  char *path;
141
142  /* cached value of strlen(PATH). */
143  apr_size_t path_len;
144
145  /* the node allocated in the cache's pool. NULL for empty entries. */
146  dag_node_t *node;
147} cache_entry_t;
148
149/* Number of entries in the cache.  Keep this low to keep pressure on the
150   CPU caches low as well.  A binary value is most efficient.  If we walk
151   a directory tree, we want enough entries to store nodes for all files
152   without overwriting the nodes for the parent folder.  That way, there
153   will be no unnecessary misses (except for a few random ones caused by
154   hash collision).
155
156   The actual number of instances may be higher but entries that got
157   overwritten are no longer visible.
158 */
159enum { BUCKET_COUNT = 256 };
160
161/* The actual cache structure.  All nodes will be allocated in POOL.
162   When the number of INSERTIONS (i.e. objects created form that pool)
163   exceeds a certain threshold, the pool will be cleared and the cache
164   with it.
165 */
166struct fs_fs_dag_cache_t
167{
168  /* fixed number of (possibly empty) cache entries */
169  cache_entry_t buckets[BUCKET_COUNT];
170
171  /* pool used for all node allocation */
172  apr_pool_t *pool;
173
174  /* number of entries created from POOL since the last cleanup */
175  apr_size_t insertions;
176
177  /* Property lookups etc. have a very high locality (75% re-hit).
178     Thus, remember the last hit location for optimistic lookup. */
179  apr_size_t last_hit;
180
181  /* Position of the last bucket hit that actually had a DAG node in it.
182     LAST_HIT may refer to a bucket that matches path@rev but has not
183     its NODE element set, yet.
184     This value is a mere hint for optimistic lookup and any value is
185     valid (as long as it is < BUCKET_COUNT). */
186  apr_size_t last_non_empty;
187};
188
189fs_fs_dag_cache_t*
190svn_fs_fs__create_dag_cache(apr_pool_t *pool)
191{
192  fs_fs_dag_cache_t *result = apr_pcalloc(pool, sizeof(*result));
193  result->pool = svn_pool_create(pool);
194
195  return result;
196}
197
198/* Clears the CACHE at regular intervals (destroying all cached nodes)
199 */
200static void
201auto_clear_dag_cache(fs_fs_dag_cache_t* cache)
202{
203  if (cache->insertions > BUCKET_COUNT)
204    {
205      svn_pool_clear(cache->pool);
206
207      memset(cache->buckets, 0, sizeof(cache->buckets));
208      cache->insertions = 0;
209    }
210}
211
212/* Returns a 32 bit hash value for the given REVISION and PATH of exactly
213 * PATH_LEN chars.
214 */
215static apr_uint32_t
216hash_func(svn_revnum_t revision,
217          const char *path,
218          apr_size_t path_len)
219{
220  apr_size_t i;
221  apr_uint32_t hash_value = (apr_uint32_t)revision;
222
223#if SVN_UNALIGNED_ACCESS_IS_OK
224  /* "randomizing" / distributing factor used in our hash function */
225  const apr_uint32_t factor = 0xd1f3da69;
226#endif
227
228  /* Calculate the hash value
229     (HASH_VALUE has been initialized to REVISION).
230
231     Note that the actual hash function is arbitrary as long as its result
232     in HASH_VALUE only depends on REVISION and *PATH.  However, we try to
233     make as much of *PATH influence the result as possible to get an "even"
234     spread across the hash buckets (maximizes our cache retention rate and
235     thus the hit rates).
236
237     When chunked access is possible (independent of the PATH pointer's
238     value!), we read 4 bytes at once and multiply the hash value with a
239     FACTOR that mirror / pattern / shift all 4 input bytes to various bits
240     of the result.  The final result will be taken from the MSBs.
241
242     When chunked access is not possible (not supported by CPU or odd bytes
243     at the end of *PATH), we use the simple traditional "* 33" hash
244     function that works very well with texts / paths and that e.g. APR uses.
245
246     Please note that the bytewise and the chunked calculation are *NOT*
247     interchangeable as they will yield different results for the same input.
248     For any given machine and *PATH, we must use a fixed combination of the
249     two functions.
250   */
251  i = 0;
252#if SVN_UNALIGNED_ACCESS_IS_OK
253  /* We relax the dependency chain between iterations by processing
254     two chunks from the input per hash_value self-multiplication.
255     The HASH_VALUE update latency is now 1 MUL latency + 1 ADD latency
256     per 2 chunks instead of 1 chunk.
257   */
258  for (; i + 8 <= path_len; i += 8)
259    hash_value = hash_value * factor * factor
260               + (  *(const apr_uint32_t*)(path + i) * factor
261                  + *(const apr_uint32_t*)(path + i + 4));
262#endif
263
264  for (; i < path_len; ++i)
265    /* Help GCC to minimize the HASH_VALUE update latency by splitting the
266       MUL 33 of the naive implementation: h = h * 33 + path[i].  This
267       shortens the dependency chain from 1 shift + 2 ADDs to 1 shift + 1 ADD.
268     */
269    hash_value = hash_value * 32 + (hash_value + (unsigned char)path[i]);
270
271  return hash_value;
272}
273
274/* For the given REVISION and PATH, return the respective node found in
275 * CACHE.  If there is none, return NULL.
276 */
277static dag_node_t *
278cache_lookup( fs_fs_dag_cache_t *cache
279            , svn_revnum_t revision
280            , const char *path)
281{
282  apr_size_t bucket_index;
283  apr_size_t path_len = strlen(path);
284  apr_uint32_t hash_value;
285
286  /* optimistic lookup: hit the same bucket again? */
287  cache_entry_t *result = &cache->buckets[cache->last_hit];
288  if (   (result->revision == revision)
289      && (result->path_len == path_len)
290      && !memcmp(result->path, path, path_len))
291    {
292      /* Remember the position of the last node we found in this cache. */
293      if (result->node)
294        cache->last_non_empty = cache->last_hit;
295
296      return result->node;
297    }
298
299  /* need to do a full lookup. */
300  hash_value = hash_func(revision, path, path_len);
301
302  bucket_index = hash_value + (hash_value >> 16);
303  bucket_index = (bucket_index + (bucket_index >> 8)) % BUCKET_COUNT;
304
305  /* access the corresponding bucket and remember its location */
306  result = &cache->buckets[bucket_index];
307  cache->last_hit = bucket_index;
308
309  /* if it is *NOT* a match,  clear the bucket, expect the caller to fill
310     in the node and count it as an insertion */
311  if (   (result->hash_value != hash_value)
312      || (result->revision != revision)
313      || (result->path_len != path_len)
314      || memcmp(result->path, path, path_len))
315    {
316      return NULL;
317    }
318  else if (result->node)
319    {
320      /* This bucket is valid & has a suitable DAG node in it.
321         Remember its location. */
322      cache->last_non_empty = bucket_index;
323    }
324
325  return result->node;
326}
327
328/* Store a copy of NODE in CACHE, taking  REVISION and PATH as key.
329 * This function will clean the cache at regular intervals.
330 */
331static void
332cache_insert(fs_fs_dag_cache_t *cache,
333             svn_revnum_t revision,
334             const char *path,
335             dag_node_t *node)
336{
337  apr_size_t bucket_index;
338  apr_size_t path_len = strlen(path);
339  apr_uint32_t hash_value;
340  cache_entry_t *entry;
341
342  auto_clear_dag_cache(cache);
343
344  /* calculate the bucket index to use */
345  hash_value = hash_func(revision, path, path_len);
346
347  bucket_index = hash_value + (hash_value >> 16);
348  bucket_index = (bucket_index + (bucket_index >> 8)) % BUCKET_COUNT;
349
350  /* access the corresponding bucket and remember its location */
351  entry = &cache->buckets[bucket_index];
352  cache->last_hit = bucket_index;
353
354  /* if it is *NOT* a match,  clear the bucket, expect the caller to fill
355     in the node and count it as an insertion */
356  entry->hash_value = hash_value;
357  entry->revision = revision;
358  if (entry->path_len < path_len)
359    entry->path = apr_palloc(cache->pool, path_len + 1);
360  entry->path_len = path_len;
361  memcpy(entry->path, path, path_len + 1);
362
363  entry->node = svn_fs_fs__dag_dup(node, cache->pool);
364  cache->insertions++;
365}
366
367/* Optimistic lookup using the last seen non-empty location in CACHE.
368   Return the node of that entry, if it is still in use and matches PATH.
369   Return NULL otherwise.  Since the caller usually already knows the path
370   length, provide it in PATH_LEN. */
371static dag_node_t *
372cache_lookup_last_path(fs_fs_dag_cache_t *cache,
373                       const char *path,
374                       apr_size_t path_len)
375{
376  cache_entry_t *result = &cache->buckets[cache->last_non_empty];
377  assert(strlen(path) == path_len);
378
379  if (   result->node
380      && (result->path_len == path_len)
381      && !memcmp(result->path, path, path_len))
382    {
383      return result->node;
384    }
385
386  return NULL;
387}
388
389/* 2nd level cache */
390
391/* Find and return the DAG node cache for ROOT and the key that
392   should be used for PATH.
393
394   Pool will only be used for allocating a new keys if necessary */
395static void
396locate_cache(svn_cache__t **cache,
397             const char **key,
398             svn_fs_root_t *root,
399             const char *path,
400             apr_pool_t *pool)
401{
402  if (root->is_txn_root)
403    {
404      fs_txn_root_data_t *frd = root->fsap_data;
405
406      if (cache)
407        *cache = frd->txn_node_cache;
408      if (key && path)
409        *key = path;
410    }
411  else
412    {
413      fs_fs_data_t *ffd = root->fs->fsap_data;
414
415      if (cache)
416        *cache = ffd->rev_node_cache;
417      if (key && path)
418        *key = svn_fs_fs__combine_number_and_string(root->rev, path, pool);
419    }
420}
421
422/* In *NODE_P, return the DAG node for PATH from ROOT's node cache, or NULL
423   if the node isn't cached.  *NODE_P is allocated in POOL. */
424static svn_error_t *
425dag_node_cache_get(dag_node_t **node_p,
426                   svn_fs_root_t *root,
427                   const char *path,
428                   apr_pool_t *pool)
429{
430  svn_boolean_t found;
431  dag_node_t *node = NULL;
432  svn_cache__t *cache;
433  const char *key;
434
435  SVN_ERR_ASSERT(*path == '/');
436
437  if (!root->is_txn_root)
438    {
439      /* immutable DAG node. use the global caches for it */
440
441      fs_fs_data_t *ffd = root->fs->fsap_data;
442
443      node = cache_lookup(ffd->dag_node_cache, root->rev, path);
444      if (node == NULL)
445        {
446          locate_cache(&cache, &key, root, path, pool);
447          SVN_ERR(svn_cache__get((void **)&node, &found, cache, key, pool));
448          if (found && node)
449            {
450              /* Patch up the FS, since this might have come from an old FS
451               * object. */
452              svn_fs_fs__dag_set_fs(node, root->fs);
453
454              /* Retain the DAG node in L1 cache. */
455              cache_insert(ffd->dag_node_cache, root->rev, path, node);
456            }
457        }
458      else
459        {
460          /* Copy the node from L1 cache into the passed-in POOL. */
461          node = svn_fs_fs__dag_dup(node, pool);
462        }
463    }
464  else
465    {
466      /* DAG is mutable / may become invalid. Use the TXN-local cache */
467
468      locate_cache(&cache, &key, root, path, pool);
469
470      SVN_ERR(svn_cache__get((void **) &node, &found, cache, key, pool));
471      if (found && node)
472        {
473          /* Patch up the FS, since this might have come from an old FS
474           * object. */
475          svn_fs_fs__dag_set_fs(node, root->fs);
476        }
477    }
478
479  *node_p = node;
480
481  return SVN_NO_ERROR;
482}
483
484
485/* Add the NODE for PATH to ROOT's node cache. */
486static svn_error_t *
487dag_node_cache_set(svn_fs_root_t *root,
488                   const char *path,
489                   dag_node_t *node,
490                   apr_pool_t *pool)
491{
492  svn_cache__t *cache;
493  const char *key;
494
495  SVN_ERR_ASSERT(*path == '/');
496
497  locate_cache(&cache, &key, root, path, pool);
498  return svn_cache__set(cache, key, node, pool);
499}
500
501
502/* Baton for find_descendants_in_cache. */
503struct fdic_baton {
504  const char *path;
505  apr_array_header_t *list;
506  apr_pool_t *pool;
507};
508
509/* If the given item is a descendant of BATON->PATH, push
510 * it onto BATON->LIST (copying into BATON->POOL).  Implements
511 * the svn_iter_apr_hash_cb_t prototype. */
512static svn_error_t *
513find_descendants_in_cache(void *baton,
514                          const void *key,
515                          apr_ssize_t klen,
516                          void *val,
517                          apr_pool_t *pool)
518{
519  struct fdic_baton *b = baton;
520  const char *item_path = key;
521
522  if (svn_fspath__skip_ancestor(b->path, item_path))
523    APR_ARRAY_PUSH(b->list, const char *) = apr_pstrdup(b->pool, item_path);
524
525  return SVN_NO_ERROR;
526}
527
528/* Invalidate cache entries for PATH and any of its children.  This
529   should *only* be called on a transaction root! */
530static svn_error_t *
531dag_node_cache_invalidate(svn_fs_root_t *root,
532                          const char *path,
533                          apr_pool_t *pool)
534{
535  struct fdic_baton b;
536  svn_cache__t *cache;
537  apr_pool_t *iterpool;
538  int i;
539
540  b.path = path;
541  b.pool = svn_pool_create(pool);
542  b.list = apr_array_make(b.pool, 1, sizeof(const char *));
543
544  SVN_ERR_ASSERT(root->is_txn_root);
545  locate_cache(&cache, NULL, root, NULL, b.pool);
546
547
548  SVN_ERR(svn_cache__iter(NULL, cache, find_descendants_in_cache,
549                          &b, b.pool));
550
551  iterpool = svn_pool_create(b.pool);
552
553  for (i = 0; i < b.list->nelts; i++)
554    {
555      const char *descendant = APR_ARRAY_IDX(b.list, i, const char *);
556      svn_pool_clear(iterpool);
557      SVN_ERR(svn_cache__set(cache, descendant, NULL, iterpool));
558    }
559
560  svn_pool_destroy(iterpool);
561  svn_pool_destroy(b.pool);
562  return SVN_NO_ERROR;
563}
564
565
566
567/* Creating transaction and revision root nodes.  */
568
569svn_error_t *
570svn_fs_fs__txn_root(svn_fs_root_t **root_p,
571                    svn_fs_txn_t *txn,
572                    apr_pool_t *pool)
573{
574  apr_uint32_t flags = 0;
575  apr_hash_t *txnprops;
576
577  /* Look for the temporary txn props representing 'flags'. */
578  SVN_ERR(svn_fs_fs__txn_proplist(&txnprops, txn, pool));
579  if (txnprops)
580    {
581      if (svn_hash_gets(txnprops, SVN_FS__PROP_TXN_CHECK_OOD))
582        flags |= SVN_FS_TXN_CHECK_OOD;
583
584      if (svn_hash_gets(txnprops, SVN_FS__PROP_TXN_CHECK_LOCKS))
585        flags |= SVN_FS_TXN_CHECK_LOCKS;
586    }
587
588  return make_txn_root(root_p, txn->fs, svn_fs_fs__txn_get_id(txn),
589                       txn->base_rev, flags, pool);
590}
591
592
593svn_error_t *
594svn_fs_fs__revision_root(svn_fs_root_t **root_p,
595                         svn_fs_t *fs,
596                         svn_revnum_t rev,
597                         apr_pool_t *pool)
598{
599  dag_node_t *root_dir;
600
601  SVN_ERR(svn_fs__check_fs(fs, TRUE));
602
603  SVN_ERR(svn_fs_fs__dag_revision_root(&root_dir, fs, rev, pool));
604
605  *root_p = make_revision_root(fs, rev, root_dir, pool);
606
607  return SVN_NO_ERROR;
608}
609
610
611
612/* Getting dag nodes for roots.  */
613
614/* Return the transaction ID to a given transaction ROOT. */
615static const svn_fs_fs__id_part_t *
616root_txn_id(svn_fs_root_t *root)
617{
618  fs_txn_root_data_t *frd = root->fsap_data;
619  assert(root->is_txn_root);
620
621  return &frd->txn_id;
622}
623
624/* Set *NODE_P to a freshly opened dag node referring to the root
625   directory of ROOT, allocating from POOL.  */
626static svn_error_t *
627root_node(dag_node_t **node_p,
628          svn_fs_root_t *root,
629          apr_pool_t *pool)
630{
631  if (root->is_txn_root)
632    {
633      /* It's a transaction root.  Open a fresh copy.  */
634      return svn_fs_fs__dag_txn_root(node_p, root->fs, root_txn_id(root),
635                                     pool);
636    }
637  else
638    {
639      /* It's a revision root, so we already have its root directory
640         opened.  */
641      dag_node_t *root_dir = root->fsap_data;
642      *node_p = svn_fs_fs__dag_dup(root_dir, pool);
643      return SVN_NO_ERROR;
644    }
645}
646
647
648/* Set *NODE_P to a mutable root directory for ROOT, cloning if
649   necessary, allocating in POOL.  ROOT must be a transaction root.
650   Use ERROR_PATH in error messages.  */
651static svn_error_t *
652mutable_root_node(dag_node_t **node_p,
653                  svn_fs_root_t *root,
654                  const char *error_path,
655                  apr_pool_t *pool)
656{
657  if (root->is_txn_root)
658    {
659      /* It's a transaction root.  Open a fresh copy.  */
660      return svn_fs_fs__dag_clone_root(node_p, root->fs, root_txn_id(root),
661                                       pool);
662    }
663  else
664    /* If it's not a transaction root, we can't change its contents.  */
665    return SVN_FS__ERR_NOT_MUTABLE(root->fs, root->rev, error_path);
666}
667
668
669
670/* Traversing directory paths.  */
671
672typedef enum copy_id_inherit_t
673{
674  copy_id_inherit_unknown = 0,
675  copy_id_inherit_self,
676  copy_id_inherit_parent,
677  copy_id_inherit_new
678
679} copy_id_inherit_t;
680
681/* A linked list representing the path from a node up to a root
682   directory.  We use this for cloning, and for operations that need
683   to deal with both a node and its parent directory.  For example, a
684   `delete' operation needs to know that the node actually exists, but
685   also needs to change the parent directory.  */
686typedef struct parent_path_t
687{
688
689  /* A node along the path.  This could be the final node, one of its
690     parents, or the root.  Every parent path ends with an element for
691     the root directory.  */
692  dag_node_t *node;
693
694  /* The name NODE has in its parent directory.  This is zero for the
695     root directory, which (obviously) has no name in its parent.  */
696  char *entry;
697
698  /* The parent of NODE, or zero if NODE is the root directory.  */
699  struct parent_path_t *parent;
700
701  /* The copy ID inheritance style. */
702  copy_id_inherit_t copy_inherit;
703
704  /* If copy ID inheritance style is copy_id_inherit_new, this is the
705     path which should be implicitly copied; otherwise, this is NULL. */
706  const char *copy_src_path;
707
708} parent_path_t;
709
710/* Return a text string describing the absolute path of parent_path
711   PARENT_PATH.  It will be allocated in POOL. */
712static const char *
713parent_path_path(parent_path_t *parent_path,
714                 apr_pool_t *pool)
715{
716  const char *path_so_far = "/";
717  if (parent_path->parent)
718    path_so_far = parent_path_path(parent_path->parent, pool);
719  return parent_path->entry
720    ? svn_fspath__join(path_so_far, parent_path->entry, pool)
721    : path_so_far;
722}
723
724
725/* Return the FS path for the parent path chain object CHILD relative
726   to its ANCESTOR in the same chain, allocated in POOL.  */
727static const char *
728parent_path_relpath(parent_path_t *child,
729                    parent_path_t *ancestor,
730                    apr_pool_t *pool)
731{
732  const char *path_so_far = "";
733  parent_path_t *this_node = child;
734  while (this_node != ancestor)
735    {
736      assert(this_node != NULL);
737      path_so_far = svn_relpath_join(this_node->entry, path_so_far, pool);
738      this_node = this_node->parent;
739    }
740  return path_so_far;
741}
742
743
744
745/* Choose a copy ID inheritance method *INHERIT_P to be used in the
746   event that immutable node CHILD in FS needs to be made mutable.  If
747   the inheritance method is copy_id_inherit_new, also return a
748   *COPY_SRC_PATH on which to base the new copy ID (else return NULL
749   for that path).  CHILD must have a parent (it cannot be the root
750   node).  Allocations are taken from POOL. */
751static svn_error_t *
752get_copy_inheritance(copy_id_inherit_t *inherit_p,
753                     const char **copy_src_path,
754                     svn_fs_t *fs,
755                     parent_path_t *child,
756                     apr_pool_t *pool)
757{
758  const svn_fs_id_t *child_id, *parent_id, *copyroot_id;
759  const svn_fs_fs__id_part_t *child_copy_id, *parent_copy_id;
760  const char *id_path = NULL;
761  svn_fs_root_t *copyroot_root;
762  dag_node_t *copyroot_node;
763  svn_revnum_t copyroot_rev;
764  const char *copyroot_path;
765
766  SVN_ERR_ASSERT(child && child->parent);
767
768  /* Initialize some convenience variables. */
769  child_id = svn_fs_fs__dag_get_id(child->node);
770  parent_id = svn_fs_fs__dag_get_id(child->parent->node);
771  child_copy_id = svn_fs_fs__id_copy_id(child_id);
772  parent_copy_id = svn_fs_fs__id_copy_id(parent_id);
773
774  /* If this child is already mutable, we have nothing to do. */
775  if (svn_fs_fs__id_is_txn(child_id))
776    {
777      *inherit_p = copy_id_inherit_self;
778      *copy_src_path = NULL;
779      return SVN_NO_ERROR;
780    }
781
782  /* From this point on, we'll assume that the child will just take
783     its copy ID from its parent. */
784  *inherit_p = copy_id_inherit_parent;
785  *copy_src_path = NULL;
786
787  /* Special case: if the child's copy ID is '0', use the parent's
788     copy ID. */
789  if (svn_fs_fs__id_part_is_root(child_copy_id))
790    return SVN_NO_ERROR;
791
792  /* Compare the copy IDs of the child and its parent.  If they are
793     the same, then the child is already on the same branch as the
794     parent, and should use the same mutability copy ID that the
795     parent will use. */
796  if (svn_fs_fs__id_part_eq(child_copy_id, parent_copy_id))
797    return SVN_NO_ERROR;
798
799  /* If the child is on the same branch that the parent is on, the
800     child should just use the same copy ID that the parent would use.
801     Else, the child needs to generate a new copy ID to use should it
802     need to be made mutable.  We will claim that child is on the same
803     branch as its parent if the child itself is not a branch point,
804     or if it is a branch point that we are accessing via its original
805     copy destination path. */
806  SVN_ERR(svn_fs_fs__dag_get_copyroot(&copyroot_rev, &copyroot_path,
807                                      child->node));
808  SVN_ERR(svn_fs_fs__revision_root(&copyroot_root, fs, copyroot_rev, pool));
809  SVN_ERR(get_dag(&copyroot_node, copyroot_root, copyroot_path, pool));
810  copyroot_id = svn_fs_fs__dag_get_id(copyroot_node);
811
812  if (svn_fs_fs__id_compare(copyroot_id, child_id) == svn_fs_node_unrelated)
813    return SVN_NO_ERROR;
814
815  /* Determine if we are looking at the child via its original path or
816     as a subtree item of a copied tree. */
817  id_path = svn_fs_fs__dag_get_created_path(child->node);
818  if (strcmp(id_path, parent_path_path(child, pool)) == 0)
819    {
820      *inherit_p = copy_id_inherit_self;
821      return SVN_NO_ERROR;
822    }
823
824  /* We are pretty sure that the child node is an unedited nested
825     branched node.  When it needs to be made mutable, it should claim
826     a new copy ID. */
827  *inherit_p = copy_id_inherit_new;
828  *copy_src_path = id_path;
829  return SVN_NO_ERROR;
830}
831
832/* Allocate a new parent_path_t node from POOL, referring to NODE,
833   ENTRY, PARENT, and COPY_ID.  */
834static parent_path_t *
835make_parent_path(dag_node_t *node,
836                 char *entry,
837                 parent_path_t *parent,
838                 apr_pool_t *pool)
839{
840  parent_path_t *parent_path = apr_pcalloc(pool, sizeof(*parent_path));
841  parent_path->node = node;
842  parent_path->entry = entry;
843  parent_path->parent = parent;
844  parent_path->copy_inherit = copy_id_inherit_unknown;
845  parent_path->copy_src_path = NULL;
846  return parent_path;
847}
848
849
850/* Flags for open_path.  */
851typedef enum open_path_flags_t {
852
853  /* The last component of the PATH need not exist.  (All parent
854     directories must exist, as usual.)  If the last component doesn't
855     exist, simply leave the `node' member of the bottom parent_path
856     component zero.  */
857  open_path_last_optional = 1,
858
859  /* When this flag is set, don't bother to lookup the DAG node in
860     our caches because we already tried this.  Ignoring this flag
861     has no functional impact.  */
862  open_path_uncached = 2,
863
864  /* The caller does not care about the parent node chain but only
865     the final DAG node. */
866  open_path_node_only = 4,
867
868  /* The caller wants a NULL path object instead of an error if the
869     path cannot be found. */
870  open_path_allow_null = 8
871} open_path_flags_t;
872
873/* Try a short-cut for the open_path() function using the last node accessed.
874 * If that ROOT is that nodes's "created rev" and PATH of PATH_LEN chars is
875 * its "created path", return the node in *NODE_P.  Set it to NULL otherwise.
876 *
877 * This function is used to support ra_serf-style access patterns where we
878 * are first asked for path@rev and then for path@c_rev of the same node.
879 * The shortcut works by ignoring the "rev" part of the cache key and then
880 * checking whether we got lucky.  Lookup and verification are both quick
881 * plus there are many early outs for common types of mismatch.
882 */
883static svn_error_t *
884try_match_last_node(dag_node_t **node_p,
885                    svn_fs_root_t *root,
886                    const char *path,
887                    apr_size_t path_len,
888                    apr_pool_t *scratch_pool)
889{
890  fs_fs_data_t *ffd = root->fs->fsap_data;
891
892  /* Optimistic lookup: if the last node returned from the cache applied to
893     the same PATH, return it in NODE. */
894  dag_node_t *node
895    = cache_lookup_last_path(ffd->dag_node_cache, path, path_len);
896
897  /* Did we get a bucket with a committed node? */
898  if (node && !svn_fs_fs__dag_check_mutable(node))
899    {
900      /* Get the path&rev pair at which this node was created.
901         This is repository location for which this node is _known_ to be
902         the right lookup result irrespective of how we found it. */
903      const char *created_path
904        = svn_fs_fs__dag_get_created_path(node);
905      svn_revnum_t revision;
906      SVN_ERR(svn_fs_fs__dag_get_revision(&revision, node, scratch_pool));
907
908      /* Is it an exact match? */
909      if (revision == root->rev && strcmp(created_path, path) == 0)
910        {
911          /* Cache it under its full path@rev access path. */
912          SVN_ERR(dag_node_cache_set(root, path, node, scratch_pool));
913
914          *node_p = node;
915          return SVN_NO_ERROR;
916        }
917    }
918
919  *node_p = NULL;
920  return SVN_NO_ERROR;
921}
922
923/* Helper for open_path() that constructs and returns an appropriate
924   SVN_ERR_FS_NOT_DIRECTORY error. */
925static svn_error_t *
926err_not_directory(svn_fs_root_t *root,
927                  const char *path,
928                  apr_pool_t *scratch_pool)
929{
930  const char *msg;
931
932  msg = root->is_txn_root
933      ? apr_psprintf(scratch_pool,
934                     _("Failure opening '%s' in transaction '%s'"),
935                     path, root->txn)
936      : apr_psprintf(scratch_pool,
937                     _("Failure opening '%s' in revision %ld"),
938                     path, root->rev);
939
940  return svn_error_quick_wrap(SVN_FS__ERR_NOT_DIRECTORY(root->fs, path), msg);
941}
942
943/* Open the node identified by PATH in ROOT, allocating in POOL.  Set
944   *PARENT_PATH_P to a path from the node up to ROOT.  The resulting
945   **PARENT_PATH_P value is guaranteed to contain at least one
946   *element, for the root directory.  PATH must be in canonical form.
947
948   If resulting *PARENT_PATH_P will eventually be made mutable and
949   modified, or if copy ID inheritance information is otherwise needed,
950   IS_TXN_PATH must be set.  If IS_TXN_PATH is FALSE, no copy ID
951   inheritance information will be calculated for the *PARENT_PATH_P chain.
952
953   If FLAGS & open_path_last_optional is zero, return the error
954   SVN_ERR_FS_NOT_FOUND if the node PATH refers to does not exist.  If
955   non-zero, require all the parent directories to exist as normal,
956   but if the final path component doesn't exist, simply return a path
957   whose bottom `node' member is zero.  This option is useful for
958   callers that create new nodes --- we find the parent directory for
959   them, and tell them whether the entry exists already.
960
961   The remaining bits in FLAGS are hints that allow this function
962   to take shortcuts based on knowledge that the caller provides,
963   such as the caller is not actually being interested in PARENT_PATH_P,
964   but only in (*PARENT_PATH_P)->NODE.
965
966   NOTE: Public interfaces which only *read* from the filesystem
967   should not call this function directly, but should instead use
968   get_dag().
969*/
970static svn_error_t *
971open_path(parent_path_t **parent_path_p,
972          svn_fs_root_t *root,
973          const char *path,
974          int flags,
975          svn_boolean_t is_txn_path,
976          apr_pool_t *pool)
977{
978  svn_fs_t *fs = root->fs;
979  dag_node_t *here = NULL; /* The directory we're currently looking at.  */
980  parent_path_t *parent_path; /* The path from HERE up to the root. */
981  const char *rest = NULL; /* The portion of PATH we haven't traversed yet. */
982  apr_pool_t *iterpool = svn_pool_create(pool);
983
984  /* path to the currently processed entry without trailing '/'.
985     We will reuse this across iterations by simply putting a NUL terminator
986     at the respective position and replacing that with a '/' in the next
987     iteration.  This is correct as we assert() PATH to be canonical. */
988  svn_stringbuf_t *path_so_far = svn_stringbuf_create(path, pool);
989  apr_size_t path_len = path_so_far->len;
990
991  /* Callers often traverse the DAG in some path-based order or along the
992     history segments.  That allows us to try a few guesses about where to
993     find the next item.  This is only useful if the caller didn't request
994     the full parent chain. */
995  assert(svn_fs__is_canonical_abspath(path));
996  path_so_far->len = 0; /* "" */
997  if (flags & open_path_node_only)
998    {
999      const char *directory;
1000
1001      /* First attempt: Assume that we access the DAG for the same path as
1002         in the last lookup but for a different revision that happens to be
1003         the last revision that touched the respective node.  This is a
1004         common pattern when e.g. checking out over ra_serf.  Note that this
1005         will only work for committed data as the revision info for nodes in
1006         txns is bogus.
1007
1008         This shortcut is quick and will exit this function upon success.
1009         So, try it first. */
1010      if (!root->is_txn_root)
1011        {
1012          dag_node_t *node;
1013          SVN_ERR(try_match_last_node(&node, root, path, path_len, iterpool));
1014
1015          /* Did the shortcut work? */
1016          if (node)
1017            {
1018              /* Construct and return the result. */
1019              svn_pool_destroy(iterpool);
1020
1021              parent_path = make_parent_path(node, 0, 0, pool);
1022              parent_path->copy_inherit = copy_id_inherit_self;
1023              *parent_path_p = parent_path;
1024
1025              return SVN_NO_ERROR;
1026            }
1027        }
1028
1029      /* Second attempt: Try starting the lookup immediately at the parent
1030         node.  We will often have recently accessed either a sibling or
1031         said parent DIRECTORY itself for the same revision. */
1032      directory = svn_dirent_dirname(path, pool);
1033      if (directory[1] != 0) /* root nodes are covered anyway */
1034        {
1035          SVN_ERR(dag_node_cache_get(&here, root, directory, pool));
1036
1037          /* Did the shortcut work? */
1038          if (here && svn_fs_fs__dag_node_kind(here) == svn_node_dir)
1039            {
1040              apr_size_t dirname_len = strlen(directory);
1041              path_so_far->len = dirname_len;
1042              rest = path + dirname_len + 1;
1043            }
1044          else if (here)
1045            {
1046              /* The parent node is not a directory.  We are looking for some
1047                 sub-path, so that sub-path will not exist.  That will be o.k.
1048                 if we are just here to check for the path's existence, but
1049                 should result in an error otherwise. */
1050              if (flags & open_path_allow_null)
1051                {
1052                  *parent_path_p = NULL;
1053                  return SVN_NO_ERROR;
1054                }
1055              else
1056                return svn_error_trace(err_not_directory(root, directory, pool));
1057            }
1058        }
1059    }
1060
1061  /* did the shortcut work? */
1062  if (!here)
1063    {
1064      /* Make a parent_path item for the root node, using its own current
1065         copy id.  */
1066      SVN_ERR(root_node(&here, root, pool));
1067      rest = path + 1; /* skip the leading '/', it saves in iteration */
1068    }
1069
1070  path_so_far->data[path_so_far->len] = '\0';
1071  parent_path = make_parent_path(here, 0, 0, pool);
1072  parent_path->copy_inherit = copy_id_inherit_self;
1073
1074  /* Whenever we are at the top of this loop:
1075     - HERE is our current directory,
1076     - ID is the node revision ID of HERE,
1077     - REST is the path we're going to find in HERE, and
1078     - PARENT_PATH includes HERE and all its parents.  */
1079  for (;;)
1080    {
1081      const char *next;
1082      char *entry;
1083      dag_node_t *child;
1084
1085      svn_pool_clear(iterpool);
1086
1087      /* Parse out the next entry from the path.  */
1088      entry = svn_fs__next_entry_name(&next, rest, pool);
1089
1090      /* Update the path traversed thus far. */
1091      path_so_far->data[path_so_far->len] = '/';
1092      path_so_far->len += strlen(entry) + 1;
1093      path_so_far->data[path_so_far->len] = '\0';
1094
1095      if (*entry == '\0')
1096        {
1097          /* Given the behavior of svn_fs__next_entry_name(), this
1098             happens when the path either starts or ends with a slash.
1099             In either case, we stay put: the current directory stays
1100             the same, and we add nothing to the parent path. */
1101          child = here;
1102        }
1103      else
1104        {
1105          copy_id_inherit_t inherit;
1106          const char *copy_path = NULL;
1107          dag_node_t *cached_node = NULL;
1108
1109          /* If we found a directory entry, follow it.  First, we
1110             check our node cache, and, failing that, we hit the DAG
1111             layer.  Don't bother to contact the cache for the last
1112             element if we already know the lookup to fail for the
1113             complete path. */
1114          if (next || !(flags & open_path_uncached))
1115            SVN_ERR(dag_node_cache_get(&cached_node, root, path_so_far->data,
1116                                       pool));
1117          if (cached_node)
1118            child = cached_node;
1119          else
1120            SVN_ERR(svn_fs_fs__dag_open(&child, here, entry, pool, iterpool));
1121
1122          /* "file not found" requires special handling.  */
1123          if (child == NULL)
1124            {
1125              /* If this was the last path component, and the caller
1126                 said it was optional, then don't return an error;
1127                 just put a NULL node pointer in the path.  */
1128
1129              if ((flags & open_path_last_optional)
1130                  && (! next || *next == '\0'))
1131                {
1132                  parent_path = make_parent_path(NULL, entry, parent_path,
1133                                                 pool);
1134                  break;
1135                }
1136              else if (flags & open_path_allow_null)
1137                {
1138                  parent_path = NULL;
1139                  break;
1140                }
1141              else
1142                {
1143                  /* Build a better error message than svn_fs_fs__dag_open
1144                     can provide, giving the root and full path name.  */
1145                  return SVN_FS__NOT_FOUND(root, path);
1146                }
1147            }
1148
1149          if (flags & open_path_node_only)
1150            {
1151              /* Shortcut: the caller only wants the final DAG node. */
1152              parent_path->node = child;
1153            }
1154          else
1155            {
1156              /* Now, make a parent_path item for CHILD. */
1157              parent_path = make_parent_path(child, entry, parent_path, pool);
1158              if (is_txn_path)
1159                {
1160                  SVN_ERR(get_copy_inheritance(&inherit, &copy_path, fs,
1161                                               parent_path, iterpool));
1162                  parent_path->copy_inherit = inherit;
1163                  parent_path->copy_src_path = apr_pstrdup(pool, copy_path);
1164                }
1165            }
1166
1167          /* Cache the node we found (if it wasn't already cached). */
1168          if (! cached_node)
1169            SVN_ERR(dag_node_cache_set(root, path_so_far->data, child,
1170                                       iterpool));
1171        }
1172
1173      /* Are we finished traversing the path?  */
1174      if (! next)
1175        break;
1176
1177      /* The path isn't finished yet; we'd better be in a directory.  */
1178      if (svn_fs_fs__dag_node_kind(child) != svn_node_dir)
1179        {
1180          /* Since this is not a directory and we are looking for some
1181             sub-path, that sub-path will not exist.  That will be o.k.,
1182             if we are just here to check for the path's existence. */
1183          if (flags & open_path_allow_null)
1184            {
1185              parent_path = NULL;
1186              break;
1187            }
1188
1189          /* It's really a problem ... */
1190          return svn_error_trace(
1191                   err_not_directory(root, path_so_far->data, iterpool));
1192        }
1193
1194      rest = next;
1195      here = child;
1196    }
1197
1198  svn_pool_destroy(iterpool);
1199  *parent_path_p = parent_path;
1200  return SVN_NO_ERROR;
1201}
1202
1203
1204/* Make the node referred to by PARENT_PATH mutable, if it isn't
1205   already, allocating from POOL.  ROOT must be the root from which
1206   PARENT_PATH descends.  Clone any parent directories as needed.
1207   Adjust the dag nodes in PARENT_PATH to refer to the clones.  Use
1208   ERROR_PATH in error messages.  */
1209static svn_error_t *
1210make_path_mutable(svn_fs_root_t *root,
1211                  parent_path_t *parent_path,
1212                  const char *error_path,
1213                  apr_pool_t *pool)
1214{
1215  dag_node_t *clone;
1216  const svn_fs_fs__id_part_t *txn_id = root_txn_id(root);
1217
1218  /* Is the node mutable already?  */
1219  if (svn_fs_fs__dag_check_mutable(parent_path->node))
1220    return SVN_NO_ERROR;
1221
1222  /* Are we trying to clone the root, or somebody's child node?  */
1223  if (parent_path->parent)
1224    {
1225      const svn_fs_id_t *parent_id, *child_id, *copyroot_id;
1226      svn_fs_fs__id_part_t copy_id = { SVN_INVALID_REVNUM, 0 };
1227      svn_fs_fs__id_part_t *copy_id_ptr = &copy_id;
1228      copy_id_inherit_t inherit = parent_path->copy_inherit;
1229      const char *clone_path, *copyroot_path;
1230      svn_revnum_t copyroot_rev;
1231      svn_boolean_t is_parent_copyroot = FALSE;
1232      svn_fs_root_t *copyroot_root;
1233      dag_node_t *copyroot_node;
1234
1235      /* We're trying to clone somebody's child.  Make sure our parent
1236         is mutable.  */
1237      SVN_ERR(make_path_mutable(root, parent_path->parent,
1238                                error_path, pool));
1239
1240      switch (inherit)
1241        {
1242        case copy_id_inherit_parent:
1243          parent_id = svn_fs_fs__dag_get_id(parent_path->parent->node);
1244          copy_id = *svn_fs_fs__id_copy_id(parent_id);
1245          break;
1246
1247        case copy_id_inherit_new:
1248          SVN_ERR(svn_fs_fs__reserve_copy_id(&copy_id, root->fs, txn_id,
1249                                             pool));
1250          break;
1251
1252        case copy_id_inherit_self:
1253          copy_id_ptr = NULL;
1254          break;
1255
1256        case copy_id_inherit_unknown:
1257        default:
1258          SVN_ERR_MALFUNCTION(); /* uh-oh -- somebody didn't calculate copy-ID
1259                      inheritance data. */
1260        }
1261
1262      /* Determine what copyroot our new child node should use. */
1263      SVN_ERR(svn_fs_fs__dag_get_copyroot(&copyroot_rev, &copyroot_path,
1264                                          parent_path->node));
1265      SVN_ERR(svn_fs_fs__revision_root(&copyroot_root, root->fs,
1266                                       copyroot_rev, pool));
1267      SVN_ERR(get_dag(&copyroot_node, copyroot_root, copyroot_path, pool));
1268
1269      child_id = svn_fs_fs__dag_get_id(parent_path->node);
1270      copyroot_id = svn_fs_fs__dag_get_id(copyroot_node);
1271      if (!svn_fs_fs__id_part_eq(svn_fs_fs__id_node_id(child_id),
1272                                 svn_fs_fs__id_node_id(copyroot_id)))
1273        is_parent_copyroot = TRUE;
1274
1275      /* Now make this node mutable.  */
1276      clone_path = parent_path_path(parent_path->parent, pool);
1277      SVN_ERR(svn_fs_fs__dag_clone_child(&clone,
1278                                         parent_path->parent->node,
1279                                         clone_path,
1280                                         parent_path->entry,
1281                                         copy_id_ptr, txn_id,
1282                                         is_parent_copyroot,
1283                                         pool));
1284
1285      /* Update the path cache. */
1286      SVN_ERR(dag_node_cache_set(root, parent_path_path(parent_path, pool),
1287                                 clone, pool));
1288    }
1289  else
1290    {
1291      /* We're trying to clone the root directory.  */
1292      SVN_ERR(mutable_root_node(&clone, root, error_path, pool));
1293    }
1294
1295  /* Update the PARENT_PATH link to refer to the clone.  */
1296  parent_path->node = clone;
1297
1298  return SVN_NO_ERROR;
1299}
1300
1301
1302/* Open the node identified by PATH in ROOT.  Set DAG_NODE_P to the
1303   node we find, allocated in POOL.  Return the error
1304   SVN_ERR_FS_NOT_FOUND if this node doesn't exist. */
1305static svn_error_t *
1306get_dag(dag_node_t **dag_node_p,
1307        svn_fs_root_t *root,
1308        const char *path,
1309        apr_pool_t *pool)
1310{
1311  parent_path_t *parent_path;
1312  dag_node_t *node = NULL;
1313
1314  /* First we look for the DAG in our cache
1315     (if the path may be canonical). */
1316  if (*path == '/')
1317    SVN_ERR(dag_node_cache_get(&node, root, path, pool));
1318
1319  if (! node)
1320    {
1321      /* Canonicalize the input PATH.  As it turns out, >95% of all paths
1322       * seen here during e.g. svnadmin verify are non-canonical, i.e.
1323       * miss the leading '/'.  Check for those quickly.
1324       *
1325       * For normalized paths, it is much faster to check the path than
1326       * to attempt a second cache lookup (which would fail). */
1327      if (*path != '/' || !svn_fs__is_canonical_abspath(path))
1328        {
1329          path = svn_fs__canonicalize_abspath(path, pool);
1330          SVN_ERR(dag_node_cache_get(&node, root, path, pool));
1331        }
1332
1333      if (! node)
1334        {
1335          /* Call open_path with no flags, as we want this to return an
1336           * error if the node for which we are searching doesn't exist. */
1337          SVN_ERR(open_path(&parent_path, root, path,
1338                            open_path_uncached | open_path_node_only,
1339                            FALSE, pool));
1340          node = parent_path->node;
1341
1342          /* No need to cache our find -- open_path() will do that for us. */
1343        }
1344    }
1345
1346  *dag_node_p = node;
1347  return SVN_NO_ERROR;
1348}
1349
1350
1351
1352/* Populating the `changes' table. */
1353
1354/* Add a change to the changes table in FS, keyed on transaction id
1355   TXN_ID, and indicated that a change of kind CHANGE_KIND occurred on
1356   PATH (whose node revision id is--or was, in the case of a
1357   deletion--NODEREV_ID), and optionally that TEXT_MODs, PROP_MODs or
1358   MERGEINFO_MODs occurred.  If the change resulted from a copy,
1359   COPYFROM_REV and COPYFROM_PATH specify under which revision and path
1360   the node was copied from.  If this was not part of a copy, COPYFROM_REV
1361   should be SVN_INVALID_REVNUM.  Do all this as part of POOL.  */
1362static svn_error_t *
1363add_change(svn_fs_t *fs,
1364           const svn_fs_fs__id_part_t *txn_id,
1365           const char *path,
1366           const svn_fs_id_t *noderev_id,
1367           svn_fs_path_change_kind_t change_kind,
1368           svn_boolean_t text_mod,
1369           svn_boolean_t prop_mod,
1370           svn_boolean_t mergeinfo_mod,
1371           svn_node_kind_t node_kind,
1372           svn_revnum_t copyfrom_rev,
1373           const char *copyfrom_path,
1374           apr_pool_t *pool)
1375{
1376  return svn_fs_fs__add_change(fs, txn_id,
1377                               svn_fs__canonicalize_abspath(path, pool),
1378                               noderev_id, change_kind,
1379                               text_mod, prop_mod, mergeinfo_mod,
1380                               node_kind, copyfrom_rev, copyfrom_path,
1381                               pool);
1382}
1383
1384
1385
1386/* Generic node operations.  */
1387
1388/* Get the id of a node referenced by path PATH in ROOT.  Return the
1389   id in *ID_P allocated in POOL. */
1390svn_error_t *
1391svn_fs_fs__node_id(const svn_fs_id_t **id_p,
1392                   svn_fs_root_t *root,
1393                   const char *path,
1394                   apr_pool_t *pool)
1395{
1396  if ((! root->is_txn_root)
1397      && (path[0] == '\0' || ((path[0] == '/') && (path[1] == '\0'))))
1398    {
1399      /* Optimize the case where we don't need any db access at all.
1400         The root directory ("" or "/") node is stored in the
1401         svn_fs_root_t object, and never changes when it's a revision
1402         root, so we can just reach in and grab it directly. */
1403      dag_node_t *root_dir = root->fsap_data;
1404      *id_p = svn_fs_fs__id_copy(svn_fs_fs__dag_get_id(root_dir), pool);
1405    }
1406  else
1407    {
1408      dag_node_t *node;
1409
1410      SVN_ERR(get_dag(&node, root, path, pool));
1411      *id_p = svn_fs_fs__id_copy(svn_fs_fs__dag_get_id(node), pool);
1412    }
1413  return SVN_NO_ERROR;
1414}
1415
1416static svn_error_t *
1417fs_node_relation(svn_fs_node_relation_t *relation,
1418                 svn_fs_root_t *root_a, const char *path_a,
1419                 svn_fs_root_t *root_b, const char *path_b,
1420                 apr_pool_t *pool)
1421{
1422  dag_node_t *node;
1423  const svn_fs_id_t *id_a, *id_b;
1424  svn_fs_fs__id_part_t node_id_a, node_id_b;
1425
1426  /* Root paths are a common special case. */
1427  svn_boolean_t a_is_root_dir
1428    = (path_a[0] == '\0') || ((path_a[0] == '/') && (path_a[1] == '\0'));
1429  svn_boolean_t b_is_root_dir
1430    = (path_b[0] == '\0') || ((path_b[0] == '/') && (path_b[1] == '\0'));
1431
1432  /* Another useful thing to know: Both are txns but not the same txn. */
1433  svn_boolean_t different_txn
1434    = root_a->is_txn_root && root_b->is_txn_root
1435        && strcmp(root_a->txn, root_b->txn);
1436
1437  /* Path from different repository are always unrelated. */
1438  if (root_a->fs != root_b->fs)
1439    {
1440      *relation = svn_fs_node_unrelated;
1441      return SVN_NO_ERROR;
1442    }
1443
1444  /* Are both (!) root paths? Then, they are related and we only test how
1445   * direct the relation is. */
1446  if (a_is_root_dir && b_is_root_dir)
1447    {
1448      /* For txn roots, root->REV is the base revision of that TXN. */
1449      *relation = (   (root_a->rev == root_b->rev)
1450                   && (root_a->is_txn_root == root_b->is_txn_root)
1451                   && !different_txn)
1452                ? svn_fs_node_unchanged
1453                : svn_fs_node_common_ancestor;
1454      return SVN_NO_ERROR;
1455    }
1456
1457  /* We checked for all separations between ID spaces (repos, txn).
1458   * Now, we can simply test for the ID values themselves. */
1459  SVN_ERR(get_dag(&node, root_a, path_a, pool));
1460  id_a = svn_fs_fs__dag_get_id(node);
1461  node_id_a = *svn_fs_fs__id_node_id(id_a);
1462
1463  SVN_ERR(get_dag(&node, root_b, path_b, pool));
1464  id_b = svn_fs_fs__dag_get_id(node);
1465  node_id_b = *svn_fs_fs__id_node_id(id_b);
1466
1467  /* Noderevs from different nodes are unrelated. */
1468  if (!svn_fs_fs__id_part_eq(&node_id_a, &node_id_b))
1469    {
1470      *relation = svn_fs_node_unrelated;
1471      return SVN_NO_ERROR;
1472    }
1473
1474  /* Noderevs have the same node-ID now. So, they *seem* to be related.
1475   *
1476   * Special case: Different txns may create the same (txn-local) node ID.
1477   * These are not related to each other, nor to any other node ID so far. */
1478  if (different_txn && node_id_a.revision == SVN_INVALID_REVNUM)
1479    {
1480      *relation = svn_fs_node_unrelated;
1481      return SVN_NO_ERROR;
1482    }
1483
1484  /* The noderevs are actually related.  Are they the same? */
1485  if (svn_fs_fs__id_eq(id_a, id_b))
1486    *relation = svn_fs_node_unchanged;
1487  else
1488    *relation = svn_fs_node_common_ancestor;
1489
1490  return SVN_NO_ERROR;
1491}
1492
1493svn_error_t *
1494svn_fs_fs__node_created_rev(svn_revnum_t *revision,
1495                            svn_fs_root_t *root,
1496                            const char *path,
1497                            apr_pool_t *pool)
1498{
1499  dag_node_t *node;
1500
1501  SVN_ERR(get_dag(&node, root, path, pool));
1502  return svn_fs_fs__dag_get_revision(revision, node, pool);
1503}
1504
1505
1506/* Set *CREATED_PATH to the path at which PATH under ROOT was created.
1507   Return a string allocated in POOL. */
1508static svn_error_t *
1509fs_node_created_path(const char **created_path,
1510                     svn_fs_root_t *root,
1511                     const char *path,
1512                     apr_pool_t *pool)
1513{
1514  dag_node_t *node;
1515
1516  SVN_ERR(get_dag(&node, root, path, pool));
1517  *created_path = svn_fs_fs__dag_get_created_path(node);
1518
1519  return SVN_NO_ERROR;
1520}
1521
1522/* Set *KIND_P to the type of node present at PATH under ROOT.  If
1523   PATH does not exist under ROOT, set *KIND_P to svn_node_none.  Use
1524   POOL for temporary allocation. */
1525svn_error_t *
1526svn_fs_fs__check_path(svn_node_kind_t *kind_p,
1527                      svn_fs_root_t *root,
1528                      const char *path,
1529                      apr_pool_t *pool)
1530{
1531  dag_node_t *node;
1532  svn_error_t *err;
1533
1534  err = get_dag(&node, root, path, pool);
1535  if (err &&
1536      ((err->apr_err == SVN_ERR_FS_NOT_FOUND)
1537       || (err->apr_err == SVN_ERR_FS_NOT_DIRECTORY)))
1538    {
1539      svn_error_clear(err);
1540      *kind_p = svn_node_none;
1541      return SVN_NO_ERROR;
1542    }
1543  else if (err)
1544    return svn_error_trace(err);
1545
1546  *kind_p = svn_fs_fs__dag_node_kind(node);
1547  return SVN_NO_ERROR;
1548}
1549
1550/* Set *VALUE_P to the value of the property named PROPNAME of PATH in
1551   ROOT.  If the node has no property by that name, set *VALUE_P to
1552   zero.  Allocate the result in POOL. */
1553static svn_error_t *
1554fs_node_prop(svn_string_t **value_p,
1555             svn_fs_root_t *root,
1556             const char *path,
1557             const char *propname,
1558             apr_pool_t *pool)
1559{
1560  dag_node_t *node;
1561  apr_hash_t *proplist;
1562
1563  SVN_ERR(get_dag(&node, root, path, pool));
1564  SVN_ERR(svn_fs_fs__dag_get_proplist(&proplist, node, pool));
1565  *value_p = NULL;
1566  if (proplist)
1567    *value_p = svn_hash_gets(proplist, propname);
1568
1569  return SVN_NO_ERROR;
1570}
1571
1572
1573/* Set *TABLE_P to the entire property list of PATH under ROOT, as an
1574   APR hash table allocated in POOL.  The resulting property table
1575   maps property names to pointers to svn_string_t objects containing
1576   the property value. */
1577static svn_error_t *
1578fs_node_proplist(apr_hash_t **table_p,
1579                 svn_fs_root_t *root,
1580                 const char *path,
1581                 apr_pool_t *pool)
1582{
1583  apr_hash_t *table;
1584  dag_node_t *node;
1585
1586  SVN_ERR(get_dag(&node, root, path, pool));
1587  SVN_ERR(svn_fs_fs__dag_get_proplist(&table, node, pool));
1588  *table_p = table ? table : apr_hash_make(pool);
1589
1590  return SVN_NO_ERROR;
1591}
1592
1593static svn_error_t *
1594fs_node_has_props(svn_boolean_t *has_props,
1595                  svn_fs_root_t *root,
1596                  const char *path,
1597                  apr_pool_t *scratch_pool)
1598{
1599  dag_node_t *node;
1600
1601  SVN_ERR(get_dag(&node, root, path, scratch_pool));
1602
1603  return svn_error_trace(svn_fs_fs__dag_has_props(has_props, node,
1604                                                  scratch_pool));
1605}
1606
1607static svn_error_t *
1608increment_mergeinfo_up_tree(parent_path_t *pp,
1609                            apr_int64_t increment,
1610                            apr_pool_t *pool)
1611{
1612  for (; pp; pp = pp->parent)
1613    SVN_ERR(svn_fs_fs__dag_increment_mergeinfo_count(pp->node,
1614                                                     increment,
1615                                                     pool));
1616
1617  return SVN_NO_ERROR;
1618}
1619
1620/* Change, add, or delete a node's property value.  The affected node
1621   is PATH under ROOT, the property value to modify is NAME, and VALUE
1622   points to either a string value to set the new contents to, or NULL
1623   if the property should be deleted.  Perform temporary allocations
1624   in POOL. */
1625static svn_error_t *
1626fs_change_node_prop(svn_fs_root_t *root,
1627                    const char *path,
1628                    const char *name,
1629                    const svn_string_t *value,
1630                    apr_pool_t *pool)
1631{
1632  parent_path_t *parent_path;
1633  apr_hash_t *proplist;
1634  const svn_fs_fs__id_part_t *txn_id;
1635  svn_boolean_t mergeinfo_mod = FALSE;
1636
1637  if (! root->is_txn_root)
1638    return SVN_FS__NOT_TXN(root);
1639  txn_id = root_txn_id(root);
1640
1641  path = svn_fs__canonicalize_abspath(path, pool);
1642  SVN_ERR(open_path(&parent_path, root, path, 0, TRUE, pool));
1643
1644  /* Check (non-recursively) to see if path is locked; if so, check
1645     that we can use it. */
1646  if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
1647    SVN_ERR(svn_fs_fs__allow_locked_operation(path, root->fs, FALSE, FALSE,
1648                                              pool));
1649
1650  SVN_ERR(make_path_mutable(root, parent_path, path, pool));
1651  SVN_ERR(svn_fs_fs__dag_get_proplist(&proplist, parent_path->node, pool));
1652
1653  /* If there's no proplist, but we're just deleting a property, exit now. */
1654  if ((! proplist) && (! value))
1655    return SVN_NO_ERROR;
1656
1657  /* Now, if there's no proplist, we know we need to make one. */
1658  if (! proplist)
1659    proplist = apr_hash_make(pool);
1660
1661  if (svn_fs_fs__fs_supports_mergeinfo(root->fs)
1662      && strcmp (name, SVN_PROP_MERGEINFO) == 0)
1663    {
1664      apr_int64_t increment = 0;
1665      svn_boolean_t had_mergeinfo;
1666      SVN_ERR(svn_fs_fs__dag_has_mergeinfo(&had_mergeinfo, parent_path->node));
1667
1668      if (value && !had_mergeinfo)
1669        increment = 1;
1670      else if (!value && had_mergeinfo)
1671        increment = -1;
1672
1673      if (increment != 0)
1674        {
1675          SVN_ERR(increment_mergeinfo_up_tree(parent_path, increment, pool));
1676          SVN_ERR(svn_fs_fs__dag_set_has_mergeinfo(parent_path->node,
1677                                                   (value != NULL), pool));
1678        }
1679
1680      mergeinfo_mod = TRUE;
1681    }
1682
1683  /* Set the property. */
1684  svn_hash_sets(proplist, name, value);
1685
1686  /* Overwrite the node's proplist. */
1687  SVN_ERR(svn_fs_fs__dag_set_proplist(parent_path->node, proplist,
1688                                      pool));
1689
1690  /* Make a record of this modification in the changes table. */
1691  return add_change(root->fs, txn_id, path,
1692                    svn_fs_fs__dag_get_id(parent_path->node),
1693                    svn_fs_path_change_modify, FALSE, TRUE, mergeinfo_mod,
1694                    svn_fs_fs__dag_node_kind(parent_path->node),
1695                    SVN_INVALID_REVNUM, NULL, pool);
1696}
1697
1698
1699/* Determine if the properties of two path/root combinations are
1700   different.  Set *CHANGED_P to TRUE if the properties at PATH1 under
1701   ROOT1 differ from those at PATH2 under ROOT2, or FALSE otherwise.
1702   Both roots must be in the same filesystem. */
1703static svn_error_t *
1704fs_props_changed(svn_boolean_t *changed_p,
1705                 svn_fs_root_t *root1,
1706                 const char *path1,
1707                 svn_fs_root_t *root2,
1708                 const char *path2,
1709                 svn_boolean_t strict,
1710                 apr_pool_t *pool)
1711{
1712  dag_node_t *node1, *node2;
1713
1714  /* Check that roots are in the same fs. */
1715  if (root1->fs != root2->fs)
1716    return svn_error_create
1717      (SVN_ERR_FS_GENERAL, NULL,
1718       _("Cannot compare property value between two different filesystems"));
1719
1720  SVN_ERR(get_dag(&node1, root1, path1, pool));
1721  SVN_ERR(get_dag(&node2, root2, path2, pool));
1722  return svn_fs_fs__dag_things_different(changed_p, NULL,
1723                                         node1, node2, strict, pool);
1724}
1725
1726
1727
1728/* Merges and commits. */
1729
1730/* Set *NODE to the root node of ROOT.  */
1731static svn_error_t *
1732get_root(dag_node_t **node, svn_fs_root_t *root, apr_pool_t *pool)
1733{
1734  return get_dag(node, root, "/", pool);
1735}
1736
1737
1738/* Set the contents of CONFLICT_PATH to PATH, and return an
1739   SVN_ERR_FS_CONFLICT error that indicates that there was a conflict
1740   at PATH.  Perform all allocations in POOL (except the allocation of
1741   CONFLICT_PATH, which should be handled outside this function).  */
1742static svn_error_t *
1743conflict_err(svn_stringbuf_t *conflict_path,
1744             const char *path)
1745{
1746  svn_stringbuf_set(conflict_path, path);
1747  return svn_error_createf(SVN_ERR_FS_CONFLICT, NULL,
1748                           _("Conflict at '%s'"), path);
1749}
1750
1751/* Compare the directory representations at nodes LHS and RHS and set
1752 * *CHANGED to TRUE, if at least one entry has been added or removed them.
1753 * Use POOL for temporary allocations.
1754 */
1755static svn_error_t *
1756compare_dir_structure(svn_boolean_t *changed,
1757                      dag_node_t *lhs,
1758                      dag_node_t *rhs,
1759                      apr_pool_t *pool)
1760{
1761  apr_array_header_t *lhs_entries;
1762  apr_array_header_t *rhs_entries;
1763  int i;
1764
1765  SVN_ERR(svn_fs_fs__dag_dir_entries(&lhs_entries, lhs, pool));
1766  SVN_ERR(svn_fs_fs__dag_dir_entries(&rhs_entries, rhs, pool));
1767
1768  /* different number of entries -> some addition / removal */
1769  if (lhs_entries->nelts != rhs_entries->nelts)
1770    {
1771      *changed = TRUE;
1772      return SVN_NO_ERROR;
1773    }
1774
1775  /* Since directories are sorted by name, we can simply compare their
1776     entries one-by-one without binary lookup etc. */
1777  for (i = 0; i < lhs_entries->nelts; ++i)
1778    {
1779      svn_fs_dirent_t *lhs_entry
1780        = APR_ARRAY_IDX(lhs_entries, i, svn_fs_dirent_t *);
1781      svn_fs_dirent_t *rhs_entry
1782        = APR_ARRAY_IDX(rhs_entries, i, svn_fs_dirent_t *);
1783
1784      if (strcmp(lhs_entry->name, rhs_entry->name)
1785          || !svn_fs_fs__id_part_eq(svn_fs_fs__id_node_id(lhs_entry->id),
1786                                    svn_fs_fs__id_node_id(rhs_entry->id))
1787          || !svn_fs_fs__id_part_eq(svn_fs_fs__id_copy_id(lhs_entry->id),
1788                                    svn_fs_fs__id_copy_id(rhs_entry->id)))
1789        {
1790          *changed = TRUE;
1791          return SVN_NO_ERROR;
1792        }
1793    }
1794
1795  *changed = FALSE;
1796  return SVN_NO_ERROR;
1797}
1798
1799/* Merge changes between ANCESTOR and SOURCE into TARGET.  ANCESTOR
1800 * and TARGET must be distinct node revisions.  TARGET_PATH should
1801 * correspond to TARGET's full path in its filesystem, and is used for
1802 * reporting conflict location.
1803 *
1804 * SOURCE, TARGET, and ANCESTOR are generally directories; this
1805 * function recursively merges the directories' contents.  If any are
1806 * files, this function simply returns an error whenever SOURCE,
1807 * TARGET, and ANCESTOR are all distinct node revisions.
1808 *
1809 * If there are differences between ANCESTOR and SOURCE that conflict
1810 * with changes between ANCESTOR and TARGET, this function returns an
1811 * SVN_ERR_FS_CONFLICT error, and updates CONFLICT_P to the name of the
1812 * conflicting node in TARGET, with TARGET_PATH prepended as a path.
1813 *
1814 * If there are no conflicting differences, CONFLICT_P is updated to
1815 * the empty string.
1816 *
1817 * CONFLICT_P must point to a valid svn_stringbuf_t.
1818 *
1819 * Do any necessary temporary allocation in POOL.
1820 */
1821static svn_error_t *
1822merge(svn_stringbuf_t *conflict_p,
1823      const char *target_path,
1824      dag_node_t *target,
1825      dag_node_t *source,
1826      dag_node_t *ancestor,
1827      const svn_fs_fs__id_part_t *txn_id,
1828      apr_int64_t *mergeinfo_increment_out,
1829      apr_pool_t *pool)
1830{
1831  const svn_fs_id_t *source_id, *target_id, *ancestor_id;
1832  apr_array_header_t *s_entries, *t_entries, *a_entries;
1833  int i, s_idx = -1, t_idx = -1;
1834  svn_fs_t *fs;
1835  apr_pool_t *iterpool;
1836  apr_int64_t mergeinfo_increment = 0;
1837  svn_boolean_t fs_supports_mergeinfo;
1838
1839  /* Make sure everyone comes from the same filesystem. */
1840  fs = svn_fs_fs__dag_get_fs(ancestor);
1841  if ((fs != svn_fs_fs__dag_get_fs(source))
1842      || (fs != svn_fs_fs__dag_get_fs(target)))
1843    {
1844      return svn_error_create
1845        (SVN_ERR_FS_CORRUPT, NULL,
1846         _("Bad merge; ancestor, source, and target not all in same fs"));
1847    }
1848
1849  /* We have the same fs, now check it. */
1850  SVN_ERR(svn_fs__check_fs(fs, TRUE));
1851
1852  source_id   = svn_fs_fs__dag_get_id(source);
1853  target_id   = svn_fs_fs__dag_get_id(target);
1854  ancestor_id = svn_fs_fs__dag_get_id(ancestor);
1855
1856  /* It's improper to call this function with ancestor == target. */
1857  if (svn_fs_fs__id_eq(ancestor_id, target_id))
1858    {
1859      svn_string_t *id_str = svn_fs_fs__id_unparse(target_id, pool);
1860      return svn_error_createf
1861        (SVN_ERR_FS_GENERAL, NULL,
1862         _("Bad merge; target '%s' has id '%s', same as ancestor"),
1863         target_path, id_str->data);
1864    }
1865
1866  svn_stringbuf_setempty(conflict_p);
1867
1868  /* Base cases:
1869   * Either no change made in source, or same change as made in target.
1870   * Both mean nothing to merge here.
1871   */
1872  if (svn_fs_fs__id_eq(ancestor_id, source_id)
1873      || (svn_fs_fs__id_eq(source_id, target_id)))
1874    return SVN_NO_ERROR;
1875
1876  /* Else proceed, knowing all three are distinct node revisions.
1877   *
1878   * How to merge from this point:
1879   *
1880   * if (not all 3 are directories)
1881   *   {
1882   *     early exit with conflict;
1883   *   }
1884   *
1885   * // Property changes may only be made to up-to-date
1886   * // directories, because once the client commits the prop
1887   * // change, it bumps the directory's revision, and therefore
1888   * // must be able to depend on there being no other changes to
1889   * // that directory in the repository.
1890   * if (target's property list differs from ancestor's)
1891   *    conflict;
1892   *
1893   * For each entry NAME in the directory ANCESTOR:
1894   *
1895   *   Let ANCESTOR-ENTRY, SOURCE-ENTRY, and TARGET-ENTRY be the IDs of
1896   *   the name within ANCESTOR, SOURCE, and TARGET respectively.
1897   *   (Possibly null if NAME does not exist in SOURCE or TARGET.)
1898   *
1899   *   If ANCESTOR-ENTRY == SOURCE-ENTRY, then:
1900   *     No changes were made to this entry while the transaction was in
1901   *     progress, so do nothing to the target.
1902   *
1903   *   Else if ANCESTOR-ENTRY == TARGET-ENTRY, then:
1904   *     A change was made to this entry while the transaction was in
1905   *     process, but the transaction did not touch this entry.  Replace
1906   *     TARGET-ENTRY with SOURCE-ENTRY.
1907   *
1908   *   Else:
1909   *     Changes were made to this entry both within the transaction and
1910   *     to the repository while the transaction was in progress.  They
1911   *     must be merged or declared to be in conflict.
1912   *
1913   *     If SOURCE-ENTRY and TARGET-ENTRY are both null, that's a
1914   *     double delete; flag a conflict.
1915   *
1916   *     If any of the three entries is of type file, declare a conflict.
1917   *
1918   *     If either SOURCE-ENTRY or TARGET-ENTRY is not a direct
1919   *     modification of ANCESTOR-ENTRY (determine by comparing the
1920   *     node-id fields), declare a conflict.  A replacement is
1921   *     incompatible with a modification or other replacement--even
1922   *     an identical replacement.
1923   *
1924   *     Direct modifications were made to the directory ANCESTOR-ENTRY
1925   *     in both SOURCE and TARGET.  Recursively merge these
1926   *     modifications.
1927   *
1928   * For each leftover entry NAME in the directory SOURCE:
1929   *
1930   *   If NAME exists in TARGET, declare a conflict.  Even if SOURCE and
1931   *   TARGET are adding exactly the same thing, two additions are not
1932   *   auto-mergeable with each other.
1933   *
1934   *   Add NAME to TARGET with the entry from SOURCE.
1935   *
1936   * Now that we are done merging the changes from SOURCE into the
1937   * directory TARGET, update TARGET's predecessor to be SOURCE.
1938   */
1939
1940  if ((svn_fs_fs__dag_node_kind(source) != svn_node_dir)
1941      || (svn_fs_fs__dag_node_kind(target) != svn_node_dir)
1942      || (svn_fs_fs__dag_node_kind(ancestor) != svn_node_dir))
1943    {
1944      return conflict_err(conflict_p, target_path);
1945    }
1946
1947
1948  /* Possible early merge failure: if target and ancestor have
1949     different property lists, then the merge should fail.
1950     Propchanges can *only* be committed on an up-to-date directory.
1951     ### TODO: see issue #418 about the inelegance of this.
1952
1953     Another possible, similar, early merge failure: if source and
1954     ancestor have different property lists (meaning someone else
1955     changed directory properties while our commit transaction was
1956     happening), the merge should fail.  See issue #2751.
1957  */
1958  {
1959    node_revision_t *tgt_nr, *anc_nr, *src_nr;
1960    svn_boolean_t same;
1961    apr_pool_t *scratch_pool;
1962
1963    /* Get node revisions for our id's. */
1964    scratch_pool = svn_pool_create(pool);
1965    SVN_ERR(svn_fs_fs__get_node_revision(&tgt_nr, fs, target_id, pool,
1966                                         scratch_pool));
1967    svn_pool_clear(scratch_pool);
1968    SVN_ERR(svn_fs_fs__get_node_revision(&anc_nr, fs, ancestor_id, pool,
1969                                         scratch_pool));
1970    svn_pool_clear(scratch_pool);
1971    SVN_ERR(svn_fs_fs__get_node_revision(&src_nr, fs, source_id, pool,
1972                                         scratch_pool));
1973    svn_pool_destroy(scratch_pool);
1974
1975    /* Now compare the prop-keys of the skels.  Note that just because
1976       the keys are different -doesn't- mean the proplists have
1977       different contents. */
1978    SVN_ERR(svn_fs_fs__prop_rep_equal(&same, fs, src_nr, anc_nr, pool));
1979    if (! same)
1980      return conflict_err(conflict_p, target_path);
1981
1982    /* The directory entries got changed in the repository but the directory
1983       properties did not. */
1984    SVN_ERR(svn_fs_fs__prop_rep_equal(&same, fs, tgt_nr, anc_nr, pool));
1985    if (! same)
1986      {
1987        /* There is an incoming prop change for this directory.
1988           We will accept it only if the directory changes were mere updates
1989           to its entries, i.e. there were no additions or removals.
1990           Those could cause update problems to the working copy. */
1991        svn_boolean_t changed;
1992        SVN_ERR(compare_dir_structure(&changed, source, ancestor, pool));
1993
1994        if (changed)
1995          return conflict_err(conflict_p, target_path);
1996      }
1997  }
1998
1999  /* ### todo: it would be more efficient to simply check for a NULL
2000     entries hash where necessary below than to allocate an empty hash
2001     here, but another day, another day... */
2002  SVN_ERR(svn_fs_fs__dag_dir_entries(&s_entries, source, pool));
2003  SVN_ERR(svn_fs_fs__dag_dir_entries(&t_entries, target, pool));
2004  SVN_ERR(svn_fs_fs__dag_dir_entries(&a_entries, ancestor, pool));
2005
2006  fs_supports_mergeinfo = svn_fs_fs__fs_supports_mergeinfo(fs);
2007
2008  /* for each entry E in a_entries... */
2009  iterpool = svn_pool_create(pool);
2010  for (i = 0; i < a_entries->nelts; ++i)
2011    {
2012      svn_fs_dirent_t *s_entry, *t_entry, *a_entry;
2013      svn_pool_clear(iterpool);
2014
2015      a_entry = APR_ARRAY_IDX(a_entries, i, svn_fs_dirent_t *);
2016      s_entry = svn_fs_fs__find_dir_entry(s_entries, a_entry->name, &s_idx);
2017      t_entry = svn_fs_fs__find_dir_entry(t_entries, a_entry->name, &t_idx);
2018
2019      /* No changes were made to this entry while the transaction was
2020         in progress, so do nothing to the target. */
2021      if (s_entry && svn_fs_fs__id_eq(a_entry->id, s_entry->id))
2022        continue;
2023
2024      /* A change was made to this entry while the transaction was in
2025         process, but the transaction did not touch this entry. */
2026      else if (t_entry && svn_fs_fs__id_eq(a_entry->id, t_entry->id))
2027        {
2028          dag_node_t *t_ent_node;
2029          SVN_ERR(svn_fs_fs__dag_get_node(&t_ent_node, fs,
2030                                          t_entry->id, iterpool));
2031          if (fs_supports_mergeinfo)
2032            {
2033              apr_int64_t mergeinfo_start;
2034              SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_start,
2035                                                         t_ent_node));
2036              mergeinfo_increment -= mergeinfo_start;
2037            }
2038
2039          if (s_entry)
2040            {
2041              dag_node_t *s_ent_node;
2042              SVN_ERR(svn_fs_fs__dag_get_node(&s_ent_node, fs,
2043                                              s_entry->id, iterpool));
2044
2045              if (fs_supports_mergeinfo)
2046                {
2047                  apr_int64_t mergeinfo_end;
2048                  SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_end,
2049                                                             s_ent_node));
2050                  mergeinfo_increment += mergeinfo_end;
2051                }
2052
2053              SVN_ERR(svn_fs_fs__dag_set_entry(target, a_entry->name,
2054                                               s_entry->id,
2055                                               s_entry->kind,
2056                                               txn_id,
2057                                               pool));
2058            }
2059          else
2060            {
2061              SVN_ERR(svn_fs_fs__dag_delete(target, a_entry->name, txn_id,
2062                                            iterpool));
2063            }
2064        }
2065
2066      /* Changes were made to this entry both within the transaction
2067         and to the repository while the transaction was in progress.
2068         They must be merged or declared to be in conflict. */
2069      else
2070        {
2071          dag_node_t *s_ent_node, *t_ent_node, *a_ent_node;
2072          const char *new_tpath;
2073          apr_int64_t sub_mergeinfo_increment;
2074
2075          /* If SOURCE-ENTRY and TARGET-ENTRY are both null, that's a
2076             double delete; if one of them is null, that's a delete versus
2077             a modification. In any of these cases, flag a conflict. */
2078          if (s_entry == NULL || t_entry == NULL)
2079            return conflict_err(conflict_p,
2080                                svn_fspath__join(target_path,
2081                                                 a_entry->name,
2082                                                 iterpool));
2083
2084          /* If any of the three entries is of type file, flag a conflict. */
2085          if (s_entry->kind == svn_node_file
2086              || t_entry->kind == svn_node_file
2087              || a_entry->kind == svn_node_file)
2088            return conflict_err(conflict_p,
2089                                svn_fspath__join(target_path,
2090                                                 a_entry->name,
2091                                                 iterpool));
2092
2093          /* If either SOURCE-ENTRY or TARGET-ENTRY is not a direct
2094             modification of ANCESTOR-ENTRY, declare a conflict. */
2095          if (!svn_fs_fs__id_part_eq(svn_fs_fs__id_node_id(s_entry->id),
2096                                     svn_fs_fs__id_node_id(a_entry->id))
2097              || !svn_fs_fs__id_part_eq(svn_fs_fs__id_copy_id(s_entry->id),
2098                                        svn_fs_fs__id_copy_id(a_entry->id))
2099              || !svn_fs_fs__id_part_eq(svn_fs_fs__id_node_id(t_entry->id),
2100                                        svn_fs_fs__id_node_id(a_entry->id))
2101              || !svn_fs_fs__id_part_eq(svn_fs_fs__id_copy_id(t_entry->id),
2102                                        svn_fs_fs__id_copy_id(a_entry->id)))
2103            return conflict_err(conflict_p,
2104                                svn_fspath__join(target_path,
2105                                                 a_entry->name,
2106                                                 iterpool));
2107
2108          /* Direct modifications were made to the directory
2109             ANCESTOR-ENTRY in both SOURCE and TARGET.  Recursively
2110             merge these modifications. */
2111          SVN_ERR(svn_fs_fs__dag_get_node(&s_ent_node, fs,
2112                                          s_entry->id, iterpool));
2113          SVN_ERR(svn_fs_fs__dag_get_node(&t_ent_node, fs,
2114                                          t_entry->id, iterpool));
2115          SVN_ERR(svn_fs_fs__dag_get_node(&a_ent_node, fs,
2116                                          a_entry->id, iterpool));
2117          new_tpath = svn_fspath__join(target_path, t_entry->name, iterpool);
2118          SVN_ERR(merge(conflict_p, new_tpath,
2119                        t_ent_node, s_ent_node, a_ent_node,
2120                        txn_id,
2121                        &sub_mergeinfo_increment,
2122                        iterpool));
2123          if (fs_supports_mergeinfo)
2124            mergeinfo_increment += sub_mergeinfo_increment;
2125        }
2126    }
2127
2128  /* For each entry E in source but not in ancestor */
2129  for (i = 0; i < s_entries->nelts; ++i)
2130    {
2131      svn_fs_dirent_t *a_entry, *s_entry, *t_entry;
2132      dag_node_t *s_ent_node;
2133
2134      svn_pool_clear(iterpool);
2135
2136      s_entry = APR_ARRAY_IDX(s_entries, i, svn_fs_dirent_t *);
2137      a_entry = svn_fs_fs__find_dir_entry(a_entries, s_entry->name, &s_idx);
2138      t_entry = svn_fs_fs__find_dir_entry(t_entries, s_entry->name, &t_idx);
2139
2140      /* Process only entries in source that are NOT in ancestor. */
2141      if (a_entry)
2142        continue;
2143
2144      /* If NAME exists in TARGET, declare a conflict. */
2145      if (t_entry)
2146        return conflict_err(conflict_p,
2147                            svn_fspath__join(target_path,
2148                                             t_entry->name,
2149                                             iterpool));
2150
2151      SVN_ERR(svn_fs_fs__dag_get_node(&s_ent_node, fs,
2152                                      s_entry->id, iterpool));
2153      if (fs_supports_mergeinfo)
2154        {
2155          apr_int64_t mergeinfo_s;
2156          SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_s,
2157                                                     s_ent_node));
2158          mergeinfo_increment += mergeinfo_s;
2159        }
2160
2161      SVN_ERR(svn_fs_fs__dag_set_entry
2162              (target, s_entry->name, s_entry->id, s_entry->kind,
2163               txn_id, iterpool));
2164    }
2165  svn_pool_destroy(iterpool);
2166
2167  SVN_ERR(svn_fs_fs__dag_update_ancestry(target, source, pool));
2168
2169  if (fs_supports_mergeinfo)
2170    SVN_ERR(svn_fs_fs__dag_increment_mergeinfo_count(target,
2171                                                     mergeinfo_increment,
2172                                                     pool));
2173
2174  if (mergeinfo_increment_out)
2175    *mergeinfo_increment_out = mergeinfo_increment;
2176
2177  return SVN_NO_ERROR;
2178}
2179
2180/* Merge changes between an ancestor and SOURCE_NODE into
2181   TXN.  The ancestor is either ANCESTOR_NODE, or if
2182   that is null, TXN's base node.
2183
2184   If the merge is successful, TXN's base will become
2185   SOURCE_NODE, and its root node will have a new ID, a
2186   successor of SOURCE_NODE.
2187
2188   If a conflict results, update *CONFLICT to the path in the txn that
2189   conflicted; see the CONFLICT_P parameter of merge() for details. */
2190static svn_error_t *
2191merge_changes(dag_node_t *ancestor_node,
2192              dag_node_t *source_node,
2193              svn_fs_txn_t *txn,
2194              svn_stringbuf_t *conflict,
2195              apr_pool_t *pool)
2196{
2197  dag_node_t *txn_root_node;
2198  svn_fs_t *fs = txn->fs;
2199  const svn_fs_fs__id_part_t *txn_id = svn_fs_fs__txn_get_id(txn);
2200
2201  SVN_ERR(svn_fs_fs__dag_txn_root(&txn_root_node, fs, txn_id, pool));
2202
2203  if (ancestor_node == NULL)
2204    {
2205      SVN_ERR(svn_fs_fs__dag_txn_base_root(&ancestor_node, fs,
2206                                           txn_id, pool));
2207    }
2208
2209  if (svn_fs_fs__id_eq(svn_fs_fs__dag_get_id(ancestor_node),
2210                       svn_fs_fs__dag_get_id(txn_root_node)))
2211    {
2212      /* If no changes have been made in TXN since its current base,
2213         then it can't conflict with any changes since that base.
2214         The caller isn't supposed to call us in that case. */
2215      SVN_ERR_MALFUNCTION();
2216    }
2217  else
2218    SVN_ERR(merge(conflict, "/", txn_root_node,
2219                  source_node, ancestor_node, txn_id, NULL, pool));
2220
2221  return SVN_NO_ERROR;
2222}
2223
2224
2225svn_error_t *
2226svn_fs_fs__commit_txn(const char **conflict_p,
2227                      svn_revnum_t *new_rev,
2228                      svn_fs_txn_t *txn,
2229                      apr_pool_t *pool)
2230{
2231  /* How do commits work in Subversion?
2232   *
2233   * When you're ready to commit, here's what you have:
2234   *
2235   *    1. A transaction, with a mutable tree hanging off it.
2236   *    2. A base revision, against which TXN_TREE was made.
2237   *    3. A latest revision, which may be newer than the base rev.
2238   *
2239   * The problem is that if latest != base, then one can't simply
2240   * attach the txn root as the root of the new revision, because that
2241   * would lose all the changes between base and latest.  It is also
2242   * not acceptable to insist that base == latest; in a busy
2243   * repository, commits happen too fast to insist that everyone keep
2244   * their entire tree up-to-date at all times.  Non-overlapping
2245   * changes should not interfere with each other.
2246   *
2247   * The solution is to merge the changes between base and latest into
2248   * the txn tree [see the function merge()].  The txn tree is the
2249   * only one of the three trees that is mutable, so it has to be the
2250   * one to adjust.
2251   *
2252   * You might have to adjust it more than once, if a new latest
2253   * revision gets committed while you were merging in the previous
2254   * one.  For example:
2255   *
2256   *    1. Jane starts txn T, based at revision 6.
2257   *    2. Someone commits (or already committed) revision 7.
2258   *    3. Jane's starts merging the changes between 6 and 7 into T.
2259   *    4. Meanwhile, someone commits revision 8.
2260   *    5. Jane finishes the 6-->7 merge.  T could now be committed
2261   *       against a latest revision of 7, if only that were still the
2262   *       latest.  Unfortunately, 8 is now the latest, so...
2263   *    6. Jane starts merging the changes between 7 and 8 into T.
2264   *    7. Meanwhile, no one commits any new revisions.  Whew.
2265   *    8. Jane commits T, creating revision 9, whose tree is exactly
2266   *       T's tree, except immutable now.
2267   *
2268   * Lather, rinse, repeat.
2269   */
2270
2271  svn_error_t *err = SVN_NO_ERROR;
2272  svn_stringbuf_t *conflict = svn_stringbuf_create_empty(pool);
2273  svn_fs_t *fs = txn->fs;
2274  fs_fs_data_t *ffd = fs->fsap_data;
2275
2276  /* Limit memory usage when the repository has a high commit rate and
2277     needs to run the following while loop multiple times.  The memory
2278     growth without an iteration pool is very noticeable when the
2279     transaction modifies a node that has 20,000 sibling nodes. */
2280  apr_pool_t *iterpool = svn_pool_create(pool);
2281
2282  /* Initialize output params. */
2283  *new_rev = SVN_INVALID_REVNUM;
2284  if (conflict_p)
2285    *conflict_p = NULL;
2286
2287  while (1729)
2288    {
2289      svn_revnum_t youngish_rev;
2290      svn_fs_root_t *youngish_root;
2291      dag_node_t *youngish_root_node;
2292
2293      svn_pool_clear(iterpool);
2294
2295      /* Get the *current* youngest revision.  We call it "youngish"
2296         because new revisions might get committed after we've
2297         obtained it. */
2298
2299      SVN_ERR(svn_fs_fs__youngest_rev(&youngish_rev, fs, iterpool));
2300      SVN_ERR(svn_fs_fs__revision_root(&youngish_root, fs, youngish_rev,
2301                                       iterpool));
2302
2303      /* Get the dag node for the youngest revision.  Later we'll use
2304         it as the SOURCE argument to a merge, and if the merge
2305         succeeds, this youngest root node will become the new base
2306         root for the svn txn that was the target of the merge (but
2307         note that the youngest rev may have changed by then -- that's
2308         why we're careful to get this root in its own bdb txn
2309         here). */
2310      SVN_ERR(get_root(&youngish_root_node, youngish_root, iterpool));
2311
2312      /* Try to merge.  If the merge succeeds, the base root node of
2313         TARGET's txn will become the same as youngish_root_node, so
2314         any future merges will only be between that node and whatever
2315         the root node of the youngest rev is by then. */
2316      err = merge_changes(NULL, youngish_root_node, txn, conflict, iterpool);
2317      if (err)
2318        {
2319          if ((err->apr_err == SVN_ERR_FS_CONFLICT) && conflict_p)
2320            *conflict_p = conflict->data;
2321          goto cleanup;
2322        }
2323      txn->base_rev = youngish_rev;
2324
2325      /* Try to commit. */
2326      err = svn_fs_fs__commit(new_rev, fs, txn, iterpool);
2327      if (err && (err->apr_err == SVN_ERR_FS_TXN_OUT_OF_DATE))
2328        {
2329          /* Did someone else finish committing a new revision while we
2330             were in mid-merge or mid-commit?  If so, we'll need to
2331             loop again to merge the new changes in, then try to
2332             commit again.  Or if that's not what happened, then just
2333             return the error. */
2334          svn_revnum_t youngest_rev;
2335          SVN_ERR(svn_fs_fs__youngest_rev(&youngest_rev, fs, iterpool));
2336          if (youngest_rev == youngish_rev)
2337            goto cleanup;
2338          else
2339            svn_error_clear(err);
2340        }
2341      else if (err)
2342        {
2343          goto cleanup;
2344        }
2345      else
2346        {
2347          err = SVN_NO_ERROR;
2348          goto cleanup;
2349        }
2350    }
2351
2352 cleanup:
2353
2354  svn_fs_fs__reset_txn_caches(fs);
2355
2356  svn_pool_destroy(iterpool);
2357
2358  SVN_ERR(err);
2359
2360  if (ffd->pack_after_commit)
2361    {
2362      SVN_ERR(svn_fs_fs__pack(fs, 0, NULL, NULL, NULL, NULL, pool));
2363    }
2364
2365  return SVN_NO_ERROR;
2366}
2367
2368
2369/* Merge changes between two nodes into a third node.  Given nodes
2370   SOURCE_PATH under SOURCE_ROOT, TARGET_PATH under TARGET_ROOT and
2371   ANCESTOR_PATH under ANCESTOR_ROOT, modify target to contain all the
2372   changes between the ancestor and source.  If there are conflicts,
2373   return SVN_ERR_FS_CONFLICT and set *CONFLICT_P to a textual
2374   description of the offending changes.  Perform any temporary
2375   allocations in POOL. */
2376static svn_error_t *
2377fs_merge(const char **conflict_p,
2378         svn_fs_root_t *source_root,
2379         const char *source_path,
2380         svn_fs_root_t *target_root,
2381         const char *target_path,
2382         svn_fs_root_t *ancestor_root,
2383         const char *ancestor_path,
2384         apr_pool_t *pool)
2385{
2386  dag_node_t *source, *ancestor;
2387  svn_fs_txn_t *txn;
2388  svn_error_t *err;
2389  svn_stringbuf_t *conflict = svn_stringbuf_create_empty(pool);
2390
2391  if (! target_root->is_txn_root)
2392    return SVN_FS__NOT_TXN(target_root);
2393
2394  /* Paranoia. */
2395  if ((source_root->fs != ancestor_root->fs)
2396      || (target_root->fs != ancestor_root->fs))
2397    {
2398      return svn_error_create
2399        (SVN_ERR_FS_CORRUPT, NULL,
2400         _("Bad merge; ancestor, source, and target not all in same fs"));
2401    }
2402
2403  /* ### kff todo: is there any compelling reason to get the nodes in
2404     one db transaction?  Right now we don't; txn_body_get_root() gets
2405     one node at a time.  This will probably need to change:
2406
2407     Jim Blandy <jimb@zwingli.cygnus.com> writes:
2408     > svn_fs_merge needs to be a single transaction, to protect it against
2409     > people deleting parents of nodes it's working on, etc.
2410  */
2411
2412  /* Get the ancestor node. */
2413  SVN_ERR(get_root(&ancestor, ancestor_root, pool));
2414
2415  /* Get the source node. */
2416  SVN_ERR(get_root(&source, source_root, pool));
2417
2418  /* Open a txn for the txn root into which we're merging. */
2419  SVN_ERR(svn_fs_fs__open_txn(&txn, ancestor_root->fs, target_root->txn,
2420                              pool));
2421
2422  /* Merge changes between ANCESTOR and SOURCE into TXN. */
2423  err = merge_changes(ancestor, source, txn, conflict, pool);
2424  if (err)
2425    {
2426      if ((err->apr_err == SVN_ERR_FS_CONFLICT) && conflict_p)
2427        *conflict_p = conflict->data;
2428      return svn_error_trace(err);
2429    }
2430
2431  return SVN_NO_ERROR;
2432}
2433
2434svn_error_t *
2435svn_fs_fs__deltify(svn_fs_t *fs,
2436                   svn_revnum_t revision,
2437                   apr_pool_t *pool)
2438{
2439  /* Deltify is a no-op for fs_fs. */
2440
2441  return SVN_NO_ERROR;
2442}
2443
2444
2445
2446/* Directories.  */
2447
2448/* Set *TABLE_P to a newly allocated APR hash table containing the
2449   entries of the directory at PATH in ROOT.  The keys of the table
2450   are entry names, as byte strings, excluding the final null
2451   character; the table's values are pointers to svn_fs_dirent_t
2452   structures.  Allocate the table and its contents in POOL. */
2453static svn_error_t *
2454fs_dir_entries(apr_hash_t **table_p,
2455               svn_fs_root_t *root,
2456               const char *path,
2457               apr_pool_t *pool)
2458{
2459  dag_node_t *node;
2460  apr_hash_t *hash = svn_hash__make(pool);
2461  apr_array_header_t *table;
2462  int i;
2463
2464  /* Get the entries for this path in the caller's pool. */
2465  SVN_ERR(get_dag(&node, root, path, pool));
2466  SVN_ERR(svn_fs_fs__dag_dir_entries(&table, node, pool));
2467
2468  /* Convert directory array to hash. */
2469  for (i = 0; i < table->nelts; ++i)
2470    {
2471      svn_fs_dirent_t *entry = APR_ARRAY_IDX(table, i, svn_fs_dirent_t *);
2472      svn_hash_sets(hash, entry->name, entry);
2473    }
2474
2475  *table_p = hash;
2476  return SVN_NO_ERROR;
2477}
2478
2479static svn_error_t *
2480fs_dir_optimal_order(apr_array_header_t **ordered_p,
2481                     svn_fs_root_t *root,
2482                     apr_hash_t *entries,
2483                     apr_pool_t *result_pool,
2484                     apr_pool_t *scratch_pool)
2485{
2486  *ordered_p = svn_fs_fs__order_dir_entries(root->fs, entries, result_pool,
2487                                            scratch_pool);
2488
2489  return SVN_NO_ERROR;
2490}
2491
2492/* Raise an error if PATH contains a newline because FSFS cannot handle
2493 * such paths. See issue #4340. */
2494static svn_error_t *
2495check_newline(const char *path, apr_pool_t *pool)
2496{
2497  char *c = strchr(path, '\n');
2498
2499  if (c)
2500    return svn_error_createf(SVN_ERR_FS_PATH_SYNTAX, NULL,
2501       _("Invalid control character '0x%02x' in path '%s'"),
2502       (unsigned char)*c, svn_path_illegal_path_escape(path, pool));
2503
2504  return SVN_NO_ERROR;
2505}
2506
2507/* Create a new directory named PATH in ROOT.  The new directory has
2508   no entries, and no properties.  ROOT must be the root of a
2509   transaction, not a revision.  Do any necessary temporary allocation
2510   in POOL.  */
2511static svn_error_t *
2512fs_make_dir(svn_fs_root_t *root,
2513            const char *path,
2514            apr_pool_t *pool)
2515{
2516  parent_path_t *parent_path;
2517  dag_node_t *sub_dir;
2518  const svn_fs_fs__id_part_t *txn_id = root_txn_id(root);
2519
2520  SVN_ERR(check_newline(path, pool));
2521
2522  path = svn_fs__canonicalize_abspath(path, pool);
2523  SVN_ERR(open_path(&parent_path, root, path, open_path_last_optional,
2524                    TRUE, pool));
2525
2526  /* Check (recursively) to see if some lock is 'reserving' a path at
2527     that location, or even some child-path; if so, check that we can
2528     use it. */
2529  if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
2530    SVN_ERR(svn_fs_fs__allow_locked_operation(path, root->fs, TRUE, FALSE,
2531                                              pool));
2532
2533  /* If there's already a sub-directory by that name, complain.  This
2534     also catches the case of trying to make a subdirectory named `/'.  */
2535  if (parent_path->node)
2536    return SVN_FS__ALREADY_EXISTS(root, path);
2537
2538  /* Create the subdirectory.  */
2539  SVN_ERR(make_path_mutable(root, parent_path->parent, path, pool));
2540  SVN_ERR(svn_fs_fs__dag_make_dir(&sub_dir,
2541                                  parent_path->parent->node,
2542                                  parent_path_path(parent_path->parent,
2543                                                   pool),
2544                                  parent_path->entry,
2545                                  txn_id,
2546                                  pool));
2547
2548  /* Add this directory to the path cache. */
2549  SVN_ERR(dag_node_cache_set(root, parent_path_path(parent_path, pool),
2550                             sub_dir, pool));
2551
2552  /* Make a record of this modification in the changes table. */
2553  return add_change(root->fs, txn_id, path, svn_fs_fs__dag_get_id(sub_dir),
2554                    svn_fs_path_change_add, FALSE, FALSE, FALSE,
2555                    svn_node_dir, SVN_INVALID_REVNUM, NULL, pool);
2556}
2557
2558
2559/* Delete the node at PATH under ROOT.  ROOT must be a transaction
2560   root.  Perform temporary allocations in POOL. */
2561static svn_error_t *
2562fs_delete_node(svn_fs_root_t *root,
2563               const char *path,
2564               apr_pool_t *pool)
2565{
2566  parent_path_t *parent_path;
2567  const svn_fs_fs__id_part_t *txn_id;
2568  apr_int64_t mergeinfo_count = 0;
2569  svn_node_kind_t kind;
2570
2571  if (! root->is_txn_root)
2572    return SVN_FS__NOT_TXN(root);
2573
2574  txn_id = root_txn_id(root);
2575  path = svn_fs__canonicalize_abspath(path, pool);
2576  SVN_ERR(open_path(&parent_path, root, path, 0, TRUE, pool));
2577  kind = svn_fs_fs__dag_node_kind(parent_path->node);
2578
2579  /* We can't remove the root of the filesystem.  */
2580  if (! parent_path->parent)
2581    return svn_error_create(SVN_ERR_FS_ROOT_DIR, NULL,
2582                            _("The root directory cannot be deleted"));
2583
2584  /* Check to see if path (or any child thereof) is locked; if so,
2585     check that we can use the existing lock(s). */
2586  if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
2587    SVN_ERR(svn_fs_fs__allow_locked_operation(path, root->fs, TRUE, FALSE,
2588                                              pool));
2589
2590  /* Make the parent directory mutable, and do the deletion.  */
2591  SVN_ERR(make_path_mutable(root, parent_path->parent, path, pool));
2592  if (svn_fs_fs__fs_supports_mergeinfo(root->fs))
2593    SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_count,
2594                                               parent_path->node));
2595  SVN_ERR(svn_fs_fs__dag_delete(parent_path->parent->node,
2596                                parent_path->entry,
2597                                txn_id, pool));
2598
2599  /* Remove this node and any children from the path cache. */
2600  SVN_ERR(dag_node_cache_invalidate(root, parent_path_path(parent_path, pool),
2601                                    pool));
2602
2603  /* Update mergeinfo counts for parents */
2604  if (mergeinfo_count > 0)
2605    SVN_ERR(increment_mergeinfo_up_tree(parent_path->parent,
2606                                        -mergeinfo_count,
2607                                        pool));
2608
2609  /* Make a record of this modification in the changes table. */
2610  return add_change(root->fs, txn_id, path,
2611                    svn_fs_fs__dag_get_id(parent_path->node),
2612                    svn_fs_path_change_delete, FALSE, FALSE, FALSE, kind,
2613                    SVN_INVALID_REVNUM, NULL, pool);
2614}
2615
2616
2617/* Set *SAME_P to TRUE if FS1 and FS2 have the same UUID, else set to FALSE.
2618   Use POOL for temporary allocation only.
2619   Note: this code is duplicated between libsvn_fs_fs and libsvn_fs_base. */
2620static svn_error_t *
2621fs_same_p(svn_boolean_t *same_p,
2622          svn_fs_t *fs1,
2623          svn_fs_t *fs2,
2624          apr_pool_t *pool)
2625{
2626  *same_p = ! strcmp(fs1->uuid, fs2->uuid);
2627  return SVN_NO_ERROR;
2628}
2629
2630/* Copy the node at FROM_PATH under FROM_ROOT to TO_PATH under
2631   TO_ROOT.  If PRESERVE_HISTORY is set, then the copy is recorded in
2632   the copies table.  Perform temporary allocations in POOL. */
2633static svn_error_t *
2634copy_helper(svn_fs_root_t *from_root,
2635            const char *from_path,
2636            svn_fs_root_t *to_root,
2637            const char *to_path,
2638            svn_boolean_t preserve_history,
2639            apr_pool_t *pool)
2640{
2641  dag_node_t *from_node;
2642  parent_path_t *to_parent_path;
2643  const svn_fs_fs__id_part_t *txn_id = root_txn_id(to_root);
2644  svn_boolean_t same_p;
2645
2646  /* Use an error check, not an assert, because even the caller cannot
2647     guarantee that a filesystem's UUID has not changed "on the fly". */
2648  SVN_ERR(fs_same_p(&same_p, from_root->fs, to_root->fs, pool));
2649  if (! same_p)
2650    return svn_error_createf
2651      (SVN_ERR_UNSUPPORTED_FEATURE, NULL,
2652       _("Cannot copy between two different filesystems ('%s' and '%s')"),
2653       from_root->fs->path, to_root->fs->path);
2654
2655  /* more things that we can't do ATM */
2656  if (from_root->is_txn_root)
2657    return svn_error_create
2658      (SVN_ERR_UNSUPPORTED_FEATURE, NULL,
2659       _("Copy from mutable tree not currently supported"));
2660
2661  if (! to_root->is_txn_root)
2662    return svn_error_create
2663      (SVN_ERR_UNSUPPORTED_FEATURE, NULL,
2664       _("Copy immutable tree not supported"));
2665
2666  /* Get the NODE for FROM_PATH in FROM_ROOT.*/
2667  SVN_ERR(get_dag(&from_node, from_root, from_path, pool));
2668
2669  /* Build up the parent path from TO_PATH in TO_ROOT.  If the last
2670     component does not exist, it's not that big a deal.  We'll just
2671     make one there. */
2672  SVN_ERR(open_path(&to_parent_path, to_root, to_path,
2673                    open_path_last_optional, TRUE, pool));
2674
2675  /* Check to see if path (or any child thereof) is locked; if so,
2676     check that we can use the existing lock(s). */
2677  if (to_root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
2678    SVN_ERR(svn_fs_fs__allow_locked_operation(to_path, to_root->fs,
2679                                              TRUE, FALSE, pool));
2680
2681  /* If the destination node already exists as the same node as the
2682     source (in other words, this operation would result in nothing
2683     happening at all), just do nothing an return successfully,
2684     proud that you saved yourself from a tiresome task. */
2685  if (to_parent_path->node &&
2686      svn_fs_fs__id_eq(svn_fs_fs__dag_get_id(from_node),
2687                       svn_fs_fs__dag_get_id(to_parent_path->node)))
2688    return SVN_NO_ERROR;
2689
2690  if (! from_root->is_txn_root)
2691    {
2692      svn_fs_path_change_kind_t kind;
2693      dag_node_t *new_node;
2694      const char *from_canonpath;
2695      apr_int64_t mergeinfo_start;
2696      apr_int64_t mergeinfo_end;
2697
2698      /* If TO_PATH already existed prior to the copy, note that this
2699         operation is a replacement, not an addition. */
2700      if (to_parent_path->node)
2701        {
2702          kind = svn_fs_path_change_replace;
2703          if (svn_fs_fs__fs_supports_mergeinfo(to_root->fs))
2704            SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_start,
2705                                                       to_parent_path->node));
2706        }
2707      else
2708        {
2709          kind = svn_fs_path_change_add;
2710          mergeinfo_start = 0;
2711        }
2712
2713      if (svn_fs_fs__fs_supports_mergeinfo(to_root->fs))
2714        SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_end,
2715                                                   from_node));
2716
2717      /* Make sure the target node's parents are mutable.  */
2718      SVN_ERR(make_path_mutable(to_root, to_parent_path->parent,
2719                                to_path, pool));
2720
2721      /* Canonicalize the copyfrom path. */
2722      from_canonpath = svn_fs__canonicalize_abspath(from_path, pool);
2723
2724      SVN_ERR(svn_fs_fs__dag_copy(to_parent_path->parent->node,
2725                                  to_parent_path->entry,
2726                                  from_node,
2727                                  preserve_history,
2728                                  from_root->rev,
2729                                  from_canonpath,
2730                                  txn_id, pool));
2731
2732      if (kind != svn_fs_path_change_add)
2733        SVN_ERR(dag_node_cache_invalidate(to_root,
2734                                          parent_path_path(to_parent_path,
2735                                                           pool), pool));
2736
2737      if (svn_fs_fs__fs_supports_mergeinfo(to_root->fs)
2738          && mergeinfo_start != mergeinfo_end)
2739        SVN_ERR(increment_mergeinfo_up_tree(to_parent_path->parent,
2740                                            mergeinfo_end - mergeinfo_start,
2741                                            pool));
2742
2743      /* Make a record of this modification in the changes table. */
2744      SVN_ERR(get_dag(&new_node, to_root, to_path, pool));
2745      SVN_ERR(add_change(to_root->fs, txn_id, to_path,
2746                         svn_fs_fs__dag_get_id(new_node), kind, FALSE,
2747                         FALSE, FALSE, svn_fs_fs__dag_node_kind(from_node),
2748                         from_root->rev, from_canonpath, pool));
2749    }
2750  else
2751    {
2752      /* See IZ Issue #436 */
2753      /* Copying from transaction roots not currently available.
2754
2755         ### cmpilato todo someday: make this not so. :-) Note that
2756         when copying from mutable trees, you have to make sure that
2757         you aren't creating a cyclic graph filesystem, and a simple
2758         referencing operation won't cut it.  Currently, we should not
2759         be able to reach this clause, and the interface reports that
2760         this only works from immutable trees anyway, but JimB has
2761         stated that this requirement need not be necessary in the
2762         future. */
2763
2764      SVN_ERR_MALFUNCTION();
2765    }
2766
2767  return SVN_NO_ERROR;
2768}
2769
2770
2771/* Create a copy of FROM_PATH in FROM_ROOT named TO_PATH in TO_ROOT.
2772   If FROM_PATH is a directory, copy it recursively.  Temporary
2773   allocations are from POOL.*/
2774static svn_error_t *
2775fs_copy(svn_fs_root_t *from_root,
2776        const char *from_path,
2777        svn_fs_root_t *to_root,
2778        const char *to_path,
2779        apr_pool_t *pool)
2780{
2781  SVN_ERR(check_newline(to_path, pool));
2782
2783  return svn_error_trace(copy_helper(from_root,
2784                                     svn_fs__canonicalize_abspath(from_path,
2785                                                                  pool),
2786                                     to_root,
2787                                     svn_fs__canonicalize_abspath(to_path,
2788                                                                  pool),
2789                                     TRUE, pool));
2790}
2791
2792
2793/* Create a copy of FROM_PATH in FROM_ROOT named TO_PATH in TO_ROOT.
2794   If FROM_PATH is a directory, copy it recursively.  No history is
2795   preserved.  Temporary allocations are from POOL. */
2796static svn_error_t *
2797fs_revision_link(svn_fs_root_t *from_root,
2798                 svn_fs_root_t *to_root,
2799                 const char *path,
2800                 apr_pool_t *pool)
2801{
2802  if (! to_root->is_txn_root)
2803    return SVN_FS__NOT_TXN(to_root);
2804
2805  path = svn_fs__canonicalize_abspath(path, pool);
2806  return svn_error_trace(copy_helper(from_root, path, to_root, path,
2807                                     FALSE, pool));
2808}
2809
2810
2811/* Discover the copy ancestry of PATH under ROOT.  Return a relevant
2812   ancestor/revision combination in *PATH_P and *REV_P.  Temporary
2813   allocations are in POOL. */
2814static svn_error_t *
2815fs_copied_from(svn_revnum_t *rev_p,
2816               const char **path_p,
2817               svn_fs_root_t *root,
2818               const char *path,
2819               apr_pool_t *pool)
2820{
2821  dag_node_t *node;
2822
2823  /* There is no cached entry, look it up the old-fashioned
2824      way. */
2825  SVN_ERR(get_dag(&node, root, path, pool));
2826  SVN_ERR(svn_fs_fs__dag_get_copyfrom_rev(rev_p, node));
2827  SVN_ERR(svn_fs_fs__dag_get_copyfrom_path(path_p, node));
2828
2829  return SVN_NO_ERROR;
2830}
2831
2832
2833
2834/* Files.  */
2835
2836/* Create the empty file PATH under ROOT.  Temporary allocations are
2837   in POOL. */
2838static svn_error_t *
2839fs_make_file(svn_fs_root_t *root,
2840             const char *path,
2841             apr_pool_t *pool)
2842{
2843  parent_path_t *parent_path;
2844  dag_node_t *child;
2845  const svn_fs_fs__id_part_t *txn_id = root_txn_id(root);
2846
2847  SVN_ERR(check_newline(path, pool));
2848
2849  path = svn_fs__canonicalize_abspath(path, pool);
2850  SVN_ERR(open_path(&parent_path, root, path, open_path_last_optional,
2851                    TRUE, pool));
2852
2853  /* If there's already a file by that name, complain.
2854     This also catches the case of trying to make a file named `/'.  */
2855  if (parent_path->node)
2856    return SVN_FS__ALREADY_EXISTS(root, path);
2857
2858  /* Check (non-recursively) to see if path is locked;  if so, check
2859     that we can use it. */
2860  if (root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
2861    SVN_ERR(svn_fs_fs__allow_locked_operation(path, root->fs, FALSE, FALSE,
2862                                              pool));
2863
2864  /* Create the file.  */
2865  SVN_ERR(make_path_mutable(root, parent_path->parent, path, pool));
2866  SVN_ERR(svn_fs_fs__dag_make_file(&child,
2867                                   parent_path->parent->node,
2868                                   parent_path_path(parent_path->parent,
2869                                                    pool),
2870                                   parent_path->entry,
2871                                   txn_id,
2872                                   pool));
2873
2874  /* Add this file to the path cache. */
2875  SVN_ERR(dag_node_cache_set(root, parent_path_path(parent_path, pool), child,
2876                             pool));
2877
2878  /* Make a record of this modification in the changes table. */
2879  return add_change(root->fs, txn_id, path, svn_fs_fs__dag_get_id(child),
2880                    svn_fs_path_change_add, TRUE, FALSE, FALSE,
2881                    svn_node_file, SVN_INVALID_REVNUM, NULL, pool);
2882}
2883
2884
2885/* Set *LENGTH_P to the size of the file PATH under ROOT.  Temporary
2886   allocations are in POOL. */
2887static svn_error_t *
2888fs_file_length(svn_filesize_t *length_p,
2889               svn_fs_root_t *root,
2890               const char *path,
2891               apr_pool_t *pool)
2892{
2893  dag_node_t *file;
2894
2895  /* First create a dag_node_t from the root/path pair. */
2896  SVN_ERR(get_dag(&file, root, path, pool));
2897
2898  /* Now fetch its length */
2899  return svn_fs_fs__dag_file_length(length_p, file, pool);
2900}
2901
2902
2903/* Set *CHECKSUM to the checksum of type KIND for PATH under ROOT, or
2904   NULL if that information isn't available.  Temporary allocations
2905   are from POOL. */
2906static svn_error_t *
2907fs_file_checksum(svn_checksum_t **checksum,
2908                 svn_checksum_kind_t kind,
2909                 svn_fs_root_t *root,
2910                 const char *path,
2911                 apr_pool_t *pool)
2912{
2913  dag_node_t *file;
2914
2915  SVN_ERR(get_dag(&file, root, path, pool));
2916  return svn_fs_fs__dag_file_checksum(checksum, file, kind, pool);
2917}
2918
2919
2920/* --- Machinery for svn_fs_file_contents() ---  */
2921
2922/* Set *CONTENTS to a readable stream that will return the contents of
2923   PATH under ROOT.  The stream is allocated in POOL. */
2924static svn_error_t *
2925fs_file_contents(svn_stream_t **contents,
2926                 svn_fs_root_t *root,
2927                 const char *path,
2928                 apr_pool_t *pool)
2929{
2930  dag_node_t *node;
2931  svn_stream_t *file_stream;
2932
2933  /* First create a dag_node_t from the root/path pair. */
2934  SVN_ERR(get_dag(&node, root, path, pool));
2935
2936  /* Then create a readable stream from the dag_node_t. */
2937  SVN_ERR(svn_fs_fs__dag_get_contents(&file_stream, node, pool));
2938
2939  *contents = file_stream;
2940  return SVN_NO_ERROR;
2941}
2942
2943/* --- End machinery for svn_fs_file_contents() ---  */
2944
2945
2946/* --- Machinery for svn_fs_try_process_file_contents() ---  */
2947
2948static svn_error_t *
2949fs_try_process_file_contents(svn_boolean_t *success,
2950                             svn_fs_root_t *root,
2951                             const char *path,
2952                             svn_fs_process_contents_func_t processor,
2953                             void* baton,
2954                             apr_pool_t *pool)
2955{
2956  dag_node_t *node;
2957  SVN_ERR(get_dag(&node, root, path, pool));
2958
2959  return svn_fs_fs__dag_try_process_file_contents(success, node,
2960                                                  processor, baton, pool);
2961}
2962
2963/* --- End machinery for svn_fs_try_process_file_contents() ---  */
2964
2965
2966/* --- Machinery for svn_fs_apply_textdelta() ---  */
2967
2968
2969/* Local baton type for all the helper functions below. */
2970typedef struct txdelta_baton_t
2971{
2972  /* This is the custom-built window consumer given to us by the delta
2973     library;  it uniquely knows how to read data from our designated
2974     "source" stream, interpret the window, and write data to our
2975     designated "target" stream (in this case, our repos file.) */
2976  svn_txdelta_window_handler_t interpreter;
2977  void *interpreter_baton;
2978
2979  /* The original file info */
2980  svn_fs_root_t *root;
2981  const char *path;
2982
2983  /* Derived from the file info */
2984  dag_node_t *node;
2985
2986  svn_stream_t *source_stream;
2987  svn_stream_t *target_stream;
2988
2989  /* MD5 digest for the base text against which a delta is to be
2990     applied, and for the resultant fulltext, respectively.  Either or
2991     both may be null, in which case ignored. */
2992  svn_checksum_t *base_checksum;
2993  svn_checksum_t *result_checksum;
2994
2995  /* Pool used by db txns */
2996  apr_pool_t *pool;
2997
2998} txdelta_baton_t;
2999
3000
3001/* The main window handler returned by svn_fs_apply_textdelta. */
3002static svn_error_t *
3003window_consumer(svn_txdelta_window_t *window, void *baton)
3004{
3005  txdelta_baton_t *tb = (txdelta_baton_t *) baton;
3006
3007  /* Send the window right through to the custom window interpreter.
3008     In theory, the interpreter will then write more data to
3009     cb->target_string. */
3010  SVN_ERR(tb->interpreter(window, tb->interpreter_baton));
3011
3012  /* Is the window NULL?  If so, we're done.  The stream has already been
3013     closed by the interpreter. */
3014  if (! window)
3015    SVN_ERR(svn_fs_fs__dag_finalize_edits(tb->node, tb->result_checksum,
3016                                          tb->pool));
3017
3018  return SVN_NO_ERROR;
3019}
3020
3021/* Helper function for fs_apply_textdelta.  BATON is of type
3022   txdelta_baton_t. */
3023static svn_error_t *
3024apply_textdelta(void *baton, apr_pool_t *pool)
3025{
3026  txdelta_baton_t *tb = (txdelta_baton_t *) baton;
3027  parent_path_t *parent_path;
3028  const svn_fs_fs__id_part_t *txn_id = root_txn_id(tb->root);
3029
3030  /* Call open_path with no flags, as we want this to return an error
3031     if the node for which we are searching doesn't exist. */
3032  SVN_ERR(open_path(&parent_path, tb->root, tb->path, 0, TRUE, pool));
3033
3034  /* Check (non-recursively) to see if path is locked; if so, check
3035     that we can use it. */
3036  if (tb->root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
3037    SVN_ERR(svn_fs_fs__allow_locked_operation(tb->path, tb->root->fs,
3038                                              FALSE, FALSE, pool));
3039
3040  /* Now, make sure this path is mutable. */
3041  SVN_ERR(make_path_mutable(tb->root, parent_path, tb->path, pool));
3042  tb->node = parent_path->node;
3043
3044  if (tb->base_checksum)
3045    {
3046      svn_checksum_t *checksum;
3047
3048      /* Until we finalize the node, its data_key points to the old
3049         contents, in other words, the base text. */
3050      SVN_ERR(svn_fs_fs__dag_file_checksum(&checksum, tb->node,
3051                                           tb->base_checksum->kind, pool));
3052      if (!svn_checksum_match(tb->base_checksum, checksum))
3053        return svn_checksum_mismatch_err(tb->base_checksum, checksum, pool,
3054                                         _("Base checksum mismatch on '%s'"),
3055                                         tb->path);
3056    }
3057
3058  /* Make a readable "source" stream out of the current contents of
3059     ROOT/PATH; obviously, this must done in the context of a db_txn.
3060     The stream is returned in tb->source_stream. */
3061  SVN_ERR(svn_fs_fs__dag_get_contents(&(tb->source_stream),
3062                                      tb->node, tb->pool));
3063
3064  /* Make a writable "target" stream */
3065  SVN_ERR(svn_fs_fs__dag_get_edit_stream(&(tb->target_stream), tb->node,
3066                                         tb->pool));
3067
3068  /* Now, create a custom window handler that uses our two streams. */
3069  svn_txdelta_apply(tb->source_stream,
3070                    tb->target_stream,
3071                    NULL,
3072                    tb->path,
3073                    tb->pool,
3074                    &(tb->interpreter),
3075                    &(tb->interpreter_baton));
3076
3077  /* Make a record of this modification in the changes table. */
3078  return add_change(tb->root->fs, txn_id, tb->path,
3079                    svn_fs_fs__dag_get_id(tb->node),
3080                    svn_fs_path_change_modify, TRUE, FALSE, FALSE,
3081                    svn_node_file, SVN_INVALID_REVNUM, NULL, pool);
3082}
3083
3084
3085/* Set *CONTENTS_P and *CONTENTS_BATON_P to a window handler and baton
3086   that will accept text delta windows to modify the contents of PATH
3087   under ROOT.  Allocations are in POOL. */
3088static svn_error_t *
3089fs_apply_textdelta(svn_txdelta_window_handler_t *contents_p,
3090                   void **contents_baton_p,
3091                   svn_fs_root_t *root,
3092                   const char *path,
3093                   svn_checksum_t *base_checksum,
3094                   svn_checksum_t *result_checksum,
3095                   apr_pool_t *pool)
3096{
3097  txdelta_baton_t *tb = apr_pcalloc(pool, sizeof(*tb));
3098
3099  tb->root = root;
3100  tb->path = svn_fs__canonicalize_abspath(path, pool);
3101  tb->pool = pool;
3102  tb->base_checksum = svn_checksum_dup(base_checksum, pool);
3103  tb->result_checksum = svn_checksum_dup(result_checksum, pool);
3104
3105  SVN_ERR(apply_textdelta(tb, pool));
3106
3107  *contents_p = window_consumer;
3108  *contents_baton_p = tb;
3109  return SVN_NO_ERROR;
3110}
3111
3112/* --- End machinery for svn_fs_apply_textdelta() ---  */
3113
3114/* --- Machinery for svn_fs_apply_text() ---  */
3115
3116/* Baton for svn_fs_apply_text(). */
3117struct text_baton_t
3118{
3119  /* The original file info */
3120  svn_fs_root_t *root;
3121  const char *path;
3122
3123  /* Derived from the file info */
3124  dag_node_t *node;
3125
3126  /* The returned stream that will accept the file's new contents. */
3127  svn_stream_t *stream;
3128
3129  /* The actual fs stream that the returned stream will write to. */
3130  svn_stream_t *file_stream;
3131
3132  /* MD5 digest for the final fulltext written to the file.  May
3133     be null, in which case ignored. */
3134  svn_checksum_t *result_checksum;
3135
3136  /* Pool used by db txns */
3137  apr_pool_t *pool;
3138};
3139
3140
3141/* A wrapper around svn_fs_fs__dag_finalize_edits, but for
3142 * fulltext data, not text deltas.  Closes BATON->file_stream.
3143 *
3144 * Note: If you're confused about how this function relates to another
3145 * of similar name, think of it this way:
3146 *
3147 * svn_fs_apply_textdelta() ==> ... ==> txn_body_txdelta_finalize_edits()
3148 * svn_fs_apply_text()      ==> ... ==> txn_body_fulltext_finalize_edits()
3149 */
3150
3151/* Write function for the publically returned stream. */
3152static svn_error_t *
3153text_stream_writer(void *baton,
3154                   const char *data,
3155                   apr_size_t *len)
3156{
3157  struct text_baton_t *tb = baton;
3158
3159  /* Psst, here's some data.  Pass it on to the -real- file stream. */
3160  return svn_stream_write(tb->file_stream, data, len);
3161}
3162
3163/* Close function for the publically returned stream. */
3164static svn_error_t *
3165text_stream_closer(void *baton)
3166{
3167  struct text_baton_t *tb = baton;
3168
3169  /* Close the internal-use stream.  ### This used to be inside of
3170     txn_body_fulltext_finalize_edits(), but that invoked a nested
3171     Berkeley DB transaction -- scandalous! */
3172  SVN_ERR(svn_stream_close(tb->file_stream));
3173
3174  /* Need to tell fs that we're done sending text */
3175  return svn_fs_fs__dag_finalize_edits(tb->node, tb->result_checksum,
3176                                       tb->pool);
3177}
3178
3179
3180/* Helper function for fs_apply_text.  BATON is of type
3181   text_baton_t. */
3182static svn_error_t *
3183apply_text(void *baton, apr_pool_t *pool)
3184{
3185  struct text_baton_t *tb = baton;
3186  parent_path_t *parent_path;
3187  const svn_fs_fs__id_part_t *txn_id = root_txn_id(tb->root);
3188
3189  /* Call open_path with no flags, as we want this to return an error
3190     if the node for which we are searching doesn't exist. */
3191  SVN_ERR(open_path(&parent_path, tb->root, tb->path, 0, TRUE, pool));
3192
3193  /* Check (non-recursively) to see if path is locked; if so, check
3194     that we can use it. */
3195  if (tb->root->txn_flags & SVN_FS_TXN_CHECK_LOCKS)
3196    SVN_ERR(svn_fs_fs__allow_locked_operation(tb->path, tb->root->fs,
3197                                              FALSE, FALSE, pool));
3198
3199  /* Now, make sure this path is mutable. */
3200  SVN_ERR(make_path_mutable(tb->root, parent_path, tb->path, pool));
3201  tb->node = parent_path->node;
3202
3203  /* Make a writable stream for replacing the file's text. */
3204  SVN_ERR(svn_fs_fs__dag_get_edit_stream(&(tb->file_stream), tb->node,
3205                                         tb->pool));
3206
3207  /* Create a 'returnable' stream which writes to the file_stream. */
3208  tb->stream = svn_stream_create(tb, tb->pool);
3209  svn_stream_set_write(tb->stream, text_stream_writer);
3210  svn_stream_set_close(tb->stream, text_stream_closer);
3211
3212  /* Make a record of this modification in the changes table. */
3213  return add_change(tb->root->fs, txn_id, tb->path,
3214                    svn_fs_fs__dag_get_id(tb->node),
3215                    svn_fs_path_change_modify, TRUE, FALSE, FALSE,
3216                    svn_node_file, SVN_INVALID_REVNUM, NULL, pool);
3217}
3218
3219
3220/* Return a writable stream that will set the contents of PATH under
3221   ROOT.  RESULT_CHECKSUM is the MD5 checksum of the final result.
3222   Temporary allocations are in POOL. */
3223static svn_error_t *
3224fs_apply_text(svn_stream_t **contents_p,
3225              svn_fs_root_t *root,
3226              const char *path,
3227              svn_checksum_t *result_checksum,
3228              apr_pool_t *pool)
3229{
3230  struct text_baton_t *tb = apr_pcalloc(pool, sizeof(*tb));
3231
3232  tb->root = root;
3233  tb->path = svn_fs__canonicalize_abspath(path, pool);
3234  tb->pool = pool;
3235  tb->result_checksum = svn_checksum_dup(result_checksum, pool);
3236
3237  SVN_ERR(apply_text(tb, pool));
3238
3239  *contents_p = tb->stream;
3240  return SVN_NO_ERROR;
3241}
3242
3243/* --- End machinery for svn_fs_apply_text() ---  */
3244
3245
3246/* Check if the contents of PATH1 under ROOT1 are different from the
3247   contents of PATH2 under ROOT2.  If they are different set
3248   *CHANGED_P to TRUE, otherwise set it to FALSE. */
3249static svn_error_t *
3250fs_contents_changed(svn_boolean_t *changed_p,
3251                    svn_fs_root_t *root1,
3252                    const char *path1,
3253                    svn_fs_root_t *root2,
3254                    const char *path2,
3255                    svn_boolean_t strict,
3256                    apr_pool_t *pool)
3257{
3258  dag_node_t *node1, *node2;
3259
3260  /* Check that roots are in the same fs. */
3261  if (root1->fs != root2->fs)
3262    return svn_error_create
3263      (SVN_ERR_FS_GENERAL, NULL,
3264       _("Cannot compare file contents between two different filesystems"));
3265
3266  SVN_ERR(get_dag(&node1, root1, path1, pool));
3267  /* Make sure that path is file. */
3268  if (svn_fs_fs__dag_node_kind(node1) != svn_node_file)
3269    return svn_error_createf
3270      (SVN_ERR_FS_NOT_FILE, NULL, _("'%s' is not a file"), path1);
3271
3272  SVN_ERR(get_dag(&node2, root2, path2, pool));
3273  /* Make sure that path is file. */
3274  if (svn_fs_fs__dag_node_kind(node2) != svn_node_file)
3275    return svn_error_createf
3276      (SVN_ERR_FS_NOT_FILE, NULL, _("'%s' is not a file"), path2);
3277
3278  return svn_fs_fs__dag_things_different(NULL, changed_p,
3279                                         node1, node2, strict, pool);
3280}
3281
3282
3283
3284/* Public interface to computing file text deltas.  */
3285
3286static svn_error_t *
3287fs_get_file_delta_stream(svn_txdelta_stream_t **stream_p,
3288                         svn_fs_root_t *source_root,
3289                         const char *source_path,
3290                         svn_fs_root_t *target_root,
3291                         const char *target_path,
3292                         apr_pool_t *pool)
3293{
3294  dag_node_t *source_node, *target_node;
3295
3296  if (source_root && source_path)
3297    SVN_ERR(get_dag(&source_node, source_root, source_path, pool));
3298  else
3299    source_node = NULL;
3300  SVN_ERR(get_dag(&target_node, target_root, target_path, pool));
3301
3302  /* Create a delta stream that turns the source into the target.  */
3303  return svn_fs_fs__dag_get_file_delta_stream(stream_p, source_node,
3304                                              target_node, pool);
3305}
3306
3307
3308
3309/* Finding Changes */
3310
3311/* Set *CHANGED_PATHS_P to a newly allocated hash containing
3312   descriptions of the paths changed under ROOT.  The hash is keyed
3313   with const char * paths and has svn_fs_path_change2_t * values.  Use
3314   POOL for all allocations. */
3315static svn_error_t *
3316fs_paths_changed(apr_hash_t **changed_paths_p,
3317                 svn_fs_root_t *root,
3318                 apr_pool_t *pool)
3319{
3320  if (root->is_txn_root)
3321    return svn_fs_fs__txn_changes_fetch(changed_paths_p, root->fs,
3322                                        root_txn_id(root), pool);
3323  else
3324    return svn_fs_fs__paths_changed(changed_paths_p, root->fs, root->rev,
3325                                    pool);
3326}
3327
3328
3329/* Copy the contents of ENTRY at PATH with LEN to OUTPUT. */
3330static void
3331convert_path_change(svn_fs_path_change3_t *output,
3332                    const char *path,
3333                    size_t path_len,
3334                    svn_fs_path_change2_t *entry)
3335{
3336  output->path.data = path;
3337  output->path.len = path_len;
3338  output->change_kind = entry->change_kind;
3339  output->node_kind = entry->node_kind;
3340  output->text_mod = entry->text_mod;
3341  output->prop_mod = entry->prop_mod;
3342  output->mergeinfo_mod = entry->mergeinfo_mod;
3343  output->copyfrom_known = entry->copyfrom_known;
3344  output->copyfrom_rev = entry->copyfrom_rev;
3345  output->copyfrom_path = entry->copyfrom_path;
3346}
3347
3348/* FSAP data structure for in-txn changes list iterators. */
3349typedef struct fs_txn_changes_iterator_data_t
3350{
3351  /* Current iterator position. */
3352  apr_hash_index_t *hi;
3353
3354  /* For efficiency such that we don't need to dynamically allocate
3355     yet another copy of that data. */
3356  svn_fs_path_change3_t change;
3357} fs_txn_changes_iterator_data_t;
3358
3359/* Implement changes_iterator_vtable_t.get for in-txn change lists. */
3360static svn_error_t *
3361fs_txn_changes_iterator_get(svn_fs_path_change3_t **change,
3362                            svn_fs_path_change_iterator_t *iterator)
3363{
3364  fs_txn_changes_iterator_data_t *data = iterator->fsap_data;
3365
3366  if (data->hi)
3367    {
3368      const void *key;
3369      apr_ssize_t length;
3370      void *value;
3371      apr_hash_this(data->hi, &key, &length, &value);
3372
3373      convert_path_change(&data->change, key, length, value);
3374
3375      *change = &data->change;
3376      data->hi = apr_hash_next(data->hi);
3377    }
3378  else
3379    {
3380      *change = NULL;
3381    }
3382
3383  return SVN_NO_ERROR;
3384}
3385
3386static changes_iterator_vtable_t txn_changes_iterator_vtable =
3387{
3388  fs_txn_changes_iterator_get
3389};
3390
3391/* FSAP data structure for in-revision changes list iterators. */
3392typedef struct fs_revision_changes_iterator_data_t
3393{
3394  /* Context that tells the lower layers from where to fetch the next
3395     block of changes. */
3396  svn_fs_fs__changes_context_t *context;
3397
3398  /* Changes to send. */
3399  apr_array_header_t *changes;
3400
3401  /* Current indexes within CHANGES. */
3402  int idx;
3403
3404  /* For efficiency such that we don't need to dynamically allocate
3405     yet another copy of that data. */
3406  svn_fs_path_change3_t change;
3407
3408  /* A cleanable scratch pool in case we need one.
3409     No further sub-pool creation necessary. */
3410  apr_pool_t *scratch_pool;
3411} fs_revision_changes_iterator_data_t;
3412
3413/* Implement changes_iterator_vtable_t.get for in-revision change lists. */
3414static svn_error_t *
3415fs_revision_changes_iterator_get(svn_fs_path_change3_t **change,
3416                                 svn_fs_path_change_iterator_t *iterator)
3417{
3418  fs_revision_changes_iterator_data_t *data = iterator->fsap_data;
3419
3420  /* If we exhausted our block of changes and did not reach the end of the
3421     list, yet, fetch the next block.  Note that that block may be empty. */
3422  if ((data->idx >= data->changes->nelts) && !data->context->eol)
3423    {
3424      apr_pool_t *changes_pool = data->changes->pool;
3425
3426      /* Drop old changes block, read new block. */
3427      svn_pool_clear(changes_pool);
3428      SVN_ERR(svn_fs_fs__get_changes(&data->changes, data->context,
3429                                     changes_pool, data->scratch_pool));
3430      data->idx = 0;
3431
3432      /* Immediately release any temporary data. */
3433      svn_pool_clear(data->scratch_pool);
3434    }
3435
3436  if (data->idx < data->changes->nelts)
3437    {
3438      change_t *entry = APR_ARRAY_IDX(data->changes, data->idx, change_t *);
3439      convert_path_change(&data->change, entry->path.data, entry->path.len,
3440                          &entry->info);
3441
3442      *change = &data->change;
3443      ++data->idx;
3444    }
3445  else
3446    {
3447      *change = NULL;
3448    }
3449
3450  return SVN_NO_ERROR;
3451}
3452
3453static changes_iterator_vtable_t rev_changes_iterator_vtable =
3454{
3455  fs_revision_changes_iterator_get
3456};
3457
3458static svn_error_t *
3459fs_report_changes(svn_fs_path_change_iterator_t **iterator,
3460                  svn_fs_root_t *root,
3461                  apr_pool_t *result_pool,
3462                  apr_pool_t *scratch_pool)
3463{
3464  svn_fs_path_change_iterator_t *result = apr_pcalloc(result_pool,
3465                                                      sizeof(*result));
3466  if (root->is_txn_root)
3467    {
3468      fs_txn_changes_iterator_data_t *data = apr_pcalloc(result_pool,
3469                                                         sizeof(*data));
3470      apr_hash_t *changed_paths;
3471      SVN_ERR(svn_fs_fs__txn_changes_fetch(&changed_paths, root->fs,
3472                                           root_txn_id(root), result_pool));
3473
3474      data->hi = apr_hash_first(result_pool, changed_paths);
3475      result->fsap_data = data;
3476      result->vtable = &txn_changes_iterator_vtable;
3477    }
3478  else
3479    {
3480      /* The block of changes that we retrieve need to live in a separately
3481         cleanable pool. */
3482      apr_pool_t *changes_pool = svn_pool_create(result_pool);
3483
3484      /* Our iteration context info. */
3485      fs_revision_changes_iterator_data_t *data = apr_pcalloc(result_pool,
3486                                                              sizeof(*data));
3487
3488      /* This pool must remain valid as long as ITERATOR lives but will
3489         be used only for temporary allocations and will be cleaned up
3490         frequently.  So, this must be a sub-pool of RESULT_POOL. */
3491      data->scratch_pool = svn_pool_create(result_pool);
3492
3493      /* Fetch the first block of data. */
3494      SVN_ERR(svn_fs_fs__create_changes_context(&data->context,
3495                                                root->fs, root->rev,
3496                                                result_pool));
3497      SVN_ERR(svn_fs_fs__get_changes(&data->changes, data->context,
3498                                     changes_pool, scratch_pool));
3499
3500      /* Return the fully initialized object. */
3501      result->fsap_data = data;
3502      result->vtable = &rev_changes_iterator_vtable;
3503    }
3504
3505  *iterator = result;
3506
3507  return SVN_NO_ERROR;
3508}
3509
3510
3511/* Our coolio opaque history object. */
3512typedef struct fs_history_data_t
3513{
3514  /* filesystem object */
3515  svn_fs_t *fs;
3516
3517  /* path and revision of historical location */
3518  const char *path;
3519  svn_revnum_t revision;
3520
3521  /* internal-use hints about where to resume the history search. */
3522  const char *path_hint;
3523  svn_revnum_t rev_hint;
3524
3525  /* FALSE until the first call to svn_fs_history_prev(). */
3526  svn_boolean_t is_interesting;
3527
3528  /* If not SVN_INVALID_REVISION, we know that the next copy operation
3529     is at this revision. */
3530  svn_revnum_t next_copy;
3531
3532  /* If not NULL, this is the noderev ID of PATH@REVISION. */
3533  const svn_fs_id_t *current_id;
3534
3535} fs_history_data_t;
3536
3537static svn_fs_history_t *
3538assemble_history(svn_fs_t *fs,
3539                 const char *path,
3540                 svn_revnum_t revision,
3541                 svn_boolean_t is_interesting,
3542                 const char *path_hint,
3543                 svn_revnum_t rev_hint,
3544                 svn_revnum_t next_copy,
3545                 const svn_fs_id_t *current_id,
3546                 apr_pool_t *pool);
3547
3548
3549/* Set *HISTORY_P to an opaque node history object which represents
3550   PATH under ROOT.  ROOT must be a revision root.  Use POOL for all
3551   allocations. */
3552static svn_error_t *
3553fs_node_history(svn_fs_history_t **history_p,
3554                svn_fs_root_t *root,
3555                const char *path,
3556                apr_pool_t *result_pool,
3557                apr_pool_t *scratch_pool)
3558{
3559  svn_node_kind_t kind;
3560
3561  /* We require a revision root. */
3562  if (root->is_txn_root)
3563    return svn_error_create(SVN_ERR_FS_NOT_REVISION_ROOT, NULL, NULL);
3564
3565  /* And we require that the path exist in the root. */
3566  SVN_ERR(svn_fs_fs__check_path(&kind, root, path, scratch_pool));
3567  if (kind == svn_node_none)
3568    return SVN_FS__NOT_FOUND(root, path);
3569
3570  /* Okay, all seems well.  Build our history object and return it. */
3571  *history_p = assemble_history(root->fs, path, root->rev, FALSE, NULL,
3572                                SVN_INVALID_REVNUM, SVN_INVALID_REVNUM,
3573                                NULL, result_pool);
3574  return SVN_NO_ERROR;
3575}
3576
3577/* Find the youngest copyroot for path PARENT_PATH or its parents in
3578   filesystem FS, and store the copyroot in *REV_P and *PATH_P.
3579   Perform all allocations in POOL. */
3580static svn_error_t *
3581find_youngest_copyroot(svn_revnum_t *rev_p,
3582                       const char **path_p,
3583                       svn_fs_t *fs,
3584                       parent_path_t *parent_path,
3585                       apr_pool_t *pool)
3586{
3587  svn_revnum_t rev_mine;
3588  svn_revnum_t rev_parent = SVN_INVALID_REVNUM;
3589  const char *path_mine;
3590  const char *path_parent = NULL;
3591
3592  /* First find our parent's youngest copyroot. */
3593  if (parent_path->parent)
3594    SVN_ERR(find_youngest_copyroot(&rev_parent, &path_parent, fs,
3595                                   parent_path->parent, pool));
3596
3597  /* Find our copyroot. */
3598  SVN_ERR(svn_fs_fs__dag_get_copyroot(&rev_mine, &path_mine,
3599                                      parent_path->node));
3600
3601  /* If a parent and child were copied to in the same revision, prefer
3602     the child copy target, since it is the copy relevant to the
3603     history of the child. */
3604  if (rev_mine >= rev_parent)
3605    {
3606      *rev_p = rev_mine;
3607      *path_p = path_mine;
3608    }
3609  else
3610    {
3611      *rev_p = rev_parent;
3612      *path_p = path_parent;
3613    }
3614
3615  return SVN_NO_ERROR;
3616}
3617
3618
3619static svn_error_t *fs_closest_copy(svn_fs_root_t **root_p,
3620                                    const char **path_p,
3621                                    svn_fs_root_t *root,
3622                                    const char *path,
3623                                    apr_pool_t *pool)
3624{
3625  svn_fs_t *fs = root->fs;
3626  parent_path_t *parent_path, *copy_dst_parent_path;
3627  svn_revnum_t copy_dst_rev, created_rev;
3628  const char *copy_dst_path;
3629  svn_fs_root_t *copy_dst_root;
3630  dag_node_t *copy_dst_node;
3631
3632  /* Initialize return values. */
3633  *root_p = NULL;
3634  *path_p = NULL;
3635
3636  path = svn_fs__canonicalize_abspath(path, pool);
3637  SVN_ERR(open_path(&parent_path, root, path, 0, FALSE, pool));
3638
3639  /* Find the youngest copyroot in the path of this node-rev, which
3640     will indicate the target of the innermost copy affecting the
3641     node-rev. */
3642  SVN_ERR(find_youngest_copyroot(&copy_dst_rev, &copy_dst_path,
3643                                 fs, parent_path, pool));
3644  if (copy_dst_rev == 0)  /* There are no copies affecting this node-rev. */
3645    return SVN_NO_ERROR;
3646
3647  /* It is possible that this node was created from scratch at some
3648     revision between COPY_DST_REV and REV.  Make sure that PATH
3649     exists as of COPY_DST_REV and is related to this node-rev. */
3650  SVN_ERR(svn_fs_fs__revision_root(&copy_dst_root, fs, copy_dst_rev, pool));
3651  SVN_ERR(open_path(&copy_dst_parent_path, copy_dst_root, path,
3652                    open_path_node_only | open_path_allow_null, FALSE, pool));
3653  if (copy_dst_parent_path == NULL)
3654    return SVN_NO_ERROR;
3655
3656  copy_dst_node = copy_dst_parent_path->node;
3657  if (! svn_fs_fs__id_check_related(svn_fs_fs__dag_get_id(copy_dst_node),
3658                                    svn_fs_fs__dag_get_id(parent_path->node)))
3659    return SVN_NO_ERROR;
3660
3661  /* One final check must be done here.  If you copy a directory and
3662     create a new entity somewhere beneath that directory in the same
3663     txn, then we can't claim that the copy affected the new entity.
3664     For example, if you do:
3665
3666        copy dir1 dir2
3667        create dir2/new-thing
3668        commit
3669
3670     then dir2/new-thing was not affected by the copy of dir1 to dir2.
3671     We detect this situation by asking if PATH@COPY_DST_REV's
3672     created-rev is COPY_DST_REV, and that node-revision has no
3673     predecessors, then there is no relevant closest copy.
3674  */
3675  SVN_ERR(svn_fs_fs__dag_get_revision(&created_rev, copy_dst_node, pool));
3676  if (created_rev == copy_dst_rev)
3677    {
3678      const svn_fs_id_t *pred;
3679      SVN_ERR(svn_fs_fs__dag_get_predecessor_id(&pred, copy_dst_node));
3680      if (! pred)
3681        return SVN_NO_ERROR;
3682    }
3683
3684  /* The copy destination checks out.  Return it. */
3685  *root_p = copy_dst_root;
3686  *path_p = copy_dst_path;
3687  return SVN_NO_ERROR;
3688}
3689
3690
3691/* Set *PREV_PATH and *PREV_REV to the path and revision which
3692   represent the location at which PATH in FS was located immediately
3693   prior to REVISION iff there was a copy operation (to PATH or one of
3694   its parent directories) between that previous location and
3695   PATH@REVISION.
3696
3697   If there was no such copy operation in that portion of PATH's
3698   history, set *PREV_PATH to NULL and *PREV_REV to SVN_INVALID_REVNUM.  */
3699static svn_error_t *
3700prev_location(const char **prev_path,
3701              svn_revnum_t *prev_rev,
3702              svn_fs_t *fs,
3703              svn_fs_root_t *root,
3704              const char *path,
3705              apr_pool_t *pool)
3706{
3707  const char *copy_path, *copy_src_path, *remainder_path;
3708  svn_fs_root_t *copy_root;
3709  svn_revnum_t copy_src_rev;
3710
3711  /* Ask about the most recent copy which affected PATH@REVISION.  If
3712     there was no such copy, we're done.  */
3713  SVN_ERR(fs_closest_copy(&copy_root, &copy_path, root, path, pool));
3714  if (! copy_root)
3715    {
3716      *prev_rev = SVN_INVALID_REVNUM;
3717      *prev_path = NULL;
3718      return SVN_NO_ERROR;
3719    }
3720
3721  /* Ultimately, it's not the path of the closest copy's source that
3722     we care about -- it's our own path's location in the copy source
3723     revision.  So we'll tack the relative path that expresses the
3724     difference between the copy destination and our path in the copy
3725     revision onto the copy source path to determine this information.
3726
3727     In other words, if our path is "/branches/my-branch/foo/bar", and
3728     we know that the closest relevant copy was a copy of "/trunk" to
3729     "/branches/my-branch", then that relative path under the copy
3730     destination is "/foo/bar".  Tacking that onto the copy source
3731     path tells us that our path was located at "/trunk/foo/bar"
3732     before the copy.
3733  */
3734  SVN_ERR(fs_copied_from(&copy_src_rev, &copy_src_path,
3735                         copy_root, copy_path, pool));
3736  remainder_path = svn_fspath__skip_ancestor(copy_path, path);
3737  *prev_path = svn_fspath__join(copy_src_path, remainder_path, pool);
3738  *prev_rev = copy_src_rev;
3739  return SVN_NO_ERROR;
3740}
3741
3742
3743static svn_error_t *
3744fs_node_origin_rev(svn_revnum_t *revision,
3745                   svn_fs_root_t *root,
3746                   const char *path,
3747                   apr_pool_t *pool)
3748{
3749  svn_fs_t *fs = root->fs;
3750  const svn_fs_id_t *given_noderev_id, *cached_origin_id;
3751  const svn_fs_fs__id_part_t *node_id;
3752
3753  path = svn_fs__canonicalize_abspath(path, pool);
3754
3755  /* Check the cache first. */
3756  SVN_ERR(svn_fs_fs__node_id(&given_noderev_id, root, path, pool));
3757  node_id = svn_fs_fs__id_node_id(given_noderev_id);
3758
3759  /* Is it a brand new uncommitted node or a new-style node ID?
3760   * (committed old-style nodes will have a 0 revision value;
3761   * rev 0, number 0 is rev 0 root node). Note that != 0 includes
3762   * SVN_INVALID_REVNUM for uncommitted nodes. */
3763  if (node_id->revision != 0 || node_id->number == 0)
3764    {
3765      *revision = node_id->revision;
3766      return SVN_NO_ERROR;
3767    }
3768
3769  /* OK, it's an old-style ID?  Maybe it's cached. */
3770  SVN_ERR(svn_fs_fs__get_node_origin(&cached_origin_id,
3771                                     fs,
3772                                     node_id,
3773                                     pool));
3774  if (cached_origin_id != NULL)
3775    {
3776      *revision = svn_fs_fs__id_rev(cached_origin_id);
3777      return SVN_NO_ERROR;
3778    }
3779
3780  {
3781    /* Ah well, the answer isn't in the ID itself or in the cache.
3782       Let's actually calculate it, then. */
3783    svn_fs_root_t *curroot = root;
3784    apr_pool_t *subpool = svn_pool_create(pool);
3785    apr_pool_t *predidpool = svn_pool_create(pool);
3786    svn_stringbuf_t *lastpath = svn_stringbuf_create(path, pool);
3787    svn_revnum_t lastrev = SVN_INVALID_REVNUM;
3788    dag_node_t *node;
3789    const svn_fs_id_t *pred_id;
3790
3791    /* Walk the closest-copy chain back to the first copy in our history.
3792
3793       NOTE: We merely *assume* that this is faster than walking the
3794       predecessor chain, because we *assume* that copies of parent
3795       directories happen less often than modifications to a given item. */
3796    while (1)
3797      {
3798        svn_revnum_t currev;
3799        const char *curpath = lastpath->data;
3800
3801        svn_pool_clear(subpool);
3802
3803        /* Get a root pointing to LASTREV.  (The first time around,
3804           LASTREV is invalid, but that's cool because CURROOT is
3805           already initialized.)  */
3806        if (SVN_IS_VALID_REVNUM(lastrev))
3807          SVN_ERR(svn_fs_fs__revision_root(&curroot, fs, lastrev, subpool));
3808
3809        /* Find the previous location using the closest-copy shortcut. */
3810        SVN_ERR(prev_location(&curpath, &currev, fs, curroot, curpath,
3811                              subpool));
3812        if (! curpath)
3813          break;
3814
3815        /* Update our LASTPATH and LASTREV variables (which survive
3816           SUBPOOL). */
3817        svn_stringbuf_set(lastpath, curpath);
3818        lastrev = currev;
3819      }
3820
3821    /* Walk the predecessor links back to origin. */
3822    SVN_ERR(svn_fs_fs__node_id(&pred_id, curroot, lastpath->data, predidpool));
3823    do
3824      {
3825        svn_pool_clear(subpool);
3826        SVN_ERR(svn_fs_fs__dag_get_node(&node, fs, pred_id, subpool));
3827
3828        /* Why not just fetch the predecessor ID in PREDIDPOOL?
3829           Because svn_fs_fs__dag_get_predecessor_id() doesn't
3830           necessarily honor the passed-in pool, and might return a
3831           value cached in the node (which is allocated in
3832           SUBPOOL... maybe). */
3833        svn_pool_clear(predidpool);
3834        SVN_ERR(svn_fs_fs__dag_get_predecessor_id(&pred_id, node));
3835        pred_id = pred_id ? svn_fs_fs__id_copy(pred_id, predidpool) : NULL;
3836      }
3837    while (pred_id);
3838
3839    /* When we get here, NODE should be the first node-revision in our
3840       chain. */
3841    SVN_ERR(svn_fs_fs__dag_get_revision(revision, node, pool));
3842
3843    /* Wow, I don't want to have to do all that again.  Let's cache
3844       the result. */
3845    if (node_id->revision != SVN_INVALID_REVNUM)
3846      SVN_ERR(svn_fs_fs__set_node_origin(fs, node_id,
3847                                         svn_fs_fs__dag_get_id(node), pool));
3848
3849    svn_pool_destroy(subpool);
3850    svn_pool_destroy(predidpool);
3851    return SVN_NO_ERROR;
3852  }
3853}
3854
3855
3856static svn_error_t *
3857history_prev(svn_fs_history_t **prev_history,
3858             svn_fs_history_t *history,
3859             svn_boolean_t cross_copies,
3860             apr_pool_t *result_pool,
3861             apr_pool_t *scratch_pool)
3862{
3863  fs_history_data_t *fhd = history->fsap_data;
3864  const char *commit_path, *src_path, *path = fhd->path;
3865  svn_revnum_t commit_rev, src_rev, dst_rev;
3866  svn_revnum_t revision = fhd->revision;
3867  svn_fs_t *fs = fhd->fs;
3868  parent_path_t *parent_path;
3869  dag_node_t *node;
3870  svn_fs_root_t *root;
3871  svn_boolean_t reported = fhd->is_interesting;
3872  svn_revnum_t copyroot_rev;
3873  const char *copyroot_path;
3874  const svn_fs_id_t *pred_id = NULL;
3875
3876  /* Initialize our return value. */
3877  *prev_history = NULL;
3878
3879  /* When following history, there tend to be long sections of linear
3880     history where there are no copies at PATH or its parents.  Within
3881     these sections, we only need to follow the node history. */
3882  if (   SVN_IS_VALID_REVNUM(fhd->next_copy)
3883      && revision > fhd->next_copy
3884      && fhd->current_id)
3885    {
3886      /* We know the last reported node (CURRENT_ID) and the NEXT_COPY
3887         revision is somewhat further in the past. */
3888      node_revision_t *noderev;
3889      assert(reported);
3890
3891      /* Get the previous node change.  If there is none, then we already
3892         reported the initial addition and this history traversal is done. */
3893      SVN_ERR(svn_fs_fs__get_node_revision(&noderev, fs, fhd->current_id,
3894                                           scratch_pool, scratch_pool));
3895      if (! noderev->predecessor_id)
3896        return SVN_NO_ERROR;
3897
3898      /* If the previous node change is younger than the next copy, it is
3899         part of the linear history section. */
3900      commit_rev = svn_fs_fs__id_rev(noderev->predecessor_id);
3901      if (commit_rev > fhd->next_copy)
3902        {
3903          /* Within the linear history, simply report all node changes and
3904             continue with the respective predecessor. */
3905          *prev_history = assemble_history(fs, noderev->created_path,
3906                                           commit_rev, TRUE, NULL,
3907                                           SVN_INVALID_REVNUM,
3908                                           fhd->next_copy,
3909                                           noderev->predecessor_id,
3910                                           result_pool);
3911
3912          return SVN_NO_ERROR;
3913        }
3914
3915     /* We hit a copy. Fall back to the standard code path. */
3916    }
3917
3918  /* If our last history report left us hints about where to pickup
3919     the chase, then our last report was on the destination of a
3920     copy.  If we are crossing copies, start from those locations,
3921     otherwise, we're all done here.  */
3922  if (fhd->path_hint && SVN_IS_VALID_REVNUM(fhd->rev_hint))
3923    {
3924      reported = FALSE;
3925      if (! cross_copies)
3926        return SVN_NO_ERROR;
3927      path = fhd->path_hint;
3928      revision = fhd->rev_hint;
3929    }
3930
3931  /* Construct a ROOT for the current revision. */
3932  SVN_ERR(svn_fs_fs__revision_root(&root, fs, revision, scratch_pool));
3933
3934  /* Open PATH/REVISION, and get its node and a bunch of other
3935     goodies.  */
3936  SVN_ERR(open_path(&parent_path, root, path, 0, FALSE, scratch_pool));
3937  node = parent_path->node;
3938  commit_path = svn_fs_fs__dag_get_created_path(node);
3939  SVN_ERR(svn_fs_fs__dag_get_revision(&commit_rev, node, scratch_pool));
3940
3941  /* The Subversion filesystem is written in such a way that a given
3942     line of history may have at most one interesting history point
3943     per filesystem revision.  Either that node was edited (and
3944     possibly copied), or it was copied but not edited.  And a copy
3945     source cannot be from the same revision as its destination.  So,
3946     if our history revision matches its node's commit revision, we
3947     know that ... */
3948  if (revision == commit_rev)
3949    {
3950      if (! reported)
3951        {
3952          /* ... we either have not yet reported on this revision (and
3953             need now to do so) ... */
3954          *prev_history = assemble_history(fs, commit_path,
3955                                           commit_rev, TRUE, NULL,
3956                                           SVN_INVALID_REVNUM,
3957                                           SVN_INVALID_REVNUM, NULL,
3958                                           result_pool);
3959          return SVN_NO_ERROR;
3960        }
3961      else
3962        {
3963          /* ... or we *have* reported on this revision, and must now
3964             progress toward this node's predecessor (unless there is
3965             no predecessor, in which case we're all done!). */
3966          SVN_ERR(svn_fs_fs__dag_get_predecessor_id(&pred_id, node));
3967          if (! pred_id)
3968            return SVN_NO_ERROR;
3969
3970          /* Replace NODE and friends with the information from its
3971             predecessor. */
3972          SVN_ERR(svn_fs_fs__dag_get_node(&node, fs, pred_id, scratch_pool));
3973          commit_path = svn_fs_fs__dag_get_created_path(node);
3974          SVN_ERR(svn_fs_fs__dag_get_revision(&commit_rev, node, scratch_pool));
3975        }
3976    }
3977
3978  /* Find the youngest copyroot in the path of this node, including
3979     itself. */
3980  SVN_ERR(find_youngest_copyroot(&copyroot_rev, &copyroot_path, fs,
3981                                 parent_path, scratch_pool));
3982
3983  /* Initialize some state variables. */
3984  src_path = NULL;
3985  src_rev = SVN_INVALID_REVNUM;
3986  dst_rev = SVN_INVALID_REVNUM;
3987
3988  if (copyroot_rev > commit_rev)
3989    {
3990      const char *remainder_path;
3991      const char *copy_dst, *copy_src;
3992      svn_fs_root_t *copyroot_root;
3993
3994      SVN_ERR(svn_fs_fs__revision_root(&copyroot_root, fs, copyroot_rev,
3995                                       scratch_pool));
3996      SVN_ERR(get_dag(&node, copyroot_root, copyroot_path, scratch_pool));
3997      copy_dst = svn_fs_fs__dag_get_created_path(node);
3998
3999      /* If our current path was the very destination of the copy,
4000         then our new current path will be the copy source.  If our
4001         current path was instead the *child* of the destination of
4002         the copy, then figure out its previous location by taking its
4003         path relative to the copy destination and appending that to
4004         the copy source.  Finally, if our current path doesn't meet
4005         one of these other criteria ... ### for now just fallback to
4006         the old copy hunt algorithm. */
4007      remainder_path = svn_fspath__skip_ancestor(copy_dst, path);
4008
4009      if (remainder_path)
4010        {
4011          /* If we get here, then our current path is the destination
4012             of, or the child of the destination of, a copy.  Fill
4013             in the return values and get outta here.  */
4014          SVN_ERR(svn_fs_fs__dag_get_copyfrom_rev(&src_rev, node));
4015          SVN_ERR(svn_fs_fs__dag_get_copyfrom_path(&copy_src, node));
4016
4017          dst_rev = copyroot_rev;
4018          src_path = svn_fspath__join(copy_src, remainder_path, scratch_pool);
4019        }
4020    }
4021
4022  /* If we calculated a copy source path and revision, we'll make a
4023     'copy-style' history object. */
4024  if (src_path && SVN_IS_VALID_REVNUM(src_rev))
4025    {
4026      svn_boolean_t retry = FALSE;
4027
4028      /* It's possible for us to find a copy location that is the same
4029         as the history point we've just reported.  If that happens,
4030         we simply need to take another trip through this history
4031         search. */
4032      if ((dst_rev == revision) && reported)
4033        retry = TRUE;
4034
4035      *prev_history = assemble_history(fs, path, dst_rev, ! retry,
4036                                       src_path, src_rev,
4037                                       SVN_INVALID_REVNUM, NULL,
4038                                       result_pool);
4039    }
4040  else
4041    {
4042      /* We know the next copy revision.  If we are not at the copy rev
4043         itself, we will also know the predecessor node ID and the next
4044         invocation will use the optimized "linear history" code path. */
4045      *prev_history = assemble_history(fs, commit_path, commit_rev, TRUE,
4046                                       NULL, SVN_INVALID_REVNUM,
4047                                       copyroot_rev, pred_id, result_pool);
4048    }
4049
4050  return SVN_NO_ERROR;
4051}
4052
4053
4054/* Implement svn_fs_history_prev, set *PREV_HISTORY_P to a new
4055   svn_fs_history_t object that represents the predecessory of
4056   HISTORY.  If CROSS_COPIES is true, *PREV_HISTORY_P may be related
4057   only through a copy operation.  Perform all allocations in POOL. */
4058static svn_error_t *
4059fs_history_prev(svn_fs_history_t **prev_history_p,
4060                svn_fs_history_t *history,
4061                svn_boolean_t cross_copies,
4062                apr_pool_t *result_pool,
4063                apr_pool_t *scratch_pool)
4064{
4065  svn_fs_history_t *prev_history = NULL;
4066  fs_history_data_t *fhd = history->fsap_data;
4067  svn_fs_t *fs = fhd->fs;
4068
4069  /* Special case: the root directory changes in every single
4070     revision, no exceptions.  And, the root can't be the target (or
4071     child of a target -- duh) of a copy.  So, if that's our path,
4072     then we need only decrement our revision by 1, and there you go. */
4073  if (strcmp(fhd->path, "/") == 0)
4074    {
4075      if (! fhd->is_interesting)
4076        prev_history = assemble_history(fs, "/", fhd->revision,
4077                                        1, NULL, SVN_INVALID_REVNUM,
4078                                        SVN_INVALID_REVNUM, NULL,
4079                                        result_pool);
4080      else if (fhd->revision > 0)
4081        prev_history = assemble_history(fs, "/", fhd->revision - 1,
4082                                        1, NULL, SVN_INVALID_REVNUM,
4083                                        SVN_INVALID_REVNUM, NULL,
4084                                        result_pool);
4085    }
4086  else
4087    {
4088      apr_pool_t *iterpool = svn_pool_create(scratch_pool);
4089      prev_history = history;
4090
4091      while (1)
4092        {
4093          svn_pool_clear(iterpool);
4094          SVN_ERR(history_prev(&prev_history, prev_history, cross_copies,
4095                               result_pool, iterpool));
4096
4097          if (! prev_history)
4098            break;
4099          fhd = prev_history->fsap_data;
4100          if (fhd->is_interesting)
4101            break;
4102        }
4103
4104      svn_pool_destroy(iterpool);
4105    }
4106
4107  *prev_history_p = prev_history;
4108  return SVN_NO_ERROR;
4109}
4110
4111
4112/* Set *PATH and *REVISION to the path and revision for the HISTORY
4113   object.  Use POOL for all allocations. */
4114static svn_error_t *
4115fs_history_location(const char **path,
4116                    svn_revnum_t *revision,
4117                    svn_fs_history_t *history,
4118                    apr_pool_t *pool)
4119{
4120  fs_history_data_t *fhd = history->fsap_data;
4121
4122  *path = apr_pstrdup(pool, fhd->path);
4123  *revision = fhd->revision;
4124  return SVN_NO_ERROR;
4125}
4126
4127static history_vtable_t history_vtable = {
4128  fs_history_prev,
4129  fs_history_location
4130};
4131
4132/* Return a new history object (marked as "interesting") for PATH and
4133   REVISION, allocated in POOL, and with its members set to the values
4134   of the parameters provided.  Note that PATH and PATH_HINT get
4135   normalized and duplicated in POOL. */
4136static svn_fs_history_t *
4137assemble_history(svn_fs_t *fs,
4138                 const char *path,
4139                 svn_revnum_t revision,
4140                 svn_boolean_t is_interesting,
4141                 const char *path_hint,
4142                 svn_revnum_t rev_hint,
4143                 svn_revnum_t next_copy,
4144                 const svn_fs_id_t *current_id,
4145                 apr_pool_t *pool)
4146{
4147  svn_fs_history_t *history = apr_pcalloc(pool, sizeof(*history));
4148  fs_history_data_t *fhd = apr_pcalloc(pool, sizeof(*fhd));
4149  fhd->path = svn_fs__canonicalize_abspath(path, pool);
4150  fhd->revision = revision;
4151  fhd->is_interesting = is_interesting;
4152  fhd->path_hint = path_hint ? svn_fs__canonicalize_abspath(path_hint, pool)
4153                             : NULL;
4154  fhd->rev_hint = rev_hint;
4155  fhd->next_copy = next_copy;
4156  fhd->current_id = current_id ? svn_fs_fs__id_copy(current_id, pool) : NULL;
4157  fhd->fs = fs;
4158
4159  history->vtable = &history_vtable;
4160  history->fsap_data = fhd;
4161  return history;
4162}
4163
4164
4165/* mergeinfo queries */
4166
4167
4168/* DIR_DAG is a directory DAG node which has mergeinfo in its
4169   descendants.  This function iterates over its children.  For each
4170   child with immediate mergeinfo, call RECEIVER with it and BATON.
4171   For each child with descendants with mergeinfo, it recurses.  Note
4172   that it does *not* call the action on the path for DIR_DAG itself.
4173
4174   SCRATCH_POOL is used for temporary allocations, including the mergeinfo
4175   hashes passed to actions.
4176 */
4177static svn_error_t *
4178crawl_directory_dag_for_mergeinfo(svn_fs_root_t *root,
4179                                  const char *this_path,
4180                                  dag_node_t *dir_dag,
4181                                  svn_fs_mergeinfo_receiver_t receiver,
4182                                  void *baton,
4183                                  apr_pool_t *scratch_pool)
4184{
4185  apr_array_header_t *entries;
4186  int i;
4187  apr_pool_t *iterpool = svn_pool_create(scratch_pool);
4188
4189  SVN_ERR(svn_fs_fs__dag_dir_entries(&entries, dir_dag, scratch_pool));
4190  for (i = 0; i < entries->nelts; ++i)
4191    {
4192      svn_fs_dirent_t *dirent = APR_ARRAY_IDX(entries, i, svn_fs_dirent_t *);
4193      const char *kid_path;
4194      dag_node_t *kid_dag;
4195      svn_boolean_t has_mergeinfo, go_down;
4196
4197      svn_pool_clear(iterpool);
4198
4199      kid_path = svn_fspath__join(this_path, dirent->name, iterpool);
4200      SVN_ERR(get_dag(&kid_dag, root, kid_path, iterpool));
4201
4202      SVN_ERR(svn_fs_fs__dag_has_mergeinfo(&has_mergeinfo, kid_dag));
4203      SVN_ERR(svn_fs_fs__dag_has_descendants_with_mergeinfo(&go_down, kid_dag));
4204
4205      if (has_mergeinfo)
4206        {
4207          /* Save this particular node's mergeinfo. */
4208          apr_hash_t *proplist;
4209          svn_mergeinfo_t kid_mergeinfo;
4210          svn_string_t *mergeinfo_string;
4211          svn_error_t *err;
4212
4213          SVN_ERR(svn_fs_fs__dag_get_proplist(&proplist, kid_dag, iterpool));
4214          mergeinfo_string = svn_hash_gets(proplist, SVN_PROP_MERGEINFO);
4215          if (!mergeinfo_string)
4216            {
4217              svn_string_t *idstr = svn_fs_fs__id_unparse(dirent->id, iterpool);
4218              return svn_error_createf
4219                (SVN_ERR_FS_CORRUPT, NULL,
4220                 _("Node-revision #'%s' claims to have mergeinfo but doesn't"),
4221                 idstr->data);
4222            }
4223
4224          /* Issue #3896: If a node has syntactically invalid mergeinfo, then
4225             treat it as if no mergeinfo is present rather than raising a parse
4226             error. */
4227          err = svn_mergeinfo_parse(&kid_mergeinfo,
4228                                    mergeinfo_string->data,
4229                                    iterpool);
4230          if (err)
4231            {
4232              if (err->apr_err == SVN_ERR_MERGEINFO_PARSE_ERROR)
4233                svn_error_clear(err);
4234              else
4235                return svn_error_trace(err);
4236              }
4237          else
4238            {
4239              SVN_ERR(receiver(kid_path, kid_mergeinfo, baton, iterpool));
4240            }
4241        }
4242
4243      if (go_down)
4244        SVN_ERR(crawl_directory_dag_for_mergeinfo(root,
4245                                                  kid_path,
4246                                                  kid_dag,
4247                                                  receiver,
4248                                                  baton,
4249                                                  iterpool));
4250    }
4251
4252  svn_pool_destroy(iterpool);
4253  return SVN_NO_ERROR;
4254}
4255
4256/* Return the cache key as a combination of REV_ROOT->REV, the inheritance
4257   flags INHERIT and ADJUST_INHERITED_MERGEINFO, and the PATH.  The result
4258   will be allocated in POOL..
4259 */
4260static const char *
4261mergeinfo_cache_key(const char *path,
4262                    svn_fs_root_t *rev_root,
4263                    svn_mergeinfo_inheritance_t inherit,
4264                    svn_boolean_t adjust_inherited_mergeinfo,
4265                    apr_pool_t *pool)
4266{
4267  apr_int64_t number = rev_root->rev;
4268  number = number * 4
4269         + (inherit == svn_mergeinfo_nearest_ancestor ? 2 : 0)
4270         + (adjust_inherited_mergeinfo ? 1 : 0);
4271
4272  return svn_fs_fs__combine_number_and_string(number, path, pool);
4273}
4274
4275/* Calculates the mergeinfo for PATH under REV_ROOT using inheritance
4276   type INHERIT.  Returns it in *MERGEINFO, or NULL if there is none.
4277   The result is allocated in RESULT_POOL; SCRATCH_POOL is
4278   used for temporary allocations.
4279 */
4280static svn_error_t *
4281get_mergeinfo_for_path_internal(svn_mergeinfo_t *mergeinfo,
4282                                svn_fs_root_t *rev_root,
4283                                const char *path,
4284                                svn_mergeinfo_inheritance_t inherit,
4285                                svn_boolean_t adjust_inherited_mergeinfo,
4286                                apr_pool_t *result_pool,
4287                                apr_pool_t *scratch_pool)
4288{
4289  parent_path_t *parent_path, *nearest_ancestor;
4290  apr_hash_t *proplist;
4291  svn_string_t *mergeinfo_string;
4292
4293  path = svn_fs__canonicalize_abspath(path, scratch_pool);
4294
4295  SVN_ERR(open_path(&parent_path, rev_root, path, 0, FALSE, scratch_pool));
4296
4297  if (inherit == svn_mergeinfo_nearest_ancestor && ! parent_path->parent)
4298    return SVN_NO_ERROR;
4299
4300  if (inherit == svn_mergeinfo_nearest_ancestor)
4301    nearest_ancestor = parent_path->parent;
4302  else
4303    nearest_ancestor = parent_path;
4304
4305  while (TRUE)
4306    {
4307      svn_boolean_t has_mergeinfo;
4308
4309      SVN_ERR(svn_fs_fs__dag_has_mergeinfo(&has_mergeinfo,
4310                                           nearest_ancestor->node));
4311      if (has_mergeinfo)
4312        break;
4313
4314      /* No need to loop if we're looking for explicit mergeinfo. */
4315      if (inherit == svn_mergeinfo_explicit)
4316        {
4317          return SVN_NO_ERROR;
4318        }
4319
4320      nearest_ancestor = nearest_ancestor->parent;
4321
4322      /* Run out?  There's no mergeinfo. */
4323      if (!nearest_ancestor)
4324        {
4325          return SVN_NO_ERROR;
4326        }
4327    }
4328
4329  SVN_ERR(svn_fs_fs__dag_get_proplist(&proplist, nearest_ancestor->node,
4330                                      scratch_pool));
4331  mergeinfo_string = svn_hash_gets(proplist, SVN_PROP_MERGEINFO);
4332  if (!mergeinfo_string)
4333    return svn_error_createf
4334      (SVN_ERR_FS_CORRUPT, NULL,
4335       _("Node-revision '%s@%ld' claims to have mergeinfo but doesn't"),
4336       parent_path_path(nearest_ancestor, scratch_pool), rev_root->rev);
4337
4338  /* Parse the mergeinfo; store the result in *MERGEINFO. */
4339  {
4340    /* Issue #3896: If a node has syntactically invalid mergeinfo, then
4341       treat it as if no mergeinfo is present rather than raising a parse
4342       error. */
4343    svn_error_t *err = svn_mergeinfo_parse(mergeinfo,
4344                                           mergeinfo_string->data,
4345                                           result_pool);
4346    if (err)
4347      {
4348        if (err->apr_err == SVN_ERR_MERGEINFO_PARSE_ERROR)
4349          {
4350            svn_error_clear(err);
4351            err = NULL;
4352            *mergeinfo = NULL;
4353          }
4354        return svn_error_trace(err);
4355      }
4356  }
4357
4358  /* If our nearest ancestor is the very path we inquired about, we
4359     can return the mergeinfo results directly.  Otherwise, we're
4360     inheriting the mergeinfo, so we need to a) remove non-inheritable
4361     ranges and b) telescope the merged-from paths. */
4362  if (adjust_inherited_mergeinfo && (nearest_ancestor != parent_path))
4363    {
4364      svn_mergeinfo_t tmp_mergeinfo;
4365
4366      SVN_ERR(svn_mergeinfo_inheritable2(&tmp_mergeinfo, *mergeinfo,
4367                                         NULL, SVN_INVALID_REVNUM,
4368                                         SVN_INVALID_REVNUM, TRUE,
4369                                         scratch_pool, scratch_pool));
4370      SVN_ERR(svn_fs__append_to_merged_froms(mergeinfo, tmp_mergeinfo,
4371                                             parent_path_relpath(
4372                                               parent_path, nearest_ancestor,
4373                                               scratch_pool),
4374                                             result_pool));
4375    }
4376
4377  return SVN_NO_ERROR;
4378}
4379
4380/* Caching wrapper around get_mergeinfo_for_path_internal().
4381 */
4382static svn_error_t *
4383get_mergeinfo_for_path(svn_mergeinfo_t *mergeinfo,
4384                       svn_fs_root_t *rev_root,
4385                       const char *path,
4386                       svn_mergeinfo_inheritance_t inherit,
4387                       svn_boolean_t adjust_inherited_mergeinfo,
4388                       apr_pool_t *result_pool,
4389                       apr_pool_t *scratch_pool)
4390{
4391  fs_fs_data_t *ffd = rev_root->fs->fsap_data;
4392  const char *cache_key;
4393  svn_boolean_t found = FALSE;
4394  svn_stringbuf_t *mergeinfo_exists;
4395
4396  *mergeinfo = NULL;
4397
4398  cache_key = mergeinfo_cache_key(path, rev_root, inherit,
4399                                  adjust_inherited_mergeinfo, scratch_pool);
4400  if (ffd->mergeinfo_existence_cache)
4401    {
4402      SVN_ERR(svn_cache__get((void **)&mergeinfo_exists, &found,
4403                             ffd->mergeinfo_existence_cache,
4404                             cache_key, result_pool));
4405      if (found && mergeinfo_exists->data[0] == '1')
4406        SVN_ERR(svn_cache__get((void **)mergeinfo, &found,
4407                              ffd->mergeinfo_cache,
4408                              cache_key, result_pool));
4409    }
4410
4411  if (! found)
4412    {
4413      SVN_ERR(get_mergeinfo_for_path_internal(mergeinfo, rev_root, path,
4414                                              inherit,
4415                                              adjust_inherited_mergeinfo,
4416                                              result_pool, scratch_pool));
4417      if (ffd->mergeinfo_existence_cache)
4418        {
4419          mergeinfo_exists = svn_stringbuf_create(*mergeinfo ? "1" : "0",
4420                                                  scratch_pool);
4421          SVN_ERR(svn_cache__set(ffd->mergeinfo_existence_cache,
4422                                 cache_key, mergeinfo_exists, scratch_pool));
4423          if (*mergeinfo)
4424            SVN_ERR(svn_cache__set(ffd->mergeinfo_cache,
4425                                  cache_key, *mergeinfo, scratch_pool));
4426        }
4427    }
4428
4429  return SVN_NO_ERROR;
4430}
4431
4432/* Invoke RECEIVER with BATON for each mergeinfo found on descendants of
4433   PATH (but not PATH itself).  Use SCRATCH_POOL for temporary values. */
4434static svn_error_t *
4435add_descendant_mergeinfo(svn_fs_root_t *root,
4436                         const char *path,
4437                         svn_fs_mergeinfo_receiver_t receiver,
4438                         void *baton,
4439                         apr_pool_t *scratch_pool)
4440{
4441  dag_node_t *this_dag;
4442  svn_boolean_t go_down;
4443
4444  SVN_ERR(get_dag(&this_dag, root, path, scratch_pool));
4445  SVN_ERR(svn_fs_fs__dag_has_descendants_with_mergeinfo(&go_down,
4446                                                        this_dag));
4447  if (go_down)
4448    SVN_ERR(crawl_directory_dag_for_mergeinfo(root,
4449                                              path,
4450                                              this_dag,
4451                                              receiver,
4452                                              baton,
4453                                              scratch_pool));
4454  return SVN_NO_ERROR;
4455}
4456
4457
4458/* Find all the mergeinfo for a set of PATHS under ROOT and report it
4459   through RECEIVER with BATON.  INHERITED, INCLUDE_DESCENDANTS and
4460   ADJUST_INHERITED_MERGEINFO are the same as in the FS API.
4461
4462   Allocate temporary values are allocated in SCRATCH_POOL. */
4463static svn_error_t *
4464get_mergeinfos_for_paths(svn_fs_root_t *root,
4465                         const apr_array_header_t *paths,
4466                         svn_mergeinfo_inheritance_t inherit,
4467                         svn_boolean_t include_descendants,
4468                         svn_boolean_t adjust_inherited_mergeinfo,
4469                         svn_fs_mergeinfo_receiver_t receiver,
4470                         void *baton,
4471                         apr_pool_t *scratch_pool)
4472{
4473  apr_pool_t *iterpool = svn_pool_create(scratch_pool);
4474  int i;
4475
4476  for (i = 0; i < paths->nelts; i++)
4477    {
4478      svn_error_t *err;
4479      svn_mergeinfo_t path_mergeinfo;
4480      const char *path = APR_ARRAY_IDX(paths, i, const char *);
4481
4482      svn_pool_clear(iterpool);
4483
4484      err = get_mergeinfo_for_path(&path_mergeinfo, root, path,
4485                                   inherit, adjust_inherited_mergeinfo,
4486                                   iterpool, iterpool);
4487      if (err)
4488        {
4489          if (err->apr_err == SVN_ERR_MERGEINFO_PARSE_ERROR)
4490            {
4491              svn_error_clear(err);
4492              err = NULL;
4493              path_mergeinfo = NULL;
4494            }
4495          else
4496            {
4497              return svn_error_trace(err);
4498            }
4499        }
4500
4501      if (path_mergeinfo)
4502        SVN_ERR(receiver(path, path_mergeinfo, baton, iterpool));
4503      if (include_descendants)
4504        SVN_ERR(add_descendant_mergeinfo(root, path, receiver, baton,
4505                                         iterpool));
4506    }
4507  svn_pool_destroy(iterpool);
4508
4509  return SVN_NO_ERROR;
4510}
4511
4512
4513/* Implements svn_fs_get_mergeinfo. */
4514static svn_error_t *
4515fs_get_mergeinfo(svn_fs_root_t *root,
4516                 const apr_array_header_t *paths,
4517                 svn_mergeinfo_inheritance_t inherit,
4518                 svn_boolean_t include_descendants,
4519                 svn_boolean_t adjust_inherited_mergeinfo,
4520                 svn_fs_mergeinfo_receiver_t receiver,
4521                 void *baton,
4522                 apr_pool_t *scratch_pool)
4523{
4524  fs_fs_data_t *ffd = root->fs->fsap_data;
4525
4526  /* We require a revision root. */
4527  if (root->is_txn_root)
4528    return svn_error_create(SVN_ERR_FS_NOT_REVISION_ROOT, NULL, NULL);
4529
4530  /* We have to actually be able to find the mergeinfo metadata! */
4531  if (! svn_fs_fs__fs_supports_mergeinfo(root->fs))
4532    return svn_error_createf
4533      (SVN_ERR_UNSUPPORTED_FEATURE, NULL,
4534       _("Querying mergeinfo requires version %d of the FSFS filesystem "
4535         "schema; filesystem '%s' uses only version %d"),
4536       SVN_FS_FS__MIN_MERGEINFO_FORMAT, root->fs->path, ffd->format);
4537
4538  /* Retrieve a path -> mergeinfo hash mapping. */
4539  return get_mergeinfos_for_paths(root, paths, inherit,
4540                                  include_descendants,
4541                                  adjust_inherited_mergeinfo,
4542                                  receiver, baton,
4543                                  scratch_pool);
4544}
4545
4546
4547/* The vtable associated with root objects. */
4548static root_vtable_t root_vtable = {
4549  fs_paths_changed,
4550  fs_report_changes,
4551  svn_fs_fs__check_path,
4552  fs_node_history,
4553  svn_fs_fs__node_id,
4554  fs_node_relation,
4555  svn_fs_fs__node_created_rev,
4556  fs_node_origin_rev,
4557  fs_node_created_path,
4558  fs_delete_node,
4559  fs_copy,
4560  fs_revision_link,
4561  fs_copied_from,
4562  fs_closest_copy,
4563  fs_node_prop,
4564  fs_node_proplist,
4565  fs_node_has_props,
4566  fs_change_node_prop,
4567  fs_props_changed,
4568  fs_dir_entries,
4569  fs_dir_optimal_order,
4570  fs_make_dir,
4571  fs_file_length,
4572  fs_file_checksum,
4573  fs_file_contents,
4574  fs_try_process_file_contents,
4575  fs_make_file,
4576  fs_apply_textdelta,
4577  fs_apply_text,
4578  fs_contents_changed,
4579  fs_get_file_delta_stream,
4580  fs_merge,
4581  fs_get_mergeinfo,
4582};
4583
4584/* Construct a new root object in FS, allocated from POOL.  */
4585static svn_fs_root_t *
4586make_root(svn_fs_t *fs,
4587          apr_pool_t *pool)
4588{
4589  svn_fs_root_t *root = apr_pcalloc(pool, sizeof(*root));
4590
4591  root->fs = fs;
4592  root->pool = pool;
4593  root->vtable = &root_vtable;
4594
4595  return root;
4596}
4597
4598
4599/* Construct a root object referring to the root of REVISION in FS,
4600   whose root directory is ROOT_DIR.  Create the new root in POOL.  */
4601static svn_fs_root_t *
4602make_revision_root(svn_fs_t *fs,
4603                   svn_revnum_t rev,
4604                   dag_node_t *root_dir,
4605                   apr_pool_t *pool)
4606{
4607  svn_fs_root_t *root = make_root(fs, pool);
4608
4609  root->is_txn_root = FALSE;
4610  root->rev = rev;
4611  root->fsap_data = root_dir;
4612
4613  return root;
4614}
4615
4616
4617/* Construct a root object referring to the root of the transaction
4618   named TXN and based on revision BASE_REV in FS, with FLAGS to
4619   describe transaction's behavior.  Create the new root in POOL.  */
4620static svn_error_t *
4621make_txn_root(svn_fs_root_t **root_p,
4622              svn_fs_t *fs,
4623              const svn_fs_fs__id_part_t *txn,
4624              svn_revnum_t base_rev,
4625              apr_uint32_t flags,
4626              apr_pool_t *pool)
4627{
4628  svn_fs_root_t *root = make_root(fs, pool);
4629  fs_txn_root_data_t *frd = apr_pcalloc(root->pool, sizeof(*frd));
4630  frd->txn_id = *txn;
4631
4632  root->is_txn_root = TRUE;
4633  root->txn = svn_fs_fs__id_txn_unparse(txn, root->pool);
4634  root->txn_flags = flags;
4635  root->rev = base_rev;
4636
4637  /* Because this cache actually tries to invalidate elements, keep
4638     the number of elements per page down.
4639
4640     Note that since dag_node_cache_invalidate uses svn_cache__iter,
4641     this *cannot* be a memcache-based cache.  */
4642  SVN_ERR(svn_cache__create_inprocess(&(frd->txn_node_cache),
4643                                      svn_fs_fs__dag_serialize,
4644                                      svn_fs_fs__dag_deserialize,
4645                                      APR_HASH_KEY_STRING,
4646                                      32, 20, FALSE,
4647                                      apr_pstrcat(pool, root->txn, ":TXN",
4648                                                  SVN_VA_NULL),
4649                                      root->pool));
4650
4651  /* Initialize transaction-local caches in FS.
4652
4653     Note that we cannot put those caches in frd because that content
4654     fs root object is not available where we would need it. */
4655  SVN_ERR(svn_fs_fs__initialize_txn_caches(fs, root->txn, root->pool));
4656
4657  root->fsap_data = frd;
4658
4659  *root_p = root;
4660  return SVN_NO_ERROR;
4661}
4662
4663
4664
4665/* Verify. */
4666static const char *
4667stringify_node(dag_node_t *node,
4668               apr_pool_t *pool)
4669{
4670  /* ### TODO: print some PATH@REV to it, too. */
4671  return svn_fs_fs__id_unparse(svn_fs_fs__dag_get_id(node), pool)->data;
4672}
4673
4674/* Check metadata sanity on NODE, and on its children.  Manually verify
4675   information for DAG nodes in revision REV, and trust the metadata
4676   accuracy for nodes belonging to older revisions.  To detect cycles,
4677   provide all parent dag_node_t * in PARENT_NODES. */
4678static svn_error_t *
4679verify_node(dag_node_t *node,
4680            svn_revnum_t rev,
4681            apr_array_header_t *parent_nodes,
4682            apr_pool_t *pool)
4683{
4684  svn_boolean_t has_mergeinfo;
4685  apr_int64_t mergeinfo_count;
4686  const svn_fs_id_t *pred_id;
4687  svn_fs_t *fs = svn_fs_fs__dag_get_fs(node);
4688  int pred_count;
4689  svn_node_kind_t kind;
4690  apr_pool_t *iterpool = svn_pool_create(pool);
4691  int i;
4692
4693  /* Detect (non-)DAG cycles. */
4694  for (i = 0; i < parent_nodes->nelts; ++i)
4695    {
4696      dag_node_t *parent = APR_ARRAY_IDX(parent_nodes, i, dag_node_t *);
4697      if (svn_fs_fs__id_eq(svn_fs_fs__dag_get_id(parent),
4698                           svn_fs_fs__dag_get_id(node)))
4699        return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4700                                "Node is its own direct or indirect parent '%s'",
4701                                stringify_node(node, iterpool));
4702    }
4703
4704  /* Fetch some data. */
4705  SVN_ERR(svn_fs_fs__dag_has_mergeinfo(&has_mergeinfo, node));
4706  SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&mergeinfo_count, node));
4707  SVN_ERR(svn_fs_fs__dag_get_predecessor_id(&pred_id, node));
4708  SVN_ERR(svn_fs_fs__dag_get_predecessor_count(&pred_count, node));
4709  kind = svn_fs_fs__dag_node_kind(node);
4710
4711  /* Sanity check. */
4712  if (mergeinfo_count < 0)
4713    return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4714                             "Negative mergeinfo-count %" APR_INT64_T_FMT
4715                             " on node '%s'",
4716                             mergeinfo_count, stringify_node(node, iterpool));
4717
4718  /* Issue #4129. (This check will explicitly catch non-root instances too.) */
4719  if (pred_id)
4720    {
4721      dag_node_t *pred;
4722      int pred_pred_count;
4723      SVN_ERR(svn_fs_fs__dag_get_node(&pred, fs, pred_id, iterpool));
4724      SVN_ERR(svn_fs_fs__dag_get_predecessor_count(&pred_pred_count, pred));
4725      if (pred_pred_count+1 != pred_count)
4726        return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4727                                 "Predecessor count mismatch: "
4728                                 "%s has %d, but %s has %d",
4729                                 stringify_node(node, iterpool), pred_count,
4730                                 stringify_node(pred, iterpool),
4731                                 pred_pred_count);
4732    }
4733
4734  /* Kind-dependent verifications. */
4735  if (kind == svn_node_none)
4736    {
4737      return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4738                               "Node '%s' has kind 'none'",
4739                               stringify_node(node, iterpool));
4740    }
4741  if (kind == svn_node_file)
4742    {
4743      if (has_mergeinfo != mergeinfo_count) /* comparing int to bool */
4744        return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4745                                 "File node '%s' has inconsistent mergeinfo: "
4746                                 "has_mergeinfo=%d, "
4747                                 "mergeinfo_count=%" APR_INT64_T_FMT,
4748                                 stringify_node(node, iterpool),
4749                                 has_mergeinfo, mergeinfo_count);
4750    }
4751  if (kind == svn_node_dir)
4752    {
4753      apr_array_header_t *entries;
4754      apr_int64_t children_mergeinfo = 0;
4755      APR_ARRAY_PUSH(parent_nodes, dag_node_t*) = node;
4756
4757      SVN_ERR(svn_fs_fs__dag_dir_entries(&entries, node, pool));
4758
4759      /* Compute CHILDREN_MERGEINFO. */
4760      for (i = 0; i < entries->nelts; ++i)
4761        {
4762          svn_fs_dirent_t *dirent
4763            = APR_ARRAY_IDX(entries, i, svn_fs_dirent_t *);
4764          dag_node_t *child;
4765          apr_int64_t child_mergeinfo;
4766
4767          svn_pool_clear(iterpool);
4768
4769          /* Compute CHILD_REV. */
4770          if (svn_fs_fs__id_rev(dirent->id) == rev)
4771            {
4772              SVN_ERR(svn_fs_fs__dag_get_node(&child, fs, dirent->id,
4773                                              iterpool));
4774              SVN_ERR(verify_node(child, rev, parent_nodes, iterpool));
4775              SVN_ERR(svn_fs_fs__dag_get_mergeinfo_count(&child_mergeinfo,
4776                                                         child));
4777            }
4778          else
4779            {
4780              /* access mergeinfo counter with minimal overhead */
4781              node_revision_t *noderev;
4782              SVN_ERR(svn_fs_fs__get_node_revision(&noderev, fs, dirent->id,
4783                                                   iterpool, iterpool));
4784              child_mergeinfo = noderev->mergeinfo_count;
4785            }
4786
4787          children_mergeinfo += child_mergeinfo;
4788        }
4789
4790      /* Side-effect of issue #4129. */
4791      if (children_mergeinfo+has_mergeinfo != mergeinfo_count)
4792        return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4793                                 "Mergeinfo-count discrepancy on '%s': "
4794                                 "expected %" APR_INT64_T_FMT "+%d, "
4795                                 "counted %" APR_INT64_T_FMT,
4796                                 stringify_node(node, iterpool),
4797                                 mergeinfo_count, has_mergeinfo,
4798                                 children_mergeinfo);
4799
4800      /* If we don't make it here, there was an error / corruption.
4801       * In that case, nobody will need PARENT_NODES anymore. */
4802      apr_array_pop(parent_nodes);
4803    }
4804
4805  svn_pool_destroy(iterpool);
4806  return SVN_NO_ERROR;
4807}
4808
4809svn_error_t *
4810svn_fs_fs__verify_root(svn_fs_root_t *root,
4811                       apr_pool_t *pool)
4812{
4813  svn_fs_t *fs = root->fs;
4814  dag_node_t *root_dir;
4815  apr_array_header_t *parent_nodes;
4816
4817  /* Issue #4129: bogus pred-counts and minfo-cnt's on the root node-rev
4818     (and elsewhere).  This code makes more thorough checks than the
4819     commit-time checks in validate_root_noderev(). */
4820
4821  /* Callers should disable caches by setting SVN_FS_CONFIG_FSFS_CACHE_NS;
4822     see r1462436.
4823
4824     When this code is called in the library, we want to ensure we
4825     use the on-disk data --- rather than some data that was read
4826     in the possibly-distance past and cached since. */
4827
4828  if (root->is_txn_root)
4829    {
4830      fs_txn_root_data_t *frd = root->fsap_data;
4831      SVN_ERR(svn_fs_fs__dag_txn_root(&root_dir, fs, &frd->txn_id, pool));
4832    }
4833  else
4834    {
4835      root_dir = root->fsap_data;
4836    }
4837
4838  /* Recursively verify ROOT_DIR. */
4839  parent_nodes = apr_array_make(pool, 16, sizeof(dag_node_t *));
4840  SVN_ERR(verify_node(root_dir, root->rev, parent_nodes, pool));
4841
4842  /* Verify explicitly the predecessor of the root. */
4843  {
4844    const svn_fs_id_t *pred_id;
4845
4846    /* Only r0 should have no predecessor. */
4847    SVN_ERR(svn_fs_fs__dag_get_predecessor_id(&pred_id, root_dir));
4848    if (! root->is_txn_root && !!pred_id != !!root->rev)
4849      return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4850                               "r%ld's root node's predecessor is "
4851                               "unexpectedly '%s'",
4852                               root->rev,
4853                               (pred_id
4854                                ? svn_fs_fs__id_unparse(pred_id, pool)->data
4855                                : "(null)"));
4856    if (root->is_txn_root && !pred_id)
4857      return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4858                               "Transaction '%s''s root node's predecessor is "
4859                               "unexpectedly NULL",
4860                               root->txn);
4861
4862    /* Check the predecessor's revision. */
4863    if (pred_id)
4864      {
4865        svn_revnum_t pred_rev = svn_fs_fs__id_rev(pred_id);
4866        if (! root->is_txn_root && pred_rev+1 != root->rev)
4867          /* Issue #4129. */
4868          return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4869                                   "r%ld's root node's predecessor is r%ld"
4870                                   " but should be r%ld",
4871                                   root->rev, pred_rev, root->rev - 1);
4872        if (root->is_txn_root && pred_rev != root->rev)
4873          return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
4874                                   "Transaction '%s''s root node's predecessor"
4875                                   " is r%ld"
4876                                   " but should be r%ld",
4877                                   root->txn, pred_rev, root->rev);
4878      }
4879  }
4880
4881  return SVN_NO_ERROR;
4882}
4883