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