Generating Lua Inheritance Trees Quickly

Relic games store their entity/building/squad/etc. attributes in Lua files. They have alot of Lua files, all of which look something like this:

-- Some comment about copyright and editing the file by hand
GameData = Inherit([[sbps\races\chaos\chaos_squad.nil]])
GameData["squad_cap_ext"]["support_cap_usage"] = 2.00000
GameData["squad_combat_stance_ext"] = Reference([[sbpextensions\squad_combat_stance_ext.lua]])
-- more changes to GameData...

If you want to create an editor like their official Lua Attribute Editor, then you need to build an inheritance tree out of all those Inherit calls in all those files. The official editor is known for being slow, but I believe I've found a nice fast way to build it.

The first component of this is a function which is given the name of one Lua file, and returns the name of the file that it inherits from. You could load the entire file as text into memory and do search for Inherit( and extract the filename like that, however that would have the following disadvantages:

• The first instance of Inherit( may occur within a comment or string, so you'd have to work to not look inside comments nor strings
• The brackets are optional; Inherit([[file]]) and Inherit [[file]] are equivalent, so you'd have to allow for both
• Lua has several methods for specifying a string; Inherit("some\file"), Inherit('some\file'), Inherit([[some\file]]) and Inherit([==[some\file]==]) are all equivalent, so you'd have to allow for all of them

It would be alot simpler to let the official Lua library handle the parsing and lexing of the source file, and then grab the information we wanted out of the parsed state. So that is exactly what I do:

#include <lua.h>
#include <lauxlib.h>
// ...
struct read_info_t {
  IFile *pFile;
  char cBuffer[1024];
};
const char* ReaderFn(lua_State *L, read_info_t* dt, size_t *size) {
  *size = dt->pFile->readNoThrow(dt->cBuffer, 1, 1024);
  return dt->cBuffer;
}
// ...
lua_State L = luaL_newstate();
read_info_t oReadInfo;
oReadInfo.pFile = RainOpenFile(L"filename", FM_Read);
lua_load(L, (lua_Reader)ReaderFn, (void*)&oReadInfo, "lua file");

The other advantage of using the Lua API to parse the file is that you don't have to read it all in at once; lua_load takes the file a piece at a time.

Now comes the clever part; finding that Inherit filename from the lua_State. The call to Inherit would have compiled to Lua bytecodes:

GETGLOBAL "Inherit" -- Push the global `Inherit` onto the stack
LOADK "filename" -- Load the constants "filename" onto the stack
CALL 1 1 -- Call a function with one argument and one result

Thus if we look through the compiled bytecode looking for a GETGLOBAL Inherit followed by a LOADK and a CALL, we can obtain the filename from the LOADK:

#include <lobject.h>
#include <lopcodes.h>
#include <lstate.h>
// ...
Proto *pPrototype = ((Closure*)lua_topointer(L, -1))->l.p;
Instruction* I = pPrototype->code;
for(int ip = 0; ip < pPrototype->sizecode; ++ip, ++I) {
  if(GET_OPCODE(*I) == OP_GETGLOBAL
  && strcmp(svalue(pPrototype->k + GETARG_Bx(*I)), "Inherit") == 0
  && GET_OPCODE(I[1]) == OP_LOADK
  && GET_OPCODE(I[2]) == OP_CALL) {
    return svalue(pPrototype->k + GETARG_Bx(I[1]));
  }
}

Delving into the Lua internals like that is rather rude, and may be made incompatible even by minor version releases of Lua, but I'll be damned if it isn't extremely fast.

Now that we know which file is Inherit-ed by each other file, it is trivial to construct this into a tree.