rename got_commit_graph_iter_start() to got_commit_graph_bfsort() This function begins a breadth-first traversal. The new name makes it easier to distinguish from got_commit_graph_toposort().

remove a confusing comment This function starts a breadth-first traversal, not necessarily first-parent.

make 'got rebase' find a merge base with topological sorting if needed Fixes a problematic case of spurious conflicts encountered by naddy@ on landry's firefox package git repository. The current implementation of toposort is expensive, so this might make rebase appear to run slowly on large repositories. However, this is better than letting users deal with spurious conflicts. ok op@

add support for topological sorting to the commit graph The algorithm implemented here is based on a description I read on github's blog. See code comments for details. ok op@

remove GOT_ERR_ITER_BUSY from got_commit_graph_iter_start() Just clear any left-over iteration state and begin a fresh iteration instead of returning GOT_ERR_ITER_BUSY if the caller did not loop through the entire graph. This change currently doesn't matter much since all existing callers only do a single pass over the graph. But it frees up an error code and makes this API more flexible.

handle merge commits that are unrelated to requested changed path history Problem found and fix tested by James Cook.

simplify ancestry checks in checkout, update, rebase, and merge No behaviour change as the end result of the rewritten checks should be the same as before. We are just doing less work where possible. Patch by James Cook

include sha2.h too where sha1.h is included In preparation for wide sha256 support; stsp@ agrees. Change done mechanically with find . -iname \*.[cy] -exec sam {} + X ,x/<sha1\.h>/i/\n#include <sha2.h>

make got_commit_graph_iter_next use caller-provided storage for the id and adjust the callers. discussed with and ok stsp@

plug leak in the commit graph iterator We fail to release the memory for the nodes. To fix it however, we some consumer of the commit graph iterator need to be corrected: the returned pointer is safe to be used only up until the next iter_next call; save a copy it if it's needed afterwards too. ok stsp@

replace an indirect call to idset_add(), via add_node(), with a direct call Avoids leaking the node structure returned from add_node(). ok op@

free commit on error path while here drop the ternary too: if add_node succeeds `new_node' is non-NULL. ok stsp@

plug leak: release nodes not added to the iter list ok stsp@

got_commit_graph_close: free tailq contents The tailq should ideally be empty when we reach got_commit_graph_close, but consumer code may exit the commit graph loop earlier. spotted by and ok stsp@

inline struct got_object_id in struct got_object_qid Saves us from doing a malloc/free call for every item on the list. ok op@

stop relying on commit cache for good performance of got_object_id_by_path() Instead of internally opening and closing the same commit object over and over again, require callers to pass an open commit object in. Avoids an inherent dependency on the commit object cache for reasonable performance. ok op@

make it possible to merge vendor branches with 'got merge'

switch from SIMPLEQ to equivalent STAILQ macros The singly-linked tail queue macros were added to OpenBSD 6.9 and are more widely available on other systems. ok stsp

add support for first-parent history traversal to got-read-pack

add copyright year for files already touched in 2020

revert e7a5b9e9b763327a7e1ddd69f6bc533565d60794; it changed blame output

commit graph's close_branch() can be inlined in one place

small simplification in got_commit_graph_iter_next()

remove a misleading comment

remove redundant code from add_node_to_iter_list()