Revision b018ff60857ee7d79e3c4a8772bac08656a2a3c6 authored by Jeff King on 29 December 2012, 20:51:54 UTC, committed by Junio C Hamano on 04 November 2013, 18:13:27 UTC
When we call "read-tree --reset -u HEAD ORIG_HEAD", the first thing we do with the index is to call read_cache_unmerged. Originally that would read the index, leaving aside any unmerged entries. However, as of d1a43f2 (reset --hard/read-tree --reset -u: remove unmerged new paths, 2008-10-15), it actually creates a new cache entry to serve as a placeholder, so that we later know to update the working tree. However, we later noticed that the sha1 of that unmerged entry was just copied from some higher stage, leaving you with random content in the index. That was fixed by e11d7b5 ("reset --merge": fix unmerged case, 2009-12-31), which instead puts the null sha1 into the newly created entry, and sets a CE_CONFLICTED flag. At the same time, it teaches the unpack-trees machinery to pay attention to this flag, so that oneway_merge throws away the current value. However, it did not update the code paths for twoway_merge, which is where we end up in the two-way read-tree with --reset. We notice that the HEAD and ORIG_HEAD versions are the same, and say "oh, we can just reuse the current version". But that's not true. The current version is bogus. Notice this case and make sure we do not keep the bogus entry; either we do not have that path in the tree we are moving to (i.e. remove it), or we want to have the cache entry we created for the tree we are moving to (i.e. resolve by explicitly saying the "newtree" version is what we want). [jc: this is from the almost year-old $gmane/212316] Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
1 parent c479d14
xhistogram.c
/*
* Copyright (C) 2010, Google Inc.
* and other copyright owners as documented in JGit's IP log.
*
* This program and the accompanying materials are made available
* under the terms of the Eclipse Distribution License v1.0 which
* accompanies this distribution, is reproduced below, and is
* available at http://www.eclipse.org/org/documents/edl-v10.php
*
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
* conditions are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* - Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
*
* - Neither the name of the Eclipse Foundation, Inc. nor the
* names of its contributors may be used to endorse or promote
* products derived from this software without specific prior
* written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "xinclude.h"
#include "xtypes.h"
#include "xdiff.h"
#define MAX_PTR UINT_MAX
#define MAX_CNT UINT_MAX
#define LINE_END(n) (line##n + count##n - 1)
#define LINE_END_PTR(n) (*line##n + *count##n - 1)
struct histindex {
struct record {
unsigned int ptr, cnt;
struct record *next;
} **records, /* an ocurrence */
**line_map; /* map of line to record chain */
chastore_t rcha;
unsigned int *next_ptrs;
unsigned int table_bits,
records_size,
line_map_size;
unsigned int max_chain_length,
key_shift,
ptr_shift;
unsigned int cnt,
has_common;
xdfenv_t *env;
xpparam_t const *xpp;
};
struct region {
unsigned int begin1, end1;
unsigned int begin2, end2;
};
#define LINE_MAP(i, a) (i->line_map[(a) - i->ptr_shift])
#define NEXT_PTR(index, ptr) \
(index->next_ptrs[(ptr) - index->ptr_shift])
#define CNT(index, ptr) \
((LINE_MAP(index, ptr))->cnt)
#define REC(env, s, l) \
(env->xdf##s.recs[l - 1])
static int cmp_recs(xpparam_t const *xpp,
xrecord_t *r1, xrecord_t *r2)
{
return r1->ha == r2->ha &&
xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,
xpp->flags);
}
#define CMP_ENV(xpp, env, s1, l1, s2, l2) \
(cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2)))
#define CMP(i, s1, l1, s2, l2) \
(cmp_recs(i->xpp, REC(i->env, s1, l1), REC(i->env, s2, l2)))
#define TABLE_HASH(index, side, line) \
XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)
static int scanA(struct histindex *index, int line1, int count1)
{
unsigned int ptr, tbl_idx;
unsigned int chain_len;
struct record **rec_chain, *rec;
for (ptr = LINE_END(1); line1 <= ptr; ptr--) {
tbl_idx = TABLE_HASH(index, 1, ptr);
rec_chain = index->records + tbl_idx;
rec = *rec_chain;
chain_len = 0;
while (rec) {
if (CMP(index, 1, rec->ptr, 1, ptr)) {
/*
* ptr is identical to another element. Insert
* it onto the front of the existing element
* chain.
*/
NEXT_PTR(index, ptr) = rec->ptr;
rec->ptr = ptr;
/* cap rec->cnt at MAX_CNT */
rec->cnt = XDL_MIN(MAX_CNT, rec->cnt + 1);
LINE_MAP(index, ptr) = rec;
goto continue_scan;
}
rec = rec->next;
chain_len++;
}
if (chain_len == index->max_chain_length)
return -1;
/*
* This is the first time we have ever seen this particular
* element in the sequence. Construct a new chain for it.
*/
if (!(rec = xdl_cha_alloc(&index->rcha)))
return -1;
rec->ptr = ptr;
rec->cnt = 1;
rec->next = *rec_chain;
*rec_chain = rec;
LINE_MAP(index, ptr) = rec;
continue_scan:
; /* no op */
}
return 0;
}
static int try_lcs(struct histindex *index, struct region *lcs, int b_ptr,
int line1, int count1, int line2, int count2)
{
unsigned int b_next = b_ptr + 1;
struct record *rec = index->records[TABLE_HASH(index, 2, b_ptr)];
unsigned int as, ae, bs, be, np, rc;
int should_break;
for (; rec; rec = rec->next) {
if (rec->cnt > index->cnt) {
if (!index->has_common)
index->has_common = CMP(index, 1, rec->ptr, 2, b_ptr);
continue;
}
as = rec->ptr;
if (!CMP(index, 1, as, 2, b_ptr))
continue;
index->has_common = 1;
for (;;) {
should_break = 0;
np = NEXT_PTR(index, as);
bs = b_ptr;
ae = as;
be = bs;
rc = rec->cnt;
while (line1 < as && line2 < bs
&& CMP(index, 1, as - 1, 2, bs - 1)) {
as--;
bs--;
if (1 < rc)
rc = XDL_MIN(rc, CNT(index, as));
}
while (ae < LINE_END(1) && be < LINE_END(2)
&& CMP(index, 1, ae + 1, 2, be + 1)) {
ae++;
be++;
if (1 < rc)
rc = XDL_MIN(rc, CNT(index, ae));
}
if (b_next <= be)
b_next = be + 1;
if (lcs->end1 - lcs->begin1 < ae - as || rc < index->cnt) {
lcs->begin1 = as;
lcs->begin2 = bs;
lcs->end1 = ae;
lcs->end2 = be;
index->cnt = rc;
}
if (np == 0)
break;
while (np <= ae) {
np = NEXT_PTR(index, np);
if (np == 0) {
should_break = 1;
break;
}
}
if (should_break)
break;
as = np;
}
}
return b_next;
}
static int find_lcs(struct histindex *index, struct region *lcs,
int line1, int count1, int line2, int count2) {
int b_ptr;
if (scanA(index, line1, count1))
return -1;
index->cnt = index->max_chain_length + 1;
for (b_ptr = line2; b_ptr <= LINE_END(2); )
b_ptr = try_lcs(index, lcs, b_ptr, line1, count1, line2, count2);
return index->has_common && index->max_chain_length < index->cnt;
}
static int fall_back_to_classic_diff(struct histindex *index,
int line1, int count1, int line2, int count2)
{
xpparam_t xpp;
xpp.flags = index->xpp->flags & ~XDF_HISTOGRAM_DIFF;
return xdl_fall_back_diff(index->env, &xpp,
line1, count1, line2, count2);
}
static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,
int line1, int count1, int line2, int count2)
{
struct histindex index;
struct region lcs;
int sz;
int result = -1;
if (count1 <= 0 && count2 <= 0)
return 0;
if (LINE_END(1) >= MAX_PTR)
return -1;
if (!count1) {
while(count2--)
env->xdf2.rchg[line2++ - 1] = 1;
return 0;
} else if (!count2) {
while(count1--)
env->xdf1.rchg[line1++ - 1] = 1;
return 0;
}
memset(&index, 0, sizeof(index));
index.env = env;
index.xpp = xpp;
index.records = NULL;
index.line_map = NULL;
/* in case of early xdl_cha_free() */
index.rcha.head = NULL;
index.table_bits = xdl_hashbits(count1);
sz = index.records_size = 1 << index.table_bits;
sz *= sizeof(struct record *);
if (!(index.records = (struct record **) xdl_malloc(sz)))
goto cleanup;
memset(index.records, 0, sz);
sz = index.line_map_size = count1;
sz *= sizeof(struct record *);
if (!(index.line_map = (struct record **) xdl_malloc(sz)))
goto cleanup;
memset(index.line_map, 0, sz);
sz = index.line_map_size;
sz *= sizeof(unsigned int);
if (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz)))
goto cleanup;
memset(index.next_ptrs, 0, sz);
/* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */
if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)
goto cleanup;
index.ptr_shift = line1;
index.max_chain_length = 64;
memset(&lcs, 0, sizeof(lcs));
if (find_lcs(&index, &lcs, line1, count1, line2, count2))
result = fall_back_to_classic_diff(&index, line1, count1, line2, count2);
else {
if (lcs.begin1 == 0 && lcs.begin2 == 0) {
while (count1--)
env->xdf1.rchg[line1++ - 1] = 1;
while (count2--)
env->xdf2.rchg[line2++ - 1] = 1;
result = 0;
} else {
result = histogram_diff(xpp, env,
line1, lcs.begin1 - line1,
line2, lcs.begin2 - line2);
if (result)
goto cleanup;
result = histogram_diff(xpp, env,
lcs.end1 + 1, LINE_END(1) - lcs.end1,
lcs.end2 + 1, LINE_END(2) - lcs.end2);
if (result)
goto cleanup;
}
}
cleanup:
xdl_free(index.records);
xdl_free(index.line_map);
xdl_free(index.next_ptrs);
xdl_cha_free(&index.rcha);
return result;
}
int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env)
{
if (xdl_prepare_env(file1, file2, xpp, env) < 0)
return -1;
return histogram_diff(xpp, env,
env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,
env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);
}
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...