{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DeriveFoldable             #-}
{-# LANGUAGE DeriveFunctor              #-}
{-# LANGUAGE DeriveTraversable          #-}
{-# LANGUAGE DerivingStrategies         #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}

-- | 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           Data.Bifunctor                           (first)
import           Data.Foldable                            (foldl')
import           Development.IDE.Graph.Classes            (NFData)
import           Language.LSP.Protocol.Types              (Position,
                                                           Range (Range),
                                                           isSubrangeOf)
#ifdef USE_FINGERTREE
import qualified HaskellWorks.Data.IntervalMap.FingerTree as IM
#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 -> ()
forall a. NFData a => RangeMap a -> ()
forall a. (a -> ()) -> NFData a
rnf :: RangeMap a -> ()
$crnf :: forall a. NFData a => RangeMap a -> ()
NFData, NonEmpty (RangeMap a) -> RangeMap a
RangeMap a -> RangeMap a -> 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
stimes :: forall b. Integral b => b -> RangeMap a -> RangeMap a
$cstimes :: forall a b. Integral b => b -> RangeMap a -> RangeMap a
sconcat :: NonEmpty (RangeMap a) -> RangeMap a
$csconcat :: forall a. NonEmpty (RangeMap a) -> RangeMap a
<> :: RangeMap a -> RangeMap a -> RangeMap a
$c<> :: forall a. RangeMap a -> RangeMap a -> RangeMap a
Semigroup, 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
mconcat :: [RangeMap a] -> RangeMap a
$cmconcat :: forall a. [RangeMap a] -> RangeMap a
mappend :: RangeMap a -> RangeMap a -> RangeMap a
$cmappend :: forall a. RangeMap a -> RangeMap a -> RangeMap a
mempty :: RangeMap a
$cmempty :: forall a. RangeMap a
Monoid)
  deriving stock (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
<$ :: forall a b. a -> RangeMap b -> RangeMap a
$c<$ :: forall a b. a -> RangeMap b -> RangeMap a
fmap :: forall a b. (a -> b) -> RangeMap a -> RangeMap b
$cfmap :: forall a b. (a -> b) -> RangeMap a -> RangeMap b
Functor, 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
product :: forall a. Num a => RangeMap a -> a
$cproduct :: forall a. Num a => RangeMap a -> a
sum :: forall a. Num a => RangeMap a -> a
$csum :: forall a. Num a => RangeMap a -> a
minimum :: forall a. Ord a => RangeMap a -> a
$cminimum :: forall a. Ord a => RangeMap a -> a
maximum :: forall a. Ord a => RangeMap a -> a
$cmaximum :: forall a. Ord a => RangeMap a -> a
elem :: forall a. Eq a => a -> RangeMap a -> Bool
$celem :: forall a. Eq a => a -> RangeMap a -> Bool
length :: forall a. RangeMap a -> Int
$clength :: forall a. RangeMap a -> Int
null :: forall a. RangeMap a -> Bool
$cnull :: forall a. RangeMap a -> Bool
toList :: forall a. RangeMap a -> [a]
$ctoList :: forall a. RangeMap a -> [a]
foldl1 :: forall a. (a -> a -> a) -> RangeMap a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> RangeMap a -> a
foldr1 :: forall a. (a -> a -> a) -> RangeMap a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> RangeMap a -> a
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
$cfoldl :: forall b a. (b -> a -> 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
$cfoldr :: forall a b. (a -> b -> b) -> b -> RangeMap a -> b
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
$cfoldMap :: forall m a. Monoid m => (a -> m) -> RangeMap a -> m
fold :: forall m. Monoid m => RangeMap m -> m
$cfold :: forall m. Monoid m => RangeMap m -> m
Foldable, Functor RangeMap
Foldable 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)
sequence :: forall (m :: * -> *) a. Monad m => RangeMap (m a) -> m (RangeMap a)
$csequence :: forall (m :: * -> *) a. Monad m => RangeMap (m a) -> m (RangeMap a)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> RangeMap a -> m (RangeMap b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> RangeMap a -> m (RangeMap b)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
RangeMap (f a) -> f (RangeMap a)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
RangeMap (f a) -> f (RangeMap a)
traverse :: 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)
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 = forall a. [(Range, a)] -> RangeMap a
fromList' forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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' = forall a. IntervalMap Position a -> RangeMap a
RangeMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall v a. Ord v => [(Interval v, a)] -> IntervalMap v a
toIntervalMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b) -> [a] -> [b]
map (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 = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\IntervalMap v a
m (Interval v
i, a
v) -> 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) 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 = forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall v a.
Ord v =>
Interval v -> IntervalMap v a -> [(Interval v, a)]
IM.dominators (Range -> Interval Position
rangeToInterval Range
range) forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = forall v. v -> v -> Interval v
IM.Interval Position
s Position
e
#endif