scientific 0.3.5.3 → 0.3.6.0

raw patch · 4 files changed

+195/−73 lines, 4 filesdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• changelog +38/−0
• scientific.cabal +1/−1
• src/Data/Scientific.hs +145/−72
• test/test.hs +11/−0

@@ -1,3 +1,41 @@+0.3.6.0+	* Make the methods of the Hashable, Eq and Ord instances safe to+	use when applied to scientific numbers coming from untrusted+	sources. Previously these methods first converted their arguments+	to Rational before applying the operation. This is unsafe because+	converting a Scientific to a Rational could fill up all space and+	crash your program when the Scientific has a huge base10Exponent.++	Do note that the hash computation of the Hashable Scientific+	instance has been changed because of this improvement!++	Thanks to Tom Sydney Kerckhove (@NorfairKing) for pushing me to+	fix this.++	* fromRational :: Rational -> Scientific now throws an error+	instead of diverging when applied to a repeating decimal. This+	does mean it will consume space linear in the number of digits of+	the resulting scientific. This makes "fromRational" and the other+	Fractional methods "recip" and "/" a bit safer to use.++	* To get the old unsafe but more efficient behaviour the following+	function was added: unsafeFromRational :: Rational -> Scientific.++	* Add alternatives for fromRationalRepetend:++	  fromRationalRepetendLimited+	      :: Int -- ^ limit+	      -> Rational+	      -> Either (Scientific, Rational)+		        (Scientific, Maybe Int)++	  and:++	  fromRationalRepetendUnlimited+	      :: Rational -> (Scientific, Maybe Int)++	  Thanks to Ian Jeffries (@seagreen) for the idea.+ 0.3.5.3 	* Dropped upper version bounds of dependencies 	  because it's to much work to maintain.

@@ -1,5 +1,5 @@ name:                scientific-version:             0.3.5.3+version:             0.3.6.0 synopsis:            Numbers represented using scientific notation description:   "Data.Scientific" provides the number type 'Scientific'. Scientific numbers are

@@ -22,6 +22,11 @@ -- aren't truly arbitrary precision. I intend to change the type of the exponent -- to 'Integer' in a future release. --+-- /WARNING:/ Although @Scientific@ has instances for all numeric classes the+-- methods should be used with caution when applied to scientific numbers coming+-- from untrusted sources. See the warnings of the instances belonging to+-- 'Scientific'.+-- -- The main application of 'Scientific' is to be used as the target of parsing -- arbitrary precision numbers coming from an untrusted source. The advantages -- over using 'Rational' for this are that:@@ -41,13 +46,6 @@ -- to @'Integral's@ (like: 'Int') or @'RealFloat's@ (like: 'Double' or 'Float') -- will always be bounded by the target type. ----- /WARNING:/ Although @Scientific@ is an instance of 'Fractional', the methods--- are only partially defined! Specifically 'recip' and '/' will diverge--- (i.e. loop and consume all space) when their outputs have an infinite decimal--- expansion. 'fromRational' will diverge when the input 'Rational' has an--- infinite decimal expansion. Consider using 'fromRationalRepetend' for these--- rationals which will detect the repetition and indicate where it starts.--- -- This module is designed to be imported qualified: -- -- @import Data.Scientific as Scientific@@@ -66,8 +64,14 @@     , isInteger        -- * Conversions+      -- ** Rational+    , unsafeFromRational     , fromRationalRepetend+    , fromRationalRepetendLimited+    , fromRationalRepetendUnlimited     , toRationalRepetend++      -- ** Floating & integer     , floatingOrInteger     , toRealFloat     , toBoundedRealFloat@@ -99,7 +103,6 @@ import           Data.Binary                  (Binary, get, put) import           Data.Char                    (intToDigit, ord) import           Data.Data                    (Data)-import           Data.Function                (on) import           Data.Hashable                (Hashable(..)) import           Data.Int                     (Int8, Int16, Int32, Int64) import qualified Data.Map            as M     (Map, empty, insert, lookup)@@ -174,42 +177,63 @@ instance NFData Scientific where     rnf (Scientific _ _) = () +-- | A hash can be safely calculated from a @Scientific@. No magnitude @10^e@ is+-- calculated so there's no risk of a blowup in space or time when hashing+-- scientific numbers coming from untrusted sources. instance Hashable Scientific where-    hashWithSalt salt = hashWithSalt salt . toRational+    hashWithSalt salt s = salt `hashWithSalt` c `hashWithSalt` e+      where+        Scientific c e = normalize s +-- | Note that in the future I intend to change the type of the 'base10Exponent'+-- from @Int@ to @Integer@. To be forward compatible the @Binary@ instance+-- already encodes the exponent as 'Integer'. instance Binary Scientific where-    put (Scientific c e) = do-      put c-      -- In the future I intend to change the type of the base10Exponent e from-      -- Int to Integer. To support backward compatibility I already convert e-      -- to Integer here:-      put $ toInteger e-+    put (Scientific c e) = put c *> put (toInteger e)     get = Scientific <$> get <*> (fromInteger <$> get) +-- | Scientific numbers can be safely compared for equality. No magnitude @10^e@+-- is calculated so there's no risk of a blowup in space or time when comparing+-- scientific numbers coming from untrusted sources. instance Eq Scientific where-    (==) = (==) `on` toRational-    {-# INLINABLE (==) #-}--    (/=) = (/=) `on` toRational-    {-# INLINABLE (/=) #-}+    s1 == s2 = c1 == c2 && e1 == e2+      where+        Scientific c1 e1 = normalize s1+        Scientific c2 e2 = normalize s2 +-- | Scientific numbers can be safely compared for ordering. No magnitude @10^e@+-- is calculated so there's no risk of a blowup in space or time when comparing+-- scientific numbers coming from untrusted sources. instance Ord Scientific where-    (<) = (<) `on` toRational-    {-# INLINABLE (<) #-}--    (<=) = (<=) `on` toRational-    {-# INLINABLE (<=) #-}+    compare s1 s2+        | c1 == c2 && e1 == e2 = EQ+        | c1 < 0    = if c2 < 0 then cmp (-c2) e2 (-c1) e1 else LT+        | c1 > 0    = if c2 > 0 then cmp   c1  e1   c2  e2 else GT+        | otherwise = if c2 > 0 then LT else GT+      where+        Scientific c1 e1 = normalize s1+        Scientific c2 e2 = normalize s2 -    (>) = (>) `on` toRational-    {-# INLINABLE (>) #-}+        cmp cx ex cy ey+            | log10sx < log10sy = LT+            | log10sx > log10sy = GT+            | d < 0     = if cx <= (cy `quotInteger` magnitude (-d)) then LT else GT+            | d > 0     = if cy >  (cx `quotInteger` magnitude   d)  then LT else GT+            | otherwise = if cx < cy                                 then LT else GT+          where+            log10sx = log10cx + ex+            log10sy = log10cy + ey -    (>=) = (>=) `on` toRational-    {-# INLINABLE (>=) #-}+            log10cx = integerLog10' cx+            log10cy = integerLog10' cy -    compare = compare `on` toRational-    {-# INLINABLE compare #-}+            d = log10cx - log10cy +-- | /WARNING:/ '+' and '-' compute the 'Integer' magnitude: @10^e@ where @e@ is+-- the difference between the @'base10Exponent's@ of the arguments. If these+-- methods are applied to arguments which have huge exponents this could fill up+-- all space and crash your program! So don't apply these methods to scientific+-- numbers coming from untrusted sources. The other methods can be used safely. instance Num Scientific where     Scientific c1 e1 + Scientific c2 e2        | e1 < e2   = Scientific (c1   + c2*l) e1@@ -264,12 +288,12 @@   "realToFrac_toRealFloat_Float"    realToFrac = toRealFloat :: Scientific -> Float #-} --- | /WARNING:/ 'recip' and '/' will diverge (i.e. loop and consume all space)--- when their outputs are <https://en.wikipedia.org/wiki/Repeating_decimal repeating decimals>.+-- | /WARNING:/ 'recip' and '/' will throw an error when their outputs are+-- <https://en.wikipedia.org/wiki/Repeating_decimal repeating decimals>. ----- 'fromRational' will diverge when the input 'Rational' is a repeating decimal.--- Consider using 'fromRationalRepetend' for these rationals which will detect--- the repetition and indicate where it starts.+-- 'fromRational' will throw an error when the input 'Rational' is a repeating+-- decimal.  Consider using 'fromRationalRepetend' for these rationals which+-- will detect the repetition and indicate where it starts. instance Fractional Scientific where     recip = fromRational . recip . toRational     {-# INLINABLE recip #-}@@ -277,23 +301,45 @@     x / y = fromRational $ toRational x / toRational y     {-# INLINABLE (/) #-} -    fromRational rational-        | d == 0    = throw DivideByZero-        | otherwise = positivize (longDiv 0 0) (numerator rational)+    fromRational rational =+        case mbRepetendIx of+          Nothing -> s+          Just _ix -> error $+            "fromRational has been applied to a repeating decimal " +++            "which can't be represented as a Scientific! " +++            "It's better to avoid performing fractional operations on Scientifics " +++            "and convert them to other fractional types like Double as early as possible."       where-        -- Divide the numerator by the denominator using long division.-        longDiv :: Integer -> Int -> (Integer -> Scientific)-        longDiv !c !e  0 = Scientific c e-        longDiv !c !e !n-                          -- TODO: Use a logarithm here!-            | n < d     = longDiv (c * 10) (e - 1) (n * 10)-            | otherwise = case n `quotRemInteger` d of-                            (#q, r#) -> longDiv (c + q) e r+        (s, mbRepetendIx) = fromRationalRepetendUnlimited rational -        d = denominator rational+-- | Although 'fromRational' is unsafe because it will throw errors on+-- <https://en.wikipedia.org/wiki/Repeating_decimal repeating decimals>,+-- @unsafeFromRational@ is even more unsafe because it will diverge instead (i.e+-- loop and consume all space). Though it will be more efficient because it+-- doesn't need to consume space linear in the number of digits in the resulting+-- scientific to detect the repetition.+--+-- Consider using 'fromRationalRepetend' for these rationals which will detect+-- the repetition and indicate where it starts.+unsafeFromRational :: Rational -> Scientific+unsafeFromRational rational+    | d == 0    = throw DivideByZero+    | otherwise = positivize (longDiv 0 0) (numerator rational)+  where+    -- Divide the numerator by the denominator using long division.+    longDiv :: Integer -> Int -> (Integer -> Scientific)+    longDiv !c !e  0 = Scientific c e+    longDiv !c !e !n+                      -- TODO: Use a logarithm here!+        | n < d     = longDiv (c * 10) (e - 1) (n * 10)+        | otherwise = case n `quotRemInteger` d of+                        (#q, r#) -> longDiv (c + q) e r --- | Like 'fromRational', this function converts a `Rational` to a `Scientific`--- but instead of diverging (i.e loop and consume all space) on+    d = denominator rational++-- | Like 'fromRational' and 'unsafeFromRational', this function converts a+-- `Rational` to a `Scientific` but instead of failing or diverging (i.e loop+-- and consume all space) on -- <https://en.wikipedia.org/wiki/Repeating_decimal repeating decimals> -- it detects the repeating part, the /repetend/, and returns where it starts. --@@ -335,7 +381,18 @@     -> Rational     -> Either (Scientific, Rational)               (Scientific, Maybe Int)-fromRationalRepetend mbLimit rational+fromRationalRepetend mbLimit rational =+    case mbLimit of+      Nothing -> Right $ fromRationalRepetendUnlimited rational+      Just l  -> fromRationalRepetendLimited l rational++-- | Like 'fromRationalRepetend' but always accepts a limit.+fromRationalRepetendLimited+    :: Int -- ^ limit+    -> Rational+    -> Either (Scientific, Rational)+              (Scientific, Maybe Int)+fromRationalRepetendLimited l rational         | d == 0    = throw DivideByZero         | num < 0   = case longDiv (-num) of                         Left  (s, r)  -> Left  (-s, -r)@@ -345,11 +402,38 @@         num = numerator rational          longDiv :: Integer -> Either (Scientific, Rational) (Scientific, Maybe Int)-        longDiv n = case mbLimit of-                      Nothing -> Right $ longDivNoLimit 0 0 M.empty n-                      Just l  -> longDivWithLimit (-l) n+        longDiv = longDivWithLimit 0 0 M.empty -        -- Divide the numerator by the denominator using long division.+        longDivWithLimit+            :: Integer+            -> Int+            -> M.Map Integer Int+            -> (Integer -> Either (Scientific, Rational)+                                  (Scientific, Maybe Int))+        longDivWithLimit !c !e _ns 0 = Right (Scientific c e, Nothing)+        longDivWithLimit !c !e  ns !n+            | Just e' <- M.lookup n ns = Right (Scientific c e, Just (-e'))+            | e <= (-l) = Left (Scientific c e, n % (d * magnitude (-e)))+            | n < d = let !ns' = M.insert n e ns+                      in longDivWithLimit (c * 10) (e - 1) ns' (n * 10)+            | otherwise = case n `quotRemInteger` d of+                            (#q, r#) -> longDivWithLimit (c + q) e ns r++        d = denominator rational++-- | Like 'fromRationalRepetend' but doesn't accept a limit.+fromRationalRepetendUnlimited :: Rational -> (Scientific, Maybe Int)+fromRationalRepetendUnlimited rational+        | d == 0    = throw DivideByZero+        | num < 0   = case longDiv (-num) of+                        (s, mb) -> (-s, mb)+        | otherwise = longDiv num+      where+        num = numerator rational++        longDiv :: Integer -> (Scientific, Maybe Int)+        longDiv = longDivNoLimit 0 0 M.empty+         longDivNoLimit :: Integer                        -> Int                        -> M.Map Integer Int@@ -362,22 +446,6 @@             | otherwise = case n `quotRemInteger` d of                             (#q, r#) -> longDivNoLimit (c + q) e ns r -        longDivWithLimit :: Int -> Integer -> Either (Scientific, Rational) (Scientific, Maybe Int)-        longDivWithLimit l = go 0 0 M.empty-            where-              go :: Integer-                 -> Int-                 -> M.Map Integer Int-                 -> (Integer -> Either (Scientific, Rational) (Scientific, Maybe Int))-              go !c !e _ns 0 = Right (Scientific c e, Nothing)-              go !c !e  ns !n-                  | Just e' <- M.lookup n ns = Right (Scientific c e, Just (-e'))-                  | e <= l    = Left (Scientific c e, n % (d * magnitude (-e)))-                  | n < d     = let !ns' = M.insert n e ns-                                in go (c * 10) (e - 1) ns' (n * 10)-                  | otherwise = case n `quotRemInteger` d of-                                  (#q, r#) -> go (c + q) e ns r-         d = denominator rational  -- |@@ -443,6 +511,10 @@      nines = m - 1 +-- | /WARNING:/ the methods of the @RealFrac@ instance need to compute the+-- magnitude @10^e@. If applied to a huge exponent this could take a long+-- time. Even worse, when the destination type is unbounded (i.e. 'Integer') it+-- could fill up all space and crash your program! instance RealFrac Scientific where     -- | The function 'properFraction' takes a Scientific number @s@     -- and returns a pair @(n,f)@ such that @s = n+f@, and:@@ -885,6 +957,7 @@ -- Pretty Printing ---------------------------------------------------------------------- +-- | See 'formatScientific' if you need more control over the rendering. instance Show Scientific where     show s | coefficient s < 0 = '-':showPositive (-s)            | otherwise         =     showPositive   s

@@ -97,6 +97,17 @@     --     show d     ] +  , testGroup "Eq"+    [ testProperty "==" $ \(s1 :: Scientific) (s2 :: Scientific) ->+        (s1 == s2) == (toRational s1 == toRational s2)+    , testProperty "s == s" $ \(s :: Scientific) -> s == s+    ]++  , testGroup "Ord"+    [ testProperty "compare" $ \(s1 :: Scientific) (s2 :: Scientific) ->+        compare s1 s2 == compare (toRational s1) (toRational s2)+    ]+   , testGroup "Num"     [ testGroup "Equal to Rational"       [ testProperty "fromInteger" $ \i -> fromInteger i === fromRational (fromInteger i)