-- generateGoalFromTree :: [([G S], G S)] -> ConsPDTree -> FN.FreshNames -> G X
generateGoalFromTree :: CpdR.Definitions -> [([G S], G S)] -> ConsPDTree -> [S] -> G X
generateGoalFromTree definitions invocations tree args =
    trace (printf "GenerateGoalFromTree\n%s\n\n" (show $ nodeContent tree)) $ 
    case go args True tree of
      Just goal ->
        let normalized = goal in --  NonConjunctive.Unfold.disj $ map NonConjunctive.Unfold.conj $ normalize goal in
        Res.vident <$> normalized
      Nothing -> error $ printf "Failed to generate relation body for %s" (show $ nodeContent tree)
    -- Res.vident <$> (disj (map conj $ filter (not . null) $ go tree))
  where
    residualizeEnv :: Subst.Subst -> Maybe (G S)
    residualizeEnv xs =
      (conj $ map (\(s, ts) -> (V s) === ts) $ reverse (Subst.toList xs)) <|> return success

    go :: [S] -> Bool -> ConsPDTree -> Maybe (G S)
    go seen r tree = 
        let res = go' seen r tree  in 
        trace (printf "Go:\n%s\nTree\n%s\nR: %s\nSeen\n%s\nResult\n%s\n\n" (show (nodeContent tree)) (show tree) (show r) (show seen) (show res)) $ 
        res 
      where 
        go' seen r Fail           = Just failure
        go' seen r (Success ss _) = residualizeEnv ss
        -- go' seen False (Or ch (Descend gs _) s) | gs `elem` map fst3 definitions = do 
        --   let unifs = residualizeEnv s 
        --   let rest = generateInvocation' definitions gs gs 
        --   mkGoal unifs (Just rest) 
        go' seen r (Or ch (Descend gs _) s) = do
          -- let vs = getNewVars seen gs s
          let unifs = residualizeEnv s
          let rest = getInvocation r gs <|> (disj $ catMaybes $ map (go seen False) ch)
          let res = mkGoal unifs rest
          res 
        go' seen r (Split ch gs s)  = do
          -- let vs = getNewVars seen gs s
          let unifs = residualizeEnv s
          let rest = getInvocation r gs <|> (conj $ catMaybes $ map (go seen False) ch)
          mkGoal unifs rest
        go' seen r (Leaf gs s _ vs) = do
          let unifs = residualizeEnv s
          let rest = getInvocation' gs vs -- snd (fromJust $ find ((gs ==) . fst) invocations)
          mkGoal unifs rest
        go' seen r (Conj ch gs s)   = do
          let unifs = residualizeEnv s
          let rest = getInvocation r gs <|> (conj $ catMaybes $ map (go seen False) ch)
          mkGoal unifs rest
        go' seen r (Gen ch gs gs' gen s) = do
          let unifs = residualizeEnv s
          let generalizer = residualizeEnv gen
          let rest = getInvocation r gs <|> (conj $ catMaybes [go seen False ch])
          mkGoal (mkGoal unifs generalizer) rest
        go' seen r (Prune _ _)     = error "Failed to residualize: Prune node in tree"

    mkGoal (Just u) (Just r) =
        Just (f u r)
      where
        f (Conjunction x x' xs) (Conjunction y y' ys) = Conjunction x x' (xs ++ y : y' : ys)
        f g (Conjunction y y' ys) = Conjunction g y (y' : ys)
        f (Conjunction x x' xs) g = Conjunction x x' (xs ++ [g])
        f g h = Conjunction g h []
    mkGoal (Just u) Nothing = Just u
    mkGoal Nothing (Just r) = Just r
    mkGoal _ _ = Nothing

    -- getNewVars seen goal subst =
    --   let vg = concatMap fvgs goal in
    --   let vs = map fst subst ++ concatMap (fv . snd) subst in
    --   (nub $ union vg vs) \\ seen

    getInvocation True gs =
      Nothing
    getInvocation _   gs =
      let res = snd <$> (find ((gs ==) . fst) invocations) in
      -- let res = snd <$> (find ((gs `isVariant`) . fst) invocations) in
      res

    getInvocation' gs v = return $ generateInvocation' definitions gs v


  -- go :: ConsPDTree -> [[G S]]
    -- go Fail            = [[fail]]
    -- go (Success ss _) | null ss = [[success]]
    -- go (Success ss _)  = [residualizeEnv ss]
    -- go (Or ch _ s)     = let unifs = residualizeEnv s in concatMap (map (unifs ++) . go) ch
    -- go (Conj ch _ s)   = let unifs = residualizeEnv s in map (unifs ++) $ concat $ productList $ map go ch
    -- go (Split ch _ s)  = let unifs = residualizeEnv s in map (unifs ++) $ concat $ productList $ map go ch
    -- go (Leaf gs s _ _) = [residualizeEnv s ++ [snd (fromJust $ find ((gs ==) . fst) invocations)]]
    -- go (Gen _ _ _)     = error "Failed to residualize: Gen node in tree"
    -- go (Prune _ _)     = error "Failed to residualize: Prune node in tree"
generateGoalFromTree :: CpdR.Definitions -> [([G S], G S)] -> ConsPDTree -> [S] -> G X
generateGoalFromTree definitions invocations tree args =
    trace (printf "GenerateGoalFromTree\n%s\n\n" (show $ nodeContent tree)) $ 
    case go args True tree of
      Just goal ->
        let normalized = goal in --  NonConjunctive.Unfold.disj $ map NonConjunctive.Unfold.conj $ normalize goal in
        Res.vident <$> normalized
      Nothing -> error $ printf "Failed to generate relation body for %s" (show $ nodeContent tree)
    -- Res.vident <$> (disj (map conj $ filter (not . null) $ go tree))
  where
    residualizeEnv :: Subst.Subst -> Maybe (G S)
    residualizeEnv xs =
      (conj $ map (\(s, ts) -> (V s) === ts) $ reverse (Subst.toList xs)) <|> return success

    go :: [S] -> Bool -> ConsPDTree -> Maybe (G S)
    go seen r tree = 
        let res = go' seen r tree  in 
        trace (printf "Go:\n%s\nTree\n%s\nR: %s\nSeen\n%s\nResult\n%s\n\n" (show (nodeContent tree)) (show tree) (show r) (show seen) (show res)) $ 
        res 
      where 
        go' seen r Fail           = Just failure
        go' seen r (Success ss _) = residualizeEnv ss
        -- go' seen False (Or ch (Descend gs _) s) | gs `elem` map fst3 definitions = do 
        --   let unifs = residualizeEnv s 
        --   let rest = generateInvocation' definitions gs gs 
        --   mkGoal unifs (Just rest) 
        go' seen r (Or ch (Descend gs _) s) = do
          -- let vs = getNewVars seen gs s
          let unifs = residualizeEnv s
          let rest = getInvocation r gs <|> (disj $ catMaybes $ map (go seen False) ch)
          let res = mkGoal unifs rest
          res 
        go' seen r (Split ch gs s)  = do
          -- let vs = getNewVars seen gs s
          let unifs = residualizeEnv s
          let rest = getInvocation r gs <|> (conj $ catMaybes $ map (go seen False) ch)
          mkGoal unifs rest
        go' seen r (Leaf gs s _ vs) = do
          let unifs = residualizeEnv s
          let rest = getInvocation' gs vs -- snd (fromJust $ find ((gs ==) . fst) invocations)
          mkGoal unifs rest
        go' seen r (Conj ch gs s)   = do
          let unifs = residualizeEnv s
          let rest = getInvocation r gs <|> (conj $ catMaybes $ map (go seen False) ch)
          mkGoal unifs rest
        go' seen r (Gen ch gs gs' gen s) = do
          let unifs = residualizeEnv s
          let generalizer = residualizeEnv gen
          let rest = getInvocation r gs <|> (conj $ catMaybes [go seen False ch])
          mkGoal (mkGoal unifs generalizer) rest
        go' seen r (Prune _ _)     = error "Failed to residualize: Prune node in tree"

    mkGoal (Just u) (Just r) =
        Just (f u r)
      where
        f (Conjunction x x' xs) (Conjunction y y' ys) = Conjunction x x' (xs ++ y : y' : ys)
        f g (Conjunction y y' ys) = Conjunction g y (y' : ys)
        f (Conjunction x x' xs) g = Conjunction x x' (xs ++ [g])
        f g h = Conjunction g h []
    mkGoal (Just u) Nothing = Just u
    mkGoal Nothing (Just r) = Just r
    mkGoal _ _ = Nothing

    -- getNewVars seen goal subst =
    --   let vg = concatMap fvgs goal in
    --   let vs = map fst subst ++ concatMap (fv . snd) subst in
    --   (nub $ union vg vs) \\ seen

    getInvocation True gs =
      Nothing
    getInvocation _   gs =
      let res = snd <$> (find ((gs ==) . fst) invocations) in
      -- let res = snd <$> (find ((gs `isVariant`) . fst) invocations) in
      res

    getInvocation' gs v = return $ generateInvocation' definitions gs v


  -- go :: ConsPDTree -> [[G S]]
    -- go Fail            = [[fail]]
    -- go (Success ss _) | null ss = [[success]]
    -- go (Success ss _)  = [residualizeEnv ss]
    -- go (Or ch _ s)     = let unifs = residualizeEnv s in concatMap (map (unifs ++) . go) ch
    -- go (Conj ch _ s)   = let unifs = residualizeEnv s in map (unifs ++) $ concat $ productList $ map go ch
    -- go (Split ch _ s)  = let unifs = residualizeEnv s in map (unifs ++) $ concat $ productList $ map go ch
    -- go (Leaf gs s _ _) = [residualizeEnv s ++ [snd (fromJust $ find ((gs ==) . fst) invocations)]]
    -- go (Gen _ _ _)     = error "Failed to residualize: Gen node in tree"
    -- go (Prune _ _)     = error "Failed to residualize: Prune node in tree"
generateGoalFromTree definitions invocations tree args =
    trace (printf "GenerateGoalFromTree\n%s\n\n" (show $ nodeContent tree)) $ 
    case go args True tree of
      Just goal ->
        let normalized = goal in --  NonConjunctive.Unfold.disj $ map NonConjunctive.Unfold.conj $ normalize goal in
        Res.vident <$> normalized
      Nothing -> error $ printf "Failed to generate relation body for %s" (show $ nodeContent tree)
    -- Res.vident <$> (disj (map conj $ filter (not . null) $ go tree))
  where
    residualizeEnv :: Subst.Subst -> Maybe (G S)
    residualizeEnv xs =
      (conj $ map (\(s, ts) -> (V s) === ts) $ reverse (Subst.toList xs)) <|> return success

    go :: [S] -> Bool -> ConsPDTree -> Maybe (G S)
    go seen r tree = 
        let res = go' seen r tree  in 
        trace (printf "Go:\n%s\nTree\n%s\nR: %s\nSeen\n%s\nResult\n%s\n\n" (show (nodeContent tree)) (show tree) (show r) (show seen) (show res)) $ 
        res 
      where 
        go' seen r Fail           = Just failure
        go' seen r (Success ss _) = residualizeEnv ss
        -- go' seen False (Or ch (Descend gs _) s) | gs `elem` map fst3 definitions = do 
        --   let unifs = residualizeEnv s 
        --   let rest = generateInvocation' definitions gs gs 
        --   mkGoal unifs (Just rest) 
        go' seen r (Or ch (Descend gs _) s) = do
          -- let vs = getNewVars seen gs s
          let unifs = residualizeEnv s
          let rest = getInvocation r gs <|> (disj $ catMaybes $ map (go seen False) ch)
          let res = mkGoal unifs rest
          res 
        go' seen r (Split ch gs s)  = do
          -- let vs = getNewVars seen gs s
          let unifs = residualizeEnv s
          let rest = getInvocation r gs <|> (conj $ catMaybes $ map (go seen False) ch)
          mkGoal unifs rest
        go' seen r (Leaf gs s _ vs) = do
          let unifs = residualizeEnv s
          let rest = getInvocation' gs vs -- snd (fromJust $ find ((gs ==) . fst) invocations)
          mkGoal unifs rest
        go' seen r (Conj ch gs s)   = do
          let unifs = residualizeEnv s
          let rest = getInvocation r gs <|> (conj $ catMaybes $ map (go seen False) ch)
          mkGoal unifs rest
        go' seen r (Gen ch gs gs' gen s) = do
          let unifs = residualizeEnv s
          let generalizer = residualizeEnv gen
          let rest = getInvocation r gs <|> (conj $ catMaybes [go seen False ch])
          mkGoal (mkGoal unifs generalizer) rest
        go' seen r (Prune _ _)     = error "Failed to residualize: Prune node in tree"

    mkGoal (Just u) (Just r) =
        Just (f u r)
      where
        f (Conjunction x x' xs) (Conjunction y y' ys) = Conjunction x x' (xs ++ y : y' : ys)
        f g (Conjunction y y' ys) = Conjunction g y (y' : ys)
        f (Conjunction x x' xs) g = Conjunction x x' (xs ++ [g])
        f g h = Conjunction g h []
    mkGoal (Just u) Nothing = Just u
    mkGoal Nothing (Just r) = Just r
    mkGoal _ _ = Nothing

    -- getNewVars seen goal subst =
    --   let vg = concatMap fvgs goal in
    --   let vs = map fst subst ++ concatMap (fv . snd) subst in
    --   (nub $ union vg vs) \\ seen

    getInvocation True gs =
      Nothing
    getInvocation _   gs =
      let res = snd <$> (find ((gs ==) . fst) invocations) in
      -- let res = snd <$> (find ((gs `isVariant`) . fst) invocations) in
      res

    getInvocation' gs v = return $ generateInvocation' definitions gs v


  -- go :: ConsPDTree -> [[G S]]
    -- go Fail            = [[fail]]
    -- go (Success ss _) | null ss = [[success]]
    -- go (Success ss _)  = [residualizeEnv ss]
    -- go (Or ch _ s)     = let unifs = residualizeEnv s in concatMap (map (unifs ++) . go) ch
    -- go (Conj ch _ s)   = let unifs = residualizeEnv s in map (unifs ++) $ concat $ productList $ map go ch
    -- go (Split ch _ s)  = let unifs = residualizeEnv s in map (unifs ++) $ concat $ productList $ map go ch
    -- go (Leaf gs s _ _) = [residualizeEnv s ++ [snd (fromJust $ find ((gs ==) . fst) invocations)]]
    -- go (Gen _ _ _)     = error "Failed to residualize: Gen node in tree"
    -- go (Prune _ _)     = error "Failed to residualize: Prune node in tree"