Revision 56d7c27af1f8aa7519f165f6c022732e64db3716 authored by Jeff King on 26 May 2011, 16:30:27 UTC, committed by Junio C Hamano on 26 May 2011, 20:54:18 UTC
The read_in_full function repeatedly calls read() to fill a buffer. If the first read() returns an error, we notify the caller by returning the error. However, if we read some data and then get an error on a subsequent read, we simply return the amount of data that we did read, and the caller is unaware of the error. This makes the tradeoff that seeing the partial data is more important than the fact that an error occurred. In practice, this is generally not the case; we care more if an error occurred, and should throw away any partial data. I audited the current callers. In most cases, this will make no difference at all, as they do: if (read_in_full(fd, buf, size) != size) error("short read"); However, it will help in a few cases: 1. In sha1_file.c:index_stream, we would fail to notice errors in the incoming stream. 2. When reading symbolic refs in resolve_ref, we would fail to notice errors and potentially use a truncated ref name. 3. In various places, we will get much better error messages. For example, callers of safe_read would erroneously print "the remote end hung up unexpectedly" instead of showing the read error. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
1 parent 09ffc70
xpatience.c
/*
* LibXDiff by Davide Libenzi ( File Differential Library )
* Copyright (C) 2003-2009 Davide Libenzi, Johannes E. Schindelin
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
* Davide Libenzi <davidel@xmailserver.org>
*
*/
#include "xinclude.h"
#include "xtypes.h"
#include "xdiff.h"
/*
* The basic idea of patience diff is to find lines that are unique in
* both files. These are intuitively the ones that we want to see as
* common lines.
*
* The maximal ordered sequence of such line pairs (where ordered means
* that the order in the sequence agrees with the order of the lines in
* both files) naturally defines an initial set of common lines.
*
* Now, the algorithm tries to extend the set of common lines by growing
* the line ranges where the files have identical lines.
*
* Between those common lines, the patience diff algorithm is applied
* recursively, until no unique line pairs can be found; these line ranges
* are handled by the well-known Myers algorithm.
*/
#define NON_UNIQUE ULONG_MAX
/*
* This is a hash mapping from line hash to line numbers in the first and
* second file.
*/
struct hashmap {
int nr, alloc;
struct entry {
unsigned long hash;
/*
* 0 = unused entry, 1 = first line, 2 = second, etc.
* line2 is NON_UNIQUE if the line is not unique
* in either the first or the second file.
*/
unsigned long line1, line2;
/*
* "next" & "previous" are used for the longest common
* sequence;
* initially, "next" reflects only the order in file1.
*/
struct entry *next, *previous;
} *entries, *first, *last;
/* were common records found? */
unsigned long has_matches;
mmfile_t *file1, *file2;
xdfenv_t *env;
xpparam_t const *xpp;
};
/* The argument "pass" is 1 for the first file, 2 for the second. */
static void insert_record(int line, struct hashmap *map, int pass)
{
xrecord_t **records = pass == 1 ?
map->env->xdf1.recs : map->env->xdf2.recs;
xrecord_t *record = records[line - 1], *other;
/*
* After xdl_prepare_env() (or more precisely, due to
* xdl_classify_record()), the "ha" member of the records (AKA lines)
* is _not_ the hash anymore, but a linearized version of it. In
* other words, the "ha" member is guaranteed to start with 0 and
* the second record's ha can only be 0 or 1, etc.
*
* So we multiply ha by 2 in the hope that the hashing was
* "unique enough".
*/
int index = (int)((record->ha << 1) % map->alloc);
while (map->entries[index].line1) {
other = map->env->xdf1.recs[map->entries[index].line1 - 1];
if (map->entries[index].hash != record->ha ||
!xdl_recmatch(record->ptr, record->size,
other->ptr, other->size,
map->xpp->flags)) {
if (++index >= map->alloc)
index = 0;
continue;
}
if (pass == 2)
map->has_matches = 1;
if (pass == 1 || map->entries[index].line2)
map->entries[index].line2 = NON_UNIQUE;
else
map->entries[index].line2 = line;
return;
}
if (pass == 2)
return;
map->entries[index].line1 = line;
map->entries[index].hash = record->ha;
if (!map->first)
map->first = map->entries + index;
if (map->last) {
map->last->next = map->entries + index;
map->entries[index].previous = map->last;
}
map->last = map->entries + index;
map->nr++;
}
/*
* This function has to be called for each recursion into the inter-hunk
* parts, as previously non-unique lines can become unique when being
* restricted to a smaller part of the files.
*
* It is assumed that env has been prepared using xdl_prepare().
*/
static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env,
struct hashmap *result,
int line1, int count1, int line2, int count2)
{
result->file1 = file1;
result->file2 = file2;
result->xpp = xpp;
result->env = env;
/* We know exactly how large we want the hash map */
result->alloc = count1 * 2;
result->entries = (struct entry *)
xdl_malloc(result->alloc * sizeof(struct entry));
if (!result->entries)
return -1;
memset(result->entries, 0, result->alloc * sizeof(struct entry));
/* First, fill with entries from the first file */
while (count1--)
insert_record(line1++, result, 1);
/* Then search for matches in the second file */
while (count2--)
insert_record(line2++, result, 2);
return 0;
}
/*
* Find the longest sequence with a smaller last element (meaning a smaller
* line2, as we construct the sequence with entries ordered by line1).
*/
static int binary_search(struct entry **sequence, int longest,
struct entry *entry)
{
int left = -1, right = longest;
while (left + 1 < right) {
int middle = (left + right) / 2;
/* by construction, no two entries can be equal */
if (sequence[middle]->line2 > entry->line2)
right = middle;
else
left = middle;
}
/* return the index in "sequence", _not_ the sequence length */
return left;
}
/*
* The idea is to start with the list of common unique lines sorted by
* the order in file1. For each of these pairs, the longest (partial)
* sequence whose last element's line2 is smaller is determined.
*
* For efficiency, the sequences are kept in a list containing exactly one
* item per sequence length: the sequence with the smallest last
* element (in terms of line2).
*/
static struct entry *find_longest_common_sequence(struct hashmap *map)
{
struct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *));
int longest = 0, i;
struct entry *entry;
for (entry = map->first; entry; entry = entry->next) {
if (!entry->line2 || entry->line2 == NON_UNIQUE)
continue;
i = binary_search(sequence, longest, entry);
entry->previous = i < 0 ? NULL : sequence[i];
sequence[++i] = entry;
if (i == longest)
longest++;
}
/* No common unique lines were found */
if (!longest) {
xdl_free(sequence);
return NULL;
}
/* Iterate starting at the last element, adjusting the "next" members */
entry = sequence[longest - 1];
entry->next = NULL;
while (entry->previous) {
entry->previous->next = entry;
entry = entry->previous;
}
xdl_free(sequence);
return entry;
}
static int match(struct hashmap *map, int line1, int line2)
{
xrecord_t *record1 = map->env->xdf1.recs[line1 - 1];
xrecord_t *record2 = map->env->xdf2.recs[line2 - 1];
return xdl_recmatch(record1->ptr, record1->size,
record2->ptr, record2->size, map->xpp->flags);
}
static int patience_diff(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env,
int line1, int count1, int line2, int count2);
static int walk_common_sequence(struct hashmap *map, struct entry *first,
int line1, int count1, int line2, int count2)
{
int end1 = line1 + count1, end2 = line2 + count2;
int next1, next2;
for (;;) {
/* Try to grow the line ranges of common lines */
if (first) {
next1 = first->line1;
next2 = first->line2;
while (next1 > line1 && next2 > line2 &&
match(map, next1 - 1, next2 - 1)) {
next1--;
next2--;
}
} else {
next1 = end1;
next2 = end2;
}
while (line1 < next1 && line2 < next2 &&
match(map, line1, line2)) {
line1++;
line2++;
}
/* Recurse */
if (next1 > line1 || next2 > line2) {
struct hashmap submap;
memset(&submap, 0, sizeof(submap));
if (patience_diff(map->file1, map->file2,
map->xpp, map->env,
line1, next1 - line1,
line2, next2 - line2))
return -1;
}
if (!first)
return 0;
while (first->next &&
first->next->line1 == first->line1 + 1 &&
first->next->line2 == first->line2 + 1)
first = first->next;
line1 = first->line1 + 1;
line2 = first->line2 + 1;
first = first->next;
}
}
static int fall_back_to_classic_diff(struct hashmap *map,
int line1, int count1, int line2, int count2)
{
/*
* This probably does not work outside Git, since
* we have a very simple mmfile structure.
*
* Note: ideally, we would reuse the prepared environment, but
* the libxdiff interface does not (yet) allow for diffing only
* ranges of lines instead of the whole files.
*/
mmfile_t subfile1, subfile2;
xpparam_t xpp;
xdfenv_t env;
subfile1.ptr = (char *)map->env->xdf1.recs[line1 - 1]->ptr;
subfile1.size = map->env->xdf1.recs[line1 + count1 - 2]->ptr +
map->env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr;
subfile2.ptr = (char *)map->env->xdf2.recs[line2 - 1]->ptr;
subfile2.size = map->env->xdf2.recs[line2 + count2 - 2]->ptr +
map->env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr;
xpp.flags = map->xpp->flags & ~XDF_PATIENCE_DIFF;
if (xdl_do_diff(&subfile1, &subfile2, &xpp, &env) < 0)
return -1;
memcpy(map->env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1);
memcpy(map->env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2);
xdl_free_env(&env);
return 0;
}
/*
* Recursively find the longest common sequence of unique lines,
* and if none was found, ask xdl_do_diff() to do the job.
*
* This function assumes that env was prepared with xdl_prepare_env().
*/
static int patience_diff(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env,
int line1, int count1, int line2, int count2)
{
struct hashmap map;
struct entry *first;
int result = 0;
/* trivial case: one side is empty */
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(&map, 0, sizeof(map));
if (fill_hashmap(file1, file2, xpp, env, &map,
line1, count1, line2, count2))
return -1;
/* are there any matching lines at all? */
if (!map.has_matches) {
while(count1--)
env->xdf1.rchg[line1++ - 1] = 1;
while(count2--)
env->xdf2.rchg[line2++ - 1] = 1;
xdl_free(map.entries);
return 0;
}
first = find_longest_common_sequence(&map);
if (first)
result = walk_common_sequence(&map, first,
line1, count1, line2, count2);
else
result = fall_back_to_classic_diff(&map,
line1, count1, line2, count2);
xdl_free(map.entries);
return result;
}
int xdl_do_patience_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;
/* environment is cleaned up in xdl_diff() */
return patience_diff(file1, file2, xpp, env,
1, env->xdf1.nrec, 1, env->xdf2.nrec);
}
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...