git
/
match-trees.c
370 строк · 8.7 Кб
1#define USE_THE_REPOSITORY_VARIABLE2
3#include "git-compat-util.h"4#include "hex.h"5#include "match-trees.h"6#include "strbuf.h"7#include "tree.h"8#include "tree-walk.h"9#include "object-store-ll.h"10
11static int score_missing(unsigned mode)12{
13int score;14
15if (S_ISDIR(mode))16score = -1000;17else if (S_ISLNK(mode))18score = -500;19else20score = -50;21return score;22}
23
24static int score_differs(unsigned mode1, unsigned mode2)25{
26int score;27
28if (S_ISDIR(mode1) != S_ISDIR(mode2))29score = -100;30else if (S_ISLNK(mode1) != S_ISLNK(mode2))31score = -50;32else33score = -5;34return score;35}
36
37static int score_matches(unsigned mode1, unsigned mode2)38{
39int score;40
41/* Heh, we found SHA-1 collisions between different kind of objects */42if (S_ISDIR(mode1) != S_ISDIR(mode2))43score = -100;44else if (S_ISLNK(mode1) != S_ISLNK(mode2))45score = -50;46
47else if (S_ISDIR(mode1))48score = 1000;49else if (S_ISLNK(mode1))50score = 500;51else52score = 250;53return score;54}
55
56static void *fill_tree_desc_strict(struct tree_desc *desc,57const struct object_id *hash)58{
59void *buffer;60enum object_type type;61unsigned long size;62
63buffer = repo_read_object_file(the_repository, hash, &type, &size);64if (!buffer)65die("unable to read tree (%s)", oid_to_hex(hash));66if (type != OBJ_TREE)67die("%s is not a tree", oid_to_hex(hash));68init_tree_desc(desc, hash, buffer, size);69return buffer;70}
71
72static int base_name_entries_compare(const struct name_entry *a,73const struct name_entry *b)74{
75return base_name_compare(a->path, tree_entry_len(a), a->mode,76b->path, tree_entry_len(b), b->mode);77}
78
79/*
80* Inspect two trees, and give a score that tells how similar they are.
81*/
82static int score_trees(const struct object_id *hash1, const struct object_id *hash2)83{
84struct tree_desc one;85struct tree_desc two;86void *one_buf = fill_tree_desc_strict(&one, hash1);87void *two_buf = fill_tree_desc_strict(&two, hash2);88int score = 0;89
90for (;;) {91int cmp;92
93if (one.size && two.size)94cmp = base_name_entries_compare(&one.entry, &two.entry);95else if (one.size)96/* two lacks this entry */97cmp = -1;98else if (two.size)99/* two has more entries */100cmp = 1;101else102break;103
104if (cmp < 0) {105/* path1 does not appear in two */106score += score_missing(one.entry.mode);107update_tree_entry(&one);108} else if (cmp > 0) {109/* path2 does not appear in one */110score += score_missing(two.entry.mode);111update_tree_entry(&two);112} else {113/* path appears in both */114if (!oideq(&one.entry.oid, &two.entry.oid)) {115/* they are different */116score += score_differs(one.entry.mode,117two.entry.mode);118} else {119/* same subtree or blob */120score += score_matches(one.entry.mode,121two.entry.mode);122}123update_tree_entry(&one);124update_tree_entry(&two);125}126}127free(one_buf);128free(two_buf);129return score;130}
131
132/*
133* Match one itself and its subtrees with two and pick the best match.
134*/
135static void match_trees(const struct object_id *hash1,136const struct object_id *hash2,137int *best_score,138char **best_match,139const char *base,140int recurse_limit)141{
142struct tree_desc one;143void *one_buf = fill_tree_desc_strict(&one, hash1);144
145while (one.size) {146const char *path;147const struct object_id *elem;148unsigned short mode;149int score;150
151elem = tree_entry_extract(&one, &path, &mode);152if (!S_ISDIR(mode))153goto next;154score = score_trees(elem, hash2);155if (*best_score < score) {156free(*best_match);157*best_match = xstrfmt("%s%s", base, path);158*best_score = score;159}160if (recurse_limit) {161char *newbase = xstrfmt("%s%s/", base, path);162match_trees(elem, hash2, best_score, best_match,163newbase, recurse_limit - 1);164free(newbase);165}166
167next:168update_tree_entry(&one);169}170free(one_buf);171}
172
173/*
174* A tree "oid1" has a subdirectory at "prefix". Come up with a tree object by
175* replacing it with another tree "oid2".
176*/
177static int splice_tree(const struct object_id *oid1, const char *prefix,178const struct object_id *oid2, struct object_id *result)179{
180char *subpath;181int toplen;182char *buf;183unsigned long sz;184struct tree_desc desc;185unsigned char *rewrite_here;186const struct object_id *rewrite_with;187struct object_id subtree;188enum object_type type;189int status;190
191subpath = strchrnul(prefix, '/');192toplen = subpath - prefix;193if (*subpath)194subpath++;195
196buf = repo_read_object_file(the_repository, oid1, &type, &sz);197if (!buf)198die("cannot read tree %s", oid_to_hex(oid1));199init_tree_desc(&desc, oid1, buf, sz);200
201rewrite_here = NULL;202while (desc.size) {203const char *name;204unsigned short mode;205
206tree_entry_extract(&desc, &name, &mode);207if (strlen(name) == toplen &&208!memcmp(name, prefix, toplen)) {209if (!S_ISDIR(mode))210die("entry %s in tree %s is not a tree", name,211oid_to_hex(oid1));212
213/*214* We cast here for two reasons:
215*
216* - to flip the "char *" (for the path) to "unsigned
217* char *" (for the hash stored after it)
218*
219* - to discard the "const"; this is OK because we
220* know it points into our non-const "buf"
221*/
222rewrite_here = (unsigned char *)(desc.entry.path +223strlen(desc.entry.path) +2241);225break;226}227update_tree_entry(&desc);228}229if (!rewrite_here)230die("entry %.*s not found in tree %s", toplen, prefix,231oid_to_hex(oid1));232if (*subpath) {233struct object_id tree_oid;234oidread(&tree_oid, rewrite_here, the_repository->hash_algo);235status = splice_tree(&tree_oid, subpath, oid2, &subtree);236if (status)237return status;238rewrite_with = &subtree;239} else {240rewrite_with = oid2;241}242hashcpy(rewrite_here, rewrite_with->hash, the_repository->hash_algo);243status = write_object_file(buf, sz, OBJ_TREE, result);244free(buf);245return status;246}
247
248/*
249* We are trying to come up with a merge between one and two that
250* results in a tree shape similar to one. The tree two might
251* correspond to a subtree of one, in which case it needs to be
252* shifted down by prefixing otherwise empty directories. On the
253* other hand, it could cover tree one and we might need to pick a
254* subtree of it.
255*/
256void shift_tree(struct repository *r,257const struct object_id *hash1,258const struct object_id *hash2,259struct object_id *shifted,260int depth_limit)261{
262char *add_prefix;263char *del_prefix;264int add_score, del_score;265
266/*267* NEEDSWORK: this limits the recursion depth to hardcoded
268* value '2' to avoid excessive overhead.
269*/
270if (!depth_limit)271depth_limit = 2;272
273add_score = del_score = score_trees(hash1, hash2);274add_prefix = xcalloc(1, 1);275del_prefix = xcalloc(1, 1);276
277/*278* See if one's subtree resembles two; if so we need to prefix
279* two with a few fake trees to match the prefix.
280*/
281match_trees(hash1, hash2, &add_score, &add_prefix, "", depth_limit);282
283/*284* See if two's subtree resembles one; if so we need to
285* pick only subtree of two.
286*/
287match_trees(hash2, hash1, &del_score, &del_prefix, "", depth_limit);288
289/* Assume we do not have to do any shifting */290oidcpy(shifted, hash2);291
292if (add_score < del_score) {293/* We need to pick a subtree of two */294unsigned short mode;295
296if (!*del_prefix)297return;298
299if (get_tree_entry(r, hash2, del_prefix, shifted, &mode))300die("cannot find path %s in tree %s",301del_prefix, oid_to_hex(hash2));302return;303}304
305if (!*add_prefix)306return;307
308splice_tree(hash1, add_prefix, hash2, shifted);309}
310
311/*
312* The user says the trees will be shifted by this much.
313* Unfortunately we cannot fundamentally tell which one to
314* be prefixed, as recursive merge can work in either direction.
315*/
316void shift_tree_by(struct repository *r,317const struct object_id *hash1,318const struct object_id *hash2,319struct object_id *shifted,320const char *shift_prefix)321{
322struct object_id sub1, sub2;323unsigned short mode1, mode2;324unsigned candidate = 0;325
326/* Can hash2 be a tree at shift_prefix in tree hash1? */327if (!get_tree_entry(r, hash1, shift_prefix, &sub1, &mode1) &&328S_ISDIR(mode1))329candidate |= 1;330
331/* Can hash1 be a tree at shift_prefix in tree hash2? */332if (!get_tree_entry(r, hash2, shift_prefix, &sub2, &mode2) &&333S_ISDIR(mode2))334candidate |= 2;335
336if (candidate == 3) {337/* Both are plausible -- we need to evaluate the score */338int best_score = score_trees(hash1, hash2);339int score;340
341candidate = 0;342score = score_trees(&sub1, hash2);343if (score > best_score) {344candidate = 1;345best_score = score;346}347score = score_trees(&sub2, hash1);348if (score > best_score)349candidate = 2;350}351
352if (!candidate) {353/* Neither is plausible -- do not shift */354oidcpy(shifted, hash2);355return;356}357
358if (candidate == 1)359/*360* shift tree2 down by adding shift_prefix above it
361* to match tree1.
362*/
363splice_tree(hash1, shift_prefix, hash2, shifted);364else365/*366* shift tree2 up by removing shift_prefix from it
367* to match tree1.
368*/
369oidcpy(shifted, &sub2);370}
371