Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?

extract the function call chains of specific length

by dwslovedh (Novice)
on Jul 11, 2013 at 14:48 UTC ( #1043743=perlquestion: print w/replies, xml ) Need Help??
dwslovedh has asked for the wisdom of the Perl Monks concerning the following question:

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; } } }

Replies are listed 'Best First'.
Re: extract the function call chains of specific length
by choroba (Bishop) on Jul 11, 2013 at 15:22 UTC
    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; }
    لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

      I tried, and the script worked! Thanks!

Re: extract the function call chains of specific length
by sundialsvc4 (Abbot) on Jul 12, 2013 at 03:34 UTC

    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.

      Thank you for your valuable advice! I will try, thanks again!
Re: extract the function call chains of specific length
by DrHyde (Prior) on Jul 15, 2013 at 11:12 UTC
    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().

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1043743]
Approved by toolic
Front-paged by toolic
Discipulus thanks back and passes around a weis bier in the berghastof hummelei celebrative glass

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (6)
As of 2018-05-25 17:01 GMT
Find Nodes?
    Voting Booth?