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