path: root/Documentation/MyFirstObjectWalk.txt

= My First Object Walk

== What's an Object Walk?

The object walk is a key concept in Git - this is the process that underpins
operations like object transfer and fsck. Beginning from a given commit, the
list of objects is found by walking parent relationships between commits (commit
X based on commit W) and containment relationships between objects (tree Y is
contained within commit X, and blob Z is located within tree Y, giving our
working tree for commit X something like `y/z.txt`).

A related concept is the revision walk, which is focused on commit objects and
their parent relationships and does not delve into other object types. The
revision walk is used for operations like `git log`.

=== Related Reading

- `Documentation/user-manual.txt` under "Hacking Git" contains some coverage of
  the revision walker in its various incarnations.
- `revision.h`
- https://eagain.net/articles/git-for-computer-scientists/[Git for Computer Scientists]
  gives a good overview of the types of objects in Git and what your object
  walk is really describing.

== Setting Up

Create a new branch from `master`.

----
git checkout -b revwalk origin/master
----

We'll put our fiddling into a new command. For fun, let's name it `git walken`.
Open up a new file `builtin/walken.c` and set up the command handler:

----
/*
 * "git walken"
 *
 * Part of the "My First Object Walk" tutorial.
 */

#include "builtin.h"

int cmd_walken(int argc, const char **argv, const char *prefix)
{
	trace_printf(_("cmd_walken incoming...\n"));
	return 0;
}
----

NOTE: `trace_printf()` differs from `printf()` in that it can be turned on or
off at runtime. For the purposes of this tutorial, we will write `walken` as
though it is intended for use as a "plumbing" command: that is, a command which
is used primarily in scripts, rather than interactively by humans (a "porcelain"
command). So we will send our debug output to `trace_printf()` instead. When
running, enable trace output by setting the environment variable `GIT_TRACE`.

Add usage text and `-h` handling, like all subcommands should consistently do
(our test suite will notice and complain if you fail to do so).

----
int cmd_walken(int argc, const char **argv, const char *prefix)
{
	const char * const walken_usage[] = {
		N_("git walken"),
		NULL,
	}
	struct option options[] = {
		OPT_END()
	};

	argc = parse_options(argc, argv, prefix, options, walken_usage, 0);

	...
}
----

Also add the relevant line in `builtin.h` near `cmd_whatchanged()`:

----
int cmd_walken(int argc, const char **argv, const char *prefix);
----

Include the command in `git.c` in `commands[]` near the entry for `whatchanged`,
maintaining alphabetical ordering:

----
{ "walken", cmd_walken, RUN_SETUP },
----

Add it to the `Makefile` near the line for `builtin/worktree.o`:

----
BUILTIN_OBJS += builtin/walken.o
----

Build and test out your command, without forgetting to ensure the `DEVELOPER`
flag is set, and with `GIT_TRACE` enabled so the debug output can be seen:

----
$ echo DEVELOPER=1 >>config.mak
$ make
$ GIT_TRACE=1 ./bin-wrappers/git walken
----

NOTE: For a more exhaustive overview of the new command process, take a look at
`Documentation/MyFirstContribution.txt`.

NOTE: A reference implementation can be found at
https://github.com/nasamuffin/git/tree/revwalk.

=== `struct rev_cmdline_info`

The definition of `struct rev_cmdline_info` can be found in `revision.h`.

This struct is contained within the `rev_info` struct and is used to reflect
parameters provided by the user over the CLI.

`nr` represents the number of `rev_cmdline_entry` present in the array.

`alloc` is used by the `ALLOC_GROW` macro. Check `cache.h` - this variable is
used to track the allocated size of the list.

Per entry, we find:

`item` is the object provided upon which to base the object walk. Items in Git
can be blobs, trees, commits, or tags. (See `Documentation/gittutorial-2.txt`.)

`name` is the object ID (OID) of the object - a hex string you may be familiar
with from using Git to organize your source in the past. Check the tutorial
mentioned above towards the top for a discussion of where the OID can come
from.

`whence` indicates some information about what to do with the parents of the
specified object. We'll explore this flag more later on; take a look at
`Documentation/revisions.txt` to get an idea of what could set the `whence`
value.

`flags` are used to hint the beginning of the revision walk and are the first
block under the `#include`s in `revision.h`. The most likely ones to be set in
the `rev_cmdline_info` are `UNINTERESTING` and `BOTTOM`, but these same flags
can be used during the walk, as well.

=== `struct rev_info`

This one is quite a bit longer, and many fields are only used during the walk
by `revision.c` - not configuration options. Most of the configurable flags in
`struct rev_info` have a mirror in `Documentation/rev-list-options.txt`. It's a
good idea to take some time and read through that document.

== Basic Commit Walk

First, let's see if we can replicate the output of `git log --oneline`. We'll
refer back to the implementation frequently to discover norms when performing
an object walk of our own.

To do so, we'll first find all the commits, in order, which preceded the current
commit. We'll extract the name and subject of the commit from each.

Ideally, we will also be able to find out which ones are currently at the tip of
various branches.

=== Setting Up

Preparing for your object walk has some distinct stages.

1. Perform default setup for this mode, and others which may be invoked.
2. Check configuration files for relevant settings.
3. Set up the `rev_info` struct.
4. Tweak the initialized `rev_info` to suit the current walk.
5. Prepare the `rev_info` for the walk.
6. Iterate over the objects, processing each one.

==== Default Setups

Before examining configuration files which may modify command behavior, set up
default state for switches or options your command may have. If your command
utilizes other Git components, ask them to set up their default states as well.
For instance, `git log` takes advantage of `grep` and `diff` functionality, so
its `init_log_defaults()` sets its own state (`decoration_style`) and asks
`grep` and `diff` to initialize themselves by calling each of their
initialization functions.

For our first example within `git walken`, we don't intend to use any other
components within Git, and we don't have any configuration to do.  However, we
may want to add some later, so for now, we can add an empty placeholder. Create
a new function in `builtin/walken.c`:

----
static void init_walken_defaults(void)
{
	/*
	 * We don't actually need the same components `git log` does; leave this
	 * empty for now.
	 */
}
----

Make sure to add a line invoking it inside of `cmd_walken()`.

----
int cmd_walken(int argc, const char **argv, const char *prefix)
{
	init_walken_defaults();
}
----

==== Configuring From `.gitconfig`

Next, we should have a look at any relevant configuration settings (i.e.,
settings readable and settable from `git config`). This is done by providing a
callback to `git_config()`; within that callback, you can also invoke methods
from other components you may need that need to intercept these options. Your
callback will be invoked once per each configuration value which Git knows about
(global, local, worktree, etc.).

Similarly to the default values, we don't have anything to do here yet
ourselves; however, we should call `git_default_config()` if we aren't calling
any other existing config callbacks.

Add a new function to `builtin/walken.c`:

----
static int git_walken_config(const char *var, const char *value, void *cb)
{
	/*
	 * For now, we don't have any custom configuration, so fall back to
	 * the default config.
	 */
	return git_default_config(var, value, cb);
}
----

Make sure to invoke `git_config()` with it in your `cmd_walken()`:

----
int cmd_walken(int argc, const char **argv, const char *prefix)
{
	...

	git_config(git_walken_config, NULL);

	...
}
----

==== Setting Up `rev_info`

Now that we've gathered external configuration and options, it's time to
initialize the `rev_info` object which we will use to perform the walk. This is
typically done by calling `repo_init_revisions()` with the repository you intend
to target, as well as the `prefix` argument of `cmd_walken` and your `rev_info`
struct.

Add the `struct rev_info` and the `repo_init_revisions()` call:
----
int cmd_walken(int argc, const char **argv, const char *prefix)
{
	/* This can go wherever you like in your declarations.*/
	struct rev_info rev;
	...

	/* This should go after the git_config() call. */
	repo_init_revisions(the_repository, &rev, prefix);

	...
}
----

==== Tweaking `rev_info` For the Walk

We're getting close, but we're still not quite ready to go. Now that `rev` is
initialized, we can modify it to fit our needs. This is usually done within a
helper for clarity, so let's add one:

----
static void final_rev_info_setup(struct rev_info *rev)
{
	/*
	 * We want to mimic the appearance of `git log --oneline`, so let's
	 * force oneline format.
	 */
	get_commit_format("oneline", rev);

	/* Start our object walk at HEAD. */
	add_head_to_pending(rev);
}
----

[NOTE]
====
Instead of using the shorthand `add_head_to_pending()`, you could do
something like this:
----
	struct setup_revision_opt opt;

	memset(&opt, 0, sizeof(opt));
	opt.def = "HEAD";
	opt.revarg_opt = REVARG_COMMITTISH;
	setup_revisions(argc, argv, rev, &opt);
----
Using a `setup_revision_opt` gives you finer control over your walk's starting
point.
====

Then let's invoke `final_rev_info_setup()` after the call to
`repo_init_revisions()`:

----
int cmd_walken(int argc, const char **argv, const char *prefix)
{
	...

	final_rev_info_setup(&rev);

	...
}
----

Later, we may wish to add more arguments to `final_rev_info_setup()`. But for
now, this is all we need.

==== Preparing `rev_info` For the Walk

Now that `rev` is all initialized and configured, we've got one more setup step
before we get rolling. We can do this in a helper, which will both prepare the
`rev_info` for the walk, and perform the walk itself. Let's start the helper
with the call to `prepare_revision_walk()`, which can return an error without
dying on its own:

----
static void walken_commit_walk(struct rev_info *rev)
{
	if (prepare_revision_walk(rev))
		die(_("revision walk setup failed"));
}
----

NOTE: `die()` prints to `stderr` and exits the program. Since it will print to
`stderr` it's likely to be seen by a human, so we will localize it.

==== Performing the Walk!

Finally! We are ready to begin the walk itself. Now we can see that `rev_info`
can also be used as an iterator; we move to the next item in the walk by using
`get_revision()` repeatedly. Add the listed variable declarations at the top and
the walk loop below the `prepare_revision_walk()` call within your
`walken_commit_walk()`:

----
static void walken_commit_walk(struct rev_info *rev)
{
	struct commit *commit;
	struct strbuf prettybuf = STRBUF_INIT;

	...

	while ((commit = get_revision(rev))) {
		strbuf_reset(&prettybuf);
		pp_commit_easy(CMIT_FMT_ONELINE, commit, &prettybuf);
		puts(prettybuf.buf);
	}
	strbuf_release(&prettybuf);
}
----

NOTE: `puts()` prints a `char*` to `stdout`. Since this is the part of the
command we expect to be machine-parsed, we're sending it directly to stdout.

Give it a shot.

----
$ make
$ ./bin-wrappers/git walken
----

You should see all of the subject lines of all the commits in
your tree's history, in order, ending with the initial commit, "Initial revision
of "git", the information manager from hell". Congratulations! You've written
your first revision walk. You can play with printing some additional fields
from each commit if you're curious; have a look at the functions available in
`commit.h`.

=== Adding a Filter

Next, let's try to filter the commits we see based on their author. This is
equivalent to running `git log --author=<pattern>`. We can add a filter by
modifying `rev_info.grep_filter`, which is a `struct grep_opt`.

First some setup. Add `init_grep_defaults()` to `init_walken_defaults()` and add
`grep_config()` to `git_walken_config()`:

----
static void init_walken_defaults(void)
{
	init_grep_defaults(the_repository);
}