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                 static VectorRef<T> front(std::vector<T> &vec) {
 127                         return VectorRef(&vec, 0);
 128                 }
 129                 static VectorRef<T> back(std::vector<T> &vec) {
 130                         return VectorRef(&vec, vec.size() - 1);
 131                 }
 132                 T &operator*() { return (*vec)[idx]; }
 133                 T *operator->() { return &(*vec)[idx]; }
 134         };
 135
 136         struct Packer {
 137                 PackInFunc fin;
 138                 PackOutFunc fout;
 139         };
 140
 141         typedef std::pair<std::string, Packer> PackerTuple;
 142 }
 143
 144 static inline auto emplace(PackedValue &pv, s16 type)
 145 {
 146         pv.i.emplace_back();
 147         auto ref = VectorRef<PackedInstr>::back(pv.i);
 148         ref->type = type;
 149         // Initialize fields that may be left untouched
 150         if (type == LUA_TTABLE) {
 151                 ref->uidata1 = 0;
 152                 ref->uidata2 = 0;
 153         } else if (type == LUA_TUSERDATA) {
 154                 ref->ptrdata = nullptr;
 155         } else if (type == INSTR_POP) {
 156                 ref->sidata2 = 0;
 157         }
 158         return ref;
 159 }
 160
 161 //
 162 // Management of registered packers
 163 //
 164
 165 static std::unordered_map<std::string, Packer> g_packers;
 166 static std::mutex g_packers_lock;
 167
 168 void script_register_packer(lua_State *L, const char *regname,
 169         PackInFunc fin, PackOutFunc fout)
 170 {
 171         // Store away callbacks
 172         {
 173                 MutexAutoLock autolock(g_packers_lock);
 174                 auto it = g_packers.find(regname);
 175                 if (it == g_packers.end()) {
 176                         auto &ref = g_packers[regname];
 177                         ref.fin = fin;
 178                         ref.fout = fout;
 179                 } else {
 180                         FATAL_ERROR_IF(it->second.fin != fin || it->second.fout != fout,
 181                                 "Packer registered twice with mismatching callbacks");
 182                 }
 183         }
 184
 185         // Save metatable so we can identify instances later
 186         lua_rawgeti(L, LUA_REGISTRYINDEX, CUSTOM_RIDX_METATABLE_MAP);
 187         if (lua_isnil(L, -1)) {
 188                 lua_newtable(L);
 189                 lua_pushvalue(L, -1);
 190                 lua_rawseti(L, LUA_REGISTRYINDEX, CUSTOM_RIDX_METATABLE_MAP);
 191         }
 192
 193         luaL_getmetatable(L, regname);
 194         FATAL_ERROR_IF(lua_isnil(L, -1), "No metatable registered with that name");
 195
 196         // CUSTOM_RIDX_METATABLE_MAP contains { [metatable] = "regname", ... }
 197         // check first
 198         lua_pushstring(L, regname);
 199         lua_rawget(L, -3);
 200         if (!lua_isnil(L, -1)) {
 201                 FATAL_ERROR_IF(lua_topointer(L, -1) != lua_topointer(L, -2),
 202                                 "Packer registered twice with inconsistent metatable");
 203         }
 204         lua_pop(L, 1);
 205         // then set
 206         lua_pushstring(L, regname);
 207         lua_rawset(L, -3);
 208
 209         lua_pop(L, 1);
 210 }
 211
 212 static bool find_packer(const char *regname, PackerTuple &out)
 213 {
 214         MutexAutoLock autolock(g_packers_lock);
 215         auto it = g_packers.find(regname);
 216         if (it == g_packers.end())
 217                 return false;
 218         // copy data for thread safety
 219         out.first = it->first;
 220         out.second = it->second;
 221         return true;
 222 }
 223
 224 static bool find_packer(lua_State *L, int idx, PackerTuple &out)
 225 {
 226 #ifndef NDEBUG
 227         StackChecker checker(L);
 228 #endif
 229
 230         // retrieve metatable of the object
 231         if (lua_getmetatable(L, idx) != 1)
 232                 return false;
 233
 234         // use our global table to map it to the registry name
 235         lua_rawgeti(L, LUA_REGISTRYINDEX, CUSTOM_RIDX_METATABLE_MAP);
 236         assert(lua_istable(L, -1));
 237         lua_pushvalue(L, -2);
 238         lua_rawget(L, -2);
 239         if (lua_isnil(L, -1)) {
 240                 lua_pop(L, 3);
 241                 return false;
 242         }
 243
 244         // load the associated data
 245         bool found = find_packer(lua_tostring(L, -1), out);
 246         FATAL_ERROR_IF(!found, "Inconsistent internal state");
 247         lua_pop(L, 3);
 248         return true;
 249 }
 250
 251 //
 252 // Packing implementation
 253 //
 254
 255 // recursively goes through the structure and ensures there are no circular references
 256 static void pack_validate(lua_State *L, int idx, std::unordered_set<const void*> &seen)
 257 {
 258 #ifndef NDEBUG
 259         StackChecker checker(L);
 260         assert(idx > 0);
 261 #endif
 262
 263         if (lua_type(L, idx) != LUA_TTABLE)
 264                 return;
 265
 266         const void *ptr = lua_topointer(L, idx);
 267         assert(ptr);
 268
 269         if (seen.find(ptr) != seen.end())
 270                 throw LuaError("Circular references cannot be packed (yet)");
 271         seen.insert(ptr);
 272
 273         lua_checkstack(L, 5);
 274         lua_pushnil(L);
 275         while (lua_next(L, idx) != 0) {
 276                 // key at -2, value at -1
 277                 pack_validate(L, absidx(L, -2), seen);
 278                 pack_validate(L, absidx(L, -1), seen);
 279
 280                 lua_pop(L, 1);
 281         }
 282
 283         seen.erase(ptr);
 284 }
 285
 286 static VectorRef<PackedInstr> pack_inner(lua_State *L, int idx, int vidx, PackedValue &pv)
 287 {
 288 #ifndef NDEBUG
 289         StackChecker checker(L);
 290         assert(idx > 0);
 291         assert(vidx > 0);
 292 #endif
 293
 294         switch (lua_type(L, idx)) {
 295                 case LUA_TNONE:
 296                 case LUA_TNIL:
 297                         return emplace(pv, LUA_TNIL);
 298                 case LUA_TBOOLEAN: {
 299                         auto r = emplace(pv, LUA_TBOOLEAN);
 300                         r->bdata = lua_toboolean(L, idx);
 301                         return r;
 302                 }
 303                 case LUA_TNUMBER: {
 304                         auto r = emplace(pv, LUA_TNUMBER);
 305                         r->ndata = lua_tonumber(L, idx);
 306                         return r;
 307                 }
 308                 case LUA_TSTRING: {
 309                         auto r = emplace(pv, LUA_TSTRING);
 310                         size_t len;
 311                         const char *str = lua_tolstring(L, idx, &len);
 312                         assert(str);
 313                         r->sdata.assign(str, len);
 314                         return r;
 315                 }
 316                 case LUA_TTABLE:
 317                         break; // execution continues
 318                 case LUA_TFUNCTION: {
 319                         auto r = emplace(pv, LUA_TFUNCTION);
 320                         call_string_dump(L, idx);
 321                         size_t len;
 322                         const char *str = lua_tolstring(L, -1, &len);
 323                         assert(str);
 324                         r->sdata.assign(str, len);
 325                         lua_pop(L, 1);
 326                         return r;
 327                 }
 328                 case LUA_TUSERDATA: {
 329                         PackerTuple ser;
 330                         if (!find_packer(L, idx, ser))
 331                                 throw LuaError("Cannot serialize unsupported userdata");
 332                         pv.contains_userdata = true;
 333                         auto r = emplace(pv, LUA_TUSERDATA);
 334                         r->sdata = ser.first;
 335                         r->ptrdata = ser.second.fin(L, idx);
 336                         return r;
 337                 }
 338                 default: {
 339                         std::string err = "Cannot serialize type ";
 340                         err += lua_typename(L, lua_type(L, idx));
 341                         throw LuaError(err);
 342                 }
 343         }
 344
 345         // LUA_TTABLE
 346         lua_checkstack(L, 5);
 347
 348         auto rtable = emplace(pv, LUA_TTABLE);
 349         const int vi_table = vidx++;
 350
 351         lua_pushnil(L);
 352         while (lua_next(L, idx) != 0) {
 353                 // key at -2, value at -1
 354                 const int ktype = lua_type(L, -2), vtype = lua_type(L, -1);
 355                 if (ktype == LUA_TNUMBER)
 356                         rtable->uidata1++; // narr
 357                 else
 358                         rtable->uidata2++; // nrec
 359
 360                 // check if we can use a shortcut
 361                 if (can_set_into(ktype, vtype) && suitable_key(L, -2)) {
 362                         // push only the value
 363                         auto rval = pack_inner(L, absidx(L, -1), vidx, pv);
 364                         rval->pop = vtype != LUA_TTABLE;
 365                         // and where to put it:
 366                         rval->set_into = vi_table;
 367                         if (ktype == LUA_TSTRING)
 368                                 rval->sdata = lua_tostring(L, -2);
 369                         else
 370                                 rval->sidata1 = lua_tointeger(L, -2);
 371                         // pop tables after the fact
 372                         if (!rval->pop) {
 373                                 auto ri1 = emplace(pv, INSTR_POP);
 374                                 ri1->sidata1 = vidx;
 375                         }
 376                 } else {
 377                         // push the key and value
 378                         pack_inner(L, absidx(L, -2), vidx, pv);
 379                         vidx++;
 380                         pack_inner(L, absidx(L, -1), vidx, pv);
 381                         vidx++;
 382                         // push an instruction to set them
 383                         auto ri1 = emplace(pv, INSTR_SETTABLE);
 384                         ri1->set_into = vi_table;
 385                         ri1->sidata1 = vidx - 2;
 386                         ri1->sidata2 = vidx - 1;
 387                         ri1->pop = true;
 388                         vidx -= 2;
 389                 }
 390
 391                 lua_pop(L, 1);
 392         }
 393
 394         assert(vidx == vi_table + 1);
 395         return rtable;
 396 }
 397
 398 PackedValue *script_pack(lua_State *L, int idx)
 399 {
 400         if (idx < 0)
 401                 idx = absidx(L, idx);
 402
 403         std::unordered_set<const void*> seen;
 404         pack_validate(L, idx, seen);
 405         assert(seen.size() == 0);
 406
 407         // Actual serialization
 408         PackedValue pv;
 409         pack_inner(L, idx, 1, pv);
 410
 411         return new PackedValue(std::move(pv));
 412 }
 413
 414 //
 415 // Unpacking implementation
 416 //
 417
 418 void script_unpack(lua_State *L, PackedValue *pv)
 419 {
 420         const int top = lua_gettop(L);
 421         int ctr = 0;
 422
 423         for (auto &i : pv->i) {
 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                 /* Instructions */
 431                 switch (i.type) {
 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                         default:
 452                                 break;
 453                 }
 454
 455                 /* Lua types */
 456                 switch (i.type) {
 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                         default:
 483                                 assert(0);
 484                                 break;
 485                 }
 486
 487                 if (i.set_into) {
 488                         if (!i.pop)
 489                                 lua_pushvalue(L, -1);
 490                         if (uses_sdata(i.type))
 491                                 lua_rawseti(L, top + i.set_into, i.sidata1);
 492                         else
 493                                 lua_setfield(L, top + i.set_into, i.sdata.c_str());
 494                 } else {
 495                         if (i.pop)
 496                                 lua_pop(L, 1);
 497                 }
 498         }
 499
 500         // as part of the unpacking process we take ownership of all userdata
 501         pv->contains_userdata = false;
 502         // leave exactly one value on the stack
 503         lua_settop(L, top+1);
 504 }
 505
 506 //
 507 // PackedValue
 508 //
 509
 510 PackedValue::~PackedValue()
 511 {
 512         if (!contains_userdata)
 513                 return;
 514         for (auto &i : this->i) {
 515                 if (i.type == LUA_TUSERDATA && i.ptrdata) {
 516                         PackerTuple ser;
 517                         if (find_packer(i.sdata.c_str(), ser)) {
 518                                 // tell it to deallocate object
 519                                 ser.second.fout(nullptr, i.ptrdata);
 520                         } else {
 521                                 assert(false);
 522                         }
 523                 }
 524         }
 525 }
 526
 527 //
 528 // script_dump_packed
 529 //
 530
 531 #ifndef NDEBUG
 532 void script_dump_packed(const PackedValue *val)
 533 {
 534         printf("instruction stream: [\n");
 535         for (const auto &i : val->i) {
 536                 printf("\t(");
 537                 switch (i.type) {
 538                         case INSTR_SETTABLE:
 539                                 printf("SETTABLE(%d, %d)", i.sidata1, i.sidata2);
 540                                 break;
 541                         case INSTR_POP:
 542                                 printf(i.sidata2 ? "POP(%d, %d)" : "POP(%d)", i.sidata1, i.sidata2);
 543                                 break;
 544                         case LUA_TNIL:
 545                                 printf("nil");
 546                                 break;
 547                         case LUA_TBOOLEAN:
 548                                 printf(i.bdata ? "true" : "false");
 549                                 break;
 550                         case LUA_TNUMBER:
 551                                 printf("%f", i.ndata);
 552                                 break;
 553                         case LUA_TSTRING:
 554                                 printf("\"%s\"", i.sdata.c_str());
 555                                 break;
 556                         case LUA_TTABLE:
 557                                 printf("table(%d, %d)", i.uidata1, i.uidata2);
 558                                 break;
 559                         case LUA_TFUNCTION:
 560                                 printf("function(%d byte)", i.sdata.size());
 561                                 break;
 562                         case LUA_TUSERDATA:
 563                                 printf("userdata %s %p", i.sdata.c_str(), i.ptrdata);
 564                                 break;
 565                         default:
 566                                 printf("!!UNKNOWN!!");
 567                                 break;
 568                 }
 569                 if (i.set_into) {
 570                         if (i.type >= 0 && uses_sdata(i.type))
 571                                 printf(", k=%d, into=%d", i.sidata1, i.set_into);
 572                         else if (i.type >= 0)
 573                                 printf(", k=\"%s\", into=%d", i.sdata.c_str(), i.set_into);
 574                         else
 575                                 printf(", into=%d", i.set_into);
 576                 }
 577                 if (i.pop)
 578                         printf(", pop");
 579                 printf(")\n");
 580         }
 581         printf("]\n");
 582 }
 583 #endif