Writing a DSL in Scribunto

I am a person who mainly does programming for recreation; it's very fun, really, but it's also one of the contributing factors that creates the bad habits that I often do.

When a person programs for fun, one often does things that are not necessarily the best way to solve a problem, as there's not really a need to worry about anyone else looking at it. I mean, who cares how I achieve the result? As long as it does the thing I want, it's good enough. But because of that, when working on a project for a site with over two million monthly page views... It's not a good mindset, is it?

It started pretty innocently. The Tower Defense Simulator Wiki has roughly 50 towers at the time, each with like four to five levels, and a bunch of derived stats like DPS that have to be right in every single cell. Often, a tower will have around 12 cells that need to be calculated, double that if it has variants such as Golden or PVP.

Doing that by hand is exactly as miserable as it sounds; the editors have to calculate everything by hand, scanning the tables, plug the formula, do the rounding, etc. And you have to update it every time the tower changes in the game. So we ended up with Neowtext and its Scribunto runner, Neowbunto.

It looks like this:

{{Neow|<nowiki>
<var>
$DPS$ = Damage / Firerate
$TP$ = $FNC-TOTAL-COST$
$COST$ = 125; 50; 375; 1350; 2200
$FNC-ROFBUG$ = Firerate
</var>
{| class="wikitable"
! Level !! Total Cost !! Damage !! Firerate !! DPS !! Cost Efficiency
|-
| 0 || {{Money|$TP$}} || 20 || 1.4 || $DPS$ || {{Money|$CE$}}
|}
</nowiki>}}

You probably noticed the use of the nowiki tag, but we'll get to it later. Basically, one simply defines a formula once in <var>, then just drop $DPS$ in a cell and it figures it out for that row. There are a lot, and I mean a lot, of other niceties such as arrays and functions, so if you are interested in its usage, feel free to check out its help documentation.

But anyhow, back to the story of how we went from the extremely flaky Lua version that broke every other week to a production-ready (as the industry likes to call it) Fennel version.

Held Together by Find-and-Replace

The last pure-Lua version is here if you want to suffer. About 900 lines in one file, not a single module in sight, and it worked just well enough to be dangerous.

The whole trick was find-and-replace, more precisely gsub. A formula like Splash Damage / Firerate had its spaces stripped so it became SplashDamage/Firerate, which was fine when every column was one word.

calc = function(e)
  e = e:gsub("%s+", "")
  -- "Splash Damage / Firerate" -> "SplashDamage/Firerate"

However, the second a table had both Splash Damage and Damage, the replacer would see Damage sitting inside SplashDamage and overwrite the wrong thing. My fix was to replace the longest names first and pray to God nothing important still hid inside a longer one and is misinterpreted:

table.sort(sorted_keys, function(a, b) return #a > #b end)
for _, k in ipairs(sorted_keys) do
  expr = expr:gsub(safe_k, clean_v)
end

Then towers got branching upgrades, and tables needed to read other tables. As an example, $COST@5@A$ (cost at level 5 on path A) and Sentry Stats.DPS (the DPS column from the Sentry Stats table, same level). The first search pattern I wrote could not see a space, so Sentry Stats never matched. I then brilliantly added a second, sloppier pattern on top. One function ended up doing lookups, running totals, following $VAR$ into $VAR$, and a hardcoded stop at depth 10 so it would not loop forever for the cherry on top. Think it stopped there? Nope, another two more replace passes over the row. Surely, you'd see the problem, right?

Tables were the same mess. We have a Rate of Fire button so editors can flip firerate to match an old in-game bug. Normal cells and that button each built their own copy of the table, cleaned headers a little differently, and sometimes stored the same column under two names. A level cell was treated as a plain number until someone wrote 1-3, which is a range, not a number. Header rows that mixed two wiki cell styles ate columns:

for cell in ((t:sub(2):gsub("%|%|", "!!")) .. "!!"):gmatch("([^!]*)!!") do
-- "||" in headers was not publicly documented
-- but MediaWiki converts "||" to "!!" anyway

Every new case was another replace.

The bugs started stepping on each other. I would fix a match in one place, then the other function would paste values in a different order and undo it. Regular and PVP live in tabs, so missing the tab name once and one tab writes over the other. Most tickets were the same three problems on shuffle: a space in a name, the wrong copy of a table, or a quiet 0 where something should have been missing. The butterfly effect is insane, basically.

Why Fennel?

Well, to be honest? Lisp is cool, that's it, really. I still do this because I want to enjoy it since I'm not paid, obviously. If I force myself through the same ugly Lua file over and over, I get bored and stop.

The old file was one blob, so everything leaked into everything else. toggleID, tableCache, and branchMapRef were globals, for example. Fennel let me split the work into small files using --require-as-include, one for reading formulas, one for doing the math, one for reading wiki tables, you get the point. Finally, smash them back into the single Lua file Scribunto will actually accept. That compile step is so beautiful I could cry; I get to work like a normal person, and the wiki gets to see the fruits of my labor.

Most importantly, I get to write an AST with its lexer and parser in a functional style. The old calc stripped spaces and gsub'd names into a string. The new lexer walks the formula and emits tokens, so Splash Damage is one ident and Sentry Stats.DPS is one :dotref instead of two words fighting over something as small as a dot:

(fn col-start? [s j]
  (and (= (at s j) ".")
       (let [n (at s (+ j 1))]
         (and (not= n "") (not (n:match "%d")) (not (n:match "%s"))
              (not (is-op-char? n))))))

(fn glued-hyphen? [s j]
  (and (= (at s j) "-") (not= (at s (+ j 1)) "-")
       (let [prev (at s (- j 1))
             nxt (at s (+ j 1))]
         (and prev (prev:match "[%w]") nxt (nxt:match "[%w]")))))

$VAR$ expansion is a case on a parse cache, not the old resolve that did pinning, lookups, totals, and d > 10 in one function. A cycle is an error with a path:

(set parse-var
  (fn [name var-env parse-cache parsing-stack]
    (case (. parse-cache name)
      nil (do
            (when (stack-has? parsing-stack name)
              (error (cycle-message parsing-stack name)))
               ;; ... parse the body, cache the AST, return it ...
            )
      ast ast)))

The evaluator is a dispatch table; each AST tag is a tiny fn, meaning there's no second gsub pass. There's no sorting keys by length, so Damage does not eat Splash Damage:

(local node-handlers {})

(fn node-handlers.dotref [ctx node]
  (let [v (table-lookup ctx (. node 2) (. node 3))]
    (if (= v nil)
        (error (.. "unresolved '" (. node 2) "." (. node 3) "'"))
        v)))

(set eval-node
  (fn [ctx node]
    (let [tag (. node 1)
          h (. node-handlers tag)]
      (if h (h ctx node) (error (.. "unhandled " tag))))))

Table reading lives in one place! parse-level-keys turns 1-3 into three rows. Regular and PVP stay under Name and Name|PVP on purpose; RoF values sit on the same row as Header_ROF. A missing $COST$ errors instead of summing to 0.

All of this to say, I can actually find a bug now, haha.

What It Does

We call it through Template:Neow, which is one line:

{{#invoke:Neowbunto|heeho|{{{1}}}}}

That means the engine never sees a page object or a list of cells; let's use the same example from the very start:

{{Neow|<nowiki>
<var>
$DPS$ = Damage / Firerate
$TP$ = $FNC-TOTAL-COST$
$COST$ = 125; 50; 375; 1350; 2200
$FNC-ROFBUG$ = Firerate
</var>
{| class="wikitable"
! Level !! Total Cost !! Damage !! Firerate !! DPS !! Cost Efficiency
|-
| 0 || {{Money|$TP$}} || 20 || 1.4 || $DPS$ || {{Money|$CE$}}
|}
</nowiki>}}

It sees one string, being whatever the editor put in {{Neow|...}}, sitting in frame.args[1]. From there, the work is just cutting that string up. It reads the <var> block, strips it out, finds every {| ... |} once, remembers each row by level, fill $DPS$ against that row. If the page asked for the Rate of Fire button (FNC-ROFBUG), wrap the result. Then frame:preprocess so a template such as {{Money|...}} still runs.

One of the crucial things done with this new system is the fact that it reads first, then does math. The old code never knew whatever the heck a column name was. It kept substituting until the string looked numeric enough. That is why something like Cash Shot-- and --3 used to mean whatever the latest replace felt like. Now with an actual parser, a name with -- after it is 'this value, minus one,' and --3 at the start is just minus three.

$VAR$ is still a shortcut, of course. As an example, if you were to write $HEY$ = 123 / $HELLO$ and $HELLO$ = 5 * 2 + 1, you get 123 / 5 * 2 + 1 and not 123 / 11. Think of it like a macro; it may feel unintuitive and even pedantic to some, but it's extremely easy to predict, which is what the original version severely lacked.

Oh Right, nowiki...

Anyone who has tried to invent syntax on MediaWiki hates this part. You still have to live with it, because the parser is built for templates, not for you.

If you hand a wiki table to a template the normal way, MediaWiki eats it before our code runs. {{ becomes a template call. {| becomes a table. | splits arguments. By the time Lua sees frame.args[1], the page you wrote is gone. That is why Dev:Arguments exists, and also why we do not use it here. Merging parent-frame args is how the old module picked up random parameters from whoever called {{Neow}}.

So editors have to wrap the body in <nowiki>. That tells MediaWiki to leave the text alone. Then we peel the wrapper off like this:

(fn content-arg [frame]
  (let [args (and frame frame.args)
        raw (and args (. args 1))]
    (if (= raw nil) "" (trim raw))))

(fn prepare-content [raw]
  (let [unstrip (or (and mw mw.text mw.text.unstripNoWiki) (fn [x] x))
        text (unstrip (or raw ""))]
    (unescape-entities text)))

(fn heeho [frame]
  (let [raw (content-arg frame)
        content (prepare-content raw)]
    (if (or (not content) (= content ""))
        "'''Neowbunto''': No valid content found."
        (preprocess frame (render-page content frame)))))

It's a shame though, since using <nowiki> means not getting syntax highlighting; you'll have to rely on a third-party text editor, or perhaps, monkey-patch the current editor to add syntax highlighting support. (I have one written for CodeMirror here, albeit not accounting for <nowiki>, still.)

If you yourself want to make a little language on MediaWiki, or merely some custom syntax, plan for this first. Anything with {|, {{, or | gets mangled unless you <nowiki> it and take it back yourself.

So Is It Faster?

Archer/History is a good check because of its rigorous usage of Neowtext. The original version took about 1.34 seconds of Lua, while the new one is about 0.88 seconds. Roughly 34% faster.

It being faster is not just it, though. As mentioned before, this new engine is more robust, less prone to errors, and is overall much more reliable and maintainable.

So, if you are ever tempted to write a 900-line file of clever find-and-replace because 'it is just a wiki template,' well, don't. At some point, I was comparing dumps at two in the morning, trying to figure out why the Dot Notation had grabbed the wrong tab, and wished past me had listened.