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