Git: Resolve revision expressions

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 with ref: NAME or hold an id), a branch name, or a unique id prefix of at least 4 characters. Suffixes: ~n follows the first parent n times (~ is ~1); ^n takes the n-th parent (^ is ^1, ^0 is the commit itself).
  • Print the full id, or error: unknown revision X for a name that matches nothing, error: ambiguous revision X for a prefix matching several ids, or error: X has no such parent when 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

Example 1 · 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
Expected output
c3c3c3
f1f1f1
b2b2b2
a1a1a1
Example 2 · Input
2
abc123
abd456 abc123
1
main abd456
abc123
3
HEAD
abd4
ab
Expected output
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}")

Lesson: Branches, HEAD and revision names →