{-# LANGUAGE CPP #-}
{-# LANGUAGE DerivingStrategies #-}
module Ide.Plugin.RangeMap
( RangeMap(..),
fromList,
fromList',
filterByRange,
) where
import Development.IDE.Graph.Classes (NFData)
#ifdef USE_FINGERTREE
import Data.Bifunctor (first)
import qualified HaskellWorks.Data.IntervalMap.FingerTree as IM
import Language.LSP.Protocol.Types (Position,
Range (Range))
#else
import Language.LSP.Protocol.Types (Range, isSubrangeOf)
#endif
#if USE_FINGERTREE && !MIN_VERSION_base(4,20,0)
import Data.List (foldl')
#endif
#ifdef USE_FINGERTREE
newtype RangeMap a = RangeMap
{ forall a. RangeMap a -> IntervalMap Position a
unRangeMap :: IM.IntervalMap Position a
}
deriving newtype (RangeMap a -> ()
(RangeMap a -> ()) -> NFData (RangeMap a)
forall a. NFData a => RangeMap a -> ()
forall a. (a -> ()) -> NFData a
$crnf :: forall a. NFData a => RangeMap a -> ()
rnf :: RangeMap a -> ()
NFData, NonEmpty (RangeMap a) -> RangeMap a
RangeMap a -> RangeMap a -> RangeMap a
(RangeMap a -> RangeMap a -> RangeMap a)
-> (NonEmpty (RangeMap a) -> RangeMap a)
-> (forall b. Integral b => b -> RangeMap a -> RangeMap a)
-> Semigroup (RangeMap a)
forall b. Integral b => b -> RangeMap a -> RangeMap a
forall a. NonEmpty (RangeMap a) -> RangeMap a
forall a. RangeMap a -> RangeMap a -> RangeMap a
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
forall a b. Integral b => b -> RangeMap a -> RangeMap a
$c<> :: forall a. RangeMap a -> RangeMap a -> RangeMap a
<> :: RangeMap a -> RangeMap a -> RangeMap a
$csconcat :: forall a. NonEmpty (RangeMap a) -> RangeMap a
sconcat :: NonEmpty (RangeMap a) -> RangeMap a
$cstimes :: forall a b. Integral b => b -> RangeMap a -> RangeMap a
stimes :: forall b. Integral b => b -> RangeMap a -> RangeMap a
Semigroup, Semigroup (RangeMap a)
RangeMap a
Semigroup (RangeMap a) =>
RangeMap a
-> (RangeMap a -> RangeMap a -> RangeMap a)
-> ([RangeMap a] -> RangeMap a)
-> Monoid (RangeMap a)
[RangeMap a] -> RangeMap a
RangeMap a -> RangeMap a -> RangeMap a
forall a. Semigroup (RangeMap a)
forall a. RangeMap a
forall a.
Semigroup a =>
a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
forall a. [RangeMap a] -> RangeMap a
forall a. RangeMap a -> RangeMap a -> RangeMap a
$cmempty :: forall a. RangeMap a
mempty :: RangeMap a
$cmappend :: forall a. RangeMap a -> RangeMap a -> RangeMap a
mappend :: RangeMap a -> RangeMap a -> RangeMap a
$cmconcat :: forall a. [RangeMap a] -> RangeMap a
mconcat :: [RangeMap a] -> RangeMap a
Monoid)
deriving stock ((forall a b. (a -> b) -> RangeMap a -> RangeMap b)
-> (forall a b. a -> RangeMap b -> RangeMap a) -> Functor RangeMap
forall a b. a -> RangeMap b -> RangeMap a
forall a b. (a -> b) -> RangeMap a -> RangeMap b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall a b. (a -> b) -> RangeMap a -> RangeMap b
fmap :: forall a b. (a -> b) -> RangeMap a -> RangeMap b
$c<$ :: forall a b. a -> RangeMap b -> RangeMap a
<$ :: forall a b. a -> RangeMap b -> RangeMap a
Functor, (forall m. Monoid m => RangeMap m -> m)
-> (forall m a. Monoid m => (a -> m) -> RangeMap a -> m)
-> (forall m a. Monoid m => (a -> m) -> RangeMap a -> m)
-> (forall a b. (a -> b -> b) -> b -> RangeMap a -> b)
-> (forall a b. (a -> b -> b) -> b -> RangeMap a -> b)
-> (forall b a. (b -> a -> b) -> b -> RangeMap a -> b)
-> (forall b a. (b -> a -> b) -> b -> RangeMap a -> b)
-> (forall a. (a -> a -> a) -> RangeMap a -> a)
-> (forall a. (a -> a -> a) -> RangeMap a -> a)
-> (forall a. RangeMap a -> [a])
-> (forall a. RangeMap a -> Bool)
-> (forall a. RangeMap a -> Int)
-> (forall a. Eq a => a -> RangeMap a -> Bool)
-> (forall a. Ord a => RangeMap a -> a)
-> (forall a. Ord a => RangeMap a -> a)
-> (forall a. Num a => RangeMap a -> a)
-> (forall a. Num a => RangeMap a -> a)
-> Foldable RangeMap
forall a. Eq a => a -> RangeMap a -> Bool
forall a. Num a => RangeMap a -> a
forall a. Ord a => RangeMap a -> a
forall m. Monoid m => RangeMap m -> m
forall a. RangeMap a -> Bool
forall a. RangeMap a -> Int
forall a. RangeMap a -> [a]
forall a. (a -> a -> a) -> RangeMap a -> a
forall m a. Monoid m => (a -> m) -> RangeMap a -> m
forall b a. (b -> a -> b) -> b -> RangeMap a -> b
forall a b. (a -> b -> b) -> b -> RangeMap a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall m. Monoid m => RangeMap m -> m
fold :: forall m. Monoid m => RangeMap m -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> RangeMap a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> RangeMap a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> RangeMap a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> RangeMap a -> m
$cfoldr :: forall a b. (a -> b -> b) -> b -> RangeMap a -> b
foldr :: forall a b. (a -> b -> b) -> b -> RangeMap a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> RangeMap a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> RangeMap a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> RangeMap a -> b
foldl :: forall b a. (b -> a -> b) -> b -> RangeMap a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> RangeMap a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> RangeMap a -> b
$cfoldr1 :: forall a. (a -> a -> a) -> RangeMap a -> a
foldr1 :: forall a. (a -> a -> a) -> RangeMap a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> RangeMap a -> a
foldl1 :: forall a. (a -> a -> a) -> RangeMap a -> a
$ctoList :: forall a. RangeMap a -> [a]
toList :: forall a. RangeMap a -> [a]
$cnull :: forall a. RangeMap a -> Bool
null :: forall a. RangeMap a -> Bool
$clength :: forall a. RangeMap a -> Int
length :: forall a. RangeMap a -> Int
$celem :: forall a. Eq a => a -> RangeMap a -> Bool
elem :: forall a. Eq a => a -> RangeMap a -> Bool
$cmaximum :: forall a. Ord a => RangeMap a -> a
maximum :: forall a. Ord a => RangeMap a -> a
$cminimum :: forall a. Ord a => RangeMap a -> a
minimum :: forall a. Ord a => RangeMap a -> a
$csum :: forall a. Num a => RangeMap a -> a
sum :: forall a. Num a => RangeMap a -> a
$cproduct :: forall a. Num a => RangeMap a -> a
product :: forall a. Num a => RangeMap a -> a
Foldable, Functor RangeMap
Foldable RangeMap
(Functor RangeMap, Foldable RangeMap) =>
(forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> RangeMap a -> f (RangeMap b))
-> (forall (f :: * -> *) a.
Applicative f =>
RangeMap (f a) -> f (RangeMap a))
-> (forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> RangeMap a -> m (RangeMap b))
-> (forall (m :: * -> *) a.
Monad m =>
RangeMap (m a) -> m (RangeMap a))
-> Traversable RangeMap
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => RangeMap (m a) -> m (RangeMap a)
forall (f :: * -> *) a.
Applicative f =>
RangeMap (f a) -> f (RangeMap a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> RangeMap a -> m (RangeMap b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> RangeMap a -> f (RangeMap b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> RangeMap a -> f (RangeMap b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> RangeMap a -> f (RangeMap b)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
RangeMap (f a) -> f (RangeMap a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
RangeMap (f a) -> f (RangeMap a)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> RangeMap a -> m (RangeMap b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> RangeMap a -> m (RangeMap b)
$csequence :: forall (m :: * -> *) a. Monad m => RangeMap (m a) -> m (RangeMap a)
sequence :: forall (m :: * -> *) a. Monad m => RangeMap (m a) -> m (RangeMap a)
Traversable)
#else
newtype RangeMap a = RangeMap
{ unRangeMap :: [(Range, a)] }
deriving newtype (NFData, Semigroup, Monoid)
deriving stock (Functor, Foldable, Traversable)
#endif
fromList :: (a -> Range) -> [a] -> RangeMap a
fromList :: forall a. (a -> Range) -> [a] -> RangeMap a
fromList a -> Range
extractRange = [(Range, a)] -> RangeMap a
forall a. [(Range, a)] -> RangeMap a
fromList' ([(Range, a)] -> RangeMap a)
-> ([a] -> [(Range, a)]) -> [a] -> RangeMap a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (Range, a)) -> [a] -> [(Range, a)]
forall a b. (a -> b) -> [a] -> [b]
map (\a
x -> (a -> Range
extractRange a
x, a
x))
fromList' :: [(Range, a)] -> RangeMap a
#ifdef USE_FINGERTREE
fromList' :: forall a. [(Range, a)] -> RangeMap a
fromList' = IntervalMap Position a -> RangeMap a
forall a. IntervalMap Position a -> RangeMap a
RangeMap (IntervalMap Position a -> RangeMap a)
-> ([(Range, a)] -> IntervalMap Position a)
-> [(Range, a)]
-> RangeMap a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Interval Position, a)] -> IntervalMap Position a
forall v a. Ord v => [(Interval v, a)] -> IntervalMap v a
toIntervalMap ([(Interval Position, a)] -> IntervalMap Position a)
-> ([(Range, a)] -> [(Interval Position, a)])
-> [(Range, a)]
-> IntervalMap Position a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Range, a) -> (Interval Position, a))
-> [(Range, a)] -> [(Interval Position, a)]
forall a b. (a -> b) -> [a] -> [b]
map ((Range -> Interval Position)
-> (Range, a) -> (Interval Position, a)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first Range -> Interval Position
rangeToInterval)
where
toIntervalMap :: Ord v => [(IM.Interval v, a)] -> IM.IntervalMap v a
toIntervalMap :: forall v a. Ord v => [(Interval v, a)] -> IntervalMap v a
toIntervalMap = (IntervalMap v a -> (Interval v, a) -> IntervalMap v a)
-> IntervalMap v a -> [(Interval v, a)] -> IntervalMap v a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\IntervalMap v a
m (Interval v
i, a
v) -> Interval v -> a -> IntervalMap v a -> IntervalMap v a
forall v a.
Ord v =>
Interval v -> a -> IntervalMap v a -> IntervalMap v a
IM.insert Interval v
i a
v IntervalMap v a
m) IntervalMap v a
forall v a. Ord v => IntervalMap v a
IM.empty
#else
fromList' = RangeMap
#endif
filterByRange :: Range -> RangeMap a -> [a]
#ifdef USE_FINGERTREE
filterByRange :: forall a. Range -> RangeMap a -> [a]
filterByRange Range
range = ((Interval Position, a) -> a) -> [(Interval Position, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (Interval Position, a) -> a
forall a b. (a, b) -> b
snd ([(Interval Position, a)] -> [a])
-> (RangeMap a -> [(Interval Position, a)]) -> RangeMap a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Interval Position
-> IntervalMap Position a -> [(Interval Position, a)]
forall v a.
Ord v =>
Interval v -> IntervalMap v a -> [(Interval v, a)]
IM.dominators (Range -> Interval Position
rangeToInterval Range
range) (IntervalMap Position a -> [(Interval Position, a)])
-> (RangeMap a -> IntervalMap Position a)
-> RangeMap a
-> [(Interval Position, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RangeMap a -> IntervalMap Position a
forall a. RangeMap a -> IntervalMap Position a
unRangeMap
#else
filterByRange range = map snd . filter (isSubrangeOf range . fst) . unRangeMap
#endif
#ifdef USE_FINGERTREE
rangeToInterval :: Range -> IM.Interval Position
rangeToInterval :: Range -> Interval Position
rangeToInterval (Range Position
s Position
e) = Position -> Position -> Interval Position
forall v. v -> v -> Interval v
IM.Interval Position
s Position
e
#endif