lib/Language/Zcode/Parser/Perl.pm

filter: Statementstmt 91.2% 114 / 125 Branchbran 87.1% 54 / 62 Conditioncond 85.7% 18 / 21 MC/DCmcdc 76.9% 10 / 13 Subroutinesub 100% 12 / 12 Podpod 20.0% 1 / 5 totaltotal 87.8% 209 / 238 CC 40 SCAR 31.7
CC
40
Cov
89%
find_subs
35.5
packed_address_str
5.1
end_of_dictionary
3.0
CRAP 23.8
« lib/Language/Zcode/Parser/Opcode.pm ↑ Summary lib/Language/Zcode/Parser/TXD.pm »
1 package Language::Zcode::Parser::Perl;
2
3 2 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
4 2 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
5 2 ▶use base qw(Language::Zcode::Parser::Generic);
Subroutine BEGIN: called CC=1 SCAR=0.0
6
7 =head1 NAME
8
9 Language::Zcode::Parser::Perl - Z-code parser in pure Perl
10
11 =head1 DESCRIPTION
12
13 =head2 Finding subroutine starts and ends
14
15 Things we know:
16
17 =over 4
18
19 =item 1a
20
21 We understand the syntax of all opcodes that are in the spec. (modulo bugs)
22
23 =item 1b
24
25 0 is not a legal opcode (almost every other 1-byte number is,
26 depending on version -- but see NOTES)
27
28 =item 2a
29
30 Subs must start at packed addresses. Bytes between subs are always zero
31 (I hope!)
32
33 =item 2b
34
35 Subs must start with a byte 0-15
36
37 =item 2c
38
39 If header byte is zero, next byte CAN'T be a zero, cuz there are
40 no locals so it has to be a command, and 0 isn't a command
41
42 =item 2d
43
44 Subs must be called with call* opcodes, although it is legal to call
45 a variable (like "call_2n sp 1 2")
46
47 =item 3a
48
49 There is no way for the program to get past a ret, rfalse (etc.) or jump
50 (backwards) command without jumping past it.
51
52 =item 3b
53
54 jump opcodes cannot take variable args
55
56 =item 3c
57
58 There may be code after a sub-ender that is not jumped into. This is a (rare,
59 but existent) orphan fragment.
60
61 =back
62
63 The upshot of this is that, if we propose that a sub starts at a given address,
64 we can unambiguously read (the header and) commands until we hit a sub-ender
65 that is not jumped past. If we find unexpected 0 bytes, for example, then we
66 were wrong about the sub's starting address.
67
68 So:
69
70 read a command. (Note if it has a sub call or a jump)
71
72 if next byte is a known start of sub {
73 we finished this sub! Celebrate
74
75 } else if next byte is a 0 {
76 # there must be a sub next
77 if there's more than one 0 {
78 skip to the last 0 in the series
79 again, if we get to known start of sub, we're done
80 }
81 if last 0 is on packed address {
82 start a sub here # 0 local vars, so next byte must be (non-zero) cmd
83 } else if next byte is on packed address and is 1-15 {
84 start a sub at that byte
85 } else error!
86
87 } else if not on packed address OR next byte is not 1-15 { # must be command
88 read next command
89
90 } else { # start doing things I'm less sure about
91 # During this less sure part, if I get a parsing error, try
92 # the other possibility
93 if previous command was a ret, rfalse etc. that we have not jumped past {
94 read sub
95 } else {
96 read command
97 }
98 }
99
100 Also stop if we get to a known string address or end of the file. The
101 first string may be referenced in a sub we don't see, or may not be referenced
102 at all (Zork1 always call print_paddr with variables, not constant string
103 addresses.) so we'll run past the end of the last sub and into the strings.
104
105 Arg to a call is considered the most authoritative demonstration that
106 a sub exists. 0..15 byte at a packed address is slightly less sure, especially
107 if there are no 0 bytes separating it from the previous sub (could be
108 an orphan fragment).
109
110 =cut
111
112 2 ▶use constant SURE => 8;
Subroutine BEGIN: called CC=1 SCAR=0.0
113 2 ▶use constant ALMOST_SURE => 4;
Subroutine BEGIN: called CC=1 SCAR=0.0
114 2 ▶use constant PROBABLE => 2;
Subroutine BEGIN: called CC=1 SCAR=0.0
115 2 ▶use constant MAYBE => 1;
Subroutine BEGIN: called CC=1 SCAR=0.0
116
117 # Note throughout that eat_byte gets a byte and sets PC() to be that byte's
118 # position PLUS ONE
119 # TODO get rid of @todo. Just use
120 # (grep {$prob ^ DONE} sort {$prob} keys %prob)[0]
121 # When finishing a sub, $prob |= DONE
122 # $packed, %end_codes go into main while loop (which becomes subroutine)
123 # $string_min, %prob = try_sub($string_min, %prob);
124 2 ▶sub find_subs {
Subroutine find_subs: called CC=33 SCAR=35.7
Pod undocumented
125 # Only sub we know of right now is (1 byte before)
126 # the start address in the header
127 2 my $main_sub = $Language::Zcode::Util::Constants{first_instruction_address} - 1;
128 2 my @todo = ($main_sub);
129 2 my %prob = ($main_sub => SURE);
130 # Also, try the address just after the dictionary ends
131 2 my $dict_end = &end_of_dictionary;
132 2 ▶ if ($dict_end != $main_sub) {
Branch: 1 branch
BranchTrueFalseTotal
if ($dict_end != $main_sub) 0 2 2
133 0 push @todo, $dict_end;
134 0 $prob{$dict_end} = MAYBE;
135 }
136 # For finding packed addresses
137 2 my $packed = $Language::Zcode::Util::Constants{packed_multiplier};
138 2 my $string_min = $Language::Zcode::Util::Constants{file_length}-1; # min addr of strings
139 2 my @subs;
140 # Codes that can end a routine
141 2 my %end_codes = map {$_ => 1}
142 # Note: only jump can cleanly end a sub, not je & other branch ops
143 qw(ret rfalse rtrue ret_popped print_ret jump quit);
144
145 # We shift subs out. So if we find something we're sure is a sub,
146 # unshift it into the list. If we're not so sure, push it onto the end,
147 # so we won't look at it until after looking at subs we're sure of.
148 2 ▶ while (defined (my $rtn = shift @todo)) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined(my $rtn = shift @todo)) 68 2 70
149 68 my $hr = sprintf('%x', $rtn);
150 # print "Routine $hr ($rtn): ";
151 # Read num_locals -- and read the locals, for v1-4
152 68 eval {&Language::Zcode::Parser::Opcode::parse_sub_header($rtn)};
153 0 ▶ if ($@) { warn $@; delete $prob{$rtn}; next }
Branch: 1 branch
BranchTrueFalseTotal
if ($@) 0 68 68
154 68 my $max_PC = PC(); # we know the sub goes at least until...
155 68 my $last_command = $max_PC; # address of last command in the sub
156 68 while (1) {
157 # changes PC
158 1481 my %command=&Language::Zcode::Parser::Opcode::parse_command;
159 1481 ▶ delete $prob{$rtn}, last unless %command; # unknown opcode
Branch: 1 branch
BranchTrueFalseTotal
unless %command 0 1481 1481
160 1481 $last_command = $command{opcode_address};
161 1481 my $sub_ender = exists $end_codes{$command{opcode}};
162 1481 my $pc = PC();
163
164 1481 ▶ if ($pc >= $string_min) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pc >= $string_min) 0 1481 1481
165 # print "sub ends at $pc, start of strings\n";
166 0 $max_PC = $string_min -1;
167 0 last;
168 }
169
170 # If we can branch to a point later in the code, we know the
171 # sub goes at least until there.
172 # (IRL, you can jump outside a sub, but we're ignoring that.)
173 # jz foo 0/1 will have label = "", cuz it really means "return"
174 1481 ▶ if (exists $command{label} && !exists $command{jump_return}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $command{"label"} and not exists $command{"jump_return"}) 229 1252 1481
Condition100%3/3
exists $command{"label"} and not exists $command{"jump_return"}
!ll&&!rl&&r
12484229
MC/DC100%2/2
exists $command{"label"} and not exists $command{"jump_return"}
exists $command{"label"} not exists $command{"jump_return"}
Truth table100%3/3
A and not(B)
A= exists $command{"label"}B= not exists $command{"jump_return"}
ABresult
0X0
100
111
175 229 my $l = $command{label};
176 229 ▶ die "Illegal to jump to a variable ($pc)!?" if $l =~ /\D/;
Branch: 1 branch
BranchTrueFalseTotal
if $l =~ /\D/ 0 229 229
177 229 ▶ $max_PC = $l if $l > $max_PC;
Branch: 1 branch
BranchTrueFalseTotal
if $l > $max_PC 60 169 229
178 }
179
180 # For call* commands, note addresses of the subs they call
181 1481 ▶ if (exists $command{routine}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $command{"routine"}) 375 1106 1481
182 # p_a_s will return 0/undef if it's not a "useful" call
183 375 ▶ if (my $r = packed_address_str($command{routine}, "routine")) {
Branch: 1 branch
BranchTrueFalseTotal
if (my $r = packed_address_str($command{"routine"}, "routine")) 371 4 375
184 371 ▶ unshift @todo, $r if !exists $prob{$r};
Branch: 1 branch
BranchTrueFalseTotal
unless exists $prob{$r} 59 312 371
185 371 $prob{$r} |= ALMOST_SURE; # pretty sure it's a sub
186 }
187 }
188
189 # Find address of first string - stop parsing routines there!
190 1481 ▶ if (exists $command{packed_address_of_string}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $command{"packed_address_of_string"}) 8 1473 1481
191 8 my $s = $command{packed_address_of_string};
192 8 $s = packed_address_str($s, "packed_address_of_string");
193 8 ▶ if (defined $s && $s < $string_min) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $s and $s < $string_min) 3 5 8
Condition100%3/3
defined $s and $s < $string_min
!ll&&!rl&&r
413
MC/DC100%2/2
defined $s and $s < $string_min
defined $s $s < $string_min
Truth table100%3/3
A and B
A= defined $sB= $s < $string_min
ABresult
0X0
100
111
194 # print "$s < $string_min - new string min\n";
195 3 $string_min = $s;
196 }
197 }
198
199
200 # Now go through a long complicated procedure to see if
201 # we've finished the sub
202
203 # 0 byte means there must be a sub next
204 # (Note: we may change PC() in here)
205 1481 ▶ if ((my $byte = &peek()) == 0) {
Branch: 2 branches
BranchTrueFalseTotal
if ((my $byte = &peek()) == 0) { } 55 1426 1481
elsif ($sub_ender and $max_PC < $pc and not exists $prob{$pc}) { } 3 2835 2838
206 # byte starting next sub must be at packed address
207 # and must be (0 followed by nonzero OR 1..15)
208 # (We also know $packed is always at least 2)
209 # Skip zero or more 0's until byte AFTER me is NOT zero
210 55 ▶ $byte = Language::Zcode::Parser::Opcode::eat_byte()
Branch: 1 branch
BranchTrueFalseTotal
peek() != 0 or do { $byte = Language::Zcode::Parser::Opcode::eat_byte() } 55 108 163
211 until peek() != 0;
212 55 $pc = PC();
213 55 ▶ if ($pc >= $string_min) {
Branch: 1 branch
BranchTrueFalseTotal
if ($pc >= $string_min) 1 54 55
214 # print "sub followed by zeroes and first string $pc\n";
215 1 $max_PC = $string_min -1;
216 1 last;
217 }
218 # If we read 0 byte starting a sub, (numlocals = 0), back up
219 54 ▶ if ($pc % $packed == 1 && $byte == 0) { PC(--$pc); }
Branch: 1 branch
BranchTrueFalseTotal
if ($pc % $packed == 1 and $byte == 0) 11 43 54
Condition66%2/3
$pc % $packed == 1 and $byte == 0
!ll&&!rl&&r
43011
MC/DC50%1/2
$pc % $packed == 1 and $byte == 0
$pc % $packed == 1 $byte == 0
Truth table66%2/3
A and B
A= $pc % $packed == 1B= $byte == 0
ABresult
0X0
100
111
220
221 # ERRORS. If we read a 0 byte, but a new sub doesn't start
222 # at the next packed address, then the *current* sub
223 # we're reading must not really be a sub!
224 54 ▶ if ($pc % $packed || &peek() > 15) { # 0 byte, but no new sub!
Branch: 2 branches
BranchTrueFalseTotal
if ($pc % $packed or &peek() > 15) { } 1 53 54
elsif ($max_PC > $pc) { } 0 53 53
Condition66%2/3
$pc % $packed or &peek() > 15
l!l&&r!l&&!r
0153
MC/DC50%1/2
$pc % $packed or &peek() > 15
$pc % $packed &peek() > 15
Truth table66%2/3
A or B
A= $pc % $packedB= &peek() > 15
ABresult
1X1
011
000
225 1 warn peek(), " at $pc > 15. 0 in middle of sub!\n";
226 1 delete $prob{$rtn};
227 1 last;
228 } elsif ($max_PC>$pc) {
229 0 warn "Max $max_PC > $pc in rtn $rtn. Jump past sub end?\n";
230 0 delete $prob{$rtn};
231 0 last;
232 }
233
234 # Sub to try. May or may not be new. We'll "last" below
235 53 $prob{$pc} |= PROBABLE; # somewhat sure it's a new sub
236
237 # If we *can* finish a sub now, but we don't KNOW there's
238 # another sub starting now, then *probably* we ended sub,
239 # but it might be an orphan code fragment
240 ▶ } elsif ($sub_ender && $max_PC < $pc && !exists $prob{$pc}) {
Condition100%6/6
$sub_ender and $max_PC < $pc and not exists $prob{$pc}
!ll&&!rl&&r
1412113
$sub_ender and $max_PC < $pc
!ll&&!rl&&r
13229014
MC/DC100%3/3
$sub_ender and $max_PC < $pc and not exists $prob{$pc}
$sub_ender $max_PC < $pc not exists $prob{$pc}
Truth table100%4/4
A and B and not(C)
A= $sub_enderB= $max_PC < $pcC= not exists $prob{$pc}
ABCresult
0XX0
10X0
1100
1111
241 3 ▶ if ($byte <=15 && $pc % $packed == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($byte <= 15 and $pc % $packed == 0) { } 2 1 3
Condition66%2/3
$byte <= 15 and $pc % $packed == 0
!ll&&!rl&&r
102
MC/DC50%1/2
$byte <= 15 and $pc % $packed == 0
$byte <= 15 $pc % $packed == 0
Truth table66%2/3
A and B
A= $byte <= 15B= $pc % $packed == 0
ABresult
0X0
100
111
242 # COULD be an orphan code fragment w/ 1..15 byte: very rare
243 # printf "ASSUME ";
244 2 $prob{$pc} |= MAYBE; # not entirely sure it's a new sub
245 } else {
246 # printf "Orphan code fragment: PC %x ($pc)\n",$pc
247 }
248 }
249
250 # We know sub lasts at least until end of command we just read
251 1479 ▶ $max_PC = $pc-1 if $pc > $max_PC;
Branch: 1 branch
BranchTrueFalseTotal
if $pc > $max_PC 811 668 1479
252
253 # Found a new sub here?
254 1479 ▶ if (exists $prob{$pc}) {
Branch: 1 branch
BranchTrueFalseTotal
if (exists $prob{$pc}) 66 1413 1479
255 # print "sub ends at ";
256 # print "start of sub " if $prob{$pc} & ALMOST_SURE;
257 # printf "%x ($pc).\n", $pc;
258 # less sure of these subs; 'push' means try them last
259 66 ▶ push @todo, $pc if $prob{$pc} < ALMOST_SURE;
Branch: 1 branch
BranchTrueFalseTotal
if $prob{$pc} < 4 7 59 66
260 66 last; # Starting a new sub, so stop reading this one
261 } # else keep reading commands
262 }
263
264 68 ▶ if (exists $prob{$rtn}) { # bad subs have been delete()d
Branch: 1 branch
BranchTrueFalseTotal
if (exists $prob{$rtn}) 67 1 68
265 67 my $routine = new Language::Zcode::Parser::Routine $rtn;
266 67 $routine->end($max_PC);
267 67 $routine->last_command_address($last_command);
268 67 push @subs, $routine;
269 # If we made it to the end of a sub, we're pretty sure it's real
270 67 $prob{$rtn} |= ALMOST_SURE; # (if we weren't sure about it already)
271 }
272 }
273
274 2 return sort {$a->address <=> $b->address} @subs;
275 }
276
277 1628 ▶sub PC {
Subroutine PC: called CC=2 SCAR=6.9
Pod undocumented
278 1628 ▶ $Language::Zcode::Parser::Opcode::PC = $_[0] if $_[0];
Branch: 1 branch
BranchTrueFalseTotal
if $_[0] 15 1613 1628
279 1628 return $Language::Zcode::Parser::Opcode::PC
280 }
281 1699 ▶sub peek { $Language::Zcode::Util::Memory[$Language::Zcode::Parser::Opcode::PC] }
Subroutine peek: called CC=1 SCAR=0.0
Pod undocumented
282
283 # Returns undef for situations where we don't get a true address
284 # "@call sp", where we don't know sub address, OR "call 0", which isn't a call
285 383 ▶sub packed_address_str {
Subroutine packed_address_str: called CC=5 SCAR=16.3
Pod undocumented
286 383 my ($address, $key) = @_;
287 383 ▶ return undef if !$address;
Branch: 1 branch
BranchTrueFalseTotal
unless $address 0 383 383
288 383 my %c = %Language::Zcode::Util::Constants;
289 383 my $mult = $c{packed_multiplier};
290 383 my $add;
291 # (Add will be zero for versions not 6 or 7)
292 383 ▶ if ($key eq "routine") {
Branch: 2 branches
BranchTrueFalseTotal
if ($key eq 'routine') { } 375 8 383
elsif ($key eq 'packed_address_of_string') { } 8 0 8
293 375 $add = 8 * $c{routines_offset};
294 } elsif ($key eq "packed_address_of_string") {
295 8 $add = 8 * $c{strings_offset};
296 0 } else { die "Unknown key $key to packed_address_str" }
297
298 # Now actually create the string. Only do calculation for true number
299 383 ▶ if ($address =~ /^\d+$/) {
Branch: 1 branch
BranchTrueFalseTotal
if ($address =~ /^\d+$/) { } 375 8 383
300 375 return $mult * $address + $add;
301 } else {
302 8 return undef;
303 }
304 }
305
306 =head2 end_of_dictionary
307
308 Find the first packed address after the end of the dictionary.
309 (This is a likely place for the lowest-address subroutine.)
310
311 =cut
312
313 2 ▶sub end_of_dictionary {
Subroutine end_of_dictionary: called CC=3 SCAR=11.0
Pod documented
314 2 my $dict = $Language::Zcode::Util::Constants{dictionary_address};
315 2 PC($dict);
316
317 # get token separators
318 2 my $sep_count = Language::Zcode::Parser::Opcode::eat_byte();
319 2 Language::Zcode::Parser::Opcode::eat_byte() for 1..$sep_count;
320
321 # number of bytes for each encoded word
322 # Spec 13.3: this includes the word itself PLUS some data
323 # number of words in the dictionary
324 2 my $entry_length = Language::Zcode::Parser::Opcode::eat_byte();
325 2 my $entry_count = Language::Zcode::Parser::Opcode::eat_word();
326 # Now skip N M-byte words -> first byte AFTER dictionary
327 # Then go to first packed address after that
328 2 my $word_start = PC();
329 2 my $dict_end = $word_start + $entry_count * $entry_length;
330 # printf "Start at $dict (%x). $entry_count $entry_length-byte words.",$dict;
331 # printf "\nEnd at $dict_end (%x)\n", $dict_end;
332 2 my $byte;
333 2 my $packed = $Language::Zcode::Util::Constants{packed_multiplier};
334 2 PC($dict_end);
335 2 ▶ $byte = Language::Zcode::Parser::Opcode::eat_byte()
Branch: 1 branch
BranchTrueFalseTotal
PC() % $packed == 0 or do { $byte = Language::Zcode::Parser::Opcode::eat_byte() } 2 3 5
336 until PC() % $packed == 0;
337 2 $dict_end = PC();
338 # printf "First possible sub after dict is PC $dict_end (%x)\n", $dict_end;
339 2 return $dict_end;
340 }
341
342 =head1 NOTES
343
344 Actually, the remarks on section 14 of the spec say, "The 2OP opcode 0 was
345 possibly intended for setting break-points in debugging (and may be used for
346 this again). It was not nop." So in theory my algorithm may not be right.
347 Oh well.
348
349 =head1 TODO
350
351 This will break if there's data interleaved between the subs.
352 See SPEC comments on section 1.
353
354 Start at the byte after the end of the dictionary. Look at every packed
355 address that's not included in a subroutine I've already found, up until
356 we get to the strings. If I find something that looks like a sub, start
357 parsing commands as above, except with a "not sure" flag set. If we find
358 calls in that sub, follow them, but propagate the "not sure" flag.
359
360 =cut
361
362 2 1;
« lib/Language/Zcode/Parser/Opcode.pm ↑ Summary lib/Language/Zcode/Parser/TXD.pm »