path: root/scripts/depsort

#!/bin/sh -e

HERE="$(dirname $(readlink -f ${0}))";
LIST="${HERE}/../.exclude";

#---------------------------------------------------------------
# overview

##
# Usage:
#
#   $ ./scripts/deplist system | ./scripts/depsort
#
# This script reads a list of packages (stdin) of the form:
#
#     pkg1 dep1 dep2 ...
#     pkg2 ...
#
# and computes a topological sort, then prints to stdout.
#
# If the file called '$LIST' exists, it will be used as a filter
# to exclude those packages, their dependencies, and transitive
# dependencies as well, from the build plan.
#
# Entries must be one per line of the form REPO/PACKAGE:
#
#     user/rust
#
# It is possible to end up with a surprisingly small build plan
# if a more essential package is excluded, so this mechanism
# should only be used to temporarily avoid problematic packages
# or known package families e.g. "all java-related".


#---------------------------------------------------------------
# supporting routines

##
# Appends text to the end of each line of stdin, in this case it
# is to assist 'grep' later on.
#
# We strictly search for ending in space or end of line instead
# of with the flag '-F', which is string literal, to avoid any
# partial and undesirable matches, e.g. 'foo' in 'foo3'.
#
# This is a function because it is used multiple times and may
# need to be updated in the future.
#
suffix ()
{
    sed -e 's@$@\\( \\|$\\)@g';
}


#---------------------------------------------------------------
# initialization

##
# We need to create a few temporary files in order to support
# handling transitive dependencies because it is not possible to
# reuse 'foo' as in: 'tee >( ... > foo) | bar -f foo'.
#
data=$(mktemp); # stdin
user=$(mktemp); # processed '$LIST'
real=$(mktemp); # processed derivation of dependencies

##
# Capture stdin because it needs to be split for filtering.
# This could in theory be done later, without 'cat', but
# it is much easier for others to follow when it's here.
#
cat > "${data}";


#---------------------------------------------------------------
# preprocessing

##
# If there is no exclusion file, passthru.
#
if test -f "${LIST}"; then

    ##
    # Preprocess user input '$LIST' to include a suffix that
    # works better with 'grep'. Write to file for multi-line
    # support. The '!' before ' grep' is to ignore a no-match
    # error that will otherwise cause the script to exit early.
    #
    suffix < "${LIST}" > "${user}";
    ! grep -f "${user}" "${data}" \
        | awk '{print $1}' \
        | suffix \
        | grep / `# ensure all lines of form: REPO/PACKAGE` \
        > "${real}" \
        ;
    exclude="grep -vf ${real} ${data}";
else
    exclude="cat ${data}";
fi

#---------------------------------------------------------------
# filtering

##
# Enumerate digraph nodes based on (possibly) filtered input.
#
# Pipe to 'tsort' for the final build plan.
#
${exclude} \
    | awk '{ for (f=1;f<=NF;f++) { print $(f),$1 } }' \
    | "${HERE}"/tsort \
    ;

#---------------------------------------------------------------
# cleanup

rm -f "${data}" "${user}" "${real}";