Blame

Date:
Message:
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().
Actions:
History | Blob | Raw File
  1 fd7552d2 2023-07-17 mark /*

  2 fd7552d2 2023-07-17 mark  * Copyright (c) 2023 Mark Jamsek <mark@jamsek.dev>

  3 fd7552d2 2023-07-17 mark  *

  4 fd7552d2 2023-07-17 mark  * Permission to use, copy, modify, and distribute this software for any

  5 fd7552d2 2023-07-17 mark  * purpose with or without fee is hereby granted, provided that the above

  6 fd7552d2 2023-07-17 mark  * copyright notice and this permission notice appear in all copies.

  7 fd7552d2 2023-07-17 mark  *

  8 fd7552d2 2023-07-17 mark  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES

  9 fd7552d2 2023-07-17 mark  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF

 10 fd7552d2 2023-07-17 mark  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR

 11 fd7552d2 2023-07-17 mark  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES

 12 fd7552d2 2023-07-17 mark  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN

 13 fd7552d2 2023-07-17 mark  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF

 14 fd7552d2 2023-07-17 mark  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

 15 fd7552d2 2023-07-17 mark  */

 16 fd7552d2 2023-07-17 mark 

 17 fd7552d2 2023-07-17 mark #include <sys/queue.h>

 18 fd7552d2 2023-07-17 mark 

 19 fd7552d2 2023-07-17 mark #include <ctype.h>

 20 fd7552d2 2023-07-17 mark #include <limits.h>

 21 fd7552d2 2023-07-17 mark #include <stddef.h>

 22 fd7552d2 2023-07-17 mark #include <stdio.h>

 23 fd7552d2 2023-07-17 mark #include <stdlib.h>

 24 fd7552d2 2023-07-17 mark #include <string.h>

 25 fd7552d2 2023-07-17 mark #include <sha1.h>

 26 fd7552d2 2023-07-17 mark #include <sha2.h>

 27 fd7552d2 2023-07-17 mark 

 28 fd7552d2 2023-07-17 mark #include "got_reference.h"

 29 fd7552d2 2023-07-17 mark #include "got_error.h"

 30 fd7552d2 2023-07-17 mark #include "got_object.h"

 31 fd7552d2 2023-07-17 mark #include "got_repository.h"

 32 fd7552d2 2023-07-17 mark #include "got_cancel.h"

 33 fd7552d2 2023-07-17 mark #include "got_worktree.h"

 34 fd7552d2 2023-07-17 mark #include "got_commit_graph.h"

 35 fd7552d2 2023-07-17 mark #include "got_keyword.h"

 36 fd7552d2 2023-07-17 mark 

 37 fd7552d2 2023-07-17 mark struct keyword_mod {

 38 fd7552d2 2023-07-17 mark 	char		*kw;

 39 fd7552d2 2023-07-17 mark 	uint64_t	 n;

 40 fd7552d2 2023-07-17 mark 	uint8_t		 sym;

 41 fd7552d2 2023-07-17 mark 	uint8_t		 iskeyword;

 42 fd7552d2 2023-07-17 mark 	uint8_t		 ismodified;

 43 fd7552d2 2023-07-17 mark };

 44 fd7552d2 2023-07-17 mark 

 45 fd7552d2 2023-07-17 mark #define GOT_KEYWORD_DESCENDANT	'+'

 46 fd7552d2 2023-07-17 mark #define GOT_KEYWORD_ANCESTOR	'-'

 47 fd7552d2 2023-07-17 mark 

 48 fd7552d2 2023-07-17 mark static const struct got_error *

 49 fd7552d2 2023-07-17 mark parse_keyword(struct keyword_mod *kwm, const char *keyword)

 50 fd7552d2 2023-07-17 mark {

 51 fd7552d2 2023-07-17 mark 	const char	*kw;

 52 fd7552d2 2023-07-17 mark 	char		*p;

 53 fd7552d2 2023-07-17 mark 

 54 fd7552d2 2023-07-17 mark 	if (keyword == NULL)

 55 fd7552d2 2023-07-17 mark 		return NULL;

 56 fd7552d2 2023-07-17 mark 

 57 fd7552d2 2023-07-17 mark 	/* check if it is a (modified) keyword or modified reference */

 58 fd7552d2 2023-07-17 mark 	if (*keyword == ':') {

 59 fd7552d2 2023-07-17 mark 		kwm->iskeyword = 1;

 60 fd7552d2 2023-07-17 mark 		kw = keyword + 1;

 61 fd7552d2 2023-07-17 mark 	} else

 62 fd7552d2 2023-07-17 mark 		kw = keyword;

 63 fd7552d2 2023-07-17 mark 

 64 fd7552d2 2023-07-17 mark 	kwm->kw = strdup(kw);

 65 fd7552d2 2023-07-17 mark 	if (kwm->kw == NULL)

 66 fd7552d2 2023-07-17 mark 		return got_error_from_errno("strdup");

 67 fd7552d2 2023-07-17 mark 

 68 fd7552d2 2023-07-17 mark 	p = strchr(kwm->kw, ':');

 69 fd7552d2 2023-07-17 mark 

 70 fd7552d2 2023-07-17 mark 	if (p != NULL) {

 71 fd7552d2 2023-07-17 mark 		*p = '\0';

 72 fd7552d2 2023-07-17 mark 		++p;

 73 fd7552d2 2023-07-17 mark 		if (*p != GOT_KEYWORD_DESCENDANT && *p != GOT_KEYWORD_ANCESTOR)

 74 fd7552d2 2023-07-17 mark 			return got_error_fmt(GOT_ERR_BAD_KEYWORD,

 75 fd7552d2 2023-07-17 mark 			    "'%s'", keyword);

 76 fd7552d2 2023-07-17 mark 

 77 fd7552d2 2023-07-17 mark 		kwm->ismodified = 1;

 78 fd7552d2 2023-07-17 mark 		kwm->sym = *p;

 79 fd7552d2 2023-07-17 mark 		++p;

 80 fd7552d2 2023-07-17 mark 

 81 fd7552d2 2023-07-17 mark 		if (*p) {

 82 fd7552d2 2023-07-17 mark 			const char	*errstr;

 83 fd7552d2 2023-07-17 mark 			long long	 n;

 84 fd7552d2 2023-07-17 mark 

 85 fd7552d2 2023-07-17 mark 			n = strtonum(p, 0, LLONG_MAX, &errstr);

 86 fd7552d2 2023-07-17 mark 			if (errstr != NULL)

 87 fd7552d2 2023-07-17 mark 				return got_error_fmt(GOT_ERR_BAD_KEYWORD,

 88 fd7552d2 2023-07-17 mark 				    "'%s'", keyword);

 89 fd7552d2 2023-07-17 mark 

 90 fd7552d2 2023-07-17 mark 			kwm->n = n;

 91 fd7552d2 2023-07-17 mark 		} else

 92 fd7552d2 2023-07-17 mark 			kwm->n = 1;	/* :(+/-) == :(+/-)1 */

 93 fd7552d2 2023-07-17 mark 	}

 94 fd7552d2 2023-07-17 mark 

 95 fd7552d2 2023-07-17 mark 	return NULL;

 96 fd7552d2 2023-07-17 mark }

 97 fd7552d2 2023-07-17 mark 

 98 fd7552d2 2023-07-17 mark const struct got_error *

 99 fd7552d2 2023-07-17 mark got_keyword_to_idstr(char **ret, const char *keyword,

100 fd7552d2 2023-07-17 mark     struct got_repository *repo, struct got_worktree *wt)

101 fd7552d2 2023-07-17 mark {

102 fd7552d2 2023-07-17 mark 	const struct got_error		*err = NULL;

103 fd7552d2 2023-07-17 mark 	struct got_commit_graph		*graph = NULL;

104 fd7552d2 2023-07-17 mark 	struct got_object_id		*head_id = NULL, *kwid = NULL;

105 fd7552d2 2023-07-17 mark 	struct got_object_id		 iter_id;

106 fd7552d2 2023-07-17 mark 	struct got_reflist_head		 refs;

107 fd7552d2 2023-07-17 mark 	struct got_object_id_queue	 commits;

108 fd7552d2 2023-07-17 mark 	struct got_object_qid		*qid;

109 fd7552d2 2023-07-17 mark 	struct keyword_mod		 kwm;

110 fd7552d2 2023-07-17 mark 	const char			*kw = NULL;

111 fd7552d2 2023-07-17 mark 	char				*kwid_str = NULL;

112 fd7552d2 2023-07-17 mark 	uint64_t			 n = 0;

113 fd7552d2 2023-07-17 mark 

114 fd7552d2 2023-07-17 mark 	*ret = NULL;

115 fd7552d2 2023-07-17 mark 	TAILQ_INIT(&refs);

116 fd7552d2 2023-07-17 mark 	STAILQ_INIT(&commits);

117 fd7552d2 2023-07-17 mark 	memset(&kwm, 0, sizeof(kwm));

118 fd7552d2 2023-07-17 mark 

119 fd7552d2 2023-07-17 mark 	err = parse_keyword(&kwm, keyword);

120 fd7552d2 2023-07-17 mark 	if (err != NULL)

121 fd7552d2 2023-07-17 mark 		goto done;

122 fd7552d2 2023-07-17 mark 

123 fd7552d2 2023-07-17 mark 	kw = kwm.kw;

124 fd7552d2 2023-07-17 mark 

125 fd7552d2 2023-07-17 mark 	if (kwm.iskeyword) {

126 fd7552d2 2023-07-17 mark 		if (strcmp(kw, GOT_KEYWORD_BASE) == 0) {

127 fd7552d2 2023-07-17 mark 			if (wt == NULL) {

128 fd7552d2 2023-07-17 mark 				err = got_error_msg(GOT_ERR_NOT_WORKTREE,

129 fd7552d2 2023-07-17 mark 				    "'-c :base' requires work tree");

130 fd7552d2 2023-07-17 mark 				goto done;

131 fd7552d2 2023-07-17 mark 			}

132 fd7552d2 2023-07-17 mark 

133 fd7552d2 2023-07-17 mark 			err = got_object_id_str(&kwid_str,

134 fd7552d2 2023-07-17 mark 			    got_worktree_get_base_commit_id(wt));

135 fd7552d2 2023-07-17 mark 			if (err != NULL)

136 fd7552d2 2023-07-17 mark 				goto done;

137 fd7552d2 2023-07-17 mark 		} else if (strcmp(kw, GOT_KEYWORD_HEAD) == 0) {

138 fd7552d2 2023-07-17 mark 			struct got_reference *head_ref;

139 fd7552d2 2023-07-17 mark 

140 fd7552d2 2023-07-17 mark 			err = got_ref_open(&head_ref, repo, wt != NULL ?

141 fd7552d2 2023-07-17 mark 			    got_worktree_get_head_ref_name(wt) :

142 fd7552d2 2023-07-17 mark 			    GOT_REF_HEAD, 0);

143 fd7552d2 2023-07-17 mark 			if (err != NULL)

144 fd7552d2 2023-07-17 mark 				goto done;

145 fd7552d2 2023-07-17 mark 

146 fd7552d2 2023-07-17 mark 			kwid_str = got_ref_to_str(head_ref);

147 fd7552d2 2023-07-17 mark 			got_ref_close(head_ref);

148 fd7552d2 2023-07-17 mark 			if (kwid_str == NULL) {

149 fd7552d2 2023-07-17 mark 				err = got_error_from_errno("got_ref_to_str");

150 fd7552d2 2023-07-17 mark 				goto done;

151 fd7552d2 2023-07-17 mark 			}

152 fd7552d2 2023-07-17 mark 		} else {

153 fd7552d2 2023-07-17 mark 			err = got_error_fmt(GOT_ERR_BAD_KEYWORD, "'%s'", kw);

154 fd7552d2 2023-07-17 mark 			goto done;

155 fd7552d2 2023-07-17 mark 		}

156 fd7552d2 2023-07-17 mark 	} else if (kwm.ismodified) {

157 fd7552d2 2023-07-17 mark 		/* reference:[(+|-)[N]] */

158 fd7552d2 2023-07-17 mark 		kwid_str = strdup(kw);

159 fd7552d2 2023-07-17 mark 		if (kwid_str == NULL) {

160 fd7552d2 2023-07-17 mark 			err = got_error_from_errno("strdup");

161 fd7552d2 2023-07-17 mark 			goto done;

162 fd7552d2 2023-07-17 mark 		}

163 fd7552d2 2023-07-17 mark 	} else

164 fd7552d2 2023-07-17 mark 		goto done;

165 fd7552d2 2023-07-17 mark 

166 fd7552d2 2023-07-17 mark 	if (kwm.n == 0)

167 fd7552d2 2023-07-17 mark 		goto done;	/* unmodified keyword */

168 fd7552d2 2023-07-17 mark 

169 fd7552d2 2023-07-17 mark 	err = got_ref_list(&refs, repo, NULL, got_ref_cmp_by_name, NULL);

170 fd7552d2 2023-07-17 mark 	if (err)

171 fd7552d2 2023-07-17 mark 		goto done;

172 fd7552d2 2023-07-17 mark 

173 fd7552d2 2023-07-17 mark 	err = got_repo_match_object_id(&kwid, NULL, kwid_str,

174 fd7552d2 2023-07-17 mark 	    GOT_OBJ_TYPE_COMMIT, &refs, repo);

175 fd7552d2 2023-07-17 mark 	if (err != NULL)

176 fd7552d2 2023-07-17 mark 		goto done;

177 fd7552d2 2023-07-17 mark 

178 fd7552d2 2023-07-17 mark 	/*

179 fd7552d2 2023-07-17 mark 	 * If looking for a descendant, we need to iterate from

180 fd7552d2 2023-07-17 mark 	 * HEAD so grab its id now if it's not already in kwid.

181 fd7552d2 2023-07-17 mark 	 */

182 fd7552d2 2023-07-17 mark 	if (kwm.sym == GOT_KEYWORD_DESCENDANT && kw != NULL &&

183 fd7552d2 2023-07-17 mark 	    strcmp(kw, GOT_KEYWORD_HEAD) != 0) {

184 fd7552d2 2023-07-17 mark 		struct got_reference *head_ref;

185 fd7552d2 2023-07-17 mark 

186 fd7552d2 2023-07-17 mark 		err = got_ref_open(&head_ref, repo, wt != NULL ?

187 fd7552d2 2023-07-17 mark 		    got_worktree_get_head_ref_name(wt) : GOT_REF_HEAD, 0);

188 fd7552d2 2023-07-17 mark 		if (err != NULL)

189 fd7552d2 2023-07-17 mark 			goto done;

190 fd7552d2 2023-07-17 mark 		err = got_ref_resolve(&head_id, repo, head_ref);

191 fd7552d2 2023-07-17 mark 		got_ref_close(head_ref);

192 fd7552d2 2023-07-17 mark 		if (err != NULL)

193 fd7552d2 2023-07-17 mark 			goto done;

194 fd7552d2 2023-07-17 mark 	}

195 fd7552d2 2023-07-17 mark 

196 fd7552d2 2023-07-17 mark 	err = got_commit_graph_open(&graph, "/", 1);

197 fd7552d2 2023-07-17 mark 	if (err)

198 fd7552d2 2023-07-17 mark 		goto done;

199 fd7552d2 2023-07-17 mark 

200 98297eed 2024-03-27 stsp 	err = got_commit_graph_bfsort(graph,

201 fd7552d2 2023-07-17 mark 	    head_id != NULL ? head_id : kwid, repo, NULL, NULL);

202 fd7552d2 2023-07-17 mark 	if (err)

203 fd7552d2 2023-07-17 mark 		goto done;

204 fd7552d2 2023-07-17 mark 

205 fd7552d2 2023-07-17 mark 	while (n <= kwm.n) {

206 fd7552d2 2023-07-17 mark 		err = got_commit_graph_iter_next(&iter_id, graph, repo,

207 fd7552d2 2023-07-17 mark 		    NULL, NULL);

208 fd7552d2 2023-07-17 mark 		if (err) {

209 fd7552d2 2023-07-17 mark 			if (err->code == GOT_ERR_ITER_COMPLETED)

210 fd7552d2 2023-07-17 mark 				err = NULL;

211 fd7552d2 2023-07-17 mark 			break;

212 fd7552d2 2023-07-17 mark 		}

213 fd7552d2 2023-07-17 mark 

214 fd7552d2 2023-07-17 mark 		if (kwm.sym == GOT_KEYWORD_DESCENDANT) {

215 fd7552d2 2023-07-17 mark 			/*

216 fd7552d2 2023-07-17 mark 			 * We want the Nth generation descendant of KEYWORD,

217 fd7552d2 2023-07-17 mark 			 * so queue all commits from HEAD to KEYWORD then we

218 fd7552d2 2023-07-17 mark 			 * can walk from KEYWORD to its Nth gen descendent.

219 fd7552d2 2023-07-17 mark 			 */

220 fd7552d2 2023-07-17 mark 			err = got_object_qid_alloc(&qid, &iter_id);

221 fd7552d2 2023-07-17 mark 			if (err)

222 fd7552d2 2023-07-17 mark 				goto done;

223 fd7552d2 2023-07-17 mark 			STAILQ_INSERT_HEAD(&commits, qid, entry);

224 fd7552d2 2023-07-17 mark 

225 fd7552d2 2023-07-17 mark 			if (got_object_id_cmp(&iter_id, kwid) == 0)

226 fd7552d2 2023-07-17 mark 				break;

227 fd7552d2 2023-07-17 mark 			continue;

228 fd7552d2 2023-07-17 mark 		}

229 fd7552d2 2023-07-17 mark 		++n;

230 fd7552d2 2023-07-17 mark 	}

231 fd7552d2 2023-07-17 mark 

232 fd7552d2 2023-07-17 mark 	if (kwm.sym == GOT_KEYWORD_DESCENDANT) {

233 fd7552d2 2023-07-17 mark 		n = 0;

234 fd7552d2 2023-07-17 mark 

235 fd7552d2 2023-07-17 mark 		STAILQ_FOREACH(qid, &commits, entry) {

236 fd7552d2 2023-07-17 mark 			if (qid == STAILQ_LAST(&commits, got_object_qid, entry)

237 fd7552d2 2023-07-17 mark 			    || n == kwm.n)

238 fd7552d2 2023-07-17 mark 				break;

239 fd7552d2 2023-07-17 mark 			++n;

240 fd7552d2 2023-07-17 mark 		}

241 fd7552d2 2023-07-17 mark 

242 fd7552d2 2023-07-17 mark 		memcpy(&iter_id, &qid->id, sizeof(iter_id));

243 fd7552d2 2023-07-17 mark 	}

244 fd7552d2 2023-07-17 mark 

245 fd7552d2 2023-07-17 mark 	free(kwid_str);

246 fd7552d2 2023-07-17 mark 	err = got_object_id_str(&kwid_str, &iter_id);

247 fd7552d2 2023-07-17 mark 

248 fd7552d2 2023-07-17 mark done:

249 fd7552d2 2023-07-17 mark 	free(kwid);

250 fd7552d2 2023-07-17 mark 	free(kwm.kw);

251 fd7552d2 2023-07-17 mark 	free(head_id);

252 fd7552d2 2023-07-17 mark 	got_ref_list_free(&refs);

253 fd7552d2 2023-07-17 mark 	got_object_id_queue_free(&commits);

254 fd7552d2 2023-07-17 mark 	if (graph != NULL)

255 fd7552d2 2023-07-17 mark 		got_commit_graph_close(graph);

256 fd7552d2 2023-07-17 mark 

257 fd7552d2 2023-07-17 mark 	if (err != NULL) {

258 fd7552d2 2023-07-17 mark 		free(kwid_str);

259 fd7552d2 2023-07-17 mark 		return err;

260 fd7552d2 2023-07-17 mark 	}

261 fd7552d2 2023-07-17 mark 

262 fd7552d2 2023-07-17 mark 	*ret = kwid_str;

263 fd7552d2 2023-07-17 mark 	return NULL;

264 fd7552d2 2023-07-17 mark }