Creating a tree data structure (Has to be native) in Perl to represent a call tree that is located in a external file

Question

Here is an example of the file.

  powrup.asm            POWER_UP
                  ......EXTERNAL_RAM_ADDRESSING_CHECK    powrup.asm:461
                  ......EXRAM    powrup.asm:490
                  ......INRAM    powrup.asm:540
                  ......OUTPUT_TEST    powrup.asm:573
                  ............AD_READ    douttst.asm:276
                  ............AD_READ    douttst.asm:366
                  ......OUTPUT2_TEST    powrup.asm:584
                  ............AD_READ    douttst2.asm:253
                  ............AD_READ    douttst2.asm:342
                  ......OUTPUT3_TEST    powrup.asm:599
                  ............AD_READ    douttst3.asm:307
                  ............AD_READ    douttst3.asm:398
                  ......INPUT_TEST    powrup.asm:614
                  ......PROGRAM_PINS2_INPUT    powrup.asm:629
                  ......ARINC_TEST    powrup.asm:633
                  ............ARINC_LEVEL_TEST    artest.asm:178
                  ..................AD_READ    arltst.asm:204
                  ..................AD_READ    arltst.asm:250
                  ..................AD_READ    arltst.asm:300
                  ..................AD_READ    arltst.asm:346
                  ..................AD_READ    arltst.asm:396
                  ..................AD_READ    arltst.asm:442
                  ............ARINC_READ    artest.asm:209
                  ............ARINC_WORD_TXRX_TEST    artest.asm:221
                  ..................ARINC_OUT    artxrx.asm:207
                  ..................ARINC_READ    artxrx.asm:221
                  ............ARINC_READ    artest.asm:251
                  ............ARINC_WORD_TXRX_TEST    artest.asm:263
                  ..................ARINC_OUT    artxrx.asm:207
                  ..................ARINC_READ    artxrx.asm:221
                  ......PROGRAM_PINS2_INPUT    powrup.asm:640
                  ......PROGRAM_PIN_TEST    powrup.asm:642
                  ......PT_RCVR_BITE    powrup.asm:645
                  ............AD_READ10    ptbite.asm:225
                  ..................AD_READ    adread10.asm:141
                  ............AD_READ10    ptbite.asm:308
                  ..................AD_READ    adread10.asm:141
                  ............AD_READ10    ptbite.asm:384
                  ..................AD_READ    adread10.asm:141
                  ............AD_READ10    ptbite.asm:467
                  ..................AD_READ    adread10.asm:141
                  ............AD_READ10    ptbite.asm:542
                  ..................AD_READ    adread10.asm:141
                  ............AD_READ10    ptbite.asm:622
                  ..................AD_READ    adread10.asm:141
                  ......PROGRAM_PINS2_INPUT    powrup.asm:653
                  ......EXEC_INIT    powrup.asm:663

The ... represents the call depth. The file name after the line indicates the file name and the line number it was called from in the parent. I can parse the file. What I am trying to do once I have parsed the file is put the data in a n-ary tree. I am doing a Data coupling and Control Coupling analysis and have already collected all the set/use data for the all the variables in the build. I need to now be able to traverse the tree and based on the depth figure out if there are any set before use situations or any set but not used situations. I thought a tree traversal would make the most sense.

Here is an example of the of the collected data:

$hash_DB{'alt_deviation_evaluation.asm->ALT_STATUS'} = [
   'alt_deviation_evaluation.asm',
   'ALT_STATUS',
   '1.1',
   1,
   "",
   "",
   "135,188,202,242",
   "130,144"
];

'alt_deviation_evaluation.asm->ALT_STATUS' is the file name and variable name.

   'alt_deviation_evaluation.asm', File name
   'ALT_STATUS', Variable name
   '1.1',   versions of file
   1,       indicates has been processed
   "",     not used (maybe in future)
   "",     not used  (maybe in future)
   "135,188,202,242", variable Set line numbers for this fileVariable
   "130,144"          Variable Use line number for this file/Variable

I also have an array with all the variable names. Shortened example:

our @vars_list = (
  'A429_TX_BUFFER_LENGTH',
  'A429_TX_INPUT_BUFFER',
  'A429_TX_INT_MASK',
  'ABS_ALT_DIFF',
  'ACTUAL_ALT',
  'ADDRESS_FAIL',
  'AD_CONV_FAIL',
  'AD_CONV_SIGNAL',
  'AD_DATA',
  'AD_FAIL',
  'AD_STATUS',
  'AIR_MODE',
  'AIR_MODE_COUNT',
  'AIR_MODE_LAST',
  'ALPHA_COR_SSM',
  'ALPHA_EC_SSM',
  'ALPHA_GRAD_SSM',
  'ALPHA_LE_SSM',
  'ALPHA_LG_SSM',
  'ALPHA_MAX_MC_SSM'
}; 

My biggest hurdle is figuring out the proper data structures and algorithms to accomplish this task.

I figured a depth first search of a n-ary tree would give me what I want.

Here is my final solution:

#!/usr/local/bin/perl
# !/usr/bin/perl
use Data::Dumper; #!!!
sub Create_Tree;
sub Treverse;

#for my $node (@TREE) {
#   print_node($node[0], 1);
#}


#Main

our @TREE;
Create_Tree("call_tree.small_01.txt");
my $str = Dumper @TREE;
$str =~ s/^(\s+)/' 'x(length($1)>>2)/meg;
#print "\n\n=======================================\n$str"; #!!!
#print "\n\n=======================================\n" . (Dumper @TREE); #!!!

#print "Arr = @TREE, SZ = $#TREE\n\n";
Treverse(\@TREE,1);

sub Create_Tree
{
  my ($call_tree) = @_;
  my @stack;
  my ($old_depth, $p_arr) = (0, \@TREE);

  open(IN, "< $call_tree" ) or die "Can not open '$call_tree' for input.\n";
  for (<IN>)
  {
    if (m/^(\s*)(\S+)\s*=>\s*(\S+):(\d+)/ or m/^(\s*)(\S+)()()/)
    {
      my ($depth, $callee_fn, $caller_fn, $ln, $diff) = ($1, $2, $3, $4, 0);
      $depth = int(length($depth) / 6);
      $diff  = $depth - $old_depth;

      if ($diff == 1)
      {
        push @stack, $p_arr;
        $p_arr = \@{$$p_arr[$#{$p_arr}]{children}};
      }
      elsif ($diff < 0)
      {
        $p_arr = pop @stack while ++$diff <= 0;
      }
      elsif ($diff > 1)
      {
        die "Incorrectly formated call tree:\n  $_\n";
      }

      push @$p_arr, {
          caller    => $caller_fn,
          called_by => $callee_fn,
          at_line   => $ln
      };

      $old_depth = $depth;
    }
  }

  close IN;
}
exit;

OUTPUT look like this:

......file1

    ............file1    101:A
    ..................XXX.AA    102:AA
    ........................XXX.AAA    103:AAA
    ........................XXX.AAB    104:AAB
    ..............................XXX.AABA    105:AABA
    ..................XXX.AB    106:AB
    ........................XXX.ABA    107:ABA
    ............file1    108:B
    ..................XXX.BA    109:BA
    ........................XXX.BAA    110:BAA
    ........................XXX.BAB    111:BAB

From this call_tree.txt file:

file1
      A => file1:101
            AA => XXX.AA:102
                  AAA => XXX.AAA:103
                  AAB => XXX.AAB:104
                        AABA => XXX.AABA:105
            AB => XXX.AB:106
                  ABA => XXX.ABA:107
      B => file1:108
            BA => XXX.BA:109
                  BAA => XXX.BAA:110
                  BAB => XXX.BAB:111

Using this subroutine:

sub Treverse
{
  my ($p_arr, $level) = @_; 
  for (my $ind=0; $ind<=$#{$p_arr}; $ind++)
  {

        print "." x ($level*6);
        if ($$p_arr[$ind]{'caller'} ne "") {print "$$p_arr[$ind]{'caller'}" . " " x 4;}
        if ($$p_arr[$ind]{'at_line'} ne "") {print "$$p_arr[$ind]{'at_line' }" . ":";}
        if ($$p_arr[$ind]{'called_by'} ne "") {print "$$p_arr[$ind]{'called_by'}" . "\n";}


    Treverse(\@{$$p_arr[$ind]{children}}, $level +1) if defined $$p_arr[$ind]{children};

  }
}
# END of Treverse

Answer 1

For data structures, one of the biggest powers of perl is arbitrary nesting of structures. Thus, rather than have a single variable that contains all the data for all the notes you can have "subnodes" inside their parents.

Lets say you had a hash for one entry:

%node1 = (
  name => 'ALPHA_MAX_MC_SSM',
  file => 'arltst.asm',
  line => 42
);

The above code will create a nice simply node to store data in. But you can actually store more data inside that one itself. A "child node":

%node2 =   (
  name => 'ACTUAL_ALT',
  file => 'foo.asm',
  line => 2001
);

$node1{children}[0] = \%node2;

Then you have a child node ('children') in the first node that is an array of all it's children. You can access date in the child directly like:

$node1{'children'}[0]{'name'};

To understand this and how it works you need to read up on perl references and the perl data types. It takes a bit as a new perl programmer to get the concepts, but once you get it you can do amazingly powerful quick programs snarfing up complex hierarchical data and processing it.

Answer 2

Here is how to print the structure you built using Wes's answer.

Once processed the data, you end up with something like this:

my @nodes = (
    {   name => 'ARINC_TEST', file => 'powrup.asm', line => 633,
        children => [
            {   name => 'ARINC_LEVEL_TEST', file => 'artest.asm', line => 178,
                children => [
                    { name => 'AD_READ', file => 'arltst.asm', line => 204 },
                    { name => 'AD_READ', file => 'arltst.asm', line => 250 },
                    { name => 'AD_READ', file => 'arltst.asm', line => 300 },
                    { name => 'AD_READ', file => 'arltst.asm', line => 346 },
                    { name => 'AD_READ', file => 'arltst.asm', line => 396 },
                    { name => 'AD_READ', file => 'arltst.asm', line => 442 },
                ],
            },
            {   name => 'ARINC_READ', file => 'artest.asm', line => 209,
                children => [],
            },
            {   name => 'ARINC_WORD_TXRX_TEST', file => 'artest.asm', line => 221,
                children => [
                    { name => 'ARINC_OUT',  file => 'artxrx.asm', line => 207 },
                    { name => 'ARINC_READ', file => 'artxrx.asm', line => 221 },
                ],
            }
        ]
    }
);

The structure is recursive and children key point to arrayref of another hash. To print this out, you need recursive code:

for my $node (@nodes) {
    print_node($node, 1);
}

sub print_node {
    my ($node, $level) = @_;

    # the node itself
    print "." x ($level*6)
        , $node->{name}, " " x 4
        , $node->{file}, ":"
        , $node->{line}, "\n";

    # recurse for children
    if(defined $node->{children}) {
        for my $child (@{ $node->{children} }) {
            print_node($child, $level + 1);
        }
    }
}

For data above, the code outputs

......ARINC_TEST    powrup.asm:633
............ARINC_LEVEL_TEST    artest.asm:178
..................AD_READ    arltst.asm:204
..................AD_READ    arltst.asm:250
..................AD_READ    arltst.asm:300
..................AD_READ    arltst.asm:346
..................AD_READ    arltst.asm:396
..................AD_READ    arltst.asm:442
............ARINC_READ    artest.asm:209
............ARINC_WORD_TXRX_TEST    artest.asm:221
..................ARINC_OUT    artxrx.asm:207
..................ARINC_READ    artxrx.asm:221