{"action":"created","issue":{"url":"https://api.github.com/repos/BurntSushi/fst/issues/5","labels_url":"https://api.github.com/repos/BurntSushi/fst/issues/5/labels{/name}","comments_url":"https://api.github.com/repos/BurntSushi/fst/issues/5/comments","events_url":"https://api.github.com/repos/BurntSushi/fst/issues/5/events","html_url":"https://github.com/BurntSushi/fst/pull/5","id":117019156,"number":5,"title":"Impl Automaton for {u8, str}","user":{"login":"gereeter","id":2328242,"avatar_url":"https://avatars.githubusercontent.com/u/2328242?v=3","gravatar_id":"","url":"https://api.github.com/users/gereeter","html_url":"https://github.com/gereeter","followers_url":"https://api.github.com/users/gereeter/followers","following_url":"https://api.github.com/users/gereeter/following{/other_user}","gists_url":"https://api.github.com/users/gereeter/gists{/gist_id}","starred_url":"https://api.github.com/users/gereeter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gereeter/subscriptions","organizations_url":"https://api.github.com/users/gereeter/orgs","repos_url":"https://api.github.com/users/gereeter/repos","events_url":"https://api.github.com/users/gereeter/events{/privacy}","received_events_url":"https://api.github.com/users/gereeter/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":2,"created_at":"2015-11-15T21:30:43Z","updated_at":"2015-11-16T13:05:57Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/BurntSushi/fst/pulls/5","html_url":"https://github.com/BurntSushi/fst/pull/5","diff_url":"https://github.com/BurntSushi/fst/pull/5.diff","patch_url":"https://github.com/BurntSushi/fst/pull/5.patch"},"body":"For better or worse, this makes `fst.search(\"foo\")` work as expected - this will be less efficient than the specialized methods. However, this also allows things like `fst.search(\"foo\".starts_with())` and so on.\r\n\r\nThe performance issue might be fixed by adding another method to `Automaton`:\r\n\r\n```rust\r\nfn suggest_next(&self, state: &Self::State) -> Option<u8> {\r\n    None\r\n}\r\n```\r\n\r\nThis would have the semantics that if `Some(byte)` is returned, then `!self.can_match(self.accept(state, other_byte))` for `other_byte != byte`. The FST searcher could then use this suggested byte to not have to explore all possible branches."},"comment":{"url":"https://api.github.com/repos/BurntSushi/fst/issues/comments/157023145","html_url":"https://github.com/BurntSushi/fst/pull/5#issuecomment-157023145","issue_url":"https://api.github.com/repos/BurntSushi/fst/issues/5","id":157023145,"user":{"login":"BurntSushi","id":456674,"avatar_url":"https://avatars.githubusercontent.com/u/456674?v=3","gravatar_id":"","url":"https://api.github.com/users/BurntSushi","html_url":"https://github.com/BurntSushi","followers_url":"https://api.github.com/users/BurntSushi/followers","following_url":"https://api.github.com/users/BurntSushi/following{/other_user}","gists_url":"https://api.github.com/users/BurntSushi/gists{/gist_id}","starred_url":"https://api.github.com/users/BurntSushi/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/BurntSushi/subscriptions","organizations_url":"https://api.github.com/users/BurntSushi/orgs","repos_url":"https://api.github.com/users/BurntSushi/repos","events_url":"https://api.github.com/users/BurntSushi/events{/privacy}","received_events_url":"https://api.github.com/users/BurntSushi/received_events","type":"User","site_admin":false},"created_at":"2015-11-16T13:05:57Z","updated_at":"2015-11-16T13:05:57Z","body":"Hmm, I don't think that change to `Stream` is actually required. As soon as `accept` returns `StringState(usize::MAX)`, `can_match` should return `false`. That should be enough to prune the search space.\r\n\r\nOh, I see, I think you're saying that `suggest_next` would allow one to only examine a single transition if there are many. I'm not sure that's really worth it, since the vast majority of states in a typical FST have exactly 1 transition.\r\n\r\nWith all that said, I actually am not sure that I want these impls at this time. Notably, `Regex::new(\"foo.*\").unwrap()` works well for \"find keys with this prefix.\" It's certainly not as ergonomic, but these impls introduce multiple ways of accomplishing the same thing. For example, `fst.search(\"foo\")` is a little strange, since I don't know when you would want to use that in lieu of `fst.get(\"foo\")` or `fst.contains_key(\"foo\")`. (I guess maybe in a generic context?)\r\n\r\nI think this falls into the \"maybe\" pile for me personally. I'd like to get more experience using the library before adding too many conveniences. :-)"}}