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