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>
loadDataFiles(const std::string & NamesFile,const std::string & AliasesFile)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
insert(llvm::StringRef Name,char32_t Codepoint)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
compact()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.
serialize()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
getNameFragments()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.
letter(char C)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
dumpIndex(const std::string & Dict)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:
collectKeys(Node * N,std::set<std::string> & Keys)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
compact(Node * N)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 {
NodeTrie::Node324 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
main(int argc,char ** argv)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() || !llvm::all_of(Name, [](char C) {
365 return llvm::is_contained(Letters, C);
366 })) {
367 continue;
368 }
369 printf("%06x: %s\n", static_cast<unsigned int>(Codepoint), Name.c_str());
370 T.insert(Name, Codepoint);
371 LongestName =
372 std::max(LongestName, std::size_t(llvm::count_if(Name, llvm::isAlnum)));
373 NameCount++;
374 }
375 T.compact();
376
377 std::pair<std::string, std::vector<uint8_t>> Data = T.serialize();
378 const std::string &Dict = Data.first;
379 const std::vector<uint8_t> &Tree = Data.second;
380
381 fprintf(Out, R"(
382 //===------------- Support/UnicodeNameToCodepointGenerated.cpp ------------===//
383 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
384 // See https://llvm.org/LICENSE.txt for license information.
385 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
386 //
387 //===----------------------------------------------------------------------===//
388 //
389 // This file implements mapping the name of a unicode code point to its value.
390 //
391 // This file was generated using %s.
392 // Do not edit manually.
393 //
394 //===----------------------------------------------------------------------===//
395 %s
396
397
398
399 #include "llvm/Support/Compiler.h"
400 #include <cstddef>
401 #include <cstdint>
402 )",
403 argv[0], UnicodeLicense);
404
405 fprintf(Out,
406 "namespace llvm { namespace sys { namespace unicode { \n"
407 "extern const char *UnicodeNameToCodepointDict;\n"
408 "extern const uint8_t *UnicodeNameToCodepointIndex;\n"
409 "extern const std::size_t UnicodeNameToCodepointIndexSize;\n"
410 "extern const std::size_t UnicodeNameToCodepointLargestNameSize;\n");
411
412 fprintf(Out, "const char* UnicodeNameToCodepointDict = \"%s\";\n",
413 Dict.c_str());
414
415 fprintf(Out, "uint8_t UnicodeNameToCodepointIndex_[%zu] = {\n",
416 Tree.size() + 1);
417
418 for (auto Byte : Tree) {
419 fprintf(Out, "0x%02x,", Byte);
420 }
421
422 fprintf(Out, "0};");
423 fprintf(Out, "const uint8_t* UnicodeNameToCodepointIndex = "
424 "UnicodeNameToCodepointIndex_; \n");
425 fprintf(Out, "const std::size_t UnicodeNameToCodepointIndexSize = %zu;\n",
426 Tree.size() + 1);
427 fprintf(Out,
428 "const std::size_t UnicodeNameToCodepointLargestNameSize = %zu;\n",
429 LongestName);
430 fprintf(Out, "\n}}}\n");
431 fclose(Out);
432 printf("Generated %s: %u Files.\nIndex: %f kB, Dictionary: %f kB.\nDone\n\n",
433 argv[3], NameCount, Tree.size() / 1024.0, Dict.size() / 1024.0);
434 }
435
436 const char *UnicodeLicense = R"(
437 /*
438 UNICODE, INC. LICENSE AGREEMENT - DATA FILES AND SOFTWARE
439
440 See Terms of Use <https://www.unicode.org/copyright.html>
441 for definitions of Unicode Inc.’s Data Files and Software.
442
443 NOTICE TO USER: Carefully read the following legal agreement.
444 BY DOWNLOADING, INSTALLING, COPYING OR OTHERWISE USING UNICODE INC.'S
445 DATA FILES ("DATA FILES"), AND/OR SOFTWARE ("SOFTWARE"),
446 YOU UNEQUIVOCALLY ACCEPT, AND AGREE TO BE BOUND BY, ALL OF THE
447 TERMS AND CONDITIONS OF THIS AGREEMENT.
448 IF YOU DO NOT AGREE, DO NOT DOWNLOAD, INSTALL, COPY, DISTRIBUTE OR USE
449 THE DATA FILES OR SOFTWARE.
450
451 COPYRIGHT AND PERMISSION NOTICE
452
453 Copyright © 1991-2022 Unicode, Inc. All rights reserved.
454 Distributed under the Terms of Use in https://www.unicode.org/copyright.html.
455
456 Permission is hereby granted, free of charge, to any person obtaining
457 a copy of the Unicode data files and any associated documentation
458 (the "Data Files") or Unicode software and any associated documentation
459 (the "Software") to deal in the Data Files or Software
460 without restriction, including without limitation the rights to use,
461 copy, modify, merge, publish, distribute, and/or sell copies of
462 the Data Files or Software, and to permit persons to whom the Data Files
463 or Software are furnished to do so, provided that either
464 (a) this copyright and permission notice appear with all copies
465 of the Data Files or Software, or
466 (b) this copyright and permission notice appear in associated
467 Documentation.
468
469 THE DATA FILES AND SOFTWARE ARE PROVIDED "AS IS", WITHOUT WARRANTY OF
470 ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
471 WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
472 NONINFRINGEMENT OF THIRD PARTY RIGHTS.
473 IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS
474 NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL
475 DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
476 DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
477 TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
478 PERFORMANCE OF THE DATA FILES OR SOFTWARE.
479
480 Except as contained in this notice, the name of a copyright holder
481 shall not be used in advertising or otherwise to promote the sale,
482 use or other dealings in these Data Files or Software without prior
483 written authorization of the copyright holder.
484 */
485 )";
486