From: Junio C Hamano Date: Mon, 25 Jun 2018 20:22:38 +0000 (-0700) Subject: Merge branch 'sb/object-store-alloc' X-Git-Tag: v2.19.0-rc0~188 X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/110240588d5c0ca88d3b55da52068f59d8d6367d?ds=inline;hp=-c Merge branch 'sb/object-store-alloc' The conversion to pass "the_repository" and then "a_repository" throughout the object access API continues. * sb/object-store-alloc: alloc: allow arbitrary repositories for alloc functions object: allow create_object to handle arbitrary repositories object: allow grow_object_hash to handle arbitrary repositories alloc: add repository argument to alloc_commit_index alloc: add repository argument to alloc_report alloc: add repository argument to alloc_object_node alloc: add repository argument to alloc_tag_node alloc: add repository argument to alloc_commit_node alloc: add repository argument to alloc_tree_node alloc: add repository argument to alloc_blob_node object: add repository argument to grow_object_hash object: add repository argument to create_object repository: introduce parsed objects field --- 110240588d5c0ca88d3b55da52068f59d8d6367d diff --combined alloc.c index e8ab14f4a1,714df63316..c2fc5d6888 --- a/alloc.c +++ b/alloc.c @@@ -4,8 -4,7 +4,7 @@@ * Copyright (C) 2006 Linus Torvalds * * The standard malloc/free wastes too much space for objects, partly because - * it maintains all the allocation infrastructure (which isn't needed, since - * we never free an object descriptor anyway), but even more because it ends + * it maintains all the allocation infrastructure, but even more because it ends * up with maximal alignment because it doesn't know what the object alignment * for the new allocation is. */ @@@ -15,6 -14,7 +14,7 @@@ #include "tree.h" #include "commit.h" #include "tag.h" + #include "alloc.h" #define BLOCKING 1024 @@@ -30,8 -30,27 +30,27 @@@ struct alloc_state int count; /* total number of nodes allocated */ int nr; /* number of nodes left in current allocation */ void *p; /* first free node in current allocation */ + + /* bookkeeping of allocations */ + void **slabs; + int slab_nr, slab_alloc; }; + void *allocate_alloc_state(void) + { + return xcalloc(1, sizeof(struct alloc_state)); + } + + void clear_alloc_state(struct alloc_state *s) + { + while (s->slab_nr > 0) { + s->slab_nr--; + free(s->slabs[s->slab_nr]); + } + + FREE_AND_NULL(s->slabs); + } + static inline void *alloc_node(struct alloc_state *s, size_t node_size) { void *ret; @@@ -39,62 -58,57 +58,59 @@@ if (!s->nr) { s->nr = BLOCKING; s->p = xmalloc(BLOCKING * node_size); + + ALLOC_GROW(s->slabs, s->slab_nr + 1, s->slab_alloc); + s->slabs[s->slab_nr++] = s->p; } s->nr--; s->count++; ret = s->p; s->p = (char *)s->p + node_size; memset(ret, 0, node_size); + return ret; } - static struct alloc_state blob_state; - void *alloc_blob_node(void) + void *alloc_blob_node(struct repository *r) { - struct blob *b = alloc_node(&blob_state, sizeof(struct blob)); + struct blob *b = alloc_node(r->parsed_objects->blob_state, sizeof(struct blob)); b->object.type = OBJ_BLOB; return b; } - static struct alloc_state tree_state; - void *alloc_tree_node(void) + void *alloc_tree_node(struct repository *r) { - struct tree *t = alloc_node(&tree_state, sizeof(struct tree)); + struct tree *t = alloc_node(r->parsed_objects->tree_state, sizeof(struct tree)); t->object.type = OBJ_TREE; return t; } - static struct alloc_state tag_state; - void *alloc_tag_node(void) + void *alloc_tag_node(struct repository *r) { - struct tag *t = alloc_node(&tag_state, sizeof(struct tag)); + struct tag *t = alloc_node(r->parsed_objects->tag_state, sizeof(struct tag)); t->object.type = OBJ_TAG; return t; } - static struct alloc_state object_state; - void *alloc_object_node(void) + void *alloc_object_node(struct repository *r) { - struct object *obj = alloc_node(&object_state, sizeof(union any_object)); + struct object *obj = alloc_node(r->parsed_objects->object_state, sizeof(union any_object)); obj->type = OBJ_NONE; return obj; } - static struct alloc_state commit_state; - - unsigned int alloc_commit_index(void) + unsigned int alloc_commit_index(struct repository *r) { - static unsigned int count; - return count++; + return r->parsed_objects->commit_count++; } - void *alloc_commit_node(void) + void *alloc_commit_node(struct repository *r) { - struct commit *c = alloc_node(&commit_state, sizeof(struct commit)); + struct commit *c = alloc_node(r->parsed_objects->commit_state, sizeof(struct commit)); c->object.type = OBJ_COMMIT; - c->index = alloc_commit_index(); + c->index = alloc_commit_index(r); + c->graph_pos = COMMIT_NOT_FROM_GRAPH; + c->generation = GENERATION_NUMBER_INFINITY; return c; } @@@ -105,9 -119,10 +121,10 @@@ static void report(const char *name, un } #define REPORT(name, type) \ - report(#name, name##_state.count, name##_state.count * sizeof(type) >> 10) + report(#name, r->parsed_objects->name##_state->count, \ + r->parsed_objects->name##_state->count * sizeof(type) >> 10) - void alloc_report(void) + void alloc_report(struct repository *r) { REPORT(blob, struct blob); REPORT(tree, struct tree); diff --combined blame.c index ba1b33c7f4,3a11f1ce52..a5c9bd78ab --- a/blame.c +++ b/blame.c @@@ -6,24 -6,7 +6,25 @@@ #include "diffcore.h" #include "tag.h" #include "blame.h" + #include "alloc.h" +#include "commit-slab.h" + +define_commit_slab(blame_suspects, struct blame_origin *); +static struct blame_suspects blame_suspects; + +struct blame_origin *get_blame_suspects(struct commit *commit) +{ + struct blame_origin **result; + + result = blame_suspects_peek(&blame_suspects, commit); + + return result ? *result : NULL; +} + +static void set_blame_suspects(struct commit *commit, struct blame_origin *origin) +{ + *blame_suspects_at(&blame_suspects, commit) = origin; +} void blame_origin_decref(struct blame_origin *o) { @@@ -33,12 -16,12 +34,12 @@@ blame_origin_decref(o->previous); free(o->file.ptr); /* Should be present exactly once in commit chain */ - for (p = o->commit->util; p; l = p, p = p->next) { + for (p = get_blame_suspects(o->commit); p; l = p, p = p->next) { if (p == o) { if (l) l->next = p->next; else - o->commit->util = p->next; + set_blame_suspects(o->commit, p->next); free(o); return; } @@@ -59,8 -42,8 +60,8 @@@ static struct blame_origin *make_origin FLEX_ALLOC_STR(o, path, path); o->commit = commit; o->refcnt = 1; - o->next = commit->util; - commit->util = o; + o->next = get_blame_suspects(commit); + set_blame_suspects(commit, o); return o; } @@@ -72,13 -55,13 +73,13 @@@ static struct blame_origin *get_origin( { struct blame_origin *o, *l; - for (o = commit->util, l = NULL; o; l = o, o = o->next) { + for (o = get_blame_suspects(commit), l = NULL; o; l = o, o = o->next) { if (!strcmp(o->path, path)) { /* bump to front */ if (l) { l->next = o->next; - o->next = commit->util; - commit->util = o; + o->next = get_blame_suspects(commit); + set_blame_suspects(commit, o); } return blame_origin_incref(o); } @@@ -179,7 -162,7 +180,7 @@@ static struct commit *fake_working_tree read_cache(); time(&now); - commit = alloc_commit_node(); + commit = alloc_commit_node(the_repository); commit->object.parsed = 1; commit->date = now; parent_tail = &commit->parents; @@@ -496,7 -479,7 +497,7 @@@ static void queue_blames(struct blame_s porigin->suspects = blame_merge(porigin->suspects, sorted); else { struct blame_origin *o; - for (o = porigin->commit->util; o; o = o->next) { + for (o = get_blame_suspects(porigin->commit); o; o = o->next) { if (o->suspects) { porigin->suspects = sorted; return; @@@ -543,7 -526,7 +544,7 @@@ static struct blame_origin *find_origin const char *paths[2]; /* First check any existing origins */ - for (porigin = parent->util; porigin; porigin = porigin->next) + for (porigin = get_blame_suspects(parent); porigin; porigin = porigin->next) if (!strcmp(porigin->path, origin->path)) { /* * The same path between origin and its parent @@@ -569,10 -552,10 +570,10 @@@ diff_setup_done(&diff_opts); if (is_null_oid(&origin->commit->object.oid)) - do_diff_cache(&parent->tree->object.oid, &diff_opts); + do_diff_cache(get_commit_tree_oid(parent), &diff_opts); else - diff_tree_oid(&parent->tree->object.oid, - &origin->commit->tree->object.oid, + diff_tree_oid(get_commit_tree_oid(parent), + get_commit_tree_oid(origin->commit), "", &diff_opts); diffcore_std(&diff_opts); @@@ -638,10 -621,10 +639,10 @@@ static struct blame_origin *find_rename diff_setup_done(&diff_opts); if (is_null_oid(&origin->commit->object.oid)) - do_diff_cache(&parent->tree->object.oid, &diff_opts); + do_diff_cache(get_commit_tree_oid(parent), &diff_opts); else - diff_tree_oid(&parent->tree->object.oid, - &origin->commit->tree->object.oid, + diff_tree_oid(get_commit_tree_oid(parent), + get_commit_tree_oid(origin->commit), "", &diff_opts); diffcore_std(&diff_opts); @@@ -1273,10 -1256,10 +1274,10 @@@ static void find_copy_in_parent(struct diff_opts.flags.find_copies_harder = 1; if (is_null_oid(&target->commit->object.oid)) - do_diff_cache(&parent->tree->object.oid, &diff_opts); + do_diff_cache(get_commit_tree_oid(parent), &diff_opts); else - diff_tree_oid(&parent->tree->object.oid, - &target->commit->tree->object.oid, + diff_tree_oid(get_commit_tree_oid(parent), + get_commit_tree_oid(target->commit), "", &diff_opts); if (!diff_opts.flags.find_copies_harder) @@@ -1568,7 -1551,7 +1569,7 @@@ void assign_blame(struct blame_scoreboa while (commit) { struct blame_entry *ent; - struct blame_origin *suspect = commit->util; + struct blame_origin *suspect = get_blame_suspects(commit); /* find one suspect to break down */ while (suspect && !suspect->suspects) @@@ -1770,8 -1753,6 +1771,8 @@@ void setup_scoreboard(struct blame_scor struct commit *final_commit = NULL; enum object_type type; + init_blame_suspects(&blame_suspects); + if (sb->reverse && sb->contents_from) die(_("--contents and --reverse do not blend well.")); @@@ -1826,7 -1807,7 +1827,7 @@@ l->item = c; if (add_decoration(&sb->revs->children, &c->parents->item->object, l)) - die("BUG: not unique item in first-parent chain"); + BUG("not unique item in first-parent chain"); c = c->parents->item; } @@@ -1835,7 -1816,7 +1836,7 @@@ } if (is_null_oid(&sb->final->object.oid)) { - o = sb->final->util; + o = get_blame_suspects(sb->final); sb->final_buf = xmemdupz(o->file.ptr, o->file.size); sb->final_buf_size = o->file.size; } diff --combined cache.h index 89a107a7f7,c75559b7d3..d49092d94d --- a/cache.h +++ b/cache.h @@@ -324,7 -324,7 +324,7 @@@ struct index_state drop_cache_tree : 1; struct hashmap name_hash; struct hashmap dir_hash; - unsigned char sha1[20]; + struct object_id oid; struct untracked_cache *untracked; uint64_t fsmonitor_last_update; struct ewah_bitmap *fsmonitor_dirty; @@@ -373,13 -373,6 +373,13 @@@ extern void free_name_hash(struct index #define read_blob_data_from_cache(path, sz) read_blob_data_from_index(&the_index, (path), (sz)) #endif +#define TYPE_BITS 3 + +/* + * Values in this enum (except those outside the 3 bit range) are part + * of pack file format. See Documentation/technical/pack-format.txt + * for more information. + */ enum object_type { OBJ_BAD = -1, OBJ_NONE = 0, @@@ -435,7 -428,6 +435,7 @@@ static inline enum object_type object_t #define GIT_ICASE_PATHSPECS_ENVIRONMENT "GIT_ICASE_PATHSPECS" #define GIT_QUARANTINE_ENVIRONMENT "GIT_QUARANTINE_PATH" #define GIT_OPTIONAL_LOCKS_ENVIRONMENT "GIT_OPTIONAL_LOCKS" +#define GIT_TEXT_DOMAIN_DIR_ENVIRONMENT "GIT_TEXTDOMAINDIR" /* * Environment variable used in handshaking the wire protocol. @@@ -485,7 -477,7 +485,7 @@@ extern const char *get_git_common_dir(v extern char *get_object_directory(void); extern char *get_index_file(void); extern char *get_graft_file(void); -extern int set_git_dir(const char *path); +extern void set_git_dir(const char *path); extern int get_common_dir_noenv(struct strbuf *sb, const char *gitdir); extern int get_common_dir(struct strbuf *sb, const char *gitdir); extern const char *get_git_namespace(void); @@@ -642,7 -634,7 +642,7 @@@ extern int unmerged_index(const struct */ extern int index_has_changes(struct strbuf *sb); -extern int verify_path(const char *path); +extern int verify_path(const char *path, unsigned mode); extern int strcmp_offset(const char *s1, const char *s2, size_t *first_change); extern int index_dir_exists(struct index_state *istate, const char *name, int namelen); extern void adjust_dirname_case(struct index_state *istate, char *name); @@@ -813,7 -805,6 +813,7 @@@ extern char *git_replace_ref_base extern int fsync_object_files; extern int core_preload_index; +extern int core_commit_graph; extern int core_apply_sparse_checkout; extern int precomposed_unicode; extern int protect_hfs; @@@ -1017,10 -1008,21 +1017,10 @@@ static inline void oidclr(struct object memset(oid->hash, 0, GIT_MAX_RAWSZ); } - -#define EMPTY_TREE_SHA1_HEX \ - "4b825dc642cb6eb9a060e54bf8d69288fbee4904" -#define EMPTY_TREE_SHA1_BIN_LITERAL \ - "\x4b\x82\x5d\xc6\x42\xcb\x6e\xb9\xa0\x60" \ - "\xe5\x4b\xf8\xd6\x92\x88\xfb\xee\x49\x04" -extern const struct object_id empty_tree_oid; -#define EMPTY_TREE_SHA1_BIN (empty_tree_oid.hash) - -#define EMPTY_BLOB_SHA1_HEX \ - "e69de29bb2d1d6434b8b29ae775ad8c2e48c5391" -#define EMPTY_BLOB_SHA1_BIN_LITERAL \ - "\xe6\x9d\xe2\x9b\xb2\xd1\xd6\x43\x4b\x8b" \ - "\x29\xae\x77\x5a\xd8\xc2\xe4\x8c\x53\x91" -extern const struct object_id empty_blob_oid; +static inline void oidread(struct object_id *oid, const unsigned char *hash) +{ + memcpy(oid->hash, hash, the_hash_algo->rawsz); +} static inline int is_empty_blob_sha1(const unsigned char *sha1) { @@@ -1042,9 -1044,6 +1042,9 @@@ static inline int is_empty_tree_oid(con return !oidcmp(oid, the_hash_algo->empty_tree); } +const char *empty_tree_oid_hex(void); +const char *empty_blob_oid_hex(void); + /* set default permissions by passing mode arguments to open(2) */ int git_mkstemps_mode(char *pattern, int suffix_len, int mode); int git_mkstemp_mode(char *pattern, int mode); @@@ -1160,15 -1159,7 +1160,15 @@@ int normalize_path_copy(char *dst, cons int longest_ancestor_length(const char *path, struct string_list *prefixes); char *strip_path_suffix(const char *path, const char *suffix); int daemon_avoid_alias(const char *path); -extern int is_ntfs_dotgit(const char *name); + +/* + * These functions match their is_hfs_dotgit() counterparts; see utf8.h for + * details. + */ +int is_ntfs_dotgit(const char *name); +int is_ntfs_dotgitmodules(const char *name); +int is_ntfs_dotgitignore(const char *name); +int is_ntfs_dotgitattributes(const char *name); /* * Returns true iff "str" could be confused as a command-line option when @@@ -1260,7 -1251,7 +1260,7 @@@ extern int has_object_file_with_flags(c * with the specified name. This function does not respect replace * references. */ -extern int has_loose_object_nonlocal(const unsigned char *sha1); +extern int has_loose_object_nonlocal(const struct object_id *oid); extern void assert_oid_type(const struct object_id *oid, enum object_type expect); @@@ -1291,6 -1282,7 +1291,6 @@@ static inline int hex2chr(const char *s #define FALLBACK_DEFAULT_ABBREV 7 struct object_context { - unsigned char tree[20]; unsigned mode; /* * symlink_path is only used by get_tree_entry_follow_symlinks, @@@ -1557,6 -1549,7 +1557,6 @@@ struct pack_window struct pack_entry { off_t offset; - unsigned char sha1[20]; struct packed_git *p; }; @@@ -1770,15 -1763,6 +1770,6 @@@ extern const char *excludes_file int decode_85(char *dst, const char *line, int linelen); void encode_85(char *buf, const unsigned char *data, int bytes); - /* alloc.c */ - extern void *alloc_blob_node(void); - extern void *alloc_tree_node(void); - extern void *alloc_commit_node(void); - extern void *alloc_tag_node(void); - extern void *alloc_object_node(void); - extern void alloc_report(void); - extern unsigned int alloc_commit_index(void); - /* pkt-line.c */ void packet_trace_identity(const char *prog); @@@ -1826,6 -1810,11 +1817,6 @@@ extern int ws_blank_line(const char *li void overlay_tree_on_index(struct index_state *istate, const char *tree_name, const char *prefix); -char *alias_lookup(const char *alias); -int split_cmdline(char *cmdline, const char ***argv); -/* Takes a negative value returned by split_cmdline */ -const char *split_cmdline_strerror(int cmdline_errno); - /* setup.c */ struct startup_info { int have_repository; diff --combined commit.c index 298ad747c6,5eb4d2f08f..0c3b75aeff --- a/commit.c +++ b/commit.c @@@ -1,19 -1,18 +1,20 @@@ #include "cache.h" #include "tag.h" #include "commit.h" +#include "commit-graph.h" #include "pkt-line.h" #include "utf8.h" #include "diff.h" #include "revision.h" #include "notes.h" + #include "alloc.h" #include "gpg-interface.h" #include "mergesort.h" #include "commit-slab.h" #include "prio-queue.h" #include "sha1-lookup.h" #include "wt-status.h" +#include "advice.h" static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **); @@@ -52,7 -51,8 +53,8 @@@ struct commit *lookup_commit(const stru { struct object *obj = lookup_object(oid->hash); if (!obj) - return create_object(oid->hash, alloc_commit_node()); + return create_object(the_repository, oid->hash, + alloc_commit_node(the_repository)); return object_as_type(obj, OBJ_COMMIT, 0); } @@@ -178,15 -178,6 +180,15 @@@ static int read_graft_file(const char * struct strbuf buf = STRBUF_INIT; if (!fp) return -1; + if (advice_graft_file_deprecated) + advise(_("Support for /info/grafts is deprecated\n" + "and will be removed in a future Git version.\n" + "\n" + "Please use \"git replace --convert-graft-file\"\n" + "to convert the grafts into replace refs.\n" + "\n" + "Turn this message off by running\n" + "\"git config advice.graftFileDeprecated false\"")); while (!strbuf_getwholeline(&buf, fp, '\n')) { /* The format is just "Commit Parent1 Parent2 ...\n" */ struct commit_graft *graft = read_graft_line(&buf); @@@ -207,9 -198,6 +209,9 @@@ static void prepare_commit_graft(void if (commit_graft_prepared) return; + if (!startup_info->have_repository) + return; + graft_file = get_graft_file(); read_graft_file(graft_file); /* make sure shallows are read */ @@@ -309,22 -297,17 +311,33 @@@ void free_commit_buffer(struct commit * } } +struct tree *get_commit_tree(const struct commit *commit) +{ + if (commit->maybe_tree || !commit->object.parsed) + return commit->maybe_tree; + + if (commit->graph_pos == COMMIT_NOT_FROM_GRAPH) + BUG("commit has NULL tree, but was not loaded from commit-graph"); + + return get_commit_tree_in_graph(commit); +} + +struct object_id *get_commit_tree_oid(const struct commit *commit) +{ + return &get_commit_tree(commit)->object.oid; +} + + void release_commit_memory(struct commit *c) + { - c->tree = NULL; ++ c->maybe_tree = NULL; + c->index = 0; + free_commit_buffer(c); + free_commit_list(c->parents); + /* TODO: what about commit->util? */ + + c->object.parsed = 0; + } + const void *detach_commit_buffer(struct commit *commit, unsigned long *sizep) { struct commit_buffer *v = buffer_slab_peek(&buffer_slab, commit); @@@ -344,7 -327,7 +357,7 @@@ return ret; } -int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long size) +int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long size, int check_graph) { const char *tail = buffer; const char *bufptr = buffer; @@@ -361,10 -344,10 +374,10 @@@ if (tail <= bufptr + tree_entry_len + 1 || memcmp(bufptr, "tree ", 5) || bufptr[tree_entry_len] != '\n') return error("bogus commit object %s", oid_to_hex(&item->object.oid)); - if (get_sha1_hex(bufptr + 5, parent.hash) < 0) + if (get_oid_hex(bufptr + 5, &parent) < 0) return error("bad tree pointer in commit %s", oid_to_hex(&item->object.oid)); - item->tree = lookup_tree(&parent); + item->maybe_tree = lookup_tree(&parent); bufptr += tree_entry_len + 1; /* "tree " + "hex sha1" + "\n" */ pptr = &item->parents; @@@ -373,7 -356,7 +386,7 @@@ struct commit *new_parent; if (tail <= bufptr + parent_entry_len + 1 || - get_sha1_hex(bufptr + 7, parent.hash) || + get_oid_hex(bufptr + 7, &parent) || bufptr[parent_entry_len] != '\n') return error("bad parents in commit %s", oid_to_hex(&item->object.oid)); bufptr += parent_entry_len + 1; @@@ -399,9 -382,6 +412,9 @@@ } item->date = parse_commit_date(bufptr, tail); + if (check_graph) + load_commit_graph_info(item); + return 0; } @@@ -416,8 -396,6 +429,8 @@@ int parse_commit_gently(struct commit * return -1; if (item->object.parsed) return 0; + if (parse_commit_in_graph(item)) + return 0; buffer = read_object_file(&item->object.oid, &type, &size); if (!buffer) return quiet_on_missing ? -1 : @@@ -428,7 -406,7 +441,7 @@@ return error("Object %s not a commit", oid_to_hex(&item->object.oid)); } - ret = parse_commit_buffer(item, buffer, size); + ret = parse_commit_buffer(item, buffer, size, 0); if (save_commit_buffer && !ret) { set_commit_buffer(item, buffer, size); return 0; @@@ -656,24 -634,6 +669,24 @@@ static int compare_commits_by_author_da return 0; } +int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused) +{ + const struct commit *a = a_, *b = b_; + + /* newer commits first */ + if (a->generation < b->generation) + return 1; + else if (a->generation > b->generation) + return -1; + + /* use date as a heuristic when generations are equal */ + if (a->date < b->date) + return 1; + else if (a->date > b->date) + return -1; + return 0; +} + int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused) { const struct commit *a = a_, *b = b_; @@@ -821,14 -781,11 +834,14 @@@ static int queue_has_nonstale(struct pr } /* all input commits in one and twos[] must have been parsed! */ -static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos) +static struct commit_list *paint_down_to_common(struct commit *one, int n, + struct commit **twos, + int min_generation) { - struct prio_queue queue = { compare_commits_by_commit_date }; + struct prio_queue queue = { compare_commits_by_gen_then_commit_date }; struct commit_list *result = NULL; int i; + uint32_t last_gen = GENERATION_NUMBER_INFINITY; one->object.flags |= PARENT1; if (!n) { @@@ -847,15 -804,6 +860,15 @@@ struct commit_list *parents; int flags; + if (commit->generation > last_gen) + BUG("bad generation skip %8x > %8x at %s", + commit->generation, last_gen, + oid_to_hex(&commit->object.oid)); + last_gen = commit->generation; + + if (commit->generation < min_generation) + break; + flags = commit->object.flags & (PARENT1 | PARENT2 | STALE); if (flags == (PARENT1 | PARENT2)) { if (!(commit->object.flags & RESULT)) { @@@ -904,7 -852,7 +917,7 @@@ static struct commit_list *merge_bases_ return NULL; } - list = paint_down_to_common(one, n, twos); + list = paint_down_to_common(one, n, twos, 0); while (list) { struct commit *commit = pop_commit(&list); @@@ -962,7 -910,6 +975,7 @@@ static int remove_redundant(struct comm parse_commit(array[i]); for (i = 0; i < cnt; i++) { struct commit_list *common; + uint32_t min_generation = array[i]->generation; if (redundant[i]) continue; @@@ -971,12 -918,8 +984,12 @@@ continue; filled_index[filled] = j; work[filled++] = array[j]; + + if (array[j]->generation < min_generation) + min_generation = array[j]->generation; } - common = paint_down_to_common(array[i], filled, work); + common = paint_down_to_common(array[i], filled, work, + min_generation); if (array[i]->object.flags & PARENT2) redundant[i] = 1; for (j = 0; j < filled; j++) @@@ -1086,21 -1029,14 +1099,21 @@@ int in_merge_bases_many(struct commit * { struct commit_list *bases; int ret = 0, i; + uint32_t min_generation = GENERATION_NUMBER_INFINITY; if (parse_commit(commit)) return ret; - for (i = 0; i < nr_reference; i++) + for (i = 0; i < nr_reference; i++) { if (parse_commit(reference[i])) return ret; + if (reference[i]->generation < min_generation) + min_generation = reference[i]->generation; + } + + if (commit->generation > min_generation) + return ret; - bases = paint_down_to_common(commit, nr_reference, reference); + bases = paint_down_to_common(commit, nr_reference, reference, commit->generation); if (commit->object.flags & PARENT2) ret = 1; clear_commit_marks(commit, all_flags); @@@ -1365,19 -1301,17 +1378,19 @@@ struct commit_extra_header *read_commit return extra; } -void for_each_mergetag(each_mergetag_fn fn, struct commit *commit, void *data) +int for_each_mergetag(each_mergetag_fn fn, struct commit *commit, void *data) { struct commit_extra_header *extra, *to_free; + int res = 0; to_free = read_commit_extra_headers(commit, NULL); - for (extra = to_free; extra; extra = extra->next) { + for (extra = to_free; !res && extra; extra = extra->next) { if (strcmp(extra->key, "mergetag")) continue; /* not a merge tag */ - fn(commit, extra, data); + res = fn(commit, extra, data); } free_commit_extra_headers(to_free); + return res; } static inline int standard_header_field(const char *field, size_t len) @@@ -1650,21 -1584,13 +1663,21 @@@ out return result; } +define_commit_slab(merge_desc_slab, struct merge_remote_desc *); +static struct merge_desc_slab merge_desc_slab = COMMIT_SLAB_INIT(1, merge_desc_slab); + +struct merge_remote_desc *merge_remote_util(struct commit *commit) +{ + return *merge_desc_slab_at(&merge_desc_slab, commit); +} + void set_merge_remote_desc(struct commit *commit, const char *name, struct object *obj) { struct merge_remote_desc *desc; FLEX_ALLOC_STR(desc, name, name); desc->obj = obj; - commit->util = desc; + *merge_desc_slab_at(&merge_desc_slab, commit) = desc; } struct commit *get_merge_parent(const char *name) @@@ -1676,7 -1602,7 +1689,7 @@@ return NULL; obj = parse_object(&oid); commit = (struct commit *)peel_to_type(name, 0, obj, OBJ_COMMIT); - if (commit && !commit->util) + if (commit && !merge_remote_util(commit)) set_merge_remote_desc(commit, name, obj); return commit; } diff --combined commit.h index cb943013d0,2d764ab7d8..3ad07c2e3d --- a/commit.h +++ b/commit.h @@@ -9,35 -9,18 +9,35 @@@ #include "string-list.h" #include "pretty.h" +#define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF +#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF +#define GENERATION_NUMBER_MAX 0x3FFFFFFF +#define GENERATION_NUMBER_ZERO 0 + struct commit_list { struct commit *item; struct commit_list *next; }; +/* + * The size of this struct matters in full repo walk operations like + * 'git clone' or 'git gc'. Consider using commit-slab to attach data + * to a commit instead of adding new fields here. + */ struct commit { struct object object; - void *util; - unsigned int index; timestamp_t date; struct commit_list *parents; - struct tree *tree; + + /* + * If the commit is loaded from the commit-graph file, then this + * member may be NULL. Only access it through get_commit_tree() + * or get_commit_tree_oid(). + */ + struct tree *maybe_tree; + uint32_t graph_pos; + uint32_t generation; + unsigned int index; }; extern int save_commit_buffer; @@@ -76,7 -59,7 +76,7 @@@ struct commit *lookup_commit_reference_ */ struct commit *lookup_commit_or_die(const struct object_id *oid, const char *ref_name); -int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long size); +int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long size, int check_graph); int parse_commit_gently(struct commit *item, int quiet_on_missing); static inline int parse_commit(struct commit *item) { @@@ -116,9 -99,12 +116,15 @@@ void unuse_commit_buffer(const struct c */ void free_commit_buffer(struct commit *); +struct tree *get_commit_tree(const struct commit *); +struct object_id *get_commit_tree_oid(const struct commit *); + + /* + * Release memory related to a commit, including the parent list and + * any cached object buffer. + */ + void release_commit_memory(struct commit *c); + /* * Disassociate any cached object buffer from the commit, but do not free it. * The buffer (or NULL, if none) is returned. @@@ -311,16 -297,16 +317,16 @@@ extern const char *find_commit_header(c /* Find the end of the log message, the right place for a new trailer. */ extern int ignore_non_trailer(const char *buf, size_t len); -typedef void (*each_mergetag_fn)(struct commit *commit, struct commit_extra_header *extra, +typedef int (*each_mergetag_fn)(struct commit *commit, struct commit_extra_header *extra, void *cb_data); -extern void for_each_mergetag(each_mergetag_fn fn, struct commit *commit, void *data); +extern int for_each_mergetag(each_mergetag_fn fn, struct commit *commit, void *data); struct merge_remote_desc { struct object *obj; /* the named object, could be a tag */ char name[FLEX_ARRAY]; }; -#define merge_remote_util(commit) ((struct merge_remote_desc *)((commit)->util)) +extern struct merge_remote_desc *merge_remote_util(struct commit *); extern void set_merge_remote_desc(struct commit *commit, const char *name, struct object *obj); @@@ -345,7 -331,6 +351,7 @@@ extern int remove_signature(struct strb extern int check_commit_signature(const struct commit *commit, struct signature_check *sigc); int compare_commits_by_commit_date(const void *a_, const void *b_, void *unused); +int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused); LAST_ARG_MUST_BE_NULL extern int run_commit_hook(int editor_is_used, const char *index_file, const char *name, ...); diff --combined merge-recursive.c index 404f050caf,cbded673c2..bed4a5be02 --- a/merge-recursive.c +++ b/merge-recursive.c @@@ -15,6 -15,7 +15,7 @@@ #include "diff.h" #include "diffcore.h" #include "tag.h" + #include "alloc.h" #include "unpack-trees.h" #include "string-list.h" #include "xdiff-interface.h" @@@ -23,7 -24,6 +24,7 @@@ #include "merge-recursive.h" #include "dir.h" #include "submodule.h" +#include "revision.h" struct path_hashmap_entry { struct hashmap_entry e; @@@ -50,67 -50,6 +51,67 @@@ static unsigned int path_hash(const cha return ignore_case ? strihash(path) : strhash(path); } +static struct dir_rename_entry *dir_rename_find_entry(struct hashmap *hashmap, + char *dir) +{ + struct dir_rename_entry key; + + if (dir == NULL) + return NULL; + hashmap_entry_init(&key, strhash(dir)); + key.dir = dir; + return hashmap_get(hashmap, &key, NULL); +} + +static int dir_rename_cmp(const void *unused_cmp_data, + const void *entry, + const void *entry_or_key, + const void *unused_keydata) +{ + const struct dir_rename_entry *e1 = entry; + const struct dir_rename_entry *e2 = entry_or_key; + + return strcmp(e1->dir, e2->dir); +} + +static void dir_rename_init(struct hashmap *map) +{ + hashmap_init(map, dir_rename_cmp, NULL, 0); +} + +static void dir_rename_entry_init(struct dir_rename_entry *entry, + char *directory) +{ + hashmap_entry_init(entry, strhash(directory)); + entry->dir = directory; + entry->non_unique_new_dir = 0; + strbuf_init(&entry->new_dir, 0); + string_list_init(&entry->possible_new_dirs, 0); +} + +static struct collision_entry *collision_find_entry(struct hashmap *hashmap, + char *target_file) +{ + struct collision_entry key; + + hashmap_entry_init(&key, strhash(target_file)); + key.target_file = target_file; + return hashmap_get(hashmap, &key, NULL); +} + +static int collision_cmp(void *unused_cmp_data, + const struct collision_entry *e1, + const struct collision_entry *e2, + const void *unused_keydata) +{ + return strcmp(e1->target_file, e2->target_file); +} + +static void collision_init(struct hashmap *map) +{ + hashmap_init(map, (hashmap_cmp_fn) collision_cmp, NULL, 0); +} + static void flush_output(struct merge_options *o) { if (o->buffer_output < 2 && o->obuf.len) { @@@ -160,10 -99,10 +161,10 @@@ static struct tree *shift_tree_object(s static struct commit *make_virtual_commit(struct tree *tree, const char *comment) { - struct commit *commit = alloc_commit_node(); + struct commit *commit = alloc_commit_node(the_repository); set_merge_remote_desc(commit, comment, (struct object *)commit); - commit->tree = tree; + commit->maybe_tree = tree; commit->object.parsed = 1; return commit; } @@@ -181,7 -120,6 +182,7 @@@ static int oid_eq(const struct object_i enum rename_type { RENAME_NORMAL = 0, + RENAME_DIR, RENAME_DELETE, RENAME_ONE_FILE_TO_ONE, RENAME_ONE_FILE_TO_TWO, @@@ -286,12 -224,10 +287,12 @@@ static void output(struct merge_option static void output_commit_title(struct merge_options *o, struct commit *commit) { + struct merge_remote_desc *desc; + strbuf_addchars(&o->obuf, ' ', o->call_depth * 2); - if (commit->util) - strbuf_addf(&o->obuf, "virtual %s\n", - merge_remote_util(commit)->name); + desc = merge_remote_util(commit); + if (desc) + strbuf_addf(&o->obuf, "virtual %s\n", desc->name); else { strbuf_add_unique_abbrev(&o->obuf, &commit->object.oid, DEFAULT_ABBREV); @@@ -319,7 -255,7 +320,7 @@@ static int add_cacheinfo(struct merge_o ce = make_cache_entry(mode, oid ? oid->hash : null_sha1, path, stage, 0); if (!ce) - return err(o, _("addinfo_cache failed for path '%s'"), path); + return err(o, _("add_cacheinfo failed for path '%s'; merge aborting."), path); ret = add_cache_entry(ce, options); if (refresh) { @@@ -327,7 -263,7 +328,7 @@@ nce = refresh_cache_entry(ce, CE_MATCH_REFRESH | CE_MATCH_IGNORE_MISSING); if (!nce) - return err(o, _("addinfo_cache failed for path '%s'"), path); + return err(o, _("add_cacheinfo failed to refresh for path '%s'; merge aborting."), path); if (nce != ce) ret = add_cache_entry(nce, options); } @@@ -340,54 -276,36 +341,54 @@@ static void init_tree_desc_from_tree(st init_tree_desc(desc, tree->buffer, tree->size); } -static int git_merge_trees(int index_only, - struct tree *common, - struct tree *head, - struct tree *merge) +static int unpack_trees_start(struct merge_options *o, + struct tree *common, + struct tree *head, + struct tree *merge) { int rc; struct tree_desc t[3]; - struct unpack_trees_options opts; + struct index_state tmp_index = { NULL }; - memset(&opts, 0, sizeof(opts)); - if (index_only) - opts.index_only = 1; + memset(&o->unpack_opts, 0, sizeof(o->unpack_opts)); + if (o->call_depth) + o->unpack_opts.index_only = 1; else - opts.update = 1; - opts.merge = 1; - opts.head_idx = 2; - opts.fn = threeway_merge; - opts.src_index = &the_index; - opts.dst_index = &the_index; - setup_unpack_trees_porcelain(&opts, "merge"); + o->unpack_opts.update = 1; + o->unpack_opts.merge = 1; + o->unpack_opts.head_idx = 2; + o->unpack_opts.fn = threeway_merge; + o->unpack_opts.src_index = &the_index; + o->unpack_opts.dst_index = &tmp_index; + o->unpack_opts.aggressive = !merge_detect_rename(o); + setup_unpack_trees_porcelain(&o->unpack_opts, "merge"); init_tree_desc_from_tree(t+0, common); init_tree_desc_from_tree(t+1, head); init_tree_desc_from_tree(t+2, merge); - rc = unpack_trees(3, t, &opts); + rc = unpack_trees(3, t, &o->unpack_opts); cache_tree_free(&active_cache_tree); + + /* + * Update the_index to match the new results, AFTER saving a copy + * in o->orig_index. Update src_index to point to the saved copy. + * (verify_uptodate() checks src_index, and the original index is + * the one that had the necessary modification timestamps.) + */ + o->orig_index = the_index; + the_index = tmp_index; + o->unpack_opts.src_index = &o->orig_index; + return rc; } +static void unpack_trees_finish(struct merge_options *o) +{ + discard_index(&o->orig_index); + clear_unpack_trees_porcelain(&o->unpack_opts); +} + struct tree *write_tree_from_memory(struct merge_options *o) { struct tree *result = NULL; @@@ -401,7 -319,7 +402,7 @@@ fprintf(stderr, "BUG: %d %.*s\n", ce_stage(ce), (int)ce_namelen(ce), ce->name); } - die("BUG: unmerged index entries in merge-recursive.c"); + BUG("unmerged index entries in merge-recursive.c"); } if (!active_cache_tree) @@@ -443,21 -361,6 +444,21 @@@ static void get_files_dirs(struct merge read_tree_recursive(tree, "", 0, 0, &match_all, save_files_dirs, o); } +static int get_tree_entry_if_blob(const struct object_id *tree, + const char *path, + struct object_id *hashy, + unsigned int *mode_o) +{ + int ret; + + ret = get_tree_entry(tree, path, hashy, mode_o); + if (S_ISDIR(*mode_o)) { + oidcpy(hashy, &null_oid); + *mode_o = 0; + } + return ret; +} + /* * Returns an index_entry instance which doesn't have to correspond to * a real cache entry in Git's index. @@@ -468,12 -371,12 +469,12 @@@ static struct stage_data *insert_stage_ { struct string_list_item *item; struct stage_data *e = xcalloc(1, sizeof(struct stage_data)); - get_tree_entry(&o->object.oid, path, - &e->stages[1].oid, &e->stages[1].mode); - get_tree_entry(&a->object.oid, path, - &e->stages[2].oid, &e->stages[2].mode); - get_tree_entry(&b->object.oid, path, - &e->stages[3].oid, &e->stages[3].mode); + get_tree_entry_if_blob(&o->object.oid, path, + &e->stages[1].oid, &e->stages[1].mode); + get_tree_entry_if_blob(&a->object.oid, path, + &e->stages[2].oid, &e->stages[2].mode); + get_tree_entry_if_blob(&b->object.oid, path, + &e->stages[3].oid, &e->stages[3].mode); item = string_list_insert(entries, path); item->util = e; return e; @@@ -632,10 -535,78 +633,10 @@@ struct rename */ struct stage_data *src_entry; struct stage_data *dst_entry; + unsigned add_turned_into_rename:1; unsigned processed:1; }; -/* - * Get information of all renames which occurred between 'o_tree' and - * 'tree'. We need the three trees in the merge ('o_tree', 'a_tree' and - * 'b_tree') to be able to associate the correct cache entries with - * the rename information. 'tree' is always equal to either a_tree or b_tree. - */ -static struct string_list *get_renames(struct merge_options *o, - struct tree *tree, - struct tree *o_tree, - struct tree *a_tree, - struct tree *b_tree, - struct string_list *entries) -{ - int i; - struct string_list *renames; - struct diff_options opts; - - renames = xcalloc(1, sizeof(struct string_list)); - if (!o->detect_rename) - return renames; - - diff_setup(&opts); - opts.flags.recursive = 1; - opts.flags.rename_empty = 0; - opts.detect_rename = DIFF_DETECT_RENAME; - opts.rename_limit = o->merge_rename_limit >= 0 ? o->merge_rename_limit : - o->diff_rename_limit >= 0 ? o->diff_rename_limit : - 1000; - opts.rename_score = o->rename_score; - opts.show_rename_progress = o->show_rename_progress; - opts.output_format = DIFF_FORMAT_NO_OUTPUT; - diff_setup_done(&opts); - diff_tree_oid(&o_tree->object.oid, &tree->object.oid, "", &opts); - diffcore_std(&opts); - if (opts.needed_rename_limit > o->needed_rename_limit) - o->needed_rename_limit = opts.needed_rename_limit; - for (i = 0; i < diff_queued_diff.nr; ++i) { - struct string_list_item *item; - struct rename *re; - struct diff_filepair *pair = diff_queued_diff.queue[i]; - if (pair->status != 'R') { - diff_free_filepair(pair); - continue; - } - re = xmalloc(sizeof(*re)); - re->processed = 0; - re->pair = pair; - item = string_list_lookup(entries, re->pair->one->path); - if (!item) - re->src_entry = insert_stage_data(re->pair->one->path, - o_tree, a_tree, b_tree, entries); - else - re->src_entry = item->util; - - item = string_list_lookup(entries, re->pair->two->path); - if (!item) - re->dst_entry = insert_stage_data(re->pair->two->path, - o_tree, a_tree, b_tree, entries); - else - re->dst_entry = item->util; - item = string_list_insert(renames, pair->one->path); - item->util = re; - } - opts.output_format = DIFF_FORMAT_NO_OUTPUT; - diff_queued_diff.nr = 0; - diff_flush(&opts); - return renames; -} - static int update_stages(struct merge_options *opt, const char *path, const struct diff_filespec *o, const struct diff_filespec *a, @@@ -667,27 -638,6 +668,27 @@@ return 0; } +static int update_stages_for_stage_data(struct merge_options *opt, + const char *path, + const struct stage_data *stage_data) +{ + struct diff_filespec o, a, b; + + o.mode = stage_data->stages[1].mode; + oidcpy(&o.oid, &stage_data->stages[1].oid); + + a.mode = stage_data->stages[2].mode; + oidcpy(&a.oid, &stage_data->stages[2].oid); + + b.mode = stage_data->stages[3].mode; + oidcpy(&b.oid, &stage_data->stages[3].oid); + + return update_stages(opt, path, + is_null_oid(&o.oid) ? NULL : &o, + is_null_oid(&a.oid) ? NULL : &a, + is_null_oid(&b.oid) ? NULL : &b); +} + static void update_entry(struct stage_data *entry, struct diff_filespec *o, struct diff_filespec *a, @@@ -789,92 -739,31 +790,92 @@@ static int dir_in_way(const char *path !(empty_ok && is_empty_dir(path)); } -static int was_tracked(const char *path) +/* + * Returns whether path was tracked in the index before the merge started, + * and its oid and mode match the specified values + */ +static int was_tracked_and_matches(struct merge_options *o, const char *path, + const struct object_id *oid, unsigned mode) { - int pos = cache_name_pos(path, strlen(path)); + int pos = index_name_pos(&o->orig_index, path, strlen(path)); + struct cache_entry *ce; + + if (0 > pos) + /* we were not tracking this path before the merge */ + return 0; + + /* See if the file we were tracking before matches */ + ce = o->orig_index.cache[pos]; + return (oid_eq(&ce->oid, oid) && ce->ce_mode == mode); +} + +/* + * Returns whether path was tracked in the index before the merge started + */ +static int was_tracked(struct merge_options *o, const char *path) +{ + int pos = index_name_pos(&o->orig_index, path, strlen(path)); if (0 <= pos) - /* we have been tracking this path */ + /* we were tracking this path before the merge */ return 1; - /* - * Look for an unmerged entry for the path, - * specifically stage #2, which would indicate - * that "our" side before the merge started - * had the path tracked (and resulted in a conflict). - */ - for (pos = -1 - pos; - pos < active_nr && !strcmp(path, active_cache[pos]->name); - pos++) - if (ce_stage(active_cache[pos]) == 2) - return 1; return 0; } static int would_lose_untracked(const char *path) { - return !was_tracked(path) && file_exists(path); + /* + * This may look like it can be simplified to: + * return !was_tracked(o, path) && file_exists(path) + * but it can't. This function needs to know whether path was in + * the working tree due to EITHER having been tracked in the index + * before the merge OR having been put into the working copy and + * index by unpack_trees(). Due to that either-or requirement, we + * check the current index instead of the original one. + * + * Note that we do not need to worry about merge-recursive itself + * updating the index after unpack_trees() and before calling this + * function, because we strictly require all code paths in + * merge-recursive to update the working tree first and the index + * second. Doing otherwise would break + * update_file()/would_lose_untracked(); see every comment in this + * file which mentions "update_stages". + */ + int pos = cache_name_pos(path, strlen(path)); + + if (pos < 0) + pos = -1 - pos; + while (pos < active_nr && + !strcmp(path, active_cache[pos]->name)) { + /* + * If stage #0, it is definitely tracked. + * If it has stage #2 then it was tracked + * before this merge started. All other + * cases the path was not tracked. + */ + switch (ce_stage(active_cache[pos])) { + case 0: + case 2: + return 0; + } + pos++; + } + return file_exists(path); +} + +static int was_dirty(struct merge_options *o, const char *path) +{ + struct cache_entry *ce; + int dirty = 1; + + if (o->call_depth || !was_tracked(o, path)) + return !dirty; + + ce = index_file_exists(o->unpack_opts.src_index, + path, strlen(path), ignore_case); + dirty = verify_uptodate(ce, &o->unpack_opts) != 0; + return dirty; } static int make_room_for_path(struct merge_options *o, const char *path) @@@ -1005,9 -894,7 +1006,9 @@@ static int update_file_flags(struct mer } update_index: if (!ret && update_cache) - add_cacheinfo(o, mode, oid, path, 0, update_wd, ADD_CACHE_OK_TO_ADD); + if (add_cacheinfo(o, mode, oid, path, 0, update_wd, + ADD_CACHE_OK_TO_ADD)) + return -1; return ret; } @@@ -1091,193 -978,13 +1092,193 @@@ static int merge_3way(struct merge_opti return merge_status; } +static int find_first_merges(struct object_array *result, const char *path, + struct commit *a, struct commit *b) +{ + int i, j; + struct object_array merges = OBJECT_ARRAY_INIT; + struct commit *commit; + int contains_another; + + char merged_revision[42]; + const char *rev_args[] = { "rev-list", "--merges", "--ancestry-path", + "--all", merged_revision, NULL }; + struct rev_info revs; + struct setup_revision_opt rev_opts; + + memset(result, 0, sizeof(struct object_array)); + memset(&rev_opts, 0, sizeof(rev_opts)); + + /* get all revisions that merge commit a */ + xsnprintf(merged_revision, sizeof(merged_revision), "^%s", + oid_to_hex(&a->object.oid)); + init_revisions(&revs, NULL); + rev_opts.submodule = path; + /* FIXME: can't handle linked worktrees in submodules yet */ + revs.single_worktree = path != NULL; + setup_revisions(ARRAY_SIZE(rev_args)-1, rev_args, &revs, &rev_opts); + + /* save all revisions from the above list that contain b */ + if (prepare_revision_walk(&revs)) + die("revision walk setup failed"); + while ((commit = get_revision(&revs)) != NULL) { + struct object *o = &(commit->object); + if (in_merge_bases(b, commit)) + add_object_array(o, NULL, &merges); + } + reset_revision_walk(); + + /* Now we've got all merges that contain a and b. Prune all + * merges that contain another found merge and save them in + * result. + */ + for (i = 0; i < merges.nr; i++) { + struct commit *m1 = (struct commit *) merges.objects[i].item; + + contains_another = 0; + for (j = 0; j < merges.nr; j++) { + struct commit *m2 = (struct commit *) merges.objects[j].item; + if (i != j && in_merge_bases(m2, m1)) { + contains_another = 1; + break; + } + } + + if (!contains_another) + add_object_array(merges.objects[i].item, NULL, result); + } + + object_array_clear(&merges); + return result->nr; +} + +static void print_commit(struct commit *commit) +{ + struct strbuf sb = STRBUF_INIT; + struct pretty_print_context ctx = {0}; + ctx.date_mode.type = DATE_NORMAL; + format_commit_message(commit, " %h: %m %s", &sb, &ctx); + fprintf(stderr, "%s\n", sb.buf); + strbuf_release(&sb); +} + +static int merge_submodule(struct merge_options *o, + struct object_id *result, const char *path, + const struct object_id *base, const struct object_id *a, + const struct object_id *b) +{ + struct commit *commit_base, *commit_a, *commit_b; + int parent_count; + struct object_array merges; + + int i; + int search = !o->call_depth; + + /* store a in result in case we fail */ + oidcpy(result, a); + + /* we can not handle deletion conflicts */ + if (is_null_oid(base)) + return 0; + if (is_null_oid(a)) + return 0; + if (is_null_oid(b)) + return 0; + + if (add_submodule_odb(path)) { + output(o, 1, _("Failed to merge submodule %s (not checked out)"), path); + return 0; + } + + if (!(commit_base = lookup_commit_reference(base)) || + !(commit_a = lookup_commit_reference(a)) || + !(commit_b = lookup_commit_reference(b))) { + output(o, 1, _("Failed to merge submodule %s (commits not present)"), path); + return 0; + } + + /* check whether both changes are forward */ + if (!in_merge_bases(commit_base, commit_a) || + !in_merge_bases(commit_base, commit_b)) { + output(o, 1, _("Failed to merge submodule %s (commits don't follow merge-base)"), path); + return 0; + } + + /* Case #1: a is contained in b or vice versa */ + if (in_merge_bases(commit_a, commit_b)) { + oidcpy(result, b); + if (show(o, 3)) { + output(o, 3, _("Fast-forwarding submodule %s to the following commit:"), path); + output_commit_title(o, commit_b); + } else if (show(o, 2)) + output(o, 2, _("Fast-forwarding submodule %s"), path); + else + ; /* no output */ + + return 1; + } + if (in_merge_bases(commit_b, commit_a)) { + oidcpy(result, a); + if (show(o, 3)) { + output(o, 3, _("Fast-forwarding submodule %s to the following commit:"), path); + output_commit_title(o, commit_a); + } else if (show(o, 2)) + output(o, 2, _("Fast-forwarding submodule %s"), path); + else + ; /* no output */ + + return 1; + } + + /* + * Case #2: There are one or more merges that contain a and b in + * the submodule. If there is only one, then present it as a + * suggestion to the user, but leave it marked unmerged so the + * user needs to confirm the resolution. + */ + + /* Skip the search if makes no sense to the calling context. */ + if (!search) + return 0; + + /* find commit which merges them */ + parent_count = find_first_merges(&merges, path, commit_a, commit_b); + switch (parent_count) { + case 0: + output(o, 1, _("Failed to merge submodule %s (merge following commits not found)"), path); + break; + + case 1: + output(o, 1, _("Failed to merge submodule %s (not fast-forward)"), path); + output(o, 2, _("Found a possible merge resolution for the submodule:\n")); + print_commit((struct commit *) merges.objects[0].item); + output(o, 2, _( + "If this is correct simply add it to the index " + "for example\n" + "by using:\n\n" + " git update-index --cacheinfo 160000 %s \"%s\"\n\n" + "which will accept this suggestion.\n"), + oid_to_hex(&merges.objects[0].item->oid), path); + break; + + default: + output(o, 1, _("Failed to merge submodule %s (multiple merges found)"), path); + for (i = 0; i < merges.nr; i++) + print_commit((struct commit *) merges.objects[i].item); + } + + object_array_clear(&merges); + return 0; +} + static int merge_file_1(struct merge_options *o, - const struct diff_filespec *one, - const struct diff_filespec *a, - const struct diff_filespec *b, - const char *branch1, - const char *branch2, - struct merge_file_info *result) + const struct diff_filespec *one, + const struct diff_filespec *a, + const struct diff_filespec *b, + const char *filename, + const char *branch1, + const char *branch2, + struct merge_file_info *result) { result->merge = 0; result->clean = 1; @@@ -1333,11 -1040,12 +1334,11 @@@ return ret; result->clean = (merge_status == 0); } else if (S_ISGITLINK(a->mode)) { - result->clean = merge_submodule(&result->oid, + result->clean = merge_submodule(o, &result->oid, one->path, &one->oid, &a->oid, - &b->oid, - !o->call_depth); + &b->oid); } else if (S_ISLNK(a->mode)) { switch (o->recursive_variant) { case MERGE_RECURSIVE_NORMAL: @@@ -1353,25 -1061,21 +1354,25 @@@ break; } } else - die("BUG: unsupported object type in the tree"); + BUG("unsupported object type in the tree"); } + if (result->merge) + output(o, 2, _("Auto-merging %s"), filename); + return 0; } static int merge_file_special_markers(struct merge_options *o, - const struct diff_filespec *one, - const struct diff_filespec *a, - const struct diff_filespec *b, - const char *branch1, - const char *filename1, - const char *branch2, - const char *filename2, - struct merge_file_info *mfi) + const struct diff_filespec *one, + const struct diff_filespec *a, + const struct diff_filespec *b, + const char *target_filename, + const char *branch1, + const char *filename1, + const char *branch2, + const char *filename2, + struct merge_file_info *mfi) { char *side1 = NULL; char *side2 = NULL; @@@ -1382,23 -1086,22 +1383,23 @@@ if (filename2) side2 = xstrfmt("%s:%s", branch2, filename2); - ret = merge_file_1(o, one, a, b, + ret = merge_file_1(o, one, a, b, target_filename, side1 ? side1 : branch1, side2 ? side2 : branch2, mfi); + free(side1); free(side2); return ret; } static int merge_file_one(struct merge_options *o, - const char *path, - const struct object_id *o_oid, int o_mode, - const struct object_id *a_oid, int a_mode, - const struct object_id *b_oid, int b_mode, - const char *branch1, - const char *branch2, - struct merge_file_info *mfi) + const char *path, + const struct object_id *o_oid, int o_mode, + const struct object_id *a_oid, int a_mode, + const struct object_id *b_oid, int b_mode, + const char *branch1, + const char *branch2, + struct merge_file_info *mfi) { struct diff_filespec one, a, b; @@@ -1409,39 -1112,7 +1410,39 @@@ a.mode = a_mode; oidcpy(&b.oid, b_oid); b.mode = b_mode; - return merge_file_1(o, &one, &a, &b, branch1, branch2, mfi); + return merge_file_1(o, &one, &a, &b, path, branch1, branch2, mfi); +} + +static int conflict_rename_dir(struct merge_options *o, + struct diff_filepair *pair, + const char *rename_branch, + const char *other_branch) +{ + const struct diff_filespec *dest = pair->two; + + if (!o->call_depth && would_lose_untracked(dest->path)) { + char *alt_path = unique_path(o, dest->path, rename_branch); + + output(o, 1, _("Error: Refusing to lose untracked file at %s; " + "writing to %s instead."), + dest->path, alt_path); + /* + * Write the file in worktree at alt_path, but not in the + * index. Instead, write to dest->path for the index but + * only at the higher appropriate stage. + */ + if (update_file(o, 0, &dest->oid, dest->mode, alt_path)) + return -1; + free(alt_path); + return update_stages(o, dest->path, NULL, + rename_branch == o->branch1 ? dest : NULL, + rename_branch == o->branch1 ? NULL : dest); + } + + /* Update dest->path both in index and in worktree */ + if (update_file(o, 1, &dest->oid, dest->mode, dest->path)) + return -1; + return 0; } static int handle_change_delete(struct merge_options *o, @@@ -1457,8 -1128,7 +1458,8 @@@ const char *update_path = path; int ret = 0; - if (dir_in_way(path, !o->call_depth, 0)) { + if (dir_in_way(path, !o->call_depth, 0) || + (!o->call_depth && would_lose_untracked(path))) { update_path = alt_path = unique_path(o, path, change_branch); } @@@ -1573,34 -1243,17 +1574,34 @@@ static int handle_file(struct merge_opt add = filespec_from_entry(&other, dst_entry, stage ^ 1); if (add) { + int ren_src_was_dirty = was_dirty(o, rename->path); char *add_name = unique_path(o, rename->path, other_branch); if (update_file(o, 0, &add->oid, add->mode, add_name)) return -1; - remove_file(o, 0, rename->path, 0); + if (ren_src_was_dirty) { + output(o, 1, _("Refusing to lose dirty file at %s"), + rename->path); + } + /* + * Because the double negatives somehow keep confusing me... + * 1) update_wd iff !ren_src_was_dirty. + * 2) no_wd iff !update_wd + * 3) so, no_wd == !!ren_src_was_dirty == ren_src_was_dirty + */ + remove_file(o, 0, rename->path, ren_src_was_dirty); dst_name = unique_path(o, rename->path, cur_branch); } else { if (dir_in_way(rename->path, !o->call_depth, 0)) { dst_name = unique_path(o, rename->path, cur_branch); output(o, 1, _("%s is a directory in %s adding as %s instead"), rename->path, other_branch, dst_name); + } else if (!o->call_depth && + would_lose_untracked(rename->path)) { + dst_name = unique_path(o, rename->path, cur_branch); + output(o, 1, _("Refusing to lose untracked file at %s; " + "adding as %s instead"), + rename->path, dst_name); } } if ((ret = update_file(o, 0, &rename->oid, rename->mode, dst_name))) @@@ -1687,8 -1340,6 +1688,8 @@@ static int conflict_rename_rename_2to1( struct diff_filespec *c1 = ci->pair1->two; struct diff_filespec *c2 = ci->pair2->two; char *path = c1->path; /* == c2->path */ + char *path_side_1_desc; + char *path_side_2_desc; struct merge_file_info mfi_c1; struct merge_file_info mfi_c2; int ret; @@@ -1702,19 -1353,13 +1703,19 @@@ remove_file(o, 1, a->path, o->call_depth || would_lose_untracked(a->path)); remove_file(o, 1, b->path, o->call_depth || would_lose_untracked(b->path)); + path_side_1_desc = xstrfmt("%s (was %s)", path, a->path); + path_side_2_desc = xstrfmt("%s (was %s)", path, b->path); if (merge_file_special_markers(o, a, c1, &ci->ren1_other, + path_side_1_desc, o->branch1, c1->path, o->branch2, ci->ren1_other.path, &mfi_c1) || merge_file_special_markers(o, b, &ci->ren2_other, c2, + path_side_2_desc, o->branch1, ci->ren2_other.path, o->branch2, c2->path, &mfi_c2)) return -1; + free(path_side_1_desc); + free(path_side_2_desc); if (o->call_depth) { /* @@@ -1734,43 -1379,11 +1735,43 @@@ char *new_path2 = unique_path(o, path, ci->branch2); output(o, 1, _("Renaming %s to %s and %s to %s instead"), a->path, new_path1, b->path, new_path2); - remove_file(o, 0, path, 0); + if (was_dirty(o, path)) + output(o, 1, _("Refusing to lose dirty file at %s"), + path); + else if (would_lose_untracked(path)) + /* + * Only way we get here is if both renames were from + * a directory rename AND user had an untracked file + * at the location where both files end up after the + * two directory renames. See testcase 10d of t6043. + */ + output(o, 1, _("Refusing to lose untracked file at " + "%s, even though it's in the way."), + path); + else + remove_file(o, 0, path, 0); ret = update_file(o, 0, &mfi_c1.oid, mfi_c1.mode, new_path1); if (!ret) ret = update_file(o, 0, &mfi_c2.oid, mfi_c2.mode, new_path2); + /* + * unpack_trees() actually populates the index for us for + * "normal" rename/rename(2to1) situtations so that the + * correct entries are at the higher stages, which would + * make the call below to update_stages_for_stage_data + * unnecessary. However, if either of the renames came + * from a directory rename, then unpack_trees() will not + * have gotten the right data loaded into the index, so we + * need to do so now. (While it'd be tempting to move this + * call to update_stages_for_stage_data() to + * apply_directory_rename_modifications(), that would break + * our intermediate calls to would_lose_untracked() since + * those rely on the current in-memory index. See also the + * big "NOTE" in update_stages()). + */ + if (update_stages_for_stage_data(o, path, ci->dst_entry1)) + ret = -1; + free(new_path2); free(new_path1); } @@@ -1778,796 -1391,40 +1779,796 @@@ return ret; } -static int process_renames(struct merge_options *o, - struct string_list *a_renames, - struct string_list *b_renames) +/* + * Get the diff_filepairs changed between o_tree and tree. + */ +static struct diff_queue_struct *get_diffpairs(struct merge_options *o, + struct tree *o_tree, + struct tree *tree) { - int clean_merge = 1, i, j; - struct string_list a_by_dst = STRING_LIST_INIT_NODUP; - struct string_list b_by_dst = STRING_LIST_INIT_NODUP; - const struct rename *sre; - - for (i = 0; i < a_renames->nr; i++) { - sre = a_renames->items[i].util; - string_list_insert(&a_by_dst, sre->pair->two->path)->util - = (void *)sre; - } - for (i = 0; i < b_renames->nr; i++) { - sre = b_renames->items[i].util; - string_list_insert(&b_by_dst, sre->pair->two->path)->util - = (void *)sre; - } - - for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) { - struct string_list *renames1, *renames2Dst; - struct rename *ren1 = NULL, *ren2 = NULL; - const char *branch1, *branch2; - const char *ren1_src, *ren1_dst; - struct string_list_item *lookup; + struct diff_queue_struct *ret; + struct diff_options opts; - if (i >= a_renames->nr) { - ren2 = b_renames->items[j++].util; - } else if (j >= b_renames->nr) { - ren1 = a_renames->items[i++].util; - } else { - int compare = strcmp(a_renames->items[i].string, - b_renames->items[j].string); + diff_setup(&opts); + opts.flags.recursive = 1; + opts.flags.rename_empty = 0; + opts.detect_rename = merge_detect_rename(o); + /* + * We do not have logic to handle the detection of copies. In + * fact, it may not even make sense to add such logic: would we + * really want a change to a base file to be propagated through + * multiple other files by a merge? + */ + if (opts.detect_rename > DIFF_DETECT_RENAME) + opts.detect_rename = DIFF_DETECT_RENAME; + opts.rename_limit = o->merge_rename_limit >= 0 ? o->merge_rename_limit : + o->diff_rename_limit >= 0 ? o->diff_rename_limit : + 1000; + opts.rename_score = o->rename_score; + opts.show_rename_progress = o->show_rename_progress; + opts.output_format = DIFF_FORMAT_NO_OUTPUT; + diff_setup_done(&opts); + diff_tree_oid(&o_tree->object.oid, &tree->object.oid, "", &opts); + diffcore_std(&opts); + if (opts.needed_rename_limit > o->needed_rename_limit) + o->needed_rename_limit = opts.needed_rename_limit; + + ret = xmalloc(sizeof(*ret)); + *ret = diff_queued_diff; + + opts.output_format = DIFF_FORMAT_NO_OUTPUT; + diff_queued_diff.nr = 0; + diff_queued_diff.queue = NULL; + diff_flush(&opts); + return ret; +} + +static int tree_has_path(struct tree *tree, const char *path) +{ + struct object_id hashy; + unsigned int mode_o; + + return !get_tree_entry(&tree->object.oid, path, + &hashy, &mode_o); +} + +/* + * Return a new string that replaces the beginning portion (which matches + * entry->dir), with entry->new_dir. In perl-speak: + * new_path_name = (old_path =~ s/entry->dir/entry->new_dir/); + * NOTE: + * Caller must ensure that old_path starts with entry->dir + '/'. + */ +static char *apply_dir_rename(struct dir_rename_entry *entry, + const char *old_path) +{ + struct strbuf new_path = STRBUF_INIT; + int oldlen, newlen; + + if (entry->non_unique_new_dir) + return NULL; + + oldlen = strlen(entry->dir); + newlen = entry->new_dir.len + (strlen(old_path) - oldlen) + 1; + strbuf_grow(&new_path, newlen); + strbuf_addbuf(&new_path, &entry->new_dir); + strbuf_addstr(&new_path, &old_path[oldlen]); + + return strbuf_detach(&new_path, NULL); +} + +static void get_renamed_dir_portion(const char *old_path, const char *new_path, + char **old_dir, char **new_dir) +{ + char *end_of_old, *end_of_new; + int old_len, new_len; + + *old_dir = NULL; + *new_dir = NULL; + + /* + * For + * "a/b/c/d/e/foo.c" -> "a/b/some/thing/else/e/foo.c" + * the "e/foo.c" part is the same, we just want to know that + * "a/b/c/d" was renamed to "a/b/some/thing/else" + * so, for this example, this function returns "a/b/c/d" in + * *old_dir and "a/b/some/thing/else" in *new_dir. + * + * Also, if the basename of the file changed, we don't care. We + * want to know which portion of the directory, if any, changed. + */ + end_of_old = strrchr(old_path, '/'); + end_of_new = strrchr(new_path, '/'); + + if (end_of_old == NULL || end_of_new == NULL) + return; + while (*--end_of_new == *--end_of_old && + end_of_old != old_path && + end_of_new != new_path) + ; /* Do nothing; all in the while loop */ + /* + * We've found the first non-matching character in the directory + * paths. That means the current directory we were comparing + * represents the rename. Move end_of_old and end_of_new back + * to the full directory name. + */ + if (*end_of_old == '/') + end_of_old++; + if (*end_of_old != '/') + end_of_new++; + end_of_old = strchr(end_of_old, '/'); + end_of_new = strchr(end_of_new, '/'); + + /* + * It may have been the case that old_path and new_path were the same + * directory all along. Don't claim a rename if they're the same. + */ + old_len = end_of_old - old_path; + new_len = end_of_new - new_path; + + if (old_len != new_len || strncmp(old_path, new_path, old_len)) { + *old_dir = xstrndup(old_path, old_len); + *new_dir = xstrndup(new_path, new_len); + } +} + +static void remove_hashmap_entries(struct hashmap *dir_renames, + struct string_list *items_to_remove) +{ + int i; + struct dir_rename_entry *entry; + + for (i = 0; i < items_to_remove->nr; i++) { + entry = items_to_remove->items[i].util; + hashmap_remove(dir_renames, entry, NULL); + } + string_list_clear(items_to_remove, 0); +} + +/* + * See if there is a directory rename for path, and if there are any file + * level conflicts for the renamed location. If there is a rename and + * there are no conflicts, return the new name. Otherwise, return NULL. + */ +static char *handle_path_level_conflicts(struct merge_options *o, + const char *path, + struct dir_rename_entry *entry, + struct hashmap *collisions, + struct tree *tree) +{ + char *new_path = NULL; + struct collision_entry *collision_ent; + int clean = 1; + struct strbuf collision_paths = STRBUF_INIT; + + /* + * entry has the mapping of old directory name to new directory name + * that we want to apply to path. + */ + new_path = apply_dir_rename(entry, path); + + if (!new_path) { + /* This should only happen when entry->non_unique_new_dir set */ + if (!entry->non_unique_new_dir) + BUG("entry->non_unqiue_dir not set and !new_path"); + output(o, 1, _("CONFLICT (directory rename split): " + "Unclear where to place %s because directory " + "%s was renamed to multiple other directories, " + "with no destination getting a majority of the " + "files."), + path, entry->dir); + clean = 0; + return NULL; + } + + /* + * The caller needs to have ensured that it has pre-populated + * collisions with all paths that map to new_path. Do a quick check + * to ensure that's the case. + */ + collision_ent = collision_find_entry(collisions, new_path); + if (collision_ent == NULL) + BUG("collision_ent is NULL"); + + /* + * Check for one-sided add/add/.../add conflicts, i.e. + * where implicit renames from the other side doing + * directory rename(s) can affect this side of history + * to put multiple paths into the same location. Warn + * and bail on directory renames for such paths. + */ + if (collision_ent->reported_already) { + clean = 0; + } else if (tree_has_path(tree, new_path)) { + collision_ent->reported_already = 1; + strbuf_add_separated_string_list(&collision_paths, ", ", + &collision_ent->source_files); + output(o, 1, _("CONFLICT (implicit dir rename): Existing " + "file/dir at %s in the way of implicit " + "directory rename(s) putting the following " + "path(s) there: %s."), + new_path, collision_paths.buf); + clean = 0; + } else if (collision_ent->source_files.nr > 1) { + collision_ent->reported_already = 1; + strbuf_add_separated_string_list(&collision_paths, ", ", + &collision_ent->source_files); + output(o, 1, _("CONFLICT (implicit dir rename): Cannot map " + "more than one path to %s; implicit directory " + "renames tried to put these paths there: %s"), + new_path, collision_paths.buf); + clean = 0; + } + + /* Free memory we no longer need */ + strbuf_release(&collision_paths); + if (!clean && new_path) { + free(new_path); + return NULL; + } + + return new_path; +} + +/* + * There are a couple things we want to do at the directory level: + * 1. Check for both sides renaming to the same thing, in order to avoid + * implicit renaming of files that should be left in place. (See + * testcase 6b in t6043 for details.) + * 2. Prune directory renames if there are still files left in the + * the original directory. These represent a partial directory rename, + * i.e. a rename where only some of the files within the directory + * were renamed elsewhere. (Technically, this could be done earlier + * in get_directory_renames(), except that would prevent us from + * doing the previous check and thus failing testcase 6b.) + * 3. Check for rename/rename(1to2) conflicts (at the directory level). + * In the future, we could potentially record this info as well and + * omit reporting rename/rename(1to2) conflicts for each path within + * the affected directories, thus cleaning up the merge output. + * NOTE: We do NOT check for rename/rename(2to1) conflicts at the + * directory level, because merging directories is fine. If it + * causes conflicts for files within those merged directories, then + * that should be detected at the individual path level. + */ +static void handle_directory_level_conflicts(struct merge_options *o, + struct hashmap *dir_re_head, + struct tree *head, + struct hashmap *dir_re_merge, + struct tree *merge) +{ + struct hashmap_iter iter; + struct dir_rename_entry *head_ent; + struct dir_rename_entry *merge_ent; + + struct string_list remove_from_head = STRING_LIST_INIT_NODUP; + struct string_list remove_from_merge = STRING_LIST_INIT_NODUP; + + hashmap_iter_init(dir_re_head, &iter); + while ((head_ent = hashmap_iter_next(&iter))) { + merge_ent = dir_rename_find_entry(dir_re_merge, head_ent->dir); + if (merge_ent && + !head_ent->non_unique_new_dir && + !merge_ent->non_unique_new_dir && + !strbuf_cmp(&head_ent->new_dir, &merge_ent->new_dir)) { + /* 1. Renamed identically; remove it from both sides */ + string_list_append(&remove_from_head, + head_ent->dir)->util = head_ent; + strbuf_release(&head_ent->new_dir); + string_list_append(&remove_from_merge, + merge_ent->dir)->util = merge_ent; + strbuf_release(&merge_ent->new_dir); + } else if (tree_has_path(head, head_ent->dir)) { + /* 2. This wasn't a directory rename after all */ + string_list_append(&remove_from_head, + head_ent->dir)->util = head_ent; + strbuf_release(&head_ent->new_dir); + } + } + + remove_hashmap_entries(dir_re_head, &remove_from_head); + remove_hashmap_entries(dir_re_merge, &remove_from_merge); + + hashmap_iter_init(dir_re_merge, &iter); + while ((merge_ent = hashmap_iter_next(&iter))) { + head_ent = dir_rename_find_entry(dir_re_head, merge_ent->dir); + if (tree_has_path(merge, merge_ent->dir)) { + /* 2. This wasn't a directory rename after all */ + string_list_append(&remove_from_merge, + merge_ent->dir)->util = merge_ent; + } else if (head_ent && + !head_ent->non_unique_new_dir && + !merge_ent->non_unique_new_dir) { + /* 3. rename/rename(1to2) */ + /* + * We can assume it's not rename/rename(1to1) because + * that was case (1), already checked above. So we + * know that head_ent->new_dir and merge_ent->new_dir + * are different strings. + */ + output(o, 1, _("CONFLICT (rename/rename): " + "Rename directory %s->%s in %s. " + "Rename directory %s->%s in %s"), + head_ent->dir, head_ent->new_dir.buf, o->branch1, + head_ent->dir, merge_ent->new_dir.buf, o->branch2); + string_list_append(&remove_from_head, + head_ent->dir)->util = head_ent; + strbuf_release(&head_ent->new_dir); + string_list_append(&remove_from_merge, + merge_ent->dir)->util = merge_ent; + strbuf_release(&merge_ent->new_dir); + } + } + + remove_hashmap_entries(dir_re_head, &remove_from_head); + remove_hashmap_entries(dir_re_merge, &remove_from_merge); +} + +static struct hashmap *get_directory_renames(struct diff_queue_struct *pairs, + struct tree *tree) +{ + struct hashmap *dir_renames; + struct hashmap_iter iter; + struct dir_rename_entry *entry; + int i; + + /* + * Typically, we think of a directory rename as all files from a + * certain directory being moved to a target directory. However, + * what if someone first moved two files from the original + * directory in one commit, and then renamed the directory + * somewhere else in a later commit? At merge time, we just know + * that files from the original directory went to two different + * places, and that the bulk of them ended up in the same place. + * We want each directory rename to represent where the bulk of the + * files from that directory end up; this function exists to find + * where the bulk of the files went. + * + * The first loop below simply iterates through the list of file + * renames, finding out how often each directory rename pair + * possibility occurs. + */ + dir_renames = xmalloc(sizeof(*dir_renames)); + dir_rename_init(dir_renames); + for (i = 0; i < pairs->nr; ++i) { + struct string_list_item *item; + int *count; + struct diff_filepair *pair = pairs->queue[i]; + char *old_dir, *new_dir; + + /* File not part of directory rename if it wasn't renamed */ + if (pair->status != 'R') + continue; + + get_renamed_dir_portion(pair->one->path, pair->two->path, + &old_dir, &new_dir); + if (!old_dir) + /* Directory didn't change at all; ignore this one. */ + continue; + + entry = dir_rename_find_entry(dir_renames, old_dir); + if (!entry) { + entry = xmalloc(sizeof(*entry)); + dir_rename_entry_init(entry, old_dir); + hashmap_put(dir_renames, entry); + } else { + free(old_dir); + } + item = string_list_lookup(&entry->possible_new_dirs, new_dir); + if (!item) { + item = string_list_insert(&entry->possible_new_dirs, + new_dir); + item->util = xcalloc(1, sizeof(int)); + } else { + free(new_dir); + } + count = item->util; + *count += 1; + } + + /* + * For each directory with files moved out of it, we find out which + * target directory received the most files so we can declare it to + * be the "winning" target location for the directory rename. This + * winner gets recorded in new_dir. If there is no winner + * (multiple target directories received the same number of files), + * we set non_unique_new_dir. Once we've determined the winner (or + * that there is no winner), we no longer need possible_new_dirs. + */ + hashmap_iter_init(dir_renames, &iter); + while ((entry = hashmap_iter_next(&iter))) { + int max = 0; + int bad_max = 0; + char *best = NULL; + + for (i = 0; i < entry->possible_new_dirs.nr; i++) { + int *count = entry->possible_new_dirs.items[i].util; + + if (*count == max) + bad_max = max; + else if (*count > max) { + max = *count; + best = entry->possible_new_dirs.items[i].string; + } + } + if (bad_max == max) + entry->non_unique_new_dir = 1; + else { + assert(entry->new_dir.len == 0); + strbuf_addstr(&entry->new_dir, best); + } + /* + * The relevant directory sub-portion of the original full + * filepaths were xstrndup'ed before inserting into + * possible_new_dirs, and instead of manually iterating the + * list and free'ing each, just lie and tell + * possible_new_dirs that it did the strdup'ing so that it + * will free them for us. + */ + entry->possible_new_dirs.strdup_strings = 1; + string_list_clear(&entry->possible_new_dirs, 1); + } + + return dir_renames; +} + +static struct dir_rename_entry *check_dir_renamed(const char *path, + struct hashmap *dir_renames) +{ + char *temp = xstrdup(path); + char *end; + struct dir_rename_entry *entry = NULL;; + + while ((end = strrchr(temp, '/'))) { + *end = '\0'; + entry = dir_rename_find_entry(dir_renames, temp); + if (entry) + break; + } + free(temp); + return entry; +} + +static void compute_collisions(struct hashmap *collisions, + struct hashmap *dir_renames, + struct diff_queue_struct *pairs) +{ + int i; + + /* + * Multiple files can be mapped to the same path due to directory + * renames done by the other side of history. Since that other + * side of history could have merged multiple directories into one, + * if our side of history added the same file basename to each of + * those directories, then all N of them would get implicitly + * renamed by the directory rename detection into the same path, + * and we'd get an add/add/.../add conflict, and all those adds + * from *this* side of history. This is not representable in the + * index, and users aren't going to easily be able to make sense of + * it. So we need to provide a good warning about what's + * happening, and fall back to no-directory-rename detection + * behavior for those paths. + * + * See testcases 9e and all of section 5 from t6043 for examples. + */ + collision_init(collisions); + + for (i = 0; i < pairs->nr; ++i) { + struct dir_rename_entry *dir_rename_ent; + struct collision_entry *collision_ent; + char *new_path; + struct diff_filepair *pair = pairs->queue[i]; + + if (pair->status != 'A' && pair->status != 'R') + continue; + dir_rename_ent = check_dir_renamed(pair->two->path, + dir_renames); + if (!dir_rename_ent) + continue; + + new_path = apply_dir_rename(dir_rename_ent, pair->two->path); + if (!new_path) + /* + * dir_rename_ent->non_unique_new_path is true, which + * means there is no directory rename for us to use, + * which means it won't cause us any additional + * collisions. + */ + continue; + collision_ent = collision_find_entry(collisions, new_path); + if (!collision_ent) { + collision_ent = xcalloc(1, + sizeof(struct collision_entry)); + hashmap_entry_init(collision_ent, strhash(new_path)); + hashmap_put(collisions, collision_ent); + collision_ent->target_file = new_path; + } else { + free(new_path); + } + string_list_insert(&collision_ent->source_files, + pair->two->path); + } +} + +static char *check_for_directory_rename(struct merge_options *o, + const char *path, + struct tree *tree, + struct hashmap *dir_renames, + struct hashmap *dir_rename_exclusions, + struct hashmap *collisions, + int *clean_merge) +{ + char *new_path = NULL; + struct dir_rename_entry *entry = check_dir_renamed(path, dir_renames); + struct dir_rename_entry *oentry = NULL; + + if (!entry) + return new_path; + + /* + * This next part is a little weird. We do not want to do an + * implicit rename into a directory we renamed on our side, because + * that will result in a spurious rename/rename(1to2) conflict. An + * example: + * Base commit: dumbdir/afile, otherdir/bfile + * Side 1: smrtdir/afile, otherdir/bfile + * Side 2: dumbdir/afile, dumbdir/bfile + * Here, while working on Side 1, we could notice that otherdir was + * renamed/merged to dumbdir, and change the diff_filepair for + * otherdir/bfile into a rename into dumbdir/bfile. However, Side + * 2 will notice the rename from dumbdir to smrtdir, and do the + * transitive rename to move it from dumbdir/bfile to + * smrtdir/bfile. That gives us bfile in dumbdir vs being in + * smrtdir, a rename/rename(1to2) conflict. We really just want + * the file to end up in smrtdir. And the way to achieve that is + * to not let Side1 do the rename to dumbdir, since we know that is + * the source of one of our directory renames. + * + * That's why oentry and dir_rename_exclusions is here. + * + * As it turns out, this also prevents N-way transient rename + * confusion; See testcases 9c and 9d of t6043. + */ + oentry = dir_rename_find_entry(dir_rename_exclusions, entry->new_dir.buf); + if (oentry) { + output(o, 1, _("WARNING: Avoiding applying %s -> %s rename " + "to %s, because %s itself was renamed."), + entry->dir, entry->new_dir.buf, path, entry->new_dir.buf); + } else { + new_path = handle_path_level_conflicts(o, path, entry, + collisions, tree); + *clean_merge &= (new_path != NULL); + } + + return new_path; +} + +static void apply_directory_rename_modifications(struct merge_options *o, + struct diff_filepair *pair, + char *new_path, + struct rename *re, + struct tree *tree, + struct tree *o_tree, + struct tree *a_tree, + struct tree *b_tree, + struct string_list *entries, + int *clean) +{ + struct string_list_item *item; + int stage = (tree == a_tree ? 2 : 3); + int update_wd; + + /* + * In all cases where we can do directory rename detection, + * unpack_trees() will have read pair->two->path into the + * index and the working copy. We need to remove it so that + * we can instead place it at new_path. It is guaranteed to + * not be untracked (unpack_trees() would have errored out + * saying the file would have been overwritten), but it might + * be dirty, though. + */ + update_wd = !was_dirty(o, pair->two->path); + if (!update_wd) + output(o, 1, _("Refusing to lose dirty file at %s"), + pair->two->path); + remove_file(o, 1, pair->two->path, !update_wd); + + /* Find or create a new re->dst_entry */ + item = string_list_lookup(entries, new_path); + if (item) { + /* + * Since we're renaming on this side of history, and it's + * due to a directory rename on the other side of history + * (which we only allow when the directory in question no + * longer exists on the other side of history), the + * original entry for re->dst_entry is no longer + * necessary... + */ + re->dst_entry->processed = 1; + + /* + * ...because we'll be using this new one. + */ + re->dst_entry = item->util; + } else { + /* + * re->dst_entry is for the before-dir-rename path, and we + * need it to hold information for the after-dir-rename + * path. Before creating a new entry, we need to mark the + * old one as unnecessary (...unless it is shared by + * src_entry, i.e. this didn't use to be a rename, in which + * case we can just allow the normal processing to happen + * for it). + */ + if (pair->status == 'R') + re->dst_entry->processed = 1; + + re->dst_entry = insert_stage_data(new_path, + o_tree, a_tree, b_tree, + entries); + item = string_list_insert(entries, new_path); + item->util = re->dst_entry; + } + + /* + * Update the stage_data with the information about the path we are + * moving into place. That slot will be empty and available for us + * to write to because of the collision checks in + * handle_path_level_conflicts(). In other words, + * re->dst_entry->stages[stage].oid will be the null_oid, so it's + * open for us to write to. + * + * It may be tempting to actually update the index at this point as + * well, using update_stages_for_stage_data(), but as per the big + * "NOTE" in update_stages(), doing so will modify the current + * in-memory index which will break calls to would_lose_untracked() + * that we need to make. Instead, we need to just make sure that + * the various conflict_rename_*() functions update the index + * explicitly rather than relying on unpack_trees() to have done it. + */ + get_tree_entry(&tree->object.oid, + pair->two->path, + &re->dst_entry->stages[stage].oid, + &re->dst_entry->stages[stage].mode); + + /* Update pair status */ + if (pair->status == 'A') { + /* + * Recording rename information for this add makes it look + * like a rename/delete conflict. Make sure we can + * correctly handle this as an add that was moved to a new + * directory instead of reporting a rename/delete conflict. + */ + re->add_turned_into_rename = 1; + } + /* + * We don't actually look at pair->status again, but it seems + * pedagogically correct to adjust it. + */ + pair->status = 'R'; + + /* + * Finally, record the new location. + */ + pair->two->path = new_path; +} + +/* + * Get information of all renames which occurred in 'pairs', making use of + * any implicit directory renames inferred from the other side of history. + * We need the three trees in the merge ('o_tree', 'a_tree' and 'b_tree') + * to be able to associate the correct cache entries with the rename + * information; tree is always equal to either a_tree or b_tree. + */ +static struct string_list *get_renames(struct merge_options *o, + struct diff_queue_struct *pairs, + struct hashmap *dir_renames, + struct hashmap *dir_rename_exclusions, + struct tree *tree, + struct tree *o_tree, + struct tree *a_tree, + struct tree *b_tree, + struct string_list *entries, + int *clean_merge) +{ + int i; + struct hashmap collisions; + struct hashmap_iter iter; + struct collision_entry *e; + struct string_list *renames; + + compute_collisions(&collisions, dir_renames, pairs); + renames = xcalloc(1, sizeof(struct string_list)); + + for (i = 0; i < pairs->nr; ++i) { + struct string_list_item *item; + struct rename *re; + struct diff_filepair *pair = pairs->queue[i]; + char *new_path; /* non-NULL only with directory renames */ + + if (pair->status != 'A' && pair->status != 'R') { + diff_free_filepair(pair); + continue; + } + new_path = check_for_directory_rename(o, pair->two->path, tree, + dir_renames, + dir_rename_exclusions, + &collisions, + clean_merge); + if (pair->status != 'R' && !new_path) { + diff_free_filepair(pair); + continue; + } + + re = xmalloc(sizeof(*re)); + re->processed = 0; + re->add_turned_into_rename = 0; + re->pair = pair; + item = string_list_lookup(entries, re->pair->one->path); + if (!item) + re->src_entry = insert_stage_data(re->pair->one->path, + o_tree, a_tree, b_tree, entries); + else + re->src_entry = item->util; + + item = string_list_lookup(entries, re->pair->two->path); + if (!item) + re->dst_entry = insert_stage_data(re->pair->two->path, + o_tree, a_tree, b_tree, entries); + else + re->dst_entry = item->util; + item = string_list_insert(renames, pair->one->path); + item->util = re; + if (new_path) + apply_directory_rename_modifications(o, pair, new_path, + re, tree, o_tree, + a_tree, b_tree, + entries, + clean_merge); + } + + hashmap_iter_init(&collisions, &iter); + while ((e = hashmap_iter_next(&iter))) { + free(e->target_file); + string_list_clear(&e->source_files, 0); + } + hashmap_free(&collisions, 1); + return renames; +} + +static int process_renames(struct merge_options *o, + struct string_list *a_renames, + struct string_list *b_renames) +{ + int clean_merge = 1, i, j; + struct string_list a_by_dst = STRING_LIST_INIT_NODUP; + struct string_list b_by_dst = STRING_LIST_INIT_NODUP; + const struct rename *sre; + + for (i = 0; i < a_renames->nr; i++) { + sre = a_renames->items[i].util; + string_list_insert(&a_by_dst, sre->pair->two->path)->util + = (void *)sre; + } + for (i = 0; i < b_renames->nr; i++) { + sre = b_renames->items[i].util; + string_list_insert(&b_by_dst, sre->pair->two->path)->util + = (void *)sre; + } + + for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) { + struct string_list *renames1, *renames2Dst; + struct rename *ren1 = NULL, *ren2 = NULL; + const char *branch1, *branch2; + const char *ren1_src, *ren1_dst; + struct string_list_item *lookup; + + if (i >= a_renames->nr) { + ren2 = b_renames->items[j++].util; + } else if (j >= b_renames->nr) { + ren1 = a_renames->items[i++].util; + } else { + int compare = strcmp(a_renames->items[i].string, + b_renames->items[j].string); if (compare <= 0) ren1 = a_renames->items[i++].util; if (compare >= 0) @@@ -2606,7 -1463,7 +2607,7 @@@ const char *ren2_dst = ren2->pair->two->path; enum rename_type rename_type; if (strcmp(ren1_src, ren2_src) != 0) - die("BUG: ren1_src != ren2_src"); + BUG("ren1_src != ren2_src"); ren2->dst_entry->processed = 1; ren2->processed = 1; if (strcmp(ren1_dst, ren2_dst) != 0) { @@@ -2640,7 -1497,7 +2641,7 @@@ ren2 = lookup->util; ren2_dst = ren2->pair->two->path; if (strcmp(ren1_dst, ren2_dst) != 0) - die("BUG: ren1_dst != ren2_dst"); + BUG("ren1_dst != ren2_dst"); clean_merge = 0; ren2->processed = 1; @@@ -2682,7 -1539,7 +2683,7 @@@ * add-source case). */ remove_file(o, 1, ren1_src, - renamed_stage == 2 || !was_tracked(ren1_src)); + renamed_stage == 2 || !was_tracked(o, ren1_src)); oidcpy(&src_other.oid, &ren1->src_entry->stages[other_stage].oid); @@@ -2692,19 -1549,7 +2693,19 @@@ dst_other.mode = ren1->dst_entry->stages[other_stage].mode; try_merge = 0; - if (oid_eq(&src_other.oid, &null_oid)) { + if (oid_eq(&src_other.oid, &null_oid) && + ren1->add_turned_into_rename) { + setup_rename_conflict_info(RENAME_DIR, + ren1->pair, + NULL, + branch1, + branch2, + ren1->dst_entry, + NULL, + o, + NULL, + NULL); + } else if (oid_eq(&src_other.oid, &null_oid)) { setup_rename_conflict_info(RENAME_DELETE, ren1->pair, NULL, @@@ -2801,105 -1646,6 +2802,105 @@@ cleanup_and_return return clean_merge; } +struct rename_info { + struct string_list *head_renames; + struct string_list *merge_renames; +}; + +static void initial_cleanup_rename(struct diff_queue_struct *pairs, + struct hashmap *dir_renames) +{ + struct hashmap_iter iter; + struct dir_rename_entry *e; + + hashmap_iter_init(dir_renames, &iter); + while ((e = hashmap_iter_next(&iter))) { + free(e->dir); + strbuf_release(&e->new_dir); + /* possible_new_dirs already cleared in get_directory_renames */ + } + hashmap_free(dir_renames, 1); + free(dir_renames); + + free(pairs->queue); + free(pairs); +} + +static int handle_renames(struct merge_options *o, + struct tree *common, + struct tree *head, + struct tree *merge, + struct string_list *entries, + struct rename_info *ri) +{ + struct diff_queue_struct *head_pairs, *merge_pairs; + struct hashmap *dir_re_head, *dir_re_merge; + int clean = 1; + + ri->head_renames = NULL; + ri->merge_renames = NULL; + + if (!merge_detect_rename(o)) + return 1; + + head_pairs = get_diffpairs(o, common, head); + merge_pairs = get_diffpairs(o, common, merge); + + dir_re_head = get_directory_renames(head_pairs, head); + dir_re_merge = get_directory_renames(merge_pairs, merge); + + handle_directory_level_conflicts(o, + dir_re_head, head, + dir_re_merge, merge); + + ri->head_renames = get_renames(o, head_pairs, + dir_re_merge, dir_re_head, head, + common, head, merge, entries, + &clean); + if (clean < 0) + goto cleanup; + ri->merge_renames = get_renames(o, merge_pairs, + dir_re_head, dir_re_merge, merge, + common, head, merge, entries, + &clean); + if (clean < 0) + goto cleanup; + clean &= process_renames(o, ri->head_renames, ri->merge_renames); + +cleanup: + /* + * Some cleanup is deferred until cleanup_renames() because the + * data structures are still needed and referenced in + * process_entry(). But there are a few things we can free now. + */ + initial_cleanup_rename(head_pairs, dir_re_head); + initial_cleanup_rename(merge_pairs, dir_re_merge); + + return clean; +} + +static void final_cleanup_rename(struct string_list *rename) +{ + const struct rename *re; + int i; + + if (rename == NULL) + return; + + for (i = 0; i < rename->nr; i++) { + re = rename->items[i].util; + diff_free_filepair(re->pair); + } + string_list_clear(rename, 1); + free(rename); +} + +static void final_cleanup_renames(struct rename_info *re_info) +{ + final_cleanup_rename(re_info->head_renames); + final_cleanup_rename(re_info->merge_renames); +} + static struct object_id *stage_oid(const struct object_id *oid, unsigned mode) { return (is_null_oid(oid) || mode == 0) ? NULL: (struct object_id *)oid; @@@ -2990,7 -1736,6 +2991,7 @@@ static int handle_modify_delete(struct static int merge_content(struct merge_options *o, const char *path, + int is_dirty, struct object_id *o_oid, int o_mode, struct object_id *a_oid, int a_mode, struct object_id *b_oid, int b_mode, @@@ -3031,26 -1776,29 +3032,26 @@@ S_ISGITLINK(pair1->two->mode))) df_conflict_remains = 1; } - if (merge_file_special_markers(o, &one, &a, &b, + if (merge_file_special_markers(o, &one, &a, &b, path, o->branch1, path1, o->branch2, path2, &mfi)) return -1; - if (mfi.clean && !df_conflict_remains && - oid_eq(&mfi.oid, a_oid) && mfi.mode == a_mode) { - int path_renamed_outside_HEAD; + /* + * We can skip updating the working tree file iff: + * a) The merge is clean + * b) The merge matches what was in HEAD (content, mode, pathname) + * c) The target path is usable (i.e. not involved in D/F conflict) + */ + if (mfi.clean && + was_tracked_and_matches(o, path, &mfi.oid, mfi.mode) && + !df_conflict_remains) { output(o, 3, _("Skipped %s (merged same as existing)"), path); - /* - * The content merge resulted in the same file contents we - * already had. We can return early if those file contents - * are recorded at the correct path (which may not be true - * if the merge involves a rename). - */ - path_renamed_outside_HEAD = !path2 || !strcmp(path, path2); - if (!path_renamed_outside_HEAD) { - add_cacheinfo(o, mfi.mode, &mfi.oid, path, - 0, (!o->call_depth), 0); - return mfi.clean; - } - } else - output(o, 2, _("Auto-merging %s"), path); + if (add_cacheinfo(o, mfi.mode, &mfi.oid, path, + 0, (!o->call_depth && !is_dirty), 0)) + return -1; + return mfi.clean; + } if (!mfi.clean) { if (S_ISGITLINK(mfi.mode)) @@@ -3062,7 -1810,7 +3063,7 @@@ return -1; } - if (df_conflict_remains) { + if (df_conflict_remains || is_dirty) { char *new_path; if (o->call_depth) { remove_file_from_cache(path); @@@ -3071,7 -1819,7 +3072,7 @@@ if (update_stages(o, path, &one, &a, &b)) return -1; } else { - int file_from_stage2 = was_tracked(path); + int file_from_stage2 = was_tracked(o, path); struct diff_filespec merged; oidcpy(&merged.oid, &mfi.oid); merged.mode = mfi.mode; @@@ -3084,10 -1832,6 +3085,10 @@@ } new_path = unique_path(o, path, rename_conflict_info->branch1); + if (is_dirty) { + output(o, 1, _("Refusing to lose dirty file at %s"), + path); + } output(o, 1, _("Adding as %s instead"), new_path); if (update_file(o, 0, &mfi.oid, mfi.mode, new_path)) { free(new_path); @@@ -3097,20 -1841,7 +3098,20 @@@ mfi.clean = 0; } else if (update_file(o, mfi.clean, &mfi.oid, mfi.mode, path)) return -1; - return mfi.clean; + return !is_dirty && mfi.clean; +} + +static int conflict_rename_normal(struct merge_options *o, + const char *path, + struct object_id *o_oid, unsigned int o_mode, + struct object_id *a_oid, unsigned int a_mode, + struct object_id *b_oid, unsigned int b_mode, + struct rename_conflict_info *ci) +{ + /* Merge the content and write it out */ + return merge_content(o, path, was_dirty(o, path), + o_oid, o_mode, a_oid, a_mode, b_oid, b_mode, + ci); } /* Per entry merge function */ @@@ -3132,20 -1863,9 +3133,20 @@@ static int process_entry(struct merge_o switch (conflict_info->rename_type) { case RENAME_NORMAL: case RENAME_ONE_FILE_TO_ONE: - clean_merge = merge_content(o, path, - o_oid, o_mode, a_oid, a_mode, b_oid, b_mode, - conflict_info); + clean_merge = conflict_rename_normal(o, + path, + o_oid, o_mode, + a_oid, a_mode, + b_oid, b_mode, + conflict_info); + break; + case RENAME_DIR: + clean_merge = 1; + if (conflict_rename_dir(o, + conflict_info->pair1, + conflict_info->branch1, + conflict_info->branch2)) + clean_merge = -1; break; case RENAME_DELETE: clean_merge = 0; @@@ -3233,8 -1953,7 +3234,8 @@@ } else if (a_oid && b_oid) { /* Case C: Added in both (check for same permissions) and */ /* case D: Modified in both, but differently. */ - clean_merge = merge_content(o, path, + int is_dirty = 0; /* unpack_trees would have bailed if dirty */ + clean_merge = merge_content(o, path, is_dirty, o_oid, o_mode, a_oid, a_mode, b_oid, b_mode, NULL); } else if (!o_oid && !a_oid && !b_oid) { @@@ -3244,7 -1963,7 +3245,7 @@@ */ remove_file(o, 1, path, !a_mode); } else - die("BUG: fatal merge failure, shouldn't happen."); + BUG("fatal merge failure, shouldn't happen."); return clean_merge; } @@@ -3275,20 -1994,18 +3276,20 @@@ int merge_trees(struct merge_options *o return 1; } - code = git_merge_trees(o->call_depth, common, head, merge); + code = unpack_trees_start(o, common, head, merge); if (code != 0) { if (show(o, 4) || o->call_depth) err(o, _("merging of trees %s and %s failed"), oid_to_hex(&head->object.oid), oid_to_hex(&merge->object.oid)); + unpack_trees_finish(o); return -1; } if (unmerged_cache()) { - struct string_list *entries, *re_head, *re_merge; + struct string_list *entries; + struct rename_info re_info; int i; /* * Only need the hashmap while processing entries, so @@@ -3302,8 -2019,9 +3303,8 @@@ get_files_dirs(o, merge); entries = get_unmerged(); - re_head = get_renames(o, head, common, head, merge, entries); - re_merge = get_renames(o, merge, common, head, merge, entries); - clean = process_renames(o, re_head, re_merge); + clean = handle_renames(o, common, head, merge, entries, + &re_info); record_df_conflict_files(o, entries); if (clean < 0) goto cleanup; @@@ -3323,28 -2041,27 +3324,28 @@@ for (i = 0; i < entries->nr; i++) { struct stage_data *e = entries->items[i].util; if (!e->processed) - die("BUG: unprocessed path??? %s", + BUG("unprocessed path??? %s", entries->items[i].string); } cleanup: - string_list_clear(re_merge, 0); - string_list_clear(re_head, 0); + final_cleanup_renames(&re_info); + string_list_clear(entries, 1); + free(entries); hashmap_free(&o->current_file_dir_set, 1); - free(re_merge); - free(re_head); - free(entries); - - if (clean < 0) + if (clean < 0) { + unpack_trees_finish(o); return clean; + } } else clean = 1; + unpack_trees_finish(o); + if (o->call_depth && !(*result = write_tree_from_memory(o))) return -1; @@@ -3438,8 -2155,7 +3439,8 @@@ int merge_recursive(struct merge_option read_cache(); o->ancestor = "merged common ancestors"; - clean = merge_trees(o, h1->tree, h2->tree, merged_common_ancestors->tree, + clean = merge_trees(o, get_commit_tree(h1), get_commit_tree(h2), + get_commit_tree(merged_common_ancestors), &mrtree); if (clean < 0) { flush_output(o); @@@ -3517,18 -2233,9 +3518,18 @@@ int merge_recursive_generic(struct merg static void merge_recursive_config(struct merge_options *o) { + char *value = NULL; git_config_get_int("merge.verbosity", &o->verbosity); git_config_get_int("diff.renamelimit", &o->diff_rename_limit); git_config_get_int("merge.renamelimit", &o->merge_rename_limit); + if (!git_config_get_string("diff.renames", &value)) { + o->diff_detect_rename = git_config_rename("diff.renames", value); + free(value); + } + if (!git_config_get_string("merge.renames", &value)) { + o->merge_detect_rename = git_config_rename("merge.renames", value); + free(value); + } git_config(git_xmerge_config, NULL); } @@@ -3541,8 -2248,7 +3542,8 @@@ void init_merge_options(struct merge_op o->diff_rename_limit = -1; o->merge_rename_limit = -1; o->renormalize = 0; - o->detect_rename = 1; + o->diff_detect_rename = -1; + o->merge_detect_rename = -1; merge_recursive_config(o); merge_verbosity = getenv("GIT_MERGE_VERBOSITY"); if (merge_verbosity) @@@ -3593,16 -2299,16 +3594,16 @@@ int parse_merge_opt(struct merge_option else if (!strcmp(s, "no-renormalize")) o->renormalize = 0; else if (!strcmp(s, "no-renames")) - o->detect_rename = 0; + o->merge_detect_rename = 0; else if (!strcmp(s, "find-renames")) { - o->detect_rename = 1; + o->merge_detect_rename = 1; o->rename_score = 0; } else if (skip_prefix(s, "find-renames=", &arg) || skip_prefix(s, "rename-threshold=", &arg)) { if ((o->rename_score = parse_rename_score(&arg)) == -1 || *arg != 0) return -1; - o->detect_rename = 1; + o->merge_detect_rename = 1; } else return -1; diff --combined object.c index d33e2a5cc8,8e29f63bf2..10d167825e --- a/object.c +++ b/object.c @@@ -5,20 -5,18 +5,18 @@@ #include "tree.h" #include "commit.h" #include "tag.h" + #include "alloc.h" #include "object-store.h" #include "packfile.h" - static struct object **obj_hash; - static int nr_objs, obj_hash_size; - unsigned int get_max_object_index(void) { - return obj_hash_size; + return the_repository->parsed_objects->obj_hash_size; } struct object *get_indexed_object(unsigned int idx) { - return obj_hash[idx]; + return the_repository->parsed_objects->obj_hash[idx]; } static const char *object_type_strings[] = { @@@ -90,15 -88,16 +88,16 @@@ struct object *lookup_object(const unsi unsigned int i, first; struct object *obj; - if (!obj_hash) + if (!the_repository->parsed_objects->obj_hash) return NULL; - first = i = hash_obj(sha1, obj_hash_size); - while ((obj = obj_hash[i]) != NULL) { + first = i = hash_obj(sha1, + the_repository->parsed_objects->obj_hash_size); + while ((obj = the_repository->parsed_objects->obj_hash[i]) != NULL) { if (!hashcmp(sha1, obj->oid.hash)) break; i++; - if (i == obj_hash_size) + if (i == the_repository->parsed_objects->obj_hash_size) i = 0; } if (obj && i != first) { @@@ -107,7 -106,8 +106,8 @@@ * that we do not need to walk the hash table the next * time we look for it. */ - SWAP(obj_hash[i], obj_hash[first]); + SWAP(the_repository->parsed_objects->obj_hash[i], + the_repository->parsed_objects->obj_hash[first]); } return obj; } @@@ -117,29 -117,30 +117,30 @@@ * power of 2 (but at least 32). Copy the existing values to the new * hash map. */ - static void grow_object_hash(void) + static void grow_object_hash(struct repository *r) { int i; /* * Note that this size must always be power-of-2 to match hash_obj * above. */ - int new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size; + int new_hash_size = r->parsed_objects->obj_hash_size < 32 ? 32 : 2 * r->parsed_objects->obj_hash_size; struct object **new_hash; new_hash = xcalloc(new_hash_size, sizeof(struct object *)); - for (i = 0; i < obj_hash_size; i++) { - struct object *obj = obj_hash[i]; + for (i = 0; i < r->parsed_objects->obj_hash_size; i++) { + struct object *obj = r->parsed_objects->obj_hash[i]; + if (!obj) continue; insert_obj_hash(obj, new_hash, new_hash_size); } - free(obj_hash); - obj_hash = new_hash; - obj_hash_size = new_hash_size; + free(r->parsed_objects->obj_hash); + r->parsed_objects->obj_hash = new_hash; + r->parsed_objects->obj_hash_size = new_hash_size; } - void *create_object(const unsigned char *sha1, void *o) + void *create_object(struct repository *r, const unsigned char *sha1, void *o) { struct object *obj = o; @@@ -147,11 -148,12 +148,12 @@@ obj->flags = 0; hashcpy(obj->oid.hash, sha1); - if (obj_hash_size - 1 <= nr_objs * 2) - grow_object_hash(); + if (r->parsed_objects->obj_hash_size - 1 <= r->parsed_objects->nr_objs * 2) + grow_object_hash(r); - insert_obj_hash(obj, obj_hash, obj_hash_size); - nr_objs++; + insert_obj_hash(obj, r->parsed_objects->obj_hash, + r->parsed_objects->obj_hash_size); + r->parsed_objects->nr_objs++; return obj; } @@@ -161,7 -163,7 +163,7 @@@ void *object_as_type(struct object *obj return obj; else if (obj->type == OBJ_NONE) { if (type == OBJ_COMMIT) - ((struct commit *)obj)->index = alloc_commit_index(); + ((struct commit *)obj)->index = alloc_commit_index(the_repository); obj->type = type; return obj; } @@@ -178,7 -180,8 +180,8 @@@ struct object *lookup_unknown_object(co { struct object *obj = lookup_object(sha1); if (!obj) - obj = create_object(sha1, alloc_object_node()); + obj = create_object(the_repository, sha1, + alloc_object_node(the_repository)); return obj; } @@@ -210,7 -213,7 +213,7 @@@ struct object *parse_object_buffer(cons } else if (type == OBJ_COMMIT) { struct commit *commit = lookup_commit(oid); if (commit) { - if (parse_commit_buffer(commit, buffer, size)) + if (parse_commit_buffer(commit, buffer, size, 1)) return NULL; if (!get_cached_commit_buffer(commit, NULL)) { set_commit_buffer(commit, buffer, size); @@@ -431,8 -434,8 +434,8 @@@ void clear_object_flags(unsigned flags { int i; - for (i=0; i < obj_hash_size; i++) { - struct object *obj = obj_hash[i]; + for (i=0; i < the_repository->parsed_objects->obj_hash_size; i++) { + struct object *obj = the_repository->parsed_objects->obj_hash[i]; if (obj) obj->flags &= ~flags; } @@@ -442,13 -445,27 +445,27 @@@ void clear_commit_marks_all(unsigned in { int i; - for (i = 0; i < obj_hash_size; i++) { - struct object *obj = obj_hash[i]; + for (i = 0; i < the_repository->parsed_objects->obj_hash_size; i++) { + struct object *obj = the_repository->parsed_objects->obj_hash[i]; if (obj && obj->type == OBJ_COMMIT) obj->flags &= ~flags; } } + struct parsed_object_pool *parsed_object_pool_new(void) + { + struct parsed_object_pool *o = xmalloc(sizeof(*o)); + memset(o, 0, sizeof(*o)); + + o->blob_state = allocate_alloc_state(); + o->tree_state = allocate_alloc_state(); + o->commit_state = allocate_alloc_state(); + o->tag_state = allocate_alloc_state(); + o->object_state = allocate_alloc_state(); + + return o; + } + struct raw_object_store *raw_object_store_new(void) { struct raw_object_store *o = xmalloc(sizeof(*o)); @@@ -481,9 -498,6 +498,9 @@@ void raw_object_store_clear(struct raw_ FREE_AND_NULL(o->objectdir); FREE_AND_NULL(o->alternate_db); + oidmap_free(o->replace_map, 1); + FREE_AND_NULL(o->replace_map); + free_alt_odbs(o); o->alt_odb_tail = NULL; @@@ -491,3 -505,43 +508,43 @@@ close_all_packs(o); o->packed_git = NULL; } + + void parsed_object_pool_clear(struct parsed_object_pool *o) + { + /* + * As objects are allocated in slabs (see alloc.c), we do + * not need to free each object, but each slab instead. + * + * Before doing so, we need to free any additional memory + * the objects may hold. + */ + unsigned i; + + for (i = 0; i < o->obj_hash_size; i++) { + struct object *obj = o->obj_hash[i]; + + if (!obj) + continue; + + if (obj->type == OBJ_TREE) + free_tree_buffer((struct tree*)obj); + else if (obj->type == OBJ_COMMIT) + release_commit_memory((struct commit*)obj); + else if (obj->type == OBJ_TAG) + release_tag_memory((struct tag*)obj); + } + + FREE_AND_NULL(o->obj_hash); + o->obj_hash_size = 0; + + clear_alloc_state(o->blob_state); + clear_alloc_state(o->tree_state); + clear_alloc_state(o->commit_state); + clear_alloc_state(o->tag_state); + clear_alloc_state(o->object_state); + FREE_AND_NULL(o->blob_state); + FREE_AND_NULL(o->tree_state); + FREE_AND_NULL(o->commit_state); + FREE_AND_NULL(o->tag_state); + FREE_AND_NULL(o->object_state); + } diff --combined object.h index acc560b24e,7916edb4ed..47d1b49022 --- a/object.h +++ b/object.h @@@ -1,6 -1,22 +1,22 @@@ #ifndef OBJECT_H #define OBJECT_H + struct parsed_object_pool { + struct object **obj_hash; + int nr_objs, obj_hash_size; + + /* TODO: migrate alloc_states to mem-pool? */ + struct alloc_state *blob_state; + struct alloc_state *tree_state; + struct alloc_state *commit_state; + struct alloc_state *tag_state; + struct alloc_state *object_state; + unsigned commit_count; + }; + + struct parsed_object_pool *parsed_object_pool_new(void); + void parsed_object_pool_clear(struct parsed_object_pool *o); + struct object_list { struct object *item; struct object_list *next; @@@ -25,6 -41,7 +41,6 @@@ struct object_array #define OBJECT_ARRAY_INIT { 0, 0, NULL } -#define TYPE_BITS 3 /* * object flag allocation: * revision.h: 0---------10 26 @@@ -36,13 -53,12 +52,13 @@@ * bundle.c: 16 * http-push.c: 16-----19 * commit.c: 16-----19 - * sha1_name.c: 20 + * sha1-name.c: 20 * list-objects-filter.c: 21 * builtin/fsck.c: 0--3 * builtin/index-pack.c: 2021 * builtin/pack-objects.c: 20 * builtin/reflog.c: 10--12 + * builtin/show-branch.c: 0-------------------------------------------26 * builtin/unpack-objects.c: 2021 */ #define FLAG_BITS 27 @@@ -85,7 -101,7 +101,7 @@@ extern struct object *get_indexed_objec */ struct object *lookup_object(const unsigned char *sha1); - extern void *create_object(const unsigned char *sha1, void *obj); + extern void *create_object(struct repository *r, const unsigned char *sha1, void *obj); void *object_as_type(struct object *obj, enum object_type type, int quiet); diff --combined repository.c index 02fe884603,c23404677e..5dd1486718 --- a/repository.c +++ b/repository.c @@@ -2,6 -2,7 +2,7 @@@ #include "repository.h" #include "object-store.h" #include "config.h" + #include "object.h" #include "submodule-config.h" /* The main repository */ @@@ -14,6 -15,8 +15,8 @@@ void initialize_the_repository(void the_repo.index = &the_index; the_repo.objects = raw_object_store_new(); + the_repo.parsed_objects = parsed_object_pool_new(); + repo_set_hash_algo(&the_repo, GIT_HASH_SHA1); } @@@ -135,14 -138,15 +138,15 @@@ static int read_and_verify_repository_f * Initialize 'repo' based on the provided 'gitdir'. * Return 0 upon success and a non-zero value upon failure. */ -static int repo_init(struct repository *repo, - const char *gitdir, - const char *worktree) +int repo_init(struct repository *repo, + const char *gitdir, + const char *worktree) { struct repository_format format; memset(repo, 0, sizeof(*repo)); repo->objects = raw_object_store_new(); + repo->parsed_objects = parsed_object_pool_new(); if (repo_init_gitdir(repo, gitdir)) goto error; @@@ -176,7 -180,7 +180,7 @@@ int repo_submodule_init(struct reposito struct strbuf worktree = STRBUF_INIT; int ret = 0; - sub = submodule_from_cache(superproject, &null_oid, path); + sub = submodule_from_path(superproject, &null_oid, path); if (!sub) { ret = -1; goto out; @@@ -226,6 -230,9 +230,9 @@@ void repo_clear(struct repository *repo raw_object_store_clear(repo->objects); FREE_AND_NULL(repo->objects); + parsed_object_pool_clear(repo->parsed_objects); + FREE_AND_NULL(repo->parsed_objects); + if (repo->config) { git_configset_clear(repo->config); FREE_AND_NULL(repo->config); @@@ -238,8 -245,7 +245,8 @@@ if (repo->index) { discard_index(repo->index); - FREE_AND_NULL(repo->index); + if (repo->index != &the_index) + FREE_AND_NULL(repo->index); } } diff --combined repository.h index f2646f0c52,6d19981990..dba3ddbfdd --- a/repository.h +++ b/repository.h @@@ -26,6 -26,15 +26,15 @@@ struct repository */ struct raw_object_store *objects; + /* + * All objects in this repository that have been parsed. This structure + * owns all objects it references, so users of "struct object *" + * generally do not need to free them; instead, when a repository is no + * longer used, call parsed_object_pool_clear() on this structure, which + * is called by the repositories repo_clear on its desconstruction. + */ + struct parsed_object_pool *parsed_objects; + /* The store in which the refs are held. */ struct ref_store *refs; @@@ -100,9 -109,6 +109,9 @@@ extern void repo_set_gitdir(struct repo extern void repo_set_worktree(struct repository *repo, const char *path); extern void repo_set_hash_algo(struct repository *repo, int algo); extern void initialize_the_repository(void); +extern int repo_init(struct repository *r, + const char *gitdir, + const char *worktree); extern int repo_submodule_init(struct repository *submodule, struct repository *superproject, const char *path); diff --combined tree.c index 244eb5e665,8f8ef3189a..2c9c49725c --- a/tree.c +++ b/tree.c @@@ -5,6 -5,7 +5,7 @@@ #include "blob.h" #include "commit.h" #include "tag.h" + #include "alloc.h" #include "tree-walk.h" const char *tree_type = "tree"; @@@ -109,7 -110,7 +110,7 @@@ static int read_tree_1(struct tree *tre oid_to_hex(entry.oid), base->buf, entry.path); - oidcpy(&oid, &commit->tree->object.oid); + oidcpy(&oid, get_commit_tree_oid(commit)); } else continue; @@@ -196,7 -197,8 +197,8 @@@ struct tree *lookup_tree(const struct o { struct object *obj = lookup_object(oid->hash); if (!obj) - return create_object(oid->hash, alloc_tree_node()); + return create_object(the_repository, oid->hash, + alloc_tree_node(the_repository)); return object_as_type(obj, OBJ_TREE, 0); } @@@ -248,7 -250,7 +250,7 @@@ struct tree *parse_tree_indirect(const if (obj->type == OBJ_TREE) return (struct tree *) obj; else if (obj->type == OBJ_COMMIT) - obj = &(((struct commit *) obj)->tree->object); + obj = &(get_commit_tree(((struct commit *)obj))->object); else if (obj->type == OBJ_TAG) obj = ((struct tag *) obj)->tagged; else