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