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