Static code validation system for Lua

["Alexander Gladysh" <agladysh@...>]

Hi, all!

On my previous job, we had developed a rather large game engine
project, heavily utilizing Lua:  about 100K lines of C++ engine code
and about 300K lines of both code and data in Lua for all games in
total. It was an adventure game engine, with several commercial games
released in it.

Needless to say, Lua is a great language for game development. We had
no regrets for picking it for our development process. Of course,
there were some things, causing discomfort, but it all was overwhelmed
by overall positive experience.

One of such 'discomforting things' is something that Lua 'inherited'
from being a dynamic language. Any typo in variable or function name,
that would be caught by compiler in languages like C++, in dynamic
language lingers until particular piece of code, containing this typo,
gets executed. Run-time errors are always worse than compile-time
ones.

It is hard to come with easy to create generic and automated solution
for this issue for complicated system-level code. But we've managed to
create a tool to validate game logic code, written by our
level-designers. Implemented validation system allowed us to catch
more errors early, and subjectively significantly sped up our
development process compared to projects, released before. I even
self-assuredly thought to write an article about it… :)

We had a cleanly defined API for end-user code, and that code was
sandboxed to see that API only. The 'API' in this case means thin
abstraction layer between end-user code and system-level stuff. Game
logic code mostly consisted of lots of separate callback functions and
it appeared that most of functions had linear execution path (that is,
no ifs or loops).

This allowed us to do code validation by running user's code in
special global environment, using heavy meta-table magic. Basically,
this environment registered an access to unauthorized global table
keys as an error (preserving context information enough to find this
error in the code). As for authorized keys – they were either global
tables (representing modules), which were instances of the same
environment with different set of allowed keys; or API functions.

API was hand-tuned for validation mode. Actually, we've used 'real'
API functions, fenv'ed to special environment, where all assertion and
type-validation functions were left as is to validate incoming
arguments, and other was turned to NOP-functions by meta-table magic.
In complex cases we've just put 'if test_mode then return' statements
right after validation. While this was roughly enough to adequately
validate API calls, in more complex cases, completely new 'mock' API
could be writing specially for validation mode.

However, there is one major flaw, which we had not time to cover
during active development phase, since whole validation system was
developed in background as a better-than-nothing experimental tool.
That is execution branching support, mentioned above. In our project
validation mode, only one branch of if statement is tested, and loops
can go infinite. Due to low number of cases which required execution
flow branching, this problem was worked around by hand-tuning the
end-user code.

When I thought about generalizing our limited static validation
approach, I thought that it would be possible to dynamically build
graphs of all possible execution paths in end-user code, and run
through each path by changing resulting values in each node by
returning different values from comparison operations involving
'global' values.

But when I came to seriously studying this matter, I've found that is
impossible to do in pure Lua, since the language does not allow user
to define comparison operators between different types. Furthermore,
it is impossible at all (again, in pure Lua) to simulate different
results for implicit nil-comparison as in 'if my_var then … else …
end'.

So, there is no chance for pure Lua solution. However the problem
allows utilizing of stand-alone code verification tools, either some
custom-written parser or even modified Lua interpreter itself.

I understand that mentioned restrictions on comparison meta-methods
are there due to execution speed issues, and I agree with such design
decision. However, for validation purposes, slow execution speed can
be tolerated within reasonable limits.

> From quick glance at code at lvm.c – it seems that it is possible to
allow user to write type-independent comparison meta-methods, and I
hope (have not checked in detail) that implicit nil-comparison can be
made overloadable too. I have little experience within Lua internals
though – so it is mostly an assumption.

Other possible solution is to analyze the compiler-generated byte-code
itself, looking for global table access instructions. This would allow
us to get rid of complicated work with execution-paths. Simple
implementation may not deal with complex cases such as dynamic global
table key generation. Handling of direct access by constant name
should still provide enough validation power… Nested tables (as module
namespaces for example) can pose some problems too, but, I think, this
should be still simpler than working with source-code directly.

So, I am a bit unsure what to do with this idea about static
validation system. First, and most important, – is there an interest
to this subject? May be I've missed some other existing approach? May
be I'm missing something that renders such system to be impractical or
even impossible to implement in generic-enough variation?

If it is feasible, I can write an article about our limited validation
system and about general script system organization. In spite of
mentioned execution-flow limitations, it was fairly effective in our
circumstances. Or I can pick one of workaround ways, develop it to the
usable implementation point, and write about it… At this point, I like
the byte-code-analyzer idea most.

What do you think?

Thanks for reading and sorry for a long letter,
Alexander.