deptrack-core (empty) → 0.1.0.0

raw patch · 8 files changed

+526/−0 lines, 8 filesdep +basedep +containersdep +dlistsetup-changed

Dependencies added: base, containers, dlist, mtl, parsec

Files

• ChangeLog.md +7/−0
• LICENSE +201/−0
• README.md +11/−0
• Setup.hs +2/−0
• deptrack-core.cabal +33/−0
• src/DepTrack.hs +174/−0
• src/DepTrack/DepCrumb.hs +10/−0
• src/DepTrack/Parsing.hs +88/−0

@@ -0,0 +1,7 @@+# Changelog for warp-grpc++## Unreleased changes++## 0.1.0.0++Initial release.

@@ -0,0 +1,201 @@+                                 Apache License+                           Version 2.0, January 2004+                        http://www.apache.org/licenses/++   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION++   1. Definitions.++      "License" shall mean the terms and conditions for use, reproduction,+      and distribution as defined by Sections 1 through 9 of this document.++      "Licensor" shall mean the copyright owner or entity authorized by+      the copyright owner that is granting the License.++      "Legal Entity" shall mean the union of the acting entity and all+      other entities that control, are controlled by, or are under common+      control with that entity. For the purposes of this definition,+      "control" means (i) the power, direct or indirect, to cause the+      direction or management of such entity, whether by contract or+      otherwise, or (ii) ownership of fifty percent (50%) or more of the+      outstanding shares, or (iii) beneficial ownership of such entity.++      "You" (or "Your") shall mean an individual or Legal Entity+      exercising permissions granted by this License.++      "Source" form shall mean the preferred form for making modifications,+      including but not limited to software source code, documentation+      source, and configuration files.++      "Object" form shall mean any form resulting from mechanical+      transformation or translation of a Source form, including but+      not limited to compiled object code, generated documentation,+      and conversions to other media types.++      "Work" shall mean the work of authorship, whether in Source or+      Object form, made available under the License, as indicated by a+      copyright notice that is included in or attached to the work+      (an example is provided in the Appendix below).++      "Derivative Works" shall mean any work, whether in Source or Object+      form, that is based on (or derived from) the Work and for which the+      editorial revisions, annotations, elaborations, or other modifications+      represent, as a whole, an original work of authorship. For the purposes+      of this License, Derivative Works shall not include works that remain+      separable from, or merely link (or bind by name) to the interfaces of,+      the Work and Derivative Works thereof.++      "Contribution" shall mean any work of authorship, including+      the original version of the Work and any modifications or additions+      to that Work or Derivative Works thereof, that is intentionally+      submitted to Licensor for inclusion in the Work by the copyright owner+      or by an individual or Legal Entity authorized to submit on behalf of+      the copyright owner. For the purposes of this definition, "submitted"+      means any form of electronic, verbal, or written communication sent+      to the Licensor or its representatives, including but not limited to+      communication on electronic mailing lists, source code control systems,+      and issue tracking systems that are managed by, or on behalf of, the+      Licensor for the purpose of discussing and improving the Work, but+      excluding communication that is conspicuously marked or otherwise+      designated in writing by the copyright owner as "Not a Contribution."++      "Contributor" shall mean Licensor and any individual or Legal Entity+      on behalf of whom a Contribution has been received by Licensor and+      subsequently incorporated within the Work.++   2. Grant of Copyright License. Subject to the terms and conditions of+      this License, each Contributor hereby grants to You a perpetual,+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable+      copyright license to reproduce, prepare Derivative Works of,+      publicly display, publicly perform, sublicense, and distribute the+      Work and such Derivative Works in Source or Object form.++   3. Grant of Patent License. Subject to the terms and conditions of+      this License, each Contributor hereby grants to You a perpetual,+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable+      (except as stated in this section) patent license to make, have made,+      use, offer to sell, sell, import, and otherwise transfer the Work,+      where such license applies only to those patent claims licensable+      by such Contributor that are necessarily infringed by their+      Contribution(s) alone or by combination of their Contribution(s)+      with the Work to which such Contribution(s) was submitted. If You+      institute patent litigation against any entity (including a+      cross-claim or counterclaim in a lawsuit) alleging that the Work+      or a Contribution incorporated within the Work constitutes direct+      or contributory patent infringement, then any patent licenses+      granted to You under this License for that Work shall terminate+      as of the date such litigation is filed.++   4. Redistribution. You may reproduce and distribute copies of the+      Work or Derivative Works thereof in any medium, with or without+      modifications, and in Source or Object form, provided that You+      meet the following conditions:++      (a) You must give any other recipients of the Work or+          Derivative Works a copy of this License; and++      (b) You must cause any modified files to carry prominent notices+          stating that You changed the files; and++      (c) You must retain, in the Source form of any Derivative Works+          that You distribute, all copyright, patent, trademark, and+          attribution notices from the Source form of the Work,+          excluding those notices that do not pertain to any part of+          the Derivative Works; and++      (d) If the Work includes a "NOTICE" text file as part of its+          distribution, then any Derivative Works that You distribute must+          include a readable copy of the attribution notices contained+          within such NOTICE file, excluding those notices that do not+          pertain to any part of the Derivative Works, in at least one+          of the following places: within a NOTICE text file distributed+          as part of the Derivative Works; within the Source form or+          documentation, if provided along with the Derivative Works; or,+          within a display generated by the Derivative Works, if and+          wherever such third-party notices normally appear. The contents+          of the NOTICE file are for informational purposes only and+          do not modify the License. You may add Your own attribution+          notices within Derivative Works that You distribute, alongside+          or as an addendum to the NOTICE text from the Work, provided+          that such additional attribution notices cannot be construed+          as modifying the License.++      You may add Your own copyright statement to Your modifications and+      may provide additional or different license terms and conditions+      for use, reproduction, or distribution of Your modifications, or+      for any such Derivative Works as a whole, provided Your use,+      reproduction, and distribution of the Work otherwise complies with+      the conditions stated in this License.++   5. Submission of Contributions. Unless You explicitly state otherwise,+      any Contribution intentionally submitted for inclusion in the Work+      by You to the Licensor shall be under the terms and conditions of+      this License, without any additional terms or conditions.+      Notwithstanding the above, nothing herein shall supersede or modify+      the terms of any separate license agreement you may have executed+      with Licensor regarding such Contributions.++   6. Trademarks. This License does not grant permission to use the trade+      names, trademarks, service marks, or product names of the Licensor,+      except as required for reasonable and customary use in describing the+      origin of the Work and reproducing the content of the NOTICE file.++   7. Disclaimer of Warranty. Unless required by applicable law or+      agreed to in writing, Licensor provides the Work (and each+      Contributor provides its Contributions) on an "AS IS" BASIS,+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or+      implied, including, without limitation, any warranties or conditions+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A+      PARTICULAR PURPOSE. You are solely responsible for determining the+      appropriateness of using or redistributing the Work and assume any+      risks associated with Your exercise of permissions under this License.++   8. Limitation of Liability. In no event and under no legal theory,+      whether in tort (including negligence), contract, or otherwise,+      unless required by applicable law (such as deliberate and grossly+      negligent acts) or agreed to in writing, shall any Contributor be+      liable to You for damages, including any direct, indirect, special,+      incidental, or consequential damages of any character arising as a+      result of this License or out of the use or inability to use the+      Work (including but not limited to damages for loss of goodwill,+      work stoppage, computer failure or malfunction, or any and all+      other commercial damages or losses), even if such Contributor+      has been advised of the possibility of such damages.++   9. Accepting Warranty or Additional Liability. While redistributing+      the Work or Derivative Works thereof, You may choose to offer,+      and charge a fee for, acceptance of support, warranty, indemnity,+      or other liability obligations and/or rights consistent with this+      License. However, in accepting such obligations, You may act only+      on Your own behalf and on Your sole responsibility, not on behalf+      of any other Contributor, and only if You agree to indemnify,+      defend, and hold each Contributor harmless for any liability+      incurred by, or claims asserted against, such Contributor by reason+      of your accepting any such warranty or additional liability.++   END OF TERMS AND CONDITIONS++   APPENDIX: How to apply the Apache License to your work.++      To apply the Apache License to your work, attach the following+      boilerplate notice, with the fields enclosed by brackets "{}"+      replaced with your own identifying information. (Don't include+      the brackets!)  The text should be enclosed in the appropriate+      comment syntax for the file format. We also recommend that a+      file or class name and description of purpose be included on the+      same "printed page" as the copyright notice for easier+      identification within third-party archives.++   Copyright {yyyy} {name of copyright owner}++   Licensed under the Apache License, Version 2.0 (the "License");+   you may not use this file except in compliance with the License.+   You may obtain a copy of the License at++       http://www.apache.org/licenses/LICENSE-2.0++   Unless required by applicable law or agreed to in writing, software+   distributed under the License is distributed on an "AS IS" BASIS,+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+   See the License for the specific language governing permissions and+   limitations under the License.

@@ -0,0 +1,11 @@+DepTrack+========++DepTrack is a library to let you _compute_ dependency trees/graphs. Rather+than maintaining a graph of dependencies, we propose to _track_ dependencies+as a side-effect of a computation.++Example uses of DepTrack are:++- devops: provision and configure machines+- architecture-documentation: map and describe business processes as dependency graphs

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,33 @@+name:                deptrack-core+version:             0.1.0.0+synopsis:            DepTrack Core types and model.+description:         Rather than building and maintaing a dependency tree/graph by hand. DepTrack proposes to _track_ dependencies as a side-effect of a computation.+homepage:            https://github.com/lucasdicioccio/deptrack-project+license:             Apache-2.0+license-file:        LICENSE+author:              Lucas DiCioccio+maintainer:          lucas@dicioccio.fr+copyright:           2017 Lucas DiCioccio+category:            Graphs+build-type:          Simple+cabal-version:       >=1.10+extra-source-files:+    ChangeLog.md+    README.md++library+  exposed-modules:     DepTrack+                     , DepTrack.DepCrumb+                     , DepTrack.Parsing+  other-extensions:    TupleSections+                     , FlexibleInstances+                     , MultiParamTypeClasses+                     , DeriveFunctor+  build-depends:       base >= 4.10 && < 5.0+                     , containers >= 0.5 && < 0.6+                     , dlist >= 0.8 && < 0.9+                     , parsec >= 3.1 && < 3.2+                     , mtl >= 2.2 && < 2.3+  hs-source-dirs:      src+  default-language:    Haskell2010+

@@ -0,0 +1,174 @@+{-# LANGUAGE FlexibleInstances     #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE TupleSections         #-}++module DepTrack (+    DepTrackT+  , track+  , declare+  , ToDep (..)+  , dep+  , evalDeps+  , value+  , evalDepForest+  , evalDepGraph+  , evalDepForest1+  , GraphData+  , evalDepGraph1+  , buildGraph+  , inject+  ) where++import           Control.Applicative         (liftA)+import           Control.Monad.Writer.Strict (WriterT, writer, tell, runWriterT)+import           Data.DList                  (DList)+import qualified Data.DList                  as DList+import           Data.Graph                  (Graph, Vertex)+import qualified Data.Graph                  as Graph+import           Data.Map.Strict             (Map)+import qualified Data.Map.Strict             as Map+import           Data.Monoid                 ((<>))+import           Data.Set                    (Set)+import qualified Data.Set                    as Set+import           Data.Tree                   (Forest, Tree (..))+import qualified Data.Tree                   as Tree+import qualified Text.Parsec                 as Parsec++import           DepTrack.DepCrumb+import           DepTrack.Parsing++type DepTrackT a m = WriterT (DList (DepCrumb a)) m++-- | Declare the dependencies of a given computation.+declare :: (Monad m) => a -> DepTrackT a m b -> DepTrackT a m b+declare obj = track (const obj)++-- | Nests a computation within annotation to record the result of the+-- computation as a dependencies.+--+-- The computation to annotate is the second parameter.+track :: (Monad m) => (b -> a) -> DepTrackT a m b -> DepTrackT a m b+track f op = do+    push+    a <- op+    _ <- pop (f a)+    return a+  where+    push :: (Monad m) => DepTrackT a m ()+    push = tell (DList.singleton Push)++    pop :: (Monad m) => a -> DepTrackT a m a+    pop a = writer (a, DList.singleton (Pop a))++-- | Artificially injects dependencies from a computation to the+-- dependencies of another given computation.+--+-- Beware that one can easily create dependency cycles when using inject.+-- This function is however necessary when you have no control over some+-- library code and you want to artificially wrap it with new dependencies.+inject :: (Monad m) => DepTrackT a m b -> DepTrackT a m c -> DepTrackT a m (b, c)+inject m1 m2 = do+    spadeIn+    a <- m1+    spadeMiddle+    b <- m2+    spadeOut+    return (a,b)+  where+    spadeIn :: (Monad m) => DepTrackT a m ()+    spadeIn = tell (DList.singleton SpadeIn)+    spadeMiddle :: (Monad m) => DepTrackT a m ()+    spadeMiddle = tell (DList.singleton SpadeMiddle)+    spadeOut :: (Monad m) => DepTrackT a m ()+    spadeOut = tell (DList.singleton SpadeOut)++forestToPairs :: Forest a -> [(a,[a])]+forestToPairs = concatMap treeToPairs++treeToPairs :: Tree a -> [(a,[a])]+treeToPairs (Node x ts) = directDeps : childrenDeps+  where+    directDeps = (x, fmap Tree.rootLabel ts)+    childrenDeps = forestToPairs ts++mapGraphFromForest :: Ord k => (a -> k) -> Forest a -> Map k (a, Set k)+mapGraphFromForest fKey ts = Map.fromListWithKey f (formatPairs ts)+  where+    f _ (a,xs) (_,ys) = (a, xs <> ys)+    formatPairs = fmap (\(x,ys) -> (fKey x, (x, Set.fromList (fmap fKey ys)))) . forestToPairs++graphFromMap :: Ord k => Map k (a, Set k) -> GraphData a k+graphFromMap = Graph.graphFromEdges . fmap formatPair . Map.toList+  where+    formatPair (k, (a, ks)) = (a, k, Set.toList ks)++-- | Builds a Graph with auxilliary from nodes in a Forest.+--+-- The identity of a node in the forest is given using a key-projection+-- function.+buildGraph :: Ord k => (a -> k) -> Forest a -> GraphData a k+buildGraph f ts = graphFromMap $ mapGraphFromForest f ts++-- | Evaluates a computation, dropping the trace of dependencies.+value :: (Monad m) => DepTrackT a m b -> m b+value = fmap fst . runWriterT++-- | Evaluates a computation, tracking dependencies as a sequence of+-- dependency-tracking actions (crumbs).+evalDeps :: DepTrackT a m b -> m (b, DList (DepCrumb a))+evalDeps = runWriterT++-- | Evaluates a computation, tracking dependencies as a forest.+evalDepForest :: (Monad m, Show a) =>+  DepTrackT a m b -> m (b, Either Parsec.ParseError (Forest a))+evalDepForest = (fmap . fmap) f . evalDeps+  where+    f crumbs = let crumbs' = DList.toList crumbs+               in Parsec.parse dependencies "" crumbs'++-- | Evaluates a computation, tracking dependencies as a forest.+evalDepForest1 :: (Monad m, Show a) =>+  DepTrackT a m b -> m (b, Forest a)+evalDepForest1 = liftA (fmap (fromRight "deptrack is broken")) . evalDepForest++fromRight :: String -> Either a b -> b+fromRight _ (Right x) = x+fromRight msg (Left _)  = error msg++-- | General type for graphs of computations+type GraphData a k = ( Graph+                       -- The underlying abtract directed `Graph` structure+                     , Vertex -> (a, k, [k])+                       -- For each `Vertex` in the graph, provides associated data `a`, key `k` and+                       -- a list of keys to linked vertices+                     , k -> Maybe Vertex+                       -- Retrieves actual `Vertex` from its key+                     )++-- | Evaluates a computation, tracking dependencies as a graph with an+-- auxilliary function.+--+-- Node identity is determined using a projection function.+evalDepGraph :: (Monad m, Ord k, Show a) =>+                DepTrackT a m b  -- ^ The dependency tracked computation+             -> (a -> k)         -- ^ How to get a key from a node's data+             -> m (b, Either Parsec.ParseError (GraphData a k))+evalDepGraph x fKey = (fmap . fmap . fmap) (buildGraph fKey) (evalDepForest x)++evalDepGraph1 :: (Monad m, Ord k, Show a) =>+  DepTrackT a m b -> (a -> k) -> m (b, GraphData a k)+evalDepGraph1 x fKey = liftA (fmap (fromRight "deptrack is broken")) $ evalDepGraph x fKey++-- | Convenience typeclass to decouple the definition of projection functions+-- to dependency nodes.+--+-- This typeclass allows to write dep-recording code once and specialize the+-- type of node by only switching the parameter.+class ToDep a b where+   toDep :: a -> b++-- | Like track but using the projection function resolved from the ToDep+-- typeclass.+dep :: (ToDep a b, Monad m) =>+  DepTrackT b m a -> DepTrackT b m a+dep = track toDep

@@ -0,0 +1,10 @@+{-# LANGUAGE DeriveFunctor #-}++module DepTrack.DepCrumb (+    DepCrumb (..)+  ) where++data DepCrumb a+  = Push | Pop a       -- push a level, record the poped value+  | SpadeIn | SpadeMiddle | SpadeOut -- wraps a node+  deriving (Functor, Show)

@@ -0,0 +1,88 @@++module DepTrack.Parsing (+   dependencies+ ) where++import           Control.Applicative ((<|>))++import           Data.Tree           (Forest, Tree (..))+import           Text.Parsec         (ParsecT, (<?>))+import qualified Text.Parsec         as Parsec+import           Text.Parsec.Prim    (tokenPrim)++import           DepTrack.DepCrumb++-- | Parser to transform a well-formed list of DepCrumb into a Forest of+-- dependencies.+--+-- The (Show a) requirements exists to be able to display error while parsing.+dependencies :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (Forest a)+dependencies = forest <* Parsec.eof++forest :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (Forest a)+forest = fmap concat $ Parsec.many (simpleForest <|> spade <?> "forest")++simpleForest :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (Forest a)+simpleForest = Parsec.many1 tree <?> "simple-forest"++spade :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (Forest a)+spade = merge <$> (spadeIn *> forest <* spadeMiddle) <*> (forest <* spadeOut)+  where merge :: Forest a -> Forest a -> Forest a+        merge [] children      = children+        merge parents children = fmap (appendChildren children) parents++        appendChildren :: Forest a -> Tree a -> Tree a+        appendChildren zs (Node x ys) = Node x (ys ++ zs)++tree :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (Tree a)+tree = Parsec.try leaf+   <|> Parsec.try parent+   <?> "tree"++parent :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (Tree a)+parent = f <$> (push *> forest) <*> pop <?> "parent"+  where f xs popx = Node (unsafeFromPop popx) xs++leaf :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (Tree a)+leaf = pure . unsafeFromPop <$> (push *> pop) <?> "leaf"++push :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (DepCrumb a)+push = satisfy isPush <?> "Push"++pop :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (DepCrumb a)+pop = satisfy isPop <?> "Pop"++spadeIn :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (DepCrumb a)+spadeIn = satisfy isSpadeIn <?> "SpadeIn"++spadeMiddle :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (DepCrumb a)+spadeMiddle = satisfy isSpadeMiddle <?> "SpadeMiddle"++spadeOut :: (Monad m, Show a) => ParsecT [DepCrumb a] () m (DepCrumb a)+spadeOut = satisfy isSpadeOut <?> "SpadeOut"++isPop,isPush,isSpadeIn,isSpadeMiddle,isSpadeOut :: DepCrumb a -> Bool+isPop (Pop _) = True+isPop _       = False++isPush (Push) = True+isPush _      = False++isSpadeIn SpadeIn = True+isSpadeIn _ = False++isSpadeMiddle SpadeMiddle = True+isSpadeMiddle _ = False++isSpadeOut SpadeOut = True+isSpadeOut _ = False++unsafeFromPop :: DepCrumb a -> a+unsafeFromPop (Pop x) = x+unsafeFromPop _ = error "partial function, not a Pop"++satisfy :: (Monad m, Show a) => (DepCrumb a -> Bool) -> ParsecT [DepCrumb a] () m (DepCrumb a)+satisfy f = tokenPrim showDepCrumb nextPos testDepCrumb+  where showDepCrumb = show+        testDepCrumb x = if f x then Just x else Nothing+        nextPos pos _ _ = Parsec.incSourceColumn pos 1