Git: Which pushes does the remote accept?

Model the rules a Git server applies to every push.

What to build

A program that simulates a sequence of pushes to a remote and prints Git's report for each.

Requirements

  • Commands: push BRANCH ID, push --force BRANCH ID and push --force-with-lease=EXPECTED BRANCH ID. Use the first 7 characters of ids in messages: new branch * [new branch] BRANCH -> BRANCH; same tip Everything up-to-date; fast-forward OLD..NEW BRANCH -> BRANCH; rejected ! [rejected] BRANCH -> BRANCH (non-fast-forward); lease mismatch ! [rejected] BRANCH -> BRANCH (stale info); accepted forced update that is not a fast-forward + OLD...NEW BRANCH -> BRANCH (forced update) (a forced push that happens to be a fast-forward prints the normal fast-forward line).
  • Accepted pushes move the remote branch. Finally print remote: and the branches as BRANCH=ID (short ids, sorted by name).

Input

Line 1: c. Then c lines ID PARENT…. Then b and b lines BRANCH ID (the remote's starting branches). Then m and m commands.

Output

One line per push, then the final line.

Constraints

c ≤ 1,000; m ≤ 100.

Example

Input:

4
a000000000
b111111111 a000000000
c222222222 b111111111
x333333333 b111111111
1
main b111111111
4
push main c222222222
push main x333333333
push feature x333333333
push main c222222222

Output:

b111111..c222222 main -> main
! [rejected] main -> main (non-fast-forward)
* [new branch] feature -> feature
Everything up-to-date
remote: feature=x333333 main=c222222

Why it works

A fast-forward only adds commits, so it can never lose anyone's work; anything else would drop commits from the branch, so it needs force, and a lease makes sure the commits dropped are ones you have seen.

Examples

Example 1 · Input
4
a000000000
b111111111 a000000000
c222222222 b111111111
x333333333 b111111111
1
main b111111111
4
push main c222222222
push main x333333333
push feature x333333333
push main c222222222
Expected output
b111111..c222222 main -> main
! [rejected] main -> main (non-fast-forward)
* [new branch] feature -> feature
Everything up-to-date
remote: feature=x333333 main=c222222
Example 2 · Input
3
a000000000
b111111111 a000000000
x333333333 a000000000
1
main b111111111
1
push --force main x333333333
Expected output
+ b111111...x333333 main -> main (forced update)
remote: main=x333333

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

Hints

Hint 1

A normal push is accepted if the branch is new, unchanged, or a fast-forward (the remote's tip is an ancestor of the pushed commit).

Hint 2

`--force-with-lease=X` is accepted only if the remote's tip is still X; a successful forced push replaces the tip whatever it was.

Solution

Show one correct solution (try it yourself first)
parents = {}
for _ in range(int(input())):
    oid, *ps = input().split()
    parents[oid] = ps
remote = dict(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


for _ in range(int(input())):
    parts = input().split()
    branch, new = parts[-2], parts[-1]
    option = parts[1] if len(parts) == 4 else ""
    old = remote.get(branch)
    if old is None:
        remote[branch] = new
        print(f"* [new branch] {branch} -> {branch}")
        continue
    if old == new:
        print("Everything up-to-date")
        continue
    fast_forward = old in reachable(new)
    if option.startswith("--force-with-lease="):
        if option.split("=", 1)[1] != old:
            print(f"! [rejected] {branch} -> {branch} (stale info)")
            continue
        forced = True
    else:
        forced = option == "--force"
    if fast_forward:
        print(f"{old[:7]}..{new[:7]} {branch} -> {branch}")
    elif forced:
        print(f"+ {old[:7]}...{new[:7]} {branch} -> {branch} (forced update)")
    else:
        print(f"! [rejected] {branch} -> {branch} (non-fast-forward)")
        continue
    remote[branch] = new
print("remote: " + " ".join(f"{b}={i[:7]}" for b, i in sorted(remote.items())))

Lesson: Remotes: clone, fetch, pull and push →