Parser: implement bitwise XOR (^), NOT (~), and any-value (x) operators

[unclesp1d3r]

Summary

Implement the remaining bitwise and special operators: ^ (XOR), ~ (NOT/complement), and x (match any value).

Context

GNU file's magic format supports these operators for bit-level format detection:

• ^ (XOR) - Used for flag toggling and bitmask checks
• ~ (NOT/complement) - Used for inverted bit patterns
• x (any value) - Matches any value at an offset (used to unconditionally output text, often in child rules)

Current state: Only =, !=, &, and &mask are implemented.

Acceptance Criteria

• Parser recognizes ^, ~, x operators
• Operator enum extended with BitwiseXor, BitwiseNot, AnyValue variants
• Evaluator implements XOR and NOT logic for numeric types
• x operator always returns true (matches any value)
• Unit tests for each operator
• All existing tests continue to pass

Impact

MEDIUM - x (any value) is particularly common in magic files for unconditional child rule output. XOR and NOT are less common but needed for full compatibility.

Files to Modify

• src/parser/ast.rs - Extend Operator enum
• src/parser/grammar.rs - Parse new operators
• src/evaluator/operators.rs - Implement logic

References

• GNU file magic(5) man page
• Epic Epic: libmagic-rs Phase 1 MVP #24

[traycerai]

Plan

Observations

The codebase has a well-structured operator implementation pattern. The Operator enum in file:src/parser/ast.rs currently supports Equal, NotEqual, BitwiseAnd, and BitwiseAndMask(u64). Operator parsing in file:src/parser/grammar.rs uses nom's tag() combinator with careful multi-character operator handling. The evaluator in file:src/evaluator/operators.rs uses a match-based dispatcher pattern with dedicated helper functions for complex operations. The x (any-value) operator is particularly important as it's commonly used in magic files for unconditional child rule output.

Approach

Extend the existing operator infrastructure by adding three new variants to the Operator enum, implementing their parsing logic following the established pattern in parse_operator, and adding evaluation logic in apply_operator. The XOR and NOT operators will follow the same numeric-only pattern as BitwiseAnd, while the x operator will be a special case that always returns true regardless of value types. This maintains consistency with the existing codebase architecture while achieving full GNU file magic format compatibility.

Implementation Steps

1. Extend the Operator Enum

File: file:src/parser/ast.rs

Add three new variants to the Operator enum (around line 114):

pub enum Operator {
    Equal,
    NotEqual,
    BitwiseAnd,
    BitwiseAndMask(u64),
    BitwiseXor,      // New: XOR operator (^)
    BitwiseNot,      // New: NOT/complement operator (~)
    AnyValue,        // New: Match any value (x)
}

Update the operator tests section (around line 590) to include the new variants in serialization and comparison tests.

2. Implement Operator Parsing

File: file:src/parser/grammar.rs

Extend the parse_operator function (around line 163) to recognize the new operators. Add parsing logic after the existing operators but before the final error return:

• Parse ^ for BitwiseXor - single character, check it's not followed by another ^
• Parse ~ for BitwiseNot - single character, check it's not followed by another ~
• Parse x for AnyValue - single character, ensure it's not part of a hex number (check surrounding context)

Follow the existing pattern: use tag() to match the operator symbol, verify no duplicate characters follow, consume trailing whitespace with multispace0, and return the appropriate Operator variant.

Add comprehensive unit tests in the test module (around line 768) following the existing pattern:

• test_parse_operator_bitwise_xor - Test ^ with and without whitespace
• test_parse_operator_bitwise_not - Test ~ with and without whitespace
• test_parse_operator_any_value - Test x with and without whitespace
• Test with remaining input to ensure proper parsing boundaries
• Test edge cases like ^^, ~~, and x in different contexts

3. Implement Operator Evaluation Logic

File: file:src/evaluator/operators.rs

Add three new helper functions before apply_operator (around line 165):

apply_bitwise_xor (similar to apply_bitwise_and at line 109):

• Accept two Value references
• Match on value types: (Value::Uint, Value::Uint), (Value::Int, Value::Int), cross-type integer coercion (Value::Uint, Value::Int) and (Value::Int, Value::Uint)
• Perform XOR operation: left ^ right
• Return true if result is non-zero, false otherwise
• Return false for non-numeric types (Bytes, String)

apply_bitwise_not:

• Accept one Value reference (the left/file value)
• Match on value type: Value::Uint or Value::Int
• Perform NOT operation: !value (bitwise complement)
• Compare the result with the right value using apply_equal
• Return false for non-numeric types

apply_any_value:

• Accept two Value references (for consistency with other operators)
• Always return true regardless of value types or content
• This operator unconditionally matches, used for child rules that always execute

Extend the apply_operator match statement (around line 218) to handle the new variants:

• Operator::BitwiseXor => apply_bitwise_xor(left, right)
• Operator::BitwiseNot => apply_bitwise_not(left, right)
• Operator::AnyValue => apply_any_value(left, right)

Add comprehensive unit tests in the test module (starting around line 240):

For BitwiseXor:

• test_apply_bitwise_xor_uint - Test XOR with unsigned integers
• test_apply_bitwise_xor_int - Test XOR with signed integers
• test_apply_bitwise_xor_cross_type - Test Uint vs Int coercion
• test_apply_bitwise_xor_zero - Test XOR with zero values
• test_apply_bitwise_xor_same_value - Test XOR of identical values (should be zero/false)
• test_apply_bitwise_xor_non_numeric - Test rejection of Bytes/String types

For BitwiseNot:

• test_apply_bitwise_not_uint - Test NOT with unsigned integers
• test_apply_bitwise_not_int - Test NOT with signed integers
• test_apply_bitwise_not_all_bits_set - Test NOT of 0xFF...
• test_apply_bitwise_not_non_numeric - Test rejection of Bytes/String types

For AnyValue:

• test_apply_any_value_uint - Test with unsigned integers
• test_apply_any_value_int - Test with signed integers
• test_apply_any_value_bytes - Test with byte sequences
• test_apply_any_value_string - Test with strings
• test_apply_any_value_different_types - Test cross-type always returns true
• test_apply_any_value_empty - Test with empty values

4. Update Documentation

File: file:src/evaluator/operators.rs

Update the module documentation (lines 1-6) to mention the new operators: XOR, NOT, and any-value matching.

Update the apply_operator function documentation (around line 166) to include examples of the new operators in the docstring.

File: file:docs/MAGIC_FORMAT.md

The XOR operator is already documented (line 198). Add documentation for the NOT operator in the Operators section (around line 187):

| `~` | Bitwise NOT | `4 byte ~0xff` |

Ensure the x (any value) documentation (line 255) is clear about its unconditional matching behavior.

5. Integration Testing

Verify all existing tests continue to pass:

• Run cargo test to ensure no regressions
• Verify operator parsing tests in file:src/parser/grammar.rs
• Verify operator evaluation tests in file:src/evaluator/operators.rs
• Check AST serialization tests in file:src/parser/ast.rs

The new operators should integrate seamlessly with the existing evaluation engine without requiring changes to file:src/evaluator/mod.rs or other components.

Sequence Diagram

sequenceDiagram
    participant Parser as parse_operator
    participant AST as Operator Enum
    participant Evaluator as apply_operator
    participant Helper as apply_bitwise_xor/not/any

    Parser->>Parser: Recognize ^ / ~ / x symbol
    Parser->>AST: Create BitwiseXor/Not/AnyValue
    AST->>Evaluator: Pass operator to evaluator
    Evaluator->>Evaluator: Match on operator variant
    Evaluator->>Helper: Dispatch to helper function
    Helper->>Helper: Perform operation on values
    Helper->>Evaluator: Return boolean result
    Evaluator->>Evaluator: Continue rule evaluation

Loading

Import In IDE

🤖 Prompt for AI Agents

## Observations

The codebase has a well-structured operator implementation pattern. The `Operator` enum in `file:src/parser/ast.rs` currently supports `Equal`, `NotEqual`, `BitwiseAnd`, and `BitwiseAndMask(u64)`. Operator parsing in `file:src/parser/grammar.rs` uses nom's `tag()` combinator with careful multi-character operator handling. The evaluator in `file:src/evaluator/operators.rs` uses a match-based dispatcher pattern with dedicated helper functions for complex operations. The `x` (any-value) operator is particularly important as it's commonly used in magic files for unconditional child rule output.

## Approach

Extend the existing operator infrastructure by adding three new variants to the `Operator` enum, implementing their parsing logic following the established pattern in `parse_operator`, and adding evaluation logic in `apply_operator`. The XOR and NOT operators will follow the same numeric-only pattern as `BitwiseAnd`, while the `x` operator will be a special case that always returns true regardless of value types. This maintains consistency with the existing codebase architecture while achieving full GNU file magic format compatibility.

## Implementation Steps

### 1. Extend the Operator Enum

**File**: `file:src/parser/ast.rs`

Add three new variants to the `Operator` enum (around line 114):

```rust
pub enum Operator {
    Equal,
    NotEqual,
    BitwiseAnd,
    BitwiseAndMask(u64),
    BitwiseXor,      // New: XOR operator (^)
    BitwiseNot,      // New: NOT/complement operator (~)
    AnyValue,        // New: Match any value (x)
}
```

Update the operator tests section (around line 590) to include the new variants in serialization and comparison tests.

### 2. Implement Operator Parsing

**File**: `file:src/parser/grammar.rs`

Extend the `parse_operator` function (around line 163) to recognize the new operators. Add parsing logic after the existing operators but before the final error return:

- Parse `^` for `BitwiseXor` - single character, check it's not followed by another `^`
- Parse `~` for `BitwiseNot` - single character, check it's not followed by another `~`  
- Parse `x` for `AnyValue` - single character, ensure it's not part of a hex number (check surrounding context)

Follow the existing pattern: use `tag()` to match the operator symbol, verify no duplicate characters follow, consume trailing whitespace with `multispace0`, and return the appropriate `Operator` variant.

Add comprehensive unit tests in the test module (around line 768) following the existing pattern:
- `test_parse_operator_bitwise_xor` - Test `^` with and without whitespace
- `test_parse_operator_bitwise_not` - Test `~` with and without whitespace
- `test_parse_operator_any_value` - Test `x` with and without whitespace
- Test with remaining input to ensure proper parsing boundaries
- Test edge cases like `^^`, `~~`, and `x` in different contexts

### 3. Implement Operator Evaluation Logic

**File**: `file:src/evaluator/operators.rs`

Add three new helper functions before `apply_operator` (around line 165):

**`apply_bitwise_xor`** (similar to `apply_bitwise_and` at line 109):
- Accept two `Value` references
- Match on value types: `(Value::Uint, Value::Uint)`, `(Value::Int, Value::Int)`, cross-type integer coercion `(Value::Uint, Value::Int)` and `(Value::Int, Value::Uint)`
- Perform XOR operation: `left ^ right`
- Return `true` if result is non-zero, `false` otherwise
- Return `false` for non-numeric types (Bytes, String)

**`apply_bitwise_not`**:
- Accept one `Value` reference (the left/file value)
- Match on value type: `Value::Uint` or `Value::Int`
- Perform NOT operation: `!value` (bitwise complement)
- Compare the result with the right value using `apply_equal`
- Return `false` for non-numeric types

**`apply_any_value`**:
- Accept two `Value` references (for consistency with other operators)
- Always return `true` regardless of value types or content
- This operator unconditionally matches, used for child rules that always execute

Extend the `apply_operator` match statement (around line 218) to handle the new variants:
- `Operator::BitwiseXor => apply_bitwise_xor(left, right)`
- `Operator::BitwiseNot => apply_bitwise_not(left, right)`
- `Operator::AnyValue => apply_any_value(left, right)`

Add comprehensive unit tests in the test module (starting around line 240):

**For BitwiseXor**:
- `test_apply_bitwise_xor_uint` - Test XOR with unsigned integers
- `test_apply_bitwise_xor_int` - Test XOR with signed integers  
- `test_apply_bitwise_xor_cross_type` - Test Uint vs Int coercion
- `test_apply_bitwise_xor_zero` - Test XOR with zero values
- `test_apply_bitwise_xor_same_value` - Test XOR of identical values (should be zero/false)
- `test_apply_bitwise_xor_non_numeric` - Test rejection of Bytes/String types

**For BitwiseNot**:
- `test_apply_bitwise_not_uint` - Test NOT with unsigned integers
- `test_apply_bitwise_not_int` - Test NOT with signed integers
- `test_apply_bitwise_not_all_bits_set` - Test NOT of 0xFF...
- `test_apply_bitwise_not_non_numeric` - Test rejection of Bytes/String types

**For AnyValue**:
- `test_apply_any_value_uint` - Test with unsigned integers
- `test_apply_any_value_int` - Test with signed integers
- `test_apply_any_value_bytes` - Test with byte sequences
- `test_apply_any_value_string` - Test with strings
- `test_apply_any_value_different_types` - Test cross-type always returns true
- `test_apply_any_value_empty` - Test with empty values

### 4. Update Documentation

**File**: `file:src/evaluator/operators.rs`

Update the module documentation (lines 1-6) to mention the new operators: XOR, NOT, and any-value matching.

Update the `apply_operator` function documentation (around line 166) to include examples of the new operators in the docstring.

**File**: `file:docs/MAGIC_FORMAT.md`

The XOR operator is already documented (line 198). Add documentation for the NOT operator in the Operators section (around line 187):

```markdown
| `~` | Bitwise NOT | `4 byte ~0xff` |
```

Ensure the `x` (any value) documentation (line 255) is clear about its unconditional matching behavior.

### 5. Integration Testing

Verify all existing tests continue to pass:
- Run `cargo test` to ensure no regressions
- Verify operator parsing tests in `file:src/parser/grammar.rs`
- Verify operator evaluation tests in `file:src/evaluator/operators.rs`
- Check AST serialization tests in `file:src/parser/ast.rs`

The new operators should integrate seamlessly with the existing evaluation engine without requiring changes to `file:src/evaluator/mod.rs` or other components.

## Sequence Diagram

```mermaid
sequenceDiagram
    participant Parser as parse_operator
    participant AST as Operator Enum
    participant Evaluator as apply_operator
    participant Helper as apply_bitwise_xor/not/any

    Parser->>Parser: Recognize ^ / ~ / x symbol
    Parser->>AST: Create BitwiseXor/Not/AnyValue
    AST->>Evaluator: Pass operator to evaluator
    Evaluator->>Evaluator: Match on operator variant
    Evaluator->>Helper: Dispatch to helper function
    Helper->>Helper: Perform operation on values
    Helper->>Evaluator: Return boolean result
    Evaluator->>Evaluator: Continue rule evaluation
```

---

Execution Information

Branch: main
Commit: 36adac5

---

💡 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.