git.sur5r.net Git - cc65/blob - src/ca65/expr.c

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