Package org.jline.builtins

Class NfaMatcher<T>

java.lang.Object
org.jline.builtins.NfaMatcher<T>
Type Parameters:
T - the type of objects to match against the pattern
public class NfaMatcher<T> extends Object
Non-deterministic Finite Automaton (NFA) implementation for pattern matching.

This class implements a Thompson NFA for regular expression matching. It converts a regular expression to postfix notation, builds an NFA, and uses it to match sequences of objects against the pattern.

The implementation is based on the algorithm described in Russ Cox's article: https://swtch.com/~rsc/regexp/regexp1.html

  • Field Details

    • regexp

      private final String regexp
      The regular expression pattern

    • matcher

      private final BiFunction<T,String,Boolean> matcher
      Function to match an input against a pattern

    • start

      private volatile NfaMatcher.State start
      The start state of the NFA

  • Constructor Details

    • NfaMatcher

      public NfaMatcher(String regexp, BiFunction<T,String,Boolean> matcher)
      Creates a new NfaMatcher with the specified regular expression and matcher function.
      Parameters:
      regexp - the regular expression pattern
      matcher - the function to match an input against a pattern

  • Method Details

    • compile

      public void compile()
      Compiles the regular expression into an NFA.

      This method is called automatically when needed, but can be called explicitly to precompile the pattern.

    • match

      public boolean match(List<T> args)
      Matches a list of arguments against the pattern.

      This method uses the NFA to determine if the sequence of arguments matches the regular expression pattern.

      Parameters:
      args - the list of arguments to match
      Returns:
      true if the arguments match the pattern, false otherwise

    • matchPartial

      public Set<String> matchPartial(List<T> args)
      Returns the list of possible matcher names for the next object
      Parameters:
      args - input list
      Returns:
      the list of possible matcher names for the next object

    • addState

      void addState(Set<NfaMatcher.State> l, NfaMatcher.State s)
      Adds a state to the set of states, handling split states recursively.
      Parameters:
      l - the set of states to add to
      s - the state to add

    • toNfa

      static NfaMatcher.State toNfa(List<String> postfix)
      Converts a postfix expression to an NFA.
      Parameters:
      postfix - the postfix expression
      Returns:
      the start state of the NFA

    • toPostFix

      static List<String> toPostFix(String regexp)
      Converts a regular expression to postfix notation.
      Parameters:
      regexp - the regular expression
      Returns:
      the postfix expression as a list of tokens