Trie alternation with empty group at start of one alternative fails

[p5pRT]

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

Searchable as RT78356$

[p5pRT]

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]

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]

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]

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

[p5pRT]

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]

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