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