Makefile: Split build into bin and obj directories

This also moves the main binary from ./bfs to ./bin/bfs, and ./tests.sh
to ./tests/tests.sh, with the goal of keeping the repository root clean.

1 files changed, 3433 insertions, 0 deletions

diff --git a/tests/tests.sh b/tests/tests.sh
new file mode 100755
index 0000000..434e058
--- /dev/null
+++ b/tests/tests.sh
@@ -0,0 +1,3433 @@
+#!/usr/bin/env bash
+
+############################################################################
+# bfs                                                                      #
+# Copyright (C) 2015-2022 Tavian Barnes <tavianator@tavianator.com>        #
+#                                                                          #
+# Permission to use, copy, modify, and/or distribute this software for any #
+# purpose with or without fee is hereby granted.                           #
+#                                                                          #
+# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES #
+# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         #
+# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  #
+# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   #
+# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    #
+# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  #
+# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           #
+############################################################################
+
+set -eP
+umask 022
+
+export LC_ALL=C
+export TZ=UTC0
+
+export ASAN_OPTIONS="abort_on_error=1"
+export LSAN_OPTIONS="abort_on_error=1"
+export MSAN_OPTIONS="abort_on_error=1"
+export TSAN_OPTIONS="abort_on_error=1"
+export UBSAN_OPTIONS="abort_on_error=1"
+
+export LS_COLORS=""
+unset BFS_COLORS
+
+if [ -t 1 ]; then
+    BLD=$(printf '\033[01m')
+    RED=$(printf '\033[01;31m')
+    GRN=$(printf '\033[01;32m')
+    YLW=$(printf '\033[01;33m')
+    BLU=$(printf '\033[01;34m')
+    MAG=$(printf '\033[01;35m')
+    CYN=$(printf '\033[01;36m')
+    RST=$(printf '\033[0m')
+fi
+
+UNAME=$(uname)
+
+if command -v capsh &>/dev/null; then
+    if capsh --has-p=cap_dac_override &>/dev/null || capsh --has-p=cap_dac_read_search &>/dev/null; then
+	if [ -n "$BFS_TRIED_DROP" ]; then
+            cat >&2 <<EOF
+${RED}error:${RST} Failed to drop capabilities.
+EOF
+
+	    exit 1
+	fi
+
+        cat >&2 <<EOF
+${YLW}warning:${RST} Running as ${BLD}$(id -un)${RST} is not recommended.  Dropping ${BLD}cap_dac_override${RST} and
+${BLD}cap_dac_read_search${RST}.
+
+EOF
+
+        BFS_TRIED_DROP=y exec capsh \
+            --drop=cap_dac_override,cap_dac_read_search \
+            --caps=cap_dac_override,cap_dac_read_search-eip \
+            -- "$0" "$@"
+    fi
+elif [ "$EUID" -eq 0 ]; then
+    UNLESS=
+    if [ "$UNAME" = "Linux" ]; then
+	UNLESS=" unless ${GRN}capsh${RST} is installed"
+    fi
+
+    cat >&2 <<EOF
+${RED}error:${RST} These tests expect filesystem permissions to be enforced, and therefore
+will not work when run as ${BLD}$(id -un)${RST}${UNLESS}.
+EOF
+    exit 1
+fi
+
+function usage() {
+    local pad=$(printf "%*s" ${#0} "")
+    cat <<EOF
+Usage: ${GRN}$0${RST} [${BLU}--bfs${RST}=${MAG}path/to/bfs${RST}] [${BLU}--posix${RST}] [${BLU}--bsd${RST}] [${BLU}--gnu${RST}] [${BLU}--all${RST}] [${BLU}--sudo${RST}]
+       $pad [${BLU}--stop${RST}] [${BLU}--noclean${RST}] [${BLU}--update${RST}] [${BLU}--verbose${RST}[=${BLD}LEVEL${RST}]] [${BLU}--help${RST}]
+       $pad [${BLD}test_*${RST} [${BLD}test_*${RST} ...]]
+
+  ${BLU}--bfs${RST}=${MAG}path/to/bfs${RST}
+      Set the path to the bfs executable to test (default: ${MAG}./bin/bfs${RST})
+
+  ${BLU}--posix${RST}, ${BLU}--bsd${RST}, ${BLU}--gnu${RST}, ${BLU}--all${RST}
+      Choose which test cases to run (default: ${BLU}--all${RST})
+
+  ${BLU}--sudo${RST}
+      Run tests that require root
+
+  ${BLU}--stop${RST}
+      Stop when the first error occurs
+
+  ${BLU}--noclean${RST}
+      Keep the test directories around after the run
+
+  ${BLU}--update${RST}
+      Update the expected outputs for the test cases
+
+  ${BLU}--verbose${RST}=${BLD}commands${RST}
+      Log the commands that get executed
+  ${BLU}--verbose${RST}=${BLD}errors${RST}
+      Don't redirect standard error
+  ${BLU}--verbose${RST}=${BLD}skipped${RST}
+      Log which tests get skipped
+  ${BLU}--verbose${RST}=${BLD}tests${RST}
+      Log all tests that get run
+  ${BLU}--verbose${RST}
+      Log everything
+
+  ${BLU}--help${RST}
+      This message
+
+  ${BLD}test_*${RST}
+      Select individual test cases to run
+EOF
+}
+
+DEFAULT=yes
+POSIX=
+BSD=
+GNU=
+ALL=
+SUDO=
+STOP=
+CLEAN=yes
+UPDATE=
+VERBOSE_COMMANDS=
+VERBOSE_ERRORS=
+VERBOSE_SKIPPED=
+VERBOSE_TESTS=
+EXPLICIT=
+
+enabled_tests=()
+
+for arg; do
+    case "$arg" in
+        --bfs=*)
+            BFS="${arg#*=}"
+            ;;
+        --posix)
+            DEFAULT=
+            POSIX=yes
+            ;;
+        --bsd)
+            DEFAULT=
+            POSIX=yes
+            BSD=yes
+            ;;
+        --gnu)
+            DEFAULT=
+            POSIX=yes
+            GNU=yes
+            ;;
+        --all)
+            DEFAULT=
+            POSIX=yes
+            BSD=yes
+            GNU=yes
+            ALL=yes
+            ;;
+        --sudo)
+            SUDO=yes
+            ;;
+        --stop)
+            STOP=yes
+            ;;
+        --noclean)
+            CLEAN=
+            ;;
+        --update)
+            UPDATE=yes
+            ;;
+        --verbose=commands)
+            VERBOSE_COMMANDS=yes
+            ;;
+        --verbose=errors)
+            VERBOSE_ERRORS=yes
+            ;;
+        --verbose=skipped)
+            VERBOSE_SKIPPED=yes
+            ;;
+        --verbose=tests)
+            VERBOSE_SKIPPED=yes
+            VERBOSE_TESTS=yes
+            ;;
+        --verbose)
+            VERBOSE_COMMANDS=yes
+            VERBOSE_ERRORS=yes
+            VERBOSE_SKIPPED=yes
+            VERBOSE_TESTS=yes
+            ;;
+        --help)
+            usage
+            exit 0
+            ;;
+        test_*)
+            EXPLICIT=yes
+            SUDO=yes
+            enabled_tests+=("$arg")
+            ;;
+        *)
+            printf "${RED}error:${RST} Unrecognized option '%s'.\n\n" "$arg" >&2
+            usage >&2
+            exit 1
+            ;;
+    esac
+done
+
+posix_tests=(
+    # General parsing
+    test_basic
+
+    test_parens
+    test_bang
+    test_implicit_and
+    test_a
+    test_o
+
+    test_weird_names
+
+    test_incomplete
+    test_missing_paren
+    test_extra_paren
+
+    # Flags
+
+    test_H
+    test_H_slash
+    test_H_broken
+    test_H_notdir
+    test_H_loops
+
+    test_L
+    test_L_broken
+    test_L_notdir
+    test_L_loops
+
+    test_flag_weird_names
+    test_flag_comma
+
+    # Primaries
+
+    test_depth
+    test_depth_slash
+    test_depth_error
+    test_L_depth
+
+    test_exec
+    test_exec_plus
+    test_exec_plus_status
+    test_exec_plus_semicolon
+
+    test_group_name
+    test_group_id
+    test_group_nogroup
+
+    test_links
+    test_links_plus
+    test_links_minus
+
+    test_name
+    test_name_root
+    test_name_root_depth
+    test_name_trailing_slash
+    test_name_star_star
+    test_name_character_class
+    test_name_bracket
+    test_name_backslash
+    test_name_double_backslash
+
+    test_newer
+    test_newer_link
+
+    test_nogroup
+    test_nogroup_ulimit
+
+    test_nouser
+    test_nouser_ulimit
+
+    test_ok_stdin
+    test_ok_plus_semicolon
+
+    test_path
+
+    test_perm_000
+    test_perm_000_minus
+    test_perm_222
+    test_perm_222_minus
+    test_perm_644
+    test_perm_644_minus
+    test_perm_symbolic
+    test_perm_symbolic_minus
+    test_perm_leading_plus_symbolic_minus
+    test_permcopy
+    test_perm_setid
+    test_perm_sticky
+
+    test_prune
+    test_prune_file
+    test_prune_or_print
+    test_not_prune
+
+    test_size
+    test_size_plus
+    test_size_bytes
+
+    test_type_d
+    test_type_f
+    test_type_l
+    test_H_type_l
+    test_L_type_l
+    test_type_bind_mount
+
+    test_user_name
+    test_user_id
+    test_user_nouser
+
+    test_xdev
+    test_L_xdev
+
+    # Closed file descriptors
+    test_closed_stdin
+    test_closed_stdout
+    test_closed_stderr
+
+    # PATH_MAX handling
+    test_deep
+
+    # Optimizer tests
+    test_or_purity
+    test_double_negation
+    test_de_morgan_not
+    test_de_morgan_and
+    test_de_morgan_or
+    test_data_flow_group
+    test_data_flow_user
+    test_data_flow_type
+    test_data_flow_and_swap
+    test_data_flow_or_swap
+)
+
+bsd_tests=(
+    # Flags
+
+    test_E
+
+    test_P
+    test_P_slash
+
+    test_X
+
+    test_d_path
+
+    test_f
+
+    test_s
+
+    test_double_dash
+    test_flag_double_dash
+
+    # Primaries
+
+    test_acl
+    test_L_acl
+
+    test_anewer
+    test_asince
+
+    test_delete
+    test_delete_many
+
+    test_depth_maxdepth_1
+    test_depth_maxdepth_2
+    test_depth_mindepth_1
+    test_depth_mindepth_2
+
+    test_depth_n
+    test_depth_n_plus
+    test_depth_n_minus
+    test_depth_depth_n
+    test_depth_depth_n_plus
+    test_depth_depth_n_minus
+    test_depth_overflow
+    test_data_flow_depth
+
+    test_exec_substring
+
+    test_execdir_pwd
+    test_execdir_slash
+    test_execdir_slash_pwd
+    test_execdir_slashes
+    test_execdir_ulimit
+
+    test_exit
+    test_exit_no_implicit_print
+
+    test_flags
+
+    test_follow
+
+    test_gid_name
+
+    test_ilname
+    test_L_ilname
+
+    test_iname
+
+    test_inum
+    test_inum_mount
+    test_inum_bind_mount
+
+    test_ipath
+
+    test_iregex
+
+    test_lname
+    test_L_lname
+
+    test_ls
+    test_L_ls
+
+    test_maxdepth
+
+    test_mindepth
+
+    test_mnewer
+    test_H_mnewer
+
+    test_mount
+    test_L_mount
+
+    test_msince
+
+    test_mtime_units
+
+    test_name_slash
+    test_name_slashes
+
+    test_H_newer
+
+    test_newerma
+    test_newermt
+    test_newermt_epoch_minus_one
+
+    test_ok_stdin
+    test_ok_closed_stdin
+
+    test_okdir_stdin
+    test_okdir_closed_stdin
+
+    test_perm_000_plus
+    test_perm_222_plus
+    test_perm_644_plus
+
+    test_printx
+
+    test_quit
+    test_quit_child
+    test_quit_depth
+    test_quit_depth_child
+    test_quit_after_print
+    test_quit_before_print
+    test_quit_implicit_print
+
+    test_rm
+
+    test_regex
+    test_regex_parens
+
+    test_samefile
+    test_samefile_symlink
+    test_H_samefile_symlink
+    test_L_samefile_symlink
+    test_samefile_broken
+    test_H_samefile_broken
+    test_L_samefile_broken
+    test_samefile_notdir
+    test_H_samefile_notdir
+    test_L_samefile_notdir
+
+    test_size_T
+    test_size_big
+
+    test_uid_name
+
+    test_xattr
+    test_L_xattr
+
+    test_xattrname
+    test_L_xattrname
+
+    # Optimizer tests
+    test_data_flow_sparse
+)
+
+gnu_tests=(
+    # General parsing
+
+    test_not
+    test_and
+    test_or
+    test_comma
+    test_precedence
+
+    test_follow_comma
+
+    # Flags
+
+    test_P
+    test_P_slash
+
+    test_L_loops_continue
+
+    test_double_dash
+    test_flag_double_dash
+
+    # Primaries
+
+    test_anewer
+
+    test_path_d
+
+    test_daystart
+    test_daystart_twice
+
+    test_delete
+    test_delete_many
+    test_L_delete
+
+    test_depth_mindepth_1
+    test_depth_mindepth_2
+    test_depth_maxdepth_1
+    test_depth_maxdepth_2
+
+    test_empty
+    test_empty_special
+
+    test_exec_nothing
+    test_exec_substring
+    test_exec_flush
+    test_exec_flush_fail
+    test_exec_plus_flush
+    test_exec_plus_flush_fail
+
+    test_execdir
+    test_execdir_substring
+    test_execdir_plus_semicolon
+    test_execdir_pwd
+    test_execdir_slash
+    test_execdir_slash_pwd
+    test_execdir_slashes
+    test_execdir_ulimit
+
+    test_executable
+
+    test_false
+
+    test_files0_from_file
+    test_files0_from_stdin
+    test_files0_from_none
+    test_files0_from_empty
+    test_files0_from_nowhere
+    test_files0_from_nothing
+    test_files0_from_ok
+
+    test_fls
+
+    test_follow
+
+    test_fprint
+    test_fprint_duplicate
+    test_fprint_error
+    test_fprint_noerror
+    test_fprint_noarg
+    test_fprint_nonexistent
+    test_fprint_truncate
+
+    test_fprint0
+
+    test_fprintf
+    test_fprintf_nofile
+    test_fprintf_noformat
+
+    test_fstype
+
+    test_gid
+    test_gid_plus
+    test_gid_plus_plus
+    test_gid_minus
+    test_gid_minus_plus
+
+    test_ignore_readdir_race
+    test_ignore_readdir_race_root
+    test_ignore_readdir_race_notdir
+
+    test_ilname
+    test_L_ilname
+
+    test_iname
+
+    test_inum
+    test_inum_mount
+    test_inum_bind_mount
+    test_inum_automount
+
+    test_ipath
+
+    test_iregex
+
+    test_iwholename
+
+    test_lname
+    test_L_lname
+
+    test_ls
+    test_L_ls
+
+    test_maxdepth
+
+    test_mindepth
+
+    test_mount
+    test_L_mount
+
+    test_name_slash
+    test_name_slashes
+
+    test_H_newer
+
+    test_newerma
+    test_newermt
+    test_newermt_epoch_minus_one
+
+    test_ok_closed_stdin
+    test_ok_nothing
+
+    test_okdir_closed_stdin
+    test_okdir_plus_semicolon
+
+    test_perm_000_slash
+    test_perm_222_slash
+    test_perm_644_slash
+    test_perm_symbolic_slash
+    test_perm_leading_plus_symbolic_slash
+
+    test_print_error
+
+    test_print0
+
+    test_printf
+    test_printf_empty
+    test_printf_slash
+    test_printf_slashes
+    test_printf_trailing_slash
+    test_printf_trailing_slashes
+    test_printf_flags
+    test_printf_types
+    test_printf_escapes
+    test_printf_times
+    test_printf_leak
+    test_printf_nul
+    test_printf_Y_error
+    test_printf_H
+    test_printf_u_g_ulimit
+    test_printf_l_nonlink
+
+    test_quit
+    test_quit_child
+    test_quit_depth
+    test_quit_depth_child
+    test_quit_after_print
+    test_quit_before_print
+
+    test_readable
+
+    test_regex
+    test_regex_parens
+    test_regex_error
+    test_regex_invalid_utf8
+
+    test_regextype_posix_basic
+    test_regextype_posix_extended
+    test_regextype_ed
+    test_regextype_emacs
+    test_regextype_grep
+    test_regextype_sed
+
+    test_samefile
+    test_samefile_symlink
+    test_H_samefile_symlink
+    test_L_samefile_symlink
+    test_samefile_broken
+    test_H_samefile_broken
+    test_L_samefile_broken
+    test_samefile_notdir
+    test_H_samefile_notdir
+    test_L_samefile_notdir
+
+    test_size_big
+
+    test_true
+
+    test_uid
+    test_uid_plus
+    test_uid_plus_plus
+    test_uid_minus
+    test_uid_minus_plus
+
+    test_wholename
+
+    test_writable
+
+    test_xtype_l
+    test_xtype_f
+    test_L_xtype_l
+    test_L_xtype_f
+    test_xtype_bind_mount
+
+    # Optimizer tests
+    test_and_purity
+    test_not_reachability
+    test_comma_reachability
+    test_and_false_or_true
+    test_comma_redundant_true
+    test_comma_redundant_false
+)
+
+bfs_tests=(
+    # General parsing
+    test_path_flag_expr
+    test_path_expr_flag
+    test_flag_expr_path
+    test_expr_flag_path
+    test_expr_path_flag
+
+    test_unexpected_operator
+
+    test_typo
+
+    # Flags
+
+    test_D_multi
+    test_D_all
+
+    test_O0
+    test_O1
+    test_O2
+    test_O3
+    test_Ofast
+
+    test_S_bfs
+    test_S_dfs
+    test_S_ids
+
+    # Special forms
+
+    test_exclude_name
+    test_exclude_depth
+    test_exclude_mindepth
+    test_exclude_print
+    test_exclude_exclude
+
+    # Primaries
+
+    test_capable
+    test_L_capable
+
+    test_color
+    test_color_L
+    test_color_rs_lc_rc_ec
+    test_color_escapes
+    test_color_nul
+    test_color_ln_target
+    test_color_L_ln_target
+    test_color_mh
+    test_color_mh0
+    test_color_or
+    test_color_mi
+    test_color_or_mi
+    test_color_or_mi0
+    test_color_or0_mi
+    test_color_or0_mi0
+    test_color_su_sg0
+    test_color_su0_sg
+    test_color_su0_sg0
+    test_color_st_tw_ow0
+    test_color_st_tw0_ow
+    test_color_st_tw0_ow0
+    test_color_st0_tw_ow
+    test_color_st0_tw_ow0
+    test_color_st0_tw0_ow
+    test_color_st0_tw0_ow0
+    test_color_ext
+    test_color_ext0
+    test_color_ext_override
+    test_color_ext_underride
+    test_color_missing_colon
+    test_color_no_stat
+    test_color_L_no_stat
+    test_color_star
+    test_color_ls
+
+    test_exec_flush_fprint
+    test_exec_flush_fprint_fail
+
+    test_execdir_plus
+
+    test_fprint_duplicate_stdout
+    test_fprint_error_stdout
+    test_fprint_error_stderr
+
+    test_help
+
+    test_hidden
+    test_hidden_root
+
+    test_links_noarg
+    test_links_empty
+    test_links_negative
+    test_links_invalid
+
+    test_newerma_nonexistent
+    test_newermt_invalid
+    test_newermq
+    test_newerqm
+
+    test_nohidden
+    test_nohidden_depth
+
+    test_perm_symbolic_trailing_comma
+    test_perm_symbolic_double_comma
+    test_perm_symbolic_missing_action
+    test_perm_leading_plus_symbolic
+
+    test_printf_w
+    test_printf_incomplete_escape
+    test_printf_invalid_escape
+    test_printf_incomplete_format
+    test_printf_invalid_format
+    test_printf_duplicate_flag
+    test_printf_must_be_numeric
+    test_printf_color
+
+    test_type_multi
+
+    test_unique
+    test_unique_depth
+    test_L_unique
+    test_L_unique_loops
+    test_L_unique_depth
+
+    test_version
+
+    test_xtype_multi
+
+    # Optimizer tests
+    test_data_flow_hidden
+    test_xtype_reorder
+    test_xtype_depth
+
+    # PATH_MAX handling
+    test_deep_strict
+
+    # Error handling
+    test_stderr_fails_silently
+    test_stderr_fails_loudly
+)
+
+if [ "$DEFAULT" ]; then
+    POSIX=yes
+    BSD=yes
+    GNU=yes
+    ALL=yes
+fi
+
+if [ ! "$EXPLICIT" ]; then
+    [ "$POSIX" ] && enabled_tests+=("${posix_tests[@]}")
+    [ "$BSD" ] && enabled_tests+=("${bsd_tests[@]}")
+    [ "$GNU" ] && enabled_tests+=("${gnu_tests[@]}")
+    [ "$ALL" ] && enabled_tests+=("${bfs_tests[@]}")
+fi
+
+eval "enabled_tests=($(printf '%q\n' "${enabled_tests[@]}" | sort -u))"
+
+function _realpath() {
+    (
+        cd "$(dirname -- "$1")"
+        echo "$PWD/$(basename -- "$1")"
+    )
+}
+
+TESTS=$(_realpath "$(dirname -- "${BASH_SOURCE[0]}")")
+BIN=$(_realpath "$TESTS/../bin")
+
+# Try to resolve the path to $BFS before we cd, while also supporting
+# --bfs="./bin/bfs -S ids"
+read -a BFS <<<"${BFS:-$BIN/bfs}"
+BFS[0]=$(_realpath "$(command -v "${BFS[0]}")")
+
+# The temporary directory that will hold our test data
+TMP=$(mktemp -d "${TMPDIR:-/tmp}"/bfs.XXXXXXXXXX)
+chown "$(id -u):$(id -g)" "$TMP"
+
+# Clean up temporary directories on exit
+function cleanup() {
+    # Don't force rm to deal with long paths
+    for dir in "$TMP"/deep/*/*; do
+        if [ -d "$dir" ]; then
+            (cd "$dir" && rm -rf *)
+        fi
+    done
+
+    # In case a test left anything weird in scratch/
+    if [ -e "$TMP"/scratch ]; then
+        chmod -R +rX "$TMP"/scratch
+    fi
+
+    rm -rf "$TMP"
+}
+
+if [ "$CLEAN" ]; then
+    trap cleanup EXIT
+else
+    echo "Test files saved to $TMP"
+fi
+
+# Install a file, creating any parent directories
+function installp() {
+    local target="${@: -1}"
+    mkdir -p "${target%/*}"
+    install "$@"
+}
+
+# Prefer GNU touch to work around https://apple.stackexchange.com/a/425730/397839
+if command -v gtouch &>/dev/null; then
+    TOUCH=gtouch
+else
+    TOUCH=touch
+fi
+
+# Like a mythical touch -p
+function touchp() {
+    for arg; do
+        installp -m644 /dev/null "$arg"
+    done
+}
+
+# Creates a simple file+directory structure for tests
+function make_basic() {
+    touchp "$1/a"
+    touchp "$1/b"
+    touchp "$1/c/d"
+    touchp "$1/e/f"
+    mkdir -p "$1/g/h"
+    mkdir -p "$1/i"
+    touchp "$1/j/foo"
+    touchp "$1/k/foo/bar"
+    touchp "$1/l/foo/bar/baz"
+    echo baz >"$1/l/foo/bar/baz"
+}
+make_basic "$TMP/basic"
+
+# Creates a file+directory structure with various permissions for tests
+function make_perms() {
+    installp -m000 /dev/null "$1/0"
+    installp -m444 /dev/null "$1/r"
+    installp -m222 /dev/null "$1/w"
+    installp -m644 /dev/null "$1/rw"
+    installp -m555 /dev/null "$1/rx"
+    installp -m311 /dev/null "$1/wx"
+    installp -m755 /dev/null "$1/rwx"
+}
+make_perms "$TMP/perms"
+
+# Creates a file+directory structure with various symbolic and hard links
+function make_links() {
+    touchp "$1/file"
+    ln -s file "$1/symlink"
+    ln "$1/file" "$1/hardlink"
+    ln -s nowhere "$1/broken"
+    ln -s symlink/file "$1/notdir"
+    mkdir -p "$1/deeply/nested/dir"
+    touchp "$1/deeply/nested/file"
+    ln -s file "$1/deeply/nested/link"
+    ln -s nowhere "$1/deeply/nested/broken"
+    ln -s deeply/nested "$1/skip"
+}
+make_links "$TMP/links"
+
+# Creates a file+directory structure with symbolic link loops
+function make_loops() {
+    touchp "$1/file"
+    ln -s file "$1/symlink"
+    ln -s nowhere "$1/broken"
+    ln -s symlink/file "$1/notdir"
+    ln -s loop "$1/loop"
+    mkdir -p "$1/deeply/nested/dir"
+    ln -s ../../deeply "$1/deeply/nested/loop"
+    ln -s deeply/nested/loop/nested "$1/skip"
+}
+make_loops "$TMP/loops"
+
+# Creates a file+directory structure with varying timestamps
+function make_times() {
+    mkdir -p "$1"
+    $TOUCH -t 199112140000 "$1/a"
+    $TOUCH -t 199112140001 "$1/b"
+    $TOUCH -t 199112140002 "$1/c"
+    ln -s a "$1/l"
+    $TOUCH -h -t 199112140003 "$1/l"
+    $TOUCH -t 199112140004 "$1"
+}
+make_times "$TMP/times"
+
+# Creates a file+directory structure with various weird file/directory names
+function make_weirdnames() {
+    touchp "$1/-/a"
+    touchp "$1/(/b"
+    touchp "$1/(-/c"
+    touchp "$1/!/d"
+    touchp "$1/!-/e"
+    touchp "$1/,/f"
+    touchp "$1/)/g"
+    touchp "$1/.../h"
+    touchp "$1/\\/i"
+    touchp "$1/ /j"
+    touchp "$1/[/k"
+}
+make_weirdnames "$TMP/weirdnames"
+
+# Creates a very deep directory structure for testing PATH_MAX handling
+function make_deep() {
+    mkdir -p "$1"
+
+    # $name will be 255 characters, aka _XOPEN_NAME_MAX
+    local name="0123456789ABCDEF"
+    name="${name}${name}${name}${name}"
+    name="${name}${name}${name}${name}"
+    name="${name:0:255}"
+
+    for i in {0..9} A B C D E F; do
+        (
+            mkdir "$1/$i"
+            cd "$1/$i"
+
+            # 16 * 256 == 4096 == PATH_MAX
+            for _ in {1..16}; do
+                mkdir "$name"
+                cd "$name" 2>/dev/null
+            done
+
+            $TOUCH "$name"
+        )
+    done
+}
+make_deep "$TMP/deep"
+
+# Creates a directory structure with many different types, and therefore colors
+function make_rainbow() {
+    touchp "$1/file.txt"
+    touchp "$1/file.dat"
+    touchp "$1/star".{gz,tar,tar.gz}
+    ln -s file.txt "$1/link.txt"
+    touchp "$1/mh1"
+    ln "$1/mh1" "$1/mh2"
+    mkfifo "$1/pipe"
+    # TODO: block
+    ln -s /dev/null "$1/chardev_link"
+    ln -s nowhere "$1/broken"
+    "$BIN/tests/mksock" "$1/socket"
+    touchp "$1"/s{u,g,ug}id
+    chmod u+s "$1"/su{,g}id
+    chmod g+s "$1"/s{u,}gid
+    mkdir "$1/ow" "$1"/sticky{,_ow}
+    chmod o+w "$1"/*ow
+    chmod +t "$1"/sticky*
+    touchp "$1"/exec.sh
+    chmod +x "$1"/exec.sh
+}
+make_rainbow "$TMP/rainbow"
+
+# Creates a scratch directory that tests can modify
+function make_scratch() {
+    mkdir -p "$1"
+}
+make_scratch "$TMP/scratch"
+
+# Close stdin so bfs doesn't think we're interactive
+exec </dev/null
+
+if [ "$VERBOSE_COMMANDS" ]; then
+    # dup stdout for verbose logging even when redirected
+    exec 3>&1
+fi
+
+function bfs_verbose() {
+    if [ "$VERBOSE_COMMANDS" ]; then
+        if [ -t 3 ]; then
+            printf "${GRN}%q${RST} " "${BFS[@]}" >&3
+
+            local expr_started=
+            for arg; do
+                if [[ $arg == -[A-Z]* ]]; then
+                    printf "${CYN}%q${RST} " "$arg" >&3
+                elif [[ $arg == [\(!] || $arg == -[ao] || $arg == -and || $arg == -or || $arg == -not ]]; then
+                    expr_started=yes
+                    printf "${RED}%q${RST} " "$arg" >&3
+                elif [[ $expr_started && $arg == [\),] ]]; then
+                    printf "${RED}%q${RST} " "$arg" >&3
+                elif [[ $arg == -?* ]]; then
+                    expr_started=yes
+                    printf "${BLU}%q${RST} " "$arg" >&3
+                elif [ "$expr_started" ]; then
+                    printf "${BLD}%q${RST} " "$arg" >&3
+                else
+                    printf "${MAG}%q${RST} " "$arg" >&3
+                fi
+            done
+        else
+            printf '%q ' "${BFS[@]}" "$@" >&3
+        fi
+        printf '\n' >&3
+    fi
+}
+
+function invoke_bfs() {
+    bfs_verbose "$@"
+    "${BFS[@]}" "$@"
+}
+
+# Expect a command to fail, but not crash
+function fail() {
+    "$@"
+    local STATUS="$?"
+
+    if ((STATUS > 125)); then
+        exit "$STATUS"
+    elif ((STATUS > 0)); then
+        return 0
+    else
+        return 1
+    fi
+}
+
+# Detect colored diff support
+if [ -t 2 ] && diff --color=always /dev/null /dev/null 2>/dev/null; then
+    DIFF="diff --color=always"
+else
+    DIFF="diff"
+fi
+
+# Return value when bfs fails
+EX_BFS=10
+# Return value when a difference is detected
+EX_DIFF=20
+# Return value when a test is skipped
+EX_SKIP=77
+
+function bfs_diff() (
+    bfs_verbose "$@"
+
+    # Close the dup()'d stdout to make sure we have enough fd's for the process
+    # substitution, even with low ulimit -n
+    exec 3>&-
+
+    local CALLER
+    for CALLER in "${FUNCNAME[@]}"; do
+        if [[ $CALLER == test_* ]]; then
+            break
+        fi
+    done
+
+    local EXPECTED="$TESTS/$CALLER.out"
+    if [ "$UPDATE" ]; then
+        local ACTUAL="$EXPECTED"
+    else
+        local ACTUAL="$TMP/$CALLER.out"
+    fi
+
+    "${BFS[@]}" "$@" | sort >"$ACTUAL"
+    local STATUS="${PIPESTATUS[0]}"
+
+    if [ ! "$UPDATE" ]; then
+        $DIFF -u "$EXPECTED" "$ACTUAL" >&2 || return $EX_DIFF
+    fi
+
+    if [ "$STATUS" -eq 0 ]; then
+        return 0
+    else
+        return $EX_BFS
+    fi
+)
+
+function skip() {
+    exit $EX_SKIP
+}
+
+function skip_if() {
+    if "$@"; then
+        skip
+    fi
+}
+
+function skip_unless() {
+    skip_if fail "$@"
+}
+
+function closefrom() {
+    if [ -d /proc/self/fd ]; then
+        local fds=/proc/self/fd
+    else
+        local fds=/dev/fd
+    fi
+
+    for fd in "$fds"/*; do
+        if [ ! -e "$fd" ]; then
+            continue
+        fi
+
+        local fd="${fd##*/}"
+        if [ "$fd" -ge "$1" ]; then
+            eval "exec ${fd}<&-"
+        fi
+    done
+}
+
+function inum() {
+    ls -id "$@" | awk '{ print $1 }'
+}
+
+
+cd "$TMP"
+set +e
+
+# Test cases
+
+function test_basic() {
+    bfs_diff basic
+}
+
+function test_type_d() {
+    bfs_diff basic -type d
+}
+
+function test_type_f() {
+    bfs_diff basic -type f
+}
+
+function test_type_l() {
+    bfs_diff links/skip -type l
+}
+
+function test_H_type_l() {
+    bfs_diff -H links/skip -type l
+}
+
+function test_L_type_l() {
+    bfs_diff -L links/skip -type l
+}
+
+function test_type_multi() {
+    bfs_diff links -type f,d,c
+}
+
+function test_mindepth() {
+    bfs_diff basic -mindepth 1
+}
+
+function test_maxdepth() {
+    bfs_diff basic -maxdepth 1
+}
+
+function test_depth() {
+    bfs_diff basic -depth
+}
+
+function test_depth_slash() {
+    bfs_diff basic/ -depth
+}
+
+function test_depth_mindepth_1() {
+    bfs_diff basic -mindepth 1 -depth
+}
+
+function test_depth_mindepth_2() {
+    bfs_diff basic -mindepth 2 -depth
+}
+
+function test_depth_maxdepth_1() {
+    bfs_diff basic -maxdepth 1 -depth
+}
+
+function test_depth_maxdepth_2() {
+    bfs_diff basic -maxdepth 2 -depth
+}
+
+function test_depth_error() {
+    rm -rf scratch/*
+    touchp scratch/foo/bar
+    chmod a-r scratch/foo
+
+    bfs_diff scratch -depth
+    local ret=$?
+
+    chmod +r scratch/foo
+    rm -rf scratch/*
+
+    [ $ret -eq $EX_BFS ]
+}
+
+function test_name() {
+    bfs_diff basic -name '*f*'
+}
+
+function test_name_root() {
+    bfs_diff basic/a -name a
+}
+
+function test_name_root_depth() {
+    bfs_diff basic/g -depth -name g
+}
+
+function test_name_trailing_slash() {
+    bfs_diff basic/g/ -name g
+}
+
+function test_name_slash() {
+    bfs_diff / -maxdepth 0 -name /
+}
+
+function test_name_slashes() {
+    bfs_diff /// -maxdepth 0 -name /
+}
+
+function test_name_star_star() {
+    bfs_diff basic -name '**f**'
+}
+
+function test_name_character_class() {
+    bfs_diff basic -name '[e-g][!a-n][!p-z]'
+}
+
+function test_name_bracket() {
+    # fnmatch() is broken on macOS
+    skip_if test "$UNAME" = "Darwin"
+
+    # An unclosed [ should be matched literally
+    bfs_diff weirdnames -name '['
+}
+
+function test_name_backslash() {
+    # An unescaped \ doesn'