tree.c

subversion-1.4.3-1.tar.gz 配置svn的源码

  /* If there are entries, recurse on 'em.  */
  if (entries)
    {
      apr_pool_t *subpool = svn_pool_create(pool);
      apr_hash_index_t *hi;

      for (hi = apr_hash_first(pool, entries); hi; hi = apr_hash_next(hi))
        {
          /* KEY will be the entry name, VAL the dirent (about
             which we really don't care) */
          const void *key;
          svn_pool_clear(subpool);
          apr_hash_this(hi, &key, NULL, NULL);
          SVN_ERR(deltify_mutable(fs, root,
                                  svn_path_join(path, key, subpool),
                                  txn_id, subpool));
        }

      svn_pool_destroy(subpool);
    }

  /* Finally, deltify old data against this node. */
  {
    /* Redeltify predecessor node-revisions of the one we added.  The
       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, trail->pool));
  return SVN_NO_ERROR;
}



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,
                apr_pool_t *pool)
{
  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, pool));
  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, pool);
}


/* 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 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,
      apr_pool_t *pool)
{
  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;
  apr_pool_t *iterpool;
  svn_fs_t *fs;
  int pred_count;

  /* 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, 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 NAME in the directory ANCESTOR:
   *
   *   Let ANCESTOR-ENTRY, SOURCE-ENTRY, and TARGET-ENTRY be the IDs of
   *   the name within ANCESTOR, SOURCE, and TARGET respectively.
   *   (Possibly null if NAME does not exist in SOURCE or TARGET.)
   *
   *   If ANCESTOR-ENTRY == SOURCE-ENTRY, then:
   *     No changes were made to this entry while the transaction was in
   *     progress, so do nothing to the target.
   *
   *   Else if ANCESTOR-ENTRY == TARGET-ENTRY, then:
   *     A change was made to this entry while the transaction was in
   *     process, but the transaction did not touch this entry.  Replace
   *     TARGET-ENTRY with SOURCE-ENTRY.
   *
   *   Else:
   *     Changes were made to this entry both within the transaction and
   *     to the repository while the transaction was in progress.  They
   *     must be merged or declared to be in conflict.
   *
   *     If SOURCE-ENTRY and TARGET-ENTRY are both null, that's a
   *     double delete; flag a conflict.
   *
   *     If any of the three entries is of type file, declare a conflict.
   *
   *     If either SOURCE-ENTRY or TARGET-ENTRY is not a direct
   *     modification of ANCESTOR-ENTRY (determine by comparing the
   *     node-id fields), declare a conflict.  A replacement is
   *     incompatible with a modification or other replacement--even
   *     an identical replacement.
   *
   *     Direct modifications were made to the directory ANCESTOR-ENTRY
   *     in both SOURCE and TARGET.  Recursively merge these
   *     modifications.
   *
   * For each leftover entry NAME in the directory SOURCE:
   *
   *   If NAME exists in TARGET, declare a conflict.  Even if SOURCE and
   *   TARGET are adding exactly the same thing, two additions are not
   *   auto-mergeable with each other.
   *
   *   Add NAME to TARGET with the entry from SOURCE.
   *
   * Now that we are done merging the changes from SOURCE into the
   * directory TARGET, update TARGET's predecessor to be SOURCE.
   */

  if ((svn_fs_base__dag_node_kind(source) != svn_node_dir)
      || (svn_fs_base__dag_node_kind(target) != svn_node_dir)
      || (svn_fs_base__dag_node_kind(ancestor) != svn_node_dir))
    {
      return conflict_err(conflict_p, target_path);
    }


  /* Possible early merge failure: if target and ancestor have
     different property lists, then the merge should fail.
     Propchanges can *only* be committed on an up-to-date directory.

     ### TODO: Please see issue #418 about the inelegance of this. */
  {
    node_revision_t *tgt_nr, *anc_nr;

    /* Get node revisions for our id's. */
    SVN_ERR(svn_fs_bdb__get_node_revision(&tgt_nr, fs, target_id, 
                                          trail, pool));
    SVN_ERR(svn_fs_bdb__get_node_revision(&anc_nr, fs, ancestor_id, 
                                          trail, pool));

    /* Now compare the prop-keys of the skels.  Note that just because
       the keys are different -doesn't- mean the proplists have
       different contents.  But merge() isn't concerned with contents;
       it doesn't do a brute-force comparison on textual contents, so
       it won't do that here either.  Checking to see if the propkey
       atoms are `equal' is enough. */
    if (! svn_fs_base__same_keys(tgt_nr->prop_key, anc_nr->prop_key))
      {
        return conflict_err(conflict_p, target_path);
      }
  }

  /* ### todo: it would be more efficient to simply check for a NULL
     entries hash where necessary below than to allocate an empty hash
     here, but another day, another day... */
  SVN_ERR(svn_fs_base__dag_dir_entries(&s_entries, source, trail, pool));
  if (! s_entries)
    s_entries = apr_hash_make(pool);
  SVN_ERR(svn_fs_base__dag_dir_entries(&t_entries, target, trail, pool));
  if (! t_entries)
    t_entries = apr_hash_make(pool);
  SVN_ERR(svn_fs_base__dag_dir_entries(&a_entries, ancestor, trail, pool));
  if (! a_entries)
    a_entries = apr_hash_make(pool);

  /* for each entry E in a_entries... */
  iterpool = svn_pool_create(pool);
  for (hi = apr_hash_first(pool, a_entries);
       hi;
       hi = apr_hash_next(hi))
    {
      svn_fs_dirent_t *s_entry, *t_entry, *a_entry;

      const void *key;
      void *val;
      apr_ssize_t klen;

      svn_pool_clear(iterpool);

      /* KEY will be the entry name in ancestor, VAL the dirent */
      apr_hash_this(hi, &key, &klen, &val);
      a_entry = val;

      s_entry = apr_hash_get(s_entries, key, klen)