kenshou-core-0.1.0.0: src/Kenshou/Plan/Components.hs
{-# LANGUAGE FieldSelectors #-}
{-# LANGUAGE TemplateHaskell #-}
module Kenshou.Plan.Components
( ComponentId (..),
SubId (..),
ComponentRef (..),
EdgeKind (..),
ComponentKind (..),
ChangeImplies (..),
Subcomponent (..),
DependencyEdge (..),
Component (..),
PathEffect (..),
RepositoryPathRule (..),
ComponentGraph (..),
Affected (..),
GraphProblem (..),
GraphError (..),
selftestGraph,
selftestGraphBytes,
loadGraphFile,
decodeGraph,
validateGraph,
parseRef,
renderRef,
dependents,
graphDigest,
componentById,
selectorsForRef,
minPolicyForRef,
)
where
import Data.Aeson
import Data.Aeson.Types (Parser)
import Data.ByteString (ByteString)
import Data.ByteString qualified as ByteString
import Data.FileEmbed (embedFile)
import Data.Graph (SCC (..), stronglyConnComp)
import Data.List (group, nub, sort)
import Data.Map.Strict (Map)
import Data.Map.Strict qualified as Map
import Data.Sequence (Seq (..), (|>))
import Data.Sequence qualified as Seq
import Data.Set (Set)
import Data.Set qualified as Set
import Data.Text (Text)
import Data.Text qualified as Text
import Kenshou.Core.Canonical (canonicalEncode, sha256Hex)
import Kenshou.Plan.Selector (Selector, parseSelector, renderSelector)
newtype ComponentId = ComponentId {unComponentId :: Text}
deriving stock (Eq, Ord, Show)
newtype SubId = SubId {unSubId :: Text}
deriving stock (Eq, Ord, Show)
data ComponentRef = ComponentRef {component :: ComponentId, sub :: Maybe SubId}
deriving stock (Eq, Ord, Show)
data EdgeKind = Build | Runtime deriving stock (Eq, Ord, Show)
data ComponentKind = Library | Migrations | Service | Harness | Assembly
deriving stock (Eq, Ord, Show)
newtype ChangeImplies = ChangeImplies {minDimensionPolicy :: Text}
deriving stock (Eq, Show)
data Subcomponent = Subcomponent
{ id :: SubId,
pathPrefixes :: [FilePath],
selectors :: [Selector],
uses :: [SubId],
changeImplies :: Maybe ChangeImplies
}
deriving stock (Eq, Show)
data DependencyEdge = DependencyEdge
{ to :: ComponentId,
kind :: EdgeKind,
toSubs :: [SubId],
fromSubs :: [SubId]
}
deriving stock (Eq, Show)
data Component = Component
{ id :: ComponentId,
kind :: ComponentKind,
uri :: Maybe Text,
repository :: Text,
sourceRoots :: [FilePath],
packages :: [Text],
selectors :: [Selector],
changeImplies :: Maybe ChangeImplies,
verifiedAgainst :: Text,
subcomponents :: [Subcomponent],
dependsOn :: [DependencyEdge]
}
deriving stock (Eq, Show)
data PathEffect = PathAll | PathNothing | PathCohort | PathSelectors [Selector]
deriving stock (Eq, Show)
data RepositoryPathRule = RepositoryPathRule {prefix :: FilePath, effect :: PathEffect}
deriving stock (Eq, Show)
data ComponentGraph = ComponentGraph
{ schema :: Text,
ignoredPackages :: [Text],
components :: [Component],
repositoryPaths :: [RepositoryPathRule]
}
deriving stock (Eq, Show)
data Affected = Affected
{ ref :: ComponentRef,
origin :: ComponentRef,
path :: [ComponentRef],
distance :: Int
}
deriving stock (Eq, Show)
newtype GraphProblem = GraphProblem {problemText :: Text}
deriving stock (Eq, Ord, Show)
newtype GraphError = GraphError {errorText :: Text}
deriving stock (Eq, Show)
selftestGraphBytes :: ByteString
selftestGraphBytes = $(embedFile "data/components.json")
selftestGraph :: Either GraphError ComponentGraph
selftestGraph = decodeGraph selftestGraphBytes
loadGraphFile :: FilePath -> IO (Either GraphError ComponentGraph)
loadGraphFile path = decodeGraph <$> ByteString.readFile path
decodeGraph :: ByteString -> Either GraphError ComponentGraph
decodeGraph bytes = case eitherDecodeStrict' bytes of
Left err -> Left (GraphError (Text.pack err))
Right graph -> case validateGraph graph of
[] -> Right graph
problems -> Left (GraphError (Text.intercalate "; " (fmap (.problemText) problems)))
validateGraph :: ComponentGraph -> [GraphProblem]
validateGraph graph =
schemaProblems
<> duplicateComponentProblems
<> duplicatePackageProblems
<> concatMap validateComponent graph.components
<> cycleProblems
where
componentIds = Set.fromList (fmap (.id) graph.components)
schemaProblems = [GraphProblem ("unsupported component graph schema " <> graph.schema) | graph.schema /= "kenshou.component-graph/v1"]
duplicateComponentProblems = duplicateProblems "component" (fmap (unComponentId . (.id)) graph.components)
duplicatePackageProblems = duplicateProblems "package" (concatMap (.packages) graph.components)
validateComponent componentValue =
duplicateProblems ("subcomponent of " <> unComponentId componentValue.id) (fmap (unSubId . (.id)) componentValue.subcomponents)
<> concatMap (validateEdge componentValue) componentValue.dependsOn
<> concatMap (validateSub componentValue) componentValue.subcomponents
validateEdge componentValue edge =
[GraphProblem (unComponentId componentValue.id <> ": unknown dependency " <> unComponentId edge.to) | edge.to `Set.notMember` componentIds]
<> case componentById graph edge.to of
Nothing -> []
Just target ->
[ GraphProblem (unComponentId componentValue.id <> ": unknown target subcomponent " <> unSubId subId)
| subId <- edge.toSubs,
subId `notElem` fmap (.id) target.subcomponents
]
<> [ GraphProblem (unComponentId componentValue.id <> ": unknown source subcomponent " <> unSubId subId)
| subId <- edge.fromSubs,
subId `notElem` fmap (.id) componentValue.subcomponents
]
validateSub componentValue subcomponentValue =
[ GraphProblem (unComponentId componentValue.id <> ": " <> unSubId subcomponentValue.id <> " uses unknown subcomponent " <> unSubId used)
| used <- subcomponentValue.uses,
used `notElem` fmap (.id) componentValue.subcomponents
]
cycleProblems =
[ GraphProblem ("component dependency cycle: " <> Text.intercalate " -> " (sort (fmap (unComponentId . (.id)) members)))
| CyclicSCC members <- stronglyConnComp [(componentValue, componentValue.id, fmap (.to) componentValue.dependsOn) | componentValue <- graph.components]
]
duplicateProblems :: Text -> [Text] -> [GraphProblem]
duplicateProblems label values =
[GraphProblem ("duplicate " <> label <> " " <> value) | entries@(value : _) <- group (sort values), length entries > 1]
componentById :: ComponentGraph -> ComponentId -> Maybe Component
componentById graph wanted = Map.lookup wanted (Map.fromList [(componentValue.id, componentValue) | componentValue <- graph.components])
parseRef :: ComponentGraph -> Text -> Either Text ComponentRef
parseRef graph raw = case Text.splitOn ":" raw of
[componentText] -> do
let componentId = ComponentId componentText
case componentById graph componentId of
Nothing -> Left ("unknown component " <> raw)
Just _ -> Right (ComponentRef componentId Nothing)
[componentText, subText] -> do
let componentId = ComponentId componentText
subId = SubId subText
componentValue <- maybe (Left ("unknown component " <> componentText)) Right (componentById graph componentId)
if subId `elem` fmap (.id) componentValue.subcomponents
then Right (ComponentRef componentId (Just subId))
else Left ("unknown subcomponent " <> raw)
_ -> Left ("invalid component reference " <> raw)
renderRef :: ComponentRef -> Text
renderRef reference = unComponentId reference.component <> maybe "" ((":" <>) . unSubId) reference.sub
dependents :: ComponentGraph -> Set ComponentRef -> Map ComponentRef Affected
dependents graph origins = go initialQueue initialMap
where
seeded = concatMap expandOrigin (Set.toAscList origins)
expandOrigin originRef@(ComponentRef componentId Nothing) =
(originRef, Affected originRef originRef [originRef] 0)
: case componentById graph componentId of
Nothing -> []
Just componentValue ->
[ let subRef = ComponentRef componentId (Just subcomponentValue.id)
in (subRef, Affected subRef originRef [originRef, subRef] 0)
| subcomponentValue <- componentValue.subcomponents
]
expandOrigin originRef = [(originRef, Affected originRef originRef [originRef] 0)]
initialMap = Map.fromListWith chooseShorter seeded
initialQueue = Seq.fromList (Map.keys initialMap)
go Empty results = results
go (current :<| rest) results =
let currentAffected = results Map.! current
candidates = fmap (mkAffected currentAffected) (neighbors current)
(results', queue') = foldl insertCandidate (results, rest) candidates
in go queue' results'
mkAffected previous next =
Affected next previous.origin (previous.path <> [next]) (previous.distance + if next.component == previous.ref.component then 0 else 1)
insertCandidate (results, queue) candidate = case Map.lookup candidate.ref results of
Just existing | existing.distance <= candidate.distance -> (results, queue)
_ -> (Map.insert candidate.ref candidate results, queue |> candidate.ref)
chooseShorter left right = if left.distance <= right.distance then left else right
neighbors target = nub (siblingUsers target <> edgeUsers target)
siblingUsers (ComponentRef componentId (Just subId)) = case componentById graph componentId of
Nothing -> []
Just componentValue -> [ComponentRef componentId (Just sibling.id) | sibling <- componentValue.subcomponents, subId `elem` sibling.uses]
siblingUsers (ComponentRef componentId Nothing) = case componentById graph componentId of
Nothing -> []
Just componentValue
| null componentValue.selectors -> fmap (ComponentRef componentId . Just . (.id)) componentValue.subcomponents
| otherwise -> []
edgeUsers target = concatMap (sourceFor target) graph.components
sourceFor target source = concatMap (edgeSource target source) source.dependsOn
edgeSource target source edge
| edge.to /= target.component = []
| not (targetMatches target edge) = []
| null edge.fromSubs = [ComponentRef source.id Nothing]
| otherwise = fmap (ComponentRef source.id . Just) edge.fromSubs
targetMatches (ComponentRef _ Nothing) _ = True
targetMatches (ComponentRef _ (Just subId)) edge = null edge.toSubs || subId `elem` edge.toSubs
selectorsForRef :: ComponentGraph -> ComponentRef -> [Selector]
selectorsForRef graph (ComponentRef componentId Nothing) = maybe [] (.selectors) (componentById graph componentId)
selectorsForRef graph (ComponentRef componentId (Just subId)) = do
componentValue <- maybe [] pure (componentById graph componentId)
subcomponentValue <- filter ((== subId) . (.id)) componentValue.subcomponents
subcomponentValue.selectors
minPolicyForRef :: ComponentGraph -> ComponentRef -> Maybe Text
minPolicyForRef graph (ComponentRef componentId Nothing) = do
componentValue <- componentById graph componentId
implies <- componentValue.changeImplies
pure implies.minDimensionPolicy
minPolicyForRef graph (ComponentRef componentId (Just subId)) = do
componentValue <- componentById graph componentId
subcomponentValue <- case filter ((== subId) . (.id)) componentValue.subcomponents of [] -> Nothing; value : _ -> Just value
implies <- subcomponentValue.changeImplies
pure implies.minDimensionPolicy
graphDigest :: ComponentGraph -> Text
graphDigest = sha256Hex . canonicalEncode . toJSON
instance FromJSON ComponentGraph where
parseJSON = withObject "ComponentGraph" \value -> ComponentGraph <$> value .: "schema" <*> value .:? "ignoredPackages" .!= [] <*> value .: "components" <*> value .: "repositoryPaths"
instance ToJSON ComponentGraph where
toJSON graph = object ["schema" .= graph.schema, "ignoredPackages" .= graph.ignoredPackages, "components" .= graph.components, "repositoryPaths" .= graph.repositoryPaths]
instance FromJSON Component where
parseJSON = withObject "Component" \value ->
Component <$> value .: "id" <*> value .: "kind" <*> value .:? "uri" <*> value .: "repository" <*> value .:? "sourceRoots" .!= [] <*> value .:? "packages" .!= [] <*> parseSelectors value <*> value .:? "changeImplies" <*> value .:? "verifiedAgainst" .!= "" <*> value .:? "subcomponents" .!= [] <*> value .:? "dependsOn" .!= []
instance ToJSON Component where
toJSON componentValue = object ["id" .= componentValue.id, "kind" .= componentValue.kind, "uri" .= componentValue.uri, "repository" .= componentValue.repository, "sourceRoots" .= componentValue.sourceRoots, "packages" .= componentValue.packages, "selectors" .= fmap renderSelector componentValue.selectors, "changeImplies" .= componentValue.changeImplies, "verifiedAgainst" .= componentValue.verifiedAgainst, "subcomponents" .= componentValue.subcomponents, "dependsOn" .= componentValue.dependsOn]
instance FromJSON Subcomponent where
parseJSON = withObject "Subcomponent" \value -> Subcomponent <$> value .: "id" <*> value .:? "pathPrefixes" .!= [] <*> parseSelectors value <*> value .:? "uses" .!= [] <*> value .:? "changeImplies"
instance ToJSON Subcomponent where
toJSON subcomponentValue = object ["id" .= subcomponentValue.id, "pathPrefixes" .= subcomponentValue.pathPrefixes, "selectors" .= fmap renderSelector subcomponentValue.selectors, "uses" .= subcomponentValue.uses, "changeImplies" .= subcomponentValue.changeImplies]
parseSelectors :: Object -> Parser [Selector]
parseSelectors value = do
raw <- value .:? "selectors" .!= []
traverse (either (fail . Text.unpack) pure . parseSelector) raw
instance FromJSON DependencyEdge where
parseJSON = withObject "DependencyEdge" \value -> DependencyEdge <$> value .: "to" <*> value .: "kind" <*> value .:? "toSubs" .!= [] <*> value .:? "fromSubs" .!= []
instance ToJSON DependencyEdge where
toJSON edge = object ["to" .= edge.to, "kind" .= edge.kind, "toSubs" .= edge.toSubs, "fromSubs" .= edge.fromSubs]
instance FromJSON RepositoryPathRule where
parseJSON = withObject "RepositoryPathRule" \value -> RepositoryPathRule <$> value .: "prefix" <*> value .: "effect"
instance ToJSON RepositoryPathRule where toJSON rule = object ["prefix" .= rule.prefix, "effect" .= rule.effect]
instance FromJSON PathEffect where
parseJSON = withObject "PathEffect" \value ->
value .: "kind" >>= \case
("all" :: Text) -> pure PathAll
"nothing" -> pure PathNothing
"cohort" -> pure PathCohort
"selectors" -> PathSelectors <$> parseSelectors value
other -> fail ("unknown path effect " <> Text.unpack other)
instance ToJSON PathEffect where
toJSON PathAll = object ["kind" .= ("all" :: Text)]
toJSON PathNothing = object ["kind" .= ("nothing" :: Text)]
toJSON PathCohort = object ["kind" .= ("cohort" :: Text)]
toJSON (PathSelectors selectors) = object ["kind" .= ("selectors" :: Text), "selectors" .= fmap renderSelector selectors]
instance FromJSON ChangeImplies where parseJSON = withObject "ChangeImplies" \value -> ChangeImplies <$> value .: "minDimensionPolicy"
instance ToJSON ChangeImplies where toJSON value = object ["minDimensionPolicy" .= value.minDimensionPolicy]
instance FromJSON ComponentId where parseJSON = withText "ComponentId" (pure . ComponentId)
instance ToJSON ComponentId where toJSON = toJSON . unComponentId
instance FromJSON SubId where parseJSON = withText "SubId" (pure . SubId)
instance ToJSON SubId where toJSON = toJSON . unSubId
instance FromJSON EdgeKind where parseJSON = withText "EdgeKind" \case "build" -> pure Build; "runtime" -> pure Runtime; other -> fail ("unknown edge kind " <> Text.unpack other)
instance ToJSON EdgeKind where toJSON Build = String "build"; toJSON Runtime = String "runtime"
instance FromJSON ComponentKind where parseJSON = withText "ComponentKind" \case "library" -> pure Library; "migrations" -> pure Migrations; "service" -> pure Service; "harness" -> pure Harness; "assembly" -> pure Assembly; other -> fail ("unknown component kind " <> Text.unpack other)
instance ToJSON ComponentKind where toJSON Library = String "library"; toJSON Migrations = String "migrations"; toJSON Service = String "service"; toJSON Harness = String "harness"; toJSON Assembly = String "assembly"