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