extract the function call chains of specific length

[dwslovedh]

Hi,there! I want to extract all the function call chains with specific length in source C codes. For example:

f1 calls (f2)
f2 calls (f3,f4)
f3 calls nothing
f4 calls f5
f5 calls nothing

So f1->f2->f4->f5 is one of the function call chains and the length is 4. If I want to extract all the function call chains with length 3, then the results should be:

f1->f2->f3
f1->f2->f4
f2->f4->f5

The source codes are big and I have gotten all the function call information like above, i.e., f1 calls f2 and saved it in a hash of array. The keys are the caller function names and the value arrays are the callee function names. For the example above, the data structure is:

key value
f1  f2
f2  f3,f4
f3
f4  f5
f5

I tended to use recursion, but was stuck, pls help! The code snippet is:

my %calls; #has all the function call information
my $length = 3; #the length of function chains
my @chain_store; #array of array, to save the chains
while (($key, $value) = each %calls) {
 my @chain = ();
 push @chain, $key;
 get_chains($value, \@chain);
}

sub get_chains {
  my $value = shift;
  my $chain_ref = shift;
  my @chain = @{$chain_ref};
  foreach my $val @{$value} {
    push @chain, $val;
    my $is_present = 1;
    for (my $count = 0; $count < $length; $count++) {
      if (exist($calls{$val})) {
        get_chains($calls{$val})
      } else {
        $is_present = 0; 
        last;
      }
    }
    if ($is_present) {
       push @chain_store, @chain;
    }
  }
}

[choroba]

No recursion needed. Just keep all the possible paths and extend them $length - 1 times:

#!/usr/bin/perl
use warnings;
use strict;

my $length = 3;

my %calls = ( f1 => ['f2'],
              f2 => [qw[f3 f4]],
              f3 => [],
              f4 => ['f5'],
              f5 => [],
            );

my @adepts = map [$_], keys %calls;
for (1 .. $length - 1) {
    @adepts = map {
        my $list = $_;
        map [@$list, $_], @{ $calls{ $list->[-1] } };
    } @adepts;
}

{   local $" = '->';
    print "@$_\n" for @adepts;
}

[dwslovedh]

I tried, and the script worked! Thanks!

[sundialsvc4]

A few years ago, I had to deal with a very similar project ... except that the system to be analyzed consisted of a Devil’s Brew of SAS files, Korn shell scripts, and Tivoli Workload Scheduler (TWS) scripts.   (Don’t ask ... it worked, and they paid, but ick ... and I forevermore shall do worshipful obesiance at the altar of Parse::RecDescent.)

One of the (key, as it turns out ...) ideas that I used was to write one set of scripts to extract the information individually from every script that might be processed.   These are individual, single links.   I stored everything in an SQLite database file.   (Once I grokked the initially-painful lesson that you must use Transactions, SQLite did everything that I could have wished-for.)   Any of the data-extraction scripts could be run or re-run at any time.   All of the chain-building or other scripts worked entirely by issuing queries against this database as their source of information.   They did not use recursion at all, but did create some fairly elaborate data structures.

[dwslovedh]

Thank you for your valuable advice! I will try, thanks again!

[DrHyde]

Assuming that you start with a data structure like this:

  {
    main => [qw(f1 f2 f3 f4 f5)],
    f1   => [qw(f2)],
    f2   => [qw(f3,f4)],
    ...
  }

then I'd use that to create a bunch of perl subroutines that contain the right subroutine calls and which use Devel::StackTrace (or caller() to figure out how they were called and log that. Then just call main().