#! /usr/bin/python3
# git-assembler: update git branches using high-level instructions
# Copyright(c) 2019-2023 by wave++ "Yuri D'Elia" <wavexx@thregr.org>
# Distributed under the GNU GPLv3+ license, WITHOUT ANY WARRANTY.
import subprocess as sp
import argparse
import os, sys
import shutil
import shlex
import pickle
import re
from enum import Enum, IntEnum
from collections import defaultdict
from copy import deepcopy

import logging
from logging import error, warning, info, debug
logging.TRACE = 5

APP_DSC = "update git branches using high-level instructions"
APP_SIG = "git-assembler"
APP_VER = "1.5"


def repo_toplevel():
    try:
        line = sp.check_output(['git', 'rev-parse', '--show-toplevel'])
    except sp.CalledProcessError as e:
        return None
    return line.decode(sys.getfilesystemencoding()).rstrip()


def repo_git_dir():
    try:
        line = sp.check_output(['git', 'rev-parse', '--git-dir'])
    except sp.CalledProcessError as e:
        return None
    return line.decode(sys.getfilesystemencoding()).rstrip()


def repo_common_dir():
    try:
        line = sp.check_output(['git', 'rev-parse', '--git-common-dir'])
    except sp.CalledProcessError as e:
        return None
    return line.decode(sys.getfilesystemencoding()).rstrip()


def assembly_path(toplevel_dir, common_dir):
    primary = os.path.join(os.path.realpath(common_dir), 'assembly')
    secondary = os.path.join(toplevel_dir, '.gitassembly')
    for path in [primary, secondary]:
        if os.path.isfile(path):
            return path
    # no path was found, prefer primary
    return primary


def parse_info(path, line, msg):
    info('{}:{}: {}'.format(path, line, msg))

def parse_error(path, line, msg):
    error('{}:{}: {}'.format(path, line, msg))

def os_error(e):
    error(str(e))


def parse_assembly(path, branches):
    try:
        fd = open(path, 'rb')
    except OSError as e:
        os_error(e)
        return None

    nodes = {}
    settings = {'target': []}
    global_flags = {'merge': [],
                    'rebase': []}

    for n, line in enumerate(fd, 1):
        # strip comments
        line = line.split(b'#', 1)[0]

        # basic tokenization
        tokens = line.split()
        if len(tokens) == 0:
            continue

        cmd = tokens[0].decode('ascii', 'surrogateescape')
        if cmd == 'target':
            if len(tokens) < 2:
                parse_error(path, n, 'invalid assembly line')
                return None
            if len(settings['target']):
                parse_error(path, n, 'default target/s redefined')
                return None

            # wilcard expansion for targets is performed later
            settings['target'] = tokens[1:]

        elif cmd == 'flags':
            if len(tokens) < 2:
                parse_error(path, n, 'invalid assembly line')
                return None
            target, args = tokens[1].decode('ascii'), tokens[2:]
            if target not in global_flags:
                parse_error(path, n, 'invalid flags target')
                return None
            global_flags[target] = args

        elif cmd in {'base', 'rebase', 'stage', 'merge'}:
            if len(tokens) < 3:
                parse_error(path, n, 'invalid assembly line')
                return None
            target, args = tokens[1], tokens[2:]

            # separate arguments and flags
            rule_flags = deepcopy(global_flags)
            if cmd in global_flags:
                for rule_arg in enumerate(args):
                    if rule_arg[1][0] == ord('-'):
                        rule_flags[cmd].extend(args[rule_arg[0]:])
                        args = args[:rule_arg[0]]
                        break

            # expand the target into multiple rules
            if not branch_is_pattern(target):
                targets = [target]
            else:
                try:
                    targets = list(expand_branches(target, branches.keys()))
                except re.error as e:
                    parse_error(path, n, str(e))
                    return None
                if len(targets) == 0:
                    parse_error(path, n, 'pattern {} in rule does not match any branch'.format(
                        branch_str(target)))
                    return None

            for branch in targets:
                node = nodes.get(branch)
                if node is None:
                    node = empty_node(branch)
                    nodes[branch] = node

                if cmd in {'base', 'rebase', 'stage'}:
                    # define the branch base
                    if node['base']:
                        parse_error(path, n, 'branch base/type cannot be redefined')
                        return None
                    if len(args) != 1:
                        parse_error(path, n, 'invalid base for branch {}'.format(branch_str(branch)))
                        return None
                    node['base'] = args[0]
                    if branch_is_pattern(node['base']):
                        parse_error(path, n, 'base {} cannot be a pattern'.format(branch_str(node['base'])))
                        return None
                    if node['base'] == node['name']:
                        parse_error(path, n, 'refusing to {} {} onto itself'.format(
                            cmd, branch_str(node['base'])))
                        return None
                    if cmd == 'stage':
                        node['type'] = BranchType.STAGE
                    elif cmd == 'rebase':
                        node['type'] = BranchType.REBASE
                        node['flags']['rebase'] = rule_flags['rebase']
                    else:
                        node['type'] = BranchType.BASE

                elif cmd == 'merge':
                    merge_deps = []
                    for arg in args:
                        if not branch_is_pattern(arg):
                            # check rules for explicit dependencies
                            if arg in merge_deps or arg in node['merge']:
                                parse_error(path, n, 'duplicate merge of {} into {}'.format(
                                    branch_str(arg), branch_str(branch)))
                                return None

                            merge_deps.append(arg)
                        else:
                            # expand the argument list
                            try:
                                arg_exp = list(expand_branches(arg, branches.keys()))
                            except re.error as e:
                                parse_error(path, n, str(e))
                                return None
                            if len(arg_exp) == 0:
                                parse_error(path, n, 'pattern {} in rule does not match any branch'.format(
                                    branch_str(target)))
                                return None
                            for arg in arg_exp:
                                # check rules that apply to expanded dependencies
                                if arg in merge_deps or arg in node['merge']:
                                    parse_info(path, n, 'ignoring duplicate merge of {} into {}'.format(
                                        branch_str(arg), branch_str(branch)))
                                    continue
                                merge_deps.append(arg)

                    # check rules that apply to all dependencies
                    for arg in merge_deps:
                        if arg == node['name']:
                            parse_error(path, n, 'refusing merge of {} into itself'.format(
                                branch_str(arg), branch_str(branch)))
                            return None

                    # add dependencies
                    for dep in merge_deps:
                        node['merge'].append(dep)
                        node['flags']['merge'][dep] = rule_flags['merge']

        else:
            parse_error(path, n, 'unknown command: {}'.format(cmd))
            return None

    return nodes, settings


def read_git_config():
    """Read configuration of interest either from git config or environment variables."""
    # The variable ``keys`` contains the configuration necessary for reading
    # the git config. Each entry is a dict with the following keys:
    #   - key: the key in the git configuration.
    #   - type: (optional) the type (git-config type) expected for this key's
    #     value. The type "bool" is converted to a Python bool.
    #   - default: the default value for this key.
    #   - env: (optional) name of the environment variable that overrides this
    #     config.
    keys = (
        {
            'key': 'assembler.mergeff',
            'type': 'bool',
            'default': None,
            'env': 'GIT_ASSEMBLER_MERGEFF',
        },
    )

    conf = {}
    for entry in keys:
        if 'type' in entry:
            type_flags = ('--type', entry['type'])
        else:
            type_flags = ()

        if entry['env'] in os.environ:
            default = os.environ[entry['env']]
            if len(default) == 0:
                default_flags = ('--file', os.devnull)
            else:
                default_flags = ('--file', os.devnull, '--default', default)
        elif entry.get('default') is not None:
            default_flags = ('--default', entry['default'])
        else:
            default_flags = ()

        proc = sp.run(['git', 'config', *type_flags, *default_flags, entry['key']],
                      stdout=sp.PIPE)
        if proc.returncode not in [0, 1]:
            error('failed to parse value for config {}'.format(entry['key']))
            return None
        value = proc.stdout.rstrip()

        if 'type' in entry:
            if entry['type'] == 'bool':
                if value == b'true':
                    value = True
                elif value == b'':
                    value = None
                else:
                    value = False

        conf[entry['key']] = value
    return conf


class BranchType(Enum):
    BRANCH = 0 # regular branch (no base)
    BASE   = 1 # optional bootstrapping
    REBASE = 2 # rebase when needed
    STAGE  = 3 # bootstrap on any change

def leaf_node(node):
    return len(node['deps']) == 0

def empty_node(name):
    return {'name': name,
            'base': None,
            'type': BranchType.BRANCH,
            'path': None,
            'merge': [],
            'deps': [],
            'flags': {'merge': defaultdict(lambda: defaultdict(list)),
                      'rebase': []},
            'state': {'dirty': False,
                      'used': False,
                      'missing': None}}


def assembly_graph(nodes, targets=None):
    # convert all nodes
    for branch in list(nodes):
        node = nodes[branch]
        deps = []

        # convert base
        if node['base'] is not None:
            base_name = node['base']
            base_node = nodes.get(base_name)
            if base_node is None:
                base_node = empty_node(base_name)
                nodes[base_name] = base_node
            node['base'] = base_node
            deps.append(base_node)

        # direct merge dependencies
        merge = []
        for branch_name in node.get('merge'):
            branch_node = nodes.get(branch_name)
            if branch_node is None:
                branch_node = empty_node(branch_name)
                nodes[branch_name] = branch_node
            if branch_node is node['base'] and node['type'] != BranchType.BASE:
                # we allow base switching for experimentation, but
                # notify the user about no-ops and discard the rule
                warning('discarding useless merge of branch {} into {}'.format(
                    color_node(branch_node), color_node(node)))
            else:
                merge.append(branch_node)
        node['merge'] = merge
        deps.extend(merge)

        # all dependencies (in order)
        node['deps'] = deps

    # filter targets
    if targets is None or len(targets) == 0:
        left = set(nodes)
    else:
        left = set(targets)

    # find roots
    connected = set()
    for branch in left:
        for dep in nodes[branch]['deps']:
            connected.add(dep['name'])
    roots = set(left) - connected
    if len(roots) == 0 and len(left) != 0:
        # graph has no root nodes, instead of exiting immediately pick a
        # random node to produce a more useful message later
        roots.add(next(iter(left)))

    # check for cycles
    stack = [(root, set()) for root in roots]
    while len(stack):
        branch, seen = stack.pop()
        if branch in seen:
            error('dependency cycle detected for branch {}'.format(branch_str(branch)))
            return None
        seen.add(branch)
        for dep in nodes[branch]['deps']:
            if not leaf_node(dep):
                stack.append((dep['name'], set(seen)))

    # return root nodes
    return [nodes[name] for name in sorted(roots)]


COLOR_MODE = None

class Ansi:
    BOLD  = "\033[;1m"
    RED   = "\033[1;31m"
    GREEN = "\033[0;32m"
    CYAN  = "\033[0;36m"
    RESET = "\033[0;0m"

def branch_str(branch):
    return branch.decode(sys.getdefaultencoding(), 'surrogateescape')

def oid_str(oid):
    if not oid:
        return '-'
    if isinstance(oid, bytes):
        oid = oid.decode('ascii', 'replace')
    return oid[:12]

def color_node(node, sigils=False):
    name = branch_str(node['name'])
    if node['state']['missing']:
        sigil = '?'
        color = Ansi.RED
    elif node['state']['dirty']:
        sigil = '~'
        color = Ansi.BOLD
    elif node['state']['used']:
        sigil = '*'
        color = Ansi.GREEN
    else:
        sigil = ''
        color = ''
    if COLOR_MODE:
        name = color + name + Ansi.RESET
    elif sigils:
        name += sigil
    return name

def color_path(path):
    return Ansi.CYAN + path + Ansi.RESET if COLOR_MODE else path


def compact_relpath(path):
    # pick the shortest representation (TODO: not necessarily more readable)
    try:
        relpath = os.path.relpath(path)
        return relpath if len(relpath) < len(path) else path
    except ValueError: # This might happen between drives on Windows.
        return path

def worktree_is_current(worktree_path, toplevel_dir):
    return (toplevel_dir == worktree_path and
            os.path.commonpath([worktree_path, toplevel_dir]) == toplevel_dir)

def branch_path_suffix(node, toplevel_dir):
    if node['path'] is None:
        return ''
    if worktree_is_current(node['path'], toplevel_dir):
        return ''
    path = compact_relpath(node['path'])
    return '(' + color_path(path) + ')'


def dump_graph(graph, state, toplevel_dir, root=None, depth=0):
    roots = list(reversed(graph))
    if root is None:
        root = roots

    seen = set()
    while len(roots):
        node = roots.pop()
        if node['name'] in seen:
            continue
        seen.add(node['name'])

        prefix = '  ' * depth
        suffix = branch_path_suffix(node, toplevel_dir)

        # base suffix
        base_node = node['base']
        while base_node is not None:
            if node['type'] == BranchType.STAGE:
                suffix += ' <= '
            elif node['type'] == BranchType.REBASE:
                suffix += ' <- '
            else:
                suffix += ' .. '
            base_name = color_node(base_node, True)
            if len(base_node['merge']) != 0:
                # split the branch into a fake root
                suffix += '[' + base_name + ']'
                root.append(base_node)
                break
            suffix += base_name + branch_path_suffix(base_node, toplevel_dir)
            base_node = base_node['base']

        # prefixes
        if node['name'] == state['current_branch']:
            prefix += '>'
        elif node['name'] == state.get('start_branch'):
            prefix += '<'
        node_name = color_node(node, True)
        print(prefix + node_name + suffix)

        merge = node['merge']
        if len(merge):
            dump_graph(merge, state, toplevel_dir, root, depth + 1)


def topo_sort(graph, seen=None):
    if seen is None:
        seen = set()
    nodes = []
    for node in graph:
        name = node['name']
        if name in seen:
            continue
        seen.add(name)
        nodes.extend(topo_sort(node['deps'], seen))
        nodes.append(node)
    return nodes


def mark_tree_dirty(node, graph):
    dirty = False
    for root in graph:
        if root is node or mark_tree_dirty(node, root['deps']):
            if root is not node and not root['state']['dirty']:
                debug('marking {} dirty (depends on {})'.format(
                    color_node(root), color_node(node)))
            root['state']['dirty'] = dirty = True
    return dirty


def is_ancestor(commit, desc):
    proc = sp.run(['git', 'merge-base', '--is-ancestor', commit, desc],
                  stderr=sp.DEVNULL)
    if proc.returncode not in [0, 1]:
        return None
    return proc.returncode == 0


def needs_merge(dst, branch):
    anc = is_ancestor(branch, dst)
    if anc is None:
        result = 'check failed'
        ret = None
    elif anc:
        result = 'already ancestor'
        ret = False
    else:
        result = 'not an ancestor'
        ret = True
    debug('checking merge of {} into {}: {}'.format(
        branch_str(branch), branch_str(dst), result))
    return ret


def fork_point(dst, base):
    proc = sp.run(['git', 'merge-base', '--fork-point', base, dst],
                  stdout=sp.PIPE, stderr=sp.DEVNULL)
    fork_point = proc.stdout.rstrip()
    if proc.returncode != 0 or len(fork_point) == 0:
        return None
    return fork_point


def branch_tip(name):
    proc = sp.run(['git', 'rev-parse', '--verify', name],
                  stdout=sp.PIPE, stderr=sp.DEVNULL)
    tip = proc.stdout.rstrip()
    if proc.returncode != 0 or len(tip) == 0:
        return None
    return tip


def needs_rebase(dst, base):
    tip = branch_tip(base)
    fp = fork_point(dst, base) if tip is not None else None
    if tip is None:
        result = 'needed (no fork-point)'
        ret = None
    elif fp is not None:
        if tip != fp:
            result = 'needed'
            ret = True
        else:
            result = 'up-to-date'
            ret = False
    else:
        # --fork-point uses the base reflog and can fail even when the
        # current tip is already in dst (expired entries, or dst was not
        # forked from an exact historical tip). Fall back to ancestry.
        anc = is_ancestor(base, dst)
        if anc is None:
            result = 'needed (no fork-point)'
            ret = None
        elif anc:
            result = 'up-to-date (no fork-point)'
            ret = False
        else:
            result = 'needed (no fork-point)'
            ret = True
    debug('checking rebase of {} onto {}: tip={} fork-point={} -> {}'.format(
        branch_str(dst), branch_str(base), oid_str(tip), oid_str(fp), result))
    return ret


def branch_exists(name):
    proc = sp.run(['git', 'rev-parse', '--verify', name],
                  stdout=sp.DEVNULL, stderr=sp.DEVNULL)
    return proc.returncode == 0


def branch_list():
    proc = sp.run(['git', 'branch', '-l', '-a', '--format=%(refname:short) %(worktreepath)'],
                  stdout=sp.PIPE)
    if proc.returncode != 0:
        return None

    lst = {}
    if len(proc.stdout) != 0:
        for line in proc.stdout.rstrip(b'\n').split(b'\n'):
            branch, path = line.split(b' ', 1)
            if len(path) == 0:
                path = None
            else:
                path = path.decode(sys.getfilesystemencoding())
            lst[branch] = path
    return lst


def branch_is_pattern(branch):
    return (branch[0] == ord('/') or b'*' in branch)

def expand_branches(pattern, branches):
    if pattern[0] == ord('/'):
        # user-supplied regex
        comp = re.compile(pattern[1:], re.LOCALE)
    else:
        # convert the glob-like expression into a RE
        pattern = re.escape(pattern)
        pattern = pattern.replace(b'\\*\\*', b'.*')
        pattern = pattern.replace(b'\\*', b'[^/]*')
        comp = re.compile(b'^' + pattern + b'$')
    for branch in branches:
        if re.search(comp, branch):
            yield branch


def node_missing(node):
    if node['state']['missing'] is None:
        node['state']['missing'] = not branch_exists(node['name'])

def nodes_missing(nodes):
    for node in nodes:
        node_missing(node)


def update_state(ordered_nodes, graph, branches, force):
    for node in ordered_nodes:
        # worktree path
        node['path'] = branches.get(node['name'])

        if leaf_node(node):
            continue

        if node['base'] is not None:
            if node['type'] == BranchType.BASE:
                # base should be created only when missing
                nodes_missing([node, node['base']])
                if node['state']['missing']:
                    node['base']['state']['used'] = True
                    debug('marking {} dirty (missing)'.format(color_node(node)))
                    mark_tree_dirty(node, graph)
            else:
                # always check if rebase is needed
                if force or node['state']['missing'] or node['base']['state']['missing']:
                    dirty = None
                else:
                    dirty = needs_rebase(node['name'], node['base']['name'])
                if dirty is not False:
                    if dirty is None:
                        nodes_missing([node, node['base']])
                    node['base']['state']['used'] = True
                    if force:
                        reason = '--recreate'
                    elif node['state']['missing'] or node['base']['state']['missing']:
                        reason = 'missing'
                    else:
                        reason = 'rebase onto {}'.format(color_node(node['base']))
                    debug('marking {} dirty ({})'.format(color_node(node), reason))
                    mark_tree_dirty(node, graph)

        # merge dependencies
        for dep in node['merge']:
            if node['state']['missing'] or dep['state']['missing']:
                ret = None
            elif node['base'] is dep and node['type'] != BranchType.BASE:
                # merge is known in advance to be a no-op
                ret = False
            else:
                ret = needs_merge(node['name'], dep['name'])
            if ret is not False:
                if ret is None:
                    nodes_missing([node, dep])
                if node['state']['missing'] or dep['state']['missing']:
                    reason = 'missing'
                else:
                    reason = 'merge of {}'.format(color_node(dep))
                debug('marking {} dirty ({})'.format(color_node(node), reason))
                mark_tree_dirty(node, graph)
                dep['state']['used'] = True
                if node['type'] == BranchType.STAGE:
                    node['base']['state']['used'] = True


def check_missing(nodes, create):
    state = True
    for node in nodes:
        if node['state']['missing']:
            if node['base'] is None:
                # find the branch requiring node
                state = False
                for ref in nodes:
                    if node in ref['deps']:
                        break
                else:
                    ref = None
                if ref is None:
                    error('branch {} is required but does not exist'.format(color_node(node)))
                else:
                    error('branch {} is required by {} but does not exist'.format(color_node(node), color_node(ref)))
            elif node['type'] != BranchType.STAGE and not create:
                # prevent creation unless explicitly allowed
                state = False
                error('branch {} needs creation from {}'.format(color_node(node), color_node(node['base'])))
    return state


def check_dirty(nodes):
    for node in nodes:
        if node['state']['dirty']:
            return True
    return False


def current_branch(path):
    proc = sp.run(['git', 'rev-parse', '--abbrev-ref', 'HEAD'],
                  cwd=path, stdout=sp.PIPE, stderr=sp.DEVNULL)
    name = proc.stdout.rstrip()
    if proc.returncode != 0 or len(name) == 0:
        return None
    return name


def read_state(git_dir):
    cache_dir = os.path.join(git_dir, 'as-cache')
    if not os.path.exists(cache_dir):
        # no state
        return {}

    # version state check
    version_path = os.path.join(git_dir, 'as-cache', 'version')
    if not os.path.exists(version_path):
        version_str = None
    else:
        with open(version_path, "r") as version_fd:
            version_str = version_fd.readline().rstrip()
    if version_str != APP_VER:
        error('incompatible state: continue with previous version or use --clear to remove')
        return None

    state_path = os.path.join(git_dir, 'as-cache', 'state')
    if not os.path.exists(state_path):
        error('inconsistent state: please file a bug report or use --clear to remove')
        return None

    return pickle.load(open(state_path, 'rb'))


def save_state(git_dir, state):
    cache_dir = os.path.join(git_dir, 'as-cache')
    dir_exists = os.path.exists(cache_dir)
    if not state:
        # no state to save, cleanup cache dir
        if dir_exists:
            shutil.rmtree(cache_dir)
        return
    if not dir_exists:
        os.mkdir(cache_dir)

    # cache assembly instructions
    assembly_path = os.path.realpath(os.path.join(cache_dir, 'assembly'))
    if not os.path.exists(assembly_path) or \
       not os.path.samefile(state['assembly_path'], assembly_path):
        shutil.copy(state['assembly_path'], assembly_path)
        state['assembly_path'] = assembly_path

    # save version state
    version_path = os.path.realpath(os.path.join(cache_dir, 'version'))
    with open(version_path, "w") as version_fd:
        version_fd.write(APP_VER + '\n')

    # save state
    state_path = os.path.join(cache_dir, 'state')
    pickle.dump(state, open(state_path, 'wb'))


def clear_state(git_dir):
    save_state(git_dir, None)


def switch_to_branch(name, path):
    proc = run(['git', 'checkout', '-q', '--no-guess', name],
               cwd=path, stdout=sp.DEVNULL, stderr=sp.PIPE)
    stderr = proc.stderr.decode(sys.getdefaultencoding(), 'surrogateescape').rstrip()
    return proc.returncode, stderr


def str_flags(flags):
    ret = []
    for flag in flags:
        if type(flag) is bytes:
            flag = flag.decode(sys.getdefaultencoding(), 'surrogateescape')
        ret.append(flag)
    return ' '.join(ret)

def using_flags(flags):
    if len(flags) == 0:
        return ''
    return ' using ' + str_flags(flags)

def run(args, **kwargs):
    if logging.TRACE >= logging.root.level:
        logging.log(logging.TRACE, 'running cwd={} {}'.format(
            kwargs.get('cwd', os.getcwd()), str_flags(args)))
    return sp.run(args, **kwargs)


def update_node(node, state, toplevel_dir, dry_run, merge_ff):
    if not node['state']['dirty']:
        debug('skipping {} (not dirty)'.format(color_node(node)))
        return True

    # logging helper
    def log(prio, msg):
        state['last_msg'] = msg
        if dry_run and prio >= logging.INFO:
            prio = logging.WARNING
        logging.log(prio, msg)

    node_worktree = node['path'] if node['path'] is not None else state['start_worktree']
    node_current = worktree_is_current(node_worktree, toplevel_dir)

    if node['type'] == BranchType.STAGE:
        # erase target (if it exists)
        if not node['state']['missing']:
            if node['path'] is not None:
                log(logging.INFO, 'detaching branch {}{}'.format(
                    color_node(node), branch_path_suffix(node, toplevel_dir)))
                if not dry_run:
                    proc = run(['git', 'checkout', '-q', '--detach', '--no-guess'],
                               cwd=node_worktree)
                    if proc.returncode != 0:
                        return False
            log(logging.INFO, 'erasing existing branch {}'.format(color_node(node)))
            if not dry_run:
                proc = run(['git', 'branch', '-q', '-D', node['name']])
                if proc.returncode != 0:
                    return False
        exists = False
    elif node['name'] == state['last_branch']:
        # starting worktree already at the right branch
        exists = True
    elif node['path'] is not None:
        # node already checked-out in some other worktree
        exists = True
    else:
        # switch starting worktree to target
        if node_current:
            log(logging.DEBUG, 'switching to branch {}'.format(color_node(node)))
        else:
            log(logging.DEBUG, 'switching {} to branch {}'.format(
                color_path(compact_relpath(node_worktree)), color_node(node)))
        if dry_run:
            exists = branch_exists(node['name'])
        else:
            # check existence optimistically to avoid extra queries
            ret, err = switch_to_branch(node['name'], node_worktree)
            exists = (ret == 0)
            if ret != 0:
                # slow path to exclude checkout errors
                if branch_exists(node['name']):
                    state['last_err'] = err
                    return False
        state['last_branch'] = node['name']

    if not exists:
        # branch is missing, bootstrap
        log(logging.INFO, 'creating branch {}{} from {}'.format(
            color_node(node), branch_path_suffix(node, toplevel_dir),
            color_node(node['base'])))
        if not dry_run:
            proc = run(['git', 'checkout', '-q', '--no-guess', '-b',
                        node['name'], node['base']['name']],
                       cwd=node_worktree)
            if proc.returncode != 0:
                return False
        if node['path'] is None:
            state['last_branch'] = node['name']
    else:
        # rebase when required
        if node['type'] == BranchType.REBASE and node['base'] is not None:
            if node['base']['state']['dirty']:
                dirty = True
                debug('rebase of {} forced because {} is dirty'.format(
                    color_node(node), color_node(node['base'])))
            else:
                dirty = needs_rebase(node['name'], node['base']['name'])
            if dirty is not False:
                flags = node['flags']['rebase']
                log(logging.INFO, 'rebasing {}{} onto {}'.format(
                    color_node(node), branch_path_suffix(node, toplevel_dir),
                    color_node(node['base'])) + using_flags(flags))
                if not dry_run:
                    proc = run(['git', 'rebase', '-q', '--fork-point',
                                *flags, node['base']['name'], node['name']],
                               cwd=node_worktree)
                    if proc.returncode != 0:
                        return False

    # merge dependencies
    for dep in node['merge']:
        if not exists and node['base'] is dep:
            # branch has been bootstrapped and dependency is the base
            # itself, skip the merge (it's useless)
            continue
        elif not exists or dep['state']['dirty']:
            # branch is new or dependency has been updated earlier on,
            # there's no need to peform another check: we need to merge
            pass
        elif not needs_merge(node['name'], dep['name']):
            continue

        flags = node['flags']['merge'][dep['name']]
        if merge_ff is not None:
            flags = ['--ff' if merge_ff else '--no-ff'] + flags

        log(logging.INFO, 'merging {} into {}{}'.format(
            color_node(dep), color_node(node),
            branch_path_suffix(node, toplevel_dir)) + using_flags(flags))
        if not dry_run:
            proc = run(['git', 'merge', '-q', '--rerere-autoupdate',
                        *flags, '--no-edit', dep['name']],
                       cwd=node_worktree)
            if proc.returncode == 1:
                # directly attempt to autocommit in case rerere was successful
                proc = run(['git', 'commit', '-q', '--no-edit'],
                           cwd=node_worktree, stderr=sp.DEVNULL)
                if proc.returncode == 0:
                    log(logging.WARN, 'automatic merge resolution successful')
            if proc.returncode != 0:
                return False

    return True


def check_pending(git_dir):
    if os.path.exists(os.path.join(git_dir, 'MERGE_HEAD')):
        error('merge in progress, refusing to continue')
        return True
    elif os.path.exists(os.path.join(git_dir, 'rebase-apply')):
        error('rebase in progress, refusing to continue')
        return True
    elif os.path.exists(os.path.join(git_dir, 'BISECT_LOG')):
        error('bisect in progress, refusing to continue')
        return True
    return False


def edit(path):
    if os.path.isfile(path):
        print('opening assembly file {}'.format(compact_relpath(path)))
    else:
        print('opening new assembly file {}'.format(compact_relpath(path)))

    # fetch the default editor
    editor = os.environ.get('VISUAL')
    if editor is None:
        editor = os.environ.get('EDITOR', 'vi')

    # handle commands with flags
    editor = shlex.split(editor)
    try:
        returncode = sp.run([*editor, path], check=False).returncode
    except OSError as e:
        error("can't execute editor: " + str(e))
        return ExitStatus.ERROR

    return returncode


class ExitStatus(IntEnum):
    SUCCESS   = 0
    ERROR     = 1
    CONFIG    = 2
    GITCONFIG = 3


def get_targets(cli_targets, set_targets, nodes):
    # initial target list
    if len(cli_targets) == 0:
        patterns = set_targets
    else:
        patterns = [branch.encode(sys.getdefaultencoding(), 'surrogateescape')
                    for branch in cli_targets]

    # expand patterns
    targets = []
    for target in patterns:
        if not branch_is_pattern(target):
            targets.append(target)
        else:
            try:
                target_exp = list(expand_branches(target, nodes))
            except re.error as e:
                error(str(e))
                return ExitStatus.ERROR
            if len(target_exp) == 0:
                error('pattern {} in argument does not match any node'.format(
                    branch_str(target)))
                return None
            targets.extend(target_exp)

    # check targets against known nodes
    for branch in targets:
        if branch not in nodes:
            error('unknown target branch {}'.format(branch_str(branch)))
            return None

    return targets


def main(argv):
    ap = argparse.ArgumentParser(description=APP_DSC)
    ap.add_argument('-f', '--config', metavar='PATH',
                    help='explicit path to assembly file')
    ap.add_argument('-c', '--create', action='store_true',
                    help='create required branches')
    ap.add_argument('--recreate', action='store_true',
                    help='recreate base branches (implies -c, destructive!)')
    ap.add_argument('-n', '--dry-run', action='store_true',
                    help='show what assemble would do')
    g = ap.add_mutually_exclusive_group()
    g.add_argument('-a', '--assemble', action='store_true',
                   help='assemble the target branches')
    g.add_argument('-e', '--edit', action='store_true',
                   help='spawn an editor on the current assembly file')
    ap.add_argument('-v', '--verbose', default=0, action='count',
                    help='increase verbosity')
    ap.add_argument('--version', action='version', version=APP_VER)
    ap.add_argument('--color', choices=['auto', 'always', 'never'],
                    default='auto', help='set terminal coloring mode')
    g = ap.add_mutually_exclusive_group()
    g.add_argument('target', nargs='*', default=[],
                   help='branch to update/display')
    g.add_argument('--all', action='store_true',
                   help='override assembly: act on all branches')
    g.add_argument('--clear', action='store_true',
                   help='reset any pending git-assembler state')
    args = ap.parse_args(argv[1:])

    # logging
    levels = (logging.WARNING, logging.INFO, logging.DEBUG, logging.TRACE)
    logging.basicConfig(level=levels[min(len(levels)-1, args.verbose)],
                        format='{}: %(message)s'.format(APP_SIG))

    # color mode
    global COLOR_MODE
    if args.color == 'always':
        COLOR_MODE = True
    elif args.color == 'never' or \
         'NO_COLOR' in os.environ or \
         os.environ.get('TERM', 'dumb') == 'dumb':
        COLOR_MODE = False
    else:
        COLOR_MODE = sys.stdout.isatty()

    # repository paths
    toplevel_dir = repo_toplevel()
    if toplevel_dir is None:
        return ExitStatus.GITCONFIG
    git_dir = repo_git_dir()
    common_dir = repo_common_dir()
    if common_dir is None:
        return ExitStatus.GITCONFIG

    # read git configuration
    git_conf = read_git_config()
    if git_conf is None:
        return ExitStatus.GITCONFIG

    # past invocation state (if any)
    if args.clear:
        clear_state(common_dir)
    state = read_state(common_dir)
    if state is None:
        return ExitStatus.ERROR

    # locate (and edit) current assembly path
    if args.config:
        state['assembly_path'] = os.path.realpath(args.config)
    elif 'assembly_path' not in state:
        state['assembly_path'] = assembly_path(toplevel_dir, common_dir)

    if args.edit:
        return edit(state['assembly_path'])

    if not os.path.isfile(state['assembly_path']):
        error('no assembly instructions')
        return ExitStatus.CONFIG
    assembly_relpath = compact_relpath(state['assembly_path'])
    debug('reading instructions from {}'.format(assembly_relpath))

    # build the list of nodes and resulting graph
    branches = branch_list()
    if branches is None:
        return ExitStatus.ERROR
    res = parse_assembly(assembly_relpath, branches)
    if res is None:
        return ExitStatus.CONFIG
    nodes, settings = res

    # construct/check the list of targets
    if args.all or (len(args.target) == 0 and len(settings['target']) == 0):
        targets = None
    else:
        targets = get_targets(args.target, settings['target'], nodes)
        if targets is None:
            return ExitStatus.ERROR

    # construct the resulting graph
    graph = assembly_graph(nodes, targets)
    if graph is None:
        return ExitStatus.CONFIG
    if len(graph) == 0:
        error('nothing to do')
        return ExitStatus.CONFIG

    # recreate works just by switching all BASE branches to STAGE
    if args.recreate:
        args.create = True
        for node in nodes.values():
            if node['type'] == BranchType.BASE:
                node['type'] = BranchType.STAGE

    # update and check current state
    ordered_nodes = topo_sort(graph)
    update_state(ordered_nodes, graph, branches, args.recreate)

    if 'start_branch' in state:
        resuming = True
        if state['start_worktree'] == toplevel_dir:
            info('resuming interrupted assembly process')
        else:
            info('resuming interrupted assembly process from {}'.format(
                color_path(compact_relpath(state['start_worktree']))))
        state['current_branch'] = current_branch(state['start_worktree'])
    else:
        resuming = False
        state['current_branch'] = current_branch(toplevel_dir)
        state['start_worktree'] = toplevel_dir
        state['start_branch'] = state['current_branch']
    state['last_branch'] = state['current_branch']

    # exit early when possible
    if not args.assemble and not args.dry_run:
        dump_graph(graph, state, toplevel_dir)
        return ExitStatus.SUCCESS
    if not check_missing(ordered_nodes, args.create):
        return ExitStatus.ERROR
    if not check_dirty(ordered_nodes):
        if state['start_branch'] == state['last_branch']:
            info('already up to date')
            if not args.dry_run:
                clear_state(common_dir)
            return ExitStatus.SUCCESS

    # refuse to continue if any stateful git operation is pending
    if check_pending(git_dir):
        return ExitStatus.ERROR
    if not os.path.exists(state['start_worktree']):
        error('initial worktree {} disappeared'.format(
            color_path(compact_relpath(state['start_worktree']))))
        return ExitStatus.ERROR

    # save the initial state and assembly before it gets modified
    if not args.dry_run:
        save_state(common_dir, state)

    # perform the required operations
    for node in ordered_nodes:
        state['last_msg'] = None
        state['last_err'] = None
        if not update_node(node, state, toplevel_dir, args.dry_run, git_conf['assembler.mergeff']):
            if not args.dry_run:
                save_state(common_dir, state)
            if state['last_msg'] is not None:
                error('error while ' + state['last_msg'])
            if state['last_err'] is not None:
                print(state['last_err'], file=sys.stderr)
            if node['path'] is not None:
                warning('stopping at branch {} in {}'.format(
                    color_node(node), color_path(compact_relpath(node['path']))))
            else:
                if state['last_branch'] in nodes:
                    branch_name = color_node(nodes[state['last_branch']])
                else:
                    branch_name = branch_str(state['last_branch'])
                warning('stopping at branch {}'.format(branch_name))
            warning('fix/commit then re-run {}'.format(APP_SIG))
            return ExitStatus.ERROR

    # restore initial branch
    if state['start_branch'] != state['last_branch']:
        # the starting branch might no longer exist or be referenced in the nodes
        if state['start_branch'] in nodes:
            start_name = color_node(nodes[state['start_branch']])
        else:
            start_name = branch_str(state['start_branch'])
        if not args.dry_run and not branch_exists(state['start_branch']):
            logging.log(logging.WARNING, 'cannot restore initial branch {}'.format(start_name))
        else:
            level = logging.WARNING if resuming else logging.INFO
            if state['start_worktree'] == toplevel_dir:
                logging.log(level, 'restoring initial branch {}'.format(start_name))
            else:
                logging.log(level, 'restoring initial branch {} in {}'.format(
                    start_name, color_path(compact_relpath(state['start_worktree']))))
            if not args.dry_run:
                ret, err = switch_to_branch(state['start_branch'], state['start_worktree'])
                if ret != 0:
                    error('error restoring initial branch {}'.format(start_name))
                    print(err, file=sys.stderr)
                    return ExitStatus.ERROR

    if not args.dry_run:
        clear_state(common_dir)
    return ExitStatus.SUCCESS


if __name__ == '__main__':
    exit(main(sys.argv))
