Usermode/Libraries/libspiderscript.so_src/ast_to_bytecode.c

   1 /*
   2  * SpiderScript Library
   3  *
   4  * AST to Bytecode Conversion
   5  */
   6 #include <stdlib.h>
   7 #include <stdio.h>
   8 #include <stdarg.h>
   9 #include <string.h>
  10 #include "ast.h"
  11 #include "bytecode_gen.h"
  12 #include "bytecode_ops.h"
  13
  14 #define TRACE_VAR_LOOKUPS       0
  15 #define TRACE_NODE_RETURNS      0
  16
  17 // === IMPORTS ===
  18 extern tSpiderFunction  *gpExports_First;
  19
  20 // === TYPES ===
  21 typedef struct sAST_BlockInfo
  22 {
  23         struct sAST_BlockInfo   *Parent;
  24         void    *Handle;
  25         const char      *Tag;
  26
  27          int    BreakTarget;
  28          int    ContinueTarget;
  29 } tAST_BlockInfo;
  30
  31 // === PROTOTYPES ===
  32 // Node Traversal
  33  int    AST_ConvertNode(tAST_BlockInfo *Block, tAST_Node *Node);
  34 // Variables
  35  int    BC_Variable_Define(tAST_BlockInfo *Block, int Type, const char *Name);
  36  int    BC_Variable_SetValue(tAST_BlockInfo *Block, tAST_Node *VarNode);
  37  int    BC_Variable_GetValue(tAST_BlockInfo *Block, tAST_Node *VarNode);
  38 // - Errors
  39 void    AST_RuntimeMessage(tAST_Node *Node, const char *Type, const char *Format, ...);
  40 void    AST_RuntimeError(tAST_Node *Node, const char *Format, ...);
  41
  42 // === GLOBALS ===
  43 // int  giNextBlockIdent = 1;
  44
  45 // === CODE ===
  46 /**
  47  * \brief Convert a function into bytecode
  48  */
  49 tBC_Function *Bytecode_ConvertFunction(tAST_Function *ASTFcn)
  50 {
  51         tBC_Function    *ret;
  52         tAST_BlockInfo bi = {0};
  53
  54         {
  55                 tAST_Node *arg;
  56                  int    i;
  57                 char    *arg_names[ASTFcn->ArgumentCount];
  58                  int    arg_types[ASTFcn->ArgumentCount];
  59
  60                 for(arg = ASTFcn->Arguments, i = 0; arg; arg = arg->NextSibling, i ++)
  61                 {
  62                         arg_names[i] = arg->DefVar.Name;
  63                         arg_types[i] = arg->DefVar.DataType;
  64                 }
  65
  66                 ret = Bytecode_CreateFunction(ASTFcn->Name, ASTFcn->ArgumentCount, arg_names, arg_types);
  67                 if(!ret)        return NULL;
  68         }
  69
  70         bi.Handle = ret;
  71         if( AST_ConvertNode(&bi, ASTFcn->Code) )
  72         {
  73                 Bytecode_DeleteFunction(ret);
  74                 return NULL;
  75         }
  76         return ret;
  77 }
  78
  79 /**
  80  * \brief Convert a node into bytecode
  81  * \param Block Execution context
  82  * \param Node  Node to execute
  83  */
  84 int AST_ConvertNode(tAST_BlockInfo *Block, tAST_Node *Node)
  85 {
  86         tAST_Node       *node;
  87          int    ret = 0;
  88          int    i, op = 0;
  89
  90         switch(Node->Type)
  91         {
  92         // No Operation
  93         case NODETYPE_NOP:
  94                 break;
  95
  96         // Code block
  97         case NODETYPE_BLOCK:
  98                 Bytecode_AppendEnterContext(Block->Handle);     // Create a new block
  99                 {
 100                         tAST_BlockInfo  blockInfo;
 101                         blockInfo.Parent = Block;
 102                         blockInfo.Handle = Block->Handle;
 103                         blockInfo.ContinueTarget = 0;
 104                         blockInfo.BreakTarget = 0;
 105                         // Loop over all nodes, or until the return value is set
 106                         for(node = Node->Block.FirstChild;
 107                                 node;
 108                                 node = node->NextSibling )
 109                         {
 110                                 AST_ConvertNode(Block, node);
 111                         }
 112                 }
 113                 Bytecode_AppendLeaveContext(Block->Handle);     // Leave this context
 114                 break;
 115
 116         // Assignment
 117         case NODETYPE_ASSIGN:
 118                 // TODO: Support assigning to object attributes
 119                 if( Node->Assign.Dest->Type != NODETYPE_VARIABLE ) {
 120                         AST_RuntimeError(Node, "LVALUE of assignment is not a variable");
 121                         return -1;
 122                 }
 123                 ret = AST_ConvertNode(Block, Node->Assign.Value);
 124                 if(ret) return ret;
 125
 126                 // Perform assignment operation
 127                 if( Node->Assign.Operation != NODETYPE_NOP )
 128                 {
 129
 130                         ret = BC_Variable_GetValue(Block, Node->Assign.Dest);
 131                         if(ret) return ret;
 132                         Bytecode_AppendBinOp(Block->Handle, Node->Assign.Operation);
 133                 }
 134
 135                 // Set the variable value
 136                 ret = BC_Variable_SetValue( Block, Node->Assign.Dest );
 137                 break;
 138
 139         // Post increment/decrement
 140         case NODETYPE_POSTINC:
 141         case NODETYPE_POSTDEC:
 142                 Bytecode_AppendConstInt(Block->Handle, 1);
 143
 144                 // TODO: Support assigning to object attributes
 145                 if( Node->UniOp.Value->Type != NODETYPE_VARIABLE ) {
 146                         AST_RuntimeError(Node, "LVALUE of assignment is not a variable");
 147                         return -1;
 148                 }
 149
 150                 ret = BC_Variable_GetValue(Block, Node->UniOp.Value);
 151                 if(ret) return ret;
 152
 153                 if( Node->Type == NODETYPE_POSTDEC )
 154                         Bytecode_AppendBinOp(Block->Handle, NODETYPE_SUBTRACT);
 155                 else
 156                         Bytecode_AppendBinOp(Block->Handle, NODETYPE_ADD);
 157                 if(ret) return ret;
 158
 159                 ret = BC_Variable_SetValue(Block, Node->UniOp.Value);
 160                 if(ret) return ret;
 161                 break;
 162
 163         // Function Call
 164         case NODETYPE_METHODCALL:
 165         case NODETYPE_FUNCTIONCALL:
 166         case NODETYPE_CREATEOBJECT:
 167                 i = 0;
 168                 for(node = Node->FunctionCall.FirstArg; node; node = node->NextSibling)
 169                 {
 170                         ret = AST_ConvertNode(Block, node);
 171                         if(ret) return ret;
 172                         i ++;
 173                 }
 174
 175                 // Call the function
 176                 if( Node->Type == NODETYPE_CREATEOBJECT )
 177                 {
 178                         // TODO: Sanity check stack top
 179                         Bytecode_AppendCreateObj(Block->Handle, Node->FunctionCall.Name, i);
 180                 }
 181                 else if( Node->Type == NODETYPE_METHODCALL )
 182                 {
 183                         // TODO: Sanity check stack top
 184                         ret = AST_ConvertNode(Block, Node->FunctionCall.Object);
 185                         if(ret) return ret;
 186                         Bytecode_AppendMethodCall(Block->Handle, Node->FunctionCall.Name, i);
 187                 }
 188                 else
 189                 {
 190                         Bytecode_AppendFunctionCall(Block->Handle, Node->FunctionCall.Name, i);
 191                 }
 192                 break;
 193
 194         // Conditional
 195         case NODETYPE_IF: {
 196                  int    if_true, if_end;
 197                 ret = AST_ConvertNode(Block, Node->If.Condition);
 198                 if(ret) return ret;
 199
 200                 if_true = Bytecode_AllocateLabel(Block->Handle);
 201                 if_end = Bytecode_AllocateLabel(Block->Handle);
 202
 203                 Bytecode_AppendCondJump(Block->Handle, if_true);
 204
 205                 // False
 206                 ret = AST_ConvertNode(Block, Node->If.False);
 207                 if(ret) return ret;
 208                 Bytecode_AppendJump(Block->Handle, if_end);
 209
 210                 // True
 211                 Bytecode_SetLabel(Block->Handle, if_true);
 212                 ret = AST_ConvertNode(Block, Node->If.True);
 213                 if(ret) return ret;
 214
 215                 // End
 216                 Bytecode_SetLabel(Block->Handle, if_end);
 217                 } break;
 218
 219         // Loop
 220         case NODETYPE_LOOP: {
 221                  int    loop_start, loop_end;
 222                  int    saved_break, saved_continue;
 223                 const char      *saved_tag;
 224
 225                 // Initialise
 226                 ret = AST_ConvertNode(Block, Node->For.Init);
 227                 if(ret) return ret;
 228
 229                 loop_start = Bytecode_AllocateLabel(Block->Handle);
 230                 loop_end = Bytecode_AllocateLabel(Block->Handle);
 231
 232                 saved_break = Block->BreakTarget;
 233                 saved_continue = Block->ContinueTarget;
 234                 saved_tag = Block->Tag;
 235                 Block->BreakTarget = loop_end;
 236                 Block->ContinueTarget = loop_end;
 237                 Block->Tag = Node->For.Tag;
 238
 239                 Bytecode_SetLabel(Block->Handle, loop_start);
 240
 241                 // Check initial condition
 242                 if( !Node->For.bCheckAfter )
 243                 {
 244                         ret = AST_ConvertNode(Block, Node->For.Condition);
 245                         if(ret) return ret;
 246                         Bytecode_AppendUniOp(Block->Handle, NODETYPE_LOGICALNOT);
 247                         Bytecode_AppendCondJump(Block->Handle, loop_end);
 248                 }
 249
 250                 // Code
 251                 ret = AST_ConvertNode(Block, Node->For.Code);
 252                 if(ret) return ret;
 253
 254                 // Increment
 255                 ret = AST_ConvertNode(Block, Node->For.Increment);
 256                 if(ret) return ret;
 257
 258                 // Tail check
 259                 if( Node->For.bCheckAfter )
 260                 {
 261                         ret = AST_ConvertNode(Block, Node->For.Condition);
 262                         if(ret) return ret;
 263                         Bytecode_AppendCondJump(Block->Handle, loop_start);
 264                 }
 265
 266                 Bytecode_SetLabel(Block->Handle, loop_end);
 267
 268                 Block->BreakTarget = saved_break;
 269                 Block->ContinueTarget = saved_continue;
 270                 Block->Tag = saved_tag;
 271                 } break;
 272
 273         // Return
 274         case NODETYPE_RETURN:
 275                 ret = AST_ConvertNode(Block, Node->UniOp.Value);
 276                 if(ret) return ret;
 277                 Bytecode_AppendReturn(Block->Handle);
 278                 break;
 279
 280         case NODETYPE_BREAK:
 281         case NODETYPE_CONTINUE: {
 282                 tAST_BlockInfo  *bi = Block;
 283                 if( Node->Variable.Name[0] ) {
 284                         while(bi && strcmp(bi->Tag, Node->Variable.Name) == 0)  bi = bi->Parent;
 285                 }
 286                 if( !bi )       return 1;
 287                 // TODO: Check if BreakTarget/ContinueTarget are valid
 288                 if( Node->Type == NODETYPE_BREAK )
 289                         Bytecode_AppendJump(Block->Handle, bi->BreakTarget);
 290                 else
 291                         Bytecode_AppendJump(Block->Handle, bi->ContinueTarget);
 292                 } break;
 293
 294         // Define a variable
 295         case NODETYPE_DEFVAR:
 296                 ret = BC_Variable_Define(Block, Node->DefVar.DataType, Node->DefVar.Name);
 297                 if(ret) return ret;
 298
 299                 if( Node->DefVar.InitialValue )
 300                 {
 301                         ret = AST_ConvertNode(Block, Node->DefVar.InitialValue);
 302                         if(ret) return ret;
 303                         Bytecode_AppendSaveVar(Block->Handle, Node->DefVar.Name);
 304                 }
 305                 break;
 306
 307         // Scope
 308         case NODETYPE_SCOPE:
 309                 Bytecode_AppendSubNamespace(Block->Handle, Node->Scope.Name);
 310                 ret = AST_ConvertNode(Block, Node->Scope.Element);
 311                 break;
 312
 313         // Variable
 314         case NODETYPE_VARIABLE:
 315                 ret = BC_Variable_GetValue( Block, Node );
 316                 break;
 317
 318         // Element of an Object
 319         case NODETYPE_ELEMENT:
 320                 ret = AST_ConvertNode( Block, Node->Scope.Element );
 321                 if(ret) return ret;
 322
 323                 Bytecode_AppendElement(Block->Handle, Node->Scope.Name);
 324                 break;
 325
 326         // Cast a value to another
 327         case NODETYPE_CAST:
 328                 ret = AST_ConvertNode(Block, Node->Cast.Value);
 329                 if(ret) return ret;
 330                 Bytecode_AppendCast(Block->Handle, Node->Cast.DataType);
 331                 break;
 332
 333         // Index into an array
 334         case NODETYPE_INDEX:
 335                 ret = AST_ConvertNode(Block, Node->BinOp.Left); // Array
 336                 if(ret) return ret;
 337                 ret = AST_ConvertNode(Block, Node->BinOp.Right);        // Offset
 338                 if(ret) return ret;
 339
 340                 Bytecode_AppendIndex(Block->Handle);
 341                 break;
 342
 343         // TODO: Implement runtime constants
 344         case NODETYPE_CONSTANT:
 345                 // TODO: Scan namespace for constant name
 346                 AST_RuntimeError(Node, "TODO - Runtime Constants");
 347                 ret = -1;
 348                 break;
 349
 350         // Constant Values
 351         case NODETYPE_STRING:
 352                 Bytecode_AppendConstString(Block->Handle, Node->Constant.String.Data, Node->Constant.String.Length);
 353                 break;
 354         case NODETYPE_INTEGER:
 355                 Bytecode_AppendConstInt(Block->Handle, Node->Constant.Integer);
 356                 break;
 357         case NODETYPE_REAL:
 358                 Bytecode_AppendConstInt(Block->Handle, Node->Constant.Real);
 359                 break;
 360
 361         // --- Operations ---
 362         // Boolean Operations
 363         case NODETYPE_LOGICALNOT:       // Logical NOT (!)
 364                 if(!op) op = BC_OP_LOGICNOT;
 365         case NODETYPE_BWNOT:    // Bitwise NOT (~)
 366                 if(!op) op = BC_OP_BITNOT;
 367         case NODETYPE_NEGATE:   // Negation (-)
 368                 if(!op) op = BC_OP_NEG;
 369                 ret = AST_ConvertNode(Block, Node->UniOp.Value);
 370                 if(ret) return ret;
 371                 Bytecode_AppendUniOp(Block->Handle, op);
 372                 break;
 373
 374         case NODETYPE_LOGICALAND:       // Logical AND (&&)
 375                 if(!op) op = BC_OP_LOGICAND;
 376         case NODETYPE_LOGICALOR:        // Logical OR (||)
 377                 if(!op) op = BC_OP_LOGICOR;
 378         case NODETYPE_LOGICALXOR:       // Logical XOR (^^)
 379                 if(!op) op = BC_OP_LOGICXOR;
 380         // Comparisons
 381         case NODETYPE_EQUALS:   if(!op) op = BC_OP_EQUALS;
 382         case NODETYPE_LESSTHAN: if(!op) op = BC_OP_LESSTHAN;
 383         case NODETYPE_GREATERTHAN:      if(!op) op = BC_OP_GREATERTHAN;
 384         case NODETYPE_LESSTHANEQUAL:    if(!op) op = BC_OP_LESSTHANOREQUAL;
 385         case NODETYPE_GREATERTHANEQUAL: if(!op) op = BC_OP_GREATERTHANOREQUAL;
 386         // General Binary Operations
 387         case NODETYPE_ADD:      if(!op) op = BC_OP_ADD;
 388         case NODETYPE_SUBTRACT: if(!op) op = BC_OP_SUBTRACT;
 389         case NODETYPE_MULTIPLY: if(!op) op = BC_OP_MULTIPLY;
 390         case NODETYPE_DIVIDE:   if(!op) op = BC_OP_DIVIDE;
 391         case NODETYPE_MODULO:   if(!op) op = BC_OP_MODULO;
 392         case NODETYPE_BWAND:    if(!op) op = BC_OP_BITAND;
 393         case NODETYPE_BWOR:     if(!op) op = BC_OP_BITOR;
 394         case NODETYPE_BWXOR:    if(!op) op = BC_OP_BITXOR;
 395         case NODETYPE_BITSHIFTLEFT:     if(!op) op = BC_OP_BITSHIFTLEFT;
 396         case NODETYPE_BITSHIFTRIGHT:    if(!op) op = BC_OP_BITSHIFTRIGHT;
 397         case NODETYPE_BITROTATELEFT:    if(!op) op = BC_OP_BITROTATELEFT;
 398                 ret = AST_ConvertNode(Block, Node->BinOp.Left);
 399                 if(ret) return ret;
 400                 ret = AST_ConvertNode(Block, Node->BinOp.Right);
 401                 if(ret) return ret;
 402
 403                 Bytecode_AppendBinOp(Block->Handle, op);
 404                 break;
 405
 406         //default:
 407         //      ret = NULL;
 408         //      AST_RuntimeError(Node, "BUG - SpiderScript AST_ConvertNode Unimplemented %i", Node->Type);
 409         //      break;
 410         }
 411
 412         #if TRACE_NODE_RETURNS
 413         if(ret && ret != ERRPTR) {
 414                 AST_RuntimeError(Node, "Ret type of %p %i is %i", Node, Node->Type, ret->Type);
 415         }
 416         else {
 417                 AST_RuntimeError(Node, "Ret type of %p %i is %p", Node, Node->Type, ret);
 418         }
 419         #endif
 420
 421         return ret;
 422 }
 423
 424 /**
 425  * \brief Define a variable
 426  * \param Block Current block state
 427  * \param Type  Type of the variable
 428  * \param Name  Name of the variable
 429  * \return Boolean Failure
 430  */
 431 int BC_Variable_Define(tAST_BlockInfo *Block, int Type, const char *Name)
 432 {
 433         #if 0
 434         tAST_Variable   *var, *prev = NULL;
 435
 436         for( var = Block->FirstVar; var; prev = var, var = var->Next )
 437         {
 438                 if( strcmp(var->Name, Name) == 0 ) {
 439                         AST_RuntimeError(NULL, "Redefinition of variable '%s'", Name);
 440                         return ERRPTR;
 441                 }
 442         }
 443
 444         var = malloc( sizeof(tAST_Variable) + strlen(Name) + 1 );
 445         var->Next = NULL;
 446         var->Type = Type;
 447         strcpy(var->Name, Name);
 448
 449         if(prev)        prev->Next = var;
 450         else    Block->FirstVar = var;
 451
 452         return var;
 453         #else
 454         Bytecode_AppendDefineVar(Block->Handle, Name, Type);
 455         return 0;
 456         #endif
 457 }
 458
 459 tAST_Variable *BC_Variable_Lookup(tAST_BlockInfo *Block, tAST_Node *VarNode, int CreateType)
 460 {
 461         #if 0
 462         tAST_Variable   *var = NULL;
 463
 464         // Speed hack
 465         if( VarNode->BlockState == Block && VarNode->BlockIdent == Block->Ident ) {
 466                 var = VarNode->ValueCache;
 467                 #if TRACE_VAR_LOOKUPS
 468                 AST_RuntimeMessage(VarNode, "debug", "Fast var fetch on '%s' %p (%p:%i)",
 469                         VarNode->Variable.Name, var,
 470                         VarNode->BlockState, VarNode->BlockIdent
 471                         );
 472                 #endif
 473         }
 474         else
 475         {
 476                 tAST_BlockInfo  *bs;
 477                 for( bs = Block; bs; bs = bs->Parent )
 478                 {
 479                         for( var = bs->FirstVar; var; var = var->Next )
 480                         {
 481                                 if( strcmp(var->Name, VarNode->Variable.Name) == 0 )
 482                                         break;
 483                         }
 484                         if(var) break;
 485                 }
 486
 487                 if( !var )
 488                 {
 489                         if( Block->Script->Variant->bDyamicTyped && CreateType != SS_DATATYPE_UNDEF ) {
 490                                 // Define variable
 491                                 var = BC_Variable_Define(Block, CreateType, VarNode->Variable.Name, NULL);
 492                         }
 493                         else
 494                         {
 495                                 AST_RuntimeError(VarNode, "Variable '%s' is undefined", VarNode->Variable.Name);
 496                                 return NULL;
 497                         }
 498                 }
 499
 500                 #if TRACE_VAR_LOOKUPS
 501                 AST_RuntimeMessage(VarNode, "debug", "Saved variable lookup of '%s' %p (%p:%i)",
 502                         VarNode->Variable.Name, var,
 503                         Block, Block->Ident);
 504                 #endif
 505
 506                 VarNode->ValueCache = var;
 507                 VarNode->BlockState = Block;
 508                 VarNode->BlockIdent = Block->Ident;
 509         }
 510
 511         return var;
 512         #else
 513         return (void*)1;
 514         #endif
 515 }
 516
 517 /**
 518  * \brief Set the value of a variable
 519  * \return Boolean Failure
 520  */
 521 int BC_Variable_SetValue(tAST_BlockInfo *Block, tAST_Node *VarNode)
 522 {
 523         tAST_Variable   *var;
 524
 525         var = BC_Variable_Lookup(Block, VarNode, SS_DATATYPE_UNDEF);
 526         if(!var)        return -1;
 527
 528         // TODO: Check types
 529
 530         Bytecode_AppendSaveVar(Block->Handle, VarNode->Variable.Name);
 531         return 0;
 532 }
 533
 534 /**
 535  * \brief Get the value of a variable
 536  */
 537 int BC_Variable_GetValue(tAST_BlockInfo *Block, tAST_Node *VarNode)
 538 {
 539         tAST_Variable   *var;
 540
 541         var = BC_Variable_Lookup(Block, VarNode, 0);
 542         if(!var)        return -1;
 543
 544         Bytecode_AppendLoadVar(Block->Handle, VarNode->Variable.Name);
 545         return 0;
 546 }
 547
 548 #if 0
 549 void AST_RuntimeMessage(tAST_Node *Node, const char *Type, const char *Format, ...)
 550 {
 551         va_list args;
 552
 553         if(Node) {
 554                 fprintf(stderr, "%s:%i: ", Node->File, Node->Line);
 555         }
 556         fprintf(stderr, "%s: ", Type);
 557         va_start(args, Format);
 558         vfprintf(stderr, Format, args);
 559         va_end(args);
 560         fprintf(stderr, "\n");
 561 }
 562 void AST_RuntimeError(tAST_Node *Node, const char *Format, ...)
 563 {
 564         va_list args;
 565
 566         if(Node) {
 567                 fprintf(stderr, "%s:%i: ", Node->File, Node->Line);
 568         }
 569         fprintf(stderr, "error: ");
 570         va_start(args, Format);
 571         vfprintf(stderr, Format, args);
 572         va_end(args);
 573         fprintf(stderr, "\n");
 574 }
 575 #endif