algorithm - 在 Perl 中创建树数据结构(必须是 native 的)以表示位于外部文件中的调用树

Question

这是该文件的示例。

  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

...代表调用深度。行后的文件名表示文件名以及它在父级中调用的行号。我可以解析文件。解析文件后，我要做的是将数据放入 n 叉树中。我正在进行数据耦合和控制耦合分析，并且已经为构建中的所有变量收集了所有设置/使用数据。我现在需要能够遍历树并根据深度确定是否有任何使用前设置的情况或任何设置但未使用的情况。我认为树遍历最有意义。

以下是所收集数据的示例:

$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

我还有一个包含所有变量名称的数组。缩短示例:

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

我最大的障碍是找出合适的数据结构和算法来完成这项任务。

我认为对 n 元树进行深度优先搜索会得到我想要的结果。

这是我的最终解决方案:

#!/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;

输出看起来像这样:

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

来自这个 call_tree.txt 文件:

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

使用这个子程序:

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

以下是如何打印您使用 Wes 的答案构建的结构。

一旦处理完数据，您最终会得到这样的结果:

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 },
                ],
            }
        ]
    }
);

该结构是递归的，children key 指向另一个哈希的 arrayref。要打印出来，您需要递归代码:

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

对于上面的数据，代码输出

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