52 2004-03-01 15:48:00 +0000 Repeated and nested subexpressions (reproducible in most other engines) 2012-03-08 04:36:24 +0000 1 1 1 Unclassified glibc regex unspecified All All SUSPENDED P3 minor --- 1 bonzini gotom carlos glibc-bugs 125 bonzini 2004-03-01 15:48:08 +0000 Most engines, including glibc's have problems with the following regexes: (b(c)|d(e))* match against bcde --> \1=de, \3=e, but erroneously \2=c (a(b)*)* match against aba --> \1=a, but erroneously \2=b This is just a nit, because most other regex matching engines, either DFA-based or syntax-directed, have problems with this kind of regex. Note that while the second can be fixed by looking ahead of a OP_DUP_ASTERISK and preventively clearing an OP_OPEN_SUBEXP to which the OP_DUP_ASTERISK epsilon transits, the first is much harder and requires storing or building a "tree" of how the subexpressions nest (which would fix the second one as well). Paolo 2080 bonzini 2004-11-13 12:55:29 +0000 I doubt this will be fixed. 8562 decimal 2006-02-21 15:54:26 +0000 Do you have a small testcase demonstrating this problem? 8565 875 decimal 2006-02-21 16:28:01 +0000 Created attachment 875 Patch taken from bug comments. 8566 decimal 2006-02-21 16:29:11 +0000 Sorry. That attachment was meant for bug 14. 43407 pasky 2010-06-01 02:06:41 +0000 no feedback to testcase query (echo aba | sed -e 's/\(a\(b\)*\)*/\2/' does produce b, but it's not clear to me what should it print instead) 43442 bonzini 2010-06-01 06:26:33 +0000 echo aba | sed -e 's/\(a\(b\)*\)*/\2/' should print nothing because the final match of \1 is "a" and \2 must be a substring of \1. Reopening... 43443 bonzini 2010-06-01 06:27:16 +0000 ... and leaving suspended. 875 2006-02-21 16:28:00 +0000 2006-02-21 16:29:48 +0000 Patch taken from bug comments. glibc-bug-14.patch text/plain 1343 decimal LS0tIGdldGRlbnRzLmMub3JpZwkyMDAzLTEyLTA0IDE5OjExOjM4LjAwMDAwMDAwMCArMDIwMAor KysgZ2V0ZGVudHMuYwkyMDAzLTEyLTA0IDE5OjM4OjA2LjAwMDAwMDAwMCArMDIwMApAQCAtMTE3 LDcgKzExNyw3IEBACiAgICAgICBzaXplX3Qga2J5dGVzID0gbmJ5dGVzOwogICAgICAgaWYgKG9m ZnNldG9mIChESVJFTlRfVFlQRSwgZF9uYW1lKQogCSAgPCBvZmZzZXRvZiAoc3RydWN0IGtlcm5l bF9kaXJlbnQ2NCwgZF9uYW1lKQotCSAgJiYgbmJ5dGVzIDw9IHNpemVvZiAoRElSRU5UX1RZUEUp KQorCSAgJiYgbmJ5dGVzIDw9IHNpemVvZiAoa2VybmVsX2RpcmVudDY0KSkKIAl7CiAJICBrYnl0 ZXMgPSBuYnl0ZXMgKyBvZmZzZXRvZiAoc3RydWN0IGtlcm5lbF9kaXJlbnQ2NCwgZF9uYW1lKQog CQkgICAtIG9mZnNldG9mIChESVJFTlRfVFlQRSwgZF9uYW1lKTsKQEAgLTE3NSw4ICsxNzUsNyBA QAogCSAgICAgIG91dHAtPnUuZF9vZmYgPSBkX29mZjsKIAkgICAgICBpZiAoKHNpemVvZiAob3V0 cC0+dS5kX2lubykgIT0gc2l6ZW9mIChpbnAtPmsuZF9pbm8pCiAJCSAgICYmIG91dHAtPnUuZF9p bm8gIT0gZF9pbm8pCi0JCSAgfHwgKHNpemVvZiAob3V0cC0+dS5kX29mZikgIT0gc2l6ZW9mIChp bnAtPmsuZF9vZmYpCi0JCSAgICAgICYmIG91dHAtPnUuZF9vZmYgIT0gZF9vZmYpKQorCQkgICkK IAkJewogCQkgIC8qIE92ZXJmbG93LiAgSWYgdGhlcmUgd2FzIGF0IGxlYXN0IG9uZSBlbnRyeQog CQkgICAgIGJlZm9yZSB0aGlzIG9uZSwgcmV0dXJuIHRoZW0gd2l0aG91dCBlcnJvciwKQEAgLTE5 MCw3ICsxODksMTAgQEAKIAkJICByZXR1cm4gLTE7CiAJCX0KIAotCSAgICAgIGxhc3Rfb2Zmc2V0 ID0gZF9vZmY7CisJICAgICAgaWYoIGxhc3Rfb2Zmc2V0ID09IC0xICkKKwkJbGFzdF9vZmZzZXQg PSAwOworCSAgICAgIGxhc3Rfb2Zmc2V0ICs9IG9sZF9yZWNsZW47CisKIAkgICAgICBvdXRwLT51 LmRfcmVjbGVuID0gbmV3X3JlY2xlbjsKIAkgICAgICBvdXRwLT51LmRfdHlwZSA9IGRfdHlwZTsK IApAQCAtMjEzLDYgKzIxNSw3IEBACiAgICAgY29uc3Qgc2l6ZV90IHNpemVfZGlmZiA9IChvZmZz ZXRvZiAoRElSRU5UX1RZUEUsIGRfbmFtZSkKIAkJCSAgICAgIC0gb2Zmc2V0b2YgKHN0cnVjdCBr ZXJuZWxfZGlyZW50LCBkX25hbWUpKTsKIAorICAgIC8qIGJ1Zz8gKG5ieXRlcyBtaWdodCBiZSBz bWFsbGVyIHRoYW4gcmlnaHQgc2lkZSBvZiBtaW51cykgKi8KICAgICByZWRfbmJ5dGVzID0gTUlO IChuYnl0ZXMKIAkJICAgICAgLSAoKG5ieXRlcyAvIChvZmZzZXRvZiAoRElSRU5UX1RZUEUsIGRf bmFtZSkgKyAxNCkpCiAJCQkgKiBzaXplX2RpZmYpLAo=