Skip to content

Embeddable parser, AST, tree walker and compiler for the Linden Scripting Language based on LSLint

License

Notifications You must be signed in to change notification settings

SaladDais/tailslide

Repository files navigation

Intro

Build Status codecov

Tailslide provides an embeddable parser, AST representation, and tree walker library for Second Life's Linden Scripting Language. These can be used as the foundation for an LSL compiler or developing a superset of LSL.

A reference byte-perfect LSO compiler and semantically equivalent CIL compiler are provided. Semantic conformity with the output of LL's compilers is proven through extensive testcases and a fuzzer.

Also provided is a CLI utility to quickly lint or optimize LSL scripts, as well as visualize the AST of the supplied script.

If you're mainly interested in a command-line linting or optimization utility, please see lslint or LSL-PyOptimizer, respectively.

Credits

Tailslide is heavily based on the lslint LSL linter written by pclewis, see the NOTICE.txt file for the original README and credits.

Build

Linux & OSX

cmake, flex and bison must be installed through your system's package manager. On OS X you must install the Homebrew versions of flex and bison because the versions provided with XCode are extremely old.

git clone https://github.com/SaladDais/tailslide.git
cd tailslide
mkdir build
cd build
cmake ..
make

Windows

Not well-supported, but possible:

inside the cloned repo:

mkdir build
cd build
cmake -G"Visual Studio 17 2022" ..
cmake --build .

Tech Overview

Parsing

The parser behaves more or less like the one on SL's servers, quirks and all.

For example:

default { $$$$
    '' state_entry() {
        llOwnerSay(L"Hello
world!");
    }"
}/*{

is completely handled:

$ tailslide --show-tree tests/scripts/parser_abuse.lsl
default
{
    state_entry()
    {
        llOwnerSay("\"Hello\nworld!");
    }
}

TOTAL:: Errors: 0  Warnings: 0
script [none] (cv=) (1,1)
  ast node list [none] (cv=) (1,1)
  ast node list [none] (cv=) (1,1)
    state [none] (cv=) (1,1)
      identifier "default" [none] (cv=) (1,1)
      event handler [none] (cv=) (2,8)
        identifier "state_entry" [none] (cv=) (2,8)
        null [none] (cv=) (2,8)
        compound statement [none] (cv=) (2,22)
          statement [none] (cv=) (3,9)
            function call [none] (cv=) (3,9)
              identifier "llOwnerSay" [none] (cv=) (3,9)
              constant expression [string] (cv=string constant: "\"Hello\nworld!") (3,20)
                string constant: "\"Hello\nworld!" [string] (cv=string constant: "\"Hello\nworld!") (3,20)

Special attention has been paid to weird, undocumented corner cases.

Optimizations

Constant Folding

The constant folding implementation is currently very simple. Tailslide makes multiple walks down the tree checking if an expression is constant, and replaces it with its value.

integer foo = 2;
foo = foo + 2 + 4 + 3 + 5;

won't currently be simplified at all due to how expressions are represented and will require term rewriting to move non-constant parts of expressions as far to the right (left) as possible.

There are still some cases where constants may be folded but currently aren't, and some differences in how floating point operations are folded.

Unused Variable / Function Pruning

Any variable or function that is unused after constant folding may be pruned to save bytecode space.

Symbol Mangling

Names of user defined functions, their parameters and globals contribute to bytecode size. To reduce bytecode size, Tailslide can mangle user-defined symbols into more compact ones like _a, _b, etc. This may also help with disambiguation when converting the AST to another language with different scoping / variable shadowing rules.

This isn't the most efficient naming scheme if targeting SL in particular, since it's better to take advantage of strings already in the constant pool.

License

MIT, scripts used for test data (barring those added by me and those in bugs/) are property of their respective owners

Serialization code based on Kai Mast's BitStream library is included in BitStream.hh, and is licensed under the BSD 3-clause license.