packages feed

clafer-0.5.8: src/Language/Clafer/Intermediate/Desugarer.hs

{-# LANGUAGE RankNTypes #-}
{-
 Copyright (C) 2012-2017 Kacper Bak, Jimmy Liang, Michal Antkiewicz, Paulius Juodisius <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.
-}
{- | Transforms an Abstract Syntax Tree (AST) from "Language.Clafer.Front.AbsClafer"
into Intermediate representation (IR) from "Language.Clafer.Intermediate.Intclafer" of a Clafer model.
-}
module Language.Clafer.Intermediate.Desugarer where

import Data.Data (Data, cast, gmapQ, gmapT)
import Data.List (nub)
import Data.Maybe (fromMaybe, mapMaybe)
import Prelude hiding ((||))
import Language.Clafer.Common
import Language.Clafer.Front.AbsClafer as AbsClafer
import Language.Clafer.Intermediate.Intclafer as IntClafer

-- | Transform the AST into the intermediate representation (IR). In a dynamic model, the
--   enumerations are final, so that their literals do not change over time, and an initializer
--   @:=@ gives the initial value of a reference (see 'desugarInit').
desugarModule :: Maybe String -> Module -> IModule
desugarModule mURL (Module _ declarations) = if isDynamicModule staticModule
  then desugarWith True
  else staticModule
  where
    -- neither the non-final enumerations nor the initializers make a model dynamic
    staticModule = desugarWith False
    desugarWith dynamic' = IModule
      (fromMaybe "" mURL)
      (declarations >>= desugarEnums dynamic' >>= desugarDeclaration dynamic')

sugarModule :: IModule -> Module
sugarModule x = Module noSpan $ map sugarDeclaration $ _mDecls x -- (fragments x >>= mDecls)

-- | desugars enumeration to abstract and global singleton features; the abstract clafer is
--   final if requested, and its literals inherit the finality
desugarEnums :: Bool -> Declaration -> [Declaration]
desugarEnums finalEnum (EnumDecl (Span p1 p2) id' enumids) = absEnum : map mkEnum enumids
    where
    p2' = case enumids of
      -- the abstract enum clafer should end before the first literal begins
      ((EnumIdIdent (Span (Pos y' x') _) _):_) -> Pos y' (x'-3) -- cutting the ' = '
      [] -> p2 -- should never happen - cannot have enum without any literals. Return the original end pos.
    oneToOne pos' = (CardInterval noSpan $
                  NCard noSpan (PosInteger (pos', "1")) (ExIntegerNum noSpan $ PosInteger (pos', "1")))
    absEnum = let
        s1 = Span p1 p2'
      in
        ElementDecl s1 $
          Subclafer s1 $
            Clafer s1 (Abstract s1) [ Final s1 | finalEnum ] (GCardEmpty s1) id' (SuperEmpty s1) (ReferenceEmpty s1) (CardEmpty s1) (InitEmpty s1) (TransitionEmpty s1) (ElementsList s1 [])
    mkEnum (EnumIdIdent s2 eId) = -- each concrete clafer must fit within the original span of the literal
      ElementDecl s2 $
        Subclafer s2 $
          Clafer s2 (AbstractEmpty s2) [] (GCardEmpty s2) eId ((SuperSome s2) (ClaferId s2 $ Path s2 [ModIdIdent s2 id'])) (ReferenceEmpty s2) (oneToOne (0, 0)) (InitEmpty s2) (TransitionEmpty s2) (ElementsList s2 [])
desugarEnums _ x = [x]


-- | The first argument tells whether the model is dynamic.
desugarDeclaration :: Bool -> Declaration -> [IElement]
desugarDeclaration dynamic' (ElementDecl _ element) = desugarElement dynamic' element
desugarDeclaration _ _ = error "Desugarer.desugarDeclaration: enum declarations should have already been converted to clafers. BUG."


sugarDeclaration :: IElement -> Declaration
sugarDeclaration (IEClafer clafer) = ElementDecl (_cinPos clafer) $ Subclafer (_cinPos clafer) $ sugarClafer clafer
sugarDeclaration (IEConstraint True constraint) =
      ElementDecl (_inPos constraint) $ Subconstraint (_inPos constraint) $ sugarConstraint constraint
sugarDeclaration  (IEConstraint False assertion) =
      ElementDecl (_inPos assertion) $ SubAssertion (_inPos assertion) $ sugarAssertion assertion
sugarDeclaration  (IEGoal isMaximize' goal) = ElementDecl (_inPos goal) $ Subgoal (_inPos goal) $ sugarGoal goal isMaximize'


desugarClafer :: Bool -> Clafer -> [IElement]
-- A reference to a constant, e.g., `-> 1`, is a reference to its type with
-- the constant as the value: `-> integer = 1`.
desugarClafer dynamic' (Clafer s abstract' tmods gcrd' id' super' reference' crd' (InitEmpty si) trans' elements')
  | Just (typeReference, constant') <- referenceToConstant reference' =
    desugarClafer dynamic' (Clafer s abstract' tmods gcrd' id' super' typeReference crd' (InitSome si (InitConstant si) constant') trans' elements')
desugarClafer dynamic' claf@(Clafer s abstract' tmods gcrd' id' super' reference' crd' init' trans' elements') =
  case (super', reference') of
    (SuperSome ss setExp, ReferenceEmpty _) -> if isPrimitive $ getPExpClaferIdent setExp
      then desugarClafer' dynamic' (Clafer s abstract' tmods gcrd' id' (SuperEmpty s) (ReferenceSet ss setExp) crd' init' trans' elements')
      else desugarClafer' dynamic' claf
    (SuperSome _ setExp, ReferenceSet _ _) -> if isPrimitive $ getPExpClaferIdent setExp
      then error "Desugarer: cannot rewrite : with primitive type into -> because a reference is also present. Using : with primitive types is discouraged."
      else desugarClafer' dynamic' claf
    (SuperSome _ setExp, ReferenceBag _ _) -> if isPrimitive $ getPExpClaferIdent setExp
      then error "Desugarer: cannot rewrite : with primitive type into -> because a reference is also present. Using : with primitive types is discouraged."
      else desugarClafer' dynamic' claf
    _ -> desugarClafer' dynamic' claf

-- | For a reference to a constant, the reference to the constant's type, and the constant.
referenceToConstant :: Reference -> Maybe (Reference, Exp)
referenceToConstant (ReferenceSet s e) = (\t -> (ReferenceSet s t, e)) <$> constantType e
referenceToConstant (ReferenceBag s e) = (\t -> (ReferenceBag s t, e)) <$> constantType e
referenceToConstant _                  = Nothing

-- | The type of a constant, as a reference target.
constantType :: Exp -> Maybe Exp
constantType e = typeExp <$> case e of
    EInt _ _               -> Just integerType
    EDouble _ _            -> Just doubleType
    EReal _ _              -> Just decimalType
    EStr _ _               -> Just stringType
    EMinExp _ (EInt _ _)   -> Just integerType
    EMinExp _ (EDouble _ _) -> Just doubleType
    EMinExp _ (EReal _ _)  -> Just decimalType
    _                      -> Nothing
  where
    s = getSpan e
    typeExp t = ClaferId s (Path s [ModIdIdent s (mkIdent t)])

desugarClafer' :: Bool -> Clafer -> [IElement]
desugarClafer' dynamic' claf'@(Clafer s' abstract' tmods' gcrd' id' super' reference' crd' init' _ elements')
  =  [(IEClafer $ IClafer s' iClaferModifiers (desugarGCard gcrd') (transIdent id')
                          "" "" (desugarSuper super') (desugarReference tmods' reference')
                          crd'' (0, -1)
                          elements'')]
  ++ parentInit
  where
    iClaferModifiers = desugarModifiers abstract' tmods' reference'
    crd'' = desugarCard crd'
    (ownInit, parentInit) = desugarInit dynamic' crd'' id' init'
    -- the transition of a clafer is a constraint of the clafer, whose obligations last as long
    -- as its parent, e.g., `on --> off` takes the traffic light from on to off
    elements'' = desugarElements dynamic' elements' ++ desugarClaferTrans claf' ++ ownInit

desugarModifiers :: Abstract -> [TempModifier] -> Reference -> IClaferModifiers
desugarModifiers    abstract'    tmods           reference' =
  IClaferModifiers (desugarAbstract abstract') (desugarInitiality tmods) (desugarFinality tmods) inherited
  where
  -- finalref or finaltarget of a clafer that inherits its reference, e.g., `finalref motor : engine`
  inherited = case reference' of
    ReferenceEmpty _ -> desugarRefModifiers [ m | m <- tmods, isRefMod m ]
    _ -> []
  isRefMod (AbsClafer.FinalRef _) = True
  isRefMod (AbsClafer.FinalTarget _) = True
  isRefMod _ = False

sugarModifier :: IClaferModifiers -> [TempModifier]
sugarModifier modifiers' =
  (if _initial modifiers' then [Initial noSpan] else [])
  ++
  (if _final modifiers' then [Final noSpan] else [])
  ++
  concatMap sugarRefModifier (_finalReferences modifiers')
  where
  sugarRefModifier m = case m of
     IntClafer.FinalRef -> [AbsClafer.FinalRef noSpan]
     IntClafer.FinalTarget -> [AbsClafer.FinalTarget noSpan]
     _ -> []


getPExpClaferIdent :: Exp -> String
getPExpClaferIdent (ClaferId _ (Path _ [ (ModIdIdent _ pident') ] )) = transIdent pident'
getPExpClaferIdent (EJoin _ _ e2) = getPExpClaferIdent e2
getPExpClaferIdent _ = error "Desugarer:getPExpClaferIdent not given a ClaferId PExp"

sugarClafer :: IClafer -> Clafer
sugarClafer (IClafer s modifiers' gcard' _ uid' _ super' reference' crd' _ elements') =
    Clafer s (sugarAbstract $ _abstract modifiers') (sugarModifier modifiers') (sugarGCard gcard') (mkIdent uid')
      (sugarSuper super') (sugarReference reference') (sugarCard crd') (InitEmpty s) (TransitionEmpty s) (sugarElements elements')

desugarSuper :: Super -> Maybe PExp
desugarSuper (SuperEmpty _) = Nothing
desugarSuper (SuperSome _ (ClaferId _ (Path _ [ (ModIdIdent _ (PosIdent (_, "clafer"))) ] ))) = Nothing
desugarSuper (SuperSome _ setexp) = Just $ desugarExp setexp

desugarReference :: [TempModifier] -> Reference -> Maybe IReference
desugarReference _ (ReferenceEmpty _) = Nothing
desugarReference mods (ReferenceSet _ setexp) = Just $ IReference True (desugarRefModifiers mods) $ desugarExp setexp
desugarReference mods (ReferenceBag _ setexp) = Just $ IReference False (desugarRefModifiers mods) $ desugarExp setexp

-- | The modifiers of the reference, e.g., `final` in `initial final x -> T`, and both in
--   `finalref finaltarget x -> T`, each once
desugarRefModifiers :: [TempModifier] -> [IReferenceModifier]
desugarRefModifiers mods = nub $ mapMaybe refModifier mods
  where
  refModifier modi = case modi of
    Final _ -> Just FinalRefTarget
    AbsClafer.FinalRef _ -> Just IntClafer.FinalRef
    AbsClafer.FinalTarget _ -> Just IntClafer.FinalTarget
    _ -> Nothing

-- | The constraints of the initializer of the clafer @x@: those in the context of @x@, and those
--   in the context of its parent. All are hard constraints.
--
--   * @x -> T = e@ is @[ some x => x.dref = e ]@ in the context of the parent; in a dynamic
--     model, it holds in every state.
--   * @x -> T := e@ is the initial value of the reference. In a static model, which has a single
--     state, it is the same as @=@. In a dynamic model, every lifetime of @x@ starts with the
--     value: @[ initially this.dref = e ]@ in the context of @x@. The value @e@ is written in the
--     context of the parent, so the name resolver resolves it there ('iInitValue'): @this@
--     stays the parent, and a sibling @y@ stays the sibling even if @x@ has a child @y@. So
--     does a @final@ or @finalref@ reference: it keeps the value that @e@ has when its lifetime
--     starts, also when @e@ changes later, which @=@ would contradict.
--   * A set initializer, @xs -> T * := e@, whose cardinality allows more than one instance,
--     constrains the set of the instances under the parent, so it stays in the context of the
--     parent: @[ initially (some xs => xs.dref = e) ]@. The instances created later are not
--     initialized.
desugarInit :: Bool -> Maybe Interval -> PosIdent -> Init -> ([IElement], [IElement])
desugarInit _ _ _ (InitEmpty _) = ([], [])
desugarInit dynamic' crd id' (InitSome s inithow exp') = case inithow of
    InitDefault _ | dynamic' -> if isSet
      then ([], [ IEConstraint True $ pExpDefPid s $ IFunExp iInitially [ pExpDefPid s implIExp ] ])
      else ([ IEConstraint True $ pExpDefPid s $ IFunExp iInitially [ pExpDefPid s ownIExp ] ], [])
    _ -> ([], [ IEConstraint True (pExpDefPid s implIExp) ])
  where
    -- this.dref = initvalue(<exp'>)
    ownIExp :: IExp
    ownIExp = IFunExp iEq
      [ pExpDefPid s $ IFunExp iJoin [ mkPLClaferId s thisIdent False NoBind, mkPLClaferId s drefIdent False NoBind ]
      , pExpDefPid s $ IFunExp iInitValue [ desugarExp exp' ] ]
    -- more than one instance of x under a parent instance
    isSet = case crd of
      Just (_, ex) -> ex `notElem` [0, 1]  -- -1 is *, unbounded
      Nothing -> False
    cId :: PExp
    cId = mkPLClaferId (getSpan id') (snd $ getIdent id') False NoBind
    -- <id> = <exp'>
    assignIExp :: IExp
    assignIExp = (IFunExp "=" [cId, desugarExp exp'])
    -- some <id> => <assignIExp>
    implIExp :: IExp
    implIExp = (IFunExp "=>" [ pExpDefPid s $ IDeclPExp ISome [] cId, pExpDefPid s assignIExp ])
    getIdent (PosIdent y) = y


desugarClaferTrans :: Clafer -> [IElement]
desugarClaferTrans (Clafer _ _ _ _ name _ _ _ _ trans _) =
  case trans of
      TransitionEmpty _ -> []
      -- the constraint spans the clafer's name and its transition, e.g., green --> yellow; its
      -- source is the instance of the clafer
      Transition s arrow e -> let s' = getSpan name >- s in [IEConstraint True (desugarTrans s' (mkClaferIdExp s' thisIdent) arrow e)]

desugarTrans :: Span -> Exp -> TransArrow -> Exp -> PExp
desugarTrans s e1 arrow e2 = desugarExp $ desugarTrans' s e1 arrow e2

-- | The transitions as in Juodisius et al., Clafer: Lightweight Modeling of Structure,
--   Behaviour, and Variability (2019), section 6.1: if the precondition holds in a state,
--   the postcondition holds in the next state (-->), or the precondition and the context
--   instance last until the postcondition holds (-->>); a guard strengthens the precondition.
--
--   Change: a chain of transitions is a sequence, e.g., a scenario
--   @[ initially (green --> yellow --> red) ]@; only its first precondition is a condition,
--   so @a --> b --> c@ is @a => X (b && X c)@, not @a => X (b => X c)@.
desugarTrans' :: Span -> Exp -> TransArrow -> Exp -> Exp
desugarTrans' s e1 arrow e2 = EImplies s (precondition s e1 arrow) (step s e1 arrow $ desugarSequence e2)

-- | The rest of a chain of transitions: the states follow each other.
desugarSequence :: Exp -> Exp
desugarSequence (TransitionExp s e1 arrow e2) = EAnd s (precondition s e1 arrow) (step s e1 arrow $ desugarSequence e2)
desugarSequence e = e

precondition :: Span -> Exp -> TransArrow -> Exp
precondition s e1 arrow = case arrow of
      GuardedSyncTransArrow _ (TransGuard _ guardExp) -> EAnd s e1 guardExp
      GuardedNextTransArrow _ (TransGuard _ guardExp) -> EAnd s e1 guardExp
      _ -> e1

-- | The step from the source @e1@ to the target @e2@.
step :: Span -> Exp -> TransArrow -> Exp -> Exp
step s e1 arrow e2 = case arrow of
      SyncTransArrow _ -> multiStep
      GuardedSyncTransArrow _ _ -> multiStep
      NextTransArrow _ -> LtlX s e2
      GuardedNextTransArrow _ _ -> LtlX s e2
  where
    this' = mkClaferIdExp s thisIdent
    -- the source of a clafer's transition is this
    multiStep = LtlU s (if isThis e1 then this' else EAnd s this' e1) e2
    isThis (ClaferId _ (Path _ [ModIdIdent _ i])) = transIdent i == thisIdent
    isThis _ = False


desugarFinality :: [TempModifier] -> Bool
desugarFinality mods = any isFinalMod mods
  where
    isFinalMod (Final _) = True
    isFinalMod _ = False

desugarInitiality :: [TempModifier] -> Bool
desugarInitiality mods = any isInitialMod mods
  where
    isInitialMod (Initial _) = True
    isInitialMod _ = False


desugarName :: Name -> IExp
desugarName (Path _ path) =
      IClaferId (concatMap ((++ modSep).desugarModId) (init path))
                (desugarModId $ last path) True NoBind

desugarModId :: ModId -> Result
desugarModId (ModIdIdent _ id') = transIdent id'

sugarModId :: String -> ModId
sugarModId modid = ModIdIdent noSpan $ mkIdent modid

sugarSuper :: Maybe PExp -> Super
sugarSuper Nothing = SuperEmpty noSpan
sugarSuper (Just pexp') = SuperSome noSpan (sugarExp pexp')

sugarReference :: Maybe IReference -> Reference
sugarReference Nothing = ReferenceEmpty noSpan
sugarReference (Just (IReference True  _ pexp')) = ReferenceSet noSpan (sugarExp pexp')
sugarReference (Just (IReference False _ pexp')) = ReferenceBag noSpan (sugarExp pexp')

desugarConstraint :: Constraint -> PExp
desugarConstraint (Constraint _ exps') = desugarPath $ desugarExp $
    (if length exps' > 1 then foldl1 (EAnd noSpan) else head) exps'

desugarAssertion :: Assertion -> PExp
desugarAssertion (Assertion _ exps') = desugarPath $ desugarExp $
    (if length exps' > 1 then foldl1 (EAnd noSpan) else head) exps'

desugarGoal :: Goal -> IElement
desugarGoal (GoalMinimize s [exp'])      = mkMinimizeMaximizePExp False s exp'
desugarGoal (GoalMinDeprecated s [exp']) = mkMinimizeMaximizePExp False s exp'
desugarGoal (GoalMaximize s [exp'])      = mkMinimizeMaximizePExp True  s exp'
desugarGoal (GoalMaxDeprecated s [exp']) = mkMinimizeMaximizePExp True  s exp'
desugarGoal goal                         = error $ "Desugarer.desugarGoal: malformed objective:\n" ++ show goal

mkMinimizeMaximizePExp :: Bool     -> Span -> Exp -> IElement
mkMinimizeMaximizePExp    isMaximize' s       exp' =
  IEGoal isMaximize' $ desugarPath $ PExp Nothing "" s $ IFunExp (if isMaximize' then iMaximize else iMinimize) [desugarExp exp']

sugarConstraint :: PExp -> Constraint
sugarConstraint pexp = Constraint (_inPos pexp)  $ map sugarExp [pexp]

sugarAssertion :: PExp -> Assertion
sugarAssertion pexp = Assertion (_inPos pexp) $ map sugarExp [pexp]

sugarGoal :: PExp -> Bool -> Goal
sugarGoal PExp{_exp=IFunExp _ [pexp]} True  = GoalMaximize (_inPos pexp) $ map sugarExp [pexp]
sugarGoal PExp{_exp=IFunExp _ [pexp]} False = GoalMinimize (_inPos pexp) $ map sugarExp [pexp]
sugarGoal goal                        _     = error $ "Desugarer.sugarGoal: malformed objective:\n" ++ show goal

desugarAbstract :: Abstract -> Bool
desugarAbstract (AbstractEmpty _) = False
desugarAbstract (Abstract _) = True


sugarAbstract :: Bool -> Abstract
sugarAbstract False = AbstractEmpty noSpan
sugarAbstract True = Abstract noSpan


desugarElements :: Bool -> Elements -> [IElement]
desugarElements _ (ElementsEmpty _) = []
desugarElements dynamic' (ElementsList _ es)  = es >>= desugarElement dynamic'


sugarElements :: [IElement] -> Elements
sugarElements x = ElementsList noSpan $ map sugarElement x


desugarElement :: Bool -> Element -> [IElement]
desugarElement dynamic' x = case x of
  Subclafer _ claf  -> (desugarClafer dynamic' claf)
  ClaferUse s name crd es  -> desugarClafer dynamic' $ Clafer s
      (AbstractEmpty s) [] (GCardEmpty s) (mkIdent $ _sident $ desugarName name)
      (SuperSome s (ClaferId s name)) (ReferenceEmpty s) crd (InitEmpty s) (TransitionEmpty s) es
  Subconstraint _ constraint  ->
      [IEConstraint True $ desugarConstraint constraint]
  SubAssertion _ assertion ->
      [IEConstraint False $ desugarAssertion assertion]
  Subgoal _ goal -> [desugarGoal goal]


sugarElement :: IElement -> Element
sugarElement x = case x of
  IEClafer claf  -> Subclafer noSpan $ sugarClafer claf
  IEConstraint True constraint -> Subconstraint noSpan $ sugarConstraint constraint
  IEConstraint False assertion -> SubAssertion noSpan $ sugarAssertion assertion
  IEGoal isMaximize' goal -> Subgoal noSpan $ sugarGoal goal isMaximize'

desugarGCard :: GCard -> Maybe IGCard
desugarGCard x = case x of
  GCardEmpty _  -> Nothing
  GCardXor _ -> Just $ IGCard True (1, 1)
  GCardOr _  -> Just $ IGCard True (1, -1)
  GCardMux _ -> Just $ IGCard True (0, 1)
  GCardOpt _ -> Just $ IGCard True (0, -1)
  GCardInterval _ ncard ->
      Just $ IGCard False $ desugarNCard ncard

sugarGCard :: Maybe IGCard -> GCard
sugarGCard x = case x of
  Nothing -> GCardEmpty noSpan
  Just (IGCard _ (i, ex)) -> GCardInterval noSpan $ NCard noSpan (PosInteger ((0, 0), show i)) (sugarExInteger ex)


desugarCard :: Card -> Maybe Interval
desugarCard x = case x of
  CardEmpty _  -> Nothing
  CardLone _  ->  Just (0, 1)
  CardSome _  ->  Just (1, -1)
  CardAny _ ->  Just (0, -1)
  CardNum _ n  -> Just (mkInteger n, mkInteger n)
  CardInterval _ ncard  -> Just $ desugarNCard ncard

desugarNCard :: NCard -> (Integer, Integer)
desugarNCard (NCard _ i ex) = (mkInteger i, desugarExInteger ex)

desugarExInteger :: ExInteger -> Integer
desugarExInteger (ExIntegerAst _) = -1
desugarExInteger (ExIntegerNum _ n) = mkInteger n

sugarCard :: Maybe Interval -> Card
sugarCard x = case x of
  Nothing -> CardEmpty noSpan
  Just (i, ex) ->
      CardInterval noSpan $ NCard noSpan (PosInteger ((0, 0), show i)) (sugarExInteger ex)

sugarExInteger :: Integer -> ExInteger
sugarExInteger n = if n == -1 then ExIntegerAst noSpan else ExIntegerNum noSpan $ PosInteger ((0, 0), show n)

desugarExp :: Exp -> PExp
desugarExp x = pExpDefPid (getSpan x) $ desugarExp' x


translateTmpPatterns :: Exp -> Exp
translateTmpPatterns e = case e of
  TmpPatNever _ p scope -> case scope of
    PatScopeEmpty _ ->            g $ not' p
    PatScopeBefore _ r ->         f r ==> (not' p `u` r)
    PatScopeAfter _ q ->          g(q ==> g (not' p))
    PatScopeBetweenAnd _ q r ->   g ((q & not' r & f r) ==> (not' p `u` r))
    PatScopeAfterUntil _ q r ->   g((q & not' r) ==> (not' p `w` r))
  TmpPatSometime _ p scope -> case scope of
    PatScopeEmpty _ ->            f p
    PatScopeBefore _ r ->         not' r `w` (p & not' r)
    PatScopeAfter _ q ->          g (not' q) || f (q & f p)
    PatScopeBetweenAnd _ q r ->   g ( (q & not' r) ==> (not' r `w` (p & not' r)) )
    PatScopeAfterUntil _ q r ->   g ( (q & not' r) ==> (not' r `u` (p & not' r)) )
  TmpPatLessOrOnce _ p scope -> case scope of
                                  -- (!P W (P W []!P))
    PatScopeEmpty _ ->            not' p `w` (p `w` g (not' p))
                                  -- <> R -> ((!P & !R) U ((R | (P & !R)) U ( R | (!P U R))))
    PatScopeBefore _ r ->         f r ==> ((not' p & not' r) `u` (r || ((p & not' r) `u` (r || (not' p `u` r)))))
                                  -- <>Q -> (!Q U (Q & (!P W (P W []!P))))
    PatScopeAfter _ q ->          f q ==> (not' q `u` (q & (not' p `w` (p `w` g (not' p))) ))
                                  -- []((Q & <>R) -> ((!P & !R) U (R | ((P & !R) U (R | (!P U R))))))
    PatScopeBetweenAnd _ q r ->   g((q & f r) ==> ((not' p & not' r) `u` (r || ((p & not' r) `u` (r || (not' p `u` r))))))
                                  -- [](Q -> ((!P & !R) U (R | ((P & !R) U (R | (!P W R) | []P)))))
    PatScopeAfterUntil _ q r ->   g(q ==> ((not' p & not' r) `u` (r || ((p & not' r) `u` (r || (not' p `w` r) || g p)))))
  TmpPatAlways _ p scope -> case scope of
    PatScopeEmpty _ ->            g p
    PatScopeBefore _ r ->         f r ==> (p `u` r)
    PatScopeAfter _ q ->          g (q ==> g p)
    PatScopeBetweenAnd _ q r ->   g ((q & not' r & f r ) ==> (p `u` r))
    PatScopeAfterUntil _ q r ->   g((q & not' r) ==> (p `w` r))
  TmpPatPrecede _ s p scope -> case scope of
    PatScopeEmpty _ ->            not' p `w` s
    PatScopeBefore _ r ->         f r ==> (not' p `u` (s || r))
                                  -- from the first q: Dwyer's []!Q | <>(Q & (!P W S)) may pick a later q
    PatScopeAfter _ q ->          f q ==> (not' q `u` (q & (not' p `w` s)))
    PatScopeBetweenAnd _ q r ->   g ((q & not' r & f r) ==> (not' p `u` (s || r)))
    PatScopeAfterUntil _ q r ->   g ((q & not' r) ==> (not' p `w` (s || r)))
  TmpPatFollow _ s p scope -> case scope of
    PatScopeEmpty _ ->            g(p ==> f s)
    PatScopeBefore _ r ->         f r ==> ((p ==> (not' r `u` (s & not' r))) `u` r)
    PatScopeAfter _ q ->          g(q ==> g(p ==> f s))
                                  -- every p up to r: []((Q & !R & <>R) -> ((P -> (!R U (S & !R))) U R))
    PatScopeBetweenAnd _ q r ->   g((q & not' r & f r) ==> ((p ==> (not' r `u` (s & not' r))) `u` r))
    PatScopeAfterUntil _ q r ->   g((q & not' r) ==> ((p==> (not' r `u` (s & not' r))) `w` r))
  {-TmpInitially s exp' -> -}
    {-let oper1 =  ENeg s $ mkClaferIdExp s "this"-}
        {-oper2 = LtlX s $ mkClaferIdExp s "this"-}
    {-in EImplies s (EAnd s oper1 oper2) $ LtlX s exp'-}
  TmpEventually s exp' -> LtlF s exp'
  TmpWUntil s exp0 exp1 -> LtlW s exp0 exp1
  TmpUntil s exp0 exp1 -> LtlU s exp0 exp1
  TmpGlobally s exp' -> LtlG s exp'
  TmpNext s exp' -> LtlX s exp'
  TransitionExp s exp0 arrow exp1 -> desugarTrans' s exp0 arrow exp1
  _ -> e
  where
    infixr 4 `u`
    infixr 4 `w`
    infixl 3 &
    infixl 2 ||
    infixr 1 ==>
    w = LtlW span'
    u = LtlU span'
    (==>) e1 e2 = EImplies span' e1 e2
    e1 & e2 = EAnd span' e1 e2
    e1 || e2 = EOr span' e1 e2
    f = LtlF span'
    g = LtlG span'
    not' = ENeg span'
    span' = getSpan e


desugarExp' :: Exp -> IExp
desugarExp' x = let x' =  translateTmpPatterns x in case x' of
  EDeclAllDisj _ decl exp' ->
      IDeclPExp IAll [desugarDecl True decl] (dpe exp')
  EDeclAll _ decl exp' -> IDeclPExp IAll [desugarDecl False decl] (dpe exp')
  EDeclQuantDisj _ quant' decl exp' ->
      IDeclPExp (desugarQuant quant') [desugarDecl True decl] (dpe exp')
  EDeclQuant _ quant' decl exp' ->
      IDeclPExp (desugarQuant quant') [desugarDecl False decl] (dpe exp')
  EIff _ exp0 exp'  -> dop iIff [exp0, exp']
  EImplies _ exp0 exp'  -> dop iImpl [exp0, exp']
  EImpliesElse _ exp0 exp1 exp'  -> dop iIfThenElse [exp0, exp1, exp']
  EOr _ exp0 exp'  -> dop iOr   [exp0, exp']
  EXor _ exp0 exp'  -> dop iXor [exp0, exp']
  EAnd _ exp0 exp'  -> dop iAnd [exp0, exp']
  ENeg _ exp'  -> dop iNot [exp']
  LtlU  _ exp0 exp'  -> dop iU  [exp0, exp']
  LtlW  _ exp0 exp'  -> dop iW  [exp0, exp']
  LtlF  _ exp'  -> dop iF  [exp']
  LtlG  _ exp'  -> dop iG  [exp']
  LtlX  _ exp'  -> dop iX  [exp']
  TmpInitially _ exp' -> dop iInitially [exp']
  TmpFinally _ exp' -> dop iFinally [exp']
  EQuantExp _ quant' exp' ->
      IDeclPExp (desugarQuant quant') [] (desugarExp exp')
  ELt  _ exp0 exp'  -> dop iLt  [exp0, exp']
  EGt  _ exp0 exp'  -> dop iGt  [exp0, exp']
  EEq  _ exp0 exp'  -> dop iEq  [exp0, exp']
  ELte _ exp0 exp'  -> dop iLte [exp0, exp']
  EGte _ exp0 exp'  -> dop iGte [exp0, exp']
  ENeq _ exp0 exp'  -> dop iNeq [exp0, exp']
  EIn  _ exp0 exp'  -> dop iIn  [exp0, exp']
  ENin _ exp0 exp'  -> dop iNin [exp0, exp']
  EAdd _ exp0 exp'  -> dop iPlus [exp0, exp']
  ESub _ exp0 exp'  -> dop iSub [exp0, exp']
  EMul _ exp0 exp'  -> dop iMul [exp0, exp']
  EDiv _ exp0 exp'  -> dop iDiv [exp0, exp']
  ERem _ exp0 exp'  -> dop iRem [exp0, exp']
  ECard _ exp'   -> dop iCSet [exp']
  ESum _ exp' -> dop iSumSet [exp']
  EProd _ exp' -> dop iProdSet [exp']
  EMinExp _ exp'    -> dop iMin [exp']
  EGMax _ exp' -> dop iMaximum [exp']
  EGMin _ exp' -> dop iMinimum [exp']
  EInt _ n  -> IInt $ mkInteger n
  EDouble _ (PosDouble n) -> IDouble $ read $ snd n
  -- a plain decimal literal, e.g., 19.99, is a decimal, kept as written
  EReal _ (PosReal n) -> IDecimal $ snd n
  EStr _ (PosString str)  -> IStr $ snd str
  EUnion _ exp0 exp'        -> dop iUnion        [exp0, exp']
  EUnionCom _ exp0 exp'     -> dop iUnion        [exp0, exp']
  EDifference _ exp0 exp'   -> dop iDifference   [exp0, exp']
  EIntersection _ exp0 exp' -> dop iIntersection [exp0, exp']
  EIntersectionDeprecated _ exp0 exp' -> dop iIntersection [exp0, exp']
  EDomain _ exp0 exp'       -> dop iDomain       [exp0, exp']
  ERange _ exp0 exp'        -> dop iRange        [exp0, exp']
  EJoin _ exp0 exp'         -> dop iJoin         [exp0, exp']
  ClaferId _ name  -> desugarName name
  TransitionExp{} -> showPatErr
  LetExp _ vb e -> desugarExp' $ desugarLet vb e
  TmpPatNever{} -> showPatErr
  TmpPatSometime{} -> showPatErr
  TmpPatLessOrOnce{} -> showPatErr
  TmpPatAlways{} -> showPatErr
  TmpPatPrecede{} -> showPatErr
  TmpPatFollow{} -> showPatErr
  TmpUntil{} -> showPatErr
  TmpWUntil{} -> showPatErr
  TmpEventually{} -> showPatErr
  TmpNext{} -> showPatErr
  TmpGlobally{} -> showPatErr
  where
  showPatErr = error ("[bug] Desugarer: pattern expressions should have been transformed previously. Problem expression:\n" ++ show x)
  dop = desugarOp desugarExp
  dpe = desugarPath.desugarExp

-- | @let v = e in body@ is @body@ with @e@ for the name @v@. A quantifier or a @let@ in @body@
--   which binds @v@ again hides it there, and one which binds a name used in @e@ is renamed
--   to a fresh name, e.g., @x_1@, so that @e@ keeps its meaning.
desugarLet :: VarBinding -> Exp -> Exp
desugarLet (VarBinding _ (LocIdIdent _ (PosIdent (_, v))) e) = substName v e

-- | Substitutes an expression for the free occurrences of a local name.
substName :: String -> Exp -> Exp -> Exp
substName v e = goE
  where
  namesOfE = namesIn e
  go :: Data a => a -> a
  go x = case cast x of
    Just ex -> fromMaybe x $ cast $ goE ex
    Nothing -> gmapT go x
  goE :: Exp -> Exp
  goE x = case x of
    ClaferId _ (Path _ [ModIdIdent _ (PosIdent (_, n))]) | n == v -> e
    EDeclAllDisj s d b -> let (d', b') = goDecl d b in EDeclAllDisj s d' b'
    EDeclAll s d b -> let (d', b') = goDecl d b in EDeclAll s d' b'
    EDeclQuantDisj s q d b -> let (d', b') = goDecl d b in EDeclQuantDisj s q d' b'
    EDeclQuant s q d b -> let (d', b') = goDecl d b in EDeclQuant s q d' b'
    LetExp s (VarBinding s' l e') b -> case goBound [l] b of
      ([l'], b') -> LetExp s (VarBinding s' l' $ goE e') b'
      _ -> x
    _ -> gmapT go x
  goDecl (Decl s ls set) b = let (ls', b') = goBound ls b in (Decl s ls' $ goE set, b')
  -- the names bound by a quantifier or a let, and its body
  goBound :: [LocId] -> Exp -> ([LocId], Exp)
  goBound ls b
    | v `elem` map locIdName ls  = (ls, b)
    | v `notElem` namesIn b     = (ls, b)
    | otherwise                 = (ls', goE $ foldr renameIn b $ zip ls ls')
    where
    taken = namesOfE ++ namesIn b ++ map locIdName ls
    ls' = map rename ls
    rename l@(LocIdIdent s (PosIdent (p, n)))
      | n `elem` namesOfE = LocIdIdent s $ PosIdent (p, head [ n' | k <- [1 :: Int ..], let n' = n ++ "_" ++ show k, n' `notElem` taken ])
      | otherwise         = l
    renameIn (old, new@(LocIdIdent s _)) b'
      | old == new = b'
      | otherwise  = substName (locIdName old) (ClaferId s $ Path s [ModIdIdent s $ locIdPosIdent new]) b'
  locIdName (LocIdIdent _ (PosIdent (_, n))) = n
  locIdPosIdent (LocIdIdent _ i) = i

-- | The identifiers in a part of the AST.
namesIn :: Data a => a -> [String]
namesIn x = case cast x of
  Just (PosIdent (_, n)) -> [n]
  Nothing                -> concat $ gmapQ namesIn x

desugarOp :: (a -> PExp) -> String -> [a] -> IExp
desugarOp f op' exps' =
    if (op' == iIfThenElse)
      then IFunExp op' $ (desugarPath $ head mappedList) : (map reducePExp $ tail mappedList)
      else IFunExp op' $ map (trans.f) exps'
    where
      mappedList = map f exps'
      trans = if op' `elem` ([iNot, iIfThenElse] ++ logBinOps ++ ltlUnOps)
          then desugarPath else id

sugarExp :: PExp -> Exp
sugarExp x = sugarExp' $ _exp x


sugarExp' :: IExp -> Exp
sugarExp' x = case x of
  IDeclPExp quant' [] pexp -> EQuantExp noSpan (sugarQuant quant') (sugarExp pexp)
  IDeclPExp IAll (decl@(IDecl True _ _):[]) pexp ->
    EDeclAllDisj noSpan (sugarDecl decl) (sugarExp pexp)
  IDeclPExp IAll  (decl@(IDecl False _ _):[]) pexp ->
    EDeclAll noSpan (sugarDecl decl) (sugarExp pexp)
  IDeclPExp quant' (decl@(IDecl True _ _):[]) pexp ->
    EDeclQuantDisj noSpan (sugarQuant quant') (sugarDecl decl) (sugarExp pexp)
  IDeclPExp quant' (decl@(IDecl False _ _):[]) pexp ->
    EDeclQuant noSpan (sugarQuant quant') (sugarDecl decl) (sugarExp pexp)
  IClaferId "" id' _ _ -> ClaferId noSpan $ Path noSpan [ModIdIdent noSpan $ mkIdent id']
  IClaferId modName' id' _ _ -> ClaferId noSpan $ Path noSpan $ (sugarModId modName') : [sugarModId id']
  IInt n -> EInt noSpan $ PosInteger ((0, 0), show n)
  IDouble n -> EDouble noSpan $ PosDouble ((0, 0), show n)
  IDecimal n -> EReal noSpan $ PosReal ((0, 0), n)
  IReal n -> EReal noSpan $ PosReal ((0, 0), show n)
  IStr str -> EStr noSpan $ PosString ((0, 0), str)
  -- the value of an initializer, which keeps its context ('iInitValue')
  IFunExp op' [value] | op' == iInitValue -> sugarExp' $ _exp value
  IFunExp op' exps' ->
    if op' `elem` unOps then (sugarUnOp op') (exps''!!0)
    else if op' `elem` binOps then (sugarOp op') (exps''!!0) (exps''!!1)
    else (sugarTerOp op') (exps''!!0) (exps''!!1) (exps''!!2)
    where
    exps'' = map sugarExp exps'
  x' -> error $ "Desugarer.sugarExp': invalid argument: " ++ show x' -- This should never happen
  where
  sugarUnOp op''
    | op'' == iNot           = ENeg noSpan
    | op'' == iCSet          = ECard noSpan
    | op'' == iMin           = EMinExp noSpan
    | op'' == iMaximum       = EGMax noSpan
    | op'' == iMinimum       = EGMin noSpan
    | op'' == iSumSet        = ESum noSpan
    | op'' == iProdSet       = EProd noSpan
    | op'' == iF             = LtlF noSpan
    | op'' == iG             = LtlG noSpan
    | op'' == iX             = LtlX noSpan
    | op'' == iInitially     = TmpInitially noSpan
    | op'' == iFinally       = TmpFinally noSpan
    | otherwise              = error $ show op'' ++ "is not an op"
  sugarOp op''
    | op'' == iIff           = EIff noSpan
    | op'' == iImpl          = EImplies noSpan
    | op'' == iOr            = EOr noSpan
    | op'' == iXor           = EXor noSpan
    | op'' == iAnd           = EAnd noSpan
    | op'' == iLt            = ELt noSpan
    | op'' == iGt            = EGt noSpan
    | op'' == iEq            = EEq noSpan
    | op'' == iLte           = ELte noSpan
    | op'' == iGte           = EGte noSpan
    | op'' == iNeq           = ENeq noSpan
    | op'' == iIn            = EIn noSpan
    | op'' == iNin           = ENin noSpan
    | op'' == iPlus          = EAdd noSpan
    | op'' == iSub           = ESub noSpan
    | op'' == iMul           = EMul noSpan
    | op'' == iDiv           = EDiv noSpan
    | op'' == iRem           = ERem noSpan
    | op'' == iU             = LtlU noSpan
    | op'' == iW             = LtlW noSpan
    | op'' == iUnion         = EUnion noSpan
    | op'' == iDifference    = EDifference noSpan
    | op'' == iIntersection  = EIntersection noSpan
    | op'' == iDomain        = EDomain noSpan
    | op'' == iRange         = ERange noSpan
    | op'' == iJoin          = EJoin noSpan
    | otherwise            = error $ show op'' ++ "is not an op"
  sugarTerOp op''
    | op'' == iIfThenElse    = EImpliesElse noSpan
    | otherwise            = error $ show op'' ++ "is not an op"


desugarPath :: PExp -> PExp
desugarPath (PExp iType' pid' pos' x) = reducePExp $ PExp iType' pid' pos' result
  where
  result
    | isSetExp x     = IDeclPExp ISome [] (pExpDefPid pos' x)
    | isNegSome x = IDeclPExp INo   [] $ _bpexp $ _exp $ head $ _exps x
    | otherwise   =  x
  isNegSome (IFunExp op' [PExp _ _ _ (IDeclPExp ISome [] _)]) = op' == iNot
  isNegSome _ = False


isSetExp :: IExp -> Bool
isSetExp (IClaferId _ _ _ _)  = True
isSetExp (IFunExp op' _) = op' `elem` setBinOps
isSetExp _ = False


-- reduce parent
reducePExp :: PExp -> PExp
reducePExp (PExp t pid' pos' x) = PExp t pid' pos' $ reduceIExp x

reduceIExp :: IExp -> IExp
reduceIExp (IDeclPExp quant' decls' pexp) = IDeclPExp quant' decls' $ reducePExp pexp
reduceIExp (IFunExp op' exps') = redNav $ IFunExp op' $ map redExps exps'
    where
    (redNav, redExps) = if op' == iJoin then (reduceNav, id) else (id, reducePExp)
reduceIExp x = x

reduceNav :: IExp -> IExp
reduceNav x@(IFunExp op' exps'@((PExp _ _ _ iexp@(IFunExp _ (pexp0:pexp:_))):pPexp:_)) =
  if op' == iJoin && isParent pPexp && isClaferName pexp
  then reduceNav $ _exp pexp0
  else x{_exps = (head exps'){_exp = reduceIExp iexp} :
                tail exps'}
reduceNav x = x


desugarDecl :: Bool -> Decl -> IDecl
desugarDecl isDisj' (Decl _ locids exp') =
    IDecl isDisj' (map desugarLocId locids) (desugarExp exp')


sugarDecl :: IDecl -> Decl
sugarDecl (IDecl _ locids exp') =
    Decl noSpan (map sugarLocId locids) (sugarExp exp')


desugarLocId :: LocId -> String
desugarLocId (LocIdIdent _ id') = transIdent id'


sugarLocId :: String -> LocId
sugarLocId x = LocIdIdent noSpan $ mkIdent x

desugarQuant :: Quant -> IQuant
desugarQuant (QuantNo _) = INo
desugarQuant (QuantNot _) = INo
desugarQuant (QuantLone _) = ILone
desugarQuant (QuantOne _) = IOne
desugarQuant (QuantSome _) = ISome

sugarQuant :: IQuant -> Quant
sugarQuant INo = QuantNo noSpan  -- will never sugar to QuantNOT
sugarQuant ILone = QuantLone noSpan
sugarQuant IOne = QuantOne noSpan
sugarQuant ISome = QuantSome noSpan
sugarQuant IAll = error "sugarQaunt was called on IAll, this is not allowed!" --Should never happen

mkClaferIdExp :: Span -> String -> Exp
mkClaferIdExp s name = ClaferId s $ Path s [ModIdIdent s $ mkIdent name]