Skip to content

Instantly share code, notes, and snippets.

@kdrnic

kdrnic/fix.md

Last active June 29, 2021 23:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kdrnic/f53878a93ed8d434f6066b201dcaeb0b to your computer and use it in GitHub Desktop.
Save kdrnic/f53878a93ed8d434f6066b201dcaeb0b to your computer and use it in GitHub Desktop.
Download ZIP
Finding and fixing a bug in a Lua JSON parser
Raw
fix.md

Finding and fixing a bug in a Lua JSON parser

This one is found in the wild while modding rnlf's Alakajam entry

Jump directly to the bug and its fix

Backstory

First I transformed the world.lua file...

return {
  version = "1.5",
  luaversion = "5.1",
  tiledversion = "1.7.0",
  orientation = "orthogonal",
  renderorder = "right-down",
  width = 256,
  height = 64,
  tilewidth = 32,
  tileheight = 32,
  nextlayerid = 6,
  nextobjectid = 203,
  properties = {},
  tilesets = {},
  layers = {
    {
      type = "objectgroup",
      draworder = "topdown",
      id = 2,
      name = "terrain",
      visible = true,
      opacity = 1,
      offsetx = 0,
      offsety = 0,
      parallaxx = 1,
      parallaxy = 1,
      properties = {},
      objects = {

...back into JSON so it is importable into Tiled...

{  "version": "1.5",  "luaversion": "5.1",  "tiledversion": "1.7.0",  "orientation": "orthogonal",  "renderorder": "right-down",  "width": 256,  "height": 64,  "tilewidth": 32,  "tileheight": 32,  "nextlayerid": 6,  "nextobjectid": 203,  "properties": {},  "tilesets": {},  "layers": [    {      "type": "objectgroup",      "draworder": "topdown",      "id": 2,      "name": "terrain",      "visible": true,      "opacity": 1,      "offsetx": 0,      "offsety": 0,      "parallaxx": 1,      "parallaxy": 1,      "properties": {},      "objects": [

...by using a hacky regex script...

var str = require("fs").readFileSync("world.lua").toString();
var diff;
do {  // replace curlies around arrays with square brackets
    diff = str.length;
    str = str.replace(/\{(((\n\t*)\t)\S.*(\2.*)*)\,\s--\s\[\d+\]\3\}/g,'[$1$3]');
    diff = diff - str.length;
} while (diff > 0);
str = str
.replace(/EPGP_DB\s=\s/, '')         // remove variable definition
.replace(/\s--\s\[\d+\](\n)/g, '$1') // remove comment
.replace(/\,(\n\t*\})/g, '$1')       // remove trailing comma
.replace(/\[(.*?)\]\s\=\s/g,'$1:')   // change equal to colon, remove brackets
.replace(/[\t\r\n]/g,'')            // remove tabs & returns
.replace("return", "") // remove starting 'return'
.replace(/([a-zA-Z_][a-zA-Z_0-9]*)\s+\=/g, '"$1":'); // turn keys into string literals

function setCharAt(str,index,chr) {
    if(index > str.length-1) return str;
    return str.substring(0,index) + chr + str.substring(index+1);
}

function obj2arr(str, polyStr)
{
	polyStr = '"' + polyStr + '": {';
	while((idx0 = str.indexOf(polyStr)) >= 0){
		var idx = idx0 + polyStr.length;
		console.log(idx, str.charAt(idx-1));
		for(var count = 1; count; idx++){
			if(str.charAt(idx) == '{') count++;
			if(str.charAt(idx) == '}') count--;
		}
		console.log(idx, str.charAt(idx - 1));
		str = setCharAt(str, idx0 + polyStr.length - 1, '[');
		str = setCharAt(str, idx - 1, ']');
	}
	return str;
}

str = obj2arr(str, "polygon");
str = obj2arr(str, "objects");
str = obj2arr(str, "polyline");
str = obj2arr(str, "layers");

require("fs").writeFileSync("world2.json", str);
JSON.parse(str);

...and then went on to modify tiledloader.lua...

--
-- coup
--
-- Copyright (c) 2014-2016, rnlf
--
-- This library is free software; you can redistribute it and/or modify it
-- under the terms of the MIT license. See LICENSE for details.
--

json = require("coup.coup.json")

local function loadTiledMap(filename, imageLoader)
  -- local mapfile = love.filesystem.load(filename)()
  local mapfile = json.decode(love.filesystem.read(filename))
  
  for i, t in ipairs(mapfile.tilesets) do
    local img = imageLoader(t.image)
    map:add_tileset(coup.tileset.Tileset(img, t.firstgid, t.tilewidth, t.tileheight))
  end

  local objectgroups = {}
  local imagelayers = {}
  for i, l in ipairs(mapfile.layers) do
    if l.type == "tilelayer" then
      map:add_layer(l.name, l.data)
    elseif l.type == "objectgroup" then
      objectgroups[l.name] = l
    elseif l.type == "imagelayer" then
      imagelayers[l.name] = l
    end
  end

  return map, objectgroups, imagelayers
end

return { loadTiledMapFile = loadTiledMap }

...which is when I found the bug.

The bug

Love2d promptly crashed thus:

Error

coup/coup/json.lua:184: JSON error in <huge string>:3945: Expected '}' or ',' instead of '1'


Traceback

[C]: in function 'error'
coup/coup/json.lua:13: in function 'throw'
coup/coup/json.lua:184: in function 'parse_value'
coup/coup/json.lua:203: in function 'parse_value'
coup/coup/json.lua:173: in function 'parse_value'
coup/coup/json.lua:203: in function 'parse_value'
coup/coup/json.lua:173: in function 'parse_value'
coup/coup/json.lua:203: in function 'parse_value'
coup/coup/json.lua:173: in function 'parse_value'
coup/coup/json.lua:295: in function 'decode'
coup/coup/tiledloader.lua:14: in function 'loadTiledMapFile'
world.lua:108: in function 'new'
coup/coup/class.lua:17: in function 'World'
main.lua:8: in function 'newGame'
main.lua:45: in function 'load'
[C]: in function 'xpcall'
[C]: in function 'xpcall'

Inside the actual string, the error was pointing at the second 1 in a float constant:

"x": 104.016

Which is absurd.

Checking however json.lua, we see the following:

local function parse_number(str, start)
  local end_of_num = start

  if str:sub(start, start) == '-' then
    end_of_num = end_of_num + 1
  end

  end_of_num = skip_int(str, end_of_num)

  if not end_of_num then
    throw(str, #str, "Input ended unexpectedly")
  end

  if str:sub(end_of_num, end_of_num) == '.' then
    end_of_num = skip_int(str, end_of_num + 1)
  end

  local exp_s, exp_e = str:find('^[eE][+-]?%d+', end_of_num)

  if exp_e then
    end_of_num = exp_e + 1
  end

  return tonumber(str:sub(start, end_of_num-1)), end_of_num

end

So this apparently handwritten parser parses fractional numbers by splitting them into int,dot,int. However, lets check skip_int:

local function skip_int(str, start)
  if str:sub(start, start) == '0' then
    return start + 1
  end

  if not str:find('^%d', start) then
    throw(str, start, "Expected decimal digit [0-9] instead of '" .. str:sub(start, start) .. "'")
  end

  return str:find('[^%d]', start)
end

so what happens is that the '016' fractional part is considered to be a valid int 0 followed by unexpected '16'.

And the fix is simple:

local function skip_frac_int(str, start)
  if not str:find('^%d', start) then
    throw(str, start, "Expected decimal digit [0-9] instead of '" .. str:sub(start, start) .. "'")
  end

  return str:find('[^%d]', start)
end


local function parse_number(str, start)
  local end_of_num = start

  if str:sub(start, start) == '-' then
    end_of_num = end_of_num + 1
  end

  end_of_num = skip_int(str, end_of_num)

  if not end_of_num then
    throw(str, #str, "Input ended unexpectedly")
  end

  if str:sub(end_of_num, end_of_num) == '.' then
    end_of_num = skip_frac_int(str, end_of_num + 1)
  end

  local exp_s, exp_e = str:find('^[eE][+-]?%d+', end_of_num)

  if exp_e then
    end_of_num = exp_e + 1
  end

  return tonumber(str:sub(start, end_of_num-1)), end_of_num

end

This also shows how untested the parser used is: apparently no one ever tried to parse any numbers with a fractional part x such 0<x<0.1

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment