1 372ccdbb 2018-06-10 stsp /*
  2 5aa81393 2020-01-06 stsp  * Copyright (c) 2018, 2019, 2020 Stefan Sperling <stsp@openbsd.org>
  3 372ccdbb 2018-06-10 stsp  *
  4 372ccdbb 2018-06-10 stsp  * Permission to use, copy, modify, and distribute this software for any
  5 372ccdbb 2018-06-10 stsp  * purpose with or without fee is hereby granted, provided that the above
  6 372ccdbb 2018-06-10 stsp  * copyright notice and this permission notice appear in all copies.
  7 372ccdbb 2018-06-10 stsp  *
  8 372ccdbb 2018-06-10 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  9 372ccdbb 2018-06-10 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 10 372ccdbb 2018-06-10 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 11 372ccdbb 2018-06-10 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 12 372ccdbb 2018-06-10 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 13 372ccdbb 2018-06-10 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 14 372ccdbb 2018-06-10 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 15 372ccdbb 2018-06-10 stsp  */
 16 372ccdbb 2018-06-10 stsp 
 17 372ccdbb 2018-06-10 stsp #include <sys/types.h>
 18 372ccdbb 2018-06-10 stsp #include <sys/stat.h>
 19 8b925c6c 2022-07-16 thomas #include <sys/queue.h>
 20 372ccdbb 2018-06-10 stsp 
 21 56e0773d 2019-11-28 stsp #include <limits.h>
 22 372ccdbb 2018-06-10 stsp #include <stdio.h>
 23 372ccdbb 2018-06-10 stsp #include <stdlib.h>
 24 372ccdbb 2018-06-10 stsp #include <string.h>
 25 372ccdbb 2018-06-10 stsp #include <zlib.h>
 26 372ccdbb 2018-06-10 stsp #include <ctype.h>
 27 dd038bc6 2021-09-21 thomas.ad 
 28 dd038bc6 2021-09-21 thomas.ad #include "got_compat.h"
 29 372ccdbb 2018-06-10 stsp 
 30 372ccdbb 2018-06-10 stsp #include "got_error.h"
 31 372ccdbb 2018-06-10 stsp #include "got_object.h"
 32 6fb7cd11 2019-08-22 stsp #include "got_cancel.h"
 33 372ccdbb 2018-06-10 stsp #include "got_commit_graph.h"
 34 324d37e7 2019-05-11 stsp #include "got_path.h"
 35 372ccdbb 2018-06-10 stsp 
 36 372ccdbb 2018-06-10 stsp #include "got_lib_delta.h"
 37 63581804 2018-07-09 stsp #include "got_lib_inflate.h"
 38 372ccdbb 2018-06-10 stsp #include "got_lib_object.h"
 39 372ccdbb 2018-06-10 stsp #include "got_lib_object_idset.h"
 40 372ccdbb 2018-06-10 stsp 
 41 372ccdbb 2018-06-10 stsp struct got_commit_graph_node {
 42 372ccdbb 2018-06-10 stsp 	struct got_object_id id;
 43 b43fbaa0 2018-06-11 stsp 
 44 ca6e02ac 2020-01-07 stsp 	/* Used only during iteration. */
 45 ca6e02ac 2020-01-07 stsp 	time_t timestamp;
 46 372ccdbb 2018-06-10 stsp 	TAILQ_ENTRY(got_commit_graph_node) entry;
 47 372ccdbb 2018-06-10 stsp };
 48 372ccdbb 2018-06-10 stsp 
 49 9ba79e04 2018-06-11 stsp TAILQ_HEAD(got_commit_graph_iter_list, got_commit_graph_node);
 50 9ba79e04 2018-06-11 stsp 
 51 b565f6f8 2018-07-23 stsp struct got_commit_graph_branch_tip {
 52 32777563 2018-11-07 stsp 	struct got_object_id *commit_id;
 53 32777563 2018-11-07 stsp 	struct got_commit_object *commit;
 54 32777563 2018-11-07 stsp 	struct got_commit_graph_node *new_node;
 55 b565f6f8 2018-07-23 stsp };
 56 b565f6f8 2018-07-23 stsp 
 57 372ccdbb 2018-06-10 stsp struct got_commit_graph {
 58 372ccdbb 2018-06-10 stsp 	/* The set of all commits we have traversed. */
 59 372ccdbb 2018-06-10 stsp 	struct got_object_idset *node_ids;
 60 372ccdbb 2018-06-10 stsp 
 61 0ed6ed4c 2018-06-13 stsp 	int flags;
 62 0ed6ed4c 2018-06-13 stsp #define GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL		0x01
 63 0ed6ed4c 2018-06-13 stsp 
 64 372ccdbb 2018-06-10 stsp 	/*
 65 372ccdbb 2018-06-10 stsp 	 * A set of object IDs of known parent commits which we have not yet
 66 372ccdbb 2018-06-10 stsp 	 * traversed. Each commit ID in this set represents a branch in commit
 67 372ccdbb 2018-06-10 stsp 	 * history: Either the first-parent branch of the head node, or another
 68 372ccdbb 2018-06-10 stsp 	 * branch corresponding to a traversed merge commit for which we have
 69 372ccdbb 2018-06-10 stsp 	 * not traversed a branch point commit yet.
 70 372ccdbb 2018-06-10 stsp 	 *
 71 372ccdbb 2018-06-10 stsp 	 * Whenever we add a commit with a matching ID to the graph, we remove
 72 372ccdbb 2018-06-10 stsp 	 * its corresponding element from this set, and add new elements for
 73 372ccdbb 2018-06-10 stsp 	 * each of that commit's parent commits which were not traversed yet.
 74 372ccdbb 2018-06-10 stsp 	 *
 75 372ccdbb 2018-06-10 stsp 	 * When API users ask us to fetch more commits, we fetch commits from
 76 372ccdbb 2018-06-10 stsp 	 * all currently open branches. This allows API users to process
 77 372ccdbb 2018-06-10 stsp 	 * commits in linear order even though the history contains branches.
 78 372ccdbb 2018-06-10 stsp 	 */
 79 372ccdbb 2018-06-10 stsp 	struct got_object_idset *open_branches;
 80 b565f6f8 2018-07-23 stsp 
 81 32777563 2018-11-07 stsp 	/* Array of branch tips for fetch_commits_from_open_branches(). */
 82 b565f6f8 2018-07-23 stsp 	struct got_commit_graph_branch_tip *tips;
 83 5e50c36a 2018-11-08 stsp 	int ntips;
 84 372ccdbb 2018-06-10 stsp 
 85 31cedeaf 2018-09-15 stsp 	/* Path of tree entry of interest to the API user. */
 86 31cedeaf 2018-09-15 stsp 	char *path;
 87 31cedeaf 2018-09-15 stsp 
 88 94489f7d 2020-01-04 stsp 	/*
 89 94489f7d 2020-01-04 stsp 	 * Nodes which will be passed to the API user next, sorted by
 90 94489f7d 2020-01-04 stsp 	 * commit timestmap.
 91 94489f7d 2020-01-04 stsp 	 */
 92 9ba79e04 2018-06-11 stsp 	struct got_commit_graph_iter_list iter_list;
 93 372ccdbb 2018-06-10 stsp };
 94 372ccdbb 2018-06-10 stsp 
 95 31cedeaf 2018-09-15 stsp static const struct got_error *
 96 41fa1437 2018-11-05 stsp detect_changed_path(int *changed, struct got_commit_object *commit,
 97 31cedeaf 2018-09-15 stsp     struct got_object_id *commit_id, const char *path,
 98 31cedeaf 2018-09-15 stsp     struct got_repository *repo)
 99 31cedeaf 2018-09-15 stsp {
100 31cedeaf 2018-09-15 stsp 	const struct got_error *err = NULL;
101 41fa1437 2018-11-05 stsp 	struct got_commit_object *pcommit = NULL;
102 31cedeaf 2018-09-15 stsp 	struct got_tree_object *tree = NULL, *ptree = NULL;
103 31cedeaf 2018-09-15 stsp 	struct got_object_qid *pid;
104 31cedeaf 2018-09-15 stsp 
105 31cedeaf 2018-09-15 stsp 	if (got_path_is_root_dir(path)) {
106 31cedeaf 2018-09-15 stsp 		*changed = 1;
107 31cedeaf 2018-09-15 stsp 		return NULL;
108 31cedeaf 2018-09-15 stsp 	}
109 31cedeaf 2018-09-15 stsp 
110 31cedeaf 2018-09-15 stsp 	*changed = 0;
111 31cedeaf 2018-09-15 stsp 
112 dbdddfee 2021-06-23 naddy 	pid = STAILQ_FIRST(&commit->parent_ids);
113 31cedeaf 2018-09-15 stsp 	if (pid == NULL) {
114 31cedeaf 2018-09-15 stsp 		struct got_object_id *obj_id;
115 945f9229 2022-04-16 thomas 		err = got_object_id_by_path(&obj_id, repo, commit, path);
116 fd1d2703 2018-11-04 stsp 		if (err) {
117 d1451975 2018-11-11 stsp 			if (err->code == GOT_ERR_NO_TREE_ENTRY)
118 fd1d2703 2018-11-04 stsp 				err = NULL;
119 fd1d2703 2018-11-04 stsp 		} else
120 fd1d2703 2018-11-04 stsp 			*changed = 1; /* The path was created in this commit. */
121 31cedeaf 2018-09-15 stsp 		free(obj_id);
122 0e9101d5 2018-11-18 stsp 		return err;
123 0e9101d5 2018-11-18 stsp 	}
124 7310c1c3 2018-11-18 stsp 
125 0e9101d5 2018-11-18 stsp 	err = got_object_open_as_tree(&tree, repo, commit->tree_id);
126 0e9101d5 2018-11-18 stsp 	if (err)
127 0e9101d5 2018-11-18 stsp 		return err;
128 372ccdbb 2018-06-10 stsp 
129 ec242592 2022-04-22 thomas 	err = got_object_open_as_commit(&pcommit, repo, &pid->id);
130 0e9101d5 2018-11-18 stsp 	if (err)
131 0e9101d5 2018-11-18 stsp 		goto done;
132 0e9101d5 2018-11-18 stsp 
133 0e9101d5 2018-11-18 stsp 	err = got_object_open_as_tree(&ptree, repo, pcommit->tree_id);
134 0e9101d5 2018-11-18 stsp 	if (err)
135 0e9101d5 2018-11-18 stsp 		goto done;
136 0e9101d5 2018-11-18 stsp 
137 81a966c0 2018-11-18 stsp 	err = got_object_tree_path_changed(changed, tree, ptree, path, repo);
138 31cedeaf 2018-09-15 stsp done:
139 31cedeaf 2018-09-15 stsp 	if (tree)
140 31cedeaf 2018-09-15 stsp 		got_object_tree_close(tree);
141 31cedeaf 2018-09-15 stsp 	if (ptree)
142 31cedeaf 2018-09-15 stsp 		got_object_tree_close(ptree);
143 31cedeaf 2018-09-15 stsp 	if (pcommit)
144 41fa1437 2018-11-05 stsp 		got_object_commit_close(pcommit);
145 31cedeaf 2018-09-15 stsp 	return err;
146 31cedeaf 2018-09-15 stsp }
147 31cedeaf 2018-09-15 stsp 
148 4626e416 2018-06-10 stsp static void
149 9ba79e04 2018-06-11 stsp add_node_to_iter_list(struct got_commit_graph *graph,
150 ca6e02ac 2020-01-07 stsp     struct got_commit_graph_node *node, time_t committer_time)
151 372ccdbb 2018-06-10 stsp {
152 4bd3f2bb 2018-06-10 stsp 	struct got_commit_graph_node *n, *next;
153 1c7a5dcb 2018-09-15 stsp 
154 ca6e02ac 2020-01-07 stsp 	node->timestamp = committer_time;
155 ca6e02ac 2020-01-07 stsp 
156 94489f7d 2020-01-04 stsp 	n = TAILQ_FIRST(&graph->iter_list);
157 bee6b577 2018-09-19 stsp 	while (n) {
158 bee6b577 2018-09-19 stsp 		next = TAILQ_NEXT(n, entry);
159 73026088 2018-11-18 stsp 		if (next && node->timestamp >= next->timestamp) {
160 bee6b577 2018-09-19 stsp 			TAILQ_INSERT_BEFORE(next, node, entry);
161 bee6b577 2018-09-19 stsp 			return;
162 fe8df4c2 2018-06-16 stsp 		}
163 bee6b577 2018-09-19 stsp 		n = next;
164 fe8df4c2 2018-06-16 stsp 	}
165 93e45b7c 2018-09-24 stsp 	TAILQ_INSERT_TAIL(&graph->iter_list, node, entry);
166 0ed6ed4c 2018-06-13 stsp }
167 0ed6ed4c 2018-06-13 stsp 
168 0ed6ed4c 2018-06-13 stsp static const struct got_error *
169 ca6e02ac 2020-01-07 stsp add_node(struct got_commit_graph_node **new_node,
170 ca6e02ac 2020-01-07 stsp     struct got_commit_graph *graph, struct got_object_id *commit_id,
171 ca6e02ac 2020-01-07 stsp     struct got_repository *repo)
172 ca6e02ac 2020-01-07 stsp {
173 ca6e02ac 2020-01-07 stsp 	const struct got_error *err = NULL;
174 ca6e02ac 2020-01-07 stsp 	struct got_commit_graph_node *node;
175 ca6e02ac 2020-01-07 stsp 
176 ca6e02ac 2020-01-07 stsp 	*new_node = NULL;
177 ca6e02ac 2020-01-07 stsp 
178 ca6e02ac 2020-01-07 stsp 	node = calloc(1, sizeof(*node));
179 ca6e02ac 2020-01-07 stsp 	if (node == NULL)
180 ca6e02ac 2020-01-07 stsp 		return got_error_from_errno("calloc");
181 ca6e02ac 2020-01-07 stsp 
182 ca6e02ac 2020-01-07 stsp 	memcpy(&node->id, commit_id, sizeof(node->id));
183 ca6e02ac 2020-01-07 stsp 	err = got_object_idset_add(graph->node_ids, &node->id, NULL);
184 ca6e02ac 2020-01-07 stsp 	if (err)
185 ca6e02ac 2020-01-07 stsp 		free(node);
186 ca6e02ac 2020-01-07 stsp 	else
187 ca6e02ac 2020-01-07 stsp 		*new_node = node;
188 ca6e02ac 2020-01-07 stsp 	return err;
189 ca6e02ac 2020-01-07 stsp }
190 ca6e02ac 2020-01-07 stsp 
191 ca6e02ac 2020-01-07 stsp /*
192 ca6e02ac 2020-01-07 stsp  * Ask got-read-pack to traverse first-parent history until a commit is
193 ca6e02ac 2020-01-07 stsp  * encountered which modified graph->path, or until the pack file runs
194 ca6e02ac 2020-01-07 stsp  * out of relevant commits. This is faster than sending an individual
195 ca6e02ac 2020-01-07 stsp  * request for each commit stored in the pack file.
196 ca6e02ac 2020-01-07 stsp  */
197 ca6e02ac 2020-01-07 stsp static const struct got_error *
198 ca6e02ac 2020-01-07 stsp packed_first_parent_traversal(int *ncommits_traversed,
199 ca6e02ac 2020-01-07 stsp     struct got_commit_graph *graph, struct got_object_id *commit_id,
200 ca6e02ac 2020-01-07 stsp     struct got_repository *repo)
201 ca6e02ac 2020-01-07 stsp {
202 ca6e02ac 2020-01-07 stsp 	const struct got_error *err = NULL;
203 ca6e02ac 2020-01-07 stsp 	struct got_object_id_queue traversed_commits;
204 ca6e02ac 2020-01-07 stsp 	struct got_object_qid *qid;
205 ca6e02ac 2020-01-07 stsp 
206 dbdddfee 2021-06-23 naddy 	STAILQ_INIT(&traversed_commits);
207 ca6e02ac 2020-01-07 stsp 	*ncommits_traversed = 0;
208 ca6e02ac 2020-01-07 stsp 
209 ca6e02ac 2020-01-07 stsp 	err = got_traverse_packed_commits(&traversed_commits,
210 ca6e02ac 2020-01-07 stsp 	    commit_id, graph->path, repo);
211 ca6e02ac 2020-01-07 stsp 	if (err)
212 ca6e02ac 2020-01-07 stsp 		return err;
213 ca6e02ac 2020-01-07 stsp 
214 ca6e02ac 2020-01-07 stsp 	/* Add all traversed commits to the graph... */
215 dbdddfee 2021-06-23 naddy 	STAILQ_FOREACH(qid, &traversed_commits, entry) {
216 ec242592 2022-04-22 thomas 		if (got_object_idset_contains(graph->open_branches, &qid->id))
217 ca6e02ac 2020-01-07 stsp 			continue;
218 ec242592 2022-04-22 thomas 		if (got_object_idset_contains(graph->node_ids, &qid->id))
219 ca6e02ac 2020-01-07 stsp 			continue;
220 ca6e02ac 2020-01-07 stsp 
221 ca6e02ac 2020-01-07 stsp 		(*ncommits_traversed)++;
222 ca6e02ac 2020-01-07 stsp 
223 ca6e02ac 2020-01-07 stsp 		/* ... except the last commit is the new branch tip. */
224 dbdddfee 2021-06-23 naddy 		if (STAILQ_NEXT(qid, entry) == NULL) {
225 ca6e02ac 2020-01-07 stsp 			err = got_object_idset_add(graph->open_branches,
226 ec242592 2022-04-22 thomas 			    &qid->id, NULL);
227 ca6e02ac 2020-01-07 stsp 			break;
228 ca6e02ac 2020-01-07 stsp 		}
229 ca6e02ac 2020-01-07 stsp 
230 99c6f580 2022-09-05 thomas 		err = got_object_idset_add(graph->node_ids, &qid->id, NULL);
231 ca6e02ac 2020-01-07 stsp 		if (err)
232 ca6e02ac 2020-01-07 stsp 			break;
233 ca6e02ac 2020-01-07 stsp 	}
234 ca6e02ac 2020-01-07 stsp 
235 ca6e02ac 2020-01-07 stsp 	got_object_id_queue_free(&traversed_commits);
236 ca6e02ac 2020-01-07 stsp 	return err;
237 ca6e02ac 2020-01-07 stsp }
238 ca6e02ac 2020-01-07 stsp 
239 ca6e02ac 2020-01-07 stsp static const struct got_error *
240 32c85d2c 2020-01-06 stsp close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id)
241 32c85d2c 2020-01-06 stsp {
242 32c85d2c 2020-01-06 stsp 	const struct got_error *err;
243 32c85d2c 2020-01-06 stsp 
244 32c85d2c 2020-01-06 stsp 	err = got_object_idset_remove(NULL, graph->open_branches, commit_id);
245 32c85d2c 2020-01-06 stsp 	if (err && err->code != GOT_ERR_NO_OBJ)
246 32c85d2c 2020-01-06 stsp 		return err;
247 32c85d2c 2020-01-06 stsp 	return NULL;
248 32c85d2c 2020-01-06 stsp }
249 32c85d2c 2020-01-06 stsp 
250 32c85d2c 2020-01-06 stsp static const struct got_error *
251 14159a7b 2020-01-04 stsp advance_branch(struct got_commit_graph *graph, struct got_object_id *commit_id,
252 14159a7b 2020-01-04 stsp     struct got_commit_object *commit, struct got_repository *repo)
253 0ed6ed4c 2018-06-13 stsp {
254 0ed6ed4c 2018-06-13 stsp 	const struct got_error *err;
255 0ed6ed4c 2018-06-13 stsp 	struct got_object_qid *qid;
256 bae38d30 2024-02-11 thomas 	struct got_object_id *merged_id = NULL;
257 0ed6ed4c 2018-06-13 stsp 
258 32c85d2c 2020-01-06 stsp 	err = close_branch(graph, commit_id);
259 32c85d2c 2020-01-06 stsp 	if (err)
260 32c85d2c 2020-01-06 stsp 		return err;
261 32c85d2c 2020-01-06 stsp 
262 0ed6ed4c 2018-06-13 stsp 	if (graph->flags & GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL) {
263 dbdddfee 2021-06-23 naddy 		qid = STAILQ_FIRST(&commit->parent_ids);
264 9b88e78c 2018-11-18 stsp 		if (qid == NULL ||
265 ec242592 2022-04-22 thomas 		    got_object_idset_contains(graph->open_branches, &qid->id))
266 0ed6ed4c 2018-06-13 stsp 			return NULL;
267 ca6e02ac 2020-01-07 stsp 		/*
268 ca6e02ac 2020-01-07 stsp 		 * The root directory always changes by definition, and when
269 ca6e02ac 2020-01-07 stsp 		 * logging the root we want to traverse consecutive commits
270 ca6e02ac 2020-01-07 stsp 		 * even if they point at the same tree.
271 ca6e02ac 2020-01-07 stsp 		 * But if we are looking for a specific path then we can avoid
272 ca6e02ac 2020-01-07 stsp 		 * fetching packed commits which did not modify the path and
273 ca6e02ac 2020-01-07 stsp 		 * only fetch their IDs. This speeds up 'got blame'.
274 ca6e02ac 2020-01-07 stsp 		 */
275 ca6e02ac 2020-01-07 stsp 		if (!got_path_is_root_dir(graph->path) &&
276 ca6e02ac 2020-01-07 stsp 		    (commit->flags & GOT_COMMIT_FLAG_PACKED)) {
277 ca6e02ac 2020-01-07 stsp 			int ncommits = 0;
278 ca6e02ac 2020-01-07 stsp 			err = packed_first_parent_traversal(&ncommits,
279 ec242592 2022-04-22 thomas 			    graph, &qid->id, repo);
280 ca6e02ac 2020-01-07 stsp 			if (err || ncommits > 0)
281 ca6e02ac 2020-01-07 stsp 				return err;
282 ca6e02ac 2020-01-07 stsp 		}
283 9b88e78c 2018-11-18 stsp 		return got_object_idset_add(graph->open_branches,
284 ec242592 2022-04-22 thomas 		    &qid->id, NULL);
285 bee6b577 2018-09-19 stsp 	}
286 bee6b577 2018-09-19 stsp 
287 bee6b577 2018-09-19 stsp 	/*
288 bee6b577 2018-09-19 stsp 	 * If we are graphing commits for a specific path, skip branches
289 bee6b577 2018-09-19 stsp 	 * which do not contribute any content to this path.
290 bee6b577 2018-09-19 stsp 	 */
291 7a62478b 2018-11-18 stsp 	if (commit->nparents > 1 && !got_path_is_root_dir(graph->path)) {
292 bae38d30 2024-02-11 thomas 		err = got_object_id_by_path(&merged_id, repo, commit, graph->path);
293 bae38d30 2024-02-11 thomas 		if (err && err->code != GOT_ERR_NO_TREE_ENTRY)
294 bae38d30 2024-02-11 thomas 			return err;
295 bae38d30 2024-02-11 thomas 		/* The requested path does not exist in this merge commit. */
296 bae38d30 2024-02-11 thomas 	}
297 bae38d30 2024-02-11 thomas 	if (commit->nparents > 1 && !got_path_is_root_dir(graph->path) &&
298 bae38d30 2024-02-11 thomas 	    merged_id != NULL) {
299 bae38d30 2024-02-11 thomas 		struct got_object_id *prev_id = NULL;
300 bee6b577 2018-09-19 stsp 		int branches_differ = 0;
301 bee6b577 2018-09-19 stsp 
302 bee6b577 2018-09-19 stsp 
303 dbdddfee 2021-06-23 naddy 		STAILQ_FOREACH(qid, &commit->parent_ids, entry) {
304 945f9229 2022-04-16 thomas 			struct got_object_id *id = NULL;
305 945f9229 2022-04-16 thomas 			struct got_commit_object *pcommit = NULL;
306 6dcdad08 2018-11-18 stsp 
307 8e291695 2020-01-04 stsp 			if (got_object_idset_contains(graph->open_branches,
308 ec242592 2022-04-22 thomas 			    &qid->id))
309 9b88e78c 2018-11-18 stsp 				continue;
310 bee6b577 2018-09-19 stsp 
311 945f9229 2022-04-16 thomas 			err = got_object_open_as_commit(&pcommit, repo,
312 ec242592 2022-04-22 thomas 			    &qid->id);
313 945f9229 2022-04-16 thomas 			if (err) {
314 945f9229 2022-04-16 thomas 				free(merged_id);
315 945f9229 2022-04-16 thomas 				free(prev_id);
316 945f9229 2022-04-16 thomas 				return err;
317 945f9229 2022-04-16 thomas 			}
318 945f9229 2022-04-16 thomas 			err = got_object_id_by_path(&id, repo, pcommit,
319 bee6b577 2018-09-19 stsp 			    graph->path);
320 945f9229 2022-04-16 thomas 			got_object_commit_close(pcommit);
321 945f9229 2022-04-16 thomas 			pcommit = NULL;
322 bee6b577 2018-09-19 stsp 			if (err) {
323 d1451975 2018-11-11 stsp 				if (err->code == GOT_ERR_NO_TREE_ENTRY) {
324 bee6b577 2018-09-19 stsp 					branches_differ = 1;
325 bee6b577 2018-09-19 stsp 					continue;
326 bee6b577 2018-09-19 stsp 				}
327 6dcdad08 2018-11-18 stsp 				free(merged_id);
328 6dcdad08 2018-11-18 stsp 				free(prev_id);
329 bee6b577 2018-09-19 stsp 				return err;
330 bee6b577 2018-09-19 stsp 			}
331 bee6b577 2018-09-19 stsp 
332 bee6b577 2018-09-19 stsp 			if (prev_id) {
333 bee6b577 2018-09-19 stsp 				if (!branches_differ &&
334 d2c2d781 2018-11-18 stsp 				    got_object_id_cmp(id, prev_id) != 0)
335 bee6b577 2018-09-19 stsp 					branches_differ = 1;
336 6dcdad08 2018-11-18 stsp 				free(prev_id);
337 6dcdad08 2018-11-18 stsp 			}
338 6dcdad08 2018-11-18 stsp 			prev_id = id;
339 bee6b577 2018-09-19 stsp 
340 bee6b577 2018-09-19 stsp 			/*
341 bee6b577 2018-09-19 stsp 			 * If a branch has created the merged content we can
342 bee6b577 2018-09-19 stsp 			 * skip any other branches.
343 bee6b577 2018-09-19 stsp 			 */
344 bee6b577 2018-09-19 stsp 			if (got_object_id_cmp(merged_id, id) == 0) {
345 b36429ab 2018-11-05 stsp 				err = got_object_idset_add(graph->open_branches,
346 ec242592 2022-04-22 thomas 				    &qid->id, NULL);
347 6dcdad08 2018-11-18 stsp 				free(merged_id);
348 6dcdad08 2018-11-18 stsp 				free(id);
349 b36429ab 2018-11-05 stsp 				return err;
350 bee6b577 2018-09-19 stsp 			}
351 bee6b577 2018-09-19 stsp 		}
352 6dcdad08 2018-11-18 stsp 
353 6dcdad08 2018-11-18 stsp 		free(prev_id);
354 6dcdad08 2018-11-18 stsp 		prev_id = NULL;
355 6dcdad08 2018-11-18 stsp 		free(merged_id);
356 6dcdad08 2018-11-18 stsp 		merged_id = NULL;
357 bee6b577 2018-09-19 stsp 
358 bee6b577 2018-09-19 stsp 		/*
359 bee6b577 2018-09-19 stsp 		 * If the path's content is the same on all branches,
360 bee6b577 2018-09-19 stsp 		 * follow the first parent only.
361 bee6b577 2018-09-19 stsp 		 */
362 bee6b577 2018-09-19 stsp 		if (!branches_differ) {
363 dbdddfee 2021-06-23 naddy 			qid = STAILQ_FIRST(&commit->parent_ids);
364 bee6b577 2018-09-19 stsp 			if (qid == NULL)
365 bee6b577 2018-09-19 stsp 				return NULL;
366 8e291695 2020-01-04 stsp 			if (got_object_idset_contains(graph->open_branches,
367 ec242592 2022-04-22 thomas 			    &qid->id))
368 b36429ab 2018-11-05 stsp 				return NULL;
369 8e291695 2020-01-04 stsp 			if (got_object_idset_contains(graph->node_ids,
370 ec242592 2022-04-22 thomas 			    &qid->id))
371 998ff57f 2018-11-18 stsp 				return NULL; /* parent already traversed */
372 b36429ab 2018-11-05 stsp 			return got_object_idset_add(graph->open_branches,
373 ec242592 2022-04-22 thomas 			    &qid->id, NULL);
374 bee6b577 2018-09-19 stsp 		}
375 0ed6ed4c 2018-06-13 stsp 	}
376 0ed6ed4c 2018-06-13 stsp 
377 dbdddfee 2021-06-23 naddy 	STAILQ_FOREACH(qid, &commit->parent_ids, entry) {
378 ec242592 2022-04-22 thomas 		if (got_object_idset_contains(graph->open_branches, &qid->id))
379 b36429ab 2018-11-05 stsp 			continue;
380 ec242592 2022-04-22 thomas 		if (got_object_idset_contains(graph->node_ids, &qid->id))
381 998ff57f 2018-11-18 stsp 			continue; /* parent already traversed */
382 ec242592 2022-04-22 thomas 		err = got_object_idset_add(graph->open_branches, &qid->id,
383 ec242592 2022-04-22 thomas 		    NULL);
384 b36429ab 2018-11-05 stsp 		if (err)
385 0ed6ed4c 2018-06-13 stsp 			return err;
386 0ed6ed4c 2018-06-13 stsp 	}
387 0ed6ed4c 2018-06-13 stsp 
388 b43fbaa0 2018-06-11 stsp 	return NULL;
389 de56b2d7 2020-01-04 stsp }
390 372ccdbb 2018-06-10 stsp 
391 de56b2d7 2020-01-04 stsp const struct got_error *
392 c4d7a9c4 2018-06-11 stsp got_commit_graph_open(struct got_commit_graph **graph,
393 3d509237 2020-01-04 stsp     const char *path, int first_parent_traversal)
394 3d509237 2020-01-04 stsp {
395 22220781 2020-01-04 stsp 	const struct got_error *err = NULL;
396 3ddcebf3 2020-01-04 stsp 
397 3ddcebf3 2020-01-04 stsp 	*graph = calloc(1, sizeof(**graph));
398 3d509237 2020-01-04 stsp 	if (*graph == NULL)
399 3ddcebf3 2020-01-04 stsp 		return got_error_from_errno("calloc");
400 88cdb9c6 2020-01-04 stsp 
401 88cdb9c6 2020-01-04 stsp 	TAILQ_INIT(&(*graph)->iter_list);
402 3ddcebf3 2020-01-04 stsp 
403 3ddcebf3 2020-01-04 stsp 	(*graph)->path = strdup(path);
404 3ddcebf3 2020-01-04 stsp 	if ((*graph)->path == NULL) {
405 3ddcebf3 2020-01-04 stsp 		err = got_error_from_errno("strdup");
406 22220781 2020-01-04 stsp 		goto done;
407 3ddcebf3 2020-01-04 stsp 	}
408 3ddcebf3 2020-01-04 stsp 
409 3ddcebf3 2020-01-04 stsp 	(*graph)->node_ids = got_object_idset_alloc();
410 3ddcebf3 2020-01-04 stsp 	if ((*graph)->node_ids == NULL) {
411 3ddcebf3 2020-01-04 stsp 		err = got_error_from_errno("got_object_idset_alloc");
412 22220781 2020-01-04 stsp 		goto done;
413 3ddcebf3 2020-01-04 stsp 	}
414 372ccdbb 2018-06-10 stsp 
415 3ddcebf3 2020-01-04 stsp 	(*graph)->open_branches = got_object_idset_alloc();
416 3ddcebf3 2020-01-04 stsp 	if ((*graph)->open_branches == NULL) {
417 3ddcebf3 2020-01-04 stsp 		err = got_error_from_errno("got_object_idset_alloc");
418 22220781 2020-01-04 stsp 		goto done;
419 3ddcebf3 2020-01-04 stsp 	}
420 3ddcebf3 2020-01-04 stsp 
421 0ed6ed4c 2018-06-13 stsp 	if (first_parent_traversal)
422 0ed6ed4c 2018-06-13 stsp 		(*graph)->flags |= GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL;
423 22220781 2020-01-04 stsp done:
424 22220781 2020-01-04 stsp 	if (err) {
425 22220781 2020-01-04 stsp 		got_commit_graph_close(*graph);
426 22220781 2020-01-04 stsp 		*graph = NULL;
427 22220781 2020-01-04 stsp 	}
428 22220781 2020-01-04 stsp 	return err;
429 372ccdbb 2018-06-10 stsp }
430 372ccdbb 2018-06-10 stsp 
431 32777563 2018-11-07 stsp struct add_branch_tip_arg {
432 b565f6f8 2018-07-23 stsp 	struct got_commit_graph_branch_tip *tips;
433 b565f6f8 2018-07-23 stsp 	int ntips;
434 32777563 2018-11-07 stsp 	struct got_repository *repo;
435 32777563 2018-11-07 stsp 	struct got_commit_graph *graph;
436 372ccdbb 2018-06-10 stsp };
437 372ccdbb 2018-06-10 stsp 
438 cb103d04 2018-11-07 stsp static const struct got_error *
439 32777563 2018-11-07 stsp add_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
440 372ccdbb 2018-06-10 stsp {
441 32777563 2018-11-07 stsp 	const struct got_error *err;
442 32777563 2018-11-07 stsp 	struct add_branch_tip_arg *a = arg;
443 32777563 2018-11-07 stsp 	struct got_commit_graph_node *new_node;
444 32777563 2018-11-07 stsp 	struct got_commit_object *commit;
445 32777563 2018-11-07 stsp 
446 32777563 2018-11-07 stsp 	err = got_object_open_as_commit(&commit, a->repo, commit_id);
447 32777563 2018-11-07 stsp 	if (err)
448 32777563 2018-11-07 stsp 		return err;
449 32777563 2018-11-07 stsp 
450 ca6e02ac 2020-01-07 stsp 	err = add_node(&new_node, a->graph, commit_id, a->repo);
451 07894e99 2022-09-04 thomas 	if (err) {
452 07894e99 2022-09-04 thomas 		got_object_commit_close(commit);
453 32777563 2018-11-07 stsp 		return err;
454 07894e99 2022-09-04 thomas 	}
455 32777563 2018-11-07 stsp 
456 07894e99 2022-09-04 thomas 	a->tips[a->ntips].commit_id = &new_node->id;
457 32777563 2018-11-07 stsp 	a->tips[a->ntips].commit = commit;
458 32777563 2018-11-07 stsp 	a->tips[a->ntips].new_node = new_node;
459 b565f6f8 2018-07-23 stsp 	a->ntips++;
460 32777563 2018-11-07 stsp 
461 cb103d04 2018-11-07 stsp 	return NULL;
462 372ccdbb 2018-06-10 stsp }
463 372ccdbb 2018-06-10 stsp 
464 1142eae9 2018-06-11 stsp static const struct got_error *
465 57eecd46 2020-01-04 stsp fetch_commits_from_open_branches(struct got_commit_graph *graph,
466 6fb7cd11 2019-08-22 stsp     struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
467 372ccdbb 2018-06-10 stsp {
468 372ccdbb 2018-06-10 stsp 	const struct got_error *err;
469 32777563 2018-11-07 stsp 	struct add_branch_tip_arg arg;
470 32777563 2018-11-07 stsp 	int i, ntips;
471 372ccdbb 2018-06-10 stsp 
472 32777563 2018-11-07 stsp 	ntips = got_object_idset_num_elements(graph->open_branches);
473 32777563 2018-11-07 stsp 	if (ntips == 0)
474 372ccdbb 2018-06-10 stsp 		return NULL;
475 372ccdbb 2018-06-10 stsp 
476 32777563 2018-11-07 stsp 	/* (Re-)allocate branch tips array if necessary. */
477 32777563 2018-11-07 stsp 	if (graph->ntips < ntips) {
478 b565f6f8 2018-07-23 stsp 		struct got_commit_graph_branch_tip *tips;
479 5e50c36a 2018-11-08 stsp 		tips = recallocarray(graph->tips, graph->ntips, ntips,
480 5e50c36a 2018-11-08 stsp 		    sizeof(*tips));
481 b565f6f8 2018-07-23 stsp 		if (tips == NULL)
482 638f9024 2019-05-13 stsp 			return got_error_from_errno("recallocarray");
483 b565f6f8 2018-07-23 stsp 		graph->tips = tips;
484 32777563 2018-11-07 stsp 		graph->ntips = ntips;
485 b565f6f8 2018-07-23 stsp 	}
486 b565f6f8 2018-07-23 stsp 	arg.tips = graph->tips;
487 32777563 2018-11-07 stsp 	arg.ntips = 0; /* add_branch_tip() will increment */
488 32777563 2018-11-07 stsp 	arg.repo = repo;
489 32777563 2018-11-07 stsp 	arg.graph = graph;
490 32777563 2018-11-07 stsp 	err = got_object_idset_for_each(graph->open_branches, add_branch_tip,
491 32777563 2018-11-07 stsp 	    &arg);
492 cb103d04 2018-11-07 stsp 	if (err)
493 32777563 2018-11-07 stsp 		goto done;
494 372ccdbb 2018-06-10 stsp 
495 b565f6f8 2018-07-23 stsp 	for (i = 0; i < arg.ntips; i++) {
496 372ccdbb 2018-06-10 stsp 		struct got_object_id *commit_id;
497 41fa1437 2018-11-05 stsp 		struct got_commit_object *commit;
498 32777563 2018-11-07 stsp 		struct got_commit_graph_node *new_node;
499 13a851c1 2020-01-04 stsp 		int changed;
500 372ccdbb 2018-06-10 stsp 
501 6fb7cd11 2019-08-22 stsp 		if (cancel_cb) {
502 6fb7cd11 2019-08-22 stsp 			err = (*cancel_cb)(cancel_arg);
503 6fb7cd11 2019-08-22 stsp 			if (err)
504 6fb7cd11 2019-08-22 stsp 				break;
505 6fb7cd11 2019-08-22 stsp 		}
506 6fb7cd11 2019-08-22 stsp 
507 32777563 2018-11-07 stsp 		commit_id = arg.tips[i].commit_id;
508 32777563 2018-11-07 stsp 		commit = arg.tips[i].commit;
509 32777563 2018-11-07 stsp 		new_node = arg.tips[i].new_node;
510 de56b2d7 2020-01-04 stsp 
511 13a851c1 2020-01-04 stsp 		err = detect_changed_path(&changed, commit, commit_id,
512 13a851c1 2020-01-04 stsp 		    graph->path, repo);
513 13a851c1 2020-01-04 stsp 		if (err) {
514 13a851c1 2020-01-04 stsp 			if (err->code != GOT_ERR_NO_OBJ)
515 13a851c1 2020-01-04 stsp 				break;
516 13a851c1 2020-01-04 stsp 			/*
517 13a851c1 2020-01-04 stsp 			 * History of the path stops here on the current
518 13a851c1 2020-01-04 stsp 			 * branch. Keep going on other branches.
519 13a851c1 2020-01-04 stsp 			 */
520 32c85d2c 2020-01-06 stsp 			err = close_branch(graph, commit_id);
521 32c85d2c 2020-01-06 stsp 			if (err)
522 32c85d2c 2020-01-06 stsp 				break;
523 ec1904dc 2020-01-04 stsp 			continue;
524 13a851c1 2020-01-04 stsp 		}
525 f3933be6 2022-09-04 thomas 		if (changed) {
526 ca6e02ac 2020-01-07 stsp 			add_node_to_iter_list(graph, new_node,
527 ca6e02ac 2020-01-07 stsp 			    got_object_commit_get_committer_time(commit));
528 f3933be6 2022-09-04 thomas 			arg.tips[i].new_node = NULL;
529 f3933be6 2022-09-04 thomas 		}
530 14159a7b 2020-01-04 stsp 		err = advance_branch(graph, commit_id, commit, repo);
531 cb352812 2018-07-22 stsp 		if (err)
532 cb352812 2018-07-22 stsp 			break;
533 372ccdbb 2018-06-10 stsp 	}
534 32777563 2018-11-07 stsp done:
535 f3933be6 2022-09-04 thomas 	for (i = 0; i < arg.ntips; i++) {
536 32777563 2018-11-07 stsp 		got_object_commit_close(arg.tips[i].commit);
537 f3933be6 2022-09-04 thomas 		free(arg.tips[i].new_node);
538 f3933be6 2022-09-04 thomas 	}
539 372ccdbb 2018-06-10 stsp 	return err;
540 372ccdbb 2018-06-10 stsp }
541 372ccdbb 2018-06-10 stsp 
542 372ccdbb 2018-06-10 stsp void
543 372ccdbb 2018-06-10 stsp got_commit_graph_close(struct got_commit_graph *graph)
544 372ccdbb 2018-06-10 stsp {
545 599785e8 2022-09-04 thomas 	struct got_commit_graph_node *node;
546 599785e8 2022-09-04 thomas 
547 599785e8 2022-09-04 thomas 	while ((node = TAILQ_FIRST(&graph->iter_list))) {
548 599785e8 2022-09-04 thomas 		TAILQ_REMOVE(&graph->iter_list, node, entry);
549 599785e8 2022-09-04 thomas 		free(node);
550 599785e8 2022-09-04 thomas 	}
551 599785e8 2022-09-04 thomas 
552 22220781 2020-01-04 stsp 	if (graph->open_branches)
553 22220781 2020-01-04 stsp 		got_object_idset_free(graph->open_branches);
554 22220781 2020-01-04 stsp 	if (graph->node_ids)
555 22220781 2020-01-04 stsp 		got_object_idset_free(graph->node_ids);
556 b565f6f8 2018-07-23 stsp 	free(graph->tips);
557 31cedeaf 2018-09-15 stsp 	free(graph->path);
558 372ccdbb 2018-06-10 stsp 	free(graph);
559 372ccdbb 2018-06-10 stsp }
560 372ccdbb 2018-06-10 stsp 
561 372ccdbb 2018-06-10 stsp const struct got_error *
562 372ccdbb 2018-06-10 stsp got_commit_graph_iter_start(struct got_commit_graph *graph,
563 6fb7cd11 2019-08-22 stsp     struct got_object_id *id, struct got_repository *repo,
564 6fb7cd11 2019-08-22 stsp     got_cancel_cb cancel_cb, void *cancel_arg)
565 372ccdbb 2018-06-10 stsp {
566 31cedeaf 2018-09-15 stsp 	const struct got_error *err = NULL;
567 372ccdbb 2018-06-10 stsp 
568 3d509237 2020-01-04 stsp 	if (!TAILQ_EMPTY(&graph->iter_list))
569 3d509237 2020-01-04 stsp 		return got_error(GOT_ERR_ITER_BUSY);
570 31cedeaf 2018-09-15 stsp 
571 3ff3126d 2020-01-04 stsp 	err = got_object_idset_add(graph->open_branches, id, NULL);
572 3d509237 2020-01-04 stsp 	if (err)
573 7e33c8c5 2020-01-04 stsp 		return err;
574 3d509237 2020-01-04 stsp 
575 3ff3126d 2020-01-04 stsp 	/* Locate first commit which changed graph->path. */
576 94489f7d 2020-01-04 stsp 	while (TAILQ_EMPTY(&graph->iter_list) &&
577 3ff3126d 2020-01-04 stsp 	    got_object_idset_num_elements(graph->open_branches) > 0) {
578 3ff3126d 2020-01-04 stsp 		err = fetch_commits_from_open_branches(graph, repo,
579 3ff3126d 2020-01-04 stsp 		    cancel_cb, cancel_arg);
580 3ff3126d 2020-01-04 stsp 		if (err)
581 7e33c8c5 2020-01-04 stsp 			return err;
582 5175b31a 2020-01-04 stsp 	}
583 5175b31a 2020-01-04 stsp 
584 94489f7d 2020-01-04 stsp 	if (TAILQ_EMPTY(&graph->iter_list)) {
585 5175b31a 2020-01-04 stsp 		const char *path;
586 5175b31a 2020-01-04 stsp 		if (got_path_is_root_dir(graph->path))
587 5175b31a 2020-01-04 stsp 			return got_error_no_obj(id);
588 5175b31a 2020-01-04 stsp 		path = graph->path;
589 5175b31a 2020-01-04 stsp 		while (path[0] == '/')
590 5175b31a 2020-01-04 stsp 			path++;
591 5175b31a 2020-01-04 stsp 		return got_error_path(path, GOT_ERR_NO_TREE_ENTRY);
592 31cedeaf 2018-09-15 stsp 	}
593 7e33c8c5 2020-01-04 stsp 
594 7e33c8c5 2020-01-04 stsp 	return NULL;
595 372ccdbb 2018-06-10 stsp }
596 372ccdbb 2018-06-10 stsp 
597 372ccdbb 2018-06-10 stsp const struct got_error *
598 7210b715 2022-09-11 thomas got_commit_graph_iter_next(struct got_object_id *id,
599 ee780d5c 2020-01-04 stsp     struct got_commit_graph *graph, struct got_repository *repo,
600 ee780d5c 2020-01-04 stsp     got_cancel_cb cancel_cb, void *cancel_arg)
601 372ccdbb 2018-06-10 stsp {
602 ee780d5c 2020-01-04 stsp 	const struct got_error *err = NULL;
603 94489f7d 2020-01-04 stsp 	struct got_commit_graph_node *node;
604 372ccdbb 2018-06-10 stsp 
605 df8cd9c6 2020-01-05 stsp 	node = TAILQ_FIRST(&graph->iter_list);
606 df8cd9c6 2020-01-05 stsp 	if (node == NULL) {
607 2c7f8870 2018-09-19 stsp 		/* We are done iterating, or iteration was not started. */
608 9ba79e04 2018-06-11 stsp 		return got_error(GOT_ERR_ITER_COMPLETED);
609 9ba79e04 2018-06-11 stsp 	}
610 9ba79e04 2018-06-11 stsp 
611 94489f7d 2020-01-04 stsp 	while (TAILQ_NEXT(node, entry) == NULL &&
612 ee780d5c 2020-01-04 stsp 	    got_object_idset_num_elements(graph->open_branches) > 0) {
613 57eecd46 2020-01-04 stsp 		err = fetch_commits_from_open_branches(graph, repo,
614 57eecd46 2020-01-04 stsp 		    cancel_cb, cancel_arg);
615 ee780d5c 2020-01-04 stsp 		if (err)
616 ee780d5c 2020-01-04 stsp 			return err;
617 ee780d5c 2020-01-04 stsp 	}
618 372ccdbb 2018-06-10 stsp 
619 7210b715 2022-09-11 thomas 	memcpy(id, &node->id, sizeof(*id));
620 d68b9737 2022-09-05 thomas 
621 94489f7d 2020-01-04 stsp 	TAILQ_REMOVE(&graph->iter_list, node, entry);
622 d68b9737 2022-09-05 thomas 	free(node);
623 372ccdbb 2018-06-10 stsp 	return NULL;
624 7210b715 2022-09-11 thomas }
625 7210b715 2022-09-11 thomas 
626 7210b715 2022-09-11 thomas static const struct got_error *
627 7210b715 2022-09-11 thomas find_yca_add_id(struct got_object_id **yca_id, struct got_commit_graph *graph,
628 7210b715 2022-09-11 thomas     struct got_object_idset *commit_ids, struct got_repository *repo,
629 7210b715 2022-09-11 thomas     got_cancel_cb cancel_cb, void *cancel_arg)
630 7210b715 2022-09-11 thomas {
631 7210b715 2022-09-11 thomas 	const struct got_error *err = NULL;
632 7210b715 2022-09-11 thomas 	struct got_object_id id;
633 7210b715 2022-09-11 thomas 
634 7210b715 2022-09-11 thomas 	err = got_commit_graph_iter_next(&id, graph, repo, cancel_cb,
635 7210b715 2022-09-11 thomas 	    cancel_arg);
636 7210b715 2022-09-11 thomas 	if (err)
637 7210b715 2022-09-11 thomas 		return err;
638 7210b715 2022-09-11 thomas 
639 7210b715 2022-09-11 thomas 	if (got_object_idset_contains(commit_ids, &id)) {
640 7210b715 2022-09-11 thomas 		*yca_id = got_object_id_dup(&id);
641 7210b715 2022-09-11 thomas 		if (*yca_id == NULL)
642 7210b715 2022-09-11 thomas 			err = got_error_from_errno("got_object_id_dup");
643 7210b715 2022-09-11 thomas 		return err;
644 7210b715 2022-09-11 thomas 	}
645 7210b715 2022-09-11 thomas 
646 7210b715 2022-09-11 thomas 	return got_object_idset_add(commit_ids, &id, NULL);
647 372ccdbb 2018-06-10 stsp }
648 a9833bc9 2019-05-13 stsp 
649 a4c8ed77 2023-05-25 thomas /*
650 a4c8ed77 2023-05-25 thomas  * Sets *yca_id to the youngest common ancestor of commit_id and
651 a4c8ed77 2023-05-25 thomas  * commit_id2. Returns got_error(GOT_ERR_ANCESTRY) if they have no
652 a4c8ed77 2023-05-25 thomas  * common ancestors.
653 a4c8ed77 2023-05-25 thomas  *
654 a4c8ed77 2023-05-25 thomas  * If first_parent_traversal is nonzero, only linear history is considered.
655 a4c8ed77 2023-05-25 thomas  */
656 a9833bc9 2019-05-13 stsp const struct got_error *
657 a9833bc9 2019-05-13 stsp got_commit_graph_find_youngest_common_ancestor(struct got_object_id **yca_id,
658 a9833bc9 2019-05-13 stsp     struct got_object_id *commit_id, struct got_object_id *commit_id2,
659 768705e3 2021-09-27 thomas     int first_parent_traversal,
660 6fb7cd11 2019-08-22 stsp     struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
661 a9833bc9 2019-05-13 stsp {
662 a9833bc9 2019-05-13 stsp 	const struct got_error *err = NULL;
663 a9833bc9 2019-05-13 stsp 	struct got_commit_graph *graph = NULL, *graph2 = NULL;
664 a9833bc9 2019-05-13 stsp 	int completed = 0, completed2 = 0;
665 a9833bc9 2019-05-13 stsp 	struct got_object_idset *commit_ids;
666 a9833bc9 2019-05-13 stsp 
667 a9833bc9 2019-05-13 stsp 	*yca_id = NULL;
668 a9833bc9 2019-05-13 stsp 
669 a9833bc9 2019-05-13 stsp 	commit_ids = got_object_idset_alloc();
670 a9833bc9 2019-05-13 stsp 	if (commit_ids == NULL)
671 638f9024 2019-05-13 stsp 		return got_error_from_errno("got_object_idset_alloc");
672 a9833bc9 2019-05-13 stsp 
673 768705e3 2021-09-27 thomas 	err = got_commit_graph_open(&graph, "/", first_parent_traversal);
674 a9833bc9 2019-05-13 stsp 	if (err)
675 a9833bc9 2019-05-13 stsp 		goto done;
676 a9833bc9 2019-05-13 stsp 
677 768705e3 2021-09-27 thomas 	err = got_commit_graph_open(&graph2, "/", first_parent_traversal);
678 a9833bc9 2019-05-13 stsp 	if (err)
679 a9833bc9 2019-05-13 stsp 		goto done;
680 a9833bc9 2019-05-13 stsp 
681 6fb7cd11 2019-08-22 stsp 	err = got_commit_graph_iter_start(graph, commit_id, repo,
682 6fb7cd11 2019-08-22 stsp 	    cancel_cb, cancel_arg);
683 a9833bc9 2019-05-13 stsp 	if (err)
684 a9833bc9 2019-05-13 stsp 		goto done;
685 a9833bc9 2019-05-13 stsp 
686 6fb7cd11 2019-08-22 stsp 	err = got_commit_graph_iter_start(graph2, commit_id2, repo,
687 6fb7cd11 2019-08-22 stsp 	    cancel_cb, cancel_arg);
688 a9833bc9 2019-05-13 stsp 	if (err)
689 a9833bc9 2019-05-13 stsp 		goto done;
690 a9833bc9 2019-05-13 stsp 
691 a9833bc9 2019-05-13 stsp 	for (;;) {
692 6fb7cd11 2019-08-22 stsp 		if (cancel_cb) {
693 6fb7cd11 2019-08-22 stsp 			err = (*cancel_cb)(cancel_arg);
694 6fb7cd11 2019-08-22 stsp 			if (err)
695 6fb7cd11 2019-08-22 stsp 				break;
696 6fb7cd11 2019-08-22 stsp 		}
697 6fb7cd11 2019-08-22 stsp 
698 a9833bc9 2019-05-13 stsp 		if (!completed) {
699 7210b715 2022-09-11 thomas 			err = find_yca_add_id(yca_id, graph, commit_ids, repo,
700 ee780d5c 2020-01-04 stsp 			    cancel_cb, cancel_arg);
701 a9833bc9 2019-05-13 stsp 			if (err) {
702 ee780d5c 2020-01-04 stsp 				if (err->code != GOT_ERR_ITER_COMPLETED)
703 a9833bc9 2019-05-13 stsp 					break;
704 ee780d5c 2020-01-04 stsp 				err = NULL;
705 ee780d5c 2020-01-04 stsp 				completed = 1;
706 a9833bc9 2019-05-13 stsp 			}
707 7210b715 2022-09-11 thomas 			if (*yca_id)
708 7210b715 2022-09-11 thomas 				break;
709 a9833bc9 2019-05-13 stsp 		}
710 a9833bc9 2019-05-13 stsp 
711 a9833bc9 2019-05-13 stsp 		if (!completed2) {
712 7210b715 2022-09-11 thomas 			err = find_yca_add_id(yca_id, graph2, commit_ids, repo,
713 ee780d5c 2020-01-04 stsp 			    cancel_cb, cancel_arg);
714 a9833bc9 2019-05-13 stsp 			if (err) {
715 ee780d5c 2020-01-04 stsp 				if (err->code != GOT_ERR_ITER_COMPLETED)
716 a9833bc9 2019-05-13 stsp 					break;
717 ee780d5c 2020-01-04 stsp 				err = NULL;
718 ee780d5c 2020-01-04 stsp 				completed2 = 1;
719 a9833bc9 2019-05-13 stsp 			}
720 7210b715 2022-09-11 thomas 			if (*yca_id)
721 a9833bc9 2019-05-13 stsp 				break;
722 a9833bc9 2019-05-13 stsp 		}
723 a9833bc9 2019-05-13 stsp 
724 a9833bc9 2019-05-13 stsp 		if (completed && completed2) {
725 a9833bc9 2019-05-13 stsp 			err = got_error(GOT_ERR_ANCESTRY);
726 a9833bc9 2019-05-13 stsp 			break;
727 a9833bc9 2019-05-13 stsp 		}
728 a9833bc9 2019-05-13 stsp 	}
729 a9833bc9 2019-05-13 stsp done:
730 a9833bc9 2019-05-13 stsp 	got_object_idset_free(commit_ids);
731 a9833bc9 2019-05-13 stsp 	if (graph)
732 a9833bc9 2019-05-13 stsp 		got_commit_graph_close(graph);
733 a9833bc9 2019-05-13 stsp 	if (graph2)
734 a9833bc9 2019-05-13 stsp 		got_commit_graph_close(graph2);
735 a9833bc9 2019-05-13 stsp 	return err;
736 a9833bc9 2019-05-13 stsp }