Création d'une arborescence de données (doit être native) en Perl pour représenter une arborescence d'appels située dans un fichier externe
https://stackoverflow.com/questions/4891453
-
28-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Voici un exemple du fichier.
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
Le ... représente la profondeur de l'appel. Le nom du fichier après la ligne indique le nom du fichier et le numéro de ligne à partir duquel il a été appelé dans le parent. Je peux analyser le fichier. Ce que j'essaie de faire une fois que j'ai analysé le fichier, c'est de placer les données dans un arbre n-aire. Je fais une analyse de couplage de données et de couplage de contrôle et j'ai déjà collecté toutes les données d'ensemble / d'utilisation pour toutes les variables de la construction. Je dois maintenant être capable de traverser l'arbre et, en fonction de la profondeur, déterminer s'il existe des situations d'ensemble avant utilisation ou des situations d'ensemble mais non utilisées. Je pensais qu'une traversée d'arbre serait la plus logique.
Voici un exemple des données collectées:
$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
J'ai aussi un tableau avec tous les noms de variables. Exemple abrégé:
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'
};
Mon plus grand obstacle est de trouver les structures de données et les algorithmes appropriés pour accomplir cette tâche.
J'ai pensé qu'une première recherche approfondie d'un arbre n-aire me donnerait ce que je veux.
Voici ma solution finale:
#!/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;
SORTIE ressemble à ceci:
......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
À partir de ce fichier 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
Utilisation de ce sous-programme:
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
La solution
Pour les structures de données, l'une des plus grandes puissances de perl est l'imbrication arbitraire des structures.Ainsi, plutôt que d'avoir une seule variable contenant toutes les données de toutes les notes, vous pouvez avoir des «sous-nœuds» à l'intérieur de leurs parents.
Disons que vous avez eu un hachage pour une entrée:
%node1 = ( name => 'ALPHA_MAX_MC_SSM', file => 'arltst.asm', line => 42 );
Le code ci-dessus créera un nœud simple pour stocker des données. Mais vous pouvez en fait stocker plus de données à l'intérieur de celui-ci.Un "nœud enfant":
%node2 = (
name => 'ACTUAL_ALT',
file => 'foo.asm',
line => 2001
);
$node1{children}[0] = \%node2;
Ensuite, vous avez un nœud enfant ( 'children' ) dans le premier nœud qui est un tableau de tous ses enfants.Vous pouvez accéder à la date dans l'enfant directement comme:
$node1{'children'}[0]{'name'};
Pour comprendre cela et comment cela fonctionne, vous devez vous renseigner sur les références Perl et les types de données Perl.Il faut un peu de temps en tant que nouveau programmeur perl pour obtenir les concepts, mais une fois que vous l'avez compris, vous pouvez faire des programmes rapides incroyablement puissants pour capturer des données hiérarchiques complexes et les traiter.
Autres conseils
Voici comment imprimer la structure que vous avez construite en utilisant la réponse de Wes.
Une fois les données traitées, vous vous retrouvez avec quelque chose comme ceci:
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 },
],
}
]
}
);
La structure est récursive et la clé children pointe vers arrayref d'un autre hachage.Pour imprimer ceci, vous avez besoin d'un code récursif:
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);
}
}
}
Pour les données ci-dessus, le code sort
......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
