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