[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: O(n**3) behaviour in reintegrate merge

From: Paul Burba <ptburba_at_gmail.com>
Date: Tue, 11 Oct 2011 11:21:16 -0700

On Tue, Oct 11, 2011 at 6:36 AM, Stefan Sperling <stsp_at_elego.de> wrote:
> On Tue, Oct 11, 2011 at 03:05:11PM +0200, Stefan Sperling wrote:
>> So while I think your fixes should be backported to 1.7.1 ASAP,
>> I don't think the status quo is acceptable. How do we want to move
>> forward?
>>
>> For reference, here's the error message I'm getting:

Hi Stefan,

Yes, the error message is rather long. But as I've already said, this
reintegrate merge is a complete and total abuse of the reintegrate
feature. I'm not sure we can save every user from themselves if they
insist on doing strange things....but I've already made that point,
and it appears I'm in the minority, so I wont belabor it any further
:-)

So while I'm a weak -0 on the basic premise of your patch[1], I won't
object to it.

Paul

[1] Re your present patch, the error message is created such that it
appears we have to sync the source branch (/fs-successor-ids) up to
HEAD:

C:\SVN\src-trunk-3>svn up
Updating '.':
At revision 1181989.

C:\SVN\src-trunk-3>svn merge
https://svn.apache.org/repos/asf/subversion/branches/fs-successor-ids
. --reintegrate
..\..\..\subversion\svn\merge-cmd.c:382: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10918: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10887: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10887: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10834: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:10834: (apr_err=195016)
svn: E195016: Reintegrate can only be used if revisions 880536 through
1181989 were previously merged from
https://svn.apache.org/repos/asf/subversion/trunk to the reintegrate
source, but this is not the case.

..\..\..\subversion\libsvn_client\merge.c:10064: (apr_err=195016)
..\..\..\subversion\libsvn_ra_neon\log.c:532: (apr_err=195016)
..\..\..\subversion\libsvn_ra_neon\util.c:1323: (apr_err=195016)
..\..\..\subversion\libsvn_ra_neon\util.c:1556: (apr_err=195016)
..\..\..\subversion\libsvn_ra_neon\log.c:321: (apr_err=195016)
..\..\..\subversion\libsvn_client\merge.c:9865: (apr_err=195016)
svn: E195016: Working copy and merge source not ready for reintegration

But we need only catch up the branch to to youngest sync from trunk
(r1167546) for the reintegrate to be successful:

---trunk_at_880535------------------------------>
        | |
       copy cherrypick
        | merge
        | r1167546
        | |
        V V
   fs-successor-ids_at_880536-----r1167550------->

> Just to drive my point home, compare to this, which is what I get
> with the patch below (I don't intend to commit this as it is, and
> certainly not before this discussion has been resolved).
>
> $ time svn merge --reintegrate ^/subversion/branches/fs-successor-ids
> subversion/svn/merge-cmd.c:382: (apr_err=195016)
> subversion/libsvn_client/merge.c:11024: (apr_err=195016)
> subversion/libsvn_client/merge.c:10993: (apr_err=195016)
> subversion/libsvn_client/merge.c:10993: (apr_err=195016)
> subversion/libsvn_client/merge.c:10940: (apr_err=195016)
> subversion/libsvn_client/merge.c:10940: (apr_err=195016)
> svn: E195016: Reintegrate can only be used if revisions 880536 through 1181776 were previously merged from https://svn.apache.org/repos/asf/subversion/trunk to the reintegrate source, but this is not the case.
>
> subversion/libsvn_client/merge.c:10064: (apr_err=195016)
> subversion/libsvn_ra_serf/log.c:684: (apr_err=195016)
> subversion/libsvn_ra_serf/util.c:768: (apr_err=195016)
> subversion/libsvn_ra_serf/util.c:2118: (apr_err=195016)
> subversion/libsvn_ra_serf/util.c:2118: (apr_err=195016)
> subversion/libsvn_ra_serf/util.c:1850: (apr_err=195016)
> subversion/libsvn_ra_serf/util.c:1491: (apr_err=195016)
> subversion/libsvn_ra_serf/log.c:337: (apr_err=195016)
> subversion/libsvn_client/merge.c:9865: (apr_err=195016)
> svn: E195016: Working copy and merge source not ready for reintegration
>    0m4.43s real     0m1.64s user     0m0.17s system
> $
>
> So the error fits on the screen and appears after 4.5 seconds.
>
> Index: subversion/libsvn_client/merge.c
> ===================================================================
> --- subversion/libsvn_client/merge.c    (revision 1181756)
> +++ subversion/libsvn_client/merge.c    (working copy)
> @@ -9818,6 +9818,57 @@ typedef struct log_find_operative_baton_t
>   apr_pool_t *result_pool;
>  } log_find_operative_baton_t;
>
> +/* A svn_log_entry_receiver_t callback for find_unsynced_range().
> + * Returns SVN_ERR_CLIENT_NOT_READY_TO_MERGE if an unsynced revision
> + * is found. Else returns SVN_NO_ERROR. */
> +static svn_error_t *
> +log_find_unsynced_rev(void *baton,
> +                      svn_log_entry_t *log_entry,
> +                      apr_pool_t *pool)
> +{
> +  log_find_operative_baton_t *log_baton = baton;
> +  apr_hash_index_t *hi;
> +  svn_revnum_t revision;
> +
> +  revision = log_entry->revision;
> +
> +  for (hi = apr_hash_first(pool, log_entry->changed_paths2);
> +       hi;
> +       hi = apr_hash_next(hi))
> +    {
> +      const char *subtree_missing_this_rev;
> +      const char *path = svn__apr_hash_index_key(hi);
> +      const char *rel_path;
> +      const char *source_rel_path;
> +      svn_boolean_t in_catalog;
> +      svn_mergeinfo_t log_entry_as_mergeinfo;
> +
> +      rel_path = svn_fspath__skip_ancestor(log_baton->target_abspath, path);
> +      /* Easy out: The path is not within the tree of interest. */
> +      if (rel_path == NULL)
> +        continue;
> +
> +      source_rel_path = svn_relpath_join(log_baton->source_repos_rel_path,
> +                                         rel_path, pool);
> +
> +      SVN_ERR(svn_mergeinfo_parse(&log_entry_as_mergeinfo,
> +                                  apr_psprintf(pool, "%s:%ld",
> +                                               path, revision),
> +                                  pool));
> +
> +      SVN_ERR(mergeinfo_in_catalog(&in_catalog, &subtree_missing_this_rev,
> +                                   source_rel_path, log_entry_as_mergeinfo,
> +                                   revision, log_baton->merged_catalog,
> +                                   pool, pool));
> +
> +      if (!in_catalog)
> +        return svn_error_create(SVN_ERR_CLIENT_NOT_READY_TO_MERGE,
> +                                NULL, NULL);
> +    }
> +
> +  return SVN_NO_ERROR;
> +}
> +
>  /* A svn_log_entry_receiver_t callback for find_unsynced_ranges(). */
>  static svn_error_t *
>  log_find_operative_revs(void *baton,
> @@ -9934,6 +9985,109 @@ log_find_operative_revs(void *baton,
>         but based on the mergeinfo in MERGED_CATALOG, the change was
>         previously merged.
>
> +   Return SVN_ERR_CLIENT_NOT_READY_TO_MERGE if a revision is found which
> +   is not a phantom. Else, return no error.
> +
> +   Note: The keys in all mergeinfo catalogs used here are relative to the
> +   root of the repository.
> +
> +   Use SCRATCH_POOL for all temporary allocations. */
> +static svn_error_t *
> +find_unsynced_range(const char *source_repos_rel_path,
> +                    const char *target_repos_rel_path,
> +                    svn_mergeinfo_catalog_t unmerged_catalog,
> +                    svn_mergeinfo_catalog_t merged_catalog,
> +                    svn_ra_session_t *ra_session,
> +                    apr_pool_t *scratch_pool)
> +{
> +  apr_array_header_t *potentially_unmerged_ranges = NULL;
> +
> +  /* Convert all the unmerged history to a rangelist. */
> +  if (apr_hash_count(unmerged_catalog))
> +    {
> +      apr_hash_index_t *hi_catalog;
> +
> +      potentially_unmerged_ranges =
> +        apr_array_make(scratch_pool, 1, sizeof(svn_merge_range_t *));
> +
> +      for (hi_catalog = apr_hash_first(scratch_pool, unmerged_catalog);
> +           hi_catalog;
> +           hi_catalog = apr_hash_next(hi_catalog))
> +        {
> +          svn_mergeinfo_t mergeinfo = svn__apr_hash_index_val(hi_catalog);
> +          apr_hash_index_t *hi_mergeinfo;
> +          apr_pool_t *iterpool = svn_pool_create(scratch_pool);
> +
> +          for (hi_mergeinfo = apr_hash_first(scratch_pool, mergeinfo);
> +               hi_mergeinfo;
> +               hi_mergeinfo = apr_hash_next(hi_mergeinfo))
> +            {
> +              apr_array_header_t *rangelist =
> +                svn__apr_hash_index_val(hi_mergeinfo);
> +
> +              svn_pool_clear(iterpool);
> +              SVN_ERR(svn_rangelist_merge2(potentially_unmerged_ranges,
> +                                           rangelist, scratch_pool, iterpool));
> +            }
> +          svn_pool_destroy(iterpool);
> +        }
> +    }
> +
> +  /* Find any unmerged revisions which both affect the source and
> +     are not yet merged to it. */
> +  if (potentially_unmerged_ranges)
> +    {
> +      svn_revnum_t oldest_rev =
> +        (APR_ARRAY_IDX(potentially_unmerged_ranges,
> +                       0,
> +                       svn_merge_range_t *))->start + 1;
> +      svn_revnum_t youngest_rev =
> +        (APR_ARRAY_IDX(potentially_unmerged_ranges,
> +                       potentially_unmerged_ranges->nelts - 1,
> +                       svn_merge_range_t *))->end;
> +      apr_array_header_t *log_targets = apr_array_make(scratch_pool, 1,
> +                                                       sizeof(const char *));
> +      log_find_operative_baton_t log_baton;
> +
> +      log_baton.merged_catalog = merged_catalog;
> +      log_baton.unmerged_catalog = NULL;
> +      log_baton.source_repos_rel_path = source_repos_rel_path;
> +      log_baton.target_abspath = apr_psprintf(scratch_pool, "/%s",
> +                                              target_repos_rel_path);
> +      log_baton.result_pool = NULL;
> +
> +      APR_ARRAY_PUSH(log_targets, const char *) = "";
> +
> +      SVN_ERR(svn_ra_get_log2(ra_session, log_targets, youngest_rev,
> +                              oldest_rev, 0, TRUE, FALSE, FALSE,
> +                              NULL, log_find_unsynced_rev, &log_baton,
> +                              scratch_pool));
> +    }
> +
> +  return SVN_NO_ERROR;
> +}
> +
> +/* Determine if the mergeinfo on a reintegrate source SOURCE_REPOS_REL_PATH,
> +   reflects that the source is fully synced with the reintegrate target
> +   TARGET_REPOS_REL_PATH, even if a naive interpretation of the source's
> +   mergeinfo says otherwise -- See issue #3577.
> +
> +   UNMERGED_CATALOG represents the history (as mergeinfo) from
> +   TARGET_REPOS_REL_PATH that is not represented in SOURCE_REPOS_REL_PATH's
> +   explicit/inherited mergeinfo as represented by MERGED_CATALOG.
> +   MERGEINFO_CATALOG may be empty if the source has no explicit or inherited
> +   mergeinfo.
> +
> +   Using RA_SESSION, which is pointed at TARGET_REPOS_REL_PATH, check that all
> +   of the unmerged revisions in UNMERGED_CATALOG's mergeinfos are "phantoms",
> +   that is, one of the following conditions holds:
> +
> +     1) The revision affects no corresponding paths in SOURCE_REPOS_REL_PATH.
> +
> +     2) The revision affects corresponding paths in SOURCE_REPOS_REL_PATH,
> +        but based on the mergeinfo in MERGED_CATALOG, the change was
> +        previously merged.
> +
>    Make a deep copy, allocated in RESULT_POOL, of any portions of
>    UNMERGED_CATALOG that are not phantoms, to TRUE_UNMERGED_CATALOG.
>
> @@ -10631,7 +10785,6 @@ merge_reintegrate_locked(const char *source,
>   const char *url1, *url2;
>   svn_revnum_t rev1, rev2;
>   svn_mergeinfo_t unmerged_to_source_mergeinfo_catalog;
> -  svn_mergeinfo_t final_unmerged_catalog;
>   svn_mergeinfo_t merged_to_source_mergeinfo_catalog;
>   svn_boolean_t use_sleep = FALSE;
>   svn_error_t *err;
> @@ -10765,34 +10918,26 @@ merge_reintegrate_locked(const char *source,
>       /* Have we actually merged anything to the source from the
>          target?  If so, make sure we've merged a contiguous
>          prefix. */
> -      final_unmerged_catalog = apr_hash_make(scratch_pool);
> -
> -      SVN_ERR(find_unsynced_ranges(source_repos_rel_path,
> -                                   yc_ancestor_path,
> -                                   unmerged_to_source_mergeinfo_catalog,
> -                                   merged_to_source_mergeinfo_catalog,
> -                                   final_unmerged_catalog,
> -                                   target_ra_session, scratch_pool,
> -                                   scratch_pool));
> -
> -      if (apr_hash_count(final_unmerged_catalog))
> +      err = find_unsynced_range(source_repos_rel_path,
> +                                yc_ancestor_path,
> +                                unmerged_to_source_mergeinfo_catalog,
> +                                merged_to_source_mergeinfo_catalog,
> +                                target_ra_session, scratch_pool);
> +      if (err)
>         {
> -          svn_string_t *source_mergeinfo_cat_string;
> +          if (err->apr_err != SVN_ERR_CLIENT_NOT_READY_TO_MERGE)
> +            return svn_error_trace(err);
>
> -          SVN_ERR(svn_mergeinfo__catalog_to_formatted_string(
> -            &source_mergeinfo_cat_string,
> -            final_unmerged_catalog,
> -            "  ", "    Missing ranges: ", scratch_pool));
> -          return svn_error_createf(SVN_ERR_CLIENT_NOT_READY_TO_MERGE,
> -                                   NULL,
> -                                   _("Reintegrate can only be used if "
> -                                     "revisions %ld through %ld were "
> -                                     "previously merged from %s to the "
> -                                     "reintegrate source, but this is "
> -                                     "not the case:\n%s"),
> -                                   yc_ancestor_rev + 1, rev2,
> -                                   target_url,
> -                                   source_mergeinfo_cat_string->data);
> +          return svn_error_trace(
> +                   svn_error_quick_wrap(err,
> +                                        apr_psprintf(scratch_pool,
> +                                        _("Reintegrate can only be used if "
> +                                          "revisions %ld through %ld were "
> +                                          "previously merged from %s to the "
> +                                          "reintegrate source, but this is "
> +                                          "not the case.\n"),
> +                                          yc_ancestor_rev + 1, rev2,
> +                                          target_url)));
>         }
>     }
>
>
>
Received on 2011-10-11 20:21:51 CEST

This is an archived mail posted to the Subversion Dev mailing list.