On Thu, Apr 20, 2017 at 10:00:04AM -0400, Jeff Hostetler wrote:
> Perhaps the thing to learn from this (and the other ones) is that
> we have lots of places where we are building a sorted list by
> iterating over a sorted list. The insert routines are general
> purpose and cannot assume this, so they search first. Perhaps it
> would be clearer to have independent _append and _insert functions
> and have the caller explicitly call the appropriate one. The mainline
> iterations on the existing index could just call the _append form
> and never have to worry about searching or the negative-integer
> return trick. Whereas, the random iterations (such as on the
> command's arg list), would always call the _insert form.
Yes. I'd be much happier if your patch was flipping between two
general-purpose insertion functions. And if that same trick was used on
the dst side.
Or even, given that this these functions are called from a single
location that has sorted input, the binary search was just replaced
completely with an append combined with a sort-check.
That's not the minimal change you were going for, but I think the end
result is simpler and more consistent.
E.g., something like this:
diff --git a/diffcore-rename.c b/diffcore-rename.c
index f7444c86b..a5c017198 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -43,26 +43,20 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two)
}
/*
- * Returns 0 on success, -1 if we found a duplicate.
+ * Returns 0 on success, -1 if we found a duplicate or a sorting problem.
*/
static int add_rename_dst(struct diff_filespec *two)
{
- int first = find_rename_dst(two);
-
- if (first >= 0)
+ if (rename_dst_nr > 0 &&
+ strcmp(two->path, rename_dst[rename_dst_nr - 1].two->path) <= 0)
return -1;
- first = -first - 1;
- /* insert to make it at "first" */
ALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);
+ rename_dst[rename_dst_nr].two = alloc_filespec(two->path);
+ fill_filespec(rename_dst[rename_dst_nr].two,
+ two->oid.hash, two->oid_valid, two->mode);
+ rename_dst[rename_dst_nr].pair = NULL;
rename_dst_nr++;
- if (first < rename_dst_nr)
- memmove(rename_dst + first + 1, rename_dst + first,
- (rename_dst_nr - first - 1) * sizeof(*rename_dst));
- rename_dst[first].two = alloc_filespec(two->path);
- fill_filespec(rename_dst[first].two, two->oid.hash, two->oid_valid,
- two->mode);
- rename_dst[first].pair = NULL;
return 0;
}
@@ -73,36 +67,17 @@ static struct diff_rename_src {
} *rename_src;
static int rename_src_nr, rename_src_alloc;
-static struct diff_rename_src *register_rename_src(struct diff_filepair *p)
+static int register_rename_src(struct diff_filepair *p)
{
- int first, last;
- struct diff_filespec *one = p->one;
- unsigned short score = p->score;
-
- first = 0;
- last = rename_src_nr;
- while (last > first) {
- int next = (last + first) >> 1;
- struct diff_rename_src *src = &(rename_src[next]);
- int cmp = strcmp(one->path, src->p->one->path);
- if (!cmp)
- return src;
- if (cmp < 0) {
- last = next;
- continue;
- }
- first = next+1;
- }
+ if (rename_src_nr > 0 &&
+ strcmp(p->one->path, rename_src[rename_src_nr - 1].p->one->path) <= 0)
+ return -1;
- /* insert to make it at "first" */
ALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);
+ rename_src[rename_src_nr].p = p;
+ rename_src[rename_src_nr].score = p->score;
rename_src_nr++;
- if (first < rename_src_nr)
- memmove(rename_src + first + 1, rename_src + first,
- (rename_src_nr - first - 1) * sizeof(*rename_src));
- rename_src[first].p = p;
- rename_src[first].score = score;
- return &(rename_src[first]);
+ return 0;
}
static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)
@@ -468,7 +443,7 @@ void diffcore_rename(struct diff_options *options)
continue;
else if (add_rename_dst(p->two) < 0) {
warning("skipping rename detection, detected"
- " duplicate destination '%s'",
+ " duplicate or out-of-order destination '%s'",
p->two->path);
goto cleanup;
}
@@ -486,7 +461,12 @@ void diffcore_rename(struct diff_options *options)
*/
if (p->broken_pair && !p->score)
p->one->rename_used++;
- register_rename_src(p);
+ if (register_rename_src(p) < 0) {
+ warning("skipping rename detection, detected"
+ " duplicate or out-of-order source '%s'",
+ p->one->path);
+ goto cleanup;
+ }
}
else if (detect_rename == DIFF_DETECT_COPY) {
/*
@@ -494,7 +474,12 @@ void diffcore_rename(struct diff_options *options)
* one, to indicate ourselves as a user.
*/
p->one->rename_used++;
- register_rename_src(p);
+ if (register_rename_src(p) < 0) {
+ warning("skipping rename detection, detected"
+ " duplicate or out-of-order source '%s'",
+ p->one->path);
+ goto cleanup;
+ }
}
}
if (rename_dst_nr == 0 || rename_src_nr == 0)