git.sur5r.net Git - cc65/blob - src/ca65/expr.c

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