git.sur5r.net Git - cc65/blob - src/ca65/expr.c

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                  expr.c                                   */
   4 /*                                                                           */
   5 /*             Expression evaluation for the ca65 macroassembler             */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 1998-2000 Ullrich von Bassewitz                                       */
  10 /*               Wacholderweg 14                                             */
  11 /*               D-70597 Stuttgart                                           */
  12 /* EMail:        uz@musoftware.de                                            */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 #include "../common/exprdefs.h"
  37 #include "../common/xmalloc.h"
  38
  39 #include "error.h"
  40 #include "global.h"
  41 #include "instr.h"
  42 #include "nexttok.h"
  43 #include "objcode.h"
  44 #include "objfile.h"
  45 #include "symtab.h"
  46 #include "toklist.h"
  47 #include "ulabel.h"
  48 #include "expr.h"
  49
  50
  51
  52 /*****************************************************************************/
  53 /*                                   Data                                    */
  54 /*****************************************************************************/
  55
  56
  57
  58 /* Since all expressions are first packed into expression trees, and each
  59  * expression tree node is allocated on the heap, we add some type of special
  60  * purpose memory allocation here: Instead of freeing the nodes, we save some
  61  * number of freed nodes for later and remember them in a single linked list
  62  * using the Left link.
  63  */
  64 #define MAX_FREE_NODES  64
  65 static ExprNode*        FreeExprNodes = 0;
  66 static unsigned         FreeNodeCount = 0;
  67
  68
  69
  70 /*****************************************************************************/
  71 /*                                  Helpers                                  */
  72 /*****************************************************************************/
  73
  74
  75
  76 static ExprNode* NewExprNode (void)
  77 /* Create a new expression node */
  78 {
  79     ExprNode* N;
  80
  81     /* Do we have some nodes in the list already? */
  82     if (FreeExprNodes) {
  83         /* Use first node from list */
  84         N = FreeExprNodes;
  85         FreeExprNodes = N->Left;
  86     } else {
  87         /* Allocate fresh memory */
  88         N = xmalloc (sizeof (ExprNode));
  89     }
  90     N->Op = EXPR_NULL;
  91     N->Left = N->Right = 0;
  92     N->Obj = 0;
  93
  94     return N;
  95 }
  96
  97
  98
  99 static void FreeExprNode (ExprNode* E)
 100 /* Free a node */
 101 {
 102     if (E) {
 103         if (FreeNodeCount < MAX_FREE_NODES) {
 104             /* Remember this node for later */
 105             E->Left = FreeExprNodes;
 106             FreeExprNodes = E;
 107         } else {
 108             /* Free the memory */
 109             xfree (E);
 110         }
 111     }
 112 }
 113
 114
 115
 116 /*****************************************************************************/
 117 /*              Dump an expression tree on stdout for debugging              */
 118 /*****************************************************************************/
 119
 120
 121
 122 static void InternalDumpExpr (ExprNode* Expr)
 123 /* Dump an expression in UPN */
 124 {
 125     if (Expr == 0) {
 126         return;
 127     }
 128     InternalDumpExpr (Expr->Left);
 129     InternalDumpExpr (Expr->Right);
 130
 131     switch (Expr->Op) {
 132
 133         case EXPR_LITERAL:
 134         case EXPR_ULABEL:
 135             printf (" $%04lX", Expr->V.Val & 0xFFFF);
 136             break;
 137
 138         case EXPR_SYMBOL:
 139             printf (" %s", GetSymName (Expr->V.Sym));
 140             break;
 141
 142         case EXPR_SEGMENT:
 143             printf (" SEG");
 144             break;
 145
 146         case EXPR_PLUS:
 147             printf (" +");
 148             break;
 149
 150         case EXPR_MINUS:
 151             printf (" -");
 152             break;
 153
 154         case EXPR_MUL:
 155             printf (" *");
 156             break;
 157
 158         case EXPR_DIV:
 159             printf (" /");
 160             break;
 161
 162         case EXPR_MOD:
 163             printf (" %%");
 164             break;
 165
 166         case EXPR_OR:
 167             printf (" OR");
 168             break;
 169
 170         case EXPR_XOR:
 171             printf (" XOR");
 172             break;
 173
 174         case EXPR_AND:
 175             printf (" AND");
 176             break;
 177
 178         case EXPR_SHL:
 179             printf (" SHL");
 180             break;
 181
 182         case EXPR_SHR:
 183             printf (" SHR");
 184             break;
 185
 186         case EXPR_EQ:
 187             printf (" =");
 188             break;
 189
 190         case EXPR_NE:
 191             printf ("<>");
 192             break;
 193
 194         case EXPR_LT:
 195             printf (" <");
 196             break;
 197
 198         case EXPR_GT:
 199             printf (" >");
 200             break;
 201
 202         case EXPR_UNARY_MINUS:
 203             printf (" NEG");
 204             break;
 205
 206         case EXPR_NOT:
 207             printf (" ~");
 208             break;
 209
 210         case EXPR_LOBYTE:
 211             printf (" LO");
 212             break;
 213
 214         case EXPR_HIBYTE:
 215             printf (" HI");
 216             break;
 217
 218         case EXPR_SWAP:
 219             printf (" SWAP");
 220             break;
 221
 222         case EXPR_BAND:
 223             printf (" BOOL_AND");
 224             break;
 225
 226         case EXPR_BOR:
 227             printf (" BOOL_OR");
 228             break;
 229
 230         case EXPR_BXOR:
 231             printf (" BOOL_XOR");
 232             break;
 233
 234         case EXPR_BNOT:
 235             printf (" BOOL_NOT");
 236             break;
 237
 238         default:
 239             Internal ("Unknown Op type: %u", Expr->Op);
 240
 241     }
 242 }
 243
 244
 245
 246 void DumpExpr (ExprNode* Expr)
 247 /* Dump an expression tree to stdout */
 248 {
 249     InternalDumpExpr (Expr);
 250     printf ("\n");
 251 }
 252
 253
 254
 255 /*****************************************************************************/
 256 /*                                   Code                                    */
 257 /*****************************************************************************/
 258
 259
 260
 261 static ExprNode* Expr0 (void);
 262
 263
 264
 265 int IsByteRange (long Val)
 266 /* Return true if this is a byte value */
 267 {
 268     return (Val & ~0xFFL) == 0;
 269 }
 270
 271
 272
 273 int IsWordRange (long Val)
 274 /* Return true if this is a word value */
 275 {
 276     return (Val & ~0xFFFF) == 0;
 277 }
 278
 279
 280
 281 static int FuncBlank (void)
 282 /* Handle the .BLANK builtin function */
 283 {
 284     /* Assume no tokens if the closing brace follows (this is not correct in
 285      * all cases, since the token may be the closing brace, but this will
 286      * give a syntax error anyway and may not be handled by .BLANK.
 287      */
 288     if (Tok == TOK_RPAREN) {
 289         /* No tokens */
 290         return 1;
 291     } else {
 292         /* Skip any tokens */
 293         int Braces = 0;
 294         while (Tok != TOK_SEP && Tok != TOK_EOF) {
 295             if (Tok == TOK_LPAREN) {
 296                 ++Braces;
 297             } else if (Tok == TOK_RPAREN) {
 298                 if (Braces == 0) {
 299                     /* Done */
 300                     break;
 301                 } else {
 302                     --Braces;
 303                 }
 304             }
 305             NextTok ();
 306         }
 307         return 0;
 308     }
 309 }
 310
 311
 312
 313 static int FuncConst (void)
 314 /* Handle the .CONST builtin function */
 315 {
 316     /* Read an expression */
 317     ExprNode* Expr = Expression ();
 318
 319     /* Check the constness of the expression */
 320     int Result = IsConstExpr (Expr);
 321
 322     /* Free the expression */
 323     FreeExpr (Expr);
 324
 325     /* Done */
 326     return Result;
 327 }
 328
 329
 330
 331 static int FuncDefined (void)
 332 /* Handle the .DEFINED builtin function */
 333 {
 334     int Result = 0;
 335
 336     if (Tok != TOK_IDENT) {
 337         Error (ERR_IDENT_EXPECTED);
 338         if (Tok != TOK_RPAREN) {
 339             NextTok ();
 340         }
 341     } else {
 342         Result = SymIsDef (SVal);
 343         NextTok ();
 344     }
 345
 346     /* Done */
 347     return Result;
 348 }
 349
 350
 351
 352 static int DoMatch (enum TC EqualityLevel)
 353 /* Handle the .MATCH and .XMATCH builtin functions */
 354 {
 355     int Result;
 356     TokNode* Root = 0;
 357     TokNode* Last = 0;
 358     TokNode* Node = 0;
 359
 360     /* A list of tokens follows. Read this list and remember it building a
 361      * single linked list of tokens including attributes. The list is
 362      * terminated by a comma.
 363      */
 364     while (Tok != TOK_COMMA) {
 365
 366         /* We may not end-of-line of end-of-file here */
 367         if (Tok == TOK_SEP || Tok == TOK_EOF) {
 368             Error (ERR_UNEXPECTED_EOL);
 369             return 0;
 370         }
 371
 372         /* Get a node with this token */
 373         Node = NewTokNode ();
 374
 375         /* Insert the node into the list */
 376         if (Last == 0) {
 377             Root = Node;
 378         } else {
 379             Last->Next = Node;
 380         }
 381         Last = Node;
 382
 383         /* Skip the token */
 384         NextTok ();
 385     }
 386
 387     /* Skip the comma */
 388     NextTok ();
 389
 390     /* Read the second list which is terminated by the right parenthesis and
 391      * compare each token against the one in the first list.
 392      */
 393     Result = 1;
 394     Node = Root;
 395     while (Tok != TOK_RPAREN) {
 396
 397         /* We may not end-of-line of end-of-file here */
 398         if (Tok == TOK_SEP || Tok == TOK_EOF) {
 399             Error (ERR_UNEXPECTED_EOL);
 400             return 0;
 401         }
 402
 403         /* Compare the tokens if the result is not already known */
 404         if (Result != 0) {
 405             if (Node == 0) {
 406                 /* The second list is larger than the first one */
 407                 Result = 0;
 408             } else if (TokCmp (Node) < EqualityLevel) {
 409                 /* Tokens do not match */
 410                 Result = 0;
 411             }
 412         }
 413
 414         /* Next token in first list */
 415         if (Node) {
 416             Node = Node->Next;
 417         }
 418
 419         /* Next token in current list */
 420         NextTok ();
 421     }
 422
 423     /* Check if there are remaining tokens in the first list */
 424     if (Node != 0) {
 425         Result = 0;
 426     }
 427
 428     /* Free the token list */
 429     while (Root) {
 430         Node = Root;
 431         Root = Root->Next;
 432         FreeTokNode (Node);
 433     }
 434
 435     /* Done, return the result */
 436     return Result;
 437 }
 438
 439
 440
 441 static int FuncMatch (void)
 442 /* Handle the .MATCH function */
 443 {
 444     return DoMatch (tcSameToken);
 445 }
 446
 447
 448
 449 static int FuncReferenced (void)
 450 /* Handle the .REFERENCED builtin function */
 451 {
 452     int Result = 0;
 453
 454     if (Tok != TOK_IDENT) {
 455         Error (ERR_IDENT_EXPECTED);
 456         if (Tok != TOK_RPAREN) {
 457             NextTok ();
 458         }
 459     } else {
 460         Result = SymIsRef (SVal);
 461         NextTok ();
 462     }
 463
 464     /* Done */
 465     return Result;
 466 }
 467
 468
 469
 470 static int FuncTCount (void)
 471 /* Handle the .TCOUNT function */
 472 {
 473     /* We have a list of tokens that ends with the closing paren. Skip
 474      * the tokens, handling nested braces and count them.
 475      */
 476     int      Count  = 0;
 477     unsigned Parens = 0;
 478     while (Parens != 0 || Tok != TOK_RPAREN) {
 479
 480         /* Check for end of line or end of input. Since the calling function
 481          * will check for the closing paren, we don't need to print an error
 482          * here, just bail out.
 483          */
 484         if (Tok == TOK_SEP || Tok == TOK_EOF) {
 485             break;
 486         }
 487
 488         /* One more token */
 489         ++Count;
 490
 491         /* Keep track of the nesting level */
 492         switch (Tok) {
 493             case TOK_LPAREN:    ++Parens;       break;
 494             case TOK_RPAREN:    --Parens;       break;
 495             default:                            break;
 496         }
 497
 498         /* Skip the token */
 499         NextTok ();
 500     }
 501
 502     /* Return the number of tokens */
 503     return Count;
 504 }
 505
 506
 507
 508 static int FuncXMatch (void)
 509 /* Handle the .XMATCH function */
 510 {
 511     return DoMatch (tcIdentical);
 512 }
 513
 514
 515
 516 static ExprNode* Function (int (*F) (void))
 517 /* Handle builtin functions */
 518 {
 519     long Result;
 520
 521     /* Skip the keyword */
 522     NextTok ();
 523
 524     /* Expression must be enclosed in braces */
 525     if (Tok != TOK_LPAREN) {
 526         Error (ERR_LPAREN_EXPECTED);
 527         SkipUntilSep ();
 528         return LiteralExpr (0);
 529     }
 530     NextTok ();
 531
 532     /* Call the function itself */
 533     Result = F ();
 534
 535     /* Closing brace must follow */
 536     ConsumeRParen ();
 537
 538     /* Return an expression node with the boolean code */
 539     return LiteralExpr (Result);
 540 }
 541
 542
 543
 544 static ExprNode* Factor (void)
 545 {
 546     ExprNode* N;
 547     SymEntry* S;
 548
 549     switch (Tok) {
 550
 551         case TOK_INTCON:
 552         case TOK_CHARCON:
 553             N = LiteralExpr (IVal);
 554             NextTok ();
 555             break;
 556
 557         case TOK_NAMESPACE:
 558             NextTok ();
 559             if (Tok != TOK_IDENT) {
 560                 Error (ERR_IDENT_EXPECTED);
 561                 N = LiteralExpr (0);    /* Dummy */
 562             } else {
 563                 S = SymRefGlobal (SVal);
 564                 if (SymIsConst (S)) {
 565                     /* Use the literal value instead */
 566                     N = LiteralExpr (GetSymVal (S));
 567                 } else {
 568                     /* Create symbol node */
 569                     N = NewExprNode ();
 570                     N->Op    = EXPR_SYMBOL;
 571                     N->V.Sym = S;
 572                 }
 573                 NextTok ();
 574             }
 575             break;
 576
 577         case TOK_IDENT:
 578             S = SymRef (SVal);
 579             if (SymIsConst (S)) {
 580                 /* Use the literal value instead */
 581                 N = LiteralExpr (GetSymVal (S));
 582             } else {
 583                 /* Create symbol node */
 584                 N = NewExprNode ();
 585                 N->Op    = EXPR_SYMBOL;
 586                 N->V.Sym = S;
 587             }
 588             NextTok ();
 589             break;
 590
 591         case TOK_ULABEL:
 592             N = ULabRef (IVal);
 593             NextTok ();
 594             break;
 595
 596         case TOK_MINUS:
 597             NextTok ();
 598             N = NewExprNode ();
 599             N->Left = Factor ();
 600             N->Op   = EXPR_UNARY_MINUS;
 601             break;
 602
 603         case TOK_NOT:
 604             NextTok ();
 605             N = NewExprNode ();
 606             N->Left = Factor ();
 607             N->Op   = EXPR_NOT;
 608             break;
 609
 610         case TOK_STAR:
 611         case TOK_PC:
 612             NextTok ();
 613             N = CurrentPC ();
 614             break;
 615
 616         case TOK_LT:
 617             NextTok ();
 618             N = NewExprNode ();
 619             N->Left = Factor ();
 620             N->Op   = EXPR_LOBYTE;
 621             break;
 622
 623         case TOK_GT:
 624             NextTok ();
 625             N = NewExprNode ();
 626             N->Left = Factor ();
 627             N->Op   = EXPR_HIBYTE;
 628             break;
 629
 630         case TOK_LPAREN:
 631             NextTok ();
 632             N = Expr0 ();
 633             ConsumeRParen ();
 634             break;
 635
 636         case TOK_BLANK:
 637             N = Function (FuncBlank);
 638             break;
 639
 640         case TOK_CONST:
 641             N = Function (FuncConst);
 642             break;
 643
 644         case TOK_CPU:
 645             N = LiteralExpr (GetCPU());
 646             NextTok ();
 647             break;
 648
 649         case TOK_DEFINED:
 650             N = Function (FuncDefined);
 651             break;
 652
 653         case TOK_MATCH:
 654             N = Function (FuncMatch);
 655             break;
 656
 657         case TOK_REFERENCED:
 658             N = Function (FuncReferenced);
 659             break;
 660
 661         case TOK_TCOUNT:
 662             N = Function (FuncTCount);
 663             break;
 664
 665         case TOK_XMATCH:
 666             N = Function (FuncXMatch);
 667             break;
 668
 669         default:
 670             N = LiteralExpr (0);        /* Dummy */
 671             Error (ERR_SYNTAX);
 672             NextTok ();
 673             break;
 674     }
 675     return N;
 676 }
 677
 678
 679
 680 static ExprNode* Term (void)
 681 {
 682     ExprNode* Root;
 683
 684     /* Read left hand side */
 685     Root = Factor ();
 686
 687     /* Handle multiplicative operations */
 688     while (Tok == TOK_MUL || Tok == TOK_DIV || Tok == TOK_MOD ||
 689            Tok == TOK_AND || Tok == TOK_XOR || Tok == TOK_SHL ||
 690            Tok == TOK_SHR) {
 691
 692         /* Create a new node and insert the left expression */
 693         ExprNode* Left = Root;
 694         Root = NewExprNode ();
 695         Root->Left = Left;
 696
 697         /* Determine the operator token */
 698         switch (Tok) {
 699             case TOK_MUL:       Root->Op = EXPR_MUL;    break;
 700             case TOK_DIV:       Root->Op = EXPR_DIV;    break;
 701             case TOK_MOD:       Root->Op = EXPR_MOD;    break;
 702             case TOK_AND:       Root->Op = EXPR_AND;    break;
 703             case TOK_XOR:       Root->Op = EXPR_XOR;    break;
 704             case TOK_SHL:       Root->Op = EXPR_SHL;    break;
 705             case TOK_SHR:       Root->Op = EXPR_SHR;    break;
 706             default:            Internal ("Invalid token");
 707         }
 708         NextTok ();
 709
 710         /* Parse the right hand side */
 711         Root->Right = Factor ();
 712
 713     }
 714
 715     /* Return the expression tree we've created */
 716     return Root;
 717 }
 718
 719
 720
 721 static ExprNode* SimpleExpr (void)
 722 {
 723     ExprNode* Root;
 724
 725     /* Read left hand side */
 726     Root = Term ();
 727
 728     /* Handle additive operations */
 729     while (Tok == TOK_PLUS || Tok == TOK_MINUS || Tok == TOK_OR) {
 730
 731         /* Create a new node and insert the left expression */
 732         ExprNode* Left = Root;
 733         Root = NewExprNode ();
 734         Root->Left = Left;
 735
 736         /* Determine the operator token */
 737         switch (Tok) {
 738             case TOK_PLUS:      Root->Op = EXPR_PLUS;   break;
 739             case TOK_MINUS:     Root->Op = EXPR_MINUS;  break;
 740             case TOK_OR:        Root->Op = EXPR_OR;     break;
 741             default:            Internal ("Invalid token");
 742         }
 743         NextTok ();
 744
 745         /* Parse the right hand side */
 746         Root->Right = Term ();
 747
 748     }
 749
 750     /* Return the expression tree we've created */
 751     return Root;
 752 }
 753
 754
 755
 756 static ExprNode* BoolExpr (void)
 757 /* Evaluate a boolean expression */
 758 {
 759     /* Read left hand side */
 760     ExprNode* Root = SimpleExpr ();
 761
 762     /* Handle booleans */
 763     while (Tok == TOK_EQ || Tok == TOK_NE || Tok == TOK_LT ||
 764            Tok == TOK_GT || Tok == TOK_LE || Tok == TOK_GE) {
 765
 766         /* Create a new node and insert the left expression */
 767         ExprNode* Left = Root;
 768         Root = NewExprNode ();
 769         Root->Left = Left;
 770
 771         /* Determine the operator token */
 772         switch (Tok) {
 773             case TOK_EQ:        Root->Op = EXPR_EQ;     break;
 774             case TOK_NE:        Root->Op = EXPR_NE;     break;
 775             case TOK_LT:        Root->Op = EXPR_LT;     break;
 776             case TOK_GT:        Root->Op = EXPR_GT;     break;
 777             case TOK_LE:        Root->Op = EXPR_LE;     break;
 778             case TOK_GE:        Root->Op = EXPR_GE;     break;
 779             default:            Internal ("Invalid token");
 780         }
 781         NextTok ();
 782
 783         /* Parse the right hand side */
 784         Root->Right = SimpleExpr ();
 785
 786     }
 787
 788     /* Return the expression tree we've created */
 789     return Root;
 790 }
 791
 792
 793
 794 static ExprNode* Expr2 (void)
 795 /* Boolean operators: AND and XOR */
 796 {
 797     /* Read left hand side */
 798     ExprNode* Root = BoolExpr ();
 799
 800     /* Handle booleans */
 801     while (Tok == TOK_BAND || Tok == TOK_BXOR) {
 802
 803         /* Create a new node and insert the left expression */
 804         ExprNode* Left = Root;
 805         Root = NewExprNode ();
 806         Root->Left = Left;
 807
 808         /* Determine the operator token */
 809         switch (Tok) {
 810             case TOK_BAND:      Root->Op = EXPR_BAND;   break;
 811             case TOK_BXOR:      Root->Op = EXPR_BXOR;   break;
 812             default:            Internal ("Invalid token");
 813         }
 814         NextTok ();
 815
 816         /* Parse the right hand side */
 817         Root->Right = BoolExpr ();
 818
 819     }
 820
 821     /* Return the expression tree we've created */
 822     return Root;
 823 }
 824
 825
 826
 827 static ExprNode* Expr1 (void)
 828 /* Boolean operators: OR */
 829 {
 830     /* Read left hand side */
 831     ExprNode* Root = Expr2 ();
 832
 833     /* Handle booleans */
 834     while (Tok == TOK_BOR) {
 835
 836         /* Create a new node and insert the left expression */
 837         ExprNode* Left = Root;
 838         Root = NewExprNode ();
 839         Root->Left = Left;
 840
 841         /* Determine the operator token */
 842         switch (Tok) {
 843             case TOK_BOR:       Root->Op = EXPR_BOR;    break;
 844             default:            Internal ("Invalid token");
 845         }
 846         NextTok ();
 847
 848         /* Parse the right hand side */
 849         Root->Right = Expr2 ();
 850
 851     }
 852
 853     /* Return the expression tree we've created */
 854     return Root;
 855 }
 856
 857
 858
 859 static ExprNode* Expr0 (void)
 860 /* Boolean operators: NOT */
 861 {
 862     ExprNode* Root;
 863
 864     /* Handle booleans */
 865     if (Tok == TOK_BNOT) {
 866
 867         /* Create a new node */
 868         Root = NewExprNode ();
 869
 870         /* Determine the operator token */
 871         switch (Tok) {
 872             case TOK_BNOT:      Root->Op = EXPR_BNOT;   break;
 873             default:            Internal ("Invalid token");
 874         }
 875         NextTok ();
 876
 877         /* Parse the left hand side, allow more BNOTs */
 878         Root->Left = Expr0 ();
 879
 880     } else {
 881
 882         /* Read left hand side */
 883         Root = Expr1 ();
 884
 885     }
 886
 887     /* Return the expression tree we've created */
 888     return Root;
 889 }
 890
 891
 892
 893 static ExprNode* SimplifyExpr (ExprNode* Root)
 894 /* Try to simplify the given expression tree */
 895 {
 896     if (Root) {
 897         SimplifyExpr (Root->Left);
 898         SimplifyExpr (Root->Right);
 899         if (IsConstExpr (Root)) {
 900             /* The complete expression is constant */
 901             Root->V.Val = GetExprVal (Root);
 902             Root->Op = EXPR_LITERAL;
 903             FreeExpr (Root->Left);
 904             FreeExpr (Root->Right);
 905             Root->Left = Root->Right = 0;
 906         }
 907     }
 908     return Root;
 909 }
 910
 911
 912
 913 ExprNode* Expression (void)
 914 /* Evaluate an expression, build the expression tree on the heap and return
 915  * a pointer to the root of the tree.
 916  */
 917 {
 918     return SimplifyExpr (Expr0 ());
 919 }
 920
 921
 922
 923 long ConstExpression (void)
 924 /* Parse an expression. Check if the expression is const, and print an error
 925  * message if not. Return the value of the expression, or a dummy, if it is
 926  * not constant.
 927  */
 928 {
 929     /* Read the expression, and call finalize (exception here, since we
 930      * expect a const).
 931      */
 932     ExprNode* Expr = FinalizeExpr (Expression ());
 933
 934     /* Return the value */
 935     if (IsConstExpr (Expr)) {
 936         return GetExprVal (Expr);
 937     } else {
 938         Error (ERR_CONSTEXPR_EXPECTED);
 939         return 0;
 940     }
 941 }
 942
 943
 944
 945 ExprNode* LiteralExpr (long Val)
 946 /* Return an expression tree that encodes the given literal value */
 947 {
 948     ExprNode* Expr = NewExprNode ();
 949     Expr->Op = EXPR_LITERAL;
 950     Expr->V.Val = Val;
 951     return Expr;
 952 }
 953
 954
 955
 956 ExprNode* CurrentPC (void)
 957 /* Return the current program counter as expression */
 958 {
 959     ExprNode* Left;
 960     ExprNode* Root;
 961
 962     if (RelocMode) {
 963         /* Create SegmentBase + Offset */
 964         Left = NewExprNode ();
 965         Left->Op = EXPR_SEGMENT;
 966         Left->V.SegNum = GetSegNum ();
 967
 968         Root = NewExprNode ();
 969         Root->Left  = Left;
 970         Root->Right = LiteralExpr (GetPC ());
 971         Root->Op = EXPR_PLUS;
 972     } else {
 973         /* Absolute mode, just return PC value */
 974         Root = LiteralExpr (GetPC ());
 975     }
 976
 977     return Root;
 978 }
 979
 980
 981
 982 ExprNode* SwapExpr (ExprNode* Expr)
 983 /* Return an extended expression with lo and hi bytes swapped */
 984 {
 985     ExprNode* N = NewExprNode ();
 986     N->Op = EXPR_SWAP;
 987     N->Left = Expr;
 988     return N;
 989 }
 990
 991
 992
 993 ExprNode* BranchExpr (unsigned Offs)
 994 /* Return an expression that encodes the difference between current PC plus
 995  * offset and the target expression (that is, Expression() - (*+Offs) ).
 996  */
 997 {
 998     ExprNode* N;
 999     ExprNode* Root;
1000     ExprNode* Left;
1001
1002     /* Create *+Offs */
1003     if (RelocMode) {
1004         Left = NewExprNode ();
1005         Left->Op = EXPR_SEGMENT;
1006         Left->V.SegNum = GetSegNum ();
1007
1008         N = NewExprNode ();
1009         N->Left  = Left;
1010         N->Right = LiteralExpr (GetPC () + Offs);
1011         N->Op = EXPR_PLUS;
1012     } else {
1013         N = LiteralExpr (GetPC () + Offs);
1014     }
1015
1016     /* Create the root node */
1017     Root = NewExprNode ();
1018     Root->Left = Expression ();
1019     Root->Right = N;
1020     Root->Op = EXPR_MINUS;
1021
1022     /* Return the result */
1023     return SimplifyExpr (Root);
1024 }
1025
1026
1027
1028 ExprNode* ULabelExpr (unsigned Num)
1029 /* Return an expression for an unnamed label with the given index */
1030 {
1031     /* Get an expression node */
1032     ExprNode* Node = NewExprNode ();
1033
1034     /* Set the values */
1035     Node->Op    = EXPR_ULABEL;
1036     Node->V.Val = Num;
1037
1038     /* Return the new node */
1039     return Node;
1040 }
1041
1042
1043
1044 void FreeExpr (ExprNode* Root)
1045 /* Free the expression, Root is pointing to. */
1046 {
1047     if (Root) {
1048         FreeExpr (Root->Left);
1049         FreeExpr (Root->Right);
1050         FreeExprNode (Root);
1051     }
1052 }
1053
1054
1055
1056 ExprNode* ForceWordExpr (ExprNode* Expr)
1057 /* Force the given expression into a word and return the result. */
1058 {
1059     /* And the expression by $FFFF to force it into word size */
1060     ExprNode* Root = NewExprNode ();
1061     Root->Left  = Expr;
1062     Root->Op    = EXPR_AND;
1063     Root->Right = LiteralExpr (0xFFFF);
1064
1065     /* Return the result */
1066     return Root;
1067 }
1068
1069
1070
1071 int IsConstExpr (ExprNode* Root)
1072 /* Return true if the given expression is a constant expression, that is, one
1073  * with no references to external symbols.
1074  */
1075 {
1076     int Const;
1077     SymEntry* Sym;
1078
1079     if (EXPR_IS_LEAF (Root->Op)) {
1080         switch (Root->Op) {
1081
1082             case EXPR_LITERAL:
1083                 return 1;
1084
1085             case EXPR_SYMBOL:
1086                 Sym = Root->V.Sym;
1087                 if (SymHasUserMark (Sym)) {
1088                     if (Verbose) {
1089                         DumpExpr (Root);
1090                     }
1091                     PError (GetSymPos (Sym), ERR_CIRCULAR_REFERENCE);
1092                     Const = 0;
1093                 } else {
1094                     SymMarkUser (Sym);
1095                     Const = SymIsConst (Sym);
1096                     SymUnmarkUser (Sym);
1097                 }
1098                 return Const;
1099
1100             default:
1101                 return 0;
1102
1103         }
1104     } else if (EXPR_IS_UNARY (Root->Op)) {
1105
1106         return IsConstExpr (Root->Left);
1107
1108     } else {
1109
1110         /* We must handle shortcut boolean expressions here */
1111         switch (Root->Op) {
1112
1113             case EXPR_BAND:
1114                 if (IsConstExpr (Root->Left)) {
1115                     /* lhs is const, if it is zero, don't eval right */
1116                     if (GetExprVal (Root->Left) == 0) {
1117                         return 1;
1118                     } else {
1119                         return IsConstExpr (Root->Right);
1120                     }
1121                 } else {
1122                     /* lhs not const --> tree not const */
1123                     return 0;
1124                 }
1125                 break;
1126
1127             case EXPR_BOR:
1128                 if (IsConstExpr (Root->Left)) {
1129                     /* lhs is const, if it is not zero, don't eval right */
1130                     if (GetExprVal (Root->Left) != 0) {
1131                         return 1;
1132                     } else {
1133                         return IsConstExpr (Root->Right);
1134                     }
1135                 } else {
1136                     /* lhs not const --> tree not const */
1137                     return 0;
1138                 }
1139                 break;
1140
1141             default:
1142                 /* All others are handled normal */
1143                 return IsConstExpr (Root->Left) && IsConstExpr (Root->Right);
1144         }
1145     }
1146 }
1147
1148
1149
1150 static void CheckByteExpr (const ExprNode* N, int* IsByte)
1151 /* Internal routine that is recursively called to check if there is a zeropage
1152  * symbol in the expression tree.
1153  */
1154 {
1155     if (N) {
1156         switch (N->Op & EXPR_TYPEMASK) {
1157
1158             case EXPR_LEAFNODE:
1159                 switch (N->Op) {
1160
1161                     case EXPR_SYMBOL:
1162                         if (SymIsZP (N->V.Sym)) {
1163                             *IsByte = 1;
1164                         }
1165                         break;
1166
1167                     case EXPR_SEGMENT:
1168                         if (GetSegType (N->V.SegNum) == SEGTYPE_ZP) {
1169                             *IsByte = 1;
1170                         }
1171                         break;
1172
1173                 }
1174                 break;
1175
1176             case EXPR_UNARYNODE:
1177                 CheckByteExpr (N->Left, IsByte);
1178                 break;
1179
1180             case EXPR_BINARYNODE:
1181                 CheckByteExpr (N->Left, IsByte);
1182                 CheckByteExpr (N->Right, IsByte);
1183                 break;
1184
1185             default:
1186                 Internal ("Unknown expression op: %02X", N->Op);
1187         }
1188     }
1189 }
1190
1191
1192
1193 int IsByteExpr (ExprNode* Root)
1194 /* Return true if this is a byte expression */
1195 {
1196     int IsByte;
1197
1198     if (IsConstExpr (Root)) {
1199         if (Root->Op != EXPR_LITERAL) {
1200             SimplifyExpr (Root);
1201         }
1202         return IsByteRange (GetExprVal (Root));
1203     } else if (Root->Op == EXPR_LOBYTE || Root->Op == EXPR_HIBYTE) {
1204         /* Symbol forced to have byte range */
1205         IsByte = 1;
1206     } else {
1207         /* We have undefined symbols in the expression. Assume that the
1208          * expression is a byte expression if there is at least one symbol
1209          * declared as zeropage in it. Being wrong here is not a very big
1210          * problem since the linker knows about all symbols and detects
1211          * error like mixing absolute and zeropage labels.
1212          */
1213         IsByte = 0;
1214         CheckByteExpr (Root, &IsByte);
1215     }
1216     return IsByte;
1217 }
1218
1219
1220
1221 long GetExprVal (ExprNode* Expr)
1222 /* Get the value of a constant expression */
1223 {
1224     long Right, Left;
1225
1226     switch (Expr->Op) {
1227
1228         case EXPR_LITERAL:
1229             return Expr->V.Val;
1230
1231         case EXPR_SYMBOL:
1232             return GetSymVal (Expr->V.Sym);
1233
1234         case EXPR_PLUS:
1235             return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
1236
1237         case EXPR_MINUS:
1238             return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
1239
1240         case EXPR_MUL:
1241             return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
1242
1243         case EXPR_DIV:
1244             Left  = GetExprVal (Expr->Left);
1245             Right = GetExprVal (Expr->Right);
1246             if (Right == 0) {
1247                 Error (ERR_DIV_BY_ZERO);
1248                 return 0;
1249             }
1250             return Left / Right;
1251
1252         case EXPR_MOD:
1253             Left  = GetExprVal (Expr->Left);
1254             Right = GetExprVal (Expr->Right);
1255             if (Right == 0) {
1256                 Error (ERR_MOD_BY_ZERO);
1257                 return 0;
1258             }
1259             return Left % Right;
1260
1261         case EXPR_OR:
1262             return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
1263
1264         case EXPR_XOR:
1265             return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
1266
1267         case EXPR_AND:
1268             return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
1269
1270         case EXPR_SHL:
1271             return GetExprVal (Expr->Left) << GetExprVal (Expr->Right);
1272
1273         case EXPR_SHR:
1274             return GetExprVal (Expr->Left) >> GetExprVal (Expr->Right);
1275
1276         case EXPR_EQ:
1277             return (GetExprVal (Expr->Left) == GetExprVal (Expr->Right));
1278
1279         case EXPR_NE:
1280             return (GetExprVal (Expr->Left) != GetExprVal (Expr->Right));
1281
1282         case EXPR_LT:
1283             return (GetExprVal (Expr->Left) < GetExprVal (Expr->Right));
1284
1285         case EXPR_GT:
1286             return (GetExprVal (Expr->Left) > GetExprVal (Expr->Right));
1287
1288         case EXPR_LE:
1289             return (GetExprVal (Expr->Left) <= GetExprVal (Expr->Right));
1290
1291         case EXPR_GE:
1292             return (GetExprVal (Expr->Left) >= GetExprVal (Expr->Right));
1293
1294         case EXPR_UNARY_MINUS:
1295             return -GetExprVal (Expr->Left);
1296
1297         case EXPR_NOT:
1298             return ~GetExprVal (Expr->Left);
1299
1300         case EXPR_LOBYTE:
1301             return GetExprVal (Expr->Left) & 0xFF;
1302
1303         case EXPR_HIBYTE:
1304             return (GetExprVal (Expr->Left) >> 8) & 0xFF;
1305
1306         case EXPR_SWAP:
1307             Left = GetExprVal (Expr->Left);
1308             return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
1309
1310         case EXPR_BAND:
1311             return GetExprVal (Expr->Left) && GetExprVal (Expr->Right);
1312
1313         case EXPR_BOR:
1314             return GetExprVal (Expr->Left) || GetExprVal (Expr->Right);
1315
1316         case EXPR_BXOR:
1317             return (GetExprVal (Expr->Left) != 0) ^ (GetExprVal (Expr->Right) != 0);
1318
1319         case EXPR_BNOT:
1320             return !GetExprVal (Expr->Left);
1321
1322         case EXPR_ULABEL:
1323             Internal ("GetExprVal called for EXPR_ULABEL");
1324             /* NOTREACHED */
1325             return 0;
1326
1327         default:
1328             Internal ("Unknown Op type: %u", Expr->Op);
1329             /* NOTREACHED */
1330             return 0;
1331     }
1332 }
1333
1334
1335
1336 static ExprNode* RemoveSyms (ExprNode* Expr, int MustClone)
1337 /* Remove resolved symbols from the tree by cloning symbol expressions */
1338 {
1339     /* Accept NULL pointers */
1340     if (Expr == 0) {
1341         return 0;
1342     }
1343
1344     /* Special node handling */
1345     switch (Expr->Op) {
1346
1347         case EXPR_SYMBOL:
1348             if (SymHasExpr (Expr->V.Sym)) {
1349                 /* The symbol has an expression tree */
1350                 SymEntry* Sym = Expr->V.Sym;
1351                 if (SymHasUserMark (Sym)) {
1352                     /* Circular definition */
1353                     if (Verbose) {
1354                         DumpExpr (Expr);
1355                     }
1356                     PError (GetSymPos (Sym), ERR_CIRCULAR_REFERENCE);
1357                     return LiteralExpr (0);             /* Return a dummy value */
1358                 }
1359                 SymMarkUser (Sym);
1360                 Expr = RemoveSyms (GetSymExpr (Sym), 1);
1361                 SymUnmarkUser (Sym);
1362                 return Expr;
1363             } else if (SymIsConst (Expr->V.Sym)) {
1364                 /* The symbol is a constant */
1365                 return LiteralExpr (GetSymVal (Expr->V.Sym));
1366             }
1367             break;
1368
1369         case EXPR_ULABEL:
1370             if (ULabCanResolve ()) {
1371                 ExprNode* NewExpr = ULabResolve (Expr->V.Val);
1372                 FreeExpr (Expr);
1373                 Expr = NewExpr;
1374             }
1375             break;
1376
1377     }
1378
1379     /* Clone the current node if needed */
1380     if (MustClone) {
1381
1382         /* Create a new node */
1383         ExprNode* Clone = NewExprNode ();
1384
1385         /* Clone the operation */
1386         Clone->Op = Expr->Op;
1387
1388         /* Clone the attribute if needed */
1389         switch (Expr->Op) {
1390
1391             case EXPR_LITERAL:
1392             case EXPR_ULABEL:
1393                 Clone->V.Val = Expr->V.Val;
1394                 break;
1395
1396             case EXPR_SYMBOL:
1397                 Clone->V.Sym = Expr->V.Sym;
1398                 break;
1399
1400             case EXPR_SEGMENT:
1401                 Clone->V.SegNum = Expr->V.SegNum;
1402                 break;
1403
1404         }
1405
1406         /* Clone the tree nodes */
1407         Clone->Left = RemoveSyms (Expr->Left, MustClone);
1408         Clone->Right = RemoveSyms (Expr->Right, MustClone);
1409
1410         /* Done */
1411         return Clone;
1412
1413     } else {
1414
1415         /* Nothing to clone */
1416         Expr->Left = RemoveSyms (Expr->Left, MustClone);
1417         Expr->Right = RemoveSyms (Expr->Right, MustClone);
1418
1419         /* Done */
1420         return Expr;
1421
1422     }
1423 }
1424
1425
1426
1427 static ExprNode* ConstExtract (ExprNode* Expr, long* Val, int Sign)
1428 /* Extract and evaluate all constant factors in an subtree that has only
1429  * additions and subtractions.
1430  */
1431 {
1432     if (Expr->Op == EXPR_LITERAL) {
1433         if (Sign < 0) {
1434             *Val -= Expr->V.Val;
1435         } else {
1436             *Val += Expr->V.Val;
1437         }
1438         FreeExprNode (Expr);
1439         return 0;
1440     }
1441
1442     if (Expr->Op == EXPR_PLUS || Expr->Op == EXPR_MINUS) {
1443         ExprNode* Left;
1444         ExprNode* Right;
1445         Left = ConstExtract (Expr->Left, Val, Sign);
1446         if (Expr->Op == EXPR_MINUS) {
1447             Sign = -Sign;
1448         }
1449         Right = ConstExtract (Expr->Right, Val, Sign);
1450         if (Left == 0 && Right == 0) {
1451             FreeExprNode (Expr);
1452             return 0;
1453         } else if (Left == 0) {
1454             FreeExprNode (Expr);
1455             return Right;
1456         } else if (Right == 0) {
1457             FreeExprNode (Expr);
1458             return Left;
1459         } else {
1460             /* Check for SEG - SEG which is now possible */
1461             if (Left->Op == EXPR_SEGMENT && Right->Op == EXPR_SEGMENT &&
1462                 Left->V.SegNum == Right->V.SegNum) {
1463                 /* SEG - SEG, remove it completely */
1464                 FreeExprNode (Left);
1465                 FreeExprNode (Right);
1466                 FreeExprNode (Expr);
1467                 return 0;
1468             } else {
1469                 Expr->Left  = Left;
1470                 Expr->Right = Right;
1471                 return Expr;
1472             }
1473         }
1474     }
1475
1476     /* Some other sort of node, finalize the terms */
1477     if (Expr->Left) {
1478         Expr->Left = FinalizeExpr (Expr->Left);
1479     }
1480     if (Expr->Right) {
1481         Expr->Right = FinalizeExpr (Expr->Right);
1482     }
1483
1484     return Expr;
1485 }
1486
1487
1488
1489 ExprNode* FinalizeExpr (ExprNode* Expr)
1490 /* Resolve any symbols by cloning the symbol expression tree instead of the
1491  * symbol reference, then try to simplify the expression as much as possible.
1492  * This function must only be called if all symbols are resolved (no undefined
1493  * symbol errors).
1494  */
1495 {
1496     long Val = 0;
1497     ExprNode* N;
1498
1499     Expr = RemoveSyms (Expr, 0);
1500     Expr = ConstExtract (Expr, &Val, 1);
1501     if (Expr == 0) {
1502         /* Reduced to a literal value */
1503         Expr = LiteralExpr (Val);
1504     } else if (Val) {
1505         /* Extracted a value */
1506         N = NewExprNode ();
1507         N->Op = EXPR_PLUS;
1508         N->Left = Expr;
1509         N->Right = LiteralExpr (Val);
1510         Expr = N;
1511     }
1512     return Expr;
1513 }
1514
1515
1516
1517 ExprNode* CloneExpr (ExprNode* Expr)
1518 /* Clone the given expression tree. The function will simply clone symbol
1519  * nodes, it will not resolve them.
1520  */
1521 {
1522     ExprNode* Clone;
1523
1524     /* Accept NULL pointers */
1525     if (Expr == 0) {
1526         return 0;
1527     }
1528
1529     /* Get a new node */
1530     Clone = NewExprNode ();
1531
1532     /* Clone the operation */
1533     Clone->Op = Expr->Op;
1534
1535     /* Clone the attribute if needed */
1536     switch (Expr->Op) {
1537
1538         case EXPR_LITERAL:
1539         case EXPR_ULABEL:
1540             Clone->V.Val = Expr->V.Val;
1541             break;
1542
1543         case EXPR_SYMBOL:
1544             Clone->V.Sym = Expr->V.Sym;
1545             break;
1546
1547         case EXPR_SEGMENT:
1548             Clone->V.SegNum = Expr->V.SegNum;
1549             break;
1550
1551     }
1552
1553     /* Clone the tree nodes */
1554     Clone->Left = CloneExpr (Expr->Left);
1555     Clone->Right = CloneExpr (Expr->Right);
1556
1557     /* Done */
1558     return Clone;
1559 }
1560
1561
1562
1563 void WriteExpr (ExprNode* Expr)
1564 /* Write the given expression to the object file */
1565 {
1566     /* Null expressions are encoded by a type byte of zero */
1567     if (Expr == 0) {
1568         ObjWrite8 (0);
1569         return;
1570     }
1571
1572     /* Write the expression code */
1573     ObjWrite8 (Expr->Op);
1574
1575     /* If the is a leafnode, write the expression attribute, otherwise
1576      * write the expression operands.
1577      */
1578     switch (Expr->Op) {
1579
1580         case EXPR_LITERAL:
1581             ObjWrite32 (Expr->V.Val);
1582             break;
1583
1584         case EXPR_SYMBOL:
1585             /* Maybe we should use a code here? */
1586             CHECK (SymIsImport (Expr->V.Sym));  /* Safety */
1587             ObjWrite16 (GetSymIndex (Expr->V.Sym));
1588             break;
1589
1590         case EXPR_SEGMENT:
1591             ObjWrite8 (Expr->V.SegNum);
1592             break;
1593
1594         case EXPR_ULABEL:
1595             Internal ("WriteExpr: Cannot write EXPR_ULABEL nodes");
1596             break;
1597
1598         default:
1599             /* Not a leaf node */
1600             WriteExpr (Expr->Left);
1601             WriteExpr (Expr->Right);
1602             break;
1603
1604     }
1605 }
1606
1607
1608