Git: Describe a commit by its nearest tag

Produce the name git describe gives a commit.

What to build

A program that describes commits relative to the nearest reachable tag.

Requirements

  • A tag is a candidate for commit X if its commit is reachable from X. Its distance is the number of commits reachable from X but not from the tag's commit. Choose the smallest distance; on a tie, the highest version (semantic versioning as in the earlier exercise).
  • Print TAG if the distance is 0, else TAG-N-gID with the first 7 characters of X's id; print fatal: No names found, cannot describe X if no tag is reachable.

Input

Line 1: c. Then c lines ID PARENT…. Then t and t lines TAG ID. Then q and q commit ids.

Output

q lines.

Constraints

c ≤ 1,000; t ≤ 50.

Example

Input:

4
a1a1a1a1a1
b2b2b2b2b2 a1a1a1a1a1
c3c3c3c3c3 b2b2b2b2b2
d4d4d4d4d4 c3c3c3c3c3
1
v1.0.0 b2b2b2b2b2
3
d4d4d4d4d4
b2b2b2b2b2
a1a1a1a1a1

Output:

v1.0.0-2-gd4d4d4d
v1.0.0
fatal: No names found, cannot describe a1a1a1a1a1

Why it works

The distance counts the commits made since a tag that are part of X's history, so the nearest tag plus that count and the id pinpoints X in human terms.

Examples

Example 1 · Input
4
a1a1a1a1a1
b2b2b2b2b2 a1a1a1a1a1
c3c3c3c3c3 b2b2b2b2b2
d4d4d4d4d4 c3c3c3c3c3
1
v1.0.0 b2b2b2b2b2
3
d4d4d4d4d4
b2b2b2b2b2
a1a1a1a1a1
Expected output
v1.0.0-2-gd4d4d4d
v1.0.0
fatal: No names found, cannot describe a1a1a1a1a1
Example 2 · Input
3
aaaaaaaaaa
bbbbbbbbbb aaaaaaaaaa
cccccccccc bbbbbbbbbb
2
v1.0.0 aaaaaaaaaa
v1.1.0 bbbbbbbbbb
1
cccccccccc
Expected output
v1.1.0-1-gccccccc

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For each tag, count the commits reachable from the target but not from the tagged commit.

Hint 2

Only tags whose commit is reachable from the target count; choose the smallest count, then the newest tag by version.

Solution

Show one correct solution (try it yourself first)
parents = {}
for _ in range(int(input())):
    oid, *ps = input().split()
    parents[oid] = ps
tags = [input().split() for _ in range(int(input()))]


def reachable(tip):
    seen, stack = set(), [tip]
    while stack:
        oid = stack.pop()
        if oid not in seen:
            seen.add(oid)
            stack.extend(parents[oid])
    return seen


def version(tag):
    core, _, pre = tag.lstrip("v").partition("-")
    numbers = tuple(int(x) for x in core.split("."))
    parts = tuple((0, int(p), "") if p.isdigit() else (1, 0, p) for p in pre.split(".")) if pre else ()
    return numbers + ((0, parts) if pre else (1, ()))


for _ in range(int(input())):
    x = input().strip()
    history = reachable(x)
    candidates = [(len(history - reachable(oid)), tag) for tag, oid in tags if oid in history]
    if not candidates:
        print(f"fatal: No names found, cannot describe {x}")
        continue
    distance = min(d for d, _ in candidates)
    best = max((t for d, t in candidates if d == distance), key=version)
    print(best if distance == 0 else f"{best}-{distance}-g{x[:7]}")

Lesson: Stashing work and tagging releases →