Evaluate HED search capability

[VisLab]

@claude Do a careful review of the HED search capabilities. Evaluate for efficiency and correctness. The main search features are in hed/models/query_*.py. The documentation is available at: http://www.hedtags.org/hed-resources/HedSearchGuide.html. If we are given plain strings rather than HedString objects, how much can we implement with string search? This is an important issue for searching within databases and platform independent search. In your response, identify which AI you are.

[github-actions]

Claude finished @VisLab's task in 5m 27s —— View job

---

HED Search Capability Review

I am Claude Sonnet 4.6, Anthropic's AI assistant.

---

Architecture Overview

The search system has a clean layered design across four files:

File	Role
query_util.py	Token (tokenizer atoms) and SearchResult (match holder)
query_expressions.py	Expression tree nodes: Expression, ExpressionAnd, ExpressionOr, ExpressionNegation, ExpressionDescendantGroup, ExpressionExactMatch, ExpressionWildcardNew
query_handler.py	QueryHandler — tokenizes, parses into expression tree, dispatches search
query_service.py	Higher-level utilities: get_query_handlers, search_hed_objs

The parser implements a correct recursive-descent grammar with proper operator precedence: OR < AND < negation < grouping < atoms. The tokenizer regex is compact and handles all documented syntax.

---

Search Modes

The Expression base class (query_expressions.py:9–23) encodes three dispatch modes via _match_mode:

Value	Trigger	Dispatches to
False	plain term e.g. Event	find_tags_with_term — ancestor search via tag_terms
True	term contains / e.g. Def/MyDef	find_exact_tags — full tag path match
1	quoted term "Event"	find_exact_tags — exact short-tag match
2	wildcard Eve* or Def/*	find_wildcard_tags — prefix match on short_tag

Using a bare boolean True and int 1 to mean different things is fragile. If "/" in token.text is True, _match_mode is True which equals 1 in Python (True == 1). That means the elif self._match_mode branch catches both the /-path case and the quoted-exact case correctly — but only by accident. The code should use named constants or an enum to avoid future confusion.

---

Correctness Issues

1. Tag form inconsistency across search methods (hed_group.py:436–596)

The four search methods use different tag representations:

• find_tags → tag.short_base_tag.casefold() (base only, no extension)
• find_wildcard_tags → tag.short_tag.casefold() (short form with value)
• find_exact_tags → tag.casefold() via tag.__eq__(str) (calls str(tag).casefold(), original-ish form)
• find_tags_with_term → tag.tag_terms (schema-derived ancestor tuple)

For a tag like Def/MyDef, short_base_tag = "Def", short_tag = "Def/MyDef", and str(tag) returns the original written form. Searching Def/MyDef uses find_exact_tags(["def/mydef"]) and calls tag.__eq__("def/mydef") → tag.casefold() == "def/mydef". If the tag was written in long form in the source HED string, this comparison may silently fail.

2. [[...]] double-bracket is tokenized but never parsed

The tokenizer regex in query_handler.py:105 captures [[ and ]]:

grouping_re = r"\[\[|\[|\]\]|\]|}|{|:"

But [[ and ]] are not mapped in Token.__init__ (they'd get kind Token.Tag), and _handle_grouping_op has no branch for them. This appears to be dead code or an unimplemented feature. Any query containing [[...]] would silently misparse.

3. ExpressionDescendantGroup drops the exact parameter (query_expressions.py:211–214)

class ExpressionDescendantGroup(Expression):
    def handle_expr(self, hed_group, exact=False):
        found_groups = self.right.handle_expr(hed_group)   # ← missing exact=exact
        found_parent_groups = self._get_parent_groups(found_groups)

The exact flag is accepted but not forwarded. For a query like {[a, b]} (exact match containing a descendant group), the inner [a, b] portion won't receive the exact=True context from its parent ExactMatch. Likely a latent bug.

4. @ operator is inconsistently documented

Token.NotInLine = 13 is accompanied by the comment # Not currently a token. In development and may become one. Yet @ IS functionally supported: the word regex in _tokenize includes @ in tag characters, so @Event tokenizes as a single word token, and Expression.__init__ (lines 15–17) strips the @ prefix and sets _must_not_be_in_line = True. It is used successfully in test_exact_group_negation4:

self.base_test("{ @c && @a && b: ???}", test_strings)

The comment and constant should be updated to reflect the actual implementation.

5. Error handling in get_query_handlers swallows exception details (query_service.py:47)

except Exception:
    issues.append(f"[BadQuery {index}]: {query} cannot be parsed")

The bare except Exception discards the original HedQueryError message. Users get no information about why the query failed to parse.

6. ExpressionNegation with wildcards restriction is overly broad (query_handler.py:141–144)

if "?" in str(interior):
    raise HedQueryError("Cannot negate wildcards...")

The check uses str(interior) which converts the entire subtree back to string. A negation like ~(Event && Action) would work fine, but ~([A, ?]) is prohibited even though the wildcard is one level removed. The prohibition is conservative but may be unnecessarily limiting.

---

Performance Issues

7. ExpressionAnd.merge_and_groups — O(n³) duplicate detection (query_expressions.py:103–123)

# This is trash and slow   ← the code's own comment
for finalized_value in return_list:
    if merged_result.has_same_children(finalized_value):
        dont_add = True
        break

For each pair (group, other_group) from a Cartesian product scan (already O(n²)), the code scans return_list linearly to check for duplicates, making the overall complexity O(n³). has_same_children itself does a sorted zip comparison which is O(k) where k = number of children. For deeply nested queries with many groups this is problematic. A proper fix would require a hashable SearchResult or a set-based deduplication scheme.

8. ExpressionOr.handle_expr — O(n²) duplicate filter (query_expressions.py:170–179)

# todo: optimize this eventually
duplicates = []
for group in groups1:
    for other_group in groups2:
        if group.has_same_children(other_group):
            duplicates.append(group)

Both the comment and the O(n²) scan signal a known deficiency. This is called on every OR operation including nested ones.

9. get_all_groups and get_all_tags use BFS with list prepend (hed_group.py:199–215, 217–241)

node_list = list(current_group_or_tag.children) + node_list  # prepend is O(n)

These are called on every search operation. List prepend is O(n); using a collections.deque or reversing to append-only would be more efficient for deep structures.

---

Design Observations

SearchResult design (query_util.py): Conceptually clean — the group represents the containing HedGroup and children the specific matched elements. The merge_and_result and has_same_children methods work by object identity (is), intentionally preventing the same physical tag from satisfying both sides of an AND query. This is correct semantics.

ExpressionExactMatch semantics: The distinction between {expr} (any-optional) and {expr:} / {expr: optional} is subtle but correctly implemented. {Event} finds groups containing Event among possibly other elements; {Event:} requires the group to contain only Event. This matches the documentation intent.

search_hed_objs (query_service.py:51–72): The implementation is straightforward but recompiles nothing (queries are pre-compiled QueryHandler objects), which is good. However, it accepts either QueryHandler objects or strings in the docstring but the code only calls .search() without checking types — passing a string would fail silently with an AttributeError.

---

String Search Feasibility

This is the core question for database/platform-independent search.

What requires a HedString (and thus a schema)

Feature	Why schema is needed
Ancestor search (e.g., Event finds Sensory-event)	tag_terms is computed from schema_entry.long_tag_name.split("/") — impossible without the schema hierarchy
Tag normalization	Sensory-event and Event/Sensory-event are the same tag — only the schema knows this
Extension/value separation	Schema tells whether Def/MyDef is base=Def, value=MyDef vs. an unknown tag
short_base_tag vs. extension	Needed for find_tags, find_top_level_tags

What CAN be implemented with plain string search

If HED strings in a database are stored in a canonical normalized form (all short tags, consistent spacing), the following subset is achievable with regex/string operations alone:

Query feature	String-search approach
Exact tag literal "Sensory-event"	Word-boundary regex: (?<![A-Za-z0-9-])Sensory-event(?![A-Za-z0-9-/])
Wildcard prefix Def/Def1*	Simple string startswith after splitting
Slash-path exact Def/MyDef	Regex with escaped slash
Boolean AND / OR / NOT	Compose regex or run separate checks
Group structure [...], {...}	A lightweight parenthesis-aware parser
@tag (not-in-line)	Negate the presence check

What is fundamentally not possible with string search

1. Ancestor-based search: Event matching Sensory-event requires the ontology. You cannot determine from "Sensory-event" alone that it is a descendant of Event.
2. Cross-form normalization: Without schema, "Event/Sensory-event" and "Sensory-event" are different strings.
3. tag_terms lookup: The find_tags_with_term call (default search mode for bare terms) uses the pre-computed tuple from the schema entry.

Practical Recommendation for Database Search

To enable string search in databases without loading the schema at query time:

Option A — Pre-expanded storage: At ingest time, for each HED string, also store a JSON array of (short_tag, long_tag_path, ancestor_list) tuples per tag. Queries can then be run as SQL/document queries against the expanded form.

Option B — Normalized flat storage: Store all tags in a canonical short form in a searchable field (e.g., comma-separated, deduplicated). Ancestor search still requires a schema index (lookable in a separate table), but boolean/wildcard/exact queries work as string operations.

Option C — Lightweight schema-free regex layer: For the subset of queries that don't need ancestor resolution (exact matches, wildcards, group structure), a dedicated StringQueryHandler could be implemented that operates on raw strings. This would be schema-free but would document clearly which query features are unavailable. The tokenizer and parser in QueryHandler could be reused; only the handle_expr dispatch in Expression would need a string-based backend.

---

Summary of Issues

#	Severity	Location	Issue
1	Medium	query_expressions.py:13	_match_mode uses True/1 ambiguously; should use named constants
2	Medium	query_handler.py:105	[[...]] tokenized but not parsed — dead/incomplete code
3	Medium	query_expressions.py:212	ExpressionDescendantGroup drops exact parameter
4	Low	query_util.py:97	@ operator implemented but Token constant says "not currently a token"
5	Low	query_service.py:47	except Exception discards parse error details
6	Low	query_handler.py:141	Wildcard negation prohibition uses string-based check on expression tree
7	High	query_expressions.py:114	O(n³) duplicate detection in AND merge (self-documented as "trash and slow")
8	Medium	query_expressions.py:170	O(n²) duplicate filter in OR (self-documented as "optimize eventually")
9	Low	hed_group.py:212	BFS in get_all_groups/get_all_tags uses O(n) list prepend
10	Medium	hed_group.py:436–596	Different tag attribute forms (short_base_tag, short_tag, casefold()) used inconsistently across search methods

The search system is functionally correct for the documented use cases (backed by solid tests in test_query_handler.py), but the performance issues in AND merge and OR deduplication would become significant for HED strings with many tags or complex nested queries. The [[...]] double-bracket issue is the most surprising — it tokenizes but produces incorrect/undefined behavior.

For string-based search, the ancestor search feature (the default for bare tag terms) is the hardest to replicate and the most commonly needed — it's what makes Event find Sensory-event. Any practical database search solution needs either schema-aware query execution or pre-expanded tag storage at ingest time.