hydra-kernel-0.18.0: src/main/haskell/Hydra/Core/Unification.hs
-- Note: this is an automatically generated file. Do not edit.
-- | Utilities for type unification.
module Hydra.Core.Unification where
import qualified Hydra.Core.Ast as Ast
import qualified Hydra.Core.Coders as Coders
import qualified Hydra.Core.Diff as Diff
import qualified Hydra.Core.Docs as Docs
import qualified Hydra.Core.Error.Checking as Checking
import qualified Hydra.Core.Error.File as ErrorFile
import qualified Hydra.Core.Error.Model as ErrorModel
import qualified Hydra.Core.Error.Packaging as ErrorPackaging
import qualified Hydra.Core.Error.System as ErrorSystem
import qualified Hydra.Core.Errors as Errors
import qualified Hydra.Core.File as File
import qualified Hydra.Core.Graph as Graph
import qualified Hydra.Core.Json.Model as JsonModel
import qualified Hydra.Core.Overlay.Haskell.Lib.Eithers as Eithers
import qualified Hydra.Core.Overlay.Haskell.Lib.Equality as Equality
import qualified Hydra.Core.Overlay.Haskell.Lib.Lists as Lists
import qualified Hydra.Core.Overlay.Haskell.Lib.Logic as Logic
import qualified Hydra.Core.Overlay.Haskell.Lib.Maps as Maps
import qualified Hydra.Core.Overlay.Haskell.Lib.Optionals as Optionals
import qualified Hydra.Core.Overlay.Haskell.Lib.Pairs as Pairs
import qualified Hydra.Core.Overlay.Haskell.Lib.Strings as Strings
import qualified Hydra.Core.Markdown as Markdown
import qualified Hydra.Core.Model as Model
import qualified Hydra.Core.Packaging as Packaging
import qualified Hydra.Core.Parsing as Parsing
import qualified Hydra.Core.Paths as Paths
import qualified Hydra.Core.Print.Model as PrintModel
import qualified Hydra.Core.Query as Query
import qualified Hydra.Core.Regex as Regex
import qualified Hydra.Core.Relational as Relational
import qualified Hydra.Core.Rewriting as Rewriting
import qualified Hydra.Core.Strip as Strip
import qualified Hydra.Core.Substitution as Substitution
import qualified Hydra.Core.System as System
import qualified Hydra.Core.Tabular as Tabular
import qualified Hydra.Core.Testing as Testing
import qualified Hydra.Core.Time as Time
import qualified Hydra.Core.Topology as Topology
import qualified Hydra.Core.Typed as Typed
import qualified Hydra.Core.Typing as Typing
import qualified Hydra.Core.Util as Util
import qualified Hydra.Core.Validation as Validation
import qualified Hydra.Core.Variants as Variants
import Prelude hiding (Enum, Ordering, decodeFloat, encodeFloat, fail, lines, map, pure, sum, unlines)
import qualified Data.Scientific as Sci
import Data.Void
import qualified Data.Map as M
-- | Join two types, producing a list of type constraints.The comment is used to provide context for the constraints.
joinTypes :: t0 -> Model.Type -> Model.Type -> String -> Either Errors.UnificationError [Typing.TypeConstraint]
joinTypes cx left right comment =
let sleft = Strip.deannotateType left
sright = Strip.deannotateType right
joinOne =
\l -> \r -> Typing.TypeConstraint {
Typing.typeConstraintLeft = l,
Typing.typeConstraintRight = r,
Typing.typeConstraintComment = (Strings.concat2 "join types; " comment)}
cannotUnify =
Left (Errors.UnificationError {
Errors.unificationErrorLeftType = sleft,
Errors.unificationErrorRightType = sright,
Errors.unificationErrorMessage = (Strings.concat2 (Strings.concat2 (Strings.concat2 "cannot unify " (PrintModel.type_ sleft)) " with ") (PrintModel.type_ sright))})
assertEqual = Logic.ifElse (Equality.equal sleft sright) (Right []) cannotUnify
joinList =
\lefts -> \rights -> Logic.ifElse (Equality.equal (Lists.length lefts) (Lists.length rights)) (Right (Lists.zipWith joinOne lefts rights)) cannotUnify
joinRowTypes =
\left2 -> \right2 -> Logic.ifElse (Logic.and (Equality.equal (Lists.length (Lists.map Model.fieldTypeName left2)) (Lists.length (Lists.map Model.fieldTypeName right2))) (Lists.foldl (\acc -> \x -> Logic.and acc x) True (Lists.zipWith (\left3 -> \right3 -> Equality.equal (Model.unName left3) (Model.unName right3)) (Lists.map Model.fieldTypeName left2) (Lists.map Model.fieldTypeName right2)))) (joinList (Lists.map Model.fieldTypeType left2) (Lists.map Model.fieldTypeType right2)) cannotUnify
in case sleft of
Model.TypeApplication v0 -> case sright of
Model.TypeApplication v1 -> Right [
joinOne (Model.applicationTypeFunction v0) (Model.applicationTypeFunction v1),
(joinOne (Model.applicationTypeArgument v0) (Model.applicationTypeArgument v1))]
_ -> cannotUnify
Model.TypeEither v0 -> case sright of
Model.TypeEither v1 -> Right [
joinOne (Model.eitherTypeLeft v0) (Model.eitherTypeLeft v1),
(joinOne (Model.eitherTypeRight v0) (Model.eitherTypeRight v1))]
_ -> cannotUnify
Model.TypeEffect v0 -> case sright of
Model.TypeEffect v1 -> Right [
joinOne v0 v1]
_ -> cannotUnify
Model.TypeFunction v0 -> case sright of
Model.TypeFunction v1 -> Right [
joinOne (Model.functionTypeDomain v0) (Model.functionTypeDomain v1),
(joinOne (Model.functionTypeCodomain v0) (Model.functionTypeCodomain v1))]
_ -> cannotUnify
Model.TypeList v0 -> case sright of
Model.TypeList v1 -> Right [
joinOne v0 v1]
_ -> cannotUnify
Model.TypeLiteral _ -> assertEqual
Model.TypeMap v0 -> case sright of
Model.TypeMap v1 -> Right [
joinOne (Model.mapTypeKeys v0) (Model.mapTypeKeys v1),
(joinOne (Model.mapTypeValues v0) (Model.mapTypeValues v1))]
_ -> cannotUnify
Model.TypeOptional v0 -> case sright of
Model.TypeOptional v1 -> Right [
joinOne v0 v1]
_ -> cannotUnify
Model.TypePair v0 -> case sright of
Model.TypePair v1 -> Right [
joinOne (Model.pairTypeFirst v0) (Model.pairTypeFirst v1),
(joinOne (Model.pairTypeSecond v0) (Model.pairTypeSecond v1))]
_ -> cannotUnify
Model.TypeRecord v0 -> case sright of
Model.TypeRecord v1 -> joinRowTypes v0 v1
_ -> cannotUnify
Model.TypeSet v0 -> case sright of
Model.TypeSet v1 -> Right [
joinOne v0 v1]
_ -> cannotUnify
Model.TypeUnion v0 -> case sright of
Model.TypeUnion v1 -> joinRowTypes v0 v1
_ -> cannotUnify
Model.TypeUnit -> case sright of
Model.TypeUnit -> Right []
_ -> cannotUnify
Model.TypeVoid -> case sright of
Model.TypeVoid -> Right []
_ -> cannotUnify
Model.TypeWrap v0 -> case sright of
Model.TypeWrap v1 -> Right [
joinOne v0 v1]
_ -> cannotUnify
_ -> cannotUnify
-- | Robinson's algorithm, following https://www.cs.cornell.edu/courses/cs6110/2017sp/lectures/lec23.pdf
-- | Specifically this is an implementation of the following rules:
-- | * Unify({(x, t)} ∪ E) = {t/x} Unify(E{t/x}) if x ∉ FV(t)
-- | * Unify(∅) = I (the identity substitution x ↦ x)
-- | * Unify({(x, x)} ∪ E) = Unify(E)
-- | * Unify({(f(s1, ..., sn), f(t1, ..., tn))} ∪ E) = Unify({(s1, t1), ..., (sn, tn)} ∪ E))
unifyTypeConstraints :: t0 -> M.Map Model.Name Model.TypeScheme -> [Typing.TypeConstraint] -> Either Errors.UnificationError Typing.TypeSubst
unifyTypeConstraints cx schemaTypes constraints =
let withConstraint =
\c -> \rest ->
let sleft = Strip.deannotateType (Typing.typeConstraintLeft c)
sright = Strip.deannotateType (Typing.typeConstraintRight c)
comment = Typing.typeConstraintComment c
bind =
\v -> \t ->
let subst = Substitution.singletonTypeSubst v t
withResult = \s -> Substitution.composeTypeSubst subst s
in (Eithers.map withResult (unifyTypeConstraints cx schemaTypes (Substitution.substituteInConstraints subst rest)))
tryBinding =
\v -> \t -> Logic.ifElse (variableOccursInType v t) (Left (Errors.UnificationError {
Errors.unificationErrorLeftType = sleft,
Errors.unificationErrorRightType = sright,
Errors.unificationErrorMessage = (Strings.concat2 (Strings.concat2 (Strings.concat2 (Strings.concat2 (Strings.concat2 (Strings.concat2 "Variable " (Model.unName v)) " appears free in type ") (PrintModel.type_ t)) " (") comment) ")")})) (bind v t)
isNominalSchemaType =
\ts -> case (Strip.deannotateType (Model.typeSchemeBody ts)) of
Model.TypeRecord _ -> True
Model.TypeUnion _ -> True
Model.TypeWrap _ -> True
_ -> False
tryBindOrSchema =
\v -> \t -> Optionals.match (Maps.lookup v schemaTypes) (tryBinding v t) (\ts -> Logic.ifElse (isNominalSchemaType ts) (Left (Errors.UnificationError {
Errors.unificationErrorLeftType = sleft,
Errors.unificationErrorRightType = sright,
Errors.unificationErrorMessage = (Strings.concat2 (Strings.concat2 (Strings.concat2 (Strings.concat2 (Strings.concat2 (Strings.concat2 "Cannot unify schema name " (Model.unName v)) " with type ") (PrintModel.type_ t)) " (") comment) ")")})) (tryBinding v t))
noVars =
let withConstraints = \constraints2 -> unifyTypeConstraints cx schemaTypes (Lists.concat2 constraints2 rest)
in (Eithers.bind (joinTypes cx sleft sright comment) withConstraints)
dflt =
case sright of
Model.TypeVariable v0 -> tryBindOrSchema v0 sleft
_ -> noVars
in case sleft of
Model.TypeVariable v0 -> case sright of
Model.TypeVariable v1 -> Logic.ifElse (Equality.equal (Model.unName v0) (Model.unName v1)) (unifyTypeConstraints cx schemaTypes rest) (Logic.ifElse (Optionals.isGiven (Maps.lookup v0 schemaTypes)) (Logic.ifElse (Optionals.isGiven (Maps.lookup v1 schemaTypes)) (Left (Errors.UnificationError {
Errors.unificationErrorLeftType = sleft,
Errors.unificationErrorRightType = sright,
Errors.unificationErrorMessage = (Strings.concat2 (Strings.concat2 (Strings.concat2 (Strings.concat2 (Strings.concat2 (Strings.concat2 "Attempted to unify schema names " (Model.unName v0)) " and ") (Model.unName v1)) " (") comment) ")")})) (bind v1 sleft)) (bind v0 sright))
_ -> tryBindOrSchema v0 sright
_ -> dflt
in (Optionals.match (Lists.uncons constraints) (Right Substitution.idTypeSubst) (\uc -> withConstraint (Pairs.first uc) (Pairs.second uc)))
-- | Unify two lists of types pairwise, producing a single substitution that satisfies every pair. The lists must have the same length; the comment is attached to each generated constraint for diagnostics.
unifyTypeLists :: t0 -> M.Map Model.Name Model.TypeScheme -> [Model.Type] -> [Model.Type] -> String -> Either Errors.UnificationError Typing.TypeSubst
unifyTypeLists cx schemaTypes l r comment =
let toConstraint =
\l2 -> \r2 -> Typing.TypeConstraint {
Typing.typeConstraintLeft = l2,
Typing.typeConstraintRight = r2,
Typing.typeConstraintComment = comment}
in (unifyTypeConstraints cx schemaTypes (Lists.zipWith toConstraint l r))
-- | Unify two types, producing a substitution that makes them equal (or an error). The comment is attached to the generated constraint for diagnostics.
unifyTypes :: t0 -> M.Map Model.Name Model.TypeScheme -> Model.Type -> Model.Type -> String -> Either Errors.UnificationError Typing.TypeSubst
unifyTypes cx schemaTypes l r comment =
unifyTypeConstraints cx schemaTypes [
Typing.TypeConstraint {
Typing.typeConstraintLeft = l,
Typing.typeConstraintRight = r,
Typing.typeConstraintComment = comment}]
-- | Determine whether a type variable appears within a type expression.No distinction is made between free and bound type variables.
variableOccursInType :: Model.Name -> Model.Type -> Bool
variableOccursInType var typ0 =
let tryType =
\b -> \typ -> case typ of
Model.TypeVariable v0 -> Logic.or b (Equality.equal (Model.unName v0) (Model.unName var))
_ -> b
in (Rewriting.foldOverType Coders.TraversalOrderPre tryType False typ0)