Compare commits

12 Commits

Author SHA1 Message Date
55f61f71d8 refactor(natu): remove custom Nix linter 2026-10-13 21:59:41 -04:00
08563c6769 refactor(nixos): remove unused direnv module 2026-10-13 21:50:37 -04:00
8462b3a5a8 refactor(copyparty): separate deployment and service policy
Move Copyparty rendering into shared dotfiles utilities, keep guest wiring focused on host/container plumbing, and let the service module derive effective volume policy.
2026-10-13 20:33:25 -04:00
d0872e7d8c fix(homepage): skip empty ordered sections 2026-10-12 11:50:27 -04:00
9be9ad7675 refactor(actualbudget): remove unused service 2026-10-12 11:40:05 -04:00
5ee328cdf8 refactor(flake): centralize custom packages 2026-10-12 11:34:18 -04:00
6532a822cd feat(userdirs): configure preferred directories 2026-10-11 22:54:11 -04:00
20a3990979 refactor(theming): simplify stylix module 2026-10-11 22:43:35 -04:00
b7ab518f58 refactor(screenshot): simplify capture bindings 2026-10-11 22:40:44 -04:00
3f1e34ef95 refactor(recording): signal status updates 2026-10-11 22:37:30 -04:00
d0abfc1625 refactor(osd): move volume bindings to audio 2026-10-11 22:33:32 -04:00
031090e4ea fix(waybar): use Lua dispatch build 2026-10-11 22:12:17 -04:00
1124 changed files with 423 additions and 354736 deletions

View File

@@ -17,15 +17,6 @@ If the target includes multiple matching file types, use all matching skills.
If the target is a diff, choose skills from the changed files.
Do not use a style skill when no reviewed file matches it.
For every reviewed `*.nix` file, run:
```bash
bazel run //src/natu:natu -- <reviewed-nix-paths>
```
Pass every reviewed Nix path to Natu.
Report every Natu diagnostic as an actionable finding.
Report only actionable findings.
Order findings by severity.
Do not report preferences unless a loaded rule states them.
@@ -45,7 +36,6 @@ Keep the code excerpt to one to three lines when possible.
Use a longer excerpt only when the violation needs surrounding context.
Use `...` to omit unrelated lines from a multi-line excerpt.
Use a style-skill rule citation in the form `skill::rule-file:line`.
Cite Natu diagnostics as `natu::<rule-id>`.
Make the fix direct.
Do not include alternatives when one fix best follows the cited rule.

View File

@@ -105,13 +105,10 @@
Do not use `nix fmt` as a validation command until a formatter is added.
- The `fix` app passes its current directory to Deadnix.
Run `nix run .#fix` from the repository root so path exclusions match.
- During the Nix refactor, address each issue that comes up by adding either a Natu rule or a new Nix style rule.
- Git pathspec searches started in a subdirectory default to that subtree.
Use `git -C <repository-root>` or top-anchored pathspecs for repository-wide history searches.
- A `**/*.nix` Git pathspec does not include Nix files directly in its starting directory.
Include both `*.nix` and `**/*.nix`, or use a recursive `*.nix` pathspec, when linting every Nix file.
- Nix `let` bindings are recursive; their source order does not determine binding availability.
Treat Natu `let_order` as a readability rule, not an evaluation dependency.
- Ariadne extraction must preserve the game-root season prefix for archived source.
Different game installs can contain compiled scripts with the same internal path.
- Clew owns Ren'Py extraction, preparation, and compiled-script AST export. Ariadne owns analysis over Clew-produced data.

154
Cargo.lock generated
View File

@@ -2,15 +2,6 @@
# It is not intended for manual editing.
version = 4
[[package]]
name = "aho-corasick"
version = "1.1.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "c982642fa9e8606056828ee9a8505737230110bb1099153c79efe865c59d12ba"
dependencies = [
"memchr",
]
[[package]]
name = "anstream"
version = "1.0.0"
@@ -71,12 +62,6 @@ dependencies = [
"serde_json",
]
[[package]]
name = "autocfg"
version = "1.5.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "f2032f911046de80f0a198e0901378627c33f59ea0ac00e363d481118bd70a53"
[[package]]
name = "clap"
version = "4.6.7"
@@ -108,7 +93,7 @@ dependencies = [
"heck",
"proc-macro2",
"quote",
"syn 3.0.6",
"syn",
]
[[package]]
@@ -123,41 +108,6 @@ version = "1.0.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "1d07550c9036bf2ae0c684c4297d503f838287c83c53686d05370d0e139ae570"
[[package]]
name = "countme"
version = "3.0.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "7704b5fdd17b18ae31c4c1da5a2e0305a2bf17b5249300a9ee9ed7b72114c636"
[[package]]
name = "googletest"
version = "0.14.3"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "f6b5e2f2b556b7b90297a5a35c8267dd43a537923d2b329beefdba2b4ec19d94"
dependencies = [
"googletest_macro",
"num-traits",
"regex",
"rustversion",
]
[[package]]
name = "googletest_macro"
version = "0.14.3"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "2ae6abc96141edd26bf5aeec0f119c129c44de3ced09e5073711a02cb74725d0"
dependencies = [
"proc-macro2",
"quote",
"syn 2.0.119",
]
[[package]]
name = "hashbrown"
version = "0.14.5"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "e5274423e17b7c9fc20b6e7e208532f9b19825d82dfd615708b70edd83df41f1"
[[package]]
name = "heck"
version = "0.5.0"
@@ -190,27 +140,6 @@ checksum = "cf8baf1c55e62ffcace7a9f06f4bd9cd3f0c4beb022d3b367256b91b87513d98"
name = "monorepo"
version = "0.1.0"
[[package]]
name = "natu"
version = "0.1.0"
dependencies = [
"clap",
"googletest",
"monorepo",
"rnix",
"rowan",
"status",
]
[[package]]
name = "num-traits"
version = "0.2.19"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841"
dependencies = [
"autocfg",
]
[[package]]
name = "once_cell_polyfill"
version = "1.70.2"
@@ -235,68 +164,6 @@ dependencies = [
"proc-macro2",
]
[[package]]
name = "regex"
version = "1.13.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "f020237b6c8eed93db2e2cb53c00c60a8e1bc73da7d073199a1180401450218d"
dependencies = [
"aho-corasick",
"memchr",
"regex-automata",
"regex-syntax",
]
[[package]]
name = "regex-automata"
version = "0.4.18"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "ad8553b9b26413251cbf30e620595c7a41b3887f03da04579c0e6b0d6a06b4b2"
dependencies = [
"aho-corasick",
"memchr",
"regex-syntax",
]
[[package]]
name = "regex-syntax"
version = "0.8.11"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "d6f6ff9a378485b298a5286656da665ba74413d36db0979633275d2e708145d4"
[[package]]
name = "rnix"
version = "0.14.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "c163bd17372eecdf10d351c34584b7de7c1a33be4e92a32f3fb3f5a7fe3f579b"
dependencies = [
"rowan",
]
[[package]]
name = "rowan"
version = "0.16.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "417a3a9f582e349834051b8a10c8d71ca88da4211e4093528e36b9845f6b5f21"
dependencies = [
"countme",
"hashbrown",
"rustc-hash",
"text-size",
]
[[package]]
name = "rustc-hash"
version = "1.1.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "08d43f7aa6b08d49f382cde6a7982047c3426db949b1424bc4b7ec9ae12c6ce2"
[[package]]
name = "rustversion"
version = "1.0.23"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "cf54715a573b99ac80df0bc206da022bcd442c974952c7b9720069370852e21f"
[[package]]
name = "serde"
version = "1.0.229"
@@ -324,7 +191,7 @@ checksum = "e7a5d71263a5a7d47b41f6b3f06ba276f10cc18b0931f1799f710578e2309348"
dependencies = [
"proc-macro2",
"quote",
"syn 3.0.6",
"syn",
]
[[package]]
@@ -350,17 +217,6 @@ version = "0.11.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "7da8b5736845d9f2fcb837ea5d9e2628564b3b043a70948a3f0b778838c5fb4f"
[[package]]
name = "syn"
version = "2.0.119"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "872831b642d1a07999a962a351ed35b955ea2cfc8f3862091e2a240a84f17297"
dependencies = [
"proc-macro2",
"quote",
"unicode-ident",
]
[[package]]
name = "syn"
version = "3.0.6"
@@ -372,12 +228,6 @@ dependencies = [
"unicode-ident",
]
[[package]]
name = "text-size"
version = "1.1.1"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "f18aa187839b2bdb1ad2fa35ead8c4c2976b64e4363c386d45ac0f7ee85c9233"
[[package]]
name = "unicode-ident"
version = "1.0.26"

View File

@@ -4,16 +4,12 @@ members = [
"src/machoke",
"src/monorepo",
"src/status",
"src/natu",
]
resolver = "3"
[workspace.dependencies]
clap = "4"
googletest = "0.14"
monorepo = { path = "src/monorepo" }
rnix = "=0.14.0"
rowan = "0.16"
serde = "1.0"
serde_json = "1.0"
status = { path = "src/status" }

View File

@@ -1,51 +0,0 @@
{
config,
lib,
...
}:
let
cfg = config.guests.actualbudget; # NOLINT(let_order)
dataDir = "/data";
in
{
options.guests.actualbudget = {
dataPath = lib.mkOption {
type = lib.types.nullOr lib.types.str;
default = null;
example = "/srv/actualbudget";
description = "Host path bind-mounted as Actual Budget's data directory.";
};
};
config = lib.mkIf cfg.enable {
assertions = [
{
assertion = cfg.dataPath != null;
message = "guests.actualbudget.dataPath must point at the host directory that stores Actual Budget data.";
}
];
registry.homepage.${config.networking.hostName}.actualbudget = {
tab = "Apps";
section = "Other";
name = "Actual Budget";
description = "Finance";
icon = "actual-budget.png";
};
guests.actualbudget = {
interior = {
modules.services.actualbudget = {
enable = true;
inherit dataDir;
};
};
mounts.${dataDir}.directory = cfg.dataPath;
limits = {
memory = lib.mkDefault "2G";
cpu = lib.mkDefault "200%";
tasksMax = lib.mkDefault 512;
};
};
};
}

View File

@@ -4,58 +4,14 @@
...
}:
let
cfg = config.guests.copyparty; # NOLINT(let_order)
volumeType = lib.types.submodule {
options = {
hostPath = lib.mkOption {
type = lib.types.str;
description = "Host path bind-mounted into the Copyparty guest for this volume.";
};
path = lib.mkOption {
type = lib.types.str;
description = "Guest path served by this Copyparty volume.";
};
access = lib.mkOption {
type = lib.types.attrsOf (lib.types.listOf lib.types.str);
default = { };
description = "Copyparty access map from permission string to account names.";
};
readOnly = lib.mkOption {
type = lib.types.bool;
default = false;
description = "Serve this Copyparty volume read-only.";
};
flags = lib.mkOption {
type = lib.types.listOf lib.types.str;
default = [ ];
description = "Copyparty volume flags.";
};
};
};
cfg = config.guests.copyparty;
in
{
options.guests.copyparty = {
accountName = lib.mkOption {
type = lib.types.str;
default = "alexion";
description = "Copyparty account name configured for password authentication.";
};
passwordSecret = lib.mkOption {
type = lib.types.str;
default = "services/copyparty/users/alexion/password";
description = "SOPS secret name containing the Copyparty account password.";
};
stateDir = lib.mkOption {
type = lib.types.str;
default = "/var/lib/copyparty";
description = "Guest path where Copyparty stores service state.";
default = "services/copyparty/users/${config.user.name}/password";
description = "SOPS secret name that contains the Copyparty account password.";
};
statePath = lib.mkOption {
@@ -72,7 +28,39 @@ in
};
volumes = lib.mkOption {
type = lib.types.attrsOf volumeType;
type = lib.types.attrsOf (
lib.types.submodule {
options = {
hostPath = lib.mkOption {
type = lib.types.str;
description = "Host path bind-mounted into the Copyparty guest for this volume.";
};
path = lib.mkOption {
type = lib.types.str;
description = "Guest path served by this Copyparty volume.";
};
access = lib.mkOption {
type = lib.types.attrsOf (lib.types.listOf lib.types.str);
default = { };
description = "Copyparty access map from permission string to account names.";
};
readOnly = lib.mkOption {
type = lib.types.bool;
default = false;
description = "Serve this Copyparty volume read-only.";
};
flags = lib.mkOption {
type = lib.types.attrs;
default = { };
description = "Copyparty volume flags.";
};
};
}
);
default = { };
description = "Copyparty volumes keyed by their URL path.";
};
@@ -102,24 +90,26 @@ in
guests.copyparty = {
interior.modules.services.copyparty = {
enable = true;
inherit (cfg) accountName stateDir;
passwordFile = "/run/secrets/${cfg.passwordSecret}";
reverseProxy = {
enable = cfg.reverseProxy.enable;
inherit (cfg.reverseProxy) trustedSources;
};
volumes = lib.mapAttrs (_urlPath: volume: {
inherit (volume)
path
access
flags
readOnly
;
}) cfg.volumes;
volumes = lib.mapAttrs (
_urlPath: volume:
{
inherit (volume)
path
readOnly
;
}
// lib.optionalAttrs (volume.access != { }) { inherit (volume) access; }
// lib.optionalAttrs (volume.flags != { }) { inherit (volume) flags; }
) cfg.volumes;
};
mounts = {
${cfg.stateDir} = {
"/var/lib/copyparty" = {
directory = cfg.statePath;
owner = config.registry."stable-uid".${config.networking.hostName}.copyparty;
group = "storage";

View File

@@ -4,7 +4,7 @@
...
}:
let
cfg = config.guests.homepage; # NOLINT(let_order)
cfg = config.guests.homepage;
environmentFile = "/run/secrets/homepage.env";
in
{

View File

@@ -4,7 +4,7 @@
...
}:
let
cfg = config.guests.palworld; # NOLINT(let_order)
cfg = config.guests.palworld;
steamDir = "/data/steamcmd";
installDir = "/data/server";
stateDir = "/data/state";

View File

@@ -4,7 +4,7 @@
...
}:
let
cfg = config.guests.valheim; # NOLINT(let_order)
cfg = config.guests.valheim;
steamDir = "/data/steamcmd";
installDir = "/data/server";
stateDir = "/data/state";

View File

@@ -71,22 +71,6 @@
};
};
guests.actualbudget = {
enable = true;
vlan = 20;
mac = "BC:24:11:C1:CD:28";
dataPath = "/pikachu/data/actualbudget";
address = "10.23.20.42";
reverseProxy = {
enable = true;
route = {
domain = "budget.alexion.dev";
protocol = "https";
port = 5006;
};
};
};
guests.navidrome = {
enable = true;
vlan = 20;
@@ -145,35 +129,21 @@
"/" = {
hostPath = "/pikachu/data/copyparty/root";
path = "/srv";
access.r = [ "alexion" ];
readOnly = true;
};
"/inbox" = {
hostPath = "/pikachu/__inbox";
path = "/pikachu/__inbox";
access.A = [ "alexion" ];
flags = [
"d2d"
"d2t"
"dthumb"
];
};
"/media" = {
hostPath = "/pikachu/media";
path = "/pikachu/media";
access.A = [ "alexion" ];
flags = [
"d2d"
"d2t"
"dthumb"
];
};
"/opds" = {
hostPath = "/pikachu/data/opds";
path = "/pikachu/data/opds";
access.r = [ "alexion" ];
readOnly = true;
flags = [ "opds" ];
flags.opds = true;
};
};
};

View File

@@ -8,7 +8,7 @@
}:
# Configures Firefox as the desktop browser.
let
cfg = config.modules.desktop.apps.firefox; # NOLINT(let_order)
cfg = config.modules.desktop.apps.firefox;
in
{
options.modules.desktop.apps.firefox = {

View File

@@ -30,6 +30,7 @@ in
home-manager.users.${config.user.name}.programs.waybar = {
enable = true;
package = pkgs.alexion.waybar;
# A user service bound to graphical-session.target, which uwsm activates,
# so the bar comes up with the session and no compositor exec-once.

View File

@@ -7,6 +7,15 @@
}:
# PipeWire as the desktop audio server.
let
volumeKey = keys: command: {
inherit keys;
repeating = true;
action = {
kind = "exec";
command = "${lib.getExe' pkgs.swayosd "swayosd-client"} --output-volume ${command}";
};
};
mediaKey = keys: command: {
inherit keys;
locked = true;
@@ -30,6 +39,17 @@ in
};
registry.keybind.${config.networking.hostName} = {
volume-up = volumeKey "XF86AudioRaiseVolume" "raise --max-volume 100";
volume-down = volumeKey "XF86AudioLowerVolume" "lower";
mute = {
keys = "XF86AudioMute";
locked = true;
action = {
kind = "exec";
command = "${lib.getExe' pkgs.swayosd "swayosd-client"} --output-volume mute-toggle";
};
};
media-play = mediaKey "XF86AudioPlay" "play-pause";
media-next = mediaKey "XF86AudioNext" "next";
media-previous = mediaKey "XF86AudioPrev" "previous";

View File

@@ -5,39 +5,41 @@
...
}:
# SwayOSD: a transient on-screen popup for volume and brightness changes.
let
user = config.user.name;
in
{
options.modules.desktop.utilities.osd.enable =
lib.mkEnableOption "the SwayOSD volume and brightness popup";
config = lib.mkIf config.modules.desktop.utilities.osd.enable {
environment.systemPackages = [ pkgs.swayosd ];
# The udev rule chgrps each backlight's brightness node to `video` and adds
# group write, so the server dims the panel without root.
# Membership below grants the running session that access.
services.udev.packages = [ pkgs.swayosd ];
users.users.${config.user.name}.extraGroups = [ "video" ];
# The server draws the popups, so it runs for the whole graphical session.
# It binds to the target uwsm activates.
home-manager.users.${config.user.name}.systemd.user.services.swayosd = {
Unit = {
Description = "SwayOSD on-screen display server";
PartOf = [ "graphical-session.target" ];
After = [ "graphical-session.target" ];
};
Service = {
ExecStart = lib.getExe' pkgs.swayosd "swayosd-server";
Restart = "on-failure";
};
Install.WantedBy = [ "graphical-session.target" ];
};
registry.keybind.${config.networking.hostName} = {
volume-up = {
keys = "XF86AudioRaiseVolume";
repeating = true;
action = {
kind = "exec";
command = "${pkgs.swayosd}/bin/swayosd-client --output-volume raise --max-volume 100";
};
};
volume-down = {
keys = "XF86AudioLowerVolume";
repeating = true;
action = {
kind = "exec";
command = "${pkgs.swayosd}/bin/swayosd-client --output-volume lower";
};
};
brightness-up = {
keys = "XF86MonBrightnessUp";
repeating = true;
action = {
kind = "exec";
command = "${pkgs.swayosd}/bin/swayosd-client --brightness raise";
command = "${lib.getExe' pkgs.swayosd "swayosd-client"} --brightness raise";
};
};
@@ -46,41 +48,9 @@ in
repeating = true;
action = {
kind = "exec";
command = "${pkgs.swayosd}/bin/swayosd-client --brightness lower";
command = "${lib.getExe' pkgs.swayosd "swayosd-client"} --brightness lower";
};
};
mute = {
keys = "XF86AudioMute";
locked = true;
action = {
kind = "exec";
command = "${pkgs.swayosd}/bin/swayosd-client --output-volume mute-toggle";
};
};
};
environment.systemPackages = [ pkgs.swayosd ];
# The udev rule chgrps each backlight's brightness node to `video` and adds
# group write, so the server dims the panel without root.
# Membership below grants the running session that access.
services.udev.packages = [ pkgs.swayosd ];
users.users.${user}.extraGroups = [ "video" ];
# The server draws the popups, so it runs for the whole graphical session.
# It binds to the target uwsm activates.
home-manager.users.${user}.systemd.user.services.swayosd = {
Unit = {
Description = "SwayOSD on-screen display server";
PartOf = [ "graphical-session.target" ];
After = [ "graphical-session.target" ];
};
Service = {
ExecStart = "${pkgs.swayosd}/bin/swayosd-server";
Restart = "on-failure";
};
Install.WantedBy = [ "graphical-session.target" ];
};
};
}

View File

@@ -7,13 +7,13 @@
}:
# Keybound screen recording: pick a region, then toggle a video-only capture.
let
# A single key both starts and stops.
# A running wf-recorder is stopped with SIGINT so it finalises the file.
# Otherwise slurp picks a region and wf-recorder runs in the foreground until
# that stop arrives, so this instance lives for the whole recording and then
# reports it saved.
# No -a means no audio is captured.
toggle = pkgs.writeShellScript "screen-record-toggle" ''
# A single key starts and stops recording.
# Waybar refreshes on state changes instead of polling.
recordingToggle = pkgs.writeShellScript "screen-record-toggle" ''
refresh_waybar() {
${lib.getExe' pkgs.procps "pkill"} -RTMIN+10 waybar >/dev/null 2>&1 || true
}
if ${lib.getExe' pkgs.procps "pgrep"} -x wf-recorder >/dev/null; then
${lib.getExe' pkgs.procps "pkill"} -INT -x wf-recorder
exit 0
@@ -25,12 +25,15 @@ let
file="$dir/recording-$(${lib.getExe' pkgs.coreutils "date"} +%Y%m%d-%H%M%S).mp4"
${lib.getExe' pkgs.libnotify "notify-send"} -a "Screen recording" "Recording started" "Region capture, no audio."
${lib.getExe pkgs.wf-recorder} -g "$region" -f "$file"
${lib.getExe pkgs.wf-recorder} -g "$region" -f "$file" &
recorder=$!
refresh_waybar
wait "$recorder" || true
refresh_waybar
${lib.getExe' pkgs.libnotify "notify-send"} -a "Screen recording" "Recording saved" "$file"
'';
# Lit while a wf-recorder capture is running.
# Empty text collapses the widget when idle, so it shows nothing until then.
# Empty text collapses the widget when recording is idle.
recordingStatus = pkgs.writeShellScript "waybar-recording-status" ''
if ${lib.getExe' pkgs.procps "pgrep"} -x wf-recorder >/dev/null; then
printf '{"text":"${util.glyph "f03d"}","tooltip":"Recording","class":"recording"}\n'
@@ -48,7 +51,7 @@ in
keys = "SUPER + SHIFT + R";
action = {
kind = "exec";
command = "${toggle}";
command = "${recordingToggle}";
};
};
@@ -57,7 +60,8 @@ in
settings = {
return-type = "json";
exec = "${recordingStatus}";
interval = 1;
interval = "once";
signal = 10;
};
};
};

View File

@@ -7,26 +7,26 @@
# Keyboard-driven screenshots copy to the clipboard before Satty opens for
# annotation. Satty copies annotated screenshots when it saves them.
let
user = config.user.name;
grimblast = "${pkgs.grimblast}/bin/grimblast";
satty = "${pkgs.satty}/bin/satty";
tee = "${pkgs.coreutils}/bin/tee";
wl-copy = "${pkgs.wl-clipboard}/bin/wl-copy";
xdgUserDir = "${pkgs.xdg-user-dirs}/bin/xdg-user-dir";
screenshotKey = keys: target: {
inherit keys;
action = {
kind = "exec";
command = "${capture target}";
};
};
# Copy the original screenshot before Satty opens.
# Satty copies and saves annotated screenshots when the user presses Enter.
capture =
target:
pkgs.writeShellScript "screenshot-${target}" ''
dir="$(${xdgUserDir} PICTURES)/Screenshots"
mkdir -p "$dir"
${grimblast} save ${target} - \
| ${tee} >(${wl-copy}) \
| ${satty} --filename - \
dir="$(${lib.getExe' pkgs.xdg-user-dirs "xdg-user-dir"} PICTURES)/Screenshots"
${lib.getExe' pkgs.coreutils "mkdir"} -p "$dir"
${lib.getExe pkgs.grimblast} save ${target} - \
| ${lib.getExe' pkgs.coreutils "tee"} >(${lib.getExe' pkgs.wl-clipboard "wl-copy"}) \
| ${lib.getExe pkgs.satty} --filename - \
--output-filename "$dir/screenshot-%Y%m%d-%H%M%S.png" \
--copy-command ${wl-copy} \
--copy-command ${lib.getExe' pkgs.wl-clipboard "wl-copy"} \
--save-after-copy \
--early-exit \
--actions-on-enter save-to-clipboard
@@ -37,33 +37,7 @@ in
lib.mkEnableOption "screenshots via grimblast and satty";
config = lib.mkIf config.modules.desktop.utilities.screenshot.enable {
registry.keybind.${config.networking.hostName} = {
screenshot-area = {
keys = "Print";
action = {
kind = "exec";
command = "${capture "area"}";
};
};
screenshot-active = {
keys = "SHIFT + Print";
action = {
kind = "exec";
command = "${capture "active"}";
};
};
screenshot-screen = {
keys = "CTRL + Print";
action = {
kind = "exec";
command = "${capture "screen"}";
};
};
};
home-manager.users.${user} = {
home-manager.users.${config.user.name} = {
# satty is a one-shot annotation surface, so float it rather than letting
# it claim a tile in the layout.
wayland.windowManager.hyprland.settings.window_rule = [
@@ -72,7 +46,12 @@ in
float = true;
}
];
};
registry.keybind.${config.networking.hostName} = {
screenshot-area = screenshotKey "Print" "area";
screenshot-active = screenshotKey "SHIFT + Print" "active";
screenshot-screen = screenshotKey "CTRL + Print" "screen";
};
};
}

View File

@@ -6,15 +6,13 @@
}:
# Nord theming for the graphical layer, driven from one base16 scheme by Stylix.
let
# A single static Nord wallpaper, drawn as a vertical gradient across the
# Polar Night shades so it needs no committed binary and no network fetch.
wallpaper = pkgs.runCommand "nord-wallpaper.png" { } ''
${pkgs.imagemagick}/bin/magick \
${lib.getExe pkgs.imagemagick} \
-size 2560x1440 gradient:'#2E3440'-'#3B4252' \
"$out"
'';
user = config.user.name;
in
{
options.modules.desktop.utilities.theming.enable =
@@ -58,12 +56,8 @@ in
};
};
};
registry.env.${config.networking.hostName} = {
HYPRCURSOR_THEME = config.stylix.cursor.name;
HYPRCURSOR_SIZE = toString config.stylix.cursor.size;
};
home-manager.users.${user} = {
home-manager.users.${config.user.name} = {
# Stylix drives the cursor through home-manager's pointer-cursor config,
# whose generation must be switched on explicitly.
home.pointerCursor.enable = true;
@@ -72,5 +66,10 @@ in
# base16 mapping Stylix would apply, so its target stays off.
stylix.targets.nixvim.enable = false;
};
registry.env.${config.networking.hostName} = {
HYPRCURSOR_THEME = config.stylix.cursor.name;
HYPRCURSOR_SIZE = toString config.stylix.cursor.size;
};
};
}

View File

@@ -1,14 +1,27 @@
{ config, lib, ... }:
# Declares the XDG user directories, so a tool that queries them lands in a
# well-known folder a host can relocate from one place.
# Declares XDG user directories, so tools that query them use predictable
# folders a host can relocate from one place.
let
user = config.user.name;
homeDirectory = "/home/${config.user.name}";
in
{
options.modules.desktop.utilities.userdirs.enable = lib.mkEnableOption "XDG user directories";
config = lib.mkIf config.modules.desktop.utilities.userdirs.enable {
# Write ~/.config/user-dirs.dirs from the option defaults.
home-manager.users.${user}.xdg.userDirs.enable = true;
home-manager.users.${config.user.name}.xdg.userDirs = {
enable = true;
createDirectories = true;
setSessionVariables = true;
desktop = "${homeDirectory}/.ignoreme";
documents = "${homeDirectory}/docs";
download = "${homeDirectory}/dwn";
music = "${homeDirectory}/mus";
pictures = "${homeDirectory}/pic";
publicShare = "${homeDirectory}/.ignoreme";
templates = "${homeDirectory}/.ignoreme";
videos = "${homeDirectory}/vid";
projects = "${homeDirectory}/.ignoreme";
};
};
}

View File

@@ -5,7 +5,7 @@
}:
# Imports existing ZFS pools that hold durable service state.
let
cfg = config.modules.host.zfs; # NOLINT(let_order)
cfg = config.modules.host.zfs;
in
{
options.modules.host.zfs = {

View File

@@ -7,19 +7,17 @@
# Configures inbound and outbound SSH access.
let
cfg = config.modules.network.ssh;
user = config.user.name; # NOLINT(let_order)
user = config.user.name;
# NOLINT(let_order)
workstationNames = [
"neogaia"
"zeus"
];
serverNames = [ "pikachu" ];
isWorkstation = lib.elem config.networking.hostName workstationNames; # NOLINT(let_order)
isServer = lib.elem config.networking.hostName serverNames; # NOLINT(let_order)
isWorkstation = lib.elem config.networking.hostName workstationNames;
isServer = lib.elem config.networking.hostName serverNames;
# NOLINT(let_order)
clientKeyFor = host: builtins.readFile (../../hosts + "/${host}/ssh_user_ed25519_key.pub");
hostKeysFor =
host:
@@ -28,7 +26,6 @@ let
(../../hosts + "/${host}/ssh_host_rsa_key.pub")
];
# NOLINT(let_order)
managedTargets = lib.genAttrs (workstationNames ++ serverNames) (name: {
hostName = registry.address.${name}.self;
clientKey = clientKeyFor name;
@@ -48,7 +45,6 @@ let
};
};
# NOLINT(let_order)
mkTarget = name: target: {
hostName = target.hostName or name;
user = target.user or user;
@@ -57,15 +53,14 @@ let
clientKey = target.clientKey or null;
hostKeys = target.hostKeys or [ ];
};
targets = lib.mapAttrs mkTarget (managedTargets // extraTargets); # NOLINT(let_order)
targets = lib.mapAttrs mkTarget (managedTargets // extraTargets);
clientKeysFor = names: lib.filter (key: key != null) (map (name: targets.${name}.clientKey) names); # NOLINT(let_order)
# NOLINT(let_order)
clientKeysFor = names: lib.filter (key: key != null) (map (name: targets.${name}.clientKey) names);
defaultAuthorizedKeys = lib.flatten (
clientKeysFor workstationNames ++ lib.optional isServer (clientKeysFor serverNames)
);
outboundTargetNames = # NOLINT(let_order)
outboundTargetNames =
let
groupTargets =
if isServer then

View File

@@ -6,7 +6,7 @@
}:
# Configures bridges for tagged VLANs on a physical interface that uses DHCP.
let
cfg = config.modules.network.vlans; # NOLINT(let_order)
cfg = config.modules.network.vlans;
in
{
options.modules.network.vlans = {

View File

@@ -6,7 +6,7 @@
...
}:
let
cfg = config.modules.network.vpn-client; # NOLINT(let_order)
cfg = config.modules.network.vpn-client;
vpnIcon = util.glyph [
"db83"

View File

@@ -1,62 +0,0 @@
{
config,
lib,
...
}:
let
cfg = config.modules.services.actualbudget; # NOLINT(let_order)
in
{
options.modules.services.actualbudget = {
enable = lib.mkEnableOption "Actual Budget";
port = lib.mkOption {
type = lib.types.port;
default = 5006;
description = "Port Actual Budget listens on.";
};
dataDir = lib.mkOption {
type = lib.types.str;
default = "/data";
description = "Directory where Actual Budget stores server and user files.";
};
user = lib.mkOption {
type = lib.types.str;
default = "actual";
description = "User account that runs Actual Budget.";
};
group = lib.mkOption {
type = lib.types.str;
default = "storage";
description = "Group account that owns Actual Budget's writable state.";
};
};
config = lib.mkMerge [
{
registry."stable-uid".${config.networking.hostName}.actualbudget = 20001;
}
(lib.mkIf cfg.enable {
users.users.${cfg.user} = {
isSystemUser = true;
uid = config.registry."stable-uid".${config.networking.hostName}.actualbudget;
inherit (cfg) group;
};
services.actual = {
enable = true;
openFirewall = true;
inherit (cfg) user;
inherit (cfg) group;
settings = {
inherit (cfg) port dataDir;
};
};
})
];
}

View File

@@ -2,147 +2,135 @@
config,
lib,
pkgs,
util,
...
}:
let
cfg = config.modules.services.copyparty; # NOLINT(let_order)
cfg = config.modules.services.copyparty;
volumeType = lib.types.submodule {
options = {
path = lib.mkOption {
type = lib.types.str;
description = "Filesystem path served by this volume.";
};
accountName = config.user.name;
access = lib.mkOption {
type = lib.types.attrsOf (lib.types.listOf lib.types.str);
default = { };
example = {
A = [ "alexion" ];
};
description = "Copyparty access map from permission string to account names.";
};
serviceGroup = "storage";
readOnly = lib.mkOption {
type = lib.types.bool;
default = false;
description = "Serve this volume read-only.";
};
serviceStateDir = "/var/lib/copyparty";
flags = lib.mkOption {
type = lib.types.listOf lib.types.str;
default = [ ];
example = [ "dthumb" ];
description = "Copyparty volume flags.";
};
};
serviceUser = "copyparty";
writableVolumes = lib.filter (volume: !volume.readOnly) (lib.attrValues cfg.volumes);
port = 3923;
defaultAccess = {
A = [ accountName ];
};
configScript = pkgs.writeShellScript "copyparty-config" ''
set -eu
defaultWritableFlags = {
d2d = true;
d2t = true;
dthumb = true;
};
umask 077
password="$(${pkgs.coreutils}/bin/tr -d '\n' < "$CREDENTIALS_DIRECTORY/password")"
credentialHash = builtins.substring 0 16 (builtins.hashString "sha256" accountName);
cat > /run/copyparty/copyparty.conf <<EOF
[global]
p: ${toString cfg.port}
usernames
http-only
no-crt
no-thumb
no-snap
no-rescan
ses-db: ${cfg.stateDir}/sessions.db
chpw-db: ${cfg.stateDir}/chpw.json
shr-db: ${cfg.stateDir}/shares.db
${renderedReverseProxy}
[accounts]
${cfg.accountName}: $password
credentialName = "password-${credentialHash}";
${renderedVolumes}
EOF
'';
renderAccess = permission: accounts: " ${permission}: ${lib.concatStringsSep ", " accounts}";
passwordPlaceholder = "@COPYPARTY_PASSWORD_${credentialHash}@";
hasFlag =
name: flags: lib.any (flag: lib.hasPrefix "${name}:" flag || lib.hasPrefix "${name}=" flag) flags;
globalSettings = {
i = "0.0.0.0";
usernames = true;
"http-only" = true;
"no-crt" = true;
"no-thumb" = true;
"no-snap" = true;
"no-rescan" = true;
"ses-db" = "${serviceStateDir}/sessions.db";
"chpw-db" = "${serviceStateDir}/chpw.json";
"shr-db" = "${serviceStateDir}/shares.db";
}
// lib.optionalAttrs cfg.reverseProxy.enable {
rproxy = 1;
"xff-hdr" = "x-forwarded-for";
};
defaultPermissionFlags =
globalExtraConfig = lib.optionalString cfg.reverseProxy.enable (
lib.concatMapStringsSep "\n" (source: "xff-src: ${source}") cfg.reverseProxy.trustedSources
);
volumeFlags =
flags:
lib.optionals (!(hasFlag "chmod_d" flags)) [ "chmod_d: 2770" ]
++ lib.optionals (!(hasFlag "chmod_f" flags)) [ "chmod_f: 660" ];
lib.optionalAttrs (flags != { }) (
{
chmod_d = "2770";
chmod_f = "660";
}
// flags
);
renderFlags =
flags: lib.concatMapStringsSep "\n" (flag: " ${flag}") (flags ++ defaultPermissionFlags flags);
renderedVolumes = lib.mapAttrs (_urlPath: volume: {
inherit (volume) path;
access = if volume.readOnly then { r = [ accountName ]; } else defaultAccess // volume.access;
flags = volumeFlags (lib.optionalAttrs (!volume.readOnly) defaultWritableFlags // volume.flags);
}) cfg.volumes;
renderVolume = urlPath: volume: ''
[${urlPath}]
${volume.path}
accs:
${lib.concatStringsSep "\n" (lib.mapAttrsToList renderAccess volume.access)}
${lib.optionalString (volume.flags != [ ]) ''
flags:
${renderFlags volume.flags}
''}
configText = util.formats.copyparty.render {
inherit globalExtraConfig;
accounts.${accountName} = passwordPlaceholder;
global = globalSettings;
volumes = renderedVolumes;
};
configFile = pkgs.writeText "copyparty.conf" configText;
replacePassword = ''
${lib.getExe pkgs.replace-secret} ${lib.escapeShellArg passwordPlaceholder} "$CREDENTIALS_DIRECTORY/${credentialName}" /run/copyparty/copyparty.conf
'';
renderTrustedSource = source: " xff-src: ${source}";
renderedReverseProxy = lib.optionalString cfg.reverseProxy.enable ''
rproxy: 1
xff-hdr: x-forwarded-for
${lib.concatStringsSep "\n" (map renderTrustedSource cfg.reverseProxy.trustedSources)}
'';
renderedVolumes = lib.concatStringsSep "\n" (lib.mapAttrsToList renderVolume cfg.volumes);
in
{
options.modules.services.copyparty = {
enable = lib.mkEnableOption "Copyparty";
package = lib.mkPackageOption pkgs "copyparty-min" { };
port = lib.mkOption {
type = lib.types.port;
default = 3923;
description = "Port Copyparty listens on.";
};
user = lib.mkOption {
type = lib.types.str;
default = "copyparty";
description = "User account that runs Copyparty.";
};
group = lib.mkOption {
type = lib.types.str;
default = "storage";
description = "Group account that owns Copyparty's writable state and served files.";
};
accountName = lib.mkOption {
type = lib.types.str;
default = "alexion";
description = "Copyparty account name configured for password authentication.";
};
passwordFile = lib.mkOption {
type = lib.types.path;
description = "Runtime file containing the Copyparty account password.";
};
stateDir = lib.mkOption {
type = lib.types.str;
default = "/var/lib/copyparty";
description = "Directory where Copyparty stores service state.";
description = "Sets the runtime file that contains the Copyparty account password.";
};
volumes = lib.mkOption {
type = lib.types.attrsOf volumeType;
type = lib.types.attrsOf (
lib.types.submodule {
options = {
path = lib.mkOption {
type = lib.types.externalPath;
description = "Sets the filesystem path served by this volume.";
};
access = lib.mkOption {
type = lib.types.attrsOf (lib.types.listOf lib.types.str);
default = { };
example = {
A = [ "alexion" ];
};
description = "Maps Copyparty permission strings to account names.";
};
readOnly = lib.mkOption {
type = lib.types.bool;
default = false;
description = "Serves this volume read-only.";
};
flags = lib.mkOption {
type = lib.types.attrs;
default = { };
example = {
dthumb = true;
};
description = "Sets Copyparty volume flags.";
};
};
}
);
default = { };
description = "Copyparty volumes keyed by their URL path.";
description = "Defines Copyparty volumes by URL path.";
};
reverseProxy = {
@@ -151,7 +139,7 @@ in
trustedSources = lib.mkOption {
type = lib.types.listOf lib.types.str;
default = [ ];
description = "IP ranges that may supply Copyparty's forwarded client IP header.";
description = "Lists proxy sources that can set Copyparty's forwarded client IP header.";
};
};
};
@@ -173,46 +161,49 @@ in
}
];
users.users.${cfg.user} = {
users.users.${serviceUser} = {
isSystemUser = true;
uid = config.registry."stable-uid".${config.networking.hostName}.copyparty;
inherit (cfg) group;
home = cfg.stateDir;
group = serviceGroup;
home = serviceStateDir;
};
systemd.services.copyparty = {
description = "Copyparty file server";
after = [ "network.target" ];
wantedBy = [ "multi-user.target" ];
preStart = ''
${lib.getExe' pkgs.coreutils "install"} -m 600 ${configFile} /run/copyparty/copyparty.conf
${replacePassword}
'';
serviceConfig = {
ReloadSignal = "SIGUSR1";
Type = "simple";
User = cfg.user;
Group = cfg.group;
WorkingDirectory = cfg.stateDir;
User = serviceUser;
Group = serviceGroup;
WorkingDirectory = serviceStateDir;
Environment = [
"HOME=${cfg.stateDir}"
"XDG_CONFIG_HOME=${cfg.stateDir}"
"HOME=${serviceStateDir}"
"XDG_CONFIG_HOME=${serviceStateDir}"
];
StateDirectory = "copyparty";
RuntimeDirectory = "copyparty";
RuntimeDirectoryMode = "0700";
LoadCredential = [ "password:${cfg.passwordFile}" ];
ExecStartPre = configScript;
ExecStart = "${lib.getExe cfg.package} -c /run/copyparty/copyparty.conf";
LoadCredential = [ "${credentialName}:${cfg.passwordFile}" ];
ExecStart = "${lib.getExe pkgs.copyparty-min} -c /run/copyparty/copyparty.conf";
Restart = "on-failure";
NoNewPrivileges = true;
PrivateTmp = true;
ProtectSystem = "strict";
ProtectHome = true;
ReadWritePaths = [
cfg.stateDir
serviceStateDir
]
++ map (volume: volume.path) (lib.filter (volume: !volume.readOnly) (lib.attrValues cfg.volumes));
++ map (volume: volume.path) writableVolumes;
};
};
networking.firewall.allowedTCPPorts = [ cfg.port ];
networking.firewall.allowedTCPPorts = [ port ];
})
];
}

View File

@@ -5,7 +5,7 @@
...
}:
let
cfg = config.modules.services.homepage; # NOLINT(let_order)
cfg = config.modules.services.homepage;
derivedAllowedHosts = lib.unique (
lib.optional (selfRoute != null) selfRoute.domain
@@ -111,7 +111,8 @@ let
let
sectionOrder = sectionOrderByTab.${tab} or [ ];
in
sectionOrder ++ lib.filter (section: !lib.elem section sectionOrder) (lib.attrNames sections);
lib.filter (section: lib.hasAttr section sections) sectionOrder
++ lib.filter (section: !lib.elem section sectionOrder) (lib.attrNames sections);
in
{

View File

@@ -4,7 +4,7 @@
...
}:
let
cfg = config.modules.services.navidrome; # NOLINT(let_order)
cfg = config.modules.services.navidrome;
in
{
options.modules.services.navidrome = {

View File

@@ -1,25 +0,0 @@
{
config,
lib,
...
}:
# direnv for the primary user, configured through home-manager.
let
user = config.user.name;
in
{
options.modules.shell.direnv.enable =
lib.mkEnableOption "direnv for the primary user, with nix-direnv shell caching";
config = lib.mkIf config.modules.shell.direnv.enable {
home-manager.users.${user}.programs.direnv = {
enable = true;
silent = true;
# nix-direnv caches the evaluated shell so re-entering a directory is instant
# instead of re-running `nix develop`, and adds the `use flake` stdlib helper.
nix-direnv.enable = true;
stdlib = builtins.readFile ./repo-flake.sh;
};
};
}

View File

@@ -1,33 +0,0 @@
if declare -f use_flake >/dev/null; then
__dotfiles_use_flake_definition="$(declare -f use_flake)"
eval "${__dotfiles_use_flake_definition/use_flake/__dotfiles_nix_direnv_use_flake}"
unset __dotfiles_use_flake_definition
use_flake() {
local flake_expr="${1:-.}"
if [[ "$flake_expr" == //* ]]; then
local git_root
if ! git_root="$(git rev-parse --show-toplevel 2>/dev/null)"; then
log_error 'use flake // requires a Git repository'
return 1
fi
local flake_suffix="${flake_expr#//}"
if [[ -n "$flake_suffix" && "$flake_suffix" != \#* && "$flake_suffix" != /* ]]; then
flake_expr="path:${git_root}/${flake_suffix}"
else
flake_expr="path:${git_root}${flake_suffix}"
fi
shift
__dotfiles_nix_direnv_use_flake "$flake_expr" "$@"
return
fi
__dotfiles_nix_direnv_use_flake "$@"
}
else
log_error 'nix-direnv must define use_flake before the // wrapper loads'
return 1
fi

View File

@@ -6,7 +6,7 @@
}:
# fish for the primary user, configured through home-manager.
let
cfg = config.modules.shell.fish; # NOLINT(let_order)
cfg = config.modules.shell.fish;
commandsOf = shortcuts: lib.mapAttrs (_name: shortcut: shortcut.command) shortcuts;
shortcuts = lib.attrByPath [ config.networking.hostName ] { } config.registry.shell-shortcut;
user = config.user.name;

View File

@@ -12,18 +12,14 @@ let
piDir = "${config.users.users.${user}.home}/.pi/agent";
in
{
options.modules.shell.pi = {
enable = lib.mkEnableOption "Pi, a terminal coding agent, configured through home-manager";
};
options.modules.shell.pi.enable =
lib.mkEnableOption "Pi, a terminal coding agent, configured through home-manager";
config = lib.mkIf config.modules.shell.pi.enable {
home-manager.users.${user} = {
programs.pi-coding-agent = {
enable = true;
package = pkgs.pi-coding-agent.overrideAttrs {
src = ../../../../../third_party/pi;
patches = [ ];
};
package = pkgs.alexion.pi-coding-agent;
settings = {
defaultProvider = "openai-codex";

View File

@@ -3,7 +3,6 @@
- machoke
- falinks
- dotfiles
- natu
- nix-style / refactor
# project ideas
@@ -101,13 +100,6 @@
- https://www.youtube.com/watch?v=kzcI5F4tGiU
- https://www.youtube.com/watch?v=iKwPaB5TUdI
- https://www.youtube.com/watch?v=A-CtdQFRX64
- natu literature
- https://rust-analyzer.github.io/book/contributing/syntax.html?utm_source=chatgpt.com
- https://github.com/dotnet/roslyn/blob/main/docs/compilers/Design/Red-Green%20Trees.md?utm_source=chatgpt.com
- https://github.com/rust-analyzer/rowan/blob/master/examples/s_expressions.rs?utm_source=chatgpt.com
- https://dl.acm.org/doi/10.1145/964001.964011
- https://web.cecs.pdx.edu/~apt/esop15.pdf?utm_source=chatgpt.com
- https://www.researchgate.net/publication/2377179_Efficient_and_flexible_incremental_parsing?utm_source=chatgpt.com
# tech debt

View File

@@ -14,7 +14,7 @@ let
registry = registry.collected;
};
util = import ./util.nix { inherit lib; };
util = import ./util { inherit lib; };
registry = import ./registry.nix {
inherit lib util;
@@ -33,7 +33,12 @@ let
repositoryModules = modules;
root = root + "/guests";
};
modules.imports = util.collectNixFiles (root + "/modules");
modules.imports = [
{
nixpkgs.overlays = [ self.overlays.custom ];
}
]
++ util.collectNixFiles (root + "/modules");
in
import ./hosts.nix {

View File

@@ -21,8 +21,9 @@ let
value: entries: builtins.length (lib.unique (map value entries)) == builtins.length entries;
in
{
inherit collectNixFiles;
formats.copyparty = import ./format-copyparty.nix { inherit lib; };
inherit collectNixFiles;
removeNixSuffix = path: lib.removeSuffix ".nix" (builtins.baseNameOf path);
glyph =

View File

@@ -0,0 +1,58 @@
{ lib }:
let
renderLine =
indent: name: value:
if value == true then
"${indent}${name}"
else if value == false then
null
else if lib.isList value then
"${indent}${name}: ${lib.concatStringsSep ", " (map toString value)}"
else
"${indent}${name}: ${toString value}";
renderAttrs =
indent: attrs:
lib.pipe attrs [
lib.attrsToList
(map ({ name, value }: renderLine indent name value))
(lib.filter (line: line != null))
(lib.concatStringsSep "\n")
];
renderSectionName = name: "[${lib.escape [ "[" "]" ] name}]";
renderSection = name: attrs: ''
${renderSectionName name}
${renderAttrs "" attrs}
'';
renderSubsection =
name: attrs:
lib.optionalString (attrs != { }) ''
${name}:
${renderAttrs " " attrs}
'';
renderVolume = urlPath: volume: ''
${renderSectionName urlPath}
${volume.path}
${renderSubsection "accs" volume.access}
${renderSubsection "flags" volume.flags}
'';
in
{
render =
{
accounts,
global,
volumes,
globalExtraConfig ? "",
}:
''
${renderSection "global" global}
${globalExtraConfig}
${renderSection "accounts" accounts}
${lib.concatStringsSep "\n" (lib.mapAttrsToList renderVolume volumes)}
'';
}

View File

@@ -24,7 +24,6 @@ in
configs/nixos/hosts/neogaia/hardware-configuration.nix \
configs/nixos/hosts/pikachu/hardware-configuration.nix \
configs/nixos/hosts/zeus/hardware-configuration.nix \
src/natu/testdata \
third_party \
-- .
treefmt

View File

@@ -6,6 +6,19 @@
system,
}:
{
overlays.custom = final: _prev: {
alexion = import ./packages {
pkgs = final;
inherit root;
};
};
packages.${system} =
(import inputs.nixpkgs {
inherit system;
overlays = [ self.overlays.custom ];
}).alexion;
nixosConfigurations = import ../dotfiles {
inherit
inputs

View File

@@ -6,7 +6,6 @@ inputs.treefmt-nix.lib.evalModule inputs.nixpkgs.legacyPackages.${system} {
settings.formatter.nixfmt.excludes = [
"configs/nixos/hosts/*/hardware-configuration.nix"
"src/natu/testdata/*.nix"
"third_party/**"
];
}

View File

@@ -0,0 +1,8 @@
{ pkgs, root }:
{
pi-coding-agent = pkgs.callPackage ./pi-coding-agent.nix {
inherit root;
};
waybar = pkgs.callPackage ./waybar.nix { };
}

View File

@@ -0,0 +1,8 @@
{
pi-coding-agent,
root,
}:
pi-coding-agent.overrideAttrs {
src = root + "/third_party/pi";
patches = [ ];
}

View File

@@ -0,0 +1,28 @@
{
fetchFromGitHub,
waybar,
}:
waybar.overrideAttrs {
src = fetchFromGitHub {
owner = "Alexays";
repo = "Waybar";
rev = "05945748dccce28bf96d26d8f64a9e69a8dd49ba";
hash = "sha256-51R3mIt8cLNvh/X5qe9vOqeJCj0U9KRyemVE5y+OhiU=";
};
postUnpack =
let
libcava = fetchFromGitHub {
owner = "LukashonakV";
repo = "cava";
tag = "0.10.7";
hash = "sha256-zkyj1vBzHtoypX4Bxdh1Vmwh967DKKxN751v79hzmgQ=";
};
in
''
pushd "$sourceRoot"
cp -R --no-preserve=mode,ownership ${libcava} subprojects/cava-0.10.7
patchShebangs .
popd
'';
}

View File

@@ -1,59 +0,0 @@
load("@rules_rust//rust:defs.bzl", "rust_binary", "rust_library", "rust_test")
rust_library(
name = "natu_lib",
crate_name = "natu",
srcs = [
"ast.rs",
"file_store.rs",
"natu.rs",
"parser.rs",
"rules.rs",
"rules/let_order.rs",
"rules/list_to_attrs_map.rs",
"rules/manual_inherit.rs",
"rules/manual_inherit_from.rs",
"rules/redundant_let.rs",
"rules/redundant_parameter_forwarding.rs",
"rules/unquoted_uri.rs",
"scope_graph.rs",
],
deps = [
"//src/status:status",
"//third_party/crates:rnix",
"//third_party/crates/rowan-0.16.1:rowan",
],
)
rust_test(
name = "file_store_test",
srcs = ["file_store_test.rs"],
deps = [":natu_lib"],
)
rust_test(
name = "natu_test",
srcs = ["natu_test.rs"],
data = [
"testdata/clean.nix",
"testdata/invalid.nix",
"testdata/lint_findings.nix",
],
deps = [
":natu_lib",
"//src/status:status",
"//third_party/crates:googletest",
],
)
rust_binary(
name = "natu",
crate_name = "natu_cli",
srcs = ["natu_main.rs"],
deps = [
":natu_lib",
"//src/monorepo:monorepo",
"//src/status:status",
"//third_party/crates:clap",
],
)

View File

@@ -1,21 +0,0 @@
[package]
name = "natu"
version = "0.1.0"
edition = "2024"
[lib]
path = "natu.rs"
[[bin]]
name = "natu"
path = "natu_main.rs"
[dependencies]
clap = { workspace = true, features = ["derive"] }
monorepo = { workspace = true }
rnix = { workspace = true }
rowan = { workspace = true }
status = { workspace = true }
[dev-dependencies]
googletest = { workspace = true }

View File

@@ -1,92 +0,0 @@
use crate::FileId;
#[derive(Debug)]
pub struct ParsedFile {
pub file_id: FileId,
pub root: Expr,
pub nodes: Vec<Node>,
pub tokens: Vec<Token>,
pub errors: Vec<ParseError>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Node {
pub range: SourceRange,
pub data: NodeData,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SourceRange {
pub start: usize,
pub end: usize,
}
impl std::fmt::Display for SourceRange {
fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(formatter, "{}..{}", self.start, self.end)
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum NodeData {
Binding(Binding),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Binding {
pub range: SourceRange,
pub key: Ident,
pub value: Expr,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Ident {
pub name: String,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expr {
Ident(Ident),
Select(Select),
Apply(Apply),
Let {
range: SourceRange,
bindings: Vec<Binding>,
body: Box<Expr>,
},
AttrSet(Vec<Binding>),
Lambda {
parameters: Vec<Ident>,
body: Box<Expr>,
},
Other(Vec<Expr>),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Select {
pub receiver: String,
pub attr: Ident,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Apply {
pub lambda: Box<Expr>,
pub argument: Box<Expr>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Token {
pub range: SourceRange,
pub data: TokenData,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum TokenData {
UnquotedUri(String),
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ParseError {
pub range: SourceRange,
pub message: String,
}

View File

@@ -1,33 +0,0 @@
use std::path::PathBuf;
#[derive(Debug, Default)]
pub struct FileStore {
files: Vec<SourceFile>,
}
impl FileStore {
pub fn add(&mut self, file: SourceFile) -> FileId {
let id = FileId(self.files.len());
self.files.push(file);
id
}
pub fn get(&self, id: FileId) -> &SourceFile {
&self.files[id.0]
}
}
impl From<Vec<SourceFile>> for FileStore {
fn from(files: Vec<SourceFile>) -> Self {
Self { files }
}
}
#[derive(Debug)]
pub struct SourceFile {
pub path: PathBuf,
pub source: String,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct FileId(usize);

View File

@@ -1,33 +0,0 @@
use std::path::PathBuf;
use natu::{FileStore, SourceFile};
fn source_file(path: &str, source: &str) -> SourceFile {
SourceFile {
path: PathBuf::from(path),
source: source.to_owned(),
}
}
#[test]
fn added_file_can_be_retrieved_by_id() {
let mut store = FileStore::default();
let id = store.add(source_file("first.nix", "{ inherit foo; }"));
let file = store.get(id);
assert_eq!(PathBuf::from("first.nix"), file.path);
assert_eq!("{ inherit foo; }", file.source);
}
#[test]
fn file_ids_refer_to_their_added_files() {
let mut store = FileStore::default();
let first = store.add(source_file("first.nix", "first"));
let second = store.add(source_file("second.nix", "second"));
assert_ne!(first, second);
assert_eq!("first", store.get(first).source);
assert_eq!("second", store.get(second).source);
}

View File

@@ -1,121 +0,0 @@
use std::collections::HashSet;
mod ast;
mod file_store;
mod parser;
mod rules;
mod scope_graph;
use scope_graph::ScopeGraph;
pub use file_store::{FileId, FileStore, SourceFile};
pub use rules::{Diagnostic, Finding};
#[derive(Debug)]
pub struct Report {
pub files: FileStore,
pub diagnostics: Vec<Diagnostic>,
}
impl Report {
pub fn is_clean(&self) -> bool {
self.diagnostics.is_empty()
}
}
impl std::fmt::Display for Report {
fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let mut reported_let_order_files = HashSet::new();
for diagnostic in &self.diagnostics {
if diagnostic.finding.rule_id == "let_order" {
if !reported_let_order_files.insert(diagnostic.file_id) {
continue;
}
let file = self.files.get(diagnostic.file_id);
writeln!(
formatter,
"{} [let_order] Let bindings must follow dependency order",
file.path.display()
)?;
let mut findings = self
.diagnostics
.iter()
.filter(|candidate| {
candidate.file_id == diagnostic.file_id
&& candidate.finding.rule_id == "let_order"
})
.collect::<Vec<_>>();
findings.sort_by_key(|finding| finding.finding.range.start);
for finding in findings {
let (start, _) = line_range(&file.source, finding.finding.range);
let expected_order =
finding.finding.expected_order.as_ref().expect("let order");
writeln!(
formatter,
" let at line {start}: {}",
expected_order.join(", ")
)?;
}
continue;
}
let file = self.files.get(diagnostic.file_id);
let (start, end) = line_range(&file.source, diagnostic.finding.range);
let location = if start == end {
start.to_string()
} else {
format!("{start}-{end}")
};
writeln!(formatter, "{}:{location} {diagnostic}", file.path.display())?;
}
Ok(())
}
}
fn line_range(source: &str, range: ast::SourceRange) -> (usize, usize) {
let line_at = |offset| {
source
.bytes()
.take(offset)
.filter(|byte| *byte == b'\n')
.count()
+ 1
};
let start = line_at(range.start);
let end = line_at(range.end);
(start, end)
}
/// Analyzes source files and returns the diagnostics Natu finds.
pub fn future_sight(files: Vec<SourceFile>) -> status::Result<Report> {
let mut store = FileStore::default();
let mut diagnostics = Vec::new();
for file in files {
let file_id = store.add(file);
let file = store.get(file_id);
let parsed = parser::parse_file(file_id, &file.source);
if !parsed.errors.is_empty() {
return Err(status::Status::failed_precondition(format!(
"failed to parse {}",
file.path.display()
)));
}
let graph = ScopeGraph::from_file(&parsed);
diagnostics.extend(rules::run_rules(&parsed, &graph, &file.source));
}
Ok(Report {
files: store,
diagnostics,
})
}

View File

@@ -1,105 +0,0 @@
use clap::Parser;
use natu::{Report, SourceFile};
use status::ResultExt;
use std::path::{Path, PathBuf};
use std::process::ExitCode;
fn main() -> ExitCode {
let args = Args::parse();
match analyze(args) {
Ok(report) if report.is_clean() => {
println!("No findings.");
ExitCode::SUCCESS
}
Ok(report) => {
print!("{report}");
ExitCode::from(1)
}
Err(error) => {
eprintln!("{error}");
ExitCode::from(2)
}
}
}
#[derive(Debug, Parser)]
struct Args {
#[arg(value_name = "PATH", default_value = ".")]
paths: Vec<PathBuf>,
}
fn analyze(args: Args) -> status::Result<Report> {
let paths: Vec<PathBuf> = args
.paths
.into_iter()
.map(monorepo::workspace::resolve_workspace_path)
.collect();
let files: Vec<SourceFile> = paths
.iter()
.map(|path| collect_source_files(path))
.collect::<status::Result<Vec<_>>>()?
.into_iter()
.flatten()
.collect();
natu::future_sight(files)
}
fn collect_source_files(path: &Path) -> status::Result<Vec<SourceFile>> {
let metadata = std::fs::symlink_metadata(path)
.with_context(|| format!("failed to read metadata for {}", path.display()))?;
if metadata.file_type().is_dir() {
if is_excluded_dir(path) {
return Ok(Vec::new());
}
let mut files = Vec::new();
for entry in std::fs::read_dir(path)
.with_context(|| format!("failed to read directory {}", path.display()))?
{
let entry =
entry.with_context(|| format!("failed to read entry in {}", path.display()))?;
files.extend(collect_source_files(&entry.path())?);
}
return Ok(files);
}
if metadata.file_type().is_file() && is_nix_file(path) {
return Ok(vec![SourceFile {
path: path.to_path_buf(),
source: std::fs::read_to_string(path)
.with_context(|| format!("failed to read source file {}", path.display()))?,
}]);
}
Ok(Vec::new())
}
// TODO: Add configurable exclusions.
fn is_excluded_dir(path: &Path) -> bool {
path.file_name()
.and_then(|name| name.to_str())
.is_some_and(|name| {
matches!(
name,
".git"
| "bazel-bin"
| "bazel-dev"
| "bazel-out"
| "bazel-testlogs"
| "target"
| "testdata"
| "third_party"
) || name == "result"
|| name.starts_with("result-")
})
}
fn is_nix_file(path: &Path) -> bool {
path.extension().is_some_and(|extension| extension == "nix")
}

View File

@@ -1,303 +0,0 @@
use std::path::{Path, PathBuf};
use googletest::matchers::{contains, eq, is_true};
use googletest::{OrFail, expect_that, gtest};
use status::Code;
use natu::SourceFile;
fn fixture_source(path: &str) -> googletest::Result<SourceFile> {
Ok(SourceFile {
path: PathBuf::from(path),
source: std::fs::read_to_string(fixture_path(path)?).or_fail()?,
})
}
fn fixture_path(path: &str) -> googletest::Result<PathBuf> {
if Path::new(path).exists() {
return Ok(PathBuf::from(path));
}
let runfiles = PathBuf::from(std::env::var("TEST_SRCDIR").or_fail()?);
let workspace = std::env::var("TEST_WORKSPACE").or_fail()?;
Ok(runfiles.join(workspace).join("src/natu").join(path))
}
#[gtest]
fn natu_accepts_clean_source() -> googletest::Result<()> {
let report = natu::future_sight(vec![fixture_source("testdata/clean.nix")?]).or_fail()?;
expect_that!(report.is_clean(), is_true());
Ok(())
}
#[gtest]
fn natu_rejects_invalid_source() -> googletest::Result<()> {
let error = natu::future_sight(vec![fixture_source("testdata/invalid.nix")?])
.err()
.or_fail()?;
expect_that!(error.code(), eq(Code::FailedPrecondition));
Ok(())
}
#[gtest]
fn natu_reports_out_of_order_let_bindings() -> googletest::Result<()> {
let report = natu::future_sight(vec![fixture_source("testdata/lint_findings.nix")?]).or_fail()?;
let let_order_count = report
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.finding.rule_id == "let_order")
.count();
expect_that!(let_order_count, eq(2));
expect_that!(
report.to_string(),
eq(concat!(
"testdata/lint_findings.nix:11 [manual_inherit] Use `inherit` for this assignment\n",
"testdata/lint_findings.nix:12 [manual_inherit_from] Use `inherit` for this selected attribute\n",
"testdata/lint_findings.nix:13 [unquoted_uri] URI literals should be quoted\n",
"testdata/lint_findings.nix [let_order] Let bindings must follow dependency order\n",
" let at line 1: first, second, nested\n",
" let at line 4: nestedSecond, nestedFirst\n",
))
);
Ok(())
}
#[gtest]
fn natu_preserves_suppressed_bindings() -> googletest::Result<()> {
let report = natu::future_sight(vec![SourceFile {
path: PathBuf::from("testdata/nolint.nix"),
source: "{ config, ... }: let # NOLINT(redundant_let)\n cfg = config.example; # NOLINT(let_order)\n value = cfg;\nin value\n".into(),
}])
.or_fail()?;
expect_that!(report.is_clean(), is_true());
Ok(())
}
#[gtest]
fn natu_reports_select_dependency_order() -> googletest::Result<()> {
let report = natu::future_sight(vec![SourceFile {
path: PathBuf::from("testdata/select_dependencies.nix"),
source: r#"
let
dependency = { value = 1; };
entry = dependency.value;
in
entry
"#
.into(),
}])
.or_fail()?;
let count = report
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.finding.rule_id == "let_order")
.count();
expect_that!(count, eq(1));
Ok(())
}
#[gtest]
fn natu_reports_redundant_let() -> googletest::Result<()> {
let report = natu::future_sight(vec![SourceFile {
path: PathBuf::from("testdata/redundant_let.nix"),
source: r#"
let
helper = 1;
value = helper;
in
value
"#
.into(),
}])
.or_fail()?;
let count = report
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.finding.rule_id == "redundant_let")
.count();
expect_that!(count, eq(1));
Ok(())
}
#[gtest]
fn natu_accepts_nonredundant_let() -> googletest::Result<()> {
let report = natu::future_sight(vec![
SourceFile {
path: PathBuf::from("testdata/recursive_let.nix"),
source: r#"
let
recursive = recursive;
in
recursive
"#
.into(),
},
SourceFile {
path: PathBuf::from("testdata/dependent_let.nix"),
source: r#"
let
value = 1;
dependent = value;
in
value
"#
.into(),
},
])
.or_fail()?;
let count = report
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.finding.rule_id == "redundant_let")
.count();
expect_that!(count, eq(0));
Ok(())
}
#[gtest]
fn natu_reports_redundant_parameter_forwarding() -> googletest::Result<()> {
let report = natu::future_sight(vec![
SourceFile {
path: PathBuf::from("testdata/attribute_parameter.nix"),
source: r#"
{ hosts, ... }:
let
collect = { hosts }: hosts;
in
collect { inherit hosts; }
"#
.into(),
},
SourceFile {
path: PathBuf::from("testdata/plain_parameter.nix"),
source: r#"
value:
let
transform = value: value;
in
transform value
"#
.into(),
},
SourceFile {
path: PathBuf::from("testdata/curried_parameter.nix"),
source: r#"
{ hosts, ... }:
let
transform = prefix: hosts: suffix: hosts;
in
transform "prefix" hosts "suffix"
"#
.into(),
},
SourceFile {
path: PathBuf::from("testdata/local_parameter.nix"),
source: r#"
let
transform = value: value;
in
transform value
"#
.into(),
},
])
.or_fail()?;
let count = report
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.finding.rule_id == "redundant_parameter_forwarding")
.count();
expect_that!(count, eq(3));
Ok(())
}
#[gtest]
fn natu_reports_list_to_attrs_after_map() -> googletest::Result<()> {
let report = natu::future_sight(vec![SourceFile {
path: PathBuf::from("testdata/list_to_attrs.nix"),
source: r#"
let
generated = lib.listToAttrs (
map (item: lib.nameValuePair item item) items
);
generated_pairs = lib.listToAttrs (
concatLists (
mapAttrsToList (name: _: lib.nameValuePair name name) attrs
)
);
precomputed = lib.listToAttrs pairs;
in
{
inherit generated generated_pairs precomputed;
}
"#
.into(),
}])
.or_fail()?;
let count = report
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.finding.rule_id == "list_to_attrs_map")
.count();
expect_that!(count, eq(1));
Ok(())
}
#[gtest]
fn natu_reports_unquoted_uri() -> googletest::Result<()> {
let report = natu::future_sight(vec![fixture_source("testdata/lint_findings.nix")?]).or_fail()?;
let findings = report
.diagnostics
.iter()
.map(|diagnostic| {
(
report.files.get(diagnostic.file_id).path.clone(),
diagnostic.finding.rule_id,
)
})
.collect::<Vec<_>>();
expect_that!(
findings,
contains(eq(&(
PathBuf::from("testdata/lint_findings.nix"),
"unquoted_uri"
)))
);
Ok(())
}
#[gtest]
fn natu_reports_manual_inherit() -> googletest::Result<()> {
let report = natu::future_sight(vec![fixture_source("testdata/lint_findings.nix")?]).or_fail()?;
let manual_inherit_count = report
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.finding.rule_id == "manual_inherit")
.count();
expect_that!(manual_inherit_count, eq(1));
Ok(())
}
#[gtest]
fn natu_reports_manual_inherit_from() -> googletest::Result<()> {
let report = natu::future_sight(vec![fixture_source("testdata/lint_findings.nix")?]).or_fail()?;
let manual_inherit_from_count = report
.diagnostics
.iter()
.filter(|diagnostic| diagnostic.finding.rule_id == "manual_inherit_from")
.count();
expect_that!(manual_inherit_from_count, eq(1));
Ok(())
}

View File

@@ -1,295 +0,0 @@
use rnix::ast::{Attr, HasEntry};
use rowan::ast::AstNode;
use crate::{FileId, ast};
pub fn parse_file(file_id: FileId, source: &str) -> ast::ParsedFile {
let parse = rnix::Root::parse(source);
let source_len = source.len();
let syntax = parse.syntax();
let root = rnix::ast::Root::cast(syntax.clone()).expect("parser root is a root node");
let root = convert_expr(root.expr().expect("parser root has an expression"));
let (nodes, tokens) = convert_syntax(syntax);
ast::ParsedFile {
file_id,
root,
nodes,
tokens,
errors: parse
.errors()
.iter()
.map(|error| convert_parse_error(error, source_len))
.collect(),
}
}
fn convert_syntax(syntax: rnix::SyntaxNode) -> (Vec<ast::Node>, Vec<ast::Token>) {
let mut nodes = Vec::new();
let mut tokens = Vec::new();
for element in syntax.descendants_with_tokens() {
match element {
rnix::NodeOrToken::Node(node) => nodes.extend(convert_node(node)),
rnix::NodeOrToken::Token(token) => tokens.extend(convert_token(token)),
}
}
(nodes, tokens)
}
fn convert_expr(expr: rnix::ast::Expr) -> ast::Expr {
match expr {
rnix::ast::Expr::Ident(ident) => ast::Expr::Ident(ident.into()),
rnix::ast::Expr::Select(select) => convert_select_expr(select),
rnix::ast::Expr::Apply(apply) => ast::Expr::Apply(ast::Apply {
lambda: Box::new(convert_expr(apply.lambda().expect("applications have a lambda"))),
argument: Box::new(convert_expr(
apply.argument().expect("applications have an argument"),
)),
}),
rnix::ast::Expr::LetIn(let_in) => ast::Expr::Let {
range: let_in.syntax().text_range().into(),
bindings: let_in
.attrpath_values()
.filter_map(convert_binding_ast)
.collect(),
body: Box::new(convert_expr(
let_in.body().expect("let expressions have bodies"),
)),
},
rnix::ast::Expr::AttrSet(attr_set) => ast::Expr::AttrSet(convert_attr_set(attr_set)),
rnix::ast::Expr::Lambda(lambda) => ast::Expr::Lambda {
parameters: lambda_parameters(&lambda),
body: Box::new(convert_expr(lambda.body().expect("lambdas have bodies"))),
},
expr => ast::Expr::Other(
expr.syntax()
.children()
.filter_map(rnix::ast::Expr::cast)
.map(convert_expr)
.collect(),
),
}
}
fn convert_select_expr(select: rnix::ast::Select) -> ast::Expr {
select.clone().try_into().map(ast::Expr::Select).unwrap_or_else(|_| {
ast::Expr::Other(
select
.syntax()
.children()
.filter_map(rnix::ast::Expr::cast)
.map(convert_expr)
.collect(),
)
})
}
fn convert_binding_ast(binding: rnix::ast::AttrpathValue) -> Option<ast::Binding> {
let mut attrs = binding.attrpath()?.attrs();
let Attr::Ident(key) = attrs.next()? else {
return None;
};
Some(ast::Binding {
range: binding.syntax().text_range().into(),
key: key.into(),
value: convert_expr(binding.value()?),
})
}
fn convert_attr_set(attr_set: rnix::ast::AttrSet) -> Vec<ast::Binding> {
attr_set
.entries()
.flat_map(|entry| match entry {
rnix::ast::Entry::AttrpathValue(binding) => {
convert_binding_ast(binding).into_iter().collect()
}
rnix::ast::Entry::Inherit(inherit) => convert_inherit(inherit),
})
.collect()
}
fn convert_inherit(inherit: rnix::ast::Inherit) -> Vec<ast::Binding> {
let value = inherit
.from()
.and_then(|from| from.expr())
.map(convert_expr);
inherit
.attrs()
.filter_map(|attr| match attr {
Attr::Ident(ident) => Some(ident),
_ => None,
})
.map(|key| ast::Binding {
range: key.syntax().text_range().into(),
value: value
.clone()
.unwrap_or_else(|| ast::Expr::Ident(key.clone().into())),
key: key.into(),
})
.collect()
}
fn lambda_parameters(lambda: &rnix::ast::Lambda) -> Vec<ast::Ident> {
match lambda.param() {
Some(rnix::ast::Param::IdentParam(parameter)) => {
parameter.ident().map(Into::into).into_iter().collect()
}
Some(rnix::ast::Param::Pattern(pattern)) => pattern
.pat_entries()
.filter_map(|entry| entry.ident())
.chain(pattern.pat_bind().and_then(|binding| binding.ident()))
.map(Into::into)
.collect(),
None => Vec::new(),
}
}
fn convert_node(node: rnix::SyntaxNode) -> Option<ast::Node> {
match node.kind() {
rnix::SyntaxKind::NODE_ATTRPATH_VALUE => convert_binding(node),
_ => None,
}
}
fn convert_binding(node: rnix::SyntaxNode) -> Option<ast::Node> {
let binding = rnix::ast::AttrpathValue::cast(node)?;
let range = binding.syntax().text_range().into();
let mut attrs = binding.attrpath()?.attrs();
let Attr::Ident(key) = attrs.next()? else {
return None;
};
if attrs.next().is_some() {
return None;
}
Some(ast::Node {
range,
data: ast::NodeData::Binding(ast::Binding {
range,
key: key.into(),
value: convert_expr(binding.value()?),
}),
})
}
impl TryFrom<rnix::ast::AttrpathValue> for ast::Binding {
type Error = ();
fn try_from(binding: rnix::ast::AttrpathValue) -> Result<Self, Self::Error> {
let mut attrs = binding.attrpath().ok_or(())?.attrs();
let key = match attrs.next().ok_or(())? {
Attr::Ident(ident) => ident.into(),
_ => return Err(()),
};
if attrs.next().is_some() {
return Err(());
}
let value = binding.value().ok_or(())?.try_into()?;
Ok(Self {
range: binding.syntax().text_range().into(),
key,
value,
})
}
}
impl TryFrom<rnix::ast::Expr> for ast::Expr {
type Error = ();
fn try_from(expr: rnix::ast::Expr) -> Result<Self, Self::Error> {
match expr {
rnix::ast::Expr::Ident(ident) => Ok(Self::Ident(ident.into())),
rnix::ast::Expr::Select(select) => Ok(Self::Select(select.try_into()?)),
_ => Err(()),
}
}
}
impl From<rnix::ast::Ident> for ast::Ident {
fn from(ident: rnix::ast::Ident) -> Self {
Self {
name: ident.to_string(),
}
}
}
impl TryFrom<rnix::ast::Select> for ast::Select {
type Error = ();
fn try_from(select: rnix::ast::Select) -> Result<Self, Self::Error> {
if select.or_token().is_some() {
return Err(());
}
let mut attrs = select.attrpath().ok_or(())?.attrs();
let attr = match attrs.next().ok_or(())? {
Attr::Ident(ident) => ident.into(),
_ => return Err(()),
};
if attrs.next().is_some() {
return Err(());
}
Ok(Self {
receiver: select.expr().ok_or(())?.syntax().to_string(),
attr,
})
}
}
fn convert_token(token: rnix::SyntaxToken) -> Option<ast::Token> {
match token.kind() {
rnix::SyntaxKind::TOKEN_URI => Some(ast::Token {
range: token.text_range().into(),
data: ast::TokenData::UnquotedUri(token.text().to_string()),
}),
_ => None,
}
}
fn convert_parse_error(error: &rnix::ParseError, source_len: usize) -> ast::ParseError {
ast::ParseError {
range: parse_error_range(error, source_len),
message: error.to_string(),
}
}
fn parse_error_range(error: &rnix::ParseError, source_len: usize) -> ast::SourceRange {
match error {
rnix::ParseError::Unexpected(range)
| rnix::ParseError::UnexpectedExtra(range)
| rnix::ParseError::UnexpectedWanted(_, range, _)
| rnix::ParseError::UnexpectedDoubleBind(range)
| rnix::ParseError::DuplicatedArgs(range, _) => (*range).into(),
rnix::ParseError::UnexpectedEOF
| rnix::ParseError::UnexpectedEOFWanted(_)
| rnix::ParseError::RecursionLimitExceeded => ast::SourceRange {
start: source_len,
end: source_len,
},
_ => ast::SourceRange {
start: source_len,
end: source_len,
},
}
}
impl From<rnix::TextRange> for ast::SourceRange {
fn from(range: rnix::TextRange) -> Self {
Self {
start: usize::from(range.start()),
end: usize::from(range.end()),
}
}
}

View File

@@ -1,187 +0,0 @@
use crate::FileId;
use crate::ast;
use crate::rules::list_to_attrs_map::ListToAttrsMap;
use crate::rules::manual_inherit::ManualInherit;
use crate::rules::manual_inherit_from::ManualInheritFrom;
use crate::rules::unquoted_uri::UnquotedUri;
use crate::scope_graph::ScopeGraph;
pub mod let_order;
pub mod list_to_attrs_map;
pub mod manual_inherit;
pub mod manual_inherit_from;
pub mod redundant_let;
pub mod redundant_parameter_forwarding;
pub mod unquoted_uri;
#[derive(Debug)]
pub struct Diagnostic {
pub file_id: FileId,
pub finding: Finding,
}
#[derive(Debug)]
pub struct Finding {
pub rule_id: &'static str,
pub range: ast::SourceRange,
pub message: &'static str,
pub binding: Option<String>,
pub expected_order: Option<Vec<String>>,
}
impl std::fmt::Display for Diagnostic {
fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(
formatter,
"[{}] {}",
self.finding.rule_id, self.finding.message
)?;
if let Some(binding) = &self.finding.binding {
write!(formatter, ": {binding}")?;
}
Ok(())
}
}
pub trait NodeRule {
type Node;
const ID: &'static str;
fn select(data: &ast::NodeData) -> Option<&Self::Node>;
fn check(node: &Self::Node) -> Option<&'static str>;
}
pub trait TokenRule {
type Token;
const ID: &'static str;
fn select(data: &ast::TokenData) -> Option<&Self::Token>;
fn check(token: &Self::Token) -> Option<&'static str>;
}
pub fn run_rules(file: &ast::ParsedFile, graph: &ScopeGraph, source: &str) -> Vec<Diagnostic> {
let node_diagnostics = file
.nodes
.iter()
.flat_map(|node| {
[
run_node_rule::<ListToAttrsMap>(node),
run_node_rule::<ManualInherit>(node),
run_node_rule::<ManualInheritFrom>(node),
]
})
.flatten();
let token_diagnostics = file
.tokens
.iter()
.flat_map(|token| [run_token_rule::<UnquotedUri>(token)])
.flatten();
let let_order_diagnostics =
let_order::check(graph, source)
.into_iter()
.map(|finding| Finding {
rule_id: "let_order",
range: finding.range,
message: "Let bindings must follow dependency order",
binding: None,
expected_order: Some(finding.expected_order),
});
let redundant_let_diagnostics =
redundant_let::check(&file.root)
.into_iter()
.map(|finding| Finding {
rule_id: "redundant_let",
range: finding.range,
message: "Inline this returned let binding",
binding: None,
expected_order: None,
});
let redundant_parameter_forwarding_diagnostics =
redundant_parameter_forwarding::check(&file.root)
.into_iter()
.map(|finding| Finding {
rule_id: "redundant_parameter_forwarding",
range: finding.range,
message: "Use the outer parameter instead of forwarding it",
binding: None,
expected_order: None,
});
node_diagnostics
.chain(token_diagnostics)
.chain(let_order_diagnostics)
.chain(redundant_let_diagnostics)
.chain(redundant_parameter_forwarding_diagnostics)
.filter(|finding| !is_suppressed(source, finding.range, finding.rule_id))
.map(|finding| Diagnostic {
file_id: file.file_id,
finding,
})
.collect()
}
pub fn is_suppressed(source: &str, range: ast::SourceRange, rule_id: &str) -> bool {
let line = source[range.start..].lines().next().unwrap_or_default();
line_suppresses(line, rule_id) || preceding_line_suppresses(source, range, rule_id)
}
fn preceding_line_suppresses(source: &str, range: ast::SourceRange, rule_id: &str) -> bool {
let Some((preceding_source, _current_line)) = source[..range.start].rsplit_once('\n') else {
return false;
};
let preceding_line = preceding_source.lines().next_back().unwrap_or_default();
line_suppresses(preceding_line, rule_id)
}
fn line_suppresses(line: &str, rule_id: &str) -> bool {
let Some(comment) = line.split_once('#').map(|(_, comment)| comment.trim()) else {
return false;
};
if comment == "NOLINT" {
return true;
}
comment
.strip_prefix("NOLINT(")
.and_then(|rules| rules.strip_suffix(')'))
.is_some_and(|rules| {
rules
.split(',')
.any(|candidate| candidate.trim() == rule_id)
})
}
fn run_node_rule<R>(node: &ast::Node) -> Option<Finding>
where
R: NodeRule,
{
let typed_node = R::select(&node.data)?;
let message = R::check(typed_node)?;
Some(Finding {
rule_id: R::ID,
range: node.range,
message,
binding: None,
expected_order: None,
})
}
fn run_token_rule<R>(token: &ast::Token) -> Option<Finding>
where
R: TokenRule,
{
let typed_token = R::select(&token.data)?;
let message = R::check(typed_token)?;
Some(Finding {
rule_id: R::ID,
range: token.range,
message,
binding: None,
expected_order: None,
})
}

View File

@@ -1,87 +0,0 @@
use crate::{
ast,
rules::is_suppressed,
scope_graph::{LetScope, NodeId, ScopeGraph},
};
pub struct Finding {
pub range: ast::SourceRange,
pub expected_order: Vec<String>,
}
pub fn check(graph: &ScopeGraph, source: &str) -> Vec<Finding> {
graph
.let_scopes()
.iter()
.flat_map(|let_scope| {
let expected = expected_order(graph, let_scope)
.into_iter()
.filter(|declaration| !binding_suppressed(let_scope, *declaration, source))
.collect::<Vec<_>>();
let actual = let_scope
.bindings
.iter()
.filter(|binding| !is_suppressed(source, binding.range, "let_order"))
.map(|binding| binding.declaration)
.collect::<Vec<_>>();
(!actual.starts_with(&expected)).then(|| Finding {
range: let_scope.range,
expected_order: expected
.iter()
.map(|declaration| binding_name(let_scope, *declaration).to_owned())
.collect(),
})
})
.collect()
}
fn binding_suppressed(let_scope: &LetScope, declaration: NodeId, source: &str) -> bool {
let binding = let_scope
.bindings
.iter()
.find(|binding| binding.declaration == declaration)
.expect("let declaration");
is_suppressed(source, binding.range, "let_order")
}
fn binding_name(let_scope: &LetScope, declaration: NodeId) -> &str {
&let_scope
.bindings
.iter()
.find(|binding| binding.declaration == declaration)
.expect("let declaration")
.name
}
fn expected_order(graph: &ScopeGraph, let_scope: &LetScope) -> Vec<NodeId> {
let mut order = Vec::new();
visit_references(graph, &let_scope.entry_references, let_scope, &mut order);
order
}
fn visit_references(
graph: &ScopeGraph,
references: &[NodeId],
let_scope: &LetScope,
order: &mut Vec<NodeId>,
) {
for reference in references {
for declaration in graph.resolve(*reference) {
let Some(binding) = let_scope
.bindings
.iter()
.find(|binding| binding.declaration == declaration)
else {
continue;
};
if order.contains(&declaration) {
continue;
}
order.push(declaration);
visit_references(graph, &binding.references, let_scope, order);
}
}
}

View File

@@ -1,58 +0,0 @@
use crate::{ast, rules::NodeRule};
pub struct ListToAttrsMap;
impl NodeRule for ListToAttrsMap {
type Node = ast::Binding;
const ID: &'static str = "list_to_attrs_map";
fn select(data: &ast::NodeData) -> Option<&Self::Node> {
let ast::NodeData::Binding(binding) = data;
Some(binding)
}
fn check(node: &Self::Node) -> Option<&'static str> {
matches_list_to_attrs_map(&node.value)
.then_some("Use `lib.genAttrs'` instead of `lib.listToAttrs` after `map`")
}
}
fn matches_list_to_attrs_map(expr: &ast::Expr) -> bool {
let ast::Expr::Apply(application) = unwrap_expr(expr) else {
return false;
};
is_lib_list_to_attrs(&application.lambda) && is_map_application(&application.argument)
}
fn unwrap_expr(expr: &ast::Expr) -> &ast::Expr {
match expr {
ast::Expr::Other(expressions) if expressions.len() == 1 => unwrap_expr(&expressions[0]),
_ => expr,
}
}
fn is_lib_list_to_attrs(expr: &ast::Expr) -> bool {
matches!(
unwrap_expr(expr),
ast::Expr::Select(select) if select.receiver == "lib" && select.attr.name == "listToAttrs"
)
}
fn is_map_application(expr: &ast::Expr) -> bool {
let ast::Expr::Apply(application) = unwrap_expr(expr) else {
return false;
};
is_map(&application.lambda)
}
fn is_map(expr: &ast::Expr) -> bool {
match unwrap_expr(expr) {
ast::Expr::Ident(ident) => ident.name == "map",
ast::Expr::Apply(application) => is_map(&application.lambda),
_ => false,
}
}

View File

@@ -1,24 +0,0 @@
use crate::{ast, rules::NodeRule};
pub struct ManualInherit;
impl NodeRule for ManualInherit {
type Node = ast::Binding;
const ID: &'static str = "manual_inherit";
fn select(data: &ast::NodeData) -> Option<&Self::Node> {
let ast::NodeData::Binding(binding) = data;
Some(binding)
}
fn check(node: &Self::Node) -> Option<&'static str> {
match &node.value {
ast::Expr::Ident(value) if node.key == *value => {
Some("Use `inherit` for this assignment")
}
_ => None,
}
}
}

View File

@@ -1,24 +0,0 @@
use crate::{ast, rules::NodeRule};
pub struct ManualInheritFrom;
impl NodeRule for ManualInheritFrom {
type Node = ast::Binding;
const ID: &'static str = "manual_inherit_from";
fn select(data: &ast::NodeData) -> Option<&Self::Node> {
let ast::NodeData::Binding(binding) = data;
Some(binding)
}
fn check(node: &Self::Node) -> Option<&'static str> {
match &node.value {
ast::Expr::Select(select) if node.key == select.attr => {
Some("Use `inherit` for this selected attribute")
}
_ => None,
}
}
}

View File

@@ -1,98 +0,0 @@
use crate::ast;
pub struct Finding {
pub range: ast::SourceRange,
}
pub fn check(expr: &ast::Expr) -> Vec<Finding> {
let mut findings = Vec::new();
check_expr(expr, &mut findings);
findings
}
fn check_expr(expr: &ast::Expr, findings: &mut Vec<Finding>) {
match expr {
ast::Expr::Let {
range,
bindings,
body,
} => {
if is_redundant(bindings, body) {
findings.push(Finding { range: *range });
}
for binding in bindings {
check_expr(&binding.value, findings);
}
check_expr(body, findings);
}
ast::Expr::AttrSet(bindings) => {
for binding in bindings {
check_expr(&binding.value, findings);
}
}
ast::Expr::Lambda { body, .. } => check_expr(body, findings),
ast::Expr::Apply(application) => {
check_expr(&application.lambda, findings);
check_expr(&application.argument, findings);
}
ast::Expr::Other(expressions) => {
for expression in expressions {
check_expr(expression, findings);
}
}
ast::Expr::Ident(_) | ast::Expr::Select(_) => { }
}
}
fn is_redundant(bindings: &[ast::Binding], body: &ast::Expr) -> bool {
let Some((binding_index, binding)) = bindings
.iter()
.enumerate()
.find(|(_, binding)| is_ident(body, &binding.key.name))
else {
return false;
};
!references_name(&binding.value, &binding.key.name)
&& !bindings.iter().enumerate().any(|(candidate_index, candidate)| {
candidate_index != binding_index && references_name(&candidate.value, &binding.key.name)
})
}
fn is_ident(expr: &ast::Expr, name: &str) -> bool {
matches!(unwrap_expr(expr), ast::Expr::Ident(ident) if ident.name == name)
}
fn references_name(expr: &ast::Expr, name: &str) -> bool {
match expr {
ast::Expr::Ident(ident) => ident.name == name,
ast::Expr::Select(select) => select.receiver == name,
ast::Expr::Apply(application) => {
references_name(&application.lambda, name) || references_name(&application.argument, name)
}
ast::Expr::Let { bindings, body, .. } => {
!bindings.iter().any(|binding| binding.key.name == name)
&& (bindings
.iter()
.any(|binding| references_name(&binding.value, name))
|| references_name(body, name))
}
ast::Expr::AttrSet(bindings) => bindings
.iter()
.any(|binding| references_name(&binding.value, name)),
ast::Expr::Lambda { parameters, body } => {
!parameters.iter().any(|parameter| parameter.name == name)
&& references_name(body, name)
}
ast::Expr::Other(expressions) => expressions
.iter()
.any(|expression| references_name(expression, name)),
}
}
fn unwrap_expr(expr: &ast::Expr) -> &ast::Expr {
match expr {
ast::Expr::Other(expressions) if expressions.len() == 1 => unwrap_expr(&expressions[0]),
_ => expr,
}
}

View File

@@ -1,244 +0,0 @@
use crate::ast;
pub struct Finding {
pub range: ast::SourceRange,
}
pub fn check(expr: &ast::Expr) -> Vec<Finding> {
let mut findings = Vec::new();
check_expr(expr, &[], &mut findings);
findings
}
fn check_expr(expr: &ast::Expr, outer_parameters: &[ast::Ident], findings: &mut Vec<Finding>) {
match expr {
ast::Expr::Let { bindings, body, .. } => {
check_let(bindings, body, outer_parameters, findings);
for binding in bindings {
check_expr(&binding.value, outer_parameters, findings);
}
check_expr(body, outer_parameters, findings);
}
ast::Expr::AttrSet(bindings) => {
for binding in bindings {
check_expr(&binding.value, outer_parameters, findings);
}
}
ast::Expr::Lambda { parameters, body } => check_expr(body, parameters, findings),
ast::Expr::Apply(application) => {
check_expr(&application.lambda, outer_parameters, findings);
check_expr(&application.argument, outer_parameters, findings);
}
ast::Expr::Other(expressions) => {
for expression in expressions {
check_expr(expression, outer_parameters, findings);
}
}
ast::Expr::Ident(_) | ast::Expr::Select(_) => { }
}
}
fn check_let(
bindings: &[ast::Binding],
let_body: &ast::Expr,
outer_parameters: &[ast::Ident],
findings: &mut Vec<Finding>,
) {
for binding in bindings {
let parameters = curried_parameters(&binding.value);
for (parameter_index, parameter) in parameters.iter().enumerate() {
if !outer_parameters
.iter()
.any(|outer_parameter| outer_parameter.name == parameter.name)
{
continue;
}
let usage = helper_usage(
bindings,
let_body,
&binding.key.name,
&parameter.name,
parameter_index,
);
if usage.calls > 0 && !usage.invalid {
findings.push(Finding {
range: binding.range,
});
break;
}
}
}
}
#[derive(Default)]
struct Usage {
calls: usize,
invalid: bool,
}
fn helper_usage(
bindings: &[ast::Binding],
body: &ast::Expr,
helper_name: &str,
parameter_name: &str,
parameter_index: usize,
) -> Usage {
let mut usage = Usage::default();
for binding in bindings {
inspect_usage(
&binding.value,
helper_name,
parameter_name,
parameter_index,
&mut usage,
);
}
inspect_usage(body, helper_name, parameter_name, parameter_index, &mut usage);
usage
}
fn inspect_usage(
expr: &ast::Expr,
helper_name: &str,
parameter_name: &str,
parameter_index: usize,
usage: &mut Usage,
) {
match expr {
ast::Expr::Ident(ident) => {
if ident.name == helper_name {
usage.invalid = true;
}
}
ast::Expr::Select(_) => { }
ast::Expr::Apply(_) => {
let (lambda, arguments) = application_parts(expr);
if is_ident(lambda, helper_name) {
let Some(argument) = arguments.get(parameter_index) else {
usage.invalid = true;
return;
};
if is_forwarded_parameter(argument, parameter_name) {
usage.calls += 1;
} else {
usage.invalid = true;
}
for argument in arguments {
inspect_usage(
argument,
helper_name,
parameter_name,
parameter_index,
usage,
);
}
} else {
for argument in arguments {
inspect_usage(
argument,
helper_name,
parameter_name,
parameter_index,
usage,
);
}
inspect_usage(lambda, helper_name, parameter_name, parameter_index, usage);
}
}
ast::Expr::Let { bindings, body, .. } => {
if bindings.iter().any(|binding| {
binding.key.name == helper_name || binding.key.name == parameter_name
}) {
return;
}
for binding in bindings {
inspect_usage(
&binding.value,
helper_name,
parameter_name,
parameter_index,
usage,
);
}
inspect_usage(body, helper_name, parameter_name, parameter_index, usage);
}
ast::Expr::AttrSet(bindings) => {
for binding in bindings {
inspect_usage(
&binding.value,
helper_name,
parameter_name,
parameter_index,
usage,
);
}
}
ast::Expr::Lambda { parameters, body } => {
if parameters.iter().any(|parameter| {
parameter.name == helper_name || parameter.name == parameter_name
}) {
return;
}
inspect_usage(body, helper_name, parameter_name, parameter_index, usage);
}
ast::Expr::Other(expressions) => {
for expression in expressions {
inspect_usage(
expression,
helper_name,
parameter_name,
parameter_index,
usage,
);
}
}
}
}
fn curried_parameters(expr: &ast::Expr) -> Vec<&ast::Ident> {
let mut parameters = Vec::new();
let mut body = expr;
while let ast::Expr::Lambda {
parameters: lambda_parameters,
body: lambda_body,
} = body
{
parameters.extend(lambda_parameters);
body = lambda_body;
}
parameters
}
fn application_parts(expr: &ast::Expr) -> (&ast::Expr, Vec<&ast::Expr>) {
let mut arguments = Vec::new();
let mut lambda = unwrap_expr(expr);
while let ast::Expr::Apply(application) = lambda {
arguments.push(&*application.argument);
lambda = unwrap_expr(&application.lambda);
}
arguments.reverse();
(lambda, arguments)
}
fn is_ident(expr: &ast::Expr, name: &str) -> bool {
matches!(unwrap_expr(expr), ast::Expr::Ident(ident) if ident.name == name)
}
fn is_forwarded_parameter(expr: &ast::Expr, parameter_name: &str) -> bool {
match unwrap_expr(expr) {
ast::Expr::Ident(ident) => ident.name == parameter_name,
ast::Expr::AttrSet(bindings) => matches!(
bindings.as_slice(),
[binding] if binding.key.name == parameter_name && is_ident(&binding.value, parameter_name)
),
_ => false,
}
}
fn unwrap_expr(expr: &ast::Expr) -> &ast::Expr {
match expr {
ast::Expr::Other(expressions) if expressions.len() == 1 => unwrap_expr(&expressions[0]),
_ => expr,
}
}

View File

@@ -1,19 +0,0 @@
use crate::{ast, rules::TokenRule};
pub struct UnquotedUri;
impl TokenRule for UnquotedUri {
type Token = String;
const ID: &'static str = "unquoted_uri";
fn select(data: &ast::TokenData) -> Option<&Self::Token> {
match data {
ast::TokenData::UnquotedUri(uri) => Some(uri),
}
}
fn check(_token: &Self::Token) -> Option<&'static str> {
Some("URI literals should be quoted")
}
}

View File

@@ -1,206 +0,0 @@
use crate::ast::{self, ParsedFile};
#[derive(Debug)]
pub(crate) struct ScopeGraph {
nodes: Vec<Node>,
edges: Vec<Edge>,
lets: Vec<LetScope>,
}
impl ScopeGraph {
pub(crate) fn from_file(file: &ParsedFile) -> Self {
let mut graph = Self {
nodes: Vec::new(),
edges: Vec::new(),
lets: Vec::new(),
};
let root = graph.add_scope(None);
graph.build_expr(&file.root, root);
graph
}
pub(crate) fn let_scopes(&self) -> &[LetScope] {
&self.lets
}
fn build_expr(&mut self, expr: &ast::Expr, scope: NodeId) -> Vec<NodeId> {
match expr {
ast::Expr::Ident(ident) => vec![self.add_reference(&ident.name, scope)],
ast::Expr::Let {
range,
bindings,
body,
} => self.build_let(*range, bindings, body, scope),
ast::Expr::AttrSet(bindings) => bindings
.iter()
.flat_map(|binding| self.build_expr(&binding.value, scope))
.collect(),
ast::Expr::Lambda { parameters, body } => {
let scope = self.add_scope(Some(scope));
for parameter in parameters {
self.add_declaration(&parameter.name, scope);
}
self.build_expr(body, scope)
}
ast::Expr::Apply(application) => [
self.build_expr(&application.lambda, scope),
self.build_expr(&application.argument, scope),
]
.concat(),
ast::Expr::Other(expressions) => expressions
.iter()
.flat_map(|expression| self.build_expr(expression, scope))
.collect(),
ast::Expr::Select(select) => vec![self.add_reference(&select.receiver, scope)],
}
}
fn build_let(
&mut self,
range: ast::SourceRange,
bindings: &[ast::Binding],
body: &ast::Expr,
parent: NodeId,
) -> Vec<NodeId> {
let scope = self.add_scope(Some(parent));
let mut graph_bindings = bindings
.iter()
.map(|binding| Binding {
declaration: self.add_declaration(&binding.key.name, scope),
name: binding.key.name.clone(),
references: Vec::new(),
range: binding.range,
})
.collect::<Vec<_>>();
for (binding, graph_binding) in bindings.iter().zip(&mut graph_bindings) {
graph_binding.references = self.build_expr(&binding.value, scope);
}
let entry_references = self.build_expr(body, scope);
let references = graph_bindings
.iter()
.flat_map(|binding| binding.references.iter().copied())
.chain(entry_references.iter().copied())
.collect();
self.lets.push(LetScope {
range,
bindings: graph_bindings,
entry_references,
});
references
}
pub(crate) fn resolve(&self, reference: NodeId) -> Vec<NodeId> {
let Node::Reference(name) = &self.nodes[reference.0] else {
return Vec::new();
};
let Some(mut scope) = self.edge_target(reference, Node::is_scope) else {
return Vec::new();
};
loop {
let declarations = self
.edge_targets(scope, |node| matches!(node, Node::Declaration(declaration) if declaration.name == *name))
.collect::<Vec<_>>();
if !declarations.is_empty() {
return declarations;
}
let Some(parent) = self.edge_target(scope, Node::is_scope) else {
return Vec::new();
};
scope = parent;
}
}
fn add_scope(&mut self, parent: Option<NodeId>) -> NodeId {
let scope = self.add_node(Node::Scope);
if let Some(parent) = parent {
self.add_edge(scope, parent);
}
scope
}
fn add_declaration(&mut self, name: &str, scope: NodeId) -> NodeId {
let declaration = self.add_node(Node::Declaration(Declaration {
name: name.to_owned(),
}));
self.add_edge(scope, declaration);
declaration
}
fn add_reference(&mut self, name: &str, scope: NodeId) -> NodeId {
let reference = self.add_node(Node::Reference(name.to_owned()));
self.add_edge(reference, scope);
reference
}
fn add_node(&mut self, node: Node) -> NodeId {
let id = NodeId(self.nodes.len());
self.nodes.push(node);
id
}
fn add_edge(&mut self, from: NodeId, to: NodeId) {
self.edges.push(Edge { from, to });
}
fn edge_target(&self, from: NodeId, predicate: fn(&Node) -> bool) -> Option<NodeId> {
self.edge_targets(from, predicate).next()
}
fn edge_targets<'graph>(
&'graph self,
from: NodeId,
predicate: impl Fn(&Node) -> bool + 'graph,
) -> impl Iterator<Item = NodeId> + 'graph {
self.edges
.iter()
.filter(move |edge| edge.from == from && predicate(&self.nodes[edge.to.0]))
.map(|edge| edge.to)
}
}
#[derive(Debug)]
enum Node {
Scope,
Declaration(Declaration),
Reference(String),
}
impl Node {
fn is_scope(&self) -> bool {
matches!(self, Self::Scope)
}
}
#[derive(Debug)]
struct Declaration {
name: String,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct NodeId(usize);
#[derive(Debug)]
struct Edge {
from: NodeId,
to: NodeId,
}
#[derive(Debug)]
pub(crate) struct LetScope {
pub(crate) range: ast::SourceRange,
pub(crate) bindings: Vec<Binding>,
pub(crate) entry_references: Vec<NodeId>,
}
#[derive(Debug)]
pub(crate) struct Binding {
pub(crate) declaration: NodeId,
pub(crate) name: String,
pub(crate) references: Vec<NodeId>,
pub(crate) range: ast::SourceRange,
}

View File

@@ -1,29 +0,0 @@
{ pkgs }:
let
first = 1;
second = first;
in {
firstField = first;
secondField = second;
nested = let
innerSecond = innerFirst;
innerFirst = first;
in {
result = innerSecond;
};
parameter = first: let
usesParameter = first;
in {
result = usesParameter;
};
path = ./. + "/foo";
url = "https://example.com";
inherit pkgs;
different = other;
nested.package = nested.package;
"quoted" = quoted;
${dynamic} = dynamic;
from = pkgs.from.other;
fallback = pkgs.fallback or null;
}

View File

@@ -1,4 +0,0 @@
{ pkgs }:
{
inherit pkgs;

View File

@@ -1,17 +0,0 @@
let
second = first;
first = 1;
nested = let
nestedFirst = first;
nestedSecond = nestedFirst;
in {
result = nestedSecond;
};
in {
package = package;
from = pkgs.from;
url = https://example.com;
firstField = first;
secondField = second;
nestedField = nested;
}

View File

@@ -12,10 +12,7 @@ After editing Nix files, run:
```bash
nix run .#fix
bazel run //src/natu:natu -- <modified-nix-paths>
```
Pass every modified Nix path to Natu.
Finish when both commands succeed and the Nix change follows the loaded rules.
If a command fails, report the failure.
Finish when the command succeeds and the Nix change follows the loaded rules.
If the command fails, report the failure.

7
third_party/BUILD vendored
View File

@@ -1,4 +1,4 @@
load("@rules_rust//crate_universe:defs.bzl", "crate", "crates_vendor")
load("@rules_rust//crate_universe:defs.bzl", "crates_vendor")
sh_binary(
name = "bazel_for_cargo_bazel",
@@ -10,11 +10,6 @@ crates_vendor(
bazel = ":bazel_for_cargo_bazel",
cargo_lockfile = "//:Cargo.lock",
manifests = ["//:Cargo.toml"],
packages = {
"rnix": crate.spec(
version = "=0.14.0",
),
},
mode = "local",
tags = ["manual"],
vendor_path = "crates",

View File

@@ -43,42 +43,6 @@ alias(
tags = ["manual"],
)
alias(
name = "googletest-0.14.3",
actual = "//third_party/crates/googletest-0.14.3:googletest",
tags = ["manual"],
)
alias(
name = "googletest",
actual = "//third_party/crates/googletest-0.14.3:googletest",
tags = ["manual"],
)
alias(
name = "rnix-0.14.0",
actual = "//third_party/crates/rnix-0.14.0:rnix",
tags = ["manual"],
)
alias(
name = "rnix",
actual = "//third_party/crates/rnix-0.14.0:rnix",
tags = ["manual"],
)
alias(
name = "rowan-0.16.1",
actual = "//third_party/crates/rowan-0.16.1:rowan",
tags = ["manual"],
)
alias(
name = "rowan",
actual = "//third_party/crates/rowan-0.16.1:rowan",
tags = ["manual"],
)
alias(
name = "serde-1.0.229",
actual = "//third_party/crates/serde-1.0.229:serde",

View File

@@ -1 +0,0 @@
{"$comment":"This file only protects against accidental modifications. It is not a security mechanism and does not protect against malicious changes.","files":{".cargo_vcs_info.json":"fa452b0920e10ae97397f4cb336b629f7cbe5de0bed8fd8046ce8c137c06e2a4",".github/FUNDING.yml":"0c65f392d32a8639ba7986bbb42ca124505b462122382f314c89d84c95dd27f1",".github/dependabot.yml":"ea498dc2f28b89e80cf42a1349ac48ba9a9cc4d53f6cb21333481a4611f95abb",".github/workflows/ci.yml":"2d9409bedd406551a2e7e62158f3826c54c38a15d35e2a1a660e47499ea1999e",".vim/coc-settings.json":"8237c8f41db352b0d83f1bb10a60bc2f60f56f3234afbf696b4075c8d4d62d9b","COPYING":"01c266bced4a434da0051174d6bee16a4c82cf634e2679b6155d40d75012390f","Cargo.lock":"9b5026fc4b42d1470b586a636f7c0e843ca9a056f4137727bf7ba36baaa9c9b0","Cargo.toml":"7ff243aed78547f286729c3c60d97577fbc685546120263548d7c4f2a3884bc1","Cargo.toml.orig":"6c8341535cb4f736c1ac6b18292df2c572ccb18740bb9325e42b22c67f9e27da","DESIGN.md":"59c960e1b73b1d7fb41e4df6c0c1b1fcf44dd2ebc8a349597a7d0595f8cb5130","LICENSE-MIT":"0f96a83840e146e43c0ec96a22ec1f392e0680e6c1226e6f3ba87e0740af850f","README.md":"afc4d559a98cf190029af0bf320fc0022725e349cd2a303aac860254e28f3c53","UNLICENSE":"7e12e5df4bae12cb21581ba157ced20e1986a0508dd10d0e8a4ab9a4cf94e85c","rustfmt.toml":"1ca600239a27401c4a43f363cf3f38183a212affc1f31bff3ae93234bbaec228","src/ahocorasick.rs":"c699c07df70be45c666e128509ad571a7649d2073e4ae16ac1efd6793c9c6890","src/automaton.rs":"22258a3e118672413119f8f543a9b912cce954e63524575c0ebfdf9011f9c2dd","src/dfa.rs":"197075923eb9d760a552f4e8652310fd4f657736613a9b1444ae05ef5d525da3","src/lib.rs":"66dea84d227f269b2f14ecc8109a97e96245b56c22eef0e8ce03b2343b8d6e66","src/macros.rs":"c6c52ae05b24433cffaca7b78b3645d797862c5d5feffddf9f54909095ed6e05","src/nfa/contiguous.rs":"f435c131ce84927e5600109722d006533ea21442dddaf18e03286d8caed82389","src/nfa/mod.rs":"ee7b3109774d14bbad5239c16bb980dd6b8185ec136d94fbaf2f0dc27d5ffa15","src/nfa/noncontiguous.rs":"de94f02b04efd8744fb096759a8897c22012b0e0ca3ace161fd87c71befefe04","src/packed/api.rs":"d555a8c7a6da33b75f1f90e21ee970629f92f7bddd4b408b78656cd93fe1a3d6","src/packed/ext.rs":"66be06fde8558429da23a290584d4b9fae665bf64c2578db4fe5f5f3ee864869","src/packed/mod.rs":"0020cd6f07ba5c8955923a9516d7f758864260eda53a6b6f629131c45ddeec62","src/packed/pattern.rs":"0e4bca57d4b941495d31fc8246ad32904eed0cd89e3cda732ad35f4deeba3bef","src/packed/rabinkarp.rs":"403146eb1d838a84601d171393542340513cd1ee7ff750f2372161dd47746586","src/packed/teddy/README.md":"3a43194b64e221543d885176aba3beb1224a927385a20eca842daf6b0ea2f342","src/packed/teddy/builder.rs":"08ec116a4a842a2bb1221d296a2515ef3672c54906bed588fb733364c07855d3","src/packed/teddy/generic.rs":"ea252ab05b32cea7dd9d71e332071d243db7dd0362e049252a27e5881ba2bf39","src/packed/teddy/mod.rs":"17d741f7e2fb9dbac5ba7d1bd4542cf1e35e9f146ace728e23fe6bbed20028b2","src/packed/tests.rs":"8e2f56eb3890ed3876ecb47d3121996e416563127b6430110d7b516df3f83b4b","src/packed/vector.rs":"70c325cfa6f7c5c4c9a6af7b133b75a29e65990a7fe0b9a4c4ce3c3d5a0fe587","src/tests.rs":"c68192ab97b6161d0d6ee96fefd80cc7d14e4486ddcd8d1f82b5c92432c24ed5","src/transducer.rs":"02daa33a5d6dac41dcfd67f51df7c0d4a91c5131c781fb54c4de3520c585a6e1","src/util/alphabet.rs":"6dc22658a38deddc0279892035b18870d4585069e35ba7c7e649a24509acfbcc","src/util/buffer.rs":"f9e37f662c46c6ecd734458dedbe76c3bb0e84a93b6b0117c0d4ad3042413891","src/util/byte_frequencies.rs":"2fb85b381c038c1e44ce94294531cdcd339dca48b1e61f41455666e802cbbc9e","src/util/debug.rs":"ab301ad59aa912529cb97233a54a05914dd3cb2ec43e6fec7334170b97ac5998","src/util/error.rs":"ecccd60e7406305023efcc6adcc826eeeb083ab8f7fbfe3d97469438cd4c4e5c","src/util/int.rs":"e264e6abebf5622b59f6500210773db36048371c4e509c930263334095959a52","src/util/mod.rs":"7ab28d11323ecdbd982087f32eb8bceeee84f1a2583f3aae27039c36d58cf12c","src/util/prefilter.rs":"183e32aa9951d9957f89062e4a6ae7235df7060722a3c91995a3d36db5a98111","src/util/primitives.rs":"f89f3fa1d8db4e37de9ca767c6d05e346404837cade6d063bba68972fafa610b","src/util/remapper.rs":"9f12d911583a325c11806eeceb46d0dfec863cfcfa241aed84d31af73da746e5","src/util/search.rs":"ac16607e69a3ff24d27c0680dc9afcd5bb7b7cb272179d5475300a2035fdf7e3","src/util/special.rs":"7d2f9cb9dd9771f59816e829b2d96b1239996f32939ba98764e121696c52b146"},"package":"c982642fa9e8606056828ee9a8505737230110bb1099153c79efe865c59d12ba"}

View File

@@ -1,6 +0,0 @@
{
"git": {
"sha1": "5178060ce73d91938f8582d0360e3be031380440"
},
"path_in_vcs": ""
}

View File

@@ -1 +0,0 @@
github: [BurntSushi]

View File

@@ -1,14 +0,0 @@
version: 2
updates:
- package-ecosystem: github-actions
directory: "/"
schedule:
interval: semiannually
open-pull-requests-limit: 1
cooldown:
default-days: 30
groups:
actions:
patterns:
- "*"

View File

@@ -1,154 +0,0 @@
name: ci
on:
pull_request:
push:
branches:
- master
schedule:
- cron: '00 01 * * *'
# The section is needed to drop write-all permissions that are granted on
# `schedule` event. By specifying any permission explicitly all others are set
# to none. By using the principle of least privilege the damage a compromised
# workflow can do (because of an injection or compromised third party tool or
# action) is restricted. Currently the worklow doesn't need any additional
# permission except for pulling the code. Adding labels to issues, commenting
# on pull-requests, etc. may need additional permissions:
#
# Syntax for this section:
# https://docs.github.com/en/actions/using-workflows/workflow-syntax-for-github-actions#permissions
#
# Reference for how to assign permissions on a job-by-job basis:
# https://docs.github.com/en/actions/using-jobs/assigning-permissions-to-jobs
#
# Reference for available permissions that we can enable if needed:
# https://docs.github.com/en/actions/security-guides/automatic-token-authentication#permissions-for-the-github_token
permissions:
# to fetch code (actions/checkout)
contents: read
jobs:
test:
name: test
env:
# For some builds, we use cross to test on 32-bit and big-endian
# systems.
CARGO: cargo
# When CARGO is set to CROSS, TARGET is set to `--target matrix.target`.
# Note that we only use cross on Linux, so setting a target on a
# different OS will just use normal cargo.
TARGET:
# Bump this as appropriate. We pin to a version to make sure CI
# continues to work as cross releases in the past have broken things
# in subtle ways.
CROSS_VERSION: v0.2.5
runs-on: ${{ matrix.os }}
strategy:
fail-fast: false
matrix:
include:
- build: pinned
os: ubuntu-latest
rust: 1.60.0
- build: stable
os: ubuntu-latest
rust: stable
- build: stable-x86
os: ubuntu-latest
rust: stable
target: i686-unknown-linux-gnu
- build: stable-aarch64
os: ubuntu-latest
rust: stable
target: aarch64-unknown-linux-gnu
- build: stable-powerpc64
os: ubuntu-latest
rust: stable
target: powerpc64-unknown-linux-gnu
- build: stable-s390x
os: ubuntu-latest
rust: stable
target: s390x-unknown-linux-gnu
- build: beta
os: ubuntu-latest
rust: beta
- build: nightly
os: ubuntu-latest
rust: nightly
- build: macos
os: macos-latest
rust: stable
- build: win-msvc
os: windows-latest
rust: stable
- build: win-gnu
os: windows-latest
rust: stable-x86_64-gnu
steps:
- name: Checkout repository
uses: actions/checkout@de0fac2e4500dabe0009e67214ff5f5447ce83dd # v6.0.2
with:
persist-credentials: false
- name: Install Rust
uses: dtolnay/rust-toolchain@e97e2d8cc328f1b50210efc529dca0028893a2d9 # v1
with:
toolchain: ${{ matrix.rust }}
- name: Install and configure Cross
if: matrix.os == 'ubuntu-latest' && matrix.target != ''
run: |
# In the past, new releases of 'cross' have broken CI. So for now, we
# pin it. We also use their pre-compiled binary releases because cross
# has over 100 dependencies and takes a bit to compile.
dir="$RUNNER_TEMP/cross-download"
mkdir "$dir"
echo "$dir" >> $GITHUB_PATH
cd "$dir"
curl -LO "https://github.com/cross-rs/cross/releases/download/$CROSS_VERSION/cross-x86_64-unknown-linux-musl.tar.gz"
tar xf cross-x86_64-unknown-linux-musl.tar.gz
# We used to install 'cross' from master, but it kept failing. So now
# we build from a known-good version until 'cross' becomes more stable
# or we find an alternative. Notably, between v0.2.1 and current
# master (2022-06-14), the number of Cross's dependencies has doubled.
echo "CARGO=cross" >> $GITHUB_ENV
echo "TARGET=--target ${{ matrix.target }}" >> $GITHUB_ENV
- name: Show command used for Cargo
run: |
echo "cargo command is: ${{ env.CARGO }}"
echo "target flag is: ${{ env.TARGET }}"
- name: Show CPU info for debugging
if: matrix.os == 'ubuntu-latest'
run: lscpu
# See: https://github.com/rust-lang/regex/blob/a2887636930156023172e4b376a6febad4e49120/.github/workflows/ci.yml#L145-L163
- name: Pin memchr to 2.6.2
if: matrix.build == 'pinned'
run: |
cargo update -p memchr --precise 2.6.2
cargo update -p log --precise 0.4.20
- run: ${{ env.CARGO }} build --verbose $TARGET
- run: ${{ env.CARGO }} doc --verbose $TARGET
- run: ${{ env.CARGO }} test --verbose $TARGET
- run: ${{ env.CARGO }} test --lib --verbose --no-default-features --features std,perf-literal $TARGET
- run: ${{ env.CARGO }} test --lib --verbose --no-default-features $TARGET
- run: ${{ env.CARGO }} test --lib --verbose --no-default-features --features std $TARGET
- run: ${{ env.CARGO }} test --lib --verbose --no-default-features --features perf-literal $TARGET
- run: ${{ env.CARGO }} test --lib --verbose --no-default-features --features std,perf-literal,logging $TARGET
- if: matrix.build == 'nightly'
run: ${{ env.CARGO }} build --manifest-path aho-corasick-debug/Cargo.toml $TARGET
rustfmt:
name: rustfmt
runs-on: ubuntu-latest
steps:
- name: Checkout repository
uses: actions/checkout@de0fac2e4500dabe0009e67214ff5f5447ce83dd # v6.0.2
with:
persist-credentials: false
- name: Install Rust
uses: dtolnay/rust-toolchain@e97e2d8cc328f1b50210efc529dca0028893a2d9 # v1
with:
toolchain: stable
components: rustfmt
- name: Check formatting
run: |
cargo fmt --all -- --check

View File

@@ -1,12 +0,0 @@
{
"rust-analyzer.linkedProjects": [
"aho-corasick-debug/Cargo.toml",
"benchmarks/engines/rust-aho-corasick/Cargo.toml",
"benchmarks/engines/rust-daachorse/Cargo.toml",
"benchmarks/engines/rust-jetscii/Cargo.toml",
"benchmarks/engines/naive/Cargo.toml",
"benchmarks/shared/Cargo.toml",
"fuzz/Cargo.toml",
"Cargo.toml"
]
}

View File

@@ -1,117 +0,0 @@
###############################################################################
# @generated
# DO NOT MODIFY: This file is auto-generated by a crate_universe tool. To
# regenerate this file, run the following:
#
# bazel run @@//third_party:vendor_crates
###############################################################################
load("@rules_rust//cargo:defs.bzl", "cargo_toml_env_vars")
load("@rules_rust//rust:defs.bzl", "rust_library")
package(default_visibility = ["//visibility:public"])
cargo_toml_env_vars(
name = "cargo_toml_env_vars",
src = "Cargo.toml",
)
rust_library(
name = "aho_corasick",
srcs = glob(
include = ["**/*.rs"],
allow_empty = False,
),
compile_data = glob(
include = ["**"],
allow_empty = True,
exclude = [
"**/* *",
".tmp_git_root/**/*",
"BUILD",
"BUILD.bazel",
"WORKSPACE",
"WORKSPACE.bazel",
],
),
crate_features = [
"perf-literal",
"std",
],
crate_root = "src/lib.rs",
edition = "2021",
rustc_env_files = [
":cargo_toml_env_vars",
],
rustc_flags = [
"--cap-lints=allow",
],
tags = [
"cargo-bazel",
"crate-name=aho-corasick",
"manual",
"noclippy",
"norustfmt",
],
target_compatible_with = select({
"@rules_rust//rust/platform:aarch64-apple-darwin": [],
"@rules_rust//rust/platform:aarch64-apple-ios": [],
"@rules_rust//rust/platform:aarch64-apple-ios-macabi": [],
"@rules_rust//rust/platform:aarch64-apple-ios-sim": [],
"@rules_rust//rust/platform:aarch64-linux-android": [],
"@rules_rust//rust/platform:aarch64-pc-windows-msvc": [],
"@rules_rust//rust/platform:aarch64-unknown-fuchsia": [],
"@rules_rust//rust/platform:aarch64-unknown-linux-gnu": [],
"@rules_rust//rust/platform:aarch64-unknown-nixos-gnu": [],
"@rules_rust//rust/platform:aarch64-unknown-none": [],
"@rules_rust//rust/platform:aarch64-unknown-nto-qnx710": [],
"@rules_rust//rust/platform:aarch64-unknown-uefi": [],
"@rules_rust//rust/platform:arm-unknown-linux-gnueabi": [],
"@rules_rust//rust/platform:arm-unknown-linux-musleabi": [],
"@rules_rust//rust/platform:armv7-linux-androideabi": [],
"@rules_rust//rust/platform:armv7-unknown-linux-gnueabi": [],
"@rules_rust//rust/platform:i686-apple-darwin": [],
"@rules_rust//rust/platform:i686-linux-android": [],
"@rules_rust//rust/platform:i686-pc-windows-msvc": [],
"@rules_rust//rust/platform:i686-unknown-freebsd": [],
"@rules_rust//rust/platform:i686-unknown-linux-gnu": [],
"@rules_rust//rust/platform:loongarch64-unknown-linux-gnu": [],
"@rules_rust//rust/platform:mips-unknown-linux-gnu": [],
"@rules_rust//rust/platform:powerpc-unknown-linux-gnu": [],
"@rules_rust//rust/platform:riscv32imac-unknown-none-elf": [],
"@rules_rust//rust/platform:riscv32imc-unknown-none-elf": [],
"@rules_rust//rust/platform:riscv64gc-unknown-linux-gnu": [],
"@rules_rust//rust/platform:riscv64gc-unknown-none-elf": [],
"@rules_rust//rust/platform:s390x-unknown-linux-gnu": [],
"@rules_rust//rust/platform:sparc64-unknown-linux-gnu": [],
"@rules_rust//rust/platform:sparc64-unknown-netbsd": [],
"@rules_rust//rust/platform:sparc64-unknown-openbsd": [],
"@rules_rust//rust/platform:thumbv6m-none-eabi": [],
"@rules_rust//rust/platform:thumbv7em-none-eabi": [],
"@rules_rust//rust/platform:thumbv7em-none-eabihf": [],
"@rules_rust//rust/platform:thumbv7m-none-eabi": [],
"@rules_rust//rust/platform:thumbv8m.main-none-eabi": [],
"@rules_rust//rust/platform:thumbv8m.main-none-eabihf": [],
"@rules_rust//rust/platform:wasm32-unknown-emscripten": [],
"@rules_rust//rust/platform:wasm32-unknown-unknown": [],
"@rules_rust//rust/platform:wasm32-wasip1": [],
"@rules_rust//rust/platform:wasm32-wasip1-threads": [],
"@rules_rust//rust/platform:wasm32-wasip2": [],
"@rules_rust//rust/platform:x86_64-apple-darwin": [],
"@rules_rust//rust/platform:x86_64-apple-ios": [],
"@rules_rust//rust/platform:x86_64-apple-ios-macabi": [],
"@rules_rust//rust/platform:x86_64-linux-android": [],
"@rules_rust//rust/platform:x86_64-pc-windows-msvc": [],
"@rules_rust//rust/platform:x86_64-unknown-freebsd": [],
"@rules_rust//rust/platform:x86_64-unknown-fuchsia": [],
"@rules_rust//rust/platform:x86_64-unknown-linux-gnu": [],
"@rules_rust//rust/platform:x86_64-unknown-nixos-gnu": [],
"@rules_rust//rust/platform:x86_64-unknown-none": [],
"@rules_rust//rust/platform:x86_64-unknown-uefi": [],
"//conditions:default": ["@platforms//:incompatible"],
}),
version = "1.1.5",
deps = [
"//third_party/crates/memchr-2.8.3:memchr",
],
)

View File

@@ -1,3 +0,0 @@
This project is dual-licensed under the Unlicense and MIT licenses.
You may use this code under the terms of either license.

View File

@@ -1,30 +0,0 @@
# This file is automatically @generated by Cargo.
# It is not intended for manual editing.
version = 3
[[package]]
name = "aho-corasick"
version = "1.1.5"
dependencies = [
"doc-comment",
"log",
"memchr",
]
[[package]]
name = "doc-comment"
version = "0.3.4"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "780955b8b195a21ab8e4ac6b60dd1dbdcec1dc6c51c0617964b08c81785e12c9"
[[package]]
name = "log"
version = "0.4.33"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "0ceec5bc11778974d1bcb055b18002eba7f4b3518b6a0081b3af5f21666da9ad"
[[package]]
name = "memchr"
version = "2.8.3"
source = "registry+https://github.com/rust-lang/crates.io-index"
checksum = "cf8baf1c55e62ffcace7a9f06f4bd9cd3f0c4beb022d3b367256b91b87513d98"

View File

@@ -1,80 +0,0 @@
# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
#
# When uploading crates to the registry Cargo will automatically
# "normalize" Cargo.toml files for maximal compatibility
# with all versions of Cargo and also rewrite `path` dependencies
# to registry (e.g., crates.io) dependencies.
#
# If you are reading this file be aware that the original Cargo.toml
# will likely look very different (and much more reasonable).
# See Cargo.toml.orig for the original contents.
[package]
edition = "2021"
rust-version = "1.60.0"
name = "aho-corasick"
version = "1.1.5"
authors = ["Andrew Gallant <jamslam@gmail.com>"]
build = false
exclude = [
"/aho-corasick-debug",
"/benchmarks",
"/tmp",
]
autolib = false
autobins = false
autoexamples = false
autotests = false
autobenches = false
description = "Fast multiple substring searching."
homepage = "https://github.com/BurntSushi/aho-corasick"
readme = "README.md"
keywords = [
"string",
"search",
"text",
"pattern",
"multi",
]
categories = ["text-processing"]
license = "Unlicense OR MIT"
repository = "https://github.com/BurntSushi/aho-corasick"
[package.metadata.docs.rs]
all-features = true
rustdoc-args = [
"--cfg",
"docsrs",
"--generate-link-to-definition",
]
[features]
default = [
"std",
"perf-literal",
]
logging = ["dep:log"]
perf-literal = ["dep:memchr"]
std = ["memchr?/std"]
[lib]
name = "aho_corasick"
path = "src/lib.rs"
[dependencies.log]
version = "0.4.17"
optional = true
[dependencies.memchr]
version = "2.4.0"
optional = true
default-features = false
[dev-dependencies.doc-comment]
version = "0.3.3"
[profile.bench]
debug = 2
[profile.release]
debug = 2

View File

@@ -1,74 +0,0 @@
[package]
name = "aho-corasick"
version = "1.1.5" #:version
authors = ["Andrew Gallant <jamslam@gmail.com>"]
description = "Fast multiple substring searching."
homepage = "https://github.com/BurntSushi/aho-corasick"
repository = "https://github.com/BurntSushi/aho-corasick"
readme = "README.md"
keywords = ["string", "search", "text", "pattern", "multi"]
license = "Unlicense OR MIT"
categories = ["text-processing"]
autotests = false
exclude = ["/aho-corasick-debug", "/benchmarks", "/tmp"]
edition = "2021"
rust-version = "1.60.0"
[lib]
name = "aho_corasick"
[features]
default = ["std", "perf-literal"]
std = ["memchr?/std"]
# Enables prefilter optimizations that depend on external crates.
perf-literal = ["dep:memchr"]
# Enable logging via the 'log' crate. This is useful for seeing messages about
# internal decisions and metrics. For example, how the choice of the internal
# Aho-Corasick implementation is used or the heap usage of an automaton.
logging = ["dep:log"]
# Provides a trait impl for fst::Automaton for nfa::noncontiguous::NFA,
# nfa::contiguous::NFA and dfa::DFA. This is useful for searching an
# FST with an Aho-Corasick automaton. Note that this does not apply
# to the top-level 'AhoCorasick' type, as it does not implement the
# aho_corasick::automaton::Automaton trait, and thus enabling this feature does
# not cause it to implement fst::Automaton either.
#
# NOTE: Currently this feature is not available as `fst` is not at 1.0 yet,
# and this would make `fst` a public dependency. If you absolutely need this,
# you can copy the (very small) src/transducer.rs file to your tree. It
# specifically does not use any private APIs and should work after replacing
# 'crate::' with 'aho_corasick::'.
#
# NOTE: I think my current plan is to flip this around an add an optional
# dependency on 'aho-corasick' to the 'fst' crate and move the trait impls
# there. But I haven't gotten around to it yet.
# transducer = ["fst"]
[dependencies]
log = { version = "0.4.17", optional = true }
memchr = { version = "2.4.0", default-features = false, optional = true }
[dev-dependencies]
doc-comment = "0.3.3"
# fst = "0.4.5"
[package.metadata.docs.rs]
# We want to document all features.
all-features = true
# This opts into a nightly unstable option to show the features that need to be
# enabled for public API items. To do that, we set 'docsrs', and when that's
# enabled, we enable the 'doc_cfg' feature.
#
# To test this locally, run:
#
# RUSTDOCFLAGS="--cfg docsrs" cargo +nightly doc --all-features
rustdoc-args = ["--cfg", "docsrs", "--generate-link-to-definition"]
[profile.release]
debug = true
[profile.bench]
debug = true

View File

@@ -1,481 +0,0 @@
This document describes the internal design of this crate, which is an object
lesson in what happens when you take a fairly simple old algorithm like
Aho-Corasick and make it fast and production ready.
The target audience of this document is Rust programmers that have some
familiarity with string searching, however, one does not need to know the
Aho-Corasick algorithm in order to read this (it is explained below). One
should, however, know what a trie is. (If you don't, go read its Wikipedia
article.)
The center-piece of this crate is an implementation of Aho-Corasick. On its
own, Aho-Corasick isn't that complicated. The complex pieces come from the
different variants of Aho-Corasick implemented in this crate. Specifically,
they are:
* Aho-Corasick as a noncontiguous NFA. States have their transitions
represented sparsely, and each state puts its transitions in its own separate
allocation. Hence the same "noncontiguous."
* Aho-Corasick as a contiguous NFA. This NFA uses a single allocation to
represent the transitions of all states. That is, transitions are laid out
contiguously in memory. Moreover, states near the starting state are
represented densely, such that finding the next state ID takes a constant
number of instructions.
* Aho-Corasick as a DFA. In this case, all states are represented densely in
a transition table that uses one allocation.
* Supporting "standard" match semantics, along with its overlapping variant,
in addition to leftmost-first and leftmost-longest semantics. The "standard"
semantics are typically what you see in a textbook description of
Aho-Corasick. However, Aho-Corasick is also useful as an optimization in
regex engines, which often use leftmost-first or leftmost-longest semantics.
Thus, it is useful to implement those semantics here. The "standard" and
"leftmost" search algorithms are subtly different, and also require slightly
different construction algorithms.
* Support for ASCII case insensitive matching.
* Support for accelerating searches when the patterns all start with a small
number of fixed bytes. Or alternatively, when the patterns all contain a
small number of rare bytes. (Searching for these bytes uses SIMD vectorized
code courtesy of `memchr`.)
* Transparent support for alternative SIMD vectorized search routines for
smaller number of literals, such as the Teddy algorithm. We called these
"packed" search routines because they use SIMD. They can often be an order of
magnitude faster than just Aho-Corasick, but don't scale as well.
* Support for searching streams. This can reuse most of the underlying code,
but does require careful buffering support.
* Support for anchored searches, which permit efficient "is prefix" checks for
a large number of patterns.
When you combine all of this together along with trying to make everything as
fast as possible, what you end up with is enitrely too much code with too much
`unsafe`. Alas, I was not smart enough to figure out how to reduce it. Instead,
we will explain it.
# Basics
The fundamental problem this crate is trying to solve is to determine the
occurrences of possibly many patterns in a haystack. The naive way to solve
this is to look for a match for each pattern at each position in the haystack:
for i in 0..haystack.len():
for p in patterns.iter():
if haystack[i..].starts_with(p.bytes()):
return Match(p.id(), i, i + p.bytes().len())
Those four lines are effectively all this crate does. The problem with those
four lines is that they are very slow, especially when you're searching for a
large number of patterns.
While there are many different algorithms available to solve this, a popular
one is Aho-Corasick. It's a common solution because it's not too hard to
implement, scales quite well even when searching for thousands of patterns and
is generally pretty fast. Aho-Corasick does well here because, regardless of
the number of patterns you're searching for, it always visits each byte in the
haystack exactly once. This means, generally speaking, adding more patterns to
an Aho-Corasick automaton does not make it slower. (Strictly speaking, however,
this is not true, since a larger automaton will make less effective use of the
CPU's cache.)
Aho-Corasick can be succinctly described as a trie with state transitions
between some of the nodes that efficiently instruct the search algorithm to
try matching alternative keys in the trie. The trick is that these state
transitions are arranged such that each byte of input needs to be inspected
only once. These state transitions are typically called "failure transitions,"
because they instruct the searcher (the thing traversing the automaton while
reading from the haystack) what to do when a byte in the haystack does not
correspond to a valid transition in the current state of the trie.
More formally, a failure transition points to a state in the automaton that may
lead to a match whose prefix is a proper suffix of the path traversed through
the trie so far. (If no such proper suffix exists, then the failure transition
points back to the start state of the trie, effectively restarting the search.)
This is perhaps simpler to explain pictorally. For example, let's say we built
an Aho-Corasick automaton with the following patterns: 'abcd' and 'cef'. The
trie looks like this:
a - S1 - b - S2 - c - S3 - d - S4*
/
S0 - c - S5 - e - S6 - f - S7*
where states marked with a `*` are match states (meaning, the search algorithm
should stop and report a match to the caller).
So given this trie, it should be somewhat straight-forward to see how it can
be used to determine whether any particular haystack *starts* with either
`abcd` or `cef`. It's easy to express this in code:
fn has_prefix(trie: &Trie, haystack: &[u8]) -> bool {
let mut state_id = trie.start();
// If the empty pattern is in trie, then state_id is a match state.
if trie.is_match(state_id) {
return true;
}
for (i, &b) in haystack.iter().enumerate() {
state_id = match trie.next_state(state_id, b) {
Some(id) => id,
// If there was no transition for this state and byte, then we know
// the haystack does not start with one of the patterns in our trie.
None => return false,
};
if trie.is_match(state_id) {
return true;
}
}
false
}
And that's pretty much it. All we do is move through the trie starting with the
bytes at the beginning of the haystack. If we find ourselves in a position
where we can't move, or if we've looked through the entire haystack without
seeing a match state, then we know the haystack does not start with any of the
patterns in the trie.
The meat of the Aho-Corasick algorithm is in how we add failure transitions to
our trie to keep searching efficient. Specifically, it permits us to not only
check whether a haystack *starts* with any one of a number of patterns, but
rather, whether the haystack contains any of a number of patterns *anywhere* in
the haystack.
As mentioned before, failure transitions connect a proper suffix of the path
traversed through the trie before, with a path that leads to a match that has a
prefix corresponding to that proper suffix. So in our case, for patterns `abcd`
and `cef`, with a haystack `abcef`, we want to transition to state `S5` (from
the diagram above) from `S3` upon seeing that the byte following `c` is not
`d`. Namely, the proper suffix in this example is `c`, which is a prefix of
`cef`. So the modified diagram looks like this:
a - S1 - b - S2 - c - S3 - d - S4*
/ /
/ ----------------
/ /
S0 - c - S5 - e - S6 - f - S7*
One thing that isn't shown in this diagram is that *all* states have a failure
transition, but only `S3` has a *non-trivial* failure transition. That is, all
other states have a failure transition back to the start state. So if our
haystack was `abzabcd`, then the searcher would transition back to `S0` after
seeing `z`, which effectively restarts the search. (Because there is no pattern
in our trie that has a prefix of `bz` or `z`.)
The code for traversing this *automaton* or *finite state machine* (it is no
longer just a trie) is not that much different from the `has_prefix` code
above:
fn contains(fsm: &FiniteStateMachine, haystack: &[u8]) -> bool {
let mut state_id = fsm.start();
// If the empty pattern is in fsm, then state_id is a match state.
if fsm.is_match(state_id) {
return true;
}
for (i, &b) in haystack.iter().enumerate() {
// While the diagram above doesn't show this, we may wind up needing
// to follow multiple failure transitions before we land on a state
// in which we can advance. Therefore, when searching for the next
// state, we need to loop until we don't see a failure transition.
//
// This loop terminates because the start state has no empty
// transitions. Every transition from the start state either points to
// another state, or loops back to the start state.
loop {
match fsm.next_state(state_id, b) {
Some(id) => {
state_id = id;
break;
}
// Unlike our code above, if there was no transition for this
// state, then we don't quit. Instead, we look for this state's
// failure transition and follow that instead.
None => {
state_id = fsm.next_fail_state(state_id);
}
};
}
if fsm.is_match(state_id) {
return true;
}
}
false
}
Other than the complication around traversing failure transitions, this code
is still roughly "traverse the automaton with bytes from the haystack, and quit
when a match is seen."
And that concludes our section on the basics. While we didn't go deep into how
the automaton is built (see `src/nfa/noncontiguous.rs`, which has detailed
comments about that), the basic structure of Aho-Corasick should be reasonably
clear.
# NFAs and DFAs
There are generally two types of finite automata: non-deterministic finite
automata (NFA) and deterministic finite automata (DFA). The difference between
them is, principally, that an NFA can be in multiple states at once. This is
typically accomplished by things called _epsilon_ transitions, where one could
move to a new state without consuming any bytes from the input. (The other
mechanism by which NFAs can be in more than one state is where the same byte in
a particular state transitions to multiple distinct states.) In contrast, a DFA
can only ever be in one state at a time. A DFA has no epsilon transitions, and
for any given state, a byte transitions to at most one other state.
By this formulation, the Aho-Corasick automaton described in the previous
section is an NFA. This is because failure transitions are, effectively,
epsilon transitions. That is, whenever the automaton is in state `S`, it is
actually in the set of states that are reachable by recursively following
failure transitions from `S` until you reach the start state. (This means
that, for example, the start state is always active since the start state is
reachable via failure transitions from any state in the automaton.)
NFAs have a lot of nice properties. They tend to be easier to construct, and
also tend to use less memory. However, their primary downside is that they are
typically slower to execute a search with. For example, the code above showing
how to search with an Aho-Corasick automaton needs to potentially iterate
through many failure transitions for every byte of input. While this is a
fairly small amount of overhead, this can add up, especially if the automaton
has a lot of overlapping patterns with a lot of failure transitions.
A DFA's search code, by contrast, looks like this:
fn contains(dfa: &DFA, haystack: &[u8]) -> bool {
let mut state_id = dfa.start();
// If the empty pattern is in dfa, then state_id is a match state.
if dfa.is_match(state_id) {
return true;
}
for (i, &b) in haystack.iter().enumerate() {
// An Aho-Corasick DFA *never* has a missing state that requires
// failure transitions to be followed. One byte of input advances the
// automaton by one state. Always.
state_id = dfa.next_state(state_id, b);
if dfa.is_match(state_id) {
return true;
}
}
false
}
The search logic here is much simpler than for the NFA, and this tends to
translate into significant performance benefits as well, since there's a lot
less work being done for each byte in the haystack. How is this accomplished?
It's done by pre-following all failure transitions for all states for all bytes
in the alphabet, and then building a single state transition table. Building
this DFA can be much more costly than building the NFA, and use much more
memory, but the better performance can be worth it.
Users of this crate can actually choose between using one of two possible NFAs
(noncontiguous or contiguous) or a DFA. By default, a contiguous NFA is used,
in most circumstances, but if the number of patterns is small enough a DFA will
be used. A contiguous NFA is chosen because it uses orders of magnitude less
memory than a DFA, takes only a little longer to build than a noncontiguous
NFA and usually gets pretty close to the search speed of a DFA. (Callers can
override this automatic selection via the `AhoCorasickBuilder::start_kind`
configuration.)
# More DFA tricks
As described in the previous section, one of the downsides of using a DFA
is that it uses more memory and can take longer to build. One small way of
mitigating these concerns is to map the alphabet used by the automaton into
a smaller space. Typically, the alphabet of a DFA has 256 elements in it:
one element for each possible value that fits into a byte. However, in many
cases, one does not need the full alphabet. For example, if all patterns in an
Aho-Corasick automaton are ASCII letters, then this only uses up 52 distinct
bytes. As far as the automaton is concerned, the rest of the 204 bytes are
indistinguishable from one another: they will never disrciminate between a
match or a non-match. Therefore, in cases like that, the alphabet can be shrunk
to just 53 elements. One for each ASCII letter, and then another to serve as a
placeholder for every other unused byte.
In practice, this library doesn't quite compute the optimal set of equivalence
classes, but it's close enough in most cases. The key idea is that this then
allows the transition table for the DFA to be potentially much smaller. The
downside of doing this, however, is that since the transition table is defined
in terms of this smaller alphabet space, every byte in the haystack must be
re-mapped to this smaller space. This requires an additional 256-byte table.
In practice, this can lead to a small search time hit, but it can be difficult
to measure. Moreover, it can sometimes lead to faster search times for bigger
automata, since it could be difference between more parts of the automaton
staying in the CPU cache or not.
One other trick for DFAs employed by this crate is the notion of premultiplying
state identifiers. Specifically, the normal way to compute the next transition
in a DFA is via the following (assuming that the transition table is laid out
sequentially in memory, in row-major order, where the rows are states):
next_state_id = dfa.transitions[current_state_id * 256 + current_byte]
However, since the value `256` is a fixed constant, we can actually premultiply
the state identifiers in the table when we build the table initially. Then, the
next transition computation simply becomes:
next_state_id = dfa.transitions[current_state_id + current_byte]
This doesn't seem like much, but when this is being executed for every byte of
input that you're searching, saving that extra multiplication instruction can
add up.
The same optimization works even when equivalence classes are enabled, as
described above. The only difference is that the premultiplication is by the
total number of equivalence classes instead of 256.
There isn't much downside to premultiplying state identifiers, other than it
imposes a smaller limit on the total number of states in the DFA. Namely, with
premultiplied state identifiers, you run out of room in your state identifier
representation more rapidly than if the identifiers are just state indices.
Both equivalence classes and premultiplication are always enabled. There is a
`AhoCorasickBuilder::byte_classes` configuration, but disabling this just makes
it so there are always 256 equivalence classes, i.e., every class corresponds
to precisely one byte. When it's disabled, the equivalence class map itself is
still used. The purpose of disabling it is when one is debugging the underlying
automaton. It can be easier to comprehend when it uses actual byte values for
its transitions instead of equivalence classes.
# Match semantics
One of the more interesting things about this implementation of Aho-Corasick
that (as far as this author knows) separates it from other implementations, is
that it natively supports leftmost-first and leftmost-longest match semantics.
Briefly, match semantics refer to the decision procedure by which searching
will disambiguate matches when there are multiple to choose from:
* **standard** match semantics emits matches as soon as they are detected by
the automaton. This is typically equivalent to the textbook non-overlapping
formulation of Aho-Corasick.
* **leftmost-first** match semantics means that 1) the next match is the match
starting at the leftmost position and 2) among multiple matches starting at
the same leftmost position, the match corresponding to the pattern provided
first by the caller is reported.
* **leftmost-longest** is like leftmost-first, except when there are multiple
matches starting at the same leftmost position, the pattern corresponding to
the longest match is returned.
(The crate API documentation discusses these differences, with examples, in
more depth on the `MatchKind` type.)
The reason why supporting these match semantics is important is because it
gives the user more control over the match procedure. For example,
leftmost-first permits users to implement match priority by simply putting the
higher priority patterns first. Leftmost-longest, on the other hand, permits
finding the longest possible match, which might be useful when trying to find
words matching a dictionary. Additionally, regex engines often want to use
Aho-Corasick as an optimization when searching for an alternation of literals.
In order to preserve correct match semantics, regex engines typically can't use
the standard textbook definition directly, since regex engines will implement
either leftmost-first (Perl-like) or leftmost-longest (POSIX) match semantics.
Supporting leftmost semantics requires a couple key changes:
* Constructing the Aho-Corasick automaton changes a bit in both how the trie is
constructed and how failure transitions are found. Namely, only a subset
of the failure transitions are added. Specifically, only the failure
transitions that either do not occur after a match or do occur after a match
but preserve that match are kept. (More details on this can be found in
`src/nfa/noncontiguous.rs`.)
* The search algorithm changes slightly. Since we are looking for the leftmost
match, we cannot quit as soon as a match is detected. Instead, after a match
is detected, we must keep searching until either the end of the input or
until a dead state is seen. (Dead states are not used for standard match
semantics. Dead states mean that searching should stop after a match has been
found.)
Most other implementations of Aho-Corasick do support leftmost match semantics,
but they do it with more overhead at search time, or even worse, with a queue
of matches and sophisticated hijinks to disambiguate the matches. While our
construction algorithm becomes a bit more complicated, the correct match
semantics fall out from the structure of the automaton itself.
# Overlapping matches
One of the nice properties of an Aho-Corasick automaton is that it can report
all possible matches, even when they overlap with one another. In this mode,
the match semantics don't matter, since all possible matches are reported.
Overlapping searches work just like regular searches, except the state
identifier at which the previous search left off is carried over to the next
search, so that it can pick up where it left off. If there are additional
matches at that state, then they are reported before resuming the search.
Enabling leftmost-first or leftmost-longest match semantics causes the
automaton to use a subset of all failure transitions, which means that
overlapping searches cannot be used. Therefore, if leftmost match semantics are
used, attempting to do an overlapping search will return an error (or panic
when using the infallible APIs). Thus, to get overlapping searches, the caller
must use the default standard match semantics. This behavior was chosen because
there are only two alternatives, which were deemed worse:
* Compile two automatons internally, one for standard semantics and one for
the semantics requested by the caller (if not standard).
* Create a new type, distinct from the `AhoCorasick` type, which has different
capabilities based on the configuration options.
The first is untenable because of the amount of memory used by the automaton.
The second increases the complexity of the API too much by adding too many
types that do similar things. It is conceptually much simpler to keep all
searching isolated to a single type.
# Stream searching
Since Aho-Corasick is an automaton, it is possible to do partial searches on
partial parts of the haystack, and then resume that search on subsequent pieces
of the haystack. This is useful when the haystack you're trying to search is
not stored contiguously in memory, or if one does not want to read the entire
haystack into memory at once.
Currently, only standard semantics are supported for stream searching. This is
some of the more complicated code in this crate, and is something I would very
much like to improve. In particular, it currently has the restriction that it
must buffer at least enough of the haystack in memory in order to fit the
longest possible match. The difficulty in getting stream searching right is
that the implementation choices (such as the buffer size) often impact what the
API looks like and what it's allowed to do.
# Prefilters
In some cases, Aho-Corasick is not the fastest way to find matches containing
multiple patterns. Sometimes, the search can be accelerated using highly
optimized SIMD routines. For example, consider searching the following
patterns:
Sherlock
Moriarty
Watson
It is plausible that it would be much faster to quickly look for occurrences of
the leading bytes, `S`, `M` or `W`, before trying to start searching via the
automaton. Indeed, this is exactly what this crate will do.
When there are more than three distinct starting bytes, then this crate will
look for three distinct bytes occurring at any position in the patterns, while
preferring bytes that are heuristically determined to be rare over others. For
example:
Abuzz
Sanchez
Vasquez
Topaz
Waltz
Here, we have more than 3 distinct starting bytes, but all of the patterns
contain `z`, which is typically a rare byte. In this case, the prefilter will
scan for `z`, back up a bit, and then execute the Aho-Corasick automaton.
If all of that fails, then a packed multiple substring algorithm will be
attempted. Currently, the only algorithm available for this is Teddy, but more
may be added in the future. Teddy is unlike the above prefilters in that it
confirms its own matches, so when Teddy is active, it might not be necessary
for Aho-Corasick to run at all. However, the current Teddy implementation
only works in `x86_64` when SSSE3 or AVX2 are available or in `aarch64`
(using NEON), and moreover, only works _well_ when there are a small number
of patterns (say, less than 100). Teddy also requires the haystack to be of a
certain length (more than 16-34 bytes). When the haystack is shorter than that,
Rabin-Karp is used instead. (See `src/packed/rabinkarp.rs`.)
There is a more thorough description of Teddy at
[`src/packed/teddy/README.md`](src/packed/teddy/README.md).

View File

@@ -1,21 +0,0 @@
The MIT License (MIT)
Copyright (c) 2015 Andrew Gallant
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

View File

@@ -1,174 +0,0 @@
aho-corasick
============
A library for finding occurrences of many patterns at once with SIMD
acceleration in some cases. This library provides multiple pattern
search principally through an implementation of the
[Aho-Corasick algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm),
which builds a finite state machine for executing searches in linear time.
Features include case insensitive matching, overlapping matches, fast searching
via SIMD and optional full DFA construction and search & replace in streams.
[![Build status](https://github.com/BurntSushi/aho-corasick/workflows/ci/badge.svg)](https://github.com/BurntSushi/aho-corasick/actions)
[![crates.io](https://img.shields.io/crates/v/aho-corasick.svg)](https://crates.io/crates/aho-corasick)
Dual-licensed under MIT or the [UNLICENSE](https://unlicense.org/).
### Documentation
https://docs.rs/aho-corasick
### Usage
Run `cargo add aho-corasick` to automatically add this crate as a dependency
in your `Cargo.toml` file.
### Example: basic searching
This example shows how to search for occurrences of multiple patterns
simultaneously. Each match includes the pattern that matched along with the
byte offsets of the match.
```rust
use aho_corasick::{AhoCorasick, PatternID};
let patterns = &["apple", "maple", "Snapple"];
let haystack = "Nobody likes maple in their apple flavored Snapple.";
let ac = AhoCorasick::new(patterns).unwrap();
let mut matches = vec![];
for mat in ac.find_iter(haystack) {
matches.push((mat.pattern(), mat.start(), mat.end()));
}
assert_eq!(matches, vec![
(PatternID::must(1), 13, 18),
(PatternID::must(0), 28, 33),
(PatternID::must(2), 43, 50),
]);
```
### Example: ASCII case insensitivity
This is like the previous example, but matches `Snapple` case insensitively
using `AhoCorasickBuilder`:
```rust
use aho_corasick::{AhoCorasick, PatternID};
let patterns = &["apple", "maple", "snapple"];
let haystack = "Nobody likes maple in their apple flavored Snapple.";
let ac = AhoCorasick::builder()
.ascii_case_insensitive(true)
.build(patterns)
.unwrap();
let mut matches = vec![];
for mat in ac.find_iter(haystack) {
matches.push((mat.pattern(), mat.start(), mat.end()));
}
assert_eq!(matches, vec![
(PatternID::must(1), 13, 18),
(PatternID::must(0), 28, 33),
(PatternID::must(2), 43, 50),
]);
```
### Example: replacing matches in a stream
This example shows how to execute a search and replace on a stream without
loading the entire stream into memory first.
```rust,ignore
use aho_corasick::AhoCorasick;
let patterns = &["fox", "brown", "quick"];
let replace_with = &["sloth", "grey", "slow"];
// In a real example, these might be `std::fs::File`s instead. All you need to
// do is supply a pair of `std::io::Read` and `std::io::Write` implementations.
let rdr = "The quick brown fox.";
let mut wtr = vec![];
let ac = AhoCorasick::new(patterns).unwrap();
ac.stream_replace_all(rdr.as_bytes(), &mut wtr, replace_with)
.expect("stream_replace_all failed");
assert_eq!(b"The slow grey sloth.".to_vec(), wtr);
```
### Example: finding the leftmost first match
In the textbook description of Aho-Corasick, its formulation is typically
structured such that it reports all possible matches, even when they overlap
with another. In many cases, overlapping matches may not be desired, such as
the case of finding all successive non-overlapping matches like you might with
a standard regular expression.
Unfortunately the "obvious" way to modify the Aho-Corasick algorithm to do
this doesn't always work in the expected way, since it will report matches as
soon as they are seen. For example, consider matching the regex `Samwise|Sam`
against the text `Samwise`. Most regex engines (that are Perl-like, or
non-POSIX) will report `Samwise` as a match, but the standard Aho-Corasick
algorithm modified for reporting non-overlapping matches will report `Sam`.
A novel contribution of this library is the ability to change the match
semantics of Aho-Corasick (without additional search time overhead) such that
`Samwise` is reported instead. For example, here's the standard approach:
```rust
use aho_corasick::AhoCorasick;
let patterns = &["Samwise", "Sam"];
let haystack = "Samwise";
let ac = AhoCorasick::new(patterns).unwrap();
let mat = ac.find(haystack).expect("should have a match");
assert_eq!("Sam", &haystack[mat.start()..mat.end()]);
```
And now here's the leftmost-first version, which matches how a Perl-like
regex will work:
```rust
use aho_corasick::{AhoCorasick, MatchKind};
let patterns = &["Samwise", "Sam"];
let haystack = "Samwise";
let ac = AhoCorasick::builder()
.match_kind(MatchKind::LeftmostFirst)
.build(patterns)
.unwrap();
let mat = ac.find(haystack).expect("should have a match");
assert_eq!("Samwise", &haystack[mat.start()..mat.end()]);
```
In addition to leftmost-first semantics, this library also supports
leftmost-longest semantics, which match the POSIX behavior of a regular
expression alternation. See `MatchKind` in the docs for more details.
### Minimum Rust version policy
This crate's minimum supported `rustc` version is `1.60.0`.
The current policy is that the minimum Rust version required to use this crate
can be increased in minor version updates. For example, if `crate 1.0` requires
Rust 1.20.0, then `crate 1.0.z` for all values of `z` will also require Rust
1.20.0 or newer. However, `crate 1.y` for `y > 0` may require a newer minimum
version of Rust.
In general, this crate will be conservative with respect to the minimum
supported version of Rust.
### FFI bindings
* [G-Research/ahocorasick_rs](https://github.com/G-Research/ahocorasick_rs/)
is a Python wrapper for this library.
* [tmikus/ahocorasick_rs](https://github.com/tmikus/ahocorasick_rs) is a Go
wrapper for this library.

View File

@@ -1,24 +0,0 @@
This is free and unencumbered software released into the public domain.
Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.
In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
For more information, please refer to <http://unlicense.org/>

View File

@@ -1,2 +0,0 @@
max_width = 79
use_small_heuristics = "max"

File diff suppressed because it is too large Load Diff

File diff suppressed because it is too large Load Diff

View File

@@ -1,835 +0,0 @@
/*!
Provides direct access to a DFA implementation of Aho-Corasick.
This is a low-level API that generally only needs to be used in niche
circumstances. When possible, prefer using [`AhoCorasick`](crate::AhoCorasick)
instead of a DFA directly. Using an `DFA` directly is typically only necessary
when one needs access to the [`Automaton`] trait implementation.
*/
use alloc::{vec, vec::Vec};
use crate::{
automaton::Automaton,
nfa::noncontiguous,
util::{
alphabet::ByteClasses,
error::{BuildError, MatchError},
int::{Usize, U32},
prefilter::Prefilter,
primitives::{IteratorIndexExt, PatternID, SmallIndex, StateID},
search::{Anchored, MatchKind, StartKind},
special::Special,
},
};
/// A DFA implementation of Aho-Corasick.
///
/// When possible, prefer using [`AhoCorasick`](crate::AhoCorasick) instead of
/// this type directly. Using a `DFA` directly is typically only necessary when
/// one needs access to the [`Automaton`] trait implementation.
///
/// This DFA can only be built by first constructing a [`noncontiguous::NFA`].
/// Both [`DFA::new`] and [`Builder::build`] do this for you automatically, but
/// [`Builder::build_from_noncontiguous`] permits doing it explicitly.
///
/// A DFA provides the best possible search performance (in this crate) via two
/// mechanisms:
///
/// * All states use a dense representation for their transitions.
/// * All failure transitions are pre-computed such that they are never
/// explicitly handled at search time.
///
/// These two facts combined mean that every state transition is performed
/// using a constant number of instructions. However, this comes at
/// great cost. The memory usage of a DFA can be quite exorbitant.
/// It is potentially multiple orders of magnitude greater than a
/// [`contiguous::NFA`](crate::nfa::contiguous::NFA) for example. In exchange,
/// a DFA will typically have better search speed than a `contiguous::NFA`, but
/// not by orders of magnitude.
///
/// Unless you have a small number of patterns or memory usage is not a concern
/// and search performance is critical, a DFA is usually not the best choice.
///
/// Moreover, unlike the NFAs in this crate, it is costly for a DFA to
/// support for anchored and unanchored search configurations. Namely,
/// since failure transitions are pre-computed, supporting both anchored
/// and unanchored searches requires a duplication of the transition table,
/// making the memory usage of such a DFA ever bigger. (The NFAs in this crate
/// unconditionally support both anchored and unanchored searches because there
/// is essentially no added cost for doing so.) It is for this reason that
/// a DFA's support for anchored and unanchored searches can be configured
/// via [`Builder::start_kind`]. By default, a DFA only supports unanchored
/// searches.
///
/// # Example
///
/// This example shows how to build an `DFA` directly and use it to execute
/// [`Automaton::try_find`]:
///
/// ```
/// use aho_corasick::{
/// automaton::Automaton,
/// dfa::DFA,
/// Input, Match,
/// };
///
/// let patterns = &["b", "abc", "abcd"];
/// let haystack = "abcd";
///
/// let nfa = DFA::new(patterns).unwrap();
/// assert_eq!(
/// Some(Match::must(0, 1..2)),
/// nfa.try_find(&Input::new(haystack))?,
/// );
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// It is also possible to implement your own version of `try_find`. See the
/// [`Automaton`] documentation for an example.
#[derive(Clone)]
pub struct DFA {
/// The DFA transition table. IDs in this table are pre-multiplied. So
/// instead of the IDs being 0, 1, 2, 3, ..., they are 0*stride, 1*stride,
/// 2*stride, 3*stride, ...
trans: Vec<StateID>,
/// The matches for every match state in this DFA. This is first indexed by
/// state index (so that's `sid >> stride2`) and then by order in which the
/// matches are meant to occur.
matches: Vec<Vec<PatternID>>,
/// The amount of heap memory used, in bytes, by the inner Vecs of
/// 'matches'.
matches_memory_usage: usize,
/// The length of each pattern. This is used to compute the start offset
/// of a match.
pattern_lens: Vec<SmallIndex>,
/// A prefilter for accelerating searches, if one exists.
prefilter: Option<Prefilter>,
/// The match semantics built into this DFA.
match_kind: MatchKind,
/// The total number of states in this DFA.
state_len: usize,
/// The alphabet size, or total number of equivalence classes, for this
/// DFA. Note that the actual number of transitions in each state is
/// stride=2^stride2, where stride is the smallest power of 2 greater than
/// or equal to alphabet_len. We do things this way so that we can use
/// bitshifting to go from a state ID to an index into 'matches'.
alphabet_len: usize,
/// The exponent with a base 2, such that stride=2^stride2. Given a state
/// index 'i', its state identifier is 'i << stride2'. Given a state
/// identifier 'sid', its state index is 'sid >> stride2'.
stride2: usize,
/// The equivalence classes for this DFA. All transitions are defined on
/// equivalence classes and not on the 256 distinct byte values.
byte_classes: ByteClasses,
/// The length of the shortest pattern in this automaton.
min_pattern_len: usize,
/// The length of the longest pattern in this automaton.
max_pattern_len: usize,
/// The information required to deduce which states are "special" in this
/// DFA.
special: Special,
}
impl DFA {
/// Create a new Aho-Corasick DFA using the default configuration.
///
/// Use a [`Builder`] if you want to change the configuration.
pub fn new<I, P>(patterns: I) -> Result<DFA, BuildError>
where
I: IntoIterator<Item = P>,
P: AsRef<[u8]>,
{
DFA::builder().build(patterns)
}
/// A convenience method for returning a new Aho-Corasick DFA builder.
///
/// This usually permits one to just import the `DFA` type.
pub fn builder() -> Builder {
Builder::new()
}
}
impl DFA {
/// A sentinel state ID indicating that a search should stop once it has
/// entered this state. When a search stops, it returns a match if one has
/// been found, otherwise no match. A DFA always has an actual dead state
/// at this ID.
///
/// N.B. DFAs, unlike NFAs, do not have any notion of a FAIL state.
/// Namely, the whole point of a DFA is that the FAIL state is completely
/// compiled away. That is, DFA construction involves pre-computing the
/// failure transitions everywhere, such that failure transitions are no
/// longer used at search time. This, combined with its uniformly dense
/// representation, are the two most important factors in why it's faster
/// than the NFAs in this crate.
const DEAD: StateID = StateID::new_unchecked(0);
/// Adds the given pattern IDs as matches to the given state and also
/// records the added memory usage.
fn set_matches(
&mut self,
sid: StateID,
pids: impl Iterator<Item = PatternID>,
) {
let index = (sid.as_usize() >> self.stride2).checked_sub(2).unwrap();
let mut at_least_one = false;
for pid in pids {
self.matches[index].push(pid);
self.matches_memory_usage += PatternID::SIZE;
at_least_one = true;
}
assert!(at_least_one, "match state must have non-empty pids");
}
}
// SAFETY: 'start_state' always returns a valid state ID, 'next_state' always
// returns a valid state ID given a valid state ID. We otherwise claim that
// all other methods are correct as well.
unsafe impl Automaton for DFA {
#[inline(always)]
fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError> {
// Either of the start state IDs can be DEAD, in which case, support
// for that type of search is not provided by this DFA. Which start
// state IDs are inactive depends on the 'StartKind' configuration at
// DFA construction time.
match anchored {
Anchored::No => {
let start = self.special.start_unanchored_id;
if start == DFA::DEAD {
Err(MatchError::invalid_input_unanchored())
} else {
Ok(start)
}
}
Anchored::Yes => {
let start = self.special.start_anchored_id;
if start == DFA::DEAD {
Err(MatchError::invalid_input_anchored())
} else {
Ok(start)
}
}
}
}
#[inline(always)]
fn next_state(
&self,
_anchored: Anchored,
sid: StateID,
byte: u8,
) -> StateID {
let class = self.byte_classes.get(byte);
self.trans[(sid.as_u32() + u32::from(class)).as_usize()]
}
#[inline(always)]
fn is_special(&self, sid: StateID) -> bool {
sid <= self.special.max_special_id
}
#[inline(always)]
fn is_dead(&self, sid: StateID) -> bool {
sid == DFA::DEAD
}
#[inline(always)]
fn is_match(&self, sid: StateID) -> bool {
!self.is_dead(sid) && sid <= self.special.max_match_id
}
#[inline(always)]
fn is_start(&self, sid: StateID) -> bool {
sid == self.special.start_unanchored_id
|| sid == self.special.start_anchored_id
}
#[inline(always)]
fn match_kind(&self) -> MatchKind {
self.match_kind
}
#[inline(always)]
fn patterns_len(&self) -> usize {
self.pattern_lens.len()
}
#[inline(always)]
fn pattern_len(&self, pid: PatternID) -> usize {
self.pattern_lens[pid].as_usize()
}
#[inline(always)]
fn min_pattern_len(&self) -> usize {
self.min_pattern_len
}
#[inline(always)]
fn max_pattern_len(&self) -> usize {
self.max_pattern_len
}
#[inline(always)]
fn match_len(&self, sid: StateID) -> usize {
debug_assert!(self.is_match(sid));
let offset = (sid.as_usize() >> self.stride2) - 2;
self.matches[offset].len()
}
#[inline(always)]
fn match_pattern(&self, sid: StateID, index: usize) -> PatternID {
debug_assert!(self.is_match(sid));
let offset = (sid.as_usize() >> self.stride2) - 2;
self.matches[offset][index]
}
#[inline(always)]
fn memory_usage(&self) -> usize {
use core::mem::size_of;
(self.trans.len() * size_of::<u32>())
+ (self.matches.len() * size_of::<Vec<PatternID>>())
+ self.matches_memory_usage
+ (self.pattern_lens.len() * size_of::<SmallIndex>())
+ self.prefilter.as_ref().map_or(0, |p| p.memory_usage())
}
#[inline(always)]
fn prefilter(&self) -> Option<&Prefilter> {
self.prefilter.as_ref()
}
}
impl core::fmt::Debug for DFA {
fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
use crate::{
automaton::{fmt_state_indicator, sparse_transitions},
util::debug::DebugByte,
};
writeln!(f, "dfa::DFA(")?;
for index in 0..self.state_len {
let sid = StateID::new_unchecked(index << self.stride2);
// While we do currently include the FAIL state in the transition
// table (to simplify construction), it is never actually used. It
// poses problems with the code below because it gets treated as
// a match state incidentally when it is, of course, not. So we
// special case it. The fail state is always the first state after
// the dead state.
//
// If the construction is changed to remove the fail state (it
// probably should be), then this special case should be updated.
if index == 1 {
writeln!(f, "F {:06}:", sid.as_usize())?;
continue;
}
fmt_state_indicator(f, self, sid)?;
write!(f, "{:06}: ", sid.as_usize())?;
let it = (0..self.byte_classes.alphabet_len()).map(|class| {
(class.as_u8(), self.trans[sid.as_usize() + class])
});
for (i, (start, end, next)) in sparse_transitions(it).enumerate() {
if i > 0 {
write!(f, ", ")?;
}
if start == end {
write!(
f,
"{:?} => {:?}",
DebugByte(start),
next.as_usize()
)?;
} else {
write!(
f,
"{:?}-{:?} => {:?}",
DebugByte(start),
DebugByte(end),
next.as_usize()
)?;
}
}
write!(f, "\n")?;
if self.is_match(sid) {
write!(f, " matches: ")?;
for i in 0..self.match_len(sid) {
if i > 0 {
write!(f, ", ")?;
}
let pid = self.match_pattern(sid, i);
write!(f, "{}", pid.as_usize())?;
}
write!(f, "\n")?;
}
}
writeln!(f, "match kind: {:?}", self.match_kind)?;
writeln!(f, "prefilter: {:?}", self.prefilter.is_some())?;
writeln!(f, "state length: {:?}", self.state_len)?;
writeln!(f, "pattern length: {:?}", self.patterns_len())?;
writeln!(f, "shortest pattern length: {:?}", self.min_pattern_len)?;
writeln!(f, "longest pattern length: {:?}", self.max_pattern_len)?;
writeln!(f, "alphabet length: {:?}", self.alphabet_len)?;
writeln!(f, "stride: {:?}", 1 << self.stride2)?;
writeln!(f, "byte classes: {:?}", self.byte_classes)?;
writeln!(f, "memory usage: {:?}", self.memory_usage())?;
writeln!(f, ")")?;
Ok(())
}
}
/// A builder for configuring an Aho-Corasick DFA.
///
/// This builder has a subset of the options available to a
/// [`AhoCorasickBuilder`](crate::AhoCorasickBuilder). Of the shared options,
/// their behavior is identical.
#[derive(Clone, Debug)]
pub struct Builder {
noncontiguous: noncontiguous::Builder,
start_kind: StartKind,
byte_classes: bool,
}
impl Default for Builder {
fn default() -> Builder {
Builder {
noncontiguous: noncontiguous::Builder::new(),
start_kind: StartKind::Unanchored,
byte_classes: true,
}
}
}
impl Builder {
/// Create a new builder for configuring an Aho-Corasick DFA.
pub fn new() -> Builder {
Builder::default()
}
/// Build an Aho-Corasick DFA from the given iterator of patterns.
///
/// A builder may be reused to create more DFAs.
pub fn build<I, P>(&self, patterns: I) -> Result<DFA, BuildError>
where
I: IntoIterator<Item = P>,
P: AsRef<[u8]>,
{
let nnfa = self.noncontiguous.build(patterns)?;
self.build_from_noncontiguous(&nnfa)
}
/// Build an Aho-Corasick DFA from the given noncontiguous NFA.
///
/// Note that when this method is used, only the `start_kind` and
/// `byte_classes` settings on this builder are respected. The other
/// settings only apply to the initial construction of the Aho-Corasick
/// automaton. Since using this method requires that initial construction
/// has already completed, all settings impacting only initial construction
/// are no longer relevant.
pub fn build_from_noncontiguous(
&self,
nnfa: &noncontiguous::NFA,
) -> Result<DFA, BuildError> {
debug!("building DFA");
let byte_classes = if self.byte_classes {
nnfa.byte_classes().clone()
} else {
ByteClasses::singletons()
};
let state_len = match self.start_kind {
StartKind::Unanchored | StartKind::Anchored => nnfa.states().len(),
StartKind::Both => {
// These unwraps are OK because we know that the number of
// NFA states is < StateID::LIMIT which is in turn less than
// i32::MAX. Thus, there is always room to multiply by 2.
// Finally, the number of states is always at least 4 in the
// NFA (DEAD, FAIL, START-UNANCHORED, START-ANCHORED), so the
// subtraction of 4 is okay.
//
// Note that we subtract 4 because the "anchored" part of
// the DFA duplicates the unanchored part (without failure
// transitions), but reuses the DEAD, FAIL and START states.
nnfa.states()
.len()
.checked_mul(2)
.unwrap()
.checked_sub(4)
.unwrap()
}
};
let trans_len =
match state_len.checked_shl(byte_classes.stride2().as_u32()) {
Some(trans_len) => trans_len,
None => {
return Err(BuildError::state_id_overflow(
StateID::MAX.as_u64(),
usize::MAX.as_u64(),
))
}
};
StateID::new(trans_len.checked_sub(byte_classes.stride()).unwrap())
.map_err(|e| {
BuildError::state_id_overflow(
StateID::MAX.as_u64(),
e.attempted(),
)
})?;
let num_match_states = match self.start_kind {
StartKind::Unanchored | StartKind::Anchored => {
nnfa.special().max_match_id.as_usize().checked_sub(1).unwrap()
}
StartKind::Both => nnfa
.special()
.max_match_id
.as_usize()
.checked_sub(1)
.unwrap()
.checked_mul(2)
.unwrap(),
};
let mut dfa = DFA {
trans: vec![DFA::DEAD; trans_len],
matches: vec![vec![]; num_match_states],
matches_memory_usage: 0,
pattern_lens: nnfa.pattern_lens_raw().to_vec(),
prefilter: nnfa.prefilter().cloned(),
match_kind: nnfa.match_kind(),
state_len,
alphabet_len: byte_classes.alphabet_len(),
stride2: byte_classes.stride2(),
byte_classes,
min_pattern_len: nnfa.min_pattern_len(),
max_pattern_len: nnfa.max_pattern_len(),
// The special state IDs are set later.
special: Special::zero(),
};
match self.start_kind {
StartKind::Both => {
self.finish_build_both_starts(nnfa, &mut dfa);
}
StartKind::Unanchored => {
self.finish_build_one_start(Anchored::No, nnfa, &mut dfa);
}
StartKind::Anchored => {
self.finish_build_one_start(Anchored::Yes, nnfa, &mut dfa)
}
}
debug!(
"DFA built, <states: {:?}, size: {:?}, \
alphabet len: {:?}, stride: {:?}>",
dfa.state_len,
dfa.memory_usage(),
dfa.byte_classes.alphabet_len(),
dfa.byte_classes.stride(),
);
// The vectors can grow ~twice as big during construction because a
// Vec amortizes growth. But here, let's shrink things back down to
// what we actually need since we're never going to add more to it.
dfa.trans.shrink_to_fit();
dfa.pattern_lens.shrink_to_fit();
dfa.matches.shrink_to_fit();
// TODO: We might also want to shrink each Vec inside of `dfa.matches`,
// or even better, convert it to one contiguous allocation. But I think
// I went with nested allocs for good reason (can't remember), so this
// may be tricky to do. I decided not to shrink them here because it
// might require a fair bit of work to do. It's unclear whether it's
// worth it.
Ok(dfa)
}
/// Finishes building a DFA for either unanchored or anchored searches,
/// but NOT both.
fn finish_build_one_start(
&self,
anchored: Anchored,
nnfa: &noncontiguous::NFA,
dfa: &mut DFA,
) {
// This function always succeeds because we check above that all of the
// states in the NFA can be mapped to DFA state IDs.
let stride2 = dfa.stride2;
let old2new = |oldsid: StateID| {
StateID::new_unchecked(oldsid.as_usize() << stride2)
};
for (oldsid, state) in nnfa.states().iter().with_state_ids() {
let newsid = old2new(oldsid);
if state.is_match() {
dfa.set_matches(newsid, nnfa.iter_matches(oldsid));
}
sparse_iter(
nnfa,
oldsid,
&dfa.byte_classes,
|byte, class, mut oldnextsid| {
if oldnextsid == noncontiguous::NFA::FAIL {
if anchored.is_anchored() {
oldnextsid = noncontiguous::NFA::DEAD;
} else if state.fail() == noncontiguous::NFA::DEAD {
// This is a special case that avoids following
// DEAD transitions in a non-contiguous NFA.
// Following these transitions is pretty slow
// because the non-contiguous NFA will always use
// a sparse representation for it (because the
// DEAD state is usually treated as a sentinel).
// The *vast* majority of failure states are DEAD
// states, so this winds up being pretty slow if
// we go through the non-contiguous NFA state
// transition logic. Instead, just do it ourselves.
oldnextsid = noncontiguous::NFA::DEAD;
} else {
oldnextsid = nnfa.next_state(
Anchored::No,
state.fail(),
byte,
);
}
}
dfa.trans[newsid.as_usize() + usize::from(class)] =
old2new(oldnextsid);
},
);
}
// Now that we've remapped all the IDs in our states, all that's left
// is remapping the special state IDs.
let old = nnfa.special();
let new = &mut dfa.special;
new.max_special_id = old2new(old.max_special_id);
new.max_match_id = old2new(old.max_match_id);
if anchored.is_anchored() {
new.start_unanchored_id = DFA::DEAD;
new.start_anchored_id = old2new(old.start_anchored_id);
} else {
new.start_unanchored_id = old2new(old.start_unanchored_id);
new.start_anchored_id = DFA::DEAD;
}
}
/// Finishes building a DFA that supports BOTH unanchored and anchored
/// searches. It works by inter-leaving unanchored states with anchored
/// states in the same transition table. This way, we avoid needing to
/// re-shuffle states afterward to ensure that our states still look like
/// DEAD, MATCH, ..., START-UNANCHORED, START-ANCHORED, NON-MATCH, ...
///
/// Honestly this is pretty inscrutable... Simplifications are most
/// welcome.
fn finish_build_both_starts(
&self,
nnfa: &noncontiguous::NFA,
dfa: &mut DFA,
) {
let stride2 = dfa.stride2;
let stride = 1 << stride2;
let mut remap_unanchored = vec![DFA::DEAD; nnfa.states().len()];
let mut remap_anchored = vec![DFA::DEAD; nnfa.states().len()];
let mut is_anchored = vec![false; dfa.state_len];
let mut newsid = DFA::DEAD;
let next_dfa_id =
|sid: StateID| StateID::new_unchecked(sid.as_usize() + stride);
for (oldsid, state) in nnfa.states().iter().with_state_ids() {
if oldsid == noncontiguous::NFA::DEAD
|| oldsid == noncontiguous::NFA::FAIL
{
remap_unanchored[oldsid] = newsid;
remap_anchored[oldsid] = newsid;
newsid = next_dfa_id(newsid);
} else if oldsid == nnfa.special().start_unanchored_id
|| oldsid == nnfa.special().start_anchored_id
{
if oldsid == nnfa.special().start_unanchored_id {
remap_unanchored[oldsid] = newsid;
remap_anchored[oldsid] = DFA::DEAD;
} else {
remap_unanchored[oldsid] = DFA::DEAD;
remap_anchored[oldsid] = newsid;
is_anchored[newsid.as_usize() >> stride2] = true;
}
if state.is_match() {
dfa.set_matches(newsid, nnfa.iter_matches(oldsid));
}
sparse_iter(
nnfa,
oldsid,
&dfa.byte_classes,
|_, class, oldnextsid| {
let class = usize::from(class);
if oldnextsid == noncontiguous::NFA::FAIL {
dfa.trans[newsid.as_usize() + class] = DFA::DEAD;
} else {
dfa.trans[newsid.as_usize() + class] = oldnextsid;
}
},
);
newsid = next_dfa_id(newsid);
} else {
let unewsid = newsid;
newsid = next_dfa_id(newsid);
let anewsid = newsid;
newsid = next_dfa_id(newsid);
remap_unanchored[oldsid] = unewsid;
remap_anchored[oldsid] = anewsid;
is_anchored[anewsid.as_usize() >> stride2] = true;
if state.is_match() {
dfa.set_matches(unewsid, nnfa.iter_matches(oldsid));
dfa.set_matches(anewsid, nnfa.iter_matches(oldsid));
}
sparse_iter(
nnfa,
oldsid,
&dfa.byte_classes,
|byte, class, oldnextsid| {
let class = usize::from(class);
if oldnextsid == noncontiguous::NFA::FAIL {
let oldnextsid =
if state.fail() == noncontiguous::NFA::DEAD {
noncontiguous::NFA::DEAD
} else {
nnfa.next_state(
Anchored::No,
state.fail(),
byte,
)
};
dfa.trans[unewsid.as_usize() + class] = oldnextsid;
} else {
dfa.trans[unewsid.as_usize() + class] = oldnextsid;
dfa.trans[anewsid.as_usize() + class] = oldnextsid;
}
},
);
}
}
for i in 0..dfa.state_len {
let sid = i << stride2;
if is_anchored[i] {
for next in dfa.trans[sid..][..stride].iter_mut() {
*next = remap_anchored[*next];
}
} else {
for next in dfa.trans[sid..][..stride].iter_mut() {
*next = remap_unanchored[*next];
}
}
}
// Now that we've remapped all the IDs in our states, all that's left
// is remapping the special state IDs.
let old = nnfa.special();
let new = &mut dfa.special;
new.max_special_id = remap_anchored[old.max_special_id];
new.max_match_id = remap_anchored[old.max_match_id];
new.start_unanchored_id = remap_unanchored[old.start_unanchored_id];
new.start_anchored_id = remap_anchored[old.start_anchored_id];
}
/// Set the desired match semantics.
///
/// This only applies when using [`Builder::build`] and not
/// [`Builder::build_from_noncontiguous`].
///
/// See
/// [`AhoCorasickBuilder::match_kind`](crate::AhoCorasickBuilder::match_kind)
/// for more documentation and examples.
pub fn match_kind(&mut self, kind: MatchKind) -> &mut Builder {
self.noncontiguous.match_kind(kind);
self
}
/// Enable ASCII-aware case insensitive matching.
///
/// This only applies when using [`Builder::build`] and not
/// [`Builder::build_from_noncontiguous`].
///
/// See
/// [`AhoCorasickBuilder::ascii_case_insensitive`](crate::AhoCorasickBuilder::ascii_case_insensitive)
/// for more documentation and examples.
pub fn ascii_case_insensitive(&mut self, yes: bool) -> &mut Builder {
self.noncontiguous.ascii_case_insensitive(yes);
self
}
/// Enable heuristic prefilter optimizations.
///
/// This only applies when using [`Builder::build`] and not
/// [`Builder::build_from_noncontiguous`].
///
/// See
/// [`AhoCorasickBuilder::prefilter`](crate::AhoCorasickBuilder::prefilter)
/// for more documentation and examples.
pub fn prefilter(&mut self, yes: bool) -> &mut Builder {
self.noncontiguous.prefilter(yes);
self
}
/// Sets the starting state configuration for the automaton.
///
/// See
/// [`AhoCorasickBuilder::start_kind`](crate::AhoCorasickBuilder::start_kind)
/// for more documentation and examples.
pub fn start_kind(&mut self, kind: StartKind) -> &mut Builder {
self.start_kind = kind;
self
}
/// A debug setting for whether to attempt to shrink the size of the
/// automaton's alphabet or not.
///
/// This should never be enabled unless you're debugging an automaton.
/// Namely, disabling byte classes makes transitions easier to reason
/// about, since they use the actual bytes instead of equivalence classes.
/// Disabling this confers no performance benefit at search time.
///
/// See
/// [`AhoCorasickBuilder::byte_classes`](crate::AhoCorasickBuilder::byte_classes)
/// for more documentation and examples.
pub fn byte_classes(&mut self, yes: bool) -> &mut Builder {
self.byte_classes = yes;
self
}
}
/// Iterate over all possible equivalence class transitions in this state.
/// The closure is called for all transitions with a distinct equivalence
/// class, even those not explicitly represented in this sparse state. For
/// any implicitly defined transitions, the given closure is called with
/// the fail state ID.
///
/// The closure is guaranteed to be called precisely
/// `byte_classes.alphabet_len()` times, once for every possible class in
/// ascending order.
fn sparse_iter<F: FnMut(u8, u8, StateID)>(
nnfa: &noncontiguous::NFA,
oldsid: StateID,
classes: &ByteClasses,
mut f: F,
) {
let mut prev_class = None;
let mut byte = 0usize;
for t in nnfa.iter_trans(oldsid) {
while byte < usize::from(t.byte()) {
let rep = byte.as_u8();
let class = classes.get(rep);
byte += 1;
if prev_class != Some(class) {
f(rep, class, noncontiguous::NFA::FAIL);
prev_class = Some(class);
}
}
let rep = t.byte();
let class = classes.get(rep);
byte += 1;
if prev_class != Some(class) {
f(rep, class, t.next());
prev_class = Some(class);
}
}
for b in byte..=255 {
let rep = b.as_u8();
let class = classes.get(rep);
if prev_class != Some(class) {
f(rep, class, noncontiguous::NFA::FAIL);
prev_class = Some(class);
}
}
}

View File

@@ -1,326 +0,0 @@
/*!
A library for finding occurrences of many patterns at once. This library
provides multiple pattern search principally through an implementation of the
[Aho-Corasick algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm),
which builds a fast finite state machine for executing searches in linear time.
Additionally, this library provides a number of configuration options for
building the automaton that permit controlling the space versus time trade
off. Other features include simple ASCII case insensitive matching, finding
overlapping matches, replacements, searching streams and even searching and
replacing text in streams.
Finally, unlike most other Aho-Corasick implementations, this one
supports enabling [leftmost-first](MatchKind::LeftmostFirst) or
[leftmost-longest](MatchKind::LeftmostLongest) match semantics, using a
(seemingly) novel alternative construction algorithm. For more details on what
match semantics means, see the [`MatchKind`] type.
# Overview
This section gives a brief overview of the primary types in this crate:
* [`AhoCorasick`] is the primary type and represents an Aho-Corasick automaton.
This is the type you use to execute searches.
* [`AhoCorasickBuilder`] can be used to build an Aho-Corasick automaton, and
supports configuring a number of options.
* [`Match`] represents a single match reported by an Aho-Corasick automaton.
Each match has two pieces of information: the pattern that matched and the
start and end byte offsets corresponding to the position in the haystack at
which it matched.
# Example: basic searching
This example shows how to search for occurrences of multiple patterns
simultaneously. Each match includes the pattern that matched along with the
byte offsets of the match.
```
use aho_corasick::{AhoCorasick, PatternID};
let patterns = &["apple", "maple", "Snapple"];
let haystack = "Nobody likes maple in their apple flavored Snapple.";
let ac = AhoCorasick::new(patterns).unwrap();
let mut matches = vec![];
for mat in ac.find_iter(haystack) {
matches.push((mat.pattern(), mat.start(), mat.end()));
}
assert_eq!(matches, vec![
(PatternID::must(1), 13, 18),
(PatternID::must(0), 28, 33),
(PatternID::must(2), 43, 50),
]);
```
# Example: case insensitivity
This is like the previous example, but matches `Snapple` case insensitively
using `AhoCorasickBuilder`:
```
use aho_corasick::{AhoCorasick, PatternID};
let patterns = &["apple", "maple", "snapple"];
let haystack = "Nobody likes maple in their apple flavored Snapple.";
let ac = AhoCorasick::builder()
.ascii_case_insensitive(true)
.build(patterns)
.unwrap();
let mut matches = vec![];
for mat in ac.find_iter(haystack) {
matches.push((mat.pattern(), mat.start(), mat.end()));
}
assert_eq!(matches, vec![
(PatternID::must(1), 13, 18),
(PatternID::must(0), 28, 33),
(PatternID::must(2), 43, 50),
]);
```
# Example: replacing matches in a stream
This example shows how to execute a search and replace on a stream without
loading the entire stream into memory first.
```
# #[cfg(feature = "std")] {
use aho_corasick::AhoCorasick;
# fn example() -> Result<(), std::io::Error> {
let patterns = &["fox", "brown", "quick"];
let replace_with = &["sloth", "grey", "slow"];
// In a real example, these might be `std::fs::File`s instead. All you need to
// do is supply a pair of `std::io::Read` and `std::io::Write` implementations.
let rdr = "The quick brown fox.";
let mut wtr = vec![];
let ac = AhoCorasick::new(patterns).unwrap();
ac.try_stream_replace_all(rdr.as_bytes(), &mut wtr, replace_with)?;
assert_eq!(b"The slow grey sloth.".to_vec(), wtr);
# Ok(()) }; example().unwrap()
# }
```
# Example: finding the leftmost first match
In the textbook description of Aho-Corasick, its formulation is typically
structured such that it reports all possible matches, even when they overlap
with another. In many cases, overlapping matches may not be desired, such as
the case of finding all successive non-overlapping matches like you might with
a standard regular expression.
Unfortunately the "obvious" way to modify the Aho-Corasick algorithm to do
this doesn't always work in the expected way, since it will report matches as
soon as they are seen. For example, consider matching the regex `Samwise|Sam`
against the text `Samwise`. Most regex engines (that are Perl-like, or
non-POSIX) will report `Samwise` as a match, but the standard Aho-Corasick
algorithm modified for reporting non-overlapping matches will report `Sam`.
A novel contribution of this library is the ability to change the match
semantics of Aho-Corasick (without additional search time overhead) such that
`Samwise` is reported instead. For example, here's the standard approach:
```
use aho_corasick::AhoCorasick;
let patterns = &["Samwise", "Sam"];
let haystack = "Samwise";
let ac = AhoCorasick::new(patterns).unwrap();
let mat = ac.find(haystack).expect("should have a match");
assert_eq!("Sam", &haystack[mat.start()..mat.end()]);
```
And now here's the leftmost-first version, which matches how a Perl-like
regex will work:
```
use aho_corasick::{AhoCorasick, MatchKind};
let patterns = &["Samwise", "Sam"];
let haystack = "Samwise";
let ac = AhoCorasick::builder()
.match_kind(MatchKind::LeftmostFirst)
.build(patterns)
.unwrap();
let mat = ac.find(haystack).expect("should have a match");
assert_eq!("Samwise", &haystack[mat.start()..mat.end()]);
```
In addition to leftmost-first semantics, this library also supports
leftmost-longest semantics, which match the POSIX behavior of a regular
expression alternation. See [`MatchKind`] for more details.
# Prefilters
While an Aho-Corasick automaton can perform admirably when compared to more
naive solutions, it is generally slower than more specialized algorithms that
are accelerated using vector instructions such as SIMD.
For that reason, this library will internally use a "prefilter" to attempt
to accelerate searches when possible. Currently, this library has several
different algorithms it might use depending on the patterns provided. Once the
number of patterns gets too big, prefilters are no longer used.
While a prefilter is generally good to have on by default since it works
well in the common case, it can lead to less predictable or even sub-optimal
performance in some cases. For that reason, prefilters can be explicitly
disabled via [`AhoCorasickBuilder::prefilter`].
# Lower level APIs
This crate also provides several sub-modules that collectively expose many of
the implementation details of the main [`AhoCorasick`] type. Most users of this
library can completely ignore the submodules and their contents, but if you
needed finer grained control, some parts of them may be useful to you. Here is
a brief overview of each and why you might want to use them:
* The [`packed`] sub-module contains a lower level API for using fast
vectorized routines for finding a small number of patterns in a haystack.
You might want to use this API when you want to completely side-step using
Aho-Corasick automata. Otherwise, the fast vectorized routines are used
automatically as prefilters for `AhoCorasick` searches whenever possible.
* The [`automaton`] sub-module provides a lower level finite state
machine interface that the various Aho-Corasick implementations in
this crate implement. This sub-module's main contribution is the
[`Automaton`](automaton::Automaton) trait, which permits manually walking the
state transitions of an Aho-Corasick automaton.
* The [`dfa`] and [`nfa`] sub-modules provide DFA and NFA implementations of
the aforementioned `Automaton` trait. The main reason one might want to use
these sub-modules is to get access to a type that implements the `Automaton`
trait. (The top-level `AhoCorasick` type does not implement the `Automaton`
trait.)
As mentioned above, if you aren't sure whether you need these sub-modules,
you should be able to safely ignore them and just focus on the [`AhoCorasick`]
type.
# Crate features
This crate exposes a few features for controlling dependency usage and whether
this crate can be used without the standard library.
* **std** -
Enables support for the standard library. This feature is enabled by
default. When disabled, only `core` and `alloc` are used. At an API
level, enabling `std` enables `std::error::Error` trait impls for the
various error types, and higher level stream search routines such as
[`AhoCorasick::try_stream_find_iter`]. But the `std` feature is also required
to enable vectorized prefilters. Prefilters can greatly accelerate searches,
but generally only apply when the number of patterns is small (less than
~100).
* **perf-literal** -
Enables support for literal prefilters that use vectorized routines from
external crates. This feature is enabled by default. If you're only using
Aho-Corasick for large numbers of patterns or otherwise can abide lower
throughput when searching with a small number of patterns, then it is
reasonable to disable this feature.
* **logging** -
Enables a dependency on the `log` crate and emits messages to aide in
diagnostics. This feature is disabled by default.
*/
#![no_std]
#![deny(missing_docs)]
#![deny(rustdoc::broken_intra_doc_links)]
#![cfg_attr(docsrs, feature(doc_cfg))]
extern crate alloc;
#[cfg(any(test, feature = "std"))]
extern crate std;
#[cfg(doctest)]
doc_comment::doctest!("../README.md");
#[cfg(feature = "std")]
pub use crate::ahocorasick::StreamFindIter;
pub use crate::{
ahocorasick::{
AhoCorasick, AhoCorasickBuilder, AhoCorasickKind, FindIter,
FindOverlappingIter,
},
util::{
error::{BuildError, MatchError, MatchErrorKind},
primitives::{PatternID, PatternIDError},
search::{Anchored, Input, Match, MatchKind, Span, StartKind},
},
};
#[macro_use]
mod macros;
mod ahocorasick;
pub mod automaton;
pub mod dfa;
pub mod nfa;
pub mod packed;
#[cfg(test)]
mod tests;
// I wrote out the module for implementing fst::Automaton only to later realize
// that this would make fst a public dependency and fst is not at 1.0 yet. I
// decided to just keep the code in tree, but build it only during tests.
//
// TODO: I think I've changed my mind again. I'm considering pushing it out
// into either a separate crate or into 'fst' directly as an optional feature.
// #[cfg(test)]
// #[allow(dead_code)]
// mod transducer;
pub(crate) mod util;
#[cfg(test)]
mod testoibits {
use std::panic::{RefUnwindSafe, UnwindSafe};
use super::*;
fn assert_all<T: Send + Sync + UnwindSafe + RefUnwindSafe>() {}
#[test]
fn oibits_main() {
assert_all::<AhoCorasick>();
assert_all::<AhoCorasickBuilder>();
assert_all::<AhoCorasickKind>();
assert_all::<FindIter>();
assert_all::<FindOverlappingIter>();
assert_all::<BuildError>();
assert_all::<MatchError>();
assert_all::<MatchErrorKind>();
assert_all::<Anchored>();
assert_all::<Input>();
assert_all::<Match>();
assert_all::<MatchKind>();
assert_all::<Span>();
assert_all::<StartKind>();
}
#[test]
fn oibits_automaton() {
use crate::{automaton, dfa::DFA};
assert_all::<automaton::FindIter<DFA>>();
assert_all::<automaton::FindOverlappingIter<DFA>>();
#[cfg(feature = "std")]
assert_all::<automaton::StreamFindIter<DFA, std::io::Stdin>>();
assert_all::<automaton::OverlappingState>();
assert_all::<automaton::Prefilter>();
assert_all::<automaton::Candidate>();
}
#[test]
fn oibits_packed() {
use crate::packed;
assert_all::<packed::Config>();
assert_all::<packed::Builder>();
assert_all::<packed::Searcher>();
assert_all::<packed::FindIter>();
assert_all::<packed::MatchKind>();
}
}

View File

@@ -1,18 +0,0 @@
#![allow(unused_macros)]
macro_rules! log {
($($tt:tt)*) => {
#[cfg(feature = "logging")]
{
$($tt)*
}
}
}
macro_rules! debug {
($($tt:tt)*) => { log!(log::debug!($($tt)*)) }
}
macro_rules! trace {
($($tt:tt)*) => { log!(log::trace!($($tt)*)) }
}

File diff suppressed because it is too large Load Diff

View File

@@ -1,40 +0,0 @@
/*!
Provides direct access to NFA implementations of Aho-Corasick.
The principle characteristic of an NFA in this crate is that it may
transition through multiple states per byte of haystack. In Aho-Corasick
parlance, NFAs follow failure transitions during a search. In contrast,
a [`DFA`](crate::dfa::DFA) pre-computes all failure transitions during
compilation at the expense of a much bigger memory footprint.
Currently, there are two NFA implementations provided: noncontiguous and
contiguous. The names reflect their internal representation, and consequently,
the trade offs associated with them:
* A [`noncontiguous::NFA`] uses a separate allocation for every NFA state to
represent its transitions in a sparse format. This is ideal for building an
NFA, since it cheaply permits different states to have a different number of
transitions. A noncontiguous NFA is where the main Aho-Corasick construction
algorithm is implemented. All other Aho-Corasick implementations are built by
first constructing a noncontiguous NFA.
* A [`contiguous::NFA`] is uses a single allocation to represent all states,
while still encoding most states as sparse states but permitting states near
the starting state to have a dense representation. The dense representation
uses more memory, but permits computing transitions during a search more
quickly. By only making the most active states dense (the states near the
starting state), a contiguous NFA better balances memory usage with search
speed. The single contiguous allocation also uses less overhead per state and
enables compression tricks where most states only use 8 bytes of heap memory.
When given the choice between these two, you almost always want to pick a
contiguous NFA. It takes only a little longer to build, but both its memory
usage and search speed are typically much better than a noncontiguous NFA. A
noncontiguous NFA is useful when prioritizing build times, or when there are
so many patterns that a contiguous NFA could not be built. (Currently, because
of both memory and search speed improvements, a contiguous NFA has a smaller
internal limit on the total number of NFA states it can represent. But you
would likely need to have hundreds of thousands or even millions of patterns
before you hit this limit.)
*/
pub mod contiguous;
pub mod noncontiguous;

File diff suppressed because it is too large Load Diff

View File

@@ -1,691 +0,0 @@
use alloc::sync::Arc;
use crate::{
packed::{pattern::Patterns, rabinkarp::RabinKarp, teddy},
util::search::{Match, Span},
};
/// This is a limit placed on the total number of patterns we're willing to try
/// and match at once. As more sophisticated algorithms are added, this number
/// may be increased.
const PATTERN_LIMIT: usize = 128;
/// A knob for controlling the match semantics of a packed multiple string
/// searcher.
///
/// This differs from the [`MatchKind`](crate::MatchKind) type in the top-level
/// crate module in that it doesn't support "standard" match semantics,
/// and instead only supports leftmost-first or leftmost-longest. Namely,
/// "standard" semantics cannot be easily supported by packed searchers.
///
/// For more information on the distinction between leftmost-first and
/// leftmost-longest, see the docs on the top-level `MatchKind` type.
///
/// Unlike the top-level `MatchKind` type, the default match semantics for this
/// type are leftmost-first.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub enum MatchKind {
/// Use leftmost-first match semantics, which reports leftmost matches.
/// When there are multiple possible leftmost matches, the match
/// corresponding to the pattern that appeared earlier when constructing
/// the automaton is reported.
///
/// This is the default.
LeftmostFirst,
/// Use leftmost-longest match semantics, which reports leftmost matches.
/// When there are multiple possible leftmost matches, the longest match
/// is chosen.
LeftmostLongest,
}
impl Default for MatchKind {
fn default() -> MatchKind {
MatchKind::LeftmostFirst
}
}
/// The configuration for a packed multiple pattern searcher.
///
/// The configuration is currently limited only to being able to select the
/// match semantics (leftmost-first or leftmost-longest) of a searcher. In the
/// future, more knobs may be made available.
///
/// A configuration produces a [`packed::Builder`](Builder), which in turn can
/// be used to construct a [`packed::Searcher`](Searcher) for searching.
///
/// # Example
///
/// This example shows how to use leftmost-longest semantics instead of the
/// default (leftmost-first).
///
/// ```
/// use aho_corasick::{packed::{Config, MatchKind}, PatternID};
///
/// # fn example() -> Option<()> {
/// let searcher = Config::new()
/// .match_kind(MatchKind::LeftmostLongest)
/// .builder()
/// .add("foo")
/// .add("foobar")
/// .build()?;
/// let matches: Vec<PatternID> = searcher
/// .find_iter("foobar")
/// .map(|mat| mat.pattern())
/// .collect();
/// assert_eq!(vec![PatternID::must(1)], matches);
/// # Some(()) }
/// # if cfg!(all(feature = "std", any(
/// # target_arch = "x86_64", target_arch = "aarch64",
/// # ))) {
/// # example().unwrap()
/// # } else {
/// # assert!(example().is_none());
/// # }
/// ```
#[derive(Clone, Debug)]
pub struct Config {
kind: MatchKind,
force: Option<ForceAlgorithm>,
only_teddy_fat: Option<bool>,
only_teddy_256bit: Option<bool>,
heuristic_pattern_limits: bool,
}
/// An internal option for forcing the use of a particular packed algorithm.
///
/// When an algorithm is forced, if a searcher could not be constructed for it,
/// then no searcher will be returned even if an alternative algorithm would
/// work.
#[derive(Clone, Debug)]
enum ForceAlgorithm {
Teddy,
RabinKarp,
}
impl Default for Config {
fn default() -> Config {
Config::new()
}
}
impl Config {
/// Create a new default configuration. A default configuration uses
/// leftmost-first match semantics.
pub fn new() -> Config {
Config {
kind: MatchKind::LeftmostFirst,
force: None,
only_teddy_fat: None,
only_teddy_256bit: None,
heuristic_pattern_limits: true,
}
}
/// Create a packed builder from this configuration. The builder can be
/// used to accumulate patterns and create a [`Searcher`] from them.
pub fn builder(&self) -> Builder {
Builder::from_config(self.clone())
}
/// Set the match semantics for this configuration.
pub fn match_kind(&mut self, kind: MatchKind) -> &mut Config {
self.kind = kind;
self
}
/// An undocumented method for forcing the use of the Teddy algorithm.
///
/// This is only exposed for more precise testing and benchmarks. Callers
/// should not use it as it is not part of the API stability guarantees of
/// this crate.
#[doc(hidden)]
pub fn only_teddy(&mut self, yes: bool) -> &mut Config {
if yes {
self.force = Some(ForceAlgorithm::Teddy);
} else {
self.force = None;
}
self
}
/// An undocumented method for forcing the use of the Fat Teddy algorithm.
///
/// This is only exposed for more precise testing and benchmarks. Callers
/// should not use it as it is not part of the API stability guarantees of
/// this crate.
#[doc(hidden)]
pub fn only_teddy_fat(&mut self, yes: Option<bool>) -> &mut Config {
self.only_teddy_fat = yes;
self
}
/// An undocumented method for forcing the use of SSE (`Some(false)`) or
/// AVX (`Some(true)`) algorithms.
///
/// This is only exposed for more precise testing and benchmarks. Callers
/// should not use it as it is not part of the API stability guarantees of
/// this crate.
#[doc(hidden)]
pub fn only_teddy_256bit(&mut self, yes: Option<bool>) -> &mut Config {
self.only_teddy_256bit = yes;
self
}
/// An undocumented method for forcing the use of the Rabin-Karp algorithm.
///
/// This is only exposed for more precise testing and benchmarks. Callers
/// should not use it as it is not part of the API stability guarantees of
/// this crate.
#[doc(hidden)]
pub fn only_rabin_karp(&mut self, yes: bool) -> &mut Config {
if yes {
self.force = Some(ForceAlgorithm::RabinKarp);
} else {
self.force = None;
}
self
}
/// Request that heuristic limitations on the number of patterns be
/// employed. This useful to disable for benchmarking where one wants to
/// explore how Teddy performs on large number of patterns even if the
/// heuristics would otherwise refuse construction.
///
/// This is enabled by default.
pub fn heuristic_pattern_limits(&mut self, yes: bool) -> &mut Config {
self.heuristic_pattern_limits = yes;
self
}
}
/// A builder for constructing a packed searcher from a collection of patterns.
///
/// # Example
///
/// This example shows how to use a builder to construct a searcher. By
/// default, leftmost-first match semantics are used.
///
/// ```
/// use aho_corasick::{packed::{Builder, MatchKind}, PatternID};
///
/// # fn example() -> Option<()> {
/// let searcher = Builder::new()
/// .add("foobar")
/// .add("foo")
/// .build()?;
/// let matches: Vec<PatternID> = searcher
/// .find_iter("foobar")
/// .map(|mat| mat.pattern())
/// .collect();
/// assert_eq!(vec![PatternID::ZERO], matches);
/// # Some(()) }
/// # if cfg!(all(feature = "std", any(
/// # target_arch = "x86_64", target_arch = "aarch64",
/// # ))) {
/// # example().unwrap()
/// # } else {
/// # assert!(example().is_none());
/// # }
/// ```
#[derive(Clone, Debug)]
pub struct Builder {
/// The configuration of this builder and subsequent matcher.
config: Config,
/// Set to true if the builder detects that a matcher cannot be built.
inert: bool,
/// The patterns provided by the caller.
patterns: Patterns,
}
impl Builder {
/// Create a new builder for constructing a multi-pattern searcher. This
/// constructor uses the default configuration.
pub fn new() -> Builder {
Builder::from_config(Config::new())
}
fn from_config(config: Config) -> Builder {
Builder { config, inert: false, patterns: Patterns::new() }
}
/// Build a searcher from the patterns added to this builder so far.
pub fn build(&self) -> Option<Searcher> {
if self.inert || self.patterns.is_empty() {
return None;
}
let mut patterns = self.patterns.clone();
patterns.set_match_kind(self.config.kind);
let patterns = Arc::new(patterns);
let rabinkarp = RabinKarp::new(&patterns);
// Effectively, we only want to return a searcher if we can use Teddy,
// since Teddy is our only fast packed searcher at the moment.
// Rabin-Karp is only used when searching haystacks smaller than what
// Teddy can support. Thus, the only way to get a Rabin-Karp searcher
// is to force it using undocumented APIs (for tests/benchmarks).
let (search_kind, minimum_len) = match self.config.force {
None | Some(ForceAlgorithm::Teddy) => {
debug!("trying to build Teddy packed matcher");
let teddy = match self.build_teddy(Arc::clone(&patterns)) {
None => return None,
Some(teddy) => teddy,
};
let minimum_len = teddy.minimum_len();
(SearchKind::Teddy(teddy), minimum_len)
}
Some(ForceAlgorithm::RabinKarp) => {
debug!("using Rabin-Karp packed matcher");
(SearchKind::RabinKarp, 0)
}
};
Some(Searcher { patterns, rabinkarp, search_kind, minimum_len })
}
fn build_teddy(&self, patterns: Arc<Patterns>) -> Option<teddy::Searcher> {
teddy::Builder::new()
.only_256bit(self.config.only_teddy_256bit)
.only_fat(self.config.only_teddy_fat)
.heuristic_pattern_limits(self.config.heuristic_pattern_limits)
.build(patterns)
}
/// Add the given pattern to this set to match.
///
/// The order in which patterns are added is significant. Namely, when
/// using leftmost-first match semantics, then when multiple patterns can
/// match at a particular location, the pattern that was added first is
/// used as the match.
///
/// If the number of patterns added exceeds the amount supported by packed
/// searchers, then the builder will stop accumulating patterns and render
/// itself inert. At this point, constructing a searcher will always return
/// `None`.
pub fn add<P: AsRef<[u8]>>(&mut self, pattern: P) -> &mut Builder {
if self.inert {
return self;
} else if self.patterns.len() >= PATTERN_LIMIT {
self.inert = true;
self.patterns.reset();
return self;
}
// Just in case PATTERN_LIMIT increases beyond u16::MAX.
assert!(self.patterns.len() <= core::u16::MAX as usize);
let pattern = pattern.as_ref();
if pattern.is_empty() {
self.inert = true;
self.patterns.reset();
return self;
}
self.patterns.add(pattern);
self
}
/// Add the given iterator of patterns to this set to match.
///
/// The iterator must yield elements that can be converted into a `&[u8]`.
///
/// The order in which patterns are added is significant. Namely, when
/// using leftmost-first match semantics, then when multiple patterns can
/// match at a particular location, the pattern that was added first is
/// used as the match.
///
/// If the number of patterns added exceeds the amount supported by packed
/// searchers, then the builder will stop accumulating patterns and render
/// itself inert. At this point, constructing a searcher will always return
/// `None`.
pub fn extend<I, P>(&mut self, patterns: I) -> &mut Builder
where
I: IntoIterator<Item = P>,
P: AsRef<[u8]>,
{
for p in patterns {
self.add(p);
}
self
}
/// Returns the number of patterns added to this builder.
pub fn len(&self) -> usize {
self.patterns.len()
}
/// Returns the length, in bytes, of the shortest pattern added.
pub fn minimum_len(&self) -> usize {
self.patterns.minimum_len()
}
}
impl Default for Builder {
fn default() -> Builder {
Builder::new()
}
}
/// A packed searcher for quickly finding occurrences of multiple patterns.
///
/// If callers need more flexible construction, or if one wants to change the
/// match semantics (either leftmost-first or leftmost-longest), then one can
/// use the [`Config`] and/or [`Builder`] types for more fine grained control.
///
/// # Example
///
/// This example shows how to create a searcher from an iterator of patterns.
/// By default, leftmost-first match semantics are used.
///
/// ```
/// use aho_corasick::{packed::{MatchKind, Searcher}, PatternID};
///
/// # fn example() -> Option<()> {
/// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
/// let matches: Vec<PatternID> = searcher
/// .find_iter("foobar")
/// .map(|mat| mat.pattern())
/// .collect();
/// assert_eq!(vec![PatternID::ZERO], matches);
/// # Some(()) }
/// # if cfg!(all(feature = "std", any(
/// # target_arch = "x86_64", target_arch = "aarch64",
/// # ))) {
/// # example().unwrap()
/// # } else {
/// # assert!(example().is_none());
/// # }
/// ```
#[derive(Clone, Debug)]
pub struct Searcher {
patterns: Arc<Patterns>,
rabinkarp: RabinKarp,
search_kind: SearchKind,
minimum_len: usize,
}
#[derive(Clone, Debug)]
enum SearchKind {
Teddy(teddy::Searcher),
RabinKarp,
}
impl Searcher {
/// A convenience function for constructing a searcher from an iterator
/// of things that can be converted to a `&[u8]`.
///
/// If a searcher could not be constructed (either because of an
/// unsupported CPU or because there are too many patterns), then `None`
/// is returned.
///
/// # Example
///
/// Basic usage:
///
/// ```
/// use aho_corasick::{packed::{MatchKind, Searcher}, PatternID};
///
/// # fn example() -> Option<()> {
/// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
/// let matches: Vec<PatternID> = searcher
/// .find_iter("foobar")
/// .map(|mat| mat.pattern())
/// .collect();
/// assert_eq!(vec![PatternID::ZERO], matches);
/// # Some(()) }
/// # if cfg!(all(feature = "std", any(
/// # target_arch = "x86_64", target_arch = "aarch64",
/// # ))) {
/// # example().unwrap()
/// # } else {
/// # assert!(example().is_none());
/// # }
/// ```
pub fn new<I, P>(patterns: I) -> Option<Searcher>
where
I: IntoIterator<Item = P>,
P: AsRef<[u8]>,
{
Builder::new().extend(patterns).build()
}
/// A convenience function for calling `Config::new()`.
///
/// This is useful for avoiding an additional import.
pub fn config() -> Config {
Config::new()
}
/// A convenience function for calling `Builder::new()`.
///
/// This is useful for avoiding an additional import.
pub fn builder() -> Builder {
Builder::new()
}
/// Return the first occurrence of any of the patterns in this searcher,
/// according to its match semantics, in the given haystack. The `Match`
/// returned will include the identifier of the pattern that matched, which
/// corresponds to the index of the pattern (starting from `0`) in which it
/// was added.
///
/// # Example
///
/// Basic usage:
///
/// ```
/// use aho_corasick::{packed::{MatchKind, Searcher}, PatternID};
///
/// # fn example() -> Option<()> {
/// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
/// let mat = searcher.find("foobar")?;
/// assert_eq!(PatternID::ZERO, mat.pattern());
/// assert_eq!(0, mat.start());
/// assert_eq!(6, mat.end());
/// # Some(()) }
/// # if cfg!(all(feature = "std", any(
/// # target_arch = "x86_64", target_arch = "aarch64",
/// # ))) {
/// # example().unwrap()
/// # } else {
/// # assert!(example().is_none());
/// # }
/// ```
#[inline]
pub fn find<B: AsRef<[u8]>>(&self, haystack: B) -> Option<Match> {
let haystack = haystack.as_ref();
self.find_in(haystack, Span::from(0..haystack.len()))
}
/// Return the first occurrence of any of the patterns in this searcher,
/// according to its match semantics, in the given haystack starting from
/// the given position.
///
/// The `Match` returned will include the identifier of the pattern that
/// matched, which corresponds to the index of the pattern (starting from
/// `0`) in which it was added. The offsets in the `Match` will be relative
/// to the start of `haystack` (and not `at`).
///
/// # Panics
///
/// When `span` does not correspond to a valid range in `haystack`.
///
/// # Example
///
/// Basic usage:
///
/// ```
/// use aho_corasick::{packed::{MatchKind, Searcher}, PatternID, Span};
///
/// # fn example() -> Option<()> {
/// let haystack = "foofoobar";
/// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
/// let mat = searcher.find_in(haystack, Span::from(3..haystack.len()))?;
/// assert_eq!(PatternID::ZERO, mat.pattern());
/// assert_eq!(3, mat.start());
/// assert_eq!(9, mat.end());
/// # Some(()) }
/// # if cfg!(all(feature = "std", any(
/// # target_arch = "x86_64", target_arch = "aarch64",
/// # ))) {
/// # example().unwrap()
/// # } else {
/// # assert!(example().is_none());
/// # }
/// ```
#[inline]
pub fn find_in<B: AsRef<[u8]>>(
&self,
haystack: B,
span: Span,
) -> Option<Match> {
let haystack = haystack.as_ref();
match self.search_kind {
SearchKind::Teddy(ref teddy) => {
if haystack[span].len() < teddy.minimum_len() {
return self.find_in_slow(haystack, span);
}
teddy.find(&haystack[..span.end], span.start)
}
SearchKind::RabinKarp => {
self.rabinkarp.find_at(&haystack[..span.end], span.start)
}
}
}
/// Return an iterator of non-overlapping occurrences of the patterns in
/// this searcher, according to its match semantics, in the given haystack.
///
/// # Example
///
/// Basic usage:
///
/// ```
/// use aho_corasick::{packed::{MatchKind, Searcher}, PatternID};
///
/// # fn example() -> Option<()> {
/// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
/// let matches: Vec<PatternID> = searcher
/// .find_iter("foobar fooba foofoo")
/// .map(|mat| mat.pattern())
/// .collect();
/// assert_eq!(vec![
/// PatternID::must(0),
/// PatternID::must(1),
/// PatternID::must(1),
/// PatternID::must(1),
/// ], matches);
/// # Some(()) }
/// # if cfg!(all(feature = "std", any(
/// # target_arch = "x86_64", target_arch = "aarch64",
/// # ))) {
/// # example().unwrap()
/// # } else {
/// # assert!(example().is_none());
/// # }
/// ```
#[inline]
pub fn find_iter<'a, 'b, B: ?Sized + AsRef<[u8]>>(
&'a self,
haystack: &'b B,
) -> FindIter<'a, 'b> {
let haystack = haystack.as_ref();
let span = Span::from(0..haystack.len());
FindIter { searcher: self, haystack, span }
}
/// Returns the match kind used by this packed searcher.
///
/// # Examples
///
/// Basic usage:
///
/// ```
/// use aho_corasick::packed::{MatchKind, Searcher};
///
/// # fn example() -> Option<()> {
/// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
/// // leftmost-first is the default.
/// assert_eq!(&MatchKind::LeftmostFirst, searcher.match_kind());
/// # Some(()) }
/// # if cfg!(all(feature = "std", any(
/// # target_arch = "x86_64", target_arch = "aarch64",
/// # ))) {
/// # example().unwrap()
/// # } else {
/// # assert!(example().is_none());
/// # }
/// ```
#[inline]
pub fn match_kind(&self) -> &MatchKind {
self.patterns.match_kind()
}
/// Returns the minimum length of a haystack that is required in order for
/// packed searching to be effective.
///
/// In some cases, the underlying packed searcher may not be able to search
/// very short haystacks. When that occurs, the implementation will defer
/// to a slower non-packed searcher (which is still generally faster than
/// Aho-Corasick for a small number of patterns). However, callers may
/// want to avoid ever using the slower variant, which one can do by
/// never passing a haystack shorter than the minimum length returned by
/// this method.
#[inline]
pub fn minimum_len(&self) -> usize {
self.minimum_len
}
/// Returns the approximate total amount of heap used by this searcher, in
/// units of bytes.
#[inline]
pub fn memory_usage(&self) -> usize {
self.patterns.memory_usage()
+ self.rabinkarp.memory_usage()
+ self.search_kind.memory_usage()
}
/// Use a slow (non-packed) searcher.
///
/// This is useful when a packed searcher could be constructed, but could
/// not be used to search a specific haystack. For example, if Teddy was
/// built but the haystack is smaller than ~34 bytes, then Teddy might not
/// be able to run.
fn find_in_slow(&self, haystack: &[u8], span: Span) -> Option<Match> {
self.rabinkarp.find_at(&haystack[..span.end], span.start)
}
}
impl SearchKind {
fn memory_usage(&self) -> usize {
match *self {
SearchKind::Teddy(ref ted) => ted.memory_usage(),
SearchKind::RabinKarp => 0,
}
}
}
/// An iterator over non-overlapping matches from a packed searcher.
///
/// The lifetime `'s` refers to the lifetime of the underlying [`Searcher`],
/// while the lifetime `'h` refers to the lifetime of the haystack being
/// searched.
#[derive(Debug)]
pub struct FindIter<'s, 'h> {
searcher: &'s Searcher,
haystack: &'h [u8],
span: Span,
}
impl<'s, 'h> Iterator for FindIter<'s, 'h> {
type Item = Match;
fn next(&mut self) -> Option<Match> {
if self.span.start > self.span.end {
return None;
}
match self.searcher.find_in(self.haystack, self.span) {
None => None,
Some(m) => {
self.span.start = m.end();
Some(m)
}
}
}
}

View File

@@ -1,39 +0,0 @@
/// A trait for adding some helper routines to pointers.
pub(crate) trait Pointer {
/// Returns the distance, in units of `T`, between `self` and `origin`.
///
/// # Safety
///
/// Same as `ptr::offset_from` in addition to `self >= origin`.
unsafe fn distance(self, origin: Self) -> usize;
/// Casts this pointer to `usize`.
///
/// Callers should not convert the `usize` back to a pointer if at all
/// possible. (And if you believe it's necessary, open an issue to discuss
/// why. Otherwise, it has the potential to violate pointer provenance.)
/// The purpose of this function is just to be able to do arithmetic, i.e.,
/// computing offsets or alignments.
fn as_usize(self) -> usize;
}
impl<T> Pointer for *const T {
unsafe fn distance(self, origin: *const T) -> usize {
// TODO: Replace with `ptr::sub_ptr` once stabilized.
usize::try_from(self.offset_from(origin)).unwrap_unchecked()
}
fn as_usize(self) -> usize {
self as usize
}
}
impl<T> Pointer for *mut T {
unsafe fn distance(self, origin: *mut T) -> usize {
(self as *const T).distance(origin as *const T)
}
fn as_usize(self) -> usize {
(self as *const T).as_usize()
}
}

View File

@@ -1,120 +0,0 @@
/*!
Provides packed multiple substring search, principally for a small number of
patterns.
This sub-module provides vectorized routines for quickly finding
matches of a small number of patterns. In general, users of this crate
shouldn't need to interface with this module directly, as the primary
[`AhoCorasick`](crate::AhoCorasick) searcher will use these routines
automatically as a prefilter when applicable. However, in some cases, callers
may want to bypass the Aho-Corasick machinery entirely and use this vectorized
searcher directly.
# Overview
The primary types in this sub-module are:
* [`Searcher`] executes the actual search algorithm to report matches in a
haystack.
* [`Builder`] accumulates patterns incrementally and can construct a
`Searcher`.
* [`Config`] permits tuning the searcher, and itself will produce a `Builder`
(which can then be used to build a `Searcher`). Currently, the only tuneable
knob are the match semantics, but this may be expanded in the future.
# Examples
This example shows how to create a searcher from an iterator of patterns.
By default, leftmost-first match semantics are used. (See the top-level
[`MatchKind`] type for more details about match semantics, which apply
similarly to packed substring search.)
```
use aho_corasick::{packed::{MatchKind, Searcher}, PatternID};
# fn example() -> Option<()> {
let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
let matches: Vec<PatternID> = searcher
.find_iter("foobar")
.map(|mat| mat.pattern())
.collect();
assert_eq!(vec![PatternID::ZERO], matches);
# Some(()) }
# if cfg!(all(feature = "std", any(
# target_arch = "x86_64", target_arch = "aarch64",
# ))) {
# example().unwrap()
# } else {
# assert!(example().is_none());
# }
```
This example shows how to use [`Config`] to change the match semantics to
leftmost-longest:
```
use aho_corasick::{packed::{Config, MatchKind}, PatternID};
# fn example() -> Option<()> {
let searcher = Config::new()
.match_kind(MatchKind::LeftmostLongest)
.builder()
.add("foo")
.add("foobar")
.build()?;
let matches: Vec<PatternID> = searcher
.find_iter("foobar")
.map(|mat| mat.pattern())
.collect();
assert_eq!(vec![PatternID::must(1)], matches);
# Some(()) }
# if cfg!(all(feature = "std", any(
# target_arch = "x86_64", target_arch = "aarch64",
# ))) {
# example().unwrap()
# } else {
# assert!(example().is_none());
# }
```
# Packed substring searching
Packed substring searching refers to the use of SIMD (Single Instruction,
Multiple Data) to accelerate the detection of matches in a haystack. Unlike
conventional algorithms, such as Aho-Corasick, SIMD algorithms for substring
search tend to do better with a small number of patterns, where as Aho-Corasick
generally maintains reasonably consistent performance regardless of the number
of patterns you give it. Because of this, the vectorized searcher in this
sub-module cannot be used as a general purpose searcher, since building the
searcher may fail even when given a small number of patterns. However, in
exchange, when searching for a small number of patterns, searching can be quite
a bit faster than Aho-Corasick (sometimes by an order of magnitude).
The key take away here is that constructing a searcher from a list of patterns
is a fallible operation with no clear rules for when it will fail. While the
precise conditions under which building a searcher can fail is specifically an
implementation detail, here are some common reasons:
* Too many patterns were given. Typically, the limit is on the order of 100 or
so, but this limit may fluctuate based on available CPU features.
* The available packed algorithms require CPU features that aren't available.
For example, currently, this crate only provides packed algorithms for
`x86_64` and `aarch64`. Therefore, constructing a packed searcher on any
other target will always fail.
* Zero patterns were given, or one of the patterns given was empty. Packed
searchers require at least one pattern and that all patterns are non-empty.
* Something else about the nature of the patterns (typically based on
heuristics) suggests that a packed searcher would perform very poorly, so
no searcher is built.
*/
pub use crate::packed::api::{Builder, Config, FindIter, MatchKind, Searcher};
mod api;
mod ext;
mod pattern;
mod rabinkarp;
mod teddy;
#[cfg(all(feature = "std", test))]
mod tests;
mod vector;

View File

@@ -1,480 +0,0 @@
use core::{cmp, fmt, mem, u16, usize};
use alloc::{boxed::Box, string::String, vec, vec::Vec};
use crate::{
packed::{api::MatchKind, ext::Pointer},
PatternID,
};
/// A non-empty collection of non-empty patterns to search for.
///
/// This collection of patterns is what is passed around to both execute
/// searches and to construct the searchers themselves. Namely, this permits
/// searches to avoid copying all of the patterns, and allows us to keep only
/// one copy throughout all packed searchers.
///
/// Note that this collection is not a set. The same pattern can appear more
/// than once.
#[derive(Clone, Debug)]
pub(crate) struct Patterns {
/// The match semantics supported by this collection of patterns.
///
/// The match semantics determines the order of the iterator over patterns.
/// For leftmost-first, patterns are provided in the same order as were
/// provided by the caller. For leftmost-longest, patterns are provided in
/// descending order of length, with ties broken by the order in which they
/// were provided by the caller.
kind: MatchKind,
/// The collection of patterns, indexed by their identifier.
by_id: Vec<Vec<u8>>,
/// The order of patterns defined for iteration, given by pattern
/// identifiers. The order of `by_id` and `order` is always the same for
/// leftmost-first semantics, but may be different for leftmost-longest
/// semantics.
order: Vec<PatternID>,
/// The length of the smallest pattern, in bytes.
minimum_len: usize,
/// The total number of pattern bytes across the entire collection. This
/// is used for reporting total heap usage in constant time.
total_pattern_bytes: usize,
}
// BREADCRUMBS: I think we want to experiment with a different bucket
// representation. Basically, each bucket is just a Range<usize> to a single
// contiguous allocation? Maybe length-prefixed patterns or something? The
// idea is to try to get rid of the pointer chasing in verification. I don't
// know that that is the issue, but I suspect it is.
impl Patterns {
/// Create a new collection of patterns for the given match semantics. The
/// ID of each pattern is the index of the pattern at which it occurs in
/// the `by_id` slice.
///
/// If any of the patterns in the slice given are empty, then this panics.
/// Similarly, if the number of patterns given is zero, then this also
/// panics.
pub(crate) fn new() -> Patterns {
Patterns {
kind: MatchKind::default(),
by_id: vec![],
order: vec![],
minimum_len: usize::MAX,
total_pattern_bytes: 0,
}
}
/// Add a pattern to this collection.
///
/// This panics if the pattern given is empty.
pub(crate) fn add(&mut self, bytes: &[u8]) {
assert!(!bytes.is_empty());
assert!(self.by_id.len() <= u16::MAX as usize);
let id = PatternID::new(self.by_id.len()).unwrap();
self.order.push(id);
self.by_id.push(bytes.to_vec());
self.minimum_len = cmp::min(self.minimum_len, bytes.len());
self.total_pattern_bytes += bytes.len();
}
/// Set the match kind semantics for this collection of patterns.
///
/// If the kind is not set, then the default is leftmost-first.
pub(crate) fn set_match_kind(&mut self, kind: MatchKind) {
self.kind = kind;
match self.kind {
MatchKind::LeftmostFirst => {
self.order.sort();
}
MatchKind::LeftmostLongest => {
let (order, by_id) = (&mut self.order, &mut self.by_id);
order.sort_by(|&id1, &id2| {
by_id[id1].len().cmp(&by_id[id2].len()).reverse()
});
}
}
}
/// Return the number of patterns in this collection.
///
/// This is guaranteed to be greater than zero.
pub(crate) fn len(&self) -> usize {
self.by_id.len()
}
/// Returns true if and only if this collection of patterns is empty.
pub(crate) fn is_empty(&self) -> bool {
self.len() == 0
}
/// Returns the approximate total amount of heap used by these patterns, in
/// units of bytes.
pub(crate) fn memory_usage(&self) -> usize {
self.order.len() * mem::size_of::<PatternID>()
+ self.by_id.len() * mem::size_of::<Vec<u8>>()
+ self.total_pattern_bytes
}
/// Clears all heap memory associated with this collection of patterns and
/// resets all state such that it is a valid empty collection.
pub(crate) fn reset(&mut self) {
self.kind = MatchKind::default();
self.by_id.clear();
self.order.clear();
self.minimum_len = usize::MAX;
}
/// Returns the length, in bytes, of the smallest pattern.
///
/// This is guaranteed to be at least one.
pub(crate) fn minimum_len(&self) -> usize {
self.minimum_len
}
/// Returns the match semantics used by these patterns.
pub(crate) fn match_kind(&self) -> &MatchKind {
&self.kind
}
/// Return the pattern with the given identifier. If such a pattern does
/// not exist, then this panics.
pub(crate) fn get(&self, id: PatternID) -> Pattern<'_> {
Pattern(&self.by_id[id])
}
/// Return the pattern with the given identifier without performing bounds
/// checks.
///
/// # Safety
///
/// Callers must ensure that a pattern with the given identifier exists
/// before using this method.
pub(crate) unsafe fn get_unchecked(&self, id: PatternID) -> Pattern<'_> {
Pattern(self.by_id.get_unchecked(id.as_usize()))
}
/// Return an iterator over all the patterns in this collection, in the
/// order in which they should be matched.
///
/// Specifically, in a naive multi-pattern matcher, the following is
/// guaranteed to satisfy the match semantics of this collection of
/// patterns:
///
/// ```ignore
/// for i in 0..haystack.len():
/// for p in patterns.iter():
/// if haystack[i..].starts_with(p.bytes()):
/// return Match(p.id(), i, i + p.bytes().len())
/// ```
///
/// Namely, among the patterns in a collection, if they are matched in
/// the order provided by this iterator, then the result is guaranteed
/// to satisfy the correct match semantics. (Either leftmost-first or
/// leftmost-longest.)
pub(crate) fn iter(&self) -> PatternIter<'_> {
PatternIter { patterns: self, i: 0 }
}
}
/// An iterator over the patterns in the `Patterns` collection.
///
/// The order of the patterns provided by this iterator is consistent with the
/// match semantics of the originating collection of patterns.
///
/// The lifetime `'p` corresponds to the lifetime of the collection of patterns
/// this is iterating over.
#[derive(Debug)]
pub(crate) struct PatternIter<'p> {
patterns: &'p Patterns,
i: usize,
}
impl<'p> Iterator for PatternIter<'p> {
type Item = (PatternID, Pattern<'p>);
fn next(&mut self) -> Option<(PatternID, Pattern<'p>)> {
if self.i >= self.patterns.len() {
return None;
}
let id = self.patterns.order[self.i];
let p = self.patterns.get(id);
self.i += 1;
Some((id, p))
}
}
/// A pattern that is used in packed searching.
#[derive(Clone)]
pub(crate) struct Pattern<'a>(&'a [u8]);
impl<'a> fmt::Debug for Pattern<'a> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("Pattern")
.field("lit", &String::from_utf8_lossy(self.0))
.finish()
}
}
impl<'p> Pattern<'p> {
/// Returns the length of this pattern, in bytes.
pub(crate) fn len(&self) -> usize {
self.0.len()
}
/// Returns the bytes of this pattern.
pub(crate) fn bytes(&self) -> &[u8] {
self.0
}
/// Returns the first `len` low nybbles from this pattern. If this pattern
/// is shorter than `len`, then this panics.
pub(crate) fn low_nybbles(&self, len: usize) -> Box<[u8]> {
let mut nybs = vec![0; len].into_boxed_slice();
for (i, byte) in self.bytes().iter().take(len).enumerate() {
nybs[i] = byte & 0xF;
}
nybs
}
/// Returns true if this pattern is a prefix of the given bytes.
#[inline(always)]
pub(crate) fn is_prefix(&self, bytes: &[u8]) -> bool {
is_prefix(bytes, self.bytes())
}
/// Returns true if this pattern is a prefix of the haystack given by the
/// raw `start` and `end` pointers.
///
/// # Safety
///
/// * It must be the case that `start < end` and that the distance between
/// them is at least equal to `V::BYTES`. That is, it must always be valid
/// to do at least an unaligned load of `V` at `start`.
/// * Both `start` and `end` must be valid for reads.
/// * Both `start` and `end` must point to an initialized value.
/// * Both `start` and `end` must point to the same allocated object and
/// must either be in bounds or at most one byte past the end of the
/// allocated object.
/// * Both `start` and `end` must be _derived from_ a pointer to the same
/// object.
/// * The distance between `start` and `end` must not overflow `isize`.
/// * The distance being in bounds must not rely on "wrapping around" the
/// address space.
#[inline(always)]
pub(crate) unsafe fn is_prefix_raw(
&self,
start: *const u8,
end: *const u8,
) -> bool {
let patlen = self.bytes().len();
let haylen = end.distance(start);
if patlen > haylen {
return false;
}
// SAFETY: We've checked that the haystack has length at least equal
// to this pattern. All other safety concerns are the responsibility
// of the caller.
is_equal_raw(start, self.bytes().as_ptr(), patlen)
}
}
/// Returns true if and only if `needle` is a prefix of `haystack`.
///
/// This uses a latency optimized variant of `memcmp` internally which *might*
/// make this faster for very short strings.
///
/// # Inlining
///
/// This routine is marked `inline(always)`. If you want to call this function
/// in a way that is not always inlined, you'll need to wrap a call to it in
/// another function that is marked as `inline(never)` or just `inline`.
#[inline(always)]
fn is_prefix(haystack: &[u8], needle: &[u8]) -> bool {
if needle.len() > haystack.len() {
return false;
}
// SAFETY: Our pointers are derived directly from borrowed slices which
// uphold all of our safety guarantees except for length. We account for
// length with the check above.
unsafe { is_equal_raw(haystack.as_ptr(), needle.as_ptr(), needle.len()) }
}
/// Compare corresponding bytes in `x` and `y` for equality.
///
/// That is, this returns true if and only if `x.len() == y.len()` and
/// `x[i] == y[i]` for all `0 <= i < x.len()`.
///
/// Note that this isn't used. We only use it in tests as a convenient way
/// of testing `is_equal_raw`.
///
/// # Inlining
///
/// This routine is marked `inline(always)`. If you want to call this function
/// in a way that is not always inlined, you'll need to wrap a call to it in
/// another function that is marked as `inline(never)` or just `inline`.
///
/// # Motivation
///
/// Why not use slice equality instead? Well, slice equality usually results in
/// a call out to the current platform's `libc` which might not be inlineable
/// or have other overhead. This routine isn't guaranteed to be a win, but it
/// might be in some cases.
#[cfg(test)]
#[inline(always)]
fn is_equal(x: &[u8], y: &[u8]) -> bool {
if x.len() != y.len() {
return false;
}
// SAFETY: Our pointers are derived directly from borrowed slices which
// uphold all of our safety guarantees except for length. We account for
// length with the check above.
unsafe { is_equal_raw(x.as_ptr(), y.as_ptr(), x.len()) }
}
/// Compare `n` bytes at the given pointers for equality.
///
/// This returns true if and only if `*x.add(i) == *y.add(i)` for all
/// `0 <= i < n`.
///
/// # Inlining
///
/// This routine is marked `inline(always)`. If you want to call this function
/// in a way that is not always inlined, you'll need to wrap a call to it in
/// another function that is marked as `inline(never)` or just `inline`.
///
/// # Motivation
///
/// Why not use slice equality instead? Well, slice equality usually results in
/// a call out to the current platform's `libc` which might not be inlineable
/// or have other overhead. This routine isn't guaranteed to be a win, but it
/// might be in some cases.
///
/// # Safety
///
/// * Both `x` and `y` must be valid for reads of up to `n` bytes.
/// * Both `x` and `y` must point to an initialized value.
/// * Both `x` and `y` must each point to an allocated object and
/// must either be in bounds or at most one byte past the end of the
/// allocated object. `x` and `y` do not need to point to the same allocated
/// object, but they may.
/// * Both `x` and `y` must be _derived from_ a pointer to their respective
/// allocated objects.
/// * The distance between `x` and `x+n` must not overflow `isize`. Similarly
/// for `y` and `y+n`.
/// * The distance being in bounds must not rely on "wrapping around" the
/// address space.
#[inline(always)]
unsafe fn is_equal_raw(mut x: *const u8, mut y: *const u8, n: usize) -> bool {
// If we don't have enough bytes to do 4-byte at a time loads, then
// handle each possible length specially. Note that I used to have a
// byte-at-a-time loop here and that turned out to be quite a bit slower
// for the memmem/pathological/defeat-simple-vector-alphabet benchmark.
if n < 4 {
return match n {
0 => true,
1 => x.read() == y.read(),
2 => {
x.cast::<u16>().read_unaligned()
== y.cast::<u16>().read_unaligned()
}
// I also tried copy_nonoverlapping here and it looks like the
// codegen is the same.
3 => x.cast::<[u8; 3]>().read() == y.cast::<[u8; 3]>().read(),
_ => unreachable!(),
};
}
// When we have 4 or more bytes to compare, then proceed in chunks of 4 at
// a time using unaligned loads.
//
// Also, why do 4 byte loads instead of, say, 8 byte loads? The reason is
// that this particular version of memcmp is likely to be called with tiny
// needles. That means that if we do 8 byte loads, then a higher proportion
// of memcmp calls will use the slower variant above. With that said, this
// is a hypothesis and is only loosely supported by benchmarks. There's
// likely some improvement that could be made here. The main thing here
// though is to optimize for latency, not throughput.
// SAFETY: The caller is responsible for ensuring the pointers we get are
// valid and readable for at least `n` bytes. We also do unaligned loads,
// so there's no need to ensure we're aligned. (This is justified by this
// routine being specifically for short strings.)
let xend = x.add(n.wrapping_sub(4));
let yend = y.add(n.wrapping_sub(4));
while x < xend {
let vx = x.cast::<u32>().read_unaligned();
let vy = y.cast::<u32>().read_unaligned();
if vx != vy {
return false;
}
x = x.add(4);
y = y.add(4);
}
let vx = xend.cast::<u32>().read_unaligned();
let vy = yend.cast::<u32>().read_unaligned();
vx == vy
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn equals_different_lengths() {
assert!(!is_equal(b"", b"a"));
assert!(!is_equal(b"a", b""));
assert!(!is_equal(b"ab", b"a"));
assert!(!is_equal(b"a", b"ab"));
}
#[test]
fn equals_mismatch() {
let one_mismatch = [
(&b"a"[..], &b"x"[..]),
(&b"ab"[..], &b"ax"[..]),
(&b"abc"[..], &b"abx"[..]),
(&b"abcd"[..], &b"abcx"[..]),
(&b"abcde"[..], &b"abcdx"[..]),
(&b"abcdef"[..], &b"abcdex"[..]),
(&b"abcdefg"[..], &b"abcdefx"[..]),
(&b"abcdefgh"[..], &b"abcdefgx"[..]),
(&b"abcdefghi"[..], &b"abcdefghx"[..]),
(&b"abcdefghij"[..], &b"abcdefghix"[..]),
(&b"abcdefghijk"[..], &b"abcdefghijx"[..]),
(&b"abcdefghijkl"[..], &b"abcdefghijkx"[..]),
(&b"abcdefghijklm"[..], &b"abcdefghijklx"[..]),
(&b"abcdefghijklmn"[..], &b"abcdefghijklmx"[..]),
];
for (x, y) in one_mismatch {
assert_eq!(x.len(), y.len(), "lengths should match");
assert!(!is_equal(x, y));
assert!(!is_equal(y, x));
}
}
#[test]
fn equals_yes() {
assert!(is_equal(b"", b""));
assert!(is_equal(b"a", b"a"));
assert!(is_equal(b"ab", b"ab"));
assert!(is_equal(b"abc", b"abc"));
assert!(is_equal(b"abcd", b"abcd"));
assert!(is_equal(b"abcde", b"abcde"));
assert!(is_equal(b"abcdef", b"abcdef"));
assert!(is_equal(b"abcdefg", b"abcdefg"));
assert!(is_equal(b"abcdefgh", b"abcdefgh"));
assert!(is_equal(b"abcdefghi", b"abcdefghi"));
}
#[test]
fn prefix() {
assert!(is_prefix(b"", b""));
assert!(is_prefix(b"a", b""));
assert!(is_prefix(b"ab", b""));
assert!(is_prefix(b"foo", b"foo"));
assert!(is_prefix(b"foobar", b"foo"));
assert!(!is_prefix(b"foo", b"fob"));
assert!(!is_prefix(b"foobar", b"fob"));
}
}

View File

@@ -1,168 +0,0 @@
use alloc::{sync::Arc, vec, vec::Vec};
use crate::{packed::pattern::Patterns, util::search::Match, PatternID};
/// The type of the rolling hash used in the Rabin-Karp algorithm.
type Hash = usize;
/// The number of buckets to store our patterns in. We don't want this to be
/// too big in order to avoid wasting memory, but we don't want it to be too
/// small either to avoid spending too much time confirming literals.
///
/// The number of buckets MUST be a power of two. Otherwise, determining the
/// bucket from a hash will slow down the code considerably. Using a power
/// of two means `hash % NUM_BUCKETS` can compile down to a simple `and`
/// instruction.
const NUM_BUCKETS: usize = 64;
/// An implementation of the Rabin-Karp algorithm. The main idea of this
/// algorithm is to maintain a rolling hash as it moves through the input, and
/// then check whether that hash corresponds to the same hash for any of the
/// patterns we're looking for.
///
/// A draw back of naively scaling Rabin-Karp to multiple patterns is that
/// it requires all of the patterns to be the same length, which in turn
/// corresponds to the number of bytes to hash. We adapt this to work for
/// multiple patterns of varying size by fixing the number of bytes to hash
/// to be the length of the smallest pattern. We also split the patterns into
/// several buckets to hopefully make the confirmation step faster.
///
/// Wikipedia has a decent explanation, if a bit heavy on the theory:
/// https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
///
/// But ESMAJ provides something a bit more concrete:
/// https://www-igm.univ-mlv.fr/~lecroq/string/node5.html
#[derive(Clone, Debug)]
pub(crate) struct RabinKarp {
/// The patterns we're searching for.
patterns: Arc<Patterns>,
/// The order of patterns in each bucket is significant. Namely, they are
/// arranged such that the first one to match is the correct match. This
/// may not necessarily correspond to the order provided by the caller.
/// For example, if leftmost-longest semantics are used, then the patterns
/// are sorted by their length in descending order. If leftmost-first
/// semantics are used, then the patterns are sorted by their pattern ID
/// in ascending order (which corresponds to the caller's order).
buckets: Vec<Vec<(Hash, PatternID)>>,
/// The length of the hashing window. Generally, this corresponds to the
/// length of the smallest pattern.
hash_len: usize,
/// The factor to subtract out of a hash before updating it with a new
/// byte.
hash_2pow: usize,
}
impl RabinKarp {
/// Compile a new Rabin-Karp matcher from the patterns given.
///
/// This panics if any of the patterns in the collection are empty, or if
/// the collection is itself empty.
pub(crate) fn new(patterns: &Arc<Patterns>) -> RabinKarp {
assert!(patterns.len() >= 1);
let hash_len = patterns.minimum_len();
assert!(hash_len >= 1);
let mut hash_2pow = 1usize;
for _ in 1..hash_len {
hash_2pow = hash_2pow.wrapping_shl(1);
}
let mut rk = RabinKarp {
patterns: Arc::clone(patterns),
buckets: vec![vec![]; NUM_BUCKETS],
hash_len,
hash_2pow,
};
for (id, pat) in patterns.iter() {
let hash = rk.hash(&pat.bytes()[..rk.hash_len]);
let bucket = hash % NUM_BUCKETS;
rk.buckets[bucket].push((hash, id));
}
rk
}
/// Return the first matching pattern in the given haystack, begining the
/// search at `at`.
pub(crate) fn find_at(
&self,
haystack: &[u8],
mut at: usize,
) -> Option<Match> {
assert_eq!(NUM_BUCKETS, self.buckets.len());
if at + self.hash_len > haystack.len() {
return None;
}
let mut hash = self.hash(&haystack[at..at + self.hash_len]);
loop {
let bucket = &self.buckets[hash % NUM_BUCKETS];
for &(phash, pid) in bucket {
if phash == hash {
if let Some(c) = self.verify(pid, haystack, at) {
return Some(c);
}
}
}
if at + self.hash_len >= haystack.len() {
return None;
}
hash = self.update_hash(
hash,
haystack[at],
haystack[at + self.hash_len],
);
at += 1;
}
}
/// Returns the approximate total amount of heap used by this searcher, in
/// units of bytes.
pub(crate) fn memory_usage(&self) -> usize {
self.buckets.len() * core::mem::size_of::<Vec<(Hash, PatternID)>>()
+ self.patterns.len() * core::mem::size_of::<(Hash, PatternID)>()
}
/// Verify whether the pattern with the given id matches at
/// `haystack[at..]`.
///
/// We tag this function as `cold` because it helps improve codegen.
/// Intuitively, it would seem like inlining it would be better. However,
/// the only time this is called and a match is not found is when there
/// there is a hash collision, or when a prefix of a pattern matches but
/// the entire pattern doesn't match. This is hopefully fairly rare, and
/// if it does occur a lot, it's going to be slow no matter what we do.
#[cold]
fn verify(
&self,
id: PatternID,
haystack: &[u8],
at: usize,
) -> Option<Match> {
let pat = self.patterns.get(id);
if pat.is_prefix(&haystack[at..]) {
Some(Match::new(id, at..at + pat.len()))
} else {
None
}
}
/// Hash the given bytes.
fn hash(&self, bytes: &[u8]) -> Hash {
assert_eq!(self.hash_len, bytes.len());
let mut hash = 0usize;
for &b in bytes {
hash = hash.wrapping_shl(1).wrapping_add(b as usize);
}
hash
}
/// Update the hash given based on removing `old_byte` at the beginning
/// of some byte string, and appending `new_byte` to the end of that same
/// byte string.
fn update_hash(&self, prev: Hash, old_byte: u8, new_byte: u8) -> Hash {
prev.wrapping_sub((old_byte as usize).wrapping_mul(self.hash_2pow))
.wrapping_shl(1)
.wrapping_add(new_byte as usize)
}
}

View File

@@ -1,386 +0,0 @@
Teddy is a SIMD accelerated multiple substring matching algorithm. The name
and the core ideas in the algorithm were learned from the [Hyperscan][1_u]
project. The implementation in this repository was mostly motivated for use in
accelerating regex searches by searching for small sets of required literals
extracted from the regex.
# Background
The key idea of Teddy is to do *packed* substring matching. In the literature,
packed substring matching is the idea of examining multiple bytes in a haystack
at a time to detect matches. Implementations of, for example, memchr (which
detects matches of a single byte) have been doing this for years. Only
recently, with the introduction of various SIMD instructions, has this been
extended to substring matching. The PCMPESTRI instruction (and its relatives),
for example, implements substring matching in hardware. It is, however, limited
to substrings of length 16 bytes or fewer, but this restriction is fine in a
regex engine, since we rarely care about the performance difference between
searching for a 16 byte literal and a 16 + N literal; 16 is already long
enough. The key downside of the PCMPESTRI instruction, on current (2016) CPUs
at least, is its latency and throughput. As a result, it is often faster to
do substring search with a Boyer-Moore (or Two-Way) variant and a well placed
memchr to quickly skip through the haystack.
There are fewer results from the literature on packed substring matching,
and even fewer for packed multiple substring matching. Ben-Kiki et al. [2]
describes use of PCMPESTRI for substring matching, but is mostly theoretical
and hand-waves performance. There is other theoretical work done by Bille [3]
as well.
The rest of the work in the field, as far as I'm aware, is by Faro and Kulekci
and is generally focused on multiple pattern search. Their first paper [4a]
introduces the concept of a fingerprint, which is computed for every block of
N bytes in every pattern. The haystack is then scanned N bytes at a time and
a fingerprint is computed in the same way it was computed for blocks in the
patterns. If the fingerprint corresponds to one that was found in a pattern,
then a verification step follows to confirm that one of the substrings with the
corresponding fingerprint actually matches at the current location. Various
implementation tricks are employed to make sure the fingerprint lookup is fast;
typically by truncating the fingerprint. (This may, of course, provoke more
steps in the verification process, so a balance must be struck.)
The main downside of [4a] is that the minimum substring length is 32 bytes,
presumably because of how the algorithm uses certain SIMD instructions. This
essentially makes it useless for general purpose regex matching, where a small
number of short patterns is far more likely.
Faro and Kulekci published another paper [4b] that is conceptually very similar
to [4a]. The key difference is that it uses the CRC32 instruction (introduced
as part of SSE 4.2) to compute fingerprint values. This also enables the
algorithm to work effectively on substrings as short as 7 bytes with 4 byte
windows. 7 bytes is unfortunately still too long. The window could be
technically shrunk to 2 bytes, thereby reducing minimum length to 3, but the
small window size ends up negating most performance benefits—and it's likely
the common case in a general purpose regex engine.
Faro and Kulekci also published [4c] that appears to be intended as a
replacement to using PCMPESTRI. In particular, it is specifically motivated by
the high throughput/latency time of PCMPESTRI and therefore chooses other SIMD
instructions that are faster. While this approach works for short substrings,
I personally couldn't see a way to generalize it to multiple substring search.
Faro and Kulekci have another paper [4d] that I haven't been able to read
because it is behind a paywall.
# Teddy
Finally, we get to Teddy. If the above literature review is complete, then it
appears that Teddy is a novel algorithm. More than that, in my experience, it
completely blows away the competition for short substrings, which is exactly
what we want in a general purpose regex engine. Again, the algorithm appears
to be developed by the authors of [Hyperscan][1_u]. Hyperscan was open sourced
late 2015, and no earlier history could be found. Therefore, tracking the exact
provenance of the algorithm with respect to the published literature seems
difficult.
At a high level, Teddy works somewhat similarly to the fingerprint algorithms
published by Faro and Kulekci, but Teddy does it in a way that scales a bit
better. Namely:
1. Teddy's core algorithm scans the haystack in 16 (for SSE, or 32 for AVX)
byte chunks. 16 (or 32) is significant because it corresponds to the number
of bytes in a SIMD vector.
2. Bitwise operations are performed on each chunk to discover if any region of
it matches a set of precomputed fingerprints from the patterns. If there are
matches, then a verification step is performed. In this implementation, our
verification step is naive. This can be improved upon.
The details to make this work are quite clever. First, we must choose how to
pick our fingerprints. In Hyperscan's implementation, I *believe* they use the
last N bytes of each substring, where N must be at least the minimum length of
any substring in the set being searched. In this implementation, we use the
first N bytes of each substring. (The tradeoffs between these choices aren't
yet clear to me.) We then must figure out how to quickly test whether an
occurrence of any fingerprint from the set of patterns appears in a 16 byte
block from the haystack. To keep things simple, let's assume N = 1 and examine
some examples to motivate the approach. Here are our patterns:
```ignore
foo
bar
baz
```
The corresponding fingerprints, for N = 1, are `f`, `b` and `b`. Now let's set
our 16 byte block to:
```ignore
bat cat foo bump
xxxxxxxxxxxxxxxx
```
To cut to the chase, Teddy works by using bitsets. In particular, Teddy creates
a mask that allows us to quickly compute membership of a fingerprint in a 16
byte block that also tells which pattern the fingerprint corresponds to. In
this case, our fingerprint is a single byte, so an appropriate abstraction is
a map from a single byte to a list of patterns that contain that fingerprint:
```ignore
f |--> foo
b |--> bar, baz
```
Now, all we need to do is figure out how to represent this map in vector space
and use normal SIMD operations to perform a lookup. The first simplification
we can make is to represent our patterns as bit fields occupying a single
byte. This is important, because a single SIMD vector can store 16 bytes.
```ignore
f |--> 00000001
b |--> 00000010, 00000100
```
How do we perform lookup though? It turns out that SSSE3 introduced a very cool
instruction called PSHUFB. The instruction takes two SIMD vectors, `A` and `B`,
and returns a third vector `C`. All vectors are treated as 16 8-bit integers.
`C` is formed by `C[i] = A[B[i]]`. (This is a bit of a simplification, but true
for the purposes of this algorithm. For full details, see [Intel's Intrinsics
Guide][5_u].) This essentially lets us use the values in `B` to lookup values
in `A`.
If we could somehow cause `B` to contain our 16 byte block from the haystack,
and if `A` could contain our bitmasks, then we'd end up with something like
this for `A`:
```ignore
0x00 0x01 ... 0x62 ... 0x66 ... 0xFF
A = 0 0 00000110 00000001 0
```
And if `B` contains our window from our haystack, we could use shuffle to take
the values from `B` and use them to look up our bitsets in `A`. But of course,
we can't do this because `A` in the above example contains 256 bytes, which
is much larger than the size of a SIMD vector.
Nybbles to the rescue! A nybble is 4 bits. Instead of one mask to hold all of
our bitsets, we can use two masks, where one mask corresponds to the lower four
bits of our fingerprint and the other mask corresponds to the upper four bits.
So our map now looks like:
```ignore
'f' & 0xF = 0x6 |--> 00000001
'f' >> 4 = 0x6 |--> 00000111
'b' & 0xF = 0x2 |--> 00000110
'b' >> 4 = 0x6 |--> 00000111
```
Notice that the bitsets for each nybble correspond to the union of all
fingerprints that contain that nybble. For example, both `f` and `b` have the
same upper 4 bits but differ on the lower 4 bits. Putting this together, we
have `A0`, `A1` and `B`, where `A0` is our mask for the lower nybble, `A1` is
our mask for the upper nybble and `B` is our 16 byte block from the haystack:
```ignore
0x00 0x01 0x02 0x03 ... 0x06 ... 0xF
A0 = 0 0 00000110 0 00000001 0
A1 = 0 0 0 0 00000111 0
B = b a t _ t p
B = 0x62 0x61 0x74 0x20 0x74 0x70
```
But of course, we can't use `B` with `PSHUFB` yet, since its values are 8 bits,
and we need indexes that are at most 4 bits (corresponding to one of 16
values). We can apply the same transformation to split `B` into lower and upper
nybbles as we did `A`. As before, `B0` corresponds to the lower nybbles and
`B1` corresponds to the upper nybbles:
```ignore
b a t _ c a t _ f o o _ b u m p
B0 = 0x2 0x1 0x4 0x0 0x3 0x1 0x4 0x0 0x6 0xF 0xF 0x0 0x2 0x5 0xD 0x0
B1 = 0x6 0x6 0x7 0x2 0x6 0x6 0x7 0x2 0x6 0x6 0x6 0x2 0x6 0x7 0x6 0x7
```
And now we have a nice correspondence. `B0` can index `A0` and `B1` can index
`A1`. Here's what we get when we apply `C0 = PSHUFB(A0, B0)`:
```ignore
b a ... f o ... p
A0[0x2] A0[0x1] A0[0x6] A0[0xF] A0[0x0]
C0 = 00000110 0 00000001 0 0
```
And `C1 = PSHUFB(A1, B1)`:
```ignore
b a ... f o ... p
A1[0x6] A1[0x6] A1[0x6] A1[0x6] A1[0x7]
C1 = 00000111 00000111 00000111 00000111 0
```
Notice how neither one of `C0` or `C1` is guaranteed to report fully correct
results all on its own. For example, `C1` claims that `b` is a fingerprint for
the pattern `foo` (since `A1[0x6] = 00000111`), and that `o` is a fingerprint
for all of our patterns. But if we combined `C0` and `C1` with an `AND`
operation:
```ignore
b a ... f o ... p
C = 00000110 0 00000001 0 0
```
Then we now have that `C[i]` contains a bitset corresponding to the matching
fingerprints in a haystack's 16 byte block, where `i` is the `ith` byte in that
block.
Once we have that, we can look for the position of the least significant bit
in `C`. (Least significant because we only target little endian here. Thus,
the least significant bytes correspond to bytes in our haystack at a lower
address.) That position, modulo `8`, gives us the pattern that the fingerprint
matches. That position, integer divided by `8`, also gives us the byte offset
that the fingerprint occurs in inside the 16 byte haystack block. Using those
two pieces of information, we can run a verification procedure that tries
to match all substrings containing that fingerprint at that position in the
haystack.
# Implementation notes
The problem with the algorithm as described above is that it uses a single byte
for a fingerprint. This will work well if the fingerprints are rare in the
haystack (e.g., capital letters or special characters in normal English text),
but if the fingerprints are common, you'll wind up spending too much time in
the verification step, which effectively negates the performance benefits of
scanning 16 bytes at a time. Remember, the key to the performance of this
algorithm is to do as little work as possible per 16 (or 32) bytes.
This algorithm can be extrapolated in a relatively straight-forward way to use
larger fingerprints. That is, instead of a single byte prefix, we might use a
two or three byte prefix. The implementation here implements N = {1, 2, 3}
and always picks the largest N possible. The rationale is that the bigger the
fingerprint, the fewer verification steps we'll do. Of course, if N is too
large, then we'll end up doing too much on each step.
The way to extend it is:
1. Add a mask for each byte in the fingerprint. (Remember that each mask is
composed of two SIMD vectors.) This results in a value of `C` for each byte
in the fingerprint while searching.
2. When testing each 16 (or 32) byte block, each value of `C` must be shifted
so that they are aligned. Once aligned, they should all be `AND`'d together.
This will give you only the bitsets corresponding to the full match of the
fingerprint. To do this, one needs to save the last byte (for N=2) or last
two bytes (for N=3) from the previous iteration, and then line them up with
the first one or two bytes of the next iteration.
## Verification
Verification generally follows the procedure outlined above. The tricky parts
are in the right formulation of operations to get our bits out of our vectors.
We have a limited set of operations available to us on SIMD vectors as 128-bit
or 256-bit numbers, so we wind up needing to rip out 2 (or 4) 64-bit integers
from our vectors, and then run our verification step on each of those. The
verification step looks at the least significant bit set, and from its
position, we can derive the byte offset and bucket. (Again, as described
above.) Once we know the bucket, we do a fairly naive exhaustive search for
every literal in that bucket. (Hyperscan is a bit smarter here and uses a hash
table, but I haven't had time to thoroughly explore that. A few initial
half-hearted attempts resulted in worse performance.)
## AVX
The AVX version of Teddy extrapolates almost perfectly from the SSE version.
The only hickup is that PALIGNR is used to align chunks in the 16-bit version,
and there is no equivalent instruction in AVX. AVX does have VPALIGNR, but it
only works within 128-bit lanes. So there's a bit of tomfoolery to get around
this by shuffling the vectors before calling VPALIGNR.
The only other aspect to AVX is that since our masks are still fundamentally
16-bytes (0x0-0xF), they are duplicated to 32-bytes, so that they can apply to
32-byte chunks.
## Fat Teddy
In the version of Teddy described above, 8 buckets are used to group patterns
that we want to search for. However, when AVX is available, we can extend the
number of buckets to 16 by permitting each byte in our masks to use 16-bits
instead of 8-bits to represent the buckets it belongs to. (This variant is also
in Hyperscan.) However, what we give up is the ability to scan 32 bytes at a
time, even though we're using AVX. Instead, we have to scan 16 bytes at a time.
What we gain, though, is (hopefully) less work in our verification routine.
It patterns are more spread out across more buckets, then there should overall
be fewer false positives. In general, Fat Teddy permits us to grow our capacity
a bit and search for more literals before Teddy gets overwhelmed.
The tricky part of Fat Teddy is in how we adjust our masks and our verification
procedure. For the masks, we simply represent the first 8 buckets in each of
the low 16 bytes, and then the second 8 buckets in each of the high 16 bytes.
Then, in the search loop, instead of loading 32 bytes from the haystack, we
load the same 16 bytes from the haystack into both the low and high 16 byte
portions of our 256-bit vector. So for example, a mask might look like this:
bits: 00100001 00000000 ... 11000000 00000000 00000001 ... 00000000
byte: 31 30 16 15 14 0
offset: 15 14 0 15 14 0
buckets: 8-15 8-15 8-15 0-7 0-7 0-7
Where `byte` is the position in the vector (higher numbers corresponding to
more significant bits), `offset` is the corresponding position in the haystack
chunk, and `buckets` corresponds to the bucket assignments for that particular
byte.
In particular, notice that the bucket assignments for offset `0` are spread
out between bytes `0` and `16`. This works well for the chunk-by-chunk search
procedure, but verification really wants to process all bucket assignments for
each offset at once. Otherwise, we might wind up finding a match at offset
`1` in one the first 8 buckets, when we really should have reported a match
at offset `0` in one of the second 8 buckets. (Because we want the leftmost
match.)
Thus, for verification, we rearrange the above vector such that it is a
sequence of 16-bit integers, where the least significant 16-bit integer
corresponds to all of the bucket assignments for offset `0`. So with the
above vector, the least significant 16-bit integer would be
11000000 000000
which was taken from bytes `16` and `0`. Then the verification step pretty much
runs as described, except with 16 buckets instead of 8.
# References
- **[1]** [Hyperscan on GitHub](https://github.com/intel/hyperscan),
[webpage](https://www.hyperscan.io/)
- **[2a]** Ben-Kiki, O., Bille, P., Breslauer, D., Gasieniec, L., Grossi, R.,
& Weimann, O. (2011).
_Optimal packed string matching_.
In LIPIcs-Leibniz International Proceedings in Informatics (Vol. 13).
Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
DOI: 10.4230/LIPIcs.FSTTCS.2011.423.
[PDF](https://drops.dagstuhl.de/opus/volltexte/2011/3355/pdf/37.pdf).
- **[2b]** Ben-Kiki, O., Bille, P., Breslauer, D., Ga̧sieniec, L., Grossi, R.,
& Weimann, O. (2014).
_Towards optimal packed string matching_.
Theoretical Computer Science, 525, 111-129.
DOI: 10.1016/j.tcs.2013.06.013.
[PDF](https://www.cs.haifa.ac.il/~oren/Publications/bpsm.pdf).
- **[3]** Bille, P. (2011).
_Fast searching in packed strings_.
Journal of Discrete Algorithms, 9(1), 49-56.
DOI: 10.1016/j.jda.2010.09.003.
[PDF](https://www.sciencedirect.com/science/article/pii/S1570866710000353).
- **[4a]** Faro, S., & Külekci, M. O. (2012, October).
_Fast multiple string matching using streaming SIMD extensions technology_.
In String Processing and Information Retrieval (pp. 217-228).
Springer Berlin Heidelberg.
DOI: 10.1007/978-3-642-34109-0_23.
[PDF](https://www.dmi.unict.it/faro/papers/conference/faro32.pdf).
- **[4b]** Faro, S., & Külekci, M. O. (2013, September).
_Towards a Very Fast Multiple String Matching Algorithm for Short Patterns_.
In Stringology (pp. 78-91).
[PDF](https://www.dmi.unict.it/faro/papers/conference/faro36.pdf).
- **[4c]** Faro, S., & Külekci, M. O. (2013, January).
_Fast packed string matching for short patterns_.
In Proceedings of the Meeting on Algorithm Engineering & Expermiments
(pp. 113-121).
Society for Industrial and Applied Mathematics.
[PDF](https://arxiv.org/pdf/1209.6449.pdf).
- **[4d]** Faro, S., & Külekci, M. O. (2014).
_Fast and flexible packed string matching_.
Journal of Discrete Algorithms, 28, 61-72.
DOI: 10.1016/j.jda.2014.07.003.
[1_u]: https://github.com/intel/hyperscan
[5_u]: https://software.intel.com/sites/landingpage/IntrinsicsGuide

View File

@@ -1,792 +0,0 @@
use core::{
fmt::Debug,
panic::{RefUnwindSafe, UnwindSafe},
};
use alloc::sync::Arc;
use crate::packed::{ext::Pointer, pattern::Patterns, teddy::generic::Match};
/// A builder for constructing a Teddy matcher.
///
/// The builder primarily permits fine grained configuration of the Teddy
/// matcher. Most options are made only available for testing/benchmarking
/// purposes. In reality, options are automatically determined by the nature
/// and number of patterns given to the builder.
#[derive(Clone, Debug)]
pub(crate) struct Builder {
/// When none, this is automatically determined. Otherwise, `false` means
/// slim Teddy is used (8 buckets) and `true` means fat Teddy is used
/// (16 buckets). Fat Teddy requires AVX2, so if that CPU feature isn't
/// available and Fat Teddy was requested, no matcher will be built.
only_fat: Option<bool>,
/// When none, this is automatically determined. Otherwise, `false` means
/// that 128-bit vectors will be used (up to SSSE3 instructions) where as
/// `true` means that 256-bit vectors will be used. As with `fat`, if
/// 256-bit vectors are requested and they aren't available, then a
/// searcher will not be built.
only_256bit: Option<bool>,
/// When true (the default), the number of patterns will be used as a
/// heuristic for refusing construction of a Teddy searcher. The point here
/// is that too many patterns can overwhelm Teddy. But this can be disabled
/// in cases where the caller knows better.
heuristic_pattern_limits: bool,
}
impl Default for Builder {
fn default() -> Builder {
Builder::new()
}
}
impl Builder {
/// Create a new builder for configuring a Teddy matcher.
pub(crate) fn new() -> Builder {
Builder {
only_fat: None,
only_256bit: None,
heuristic_pattern_limits: true,
}
}
/// Build a matcher for the set of patterns given. If a matcher could not
/// be built, then `None` is returned.
///
/// Generally, a matcher isn't built if the necessary CPU features aren't
/// available, an unsupported target or if the searcher is believed to be
/// slower than standard techniques (i.e., if there are too many literals).
pub(crate) fn build(&self, patterns: Arc<Patterns>) -> Option<Searcher> {
self.build_imp(patterns)
}
/// Require the use of Fat (true) or Slim (false) Teddy. Fat Teddy uses
/// 16 buckets where as Slim Teddy uses 8 buckets. More buckets are useful
/// for a larger set of literals.
///
/// `None` is the default, which results in an automatic selection based
/// on the number of literals and available CPU features.
pub(crate) fn only_fat(&mut self, yes: Option<bool>) -> &mut Builder {
self.only_fat = yes;
self
}
/// Request the use of 256-bit vectors (true) or 128-bit vectors (false).
/// Generally, a larger vector size is better since it either permits
/// matching more patterns or matching more bytes in the haystack at once.
///
/// `None` is the default, which results in an automatic selection based on
/// the number of literals and available CPU features.
pub(crate) fn only_256bit(&mut self, yes: Option<bool>) -> &mut Builder {
self.only_256bit = yes;
self
}
/// Request that heuristic limitations on the number of patterns be
/// employed. This useful to disable for benchmarking where one wants to
/// explore how Teddy performs on large number of patterns even if the
/// heuristics would otherwise refuse construction.
///
/// This is enabled by default.
pub(crate) fn heuristic_pattern_limits(
&mut self,
yes: bool,
) -> &mut Builder {
self.heuristic_pattern_limits = yes;
self
}
fn build_imp(&self, patterns: Arc<Patterns>) -> Option<Searcher> {
let patlimit = self.heuristic_pattern_limits;
// There's no particular reason why we limit ourselves to little endian
// here, but it seems likely that some parts of Teddy as they are
// currently written (e.g., the uses of `trailing_zeros`) are likely
// wrong on non-little-endian targets. Such things are likely easy to
// fix, but at the time of writing (2023/09/18), I actually do not know
// how to test this code on a big-endian target. So for now, we're
// conservative and just bail out.
if !cfg!(target_endian = "little") {
debug!("skipping Teddy because target isn't little endian");
return None;
}
// Too many patterns will overwhelm Teddy and likely lead to slow
// downs, typically in the verification step.
if patlimit && patterns.len() > 64 {
debug!("skipping Teddy because of too many patterns");
return None;
}
#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
{
use self::x86_64::{FatAVX2, SlimAVX2, SlimSSSE3};
let mask_len = core::cmp::min(4, patterns.minimum_len());
let beefy = patterns.len() > 32;
let has_avx2 = self::x86_64::is_available_avx2();
let has_ssse3 = has_avx2 || self::x86_64::is_available_ssse3();
let use_avx2 = if self.only_256bit == Some(true) {
if !has_avx2 {
debug!(
"skipping Teddy because avx2 was demanded but unavailable"
);
return None;
}
true
} else if self.only_256bit == Some(false) {
if !has_ssse3 {
debug!(
"skipping Teddy because ssse3 was demanded but unavailable"
);
return None;
}
false
} else if !has_ssse3 && !has_avx2 {
debug!(
"skipping Teddy because ssse3 and avx2 are unavailable"
);
return None;
} else {
has_avx2
};
let fat = match self.only_fat {
None => use_avx2 && beefy,
Some(false) => false,
Some(true) if !use_avx2 => {
debug!(
"skipping Teddy because fat was demanded, but fat \
Teddy requires avx2 which is unavailable"
);
return None;
}
Some(true) => true,
};
// Just like for aarch64, it's possible that too many patterns will
// overhwelm Teddy. Unlike aarch64 though, we have Fat teddy which
// helps things scale a bit more by spreading patterns over more
// buckets.
//
// These thresholds were determined by looking at the measurements
// for the rust/aho-corasick/packed/leftmost-first and
// rust/aho-corasick/dfa/leftmost-first engines on the `teddy/`
// benchmarks.
if patlimit && mask_len == 1 && patterns.len() > 16 {
debug!(
"skipping Teddy (mask len: 1) because there are \
too many patterns",
);
return None;
}
match (mask_len, use_avx2, fat) {
(1, false, _) => {
debug!("Teddy choice: 128-bit slim, 1 byte");
SlimSSSE3::<1>::new(&patterns)
}
(1, true, false) => {
debug!("Teddy choice: 256-bit slim, 1 byte");
SlimAVX2::<1>::new(&patterns)
}
(1, true, true) => {
debug!("Teddy choice: 256-bit fat, 1 byte");
FatAVX2::<1>::new(&patterns)
}
(2, false, _) => {
debug!("Teddy choice: 128-bit slim, 2 bytes");
SlimSSSE3::<2>::new(&patterns)
}
(2, true, false) => {
debug!("Teddy choice: 256-bit slim, 2 bytes");
SlimAVX2::<2>::new(&patterns)
}
(2, true, true) => {
debug!("Teddy choice: 256-bit fat, 2 bytes");
FatAVX2::<2>::new(&patterns)
}
(3, false, _) => {
debug!("Teddy choice: 128-bit slim, 3 bytes");
SlimSSSE3::<3>::new(&patterns)
}
(3, true, false) => {
debug!("Teddy choice: 256-bit slim, 3 bytes");
SlimAVX2::<3>::new(&patterns)
}
(3, true, true) => {
debug!("Teddy choice: 256-bit fat, 3 bytes");
FatAVX2::<3>::new(&patterns)
}
(4, false, _) => {
debug!("Teddy choice: 128-bit slim, 4 bytes");
SlimSSSE3::<4>::new(&patterns)
}
(4, true, false) => {
debug!("Teddy choice: 256-bit slim, 4 bytes");
SlimAVX2::<4>::new(&patterns)
}
(4, true, true) => {
debug!("Teddy choice: 256-bit fat, 4 bytes");
FatAVX2::<4>::new(&patterns)
}
_ => {
debug!("no supported Teddy configuration found");
None
}
}
}
#[cfg(all(
target_arch = "aarch64",
target_feature = "neon",
target_endian = "little"
))]
{
use self::aarch64::SlimNeon;
let mask_len = core::cmp::min(4, patterns.minimum_len());
if self.only_256bit == Some(true) {
debug!(
"skipping Teddy because 256-bits were demanded \
but unavailable"
);
return None;
}
if self.only_fat == Some(true) {
debug!(
"skipping Teddy because fat was demanded but unavailable"
);
}
// Since we don't have Fat teddy in aarch64 (I think we'd want at
// least 256-bit vectors for that), we need to be careful not to
// allow too many patterns as it might overwhelm Teddy. Generally
// speaking, as the mask length goes up, the more patterns we can
// handle because the mask length results in fewer candidates
// generated.
//
// These thresholds were determined by looking at the measurements
// for the rust/aho-corasick/packed/leftmost-first and
// rust/aho-corasick/dfa/leftmost-first engines on the `teddy/`
// benchmarks.
match mask_len {
1 => {
if patlimit && patterns.len() > 16 {
debug!(
"skipping Teddy (mask len: 1) because there are \
too many patterns",
);
}
debug!("Teddy choice: 128-bit slim, 1 byte");
SlimNeon::<1>::new(&patterns)
}
2 => {
if patlimit && patterns.len() > 32 {
debug!(
"skipping Teddy (mask len: 2) because there are \
too many patterns",
);
}
debug!("Teddy choice: 128-bit slim, 2 bytes");
SlimNeon::<2>::new(&patterns)
}
3 => {
if patlimit && patterns.len() > 48 {
debug!(
"skipping Teddy (mask len: 3) because there are \
too many patterns",
);
}
debug!("Teddy choice: 128-bit slim, 3 bytes");
SlimNeon::<3>::new(&patterns)
}
4 => {
debug!("Teddy choice: 128-bit slim, 4 bytes");
SlimNeon::<4>::new(&patterns)
}
_ => {
debug!("no supported Teddy configuration found");
None
}
}
}
#[cfg(not(any(
all(target_arch = "x86_64", target_feature = "sse2"),
all(
target_arch = "aarch64",
target_feature = "neon",
target_endian = "little"
)
)))]
{
None
}
}
}
/// A searcher that dispatches to one of several possible Teddy variants.
#[derive(Clone, Debug)]
pub(crate) struct Searcher {
/// The Teddy variant we use. We use dynamic dispatch under the theory that
/// it results in better codegen then a enum, although this is a specious
/// claim.
///
/// This `Searcher` is essentially a wrapper for a `SearcherT` trait
/// object. We just make `memory_usage` and `minimum_len` available without
/// going through dynamic dispatch.
imp: Arc<dyn SearcherT>,
/// Total heap memory used by the Teddy variant.
memory_usage: usize,
/// The minimum haystack length this searcher can handle. It is intended
/// for callers to use some other search routine (such as Rabin-Karp) in
/// cases where the haystack (or remainer of the haystack) is too short.
minimum_len: usize,
}
impl Searcher {
/// Look for the leftmost occurrence of any pattern in this search in the
/// given haystack starting at the given position.
///
/// # Panics
///
/// This panics when `haystack[at..].len()` is less than the minimum length
/// for this haystack.
#[inline(always)]
pub(crate) fn find(
&self,
haystack: &[u8],
at: usize,
) -> Option<crate::Match> {
// SAFETY: The Teddy implementations all require a minimum haystack
// length, and this is required for safety. Therefore, we assert it
// here in order to make this method sound.
assert!(haystack[at..].len() >= self.minimum_len);
let hayptr = haystack.as_ptr();
// SAFETY: Construction of the searcher guarantees that we are able
// to run it in the current environment (i.e., we won't get an AVX2
// searcher on a x86-64 CPU without AVX2 support). Also, the pointers
// are valid as they are derived directly from a borrowed slice.
let teddym = unsafe {
self.imp.find(hayptr.add(at), hayptr.add(haystack.len()))?
};
let start = teddym.start().as_usize().wrapping_sub(hayptr.as_usize());
let end = teddym.end().as_usize().wrapping_sub(hayptr.as_usize());
let span = crate::Span { start, end };
// OK because we won't permit the construction of a searcher that
// could report a pattern ID bigger than what can fit in the crate-wide
// PatternID type.
let pid = crate::PatternID::new_unchecked(teddym.pattern().as_usize());
let m = crate::Match::new(pid, span);
Some(m)
}
/// Returns the approximate total amount of heap used by this type, in
/// units of bytes.
#[inline(always)]
pub(crate) fn memory_usage(&self) -> usize {
self.memory_usage
}
/// Returns the minimum length, in bytes, that a haystack must be in order
/// to use it with this searcher.
#[inline(always)]
pub(crate) fn minimum_len(&self) -> usize {
self.minimum_len
}
}
/// A trait that provides dynamic dispatch over the different possible Teddy
/// variants on the same algorithm.
///
/// On `x86_64` for example, it isn't known until runtime which of 12 possible
/// variants will be used. One might use one of the four slim 128-bit vector
/// variants, or one of the four 256-bit vector variants or even one of the
/// four fat 256-bit vector variants.
///
/// Since this choice is generally made when the Teddy searcher is constructed
/// and this choice is based on the patterns given and what the current CPU
/// supports, it follows that there must be some kind of indirection at search
/// time that "selects" the variant chosen at build time.
///
/// There are a few different ways to go about this. One approach is to use an
/// enum. It works fine, but in my experiments, this generally results in worse
/// codegen. Another approach, which is what we use here, is dynamic dispatch
/// via a trait object. We basically implement this trait for each possible
/// variant, select the variant we want at build time and convert it to a
/// trait object for use at search time.
///
/// Another approach is to use function pointers and stick each of the possible
/// variants into a union. This is essentially isomorphic to the dynamic
/// dispatch approach, but doesn't require any allocations. Since this crate
/// requires `alloc`, there's no real reason (AFAIK) to go down this path. (The
/// `memchr` crate does this.)
trait SearcherT:
Debug + Send + Sync + UnwindSafe + RefUnwindSafe + 'static
{
/// Execute a search on the given haystack (identified by `start` and `end`
/// raw pointers).
///
/// # Safety
///
/// Essentially, the `start` and `end` pointers must be valid and point
/// to a haystack one can read. As long as you derive them from, for
/// example, a `&[u8]`, they should automatically satisfy all of the safety
/// obligations:
///
/// * Both `start` and `end` must be valid for reads.
/// * Both `start` and `end` must point to an initialized value.
/// * Both `start` and `end` must point to the same allocated object and
/// must either be in bounds or at most one byte past the end of the
/// allocated object.
/// * Both `start` and `end` must be _derived from_ a pointer to the same
/// object.
/// * The distance between `start` and `end` must not overflow `isize`.
/// * The distance being in bounds must not rely on "wrapping around" the
/// address space.
/// * It must be the case that `start <= end`.
/// * `end - start` must be greater than the minimum length for this
/// searcher.
///
/// Also, it is expected that implementations of this trait will tag this
/// method with a `target_feature` attribute. Callers must ensure that
/// they are executing this method in an environment where that attribute
/// is valid.
unsafe fn find(&self, start: *const u8, end: *const u8) -> Option<Match>;
}
#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
mod x86_64 {
use core::arch::x86_64::{__m128i, __m256i};
use alloc::sync::Arc;
use crate::packed::{
ext::Pointer,
pattern::Patterns,
teddy::generic::{self, Match},
};
use super::{Searcher, SearcherT};
#[derive(Clone, Debug)]
pub(super) struct SlimSSSE3<const BYTES: usize> {
slim128: generic::Slim<__m128i, BYTES>,
}
// Defines SlimSSSE3 wrapper functions for 1, 2, 3 and 4 bytes.
macro_rules! slim_ssse3 {
($len:expr) => {
impl SlimSSSE3<$len> {
/// Creates a new searcher using "slim" Teddy with 128-bit
/// vectors. If SSSE3 is not available in the current
/// environment, then this returns `None`.
pub(super) fn new(
patterns: &Arc<Patterns>,
) -> Option<Searcher> {
if !is_available_ssse3() {
return None;
}
Some(unsafe { SlimSSSE3::<$len>::new_unchecked(patterns) })
}
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors without checking whether SSSE3 is available or not.
///
/// # Safety
///
/// Callers must ensure that SSSE3 is available in the current
/// environment.
#[target_feature(enable = "ssse3")]
unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
let slim128 = generic::Slim::<__m128i, $len>::new(
Arc::clone(patterns),
);
let memory_usage = slim128.memory_usage();
let minimum_len = slim128.minimum_len();
let imp = Arc::new(SlimSSSE3 { slim128 });
Searcher { imp, memory_usage, minimum_len }
}
}
impl SearcherT for SlimSSSE3<$len> {
#[target_feature(enable = "ssse3")]
#[inline]
unsafe fn find(
&self,
start: *const u8,
end: *const u8,
) -> Option<Match> {
// SAFETY: All obligations except for `target_feature` are
// passed to the caller. Our use of `target_feature` is
// safe because construction of this type requires that the
// requisite target features are available.
self.slim128.find(start, end)
}
}
};
}
slim_ssse3!(1);
slim_ssse3!(2);
slim_ssse3!(3);
slim_ssse3!(4);
#[derive(Clone, Debug)]
pub(super) struct SlimAVX2<const BYTES: usize> {
slim128: generic::Slim<__m128i, BYTES>,
slim256: generic::Slim<__m256i, BYTES>,
}
// Defines SlimAVX2 wrapper functions for 1, 2, 3 and 4 bytes.
macro_rules! slim_avx2 {
($len:expr) => {
impl SlimAVX2<$len> {
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors. If AVX2 is not available in the current
/// environment, then this returns `None`.
pub(super) fn new(
patterns: &Arc<Patterns>,
) -> Option<Searcher> {
if !is_available_avx2() {
return None;
}
Some(unsafe { SlimAVX2::<$len>::new_unchecked(patterns) })
}
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors without checking whether AVX2 is available or not.
///
/// # Safety
///
/// Callers must ensure that AVX2 is available in the current
/// environment.
#[target_feature(enable = "avx2")]
unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
let slim128 = generic::Slim::<__m128i, $len>::new(
Arc::clone(&patterns),
);
let slim256 = generic::Slim::<__m256i, $len>::new(
Arc::clone(&patterns),
);
let memory_usage =
slim128.memory_usage() + slim256.memory_usage();
let minimum_len = slim128.minimum_len();
let imp = Arc::new(SlimAVX2 { slim128, slim256 });
Searcher { imp, memory_usage, minimum_len }
}
}
impl SearcherT for SlimAVX2<$len> {
#[target_feature(enable = "avx2")]
#[inline]
unsafe fn find(
&self,
start: *const u8,
end: *const u8,
) -> Option<Match> {
// SAFETY: All obligations except for `target_feature` are
// passed to the caller. Our use of `target_feature` is
// safe because construction of this type requires that the
// requisite target features are available.
let len = end.distance(start);
if len < self.slim256.minimum_len() {
self.slim128.find(start, end)
} else {
self.slim256.find(start, end)
}
}
}
};
}
slim_avx2!(1);
slim_avx2!(2);
slim_avx2!(3);
slim_avx2!(4);
#[derive(Clone, Debug)]
pub(super) struct FatAVX2<const BYTES: usize> {
fat256: generic::Fat<__m256i, BYTES>,
}
// Defines SlimAVX2 wrapper functions for 1, 2, 3 and 4 bytes.
macro_rules! fat_avx2 {
($len:expr) => {
impl FatAVX2<$len> {
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors. If AVX2 is not available in the current
/// environment, then this returns `None`.
pub(super) fn new(
patterns: &Arc<Patterns>,
) -> Option<Searcher> {
if !is_available_avx2() {
return None;
}
Some(unsafe { FatAVX2::<$len>::new_unchecked(patterns) })
}
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors without checking whether AVX2 is available or not.
///
/// # Safety
///
/// Callers must ensure that AVX2 is available in the current
/// environment.
#[target_feature(enable = "avx2")]
unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
let fat256 = generic::Fat::<__m256i, $len>::new(
Arc::clone(&patterns),
);
let memory_usage = fat256.memory_usage();
let minimum_len = fat256.minimum_len();
let imp = Arc::new(FatAVX2 { fat256 });
Searcher { imp, memory_usage, minimum_len }
}
}
impl SearcherT for FatAVX2<$len> {
#[target_feature(enable = "avx2")]
#[inline]
unsafe fn find(
&self,
start: *const u8,
end: *const u8,
) -> Option<Match> {
// SAFETY: All obligations except for `target_feature` are
// passed to the caller. Our use of `target_feature` is
// safe because construction of this type requires that the
// requisite target features are available.
self.fat256.find(start, end)
}
}
};
}
fat_avx2!(1);
fat_avx2!(2);
fat_avx2!(3);
fat_avx2!(4);
#[inline]
pub(super) fn is_available_ssse3() -> bool {
#[cfg(not(target_feature = "sse2"))]
{
false
}
#[cfg(target_feature = "sse2")]
{
#[cfg(target_feature = "ssse3")]
{
true
}
#[cfg(not(target_feature = "ssse3"))]
{
#[cfg(feature = "std")]
{
std::is_x86_feature_detected!("ssse3")
}
#[cfg(not(feature = "std"))]
{
false
}
}
}
}
#[inline]
pub(super) fn is_available_avx2() -> bool {
#[cfg(not(target_feature = "sse2"))]
{
false
}
#[cfg(target_feature = "sse2")]
{
#[cfg(target_feature = "avx2")]
{
true
}
#[cfg(not(target_feature = "avx2"))]
{
#[cfg(feature = "std")]
{
std::is_x86_feature_detected!("avx2")
}
#[cfg(not(feature = "std"))]
{
false
}
}
}
}
}
#[cfg(all(
target_arch = "aarch64",
target_feature = "neon",
target_endian = "little"
))]
mod aarch64 {
use core::arch::aarch64::uint8x16_t;
use alloc::sync::Arc;
use crate::packed::{
pattern::Patterns,
teddy::generic::{self, Match},
};
use super::{Searcher, SearcherT};
#[derive(Clone, Debug)]
pub(super) struct SlimNeon<const BYTES: usize> {
slim128: generic::Slim<uint8x16_t, BYTES>,
}
// Defines SlimSSSE3 wrapper functions for 1, 2, 3 and 4 bytes.
macro_rules! slim_neon {
($len:expr) => {
impl SlimNeon<$len> {
/// Creates a new searcher using "slim" Teddy with 128-bit
/// vectors. If SSSE3 is not available in the current
/// environment, then this returns `None`.
pub(super) fn new(
patterns: &Arc<Patterns>,
) -> Option<Searcher> {
Some(unsafe { SlimNeon::<$len>::new_unchecked(patterns) })
}
/// Creates a new searcher using "slim" Teddy with 256-bit
/// vectors without checking whether SSSE3 is available or not.
///
/// # Safety
///
/// Callers must ensure that SSSE3 is available in the current
/// environment.
#[target_feature(enable = "neon")]
unsafe fn new_unchecked(patterns: &Arc<Patterns>) -> Searcher {
let slim128 = generic::Slim::<uint8x16_t, $len>::new(
Arc::clone(patterns),
);
let memory_usage = slim128.memory_usage();
let minimum_len = slim128.minimum_len();
let imp = Arc::new(SlimNeon { slim128 });
Searcher { imp, memory_usage, minimum_len }
}
}
impl SearcherT for SlimNeon<$len> {
#[target_feature(enable = "neon")]
#[inline]
unsafe fn find(
&self,
start: *const u8,
end: *const u8,
) -> Option<Match> {
// SAFETY: All obligations except for `target_feature` are
// passed to the caller. Our use of `target_feature` is
// safe because construction of this type requires that the
// requisite target features are available.
self.slim128.find(start, end)
}
}
};
}
slim_neon!(1);
slim_neon!(2);
slim_neon!(3);
slim_neon!(4);
}

File diff suppressed because it is too large Load Diff

View File

@@ -1,9 +0,0 @@
// Regrettable, but Teddy stuff just isn't used on all targets. And for some
// targets, like aarch64, only "slim" Teddy is used and so "fat" Teddy gets a
// bunch of dead-code warnings. Just not worth trying to squash them. Blech.
#![allow(dead_code)]
pub(crate) use self::builder::{Builder, Searcher};
mod builder;
mod generic;

View File

@@ -1,583 +0,0 @@
use std::collections::HashMap;
use alloc::{
format,
string::{String, ToString},
vec,
vec::Vec,
};
use crate::{
packed::{Config, MatchKind},
util::search::Match,
};
/// A description of a single test against a multi-pattern searcher.
///
/// A single test may not necessarily pass on every configuration of a
/// searcher. The tests are categorized and grouped appropriately below.
#[derive(Clone, Debug, Eq, PartialEq)]
struct SearchTest {
/// The name of this test, for debugging.
name: &'static str,
/// The patterns to search for.
patterns: &'static [&'static str],
/// The text to search.
haystack: &'static str,
/// Each match is a triple of (pattern_index, start, end), where
/// pattern_index is an index into `patterns` and `start`/`end` are indices
/// into `haystack`.
matches: &'static [(usize, usize, usize)],
}
struct SearchTestOwned {
offset: usize,
name: String,
patterns: Vec<String>,
haystack: String,
matches: Vec<(usize, usize, usize)>,
}
impl SearchTest {
fn variations(&self) -> Vec<SearchTestOwned> {
let count = if cfg!(miri) { 1 } else { 261 };
let mut tests = vec![];
for i in 0..count {
tests.push(self.offset_prefix(i));
tests.push(self.offset_suffix(i));
tests.push(self.offset_both(i));
}
tests
}
fn offset_both(&self, off: usize) -> SearchTestOwned {
SearchTestOwned {
offset: off,
name: self.name.to_string(),
patterns: self.patterns.iter().map(|s| s.to_string()).collect(),
haystack: format!(
"{}{}{}",
"Z".repeat(off),
self.haystack,
"Z".repeat(off)
),
matches: self
.matches
.iter()
.map(|&(id, s, e)| (id, s + off, e + off))
.collect(),
}
}
fn offset_prefix(&self, off: usize) -> SearchTestOwned {
SearchTestOwned {
offset: off,
name: self.name.to_string(),
patterns: self.patterns.iter().map(|s| s.to_string()).collect(),
haystack: format!("{}{}", "Z".repeat(off), self.haystack),
matches: self
.matches
.iter()
.map(|&(id, s, e)| (id, s + off, e + off))
.collect(),
}
}
fn offset_suffix(&self, off: usize) -> SearchTestOwned {
SearchTestOwned {
offset: off,
name: self.name.to_string(),
patterns: self.patterns.iter().map(|s| s.to_string()).collect(),
haystack: format!("{}{}", self.haystack, "Z".repeat(off)),
matches: self.matches.to_vec(),
}
}
}
/// Short-hand constructor for SearchTest. We use it a lot below.
macro_rules! t {
($name:ident, $patterns:expr, $haystack:expr, $matches:expr) => {
SearchTest {
name: stringify!($name),
patterns: $patterns,
haystack: $haystack,
matches: $matches,
}
};
}
/// A collection of test groups.
type TestCollection = &'static [&'static [SearchTest]];
// Define several collections corresponding to the different type of match
// semantics supported. These collections have some overlap, but each
// collection should have some tests that no other collection has.
/// Tests for leftmost-first match semantics.
const PACKED_LEFTMOST_FIRST: TestCollection =
&[BASICS, LEFTMOST, LEFTMOST_FIRST, REGRESSION, TEDDY];
/// Tests for leftmost-longest match semantics.
const PACKED_LEFTMOST_LONGEST: TestCollection =
&[BASICS, LEFTMOST, LEFTMOST_LONGEST, REGRESSION, TEDDY];
// Now define the individual tests that make up the collections above.
/// A collection of tests for the that should always be true regardless of
/// match semantics. That is, all combinations of leftmost-{first, longest}
/// should produce the same answer.
const BASICS: &'static [SearchTest] = &[
t!(basic001, &["a"], "", &[]),
t!(basic010, &["a"], "a", &[(0, 0, 1)]),
t!(basic020, &["a"], "aa", &[(0, 0, 1), (0, 1, 2)]),
t!(basic030, &["a"], "aaa", &[(0, 0, 1), (0, 1, 2), (0, 2, 3)]),
t!(basic040, &["a"], "aba", &[(0, 0, 1), (0, 2, 3)]),
t!(basic050, &["a"], "bba", &[(0, 2, 3)]),
t!(basic060, &["a"], "bbb", &[]),
t!(basic070, &["a"], "bababbbba", &[(0, 1, 2), (0, 3, 4), (0, 8, 9)]),
t!(basic100, &["aa"], "", &[]),
t!(basic110, &["aa"], "aa", &[(0, 0, 2)]),
t!(basic120, &["aa"], "aabbaa", &[(0, 0, 2), (0, 4, 6)]),
t!(basic130, &["aa"], "abbab", &[]),
t!(basic140, &["aa"], "abbabaa", &[(0, 5, 7)]),
t!(basic150, &["aaa"], "aaa", &[(0, 0, 3)]),
t!(basic200, &["abc"], "abc", &[(0, 0, 3)]),
t!(basic210, &["abc"], "zazabzabcz", &[(0, 6, 9)]),
t!(basic220, &["abc"], "zazabczabcz", &[(0, 3, 6), (0, 7, 10)]),
t!(basic230, &["abcd"], "abcd", &[(0, 0, 4)]),
t!(basic240, &["abcd"], "zazabzabcdz", &[(0, 6, 10)]),
t!(basic250, &["abcd"], "zazabcdzabcdz", &[(0, 3, 7), (0, 8, 12)]),
t!(basic300, &["a", "b"], "", &[]),
t!(basic310, &["a", "b"], "z", &[]),
t!(basic320, &["a", "b"], "b", &[(1, 0, 1)]),
t!(basic330, &["a", "b"], "a", &[(0, 0, 1)]),
t!(
basic340,
&["a", "b"],
"abba",
&[(0, 0, 1), (1, 1, 2), (1, 2, 3), (0, 3, 4),]
),
t!(
basic350,
&["b", "a"],
"abba",
&[(1, 0, 1), (0, 1, 2), (0, 2, 3), (1, 3, 4),]
),
t!(basic360, &["abc", "bc"], "xbc", &[(1, 1, 3),]),
t!(basic400, &["foo", "bar"], "", &[]),
t!(basic410, &["foo", "bar"], "foobar", &[(0, 0, 3), (1, 3, 6),]),
t!(basic420, &["foo", "bar"], "barfoo", &[(1, 0, 3), (0, 3, 6),]),
t!(basic430, &["foo", "bar"], "foofoo", &[(0, 0, 3), (0, 3, 6),]),
t!(basic440, &["foo", "bar"], "barbar", &[(1, 0, 3), (1, 3, 6),]),
t!(basic450, &["foo", "bar"], "bafofoo", &[(0, 4, 7),]),
t!(basic460, &["bar", "foo"], "bafofoo", &[(1, 4, 7),]),
t!(basic470, &["foo", "bar"], "fobabar", &[(1, 4, 7),]),
t!(basic480, &["bar", "foo"], "fobabar", &[(0, 4, 7),]),
t!(basic700, &["yabcdef", "abcdezghi"], "yabcdefghi", &[(0, 0, 7),]),
t!(basic710, &["yabcdef", "abcdezghi"], "yabcdezghi", &[(1, 1, 10),]),
t!(
basic720,
&["yabcdef", "bcdeyabc", "abcdezghi"],
"yabcdezghi",
&[(2, 1, 10),]
),
t!(basic810, &["abcd", "bcd", "cd"], "abcd", &[(0, 0, 4),]),
t!(basic820, &["bcd", "cd", "abcd"], "abcd", &[(2, 0, 4),]),
t!(basic830, &["abc", "bc"], "zazabcz", &[(0, 3, 6),]),
t!(
basic840,
&["ab", "ba"],
"abababa",
&[(0, 0, 2), (0, 2, 4), (0, 4, 6),]
),
t!(basic850, &["foo", "foo"], "foobarfoo", &[(0, 0, 3), (0, 6, 9),]),
];
/// Tests for leftmost match semantics. These should pass for both
/// leftmost-first and leftmost-longest match kinds. Stated differently, among
/// ambiguous matches, the longest match and the match that appeared first when
/// constructing the automaton should always be the same.
const LEFTMOST: &'static [SearchTest] = &[
t!(leftmost000, &["ab", "ab"], "abcd", &[(0, 0, 2)]),
t!(leftmost030, &["a", "ab"], "aa", &[(0, 0, 1), (0, 1, 2)]),
t!(leftmost031, &["ab", "a"], "aa", &[(1, 0, 1), (1, 1, 2)]),
t!(leftmost032, &["ab", "a"], "xayabbbz", &[(1, 1, 2), (0, 3, 5)]),
t!(leftmost300, &["abcd", "bce", "b"], "abce", &[(1, 1, 4)]),
t!(leftmost310, &["abcd", "ce", "bc"], "abce", &[(2, 1, 3)]),
t!(leftmost320, &["abcd", "bce", "ce", "b"], "abce", &[(1, 1, 4)]),
t!(leftmost330, &["abcd", "bce", "cz", "bc"], "abcz", &[(3, 1, 3)]),
t!(leftmost340, &["bce", "cz", "bc"], "bcz", &[(2, 0, 2)]),
t!(leftmost350, &["abc", "bd", "ab"], "abd", &[(2, 0, 2)]),
t!(
leftmost360,
&["abcdefghi", "hz", "abcdefgh"],
"abcdefghz",
&[(2, 0, 8),]
),
t!(
leftmost370,
&["abcdefghi", "cde", "hz", "abcdefgh"],
"abcdefghz",
&[(3, 0, 8),]
),
t!(
leftmost380,
&["abcdefghi", "hz", "abcdefgh", "a"],
"abcdefghz",
&[(2, 0, 8),]
),
t!(
leftmost390,
&["b", "abcdefghi", "hz", "abcdefgh"],
"abcdefghz",
&[(3, 0, 8),]
),
t!(
leftmost400,
&["h", "abcdefghi", "hz", "abcdefgh"],
"abcdefghz",
&[(3, 0, 8),]
),
t!(
leftmost410,
&["z", "abcdefghi", "hz", "abcdefgh"],
"abcdefghz",
&[(3, 0, 8), (0, 8, 9),]
),
];
/// Tests for non-overlapping leftmost-first match semantics. These tests
/// should generally be specific to leftmost-first, which means they should
/// generally fail under leftmost-longest semantics.
const LEFTMOST_FIRST: &'static [SearchTest] = &[
t!(leftfirst000, &["ab", "abcd"], "abcd", &[(0, 0, 2)]),
t!(leftfirst020, &["abcd", "ab"], "abcd", &[(0, 0, 4)]),
t!(leftfirst030, &["ab", "ab"], "abcd", &[(0, 0, 2)]),
t!(leftfirst040, &["a", "ab"], "xayabbbz", &[(0, 1, 2), (0, 3, 4)]),
t!(leftfirst100, &["abcdefg", "bcde", "bcdef"], "abcdef", &[(1, 1, 5)]),
t!(leftfirst110, &["abcdefg", "bcdef", "bcde"], "abcdef", &[(1, 1, 6)]),
t!(leftfirst300, &["abcd", "b", "bce"], "abce", &[(1, 1, 2)]),
t!(
leftfirst310,
&["abcd", "b", "bce", "ce"],
"abce",
&[(1, 1, 2), (3, 2, 4),]
),
t!(
leftfirst320,
&["a", "abcdefghi", "hz", "abcdefgh"],
"abcdefghz",
&[(0, 0, 1), (2, 7, 9),]
),
t!(leftfirst330, &["a", "abab"], "abab", &[(0, 0, 1), (0, 2, 3)]),
t!(
leftfirst340,
&["abcdef", "x", "x", "x", "x", "x", "x", "abcde"],
"abcdef",
&[(0, 0, 6)]
),
];
/// Tests for non-overlapping leftmost-longest match semantics. These tests
/// should generally be specific to leftmost-longest, which means they should
/// generally fail under leftmost-first semantics.
const LEFTMOST_LONGEST: &'static [SearchTest] = &[
t!(leftlong000, &["ab", "abcd"], "abcd", &[(1, 0, 4)]),
t!(leftlong010, &["abcd", "bcd", "cd", "b"], "abcd", &[(0, 0, 4),]),
t!(leftlong040, &["a", "ab"], "a", &[(0, 0, 1)]),
t!(leftlong050, &["a", "ab"], "ab", &[(1, 0, 2)]),
t!(leftlong060, &["ab", "a"], "a", &[(1, 0, 1)]),
t!(leftlong070, &["ab", "a"], "ab", &[(0, 0, 2)]),
t!(leftlong100, &["abcdefg", "bcde", "bcdef"], "abcdef", &[(2, 1, 6)]),
t!(leftlong110, &["abcdefg", "bcdef", "bcde"], "abcdef", &[(1, 1, 6)]),
t!(leftlong300, &["abcd", "b", "bce"], "abce", &[(2, 1, 4)]),
t!(
leftlong310,
&["a", "abcdefghi", "hz", "abcdefgh"],
"abcdefghz",
&[(3, 0, 8),]
),
t!(leftlong320, &["a", "abab"], "abab", &[(1, 0, 4)]),
t!(leftlong330, &["abcd", "b", "ce"], "abce", &[(1, 1, 2), (2, 2, 4),]),
t!(leftlong340, &["a", "ab"], "xayabbbz", &[(0, 1, 2), (1, 3, 5)]),
];
/// Regression tests that are applied to all combinations.
///
/// If regression tests are needed for specific match semantics, then add them
/// to the appropriate group above.
const REGRESSION: &'static [SearchTest] = &[
t!(regression010, &["inf", "ind"], "infind", &[(0, 0, 3), (1, 3, 6),]),
t!(regression020, &["ind", "inf"], "infind", &[(1, 0, 3), (0, 3, 6),]),
t!(
regression030,
&["libcore/", "libstd/"],
"libcore/char/methods.rs",
&[(0, 0, 8),]
),
t!(
regression040,
&["libstd/", "libcore/"],
"libcore/char/methods.rs",
&[(1, 0, 8),]
),
t!(
regression050,
&["\x00\x00\x01", "\x00\x00\x00"],
"\x00\x00\x00",
&[(1, 0, 3),]
),
t!(
regression060,
&["\x00\x00\x00", "\x00\x00\x01"],
"\x00\x00\x00",
&[(0, 0, 3),]
),
];
const TEDDY: &'static [SearchTest] = &[
t!(
teddy010,
&["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k"],
"abcdefghijk",
&[
(0, 0, 1),
(1, 1, 2),
(2, 2, 3),
(3, 3, 4),
(4, 4, 5),
(5, 5, 6),
(6, 6, 7),
(7, 7, 8),
(8, 8, 9),
(9, 9, 10),
(10, 10, 11)
]
),
t!(
teddy020,
&["ab", "bc", "cd", "de", "ef", "fg", "gh", "hi", "ij", "jk", "kl"],
"abcdefghijk",
&[(0, 0, 2), (2, 2, 4), (4, 4, 6), (6, 6, 8), (8, 8, 10),]
),
t!(
teddy030,
&["abc"],
"abcdefghijklmnopqrstuvwxyzabcdefghijk",
&[(0, 0, 3), (0, 26, 29)]
),
];
// Now define a test for each combination of things above that we want to run.
// Since there are a few different combinations for each collection of tests,
// we define a couple of macros to avoid repetition drudgery. The testconfig
// macro constructs the automaton from a given match kind, and runs the search
// tests one-by-one over the given collection. The `with` parameter allows one
// to configure the config with additional parameters. The testcombo macro
// invokes testconfig in precisely this way: it sets up several tests where
// each one turns a different knob on Config.
macro_rules! testconfig {
($name:ident, $collection:expr, $with:expr) => {
#[test]
fn $name() {
run_search_tests($collection, |test| {
let mut config = Config::new();
$with(&mut config);
let mut builder = config.builder();
builder.extend(test.patterns.iter().map(|p| p.as_bytes()));
let searcher = match builder.build() {
Some(searcher) => searcher,
None => {
// For x86-64 and aarch64, not building a searcher is
// probably a bug, so be loud.
if cfg!(any(
target_arch = "x86_64",
target_arch = "aarch64"
)) {
panic!("failed to build packed searcher")
}
return None;
}
};
Some(searcher.find_iter(&test.haystack).collect())
});
}
};
}
testconfig!(
search_default_leftmost_first,
PACKED_LEFTMOST_FIRST,
|_: &mut Config| {}
);
testconfig!(
search_default_leftmost_longest,
PACKED_LEFTMOST_LONGEST,
|c: &mut Config| {
c.match_kind(MatchKind::LeftmostLongest);
}
);
testconfig!(
search_teddy_leftmost_first,
PACKED_LEFTMOST_FIRST,
|c: &mut Config| {
c.only_teddy(true);
}
);
testconfig!(
search_teddy_leftmost_longest,
PACKED_LEFTMOST_LONGEST,
|c: &mut Config| {
c.only_teddy(true).match_kind(MatchKind::LeftmostLongest);
}
);
testconfig!(
search_teddy_ssse3_leftmost_first,
PACKED_LEFTMOST_FIRST,
|c: &mut Config| {
c.only_teddy(true);
#[cfg(target_arch = "x86_64")]
if std::is_x86_feature_detected!("ssse3") {
c.only_teddy_256bit(Some(false));
}
}
);
testconfig!(
search_teddy_ssse3_leftmost_longest,
PACKED_LEFTMOST_LONGEST,
|c: &mut Config| {
c.only_teddy(true).match_kind(MatchKind::LeftmostLongest);
#[cfg(target_arch = "x86_64")]
if std::is_x86_feature_detected!("ssse3") {
c.only_teddy_256bit(Some(false));
}
}
);
testconfig!(
search_teddy_avx2_leftmost_first,
PACKED_LEFTMOST_FIRST,
|c: &mut Config| {
c.only_teddy(true);
#[cfg(target_arch = "x86_64")]
if std::is_x86_feature_detected!("avx2") {
c.only_teddy_256bit(Some(true));
}
}
);
testconfig!(
search_teddy_avx2_leftmost_longest,
PACKED_LEFTMOST_LONGEST,
|c: &mut Config| {
c.only_teddy(true).match_kind(MatchKind::LeftmostLongest);
#[cfg(target_arch = "x86_64")]
if std::is_x86_feature_detected!("avx2") {
c.only_teddy_256bit(Some(true));
}
}
);
testconfig!(
search_teddy_fat_leftmost_first,
PACKED_LEFTMOST_FIRST,
|c: &mut Config| {
c.only_teddy(true);
#[cfg(target_arch = "x86_64")]
if std::is_x86_feature_detected!("avx2") {
c.only_teddy_fat(Some(true));
}
}
);
testconfig!(
search_teddy_fat_leftmost_longest,
PACKED_LEFTMOST_LONGEST,
|c: &mut Config| {
c.only_teddy(true).match_kind(MatchKind::LeftmostLongest);
#[cfg(target_arch = "x86_64")]
if std::is_x86_feature_detected!("avx2") {
c.only_teddy_fat(Some(true));
}
}
);
testconfig!(
search_rabinkarp_leftmost_first,
PACKED_LEFTMOST_FIRST,
|c: &mut Config| {
c.only_rabin_karp(true);
}
);
testconfig!(
search_rabinkarp_leftmost_longest,
PACKED_LEFTMOST_LONGEST,
|c: &mut Config| {
c.only_rabin_karp(true).match_kind(MatchKind::LeftmostLongest);
}
);
#[test]
fn search_tests_have_unique_names() {
let assert = |constname, tests: &[SearchTest]| {
let mut seen = HashMap::new(); // map from test name to position
for (i, test) in tests.iter().enumerate() {
if !seen.contains_key(test.name) {
seen.insert(test.name, i);
} else {
let last = seen[test.name];
panic!(
"{} tests have duplicate names at positions {} and {}",
constname, last, i
);
}
}
};
assert("BASICS", BASICS);
assert("LEFTMOST", LEFTMOST);
assert("LEFTMOST_FIRST", LEFTMOST_FIRST);
assert("LEFTMOST_LONGEST", LEFTMOST_LONGEST);
assert("REGRESSION", REGRESSION);
assert("TEDDY", TEDDY);
}
fn run_search_tests<F: FnMut(&SearchTestOwned) -> Option<Vec<Match>>>(
which: TestCollection,
mut f: F,
) {
let get_match_triples =
|matches: Vec<Match>| -> Vec<(usize, usize, usize)> {
matches
.into_iter()
.map(|m| (m.pattern().as_usize(), m.start(), m.end()))
.collect()
};
for &tests in which {
for spec in tests {
for test in spec.variations() {
let results = match f(&test) {
None => continue,
Some(results) => results,
};
assert_eq!(
test.matches,
get_match_triples(results).as_slice(),
"test: {}, patterns: {:?}, haystack(len={:?}): {:?}, \
offset: {:?}",
test.name,
test.patterns,
test.haystack.len(),
test.haystack,
test.offset,
);
}
}
}
}

File diff suppressed because it is too large Load Diff

File diff suppressed because it is too large Load Diff

Some files were not shown because too many files have changed in this diff Show More