/usr/share/doc/libghc-text-doc/html/src/Data-Text-Internal-Lazy-Search.html is in libghc-text-doc 1.2.2.2-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | <?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<head>
<!-- Generated by HsColour, http://code.haskell.org/~malcolm/hscolour/ -->
<title>Data/Text/Internal/Lazy/Search.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-comment'>{-# LANGUAGE BangPatterns, ScopedTypeVariables #-}</span>
<a name="line-2"></a>
<a name="line-3"></a><span class='hs-comment'>-- |</span>
<a name="line-4"></a><span class='hs-comment'>-- Module : Data.Text.Lazy.Search</span>
<a name="line-5"></a><span class='hs-comment'>-- Copyright : (c) 2009, 2010 Bryan O'Sullivan</span>
<a name="line-6"></a><span class='hs-comment'>--</span>
<a name="line-7"></a><span class='hs-comment'>-- License : BSD-style</span>
<a name="line-8"></a><span class='hs-comment'>-- Maintainer : bos@serpentine.com</span>
<a name="line-9"></a><span class='hs-comment'>-- Stability : experimental</span>
<a name="line-10"></a><span class='hs-comment'>-- Portability : GHC</span>
<a name="line-11"></a><span class='hs-comment'>--</span>
<a name="line-12"></a><span class='hs-comment'>-- /Warning/: this is an internal module, and does not have a stable</span>
<a name="line-13"></a><span class='hs-comment'>-- API or name. Functions in this module may not check or enforce</span>
<a name="line-14"></a><span class='hs-comment'>-- preconditions expected by public modules. Use at your own risk!</span>
<a name="line-15"></a><span class='hs-comment'>--</span>
<a name="line-16"></a><span class='hs-comment'>-- Fast substring search for lazy 'Text', based on work by Boyer,</span>
<a name="line-17"></a><span class='hs-comment'>-- Moore, Horspool, Sunday, and Lundh. Adapted from the strict</span>
<a name="line-18"></a><span class='hs-comment'>-- implementation.</span>
<a name="line-19"></a>
<a name="line-20"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>Internal</span><span class='hs-varop'>.</span><span class='hs-conid'>Lazy</span><span class='hs-varop'>.</span><span class='hs-conid'>Search</span>
<a name="line-21"></a> <span class='hs-layout'>(</span>
<a name="line-22"></a> <span class='hs-varid'>indices</span>
<a name="line-23"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-24"></a>
<a name="line-25"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>Array</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>A</span>
<a name="line-26"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Int</span> <span class='hs-layout'>(</span><span class='hs-conid'>Int64</span><span class='hs-layout'>)</span>
<a name="line-27"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Word</span> <span class='hs-layout'>(</span><span class='hs-conid'>Word16</span><span class='hs-layout'>,</span> <span class='hs-conid'>Word64</span><span class='hs-layout'>)</span>
<a name="line-28"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>Internal</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>T</span>
<a name="line-29"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>Internal</span><span class='hs-varop'>.</span><span class='hs-conid'>Fusion</span><span class='hs-varop'>.</span><span class='hs-conid'>Types</span> <span class='hs-layout'>(</span><span class='hs-conid'>PairS</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-30"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>Internal</span><span class='hs-varop'>.</span><span class='hs-conid'>Lazy</span> <span class='hs-layout'>(</span><span class='hs-conid'>Text</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>foldlChunks</span><span class='hs-layout'>)</span>
<a name="line-31"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Bits</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varop'>.|.</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-layout'>(</span><span class='hs-varop'>.&.</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-32"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span><span class='hs-varop'>.</span><span class='hs-conid'>Internal</span><span class='hs-varop'>.</span><span class='hs-conid'>Unsafe</span><span class='hs-varop'>.</span><span class='hs-conid'>Shift</span> <span class='hs-layout'>(</span><span class='hs-varid'>shiftL</span><span class='hs-layout'>)</span>
<a name="line-33"></a>
<a name="line-34"></a><a name="indices"></a><span class='hs-comment'>-- | /O(n+m)/ Find the offsets of all non-overlapping indices of</span>
<a name="line-35"></a><span class='hs-comment'>-- @needle@ within @haystack@.</span>
<a name="line-36"></a><span class='hs-comment'>--</span>
<a name="line-37"></a><span class='hs-comment'>-- This function is strict in @needle@, and lazy (as far as possible)</span>
<a name="line-38"></a><span class='hs-comment'>-- in the chunks of @haystack@.</span>
<a name="line-39"></a><span class='hs-comment'>--</span>
<a name="line-40"></a><span class='hs-comment'>-- In (unlikely) bad cases, this algorithm's complexity degrades</span>
<a name="line-41"></a><span class='hs-comment'>-- towards /O(n*m)/.</span>
<a name="line-42"></a><span class='hs-definition'>indices</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Text</span> <span class='hs-comment'>-- ^ Substring to search for (@needle@)</span>
<a name="line-43"></a> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Text</span> <span class='hs-comment'>-- ^ Text to search in (@haystack@)</span>
<a name="line-44"></a> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Int64</span><span class='hs-keyglyph'>]</span>
<a name="line-45"></a><span class='hs-definition'>indices</span> <span class='hs-varid'>needle</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Chunk</span> <span class='hs-varid'>n</span> <span class='hs-varid'>ns</span><span class='hs-layout'>)</span> <span class='hs-sel'>_haystack</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>Chunk</span> <span class='hs-varid'>k</span> <span class='hs-varid'>ks</span><span class='hs-layout'>)</span>
<a name="line-46"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>nlen</span> <span class='hs-varop'><=</span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-47"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>nlen</span> <span class='hs-varop'>==</span> <span class='hs-num'>1</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>indicesOne</span> <span class='hs-layout'>(</span><span class='hs-varid'>nindex</span> <span class='hs-num'>0</span><span class='hs-layout'>)</span> <span class='hs-num'>0</span> <span class='hs-varid'>k</span> <span class='hs-varid'>ks</span>
<a name="line-48"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>advance</span> <span class='hs-varid'>k</span> <span class='hs-varid'>ks</span> <span class='hs-num'>0</span> <span class='hs-num'>0</span>
<a name="line-49"></a> <span class='hs-keyword'>where</span>
<a name="line-50"></a> <span class='hs-varid'>advance</span> <span class='hs-varid'>x</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-conid'>T</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>scan</span>
<a name="line-51"></a> <span class='hs-keyword'>where</span>
<a name="line-52"></a> <span class='hs-varid'>scan</span> <span class='hs-varop'>!</span><span class='hs-varid'>g</span> <span class='hs-varop'>!</span><span class='hs-varid'>i</span>
<a name="line-53"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span> <span class='hs-varop'>>=</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>xs</span> <span class='hs-keyword'>of</span>
<a name="line-54"></a> <span class='hs-conid'>Empty</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>[]</span>
<a name="line-55"></a> <span class='hs-conid'>Chunk</span> <span class='hs-varid'>y</span> <span class='hs-varid'>ys</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>advance</span> <span class='hs-varid'>y</span> <span class='hs-varid'>ys</span> <span class='hs-varid'>g</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-comment'>-</span><span class='hs-varid'>m</span><span class='hs-layout'>)</span>
<a name="line-56"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>lackingHay</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span> <span class='hs-varop'>+</span> <span class='hs-varid'>nlen</span><span class='hs-layout'>)</span> <span class='hs-varid'>x</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-57"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>c</span> <span class='hs-varop'>==</span> <span class='hs-varid'>z</span> <span class='hs-varop'>&&</span> <span class='hs-varid'>candidateMatch</span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>g</span> <span class='hs-conop'>:</span> <span class='hs-varid'>scan</span> <span class='hs-layout'>(</span><span class='hs-varid'>g</span><span class='hs-varop'>+</span><span class='hs-varid'>nlen</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-varop'>+</span><span class='hs-varid'>nlen</span><span class='hs-layout'>)</span>
<a name="line-58"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>scan</span> <span class='hs-layout'>(</span><span class='hs-varid'>g</span><span class='hs-varop'>+</span><span class='hs-varid'>delta</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-varop'>+</span><span class='hs-varid'>delta</span><span class='hs-layout'>)</span>
<a name="line-59"></a> <span class='hs-keyword'>where</span>
<a name="line-60"></a> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fromIntegral</span> <span class='hs-varid'>l</span>
<a name="line-61"></a> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>hindex</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span> <span class='hs-varop'>+</span> <span class='hs-varid'>nlast</span><span class='hs-layout'>)</span>
<a name="line-62"></a> <span class='hs-varid'>delta</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>nextInPattern</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>nlen</span> <span class='hs-varop'>+</span> <span class='hs-num'>1</span>
<a name="line-63"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>c</span> <span class='hs-varop'>==</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>skip</span> <span class='hs-varop'>+</span> <span class='hs-num'>1</span>
<a name="line-64"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>1</span>
<a name="line-65"></a> <span class='hs-varid'>nextInPattern</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mask</span> <span class='hs-varop'>.&.</span> <span class='hs-varid'>swizzle</span> <span class='hs-layout'>(</span><span class='hs-varid'>hindex</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-varop'>+</span><span class='hs-varid'>nlen</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-varop'>==</span> <span class='hs-num'>0</span>
<a name="line-66"></a> <span class='hs-varid'>candidateMatch</span> <span class='hs-varop'>!</span><span class='hs-varid'>j</span>
<a name="line-67"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>j</span> <span class='hs-varop'>>=</span> <span class='hs-varid'>nlast</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span>
<a name="line-68"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>hindex</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-varop'>+</span><span class='hs-varid'>j</span><span class='hs-layout'>)</span> <span class='hs-varop'>/=</span> <span class='hs-varid'>nindex</span> <span class='hs-varid'>j</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span>
<a name="line-69"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>candidateMatch</span> <span class='hs-layout'>(</span><span class='hs-varid'>j</span><span class='hs-varop'>+</span><span class='hs-num'>1</span><span class='hs-layout'>)</span>
<a name="line-70"></a> <span class='hs-varid'>hindex</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>index</span> <span class='hs-varid'>x</span> <span class='hs-varid'>xs</span>
<a name="line-71"></a> <span class='hs-varid'>nlen</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>wordLength</span> <span class='hs-varid'>needle</span>
<a name="line-72"></a> <span class='hs-varid'>nlast</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>nlen</span> <span class='hs-comment'>-</span> <span class='hs-num'>1</span>
<a name="line-73"></a> <span class='hs-varid'>nindex</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>index</span> <span class='hs-varid'>n</span> <span class='hs-varid'>ns</span>
<a name="line-74"></a> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldlChunks</span> <span class='hs-varid'>fin</span> <span class='hs-num'>0</span> <span class='hs-varid'>needle</span>
<a name="line-75"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>fin</span> <span class='hs-keyword'>_</span> <span class='hs-layout'>(</span><span class='hs-conid'>T</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span> <span class='hs-varid'>farr</span> <span class='hs-varid'>foff</span> <span class='hs-varid'>flen</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>A</span><span class='hs-varop'>.</span><span class='hs-varid'>unsafeIndex</span> <span class='hs-varid'>farr</span> <span class='hs-layout'>(</span><span class='hs-varid'>foff</span><span class='hs-varop'>+</span><span class='hs-varid'>flen</span><span class='hs-comment'>-</span><span class='hs-num'>1</span><span class='hs-layout'>)</span>
<a name="line-76"></a> <span class='hs-layout'>(</span><span class='hs-varid'>mask</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Word64</span><span class='hs-layout'>)</span> <span class='hs-conop'>:*:</span> <span class='hs-varid'>skip</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>buildTable</span> <span class='hs-varid'>n</span> <span class='hs-varid'>ns</span> <span class='hs-num'>0</span> <span class='hs-num'>0</span> <span class='hs-num'>0</span> <span class='hs-layout'>(</span><span class='hs-varid'>nlen</span><span class='hs-comment'>-</span><span class='hs-num'>2</span><span class='hs-layout'>)</span>
<a name="line-77"></a> <span class='hs-varid'>swizzle</span> <span class='hs-varid'>w</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>1</span> <span class='hs-varop'>`shiftL`</span> <span class='hs-layout'>(</span><span class='hs-varid'>fromIntegral</span> <span class='hs-varid'>w</span> <span class='hs-varop'>.&.</span> <span class='hs-num'>0x3f</span><span class='hs-layout'>)</span>
<a name="line-78"></a> <span class='hs-varid'>buildTable</span> <span class='hs-layout'>(</span><span class='hs-conid'>T</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span> <span class='hs-varid'>xarr</span> <span class='hs-varid'>xoff</span> <span class='hs-varid'>xlen</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span>
<a name="line-79"></a> <span class='hs-keyword'>where</span>
<a name="line-80"></a> <span class='hs-varid'>go</span> <span class='hs-varop'>!</span><span class='hs-layout'>(</span><span class='hs-varid'>g</span><span class='hs-keyglyph'>::</span><span class='hs-conid'>Int64</span><span class='hs-layout'>)</span> <span class='hs-varop'>!</span><span class='hs-varid'>i</span> <span class='hs-varop'>!</span><span class='hs-varid'>msk</span> <span class='hs-varop'>!</span><span class='hs-varid'>skp</span>
<a name="line-81"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>i</span> <span class='hs-varop'>>=</span> <span class='hs-varid'>xlast</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>xs</span> <span class='hs-keyword'>of</span>
<a name="line-82"></a> <span class='hs-conid'>Empty</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>msk</span> <span class='hs-varop'>.|.</span> <span class='hs-varid'>swizzle</span> <span class='hs-varid'>z</span><span class='hs-layout'>)</span> <span class='hs-conop'>:*:</span> <span class='hs-varid'>skp</span>
<a name="line-83"></a> <span class='hs-conid'>Chunk</span> <span class='hs-varid'>y</span> <span class='hs-varid'>ys</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>buildTable</span> <span class='hs-varid'>y</span> <span class='hs-varid'>ys</span> <span class='hs-varid'>g</span> <span class='hs-num'>0</span> <span class='hs-varid'>msk'</span> <span class='hs-varid'>skp'</span>
<a name="line-84"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-varid'>g</span><span class='hs-varop'>+</span><span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-varop'>+</span><span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>msk'</span> <span class='hs-varid'>skp'</span>
<a name="line-85"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>A</span><span class='hs-varop'>.</span><span class='hs-varid'>unsafeIndex</span> <span class='hs-varid'>xarr</span> <span class='hs-layout'>(</span><span class='hs-varid'>xoff</span><span class='hs-varop'>+</span><span class='hs-varid'>i</span><span class='hs-layout'>)</span>
<a name="line-86"></a> <span class='hs-varid'>msk'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>msk</span> <span class='hs-varop'>.|.</span> <span class='hs-varid'>swizzle</span> <span class='hs-varid'>c</span>
<a name="line-87"></a> <span class='hs-varid'>skp'</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>c</span> <span class='hs-varop'>==</span> <span class='hs-varid'>z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>nlen</span> <span class='hs-comment'>-</span> <span class='hs-varid'>g</span> <span class='hs-comment'>-</span> <span class='hs-num'>2</span>
<a name="line-88"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>skp</span>
<a name="line-89"></a> <span class='hs-varid'>xlast</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>xlen</span> <span class='hs-comment'>-</span> <span class='hs-num'>1</span>
<a name="line-90"></a> <span class='hs-comment'>-- | Check whether an attempt to index into the haystack at the</span>
<a name="line-91"></a> <span class='hs-comment'>-- given offset would fail.</span>
<a name="line-92"></a> <span class='hs-varid'>lackingHay</span> <span class='hs-varid'>q</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-num'>0</span>
<a name="line-93"></a> <span class='hs-keyword'>where</span>
<a name="line-94"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>p</span> <span class='hs-layout'>(</span><span class='hs-conid'>T</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-varid'>ps</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>p'</span> <span class='hs-varop'><</span> <span class='hs-varid'>q</span> <span class='hs-varop'>&&</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>ps</span> <span class='hs-keyword'>of</span>
<a name="line-95"></a> <span class='hs-conid'>Empty</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>True</span>
<a name="line-96"></a> <span class='hs-conid'>Chunk</span> <span class='hs-varid'>r</span> <span class='hs-varid'>rs</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>go</span> <span class='hs-varid'>p'</span> <span class='hs-varid'>r</span> <span class='hs-varid'>rs</span>
<a name="line-97"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>p'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>p</span> <span class='hs-varop'>+</span> <span class='hs-varid'>fromIntegral</span> <span class='hs-varid'>l</span>
<a name="line-98"></a><span class='hs-definition'>indices</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span>
<a name="line-99"></a>
<a name="line-100"></a><a name="index"></a><span class='hs-comment'>-- | Fast index into a partly unpacked 'Text'. We take into account</span>
<a name="line-101"></a><span class='hs-comment'>-- the possibility that the caller might try to access one element</span>
<a name="line-102"></a><span class='hs-comment'>-- past the end.</span>
<a name="line-103"></a><span class='hs-definition'>index</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>T</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Text</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int64</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Word16</span>
<a name="line-104"></a><span class='hs-definition'>index</span> <span class='hs-layout'>(</span><span class='hs-conid'>T</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span> <span class='hs-varid'>arr</span> <span class='hs-varid'>off</span> <span class='hs-varid'>len</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span> <span class='hs-varop'>!</span><span class='hs-varid'>i</span>
<a name="line-105"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>j</span> <span class='hs-varop'><</span> <span class='hs-varid'>len</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>A</span><span class='hs-varop'>.</span><span class='hs-varid'>unsafeIndex</span> <span class='hs-varid'>arr</span> <span class='hs-layout'>(</span><span class='hs-varid'>off</span><span class='hs-varop'>+</span><span class='hs-varid'>j</span><span class='hs-layout'>)</span>
<a name="line-106"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>xs</span> <span class='hs-keyword'>of</span>
<a name="line-107"></a> <span class='hs-conid'>Empty</span>
<a name="line-108"></a> <span class='hs-comment'>-- out of bounds, but legal</span>
<a name="line-109"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>j</span> <span class='hs-varop'>==</span> <span class='hs-varid'>len</span> <span class='hs-keyglyph'>-></span> <span class='hs-num'>0</span>
<a name="line-110"></a> <span class='hs-comment'>-- should never happen, due to lackingHay above</span>
<a name="line-111"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>emptyError</span> <span class='hs-str'>"index"</span>
<a name="line-112"></a> <span class='hs-conid'>Chunk</span> <span class='hs-varid'>c</span> <span class='hs-varid'>cs</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>index</span> <span class='hs-varid'>c</span> <span class='hs-varid'>cs</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-comment'>-</span><span class='hs-varid'>fromIntegral</span> <span class='hs-varid'>len</span><span class='hs-layout'>)</span>
<a name="line-113"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>j</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fromIntegral</span> <span class='hs-varid'>i</span>
<a name="line-114"></a>
<a name="line-115"></a><a name="indicesOne"></a><span class='hs-comment'>-- | A variant of 'indices' that scans linearly for a single 'Word16'.</span>
<a name="line-116"></a><span class='hs-definition'>indicesOne</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Word16</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int64</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>T</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Text</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Int64</span><span class='hs-keyglyph'>]</span>
<a name="line-117"></a><span class='hs-definition'>indicesOne</span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>chunk</span>
<a name="line-118"></a> <span class='hs-keyword'>where</span>
<a name="line-119"></a> <span class='hs-varid'>chunk</span> <span class='hs-varop'>!</span><span class='hs-varid'>i</span> <span class='hs-layout'>(</span><span class='hs-conid'>T</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span> <span class='hs-varid'>oarr</span> <span class='hs-varid'>ooff</span> <span class='hs-varid'>olen</span><span class='hs-layout'>)</span> <span class='hs-varid'>os</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-num'>0</span>
<a name="line-120"></a> <span class='hs-keyword'>where</span>
<a name="line-121"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>h</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>h</span> <span class='hs-varop'>>=</span> <span class='hs-varid'>olen</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>case</span> <span class='hs-varid'>os</span> <span class='hs-keyword'>of</span>
<a name="line-122"></a> <span class='hs-conid'>Empty</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>[]</span>
<a name="line-123"></a> <span class='hs-conid'>Chunk</span> <span class='hs-varid'>y</span> <span class='hs-varid'>ys</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>chunk</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-varop'>+</span><span class='hs-varid'>fromIntegral</span> <span class='hs-varid'>olen</span><span class='hs-layout'>)</span> <span class='hs-varid'>y</span> <span class='hs-varid'>ys</span>
<a name="line-124"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>on</span> <span class='hs-varop'>==</span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>i</span> <span class='hs-varop'>+</span> <span class='hs-varid'>fromIntegral</span> <span class='hs-varid'>h</span> <span class='hs-conop'>:</span> <span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-varid'>h</span><span class='hs-varop'>+</span><span class='hs-num'>1</span><span class='hs-layout'>)</span>
<a name="line-125"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-varid'>h</span><span class='hs-varop'>+</span><span class='hs-num'>1</span><span class='hs-layout'>)</span>
<a name="line-126"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>on</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>A</span><span class='hs-varop'>.</span><span class='hs-varid'>unsafeIndex</span> <span class='hs-varid'>oarr</span> <span class='hs-layout'>(</span><span class='hs-varid'>ooff</span><span class='hs-varop'>+</span><span class='hs-varid'>h</span><span class='hs-layout'>)</span>
<a name="line-127"></a>
<a name="line-128"></a><a name="wordLength"></a><span class='hs-comment'>-- | The number of 'Word16' values in a 'Text'.</span>
<a name="line-129"></a><span class='hs-definition'>wordLength</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Text</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Int64</span>
<a name="line-130"></a><span class='hs-definition'>wordLength</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>foldlChunks</span> <span class='hs-varid'>sumLength</span> <span class='hs-num'>0</span>
<a name="line-131"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>sumLength</span> <span class='hs-varid'>i</span> <span class='hs-layout'>(</span><span class='hs-conid'>T</span><span class='hs-varop'>.</span><span class='hs-conid'>Text</span> <span class='hs-keyword'>_</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>l</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>i</span> <span class='hs-varop'>+</span> <span class='hs-varid'>fromIntegral</span> <span class='hs-varid'>l</span>
<a name="line-132"></a>
<a name="line-133"></a><a name="emptyError"></a><span class='hs-definition'>emptyError</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span>
<a name="line-134"></a><span class='hs-definition'>emptyError</span> <span class='hs-varid'>fun</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>error</span> <span class='hs-layout'>(</span><span class='hs-str'>"Data.Text.Lazy.Search."</span> <span class='hs-varop'>++</span> <span class='hs-varid'>fun</span> <span class='hs-varop'>++</span> <span class='hs-str'>": empty input"</span><span class='hs-layout'>)</span>
</pre></body>
</html>
|