clafer-0.5.8: src/Language/Clafer/Generator/AlloyLtl.hs
{-# LANGUAGE RankNTypes, FlexibleContexts #-}
{-
Copyright (C) 2012-2026 Kacper Bak, 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.
-}
{- | Generates Alloy 6 code with its native temporal logic for a dynamic Clafer model, one
with temporal operators or modifiers. The semantics follows Juodisius et al., Clafer:
Lightweight Modeling of Structure, Behaviour, and Variability (2019), section 5, with
two changes (an errata to the paper, which was never implemented):
* A trace is an infinite sequence of snapshots (Alloy's lasso traces).
* The signature of a clafer is the pool of all its instances over the trace. An instance
exists in a snapshot when its parent links it through the containment relation
@r_c@, which is @var@ unless the clafer is static (see 'isStatic'); @alive_c@ is the
set of the existing instances of @c@.
* An instance does not change its parent (the static field @p_c@), also when it
disappears and reappears, and nothing outlives its parent. A scope bounds the instances
of a clafer over the trace, not in a snapshot.
* Change: an instance may reappear. The paper forbids it, but then a cyclic behaviour,
e.g., green, yellow, red, green, ..., needs infinitely many instances, which no lasso
trace over finitely many atoms has.
* The multiplicities, group cardinalities and constraints of a clafer hold in every
snapshot, for every existing instance; the top-level ones hold in every snapshot.
* Change: the temporal obligations of a constraint (X, F, G and U, Alloy's @after@,
@eventually@, @always@ and @until@) hold while the parent of the context instance
exists; the paper does not bound them. So @[ req=down --> movingDown ]@ in the state
@movingUp@ takes the machine to @movingDown@, and the pending obligations of nested
states lapse when their enclosing state is left. A modeller extends the timeline of
a constraint by placing it higher in the hierarchy, or at the top level. A transition
of a clafer, e.g., @on --> off@, is a constraint of the clafer.
* The negations are pushed inside the temporal operators first (see 'pushNegations'),
so a negated obligation lapses with the parent too: @!(F error)@ is @G !error@.
* @initial@ children exist whenever their parent appears; the instances of a @final@
clafer do not change while their parent exists.
* @initially@ and @finally@ refer to the first and the last snapshot of the context
instance's lifetime.
-}
module Language.Clafer.Generator.AlloyLtl (genAlloyLtlModule, bindSelf, selfIdent) where
import Control.Monad.State
import Data.Char (isAlphaNum)
import Data.List
import Data.Maybe
import Prelude
import Language.Clafer.Common
import Language.Clafer.ClaferArgs
import Language.Clafer.Front.AbsClafer hiding (FinalRef, FinalTarget)
import Language.Clafer.Front.LexClafer
import Language.Clafer.Generator.Concat
import Language.Clafer.Intermediate.Intclafer hiding (exp)
data GenEnv = GenEnv
{ claferargs :: ClaferArgs
, uidIClaferMap :: UIDIClaferMap
, allClafers :: [IClafer] -- ^ the clafers of the model, without the root
, forScopes :: String
, contextInstance :: String -- ^ the context instance, @this@ unless in the value of an initializer
}
-- | Alloy 6 code generation
genAlloyLtlModule :: ClaferArgs -> (IModule, GEnv) -> [(UID, Integer)] -> [Token] -> (Result, [(Span, IrTrace)])
genAlloyLtlModule claferargs' (imodule, genv) scopes otherTokens' = (flatten output, filter ((/= NoTrace) . snd) $ mapLineCol output)
where
uidIClaferMap' = uidClaferMap genv
-- the clafers of the module, as the optimizer left them: the map of the environment still has
-- the abstract clafers that no concrete clafer extends, which the optimizer removed
root = (fromMaybe (error "AlloyLtl: missing root clafer") $ findIClafer uidIClaferMap' rootIdent)
{ _elements = _mDecls imodule }
clafers' = tail $ nestedClafers root
tl = trace_len claferargs'
genEnv = GenEnv claferargs' uidIClaferMap' clafers' forScopes' "this"
-- a scope bounds the instance identities across the trace, which may be reused when an
-- instance reappears; the multiplicities bound the existing instances in each snapshot
forScopes' = "for 1 but " ++ intercalate ", " (map (\(uid', scope') -> show scope' ++ " " ++ uid') scopes ++ [show tl ++ " steps"])
output = header genEnv otherTokens' +++ cconcat (map (genClafer genEnv) $ root : clafers')
nestedClafers :: IClafer -> [IClafer]
nestedClafers c = c : concatMap nestedClafers (getSubclafers $ _elements c)
header :: GenEnv -> [Token] -> Concat
header genEnv otherTokens' = CString $ unlines
[ "open util/integer"
, genAlloyEscapes otherTokens' ++ "pred show {}"
, if validate $ claferargs genEnv
then ""
else "run show " ++ forScopes genEnv
, ""]
genAlloyEscapes :: [Token] -> String
genAlloyEscapes otherTokens' = concatMap printAlloyEscape otherTokens'
where
printAlloyEscape (PT _ (T_PosAlloy code)) = let
code' = fromJust $ stripPrefix "[alloy|" code
in
take (length code' - 2) code' ++ "\n"
printAlloyEscape _ = ""
-- -----------------------------------------------------------------------------
-- the structure of the model
isRoot :: IClafer -> Bool
isRoot c = _uid c == rootIdent
-- | The parent of the clafer, the root for the top-level ones.
parentOf :: GenEnv -> IClafer -> Maybe IClafer
parentOf genEnv c
| isRoot c = Nothing
| isTopLevel c = findIClafer (uidIClaferMap genEnv) rootIdent
| otherwise = findIClafer (uidIClaferMap genEnv) $ _parentUID c
-- | A top-level abstract clafer has no containment relation; its instances are those of its subclafers.
hasContainment :: IClafer -> Bool
hasContainment c = not (isRoot c) && not (_isAbstract c && isTopLevel c)
-- | The children that the clafer contains through a containment relation.
containedClafers :: IClafer -> [IClafer]
containedClafers = filter hasContainment . getSubclafers . _elements
-- | Whether the containment relation of the clafer is static: the clafer is final and so
-- are its ancestors, so its instances exist in the whole trace (Juodisius et al., 6.2).
isStatic :: GenEnv -> IClafer -> Bool
isStatic genEnv c
| isRoot c = True
| otherwise = _isFinal c && maybe True (isStatic genEnv) (parentOf genEnv c)
-- | The nearest super clafer that declares a reference, and the reference.
inheritedReference :: GenEnv -> IClafer -> Maybe (IClafer, IReference)
inheritedReference genEnv c = listToMaybe
[ (s, r) | s <- tail $ findHierarchy getSuper (uidIClaferMap genEnv) c, Just r <- [_reference s] ]
-- | The direct subclafers of the clafer.
subsOf :: GenEnv -> IClafer -> [IClafer]
subsOf genEnv c = [ c' | c' <- allClafers genEnv, getSuper c' == [_uid c] ]
-- | The concrete clafers that are or extend the clafer.
concreteSubs :: GenEnv -> IClafer -> [IClafer]
concreteSubs genEnv c
| _isAbstract c = concatMap (concreteSubs genEnv) $ subsOf genEnv c
| otherwise = [c]
aliveName :: UID -> String
aliveName uid'
| uid' == rootIdent = rootIdent
| otherwise = "alive_" ++ uid'
genRelName :: String -> String
genRelName name = "r_" ++ name
genRefName :: String -> String
genRefName name = name ++ "_ref"
genParentName :: String -> String
genParentName name = "p_" ++ name
-- | The relation from the instances of the clafer to their existing parents. The parent of an
-- instance does not change, so the navigation also works after the instance disappeared.
-- An abstract clafer's instances are those of its concrete subclafers, which may have
-- other parents, e.g., the subclafers of a top-level abstract clafer.
parentRel :: GenEnv -> UID -> String
parentRel genEnv uid' = case findIClafer (uidIClaferMap genEnv) uid' of
Just c -> case map rel $ concreteSubs genEnv c of
[] -> "(none->none)"
[r] -> r
rels' -> "(" ++ intercalate " + " rels' ++ ")"
Nothing -> error $ "AlloyLtl.parentRel: clafer not found: " ++ uid'
where
rel c = "(@" ++ genParentName (_uid c) ++ " :> " ++ maybe rootIdent (aliveName . _uid) (parentOf genEnv c) ++ ")"
-- | The relation from the instances of the clafer to their parents, also those that do not exist:
-- the parent of an instance does not change.
fixedParentRel :: GenEnv -> IClafer -> String
fixedParentRel genEnv c = case map (("@" ++) . genParentName . _uid) $ concreteSubs genEnv c of
[] -> "(none->none)"
[r] -> "(" ++ r ++ ")"
rels' -> "(" ++ intercalate " + " rels' ++ ")"
mkFact :: Concat -> Concat
mkFact x@(CString "") = x
mkFact xs = cconcat [CString "fact ", mkSet xs, CString "\n"]
mkSet :: Concat -> Concat
mkSet xs = cconcat [CString "{ ", xs, CString " }"]
showSet :: Concat -> [Concat] -> Concat
showSet delim xs = showSet' delim $ filterNull xs
where
showSet' _ [] = CString "{}"
showSet' delim' xs' = mkSet $ cintercalate delim' xs'
optShowSet :: [Concat] -> Concat
optShowSet [] = CString ""
optShowSet xs = CString "\n" +++ showSet (CString "\n ") xs
genClafer :: GenEnv -> IClafer -> Concat
genClafer genEnv c = cunlines (filterNull
[ claferDecl c (showSet (CString "\n, ") (genRelations genEnv c) +++ optShowSet (filterNull $ genConstraints genEnv c))
, if isRoot c then CString "" else aliveFun
, mkFact $ cintercalate (CString "\n ") $ filterNull $ genStructure genEnv c
, cunlines $ genFacts genEnv c
, cconcat $ map (mkAssert genEnv c) $ getAssertions c
]) +++ CString "\n"
where
aliveFun = CString $ "fun " ++ aliveName (_uid c) ++ " : set " ++ _uid c ++ " { " ++ aliveBody ++ " }"
aliveBody
| hasContainment c = sigOf (fromJust $ parentOf genEnv c) ++ ".@" ++ genRelName (_uid c)
| otherwise = case map (aliveName . _uid) $ subsOf genEnv c of
[] -> "none"
alive -> intercalate " + " alive
sigOf p = if isRoot p then rootIdent else _uid p
claferDecl :: IClafer -> Concat -> Concat
claferDecl c rest = cconcat
[ CString $ if isRoot c then "one " else ""
, CString $ if _isAbstract c then "abstract " else ""
, CString "sig "
, Concat NoTrace [CString $ _uid c, genExtends $ _super c, CString "\n", rest]
]
where
genExtends (Just (PExp _ _ _ (IClaferId _ i _ _))) = CString " " +++ Concat NoTrace [CString $ "extends " ++ i]
genExtends _ = CString ""
-- | The parent, reference and containment fields of the clafer.
genRelations :: GenEnv -> IClafer -> [Concat]
genRelations genEnv c = parent' ++ reference' ++ map mkRel (containedClafers c)
where
parent'
| hasContainment c && not (_isAbstract c) =
[CString $ genParentName (_uid c) ++ " : lone " ++ maybe rootIdent sigName (parentOf genEnv c)]
| otherwise = []
sigName p = if isRoot p then rootIdent else _uid p
reference' = case _reference c of
Just r -> [CString $ var' (isStatic genEnv c && not (null (_refModifiers r))) ++ genRefName (_uid c) ++ " : set " ++ refType genEnv c]
Nothing -> []
mkRel c' = Concat NoTrace [CString $ var' (isStatic genEnv c') ++ genRelName (_uid c') ++ " : set " ++ _uid c']
var' static = if static then "" else "var "
refType :: GenEnv -> IClafer -> String
refType genEnv c = maybe "" (targetType . _ref) $ _reference c
where
targetType pexp = case getTarget pexp of
PExp _ _ _ (IClaferId _ sid _ _) | isPrimitive sid -> "Int"
| otherwise -> sid
-- a union of targets, e.g., Hub.p ++ fast: the union of their signatures (p + fast), since a
-- field declaration cannot name another signature's field
PExp _ _ _ (IFunExp op' ps) | op' == iUnion -> intercalate " + " $ map targetType ps
target -> flatten $ genPExp genEnv [_uid c] target
getTarget :: PExp -> PExp
getTarget x = case x of
PExp _ _ _ (IFunExp op' (_:pexp:_)) -> if op' == iJoin then pexp else x
_ -> x
-- | The facts about the instances of the clafer: a fixed parent, which exists; for a nested
-- abstract clafer, its instances are those of its subclafers.
genStructure :: GenEnv -> IClafer -> [Concat]
genStructure genEnv c
| not (hasContainment c) = []
| _isAbstract c =
[ CString $ "always @" ++ rel ++ " = " ++ case map (('@' :) . genRelName . _uid) $ subsOf genEnv c of
[] -> "none->none"
rels -> "(" ++ intercalate " + " rels ++ ")" ]
| otherwise =
[ CString $ "always ~@" ++ rel ++ " in @" ++ genParentName (_uid c)
, if isRoot parent' then CString "" else CString $ "always @" ++ rel ++ ".univ in " ++ aliveName (_uid parent')
]
where
rel = genRelName $ _uid c
parent' = fromJust $ parentOf genEnv c
-- | The constraints in the signature fact of the clafer, which hold for every existing instance.
genConstraints :: GenEnv -> IClafer -> [Concat]
genConstraints genEnv c = map always' (filterNull $ refConsts ++ groupConst ++ childConsts) ++ absentConsts ++ initialConsts ++ finalConsts
where
uid' = _uid c
alive = aliveName uid'
-- in every snapshot in which this instance exists
always' x
| isRoot c = cconcat [CString "always (", x, CString ")"]
| otherwise = cconcat [CString "always (this in ", CString alive, CString " implies (", x, CString "))"]
-- an instance refers to one existing target
refConsts = case _reference c of
Just _ ->
[ CString $ "one this.@" ++ genRefName uid' ] ++
[ CString $ "this.@" ++ genRefName uid' ++ " in " ++ aliveName target
| let target = refType genEnv c, target /= "Int", isJust (findIClafer (uidIClaferMap genEnv) target) ] ++
-- a reference that refines an inherited one is the same reference, seen through the
-- subclafer: an instance has one target (gsdlab/clafer#120)
[ CString $ "this.@" ++ genRefName uid' ++ " in this.@" ++ genRefName (_uid s)
| Just (s, _) <- [inheritedReference genEnv c] ]
Nothing -> []
-- an instance has a reference only while it exists, as it has children only while it exists:
-- a state is an instance of the model, so an obligation on the value of an instance that does
-- not exist fails (kbak/clafer-semantics#168, reading A; gsdlab/clafer#122)
absentConsts =
[ CString $ "always (this not in " ++ alive ++ " implies no this.@" ++ genRefName uid' ++ ")"
| not (isRoot c), Just _ <- [_reference c] ]
groupConst = [ genGroupConst genEnv c ]
childConsts = concatMap childConst $ containedClafers c
childConst c' = genParentSubrelationConstraint (uidIClaferMap genEnv) c' : genSetUniquenessConstraint genEnv c'
-- whenever this instance appears
initialConsts =
[ appears $ CString $ "some this.@" ++ genRelName (_uid c') | c' <- containedClafers c, _isInitial c' ]
appears x
| isRoot c = x
| otherwise = cconcat [CString "always (this in ", CString alive, CString " and not before this in ", CString alive, CString " implies (", x, CString "))"]
-- the relation does not change while this instance exists
stable x
| isRoot c = CString $ "always ((" ++ x ++ ")' = " ++ x ++ ")"
| otherwise = CString $ "always (this in " ++ alive ++ " and after this in " ++ alive ++ " implies (" ++ x ++ ")' = " ++ x ++ ")"
-- final and finalref fix the target of each instance, finaltarget only the set of targets
fixesEach s r = _isFinal s || any (`elem` [FinalRefTarget, FinalRef]) (_refModifiers r)
finalConsts =
-- the instances of a final child do not change while this instance exists
[ stable $ "this.@" ++ genRelName (_uid c') | c' <- containedClafers c, _isFinal c', not (isStatic genEnv c') ] ++
[ stable $ "this.@" ++ genRefName uid' | Just r <- [_reference c], fixesEach c r, not (isStatic genEnv c) ] ++
-- `final motor : engine` or `finalref motor : engine` fixes the reference that motor inherits
-- from engine, unless engine's modifier fixes it already (#109)
[ stable $ "this.@" ++ genRefName (_uid sup)
| Nothing <- [_reference c], _isFinal c || FinalRef `elem` _finalReferences (_modifiers c)
, Just (sup, r) <- [inheritedReference genEnv c], not (fixesEach sup r) ] ++
-- a finaltarget child points to the same set of targets while this instance exists; its
-- instances may change and swap their targets
[ stable $ "this.@" ++ genRelName (_uid c') ++ ".@" ++ refRel | c' <- containedClafers c, Just refRel <- [finalTargetRef c'] ]
finalTargetRef c' = case _reference c' of
Just r | FinalTarget `elem` _refModifiers r, not (isStatic genEnv c') -> Just $ genRefName (_uid c')
Just _ -> Nothing
Nothing
| FinalTarget `elem` _finalReferences (_modifiers c'), not (isStatic genEnv c') -> genRefName . _uid . fst <$> inheritedReference genEnv c'
| otherwise -> Nothing
-- | The constraints of the clafer and the cardinalities of its children, each a fact of its own,
-- which holds for every existing instance: an unsat core gives these, which are removed to find
-- a near-miss example. Alloy gives the unsat core of the temporal formulas of a signature fact
-- for the whole fact, so they are not in the signature fact. The bounds of an interval are two
-- facts, which are removed one by one.
genFacts :: GenEnv -> IClafer -> [Concat]
genFacts genEnv c = map fact $ concatMap childCards (containedClafers c) ++ userFacts
where
uid' = _uid c
userFacts = [ (IrPExp $ _pid pexp, genPExp genEnv [uid'] pexp) | IEConstraint True pexp <- _elements c ]
childCards c' = case fromJust $ _card c' of
(1, 1) -> [(ExactCard child False, CString $ "one " ++ rel)]
(0, 1) -> [(ExactCard child False, CString $ "lone " ++ rel)]
(1, -1) -> [(ExactCard child False, CString $ "some " ++ rel)]
(n, m) -> [ (LowerCard child False, CString $ show n ++ " <= #(" ++ rel ++ ")") | n > 0 ] ++
[ (UpperCard child False, CString $ "#(" ++ rel ++ ") <= " ++ show m) | m /= -1 ]
where
child = _uid c'
rel = "this.@" ++ genRelName child
-- the constraint, for every instance in every snapshot in which it exists
fact (trace, x) = cconcat
[ CString "fact { "
, Concat trace [forEveryInstance c x]
, CString " }" ]
-- | The constraint for every instance of the clafer, in every snapshot in which it exists. The
-- root has one instance, root itself, which this is in a top-level constraint: a quantified
-- variable would mostly be unused, which Alloy warns about.
forEveryInstance :: IClafer -> Concat -> Concat
forEveryInstance c x
| isRoot c = bindTo rootIdent $ cconcat [CString "always (", x, CString ")"]
| otherwise = cconcat [CString $ "all " ++ selfIdent ++ " : " ++ uid' ++ " | ", bindSelf always']
where
uid' = _uid c
always' = cconcat [CString $ "always (" ++ selfIdent ++ " in " ++ aliveName uid' ++ " implies (", x, CString "))"]
-- | The variable of the instance in a fact: this is a keyword, which only signature facts bind.
selfIdent :: String
selfIdent = "self_"
-- | The constraint for the instance bound to 'selfIdent' instead of this.
bindSelf :: Concat -> Concat
bindSelf = bindTo selfIdent
-- | The constraint with this replaced by the given name.
bindTo :: String -> Concat -> Concat
bindTo ident (CString str) = CString $ bind Nothing str
where
bind prev ('t':'h':'i':'s':rest)
| maybe True (not . identChar) prev && not (startsIdent rest) = ident ++ bind (Just '_') rest
bind _ (x:xs) = x : bind (Just x) xs
bind _ [] = []
startsIdent (x:_) = identChar x
startsIdent [] = False
identChar x = isAlphaNum x || x == '_' || x == '\''
bindTo ident (Concat trace xs) = Concat trace $ map (bindTo ident) xs
getAssertions :: IClafer -> [PExp]
getAssertions c = [ pexp | IEConstraint False pexp <- _elements c ]
mkAssert :: GenEnv -> IClafer -> PExp -> Concat
mkAssert genEnv c pexp = cconcat
[ CString "assert ", name, CString " { ", forEveryInstance c $ genPExp genEnv [_uid c] pexp, CString " }\n"
, CString "check ", name, CString " ", CString $ forScopes genEnv, CString "\n\n"
]
where
name = CString $ assertionName pexp
-- | The targets of the instances of a set reference under one parent are distinct (see
-- 'setReferenceKey').
genSetUniquenessConstraint :: GenEnv -> IClafer -> [Concat]
genSetUniquenessConstraint genEnv c = case setReferenceKey (uidIClaferMap genEnv) c of
Just s -> [ CString $ "all disj x, y : this.@" ++ genRelName (_uid c) ++ " | (x.@" ++ genRefName (_uid s) ++ ") != (y.@" ++ genRefName (_uid s) ++ ")" ]
Nothing -> []
genParentSubrelationConstraint :: UIDIClaferMap -> IClafer -> Concat
genParentSubrelationConstraint uidIClaferMap' headClafer = case matchNestedInheritance uidIClaferMap' headClafer of
Just match@NestedInheritanceMatch{ _superClafer = superClafer }
| isProperNesting uidIClaferMap' (Just match) && not (isTopLevel superClafer) ->
CString $ "this.@" ++ genRelName (_uid headClafer) ++ " in this.@" ++ genRelName (_uid superClafer)
_ -> CString ""
genGroupConst :: GenEnv -> IClafer -> Concat
genGroupConst genEnv clafer'
| _isAbstract clafer' || null children' || flatten card' == "" = CString ""
| otherwise = cconcat [CString "let children = ", brArg id $ CString children', CString " | ", card']
where
superHierarchy = findHierarchy getSuper (uidIClaferMap genEnv) clafer'
children' = intercalate " + " $ map (("this.@" ++) . genRelName . _uid) $ getSubclafers $ concatMap _elements superHierarchy
card' = mkCard (_uid clafer') True "children" $ _interval $ fromJust $ _gcard clafer'
mkCard :: String -> Bool -> String -> (Integer, Integer) -> Concat
mkCard constraintName group' element' crd
| crd' == "set" || crd' == "" = CString ""
| crd' `elem` ["one", "lone", "some"] = CString $ crd' ++ " " ++ element'
| otherwise = interval'
where
interval' = genInterval constraintName group' element' crd
crd' = flatten interval'
genInterval :: String -> Bool -> String -> Interval -> Concat
genInterval constraintName group' element' x = case x of
(1, 1) -> cardConcat constraintName group' [CString "one"]
(0, 1) -> cardConcat constraintName group' [CString "lone"]
(1, -1) -> cardConcat constraintName group' [CString "some"]
(0, -1) -> CString "set"
(n, exinteger) ->
case (s1, s2) of
(Just c1, Just c2) -> cconcat [c1, CString " and ", c2]
(Just c1, Nothing) -> c1
(Nothing, Just c2) -> c2
(Nothing, Nothing) -> undefined
where
element'' = "(" ++ element' ++ ")"
s1 = if n == 0 then Nothing else Just $ cardLowerConcat constraintName group' [CString $ show n ++ " <= #" ++ element'']
s2 = cardUpperConcat constraintName group' . (: []) . CString <$> genExInteger element'' x exinteger
cardConcat :: String -> Bool -> [Concat] -> Concat
cardConcat constraintName = Concat . ExactCard constraintName
cardLowerConcat :: String -> Bool -> [Concat] -> Concat
cardLowerConcat constraintName = Concat . LowerCard constraintName
cardUpperConcat :: String -> Bool -> [Concat] -> Concat
cardUpperConcat constraintName = Concat . UpperCard constraintName
genExInteger :: String -> Interval -> Integer -> Maybe Result
genExInteger element' (y, z) x
| y == 0 && z == 0 = Just $ "#" ++ element' ++ " = 0"
| x == -1 = Nothing
| otherwise = Just $ "#" ++ element' ++ " <= " ++ show x
-- -----------------------------------------------------------------------------
-- expressions; the head of the path is the UID of the context clafer
genPExp :: GenEnv -> [String] -> PExp -> Concat
genPExp genEnv resPath x = genPExp' genEnv resPath $ adjustPExp genEnv resPath $ pushNegations True x
-- | Pushes the negations of the formulas with temporal operators to the formulas without them,
-- with the dualities of LTL (@!F a@ is @G !a@, @!X a@ is @X !a@, @!(a U b)@ is @!b W (!a && !b)@).
-- The obligations are bounded by the parent's lifetime afterwards, so an obligation lapses with
-- the parent also when it is negated: @!(F error)@ means @G !error@, and lets the parent
-- disappear. @initially@ and @finally@ anchor their negation: @!initially a@ is @initially !a@.
-- A formula and its negation may both hold, on a lifetime that ends before their obligations.
-- The polarity is @True@ for the formula itself, @False@ for its negation. @one@ and @lone@
-- keep the classical negation.
pushNegations :: Bool -> PExp -> PExp
pushNegations pos' x@(PExp t pid' sp e)
| not $ hasTemporal x = if pos' then x else neg x
| otherwise = case e of
IFunExp op' [a]
| op' == iNot -> pushNegations (not pos') a
| op' == iF -> mk (if pos' then iF else iG) [push a]
| op' == iG -> mk (if pos' then iG else iF) [push a]
| op' `elem` [iX, iInitially, iFinally] -> mk op' [push a]
IFunExp op' [a, b]
| op' == iAnd -> mk (if pos' then iAnd else iOr) [push a, push b]
| op' == iOr -> mk (if pos' then iOr else iAnd) [push a, push b]
| op' == iImpl, pos', not (hasTemporal a) -> mk iImpl [a, push b]
| op' == iImpl -> mk (if pos' then iOr else iAnd) [pushNegations (not pos') a, push b]
| op' == iIff -> pushNegations pos' $ bool iAnd [bool iImpl [a, b], bool iImpl [b, a]]
| op' == iXor -> pushNegations pos' $ bool iOr [bool iAnd [a, bool iNot [b]], bool iAnd [bool iNot [a], b]]
| op' `elem` [iU, iW], pos' -> mk op' [push a, push b]
| op' `elem` [iU, iW] -> mk (if op' == iU then iW else iU) [push b, mk iAnd [push a, push b]]
IFunExp op' [c, a, b]
| op' == iIfThenElse, t == Just TBoolean, not (hasTemporal c) -> mk op' [c, push a, push b]
| op' == iIfThenElse, t == Just TBoolean ->
pushNegations pos' $ bool iAnd [bool iImpl [c, a], bool iImpl [bool iNot [c], b]]
IDeclPExp q ds@(_:_) body
| q == IAll -> PExp t pid' sp $ IDeclPExp (if pos' then IAll else ISome) ds $ push body
| q == ISome -> PExp t pid' sp $ IDeclPExp (if pos' then ISome else IAll) ds $ push body
| q == INo -> PExp t pid' sp $ IDeclPExp (if pos' then IAll else ISome) ds $ pushNegations (not pos') body
_ -> if pos' then x else neg x
where
push = pushNegations pos'
mk op' = PExp t pid' sp . IFunExp op'
bool op' = PExp (Just TBoolean) pid' sp . IFunExp op'
neg a = bool iNot [a]
-- | Whether the formula has temporal operators.
hasTemporal :: PExp -> Bool
hasTemporal (PExp _ _ _ e) = case e of
IFunExp op' es -> op' `elem` (iFinally : ltlOps) || any hasTemporal es
IDeclPExp _ _ body -> hasTemporal body
_ -> False
genPExp' :: GenEnv -> [String] -> PExp -> Concat
genPExp' genEnv resPath (PExp iType' pid' pos exp') = case exp' of
IDeclPExp q d pexp -> Concat (IrPExp pid')
[ CString $ genQuant q, CString " "
, cintercalate (CString ", ") $ map (genDecl genEnv resPath) d
, CString $ optBar d, genPExp' genEnv resPath pexp]
where
optBar [] = ""
optBar _ = " | "
IClaferId _ "integer" _ _ -> CString "Int"
IClaferId _ "int" _ _ -> CString "Int"
IClaferId _ "string" _ _ -> CString "Int"
-- the empty set
IClaferId _ "noclafer" _ _ -> CString "none"
IClaferId _ "dref" _ _ -> CString $ "@" ++ genRefName (getTClaferUID iType')
where
getTClaferUID (Just TMap{_so = TClafer{_hi = (u:_)}}) = u
getTClaferUID t = error $ "[bug] AlloyLtl.genPExp'.getTClaferUID: unknown type: " ++ show t
-- a variable of a quantifier
IClaferId _ sid _ (LocalBind _) -> CString sid
IClaferId _ sid istop _ -> CString $
if head sid `elem` "~@("
then sid
else case iType' of
Just TInteger -> vsident
Just TDecimal -> vsident
Just TDouble -> vsident
Just TReal -> vsident
Just TString -> vsident
_ -> sid'
where
sid'
| sid == thisIdent = thisAlive genEnv resPath
| sid == rootIdent = rootIdent
| istop = aliveName sid
| otherwise = '@' : genRelName sid
vsident = sid' ++ ".@" ++ genRefName (if sid == thisIdent then head resPath else sid)
IFunExp _ _ -> case exp'' of
IFunExp _ _ -> genIFunExp pid' genEnv resPath exp''
_ -> genPExp' genEnv resPath $ PExp iType' pid' pos exp''
where
exp'' = transformExp exp'
IInt n -> CString $ show n
IDouble _ -> error "no double numbers allowed"
IDecimal _ -> error "no decimal numbers allowed"
IReal _ -> error "no real numbers allowed"
IStr _ -> error "no strings allowed"
-- | The context instance, as long as it exists.
thisAlive :: GenEnv -> [String] -> String
thisAlive genEnv (ctx:_) | ctx /= rootIdent = "(" ++ contextInstance genEnv ++ " & " ++ aliveName ctx ++ ")"
thisAlive _ _ = rootIdent
-- | Whether the parent of the context instance exists, unless the parent is the root, which
-- always exists. The obligations of a constraint last as long as the parent.
parentExists :: GenEnv -> [String] -> Maybe String
parentExists genEnv (ctx:_)
| Just c <- findIClafer (uidIClaferMap genEnv) ctx
, any (maybe False (not . isRoot) . parentOf genEnv) $ concreteSubs genEnv c
= Just $ "some " ++ contextInstance genEnv ++ "." ++ parentRel genEnv ctx
parentExists _ _ = Nothing
-- | Whether the context instance appears now (its first snapshot), or the trace begins.
appearsNow :: GenEnv -> [String] -> String
appearsNow genEnv (ctx:_) | ctx /= rootIdent = "not before " ++ contextInstance genEnv ++ " in " ++ aliveName ctx
appearsNow _ _ = "not before some " ++ rootIdent
-- 3-May-2012 Rafael Olaechea.
-- Removed transfromation from x = -2 to x = (0-2) as this creates problem with partial instances.
-- See http://gsd.uwaterloo.ca:8888/question/461/new-translation-of-negative-number-x-into-0-x-is.
-- Weak until: a W b === G a || a U b
transformExp :: IExp -> IExp
transformExp (IFunExp op' [e1])
| op' == iMin = IFunExp iMul [PExp (_iType e1) "" noSpan $ IInt (-1), e1]
transformExp x@(IFunExp op' exps'@(e1:e2:_))
| op' == iXor = IFunExp iNot [PExp (Just TBoolean) "" noSpan (IFunExp iIff exps')]
| op' == iW = IFunExp iOr [PExp (Just TBoolean) "" noSpan $ IFunExp iG [e1], PExp (Just TBoolean) "" noSpan x{_op = iU}]
| op' == iJoin && isClaferName' e1 && isClaferName' e2 &&
getClaferName e1 == thisIdent && head (getClaferName e2) == '~' =
IFunExp op' [e1{_iType = Just $ TClafer []}, e2]
| otherwise = x
transformExp x = x
genIFunExp :: String -> GenEnv -> [String] -> IExp -> Concat
genIFunExp pid' genEnv resPath (IFunExp "min" [exp']) = Concat (IrPExp pid') [CString "min[", genPExp' genEnv resPath exp', CString "]"]
genIFunExp pid' genEnv resPath (IFunExp "max" [exp']) = Concat (IrPExp pid') [CString "max[", genPExp' genEnv resPath exp', CString "]"]
-- the navigation starts from the context instance, also after it has disappeared
genIFunExp pid' genEnv resPath (IFunExp op' [PExp{_exp=IClaferId{_sident=sid}}, exp2])
| op' == iJoin && sid == thisIdent = Concat (IrPExp pid') [CString "this.", optBrArg genEnv resPath exp2]
| op' == iJoin && sid == rootIdent = genPExp' genEnv resPath exp2
genIFunExp pid' genEnv resPath (IFunExp op' [exp'])
| op' == iInitially = Concat (IrPExp pid') [CString $ "(" ++ appearsNow genEnv resPath ++ ") implies ", brArg (genPExp' genEnv resPath) exp']
| op' == iFinally = Concat (IrPExp pid') [CString $ "(some " ++ thisAlive genEnv resPath ++ " and after no " ++ thisAlive genEnv resPath ++ ") implies ", brArg (genPExp' genEnv resPath) exp']
-- the value of an initializer of the context clafer x, with temporal operators: it is
-- evaluated in the context of the parent of x, where it is written (gsdlab/clafer#123). Its
-- obligations last as long as the parent of the parent, and initially and finally refer to
-- the lifetime of the parent. The names in it are already paths from this, the instance of x.
| op' == iInitValue = case resPath of
ctx : rest | Just c <- findIClafer (uidIClaferMap genEnv) ctx, Just p <- parentOf genEnv c ->
brArg (genPExp' genEnv{contextInstance = "(" ++ contextInstance genEnv ++ "." ++ fixedParentRel genEnv c ++ ")"} (_uid p : rest)) (pushNegations True exp')
_ -> brArg (genPExp' genEnv resPath) (pushNegations True exp')
-- the obligations hold while the parent of the context instance exists
| Just p <- parentExists genEnv resPath, op' == iX =
Concat (IrPExp pid') [CString $ "after (not " ++ p ++ " or ", e, CString ")"]
| Just p <- parentExists genEnv resPath, op' == iF =
Concat (IrPExp pid') [CString $ "eventually (not " ++ p ++ " or ", e, CString ")"]
| Just p <- parentExists genEnv resPath, op' == iG =
Concat (IrPExp pid') [CString $ "(not " ++ p ++ ") releases (not " ++ p ++ " or ", e, CString ")"]
where
e = brArg (genPExp' genEnv resPath) exp'
genIFunExp pid' genEnv resPath (IFunExp op' [exp1, exp2])
| Just p <- parentExists genEnv resPath, op' == iU =
Concat (IrPExp pid') [CString $ "(" ++ p ++ " and ", brArg (genPExp' genEnv resPath) exp1,
CString $ ") until (not " ++ p ++ " or ", brArg (genPExp' genEnv resPath) exp2, CString ")"]
genIFunExp pid' genEnv resPath (IFunExp op' exps')
| op' == iSumSet = genIFunExp pid' genEnv resPath (IFunExp iSumSet' [removeright (head exps'), getRight $ head exps'])
| op' == iSumSet' = Concat (IrPExp pid') $ intl exps'' (map CString $ genOp iSumSet)
| otherwise = Concat (IrPExp pid') $ intl exps'' (map CString $ genOp op')
where
iSumSet' = "sum'"
intl
| op' == iSumSet' = flip interleave
| op' `elem` arithBinOps && length exps' == 2 = interleave
| otherwise = \xs ys -> reverse $ interleave (reverse xs) (reverse ys)
exps'' = map (optBrArg genEnv resPath) exps'
genIFunExp _ _ _ x = error $ "[bug] AlloyLtl.genIFunExp: expecting a IFunExp, instead got: " ++ show x
optBrArg :: GenEnv -> [String] -> PExp -> Concat
optBrArg genEnv resPath x = brFun (genPExp' genEnv resPath) x
where
brFun = case x of
PExp _ _ _ IClaferId{} -> ($)
PExp _ _ _ (IInt _) -> ($)
_ -> brArg
interleave :: [Concat] -> [Concat] -> [Concat]
interleave [] [] = []
interleave (x:xs) [] = x:xs
interleave [] (x:xs) = x:xs
interleave (x:xs) ys = x : interleave ys xs
brArg :: (a -> Concat) -> a -> Concat
brArg f arg = cconcat [CString "(", f arg, CString ")"]
genOp :: String -> [String]
genOp op'
| op' == iX = ["after "]
| op' == iF = ["eventually "]
| op' == iG = ["always "]
| op' == iU = [" until "]
| op' == iPlus = [".plus[", "]"]
| op' == iSub = [".minus[", "]"]
| op' == iSumSet = ["sum temp : "," | temp."]
| op' == iProdSet = ["prod temp : "," | temp."]
| op' `elem` unOps = [op']
| op' == iMul = [".mul[", "]"]
| op' == iDiv = [".div[", "]"]
| op' == iRem = [".rem[", "]"]
| op' `elem` logBinOps ++ relBinOps ++ arithBinOps = [" " ++ op' ++ " "]
| op' == iUnion = [" + "]
| op' == iDifference = [" - "]
| op' == iIntersection = [" & "]
| op' == iDomain = [" <: "]
| op' == iRange = [" :> "]
| op' == iJoin = ["."]
| op' == iIfThenElse = [" => ", " else "]
genOp op' = error $ "[bug] AlloyLtl.genOp: Unmatched operator: " ++ op'
-- | Replaces the navigation to the parent with the relation to the parent.
adjustPExp :: GenEnv -> [String] -> PExp -> PExp
adjustPExp genEnv resPath (PExp t pid' pos x) = PExp t pid' pos $ adjustIExp genEnv resPath x
adjustIExp :: GenEnv -> [String] -> IExp -> IExp
adjustIExp genEnv resPath x = case x of
IDeclPExp q d pexp -> IDeclPExp q d $ adjustPExp genEnv resPath pexp
IFunExp op' exps' -> adjNav $ IFunExp op' $ map adjExps exps'
where
(adjNav, adjExps) = if op' == iJoin then (aNav, id)
else (id, adjustPExp genEnv resPath)
IClaferId{} -> aNav x
_ -> x
where
aNav = fst . adjustNav genEnv resPath
adjustNav :: GenEnv -> [String] -> IExp -> (IExp, [String])
adjustNav genEnv resPath x@(IFunExp op' (pexp0:pexp:_))
| op' == iJoin = (IFunExp iJoin [pexp0{_exp = iexp0}, pexp{_exp = iexp}], path')
| otherwise = (x, resPath)
where
(iexp0, path) = adjustNav genEnv resPath (_exp pexp0)
(iexp, path') = adjustNav genEnv (typePath path) (_exp pexp)
-- the right operand navigates from the clafer of the left one, e.g., a variable @b1@ in @b1.parent@
typePath p = case _iType pexp0 of
Just (TClafer (uid':_)) | isJust (findIClafer (uidIClaferMap genEnv) uid') -> uid' : drop 1 p
_ -> p
adjustNav genEnv resPath x@(IClaferId _ id' _ _)
| id' == parentIdent = (x{_sident = parentRel genEnv $ head resPath}, parentPath)
| otherwise = (x, resPath)
where
-- the path continues with the parent of the context clafer
parentPath = case findIClafer (uidIClaferMap genEnv) (head resPath) >>= parentOf genEnv of
Just p -> _uid p : tail resPath
Nothing -> tail resPath
adjustNav _ _ _ = error "AlloyLtl.adjustNav: expects a IFunExp or IClaferId"
genQuant :: IQuant -> String
genQuant x = case x of
INo -> "no"
ILone -> "lone"
IOne -> "one"
ISome -> "some"
IAll -> "all"
genDecl :: GenEnv -> [String] -> IDecl -> Concat
genDecl genEnv resPath x = case x of
IDecl disj locids pexp -> cconcat [CString $ if disj then "disj" else "", CString " ",
CString $ intercalate ", " locids, CString " : ", genPExp genEnv resPath pexp]
removeright :: PExp -> PExp
removeright (PExp _ _ _ (IFunExp _ (x : PExp _ _ _ IClaferId{} : _))) = x
removeright (PExp _ _ _ (IFunExp _ (x : PExp _ _ _ (IInt _ ) : _))) = x
removeright (PExp _ _ _ (IFunExp _ (x : PExp _ _ _ (IStr _ ) : _))) = x
removeright (PExp _ _ _ (IFunExp _ (x : PExp _ _ _ (IDouble _ ) : _))) = x
removeright (PExp t id' pos (IFunExp o (x1:x2:xs))) = PExp t id' pos (IFunExp o (x1:removeright x2:xs))
removeright x@PExp{} = error $ "[bug] AlloyLtl.removeright: expects a PExp with a IFunExp inside but was given: " ++ show x
getRight :: PExp -> PExp
getRight (PExp _ _ _ (IFunExp _ (_:x:_))) = getRight x
getRight p = p
-- mapping line/columns between Clafer and Alloy code
data AlloyEnv = AlloyEnv {
lineCol :: (LineNo, ColNo),
mapping :: [(Span, IrTrace)]
} deriving (Eq,Show)
mapLineCol :: Concat -> [(Span, IrTrace)]
mapLineCol code = mapping $ execState (mapLineCol' code) (AlloyEnv (firstLine, firstCol) [])
addCode :: MonadState AlloyEnv m => String -> m ()
addCode str = modify (\s -> s {lineCol = lineno (lineCol s) str})
mapLineCol' :: MonadState AlloyEnv m => Concat -> m ()
mapLineCol' (CString str) = addCode str
mapLineCol' c@(Concat srcPos' n) = do
posStart <- gets lineCol
mapM_ mapLineCol' n
posEnd <- gets lineCol
-- Alloy counts the inner parentheses as part of a constraint, but not the outer ones
let flat = flatten c
raiseStart = countLeading "([" flat
deductEnd = -(countTrailing ")]" flat)
modify (\s -> s {mapping = (Span (uncurry Pos $ posStart `addColumn` raiseStart) (uncurry Pos $ posEnd `addColumn` deductEnd), srcPos') : mapping s})
addColumn :: Interval -> Integer -> Interval
addColumn (x, y) c = (x, y + c)
countLeading :: String -> String -> Integer
countLeading c xs = toInteger $ length $ takeWhile (`elem` c) xs
countTrailing :: String -> String -> Integer
countTrailing c xs = countLeading c (reverse xs)
lineno :: (Integer, ColNo) -> String -> (Integer, ColNo)
lineno (l, c) str = (l + newLines, (if newLines > 0 then firstCol else c) + newCol)
where
newLines = toInteger $ length $ filter (== '\n') str
newCol = toInteger $ length $ takeWhile (/= '\n') $ reverse str
firstCol :: ColNo
firstCol = 1 :: ColNo
firstLine :: LineNo
firstLine = 1 :: LineNo