1 /*
2  * Copyright (c) 2023 Mark Jamsek <mark@jamsek.dev>
3  *
4  * Permission to use, copy, modify, and distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15  */
16 
17 #include <sys/queue.h>
18 
19 #include <ctype.h>
20 #include <limits.h>
21 #include <stddef.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <sha1.h>
26 #include <sha2.h>
27 
28 #include "got_reference.h"
29 #include "got_error.h"
30 #include "got_object.h"
31 #include "got_repository.h"
32 #include "got_cancel.h"
33 #include "got_worktree.h"
34 #include "got_commit_graph.h"
35 #include "got_keyword.h"
36 
37 struct keyword_mod {
38 	char		*kw;
39 	uint64_t	 n;
40 	uint8_t		 sym;
41 	uint8_t		 iskeyword;
42 	uint8_t		 ismodified;
43 };
44 
45 #define GOT_KEYWORD_DESCENDANT	'+'
46 #define GOT_KEYWORD_ANCESTOR	'-'
47 
48 static const struct got_error *
49 parse_keyword(struct keyword_mod *kwm, const char *keyword)
50 {
51 	const char	*kw;
52 	char		*p;
53 
54 	if (keyword == NULL)
55 		return NULL;
56 
57 	/* check if it is a (modified) keyword or modified reference */
58 	if (*keyword == ':') {
59 		kwm->iskeyword = 1;
60 		kw = keyword + 1;
61 	} else
62 		kw = keyword;
63 
64 	kwm->kw = strdup(kw);
65 	if (kwm->kw == NULL)
66 		return got_error_from_errno("strdup");
67 
68 	p = strchr(kwm->kw, ':');
69 
70 	if (p != NULL) {
71 		*p = '\0';
72 		++p;
73 		if (*p != GOT_KEYWORD_DESCENDANT && *p != GOT_KEYWORD_ANCESTOR)
74 			return got_error_fmt(GOT_ERR_BAD_KEYWORD,
75 			    "'%s'", keyword);
76 
77 		kwm->ismodified = 1;
78 		kwm->sym = *p;
79 		++p;
80 
81 		if (*p) {
82 			const char	*errstr;
83 			long long	 n;
84 
85 			n = strtonum(p, 0, LLONG_MAX, &errstr);
86 			if (errstr != NULL)
87 				return got_error_fmt(GOT_ERR_BAD_KEYWORD,
88 				    "'%s'", keyword);
89 
90 			kwm->n = n;
91 		} else
92 			kwm->n = 1;	/* :(+/-) == :(+/-)1 */
93 	}
94 
95 	return NULL;
96 }
97 
98 const struct got_error *
99 got_keyword_to_idstr(char **ret, const char *keyword,
100     struct got_repository *repo, struct got_worktree *wt)
101 {
102 	const struct got_error		*err = NULL;
103 	struct got_commit_graph		*graph = NULL;
104 	struct got_object_id		*head_id = NULL, *kwid = NULL;
105 	struct got_object_id		 iter_id;
106 	struct got_reflist_head		 refs;
107 	struct got_object_id_queue	 commits;
108 	struct got_object_qid		*qid;
109 	struct keyword_mod		 kwm;
110 	const char			*kw = NULL;
111 	char				*kwid_str = NULL;
112 	uint64_t			 n = 0;
113 
114 	*ret = NULL;
115 	TAILQ_INIT(&refs);
116 	STAILQ_INIT(&commits);
117 	memset(&kwm, 0, sizeof(kwm));
118 
119 	err = parse_keyword(&kwm, keyword);
120 	if (err != NULL)
121 		goto done;
122 
123 	kw = kwm.kw;
124 
125 	if (kwm.iskeyword) {
126 		if (strcmp(kw, GOT_KEYWORD_BASE) == 0) {
127 			if (wt == NULL) {
128 				err = got_error_msg(GOT_ERR_NOT_WORKTREE,
129 				    "'-c :base' requires work tree");
130 				goto done;
131 			}
132 
133 			err = got_object_id_str(&kwid_str,
134 			    got_worktree_get_base_commit_id(wt));
135 			if (err != NULL)
136 				goto done;
137 		} else if (strcmp(kw, GOT_KEYWORD_HEAD) == 0) {
138 			struct got_reference *head_ref;
139 
140 			err = got_ref_open(&head_ref, repo, wt != NULL ?
141 			    got_worktree_get_head_ref_name(wt) :
142 			    GOT_REF_HEAD, 0);
143 			if (err != NULL)
144 				goto done;
145 
146 			kwid_str = got_ref_to_str(head_ref);
147 			got_ref_close(head_ref);
148 			if (kwid_str == NULL) {
149 				err = got_error_from_errno("got_ref_to_str");
150 				goto done;
151 			}
152 		} else {
153 			err = got_error_fmt(GOT_ERR_BAD_KEYWORD, "'%s'", kw);
154 			goto done;
155 		}
156 	} else if (kwm.ismodified) {
157 		/* reference:[(+|-)[N]] */
158 		kwid_str = strdup(kw);
159 		if (kwid_str == NULL) {
160 			err = got_error_from_errno("strdup");
161 			goto done;
162 		}
163 	} else
164 		goto done;
165 
166 	if (kwm.n == 0)
167 		goto done;	/* unmodified keyword */
168 
169 	err = got_ref_list(&refs, repo, NULL, got_ref_cmp_by_name, NULL);
170 	if (err)
171 		goto done;
172 
173 	err = got_repo_match_object_id(&kwid, NULL, kwid_str,
174 	    GOT_OBJ_TYPE_COMMIT, &refs, repo);
175 	if (err != NULL)
176 		goto done;
177 
178 	/*
179 	 * If looking for a descendant, we need to iterate from
180 	 * HEAD so grab its id now if it's not already in kwid.
181 	 */
182 	if (kwm.sym == GOT_KEYWORD_DESCENDANT && kw != NULL &&
183 	    strcmp(kw, GOT_KEYWORD_HEAD) != 0) {
184 		struct got_reference *head_ref;
185 
186 		err = got_ref_open(&head_ref, repo, wt != NULL ?
187 		    got_worktree_get_head_ref_name(wt) : GOT_REF_HEAD, 0);
188 		if (err != NULL)
189 			goto done;
190 		err = got_ref_resolve(&head_id, repo, head_ref);
191 		got_ref_close(head_ref);
192 		if (err != NULL)
193 			goto done;
194 	}
195 
196 	err = got_commit_graph_open(&graph, "/", 1);
197 	if (err)
198 		goto done;
199 
200 	err = got_commit_graph_bfsort(graph,
201 	    head_id != NULL ? head_id : kwid, repo, NULL, NULL);
202 	if (err)
203 		goto done;
204 
205 	while (n <= kwm.n) {
206 		err = got_commit_graph_iter_next(&iter_id, graph, repo,
207 		    NULL, NULL);
208 		if (err) {
209 			if (err->code == GOT_ERR_ITER_COMPLETED)
210 				err = NULL;
211 			break;
212 		}
213 
214 		if (kwm.sym == GOT_KEYWORD_DESCENDANT) {
215 			/*
216 			 * We want the Nth generation descendant of KEYWORD,
217 			 * so queue all commits from HEAD to KEYWORD then we
218 			 * can walk from KEYWORD to its Nth gen descendent.
219 			 */
220 			err = got_object_qid_alloc(&qid, &iter_id);
221 			if (err)
222 				goto done;
223 			STAILQ_INSERT_HEAD(&commits, qid, entry);
224 
225 			if (got_object_id_cmp(&iter_id, kwid) == 0)
226 				break;
227 			continue;
228 		}
229 		++n;
230 	}
231 
232 	if (kwm.sym == GOT_KEYWORD_DESCENDANT) {
233 		n = 0;
234 
235 		STAILQ_FOREACH(qid, &commits, entry) {
236 			if (qid == STAILQ_LAST(&commits, got_object_qid, entry)
237 			    || n == kwm.n)
238 				break;
239 			++n;
240 		}
241 
242 		memcpy(&iter_id, &qid->id, sizeof(iter_id));
243 	}
244 
245 	free(kwid_str);
246 	err = got_object_id_str(&kwid_str, &iter_id);
247 
248 done:
249 	free(kwid);
250 	free(kwm.kw);
251 	free(head_id);
252 	got_ref_list_free(&refs);
253 	got_object_id_queue_free(&commits);
254 	if (graph != NULL)
255 		got_commit_graph_close(graph);
256 
257 	if (err != NULL) {
258 		free(kwid_str);
259 		return err;
260 	}
261 
262 	*ret = kwid_str;
263 	return NULL;
264 }