#!/usr/bin/env bash

# Copyright (c) 2020 International Business Machines Corporation
# Prepared by: Geert Janssen <geert@us.ibm.com>

# This file is sourced by various top-level scripts that explore
# a source file's call graph. It contains all the shared functionality.

# FIXED:
# Pretty slow execution: uses a call to srcml and xmlstarlet for each newly
# discovered reachable function. Could speed things up by caching the
# xml generated by srcml per function and only repeatedly calling xmlstarlet.

die() {
    echo "(E) ${@}" 1>&2
    exit 1
}

info() {
    [ ${VERBOSE} ] && echo "(I) ${@}" 1>&2
}

FUNCTION="main"			# Name of root function
OUTPUT=
VERBOSE=

for i in "$@"; do
case $i in
    -h|--help)
    echo "Usage: ${SCRIPT_NAME} [-hv] [-f=function] [-o=file] FILE"
    echo -e "  -h|--help:\t show this brief usage summary"
    echo -e "  -f|--function: name of root function"
    echo -e "  -o|--output:\t path to the output file"
    echo -e "  -v|--verbose:\t output informational messages"
    echo
    echo "Option defaults are (empty means not in effect):"
    echo -e "  -f:\t${FUNCTION}"
    echo -e "  -o:\t${OUTPUT:-stdout}"
    echo -e "  -v:\t${VERBOSE}"
    echo
    echo -e "${USAGE}"
    exit 2
    ;;
    -f=*|--function=*)
    FUNCTION="${i#*=}"
    shift
    ;;
    -o=*|--output=*)
    OUTPUT="${i#*=}"
    shift
    ;;
    -v|--verbose)
    VERBOSE=1
    shift
    ;;
    *)
    break;
    ;;
esac
done

# We need an input file (extension is used by srcml):
[[ "$#" < 1 ]] && die "expect a Java, C, C++, or C# file as argument"
# Check if source file exists:
[ -f $1 ] || die "file does not exist"

info "Script '${SCRIPT_NAME}' parameters:"
#info "Script directory: ${SCRIPT_DIR}"                                      
info "Root function: ${FUNCTION}"
info "Output file  : ${OUTPUT:-stdout}"
[ "${VERBOSE}" ] && yesorno="yes" || yesorno="no"
info "Verbose?     : ${yesorno}"

# Quick check for availabilty of srcml and xmlstarlet:
command -v srcml &>/dev/null
[ $? == 0 ] || die "srcml not available; please install"
command -v xmlstarlet &>/dev/null
[ $? == 0 ] || die "xmlstarlet not available; please install"
#command -v xidel &>/dev/null
#[ $? == 0 ] || die "xidel not available; please install"

# Create temp file:
XML=$(mktemp)
trap "/bin/rm -f $XML" EXIT

# All function definitions each as a unit inside the top-level unit:
# (Called only once!)
srcml --xpath="//src:function" $1 -o $XML

# Given (existing) function name return all function calls in its body.
# Searches in XML-annotated version of source file $1 in body of
# <function><name>$2 for all occurrences of <call><name>name.
function calls() {
#    echo $(srcml --xpath="//src:function[src:name=\"$2\"]" $1 \
#         | xidel -s -e '//call/name' -)
    # Get all calls within the body of a given function:
    # Xidel incorrectly treats XML names case-insensitive!
#    xidel -s -e "//function[name=\"$2\"]//call/name" $1
    xmlstarlet sel -N src="http://www.srcML.org/srcML/src" -t -v \
       "//src:function[src:name=\"$2\"]//src:call/src:name" $1
}

# Avoid treating the same (reachable) function more than once:

# Call graph adjacency lists:
declare -A graph		# node name (caller) -> successors (callees)

# DFS numbering of nodes:
next_num=0
declare -A dfs_num		# node name -> number
# inverse:
declare -A dfs_name		# number -> node name

# Multiplicity of A calling B:
declare -A multi		# multi[A,B]

# Depth-first call graph traversal.
# $1: source file name
# $2: name of function to start with
function trace_calls() {
    # Check if already treated:
    [ ${graph[$2]+_} ] && return

    # Hand out dfs number:
    dfs_num[$2]=$next_num
    dfs_name[$next_num]=$2
    ((next_num++))

    # Get list of calls in order of lexical occurrence:
    local CALLS=$(calls $1 $2)

    # Could have multiple calls to same function; count them:
    declare -A rank
    local next_rank=0
    # Unique function names being called:
    local FUNCS=()
    for func in ${CALLS}; do
	# Record multiplicity:
	((multi[$2,$func]++))
         # Build unique names list in original order:
	[ ${rank[$func]+_} ] && continue
	FUNCS[$next_rank]=$func
	rank[$func]=$next_rank
	((next_rank++))
    done

    # Create adjacency list for $2 and also mark treated:
    graph[$2]=${FUNCS[@]}

    for func in ${FUNCS[@]}; do
	trace_calls $1 "${func}"
    done
}

info "Constructing call graph recursively..."
trace_calls "${XML}" "${FUNCTION}"

# Output to file or stdout:
[ "${OUTPUT}" ] && exec 1>"${OUTPUT}"
