310 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 prop: int = -136 37 38LINE_REGEX = re.compile(39 r"^(?P<lower>[0-9A-F]{4,5})(?:\.\.(?P<upper>[0-9A-F]{4,5}))?\s*;\s*InCB;\s*(?P<prop>\w+)"40)41 42def parsePropertyLine(inputLine: str) -> Optional[PropertyRange]:43 result = PropertyRange()44 if m := LINE_REGEX.match(inputLine):45 lower_str, upper_str, result.prop = m.group("lower", "upper", "prop")46 result.lower = int(lower_str, base=16)47 result.upper = result.lower48 if upper_str is not None:49 result.upper = int(upper_str, base=16)50 return result51 52 else:53 return None54 55 56 57def compactPropertyRanges(input: list[PropertyRange]) -> list[PropertyRange]:58 """59 Merges consecutive ranges with the same property to one range.60 61 Merging the ranges results in fewer ranges in the output table,62 reducing binary and improving lookup performance.63 """64 result = list()65 for x in input:66 if (67 len(result)68 and result[-1].prop == x.prop69 and result[-1].upper + 1 == x.lower70 ):71 result[-1].upper = x.upper72 continue73 result.append(x)74 return result75 76 77PROP_VALUE_ENUMERATOR_TEMPLATE = " __{}"78PROP_VALUE_ENUM_TEMPLATE = """79enum class __property : uint8_t {{80 // Values generated from the data files.81{enumerators},82 83 // The code unit has none of above properties.84 __none85}};86"""87 88DATA_ARRAY_TEMPLATE = """89/// The entries of the indic conjunct break property table.90///91/// The data is generated from92/// - https://www.unicode.org/Public/UCD/latest/ucd/DerivedCoreProperties.txt93///94/// The data has 3 values95/// - bits [0, 1] The property. One of the values generated from the datafiles96/// of \\ref __property97/// - bits [2, 10] The size of the range.98/// - bits [11, 31] The lower bound code point of the range. The upper bound of99/// the range is lower bound + size.100///101/// The 9 bits for the size allow a maximum range of 512 elements. Some ranges102/// in the Unicode tables are larger. They are stored in multiple consecutive103/// ranges in the data table. An alternative would be to store the sizes in a104/// separate 16-bit value. The original MSVC STL code had such an approach, but105/// this approach uses less space for the data and is about 4% faster in the106/// following benchmark.107/// libcxx/benchmarks/std_format_spec_string_unicode.bench.cpp108// clang-format off109_LIBCPP_HIDE_FROM_ABI inline constexpr uint32_t __entries[{size}] = {{110{entries}}};111// clang-format on112 113/// Returns the indic conjuct break property of a code point.114[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr __property __get_property(const char32_t __code_point) noexcept {{115 // The algorithm searches for the upper bound of the range and, when found,116 // steps back one entry. This algorithm is used since the code point can be117 // anywhere in the range. After a lower bound is found the next step is to118 // compare whether the code unit is indeed in the range.119 //120 // Since the entry contains a code unit, size, and property the code point121 // being sought needs to be adjusted. Just shifting the code point to the122 // proper position doesn't work; suppose an entry has property 0, size 1,123 // and lower bound 3. This results in the entry 0x1810.124 // When searching for code point 3 it will search for 0x1800, find 0x1810125 // and moves to the previous entry. Thus the lower bound value will never126 // be found.127 // The simple solution is to set the bits belonging to the property and128 // size. Then the upper bound for code point 3 will return the entry after129 // 0x1810. After moving to the previous entry the algorithm arrives at the130 // correct entry.131 ptrdiff_t __i = std::ranges::upper_bound(__entries, (__code_point << 11) | 0x7ffu) - __entries;132 if (__i == 0)133 return __property::__none;134 135 --__i;136 uint32_t __upper_bound = (__entries[__i] >> 11) + ((__entries[__i] >> 2) & 0b1'1111'1111);137 if (__code_point <= __upper_bound)138 return static_cast<__property>(__entries[__i] & 0b11);139 140 return __property::__none;141}}142"""143 144MSVC_FORMAT_UCD_TABLES_HPP_TEMPLATE = """145// -*- C++ -*-146//===----------------------------------------------------------------------===//147//148// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.149// See https://llvm.org/LICENSE.txt for license information.150// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception151//152//===----------------------------------------------------------------------===//153 154// WARNING, this entire header is generated by155// utils/generate_indic_conjunct_break_table.py156// DO NOT MODIFY!157 158// UNICODE, INC. LICENSE AGREEMENT - DATA FILES AND SOFTWARE159//160// See Terms of Use <https://www.unicode.org/copyright.html>161// for definitions of Unicode Inc.'s Data Files and Software.162//163// NOTICE TO USER: Carefully read the following legal agreement.164// BY DOWNLOADING, INSTALLING, COPYING OR OTHERWISE USING UNICODE INC.'S165// DATA FILES ("DATA FILES"), AND/OR SOFTWARE ("SOFTWARE"),166// YOU UNEQUIVOCALLY ACCEPT, AND AGREE TO BE BOUND BY, ALL OF THE167// TERMS AND CONDITIONS OF THIS AGREEMENT.168// IF YOU DO NOT AGREE, DO NOT DOWNLOAD, INSTALL, COPY, DISTRIBUTE OR USE169// THE DATA FILES OR SOFTWARE.170//171// COPYRIGHT AND PERMISSION NOTICE172//173// Copyright (c) 1991-2022 Unicode, Inc. All rights reserved.174// Distributed under the Terms of Use in https://www.unicode.org/copyright.html.175//176// Permission is hereby granted, free of charge, to any person obtaining177// a copy of the Unicode data files and any associated documentation178// (the "Data Files") or Unicode software and any associated documentation179// (the "Software") to deal in the Data Files or Software180// without restriction, including without limitation the rights to use,181// copy, modify, merge, publish, distribute, and/or sell copies of182// the Data Files or Software, and to permit persons to whom the Data Files183// or Software are furnished to do so, provided that either184// (a) this copyright and permission notice appear with all copies185// of the Data Files or Software, or186// (b) this copyright and permission notice appear in associated187// Documentation.188//189// THE DATA FILES AND SOFTWARE ARE PROVIDED "AS IS", WITHOUT WARRANTY OF190// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE191// WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND192// NONINFRINGEMENT OF THIRD PARTY RIGHTS.193// IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS194// NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL195// DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,196// DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER197// TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR198// PERFORMANCE OF THE DATA FILES OR SOFTWARE.199//200// Except as contained in this notice, the name of a copyright holder201// shall not be used in advertising or otherwise to promote the sale,202// use or other dealings in these Data Files or Software without prior203// written authorization of the copyright holder.204 205#ifndef _LIBCPP___FORMAT_INDIC_CONJUNCT_BREAK_TABLE_H206#define _LIBCPP___FORMAT_INDIC_CONJUNCT_BREAK_TABLE_H207 208#include <__algorithm/ranges_upper_bound.h>209#include <__config>210#include <__cstddef/ptrdiff_t.h>211#include <__iterator/access.h>212#include <cstdint>213 214#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)215# pragma GCC system_header216#endif217 218_LIBCPP_BEGIN_NAMESPACE_STD219 220#if _LIBCPP_STD_VER >= 20221 222namespace __indic_conjunct_break {{223{content}224}} // namespace __indic_conjunct_break225 226#endif // _LIBCPP_STD_VER >= 20227 228_LIBCPP_END_NAMESPACE_STD229 230#endif // _LIBCPP___FORMAT_INDIC_CONJUNCT_BREAK_TABLE_H"""231 232 233def property_ranges_to_table(234 ranges: list[PropertyRange], props: list[str]235) -> list[Entry]:236 assert len(props) < 4237 result = list[Entry]()238 high = -1239 for range in sorted(ranges, key=lambda x: x.lower):240 # Validate overlapping ranges241 assert range.lower > high242 high = range.upper243 244 while True:245 e = Entry(range.lower, range.upper - range.lower, props.index(range.prop))246 if e.offset <= 511:247 result.append(e)248 break249 e.offset = 511250 result.append(e)251 range.lower += 512252 return result253 254 255cpp_entrytemplate = " 0x{:08x}"256 257 258def generate_cpp_data(prop_name: str, ranges: list[PropertyRange]) -> str:259 result = StringIO()260 prop_values = sorted(set(x.prop for x in ranges))261 table = property_ranges_to_table(ranges, prop_values)262 enumerator_values = [PROP_VALUE_ENUMERATOR_TEMPLATE.format(x) for x in prop_values]263 result.write(264 PROP_VALUE_ENUM_TEMPLATE.format(enumerators=",\n".join(enumerator_values))265 )266 result.write(267 DATA_ARRAY_TEMPLATE.format(268 prop_name=prop_name,269 size=len(table),270 entries=",\n".join(271 [272 cpp_entrytemplate.format(x.lower << 11 | x.offset << 2 | x.prop)273 for x in table274 ]275 ),276 )277 )278 279 return result.getvalue()280 281 282def generate_data_tables() -> str:283 """284 Generate Unicode data for inclusion into <format> from285 - https://www.unicode.org/Public/UCD/latest/ucd/DerivedCoreProperties.txt286 287 These files are expected to be stored in the same directory as this script.288 """289 root = Path(__file__).absolute().parent / "data" / "unicode"290 derived_core_path = root / "DerivedCoreProperties.txt"291 292 indic_conjunct_break = list()293 with derived_core_path.open(encoding="utf-8") as f:294 indic_conjunct_break_ranges = compactPropertyRanges(295 [x for line in f if (x := parsePropertyLine(line))]296 )297 298 indic_conjunct_break_data = generate_cpp_data("Grapheme_Break", indic_conjunct_break_ranges)299 return "\n".join([indic_conjunct_break_data])300 301 302if __name__ == "__main__":303 if len(sys.argv) == 2:304 sys.stdout = open(sys.argv[1], "w")305 print(306 MSVC_FORMAT_UCD_TABLES_HPP_TEMPLATE.lstrip().format(307 content=generate_data_tables()308 )309 )310