Debian Codegraph @

src/Yi/Syntax/Tree.hs

raw
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)