Claim 8: Empirical Validation of AST-Free Parsing
The software engineering industry operates on a long-held axiom: you cannot reliably parse code with regular expressions. Traditional wisdom dictates that analyzing source code requires compiling an Abstract Syntax Tree (AST).
While ASTs are precise, they are rigid. They require complete, compilable environments, they break on legacy or fragmented code, and they demand a unique toolchain for every language. GitGalaxy claims we can bypass the AST entirely, using a polyglot engine driven by bounded mathematical regex and structural physics.
To make a claim this radical, the burden of proof is high.
We do not prove this with standard unit tests. We prove it through a localized adversarial testing architecture known as the Strict Extraction Gauntlets. These suites check that our regex engine isolates structural boundaries on adversarial cases and does not fall into catastrophic backtracking. Accuracy on real code is measured separately: on the pinned Language Crucible corpus, validated function precision is 100% across 31 tree-sitter-comparable languages (audit of 2026-08-30). That does not show it parses as accurately as an AST in general (Accuracy, measured).
The 3-Tier Adversarial Matrix
Because our regular expressions are the compiler, a poorly bounded pattern won't just fail a parse—it will hallucinate false architecture or lock the CPU in a ReDoS (Regular Expression Denial of Service) death spiral.
To validate our AST-free method, every structural rule across the supported languages (59 with function-level extraction) is subjected to a 3-tier adversarial matrix:
- The Iron Wall (Precision): The engine must match the target payload and isolate exactly the identifier name using strict capture groups, shedding all surrounding modifiers, generic bounds, and return types.
- Ghost Prevention (Hallucination Defense): The engine is fed structural lookalikes—variable assignments (
Target = function()), instantiations (new Target()), and control flow (if (Target)). It must definitively returnNone. It cannot hallucinate an entity that does not exist. - The Frankenstein Test (Pathological Formatting): Code in the wild is chaotic. The engine is bombarded with pathological payloads: massive vertical newlines, absurd attribute stacking, C-macro soup, and erratic pointer spacing. It must successfully extract the target in linear \(O(N)\) time.
Proving the AST-Free Claims
By leveraging the /extraction test suite, we empirically validate the four foundational pillars of GitGalaxy's structural physics.
1. Extracting Executable Logic (test_function_extraction_strict.py)
To map the execution surface of a system, we must accurately identify where logic begins. Standard regex fails on modern function signatures due to complex return types and decorator stacking.
Through the strict function gauntlet, we prove the engine can anchor onto the exact satellite name (the function or method). We validate that the engine can step over the C# "Iron Wall" (e.g., public async Task<Dictionary<string, List<int>>>), bypass C++ macro metadata ([[nodiscard]]), and gracefully handle vertical fragmentation in Swift and Scala. It proves we can map execution boundaries without generating a single AST node.
2. Extracting Object-Oriented Entities (test_class_extraction_strict.py)
To build the entity census, we must isolate the structural containers of the code (Classes, Structs, Traits, Enums).
The class extraction gauntlet proves our engine can identify the core entity name while completely ignoring massive inheritance chains and interface implementations. We validate that a pathological PHP 8 payload stacking #[Attributes], final, class, and implements Serializable across a dozen lines is instantly reduced to its true structural identifier, proving regex can reliably map object-oriented topology.
3. Extracting Coupling Mass (test_args_extraction_strict.py)
Extracting parameters is the most notorious trap in regex-based parsing because regular expressions cannot natively count nested parentheses.
The arguments gauntlet proves the efficacy of our 1-Level Nesting Protocol. By applying strict structural boundaries, we prove the engine can accurately swallow complex parameter blocks—including default arguments, explicit types, and inline closure callbacks in Rust and Dart—without breaking the regex boundary. We prove that coupling complexity can be measured without a syntax tree.
4. Tracing Information Flow (test_dependency_extraction_strict.py)
To build the global dependency graph, we must map how files link to one another.
The gravity link gauntlet proves our regex can isolate exactly the imported file or module path across all ecosystems. It validates that the engine survives multi-line destructuring in TypeScript (import type { A, B } from '@scope'), alias stacking in Go and Python, and C-style relative includes, The gauntlet tests extraction on hard cases; measured graph accuracy is narrower: the import graph is measured in 20 of 59 languages, and call links (measured in 3) are 93.2-99.9% precise with 44-57% recall (docs/graph_accuracy.md).
The ReDoS Shield: Guarding System Stability
If you attempt to parse code with regex, you will eventually encounter a string that forces the engine to evaluate millions of permutations, freezing the thread. This is Catastrophic Backtracking.
To validate that GitGalaxy is enterprise-ready, we back our extraction gauntlets with the Blast Chamber (test_language_standards_strict.py) and the Global Fuzzer (test_redos_poison.py).
We spawn an isolated 8-core multiprocessing pool and blast every single regex in the production pipeline (over 1,200 rules) with a "Toxic Arsenal" of classic ReDoS payloads: unclosed scopes, exponential overlapping whitespace, escaping quote hell, and C/C++ K&R ambiguity traps.
If any rule takes longer than a 0.25-second kill-switch, it fails the build.
The Conclusion
The GitGalaxy test architecture is not just a safety net; it is a specification. These strict, adversarial gauntlets, together with the measured comparisons in the README, are our evidence that AST-free structural parsing is possible and, on the measured corpus, accurate, with the limits stated there.