Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Trie alternation with empty group at start of one alternative fails #10721

Closed
p5pRT opened this issue Oct 13, 2010 · 6 comments
Closed

Trie alternation with empty group at start of one alternative fails #10721

p5pRT opened this issue Oct 13, 2010 · 6 comments

Comments

@p5pRT
Copy link

p5pRT commented Oct 13, 2010

Migrated from rt.perl.org#78356 (status was 'resolved')

Searchable as RT78356$

@p5pRT
Copy link
Author

p5pRT commented Oct 13, 2010

From @ilmari

Created by @ilmari

$ perl5.8.8 -le 'print "foo" =~ /\A(?​:(?​:)foo|bar|zot)\z/ ? "match" : "FAIL"'
match

$ perl5.12.2 -le 'print "foo" =~ /\A(?​:(?​:)foo|bar|zot)\z/ ? "match" : "FAIL"'
FAIL

Removing any of the the anchors, the empty group, or one of the
alterations makes it match, as does changing any of the other
alternatives to starting with "f".

This regression was introduced in perl 5.9.5.

$ perl5.12.2 -le 'use re Debug => "ALL"; print "foo" =~ /\A(?​:(?​:)foo|bar|zot)\z/ ? "match" : "FAIL"'

Compiling REx "\A(?​:(?​:)foo|bar|zot)\z"
Starting first pass (sizing)

\A(?​:(?​:)f... | 1| reg
  | | brnc
  | | piec
  | | atom
(?​:(?​:)foo... | 2| piec
  | | atom
?​:(?​:)foo|... | | reg
(?​:)foo|ba... | | brnc
  | | piec
  | | atom
?​:)foo|bar... | | reg
)foo|bar|z... | | brnc
foo|bar|zo... | 3| piec
  | | atom
|bar|zot)\... | 5| inst - BRANCH
bar|zot)\z< | 6| brnc
  | 7| piec
  | | atom
zot)\z< | 9| brnc
  | 10| piec
  | | atom
\z< | 13| piec
  | | atom
Required size 14 nodes
Starting second pass (creation)
\A(?​:(?​:)f... | 1| reg
  | | brnc
  | | piec
  | | atom
(?​:(?​:)foo... | 2| piec
  | | atom
?​:(?​:)foo|... | | reg
(?​:)foo|ba... | | brnc
  | | piec
  | | atom
?​:)foo|bar... | | reg
)foo|bar|z... | | brnc
foo|bar|zo... | 3| piec
  | | atom
|bar|zot)\... | 5| tail~ NOTHING (2) -> EXACT
  | | inst - BRANCH
bar|zot)\z< | 6| brnc
  | 7| piec
  | | atom
|zot)\z< | 9| tail~ BRANCH (2) -> BRANCH
zot)\z< | | brnc
  | 10| piec
  | | atom
)\z< | 12| tail~ BRANCH (6) -> BRANCH
  | 13| tail~ BRANCH (9) -> TAIL
  | | tsdy~ NOTHING (3) -> PSEUDO
  | | ~ EXACT <foo> (4) -> EXACT
  | | ~ attach to TAIL (12) offset to 8
  | | tsdy~ EXACT <bar> (7) -> EXACT
  | | ~ attach to TAIL (12) offset to 5
  | | tsdy~ EXACT <zot> (10) -> EXACT
  | | ~ attach to TAIL (12) offset to 2
\z< | | tail~ SBOL (1) -> BRANCH
  | | piec
  | | atom
< | 14| tail~ BRANCH (2)
  | | ~ BRANCH (6)
  | | ~ BRANCH (9)
  | | ~ TAIL (12) -> EOS
  | 15| tail~ SBOL (1)
  | | ~ BRANCH (2)
  | | ~ BRANCH (6)
  | | ~ BRANCH (9)
  | | ~ TAIL (12)
  | | ~ EOS (13) -> END
first​:> 1​: SBOL (2)
first​:> 2​: BRANCH (6)
first at 2
Peep​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0 Last​:'' 0​:0/0 *Fixed​:'' @​ 0 Float​: '' @​ 0/0
Peep> 1​: SBOL (2)
Peep​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0 Last​:'' 0​:0/0 *Fixed​:'' @​ 0 Float​: '' @​ 0/0
Peep> 2​: BRANCH (6)
commit​: Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0 Last​:'' -1​:0/0 *Fixed​:'' @​ 0 Float​: '' @​ 0/0
  Peep​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0
  Peep> 3​: NOTHING (4)
  Peep​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0
  Peep> 4​: EXACT <foo> (12)
  join> 4​: EXACT <foo> (12)
  skip​:> 12​: TAIL (13)
  pre-fin​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0
  post-fin​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0
  Peep​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0
  Peep> 7​: EXACT <bar> (12)
  join> 7​: EXACT <bar> (12)
  skip​:> 12​: TAIL (13)
  pre-fin​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0
  post-fin​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0
  Peep​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0
  Peep> 10​: EXACT <zot> (12)
  join> 10​: EXACT <zot> (12)
  skip​:> 12​: TAIL (13)
  pre-fin​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0
  post-fin​:Pos​:0/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0
  Looking for TRIE'able sequences. Tail node is​: EOS
  - BRANCH (2) -> NOTHING => EXACT <foo> (First==-1,Last==-1,Cur==2)
  - BRANCH (6) -> EXACT <bar> => EOS (First==2,Last==-1,Cur==6)
  - BRANCH (9) -> EXACT <zot> => EOS (First==2,Last==-1,Cur==9)
  - TAIL (12) <SCAN FINISHED>
  make_trie start==2, first==2, last==12, tail==13 depth=1
  TRIE(NATIVE)​: W​:3 C​:6 Uq​:6 Min​:0 Max​:3
  Compiling trie using table compiler
  Char : b a r z o t
  State+-------------------------
  1 : 2 . . 5 . . ( 2) W 1
  2 : . 3 . . . . ( 1)
  3 : . . 4 . . . ( 1)
  4 : . . . . . . ( 0) W 2
  5 : . . . . 6 . ( 1)
  6 : . . . . . 7 ( 1)
  7 : . . . . . . ( 0) W 3
  Alloc​: 43 Orig​: 43 elements, Final​:6. Savings of %86.05
  Statecount​:8 Lasttrans​:7
  Char : Match Base Ofs b a r z o t
  State|-----------------------------------------------
  # 1| W 1 @​ 6 + 0[ 2 . . 5 . .]
  # 2| @​ 6 + 1[ . 3 . . . .]
  # 3| @​ 6 + 2[ . . 4 . . .]
  # 4| W 2 @​ 0
  # 5| @​ 6 + 4[ . . . . 6 .]
  # 6| @​ 6 + 5[ . . . . . 7]
  # 7| W 3 @​ 0
  MJD offset​:8 MJD length​:0
Peep​:Pos​:3/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0 Last​:'' -1​:0/0 *Fixed​:'' @​ 0 Float​: '' @​ 0/0
Peep> 12​: TAIL (13)
Peep​:Pos​:3/0 Flags​: 0x0 Whilem_c​: 0 Lcp​: 0 Last​:'' -1​:0/0 *Fixed​:'' @​ 0 Float​: '' @​ 0/0
Peep> 13​: EOS (14)
pre-fin​:Pos​:3/0 Flags​: 0x1 Whilem_c​: 0 Lcp​: 0 Last​:'' -1​:0/0 *Fixed​:'' @​ 0 Float​: '' @​ 0/0
post-fin​:Pos​:3/0 Flags​: 0x1 Whilem_c​: 0 Lcp​: 0 Last​:'' -1​:0/0 *Fixed​:'' @​ 0 Float​: '' @​ 0/0
commit​: Pos​:3/0 Flags​: 0x4 Whilem_c​: 0 Lcp​: 0 Last​:'' -1​:0/0 *Fixed​:'' @​ 3 Float​: '' @​ 0/0
minlen​: 3 r->minlen​:0
Final program​:
  1​: SBOL (2)
  2​: TRIE-EXACT<S​:1/7 W​:3 L​:0/3 C​:6/6>[bz] (13)
  <> (4)
  4​: EXACT <foo> (13)
  <bar> (13)
  <zot> (13)
  13​: EOS (14)
  14​: END (0)
anchored ""$ at 3 anchored(SBOL) minlen 3
r->extflags​: ANCH_SBOL
Matching REx "\A(?​:(?​:)foo|bar|zot)\z" against "foo"
  Setting an EVAL scope, savestack=3
regmatch start
  0 <> <foo> | 1​:SBOL(2)
  0 <> <foo> | 2​:TRIE-EXACT<S​:1/7 W​:3 L​:0/3 C​:6/6>[bz](13)
  matched empty string...
  0 <> <foo> | 13​:EOS(14)
  failed...
Match failed
FAIL
Freeing REx​: "\A(?​:(?​:)foo|bar|zot)\z"

Perl Info

Flags:
    category=core
    severity=medium

Site configuration information for perl 5.12.2:

Configured by ilmari at Thu Sep  9 18:09:40 BST 2010.

Summary of my perl5 (revision 5 version 12 subversion 2) configuration:
  Commit id: 7a3b65c9d99f69553fffe01f73d49fe9abf95120
  Platform:
    osname=linux, osvers=2.6.32-24-generic, archname=x86_64-linux
    uname='linux fenchurch 2.6.32-24-generic #42-ubuntu smp fri aug 20 14:21:58 utc 2010 x86_64 gnulinux '
    config_args='-Dprefix=/home/ilmari/perls/v5.12.2 -Duse64bitint -Uuselongdouble -DDEBUGGING -Doptimize=-g3 -Dusedevel -Uusethreads -Uversiononly -Dcccdlflags=-fPIC -Duseshrplib -des'
    hint=recommended, useposix=true, d_sigaction=define
    useithreads=undef, usemultiplicity=undef
    useperlio=define, d_sfio=undef, uselargefiles=define, usesocks=undef
    use64bitint=define, use64bitall=define, uselongdouble=undef
    usemymalloc=n, bincompat5005=undef
  Compiler:
    cc='cc', ccflags ='-DDEBUGGING -fno-strict-aliasing -pipe -fstack-protector -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64',
    optimize='-g3',
    cppflags='-DDEBUGGING -fno-strict-aliasing -pipe -fstack-protector -I/usr/local/include'
    ccversion='', gccversion='4.4.3', gccosandvers=''
    intsize=4, longsize=8, ptrsize=8, doublesize=8, byteorder=12345678
    d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=16
    ivtype='long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8
    alignbytes=8, prototype=define
  Linker and Libraries:
    ld='cc', ldflags =' -fstack-protector -L/usr/local/lib'
    libpth=/usr/local/lib /lib /usr/lib /lib64 /usr/lib64
    libs=-lnsl -lgdbm -ldb -ldl -lm -lcrypt -lutil -lc -lgdbm_compat
    perllibs=-lnsl -ldl -lm -lcrypt -lutil -lc
    libc=/lib/libc-2.11.1.so, so=so, useshrplib=true, libperl=libperl.so
    gnulibc_version='2.11.1'
  Dynamic Linking:
    dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E -Wl,-rpath,/home/ilmari/perls/v5.12.2/lib/5.12.2/x86_64-linux/CORE'
    cccdlflags='-fPIC', lddlflags='-shared -g3 -L/usr/local/lib -fstack-protector'

Locally applied patches:
    


@INC for perl 5.12.2:
    /home/ilmari/perls/v5.12.2/lib/site_perl/5.12.2/x86_64-linux
    /home/ilmari/perls/v5.12.2/lib/site_perl/5.12.2
    /home/ilmari/perls/v5.12.2/lib/5.12.2/x86_64-linux
    /home/ilmari/perls/v5.12.2/lib/5.12.2
    .


Environment for perl 5.12.2:
    HOME=/home/ilmari
    LANG=en_GB.utf8
    LANGUAGE (unset)
    LD_LIBRARY_PATH (unset)
    LOGDIR (unset)
    PATH=/home/ilmari/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/Babel/scripts:/home/ilmari/Babel/hk/script:/home/ilmari/Babel/hk/logfilters:/home/ilmari/Babel/hk/markf-svn
    PERL_AUTOINSTALL_PREFER_CPAN=1
    PERL_BADLANG (unset)
    PERL_CPANM_DEV=1
    PERL_MB_OPT=--installdirs site
    PERL_MM_OPT=INSTALLDIRS=site
    PERL_MM_USE_DEFAULT=1
    SHELL=/bin/bash

@p5pRT
Copy link
Author

p5pRT commented Oct 18, 2010

From @cpansprout

On Wed Oct 13 02​:53​:36 2010, ilmari wrote​:

$ perl5.8.8 -le 'print "foo" =~ /\A(?​:(?​:)foo|bar|zot)\z/ ? "match" :
"FAIL"'
match

$ perl5.12.2 -le 'print "foo" =~ /\A(?​:(?​:)foo|bar|zot)\z/ ? "match" :
"FAIL"'
FAIL

...

This regression was introduced in perl 5.9.5.

by​:

From​: Yves Orton <demerphq gmail.com>
Date​: Sat, 2 Sep 2006 16​:40​:12 +0000 (+0200)
Subject​: Re​: [PATCH] Trie jumping
X-Git-Tag​: perl-5.9.5~2170
X-Git-Url​:
http​://perl5.git.perl.org/perl.git/commitdiff_plain/786e8c118e1218e4c348fecf469934e080881633

Re​: [PATCH] Trie jumping
Message-ID​: <9b18b3110609020740y2eb9004cpab313c3353a437ca@​mail.gmail.com>

p4raw-id​: //depot/perl@​28785

See also
<http​://www.nntp.perl.org/group/perl.perl5.porters/2006/09/msg116095.html>.

@p5pRT
Copy link
Author

p5pRT commented Oct 18, 2010

From [Unknown Contact. See original ticket]

On Wed Oct 13 02​:53​:36 2010, ilmari wrote​:

$ perl5.8.8 -le 'print "foo" =~ /\A(?​:(?​:)foo|bar|zot)\z/ ? "match" :
"FAIL"'
match

$ perl5.12.2 -le 'print "foo" =~ /\A(?​:(?​:)foo|bar|zot)\z/ ? "match" :
"FAIL"'
FAIL

...

This regression was introduced in perl 5.9.5.

by​:

From​: Yves Orton <demerphq gmail.com>
Date​: Sat, 2 Sep 2006 16​:40​:12 +0000 (+0200)
Subject​: Re​: [PATCH] Trie jumping
X-Git-Tag​: perl-5.9.5~2170
X-Git-Url​:
http​://perl5.git.perl.org/perl.git/commitdiff_plain/786e8c118e1218e4c348fecf469934e080881633

Re​: [PATCH] Trie jumping
Message-ID​: <9b18b3110609020740y2eb9004cpab313c3353a437ca@​mail.gmail.com>

p4raw-id​: //depot/perl@​28785

See also
<http​://www.nntp.perl.org/group/perl.perl5.porters/2006/09/msg116095.html>.

@p5pRT
Copy link
Author

p5pRT commented Oct 18, 2010

@cpansprout - Status changed from 'new' to 'open'

@p5pRT
Copy link
Author

p5pRT commented Nov 3, 2010

From @cpansprout

On Sun Oct 17 17​:42​:17 2010, sprout wrote​:

On Wed Oct 13 02​:53​:36 2010, ilmari wrote​:

This regression was introduced in perl 5.9.5.

by​:

From​: Yves Orton <demerphq gmail.com>
Date​: Sat, 2 Sep 2006 16​:40​:12 +0000 (+0200)
Subject​: Re​: [PATCH] Trie jumping
X-Git-Tag​: perl-5.9.5~2170
X-Git-Url​:

http​://perl5.git.perl.org/perl.git/commitdiff_plain/786e8c118e1218e4c348fecf469934e080881633

Re​: [PATCH] Trie jumping
Message-ID​:
<9b18b3110609020740y2eb9004cpab313c3353a437ca@​mail.gmail.com>

p4raw-id​: //depot/perl@​28785

and fixed by 20dbff7.

@p5pRT
Copy link
Author

p5pRT commented Nov 3, 2010

@cpansprout - Status changed from 'open' to 'resolved'

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

No branches or pull requests

1 participant