From efe5986ddc767ce0484e1749b61da1927c5c34b9 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Vladim=C3=ADr=20Vondru=C5=A1?= Date: Sun, 4 Feb 2018 21:14:52 +0100 Subject: [PATCH] doxygen: add functions twice to the search data. With the breadth-first traversal for search result gathering we need to handle two things: 1. Show a function named min() among other three-letter names (such as BlendEquation::Min), so in fact have it just as "min" in the trie. 2. But make it still possible to search for min() with the parentheses after in order to filter out non-function results, so in fact have it *also* as "min()" in the trie. This required that the result prefix merging was updated to allow self-referencing (an item being a complete alias of another item). That's now allowed only if the suffix length differ and is allowed only from one side to avoid a cycle. Suffix length differs, because one result has the () suffix while the other hasn't. In order to prevent the function from appearing twice in the results, a lookahead barrier is added to the ( character. That was nicely simple. --- doxygen/dox2html5.py | 53 ++++++++++++---- doxygen/test/test_search.py | 122 +++++++++++++++++++++--------------- 2 files changed, 113 insertions(+), 62 deletions(-) diff --git a/doxygen/dox2html5.py b/doxygen/dox2html5.py index ef97cfef..9d3c2ac1 100755 --- a/doxygen/dox2html5.py +++ b/doxygen/dox2html5.py @@ -210,35 +210,50 @@ class ResultMap: # Create a new list with merged prefixes merged = [] - for e in self.entries: + for index, e in enumerate(self.entries): # Search in the trie and get the longest shared name prefix # that is already fully contained in some other entry current = trie longest_prefix = None for c in e.name.encode('utf-8'): - # If current node has results, save it as the longest prefix - if current.results: - # well, the prefix would have 0 bytes - assert current is not trie - longest_prefix = current - for candidate, child in current.children.items(): if c == candidate: current = child[1] break else: assert False + # Allow self-reference only when referenced result suffix + # is longer (otherwise cycles happen). This is for + # functions that should appear when searching for foo (so + # they get ordered properly based on the name lenght) and + # also when searching for foo() (so everything that's not + # a function gets filtered out). Such entries are + # completely the same except for a different suffix length. + if index in current.results: + for i in current.results: + if self.entries[i].suffix_length > self.entries[index].suffix_length: + longest_prefix = current + break + elif current.results: + longest_prefix = current + # Name prefix found, for all possible URLs find the one that # shares the longest prefix if longest_prefix: max_prefix = (0, -1) - for index in longest_prefix.results: + for longest_index in longest_prefix.results: + # Ignore self (function self-reference, see above) + if longest_index == index: continue + prefix_length = 0 - for i in range(min(len(e.url), len(self.entries[index].url))): - if e.url[i] != self.entries[index].url[i]: break + for i in range(min(len(e.url), len(self.entries[longest_index].url))): + if e.url[i] != self.entries[longest_index].url[i]: break prefix_length += 1 if max_prefix[1] < prefix_length: - max_prefix = (index, prefix_length) + max_prefix = (longest_index, prefix_length) + + # Expect we found something + assert max_prefix[1] != -1 # Save the entry with reference to the prefix entry = Empty() @@ -1720,14 +1735,14 @@ def build_search_data(state: State, merge_subtrees=True, add_lookahead_barriers= return strip_tags_re.sub('', text) for result in state.search: + # Handle function arguments name_with_args = result.name name = result.name suffix_length = 0 if hasattr(result, 'params') and result.params is not None: params = strip_tags(', '.join(result.params)) name_with_args += '(' + params + ')' - name += '()' - suffix_length += len(html.unescape(params)) + suffix_length += len(html.unescape(params)) + 2 if hasattr(result, 'suffix') and result.suffix: name_with_args += result.suffix # TODO: escape elsewhere so i don't have to unescape here @@ -1736,6 +1751,13 @@ def build_search_data(state: State, merge_subtrees=True, add_lookahead_barriers= # TODO: escape elsewhere so i don't have to unescape here index = map.add(html.unescape('::'.join(result.prefix + [name_with_args])), result.url, suffix_length=suffix_length, flags=result.flags) + # Add functions and function macros the second time with () appended, + # everything is the same except for suffix length which is 2 chars + # shorter + if hasattr(result, 'params') and result.params is not None: + index_args = map.add(html.unescape('::'.join(result.prefix + [name_with_args])), result.url, + suffix_length=suffix_length - 2, flags=result.flags) + prefixed_name = result.prefix + [name] for i in range(len(prefixed_name)): lookahead_barriers = [] @@ -1747,6 +1769,11 @@ def build_search_data(state: State, merge_subtrees=True, add_lookahead_barriers= name += html.unescape(j) trie.insert(name.lower(), index, lookahead_barriers=lookahead_barriers if add_lookahead_barriers else []) + # Add functions and function macros the second time with () + # appended, referencing the other result that expects () appended + if hasattr(result, 'params') and result.params is not None: + trie.insert(name.lower() + '()', index_args, lookahead_barriers=lookahead_barriers + [len(name)] if add_lookahead_barriers else []) + return serialize_search_data(trie, map, merge_subtrees=merge_subtrees, merge_prefixes=merge_prefixes) def base85encode_search_data(data: bytearray) -> bytearray: diff --git a/doxygen/test/test_search.py b/doxygen/test/test_search.py index 369376e4..36416610 100755 --- a/doxygen/test/test_search.py +++ b/doxygen/test/test_search.py @@ -372,66 +372,82 @@ deprecated list [0] || | /$ || | deprecatedfile.h [2] || file.h [2] -|| |oo() [31] +|| |oo [38] +|| || ($ +|| || ) [39] || namespace [7] || | :$ || | :deprecatedclass [8] || | | struct [9] || | | union [10] -|| | | enum [26] +|| | | enum [33] || | | | :$ -|| | | | :value [25] -|| | | typedef [29] -|| | | variable [30] -|| | | foo() [31] -|| | enum [28] +|| | | | :value [32] +|| | | typedef [36] +|| | | variable [37] +|| | | foo [38] +|| | | | ($ +|| | | | ) [39] +|| | enum [35] || | | :$ -|| | | :deprecatedvalue [27] +|| | | :deprecatedvalue [34] || class [8] || struct [9] || union [10] -|| _macro() [17] -|| enum [26] +|| _macro [17] +|| | ($ +|| | ) [18] +|| enum [33] || | :$ -|| | :value [25] -|| value [27] -|| | riable [30] -|| typedef [29] +|| | :value [32] +|| value [34] +|| | riable [37] +|| typedef [36] |ir [3] || /$ || file.h [4] file.h [4] -|oo() [21, 22, 23, 24] +|oo [24, 26, 28, 30] +|| ($ +|| ) [25, 27, 29, 31] a group [5, 6] | page [15] namespace [11] | :$ | :class [12] | | :$ -| | :foo() [21, 22, 23, 24] +| | :foo [24, 26, 28, 30] +| | ($ +| | ) [25, 27, 29, 31] | struct [13] | union [14] -| enum [33] +| enum [41] | | :$ -| | :value [32] -| typedef [34] -| variable [35] +| | :value [40] +| typedef [42] +| variable [43] class [12] | :$ -| :foo() [21, 22, 23, 24] +| :foo [24, 26, 28, 30] +| ($ +| ) [25, 27, 29, 31] struct [13] |ubpage [16] union [14] -macro [18] -| _function() [19] -| _with_params() [20] -value [25, 32] -| riable [35] -enum [28, 33] +macro [19] +| _function [20] +| ($ +| ) [21] +| _with_params [22] +| | ($ +| | ) [23] +value [32, 40] +| riable [43] +enum [35, 41] | :$ -| :deprecatedvalue [27] -| value [32] -typedef [34] +| :deprecatedvalue [34] +| value [40] +typedef [42] 0: Deprecated List [type=PAGE] -> deprecated.html 1: DeprecatedDir [deprecated, type=DIR] -> dir_c6c97faf5a6cbd0f62c27843ce3af4d0.html 2: /DeprecatedFile.h [prefix=1[:0], deprecated, type=FILE] -> DeprecatedFile_8h.html @@ -449,25 +465,33 @@ typedef [34] 14: ::Union [prefix=11[:0], type=UNION] -> unionNamespace_1_1Union.html 15: A page [type=PAGE] -> page.html 16: » Subpage [prefix=15[:0], type=PAGE] -> subpage.html -17: DEPRECATED_MACRO(a, b, c) [suffix_length=7, deprecated, type=DEFINE] -> DeprecatedFile_8h.html#a7f8376730349fef9ff7d103b0245a13e -18: MACRO [type=DEFINE] -> File_8h.html#a824c99cb152a3c2e9111a2cb9c34891e -19: _FUNCTION() [prefix=18[:14], type=DEFINE] -> 025158d6007b306645a8eb7c7a9237c1 -20: _FUNCTION_WITH_PARAMS(params) [prefix=18[:15], suffix_length=6, type=DEFINE] -> 8602bba5a72becb4f2dc544ce12c420 -21: ::foo() [prefix=12[:28], type=FUNC] -> #aaeba4096356215868370d6ea476bf5d9 -22: const [prefix=21[:30], suffix_length=6, type=FUNC] -> c03c5b93907dda16763eabd26b25500a -23: && [prefix=21[:30], suffix_length=3, deleted, type=FUNC] -> 77803233441965cad057a6619e9a75fd -24: ::foo(const Enum&, Typedef) [prefix=12[:28], suffix_length=20, type=FUNC] -> #aba8d57a830d4d79f86d58d92298677fa -25: ::Value [prefix=26[:67], type=ENUM_VALUE] -> a689202409e48743b914713f96d93947c -26: ::DeprecatedEnum [prefix=7[:33], deprecated, type=ENUM] -> #ab1e37ddc1d65765f2a48485df4af7b47 -27: ::DeprecatedValue [prefix=28[:67], deprecated, type=ENUM_VALUE] -> a4b5b0e9709902228c33df7e5e377e596 -28: ::Enum [prefix=7[:33], type=ENUM] -> #ac59010e983270c330b8625b5433961b9 -29: ::DeprecatedTypedef [prefix=7[:33], deprecated, type=TYPEDEF] -> #af503ad3ff194a4c2512aff16df771164 -30: ::DeprecatedVariable [prefix=7[:33], deprecated, type=VAR] -> #ae934297fc39624409333eefbfeabf5e5 -31: ::deprecatedFoo(int, bool, double) [prefix=7[:33], suffix_length=17, deprecated, type=FUNC] -> #a9a1b3fc71d294b548095985acc0d5092 -32: ::Value [prefix=33[:57], type=ENUM_VALUE] -> a689202409e48743b914713f96d93947c -33: ::Enum [prefix=11[:23], type=ENUM] -> #add172b93283b1ab7612c3ca6cc5dcfea -34: ::Typedef [prefix=11[:23], type=TYPEDEF] -> #abe2a245304bc2234927ef33175646e08 -35: ::Variable [prefix=11[:23], type=VAR] -> #ad3121960d8665ab045ca1bfa1480a86d +17: DEPRECATED_MACRO(a, b, c) [suffix_length=9, deprecated, type=DEFINE] -> DeprecatedFile_8h.html#a7f8376730349fef9ff7d103b0245a13e +18: [prefix=17[:56], suffix_length=7, deprecated, type=DEFINE] -> +19: MACRO [type=DEFINE] -> File_8h.html#a824c99cb152a3c2e9111a2cb9c34891e +20: _FUNCTION() [prefix=19[:14], suffix_length=2, type=DEFINE] -> 025158d6007b306645a8eb7c7a9237c1 +21: [prefix=20[:46], type=DEFINE] -> +22: _FUNCTION_WITH_PARAMS(params) [prefix=19[:15], suffix_length=8, type=DEFINE] -> 8602bba5a72becb4f2dc544ce12c420 +23: [prefix=22[:46], suffix_length=6, type=DEFINE] -> +24: ::foo() [prefix=12[:28], suffix_length=2, type=FUNC] -> #aaeba4096356215868370d6ea476bf5d9 +25: [prefix=24[:62], type=FUNC] -> +26: const [prefix=24[:30], suffix_length=8, type=FUNC] -> c03c5b93907dda16763eabd26b25500a +27: [prefix=26[:62], suffix_length=6, type=FUNC] -> +28: && [prefix=24[:30], suffix_length=5, deleted, type=FUNC] -> 77803233441965cad057a6619e9a75fd +29: [prefix=28[:62], suffix_length=3, deleted, type=FUNC] -> +30: ::foo(const Enum&, Typedef) [prefix=12[:28], suffix_length=22, type=FUNC] -> #aba8d57a830d4d79f86d58d92298677fa +31: [prefix=30[:62], suffix_length=20, type=FUNC] -> +32: ::Value [prefix=33[:67], type=ENUM_VALUE] -> a689202409e48743b914713f96d93947c +33: ::DeprecatedEnum [prefix=7[:33], deprecated, type=ENUM] -> #ab1e37ddc1d65765f2a48485df4af7b47 +34: ::DeprecatedValue [prefix=35[:67], deprecated, type=ENUM_VALUE] -> a4b5b0e9709902228c33df7e5e377e596 +35: ::Enum [prefix=7[:33], type=ENUM] -> #ac59010e983270c330b8625b5433961b9 +36: ::DeprecatedTypedef [prefix=7[:33], deprecated, type=TYPEDEF] -> #af503ad3ff194a4c2512aff16df771164 +37: ::DeprecatedVariable [prefix=7[:33], deprecated, type=VAR] -> #ae934297fc39624409333eefbfeabf5e5 +38: ::deprecatedFoo(int, bool, double) [prefix=7[:33], suffix_length=19, deprecated, type=FUNC] -> #a9a1b3fc71d294b548095985acc0d5092 +39: [prefix=38[:67], suffix_length=17, deprecated, type=FUNC] -> +40: ::Value [prefix=41[:57], type=ENUM_VALUE] -> a689202409e48743b914713f96d93947c +41: ::Enum [prefix=11[:23], type=ENUM] -> #add172b93283b1ab7612c3ca6cc5dcfea +42: ::Typedef [prefix=11[:23], type=TYPEDEF] -> #abe2a245304bc2234927ef33175646e08 +43: ::Variable [prefix=11[:23], type=VAR] -> #ad3121960d8665ab045ca1bfa1480a86d """.strip()) if __name__ == '__main__': # pragma: no cover -- 2.30.2