llvm/utils/UnicodeData/UnicodeNameMappingGenerator.cpp

   1 //===--- UnicodeNameMappingGenerator.cpp - Unicode name data generator ---===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file is used to generate lib/Support/UnicodeNameToCodepointGenerated.cpp
  10 // using UnicodeData.txt and NameAliases.txt available at
  11 // https://unicode.org/Public/15.0.0/ucd/
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/ADT/STLExtras.h"
  15 #include "llvm/ADT/StringExtras.h"
  16 #include "llvm/ADT/StringRef.h"
  17 #include <algorithm>
  18 #include <array>
  19 #include <deque>
  20 #include <fstream>
  21 #include <memory>
  22 #include <optional>
  23 #include <set>
  24 #include <string>
  25 #include <unordered_map>
  26 #include <utility>
  27 #include <vector>
  28
  29 static const llvm::StringRef Letters =
  30     " _-ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
  31
  32 // Collect names UnicodeData.txt and AliasNames.txt
  33 // There may be multiple names per code points.
  34 static std::unordered_multimap<char32_t, std::string>
  35 loadDataFiles(const std::string &NamesFile, const std::string &AliasesFile) {
  36   std::unordered_multimap<char32_t, std::string> CollectedCharacters;
  37   auto FromFile = [&](const std::string &File, bool IsAliasFile = false) {
  38     std::ifstream InputFile(File);
  39     for (std::string Line; getline(InputFile, Line);) {
  40       if (Line.empty() || !isxdigit(Line[0]))
  41         continue;
  42       auto FirstSemiPos = Line.find(';');
  43       if (FirstSemiPos == std::string::npos)
  44         continue;
  45       auto SecondSemiPos = Line.find(';', FirstSemiPos + 1);
  46       if (SecondSemiPos == std::string::npos)
  47         continue;
  48       unsigned long long CodePoint;
  49       if (llvm::getAsUnsignedInteger(
  50               llvm::StringRef(Line.c_str(), FirstSemiPos), 16, CodePoint)) {
  51         continue;
  52       }
  53
  54       std::string Name =
  55           Line.substr(FirstSemiPos + 1, SecondSemiPos - FirstSemiPos - 1);
  56
  57       if (!Name.empty() && Name[0] == '<') {
  58         // Ignore ranges of characters, as their name is either absent or
  59         // generated.
  60         continue;
  61       }
  62
  63       // Some aliases are ignored for compatibility with C++
  64       if (IsAliasFile) {
  65         std::string Kind = Line.substr(SecondSemiPos + 1);
  66         if (Kind != "control" && Kind != "correction" && Kind != "alternate")
  67           continue;
  68       }
  69
  70       auto InsertUnique = [&](char32_t CP, std::string Name) {
  71         auto It = CollectedCharacters.find(CP);
  72         while (It != std::end(CollectedCharacters) && It->first == CP) {
  73           if (It->second == Name)
  74             return;
  75           ++It;
  76         }
  77         CollectedCharacters.insert({CP, std::move(Name)});
  78       };
  79       InsertUnique(CodePoint, std::move(Name));
  80     }
  81   };
  82
  83   FromFile(NamesFile);
  84   FromFile(AliasesFile, true);
  85   return CollectedCharacters;
  86 }
  87
  88 class Trie {
  89   struct Node;
  90
  91 public:
  92   // When inserting named codepoint
  93   // We create a node per character in the name.
  94   // SPARKLE becomes S <- P <- A <- R <- K <- L <- E
  95   // Once all  characters are inserted, the tree is compacted
  96   void insert(llvm::StringRef Name, char32_t Codepoint) {
  97     Node *N = Root.get();
  98     for (auto Ch : Name) {
  99       std::string Label(1, Ch);
 100       auto It = llvm::find_if(N->Children,
 101                               [&](const auto &C) { return C->Name == Label; });
 102       if (It == N->Children.end()) {
 103         It = N->Children.insert(It, std::make_unique<Node>(Label, N));
 104       }
 105       N = It->get();
 106     }
 107     N->Value = Codepoint;
 108   }
 109
 110   void compact() { compact(Root.get()); }
 111
 112   // This creates 2 arrays of bytes from the tree:
 113   // A serialized dictionary of node labels,
 114   // And the nodes themselves.
 115   // The name of each label is found by indexing into the dictionary.
 116   // The longest names are inserted first into the dictionary,
 117   // in the hope it will contain shorter labels as substring,
 118   // thereby reducing duplication.
 119   // We could theorically be more clever by trying to minimizing the size
 120   // of the dictionary.
 121   std::pair<std::string, std::vector<uint8_t>> serialize() {
 122     std::set<std::string> Names = this->getNameFragments();
 123     std::vector<std::string> Sorted(Names.begin(), Names.end());
 124     llvm::sort(Sorted, [](const auto &a, const auto &b) {
 125       return a.size() > b.size();
 126     });
 127     std::string Dict(Letters.begin(), Letters.end());
 128     Dict.reserve(50000);
 129     for (const std::string &Name : Sorted) {
 130       if (Name.size() <= 1)
 131         continue;
 132       if (Dict.find(Name) != std::string::npos)
 133         continue;
 134       Dict += Name;
 135     }
 136
 137     if (Dict.size() >= std::numeric_limits<uint16_t>::max()) {
 138       fprintf(stderr, "Dictionary too big  to be serialized");
 139       exit(1);
 140     }
 141
 142     auto Bytes = dumpIndex(Dict);
 143     return {Dict, Bytes};
 144   }
 145
 146   std::set<std::string> getNameFragments() {
 147     std::set<std::string> Keys;
 148     collectKeys(Root.get(), Keys);
 149     return Keys;
 150   }
 151
 152   // Maps a valid char in an Unicode character name
 153   // To a 6 bits index.
 154   static uint8_t letter(char C) {
 155     auto Pos = Letters.find(C);
 156     assert(Pos != std::string::npos &&
 157            "Invalid letter in Unicode character name");
 158     return Pos;
 159   }
 160
 161   // clang-format off
 162   // +================+============+======================+=============+========+===+==============+===============+
 163   // | 0          | 1             | 2-7 (6)              | 8-23        | 24-44  |    | 46           | 47            |
 164   // +================+============+======================+=============+========+===+==============+===============+
 165   // | Has Value |  Has Long Name | Letter OR Name Size  | Dict Index  | Value  |    | Has Sibling  | Has Children  |
 166   // +----------------+------------+----------------------+-------------+--------+---+--------------+---------------+
 167   // clang-format on
 168
 169   std::vector<uint8_t> dumpIndex(const std::string &Dict) {
 170     struct ChildrenOffset {
 171       Node *FirstChild;
 172       std::size_t Offset;
 173       bool HasValue;
 174     };
 175
 176     // Keep track of the start of each node
 177     // position in the serialized data.
 178     std::unordered_map<Node *, int32_t> Offsets;
 179
 180     // Keep track of where to write the index
 181     // of the first children
 182     std::vector<ChildrenOffset> ChildrenOffsets;
 183     std::unordered_map<Node *, bool> SiblingTracker;
 184     std::deque<Node *> AllNodes;
 185     std::vector<uint8_t> Bytes;
 186     Bytes.reserve(250'000);
 187     // This leading byte is used by the reading code to detect the root node.
 188     Bytes.push_back(0);
 189
 190     auto CollectChildren = [&SiblingTracker, &AllNodes](const auto &Children) {
 191       for (std::size_t Index = 0; Index < Children.size(); Index++) {
 192         const std::unique_ptr<Node> &Child = Children[Index];
 193         AllNodes.push_back(Child.get());
 194         if (Index != Children.size() - 1)
 195           SiblingTracker[Child.get()] = true;
 196       }
 197     };
 198     CollectChildren(Root->Children);
 199
 200     while (!AllNodes.empty()) {
 201       const std::size_t Offset = Bytes.size();
 202       Node *const N = AllNodes.front();
 203       AllNodes.pop_front();
 204
 205       assert(!N->Name.empty());
 206       Offsets[N] = Offset;
 207
 208       uint8_t FirstByte = (!!N->Value) ? 0x80 : 0;
 209       // Single letter node are indexed in 6 bits
 210       if (N->Name.size() == 1) {
 211         FirstByte |= letter(N->Name[0]);
 212         Bytes.push_back(FirstByte);
 213       } else {
 214         // Otherwise we use a 16 bits index
 215         FirstByte = FirstByte | uint8_t(N->Name.size()) | 0x40;
 216         Bytes.push_back(FirstByte);
 217         auto PosInDict = Dict.find(N->Name);
 218         assert(PosInDict != std::string::npos);
 219         uint8_t Low = PosInDict;
 220         uint8_t High = ((PosInDict >> 8) & 0xFF);
 221         Bytes.push_back(High);
 222         Bytes.push_back(Low);
 223       }
 224
 225       const bool HasSibling = SiblingTracker.count(N) != 0;
 226       const bool HasChildren = N->Children.size() != 0;
 227
 228       if (!!N->Value) {
 229         uint32_t Value = (*(N->Value) << 3);
 230         uint8_t H = ((Value >> 16) & 0xFF);
 231         uint8_t M = ((Value >> 8) & 0xFF);
 232         uint8_t L = (Value & 0xFF) | uint8_t(HasSibling ? 0x01 : 0) |
 233                     uint8_t(HasChildren ? 0x02 : 0);
 234
 235         Bytes.push_back(H);
 236         Bytes.push_back(M);
 237         Bytes.push_back(L);
 238
 239         if (HasChildren) {
 240           ChildrenOffsets.push_back(
 241               ChildrenOffset{N->Children[0].get(), Bytes.size(), true});
 242           // index of the first children
 243           Bytes.push_back(0x00);
 244           Bytes.push_back(0x00);
 245           Bytes.push_back(0x00);
 246         }
 247       } else {
 248         // When there is no value (that's most intermediate nodes)
 249         // Dispense of the 3 values bytes, and only store
 250         // 1 byte to track whether the node has sibling and children
 251         // + 2 bytes for the index of the first children if necessary.
 252         // That index also uses bytes 0-6 of the previous byte.
 253         uint8_t Byte =
 254             uint8_t(HasSibling ? 0x80 : 0) | uint8_t(HasChildren ? 0x40 : 0);
 255         Bytes.push_back(Byte);
 256         if (HasChildren) {
 257           ChildrenOffsets.emplace_back(
 258               ChildrenOffset{N->Children[0].get(), Bytes.size() - 1, false});
 259           Bytes.push_back(0x00);
 260           Bytes.push_back(0x00);
 261         }
 262       }
 263       CollectChildren(N->Children);
 264     }
 265
 266     // Once all the nodes are in the inndex
 267     // Fill the bytes we left to indicate the position
 268     // of the children
 269     for (const ChildrenOffset &Parent : ChildrenOffsets) {
 270       const auto It = Offsets.find(Parent.FirstChild);
 271       assert(It != Offsets.end());
 272       std::size_t Pos = It->second;
 273       if (Parent.HasValue) {
 274         Bytes[Parent.Offset] = ((Pos >> 16) & 0xFF);
 275       } else {
 276         Bytes[Parent.Offset] =
 277             Bytes[Parent.Offset] | uint8_t((Pos >> 16) & 0xFF);
 278       }
 279       Bytes[Parent.Offset + 1] = ((Pos >> 8) & 0xFF);
 280       Bytes[Parent.Offset + 2] = Pos & 0xFF;
 281     }
 282
 283     // Add some padding so that the deserialization code
 284     // doesn't try to read past the enf of the array.
 285     Bytes.push_back(0);
 286     Bytes.push_back(0);
 287     Bytes.push_back(0);
 288     Bytes.push_back(0);
 289     Bytes.push_back(0);
 290     Bytes.push_back(0);
 291
 292     return Bytes;
 293   }
 294
 295 private:
 296   void collectKeys(Node *N, std::set<std::string> &Keys) {
 297     Keys.insert(N->Name);
 298     for (const std::unique_ptr<Node> &Child : N->Children) {
 299       collectKeys(Child.get(), Keys);
 300     }
 301   }
 302
 303   // Merge sequences of 1-character nodes
 304   // This greatly reduce the total number of nodes,
 305   // and therefore the size of the index.
 306   // When the tree gets serialized, we only have 5 bytes to store the
 307   // size of a name. Overlong names (>32 characters) are therefore
 308   // kep into separate nodes
 309   void compact(Node *N) {
 310     for (auto &&Child : N->Children) {
 311       compact(Child.get());
 312     }
 313     if (N->Parent && N->Parent->Children.size() == 1 && !N->Parent->Value &&
 314         (N->Parent->Name.size() + N->Name.size() <= 32)) {
 315       N->Parent->Value = N->Value;
 316       N->Parent->Name += N->Name;
 317       N->Parent->Children = std::move(N->Children);
 318       for (std::unique_ptr<Node> &c : N->Parent->Children) {
 319         c->Parent = N->Parent;
 320       }
 321     }
 322   }
 323   struct Node {
 324     Node(std::string Name, Node *Parent = nullptr)
 325         : Name(Name), Parent(Parent) {}
 326
 327     std::vector<std::unique_ptr<Node>> Children;
 328     std::string Name;
 329     Node *Parent = nullptr;
 330     std::optional<char32_t> Value;
 331   };
 332
 333   std::unique_ptr<Node> Root = std::make_unique<Node>("");
 334 };
 335
 336 extern const char *UnicodeLicense;
 337
 338 int main(int argc, char **argv) {
 339   printf("Unicode name -> codepoint mapping generator\n"
 340          "Usage: %s UnicodeData.txt NameAliases.txt output\n\n",
 341          argv[0]);
 342   printf("NameAliases.txt can be found at "
 343          "https://unicode.org/Public/15.0.0/ucd/NameAliases.txt\n"
 344          "UnicodeData.txt can be found at "
 345          "https://unicode.org/Public/15.0.0/ucd/UnicodeData.txt\n\n");
 346
 347   if (argc != 4)
 348     return EXIT_FAILURE;
 349
 350   FILE *Out = fopen(argv[3], "w");
 351   if (!Out) {
 352     printf("Error creating output file.\n");
 353     return EXIT_FAILURE;
 354   }
 355
 356   Trie T;
 357   uint32_t NameCount = 0;
 358   std::size_t LongestName = 0;
 359   auto Entries = loadDataFiles(argv[1], argv[2]);
 360   for (const std::pair<const char32_t, std::string> &Entry : Entries) {
 361     char32_t Codepoint = Entry.first;
 362     const std::string &Name = Entry.second;
 363     // Ignore names which are not valid.
 364     if (Name.empty() ||
 365         !llvm::all_of(Name, [](char C) { return Letters.contains(C); })) {
 366       continue;
 367     }
 368     printf("%06x: %s\n", static_cast<unsigned int>(Codepoint), Name.c_str());
 369     T.insert(Name, Codepoint);
 370     LongestName =
 371         std::max(LongestName, std::size_t(llvm::count_if(Name, llvm::isAlnum)));
 372     NameCount++;
 373   }
 374   T.compact();
 375
 376   std::pair<std::string, std::vector<uint8_t>> Data = T.serialize();
 377   const std::string &Dict = Data.first;
 378   const std::vector<uint8_t> &Tree = Data.second;
 379
 380   fprintf(Out, R"(
 381 //===------------- Support/UnicodeNameToCodepointGenerated.cpp ------------===//
 382 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 383 // See https://llvm.org/LICENSE.txt for license information.
 384 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 385 //
 386 //===----------------------------------------------------------------------===//
 387 //
 388 // This file implements mapping the name of a unicode code point to its value.
 389 //
 390 // This file was generated using %s.
 391 // Do not edit manually.
 392 //
 393 //===----------------------------------------------------------------------===//
 394 %s
 395
 396
 397
 398 #include "llvm/Support/Compiler.h"
 399 #include <cstddef>
 400 #include <cstdint>
 401 )",
 402           argv[0], UnicodeLicense);
 403
 404   fprintf(Out,
 405           "namespace llvm { namespace sys { namespace unicode { \n"
 406           "extern const char *UnicodeNameToCodepointDict;\n"
 407           "extern const uint8_t *UnicodeNameToCodepointIndex;\n"
 408           "extern const std::size_t UnicodeNameToCodepointIndexSize;\n"
 409           "extern const std::size_t UnicodeNameToCodepointLargestNameSize;\n");
 410
 411   fprintf(Out, "const char* UnicodeNameToCodepointDict = \"%s\";\n",
 412           Dict.c_str());
 413
 414   fprintf(Out, "uint8_t UnicodeNameToCodepointIndex_[%zu] = {\n",
 415           Tree.size() + 1);
 416
 417   for (auto Byte : Tree) {
 418     fprintf(Out, "0x%02x,", Byte);
 419   }
 420
 421   fprintf(Out, "0};");
 422   fprintf(Out, "const uint8_t* UnicodeNameToCodepointIndex = "
 423                "UnicodeNameToCodepointIndex_; \n");
 424   fprintf(Out, "const std::size_t UnicodeNameToCodepointIndexSize = %zu;\n",
 425           Tree.size() + 1);
 426   fprintf(Out,
 427           "const std::size_t UnicodeNameToCodepointLargestNameSize = %zu;\n",
 428           LongestName);
 429   fprintf(Out, "\n}}}\n");
 430   fclose(Out);
 431   printf("Generated %s: %u Files.\nIndex: %f kB, Dictionary: %f kB.\nDone\n\n",
 432          argv[3], NameCount, Tree.size() / 1024.0, Dict.size() / 1024.0);
 433 }
 434
 435 const char *UnicodeLicense = R"(
 436 /*
 437 UNICODE, INC. LICENSE AGREEMENT - DATA FILES AND SOFTWARE
 438
 439 See Terms of Use <https://www.unicode.org/copyright.html>
 440 for definitions of Unicode Inc.’s Data Files and Software.
 441
 442 NOTICE TO USER: Carefully read the following legal agreement.
 443 BY DOWNLOADING, INSTALLING, COPYING OR OTHERWISE USING UNICODE INC.'S
 444 DATA FILES ("DATA FILES"), AND/OR SOFTWARE ("SOFTWARE"),
 445 YOU UNEQUIVOCALLY ACCEPT, AND AGREE TO BE BOUND BY, ALL OF THE
 446 TERMS AND CONDITIONS OF THIS AGREEMENT.
 447 IF YOU DO NOT AGREE, DO NOT DOWNLOAD, INSTALL, COPY, DISTRIBUTE OR USE
 448 THE DATA FILES OR SOFTWARE.
 449
 450 COPYRIGHT AND PERMISSION NOTICE
 451
 452 Copyright © 1991-2022 Unicode, Inc. All rights reserved.
 453 Distributed under the Terms of Use in https://www.unicode.org/copyright.html.
 454
 455 Permission is hereby granted, free of charge, to any person obtaining
 456 a copy of the Unicode data files and any associated documentation
 457 (the "Data Files") or Unicode software and any associated documentation
 458 (the "Software") to deal in the Data Files or Software
 459 without restriction, including without limitation the rights to use,
 460 copy, modify, merge, publish, distribute, and/or sell copies of
 461 the Data Files or Software, and to permit persons to whom the Data Files
 462 or Software are furnished to do so, provided that either
 463 (a) this copyright and permission notice appear with all copies
 464 of the Data Files or Software, or
 465 (b) this copyright and permission notice appear in associated
 466 Documentation.
 467
 468 THE DATA FILES AND SOFTWARE ARE PROVIDED "AS IS", WITHOUT WARRANTY OF
 469 ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 470 WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 471 NONINFRINGEMENT OF THIRD PARTY RIGHTS.
 472 IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS
 473 NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL
 474 DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
 475 DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 476 TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 477 PERFORMANCE OF THE DATA FILES OR SOFTWARE.
 478
 479 Except as contained in this notice, the name of a copyright holder
 480 shall not be used in advertising or otherwise to promote the sale,
 481 use or other dealings in these Data Files or Software without prior
 482 written authorization of the copyright holder.
 483 */
 484 )";