src/script/common/c_packer.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2022 sfan5 <sfan5@live.de>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include <cstdio>
  21 #include <cstring>
  22 #include <cmath>
  23 #include <cassert>
  24 #include <unordered_set>
  25 #include <unordered_map>
  26 #include "c_packer.h"
  27 #include "c_internal.h"
  28 #include "log.h"
  29 #include "debug.h"
  30 #include "threading/mutex_auto_lock.h"
  31
  32 extern "C" {
  33 #include <lauxlib.h>
  34 }
  35
  36 //
  37 // Helpers
  38 //
  39
  40 // convert negative index to absolute position on Lua stack
  41 static inline int absidx(lua_State *L, int idx)
  42 {
  43         assert(idx < 0);
  44         return lua_gettop(L) + idx + 1;
  45 }
  46
  47 // does the type put anything into PackedInstr::sdata?
  48 static inline bool uses_sdata(int type)
  49 {
  50         switch (type) {
  51                 case LUA_TSTRING:
  52                 case LUA_TFUNCTION:
  53                 case LUA_TUSERDATA:
  54                         return true;
  55                 default:
  56                         return false;
  57         }
  58 }
  59
  60 // does the type put anything into PackedInstr::<union>?
  61 static inline bool uses_union(int type)
  62 {
  63         switch (type) {
  64                 case LUA_TNIL:
  65                 case LUA_TSTRING:
  66                 case LUA_TFUNCTION:
  67                         return false;
  68                 default:
  69                         return true;
  70         }
  71 }
  72
  73 static inline bool can_set_into(int ktype, int vtype)
  74 {
  75         switch (ktype) {
  76                 case LUA_TNUMBER:
  77                         return !uses_union(vtype);
  78                 case LUA_TSTRING:
  79                         return !uses_sdata(vtype);
  80                 default:
  81                         return false;
  82         }
  83 }
  84
  85 // is the key suitable for use with set_into?
  86 static inline bool suitable_key(lua_State *L, int idx)
  87 {
  88         if (lua_type(L, idx) == LUA_TSTRING) {
  89                 // strings may not have a NULL byte (-> lua_setfield)
  90                 size_t len;
  91                 const char *str = lua_tolstring(L, idx, &len);
  92                 return strlen(str) == len;
  93         } else {
  94                 assert(lua_type(L, idx) == LUA_TNUMBER);
  95                 // numbers must fit into an s32 and be integers (-> lua_rawseti)
  96                 lua_Number n = lua_tonumber(L, idx);
  97                 return std::floor(n) == n && n >= S32_MIN && n <= S32_MAX;
  98         }
  99 }
 100
 101 namespace {
 102         // checks if you left any values on the stack, for debugging
 103         class StackChecker {
 104                 lua_State *L;
 105                 int top;
 106         public:
 107                 StackChecker(lua_State *L) : L(L), top(lua_gettop(L)) {}
 108                 ~StackChecker() {
 109                         assert(lua_gettop(L) >= top);
 110                         if (lua_gettop(L) > top) {
 111                                 rawstream << "Lua stack not cleaned up: "
 112                                         << lua_gettop(L) << " != " << top
 113                                         << " (false-positive if exception thrown)" << std::endl;
 114                         }
 115                 }
 116         };
 117
 118         // Since an std::vector may reallocate, this is the only safe way to keep
 119         // a reference to a particular element.
 120         template <typename T>
 121         class VectorRef {
 122                 std::vector<T> *vec;
 123                 size_t idx;
 124                 VectorRef(std::vector<T> *vec, size_t idx) : vec(vec), idx(idx) {}
 125         public:
 126                 constexpr VectorRef() : vec(nullptr), idx(0) {}
 127                 static VectorRef<T> front(std::vector<T> &vec) {
 128                         return VectorRef(&vec, 0);
 129                 }
 130                 static VectorRef<T> back(std::vector<T> &vec) {
 131                         return VectorRef(&vec, vec.size() - 1);
 132                 }
 133                 T &operator*() { return (*vec)[idx]; }
 134                 T *operator->() { return &(*vec)[idx]; }
 135                 operator bool() const { return vec != nullptr; }
 136         };
 137
 138         struct Packer {
 139                 PackInFunc fin;
 140                 PackOutFunc fout;
 141         };
 142
 143         typedef std::pair<std::string, Packer> PackerTuple;
 144 }
 145
 146 static inline auto emplace(PackedValue &pv, s16 type)
 147 {
 148         pv.i.emplace_back();
 149         auto ref = VectorRef<PackedInstr>::back(pv.i);
 150         ref->type = type;
 151         // Initialize fields that may be left untouched
 152         if (type == LUA_TTABLE) {
 153                 ref->uidata1 = 0;
 154                 ref->uidata2 = 0;
 155         } else if (type == LUA_TUSERDATA) {
 156                 ref->ptrdata = nullptr;
 157         } else if (type == INSTR_POP) {
 158                 ref->sidata2 = 0;
 159         }
 160         return ref;
 161 }
 162
 163 //
 164 // Management of registered packers
 165 //
 166
 167 static std::unordered_map<std::string, Packer> g_packers;
 168 static std::mutex g_packers_lock;
 169
 170 void script_register_packer(lua_State *L, const char *regname,
 171         PackInFunc fin, PackOutFunc fout)
 172 {
 173         // Store away callbacks
 174         {
 175                 MutexAutoLock autolock(g_packers_lock);
 176                 auto it = g_packers.find(regname);
 177                 if (it == g_packers.end()) {
 178                         auto &ref = g_packers[regname];
 179                         ref.fin = fin;
 180                         ref.fout = fout;
 181                 } else {
 182                         FATAL_ERROR_IF(it->second.fin != fin || it->second.fout != fout,
 183                                 "Packer registered twice with mismatching callbacks");
 184                 }
 185         }
 186
 187         // Save metatable so we can identify instances later
 188         lua_rawgeti(L, LUA_REGISTRYINDEX, CUSTOM_RIDX_METATABLE_MAP);
 189         if (lua_isnil(L, -1)) {
 190                 lua_newtable(L);
 191                 lua_pushvalue(L, -1);
 192                 lua_rawseti(L, LUA_REGISTRYINDEX, CUSTOM_RIDX_METATABLE_MAP);
 193         }
 194
 195         luaL_getmetatable(L, regname);
 196         FATAL_ERROR_IF(lua_isnil(L, -1), "No metatable registered with that name");
 197
 198         // CUSTOM_RIDX_METATABLE_MAP contains { [metatable] = "regname", ... }
 199         // check first
 200         lua_pushstring(L, regname);
 201         lua_rawget(L, -3);
 202         if (!lua_isnil(L, -1)) {
 203                 FATAL_ERROR_IF(lua_topointer(L, -1) != lua_topointer(L, -2),
 204                                 "Packer registered twice with inconsistent metatable");
 205         }
 206         lua_pop(L, 1);
 207         // then set
 208         lua_pushstring(L, regname);
 209         lua_rawset(L, -3);
 210
 211         lua_pop(L, 1);
 212 }
 213
 214 static bool find_packer(const char *regname, PackerTuple &out)
 215 {
 216         MutexAutoLock autolock(g_packers_lock);
 217         auto it = g_packers.find(regname);
 218         if (it == g_packers.end())
 219                 return false;
 220         // copy data for thread safety
 221         out.first = it->first;
 222         out.second = it->second;
 223         return true;
 224 }
 225
 226 static bool find_packer(lua_State *L, int idx, PackerTuple &out)
 227 {
 228 #ifndef NDEBUG
 229         StackChecker checker(L);
 230 #endif
 231
 232         // retrieve metatable of the object
 233         if (lua_getmetatable(L, idx) != 1)
 234                 return false;
 235
 236         // use our global table to map it to the registry name
 237         lua_rawgeti(L, LUA_REGISTRYINDEX, CUSTOM_RIDX_METATABLE_MAP);
 238         assert(lua_istable(L, -1));
 239         lua_pushvalue(L, -2);
 240         lua_rawget(L, -2);
 241         if (lua_isnil(L, -1)) {
 242                 lua_pop(L, 3);
 243                 return false;
 244         }
 245
 246         // load the associated data
 247         bool found = find_packer(lua_tostring(L, -1), out);
 248         FATAL_ERROR_IF(!found, "Inconsistent internal state");
 249         lua_pop(L, 3);
 250         return true;
 251 }
 252
 253 //
 254 // Packing implementation
 255 //
 256
 257 static VectorRef<PackedInstr> record_object(lua_State *L, int idx, PackedValue &pv,
 258                 std::unordered_map<const void *, s32> &seen)
 259 {
 260         const void *ptr = lua_topointer(L, idx);
 261         assert(ptr);
 262         auto found = seen.find(ptr);
 263         if (found == seen.end()) {
 264                 seen[ptr] = pv.i.size();
 265                 return VectorRef<PackedInstr>();
 266         }
 267         s32 ref = found->second;
 268         assert(ref < (s32)pv.i.size());
 269         // reuse the value from first time
 270         auto r = emplace(pv, INSTR_PUSHREF);
 271         r->ref = ref;
 272         pv.i[ref].keep_ref = true;
 273         return r;
 274 }
 275
 276 static VectorRef<PackedInstr> pack_inner(lua_State *L, int idx, int vidx, PackedValue &pv,
 277                 std::unordered_map<const void *, s32> &seen)
 278 {
 279 #ifndef NDEBUG
 280         StackChecker checker(L);
 281         assert(idx > 0);
 282         assert(vidx > 0);
 283 #endif
 284
 285         switch (lua_type(L, idx)) {
 286                 case LUA_TNONE:
 287                 case LUA_TNIL:
 288                         return emplace(pv, LUA_TNIL);
 289                 case LUA_TBOOLEAN: {
 290                         auto r = emplace(pv, LUA_TBOOLEAN);
 291                         r->bdata = lua_toboolean(L, idx);
 292                         return r;
 293                 }
 294                 case LUA_TNUMBER: {
 295                         auto r = emplace(pv, LUA_TNUMBER);
 296                         r->ndata = lua_tonumber(L, idx);
 297                         return r;
 298                 }
 299                 case LUA_TSTRING: {
 300                         auto r = emplace(pv, LUA_TSTRING);
 301                         size_t len;
 302                         const char *str = lua_tolstring(L, idx, &len);
 303                         assert(str);
 304                         r->sdata.assign(str, len);
 305                         return r;
 306                 }
 307                 case LUA_TTABLE: {
 308                         auto r = record_object(L, idx, pv, seen);
 309                         if (r)
 310                                 return r;
 311                         break; // execution continues
 312                 }
 313                 case LUA_TFUNCTION: {
 314                         auto r = record_object(L, idx, pv, seen);
 315                         if (r)
 316                                 return r;
 317                         r = emplace(pv, LUA_TFUNCTION);
 318                         call_string_dump(L, idx);
 319                         size_t len;
 320                         const char *str = lua_tolstring(L, -1, &len);
 321                         assert(str);
 322                         r->sdata.assign(str, len);
 323                         lua_pop(L, 1);
 324                         return r;
 325                 }
 326                 case LUA_TUSERDATA: {
 327                         auto r = record_object(L, idx, pv, seen);
 328                         if (r)
 329                                 return r;
 330                         PackerTuple ser;
 331                         if (!find_packer(L, idx, ser))
 332                                 throw LuaError("Cannot serialize unsupported userdata");
 333                         pv.contains_userdata = true;
 334                         r = emplace(pv, LUA_TUSERDATA);
 335                         r->sdata = ser.first;
 336                         r->ptrdata = ser.second.fin(L, idx);
 337                         return r;
 338                 }
 339                 default: {
 340                         std::string err = "Cannot serialize type ";
 341                         err += lua_typename(L, lua_type(L, idx));
 342                         throw LuaError(err);
 343                 }
 344         }
 345
 346         // LUA_TTABLE
 347         lua_checkstack(L, 5);
 348
 349         auto rtable = emplace(pv, LUA_TTABLE);
 350         const int vi_table = vidx++;
 351
 352         lua_pushnil(L);
 353         while (lua_next(L, idx) != 0) {
 354                 // key at -2, value at -1
 355                 const int ktype = lua_type(L, -2), vtype = lua_type(L, -1);
 356                 if (ktype == LUA_TNUMBER)
 357                         rtable->uidata1++; // narr
 358                 else
 359                         rtable->uidata2++; // nrec
 360
 361                 // check if we can use a shortcut
 362                 if (can_set_into(ktype, vtype) && suitable_key(L, -2)) {
 363                         // push only the value
 364                         auto rval = pack_inner(L, absidx(L, -1), vidx, pv, seen);
 365                         rval->pop = rval->type != LUA_TTABLE;
 366                         // and where to put it:
 367                         rval->set_into = vi_table;
 368                         if (ktype == LUA_TSTRING)
 369                                 rval->sdata = lua_tostring(L, -2);
 370                         else
 371                                 rval->sidata1 = lua_tointeger(L, -2);
 372                         // pop tables after the fact
 373                         if (!rval->pop) {
 374                                 auto ri1 = emplace(pv, INSTR_POP);
 375                                 ri1->sidata1 = vidx;
 376                         }
 377                 } else {
 378                         // push the key and value
 379                         pack_inner(L, absidx(L, -2), vidx, pv, seen);
 380                         vidx++;
 381                         pack_inner(L, absidx(L, -1), vidx, pv, seen);
 382                         vidx++;
 383                         // push an instruction to set them
 384                         auto ri1 = emplace(pv, INSTR_SETTABLE);
 385                         ri1->set_into = vi_table;
 386                         ri1->sidata1 = vidx - 2;
 387                         ri1->sidata2 = vidx - 1;
 388                         ri1->pop = true;
 389                         vidx -= 2;
 390                 }
 391
 392                 lua_pop(L, 1);
 393         }
 394
 395         assert(vidx == vi_table + 1);
 396         return rtable;
 397 }
 398
 399 PackedValue *script_pack(lua_State *L, int idx)
 400 {
 401         if (idx < 0)
 402                 idx = absidx(L, idx);
 403
 404         PackedValue pv;
 405         std::unordered_map<const void *, s32> seen;
 406         pack_inner(L, idx, 1, pv, seen);
 407
 408         return new PackedValue(std::move(pv));
 409 }
 410
 411 //
 412 // Unpacking implementation
 413 //
 414
 415 void script_unpack(lua_State *L, PackedValue *pv)
 416 {
 417         lua_newtable(L); // table at index top to track ref indices -> objects
 418         const int top = lua_gettop(L);
 419         int ctr = 0;
 420
 421         for (size_t packed_idx = 0; packed_idx < pv->i.size(); packed_idx++) {
 422                 auto &i = pv->i[packed_idx];
 423
 424                 // If leaving values on stack make sure there's space (every 5th iteration)
 425                 if (!i.pop && (ctr++) >= 5) {
 426                         lua_checkstack(L, 5);
 427                         ctr = 0;
 428                 }
 429
 430                 switch (i.type) {
 431                         /* Instructions */
 432                         case INSTR_SETTABLE:
 433                                 lua_pushvalue(L, top + i.sidata1); // key
 434                                 lua_pushvalue(L, top + i.sidata2); // value
 435                                 lua_rawset(L, top + i.set_into);
 436                                 if (i.pop) {
 437                                         if (i.sidata1 != i.sidata2) {
 438                                                 // removing moves indices so pop higher index first
 439                                                 lua_remove(L, top + std::max(i.sidata1, i.sidata2));
 440                                                 lua_remove(L, top + std::min(i.sidata1, i.sidata2));
 441                                         } else {
 442                                                 lua_remove(L, top + i.sidata1);
 443                                         }
 444                                 }
 445                                 continue;
 446                         case INSTR_POP:
 447                                 lua_remove(L, top + i.sidata1);
 448                                 if (i.sidata2 > 0)
 449                                         lua_remove(L, top + i.sidata2);
 450                                 continue;
 451                         case INSTR_PUSHREF:
 452                                 lua_pushinteger(L, i.ref);
 453                                 lua_rawget(L, top);
 454                                 break;
 455
 456                         /* Lua types */
 457                         case LUA_TNIL:
 458                                 lua_pushnil(L);
 459                                 break;
 460                         case LUA_TBOOLEAN:
 461                                 lua_pushboolean(L, i.bdata);
 462                                 break;
 463                         case LUA_TNUMBER:
 464                                 lua_pushnumber(L, i.ndata);
 465                                 break;
 466                         case LUA_TSTRING:
 467                                 lua_pushlstring(L, i.sdata.data(), i.sdata.size());
 468                                 break;
 469                         case LUA_TTABLE:
 470                                 lua_createtable(L, i.uidata1, i.uidata2);
 471                                 break;
 472                         case LUA_TFUNCTION:
 473                                 luaL_loadbuffer(L, i.sdata.data(), i.sdata.size(), nullptr);
 474                                 break;
 475                         case LUA_TUSERDATA: {
 476                                 PackerTuple ser;
 477                                 sanity_check(find_packer(i.sdata.c_str(), ser));
 478                                 ser.second.fout(L, i.ptrdata);
 479                                 i.ptrdata = nullptr; // ownership taken by callback
 480                                 break;
 481                         }
 482
 483                         default:
 484                                 assert(0);
 485                                 break;
 486                 }
 487
 488                 if (i.keep_ref) {
 489                         lua_pushinteger(L, packed_idx);
 490                         lua_pushvalue(L, -2);
 491                         lua_rawset(L, top);
 492                 }
 493
 494                 if (i.set_into) {
 495                         if (!i.pop)
 496                                 lua_pushvalue(L, -1);
 497                         if (uses_sdata(i.type))
 498                                 lua_rawseti(L, top + i.set_into, i.sidata1);
 499                         else
 500                                 lua_setfield(L, top + i.set_into, i.sdata.c_str());
 501                 } else {
 502                         if (i.pop)
 503                                 lua_pop(L, 1);
 504                 }
 505         }
 506
 507         // as part of the unpacking process we take ownership of all userdata
 508         pv->contains_userdata = false;
 509         // leave exactly one value on the stack
 510         lua_settop(L, top+1);
 511         lua_remove(L, top);
 512 }
 513
 514 //
 515 // PackedValue
 516 //
 517
 518 PackedValue::~PackedValue()
 519 {
 520         if (!contains_userdata)
 521                 return;
 522         for (auto &i : this->i) {
 523                 if (i.type == LUA_TUSERDATA && i.ptrdata) {
 524                         PackerTuple ser;
 525                         if (find_packer(i.sdata.c_str(), ser)) {
 526                                 // tell it to deallocate object
 527                                 ser.second.fout(nullptr, i.ptrdata);
 528                         } else {
 529                                 assert(false);
 530                         }
 531                 }
 532         }
 533 }
 534
 535 //
 536 // script_dump_packed
 537 //
 538
 539 #ifndef NDEBUG
 540 void script_dump_packed(const PackedValue *val)
 541 {
 542         printf("instruction stream: [\n");
 543         for (const auto &i : val->i) {
 544                 printf("\t(");
 545                 switch (i.type) {
 546                         case INSTR_SETTABLE:
 547                                 printf("SETTABLE(%d, %d)", i.sidata1, i.sidata2);
 548                                 break;
 549                         case INSTR_POP:
 550                                 printf(i.sidata2 ? "POP(%d, %d)" : "POP(%d)", i.sidata1, i.sidata2);
 551                                 break;
 552                         case INSTR_PUSHREF:
 553                                 printf("PUSHREF(%d)", i.ref);
 554                                 break;
 555                         case LUA_TNIL:
 556                                 printf("nil");
 557                                 break;
 558                         case LUA_TBOOLEAN:
 559                                 printf(i.bdata ? "true" : "false");
 560                                 break;
 561                         case LUA_TNUMBER:
 562                                 printf("%f", i.ndata);
 563                                 break;
 564                         case LUA_TSTRING:
 565                                 printf("\"%s\"", i.sdata.c_str());
 566                                 break;
 567                         case LUA_TTABLE:
 568                                 printf("table(%d, %d)", i.uidata1, i.uidata2);
 569                                 break;
 570                         case LUA_TFUNCTION:
 571                                 printf("function(%d byte)", i.sdata.size());
 572                                 break;
 573                         case LUA_TUSERDATA:
 574                                 printf("userdata %s %p", i.sdata.c_str(), i.ptrdata);
 575                                 break;
 576                         default:
 577                                 printf("!!UNKNOWN!!");
 578                                 break;
 579                 }
 580                 if (i.set_into) {
 581                         if (i.type >= 0 && uses_sdata(i.type))
 582                                 printf(", k=%d, into=%d", i.sidata1, i.set_into);
 583                         else if (i.type >= 0)
 584                                 printf(", k=\"%s\", into=%d", i.sdata.c_str(), i.set_into);
 585                         else
 586                                 printf(", into=%d", i.set_into);
 587                 }
 588                 if (i.keep_ref)
 589                         printf(", keep_ref");
 590                 if (i.pop)
 591                         printf(", pop");
 592                 printf(")\n");
 593         }
 594         printf("]\n");
 595 }
 596 #endif