Architectural Specification and Implementation Strategy for Tantivy Engine Integration

Architectural Specification and Implementation Strategy for dt2tantivy: A dtSearch-to-Tantivy Transpiler The intersection of legal technology, electronic discovery (eDiscovery), and modern high-performance information retrieval presents a unique architectural challenge. For decades, the eDiscovery industry has relied heavily on the dtSearch engine and its highly specialized query syntax to execute complex document retrieval, pattern matching, and proximity calculations across massive corporate data corpora. The syntactic conventions of dtSearch have become the entrenched standard for legal review workflows, dictating everything from complex Boolean precedence rules to unordered and ordered proximity operators, as well as the specific spatial handling of noise words. Legal professionals and boutique litigation firms construct heavily nested queries to establish defensible document review sets, meaning any deviation in query interpretation can result in catastrophic legal liabilities, missed evidence, or false positives.

Concurrently, Tantivy has emerged as a state-of-the-art, open-source full-text search engine library written in Rust. Heavily inspired by the design paradigms of Apache Lucene, Tantivy offers memory safety, zero-cost abstractions, and blazing-fast performance metrics, operating via an embedded segment-based architecture rather than a standalone server. Tantivy leverages finite state transducers (FSTs) for its term dictionaries, bitpacked integer compression for its inverted indexes, and natively supports Best Match 25 (BM25) scoring. Despite its unparalleled performance, Tantivy utilizes a native query parser that defaults to standard mathematical Boolean precedence and lacks native parsing logic for the idiosyncratic operators unique to the dtSearch ecosystem.

The dt2tantivy project proposes a strictly bounded, Abstract Syntax Tree (AST)-based transpiler written in Rust to bridge this critical capability gap. By leveraging a formal Parsing Expression Grammar (PEG) via the pest crate, the system will deterministically lex and parse dtSearch syntax, construct a strongly typed AST, and compile that tree directly into native tantivy::query::Query objects. This comprehensive report details the exhaustive architectural strategy for the Minimum Viable Product (MVP), explicitly addressing the complex transposition of dtSearch proximity semantics, character normalization, and noise word offset handling into Tantivy’s native indexing structures.

Tantivy Core Architecture and Indexing Foundations

To successfully transpile queries from one domain-specific language into another, the underlying index structures of the target engine must be thoroughly understood. Tantivy’s architecture follows a write-once, read-many (WORM) directory abstraction, where documents are indexed into discrete, immutable segments. Each segment contains its own inverted index, which maps unique terms to posting lists—sorted lists of document identifiers where that term appears, alongside metadata such as term frequency and spatial positions.

When a text field is configured in Tantivy’s schema using the TEXT flag, the engine tokenizes the input, indexes the terms, and explicitly stores term positions. This positional data is critical for phrase matching and proximity queries. The position file contains bitpacked position deltas for all terms within a given field, encoded in blocks of 128 deltas using SIMD (Single Instruction, Multiple Data) bitpacking. Because word offsets are stored as variable byte integers, Tantivy is highly optimized for sequential access and rapid skipping over position payloads during phrase queries.

Furthermore, Tantivy’s term dictionary maps terms to their posting list offsets using a finite state transducer. The FST is an immutable data structure that represents a sorted set of key-value pairs, achieving extreme space efficiency by sharing common prefixes and suffixes between terms. Understanding this FST architecture is vital for the transpiler’s handling of wildcards; while suffix wildcards perform efficiently via prefix lookups in the FST, leading wildcards force a full index scan, a performance bottleneck that both dtSearch and Tantivy seek to avoid.

Phase 1: Lexical Analysis and PEG Grammar Definition

The foundation of the transpiler requires mapping the idiosyncratic lexical rules of dtSearch into a formal Parsing Expression Grammar. Unlike standard search engines that rely on simple regular expression tokenizers, dtSearch employs highly specific character normalization, truncation limits, and wildcard execution rules that must be captured at the lexer level before AST construction can begin. The pest crate in Rust provides an elegant, highly performant mechanism to define these rules using PEG, which avoids the pitfalls of ambiguous regex-based string manipulation by enforcing deterministic parsing paths.

Character Normalization and Punctuation Handling

In the dtSearch ecosystem, punctuation inside a search word is fundamentally treated as a space character, unless explicitly modified via a custom alphabet file. For instance, the string can't is automatically interpreted as a phrase consisting of two distinct words: can and t. Similarly, complex alphanumeric strings containing parentheses, such as 1843(c)(8)(ii), are parsed as four distinct, consecutive words: 1843 c 8 ii.

The PEG grammar defined in the pest crate must account for this behavior by defining a word token rule that terminates at any punctuation boundary not explicitly escaped or part of a recognized dtSearch operator (such as the forward slash in the w/N proximity operator). The transpiler must seamlessly split these punctuated strings during the lexing phase, transforming them into sequence arrays that will eventually map to phrase queries. Furthermore, dtSearch indexes are inherently case-insensitive, normalizing all characters to lowercase upon ingestion. The lexer must normalize all incoming query strings to lowercase prior to matching exact phrase literals or generating Term objects for Tantivy, ensuring that queries for the acronym "ACT" identically match indexed tokens for "act", "AcT", or "aCt".

Wildcard and Pattern Matching Tokens

The grammar must explicitly define the allowed wildcard characters and establish their operational boundaries. dtSearch utilizes several specific wildcard patterns that differ slightly from standard POSIX regex or Lucene wildcard implementations. The transpiler must lex these characters uniquely to ensure they trigger the correct compilation path later in the pipeline.

dtSearch Operator Functionality Lexer Token Mapping Target Tantivy Compilation

• Matches zero or more characters. Rule::WildcardAsterisk Regex .* via RegexQuery

[cite: 8, 18, 19]

? Matches any single character. Rule::WildcardQuestion Regex . via RegexQuery

[cite: 17]

= Matches any single numerical digit. Rule::WildcardDigit Regex \d via RegexQuery

[cite: 1, 20]

% Applies fuzzy matching based on edit distance. Rule::FuzzyMatch FuzzyTermQuery

[cite: 17, 21, 22]

The lexer must differentiate between wildcards appended to literals (e.g., apple) and standalone wildcards. Notably, dtSearch explicitly prohibits wildcards at the beginning of a word due to the massive performance impact on the underlying index structures. Leading wildcards cannot leverage the FST term dictionary efficiently. The pest grammar must therefore define the term rule such that it mandates an alphanumeric character prefix prior to accepting wildcard characters. If a leading wildcard (e.g., ing) is detected, the parser should immediately return a descriptive error, maintaining parity with standard dtSearch limitations.

Truncation Limits and Literal Constraints

In traditional dtSearch indexing, words longer than 32 characters are automatically truncated, acting as an internal safeguard against buffer overflows and index bloat. Furthermore, if a symbol (such as an underscore or ampersand) is remapped to act as a searchable character in the environment's alphabet file, dtSearch will unconditionally truncate the search string after the 32nd character. To perfectly align with legacy dtSearch behavior and prevent unexpected query misses, the transpiler’s lexing phase should enforce a 32-character maximum on all literal terms. When a token exceeds this limit, the transpiler should either silently truncate it to match the assumed index state or raise a strict mode warning to the consuming application.

Phase 2: AST Construction and the Precedence Anomaly

Once the raw strings are accurately tokenized, the system must structure them into an Abstract Syntax Tree. Because dtSearch queries can be deeply nested with parentheses and complex logical operators, a simple linear evaluation or recursive descent parser is insufficient and prone to deep call-stack errors. The architecture relies on top-down operator precedence parsing to manage this complexity.

The pest PrattParser Implementation

To handle operator precedence efficiently without smearing the grammar across recursive descent rules, the architecture leverages the PrattParser struct provided by the pest crate. Vaughan Pratt's parsing algorithm is uniquely suited for expression parsing, allowing developers to define a flat sequence of tokens in the grammar (e.g., prefix ~ primary ~ postfix ~ (infix ~ prefix ~ primary ~ postfix)*) and dynamically bind them into a hierarchical AST based on explicit precedence and associativity rules.

By utilizing the PrattParser, the transpiler evaluates expressions from left to right, combining tokens into nodes based on the strength (binding power) of the operators. This prevents the need for overly verbose grammars that attempt to manually stratify operator precedence into a tower of rules.

The dtSearch Precedence Inversion

The most critical architectural requirement in the parsing phase is the accurate handling of dtSearch's anomalous Boolean precedence. In standard Boolean logic, SQL, and Tantivy's native QueryParser, the AND operator binds more tightly (takes precedence) over the OR operator. For example, a search engine evaluating the query A AND B OR C universally interprets the syntax as (A AND B) OR C.

However, dtSearch fundamentally violates this standard. By default, dtSearch prioritizes OR operators before AND operators. Therefore, the dtSearch query apple AND pear OR grape evaluates as apple AND (pear OR grape). This distinction is paramount in eDiscovery contexts. If a litigation team attempts to query for communications containing "contract" AND either "breach" OR "violation", a standard parser would execute (contract AND breach) OR violation, returning thousands of irrelevant documents that simply contain the word "violation" without any mention of a contract. Failure to respect this precedence inversion would result in catastrophic search inaccuracies.

Within the Rust pest::pratt_parser::PrattParser implementation, the order of precedence corresponds precisely to the sequential order in which the .op() method is invoked during parser instantiation. The operator registered later in the chain receives higher precedence. To accurately model dtSearch syntax, the transpiler must define the Pratt Parser explicitly in inverted order:

Rust let pratt = PrattParser::new() .op(Op::infix(Rule::and, Assoc::Left)) // Lower precedence in dtSearch .op(Op::infix(Rule::or, Assoc::Left)) // Higher precedence in dtSearch .op(Op::infix(Rule::wn, Assoc::Left)) // Proximity binds tighter than Boolean

Structuring the Rust AST Enums

The map_infix, map_prefix, and map_primary mapping functions of the PrattParser will collapse the evaluated token pairs into a strongly typed, recursive Rust enum. Due to the recursive nature of trees, the DtNode enum requires Box pointers to ensure the Rust compiler can ascertain the size of the structure at compile time.

Node Type Enum Definition Semantic Description

Literal Term(String) A standalone alphanumeric search word, normalized to lowercase. Phrase Phrase(Vec<String>) A strict sequence of words enclosed in quotes, maintaining order. Wildcard Regex(String) A term containing dtSearch wildcards (e.g., *, ?), pending regex conversion. Logical AND And(Box<DtNode>, Box<DtNode>) Requires both child nodes to be present in the document. Logical OR Or(Box<DtNode>, Box<DtNode>) Requires at least one child node to be present in the document. Logical NOT Not(Box<DtNode>) Excludes documents containing the child node. Proximity Within(Box<DtNode>, Box<DtNode>, u32) Unordered distance constraint (w/N), capping intervening words.

Phase 3: Compiling the AST to Tantivy Native Queries

With a validated and correctly nested AST, the transpiler must recursively traverse the DtNode tree and map it to Box<dyn tantivy::query::Query> objects. This recursive evaluation converts abstract user intent into actionable scoring and retrieval mechanics.

Standard Boolean Operations

The core logical operations map smoothly to Tantivy's highly optimized tantivy::query::BooleanQuery.

DtNode::And: Maps to a BooleanQuery where both sub-queries are combined using the Occur::Must constraint, ensuring that the document satisfies both branches of the AST to receive a score.

DtNode::Or: Maps to a BooleanQuery where sub-queries are combined using Occur::Should. If multiple Should clauses match, Tantivy will sum their BM25 scores, boosting the relevance of documents that contain multiple terms.

DtNode::Not: The NOT operator presents a unique translation challenge. In dtSearch, the NOT operator can act as a standalone prefix (e.g., NOT pear), which theoretically returns all documents in the corpus that do not contain the specified word. In Tantivy, a pure negative query cannot execute efficiently on its own because there is no positive posting list to iterate over. To execute this, the transpiler must wrap the negative clause in a BooleanQuery combined with an Occur::Must clause containing an AllQuery (which matches all documents in the index), paired with the negated term mapped to Occur::MustNot. When NOT acts as a connector (e.g., apple AND NOT pear), it simplifies to an Occur::Must for "apple" and an Occur::MustNot for "pear".

Wildcards and Regex Mapping

Because Tantivy does not natively support dtSearch wildcard syntax out of the box, AST nodes containing wildcards must be transformed into standard POSIX regular expressions before being injected into tantivy::query::RegexQuery.

The compilation engine applies a simple substitution routine:

The dtSearch asterisk () is mapped to . in regex.

The dtSearch question mark (?) is mapped to . in regex.

The dtSearch equals sign (=), which matches a single digit, is mapped to \d in regex.

All other regex control characters must be aggressively escaped to prevent users from injecting invalid patterns that could panic the engine.

Once the substitution is complete, the transpiler wraps the resulting pattern in regex anchors (e.g., ^pattern$) to ensure it matches the entire token exactly, rather than matching a substring within a larger token. The resulting string initializes the RegexQuery.

Phrase Queries and Strict Adjacency

Exact phrases dictate that a sequence of terms must appear contiguously and in the specified order. In Tantivy, this maps to a PhraseQuery. The lexing phase will have already split the original quoted string by spaces and punctuation, resulting in a vector of individual words. The transpiler iterates this vector, constructing a sequence of Term objects, and utilizes tantivy::query::PhraseQuery::new(terms). By default, this method assigns a slop of 0, enforcing strict adjacency by verifying that the positional offsets in the bitpacked position block are perfectly sequential. However, the presence of noise words severely complicates this logic, an issue addressed extensively below.

Deep Dive 1: Approximating w/N via Tantivy Phrase Slop

The most technically demanding aspect of the initial MVP is the implementation of the dtSearch w/N (unordered proximity) operator. In dtSearch, the syntax apple w/5 pear dictates that the word "apple" must occur within 5 words of "pear". Crucially, the w/N operator is mathematically symmetrical; executing apple w/5 pear returns the exact same result set and proximity highlights as pear w/5 apple.

Tantivy does not feature a native unordered proximity query object. However, it does possess a highly optimized PhraseQuery structure that allows for configurable "slop". Slop allows leniency in term proximity for a performance trade-off, relying on an edit distance calculation across the token position ordinals retrieved from the PositionReader. To determine if w/N can be robustly approximated by this slop parameter, an analysis of the mathematical differences in how both engines calculate term distance is required.

The Mathematics of dtSearch Proximity vs. Tantivy Slop

In dtSearch, distance is calculated by absolute word count between the targets. If the document text is A x y B, the distance between term A and term B is exactly 2 intervening words, cleanly satisfying a w/2 constraint.

In Tantivy, slop is not a count of intervening words; it is defined as an edit distance budget. The query will successfully match a document only if its terms can be aligned by performing a number of positional moves less than or equal to the designated slop budget. By default, PhraseQuery terms have sequential offsets assigned during query construction (e.g., Term A at offset 0, Term B at offset 1).

Forward Match: To match the document text A x y B, Term B must move 2 positions to the right from its expected adjacent offset. This operation costs 2 slop. Therefore, for a forward match, Tantivy slop perfectly mimics dtSearch intervening word counts.

Reverse Match: If the terms appear in reverse order in the document, for example, B x y A, Tantivy requires Term A to move past Term B. As explicitly documented in the Tantivy source code, transposition inherently costs 2 slop: Term A is moved 1 position forward, and Term B is moved 1 position backward, yielding a combined budget deduction of 2. Consequently, simply to match the adjacent string B A with a query for A B, a slop of 2 is immediately required before accounting for any intervening words.

Because dtSearch w/N is symmetrically unordered, an effective approximation using Tantivy requires calculating a slop value that permits both the maximum intervening words and the maximum penalty incurred by the transposition cost.

The N + 2 Implementation Strategy for w/N Approximation When the AST compiler encounters a DtNode::Within(node_a, node_b, n) where both child nodes are literals, the transpiler must utilize the specialized tantivy::query::PhraseQuery::new_with_offset_and_slop constructor.

Offset Assignment: The transpiler generates a base vector mapping Term A to offset 0 and Term B to offset 1.

Slop Calculation: To approximate w/N symmetrically, the slop must be mathematically set to N + 2.

The N accounts for the maximum allowed intervening words (positional moves).

The + 2 accounts for the unavoidable transposition cost penalty incurred if the words appear in reverse order in the index.

Limitations of the Approximation: This method is a highly effective approximation, but it has boundaries. Tantivy's slop is a shared budget across all terms in a multi-term phrase query. For simple two-term proximities (e.g., A w/5 B), the N+2 slop behaves almost identically to dtSearch. However, for deeply nested proximities—such as (A and B) w/10 C—this PhraseQuery approximation breaks down entirely, because Tantivy's phrase mechanics expect strict string Term types, not complex recursive Boolean sub-queries.

To maintain system integrity, the AST compiler must enforce a strict typing rule during the compilation phase: if the children of a DtNode::Within are not literals or simple un-nested phrases, the compiler must explicitly fail and return an error, preventing silent search failures.

def compile_to_tantivy(node: DtNode, warnings: list[str], target_field: str = "text") -> str:
    """Compile a DtNode AST into a Tantivy-compatible query string."""
    expanded = expand_proximity_or(node)
    return _compile(expanded, warnings, target_field=target_field)

def _compile_proximity(node: Within | NotWithin | Pre, warnings: list[str], target_field: str) -> str:
    match node:
        case Within(left=left, right=right, distance=d) | Pre(left=left, right=right, distance=d):
            val1 = _get_raw_val(left)
            val2 = _get_raw_val(right)
            # w/N approximation: Tantivy slop accounts for distance + transposition cost (N + 2)
            slop = d + 2
            return f'{target_field}:"{val1} {val2}"~{slop}'

Deep Dive 2: Noise Word Configurations and AST Adjustments

Noise words—also known as stop words—are highly common linguistic constructs (e.g., the, if, in, are, to, of) that are frequently ignored during index construction to save compute time and minimize index size. The default dtSearch environment maintains a list of roughly 100 configured noise words.

While noise words are actively discarded from the searchable index, their spatial presence is strictly maintained. They fundamentally affect word counting and proximity algorithms. If the phrase "The Statue of Liberty" is indexed, dtSearch recognizes that the word offset of "statue" is 2 (accounting for the noise word "The"). When a legal user subsequently searches for a phrase containing a noise word (e.g., "statue of liberty"), dtSearch ignores the noise word within the query string but enforces the spatial gap, searching for the word statue, followed by any single intervening word, followed by the word liberty.

The Tantivy Tokenization Discrepancy

By default in the Tantivy ecosystem, if a text field utilizes a tokenizer configured with a StopWordFilter, the stop words are completely excised from the token stream. If the source text is "statue of liberty", the tokenizer outputs "statue" at position 0, and "liberty" at position 1. If Tantivy indexes the document under this configuration, a standard PhraseQuery for "statue of liberty" will catastrophically fail because it expects "statue" at offset 0, "of" at offset 1, and "liberty" at offset 2.

To successfully transpile dtSearch syntax while respecting noise word spacing, the architecture must coordinate both index-time schema assumptions and dynamic search-time AST mutations.

Search-Time AST Mutation via Custom Offsets

The transpiler itself does not control the data ingestion pipeline, but it must generate queries that exhibit dtSearch-like behavior. During Phase 2, when the compiler maps a DtNode::Phrase(Vec<String>) into a tantivy::query::PhraseQuery, the transpiler must intercept the individual terms and cross-reference them against a configurable HashSet containing the active dtSearch noise word list.

If a term in the phrase matches an entry in the noise word list, it must be discarded from the PhraseQuery term list, but the subsequent term offsets must be explicitly incremented to preserve the spatial gap.

Array Index Input Term Noise Word Check AST Action Tantivy Query Offset Assignment

0 "statue" False Retain Offset 0 1 "of" True Discard Skipped (Increment counter) 2 "liberty" False Retain Offset 2 By iterating through this logic, the transpiler invokes tantivy::query::PhraseQuery::new_with_offset(terms) where terms is explicitly defined as the vector [(0, Term("statue")), (2, Term("liberty"))].

By injecting custom offsets, Tantivy natively searches the inverted BitPackedPositionBlock lists for the exact token spacing expected by the end user, effortlessly mimicking dtSearch’s noise word skipping behavior at the query level.

Architectural Dependency Note: This search-time AST mutation relies entirely on the assumption that the underlying Tantivy index was built using a tokenizer that either does not strip stop words, or strips them but explicitly preserves the position increments (leaving a blank ordinal position in the token stream). This hard dependency must be documented as a requirement in the dt2tantivy library API.

Phase 4: Graceful Degradation and the Rejection of pre/N

To ensure the MVP remains a manageable, highly performant software artifact, certain complex positional features from the dtSearch specification must be explicitly rejected rather than approximated poorly. The most prominent and technically prohibitive of these is the dtSearch pre/N operator.

The pre/N operator executes a directed, strictly ordered proximity search. The query string apple pre/5 pear dictates that the word "apple" must occur within 5 or fewer words before "pear". It strictly enforces token sequence and directional flow through the document text.

While the transpiler successfully approximated w/N (unordered proximity) using Tantivy's PhraseQuery slop budget, slop is inherently omnidirectional. A PhraseQuery configured with a slop of 5 will routinely match documents where "pear" appears before "apple", directly violating the legal constraints and syntactic expectations of the pre/N operator.

Because Tantivy lacks a native directed proximity query out of the box, supporting pre/N would require constructing a low-level custom Scorer and Weight implementation directly in Rust. This advanced implementation would necessitate manual iteration over SegmentReaders, utilizing the PositionReader to unpack and decode bitpacked position deltas, and writing highly optimized custom traversal logic to verify forward-only ordinal distances between term matches across millions of records.

This level of custom inverted index traversal and memory management falls far outside the scope of an AST transpiler MVP. Therefore, Phase 4 mandates an architecture of graceful degradation. When the Pratt Parser identifies a pre/n token, it will successfully build a DtNode::Pre(Box<DtNode>, Box<DtNode>, u32) node, maintaining the integrity of the parsing phase. However, the compilation engine will explicitly intercept this node during the traversal and return a strongly typed Rust Result::Err(DtCompilerError::UnsupportedOperator("pre/N requires custom Scorer")). This fail-fast mechanism prevents silent query inaccuracies and protects the integrity of eDiscovery workflows, establishing a clear path for a custom Scorer implementation in a future release cycle.

Synthesis and Strategic Outlook

The dt2tantivy library represents a critical architectural bridge, empowering the eDiscovery and legal tech industries to transition their backend infrastructure from legacy systems into the memory-safe, ultra-fast Rust ecosystem without abandoning their vast, deeply entrenched libraries of complex dtSearch queries.

By strategically utilizing the pest crate to handle lexical nuances and deploying a PrattParser to explicitly invert the Boolean precedence anomaly inherent to dtSearch, the transpiler guarantees syntactically flawless Abstract Syntax Trees. Furthermore, by exploiting Tantivy's low-level PhraseQuery constructors—specifically leveraging new_with_offset for noise word preservation and mathematically mapping unordered proximity to new_with_offset_and_slop—the MVP can successfully execute the vast majority of high-value dtSearch operations using purely native, highly optimized Tantivy objects.

This phased, strictly bounded approach ensures a robust, fail-safe compiler that delivers immediate performance value while gracefully rejecting unsupported operations, laying a stable, extensible foundation for future custom scoring implementations.

@techreport{deepthought2026dt2tantivy,
  author      = {Epistemon and {Deep Thought Labs}},
  title       = {{Architectural Specification and Implementation Strategy for Tantivy Engine Integration: dt2tantivy: Complete Replacement of Legacy dtSearch with Native Embedded Rust Search Engine}},
  institution = {Deep Thought Labs},
  type        = {Architectural White Paper},
  series      = {Sublate Catalyst Technical Reports},
  year        = {2026},
  month       = {10},
  url         = {https://deepthoughtlabs.ai/papers/dt2tantivy/},
  note        = {Permanent canonical archive}
}