tree.c

linux subdivision ying gai ke yi le ba

       idea is to require at most 2*lg(N) deltas to be applied to get
       to any node-revision in a chain of N predecessors.  We do this
       using a technique derived from skip lists:

          - Always redeltify the immediate parent

          - If the number of predecessors is divisible by 2,
              redeltify the revision two predecessors back

          - If the number of predecessors is divisible by 4,
              redeltify the revision four predecessors back

       ... and so on.

       That's the theory, anyway.  Unfortunately, if we strictly
       follow that theory we get a bunch of overhead up front and no
       great benefit until the number of predecessors gets large.  So,
       stop at redeltifying the parent if the number of predecessors
       is less than 32, and also skip the second level (redeltifying
       two predecessors back), since that doesn't help much.  Also,
       don't redeltify the oldest node-revision; it's potentially
       expensive and doesn't help retrieve any other revision.
       (Retrieving the oldest node-revision will still be fast, just
       not as blindingly so.)  */

    int pred_count, nlevels, lev, count;
    const svn_fs_id_t *pred_id;
    struct txn_pred_count_args tpc_args;
    apr_pool_t *subpools[2];
    int active_subpool = 0;

    tpc_args.id = id;
    SVN_ERR (svn_fs_base__retry_txn (fs, txn_body_pred_count, &tpc_args,
                                     pool));
    pred_count = tpc_args.pred_count;

    /* If nothing to deltify, then we're done. */
    if (pred_count == 0)
      return SVN_NO_ERROR;

    /* Decide how many predecessors to redeltify.  To save overhead,
       don't redeltify anything but the immediate predecessor if there
       are less than 32 predecessors. */
    nlevels = 1;
    if (pred_count >= 32)
      {
        while (pred_count % 2 == 0)
          {
            pred_count /= 2;
            nlevels++;
          }

        /* Don't redeltify the oldest revision. */
        if (1 << (nlevels - 1) == pred_count)
          nlevels--;
      }

    /* Redeltify the desired number of predecessors. */
    count = 0;
    pred_id = id;

    /* We need to use two alternating pools because the id used in the
       call to txn_body_pred_id is allocated by the previous inner
       loop iteration.  If we would clear the pool each iteration we
       would free the previous result.  */
    subpools[0] = svn_pool_create (pool);
    subpools[1] = svn_pool_create (pool);
    for (lev = 0; lev < nlevels; lev++)
      {
        /* To save overhead, skip the second level (that is, never
           redeltify the node-revision two predecessors back). */
        if (lev == 1)
          continue;

        /* Note that COUNT is not reset between levels, and neither is
           PREDNODE; we just keep counting from where we were up to
           where we're supposed to get. */
        while (count < (1 << lev))
          {
            struct txn_pred_id_args tpi_args;

            active_subpool = !active_subpool;
            svn_pool_clear (subpools[active_subpool]);

            tpi_args.id = pred_id;
            tpi_args.pool = subpools[active_subpool];
            SVN_ERR (svn_fs_base__retry_txn (fs, txn_body_pred_id, &tpi_args,
                                             subpools[active_subpool]));
            pred_id = tpi_args.pred_id;

            if (pred_id == NULL)
              return svn_error_create (SVN_ERR_FS_CORRUPT, 0,
                                       "Corrupt DB: faulty predecessor count");

            count++;
          }

        /* Finally, do the deltification. */
        td_args.tgt_id = pred_id;
        td_args.base_id = id;
        td_args.is_dir = (kind == svn_node_dir);
        SVN_ERR (svn_fs_base__retry_txn (fs, txn_body_txn_deltify, &td_args,
                                         subpools[active_subpool]));

      }
    svn_pool_destroy (subpools[0]);
    svn_pool_destroy (subpools[1]);
  }

  return SVN_NO_ERROR;
}


struct get_root_args
{
  svn_fs_root_t *root;
  dag_node_t *node;
};


/* Set ARGS->node to the root node of ARGS->root.  */
static svn_error_t *
txn_body_get_root (void *baton, trail_t *trail)
{
  struct get_root_args *args = baton;
  SVN_ERR (get_dag (&(args->node), args->root, "", trail));
  return SVN_NO_ERROR;
}


/* Set *IS_ANCESTOR to non-zero iff ID1 is an ancestor of ID2 in FS,
   as part of TRAIL. */
static svn_error_t *
id_check_ancestor (svn_boolean_t *is_ancestor,
                   svn_fs_t *fs,
                   const svn_fs_id_t *id1,
                   const svn_fs_id_t *id2,
                   trail_t *trail)
{
  dag_node_t *node1, *node2;

  /* Get the nodes. */
  SVN_ERR (svn_fs_base__dag_get_node (&node1, fs, id1, trail));
  SVN_ERR (svn_fs_base__dag_get_node (&node2, fs, id2, trail));

  /* Do the test.  If the test fails, we'll just go with "not an
     ancestor" for now.  ### better come back and check this out.  */
  return svn_fs_base__dag_is_ancestor (is_ancestor, node1, node2, trail);
}


static svn_error_t *
update_ancestry (svn_fs_t *fs,
                 const svn_fs_id_t *source_id,
                 const svn_fs_id_t *target_id,
                 const char *txn_id,
                 const char *target_path,
                 int source_pred_count,
                 trail_t *trail)
{
  node_revision_t *noderev;

  /* Set target's predecessor-id to source_id.  */
  if (strcmp (svn_fs_base__id_txn_id (target_id), txn_id))
    return svn_error_createf
      (SVN_ERR_FS_NOT_MUTABLE, NULL,
       "Unexpected immutable node at '%s'", target_path);
  SVN_ERR (svn_fs_bdb__get_node_revision (&noderev, fs, target_id, trail));
  noderev->predecessor_id = source_id;
  noderev->predecessor_count = source_pred_count;
  if (noderev->predecessor_count != -1)
    noderev->predecessor_count++;
  return svn_fs_bdb__put_node_revision (fs, target_id, noderev, trail);
}


/* Possibly */
static svn_error_t *
undelete_change (svn_fs_t *fs,
                 const char *path,
                 const char *txn_id,
                 trail_t *trail)
{
  apr_hash_t *changes;
  svn_fs_path_change_t *this_change;

  /* Canonicalize PATH. */
  path = svn_fs_base__canonicalize_abspath (path, trail->pool);

  /* First, get the changes associated with TXN_ID. */
  SVN_ERR (svn_fs_bdb__changes_fetch (&changes, fs, txn_id, trail));

  /* Now, do any of those changes apply to path and indicate deletion? */
  this_change = apr_hash_get (changes, path, APR_HASH_KEY_STRING);
  if (this_change
      && ((this_change->change_kind == svn_fs_path_change_delete)
          || (this_change->change_kind == svn_fs_path_change_replace)))
    {
      /* If so, reset the changes and re-add everything except the
         deletion. */
      SVN_ERR (add_change (fs, txn_id, path, NULL,
                           svn_fs_path_change_reset, 0, 0, trail));
      if (this_change->change_kind == svn_fs_path_change_replace)
        {
          SVN_ERR (add_change (fs, txn_id, path, this_change->node_rev_id,
                               svn_fs_path_change_add, this_change->text_mod,
                               this_change->prop_mod, trail));
        }
    }
  else
    {
      /* Else, this function was called in error, OR something is not
         as we expected it to be in the changes table. */
      return svn_error_createf
        (SVN_ERR_FS_CORRUPT, NULL,
         "No deletion changes for path '%s' "
         "in transaction '%s' of filesystem '%s'",
         path, txn_id, fs->path);
    }

  return SVN_NO_ERROR;
}


/* Set the contents of CONFLICT_PATH to PATH, and return an
   SVN_ERR_FS_CONFLICT error that indicates that there was a conflict
   at PATH.  Perform all allocations in POOL (except the allocation of
   CONFLICT_PATH, which should be handled outside this function).  */
static svn_error_t *
conflict_err (svn_stringbuf_t *conflict_path,
              const char *path)
{
  svn_stringbuf_set (conflict_path, path);
  return svn_error_createf (SVN_ERR_FS_CONFLICT, NULL,
                            "Conflict at '%s'", path);
}


/* Merge changes between ANCESTOR and SOURCE into TARGET, as part of
 * TRAIL.  ANCESTOR and TARGET must be distinct node revisions.
 * TARGET_PATH should correspond to TARGET's full path in its
 * filesystem, and is used for reporting conflict location.
 *
 * SOURCE, TARGET, and ANCESTOR are generally directories; this
 * function recursively merges the directories' contents.  If any are
 * files, this function simply returns an error whenever SOURCE,
 * TARGET, and ANCESTOR are all distinct node revisions.
 *
 * If there are differences between ANCESTOR and SOURCE that conflict
 * with changes between ANCESTOR and TARGET, this function returns an
 * SVN_ERR_FS_CONFLICT error, and updates CONFLICT_P to the name of the
 * conflicting node in TARGET, with TARGET_PATH prepended as a path.
 *
 * If there are no conflicting differences, CONFLICT_P is updated to
 * the empty string.
 *
 * CONFLICT_P must point to a valid svn_stringbuf_t.
 *
 * Do any necessary temporary allocation in TRAIL->pool.
 */
static svn_error_t *
merge (svn_stringbuf_t *conflict_p,
       const char *target_path,
       dag_node_t *target,
       dag_node_t *source,
       dag_node_t *ancestor,
       const char *txn_id,
       trail_t *trail)
{
  const svn_fs_id_t *source_id, *target_id, *ancestor_id;
  apr_hash_t *s_entries, *t_entries, *a_entries;
  apr_hash_index_t *hi;
  svn_fs_t *fs;

  /* Make sure everyone comes from the same filesystem. */
  fs = svn_fs_base__dag_get_fs (ancestor);
  if ((fs != svn_fs_base__dag_get_fs (source))
      || (fs != svn_fs_base__dag_get_fs (target)))
    {
      return svn_error_create
        (SVN_ERR_FS_CORRUPT, NULL,
         "Bad merge; ancestor, source, and target not all in same fs");
    }

  /* We have the same fs, now check it. */
  SVN_ERR (svn_fs_base__check_fs (fs));

  source_id   = svn_fs_base__dag_get_id (source);
  target_id   = svn_fs_base__dag_get_id (target);
  ancestor_id = svn_fs_base__dag_get_id (ancestor);

  /* It's improper to call this function with ancestor == target. */
  if (svn_fs_base__id_eq (ancestor_id, target_id))
    {
      svn_string_t *id_str = svn_fs_base__id_unparse (target_id, trail->pool);
      return svn_error_createf
        (SVN_ERR_FS_GENERAL, NULL,
         "Bad merge; target '%s' has id '%s', same as ancestor",
         target_path, id_str->data);
    }

  svn_stringbuf_setempty (conflict_p);

  /* Base cases:
   * Either no change made in source, or same change as made in target.
   * Both mean nothing to merge here.
   */
  if (svn_fs_base__id_eq (ancestor_id, source_id)
      || (svn_fs_base__id_eq (source_id, target_id)))
    return SVN_NO_ERROR;

  /* Else proceed, knowing all three are distinct node revisions.
   *
   * How to merge from this point:
   *
   * if (not all 3 are directories)
   *   {
   *     early exit with conflict;
   *   }
   *
   * // Property changes may only be made to up-to-date
   * // directories, because once the client commits the prop
   * // change, it bumps the directory's revision, and therefore
   * // must be able to depend on there being no other changes to
   * // that directory in the repository.
   * if (target's property list differs from ancestor's)
   *    conflict;
   *
   * for (each entry E in ancestor)
   *   {
   *     if (E exists in target and source)
   *       {
   *         if (source entry points to different id than E)
   *           {
   *             if (target entry points to same id as ancestor E)
   *               change target to point to same id as source entry;
   *             else if ((target entry id different from source)
   *                      && (target entry not descended from source))
   *               {
   *                 if (not all 3 entries point to directories)
   *                   {
   *                     early exit with conflict;
   *                   }
   *
   *                 // We know they are different directories, so...
   *                 recursively merge;
   *               }
   *             // Else target entry same as source entry, or is
   *             // descendant of source entry; either way, leave it.
   *           }
   *       }
   *     else if (E exists in source but not target)
   *       {
   *         if (E changed between ancestor and source)
   *           conflict;
   *         else if (E did not change between ancestor and source)
   *           // do nothing
   *     else if (E exists in target but not source)
   *       {
   *         if (E points the same node rev in target and ancestor)
   *            delete E from target;
   *         else // E points to different node revs in target & ancestor
   *           {
   *             if (E in target is not related to E in ancestor)
   *               conflict;
   *             else
   *               // do nothing
   *           }
   *       }
   *     else
   *       {
   *         // E exists in neither target nor source, so it's a
   *         // double delete -- do nothing, since E is already
   *         // absent from target.  ### kff todo: but it would be
   *         // nice to handle the rename case better.  How?
   *       }
   *   }
   *
   * // This next loop is over those entries in source that were
   * // not already covered in the loop over ancestor above.
   * for (each remaining entry E in source)
   *   {
   *     if (E does not exist in target)
   *       add it to target, based on source;
   *     else if (E exists in target but different id than E in source)
   *       conflict;
   *   }
   *
   *     // All entries in ancestor and source are accounted for.
   *     // Remaining entries in target should be left as-is.
   *   }
   *
   *
   * A WORD ABOUT MERGE RECURSION AND ANCESTRY TRACKING
   *
   * After we do the merge into target, target has absorbed the
   * history between ancestor and source, but there is no record of
   * this absorbtion having happened.  For example, when generating a
   * log message for target, you'd want to include al