From b0cf44e4ddbf42ce79a8612563e84e00e8a75808 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Vladim=C3=ADr=20Vondru=C5=A1?= Date: Sat, 8 Jan 2022 20:49:26 +0100 Subject: [PATCH] documentation: parametrize the search binary data type sizes. Needed in order to support more than 65k symbols or files larger than 16 MB. What I thought was "more than enough" during the initial design was quickly stepped over by various projects, including my own Magnum Python bindings. To avoid having to either maintain two separate formats and two separate en/decoders or needlessly inflate the format for everyone, certain data types are parametrized based on how large the data is: * RESULT_ID_BYTES describes how many bytes is needed to store result IDs. By default it's 2 (so 65536 results) but can be also 3 (16M results) or 4. * FILE_OFFSET_BYTES describes how many bytes is needed to store file offsets. By default it's 3 (so 16 MB), but can be also 4. * NAME_SIZE_BYTES describes how many bytes is needed to store various name lengths (prefix, suffix lengths etc). By default it's 1 (so 256 bytes at most), but can be also 2. At first I tried to preserve 32-bit alignment as much as possible, but eventually realized this is completely unimportant in the browser environment -- there's other much worse performance pitfalls than reading an unaligned value. This is also why there are 24-bit integer types, even though they're quite annoying to pack from Python. Furthermore, the original hack to reserve 11 bits for result count at the cost of having only 4 bits for child count was changed to instead expand the result count to a 15-bit value if there's > 127 results. Some endianness tricks involved, but much cleaner than before. I briefly considered having a global RESULT_COUNT_BYTES parameter as well, but considering >90% of result counts fit into 8 bits and this is only for weird outliers like Python __init__(), it would be a giant waste of precious bytes. The minor differences in the test file sizes are due to: * The header expanding symbol count from 16 to 32 bits (+2B) * The header containing type description and associated padding (+4B) * The result map no longer packing flags and offsets together, thus saving one byte from flags (-1B) To ensure there's no hardcoded type size assumptions anymore, the tests now go through all type size combinations. --- documentation/_search.py | 532 +++++++++++------- documentation/doxygen.py | 4 +- documentation/python.py | 4 +- documentation/search.js | 131 +++-- documentation/test/_search_test_metadata.py | 45 ++ .../test/js-test-data/empty-ns1-ri2-fo3.bin | Bin 0 -> 31 bytes .../test/js-test-data/empty-ns1-ri2-fo4.bin | Bin 0 -> 32 bytes .../test/js-test-data/empty-ns1-ri3-fo3.bin | Bin 0 -> 31 bytes .../test/js-test-data/empty-ns1-ri3-fo4.bin | Bin 0 -> 32 bytes .../test/js-test-data/empty-ns1-ri4-fo3.bin | Bin 0 -> 31 bytes .../test/js-test-data/empty-ns1-ri4-fo4.bin | Bin 0 -> 32 bytes .../test/js-test-data/empty-ns2-ri2-fo3.bin | Bin 0 -> 31 bytes .../test/js-test-data/empty-ns2-ri2-fo4.bin | Bin 0 -> 32 bytes .../test/js-test-data/empty-ns2-ri3-fo3.bin | Bin 0 -> 31 bytes .../test/js-test-data/empty-ns2-ri3-fo4.bin | Bin 0 -> 32 bytes .../test/js-test-data/empty-ns2-ri4-fo3.bin | Bin 0 -> 31 bytes .../test/js-test-data/empty-ns2-ri4-fo4.bin | Bin 0 -> 32 bytes documentation/test/js-test-data/empty.bin | Bin 26 -> 0 bytes .../js-test-data/manyresults-ns1-ri2-fo3.bin | Bin 0 -> 6421 bytes .../js-test-data/manyresults-ns1-ri2-fo4.bin | Bin 0 -> 6571 bytes .../js-test-data/manyresults-ns1-ri3-fo3.bin | Bin 0 -> 6552 bytes .../js-test-data/manyresults-ns1-ri3-fo4.bin | Bin 0 -> 6702 bytes .../js-test-data/manyresults-ns1-ri4-fo3.bin | Bin 0 -> 6683 bytes .../js-test-data/manyresults-ns1-ri4-fo4.bin | Bin 0 -> 6833 bytes .../js-test-data/manyresults-ns2-ri2-fo3.bin | Bin 0 -> 6552 bytes .../js-test-data/manyresults-ns2-ri2-fo4.bin | Bin 0 -> 6702 bytes .../js-test-data/manyresults-ns2-ri3-fo3.bin | Bin 0 -> 6683 bytes .../js-test-data/manyresults-ns2-ri3-fo4.bin | Bin 0 -> 6833 bytes .../js-test-data/manyresults-ns2-ri4-fo3.bin | Bin 0 -> 6814 bytes .../js-test-data/manyresults-ns2-ri4-fo4.bin | Bin 0 -> 6964 bytes .../test/js-test-data/manyresults.bin | Bin 6415 -> 0 bytes documentation/test/js-test-data/nested.bin | Bin 331 -> 336 bytes .../js-test-data/searchdata-ns1-ri2-fo3.b85 | 1 + .../js-test-data/searchdata-ns1-ri2-fo3.bin | Bin 0 -> 750 bytes .../js-test-data/searchdata-ns1-ri2-fo4.bin | Bin 0 -> 828 bytes .../js-test-data/searchdata-ns1-ri3-fo3.bin | Bin 0 -> 772 bytes .../js-test-data/searchdata-ns1-ri3-fo4.bin | Bin 0 -> 850 bytes .../js-test-data/searchdata-ns1-ri4-fo3.bin | Bin 0 -> 794 bytes .../js-test-data/searchdata-ns1-ri4-fo4.bin | Bin 0 -> 872 bytes .../js-test-data/searchdata-ns2-ri2-fo3.bin | Bin 0 -> 761 bytes .../js-test-data/searchdata-ns2-ri2-fo4.bin | Bin 0 -> 839 bytes .../js-test-data/searchdata-ns2-ri3-fo3.bin | Bin 0 -> 783 bytes .../js-test-data/searchdata-ns2-ri3-fo4.bin | Bin 0 -> 861 bytes .../js-test-data/searchdata-ns2-ri4-fo3.bin | Bin 0 -> 805 bytes .../js-test-data/searchdata-ns2-ri4-fo4.bin | Bin 0 -> 883 bytes .../test/js-test-data/searchdata.b85 | 1 - .../test/js-test-data/searchdata.bin | Bin 745 -> 0 bytes documentation/test/js-test-data/short.bin | 2 +- documentation/test/js-test-data/unicode.bin | Bin 160 -> 165 bytes .../test/js-test-data/wrong-magic.bin | Bin 26 -> 31 bytes .../js-test-data/wrong-result-id-bytes.bin | Bin 0 -> 31 bytes .../test/js-test-data/wrong-version.bin | Bin 26 -> 31 bytes documentation/test/populate-js-test-data.py | 58 +- documentation/test/test-search.js | 119 +++- documentation/test/test_search.py | 250 ++++++-- documentation/test_doxygen/layout/pages.html | 4 +- .../layout_generated_doxyfile/index.html | 4 +- .../test_doxygen/layout_minimal/index.html | 4 +- .../layout_search_binary/index.html | 4 +- .../layout_search_opensearch/index.html | 4 +- documentation/test_doxygen/test_search.py | 4 +- .../test_doxygen/test_undocumented.py | 4 +- .../test_doxygen/undocumented/File_8h.html | 4 +- .../test_doxygen/undocumented/annotated.html | 4 +- .../test_doxygen/undocumented/classClass.html | 4 +- .../dir_4b0d5f8864bf89936129251a2d32609b.html | 4 +- .../test_doxygen/undocumented/files.html | 4 +- .../undocumented/group__group.html | 4 +- .../undocumented/namespaceNamespace.html | 4 +- .../structNamespace_1_1ClassInANamespace.html | 4 +- documentation/test_python/layout/index.html | 4 +- .../layout_search_binary/index.html | 4 +- .../layout_search_open_search/index.html | 4 +- .../c.link_formatting.Class.Sub.html | 4 +- .../c.link_formatting.Class.html | 4 +- .../c.link_formatting.pybind.Foo.html | 4 +- .../link_formatting/m.link_formatting.html | 4 +- .../m.link_formatting.pybind.html | 4 +- .../m.link_formatting.sub.html | 4 +- .../test_python/link_formatting/p.page.html | 4 +- .../link_formatting/s.classes.html | 4 +- .../link_formatting/s.modules.html | 4 +- .../test_python/link_formatting/s.pages.html | 4 +- documentation/test_python/test_search.py | 4 +- 84 files changed, 888 insertions(+), 375 deletions(-) create mode 100644 documentation/test/js-test-data/empty-ns1-ri2-fo3.bin create mode 100644 documentation/test/js-test-data/empty-ns1-ri2-fo4.bin create mode 100644 documentation/test/js-test-data/empty-ns1-ri3-fo3.bin create mode 100644 documentation/test/js-test-data/empty-ns1-ri3-fo4.bin create mode 100644 documentation/test/js-test-data/empty-ns1-ri4-fo3.bin create mode 100644 documentation/test/js-test-data/empty-ns1-ri4-fo4.bin create mode 100644 documentation/test/js-test-data/empty-ns2-ri2-fo3.bin create mode 100644 documentation/test/js-test-data/empty-ns2-ri2-fo4.bin create mode 100644 documentation/test/js-test-data/empty-ns2-ri3-fo3.bin create mode 100644 documentation/test/js-test-data/empty-ns2-ri3-fo4.bin create mode 100644 documentation/test/js-test-data/empty-ns2-ri4-fo3.bin create mode 100644 documentation/test/js-test-data/empty-ns2-ri4-fo4.bin delete mode 100644 documentation/test/js-test-data/empty.bin create mode 100644 documentation/test/js-test-data/manyresults-ns1-ri2-fo3.bin create mode 100644 documentation/test/js-test-data/manyresults-ns1-ri2-fo4.bin create mode 100644 documentation/test/js-test-data/manyresults-ns1-ri3-fo3.bin create mode 100644 documentation/test/js-test-data/manyresults-ns1-ri3-fo4.bin create mode 100644 documentation/test/js-test-data/manyresults-ns1-ri4-fo3.bin create mode 100644 documentation/test/js-test-data/manyresults-ns1-ri4-fo4.bin create mode 100644 documentation/test/js-test-data/manyresults-ns2-ri2-fo3.bin create mode 100644 documentation/test/js-test-data/manyresults-ns2-ri2-fo4.bin create mode 100644 documentation/test/js-test-data/manyresults-ns2-ri3-fo3.bin create mode 100644 documentation/test/js-test-data/manyresults-ns2-ri3-fo4.bin create mode 100644 documentation/test/js-test-data/manyresults-ns2-ri4-fo3.bin create mode 100644 documentation/test/js-test-data/manyresults-ns2-ri4-fo4.bin delete mode 100644 documentation/test/js-test-data/manyresults.bin create mode 100644 documentation/test/js-test-data/searchdata-ns1-ri2-fo3.b85 create mode 100644 documentation/test/js-test-data/searchdata-ns1-ri2-fo3.bin create mode 100644 documentation/test/js-test-data/searchdata-ns1-ri2-fo4.bin create mode 100644 documentation/test/js-test-data/searchdata-ns1-ri3-fo3.bin create mode 100644 documentation/test/js-test-data/searchdata-ns1-ri3-fo4.bin create mode 100644 documentation/test/js-test-data/searchdata-ns1-ri4-fo3.bin create mode 100644 documentation/test/js-test-data/searchdata-ns1-ri4-fo4.bin create mode 100644 documentation/test/js-test-data/searchdata-ns2-ri2-fo3.bin create mode 100644 documentation/test/js-test-data/searchdata-ns2-ri2-fo4.bin create mode 100644 documentation/test/js-test-data/searchdata-ns2-ri3-fo3.bin create mode 100644 documentation/test/js-test-data/searchdata-ns2-ri3-fo4.bin create mode 100644 documentation/test/js-test-data/searchdata-ns2-ri4-fo3.bin create mode 100644 documentation/test/js-test-data/searchdata-ns2-ri4-fo4.bin delete mode 100644 documentation/test/js-test-data/searchdata.b85 delete mode 100644 documentation/test/js-test-data/searchdata.bin create mode 100644 documentation/test/js-test-data/wrong-result-id-bytes.bin diff --git a/documentation/_search.py b/documentation/_search.py index 1a1d893e..a2d44556 100644 --- a/documentation/_search.py +++ b/documentation/_search.py @@ -29,14 +29,263 @@ import base64 import enum import struct from types import SimpleNamespace as Empty -from typing import List, Tuple +from typing import List, Tuple, Union # Version 0 was without the type map -searchdata_format_version = 1 +searchdata_format_version = 2 search_filename = f'search-v{searchdata_format_version}.js' searchdata_filename = f'{{search_filename_prefix}}-v{searchdata_format_version}.bin' searchdata_filename_b85 = f'{{search_filename_prefix}}-v{searchdata_format_version}.js' +# In order to be both space-efficient and flexible enough to accomodate for +# larger projects, the bit counts for particular data types can vary in each +# file. There's the following categories: +# +# - NAME_SIZE_BITS, how many bits is needed to store name lengths (such as +# prefix length). Can be either 8 or 16. +# - RESULT_ID_BITS, how many bits is needed for IDs pointing into the result +# map. Can be either 16, 24 or 32. +# - FILE_OFFSET_BITS, how many bits is needed to store general offsets into +# the file. Can be either 24 or 32. +# +# Whole file encoding +# =================== +# +# magic | version | type | not | symbol | result | type | trie | result | type +# 'MCS' | (0x02) | data | used | count | map | map | data | map | map +# | | | | | offset | offset | | data | data +# 24b | 8b | 8b | 24b | 32b | 32b | 32b | … | … | … +# +# The type data encode the NAME_SIZE_BITS, RESULT_ID_BITS and +# FILE_OFFSET_BITS: +# +# not | NAME_SIZE_BITS | RESULT_ID_BITS | FILE_OFFSET_BITS +# used | 0b0 = 8b | 0b00 = 16b | 0b0 = 24b +# | 0b1 = 16b | 0b01 = 24b | 0b1 = 32b +# | | 0b10 = 32b | +# 4b | 1b | 2b | 1b +# +# Trie encoding +# ============= +# +# Because child tries are serialized first, the trie containing the initial +# characters is never the first, and instead the root offset points to it. If +# result count < 128: +# +# root | | header | results | children +# offset | … | | result # | child # | … | data +# 32b | |0| 7b | 8b | n*RESULT_ID_BITS | … +# +# If result count > 127, it's instead this -- since entries with very large +# number of results (such as python __init__()) are rather rare, it doesn't +# make sense to have it globally configurable and then waste 8 bits in the +# majority of cases. Note that the 15-bit value is stored as Big-Endian, +# otherwise the leftmost bit couldn't be used to denote the size. +# +# root | | header | results | children +# offset | … | | result # | child # | … | data +# 32b | |1| 15b (BE) | 8b | n*RESULT_ID_BITS | … +# +# Trie children data encoding, the barrier is stored in the topmost offset bit: +# +# child 1 | child 2 | | child 1 | child 2 | +# char | char | … | barrier + offset | barrier + offset | … +# 8b | 8b | | FILE_OFFSET_BITS | FILE_OFFSET_BITS | +# +# Result map encoding +# =================== +# +# First all flags, then all offsets, so we don't need to have weird paddings or +# alignments. The "file size" is there so size of item N can be always +# retrieved as `offsets[N + 1] - offsets[N]` +# +# item | file | item | item 1 | item 2 | +# offsets | size | flags | data | data | … +# n*FILE_OFFSET_BITS | FILE_OFFSET_BITS | n*8b | | | +# +# Basic item data (flags & 0b11 == 0b00): +# +# name | \0 | URL +# | | +# | 8b | +# +# Suffixed item data (flags & 0b11 == 0b01): +# +# suffix | name | \0 | URL +# length | | | +# NAME_SIZE_BITS | | 8b | +# +# Prefixed item data (flags & 0xb11 == 0b10): +# +# prefix | prefix | name | \0 | URL +# id | length | suffix | | suffix +# RESULT_ID_BITS | NAME_SIZE_BITS | | 8b | +# +# Prefixed & suffixed item (flags & 0xb11 == 0b11): +# +# prefix | prefix | suffix | name | \0 | URL +# id | length | length | suffix | | +# RESULT_ID_BITS | NAME_SIZE_BITS | NAME_SIZE_BITS | | 8b | +# +# Alias item (flags & 0xf0 == 0x00), flags & 0xb11 then denote what's in the +# `…` portion, alias have no URL so the alias name is in place of it: +# +# alias | | alias +# id | … | name +# RESULT_ID_BITS | | +# +# Type map encoding +# ================= +# +# Again the "end offset" is here so size of type N can be always retrieved as +# `offsets[N + 1] - offsets[N]`. Type names are not expected to have more than +# 255 chars, so NAME_SIZE_BITS is not used here. +# +# type 1 | type 2 | | | | type 1 | +# class | name | class | name | … | padding | end | name | … +# ID | offset | ID | offset | | | offset | data | +# 8b | 8b | 8b | 8b | | 8b | 8b | | + +class Serializer: + # This is currently hardcoded + result_map_flag_bytes = 1 + + header_struct = struct.Struct('<3sBBxxxIII') + result_map_flags_struct = struct.Struct('= child_barrier_mask: raise OverflowError + out += (offset | (barrier*child_barrier_mask)).to_bytes(self.file_offset_bytes, byteorder='little') + return out + + def pack_type_map_entry(self, class_: int, offset: int): + return self.type_map_entry_struct.pack(class_, offset) + +class Deserializer: + def __init__(self, *, file_offset_bytes, result_id_bytes, name_size_bytes): + assert file_offset_bytes in [3, 4] + self.file_offset_bytes = file_offset_bytes + + assert result_id_bytes in [2, 3, 4] + self.result_id_bytes = result_id_bytes + + assert name_size_bytes in [1, 2] + self.name_size_bytes = name_size_bytes + + @classmethod + def from_serialized(self, serialized: bytes): + magic, version, type_data, symbol_count, map_offset, type_map_offset = Serializer.header_struct.unpack_from(serialized) + assert magic == b'MCS' + assert version == searchdata_format_version + out = Deserializer( + file_offset_bytes=[3, 4][(type_data & 0b0001) >> 0], + result_id_bytes=[2, 3, 4][(type_data & 0b0110) >> 1], + name_size_bytes=[1, 2][(type_data & 0b1000) >> 3]) + out.symbol_count = symbol_count + out.map_offset = map_offset + out.type_map_offset = type_map_offset + return out + + # The last tuple item is number of bytes extracted + def unpack_result_map_flags(self, serialized: bytes, offset: int) -> Tuple[int, int]: + return Serializer.result_map_flags_struct.unpack_from(serialized, offset) + (Serializer.result_map_flags_struct.size, ) + def unpack_result_map_offset(self, serialized: bytes, offset: int) -> Tuple[int, int]: + return int.from_bytes(serialized[offset:offset + self.file_offset_bytes], byteorder='little'), self.file_offset_bytes + def unpack_result_map_prefix(self, serialized: bytes, offset: int) -> Tuple[int, int, int]: + return int.from_bytes(serialized[offset:offset + self.result_id_bytes], byteorder='little'), int.from_bytes(serialized[offset + self.result_id_bytes:offset + self.result_id_bytes + self.name_size_bytes], byteorder='little'), self.result_id_bytes + self.name_size_bytes + def unpack_result_map_suffix_length(self, serialized: bytes, offset: int) -> Tuple[int, int]: + return int.from_bytes(serialized[offset:offset + self.name_size_bytes], byteorder='little'), self.name_size_bytes + def unpack_result_map_alias(self, serialized: bytes, offset: int) -> Tuple[int, int]: + return int.from_bytes(serialized[offset:offset + self.result_id_bytes], byteorder='little'), self.result_id_bytes + + def unpack_trie_root_offset(self, serialized: bytes, offset: int) -> Tuple[int, int]: + return Serializer.trie_root_offset_struct.unpack_from(serialized, offset) + (Serializer.trie_root_offset_struct.size, ) + def unpack_trie_node(self, serialized: bytes, offset: int) -> Tuple[List[int], List[int], List[Tuple[int, int, bool]], int]: + prev_offset = offset + # Result count, first try 8-bit, if it has the highest bit set, extract + # two bytes (as a BE) and then remove the highest bit + result_count = int.from_bytes(serialized[offset:offset + 1], byteorder='little') + if result_count & 0x80: + result_count = int.from_bytes(serialized[offset:offset + 2], byteorder='big') & ~0x8000 + offset += 1 + offset += 1 + child_count = int.from_bytes(serialized[offset:offset + 1], byteorder='little') + offset += 1 + + # Unpack all result IDs + result_ids = [] + for i in range(result_count): + result_ids += [int.from_bytes(serialized[offset:offset + self.result_id_bytes], byteorder='little')] + offset += self.result_id_bytes + + # Unpack all child chars + child_chars = list(serialized[offset:offset + child_count]) + offset += child_count + + # Unpack all children offsets and lookahead barriers + child_chars_offsets_barriers = [] + child_barrier_mask = 1 << (self.file_offset_bytes*8 - 1) + for i in range(child_count): + child_offset_barrier = int.from_bytes(serialized[offset:offset + self.file_offset_bytes], byteorder='little') + child_chars_offsets_barriers += [(child_chars[i], child_offset_barrier & ~child_barrier_mask, bool(child_offset_barrier & child_barrier_mask))] + offset += self.file_offset_bytes + + return result_ids, child_chars_offsets_barriers, offset - prev_offset + + def unpack_type_map_entry(self, serialized: bytes, offset: int) -> Tuple[int, int, int]: + return Serializer.type_map_entry_struct.unpack_from(serialized, offset) + (Serializer.type_map_entry_struct.size, ) + class CssClass(enum.Enum): DEFAULT = 0 PRIMARY = 1 @@ -87,50 +336,7 @@ class ResultFlag(enum.Flag): _TYPE14 = 14 << 4 _TYPE15 = 15 << 4 -# Result map encoding -- the "file size" is there so size of item N can be -# always retrieved as `offsets[N + 1] - offsets[N]` -# -# item 1 flags | item 2 flags | | item N flags | file | item 1 | -# + offset | + offset | … | + offset | size | data | … -# 8 + 24b | 8 + 24b | | 8 + 24b | 32b | | -# -# basic item (flags & 0b11 == 0b00): -# -# name | \0 | URL -# | | -# | 8b | -# -# suffixed item (flags & 0b11 == 0b01): -# -# suffix | name | \0 | URL -# length | | | -# 8b | | 8b | -# -# prefixed item (flags & 0xb11 == 0b10): -# -# prefix | name | \0 | URL -# id + len | suffix | | suffix -# 16b + 8b | | 8b | -# -# prefixed & suffixed item (flags & 0xb11 == 0b11): -# -# prefix | suffix | name | \0 | URL -# id + len | length | suffix | | -# 16b + 8b | 8b | | 8b | -# -# alias item (flags & 0xf0 == 0x00), flags & 0xb11 then denote what's in the -# `…` portion, alias have no URL so the alias name is in place of it: -# -# alias | | alias -# id | … | name -# 16b | | class ResultMap: - offset_struct = struct.Struct(' bytearray: - output = bytearray() - + def serialize(self, serializer: Serializer, merge_prefixes=True) -> bytearray: if merge_prefixes: # Put all entry names into a trie to discover common prefixes trie = Trie() @@ -225,25 +429,24 @@ class ResultMap: # Everything merged, replace the original list self.entries = merged - # Write the offset array. Starting offset for items is after the offset - # array and the file size - offset = (len(self.entries) + 1)*4 + # Write the offset array. Starting offset for items is after the + # (aligned) flag array and (aligned) offset + file size array. + output = bytearray() + offset = len(self.entries)*serializer.result_map_flag_bytes + (len(self.entries) + 1)*serializer.file_offset_bytes for e in self.entries: - assert offset < 2**24 - output += self.offset_struct.pack(offset) - self.flags_struct.pack_into(output, len(output) - 1, e.flags.value) + output += serializer.pack_result_map_offset(offset) # The entry is an alias, extra field for alias index if e.flags & ResultFlag._TYPE == ResultFlag.ALIAS: - offset += self.alias_struct.size + offset += serializer.result_id_bytes # Extra field for prefix index and length if e.flags & ResultFlag.HAS_PREFIX: - offset += self.prefix_struct.size + offset += serializer.result_id_bytes + serializer.name_size_bytes # Extra field for suffix length if e.flags & ResultFlag.HAS_SUFFIX: - offset += self.suffix_length_struct.size + offset += serializer.name_size_bytes # Length of the name offset += len(e.name.encode('utf-8')) @@ -254,18 +457,22 @@ class ResultMap: offset += len(e.url.encode('utf-8')) + 1 # Write file size - output += self.offset_struct.pack(offset) + output += serializer.pack_result_map_offset(offset) + + # Write the flag array + for e in self.entries: + output += serializer.pack_result_map_flags(e.flags.value) # Write the entries themselves for e in self.entries: if e.flags & ResultFlag._TYPE == ResultFlag.ALIAS: assert not e.alias is None assert not e.url - output += self.alias_struct.pack(e.alias) + output += serializer.pack_result_map_alias(e.alias) if e.flags & ResultFlag.HAS_PREFIX: - output += self.prefix_struct.pack(e.prefix, e.prefix_length) + output += serializer.pack_result_map_prefix(e.prefix, e.prefix_length) if e.flags & ResultFlag.HAS_SUFFIX: - output += self.suffix_length_struct.pack(e.suffix_length) + output += serializer.pack_result_map_suffix_length(e.suffix_length) output += e.name.encode('utf-8') if e.url: output += b'\0' @@ -274,31 +481,21 @@ class ResultMap: assert len(output) == offset return output -# Trie encoding: -# -# root | | header | results | child 1 | child 1 | child 1 | -# offset | … | | result # | child # | … | char | barrier | offset | … -# 32b | |0| 7b | 8b | n*16b | 8b | 1b | 23b | -# -# if result count > 127, it's instead: -# -# root | | header | results | child 1 | child 1 | child 1 | -# offset | … | | result # | child # | … | char | barrier | offset | … -# 32b | |1| 11b | 4b | n*16b | 8b | 1b | 23b | class Trie: - root_offset_struct = struct.Struct(' int: + def _serialize(self, serializer: Serializer, hashtable, output: bytearray, merge_subtrees) -> int: # Serialize all children first - child_offsets = [] + child_chars_offsets_barriers = [] for char, child in self.children.items(): - offset = child[1]._serialize(hashtable, output, merge_subtrees=merge_subtrees) - child_offsets += [(char, child[0], offset)] - - # Serialize this node. Sometimes we'd have an insane amount of results - # (such as Python's __init__), but very little children to go with - # that. Then we can make the result count storage larger (11 bits, - # 2048 results) and the child count storage smaller (4 bits, 16 - # children). Hopefully that's enough. The remaining leftmost bit is - # used as an indicator of this shifted state. - serialized = bytearray() - if len(self.results) > 127: - assert len(self.children) < 16 and len(self.results) < 2048 - result_count = (len(self.results) & 0x7f) | 0x80 - children_count = ((len(self.results) & 0xf80) >> 3) | len(self.children) - else: - result_count = len(self.results) - children_count = len(self.children) - serialized += self.header_struct.pack(result_count, children_count) - for v in self.results: - serialized += self.result_struct.pack(v) - - # Serialize child offsets - for char, lookahead_barrier, abs_offset in child_offsets: - assert abs_offset < 2**23 - - # write them over each other because that's the only way to pack - # a 24 bit field - offset = len(serialized) - serialized += self.child_struct.pack(abs_offset | ((1 if lookahead_barrier else 0) << 23)) - self.child_char_struct.pack_into(serialized, offset + 3, char) + offset = child[1]._serialize(serializer, hashtable, output, merge_subtrees=merge_subtrees) + child_chars_offsets_barriers += [(char, offset, child[0])] + + # Serialize this node + serialized = serializer.pack_trie_node(self.results, child_chars_offsets_barriers) # Subtree merging: if this exact tree is already in the table, return # its offset. Otherwise add it and return the new offset. @@ -389,21 +561,13 @@ class Trie: if merge_subtrees: hashtable[hashable] = offset return offset - def serialize(self, merge_subtrees=True) -> bytearray: + def serialize(self, serializer: Serializer, merge_subtrees=True) -> bytearray: output = bytearray(b'\x00\x00\x00\x00') hashtable = {} - self.root_offset_struct.pack_into(output, 0, self._serialize(hashtable, output, merge_subtrees=merge_subtrees)) + output[0:4] = serializer.pack_trie_root_offset(self._serialize(serializer, hashtable, output, merge_subtrees=merge_subtrees)) return output -# Type map encoding: -# -# type 1 | type 2 | | | | type 1 | -# class | name | class | name | … | padding | end | name | … -# ID | offset | ID | offset | | | offset | data | -# 8b | 8b | 8b | 8b | | 8b | 8b | | -type_map_entry_struct = struct.Struct(' bytearray: +def serialize_type_map(serializer: Serializer, map: List[Tuple[CssClass, str]]) -> bytearray: serialized = bytearray() names = bytearray() @@ -412,42 +576,31 @@ def serialize_type_map(map: List[Tuple[CssClass, str]]) -> bytearray: assert len(map) <= 15 # Initial name offset is after all the offset entries plus the final one - initial_name_offset = (len(map) + 1)*type_map_entry_struct.size + initial_name_offset = (len(map) + 1)*serializer.type_map_entry_struct.size # Add all entries (and the final offset), encode the names separately, # concatenate at the end for css_class, name in map: - serialized += type_map_entry_struct.pack(css_class.value, initial_name_offset + len(names)) + serialized += serializer.pack_type_map_entry(css_class.value, initial_name_offset + len(names)) names += name.encode('utf-8') - serialized += type_map_entry_struct.pack(0, initial_name_offset + len(names)) + serialized += serializer.pack_type_map_entry(0, initial_name_offset + len(names)) assert len(serialized) == initial_name_offset return serialized + names -# Whole file encoding: -# -# magic | version | symbol | result | type | trie | result | type -# header | | count | map | map | data | map | map -# | | | offset | offset | | data | data -# 24b | 8b | 16b | 32b | 32b | … | … | … -search_data_header_struct = struct.Struct('<3sBHII') - -def serialize_search_data(trie: Trie, map: ResultMap, type_map: List[Tuple[CssClass, str]], symbol_count, *, merge_subtrees=True, merge_prefixes=True) -> bytearray: - serialized_trie = trie.serialize(merge_subtrees=merge_subtrees) - serialized_map = map.serialize(merge_prefixes=merge_prefixes) - serialized_type_map = serialize_type_map(type_map) +def serialize_search_data(serializer: Serializer, trie: Trie, map: ResultMap, type_map: List[Tuple[CssClass, str]], symbol_count, *, merge_subtrees=True, merge_prefixes=True) -> bytearray: + serialized_trie = trie.serialize(serializer, merge_subtrees=merge_subtrees) + serialized_map = map.serialize(serializer, merge_prefixes=merge_prefixes) + serialized_type_map = serialize_type_map(serializer, type_map) - preamble = search_data_header_struct.pack(b'MCS', - searchdata_format_version, symbol_count, - search_data_header_struct.size + len(serialized_trie), - search_data_header_struct.size + len(serialized_trie) + len(serialized_map)) + preamble = serializer.pack_header(symbol_count, len(serialized_trie), len(serialized_map)) return preamble + serialized_trie + serialized_map + serialized_type_map def base85encode_search_data(data: bytearray) -> bytearray: return (b"/* Generated by https://mcss.mosra.cz/documentation/doxygen/. Do not edit. */\n" + b"Search.load('" + base64.b85encode(data, True) + b"');\n") -def _pretty_print_trie(serialized: bytearray, hashtable, stats, base_offset, indent, *, show_merged, show_lookahead_barriers, color_map) -> str: +def _pretty_print_trie(deserializer: Deserializer, serialized: bytearray, hashtable, stats, base_offset, indent, *, show_merged, show_lookahead_barriers, color_map) -> str: # Visualize where the trees were merged if show_merged and base_offset in hashtable: return color_map['red'] + '#' + color_map['reset'] @@ -455,46 +608,35 @@ def _pretty_print_trie(serialized: bytearray, hashtable, stats, base_offset, ind stats.node_count += 1 out = '' - result_count, child_count = Trie.header_struct.unpack_from(serialized, base_offset) - # If result count has the high bit set, it's stored in 11 bits and child - # count in 4 bits instead of 7 + 8 - if result_count & 0x80: - result_count = (result_count & 0x7f) | ((child_count & 0xf0) << 3) - child_count = child_count & 0x0f - stats.max_node_results = max(result_count, stats.max_node_results) - stats.max_node_children = max(child_count, stats.max_node_children) - offset = base_offset + Trie.header_struct.size + result_ids, child_chars_offsets_barriers, offset = deserializer.unpack_trie_node(serialized, base_offset) + + stats.max_node_results = max(len(result_ids), stats.max_node_results) + stats.max_node_children = max(len(child_chars_offsets_barriers), stats.max_node_children) # print results, if any - if result_count: + if result_ids: out += color_map['blue'] + ' [' - for i in range(result_count): + for i, result in enumerate(result_ids): if i: out += color_map['blue']+', ' - result = Trie.result_struct.unpack_from(serialized, offset)[0] stats.max_node_result_index = max(result, stats.max_node_result_index) out += color_map['cyan'] + str(result) - offset += Trie.result_struct.size out += color_map['blue'] + ']' # print children, if any - for i in range(child_count): - if result_count or i: + for i, (char, offset, barrier) in enumerate(child_chars_offsets_barriers): + if len(result_ids) or i: out += color_map['reset'] + '\n' out += color_map['blue'] + indent + color_map['white'] - char = Trie.child_char_struct.unpack_from(serialized, offset + 3)[0] if char <= 127: out += chr(char) else: out += color_map['reset'] + hex(char) - if (show_lookahead_barriers and Trie.child_struct.unpack_from(serialized, offset)[0] & 0x00800000): + if (show_lookahead_barriers and barrier): out += color_map['green'] + '$' - if char > 127 or (show_lookahead_barriers and Trie.child_struct.unpack_from(serialized, offset)[0] & 0x00800000): + if char > 127 or (show_lookahead_barriers and barrier): out += color_map['reset'] + '\n' + color_map['blue'] + indent + ' ' + color_map['white'] - child_offset = Trie.child_struct.unpack_from(serialized, offset)[0] & 0x007fffff - stats.max_node_child_offset = max(child_offset, stats.max_node_child_offset) - offset += Trie.child_struct.size - out += _pretty_print_trie(serialized, hashtable, stats, child_offset, indent + ('|' if child_count > 1 else ' '), show_merged=show_merged, show_lookahead_barriers=show_lookahead_barriers, color_map=color_map) - child_count += 1 + stats.max_node_child_offset = max(offset, stats.max_node_child_offset) + out += _pretty_print_trie(deserializer, serialized, hashtable, stats, offset, indent + ('|' if len(child_chars_offsets_barriers) > 1 else ' '), show_merged=show_merged, show_lookahead_barriers=show_lookahead_barriers, color_map=color_map) hashtable[base_offset] = True return out @@ -515,7 +657,7 @@ color_map_dummy = {'blue': '', 'yellow': '', 'reset': ''} -def pretty_print_trie(serialized: bytes, *, show_merged=False, show_lookahead_barriers=True, colors=False): +def pretty_print_trie(deserializer: Deserializer, serialized: bytes, *, show_merged=False, show_lookahead_barriers=True, colors=False): color_map = color_map_colors if colors else color_map_dummy hashtable = {} @@ -527,7 +669,7 @@ def pretty_print_trie(serialized: bytes, *, show_merged=False, show_lookahead_ba stats.max_node_result_index = 0 stats.max_node_child_offset = 0 - out = _pretty_print_trie(serialized, hashtable, stats, Trie.root_offset_struct.unpack_from(serialized, 0)[0], '', show_merged=show_merged, show_lookahead_barriers=show_lookahead_barriers, color_map=color_map) + out = _pretty_print_trie(deserializer, serialized, hashtable, stats, deserializer.unpack_trie_root_offset(serialized, 0)[0], '', show_merged=show_merged, show_lookahead_barriers=show_lookahead_barriers, color_map=color_map) if out: out = color_map['white'] + out stats = """ node count: {} @@ -537,59 +679,61 @@ max node result index: {} max node child offset: {}""".lstrip().format(stats.node_count, stats.max_node_results, stats.max_node_children, stats.max_node_result_index, stats.max_node_child_offset) return out, stats -def pretty_print_map(serialized: bytes, *, entryTypeClass, colors=False): +def pretty_print_map(deserializer: Deserializer, serialized: bytes, *, entryTypeClass, colors=False): color_map = color_map_colors if colors else color_map_dummy # The first item gives out offset of first value, which can be used to # calculate total value count - offset = ResultMap.offset_struct.unpack_from(serialized, 0)[0] & 0x00ffffff - size = int(offset/4 - 1) + offset, offset_size = deserializer.unpack_result_map_offset(serialized, 0) + size = int((offset - offset_size)/(offset_size + Serializer.result_map_flag_bytes)) + flags_offset = (size + 1)*offset_size out = '' for i in range(size): if i: out += '\n' - flags = ResultFlag(ResultMap.flags_struct.unpack_from(serialized, i*4 + 3)[0]) + flags = ResultFlag(deserializer.unpack_result_map_flags(serialized, flags_offset + i*Serializer.result_map_flag_bytes)[0]) extra = [] if flags & ResultFlag._TYPE == ResultFlag.ALIAS: - extra += ['alias={}'.format(ResultMap.alias_struct.unpack_from(serialized, offset)[0])] - offset += ResultMap.alias_struct.size + alias, alias_bytes = deserializer.unpack_result_map_alias(serialized, offset) + extra += ['alias={}'.format(alias)] + offset += alias_bytes if flags & ResultFlag.HAS_PREFIX: - extra += ['prefix={}[:{}]'.format(*ResultMap.prefix_struct.unpack_from(serialized, offset))] - offset += ResultMap.prefix_struct.size + prefix_id, prefix_length, prefix_bytes = deserializer.unpack_result_map_prefix(serialized, offset) + extra += ['prefix={}[:{}]'.format(prefix_id, prefix_length)] + offset += prefix_bytes if flags & ResultFlag.HAS_SUFFIX: - extra += ['suffix_length={}'.format(ResultMap.suffix_length_struct.unpack_from(serialized, offset)[0])] - offset += ResultMap.suffix_length_struct.size + suffix_length, suffix_bytes = deserializer.unpack_result_map_suffix_length(serialized, offset) + extra += ['suffix_length={}'.format(suffix_length)] + offset += suffix_bytes if flags & ResultFlag.DEPRECATED: extra += ['deprecated'] if flags & ResultFlag.DELETED: extra += ['deleted'] if flags & ResultFlag._TYPE: extra += ['type={}'.format(entryTypeClass(flags.type).name)] - next_offset = ResultMap.offset_struct.unpack_from(serialized, (i + 1)*4)[0] & 0x00ffffff + next_offset = deserializer.unpack_result_map_offset(serialized, (i + 1)*offset_size)[0] name, _, url = serialized[offset:next_offset].partition(b'\0') out += color_map['cyan'] + str(i) + color_map['blue'] + ': ' + color_map['white'] + name.decode('utf-8') + color_map['blue'] + ' [' + color_map['yellow'] + (color_map['blue'] + ', ' + color_map['yellow']).join(extra) + color_map['blue'] + '] ->' + (' ' + color_map['reset'] + url.decode('utf-8') if url else '') offset = next_offset return out -def pretty_print_type_map(serialized: bytes, *, entryTypeClass): +def pretty_print_type_map(deserializer: Deserializer, serialized: bytes, *, entryTypeClass): # Unpack until we aren't at EOF i = 0 out = '' - class_id, offset = type_map_entry_struct.unpack_from(serialized, 0) - while offset < len(serialized): + class_id, name_offset, type_map_bytes = deserializer.unpack_type_map_entry(serialized, 0) + while name_offset < len(serialized): if i: out += ',\n' - next_class_id, next_offset = type_map_entry_struct.unpack_from(serialized, (i + 1)*type_map_entry_struct.size) - out += "({}, {}, '{}')".format(entryTypeClass(i + 1), CssClass(class_id), serialized[offset:next_offset].decode('utf-8')) + next_class_id, next_name_offset = deserializer.unpack_type_map_entry(serialized, (i + 1)*type_map_bytes)[:2] + out += "({}, {}, '{}')".format(entryTypeClass(i + 1), CssClass(class_id), serialized[name_offset:next_name_offset].decode('utf-8')) i += 1 - class_id, offset = next_class_id, next_offset + class_id, name_offset = next_class_id, next_name_offset return out def pretty_print(serialized: bytes, *, entryTypeClass, show_merged=False, show_lookahead_barriers=True, colors=False): - magic, version, symbol_count, map_offset, type_map_offset = search_data_header_struct.unpack_from(serialized) - assert magic == b'MCS' - assert version == searchdata_format_version - - pretty_trie, stats = pretty_print_trie(serialized[search_data_header_struct.size:map_offset], show_merged=show_merged, show_lookahead_barriers=show_lookahead_barriers, colors=colors) - pretty_map = pretty_print_map(serialized[map_offset:type_map_offset], entryTypeClass=entryTypeClass, colors=colors) - pretty_type_map = pretty_print_type_map(serialized[type_map_offset:], entryTypeClass=entryTypeClass) - return '{} symbols\n'.format(symbol_count) + pretty_trie + '\n' + pretty_map + '\n' + pretty_type_map, stats + deserializer = Deserializer.from_serialized(serialized) + + pretty_trie, stats = pretty_print_trie(deserializer, serialized[Serializer.header_struct.size:deserializer.map_offset], show_merged=show_merged, show_lookahead_barriers=show_lookahead_barriers, colors=colors) + pretty_map = pretty_print_map(deserializer, serialized[deserializer.map_offset:deserializer.type_map_offset], entryTypeClass=entryTypeClass, colors=colors) + pretty_type_map = pretty_print_type_map(deserializer, serialized[deserializer.type_map_offset:], entryTypeClass=entryTypeClass) + return '{} symbols\n'.format(deserializer.symbol_count) + pretty_trie + '\n' + pretty_map + '\n' + pretty_type_map, stats diff --git a/documentation/doxygen.py b/documentation/doxygen.py index 822dca78..973c3973 100755 --- a/documentation/doxygen.py +++ b/documentation/doxygen.py @@ -49,7 +49,7 @@ from pygments import highlight from pygments.formatters import HtmlFormatter from pygments.lexers import TextLexer, BashSessionLexer, get_lexer_by_name, find_lexer_class_for_filename -from _search import CssClass, ResultFlag, ResultMap, Trie, serialize_search_data, base85encode_search_data, search_filename, searchdata_filename, searchdata_filename_b85, searchdata_format_version +from _search import CssClass, ResultFlag, ResultMap, Trie, Serializer, serialize_search_data, base85encode_search_data, search_filename, searchdata_filename, searchdata_filename_b85, searchdata_format_version sys.path.append(os.path.join(os.path.dirname(os.path.realpath(__file__)), '../plugins')) import dot2svg @@ -2440,7 +2440,7 @@ def build_search_data(state: State, merge_subtrees=True, add_lookahead_barriers= # order by default trie.sort(map) - return serialize_search_data(trie, map, search_type_map, symbol_count, merge_subtrees=merge_subtrees, merge_prefixes=merge_prefixes) + return serialize_search_data(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=1), trie, map, search_type_map, symbol_count, merge_subtrees=merge_subtrees, merge_prefixes=merge_prefixes) def parse_xml(state: State, xml: str): # Reset counter for unique math formulas diff --git a/documentation/python.py b/documentation/python.py index 1d2dfe12..2d048858 100755 --- a/documentation/python.py +++ b/documentation/python.py @@ -54,7 +54,7 @@ from docutils.transforms import Transform import jinja2 -from _search import CssClass, ResultFlag, ResultMap, Trie, serialize_search_data, base85encode_search_data, searchdata_format_version, search_filename, searchdata_filename, searchdata_filename_b85 +from _search import CssClass, ResultFlag, ResultMap, Trie, Serializer, serialize_search_data, base85encode_search_data, searchdata_format_version, search_filename, searchdata_filename, searchdata_filename_b85 sys.path.append(os.path.join(os.path.dirname(os.path.realpath(__file__)), '../plugins')) import m.htmlsanity @@ -2454,7 +2454,7 @@ def build_search_data(state: State, merge_subtrees=True, add_lookahead_barriers= # order by default trie.sort(map) - return serialize_search_data(trie, map, search_type_map, symbol_count, merge_subtrees=merge_subtrees, merge_prefixes=merge_prefixes) + return serialize_search_data(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=1), trie, map, search_type_map, symbol_count, merge_subtrees=merge_subtrees, merge_prefixes=merge_prefixes) def run(basedir, config, *, templates=default_templates, search_add_lookahead_barriers=True, search_merge_subtrees=True, search_merge_prefixes=True): # Populate the INPUT, if not specified, make it absolute diff --git a/documentation/search.js b/documentation/search.js index 87a3ed7d..8cc2a3d4 100644 --- a/documentation/search.js +++ b/documentation/search.js @@ -25,15 +25,27 @@ "use strict"; /* it summons the Cthulhu in a proper way, they say */ var Search = { - formatVersion: 1, /* the data filename contains this number too */ + formatVersion: 2, /* the data filename contains this number too */ dataSize: 0, /* used mainly by tests, not here */ symbolCount: '…', trie: null, map: null, + mapFlagsOffset: null, typeMap: null, maxResults: 0, + /* Type sizes and masks. The data is always fetched as 16/32bit number and + then masked to 1, 2, 3 or 4 bytes. Fortunately on LE a mask is enough, + on BE we'd have to read N bytes before and then mask. */ + nameSizeBytes: null, + nameSizeMask: null, + resultIdBytes: null, + resultIdMask: null, + fileOffsetBytes: null, + fileOffsetMask: null, + lookaheadBarrierMask: null, + /* Always contains at least the root node offset and then one node offset per entered character */ searchString: '', @@ -57,7 +69,7 @@ var Search = { /* The file is too short to contain at least the headers and empty sections */ - if(view.byteLength < 26) { + if(view.byteLength < 31) { console.error("Search data too short"); return false; } @@ -74,16 +86,61 @@ var Search = { return false; } - /* Separate the data into the trie and the result / type map */ - let mapOffset = view.getUint32(6, true); - let typeMapOffset = view.getUint32(10, true); - this.trie = new DataView(buffer, 14, mapOffset - 14); - this.map = new DataView(buffer, mapOffset, typeMapOffset - mapOffset); + /* Fetch type sizes. The only value that can fail is result ID byte + count, where value of 3 has no assigned meaning. */ + let typeSizes = view.getUint8(4, true); + if((typeSizes & 0x01) >> 0 == 0) { + this.fileOffsetBytes = 3; + this.fileOffsetMask = 0x00ffffff; + this.lookaheadBarrierMask = 0x00800000; + } else /* (typeSizes & 0x01) >> 0 == 1 */ { + this.fileOffsetBytes = 4; + this.fileOffsetMask = 0xffffffff; + this.lookaheadBarrierMask = 0x80000000; + } + if((typeSizes & 0x06) >> 1 == 0) { + this.resultIdBytes = 2; + this.resultIdMask = 0x0000ffff; + } else if((typeSizes & 0x06) >> 1 == 1) { + this.resultIdBytes = 3; + this.resultIdMask = 0x00ffffff; + } else if((typeSizes & 0x06) >> 1 == 2) { + this.resultIdBytes = 4; + this.resultIdMask = 0xffffffff; + } else /* (typeSizes & 0x06) >> 1 == 3 */ { + console.error("Invalid search data result ID byte value"); + return false; + } + if((typeSizes & 0x08) >> 3 == 0) { + this.nameSizeBytes = 1; + this.nameSizeMask = 0x00ff; + } else /* (typeSizes & 0x08) >> 3 == 1 */ { + this.nameSizeBytes = 2; + this.nameSizeMask = 0xffff; + } + + /* Separate the data into the trie and the result / type map. Because + we're reading larger values than there might be and then masking out + the high bytes, keep extra 1/2 byte padding at the end to avoid + OOB errors. */ + let mapOffset = view.getUint32(12, true); + let typeMapOffset = view.getUint32(16, true); + /* There may be a 3-byte file offset at the end of the trie which we'll + read as 32-bit, add one safety byte in that case */ + this.trie = new DataView(buffer, 20, mapOffset - 20 + (4 - this.fileOffsetBytes)); + /* There may be a 3-byte file size (for zero results) which we'll read + as 32-bit, add one safety byte in that case */ + this.map = new DataView(buffer, mapOffset, typeMapOffset - mapOffset + (4 - this.fileOffsetBytes)); + /* No variable-size types in the type map at the moment */ this.typeMap = new DataView(buffer, typeMapOffset); + /* Offset of the first result map item is after N + 1 offsets and N + flags, calculate flag offset from that */ + this.mapFlagsOffset = this.fileOffsetBytes*(((this.map.getUint32(0, true) & this.fileOffsetMask) - this.fileOffsetBytes)/(this.fileOffsetBytes + 1) + 1); + /* Set initial properties */ this.dataSize = buffer.byteLength; - this.symbolCount = view.getUint16(4, true) + " symbols (" + Math.round(this.dataSize/102.4)/10 + " kB)"; + this.symbolCount = view.getUint32(8, true) + " symbols (" + Math.round(this.dataSize/102.4)/10 + " kB)"; this.maxResults = maxResults ? maxResults : 100; this.searchString = ''; this.searchStack = [this.trie.getUint32(0, true)]; @@ -257,23 +314,25 @@ var Search = { /* Calculate offset and count of children */ let offset = this.searchStack[this.searchStack.length - 1]; - /* Calculate child count. If there's a lot of results, the count - "leaks over" to the child count storage. */ + /* If there's a lot of results, the result count is a 16bit BE value + instead */ let resultCount = this.trie.getUint8(offset); - let childCount = this.trie.getUint8(offset + 1); + let resultCountSize = 1; if(resultCount & 0x80) { - resultCount = (resultCount & 0x7f) | ((childCount & 0xf0) << 3); - childCount = childCount & 0x0f; + resultCount = this.trie.getUint16(offset, false) & ~0x8000; + ++resultCountSize; } + let childCount = this.trie.getUint8(offset + resultCountSize); + /* Go through all children and find the next offset */ - let childOffset = offset + 2 + resultCount*2; + let childOffset = offset + resultCountSize + 1 + resultCount*this.resultIdBytes; let found = false; for(let j = 0; j != childCount; ++j) { - if(String.fromCharCode(this.trie.getUint8(childOffset + j*4 + 3)) != searchString[foundPrefix]) + if(String.fromCharCode(this.trie.getUint8(childOffset + j)) != searchString[foundPrefix]) continue; - this.searchStack.push(this.trie.getUint32(childOffset + j*4, true) & 0x007fffff); + this.searchStack.push(this.trie.getUint32(childOffset + childCount + j*this.fileOffsetBytes, true) & this.fileOffsetMask & ~this.lookaheadBarrierMask); found = true; break; } @@ -321,15 +380,17 @@ var Search = { "leaks over" to the child count storage. */ /* TODO: hmmm. this is helluvalot duplicated code. hmm. */ let resultCount = this.trie.getUint8(offset); - let childCount = this.trie.getUint8(offset + 1); + let resultCountSize = 1; if(resultCount & 0x80) { - resultCount = (resultCount & 0x7f) | ((childCount & 0xf0) << 3); - childCount = childCount & 0x0f; + resultCount = this.trie.getUint16(offset, false) & ~0x8000; + ++resultCountSize; } + let childCount = this.trie.getUint8(offset + resultCountSize); + /* Populate the results with all values associated with this node */ for(let i = 0; i != resultCount; ++i) { - let index = this.trie.getUint16(offset + 2 + i*2, true); + let index = this.trie.getUint32(offset + resultCountSize + 1 + i*this.resultIdBytes, true) & this.resultIdMask; results.push(this.gatherResult(index, suffixLength, 0xffffff)); /* should be enough haha */ /* 'nuff said. */ @@ -338,15 +399,15 @@ var Search = { } /* Dig deeper */ - let childOffset = offset + 2 + resultCount*2; + let childOffset = offset + resultCountSize + 1 + resultCount*this.resultIdBytes; for(let j = 0; j != childCount; ++j) { - let offsetBarrier = this.trie.getUint32(childOffset + j*4, true); + let offsetBarrier = this.trie.getUint32(childOffset + childCount + j*this.fileOffsetBytes, true) & this.fileOffsetMask; /* Lookahead barrier, don't dig deeper */ - if(offsetBarrier & 0x00800000) continue; + if(offsetBarrier & this.lookaheadBarrierMask) continue; /* Append to the queue */ - leaves.push([offsetBarrier & 0x007fffff, suffixLength + 1]); + leaves.push([offsetBarrier & ~this.lookaheadBarrierMask, suffixLength + 1]); /* We don't have anything yet and this is the only path forward, add the char to suggested Tab autocompletion. Can't @@ -357,7 +418,7 @@ var Search = { absolutely unwanted when all I want is check for truncated UTF-8. */ if(!results.length && leaves.length == 1 && childCount == 1) - suggestedTabAutocompletionChars.push(this.trie.getUint8(childOffset + j*4 + 3)); + suggestedTabAutocompletionChars.push(this.trie.getUint8(childOffset + j)); } } @@ -365,38 +426,38 @@ var Search = { }, gatherResult: function(index, suffixLength, maxUrlPrefix) { - let flags = this.map.getUint8(index*4 + 3); - let resultOffset = this.map.getUint32(index*4, true) & 0x00ffffff; + let flags = this.map.getUint8(this.mapFlagsOffset + index); + let resultOffset = this.map.getUint32(index*this.fileOffsetBytes, true) & this.fileOffsetMask; /* The result is an alias, parse the aliased prefix */ let aliasedIndex = null; if((flags & 0xf0) == 0x00) { - aliasedIndex = this.map.getUint16(resultOffset, true); - resultOffset += 2; + aliasedIndex = this.map.getUint32(resultOffset, true) & this.resultIdMask; + resultOffset += this.resultIdBytes; } /* The result has a prefix, parse that first, recursively */ let name = ''; let url = ''; if(flags & (1 << 3)) { - let prefixIndex = this.map.getUint16(resultOffset, true); - let prefixUrlPrefixLength = Math.min(this.map.getUint8(resultOffset + 2), maxUrlPrefix); + let prefixIndex = this.map.getUint32(resultOffset, true) & this.resultIdMask; + let prefixUrlPrefixLength = Math.min(this.map.getUint16(resultOffset + this.resultIdBytes, true) & this.nameSizeMask, maxUrlPrefix); let prefix = this.gatherResult(prefixIndex, 0 /*ignored*/, prefixUrlPrefixLength); name = prefix.name; url = prefix.url; - resultOffset += 3; + resultOffset += this.resultIdBytes + this.nameSizeBytes; } /* The result has a suffix, extract its length */ let resultSuffixLength = 0; if(flags & (1 << 0)) { - resultSuffixLength = this.map.getUint8(resultOffset); - ++resultOffset; + resultSuffixLength = this.map.getUint16(resultOffset, true) & this.nameSizeMask; + resultOffset += this.nameSizeBytes; } - let nextResultOffset = this.map.getUint32((index + 1)*4, true) & 0x00ffffff; + let nextResultOffset = this.map.getUint32((index + 1)*this.fileOffsetBytes, true) & this.fileOffsetMask; /* Extract name */ let j = resultOffset; diff --git a/documentation/test/_search_test_metadata.py b/documentation/test/_search_test_metadata.py index 33711f50..89ee55b0 100644 --- a/documentation/test/_search_test_metadata.py +++ b/documentation/test/_search_test_metadata.py @@ -44,3 +44,48 @@ search_type_map = [ (CssClass.PRIMARY, "class"), (CssClass.INFO, "func") ] + +# Tries don't store any strings, so name_size_bytes can be whatever +trie_type_sizes = [ + {'file_offset_bytes': 3, + 'result_id_bytes': 2, + 'name_size_bytes': 1}, + {'file_offset_bytes': 3, + 'result_id_bytes': 3, + 'name_size_bytes': 1}, + {'file_offset_bytes': 3, + 'result_id_bytes': 4, + 'name_size_bytes': 1}, + + {'file_offset_bytes': 4, + 'result_id_bytes': 2, + 'name_size_bytes': 1}, + {'file_offset_bytes': 4, + 'result_id_bytes': 3, + 'name_size_bytes': 1}, + {'file_offset_bytes': 4, + 'result_id_bytes': 4, + 'name_size_bytes': 1}, +] + +type_sizes = trie_type_sizes + [ + {'file_offset_bytes': 3, + 'result_id_bytes': 2, + 'name_size_bytes': 2}, + {'file_offset_bytes': 3, + 'result_id_bytes': 3, + 'name_size_bytes': 2}, + {'file_offset_bytes': 3, + 'result_id_bytes': 4, + 'name_size_bytes': 2}, + + {'file_offset_bytes': 4, + 'result_id_bytes': 2, + 'name_size_bytes': 2}, + {'file_offset_bytes': 4, + 'result_id_bytes': 3, + 'name_size_bytes': 2}, + {'file_offset_bytes': 4, + 'result_id_bytes': 4, + 'name_size_bytes': 2}, +] diff --git a/documentation/test/js-test-data/empty-ns1-ri2-fo3.bin b/documentation/test/js-test-data/empty-ns1-ri2-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..d13e176c93508907b4566d3f386cda686e22f25b GIT binary patch literal 31 ZcmeZu4rXG20x2LZ3&bp7J~NPH0stP#0VV(d literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty-ns1-ri2-fo4.bin b/documentation/test/js-test-data/empty-ns1-ri2-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..3803349e0fed4e57d7f5dcf587f17eaad4282772 GIT binary patch literal 32 ZcmeZu4rXFxfB-2VB?rVTU@n+s0stT%0Vx0g literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty-ns1-ri3-fo3.bin b/documentation/test/js-test-data/empty-ns1-ri3-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..4d98643ae5e8c57b89e1d1123a14dd0e706122b8 GIT binary patch literal 31 acmeZu4rXFvfB-2VB@4tXU@kL|WC8#l{{bif literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty-ns1-ri3-fo4.bin b/documentation/test/js-test-data/empty-ns1-ri3-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..8b484e181b35ea031be7b3201b4541cdea912ae2 GIT binary patch literal 32 ZcmeZu4rXFzfB-2VB?rVTU@n+s0stUa0V@Ci literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty-ns1-ri4-fo3.bin b/documentation/test/js-test-data/empty-ns1-ri4-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..abbc4d41f05e2bf81142f62b47dee7d30d58caff GIT binary patch literal 31 ZcmeZu4rXFufB-2VB@4t5J~NQT1OOj30V)6h literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty-ns1-ri4-fo4.bin b/documentation/test/js-test-data/empty-ns1-ri4-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..4fbe1f527ca27d28ab46ddc03ec4123a63212ca0 GIT binary patch literal 32 ZcmeZu4rXFyfB-2VB?rVTU@n+s0stV70WAOk literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty-ns2-ri2-fo3.bin b/documentation/test/js-test-data/empty-ns2-ri2-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..f856f5b436f3bdd872a43d0e6ab13046c6fa78db GIT binary patch literal 31 acmeZu4rbzDfB-2VB@4tXU@kL|WC8#mp#d%c literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty-ns2-ri2-fo4.bin b/documentation/test/js-test-data/empty-ns2-ri2-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..cd7ce16ecd0a8d0c7831f41c7d3ce4f8fe30d4ac GIT binary patch literal 32 ZcmeZu4rbzHfB-2VB?rVTU@n+s0stWY0Wkmo literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty-ns2-ri3-fo3.bin b/documentation/test/js-test-data/empty-ns2-ri3-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..81f31146adc9e231c5ebf0f87a40faf2e0dff2f2 GIT binary patch literal 31 acmeZu4rbzFfB-2VB@4tXU@kL|WC8#m*8wm9 literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty-ns2-ri3-fo4.bin b/documentation/test/js-test-data/empty-ns2-ri3-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..ef2ee6500d271d84100529e6a903adab587dba79 GIT binary patch literal 32 ZcmeZu4rbzJfB-2VB?rVTU@n+s0stX50W$yq literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty-ns2-ri4-fo3.bin b/documentation/test/js-test-data/empty-ns2-ri4-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..9f94c887e402c7dee2df5438b166759bd0ebc27b GIT binary patch literal 31 acmeZu4rbzEfB-2VB@4tXU@kL|WC8#n4FNI$ literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty-ns2-ri4-fo4.bin b/documentation/test/js-test-data/empty-ns2-ri4-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..90c4aa8dbcfce188efa88f9219cc168d45fdb835 GIT binary patch literal 32 ZcmeZu4rbzIfB-2VB?rVTU@n+s0stXz0W|;s literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/empty.bin b/documentation/test/js-test-data/empty.bin deleted file mode 100644 index 36e30edcedd56ce0b203ee32f441a8b676543277..0000000000000000000000000000000000000000 GIT binary patch literal 0 HcmV?d00001 literal 26 YcmeZu4rXLv5Mf|okN{#9Acm4m02#0W8vp9hckDQx8HKh`=pLm0d%G>8n*tqBN=GOrNz*ovQE*CIW;%qBpxhWo z;7F+uV%-==;KryBV%-=A4vYg5>-|TnT=nq=l}YV?T;;4@7DD@gV^n~{hbZK zAG4rk_aUY^$tegl!*(gqO!{XlH*?wyfx)Z%b8LZs4lnc1p@M%Nt-|!QRRjoHO_&H# zVssEEK_^MNNRcK(mK=Gy>7kcCW^n~qGMhQfwz7@w?BI6pU?+F7 zi@Vs(9`>@20q$l$_t4~C1{q?Q1B`HxLmXz5`?#Mm#+hJ}BRs%^w3y;34{?m+oZw*| z;ZYvrah{;H#(y)K>t@a^{@XFN-9JZn`RByI%>RS_**r9Jjt58wsRr2}}<@{TM&S$ab)*gW(RI>EP`SzU?3urx0gvoKtbm#rZtW-*FZt z*q-2cf|nC~oZzcEUG%u$4FwM_t@)_1-7|HN#hIcc3pCO*5m}MZ# znJnkCT*&fomSs71<(STKF2{u&fjlen?9Ov4&-pxG<_UGv-_71`&UEv7H(zxV>7mfW zKo3v$@J0_`_Ymu)*vtN2p6cbzUViCic^`-SSo{CqqMIfs3;oUJ=)~w$v$>=-GInq& zGuh#(@v-?AFZg4g81wp_v7#6&x??3VR&vM6Vyx_rRm51u9jl75sykK_V>NfIF2?Ha zSVN38+%ZovSm?aLo`et*o}#eOZB!VZ(C`$8g>It)@q~z{NGx<46^bWRJjG(6+o)hX zAyZT`7CMbZC1asGsAP&lrl@2rbQ_gSQOFdPjD>Eak|_$AqLQ)DZB#NvAyZT`7CMb3 zC1asGsANh)rle#nbQ_gSNywCxjD>Eak|_z9l9I8|ZB#NPAyZN^7P^f}rX*y_O2$H` zv8-e)bO)78S;&-?jD>Eak|_(BvXZgTZB#O4AyZZ|7P^f}rYvO2O2$H`v7%%wbO)78 zMaWc?jD>EalBo!pijuL=ZB#N9AyZK@7P^f}rXpl2O2$IBQOQ(aaO2$IBQOVSWOkK%X=r$^ux{#?W84I1phLW++9aJ(6A=6MY7P^f}rXge+ zO2$IBQOPufOhd_7=r$^uhLC9}84KM;CDRZxUP00Lsnh8d6po*YQN`mGgpXHHKz=G( z6_HmEMqWW7`Kf4COkP1ac?AXKr=nF+c?DtR6%>}Ax~+OKpf>|j%N7QrRcguYfNcUU z?t$71B2VrI^nyTc2y7dmT9uYw638uqZ3I-S($b3pxhb%%fNE7*a#`T1ZGk7(1%B#k z*=|5Q0ktvkv!;?F;P(U;gv6Jrhg>Qh~n69OfMvJTx*fI6l%k PGB`Xk^VAO>of!TPjN!sp literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/manyresults-ns1-ri2-fo4.bin b/documentation/test/js-test-data/manyresults-ns1-ri2-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..ea42fbcf019168982010b96c3a179bdf0c839d0d GIT binary patch literal 6571 zcmc(jNoYy5KvK;iVV}z(n=R(TEL}RKx4Fe zayz1l7d26%$ic+r=yFppMv-uFNxXG) z&A#cVK`myW4l_}YS(uGEn2UL6zAVr3CSdUw<0k`5d+>VXdgm!dbGq&Ik+=;tz zH@4y)Y{Pc!z`eK+_hTm>z=PO@-PnV@=)^YMy& zI3I;$lVgnIpOIfl!%QF}U1WlsCFe!XJn!HDT zAk+C#Xd|8ES@Hq-k<>2aKG{c}BOj9Uq;3%qkp1L&a+X{m^^1Xs93T_q9JxqlF98yA zl)O*=ARGVxui7oc!(MBl&_C2aQYf^PdIoyeBG39p1_xGNexSVO#F}e0Yra_X?OGt# z0=pK9wa~6bVlA?3u~>`kS|ZjGyOxTz)UIV>EwgJ*X<%qxU?)Wg6HcjMXd9IbCu}&S zgQ0CyLYy$-loE!vQAu&aic?w`+D0YD2{XPj!_YMP$_zuhsLc4njIYcvw2jJ)FU>2GYsvbG7|_hfilC;HYziLFcT;<3~i$_69_Yb zGQ-d|Dl>sF6DTtbZKE<12s5EF!_YK_$_zuhsLX`IOsLE-w2jJ4D9nV)3`5(f%!I;B zsLU|5jmk_Y%!JAeL(>>3GYsvbG7||ikut;3HYzibFcT>=3~i$_6A3esGQ-d|Dl?HV z6DczcZKE<12{W-W!_YLw$_zuhsLaH|Osvc>w2jJ4EX>5p3`5(f%*4V>tjsX9jmk_c z%*4tJL(`ZjGYsvbGLr~1i88~`HYziTFq0@V3~i$_lL#}3GQ-d|Dl>^NlPEI`ZKE=i z2s5cN!_YLQ$_zuhsLZ6oOsdQQVc}h?@6|G8<^MoVkDM{s2v?@)`6P}!>M3qy~s#G~oxN@G7RZeZI zJ`Cu~fV9PffoPSsiToID$pQ_(6vTk3M)?*9LDi)XF6*;Tc?W(D2nV@=AC^27i4o|QA9SewxvL|3)&*!T9z0Smz&E` zJ&ME_x0}n+<%CLzQS@Mf^(v4`kWD*{Z|I($o$|Oye2pYO2K)c0aH`ff<3G> z4Au~VD8wKR2}nX4v_lHgVC7lJK?mfa6YLjtLl0a6cB{+4e(6k@1((AWFdOUwSHT>( z8s@@0u*)ofg|G+~!xFHI^}vVycmN)R37CWf@DLm{GdK(n!z1u0JO+=$6E`Ob zZLDcytc@4j_^^$i+URI!c{{t?dA6N*+xfPgcnX(dM~Y)9UQh95ihokfPqQh_;WV$N z`83V%X=Y_un_)b|OBp`Oa4thW%Ze;RS)R-CUY75&BytpU?96dI$H^S0bNriQQ3qQ( znCjp}2d6t|$+INS);ve^oXm43Pq>rbPPTV)ypuON`Kpsh7lkf%cJX8vZ+7u@7qM=N z-R$b-sczot=I3q}_pq;rmH+=&bnWAPKY=~VxixtP@GV4ip4^|QNcJNQ&ch*dW}UTW1&B& zWQszjsAMek8&Q&ch*dW|I|W1&B&WJ*G&q+~4g z8LtYj?o2bD}&$dr|g zg?^)wDGQmhlCjWlR5E2DQ&ut-`i)AaEM&?`#zL>LqGT-e2bD}k$W)Y!g?^)wsR)^h zlCjWlR5BGIQ&BP&`i)AaB4jE`#zMbQ$y9_)RmoWBHCC03h5n$DsS25@lCjWlR5Dc| zQ&ln+`i)AaDrBlk#zMbQ$y9|*RmoWBHP)1jh5n$DsR@~ylCjWlR5CRoQ&Tb)`i)Aa zCS+<##zMbQ$<%~QP03j3H!7K$kf|#f3%$m=lCjVqR5EoTQ&%z;`i)AaE@bLT#zMbQ z$<&2RUCCJJH!7LBkf|#f3%$mMlCjVqR5A@A(@-)N`i)AaA!Hg##zMbQ$uxvaL&;d^ zH!7KikZC9x3;jkV(-1PQplE{B>vRQ$6Qp8P@wkHUaRmhwq@q<3xq>iq1%(u(qE#`u zf^c#L1r?;CRZ+QuuyO^36{LQvUJU5XfYh>ufoPRlaywv~fb)Bx=7Pw{{eWH&$PIyQ z15~Th(n|ulC9sWvYE@c#Q6M)3wiQsVN=q&aoZ1#Rxh@D&U(0p_;sR=8;N;36NJXps z-%?uxC)Wl+Dq7|Lmf9RRxjG0^ueJFWoH#HrIMP2capAV|q8Ha3nciDA-)PMzE_fqf z^ctEo!4F^Xp|kl!^M^0~_}QEZC0o)hJ&~Er-rv7>Xsmy9Xkvf=;L!Bd_Z%1-{103T B#g_m8 literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/manyresults-ns1-ri3-fo4.bin b/documentation/test/js-test-data/manyresults-ns1-ri3-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..56dfd9e6d9ba47985c888d287824fe93effbd4c4 GIT binary patch literal 6702 zcmc(jNoxIr=f8wp!h80TJpIDy+ta^&zCUT+6>Y0Wj06se zD@MThX)s3TNQU7698})aK1v^TOsF3N7o9pTsUID)>qqa^^`k3aKRRpmW9TLw!^2Jb zDC(`KYBV(KyFd$^17qP_7zgL++k?KzM3@AV;e5CNE(CqcDR41N1wG+(m;ri#OW`t@ z376~fVHW6d=D=LI66V2txC-=e*TA*V3JV|y3G}E1C_)L!P=PAw!56|JxDKv|8{kIJ zkFgk*KpQNDWw0D>hFjoPxD9THJ75K@gjH}S+y!^TYPbjPg*C7i*1>w%0QbR0xF0q_ zJ8Xsy=!7oV0^P6`w!wDjfd^m*^g!%o-*55jI3fI%37J+K${!9(ycJOYoxes~NX z*O;C)^QWiFj&GW>WAIr0==rgJ^#6A1e<$ll`(LMy%-M6|193vMjMVQ>tP%UgYvK!W zQcRWEC1QtoUVJEi5)-7mDmui|;yv-b7_B?dD%Of&@w)g@{4HjW(Qi}i5ig5R#UEmt zZcLl#6)%X7#Lr@)u2D^Nio@cFI3}8Pw-$(X;(&NVd?o%7b9CueioN0$@tHU&rt2my z6@B7G@v-PKa@O=_+Ekcw77~7XSbMnwRg~nQLut@9FOu zY;T`8(A~RrKJ{$-U|;X7)1S!3k{L^_VJvUP@^P$S#tLz)XvT_htYpSYaja~{%5kh> z#wu~FYR0N@tY*e)aV$9v3d1irSrNuWaw-(YMkgZ~8_DTV7#p3CWQ-)IL}6@nQj)Qf zoEC+#(TPdMOx~GM7#j1=jKVnR%;b%kyfdRPHaatTVVZGYVs)GgCBXiq4F}*yzj@jhUh|qcAo)Geu*j=*%b# zjU{JBVH|X3O2$mdnNb)Uotcs`Q*ve$#ztqRWXzPD8HKUYnJF1FC1*xqY;^uDLXR?W1}-uHfGAsjKa`Zab^_8 zL1(67%v78ig|X3@sTeaAXGURcbY?2XOvRZ|7#p3LiZN4hW)#LoXQpDzRGk@xp|R@B zD2#*7Ox2jFIx`Amqcc-AW~$DN!r17{RE?RcGovszIx|&crs~Wn42?BsMqwOuW@^Sv z&6!ac8=aY&F;jD96vjqpre@64oEe3&(V3|kGc{*MVQh3}YQ{{;IW<`tI#bTc$x<`w z^rW2elX6Z_mYP9{k_{VN*AjGO6ds2Bx%|PG73&<%S?w5661mx zN8m`Q5MtdJN8rY&5MtdJ2M)jmF`q9|<*M&wud_aoFvbN zfj=(>j`4Q{Gfa+?69l2A9||?Q{n@%`_Po@eLs$B9e3?H-ivAp~`t$G_U}h%7hwuj* zSqb=-D2b6cNsuH-kxtS@(j-H&BuDbZ|J?%VA-$xJ^b>z2ykcBJ=8(B$9`V<98JSNm zCs&XK#9!?~vWP4uOUP2LCHu(%a*&LXd&s?HoJ^2OGDQxN`^f#IMW)GN@&GwPj*?^K zLGloJm^?xrC6AGozwuDh-)5+}HOzB*hd;*#{W&=_`}lxAn-jBVD~xOy)iCykaVm_{ zVSF0KA7RXoU{eH>5j+>cdlCE)L9PRh4h(nT$qu~Lfp0nxi(+LIyP`NA#j8<#7R6st zER11G3`b&kDTa??_%(((ajcJHB97H1?!%GL6^L_#%ye(pa3qwhWGC@Ja@sWbk_i^Rn2O#Z(qAX7OPbKW9BU#F!f}V}Te8>{v;RmF!qqjFs(J zMT}MKSXGQw?O08W)$CYZjMeQ}LyR@-m{S@Unt!m9B7_O2R4}xSN`@0QoYKM2HYy=b z7;#DoL))mNIAO&pEevg=661uKK$&4^8Utm9p&e9a0%0alW*FK=WhM}20%eAwZB%9g zVJ1*!7}`csLa%anVK@g&^9VFHDRWv%rLZ#%1lj|sVOrIZKE<% z6K3kl3`5gcS7sR6L1m^c%+!?`hPF|esS7i8Wrm?`RA%bJOkJ5_Xd9K8x-e5$W*C~r zhBCv@4k|MZVWy$XFtm-zOhcGyC^HOgqcYPFW*W*2L))m#G=!OkGQ-d|Dl-jX#ub$s zpPEirRC0VOMwK2{6nvv3$rY6-pNdwc$`yqxS5&fm zYFqVUKyL=5EiMd1tF$Gz1Kb3h+XJ;1L{9Dp^nyTc2)GSUt;&{O638t9Hv+0v+0u&w zxhddQK(#7ca#`Tiw!q1CflsY1?gqpKsEvV>D+8a3R{7adTLUN820j(7^0TEj2TraI zd}> literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/manyresults-ns1-ri4-fo4.bin b/documentation/test/js-test-data/manyresults-ns1-ri4-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..6b1c4941afbf6c740ecf925dcca10f1fb1693e4e GIT binary patch literal 6833 zcmc(jNo-YR7=}*^lvXG3J+G)Mer^j)hE})$+TcQ%0vEwlmk@h09xVL99c z#ogZmx5903JFI|}Q2a_(!x~r%cfg%+7u*f^z`d{z*24z45AKHtU?V&T55Xqb3|pWB zw!*`(4IY8*P=QXULKk$y4(Nei=!2cm50Anw7=S^j!4M3?W3U_QFao2n2lm1~cpRR9 zCt*JvfT!Rf)QcPAF)HqXqocVvMmo!*zpp%Mwehb;%cHV?{5Zn#B76d;p>+a6U=tjG zH{lyN1G9OmR>CfL2|k5iU>Z+a230r;AHh#BiKnj}Hp3Xa4d24wu#l&69qfVE;7j-u z=J2Ghf&q9LK7(IjI!|v7U2qJJ!%1jq<9cBW9D;Y?JNO3{@uaVZz3@7G1!rI`PycEd zgje8m_zh<8Ml6SJcn&^>pJ6g@i4Prc7~X~N;a^zH+p_`o!5i>3`~~xPqt-wTUWG5< zcbGYY2N-t1^Kb%AK`U>bgRO7`-h&@tB5&g|*a}a>2k;}b@P<0r2G78Ua1vU1YeU!$ z&%$vy1#P^^F?7N)I02_&3U7A`yWxHK16KV1|60}#4f*YrN`I|?q*7T@?-}S_>Xq5f zk->olXFn*$oEUTMW-Jh6fgKCQSZK#0F&5deSd7JXED>Xg9ZSVnYR57$mf5jfjOBLB zDGh|?7wn`6VZtdDgtk%1aKeUDItXo}65@mrr<4%dMkU1wD^6)4w2exP6J`QshR`$y z$_$|$RAvHUCQxPwZKE<12s42)Lueb7nLwBclo>+XsLTYyOrXpVn#NF>A+&?aOeoBR z$_$}xRAxe9CRAn!ZKE<13NxWHLueb7nNXMsl^H_YsLX`IOr*>Zn#M?(A+&?aOeD-i z$_$}xRAwS!CQ@byZKE<12{Vy0Lueb7nMjz4lo>+P7%MY`c2Jp#g_&5HA+(LkOf1aA z$_$}xRAypfCRSz$ZKE<13p24YLueb7nOK-flo>+Pm?$%Zc2Jo~gqcK{A+(LkOd`xA z$_$}xRAv%kCQ)VxZKE=i2s4Q?LueXPWrolWDl@4tlPWWWwo#c$g_%^DA+(LkOe)Nz z$_$}xRAy3PCRJt#ZKE=i3Nx89LueW^WrolWDl?fdlPNQVwo#eMgqcj4A+(LkOeV}^ z$_$}xRAw?^CR1hzO=GUi5ZXayCKqOMWrol;Dl@q-lPfcXwo#eMg_&HLA+(LkOfJmi z$_$}xRAzEv#`#K3k(y5DD>+3fMwK4t3qQ_Rf{IkMDn-s0j-0O~6{%=dnw&2@IbVq? zQqihZIbXPPzLHg>wpA|%^kzWXVqqX!r7gJ~U=wh557bx?Ik_Lu3j(l%Xl`Xv_ zkXr&a0;*Nn(u)GQDPSw0T9qxiEO2UD;N-fXNUbe)1L6YI#=yyyL6M49`EIGLfs<>4 zA{DLj-BOzaCszkWYFZnQV12Z!d!SmcpS!I*@8%jK<=(RKpfx@?=RrR29vU;nH=pxI sXXAs$H=qCKXJe+ht!Zl0tV#2{`NP$|o?3OVr#@Wm?kO+5ceK|1A7*~TbN~PV literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/manyresults-ns2-ri2-fo3.bin b/documentation/test/js-test-data/manyresults-ns2-ri2-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..62ecdcde095240f8da7cb38c08577763de601fd6 GIT binary patch literal 6552 zcmc)OPi&KQ9LMo@yZ+hwcU{*N<4wE#8JeJ!F>x^@M*mduGmA{@IxCpQDTXb8wk| z?k)J|R0XD|ts+3sYC?pG5T%nYV#G<1Bt@ETGW3w8mmGcMnZ<1GU=DMc$9xvBkUP1H zeim^z_pq2HEM*zXxtIG`!Ac4^6mcn0rh-S68uzn`)vVzG*76|hSkDF?Vk4W_%)@Nq z5gz3+w(>XwJi#`eWIIo>gQwZaGwkA7cJmy2c%C{h&|oivyvPvy7-l~syu<-U8DpFY z4swW>X)?(auW*k2HUXXf_6G6@fxfJAjki{Jgba1$X(;fWK!5P_dqa-`=I%#zBPA6Y>@{88DVixhPVs$;-&4#QPxD)vd^hX5Ind1q-F(x{ zuia!btjRE(;k^v!GW?Pu-9xR1!5&WbaIS|db{Az?o8>^3Q(4Yuxt3*4FPnR5_Hw$H z3%&f+OMi}m97l6}mg8cM>p7P9v9pikeVpy%av#w=Zk~xeXYyRlv+n=@iLhy6qOhV~ z9~mE+tk;(`her1;y^-yo92@Pwd0}SG5p&Lp_PL^%D~dT+%(-H&B<4zDt}N!tVy+_Q zDq_wPbDo&1in*$otBJXqm~#|}h3)UOBT1Brqfjgqor=X#E{=k+P;@F9N7*6rIY*RYtBdvQTs?BUc%@%E&^| zsf=7@R8mG3ws)44k%eMX8I_b#Nf}uvI+amL8I_cgg`!g#m6TCQ8CfVgl~G90R8>Y6icV!zRYp~1WTEI(Mpb20RYn$yPGwY8Mpb2GVS8sy8CfVMl~GL@)s&Hi zqEi{wlu=C?StvS{QB4`ul#zv^QyJBiQB4_HC_0ra+BIR&NV6cm@As$K==6qJ}#P-K3pdKH>eP-;#=vH7X!)ys$f*gi-%TS};2 z>83Xjwr#k%cxr8=9KD0kO9;J%u#JQ2m2P?wp*In>bx^(1O)n$#Ho`U!s#m(ng@hwF z5{_I+_^EKS{eyT8ax3A;wS=FlUio>Gn+Zp*Cj3&h)R_HD1DH8b<*TfVcluCyL~`?uHDOfVKm1@hs!EIim4 W9vW|q4K)uo28U*z{JyF2!G8fiufxdz literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/manyresults-ns2-ri2-fo4.bin b/documentation/test/js-test-data/manyresults-ns2-ri2-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..858d45663c6dd2a716246ae4964843daa90138ad GIT binary patch literal 6702 zcmc(jU5He59ERUrKUQ5`KUQ5oQ`;=f)cMbubLO1N%>2sCthTbWn#OI_&Hd13SF^G- z>ms6ykdTOw=)wyxyy(IUi3o`Z=^~_yh%O=`B0@sK3oq=QS!Bd{x^Cg&&%Wn3FK6aC z1H*62+OFpDl8%{^O;Xz&>205*bVNt>mef=l?Mpr;){aX1$l)=EmJ>!Rk}~Bb-&i= z0j+NP)VjJ9isp4D@DUM0PtvUaLl zFRDkov|D@BtCzG_ed^bM2DMN7^|C4&(y$KbpkC1-y{gyrx(@3Ny{XE&+Q(7aJaTmT z15wk^_S(@~t{nq=M*bVD9i;;!$6+7Go27H+SJOI5ip&mk%$znC%~jKBNn6Z8^QpOD z{xJ*2NSjQ>d}6*af19~urS)ded}Pj>zf4Dqw8rc;ADS=CAEterw94!@ADDCIH#6DK zPG-8z`{u0q#k5Y4VpB5jn$OM8rlnO1W`}vloH0L|QGU9Xn{DQ(Ic^O`wjE}Cm**-XD* zbIhDEKbe*eJ2oZro;hnSn=s3+%$ooIZ>%;94(3*rO1%TUL#5J^N>AUer6bv%q5i(k z>lbQs0p`Mr#<@JqfgCx6PI6Qr zM+I`^5IV_GfgBackwfStM+I_JAV&@xJ7aR>5GKh{Opao5 zVshjVI>}K?j$(4;5IV_GOpX$ALqC*N7h1)v{h5+ z<>kYFY#-2@mlD*A-gpDyZNv4&Q+*>9cn85t2;M??<3PRWjTaHTiSX8edeIv%BX}F( z%>(tKH(W>r+(-mmNmNtt=KTZQ18yY(t|h7|_2TypHxmI@6V;S@@%x6`iGb^gYTDRa zeBT7T^7S8jN)Z+ai~ncAyw_|00sQh)W$zh3Jz%@dm1 enmWeJ)53k_-8}>4{+`Oda(7Sd=64MbbpH##F~wg1 literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/manyresults-ns2-ri3-fo3.bin b/documentation/test/js-test-data/manyresults-ns2-ri3-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..4e3f2840dcdd15bad44f16a8b4770f26457e77d9 GIT binary patch literal 6683 zcmc)Oe~8m{9LMqJw%d05z1?oNOik-5HB0y1ciVT%%*@oR%*@QJY@OGsm-j>4T~=0J z`GheU)#g!D&5e~9!)e}qJYM1(<*e;5e$M}?GxMN~wDy}u_iaj*XF;65C$z3;Wp z?yWO-#TLP0D1ifIuuE2;3N`Sc4tC+2VF}y< zOW{^n2Dia-xE)r&9k3Es!D_e@*1%nGH{1hj;a*q=_rZF&A2z@Pun``FP4EzGhKJ!1 zcoeq4W6*@hVF0$mAUpv>uno4u4j6_fVJD2hD2%~4?1J6!6trLhCgEw=1JA&-@Eq)g z=ivo-5%$@by#~Xxd)xU%z|M)U{B!tg{~Y^f`seTcv-#8X`AdLI5HCnG$ble7gPaO- zKFGWf>q6`aaX7^1A$|)nyNlIb?C#>tE+) zd=%kKgj|#*QHG)%jPhZW@1mr-@wyr4=9O+f=;qsQVlmtpTVfoD@qUccF~V^c$Jrcb zf1D$6PQ?i%SeRgAf_(|zOK>v5KMCd~S)XKYl6R7PndGk|{VCR_*puSz6em*ro?=d# zHECLD-b(XXnqSk*%&;=Uc!oDJ9MAA`hGLfGS$1Z5Jge$0~3u{6i_9Ixg$mg9#U znI0NF4EAuahhsgQ=^>wIS)QGF4&^zX=Ukqdy{zt~)yv^tPW19;FZ~7971&$g-2x{I zoG-Ajk4=5-@8f76r~8N&af^%>Ia1_ok>&sYSA#RsP695LrC>YOW!xw4pZ#hfeVDq^l8=Bi?@D&}fpt|sO@G3SZ7x|pkrxrUf) zh&e}rSlIcOb|i^1aTJP$qEoRr%EeJI7K%d=u||GGAb)0 z3p+c@%E&@7sf^0XsH}`E6rIYbtc=Ra$U@PnjLOQWtc)xaoyw@JjLOQ$!p=@t8CfVM zm65BATxDdT=u}3oGIEuXg`!g#xyr~@Miz=rW#lR&R~cC-I+c;Dj4H~=!p_c$GO|!i zDx-=rswg81MW-^VD5HupvQTs?qlz-BC?g9+r!uN2qlz-Ju(PwOj4TwB%BZT0s>;Yh z(W#88%BZT0EEJu}sH%*r%E&^|sf?=1sH%)C6rIYbs*GyN$imLfnliFbOe&+AGO8&f z3q_|gswtzIGO|!~Dx;b*swpE2MW-^VDWjS)vaqw$Q$`kwNoC|IBTpGwC_0sqr;I#h zWTEI(MxHYAl#zv^QyF>6$WulZicV$ZDWkeFvaqwWu8b@clgg;BjOxnBLeZ&=>dL6D zj4TwL%BZf4>dMGM(W#8;%BZf4EbQ!TC?gBSq%vwKqlPlFP;@GzhB9g>BMU{RGHNKJ zhBC5HbSk5UGHNIz3q_|gYA7S8q>%iyv(+gnCO=iP3d$)dDW{~U{8aTSET^QjoRZ@5 zQ`M`$oRSiAN{Y-+Rj)#GN=nTsDKy;5}y|r|EgDHF@TrzVn-RzM1F$C6nK(<*R4R z2DXJ$XTbL3VOGwWY=x)cndC$5{qix#VZEbs%=B?$?-)LP)NSF&p!O@U!IS-D7;~-BsA5MTg zz)5g2EPzw;_^=T2IH$uIa3(B*#c&qn;m(G0U@4pnB`6?|T7fFmpbiaaLLU4)I3F&6 z3*jPI2Kg~AflFaITn3lJ6|e%Xgq3g=Tn*R2D!3M|gX`f2xDi&vO>i^Z0&Cz_xD9TH zwQvXA33ovo?uKDl2P1F~jKX@@0QbTe+y@(B95%rOOu}ZkA0B`XY=J3w5FUbu;SqQg z9)ri>33w8o%2=MY>n~5&J-!<19$R+xjdxxUe!W7JQv;#yTYtowj!(z&xUux z*I{OE;5lJUcsjftz6^hd#krcR!xQ1H@J0A5oIWSM!z1C%@Ok(noRUj?b(jjThfl+A z;l$kR72*EyYWO(p3CHESFAtl-%i+VYI~<*NU|ARoFNXKSk6~_JjAdbCcsYC&_JsL) zTULZlcs+a;{s;^63SAc-3vY#;;qR~{@70>HExZ%H3A6H|RYE&FA9jS_LXo#`GFilu{dWtl6>Tt((8GFO$k zs?617t|oJJnXAiOL*^PX*Oa-Y%(Y~$C3A%dNjUhME>wv*DNIU2=`<~cc_~axLg_R$ zg}EtAPD1H4J%#xxOi)7UG)09uDx0H(gPmn_lu#zkQP~`o%~3+>G)HA~R5nKmrPCah z%~9DLC6rEcR5nLtbChtfvto`C%A`4}n4^k0N+_M?sA7&P<|v_bnxl$2s+gmM(rJz= z=BQ$h5=y5zs+gmyIZ8O#Sv5xqWzrl~%~91HC6rEcR5eFcbCggz%~91HRn1XC=`=@G zb5u1)2?slC<|v^|nxmRIs+psN(rJ!r=BQ?l5=y5zs+psjIZ7y<=BQ?lYUU`Rbef}@ zIjWnZgoB-RbCggf%~9PP)y+{t=`=@mb5u7+38m8<)y+}e93_-ab5u7+b#s((u(M%~ z63V1GYM7&jIZ7y<=BQzg8s;dWbef}vIck`rgwkn_8s?~BjuJ|zIck`rra4MD*x58k z31!k8HO*1e93_-abJR3PO>>k`I?Ykj95u~RLg_R|O>@*VM+pZzTjnUCOq!#XIck}s zgwkn_TIQ%_juJ|zIck}smN`l&o#v=zj#}m@p>&#~mN_a)CaIeawiYGR)J<*HL=`17 zRg_FsH?>}qRg}zDQ8HcK)Ot-=Q8Hsi$&__d>osXb$*dJ6)7DL;*Ow3fv3*c)SxQ*1 zdh-oLwhjL-p86Z9!gmn9gzzmyHV)RS-h2_^n}}>3tXIAHGQzhJ**sXUdeenOp&N-p zR}$S+yk-9&&!Ah0Le~=A)Oz)O)6GPotBG!Ez52fCcB0VrL^mDm?cd1G)Vh)J;ZA4o zZRtKgVSi+LZ`!|h{m<-mvG@5o`ZK++-s^AH{%87Mz3*SI{h1jD56u~xxBm$&*gU*p VbYghZXlL{A$Y}53*H2B1`~xI+$DjZJ literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/manyresults-ns2-ri4-fo3.bin b/documentation/test/js-test-data/manyresults-ns2-ri4-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..9b295b7abb8419592c0b109785c34a560ebb7c9d GIT binary patch literal 6814 zcmc(jPi&KQ9LAq@>;80GyRF+Q0)kEjM4@m0S42bvM8%1Sh=_H}F(&&1b`ud5lmiD3 z#1KP_F~oy09tiQ^!4P8%F~)H4z<~n?55^Ef3^B$S4+fuigp|;aXP10_Yo31l?0xrX zljgf|&E`mlq$B2dM0)#H>41MX>ade{%)3Snm8RLVCp@dS%$~P}=g^(uIet%g4yVI& zXCXXi9*_Z7*O`qvEDHC4F z9OJ9jTr-8uN%*Yu1_d=25f3JZ2s@PneD7Ni%4kGMmiP zX0v(5Y%$N8t>!ti%{*_mn-|Ou^P;Jkm&}maX@HBn7Obt0;7qq-bbU$a&}gx2UsK#a0cq z>b+Kd*{Yvf)z+qLn|8G6Xq&!h)5SJLV_F{5wwR8@bSkC`F*USnX}h+x>rlHsZ`b*D z{nM^R9op2PgB|*`LqB%t?+y)gYGbGNcj}W)o$J(}omvprhPbM6eH_>Kas3|G+=SL9 zG?mbY37t*ow}et%THU2RUHYI)-*oBME+xCQvRk9wdcRv|y7f!95;YE@Euk~)#p*`%%{HMdvmdsXe#$zGl7)nC0D=+j`I4)*D@KArE=)jlol*VcX= z>DTFgUF=s&O4*dAQaY8=<&;+c|3A%IH#L=BR;i3lj!jo8i>o8!yOvzbc27@?4_tp@ zb}oRqU|IcK2Iev_mxZ}3%;jJ%2XlFt%fnm&<_a)Zgt;Qjm0+#}b7hz-!(2c@9M=D* z15`pz0+QkoI!Q}FUIG&15IRXsKyCt(;}AMYPe6VG666p%Nl`$KGUUi%eP@OoIfO}a zlp#kMa^w&?$x((JWyq03=p;uOa+D!Q4xy7AWyn#6967A-%#tIAFiDQGI>}Lv9OcN7!}`uVIdTY-}Li92LlsL+B(& z1#(m%M-HKr92Lk>fgCxk?<|rdhcHQwisYzBjvPWKIVzH)A~|vho#d!Uj*8^SA#{?X zA~`COBZtsQj*8@{M2;NRcb3SJLzpB-C2~|EM-HKr9F@pXi5xkEPI6QtM_c7A#{?XGC3-fBZtsQj>_byOpY8vCpjvUqcS;i2%Y4p zOpbyyNea{Y)*wxq!jxu7RFEc9L7G&BDfN=9AWgP{H0cUc>Lp=8nv4Z$QWmDvOVWZg zSqsvnEli=8mkDF);|+wj4c8Y>wT)E3I|yDv@D{=w2kJ#{yolgUgtrdV zi{5w{!P^LL9;g?+;X)$7jYNPei7*9k-ao)K;8r5QwM3XwFMi%|GZElwB21|lKX165 z2yi_SruDtGcVu;D=kWMYwR+>W^rkzkja=KC*4}otXKr|7-*g|fnb}w0@SU~xOzqV- me|xRXL}Cr`hE#N(7VaGy9hn@O7^&_Z8XlRw_+2xT!~X)AC&W(x literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/manyresults-ns2-ri4-fo4.bin b/documentation/test/js-test-data/manyresults-ns2-ri4-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..8097294ab4baeac46e5384a206be4eebf6c07907 GIT binary patch literal 6964 zcmc(jPl#1z7>Ccyq?VRuYG!I`ljUUE{m!}P-g_!DGc_}_vNE%}j?*|!&L8d0WTvJz zw5Vti5)u&-5iVS~XyHO4LLx$1gtUlg5fKp)5)v+4*mLe6SG-T_gvXEh%{xEu@%au6 z@7m?-Td#|vXaqiMjiRYDqv##Zw&(!KL3k6Qmg-fb#|`zPHe>XdTR%GQs2_cc>ql2w zKepUgKZcic95~QY|AN1$raOxAx-l>o#=+Ha4UC5ga4qDYYa&d7>tQnF|Na!13e(_5 zm<~5V{-JIL9wC|qv*8w)19M>>+zRb*8_b8>A^-RbpabrNg>V-vg8Z58h5`hLA%P;~ z4_bmUR3L+U;9kg|ehJ(UOW^@n1`k61U-A&FfR(Tc9){KM2&{oeVJ$oc>)>&C0-l8R z@Dw}^&%g$F7B<3junC@r7vM#x!e;1%EzkuoK{srL9@qxG@G@+NKIn%57=#_L6JCKD z48btG3cKJn*bT449@q=};0@Rhwfw=jM)@;vY;4Vsq0RN9x2Jv#42*s?TtBLNM~@MX zLvRv)g$Zp4fK4z0$KVWHfOc-xTG$1jz-jmg=5W(iLk&KLZ{Tm3$?aPKgYY4og1=xo zH*y(lhY#RO_yeYJOP4?oybmYgH<-lD&7ce3gA?!zOc>84fhxQWpTo~EjvF3e6TAh- z;YVoW)-Qq$a1f5c4{#AWcpKKkJ~#^B!v&bn8?p{|!>8~aoQHY5HEUoPj=;BY4rcQv zt%9BK5qu42Va8-GCiKH$_zM1nX}obup%)Ip7w|hw;VoPW+u<;rg0nD_H**!#;0T&#~#2h8&h)_DsQDTmY=7_MlvuKV8 zWzrlK%~8=D5lW{yDw?CBIUleM}#tIj#6`!nj=E# zG)Jj9O3e|Wbef~o9Hr)nP&&;~YK~HKL@1r+C^bhVb41wOSu#h2GHH%V=BQ+j2&K~; zmCRAe91%*VIVzc>k~t!jPIFW;M_h!Y>o(}(;St}QP~_3N~bw0 zo1?NhB9u;ZR5nLtb3`be=BR9rD&~l=xwB%92xZb7Rm@Sv91%*VIjWeWia8>bPIFW- zM-_8KD4pi0VvZ{2h_JacGe?9nX^t{;l$j$!=`=@~Im*ltp>&#~%p7Irh)_DsQD%-Z zb3`be<|s2qpW z>osYiVAevxwB@Pv`tspFwh!u!rG)jWH{U?8ZMd{}YHXx}?;v~$;adnc4%VyQd=cTB z2(}K^tKNJW;oAr{57w*RbRiLRBN22Zk*DH~{eyf4-AV*qOXR8b>iedfiJ+^AJhfhZ z-*h_>bUl%$&Ap8qSsUKc)z?|8UA`^7;t3lgqkGfFwQGFmvWtDib2Mh^KYiKntc~w9 qe)`JaUK=y5<69=SOdm5Vn!BU3r+c8Yzq_`hv#Y!Q;kOPCbo~oBrp4s| literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/manyresults.bin b/documentation/test/js-test-data/manyresults.bin deleted file mode 100644 index 4d3eb35f13ea8547586e8fac5a707c7b80de6bff..0000000000000000000000000000000000000000 GIT binary patch literal 0 HcmV?d00001 literal 6415 zcmZvgNo-Yh7{$*mZ7Br`ZGoZ!f*|v7|98F&>IE4bm;@0DQc7u|TG~pf0!~1!#>8Rg zuvC{KF~(`yHeCFC{z&f@p_a_)Ce-@U*4l9zA$raj&Wp7wyN zvw>6mI|1i$0T%(U7U+OCrSjSW48h|FU*`dx@D>4m@RkEz@O$H!_fJtb?WK6+SG+`R1qZut|#SF~EEVN-ZuEX`X0dp`H^Kc{PV*zf$LM+0~Sd1lD zie*@i6#!aha0_n5Z78r2n{YceV+*!o8}7iJxC?h< zJ9c0vc40T}!5-|zz1WBQupbA|j)ORa`*D~Te1sQwloxdj-RQw_oIo!gz=OQlljz3) z2JsM1@iv^sFdoJuID@k|hez=k9>)`SlAoizM;j}5ZJSr#!5toly}cfbympTz-jT}t zp32cazD}<}k&?q?lw2ZTlE2A<2`ILa0rC?0i2OpDYf-EvUF13P9{GVxtV7|G1LPuk zlYB+~A&cu#>?CK%YveQX2bnVw#b(k^UM3%tUr9>?ign}|d7ivaek2W(P&m>~M#v@d zHTjn;X+*J$oF%W5&&i);?qn2O$N+hTd_sOBty55}C*9-)@&WmYOqz-!AP31){2MX`$PCnMxC`IgkqK(U6jlTq?E`Hs}j}@;zyo#s5nV zlV{1h0oFZl@KS4IHiQ4ZB$a6u;P>!hPF|Oal%ZX%rG>KfilC;4k|N&FcT;<3~i$_ z69_YbGQ-d|Dl>sF6DTtbZKE<12s42)!_YK_$_zt0sLX`IOsLE-w2jJ4D9nV)3`5(f z%!I;BsLU|5jmk_Y%!JAeL))m#gu+au%rG>Kkut;34k|N|FcT>=3~i$_6A3esGQ-d| zDl?HV6DczcZKE<12{Vy0!_YLw$_zt0sLaH|Osvc>w2jJ4EX>5p3`5(f%*4V>tjsX9 zjmk_c%*4tJL))m##KKIX%rG>Ki88~`4k|N=Fq0@V3~i$_lL#}3GQ-d|Dl>^NlPEI` zZKE=i2s4Q?!_YLQ$_zt0sLZ6oOsdQKnKHxB4k|O5Fq0`W3~i$_lL<4KGQ-d|Dl?fdlPNO{ZKE=i2{V~8 z!_YM5$_zt0sLbTTOs>o@w2jJ4F3jZ03`5(f%;dsMuFNpBjmk_e%;d@pL))m#e zm6|d&oz7Qs%2bRhJ=+6RjG2maOHd@ zt4wXHUJU5XfV9PhfoPSsVnA0{eWH&$PEFv0jgEm(n|ulCE!LtwJKYB zQ6M)3+zO~xWlJs#oZ1#Rxh^PEYm2)9@d4Dvz{!D|c delta 183 zcmW-btqKBR6hzN_yTN2K8N^@^1h*JASrmgH2!hF?u&%)$SQNDAGi()n3LnGbBROuk zcVK2X_kP1CJZ7VXVxB-xaJO2#VmP20Tu>d3`ul3aj?jR-1!vTOwFpiIa6>5+Xjo-q v$k4Rn%;AKVc0}a%rpmUECy00C)!00001ZG->-00BCR000321OPga0Du4iWtIQ{00C#700001ZlnMJ00CjD00003ZFX`R003wJ0I&c600BC-000320026~0Du4iXvzQp00DH;000930RRI41poj6Dc%4800AiG00001ZtMU600LoY*Z=_X000312mk;9WdZ>J00C?U0RR92XAA)V00C|i0RRC32>@Xj0RR92bRGc!00Cnr0RR93VP&cS04xCj0RRU800Ct@0RR92XFve}00Ch}0RR92a7+OJ00ClB0RR92byxua00DDe0RR92AY=gm00Fyd0RR92!f*iq0RaX8Aa((O00Cuu0RR92XM_O&00Ci&0RR96ZFX{SbNB!NXaE2*0RWHz0A2wAD*ymO003G50Db@flmGy>007JY0NMZm^#A|>0RRpG03b;^NjOaq7yt=PVRUE!ZeeX@b8ul}WldppXf9}UZEOGl5(qjvZE0>OX>N2ZAZc!NDF7pFX>I@j06IEWWn*-2asXp&VRLg$VRUF;F<&uOWn*-2axQ3eZEOMn7zR2zZE0>ODIjBSZgX@1BW-DJ0000wI#OY7XJr6mY+-YAO<{CsUol@XQekdqWiDuRZEOSp7X~^yZE0>ODIjBSZgX@1BW-DJP+@0f0B~VvWiDuRZEOYr03gDaA9X<0CRO>aA9XkOK&AhkWo9hweIVRs51$>a` zKvpF$RMHSx#j~VulldtDW(0{2x$_}+G32h0#Wm6_3seNNf*q*wZEB-6vfd!m`=sj& z&=e$|aXcpdV={kA7Q3X`6Q~BvKC8I{YT0wrzaZ^P;Y_hTJ`D_jSJcdFfiz*>(ldBR zt^O$6!u`XUU#P`jN&ih4+58jmT|!99%0-;PutjDkNIx%gQFE{zM)g@Ty&#ONlPfH8 zYBEXXmYK z0}KE0tyyuDg0QCr=%YiuKIv0JHC=z(dvY&1VCWkBQ;{(g;v_n*+G?SB2AZBfy@u;Q Hn)vh=1VNAG literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/searchdata-ns1-ri2-fo4.bin b/documentation/test/js-test-data/searchdata-ns1-ri2-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..9b67dce2d025c924a9656080d64558ed9a14e9c9 GIT binary patch literal 828 zcmZvZKWG#|6vp4%`;$b$h(!`1fdwsg!9N52Sxk9u1xy{?c^gi&3-~)gb`K~X0OpZ^xlQINc6QHUr!N8j8nEvat>X4%MYtvUpaz>y zI?5f*SA<93Vb?zdE!+;L&@Slx0Y9$@Z1z*IAn#1l7u;{ob?3vzL|L79U^=&;OZwptI zHgP&TGpdW6=-8|=MdqW-*QY`mVmcvH*~XY_E~&>8N^)COn%G?3Tx~pL16t}f**Hwb zzN-Hw2iB+V-ykgH+O+te+*K=yQUv(s1J9pmhU6mrF zN+k$FK(I<>Wo6@a=`2L-th7mQWo6@gdngLB>~Hsb-@I?<%{H#Lq6ok|?~evJWU2Mf;pE+>d>!dH$8e_P!Y2i0&;plZ}U`fv3PbX?8*=iTxl`=aaGCUV|R%MZhX`PIm=SD8; z0ClLw-&Cu8TXaova8KNPD2^V9`4cf7h?B8+u%-EPK)hqNIb>I2`-SNC$O>}~azSCwJdff1d z1#7czNV=g|jfoo0v19|*-t}qGA0q9!JeOyqzEPiQrJFx{d2Z^i#c4m}#b4g03vK_e zwUkQdEKvQA^NyosK$MGk8i)@jaci_G4f*u>dq9($<2QPq!}Ql8Yb7PM=!iLHs+ASQ Nvi%8Nrg%IG=`We3kpch! literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/searchdata-ns1-ri3-fo4.bin b/documentation/test/js-test-data/searchdata-ns1-ri3-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..189938577f181318a1919d54f271d1af0b3ca87f GIT binary patch literal 850 zcmZvaF^CgE6o%hyOuVy@cui7>E{d`%BHR^vOreD+92k&`*y%C1&LxZ4Nyu&##6l4) z6br#Zun;T+3&Fz5R0aeK!9uVQ8!N%W+D`xX2Sq`a_r9Hf=6^f$W;-XlQB6d)Bbt%O z3I<<{h{1!LZbKH6EE1tf7=vBfXRPgCQ187W!fV34Rn&?r<2~Rt#CsKt z{isGtP7jU|z2ihUr3(x? z=+026x5M7(C#Ry)nM zEOuPgm*5Itj$Gz-bfjMudZSAV))sk4@=zU)ky6=@AtuDy^FFJFW61`tEY-8Iys^(#O$1yThU%53=_g$!31V>P3mw`6^uivG3e-jXx<&S(Yjz&mO715uA- zKg!krB(?g=7waiC%b)7s6^VX`{uddz>>JR~Hs*L_#ba8|;DnflqCd^3nPRg=_ z;|pZq61H7M9b zkWJ28lr5u)uNu5EV2(4a3~chJ{DGL`T zI<57qe4v((&RLshKFWNx8WL@s;!zP;yOqS%aD;f^%2KZF_3ibkR{QnkmuIK`b{G$R zS^e$qI-e&0nro@{Ht1dYkN3Kxry%OLv=f8}`{CxeClTfJewd=m4q0Z9C|~^r18XHl W?Vx2A%u;g&p`3@)*TdWy`}jA8`H>(1 literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/searchdata-ns1-ri4-fo4.bin b/documentation/test/js-test-data/searchdata-ns1-ri4-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..8e5acd73f39364d62de0b0eefc6183febb11650a GIT binary patch literal 872 zcmZvaKWG#|6vp4|c`*qhYLinGR|MI^pael=tb)y@I3fvLCtJo%%#0erR&*EbI_Ci>1U5dn&c1>jwvFSH^BrlG7Ezkf1duqGLdzNu&NPe4gs!5 zOMQt*`-;eUZL!oK-UrHDqd&VrxZA|=F0px^7(XPcCq(>=*m^;1zXFVzLDl$;(YgEg zbYve1_gT@zNQTvE{MDgMz^{@^F`!xC%e&gprW%j1y#2K4)sE&u=k literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/searchdata-ns2-ri2-fo3.bin b/documentation/test/js-test-data/searchdata-ns2-ri2-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..9d4a372c578c3a90bb6ab94d4f18f13c360eaaa3 GIT binary patch literal 761 zcmZvaF=!M)6o&uV+?}3CkRap~kpV?^HHfhg8B$0DG2lVCK(G+Q+&b=UxSd;W_kx8; zgjA_g1#GOWtgLKeA;HR0EVQw(u(GnU65l@wq9DtD!~19cH}AdO?#-3xD1amKzE!~I z2-uZX$pe)%L{>2mC_hc+Ck2=iBs%P!4|^BG-W9UAMw$hIieMJ82{pb=ZM00*t7LkQ zbbSGug2Xe9$E1Hm=1<6Ci!|E;)qvSyHn&SHdrtZnqPIiN|x5)Ai+3%5)yJU5r)DOtLb#lLC_7?Pp+LRoRsbyQF-4-^bzq0xn zI=rf|qaYbB0gHeP^C|EQcmsR{z5>61w!$d|y=0cIcTaTC?%H|)ZwptIHg$|H59(qF z%t*J!6uFOcU(ablf^!neL_}Y8X+0Vv9onj*X>ERO{y+=%2pzNz?TJoDzN-H+_pHy{ zzuq7PYXh_YwJuxnl!9=oB~|GCJ-ssNQ$uyI9%krCb#lkhHTcOOKb)ZyC($uAt!A5N Ppy~S4c4*__#HYUj)BKP% literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/searchdata-ns2-ri2-fo4.bin b/documentation/test/js-test-data/searchdata-ns2-ri2-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..a48977fbc3a5f477f933fcf8e08d52acce38c4fb GIT binary patch literal 839 zcmZvaKWG$D5XNWr{=~B|B9f#quwcMl@DG6?;Yk{`IpjbtAc#eLw>S<9ok--@KW7GrPSj>p_QzW<-sE z=uCs?3lp*Yh~uW%#L*GJ&jQ(;dL#!qUV;-v)A)sH{31}S0p_ZJIUsY5Xoq;*hdsIl z)B_;N09Oi_T3UG{dlv4FWr<{2ux7qHV;fPVwncZx=_IbIZQi9V{q z=CiKSqxpv9;dj{ePeB9S;TAdt?H};7ioj;S1atDtB!giWBbuKB(iOm8(l~d>UdF!e z0!d#HSf|&zsYi73>~ciY60lo9xeW~N0h3*zdH{rvfc+=H!E*s~o5Gi@Gj^|Gr*8rK zUeS^fl+~g<>JV-VKZ&%OzOJ4q743?iiavVEA}2Z_Loueve3be6Y$!`ir)4XZ#J}N^dNigaw^gM{8_OHZQxE9@El~R~ zJr0wRuj;>&`_`xK-&|NoZPNUIQ?FaeDP_T_w%j5-*bmny1NEqy@~}c*ZYTedyQaQb cl8@G?6~)0(KF0H{Qxs~}pSID)orzC=18#PaMF0Q* literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/searchdata-ns2-ri3-fo3.bin b/documentation/test/js-test-data/searchdata-ns2-ri3-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..c30d3d9aff0aaf8831c4e8bd11f944fedb2694e7 GIT binary patch literal 783 zcmZvZF=!M)6o&uV_N$gjy|O=7Pp7PrNuB|1l- zqR;9hF&c?}OH6mfY*&n*5QhE4&s5L7kl5Z6{cF*_A*Zs@;3V)6cq=U)6LJ#2S5oJr z#Nrdr$sb)ze*9H(bRhcgWMI=Tzz=S5SfV?^)22HwwoizDnG-Uci#@Gv5s68S46I`# zYZ{=2YTQ+Y+Sf(f5c{{p&Aa08o|r!n!@f8kiThisKLdn2W}8KJCAOc6_BmOh&wfs8 zbb7(yl>tkf113@Fj{qH$v?mhQ)kM)8LBC-~01|o-R zBA<+i!4ENBgD56iAbgX^Tj~iik+6$aw1@B=B3~qmqeOB7Fb2(&uE;ep40!0V5F`wzD_H;N%-4Devc>~5XmFJ80<26%HHld{p=;-UlI1TqE=iQZwIeH@6<5K z2aS5r%xNmArK%6+vrM2KZ4Ua^F!Cudw*4abrWY*}jAN@t}r z_t*g6Oj{bi8pL5b^kwyT`Lgwy`?s1Fi}6vk{#$&?qG*J`G)xLdnN7pqWK~Tm=ltDc l8C%5P3>^CDElYs?s2Rnf0pL!awKdX)a8B`V+D}lVJb= literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/searchdata-ns2-ri4-fo3.bin b/documentation/test/js-test-data/searchdata-ns2-ri4-fo3.bin new file mode 100644 index 0000000000000000000000000000000000000000..c53ec70e660254f249ddbc96f8cb90684b12858e GIT binary patch literal 805 zcmZvZziSjh9L3*k?xHzFf`}I+#iAg)7y=Os87xFW40s?H2o{nsx2|_9w{y$wUJ9`| z1jRxu#KI~z7Gfb5R;H0)ZDnO)WhMRrR^oe`5D2)-erD(Uo%j7Uooj2sF#t#SeK$aJ z2Kd0$@a1FTh8VR(KQCsd2=Ew}_>34uqF)xXi(+m?dxbCof9-WlVa7LQ9j%Mi9Wm*N z>3~3!zl>Ok(F4&>#q5cgKNIZ>!l)$sN)gj-S^IBA|6X(-$(ej>ya;&UlWg`gQMY5i zN;UWn_#He)eDTM1Ms8mkeC?6KH4}N4aIjlN!$OwAc?te~w-=N2goTzPcbL zm&w4TEa$4!nlIH|`TDm-w;>jH#om2!Qi$c27(Ntt9*Mh8m0^|v!slknC@*F0Z;S2? z*<`;(*)r<*hQT`n#yHQ+zy|Obcny33*zj+F$J+E7gsXP-QfGbva~)R=;9Z`Ug-cTH zmIqZnRLLjUx3ziZqs&)JAra#&xAO58?0TA1qcM`9D@zGCS2kDnY;_1-{sLzAL&RY+ z@?~`>K-c+xdRSkZYI%e5_J8HK990ETpVMqOo!y;qZPJq!<=%P_rOP^*X_zWxeU%7U ZmCR8bw9IkSZZ0B}_FxcoQ}-r5`3G6SkZ}M2 literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/searchdata-ns2-ri4-fo4.bin b/documentation/test/js-test-data/searchdata-ns2-ri4-fo4.bin new file mode 100644 index 0000000000000000000000000000000000000000..16b08a6db0feff5c7bb83149bafd90c97e4738bb GIT binary patch literal 883 zcmZvaKWG#|6vp4|dC>$F6(ol!t_rdTArb_Uu?jXxaYS-(orK9U?k(KT9=Chf2_hC^ zqc&nAHe#XJh>fIBQfQ?%HezEZg4kHtiQoGY0s(LN=6Cb{?VC5-x!jEoh{#^(L?qH} zi2O1l1`mFwy@yC{GxPZPdPCb^nTv>F!jK4(xV3Ej{h_Ip&W*Pym zM@xN`Nc)P&d2O-OAl?Vc+@wFdO}M+n@By*@h!{U1s^>)flGu1nY`z7InL^e0z0tY* zk91^T2=`6V#7KtKIsDb3Ou+Au*1Ldx2g;#)&@<>0^aJ_>9YxG(jf3K4yL_>8s3p@K zhx-h!@YT?zUU&2Tx)>l{j$l027I{eWP|w9!+HwY4_2Kqx&!=@cl62szN)y)>))uyG zETJDzOQyCAY~D&5gJ_URSGBTimI# liaznCf!C6}af#5Cnv-@kV-A|x=5dKNcV`eh)U|O){{aF(lzspJ literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/searchdata.b85 b/documentation/test/js-test-data/searchdata.b85 deleted file mode 100644 index 1a915d15..00000000 --- a/documentation/test/js-test-data/searchdata.b85 +++ /dev/null @@ -1 +0,0 @@ -O+!-w2LQSO007AX005Q&000310RR921ONaj009U904M+f4gdgd009&L0BHdL0{{R4AOHX<00ATb04M+fDgXd(00A%n0BHaLHUI!^00BGz06GBy0suk)fI0vHNB{tG00B?{0B-;RRsaBW00CS80Am0FVgLYT0RRO600C|Q04V?gasU7*00DRa0B!&QegFVz00D#m0BryPiU0sQ0RaR6kN|)>00EW&0A&CHo&W%600E=`0B!&QssI3C00SBT0BvXh0Cund0CE5Uwg3P+0RaF2!~lRg00GJX0B8UK(f|N-0{{U40{{g800G_r04V?g<^TXF00Ha(0B!&R*Z=@w@&Ev70RRX9009C40A&CH1_1zU009gE0A~OJ5&-~i0RagB7y$rb00ABW0CWHWCIJ9r00OE20AVZv0A&FH2LJ#8JOKb@00BS&0A~OJMgag}00B$^0B`^SQUL&B00CG50CfNXUI74e00CqH03ZMXY5@Sd00D3T0Kx$Q1^{*efFJ+?d;tJu00D#n0A~OJiU9y&00sB}0BvXh0Cq9~0CJE40B~Lb0COw=03bsE07+W_06KpF07;bq064b*08PyR01(>%02uZF0003200|EP002#4bZ7u>VQpn|aA9L*O<{CsE@*UZYybcf2s%1#X>KTKZgealX>N2W03&T_ZU6uPIyzQmV{~tF0Ap-nb8}5$bZB2OUolo?V{~tFE@*UZYyton20A)zX>KSfAY*TCb94YBZE0=*0025VQekdqWdLJrVRLg$VRUF;F<&uKVQyz-E@*UZYyKSfAY*TCb94YBZE0>$VP|CkaA9X>a=%FQuq=0K|Md$_$(F*j@8f54$v``ZgQ8KmE z)rPM2$km>>+P16hxLT22SKBiRJ%wqf&?yS;V>-Z}FD+US#c7c5!9 zJ-@o=H~0LW>ja-o=Z7b>%nFqIltmXERqi$?QfY>Y%ulD4Cpjle666~!*u0oBa>>c7 z&RqA|TVjA3qKR&cF}f#4=)MTiL$Qwr;y^01sV%ELc8zV<*vU0YzYgEbUXfpTU(kQ2z+Wzd+?DwvL!NX1}u@XKm8Bmy8B+E6HCM+F7p)bJJ1O>!j6A znk|HO)Hq{LBco_7X=VK(t!_LT<;42p`r@SKY(S+vVQXQlpN_J>WFt;Dl7B%jIag%< zKio=e#J~=pDOgzuk Gr>)=hi;v_0 diff --git a/documentation/test/js-test-data/short.bin b/documentation/test/js-test-data/short.bin index ce004a84..3bde6d3c 100644 --- a/documentation/test/js-test-data/short.bin +++ b/documentation/test/js-test-data/short.bin @@ -1 +1 @@ -############# \ No newline at end of file +############################## \ No newline at end of file diff --git a/documentation/test/js-test-data/unicode.bin b/documentation/test/js-test-data/unicode.bin index 132cec998a3484675fc17a0353b3b7f784e3dbca..d72ae17f51a1c12e86d2e9a86c34e5fa5e5e506c 100644 GIT binary patch delta 135 zcmZ3$xRkNp*EyJp0SG`u8W6Vvu@4Y40x<*QY!(oCgabsT@PWvEA|Udp6p#R^VO*#N z;vd!mkwpeTl4KoA6lC-4fgLhu+AyqCWlzVbWgky{Sy z#U_<4&c&)oAuX=b<|AEp(&r^ZzWIML<}MT7GUcQi@tiev-qa=g4!uE9HkV`l17m0o Avj6}9 diff --git a/documentation/test/js-test-data/wrong-magic.bin b/documentation/test/js-test-data/wrong-magic.bin index 6a3dd03eb7cd398f2b0b43a2b7234fd00cff1f77..3e3670235969810fa1e52e6dd3cd52d51bb9d834 100644 GIT binary patch literal 31 NcmebE4`yP(4FDWd0P+9; literal 26 NcmebE4`x)r3II1E1F--A diff --git a/documentation/test/js-test-data/wrong-result-id-bytes.bin b/documentation/test/js-test-data/wrong-result-id-bytes.bin new file mode 100644 index 0000000000000000000000000000000000000000..3e99537d09ae8ec6a5819640f1b7d56febf51a37 GIT binary patch literal 31 OcmeZu4rXFwzzF~wjR5Qb literal 0 HcmV?d00001 diff --git a/documentation/test/js-test-data/wrong-version.bin b/documentation/test/js-test-data/wrong-version.bin index 9b66517fd264a88dd8c3adcc63b62610134239ee..f555f700e8fbf8b8c5aa78f0a619c7126f5080df 100644 GIT binary patch literal 31 NcmeZu4rXM)4FDR?0ObGx literal 26 NcmeZu4rWlm3IH|V1Ec@| diff --git a/documentation/test/populate-js-test-data.py b/documentation/test/populate-js-test-data.py index 81d9fa9c..b17e0233 100755 --- a/documentation/test/populate-js-test-data.py +++ b/documentation/test/populate-js-test-data.py @@ -31,23 +31,37 @@ import pathlib sys.path.append(os.path.join(os.path.dirname(os.path.realpath(__file__)))) sys.path.append(os.path.join(os.path.dirname(os.path.realpath(__file__)), '..')) -from _search_test_metadata import EntryType, search_type_map -from _search import Trie, ResultMap, ResultFlag, serialize_search_data, search_data_header_struct +from _search_test_metadata import EntryType, search_type_map, type_sizes +from _search import Trie, ResultMap, ResultFlag, serialize_search_data, Serializer basedir = pathlib.Path(os.path.dirname(os.path.realpath(__file__)))/'js-test-data' +def type_size_suffix(*, name_size_bytes, result_id_bytes, file_offset_bytes): + return f'ns{name_size_bytes}-ri{result_id_bytes}-fo{file_offset_bytes}' + # Basic error handling +min_size = len(serialize_search_data(Serializer(name_size_bytes=1, result_id_bytes=2, file_offset_bytes=3), Trie(), ResultMap(), [], 0)) + with open(basedir/'short.bin', 'wb') as f: - f.write(b'#'*(search_data_header_struct.size - 1)) + f.write(b'#'*(min_size - 1)) with open(basedir/'wrong-magic.bin', 'wb') as f: - f.write(b'MOS\1 ') + f.write(b'MOS\2') + f.write(b'\0'*(min_size - 4)) with open(basedir/'wrong-version.bin', 'wb') as f: - f.write(b'MCS\0 ') -with open(basedir/'empty.bin', 'wb') as f: - f.write(serialize_search_data(Trie(), ResultMap(), [], 0)) + f.write(b'MCS\1') + f.write(b'\0'*(min_size - 4)) +with open(basedir/'wrong-result-id-bytes.bin', 'wb') as f: + f.write(Serializer.header_struct.pack(b'MCS', 2, 3 << 1, 0, 0, 0)) + f.write(b'\0'*(min_size - Serializer.header_struct.size)) + +# Empty file, in all possible type size combinations -# General test +for i in type_sizes: + with open(basedir/'empty-{}.bin'.format(type_size_suffix(**i)), 'wb') as f: + f.write(serialize_search_data(Serializer(**i), Trie(), ResultMap(), [], 0)) + +# General test, in all possible type size combinations trie = Trie() map = ResultMap() @@ -78,12 +92,16 @@ trie.insert("subpage", index) trie.insert("rectangle", map.add("Rectangle", "", alias=range_index)) trie.insert("rect", map.add("Rectangle::Rect()", "", suffix_length=2, alias=range_index)) -with open(basedir/'searchdata.bin', 'wb') as f: - f.write(serialize_search_data(trie, map, search_type_map, 7)) -with open(basedir/'searchdata.b85', 'wb') as f: - f.write(base64.b85encode(serialize_search_data(trie, map, search_type_map, 7), True)) +for i in type_sizes: + with open(basedir/'searchdata-{}.bin'.format(type_size_suffix(**i)), 'wb') as f: + f.write(serialize_search_data(Serializer(**i), trie, map, search_type_map, 7)) + +# The Base-85 file however doesn't need to have all type size variants as it's +# just used to verify it decodes to the right binary variant +with open(basedir/'searchdata-{}.b85'.format(type_size_suffix(**type_sizes[0])), 'wb') as f: + f.write(base64.b85encode(serialize_search_data(Serializer(**type_sizes[0]), trie, map, search_type_map, 7), True)) -# UTF-8 names +# UTF-8 names, nothing size-dependent here so just one variant trie = Trie() map = ResultMap() @@ -92,9 +110,9 @@ trie.insert("hýždě", map.add("Hýždě", "#a", flags=ResultFlag.from_type(Res trie.insert("hárá", map.add("Hárá", "#b", flags=ResultFlag.from_type(ResultFlag.NONE, EntryType.PAGE))) with open(basedir/'unicode.bin', 'wb') as f: - f.write(serialize_search_data(trie, map, search_type_map, 2)) + f.write(serialize_search_data(Serializer(**type_sizes[0]), trie, map, search_type_map, 2)) -# Heavy prefix nesting +# Heavy prefix nesting, nothing size-dependent here so just one variant trie = Trie() map = ResultMap() @@ -105,9 +123,10 @@ trie.insert("geometry", map.add("Magnum::Math::Geometry", "namespaceMagnum_1_1Ma trie.insert("range", map.add("Magnum::Math::Range", "classMagnum_1_1Math_1_1Range.html", flags=ResultFlag.from_type(ResultFlag.NONE, EntryType.CLASS))) with open(basedir/'nested.bin', 'wb') as f: - f.write(serialize_search_data(trie, map, search_type_map, 4)) + f.write(serialize_search_data(Serializer(**type_sizes[0]), trie, map, search_type_map, 4)) -# Extreme amount of search results (Python's __init__, usually) +# Extreme amount of search results (Python's __init__, usually), in all +# possible type size combinations trie = Trie() map = ResultMap() @@ -120,5 +139,6 @@ for i in range(128): for i in [3, 15, 67]: trie.insert("__init__subclass__", map.add(f"Foo{i}.__init__subclass__(self)", f"Foo{i}.html#__init__subclass__", suffix_length=6, flags=ResultFlag.from_type(ResultFlag.NONE, EntryType.FUNC))) -with open(basedir/'manyresults.bin', 'wb') as f: - f.write(serialize_search_data(trie, map, search_type_map, 128 + 3)) +for i in type_sizes: + with open(basedir/'manyresults-{}.bin'.format(type_size_suffix(**i)), 'wb') as f: + f.write(serialize_search_data(Serializer(**i), trie, map, search_type_map, 128 + 3)) diff --git a/documentation/test/test-search.js b/documentation/test/test-search.js index 63827868..269d8cc8 100644 --- a/documentation/test/test-search.js +++ b/documentation/test/test-search.js @@ -76,11 +76,28 @@ const { StringDecoder } = require('string_decoder'); assert.deepEqual(Buffer.from(buf), Buffer.from([0, 0, 0, 0])); } -/* Verify that base85-decoded file is equivalent to the binary */ +let type_size_suffixes = [ + 'ns1-ri2-fo3', + 'ns1-ri2-fo4', + 'ns1-ri3-fo3', + 'ns1-ri3-fo4', + 'ns1-ri4-fo3', + 'ns1-ri4-fo4', + + 'ns2-ri2-fo3', + 'ns2-ri2-fo4', + 'ns2-ri3-fo3', + 'ns2-ri3-fo4', + 'ns2-ri4-fo3', + 'ns2-ri4-fo4', +] + +/* Verify that base85-decoded file is equivalent to the binary. Nothing + type-size-dependent in the decoder, so test just on the first variant. */ { - let binary = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata.bin")); - assert.equal(binary.byteLength, 745); - let b85 = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata.b85"), {encoding: 'utf-8'}); + let binary = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata-" + type_size_suffixes[0] + ".bin")); + assert.equal(binary.byteLength, 750); + let b85 = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata-" + type_size_suffixes[0] + ".b85"), {encoding: 'utf-8'}); assert.deepEqual(new DataView(binary.buffer.slice(binary.byteOffset, binary.byteOffset + binary.byteLength)), new DataView(Search.base85decode(b85), 0, binary.byteLength)); } @@ -102,21 +119,48 @@ const { StringDecoder } = require('string_decoder'); assert.ok(!Search.init(buffer.buffer.slice(buffer.byteOffset, buffer.byteOffset + buffer.byteLength))); } -/* Search with empty data */ +/* Opening file with wrong result id byte count */ { - let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/empty.bin")); + let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/wrong-result-id-bytes.bin")); + assert.ok(!Search.init(buffer.buffer.slice(buffer.byteOffset, buffer.byteOffset + buffer.byteLength))); +} + +/* Search with empty data, in all type size variants */ +for(let i = 0; i != type_size_suffixes.length; ++i) { + let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/empty-" + type_size_suffixes[i] + ".bin")); assert.ok(Search.init(buffer.buffer.slice(buffer.byteOffset, buffer.byteOffset + buffer.byteLength))); - assert.equal(Search.dataSize, 26); + + /* Test just the smallest and largest size, everything else should be in + between */ + if(i == 0) + assert.equal(Search.dataSize, 31); + else if(i == type_size_suffixes.length - 1) + assert.equal(Search.dataSize, 32); + else { + assert.ok(Search.dataSize >= 31 && Search.dataSize <= 32); + } + assert.equal(Search.symbolCount, "0 symbols (0 kB)"); assert.deepEqual(Search.search(''), [[], '']); } -/* Search */ -{ - let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata.bin")); +/* Search, in all type size variants */ +for(let i = 0; i != type_size_suffixes.length; ++i) { + let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata-" + type_size_suffixes[i] + ".bin")); assert.ok(Search.init(buffer.buffer.slice(buffer.byteOffset, buffer.byteOffset + buffer.byteLength))); - assert.equal(Search.dataSize, 745); - assert.equal(Search.symbolCount, "7 symbols (0.7 kB)"); + + /* Test just the smallest and largest size, everything else should be in + between */ + if(i == 0) { + assert.equal(Search.dataSize, 750); + assert.equal(Search.symbolCount, "7 symbols (0.7 kB)"); + } else if(i == type_size_suffixes.length - 1) { + assert.equal(Search.dataSize, 883); + assert.equal(Search.symbolCount, "7 symbols (0.9 kB)"); + } else { + assert.ok(Search.dataSize > 750 && Search.dataSize < 883); + } + assert.equal(Search.maxResults, 100); /* Blow up */ @@ -217,11 +261,12 @@ const { StringDecoder } = require('string_decoder'); suffixLength: 8 }], '']); } -/* Search with spaces */ +/* Search with spaces. Nothing type-size-dependent here, so test just on the + first variant. */ { - let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata.bin")); + let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata-" + type_size_suffixes[0] + ".bin")); assert.ok(Search.init(buffer.buffer.slice(buffer.byteOffset, buffer.byteOffset + buffer.byteLength))); - assert.equal(Search.dataSize, 745); + assert.equal(Search.dataSize, 750); assert.equal(Search.symbolCount, "7 symbols (0.7 kB)"); assert.equal(Search.maxResults, 100); @@ -269,11 +314,12 @@ const { StringDecoder } = require('string_decoder'); suffixLength: 10 }], Search.toUtf8('» subpage')]); } -/* Search, limiting the results to 3 */ +/* Search, limiting the results to 3. Nothing type-size-dependent here, so test + just on the first variant. */ { - let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata.bin")); + let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata-" + type_size_suffixes[0] + ".bin")); assert.ok(Search.init(buffer.buffer.slice(buffer.byteOffset, buffer.byteOffset + buffer.byteLength), 3)); - assert.equal(Search.dataSize, 745); + assert.equal(Search.dataSize, 750); assert.equal(Search.symbolCount, "7 symbols (0.7 kB)"); assert.equal(Search.maxResults, 3); assert.deepEqual(Search.search('m'), [[ @@ -297,11 +343,12 @@ const { StringDecoder } = require('string_decoder'); suffixLength: 10 }], '']); } -/* Search loaded from a base85-encoded file should work properly */ +/* Search loaded from a base85-encoded file should work properly. Nothing + type-size-dependent here, so test just on the first variant. */ { - let b85 = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata.b85"), {encoding: 'utf-8'}); + let b85 = fs.readFileSync(path.join(__dirname, "js-test-data/searchdata-" + type_size_suffixes[0] + ".b85"), {encoding: 'utf-8'}); assert.ok(Search.load(b85)); - assert.equal(Search.dataSize, 748); /* some padding on the end, that's okay */ + assert.equal(Search.dataSize, 752); /* some padding on the end, that's okay */ assert.equal(Search.symbolCount, "7 symbols (0.7 kB)"); assert.equal(Search.maxResults, 100); assert.deepEqual(Search.search('min'), [[ @@ -325,11 +372,11 @@ const { StringDecoder } = require('string_decoder'); suffixLength: 8 }], '()']); } -/* Search, Unicode */ +/* Search, Unicode. Nothing type-size-dependent here. */ { let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/unicode.bin")); assert.ok(Search.init(buffer.buffer.slice(buffer.byteOffset, buffer.byteOffset + buffer.byteLength))); - assert.equal(Search.dataSize, 160); + assert.equal(Search.dataSize, 165); assert.equal(Search.symbolCount, "2 symbols (0.2 kB)"); /* Both "Hýždě" and "Hárá" have common autocompletion to "h\xA1", which is not valid UTF-8, so it has to get truncated */ @@ -363,11 +410,11 @@ const { StringDecoder } = require('string_decoder'); suffixLength: 3 }], Search.toUtf8('rá')]); } -/* Properly combine heavily nested URLs */ +/* Properly combine heavily nested URLs. Nothing type-size-dependent here. */ { let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/nested.bin")); assert.ok(Search.init(buffer.buffer.slice(buffer.byteOffset, buffer.byteOffset + buffer.byteLength))); - assert.equal(Search.dataSize, 331); + assert.equal(Search.dataSize, 336); assert.equal(Search.symbolCount, "4 symbols (0.3 kB)"); assert.deepEqual(Search.search('geo'), [[ { name: 'Magnum::Math::Geometry', @@ -386,12 +433,24 @@ const { StringDecoder } = require('string_decoder'); suffixLength: 3 }], 'nge']); } -/* Extreme amount of search results */ -{ - let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/manyresults.bin")); +/* Extreme amount of search results, in all type size variants to ensure no + size assumptions were left there */ +for(let i = 0; i != type_size_suffixes.length; ++i) { + let buffer = fs.readFileSync(path.join(__dirname, "js-test-data/manyresults-" + type_size_suffixes[i] + ".bin")); assert.ok(Search.init(buffer.buffer.slice(buffer.byteOffset, buffer.byteOffset + buffer.byteLength), 10000)); - assert.equal(Search.dataSize, 6415); - assert.equal(Search.symbolCount, "131 symbols (6.3 kB)"); + + /* Test just the smallest and largest size, everything else should be in + between */ + if(i == 0) { + assert.equal(Search.dataSize, 6421); + assert.equal(Search.symbolCount, "131 symbols (6.3 kB)"); + } else if(i == type_size_suffixes.length - 1) { + assert.equal(Search.dataSize, 6964); + assert.equal(Search.symbolCount, "131 symbols (6.8 kB)"); + } else { + assert.ok(Search.dataSize > 6421 && Search.dataSize < 6964); + } + assert.equal(Search.maxResults, 10000); assert.deepEqual(Search.search('__init__')[0].length, 128 + 3); assert.deepEqual(Search.search('__init__')[1], ''); diff --git a/documentation/test/test_search.py b/documentation/test/test_search.py index c716589a..2e8c8e01 100755 --- a/documentation/test/test_search.py +++ b/documentation/test/test_search.py @@ -27,8 +27,8 @@ import sys import unittest from types import SimpleNamespace as Empty -from ._search_test_metadata import EntryType, search_type_map -from _search import Trie, ResultMap, ResultFlag, serialize_search_data, pretty_print_trie, pretty_print_map, pretty_print +from ._search_test_metadata import EntryType, search_type_map, trie_type_sizes, type_sizes +from _search import Trie, ResultMap, ResultFlag, Serializer, Deserializer, serialize_search_data, pretty_print_trie, pretty_print_map, pretty_print from test_doxygen import IntegrationTestCase @@ -37,28 +37,40 @@ class TrieSerialization(unittest.TestCase): super().__init__(*args, **kwargs) self.maxDiff = None - def compare(self, serialized: bytes, expected: str): - pretty = pretty_print_trie(serialized)[0] + def compare(self, deserializer: Deserializer, serialized: bytes, expected: str): + pretty = pretty_print_trie(deserializer, serialized)[0] #print(pretty) self.assertEqual(pretty, expected.strip()) def test_empty(self): trie = Trie() - serialized = trie.serialize() - self.compare(serialized, "") - self.assertEqual(len(serialized), 6) + for i in trie_type_sizes: + with self.subTest(**i): + serialized = trie.serialize(Serializer(**i)) + self.compare(Deserializer(**i), serialized, "") + self.assertEqual(len(serialized), 6) def test_single(self): trie = Trie() trie.insert("magnum", 1337) trie.insert("magnum", 21) - serialized = trie.serialize() - self.compare(serialized, """ + for i in trie_type_sizes: + with self.subTest(**i): + serialized = trie.serialize(Serializer(**i)) + self.compare(Deserializer(**i), serialized, """ magnum [1337, 21] """) - self.assertEqual(len(serialized), 46) + # Verify just the smallest and largest size, everything else + # should fit in between + if i['file_offset_bytes'] == 3 and i['result_id_bytes'] == 2: + self.assertEqual(len(serialized), 46) + elif i['file_offset_bytes'] == 4 and i['result_id_bytes'] == 4: + self.assertEqual(len(serialized), 56) + else: + self.assertGreater(len(serialized), 46) + self.assertLess(len(serialized), 56) def test_multiple(self): trie = Trie() @@ -94,8 +106,10 @@ magnum [1337, 21] trie.insert("range::max", 10) trie.insert("max", 10) - serialized = trie.serialize() - self.compare(serialized, """ + for i in trie_type_sizes: + with self.subTest(**i): + serialized = trie.serialize(Serializer(**i)) + self.compare(Deserializer(**i), serialized, """ math [0] ||| :$ ||| :vector [1] @@ -123,7 +137,15 @@ range [2] | :min [9] | ax [10] """) - self.assertEqual(len(serialized), 340) + # Verify just the smallest and largest size, everything else + # should fit in between + if i['file_offset_bytes'] == 3 and i['result_id_bytes'] == 2: + self.assertEqual(len(serialized), 340) + elif i['file_offset_bytes'] == 4 and i['result_id_bytes'] == 4: + self.assertEqual(len(serialized), 428) + else: + self.assertGreater(len(serialized), 340) + self.assertLess(len(serialized), 428) def test_unicode(self): trie = Trie() @@ -131,8 +153,8 @@ range [2] trie.insert("hýždě", 0) trie.insert("hárá", 1) - serialized = trie.serialize() - self.compare(serialized, """ + serialized = trie.serialize(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=1)) + self.compare(Deserializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=1), serialized, """ h0xc3 0xbd 0xc5 @@ -147,7 +169,7 @@ h0xc3 """) self.assertEqual(len(serialized), 82) - def test_many_results(self): + def test_16bit_result_count(self): trie = Trie() for i in range(128): @@ -158,39 +180,99 @@ h0xc3 for i in [203, 215, 267]: trie.insert("__init__subclass__", i) - serialized = trie.serialize() - self.compare(serialized, """ + for i in trie_type_sizes: + with self.subTest(**i): + serialized = trie.serialize(Serializer(**i)) + self.compare(Deserializer(**i), serialized, """ __init__ [{}] subclass__ [203, 215, 267] """.format(', '.join([str(i) for i in range(128)]))) - self.assertEqual(len(serialized), 376) + # Verify just the smallest and largest size, everything else + # should fit in between + if i['file_offset_bytes'] == 3 and i['result_id_bytes'] == 2: + self.assertEqual(len(serialized), 377) + elif i['file_offset_bytes'] == 4 and i['result_id_bytes'] == 4: + self.assertEqual(len(serialized), 657) + else: + self.assertGreater(len(serialized), 377) + self.assertLess(len(serialized), 657) + + def test_16bit_result_id_too_small(self): + trie = Trie() + trie.insert("a", 65536) + with self.assertRaises(OverflowError): + trie.serialize(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=1)) + + # This should work + trie.serialize(Serializer(file_offset_bytes=3, result_id_bytes=3, name_size_bytes=1)) + + def test_24bit_result_id_too_small(self): + trie = Trie() + trie.insert("a", 16*1024*1024) + with self.assertRaises(OverflowError): + trie.serialize(Serializer(file_offset_bytes=3, result_id_bytes=3, name_size_bytes=1)) + + # This should work + trie.serialize(Serializer(file_offset_bytes=3, result_id_bytes=4, name_size_bytes=1)) + + def test_23bit_file_offset_too_small(self): + trie = Trie() + + # The hight bit of the child offset stores a lookahead barrier, so the + # file has to be smaller than 8M, not 16. Python has a recursion limit + # of 1000, so we can't really insert a 8M character long string. + # Instead, insert one 130-character string where each char has 32k + # 16bit result IDs. 129 isn't enough to overflow the offsets. + results_32k = [j for j in range(32767)] + for i in range(130): + trie.insert('a'*i, results_32k) + + with self.assertRaises(OverflowError): + trie.serialize(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=1)) + + # This should work + trie.serialize(Serializer(file_offset_bytes=4, result_id_bytes=2, name_size_bytes=1)) class MapSerialization(unittest.TestCase): def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) self.maxDiff = None - def compare(self, serialized: bytes, expected: str): - pretty = pretty_print_map(serialized, entryTypeClass=EntryType) + def compare(self, deserializer: Deserializer, serialized: bytes, expected: str): + pretty = pretty_print_map(deserializer, serialized, entryTypeClass=EntryType) #print(pretty) self.assertEqual(pretty, expected.strip()) def test_empty(self): map = ResultMap() - serialized = map.serialize() - self.compare(serialized, "") - self.assertEqual(len(serialized), 4) + for i in type_sizes: + with self.subTest(**i): + serialized = map.serialize(Serializer(**i)) + self.compare(Deserializer(**i), serialized, "") + self.assertEqual(len(serialized), i['file_offset_bytes']) def test_single(self): map = ResultMap() + self.assertEqual(map.add("Magnum", "namespaceMagnum.html", suffix_length=11, flags=ResultFlag.from_type(ResultFlag.NONE, EntryType.NAMESPACE)), 0) - serialized = map.serialize() - self.compare(serialized, """ + for i in type_sizes: + with self.subTest(**i): + serialized = map.serialize(Serializer(**i)) + self.compare(Deserializer(**i), serialized, """ 0: Magnum [suffix_length=11, type=NAMESPACE] -> namespaceMagnum.html """) - self.assertEqual(len(serialized), 36) + # Verify just the smallest and largest size, everything else + # should fit in between. The `result_id_bytes` don't affect + # this case. + if i['file_offset_bytes'] == 3 and i['name_size_bytes'] == 1: + self.assertEqual(len(serialized), 35) + elif i['file_offset_bytes'] == 4 and i['name_size_bytes'] == 2: + self.assertEqual(len(serialized), 38) + else: + self.assertGreater(len(serialized), 35) + self.assertLess(len(serialized), 38) def test_multiple(self): map = ResultMap() @@ -203,8 +285,10 @@ class MapSerialization(unittest.TestCase): self.assertEqual(map.add("Rectangle", "", alias=2), 5) self.assertEqual(map.add("Rectangle::Rect()", "", suffix_length=2, alias=2), 6) - serialized = map.serialize() - self.compare(serialized, """ + for i in type_sizes: + with self.subTest(**i): + serialized = map.serialize(Serializer(**i)) + self.compare(Deserializer(**i), serialized, """ 0: Math [type=NAMESPACE] -> namespaceMath.html 1: ::Vector [prefix=0[:0], type=CLASS] -> classMath_1_1Vector.html 2: ::Range [prefix=0[:0], type=CLASS] -> classMath_1_1Range.html @@ -213,7 +297,97 @@ class MapSerialization(unittest.TestCase): 5: Rectangle [alias=2] -> 6: ::Rect() [alias=2, prefix=5[:0], suffix_length=2] -> """) - self.assertEqual(len(serialized), 203) + # Verify just the smallest and largest size, everything else + # should fit in between + if i['file_offset_bytes'] == 3 and i['result_id_bytes'] == 2 and i['name_size_bytes'] == 1: + self.assertEqual(len(serialized), 202) + elif i['file_offset_bytes'] == 4 and i['result_id_bytes'] == 4 and i['name_size_bytes'] == 2: + self.assertEqual(len(serialized), 231) + else: + self.assertGreater(len(serialized), 202) + self.assertLess(len(serialized), 231) + + def test_24bit_file_offset_too_small(self): + map = ResultMap() + # 3 bytes for the initial offset, 3 bytes for file size, 1 byte for the + # flags, 1 byte for the null terminator, 6 bytes for the URL + map.add('F'*(16*1024*1024 - 14), 'f.html', flags=ResultFlag.from_type(ResultFlag.NONE, EntryType.CLASS)) + + with self.assertRaises(OverflowError): + # Disabling prefix merging otherwise memory usage goes to hell + map.serialize(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=1), merge_prefixes=False) + + # This should work. Disabling prefix merging otherwise memory usage + # goes to hell. + map.serialize(Serializer(file_offset_bytes=4, result_id_bytes=2, name_size_bytes=1), merge_prefixes=False) + + def test_8bit_suffix_length_too_small(self): + map = ResultMap() + map.add("F()" + ';'*256, "f.html", flags=ResultFlag.from_type(ResultFlag.NONE, EntryType.FUNC), suffix_length=256) + + with self.assertRaises(OverflowError): + map.serialize(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=1)) + + # This should work + map.serialize(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=2)) + + def test_8bit_prefix_length_too_small(self): + map = ResultMap() + map.add("A", 'a'*251 + ".html", flags=ResultFlag.from_type(ResultFlag.NONE, EntryType.CLASS)) + map.add("A::foo()", 'a'*251 + ".html#foo", flags=ResultFlag.from_type(ResultFlag.NONE, EntryType.FUNC)) + + with self.assertRaises(OverflowError): + map.serialize(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=1)) + + # This should work + map.serialize(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=2)) + + def test_16bit_prefix_id_too_small(self): + map = ResultMap() + + # Adding A0 to A65535 would be too slow due to the recursive Trie + # population during prefix merging (SIGH) so trying this instead. It's + # still hella slow, but at least not TWO MINUTES. + for i in range(128): + for j in range(128): + for k in range(4): + map.add(bytes([i, j, k]).decode('utf-8'), "a.html", flags=ResultFlag.from_type(ResultFlag.NONE, EntryType.CLASS)) + + self.assertEqual(map.add("B", "b.html", flags=ResultFlag.from_type(ResultFlag.NONE, EntryType.CLASS)), 65536) + map.add("B::foo()", "b.html#foo", flags=ResultFlag.from_type(ResultFlag.NONE, EntryType.FUNC)) + + with self.assertRaises(OverflowError): + map.serialize(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=1)) + + # This should work + map.serialize(Serializer(file_offset_bytes=3, result_id_bytes=3, name_size_bytes=1)) + + # Testing this error for a 24bit prefix seems infeasibly slow, not + # doing that + + def test_16bit_alias_id_too_small(self): + map = ResultMap() + + # The alias doesn't exist of course, hopefully that's fine in this case + map.add("B", "", alias=65536) + + with self.assertRaises(OverflowError): + map.serialize(Serializer(file_offset_bytes=3, result_id_bytes=2, name_size_bytes=1)) + + # This should work + map.serialize(Serializer(file_offset_bytes=3, result_id_bytes=3, name_size_bytes=1)) + + def test_24bit_alias_id_too_small(self): + map = ResultMap() + + # The alias doesn't exist of course, hopefully that's fine in this case + map.add("B", "", alias=16*1024*1024) + + with self.assertRaises(OverflowError): + map.serialize(Serializer(file_offset_bytes=3, result_id_bytes=3, name_size_bytes=1)) + + # This should work + map.serialize(Serializer(file_offset_bytes=3, result_id_bytes=4, name_size_bytes=1)) class Serialization(unittest.TestCase): def __init__(self, *args, **kwargs): @@ -237,8 +411,10 @@ class Serialization(unittest.TestCase): trie.insert("math::range", index) trie.insert("range", index) - serialized = serialize_search_data(trie, map, search_type_map, 3) - self.compare(serialized, """ + for i in type_sizes: + with self.subTest(**i): + serialized = serialize_search_data(Serializer(**i), trie, map, search_type_map, 3) + self.compare(serialized, """ 3 symbols math [0] | ::vector [1] @@ -253,4 +429,12 @@ range [2] (EntryType.CLASS, CssClass.PRIMARY, 'class'), (EntryType.FUNC, CssClass.INFO, 'func') """) - self.assertEqual(len(serialized), 277) + # Verify just the smallest and largest size, everything else + # should fit in between + if i['file_offset_bytes'] == 3 and i['result_id_bytes'] == 2 and i['name_size_bytes'] == 1: + self.assertEqual(len(serialized), 282) + elif i['file_offset_bytes'] == 4 and i['result_id_bytes'] == 4 and i['name_size_bytes'] == 2: + self.assertEqual(len(serialized), 317) + else: + self.assertGreater(len(serialized), 282) + self.assertLess(len(serialized), 317) diff --git a/documentation/test_doxygen/layout/pages.html b/documentation/test_doxygen/layout/pages.html index 943167cf..13d27fb1 100644 --- a/documentation/test_doxygen/layout/pages.html +++ b/documentation/test_doxygen/layout/pages.html @@ -111,8 +111,8 @@ - - + +