{-# LANGUAGE CPP                #-}
{-# LANGUAGE DerivingStrategies #-}

-- | A map that allows fast \"in-range\" filtering. 'RangeMap' is meant
-- to be constructed once and cached as part of a Shake rule. If
-- not, the map will be rebuilt upon each invocation, yielding slower
-- results compared to the list-based approach!
--
-- Note that 'RangeMap' falls back to the list-based approach if
-- `use-fingertree` flag of `hls-plugin-api` is set to false.
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

-- | A map from code ranges to values.
#ifdef USE_FINGERTREE
newtype RangeMap a = RangeMap
  { forall a. RangeMap a -> IntervalMap Position a
unRangeMap :: IM.IntervalMap Position a
    -- ^ 'IM.Interval' of 'Position' corresponds to a 'Range'
  }
  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

-- | Construct a 'RangeMap' from a 'Range' accessor and a list of values.
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

-- | Filter a 'RangeMap' by a given 'Range'.
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
-- NOTE(ozkutuk): In itself, this conversion is wrong. As Michael put it:
-- "LSP Ranges have exclusive upper bounds, whereas the intervals here are
-- supposed to be closed (i.e. inclusive at both ends)"
-- However, in our use-case this turns out not to be an issue (supported
-- by the accompanying property test).  I think the reason for this is,
-- even if rangeToInterval isn't a correct 1:1 conversion by itself, it
-- is used for both the construction of the RangeMap and during the actual
-- filtering (filterByRange), so it still behaves identical to the list
-- approach.
-- This definition isn't exported from the module, therefore we need not
-- worry about other uses where it potentially makes a difference.
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