package syntax

import (
	"testing"
)

// patterns that should produce the same trees
func TestIdenticalTreePatterns(t *testing.T) {

	scenarios := []struct{ a, b string }{
		// Two greedy one loops
		{"a*a*", "a*"},
		{"(a*a*)", "(a*)"},
		{"a*(?:a*)", "a*"},
		{"a*a+", "a+"},
		{"a*a?", "a*"},
		{"a*a{1,3}", "a+"},
		{"a+a*", "a+"},
		{"a+a+", "a{2,}"},
		{"a+a?", "a+"},
		{"a+a{1,3}", "a{2,}"},
		{"a?a*", "a*"},
		{"a?a+", "a+"},
		{"a?a?", "a{0,2}"},
		{"a?a{1,3}", "a{1,4}"},
		{"a{1,3}a*", "a+"},
		{"a{1,3}a+", "a{2,}"},
		{"a{1,3}a?", "a{1,4}"},
		{"a{1,3}a{1,3}", "a{2,6}"},
		// Greedy one loop and one
		{"a*a", "a+"},
		{"a+a", "a{2,}"},
		{"a?a", "a{1,2}"},
		{"a{1,3}a", "a{2,4}"},
		{"aa*", "a+"},
		{"aa+", "a{2,}"},
		{"aa?", "a{1,2}"},
		{"aa{1,3}", "a{2,4}"},
		{"aaa+b", "aa(?>a+)b"},
		{"a+aab", "(?>a{3,})b"},
		{"a{3}b", "aaab"},
		{"a{2}ab", "aaab"},
		{"aa{2}b", "aaab"},
		{"ca{3}b", "caaab"},
		{"caa{2}b", "caaab"},
		{"ca{2}ab", "caaab"},
		{"ca{2}", "caa"},
		{`ca{2}\w`, `caa\w`},
		// Two atomic one loops
		{"(?>a*)(?>a*)", "(?>a*)"},
		{"(?>a*)(?>(?:a*))", "(?>a*)"},
		{"(?>a*)(?>a?)", "(?>a*)"},
		{"(?>a+)(?>a*)", "(?>a+)"},
		{"(?>a+)(?>a?)", "(?>a+)"},
		{"(?>a?)(?>a*)", "(?>a*)"},
		{"(?>a?)(?>a?)", "(?>a{0,2})"},
		{"(?>a{1,3})(?>a*)", "(?>a+)"},
		{"(?>a{1,3})(?>a?)", "(?>a{1,4})"},
		// One and atomic one loop
		{"a(?>a*)", "(?>a+)"},
		{"a(?>a+)", "(?>a{2,})"},
		{"a(?>a?)", "(?>a{1,2})"},
		{"a(?>a{1,3})", "(?>a{2,4})"},
		// Two lazy one loops
		{"a*?a*?", "a*?"},
		{"a*?a+?", "a+?"},
		{"a*?a??", "a*?"},
		{"a*?a{1,3}?", "a+?"},
		{"a+?a*?", "a+?"},
		{"a+?a+?", "a{2,}?"},
		{"a+?a??", "a+?"},
		{"a+?a{1,3}?", "a{2,}?"},
		{"a??a*?", "a*?"},
		{"a??a+?", "a+?"},
		{"a??a??", "a{0,2}?"},
		{"a??a{1,3}?", "a{1,4}?"},
		{"a{1,3}?a*?", "a+?"},
		{"a{1,3}?a+?", "a{2,}?"},
		{"a{1,3}?a??", "a{1,4}?"},
		{"a{1,3}?a{1,3}?", "a{2,6}?"},
		// Lazy one loop and one
		{"a*?a", "a+?"},
		{"a+?a", "a{2,}?"},
		{"a??a", "a{1,2}?"},
		{"a{1,3}?a", "a{2,4}?"},
		{"aa*?", "a+?"},
		{"aa+?", "a{2,}?"},
		{"aa??", "a{1,2}?"},
		{"aa{1,3}?", "a{2,4}?"},
		// Two greedy notone loops
		{"[^a]*[^a]*", "[^a]*"},
		{"[^a]*[^a]+", "[^a]+"},
		{"[^a]*[^a]?", "[^a]*"},
		{"[^a]*[^a]{1,3}", "[^a]+"},
		{"[^a]+[^a]*", "[^a]+"},
		{"[^a]+[^a]+", "[^a]{2,}"},
		{"[^a]+[^a]?", "[^a]+"},
		{"[^a]+[^a]{1,3}", "[^a]{2,}"},
		{"[^a]?[^a]*", "[^a]*"},
		{"[^a]?[^a]+", "[^a]+"},
		{"[^a]?[^a]?", "[^a]{0,2}"},
		{"[^a]?[^a]{1,3}", "[^a]{1,4}"},
		{"[^a]{1,3}[^a]*", "[^a]+"},
		{"[^a]{1,3}[^a]+", "[^a]{2,}"},
		{"[^a]{1,3}[^a]?", "[^a]{1,4}"},
		{"[^a]{1,3}[^a]{1,3}", "[^a]{2,6}"},
		// Two lazy notone loops
		{"[^a]*?[^a]*?", "[^a]*?"},
		{"[^a]*?[^a]+?", "[^a]+?"},
		{"[^a]*?[^a]??", "[^a]*?"},
		{"[^a]*?[^a]{1,3}?", "[^a]+?"},
		{"[^a]+?[^a]*?", "[^a]+?"},
		{"[^a]+?[^a]+?", "[^a]{2,}?"},
		{"[^a]+?[^a]??", "[^a]+?"},
		{"[^a]+?[^a]{1,3}?", "[^a]{2,}?"},
		{"[^a]??[^a]*?", "[^a]*?"},
		{"[^a]??[^a]+?", "[^a]+?"},
		{"[^a]??[^a]??", "[^a]{0,2}?"},
		{"[^a]??[^a]{1,3}?", "[^a]{1,4}?"},
		{"[^a]{1,3}?[^a]*?", "[^a]+?"},
		{"[^a]{1,3}?[^a]+?", "[^a]{2,}?"},
		{"[^a]{1,3}?[^a]??", "[^a]{1,4}?"},
		{"[^a]{1,3}?[^a]{1,3}?", "[^a]{2,6}?"},
		// Two atomic notone loops
		{"(?>[^a]*)(?>[^a]*)", "(?>[^a]*)"},
		{"(?>[^a]*)(?>[^a]?)", "(?>[^a]*)"},
		{"(?>[^a]+)(?>[^a]*)", "(?>[^a]+)"},
		{"(?>[^a]+)(?>[^a]?)", "(?>[^a]+)"},
		{"(?>[^a]?)(?>[^a]*)", "(?>[^a]*)"},
		{"(?>[^a]?)(?>[^a]?)", "(?>[^a]{0,2})"},
		{"(?>[^a]{1,3})(?>[^a]*)", "(?>[^a]+)"},
		{"(?>[^a]{1,3})(?>[^a]?)", "(?>[^a]{1,4})"},
		// Greedy notone loop and notone
		{"[^a]*[^a]", "[^a]+"},
		{"[^a]+[^a]", "[^a]{2,}"},
		{"[^a]?[^a]", "[^a]{1,2}"},
		{"[^a]{1,3}[^a]", "[^a]{2,4}"},
		{"[^a][^a]*", "[^a]+"},
		{"[^a][^a]+", "[^a]{2,}"},
		{"[^a][^a]?", "[^a]{1,2}"},
		{"[^a][^a]{1,3}", "[^a]{2,4}"},
		// Lazy notone loop and notone
		{"[^a]*?[^a]", "[^a]+?"},
		{"[^a]+?[^a]", "[^a]{2,}?"},
		{"[^a]??[^a]", "[^a]{1,2}?"},
		{"[^a]{1,3}?[^a]", "[^a]{2,4}?"},
		{"[^a][^a]*?", "[^a]+?"},
		{"[^a][^a]+?", "[^a]{2,}?"},
		{"[^a][^a]??", "[^a]{1,2}?"},
		{"[^a][^a]{1,3}?", "[^a]{2,4}?"},
		// Notone and atomic notone loop
		{"[^a](?>[^a]*)", "(?>[^a]+)"},
		{"[^a](?>[^a]+)", "(?>[^a]{2,})"},
		{"[^a](?>[^a]?)", "(?>[^a]{1,2})"},
		{"[^a](?>[^a]{1,3})", "(?>[^a]{2,4})"},
		// Notone and notone
		{"[^a][^a]", "[^a]{2}"},
		// Two greedy set loops
		{"[0-9]*[0-9]*", "[0-9]*"},
		{"[0-9]*[0-9]+", "[0-9]+"},
		{"[0-9]*[0-9]?", "[0-9]*"},
		{"[0-9]*[0-9]{1,3}", "[0-9]+"},
		{"[0-9]+[0-9]*", "[0-9]+"},
		{"[0-9]+[0-9]+", "[0-9]{2,}"},
		{"[0-9]+[0-9]?", "[0-9]+"},
		{"[0-9]+[0-9]{1,3}", "[0-9]{2,}"},
		{"[0-9]?[0-9]*", "[0-9]*"},
		{"[0-9]?[0-9]+", "[0-9]+"},
		{"[0-9]?[0-9]?", "[0-9]{0,2}"},
		{"[0-9]?[0-9]{1,3}", "[0-9]{1,4}"},
		{"[0-9]{1,3}[0-9]*", "[0-9]+"},
		{"[0-9]{1,3}[0-9]+", "[0-9]{2,}"},
		{"[0-9]{1,3}[0-9]?", "[0-9]{1,4}"},
		{"[0-9]{1,3}[0-9]{1,3}", "[0-9]{2,6}"},
		// Greedy set loop and set
		{"[0-9]*[0-9]", "[0-9]+"},
		{"[0-9]+[0-9]", "[0-9]{2,}"},
		{"[0-9]?[0-9]", "[0-9]{1,2}"},
		{"[0-9]{1,3}[0-9]", "[0-9]{2,4}"},
		{"[0-9][0-9]*", "[0-9]+"},
		{"[0-9][0-9]+", "[0-9]{2,}"},
		{"[0-9][0-9]?", "[0-9]{1,2}"},
		{"[0-9][0-9]{1,3}", "[0-9]{2,4}"},
		// Set and atomic set loop
		{"[0-9](?>[0-9]*)", "(?>[0-9]+)"},
		{"[0-9](?>[0-9]+)", "(?>[0-9]{2,})"},
		{"[0-9](?>[0-9]?)", "(?>[0-9]{1,2})"},
		{"[0-9](?>[0-9]{1,3})", "(?>[0-9]{2,4})"},
		// Two lazy set loops
		{"[0-9]*?[0-9]*?", "[0-9]*?"},
		{"[0-9]*?[0-9]+?", "[0-9]+?"},
		{"[0-9]*?[0-9]??", "[0-9]*?"},
		{"[0-9]*?[0-9]{1,3}?", "[0-9]+?"},
		{"[0-9]+?[0-9]*?", "[0-9]+?"},
		{"[0-9]+?[0-9]+?", "[0-9]{2,}?"},
		{"[0-9]+?[0-9]??", "[0-9]+?"},
		{"[0-9]+?[0-9]{1,3}?", "[0-9]{2,}?"},
		{"[0-9]??[0-9]*?", "[0-9]*?"},
		{"[0-9]??[0-9]+?", "[0-9]+?"},
		{"[0-9]??[0-9]??", "[0-9]{0,2}?"},
		{"[0-9]??[0-9]{1,3}?", "[0-9]{1,4}?"},
		{"[0-9]{1,3}?[0-9]*?", "[0-9]+?"},
		{"[0-9]{1,3}?[0-9]+?", "[0-9]{2,}?"},
		{"[0-9]{1,3}?[0-9]??", "[0-9]{1,4}?"},
		{"[0-9]{1,3}?[0-9]{1,3}?", "[0-9]{2,6}?"},
		// Two atomic set loops
		{"(?>[0-9]*)(?>[0-9]*)", "(?>[0-9]*)"},
		{"(?>[0-9]*)(?>[0-9]?)", "(?>[0-9]*)"},
		{"(?>[0-9]+)(?>[0-9]*)", "(?>[0-9]+)"},
		{"(?>[0-9]+)(?>[0-9]?)", "(?>[0-9]+)"},
		{"(?>[0-9]?)(?>[0-9]*)", "(?>[0-9]*)"},
		{"(?>[0-9]?)(?>[0-9]?)", "(?>[0-9]{0,2})"},
		{"(?>[0-9]{1,3})(?>[0-9]*)", "(?>[0-9]+)"},
		{"(?>[0-9]{1,3})(?>[0-9]?)", "(?>[0-9]{1,4})"},
		// Lazy set loop and set
		{"[0-9]*?[0-9]", "[0-9]+?"},
		{"[0-9]+?[0-9]", "[0-9]{2,}?"},
		{"[0-9]??[0-9]", "[0-9]{1,2}?"},
		{"[0-9]{1,3}?[0-9]", "[0-9]{2,4}?"},
		{"[0-9][0-9]*?", "[0-9]+?"},
		{"[0-9][0-9]+?", "[0-9]{2,}?"},
		{"[0-9][0-9]??", "[0-9]{1,2}?"},
		{"[0-9][0-9]{1,3}?", "[0-9]{2,4}?"},
		// Set and set
		{"[ace][ace]", "[ace]{2}"},
		// Set and one
		{"[a]", "a"},
		{"[a]*", "a*"},
		{"(?>[a]*)", "(?>a*)"},
		{"[a]*?", "a*?"},
		// Set and notone
		{"[^\n]", "."},
		{"[^\n]*", ".*"},
		{"(?>[^\n]*)", "(?>.*)"},
		{"[^\n]*?", ".*?"},
		// Set reduction
		{"[\u0001-\U0010FFFF]", "[^\u0000]"},
		{"[\u0000-\U0010FFFE]", "[^\U0010FFFF]"},
		{"[\u0000-AB-\uFFFF]", "[\u0000-\uFFFF]"},
		{"[ABC-EG-J]", "[A-EG-J]"},
		{"[\u0000-AC-\U0010FFFF]", "[^B]"},
		{"[\u0000-AF-\U0010FFFF]", "[^B-E]"},
		// Large loop patterns
		{"a*a*a*a*a*a*a*b*b*?a+a*", "a*b*b*?a+"},
		{"a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", "a{0,30}aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"},
		// Group elimination
		{"(?:(?:(?:(?:(?:(?:a*))))))", "a*"},
		// Nested loops
		{"(?:a*)*", "a*"},
		{"(?:a*)+", "a*"},
		{"(?:a+){4}", "a{4,}"},
		{"(?:a{1,2}){4}", "a{4,8}"},
		// Nested atomic
		{"(?>(?>(?>(?>abc*))))", "(?>ab(?>c*))"},
		{"(?>(?>(?>(?>))))", ""},
		{"(?>(?>(?>(?>(?!)))))", "(?!)"},
		{"(?=(?>))", ""},
		// Alternation reduction
		{"a|b", "[ab]"},
		{"a|b|c|d|e|g|h|z", "[a-eghz]"},
		{"a|b|c|def|g|h", "(?>[a-c]|def|[gh])"},
		{"this|that|there|then|those", "th(?>is|at|ere|en|ose)"},
		{"it's (?>this|that|there|then|those)", "it's (?>th(?>is|at|e(?>re|n)|ose))"},
		{"it's (?>this|that|there|then|those)!", "it's (?>th(?>is|at|e(?>re|n)|ose))!"},
		{"abcd|abce", "abc[de]"},
		{"abcd|abef", "ab(?>cd|ef)"},
		{"abcd|aefg", "a(?>bcd|efg)"},
		{"abcd|abc|ab|a", "a(?>bcd|bc|b|)"},
		// {"abcde|abcdef", "abcde(?>|f)"}, // TODO https://github.com/dotnet/runtime/issues/66031: Need to reorganize optimizations to avoid an extra Empty being left at the end of the tree
		{"abcdef|abcde", "abcde(?>f|)"},
		{"abcdef|abcdeg|abcdeh|abcdei|abcdej|abcdek|abcdel", "abcde[f-l]"},
		{"(ab|ab*)bc", "(a(?:b|b*))bc"},
		{"abc(?:defgh|defij)klmn", "abcdef(?:gh|ij)klmn"},
		{"abc(defgh|defij)klmn", "abc(def(?:gh|ij))klmn"},
		{"a[b-f]|a[g-k]", "a[b-k]"},
		{"this|this", "this"},
		{"this|this|this", "this"},
		{"hello there|hello again|hello|hello|hello|hello", "hello(?> there| again|)"},
		{"hello there|hello again|hello|hello|hello|hello|hello world", "hello(?> there| again|)"},
		{"hello there|hello again|hello|hello|hello|hello|hello world|hello", "hello(?> there| again|)"},
		{"ab|cd|||ef", "ab|cd|"},
		{"|ab|cd|e||f", ""},
		{"ab|cd|||||||||||ef", "ab|cd|"},
		{"ab|cd|||||||||||e||f|||", "ab|cd|"},
		{"ab|cd|(?!)|ef", "ab|cd|ef"},
		{"abcd(?:(?i:e)|(?i:f))", "abcd(?i:[ef])"},
		{"(?i:abcde)|(?i:abcdf)", "(?i:abcd[ef])"},
		{"xyz(?:(?i:abcde)|(?i:abcdf))", "xyz(?i:abcd[ef])"},
		{"bonjour|hej|ciao|shalom|zdravo|pozdrav|hallo|hola|hello|hey|witam|tere|bonjou|salam|helo|sawubona", "(?>bonjou(?>r|)|h(?>e(?>j|(?>l(?>lo|o)|y))|allo|ola)|ciao|s(?>halom|a(?>lam|wubona))|zdravo|pozdrav|witam|tere)"},
		{"\\w\\d123|\\w\\dabc", "\\w\\d(?:123|abc)"},
		{"(a)(?(1)b)", "(a)(?(1)b|)"},
		{"(abc)(?(1)def)", "(abc)(?(1)def|)"},
		{"(?(a)a)", "(?(a)a|)"},
		{"(?(abc)def)", "(?(abc)def|)"},
		{"(?(\\w)\\d)", "(?(\\w)\\d|)"},
		// Loops inside alternation constructs
		{"(abc*|def)ghi", "(ab(?>c*)|def)ghi"},
		{"(abc|def*)ghi", "(abc|de(?>f*))ghi"},
		{"(abc*|def*)ghi", "(ab(?>c*)|de(?>f*))ghi"},
		{"(abc*|def*)", "(ab(?>c*)|de(?>f*))"},
		{"(?(\\w)abc*|def*)ghi", "(?(\\w)ab(?>c*)|de(?>f*))ghi"},
		{"(?(\\w)abc*|def*)", "(?(\\w)ab(?>c*)|de(?>f*))"},
		{"(?(xyz*)abc|def)", "(?(xy(?>z*))abc|def)"},
		{"(?(xyz*)abc|def)\\w", "(?(xy(?>z*))abc|def)\\w"},
		// Loops followed by alternation constructs
		{"a*(bcd|efg)", "(?>a*)(bcd|efg)"},
		{"a*(?(xyz)bcd|efg)", "(?>a*)(?(xyz)bcd|efg)"},
		// Auto-atomicity
		{"a*b", "(?>a*)b"},
		{"a*b+", "(?>a*)(?>b+)"},
		{"a*b*", "(?>a*)(?>b*)"},
		{"a*b+c*", "(?>a*)(?>b+)(?>c*)"},
		{"a*b*c*", "(?>a*)(?>b*)(?>c*)"},
		{"a*b*c*|d*[ef]*", "(?>a*)(?>b*)(?>c*)|(?>d*)(?>[ef]*)"},
		{"(a*)(b*)(c*)", "((?>a*))((?>b*))((?>c*))"},
		{"a*b{3,4}", "(?>a*)(?>b{3,4})"},
		{"[ab]*[^a]*", "[ab]*(?>[^a]*)"},
		{"[aa]*[^a]*", "(?>a*)(?>[^a]*)"},
		{"a??", ""},
		{"ab?c", "a(?>b?)c"},
		{"ab??c", "a(?>b?)c"},
		{"ab{2}?c", "abbc"},
		{"ab{2,3}?c", "a(?>b{2,3})c"},
		// {"(abc*?)", "(ab)"}, // TODO https://github.com/dotnet/runtime/issues/66031: Need to reorganize optimizations to avoid an extra Empty being left at the end of the tree
		{"a{1,3}?", "a{1,4}?"},
		{"a{2,3}?", "a{2}"},
		{"bc(a){1,3}?", "bc(a){1,2}?"},
		{"c{3,}?|f{2,}?", "c{3}|f{2}"},
		{"[a-z]*[\x0000-\xFFFF]+", "[a-z]*(?>[\x0000-\xFFFF]+)"},
		{"a+b", "(?>a+)b"},
		{"a?b", "(?>a?)b"},
		{"[^\n]*\n", "(?>[^\n]*)\n"},
		{"[^\n]*\n+", "(?>[^\n]*)(?>\n+)"},
		{"(a+)b", "((?>a+))b"},
		{"a*(?:bcd|efg)", "(?>a*)(?:bcd|efg)"},
		{"\\w+\\b", "(?>\\w+)\\b"},
		{"\\d+\\b", "(?>\\d+)\\b"},
		{"\\W+\\B", "(?>\\W+)\\B"},
		{"\\D+\\B", "(?>\\D+)\\B"},
		{"(?:abc*|def*)g", "(?:ab(?>c*)|de(?>f*))g"},
		{"(?:a[ce]*|b*)g", "(?:a(?>[ce]*)|(?>b*))g"},
		{"(?:a[ce]*|b*)c", "(?:a[ce]*|(?>b*))c"},
		{"apple|(?:orange|pear)|grape", "apple|orange|pear|grape"},
		{"(?:abc)*", "(?>(?>(?>(?:abc)*)))"},
		{"(?:w*)+", "(?>(?>w*)+)"},
		{"(?:w*)+\\.", "(?>w*)+\\."},
		{"(a[bcd]e*)*fg", "(a[bcd](?>e*))*fg"},
		{"(\\w[bcd]\\s*)*fg", "(\\w[bcd](?>\\s*))*fg"},
		{`\b(\w+)\b`, `\b((?>\w+))\b`},
		{`\b(?:\w+)\b `, `\b(?>\w+)\b `},
		// Nothing handling
		{`\wabc(?!)def`, "(?!)"},
		{`\wabc(?!)def|ghi(?!)`, "(?!)"},
		// IgnoreCase set creation
		{"(?i)abcd", "[Aa][Bb][Cc][Dd]"},
		{"(?i)abcd|efgh", "[Aa][Bb][Cc][Dd]|[Ee][Ff][Gg][Hh]"},
		{"(?i)a|b", "[AaBb]"},
		{"(?i)[abcd]", "[AaBbCcDd]"},
		{"(?i)[acexyz]", "[AaCcEeXxYyZz]"},
		{"(?i)\\w", "\\w"},
		{"(?i)\\d", "\\d"},
		{"(?i).", "."},
		{"(?i)\\$", "\\$"}}

	for _, s := range scenarios {
		t.Run(s.a, func(t *testing.T) {
			//parse our two strings into trees, debug dump them, expecting equal
			treeA, err := Parse(s.a, ParseOptions{})
			if err != nil {
				t.Fatalf("failed to parse %s: %v", s.a, err)
			}
			treeB, err := Parse(s.b, ParseOptions{})
			if err != nil {
				t.Fatalf("failed to parse %s: %v", s.b, err)
			}
			got := treeA.Dump()
			want := treeB.Dump()

			if want != got {
				t.Errorf("Pattern %#v and %#v\nWant:\n%s\nGot:\n%s", s.a, s.b, want, got)
			}
		})
	}
}

func TestNonMatchingTreePatterns(t *testing.T) {
	scenarios := []struct{ a, b string }{
		// Not coalescing loops
		{"a[^a]", "a{2}"},
		{"[^a]a", "[^a]{2}"},
		{"a*b*", "a*"},
		{"a*b*", "b*"},
		{"[^a]*[^b]", "[^a]*"},
		{"[ace]*[acd]", "[ace]*"},
		{"a+b+", "a+"},
		{"a+b+", "b+"},
		{"a*(a*)", "a*"},
		{"(a*)a*", "a*"},
		{"a*(?>a*)", "a*"},
		{"a*a*?", "a*"},
		{"a*?a*", "a*"},
		{"a*[^a]*", "a*"},
		{"[^a]*a*", "a*"},
		{"(?>a*)(?>a+)", "(?>a+)"},
		{"(?>a*)(?>a{1,3})", "(?>a+)"},
		{"(?>a+)(?>a+)", "(?>a{2,})"},
		{"(?>a+)(?>a{1,3})", "(?>a{2,})"},
		{"(?>a?)(?>a+)", "(?>a+)"},
		{"(?>a?)(?>a{1,3})", "(?>a{1,4})"},
		{"(?>a{1,3})(?>a+)", "(?>a{2,})"},
		{"(?>a{1,3})(?>a{1,3})", "(?>a{2,6})"},
		{"(?>[^a]*)(?>[^a]+)", "(?>[^a]+)"},
		{"(?>[^a]*)(?>[^a]{1,3})", "(?>[^a]+)"},
		{"(?>[^a]+)(?>[^a]+)", "(?>[^a]{2,})"},
		{"(?>[^a]+)(?>[^a]{1,3})", "(?>[^a]{2,})"},
		{"(?>[^a]?)(?>[^a]+)", "(?>[^a]+)"},
		{"(?>[^a]?)(?>[^a]{1,3})", "(?>[^a]{1,4})"},
		{"(?>[^a]{1,3})(?>[^a]+)", "(?>[^a]{2,})"},
		{"(?>[^a]{1,3})(?>[^a]{1,3})", "(?>[^a]{2,6})"},
		{"(?>[0-9]*)(?>[0-9]+)", "(?>[0-9]+)"},
		{"(?>[0-9]*)(?>[0-9]{1,3})", "(?>[0-9]+)"},
		{"(?>[0-9]+)(?>[0-9]+)", "(?>[0-9]{2,})"},
		{"(?>[0-9]+)(?>[0-9]{1,3})", "(?>[0-9]{2,})"},
		{"(?>[0-9]?)(?>[0-9]+)", "(?>[0-9]+)"},
		{"(?>[0-9]?)(?>[0-9]{1,3})", "(?>[0-9]{1,4})"},
		{"(?>[0-9]{1,3})(?>[0-9]+)", "(?>[0-9]{2,})"},
		{"(?>[0-9]{1,3})(?>[0-9]{1,3})", "(?>[0-9]{2,6})"},
		{"(?>a*)a", "(?>a+)"},
		{"(?>a+)a", "(?>a{2,})"},
		{"(?>a?)a", "(?>a{1,2})"},
		{"(?>a{1,3})a", "(?>a{2,4})"},
		{"(?>[^a]*)[^a]", "(?>[^a]+)"},
		{"(?>[^a]+)[^a]", "(?>[^a]{2,})"},
		{"(?>[^a]?)[^a]", "(?>[^a]{1,2})"},
		{"(?>[^a]{1,3})[^a]", "(?>[^a]{2,4})"},
		{"(?>[0-9]*)[0-9]", "(?>[0-9]+)"},
		{"(?>[0-9]+)[0-9]", "(?>[0-9]{2,})"},
		{"(?>[0-9]?)[0-9]", "(?>[0-9]{1,2})"},
		{"(?>[0-9]{1,3})[0-9]", "(?>[0-9]{2,4})"},
		{"a{2147483646}a", "a{2147483647}"},
		{"a{2147483647}a", "a{2147483647}"},
		{"a{0,2147483646}a", "a{0,2147483647}"},
		{"aa{2147483646}", "a{2147483647}"},
		{"aa{0,2147483646}", "a{0,2147483647}"},
		{"a{2147482647}a{1000}", "a{2147483647}"},
		{"a{0,2147482647}a{0,1000}", "a{0,2147483647}"},
		{"[^a]{2147483646}[^a]", "[^a]{2147483647}"},
		{"[^a]{2147483647}[^a]", "[^a]{2147483647}"},
		{"[^a]{0,2147483646}[^a]", "[^a]{0,2147483647}"},
		{"[^a][^a]{2147483646}", "[^a]{2147483647}"},
		{"[^a][^a]{0,2147483646}", "[^a]{0,2147483647}"},
		{"[^a]{2147482647}[^a]{1000}", "[^a]{2147483647}"},
		{"[^a]{0,2147482647}[^a]{0,1000}", "[^a]{0,2147483647}"},
		{"[ace]{2147483646}[ace]", "[ace]{2147483647}"},
		{"[ace]{2147483647}[ace]", "[ace]{2147483647}"},
		{"[ace]{0,2147483646}[ace]", "[ace]{0,2147483647}"},
		{"[ace][ace]{2147483646}", "[ace]{2147483647}"},
		{"[ace][ace]{0,2147483646}", "[ace]{0,2147483647}"},
		{"[ace]{2147482647}[ace]{1000}", "[ace]{2147483647}"},
		{"[ace]{0,2147482647}[ace]{0,1000}", "[ace]{0,2147483647}"},
		// Not reducing branches of alternations with different casing
		{"(?i:abcd)|abcd", "abcd|abcd"},
		{"abcd|(?i:abcd)", "abcd|abcd"},
		// Not applying auto-atomicity
		{"(a*|b*)\\w*", "((?>a*)|(?>b*))\\w*"},
		{"[ab]*[^a]", "(?>[ab]*)[^a]"},
		{"[ab]*[^a]*", "(?>[ab]*)[^a]*"},
		{"[ab]*[^a]*?", "(?>[ab]*)[^a]*?"},
		{"[ab]*(?>[^a]*)", "(?>[ab]*)(?>[^a]*)"},
		{"[^\n]*\n*", "(?>[^\n]*)\n"},
		{"(a[bcd]a*)*fg", "(a[bcd](?>a*))*fg"},
		{"(\\w[bcd]\\d*)*fg", "(\\w[bcd](?>\\d*))*fg"},
		{"a*(?<=[^a])b", "(?>a*)(?<=[^a])b"},
		{"[\x0000-\xFFFF]*[a-z]", "(?>[\x0000-\xFFFF]*)[a-z]"},
		{"[a-z]*[\x0000-\xFFFF]+", "(?>[a-z]*)[\x0000-\xFFFF]+"},
		{"[^a-c]*[e-g]", "(?>[^a-c]*)[e-g]"},
		{"[^a-c]*[^e-g]", "(?>[^a-c]*)[^e-g]"},
		{"(w+)+", "((?>w+))+"},
		{"(w{1,2})+", "((?>w{1,2}))+"},
		{"(?:ab|cd|ae)f", "(?>ab|cd|ae)f"},
		{"ab?(b)", "a(?>b?)(b)"},
		{"ab??c?", "a(?>b??)c?"},
		{"ab{2,3}?c?", "a(?>b{2,3}?)c?"},
		{"(?:ab??){2}", "(?:a(?>b??)){2}"},
		{"(?:ab??){2, 3}", "(?:a(?>b??)){2, 3}"},
		{"ab??(b)", "a(?>b??)(b)"},
		{`\w+\b\w+`, `(?>\w+)\b\w`},
		{`\w*\b\w+`, `(?>\w*)\b\w+`},
		{`\W+\B\W+`, `(?>\W+)\B\W`},
		{`\W*\B\W+`, `(?>\W*)\B\W`},
		{`a?\b`, `(?>a?)\b`},
		{`\w*\b`, `(?>\w*)\b`},
		{`\d*\b`, `(?>\d*)\b`},
		{`\W*\B`, `(?>\W*)\B`},
		{`\D*\B`, `(?>\D*)\B`},
		// Loops inside alternation constructs
		{"(abc*|def)chi", "(ab(?>c*)|def)chi"},
		{"(abc|def*)fhi", "(abc|de(?>f*))fhi"},
		{"(abc*|def*)\\whi", "(ab(?>c*)|de(?>f*))\\whi"},
		{"(?(\\w)abc*|def*)\\whi", "(?(\\w)ab(?>c*)|de(?>f*))\\whi"},
		// Loops followed by alternation constructs
		{"a*(bcd|afg)", "(?>a*)(bcd|afg)"},
		{"(a*)(?(1)bcd|efg)", "((?>a*))(?(1)bcd|efg)"},
		{"a*(?(abc)bcd|efg)", "(?>a*)(?(abc)bcd|efg)"},
		{"a*(?(xyz)acd|efg)", "(?>a*)(?(xyz)acd|efg)"},
		{"a*(?(xyz)bcd|afg)", "(?>a*)(?(xyz)bcd|afg)"},
		{"a*(?(xyz)bcd)", "(?>a*)(?(xyz)bcd)"},
	}

	for _, s := range scenarios {
		t.Run(s.a, func(t *testing.T) {
			//parse our two strings into trees, debug dump them, expecting equal
			treeA, err := Parse(s.a, ParseOptions{})
			if err != nil {
				t.Fatalf("failed to parse %s: %v", s.a, err)
			}
			treeB, err := Parse(s.b, ParseOptions{})
			if err != nil {
				t.Fatalf("failed to parse %s: %v", s.b, err)
			}
			got := treeA.Dump()
			dontWant := treeB.Dump()

			if dontWant == got {
				t.Errorf("For Pattern %s, Didn't Want: %s\n%s", s.a, s.b, got)
			}
		})
	}
}