Fix handling of medial hyphens in Unicode Names.

[cor3ntin]

Summary

In a Unicode name was stored in a way that caused
a medial hyphen to be at the end of a a chunk, it would not
be properly ignored by the loose matching algorithm.

For example if LEFT-TO-RIGHT OVERRIDE was stored as
LEFT- [...], the - would not be ignored.

The generators now ensures nodes are not cut accross
medial hyphen boundaries.

Fixes #64161

[tbaeder]

llvm/lib/Support/UnicodeNameToCodepoint.cpp

350

[cor3ntin]

Fix comment

[aaron.ballman]

LGTM

llvm/utils/UnicodeData/UnicodeNameMappingGenerator.cpp

100

Parens here might be a kindness to folks who don't keep precedence rules in their head very well. ;-)

[cor3ntin]

llvm/utils/UnicodeData/UnicodeNameMappingGenerator.cpp

100

you are not wrong, I added parens!

clang/docs/ReleaseNotes.rst

 Bug Fixes to C++ Support
 ^^^^^^^^^^^^^^^^^^^^^^^^
 
 - Clang limits the size of arrays it will try to evaluate at compile time
   to avoid memory exhaustion.
   This limit can be modified by `-fconstexpr-steps`.
   (`#63562 <https://github.com/llvm/llvm-project/issues/63562>`_)
 
+- Fix a crash caused by some named unicode escape sequences designating
+  a Unicode character whose name contains a ``-``.
+  (`Fixes #64161 <https://github.com/llvm/llvm-project/issues/64161>_`)
+
 Bug Fixes to AST Handling
 ^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Miscellaneous Bug Fixes
 ^^^^^^^^^^^^^^^^^^^^^^^
 
 Miscellaneous Clang Crashes Fixed
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

clang/lib/Lex/LiteralSupport.cpp

if (Kind == 'u' && *I == '{') {
       continue;
     }
 
     if (Kind == 'N') {
       assert(*I == '{');
       ++I;
       auto Delim = std::find(I, Input.end(), '}');
       assert(Delim != Input.end());
+      StringRef Name(I, std::distance(I, Delim));
       std::optional<llvm::sys::unicode::LooseMatchingResult> Res =
-          llvm::sys::unicode::nameToCodepointLooseMatching(
-              StringRef(I, std::distance(I, Delim)));
-      assert(Res);
+          llvm::sys::unicode::nameToCodepointLooseMatching(Name);
+      assert(Res && "could not find a codepoint that was previously found");
       CodePoint = Res->CodePoint;
       assert(CodePoint != 0xFFFFFFFF);
       appendCodePoint(CodePoint, Buf);
       I = Delim;
       continue;
     }
 
     unsigned NumHexDigits;

clang/test/Preprocessor/ucn-pp-identifier.c

 #endif
 
 #ifndef TRIGRAPHS
 int a\N{LATIN CAPITAL LETTER A WITH GRAVE??>;
 // expected-warning@-1 {{trigraph ignored}}\
 // expected-warning@-1 {{incomplete}}\
 // expected-error@-1 {{expected unqualified-id}}
 #endif
+
+// GH64161
+int A\N{LEFT-TO-RIGHT OVERRIDE}; // expected-error {{character <U+202D> not allowed in an identifier}}

llvm/lib/Support/UnicodeNameToCodepoint.cpp

if (HasValue) {
     }
   }
   N.Size = Offset - Origin;
   return N;
 }
 
 static bool startsWith(StringRef Name, StringRef Needle, bool Strict,
                        std::size_t &Consummed, char &PreviousCharInName,
-                       char &PreviousCharInNeedle, bool IsPrefix = false) {
+                       bool IsPrefix = false) {
 
   Consummed = 0;
   if (Strict) {
     if (!Name.startswith(Needle))
       return false;
     Consummed = Needle.size();
     return true;
   }
   if (Needle.empty())
     return true;
 
   auto NamePos = Name.begin();
   auto NeedlePos = Needle.begin();
 
   char PreviousCharInNameOrigin = PreviousCharInName;
-  char PreviousCharInNeedleOrigin = PreviousCharInNeedle;
-
+  char PreviousCharInNeedle = *Needle.begin();
   auto IgnoreSpaces = [](auto It, auto End, char &PreviousChar,
-                         bool IgnoreEnd = false) {
+                         bool IsPrefix = false) {
     while (It != End) {
       const auto Next = std::next(It);
       // Ignore spaces, underscore, medial hyphens
-      // https://unicode.org/reports/tr44/#UAX44-LM2.
+      // The generator ensures a needle never ends (or starts) by a medial
+      // hyphen https://unicode.org/reports/tr44/#UAX44-LM2.
       bool Ignore =
           *It == ' ' || *It == '_' ||
           (*It == '-' && isAlnum(PreviousChar) &&
-           ((Next != End && isAlnum(*Next)) || (Next == End && IgnoreEnd)));
+           ((Next != End && isAlnum(*Next)) || (Next == End && IsPrefix)));
       PreviousChar = *It;
       if (!Ignore)
         break;
       ++It;
     }
     return It;
   };
 
   while (true) {
     NamePos = IgnoreSpaces(NamePos, Name.end(), PreviousCharInName);
     NeedlePos =
         IgnoreSpaces(NeedlePos, Needle.end(), PreviousCharInNeedle, IsPrefix);
     if (NeedlePos == Needle.end())
       break;
     if (NamePos == Name.end())
       break;
     if (toUpper(*NeedlePos) != toUpper(*NamePos))
       break;
     NeedlePos++;
     NamePos++;
   }
   Consummed = std::distance(Name.begin(), NamePos);
   if (NeedlePos != Needle.end()) {
     PreviousCharInName = PreviousCharInNameOrigin;
-    PreviousCharInNeedle = PreviousCharInNeedleOrigin;
   }
   return NeedlePos == Needle.end();
 }
 
 static std::tuple<Node, bool, uint32_t>
 compareNode(uint32_t Offset, StringRef Name, bool Strict,
-            char PreviousCharInName, char PreviousCharInNeedle,
-            BufferType &Buffer, const Node *Parent = nullptr) {
+            char PreviousCharInName, BufferType &Buffer,
+            const Node *Parent = nullptr) {
   Node N = readNode(Offset, Parent);
   std::size_t Consummed = 0;
-  bool DoesStartWith =
-      N.IsRoot || startsWith(Name, N.Name, Strict, Consummed,
-                             PreviousCharInName, PreviousCharInNeedle);
+  bool DoesStartWith = N.IsRoot || startsWith(Name, N.Name, Strict, Consummed,
+                                              PreviousCharInName);
   if (!DoesStartWith)
     return std::make_tuple(N, false, 0);
 
   if (Name.size() - Consummed == 0 && N.Value != 0xFFFFFFFF)
     return std::make_tuple(N, true, N.Value);
 
   if (N.hasChildren()) {
     uint32_t ChildOffset = N.ChildrenOffset;
     for (;;) {
       Node C;
       bool Matches;
       uint32_t Value;
       std::tie(C, Matches, Value) =
           compareNode(ChildOffset, Name.substr(Consummed), Strict,
-                      PreviousCharInName, PreviousCharInNeedle, Buffer, &N);
+                      PreviousCharInName, Buffer, &N);
       if (Matches) {
         std::reverse_copy(C.Name.begin(), C.Name.end(),
                           std::back_inserter(Buffer));
         return std::make_tuple(N, true, Value);
       }
       ChildOffset += C.Size;
       if (!C.HasSibling)
         break;
     }
   }
   return std::make_tuple(N, false, 0);
 }
 
 static std::tuple<Node, bool, uint32_t>
 compareNode(uint32_t Offset, StringRef Name, bool Strict, BufferType &Buffer) {
-  return compareNode(Offset, Name, Strict, 0, 0, Buffer);
+  return compareNode(Offset, Name, Strict, 0, Buffer);
 }
 
 // clang-format off
 constexpr const char *const HangulSyllables[][3] = {
     { "G",  "A",   ""   },
     { "GG", "AE",  "G"  },
     { "N",  "YA",  "GG" },
     { "D",  "YAE", "GS" },

 constexpr const uint32_t LCount = 19;
 constexpr const uint32_t VCount = 21;
 constexpr const uint32_t TCount = 28;
 
 static std::size_t findSyllable(StringRef Name, bool Strict,
                                 char &PreviousInName, int &Pos, int Column) {
   assert(Column == 0 || Column == 1 || Column == 2);
   static std::size_t CountPerColumn[] = {LCount, VCount, TCount};
-  char NeedleStart = 0;
   int Len = -1;
   int Prev = PreviousInName;
   for (std::size_t I = 0; I < CountPerColumn[Column]; I++) {
     StringRef Syllable(HangulSyllables[I][Column]);
     if (int(Syllable.size()) <= Len)
       continue;
     std::size_t Consummed = 0;
     char PreviousInNameCopy = PreviousInName;
-    bool DoesStartWith = startsWith(Name, Syllable, Strict, Consummed,
-                                    PreviousInNameCopy, NeedleStart);
+    bool DoesStartWith =
+        startsWith(Name, Syllable, Strict, Consummed, PreviousInNameCopy);
     if (!DoesStartWith)
       continue;
     Len = Consummed;
     Pos = I;
     Prev = PreviousInNameCopy;
   }
   if (Len == -1)
     return 0;
   PreviousInName = Prev;
   return size_t(Len);
 }
 
 static std::optional<char32_t>
 nameToHangulCodePoint(StringRef Name, bool Strict, BufferType &Buffer) {
   Buffer.clear();
   // Hangul Syllable Decomposition
   std::size_t Consummed = 0;
-  char NameStart = 0, NeedleStart = 0;
-  bool DoesStartWith = startsWith(Name, "HANGUL SYLLABLE ", Strict, Consummed,
-                                  NameStart, NeedleStart);
+  char NameStart = 0;
+  bool DoesStartWith =
+      startsWith(Name, "HANGUL SYLLABLE ", Strict, Consummed, NameStart);
   if (!DoesStartWith)
     return std::nullopt;
   Name = Name.substr(Consummed);
   int L = -1, V = -1, T = -1;
   Name = Name.substr(findSyllable(Name, Strict, NameStart, L, 0));
   Name = Name.substr(findSyllable(Name, Strict, NameStart, V, 1));
   Name = Name.substr(findSyllable(Name, Strict, NameStart, T, 2));
   if (L != -1 && V != -1 && T != -1 && Name.empty()) {
static const GeneratedNamesData GeneratedNamesDataTable[] = {
     {"CJK COMPATIBILITY IDEOGRAPH-", 0x2F800, 0x2FA1D},
 };
 
 static std::optional<char32_t>
 nameToGeneratedCodePoint(StringRef Name, bool Strict, BufferType &Buffer) {
   for (auto &&Item : GeneratedNamesDataTable) {
     Buffer.clear();
     std::size_t Consummed = 0;
-    char NameStart = 0, NeedleStart = 0;
+    char NameStart = 0;
     bool DoesStartWith = startsWith(Name, Item.Prefix, Strict, Consummed,
-                                    NameStart, NeedleStart, /*isPrefix*/ true);
+                                    NameStart, /*IsPrefix=*/true);
     if (!DoesStartWith)
       continue;
     auto Number = Name.substr(Consummed);
     unsigned long long V = 0;
     // Be consistent about mandating upper casing.
     if (Strict &&
         llvm::any_of(Number, [](char C) { return C >= 'a' && C <= 'f'; }))
       return {};

llvm/unittests/Support/UnicodeTest.cpp

TEST(Unicode, nameToCodepointLoose) {
   EXPECT_EQ(0xFFFFFFFFu, map("STICK FIGURE --"));
   EXPECT_EQ(0xFFFFFFFFu, map("STICK--FIGURE"));
 
   EXPECT_EQ(0x0F68u, map("TIBETAN LETTER A"));
   EXPECT_EQ(0x0F68u, map("TIBETAN LETTERA"));
   EXPECT_EQ(0x0F68u, map("TIBETAN LETTER-A"));
   EXPECT_EQ(0x0F60u, map("TIBETAN LETTER -A"));
   EXPECT_EQ(0x0F60u, map("TIBETAN LETTER  -A"));
-  ;
+
+  // GH64161
+  EXPECT_EQ(0x202Du, map("LEFT-TO-RIGHT OVERRIDE"));
+  EXPECT_EQ(0x202Du, map("LEFT TO RIGHT OVERRIDE"));
+  EXPECT_EQ(0x202Du, map("LEFTTORIGHTOVERRIDE"));
+  EXPECT_EQ(0x202Du, map("LEFT-TO-RIGHT-OVERRIDE"));
+  EXPECT_FALSE(nameToCodepointLooseMatching("-LEFT-TO-RIGHT OVERRIDE"));
+  EXPECT_FALSE(nameToCodepointLooseMatching("LEFT-TO-RIGHT OVERRIDE-"));
 
   // special case
   EXPECT_EQ(0x1180u, map("HANGUL JUNGSEONG O-E"));
   EXPECT_EQ(0x116Cu, map("HANGUL JUNGSEONG OE"));
 
   // names that are prefix to existing characters should not match
   EXPECT_FALSE(nameToCodepointLooseMatching("B"));
   EXPECT_FALSE(nameToCodepointLooseMatching("BE"));

llvm/utils/UnicodeData/UnicodeNameMappingGenerator.cpp

 
 public:
   // When inserting named codepoint
   // We create a node per character in the name.
   // SPARKLE becomes S <- P <- A <- R <- K <- L <- E
   // Once all  characters are inserted, the tree is compacted
   void insert(llvm::StringRef Name, char32_t Codepoint) {
     Node *N = Root.get();
-    for (auto Ch : Name) {
+    bool IsBeforeMedial = false;
+    for (auto ChIt = Name.begin(); ChIt != Name.end();
+         ChIt += (IsBeforeMedial ? 3 : 1)) {
+      char Ch = *ChIt;
+      assert(Letters.contains(Ch) && "Unexpected symbol in Unicode name");
+
       std::string Label(1, Ch);
+
+      // We need to ensure a node never ends or starts by
+      // a medial hyphen as this would break the
+      // loose matching algorithm.
+      IsBeforeMedial = llvm::isAlnum(Ch) && ChIt + 1 != Name.end() &&
+                       *(ChIt + 1) == '-' && ChIt + 2 != Name.end() &&
+                       llvm::isAlnum(*(ChIt + 2));
+      if (IsBeforeMedial)
+        Label.assign(ChIt, ChIt + 3);
+
       auto It = llvm::find_if(N->Children,
                               [&](const auto &C) { return C->Name == Label; });
       if (It == N->Children.end()) {
         It = N->Children.insert(It, std::make_unique<Node>(Label, N));
       }
       N = It->get();
     }
     N->Value = Codepoint;