String Utilities & Distance Metrics Subsystem Architectural & Operational Guide
1. Executive Architectural Summary
The String Utilities & Distance Metrics Subsystem (pkg/strutil) provides fundamental string manipulation, fuzzy distance computation, rune escaping, and token extraction services across the ZQK Knowledge Kernel.
String processing is central to human-agent collaboration and kernel operations:
- Deterministic Default & Fallback Resolution: Safe handling of optional parameters, configuration cascades, pointer dereferences, and fallback chains without nil-pointer dereferences or unexpected empty string assignments.
- Fuzzy Distance Metrics & Typo Correction: Fast, memory-bounded Levenshtein distance computations that power CLI command suggestion ("Did you mean..."), filter query validation, acronym resolution, and knowledge graph fuzzy matching.
- Escaping & Syntax Sanitization: Precise escape rune decoding for parser grammars (e.g. ZQL mutations, ZPARQL queries, template expansion) and injection defense across shell and query boundaries.
- Line-Delimited Token Extraction: Extraction of operational metadata, command prefixes (e.g.,
CMD:,VERIFY:), and numeric validation across stdout, log streams, and process output. - Static Floor Coverage Invariant: A strict statement test coverage invariant (>= 85.0%, maintained at 100.0%) ensuring all edge branches and memory bounds are deterministically verified.
2. Component Topology & Subsystem Architecture
The subsystem is organized into four modular, stateless functional components designed for zero memory leaks and linear space complexity:
flowchart TD
subgraph Clients["Subsystem Consumers"]
CLI["CLI Commands & Parser (cmd/zqk)"]
Scheduler["Scheduler Core & Daemons"]
Validation["Object Validation Engine"]
Storage["Storage & Filter Parser"]
Swarm["Agent Swarm & MCP Mesh"]
end
subgraph StrUtil["String Utilities Subsystem (pkg/strutil)"]
DefaultResolver["Default Resolver & Fallback\n(default.go)"]
DistanceEngine["Levenshtein Distance Engine\n(distance.go)"]
StringEscaper["Escape Rune Decoder\n(escape.go)"]
TokenExtractor["Token & Line Extractor\n(extraction.go)"]
end
CLI -->|"Command Typo Suggestions"| DistanceEngine
CLI -->|"Prefix Extraction (CMD:, VERIFY:)"| TokenExtractor
Scheduler -->|"Profile & Fallback Resolution"| DefaultResolver
Validation -->|"Line Prefixes & Digit Checks"| TokenExtractor
Storage -->|"Fuzzy Filter Matching"| DistanceEngine
Swarm -->|"Rune Decoding & Escapes"| StringEscaper
Component Responsibilities
| Component | Source File | Core Responsibility |
|---|---|---|
| Default Resolver | default.go |
Non-empty string fallbacks (OrDefault, DefaultWhenNonEmpty), generic pointer resolution (PtrOrDefault), first-non-nil search (FirstNonNil), and cross-platform newline splitting (SplitLines). |
| Levenshtein Distance Engine | distance.go |
Dynamic programming matrix edit distance calculation with memory safety guards (maxLevenshteinStringLen = 4096) and O(min(N, M)) buffer allocation. |
| String Escaper | escape.go |
Lexical escape rune decoding (\n, \t, \r, \\, \", \') preventing unescaped control sequence corruption in query and mutation parsers. |
| Token Extractor | extraction.go |
Line scanning, prefix-based metadata extraction (ExtractFirstPrefixedValue), line location (FindLineWithPrefix), and strict ASCII digit verification (IsAllDigits). |
3. Levenshtein Distance & Fuzzy Match Mechanics
The subsystem calculates edit distance between strings using the Wagner-Fischer dynamic programming algorithm optimized for space efficiency and bounded against denial-of-service allocations.
sequenceDiagram
autonumber
actor Caller as CLI / Query Engine
participant Engine as strutil.LevenshteinDistance
participant Bounds as Memory & Length Guard
participant Matrix as DP Vector Buffer
Caller->>Engine: LevenshteinDistance(s1, s2)
Engine->>Bounds: Check len(s1), len(s2) == 0
alt Either string empty
Bounds-->>Caller: Return length of other string
end
Engine->>Bounds: Check len > maxLevenshteinStringLen (4096)
alt Length exceeds 4096
Bounds-->>Caller: Return max(len(s1), len(s2)) immediately
end
Engine->>Engine: Swap so s2 is shorter: O(min(la, lb)) space
Engine->>Matrix: Allocate 2 rows: prev, curr of size (lb + 1)
loop For each char i in s1 (1..la)
Matrix->>Matrix: Compute substitution / insertion / deletion min cost
Matrix->>Matrix: copy(prev, curr)
end
Matrix-->>Caller: prev[lb] (Minimum Edit Distance)
Space & Memory Bounds
- Length Ceilings: Comparisons between strings exceeding
maxLevenshteinStringLen(4,096 bytes) bypass DP matrix allocation entirely and returnmax(len(s1), len(s2)). This guards against quadratic allocation attacks from unverified external payloads. - Buffer Recycling: Instead of a full
O(la * lb)matrix, the engine maintains only two rows (prevandcurr), reducing allocation toO(min(la, lb))integers. - Symmetry Optimization: If
la < lb, inputs are swapped so that the inner loop allocations always match the shorter string.
Normalized Similarity Ratio
When suggesting commands or fuzzy matching object identifiers, consumers normalize Levenshtein distance into a unit interval score [0.0, 1.0]:
A match threshold of >= 0.70 is typically applied for CLI command suggestions (e.g., matching stat to status).
4. Default Resolution & Coalesce Patterns
Configuration layers across the kernel resolve values hierarchically: CLI flags override environment variables, which override configuration files, which override system defaults.
flowchart LR
CLI_Flag["CLI Flag\n(opts.Profile)"] -->|nil / empty| EnvVar["Environment Variable\n(ZQK_PROFILE)"]
EnvVar -->|nil / empty| ConfigFile["Config File\n(config.Profile)"]
ConfigFile -->|nil / empty| SysDefault["System Fallback\n('default')"]
SysDefault --> Resolved["Resolved Non-Empty Value"]
Primary Resolution Functions
OrDefault(value, defaultVal string) string: Returnsvalueif non-empty; otherwise returnsdefaultVal.DefaultWhenNonEmpty(value, defaultVal string) string: ReturnsdefaultValwhenvalueis non-empty; used for override masking.PtrOrDefault[T any](v *T, defaultVal T) T: Dereferencesvwhen non-nil; returnsdefaultValifvis nil.FirstNonNil[T any](ptrs ...*T) *T: Returns the first non-nil pointer in a variadic sequence, enabling clean hierarchical chains.SplitLines(s string) []string: Normalizes CRLF (\r\n), CR (\r), and LF (\n) line endings consistently across platforms.
5. Escaping & Lexical Parsing Safeguards
Parsers in pkg/mutation (ZQL AST) and pkg/traversal (ZPARQL AST) encounter escaped string literals in query clauses. DecodeEscapeRune converts escape sequences back to their raw characters:
stateDiagram-v2
[*] --> ReadRune
ReadRune --> Newline: 'n'
ReadRune --> Tab: 't'
ReadRune --> CarriageReturn: 'r'
ReadRune --> Backslash: '\\'
ReadRune --> DoubleQuote: '\"'
ReadRune --> SingleQuote: '\''
ReadRune --> PassThrough: Any other rune
Newline --> [*]: Returns '\n'
Tab --> [*]: Returns '\t'
CarriageReturn --> [*]: Returns '\r'
Backslash --> [*]: Returns '\\'
DoubleQuote --> [*]: Returns '\"'
SingleQuote --> [*]: Returns '\''
PassThrough --> [*]: Returns raw rune
Safety Guarantees
- No Panic on Unknown Escapes: Unknown or unescaped runes fall through unmodified rather than causing parser faults.
- Control Character Isolation: Translates escaped control runes without invoking external shell or CGo libraries.
6. Token Extraction & Line Parsing
The subsystem provides deterministic line inspection functions optimized for parsing CLI outputs and formatted reports:
-
ExtractFirstPrefixedValue(lines []string, prefixes ...string) string: - Iterates lines, trims outer whitespace, and tests against candidate prefixes. - Trims and returns the remainder after the first matching prefix. - Used extensively by verification and test drivers to extract metadata keys likeCMD:,VERIFY:, orHASH:. -
FindLineWithPrefix(lines []string, prefixes ...string) string: - Returns the entire line that matches any of the prefixes. - Useful for locating actionable command invocations in unstructured instruction logs. -
IsAllDigits(s string) bool: - Strictly validates whether a string contains only ASCII decimal digits ('0'through'9'). - Rejects empty strings, signed integers (+,-), whitespace, punctuation, and Unicode non-ASCII numerals to prevent injection into identifier parsers.
7. Verification & Coverage Invariant
Statement test coverage for pkg/strutil is governed by a strict architectural floor invariant:
Verification Command
To verify coverage locally in isolation without triggering broad test suites:
ZQK_ALLOW_FOREGROUND_GO_TEST=1 go test -v -timeout 30s -cover ./pkg/strutil
Test Fixture Architecture
All unit and boundary proofs are maintained in:
pkg/strutil/default_test.gopkg/strutil/distance_test.gopkg/strutil/escape_test.gopkg/strutil/extraction_test.gopkg/strutil/strutil_coverage_elevation_cycle174_test.go