libcxx/utils/generate_escaped_output_table.py

   1 #!/usr/bin/env python
   2 # ===----------------------------------------------------------------------===##
   3 #
   4 # Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 # See https://llvm.org/LICENSE.txt for license information.
   6 # SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 #
   8 # ===----------------------------------------------------------------------===##
   9
  10 # The code is based on
  11 # https://github.com/microsoft/STL/blob/main/tools/unicode_properties_parse/grapheme_break_property_data_gen.py
  12 #
  13 # Copyright (c) Microsoft Corporation.
  14 # SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  15
  16 from io import StringIO
  17 from pathlib import Path
  18 from dataclasses import dataclass, field
  19 from typing import Optional
  20 import re
  21 import sys
  22
  23
  24 @dataclass
  25 class PropertyRange:
  26     lower: int = -1
  27     upper: int = -1
  28     prop: str = None
  29
  30
  31 @dataclass
  32 class Entry:
  33     lower: int = -1
  34     offset: int = -1
  35
  36
  37 LINE_REGEX = re.compile(
  38     r"^(?P<lower>[0-9A-F]{4,6})(?:\.\.(?P<upper>[0-9A-F]{4,6}))?\s*;\s*(?P<prop>\w+)"
  39 )
  40
  41
  42 def filterCoreProperty(element: PropertyRange) -> Optional[PropertyRange]:
  43     if element.prop == "Grapheme_Extend":
  44         return element
  45     return None
  46
  47
  48 # https://www.unicode.org/reports/tr44/#GC_Values_Table
  49 def filterGeneralProperty(element: PropertyRange) -> Optional[PropertyRange]:
  50     if element.prop in ["Zs", "Zl", "Zp", "Cc", "Cf", "Cs", "Co", "Cn"]:
  51         return element
  52     return None
  53
  54
  55 def parsePropertyLine(inputLine: str) -> Optional[PropertyRange]:
  56     result = PropertyRange()
  57     if m := LINE_REGEX.match(inputLine):
  58         lower_str, upper_str, result.prop = m.group("lower", "upper", "prop")
  59         result.lower = int(lower_str, base=16)
  60         result.upper = result.lower
  61         if upper_str is not None:
  62             result.upper = int(upper_str, base=16)
  63         return result
  64
  65     else:
  66         return None
  67
  68
  69 def compactPropertyRanges(input: list[PropertyRange]) -> list[PropertyRange]:
  70     """
  71     Merges overlapping and consecutive ranges to one range.
  72
  73     Since the input properties are filtered the exact property isn't
  74     interesting anymore. The properties in the output are merged to aid
  75     debugging.
  76     Merging the ranges results in fewer ranges in the output table,
  77     reducing binary and improving lookup performance.
  78     """
  79     result = list()
  80     for x in input:
  81         if (
  82             len(result)
  83             and x.lower > result[-1].lower
  84             and x.lower <= result[-1].upper + 1
  85         ):
  86             result[-1].upper = max(result[-1].upper, x.upper)
  87             result[-1].prop += f" {x.prop}"
  88             continue
  89         result.append(x)
  90     return result
  91
  92
  93 DATA_ARRAY_TEMPLATE = """
  94 /// The entries of the characters to escape in format's debug string.
  95 ///
  96 /// Contains the entries for [format.string.escaped]/2.2.1.2.1
  97 ///   CE is a Unicode encoding and C corresponds to either a UCS scalar value
  98 ///   whose Unicode property General_Category has a value in the groups
  99 ///   Separator (Z) or Other (C) or to a UCS scalar value which has the Unicode
 100 ///   property Grapheme_Extend=Yes, as described by table 12 of UAX #44
 101 ///
 102 /// Separator (Z) consists of General_Category
 103 /// - Space_Separator,
 104 /// - Line_Separator,
 105 /// - Paragraph_Separator.
 106 ///
 107 /// Other (C) consists of General_Category
 108 /// - Control,
 109 /// - Format,
 110 /// - Surrogate,
 111 /// - Private_Use,
 112 /// - Unassigned.
 113 ///
 114 /// The data is generated from
 115 /// - https://www.unicode.org/Public/UCD/latest/ucd/DerivedCoreProperties.txt
 116 /// - https://www.unicode.org/Public/UCD/latest/ucd/extracted/DerivedGeneralCategory.txt
 117 ///
 118 /// The table is similar to the table
 119 ///  __extended_grapheme_custer_property_boundary::__entries
 120 /// which explains the details of these classes. The only difference is this
 121 /// table lacks a property, thus having more bits available for the size.
 122 ///
 123 /// The data has 2 values:
 124 /// - bits [0, 10] The size of the range, allowing 2048 elements.
 125 /// - bits [11, 31] The lower bound code point of the range. The upper bound of
 126 ///   the range is lower bound + size.
 127 inline constexpr uint32_t __entries[{size}] = {{
 128 {entries}}};
 129
 130 /// At the end of the valid Unicode code points space a lot of code points are
 131 /// either reserved or a noncharacter. Adding all these entries to the
 132 /// lookup table would add 446 entries to the table (in Unicode 14).
 133 /// Instead the only the start of the region is stored, every code point in
 134 /// this region needs to be escaped.
 135 inline constexpr uint32_t __unallocated_region_lower_bound = 0x{unallocated:08x};
 136
 137 /// Returns whether the code unit needs to be escaped.
 138 ///
 139 /// \pre The code point is a valid Unicode code point.
 140 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool __needs_escape(const char32_t __code_point) noexcept {{
 141   // Since __unallocated_region_lower_bound contains the unshifted range do the
 142   // comparison without shifting.
 143   if (__code_point >= __unallocated_region_lower_bound)
 144     return true;
 145
 146   ptrdiff_t __i = std::ranges::upper_bound(__entries, (__code_point << 11) | 0x7ffu) - __entries;
 147   if (__i == 0)
 148     return false;
 149
 150   --__i;
 151   uint32_t __upper_bound = (__entries[__i] >> 11) + (__entries[__i] & 0x7ffu);
 152   return __code_point <= __upper_bound;
 153 }}
 154 """
 155
 156 TABLES_HPP_TEMPLATE = """
 157 // -*- C++ -*-
 158 //===----------------------------------------------------------------------===//
 159 //
 160 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 161 // See https://llvm.org/LICENSE.txt for license information.
 162 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 163 //
 164 //===----------------------------------------------------------------------===//
 165
 166 // WARNING, this entire header is generated by
 167 // utils/generate_escaped_output_table.py
 168 // DO NOT MODIFY!
 169
 170 // UNICODE, INC. LICENSE AGREEMENT - DATA FILES AND SOFTWARE
 171 //
 172 // See Terms of Use <https://www.unicode.org/copyright.html>
 173 // for definitions of Unicode Inc.'s Data Files and Software.
 174 //
 175 // NOTICE TO USER: Carefully read the following legal agreement.
 176 // BY DOWNLOADING, INSTALLING, COPYING OR OTHERWISE USING UNICODE INC.'S
 177 // DATA FILES ("DATA FILES"), AND/OR SOFTWARE ("SOFTWARE"),
 178 // YOU UNEQUIVOCALLY ACCEPT, AND AGREE TO BE BOUND BY, ALL OF THE
 179 // TERMS AND CONDITIONS OF THIS AGREEMENT.
 180 // IF YOU DO NOT AGREE, DO NOT DOWNLOAD, INSTALL, COPY, DISTRIBUTE OR USE
 181 // THE DATA FILES OR SOFTWARE.
 182 //
 183 // COPYRIGHT AND PERMISSION NOTICE
 184 //
 185 // Copyright (c) 1991-2022 Unicode, Inc. All rights reserved.
 186 // Distributed under the Terms of Use in https://www.unicode.org/copyright.html.
 187 //
 188 // Permission is hereby granted, free of charge, to any person obtaining
 189 // a copy of the Unicode data files and any associated documentation
 190 // (the "Data Files") or Unicode software and any associated documentation
 191 // (the "Software") to deal in the Data Files or Software
 192 // without restriction, including without limitation the rights to use,
 193 // copy, modify, merge, publish, distribute, and/or sell copies of
 194 // the Data Files or Software, and to permit persons to whom the Data Files
 195 // or Software are furnished to do so, provided that either
 196 // (a) this copyright and permission notice appear with all copies
 197 // of the Data Files or Software, or
 198 // (b) this copyright and permission notice appear in associated
 199 // Documentation.
 200 //
 201 // THE DATA FILES AND SOFTWARE ARE PROVIDED "AS IS", WITHOUT WARRANTY OF
 202 // ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 203 // WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 204 // NONINFRINGEMENT OF THIRD PARTY RIGHTS.
 205 // IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS
 206 // NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL
 207 // DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
 208 // DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 209 // TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 210 // PERFORMANCE OF THE DATA FILES OR SOFTWARE.
 211 //
 212 // Except as contained in this notice, the name of a copyright holder
 213 // shall not be used in advertising or otherwise to promote the sale,
 214 // use or other dealings in these Data Files or Software without prior
 215 // written authorization of the copyright holder.
 216
 217 #ifndef _LIBCPP___FORMAT_ESCAPED_OUTPUT_TABLE_H
 218 #define _LIBCPP___FORMAT_ESCAPED_OUTPUT_TABLE_H
 219
 220 #include <__algorithm/ranges_upper_bound.h>
 221 #include <__config>
 222 #include <cstddef>
 223 #include <cstdint>
 224
 225 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 226 #  pragma GCC system_header
 227 #endif
 228
 229 _LIBCPP_BEGIN_NAMESPACE_STD
 230
 231 #if _LIBCPP_STD_VER >= 23
 232
 233 namespace __escaped_output_table {{
 234 {content}
 235 }} // namespace __escaped_output_table
 236
 237 #endif //_LIBCPP_STD_VER >= 23
 238
 239 _LIBCPP_END_NAMESPACE_STD
 240
 241 #endif // _LIBCPP___FORMAT_ESCAPED_OUTPUT_TABLE_H"""
 242
 243
 244 def property_ranges_to_table(ranges: list[PropertyRange]) -> list[Entry]:
 245     result = list[Entry]()
 246     high = -1
 247     for range in sorted(ranges, key=lambda x: x.lower):
 248         # Validate overlapping ranges
 249         assert range.lower > high
 250         high = range.upper
 251
 252         while True:
 253             e = Entry(range.lower, range.upper - range.lower)
 254             if e.offset <= 2047:
 255                 result.append(e)
 256                 break
 257             e.offset = 2047
 258             result.append(e)
 259             range.lower += 2048
 260     return result
 261
 262
 263 cpp_entrytemplate = "    0x{:08x}"
 264
 265
 266 def generate_cpp_data(ranges: list[PropertyRange], unallocated: int) -> str:
 267     result = StringIO()
 268     table = property_ranges_to_table(ranges)
 269     result.write(
 270         DATA_ARRAY_TEMPLATE.format(
 271             size=len(table),
 272             entries=",\n".join(
 273                 [cpp_entrytemplate.format(x.lower << 11 | x.offset) for x in table]
 274             ),
 275             unallocated=unallocated,
 276         )
 277     )
 278
 279     return result.getvalue()
 280
 281
 282 def generate_data_tables() -> str:
 283     """
 284     Generate Unicode data for [format.string.escaped]/2.2.1.2.1
 285     """
 286     derived_general_catagory_path = (
 287         Path(__file__).absolute().parent
 288         / "data"
 289         / "unicode"
 290         / "DerivedGeneralCategory.txt"
 291     )
 292     derived_core_catagory_path = (
 293         Path(__file__).absolute().parent
 294         / "data"
 295         / "unicode"
 296         / "DerivedCoreProperties.txt"
 297     )
 298
 299     properties = list()
 300     with derived_general_catagory_path.open(encoding="utf-8") as f:
 301         properties.extend(
 302             list(
 303                 filter(
 304                     filterGeneralProperty,
 305                     [x for line in f if (x := parsePropertyLine(line))],
 306                 )
 307             )
 308         )
 309     with derived_core_catagory_path.open(encoding="utf-8") as f:
 310         properties.extend(
 311             list(
 312                 filter(
 313                     filterCoreProperty,
 314                     [x for line in f if (x := parsePropertyLine(line))],
 315                 )
 316             )
 317         )
 318
 319     data = compactPropertyRanges(sorted(properties, key=lambda x: x.lower))
 320
 321     # The last entry is large. In Unicode 14 it contains the entries
 322     # 3134B..0FFFF 912564 elements
 323     # This are 446 entries of 1325 entries in the table.
 324     # Based on the nature of these entries it is expected they remain for the
 325     # forseeable future. Therefore we only store the lower bound of this section.
 326     #
 327     # When this region becomes substantially smaller we need to investigate
 328     # this design.
 329     assert data[-1].upper == 0x10FFFF
 330     assert data[-1].upper - data[-1].lower > 900000
 331
 332     return "\n".join([generate_cpp_data(data[:-1], data[-1].lower)])
 333
 334
 335 if __name__ == "__main__":
 336     if len(sys.argv) == 2:
 337         sys.stdout = open(sys.argv[1], "w")
 338     print(TABLES_HPP_TEMPLATE.lstrip().format(content=generate_data_tables()))