4 ms·

Backtracking in a UTF-8 string is easy: when you need to remember a location, just record its byte offset. You have exactly the same issue in UTF-16, which is a

• sanxiyn 10y ago
  Yes, you have exactly the same issue in UTF-16, I never said otherwise.
  • pjscott 10y ago
    I agree that you never said otherwise, and I applaud you for your accuracy in not doing so. :-D The reason I bring it up is that UTF-16 is a very commonly used internal encoding for strings, and regular expression engines for platforms which use UTF-16 internally are generally designed to work on that encoding without conversion to UTF-32. Examples that spring to mind are most JavaScript regular expression engines, the ICU regular expression engine, and java.util.regex. If variable-width encodings were so difficult to deal with then you would expect these to have run into some problems with it; however, as far as I can tell, they have not. This is evidence against variable-width encodings being difficult for regular expression engines to deal with. (Sanity check for my argument above: If you read through https://swtch.com/~rsc/regexp/regexp2.html https://swtch.com/~rsc/regexp/regexp2.html, which covers both backtracking and non-backtracking regex engines and includes code, none of the code examples would need more than trivial modification to deal with variable-width encodings.)
    • Manishearth 10y ago
      Note that JS isn't UTF-16, it's slightly different. In JS unpaired surrogates are allowed. String indexing is by code unit, so non-BMP code points are considered to be two "characters". IIRC Java also allows unpaired surrogates? But does consider non-BMP codepoints to be single characters. I think. Idk. So from JSs point of view it is a fixed-width encoding, one where all byte values are valid. `"\uD83D\uDC68".match(/\ud83d/)` works (U+D83D is a high surrogate, and "\uD83D\uDC68" is U+1F468 MAN), so the regex engine operates on code units, not code points. I think for Java the regex engine would have to deal with it as a variable-width encoding, though. Edit: Hacker News removes emoji from comments.
      • hsivonen 10y ago
        Java strings are sequences of 16-bit units and don't guarantee UTF-16 validity. There are newer standard library APIs that perform astral-aware operations, though.
        • Manishearth 10y ago
          So does regex matching break up paired surrogates? It seems like Java Characters can be from the higher planes. JS treats surrogates as their own kind of character, but I think Java only does this for unpaired surrogates, so the encoding is still multibyte. ICBW.
          • throwawayish 10y ago
            Java, like NT, was originally UCS-2 and moved to UTF-16 when it became clear that UCS-2 won't suffice. APIs that operate on units (anything involving "char"s [the type], CharSequences and so on) are legacy and, when used, are almost certainly used incorrectly. Note that newer APIs on String also use the word "char", but the type "int", these are actually operating on code points and not CUs, ie. these APIs are correct. (Note that java.lang.Character is a char, so wrong. I think there is no CodePoint type or similar that wraps int.)
          • hsivonen 10y ago
            In Java regexps, the dot matches a code point or an unpaired surrogate, so if you have a proper surrogate pair, the dot matches the whole pair without splitting it. It does split grapheme clusters. It's unclear to me what you mean by "Java Characters". A Java char is a UTF-16 code unit, and the java.lang.Character boxes a char (16 bits unsigned). However, since Java 5, java.lang.Character has static methods for astral-aware UTF-16 operations where a code point is a Java int (32 bits signed).
            • Manishearth 10y ago
              Yeah, by Character I meant java.lang.Character. > the dot matches the whole pair without splitting it Yeah, so UTF16 in Java is being used as a variable-width encoding. Nice to know.