| 1 |
{-# LANGUAGE CPP #-} |
| 2 |
{-# LANGUAGE DeriveFoldable #-} |
| 3 |
{-# LANGUAGE FlexibleInstances #-} |
| 4 |
{-# LANGUAGE OverloadedStrings #-} |
| 5 |
{-# LANGUAGE ScopedTypeVariables #-} |
| 6 |
|
| 7 |
-- the CPP seems to confuse GHC; we have uniplate patterns |
| 8 |
{-# OPTIONS_GHC -fno-warn-unused-binds -fno-warn-incomplete-patterns #-} |
| 9 |
{-# OPTIONS_HADDOCK show-extensions #-} |
| 10 |
|
| 11 |
-- | |
| 12 |
-- Module : Yi.Syntax.Tree |
| 13 |
-- License : GPL-2 |
| 14 |
-- Maintainer : [email protected] |
| 15 |
-- Stability : experimental |
| 16 |
-- Portability : portable |
| 17 |
|
| 18 |
-- Generic syntax tree handling functions |
| 19 |
module Yi.Syntax.Tree (IsTree(..), toksAfter, allToks, tokAtOrBefore, |
| 20 |
toksInRegion, sepBy, sepBy1, |
| 21 |
getLastOffset, getFirstOffset, |
| 22 |
getFirstElement, getLastElement, |
| 23 |
getLastPath, |
| 24 |
getAllSubTrees, |
| 25 |
tokenBasedAnnots, tokenBasedStrokes, |
| 26 |
subtreeRegion, |
| 27 |
fromLeafToLeafAfter, fromNodeToFinal) |
| 28 |
where |
| 29 |
|
| 30 |
-- Some of this might be replaced by a generic package |
| 31 |
-- such as multirec, uniplace, emgm, ... |
| 32 |
|
| 33 |
import Prelude hiding (concatMap, error) |
| 34 |
|
| 35 |
import Control.Applicative (Alternative ((<|>), many)) |
| 36 |
import Control.Arrow (first) |
| 37 |
import Data.Foldable (concatMap, toList) |
| 38 |
import Data.List.NonEmpty (NonEmpty (..)) |
| 39 |
import qualified Data.List.NonEmpty as NE (reverse, toList, (<|)) |
| 40 |
import Data.Maybe (catMaybes, listToMaybe) |
| 41 |
import Data.Monoid (First (First, getFirst), Last (Last, getLast), (<>)) |
| 42 |
import Yi.Buffer.Basic (Point) |
| 43 |
import Yi.Debug (error, trace) |
| 44 |
import Yi.Lexer.Alex (posnLine, posnOfs, |
| 45 |
Tok (tokPosn), tokBegin, tokEnd) |
| 46 |
import Yi.Region (Region (regionEnd, regionStart), mkRegion) |
| 47 |
import Yi.String (showT) |
| 48 |
|
| 49 |
-- Fundamental types |
| 50 |
type Path = [Int] |
| 51 |
type Node t = (Path, t) |
| 52 |
|
| 53 |
class Foldable tree => IsTree tree where |
| 54 |
-- | Direct subtrees of a tree |
| 55 |
subtrees :: tree t -> [tree t] |
| 56 |
subtrees = fst . uniplate |
| 57 |
uniplate :: tree t -> ([tree t], [tree t] -> tree t) |
| 58 |
emptyNode :: tree t |
| 59 |
|
| 60 |
toksAfter :: Foldable t1 => t -> t1 a -> [a] |
| 61 |
toksAfter _begin = allToks |
| 62 |
|
| 63 |
allToks :: Foldable t => t a -> [a] |
| 64 |
allToks = toList |
| 65 |
|
| 66 |
tokAtOrBefore :: Foldable t => Point -> t (Tok t1) -> Maybe (Tok t1) |
| 67 |
tokAtOrBefore p res = |
| 68 |
listToMaybe $ reverse $ toksInRegion (mkRegion 0 (p+1)) res |
| 69 |
|
| 70 |
toksInRegion :: Foldable t1 => Region -> t1 (Tok t) -> [Tok t] |
| 71 |
toksInRegion reg = takeWhile (\t -> tokBegin t <= regionEnd reg) |
| 72 |
. dropWhile (\t -> tokEnd t < regionStart reg) |
| 73 |
. toksAfter (regionStart reg) |
| 74 |
|
| 75 |
tokenBasedAnnots :: (Foldable t1) => (a1 -> Maybe a) -> t1 a1 -> t -> [a] |
| 76 |
tokenBasedAnnots tta t begin = catMaybes (tta <$> toksAfter begin t) |
| 77 |
|
| 78 |
tokenBasedStrokes :: (Foldable t3) => (a -> b) -> t3 a -> t -> t2 -> t1 -> [b] |
| 79 |
tokenBasedStrokes tts t _point begin _end = tts <$> toksAfter begin t |
| 80 |
|
| 81 |
-- | Prune the nodes before the given point. |
| 82 |
-- The path is used to know which nodes we can force or not. |
| 83 |
pruneNodesBefore :: IsTree tree => Point -> Path -> tree (Tok a) -> tree (Tok a) |
| 84 |
pruneNodesBefore _ [] t = t |
| 85 |
pruneNodesBefore p (x:xs) t = rebuild $ left' <> (pruneNodesBefore p xs c : rs) |
| 86 |
where (children,rebuild) = uniplate t |
| 87 |
(left,c:rs) = splitAt x children |
| 88 |
left' = fmap replaceEmpty left |
| 89 |
replaceEmpty s = if getLastOffset s < p then emptyNode else s |
| 90 |
|
| 91 |
-- | Given an approximate path to a leaf at the end of the region, |
| 92 |
-- return: (path to leaf at the end of the region,path from focused |
| 93 |
-- node to the leaf, small node encompassing the region) |
| 94 |
fromNodeToFinal :: IsTree tree => Region -> Node (tree (Tok a)) |
| 95 |
-> Node (tree (Tok a)) |
| 96 |
fromNodeToFinal r (xs,root) = |
| 97 |
trace ("r = " <> showT r) $ |
| 98 |
trace ("focused ~ " <> showT (subtreeRegion focused) ) $ |
| 99 |
trace ("pathFromFocusedToLeaf = " <> showT focusedToLeaf) $ |
| 100 |
trace ("pruned ~ " <> showT (subtreeRegion focused)) (xs', pruned) |
| 101 |
|
| 102 |
where n@(xs',_) = fromLeafToLeafAfter (regionEnd r) (xs,root) |
| 103 |
(_,(focusedToLeaf,focused)) = fromLeafAfterToFinal p0 n |
| 104 |
p0 = regionStart r |
| 105 |
pruned = pruneNodesBefore p0 focusedToLeaf focused |
| 106 |
|
| 107 |
-- | Return the first element that matches the predicate, or the last |
| 108 |
-- of the list if none matches. |
| 109 |
firstThat :: (a -> Bool) -> NonEmpty a -> a |
| 110 |
firstThat _ (x :| []) = x |
| 111 |
firstThat p (x :| [y]) = if p x then x else y |
| 112 |
firstThat p (x :| y : xs) = if p x then x else firstThat p (y :| xs) |
| 113 |
|
| 114 |
-- | Return the element before first element that violates the |
| 115 |
-- predicate, or the first of the list if that one violates the |
| 116 |
-- predicate. |
| 117 |
lastThat :: (a -> Bool) -> NonEmpty a -> a |
| 118 |
lastThat p (x :| xs) = if p x then work x xs else x |
| 119 |
where work x0 [] = x0 |
| 120 |
work x0 (y:ys) = if p y then work y ys else x0 |
| 121 |
|
| 122 |
-- | Given a path to a node, return a path+node which node that |
| 123 |
-- encompasses the given node + a point before it. |
| 124 |
fromLeafAfterToFinal :: IsTree tree => Point -> Node (tree (Tok a)) |
| 125 |
-> (Path, Node (tree (Tok a))) |
| 126 |
fromLeafAfterToFinal p n = |
| 127 |
-- trace ("reg = " <> showT (fmap (subtreeRegion . snd) nsPth)) $ |
| 128 |
firstThat (\(_,(_,s)) -> getFirstOffset s <= p) ns |
| 129 |
where ns = NE.reverse (nodesOnPath n) |
| 130 |
|
| 131 |
-- | Search the tree in pre-order starting at a given node, until |
| 132 |
-- finding a leaf which is at or after the given point. An effort is |
| 133 |
-- also made to return a leaf as close as possible to @p@. |
| 134 |
-- |
| 135 |
-- TODO: rename to fromLeafToLeafAt |
| 136 |
fromLeafToLeafAfter :: IsTree tree => Point |
| 137 |
-> Node (tree (Tok a)) |
| 138 |
-> Node (tree (Tok a)) |
| 139 |
fromLeafToLeafAfter p (xs, root) = |
| 140 |
trace "fromLeafToLeafAfter:" $ |
| 141 |
trace ("xs = " <> showT xs) $ |
| 142 |
trace ("xsValid = " <> showT xsValid) $ |
| 143 |
trace ("p = " <> showT p) $ |
| 144 |
trace ("leafBeforeP = " <> showT leafBeforeP) $ |
| 145 |
trace ("leaf ~ " <> showT (subtreeRegion leaf)) $ |
| 146 |
trace ("xs' = " <> showT xs') result |
| 147 |
where |
| 148 |
xs' = case candidateLeaves of |
| 149 |
[] -> [] |
| 150 |
c:cs -> fst $ firstOrLastThat (\(_,s) -> getFirstOffset s >= p) (c :| cs) |
| 151 |
candidateLeaves = allLeavesRelative relChild n |
| 152 |
(firstOrLastThat,relChild) = if leafBeforeP then (firstThat,afterChild) |
| 153 |
else (lastThat,beforeChild) |
| 154 |
(xsValid,leaf) = wkDown (xs,root) |
| 155 |
leafBeforeP = getFirstOffset leaf <= p |
| 156 |
n = (xsValid,root) |
| 157 |
result = (xs',root) |
| 158 |
|
| 159 |
allLeavesRelative :: IsTree tree => (Int -> [(Int, tree a)] -> [(Int, tree a)]) |
| 160 |
-> Node (tree a) |
| 161 |
-> [Node (tree a)] |
| 162 |
allLeavesRelative select |
| 163 |
= filter (not . nullSubtree . snd) . allLeavesRelative' select |
| 164 |
. NE.toList . NE.reverse . nodesAndChildIndex |
| 165 |
-- we remove empty subtrees because their region is [0,0]. |
| 166 |
|
| 167 |
-- | Takes a list of (node, index of already inspected child), and |
| 168 |
-- return all leaves in this node after the said child). |
| 169 |
allLeavesRelative' :: IsTree tree => (Int -> [(Int, tree a)] -> [(Int, tree a)]) |
| 170 |
-> [(Node (tree a), Int)] -> [Node (tree a)] |
| 171 |
allLeavesRelative' select l = |
| 172 |
[(xs <> xs', t') | ((xs,t),c) <- l |
| 173 |
, (xs',t') <- allLeavesRelativeChild select c t] |
| 174 |
|
| 175 |
-- | Given a root, return all the nodes encountered along it, their |
| 176 |
-- paths, and the index of the child which comes next. |
| 177 |
nodesAndChildIndex :: IsTree tree => Node (tree a) |
| 178 |
-> NonEmpty (Node (tree a), Int) |
| 179 |
nodesAndChildIndex ([],t) = return (([],t),negate 1) |
| 180 |
nodesAndChildIndex (x:xs, t) = case index x (subtrees t) of |
| 181 |
Just c' -> (([],t), x) |
| 182 |
NE.<| fmap (first $ first (x:)) (nodesAndChildIndex (xs,c')) |
| 183 |
Nothing -> return (([],t),negate 1) |
| 184 |
|
| 185 |
nodesOnPath :: IsTree tree => Node (tree a) -> NonEmpty (Path, Node (tree a)) |
| 186 |
nodesOnPath ([],t) = return ([],([],t)) |
| 187 |
nodesOnPath (x:xs,t) = ([],(x:xs,t)) NE.<| case index x (subtrees t) of |
| 188 |
Nothing -> error "nodesOnPath: non-existent path" |
| 189 |
Just c -> fmap (first (x:)) (nodesOnPath (xs,c)) |
| 190 |
|
| 191 |
|
| 192 |
beforeChild :: Int -> [a] -> [a] |
| 193 |
|
| 194 |
beforeChild (-1) = reverse -- (-1) indicates that all children should be taken. |
| 195 |
beforeChild c = reverse . take (c-1) |
| 196 |
|
| 197 |
afterChild :: Int -> [a] -> [a] |
| 198 |
afterChild c = drop (c+1) |
| 199 |
|
| 200 |
-- | Return all leaves after or before child depending on the relation |
| 201 |
-- which is given. |
| 202 |
allLeavesRelativeChild :: IsTree tree => (Int -> [(Int, tree a)] |
| 203 |
-> [(Int, tree a)]) |
| 204 |
-> Int |
| 205 |
-> tree a -> [Node (tree a)] |
| 206 |
allLeavesRelativeChild select c t |
| 207 |
| null ts = return ([], t) |
| 208 |
| otherwise = [(x:xs,t') | (x,ct) <- select c (zip [0..] ts), |
| 209 |
(xs, t') <- allLeavesIn select ct] |
| 210 |
where ts = subtrees t |
| 211 |
|
| 212 |
|
| 213 |
-- | Return all leaves (with paths) inside a given root. |
| 214 |
allLeavesIn :: (IsTree tree) => (Int -> [(Int, tree a)] -> [(Int, tree a)]) |
| 215 |
-> tree a -> [Node (tree a)] |
| 216 |
allLeavesIn select = allLeavesRelativeChild select (-1) |
| 217 |
|
| 218 |
-- | Return all subtrees in a tree; each element of the return list |
| 219 |
-- contains paths to nodes. (Root is at the start of each path) |
| 220 |
getAllPaths :: IsTree tree => tree t -> [[tree t]] |
| 221 |
getAllPaths t = fmap (<>[t]) ([] : concatMap getAllPaths (subtrees t)) |
| 222 |
|
| 223 |
goDown :: IsTree tree => Int -> tree t -> Maybe (tree t) |
| 224 |
goDown i = index i . subtrees |
| 225 |
|
| 226 |
index :: Int -> [a] -> Maybe a |
| 227 |
index _ [] = Nothing |
| 228 |
index 0 (h:_) = Just h |
| 229 |
index n (_:t) = index (n-1) t |
| 230 |
|
| 231 |
walkDown :: IsTree tree => Node (tree t) -> Maybe (tree t) |
| 232 |
walkDown ([],t) = return t |
| 233 |
walkDown (x:xs,t) = goDown x t >>= curry walkDown xs |
| 234 |
|
| 235 |
wkDown :: IsTree tree => Node (tree a) -> Node (tree a) |
| 236 |
wkDown ([],t) = ([],t) |
| 237 |
wkDown (x:xs,t) = case goDown x t of |
| 238 |
Nothing -> ([],t) |
| 239 |
Just t' -> first (x:) $ wkDown (xs,t') |
| 240 |
|
| 241 |
-- | Search the given list, and return the last tree before the given |
| 242 |
-- point; with path to the root. (Root is at the start of the path) |
| 243 |
getLastPath :: IsTree tree => [tree (Tok t)] -> Point -> Maybe [tree (Tok t)] |
| 244 |
getLastPath roots offset = |
| 245 |
case takeWhile ((< offset) . posnOfs . snd) allSubPathPosn of |
| 246 |
[] -> Nothing |
| 247 |
xs -> Just $ fst $ last xs |
| 248 |
where |
| 249 |
allSubPathPosn = [ (p,posn) | root <- roots |
| 250 |
, p@(t':_) <- getAllPaths root |
| 251 |
, Just tok <- [getFirstElement t'] |
| 252 |
, let posn = tokPosn tok |
| 253 |
] |
| 254 |
|
| 255 |
-- | Return all subtrees in a tree, in preorder. |
| 256 |
getAllSubTrees :: IsTree tree => tree t -> [tree t] |
| 257 |
getAllSubTrees t = t : concatMap getAllSubTrees (subtrees t) |
| 258 |
|
| 259 |
-- | Return the 1st token of a subtree. |
| 260 |
getFirstElement :: Foldable t => t a -> Maybe a |
| 261 |
getFirstElement tree = getFirst $ foldMap (First . Just) tree |
| 262 |
|
| 263 |
nullSubtree :: Foldable t => t a -> Bool |
| 264 |
nullSubtree = null . toList |
| 265 |
|
| 266 |
getFirstTok, getLastTok :: Foldable t => t a -> Maybe a |
| 267 |
|
| 268 |
getFirstTok = getFirstElement |
| 269 |
getLastTok = getLastElement |
| 270 |
|
| 271 |
-- | Return the last token of a subtree. |
| 272 |
getLastElement :: Foldable t => t a -> Maybe a |
| 273 |
getLastElement tree = getLast $ foldMap (Last . Just) tree |
| 274 |
|
| 275 |
getFirstOffset, getLastOffset :: Foldable t => t (Tok t1) -> Point |
| 276 |
getFirstOffset = maybe 0 tokBegin . getFirstTok |
| 277 |
getLastOffset = maybe 0 tokEnd . getLastTok |
| 278 |
|
| 279 |
subtreeRegion :: Foldable t => t (Tok t1) -> Region |
| 280 |
subtreeRegion t = mkRegion (getFirstOffset t) (getLastOffset t) |
| 281 |
|
| 282 |
-- | Given a tree, return (first offset, number of lines). |
| 283 |
getSubtreeSpan :: (Foldable tree) => tree (Tok t) -> (Point, Int) |
| 284 |
getSubtreeSpan tree = (posnOfs firstOff, lastLine - firstLine) |
| 285 |
where bounds@[firstOff, _last] = fmap (tokPosn . assertJust) |
| 286 |
[getFirstElement tree, getLastElement tree] |
| 287 |
[firstLine, lastLine] = fmap posnLine bounds |
| 288 |
assertJust (Just x) = x |
| 289 |
assertJust _ = error "assertJust: Just expected" |
| 290 |
|
| 291 |
------------------------------------- |
| 292 |
-- Should be in Control.Applicative.? |
| 293 |
|
| 294 |
sepBy :: (Alternative f) => f a -> f v -> f [a] |
| 295 |
sepBy p s = sepBy1 p s <|> pure [] |
| 296 |
|
| 297 |
sepBy1 :: (Alternative f) => f a -> f v -> f [a] |
| 298 |
sepBy1 p s = (:) <$> p <*> many (s *> p) |