Git: Which commits will be replayed?

Predict the to-do list of git rebase.

What to build

A program that lists the commits a rebase will replay, oldest first.

Requirements

  • Follow first parents from the branch tip, stopping at the first commit that is reachable from the upstream tip; every commit passed on the way is replayed.
  • Print pick ID MESSAGE for each, oldest first, or Current branch is up to date. if there are none.

Input

Line 1: c. Then c lines ID PARENTS MESSAGE… where PARENTS is - or ids joined by commas. Last line: the branch tip and the upstream tip.

Output

The to-do lines, or the up-to-date message.

Constraints

c ≤ 1,000.

Example

Input:

5
a - Start
b a Add page
m1 b Fix footer
f1 b Add search
f2 f1 Search results
f2 m1

Output:

pick f1 Add search
pick f2 Search results

Why it works

A rebase only needs to move the work the upstream does not already have, and that work is exactly the part of the branch's line that the upstream cannot reach.

Examples

Example 1 · Input
5
a - Start
b a Add page
m1 b Fix footer
f1 b Add search
f2 f1 Search results
f2 m1
Expected output
pick f1 Add search
pick f2 Search results
Example 2 · Input
3
a - Start
b a Next
c b Latest
b c
Expected output
Current branch is up to date.

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

Hints

Hint 1

Collect every commit reachable from the upstream's tip.

Hint 2

Walk first parents from the branch tip until you reach one of those commits, then reverse the list.

Solution

Show one correct solution (try it yourself first)
commits = {}
for _ in range(int(input())):
    oid, parents, message = input().split(maxsplit=2)
    commits[oid] = ([] if parents == "-" else parents.split(","), message)
branch, upstream = input().split()
reach, stack = set(), [upstream]
while stack:
    oid = stack.pop()
    if oid not in reach:
        reach.add(oid)
        stack.extend(commits[oid][0])
todo, oid = [], branch
while oid not in reach:
    todo.append(oid)
    oid = commits[oid][0][0]
if todo:
    for oid in reversed(todo):
        print("pick", oid, commits[oid][1])
else:
    print("Current branch is up to date.")

Lesson: Rebasing →