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