RFC: Pattern-Based Code Fixing System Using Parser Combinator

[notJoon]

Description

The current system modifies code based on the line numbers and offsets. While this approach is simple, but the limitation is definitely bold.

1. Simple test substitution without considering syntatic context.
2. Difficulty in complex case
3. Limitations in multi-line pattern matching
4. Difficulty in defining reusable rules

We aim to address these limitations by introducing a Comby-style pattern matching system, by using parser combinator.

Implementation Strategy

Phase 1: Basic Pattern Engine

1. Implement pattern parsing engine
2. Support basic metavariables
3. Simple substitution functionality

Phase 2: Advanced Features

1. gno-specific context support
2. conditional matching
3. nested pattern support

Each of these tasks should be migrated incrementally as they proceeds.

Design

This design is a conceptual sketch, so it can be change at any time.

1. Pattern Matching Engine

type Pattern struct {
    Match    string          // Matching pattern including metavariables in :[[name]] format
    Rewrite  string          // Transformation pattern
    Where    PatternContext  // Additional constraints
}

type PatternContext struct {
    Language    string                 // Language-specific rule application
    Predicates  []func(Match) bool     // Match validation functions
}

type Match struct {
    Variables map[string]string  // Metavariable capture results
    Range     Range             // Range of matched code
}

2. New Fixer Interface

type Fixer struct {
    patterns []Pattern
    config   FixerConfig
}

type FixerConfig struct {
    MinConfidence float64
    DryRun       bool
    Language     string
}

func (f *Fixer) AddPattern(pattern Pattern) error
func (f *Fixer) Fix(filename string, issues []tt.Issue) error

3. Pattern Definition Format

Need to allow users to add custom patterns via the config file.

patterns:
  - name: "remove-redundant-if"
    match: "if :[[cond]] { return :[[value]] } else { return !:[[value]] }"
    rewrite: "return :[[cond]]"
    where:
      language: "go"
      
  - name: "deprecated-function"
    match: ":[[old]](:[[args]])"
    rewrite: ":[[new]](:[[args]])"
    where:
      predicates:
        - IsDeprecated

Example Usage

fixer := New(FixerConfig{
    MinConfidence: 0.8,
    Language: "go",
})

fixer.AddPattern(Pattern{
    Match: "if :[[cond]] { return true } else { return false }",
    Rewrite: "return :[[cond]]",
})

err := fixer.Fix("example.go", issues)

Metavariable Syntax

Defines metavariable syntax for Comby-style pattern matching

1. Basic Metavariables

:[[identifier]]      # Basic metavariable, matches single token/expression
:[identifier]        # Short syntax

2. Special Metavariables

# Whitespace handling
:[[spacing]]         # Match whitespace characters (space, tab, newline)
:[s]                # Short syntax
# Nested structure matching
:[[block]]          # Match nested blocks (e.g., {...}, (...))
:[b]               # Short syntax
# Repetition matching
:[[...]]*          # Match 0 or more times
:[[...]]+          # Match 1 or more times
:[[...]]?          # Match 0 or 1 time

3. Constraints

where:
  # Metavariable value validation
  :[[expr]] != "nil"
  :[[type]] matches "^int|float"
  
  # Structural constraints
  :[[block]] contains "return"
  :[[stmt]] ends_with ";"

4. Example

patterns:
  # Remove unnecessary if-else
  - match: |
      if :[[cond]] {
        return :[[value]]
      } else {
        :[[rest:block]]
      }
    rewrite: |
      if :[[cond]] {
        return :[[value]]
      }
      :[[rest]]
  # Simplify nil check
  - match: |
      if :[[x]] != nil {
        :[[body:block]]
      }
    rewrite: |
      if :[[x]] {
        :[[body]]
      }
    where:
      :[[x]] matches "^[A-Za-z]"

[notJoon]

TODO: Update metavariable parser to use state machine and SIMD after support all expressions.

Resolved: #113