Epic: Type System Expansion

[unclesp1d3r]

Summary

Expand the type system from 4 basic types to full coverage of GNU file's magic format type specifiers.

Current State

Only 4 of 33+ types implemented: byte, short, long, string

Tracking

v0.2.0 - Core Types

• Parser: implement quad (64-bit integer) type with endian variants #36 - Quad (64-bit integer) with endian variants HIGH
• Parser: implement float and double types with endian variants #40 - Float and double with endian variants
• Parser: implement date and timestamp types #41 - Date and timestamp types
• Parser: implement pstring (Pascal string) type #43 - Pstring (Pascal string)

v0.3.0 - Advanced Types

• Parser: implement regex and search types #39 - Regex and search types HIGH
• Parser: implement default, clear, name, use, and indirect meta-types #42 - Meta-types: default, clear, name, use, indirect HIGH
• lestring16/bestring16: UCS-2 string types #232 - lestring16/bestring16 (UCS-2 string types) HIGH (blocker for loading /usr/share/file/magic/filesystems)
• Implement string-type flag semantics (/c /C /w /W /B /b /t /T) #234 - String-type flag semantics (/c /C /w /W /B /b /t /T) — parser landed in fix: load and correctly evaluate /usr/share/file/magic/filesystems and adjacent magic files #233; semantics deferred
• Implement search-type flag semantics (/s start-anchor, /b binary, etc.) #235 - Search-type flag semantics (/s start-anchor, /b binary, etc.) — parser landed in fix: load and correctly evaluate /usr/share/file/magic/filesystems and adjacent magic files #233; semantics deferred
• Implement ID3 variable-byte decoding for indirect pointer specifiers (i / I) #237 - ID3 synchsafe decoding for i / I indirect pointer specifiers — placeholder Long mapping landed in fix: load and correctly evaluate /usr/share/file/magic/filesystems and adjacent magic files #233

Success Criteria

All types needed to parse system magic databases (/usr/share/file/magic/) are supported.

Priority Order

1. Quad (needed for modern binary formats)
2. Regex/search (needed for text detection - JSON, scripts, XML)
3. Meta-types (needed for rule composition and indirect format detection)
4. Date types (archives, filesystem images)
5. Float/double (scientific data, image metadata)
6. Pstring (rare, but needed for full compat)
7. UCS-2 strings (lestring16/bestring16, NTFS/FAT/Windows formats)
8. String/search flag semantics (case-insensitive, whitespace, /s anchor) — common in shebang and scan rules
9. ID3 synchsafe (i/I) — needed for accurate MP3 inner-stream detection

[traycerai]

Warning

Ticket Assist will be discontinued on May 1, 2026. After that date, the feature will no longer be available. We suggest installing the Traycer IDE Extension for continued AI-powered, spec-driven development. Thank you for choosing Traycer!

Plan

Observations

The codebase is already significantly more advanced than the epic's "Current State" description suggests. Reviewing the actual code:

• Already fully implemented: Byte, Short, Long, Quad (all endian/signed variants), Float, Double, Date, QDate, String, PString — all with parser, evaluator, codegen, strength, and output support.
• Genuinely missing: Regex, Search, and the meta-types (default, clear, name, use, indirect).
• The regex crate is already a dev-dependency but not a runtime dependency; regex::bytes is not yet available at runtime.

Approach

The plan addresses the two remaining open sub-issues: #39 (Regex + Search types) and #42 (Meta-types). These are the only items in the epic that are not yet implemented. Each follows the established pattern documented in AGENTS.md: extend TypeKind → update parser → implement evaluator → update codegen/strength/output.

---

Implementation Plan

Phase 1 — Regex and Search Types (#39)

Step 1 — Add regex as a runtime dependency

In file:Cargo.toml, add regex with the bytes feature to [dependencies] (it is currently only a dev-dependency). This enables binary-safe regex matching at runtime without unsafe code.

regex = { version = "1", features = ["bytes"] }

Step 2 — Extend TypeKind in file:src/parser/ast.rs

Add two new variants after PString:

• Regex { case_insensitive: bool, line_count: Option<u32> } — matches a regex pattern against file content starting at the given offset. line_count limits the search to N lines (GNU file regex/N syntax). case_insensitive maps to the /c flag.
• Search { max_offset: Option<u32>, flags: SearchFlags } — searches for a byte sequence within a range. max_offset is the /N range limit. flags captures /c (case-insensitive) and /b (binary) modifiers.

Add a SearchFlags struct (or bitfield-style struct with bool fields) in ast.rs alongside the new variants. Update bit_width() to return None for both new variants (they are string-like).

Checklist note (GOTCHAS.md §2.1): TypeKind has exhaustive matches in 10+ files. Track all sites below.

Step 3 — Update parse_type_keyword and type_keyword_to_kind in file:src/parser/types.rs

• In parse_type_keyword: add tag("regex") and tag("search") to the alt chain (in a new alt group to stay within nom's 21-branch limit).
• In type_keyword_to_kind: add match arms for "regex" → TypeKind::Regex { case_insensitive: false, line_count: None } and "search" → TypeKind::Search { max_offset: None, flags: SearchFlags::default() } (defaults; suffix parsing is handled by the grammar layer).

Step 4 — Add suffix parsing in file:src/parser/grammar/mod.rs

Following the existing pstring suffix pattern (/B, /H, etc.), add a parse_regex_suffix function that:

• Parses optional /c (case-insensitive), /l (line-anchored), and /N (line count as integer) flags after regex.
• Parses optional /c, /b, /N (range) flags after search.
• Updates the TypeKind returned by parse_type_and_operator for these two types.

Step 5 — Implement evaluator reading in file:src/evaluator/types/

Create file:src/evaluator/types/regex.rs with:

• read_regex(buffer, offset, pattern_bytes, case_insensitive, line_count) -> Result<Value, TypeReadError> — builds a regex::bytes::Regex from the pattern bytes, applies it to &buffer[offset..] (limited to line_count lines if set), returns Value::String of the matched text on success, or Ok(Value::String(String::new())) on no-match (the operator comparison handles the actual pass/fail).
• read_search(buffer, offset, pattern_bytes, max_offset, flags) -> Result<Value, TypeReadError> — performs a bounded byte-sequence search using memchr (already a dependency) or regex::bytes for case-insensitive search.

Add mod regex; and pub use regex::{read_regex, read_search}; in file:src/evaluator/types/mod.rs.

Extend read_typed_value in file:src/evaluator/types/mod.rs with match arms for TypeKind::Regex and TypeKind::Search. Note: the pattern to match against comes from rule.value (a Value::Bytes or Value::String), not from the type itself — the evaluator already passes rule.value as the expected value. The read function should return the matched region as Value::String or Value::Bytes.

Step 6 — Update coerce_value_to_type in file:src/evaluator/types/mod.rs

Add catch-all arms for TypeKind::Regex and TypeKind::Search that return the value unchanged (no numeric coercion needed).

Step 7 — Update serialize_type_kind in file:src/parser/codegen.rs

Add match arms for TypeKind::Regex and TypeKind::Search that emit the correct Rust struct literal syntax. Also update the use crate::parser::ast::{...} import line in generate_builtin_rules to include SearchFlags if it becomes a public type.

Step 8 — Update calculate_default_strength in file:src/evaluator/strength.rs

Add match arms for TypeKind::Regex and TypeKind::Search in the type contribution block. Regex is pattern-based (similar to string, assign ~18); Search is range-limited (assign ~15).

Step 9 — Update bit_width in file:src/parser/ast.rs

Ensure the bit_width() match returns None for both new variants (they have no fixed width).

Step 10 — Update format_value_as_hex in file:src/output/json.rs and length calculation in file:src/output/mod.rs

Both files have exhaustive Value matches. Since no new Value variants are added (regex/search results are Value::String or Value::Bytes), no changes are needed here — but verify the TypeKind match in from_evaluator_match (the bit_width() call) handles None correctly for the new types (it already does via map_or(0, ...)).

Step 11 — Update property tests in file:tests/property_tests.rs

Add TypeKind::Regex and TypeKind::Search to the arb_type_kind() strategy (or equivalent arbitrary generator) so property tests cover the new variants.

---

Phase 2 — Meta-types: default, clear, name, use, indirect (#42)

Meta-types are control-flow directives, not data-reading types. The cleanest approach (matching the existing architecture) is to represent them as additional TypeKind variants that the evaluator handles specially, rather than a separate enum — this avoids changing MagicRule's structure.

Step 12 — Extend TypeKind with meta-type variants in file:src/parser/ast.rs

Add:

• Default — fallback rule; matches when no sibling at the same level has matched.
• Clear — resets match state for the current level.
• Name { label: String } — defines a named subroutine.
• Use { label: String } — invokes a named subroutine by label.
• Indirect — recursively applies magic rules at the resolved offset.

bit_width() returns None for all five.

Step 13 — Update parser in file:src/parser/types.rs and file:src/parser/grammar/mod.rs

• parse_type_keyword: add tag("default"), tag("clear"), tag("name"), tag("use"), tag("indirect").
• type_keyword_to_kind: add match arms returning the new variants with default fields.
• In grammar/mod.rs, for name and use, parse the label string that follows the type keyword (it appears in the value field of the rule in GNU magic files — e.g., 0 name my_label or 0 use my_label). The grammar layer should capture this and store it in the TypeKind::Name/TypeKind::Use variant's label field rather than in rule.value.

Step 14 — Implement evaluator logic in file:src/evaluator/engine/mod.rs

The evaluation engine (evaluate_rules and evaluate_single_rule) needs to handle meta-types:

• TypeKind::Default: In evaluate_rules, track whether any sibling rule at the current level has matched. If none have, evaluate the Default rule unconditionally (it always "matches"). This requires threading a sibling_matched: bool flag through the loop.
• TypeKind::Clear: Reset the sibling-matched tracking flag for the current level. Does not produce a RuleMatch.
• TypeKind::Name: Register the rule's children under the label in a HashMap<String, &[MagicRule]> passed through the evaluation context. Does not produce a RuleMatch itself.
• TypeKind::Use: Look up the label in the named-rule registry and recursively evaluate those rules at the current offset.
• TypeKind::Indirect: Read a pointer value at the resolved offset (using the rule's type width), then recursively call evaluate_rules with the pointer value as the new base offset.

Add a named_rules: HashMap<String, Vec<MagicRule>> field to EvaluationContext in file:src/evaluator/mod.rs to support name/use. Populate it during a pre-pass over the top-level rules before evaluation begins (in evaluate_rules_with_config).

Step 15 — Update read_typed_value in file:src/evaluator/types/mod.rs

Add match arms for all five meta-type variants. Since they don't read bytes in the traditional sense, return TypeReadError::UnsupportedType for Name, Clear, and Default (the engine handles them before calling read_typed_value), and implement actual byte-reading for Indirect (reads a pointer using the inner type).

Step 16 — Update serialize_type_kind in file:src/parser/codegen.rs

Add match arms for all five new variants. Name and Use must serialize the label: String field.

Step 17 — Update calculate_default_strength in file:src/evaluator/strength.rs

Add match arms for the five meta-type variants. Assign low strength values (e.g., 1) since they are control-flow, not data-matching rules.

Step 18 — Update bit_width in file:src/parser/ast.rs

Ensure all five new variants return None.

---

Cross-cutting: Exhaustive Match Sites

The following files require updates for every new TypeKind variant added (per GOTCHAS.md §2.1):

File	What to update
file:src/parser/ast.rs	bit_width() match
file:src/parser/types.rs	parse_type_keyword, type_keyword_to_kind
file:src/parser/grammar/mod.rs	parse_type_and_operator
file:src/parser/codegen.rs	serialize_type_kind
file:src/evaluator/types/mod.rs	read_typed_value, coerce_value_to_type
file:src/evaluator/strength.rs	calculate_default_strength type match
file:tests/property_tests.rs	arb_type_kind() or equivalent

The output/mod.rs and output/json.rs exhaustive matches are on Value, not TypeKind, so they are unaffected unless new Value variants are added (none are needed here).

sequenceDiagram
    participant MF as Magic File
    participant P as Parser (types.rs + grammar/mod.rs)
    participant AST as TypeKind (ast.rs)
    participant E as Evaluator Engine (engine/mod.rs)
    participant T as Type Reader (types/regex.rs)
    participant O as Output

    MF->>P: "0 regex/c pattern"
    P->>AST: TypeKind::Regex { case_insensitive: true, .. }
    AST->>E: evaluate_single_rule(rule, buffer)
    E->>T: read_regex(buffer, offset, pattern, flags)
    T-->>E: Ok(Value::String(matched))
    E->>E: apply_operator(Equal, matched, expected)
    E-->>O: RuleMatch { value: Value::String(..) }

Loading

Import In IDE

🤖 Prompt for AI Agents

## Observations

The codebase is already significantly more advanced than the epic's "Current State" description suggests. Reviewing the actual code:

- **Already fully implemented**: `Byte`, `Short`, `Long`, `Quad` (all endian/signed variants), `Float`, `Double`, `Date`, `QDate`, `String`, `PString` — all with parser, evaluator, codegen, strength, and output support.
- **Genuinely missing**: `Regex`, `Search`, and the meta-types (`default`, `clear`, `name`, `use`, `indirect`).
- The `regex` crate is already a dev-dependency but **not** a runtime dependency; `regex::bytes` is not yet available at runtime.

## Approach

The plan addresses the two remaining open sub-issues: **#39** (Regex + Search types) and **#42** (Meta-types). These are the only items in the epic that are not yet implemented. Each follows the established pattern documented in `AGENTS.md`: extend `TypeKind` → update parser → implement evaluator → update codegen/strength/output.

---

## Implementation Plan

### Phase 1 — Regex and Search Types (#39)

#### Step 1 — Add `regex` as a runtime dependency

In `file:Cargo.toml`, add `regex` with the `bytes` feature to `[dependencies]` (it is currently only a dev-dependency). This enables binary-safe regex matching at runtime without `unsafe` code.

```
regex = { version = "1", features = ["bytes"] }
```

#### Step 2 — Extend `TypeKind` in `file:src/parser/ast.rs`

Add two new variants after `PString`:

- `Regex { case_insensitive: bool, line_count: Option<u32> }` — matches a regex pattern against file content starting at the given offset. `line_count` limits the search to N lines (GNU file `regex/N` syntax). `case_insensitive` maps to the `/c` flag.
- `Search { max_offset: Option<u32>, flags: SearchFlags }` — searches for a byte sequence within a range. `max_offset` is the `/N` range limit. `flags` captures `/c` (case-insensitive) and `/b` (binary) modifiers.

Add a `SearchFlags` struct (or bitfield-style struct with `bool` fields) in `ast.rs` alongside the new variants. Update `bit_width()` to return `None` for both new variants (they are string-like).

> **Checklist note (GOTCHAS.md §2.1):** `TypeKind` has exhaustive matches in 10+ files. Track all sites below.

#### Step 3 — Update `parse_type_keyword` and `type_keyword_to_kind` in `file:src/parser/types.rs`

- In `parse_type_keyword`: add `tag("regex")` and `tag("search")` to the `alt` chain (in a new `alt` group to stay within nom's 21-branch limit).
- In `type_keyword_to_kind`: add match arms for `"regex"` → `TypeKind::Regex { case_insensitive: false, line_count: None }` and `"search"` → `TypeKind::Search { max_offset: None, flags: SearchFlags::default() }` (defaults; suffix parsing is handled by the grammar layer).

#### Step 4 — Add suffix parsing in `file:src/parser/grammar/mod.rs`

Following the existing `pstring` suffix pattern (`/B`, `/H`, etc.), add a `parse_regex_suffix` function that:
- Parses optional `/c` (case-insensitive), `/l` (line-anchored), and `/N` (line count as integer) flags after `regex`.
- Parses optional `/c`, `/b`, `/N` (range) flags after `search`.
- Updates the `TypeKind` returned by `parse_type_and_operator` for these two types.

#### Step 5 — Implement evaluator reading in `file:src/evaluator/types/`

Create `file:src/evaluator/types/regex.rs` with:

- `read_regex(buffer, offset, pattern_bytes, case_insensitive, line_count) -> Result<Value, TypeReadError>` — builds a `regex::bytes::Regex` from the pattern bytes, applies it to `&buffer[offset..]` (limited to `line_count` lines if set), returns `Value::String` of the matched text on success, or `Ok(Value::String(String::new()))` on no-match (the operator comparison handles the actual pass/fail).
- `read_search(buffer, offset, pattern_bytes, max_offset, flags) -> Result<Value, TypeReadError>` — performs a bounded byte-sequence search using `memchr` (already a dependency) or `regex::bytes` for case-insensitive search.

Add `mod regex;` and `pub use regex::{read_regex, read_search};` in `file:src/evaluator/types/mod.rs`.

Extend `read_typed_value` in `file:src/evaluator/types/mod.rs` with match arms for `TypeKind::Regex` and `TypeKind::Search`. Note: the pattern to match against comes from `rule.value` (a `Value::Bytes` or `Value::String`), not from the type itself — the evaluator already passes `rule.value` as the expected value. The read function should return the matched region as `Value::String` or `Value::Bytes`.

#### Step 6 — Update `coerce_value_to_type` in `file:src/evaluator/types/mod.rs`

Add catch-all arms for `TypeKind::Regex` and `TypeKind::Search` that return the value unchanged (no numeric coercion needed).

#### Step 7 — Update `serialize_type_kind` in `file:src/parser/codegen.rs`

Add match arms for `TypeKind::Regex` and `TypeKind::Search` that emit the correct Rust struct literal syntax. Also update the `use crate::parser::ast::{...}` import line in `generate_builtin_rules` to include `SearchFlags` if it becomes a public type.

#### Step 8 — Update `calculate_default_strength` in `file:src/evaluator/strength.rs`

Add match arms for `TypeKind::Regex` and `TypeKind::Search` in the type contribution block. Regex is pattern-based (similar to string, assign ~18); Search is range-limited (assign ~15).

#### Step 9 — Update `bit_width` in `file:src/parser/ast.rs`

Ensure the `bit_width()` match returns `None` for both new variants (they have no fixed width).

#### Step 10 — Update `format_value_as_hex` in `file:src/output/json.rs` and length calculation in `file:src/output/mod.rs`

Both files have exhaustive `Value` matches. Since no new `Value` variants are added (regex/search results are `Value::String` or `Value::Bytes`), no changes are needed here — but verify the `TypeKind` match in `from_evaluator_match` (the `bit_width()` call) handles `None` correctly for the new types (it already does via `map_or(0, ...)`).

#### Step 11 — Update property tests in `file:tests/property_tests.rs`

Add `TypeKind::Regex` and `TypeKind::Search` to the `arb_type_kind()` strategy (or equivalent arbitrary generator) so property tests cover the new variants.

---

### Phase 2 — Meta-types: default, clear, name, use, indirect (#42)

Meta-types are control-flow directives, not data-reading types. The cleanest approach (matching the existing architecture) is to represent them as additional `TypeKind` variants that the evaluator handles specially, rather than a separate enum — this avoids changing `MagicRule`'s structure.

#### Step 12 — Extend `TypeKind` with meta-type variants in `file:src/parser/ast.rs`

Add:
- `Default` — fallback rule; matches when no sibling at the same level has matched.
- `Clear` — resets match state for the current level.
- `Name { label: String }` — defines a named subroutine.
- `Use { label: String }` — invokes a named subroutine by label.
- `Indirect` — recursively applies magic rules at the resolved offset.

`bit_width()` returns `None` for all five.

#### Step 13 — Update parser in `file:src/parser/types.rs` and `file:src/parser/grammar/mod.rs`

- `parse_type_keyword`: add `tag("default")`, `tag("clear")`, `tag("name")`, `tag("use")`, `tag("indirect")`.
- `type_keyword_to_kind`: add match arms returning the new variants with default fields.
- In `grammar/mod.rs`, for `name` and `use`, parse the label string that follows the type keyword (it appears in the value field of the rule in GNU magic files — e.g., `0 name my_label` or `0 use my_label`). The grammar layer should capture this and store it in the `TypeKind::Name`/`TypeKind::Use` variant's `label` field rather than in `rule.value`.

#### Step 14 — Implement evaluator logic in `file:src/evaluator/engine/mod.rs`

The evaluation engine (`evaluate_rules` and `evaluate_single_rule`) needs to handle meta-types:

- **`TypeKind::Default`**: In `evaluate_rules`, track whether any sibling rule at the current level has matched. If none have, evaluate the `Default` rule unconditionally (it always "matches"). This requires threading a `sibling_matched: bool` flag through the loop.
- **`TypeKind::Clear`**: Reset the sibling-matched tracking flag for the current level. Does not produce a `RuleMatch`.
- **`TypeKind::Name`**: Register the rule's children under the label in a `HashMap<String, &[MagicRule]>` passed through the evaluation context. Does not produce a `RuleMatch` itself.
- **`TypeKind::Use`**: Look up the label in the named-rule registry and recursively evaluate those rules at the current offset.
- **`TypeKind::Indirect`**: Read a pointer value at the resolved offset (using the rule's type width), then recursively call `evaluate_rules` with the pointer value as the new base offset.

Add a `named_rules: HashMap<String, Vec<MagicRule>>` field to `EvaluationContext` in `file:src/evaluator/mod.rs` to support `name`/`use`. Populate it during a pre-pass over the top-level rules before evaluation begins (in `evaluate_rules_with_config`).

#### Step 15 — Update `read_typed_value` in `file:src/evaluator/types/mod.rs`

Add match arms for all five meta-type variants. Since they don't read bytes in the traditional sense, return `TypeReadError::UnsupportedType` for `Name`, `Clear`, and `Default` (the engine handles them before calling `read_typed_value`), and implement actual byte-reading for `Indirect` (reads a pointer using the inner type).

#### Step 16 — Update `serialize_type_kind` in `file:src/parser/codegen.rs`

Add match arms for all five new variants. `Name` and `Use` must serialize the `label: String` field.

#### Step 17 — Update `calculate_default_strength` in `file:src/evaluator/strength.rs`

Add match arms for the five meta-type variants. Assign low strength values (e.g., 1) since they are control-flow, not data-matching rules.

#### Step 18 — Update `bit_width` in `file:src/parser/ast.rs`

Ensure all five new variants return `None`.

---

### Cross-cutting: Exhaustive Match Sites

The following files require updates for **every** new `TypeKind` variant added (per GOTCHAS.md §2.1):

| File | What to update |
|---|---|
| `file:src/parser/ast.rs` | `bit_width()` match |
| `file:src/parser/types.rs` | `parse_type_keyword`, `type_keyword_to_kind` |
| `file:src/parser/grammar/mod.rs` | `parse_type_and_operator` |
| `file:src/parser/codegen.rs` | `serialize_type_kind` |
| `file:src/evaluator/types/mod.rs` | `read_typed_value`, `coerce_value_to_type` |
| `file:src/evaluator/strength.rs` | `calculate_default_strength` type match |
| `file:tests/property_tests.rs` | `arb_type_kind()` or equivalent |

The `output/mod.rs` and `output/json.rs` exhaustive matches are on `Value`, not `TypeKind`, so they are unaffected unless new `Value` variants are added (none are needed here).

```mermaid
sequenceDiagram
    participant MF as Magic File
    participant P as Parser (types.rs + grammar/mod.rs)
    participant AST as TypeKind (ast.rs)
    participant E as Evaluator Engine (engine/mod.rs)
    participant T as Type Reader (types/regex.rs)
    participant O as Output

    MF->>P: "0 regex/c pattern"
    P->>AST: TypeKind::Regex { case_insensitive: true, .. }
    AST->>E: evaluate_single_rule(rule, buffer)
    E->>T: read_regex(buffer, offset, pattern, flags)
    T-->>E: Ok(Value::String(matched))
    E->>E: apply_operator(Equal, matched, expected)
    E-->>O: RuleMatch { value: Value::String(..) }
```

---

Execution Information

Branch: main
Commit: db661cb

---

💡 Tips

Supported Commands (Inside Comments)

• Use @traycerai generate to iterate on the previous version of the implementation plan.

Supported Commands (Inside Description)

• Add @traycerai ignore anywhere in the ticket description to prevent this ticket from being processed.
• Add @traycerai branch:<branch-name> anywhere in the ticket description to specify the target branch for the implementation plan.

Community

• Join our Discord Community to get help, request features, and share feedback.
• Follow us on X/Twitter for updates and announcements.