350 lines · python
1#!/usr/bin/env python2# ===----------------------------------------------------------------------===##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-exception7#8# ===----------------------------------------------------------------------===##9 10# The code is based on11# https://github.com/microsoft/STL/blob/main/tools/unicode_properties_parse/grapheme_break_property_data_gen.py12#13# Copyright (c) Microsoft Corporation.14# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception15 16from io import StringIO17from pathlib import Path18from dataclasses import dataclass19from typing import Optional20import re21import sys22 23 24@dataclass25class PropertyRange:26 lower: int = -127 upper: int = -128 prop: str = None29 30 31@dataclass32class Entry:33 lower: int = -134 offset: int = -135 36 37LINE_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_Table43def filterGeneralProperty(element: PropertyRange) -> Optional[PropertyRange]:44 if element.prop in ["Zs", "Zl", "Zp", "Cc", "Cf", "Cs", "Co", "Cn"]:45 return element46 return None47 48 49def 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.lower55 if upper_str is not None:56 result.upper = int(upper_str, base=16)57 return result58 59 else:60 return None61 62 63def 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't68 interesting anymore. The properties in the output are merged to aid69 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].lower78 and x.lower <= result[-1].upper + 179 ):80 result[-1].upper = max(result[-1].upper, x.upper)81 result[-1].prop += f" {x.prop}"82 continue83 result.append(x)84 return result85 86 87DATA_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.191/// CE is a Unicode encoding and C corresponds to a UCS scalar value whose92/// Unicode property General_Category has a value in the groups Separator (Z)93/// or Other (C), as described by table 12 of UAX #4494///95/// Separator (Z) consists of General_Category96/// - Space_Separator,97/// - Line_Separator,98/// - Paragraph_Separator.99///100/// Other (C) consists of General_Category101/// - Control,102/// - Format,103/// - Surrogate,104/// - Private_Use,105/// - Unassigned.106///107/// The data is generated from108/// - https://www.unicode.org/Public/UCD/latest/ucd/extracted/DerivedGeneralCategory.txt109///110/// The table is similar to the table111/// __extended_grapheme_custer_property_boundary::__entries112/// which explains the details of these classes. The only difference is this113/// 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 of118/// the range is lower bound + size. Note the code expects code units the fit119/// 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 are126/// either reserved or a noncharacter. Adding all these entries to the127/// lookup table would greatly increase the size of the table. Instead these128/// 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 escaped130/// unconditionally. This is also manually coded. See the generation script for131/// 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 155TABLES_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-exception162//163//===----------------------------------------------------------------------===//164 165// WARNING, this entire header is generated by166// utils/generate_escaped_output_table.py167// DO NOT MODIFY!168 169// UNICODE, INC. LICENSE AGREEMENT - DATA FILES AND SOFTWARE170//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.'S176// DATA FILES ("DATA FILES"), AND/OR SOFTWARE ("SOFTWARE"),177// YOU UNEQUIVOCALLY ACCEPT, AND AGREE TO BE BOUND BY, ALL OF THE178// TERMS AND CONDITIONS OF THIS AGREEMENT.179// IF YOU DO NOT AGREE, DO NOT DOWNLOAD, INSTALL, COPY, DISTRIBUTE OR USE180// THE DATA FILES OR SOFTWARE.181//182// COPYRIGHT AND PERMISSION NOTICE183//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 obtaining188// a copy of the Unicode data files and any associated documentation189// (the "Data Files") or Unicode software and any associated documentation190// (the "Software") to deal in the Data Files or Software191// without restriction, including without limitation the rights to use,192// copy, modify, merge, publish, distribute, and/or sell copies of193// the Data Files or Software, and to permit persons to whom the Data Files194// or Software are furnished to do so, provided that either195// (a) this copyright and permission notice appear with all copies196// of the Data Files or Software, or197// (b) this copyright and permission notice appear in associated198// Documentation.199//200// THE DATA FILES AND SOFTWARE ARE PROVIDED "AS IS", WITHOUT WARRANTY OF201// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE202// WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND203// NONINFRINGEMENT OF THIRD PARTY RIGHTS.204// IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS205// NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL206// DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,207// DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER208// TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR209// PERFORMANCE OF THE DATA FILES OR SOFTWARE.210//211// Except as contained in this notice, the name of a copyright holder212// shall not be used in advertising or otherwise to promote the sale,213// use or other dealings in these Data Files or Software without prior214// written authorization of the copyright holder.215 216#ifndef _LIBCPP___FORMAT_ESCAPED_OUTPUT_TABLE_H217#define _LIBCPP___FORMAT_ESCAPED_OUTPUT_TABLE_H218 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_header226#endif227 228_LIBCPP_BEGIN_NAMESPACE_STD229 230#if _LIBCPP_STD_VER >= 23231 232namespace __escaped_output_table {{233// clang-format off234{content}235// clang-format on236}} // namespace __escaped_output_table237 238#endif // _LIBCPP_STD_VER >= 23239 240_LIBCPP_END_NAMESPACE_STD241 242#endif // _LIBCPP___FORMAT_ESCAPED_OUTPUT_TABLE_H"""243 244 245def property_ranges_to_table(ranges: list[PropertyRange]) -> list[Entry]:246 result = list[Entry]()247 high = -1248 for range in sorted(ranges, key=lambda x: x.lower):249 # Validate overlapping ranges250 assert range.lower > high251 high = range.upper252 253 while True:254 e = Entry(range.lower, range.upper - range.lower)255 if e.offset <= 16383:256 result.append(e)257 break258 e.offset = 16383259 result.append(e)260 range.lower += 16384261 return result262 263 264cpp_entrytemplate = " 0x{:08x} /* {:08x} - {:08x} [{:>5}] */"265 266 267def generate_cpp_data(268 ranges: list[PropertyRange], unallocated: int, gap_lower: int, gap_upper: int269) -> 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 < 0x3FFFF275 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 table287 ]288 ),289 unallocated=unallocated,290 gap_lower=gap_lower,291 gap_upper=gap_upper,292 )293 )294 295 return result.getvalue()296 297 298def generate_data_tables() -> str:299 """300 Generate Unicode data for [format.string.escaped]/2.2.1.2.1301 """302 derived_general_catagory_path = (303 Path(__file__).absolute().parent304 / "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-256324 # 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 performance328 # by having fewer elements to search.329 # The exact entries may differ between Unicode versions. When these numbers330 # change the test needs to be updated too.331 # libcxx/test/libcxx/utilities/format/format.string/format.string.std/escaped_output.pass.cpp332 assert (data[-2].lower) == 0x323B0333 assert (data[-2].upper) == 0xE00FF334 assert (data[-1].lower) == 0xE01F0335 assert (data[-1].upper) == 0x10FFFF336 337 return "\n".join(338 [339 generate_cpp_data(340 data[:-2], data[-2].lower, data[-2].upper + 1, data[-1].lower - 1341 )342 ]343 )344 345 346if __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()))350