Repository files navigation

This macro speeds up Rust'smatch expression for comparing strings by using acompact double-array data structure.

Simply wrap the existingmatch expression with thetrie_match! {} macro asfollows:

use trie_match::trie_match;let x ="abd";let result =trie_match!{match x{"a" =>0,"abc" =>1,        pat @("abd" |"bcc") => pat.bytes()[0],"bc" =>3,        _ =>4,}};assert_eq!(result,3);

In a normalmatch expression, the string is compared for each pattern. It isequivalent to the following code:

if x =="a"{0}elseif x =="abc"{1}elseif x =="abd" || x =="bcc"{    x.bytes()[0]}elseif x =="bc"{3}else{4}

The above code requires that string comparisons be made from the beginning ofthe string each time. The time complexity of the above code isO(mn), wherem is the average pattern length, andn is the number of patterns.

In contrast, this macro builds the following trie structure to retrieve theindex of the matched arm:

Furthermore, this implementation uses the compact double-array data structureto achieve efficient state-to-state traversal, and the time complexity becomesO(m).

Only when using Nightly Rust, this macro supports conditional compilation withthecfg attribute. To use this feature, enablefeatures = ["cfg_attribute"]in yourCargo.toml.

trie_match!{match x{        #[cfg(feature ="foo")]"a" =>{ ..}        #[cfg(feature ="bar")]"b" =>{ ..}        _ =>{ ..}}}

The followings are different from the normalmatch expression:

• Only supports strings, byte strings, and u8 slices as patterns.
• The wildcard is evaluated last. (The normalmatch expression does notmatch patterns after the wildcard.)
• Guards are unavailable.

Sometimes the normalmatch expression is faster, depending on howoptimization is performed, so it is better to choose based on your speedexperiments.

Run the following command:

cargo bench

Experimental results are as follows [μs]:

• AMD Ryzen 7 5700U with Radeon Graphics

  Bench name	Normal match	phf crate	trie-match crate
  100 words random	1.94	2.02	1.09
  HTML elements random	2.32	2.43	0.55

• 12th Gen Intel(R) Core(TM) i7-1270P

  Bench name	Normal match	phf crate	trie-match crate
  100 words random	1.13	1.29	0.61
  HTML elements random	1.24	1.51	0.36

phf crate: Compile time static mapsusing perfect hash functions.

Licensed under either of

• Apache License, Version 2.0(LICENSE-APACHE orhttp://www.apache.org/licenses/LICENSE-2.0)
• MIT license(LICENSE-MIT orhttp://opensource.org/licenses/MIT)

at your option.

Seethe guidelines.