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