Implement the revision syntax that every Git command accepts.
What to build
A program that resolves revision expressions to full commit ids, as git rev-parse does.
Requirements
- Names:
HEAD(which may point to a branch withref: NAMEor hold an id), a branch name, or a unique id prefix of at least 4 characters. Suffixes:~nfollows the first parent n times (~is~1);^ntakes the n-th parent (^is^1,^0is the commit itself). - Print the full id, or
error: unknown revision Xfor a name that matches nothing,error: ambiguous revision Xfor a prefix matching several ids, orerror: X has no such parentwhen a step needs a parent that does not exist (X is the whole expression).
Input
Line 1: c. Then c lines ID PARENT…. Then b and b lines NAME ID. Then the HEAD line. Then q and q expressions.
Output
q lines.
Constraints
c ≤ 1,000; numbers in suffixes ≤ 100.
Example
Input:
5
a1a1a1
b2b2b2 a1a1a1
c3c3c3 b2b2b2
f1f1f1 b2b2b2
m4m4m4 c3c3c3 f1f1f1
2
main m4m4m4
feature f1f1f1
ref: main
4
HEAD~1
HEAD^2
HEAD^2~1
feature~2
Output:
c3c3c3
f1f1f1
b2b2b2
a1a1a1
Why it works
Every suffix is one step along parent links from the commit the name points to, so applying them in order reaches exactly the commit the expression describes.
Examples
5 a1a1a1 b2b2b2 a1a1a1 c3c3c3 b2b2b2 f1f1f1 b2b2b2 m4m4m4 c3c3c3 f1f1f1 2 main m4m4m4 feature f1f1f1 ref: main 4 HEAD~1 HEAD^2 HEAD^2~1 feature~2
c3c3c3 f1f1f1 b2b2b2 a1a1a1
2 abc123 abd456 abc123 1 main abd456 abc123 3 HEAD abd4 ab
abc123 abd456 error: unknown revision ab
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Split the expression at the first `~` or `^`: the part before is a name, the rest is a list of suffixes applied left to right.
Hint 2
A name is HEAD, a branch, or an abbreviation of at least 4 characters matching exactly one commit id.
Solution
Show one correct solution (try it yourself first)
parents = {}
for _ in range(int(input())):
oid, *ps = input().split()
parents[oid] = ps
branches = dict(input().split() for _ in range(int(input())))
head = input().strip()
class RevError(Exception):
pass
def resolve_name(name, expression):
if name == "HEAD":
return branches[head[5:]] if head.startswith("ref: ") else head
if name in branches:
return branches[name]
matches = [oid for oid in parents if len(name) >= 4 and oid.startswith(name)]
if len(matches) > 1:
raise RevError(f"ambiguous revision {expression}")
if not matches:
raise RevError(f"unknown revision {expression}")
return matches[0]
def rev_parse(expression):
cut = next((i for i, ch in enumerate(expression) if ch in "~^"), len(expression))
oid = resolve_name(expression[:cut], expression)
i = cut
while i < len(expression):
op = expression[i]
i += 1
j = i
while j < len(expression) and expression[j].isdigit():
j += 1
n = int(expression[i:j]) if j > i else 1
i = j
if op == "~":
for _ in range(n):
if not parents[oid]:
raise RevError(f"{expression} has no such parent")
oid = parents[oid][0]
elif n > 0:
if n > len(parents[oid]):
raise RevError(f"{expression} has no such parent")
oid = parents[oid][n - 1]
return oid
for _ in range(int(input())):
expression = input().strip()
try:
print(rev_parse(expression))
except RevError as error:
print(f"error: {error}")