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