contrib/subversion/subversion/libsvn_delta/branch.c

   1 /*
   2  * branch.c : Element-Based Branching and Move Tracking.
   3  *
   4  * ====================================================================
   5  *    Licensed to the Apache Software Foundation (ASF) under one
   6  *    or more contributor license agreements.  See the NOTICE file
   7  *    distributed with this work for additional information
   8  *    regarding copyright ownership.  The ASF licenses this file
   9  *    to you under the Apache License, Version 2.0 (the
  10  *    "License"); you may not use this file except in compliance
  11  *    with the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  *    Unless required by applicable law or agreed to in writing,
  16  *    software distributed under the License is distributed on an
  17  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  18  *    KIND, either express or implied.  See the License for the
  19  *    specific language governing permissions and limitations
  20  *    under the License.
  21  * ====================================================================
  22  */
  23
  24 #include <assert.h>
  25
  26 #include "svn_types.h"
  27 #include "svn_error.h"
  28 #include "svn_dirent_uri.h"
  29 #include "svn_hash.h"
  30 #include "svn_iter.h"
  31 #include "svn_pools.h"
  32
  33 #include "private/svn_element.h"
  34 #include "private/svn_branch.h"
  35 #include "private/svn_branch_impl.h"
  36 #include "private/svn_sorts_private.h"
  37
  38 #include "svn_private_config.h"
  39
  40
  41 /* Is EID allocated (no matter whether an element with this id exists)? */
  42 #define EID_IS_ALLOCATED(branch, eid) \
  43   ((eid) >= (branch)->txn->priv->first_eid \
  44    && (eid) < (branch)->txn->priv->next_eid)
  45
  46 #define IS_BRANCH_ROOT_EID(branch, eid) \
  47   ((eid) == (branch)->priv->element_tree->root_eid)
  48
  49 /* Is BRANCH1 the same branch as BRANCH2? Compare by full branch-ids; don't
  50    require identical branch objects. */
  51 #define BRANCH_IS_SAME_BRANCH(branch1, branch2, scratch_pool) \
  52   (strcmp(svn_branch__get_id(branch1, scratch_pool), \
  53           svn_branch__get_id(branch2, scratch_pool)) == 0)
  54
  55 struct svn_branch__txn_priv_t
  56 {
  57   /* All branches. */
  58   apr_array_header_t *branches;
  59
  60   /* The range of element ids assigned. */
  61   /* EIDs local to the txn are negative, assigned by decrementing FIRST_EID
  62    * (skipping -1). */
  63   int first_eid, next_eid;
  64
  65 };
  66
  67 struct svn_branch__state_priv_t
  68 {
  69   /* EID -> svn_element__content_t mapping. */
  70   svn_element__tree_t *element_tree;
  71
  72   /* Merge history for this branch state. */
  73   svn_branch__history_t *history;
  74
  75   svn_boolean_t is_flat;
  76
  77 };
  78
  79 static svn_branch__state_t *
  80 branch_state_create(const char *bid,
  81                     int root_eid,
  82                     svn_branch__txn_t *txn,
  83                     apr_pool_t *result_pool);
  84
  85 static svn_error_t *
  86 branch_instantiate_elements(svn_branch__state_t *to_branch,
  87                             const svn_element__tree_t *elements,
  88                             apr_pool_t *scratch_pool);
  89
  90 static svn_error_t *
  91 svn_branch__map_add_subtree(svn_branch__state_t *to_branch,
  92                             int to_eid,
  93                             svn_branch__eid_t new_parent_eid,
  94                             const char *new_name,
  95                             svn_element__tree_t *new_subtree,
  96                             apr_pool_t *scratch_pool);
  97
  98 /*  */
  99 static apr_pool_t *
 100 branch_state_pool_get(svn_branch__state_t *branch)
 101 {
 102   return apr_hash_pool_get(branch->priv->element_tree->e_map);
 103 }
 104
 105 /* ### Layering: we didn't want to look at the whole repos in here, but
 106    copying seems to require it. */
 107 svn_error_t *
 108 svn_branch__repos_get_branch_by_id(svn_branch__state_t **branch_p,
 109                                   const svn_branch__repos_t *repos,
 110                                   svn_revnum_t revnum,
 111                                   const char *branch_id,
 112                                   apr_pool_t *scratch_pool);
 113
 114 /*  */
 115 static svn_error_t *
 116 branch_in_rev_or_txn(svn_branch__state_t **src_branch,
 117                      const svn_branch__rev_bid_eid_t *src_el_rev,
 118                      svn_branch__txn_t *txn,
 119                      apr_pool_t *result_pool)
 120 {
 121   if (SVN_IS_VALID_REVNUM(src_el_rev->rev))
 122     {
 123       SVN_ERR(svn_branch__repos_get_branch_by_id(src_branch,
 124                                                  txn->repos,
 125                                                  src_el_rev->rev,
 126                                                  src_el_rev->bid,
 127                                                  result_pool));
 128     }
 129   else
 130     {
 131       *src_branch
 132         = svn_branch__txn_get_branch_by_id(txn, src_el_rev->bid, result_pool);
 133     }
 134
 135   return SVN_NO_ERROR;
 136 }
 137
 138 /* An #svn_branch__txn_t method. */
 139 static apr_array_header_t *
 140 branch_txn_get_branches(const svn_branch__txn_t *txn,
 141                         apr_pool_t *result_pool)
 142 {
 143   return apr_array_copy(result_pool, txn->priv->branches);
 144 }
 145
 146 /* An #svn_branch__txn_t method. */
 147 static svn_error_t *
 148 branch_txn_delete_branch(svn_branch__txn_t *txn,
 149                          const char *bid,
 150                          apr_pool_t *scratch_pool)
 151 {
 152   int i;
 153
 154   for (i = 0; i < txn->priv->branches->nelts; i++)
 155     {
 156       svn_branch__state_t *b = APR_ARRAY_IDX(txn->priv->branches, i, void *);
 157
 158       if (strcmp(b->bid, bid) == 0)
 159         {
 160           svn_sort__array_delete(txn->priv->branches, i, 1);
 161           break;
 162         }
 163     }
 164   return SVN_NO_ERROR;
 165 }
 166
 167 /* An #svn_branch__txn_t method. */
 168 static svn_error_t *
 169 branch_txn_get_num_new_eids(const svn_branch__txn_t *txn,
 170                             int *num_new_eids_p,
 171                             apr_pool_t *scratch_pool)
 172 {
 173   if (num_new_eids_p)
 174     *num_new_eids_p = -1 - txn->priv->first_eid;
 175   return SVN_NO_ERROR;
 176 }
 177
 178 /* An #svn_branch__txn_t method. */
 179 static svn_error_t *
 180 branch_txn_new_eid(svn_branch__txn_t *txn,
 181                    svn_branch__eid_t *eid_p,
 182                    apr_pool_t *scratch_pool)
 183 {
 184   int eid = (txn->priv->first_eid < 0) ? txn->priv->first_eid - 1 : -2;
 185
 186   txn->priv->first_eid = eid;
 187   if (eid_p)
 188     *eid_p = eid;
 189   return SVN_NO_ERROR;
 190 }
 191
 192 /* An #svn_branch__txn_t method. */
 193 static svn_error_t *
 194 branch_txn_open_branch(svn_branch__txn_t *txn,
 195                        svn_branch__state_t **new_branch_p,
 196                        const char *branch_id,
 197                        int root_eid,
 198                        svn_branch__rev_bid_eid_t *tree_ref,
 199                        apr_pool_t *result_pool,
 200                        apr_pool_t *scratch_pool)
 201 {
 202   svn_branch__state_t *new_branch;
 203
 204   /* if the branch already exists, just return it, else create it */
 205   new_branch
 206     = svn_branch__txn_get_branch_by_id(txn, branch_id, scratch_pool);
 207   if (new_branch)
 208     {
 209       SVN_ERR_ASSERT(root_eid == svn_branch__root_eid(new_branch));
 210     }
 211   else
 212     {
 213       SVN_ERR_ASSERT_NO_RETURN(root_eid != -1);
 214
 215       new_branch = branch_state_create(branch_id, root_eid, txn,
 216                                        txn->priv->branches->pool);
 217       APR_ARRAY_PUSH(txn->priv->branches, void *) = new_branch;
 218     }
 219
 220   if (tree_ref)
 221     {
 222       svn_branch__state_t *from_branch;
 223       svn_element__tree_t *tree;
 224
 225       SVN_ERR(branch_in_rev_or_txn(&from_branch, tree_ref, txn, scratch_pool));
 226       /* Source branch must exist */
 227       if (! from_branch)
 228         {
 229           return svn_error_createf(SVN_BRANCH__ERR, NULL,
 230                                    _("Cannot branch from r%ld %s e%d: "
 231                                      "branch does not exist"),
 232                                    tree_ref->rev, tree_ref->bid, tree_ref->eid);
 233         }
 234
 235       SVN_ERR_ASSERT(from_branch->priv->is_flat);
 236
 237       SVN_ERR(svn_branch__state_get_elements(from_branch, &tree,
 238                                              scratch_pool));
 239       tree = svn_element__tree_get_subtree_at_eid(tree, tree_ref->eid,
 240                                                   scratch_pool);
 241       /* Source element must exist */
 242       if (! tree)
 243         {
 244           return svn_error_createf(SVN_BRANCH__ERR, NULL,
 245                                    _("Cannot branch from r%ld %s e%d: "
 246                                      "element does not exist"),
 247                                    tree_ref->rev, tree_ref->bid, tree_ref->eid);
 248         }
 249
 250       /* Populate the tree from the 'from' source */
 251       SVN_ERR(branch_instantiate_elements(new_branch, tree, scratch_pool));
 252     }
 253
 254   if (new_branch_p)
 255     *new_branch_p = new_branch;
 256   return SVN_NO_ERROR;
 257 }
 258
 259 /* An #svn_branch__txn_t method. */
 260 static svn_error_t *
 261 branch_txn_sequence_point(svn_branch__txn_t *txn,
 262                           apr_pool_t *scratch_pool)
 263 {
 264   int i;
 265
 266   /* purge elements in each branch */
 267   for (i = 0; i < txn->priv->branches->nelts; i++)
 268     {
 269       svn_branch__state_t *b
 270         = APR_ARRAY_IDX(txn->priv->branches, i, void *);
 271
 272       SVN_ERR(svn_branch__state_purge(b, scratch_pool));
 273     }
 274
 275   return SVN_NO_ERROR;
 276 }
 277
 278 /* An #svn_branch__txn_t method. */
 279 static svn_error_t *
 280 branch_txn_complete(svn_branch__txn_t *txn,
 281                     apr_pool_t *scratch_pool)
 282 {
 283   return SVN_NO_ERROR;
 284 }
 285
 286 /* An #svn_branch__txn_t method. */
 287 static svn_error_t *
 288 branch_txn_abort(svn_branch__txn_t *txn,
 289                  apr_pool_t *scratch_pool)
 290 {
 291   return SVN_NO_ERROR;
 292 }
 293
 294 /*
 295  * ========================================================================
 296  * Branch Txn Object
 297  * ========================================================================
 298  */
 299
 300 apr_array_header_t *
 301 svn_branch__txn_get_branches(const svn_branch__txn_t *txn,
 302                              apr_pool_t *result_pool)
 303 {
 304   apr_array_header_t *branches
 305     = txn->vtable->get_branches(txn,
 306                                 result_pool);
 307   return branches;
 308 }
 309
 310 svn_error_t *
 311 svn_branch__txn_delete_branch(svn_branch__txn_t *txn,
 312                               const char *bid,
 313                               apr_pool_t *scratch_pool)
 314 {
 315   SVN_ERR(txn->vtable->delete_branch(txn,
 316                                     bid,
 317                                     scratch_pool));
 318   return SVN_NO_ERROR;
 319 }
 320
 321 svn_error_t *
 322 svn_branch__txn_get_num_new_eids(const svn_branch__txn_t *txn,
 323                                  int *num_new_eids_p,
 324                                  apr_pool_t *scratch_pool)
 325 {
 326   SVN_ERR(txn->vtable->get_num_new_eids(txn,
 327                                         num_new_eids_p,
 328                                         scratch_pool));
 329   return SVN_NO_ERROR;
 330 }
 331
 332 svn_error_t *
 333 svn_branch__txn_new_eid(svn_branch__txn_t *txn,
 334                         int *new_eid_p,
 335                         apr_pool_t *scratch_pool)
 336 {
 337   SVN_ERR(txn->vtable->new_eid(txn,
 338                                new_eid_p,
 339                                scratch_pool));
 340   return SVN_NO_ERROR;
 341 }
 342
 343 svn_error_t *
 344 svn_branch__txn_open_branch(svn_branch__txn_t *txn,
 345                             svn_branch__state_t **new_branch_p,
 346                             const char *branch_id,
 347                             int root_eid,
 348                             svn_branch__rev_bid_eid_t *tree_ref,
 349                             apr_pool_t *result_pool,
 350                             apr_pool_t *scratch_pool)
 351 {
 352   SVN_ERR(txn->vtable->open_branch(txn,
 353                                    new_branch_p,
 354                                    branch_id,
 355                                    root_eid, tree_ref, result_pool,
 356                                    scratch_pool));
 357   return SVN_NO_ERROR;
 358 }
 359
 360 svn_error_t *
 361 svn_branch__txn_finalize_eids(svn_branch__txn_t *txn,
 362                               apr_pool_t *scratch_pool)
 363 {
 364   SVN_ERR(txn->vtable->finalize_eids(txn,
 365                                      scratch_pool));
 366   return SVN_NO_ERROR;
 367 }
 368
 369 svn_error_t *
 370 svn_branch__txn_serialize(svn_branch__txn_t *txn,
 371                           svn_stream_t *stream,
 372                           apr_pool_t *scratch_pool)
 373 {
 374   SVN_ERR(txn->vtable->serialize(txn,
 375                                  stream,
 376                                  scratch_pool));
 377   return SVN_NO_ERROR;
 378 }
 379
 380 svn_error_t *
 381 svn_branch__txn_sequence_point(svn_branch__txn_t *txn,
 382                                apr_pool_t *scratch_pool)
 383 {
 384   SVN_ERR(txn->vtable->sequence_point(txn,
 385                                       scratch_pool));
 386   return SVN_NO_ERROR;
 387 }
 388
 389 svn_error_t *
 390 svn_branch__txn_complete(svn_branch__txn_t *txn,
 391                          apr_pool_t *scratch_pool)
 392 {
 393   SVN_ERR(txn->vtable->complete(txn,
 394                                 scratch_pool));
 395   return SVN_NO_ERROR;
 396 }
 397
 398 svn_error_t *
 399 svn_branch__txn_abort(svn_branch__txn_t *txn,
 400                       apr_pool_t *scratch_pool)
 401 {
 402   SVN_ERR(txn->vtable->abort(txn,
 403                              scratch_pool));
 404   return SVN_NO_ERROR;
 405 }
 406
 407 svn_branch__txn_t *
 408 svn_branch__txn_create(const svn_branch__txn_vtable_t *vtable,
 409                        svn_cancel_func_t cancel_func,
 410                        void *cancel_baton,
 411                        apr_pool_t *result_pool)
 412 {
 413   svn_branch__txn_t *txn = apr_pcalloc(result_pool, sizeof(*txn));
 414
 415   txn->vtable = apr_pmemdup(result_pool, vtable, sizeof(*vtable));
 416
 417   txn->vtable->vpriv.cancel_func = cancel_func;
 418   txn->vtable->vpriv.cancel_baton = cancel_baton;
 419
 420 #ifdef ENABLE_ORDERING_CHECK
 421   txn->vtable->vpriv.within_callback = FALSE;
 422   txn->vtable->vpriv.finished = FALSE;
 423   txn->vtable->vpriv.state_pool = result_pool;
 424 #endif
 425
 426   return txn;
 427 }
 428
 429 /*
 430  * ========================================================================
 431  */
 432
 433 /*  */
 434 static const char *
 435 branch_finalize_bid(const char *bid,
 436                     int mapping_offset,
 437                     apr_pool_t *result_pool)
 438 {
 439   const char *outer_bid;
 440   int outer_eid;
 441
 442   svn_branch__id_unnest(&outer_bid, &outer_eid, bid, result_pool);
 443
 444   if (outer_bid)
 445     {
 446       outer_bid = branch_finalize_bid(outer_bid, mapping_offset, result_pool);
 447     }
 448
 449   if (outer_eid < -1)
 450     {
 451       outer_eid = mapping_offset - outer_eid;
 452     }
 453
 454   return svn_branch__id_nest(outer_bid, outer_eid, result_pool);
 455 }
 456
 457 /* Change txn-local EIDs (negative integers) in BRANCH to revision EIDs, by
 458  * assigning a new revision-EID (positive integer) for each one.
 459  */
 460 static svn_error_t *
 461 branch_finalize_eids(svn_branch__state_t *branch,
 462                      int mapping_offset,
 463                      apr_pool_t *scratch_pool)
 464 {
 465   apr_hash_index_t *hi;
 466
 467   branch->bid = branch_finalize_bid(branch->bid, mapping_offset,
 468                                     branch_state_pool_get(branch));
 469   if (branch->priv->element_tree->root_eid < -1)
 470     {
 471       branch->priv->element_tree->root_eid
 472         = mapping_offset - branch->priv->element_tree->root_eid;
 473     }
 474
 475   for (hi = apr_hash_first(scratch_pool, branch->priv->element_tree->e_map);
 476        hi; hi = apr_hash_next(hi))
 477     {
 478       int old_eid = svn_eid__hash_this_key(hi);
 479       svn_element__content_t *element = apr_hash_this_val(hi);
 480
 481       if (old_eid < -1)
 482         {
 483           int new_eid = mapping_offset - old_eid;
 484
 485           svn_element__tree_set(branch->priv->element_tree, old_eid, NULL);
 486           svn_element__tree_set(branch->priv->element_tree, new_eid, element);
 487         }
 488       if (element->parent_eid < -1)
 489         {
 490           element->parent_eid = mapping_offset - element->parent_eid;
 491         }
 492     }
 493   return SVN_NO_ERROR;
 494 }
 495
 496 /* An #svn_branch__txn_t method. */
 497 static svn_error_t *
 498 branch_txn_finalize_eids(svn_branch__txn_t *txn,
 499                          apr_pool_t *scratch_pool)
 500 {
 501   int n_txn_eids = (-1) - txn->priv->first_eid;
 502   int mapping_offset;
 503   apr_array_header_t *branches = branch_txn_get_branches(txn, scratch_pool);
 504   int i;
 505
 506   if (txn->priv->first_eid == 0)
 507     return SVN_NO_ERROR;
 508
 509   /* mapping from txn-local (negative) EID to committed (positive) EID is:
 510        txn_local_eid == -2  =>  committed_eid := (txn.next_eid + 0)
 511        txn_local_eid == -3  =>  committed_eid := (txn.next_eid + 1) ... */
 512   mapping_offset = txn->priv->next_eid - 2;
 513
 514   for (i = 0; i < branches->nelts; i++)
 515     {
 516       svn_branch__state_t *b = APR_ARRAY_IDX(branches, i, void *);
 517
 518       SVN_ERR(branch_finalize_eids(b, mapping_offset, scratch_pool));
 519     }
 520
 521   txn->priv->next_eid += n_txn_eids;
 522   txn->priv->first_eid = 0;
 523   return SVN_NO_ERROR;
 524 }
 525
 526 /*
 527  * ========================================================================
 528  */
 529
 530 static svn_error_t *
 531 branch_txn_serialize(svn_branch__txn_t *txn,
 532                      svn_stream_t *stream,
 533                      apr_pool_t *scratch_pool)
 534 {
 535   apr_array_header_t *branches = branch_txn_get_branches(txn, scratch_pool);
 536   int i;
 537
 538   SVN_ERR(svn_stream_printf(stream, scratch_pool,
 539                             "r%ld: eids %d %d "
 540                             "branches %d\n",
 541                             txn->rev,
 542                             txn->priv->first_eid, txn->priv->next_eid,
 543                             branches->nelts));
 544
 545   for (i = 0; i < branches->nelts; i++)
 546     {
 547       svn_branch__state_t *branch = APR_ARRAY_IDX(branches, i, void *);
 548
 549       SVN_ERR(svn_branch__state_serialize(stream, branch, scratch_pool));
 550     }
 551   return SVN_NO_ERROR;
 552 }
 553
 554 /*
 555  * ========================================================================
 556  */
 557
 558 svn_branch__state_t *
 559 svn_branch__txn_get_branch_by_id(const svn_branch__txn_t *txn,
 560                                  const char *branch_id,
 561                                  apr_pool_t *scratch_pool)
 562 {
 563   apr_array_header_t *branches = svn_branch__txn_get_branches(txn, scratch_pool);
 564   int i;
 565   svn_branch__state_t *branch = NULL;
 566
 567   for (i = 0; i < branches->nelts; i++)
 568     {
 569       svn_branch__state_t *b = APR_ARRAY_IDX(branches, i, void *);
 570
 571       if (strcmp(svn_branch__get_id(b, scratch_pool), branch_id) == 0)
 572         {
 573           branch = b;
 574           break;
 575         }
 576     }
 577   return branch;
 578 }
 579
 580 /*
 581  * ========================================================================
 582  */
 583
 584 /* Create a new branch txn object.
 585  *
 586  * It will have no branches.
 587  */
 588 static svn_branch__txn_t *
 589 branch_txn_create(svn_branch__repos_t *repos,
 590                   svn_revnum_t rev,
 591                   svn_revnum_t base_rev,
 592                   apr_pool_t *result_pool)
 593 {
 594   static const svn_branch__txn_vtable_t vtable = {
 595     {0},
 596     branch_txn_get_branches,
 597     branch_txn_delete_branch,
 598     branch_txn_get_num_new_eids,
 599     branch_txn_new_eid,
 600     branch_txn_open_branch,
 601     branch_txn_finalize_eids,
 602     branch_txn_serialize,
 603     branch_txn_sequence_point,
 604     branch_txn_complete,
 605     branch_txn_abort,
 606   };
 607   svn_branch__txn_t *txn
 608     = svn_branch__txn_create(&vtable, NULL, NULL, result_pool);
 609
 610   txn->priv = apr_pcalloc(result_pool, sizeof(*txn->priv));
 611   txn->repos = repos;
 612   txn->rev = rev;
 613   txn->base_rev = base_rev;
 614   txn->priv->branches = apr_array_make(result_pool, 0, sizeof(void *));
 615   return txn;
 616 }
 617
 618 /*
 619  * ========================================================================
 620  */
 621
 622 static void
 623 branch_validate_element(const svn_branch__state_t *branch,
 624                         int eid,
 625                         const svn_element__content_t *element);
 626
 627 /* Assert BRANCH satisfies all its invariants.
 628  */
 629 static void
 630 assert_branch_state_invariants(const svn_branch__state_t *branch,
 631                                apr_pool_t *scratch_pool)
 632 {
 633   apr_hash_index_t *hi;
 634
 635   assert(branch->bid);
 636   assert(branch->txn);
 637   assert(branch->priv->element_tree);
 638   assert(branch->priv->element_tree->e_map);
 639
 640   /* Validate elements in the map */
 641   for (hi = apr_hash_first(scratch_pool, branch->priv->element_tree->e_map);
 642        hi; hi = apr_hash_next(hi))
 643     {
 644       branch_validate_element(branch, svn_eid__hash_this_key(hi),
 645                               apr_hash_this_val(hi));
 646     }
 647 }
 648
 649 /* An #svn_branch__state_t method. */
 650 static svn_error_t *
 651 branch_state_copy_one(svn_branch__state_t *branch,
 652                       const svn_branch__rev_bid_eid_t *src_el_rev,
 653                       svn_branch__eid_t eid,
 654                       svn_branch__eid_t new_parent_eid,
 655                       const char *new_name,
 656                       const svn_element__payload_t *new_payload,
 657                       apr_pool_t *scratch_pool)
 658 {
 659   /* New payload shall be the same as the source if NEW_PAYLOAD is null. */
 660   /* ### if (! new_payload)
 661     {
 662       new_payload = branch_map_get(branch, eid)->payload;
 663     }
 664    */
 665
 666   return SVN_NO_ERROR;
 667 }
 668
 669 /* Copy a subtree.
 670  *
 671  * Adjust TO_BRANCH and its subbranches (recursively), to reflect a copy
 672  * of a subtree from FROM_EL_REV to TO_PARENT_EID:TO_NAME.
 673  *
 674  * FROM_EL_REV must be an existing element. (It may be a branch root.)
 675  *
 676  * ### TODO:
 677  * If FROM_EL_REV is the root of a subbranch and/or contains nested
 678  * subbranches, also copy them ...
 679  * ### What shall we do with a subbranch? Make plain copies of its raw
 680  *     elements; make a subbranch by branching the source subbranch?
 681  *
 682  * TO_PARENT_EID must be a directory element in TO_BRANCH, and TO_NAME a
 683  * non-existing path in it.
 684  */
 685 static svn_error_t *
 686 copy_subtree(const svn_branch__el_rev_id_t *from_el_rev,
 687              svn_branch__state_t *to_branch,
 688              svn_branch__eid_t to_parent_eid,
 689              const char *to_name,
 690              apr_pool_t *scratch_pool)
 691 {
 692   svn_element__tree_t *new_subtree;
 693
 694   SVN_ERR_ASSERT(from_el_rev->branch->priv->is_flat);
 695
 696   SVN_ERR(svn_branch__state_get_elements(from_el_rev->branch, &new_subtree,
 697                                          scratch_pool));
 698   new_subtree = svn_element__tree_get_subtree_at_eid(new_subtree,
 699                                                      from_el_rev->eid,
 700                                                      scratch_pool);
 701
 702   /* copy the subtree, assigning new EIDs */
 703   SVN_ERR(svn_branch__map_add_subtree(to_branch, -1 /*to_eid*/,
 704                                       to_parent_eid, to_name,
 705                                       new_subtree,
 706                                       scratch_pool));
 707
 708   return SVN_NO_ERROR;
 709 }
 710
 711 /* An #svn_branch__state_t method. */
 712 static svn_error_t *
 713 branch_state_copy_tree(svn_branch__state_t *to_branch,
 714                        const svn_branch__rev_bid_eid_t *src_el_rev,
 715                        svn_branch__eid_t new_parent_eid,
 716                        const char *new_name,
 717                        apr_pool_t *scratch_pool)
 718 {
 719   svn_branch__txn_t *txn = to_branch->txn;
 720   svn_branch__state_t *src_branch;
 721   svn_branch__el_rev_id_t *from_el_rev;
 722
 723   SVN_ERR(branch_in_rev_or_txn(&src_branch, src_el_rev, txn, scratch_pool));
 724   from_el_rev = svn_branch__el_rev_id_create(src_branch, src_el_rev->eid,
 725                                              src_el_rev->rev, scratch_pool);
 726   SVN_ERR(copy_subtree(from_el_rev,
 727                        to_branch, new_parent_eid, new_name,
 728                        scratch_pool));
 729
 730   return SVN_NO_ERROR;
 731 }
 732
 733 const char *
 734 svn_branch__get_id(const svn_branch__state_t *branch,
 735                    apr_pool_t *result_pool)
 736 {
 737   return branch->bid;
 738 }
 739
 740 int
 741 svn_branch__root_eid(const svn_branch__state_t *branch)
 742 {
 743   svn_element__tree_t *elements;
 744
 745   svn_error_clear(svn_branch__state_get_elements(branch, &elements,
 746                                                  NULL/*scratch_pool*/));
 747   return elements->root_eid;
 748 }
 749
 750 svn_branch__el_rev_id_t *
 751 svn_branch__el_rev_id_create(svn_branch__state_t *branch,
 752                              int eid,
 753                              svn_revnum_t rev,
 754                              apr_pool_t *result_pool)
 755 {
 756   svn_branch__el_rev_id_t *id = apr_palloc(result_pool, sizeof(*id));
 757
 758   id->branch = branch;
 759   id->eid = eid;
 760   id->rev = rev;
 761   return id;
 762 }
 763
 764 svn_branch__el_rev_id_t *
 765 svn_branch__el_rev_id_dup(const svn_branch__el_rev_id_t *old_id,
 766                           apr_pool_t *result_pool)
 767 {
 768   if (! old_id)
 769     return NULL;
 770
 771   return svn_branch__el_rev_id_create(old_id->branch,
 772                                       old_id->eid,
 773                                       old_id->rev,
 774                                       result_pool);
 775 }
 776
 777 svn_branch__rev_bid_eid_t *
 778 svn_branch__rev_bid_eid_create(svn_revnum_t rev,
 779                                const char *branch_id,
 780                                int eid,
 781                                apr_pool_t *result_pool)
 782 {
 783   svn_branch__rev_bid_eid_t *id = apr_palloc(result_pool, sizeof(*id));
 784
 785   id->bid = apr_pstrdup(result_pool, branch_id);
 786   id->eid = eid;
 787   id->rev = rev;
 788   return id;
 789 }
 790
 791 svn_branch__rev_bid_eid_t *
 792 svn_branch__rev_bid_eid_dup(const svn_branch__rev_bid_eid_t *old_id,
 793                             apr_pool_t *result_pool)
 794 {
 795   svn_branch__rev_bid_eid_t *id;
 796
 797   if (! old_id)
 798     return NULL;
 799
 800   id = apr_pmemdup(result_pool, old_id, sizeof(*id));
 801   id->bid = apr_pstrdup(result_pool, old_id->bid);
 802   return id;
 803 }
 804
 805 svn_branch__rev_bid_t *
 806 svn_branch__rev_bid_create(svn_revnum_t rev,
 807                            const char *branch_id,
 808                            apr_pool_t *result_pool)
 809 {
 810   svn_branch__rev_bid_t *id = apr_palloc(result_pool, sizeof(*id));
 811
 812   id->bid = apr_pstrdup(result_pool, branch_id);
 813   id->rev = rev;
 814   return id;
 815 }
 816
 817 svn_branch__rev_bid_t *
 818 svn_branch__rev_bid_dup(const svn_branch__rev_bid_t *old_id,
 819                         apr_pool_t *result_pool)
 820 {
 821   svn_branch__rev_bid_t *id;
 822
 823   if (! old_id)
 824     return NULL;
 825
 826   id = apr_pmemdup(result_pool, old_id, sizeof(*id));
 827   id->bid = apr_pstrdup(result_pool, old_id->bid);
 828   return id;
 829 }
 830
 831 svn_boolean_t
 832 svn_branch__rev_bid_equal(const svn_branch__rev_bid_t *id1,
 833                           const svn_branch__rev_bid_t *id2)
 834 {
 835   return (id1->rev == id2->rev
 836           && strcmp(id1->bid, id2->bid) == 0);
 837 }
 838
 839 svn_branch__history_t *
 840 svn_branch__history_create_empty(apr_pool_t *result_pool)
 841 {
 842   svn_branch__history_t *history
 843     = svn_branch__history_create(NULL, result_pool);
 844
 845   return history;
 846 }
 847
 848 svn_branch__history_t *
 849 svn_branch__history_create(apr_hash_t *parents,
 850                            apr_pool_t *result_pool)
 851 {
 852   svn_branch__history_t *history
 853     = apr_pcalloc(result_pool, sizeof(*history));
 854
 855   history->parents = apr_hash_make(result_pool);
 856   if (parents)
 857     {
 858       apr_hash_index_t *hi;
 859
 860       for (hi = apr_hash_first(result_pool, parents);
 861            hi; hi = apr_hash_next(hi))
 862         {
 863           const char *bid = apr_hash_this_key(hi);
 864           svn_branch__rev_bid_t *val = apr_hash_this_val(hi);
 865
 866           svn_hash_sets(history->parents,
 867                         apr_pstrdup(result_pool, bid),
 868                         svn_branch__rev_bid_dup(val, result_pool));
 869         }
 870     }
 871   return history;
 872 }
 873
 874 svn_branch__history_t *
 875 svn_branch__history_dup(const svn_branch__history_t *old,
 876                         apr_pool_t *result_pool)
 877 {
 878   svn_branch__history_t *history = NULL;
 879
 880   if (old)
 881     {
 882       history
 883         = svn_branch__history_create(old->parents, result_pool);
 884     }
 885   return history;
 886 }
 887
 888
 889 /*
 890  * ========================================================================
 891  * Branch mappings
 892  * ========================================================================
 893  */
 894
 895 /* Validate that ELEMENT is suitable for a mapping of BRANCH:EID.
 896  * ELEMENT->payload may be null.
 897  */
 898 static void
 899 branch_validate_element(const svn_branch__state_t *branch,
 900                         int eid,
 901                         const svn_element__content_t *element)
 902 {
 903   SVN_ERR_ASSERT_NO_RETURN(element);
 904
 905   /* Parent EID must be valid and different from this element's EID, or -1
 906      iff this is the branch root element. */
 907   SVN_ERR_ASSERT_NO_RETURN(
 908     IS_BRANCH_ROOT_EID(branch, eid)
 909     ? (element->parent_eid == -1)
 910     : (element->parent_eid != eid
 911        && EID_IS_ALLOCATED(branch, element->parent_eid)));
 912
 913   /* Element name must be given, and empty iff EID is the branch root. */
 914   SVN_ERR_ASSERT_NO_RETURN(
 915     element->name
 916     && IS_BRANCH_ROOT_EID(branch, eid) == (*element->name == '\0'));
 917
 918   SVN_ERR_ASSERT_NO_RETURN(svn_element__payload_invariants(element->payload));
 919   if (element->payload->is_subbranch_root)
 920     {
 921       /* a subbranch root element must not be the branch root element */
 922       SVN_ERR_ASSERT_NO_RETURN(! IS_BRANCH_ROOT_EID(branch, eid));
 923     }
 924 }
 925
 926 static svn_error_t *
 927 branch_state_get_elements(const svn_branch__state_t *branch,
 928                           svn_element__tree_t **element_tree_p,
 929                           apr_pool_t *result_pool)
 930 {
 931   *element_tree_p = branch->priv->element_tree;
 932   return SVN_NO_ERROR;
 933 }
 934
 935 static svn_element__content_t *
 936 branch_get_element(const svn_branch__state_t *branch,
 937                    int eid)
 938 {
 939   svn_element__content_t *element;
 940
 941   element = svn_element__tree_get(branch->priv->element_tree, eid);
 942
 943   if (element)
 944     branch_validate_element(branch, eid, element);
 945   return element;
 946 }
 947
 948 static svn_error_t *
 949 branch_state_get_element(const svn_branch__state_t *branch,
 950                          svn_element__content_t **element_p,
 951                          int eid,
 952                          apr_pool_t *result_pool)
 953 {
 954   *element_p = branch_get_element(branch, eid);
 955   return SVN_NO_ERROR;
 956 }
 957
 958 /* In BRANCH, set element EID to ELEMENT.
 959  *
 960  * If ELEMENT is null, delete element EID.
 961  *
 962  * Assume ELEMENT is already allocated with sufficient lifetime.
 963  */
 964 static void
 965 branch_map_set(svn_branch__state_t *branch,
 966                int eid,
 967                const svn_element__content_t *element)
 968 {
 969   apr_pool_t *map_pool = apr_hash_pool_get(branch->priv->element_tree->e_map);
 970
 971   SVN_ERR_ASSERT_NO_RETURN(EID_IS_ALLOCATED(branch, eid));
 972   if (element)
 973     branch_validate_element(branch, eid, element);
 974
 975   svn_element__tree_set(branch->priv->element_tree, eid, element);
 976   branch->priv->is_flat = FALSE;
 977   assert_branch_state_invariants(branch, map_pool);
 978 }
 979
 980 /* An #svn_branch__state_t method. */
 981 static svn_error_t *
 982 branch_state_set_element(svn_branch__state_t *branch,
 983                          svn_branch__eid_t eid,
 984                          const svn_element__content_t *element,
 985                          apr_pool_t *scratch_pool)
 986 {
 987   apr_pool_t *map_pool = apr_hash_pool_get(branch->priv->element_tree->e_map);
 988
 989   /* EID must be a valid element id */
 990   SVN_ERR_ASSERT(EID_IS_ALLOCATED(branch, eid));
 991
 992   if (element)
 993     {
 994       element = svn_element__content_dup(element, map_pool);
 995
 996       /* NEW_PAYLOAD must be specified, either in full or by reference */
 997       SVN_ERR_ASSERT(element->payload);
 998
 999       if ((element->parent_eid == -1) != IS_BRANCH_ROOT_EID(branch, eid)
1000           || (*element->name == '\0') != IS_BRANCH_ROOT_EID(branch, eid))
1001         {
1002           return svn_error_createf(SVN_BRANCH__ERR, NULL,
1003                                    _("Cannot set e%d to (parent=e%d, name='%s'): "
1004                                      "branch root is e%d"),
1005                                    eid, element->parent_eid, element->name,
1006                                    branch->priv->element_tree->root_eid);
1007         }
1008     }
1009
1010   /* Insert the new version */
1011   branch_map_set(branch, eid, element);
1012   return SVN_NO_ERROR;
1013 }
1014
1015 /* An #svn_branch__state_t method. */
1016 static svn_error_t *
1017 branch_state_purge(svn_branch__state_t *branch,
1018                    apr_pool_t *scratch_pool)
1019 {
1020   svn_element__tree_purge_orphans(branch->priv->element_tree->e_map,
1021                                   branch->priv->element_tree->root_eid,
1022                                   scratch_pool);
1023   branch->priv->is_flat = TRUE;
1024   return SVN_NO_ERROR;
1025 }
1026
1027 /* An #svn_branch__state_t method. */
1028 static svn_error_t *
1029 branch_state_get_history(svn_branch__state_t *branch,
1030                          svn_branch__history_t **history_p,
1031                          apr_pool_t *result_pool)
1032 {
1033   if (history_p)
1034     {
1035       *history_p
1036         = svn_branch__history_dup(branch->priv->history, result_pool);
1037     }
1038   return SVN_NO_ERROR;
1039 }
1040
1041 /* An #svn_branch__state_t method. */
1042 static svn_error_t *
1043 branch_state_set_history(svn_branch__state_t *branch,
1044                          const svn_branch__history_t *history,
1045                          apr_pool_t *scratch_pool)
1046 {
1047   apr_pool_t *branch_pool = branch_state_pool_get(branch);
1048
1049   branch->priv->history
1050     = svn_branch__history_dup(history, branch_pool);
1051   return SVN_NO_ERROR;
1052 }
1053
1054 const char *
1055 svn_branch__get_path_by_eid(const svn_branch__state_t *branch,
1056                             int eid,
1057                             apr_pool_t *result_pool)
1058 {
1059   svn_element__tree_t *elements;
1060
1061   SVN_ERR_ASSERT_NO_RETURN(EID_IS_ALLOCATED(branch, eid));
1062   /*SVN_ERR_ASSERT_NO_RETURN(branch->priv->is_flat);*/
1063
1064   svn_error_clear(svn_branch__state_get_elements(branch, &elements, result_pool));
1065   return svn_element__tree_get_path_by_eid(elements, eid, result_pool);
1066 }
1067
1068 int
1069 svn_branch__get_eid_by_path(const svn_branch__state_t *branch,
1070                             const char *path,
1071                             apr_pool_t *scratch_pool)
1072 {
1073   svn_element__tree_t *elements;
1074   apr_hash_index_t *hi;
1075
1076   /*SVN_ERR_ASSERT_NO_RETURN(branch->priv->is_flat);*/
1077
1078   /* ### This is a crude, linear search */
1079   svn_error_clear(svn_branch__state_get_elements(branch, &elements, scratch_pool));
1080   for (hi = apr_hash_first(scratch_pool, elements->e_map);
1081        hi; hi = apr_hash_next(hi))
1082     {
1083       int eid = svn_eid__hash_this_key(hi);
1084       const char *this_path = svn_element__tree_get_path_by_eid(elements, eid,
1085                                                                 scratch_pool);
1086
1087       if (! this_path)
1088         {
1089           /* Mapping is not complete; this element is in effect not present. */
1090           continue;
1091         }
1092       if (strcmp(path, this_path) == 0)
1093         {
1094           return eid;
1095         }
1096     }
1097
1098   return -1;
1099 }
1100
1101 /* Create a copy of NEW_SUBTREE in TO_BRANCH.
1102  *
1103  * For each non-root element in NEW_SUBTREE, create a new element with
1104  * a new EID, no matter what EID is used to represent it in NEW_SUBTREE.
1105  *
1106  * For the new subtree root element, if TO_EID is -1, generate a new EID,
1107  * otherwise alter (if it exists) or instantiate the element TO_EID.
1108  *
1109  * Set the new subtree root element's parent to NEW_PARENT_EID and name to
1110  * NEW_NAME.
1111  */
1112 static svn_error_t *
1113 svn_branch__map_add_subtree(svn_branch__state_t *to_branch,
1114                             int to_eid,
1115                             svn_branch__eid_t new_parent_eid,
1116                             const char *new_name,
1117                             svn_element__tree_t *new_subtree,
1118                             apr_pool_t *scratch_pool)
1119 {
1120   apr_hash_index_t *hi;
1121   svn_element__content_t *new_root_content;
1122
1123   /* Get a new EID for the root element, if not given. */
1124   if (to_eid == -1)
1125     {
1126       SVN_ERR(svn_branch__txn_new_eid(to_branch->txn, &to_eid,
1127                                       scratch_pool));
1128     }
1129
1130   /* Create the new subtree root element */
1131   new_root_content = svn_element__tree_get(new_subtree, new_subtree->root_eid);
1132   new_root_content = svn_element__content_create(new_parent_eid, new_name,
1133                                                  new_root_content->payload,
1134                                                  scratch_pool);
1135   SVN_ERR(branch_state_set_element(to_branch, to_eid, new_root_content,
1136                                    scratch_pool));
1137
1138   /* Process its immediate children */
1139   for (hi = apr_hash_first(scratch_pool, new_subtree->e_map);
1140        hi; hi = apr_hash_next(hi))
1141     {
1142       int this_from_eid = svn_eid__hash_this_key(hi);
1143       svn_element__content_t *from_element = apr_hash_this_val(hi);
1144
1145       if (from_element->parent_eid == new_subtree->root_eid)
1146         {
1147           svn_element__tree_t *this_subtree;
1148
1149           /* Recurse. (We don't try to check whether it's a directory node,
1150              as we might not have the node kind in the map.) */
1151           this_subtree
1152             = svn_element__tree_create(new_subtree->e_map, this_from_eid,
1153                                        scratch_pool);
1154           SVN_ERR(svn_branch__map_add_subtree(to_branch, -1 /*to_eid*/,
1155                                               to_eid, from_element->name,
1156                                               this_subtree, scratch_pool));
1157         }
1158     }
1159
1160   return SVN_NO_ERROR;
1161 }
1162
1163 /* Instantiate elements in a branch.
1164  *
1165  * In TO_BRANCH, instantiate (or alter, if existing) each element of
1166  * ELEMENTS, each with its given tree structure (parent, name) and payload.
1167  */
1168 static svn_error_t *
1169 branch_instantiate_elements(svn_branch__state_t *to_branch,
1170                             const svn_element__tree_t *elements,
1171                             apr_pool_t *scratch_pool)
1172 {
1173   apr_hash_index_t *hi;
1174
1175   for (hi = apr_hash_first(scratch_pool, elements->e_map);
1176        hi; hi = apr_hash_next(hi))
1177     {
1178       int this_eid = svn_eid__hash_this_key(hi);
1179       svn_element__content_t *this_element = apr_hash_this_val(hi);
1180
1181       branch_map_set(to_branch, this_eid,
1182                      svn_element__content_dup(
1183                        this_element,
1184                        apr_hash_pool_get(to_branch->priv->element_tree->e_map)));
1185     }
1186
1187   return SVN_NO_ERROR;
1188 }
1189
1190 /*
1191  * ========================================================================
1192  * Branch State Object
1193  * ========================================================================
1194  */
1195
1196 svn_error_t *
1197 svn_branch__state_get_elements(const svn_branch__state_t *branch,
1198                                svn_element__tree_t **element_tree_p,
1199                                apr_pool_t *result_pool)
1200 {
1201   SVN_ERR(branch->vtable->get_elements(branch,
1202                                        element_tree_p,
1203                                        result_pool));
1204   return SVN_NO_ERROR;
1205 }
1206
1207 svn_error_t *
1208 svn_branch__state_get_element(const svn_branch__state_t *branch,
1209                               svn_element__content_t **element_p,
1210                               int eid,
1211                               apr_pool_t *result_pool)
1212 {
1213   SVN_ERR(branch->vtable->get_element(branch,
1214                                       element_p, eid, result_pool));
1215   return SVN_NO_ERROR;
1216 }
1217
1218 svn_error_t *
1219 svn_branch__state_set_element(svn_branch__state_t *branch,
1220                               int eid,
1221                               const svn_element__content_t *element,
1222                               apr_pool_t *scratch_pool)
1223 {
1224   SVN_ERR(branch->vtable->set_element(branch,
1225                                       eid, element,
1226                                       scratch_pool));
1227   return SVN_NO_ERROR;
1228 }
1229
1230 svn_error_t *
1231 svn_branch__state_alter_one(svn_branch__state_t *branch,
1232                             svn_branch__eid_t eid,
1233                             svn_branch__eid_t new_parent_eid,
1234                             const char *new_name,
1235                             const svn_element__payload_t *new_payload,
1236                             apr_pool_t *scratch_pool)
1237 {
1238   svn_element__content_t *element
1239     = svn_element__content_create(new_parent_eid, new_name, new_payload,
1240                                   scratch_pool);
1241
1242   SVN_ERR(svn_branch__state_set_element(branch, eid, element, scratch_pool));
1243   return SVN_NO_ERROR;
1244 }
1245
1246 svn_error_t *
1247 svn_branch__state_copy_tree(svn_branch__state_t *branch,
1248                             const svn_branch__rev_bid_eid_t *src_el_rev,
1249                             svn_branch__eid_t new_parent_eid,
1250                             const char *new_name,
1251                             apr_pool_t *scratch_pool)
1252 {
1253   SVN_ERR(branch->vtable->copy_tree(branch,
1254                                     src_el_rev, new_parent_eid, new_name,
1255                                     scratch_pool));
1256   return SVN_NO_ERROR;
1257 }
1258
1259 svn_error_t *
1260 svn_branch__state_delete_one(svn_branch__state_t *branch,
1261                              svn_branch__eid_t eid,
1262                              apr_pool_t *scratch_pool)
1263 {
1264   SVN_ERR(svn_branch__state_set_element(branch, eid, NULL, scratch_pool));
1265   return SVN_NO_ERROR;
1266 }
1267
1268 svn_error_t *
1269 svn_branch__state_purge(svn_branch__state_t *branch,
1270                         apr_pool_t *scratch_pool)
1271 {
1272   SVN_ERR(branch->vtable->purge(branch,
1273                                 scratch_pool));
1274   return SVN_NO_ERROR;
1275 }
1276
1277 svn_error_t *
1278 svn_branch__state_get_history(svn_branch__state_t *branch,
1279                               svn_branch__history_t **history_p,
1280                               apr_pool_t *result_pool)
1281 {
1282   SVN_ERR(branch->vtable->get_history(branch,
1283                                       history_p,
1284                                       result_pool));
1285   SVN_ERR_ASSERT(*history_p);
1286   return SVN_NO_ERROR;
1287 }
1288
1289 svn_error_t *
1290 svn_branch__state_set_history(svn_branch__state_t *branch,
1291                               const svn_branch__history_t *history,
1292                               apr_pool_t *scratch_pool)
1293 {
1294   SVN_ERR_ASSERT(history);
1295   SVN_ERR(branch->vtable->set_history(branch,
1296                                       history,
1297                                       scratch_pool));
1298   return SVN_NO_ERROR;
1299 }
1300
1301 svn_branch__state_t *
1302 svn_branch__state_create(const svn_branch__state_vtable_t *vtable,
1303                          svn_cancel_func_t cancel_func,
1304                          void *cancel_baton,
1305                          apr_pool_t *result_pool)
1306 {
1307   svn_branch__state_t *b = apr_pcalloc(result_pool, sizeof(*b));
1308
1309   b->vtable = apr_pmemdup(result_pool, vtable, sizeof(*vtable));
1310
1311   b->vtable->vpriv.cancel_func = cancel_func;
1312   b->vtable->vpriv.cancel_baton = cancel_baton;
1313
1314 #ifdef ENABLE_ORDERING_CHECK
1315   b->vtable->vpriv.within_callback = FALSE;
1316   b->vtable->vpriv.finished = FALSE;
1317   b->vtable->vpriv.state_pool = result_pool;
1318 #endif
1319
1320   return b;
1321 }
1322
1323 /* Create a new branch state object.
1324  *
1325  * It will have no elements (not even a root element).
1326  */
1327 static svn_branch__state_t *
1328 branch_state_create(const char *bid,
1329                     int root_eid,
1330                     svn_branch__txn_t *txn,
1331                     apr_pool_t *result_pool)
1332 {
1333   static const svn_branch__state_vtable_t vtable = {
1334     {0},
1335     branch_state_get_elements,
1336     branch_state_get_element,
1337     branch_state_set_element,
1338     branch_state_copy_one,
1339     branch_state_copy_tree,
1340     branch_state_purge,
1341     branch_state_get_history,
1342     branch_state_set_history,
1343   };
1344   svn_branch__state_t *b
1345     = svn_branch__state_create(&vtable, NULL, NULL, result_pool);
1346
1347   b->priv = apr_pcalloc(result_pool, sizeof(*b->priv));
1348   b->bid = apr_pstrdup(result_pool, bid);
1349   b->txn = txn;
1350   b->priv->element_tree = svn_element__tree_create(NULL, root_eid, result_pool);
1351   assert_branch_state_invariants(b, result_pool);
1352   b->priv->is_flat = TRUE;
1353   b->priv->history = svn_branch__history_create_empty(result_pool);
1354   return b;
1355 }
1356
1357 /*
1358  * ========================================================================
1359  * Parsing and Serializing
1360  * ========================================================================
1361  */
1362
1363 svn_string_t *
1364 svn_branch__get_default_r0_metadata(apr_pool_t *result_pool)
1365 {
1366   static const char *default_repos_info
1367     = "r0: eids 0 1 branches 1\n"
1368       "B0 root-eid 0 num-eids 1\n"
1369       "history: parents 0\n"
1370       "e0: normal -1 .\n";
1371
1372   return svn_string_create(default_repos_info, result_pool);
1373 }
1374
1375 /*  */
1376 static svn_error_t *
1377 parse_branch_line(char *bid_p,
1378                   int *root_eid_p,
1379                   int *num_eids_p,
1380                   svn_stream_t *stream,
1381                   apr_pool_t *result_pool,
1382                   apr_pool_t *scratch_pool)
1383 {
1384   svn_stringbuf_t *line;
1385   svn_boolean_t eof;
1386   int n;
1387
1388   /* Read a line */
1389   SVN_ERR(svn_stream_readline(stream, &line, "\n", &eof, scratch_pool));
1390   SVN_ERR_ASSERT(!eof);
1391
1392   n = sscanf(line->data, "%s root-eid %d num-eids %d",
1393              bid_p, root_eid_p, num_eids_p);
1394   SVN_ERR_ASSERT(n == 3);
1395
1396   return SVN_NO_ERROR;
1397 }
1398
1399 /* Parse the history metadata for BRANCH.
1400  */
1401 static svn_error_t *
1402 history_parse(svn_branch__history_t **history_p,
1403               svn_stream_t *stream,
1404               apr_pool_t *result_pool,
1405               apr_pool_t *scratch_pool)
1406 {
1407   svn_branch__history_t *history
1408     = svn_branch__history_create_empty(result_pool);
1409   svn_stringbuf_t *line;
1410   svn_boolean_t eof;
1411   int n;
1412   int num_parents;
1413   int i;
1414
1415   /* Read a line */
1416   SVN_ERR(svn_stream_readline(stream, &line, "\n", &eof, scratch_pool));
1417   SVN_ERR_ASSERT(!eof);
1418
1419   n = sscanf(line->data, "history: parents %d",
1420              &num_parents);
1421   SVN_ERR_ASSERT(n == 1);
1422
1423   for (i = 0; i < num_parents; i++)
1424     {
1425       svn_revnum_t rev;
1426       char bid[100];
1427
1428       SVN_ERR(svn_stream_readline(stream, &line, "\n", &eof, scratch_pool));
1429       SVN_ERR_ASSERT(!eof);
1430
1431       n = sscanf(line->data, "parent: r%ld.%99s",
1432                  &rev, bid);
1433       SVN_ERR_ASSERT(n == 2);
1434
1435       svn_hash_sets(history->parents,
1436                     apr_pstrdup(result_pool, bid),
1437                     svn_branch__rev_bid_create(rev, bid, result_pool));
1438     }
1439
1440   if (history_p)
1441     *history_p = history;
1442   return SVN_NO_ERROR;
1443 }
1444
1445 /* Parse the mapping for one element.
1446  */
1447 static svn_error_t *
1448 parse_element_line(int *eid_p,
1449                    svn_boolean_t *is_subbranch_p,
1450                    int *parent_eid_p,
1451                    const char **name_p,
1452                    svn_stream_t *stream,
1453                    apr_pool_t *result_pool,
1454                    apr_pool_t *scratch_pool)
1455 {
1456   svn_stringbuf_t *line;
1457   svn_boolean_t eof;
1458   char kind[10];
1459   int n;
1460   int offset;
1461
1462   /* Read a line */
1463   SVN_ERR(svn_stream_readline(stream, &line, "\n", &eof, scratch_pool));
1464   SVN_ERR_ASSERT(!eof);
1465
1466   n = sscanf(line->data, "e%d: %9s %d%n",
1467              eid_p,
1468              kind, parent_eid_p, &offset);
1469   SVN_ERR_ASSERT(n >= 3);  /* C std is unclear on whether '%n' counts */
1470   SVN_ERR_ASSERT(line->data[offset] == ' ');
1471
1472   *name_p = apr_pstrdup(result_pool, line->data + offset + 1);
1473   *is_subbranch_p = (strcmp(kind, "subbranch") == 0);
1474
1475   if (strcmp(*name_p, "(null)") == 0)
1476     *name_p = NULL;
1477   else if (strcmp(*name_p, ".") == 0)
1478     *name_p = "";
1479
1480   return SVN_NO_ERROR;
1481 }
1482
1483 const char *
1484 svn_branch__id_nest(const char *outer_bid,
1485                     int outer_eid,
1486                     apr_pool_t *result_pool)
1487 {
1488   if (!outer_bid)
1489     return apr_psprintf(result_pool, "B%d", outer_eid);
1490
1491   return apr_psprintf(result_pool, "%s.%d", outer_bid, outer_eid);
1492 }
1493
1494 void
1495 svn_branch__id_unnest(const char **outer_bid,
1496                       int *outer_eid,
1497                       const char *bid,
1498                       apr_pool_t *result_pool)
1499 {
1500   char *last_dot = strrchr(bid, '.');
1501
1502   if (last_dot) /* BID looks like "B3.11" or "B3.11.22" etc. */
1503     {
1504       *outer_bid = apr_pstrndup(result_pool, bid, last_dot - bid);
1505       *outer_eid = atoi(last_dot + 1);
1506     }
1507   else /* looks like "B0" or B22" (with no dot) */
1508     {
1509       *outer_bid = NULL;
1510       *outer_eid = atoi(bid + 1);
1511     }
1512 }
1513
1514 /* Create a new branch *NEW_BRANCH, initialized
1515  * with info parsed from STREAM, allocated in RESULT_POOL.
1516  */
1517 static svn_error_t *
1518 svn_branch__state_parse(svn_branch__state_t **new_branch,
1519                        svn_branch__txn_t *txn,
1520                        svn_stream_t *stream,
1521                        apr_pool_t *result_pool,
1522                        apr_pool_t *scratch_pool)
1523 {
1524   char bid[1000];
1525   int root_eid, num_eids;
1526   svn_branch__state_t *branch_state;
1527   int i;
1528
1529   SVN_ERR(parse_branch_line(bid, &root_eid, &num_eids,
1530                             stream, scratch_pool, scratch_pool));
1531
1532   branch_state = branch_state_create(bid, root_eid, txn,
1533                                      result_pool);
1534
1535   /* Read in the merge history. */
1536   SVN_ERR(history_parse(&branch_state->priv->history,
1537                         stream, result_pool, scratch_pool));
1538
1539   /* Read in the structure. Set the payload of each normal element to a
1540      (branch-relative) reference. */
1541   for (i = 0; i < num_eids; i++)
1542     {
1543       int eid, this_parent_eid;
1544       const char *this_name;
1545       svn_boolean_t is_subbranch;
1546
1547       SVN_ERR(parse_element_line(&eid,
1548                                  &is_subbranch, &this_parent_eid, &this_name,
1549                                  stream, scratch_pool, scratch_pool));
1550
1551       if (this_name)
1552         {
1553           svn_element__payload_t *payload;
1554           svn_element__content_t *element;
1555
1556           if (! is_subbranch)
1557             {
1558               payload = svn_element__payload_create_ref(txn->rev, bid, eid,
1559                                                         result_pool);
1560             }
1561           else
1562             {
1563               payload
1564                 = svn_element__payload_create_subbranch(result_pool);
1565             }
1566           element = svn_element__content_create(this_parent_eid,
1567                                                 this_name, payload,
1568                                                 scratch_pool);
1569           SVN_ERR(branch_state_set_element(branch_state, eid, element,
1570                                            scratch_pool));
1571         }
1572     }
1573
1574   branch_state->priv->is_flat = TRUE;
1575   *new_branch = branch_state;
1576   return SVN_NO_ERROR;
1577 }
1578
1579 svn_error_t *
1580 svn_branch__txn_parse(svn_branch__txn_t **txn_p,
1581                       svn_branch__repos_t *repos,
1582                       svn_stream_t *stream,
1583                       apr_pool_t *result_pool,
1584                       apr_pool_t *scratch_pool)
1585 {
1586   svn_branch__txn_t *txn;
1587   svn_revnum_t rev;
1588   int first_eid, next_eid;
1589   int num_branches;
1590   svn_stringbuf_t *line;
1591   svn_boolean_t eof;
1592   int n;
1593   int j;
1594
1595   SVN_ERR(svn_stream_readline(stream, &line, "\n", &eof, scratch_pool));
1596   SVN_ERR_ASSERT(! eof);
1597   n = sscanf(line->data, "r%ld: eids %d %d "
1598                          "branches %d",
1599              &rev,
1600              &first_eid, &next_eid,
1601              &num_branches);
1602   SVN_ERR_ASSERT(n == 4);
1603
1604   txn = branch_txn_create(repos, rev, rev - 1, result_pool);
1605   txn->priv->first_eid = first_eid;
1606   txn->priv->next_eid = next_eid;
1607
1608   /* parse the branches */
1609   for (j = 0; j < num_branches; j++)
1610     {
1611       svn_branch__state_t *branch;
1612
1613       SVN_ERR(svn_branch__state_parse(&branch, txn, stream,
1614                                       result_pool, scratch_pool));
1615       APR_ARRAY_PUSH(txn->priv->branches, void *) = branch;
1616     }
1617
1618   *txn_p = txn;
1619   return SVN_NO_ERROR;
1620 }
1621
1622 /* Serialize the history metadata for BRANCH.
1623  */
1624 static svn_error_t *
1625 history_serialize(svn_stream_t *stream,
1626                   svn_branch__history_t *history,
1627                   apr_pool_t *scratch_pool)
1628 {
1629   apr_array_header_t *ancestors_sorted;
1630   int i;
1631
1632   /* Write entries in sorted order for stability -- so that for example
1633      we can test parse-then-serialize by expecting identical output. */
1634   ancestors_sorted = svn_sort__hash(history->parents,
1635                                     svn_sort_compare_items_lexically,
1636                                     scratch_pool);
1637   SVN_ERR(svn_stream_printf(stream, scratch_pool,
1638                             "history: parents %d\n",
1639                             ancestors_sorted->nelts));
1640   for (i = 0; i < ancestors_sorted->nelts; i++)
1641     {
1642       svn_sort__item_t *item
1643         = &APR_ARRAY_IDX(ancestors_sorted, i, svn_sort__item_t);
1644       svn_branch__rev_bid_t *rev_bid = item->value;
1645
1646       SVN_ERR(svn_stream_printf(stream, scratch_pool,
1647                                 "parent: r%ld.%s\n",
1648                                 rev_bid->rev, rev_bid->bid));
1649     }
1650
1651   return SVN_NO_ERROR;
1652 }
1653
1654 /* Write to STREAM a parseable representation of BRANCH.
1655  */
1656 svn_error_t *
1657 svn_branch__state_serialize(svn_stream_t *stream,
1658                             svn_branch__state_t *branch,
1659                             apr_pool_t *scratch_pool)
1660 {
1661   svn_eid__hash_iter_t *ei;
1662
1663   SVN_ERR_ASSERT(branch->priv->is_flat);
1664
1665   SVN_ERR(svn_stream_printf(stream, scratch_pool,
1666                             "%s root-eid %d num-eids %d\n",
1667                             svn_branch__get_id(branch, scratch_pool),
1668                             branch->priv->element_tree->root_eid,
1669                             apr_hash_count(branch->priv->element_tree->e_map)));
1670
1671   SVN_ERR(history_serialize(stream, branch->priv->history,
1672                                   scratch_pool));
1673
1674   for (SVN_EID__HASH_ITER_SORTED_BY_EID(ei, branch->priv->element_tree->e_map,
1675                                         scratch_pool))
1676     {
1677       int eid = ei->eid;
1678       svn_element__content_t *element = branch_get_element(branch, eid);
1679       int parent_eid;
1680       const char *name;
1681
1682       SVN_ERR_ASSERT(element);
1683       parent_eid = element->parent_eid;
1684       name = element->name[0] ? element->name : ".";
1685       SVN_ERR(svn_stream_printf(stream, scratch_pool,
1686                                 "e%d: %s %d %s\n",
1687                                 eid,
1688                                 element ? ((! element->payload->is_subbranch_root)
1689                                              ? "normal" : "subbranch")
1690                                      : "none",
1691                                 parent_eid, name));
1692     }
1693   return SVN_NO_ERROR;
1694 }
1695
1696 /*
1697  * ========================================================================
1698  */
1699