list-lpeg and capture stack overflow

[Wesley Smith <wesley.hoke@...>]

I'm trying to figure out why a listlpeg pattern I've written is
generating so many captures.  Below is a vastly simplified script that
generates a stack of 15 captures when only 1 is returned by the
pattern.  When the subject of the match is larger, I easily get in
excess of 9000 captures.  It seems that the pattern is capturing every
singly sub-table and I have absolutely no idea why.  Is there
something about recursive grammar rules that implicitly generates
captures?  Is it possibly a bug where the stack isn't being properly
cleared after going down a level in the tree of tables?

There's no way to see what's going on from within Lua itself unless
you hit the stack overflow limit, so to test, put a printf in the
pushcapture function and watch.


static int pushcapture (CapState *cs) {
	printf("push_capture top %d\n", lua_gettop(cs->L));
        luaL_checkstack(cs->L, 4, "too many captures)");
....

}


Thanks for any hints.  I've been at it for a few days now and haven't
been able to figure it out.
wes



local listlpeg = require("listlpeg")

local Ct = listlpeg.Ct
local Cc = listlpeg.Cc
local Cg = listlpeg.Cg
local Cmt = listlpeg.Cmt
local C = listlpeg.C
local V = listlpeg.V
local P = listlpeg.P
local S = listlpeg.S
local R = listlpeg.R
local P = listlpeg.P
local L = listlpeg.L

function print_table(t, name, lvl)
	lvl  = lvl or 1
	
	local tab = string.rep("   ", lvl)
	print(tab..(name and (name .. " = {") or "{"))
	for k, v in pairs(t) do
		if(type(v) == "table") then
			print_table(v, k, lvl+1)
		else
			print(tab..tab..tostring(k).." = "..tostring(v)..",")
		end
	end
	print(tab.."}")
end

function print_match(t)
	if(type(t) == "table") then
		print_table(t)
	else
		print(t)
	end
end


function compress(t)
	local tt = {}
	local maxidx = 0
	for k, v in pairs(t) do
		maxidx = max(maxidx, k)
	end
	
	for i=1, maxidx do
		tt[#tt+1] = t[i]
	end
	
	return tt
end



local
ast_token = function(patt, name)
	return Cmt(L(P(1)), function(s, i)
				if(s[i].token == name) then
					return i, nil
				end
			end
		)
end

local
function ret(i, t)
	if(#t == 0) then
		return i, nil
	else
		return i, unpack(t)
	end
end

local
ast_rule = function(patt, name)
	return Cmt(L(patt), function(s, i, ...)
				if(s[i].rule == name) then
					-- propagate any captures
					return ret(i, compress{...})
				end
			end
		)
end

local
function apply_depth_first(grammar, p)
	local rules = {
		_patt = p,
		-- (the pattern) + (the pattern down one level in the list) + (look
in the next element)
		_depth_first = (V"_patt" + L(V"_depth_first") + P(1))^0
	}
	for k, v in pairs(grammar) do
		rules[k] = v
	end
	
	rules[1] = V"_depth_first"
	
	return P(rules)
end



local grammar = {
	[1] = "A",
	A = ast_rule(V"B" * V"C", "A"),
	
	B = ast_token("B", "B"),
	C = ast_token("C", "C"),
}

--patt = P(grammar)
patt = apply_depth_first(grammar, V"B")




local ast = {
	{
		"B",
		token = "B",
	},
	{
		"C",
		token = "C",
	},
	rule = "A",
}

print_match( patt:match{ast} )