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
  38 #include "error.h"
  39 #include "global.h"
  40 #include "instr.h"
  41 #include "mem.h"
  42 #include "objcode.h"
  43 #include "objfile.h"
  44 #include "scanner.h"
  45 #include "symtab.h"
  46 #include "toknode.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 FuncXMatch (void)
 471 /* Handle the .XMATCH function */
 472 {
 473     return DoMatch (tcIdentical);
 474 }
 475
 476
 477
 478 static ExprNode* Function (int (*F) (void))
 479 /* Handle builtin functions */
 480 {
 481     long Result;
 482
 483     /* Skip the keyword */
 484     NextTok ();
 485
 486     /* Expression must be enclosed in braces */
 487     if (Tok != TOK_LPAREN) {
 488         Error (ERR_LPAREN_EXPECTED);
 489         SkipUntilSep ();
 490         return LiteralExpr (0);
 491     }
 492     NextTok ();
 493
 494     /* Call the function itself */
 495     Result = (F () != 0);
 496
 497     /* Closing brace must follow */
 498     ConsumeRParen ();
 499
 500     /* Return an expression node with the boolean code */
 501     return LiteralExpr (Result);
 502 }
 503
 504
 505
 506 static ExprNode* Factor (void)
 507 {
 508     ExprNode* N;
 509     SymEntry* S;
 510
 511     switch (Tok) {
 512
 513         case TOK_INTCON:
 514         case TOK_CHARCON:
 515             N = LiteralExpr (IVal);
 516             NextTok ();
 517             break;
 518
 519         case TOK_NAMESPACE:
 520             NextTok ();
 521             if (Tok != TOK_IDENT) {
 522                 Error (ERR_IDENT_EXPECTED);
 523                 N = LiteralExpr (0);    /* Dummy */
 524             } else {
 525                 S = SymRefGlobal (SVal);
 526                 if (SymIsConst (S)) {
 527                     /* Use the literal value instead */
 528                     N = LiteralExpr (GetSymVal (S));
 529                 } else {
 530                     /* Create symbol node */
 531                     N = NewExprNode ();
 532                     N->Op    = EXPR_SYMBOL;
 533                     N->V.Sym = S;
 534                 }
 535                 NextTok ();
 536             }
 537             break;
 538
 539         case TOK_IDENT:
 540             S = SymRef (SVal);
 541             if (SymIsConst (S)) {
 542                 /* Use the literal value instead */
 543                 N = LiteralExpr (GetSymVal (S));
 544             } else {
 545                 /* Create symbol node */
 546                 N = NewExprNode ();
 547                 N->Op    = EXPR_SYMBOL;
 548                 N->V.Sym = S;
 549             }
 550             NextTok ();
 551             break;
 552
 553         case TOK_ULABEL:
 554             N = ULabRef (IVal);
 555             NextTok ();
 556             break;
 557
 558         case TOK_MINUS:
 559             NextTok ();
 560             N = NewExprNode ();
 561             N->Left = Factor ();
 562             N->Op   = EXPR_UNARY_MINUS;
 563             break;
 564
 565         case TOK_NOT:
 566             NextTok ();
 567             N = NewExprNode ();
 568             N->Left = Factor ();
 569             N->Op   = EXPR_NOT;
 570             break;
 571
 572         case TOK_STAR:
 573         case TOK_PC:
 574             NextTok ();
 575             N = CurrentPC ();
 576             break;
 577
 578         case TOK_LT:
 579             NextTok ();
 580             N = NewExprNode ();
 581             N->Left = Factor ();
 582             N->Op   = EXPR_LOBYTE;
 583             break;
 584
 585         case TOK_GT:
 586             NextTok ();
 587             N = NewExprNode ();
 588             N->Left = Factor ();
 589             N->Op   = EXPR_HIBYTE;
 590             break;
 591
 592         case TOK_LPAREN:
 593             NextTok ();
 594             N = Expr0 ();
 595             ConsumeRParen ();
 596             break;
 597
 598         case TOK_BLANK:
 599             N = Function (FuncBlank);
 600             break;
 601
 602         case TOK_CONST:
 603             N = Function (FuncConst);
 604             break;
 605
 606         case TOK_CPU:
 607             N = LiteralExpr (GetCPU());
 608             NextTok ();
 609             break;
 610
 611         case TOK_DEFINED:
 612             N = Function (FuncDefined);
 613             break;
 614
 615         case TOK_MATCH:
 616             N = Function (FuncMatch);
 617             break;
 618
 619         case TOK_REFERENCED:
 620             N = Function (FuncReferenced);
 621             break;
 622
 623         case TOK_XMATCH:
 624             N = Function (FuncXMatch);
 625             break;
 626
 627         default:
 628             N = LiteralExpr (0);        /* Dummy */
 629             Error (ERR_SYNTAX);
 630             NextTok ();
 631             break;
 632     }
 633     return N;
 634 }
 635
 636
 637
 638 static ExprNode* Term (void)
 639 {
 640     ExprNode* Root;
 641
 642     /* Read left hand side */
 643     Root = Factor ();
 644
 645     /* Handle multiplicative operations */
 646     while (Tok == TOK_MUL || Tok == TOK_DIV || Tok == TOK_MOD ||
 647            Tok == TOK_AND || Tok == TOK_XOR || Tok == TOK_SHL ||
 648            Tok == TOK_SHR) {
 649
 650         /* Create a new node and insert the left expression */
 651         ExprNode* Left = Root;
 652         Root = NewExprNode ();
 653         Root->Left = Left;
 654
 655         /* Determine the operator token */
 656         switch (Tok) {
 657             case TOK_MUL:       Root->Op = EXPR_MUL;    break;
 658             case TOK_DIV:       Root->Op = EXPR_DIV;    break;
 659             case TOK_MOD:       Root->Op = EXPR_MOD;    break;
 660             case TOK_AND:       Root->Op = EXPR_AND;    break;
 661             case TOK_XOR:       Root->Op = EXPR_XOR;    break;
 662             case TOK_SHL:       Root->Op = EXPR_SHL;    break;
 663             case TOK_SHR:       Root->Op = EXPR_SHR;    break;
 664             default:            Internal ("Invalid token");
 665         }
 666         NextTok ();
 667
 668         /* Parse the right hand side */
 669         Root->Right = Factor ();
 670
 671     }
 672
 673     /* Return the expression tree we've created */
 674     return Root;
 675 }
 676
 677
 678
 679 static ExprNode* SimpleExpr (void)
 680 {
 681     ExprNode* Root;
 682
 683     /* Read left hand side */
 684     Root = Term ();
 685
 686     /* Handle additive operations */
 687     while (Tok == TOK_PLUS || Tok == TOK_MINUS || Tok == TOK_OR) {
 688
 689         /* Create a new node and insert the left expression */
 690         ExprNode* Left = Root;
 691         Root = NewExprNode ();
 692         Root->Left = Left;
 693
 694         /* Determine the operator token */
 695         switch (Tok) {
 696             case TOK_PLUS:      Root->Op = EXPR_PLUS;   break;
 697             case TOK_MINUS:     Root->Op = EXPR_MINUS;  break;
 698             case TOK_OR:        Root->Op = EXPR_OR;     break;
 699             default:            Internal ("Invalid token");
 700         }
 701         NextTok ();
 702
 703         /* Parse the right hand side */
 704         Root->Right = Term ();
 705
 706     }
 707
 708     /* Return the expression tree we've created */
 709     return Root;
 710 }
 711
 712
 713
 714 static ExprNode* BoolExpr (void)
 715 /* Evaluate a boolean expression */
 716 {
 717     /* Read left hand side */
 718     ExprNode* Root = SimpleExpr ();
 719
 720     /* Handle booleans */
 721     while (Tok == TOK_EQ || Tok == TOK_NE || Tok == TOK_LT ||
 722            Tok == TOK_GT || Tok == TOK_LE || Tok == TOK_GE) {
 723
 724         /* Create a new node and insert the left expression */
 725         ExprNode* Left = Root;
 726         Root = NewExprNode ();
 727         Root->Left = Left;
 728
 729         /* Determine the operator token */
 730         switch (Tok) {
 731             case TOK_EQ:        Root->Op = EXPR_EQ;     break;
 732             case TOK_NE:        Root->Op = EXPR_NE;     break;
 733             case TOK_LT:        Root->Op = EXPR_LT;     break;
 734             case TOK_GT:        Root->Op = EXPR_GT;     break;
 735             case TOK_LE:        Root->Op = EXPR_LE;     break;
 736             case TOK_GE:        Root->Op = EXPR_GE;     break;
 737             default:            Internal ("Invalid token");
 738         }
 739         NextTok ();
 740
 741         /* Parse the right hand side */
 742         Root->Right = SimpleExpr ();
 743
 744     }
 745
 746     /* Return the expression tree we've created */
 747     return Root;
 748 }
 749
 750
 751
 752 static ExprNode* Expr2 (void)
 753 /* Boolean operators: AND and XOR */
 754 {
 755     /* Read left hand side */
 756     ExprNode* Root = BoolExpr ();
 757
 758     /* Handle booleans */
 759     while (Tok == TOK_BAND || Tok == TOK_BXOR) {
 760
 761         /* Create a new node and insert the left expression */
 762         ExprNode* Left = Root;
 763         Root = NewExprNode ();
 764         Root->Left = Left;
 765
 766         /* Determine the operator token */
 767         switch (Tok) {
 768             case TOK_BAND:      Root->Op = EXPR_BAND;   break;
 769             case TOK_BXOR:      Root->Op = EXPR_BXOR;   break;
 770             default:            Internal ("Invalid token");
 771         }
 772         NextTok ();
 773
 774         /* Parse the right hand side */
 775         Root->Right = BoolExpr ();
 776
 777     }
 778
 779     /* Return the expression tree we've created */
 780     return Root;
 781 }
 782
 783
 784
 785 static ExprNode* Expr1 (void)
 786 /* Boolean operators: OR */
 787 {
 788     /* Read left hand side */
 789     ExprNode* Root = Expr2 ();
 790
 791     /* Handle booleans */
 792     while (Tok == TOK_BOR) {
 793
 794         /* Create a new node and insert the left expression */
 795         ExprNode* Left = Root;
 796         Root = NewExprNode ();
 797         Root->Left = Left;
 798
 799         /* Determine the operator token */
 800         switch (Tok) {
 801             case TOK_BOR:       Root->Op = EXPR_BOR;    break;
 802             default:            Internal ("Invalid token");
 803         }
 804         NextTok ();
 805
 806         /* Parse the right hand side */
 807         Root->Right = Expr2 ();
 808
 809     }
 810
 811     /* Return the expression tree we've created */
 812     return Root;
 813 }
 814
 815
 816
 817 static ExprNode* Expr0 (void)
 818 /* Boolean operators: NOT */
 819 {
 820     ExprNode* Root;
 821
 822     /* Handle booleans */
 823     if (Tok == TOK_BNOT) {
 824
 825         /* Create a new node */
 826         Root = NewExprNode ();
 827
 828         /* Determine the operator token */
 829         switch (Tok) {
 830             case TOK_BNOT:      Root->Op = EXPR_BNOT;   break;
 831             default:            Internal ("Invalid token");
 832         }
 833         NextTok ();
 834
 835         /* Parse the left hand side, allow more BNOTs */
 836         Root->Left = Expr0 ();
 837
 838     } else {
 839
 840         /* Read left hand side */
 841         Root = Expr1 ();
 842
 843     }
 844
 845     /* Return the expression tree we've created */
 846     return Root;
 847 }
 848
 849
 850
 851 static ExprNode* SimplifyExpr (ExprNode* Root)
 852 /* Try to simplify the given expression tree */
 853 {
 854     if (Root) {
 855         SimplifyExpr (Root->Left);
 856         SimplifyExpr (Root->Right);
 857         if (IsConstExpr (Root)) {
 858             /* The complete expression is constant */
 859             Root->V.Val = GetExprVal (Root);
 860             Root->Op = EXPR_LITERAL;
 861             FreeExpr (Root->Left);
 862             FreeExpr (Root->Right);
 863             Root->Left = Root->Right = 0;
 864         }
 865     }
 866     return Root;
 867 }
 868
 869
 870
 871 ExprNode* Expression (void)
 872 /* Evaluate an expression, build the expression tree on the heap and return
 873  * a pointer to the root of the tree.
 874  */
 875 {
 876     return SimplifyExpr (Expr0 ());
 877 }
 878
 879
 880
 881 long ConstExpression (void)
 882 /* Parse an expression. Check if the expression is const, and print an error
 883  * message if not. Return the value of the expression, or a dummy, if it is
 884  * not constant.
 885  */
 886 {
 887     /* Read the expression, and call finalize (exception here, since we
 888      * expect a const).
 889      */
 890     ExprNode* Expr = FinalizeExpr (Expression ());
 891
 892     /* Return the value */
 893     if (IsConstExpr (Expr)) {
 894         return GetExprVal (Expr);
 895     } else {
 896         Error (ERR_CONSTEXPR_EXPECTED);
 897         return 0;
 898     }
 899 }
 900
 901
 902
 903 ExprNode* LiteralExpr (long Val)
 904 /* Return an expression tree that encodes the given literal value */
 905 {
 906     ExprNode* Expr = NewExprNode ();
 907     Expr->Op = EXPR_LITERAL;
 908     Expr->V.Val = Val;
 909     return Expr;
 910 }
 911
 912
 913
 914 ExprNode* CurrentPC (void)
 915 /* Return the current program counter as expression */
 916 {
 917     ExprNode* Left;
 918     ExprNode* Root;
 919
 920     if (RelocMode) {
 921         /* Create SegmentBase + Offset */
 922         Left = NewExprNode ();
 923         Left->Op = EXPR_SEGMENT;
 924         Left->V.SegNum = GetSegNum ();
 925
 926         Root = NewExprNode ();
 927         Root->Left  = Left;
 928         Root->Right = LiteralExpr (GetPC ());
 929         Root->Op = EXPR_PLUS;
 930     } else {
 931         /* Absolute mode, just return PC value */
 932         Root = LiteralExpr (GetPC ());
 933     }
 934
 935     return Root;
 936 }
 937
 938
 939
 940 ExprNode* SwapExpr (ExprNode* Expr)
 941 /* Return an extended expression with lo and hi bytes swapped */
 942 {
 943     ExprNode* N = NewExprNode ();
 944     N->Op = EXPR_SWAP;
 945     N->Left = Expr;
 946     return N;
 947 }
 948
 949
 950
 951 ExprNode* BranchExpr (unsigned Offs)
 952 /* Return an expression that encodes the difference between current PC plus
 953  * offset and the target expression (that is, Expression() - (*+Offs) ).
 954  */
 955 {
 956     ExprNode* N;
 957     ExprNode* Root;
 958     ExprNode* Left;
 959
 960     /* Create *+Offs */
 961     if (RelocMode) {
 962         Left = NewExprNode ();
 963         Left->Op = EXPR_SEGMENT;
 964         Left->V.SegNum = GetSegNum ();
 965
 966         N = NewExprNode ();
 967         N->Left  = Left;
 968         N->Right = LiteralExpr (GetPC () + Offs);
 969         N->Op = EXPR_PLUS;
 970     } else {
 971         N = LiteralExpr (GetPC () + Offs);
 972     }
 973
 974     /* Create the root node */
 975     Root = NewExprNode ();
 976     Root->Left = Expression ();
 977     Root->Right = N;
 978     Root->Op = EXPR_MINUS;
 979
 980     /* Return the result */
 981     return SimplifyExpr (Root);
 982 }
 983
 984
 985
 986 ExprNode* ULabelExpr (unsigned Num)
 987 /* Return an expression for an unnamed label with the given index */
 988 {
 989     /* Get an expression node */
 990     ExprNode* Node = NewExprNode ();
 991
 992     /* Set the values */
 993     Node->Op    = EXPR_ULABEL;
 994     Node->V.Val = Num;
 995
 996     /* Return the new node */
 997     return Node;
 998 }
 999
1000
1001
1002 void FreeExpr (ExprNode* Root)
1003 /* Free the expression, Root is pointing to. */
1004 {
1005     if (Root) {
1006         FreeExpr (Root->Left);
1007         FreeExpr (Root->Right);
1008         FreeExprNode (Root);
1009     }
1010 }
1011
1012
1013
1014 ExprNode* ForceWordExpr (ExprNode* Expr)
1015 /* Force the given expression into a word and return the result. */
1016 {
1017     /* And the expression by $FFFF to force it into word size */
1018     ExprNode* Root = NewExprNode ();
1019     Root->Left  = Expr;
1020     Root->Op    = EXPR_AND;
1021     Root->Right = LiteralExpr (0xFFFF);
1022
1023     /* Return the result */
1024     return Root;
1025 }
1026
1027
1028
1029 int IsConstExpr (ExprNode* Root)
1030 /* Return true if the given expression is a constant expression, that is, one
1031  * with no references to external symbols.
1032  */
1033 {
1034     int Const;
1035     SymEntry* Sym;
1036
1037     if (EXPR_IS_LEAF (Root->Op)) {
1038         switch (Root->Op) {
1039
1040             case EXPR_LITERAL:
1041                 return 1;
1042
1043             case EXPR_SYMBOL:
1044                 Sym = Root->V.Sym;
1045                 if (SymHasUserMark (Sym)) {
1046                     if (Verbose) {
1047                         DumpExpr (Root);
1048                     }
1049                     PError (GetSymPos (Sym), ERR_CIRCULAR_REFERENCE);
1050                     Const = 0;
1051                 } else {
1052                     SymMarkUser (Sym);
1053                     Const = SymIsConst (Sym);
1054                     SymUnmarkUser (Sym);
1055                 }
1056                 return Const;
1057
1058             default:
1059                 return 0;
1060
1061         }
1062     } else if (EXPR_IS_UNARY (Root->Op)) {
1063
1064         return IsConstExpr (Root->Left);
1065
1066     } else {
1067
1068         /* We must handle shortcut boolean expressions here */
1069         switch (Root->Op) {
1070
1071             case EXPR_BAND:
1072                 if (IsConstExpr (Root->Left)) {
1073                     /* lhs is const, if it is zero, don't eval right */
1074                     if (GetExprVal (Root->Left) == 0) {
1075                         return 1;
1076                     } else {
1077                         return IsConstExpr (Root->Right);
1078                     }
1079                 } else {
1080                     /* lhs not const --> tree not const */
1081                     return 0;
1082                 }
1083                 break;
1084
1085             case EXPR_BOR:
1086                 if (IsConstExpr (Root->Left)) {
1087                     /* lhs is const, if it is not zero, don't eval right */
1088                     if (GetExprVal (Root->Left) != 0) {
1089                         return 1;
1090                     } else {
1091                         return IsConstExpr (Root->Right);
1092                     }
1093                 } else {
1094                     /* lhs not const --> tree not const */
1095                     return 0;
1096                 }
1097                 break;
1098
1099             default:
1100                 /* All others are handled normal */
1101                 return IsConstExpr (Root->Left) && IsConstExpr (Root->Right);
1102         }
1103     }
1104 }
1105
1106
1107
1108 static void CheckByteExpr (const ExprNode* N, int* IsByte)
1109 /* Internal routine that is recursively called to check if there is a zeropage
1110  * symbol in the expression tree.
1111  */
1112 {
1113     if (N) {
1114         switch (N->Op & EXPR_TYPEMASK) {
1115
1116             case EXPR_LEAFNODE:
1117                 switch (N->Op) {
1118
1119                     case EXPR_SYMBOL:
1120                         if (SymIsZP (N->V.Sym)) {
1121                             *IsByte = 1;
1122                         }
1123                         break;
1124
1125                     case EXPR_SEGMENT:
1126                         if (GetSegType (N->V.SegNum) == SEGTYPE_ZP) {
1127                             *IsByte = 1;
1128                         }
1129                         break;
1130
1131                 }
1132                 break;
1133
1134             case EXPR_UNARYNODE:
1135                 CheckByteExpr (N->Left, IsByte);
1136                 break;
1137
1138             case EXPR_BINARYNODE:
1139                 CheckByteExpr (N->Left, IsByte);
1140                 CheckByteExpr (N->Right, IsByte);
1141                 break;
1142
1143             default:
1144                 Internal ("Unknown expression op: %02X", N->Op);
1145         }
1146     }
1147 }
1148
1149
1150
1151 int IsByteExpr (ExprNode* Root)
1152 /* Return true if this is a byte expression */
1153 {
1154     int IsByte;
1155
1156     if (IsConstExpr (Root)) {
1157         if (Root->Op != EXPR_LITERAL) {
1158             SimplifyExpr (Root);
1159         }
1160         return IsByteRange (GetExprVal (Root));
1161     } else if (Root->Op == EXPR_LOBYTE || Root->Op == EXPR_HIBYTE) {
1162         /* Symbol forced to have byte range */
1163         IsByte = 1;
1164     } else {
1165         /* We have undefined symbols in the expression. Assume that the
1166          * expression is a byte expression if there is at least one symbol
1167          * declared as zeropage in it. Being wrong here is not a very big
1168          * problem since the linker knows about all symbols and detects
1169          * error like mixing absolute and zeropage labels.
1170          */
1171         IsByte = 0;
1172         CheckByteExpr (Root, &IsByte);
1173     }
1174     return IsByte;
1175 }
1176
1177
1178
1179 long GetExprVal (ExprNode* Expr)
1180 /* Get the value of a constant expression */
1181 {
1182     long Right, Left;
1183
1184     switch (Expr->Op) {
1185
1186         case EXPR_LITERAL:
1187             return Expr->V.Val;
1188
1189         case EXPR_SYMBOL:
1190             return GetSymVal (Expr->V.Sym);
1191
1192         case EXPR_PLUS:
1193             return GetExprVal (Expr->Left) + GetExprVal (Expr->Right);
1194
1195         case EXPR_MINUS:
1196             return GetExprVal (Expr->Left) - GetExprVal (Expr->Right);
1197
1198         case EXPR_MUL:
1199             return GetExprVal (Expr->Left) * GetExprVal (Expr->Right);
1200
1201         case EXPR_DIV:
1202             Left  = GetExprVal (Expr->Left);
1203             Right = GetExprVal (Expr->Right);
1204             if (Right == 0) {
1205                 Error (ERR_DIV_BY_ZERO);
1206                 return 0;
1207             }
1208             return Left / Right;
1209
1210         case EXPR_MOD:
1211             Left  = GetExprVal (Expr->Left);
1212             Right = GetExprVal (Expr->Right);
1213             if (Right == 0) {
1214                 Error (ERR_MOD_BY_ZERO);
1215                 return 0;
1216             }
1217             return Left % Right;
1218
1219         case EXPR_OR:
1220             return GetExprVal (Expr->Left) | GetExprVal (Expr->Right);
1221
1222         case EXPR_XOR:
1223             return GetExprVal (Expr->Left) ^ GetExprVal (Expr->Right);
1224
1225         case EXPR_AND:
1226             return GetExprVal (Expr->Left) & GetExprVal (Expr->Right);
1227
1228         case EXPR_SHL:
1229             return GetExprVal (Expr->Left) << GetExprVal (Expr->Right);
1230
1231         case EXPR_SHR:
1232             return GetExprVal (Expr->Left) >> GetExprVal (Expr->Right);
1233
1234         case EXPR_EQ:
1235             return (GetExprVal (Expr->Left) == GetExprVal (Expr->Right));
1236
1237         case EXPR_NE:
1238             return (GetExprVal (Expr->Left) != GetExprVal (Expr->Right));
1239
1240         case EXPR_LT:
1241             return (GetExprVal (Expr->Left) < GetExprVal (Expr->Right));
1242
1243         case EXPR_GT:
1244             return (GetExprVal (Expr->Left) > GetExprVal (Expr->Right));
1245
1246         case EXPR_LE:
1247             return (GetExprVal (Expr->Left) <= GetExprVal (Expr->Right));
1248
1249         case EXPR_GE:
1250             return (GetExprVal (Expr->Left) >= GetExprVal (Expr->Right));
1251
1252         case EXPR_UNARY_MINUS:
1253             return -GetExprVal (Expr->Left);
1254
1255         case EXPR_NOT:
1256             return ~GetExprVal (Expr->Left);
1257
1258         case EXPR_LOBYTE:
1259             return GetExprVal (Expr->Left) & 0xFF;
1260
1261         case EXPR_HIBYTE:
1262             return (GetExprVal (Expr->Left) >> 8) & 0xFF;
1263
1264         case EXPR_SWAP:
1265             Left = GetExprVal (Expr->Left);
1266             return ((Left >> 8) & 0x00FF) | ((Left << 8) & 0xFF00);
1267
1268         case EXPR_BAND:
1269             return GetExprVal (Expr->Left) && GetExprVal (Expr->Right);
1270
1271         case EXPR_BOR:
1272             return GetExprVal (Expr->Left) || GetExprVal (Expr->Right);
1273
1274         case EXPR_BXOR:
1275             return (GetExprVal (Expr->Left) != 0) ^ (GetExprVal (Expr->Right) != 0);
1276
1277         case EXPR_BNOT:
1278             return !GetExprVal (Expr->Left);
1279
1280         case EXPR_ULABEL:
1281             Internal ("GetExprVal called for EXPR_ULABEL");
1282             /* NOTREACHED */
1283             return 0;
1284
1285         default:
1286             Internal ("Unknown Op type: %u", Expr->Op);
1287             /* NOTREACHED */
1288             return 0;
1289     }
1290 }
1291
1292
1293
1294 static ExprNode* RemoveSyms (ExprNode* Expr, int MustClone)
1295 /* Remove resolved symbols from the tree by cloning symbol expressions */
1296 {
1297     /* Accept NULL pointers */
1298     if (Expr == 0) {
1299         return 0;
1300     }
1301
1302     /* Special node handling */
1303     switch (Expr->Op) {
1304
1305         case EXPR_SYMBOL:
1306             if (SymHasExpr (Expr->V.Sym)) {
1307                 /* The symbol has an expression tree */
1308                 SymEntry* Sym = Expr->V.Sym;
1309                 if (SymHasUserMark (Sym)) {
1310                     /* Circular definition */
1311                     if (Verbose) {
1312                         DumpExpr (Expr);
1313                     }
1314                     PError (GetSymPos (Sym), ERR_CIRCULAR_REFERENCE);
1315                     return LiteralExpr (0);             /* Return a dummy value */
1316                 }
1317                 SymMarkUser (Sym);
1318                 Expr = RemoveSyms (GetSymExpr (Sym), 1);
1319                 SymUnmarkUser (Sym);
1320                 return Expr;
1321             } else if (SymIsConst (Expr->V.Sym)) {
1322                 /* The symbol is a constant */
1323                 return LiteralExpr (GetSymVal (Expr->V.Sym));
1324             }
1325             break;
1326
1327         case EXPR_ULABEL:
1328             if (ULabCanResolve ()) {
1329                 ExprNode* NewExpr = ULabResolve (Expr->V.Val);
1330                 FreeExpr (Expr);
1331                 Expr = NewExpr;
1332             }
1333             break;
1334
1335     }
1336
1337     /* Clone the current node if needed */
1338     if (MustClone) {
1339
1340         /* Create a new node */
1341         ExprNode* Clone = NewExprNode ();
1342
1343         /* Clone the operation */
1344         Clone->Op = Expr->Op;
1345
1346         /* Clone the attribute if needed */
1347         switch (Expr->Op) {
1348
1349             case EXPR_LITERAL:
1350             case EXPR_ULABEL:
1351                 Clone->V.Val = Expr->V.Val;
1352                 break;
1353
1354             case EXPR_SYMBOL:
1355                 Clone->V.Sym = Expr->V.Sym;
1356                 break;
1357
1358             case EXPR_SEGMENT:
1359                 Clone->V.SegNum = Expr->V.SegNum;
1360                 break;
1361
1362         }
1363
1364         /* Clone the tree nodes */
1365         Clone->Left = RemoveSyms (Expr->Left, MustClone);
1366         Clone->Right = RemoveSyms (Expr->Right, MustClone);
1367
1368         /* Done */
1369         return Clone;
1370
1371     } else {
1372
1373         /* Nothing to clone */
1374         Expr->Left = RemoveSyms (Expr->Left, MustClone);
1375         Expr->Right = RemoveSyms (Expr->Right, MustClone);
1376
1377         /* Done */
1378         return Expr;
1379
1380     }
1381 }
1382
1383
1384
1385 static ExprNode* ConstExtract (ExprNode* Expr, long* Val, int Sign)
1386 /* Extract and evaluate all constant factors in an subtree that has only
1387  * additions and subtractions.
1388  */
1389 {
1390     if (Expr->Op == EXPR_LITERAL) {
1391         if (Sign < 0) {
1392             *Val -= Expr->V.Val;
1393         } else {
1394             *Val += Expr->V.Val;
1395         }
1396         FreeExprNode (Expr);
1397         return 0;
1398     }
1399
1400     if (Expr->Op == EXPR_PLUS || Expr->Op == EXPR_MINUS) {
1401         ExprNode* Left;
1402         ExprNode* Right;
1403         Left = ConstExtract (Expr->Left, Val, Sign);
1404         if (Expr->Op == EXPR_MINUS) {
1405             Sign = -Sign;
1406         }
1407         Right = ConstExtract (Expr->Right, Val, Sign);
1408         if (Left == 0 && Right == 0) {
1409             FreeExprNode (Expr);
1410             return 0;
1411         } else if (Left == 0) {
1412             FreeExprNode (Expr);
1413             return Right;
1414         } else if (Right == 0) {
1415             FreeExprNode (Expr);
1416             return Left;
1417         } else {
1418             /* Check for SEG - SEG which is now possible */
1419             if (Left->Op == EXPR_SEGMENT && Right->Op == EXPR_SEGMENT &&
1420                 Left->V.SegNum == Right->V.SegNum) {
1421                 /* SEG - SEG, remove it completely */
1422                 FreeExprNode (Left);
1423                 FreeExprNode (Right);
1424                 FreeExprNode (Expr);
1425                 return 0;
1426             } else {
1427                 Expr->Left  = Left;
1428                 Expr->Right = Right;
1429                 return Expr;
1430             }
1431         }
1432     }
1433
1434     /* Some other sort of node, finalize the terms */
1435     if (Expr->Left) {
1436         Expr->Left = FinalizeExpr (Expr->Left);
1437     }
1438     if (Expr->Right) {
1439         Expr->Right = FinalizeExpr (Expr->Right);
1440     }
1441
1442     return Expr;
1443 }
1444
1445
1446
1447 ExprNode* FinalizeExpr (ExprNode* Expr)
1448 /* Resolve any symbols by cloning the symbol expression tree instead of the
1449  * symbol reference, then try to simplify the expression as much as possible.
1450  * This function must only be called if all symbols are resolved (no undefined
1451  * symbol errors).
1452  */
1453 {
1454     long Val = 0;
1455     ExprNode* N;
1456
1457     Expr = RemoveSyms (Expr, 0);
1458     Expr = ConstExtract (Expr, &Val, 1);
1459     if (Expr == 0) {
1460         /* Reduced to a literal value */
1461         Expr = LiteralExpr (Val);
1462     } else if (Val) {
1463         /* Extracted a value */
1464         N = NewExprNode ();
1465         N->Op = EXPR_PLUS;
1466         N->Left = Expr;
1467         N->Right = LiteralExpr (Val);
1468         Expr = N;
1469     }
1470     return Expr;
1471 }
1472
1473
1474
1475 ExprNode* CloneExpr (ExprNode* Expr)
1476 /* Clone the given expression tree. The function will simply clone symbol
1477  * nodes, it will not resolve them.
1478  */
1479 {
1480     ExprNode* Clone;
1481
1482     /* Accept NULL pointers */
1483     if (Expr == 0) {
1484         return 0;
1485     }
1486
1487     /* Get a new node */
1488     Clone = NewExprNode ();
1489
1490     /* Clone the operation */
1491     Clone->Op = Expr->Op;
1492
1493     /* Clone the attribute if needed */
1494     switch (Expr->Op) {
1495
1496         case EXPR_LITERAL:
1497         case EXPR_ULABEL:
1498             Clone->V.Val = Expr->V.Val;
1499             break;
1500
1501         case EXPR_SYMBOL:
1502             Clone->V.Sym = Expr->V.Sym;
1503             break;
1504
1505         case EXPR_SEGMENT:
1506             Clone->V.SegNum = Expr->V.SegNum;
1507             break;
1508
1509     }
1510
1511     /* Clone the tree nodes */
1512     Clone->Left = CloneExpr (Expr->Left);
1513     Clone->Right = CloneExpr (Expr->Right);
1514
1515     /* Done */
1516     return Clone;
1517 }
1518
1519
1520
1521 void WriteExpr (ExprNode* Expr)
1522 /* Write the given expression to the object file */
1523 {
1524     /* Null expressions are encoded by a type byte of zero */
1525     if (Expr == 0) {
1526         ObjWrite8 (0);
1527         return;
1528     }
1529
1530     /* Write the expression code */
1531     ObjWrite8 (Expr->Op);
1532
1533     /* If the is a leafnode, write the expression attribute, otherwise
1534      * write the expression operands.
1535      */
1536     switch (Expr->Op) {
1537
1538         case EXPR_LITERAL:
1539             ObjWrite32 (Expr->V.Val);
1540             break;
1541
1542         case EXPR_SYMBOL:
1543             /* Maybe we should use a code here? */
1544             CHECK (SymIsImport (Expr->V.Sym));  /* Safety */
1545             ObjWrite16 (GetSymIndex (Expr->V.Sym));
1546             break;
1547
1548         case EXPR_SEGMENT:
1549             ObjWrite8 (Expr->V.SegNum);
1550             break;
1551
1552         case EXPR_ULABEL:
1553             Internal ("WriteExpr: Cannot write EXPR_ULABEL nodes");
1554             break;
1555
1556         default:
1557             /* Not a leaf node */
1558             WriteExpr (Expr->Left);
1559             WriteExpr (Expr->Right);
1560             break;
1561
1562     }
1563 }
1564
1565
1566