Package: lua-lpeg
Version: 1.0.0-2
Severity: normal
Tags: patch
Dear Maintainer,
under certain conditions, lpeg will crash while walking the pattern tree
looking for TCapture nodes.
The reproducer, taken from the upstream discussion, is:
root@sid-lua:~# cat repro.lua
#!/usr/bin/env lua
lpeg = require "lpeg"
p = lpeg.C(-lpeg.P{lpeg.P'x' * lpeg.V(1) + lpeg.P'y'})
p:match("xx")
The program crashes due to a hascaptures() infinite recursion:
root@sid-lua:~# ./repro.lua
Segmentation fault (core dumped)
(gdb) bt -25
#523984 0x00007ffff7a3743c in hascaptures () from
/usr/lib/x86_64-linux-gnu/lua/5.2/lpeg.so
#523985 0x00007ffff7a3743c in hascaptures () from
/usr/lib/x86_64-linux-gnu/lua/5.2/lpeg.so
#523986 0x00007ffff7a3743c in hascaptures () from
/usr/lib/x86_64-linux-gnu/lua/5.2/lpeg.so
#523987 0x00007ffff7a3743c in hascaptures () from
/usr/lib/x86_64-linux-gnu/lua/5.2/lpeg.so
#523988 0x00007ffff7a3743c in hascaptures () from
/usr/lib/x86_64-linux-gnu/lua/5.2/lpeg.so
#523989 0x00007ffff7a3743c in hascaptures () from
/usr/lib/x86_64-linux-gnu/lua/5.2/lpeg.so
#523990 0x00007ffff7a3815c in ?? () from
/usr/lib/x86_64-linux-gnu/lua/5.2/lpeg.so
#523991 0x00007ffff7a388e3 in compile () from
/usr/lib/x86_64-linux-gnu/lua/5.2/lpeg.so
#523992 0x00007ffff7a36fab in ?? () from
/usr/lib/x86_64-linux-gnu/lua/5.2/lpeg.so
#523993 0x000055555555fd1e in ?? ()
#523994 0x000055555556a5fc in ?? ()
#523995 0x00005555555600c8 in ?? ()
#523996 0x000055555555f63f in ?? ()
#523997 0x000055555556030f in ?? ()
#523998 0x000055555555dc91 in lua_pcallk ()
#523999 0x000055555555b896 in ?? ()
#524000 0x000055555555c54b in ?? ()
#524001 0x000055555555fd1e in ?? ()
#524002 0x0000555555560092 in ?? ()
#524003 0x000055555555f63f in ?? ()
#524004 0x000055555556030f in ?? ()
#524005 0x000055555555dc91 in lua_pcallk ()
#524006 0x000055555555b64b in ?? ()
#524007 0x00007ffff7c94bbb in __libc_start_main (main=0x55555555b5f0, argc=2,
argv=0x7fffffffe6d8, init=<optimized out>, fini=<optimized out>,
rtld_fini=<optimized out>, stack_end=0x7fffffffe6c8)
at ../csu/libc-start.c:308
#524008 0x000055555555b70a in ?? ()
The expected behavior is to have the program finish normally
This was reproduced in Debian Sid, and the versions of lua5.2 and lua-lpeg are:
root@sid-lua:~# dpkg -l | grep lua
ii lua-lpeg:amd64 1.0.0-2 amd64 LPeg
library for the Lua language
ii lua5.2 5.2.4-1.1+b3 amd64 Simple,
extensible, embeddable programming language
This was fixed upstream in 1.0.1 by stopping the recursion in TCall nodes and
controlling that TRule nodes do not follow siblings (sib2). Attached there's a
backported patch from upstream that should fix the issue.
The upstream discussion can be found here:
http://lua.2524044.n2.nabble.com/LPeg-intermittent-stack-exhaustion-td7674831.html
Thanks for considering the patch!
Victor
diff -Nru lua-lpeg-1.0.0/debian/patches/series
lua-lpeg-1.0.0/debian/patches/series
--- lua-lpeg-1.0.0/debian/patches/series 2018-02-23 12:39:59.000000000
+0100
+++ lua-lpeg-1.0.0/debian/patches/series 2019-10-02 17:49:19.000000000
+0200
@@ -0,0 +1 @@
+stop-hascaptures-recursion.patch
diff -Nru lua-lpeg-1.0.0/debian/patches/stop-hascaptures-recursion.patch
lua-lpeg-1.0.0/debian/patches/stop-hascaptures-recursion.patch
--- lua-lpeg-1.0.0/debian/patches/stop-hascaptures-recursion.patch
1970-01-01 01:00:00.000000000 +0100
+++ lua-lpeg-1.0.0/debian/patches/stop-hascaptures-recursion.patch
2019-10-02 17:49:19.000000000 +0200
@@ -0,0 +1,59 @@
+From: Victor Tapia <victor.ta...@canonical.com>
+Date: Tue, 8 Oct 2014 18:44:17 +0200
+Origin: backport, http://www.inf.puc-rio.br/~roberto/lpeg/lpeg-1.0.1.tar.gz
+Description: Stop infinite recursion in hascaptures()
+ Stop recursion in TCall nodes and control that TRule nodes do not follow sib2
+
+Bug-Ubuntu: https://bugs.launchpad.net/ubuntu/+bug/1580385
+
+---
+--- a/lpcode.c
++++ b/lpcode.c
+@@ -126,6 +126,27 @@
+
+
+ /*
++** Visit a TCall node taking care to stop recursion. If node not yet
++** visited, return 'f(sib2(tree))', otherwise return 'def' (default
++** value)
++*/
++static int callrecursive (TTree *tree, int f (TTree *t), int def) {
++ int key = tree->key;
++ assert(tree->tag == TCall);
++ assert(sib2(tree)->tag == TRule);
++ if (key == 0) /* node already visited? */
++ return def; /* return default value */
++ else { /* first visit */
++ int result;
++ tree->key = 0; /* mark call as already visited */
++ result = f(sib2(tree)); /* go to called rule */
++ tree->key = key; /* restore tree */
++ return result;
++ }
++}
++
++
++/*
+ ** Check whether a pattern tree has captures
+ */
+ int hascaptures (TTree *tree) {
+@@ -134,14 +155,17 @@
+ case TCapture: case TRunTime:
+ return 1;
+ case TCall:
+- tree = sib2(tree); goto tailcall; /* return hascaptures(sib2(tree)); */
++ return callrecursive(tree, hascaptures, 0);
++ case TRule: /* do not follow siblings */
++ tree = sib1(tree); goto tailcall;
+ case TOpenCall: assert(0);
+ default: {
+ switch (numsiblings[tree->tag]) {
+ case 1: /* return hascaptures(sib1(tree)); */
+ tree = sib1(tree); goto tailcall;
+ case 2:
+- if (hascaptures(sib1(tree))) return 1;
++ if (hascaptures(sib1(tree)))
++ return 1;
+ /* else return hascaptures(sib2(tree)); */
+ tree = sib2(tree); goto tailcall;
+ default: assert(numsiblings[tree->tag] == 0); return 0;
