GeneratorUtil.h 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635
  1. /*
  2. * Copyright (c) 2021, Tim Flynn <trflynn89@serenityos.org>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #pragma once
  7. #include <AK/Format.h>
  8. #include <AK/HashFunctions.h>
  9. #include <AK/HashMap.h>
  10. #include <AK/JsonValue.h>
  11. #include <AK/LexicalPath.h>
  12. #include <AK/NumericLimits.h>
  13. #include <AK/Optional.h>
  14. #include <AK/QuickSort.h>
  15. #include <AK/SourceGenerator.h>
  16. #include <AK/String.h>
  17. #include <AK/StringBuilder.h>
  18. #include <AK/StringView.h>
  19. #include <AK/Traits.h>
  20. #include <AK/Vector.h>
  21. #include <LibCore/DirIterator.h>
  22. #include <LibCore/File.h>
  23. #include <LibCore/Stream.h>
  24. #include <LibUnicode/Locale.h>
  25. template<class T>
  26. inline constexpr bool StorageTypeIsList = false;
  27. template<class T>
  28. inline constexpr bool StorageTypeIsList<Vector<T>> = true;
  29. template<typename T>
  30. concept IntegralOrEnum = Integral<T> || Enum<T>;
  31. template<IntegralOrEnum T>
  32. struct AK::Traits<Vector<T>> : public GenericTraits<Vector<T>> {
  33. static unsigned hash(Vector<T> const& list)
  34. {
  35. auto hash = int_hash(static_cast<u32>(list.size()));
  36. for (auto value : list) {
  37. if constexpr (Enum<T>)
  38. hash = pair_int_hash(hash, to_underlying(value));
  39. else
  40. hash = pair_int_hash(hash, value);
  41. }
  42. return hash;
  43. }
  44. };
  45. template<typename StorageType, typename IndexType>
  46. class UniqueStorage {
  47. public:
  48. IndexType ensure(StorageType value)
  49. {
  50. // We maintain a set of unique values in two structures: a vector which stores the values in
  51. // the order they are added, and a hash map which maps that value to its index in the vector.
  52. // The vector is to ensure the values are generated in an easily known order, and the map is
  53. // to allow quickly deciding if a value is actually unique (otherwise, we'd have to linearly
  54. // search the vector for each value).
  55. //
  56. // Also note that index 0 will be reserved for the default-initialized value, so the index
  57. // returned from this method is actually the real index in the vector + 1.
  58. if (auto index = m_storage_indices.get(value); index.has_value())
  59. return *index;
  60. m_storage.append(move(value));
  61. size_t index = m_storage.size();
  62. VERIFY(index < NumericLimits<IndexType>::max());
  63. auto storage_index = static_cast<IndexType>(index);
  64. m_storage_indices.set(m_storage.last(), storage_index);
  65. return storage_index;
  66. }
  67. StorageType const& get(IndexType index) const
  68. {
  69. if (index == 0) {
  70. static StorageType empty {};
  71. return empty;
  72. }
  73. VERIFY(index <= m_storage.size());
  74. return m_storage.at(index - 1);
  75. }
  76. void generate(SourceGenerator& generator, StringView type, StringView name, size_t max_values_per_row) requires(!StorageTypeIsList<StorageType>)
  77. {
  78. generator.set("type"sv, type);
  79. generator.set("name"sv, name);
  80. generator.set("size"sv, String::number(m_storage.size()));
  81. generator.append(R"~~~(
  82. static constexpr Array<@type@, @size@ + 1> @name@ { {
  83. {})~~~");
  84. size_t values_in_current_row = 1;
  85. for (auto const& value : m_storage) {
  86. if (values_in_current_row++ > 0)
  87. generator.append(", ");
  88. if constexpr (IsSame<StorageType, String>)
  89. generator.append(String::formatted("\"{}\"sv", value));
  90. else
  91. generator.append(String::formatted("{}", value));
  92. if (values_in_current_row == max_values_per_row) {
  93. values_in_current_row = 0;
  94. generator.append(",\n ");
  95. }
  96. }
  97. generator.append(R"~~~(
  98. } };
  99. )~~~");
  100. }
  101. void generate(SourceGenerator& generator, StringView type, StringView name) requires(StorageTypeIsList<StorageType>)
  102. {
  103. generator.set("type"sv, type);
  104. generator.set("name"sv, name);
  105. for (size_t i = 0; i < m_storage.size(); ++i) {
  106. auto const& list = m_storage[i];
  107. generator.set("index"sv, String::number(i));
  108. generator.set("size"sv, String::number(list.size()));
  109. generator.append(R"~~~(
  110. static constexpr Array<@type@, @size@> @name@@index@ { {)~~~");
  111. bool first = true;
  112. for (auto const& value : list) {
  113. generator.append(first ? " "sv : ", "sv);
  114. generator.append(String::formatted("{}", value));
  115. first = false;
  116. }
  117. generator.append(" } };");
  118. }
  119. generator.set("size"sv, String::number(m_storage.size()));
  120. generator.append(R"~~~(
  121. static constexpr Array<Span<@type@ const>, @size@ + 1> @name@ { {
  122. {})~~~");
  123. constexpr size_t max_values_per_row = 10;
  124. size_t values_in_current_row = 1;
  125. for (size_t i = 0; i < m_storage.size(); ++i) {
  126. if (values_in_current_row++ > 0)
  127. generator.append(", ");
  128. generator.set("index"sv, String::number(i));
  129. generator.append("@name@@index@.span()");
  130. if (values_in_current_row == max_values_per_row) {
  131. values_in_current_row = 0;
  132. generator.append(",\n ");
  133. }
  134. }
  135. generator.append(R"~~~(
  136. } };
  137. )~~~");
  138. }
  139. // clang-format off
  140. // clang-format gets confused by the requires() clauses above, and formats this section very weirdly.
  141. protected:
  142. Vector<StorageType> m_storage;
  143. HashMap<StorageType, IndexType> m_storage_indices;
  144. // clang-format on
  145. };
  146. template<typename StringIndexType>
  147. class UniqueStringStorage : public UniqueStorage<String, StringIndexType> {
  148. using Base = UniqueStorage<String, StringIndexType>;
  149. public:
  150. // The goal of the string table generator is to ensure the table is located within the read-only
  151. // section of the shared library. If StringViews are generated directly, the table will be located
  152. // in the initialized data section. So instead, we generate run-length encoded (RLE) arrays to
  153. // represent the strings.
  154. void generate(SourceGenerator& generator) const
  155. {
  156. constexpr size_t max_values_per_row = 300;
  157. size_t values_in_current_row = 0;
  158. auto append_hex_value = [&](auto value) {
  159. if (values_in_current_row++ > 0)
  160. generator.append(", ");
  161. generator.append(String::formatted("{:#x}", value));
  162. if (values_in_current_row == max_values_per_row) {
  163. values_in_current_row = 0;
  164. generator.append(",\n ");
  165. }
  166. };
  167. Vector<u32> string_indices;
  168. string_indices.ensure_capacity(Base::m_storage.size());
  169. u32 next_index { 0 };
  170. for (auto const& string : Base::m_storage) {
  171. // Ensure the string length may be encoded as two u8s.
  172. VERIFY(string.length() <= NumericLimits<u16>::max());
  173. string_indices.unchecked_append(next_index);
  174. next_index += string.length() + 2;
  175. }
  176. generator.set("size", String::number(next_index));
  177. generator.append(R"~~~(
  178. static constexpr Array<u8, @size@> s_encoded_strings { {
  179. )~~~");
  180. for (auto const& string : Base::m_storage) {
  181. auto length = string.length();
  182. append_hex_value((length & 0xff00) >> 8);
  183. append_hex_value(length & 0x00ff);
  184. for (auto ch : string)
  185. append_hex_value(static_cast<u8>(ch));
  186. }
  187. generator.append(R"~~~(
  188. } };
  189. )~~~");
  190. generator.set("size", String::number(string_indices.size()));
  191. generator.append(R"~~~(
  192. static constexpr Array<u32, @size@> s_encoded_string_indices { {
  193. )~~~");
  194. values_in_current_row = 0;
  195. for (auto index : string_indices)
  196. append_hex_value(index);
  197. generator.append(R"~~~(
  198. } };
  199. static constexpr StringView decode_string(size_t index)
  200. {
  201. if (index == 0)
  202. return {};
  203. index = s_encoded_string_indices[index - 1];
  204. auto length_high = s_encoded_strings[index];
  205. auto length_low = s_encoded_strings[index + 1];
  206. size_t length = (length_high << 8) | length_low;
  207. if (length == 0)
  208. return {};
  209. auto const* start = &s_encoded_strings[index + 2];
  210. return { reinterpret_cast<char const*>(start), length };
  211. }
  212. )~~~");
  213. }
  214. };
  215. struct Alias {
  216. String name;
  217. String alias;
  218. };
  219. template<typename StringIndexType>
  220. struct CanonicalLanguageID {
  221. static ErrorOr<CanonicalLanguageID> parse(UniqueStringStorage<StringIndexType>& unique_strings, StringView language)
  222. {
  223. CanonicalLanguageID language_id {};
  224. auto segments = language.split_view('-');
  225. VERIFY(!segments.is_empty());
  226. size_t index = 0;
  227. if (Unicode::is_unicode_language_subtag(segments[index])) {
  228. language_id.language = unique_strings.ensure(segments[index]);
  229. if (segments.size() == ++index)
  230. return language_id;
  231. } else {
  232. return Error::from_string_literal("Expected language subtag");
  233. }
  234. if (Unicode::is_unicode_script_subtag(segments[index])) {
  235. language_id.script = unique_strings.ensure(segments[index]);
  236. if (segments.size() == ++index)
  237. return language_id;
  238. }
  239. if (Unicode::is_unicode_region_subtag(segments[index])) {
  240. language_id.region = unique_strings.ensure(segments[index]);
  241. if (segments.size() == ++index)
  242. return language_id;
  243. }
  244. while (index < segments.size()) {
  245. if (!Unicode::is_unicode_variant_subtag(segments[index]))
  246. return Error::from_string_literal("Expected variant subtag");
  247. language_id.variants.append(unique_strings.ensure(segments[index++]));
  248. }
  249. return language_id;
  250. }
  251. StringIndexType language { 0 };
  252. StringIndexType script { 0 };
  253. StringIndexType region { 0 };
  254. Vector<StringIndexType> variants {};
  255. };
  256. inline ErrorOr<NonnullOwnPtr<Core::Stream::BufferedFile>> open_file(StringView path, Core::Stream::OpenMode mode)
  257. {
  258. if (path.is_empty())
  259. return Error::from_string_literal("Provided path is empty, please provide all command line options");
  260. auto file = TRY(Core::Stream::File::open(path, mode));
  261. return Core::Stream::BufferedFile::create(move(file));
  262. }
  263. inline ErrorOr<JsonValue> read_json_file(StringView path)
  264. {
  265. auto file = TRY(open_file(path, Core::Stream::OpenMode::Read));
  266. StringBuilder builder;
  267. Array<u8, 4096> buffer;
  268. // FIXME: When Core::Stream supports reading an entire file, use that.
  269. while (TRY(file->can_read_line())) {
  270. auto bytes_read = TRY(file->read(buffer));
  271. TRY(builder.try_append(StringView { bytes_read }));
  272. }
  273. return JsonValue::from_string(builder.build());
  274. }
  275. inline ErrorOr<Core::DirIterator> path_to_dir_iterator(String path, StringView subpath = "main"sv)
  276. {
  277. LexicalPath lexical_path(move(path));
  278. if (!subpath.is_empty())
  279. lexical_path = lexical_path.append(subpath);
  280. Core::DirIterator iterator(lexical_path.string(), Core::DirIterator::SkipParentAndBaseDir);
  281. if (iterator.has_error()) {
  282. // FIXME: Make Core::DirIterator return a StringView for its error
  283. // string.
  284. auto const* error_string_ptr = iterator.error_string();
  285. return Error::from_string_view({ error_string_ptr, strlen(error_string_ptr) });
  286. }
  287. return iterator;
  288. }
  289. inline ErrorOr<String> next_path_from_dir_iterator(Core::DirIterator& iterator)
  290. {
  291. auto next_path = iterator.next_full_path();
  292. if (iterator.has_error()) {
  293. // FIXME: Make Core::DirIterator return a StringView for its error
  294. // string.
  295. auto const* error_string_ptr = iterator.error_string();
  296. return Error::from_string_view({ error_string_ptr, strlen(error_string_ptr) });
  297. }
  298. return next_path;
  299. }
  300. inline void ensure_from_string_types_are_generated(SourceGenerator& generator)
  301. {
  302. static bool generated_from_string_types = false;
  303. if (generated_from_string_types)
  304. return;
  305. generator.append(R"~~~(
  306. template <typename ValueType>
  307. struct HashValuePair {
  308. unsigned hash { 0 };
  309. ValueType value {};
  310. };
  311. template <typename ValueType>
  312. struct HashValueComparator
  313. {
  314. constexpr int operator()(unsigned hash, HashValuePair<ValueType> const& pair)
  315. {
  316. if (hash > pair.hash)
  317. return 1;
  318. if (hash < pair.hash)
  319. return -1;
  320. return 0;
  321. }
  322. };
  323. )~~~");
  324. generated_from_string_types = true;
  325. }
  326. template<typename ValueType>
  327. using HashValueMap = HashMap<unsigned, ValueType>;
  328. struct ValueFromStringOptions {
  329. Optional<StringView> return_type {};
  330. StringView return_format { "{}"sv };
  331. CaseSensitivity sensitivity { CaseSensitivity::CaseSensitive };
  332. };
  333. template<typename ValueType>
  334. void generate_value_from_string(SourceGenerator& generator, StringView method_name_format, StringView value_type, StringView value_name, HashValueMap<ValueType> hashes, ValueFromStringOptions options = {})
  335. {
  336. ensure_from_string_types_are_generated(generator);
  337. generator.set("method_name", String::formatted(method_name_format, value_name));
  338. generator.set("value_type", value_type);
  339. generator.set("value_name", value_name);
  340. generator.set("return_type", options.return_type.has_value() ? *options.return_type : value_type);
  341. generator.set("size", String::number(hashes.size()));
  342. generator.append(R"~~~(
  343. Optional<@return_type@> @method_name@(StringView key)
  344. {
  345. constexpr Array<HashValuePair<@value_type@>, @size@> hash_pairs { {
  346. )~~~");
  347. auto hash_keys = hashes.keys();
  348. quick_sort(hash_keys);
  349. constexpr size_t max_values_per_row = 10;
  350. size_t values_in_current_row = 0;
  351. for (auto hash_key : hash_keys) {
  352. if (values_in_current_row++ > 0)
  353. generator.append(" ");
  354. if constexpr (IsIntegral<ValueType>)
  355. generator.set("value"sv, String::number(hashes.get(hash_key).value()));
  356. else
  357. generator.set("value"sv, String::formatted("{}::{}", value_type, hashes.get(hash_key).value()));
  358. generator.set("hash"sv, String::number(hash_key));
  359. generator.append("{ @hash@U, @value@ },"sv);
  360. if (values_in_current_row == max_values_per_row) {
  361. generator.append("\n ");
  362. values_in_current_row = 0;
  363. }
  364. }
  365. generator.set("return_statement", String::formatted(options.return_format, "value->value"sv));
  366. generator.append(R"~~~(
  367. } };
  368. )~~~");
  369. if (options.sensitivity == CaseSensitivity::CaseSensitive) {
  370. generator.append(R"~~~(
  371. auto hash = key.hash();
  372. )~~~");
  373. } else {
  374. generator.append(R"~~~(
  375. auto hash = CaseInsensitiveStringViewTraits::hash(key);
  376. )~~~");
  377. }
  378. generator.append(R"~~~(
  379. if (auto const* value = binary_search(hash_pairs, hash, nullptr, HashValueComparator<@value_type@> {}))
  380. return @return_statement@;
  381. return {};
  382. }
  383. )~~~");
  384. }
  385. template<typename IdentifierFormatter>
  386. void generate_value_to_string(SourceGenerator& generator, StringView method_name_format, StringView value_type, StringView value_name, IdentifierFormatter&& format_identifier, Span<String const> values)
  387. {
  388. generator.set("method_name", String::formatted(method_name_format, value_name));
  389. generator.set("value_type", value_type);
  390. generator.set("value_name", value_name);
  391. generator.append(R"~~~(
  392. StringView @method_name@(@value_type@ @value_name@)
  393. {
  394. using enum @value_type@;
  395. switch (@value_name@) {)~~~");
  396. for (auto const& value : values) {
  397. generator.set("enum_value", format_identifier(value_type, value));
  398. generator.set("string_value", value);
  399. generator.append(R"~~~(
  400. case @enum_value@:
  401. return "@string_value@"sv;)~~~");
  402. }
  403. generator.append(R"~~~(
  404. }
  405. VERIFY_NOT_REACHED();
  406. }
  407. )~~~");
  408. }
  409. template<typename IdentifierFormatter>
  410. void generate_enum(SourceGenerator& generator, IdentifierFormatter&& format_identifier, StringView name, StringView default_, Vector<String>& values, Vector<Alias> aliases = {})
  411. {
  412. quick_sort(values, [](auto const& value1, auto const& value2) { return value1.to_lowercase() < value2.to_lowercase(); });
  413. quick_sort(aliases, [](auto const& alias1, auto const& alias2) { return alias1.alias.to_lowercase() < alias2.alias.to_lowercase(); });
  414. generator.set("name", name);
  415. generator.set("underlying", ((values.size() + !default_.is_empty()) < 256) ? "u8"sv : "u16"sv);
  416. generator.append(R"~~~(
  417. enum class @name@ : @underlying@ {)~~~");
  418. if (!default_.is_empty()) {
  419. generator.set("default", default_);
  420. generator.append(R"~~~(
  421. @default@,)~~~");
  422. }
  423. for (auto const& value : values) {
  424. generator.set("value", format_identifier(name, value));
  425. generator.append(R"~~~(
  426. @value@,)~~~");
  427. }
  428. for (auto const& alias : aliases) {
  429. generator.set("alias", format_identifier(name, alias.alias));
  430. generator.set("value", format_identifier(name, alias.name));
  431. generator.append(R"~~~(
  432. @alias@ = @value@,)~~~");
  433. }
  434. generator.append(R"~~~(
  435. };
  436. )~~~");
  437. }
  438. template<typename LocalesType, typename IdentifierFormatter, typename ListFormatter>
  439. void generate_mapping(SourceGenerator& generator, LocalesType const& locales, StringView type, StringView name, StringView format, IdentifierFormatter&& format_identifier, ListFormatter&& format_list)
  440. {
  441. auto format_mapping_name = [&](StringView format, StringView name) {
  442. String mapping_name;
  443. if constexpr (IsNullPointer<IdentifierFormatter>)
  444. mapping_name = name.replace("-"sv, "_"sv, ReplaceMode::All);
  445. else
  446. mapping_name = format_identifier(type, name);
  447. return String::formatted(format, mapping_name.to_lowercase());
  448. };
  449. Vector<String> mapping_names;
  450. for (auto const& locale : locales) {
  451. String mapping_name;
  452. if constexpr (requires { locale.key; }) {
  453. mapping_name = format_mapping_name(format, locale.key);
  454. format_list(mapping_name, locale.value);
  455. } else {
  456. mapping_name = format_mapping_name(format, locale);
  457. format_list(mapping_name, locale);
  458. }
  459. mapping_names.append(move(mapping_name));
  460. }
  461. quick_sort(mapping_names);
  462. generator.set("type", type);
  463. generator.set("name", name);
  464. generator.set("size", String::number(locales.size()));
  465. generator.append(R"~~~(
  466. static constexpr Array<Span<@type@ const>, @size@> @name@ { {
  467. )~~~");
  468. constexpr size_t max_values_per_row = 10;
  469. size_t values_in_current_row = 0;
  470. for (auto& mapping_name : mapping_names) {
  471. if (values_in_current_row++ > 0)
  472. generator.append(" ");
  473. generator.set("name", move(mapping_name));
  474. generator.append("@name@.span(),");
  475. if (values_in_current_row == max_values_per_row) {
  476. values_in_current_row = 0;
  477. generator.append("\n ");
  478. }
  479. }
  480. generator.append(R"~~~(
  481. } };
  482. )~~~");
  483. }
  484. template<typename T>
  485. void generate_available_values(SourceGenerator& generator, StringView name, Vector<T> const& values, Vector<Alias> const& aliases = {}, Function<bool(StringView)> value_filter = {})
  486. {
  487. generator.set("name", name);
  488. generator.append(R"~~~(
  489. Span<StringView const> @name@()
  490. {
  491. static constexpr auto values = Array {)~~~");
  492. bool first = true;
  493. for (auto const& value : values) {
  494. if (value_filter && !value_filter(value))
  495. continue;
  496. generator.append(first ? " "sv : ", "sv);
  497. first = false;
  498. if (auto it = aliases.find_if([&](auto const& alias) { return alias.alias == value; }); it != aliases.end())
  499. generator.append(String::formatted("\"{}\"sv", it->name));
  500. else
  501. generator.append(String::formatted("\"{}\"sv", value));
  502. }
  503. generator.append(R"~~~( };
  504. return values.span();
  505. }
  506. )~~~");
  507. }