summaryrefslogtreecommitdiff
path: root/src/pkg/regexp/syntax/parse_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/regexp/syntax/parse_test.go')
-rw-r--r--src/pkg/regexp/syntax/parse_test.go559
1 files changed, 0 insertions, 559 deletions
diff --git a/src/pkg/regexp/syntax/parse_test.go b/src/pkg/regexp/syntax/parse_test.go
deleted file mode 100644
index f3089294c..000000000
--- a/src/pkg/regexp/syntax/parse_test.go
+++ /dev/null
@@ -1,559 +0,0 @@
-// Copyright 2011 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package syntax
-
-import (
- "bytes"
- "fmt"
- "testing"
- "unicode"
-)
-
-type parseTest struct {
- Regexp string
- Dump string
-}
-
-var parseTests = []parseTest{
- // Base cases
- {`a`, `lit{a}`},
- {`a.`, `cat{lit{a}dot{}}`},
- {`a.b`, `cat{lit{a}dot{}lit{b}}`},
- {`ab`, `str{ab}`},
- {`a.b.c`, `cat{lit{a}dot{}lit{b}dot{}lit{c}}`},
- {`abc`, `str{abc}`},
- {`a|^`, `alt{lit{a}bol{}}`},
- {`a|b`, `cc{0x61-0x62}`},
- {`(a)`, `cap{lit{a}}`},
- {`(a)|b`, `alt{cap{lit{a}}lit{b}}`},
- {`a*`, `star{lit{a}}`},
- {`a+`, `plus{lit{a}}`},
- {`a?`, `que{lit{a}}`},
- {`a{2}`, `rep{2,2 lit{a}}`},
- {`a{2,3}`, `rep{2,3 lit{a}}`},
- {`a{2,}`, `rep{2,-1 lit{a}}`},
- {`a*?`, `nstar{lit{a}}`},
- {`a+?`, `nplus{lit{a}}`},
- {`a??`, `nque{lit{a}}`},
- {`a{2}?`, `nrep{2,2 lit{a}}`},
- {`a{2,3}?`, `nrep{2,3 lit{a}}`},
- {`a{2,}?`, `nrep{2,-1 lit{a}}`},
- // Malformed { } are treated as literals.
- {`x{1001`, `str{x{1001}`},
- {`x{9876543210`, `str{x{9876543210}`},
- {`x{9876543210,`, `str{x{9876543210,}`},
- {`x{2,1`, `str{x{2,1}`},
- {`x{1,9876543210`, `str{x{1,9876543210}`},
- {``, `emp{}`},
- {`|`, `emp{}`}, // alt{emp{}emp{}} but got factored
- {`|x|`, `alt{emp{}lit{x}emp{}}`},
- {`.`, `dot{}`},
- {`^`, `bol{}`},
- {`$`, `eol{}`},
- {`\|`, `lit{|}`},
- {`\(`, `lit{(}`},
- {`\)`, `lit{)}`},
- {`\*`, `lit{*}`},
- {`\+`, `lit{+}`},
- {`\?`, `lit{?}`},
- {`{`, `lit{{}`},
- {`}`, `lit{}}`},
- {`\.`, `lit{.}`},
- {`\^`, `lit{^}`},
- {`\$`, `lit{$}`},
- {`\\`, `lit{\}`},
- {`[ace]`, `cc{0x61 0x63 0x65}`},
- {`[abc]`, `cc{0x61-0x63}`},
- {`[a-z]`, `cc{0x61-0x7a}`},
- {`[a]`, `lit{a}`},
- {`\-`, `lit{-}`},
- {`-`, `lit{-}`},
- {`\_`, `lit{_}`},
- {`abc`, `str{abc}`},
- {`abc|def`, `alt{str{abc}str{def}}`},
- {`abc|def|ghi`, `alt{str{abc}str{def}str{ghi}}`},
-
- // Posix and Perl extensions
- {`[[:lower:]]`, `cc{0x61-0x7a}`},
- {`[a-z]`, `cc{0x61-0x7a}`},
- {`[^[:lower:]]`, `cc{0x0-0x60 0x7b-0x10ffff}`},
- {`[[:^lower:]]`, `cc{0x0-0x60 0x7b-0x10ffff}`},
- {`(?i)[[:lower:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
- {`(?i)[a-z]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
- {`(?i)[^[:lower:]]`, `cc{0x0-0x40 0x5b-0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
- {`(?i)[[:^lower:]]`, `cc{0x0-0x40 0x5b-0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
- {`\d`, `cc{0x30-0x39}`},
- {`\D`, `cc{0x0-0x2f 0x3a-0x10ffff}`},
- {`\s`, `cc{0x9-0xa 0xc-0xd 0x20}`},
- {`\S`, `cc{0x0-0x8 0xb 0xe-0x1f 0x21-0x10ffff}`},
- {`\w`, `cc{0x30-0x39 0x41-0x5a 0x5f 0x61-0x7a}`},
- {`\W`, `cc{0x0-0x2f 0x3a-0x40 0x5b-0x5e 0x60 0x7b-0x10ffff}`},
- {`(?i)\w`, `cc{0x30-0x39 0x41-0x5a 0x5f 0x61-0x7a 0x17f 0x212a}`},
- {`(?i)\W`, `cc{0x0-0x2f 0x3a-0x40 0x5b-0x5e 0x60 0x7b-0x17e 0x180-0x2129 0x212b-0x10ffff}`},
- {`[^\\]`, `cc{0x0-0x5b 0x5d-0x10ffff}`},
- // { `\C`, `byte{}` }, // probably never
-
- // Unicode, negatives, and a double negative.
- {`\p{Braille}`, `cc{0x2800-0x28ff}`},
- {`\P{Braille}`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
- {`\p{^Braille}`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
- {`\P{^Braille}`, `cc{0x2800-0x28ff}`},
- {`\pZ`, `cc{0x20 0xa0 0x1680 0x2000-0x200a 0x2028-0x2029 0x202f 0x205f 0x3000}`},
- {`[\p{Braille}]`, `cc{0x2800-0x28ff}`},
- {`[\P{Braille}]`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
- {`[\p{^Braille}]`, `cc{0x0-0x27ff 0x2900-0x10ffff}`},
- {`[\P{^Braille}]`, `cc{0x2800-0x28ff}`},
- {`[\pZ]`, `cc{0x20 0xa0 0x1680 0x2000-0x200a 0x2028-0x2029 0x202f 0x205f 0x3000}`},
- {`\p{Lu}`, mkCharClass(unicode.IsUpper)},
- {`[\p{Lu}]`, mkCharClass(unicode.IsUpper)},
- {`(?i)[\p{Lu}]`, mkCharClass(isUpperFold)},
- {`\p{Any}`, `dot{}`},
- {`\p{^Any}`, `cc{}`},
-
- // Hex, octal.
- {`[\012-\234]\141`, `cat{cc{0xa-0x9c}lit{a}}`},
- {`[\x{41}-\x7a]\x61`, `cat{cc{0x41-0x7a}lit{a}}`},
-
- // More interesting regular expressions.
- {`a{,2}`, `str{a{,2}}`},
- {`\.\^\$\\`, `str{.^$\}`},
- {`[a-zABC]`, `cc{0x41-0x43 0x61-0x7a}`},
- {`[^a]`, `cc{0x0-0x60 0x62-0x10ffff}`},
- {`[α-ε☺]`, `cc{0x3b1-0x3b5 0x263a}`}, // utf-8
- {`a*{`, `cat{star{lit{a}}lit{{}}`},
-
- // Test precedences
- {`(?:ab)*`, `star{str{ab}}`},
- {`(ab)*`, `star{cap{str{ab}}}`},
- {`ab|cd`, `alt{str{ab}str{cd}}`},
- {`a(b|c)d`, `cat{lit{a}cap{cc{0x62-0x63}}lit{d}}`},
-
- // Test flattening.
- {`(?:a)`, `lit{a}`},
- {`(?:ab)(?:cd)`, `str{abcd}`},
- {`(?:a+b+)(?:c+d+)`, `cat{plus{lit{a}}plus{lit{b}}plus{lit{c}}plus{lit{d}}}`},
- {`(?:a+|b+)|(?:c+|d+)`, `alt{plus{lit{a}}plus{lit{b}}plus{lit{c}}plus{lit{d}}}`},
- {`(?:a|b)|(?:c|d)`, `cc{0x61-0x64}`},
- {`a|.`, `dot{}`},
- {`.|a`, `dot{}`},
- {`(?:[abc]|A|Z|hello|world)`, `alt{cc{0x41 0x5a 0x61-0x63}str{hello}str{world}}`},
- {`(?:[abc]|A|Z)`, `cc{0x41 0x5a 0x61-0x63}`},
-
- // Test Perl quoted literals
- {`\Q+|*?{[\E`, `str{+|*?{[}`},
- {`\Q+\E+`, `plus{lit{+}}`},
- {`\Q\\E`, `lit{\}`},
- {`\Q\\\E`, `str{\\}`},
-
- // Test Perl \A and \z
- {`(?m)^`, `bol{}`},
- {`(?m)$`, `eol{}`},
- {`(?-m)^`, `bot{}`},
- {`(?-m)$`, `eot{}`},
- {`(?m)\A`, `bot{}`},
- {`(?m)\z`, `eot{\z}`},
- {`(?-m)\A`, `bot{}`},
- {`(?-m)\z`, `eot{\z}`},
-
- // Test named captures
- {`(?P<name>a)`, `cap{name:lit{a}}`},
-
- // Case-folded literals
- {`[Aa]`, `litfold{A}`},
- {`[\x{100}\x{101}]`, `litfold{Ā}`},
- {`[Δδ]`, `litfold{Δ}`},
-
- // Strings
- {`abcde`, `str{abcde}`},
- {`[Aa][Bb]cd`, `cat{strfold{AB}str{cd}}`},
-
- // Factoring.
- {`abc|abd|aef|bcx|bcy`, `alt{cat{lit{a}alt{cat{lit{b}cc{0x63-0x64}}str{ef}}}cat{str{bc}cc{0x78-0x79}}}`},
- {`ax+y|ax+z|ay+w`, `cat{lit{a}alt{cat{plus{lit{x}}cc{0x79-0x7a}}cat{plus{lit{y}}lit{w}}}}`},
-
- // Bug fixes.
- {`(?:.)`, `dot{}`},
- {`(?:x|(?:xa))`, `cat{lit{x}alt{emp{}lit{a}}}`},
- {`(?:.|(?:.a))`, `cat{dot{}alt{emp{}lit{a}}}`},
- {`(?:A(?:A|a))`, `cat{lit{A}litfold{A}}`},
- {`(?:A|a)`, `litfold{A}`},
- {`A|(?:A|a)`, `litfold{A}`},
- {`(?s).`, `dot{}`},
- {`(?-s).`, `dnl{}`},
- {`(?:(?:^).)`, `cat{bol{}dot{}}`},
- {`(?-s)(?:(?:^).)`, `cat{bol{}dnl{}}`},
-
- // RE2 prefix_tests
- {`abc|abd`, `cat{str{ab}cc{0x63-0x64}}`},
- {`a(?:b)c|abd`, `cat{str{ab}cc{0x63-0x64}}`},
- {`abc|abd|aef|bcx|bcy`,
- `alt{cat{lit{a}alt{cat{lit{b}cc{0x63-0x64}}str{ef}}}` +
- `cat{str{bc}cc{0x78-0x79}}}`},
- {`abc|x|abd`, `alt{str{abc}lit{x}str{abd}}`},
- {`(?i)abc|ABD`, `cat{strfold{AB}cc{0x43-0x44 0x63-0x64}}`},
- {`[ab]c|[ab]d`, `cat{cc{0x61-0x62}cc{0x63-0x64}}`},
- {`(?:xx|yy)c|(?:xx|yy)d`,
- `cat{alt{str{xx}str{yy}}cc{0x63-0x64}}`},
- {`x{2}|x{2}[0-9]`,
- `cat{rep{2,2 lit{x}}alt{emp{}cc{0x30-0x39}}}`},
- {`x{2}y|x{2}[0-9]y`,
- `cat{rep{2,2 lit{x}}alt{lit{y}cat{cc{0x30-0x39}lit{y}}}}`},
-}
-
-const testFlags = MatchNL | PerlX | UnicodeGroups
-
-func TestParseSimple(t *testing.T) {
- testParseDump(t, parseTests, testFlags)
-}
-
-var foldcaseTests = []parseTest{
- {`AbCdE`, `strfold{ABCDE}`},
- {`[Aa]`, `litfold{A}`},
- {`a`, `litfold{A}`},
-
- // 0x17F is an old English long s (looks like an f) and folds to s.
- // 0x212A is the Kelvin symbol and folds to k.
- {`A[F-g]`, `cat{litfold{A}cc{0x41-0x7a 0x17f 0x212a}}`}, // [Aa][A-z...]
- {`[[:upper:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
- {`[[:lower:]]`, `cc{0x41-0x5a 0x61-0x7a 0x17f 0x212a}`},
-}
-
-func TestParseFoldCase(t *testing.T) {
- testParseDump(t, foldcaseTests, FoldCase)
-}
-
-var literalTests = []parseTest{
- {"(|)^$.[*+?]{5,10},\\", "str{(|)^$.[*+?]{5,10},\\}"},
-}
-
-func TestParseLiteral(t *testing.T) {
- testParseDump(t, literalTests, Literal)
-}
-
-var matchnlTests = []parseTest{
- {`.`, `dot{}`},
- {"\n", "lit{\n}"},
- {`[^a]`, `cc{0x0-0x60 0x62-0x10ffff}`},
- {`[a\n]`, `cc{0xa 0x61}`},
-}
-
-func TestParseMatchNL(t *testing.T) {
- testParseDump(t, matchnlTests, MatchNL)
-}
-
-var nomatchnlTests = []parseTest{
- {`.`, `dnl{}`},
- {"\n", "lit{\n}"},
- {`[^a]`, `cc{0x0-0x9 0xb-0x60 0x62-0x10ffff}`},
- {`[a\n]`, `cc{0xa 0x61}`},
-}
-
-func TestParseNoMatchNL(t *testing.T) {
- testParseDump(t, nomatchnlTests, 0)
-}
-
-// Test Parse -> Dump.
-func testParseDump(t *testing.T, tests []parseTest, flags Flags) {
- for _, tt := range tests {
- re, err := Parse(tt.Regexp, flags)
- if err != nil {
- t.Errorf("Parse(%#q): %v", tt.Regexp, err)
- continue
- }
- d := dump(re)
- if d != tt.Dump {
- t.Errorf("Parse(%#q).Dump() = %#q want %#q", tt.Regexp, d, tt.Dump)
- }
- }
-}
-
-// dump prints a string representation of the regexp showing
-// the structure explicitly.
-func dump(re *Regexp) string {
- var b bytes.Buffer
- dumpRegexp(&b, re)
- return b.String()
-}
-
-var opNames = []string{
- OpNoMatch: "no",
- OpEmptyMatch: "emp",
- OpLiteral: "lit",
- OpCharClass: "cc",
- OpAnyCharNotNL: "dnl",
- OpAnyChar: "dot",
- OpBeginLine: "bol",
- OpEndLine: "eol",
- OpBeginText: "bot",
- OpEndText: "eot",
- OpWordBoundary: "wb",
- OpNoWordBoundary: "nwb",
- OpCapture: "cap",
- OpStar: "star",
- OpPlus: "plus",
- OpQuest: "que",
- OpRepeat: "rep",
- OpConcat: "cat",
- OpAlternate: "alt",
-}
-
-// dumpRegexp writes an encoding of the syntax tree for the regexp re to b.
-// It is used during testing to distinguish between parses that might print
-// the same using re's String method.
-func dumpRegexp(b *bytes.Buffer, re *Regexp) {
- if int(re.Op) >= len(opNames) || opNames[re.Op] == "" {
- fmt.Fprintf(b, "op%d", re.Op)
- } else {
- switch re.Op {
- default:
- b.WriteString(opNames[re.Op])
- case OpStar, OpPlus, OpQuest, OpRepeat:
- if re.Flags&NonGreedy != 0 {
- b.WriteByte('n')
- }
- b.WriteString(opNames[re.Op])
- case OpLiteral:
- if len(re.Rune) > 1 {
- b.WriteString("str")
- } else {
- b.WriteString("lit")
- }
- if re.Flags&FoldCase != 0 {
- for _, r := range re.Rune {
- if unicode.SimpleFold(r) != r {
- b.WriteString("fold")
- break
- }
- }
- }
- }
- }
- b.WriteByte('{')
- switch re.Op {
- case OpEndText:
- if re.Flags&WasDollar == 0 {
- b.WriteString(`\z`)
- }
- case OpLiteral:
- for _, r := range re.Rune {
- b.WriteRune(r)
- }
- case OpConcat, OpAlternate:
- for _, sub := range re.Sub {
- dumpRegexp(b, sub)
- }
- case OpStar, OpPlus, OpQuest:
- dumpRegexp(b, re.Sub[0])
- case OpRepeat:
- fmt.Fprintf(b, "%d,%d ", re.Min, re.Max)
- dumpRegexp(b, re.Sub[0])
- case OpCapture:
- if re.Name != "" {
- b.WriteString(re.Name)
- b.WriteByte(':')
- }
- dumpRegexp(b, re.Sub[0])
- case OpCharClass:
- sep := ""
- for i := 0; i < len(re.Rune); i += 2 {
- b.WriteString(sep)
- sep = " "
- lo, hi := re.Rune[i], re.Rune[i+1]
- if lo == hi {
- fmt.Fprintf(b, "%#x", lo)
- } else {
- fmt.Fprintf(b, "%#x-%#x", lo, hi)
- }
- }
- }
- b.WriteByte('}')
-}
-
-func mkCharClass(f func(rune) bool) string {
- re := &Regexp{Op: OpCharClass}
- lo := rune(-1)
- for i := rune(0); i <= unicode.MaxRune; i++ {
- if f(i) {
- if lo < 0 {
- lo = i
- }
- } else {
- if lo >= 0 {
- re.Rune = append(re.Rune, lo, i-1)
- lo = -1
- }
- }
- }
- if lo >= 0 {
- re.Rune = append(re.Rune, lo, unicode.MaxRune)
- }
- return dump(re)
-}
-
-func isUpperFold(r rune) bool {
- if unicode.IsUpper(r) {
- return true
- }
- c := unicode.SimpleFold(r)
- for c != r {
- if unicode.IsUpper(c) {
- return true
- }
- c = unicode.SimpleFold(c)
- }
- return false
-}
-
-func TestFoldConstants(t *testing.T) {
- last := rune(-1)
- for i := rune(0); i <= unicode.MaxRune; i++ {
- if unicode.SimpleFold(i) == i {
- continue
- }
- if last == -1 && minFold != i {
- t.Errorf("minFold=%#U should be %#U", minFold, i)
- }
- last = i
- }
- if maxFold != last {
- t.Errorf("maxFold=%#U should be %#U", maxFold, last)
- }
-}
-
-func TestAppendRangeCollapse(t *testing.T) {
- // AppendRange should collapse each of the new ranges
- // into the earlier ones (it looks back two ranges), so that
- // the slice never grows very large.
- // Note that we are not calling cleanClass.
- var r []rune
- for i := rune('A'); i <= 'Z'; i++ {
- r = appendRange(r, i, i)
- r = appendRange(r, i+'a'-'A', i+'a'-'A')
- }
- if string(r) != "AZaz" {
- t.Errorf("appendRange interlaced A-Z a-z = %s, want AZaz", string(r))
- }
-}
-
-var invalidRegexps = []string{
- `(`,
- `)`,
- `(a`,
- `a)`,
- `(a))`,
- `(a|b|`,
- `a|b|)`,
- `(a|b|))`,
- `(a|b`,
- `a|b)`,
- `(a|b))`,
- `[a-z`,
- `([a-z)`,
- `[a-z)`,
- `([a-z]))`,
- `x{1001}`,
- `x{9876543210}`,
- `x{2,1}`,
- `x{1,9876543210}`,
- "\xff", // Invalid UTF-8
- "[\xff]",
- "[\\\xff]",
- "\\\xff",
- `(?P<name>a`,
- `(?P<name>`,
- `(?P<name`,
- `(?P<x y>a)`,
- `(?P<>a)`,
- `[a-Z]`,
- `(?i)[a-Z]`,
- `a{100000}`,
- `a{100000,}`,
-}
-
-var onlyPerl = []string{
- `[a-b-c]`,
- `\Qabc\E`,
- `\Q*+?{[\E`,
- `\Q\\E`,
- `\Q\\\E`,
- `\Q\\\\E`,
- `\Q\\\\\E`,
- `(?:a)`,
- `(?P<name>a)`,
-}
-
-var onlyPOSIX = []string{
- "a++",
- "a**",
- "a?*",
- "a+*",
- "a{1}*",
- ".{1}{2}.{3}",
-}
-
-func TestParseInvalidRegexps(t *testing.T) {
- for _, regexp := range invalidRegexps {
- if re, err := Parse(regexp, Perl); err == nil {
- t.Errorf("Parse(%#q, Perl) = %s, should have failed", regexp, dump(re))
- }
- if re, err := Parse(regexp, POSIX); err == nil {
- t.Errorf("Parse(%#q, POSIX) = %s, should have failed", regexp, dump(re))
- }
- }
- for _, regexp := range onlyPerl {
- if _, err := Parse(regexp, Perl); err != nil {
- t.Errorf("Parse(%#q, Perl): %v", regexp, err)
- }
- if re, err := Parse(regexp, POSIX); err == nil {
- t.Errorf("Parse(%#q, POSIX) = %s, should have failed", regexp, dump(re))
- }
- }
- for _, regexp := range onlyPOSIX {
- if re, err := Parse(regexp, Perl); err == nil {
- t.Errorf("Parse(%#q, Perl) = %s, should have failed", regexp, dump(re))
- }
- if _, err := Parse(regexp, POSIX); err != nil {
- t.Errorf("Parse(%#q, POSIX): %v", regexp, err)
- }
- }
-}
-
-func TestToStringEquivalentParse(t *testing.T) {
- for _, tt := range parseTests {
- re, err := Parse(tt.Regexp, testFlags)
- if err != nil {
- t.Errorf("Parse(%#q): %v", tt.Regexp, err)
- continue
- }
- d := dump(re)
- if d != tt.Dump {
- t.Errorf("Parse(%#q).Dump() = %#q want %#q", tt.Regexp, d, tt.Dump)
- continue
- }
-
- s := re.String()
- if s != tt.Regexp {
- // If ToString didn't return the original regexp,
- // it must have found one with fewer parens.
- // Unfortunately we can't check the length here, because
- // ToString produces "\\{" for a literal brace,
- // but "{" is a shorter equivalent in some contexts.
- nre, err := Parse(s, testFlags)
- if err != nil {
- t.Errorf("Parse(%#q.String() = %#q): %v", tt.Regexp, s, err)
- continue
- }
- nd := dump(nre)
- if d != nd {
- t.Errorf("Parse(%#q) -> %#q; %#q vs %#q", tt.Regexp, s, d, nd)
- }
-
- ns := nre.String()
- if s != ns {
- t.Errorf("Parse(%#q) -> %#q -> %#q", tt.Regexp, s, ns)
- }
- }
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-29 18:30:21 +0000