#!/bin/bash -eu

. shell-error
. shell-args
. shell-getopt

system_provides=
runlevels='0 1 2 3 4 5 6'
result='print'
rcdir='/etc/rc.d'
rootdir='/'

show_help()
{
	cat <<-EOF
	Usage: $PROG [options]

	The utility sorts services on the basis of LSB headers.

	Options:
	  --runlevels=LIST         sets list of runlevels (default: $runlevels);
	  --rootdir=DIR            defines root directory (default: '$rootdir');
	  --rcdir=DIR              defines initscripts base directory (default: '$rcdir');
	  -r, --result=TYPE        defines that need to be done (default: '$result')
	                           valid options: 'print','gencpio','symlink','none';
	  -P,--sys-provides=LIST   defines list of system services;
	  -q, --quiet              try to be more quiet;
	  -v, --verbose            print a message for each action;
	  -V, --version            print program version and exit;
	  -h, --help               show this text and exit.

	Report bugs to authors.

	EOF
	exit
}

print_version()
{
	cat <<-EOF
	$PROG version $PROG_VERSION
	Written by Alexey Gladkov <gladkov.alexey@gmail.com>

	Copyright (C) 2014  Alexey Gladkov <gladkov.alexey@gmail.com>
	This is free software; see the source for copying conditions.  There is NO
	warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
	EOF
	exit
}

result()
{
	local ltarget lfile

	lfile="${rootdir%/}${rcdir%/}/rc$2.d/$3$1"
	ltarget="../init.d/$1"

	case "$result" in
		'print')
			printf '%s\n' \
				"$lfile"
			;;
		'gencpio')
			printf 'slink %s %s 0777 0 0\n' \
				"$ltarget" ".${lfile#$rootdir}"
			;;
		'symlink')
			mkdir -p -- "${lfile%/*}"
			ln -s -- \
				"$ltarget" "$lfile"
			;;
		'none')
			;;
	esac
}

empty()
{
	[ "$#" -eq 0 ] || return 1
}

in_list()
{
	local __in_list_strlist
	declare -n "__in_list_strlist=$1"; shift
	[ -n "$1" ] &&
	! empty $__in_list_strlist ||
		return 1
	[ "$__in_list_strlist" != "$1" ] &&
	[ -n "${__in_list_strlist##$1 *}" ] &&
	[ -n "${__in_list_strlist##* $1 *}" ] &&
	[ -n "${__in_list_strlist##* $1}" ] ||
		return 0
	return 1
}

remove_from_list()
{
	in_list "$@" ||
		return 0
	local __strlist __elem
	declare -n "__strlist=$1"; shift
	__elem="$1"
	set -- $__strlist
	__strlist=
	while [ "$#" != 0 ]; do
		if [ "$__elem" != "$1" ]; then
			[ -z "$__strlist" ] ||
				__strlist+=" "
			__strlist+="$1"
		fi
		shift
	done
}

append()
{
	local __append_strlist n
	declare -n "__append_strlist=$1"; shift
	for n; do
		[ "$n" = '@mark' ] || ! in_list __append_strlist "$n" ||
			continue
		[ -z "$__append_strlist" ] ||
			__append_strlist+=" "
		__append_strlist+="$n"
	done
}

rc_names=0
parse_services()
{
	local f name='' l block value level type vname
	local provides S_requires S_suggests S_level S_before K_requires K_suggests K_level K_before

	verbose "Parsing services"

	while :; do
		for f in "${rootdir%/}${rcdir%/}/init.d"/*; do
			[ -x "$f" ] ||
				continue

			block=0
			service="${f##*/}"

			# provide service filename
			provides="$service"

			S_requires='' S_suggests='' S_level='' S_before=''
			K_requires='' K_suggests='' K_level='' K_before=''

			# shellcheck disable=SC2162
			while read l; do
				vname=
				case "$l" in
					'### BEGIN INIT INFO')
						[ "$block" = 0 ] || break
						block=1
						;;
					'### END INIT INFO')
						[ "$block" = 1 ] || continue
						block=2
						break
						;;
					'# Provides:'*)       vname='provides'   ;;
					'# Default-Start:'*)  vname='S_level'    ;;
					'# Required-Start:'*) vname='S_requires' ;;
					'# Should-Start:'*)   vname='S_suggests' ;;
					'# Required-Stop:'*)  vname='K_requires' ;;
					'# Should-Stop:'*)    vname='K_suggests' ;;
					'# X-Start-Before:'*) vname='S_before'   ;;
					'# Default-Stop:'*)   vname=             ;;
				esac

				[ "$block" != 1 ] || [ -z "$vname" ] ||
					append $vname ${l#*:}
			done < "$f"

			if [ "$block" != 2 ]; then
				verbose "Service without LSB header (ignored): $f"
				continue
			fi

			! empty $K_requires || K_requires="$S_requires"
			! empty $K_suggests || K_suggests="$S_suggests"

			verbose "Service with LSB header: $f"
			verbose "   Levels   (S): $S_level"
			verbose "   Provides    : $provides"
			verbose "   Before   (S): $S_before"
			verbose "   Requires (S): $S_requires"
			verbose "   Requires (K): $K_requires"
			verbose "   Suggests (S): $S_suggests"
			verbose "   Suggests (K): $K_suggests"

			name="$rc_names"
			rc_names=$(($rc_names + 1))

			eval "rc_${name}=\"\$service\""
			eval "rc_${name}_provides=\"\$provides\""

			for type in S K; do
				eval "rc_${name}_${type}_before=\"\$${type}_before\""
				eval "rc_${name}_${type}_requires=\"\$${type}_requires\""
				eval "rc_${name}_${type}_suggests=\"\$${type}_suggests\""
			done

			for level in $runlevels; do
				in_list S_level "$level" &&
					type='S' ||
					type='K'
				append "rc${level}_${type}_names" $name
			done
		done
		break
	done
}

print_name()
{
	local service
	eval "service=\"\$rc_$1\""
	printf '%s' "$service"
}

print_list()
{
	local __print_names __print_name
	declare -n "__print_names=$1"; shift
	set --
	for __print_name in $__print_names; do
		if [ "$__print_name" = '@mark' ]; then
			set -- "$@" "$__print_name"
			continue
		fi
		eval "set -- \"\$@\" \"\$rc_${__print_name}\""
	done
	printf '%s\n' "$*"
}

process_suggests()
{
	local level type names deps requires suggests name req
	level="$1"; shift
	type="$1"; shift

	declare -n "names=rc${level}_${type}_names"

	deps=
	for name in $names; do
		eval "append deps \$rc_${name}_provides"
	done

	for name in $names; do
		declare -n "requires=rc_${name}_${type}_requires"
		declare -n "suggests=rc_${name}_${type}_suggests"

		for req in $suggests; do
			! in_list deps "$req" ||
				append requires $req
		done
	done
}

process_before()
{
	local level type names before provides requires name req reqname dep rcname
	level="$1"; shift
	type="$1"; shift

	verbose "Processing x-start-before services ($type$level)"

	declare -n "names=rc${level}_${type}_names"

	for name in $names; do
		declare -n "rcname=rc_${name}"
		declare -n "provides=rc_${name}_provides"
		declare -n "requires=rc_${name}_${type}_requires"

		for req in $names; do
			declare -n "reqname=rc_${req}"
			declare -n "before=rc_${req}_${type}_before"

			for dep in $before; do
				if in_list provides "$dep"; then
					verbose "   $rcname requires $reqname"
					append requires "$reqname"
				fi
			done
		done
	done
}

find_provider()
{
	local i=0 provides

	while [ "$i" -lt "$rc_names" ]; do
		declare -n "provides=rc_${i}_provides"

		if in_list provides "$1"; then
			printf '%s' "$i"
			return
		fi

		i=$(($i + 1))
	done
	return 1
}

sort_services()
{
	local level type
	level="$1"; shift
	type="$1"; shift

	local names name services='' deps='' found
	local req requires provides new_serv='' new_prov=''
	local unmet_name unmet_req

	verbose "Ordering services ($type$level)"

	eval "names=\"\$rc${level}_${type}_names\""
	eval "unset rc${level}_${type}_names"

	[ -z "$system_provides" ] ||
		append deps $system_provides

	# First: filter names withoout requires
	for name in $names; do
		declare -n "provides=rc_${name}_provides"
		declare -n "requires=rc_${name}_${type}_requires"

		empty $requires ||
			continue

		append new_serv $name
		append new_prov $provides

		remove_from_list names "$name"
	done

	if [ -n "$new_serv" ]; then
		append deps $new_prov
		append services '@mark' $new_serv
	fi

	# Second: order others by requires
	while :; do
		new_serv=
		new_prov=

		verbose "   ($type$level) order: $(print_list services)"

		for name in $names; do
			declare -n "provides=rc_${name}_provides"
			declare -n "requires=rc_${name}_${type}_requires"

			found=1
			for req in $requires; do
				if ! in_list deps "$req"; then
					unmet_name="$name"
					unmet_req="$req"
					found=
					break
				fi
			done

			[ -n "$found" ] ||
				continue

			append new_serv $name
			append new_prov $provides

			remove_from_list names "$name"
		done

		if [ -n "$new_serv" ]; then
			append deps $new_prov
			append services '@mark' $new_serv
		else
			break
		fi
	done

	if ! empty $names; then
		services=
		for name in $names; do
			[ -z "$services" ] ||
				services+=" "
			eval "services+=\"\$rc_${name}\""
		done

		if badname="$(find_provider "$unmet_req")"; then
			unmet_name="$badname"
			unmet_req=
			declare -n "requires=rc_${badname}_${type}_requires"
			for req in $requires; do
				in_list deps "$req" || unmet_req+="$req "
			done
		fi

		fatal "Error: runlevel=$type$level: Unable to find service(s) required by '$(print_name $unmet_name)': $unmet_req"
	fi

	empty $services ||
		append services '@mark'

	eval "rc${level}_${type}_order=\"\$services\""
}

make_start_links()
{
	local order serv name rank=1 vrank
	declare -n "order=rc${1}_S_order"

	for serv in $order; do
		if [ "$serv" != '@mark' ]; then
			declare -n "name=rc_${serv}"
			printf -v vrank "S%0${#rc_names}d:" "$rank"
			result "$name" "$level" "$vrank"
		else
			rank=$(($rank + 1))
		fi
	done
}

make_stop_links()
{
	local order serv name rank=1 vrank
	declare -n "order=rc${1}_K_order"

	for serv in $order; do
		[ "$serv" != '@mark' ] ||
			rank=$(($rank + 1))
	done

	for serv in $order; do
		if [ "$serv" != '@mark' ]; then
			declare -n "name=rc_${serv}"
			printf -v vrank "K%0${#rc_names}d:" "$rank"
			result "$name" "$level" "$vrank"
		else
			rank=$(($rank - 1))
		fi
	done
}

process_runlevel()
{
	local level="$1"

	if [ -n "$verbose" ]; then
		printf '\n' >&2
		verbose "Services per runlevel $level"
		verbose "   (S$level) services: $(print_list rc${level}_S_names)"
		verbose "   (K$level) services: $(print_list rc${level}_K_names)"
	fi

	process_suggests "$level" S
	process_suggests "$level" K

	process_before "$level" S

	sort_services "$level" S
	sort_services "$level" K

	[ "$result" = 'none' ] ||
		verbose "Runlevel: $level"

	make_stop_links  "$level"
	make_start_links "$level"
}

TEMP=`getopt -n "$PROG" -o "$getopt_common_opts,P:,r:" -l "$getopt_common_longopts,rcdir:,result:,rootdir:,runlevels:,sys-provides:" -- "$@"` ||
	show_usage
eval set -- "$TEMP"

while :; do
	case "$1" in
		--sys-provides) shift
			system_provides="$1"
			;;
		--rootdir)
			rootdir="$(opt_check_dir "$1" "$2")"
			shift
			;;
		--rcdir)
			rcdir="$(opt_check_dir "$1" "$2")"
			shift
			;;
		--runlevels) shift
			runlevels="$1"
			;;
		-r|--result) shift
			case "$1" in
				'gencpio'|'print'|'symlink'|'none') result="$1" ;;
				*)
					fatal "Unknown argument: $1"
					;;
			esac
			;;
		-h|--help) show_help
			;;
		-q|--quiet) quiet=-q; verbose=
			;;
		-v|--verbose) verbose=-v; quiet=
			;;
		-V|--version) print_version "$PROG"
			;;
		--) shift; break
			;;
		*) fatal "Unrecognized option: $1"
			;;
	esac
	shift
done

# Prepare
for level in $runlevels; do
	eval "rc${level}_S_names=' '"
	eval "rc${level}_K_names=' '"
done

# Global parsing
parse_services

# Process runlevels
for level in $runlevels; do
    (process_runlevel "$level")
done
