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