[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: Stefan Sperling <stsp_at_elego.de>
Date: Tue, 11 Oct 2011 15:36:56 +0200

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:

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 15:37:38 CEST

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