You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


/*
 * Copyright (C) the libgit2 contributors. All rights reserved.
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */

#include "diff_generate.h"

#include "diff.h"
#include "patch_generate.h"
#include "fileops.h"
#include "config.h"
#include "attr_file.h"
#include "filter.h"
#include "pathspec.h"
#include "index.h"
#include "odb.h"
#include "submodule.h"

#define DIFF_FLAG_IS_SET(DIFF,FLAG) \
	(((DIFF)->base.opts.flags & (FLAG)) != 0)
#define DIFF_FLAG_ISNT_SET(DIFF,FLAG) \
	(((DIFF)->base.opts.flags & (FLAG)) == 0)
#define DIFF_FLAG_SET(DIFF,FLAG,VAL) (DIFF)->base.opts.flags = \
	(VAL) ? ((DIFF)->base.opts.flags | (FLAG)) : \
	((DIFF)->base.opts.flags & ~(FLAG))

typedef struct {
	struct git_diff base;

	git_vector pathspec;

	uint32_t diffcaps;
	bool index_updated;
} git_diff_generated;

static git_diff_delta *diff_delta__alloc(
	git_diff_generated *diff,
	git_delta_t status,
	const char *path)
{
	git_diff_delta *delta = git__calloc(1, sizeof(git_diff_delta));
	if (!delta)
		return NULL;

	delta->old_file.path = git_pool_strdup(&diff->base.pool, path);
	if (delta->old_file.path == NULL) {
		git__free(delta);
		return NULL;
	}

	delta->new_file.path = delta->old_file.path;

	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_REVERSE)) {
		switch (status) {
		case GIT_DELTA_ADDED:   status = GIT_DELTA_DELETED; break;
		case GIT_DELTA_DELETED: status = GIT_DELTA_ADDED; break;
		default: break; /* leave other status values alone */
		}
	}
	delta->status = status;

	return delta;
}

static int diff_insert_delta(
	git_diff_generated *diff,
	git_diff_delta *delta,
	const char *matched_pathspec)
{
	int error = 0;

	if (diff->base.opts.notify_cb) {
		error = diff->base.opts.notify_cb(
			&diff->base, delta, matched_pathspec, diff->base.opts.payload);

		if (error) {
			git__free(delta);

			if (error > 0)	/* positive value means to skip this delta */
				return 0;
			else			/* negative value means to cancel diff */
				return giterr_set_after_callback_function(error, "git_diff");
		}
	}

	if ((error = git_vector_insert(&diff->base.deltas, delta)) < 0)
		git__free(delta);

	return error;
}

static bool diff_pathspec_match(
	const char **matched_pathspec,
	git_diff_generated *diff,
	const git_index_entry *entry)
{
	bool disable_pathspec_match =
		DIFF_FLAG_IS_SET(diff, GIT_DIFF_DISABLE_PATHSPEC_MATCH);

	/* If we're disabling fnmatch, then the iterator has already applied
	 * the filters to the files for us and we don't have to do anything.
	 * However, this only applies to *files* - the iterator will include
	 * directories that we need to recurse into when not autoexpanding,
	 * so we still need to apply the pathspec match to directories.
	 */
	if ((S_ISLNK(entry->mode) || S_ISREG(entry->mode)) &&
		disable_pathspec_match) {
		*matched_pathspec = entry->path;
		return true;
	}

	return git_pathspec__match(
		&diff->pathspec, entry->path, disable_pathspec_match,
		DIFF_FLAG_IS_SET(diff, GIT_DIFF_IGNORE_CASE),
		matched_pathspec, NULL);
}

static int diff_delta__from_one(
	git_diff_generated *diff,
	git_delta_t status,
	const git_index_entry *oitem,
	const git_index_entry *nitem)
{
	const git_index_entry *entry = nitem;
	bool has_old = false;
	git_diff_delta *delta;
	const char *matched_pathspec;

	assert((oitem != NULL) ^ (nitem != NULL));

	if (oitem) {
		entry = oitem;
		has_old = true;
	}

	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_REVERSE))
		has_old = !has_old;

	if ((entry->flags & GIT_IDXENTRY_VALID) != 0)
		return 0;

	if (status == GIT_DELTA_IGNORED &&
		DIFF_FLAG_ISNT_SET(diff, GIT_DIFF_INCLUDE_IGNORED))
		return 0;

	if (status == GIT_DELTA_UNTRACKED &&
		DIFF_FLAG_ISNT_SET(diff, GIT_DIFF_INCLUDE_UNTRACKED))
		return 0;

	if (status == GIT_DELTA_UNREADABLE &&
		DIFF_FLAG_ISNT_SET(diff, GIT_DIFF_INCLUDE_UNREADABLE))
		return 0;

	if (!diff_pathspec_match(&matched_pathspec, diff, entry))
		return 0;

	delta = diff_delta__alloc(diff, status, entry->path);
	GITERR_CHECK_ALLOC(delta);

	/* This fn is just for single-sided diffs */
	assert(status != GIT_DELTA_MODIFIED);
	delta->nfiles = 1;

	if (has_old) {
		delta->old_file.mode = entry->mode;
		delta->old_file.size = entry->file_size;
		delta->old_file.flags |= GIT_DIFF_FLAG_EXISTS;
		git_oid_cpy(&delta->old_file.id, &entry->id);
		delta->old_file.id_abbrev = GIT_OID_HEXSZ;
	} else /* ADDED, IGNORED, UNTRACKED */ {
		delta->new_file.mode = entry->mode;
		delta->new_file.size = entry->file_size;
		delta->new_file.flags |= GIT_DIFF_FLAG_EXISTS;
		git_oid_cpy(&delta->new_file.id, &entry->id);
		delta->new_file.id_abbrev = GIT_OID_HEXSZ;
	}

	delta->old_file.flags |= GIT_DIFF_FLAG_VALID_ID;

	if (has_old || !git_oid_iszero(&delta->new_file.id))
		delta->new_file.flags |= GIT_DIFF_FLAG_VALID_ID;

	return diff_insert_delta(diff, delta, matched_pathspec);
}

static int diff_delta__from_two(
	git_diff_generated *diff,
	git_delta_t status,
	const git_index_entry *old_entry,
	uint32_t old_mode,
	const git_index_entry *new_entry,
	uint32_t new_mode,
	const git_oid *new_id,
	const char *matched_pathspec)
{
	const git_oid *old_id = &old_entry->id;
	git_diff_delta *delta;
	const char *canonical_path = old_entry->path;

	if (status == GIT_DELTA_UNMODIFIED &&
		DIFF_FLAG_ISNT_SET(diff, GIT_DIFF_INCLUDE_UNMODIFIED))
		return 0;

	if (!new_id)
		new_id = &new_entry->id;

	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_REVERSE)) {
		uint32_t temp_mode = old_mode;
		const git_index_entry *temp_entry = old_entry;
		const git_oid *temp_id = old_id;

		old_entry = new_entry;
		new_entry = temp_entry;
		old_mode = new_mode;
		new_mode = temp_mode;
		old_id = new_id;
		new_id = temp_id;
	}

	delta = diff_delta__alloc(diff, status, canonical_path);
	GITERR_CHECK_ALLOC(delta);
	delta->nfiles = 2;

	if (!git_index_entry_is_conflict(old_entry)) {
		delta->old_file.size = old_entry->file_size;
		delta->old_file.mode = old_mode;
		git_oid_cpy(&delta->old_file.id, old_id);
		delta->old_file.id_abbrev = GIT_OID_HEXSZ;
		delta->old_file.flags |= GIT_DIFF_FLAG_VALID_ID |
			GIT_DIFF_FLAG_EXISTS;
	}

	if (!git_index_entry_is_conflict(new_entry)) {
		git_oid_cpy(&delta->new_file.id, new_id);
		delta->new_file.id_abbrev = GIT_OID_HEXSZ;
		delta->new_file.size = new_entry->file_size;
		delta->new_file.mode = new_mode;
		delta->old_file.flags |= GIT_DIFF_FLAG_EXISTS;
		delta->new_file.flags |= GIT_DIFF_FLAG_EXISTS;

		if (!git_oid_iszero(&new_entry->id))
			delta->new_file.flags |= GIT_DIFF_FLAG_VALID_ID;
	}

	return diff_insert_delta(diff, delta, matched_pathspec);
}

static git_diff_delta *diff_delta__last_for_item(
	git_diff_generated *diff,
	const git_index_entry *item)
{
	git_diff_delta *delta = git_vector_last(&diff->base.deltas);
	if (!delta)
		return NULL;

	switch (delta->status) {
	case GIT_DELTA_UNMODIFIED:
	case GIT_DELTA_DELETED:
		if (git_oid__cmp(&delta->old_file.id, &item->id) == 0)
			return delta;
		break;
	case GIT_DELTA_ADDED:
		if (git_oid__cmp(&delta->new_file.id, &item->id) == 0)
			return delta;
		break;
	case GIT_DELTA_UNREADABLE:
	case GIT_DELTA_UNTRACKED:
		if (diff->base.strcomp(delta->new_file.path, item->path) == 0 &&
			git_oid__cmp(&delta->new_file.id, &item->id) == 0)
			return delta;
		break;
	case GIT_DELTA_MODIFIED:
		if (git_oid__cmp(&delta->old_file.id, &item->id) == 0 ||
			git_oid__cmp(&delta->new_file.id, &item->id) == 0)
			return delta;
		break;
	default:
		break;
	}

	return NULL;
}

static char *diff_strdup_prefix(git_pool *pool, const char *prefix)
{
	size_t len = strlen(prefix);

	/* append '/' at end if needed */
	if (len > 0 && prefix[len - 1] != '/')
		return git_pool_strcat(pool, prefix, "/");
	else
		return git_pool_strndup(pool, prefix, len + 1);
}

GIT_INLINE(const char *) diff_delta__i2w_path(const git_diff_delta *delta)
{
	return delta->old_file.path ?
		delta->old_file.path : delta->new_file.path;
}

int git_diff_delta__i2w_cmp(const void *a, const void *b)
{
	const git_diff_delta *da = a, *db = b;
	int val = strcmp(diff_delta__i2w_path(da), diff_delta__i2w_path(db));
	return val ? val : ((int)da->status - (int)db->status);
}

int git_diff_delta__i2w_casecmp(const void *a, const void *b)
{
	const git_diff_delta *da = a, *db = b;
	int val = strcasecmp(diff_delta__i2w_path(da), diff_delta__i2w_path(db));
	return val ? val : ((int)da->status - (int)db->status);
}

bool git_diff_delta__should_skip(
	const git_diff_options *opts, const git_diff_delta *delta)
{
	uint32_t flags = opts ? opts->flags : 0;

	if (delta->status == GIT_DELTA_UNMODIFIED &&
		(flags & GIT_DIFF_INCLUDE_UNMODIFIED) == 0)
		return true;

	if (delta->status == GIT_DELTA_IGNORED &&
		(flags & GIT_DIFF_INCLUDE_IGNORED) == 0)
		return true;

	if (delta->status == GIT_DELTA_UNTRACKED &&
		(flags & GIT_DIFF_INCLUDE_UNTRACKED) == 0)
		return true;

	if (delta->status == GIT_DELTA_UNREADABLE &&
		(flags & GIT_DIFF_INCLUDE_UNREADABLE) == 0)
		return true;

	return false;
}


static const char *diff_mnemonic_prefix(
	git_iterator_type_t type, bool left_side)
{
	const char *pfx = "";

	switch (type) {
	case GIT_ITERATOR_TYPE_EMPTY:   pfx = "c"; break;
	case GIT_ITERATOR_TYPE_TREE:    pfx = "c"; break;
	case GIT_ITERATOR_TYPE_INDEX:   pfx = "i"; break;
	case GIT_ITERATOR_TYPE_WORKDIR: pfx = "w"; break;
	case GIT_ITERATOR_TYPE_FS:      pfx = left_side ? "1" : "2"; break;
	default: break;
	}

	/* note: without a deeper look at pathspecs, there is no easy way
	 * to get the (o)bject / (w)ork tree mnemonics working...
	 */

	return pfx;
}

void git_diff__set_ignore_case(git_diff *diff, bool ignore_case)
{
	if (!ignore_case) {
		diff->opts.flags &= ~GIT_DIFF_IGNORE_CASE;

		diff->strcomp    = git__strcmp;
		diff->strncomp   = git__strncmp;
		diff->pfxcomp    = git__prefixcmp;
		diff->entrycomp  = git_diff__entry_cmp;

		git_vector_set_cmp(&diff->deltas, git_diff_delta__cmp);
	} else {
		diff->opts.flags |= GIT_DIFF_IGNORE_CASE;

		diff->strcomp    = git__strcasecmp;
		diff->strncomp   = git__strncasecmp;
		diff->pfxcomp    = git__prefixcmp_icase;
		diff->entrycomp  = git_diff__entry_icmp;

		git_vector_set_cmp(&diff->deltas, git_diff_delta__casecmp);
	}

	git_vector_sort(&diff->deltas);
}

static void diff_generated_free(git_diff *d)
{
	git_diff_generated *diff = (git_diff_generated *)d;

	git_attr_session__free(&diff->base.attrsession);
	git_vector_free_deep(&diff->base.deltas);

	git_pathspec__vfree(&diff->pathspec);
	git_pool_clear(&diff->base.pool);

	git__memzero(diff, sizeof(*diff));
	git__free(diff);
}

static git_diff_generated *diff_generated_alloc(
	git_repository *repo,
	git_iterator *old_iter,
	git_iterator *new_iter)
{
	git_diff_generated *diff;
	git_diff_options dflt = GIT_DIFF_OPTIONS_INIT;

	assert(repo && old_iter && new_iter);

	if ((diff = git__calloc(1, sizeof(git_diff_generated))) == NULL)
		return NULL;

	GIT_REFCOUNT_INC(&diff->base);
	diff->base.type = GIT_DIFF_TYPE_GENERATED;
	diff->base.repo = repo;
	diff->base.old_src = old_iter->type;
	diff->base.new_src = new_iter->type;
	diff->base.patch_fn = git_patch_generated_from_diff;
	diff->base.free_fn = diff_generated_free;
	git_attr_session__init(&diff->base.attrsession, repo);
	memcpy(&diff->base.opts, &dflt, sizeof(git_diff_options));

	git_pool_init(&diff->base.pool, 1);

	if (git_vector_init(&diff->base.deltas, 0, git_diff_delta__cmp) < 0) {
		git_diff_free(&diff->base);
		return NULL;
	}

	/* Use case-insensitive compare if either iterator has
	 * the ignore_case bit set */
	git_diff__set_ignore_case(
		&diff->base,
		git_iterator_ignore_case(old_iter) ||
		git_iterator_ignore_case(new_iter));

	return diff;
}

static int diff_generated_apply_options(
	git_diff_generated *diff,
	const git_diff_options *opts)
{
	git_config *cfg = NULL;
	git_repository *repo = diff->base.repo;
	git_pool *pool = &diff->base.pool;
	int val;

	if (opts) {
		/* copy user options (except case sensitivity info from iterators) */
		bool icase = DIFF_FLAG_IS_SET(diff, GIT_DIFF_IGNORE_CASE);
		memcpy(&diff->base.opts, opts, sizeof(diff->base.opts));
		DIFF_FLAG_SET(diff, GIT_DIFF_IGNORE_CASE, icase);

		/* initialize pathspec from options */
		if (git_pathspec__vinit(&diff->pathspec, &opts->pathspec, pool) < 0)
			return -1;
	}

	/* flag INCLUDE_TYPECHANGE_TREES implies INCLUDE_TYPECHANGE */
	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_INCLUDE_TYPECHANGE_TREES))
		diff->base.opts.flags |= GIT_DIFF_INCLUDE_TYPECHANGE;

	/* flag INCLUDE_UNTRACKED_CONTENT implies INCLUDE_UNTRACKED */
	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_SHOW_UNTRACKED_CONTENT))
		diff->base.opts.flags |= GIT_DIFF_INCLUDE_UNTRACKED;

	/* load config values that affect diff behavior */
	if ((val = git_repository_config_snapshot(&cfg, repo)) < 0)
		return val;

	if (!git_config__cvar(&val, cfg, GIT_CVAR_SYMLINKS) && val)
		diff->diffcaps |= GIT_DIFFCAPS_HAS_SYMLINKS;

	if (!git_config__cvar(&val, cfg, GIT_CVAR_IGNORESTAT) && val)
		diff->diffcaps |= GIT_DIFFCAPS_IGNORE_STAT;

	if ((diff->base.opts.flags & GIT_DIFF_IGNORE_FILEMODE) == 0 &&
		!git_config__cvar(&val, cfg, GIT_CVAR_FILEMODE) && val)
		diff->diffcaps |= GIT_DIFFCAPS_TRUST_MODE_BITS;

	if (!git_config__cvar(&val, cfg, GIT_CVAR_TRUSTCTIME) && val)
		diff->diffcaps |= GIT_DIFFCAPS_TRUST_CTIME;

	/* Don't set GIT_DIFFCAPS_USE_DEV - compile time option in core git */

	/* If not given explicit `opts`, check `diff.xyz` configs */
	if (!opts) {
		int context = git_config__get_int_force(cfg, "diff.context", 3);
		diff->base.opts.context_lines = context >= 0 ? (uint32_t)context : 3;

		/* add other defaults here */
	}

	/* Reverse src info if diff is reversed */
	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_REVERSE)) {
		git_iterator_type_t tmp_src = diff->base.old_src;
		diff->base.old_src = diff->base.new_src;
		diff->base.new_src = tmp_src;
	}

	/* Unset UPDATE_INDEX unless diffing workdir and index */
	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_UPDATE_INDEX) &&
		(!(diff->base.old_src == GIT_ITERATOR_TYPE_WORKDIR ||
		   diff->base.new_src == GIT_ITERATOR_TYPE_WORKDIR) ||
		 !(diff->base.old_src == GIT_ITERATOR_TYPE_INDEX ||
		   diff->base.new_src == GIT_ITERATOR_TYPE_INDEX)))
		diff->base.opts.flags &= ~GIT_DIFF_UPDATE_INDEX;

	/* if ignore_submodules not explicitly set, check diff config */
	if (diff->base.opts.ignore_submodules <= 0) {
		 git_config_entry *entry;
		git_config__lookup_entry(&entry, cfg, "diff.ignoresubmodules", true);

		if (entry && git_submodule_parse_ignore(
				&diff->base.opts.ignore_submodules, entry->value) < 0)
			giterr_clear();
		git_config_entry_free(entry);
	}

	/* if either prefix is not set, figure out appropriate value */
	if (!diff->base.opts.old_prefix || !diff->base.opts.new_prefix) {
		const char *use_old = DIFF_OLD_PREFIX_DEFAULT;
		const char *use_new = DIFF_NEW_PREFIX_DEFAULT;

		if (git_config__get_bool_force(cfg, "diff.noprefix", 0))
			use_old = use_new = "";
		else if (git_config__get_bool_force(cfg, "diff.mnemonicprefix", 0)) {
			use_old = diff_mnemonic_prefix(diff->base.old_src, true);
			use_new = diff_mnemonic_prefix(diff->base.new_src, false);
		}

		if (!diff->base.opts.old_prefix)
			diff->base.opts.old_prefix = use_old;
		if (!diff->base.opts.new_prefix)
			diff->base.opts.new_prefix = use_new;
	}

	/* strdup prefix from pool so we're not dependent on external data */
	diff->base.opts.old_prefix = diff_strdup_prefix(pool, diff->base.opts.old_prefix);
	diff->base.opts.new_prefix = diff_strdup_prefix(pool, diff->base.opts.new_prefix);

	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_REVERSE)) {
		const char *tmp_prefix = diff->base.opts.old_prefix;
		diff->base.opts.old_prefix  = diff->base.opts.new_prefix;
		diff->base.opts.new_prefix  = tmp_prefix;
	}

	git_config_free(cfg);

	/* check strdup results for error */
	return (!diff->base.opts.old_prefix || !diff->base.opts.new_prefix) ? -1 : 0;
}

int git_diff__oid_for_file(
	git_oid *out,
	git_diff *diff,
	const char *path,
	uint16_t mode,
	git_off_t size)
{
	git_index_entry entry;

	memset(&entry, 0, sizeof(entry));
	entry.mode = mode;
	entry.file_size = size;
	entry.path = (char *)path;

	return git_diff__oid_for_entry(out, diff, &entry, mode, NULL);
}

int git_diff__oid_for_entry(
	git_oid *out,
	git_diff *d,
	const git_index_entry *src,
	uint16_t mode,
	const git_oid *update_match)
{
	git_diff_generated *diff;
	git_buf full_path = GIT_BUF_INIT;
	git_index_entry entry = *src;
	git_filter_list *fl = NULL;
	int error = 0;

	assert(d->type == GIT_DIFF_TYPE_GENERATED);
	diff = (git_diff_generated *)d;

	memset(out, 0, sizeof(*out));

	if (git_buf_joinpath(&full_path,
		git_repository_workdir(diff->base.repo), entry.path) < 0)
		return -1;

	if (!mode) {
		struct stat st;

		diff->base.perf.stat_calls++;

		if (p_stat(full_path.ptr, &st) < 0) {
			error = git_path_set_error(errno, entry.path, "stat");
			git_buf_free(&full_path);
			return error;
		}

		git_index_entry__init_from_stat(&entry,
			&st, (diff->diffcaps & GIT_DIFFCAPS_TRUST_MODE_BITS) != 0);
	}

	/* calculate OID for file if possible */
	if (S_ISGITLINK(mode)) {
		git_submodule *sm;

		if (!git_submodule_lookup(&sm, diff->base.repo, entry.path)) {
			const git_oid *sm_oid = git_submodule_wd_id(sm);
			if (sm_oid)
				git_oid_cpy(out, sm_oid);
			git_submodule_free(sm);
		} else {
			/* if submodule lookup failed probably just in an intermediate
			 * state where some init hasn't happened, so ignore the error
			 */
			giterr_clear();
		}
	} else if (S_ISLNK(mode)) {
		error = git_odb__hashlink(out, full_path.ptr);
		diff->base.perf.oid_calculations++;
	} else if (!git__is_sizet(entry.file_size)) {
		giterr_set(GITERR_OS, "file size overflow (for 32-bits) on '%s'",
			entry.path);
		error = -1;
	} else if (!(error = git_filter_list_load(&fl,
		diff->base.repo, NULL, entry.path,
		GIT_FILTER_TO_ODB, GIT_FILTER_ALLOW_UNSAFE)))
	{
		int fd = git_futils_open_ro(full_path.ptr);
		if (fd < 0)
			error = fd;
		else {
			error = git_odb__hashfd_filtered(
				out, fd, (size_t)entry.file_size, GIT_OBJ_BLOB, fl);
			p_close(fd);
			diff->base.perf.oid_calculations++;
		}

		git_filter_list_free(fl);
	}

	/* update index for entry if requested */
	if (!error && update_match && git_oid_equal(out, update_match)) {
		git_index *idx;
		git_index_entry updated_entry;

		memcpy(&updated_entry, &entry, sizeof(git_index_entry));
		updated_entry.mode = mode;
		git_oid_cpy(&updated_entry.id, out);

		if (!(error = git_repository_index__weakptr(&idx,
			diff->base.repo))) {
			error = git_index_add(idx, &updated_entry);
			diff->index_updated = true;
		}
 	}

	git_buf_free(&full_path);
	return error;
}

typedef struct {
	git_repository *repo;
	git_iterator *old_iter;
	git_iterator *new_iter;
	const git_index_entry *oitem;
	const git_index_entry *nitem;
} diff_in_progress;

#define MODE_BITS_MASK 0000777

static int maybe_modified_submodule(
	git_delta_t *status,
	git_oid *found_oid,
	git_diff_generated *diff,
	diff_in_progress *info)
{
	int error = 0;
	git_submodule *sub;
	unsigned int sm_status = 0;
	git_submodule_ignore_t ign = diff->base.opts.ignore_submodules;

	*status = GIT_DELTA_UNMODIFIED;

	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_IGNORE_SUBMODULES) ||
		ign == GIT_SUBMODULE_IGNORE_ALL)
		return 0;

	if ((error = git_submodule_lookup(
			&sub, diff->base.repo, info->nitem->path)) < 0) {

		/* GIT_EEXISTS means dir with .git in it was found - ignore it */
		if (error == GIT_EEXISTS) {
			giterr_clear();
			error = 0;
		}
		return error;
	}

	if (ign <= 0 && git_submodule_ignore(sub) == GIT_SUBMODULE_IGNORE_ALL)
		/* ignore it */;
	else if ((error = git_submodule__status(
			&sm_status, NULL, NULL, found_oid, sub, ign)) < 0)
		/* return error below */;

	/* check IS_WD_UNMODIFIED because this case is only used
	 * when the new side of the diff is the working directory
	 */
	else if (!GIT_SUBMODULE_STATUS_IS_WD_UNMODIFIED(sm_status))
		*status = GIT_DELTA_MODIFIED;

	/* now that we have a HEAD OID, check if HEAD moved */
	else if ((sm_status & GIT_SUBMODULE_STATUS_IN_WD) != 0 &&
		!git_oid_equal(&info->oitem->id, found_oid))
		*status = GIT_DELTA_MODIFIED;

	git_submodule_free(sub);
	return error;
}

static int maybe_modified(
	git_diff_generated *diff,
	diff_in_progress *info)
{
	git_oid noid;
	git_delta_t status = GIT_DELTA_MODIFIED;
	const git_index_entry *oitem = info->oitem;
	const git_index_entry *nitem = info->nitem;
	unsigned int omode = oitem->mode;
	unsigned int nmode = nitem->mode;
	bool new_is_workdir = (info->new_iter->type == GIT_ITERATOR_TYPE_WORKDIR);
	bool modified_uncertain = false;
	const char *matched_pathspec;
	int error = 0;

	if (!diff_pathspec_match(&matched_pathspec, diff, oitem))
		return 0;

	memset(&noid, 0, sizeof(noid));

	/* on platforms with no symlinks, preserve mode of existing symlinks */
	if (S_ISLNK(omode) && S_ISREG(nmode) && new_is_workdir &&
		!(diff->diffcaps & GIT_DIFFCAPS_HAS_SYMLINKS))
		nmode = omode;

	/* on platforms with no execmode, just preserve old mode */
	if (!(diff->diffcaps & GIT_DIFFCAPS_TRUST_MODE_BITS) &&
		(nmode & MODE_BITS_MASK) != (omode & MODE_BITS_MASK) &&
		new_is_workdir)
		nmode = (nmode & ~MODE_BITS_MASK) | (omode & MODE_BITS_MASK);

	/* if one side is a conflict, mark the whole delta as conflicted */
	if (git_index_entry_is_conflict(oitem) ||
			git_index_entry_is_conflict(nitem)) {
		status = GIT_DELTA_CONFLICTED;

	/* support "assume unchanged" (poorly, b/c we still stat everything) */
	} else if ((oitem->flags & GIT_IDXENTRY_VALID) != 0) {
		status = GIT_DELTA_UNMODIFIED;

	/* support "skip worktree" index bit */
	} else if ((oitem->flags_extended & GIT_IDXENTRY_SKIP_WORKTREE) != 0) {
		status = GIT_DELTA_UNMODIFIED;

	/* if basic type of file changed, then split into delete and add */
	} else if (GIT_MODE_TYPE(omode) != GIT_MODE_TYPE(nmode)) {
		if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_INCLUDE_TYPECHANGE)) {
			status = GIT_DELTA_TYPECHANGE;
		}

		else if (nmode == GIT_FILEMODE_UNREADABLE) {
			if (!(error = diff_delta__from_one(diff, GIT_DELTA_DELETED, oitem, NULL)))
				error = diff_delta__from_one(diff, GIT_DELTA_UNREADABLE, NULL, nitem);
			return error;
		}

		else {
			if (!(error = diff_delta__from_one(diff, GIT_DELTA_DELETED, oitem, NULL)))
				error = diff_delta__from_one(diff, GIT_DELTA_ADDED, NULL, nitem);
			return error;
		}

	/* if oids and modes match (and are valid), then file is unmodified */
	} else if (git_oid_equal(&oitem->id, &nitem->id) &&
			 omode == nmode &&
			 !git_oid_iszero(&oitem->id)) {
		status = GIT_DELTA_UNMODIFIED;

	/* if we have an unknown OID and a workdir iterator, then check some
	 * circumstances that can accelerate things or need special handling
	 */
	} else if (git_oid_iszero(&nitem->id) && new_is_workdir) {
		bool use_ctime =
			((diff->diffcaps & GIT_DIFFCAPS_TRUST_CTIME) != 0);
		git_index *index = git_iterator_index(info->new_iter);

		status = GIT_DELTA_UNMODIFIED;

		if (S_ISGITLINK(nmode)) {
			if ((error = maybe_modified_submodule(&status, &noid, diff, info)) < 0)
				return error;
		}

		/* if the stat data looks different, then mark modified - this just
		 * means that the OID will be recalculated below to confirm change
		 */
		else if (omode != nmode || oitem->file_size != nitem->file_size) {
			status = GIT_DELTA_MODIFIED;
			modified_uncertain =
				(oitem->file_size <= 0 && nitem->file_size > 0);
		}
		else if (!git_index_time_eq(&oitem->mtime, &nitem->mtime) ||
			(use_ctime && !git_index_time_eq(&oitem->ctime, &nitem->ctime)) ||
			oitem->ino != nitem->ino ||
			oitem->uid != nitem->uid ||
			oitem->gid != nitem->gid ||
			git_index_entry_newer_than_index(nitem, index))
		{
			status = GIT_DELTA_MODIFIED;
			modified_uncertain = true;
		}

	/* if mode is GITLINK and submodules are ignored, then skip */
	} else if (S_ISGITLINK(nmode) &&
			 DIFF_FLAG_IS_SET(diff, GIT_DIFF_IGNORE_SUBMODULES)) {
		status = GIT_DELTA_UNMODIFIED;
	}

	/* if we got here and decided that the files are modified, but we
	 * haven't calculated the OID of the new item, then calculate it now
	 */
	if (modified_uncertain && git_oid_iszero(&nitem->id)) {
		const git_oid *update_check =
			DIFF_FLAG_IS_SET(diff, GIT_DIFF_UPDATE_INDEX) && omode == nmode ?
			&oitem->id : NULL;

		if ((error = git_diff__oid_for_entry(
				&noid, &diff->base, nitem, nmode, update_check)) < 0)
			return error;

		/* if oid matches, then mark unmodified (except submodules, where
		 * the filesystem content may be modified even if the oid still
		 * matches between the index and the workdir HEAD)
		 */
		if (omode == nmode && !S_ISGITLINK(omode) &&
			git_oid_equal(&oitem->id, &noid))
			status = GIT_DELTA_UNMODIFIED;
	}

	/* If we want case changes, then break this into a delete of the old
	 * and an add of the new so that consumers can act accordingly (eg,
	 * checkout will update the case on disk.)
	 */
	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_IGNORE_CASE) &&
		DIFF_FLAG_IS_SET(diff, GIT_DIFF_INCLUDE_CASECHANGE) &&
		strcmp(oitem->path, nitem->path) != 0) {

		if (!(error = diff_delta__from_one(diff, GIT_DELTA_DELETED, oitem, NULL)))
			error = diff_delta__from_one(diff, GIT_DELTA_ADDED, NULL, nitem);

		return error;
	}

	return diff_delta__from_two(
		diff, status, oitem, omode, nitem, nmode,
		git_oid_iszero(&noid) ? NULL : &noid, matched_pathspec);
}

static bool entry_is_prefixed(
	git_diff_generated *diff,
	const git_index_entry *item,
	const git_index_entry *prefix_item)
{
	size_t pathlen;

	if (!item || diff->base.pfxcomp(item->path, prefix_item->path) != 0)
		return false;

	pathlen = strlen(prefix_item->path);

	return (prefix_item->path[pathlen - 1] == '/' ||
			item->path[pathlen] == '\0' ||
			item->path[pathlen] == '/');
}

static int iterator_current(
	const git_index_entry **entry,
	git_iterator *iterator)
{
	int error;

	if ((error = git_iterator_current(entry, iterator)) == GIT_ITEROVER) {
		*entry = NULL;
		error = 0;
	}

	return error;
}

static int iterator_advance(
	const git_index_entry **entry,
	git_iterator *iterator)
{
	const git_index_entry *prev_entry = *entry;
	int cmp, error;

	/* if we're looking for conflicts, we only want to report
	 * one conflict for each file, instead of all three sides.
	 * so if this entry is a conflict for this file, and the
	 * previous one was a conflict for the same file, skip it.
	 */
	while ((error = git_iterator_advance(entry, iterator)) == 0) {
		if (!(iterator->flags & GIT_ITERATOR_INCLUDE_CONFLICTS) ||
			!git_index_entry_is_conflict(prev_entry) ||
			!git_index_entry_is_conflict(*entry))
			break;

		cmp = (iterator->flags & GIT_ITERATOR_IGNORE_CASE) ?
			strcasecmp(prev_entry->path, (*entry)->path) :
			strcmp(prev_entry->path, (*entry)->path);

		if (cmp)
			break;
	}

	if (error == GIT_ITEROVER) {
		*entry = NULL;
		error = 0;
	}

	return error;
}

static int iterator_advance_into(
	const git_index_entry **entry,
	git_iterator *iterator)
{
	int error;

	if ((error = git_iterator_advance_into(entry, iterator)) == GIT_ITEROVER) {
		*entry = NULL;
		error = 0;
	}

	return error;
}

static int iterator_advance_over(
	const git_index_entry **entry,
	git_iterator_status_t *status,
	git_iterator *iterator)
{
	int error = git_iterator_advance_over(entry, status, iterator);

	if (error == GIT_ITEROVER) {
		*entry = NULL;
		error = 0;
	}

	return error;
}

static int handle_unmatched_new_item(
	git_diff_generated *diff, diff_in_progress *info)
{
	int error = 0;
	const git_index_entry *nitem = info->nitem;
	git_delta_t delta_type = GIT_DELTA_UNTRACKED;
	bool contains_oitem;

	/* check if this is a prefix of the other side */
	contains_oitem = entry_is_prefixed(diff, info->oitem, nitem);

	/* update delta_type if this item is conflicted */
	if (git_index_entry_is_conflict(nitem))
		delta_type = GIT_DELTA_CONFLICTED;

	/* update delta_type if this item is ignored */
	else if (git_iterator_current_is_ignored(info->new_iter))
		delta_type = GIT_DELTA_IGNORED;

	if (nitem->mode == GIT_FILEMODE_TREE) {
		bool recurse_into_dir = contains_oitem;

		/* check if user requests recursion into this type of dir */
		recurse_into_dir = contains_oitem ||
			(delta_type == GIT_DELTA_UNTRACKED &&
			 DIFF_FLAG_IS_SET(diff, GIT_DIFF_RECURSE_UNTRACKED_DIRS)) ||
			(delta_type == GIT_DELTA_IGNORED &&
			 DIFF_FLAG_IS_SET(diff, GIT_DIFF_RECURSE_IGNORED_DIRS));

		/* do not advance into directories that contain a .git file */
		if (recurse_into_dir && !contains_oitem) {
			git_buf *full = NULL;
			if (git_iterator_current_workdir_path(&full, info->new_iter) < 0)
				return -1;
			if (full && git_path_contains(full, DOT_GIT)) {
				/* TODO: warning if not a valid git repository */
				recurse_into_dir = false;
			}
		}

		/* still have to look into untracked directories to match core git -
		 * with no untracked files, directory is treated as ignored
		 */
		if (!recurse_into_dir &&
			delta_type == GIT_DELTA_UNTRACKED &&
			DIFF_FLAG_ISNT_SET(diff, GIT_DIFF_ENABLE_FAST_UNTRACKED_DIRS))
		{
			git_diff_delta *last;
			git_iterator_status_t untracked_state;

			/* attempt to insert record for this directory */
			if ((error = diff_delta__from_one(diff, delta_type, NULL, nitem)) != 0)
				return error;

			/* if delta wasn't created (because of rules), just skip ahead */
			last = diff_delta__last_for_item(diff, nitem);
			if (!last)
				return iterator_advance(&info->nitem, info->new_iter);

			/* iterate into dir looking for an actual untracked file */
			if ((error = iterator_advance_over(
					&info->nitem, &untracked_state, info->new_iter)) < 0)
				return error;

			/* if we found nothing that matched our pathlist filter, exclude */
			if (untracked_state == GIT_ITERATOR_STATUS_FILTERED) {
				git_vector_pop(&diff->base.deltas);
				git__free(last);
			}

			/* if we found nothing or just ignored items, update the record */
			if (untracked_state == GIT_ITERATOR_STATUS_IGNORED ||
				untracked_state == GIT_ITERATOR_STATUS_EMPTY) {
				last->status = GIT_DELTA_IGNORED;

				/* remove the record if we don't want ignored records */
				if (DIFF_FLAG_ISNT_SET(diff, GIT_DIFF_INCLUDE_IGNORED)) {
					git_vector_pop(&diff->base.deltas);
					git__free(last);
				}
			}

			return 0;
		}

		/* try to advance into directory if necessary */
		if (recurse_into_dir) {
			error = iterator_advance_into(&info->nitem, info->new_iter);

			/* if directory is empty, can't advance into it, so skip it */
			if (error == GIT_ENOTFOUND) {
				giterr_clear();
				error = iterator_advance(&info->nitem, info->new_iter);
			}

			return error;
		}
	}

	else if (delta_type == GIT_DELTA_IGNORED &&
		DIFF_FLAG_ISNT_SET(diff, GIT_DIFF_RECURSE_IGNORED_DIRS) &&
		git_iterator_current_tree_is_ignored(info->new_iter))
		/* item contained in ignored directory, so skip over it */
		return iterator_advance(&info->nitem, info->new_iter);

	else if (info->new_iter->type != GIT_ITERATOR_TYPE_WORKDIR) {
		if (delta_type != GIT_DELTA_CONFLICTED)
			delta_type = GIT_DELTA_ADDED;
	}

	else if (nitem->mode == GIT_FILEMODE_COMMIT) {
		/* ignore things that are not actual submodules */
		if (git_submodule_lookup(NULL, info->repo, nitem->path) != 0) {
			giterr_clear();
			delta_type = GIT_DELTA_IGNORED;

			/* if this contains a tracked item, treat as normal TREE */
			if (contains_oitem) {
				error = iterator_advance_into(&info->nitem, info->new_iter);
				if (error != GIT_ENOTFOUND)
					return error;

				giterr_clear();
				return iterator_advance(&info->nitem, info->new_iter);
			}
		}
	}

	else if (nitem->mode == GIT_FILEMODE_UNREADABLE) {
		if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_INCLUDE_UNREADABLE_AS_UNTRACKED))
			delta_type = GIT_DELTA_UNTRACKED;
		else
			delta_type = GIT_DELTA_UNREADABLE;
	}

	/* Actually create the record for this item if necessary */
	if ((error = diff_delta__from_one(diff, delta_type, NULL, nitem)) != 0)
		return error;

	/* If user requested TYPECHANGE records, then check for that instead of
	 * just generating an ADDED/UNTRACKED record
	 */
	if (delta_type != GIT_DELTA_IGNORED &&
		DIFF_FLAG_IS_SET(diff, GIT_DIFF_INCLUDE_TYPECHANGE_TREES) &&
		contains_oitem)
	{
		/* this entry was prefixed with a tree - make TYPECHANGE */
		git_diff_delta *last = diff_delta__last_for_item(diff, nitem);
		if (last) {
			last->status = GIT_DELTA_TYPECHANGE;
			last->old_file.mode = GIT_FILEMODE_TREE;
		}
	}

	return iterator_advance(&info->nitem, info->new_iter);
}

static int handle_unmatched_old_item(
	git_diff_generated *diff, diff_in_progress *info)
{
	git_delta_t delta_type = GIT_DELTA_DELETED;
	int error;

	/* update delta_type if this item is conflicted */
	if (git_index_entry_is_conflict(info->oitem))
		delta_type = GIT_DELTA_CONFLICTED;

	if ((error = diff_delta__from_one(diff, delta_type, info->oitem, NULL)) < 0)
		return error;

	/* if we are generating TYPECHANGE records then check for that
	 * instead of just generating a DELETE record
	 */
	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_INCLUDE_TYPECHANGE_TREES) &&
		entry_is_prefixed(diff, info->nitem, info->oitem))
	{
		/* this entry has become a tree! convert to TYPECHANGE */
		git_diff_delta *last = diff_delta__last_for_item(diff, info->oitem);
		if (last) {
			last->status = GIT_DELTA_TYPECHANGE;
			last->new_file.mode = GIT_FILEMODE_TREE;
		}

		/* If new_iter is a workdir iterator, then this situation
		 * will certainly be followed by a series of untracked items.
		 * Unless RECURSE_UNTRACKED_DIRS is set, skip over them...
		 */
		if (S_ISDIR(info->nitem->mode) &&
			DIFF_FLAG_ISNT_SET(diff, GIT_DIFF_RECURSE_UNTRACKED_DIRS))
			return iterator_advance(&info->nitem, info->new_iter);
	}

	return iterator_advance(&info->oitem, info->old_iter);
}

static int handle_matched_item(
	git_diff_generated *diff, diff_in_progress *info)
{
	int error = 0;

	if ((error = maybe_modified(diff, info)) < 0)
		return error;

	if (!(error = iterator_advance(&info->oitem, info->old_iter)))
		error = iterator_advance(&info->nitem, info->new_iter);

	return error;
}

int git_diff__from_iterators(
	git_diff **out,
	git_repository *repo,
	git_iterator *old_iter,
	git_iterator *new_iter,
	const git_diff_options *opts)
{
	git_diff_generated *diff;
	diff_in_progress info;
	int error = 0;

	*out = NULL;

	diff = diff_generated_alloc(repo, old_iter, new_iter);
	GITERR_CHECK_ALLOC(diff);

	info.repo = repo;
	info.old_iter = old_iter;
	info.new_iter = new_iter;

	/* make iterators have matching icase behavior */
	if (DIFF_FLAG_IS_SET(diff, GIT_DIFF_IGNORE_CASE)) {
		git_iterator_set_ignore_case(old_iter, true);
		git_iterator_set_ignore_case(new_iter, true);
	}

	/* finish initialization */
	if ((error = diff_generated_apply_options(diff, opts)) < 0)
		goto cleanup;

	if ((error = iterator_current(&info.oitem, old_iter)) < 0 ||
		(error = iterator_current(&info.nitem, new_iter)) < 0)
		goto cleanup;

	/* run iterators building diffs */
	while (!error && (info.oitem || info.nitem)) {
		int cmp;

		/* report progress */
		if (opts && opts->progress_cb) {
			if ((error = opts->progress_cb(&diff->base,
					info.oitem ? info.oitem->path : NULL,
					info.nitem ? info.nitem->path : NULL,
					opts->payload)))
				break;
		}

		cmp = info.oitem ?
			(info.nitem ? diff->base.entrycomp(info.oitem, info.nitem) : -1) : 1;

		/* create DELETED records for old items not matched in new */
		if (cmp < 0)
			error = handle_unmatched_old_item(diff, &info);

		/* create ADDED, TRACKED, or IGNORED records for new items not
		 * matched in old (and/or descend into directories as needed)
		 */
		else if (cmp > 0)
			error = handle_unmatched_new_item(diff, &info);

		/* otherwise item paths match, so create MODIFIED record
		 * (or ADDED and DELETED pair if type changed)
		 */
		else
			error = handle_matched_item(diff, &info);
	}

	diff->base.perf.stat_calls +=
		old_iter->stat_calls + new_iter->stat_calls;

cleanup:
	if (!error)
		*out = &diff->base;
	else
		git_diff_free(&diff->base);

	return error;
}

#define DIFF_FROM_ITERATORS(MAKE_FIRST, FLAGS_FIRST, MAKE_SECOND, FLAGS_SECOND) do { \
	git_iterator *a = NULL, *b = NULL; \
	char *pfx = (opts && !(opts->flags & GIT_DIFF_DISABLE_PATHSPEC_MATCH)) ? \
		git_pathspec_prefix(&opts->pathspec) : NULL; \
	git_iterator_options a_opts = GIT_ITERATOR_OPTIONS_INIT, \
		b_opts = GIT_ITERATOR_OPTIONS_INIT; \
	a_opts.flags = FLAGS_FIRST; \
	a_opts.start = pfx; \
	a_opts.end = pfx; \
	b_opts.flags = FLAGS_SECOND; \
	b_opts.start = pfx; \
	b_opts.end = pfx; \
	GITERR_CHECK_VERSION(opts, GIT_DIFF_OPTIONS_VERSION, "git_diff_options"); \
	if (opts && (opts->flags & GIT_DIFF_DISABLE_PATHSPEC_MATCH)) { \
		a_opts.pathlist.strings = opts->pathspec.strings; \
		a_opts.pathlist.count = opts->pathspec.count; \
		b_opts.pathlist.strings = opts->pathspec.strings; \
		b_opts.pathlist.count = opts->pathspec.count; \
	} \
	if (!error && !(error = MAKE_FIRST) && !(error = MAKE_SECOND)) \
		error = git_diff__from_iterators(&diff, repo, a, b, opts); \
	git__free(pfx); git_iterator_free(a); git_iterator_free(b); \
} while (0)

int git_diff_tree_to_tree(
	git_diff **out,
	git_repository *repo,
	git_tree *old_tree,
	git_tree *new_tree,
	const git_diff_options *opts)
{
	git_diff *diff = NULL;
	git_iterator_flag_t iflag = GIT_ITERATOR_DONT_IGNORE_CASE;
	int error = 0;

	assert(out && repo);

	*out = NULL;

	/* for tree to tree diff, be case sensitive even if the index is
	 * currently case insensitive, unless the user explicitly asked
	 * for case insensitivity
	 */
	if (opts && (opts->flags & GIT_DIFF_IGNORE_CASE) != 0)
		iflag = GIT_ITERATOR_IGNORE_CASE;

	DIFF_FROM_ITERATORS(
		git_iterator_for_tree(&a, old_tree, &a_opts), iflag,
		git_iterator_for_tree(&b, new_tree, &b_opts), iflag
	);

	if (!error)
		*out = diff;

	return error;
}

static int diff_load_index(git_index **index, git_repository *repo)
{
	int error = git_repository_index__weakptr(index, repo);

	/* reload the repository index when user did not pass one in */
	if (!error && git_index_read(*index, false) < 0)
		giterr_clear();

	return error;
}

int git_diff_tree_to_index(
	git_diff **out,
	git_repository *repo,
	git_tree *old_tree,
	git_index *index,
	const git_diff_options *opts)
{
	git_diff *diff = NULL;
	git_iterator_flag_t iflag = GIT_ITERATOR_DONT_IGNORE_CASE |
		GIT_ITERATOR_INCLUDE_CONFLICTS;
	bool index_ignore_case = false;
	int error = 0;

	assert(out && repo);

	*out = NULL;

	if (!index && (error = diff_load_index(&index, repo)) < 0)
		return error;

	index_ignore_case = index->ignore_case;

	DIFF_FROM_ITERATORS(
		git_iterator_for_tree(&a, old_tree, &a_opts), iflag,
		git_iterator_for_index(&b, repo, index, &b_opts), iflag
	);

	/* if index is in case-insensitive order, re-sort deltas to match */
	if (!error && index_ignore_case)
		git_diff__set_ignore_case(diff, true);

	if (!error)
		*out = diff;

	return error;
}

int git_diff_index_to_workdir(
	git_diff **out,
	git_repository *repo,
	git_index *index,
	const git_diff_options *opts)
{
	git_diff *diff = NULL;
	int error = 0;

	assert(out && repo);

	*out = NULL;

	if (!index && (error = diff_load_index(&index, repo)) < 0)
		return error;

	DIFF_FROM_ITERATORS(
		git_iterator_for_index(&a, repo, index, &a_opts),
		GIT_ITERATOR_INCLUDE_CONFLICTS,

		git_iterator_for_workdir(&b, repo, index, NULL, &b_opts),
		GIT_ITERATOR_DONT_AUTOEXPAND
	);

	if (!error && (diff->opts.flags & GIT_DIFF_UPDATE_INDEX) != 0 &&
		((git_diff_generated *)diff)->index_updated)
		error = git_index_write(index);

	if (!error)
		*out = diff;

	return error;
}

int git_diff_tree_to_workdir(
	git_diff **out,
	git_repository *repo,
	git_tree *old_tree,
	const git_diff_options *opts)
{
	git_diff *diff = NULL;
	git_index *index;
	int error = 0;

	assert(out && repo);

	*out = NULL;

	if ((error = git_repository_index__weakptr(&index, repo)))
		return error;

	DIFF_FROM_ITERATORS(
		git_iterator_for_tree(&a, old_tree, &a_opts), 0,
		git_iterator_for_workdir(&b, repo, index, old_tree, &b_opts), GIT_ITERATOR_DONT_AUTOEXPAND
	);

	if (!error)
		*out = diff;

	return error;
}

int git_diff_tree_to_workdir_with_index(
	git_diff **out,
	git_repository *repo,
	git_tree *tree,
	const git_diff_options *opts)
{
	git_diff *d1 = NULL, *d2 = NULL;
	git_index *index = NULL;
	int error = 0;

	assert(out && repo);

	*out = NULL;

	if ((error = diff_load_index(&index, repo)) < 0)
		return error;

	if (!(error = git_diff_tree_to_index(&d1, repo, tree, index, opts)) &&
		!(error = git_diff_index_to_workdir(&d2, repo, index, opts)))
		error = git_diff_merge(d1, d2);

	git_diff_free(d2);

	if (error) {
		git_diff_free(d1);
		d1 = NULL;
	}

	*out = d1;
	return error;
}

int git_diff_index_to_index(
	git_diff **out,
	git_repository *repo,
	git_index *old_index,
	git_index *new_index,
	const git_diff_options *opts)
{
	git_diff *diff;
	int error = 0;

	assert(out && old_index && new_index);

	*out = NULL;

	DIFF_FROM_ITERATORS(
		git_iterator_for_index(&a, repo, old_index, &a_opts), GIT_ITERATOR_DONT_IGNORE_CASE,
		git_iterator_for_index(&b, repo, new_index, &b_opts), GIT_ITERATOR_DONT_IGNORE_CASE
	);

	/* if index is in case-insensitive order, re-sort deltas to match */
	if (!error && (old_index->ignore_case || new_index->ignore_case))
		git_diff__set_ignore_case(diff, true);

	if (!error)
		*out = diff;

	return error;
}

int git_diff__paired_foreach(
	git_diff *head2idx,
	git_diff *idx2wd,
	int (*cb)(git_diff_delta *h2i, git_diff_delta *i2w, void *payload),
	void *payload)
{
	int cmp, error = 0;
	git_diff_delta *h2i, *i2w;
	size_t i, j, i_max, j_max;
	int (*strcomp)(const char *, const char *) = git__strcmp;
	bool h2i_icase, i2w_icase, icase_mismatch;

	i_max = head2idx ? head2idx->deltas.length : 0;
	j_max = idx2wd ? idx2wd->deltas.length : 0;
	if (!i_max && !j_max)
		return 0;

	/* At some point, tree-to-index diffs will probably never ignore case,
	 * even if that isn't true now.  Index-to-workdir diffs may or may not
	 * ignore case, but the index filename for the idx2wd diff should
	 * still be using the canonical case-preserving name.
	 *
	 * Therefore the main thing we need to do here is make sure the diffs
	 * are traversed in a compatible order.  To do this, we temporarily
	 * resort a mismatched diff to get the order correct.
	 *
	 * In order to traverse renames in the index->workdir, we need to
	 * ensure that we compare the index name on both sides, so we
	 * always sort by the old name in the i2w list.
	 */
	h2i_icase = head2idx != NULL && git_diff_is_sorted_icase(head2idx);
	i2w_icase = idx2wd != NULL && git_diff_is_sorted_icase(idx2wd);

	icase_mismatch =
		(head2idx != NULL && idx2wd != NULL && h2i_icase != i2w_icase);

	if (icase_mismatch && h2i_icase) {
		git_vector_set_cmp(&head2idx->deltas, git_diff_delta__cmp);
		git_vector_sort(&head2idx->deltas);
	}

	if (i2w_icase && !icase_mismatch) {
		strcomp = git__strcasecmp;

		git_vector_set_cmp(&idx2wd->deltas, git_diff_delta__i2w_casecmp);
		git_vector_sort(&idx2wd->deltas);
	} else if (idx2wd != NULL) {
		git_vector_set_cmp(&idx2wd->deltas, git_diff_delta__i2w_cmp);
		git_vector_sort(&idx2wd->deltas);
	}

	for (i = 0, j = 0; i < i_max || j < j_max; ) {
		h2i = head2idx ? GIT_VECTOR_GET(&head2idx->deltas, i) : NULL;
		i2w = idx2wd ? GIT_VECTOR_GET(&idx2wd->deltas, j) : NULL;

		cmp = !i2w ? -1 : !h2i ? 1 :
			strcomp(h2i->new_file.path, i2w->old_file.path);

		if (cmp < 0) {
			i++; i2w = NULL;
		} else if (cmp > 0) {
			j++; h2i = NULL;
		} else {
			i++; j++;
		}

		if ((error = cb(h2i, i2w, payload)) != 0) {
			giterr_set_after_callback(error);
			break;
		}
	}

	/* restore case-insensitive delta sort */
	if (icase_mismatch && h2i_icase) {
		git_vector_set_cmp(&head2idx->deltas, git_diff_delta__casecmp);
		git_vector_sort(&head2idx->deltas);
	}

	/* restore idx2wd sort by new path */
	if (idx2wd != NULL) {
		git_vector_set_cmp(&idx2wd->deltas,
			i2w_icase ? git_diff_delta__casecmp : git_diff_delta__cmp);
		git_vector_sort(&idx2wd->deltas);
	}

	return error;
}

int git_diff__commit(
	git_diff **out,
	git_repository *repo,
	const git_commit *commit,
	const git_diff_options *opts)
{
	git_commit *parent = NULL;
	git_diff *commit_diff = NULL;
	git_tree *old_tree = NULL, *new_tree = NULL;
	size_t parents;
	int error = 0;

	*out = NULL;

	if ((parents = git_commit_parentcount(commit)) > 1) {
		char commit_oidstr[GIT_OID_HEXSZ + 1];

		error = -1;
		giterr_set(GITERR_INVALID, "commit %s is a merge commit",
			git_oid_tostr(commit_oidstr, GIT_OID_HEXSZ + 1, git_commit_id(commit)));
		goto on_error;
	}

	if (parents > 0)
		if ((error = git_commit_parent(&parent, commit, 0)) < 0 ||
			(error = git_commit_tree(&old_tree, parent)) < 0)
				goto on_error;

	if ((error = git_commit_tree(&new_tree, commit)) < 0 ||
		(error = git_diff_tree_to_tree(&commit_diff, repo, old_tree, new_tree, opts)) < 0)
			goto on_error;

	*out = commit_diff;

on_error:
	git_tree_free(new_tree);
	git_tree_free(old_tree);
	git_commit_free(parent);

	return error;
}