Introduction

Noted in my diary entry on Wednesday, Oct 8th 2014, I've implemented a tool to produce a function Callgraph – an indended list of shell functions calling other shell functions.

This tool is part of my Commonplace Book

Example

Today I built a callgraph process in my newly acquired python experience.

The problem is to visualize a function's calling hierarchy in context: who does it call; who calls on it?

The top of the heap on this one is do_fun_uses:

do_fun_uses () { echo $1 $(fun_uses $1 | grep -v "^$1$" ); }
fun_uses    () { foreach alltype $(fbdy $* | fun_clean) |
                     awk '$1 ~ /function/ { print $2 }'
}
tpl () { cat ${*:--} | tr -s ' \t' '\n'; }
fun_names   () { grep '^[a-z][a-zA-Z0-9_-][a-zA-Z0-9_-]*$'; }
alltype () 
{ 
    function _alltype () 
    { 
        echo $(type -t $1) $1
    };
    foreach _alltype $* | sort -u
}
fun_clean () 
{ 
    cat ${*:--} | sed '
        s/comment .*/comment/
        s/trace_call .*/trace_call/
    ' | tpl | sed '
      s/;$//
      s/)*$//
      s/^$(//
      s/^<(//
      ' | sort -u | fun_names
}

Here's an example:

$  foreach do_fun_uses $(functions booklib)  | callgraph.py

And here is the callgraph for do_fun_uses:

do_fun_uses
    fun_uses
        alltype
            foreach
        fbdy
            f_fnx
            foreach
            fx_fnb
                f_fnx
                fun_oneline
        foreach
        fun_clean
            fun_names
            tpl

Now I can examine the functions at the top of a call tree to see if they are main functions, like commands, and set them aside for a thorough documentation and rigorous testing. Many are likely command line utilities which fit in some package or other. Some may be left-overs and should be shelved.

Code

python

#!/usr/bin/env python

import sys

descended = { "": [] }

def descendents( person, n, children):

    global descended

    # print "    "*n + person
    # OR for OrgMode **..
    # print "*"*(n+1) + " " + person
    print "   "*n + "* " + person

    if not person in descended:
        descended[person] = 1
        if person in children:
            for c in children[person]:
                descendents (c, n+1, children)

def callgraph ():
    """
    reads the STDIN with lines of a calling function (parent)
    followed by a list of one or more called functions (children)
    producing a callgraph on the STDOUT, where a function's
    descendents are displayed only the first time they appear.
    """

    children = { }
    parents  = { }
    people   = []             # list of parents and children

    for line in sys.stdin:

        words  = line.split()
        mother = words[0]
        kidsof = words[1:]

        # the mother knows her children
        if not mother in children:
            children[mother] = []

        children[mother] += kidsof

        if not mother in people:
            people.append( mother)

        for indiv in kidsof:
            if not indiv in people:
                people.append( indiv)

            # individuals may have many parents
        if not indiv in parents:
                parents[indiv] = [mother]
            else:
                parents[indiv].append( mother)

    for indiv in people:
        if indiv not in parents:
            # the indiv is either adam or eve, so
            print # a blank line
            descendents( indiv, 0, children)

callgraph() 

shell

TODO my_callgraph should take either files or functions

if the first argument is a function, they all are (assumed) functions, and a commplete list, such as collected from:

app_fun Top_Function | tee .y   

funlib

function callgraph_iports
{
    echo report_notargcount newest functions 
    : implict report_* and trace_* families
}
function callgraph_eg
{ 
    in=~/tmp/callgraph.in;
    out=~/tmp/callgraph.out;
    report_notargcount 1 $# function ... && return 1;
    foreach fun_call $* | tee $in | callgraph | egrep -v '(comment|trace_)' | tee $out;
    comment in: $in;
    comment out: $out
}
function my_callgraph
{ 
    file=~/tmp/callgraph.out;
    trace_call $file : $*;
    newest $file $* || { 
        for f in $*;
        do
            . $f;
        done;
        callgraph_eg $(functions $*)
    };
    ( 
      sed 5q ~/Dropbox/dbx.org | sed "/TITLE/{ s=Dropbox=${1:-~$(rwd)}= }"
      printf "#+OPTIONS: ^:nil\n", $1
      printf "* reference\n[[~/Dropbox/commonplace/software/callgraph.org::*python][python source]]\n"
      printf "* the callgraph\n"
      cat $file 
    ) > $1.org
}
function fun_call
{ 
    fun_uses $1 | awk "\$1 ~ /^$1\$/ { next }; { print \"$1\", \$1 }"
}
function fun_uses
{ 
    foreach alltype $(fbdy $* | fun_clean | fun_candidates  | fun_names) | awk '$1 ~ /function/ { print $2 }'
}
function fun_clean
{ 
    sed '

        s/$(/\
&/g' $* | sed '

    s/report_\([a-zA-Z][a-z0-9A-Z]*\) .*/report_\1/
        s/comment .*/comment/
        s/trace_call .*/trace_call/
        s/usage .*/usage/
    '
}
function fun_candidates
{ 
    cat ${*--} | tpl | sed '
      s/;$//
      s/)*$//
      s/^$(//
      s/^<(//
      ' | sort -u
}
function fun_names
{ 
    grep '^[a-z][a-za-z0-9_-][a-za-z0-9_-]*$'
}

Reader's Guide

TBD

Comments