diff options
Diffstat (limited to 'src/aho_corasick/full.rs.html')
| -rw-r--r-- | src/aho_corasick/full.rs.html | 329 |
1 files changed, 329 insertions, 0 deletions
diff --git a/src/aho_corasick/full.rs.html b/src/aho_corasick/full.rs.html new file mode 100644 index 0000000..f9f4f65 --- /dev/null +++ b/src/aho_corasick/full.rs.html @@ -0,0 +1,329 @@ +<!DOCTYPE html> +<html lang="en"> +<head> + <meta charset="utf-8"> + <meta name="viewport" content="width=device-width, initial-scale=1.0"> + <meta name="generator" content="rustdoc"> + <meta name="description" content="Source to the Rust file `/home/travis/.cargo/registry/src/github.com-0a35038f75765ae4/aho-corasick-0.2.1/src/full.rs`."> + <meta name="keywords" content="rust, rustlang, rust-lang"> + + <title>full.rs.html -- source</title> + + <link rel="stylesheet" type="text/css" href="../../main.css"> + + + +</head> +<body class="rustdoc"> + <!--[if lte IE 8]> + <div class="warning"> + This old browser is unsupported and will most likely display funky + things. + </div> + <![endif]--> + + + + <section class="sidebar"> + + + </section> + + <nav class="sub"> + <form class="search-form js-only"> + <div class="search-container"> + <input class="search-input" name="search" + autocomplete="off" + placeholder="Click or press 'S' to search, '?' for more options..." + type="search"> + </div> + </form> + </nav> + + <section id='main' class="content source"><pre class="line-numbers"><span id="1"> 1</span> +<span id="2"> 2</span> +<span id="3"> 3</span> +<span id="4"> 4</span> +<span id="5"> 5</span> +<span id="6"> 6</span> +<span id="7"> 7</span> +<span id="8"> 8</span> +<span id="9"> 9</span> +<span id="10"> 10</span> +<span id="11"> 11</span> +<span id="12"> 12</span> +<span id="13"> 13</span> +<span id="14"> 14</span> +<span id="15"> 15</span> +<span id="16"> 16</span> +<span id="17"> 17</span> +<span id="18"> 18</span> +<span id="19"> 19</span> +<span id="20"> 20</span> +<span id="21"> 21</span> +<span id="22"> 22</span> +<span id="23"> 23</span> +<span id="24"> 24</span> +<span id="25"> 25</span> +<span id="26"> 26</span> +<span id="27"> 27</span> +<span id="28"> 28</span> +<span id="29"> 29</span> +<span id="30"> 30</span> +<span id="31"> 31</span> +<span id="32"> 32</span> +<span id="33"> 33</span> +<span id="34"> 34</span> +<span id="35"> 35</span> +<span id="36"> 36</span> +<span id="37"> 37</span> +<span id="38"> 38</span> +<span id="39"> 39</span> +<span id="40"> 40</span> +<span id="41"> 41</span> +<span id="42"> 42</span> +<span id="43"> 43</span> +<span id="44"> 44</span> +<span id="45"> 45</span> +<span id="46"> 46</span> +<span id="47"> 47</span> +<span id="48"> 48</span> +<span id="49"> 49</span> +<span id="50"> 50</span> +<span id="51"> 51</span> +<span id="52"> 52</span> +<span id="53"> 53</span> +<span id="54"> 54</span> +<span id="55"> 55</span> +<span id="56"> 56</span> +<span id="57"> 57</span> +<span id="58"> 58</span> +<span id="59"> 59</span> +<span id="60"> 60</span> +<span id="61"> 61</span> +<span id="62"> 62</span> +<span id="63"> 63</span> +<span id="64"> 64</span> +<span id="65"> 65</span> +<span id="66"> 66</span> +<span id="67"> 67</span> +<span id="68"> 68</span> +<span id="69"> 69</span> +<span id="70"> 70</span> +<span id="71"> 71</span> +<span id="72"> 72</span> +<span id="73"> 73</span> +<span id="74"> 74</span> +<span id="75"> 75</span> +<span id="76"> 76</span> +<span id="77"> 77</span> +<span id="78"> 78</span> +<span id="79"> 79</span> +<span id="80"> 80</span> +<span id="81"> 81</span> +<span id="82"> 82</span> +<span id="83"> 83</span> +<span id="84"> 84</span> +<span id="85"> 85</span> +<span id="86"> 86</span> +<span id="87"> 87</span> +<span id="88"> 88</span> +<span id="89"> 89</span> +<span id="90"> 90</span> +<span id="91"> 91</span> +<span id="92"> 92</span> +<span id="93"> 93</span> +<span id="94"> 94</span> +<span id="95"> 95</span> +<span id="96"> 96</span> +<span id="97"> 97</span> +<span id="98"> 98</span> +<span id="99"> 99</span> +<span id="100">100</span> +<span id="101">101</span> +<span id="102">102</span> +<span id="103">103</span> +<span id="104">104</span> +<span id="105">105</span> +<span id="106">106</span> +<span id="107">107</span> +<span id="108">108</span> +<span id="109">109</span> +<span id="110">110</span> +<span id="111">111</span> +<span id="112">112</span> +<span id="113">113</span> +<span id="114">114</span> +<span id="115">115</span> +<span id="116">116</span> +</pre><pre class='rust '> +<span class='kw'>use</span> <span class='ident'>memchr</span>::<span class='ident'>memchr</span>; + +<span class='kw'>use</span> <span class='ident'>super</span>::{ + <span class='ident'>FAIL_STATE</span>, <span class='ident'>ROOT_STATE</span>, + <span class='ident'>StateIdx</span>, <span class='ident'>PatIdx</span>, + <span class='ident'>AcAutomaton</span>, <span class='ident'>Transitions</span>, <span class='ident'>Match</span>, +}; +<span class='kw'>use</span> <span class='ident'>super</span>::<span class='ident'>autiter</span>::<span class='ident'>Automaton</span>; + +<span class='doccomment'>/// A complete Aho-Corasick automaton.</span> +<span class='doccomment'>///</span> +<span class='doccomment'>/// This uses a single transition matrix that permits each input character</span> +<span class='doccomment'>/// to move to the next state with a single lookup in the matrix.</span> +<span class='doccomment'>///</span> +<span class='doccomment'>/// This is as fast as it gets, but it is guaranteed to use a lot of memory.</span> +<span class='doccomment'>/// Namely, it will use at least `4 * 256 * #states`, where the number of</span> +<span class='doccomment'>/// states is capped at length of all patterns concatenated.</span> +<span class='attribute'>#[<span class='ident'>derive</span>(<span class='ident'>Clone</span>, <span class='ident'>Debug</span>)]</span> +<span class='kw'>pub</span> <span class='kw'>struct</span> <span class='ident'>FullAcAutomaton</span> { + <span class='ident'>pats</span>: <span class='ident'>Vec</span><span class='op'><</span><span class='ident'>String</span><span class='op'>></span>, + <span class='comment'>// i * #states + si</span> + <span class='ident'>trans</span>: <span class='ident'>Vec</span><span class='op'><</span><span class='ident'>StateIdx</span><span class='op'>></span>, <span class='comment'>// row-major, where states are rows</span> + <span class='ident'>out</span>: <span class='ident'>Vec</span><span class='op'><</span><span class='ident'>Vec</span><span class='op'><</span><span class='ident'>PatIdx</span><span class='op'>>></span>, <span class='comment'>// indexed by StateIdx</span> + <span class='ident'>start_bytes</span>: <span class='ident'>Vec</span><span class='op'><</span><span class='ident'>u8</span><span class='op'>></span>, +} + +<span class='kw'>impl</span> <span class='ident'>FullAcAutomaton</span> { + <span class='doccomment'>/// Build a new expanded Aho-Corasick automaton from an existing</span> + <span class='doccomment'>/// Aho-Corasick automaton.</span> + <span class='kw'>pub</span> <span class='kw'>fn</span> <span class='ident'>new</span><span class='op'><</span><span class='ident'>T</span>: <span class='ident'>Transitions</span><span class='op'>></span>(<span class='ident'>ac</span>: <span class='ident'>AcAutomaton</span><span class='op'><</span><span class='ident'>T</span><span class='op'>></span>) <span class='op'>-></span> <span class='ident'>FullAcAutomaton</span> { + <span class='kw'>let</span> <span class='kw-2'>mut</span> <span class='ident'>fac</span> <span class='op'>=</span> <span class='ident'>FullAcAutomaton</span> { + <span class='ident'>pats</span>: <span class='macro'>vec</span><span class='macro'>!</span>[], + <span class='ident'>trans</span>: <span class='macro'>vec</span><span class='macro'>!</span>[<span class='ident'>FAIL_STATE</span>; <span class='number'>256</span> <span class='op'>*</span> <span class='ident'>ac</span>.<span class='ident'>states</span>.<span class='ident'>len</span>()], + <span class='ident'>out</span>: <span class='macro'>vec</span><span class='macro'>!</span>[<span class='macro'>vec</span><span class='macro'>!</span>[]; <span class='ident'>ac</span>.<span class='ident'>states</span>.<span class='ident'>len</span>()], + <span class='ident'>start_bytes</span>: <span class='macro'>vec</span><span class='macro'>!</span>[], + }; + <span class='ident'>fac</span>.<span class='ident'>build_matrix</span>(<span class='kw-2'>&</span><span class='ident'>ac</span>); + <span class='ident'>fac</span>.<span class='ident'>pats</span> <span class='op'>=</span> <span class='ident'>ac</span>.<span class='ident'>pats</span>; + <span class='ident'>fac</span>.<span class='ident'>start_bytes</span> <span class='op'>=</span> <span class='ident'>ac</span>.<span class='ident'>start_bytes</span>; + <span class='ident'>fac</span> + } + + <span class='kw'>fn</span> <span class='ident'>set</span>(<span class='kw-2'>&</span><span class='kw-2'>mut</span> <span class='self'>self</span>, <span class='ident'>si</span>: <span class='ident'>StateIdx</span>, <span class='ident'>i</span>: <span class='ident'>u8</span>, <span class='ident'>goto</span>: <span class='ident'>StateIdx</span>) { + <span class='kw'>let</span> <span class='ident'>ns</span> <span class='op'>=</span> <span class='self'>self</span>.<span class='ident'>num_states</span>(); + <span class='self'>self</span>.<span class='ident'>trans</span>[<span class='ident'>i</span> <span class='kw'>as</span> <span class='ident'>usize</span> <span class='op'>*</span> <span class='ident'>ns</span> <span class='op'>+</span> <span class='ident'>si</span> <span class='kw'>as</span> <span class='ident'>usize</span>] <span class='op'>=</span> <span class='ident'>goto</span>; + } + + <span class='attribute'>#[<span class='ident'>inline</span>]</span> + <span class='kw'>fn</span> <span class='ident'>num_states</span>(<span class='kw-2'>&</span><span class='self'>self</span>) <span class='op'>-></span> <span class='ident'>usize</span> { + <span class='self'>self</span>.<span class='ident'>out</span>.<span class='ident'>len</span>() + } +} + +<span class='kw'>impl</span> <span class='ident'>Automaton</span> <span class='kw'>for</span> <span class='ident'>FullAcAutomaton</span> { + <span class='attribute'>#[<span class='ident'>inline</span>]</span> + <span class='kw'>fn</span> <span class='ident'>next_state</span>(<span class='kw-2'>&</span><span class='self'>self</span>, <span class='ident'>si</span>: <span class='ident'>StateIdx</span>, <span class='ident'>i</span>: <span class='ident'>u8</span>) <span class='op'>-></span> <span class='ident'>StateIdx</span> { + <span class='self'>self</span>.<span class='ident'>trans</span>[<span class='ident'>i</span> <span class='kw'>as</span> <span class='ident'>usize</span> <span class='op'>*</span> <span class='self'>self</span>.<span class='ident'>num_states</span>() <span class='op'>+</span> <span class='ident'>si</span> <span class='kw'>as</span> <span class='ident'>usize</span>] + } + + <span class='attribute'>#[<span class='ident'>inline</span>]</span> + <span class='kw'>fn</span> <span class='ident'>get_match</span>(<span class='kw-2'>&</span><span class='self'>self</span>, <span class='ident'>si</span>: <span class='ident'>StateIdx</span>, <span class='ident'>outi</span>: <span class='ident'>usize</span>, <span class='ident'>texti</span>: <span class='ident'>usize</span>) <span class='op'>-></span> <span class='ident'>Match</span> { + <span class='kw'>let</span> <span class='ident'>pati</span> <span class='op'>=</span> <span class='self'>self</span>.<span class='ident'>out</span>[<span class='ident'>si</span> <span class='kw'>as</span> <span class='ident'>usize</span>][<span class='ident'>outi</span>]; + <span class='kw'>let</span> <span class='ident'>patlen</span> <span class='op'>=</span> <span class='self'>self</span>.<span class='ident'>pats</span>[<span class='ident'>pati</span>].<span class='ident'>len</span>(); + <span class='kw'>let</span> <span class='ident'>start</span> <span class='op'>=</span> <span class='ident'>texti</span> <span class='op'>+</span> <span class='number'>1</span> <span class='op'>-</span> <span class='ident'>patlen</span>; + <span class='ident'>Match</span> { + <span class='ident'>pati</span>: <span class='ident'>pati</span>, + <span class='ident'>start</span>: <span class='ident'>start</span>, + <span class='ident'>end</span>: <span class='ident'>start</span> <span class='op'>+</span> <span class='ident'>patlen</span>, + } + } + + <span class='attribute'>#[<span class='ident'>inline</span>]</span> + <span class='kw'>fn</span> <span class='ident'>has_match</span>(<span class='kw-2'>&</span><span class='self'>self</span>, <span class='ident'>si</span>: <span class='ident'>StateIdx</span>, <span class='ident'>outi</span>: <span class='ident'>usize</span>) <span class='op'>-></span> <span class='ident'>bool</span> { + <span class='ident'>outi</span> <span class='op'><</span> <span class='self'>self</span>.<span class='ident'>out</span>[<span class='ident'>si</span> <span class='kw'>as</span> <span class='ident'>usize</span>].<span class='ident'>len</span>() + } + + <span class='attribute'>#[<span class='ident'>inline</span>]</span> + <span class='kw'>fn</span> <span class='ident'>skip_to</span>(<span class='kw-2'>&</span><span class='self'>self</span>, <span class='ident'>si</span>: <span class='ident'>StateIdx</span>, <span class='ident'>text</span>: <span class='kw-2'>&</span>[<span class='ident'>u8</span>], <span class='ident'>at</span>: <span class='ident'>usize</span>) <span class='op'>-></span> <span class='ident'>usize</span> { + <span class='kw'>if</span> <span class='ident'>si</span> <span class='op'>!=</span> <span class='ident'>ROOT_STATE</span> <span class='op'>||</span> <span class='op'>!</span><span class='self'>self</span>.<span class='ident'>is_skippable</span>() { + <span class='kw'>return</span> <span class='ident'>at</span>; + } + <span class='kw'>let</span> <span class='ident'>b</span> <span class='op'>=</span> <span class='self'>self</span>.<span class='ident'>start_bytes</span>[<span class='number'>0</span>]; + <span class='kw'>match</span> <span class='ident'>memchr</span>(<span class='ident'>b</span>, <span class='kw-2'>&</span><span class='ident'>text</span>[<span class='ident'>at</span>..]) { + <span class='prelude-val'>None</span> <span class='op'>=></span> <span class='ident'>text</span>.<span class='ident'>len</span>(), + <span class='prelude-val'>Some</span>(<span class='ident'>i</span>) <span class='op'>=></span> <span class='ident'>at</span> <span class='op'>+</span> <span class='ident'>i</span>, + } + } + + <span class='attribute'>#[<span class='ident'>inline</span>]</span> + <span class='kw'>fn</span> <span class='ident'>is_skippable</span>(<span class='kw-2'>&</span><span class='self'>self</span>) <span class='op'>-></span> <span class='ident'>bool</span> { + <span class='self'>self</span>.<span class='ident'>start_bytes</span>.<span class='ident'>len</span>() <span class='op'>==</span> <span class='number'>1</span> + } + + <span class='attribute'>#[<span class='ident'>inline</span>]</span> + <span class='kw'>fn</span> <span class='ident'>patterns</span>(<span class='kw-2'>&</span><span class='self'>self</span>) <span class='op'>-></span> <span class='kw-2'>&</span>[<span class='ident'>String</span>] { + <span class='kw-2'>&</span><span class='self'>self</span>.<span class='ident'>pats</span> + } + + <span class='attribute'>#[<span class='ident'>inline</span>]</span> + <span class='kw'>fn</span> <span class='ident'>pattern</span>(<span class='kw-2'>&</span><span class='self'>self</span>, <span class='ident'>i</span>: <span class='ident'>usize</span>) <span class='op'>-></span> <span class='kw-2'>&</span><span class='ident'>str</span> { + <span class='kw-2'>&</span><span class='self'>self</span>.<span class='ident'>pats</span>[<span class='ident'>i</span>] + } +} + +<span class='kw'>impl</span> <span class='ident'>FullAcAutomaton</span> { + <span class='kw'>fn</span> <span class='ident'>build_matrix</span><span class='op'><</span><span class='ident'>T</span>: <span class='ident'>Transitions</span><span class='op'>></span>(<span class='kw-2'>&</span><span class='kw-2'>mut</span> <span class='self'>self</span>, <span class='ident'>ac</span>: <span class='kw-2'>&</span><span class='ident'>AcAutomaton</span><span class='op'><</span><span class='ident'>T</span><span class='op'>></span>) { + <span class='kw'>for</span> (<span class='ident'>si</span>, <span class='ident'>s</span>) <span class='kw'>in</span> <span class='ident'>ac</span>.<span class='ident'>states</span>.<span class='ident'>iter</span>().<span class='ident'>enumerate</span>().<span class='ident'>skip</span>(<span class='number'>1</span>) { + <span class='kw'>for</span> <span class='ident'>b</span> <span class='kw'>in</span> (<span class='number'>0</span>..<span class='number'>256</span>).<span class='ident'>map</span>(<span class='op'>|</span><span class='ident'>b</span><span class='op'>|</span> <span class='ident'>b</span> <span class='kw'>as</span> <span class='ident'>u8</span>) { + <span class='self'>self</span>.<span class='ident'>set</span>(<span class='ident'>si</span> <span class='kw'>as</span> <span class='ident'>StateIdx</span>, <span class='ident'>b</span>, <span class='ident'>ac</span>.<span class='ident'>next_state</span>(<span class='ident'>si</span> <span class='kw'>as</span> <span class='ident'>StateIdx</span>, <span class='ident'>b</span>)); + } + <span class='kw'>for</span> <span class='kw-2'>&</span><span class='ident'>pati</span> <span class='kw'>in</span> <span class='kw-2'>&</span><span class='ident'>s</span>.<span class='ident'>out</span> { + <span class='self'>self</span>.<span class='ident'>out</span>[<span class='ident'>si</span>].<span class='ident'>push</span>(<span class='ident'>pati</span>); + } + } + } +} +</pre> +</section> + <section id='search' class="content hidden"></section> + + <section class="footer"></section> + + <div id="help" class="hidden"> + <div class="shortcuts"> + <h1>Keyboard shortcuts</h1> + <dl> + <dt>?</dt> + <dd>Show this help dialog</dd> + <dt>S</dt> + <dd>Focus the search field</dd> + <dt>⇤</dt> + <dd>Move up in search results</dd> + <dt>⇥</dt> + <dd>Move down in search results</dd> + <dt>⏎</dt> + <dd>Go to active search result</dd> + </dl> + </div> + <div class="infos"> + <h1>Search tricks</h1> + <p> + Prefix searches with a type followed by a colon (e.g. + <code>fn:</code>) to restrict the search to a given type. + </p> + <p> + Accepted types are: <code>fn</code>, <code>mod</code>, + <code>struct</code>, <code>enum</code>, + <code>trait</code>, <code>typedef</code> (or + <code>tdef</code>). + </p> + <p> + Search functions by type signature (e.g. + <code>vec -> usize</code>) + </p> + </div> + </div> + + + + <script> + window.rootPath = "../../"; + window.currentCrate = "aho_corasick"; + window.playgroundUrl = ""; + </script> + <script src="../../jquery.js"></script> + <script src="../../main.js"></script> + + <script async src="../../search-index.js"></script> +</body> +</html>
\ No newline at end of file |