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