HORIZON HASKELLDocslts/ghc-10.0.xfc4e5982026-10-11Search names, modules, packages, or :: a typeCtrl K

GHC 10.0.0.20260917 · lts/ghc-10.0.x · fc4e598 · 2026-10-11

Modulealfred-margaret-2.1.1.1Haskell2010

Data.Text.AhoCorasick.Automaton

An efficient implementation of the Aho-Corasick string matching algorithm. See http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Small02.pdf for a good explanation of the algorithm.

The memory layout of the automaton, and the function that steps it, were optimized to the point where string matching compiles roughly to a loop over the code units in the input text, that keeps track of the current state. Lookup of the next state is either just an array index (for the root state), or a linear scan through a small array (for non-root states). The pointer chases that are common for traversing Haskell data structures have been eliminated.

The construction of the automaton has not been optimized that much, because construction time is usually negligible in comparison to matching time. Therefore construction is a two-step process, where first we build the automaton as int maps, which are convenient for incremental construction. Afterwards we pack the automaton into unboxed vectors.

This module is a rewrite of the previous version which used an older version of the text package which in turn used UTF-16 internally.

  • 5 types
  • 6 values
datadata AcMachine v
#

An Aho-Corasick automaton.

Constructors

Instances4Functor, Generic, NFData, Rep
datadata CaseSensitivity
#
CaseSensitiveIgnoreCase
Instances8Eq, Show, Generic, NFData, Hashable, FromJSON, …
newtypenewtype CodeUnitIndex
#

An index into the raw UTF-8 data of a Text. This is not the code point index as conventionally accepted by Text, so we wrap it to avoid confusing the two. Incorrect index manipulation can lead to surrogate pairs being sliced, so manipulate indices with care. This type is also used for lengths.

Constructors

Instances12Bounded, Eq, Num, Ord, Show, Generic, …
datadata Match v
#

Constructors

  • Match
    • matchPos :: !CodeUnitIndex

      The code unit index past the last code unit of the match. Note that this is not a code *point* (Haskell Char) index; a code point might be encoded as up to four code units.

    • matchValue :: v

      The payload associated with the matched needle.

datadata Next a
#

Result of handling a match: stepping the automaton can exit early by returning a Done, or it can continue with a new accumulator with Step.

Constructors

valuebuild :: [(Text, v)] -> AcMachine v
#

Construct an Aho-Corasick automaton for the given needles. The automaton uses Unicode code points to match the input.

valuerunWithCase
  1. :: CaseSensitivity
  2. -> a
  3. -> a -> Match v -> Next a
  4. -> AcMachine v
  5. -> Text
  6. -> a
#

Run the automaton, possibly lowercasing the input text on the fly if case insensitivity is desired. See also runLower.

The code of this function itself is organized as a state machine as well. Each state in the diagram below corresponds to a function defined in runWithCase. These functions are written in a way such that GHC identifies them as join points. This means that they can be compiled to jumps instead of function calls, which helps performance a lot.

  ┌─────────────────────────────┐
  │                             │
┌─▼──────────┐   ┌──────────────┴─┐   ┌──────────────┐
│consumeInput├───►lookupTransition├───►collectMatches│
└─▲──────────┘   └─▲────────────┬─┘   └────────────┬─┘
  │                │            │                  │
  │                └────────────┘                  │
  │                                                │
  └────────────────────────────────────────────────┘

  • consumeInput decodes a code point of up to four code units and possibly lowercases it. It passes this code point to followCodePoint, which in turn calls lookupTransition.

  • lookupTransition checks whether the given code point matches any transitions at the given state. If so, it follows the transition and calls collectMatches. Otherwise, it follows the fallback transition and calls followCodePoint or consumeInput.

  • collectMatches checks whether the current state is accepting and updates the accumulator accordingly. Afterwards it loops back to consumeInput.

NOTE: followCodePoint is actually inlined into consumeInput by GHC. It is included in the diagram for illustrative reasons only.

All of these functions have the arguments offset, state and acc which encode the current input position and the accumulator, which contains the matches. If you change any of the functions above, make sure to check the Core dumps afterwards that offset and state were turned into unboxed Int# by GHC. If any of them aren't, the program will constantly allocate and deallocate heap space for them. You can nudge GHC in the right direction by using bang patterns on these arguments.

WARNING: Run benchmarks when modifying this function; its performance is fragile. It took many days to discover the current formulation which compiles to fast code; removing the wrong bang pattern could cause a 10% performance regression.

valueneedleCasings :: Text -> [Text]
#

Given a lower case text, this gives all the texts that would lowercase to this one

needleCasings "abc" == ["abc","abC","aBc","aBC",Abc,AbC,ABc,ABC] needleCasings ABC == [] needleCasings "ω1" == [Ω1,"ω1",Ω1]