Start of Lua rewrite in C++

[Colin <share-lua@...>]

Hi,

attached is the result of a few hours of starting to rewrite Lua
in C++. Actually I only wanted to understand the internals of Lua
better, so I started making some notes; these notes slowly turned
into code, and in the end I made it compile with g++ 4, for fun.

A few hours of work is of course not nearly enough, but it helped
me understand Lua as much as I need for my current task at hand,
so this is not even 1% complete, but if anybody is interested in 
continuing ... here it is, do as you please.

It's not particularly heavy-weight C++, it's more of a first step
that only changes some obvious things to clean up the cast and
macro chaos. It also orthogonalises a bit of the naming.

Regards, Colin

#include <unistd.h>
#include <assert.h>
#include <string.h>
#include <inttypes.h>


namespace lua
{
   typedef double number;
   typedef uint32_t instruction;

   const size_t minstack = 20;
   const size_t extrastack = 5;
   const size_t maxcalls = 42;
   const size_t extraspace = 0;
   const size_t basicstack = 2 * minstack;
   const size_t basiccallinfo = 8;

#define LUA_ASSERT( aRG1 )                      \
   assert( aRG1 )
   
#define LUA_CHECKED( aRG1, aRG2 )               \
   ( LUA_ASSERT( aRG1 ), ( aRG2 ) )

   typedef void * ( * reallocator )( void * ud, void * ptr, size_t osize, size_t nsize );

   namespace types
   {
      static const uint8_t none = -1;
      static const uint8_t nil = 0;
      static const uint8_t boolean = 1;
      static const uint8_t lightuserdata = 2;
      static const uint8_t number = 3;
      static const uint8_t string = 4;
      static const uint8_t table = 5;
      static const uint8_t closure = 6;
      static const uint8_t userdata = 7;
      static const uint8_t coroutine = 8;

   } // types

   namespace detail
   {
      struct memory;
      struct gc_state;

      namespace types
      {
         using namespace ::lua::types;

         static const uint8_t last_type = 8;
         static const uint8_t type_count = last_type + 1;
         
         static const uint8_t prototype = last_type + 1;
         static const uint8_t upvalue = last_type + 2;
         static const uint8_t deadkey = last_type + 3;

      } // types

      template< class T > T bitmask1( const unsigned b ) { return T( 1 ) << b; }
      template< class T > T bitmask2( const unsigned b, const unsigned c ) { return ( T( 1 ) << b ) | ( T( 1 ) << c ); }

      template< class T > T set1bit( T & t, const unsigned b ) { return t |= bitmask1< T >( b ); }
      template< class T > T set2bits( T & t, const unsigned b, const unsigned c ) { return t |= ( bitmask2< T >( b, c ) ); }

      template< class T > T reset1bit( T & t, const unsigned b ) { return t &= ~ bitmask1< T >( b ); }
      template< class T > T reset2bits( T & t, const unsigned b, const unsigned c ) { return t &= ~ ( bitmask2< T >( b, c ) ); }

      void * default_realloc( void *, void * ptr, size_t, size_t nsize )
      {
         if ( nsize )
            return ::realloc( ptr, nsize );
         
         ::free( ptr );
         return 0;
      }

      void * realloc_wrapper( gc_state * s, void * ptr, const size_t osize, const size_t nsize );
   
      void * malloc( gc_state * s, const size_t nsize )
      {
         return realloc_wrapper( s, 0, 0, nsize );
      }
      
      template< class T >
      T * malloc( gc_state * s )
      {
         return static_cast< T * >( realloc_wrapper( s, 0, 0, sizeof( T ) ) );
      }

      template< class T >
      T * malloc( gc_state * s, const size_t nsize )
      {
         return static_cast< T * >( realloc_wrapper( s, 0, 0, sizeof( T ) * nsize ) );
      }
      
      void free( gc_state * s, void * ptr, size_t osize )
      {
         realloc_wrapper( s, ptr, osize, 0 );
      }
      
      template< class T >
      void free( gc_state * s, T * ptr )
      {
         realloc_wrapper( s, ptr, sizeof( T ), 0 );
      }
      
      template< class T >
      void free( gc_state * s, T * ptr, const size_t osize )
      {
         realloc_wrapper( s, ptr, sizeof( T ) * osize, 0 );
      }

      template< class T >
      T * realloc( gc_state * s, T * ptr, const size_t osize, const size_t nsize )
      {
         return static_cast< T * >( realloc_wrapper( s, ptr, osize * sizeof( T ), nsize * sizeof( T ) ) );
      }
      
      typedef int ( * c_function )( gc_state * );

      union gc_union;

      struct gc_super
      {
         gc_union * next;
         uint8_t type;
         uint8_t mark;
      };

      struct st_value
      {
         union
         {
            gc_union * gc;
            gc_super * super;
            void * pointer;
            ::lua::number number;
            bool boolean;
         };
         uint8_t type;
      };
      
      struct table_node;
      
      struct table_key
      {
         st_value key;
         table_node * next;
      };
   
      struct table_node
      {
         table_key key;
         st_value value;
      };

      struct gc_table : public gc_super
      {
         uint8_t flags;
         uint8_t lsizenode;
         gc_table * meta;
         st_value * array;
         table_node * node;
         table_node * last;
         gc_super * gc_list;
         size_t size;
      };
      
      struct gc_string : public gc_super
      {
         size_t size;
         uint8_t reserved;
         uint32_t hash;
      };

      struct gc_userdata : public gc_super
      {
         size_t size;
         gc_table * env;
         gc_table * meta;
      };

      struct locvar
      {
         gc_string * varname;
         size_t startpc;
         size_t endpc;
      };

      struct gc_upvalue : public gc_super
      {
         st_value * v;

         union
         {
            st_value value;

            struct
            {
               gc_upvalue * prev;
               gc_upvalue * next;
            };
         };
      };

      struct gc_prototype : public gc_super
      {
         st_value * k;  /* constants used by the function */
         instruction * code;
         gc_prototype ** p;  /* functions defined inside the function */
         int * lineinfo;  /* map from opcodes to source lines */
         locvar * locvars;  /* information about local variables */
         gc_string ** upvalues;  /* upvalue names */
         gc_string * source;
         int sizeupvalues;
         int sizek;  /* size of `k' */
         int sizecode;
         int sizelineinfo;
         int sizep;  /* size of `p' */
         int sizelocvars;
         int linedefined;
         int lastlinedefined;
         gc_super * gclist;
         uint8_t nups;  /* number of upvalues */
         uint8_t numparams;
         uint8_t is_vararg;
         uint8_t maxstacksize;      
      };

      struct gc_closure_super : gc_super
      {
         uint8_t C;
         uint8_t upvalues;
         gc_super * gclist;
         gc_table * env;
      };

      struct gc_c_closure : public gc_closure_super
      {
         c_function f;
         st_value upvalue[ 1 ];
      };

      struct gc_lua_closure : public gc_closure_super
      {
         gc_prototype * p;
         gc_upvalue * upvalues[ 1 ];
      };

      union gc_closure
      {
         gc_closure_super s;
         gc_c_closure c;
         gc_lua_closure l;
      };

      struct stringtable
      {
         stringtable()
               : hash( 0 ),
                 used( 0 ),
                 size( 0 )
         { }

         gc_union ** hash;
         size_t used;
         size_t size;
      };
   
      size_t hash_modulus( const size_t hash, const size_t size )
      {
         LUA_ASSERT( ! ( size & ( size - 1 ) ) );
         return hash & ( size - 1 );
      }

      size_t hash_function( const char * s, const size_t l )
      {
         unsigned h = l;
         const size_t step = ( l >> 5 ) + 1;
         
         for ( size_t l1 = l; l1 >= step; l1 -= step )
            h = h ^ ( ( h << 5 ) + ( h >> 2 ) + ( * reinterpret_cast< const unsigned char * >( s + l1 - 1 ) ) );
         
         return h;
      }

      void set_nil( st_value * a )
      {
         a->type = types::nil;
      }

      struct memory
      {
         explicit memory( gc_state * main, reallocator realloc, void * userdata )
               : main( main ),
                 realloc( realloc ),
                 realloc_total( 0 ),
                 realloc_userdata( userdata )
         {
            set_nil( & registry );
         }

         gc_state * main;

         st_value registry;

         reallocator realloc;
         size_t realloc_total;
         void * realloc_userdata;

         stringtable strings;


      };

      struct callinfo
      {
         st_value * st_base;
         st_value * st_func;
         st_value * st_top;

         const instruction * savedpc;

         int nresults;
         int tailcalls;
      };

      struct gc_state : public gc_super
      {
         uint8_t status;

         size_t st_size;  // st_end - st_begin + 1 + extrastack

         st_value * st_begin;
         st_value * st_end;
         st_value * st_base;
         st_value * st_top;

         callinfo * ci_begin;
         callinfo * ci_end;
         callinfo * ci_current;

         st_value env;
         st_value globals;

         gc_union * open_upvalues;

         const instruction * savedpc;

         ::lua::detail::memory * memory;
      };

      class main_state : public gc_state
      {
      public:
         main_state();
         main_state( reallocator realloc, void * userdata );

         ~main_state();

      private:
         void initialise();

         ::lua::detail::memory memory_;

      private:
         main_state( const main_state & );
         void operator= ( const main_state & );
      };

      void correct_stack_impl( gc_state * s, st_value * old );
      st_value * realloc_stack_impl( gc_state * s, size_t nelems );

      void realloc_stack( gc_state * s, size_t nelems )
      {
         correct_stack_impl( s, realloc_stack_impl( s, nelems ) );
      }

      void grow_stack( gc_state * s, size_t nelems )
      {
         if ( nelems <= s->st_size )
            realloc_stack( s, 2 * s->st_size );
         else
            realloc_stack( s, s->st_size + nelems );
      }

      void realloc_callinfo( gc_state * s, size_t nelems )
      {
         const size_t diff = s->ci_current - s->ci_begin;
         s->ci_begin = realloc< callinfo >( s, s->ci_begin, s->ci_end - s->ci_begin, nelems );
         s->ci_current = s->ci_begin + diff;
         s->ci_end = s->ci_begin + nelems - 1;  // Why the -1?
      }

      callinfo * grow_callinfo( gc_state * s )
      {
         const size_t size = s->ci_end - s->ci_begin;

         if ( size > maxcalls )
            throw "callinfo growing in error handler";
      
         realloc_callinfo( s, 2 * size );

         if ( s->ci_end > maxcalls + s->ci_begin )
            throw "callinfo growing too large";

         return ++s->ci_current;
      }

      union gc_union
      {
         gc_super super;
         gc_closure closure;
         gc_prototype prototype;
         gc_string string;
         gc_table table;
         gc_userdata userdata;
         gc_upvalue upvalue;
         gc_state state;
      };

      gc_union * get_next( gc_union * u ) { return u->super.next; }

      uint8_t type( st_value * a ) { return a->type; }
      uint8_t type( gc_super * a ) { return a->type; }

      bool is_nil( gc_super * a ) { return a->type == types::nil; }
      bool is_boolean( gc_super * a ) { return a->type == types::boolean; }
      bool is_lightuserdata( gc_super * a ) { return a->type == types::lightuserdata; }
      bool is_number( gc_super * a ) { return a->type == types::number; }
      bool is_string( gc_super * a ) { return a->type == types::string; }
      bool is_table( gc_super * a ) { return a->type == types::table; }
      bool is_closure( gc_super * a ) { return a->type == types::closure; }
      bool is_userdata( gc_super * a ) { return a->type == types::userdata; }
      bool is_coroutine( gc_super * a ) { return a->type == types::coroutine; }

      bool is_nil( st_value * a ) { return a->type == types::nil; }
      bool is_boolean( st_value * a ) { return a->type == types::boolean; }
      bool is_lightuserdata( st_value * a ) { return a->type == types::lightuserdata; }
      bool is_number( st_value * a ) { return a->type == types::number; }
      bool is_string( st_value * a ) { return a->type == types::string; }
      bool is_table( st_value * a ) { return a->type == types::table; }
      bool is_closure( st_value * a ) { return a->type == types::closure; }
      bool is_userdata( st_value * a ) { return a->type == types::userdata; }
      bool is_coroutine( st_value * a ) { return a->type == types::coroutine; }

      bool is_upvalue( gc_super * a ) { return a->type == types::upvalue; }

      bool is_c_closure( st_value * a ) { return is_closure( a ) && a->gc->closure.s.C; }
      bool is_lua_closure( st_value * a ) { return is_closure( a ) && ! a->gc->closure.s.C; }
      bool is_collectable( st_value * a ) { return type( a ) >= types::string; }

      size_t get_size( gc_string * a ) { return sizeof( gc_string ) + sizeof( char ) * ( a->size + 1 ); }
      size_t get_size( gc_userdata * a ) { return sizeof( gc_userdata ) + a->size; }

      gc_super * to_super( st_value * a ) { return LUA_CHECKED( is_collectable( a ), & a->gc->super ); }
      bool to_boolean( st_value * a ) { return LUA_CHECKED( is_boolean( a ), a->boolean ); }
      void * to_pointer( st_value * a ) { return LUA_CHECKED( is_lightuserdata( a ), a->pointer ); }
      gc_string * to_string( st_value * a ) { return LUA_CHECKED( is_string( a ), & a->gc->string ); }
      gc_table * to_table( st_value * a ) { return LUA_CHECKED( is_table( a ), & a->gc->table ); }
      gc_closure * to_closure( st_value * a ) { return LUA_CHECKED( is_closure( a ), & a->gc->closure ); }

      gc_string * to_string( gc_union * a ) { return LUA_CHECKED( is_string( & a->super ), & a->string ); }
      gc_upvalue * to_upvalue( gc_union * a ) { return LUA_CHECKED( is_upvalue( & a->super ), & a->upvalue ); }

      bool is_false( st_value * a ) { return is_nil( a ) || ( is_boolean( a ) && ! to_boolean( a ) ); }
      bool is_true( st_value * a ) { return ! is_false( a ); }

      void realloc_strings( gc_state * s, const size_t news )
      {
         // TODO sweepstring check

         stringtable * t = & s->memory->strings;
         gc_union ** newh = malloc< gc_union * >( s, news );

         ::memset( newh, 0, news * sizeof( gc_union * ) );

         for ( size_t i = 0; i < t->size; ++t )
         {
            gc_union * p = t->hash[ i ];
            
            while ( p )
            {
               gc_union * n = get_next( p );

               const size_t h0 = to_string( p )->hash;
               const size_t h1 = hash_modulus( h0, news );

               p->super.next = newh[ h1 ];
               newh[ h1 ] = p;

               p = n;
            }
         }
         free< gc_union * >( s, t->hash, t->size );
         t->hash = newh;
         t->size = news;
      }

      void set_userdata( gc_state * s, st_value * t, gc_super * x )
      {
         t->super = x;
         t->type = types::userdata;
         // TODO: checkliveness
      }

      void api_increment_stack( gc_state * s )
      {
         LUA_CHECKED( s->st_top < s->ci_current->st_top, ++s->st_top );
      }

      gc_union * push_next( gc_super * a )
      {
         gc_union * nrv = a->next;
         a->next = reinterpret_cast< gc_union * >( a );
         return nrv;
      }

      gc_userdata * new_userdata_impl( gc_state * s, const size_t size, gc_table * env )
      {
         gc_userdata * nrv = static_cast< gc_userdata * >( malloc( s, sizeof( gc_userdata ) + size ) );

         nrv->type = types::userdata;
         nrv->size = size;
         nrv->env = env;
         nrv->meta = 0;
         nrv->next = push_next( s->memory->main );
         return nrv;
      }

      gc_table * get_current_env( gc_state * s )
      {
         if ( s->ci_current == s->ci_begin )
            return to_table( & s->globals );
         else
            return to_closure( s->ci_current->st_func )->s.env;
      }

      void * new_userdata( gc_state * s, size_t size )
      {
         // TODO checkgc()
         // TODO check alignment

         gc_userdata * nrv = new_userdata_impl( s, size, get_current_env( s ) );
         set_userdata( s, s->st_top, nrv );
         api_increment_stack( s );
      
         return nrv + 1;
      }

      template< class T >
      T * new_userdata( gc_state * s )
      {
         return static_cast< T * >( new_userdata( s, sizeof( T ) ) );
      }

      main_state::main_state()
            : memory_( this, default_realloc, 0 )
      {
         initialise();
      }

      main_state::main_state( reallocator realloc, void * userdata )
            : memory_( this, realloc, userdata )
      {
         initialise();
      }

      main_state::~main_state()
      {
         // TODO heck of a lot of stuff
      }

      void main_state::initialise()
      {
         next = 0;
         type = types::coroutine;
         mark = 0;  // TODO

         status = 0;

         st_size = 0;
         st_begin = st_end = st_base = st_top = 0;

         ci_begin = ci_end = ci_current = 0;

         set_nil( & env );
         set_nil( & globals );

         savedpc = 0;

         memory = & memory_;

         realloc_stack( this, basicstack );
         realloc_callinfo( this, basiccallinfo );

         set_nil( st_top++ );
      }

      void * realloc_wrapper( gc_state * s, void * ptr, const size_t osize, const size_t nsize )
      {
         memory * g = s->memory;

         LUA_ASSERT( bool( osize ) == bool( ptr ) );

         ptr = g->realloc( g->realloc_userdata, ptr, osize, nsize );

         if ( nsize && ! bool( ptr ) )
            throw "out of memory";

         LUA_ASSERT( bool( nsize ) == bool( ptr ) );

         g->realloc_total += nsize - osize;

         return ptr;
      }

      void correct_stack_impl( gc_state * s, st_value * old )
      {
         const size_t diff = s->st_begin - old;

         s->st_top += diff;
         s->st_base += diff;
      
         for ( gc_union * u = s->open_upvalues; u; u = get_next( u ) )
         {
            to_upvalue( u )->v += diff;
         }
         for ( callinfo * i = s->ci_begin; i <= s->ci_current; ++i )
         {
            i->st_top += diff;
            i->st_base += diff;
            i->st_func += diff;
         }
      }

      st_value * realloc_stack_impl( gc_state * s, size_t nelems )
      {
         st_value * old = s->st_begin;

         const size_t realn = nelems + 1 + extrastack;
      
         s->st_begin = realloc< st_value >( s, s->st_begin, s->st_end - s->st_begin, realn );
         s->st_end = s->st_begin + nelems;
         s->st_size = realn;
      
         return old;
      }

   } // detail

} // lua

int main( int, char ** )
{
   return 0;
}