summaryrefslogtreecommitdiff
path: root/match-trees.c
AgeCommit message (Collapse)AuthorFilesLines
2018-08-17Merge branch 'jk/merge-subtree-heuristics'Libravatar Junio C Hamano1-17/+26
The automatic tree-matching in "git merge -s subtree" was broken 5 years ago and nobody has noticed since then, which is now fixed. * jk/merge-subtree-heuristics: score_trees(): fix iteration over trees with missing entries
2018-08-02score_trees(): fix iteration over trees with missing entriesLibravatar Jeff King1-17/+26
In score_trees(), we walk over two sorted trees to find which entries are missing or have different content between the two. So if we have two trees with these entries: one two --- --- a a b c c d we'd expect the loop to: - compare "a" to "a" - compare "b" to "c"; because these are sorted lists, we know that the second tree does not have "b" - compare "c" to "c" - compare "d" to end-of-list; we know that the first tree does not have "d" And prior to d8febde370 (match-trees: simplify score_trees() using tree_entry(), 2013-03-24) that worked. But after that commit, we mistakenly increment the tree pointers for every loop iteration, even when we've processed the entry for only one side. As a result, we end up doing this: - compare "a" to "a" - compare "b" to "c"; we know that we do not have "b", but we still increment both tree pointers; at this point we're out of sync and all further comparisons are wrong - compare "c" to "d" and mistakenly claim that the second tree does not have "c" - exit the loop, mistakenly not realizing that the first tree does not have "d" So contrary to the claim in d8febde370, we really do need to manually use update_tree_entry(), because advancing the tree pointer depends on the entry comparison. That means we must stop using tree_entry() to access each entry, since it auto-advances the pointer. Instead: - we'll use tree_desc.size directly to know if there's anything left to look at (which is what tree_entry() was doing under the hood) - rather than do an extra struct assignment to "e1" and "e2", we can just access the "entry" field of tree_desc directly That makes us a little more intimate with the tree_desc code, but that's not uncommon for its callers. The included test shows off the bug by adding a new entry "bar.t", which sorts early in the tree and de-syncs the comparison for "foo.t", which comes after. Reported-by: George Shammas <georgyo@gmail.com> Helped-by: René Scharfe <l.s.r@web.de> Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-05-16object-store: move object access functions to object-store.hLibravatar Stefan Beller1-0/+1
This should make these functions easier to find and cache.h less overwhelming to read. In particular, this moves: - read_object_file - oid_object_info - write_object_file As a result, most of the codebase needs to #include object-store.h. In this patch the #include is only added to files that would fail to compile otherwise. It would be better to #include wherever identifiers from the header are used. That can happen later when we have better tooling for it. Signed-off-by: Stefan Beller <sbeller@google.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-03-14sha1_file: convert read_sha1_file to struct object_idLibravatar brian m. carlson1-2/+2
Convert read_sha1_file to take a pointer to struct object_id and rename it read_object_file. Do the same for read_sha1_file_extended. Convert one use in grep.c to use the new function without any other code change, since the pointer being passed is a void pointer that is already initialized with a pointer to struct object_id. Update the declaration and definitions of the modified functions, and apply the following semantic patch to convert the remaining callers: @@ expression E1, E2, E3; @@ - read_sha1_file(E1.hash, E2, E3) + read_object_file(&E1, E2, E3) @@ expression E1, E2, E3; @@ - read_sha1_file(E1->hash, E2, E3) + read_object_file(E1, E2, E3) @@ expression E1, E2, E3, E4; @@ - read_sha1_file_extended(E1.hash, E2, E3, E4) + read_object_file_extended(&E1, E2, E3, E4) @@ expression E1, E2, E3, E4; @@ - read_sha1_file_extended(E1->hash, E2, E3, E4) + read_object_file_extended(E1, E2, E3, E4) Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-03-14tree-walk: convert tree entry functions to object_idLibravatar brian m. carlson1-3/+3
Convert get_tree_entry and find_tree_entry to take pointers to struct object_id. Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-01-30sha1_file: convert write_sha1_file to object_idLibravatar Patryk Obara1-1/+1
Convert the definition and declaration of write_sha1_file to struct object_id and adjust usage of this function. This commit also converts static function write_sha1_file_prepare, as it is closely related. Rename these functions to write_object_file and write_object_file_prepare respectively. Replace sha1_to_hex, hashcpy and hashclr with their oid equivalents wherever possible. Signed-off-by: Patryk Obara <patryk.obara@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2018-01-30match-trees: convert splice_tree to object_idLibravatar Patryk Obara1-24/+22
Convert the definition of static recursive splice_tree function to use struct object_id and adjust single caller. Signed-off-by: Patryk Obara <patryk.obara@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-04-25match-trees: convert several leaf functions to use struct object_idLibravatar brian m. carlson1-15/+15
Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-04-25tree-walk: convert tree_entry_extract() to use struct object_idLibravatar brian m. carlson1-6/+6
Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-04-25struct name_entry: use struct object_id instead of unsigned char sha1[20]Libravatar brian m. carlson1-1/+1
Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-04-19match-trees: convert shift_tree() and shift_tree_by() to use object_idLibravatar brian m. carlson1-22/+22
Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-06-19use xstrfmt to replace xmalloc + sprintfLibravatar Jeff King1-7/+2
This is one line shorter, and makes sure the length in the malloc and sprintf steps match. These conversions are very straightforward; we can drop the malloc entirely, and replace the sprintf with xstrfmt. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-03-10use strchrnul() in place of strchr() and strlen()Libravatar Rohit Mani1-7/+4
Avoid scanning strings twice, once with strchr() and then with strlen(), by using strchrnul(). Helped-by: Junio C Hamano <gitster@pobox.com> Signed-off-by: Rohit Mani <rohit.mani@outlook.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2013-06-13match-trees: factor out fill_tree_desc_strictLibravatar René Scharfe1-25/+19
Deduplicate code by moving tree_desc initialization into a helper function, fill_tree_desc_strict. It is like fill_tree_descriptor, except that it only accepts tree hashes and no tree references (tags, commits). No functional change. Signed-off-by: René Scharfe <rene.scharfe@lsrfire.ath.cx> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2013-03-25match-trees: simplify score_trees() using tree_entry()Libravatar René Scharfe1-40/+28
Convert the loop in score_trees() to tree_entry(). The code becomes shorter and simpler because the calls to update_tree_entry() are not needed any more. Another benefit is that we need less variables to track the current tree entries; as a side-effect of that the compiler has an easier job figuring out the control flow and thus can avoid false warnings about uninitialized variables. Using struct name_entry also allows the use of tree_entry_len() for finding the path length instead of strlen(), which may be slightly more efficient. Also unify the handling of missing entries in one of the two trees (i.e. added or removed files): Just set cmp appropriately first, no matter if we ran off the end of a tree or if we actually have two entries to compare, and check its value a bit later without duplicating the handler code. Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2010-01-17Make "subtree" part more orthogonal to the rest of merge-recursive.Libravatar Junio C Hamano1-1/+68
This makes "subtree" more orthogonal to the rest of recursive merge, so that you can use subtree and ours/theirs features at the same time. For example, you can now say: git merge -s subtree -Xtheirs other to merge with "other" branch while shifting it up or down to match the shape of the tree of the current branch, and resolving conflicts favoring the changes "other" branch made over changes made in the current branch. It also allows the prefix used to shift the trees to be specified using the "-Xsubtree=$prefix" option. Giving an empty prefix tells the command to figure out how much to shift trees automatically as we have always done. "merge -s subtree" is the same as "merge -s recursive -Xsubtree=" (or "merge -s recursive -Xsubtree"). Based on an old patch done back in the days when git-merge was a script; Avery ported the script part to builtin-merge.c. Bugs in shift_tree() is mine. Signed-off-by: Avery Pennarun <apenwarr@gmail.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-10-21Improved const correctness for stringsLibravatar Shawn O. Pearce1-1/+1
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
2007-06-07War on whitespaceLibravatar Junio C Hamano1-1/+0
This uses "git-apply --whitespace=strip" to fix whitespace errors that have crept in to our source files over time. There are a few files that need to have trailing whitespaces (most notably, test vectors). The results still passes the test, and build result in Documentation/ area is unchanged. Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-04-07A new merge stragety 'subtree'.Libravatar Junio C Hamano1-0/+304
This merge strategy largely piggy-backs on git-merge-recursive. When merging trees A and B, if B corresponds to a subtree of A, B is first adjusted to match the tree structure of A, instead of reading the trees at the same level. This adjustment is also done to the common ancestor tree. If you are pulling updates from git-gui repository into git.git repository, the root level of the former corresponds to git-gui/ subdirectory of the latter. The tree object of git-gui's toplevel is wrapped in a fake tree object, whose sole entry has name 'git-gui' and records object name of the true tree, before being used by the 3-way merge code. If you are merging the other way, only the git-gui/ subtree of git.git is extracted and merged into git-gui's toplevel. The detection of corresponding subtree is done by comparing the pathnames and types in the toplevel of the tree. Heuristics galore! That's the git way ;-). Signed-off-by: Junio C Hamano <junkio@cox.net>