web-routing 0.1.2 → 0.2.0
raw patch · 8 files changed
+295/−214 lines, 8 filesdep +criteriondep +primitivedep +web-routingdep −tastydep −tasty-quickcheckdep ~text
Dependencies added: criterion, primitive, web-routing
Dependencies removed: tasty, tasty-quickcheck
Dependency ranges changed: text
Files
- bench/main.hs +65/−0
- src/Network/Routing.hs +39/−25
- src/Network/Routing/Dict.hs +9/−125
- src/Network/Routing/Dict/Internal.hs +171/−0
- src/Network/Routing/Tree.hs +0/−30
- tests/Tree.hs +0/−16
- tests/tasty.hs +0/−7
- web-routing.cabal +11/−11
+ bench/main.hs view
@@ -0,0 +1,65 @@+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE OverloadedStrings #-}+{-# LANGUAGE TypeOperators #-}+{-# LANGUAGE NoMonomorphismRestriction #-}++import Control.Monad+import Data.Proxy+import qualified Data.Text as T+import Data.Text.Read(decimal)+import Network.Routing+import Criterion.Main++p0 :: Proxy "0"; p0 = Proxy+p1 :: Proxy "1"; p1 = Proxy+p2 :: Proxy "2"; p2 = Proxy+p3 :: Proxy "3"; p3 = Proxy+p4 :: Proxy "4"; p4 = Proxy+p5 :: Proxy "5"; p5 = Proxy+p6 :: Proxy "6"; p6 = Proxy+p7 :: Proxy "7"; p7 = Proxy+p8 :: Proxy "8"; p8 = Proxy+p9 :: Proxy "9"; p9 = Proxy+p10 :: Proxy "10"; p10 = Proxy+p11 :: Proxy "11"; p11 = Proxy+p12 :: Proxy "12"; p12 = Proxy+p13 :: Proxy "13"; p13 = Proxy+p14 :: Proxy "14"; p14 = Proxy+p15 :: Proxy "15"; p15 = Proxy+p16 :: Proxy "16"; p16 = Proxy+p17 :: Proxy "17"; p17 = Proxy+p18 :: Proxy "18"; p18 = Proxy+p19 :: Proxy "19"; p19 = Proxy++readInt :: T.Text -> Maybe Int+readInt t = case decimal t of+ Right (i, "") -> Just i+ _ -> Nothing++test :: Path '[] Maybe Int+test = root $ exact "foo" $+ r p0 $ r p1 $ r p2 $ r p3 $ r p4 $+ r p5 $ r p6 $ r p7 $ r p8 $ r p9 $+ r p10 $ r p11 $ r p12 $ r p13 $ r p14 $+ r p15 $ r p16 $ r p17 $ r p18 $ r p19 $+ action Nothing $ \d -> Just $+ get p0 d + get p1 d + get p2 d + get p3 d + get p4 d ++ get p5 d + get p6 d + get p7 d + get p8 d + get p9 d ++ get p10 d + get p11 d + get p12 d + get p13 d + get p14 d ++ get p15 d + get p16 d + get p17 d + get p18 d + get p19 d+ where+ r p = fetch p readInt++route :: Router '[] Maybe Int+route = test +| empty++testPath :: [T.Text]+testPath = "foo" : map (T.pack . show) [0..19::Int]++main :: IO ()+main = do+ unless ((execute route "GET") testPath == Just 190) $+ fail "result not matched"+ defaultMain+ [ bench "routing" $ nf (execute route "GET") testPath+ ]
src/Network/Routing.hs view
@@ -7,18 +7,22 @@ {-# LANGUAGE DataKinds #-} {-# LANGUAGE GADTs #-} --- | >>> :set -XDataKinds -XOverloadedStrings -XNoMonomorphismRestriction--- >>> import Data.Proxy (Proxy(..))+-- | >>> :set -XDataKinds -XPolyKinds -XOverloadedStrings+-- >>> data Proxy s = Proxy -- >>> import Text.Read(readMaybe) -- >>> import qualified Data.Text as T -- -- 1. create path ----- >>> data Result = A | B T.Text | C | D Int deriving Show+-- >>> data Result = A | B T.Text | C | D Int | E T.Text deriving Show+--+-- >>> let key = Proxy :: Proxy "key"+-- -- >>> let a = root $ exact "foo" $ action Nothing (\_ -> Just A)--- >>> let b = root $ exact "bar" $ fetch (Proxy :: Proxy "key") Just $ action Nothing (\d -> Just . B $ D.get (Proxy :: Proxy "key") d)+-- >>> let b = root $ exact "bar" $ fetch key Just $ action Nothing (\d -> Just . B $ D.get key d) -- >>> let c = root $ exact "bar" $ any $ action (Just "GET") (\_ -> Just C)--- >>> let d = root $ exact "bar" $ fetch (Proxy :: Proxy "key") (\t -> readMaybe (T.unpack t) :: Maybe Int) $ action Nothing (\d -> Just . D $ D.get (Proxy :: Proxy "key") d)+-- >>> let d = root $ exact "bar" $ fetch key (\t -> readMaybe (T.unpack t) :: Maybe Int) $ action Nothing (\d -> Just . D $ D.get key d)+-- >>> let e = root $ exact "foo" $ fetch key Just $ exact "qux" $ action (Just "POST") (\d -> Just . E $ D.get key d) -- >>> a -- * /foo -- >>> b@@ -27,10 +31,12 @@ -- GET /bar/** -- >>> d -- * /bar/:key+-- >>> e+-- POST /foo/:key/qux -- -- 2. create router ----- >>> let r = d +| a +| b +| c +| empty+-- >>> let r = e +| d +| a +| b +| c +| empty -- -- 3. execute router --@@ -48,18 +54,21 @@ -- Just C -- >>> run "POST" ["bar", "baz", "qux"] -- Nothing+-- >>> run "POST" ["foo", "bar", "baz"]+-- Nothing+-- >>> run "POST" ["foo", "bar", "qux"]+-- Just (E "bar") module Network.Routing ( Method -- * Path , Path- -- ** Path constructors , root- -- *** children+ -- ** children , exact- -- *** action+ -- ** action , action- -- *** get parameter+ -- ** get parameter , Raw , raw , fetch@@ -69,26 +78,31 @@ -- * Router , Router , empty- , add, (+|)+ , insert, (+|) -- * execute , execute++ -- * reexport+ , module Network.Routing.Dict ) where import Prelude hiding(any) import Control.Monad(MonadPlus(..)) import Network.Routing.Compat(KnownSymbol, symbolVal)-import qualified Network.Routing.Dict as D+import qualified Network.Routing.Dict.Internal as D import qualified Data.Text as T import qualified Data.HashMap.Strict as H import qualified Data.ByteString as S import qualified Data.ByteString.Char8 as SC +import Network.Routing.Dict+ type Method = S.ByteString data Params d m a where- PCons :: (D.Dict d -> [T.Text] -> m (D.Dict d', [T.Text]))+ PCons :: (D.Store d -> [T.Text] -> m (D.Store d', [T.Text])) -> Router d' m a -> Params d m a -> Params d m a PNil :: Params d m a@@ -97,7 +111,7 @@ data Path d m a where Exact :: T.Text -> Path d m a -> Path d m a - Param :: String -> (D.Dict d -> [T.Text] -> m (D.Dict d', [T.Text]))+ Param :: String -> (D.Store d -> [T.Text] -> m (D.Store d', [T.Text])) -> Path d' m a -> Path d m a Action :: Maybe Method@@ -116,9 +130,9 @@ exact = Exact type Raw m d d'- = D.Dict d -- ^ input dictionary+ = D.Store d -- ^ input dictionary -> [T.Text] -- ^ input path information- -> m (D.Dict d', [T.Text]) -- ^ output dictionary and path information+ -> m (D.Store d', [T.Text]) -- ^ output dictionary and path information -- | raw get parameter function --@@ -209,25 +223,25 @@ r { anyMethod = \d -> anyMethod r d `mplus` n d } -- | insert path to router-add :: MonadPlus m => Path '[] m a -> Router '[] m a -> Router '[] m a-add = add'+insert :: MonadPlus m => Path '[] m a -> Router '[] m a -> Router '[] m a+insert = add' --- | infix version of 'add'+-- | infix version of `insert` (+|) :: MonadPlus m => Path '[] m a -> Router '[] m a -> Router '[] m a-(+|) = add+(+|) = insert -infixr `add`+infixr `insert` infixr +| -- | execute router execute :: MonadPlus m => Router '[] m a -> Method -> [T.Text] -> m a execute = execute' D.empty -execute' :: MonadPlus m => D.Dict d -> Router d m a -> Method -> [T.Text] -> m a+execute' :: MonadPlus m => D.Store d -> Router d m a -> Method -> [T.Text] -> m a execute' d Router{params, methods, anyMethod} m [] = fetching d m [] params `mplus` case H.lookup m methods of- Nothing -> anyMethod d- Just f -> f d+ Nothing -> anyMethod (D.mkDict d)+ Just f -> f (D.mkDict d) execute' d Router{params, children} m pps@(p:ps) = child `mplus` fetching d m pps params where@@ -235,7 +249,7 @@ Nothing -> mzero Just c -> execute' d c m ps -fetching :: MonadPlus m => D.Dict d -> Method -> [T.Text] -> Params d m a -> m a+fetching :: MonadPlus m => D.Store d -> Method -> [T.Text] -> Params d m a -> m a fetching d m pps = loop where loop PNil = mzero
src/Network/Routing/Dict.hs view
@@ -1,145 +1,29 @@-{-# LANGUAGE FunctionalDependencies #-}-{-# LANGUAGE UndecidableInstances #-}-{-# LANGUAGE OverlappingInstances #-}-{-# LANGUAGE ScopedTypeVariables #-}-{-# LANGUAGE FlexibleInstances #-}-{-# LANGUAGE FlexibleContexts #-}-{-# LANGUAGE ConstraintKinds #-} {-# LANGUAGE KindSignatures #-} {-# LANGUAGE TypeOperators #-} {-# LANGUAGE TypeFamilies #-}-{-# LANGUAGE BangPatterns #-} -- for ghc-7.6 {-# LANGUAGE DataKinds #-}-{-# LANGUAGE CPP #-} module Network.Routing.Dict- ( -- * dictionary- Dict- , ShowDict- , KV(..)- , empty-- -- * insert+ ( -- * store+ Store , type (</) , add - -- * get+ -- * dictionary+ , Dict , Member , get + -- * types+ , ShowDict+ , KV(..)+ -- * convenient , Members ) where import GHC.Exts(Constraint)--import Network.Routing.Tree--#if __GLASGOW_HASKELL__ > 707-import GHC.TypeLits-#endif--import Network.Routing.Compat-import Data.Typeable(typeOf, Typeable, TypeRep)-import Data.List(intercalate)-import Unsafe.Coerce---- | (kind) key-value pair-data KV v = Symbol := v---- | heterogeneous dictionary-newtype Dict (kvs :: [KV *]) = Dict Tree--class ShowDict (kvs :: [KV *]) where- showDict :: Int -> Dict kvs -> [(String, String, TypeRep)]--instance ShowDict '[] where- showDict _ _ = []--instance (KnownSymbol k, Typeable v, Show v, ShowDict kvs) => ShowDict (k := v ': kvs) where- showDict i (Dict t) =- (symbolVal (Proxy :: Proxy k), show (unsafeCoerce $ index t i :: v), typeOf (undefined :: v)):- showDict (i + 1) (unsafeCoerce $ Dict t :: Dict kvs)--instance ShowDict kvs => Show (Dict kvs) where- show d = "Dict {" ++- (intercalate ", " . map (\(k, v, t) -> k ++ " = " ++ v ++ " :: " ++ show t) $ showDict 0 d)- ++ "}"---- | empty dictionary-empty :: Dict '[]-empty = Dict Tip---- | result type for pretty printing type error.-data HasKeyResult- = AlreadyExists Symbol- | Dictionary--#if __GLASGOW_HASKELL__ > 707-type family HasKey (k :: Symbol) (kvs :: [KV *]) :: HasKeyResult where- HasKey k '[] = AlreadyExists k- HasKey k (k := v ': kvs) = Dictionary- HasKey k (k' := v ': kvs) = HasKey k kvs-#else-type family HasKey (k :: Symbol) (kvs :: [KV *]) :: HasKeyResult-type instance HasKey k kvs = AlreadyExists k-#endif---- | 'not elem key' constraint(ghc >= 7.8)-type k </ v = HasKey k v ~ AlreadyExists k---- | add key value pair to dictionary.------ >>> let a = add (Proxy :: Proxy "foo") (12 :: Int) empty--- >>> a--- Dict {foo = 12 :: Int}------ >>> add (Proxy :: Proxy "bar") "baz" a--- Dict {bar = "baz" :: [Char], foo = 12 :: Int}-add :: (k </ kvs) => proxy k -> v -> Dict kvs -> Dict (k := v ': kvs)-add _ v (Dict d) = Dict (unsafeCoerce v `cons` d)--#if __GLASGOW_HASKELL__ > 707-type family Ix (k :: Symbol) (kvs :: [KV *]) :: Nat where- Ix k (k := v ': kvs) = 0- Ix k (k' := v ': kvs) = 1 + Ix k kvs--getImpl :: forall proxy k kvs v. KnownNat (Ix k kvs) => proxy (k :: Symbol) -> Dict kvs -> v-getImpl _ (Dict d) = unsafeCoerce $ d `index` fromIntegral (natVal (Proxy :: Proxy (Ix k kvs)))--class Member (k :: Symbol) (v :: *) (kvs :: [KV *]) | k kvs -> v where- get' :: proxy k -> Dict kvs -> v--instance Member k v (k := v ': kvs) where- get' = getImpl- {-# INLINE get' #-}--instance (Member k v kvs, KnownNat (Ix k (k' := v' ': kvs))) => Member k v (k' := v' ': kvs) where- get' = getImpl- {-# INLINE get' #-}--get = get'-#else-class Member (k :: Symbol) (v :: *) (kvs :: [KV *]) | k kvs -> v where- get' :: Int -> proxy k -> Dict kvs -> v--instance Member k v (k := v ': kvs) where- get' !i _ (Dict d) = unsafeCoerce $ d `index` i--instance Member k v kvs => Member k v (k' := v' ': kvs) where- get' !i k d = get' (i + 1) k (unsafeCoerce d :: Dict kvs)--get = get' 0-#endif---- | get key from dictionary------ >>> let d = add (Proxy :: Proxy "foo") 12 $ add (Proxy :: Proxy "bar") "baz" empty--- >>> get (Proxy :: Proxy "foo") d--- 12--- >>> get (Proxy :: Proxy "bar") d--- "baz"-get :: Member k v kvs => proxy k -> Dict kvs -> v+import Network.Routing.Dict.Internal -- | type family to constraint multi kvs. --
+ src/Network/Routing/Dict/Internal.hs view
@@ -0,0 +1,171 @@+{-# LANGUAGE FunctionalDependencies #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE OverlappingInstances #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE ConstraintKinds #-}+{-# LANGUAGE KindSignatures #-}+{-# LANGUAGE TypeOperators #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE BangPatterns #-} -- for ghc-7.6+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE GADTs #-}+{-# LANGUAGE CPP #-}++module Network.Routing.Dict.Internal+ ( Dict, Store+ , ShowDict+ , KV(..)+ , empty+ , type (</)+ , add+ , Member+ , get+ , mkDict+ ) where++import GHC.Exts(Any)++import GHC.TypeLits+import Network.Routing.Compat+import Data.Typeable(typeOf, Typeable, TypeRep)+import Data.List(intercalate)+import Unsafe.Coerce+import qualified Control.Monad.Primitive as P+import qualified Data.Primitive as P+import Control.Monad.ST (ST, runST)++-- | (kind) key-value pair+data KV v = Symbol := v++-- | data store to construct dictionary.+--+-- `add` and `mkDict` operation only allowed.+data Store (kvs :: [KV *]) where+ Cons :: {-# UNPACK #-} !Int -> v -> Store kvs -> Store (k := v ': kvs)+ Empty :: Store '[]++instance ShowDict kvs => Show (Store kvs) where+ show d = "Store {" +++ (intercalate ", " . map (\(k, v, t) -> k ++ " = " ++ v ++ " :: " ++ show t) $ showDict 0 (mkDict d))+ ++ "}"++empty :: Store '[]+empty = Empty++size :: Store kvs -> Int+size Empty = 0+size (Cons l _ _) = l++-- | result type for pretty printing type error.+data HasKeyResult+ = AlreadyExists Symbol+ | Dictionary++#if __GLASGOW_HASKELL__ > 707+type family HasKey (k :: Symbol) (kvs :: [KV *]) :: HasKeyResult where+ HasKey k '[] = AlreadyExists k+ HasKey k (k := v ': kvs) = Dictionary+ HasKey k (k' := v ': kvs) = HasKey k kvs+#else+type family HasKey (k :: Symbol) (kvs :: [KV *]) :: HasKeyResult+type instance HasKey k kvs = AlreadyExists k+#endif++-- | 'not elem key' constraint(ghc >= 7.8)+type k </ v = HasKey k v ~ AlreadyExists k++-- | O(1) add key value pair to dictionary.+--+-- >>> let a = add (Proxy :: Proxy "foo") (12 :: Int) empty+-- >>> a+-- Store {foo = 12 :: Int}+--+-- >>> add (Proxy :: Proxy "bar") "baz" a+-- Store {bar = "baz" :: [Char], foo = 12 :: Int}+add :: (k </ kvs) => proxy k -> v -> Store kvs -> Store (k := v ': kvs)+add _ v Empty = Cons 1 v Empty+add _ v c@(Cons i _ _) = Cons (i + 1) v c++-- | heterogeneous dictionary+--+-- 'get' operation only allowed.+newtype Dict (kvs :: [KV *]) = Dict (P.Array Any)++class ShowDict (kvs :: [KV *]) where+ showDict :: Int -> Dict kvs -> [(String, String, TypeRep)]++instance ShowDict '[] where+ showDict _ _ = []++instance (KnownSymbol k, Typeable v, Show v, ShowDict kvs) => ShowDict (k := v ': kvs) where+ showDict i (Dict t) =+ (symbolVal (Proxy :: Proxy k), show (unsafeCoerce $ P.indexArray t i :: v), typeOf (undefined :: v)):+ showDict (i + 1) (unsafeCoerce $ Dict t :: Dict kvs)++instance ShowDict kvs => Show (Dict kvs) where+ show d = "Dict {" +++ (intercalate ", " . map (\(k, v, t) -> k ++ " = " ++ v ++ " :: " ++ show t) $ showDict 0 d)+ ++ "}"++mkDict' :: forall s kvs. Store kvs -> ST s (Dict kvs)+mkDict' store = do+ ary <- P.newArray (size store) undefined+ go (size store) ary+ Dict `fmap` P.unsafeFreezeArray ary+ where+ go :: Int -> P.MutableArray (P.PrimState (ST s)) Any -> ST s ()+ go size' array = loop store+ where+ loop :: Store kvs -> ST s ()+ loop (Cons i v ss) = do+ P.writeArray array (size' - i) (unsafeCoerce v)+ loop (unsafeCoerce ss)+ loop Empty = return ()++-- | O(n) convert "Store" to "Dictionary".+mkDict :: Store kvs -> Dict kvs+mkDict store = runST $ mkDict' store++-- | O(1) (>= ghc-7.8), O(n) (< ghc-7.8) get key from dictionary+--+-- >>> let d = mkDict $ add (Proxy :: Proxy "foo") 12 $ add (Proxy :: Proxy "bar") "baz" empty+-- >>> get (Proxy :: Proxy "foo") d+-- 12+-- >>> get (Proxy :: Proxy "bar") d+-- "baz"+get :: Member k v kvs => proxy k -> Dict kvs -> v++#if __GLASGOW_HASKELL__ > 707+type family Ix (k :: Symbol) (kvs :: [KV *]) :: Nat where+ Ix k (k := v ': kvs) = 0+ Ix k (k' := v ': kvs) = 1 + Ix k kvs++getImpl :: forall proxy k kvs v. KnownNat (Ix k kvs) => proxy (k :: Symbol) -> Dict kvs -> v+getImpl _ (Dict d) = unsafeCoerce $ d `P.indexArray` fromIntegral (natVal (Proxy :: Proxy (Ix k kvs)))++class Member (k :: Symbol) (v :: *) (kvs :: [KV *]) | k kvs -> v where+ get' :: proxy k -> Dict kvs -> v++instance Member k v (k := v ': kvs) where+ get' = getImpl+ {-# INLINE get' #-}++instance (Member k v kvs, KnownNat (Ix k (k' := v' ': kvs))) => Member k v (k' := v' ': kvs) where+ get' = getImpl+ {-# INLINE get' #-}++get = get'+#else+class Member (k :: Symbol) (v :: *) (kvs :: [KV *]) | k kvs -> v where+ get' :: Int -> proxy k -> Dict kvs -> v++instance Member k v (k := v ': kvs) where+ get' !i _ (Dict d) = unsafeCoerce $ d `P.indexArray` i++instance Member k v kvs => Member k v (k' := v' ': kvs) where+ get' !i k d = get' (i + 1) k (unsafeCoerce d :: Dict kvs)++get = get' 0+#endif
− src/Network/Routing/Tree.hs
@@ -1,30 +0,0 @@-{-# LANGUAGE BangPatterns #-}--module Network.Routing.Tree- ( Tree(Tip)- , cons- , index- , ) where--import GHC.Exts(Any)--data Dir = L | R--data Tree- = Branch !Dir !Any !Tree !Tree- | Tip--cons :: Any -> Tree -> Tree-cons v Tip = Branch L v Tip Tip-cons v (Branch _ a Tip Tip) = Branch R v (Branch L a Tip Tip) Tip-cons v (Branch _ a l Tip) = Branch L v l (Branch L a Tip Tip)-cons v (Branch L a l r) = Branch R v (cons a l) r-cons v (Branch R a l r) = Branch L v l (cons a r)--index :: Tree -> Int -> Any-index Tip _ = error "out of range"-index (Branch _ v _ _) 0 = v-index (Branch L _ l r) !i | even i = index l (i `quot` 2 - 1)- | otherwise = index r (i `quot` 2)-index (Branch R _ l r) !i | odd i = index l (i `quot` 2)- | otherwise = index r (i `quot` 2 - 1)
− tests/Tree.hs
@@ -1,16 +0,0 @@-module Tree(test) where--import Network.Routing.Tree-import Test.Tasty-import Test.Tasty.QuickCheck-import Unsafe.Coerce--mkTestTree :: Int -> Tree-mkTestTree i = foldr cons Tip $ map unsafeCoerce [0..i]--testTreeToList :: Int -> Tree -> [Int]-testTreeToList l t = foldr (\i b -> unsafeCoerce (t `index` i) : b) [] [0..l]--test :: TestTree-test = testProperty "Data.Apiary.Tree" $ \len ->- testTreeToList len (mkTestTree len) == [0..len]
− tests/tasty.hs
@@ -1,7 +0,0 @@-import Test.Tasty-import qualified Tree--main :: IO ()-main = defaultMain $ testGroup ""- [ Tree.test- ]
web-routing.cabal view
@@ -1,5 +1,5 @@ name: web-routing-version: 0.1.2+version: 0.2.0 synopsis: simple routing library -- description: license: MIT@@ -16,12 +16,13 @@ library exposed-modules: Network.Routing Network.Routing.Dict- other-modules: Network.Routing.Tree- Network.Routing.Compat+ other-modules: Network.Routing.Compat+ Network.Routing.Dict.Internal build-depends: base >=4.6 && <4.8 , bytestring >=0.10 && <0.11 , text >=1.1 && <1.3 , unordered-containers >=0.2 && <0.3+ , primitive >=0.5 && <0.6 ghc-options: -O2 -Wall hs-source-dirs: src default-language: Haskell2010@@ -35,13 +36,12 @@ , doctest >=0.9 && <0.10 default-language: Haskell2010 -test-suite tasty+benchmark benchmarks type: exitcode-stdio-1.0- ghc-options: -threaded- main-is: tasty.hs- other-modules: Tree- hs-source-dirs: tests, src- build-depends: base >=4.6 && <4.8- , tasty >=0.10 && <0.11- , tasty-quickcheck >=0.8 && <0.9+ main-is: bench/main.hs+ build-depends: base >=4.6 && <4.8+ , web-routing+ , criterion+ , text+ ghc-options: -O2 -Wall -threaded default-language: Haskell2010