| Chih-Hung Hsieh | e42c505 | 2020-04-16 10:44:21 -0700 | [diff] [blame] | 1 | NOTE implicit vs. explicit repetitions : 2009-02-02 |
| 2 | |
| 3 | # Glenn Fowler <gsf@research.att.com> |
| 4 | # conforming matches (column 4) must match one of the following BREs |
| 5 | # NOMATCH |
| 6 | # (0,.)\((\(.\),\(.\))(?,?)(\2,\3)\)* |
| 7 | # (0,.)\((\(.\),\(.\))(\2,\3)(?,?)\)* |
| 8 | # i.e., each 3-tuple has two identical elements and one (?,?) |
| 9 | |
| 10 | E ((..)|(.)) NULL NOMATCH |
| 11 | E ((..)|(.))((..)|(.)) NULL NOMATCH |
| 12 | E ((..)|(.))((..)|(.))((..)|(.)) NULL NOMATCH |
| 13 | |
| 14 | E ((..)|(.)){1} NULL NOMATCH |
| 15 | E ((..)|(.)){2} NULL NOMATCH |
| 16 | E ((..)|(.)){3} NULL NOMATCH |
| 17 | |
| 18 | E ((..)|(.))* NULL (0,0) |
| 19 | |
| 20 | E ((..)|(.)) a (0,1)(0,1)(?,?)(0,1) |
| 21 | E ((..)|(.))((..)|(.)) a NOMATCH |
| 22 | E ((..)|(.))((..)|(.))((..)|(.)) a NOMATCH |
| 23 | |
| 24 | E ((..)|(.)){1} a (0,1)(0,1)(?,?)(0,1) |
| 25 | E ((..)|(.)){2} a NOMATCH |
| 26 | E ((..)|(.)){3} a NOMATCH |
| 27 | |
| 28 | E ((..)|(.))* a (0,1)(0,1)(?,?)(0,1) |
| 29 | |
| 30 | E ((..)|(.)) aa (0,2)(0,2)(0,2)(?,?) |
| 31 | E ((..)|(.))((..)|(.)) aa (0,2)(0,1)(?,?)(0,1)(1,2)(?,?)(1,2) |
| 32 | E ((..)|(.))((..)|(.))((..)|(.)) aa NOMATCH |
| 33 | |
| 34 | E ((..)|(.)){1} aa (0,2)(0,2)(0,2)(?,?) |
| 35 | E ((..)|(.)){2} aa (0,2)(1,2)(?,?)(1,2) |
| 36 | E ((..)|(.)){3} aa NOMATCH |
| 37 | |
| 38 | E ((..)|(.))* aa (0,2)(0,2)(0,2)(?,?) |
| 39 | |
| 40 | E ((..)|(.)) aaa (0,2)(0,2)(0,2)(?,?) |
| 41 | E ((..)|(.))((..)|(.)) aaa (0,3)(0,2)(0,2)(?,?)(2,3)(?,?)(2,3) |
| 42 | E ((..)|(.))((..)|(.))((..)|(.)) aaa (0,3)(0,1)(?,?)(0,1)(1,2)(?,?)(1,2)(2,3)(?,?)(2,3) |
| 43 | |
| 44 | E ((..)|(.)){1} aaa (0,2)(0,2)(0,2)(?,?) |
| 45 | #E ((..)|(.)){2} aaa (0,3)(2,3)(?,?)(2,3) |
| 46 | E ((..)|(.)){2} aaa (0,3)(2,3)(0,2)(2,3) RE2/Go |
| 47 | E ((..)|(.)){3} aaa (0,3)(2,3)(?,?)(2,3) |
| 48 | |
| 49 | #E ((..)|(.))* aaa (0,3)(2,3)(?,?)(2,3) |
| 50 | E ((..)|(.))* aaa (0,3)(2,3)(0,2)(2,3) RE2/Go |
| 51 | |
| 52 | E ((..)|(.)) aaaa (0,2)(0,2)(0,2)(?,?) |
| 53 | E ((..)|(.))((..)|(.)) aaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) |
| 54 | E ((..)|(.))((..)|(.))((..)|(.)) aaaa (0,4)(0,2)(0,2)(?,?)(2,3)(?,?)(2,3)(3,4)(?,?)(3,4) |
| 55 | |
| 56 | E ((..)|(.)){1} aaaa (0,2)(0,2)(0,2)(?,?) |
| 57 | E ((..)|(.)){2} aaaa (0,4)(2,4)(2,4)(?,?) |
| 58 | #E ((..)|(.)){3} aaaa (0,4)(3,4)(?,?)(3,4) |
| 59 | E ((..)|(.)){3} aaaa (0,4)(3,4)(0,2)(3,4) RE2/Go |
| 60 | |
| 61 | E ((..)|(.))* aaaa (0,4)(2,4)(2,4)(?,?) |
| 62 | |
| 63 | E ((..)|(.)) aaaaa (0,2)(0,2)(0,2)(?,?) |
| 64 | E ((..)|(.))((..)|(.)) aaaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) |
| 65 | E ((..)|(.))((..)|(.))((..)|(.)) aaaaa (0,5)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?)(4,5)(?,?)(4,5) |
| 66 | |
| 67 | E ((..)|(.)){1} aaaaa (0,2)(0,2)(0,2)(?,?) |
| 68 | E ((..)|(.)){2} aaaaa (0,4)(2,4)(2,4)(?,?) |
| 69 | #E ((..)|(.)){3} aaaaa (0,5)(4,5)(?,?)(4,5) |
| 70 | E ((..)|(.)){3} aaaaa (0,5)(4,5)(2,4)(4,5) RE2/Go |
| 71 | |
| 72 | #E ((..)|(.))* aaaaa (0,5)(4,5)(?,?)(4,5) |
| 73 | E ((..)|(.))* aaaaa (0,5)(4,5)(2,4)(4,5) RE2/Go |
| 74 | |
| 75 | E ((..)|(.)) aaaaaa (0,2)(0,2)(0,2)(?,?) |
| 76 | E ((..)|(.))((..)|(.)) aaaaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) |
| 77 | E ((..)|(.))((..)|(.))((..)|(.)) aaaaaa (0,6)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?)(4,6)(4,6)(?,?) |
| 78 | |
| 79 | E ((..)|(.)){1} aaaaaa (0,2)(0,2)(0,2)(?,?) |
| 80 | E ((..)|(.)){2} aaaaaa (0,4)(2,4)(2,4)(?,?) |
| 81 | E ((..)|(.)){3} aaaaaa (0,6)(4,6)(4,6)(?,?) |
| 82 | |
| 83 | E ((..)|(.))* aaaaaa (0,6)(4,6)(4,6)(?,?) |
| 84 | |
| 85 | NOTE additional repetition tests graciously provided by Chris Kuklewicz www.haskell.org 2009-02-02 |
| 86 | |
| 87 | # These test a bug in OS X / FreeBSD / NetBSD, and libtree. |
| 88 | # Linux/GLIBC gets the {8,} and {8,8} wrong. |
| 89 | |
| 90 | :HA#100:E X(.?){0,}Y X1234567Y (0,9)(7,8) |
| 91 | :HA#101:E X(.?){1,}Y X1234567Y (0,9)(7,8) |
| 92 | :HA#102:E X(.?){2,}Y X1234567Y (0,9)(7,8) |
| 93 | :HA#103:E X(.?){3,}Y X1234567Y (0,9)(7,8) |
| 94 | :HA#104:E X(.?){4,}Y X1234567Y (0,9)(7,8) |
| 95 | :HA#105:E X(.?){5,}Y X1234567Y (0,9)(7,8) |
| 96 | :HA#106:E X(.?){6,}Y X1234567Y (0,9)(7,8) |
| 97 | :HA#107:E X(.?){7,}Y X1234567Y (0,9)(7,8) |
| 98 | :HA#108:E X(.?){8,}Y X1234567Y (0,9)(8,8) |
| 99 | #:HA#110:E X(.?){0,8}Y X1234567Y (0,9)(7,8) |
| 100 | :HA#110:E X(.?){0,8}Y X1234567Y (0,9)(8,8) RE2/Go |
| 101 | #:HA#111:E X(.?){1,8}Y X1234567Y (0,9)(7,8) |
| 102 | :HA#111:E X(.?){1,8}Y X1234567Y (0,9)(8,8) RE2/Go |
| 103 | #:HA#112:E X(.?){2,8}Y X1234567Y (0,9)(7,8) |
| 104 | :HA#112:E X(.?){2,8}Y X1234567Y (0,9)(8,8) RE2/Go |
| 105 | #:HA#113:E X(.?){3,8}Y X1234567Y (0,9)(7,8) |
| 106 | :HA#113:E X(.?){3,8}Y X1234567Y (0,9)(8,8) RE2/Go |
| 107 | #:HA#114:E X(.?){4,8}Y X1234567Y (0,9)(7,8) |
| 108 | :HA#114:E X(.?){4,8}Y X1234567Y (0,9)(8,8) RE2/Go |
| 109 | #:HA#115:E X(.?){5,8}Y X1234567Y (0,9)(7,8) |
| 110 | :HA#115:E X(.?){5,8}Y X1234567Y (0,9)(8,8) RE2/Go |
| 111 | #:HA#116:E X(.?){6,8}Y X1234567Y (0,9)(7,8) |
| 112 | :HA#116:E X(.?){6,8}Y X1234567Y (0,9)(8,8) RE2/Go |
| 113 | #:HA#117:E X(.?){7,8}Y X1234567Y (0,9)(7,8) |
| 114 | :HA#117:E X(.?){7,8}Y X1234567Y (0,9)(8,8) RE2/Go |
| 115 | :HA#118:E X(.?){8,8}Y X1234567Y (0,9)(8,8) |
| 116 | |
| 117 | # These test a fixed bug in my regex-tdfa that did not keep the expanded |
| 118 | # form properly grouped, so right association did the wrong thing with |
| 119 | # these ambiguous patterns (crafted just to test my code when I became |
| 120 | # suspicious of my implementation). The first subexpression should use |
| 121 | # "ab" then "a" then "bcd". |
| 122 | |
| 123 | # OS X / FreeBSD / NetBSD badly fail many of these, with impossible |
| 124 | # results like (0,6)(4,5)(6,6). |
| 125 | |
| 126 | :HA#260:E (a|ab|c|bcd){0,}(d*) ababcd (0,1)(0,1)(1,1) |
| 127 | :HA#261:E (a|ab|c|bcd){1,}(d*) ababcd (0,1)(0,1)(1,1) |
| 128 | :HA#262:E (a|ab|c|bcd){2,}(d*) ababcd (0,6)(3,6)(6,6) |
| 129 | :HA#263:E (a|ab|c|bcd){3,}(d*) ababcd (0,6)(3,6)(6,6) |
| 130 | :HA#264:E (a|ab|c|bcd){4,}(d*) ababcd NOMATCH |
| 131 | :HA#265:E (a|ab|c|bcd){0,10}(d*) ababcd (0,1)(0,1)(1,1) |
| 132 | :HA#266:E (a|ab|c|bcd){1,10}(d*) ababcd (0,1)(0,1)(1,1) |
| 133 | :HA#267:E (a|ab|c|bcd){2,10}(d*) ababcd (0,6)(3,6)(6,6) |
| 134 | :HA#268:E (a|ab|c|bcd){3,10}(d*) ababcd (0,6)(3,6)(6,6) |
| 135 | :HA#269:E (a|ab|c|bcd){4,10}(d*) ababcd NOMATCH |
| 136 | :HA#270:E (a|ab|c|bcd)*(d*) ababcd (0,1)(0,1)(1,1) |
| 137 | :HA#271:E (a|ab|c|bcd)+(d*) ababcd (0,1)(0,1)(1,1) |
| 138 | |
| 139 | # The above worked on Linux/GLIBC but the following often fail. |
| 140 | # They also trip up OS X / FreeBSD / NetBSD: |
| 141 | |
| 142 | #:HA#280:E (ab|a|c|bcd){0,}(d*) ababcd (0,6)(3,6)(6,6) |
| 143 | :HA#280:E (ab|a|c|bcd){0,}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go |
| 144 | #:HA#281:E (ab|a|c|bcd){1,}(d*) ababcd (0,6)(3,6)(6,6) |
| 145 | :HA#281:E (ab|a|c|bcd){1,}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go |
| 146 | #:HA#282:E (ab|a|c|bcd){2,}(d*) ababcd (0,6)(3,6)(6,6) |
| 147 | :HA#282:E (ab|a|c|bcd){2,}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go |
| 148 | #:HA#283:E (ab|a|c|bcd){3,}(d*) ababcd (0,6)(3,6)(6,6) |
| 149 | :HA#283:E (ab|a|c|bcd){3,}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go |
| 150 | :HA#284:E (ab|a|c|bcd){4,}(d*) ababcd NOMATCH |
| 151 | #:HA#285:E (ab|a|c|bcd){0,10}(d*) ababcd (0,6)(3,6)(6,6) |
| 152 | :HA#285:E (ab|a|c|bcd){0,10}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go |
| 153 | #:HA#286:E (ab|a|c|bcd){1,10}(d*) ababcd (0,6)(3,6)(6,6) |
| 154 | :HA#286:E (ab|a|c|bcd){1,10}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go |
| 155 | #:HA#287:E (ab|a|c|bcd){2,10}(d*) ababcd (0,6)(3,6)(6,6) |
| 156 | :HA#287:E (ab|a|c|bcd){2,10}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go |
| 157 | #:HA#288:E (ab|a|c|bcd){3,10}(d*) ababcd (0,6)(3,6)(6,6) |
| 158 | :HA#288:E (ab|a|c|bcd){3,10}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go |
| 159 | :HA#289:E (ab|a|c|bcd){4,10}(d*) ababcd NOMATCH |
| 160 | #:HA#290:E (ab|a|c|bcd)*(d*) ababcd (0,6)(3,6)(6,6) |
| 161 | :HA#290:E (ab|a|c|bcd)*(d*) ababcd (0,6)(4,5)(5,6) RE2/Go |
| 162 | #:HA#291:E (ab|a|c|bcd)+(d*) ababcd (0,6)(3,6)(6,6) |
| 163 | :HA#291:E (ab|a|c|bcd)+(d*) ababcd (0,6)(4,5)(5,6) RE2/Go |