bdm.template

#!/usr/bin/env bash
# BDM - A dotfile manager written in bash
# Copyright (C) 2021  Hu Sixu <husixu1@hotmail.com>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <https://www.gnu.org/licenses/>.
################################################################################

# shellcheck disable=SC1090
# shellcheck disable=SC2181

# Startup Checking #############################################################
################################################################################
# This script requires bash >= 4.3, since it uses `declare -n`
if [[ ${BASH_VERSINFO[0]} -lt 4 ]] ||
    [[ ${BASH_VERSINFO[0]} -eq 4 && ${BASH_VERSINFO[1]} -lt 3 ]]; then
    echo "This script requires Bash version >= 4.3"
    exit 1
fi

[[ $EUID -eq 0 ]] && {
    echo "This script cannot be run as root," \
        "as it might cause unexpected damage." >&2
    exit 1
}

BDM_PREFIX=$(
    cd "$(dirname "$(realpath "${BASH_SOURCE[0]}")")" || exit
    pwd
)
export BDM_PREFIX

# replaced by Makefile
BDM_LIBDIR="@BDM_LIBDIR@"
BDM_CONFDIR="@BDM_CONFDIR@"
export BDM_LIBDIR

# Init & Includes ##############################################################
################################################################################
source "$BDM_LIBDIR/utils.sh"
source "$BDM_LIBDIR/distro.sh"
source "$BDM_LIBDIR/read_ini.sh"
source "$BDM_LIBDIR/install.sh"

# Read Configs #################################################################
################################################################################
readonly configs=(
    "$HOME/.bdm/bdm.conf"
    "$LOCAL_CONFIG_DIR/bdm.conf"
    "$LOCAL_CONFIG_DIR/bdm/bdm.conf"
    "$BDM_CONFDIR/bdm.conf"
)

config=""
for f in "${configs[@]}"; do
    [[ -f "$f" ]] && {
        config="$f"
        read_ini --prefix CONF --booleans 0 "$config"
        break
    }
done
[[ -n $config ]] || {
    log:error "Cannot find config file"
    exit 1
}

# for lib/install.sh to store dotfile installation information
STORAGE_DIR="$LOCAL_CONFIG_DIR/bdm/.db"
mkdir -p "$STORAGE_DIR"
export STORAGE_DIR

# global variables
declare -a dotfile_dirs parsed_dotfile_dirs
read -ra dotfile_dirs <<<"${CONF__bdm__dotfile_dirs:-~/.config/bdm/dotfiles}"
for dotfile_dir in "${dotfile_dirs[@]}"; do
    parsed_dotfile_dirs+=("${dotfile_dir/#\~/$HOME}")
done
dotfile_dirs=("${parsed_dotfile_dirs[@]}")
unset parsed_dotfile_dirs

declare cache_dir="${CONF__bdm__cache_dir:-$HOME/.cache/bdm}"
cache_dir="${cache_dir/#\~/$HOME}"
mkdir -p "$cache_dir" || return 1

# Termux Support ###############################################################
################################################################################
# Fake a `sudo' command, since termux does not have a sudo command
[[ $DISTRO == "termux" ]] && {
    sudo() {
        while [[ $1 =~ ^- ]]; do shift; done
        "$@"
    }
    export -f sudo
}

# FUNCTIONS ####################################################################
################################################################################
readonly _OPTION_PATTERN='^--?[[:alnum:]][[:alnum:]-]*$'

main() {
    [[ $# -eq 0 ]] && {
        echo "$_HELP_MESSAGE"
        return 0
    }

    # Parse command line #######################################################
    ############################################################################
    # get command
    local cmd=$1
    shift

    # avoid updating cache when printing help/version
    case $cmd in
    -h | --help)
        echo "$_HELP_MESSAGE"
        return 0
        ;;
    -v | --version)
        echo "bdm @BDM_VERSION@"
        return 0
        ;;
    esac

    update_cache || return $?
    case $cmd in
    i*)
        # Install a package
        local -A install_options=(
            [depends]="${CONF__bdm__depends:-check}"
            [usermode]="${CONF__bdm__usermode:-false}"
            [holdsudo]=true
        )

        while [[ $1 =~ $_OPTION_PATTERN ]]; do
            case $1 in
            "-d" | "--depends")
                shift
                install_options[depends]="$1"
                ;;
            "-s" | "--skip-depends")
                install_options[depends]="skip"
                ;;
            "-c" | "--check-depends")
                install_options[depends]="check"
                ;;
            "-i" | "--install-depends")
                install_options[depends]="install"
                ;;
            "-u" | "--user-mode")
                install_options[usermode]=true
                ;;
            "-r" | "--root-mode")
                install_options[usermode]=false
                ;;
                # BDM refresh sudo periodically in the background,
                # this option turns this behavior off. It's currently only used
                # for testing (to workaround SimonKagstrom/kcov/issues/325).
            "-dhs" | "--dont-hold-sudo")
                install_options[holdsudo]=false
                ;;
            *)
                log:error "Option $1 unrecognized"
                return 1
                ;;
            esac
            shift
        done

        [[ ' skip check install ' == *" ${install_options[depends]} "* ]] || {
            log:error "-d | --depends must be followed by one of skip|check|install"
            return 1
        }

        [[ ' false true ' == *" ${install_options[usermode]} "* ]] || {
            log:error "-u | --usermode must be followed by either 'true' or 'false'"
            return 1
        }

        export ISROOT=true
        ${install_options[usermode]} && export ISROOT=false
        bdm:install "$@"
        ;;
    u*)
        # Uninstall a package
        while [[ $1 =~ $_OPTION_PATTERN ]]; do
            case $1 in
            *)
                log:error "Option $1 unrecognized"
                return 1
                ;;
            esac
            shift
        done
        bdm:uninstall "$@"
        ;;
    s*)
        # search packages
        local -A search_options=(
            [depends]=false
            [tags]=false
            [usermode]="$CONF__bdm__usermode"
        )

        while [[ $1 =~ $_OPTION_PATTERN ]]; do
            case $1 in
            '-t' | '--tags')
                search_options['tags']=true
                ;;
            '-d' | '--depends')
                search_options['depends']=true
                ;;
            *)
                log:error "Option $1 unrecognized"
                exit 1
                ;;
            esac
            shift
        done
        bdm:search "$@"
        ;;
    l*)
        # search packages
        local -A list_options=(
            [files]=false
        )

        while [[ $1 =~ $_OPTION_PATTERN ]]; do
            case $1 in
            '-f' | '--files')
                list_options['files']=true
                ;;
            *)
                log:error "Option $1 unrecognized"
                exit 1
                ;;
            esac
            shift
        done
        # list only installed packages
        bdm:list "$@"
        ;;
    n*)
        # search packages
        local -A new_options=(
            [usermode]=''
            [target_dir]=''
            [distros]=''
        )

        while [[ $1 =~ $_OPTION_PATTERN ]]; do
            case $1 in
            '-u' | '--usermode')
                new_options['usermode']=true
                ;;
            '-d' | '--distros')
                shift
                new_options[distros]+=":$1:"
                ;;
            '-t' | '--target-dir')
                shift
                new_options[target_dir]="$1"
                ;;
            *)
                log:error "Option $1 unrecognized"
                exit 1
                ;;
            esac
            shift
        done

        # create a new package
        bdm:new "$1"
        ;;
    *)
        log:error "Command '$cmd' not recognized. Run '${BASH_SOURCE[0]}' for help"
        exit 1
        ;;
    esac
}

# 'bdm:' namesapce avoids function name overwrites
bdm:install() {
    # Preparation install ######################################################
    # require root if not in usermode
    if ${install_options[holdsudo]}; then
        ${install_options[usermode]} || require_and_hold_root_access || return 1
    fi

    # dotfiles to install
    local -a dotfiles=()

    # filter a list of valid dotfiles
    mapfile -t dotfiles < <(filter_valid_dotfiles "$@")
    if [[ "${#dotfiles[@]}" -eq 0 ]]; then
        log:warning "No dotfile to install..."
        return 0
    fi

    # Parse dependency graph
    if [[ ${install_options[depends]} != 'skip' ]]; then
        # Check for dependency loop, including makedepends
        dependency_loop_detection "${dotfiles[@]}" || {
            log:error "Dependency checking failed"
            return 1
        }

        if [[ ${install_options[depends]} == 'install' ]]; then
            # add all dependency to 'dotfiles' and correct their order
            mapfile -t dotfiles < <(list_and_sort_dependencies "${dotfiles[@]}")
        fi
    fi

    echo "dotfiles to install: ${dotfiles[*]}"
    echo -n "Proceed? [Y/n]: "
    read -r ans
    [[ $ans == n ]] && return 0

    # Dotfile installation #####################################################
    for dotfile in "${dotfiles[@]}"; do
        log:info "Processing $dotfile ..."

        # 1. check for misisng dependencies
        if [[ ${install_options[depends]} != 'skip' ]]; then
            # 1. check if all dependencies in the 'check' array,
            # if dependency is not met, check if there's a entry in the
            # 'packages' array to install it
            local -a missing_deps=()
            local missing_deps_list
            missing_deps_list="$(check_depends "$dotfile")" || {
                log:error "Unable to meet dependency(s), aborting... "
                return 1
            }
            [[ -n $missing_deps_list ]] &&
                mapfile -t missing_deps <<<"$missing_deps_list"
        fi

        # 2. install misisng dependencies
        if [[ ${#missing_deps[@]} -gt 0 ]]; then
            if [[ ${install_options[depends]} == 'check' ]]; then
                log:error "dependency missing."
                return 1
            elif [[ ${install_options[depends]} == 'install' ]]; then
                # Don't use `install_depends ... || return $?' here, otherwise
                # all errexit flags in the install_depends function will be shadowed
                install_depends "$dotfile" "${missing_deps[@]}"
                [[ $? == 0 ]] || return 1
            fi
        fi

        # 3. install dotfiles
        (
            set -eo pipefail
            bootstrap_path="$(find_bootstrap_sh "$dotfile")" || return $?
            source "$bootstrap_path" >/dev/null

            if [[ $(type -t "bootstrap:__install") == "function" ]]; then
                bootstrap:__install
            else
                log:warning "'bootstrap:__install()' not defined in '$bootstrap_path', skipping."
            fi
        )
        [[ $? == 0 ]] || {
            log:warning "Failed installing $dotfile"
            return 1
        }

        # 4. evaluate post-install function
        local evaluate_func
        evaluate_func="$(
            set -eo pipefail
            export LOG_INDENT=4
            bootstrap_path="$(find_bootstrap_sh "$dotfile")" || return 1
            source "$bootstrap_path" >/dev/null

            if [[ $(type -t "bootstrap:evaluate") == "function" ]]; then
                declare -pf bootstrap:evaluate
            fi
        )"

        if [[ -n ${evaluate_func} ]]; then
            log:info "Executing bootstrap:evaluate function of $dotfile"
            eval "${evaluate_func}"

            bootstrap:evaluate || {
                log:error "$dotfile: Failed executing the bootstrap:evaluate function. " \
                    "Aborting to avoid subsequent failures..."
                return 1
            }

            unset bootstrap:evaluate
        fi
    done

    for dotfile in "${dotfiles[@]}"; do
        (
            set -eo pipefail
            bootstrap_path="$(find_bootstrap_sh "$dotfile")" || return $?
            source "$bootstrap_path" >/dev/null

            if [[ $(type -t "bootstrap:post_install") == "function" ]]; then
                bootstrap:post_install
            else
                exit 0
            fi
        )
        [[ $? == 0 ]] || {
            log:warning "Failed to execute bootstrap:post_install of $dotfile"
            return 1
        }
    done
}

bdm:uninstall() {
    # dotfiles to uninstall
    local -a dotfiles=()

    # filter a list of valid dotfiles
    mapfile -t dotfiles < <(filter_valid_dotfiles "$@")
    if [[ "${#dotfiles[@]}" -eq 0 ]]; then
        log:warning "No dotfile to uninstall..."
        return 0
    fi

    for dotfile in "${dotfiles[@]}"; do
        log:info "Processing $dotfile ..."

        # uninstall dotfiles
        (
            set -eo pipefail
            bootstrap_path="$(find_bootstrap_sh "$dotfile")" || return $?
            source "$bootstrap_path" >/dev/null

            if [[ $(type -t "bootstrap:__uninstall") == "function" ]]; then
                bootstrap:__uninstall >/dev/null
            else
                log:warning "'bootstrap:__uninstall()' not defined in '$dotfile/bootstrap.sh', skipping."
            fi
        )
        [[ $? == 0 ]] || {
            log:warning "Failed uninstalling $dotfile"
            return 1
        }
    done
}

bdm:search() {
    # dotfiles to search
    local -a dotfiles
    mapfile -t dotfiles < <(filter_valid_dotfiles "$@")
    if [[ "${#dotfiles[@]}" -eq 0 ]]; then
        log:warning "No result ..."
        return 0
    fi

    if ${search_options[depends]}; then
        # Check for dependency loop, including makedepends
        dependency_loop_detection "${dotfiles[@]}" || {
            log:error "Dependency checking failed"
            return 1
        }
    fi

    for dotfile in "${dotfiles[@]}"; do
        echo -e "\033[1m$dotfile\033[0m"
        if "${search_options[tags]}"; then
            local -a tags
            mapfile -t tags < <(dotfile_tags "$dotfile")
            echo "  Tags: ${tags[*]}"
        fi
        if "${search_options[depends]}"; then
            local -a deps
            mapfile -t deps < <(dotfile_deps "$dotfile")
            echo "  Deps: ${deps[*]}"
        fi
        echo
    done
}

bdm:list() {
    # dotfiles to list
    local -a dotfiles
    local -A dotfiles_set
    mapfile -t dotfiles < <(filter_valid_dotfiles "$@")
    for dotfile in "${dotfiles[@]}"; do
        dotfiles_set["$dotfile"]=1
    done

    # installed dotfiles
    local dotfile_name
    local -a installed_dotfiles
    for db_file in "$STORAGE_DIR"/*.db; do
        if [[ -f "$db_file" ]]; then
            dotfile_name="$(basename "${db_file%.db}")"
            local -gA tmp_db=()
            db:load "$db_file" tmp_db
            if [[ "${#tmp_db[@]}" -gt 0 && -n "${dotfiles_set["$dotfile_name"]}" ]]; then
                installed_dotfiles+=("$dotfile_name")
            fi
        fi
    done

    # list all entries
    for dotfile in "${installed_dotfiles[@]}"; do
        echo -e "\033[1m$dotfile\033[0m"
        if "${list_options[files]}"; then
            local -gA tmp_db=()
            db:load "$STORAGE_DIR/$dotfile.db" tmp_db
            for rec in "${tmp_db[@]}"; do
                local -A record=()
                eval "$rec"
                if [[ "${record[hash]}" == "directory" ]]; then
                    echo "  Dir:  ${record[target]}"
                elif [[ "${record[hash]}" == "symlink" ]]; then
                    echo "  Link: ${record[source]} --> ${record[target]}"
                else
                    echo "  File: ${record[source]} --> ${record[target]}"
                fi
            done
            echo
        fi
    done
}

# $@: list of dotfiles or tags. 'all' or 't:all' for every valid dotfiles
# print: list of valid dotfiles, one per line
filter_valid_dotfiles() {
    local -a items=("$@")
    [[ $# -eq 1 && ($1 == "all" || $1 == "t:all") ]] && {
        items=()
        for dir in "${dotfile_dirs[@]}"; do
            if [[ -d "$dir" ]]; then
                mapfile -t list < <(ls "$dir")
                items+=("${list[@]}")
            else
                log:warning "dotfiles dir '$dir' does not exist"
            fi
        done
    }

    # filter out invalid dotfiles and tags
    local -a valid_dotfiles=()
    local -a tags=()
    for item in "${items[@]}"; do
        if [[ "$item" =~ ^t: ]]; then
            tags+=("${item#t:}")
        else
            if find_dotfile_dir "$item" >/dev/null; then
                valid_dotfiles+=("$item")
            else
                tags+=("$item")
            fi
        fi
    done

    local -a extra_dotfiles=()
    mapfile -t extra_dotfiles <<<"$(tags_to_dotfiles "${tags[@]}")"
    [[ -n "${extra_dotfiles[*]}" ]] && valid_dotfiles+=("${extra_dotfiles[@]}")

    # return
    for dotfile in "${valid_dotfiles[@]}"; do
        echo "$dotfile"
    done | sort -u
}

require_and_hold_root_access() {
    # At least `sudo` is needed
    type sudo >/dev/null 2>&1 || {
        log:error "the 'sudo' program is needed for running this script"
        exit 1
    }

    # Require root privilege
    if sudo -v; then
        export ISROOT=true
    else
        log:warning "Require root failed."
        echo "All installation process will be done in user mode."
        echo -n "Those dotfiles that requires root are doomed to fail. Proceed? [y/N]: "
        read -r ans
        if [[ $ans != y ]]; then
            return 1
        fi
        export ISROOT=false
    fi

    # keep sudo credential cache up-to-date
    while true; do
        sleep 5
        sudo -n true
        kill -0 "$$" 2>/dev/null || exit
    done &
    pid=$!

    trap_add "kill -- $pid" SIGINT SIGTERM EXIT
}

# $1 dependency string
# print: <type> <name> <install-type> <install-name>, separated with space,
# can be read into variable with `read -r type name i_type i_name`
parse_dep_info() {
    local dep_check="${1%%::*}"
    if [[ "$1" == *::* ]]; then
        local dep_install="${1##*::}"
    else
        local dep_install=""
    fi

    local -A check_prefix_map=(
        ["v"]="virtual" ["fi"]="file" ["fu"]="function"
        ["d"]="dotfile" ["e"]="executable"
    )

    local dep_type=""
    local dep_name=""
    local number_virtual=0
    if [[ -z $dep_check ]]; then
        dep_type="virtual"
        dep_name="virtual-$number_virtual"
        ((++number_virtual))
    else
        local match_prefix=false
        for prefix in "${!check_prefix_map[@]}"; do
            if [[ $dep_check =~ ^${prefix}[[:alnum:]]*:[[:print:]]+$ ]]; then
                dep_type="${check_prefix_map[$prefix]}"
                dep_name="${dep_check#${prefix}*:}"
                match_prefix=true
                break
            fi
        done

        if ! $match_prefix; then
            if [[ $dep_check =~ ^[[:alnum:]]*:[[:print:]]+$ ]]; then
                dep_type="unknown"
                dep_name="unknown"
            else
                # If command not found, and bootstrap script for the dotfile
                # of the same name is found, treat as dotfile.
                # In all other cases still treat as executable.
                if ! command -v "$dep_check" >/dev/null 2>&1 &&
                    find_dotfile_dir "$dep_check" >/dev/null 2>&1; then
                    dep_type="dotfile"
                    dep_name="$dep_check"
                else
                    dep_type="executable"
                    dep_name="$dep_check"
                fi
            fi
        fi
    fi

    local -A install_prefix_map=(["s"]="system" ["u"]="user" ["f"]="function" ["a"]="aur")

    local install_type=""
    local install_name=""
    if [[ $dep_type == "dotfile" ]]; then
        # installation type and name is invalid for dotfiles
        install_type="_"
        install_name="_"
    elif [[ $dep_type == "executable" && -z "$dep_install" ]]; then
        # if item after `::` is not specified, and dep_type is executable,
        # treat as a system package with the of the same name
        install_type="system"
        install_name="${dep_check#*:}"
    elif [[ -z "$dep_install" ]]; then
        # if item after `::` is not specified, report error
        install_type="unspecified"
        install_name="unspecified"
    else
        local match_prefix=false
        for prefix in "${!install_prefix_map[@]}"; do
            if [[ $dep_install =~ ^${prefix}[[:alnum:]]*:[[:print:]]+$ ]]; then
                install_type="${install_prefix_map[$prefix]}"
                install_name="${dep_install#${prefix}*:}"
                match_prefix=true
                break
            fi
        done

        if ! $match_prefix; then
            if [[ $dep_install =~ ^[[:alnum:]]*:[[:print:]]+$ ]]; then
                install_type="unknown"
                install_name="unknown"
            else
                # if no prefix is detected, default to system package if $ISROOT is
                # set, otherwise default to usermode package
                if $ISROOT; then
                    install_type="system"
                else
                    install_type="user"
                fi
                install_name="${dep_install}"
            fi
        fi
    fi
    echo "$dep_type $dep_name $install_type $install_name"
}

# $@: dotfiles to install
dependency_loop_detection() {
    local -a exam_queue
    local -a exam_queue_level
    for dotfile in "$@"; do
        exam_queue+=("$dotfile")
        exam_queue_level+=("1")
    done

    # non-recursive DFS to find all dependency loops
    local -A deps_set
    local -a deps_stack # deps_stack[-1] is stack top
    while [[ ${#exam_queue[@]} -ne 0 ]]; do
        local cur_dotfile="${exam_queue[0]}"
        local cur_dotfile_level="${exam_queue_level[0]}"
        exam_queue=("${exam_queue[@]:1}")
        exam_queue_level=("${exam_queue_level[@]:1}")

        # set depends stack to correct level
        while [[ ${#deps_stack[@]} -ne $((cur_dotfile_level - 1)) ]]; do
            unset deps_set["${deps_stack[-1]}"]
            deps_stack=("${deps_stack[@]::${#deps_stack[@]}-1}")
        done

        # check for dependency loop
        if [[ -n ${deps_set[$cur_dotfile]} ]]; then
            local loop
            for depend in "${deps_stack[@]}"; do
                if [[ "$depend" == "$cur_dotfile" ]]; then
                    loop+="${depend} -> "
                else
                    loop+="$depend -> "
                fi
            done
            loop+="$cur_dotfile"
            log:error "Dependency loop detected: $loop"
            unset loop
            return 1
        fi

        # read all dependency of current dotfile
        if ! find_dotfile_dir "$cur_dotfile" >/dev/null; then
            local chain
            chain=$(printf "%s -> " "${deps_stack[@]}")
            chain+="$cur_dotfile"
            log:error "Dependency chain: $chain," \
                "but 'bootstrap.sh' script for '$cur_dotfile' does not exist."
            return 1
        fi

        local -a depends
        mapfile -t depends < <(extract_dotfile_depends "$cur_dotfile")

        if [[ ${#depends[@]} -ne 0 ]]; then
            exam_queue=("${depends[@]}" "${exam_queue[@]}")
            for ((i = 0; i < ${#depends[@]}; ++i)); do
                exam_queue_level=("$((cur_dotfile_level + 1))" "${exam_queue_level[@]}")
            done
            deps_stack+=("$cur_dotfile")
            deps_set["$cur_dotfile"]=1
        fi
    done
    return 0
}

# $@: all dotfiles to install
list_and_sort_dependencies() {
    local -a exam_queue
    for dotfile in "$@"; do
        exam_queue+=("$dotfile")
    done

    # Use BFS to get the topological order.
    # Yeah I know this function can be merged with dependency_loop_detection,
    # but for the sake of simplicity and readability I'll just use BFS here.
    for ((i = 0; i < ${#exam_queue[@]}; ++i)); do
        local cur_dotfile="${exam_queue[$i]}"
        local -a depends
        mapfile -t depends < <(extract_dotfile_depends "$cur_dotfile")
        if [[ ${#depends[@]} -ne 0 ]]; then
            exam_queue+=("${depends[@]}")
        fi
    done

    local -A unique_set
    for ((i = 1; i <= ${#exam_queue[@]}; ++i)); do
        if [[ -z ${unique_set[${exam_queue[-$i]}]} ]]; then
            unique_set[${exam_queue[-$i]}]=1
            echo "${exam_queue[-$i]}"
        fi
    done
}

# Extract `d*:` types dependencies from dotfiles' bootstrap file
# $1: name of the dotfile
extract_dotfile_depends() {
    # avoid variable contamination of parent shell
    local -a deps=()
    mapfile -t deps < <(dotfile_deps "$1")
    if [[ "${#deps[@]}" -eq 0 ]]; then return 0; fi

    for dep in "${deps[@]}"; do
        read -r dep_type dep_name _ _ <<<"$(parse_dep_info "$dep")"
        if [[ $dep_type == "dotfile" ]]; then
            echo "$dep_name"
        fi
    done
}

# $1 dotfile dir name
# ${install_options[depends]} affects the behavior of this function
# print: a list of missing depends, one per line
# return: 0 for success, 1 for fail
check_depends() {
    (
        # run in subshell. exit when any error happens
        set -eo pipefail

        unset tags
        local -a deps=()
        mapfile -t deps <<<"$(dotfile_deps "$1")"
        if [[ -z ${deps[*]} ]]; then return 0; fi

        # these variables are defined in subshell and
        # does not interfere with the variables outside
        declare -a missing_deps=()

        # Check dependency files before installing
        for dep in "${deps[@]}"; do
            read -r dep_type dep_name _ _ <<<"$(parse_dep_info "$dep")"
            case "$dep_type" in
            'file')
                # test if file exists
                if [[ ! -e $dep_name ]]; then
                    missing_deps+=("$dep")
                fi
                ;;
            'virtual')
                # item is virtual, skip checking, but list as install
                if [[ ${install_options[depends]} == 'install' ]]; then
                    missing_deps+=("$dep")
                fi
                ;;
            'function')
                # if dep_type is function, update corresponding functions
                bootstrap_path="$(find_bootstrap_sh "$1")" || return 1
                source "$bootstrap_path" >/dev/null

                # Use a function to decide if item exists
                set +e
                (
                    set -e
                    ${dep_name#fu*:}
                )
                if [[ $? != 0 ]]; then
                    missing_deps+=("$dep")
                fi
                set -e
                ;;
            'executable')
                # test if executable exists in $PATH
                if ! command -v "$dep_name" >/dev/null 2>&1; then
                    missing_deps+=("$dep")
                fi
                ;;
            'dotfile')
                : # Skip. dotfile dependency is already handled before checking.
                ;;
            'unknown')
                log:error "$dotfile: unrecognized dependency prefix in '$dep'"
                return 1
                ;;
            esac
        done

        if [[ ${#missing_deps[@]} -gt 0 ]]; then
            log:warning "$dotfile: Dependency missing: ${missing_deps[*]}" >&2
        fi

        local able_to_meet_dependency=true
        for dep in "${missing_deps[@]}"; do

            # pass to outer shell
            echo "$dep"

            # check if this dependency can be met
            read -r _ _ install_type install_name <<<"$(parse_dep_info "$dep")"
            if [[ $install_type == 'unknown' || \
                $install_type == 'unspecified' ]]; then
                log:error "$dotfile: Dependency '$dep': installation method $install_type."
                able_to_meet_dependency=false
            fi
        done

        $able_to_meet_dependency
    )
}

# $1: dotfile dir name
# ${@:1}: a list of missing deps in the `deps` array
# return: 0 for success, 1 for fail
install_depends() {

    local dotfile=$1
    shift
    local -a missing_deps=("$@")
    # 2. install all the missing dependencies
    (
        set -eo pipefail
        unset deps

        for dep in "${missing_deps[@]}"; do
            read -r _ _ install_type install_name <<<"$(parse_dep_info "$dep")"
            case $install_type in
            'function')
                install_pkg_command="${install_name}"
                # update functions if install_type is functions
                bootstrap_path="$(find_bootstrap_sh "$dotfile")" || return 1
                source "$bootstrap_path" >/dev/null 2>&1
                ;;
            'system')
                # package should be installed through package manager.
                install_pkg_command="install_system_package_$DISTRO ${install_name}"
                ;;
            'user')
                install_pkg_command="install_userland_package_pkgsrc ${install_name}"
                ;;
            'aur')
                install_pkg_command="install_aur_package ${install_name}"
                ;;
            esac

            # package should be installed through function, in a subshell,
            # so that set -e works correctly (both "exceptions" and returned
            # error code are captured)
            # We have to use this crooked way to simulate try-catch in an errexit environment ...
            # see https://stackoverflow.com/questions/29532904/bash-subshell-errexit-semantics
            set +e
            (
                set -e
                $install_pkg_command
            )
            [[ $? == 0 ]] || {
                log:error "$dotfile: Failed to process dependency $dep. Aborting ..."
                return 1
            }
            set -e
        done
    )
}

bdm:new() {
    [[ -z $1 ]] && {
        log:error "Please specify a name."
        return 1
    }

    local old_dir
    if old_dir="$(find_dotfile_dir "$1")"; then
        log:error "$1 already exists ($old_dir)"
        return 1
    fi

    log:info "Creating package '$1'"
    install_dir="${dotfile_dirs[0]}"
    if [[ ${#dotfile_dirs[@]} -eq 0 ]]; then
        log:error "'dotfile_dirs' not specified in config file."
    elif [[ ${#dotfile_dirs[@]} -ge 1 ]]; then
        if [[ -n "${new_options[target_dir]}" ]]; then
            # test if the specified dir is one of the configured dirs ...
            for dir in "${dotfile_dirs[@]}"; do
                local dir_found=false
                if [[ "$dir" -ef "${new_options[target_dir]}" ]]; then
                    dir_found=true
                    install_dir="$dir"
                fi
            done
            # ... if not, report erro and exit
            if ! $dir_found; then
                log:error "'${new_options[target_dir]}' invalid. " \
                    "Please specify one of the following directory:"
                for dir in "${dotfile_dirs[@]}"; do echo "  $dir"; done
                return 1
            fi
        else
            # if target dir not specified, ask interactively
            log:info "Select one of the following directories to put the new dotfile package:"
            for i in $(seq "${#dotfile_dirs[@]}"); do
                echo "$i: ${dotfile_dirs[$((i - 1))]}"
            done
            while true; do
                echo -n "Please specify a number [1-${#dotfile_dirs[@]}], (default 1, 'q' to quit): "
                read -r ans
                if [[ -z $ans ]]; then
                    break
                elif [[ $ans == 'q' ]]; then
                    return 0
                elif [[ -n ${dotfile_dirs["$((ans - 1))"]} ]]; then
                    install_dir=${dotfile_dirs["$((ans - 1))"]}
                    break
                else
                    log:warning "Please sepcify a valid number."
                fi
            done
        fi
    fi

    mkdir -p "$install_dir/$1"
    NON_ROOT="${new_options[usermode]}" \
        DEBIAN="$([[ ${new_options[distros]} == :debian: ]] && echo true)" \
        TERMUX="$([[ ${new_options[distros]} == :termux: ]] && echo true)" \
        source "$BDM_LIBDIR/templates/gen_bootstrap.sh" >"$install_dir/$1/bootstrap.sh"
    if command -v "$EDITOR" >/dev/null 2>&1; then
        $EDITOR "$install_dir/$1/bootstrap.sh"
    else
        log:info "\$EDITOR not set, template copied to $install_dir/$1"
    fi
}

# find the directory of the dotfile
# $1: name of the dotfile
# print: absolute path to the dotfile dir
# return: 1 if not found
find_dotfile_dir() {
    for dir in "${dotfile_dirs[@]}"; do
        if [[ -d "$dir/$1" && -f \
            "$dir/$1/bootstrap.sh" ]]; then
            echo "$dir/$1"
            return 0
        fi
    done
    return 1
}

find_bootstrap_sh() {
    # $1: name of the dotfile
    # print: absolute path to the dotfile dir
    # return: 1 if not found
    dir=$(find_dotfile_dir "$1") || {
        log:error "Cannot find bootstrap.sh for $1"
        return 1
    }
    echo "$dir/bootstrap.sh"
}

# Dotfile Caches ###############################################################
################################################################################

# create cache dir if not exists
if [[ ! -d $cache_dir ]]; then
    mkdir -p "$cache_dir" || {
        log:error "Cannot create cache dir '$cache_dir'"
        exit 1
    }
fi

# dotfile dependency arrays
# key: dotfile name
# value: dotfile hash value
declare -A __dotfile_hashs
# dotfile dependency arrays
# key: dotfile name
# value: declare command of the tags list of this dotfile
declare -A __dotfile_tags
# dotfile dependency arrays
# key: dotfile name
# value: declare command of the dependencies list
declare -A __dotfile_deps
# dotfile options
# key: dotfile name
# value: declare command of the option dict
declare -A __dotfile_opts

# update tags of all dotfiles packages
update_cache() {
    # read in old tags file
    local cache_file="${cache_dir}/dotfiles.cache"
    [[ -f "$cache_file" ]] && {
        local cmd=""
        while read -r cmd; do
            eval "${cmd/#declare /declare -g }"
        done <"$cache_file"
    }

    local -A new_hashs=()
    local -A new_tags=()
    local -A new_opts=()
    local -A new_deps=()

    # decide which dotfiles to preserve and which to update
    mapfile -t dotfiles < <(filter_valid_dotfiles "t:all")
    for dotfile in "${dotfiles[@]}"; do
        bootstrap_path="$(find_bootstrap_sh "$dotfile")" || return $?
        new_hash="$(md5sum "$bootstrap_path" | cut -d' ' -f1)"

        # if new has is equal to old hash, we need further judgement
        if [[ "$new_hash" == "$(dotfile_hash "$dotfile")" ]]; then
            local -A opts=()
            eval "${__dotfile_opts["$dotfile"]}"
            for opt in "${!opts[@]}"; do
                if [[ "${opts["$opt"]}" == "${!opt}" ]]; then
                    dotfile_unchanged=false
                    break
                fi
            done

            if $dotfile_unchanged; then
                # copy old metas to new metas
                new_hashs["$dotfile"]="${__dotfile_hashs["$dotfile"]}"
                new_opts["$dotfile"]="${__dotfile_opts["$dotfile"]}"
                new_deps["$dotfile"]="${__dotfile_deps["$dotfile"]}"
                new_tags["$dotfile"]="${__dotfile_tags["$dotfile"]}"
                continue
            fi
        fi

        # get new metadatas
        local -a cmds=()
        mapfile -t cmds < <(
            # ignore any errors when parsing tags, otherwise some options
            # may cause parsing failure. Don't use set -e here.
            declare -a tags=()
            declare -a deps=()
            unset opts
            declare -a opts=()

            source "$bootstrap_path" >/dev/null 2>&1
            export -n tags
            export -n deps
            export -n opts

            declare -p tags
            declare -p deps

            # prase and print opts dict
            declare -A __opts_dict=()
            for opt in "${opts[@]}"; do
                __opts_dict["$opt"]="${!opt}"
            done
            __opts_cmd="$(declare -p __opts_dict)"
            echo "${__opts_cmd/ __opts_dict/ opts}"
        )
        if [[ "${#cmds[@]}" -eq 0 ]]; then
            log:warning "'$dotfile' can't be parsed given current config, using empty metadata instead."
            new_hashs["$dotfile"]="$new_hash"
            new_tags["$dotfile"]="declare -a tags=()"
            new_deps["$dotfile"]="declare -a deps=()"
            new_opts["$dotfile"]="declare -A opts=()"
        else
            new_hashs["$dotfile"]="$new_hash"
            new_tags["$dotfile"]="${cmds[0]}"
            new_deps["$dotfile"]="${cmds[1]}"
            new_opts["$dotfile"]="${cmds[2]}"
        fi
    done

    __dotfile_hashs=()
    __dotfile_tags=()
    __dotfile_opts=()
    __dotfile_deps=()
    for dotfile in "${!new_hashs[@]}"; do
        __dotfile_hashs["$dotfile"]="${new_hashs["$dotfile"]}"
        __dotfile_tags["$dotfile"]="${new_tags["$dotfile"]}"
        __dotfile_deps["$dotfile"]="${new_deps["$dotfile"]}"
        __dotfile_opts["$dotfile"]="${new_opts["$dotfile"]}"
    done

    {
        declare -p __dotfile_hashs
        declare -p __dotfile_tags
        declare -p __dotfile_deps
        declare -p __dotfile_opts
    } >|"$cache_file"
}

# read deps from cache
# $1: name of the dotfile
dotfile_hash() {
    echo "${__dotfile_hashs["$1"]}"
}

# read deps from cache
# $1: name of the dotfile
dotfile_deps() {
    declare -a deps=()
    eval "${__dotfile_deps["$1"]}"
    for dep in "${deps[@]}"; do
        echo "$dep"
    done
}

# read deps from cache
# $1: name of the dotfile
dotfile_tags() {
    declare -a tags=()
    eval "${__dotfile_tags["$1"]}"
    for tag in "${tags[@]}"; do
        echo "$tag"
    done
}

# read existing opts from cache
# echo: opt_name="opt_value" ..., one per line. This can be read into an array
# and passed to the 'env'  command
dotfile_opts() {
    declare -a opts=()
    eval "${__dotfile_opts["$1"]}"
    for opt in "${!opts[@]}"; do
        printf "%s=%q\n" "$opt" "${opts["$opt"]}"
    done
}

# find dotfiles trough tags
# $@: tags
tags_to_dotfiles() {
    for dotfile in "${!__dotfile_hashs[@]}"; do
        local dotfile_tags=()
        mapfile -t dotfile_tags < <(dotfile_tags "$dotfile")
        for tag in "$@"; do
            if [[ " ${dotfile_tags[*]} " == *" $tag "* ]]; then
                echo "$dotfile"
                break
            fi
        done
    done
}

# from https://stackoverflow.com/questions/3338030/multiple-bash-traps-for-the-same-signal#answer-7287873
trap_add() {
    trap_add_cmd=$1
    shift || log:error "${FUNCNAME[0]} usage error"
    for trap_add_name in "$@"; do
        trap -- "$(
            # get existing trap command from output
            extract_trap_cmd() { printf '%s\n' "${3:-:}"; }
            # print existing trap command with newline
            eval "extract_trap_cmd $(trap -p "${trap_add_name}")"
            # print the new trap command
            printf '%s\n' "${trap_add_cmd}"
        )" "${trap_add_name}" || log:error "unable to add to trap ${trap_add_name}"
    done
}

# Help Messages ################################################################
################################################################################

_HELP_MESSAGE="\
SYNOPSIS
    ${BASH_SOURCE[0]} COMMAND [OPTIONS] <name>|[t:]<tag>|all...

    ${BASH_SOURCE[0]} i -i t:all
    ${BASH_SOURCE[0]} install vim git
    ${BASH_SOURCE[0]} uninstall git
    ${BASH_SOURCE[0]} search -t -d vim tmux
    ${BASH_SOURCE[0]} list -f t:all
    ${BASH_SOURCE[0]} new zsh

COMMAND & OPTIONS
    i*, install:
        -d <DEP_POLICY>, --depends <DEP_POLICY>
        -s, --skip-depends
        -c, --check-depends
        -i, --install-depends
        -u, --user-mode
        -r, --root-mode

    u*, uninstall
        No options available

	s*, search
        -t, --tags
        -d, --depends

    l*, list
        -f, --files

    n*, new
        -u, --usermode
        -d <DISTRO>, --distro <DISTRO>
        -t <DIR>, --target-dir <DIR>
"

main "$@"