45 lines
2.3 KiB
Markdown
45 lines
2.3 KiB
Markdown
|
# 3. Method-level n-gram clustering before inference
|
||
|
|
|
||
|
|
**Date:** 2026-07-03
|
||
|
|
|
||
|
|
**Status:** Accepted
|
||
|
|
|
||
|
|
## Context
|
||
|
|
|
||
|
|
The BEX ensemble (CRX, iDRegEx, kORE) infers grammars from sets of symbol sequences. When we run inference on *all methods in a codebase*, the sequences are too diverse — each file has different conventions, and the ensemble produces only a flat vocabulary bag like `(any+assertEquals+assertTrue+every+listOf+verify)+`.
|
||
|
|
|
||
|
|
This doesn't capture the *ordering* of calls or the distinct methodological styles present in the codebase.
|
||
|
|
|
||
|
|
## Decision
|
||
|
|
|
||
|
|
Group methods by shared n-gram (default: 3-gram) call patterns *before* running inference.
|
||
|
|
|
||
|
|
Pipeline: `preprocess_by_method` → `frequency_filter` → `cluster_methods` → per-cluster `infer_ensemble`
|
||
|
|
|
||
|
|
The clustering algorithm:
|
||
|
|
1. Extract call tokens from each method sequence (filter to `function`, `reference.call`, `reference.class` captures).
|
||
|
|
2. Build an n-gram index: for each method, for each sliding window of size N, record the n-gram.
|
||
|
|
3. Sort n-grams by frequency (most shared first).
|
||
|
|
4. Assign each method to the largest matching cluster, then remove assigned methods.
|
||
|
|
5. Remaining unclustered methods go to `(other)`.
|
||
|
|
|
||
|
|
This produces 10-30 clusters for a typical test suite, each with 3-100+ methods sharing a call-order pattern.
|
||
|
|
|
||
|
|
## Consequences
|
||
|
|
|
||
|
|
**Positive:**
|
||
|
|
- iDRegEx and kOREInference now produce ordered grammars (e.g. `every+.assertEquals.verify+.any?`) because small, focused clusters have enough signal.
|
||
|
|
- Each cluster reveals a distinct *methodological style* in the codebase (mockist TDD vs data-driven testing vs pure assertion).
|
||
|
|
- The `(other)` cluster still captures the full vocabulary bag for diverse methods.
|
||
|
|
|
||
|
|
**Negative:**
|
||
|
|
- Clustering adds a hyperparameter (`ngram_size`, default 3). Wrong value can produce too many tiny clusters or one giant cluster.
|
||
|
|
- `min_cluster_size` (default 3) filters out tiny but potentially interesting patterns.
|
||
|
|
- Methods in `(other)` never get ordered grammar inference — just vocabulary.
|
||
|
|
|
||
|
|
## Alternatives Considered
|
||
|
|
|
||
|
|
- **Infer on all methods (no clustering)**: Produces flat vocabulary only. CRX works at 100% coverage, but iDRegEx and kORE fail on diverse inputs.
|
||
|
|
- **Infer per file**: Too fine-grained — most files have 1-5 methods, not enough for inference.
|
||
|
|
- **Infer per directory**: Better, but directories mix unrelated conventions (setup/teardown vs actual test logic).
|