smap 0.2.1 → 0.3.0
raw patch · 4 files changed
+177/−70 lines, 4 filesdep +memorydep +mmorphdep −siphash
Dependencies added: memory, mmorph
Dependencies removed: siphash
Files
- README.md +66/−7
- smap.cabal +11/−8
- src/Smap/Commands.hs +62/−25
- src/Smap/Flags.hs +38/−30
README.md view
@@ -1,21 +1,22 @@ # smap - a command line tool for sets and maps +This is a very minimal but powerful tool for performing set/map union, subtraction, and intersection on text files. If you find yourself using commands like `sort`, `uniq`, `comm`, and really contorted `sed`/`awk` invocations, this tool will probably help you. It's faster, simpler to use, and doesn't require lexicographic ordering.+ ## Installation: -To install from Hackage, run:+To install from hackage (without downloading this repo), you will want [cabal](https://www.haskell.org/cabal/). Then you can run ```bash cabal install smap ``` -To install from source, you can use that or download this repo and run+To install from this repo, I recommend getting [stack](https://www.haskellstack.org) and running + ```bash stack install smap ``` -You will need [cabal](https://www.haskell.org/cabal/) or [stack](https://www.haskellstack.org) if you don't already have one of them. - ## Tutorial: The setup:@@ -70,6 +71,8 @@ Carol Carell ``` +By default, output goes to stdout, but you can send it elsewhere with `-o`. (This also works for any command.)+ #### sub - Set subtraction Healthy patients:@@ -107,10 +110,16 @@ When using `smap` with sets, the behavior is pretty straightforward. It gets a bit more complicated when dealing with maps. -If you provide `smap` with a filepath, it will construct a map where the keys equal the values. (This-is equivalent to a set). If you pass in `+file1,file2` -as an argument, `smap` will construct a map using lines from file1 as keys and lines from file2 as values. +There are actually three ways you can pass a file argument to `smap`. +1. If you just use a regular filepath, like `patients.txt` or `-` (for stdin/out), `smap` will create a map where the keys are equal to the values. This behaves like a set, which is why all the simple usage examples work this way.+2. If you instead use an argument like `+file1,file2`, `smap` will use `file1` for the keys and `file2` for the values.+3. If you instead use an argument like `@file`, `smap` will read/write keys/values on alternating lines. +This is useful for passing maps between invocations of `smap`. You can of course use `@-` to mean "alternating between keys and values on stdin/stdout".+++Here are some examples.+ We can get a list of patient last names using `cut -f 2 -d ' ' <patient file>` #### Pick one patient from each family:@@ -147,9 +156,59 @@ So `int` is filtering the first argument (treated as a `key,value` stream) by the keys present in the second argument. +#### Passing maps between `smap` invocations++In earlier examples where we composed invocations of `smap`, we only passed sets between the various invocations. We can easily pass maps as well, using the `@` syntax to read/write keys and values from the same file (on alternating lines). For example, let's say we wanted to find patients whose family members have a cold *and* mumps. One way we could do it is++```bash+$ smap int +<(cut -f 2 -d ' ' patients),patients <(cut -f 2 -d ' ' has_cold) <(cut -f 2 -d ' ' has_mumps)+Jane Doe+```++Thankfully Jane doesn't have any other family members who are at risk of catching both a cold and mumps. We could also write this as++```bash+$ smap int +<(cut -f 2 -d ' ' patients),patients <(cut -f 2 -d ' ' has_cold) -o @- | smap int @- <(cut -f 2 -d ' ' has_mumps)+Jane Doe+```++What's going on here is that the first command is finding all patients who have a family member with a cold, and outputting to stdout each person's name (the value) *as well as* their family name (the key). We can see this by running:++```bash+$ smap int +<(cut -f 2 -d ' ' patients),patients <(cut -f 2 -d ' ' has_cold) -o @-+Smith+Bob Smith+Doe+Jane Doe+Smith+John Smith+```++Then, we have a second invocation of `smap int` which is reading these key/value pairs in from stdin and intersecting them with the set of families where someone has mumps.+ ### Approximate mode If you're processing lots of lines and running up against memory limits, you can use the `--approximate` or `-a` option to keep track of a 64-bit hash of each line instead of the entire line. You can also use `--approx-with-key` or `-k` if you want to specify the SipHash key.++Illustrative example:++```bash+$ smap sub -a +<(cut -f 2 -d ' ' patients),patients -o @-+5e1334422d6eedac+Bob Smith+c62edd9db8aac96c+Jane Doe+5e1334422d6eedac+John Smith+79db904924f32d34+Carol Carell+```++Notice that the Smiths both have a key of `5e13...`++### Performance++It's pretty fast. On my laptop, I can churn through 1.something million lines per second for short lines and a few hundred megabytes per second on long lines. I'll probably run out of RAM before I run out of time. Of course, faster is better, so please feel free to open an issue/PR with suggestions.
smap.cabal view
@@ -4,10 +4,10 @@ -- -- see: https://github.com/sol/hpack ----- hash: f341330ce026ba29d5e5b23a17af3e56e1a415c1dc7d595c07a06ffe622d12ce+-- hash: dc720fa6c892a34f74beb6a1e1ed38ba1e526f447ab01acf0def007688bdb05e name: smap-version: 0.2.1+version: 0.3.0 synopsis: A command line tool for working with sets and maps description: Please see the README below or on GitHub at <https://github.com/wyager/smap> category: Text@@ -35,16 +35,17 @@ Paths_smap hs-source-dirs: src- default-extensions: TupleSections RankNTypes ScopedTypeVariables LambdaCase BangPatterns KindSignatures DataKinds+ default-extensions: TupleSections RankNTypes ScopedTypeVariables LambdaCase BangPatterns KindSignatures DataKinds OverloadedStrings ghc-options: -O2 -Wall -fexpose-all-unfoldings -optP-Wno-nonportable-include-path build-depends: attoparsec , base >=4.7 && <5 , bytestring , hashable+ , memory+ , mmorph , optparse-applicative , resourcet- , siphash , streaming , streaming-bytestring , strict@@ -59,16 +60,17 @@ Paths_smap hs-source-dirs: app- default-extensions: TupleSections RankNTypes ScopedTypeVariables LambdaCase BangPatterns KindSignatures DataKinds+ default-extensions: TupleSections RankNTypes ScopedTypeVariables LambdaCase BangPatterns KindSignatures DataKinds OverloadedStrings ghc-options: -rtsopts -Wall -O2 -fspecialize-aggressively -optP-Wno-nonportable-include-path build-depends: attoparsec , base >=4.7 && <5 , bytestring , hashable+ , memory+ , mmorph , optparse-applicative , resourcet- , siphash , smap , streaming , streaming-bytestring@@ -85,16 +87,17 @@ Paths_smap hs-source-dirs: test- default-extensions: TupleSections RankNTypes ScopedTypeVariables LambdaCase BangPatterns KindSignatures DataKinds+ default-extensions: TupleSections RankNTypes ScopedTypeVariables LambdaCase BangPatterns KindSignatures DataKinds OverloadedStrings ghc-options: -rtsopts build-depends: attoparsec , base >=4.7 && <5 , bytestring , hashable+ , memory+ , mmorph , optparse-applicative , resourcet- , siphash , smap , streaming , streaming-bytestring
src/Smap/Commands.hs view
@@ -1,7 +1,7 @@ module Smap.Commands (run) where import Prelude hiding (filter, subtract, init, sin)-import qualified Data.HashMap.Strict as Map (insert, empty, member)+import qualified Data.HashMap.Strict as Map (insert, intersection, empty, member) import Data.HashMap.Strict as Map (HashMap) import Data.Hashable (Hashable) import Data.ByteString.Char8 (ByteString)@@ -9,14 +9,16 @@ import qualified Streaming.Prelude as P import qualified Streaming as S import Control.Monad (foldM)-import Control.Monad.Trans.Class (lift)+import Control.Monad.Morph (hoist, lift) import Data.Strict.Tuple (Pair((:!:))) import Data.List.NonEmpty (NonEmpty((:|))) import qualified Control.Monad.Trans.Resource as Resource-import Crypto.MAC.SipHash (SipHash(..), hash)+import Data.ByteArray.Hash (SipHash(..), sipHash)+import Data.ByteString.Builder (word64HexFixed, toLazyByteString)+import Data.ByteString.Lazy (toStrict) import Smap.Flags ( Hdl(Std, File)- , Descriptor(Keyed, UnKeyed)+ , Descriptor(Separate, UnKeyed, Interleaved) , Command(Union, Subtract, Intersect) , Accuracy(Approximate, Exact) )@@ -34,30 +36,55 @@ cat :: SetOperation cat streams = foldM filter Map.empty streams *> return () where- filter seen = P.foldM_ filter' (return seen) return . S.hoist lift+ filter seen = P.foldM_ filter' (return seen) return . hoist lift -- for some strange reason I can't import alterF from Data.HashMap.Strict filter' (seen :: HashMap k ()) (bs :!: v) = if bs `Map.member` seen then return seen else P.yield (bs :!: v) >> return (Map.insert bs () seen) -filterStreamWith :: (Bool -> Bool) -> SetOperation-filterStreamWith includeIfPresent (first :| seconds) = do- second <- lift $ collects seconds- P.filter (\(k :!: _) -> includeIfPresent (k `Map.member` second)) first- where- collects = foldM collect Map.empty- collect subs = P.fold_ (\s (k :!: _) -> Map.insert k () s) subs id- sub :: SetOperation-sub = filterStreamWith not+sub (first :| seconds) = do+ subs <- lift $ foldM collect Map.empty seconds+ P.filter (\(k :!: _) -> not (k `Map.member` subs)) first+ where collect subs = P.fold_ (\s (k :!: _) -> Map.insert k () s) subs id int :: SetOperation-int = filterStreamWith id+int (_first :| [] ) = return ()+int (first :| (x : xs)) = do+ init <- lift $ collect x+ intersection <- lift $ foldM reduce init xs+ P.filter (\(k :!: _) -> k `Map.member` intersection) first+ where+ collect = P.fold_ (\s (k :!: _) -> Map.insert k () s) Map.empty id+ reduce ints stream = Map.intersection ints <$> collect stream ++deinterleave :: Monad m => S.Stream (S.Of a) m r -> S.Stream (S.Of (Pair a a)) m r+deinterleave = fmap P.snd' . P.foldM step (return Nothing) return . hoist lift+ where+ step Nothing a = return (Just a)+ step (Just a) b = P.yield (a :!: b) >> return Nothing++-- Outputs the keys to one file and values to the other (simultaneously)+splitWith+ :: (Pair k ByteString -> P.Stream (P.Of (Either ByteString ByteString)) RIO ())+ -> Hdl+ -> Hdl+ -> Stream RIO k ByteString+ -> RIO ()+splitWith split kFile vFile = hout kFile . hout vFile . hoist unlinify . unlinify . separate+ where+ hout Std = BS8.stdout+ hout (File path) = BS8.writeFile path+ separate paired = P.partitionEithers $ P.for paired split+ unlinify :: Monad n => S.Stream (S.Of ByteString) n x -> BS8.ByteString n x+ unlinify = BS8.unlines . S.maps (\(b P.:> r) -> BS8.fromStrict b >> return r)+ load :: Descriptor ty -> Stream RIO ByteString ByteString load descriptor = case descriptor of- UnKeyed hdl -> P.map (\x -> x :!: x) (linesOf hdl)- Keyed keys values -> S.zipsWith'+ UnKeyed hdl -> P.map (\x -> x :!: x) (linesOf hdl)+ Interleaved hdl -> deinterleave (linesOf hdl)+ Separate keys values -> S.zipsWith' (\q (k P.:> ks) (v P.:> vs) -> (k :!: v) P.:> (q ks vs)) (linesOf keys) (linesOf values)@@ -67,17 +94,27 @@ hin (File path) = BS8.readFile path withAccuracy- :: Accuracy -> SetOperation -> NonEmpty (Stream RIO ByteString ByteString) -> Hdl -> IO ()+ :: Accuracy+ -> SetOperation+ -> NonEmpty (Stream RIO ByteString ByteString)+ -> Descriptor out+ -> IO () withAccuracy accuracy op inputs output = case accuracy of- Exact -> approximateWith id- Approximate key -> approximateWith (\bs -> let SipHash h = hash key bs in h)+ Exact -> approximateWith id id+ Approximate key -> approximateWith+ (\bs -> let SipHash h = sipHash key bs in h)+ (toStrict . toLazyByteString . word64HexFixed) where- format = BS8.unlines . S.maps (\((_k :!: v) P.:> r) -> BS8.fromStrict v >> return r)- hout Std = BS8.stdout- hout (File path) = BS8.writeFile path+ valuesOnly (_k :!: v) = P.yield (Right v)+ separateFiles k2bs (k :!: v) = P.yield (Left (k2bs k)) >> P.yield (Right v)+ sameFile k2bs (k :!: v) = P.yield (Right (k2bs k)) >> P.yield (Right v)+ outputUsing k2bs = case output of+ UnKeyed hdl -> splitWith valuesOnly hdl hdl+ Interleaved hdl -> splitWith (sameFile k2bs) hdl hdl+ Separate l r -> splitWith (separateFiles k2bs) l r keyMap f = P.map (\(k :!: v) -> (f k :!: v))- approximateWith approximator =- Resource.runResourceT $ hout output $ format $ op $ fmap (keyMap approximator) inputs+ approximateWith approximator k2bs =+ Resource.runResourceT $ outputUsing k2bs $ op $ fmap (keyMap approximator) inputs run :: Command -> IO () run cmd = case cmd of
src/Smap/Flags.hs view
@@ -1,9 +1,11 @@++ -- Command line flag parsing module Smap.Flags ( Hdl(Std, File)- , Descriptor(Keyed, UnKeyed)- , InputType(Set, Stream)+ , Descriptor(Separate, UnKeyed, Interleaved)+ , FileType(Set, Stream) , Command(Union, Subtract, Intersect) , Accuracy(Approximate, Exact) , command@@ -14,25 +16,26 @@ import qualified Data.Text as Text import qualified Options.Applicative as O import Control.Applicative (many, (<|>))-import Crypto.MAC.SipHash (SipKey(..))+import Data.ByteArray.Hash (SipKey(..)) data Hdl = Std -- stdin/stdout | File FilePath -- Just to help us keep track of how a descriptor is used-data InputType = Set -- Duplicates are discarded- | Stream -- Duplicates are not discarded+data FileType = Set -- Duplicates are discarded+ | Stream -- Duplicates are not discarded -data Descriptor (ty :: InputType)- = Keyed Hdl Hdl -- Keys are in the first file, values in the second (map behavior)+data Descriptor (ty :: FileType)+ = Separate Hdl Hdl -- Keys are in the first file, values in the second (map behavior)+ | Interleaved Hdl -- Keys and values are on separate lines in the same file | UnKeyed Hdl -- key = value (set behavior) data Accuracy = Approximate SipKey -- Don't keep the actual value as a key, just its hash | Exact -- Keep the actual value as a key -data Command = Union Accuracy [Descriptor 'Set] Hdl- | Subtract Accuracy (Descriptor 'Stream) [Descriptor 'Set] Hdl- | Intersect Accuracy (Descriptor 'Stream) [Descriptor 'Set] Hdl+data Command = Union Accuracy [Descriptor 'Set] (Descriptor 'Set)+ | Subtract Accuracy (Descriptor 'Stream) [Descriptor 'Set] (Descriptor 'Stream)+ | Intersect Accuracy (Descriptor 'Stream) [Descriptor 'Set] (Descriptor 'Stream) hdl :: A.Parser Hdl hdl = stdin <|> path@@ -40,15 +43,9 @@ stdin = Std <$ A.char '-' path = File . Text.unpack <$> A.takeWhile (/= ',') -outHdl :: O.Parser Hdl-outHdl = O.option- (aToO hdl)- (O.metavar "OUTFILE" <> O.short 'o' <> O.long "out" <> O.value Std <> O.help "Defaults to stdout."- )- descriptor :: A.Parser (Descriptor ty) descriptor =- (keyed <|> unkeyed)+ (keyed <|> interleaved <|> unkeyed) <* (A.endOfInput A.<?> "more filepath characters than expected") A.<?> "Could not parse filepath" where@@ -58,26 +55,37 @@ k <- hdl _ <- A.char ',' v <- hdl- return (Keyed k v)+ return (Separate k v)+ interleaved = Interleaved <$> (A.char '@' *> hdl) aToO :: A.Parser a -> O.ReadM a aToO p = O.eitherReader (A.parseOnly p . Text.pack) +argDescription :: String+argDescription =+ "Use '-' for stdin/out. Use +keyfile,valfile for separate keys and values. Use @file for keys and values on alternating lines."+ stream :: O.Parser (Descriptor 'Stream) stream = O.argument (aToO descriptor)- (O.metavar "STREAM" <> O.help- "Stream source file. Use '-' for stdin. Use +keyfile,valfile for separate keys and values."- )+ (O.metavar "STREAM" <> O.help ("Stream source file. " ++ argDescription)) +output :: O.Parser (Descriptor a)+output =+ O.option+ (aToO descriptor)+ ( O.metavar "OUTPUT"+ <> O.help ("Output file(s). Defaults to stdout. " ++ argDescription)+ <> O.short 'o'+ <> O.long "output"+ )+ <|> pure (UnKeyed Std)+ sets :: O.Parser [Descriptor 'Set] sets = many $ O.argument (aToO descriptor)- ( O.metavar "SET*"- <> O.help- "Set/map source files (0 or more). Use '-' for stdin. Use +keyfile,valfile for separate keys and values."- )+ (O.metavar "SET*" <> O.help ("Set/map source files (0 or more). " ++ argDescription)) accuracy :: O.Parser Accuracy accuracy = approx <|> approxWithKey <|> exact@@ -104,7 +112,7 @@ catCommand = O.command "cat" $ O.info (value O.<**> O.helper) (O.fullDesc <> O.progDesc "Set union. Output everything from the input sets, deduplicated.")- where value = Union <$> accuracy <*> sets <*> outHdl+ where value = Union <$> accuracy <*> sets <*> output subCommand :: O.Mod O.CommandFields Command subCommand = O.command "sub" $ O.info@@ -112,12 +120,12 @@ (O.fullDesc <> O.progDesc (concat [ "Set subtraction. "- , "Given stream A and sets B,C,..., output values in A but not in B,C,... "+ , "Given stream A and sets B,C,..., output values in A but not in any of B,C,... " , "Does not deduplicate values from A." ] ) )- where value = Subtract <$> accuracy <*> stream <*> sets <*> outHdl+ where value = Subtract <$> accuracy <*> stream <*> sets <*> output intersectCommand :: O.Mod O.CommandFields Command intersectCommand = O.command "int" $ O.info@@ -126,12 +134,12 @@ (concat [ "Set intersection. " , "Given stream A and sets B,C,..., output values in A "- , "only if they are in at least one of B,C,... "+ , "only if they are in all of of B,C,... " , "Does not deduplicate values from A." ] ) )- where value = Intersect <$> accuracy <*> stream <*> sets <*> outHdl+ where value = Intersect <$> accuracy <*> stream <*> sets <*> output command :: IO Command command = O.execParser