Diff 0.4.1 → 0.5

raw patch · 4 files changed

+52/−24 lines, 4 filesdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Diff.cabal +7/−5
• src/Data/Algorithm/Diff.hs +21/−9
• src/Data/Algorithm/DiffContext.hs +18/−9
• test/Test.hs +6/−1

@@ -1,25 +1,27 @@ name:                Diff-version:             0.4.1+version:             0.5 synopsis:            O(ND) diff algorithm in haskell. description:         Implementation of the standard diff algorithm, and utilities for pretty printing. category:            Algorithms license:             BSD3 license-file:        LICENSE author:              Sterling Clover-maintainer:          s.clover@gmail.com-Tested-With:         GHC == 7.8.4+maintainer:          David Fox <dsf@seereason.com>+Tested-With:         GHC == 7.10.3, GHC == 8.0.2, GHC == 8.2.2, GHC == 8.4.4, GHC == 8.6.5,+                     GHC == 8.8.4, GHC == 8.10.7, GHC == 9.0.2, GHC == 9.2.8, GHC == 9.4.7,+                     GHC == 9.6.3, GHC == 9.8.1 Build-Type:          Simple Cabal-Version:       >= 1.10  library   default-language: Haskell2010-  build-depends:   base >= 3 && <= 6, array, pretty >= 1.1+  build-depends:   base >= 4.8 && <= 6, array, pretty >= 1.1   hs-source-dirs:  src   exposed-modules:                    Data.Algorithm.Diff,                    Data.Algorithm.DiffOutput                    Data.Algorithm.DiffContext-  ghc-options:     -O2 -Wall -funbox-strict-fields+  ghc-options:     -Wall -funbox-strict-fields  source-repository head   type:      git

@@ -7,10 +7,11 @@ -- Stability   :  experimental -- Portability :  portable ----- This is an implementation of the O(ND) diff algorithm as described in--- \"An O(ND) Difference Algorithm and Its Variations (1986)\"--- <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927>. It is O(mn) in space.--- The algorithm is the same one used by standared Unix diff.+-- This is an implementation of the diff algorithm as described in+-- \"An \( O(ND) \) Difference Algorithm and Its Variations (1986)\"+-- <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927>.+-- For inputs of size \( O(N) \) with the number of differences \( D \)+-- it has \( O(ND) \) time and \( O(D^2) \) space complexity. -----------------------------------------------------------------------------  module Data.Algorithm.Diff@@ -25,10 +26,10 @@     ) where  import Prelude hiding (pi)- import Data.Array (listArray, (!))+import Data.Bifunctor -data DI = F | S | B deriving (Show, Eq)+data DI = F | S deriving (Show, Eq)  -- | A value is either from the 'First' list, the 'Second' or from 'Both'. -- 'Both' contains both the left and right values, in case you are using a form@@ -37,6 +38,16 @@ data PolyDiff a b = First a | Second b | Both a b     deriving (Show, Eq) +instance Functor (PolyDiff a) where+  fmap _ (First a) = First a+  fmap g (Second b) = Second (g b)+  fmap g (Both a b) = Both a (g b)++instance Bifunctor PolyDiff where+  bimap f _ (First a) = First (f a)+  bimap _ g (Second b) = Second (g b)+  bimap f g (Both a b) = Both (f a) (g b)+ -- | This is 'PolyDiff' specialized so both sides are the same type. type Diff a = PolyDiff a a @@ -68,7 +79,7 @@ addsnake :: (Int -> Int -> Bool) -> DL -> DL addsnake cd dl     | cd pi pj = addsnake cd $-                 dl {poi = pi + 1, poj = pj + 1, path=(B : path dl)}+                 dl {poi = pi + 1, poj = pj + 1, path = path dl}     | otherwise   = dl     where pi = poi dl; pj = poj dl @@ -93,9 +104,10 @@ -- is taken as the first argument. getDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff a b] getDiffBy eq a b = markup a b . reverse $ lcs eq a b-    where markup (x:xs)   ys   (F:ds) = First x  : markup xs ys ds+    where markup (x:xs) (y:ys) ds+            | eq x y = Both x y : markup xs ys ds+          markup (x:xs)   ys   (F:ds) = First x  : markup xs ys ds           markup   xs   (y:ys) (S:ds) = Second y : markup xs ys ds-          markup (x:xs) (y:ys) (B:ds) = Both x y : markup xs ys ds           markup _ _ _ = []  getGroupedDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff [a] [b]]

@@ -11,7 +11,8 @@ -- Generates a grouped diff with merged runs, and outputs them in the manner of diff -u ----------------------------------------------------------------------------- module Data.Algorithm.DiffContext-    ( getContextDiff+    ( getContextDiffNew+    , getContextDiff     , getContextDiffOld     , prettyContextDiff     ) where@@ -65,8 +66,13 @@ --      i --      j --     -k-getContextDiff :: Eq a => Int -> [a] -> [a] -> ContextDiff a-getContextDiff context a b =+getContextDiffNew ::+  Eq a+  => Maybe Int -- ^ Number of context elements, Nothing means infinite+  -> [a]+  -> [a]+  -> ContextDiff a+getContextDiffNew context a b =     groupBy' (\a b -> not (isBoth a && isBoth b)) $ doPrefix $ getGroupedDiff a b     where       isBoth (Both {}) = True@@ -75,20 +81,23 @@       doPrefix [] = []       doPrefix [Both _ _] = []       doPrefix (Both xs ys : more) =-          Both (drop (max 0 (length xs - context)) xs)-               (drop (max 0 (length ys - context)) ys) : doSuffix more+          Both (maybe xs (\n -> drop (max 0 (length xs - n)) xs) context)+               (maybe ys (\n -> drop (max 0 (length ys - n)) ys) context) : doSuffix more       -- Prefix finished, do the diff then the following suffix       doPrefix (d : ds) = doSuffix (d : ds)       -- Handle the common text following a diff.       doSuffix [] = []-      doSuffix [Both xs ys] = [Both (take context xs) (take context ys)]+      doSuffix [Both xs ys] = [Both (maybe xs (\n -> take n xs) context) (maybe ys (\n -> take n ys) context)]       doSuffix (Both xs ys : more)-          | length xs <= context * 2 =+          | maybe True (\n -> length xs <= n * 2) context =               Both xs ys : doPrefix more       doSuffix (Both xs ys : more) =-          Both (take context xs) (take context ys)-                   : doPrefix (Both (drop context xs) (drop context ys) : more)+          Both (maybe xs (\n -> take n xs) context) (maybe ys (\n -> take n ys) context)+                   : doPrefix (Both (maybe mempty (\n -> drop n xs) context) (maybe mempty (\n -> drop n ys) context) : more)       doSuffix (d : ds) = d : doSuffix ds++getContextDiff :: Eq a => Int -> [a] -> [a] -> ContextDiff a+getContextDiff context a b = getContextDiffNew (Just context) a b  -- | Do a grouped diff and then split up the chunks into runs that -- contain differences surrounded by N lines of unchanged text.  If

@@ -38,6 +38,11 @@                         testProperty "self generates empty" $ forAll shortLists  prop_ppDiffEqual,                         --testProperty "compare our lists with diff" $ forAll2 shortLists  prop_ppDiffShort,                         testProperty "compare random with diff" prop_ppDiffR,+                        testProperty "compare with diff, issue #5" $ prop_ppDiffR+                          (DiffInput+                            { diLeft = ["1","2","3","4","","5","6","7"]+                            , diRight = ["1","2","3","q","b","u","l","","XXX6",""]+                            }),                         testProperty "test parse" prop_parse,                         testProperty "test context" prop_context_diff                      ]@@ -138,7 +143,7 @@         utilDiff= unsafePerformIO (runDiff (unlines le) (unlines ri))     in  cover 90 (haskDiff == utilDiff) "exact match" $                 classify (haskDiff == utilDiff) "exact match"-                        (div ((length haskDiff)*100) (length utilDiff) < 110) -- less than 10% bigger+                        (div ((length (lines haskDiff))*100) (length (lines utilDiff)) < 110) -- less than 10% bigger     where       runDiff left right =           do leftFile <- writeTemp left