From aaef96a2faeb761b2a8b893158899f48c39cbf4b Mon Sep 17 00:00:00 2001 From: Benoit Germain Date: Fri, 7 Mar 2025 17:44:59 +0100 Subject: Revamped lanes.nameof --- src/nameof.cpp | 310 +++++++++++++++++++++++++++++++++++++-------------------- src/tools.cpp | 9 +- src/tools.hpp | 2 +- 3 files changed, 206 insertions(+), 115 deletions(-) (limited to 'src') diff --git a/src/nameof.cpp b/src/nameof.cpp index b3874f3..1f338a5 100644 --- a/src/nameof.cpp +++ b/src/nameof.cpp @@ -31,137 +31,225 @@ THE SOFTWARE. // ################################################################################################# +DECLARE_UNIQUE_TYPE(FqnLength, lua_Unsigned); + // Return some name helping to identify an object [[nodiscard]] -static int DiscoverObjectNameRecur(lua_State* const L_, int shortest_, TableIndex const curDepth_) +FqnLength DiscoverObjectNameRecur(lua_State* const L_, FqnLength const shortest_) { - static constexpr StackIndex kWhat{ 1 }; // the object to investigate // L_: o "r" {c} {fqn} ... {?} + static constexpr StackIndex kWhat{ 1 }; // the object to investigate // L_: o "r" {c} {fqn} ... <> static constexpr StackIndex kResult{ 2 }; // where the result string is stored - static constexpr StackIndex kCache{ 3 }; // a cache + static constexpr StackIndex kCache{ 3 }; // a cache, where visited locations remember the FqnLength to reach them static constexpr StackIndex kFQN{ 4 }; // the name compositing stack - // no need to scan this table if the name we will discover is longer than one we already know - TableIndex const _nextDepth{ curDepth_ + 1 }; - if (shortest_ <= _nextDepth) { + + // no need to scan this location if the name we will discover is longer than one we already know + FqnLength const _fqnLength{ lua_rawlen(L_, kFQN) }; + if (shortest_ <= _fqnLength) { return shortest_; } - auto _pushNameOnFQN = [L_](std::string_view const& name_, TableIndex const depth_) { - luaG_pushstring(L_, name_); // L_: o "r" {c} {fqn} ... name_ - lua_rawseti(L_, kFQN, depth_); // L_: o "r" {c} {fqn} ... {mt} + // in: k, v at the top of the stack + static constexpr auto _pushNameOnFQN = [](lua_State* const L_) { + STACK_CHECK_START_REL(L_, 0); + lua_pushvalue(L_, -2); // L_: o "r" {c} {fqn} ... k v k + auto const _keyType{ luaG_type(L_, kIdxTop) }; + if (_keyType != LuaType::STRING) { + lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... k v + luaG_pushstring(L_, "<%s>", luaG_typename(L_, _keyType).data()); // L_: o "r" {c} {fqn} ... k v "" + } else { + // decorate the key string with something that tells us the type of the value + switch (luaG_type(L_, StackIndex{ -2 })) { + default: + luaG_pushstring(L_, "??"); // L_: o "r" {c} {fqn} ... k v "k" "??" + break; + case LuaType::FUNCTION: + luaG_pushstring(L_, "()"); // L_: o "r" {c} {fqn} ... k v "k" "()" + break; + case LuaType::TABLE: + luaG_pushstring(L_, "[]"); // L_: o "r" {c} {fqn} ... k v "k" "[]" + break; + case LuaType::USERDATA: + luaG_pushstring(L_, "<>"); // L_: o "r" {c} {fqn} ... k v "k" "<>" + break; + } + lua_concat(L_, 2); // L_: o "r" {c} {fqn} ... k v "k??" + } + + FqnLength const _depth{ lua_rawlen(L_, kFQN) + 1 }; + lua_rawseti(L_, kFQN, _depth); // L_: o "r" {c} {fqn} ... k v + STACK_CHECK(L_, 0); + STACK_CHECK(L_, 0); + return _depth; }; - auto _popNameFromFQN = [L_](TableIndex const depth_) { + static constexpr auto _popNameFromFQN = [](lua_State* const L_) { + STACK_CHECK_START_REL(L_, 0); lua_pushnil(L_); // L_: o "r" {c} {fqn} ... nil - lua_rawseti(L_, kFQN, depth_); // L_: o "r" {c} {fqn} ... + lua_rawseti(L_, kFQN, lua_rawlen(L_, kFQN)); // L_: o "r" {c} {fqn} ... + STACK_CHECK(L_, 0); }; - auto _recurseIfTableThenPop = [&_pushNameOnFQN, &_popNameFromFQN, L_](std::string_view const& name_, TableIndex const depth_, int shortest_) { - STACK_CHECK_START_REL(L_, 0); // L_: o "r" {c} {fqn} ... <> {}? - if (lua_istable(L_, kIdxTop)) { - _pushNameOnFQN(name_, depth_); - shortest_ = DiscoverObjectNameRecur(L_, shortest_, TableIndex{ depth_ + 1 }); - _popNameFromFQN(depth_); + static constexpr auto _recurseThenPop = [](lua_State* const L_, FqnLength const shortest_) -> FqnLength { + STACK_CHECK_START_REL(L_, 0); // L_: o "r" {c} {fqn} ... <> + FqnLength r_{ shortest_ }; + auto const _type{ luaG_type(L_, kIdxTop) }; + if (_type == LuaType::TABLE || _type == LuaType::USERDATA || _type == LuaType::FUNCTION) { + r_ = DiscoverObjectNameRecur(L_, shortest_); + STACK_CHECK(L_, 0); + _popNameFromFQN(L_); + STACK_CHECK(L_, 0); } - lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... <> + + lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... STACK_CHECK(L_, -1); - return shortest_; + return r_; }; - STACK_GROW(L_, 3); - STACK_CHECK_START_REL(L_, 0); - // stack top contains the table to search in - LUA_ASSERT(L_, lua_istable(L_, kIdxTop)); - lua_pushvalue(L_, kIdxTop); // L_: o "r" {c} {fqn} ... {?} {?} - lua_rawget(L_, kCache); // L_: o "r" {c} {fqn} ... {?} nil/1 - // if table is already visited, we are done - if (!lua_isnil(L_, kIdxTop)) { - lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... {?} - return shortest_; - } - // examined table is not in the cache, add it now - lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... {?} - // cache[o] = 1 - lua_pushvalue(L_, kIdxTop); // L_: o "r" {c} {fqn} ... {?} {?} - lua_pushinteger(L_, 1); // L_: o "r" {c} {fqn} ... {?} {?} 1 - lua_rawset(L_, kCache); // L_: o "r" {c} {fqn} ... {?} - // scan table contents - lua_pushnil(L_); // L_: o "r" {c} {fqn} ... {?} nil - while (lua_next(L_, -2)) { // L_: o "r" {c} {fqn} ... {?} k v - // std::string_view const _strKey{ (luaG_type(L_, -2) == LuaType::STRING) ? luaG_tostring(L_, -2) : "" }; // only for debugging - // lua_Number const numKey = (luaG_type(L_, -2) == LuaType::NUMBER) ? lua_tonumber(L_, -2) : -6666; // only for debugging - STACK_CHECK(L_, 2); + // in: k, v at the top of the stack + // out: v popped from the stack + static constexpr auto _processKeyValue = [](lua_State* const L_, FqnLength const shortest_) -> FqnLength { + FqnLength _r{ shortest_ }; + STACK_GROW(L_, 2); + STACK_CHECK_START_REL(L_, 0); // L_: o "r" {c} {fqn} ... k v + + // filter out uninteresting values + auto const _valType{ luaG_type(L_, kIdxTop) }; + if (_valType == LuaType::BOOLEAN || _valType == LuaType::LIGHTUSERDATA || _valType == LuaType::NUMBER || _valType == LuaType::STRING) { + lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... k + return _r; + } + // append key name to fqn stack - lua_pushvalue(L_, -2); // L_: o "r" {c} {fqn} ... {?} k v k - lua_rawseti(L_, kFQN, _nextDepth); // L_: o "r" {c} {fqn} ... {?} k v + FqnLength const _depth{ _pushNameOnFQN(L_) }; // L_: o "r" {c} {fqn} ... k v + + // process the value if (lua_rawequal(L_, kIdxTop, kWhat)) { // is it what we are looking for? - STACK_CHECK(L_, 2); // update shortest name - if (_nextDepth < shortest_) { - shortest_ = _nextDepth; - std::ignore = tools::PushFQN(L_, kFQN, _nextDepth); // L_: o "r" {c} {fqn} ... {?} k v "fqn" - lua_replace(L_, kResult); // L_: o "r" {c} {fqn} ... {?} k v + if (_depth < _r) { + _r = _depth; + std::ignore = tools::PushFQN(L_, kFQN); // L_: o "r" {c} {fqn} ... k v "fqn" + lua_replace(L_, kResult); // L_: o "r" {c} {fqn} ... k v } - // no need to search further at this level - lua_pop(L_, 2); // L_: o "r" {c} {fqn} ... {?} - STACK_CHECK(L_, 0); - break; + + lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... k + _popNameFromFQN(L_); + } else { + // let's see if the value contains what we are looking for + _r = _recurseThenPop(L_, _r); // L_: o "r" {c} {fqn} ... k } - switch (luaG_type(L_, kIdxTop)) { // L_: o "r" {c} {fqn} ... {?} k v - default: // nil, boolean, light userdata, number and string aren't identifiable - break; - - case LuaType::TABLE: // L_: o "r" {c} {fqn} ... {?} k {} - STACK_CHECK(L_, 2); - shortest_ = DiscoverObjectNameRecur(L_, shortest_, _nextDepth); - // search in the table's metatable too - if (lua_getmetatable(L_, -1)) { // L_: o "r" {c} {fqn} ... {?} k {} {mt} - shortest_ = _recurseIfTableThenPop("__metatable", _nextDepth, shortest_); // L_: o "r" {c} {fqn} ... {?} k {} - } - STACK_CHECK(L_, 2); - break; - - case LuaType::THREAD: // L_: o "r" {c} {fqn} ... {?} k T - // TODO: explore the thread's stack frame looking for our culprit? - break; - - case LuaType::USERDATA: // L_: o "r" {c} {fqn} ... {?} k U - STACK_CHECK(L_, 2); - // search in the object's metatable (some modules are built that way) - if (lua_getmetatable(L_, -1)) { // L_: o "r" {c} {fqn} ... {?} k U {mt} - shortest_ = _recurseIfTableThenPop("__metatable", _nextDepth, shortest_); // L_: o "r" {c} {fqn} ... {?} k U - } - STACK_CHECK(L_, 2); - // search in the object's uservalues - { - UserValueIndex _uvi{ 1 }; - while (lua_getiuservalue(L_, kIdxTop, _uvi) != LUA_TNONE) { // L_: o "r" {c} {fqn} ... {?} k U {u} - shortest_ = _recurseIfTableThenPop("uservalue", _nextDepth, shortest_); // L_: o "r" {c} {fqn} ... {?} k U - ++_uvi; - } - // when lua_getiuservalue() returned LUA_TNONE, it pushed a nil. pop it now - lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... {?} k U + STACK_CHECK(L_, -1); + return _r; + }; + + static constexpr auto _scanTable = [](lua_State* const L_, FqnLength const shortest_) -> FqnLength { + FqnLength r_{ shortest_ }; + STACK_GROW(L_, 2); + STACK_CHECK_START_REL(L_, 0); + lua_pushnil(L_); // L_: o "r" {c} {fqn} ... {?} nil + while (lua_next(L_, -2)) { // L_: o "r" {c} {fqn} ... {?} k v + r_ = _processKeyValue(L_, r_); // L_: o "r" {c} {fqn} ... {?} k + } // L_: o "r" {c} {fqn} ... {?} + + if (lua_getmetatable(L_, kIdxTop)) { // L_: o "r" {c} {fqn} ... {?} {mt} + lua_pushstring(L_, "__metatable"); // L_: o "r" {c} {fqn} ... {?} {mt} "__metatable" + lua_insert(L_, -2); // L_: o "r" {c} {fqn} ... {?} "__metatable" {mt} + r_ = _processKeyValue(L_, r_); // L_: o "r" {c} {fqn} ... {?} "__metatable" + lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... {?} + } + + STACK_CHECK(L_, 0); + return r_; + }; + + static constexpr auto _scanUserData = [](lua_State* const L_, FqnLength const shortest_) -> FqnLength { + FqnLength r_{ shortest_ }; + FqnLength const _depth{ lua_rawlen(L_, kFQN) + 1 }; + STACK_GROW(L_, 2); + STACK_CHECK_START_REL(L_, 0); + if (lua_getmetatable(L_, kIdxTop)) { // L_: o "r" {c} {fqn} ... U {mt} + lua_pushstring(L_, "__metatable"); // L_: o "r" {c} {fqn} ... U {mt} "__metatable" + lua_insert(L_, -2); // L_: o "r" {c} {fqn} ... U "__metatable" {mt} + r_ = _processKeyValue(L_, r_); // L_: o "r" {c} {fqn} ... U "__metatable" + lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... U + } + + STACK_CHECK(L_, 0); + + UserValueIndex _uvi{ 0 }; + while (lua_getiuservalue(L_, kIdxTop, ++_uvi) != LUA_TNONE) { // L_: o "r" {c} {fqn} ... U uv + luaG_pushstring(L_, "", _uvi); // L_: o "r" {c} {fqn} ... U uv name + lua_insert(L_, -2); // L_: o "r" {c} {fqn} ... U name uv + r_ = _processKeyValue(L_, r_); // L_: o "r" {c} {fqn} ... U name + lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... U + } + + // when lua_getiuservalue() returned LUA_TNONE, it pushed a nil. pop it now + lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... U + + STACK_CHECK(L_, 0); + return r_; + }; + + static constexpr auto _scanFunction = [](lua_State* const L_, FqnLength const shortest_) -> FqnLength { + FqnLength r_{ shortest_ }; + STACK_GROW(L_, 2); + STACK_CHECK_START_REL(L_, 0); // L_: o "r" {c} {fqn} ... F + int _n{ 0 }; + for (char const* _upname{}; (_upname = lua_getupvalue(L_, kIdxTop, ++_n));) { // L_: o "r" {c} {fqn} ... F up + if (*_upname == 0) { + _upname = ""; } - STACK_CHECK(L_, 2); - break; - case LuaType::FUNCTION: // L_: o "r" {c} {fqn} ... {?} k F - // TODO: explore the function upvalues - break; + luaG_pushstring(L_, "upvalue:%s", _upname); // L_: o "r" {c} {fqn} ... F up name + lua_insert(L_, -2); // L_: o "r" {c} {fqn} ... F name up + r_ = _processKeyValue(L_, r_); // L_: o "r" {c} {fqn} ... F name + lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... F } - // make ready for next iteration - lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... {?} k - // remove name from fqn stack - _popNameFromFQN(_nextDepth); - STACK_CHECK(L_, 1); - } // L_: o "r" {c} {fqn} ... {?} - STACK_CHECK(L_, 0); - // remove the visited table from the cache, in case a shorter path to the searched object exists - lua_pushvalue(L_, kIdxTop); // L_: o "r" {c} {fqn} ... {?} {?} - lua_pushnil(L_); // L_: o "r" {c} {fqn} ... {?} {?} nil - lua_rawset(L_, kCache); // L_: o "r" {c} {fqn} ... {?} + + STACK_CHECK(L_, 0); + return r_; + }; + + STACK_GROW(L_, 2); + STACK_CHECK_START_REL(L_, 0); + // stack top contains the location to search in (table, function, userdata) + [[maybe_unused]] auto const _typeWhere{ luaG_type(L_, kIdxTop) }; + LUA_ASSERT(L_, _typeWhere == LuaType::TABLE || _typeWhere == LuaType::USERDATA || _typeWhere == LuaType::FUNCTION); + lua_pushvalue(L_, kIdxTop); // L_: o "r" {c} {fqn} ... <> <> + lua_rawget(L_, kCache); // L_: o "r" {c} {fqn} ... <> nil/N + auto const _visitDepth{ lua_isnil(L_, kIdxTop) ? std::numeric_limits::max() : lua_tointeger(L_, kIdxTop) }; + lua_pop(L_, 1); // L_: o "r" {c} {fqn} ... <> + // if location is already visited with a name of <= length, we are done + if (_visitDepth <= _fqnLength) { + return shortest_; + } + + // examined location is not in the cache, add it now + // cache[o] = _fqnLength + lua_pushvalue(L_, kIdxTop); // L_: o "r" {c} {fqn} ... <> <> + lua_pushinteger(L_, _fqnLength); // L_: o "r" {c} {fqn} ... <> <> N + lua_rawset(L_, kCache); // L_: o "r" {c} {fqn} ... <> + + FqnLength r_; + // scan location contents + switch (luaG_type(L_, kIdxTop)) { // L_: o "r" {c} {fqn} ... <> + default: + raise_luaL_error(L_, "unexpected error, please investigate"); + break; + case LuaType::TABLE: + r_ = _scanTable(L_, shortest_); + break; + case LuaType::USERDATA: + r_ = _scanUserData(L_, shortest_); + break; + case LuaType::FUNCTION: + r_ = _scanFunction(L_, shortest_); + break; + } + STACK_CHECK(L_, 0); - return shortest_; + return r_; } // ################################################################################################# @@ -170,16 +258,17 @@ static int DiscoverObjectNameRecur(lua_State* const L_, int shortest_, TableInde LUAG_FUNC(nameof) { auto const _argCount{ lua_gettop(L_) }; - if (_argCount > 1) { - raise_luaL_argerror(L_, StackIndex{ _argCount }, "too many arguments."); + if (_argCount != 1) { + raise_luaL_argerror(L_, StackIndex{ _argCount }, "exactly 1 argument expected"); } // nil, boolean, light userdata, number and string aren't identifiable - auto const _isIdentifiable = [L_]() { + static constexpr auto _isIdentifiable = [](lua_State* const L_) { auto const _valType{ luaG_type(L_, kIdxTop) }; return _valType == LuaType::TABLE || _valType == LuaType::FUNCTION || _valType == LuaType::USERDATA || _valType == LuaType::THREAD; }; - if (!_isIdentifiable()) { + + if (!_isIdentifiable(L_)) { luaG_pushstring(L_, luaG_typename(L_, kIdxTop)); // L_: o "type" lua_insert(L_, -2); // L_: "type" o return 2; @@ -198,13 +287,14 @@ LUAG_FUNC(nameof) lua_rawseti(L_, -2, 1); // L_: o nil {c} {fqn} // this is where we start the search luaG_pushglobaltable(L_); // L_: o nil {c} {fqn} _G - std::ignore = DiscoverObjectNameRecur(L_, std::numeric_limits::max(), TableIndex{ 1 }); + auto const _foundInG{ DiscoverObjectNameRecur(L_, FqnLength{ std::numeric_limits::max() }) }; if (lua_isnil(L_, 2)) { // try again with registry, just in case... + LUA_ASSERT(L_, _foundInG == std::numeric_limits::max()); lua_pop(L_, 1); // L_: o nil {c} {fqn} luaG_pushstring(L_, "_R"); // L_: o nil {c} {fqn} "_R" lua_rawseti(L_, -2, 1); // L_: o nil {c} {fqn} lua_pushvalue(L_, kIdxRegistry); // L_: o nil {c} {fqn} _R - std::ignore = DiscoverObjectNameRecur(L_, std::numeric_limits::max(), TableIndex{ 1 }); + [[maybe_unused]] auto const _foundInR{ DiscoverObjectNameRecur(L_, FqnLength{ std::numeric_limits::max() }) }; } lua_pop(L_, 3); // L_: o "result" STACK_CHECK(L_, 1); diff --git a/src/tools.cpp b/src/tools.cpp index ee6d720..cbfefb0 100644 --- a/src/tools.cpp +++ b/src/tools.cpp @@ -95,19 +95,20 @@ namespace tools { // inspired from tconcat() in ltablib.c [[nodiscard]] - std::string_view PushFQN(lua_State* const L_, StackIndex const t_, TableIndex const last_) + std::string_view PushFQN(lua_State* const L_, StackIndex const t_) { STACK_CHECK_START_REL(L_, 0); // Lua 5.4 pushes &b as light userdata on the stack. be aware of it... luaL_Buffer _b; luaL_buffinit(L_, &_b); // L_: ... {} ... &b? TableIndex _i{ 1 }; - for (; _i < last_; ++_i) { + TableIndex const _last{ static_cast(lua_rawlen(L_, t_)) }; + for (; _i < _last; ++_i) { lua_rawgeti(L_, t_, _i); luaL_addvalue(&_b); luaL_addlstring(&_b, "/", 1); } - if (_i == last_) { // add last value (if interval was not empty) + if (_i == _last) { // add last value (if interval was not empty) lua_rawgeti(L_, t_, _i); luaL_addvalue(&_b); } @@ -151,7 +152,7 @@ static void update_lookup_entry(lua_State* const L_, StackIndex const ctxBase_, TableIndex const _deeper{ depth_ + 1 }; lua_rawseti(L_, _fqn, _deeper); // L_: ... {bfc} k o name? // generate name - std::string_view const _newName{ tools::PushFQN(L_, _fqn, _deeper) }; // L_: ... {bfc} k o name? "f.q.n" + std::string_view const _newName{ tools::PushFQN(L_, _fqn) }; // L_: ... {bfc} k o name? "f.q.n" // Lua 5.2 introduced a hash randomizer seed which causes table iteration to yield a different key order // on different VMs even when the tables are populated the exact same way. // Also, when Lua is built with compatibility options (such as LUA_COMPAT_ALL), some base libraries register functions under multiple names. diff --git a/src/tools.hpp b/src/tools.hpp index 7955263..420b5f8 100644 --- a/src/tools.hpp +++ b/src/tools.hpp @@ -36,6 +36,6 @@ static constexpr RegistryUniqueKey kLookupRegKey{ 0xBF1FC5CF3C6DD47Bull }; // re namespace tools { void PopulateFuncLookupTable(lua_State* L_, StackIndex i_, std::string_view const& name_); [[nodiscard]] - std::string_view PushFQN(lua_State* L_, StackIndex t_, TableIndex last_); + std::string_view PushFQN(lua_State* L_, StackIndex t_); void SerializeRequire(lua_State* L_); } // namespace tools -- cgit v1.2.3-55-g6feb