git/tree-diff.c

/*
 * Helper functions for tree diff generation
 */

#define USE_THE_REPOSITORY_VARIABLE

#include "git-compat-util.h"
#include "diff.h"
#include "diffcore.h"
#include "hash.h"
#include "tree.h"
#include "tree-walk.h"
#include "environment.h"
#include "repository.h"

/*
 * Some mode bits are also used internally for computations.
 *
 * They *must* not overlap with any valid modes, and they *must* not be emitted
 * to outside world - i.e. appear on disk or network. In other words, it's just
 * temporary fields, which we internally use, but they have to stay in-house.
 *
 * ( such approach is valid, as standard S_IF* fits into 16 bits, and in Git
 *   codebase mode is `unsigned int` which is assumed to be at least 32 bits )
 */

#define S_DIFFTREE_IFXMIN_NEQ …

/*
 * internal mode marker, saying a tree entry != entry of tp[imin]
 * (see ll_diff_tree_paths for what it means there)
 *
 * we will update/use/emit entry for diff only with it unset.
 */
#define S_IFXMIN_NEQ …

#define FAST_ARRAY_ALLOC(x, nr) …
#define FAST_ARRAY_FREE(x, nr) …

static struct combine_diff_path *ll_diff_tree_paths(
	struct combine_diff_path *p, const struct object_id *oid,
	const struct object_id **parents_oid, int nparent,
	struct strbuf *base, struct diff_options *opt,
	int depth);
static void ll_diff_tree_oid(const struct object_id *old_oid,
			     const struct object_id *new_oid,
			     struct strbuf *base, struct diff_options *opt);

/*
 * Compare two tree entries, taking into account only path/S_ISDIR(mode),
 * but not their sha1's.
 *
 * NOTE files and directories *always* compare differently, even when having
 *      the same name - thanks to base_name_compare().
 *
 * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty,
 *      so that they sort *after* valid tree entries.
 *
 *      Due to this convention, if trees are scanned in sorted order, all
 *      non-empty descriptors will be processed first.
 */
static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
{ … }


/*
 * convert path -> opt->diff_*() callbacks
 *
 * emits diff to first parent only, and tells diff tree-walker that we are done
 * with p and it can be freed.
 */
static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_diff_path *p)
{ … }


/*
 * Make a new combine_diff_path from path/mode/sha1
 * and append it to paths list tail.
 *
 * Memory for created elements could be reused:
 *
 *	- if last->next == NULL, the memory is allocated;
 *
 *	- if last->next != NULL, it is assumed that p=last->next was returned
 *	  earlier by this function, and p->next was *not* modified.
 *	  The memory is then reused from p.
 *
 * so for clients,
 *
 * - if you do need to keep the element
 *
 *	p = path_appendnew(p, ...);
 *	process(p);
 *	p->next = NULL;
 *
 * - if you don't need to keep the element after processing
 *
 *	pprev = p;
 *	p = path_appendnew(p, ...);
 *	process(p);
 *	p = pprev;
 *	; don't forget to free tail->next in the end
 *
 * p->parent[] remains uninitialized.
 */
static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
	int nparent, const struct strbuf *base, const char *path, int pathlen,
	unsigned mode, const struct object_id *oid)
{ … }

/*
 * new path should be added to combine diff
 *
 * 3 cases on how/when it should be called and behaves:
 *
 *	 t, !tp		-> path added, all parents lack it
 *	!t,  tp		-> path removed from all parents
 *	 t,  tp		-> path modified/added
 *			   (M for tp[i]=tp[imin], A otherwise)
 */
static struct combine_diff_path *emit_path(struct combine_diff_path *p,
	struct strbuf *base, struct diff_options *opt, int nparent,
	struct tree_desc *t, struct tree_desc *tp,
	int imin, int depth)
{ … }

static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
			       struct diff_options *opt)
{ … }


/*
 * generate paths for combined diff D(sha1,parents_oid[])
 *
 * Resulting paths are appended to combine_diff_path linked list, and also, are
 * emitted on the go via opt->pathchange() callback, so it is possible to
 * process the result as batch or incrementally.
 *
 * The paths are generated scanning new tree and all parents trees
 * simultaneously, similarly to what diff_tree() was doing for 2 trees.
 * The theory behind such scan is as follows:
 *
 *
 * D(T,P1...Pn) calculation scheme
 * -------------------------------
 *
 * D(T,P1...Pn) = D(T,P1) ^ ... ^ D(T,Pn)	(regarding resulting paths set)
 *
 *	D(T,Pj)		- diff between T..Pj
 *	D(T,P1...Pn)	- combined diff from T to parents P1,...,Pn
 *
 *
 * We start from all trees, which are sorted, and compare their entries in
 * lock-step:
 *
 *	 T     P1       Pn
 *	 -     -        -
 *	|t|   |p1|     |pn|
 *	|-|   |--| ... |--|      imin = argmin(p1...pn)
 *	| |   |  |     |  |
 *	|-|   |--|     |--|
 *	|.|   |. |     |. |
 *	 .     .        .
 *	 .     .        .
 *
 * at any time there could be 3 cases:
 *
 *	1)  t < p[imin];
 *	2)  t > p[imin];
 *	3)  t = p[imin].
 *
 * Schematic deduction of what every case means, and what to do, follows:
 *
 * 1)  t < p[imin]  ->  ∀j t ∉ Pj  ->  "+t" ∈ D(T,Pj)  ->  D += "+t";  t↓
 *
 * 2)  t > p[imin]
 *
 *     2.1) ∃j: pj > p[imin]  ->  "-p[imin]" ∉ D(T,Pj)  ->  D += ø;  ∀ pi=p[imin]  pi↓
 *     2.2) ∀i  pi = p[imin]  ->  pi ∉ T  ->  "-pi" ∈ D(T,Pi)  ->  D += "-p[imin]";  ∀i pi↓
 *
 * 3)  t = p[imin]
 *
 *     3.1) ∃j: pj > p[imin]  ->  "+t" ∈ D(T,Pj)  ->  only pi=p[imin] remains to investigate
 *     3.2) pi = p[imin]  ->  investigate δ(t,pi)
 *      |
 *      |
 *      v
 *
 *     3.1+3.2) looking at δ(t,pi) ∀i: pi=p[imin] - if all != ø  ->
 *
 *                       ⎧δ(t,pi)  - if pi=p[imin]
 *              ->  D += ⎨
 *                       ⎩"+t"     - if pi>p[imin]
 *
 *
 *     in any case t↓  ∀ pi=p[imin]  pi↓
 *
 *
 * ~~~~~~~~
 *
 * NOTE
 *
 *	Usual diff D(A,B) is by definition the same as combined diff D(A,[B]),
 *	so this diff paths generator can, and is used, for plain diffs
 *	generation too.
 *
 *	Please keep attention to the common D(A,[B]) case when working on the
 *	code, in order not to slow it down.
 *
 * NOTE
 *	nparent must be > 0.
 */


/* ∀ pi=p[imin]  pi↓ */
static inline void update_tp_entries(struct tree_desc *tp, int nparent)
{ … }

static struct combine_diff_path *ll_diff_tree_paths(
	struct combine_diff_path *p, const struct object_id *oid,
	const struct object_id **parents_oid, int nparent,
	struct strbuf *base, struct diff_options *opt,
	int depth)
{ … }

struct combine_diff_path *diff_tree_paths(
	struct combine_diff_path *p, const struct object_id *oid,
	const struct object_id **parents_oid, int nparent,
	struct strbuf *base, struct diff_options *opt)
{ … }

/*
 * Does it look like the resulting diff might be due to a rename?
 *  - single entry
 *  - not a valid previous file
 */
static inline int diff_might_be_rename(void)
{ … }

static void try_to_follow_renames(const struct object_id *old_oid,
				  const struct object_id *new_oid,
				  struct strbuf *base, struct diff_options *opt)
{ … }

static void ll_diff_tree_oid(const struct object_id *old_oid,
			     const struct object_id *new_oid,
			     struct strbuf *base, struct diff_options *opt)
{ … }

void diff_tree_oid(const struct object_id *old_oid,
		   const struct object_id *new_oid,
		   const char *base_str, struct diff_options *opt)
{ … }

void diff_root_tree_oid(const struct object_id *new_oid,
			const char *base,
			struct diff_options *opt)
{ … }