Bug 48100 - YARR allows what seems like a bogus character-class range
authorbarraclough@apple.com <barraclough@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 29 Nov 2010 18:52:16 +0000 (18:52 +0000)
committerbarraclough@apple.com <barraclough@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 29 Nov 2010 18:52:16 +0000 (18:52 +0000)
Reviewed by Sam Weinig.

JavaScriptCore:

Per ECMA-262 character classes containing character ranges containing
character classes are invalid, eg:
    /[\d-x]/
    /[x-\d]/
    /[\d-\d]/
These should throw a syntax error.

* yarr/RegexParser.h:

LayoutTests:

Add/update layout test results.

* fast/js/regexp-overflow-expected.txt:
* fast/js/regexp-ranges-and-escaped-hyphens-expected.txt:
* fast/js/script-tests/regexp-overflow.js:
* fast/js/script-tests/regexp-ranges-and-escaped-hyphens.js:
* fast/regex/invalid-range-in-class-expected.txt: Added.
* fast/regex/invalid-range-in-class.html: Added.
* fast/regex/script-tests/invalid-range-in-class.js: Added.
* fast/regex/test1-expected.txt:
* fast/regex/test4-expected.txt:
* fast/regex/testinput4:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@72813 268f45cc-cd09-0410-ab3c-d52691b4dbfc

13 files changed:
JavaScriptCore/ChangeLog
JavaScriptCore/yarr/RegexParser.h
LayoutTests/ChangeLog
LayoutTests/fast/js/regexp-overflow-expected.txt
LayoutTests/fast/js/regexp-ranges-and-escaped-hyphens-expected.txt
LayoutTests/fast/js/script-tests/regexp-overflow.js
LayoutTests/fast/js/script-tests/regexp-ranges-and-escaped-hyphens.js
LayoutTests/fast/regex/invalid-range-in-class-expected.txt [new file with mode: 0644]
LayoutTests/fast/regex/invalid-range-in-class.html [new file with mode: 0644]
LayoutTests/fast/regex/script-tests/invalid-range-in-class.js [new file with mode: 0644]
LayoutTests/fast/regex/test1-expected.txt
LayoutTests/fast/regex/test4-expected.txt
LayoutTests/fast/regex/testinput4

index f5176f2..81e1ce6 100644 (file)
@@ -1,3 +1,18 @@
+2010-11-28  Gavin Barraclough  <barraclough@apple.com>
+
+        Reviewed by Sam Weinig.
+
+        Bug 48100 - YARR allows what seems like a bogus character-class range
+
+        Per ECMA-262 character classes containing character ranges containing
+        character classes are invalid, eg:
+            /[\d-x]/
+            /[x-\d]/
+            /[\d-\d]/
+        These should throw a syntax error.
+
+        * yarr/RegexParser.h:
+
 2010-11-27  Gavin Barraclough  <barraclough@apple.com>
 
         Reviewed by Sam Weinig.
index a5c0ba2..f964be4 100644 (file)
@@ -56,6 +56,7 @@ private:
         ParenthesesUnmatched,
         ParenthesesTypeInvalid,
         CharacterClassUnmatched,
+        CharacterClassInvalidRange,
         CharacterClassOutOfOrder,
         EscapeUnterminated,
         NumberOfErrorCodes
@@ -75,7 +76,7 @@ private:
         CharacterClassParserDelegate(Delegate& delegate, ErrorCode& err)
             : m_delegate(delegate)
             , m_err(err)
-            , m_state(empty)
+            , m_state(Empty)
         {
         }
 
@@ -90,54 +91,60 @@ private:
         }
 
         /*
-         * atomPatternCharacterUnescaped():
+         * atomPatternCharacter():
          *
-         * This method is called directly from parseCharacterClass(), to report a new
-         * pattern character token.  This method differs from atomPatternCharacter(),
-         * which will be called from parseEscape(), since a hypen provided via this
-         * method may be indicating a character range, but a hyphen parsed by
-         * parseEscape() cannot be interpreted as doing so.
+         * This method is called either from parseCharacterClass() (for an unescaped
+         * character in a character class), or from parseEscape(). In the former case
+         * the value true will be passed for the argument 'hyphenIsRange', and in this
+         * mode we will allow a hypen to be treated as indicating a range (i.e. /[a-z]/
+         * is different to /[a\-z]/).
          */
-        void atomPatternCharacterUnescaped(UChar ch)
+        void atomPatternCharacter(UChar ch, bool hyphenIsRange = false)
         {
             switch (m_state) {
-            case empty:
+            case AfterCharacterClass:
+                // Following a builtin character class we need look out for a hyphen.
+                // We're looking for invalid ranges, such as /[\d-x]/ or /[\d-\d]/.
+                // If we see a hyphen following a charater class then unlike usual
+                // we'll report it to the delegate immediately, and put ourself into
+                // a poisoned state. Any following calls to add another character or
+                // character class will result in an error. (A hypen following a
+                // character-class is itself valid, but only  at the end of a regex).
+                if (hyphenIsRange && ch == '-') {
+                    m_delegate.atomCharacterClassAtom('-');
+                    m_state = AfterCharacterClassHyphen;
+                    return;
+                }
+                // Otherwise just fall through - cached character so treat this as Empty.
+
+            case Empty:
                 m_character = ch;
-                m_state = cachedCharacter;
-                break;
+                m_state = CachedCharacter;
+                return;
 
-            case cachedCharacter:
-                if (ch == '-')
-                    m_state = cachedCharacterHyphen;
+            case CachedCharacter:
+                if (hyphenIsRange && ch == '-')
+                    m_state = CachedCharacterHyphen;
                 else {
                     m_delegate.atomCharacterClassAtom(m_character);
                     m_character = ch;
                 }
-                break;
+                return;
 
-            case cachedCharacterHyphen:
-                if (ch >= m_character)
-                    m_delegate.atomCharacterClassRange(m_character, ch);
-                else
+            case CachedCharacterHyphen:
+                if (ch < m_character) {
                     m_err = CharacterClassOutOfOrder;
-                m_state = empty;
-            }
-        }
-
-        /*
-         * atomPatternCharacter():
-         *
-         * Adds a pattern character, called by parseEscape(), as such will not
-         * interpret a hyphen as indicating a character range.
-         */
-        void atomPatternCharacter(UChar ch)
-        {
-            // Flush if a character is already pending to prevent the
-            // hyphen from begin interpreted as indicating a range.
-            if((ch == '-') && (m_state == cachedCharacter))
-                flush();
+                    return;
+                }
+                m_delegate.atomCharacterClassRange(m_character, ch);
+                m_state = Empty;
+                return;
 
-            atomPatternCharacterUnescaped(ch);
+            case AfterCharacterClassHyphen:
+                // Error! We have something like /[\d-x]/.
+                m_err = CharacterClassInvalidRange;
+                return;
+            }
         }
 
         /*
@@ -147,8 +154,25 @@ private:
          */
         void atomBuiltInCharacterClass(BuiltInCharacterClassID classID, bool invert)
         {
-            flush();
-            m_delegate.atomCharacterClassBuiltIn(classID, invert);
+            switch (m_state) {
+            case CachedCharacter:
+                // Flush the currently cached character, then fall through.
+                m_delegate.atomCharacterClassAtom(m_character);
+
+            case Empty:
+            case AfterCharacterClass:
+                m_state = AfterCharacterClass;
+                m_delegate.atomCharacterClassBuiltIn(classID, invert);
+                return;
+
+            case CachedCharacterHyphen:
+            case AfterCharacterClassHyphen:
+                // Error! If we hit either of these cases, we have an
+                // invalid range that looks something like /[x-\d]/
+                // or /[\d-\d]/.
+                m_err = CharacterClassInvalidRange;
+                return;
+            }
         }
 
         /*
@@ -158,7 +182,12 @@ private:
          */
         void end()
         {
-            flush();
+            if (m_state == CachedCharacter)
+                m_delegate.atomCharacterClassAtom(m_character);
+            else if (m_state == CachedCharacterHyphen) {
+                m_delegate.atomCharacterClassAtom(m_character);
+                m_delegate.atomCharacterClassAtom('-');
+            }
             m_delegate.atomCharacterClassEnd();
         }
 
@@ -168,21 +197,14 @@ private:
         void atomBackReference(unsigned) { ASSERT_NOT_REACHED(); }
 
     private:
-        void flush()
-        {
-            if (m_state != empty) // either cachedCharacter or cachedCharacterHyphen
-                m_delegate.atomCharacterClassAtom(m_character);
-            if (m_state == cachedCharacterHyphen)
-                m_delegate.atomCharacterClassAtom('-');
-            m_state = empty;
-        }
-    
         Delegate& m_delegate;
         ErrorCode& m_err;
         enum CharacterClassConstructionState {
-            empty,
-            cachedCharacter,
-            cachedCharacterHyphen,
+            Empty,
+            CachedCharacter,
+            CachedCharacterHyphen,
+            AfterCharacterClass,
+            AfterCharacterClassHyphen,
         } m_state;
         UChar m_character;
     };
@@ -428,7 +450,7 @@ private:
                 break;
 
             default:
-                characterClassConstructor.atomPatternCharacterUnescaped(consume());
+                characterClassConstructor.atomPatternCharacter(consume(), true);
             }
 
             if (m_err)
@@ -657,6 +679,7 @@ private:
             "unmatched parentheses",
             "unrecognized character after (?",
             "missing terminating ] for character class",
+            "invalid range in character class",
             "range out of order in character class",
             "\\ at end of pattern"
         };
index 39daaa9..e901674 100644 (file)
@@ -1,3 +1,22 @@
+2010-11-28  Gavin Barraclough  <barraclough@apple.com>
+
+        Reviewed by Sam Weinig.
+
+        Bug 48100 - YARR allows what seems like a bogus character-class range
+
+        Add/update layout test results.
+
+        * fast/js/regexp-overflow-expected.txt:
+        * fast/js/regexp-ranges-and-escaped-hyphens-expected.txt:
+        * fast/js/script-tests/regexp-overflow.js:
+        * fast/js/script-tests/regexp-ranges-and-escaped-hyphens.js:
+        * fast/regex/invalid-range-in-class-expected.txt: Added.
+        * fast/regex/invalid-range-in-class.html: Added.
+        * fast/regex/script-tests/invalid-range-in-class.js: Added.
+        * fast/regex/test1-expected.txt:
+        * fast/regex/test4-expected.txt:
+        * fast/regex/testinput4:
+
 2010-11-24  Dimitri Glazkov  <dglazkov@chromium.org>
 
         Reviewed by Darin Adler.
index e30b0e8..335c60b 100644 (file)
@@ -10,7 +10,7 @@ PASS /\[["'\s]{0,1}([\w-]*)["'\s]{0,1}([\W]{0,1}=){0,2}["'\s]{0,1}([\w-]*)["'\s]
 PASS /(x){0,2}/.exec("").toString() is ","
 PASS /[¡]{4,6}/.exec("¡¡¡¡").toString() is "¡¡¡¡"
 PASS /[¡]{1,100}[¡]{1,100}[¡]{1,100}[¡]{1,100}[¡]{1,100}[¡]{1,100}[¡]{1,100}[¡]{1,100}/.exec("¡¡¡¡¡¡¡¡").toString() is "¡¡¡¡¡¡¡¡"
-PASS /{([\D-\ca]]„£µ+?)}|[[\B-\u00d4]√π- ]]]{0,3}/i.exec("B√π- ]]").toString() is "B√π- ]],"
+PASS /{([\D\-\ca]]„£µ+?)}|[[\B-\u00d4]√π- ]]]{0,3}/i.exec("B√π- ]]").toString() is "B√π- ]],"
 PASS /|[x\B-\u00b5]/i.exec("").toString() is ""
 PASS new RegExp(complexPattern).exec(complexInput)[0] is complexInput
 PASS new RegExp(s); threw exception SyntaxError: Invalid regular expression: regular expression too large.
index 3aa8084..795b5fb 100644 (file)
@@ -5,8 +5,8 @@ On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE
 
 PASS regexp01.toString() is "1235"
 PASS regexp01a.toString() is "123 5"
-PASS regexp01b.toString() is "1-3 5"
-PASS regexp01c.toString() is "1-3 5"
+PASS /[1\s-35]+/.exec("21-3 54"); threw exception SyntaxError: Invalid regular expression: invalid range in character class.
+PASS /[1-\s35]+/.exec("21-3 54"); threw exception SyntaxError: Invalid regular expression: invalid range in character class.
 PASS regexp01d.toString() is "123 5"
 PASS regexp01e.toString() is "123 5"
 PASS regexp01f.toString() is "-3"
index d3edc6f..dc6735f 100644 (file)
@@ -17,7 +17,7 @@ shouldBe('/(x){0,2}/.exec("").toString()', '","');
 shouldBe('/[\u00A1]{4,6}/.exec("\u00A1\u00A1\u00A1\u00A1").toString()', '"\u00A1\u00A1\u00A1\u00A1"');
 shouldBe('/[\u00A1]{1,100}[\u00A1]{1,100}[\u00A1]{1,100}[\u00A1]{1,100}[\u00A1]{1,100}[\u00A1]{1,100}[\u00A1]{1,100}[\u00A1]{1,100}/.exec("\u00A1\u00A1\u00A1\u00A1\u00A1\u00A1\u00A1\u00A1").toString()', '"\u00A1\u00A1\u00A1\u00A1\u00A1\u00A1\u00A1\u00A1"');
 
-shouldBe('/{([\\D-\\ca]]„£µ+?)}|[[\\B-\\u00d4]√π- ]]]{0,3}/i.exec("B√π- ]]").toString()', '"B√π- ]],"');
+shouldBe('/{([\\D\\-\\ca]]„£µ+?)}|[[\\B-\\u00d4]√π- ]]]{0,3}/i.exec("B√π- ]]").toString()', '"B√π- ]],"');
 shouldBe('/|[x\\B-\\u00b5]/i.exec("").toString()', '""');
 
 var complexPattern = "";
index fcac6ec..3a3e35d 100644 (file)
@@ -9,10 +9,11 @@ shouldBe('regexp01.toString()', '"1235"');
 // range it is no longer a range - hyphens should now match, two should not.
 var regexp01a = /[\s1-35]+/.exec("-123 54");
 shouldBe('regexp01a.toString()', '"123 5"');
-var regexp01b = /[1\s-35]+/.exec("21-3 54");
-shouldBe('regexp01b.toString()', '"1-3 5"');
-var regexp01c = /[1-\s35]+/.exec("21-3 54"); // This was a cricial case; the '-' m_isPendingDash wasn't being reset properly, causing the '35' to be treated like a range '3-5'.
-shouldBe('regexp01c.toString()', '"1-3 5"');
+
+// These are invalid ranges.
+shouldThrow('/[1\\s-35]+/.exec("21-3 54");');
+shouldThrow('/[1-\\s35]+/.exec("21-3 54");');
+
 var regexp01d = /[1-3\s5]+/.exec("-123 54");
 shouldBe('regexp01d.toString()', '"123 5"');
 var regexp01e = /[1-35\s5]+/.exec("-123 54");
diff --git a/LayoutTests/fast/regex/invalid-range-in-class-expected.txt b/LayoutTests/fast/regex/invalid-range-in-class-expected.txt
new file mode 100644 (file)
index 0000000..99c036b
--- /dev/null
@@ -0,0 +1,19 @@
+This page tests invalid character ranges in character classes.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS /[a-c]+/.exec("-acbd"); is ["acb"]
+PASS /[a\-c]+/.exec("-acbd") is ["-ac"]
+PASS /[c-a]+/.exec("-acbd"); threw exception SyntaxError: Invalid regular expression: range out of order in character class.
+PASS /[\d-x]+/.exec("1-3xy"); threw exception SyntaxError: Invalid regular expression: invalid range in character class.
+PASS /[x-\d]+/.exec("1-3xy"); threw exception SyntaxError: Invalid regular expression: invalid range in character class.
+PASS /[\d-\d]+/.exec("1-3xy"); threw exception SyntaxError: Invalid regular expression: invalid range in character class.
+PASS /[\d\-x]+/.exec("1-3xy"); is ["1-3x"]
+PASS /[x\-\d]+/.exec("1-3xy"); is ["1-3x"]
+PASS /[\d\-\d]+/.exec("1-3xy"); is ["1-3"]
+PASS /[\d-]+/.exec("1-3xy") is ["1-3"]
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/regex/invalid-range-in-class.html b/LayoutTests/fast/regex/invalid-range-in-class.html
new file mode 100644 (file)
index 0000000..8550422
--- /dev/null
@@ -0,0 +1,13 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="../js/resources/js-test-style.css">
+<script src="../js/resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="script-tests/invalid-range-in-class.js"></script>
+<script src="../js/resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/fast/regex/script-tests/invalid-range-in-class.js b/LayoutTests/fast/regex/script-tests/invalid-range-in-class.js
new file mode 100644 (file)
index 0000000..e440f35
--- /dev/null
@@ -0,0 +1,25 @@
+description(
+"This page tests invalid character ranges in character classes."
+);
+
+// These test a basic range / non range.
+shouldBe('/[a-c]+/.exec("-acbd");', '["acb"]');
+shouldBe('/[a\\-c]+/.exec("-acbd")', '["-ac"]');
+
+// A reverse-range is invalid.
+shouldThrow('/[c-a]+/.exec("-acbd");');
+
+// A character-class in a range is invalid.
+shouldThrow('/[\\d-x]+/.exec("1-3xy");');
+shouldThrow('/[x-\\d]+/.exec("1-3xy");');
+shouldThrow('/[\\d-\\d]+/.exec("1-3xy");');
+
+// An escaped hypen should not be confused for an invalid range.
+shouldBe('/[\\d\\-x]+/.exec("1-3xy");', '["1-3x"]');
+shouldBe('/[x\\-\\d]+/.exec("1-3xy");', '["1-3x"]');
+shouldBe('/[\\d\\-\\d]+/.exec("1-3xy");', '["1-3"]');
+
+// A hyphen after a character-class is not invalid.
+shouldBe('/[\\d-]+/.exec("1-3xy")', '["1-3"]');
+
+var successfullyParsed = true;
index 2d95ad9..88cd1d1 100644 (file)
@@ -617,9 +617,7 @@ FAILED TO COMPILE
     aaa: PASS
 
 /[\d-z]+/
-    12-34z: PASS
-    *** Failers
-    aaa: PASS
+FAILED TO COMPILE
 
 /\x5c/
 FAILED TO COMPILE
@@ -2598,18 +2596,10 @@ FAILED TO COMPILE
     abbab: PASS
 
 /^[a-\d]/
-    abcde: PASS
-    -things: PASS
-    0digit: PASS
-    *** Failers
-    bcdef: PASS
+FAILED TO COMPILE
 
 /^[\d-a]/
-    abcde: PASS
-    -things: PASS
-    0digit: PASS
-    *** Failers
-    bcdef: PASS
+FAILED TO COMPILE
 
 /[[:space:]]+/
     >  
index 01517fc..2b39479 100644 (file)
Binary files a/LayoutTests/fast/regex/test4-expected.txt and b/LayoutTests/fast/regex/test4-expected.txt differ
index c98c085..d31d19a 100644 (file)
 /[[:^xdigit:]]/8g
     M\x{442}
 
-/[^ABCDEFGHIJKLMNOPQRSTUVWXYZÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖØÙÚÛÜÝÞĀĂĄĆĈĊČĎĐĒĔĖĘĚĜĞĠĢĤĦĨĪĬĮİIJĴĶĹĻĽĿŁŃŅŇŊŌŎŐŒŔŖŘŚŜŞŠŢŤŦŨŪŬŮŰŲŴŶŸŹŻŽƁƂƄƆƇƉƊƋƎƏƐƑƓƔƖƗƘƜƝƟƠƢƤƦƧƩƬƮƯƱƲƳƵƷƸƼDŽLJNJǍǏǑǓǕǗǙǛǞǠǢǤǦǨǪǬǮDZǴǶǷǸǺǼǾȀȂȄȆȈȊȌȎȐȒȔȖȘȚȜȞȠȢȤȦȨȪȬȮȰȲȺȻȽȾɁΆΈΉΊΌΎΏΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΪΫϒϓϔϘϚϜϞϠϢϤϦϨϪϬϮϴϷϹϺϽϾϿЀЁЂЃЄЅІЇЈЉЊЋЌЍЎЏАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯѠѢѤѦѨѪѬѮѰѲѴѶѸѺѼѾҀҊҌҎҐҒҔҖҘҚҜҞҠҢҤҦҨҪҬҮҰҲҴҶҸҺҼҾӀӁӃӅӇӉӋӍӐӒӔӖӘӚӜӞӠӢӤӦӨӪӬӮӰӲӴӶӸԀԂԄԆԈԊԌԎԱԲԳԴԵԶԷԸԹԺԻԼԽԾԿՀՁՂՃՄՅՆՇՈՉՊՋՌՍՎՏՐՑՒՓՔՕՖႠႡႢႣႤႥႦႧႨႩႪႫႬႭႮႯႰႱႲႳႴႵႶႷႸႹႺႻႼႽႾႿჀჁჂჃჄჅḀḂḄḆḈḊḌḎḐḒḔḖḘḚḜḞḠḢḤḦḨḪḬḮḰḲḴḶḸḺḼḾṀṂṄṆṈṊṌṎṐṒṔṖṘṚṜṞṠṢṤṦṨṪṬṮṰṲṴṶṸṺṼṾẀẂẄẆẈẊẌẎẐẒẔẠẢẤẦẨẪẬẮẰẲẴẶẸẺẼẾỀỂỄỆỈỊỌỎỐỒỔỖỘỚỜỞỠỢỤỦỨỪỬỮỰỲỴỶỸἈἉἊἋἌἍἎἏἘἙἚἛἜἝἨἩἪἫἬἭἮἯἸἹἺἻἼἽἾἿὈὉὊὋὌὍὙὛὝὟὨὩὪὫὬὭὮὯᾸᾹᾺΆῈΈῊΉῘῙῚΊῨῩῪΎῬῸΌῺΏabcdefghijklmnopqrstuvwxyzªµºßàáâãäåæçèéêëìíîïðñòóôõöøùúûüýþÿāăąćĉċčďđēĕėęěĝğġģĥħĩīĭįıijĵķĸĺļľŀłńņňʼnŋōŏőœŕŗřśŝşšţťŧũūŭůűųŵŷźżžſƀƃƅƈƌƍƒƕƙƚƛƞơƣƥƨƪƫƭưƴƶƹƺƽƾƿdžljnjǎǐǒǔǖǘǚǜǝǟǡǣǥǧǩǫǭǯǰdzǵǹǻǽǿȁȃȅȇȉȋȍȏȑȓȕȗșțȝȟȡȣȥȧȩȫȭȯȱȳȴȵȶȷȸȹȼȿɀɐɑɒɓɔɕɖɗɘəɚɛɜɝɞɟɠɡɢɣɤɥɦɧɨɩɪɫɬɭɮɯɰɱɲɳɴɵɶɷɸɹɺɻɼɽɾɿʀʁʂʃʄʅʆʇʈʉʊʋʌʍʎʏʐʑʒʓʔʕʖʗʘʙʚʛʜʝʞʟʠʡʢʣʤʥʦʧʨʩʪʫʬʭʮʯΐάέήίΰαβγδεζηθικλμνξοπρςστυφχψωϊϋόύώϐϑϕϖϗϙϛϝϟϡϣϥϧϩϫϭϯϰϱϲϳϵϸϻϼабвгдежзийклмнопрстуфхцчшщъыьэюяѐёђѓєѕіїјљњћќѝўџѡѣѥѧѩѫѭѯѱѳѵѷѹѻѽѿҁҋҍҏґғҕҗҙқҝҟҡңҥҧҩҫҭүұҳҵҷҹһҽҿӂӄӆӈӊӌӎӑӓӕӗәӛӝӟӡӣӥӧөӫӭӯӱӳӵӷӹԁԃԅԇԉԋԍԏաբգդեզէըթժիլխծկհձղճմյնշոչպջռսվտրցւփքօֆևᴀᴁᴂᴃᴄᴅᴆᴇᴈᴉᴊᴋᴌᴍᴎᴏᴐᴑᴒᴓᴔᴕᴖᴗᴘᴙᴚᴛᴜᴝᴞᴟᴠᴡᴢᴣᴤᴥᴦᴧᴨᴩᴪᴫᵢᵣᵤᵥᵦᵧᵨᵩᵪᵫᵬᵭᵮᵯᵰᵱᵲᵳᵴᵵᵶᵷᵹᵺᵻᵼᵽᵾᵿᶀᶁᶂᶃᶄᶅᶆᶇᶈᶉᶊᶋᶌᶍᶎᶏᶐᶑᶒᶓᶔᶕᶖᶗᶘᶙᶚḁḃḅḇḉḋḍḏḑḓḕḗḙḛḝḟḡḣḥḧḩḫḭḯḱḳḵḷḹḻḽḿṁṃṅṇṉṋṍṏṑṓṕṗṙṛṝṟṡṣṥṧṩṫṭṯṱṳṵṷṹṻṽṿẁẃẅẇẉẋẍẏẑẓẕẖẗẘẙẚẛạảấầẩẫậắằẳẵặẹẻẽếềểễệỉịọỏốồổỗộớờởỡợụủứừửữựỳỵỷỹἀἁἂἃἄἅἆἇἐἑἒἓἔἕἠἡἢἣἤἥἦἧἰἱἲἳἴἵἶἷὀὁὂὃὄὅὐὑὒὓὔὕὖὗὠὡὢὣὤὥὦὧὰάὲέὴήὶίὸόὺύὼώᾀᾁᾂᾃᾄᾅᾆᾇᾐᾑᾒᾓᾔᾕᾖᾗᾠᾡᾢᾣᾤᾥᾦᾧᾰᾱᾲᾳᾴᾶᾷιῂῃῄῆῇῐῑῒΐῖῗῠῡῢΰῤῥῦῧῲῳῴῶῷⲁⲃⲅⲇⲉⲋⲍⲏⲑⲓⲕⲗⲙⲛⲝⲟⲡⲣⲥⲧⲩⲫⲭⲯⲱⲳⲵⲷⲹⲻⲽⲿⳁⳃⳅⳇⳉⳋⳍⳏⳑⳓⳕⳗⳙⳛⳝⳟⳡⳣⳤⴀⴁⴂⴃⴄⴅⴆⴇⴈⴉⴊⴋⴌⴍⴎⴏⴐⴑⴒⴓⴔⴕⴖⴗⴘⴙⴚⴛⴜⴝⴞⴟⴠⴡⴢⴣⴤⴥfffiflffifflſtstﬓﬔﬕﬖﬗ\d-_^]/8
+/[^ABCDEFGHIJKLMNOPQRSTUVWXYZÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖØÙÚÛÜÝÞĀĂĄĆĈĊČĎĐĒĔĖĘĚĜĞĠĢĤĦĨĪĬĮİIJĴĶĹĻĽĿŁŃŅŇŊŌŎŐŒŔŖŘŚŜŞŠŢŤŦŨŪŬŮŰŲŴŶŸŹŻŽƁƂƄƆƇƉƊƋƎƏƐƑƓƔƖƗƘƜƝƟƠƢƤƦƧƩƬƮƯƱƲƳƵƷƸƼDŽLJNJǍǏǑǓǕǗǙǛǞǠǢǤǦǨǪǬǮDZǴǶǷǸǺǼǾȀȂȄȆȈȊȌȎȐȒȔȖȘȚȜȞȠȢȤȦȨȪȬȮȰȲȺȻȽȾɁΆΈΉΊΌΎΏΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩΪΫϒϓϔϘϚϜϞϠϢϤϦϨϪϬϮϴϷϹϺϽϾϿЀЁЂЃЄЅІЇЈЉЊЋЌЍЎЏАБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯѠѢѤѦѨѪѬѮѰѲѴѶѸѺѼѾҀҊҌҎҐҒҔҖҘҚҜҞҠҢҤҦҨҪҬҮҰҲҴҶҸҺҼҾӀӁӃӅӇӉӋӍӐӒӔӖӘӚӜӞӠӢӤӦӨӪӬӮӰӲӴӶӸԀԂԄԆԈԊԌԎԱԲԳԴԵԶԷԸԹԺԻԼԽԾԿՀՁՂՃՄՅՆՇՈՉՊՋՌՍՎՏՐՑՒՓՔՕՖႠႡႢႣႤႥႦႧႨႩႪႫႬႭႮႯႰႱႲႳႴႵႶႷႸႹႺႻႼႽႾႿჀჁჂჃჄჅḀḂḄḆḈḊḌḎḐḒḔḖḘḚḜḞḠḢḤḦḨḪḬḮḰḲḴḶḸḺḼḾṀṂṄṆṈṊṌṎṐṒṔṖṘṚṜṞṠṢṤṦṨṪṬṮṰṲṴṶṸṺṼṾẀẂẄẆẈẊẌẎẐẒẔẠẢẤẦẨẪẬẮẰẲẴẶẸẺẼẾỀỂỄỆỈỊỌỎỐỒỔỖỘỚỜỞỠỢỤỦỨỪỬỮỰỲỴỶỸἈἉἊἋἌἍἎἏἘἙἚἛἜἝἨἩἪἫἬἭἮἯἸἹἺἻἼἽἾἿὈὉὊὋὌὍὙὛὝὟὨὩὪὫὬὭὮὯᾸᾹᾺΆῈΈῊΉῘῙῚΊῨῩῪΎῬῸΌῺΏabcdefghijklmnopqrstuvwxyzªµºßàáâãäåæçèéêëìíîïðñòóôõöøùúûüýþÿāăąćĉċčďđēĕėęěĝğġģĥħĩīĭįıijĵķĸĺļľŀłńņňʼnŋōŏőœŕŗřśŝşšţťŧũūŭůűųŵŷźżžſƀƃƅƈƌƍƒƕƙƚƛƞơƣƥƨƪƫƭưƴƶƹƺƽƾƿdžljnjǎǐǒǔǖǘǚǜǝǟǡǣǥǧǩǫǭǯǰdzǵǹǻǽǿȁȃȅȇȉȋȍȏȑȓȕȗșțȝȟȡȣȥȧȩȫȭȯȱȳȴȵȶȷȸȹȼȿɀɐɑɒɓɔɕɖɗɘəɚɛɜɝɞɟɠɡɢɣɤɥɦɧɨɩɪɫɬɭɮɯɰɱɲɳɴɵɶɷɸɹɺɻɼɽɾɿʀʁʂʃʄʅʆʇʈʉʊʋʌʍʎʏʐʑʒʓʔʕʖʗʘʙʚʛʜʝʞʟʠʡʢʣʤʥʦʧʨʩʪʫʬʭʮʯΐάέήίΰαβγδεζηθικλμνξοπρςστυφχψωϊϋόύώϐϑϕϖϗϙϛϝϟϡϣϥϧϩϫϭϯϰϱϲϳϵϸϻϼабвгдежзийклмнопрстуфхцчшщъыьэюяѐёђѓєѕіїјљњћќѝўџѡѣѥѧѩѫѭѯѱѳѵѷѹѻѽѿҁҋҍҏґғҕҗҙқҝҟҡңҥҧҩҫҭүұҳҵҷҹһҽҿӂӄӆӈӊӌӎӑӓӕӗәӛӝӟӡӣӥӧөӫӭӯӱӳӵӷӹԁԃԅԇԉԋԍԏաբգդեզէըթժիլխծկհձղճմյնշոչպջռսվտրցւփքօֆևᴀᴁᴂᴃᴄᴅᴆᴇᴈᴉᴊᴋᴌᴍᴎᴏᴐᴑᴒᴓᴔᴕᴖᴗᴘᴙᴚᴛᴜᴝᴞᴟᴠᴡᴢᴣᴤᴥᴦᴧᴨᴩᴪᴫᵢᵣᵤᵥᵦᵧᵨᵩᵪᵫᵬᵭᵮᵯᵰᵱᵲᵳᵴᵵᵶᵷᵹᵺᵻᵼᵽᵾᵿᶀᶁᶂᶃᶄᶅᶆᶇᶈᶉᶊᶋᶌᶍᶎᶏᶐᶑᶒᶓᶔᶕᶖᶗᶘᶙᶚḁḃḅḇḉḋḍḏḑḓḕḗḙḛḝḟḡḣḥḧḩḫḭḯḱḳḵḷḹḻḽḿṁṃṅṇṉṋṍṏṑṓṕṗṙṛṝṟṡṣṥṧṩṫṭṯṱṳṵṷṹṻṽṿẁẃẅẇẉẋẍẏẑẓẕẖẗẘẙẚẛạảấầẩẫậắằẳẵặẹẻẽếềểễệỉịọỏốồổỗộớờởỡợụủứừửữựỳỵỷỹἀἁἂἃἄἅἆἇἐἑἒἓἔἕἠἡἢἣἤἥἦἧἰἱἲἳἴἵἶἷὀὁὂὃὄὅὐὑὒὓὔὕὖὗὠὡὢὣὤὥὦὧὰάὲέὴήὶίὸόὺύὼώᾀᾁᾂᾃᾄᾅᾆᾇᾐᾑᾒᾓᾔᾕᾖᾗᾠᾡᾢᾣᾤᾥᾦᾧᾰᾱᾲᾳᾴᾶᾷιῂῃῄῆῇῐῑῒΐῖῗῠῡῢΰῤῥῦῧῲῳῴῶῷⲁⲃⲅⲇⲉⲋⲍⲏⲑⲓⲕⲗⲙⲛⲝⲟⲡⲣⲥⲧⲩⲫⲭⲯⲱⲳⲵⲷⲹⲻⲽⲿⳁⳃⳅⳇⳉⳋⳍⳏⳑⳓⳕⳗⳙⳛⳝⳟⳡⳣⳤⴀⴁⴂⴃⴄⴅⴆⴇⴈⴉⴊⴋⴌⴍⴎⴏⴐⴑⴒⴓⴔⴕⴖⴗⴘⴙⴚⴛⴜⴝⴞⴟⴠⴡⴢⴣⴤⴥfffiflffifflſtstﬓﬔﬕﬖﬗ\d\-_^]/8
 
 / End of testinput4 /