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