1 /* expression.c: A numeric expression
2 Copyright (c) 2003-2016 Philip Kendall
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
17
18 Author contact information:
19
20 E-mail: philip-fuse@shadowmagic.org.uk
21
22 */
23
24 #include <config.h>
25
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29
30 #include "debugger_internals.h"
31 #include "fuse.h"
32 #include "mempool.h"
33 #include "ui/ui.h"
34 #include "utils.h"
35
36 typedef enum expression_type {
37
38 DEBUGGER_EXPRESSION_TYPE_INTEGER,
39 DEBUGGER_EXPRESSION_TYPE_UNARYOP,
40 DEBUGGER_EXPRESSION_TYPE_BINARYOP,
41 DEBUGGER_EXPRESSION_TYPE_SYSVAR,
42 DEBUGGER_EXPRESSION_TYPE_VARIABLE,
43
44 } expression_type;
45
46 enum precedence_t {
47
48 /* Lowest precedence */
49 PRECEDENCE_LOGICAL_OR,
50 PRECEDENCE_LOGICAL_AND,
51 PRECEDENCE_BITWISE_OR,
52 PRECEDENCE_BITWISE_XOR,
53 PRECEDENCE_BITWISE_AND,
54 PRECEDENCE_EQUALITY,
55 PRECEDENCE_COMPARISON,
56 PRECEDENCE_ADDITION,
57 PRECEDENCE_MULTIPLICATION,
58 PRECEDENCE_NEGATE,
59 PRECEDENCE_DEREFERENCE,
60
61 PRECEDENCE_ATOMIC,
62 /* Highest precedence */
63
64 };
65
66 struct unaryop_type {
67
68 int operation;
69 debugger_expression *op;
70
71 };
72
73 struct binaryop_type {
74
75 int operation;
76 debugger_expression *op1, *op2;
77
78 };
79
80 struct debugger_expression {
81
82 expression_type type;
83 enum precedence_t precedence;
84
85 union {
86 int integer;
87 struct unaryop_type unaryop;
88 struct binaryop_type binaryop;
89 char *variable;
90 int system_variable;
91 } types;
92
93 };
94
95 static libspectrum_dword evaluate_unaryop( struct unaryop_type *unaryop );
96 static libspectrum_dword evaluate_binaryop( struct binaryop_type *binary );
97
98 static int deparse_unaryop( char *buffer, size_t length,
99 const struct unaryop_type *unaryop );
100 static int deparse_binaryop( char *buffer, size_t length,
101 const struct binaryop_type *binaryop );
102 static int
103 brackets_necessary( int top_operation, debugger_expression *operand );
104 static int is_non_associative( int operation );
105
106 static enum precedence_t
unaryop_precedence(int operation)107 unaryop_precedence( int operation )
108 {
109 switch( operation ) {
110
111 case '!': case '~': case '-': return PRECEDENCE_NEGATE;
112
113 case DEBUGGER_TOKEN_DEREFERENCE:
114 return PRECEDENCE_DEREFERENCE;
115
116 default:
117 ui_error( UI_ERROR_ERROR, "unknown unary operator %d", operation );
118 fuse_abort();
119 }
120 }
121
122 static enum precedence_t
binaryop_precedence(int operation)123 binaryop_precedence( int operation )
124 {
125 switch( operation ) {
126
127 case DEBUGGER_TOKEN_LOGICAL_OR: return PRECEDENCE_LOGICAL_OR;
128 case DEBUGGER_TOKEN_LOGICAL_AND: return PRECEDENCE_LOGICAL_AND;
129 case '|': return PRECEDENCE_BITWISE_OR;
130 case '^': return PRECEDENCE_BITWISE_XOR;
131 case '&': return PRECEDENCE_BITWISE_AND;
132 case '+': case '-': return PRECEDENCE_ADDITION;
133 case '*': case '/': return PRECEDENCE_MULTIPLICATION;
134
135 case DEBUGGER_TOKEN_EQUAL_TO:
136 case DEBUGGER_TOKEN_NOT_EQUAL_TO:
137 return PRECEDENCE_EQUALITY;
138
139 case '<': case '>':
140 case DEBUGGER_TOKEN_LESS_THAN_OR_EQUAL_TO:
141 case DEBUGGER_TOKEN_GREATER_THAN_OR_EQUAL_TO:
142 return PRECEDENCE_COMPARISON;
143
144 default:
145 ui_error( UI_ERROR_ERROR, "unknown binary operator %d", operation );
146 fuse_abort();
147 }
148 }
149
150 debugger_expression*
debugger_expression_new_number(libspectrum_dword number,int pool)151 debugger_expression_new_number( libspectrum_dword number, int pool )
152 {
153 debugger_expression *exp;
154
155 exp = mempool_new( pool, debugger_expression, 1 );
156
157 exp->type = DEBUGGER_EXPRESSION_TYPE_INTEGER;
158 exp->precedence = PRECEDENCE_ATOMIC;
159 exp->types.integer = number;
160
161 return exp;
162 }
163
164 debugger_expression*
debugger_expression_new_binaryop(int operation,debugger_expression * operand1,debugger_expression * operand2,int pool)165 debugger_expression_new_binaryop( int operation, debugger_expression *operand1,
166 debugger_expression *operand2, int pool )
167 {
168 debugger_expression *exp;
169
170 exp = mempool_new( pool, debugger_expression, 1 );
171
172 exp->type = DEBUGGER_EXPRESSION_TYPE_BINARYOP;
173 exp->precedence = binaryop_precedence( operation );
174
175 exp->types.binaryop.operation = operation;
176 exp->types.binaryop.op1 = operand1;
177 exp->types.binaryop.op2 = operand2;
178
179 return exp;
180 }
181
182 debugger_expression*
debugger_expression_new_unaryop(int operation,debugger_expression * operand,int pool)183 debugger_expression_new_unaryop( int operation, debugger_expression *operand,
184 int pool )
185 {
186 debugger_expression *exp;
187
188 exp = mempool_new( pool, debugger_expression, 1 );
189
190 exp->type = DEBUGGER_EXPRESSION_TYPE_UNARYOP;
191 exp->precedence = unaryop_precedence( operation );
192
193 exp->types.unaryop.operation = operation;
194 exp->types.unaryop.op = operand;
195
196 return exp;
197 }
198
199 debugger_expression*
debugger_expression_new_system_variable(const char * type,const char * detail,int pool)200 debugger_expression_new_system_variable( const char *type, const char *detail,
201 int pool )
202 {
203 debugger_expression *exp;
204 int system_variable;
205
206 system_variable = debugger_system_variable_find( type, detail );
207 if( system_variable == -1 ) {
208 ui_error( UI_ERROR_WARNING, "System variable %s:%s not known", type,
209 detail );
210 return NULL;
211 }
212
213 exp = mempool_new( pool, debugger_expression, 1 );
214
215 exp->type = DEBUGGER_EXPRESSION_TYPE_SYSVAR;
216 exp->precedence = PRECEDENCE_ATOMIC;
217 exp->types.system_variable = system_variable;
218
219 return exp;
220 }
221
222 debugger_expression*
debugger_expression_new_variable(const char * name,int pool)223 debugger_expression_new_variable( const char *name, int pool )
224 {
225 debugger_expression *exp;
226
227 exp = mempool_new( pool, debugger_expression, 1 );
228
229 exp->type = DEBUGGER_EXPRESSION_TYPE_VARIABLE;
230 exp->precedence = PRECEDENCE_ATOMIC;
231 exp->types.variable = mempool_strdup( pool, name );
232
233 return exp;
234 }
235
236 void
debugger_expression_delete(debugger_expression * exp)237 debugger_expression_delete( debugger_expression *exp )
238 {
239 switch( exp->type ) {
240
241 case DEBUGGER_EXPRESSION_TYPE_INTEGER:
242 case DEBUGGER_EXPRESSION_TYPE_SYSVAR:
243 break;
244
245 case DEBUGGER_EXPRESSION_TYPE_UNARYOP:
246 debugger_expression_delete( exp->types.unaryop.op );
247 break;
248
249 case DEBUGGER_EXPRESSION_TYPE_BINARYOP:
250 debugger_expression_delete( exp->types.binaryop.op1 );
251 debugger_expression_delete( exp->types.binaryop.op2 );
252 break;
253
254 case DEBUGGER_EXPRESSION_TYPE_VARIABLE:
255 libspectrum_free( exp->types.variable );
256 break;
257 }
258
259 libspectrum_free( exp );
260 }
261
262 debugger_expression*
debugger_expression_copy(debugger_expression * src)263 debugger_expression_copy( debugger_expression *src )
264 {
265 debugger_expression *dest;
266
267 dest = libspectrum_new( debugger_expression, 1 );
268 if( !dest ) return NULL;
269
270 dest->type = src->type;
271 dest->precedence = src->precedence;
272
273 switch( dest->type ) {
274
275 case DEBUGGER_EXPRESSION_TYPE_INTEGER:
276 dest->types.integer = src->types.integer;
277 break;
278
279 case DEBUGGER_EXPRESSION_TYPE_UNARYOP:
280 dest->types.unaryop.operation = src->types.unaryop.operation;
281 dest->types.unaryop.op = debugger_expression_copy( src->types.unaryop.op );
282 if( !dest->types.unaryop.op ) {
283 libspectrum_free( dest );
284 return NULL;
285 }
286 break;
287
288 case DEBUGGER_EXPRESSION_TYPE_BINARYOP:
289 dest->types.binaryop.operation = src->types.binaryop.operation;
290 dest->types.binaryop.op1 =
291 debugger_expression_copy( src->types.binaryop.op1 );
292 if( !dest->types.binaryop.op1 ) {
293 libspectrum_free( dest );
294 return NULL;
295 }
296 dest->types.binaryop.op2 =
297 debugger_expression_copy( src->types.binaryop.op2 );
298 if( !dest->types.binaryop.op2 ) {
299 debugger_expression_delete( dest->types.binaryop.op1 );
300 libspectrum_free( dest );
301 return NULL;
302 }
303 break;
304
305 case DEBUGGER_EXPRESSION_TYPE_SYSVAR:
306 dest->types.system_variable = src->types.system_variable;
307 break;
308
309 case DEBUGGER_EXPRESSION_TYPE_VARIABLE:
310 dest->types.variable = utils_safe_strdup( src->types.variable );
311 break;
312 }
313
314 return dest;
315 }
316
317 libspectrum_dword
debugger_expression_evaluate(debugger_expression * exp)318 debugger_expression_evaluate( debugger_expression *exp )
319 {
320 switch( exp->type ) {
321
322 case DEBUGGER_EXPRESSION_TYPE_INTEGER:
323 return exp->types.integer;
324
325 case DEBUGGER_EXPRESSION_TYPE_UNARYOP:
326 return evaluate_unaryop( &( exp->types.unaryop ) );
327
328 case DEBUGGER_EXPRESSION_TYPE_BINARYOP:
329 return evaluate_binaryop( &( exp->types.binaryop ) );
330
331 case DEBUGGER_EXPRESSION_TYPE_SYSVAR:
332 return debugger_system_variable_get( exp->types.system_variable );
333
334 case DEBUGGER_EXPRESSION_TYPE_VARIABLE:
335 return debugger_variable_get( exp->types.variable );
336
337 }
338
339 ui_error( UI_ERROR_ERROR, "unknown expression type %d", exp->type );
340 fuse_abort();
341 }
342
343 static libspectrum_dword
evaluate_unaryop(struct unaryop_type * unary)344 evaluate_unaryop( struct unaryop_type *unary )
345 {
346 switch( unary->operation ) {
347
348 case '!': return !debugger_expression_evaluate( unary->op );
349 case '~': return ~debugger_expression_evaluate( unary->op );
350 case '-': return -debugger_expression_evaluate( unary->op );
351
352 case DEBUGGER_TOKEN_DEREFERENCE:
353 return readbyte_internal( debugger_expression_evaluate( unary->op ) );
354
355 }
356
357 ui_error( UI_ERROR_ERROR, "unknown unary operator %d", unary->operation );
358 fuse_abort();
359 }
360
361 static libspectrum_dword
evaluate_binaryop(struct binaryop_type * binary)362 evaluate_binaryop( struct binaryop_type *binary )
363 {
364 switch( binary->operation ) {
365
366 case '+': return debugger_expression_evaluate( binary->op1 ) +
367 debugger_expression_evaluate( binary->op2 );
368
369 case '-': return debugger_expression_evaluate( binary->op1 ) -
370 debugger_expression_evaluate( binary->op2 );
371
372 case '*': return debugger_expression_evaluate( binary->op1 ) *
373 debugger_expression_evaluate( binary->op2 );
374
375 case '/': {
376 libspectrum_dword op2 = debugger_expression_evaluate( binary->op2 );
377 if( op2 == 0 ) {
378 ui_error( UI_ERROR_ERROR, "divide by 0" );
379 return 0;
380 }
381 return debugger_expression_evaluate( binary->op1 ) / op2;
382 }
383
384 case DEBUGGER_TOKEN_EQUAL_TO:
385 return debugger_expression_evaluate( binary->op1 ) ==
386 debugger_expression_evaluate( binary->op2 );
387
388 case DEBUGGER_TOKEN_NOT_EQUAL_TO:
389 return debugger_expression_evaluate( binary->op1 ) !=
390 debugger_expression_evaluate( binary->op2 );
391
392 case '>': return debugger_expression_evaluate( binary->op1 ) >
393 debugger_expression_evaluate( binary->op2 );
394
395 case '<': return debugger_expression_evaluate( binary->op1 ) <
396 debugger_expression_evaluate( binary->op2 );
397
398 case DEBUGGER_TOKEN_LESS_THAN_OR_EQUAL_TO:
399 return debugger_expression_evaluate( binary->op1 ) <=
400 debugger_expression_evaluate( binary->op2 );
401
402 case DEBUGGER_TOKEN_GREATER_THAN_OR_EQUAL_TO:
403 return debugger_expression_evaluate( binary->op1 ) >=
404 debugger_expression_evaluate( binary->op2 );
405
406 case '&': return debugger_expression_evaluate( binary->op1 ) &
407 debugger_expression_evaluate( binary->op2 );
408
409 case '^': return debugger_expression_evaluate( binary->op1 ) ^
410 debugger_expression_evaluate( binary->op2 );
411
412 case '|': return debugger_expression_evaluate( binary->op1 ) |
413 debugger_expression_evaluate( binary->op2 );
414
415 case DEBUGGER_TOKEN_LOGICAL_AND:
416 return debugger_expression_evaluate( binary->op1 ) &&
417 debugger_expression_evaluate( binary->op2 );
418
419 case DEBUGGER_TOKEN_LOGICAL_OR:
420 return debugger_expression_evaluate( binary->op1 ) ||
421 debugger_expression_evaluate( binary->op2 );
422
423 }
424
425 ui_error( UI_ERROR_ERROR, "unknown binary operator %d", binary->operation );
426 fuse_abort();
427 }
428
429 int
debugger_expression_deparse(char * buffer,size_t length,const debugger_expression * exp)430 debugger_expression_deparse( char *buffer, size_t length,
431 const debugger_expression *exp )
432 {
433 switch( exp->type ) {
434
435 case DEBUGGER_EXPRESSION_TYPE_INTEGER:
436 if( debugger_output_base == 10 ) {
437 snprintf( buffer, length, "%d", exp->types.integer );
438 } else {
439 snprintf( buffer, length, "0x%x", exp->types.integer );
440 }
441 return 0;
442
443 case DEBUGGER_EXPRESSION_TYPE_UNARYOP:
444 return deparse_unaryop( buffer, length, &( exp->types.unaryop ) );
445
446 case DEBUGGER_EXPRESSION_TYPE_BINARYOP:
447 return deparse_binaryop( buffer, length, &( exp->types.binaryop ) );
448
449 case DEBUGGER_EXPRESSION_TYPE_SYSVAR:
450 debugger_system_variable_text( buffer, length, exp->types.system_variable );
451 return 0;
452
453 case DEBUGGER_EXPRESSION_TYPE_VARIABLE:
454 snprintf( buffer, length, "$%s", exp->types.variable );
455 return 0;
456
457 }
458
459 ui_error( UI_ERROR_ERROR, "unknown expression type %d", exp->type );
460 fuse_abort();
461 }
462
463 static int
deparse_unaryop(char * buffer,size_t length,const struct unaryop_type * unaryop)464 deparse_unaryop( char *buffer, size_t length,
465 const struct unaryop_type *unaryop )
466 {
467 char *operand_buffer; const char *operation_string = NULL;
468 const char *operation_suffix = "";
469 int brackets_possible = 1;
470 int brackets = 0;
471
472 int error;
473
474 operand_buffer = libspectrum_new( char, length );
475
476 error = debugger_expression_deparse( operand_buffer, length, unaryop->op );
477 if( error ) { libspectrum_free( operand_buffer ); return error; }
478
479 switch( unaryop->operation ) {
480 case '!': operation_string = "!"; break;
481 case '~': operation_string = "~"; break;
482 case '-': operation_string = "-"; break;
483 case DEBUGGER_TOKEN_DEREFERENCE:
484 operation_string = "[";
485 operation_suffix = "]";
486 brackets_possible = 0;
487 break;
488
489 default:
490 ui_error( UI_ERROR_ERROR, "unknown unary operation %d",
491 unaryop->operation );
492 fuse_abort();
493 }
494
495 if( brackets_possible )
496 brackets = ( unaryop->op->precedence <
497 unaryop_precedence( unaryop->operation ) );
498
499 snprintf( buffer, length, "%s%s%s%s%s", operation_string,
500 brackets ? "( " : "", operand_buffer,
501 brackets ? " )" : "", operation_suffix );
502
503 libspectrum_free( operand_buffer );
504
505 return 0;
506 }
507
508 static int
deparse_binaryop(char * buffer,size_t length,const struct binaryop_type * binaryop)509 deparse_binaryop( char *buffer, size_t length,
510 const struct binaryop_type *binaryop )
511 {
512 char *operand1_buffer, *operand2_buffer; const char *operation_string = NULL;
513 int brackets_necessary1, brackets_necessary2;
514
515 int error;
516
517 operand1_buffer = libspectrum_new( char, 2 * length );
518 operand2_buffer = &operand1_buffer[ length ];
519
520 error = debugger_expression_deparse( operand1_buffer, length,
521 binaryop->op1 );
522 if( error ) { libspectrum_free( operand1_buffer ); return error; }
523
524 error = debugger_expression_deparse( operand2_buffer, length,
525 binaryop->op2 );
526 if( error ) { libspectrum_free( operand1_buffer ); return error; }
527
528 switch( binaryop->operation ) {
529 case '+': operation_string = "+"; break;
530 case '-': operation_string = "-"; break;
531 case '*': operation_string = "*"; break;
532 case '/': operation_string = "/"; break;
533 case DEBUGGER_TOKEN_EQUAL_TO: operation_string = "=="; break;
534 case DEBUGGER_TOKEN_NOT_EQUAL_TO: operation_string = "!="; break;
535 case '<': operation_string = "<"; break;
536 case '>': operation_string = ">"; break;
537 case DEBUGGER_TOKEN_LESS_THAN_OR_EQUAL_TO: operation_string = "<="; break;
538 case DEBUGGER_TOKEN_GREATER_THAN_OR_EQUAL_TO: operation_string = ">="; break;
539 case '&': operation_string = "&"; break;
540 case '^': operation_string = "^"; break;
541 case '|': operation_string = "|"; break;
542 case DEBUGGER_TOKEN_LOGICAL_AND: operation_string = "&&"; break;
543 case DEBUGGER_TOKEN_LOGICAL_OR: operation_string = "||"; break;
544
545 default:
546 ui_error( UI_ERROR_ERROR, "unknown binary operation %d",
547 binaryop->operation );
548 fuse_abort();
549 }
550
551 brackets_necessary1 = brackets_necessary( binaryop->operation,
552 binaryop->op1 );
553 brackets_necessary2 = brackets_necessary( binaryop->operation,
554 binaryop->op2 );
555
556 snprintf( buffer, length, "%s%s%s %s %s%s%s",
557 brackets_necessary1 ? "( " : "", operand1_buffer,
558 brackets_necessary1 ? " )" : "",
559 operation_string,
560 brackets_necessary2 ? "( " : "", operand2_buffer,
561 brackets_necessary2 ? " )" : "" );
562
563 libspectrum_free( operand1_buffer );
564
565 return 0;
566 }
567
568 /* When deparsing, do we need to put brackets around `operand' when
569 being used as an operand of the binary operation `top_operation'? */
570 static int
brackets_necessary(int top_operation,debugger_expression * operand)571 brackets_necessary( int top_operation, debugger_expression *operand )
572 {
573 enum precedence_t top_precedence, bottom_precedence;
574
575 top_precedence = binaryop_precedence( top_operation );
576 bottom_precedence = operand->precedence;
577
578 /* If the top level operation has a higher precedence than the
579 bottom level operation, we always need brackets */
580 if( top_precedence > bottom_precedence ) return 1;
581
582 /* If the two operations are of equal precedence, we need brackets
583 i) if the top level operation is non-associative, or
584 ii) if the operand is a non-associative operation
585
586 Note the assumption here that all things with a precedence equal to
587 a binary operator are also binary operators
588
589 Strictly, we don't need brackets in either of these cases, but
590 otherwise the user is going to have to remember operator
591 left-right associativity; I think things are clearer with
592 brackets in.
593 */
594 if( top_precedence == bottom_precedence ) {
595
596 if( is_non_associative( top_operation ) ) return 1;
597
598 /* Sanity check */
599 if( operand->type != DEBUGGER_EXPRESSION_TYPE_BINARYOP ) {
600 ui_error( UI_ERROR_ERROR,
601 "binary operator has same precedence as non-binary operator" );
602 fuse_abort();
603 }
604
605 return is_non_associative( operand->types.binaryop.operation );
606 }
607
608 /* Otherwise (ie if the top level operation is of lower precedence
609 than the bottom, or both operators have equal precedence and
610 everything is associative) we don't need brackets */
611 return 0;
612 }
613
614 /* Is a binary operator non-associative? */
615 static int
is_non_associative(int operation)616 is_non_associative( int operation )
617 {
618 switch( operation ) {
619
620 /* Simple cases */
621 case '+': case '*': return 0;
622 case '-': case '/': return 1;
623
624 /* None of the comparison operators are associative due to them
625 returning truth values */
626 case DEBUGGER_TOKEN_EQUAL_TO:
627 case DEBUGGER_TOKEN_NOT_EQUAL_TO:
628 case '<': case '>':
629 case DEBUGGER_TOKEN_LESS_THAN_OR_EQUAL_TO:
630 case DEBUGGER_TOKEN_GREATER_THAN_OR_EQUAL_TO:
631 return 1;
632
633 /* The logical operators are associative */
634 case DEBUGGER_TOKEN_LOGICAL_AND: return 0;
635 case DEBUGGER_TOKEN_LOGICAL_OR: return 0;
636
637 /* The bitwise operators are also associative (consider them as
638 vectorised logical operators) */
639 case '&': return 0;
640 case '^': return 0;
641 case '|': return 0;
642
643 }
644
645 /* Should never get here */
646 ui_error( UI_ERROR_ERROR, "unknown binary operation %d", operation );
647 fuse_abort();
648 }
649
650