static int fsck_walk_commit(struct commit *commit, fsck_walk_func walk, void *data)
{
	struct commit_list *parents;
	int res;
	int result;

	if (parse_commit(commit))
		return -1;

	result = walk((struct object *)commit->tree, OBJ_TREE, data);
	if (result < 0)
		return result;
	res = result;

	parents = commit->parents;
	while (parents) {
		result = walk((struct object *)parents->item, OBJ_COMMIT, data);
		if (result < 0)
			return result;
		if (!res)
			res = result;
		parents = parents->next;
	}
	return res;
}

static void mark_common(struct commit *commit,
		int ancestors_only, int dont_parse)
{
	if (commit != NULL && !(commit->object.flags & COMMON)) {
		struct object *o = (struct object *)commit;

		if (!ancestors_only)
			o->flags |= COMMON;

		if (!(o->flags & SEEN))
			rev_list_push(commit, SEEN);
		else {
			struct commit_list *parents;

			if (!ancestors_only && !(o->flags & POPPED))
				non_common_revs--;
			if (!o->parsed && !dont_parse)
				if (parse_commit(commit))
					return;

			for (parents = commit->parents;
					parents;
					parents = parents->next)
				mark_common(parents->item, 0, dont_parse);
		}
	}
}

int git_get_commit_from_hash(GIT_COMMIT* commit, const GIT_HASH hash)
{
	int ret = 0;

	struct commit *p;
	struct object_id oid;

	if (commit == NULL)
		return -1;

	memset(commit,0,sizeof(GIT_COMMIT));

	hashcpy(oid.hash, hash);

	commit->m_pGitCommit = p = lookup_commit(the_repository, &oid);

	if(p == NULL)
		return -1;

	ret = parse_commit(p);
	if( ret )
		return ret;

	return git_parse_commit(commit);
}

void cgit_print_plain(struct cgit_context *ctx)
{
	const char *rev = ctx->qry.sha1;
	unsigned char sha1[20];
	struct commit *commit;
	const char *paths[] = {ctx->qry.path, NULL};

	if (!rev)
		rev = ctx->qry.head;

	curr_rev = xstrdup(rev);
	if (get_sha1(rev, sha1)) {
		html_status(404, "Not found", 0);
		return;
	}
	commit = lookup_commit_reference(sha1);
	if (!commit || parse_commit(commit)) {
		html_status(404, "Not found", 0);
		return;
	}
	match_path = ctx->qry.path;
	read_tree_recursive(commit->tree, "", 0, 0, paths, walk_tree, NULL);
	if (!match)
		html_status(404, "Not found", 0);
}

static unsigned long finish_depth_computation(
    struct commit_list **list,
    struct possible_tag *best)
{
    unsigned long seen_commits = 0;
    while (*list) {
        struct commit *c = pop_commit(list);
        struct commit_list *parents = c->parents;
        seen_commits++;
        if (c->object.flags & best->flag_within) {
            struct commit_list *a = *list;
            while (a) {
                struct commit *i = a->item;
                if (!(i->object.flags & best->flag_within))
                    break;
                a = a->next;
            }
            if (!a)
                break;
        } else
            best->depth++;
        while (parents) {
            struct commit *p = parents->item;
            parse_commit(p);
            if (!(p->object.flags & SEEN))
                commit_list_insert_by_date(p, list);
            p->object.flags |= c->object.flags;
            parents = parents->next;
        }
    }
    return seen_commits;
}

static int is_a_merge(const unsigned char *sha1)
{
	struct commit *commit = lookup_commit(sha1);
	if (!commit || parse_commit(commit))
		die("could not parse HEAD commit");
	return !!(commit->parents && commit->parents->next);
}

static int process_commit(struct walker *walker, struct commit *commit)
{
	if (parse_commit(commit))
		return -1;

	while (complete && complete->item->date >= commit->date) {
		pop_most_recent_commit(&complete, COMPLETE);
	}

	if (commit->object.flags & COMPLETE)
		return 0;

	hashcpy(current_commit_sha1, commit->object.sha1);

	walker_say(walker, "walk %s\n", sha1_to_hex(commit->object.sha1));

	if (walker->get_tree) {
		if (process(walker, &commit->tree->object))
			return -1;
		if (!walker->get_all)
			walker->get_tree = 0;
	}
	if (walker->get_history) {
		struct commit_list *parents = commit->parents;
		for (; parents; parents = parents->next) {
			if (process(walker, &parents->item->object))
				return -1;
		}
	}
	return 0;
}

static int is_index_unchanged(void)
{
	unsigned char head_sha1[20];
	struct commit *head_commit;

	if (!resolve_ref_unsafe("HEAD", RESOLVE_REF_READING, head_sha1, NULL))
		return error(_("could not resolve HEAD commit\n"));

	head_commit = lookup_commit(head_sha1);

	/*
	 * If head_commit is NULL, check_commit, called from
	 * lookup_commit, would have indicated that head_commit is not
	 * a commit object already.  parse_commit() will return failure
	 * without further complaints in such a case.  Otherwise, if
	 * the commit is invalid, parse_commit() will complain.  So
	 * there is nothing for us to say here.  Just return failure.
	 */
	if (parse_commit(head_commit))
		return -1;

	if (!active_cache_tree)
		active_cache_tree = cache_tree();

	if (!cache_tree_fully_valid(active_cache_tree))
		if (cache_tree_update(&the_index, 0))
			return error(_("unable to update cache tree\n"));

	return !hashcmp(active_cache_tree->sha1, head_commit->tree->object.oid.hash);
}

/*
 * Starting from commits in the cb->mark_list, mark commits that are
 * reachable from them.  Stop the traversal at commits older than
 * the expire_limit and queue them back, so that the caller can call
 * us again to restart the traversal with longer expire_limit.
 */
static void mark_reachable(struct expire_reflog_policy_cb *cb)
{
	struct commit_list *pending;
	timestamp_t expire_limit = cb->mark_limit;
	struct commit_list *leftover = NULL;

	for (pending = cb->mark_list; pending; pending = pending->next)
		pending->item->object.flags &= ~REACHABLE;

	pending = cb->mark_list;
	while (pending) {
		struct commit_list *parent;
		struct commit *commit = pop_commit(&pending);
		if (commit->object.flags & REACHABLE)
			continue;
		if (parse_commit(commit))
			continue;
		commit->object.flags |= REACHABLE;
		if (commit->date < expire_limit) {
			commit_list_insert(commit, &leftover);
			continue;
		}
		commit->object.flags |= REACHABLE;
		parent = commit->parents;
		while (parent) {
			commit = parent->item;
			parent = parent->next;
			if (commit->object.flags & REACHABLE)
				continue;
			commit_list_insert(commit, &pending);
		}
	}
	cb->mark_list = leftover;
}

static void name_rev(struct commit *commit,
		const char *tip_name, int generation, int distance,
		int deref)
{
	struct rev_name *name = (struct rev_name *)commit->util;
	struct commit_list *parents;
	int parent_number = 1;

	parse_commit(commit);

	if (commit->date < cutoff)
		return;

	if (deref) {
		tip_name = xstrfmt("%s^0", tip_name);

		if (generation)
			die("generation: %d, but deref?", generation);
	}

	if (name == NULL) {
		name = xmalloc(sizeof(rev_name));
		commit->util = name;
		goto copy_data;
	} else if (name->distance > distance) {
copy_data:
		name->tip_name = tip_name;
		name->generation = generation;
		name->distance = distance;
	} else
		return;

	for (parents = commit->parents;
			parents;
			parents = parents->next, parent_number++) {
		if (parent_number > 1) {
			int len = strlen(tip_name);
			char *new_name = xmalloc(len +
				1 + decimal_length(generation) +  /* ~<n> */
				1 + 2 +				  /* ^NN */
				1);

			if (len > 2 && !strcmp(tip_name + len - 2, "^0"))
				len -= 2;
			if (generation > 0)
				sprintf(new_name, "%.*s~%d^%d", len, tip_name,
						generation, parent_number);
			else
				sprintf(new_name, "%.*s^%d", len, tip_name,
						parent_number);

			name_rev(parents->item, new_name, 0,
				distance + MERGE_TRAVERSAL_WEIGHT, 0);
		} else {
			name_rev(parents->item, tip_name, generation + 1,
				distance + 1, 0);
		}
	}
}

static void describe_one_orphan(struct strbuf *sb, struct commit *commit)
{
	strbuf_addstr(sb, "  ");
	strbuf_add_unique_abbrev(sb, &commit->object.oid, DEFAULT_ABBREV);
	strbuf_addch(sb, ' ');
	if (!parse_commit(commit))
		pp_commit_easy(CMIT_FMT_ONELINE, commit, sb);
	strbuf_addch(sb, '\n');
}

/*
 * Usage: rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id2>]
 *
 * The cache-file can be quite important for big trees. This is an
 * expensive operation if you have to walk the whole chain of
 * parents in a tree with a long revision history.
 */
int main(int argc, char **argv)
{
	int i;
	int nr = 0;
	unsigned char sha1[MAX_COMMITS][20];

	/*
	 * First - pick up all the revisions we can (both from
	 * caches and from commit file chains).
	 */
	for (i = 1; i < argc ; i++) {
		char *arg = argv[i];

		if (!strcmp(arg, "--cache")) {
			read_cache_file(argv[2]);
			i++;
			continue;
		}

		if (!strcmp(arg, "--edges")) {
			show_edges = 1;
			continue;
		}

		if (nr >= MAX_COMMITS || get_sha1_hex(arg, sha1[nr]))
			usage("rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id>]");
		parse_commit(sha1[nr]);
		nr++;
	}

	/*
	 * Now we have the maximal tree. Walk the different sha files back to the root.
	 */
	for (i = 0; i < nr; i++)
		mark_sha1_path(lookup_rev(sha1[i]), 1 << i);

	/*
	 * Now print out the results..
	 */
	for (i = 0; i < nr_revs; i++) {
		struct revision *rev = revs[i];
		struct parent *p;

		if (!interesting(rev))
			continue;

		printf("%s:%d", sha1_to_hex(rev->sha1), marked(rev));
		p = rev->parent;
		while (p) {
			printf(" %s:%d", sha1_to_hex(p->parent->sha1), marked(p->parent));
			p = p->next;
		}
		printf("\n");
	}
	return 0;
}

static int is_original_commit_empty(struct commit *commit)
{
	const unsigned char *ptree_sha1;

	if (parse_commit(commit))
		return error(_("Could not parse commit %s\n"),
			     oid_to_hex(&commit->object.oid));
	if (commit->parents) {
		struct commit *parent = commit->parents->item;
		if (parse_commit(parent))
			return error(_("Could not parse parent commit %s\n"),
				oid_to_hex(&parent->object.oid));
		ptree_sha1 = parent->tree->object.oid.hash;
	} else {
		ptree_sha1 = EMPTY_TREE_SHA1_BIN; /* commit is root */
	}

	return !hashcmp(ptree_sha1, commit->tree->object.oid.hash);
}

static void name_rev(struct commit *commit,
		const char *tip_name, int generation, int distance,
		int deref)
{
	struct rev_name *name = (struct rev_name *)commit->util;
	struct commit_list *parents;
	int parent_number = 1;

	parse_commit(commit);

	if (commit->date < cutoff)
		return;

	if (deref) {
		tip_name = xstrfmt("%s^0", tip_name);

		if (generation)
			die("generation: %d, but deref?", generation);
	}

	if (name == NULL) {
		name = xmalloc(sizeof(rev_name));
		commit->util = name;
		goto copy_data;
	} else if (name->distance > distance) {
copy_data:
		name->tip_name = tip_name;
		name->generation = generation;
		name->distance = distance;
	} else
		return;

	for (parents = commit->parents;
			parents;
			parents = parents->next, parent_number++) {
		if (parent_number > 1) {
			size_t len;
			char *new_name;

			strip_suffix(tip_name, "^0", &len);
			if (generation > 0)
				new_name = xstrfmt("%.*s~%d^%d", (int)len, tip_name,
						   generation, parent_number);
			else
				new_name = xstrfmt("%.*s^%d", (int)len, tip_name,
						   parent_number);

			name_rev(parents->item, new_name, 0,
				distance + MERGE_TRAVERSAL_WEIGHT, 0);
		} else {
			name_rev(parents->item, tip_name, generation + 1,
				distance + 1, 0);
		}
	}
}

static void print_ref_item(struct ref_item *item, int maxwidth, int verbose,
			   int abbrev, int current)
{
	char c;
	int color;
	struct commit *commit = item->commit;

	if (!matches_merge_filter(commit))
		return;

	switch (item->kind) {
	case REF_LOCAL_BRANCH:
		color = COLOR_BRANCH_LOCAL;
		break;
	case REF_REMOTE_BRANCH:
		color = COLOR_BRANCH_REMOTE;
		break;
	default:
		color = COLOR_BRANCH_PLAIN;
		break;
	}

	c = ' ';
	if (current) {
		c = '*';
		color = COLOR_BRANCH_CURRENT;
	}

	if (verbose) {
		struct strbuf subject = STRBUF_INIT, stat = STRBUF_INIT;
		const char *sub = " **** invalid ref ****";

		commit = item->commit;
		if (commit && !parse_commit(commit)) {
			pretty_print_commit(CMIT_FMT_ONELINE, commit,
					    &subject, 0, NULL, NULL, 0, 0);
			sub = subject.buf;
		}

		if (item->kind == REF_LOCAL_BRANCH)
			fill_tracking_info(&stat, item->name);

		printf("%c %s%-*s%s %s %s%s\n", c, branch_get_color(color),
		       maxwidth, item->name,
		       branch_get_color(COLOR_BRANCH_RESET),
		       find_unique_abbrev(item->commit->object.sha1, abbrev),
		       stat.buf, sub);
		strbuf_release(&stat);
		strbuf_release(&subject);
	} else {
		printf("%c %s%s%s\n", c, branch_get_color(color), item->name,
		       branch_get_color(COLOR_BRANCH_RESET));
	}
}

static int merge_commit(struct notes_merge_options *o)
{
	struct strbuf msg = STRBUF_INIT;
	unsigned char sha1[20], parent_sha1[20];
	struct notes_tree *t;
	struct commit *partial;
	struct pretty_print_context pretty_ctx;
	void *local_ref_to_free;
	int ret;

	/*
	 * Read partial merge result from .git/NOTES_MERGE_PARTIAL,
	 * and target notes ref from .git/NOTES_MERGE_REF.
	 */

	if (get_sha1("NOTES_MERGE_PARTIAL", sha1))
		die("Failed to read ref NOTES_MERGE_PARTIAL");
	else if (!(partial = lookup_commit_reference(sha1)))
		die("Could not find commit from NOTES_MERGE_PARTIAL.");
	else if (parse_commit(partial))
		die("Could not parse commit from NOTES_MERGE_PARTIAL.");

	if (partial->parents)
		hashcpy(parent_sha1, partial->parents->item->object.sha1);
	else
		hashclr(parent_sha1);

	t = xcalloc(1, sizeof(struct notes_tree));
	init_notes(t, "NOTES_MERGE_PARTIAL", combine_notes_overwrite, 0);

	o->local_ref = local_ref_to_free =
		resolve_refdup("NOTES_MERGE_REF", 0, sha1, NULL);
	if (!o->local_ref)
		die("Failed to resolve NOTES_MERGE_REF");

	if (notes_merge_commit(o, t, partial, sha1))
		die("Failed to finalize notes merge");

	/* Reuse existing commit message in reflog message */
	memset(&pretty_ctx, 0, sizeof(pretty_ctx));
	format_commit_message(partial, "%s", &msg, &pretty_ctx);
	strbuf_trim(&msg);
	strbuf_insert(&msg, 0, "notes: ", 7);
	update_ref(msg.buf, o->local_ref, sha1,
		   is_null_sha1(parent_sha1) ? NULL : parent_sha1,
		   0, UPDATE_REFS_DIE_ON_ERR);

	free_notes(t);
	strbuf_release(&msg);
	ret = merge_abort(o);
	free(local_ref_to_free);
	return ret;
}

static void rev_list_push(struct commit *commit, int mark)
{
	if (!(commit->object.flags & mark)) {
		commit->object.flags |= mark;

		if (parse_commit(commit))
			return;

		prio_queue_put(&rev_list, commit);

		if (!(commit->object.flags & COMMON))
			non_common_revs++;
	}
}

static void rev_list_push(struct commit *commit, int mark)
{
	if (!(commit->object.flags & mark)) {
		commit->object.flags |= mark;

		if (!(commit->object.parsed))
			if (parse_commit(commit))
				return;

		insert_by_date(commit, &rev_list);

		if (!(commit->object.flags & COMMON))
			non_common_revs++;
	}
}

static void describe_detached_head(const char *msg, struct commit *commit)
{
	struct strbuf sb = STRBUF_INIT;

	if (!parse_commit(commit))
		pp_commit_easy(CMIT_FMT_ONELINE, commit, &sb);
	if (print_sha1_ellipsis()) {
		fprintf(stderr, "%s %s... %s\n", msg,
			find_unique_abbrev(&commit->object.oid, DEFAULT_ABBREV), sb.buf);
	} else {
		fprintf(stderr, "%s %s %s\n", msg,
			find_unique_abbrev(&commit->object.oid, DEFAULT_ABBREV), sb.buf);
	}
	strbuf_release(&sb);
}

static struct commit *get_ref(const unsigned char *sha1, const char *name)
{
	struct object *object;

	object = deref_tag(parse_object(sha1), name, strlen(name));
	if (!object)
		return NULL;
	if (object->type == OBJ_TREE)
		return make_virtual_commit((struct tree*)object, name);
	if (object->type != OBJ_COMMIT)
		return NULL;
	if (parse_commit((struct commit *)object))
		return NULL;
	return (struct commit *)object;
}