1 /*
2 * Copyright (C) 2013, CloudBees, Inc.
3 * and other copyright owners as documented in the project's IP log.
4 *
5 * This program and the accompanying materials are made available
6 * under the terms of the Eclipse Distribution License v1.0 which
7 * accompanies this distribution, is reproduced below, and is
8 * available at http://www.eclipse.org/org/documents/edl-v10.php
9 *
10 * All rights reserved.
11 *
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
14 * conditions are met:
15 *
16 * - Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 *
19 * - Redistributions in binary form must reproduce the above
20 * copyright notice, this list of conditions and the following
21 * disclaimer in the documentation and/or other materials provided
22 * with the distribution.
23 *
24 * - Neither the name of the Eclipse Foundation, Inc. nor the
25 * names of its contributors may be used to endorse or promote
26 * products derived from this software without specific prior
27 * written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
42 */
43 package org.eclipse.jgit.api;
44
45 import static org.eclipse.jgit.lib.Constants.R_TAGS;
46
47 import java.io.IOException;
48 import java.text.MessageFormat;
49 import java.util.ArrayList;
50 import java.util.Collection;
51 import java.util.Collections;
52 import java.util.Comparator;
53 import java.util.List;
54 import java.util.Map;
55 import java.util.Optional;
56 import java.util.stream.Collectors;
57
58 import org.eclipse.jgit.api.errors.GitAPIException;
59 import org.eclipse.jgit.api.errors.JGitInternalException;
60 import org.eclipse.jgit.api.errors.RefNotFoundException;
61 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
62 import org.eclipse.jgit.errors.InvalidPatternException;
63 import org.eclipse.jgit.errors.MissingObjectException;
64 import org.eclipse.jgit.ignore.internal.IMatcher;
65 import org.eclipse.jgit.ignore.internal.PathMatcher;
66 import org.eclipse.jgit.internal.JGitText;
67 import org.eclipse.jgit.lib.Constants;
68 import org.eclipse.jgit.lib.ObjectId;
69 import org.eclipse.jgit.lib.Ref;
70 import org.eclipse.jgit.lib.Repository;
71 import org.eclipse.jgit.revwalk.RevCommit;
72 import org.eclipse.jgit.revwalk.RevFlag;
73 import org.eclipse.jgit.revwalk.RevFlagSet;
74 import org.eclipse.jgit.revwalk.RevWalk;
75
76 /**
77 * Given a commit, show the most recent tag that is reachable from a commit.
78 *
79 * @since 3.2
80 */
81 public class DescribeCommand extends GitCommand<String> {
82 private final RevWalk w;
83
84 /**
85 * Commit to describe.
86 */
87 private RevCommit target;
88
89 /**
90 * How many tags we'll consider as candidates.
91 * This can only go up to the number of flags JGit can support in a walk,
92 * which is 24.
93 */
94 private int maxCandidates = 10;
95
96 /**
97 * Whether to always use long output format or not.
98 */
99 private boolean longDesc;
100
101 /**
102 * Pattern matchers to be applied to tags under consideration
103 */
104 private List<IMatcher> matchers = new ArrayList<>();
105
106 /**
107 * Constructor for DescribeCommand.
108 *
109 * @param repo
110 * the {@link org.eclipse.jgit.lib.Repository}
111 */
112 protected DescribeCommand(Repository repo) {
113 super(repo);
114 w = new RevWalk(repo);
115 w.setRetainBody(false);
116 }
117
118 /**
119 * Sets the commit to be described.
120 *
121 * @param target
122 * A non-null object ID to be described.
123 * @return {@code this}
124 * @throws MissingObjectException
125 * the supplied commit does not exist.
126 * @throws IncorrectObjectTypeException
127 * the supplied id is not a commit or an annotated tag.
128 * @throws java.io.IOException
129 * a pack file or loose object could not be read.
130 */
131 public DescribeCommand setTarget(ObjectId target) throws IOException {
132 this.target = w.parseCommit(target);
133 return this;
134 }
135
136 /**
137 * Sets the commit to be described.
138 *
139 * @param rev
140 * Commit ID, tag, branch, ref, etc. See
141 * {@link org.eclipse.jgit.lib.Repository#resolve(String)} for
142 * allowed syntax.
143 * @return {@code this}
144 * @throws IncorrectObjectTypeException
145 * the supplied id is not a commit or an annotated tag.
146 * @throws org.eclipse.jgit.api.errors.RefNotFoundException
147 * the given rev didn't resolve to any object.
148 * @throws java.io.IOException
149 * a pack file or loose object could not be read.
150 */
151 public DescribeCommand setTarget(String rev) throws IOException,
152 RefNotFoundException {
153 ObjectId id = repo.resolve(rev);
154 if (id == null)
155 throw new RefNotFoundException(MessageFormat.format(JGitText.get().refNotResolved, rev));
156 return setTarget(id);
157 }
158
159 /**
160 * Determine whether always to use the long format or not. When set to
161 * <code>true</code> the long format is used even the commit matches a tag.
162 *
163 * @param longDesc
164 * <code>true</code> if always the long format should be used.
165 * @return {@code this}
166 * @see <a
167 * href="https://www.kernel.org/pub/software/scm/git/docs/git-describe.html"
168 * >Git documentation about describe</a>
169 * @since 4.0
170 */
171 public DescribeCommand setLong(boolean longDesc) {
172 this.longDesc = longDesc;
173 return this;
174 }
175
176 private String longDescription(Ref tag, int depth, ObjectId tip)
177 throws IOException {
178 return String.format(
179 "%s-%d-g%s", tag.getName().substring(R_TAGS.length()), //$NON-NLS-1$
180 Integer.valueOf(depth), w.getObjectReader().abbreviate(tip)
181 .name());
182 }
183
184 /**
185 * Sets one or more {@code glob(7)} patterns that tags must match to be
186 * considered. If multiple patterns are provided, tags only need match one
187 * of them.
188 *
189 * @param patterns
190 * the {@code glob(7)} pattern or patterns
191 * @return {@code this}
192 * @throws org.eclipse.jgit.errors.InvalidPatternException
193 * if the pattern passed in was invalid.
194 * @see <a href=
195 * "https://www.kernel.org/pub/software/scm/git/docs/git-describe.html"
196 * >Git documentation about describe</a>
197 * @since 4.9
198 */
199 public DescribeCommand setMatch(String... patterns) throws InvalidPatternException {
200 for (String p : patterns) {
201 matchers.add(PathMatcher.createPathMatcher(p, null, false));
202 }
203 return this;
204 }
205
206 private Optional<Ref> getBestMatch(List<Ref> tags) {
207 if (tags == null || tags.size() == 0) {
208 return Optional.empty();
209 } else if (matchers.size() == 0) {
210 // No matchers, simply return the first tag entry
211 return Optional.of(tags.get(0));
212 } else {
213 // Find the first tag that matches one of the matchers; precedence according to matcher definition order
214 for (IMatcher matcher : matchers) {
215 Optional<Ref> match = tags.stream()
216 .filter(tag -> matcher.matches(tag.getName(), false,
217 false))
218 .findFirst();
219 if (match.isPresent()) {
220 return match;
221 }
222 }
223 return Optional.empty();
224 }
225 }
226
227 private ObjectId getObjectIdFromRef(Ref r) {
228 ObjectId key = repo.peel(r).getPeeledObjectId();
229 if (key == null) {
230 key = r.getObjectId();
231 }
232 return key;
233 }
234
235 /**
236 * {@inheritDoc}
237 * <p>
238 * Describes the specified commit. Target defaults to HEAD if no commit was
239 * set explicitly.
240 */
241 @Override
242 public String call() throws GitAPIException {
243 try {
244 checkCallable();
245
246 if (target == null)
247 setTarget(Constants.HEAD);
248
249 Collection<Ref> tagList = repo.getRefDatabase().getRefs(R_TAGS).values();
250 Map<ObjectId, List<Ref>> tags = tagList.stream()
251 .collect(Collectors.groupingBy(this::getObjectIdFromRef));
252
253 // combined flags of all the candidate instances
254 final RevFlagSet allFlags = new RevFlagSet();
255
256 /**
257 * Tracks the depth of each tag as we find them.
258 */
259 class Candidate {
260 final Ref tag;
261 final RevFlag flag;
262
263 /**
264 * This field counts number of commits that are reachable from
265 * the tip but not reachable from the tag.
266 */
267 int depth;
268
269 Candidate(RevCommit commit, Ref tag) {
270 this.tag = tag;
271 this.flag = w.newFlag(tag.getName());
272 // we'll mark all the nodes reachable from this tag accordingly
273 allFlags.add(flag);
274 w.carry(flag);
275 commit.add(flag);
276 // As of this writing, JGit carries a flag from a child to its parents
277 // right before RevWalk.next() returns, so all the flags that are added
278 // must be manually carried to its parents. If that gets fixed,
279 // this will be unnecessary.
280 commit.carry(flag);
281 }
282
283 /**
284 * Does this tag contain the given commit?
285 */
286 boolean reaches(RevCommit c) {
287 return c.has(flag);
288 }
289
290 String describe(ObjectId tip) throws IOException {
291 return longDescription(tag, depth, tip);
292 }
293
294 }
295 List<Candidate> candidates = new ArrayList<>(); // all the candidates we find
296
297 // is the target already pointing to a suitable tag? if so, we are done!
298 Optional<Ref> bestMatch = getBestMatch(tags.get(target));
299 if (bestMatch.isPresent()) {
300 return longDesc ? longDescription(bestMatch.get(), 0, target) :
301 bestMatch.get().getName().substring(R_TAGS.length());
302 }
303
304 w.markStart(target);
305
306 int seen = 0; // commit seen thus far
307 RevCommit c;
308 while ((c = w.next()) != null) {
309 if (!c.hasAny(allFlags)) {
310 // if a tag already dominates this commit,
311 // then there's no point in picking a tag on this commit
312 // since the one that dominates it is always more preferable
313 bestMatch = getBestMatch(tags.get(c));
314 if (bestMatch.isPresent()) {
315 Candidate cd = new Candidate(c, bestMatch.get());
316 candidates.add(cd);
317 cd.depth = seen;
318 }
319 }
320
321 // if the newly discovered commit isn't reachable from a tag that we've seen
322 // it counts toward the total depth.
323 for (Candidate cd : candidates) {
324 if (!cd.reaches(c))
325 cd.depth++;
326 }
327
328 // if we have search going for enough tags, we will start
329 // closing down. JGit can only give us a finite number of bits,
330 // so we can't track all tags even if we wanted to.
331 if (candidates.size() >= maxCandidates)
332 break;
333
334 // TODO: if all the commits in the queue of RevWalk has allFlags
335 // there's no point in continuing search as we'll not discover any more
336 // tags. But RevWalk doesn't expose this.
337 seen++;
338 }
339
340 // at this point we aren't adding any more tags to our search,
341 // but we still need to count all the depths correctly.
342 while ((c = w.next()) != null) {
343 if (c.hasAll(allFlags)) {
344 // no point in visiting further from here, so cut the search here
345 for (RevCommit p : c.getParents())
346 p.add(RevFlag.SEEN);
347 } else {
348 for (Candidate cd : candidates) {
349 if (!cd.reaches(c))
350 cd.depth++;
351 }
352 }
353 }
354
355 // if all the nodes are dominated by all the tags, the walk stops
356 if (candidates.isEmpty())
357 return null;
358
359 Candidate best = Collections.min(candidates, new Comparator<Candidate>() {
360 @Override
361 public int compare(Candidate o1, Candidate o2) {
362 return o1.depth - o2.depth;
363 }
364 });
365
366 return best.describe(target);
367 } catch (IOException e) {
368 throw new JGitInternalException(e.getMessage(), e);
369 } finally {
370 setCallable(false);
371 w.close();
372 }
373 }
374 }