Take the first stab at defining revision traversal

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

5 files changed, 360 insertions, 0 deletions

diff --git a/src/git_commit.c b/src/git_commit.c
new file mode 100644
index 000000000..ed6e85be8
--- /dev/null
+++ b/src/git_commit.c
@@ -0,0 +1,41 @@
+/*
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "git_commit.h"
+
+const git_oid_t *git_commit_id(git_commit_t *c)
+{
+	return &c->id;
+}
diff --git a/src/git_commit.h b/src/git_commit.h
new file mode 100644
index 000000000..05bf6713e
--- /dev/null
+++ b/src/git_commit.h
@@ -0,0 +1,92 @@
+/*
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef INCLUDE_git_commit_h__
+#define INCLUDE_git_commit_h__
+
+#include "git_common.h"
+#include "git_oid.h"
+#include <time.h>
+
+/**
+ * @file git_commit.h
+ * @brief Git commit parsing, formatting routines
+ * @defgroup git_commit Git commit parsing, formatting routines
+ * @ingroup Git
+ * @{
+ */
+GIT_BEGIN_DECL
+
+/** Parsed representation of a commit object. */
+typedef struct git_commit_t git_commit_t;
+#ifdef GIT__PRIVATE
+struct git_commit_t {
+	git_oid_t id;
+	time_t commit_time;
+	unsigned parsed:1,
+	         flags:26;
+};
+#endif
+
+/**
+ * Parse (or lookup) a commit from a revision pool.
+ * @param pool the pool to use when parsing/caching the commit.
+ * @param id identity of the commit to locate.  If the object is
+ *        an annotated tag it will be peeled back to the commit.
+ * @return the commit; NULL if the commit does not exist in the
+ *         pool's git_odb_t, or if the commit is present but is
+ *         too malformed to be parsed successfully.
+ */
+GIT_EXTERN(git_commit_t*) git_commit_parse(git_revp_t *pool, const git_oid_t *id);
+
+/**
+ * Get the id of a commit.
+ * @param commit a previously parsed commit.
+ * @return object identity for the commit.
+ */
+GIT_EXTERN(const git_oid_t*) git_commit_id(git_commit_t *commit);
+
+/**
+ * Get the application data address.
+ * @param commit a previously parsed commit.
+ * @return address of the application's data buffer.
+ *         Applications should cast to something like
+ *         'struct mydata*' in order to access fields.
+ */
+GIT_EXTERN(void*) git_commit_appdata(git_commit_t *commit);
+
+/** @} */
+GIT_END_DECL
+#endif
diff --git a/src/git_common.h b/src/git_common.h
index f5121b1e6..6e19d89f3 100644
--- a/src/git_common.h
+++ b/src/git_common.h
@@ -78,6 +78,9 @@ typedef int git_result_t;
 /** Input does not exist in the scope searched. */
 #define GIT_ENOTFOUND (GIT_ERROR - 2)
 
+/** A revision traversal pool. */
+typedef struct git_revp_t git_revp_t;
+
 /** @} */
 GIT_END_DECL
 #endif
diff --git a/src/git_revwalk.c b/src/git_revwalk.c
new file mode 100644
index 000000000..7b7d17f9b
--- /dev/null
+++ b/src/git_revwalk.c
@@ -0,0 +1,71 @@
+/*
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "git_revwalk.h"
+#include <stdlib.h>
+#include <string.h>
+
+struct git_revp_attr_t {
+	size_t app_size;
+	git_result_t (*app_init)(git_commit_t *, void *);
+};
+
+struct git_revp_t {
+	git_odb_t *db;
+	git_revp_attr_t attr;
+};
+
+
+git_revp_t *git_revp_alloc(
+	git_odb_t *db,
+	const git_revp_attr_t *attr)
+{
+	git_revp_t *walk = malloc(sizeof(*walk));
+	if (!walk)
+		return NULL;
+
+	walk->db = db;
+	if (attr)
+		memcpy(&walk->attr, attr, sizeof(walk->attr));
+	else
+		memset(&walk->attr, 0, sizeof(walk->attr));
+
+	return walk;
+}
+
+void git_revp_free(git_revp_t *walk)
+{
+	free(walk);
+}
diff --git a/src/git_revwalk.h b/src/git_revwalk.h
new file mode 100644
index 000000000..a84d13091
--- /dev/null
+++ b/src/git_revwalk.h
@@ -0,0 +1,153 @@
+/*
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef INCLUDE_git_revwalk_h__
+#define INCLUDE_git_revwalk_h__
+
+#include "git_common.h"
+#include "git_odb.h"
+#include "git_commit.h"
+
+/**
+ * @file git_revwalk.h
+ * @brief Git revision traversal routines
+ * @defgroup git_revwalk Git revision traversal routines
+ * @ingroup Git
+ * @{
+ */
+GIT_BEGIN_DECL
+
+/** Configuration of a revision pool. */
+typedef struct git_revp_attr_t git_revp_attr_t;
+
+/**
+ * Allocate an empty pool configuration.
+ *
+ * The resulting configuration is identical to passing NULL
+ * to git_revp_alloc().
+ *
+ * @return a new configuration block.
+ *         NULL if there is insufficient memory.
+ */
+GIT_EXTERN(git_revp_attr_t*) git_revp_attr_alloc(void);
+
+/**
+ * Setup the application's per-commit data allocation.
+ *
+ * If size is non-zero the requested number of bytes is allocated
+ * alongside every git_commit_t used by the revision pool, allowing
+ * constant-time access to per-commit application data.
+ *
+ * If init is not NULL the function is invoked with the commit and
+ * the application data pointer, allowing the function to populate
+ * the application's data space the first time the commit is parsed
+ * into the pool.  Space available within the application data is
+ * not initialized.  Subsequent resets do not invoke this method.
+ *
+ * If init is NULL and size is non-zero the application data space
+ * is cleared during the first parse.
+ *
+ * @param attr the pool configuration to adjust.
+ * @param size number of bytes required by the application on
+ *        each rev_commit_t instance within the pool.
+ * @param init optional callback function to initialize the
+ *        application data space.  If NULL the application
+ *        space will be zeroed.  If supplied the application
+ *        space may contain random garbage.
+ */
+GIT_EXTERN(void) git_revp_attr_appdata(
+	git_revp_attr_t *attr,
+	size_t size,
+	git_result_t (*init)(git_commit_t *, void *));
+
+/**
+ * Free a pool configuration.
+ * @param attr the configuration to free.  No-op if NULL.
+ */
+GIT_EXTERN(void) git_revp_attr_free(git_revp_attr_t *attr);
+
+/**
+ * Allocate a new revision traversal pool.
+ *
+ * The configuration is copied during allocation.  Changes
+ * to the configuration after allocation do not affect the pool
+ * returned by this function.  Callers may safely free the
+ * passed configuration after the function completes.
+ *
+ * @param db the database objects are read from.
+ * @param attr configuration for the pool.
+ *        NULL to use a default configuration.
+ * @return the new traversal handle; NULL if memory is exhausted.
+ */
+GIT_EXTERN(git_revp_t*) git_revp_alloc(
+	git_odb_t *db,
+	const git_revp_attr_t *attr);
+
+/**
+ * Reset the traversal machinary for reuse.
+ * @param pool traversal handle to reset.
+ */
+GIT_EXTERN(void) git_revp_reset(git_revp_t *pool);
+
+/**
+ * Mark an object to start traversal from.
+ * @param pool the pool being used for the traversal.
+ * @param commit the commit the commit to start from.
+ */
+GIT_EXTERN(void) git_revp_pushc(git_revp_t *pool, git_commit_t *commit);
+
+/**
+ * Mark a commit (and its ancestors) uninteresting for the output.
+ * @param pool the pool being used for the traversal.
+ * @param commit the commit the commit to start from.
+ */
+GIT_EXTERN(void) git_revp_hidec(git_revp_t *pool, git_commit_t *commit);
+
+/**
+ * Get the next commit from the revision traversal.
+ * @param pool the pool to pop the commit from.
+ * @return next commit; NULL if there is no more output.
+ */
+GIT_EXTERN(git_commit_t*) git_revp_nextc(git_revp_t *pool);
+
+/**
+ * Free a revwalk previously allocated.
+ * @param pool traversal handle to close.  If NULL nothing occurs.
+ */
+GIT_EXTERN(void) git_revp_free(git_revp_t *pool);
+
+/** @} */
+GIT_END_DECL
+#endif