bitset-word8 (empty) → 0.1.0.0
raw patch · 10 files changed
+391/−0 lines, 10 filesdep +QuickCheckdep +basedep +bitset-word8setup-changed
Dependencies added: QuickCheck, base, bitset-word8, bytestring, containers, hspec, template-haskell, th-lift-instances
Files
- CHANGELOG.md +3/−0
- LICENSE +21/−0
- README.md +28/−0
- Setup.hs +2/−0
- bitset-word8.cabal +44/−0
- src/Data/BitSetWord8.hs +69/−0
- src/Data/BitSetWord8/CharSets.hs +44/−0
- src/Data/BitSetWord8/Internal.hs +133/−0
- test/Data/BitSetWord8Spec.hs +46/−0
- test/Spec.hs +1/−0
+ CHANGELOG.md view
@@ -0,0 +1,3 @@+## Bitset-word8 0.1.0.0++* Initial release.
+ LICENSE view
@@ -0,0 +1,21 @@+MIT License++Copyright (c) 2017 Naoto Shimazaki++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.
+ README.md view
@@ -0,0 +1,28 @@+# bitset-word8++[](https://opensource.org/licenses/MIT)+[](https://travis-ci.org/nshimaza/bitset-word8)+[](https://hackage.haskell.org/package/bitset-word8)++Space efficient set of `Word8` and some pre-canned sets useful for parsing HTTP related `ByteString`.+This packaged is intended to provide O(1) membership test on any subset of ASCII and Latin-1 character set+in order to write efficient HTTP related parser.++### Creating your own set++You can create your own set by `fromList`.++```haskell+myCharSet :: BitSetWord8+myCharSet = fromList [ 'Y', 'y', 'N', 'n' ]+```++You can create pre-evaluated set using Template Haskell.++```haskell+{-# LANGUAGE TemplateHaskell #-}+import Language.Haskell.TH.Syntax (Lift, lift)++myPreEvaluatedCharSet :: BitSetWord8+myPreEvaluatedCharSet = $(lift myCharSet)+```
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ bitset-word8.cabal view
@@ -0,0 +1,44 @@+name: bitset-word8+version: 0.1.0.0+synopsis: Space efficient set of Word8 and some pre-canned sets useful for parsing HTTP+description: This packaged is intended to provide O(1) membership test on any subset of ASCII+ and Latin-1 character set in order to write efficient HTTP related parser.+homepage: https://github.com/nshimaza/bitset-word8#readme+license: MIT+license-file: LICENSE+author: Naoto Shimazaki+maintainer: Naoto.Shimazaki@gmail.com+copyright: Copyright: (c) 2017 Naoto Shimazaki+category: Data+build-type: Simple+extra-source-files: CHANGELOG.md+ , README.md+cabal-version: >=1.10++library+ hs-source-dirs: src+ exposed-modules: Data.BitSetWord8+ , Data.BitSetWord8.CharSets+ , Data.BitSetWord8.Internal+ build-depends: base >= 4.7 && < 5+ , bytestring+ , containers+ , template-haskell+ , th-lift-instances+ default-language: Haskell2010++test-suite bitset-word8-test+ type: exitcode-stdio-1.0+ hs-source-dirs: test+ main-is: Spec.hs+ other-modules: Data.BitSetWord8Spec+ build-depends: base+ , hspec+ , QuickCheck+ , bitset-word8+ ghc-options: -threaded -rtsopts -with-rtsopts=-N+ default-language: Haskell2010++source-repository head+ type: git+ location: https://github.com/nshimaza/bitset-word8
+ src/Data/BitSetWord8.hs view
@@ -0,0 +1,69 @@+{-|+Module : Network.BitSetWord8+Copyright : (c) Naoto Shimazaki 2017+License : MIT (see the file LICENSE)++Maintainer : https://github.com/nshimaza+Stability : experimental++Space efficient set of 'Word8' and some pre-canned sets useful for parsing HTTP related 'ByteString'.+This packaged is intended to provide O(1) membership test on any subset of ASCII and Latin-1 character set+in order to write efficient HTTP related parser.++=== Creating your own set++You can create your own set by 'fromList'.++@+myCharSet :: BitSetWord8+myCharSet = fromList [ 'Y', 'y', 'N', 'n' ]+@++You can create pre-evaluated set using Template Haskell.++@+{-# LANGUAGE TemplateHaskell #-}+import Language.Haskell.TH.Syntax (Lift, lift)++myPreEvaluatedCharSet :: BitSetWord8+myPreEvaluatedCharSet = $(lift myCharSet)+@+-}++{-# LANGUAGE DeriveLift #-}++module Data.BitSetWord8+ (+ -- * Types+ BitSetWord8+ -- * Useful charset constants in BitSetWord8+ , rfc3986UriReference+ , rfc7230TChar+ , rfc7230QDText+ , rfc7230QuotedPair+ -- * Source Constants+ , rfc3986UriReference'+ , rfc7230QDText'+ , rfc7230QuotedPair'+ , rfc5234Digit'+ , rfc2616UpAlpha'+ , rfc2616LoAlpha'+ , rfc5234Alpha'+ , rfc5234HexDig'+ , rfc5234VChar'+ , rfc5324Wsp'+ , rfc3986SubDelims'+ , rfc3986GenDelims'+ , rfc3986Reserved'+ , rfc3986Unreserved'+ , rfc3986PctEncodedChar'+ , rfc3986PChar'+ , rfc7230TChar'+ , rfc7230ObsText'+ -- * Functions+ , fromList+ , member+ ) where++import Data.BitSetWord8.Internal+import Data.BitSetWord8.CharSets
+ src/Data/BitSetWord8/CharSets.hs view
@@ -0,0 +1,44 @@+{-|+Module : Network.BitSetWord8.CharSets+Copyright : (c) Naoto Shimazaki 2017+License : MIT (see the file LICENSE)++Maintainer : https://github.com/nshimaza+Stability : experimental++Some pre-canned character sets useful for HTTP related parsing.+All sets provided by this module are evaluated at compile time using Template Haskell.+-}++{-# LANGUAGE TemplateHaskell #-}++module Data.BitSetWord8.CharSets+ (+ rfc3986UriReference+ , rfc7230TChar+ , rfc7230QDText+ , rfc7230QuotedPair+ ) where++import Language.Haskell.TH.Syntax (Lift, lift)++import Data.BitSetWord8.Internal++-- | URI-Reference of RFC3986 in BitSetWord8. Evaluated at compile time.+rfc3986UriReference :: BitSetWord8+rfc3986UriReference = $(lift $ fromList rfc3986UriReference')++-- | tcher of RFC7230 in BitSetWord8. Evaluated at compile time.+rfc7230TChar :: BitSetWord8+rfc7230TChar = $(lift $ fromList rfc7230TChar')++-- | qdtext of RFC7230 in BitSetWord8. Evaluated at compile time.+rfc7230QDText :: BitSetWord8+rfc7230QDText = $(lift $ fromList rfc7230QDText')++-- | quoted-string of RFC7230 in BitSetWord8. Evaluated at compile time.+rfc7230QuotedPair :: BitSetWord8+rfc7230QuotedPair = $(lift $ fromList rfc7230QuotedPair')+++
+ src/Data/BitSetWord8/Internal.hs view
@@ -0,0 +1,133 @@+{-|+Module : Network.BitSetWord8.Internal+Copyright : (c) Naoto Shimazaki 2017+License : MIT (see the file LICENSE)++Maintainer : https://github.com/nshimaza+Stability : experimental++Space efficient set of 'Word8' and some pre-canned sets useful for parsing HTTP related 'ByteString'.+This file contains additional useful character sets but they aren't evaluated at compile time.+-}++{-# LANGUAGE DeriveLift #-}++module Data.BitSetWord8.Internal where++import Prelude hiding (zipWith)++import Data.Bits (setBit, shiftR, testBit)+import Data.ByteString (ByteString, index, pack, zipWith)+import Data.Char (chr, ord)+import Data.List (foldl', splitAt)+import Data.Monoid ((<>))+import qualified Data.Set as Set (Set, fromList, member)+import Data.Word (Word8)+import Instances.TH.Lift+import Language.Haskell.TH.Syntax (Lift)+++-- | Bitwise set of Word8. Space efficient backend and O(1) membership test.+newtype BitSetWord8 = BitSetWord8 ByteString deriving (Eq, Lift, Show)++-- | DIGIT of RFC5324 in 'Char' list.+rfc5234Digit' :: [Char]+rfc5234Digit' = ['0'..'9']++-- | UPALPHA of RFC2616 in 'Char' list.+-- Note that RFC2616 has been obsoleted by RFC7230 and RFC7230 doesn't define UPALPHA.+rfc2616UpAlpha' :: [Char]+rfc2616UpAlpha' = [ 'A'..'Z' ]++-- | LOALPHA of RFC2616 in 'Char' list.+-- Note that RFC2616 has been obsoleted by RFC7230 and RFC7230 doesn't define LOALPHA.+rfc2616LoAlpha' :: [Char]+rfc2616LoAlpha' = [ 'a'..'z' ]++-- | ALPHA of RFC5324 in 'Char' list.+rfc5234Alpha' :: [Char]+rfc5234Alpha' = rfc2616UpAlpha' <> rfc2616LoAlpha'++-- | HEXDIG of RFC5324 in 'Char' list.+rfc5234HexDig' :: [Char]+rfc5234HexDig' = rfc5234Digit' <> ['A'..'F']++-- | VCHAR of RFC5324 in 'Char' list.+rfc5234VChar' :: [Char]+rfc5234VChar' = [ '!'..'~']++-- | WSP (aka white space) of RFC5324 in 'Char' list.+rfc5324Wsp' :: [Char]+rfc5324Wsp' = [ '\t', ' ' ]++-- | sub-delim of RFC3986 in 'Char' list.+rfc3986SubDelims' :: [Char]+rfc3986SubDelims' = [ '!', '$', '&', '\'', '(', ')', '*', '+', ',', ';', '=' ]++-- | gen-delim of RFC3986 in 'Char' list.+rfc3986GenDelims' :: [Char]+rfc3986GenDelims' = [ ':', '/', '?', '#', '[', ']', '@']++-- | reserved of RFC3986 in 'Char' list.+rfc3986Reserved' :: [Char]+rfc3986Reserved' = rfc3986GenDelims' <> rfc3986SubDelims'++-- | unreserved of RFC3986 in 'Char' list.+rfc3986Unreserved' :: [Char]+rfc3986Unreserved' = rfc5234Alpha' <> rfc5234Digit' <> [ '-', '.', '_', '~' ]++-- | pct-encoded of RFC3986 in 'Char' list.+rfc3986PctEncodedChar' :: [Char]+rfc3986PctEncodedChar' = ['%'] <> rfc5234HexDig'++-- | pchar of RFC3986 in 'Char' list.+rfc3986PChar' :: [Char]+rfc3986PChar' = rfc3986Unreserved' <> rfc3986PctEncodedChar' <> rfc3986SubDelims' <> [':', '@']++-- | URI-Reference of RFC3986 in 'Char' list.+rfc3986UriReference' :: [Char]+rfc3986UriReference' = rfc3986Reserved' <> rfc3986Unreserved' <> ['%']++-- | tchar of RFC7230 in 'Char' list.+rfc7230TChar' :: [Char]+rfc7230TChar' = [ '!', '#', '$', '%', '&', '\'', '*', '+', '-', '.', '^', '_', '`', '|', '~' ]+ <> rfc5234Digit' <> rfc5234Alpha'++-- | obs-text of RFC7230 in 'Char' list.+rfc7230ObsText' :: [Char]+rfc7230ObsText' = [ chr 0x80 .. chr 0xff]++-- | qdtext of RFC7230 in 'Char' list.+rfc7230QDText' :: [Char]+rfc7230QDText' = rfc5324Wsp' <> [ '!' ] <> [ '#' .. '[' ] <> [ ']' .. '~'] <> rfc7230ObsText'++-- | quoted-pair of RFC7230 in 'Char' list.+rfc7230QuotedPair' :: [Char]+rfc7230QuotedPair' = rfc5324Wsp' <> rfc5234VChar' <> rfc7230ObsText'++-- | O(1). Return 'True' if given 'Word8' is a member of given 'BitSetWord8'.+member :: BitSetWord8 -> Word8 -> Bool+member (BitSetWord8 bs) w = testBit (index bs (fromIntegral (w `div` 8))) (fromIntegral (w `mod` 8))++-- | Convert given list of 'Char' into 'Set' of 'Word8'. Any 'Char' having code point greater than 0xff is ignored.+toWord8Set :: [Char] -> Set.Set Word8+toWord8Set = Set.fromList . map fromIntegral . filter (<= fromIntegral (maxBound :: Word8)) . map ord++-- | Convert 'Set' of Word8 to full filled list of boolean existence flag.+toBoolList :: Set.Set Word8 -> [Bool]+toBoolList wSet = map (\w -> Set.member w wSet) [0..0xff]++-- | Pack 8 of boolean list into single 'Word8' bitwise set.+toWord8 :: [Bool] -> Word8+toWord8 = foldl' (\a e -> let aL = shiftR a 1 in if e == True then setBit aL 7 else aL) 0++-- | Convert full filled boolean list into 32 packed 'Word8' list.+toWord8List :: [Bool] -> [Word8]+toWord8List [] = []+toWord8List bs = let (bs8, rest) = splitAt 8 bs in toWord8 bs8 : toWord8List rest++-- | Convert given List of 'Char' into packed bitwise set of Word8.+-- Any 'Char' having code point greater than 0xff is ignored.+fromList :: [Char] -> BitSetWord8+fromList = BitSetWord8 . pack . toWord8List . toBoolList . toWord8Set+
+ test/Data/BitSetWord8Spec.hs view
@@ -0,0 +1,46 @@+module Data.BitSetWord8Spec where++import Data.Char (chr)+import Data.Word (Word8)++import Test.Hspec+import Test.Hspec.QuickCheck (prop)+import Test.QuickCheck++import Data.BitSetWord8++spec :: Spec+spec = do+ describe "fromList" $ do+ prop "creates empty BitSetWord8 from empty list" $ forAll (choose (0, 0xff :: Word8)) $ \n -> do+ member (fromList []) n `shouldBe` False++ prop "creates fullfilled BitSetWord8 from fullfilled list" $ forAll (choose (0, 0xff :: Word8)) $ \n -> do+ member (fromList [chr 0 .. chr 0xff]) n `shouldBe` True++ describe "rfc5234Digit'" $ do+ prop "recognizes any digit" $ forAll (choose (0x30, 0x39 :: Word8)) $ \n -> do+ member (fromList rfc5234Digit') n `shouldBe` True++ prop "unrecognizes any non-digit characters (lower)" $ forAll (choose (0, 0x2f :: Word8)) $ \n -> do+ member (fromList rfc5234Digit') n `shouldBe` False++ prop "unrecognizes any non-digit characters (higher)" $ forAll (choose (0x3a, 0xff :: Word8)) $ \n -> do+ member (fromList rfc5234Digit') n `shouldBe` False++ describe "rfc5234Alpha'" $ do+ prop "recognizes any upper case alphabet" $ forAll (choose (0x41, 0x5a :: Word8)) $ \n -> do+ member (fromList rfc5234Alpha') n `shouldBe` True++ prop "recognizes any lower case alphabet" $ forAll (choose (0x61, 0x7a :: Word8)) $ \n -> do+ member (fromList rfc5234Alpha') n `shouldBe` True++ prop "unrecognizes any non-alphabet (lower)" $ forAll (choose (0, 0x40 :: Word8)) $ \n -> do+ member (fromList rfc5234Alpha') n `shouldBe` False++ prop "unrecognizes any non-alphabet (middle)" $ forAll (choose (0x5b, 0x60 :: Word8)) $ \n -> do+ member (fromList rfc5234Alpha') n `shouldBe` False++ prop "unrecognizes any non-alphabet (higher)" $ forAll (choose (0x7b, 0xff :: Word8)) $ \n -> do+ member (fromList rfc5234Alpha') n `shouldBe` False+
+ test/Spec.hs view
@@ -0,0 +1,1 @@+{-# OPTIONS_GHC -F -pgmF hspec-discover #-}