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