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