#!/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='/'
rc_names=' '

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
}

append()
{
	local name var n
	var="$1"; shift
	eval "name=\" \${$var:-}\""
	for n; do
		[ "$n" = '@mark' ] || [ -n "${name##* $n *}" ] ||
			continue
		name="$name $n "
	done
	set -- $name
	eval "$var=\" \$* \""
}

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##*/}"
			provides=

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

			# provide service filename
			append provides "${f##*/}"

			# 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="$(printf '%s' "$name" | sha1sum)"
			name="${name%% *}"
			eval "rc_${name}=\"\$service\""

			append rc_names $name

			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
				[ -z "${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 name service

	for name; do
		if [ "$name" = '@mark' ]; then
			printf '%s ' "$name"
			continue
		fi
		eval "service=\"\$rc_${name}\""
		printf '%s ' "$service"
	done
	printf '\n'
}

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

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

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

	for name in $names; do
		eval "requires=\"\$rc_${name}_${type}_requires\""
		eval "suggests=\"\$rc_${name}_${type}_suggests\""

		for req in $suggests; do
			[ -n "${deps##* $req *}" ] ||
				append requires $req
		done

		eval "rc_${name}_${type}_requires=\"\$requires\""
	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)"

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

	for name in $names; do
		eval "rcname=\"\$rc_${name}\""
		eval "provides=\" \$rc_${name}_provides \""
		eval "requires=\"\$rc_${name}_${type}_requires\""

		for req in $names; do
			eval "reqname=\"\$rc_${req}\""
			eval "before=\"\$rc_${req}_${type}_before\""

			for dep in $before; do
				if [ -z "${provides##* $dep *}" ]; then
					verbose "   $rcname requires $reqname"
					append requires "$reqname"
				fi
			done
		done

		eval "rc_${name}_${type}_requires=\"\$requires\""
	done
}

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
		eval "provides=\"\$rc_${name}_provides\""
		eval "requires=\"\$rc_${name}_${type}_requires\""

		empty $requires ||
			continue

		append new_serv $name
		append new_prov $provides

		names="${names% $name *} ${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
			eval "provides=\"\$rc_${name}_provides\""
			eval "requires=\"\$rc_${name}_${type}_requires\""

			found=1
			for req in $requires; do
				[ -n "${deps##* $req *}" ] ||
					continue
				found=
				unmet_name="$name"
				unmet_req="$req"
				break
			done

			[ -n "$found" ] ||
				continue

			append new_serv $name
			append new_prov $provides

			names="${names% $name *} ${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
			eval "services=\"\$services \$rc_${name}\""
		done
		message "Error: Unable to find dependency for '$(print_name $unmet_name)' on $type$level: $unmet_req"
		fatal "Error: Unmet found at runlevel $type$level in services:$services"
	fi

	empty $services ||
		append services '@mark'

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

make_start_links()
{
	local level order serv name rank=10
	level="$1"

	eval "order=\"\$rc${level}_S_order\""

	for serv in $order; do
		if [ "$serv" != '@mark' ]; then
			eval "name=\"\$rc_${serv}\""
			result "$name" "$level" "S$rank"
		else
			rank=$(($rank + 10))
		fi
	done
}

make_stop_links()
{
	local level order serv name rank=10
	level="$1"

	eval "order=\"\$rc${level}_K_order\""

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

	for serv in $order; do
		if [ "$serv" != '@mark' ]; then
			eval "name=\"\$rc_${serv}\""
			result "$name" "$level" "K$rank"
		else
			rank=$(($rank - 10))
		fi
	done
}

process_runlevel()
{
	local level="$1"

	if [ -n "$verbose" ]; then
		printf '\n' >&2
		verbose "Services per runlevel $level"
		verbose "   (S$level) services: $(eval "print_list \$rc${level}_S_names")"
		verbose "   (K$level) services: $(eval "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
