#wildcards #no-std

no-std wildflower

Wildcard matching against strings

4 releases (2 breaking)

0.3.0 Apr 1, 2023
0.2.0 Jan 30, 2023
0.1.1 Sep 12, 2022
0.1.0 Sep 12, 2022

#2170 in Algorithms

Download history 13/week @ 2023-10-28 10/week @ 2023-11-04 9/week @ 2023-11-11 11/week @ 2023-11-18 21/week @ 2023-11-25 17/week @ 2023-12-02 7/week @ 2023-12-09 13/week @ 2023-12-16 16/week @ 2023-12-23 7/week @ 2023-12-30 11/week @ 2024-01-06 11/week @ 2024-01-13 6/week @ 2024-01-20 17/week @ 2024-01-27 6/week @ 2024-02-03 24/week @ 2024-02-10

57 downloads per month

MIT license

78KB
187 lines

wildflower

workflow status crates.io docs.rs

(kitten trying to eat some some flowers that look suspicously like asterisks)

wildflower is a Rust library that performs wildcard matching against strings. It's fast, ergonomic, zero-copy, and works on no_std.

Usage

The wildcard matching grammar contains the following special characters:

  • ? matches a single character.
  • * matches zero or more characters.
  • \ escapes these special characters.

A pattern is constructed from a UTF-8-encoded string which may contain these special characters. When a pattern is created, the given source string is parsed and compiled into an optimized internal form. Since no internal state is maintained between matches, it is recommended that you reuse patterns for best results.

Alternatives

wildmatch is the closest alternative at the time of writing. Unfortunately, it explicitly does not support escaping special characters, which I found to be a significant limitation to warrant an alternative. wildflower also performs certain optimizations that make it more performant when matching, in many cases by an order of magnitude (see benchmarks).

Several other crates exist for pattern matching, namely regex (for regular expressions) and glob (for Unix shell patterns).

Benchmarking

Using a benchmark similar to the one found in wildmatch (source), I obtained the following results on my machine:

Benchmark wildflower wildmatch regex glob
compiling/text 362 ns 390 ns 131,770 ns 2,041 ns
compiling/complex 218 ns 47 ns 84,236 µs 165 ns
matching/text 7 ns 416 ns 415 ns 832 ns
matching/complex 104 ns 494 ns 409 ns 2,222 ns

In this benchmark run, wildflower is shown to be 76x and 4x as fast as wildmatch in the simple and complex case of matching respectfully. It could certainly stand to see performance improvements in compiling, but even in the worst case of a single-use compilation, it still outperforms wildmatch.

Credits

Credit to Armin Becher for the benchmarking code and table format from wildmatch, and to Ilona Ilyés of Pixabay for the original of the cat image featured above.

Dependencies

~0.5–1MB
~20K SLoC