dymokomi/luce-browser-foundation
Source of release 0.6.1
0.6.1 / src / ak / fly_string.lucb
#==============================================================================================
#
# fly_string - FlyString: interned UTF-8 strings that compare by identity
#
# DESCRIPTION:
# Port of AK/FlyString.h (lines 1-159) and AK/FlyString.cpp (lines 1-217).
#
# A FlyString is a StringBase: short strings inline, longer ones a StringData marked as a
# fly string and registered in the all_fly_strings table, so equal FlyStrings share one
# StringData and `==` is a comparison of the eight bytes. The table is a module global;
# its HashTable calls are gathered in the fly_string_table_* helpers, which compare the
# found iterator with end() as the C++ does.
#
# The table outlives every allocator scope (a test's buffer, an arena), so the table and
# every interned StringData live in `memory.heap`, whatever allocator is current:
# interning copies the string's bytes there (the C++ interns the String's own data), and
# the table only changes under `with memory.heap:`. A FlyString is therefore valid
# wherever it is kept, including module globals such as generated FlyString caches.
#
# FIXME: interned strings are never released. In the C++, StringData is reference
# counted and its destructor removes it from the table (did_destroy_fly_string_data);
# here nothing is counted or destroyed. Making the entries weak needs the interned data
# in the collected heap with a blob finalizer that calls did_destroy_fly_string_data,
# which gc does not have (cells only), and a heap_destroy that drops its entries; until
# then the table grows by every distinct long string interned, as a static Singleton
# that never shrinks. See docs/regions/INTEGRATION.md.
#
#==============================================================================================
# mark: The table ===============================================================================
## Ported from AK/FlyString.cpp:18 AK::FlyStringTableHashTraits::hash.
pub func fly_string_table_hash_traits_hash(string: const StringData*?) -> u32:
return string_data_hash(string else trap("VERIFY: null StringData in the FlyString table"))
## Ported from AK/FlyString.cpp:19 AK::FlyStringTableHashTraits::equals.
pub func fly_string_table_hash_traits_equals(a: const StringData*?, b: const StringData*?) -> bool:
return string_data_eq(a else trap("VERIFY: null StringData"), b else trap("VERIFY: null StringData"))
## Ported from AK/FlyString.cpp:20 AK::FlyStringTableHashTraits::may_have_slow_equality_check.
pub func fly_string_table_hash_traits_may_have_slow_equality_check() -> bool:
return true
## `static Singleton<HashTable<StringData const*, FlyStringTableHashTraits>> table`. Its
## buckets and entries are in `memory.heap` (see the header).
var s_all_fly_strings: HashTable[const StringData*?, FlyStringTableHashTraits]
## Ported from AK/FlyString.cpp:23 AK::all_fly_strings.
func all_fly_strings() -> HashTable[const StringData*?, FlyStringTableHashTraits]*:
return &s_all_fly_strings
## The captures of the `[&](auto& entry) { return entry->bytes_as_string_view() == string; }`
## predicate of FlyString::from_utf8.
struct FlyStringTableViewPredicate:
var string: StringView
# The predicate's body: whether the interned `entry` holds the bytes of `string`.
func fly_string_table_view_predicate_call(context: void*?, entry: const (const StringData*?)*) -> bool:
let captures = (const FlyStringTableViewPredicate*)(context else trap("FlyString: no captures"))
let view = string_data_bytes_as_string_view(*entry else trap("VERIFY: null StringData"))
return string_view_eq_string_view(&view, captures.string)
## `all_fly_strings().find(hash, predicate)`: the interned StringData equal to `string`, if any.
func fly_string_table_find_view(string: StringView) -> const StringData*?:
var captures = FlyStringTableViewPredicate(string = string)
let predicate = Function1[const (const StringData*?)*, bool](call = fly_string_table_view_predicate_call, context = &captures)
var it = hash_table_find_u32_tt_unary_predicate(all_fly_strings(), string_view_hash(&string), predicate)
if hash_table_iterator_eq(&it, hash_table_end(all_fly_strings())):
return none
return *hash_table_iterator_deref(&it)
## `all_fly_strings().find(data)`: the interned StringData equal to `data`, if any.
func fly_string_table_find(data: const StringData*) -> const StringData*?:
var it = hash_table_find_t(all_fly_strings(), (const StringData*?)data)
if hash_table_iterator_eq(&it, hash_table_end(all_fly_strings())):
return none
return *hash_table_iterator_deref(&it)
## Ported from AK/FlyString.cpp:210 AK::Detail::did_destroy_fly_string_data: drops a StringData
## from the table when it dies (the StringData destructor's call; nothing makes it yet, see the
## header's FIXME).
pub func did_destroy_fly_string_data(string_data: const StringData*):
with memory.heap:
_ = hash_table_remove_t(all_fly_strings(), string_data)
## Adds a copy of `data`'s bytes to the table and answers it (addition: the C++ adds `data`
## itself). The copy and the table's buckets come from `memory.heap`, which outlives any
## allocator scope, so an interned string stays valid after the allocator that was current
## when it was interned is gone. The copy is never a substring, so it points at nothing else.
func fly_string_table_add(data: const StringData*) -> const StringData*:
let bytes = string_data_bytes(data)
with memory.heap:
var buffer: u8*? = none
let interned = string_data_create_uninitialized(bytes.length, &buffer) else trap("MUST: intern a FlyString")
copy_bytes(u8[](buffer else trap("VERIFY: interned bytes"), bytes.length), bytes)
_ = hash_table_set(all_fly_strings(), (const StringData*?)interned)
string_data_set_fly_string(interned, true)
return interned
# mark: Creation ================================================================================
## Ported from AK/FlyString.cpp:29 AK::FlyString::from_utf8: fails when `string` is not valid UTF-8.
pub func fly_string_from_utf8(string: StringView) -> FlyString!:
if string_view_is_empty(&string):
return fly_string_new()
if string_view_length(&string) <= max_short_string_byte_count:
return fly_string_from_string(try string_from_utf8(string))
if let data = fly_string_table_find_view(string):
var result = FlyString(m_data = StringBase())
string_base_construct_string_data(&result.m_data, data)
return result
return fly_string_from_string(try string_from_utf8(string))
## Ported from AK/FlyString.cpp:40 AK::FlyString::from_utf8_without_validation.
pub func fly_string_from_utf8_without_validation(string: const u8[]) -> FlyString:
if string.length == 0:
return fly_string_new()
if string.length <= max_short_string_byte_count:
return fly_string_from_string(string_from_utf8_without_validation(string))
if let data = fly_string_table_find_view(string_view_from_bytes(string)):
var result = FlyString(m_data = StringBase())
string_base_construct_string_data(&result.m_data, data)
return result
return fly_string_from_string(string_from_utf8_without_validation(string))
## Ported from AK/FlyString.h:30 AK::FlyString::from_ascii_short_string_without_validation.
pub func fly_string_from_ascii_short_string_without_validation(data: const u8[]) -> FlyString:
assert(data.length <= max_short_string_byte_count)
var short_string = short_string_create_with_byte_count(data.length)
for i in 0..<data.length:
short_string.storage[i] = data[i]
var result = FlyString(m_data = StringBase())
string_base_construct_short_string(&result.m_data, short_string)
return result
## Ported from AK/FlyString.cpp:51 AK::FlyString::FlyString(String const&): interns `string`.
pub func fly_string_construct_string(this: FlyString*, string: const String*):
# (ASSERT(!string.is_invalid()): the null sentinel of Optional<String> does not exist here.)
if string_base_is_short_string(&string.string_base):
this.m_data = string.string_base
return
let data = string_base_data_without_union_member_assertion(&string.string_base) else trap("VERIFY: string data")
if string_data_is_fly_string(data):
this.m_data = string.string_base
return
if let existing = fly_string_table_find(data):
string_base_construct_string_data(&this.m_data, existing)
else:
# The C++ interns `data` itself and marks it; here the table's copy is interned, since
# `data` may come from a shorter-lived allocator.
string_base_construct_string_data(&this.m_data, fly_string_table_add(data))
## `FlyString { string }`: the value form of the String constructor (and of `operator=(String)`).
pub func fly_string_from_string(string: String) -> FlyString:
var result = fly_string_new()
fly_string_construct_string(&result, &string)
return result
## `FlyString {}`: the empty string.
pub func fly_string_new() -> FlyString:
return FlyString(m_data = string_base_new())
## `"text"_fly_string` from a `str` (DESIGN.md ยง2.6's generated FlyString constants are built on it).
pub func fly_string_from_str(text: str) -> FlyString:
return literalfly_string(text.bytes.data, text.length)
# mark: Accessors and comparison ================================================================
## Ported from AK/FlyString.h:46 AK::FlyString::is_empty.
pub func fly_string_is_empty(this: const FlyString*) -> bool:
return string_base_byte_count(&this.m_data) == 0
## Ported from AK/FlyString.h:47 AK::FlyString::hash.
pub func fly_string_hash(this: const FlyString*) -> u32:
return string_base_hash(&this.m_data)
## Ported from AK/FlyString.cpp:82 AK::FlyString::ascii_case_insensitive_hash.
pub func fly_string_ascii_case_insensitive_hash(this: const FlyString*) -> u32:
let bytes = fly_string_bytes(this)
return case_insensitive_string_hash(bytes.data, bytes.length)
## Ported from AK/FlyString.cpp:87 AK::FlyString::operator String.
pub func fly_string_to_string_const(this: const FlyString*) -> String:
return fly_string_to_string_const_2(this)
## Ported from AK/FlyString.cpp:92 AK::FlyString::to_string.
pub func fly_string_to_string_const_2(this: const FlyString*) -> String:
return String(string_base = this.m_data)
## Ported from AK/FlyString.cpp:98 AK::FlyString::code_points.
pub func fly_string_code_points(this: const FlyString*) -> Utf8View:
return Utf8View(m_string = fly_string_bytes_as_string_view(this))
## Ported from AK/FlyString.h:54 AK::FlyString::bytes.
pub func fly_string_bytes(this: const FlyString*) -> const u8[]:
return string_base_bytes(&this.m_data)
## Ported from AK/FlyString.h:55 AK::FlyString::bytes_as_string_view.
pub func fly_string_bytes_as_string_view(this: const FlyString*) -> StringView:
return string_view_from_bytes(string_base_bytes(&this.m_data))
## Ported from AK/FlyString.h:57 AK::FlyString::operator==(FlyString const&): identity of the
## eight bytes. `==` on two FlyStrings is a compile error (the union), so compare with this.
pub func fly_string_eq_fly_string(this: const FlyString*, other: const FlyString*) -> bool:
return string_base_raw_fly_string(&this.m_data) == string_base_raw_fly_string(&other.m_data)
## Ported from AK/FlyString.h:58 AK::FlyString::operator==(String const&).
pub func fly_string_eq_string(this: const FlyString*, other: const String*) -> bool:
return string_base_eq(&this.m_data, &other.string_base)
## Ported from AK/FlyString.cpp:103 AK::FlyString::operator==(StringView).
pub func fly_string_eq_string_view(this: const FlyString*, string: StringView) -> bool:
let view = fly_string_bytes_as_string_view(this)
return string_view_eq_string_view(&view, string)
## Ported from AK/FlyString.cpp:108 AK::FlyString::operator==(char const*).
pub func fly_string_eq_u8(this: const FlyString*, string: const u8*?) -> bool:
let view = fly_string_bytes_as_string_view(this)
return string_view_eq_u8_const(&view, string)
## Ported from AK/FlyString.cpp:128 AK::FlyString::operator<=>.
pub func fly_string_cmp(this: const FlyString*, other: const FlyString*) -> i32:
let view = fly_string_bytes_as_string_view(this)
return string_view_compare(&view, fly_string_bytes_as_string_view(other))
## Ported from AK/FlyString.cpp:113 AK::FlyString::data(Badge<String>).
pub func fly_string_data(this: const FlyString*) -> StringBase:
return this.m_data
## Ported from AK/FlyString.cpp:118 AK::FlyString::number_of_fly_strings. This is primarily
## interesting to unit tests.
pub func fly_string_number_of_fly_strings() -> usize:
return hash_table_size(all_fly_strings())
## Ported from AK/FlyString.cpp:186 AK::FlyString::equals_ignoring_ascii_case(FlyString const&).
pub func fly_string_equals_ignoring_ascii_case_fly_string(this: const FlyString*, other: const FlyString*) -> bool:
if fly_string_eq_fly_string(this, other):
return true
return string_utils_equals_ignoring_ascii_case(fly_string_bytes_as_string_view(this), fly_string_bytes_as_string_view(other))
## Ported from AK/FlyString.cpp:193 AK::FlyString::equals_ignoring_ascii_case(StringView).
pub func fly_string_equals_ignoring_ascii_case_string_view(this: const FlyString*, other: StringView) -> bool:
return string_utils_equals_ignoring_ascii_case(fly_string_bytes_as_string_view(this), other)
## Ported from AK/FlyString.cpp:138 AK::FlyString::to_ascii_lowercase.
pub func fly_string_to_ascii_lowercase(this: const FlyString*) -> FlyString:
let bytes = fly_string_bytes(this)
var has_ascii_uppercase = false
for byte in bytes:
if is_ascii_upper_alpha(byte):
has_ascii_uppercase = true
break
if not has_ascii_uppercase:
return *this
let lowercase_bytes = new u8[bytes.length] else trap("out of memory")
for i in 0..<bytes.length:
lowercase_bytes[i] = (u8)to_ascii_lowercase(bytes[i])
return fly_string_from_string(string_from_utf8_without_validation(lowercase_bytes))
## Ported from AK/FlyString.cpp:162 AK::FlyString::to_ascii_uppercase.
pub func fly_string_to_ascii_uppercase(this: const FlyString*) -> FlyString:
let bytes = fly_string_bytes(this)
var has_ascii_lowercase = false
for byte in bytes:
if is_ascii_lower_alpha(byte):
has_ascii_lowercase = true
break
if not has_ascii_lowercase:
return *this
let uppercase_bytes = new u8[bytes.length] else trap("out of memory")
for i in 0..<bytes.length:
uppercase_bytes[i] = (u8)to_ascii_uppercase(bytes[i])
return fly_string_from_string(string_from_utf8_without_validation(uppercase_bytes))
## Ported from AK/FlyString.h:79 AK::FlyString::is_ascii.
pub func fly_string_is_ascii(this: const FlyString*) -> bool:
let view = fly_string_bytes_as_string_view(this)
return string_view_is_ascii(&view)
## Ported from AK/FlyString.cpp:198 AK::FlyString::starts_with_bytes.
pub func fly_string_starts_with_bytes(this: const FlyString*, bytes: StringView, case_sensitivity: CaseSensitivity = CaseSensitivity.case_sensitive) -> bool:
let view = fly_string_bytes_as_string_view(this)
return string_view_starts_with_string_view(&view, bytes, case_sensitivity)
## Ported from AK/FlyString.cpp:203 AK::FlyString::ends_with_bytes.
pub func fly_string_ends_with_bytes(this: const FlyString*, bytes: StringView, case_sensitivity: CaseSensitivity = CaseSensitivity.case_sensitive) -> bool:
let view = fly_string_bytes_as_string_view(this)
return string_view_ends_with_string_view(&view, bytes, case_sensitivity)
## Ported from AK/FlyString.h:105 AK::FlyString::FlyString(StringBase).
pub func fly_string_construct_string_base(this: FlyString*, data: StringBase):
this.m_data = data
# mark: Traits and literals =====================================================================
## Ported from AK/FlyString.h:139 AK::ASCIICaseInsensitiveFlyStringTraits::hash.
pub func ascii_case_insensitive_fly_string_traits_hash(s: const FlyString*) -> u32:
return fly_string_ascii_case_insensitive_hash(s)
## Ported from AK/FlyString.h:140 AK::ASCIICaseInsensitiveFlyStringTraits::equals.
pub func ascii_case_insensitive_fly_string_traits_equals(a: const FlyString*, b: const FlyString*) -> bool:
return fly_string_equals_ignoring_ascii_case_fly_string(a, b)
## Ported from AK/FlyString.h:145 operator""_fly_string: short ASCII literals become inline fly
## strings without validation or table lookup; anything else must be valid UTF-8.
pub func literalfly_string(cstring: const u8*?, length: usize) -> FlyString:
let view = literalsv_u8(cstring, length)
let bytes = string_view_bytes(&view)
# OPTIMIZATION: Short ASCII strings become compile-time constants with no runtime validation
# or table lookup.
if length <= max_short_string_byte_count and simdutf_validate_ascii(bytes):
return fly_string_from_ascii_short_string_without_validation(bytes)
let utf8 = Utf8View(m_string = view)
assert(utf8_view_validate_allow_lonely_surrogates(&utf8))
return fly_string_from_utf8_without_validation(bytes)