a Callgraph

1. Introduction
2. Example
3. Code
- 3.1. python
- 3.2. shell
4. Reader's Guide
5. Comments

1 Introduction

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

2 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.

3 Code

3.1 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()

3.2 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_-]*$'
}

4 Reader's Guide

TBD