LPEG bug?

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

LPEG bug?

Daurnimator
Today I was working on an lpeg pattern, and ran into this oddity,
which I believe to be a bug.
I've condensed it down as far as I could, if I remove any more the bug
seems to disappear.

The following script throws in the assert.
If you uncomment either of the alternate `path_abempty` definitions, it works.



local lpeg = require "lpeg"
local P = lpeg.P
local HEXDIG = lpeg.R("09","af", "AF")
local pct_encoded = P"%" * lpeg.C ( HEXDIG * HEXDIG ) / function (hex_num)
return string.char(tonumber(hex_num, 16))
end
local pchar         = lpeg.R("az","AZ") + pct_encoded
local path_abempty  = ( P"/" * pchar^0 )^0
-- local path_abempty  = ( P"/" * pchar^0 )^0 * ( P"/" * pchar^0 )^0
-- local path_abempty  = ( P"/" * pchar^0 )^0 * function() return true end
local path_rootless = pchar^1 * path_abempty
local path_absolute = P"/" * path_rootless^-1

assert(lpeg.Cs ( path_absolute ):match "/var/log/messages" ==
"/var/log/messages")

Reply | Threaded
Open this post in threaded view
|

Re: LPEG bug?

Dirk Laurie-2
2015-05-17 12:36 GMT+02:00 Daurnimator <[hidden email]>:

> Today I was working on an lpeg pattern, and ran into this oddity,
> which I believe to be a bug.
> I've condensed it down as far as I could, if I remove any more the bug
> seems to disappear.
>
> The following script throws in the assert.
> If you uncomment either of the alternate `path_abempty` definitions, it works.
>
>
>
> local lpeg = require "lpeg"
> local P = lpeg.P
> local HEXDIG = lpeg.R("09","af", "AF")
> local pct_encoded = P"%" * lpeg.C ( HEXDIG * HEXDIG ) / function (hex_num)
> return string.char(tonumber(hex_num, 16))
> end
> local pchar         = lpeg.R("az","AZ") + pct_encoded
> local path_abempty  = ( P"/" * pchar^0 )^0
> -- local path_abempty  = ( P"/" * pchar^0 )^0 * ( P"/" * pchar^0 )^0
> -- local path_abempty  = ( P"/" * pchar^0 )^0 * function() return true end
> local path_rootless = pchar^1 * path_abempty
> local path_absolute = P"/" * path_rootless^-1
>
> assert(lpeg.Cs ( path_absolute ):match "/var/log/messages" ==
> "/var/log/messages")
>

I don't even get this far. A freshly built LPEG does not load.
This is 64-bit Ubuntu 14.04 with Lua 5.3 installed under the
default directory /usr/local.

$ sudo luarocks install lpeg
[sudo] password for dirk:
Installing https://rocks.moonscript.org/lpeg-0.12.2-1.src.rock...
Using https://rocks.moonscript.org/lpeg-0.12.2-1.src.rock... switching
to 'build' mode
gcc -O2 -fPIC -I/home/dirk/include -c lpcap.c -o lpcap.o
gcc -O2 -fPIC -I/home/dirk/include -c lpcode.c -o lpcode.o
gcc -O2 -fPIC -I/home/dirk/include -c lpprint.c -o lpprint.o
gcc -O2 -fPIC -I/home/dirk/include -c lptree.c -o lptree.o
gcc -O2 -fPIC -I/home/dirk/include -c lpvm.c -o lpvm.o
gcc -shared -o lpeg.so -L/home/dirk/lib lpcap.o lpcode.o lpprint.o
lptree.o lpvm.o
Updating manifest for /usr/local/lib/luarocks/rocks
lpeg 0.12.2-1 is now built and installed in /usr/local (license: MIT/X11)

$ luarocks show lpeg

LPeg 0.12.2-1 - Parsing Expression Grammars For Lua

LPeg is a new pattern-matching library for Lua, based on Parsing Expression
Grammars (PEGs). The nice thing about PEGs is that it has a formal basis
(instead of being an ad-hoc set of features), allows an efficient and simple
implementation, and does most things we expect from a pattern-matching library
(and more, as we can define entire grammars).

License:     MIT/X11
Homepage:     http://www.inf.puc-rio.br/~roberto/lpeg.html
Installed in:     /usr/local

Modules:
    lpeg (/usr/local/lib/lua/5.3/lpeg.so)
    re (/usr/local/share/lua/5.3/re.lua)

$ lua -v -l lpeg
Lua 5.3.0  Copyright (C) 1994-2015 Lua.org, PUC-Rio
lua: error loading module 'lpeg' from file '/usr/local/lib/lua/5.3/lpeg.so':
    /usr/local/lib/lua/5.3/lpeg.so: undefined symbol: lua_replace
stack traceback:
    [C]: in ?
    [C]: in function 'require'
    [C]: in ?

Reply | Threaded
Open this post in threaded view
|

Re: LPEG bug?

Dirk Laurie-2
In reply to this post by Daurnimator
2015-05-17 12:36 GMT+02:00 Daurnimator <[hidden email]>:

> Today I was working on an lpeg pattern, and ran into this oddity,
> which I believe to be a bug.
> I've condensed it down as far as I could, if I remove any more the bug
> seems to disappear.
>
> The following script throws in the assert.
> If you uncomment either of the alternate `path_abempty` definitions, it works.
>
>
>
> local lpeg = require "lpeg"
> local P = lpeg.P
> local HEXDIG = lpeg.R("09","af", "AF")
> local pct_encoded = P"%" * lpeg.C ( HEXDIG * HEXDIG ) / function (hex_num)
> return string.char(tonumber(hex_num, 16))
> end
> local pchar         = lpeg.R("az","AZ") + pct_encoded
> local path_abempty  = ( P"/" * pchar^0 )^0
> -- local path_abempty  = ( P"/" * pchar^0 )^0 * ( P"/" * pchar^0 )^0
> -- local path_abempty  = ( P"/" * pchar^0 )^0 * function() return true end
> local path_rootless = pchar^1 * path_abempty
> local path_absolute = P"/" * path_rootless^-1
>
> assert(lpeg.Cs ( path_absolute ):match "/var/log/messages" ==
> "/var/log/messages")
>

Not having succeeded in building the current lpeg rock, I tried your
code using texlua, which runs Lua 5.2 with lpeg 0.10 preloaded in
its binary. No error.

Reply | Threaded
Open this post in threaded view
|

Re: LPEG bug?

Hisham
In reply to this post by Dirk Laurie-2
On 17 May 2015 at 15:41, Dirk Laurie <[hidden email]> wrote:

> 2015-05-17 12:36 GMT+02:00 Daurnimator <[hidden email]>:
>> Today I was working on an lpeg pattern, and ran into this oddity,
>> which I believe to be a bug.
>> I've condensed it down as far as I could, if I remove any more the bug
>> seems to disappear.
>>
>> The following script throws in the assert.
>> If you uncomment either of the alternate `path_abempty` definitions, it works.
>>
>>
>>
>> local lpeg = require "lpeg"
>> local P = lpeg.P
>> local HEXDIG = lpeg.R("09","af", "AF")
>> local pct_encoded = P"%" * lpeg.C ( HEXDIG * HEXDIG ) / function (hex_num)
>> return string.char(tonumber(hex_num, 16))
>> end
>> local pchar         = lpeg.R("az","AZ") + pct_encoded
>> local path_abempty  = ( P"/" * pchar^0 )^0
>> -- local path_abempty  = ( P"/" * pchar^0 )^0 * ( P"/" * pchar^0 )^0
>> -- local path_abempty  = ( P"/" * pchar^0 )^0 * function() return true end
>> local path_rootless = pchar^1 * path_abempty
>> local path_absolute = P"/" * path_rootless^-1
>>
>> assert(lpeg.Cs ( path_absolute ):match "/var/log/messages" ==
>> "/var/log/messages")
>>
>
> I don't even get this far. A freshly built LPEG does not load.
> This is 64-bit Ubuntu 14.04 with Lua 5.3 installed under the
> default directory /usr/local.
>
> $ sudo luarocks install lpeg
> [sudo] password for dirk:
> Installing https://rocks.moonscript.org/lpeg-0.12.2-1.src.rock...
> Using https://rocks.moonscript.org/lpeg-0.12.2-1.src.rock... switching
> to 'build' mode
> gcc -O2 -fPIC -I/home/dirk/include -c lpcap.c -o lpcap.o
> gcc -O2 -fPIC -I/home/dirk/include -c lpcode.c -o lpcode.o
> gcc -O2 -fPIC -I/home/dirk/include -c lpprint.c -o lpprint.o
> gcc -O2 -fPIC -I/home/dirk/include -c lptree.c -o lptree.o
> gcc -O2 -fPIC -I/home/dirk/include -c lpvm.c -o lpvm.o
> gcc -shared -o lpeg.so -L/home/dirk/lib lpcap.o lpcode.o lpprint.o
> lptree.o lpvm.o
> Updating manifest for /usr/local/lib/luarocks/rocks
> lpeg 0.12.2-1 is now built and installed in /usr/local (license: MIT/X11)
>
> $ luarocks show lpeg
>
> LPeg 0.12.2-1 - Parsing Expression Grammars For Lua
>
> LPeg is a new pattern-matching library for Lua, based on Parsing Expression
> Grammars (PEGs). The nice thing about PEGs is that it has a formal basis
> (instead of being an ad-hoc set of features), allows an efficient and simple
> implementation, and does most things we expect from a pattern-matching library
> (and more, as we can define entire grammars).
>
> License:     MIT/X11
> Homepage:     http://www.inf.puc-rio.br/~roberto/lpeg.html
> Installed in:     /usr/local
>
> Modules:
>     lpeg (/usr/local/lib/lua/5.3/lpeg.so)
>     re (/usr/local/share/lua/5.3/re.lua)
>
> $ lua -v -l lpeg
> Lua 5.3.0  Copyright (C) 1994-2015 Lua.org, PUC-Rio
> lua: error loading module 'lpeg' from file '/usr/local/lib/lua/5.3/lpeg.so':
>     /usr/local/lib/lua/5.3/lpeg.so: undefined symbol: lua_replace
> stack traceback:
>     [C]: in ?
>     [C]: in function 'require'
>     [C]: in ?

Looks like your Lua install doesn't match your lua.h headers. Note
that at build time it's picking stuff from /home/dirk/include and
/home/dirk/lib. Do you have another Lua version in there?

-- Hisham

Reply | Threaded
Open this post in threaded view
|

Re: LPEG bug?

Dirk Laurie-2
2015-05-17 22:09 GMT+02:00 Hisham <[hidden email]>:

> On 17 May 2015 at 15:41, Dirk Laurie <[hidden email]> wrote:
>> $ lua -v -l lpeg
>> Lua 5.3.0  Copyright (C) 1994-2015 Lua.org, PUC-Rio
>> lua: error loading module 'lpeg' from file '/usr/local/lib/lua/5.3/lpeg.so':
>>     /usr/local/lib/lua/5.3/lpeg.so: undefined symbol: lua_replace
>> stack traceback:
>>     [C]: in ?
>>     [C]: in function 'require'
>>     [C]: in ?
>
> Looks like your Lua install doesn't match your lua.h headers. Note
> that at build time it's picking stuff from /home/dirk/include and
> /home/dirk/lib. Do you have another Lua version in there?

That's it! I do have ~/include and it's a forgotten symlink to Lua 5.3
beta which I did not want to install systemwideI deleted it, rebuilt
lpeg and now it works, if "works" is the right word for "reproduces
the bug reported by the OP".

Reply | Threaded
Open this post in threaded view
|

Re: LPEG bug?

Roberto Ierusalimschy
In reply to this post by Daurnimator
> Today I was working on an lpeg pattern, and ran into this oddity,
> which I believe to be a bug.
> I've condensed it down as far as I could, if I remove any more the bug
> seems to disappear.
>
> The following script throws in the assert.
> If you uncomment either of the alternate `path_abempty` definitions, it works.
>
>
>
> local lpeg = require "lpeg"
> local P = lpeg.P
> local HEXDIG = lpeg.R("09","af", "AF")
> local pct_encoded = P"%" * lpeg.C ( HEXDIG * HEXDIG ) / function (hex_num)
> return string.char(tonumber(hex_num, 16))
> end
> local pchar         = lpeg.R("az","AZ") + pct_encoded
> local path_abempty  = ( P"/" * pchar^0 )^0
> -- local path_abempty  = ( P"/" * pchar^0 )^0 * ( P"/" * pchar^0 )^0
> -- local path_abempty  = ( P"/" * pchar^0 )^0 * function() return true end
> local path_rootless = pchar^1 * path_abempty
> local path_absolute = P"/" * path_rootless^-1
>
> assert(lpeg.Cs ( path_absolute ):match "/var/log/messages" ==
> "/var/log/messages")

That one is tough...

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: LPEG bug?

Roberto Ierusalimschy
In reply to this post by Daurnimator
> Today I was working on an lpeg pattern, and ran into this oddity,
> which I believe to be a bug.
> I've condensed it down as far as I could, if I remove any more the bug
> seems to disappear.
>
> The following script throws in the assert.
> If you uncomment either of the alternate `path_abempty` definitions, it works.
>
> local lpeg = require "lpeg"
> local P = lpeg.P
> local HEXDIG = lpeg.R("09","af", "AF")
> local pct_encoded = P"%" * lpeg.C ( HEXDIG * HEXDIG ) / function (hex_num)
> return string.char(tonumber(hex_num, 16))
> end
> local pchar         = lpeg.R("az","AZ") + pct_encoded
> local path_abempty  = ( P"/" * pchar^0 )^0
> -- local path_abempty  = ( P"/" * pchar^0 )^0 * ( P"/" * pchar^0 )^0
> -- local path_abempty  = ( P"/" * pchar^0 )^0 * function() return true end
> local path_rootless = pchar^1 * path_abempty
> local path_absolute = P"/" * path_rootless^-1
>
> assert(lpeg.Cs ( path_absolute ):match "/var/log/messages" ==
> "/var/log/messages")

The problem can be reduced to the following example:

   local re = require're'
   local p = re.compile[[ { ('ab' ('c' 'ef'?)*)? } ]]
   s = "abcefccefc"
   print(s, p:match(s))  --> abcefccefc abcefc

(An optional at the end of a repetition at the end of an
optional...) The bug is caused by a wrong optimization; the following
patch (in lpcode.c) should fix it:

@@ -759,7 +759,7 @@
       /* L1: test (fail(p1)) -> L2; <p>; jmp L1; L2: */
       int jmp;
       int test = codetestset(compst, &st, 0);
-      codegen(compst, tree, opt, test, fullset);
+      codegen(compst, tree, 0, test, fullset);  /* ?????? */
       jmp = addoffsetinst(compst, IJmp);
       jumptohere(compst, test);
       jumptothere(compst, jmp, test);

(I think there is a similar bug in repetitions, line 678, but I have to
recheck that.)

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: LPEG bug?

Daurnimator
On 5 June 2015 at 00:15, Roberto Ierusalimschy <[hidden email]> wrote:

>> Today I was working on an lpeg pattern, and ran into this oddity,
>> which I believe to be a bug.
>> I've condensed it down as far as I could, if I remove any more the bug
>> seems to disappear.
>>
>> The following script throws in the assert.
>> If you uncomment either of the alternate `path_abempty` definitions, it works.
>>
>> local lpeg = require "lpeg"
>> local P = lpeg.P
>> local HEXDIG = lpeg.R("09","af", "AF")
>> local pct_encoded = P"%" * lpeg.C ( HEXDIG * HEXDIG ) / function (hex_num)
>> return string.char(tonumber(hex_num, 16))
>> end
>> local pchar         = lpeg.R("az","AZ") + pct_encoded
>> local path_abempty  = ( P"/" * pchar^0 )^0
>> -- local path_abempty  = ( P"/" * pchar^0 )^0 * ( P"/" * pchar^0 )^0
>> -- local path_abempty  = ( P"/" * pchar^0 )^0 * function() return true end
>> local path_rootless = pchar^1 * path_abempty
>> local path_absolute = P"/" * path_rootless^-1
>>
>> assert(lpeg.Cs ( path_absolute ):match "/var/log/messages" ==
>> "/var/log/messages")
>
> The problem can be reduced to the following example:
>
>    local re = require're'
>    local p = re.compile[[ { ('ab' ('c' 'ef'?)*)? } ]]
>    s = "abcefccefc"
>    print(s, p:match(s))  --> abcefccefc abcefc
>
> (An optional at the end of a repetition at the end of an
> optional...) The bug is caused by a wrong optimization; the following
> patch (in lpcode.c) should fix it:
>
> @@ -759,7 +759,7 @@
>        /* L1: test (fail(p1)) -> L2; <p>; jmp L1; L2: */
>        int jmp;
>        int test = codetestset(compst, &st, 0);
> -      codegen(compst, tree, opt, test, fullset);
> +      codegen(compst, tree, 0, test, fullset);  /* ?????? */
>        jmp = addoffsetinst(compst, IJmp);
>        jumptohere(compst, test);
>        jumptothere(compst, jmp, test);
>
> (I think there is a similar bug in repetitions, line 678, but I have to
> recheck that.)
>
> -- Roberto


Hi Roberto,

Have you had a chance to follow up this and the outstanding LPEG bugs?
  - http://lua-users.org/lists/lua-l/2015-05/msg00483.html
  - http://lua-users.org/lists/lua-l/2015-05/msg00410.html

Reply | Threaded
Open this post in threaded view
|

Re: LPEG bug?

Roberto Ierusalimschy
> > The problem can be reduced to the following example:
> [...]
> > (I think there is a similar bug in repetitions, line 678, but I have to
> > recheck that.)
>
> Hi Roberto,
>
> Have you had a chance to follow up this and the outstanding LPEG bugs?

By follow up you mean the "similar bug in repetitions"? I checked, there
is no similar bug in repetitions.


>   - http://lua-users.org/lists/lua-l/2015-05/msg00483.html

I missed that message completely. (I mean, I did not see it.) The fix
seems trivial (again, a stupid bug):

lptree.c, in function lp_behind:

   TTree *tree;
   TTree *tree1 = getpatt(L, 1, NULL);
   int n = fixedlen(tree1);
-  luaL_argcheck(L, n > 0, 1, "pattern may not have fixed length");
+  luaL_argcheck(L, n >= 0, 1, "pattern may not have fixed length");
   luaL_argcheck(L, !hascaptures(tree1), 1, "pattern have captures");
   luaL_argcheck(L, n <= MAXBEHIND, 1, "pattern too long to look behind");
   tree = newroot1sib(L, TBehind);


>   - http://lua-users.org/lists/lua-l/2015-05/msg00410.html

That one the fix is this:

lptree.c:
 static TTree *newtree (lua_State *L, int len) {
   size_t size = (len - 1) * sizeof(TTree) + sizeof(Pattern);
   Pattern *p = (Pattern *)lua_newuserdata(L, size);
   luaL_getmetatable(L, PATTERN_T);
+  lua_pushvalue(L, -1);
+  lua_setuservalue(L, -3);
   lua_setmetatable(L, -2);
   p->code = NULL;  p->codesize = 0;
   return p->tree;

(OK, I will do a new release with these fixes...)

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: LPEG bug?

Daurnimator
On 17 July 2015 at 22:35, Roberto Ierusalimschy <[hidden email]> wrote:
> (OK, I will do a new release with these fixes...)
>
> -- Roberto

Any sign of this release?