clafer-0.5.8: src/Language/Clafer/Generator/ChocoModel.hs
{-# LANGUAGE NamedFieldPuns #-}
{-
Copyright (C) 2012-2017 Jimmy Liang, Michal Antkiewicz, Rafael Olaechea <http://gsd.uwaterloo.ca>
Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is furnished to do
so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
-}
-- | The model the <https://github.com/gsdlab/chocosolver Chocosolver> solves, built by one walk
-- over the IR, which "Language.Clafer.Generator.Choco" prints as JavaScript and
-- "Language.Clafer.Generator.Explicit" as an explicit Clafer model, so that both give the same
-- model.
module Language.Clafer.Generator.ChocoModel
( CModel(..)
, CElement(..)
, CClafer(..)
, CExp(..)
, CDecl(..)
, CScope(..)
, chocoModel
) where
import Control.Applicative
import Control.Lens.Plated hiding (rewrite)
import Control.Monad
import Data.Data.Lens
import Data.List
import Data.Maybe
import Prelude hiding (exp)
import Language.Clafer.Common
import Language.Clafer.Intermediate.Intclafer
import Language.Clafer.Front.LexClafer
-- | A formula over the target of a reference, simplified when constant.
data Membership = MTrue | MFalse | MExp CExp
-- | The model chocosolver gets: its clafers and the elements in them, in the order of the IR.
data CModel = CModel
{ cmElements :: [CElement] -- ^ the top-level clafers, constraints, objectives and assertions
, cmScope :: CScope
, cmEscapes :: String -- ^ the [choco| |] escapes, JavaScript
}
data CElement
= CEClafer CClafer
| CEConstraint CExp
| CEAssert CExp -- ^ an assertion, quantified over its clafer if nested
| CEObjective Bool CExp -- ^ maximize, or minimize
data CClafer = CClafer
{ ccUid :: UID
, ccParent :: UID -- ^ "clafer" for a top-level abstract clafer, "root" for a top-level concrete one
, ccAbstract :: Bool
, ccModifiers :: [String] -- ^ its temporal modifiers, e.g., initial, final, finalref, which chocosolver does not read
, ccCard :: Maybe Interval -- ^ only if not 0..*
, ccGCard :: Maybe Interval -- ^ only if not 0..*
, ccLinked :: Bool -- ^ whether it has a super clafer or a reference in the IR
, ccSuper :: Maybe UID -- ^ a clafer
, ccRef :: Maybe (Bool, String) -- ^ its own reference: whether a set, and the target
, ccRefConstraints :: [CExp] -- ^ the constraints of a reference to a set expression
, ccElements :: [CElement]
}
-- | An expression, by the functions of chocosolver's JavaScript API.
data CExp
= CThis
| CGlobal UID -- ^ all instances of a clafer
| CName String -- ^ a local
| CInt Integer
| CStr String -- ^ a Clafer string literal, with its quotes
| CDouble Double
| CDecimal String -- ^ as written, with the fractional digits of the decimal scale
| CEmpty String -- ^ the empty set, typed by a clafer (or Int)
| CJoin CExp String
| CJoinRef CExp
| CJoinParent CExp
| CFun String [CExp] -- ^ a function of the API by its name, e.g., equal
| CQuant IQuant [CDecl] CExp -- ^ without declarations, a quantifier over a set, e.g., none(x)
data CDecl = CDecl Bool [String] CExp
-- | The scopes, as chocosolver solves the model with no options.
data CScope = CScope
{ csClafers :: [(UID, Integer)] -- ^ the scopes given, without int
, csIntRange :: Maybe (Integer, Integer)
, csStringLength :: Int
, csDecimalScale :: Maybe Integer -- ^ only if the model uses decimals or the scale is given
}
-- | The model of the IR, with the given scopes, smallest and largest integers, if any, number of
-- fractional digits of decimals, if given, and the tokens with the [choco| |] escapes
chocoModel :: (IModule, GEnv) -> [(UID, Integer)] -> (Maybe Integer, Maybe Integer) -> Maybe Integer -> [Token] -> CModel
chocoModel (imodule@IModule{_mDecls}, genv') scopes (minInt, maxInt) decimalDigits otherTokens' =
CModel
{ cmElements = mapMaybe (genElement "root") _mDecls
, cmScope = CScope
{ csClafers = [(uid', scope) | (uid', scope) <- scopes, uid' /= "int"]
-- Without --minint and --maxint, chocosolver chooses the range (-128..127
-- unless overridden on its command line).
, csIntRange = if isNothing minInt && isNothing maxInt then Nothing
else Just (fromMaybe (-128) minInt, fromMaybe 127 maxInt)
, csStringLength = longestString
, csDecimalScale = if usesDecimals || isJust decimalDigits then Just decimalScale else Nothing
}
, cmEscapes = genChocoEscapes
}
where
uidIClaferMap' = uidClaferMap genv'
genElement :: String -> IElement -> Maybe CElement
genElement _ (IEClafer c@IClafer{_uid, _card, _gcard, _super, _reference, _elements, _parentUID, _modifiers}) = Just $ CEClafer CClafer
{ ccUid = _uid
, ccParent = _parentUID
, ccAbstract = _abstract _modifiers
, ccModifiers = temporalModifiers' _modifiers _reference
, ccCard = nonDefault _card
, ccGCard = nonDefault $ _interval <$> _gcard
, ccLinked = isJust _super || isJust _reference
, ccSuper = superOf _uid
, ccRef = case (getReference c, _reference) of
(_, Just (IReference isSet' _ ref')) | isSetExp ref', Just target <- setExpType ref' -> Just (isSet', target)
([target], Just (IReference isSet' _ _)) -> Just (isSet', target)
_ -> Nothing
, ccRefConstraints = case _reference of
Just (IReference _ _ ref') | isSetExp ref', Just _ <- setExpType ref' -> genSetExpTarget ref'
_ -> []
, ccElements = mapMaybe (genElement _uid) _elements
}
genElement _ (IEConstraint True pexp) = Just $ CEConstraint $ genConstraintPExp pexp
genElement "root" (IEConstraint False pexp) = Just $ CEAssert $ genConstraintPExp pexp
-- chocosolver's assertions have no context: a nested assertion holds for each instance of its
-- clafer, so it is quantified over them, with `this` as the local this_, e.g., in clafer P:
-- assert(all([decl([this_ = local("this_")], global(P))], ... join(this_, age) ...)); the
-- instances of a nested clafer by the path from its top-level clafer, as clafer resolves
-- its name, e.g., machine . ctx
genElement pUID (IEConstraint False pexp) = Just $ CEAssert $
CQuant IAll [CDecl False [thisLocal] (instancesOf pUID)] (genConstraintPExp (transformOn biplate thisToLocal pexp))
where
thisToLocal e@IClaferId{_sident = "this"} = e{_sident = thisLocal}
thisToLocal e = e
instancesOf u
| isTopLevel c = CGlobal u
| otherwise = CJoin (instancesOf $ _parentUID c) u
where
c = claferWithUid u
genElement _ (IEGoal isMax PExp{_exp=IFunExp _ [pexp]}) = Just $ CEObjective isMax $ genConstraintPExp pexp
genElement _ _ = Nothing
thisLocal = "this_"
-- the temporal modifiers of a clafer: final, which implies finalref and finaltarget, or the
-- modifiers of its own reference or of the reference it inherits
temporalModifiers' IClaferModifiers{_initial, _final, _finalReferences} ref' =
[ "initial" | _initial ] ++ [ "final" | _final ] ++
[ refModifierKeyword m | not _final, m <- nub (maybe [] _refModifiers ref' ++ _finalReferences) ]
refModifierKeyword FinalRef = "finalref"
refModifierKeyword FinalTarget = "finaltarget"
refModifierKeyword FinalRefTarget = "final"
-- a card or group card, unless it is 0..*, which chocosolver has by default
nonDefault (Just (0, -1)) = Nothing
nonDefault i = i
superOf u =
case _super $ claferWithUid u of
Just (PExp{_exp = IClaferId{_sident}})
| _sident == baseClafer -> Nothing
| isPrimitive _sident -> Nothing
| otherwise -> Just _sident
_ -> Nothing
claferWithUid u = fromMaybe (error $ "claferWithUid: \"" ++ u ++ "\" is not a clafer") $ findIClafer uidIClaferMap' u
genChocoEscapes :: String
genChocoEscapes = concatMap printChocoEscape otherTokens'
where
printChocoEscape (PT _ (T_PosChoco code)) = let
code' = fromJust $ stripPrefix "[choco|" code
in
take (length code' - 2) code'
printChocoEscape _ = ""
exprs :: [IExp]
exprs = universeOn biplate imodule
stringLength :: IExp -> Maybe Int
stringLength (IStr string) = Just $ length string
stringLength _ = Nothing
longestString :: Int
longestString = maximum $ 16 : mapMaybe stringLength exprs
-- | The number of fractional digits of a decimal literal, as written, e.g., 2 for 2.50
fractionalDigits :: String -> Integer
fractionalDigits literal = genericLength $ drop 1 $ dropWhile (/= '.') literal
decimalLiterals :: [String]
decimalLiterals = [ literal | IDecimal literal <- exprs ]
-- | Whether the model has decimal literals or references to decimals
usesDecimals :: Bool
usesDecimals = not (null decimalLiterals) || any refersToDecimal (universeOn biplate imodule :: [IClafer])
where
refersToDecimal IClafer{_reference = Just IReference{_ref = ref'}} = decimalType `elem` getRefIds ref'
refersToDecimal _ = False
-- | The decimal scale: the largest number of fractional digits of the decimal literals,
-- unless given by --decimal-digits
decimalScale :: Integer
decimalScale = fromMaybe (maximum $ 0 : map fractionalDigits decimalLiterals) decimalDigits
-- | A decimal literal with the fractional digits of the decimal scale, e.g., 2.5 as 2.50
-- with 2 digits; with more digits, chocosolver reports that the literal does not fit.
genDecimal :: String -> String
genDecimal literal = literal ++ genericReplicate (decimalScale - fractionalDigits literal) '0'
-- an empty set of the clafer; with no clafer beside it, e.g., in #noclafer, of the model's
-- first clafer, since chocosolver neither counts nor quantifies sets of integers
emptyOf :: Maybe String -> CExp
emptyOf c = CEmpty $ fromMaybe "Int" (c <|> firstClafer)
firstClafer = listToMaybe [ _uid c | IEClafer c <- _mDecls ]
-- the clafer whose instances a set expression is of, e.g., c0_a for a, its type's first; for
-- an expression of the type of noclafer, e.g., a ** noclafer, that of an operand
claferOf :: PExp -> Maybe String
claferOf PExp{_iType = t, _exp = e} = (claferOfType =<< t) <|> case e of
IFunExp _ args' -> listToMaybe $ mapMaybe claferOf args'
_ -> Nothing
where
claferOfType (TClafer (u : _)) | u `notElem` [noClaferIdent, rootIdent, baseClafer] = Just u
claferOfType (TMap so _) = claferOfType so
claferOfType (TUnion (t' : _)) = claferOfType t'
claferOfType _ = Nothing
-- A reference to a set expression, e.g., `-> 1, 2, 3`, `-> integer -- 0` or
-- `-> Alice ++ Ella`, is a reference to a type containing all its values,
-- constrained to the values of the expression.
isSetExp :: PExp -> Bool
isSetExp PExp{_exp = IFunExp op' _} = op' `elem` ["++", "**", "--"]
isSetExp _ = False
-- | The type to reference: the primitive type of the values, or the nearest
-- common super of the clafers.
setExpType :: PExp -> Maybe String
setExpType ref' = case nub $ getRefIds ref' of
ids@(_:_) | all isPrimitive ids -> case sort $ nub $ map normalize ids of
[t] -> Just t
-- integers are decimals, e.g., in `-> 1, 2.5`
[d, i] | d == decimalType && i == integerType -> Just decimalType
_ -> Nothing
| not (any isPrimitive ids) -> commonSuper ids
_ -> Nothing
where
normalize "int" = "integer"
normalize t = t
commonSuper :: [String] -> Maybe String
commonSuper ids = case map supersOf ids of
(first:rest) -> find (\u -> all (u `elem`) rest) first
[] -> Nothing
where
supersOf uid' = uid' : maybe [] (tail . mapHierarchy _uid getSuper uidIClaferMap') (findIClafer uidIClaferMap' uid')
-- | Constrains the target of the reference to the values of the set expression.
genSetExpTarget :: PExp -> [CExp]
genSetExpTarget ref'
| Just _ <- setExpType ref', any isPrimitive (getRefIds ref') =
case member ref' of
MTrue -> []
MFalse -> [CQuant INo [] CThis]
MExp e' -> [e']
| otherwise = [CFun "$in" [CJoinRef CThis, genConstraintPExp ref']]
where
-- membership of the target in a set expression over primitives, as a formula
member PExp{_exp = IFunExp "++" [a, b]} = mOr (member a) (member b)
member PExp{_exp = IFunExp "**" [a, b]} = mAnd (member a) (member b)
member PExp{_exp = IFunExp "--" [a, b]} = mAnd (member a) (mNot $ member b)
member PExp{_exp = IClaferId{_sident}} | isPrimitive _sident = MTrue
member e' = MExp $ CFun "equal" [CJoinRef CThis, genConstraintPExp e']
mOr MTrue _ = MTrue
mOr _ MTrue = MTrue
mOr MFalse b = b
mOr a MFalse = a
mOr (MExp a) (MExp b) = MExp $ CFun "or" [a, b]
mAnd MFalse _ = MFalse
mAnd _ MFalse = MFalse
mAnd MTrue b = b
mAnd a MTrue = a
mAnd (MExp a) (MExp b) = MExp $ CFun "and" [a, b]
mNot MTrue = MFalse
mNot MFalse = MTrue
mNot (MExp a) = MExp $ CFun "not" [a]
rewrite :: PExp -> PExp
-- Rearrange right joins to left joins.
rewrite p1@PExp{_iType = Just _, _exp = IFunExp "." [p2, p3@PExp{_exp = IFunExp "." _}]} =
p1{_exp = IFunExp "." [p3{_iType = _iType p4, _exp = IFunExp "." [p2, p4]}, p5]}
where
PExp{_exp = IFunExp "." [p4, p5]} = rewrite p3
rewrite p1@PExp{_exp = IFunExp{_op = "-", _exps = [PExp{_exp = IInt i}]}} =
-- This is so that the output looks cleaner, no other purpose since the Choco optimizer
-- in the backend will treat the pre-rewritten expression the same.
p1{_exp = IInt (-i)}
rewrite p = p
genConstraintPExp :: PExp -> CExp
genConstraintPExp = genConstraintExp . _exp . rewrite
genConstraintExp :: IExp -> CExp
genConstraintExp (IDeclPExp quant' decls' body') =
CQuant quant' (map genDecl decls') (genConstraintPExp body')
where
genDecl (IDecl isDisj' locals body'') = CDecl isDisj' locals (genConstraintPExp body'')
genConstraintExp (IFunExp "." [PExp{_exp = IClaferId{_sident = "root"}}, e2]) =
genConstraintPExp e2
genConstraintExp (IFunExp "." [e1, PExp{_exp = IClaferId{_sident = "dref"}}]) =
CJoinRef $ genConstraintPExp e1
genConstraintExp (IFunExp "." [e1, PExp{_exp = IClaferId{_sident = "parent"}}]) =
CJoinParent $ genConstraintPExp e1
genConstraintExp (IFunExp "." [e1, PExp{_exp = IClaferId{_sident}}]) =
CJoin (genConstraintPExp e1) _sident
genConstraintExp (IFunExp "." [_, _]) =
error "Did not rewrite all joins to left joins."
-- the value of an initializer with temporal operators, which the explicit form shows as it
-- is: its context is the parent (gsdlab/clafer#123), which only the temporal output keeps
genConstraintExp (IFunExp op' [arg]) | op' == iInitValue =
genConstraintPExp arg
genConstraintExp (IFunExp "-" [arg]) =
CFun "minus" [genConstraintPExp arg]
genConstraintExp (IFunExp "-" [arg1, arg2]) =
CFun "sub" [genConstraintPExp arg1, genConstraintPExp arg2]
genConstraintExp (IFunExp "sum" args')
| [arg] <- args', PExp{_exp = IFunExp{_exps = [a, PExp{_exp = IClaferId{_sident = "dref"}}]}} <- rewrite arg =
CFun "sum" [genConstraintPExp a]
| [arg] <- args' =
CFun "sum" [genConstraintPExp arg]
| otherwise = error $ "[bug] Choco.genConstraintExp: Unexpected sum argument: " ++ show args'
genConstraintExp (IFunExp "product" args')
| [arg] <- args', PExp{_exp = IFunExp{_exps = [a, PExp{_exp = IClaferId{_sident = "dref"}}]}} <- rewrite arg =
CFun "product" [genConstraintPExp a]
| otherwise = error "Choco: Unexpected product argument."
genConstraintExp (IFunExp "+" args') =
CFun (if _iType (head args') == Just TString then "concat" else "add") (map genConstraintPExp args')
genConstraintExp (IFunExp op' args') =
CFun (mapFunc op') (map genArg args')
where
-- noclafer, the empty set, is an empty constant of the type of a set beside it, e.g.,
-- constant(c0_a) in if some extra then a else noclafer
genArg a
| isNoClafer a = emptyOf $ listToMaybe $ mapMaybe claferOf $ filter (not . isNoClafer) args'
| otherwise = genConstraintPExp a
-- noclafer alone, e.g., #noclafer
genConstraintExp IClaferId{_sident = "noclafer"} = emptyOf Nothing
genConstraintExp IClaferId{_sident = "this"} = CThis
genConstraintExp IClaferId{_sident}
| isJust $ findIClafer uidIClaferMap' _sident = CGlobal _sident
| otherwise = CName _sident
genConstraintExp (IInt val) = CInt val
genConstraintExp (IStr val) = CStr val
genConstraintExp (IDouble val) = CDouble val
genConstraintExp (IDecimal val) = CDecimal $ genDecimal val
genConstraintExp (IReal _) = error "no real numbers allowed"
mapFunc "!" = "not"
mapFunc "#" = "card"
mapFunc "min" = "minimum"
mapFunc "max" = "maximum"
mapFunc "<=>" = "ifOnlyIf"
mapFunc "=>" = "implies"
mapFunc "||" = "or"
mapFunc "xor" = "xor"
mapFunc "&&" = "and"
mapFunc "<" = "lessThan"
mapFunc ">" = "greaterThan"
mapFunc "=" = "equal"
mapFunc "<=" = "lessThanEqual"
mapFunc ">=" = "greaterThanEqual"
mapFunc "!=" = "notEqual"
mapFunc "in" = "$in"
mapFunc "not in" = "notIn"
mapFunc "+" = "add"
mapFunc "*" = "mul"
mapFunc "/" = "div"
mapFunc "%" = "mod"
mapFunc "++" = "union"
mapFunc "--" = "diff"
mapFunc "**" = "inter"
mapFunc "ifthenelse" = "ifThenElse"
-- the temporal operators, which chocosolver does not solve, by their names
mapFunc op' | op' `elem` ltlOps = op'
mapFunc op' = error $ "Choco: Unknown op: " ++ op'