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