tree-diff 0.0.2.1 → 0.1
raw patch · 11 files changed
+592/−149 lines, 11 filesdep +bytestring-builderdep +generic-derivingdep +ghc-primdep −MemoTriedep −generics-sopdep ~QuickCheckdep ~aesondep ~ansi-terminal
Dependencies added: bytestring-builder, generic-deriving, ghc-prim
Dependencies removed: MemoTrie, generics-sop
Dependency ranges changed: QuickCheck, aeson, ansi-terminal, ansi-wl-pprint, base, base-compat, bytestring, containers, hashable, nats, parsec, parsers, pretty, scientific, semigroups, tagged, tasty, tasty-golden, tasty-quickcheck, text, time, transformers, trifecta, unordered-containers, uuid-types, vector, void
Files
- ChangeLog.md +7/−1
- LICENSE +333/−24
- fixtures/MyInt1.expr +1/−0
- fixtures/MyInt2.expr +1/−0
- fixtures/MyInt3.expr +1/−0
- fixtures/Positional.expr +1/−0
- src/Data/TreeDiff/Class.hs +97/−38
- src/Data/TreeDiff/List.hs +13/−3
- src/Data/TreeDiff/Pretty.hs +1/−1
- tests/Tests.hs +43/−5
- tree-diff.cabal +94/−77
ChangeLog.md view
@@ -1,4 +1,10 @@-# Revision history for tree-diff+## 0.1++- Support GHC-7.4 ... 8.8 (use allow-newer for GHC-8.8-alpha).+- Use raw GHC.Generics (drop `generics-sop` dependency)+- Use own memoising (Vector lookup, drop `MemoTrie` dependency)+- Singleton data-types (both `data` and `newtype`s) are printed in App form (i.e. no-record).+- Change license to GPL-2.0-or-later ## 0.0.2.1
LICENSE view
@@ -1,30 +1,339 @@-Copyright (c) 2017, Oleg Grenrus+ GNU GENERAL PUBLIC LICENSE+ Version 2, June 1991 -All rights reserved.+ Copyright (C) 1989, 1991 Free Software Foundation, Inc.,+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA+ Everyone is permitted to copy and distribute verbatim copies+ of this license document, but changing it is not allowed. -Redistribution and use in source and binary forms, with or without-modification, are permitted provided that the following conditions are met:+ Preamble - * Redistributions of source code must retain the above copyright- notice, this list of conditions and the following disclaimer.+ The licenses for most software are designed to take away your+freedom to share and change it. By contrast, the GNU General Public+License is intended to guarantee your freedom to share and change free+software--to make sure the software is free for all its users. This+General Public License applies to most of the Free Software+Foundation's software and to any other program whose authors commit to+using it. (Some other Free Software Foundation software is covered by+the GNU Lesser General Public License instead.) You can apply it to+your programs, too. - * Redistributions in binary form must reproduce the above- copyright notice, this list of conditions and the following- disclaimer in the documentation and/or other materials provided- with the distribution.+ When we speak of free software, we are referring to freedom, not+price. Our General Public Licenses are designed to make sure that you+have the freedom to distribute copies of free software (and charge for+this service if you wish), that you receive source code or can get it+if you want it, that you can change the software or use pieces of it+in new free programs; and that you know you can do these things. - * Neither the name of Oleg Grenrus nor the names of other- contributors may be used to endorse or promote products derived- from this software without specific prior written permission.+ To protect your rights, we need to make restrictions that forbid+anyone to deny you these rights or to ask you to surrender the rights.+These restrictions translate to certain responsibilities for you if you+distribute copies of the software, or if you modify it. -THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS-"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT-LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR-A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT-OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,-SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT-LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,-DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY-THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT-(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE-OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.+ For example, if you distribute copies of such a program, whether+gratis or for a fee, you must give the recipients all the rights that+you have. You must make sure that they, too, receive or can get the+source code. And you must show them these terms so they know their+rights.++ We protect your rights with two steps: (1) copyright the software, and+(2) offer you this license which gives you legal permission to copy,+distribute and/or modify the software.++ Also, for each author's protection and ours, we want to make certain+that everyone understands that there is no warranty for this free+software. If the software is modified by someone else and passed on, we+want its recipients to know that what they have is not the original, so+that any problems introduced by others will not reflect on the original+authors' reputations.++ Finally, any free program is threatened constantly by software+patents. We wish to avoid the danger that redistributors of a free+program will individually obtain patent licenses, in effect making the+program proprietary. To prevent this, we have made it clear that any+patent must be licensed for everyone's free use or not licensed at all.++ The precise terms and conditions for copying, distribution and+modification follow.++ GNU GENERAL PUBLIC LICENSE+ TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION++ 0. This License applies to any program or other work which contains+a notice placed by the copyright holder saying it may be distributed+under the terms of this General Public License. The "Program", below,+refers to any such program or work, and a "work based on the Program"+means either the Program or any derivative work under copyright law:+that is to say, a work containing the Program or a portion of it,+either verbatim or with modifications and/or translated into another+language. (Hereinafter, translation is included without limitation in+the term "modification".) Each licensee is addressed as "you".++Activities other than copying, distribution and modification are not+covered by this License; they are outside its scope. The act of+running the Program is not restricted, and the output from the Program+is covered only if its contents constitute a work based on the+Program (independent of having been made by running the Program).+Whether that is true depends on what the Program does.++ 1. You may copy and distribute verbatim copies of the Program's+source code as you receive it, in any medium, provided that you+conspicuously and appropriately publish on each copy an appropriate+copyright notice and disclaimer of warranty; keep intact all the+notices that refer to this License and to the absence of any warranty;+and give any other recipients of the Program a copy of this License+along with the Program.++You may charge a fee for the physical act of transferring a copy, and+you may at your option offer warranty protection in exchange for a fee.++ 2. You may modify your copy or copies of the Program or any portion+of it, thus forming a work based on the Program, and copy and+distribute such modifications or work under the terms of Section 1+above, provided that you also meet all of these conditions:++ a) You must cause the modified files to carry prominent notices+ stating that you changed the files and the date of any change.++ b) You must cause any work that you distribute or publish, that in+ whole or in part contains or is derived from the Program or any+ part thereof, to be licensed as a whole at no charge to all third+ parties under the terms of this License.++ c) If the modified program normally reads commands interactively+ when run, you must cause it, when started running for such+ interactive use in the most ordinary way, to print or display an+ announcement including an appropriate copyright notice and a+ notice that there is no warranty (or else, saying that you provide+ a warranty) and that users may redistribute the program under+ these conditions, and telling the user how to view a copy of this+ License. (Exception: if the Program itself is interactive but+ does not normally print such an announcement, your work based on+ the Program is not required to print an announcement.)++These requirements apply to the modified work as a whole. If+identifiable sections of that work are not derived from the Program,+and can be reasonably considered independent and separate works in+themselves, then this License, and its terms, do not apply to those+sections when you distribute them as separate works. But when you+distribute the same sections as part of a whole which is a work based+on the Program, the distribution of the whole must be on the terms of+this License, whose permissions for other licensees extend to the+entire whole, and thus to each and every part regardless of who wrote it.++Thus, it is not the intent of this section to claim rights or contest+your rights to work written entirely by you; rather, the intent is to+exercise the right to control the distribution of derivative or+collective works based on the Program.++In addition, mere aggregation of another work not based on the Program+with the Program (or with a work based on the Program) on a volume of+a storage or distribution medium does not bring the other work under+the scope of this License.++ 3. You may copy and distribute the Program (or a work based on it,+under Section 2) in object code or executable form under the terms of+Sections 1 and 2 above provided that you also do one of the following:++ a) Accompany it with the complete corresponding machine-readable+ source code, which must be distributed under the terms of Sections+ 1 and 2 above on a medium customarily used for software interchange; or,++ b) Accompany it with a written offer, valid for at least three+ years, to give any third party, for a charge no more than your+ cost of physically performing source distribution, a complete+ machine-readable copy of the corresponding source code, to be+ distributed under the terms of Sections 1 and 2 above on a medium+ customarily used for software interchange; or,++ c) Accompany it with the information you received as to the offer+ to distribute corresponding source code. (This alternative is+ allowed only for noncommercial distribution and only if you+ received the program in object code or executable form with such+ an offer, in accord with Subsection b above.)++The source code for a work means the preferred form of the work for+making modifications to it. For an executable work, complete source+code means all the source code for all modules it contains, plus any+associated interface definition files, plus the scripts used to+control compilation and installation of the executable. However, as a+special exception, the source code distributed need not include+anything that is normally distributed (in either source or binary+form) with the major components (compiler, kernel, and so on) of the+operating system on which the executable runs, unless that component+itself accompanies the executable.++If distribution of executable or object code is made by offering+access to copy from a designated place, then offering equivalent+access to copy the source code from the same place counts as+distribution of the source code, even though third parties are not+compelled to copy the source along with the object code.++ 4. You may not copy, modify, sublicense, or distribute the Program+except as expressly provided under this License. Any attempt+otherwise to copy, modify, sublicense or distribute the Program is+void, and will automatically terminate your rights under this License.+However, parties who have received copies, or rights, from you under+this License will not have their licenses terminated so long as such+parties remain in full compliance.++ 5. You are not required to accept this License, since you have not+signed it. However, nothing else grants you permission to modify or+distribute the Program or its derivative works. These actions are+prohibited by law if you do not accept this License. Therefore, by+modifying or distributing the Program (or any work based on the+Program), you indicate your acceptance of this License to do so, and+all its terms and conditions for copying, distributing or modifying+the Program or works based on it.++ 6. Each time you redistribute the Program (or any work based on the+Program), the recipient automatically receives a license from the+original licensor to copy, distribute or modify the Program subject to+these terms and conditions. You may not impose any further+restrictions on the recipients' exercise of the rights granted herein.+You are not responsible for enforcing compliance by third parties to+this License.++ 7. If, as a consequence of a court judgment or allegation of patent+infringement or for any other reason (not limited to patent issues),+conditions are imposed on you (whether by court order, agreement or+otherwise) that contradict the conditions of this License, they do not+excuse you from the conditions of this License. If you cannot+distribute so as to satisfy simultaneously your obligations under this+License and any other pertinent obligations, then as a consequence you+may not distribute the Program at all. For example, if a patent+license would not permit royalty-free redistribution of the Program by+all those who receive copies directly or indirectly through you, then+the only way you could satisfy both it and this License would be to+refrain entirely from distribution of the Program.++If any portion of this section is held invalid or unenforceable under+any particular circumstance, the balance of the section is intended to+apply and the section as a whole is intended to apply in other+circumstances.++It is not the purpose of this section to induce you to infringe any+patents or other property right claims or to contest validity of any+such claims; this section has the sole purpose of protecting the+integrity of the free software distribution system, which is+implemented by public license practices. Many people have made+generous contributions to the wide range of software distributed+through that system in reliance on consistent application of that+system; it is up to the author/donor to decide if he or she is willing+to distribute software through any other system and a licensee cannot+impose that choice.++This section is intended to make thoroughly clear what is believed to+be a consequence of the rest of this License.++ 8. If the distribution and/or use of the Program is restricted in+certain countries either by patents or by copyrighted interfaces, the+original copyright holder who places the Program under this License+may add an explicit geographical distribution limitation excluding+those countries, so that distribution is permitted only in or among+countries not thus excluded. In such case, this License incorporates+the limitation as if written in the body of this License.++ 9. The Free Software Foundation may publish revised and/or new versions+of the General Public License from time to time. Such new versions will+be similar in spirit to the present version, but may differ in detail to+address new problems or concerns.++Each version is given a distinguishing version number. If the Program+specifies a version number of this License which applies to it and "any+later version", you have the option of following the terms and conditions+either of that version or of any later version published by the Free+Software Foundation. If the Program does not specify a version number of+this License, you may choose any version ever published by the Free Software+Foundation.++ 10. If you wish to incorporate parts of the Program into other free+programs whose distribution conditions are different, write to the author+to ask for permission. For software which is copyrighted by the Free+Software Foundation, write to the Free Software Foundation; we sometimes+make exceptions for this. Our decision will be guided by the two goals+of preserving the free status of all derivatives of our free software and+of promoting the sharing and reuse of software generally.++ NO WARRANTY++ 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY+FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN+OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES+PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED+OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS+TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE+PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,+REPAIR OR CORRECTION.++ 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING+WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR+REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,+INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING+OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED+TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY+YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER+PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE+POSSIBILITY OF SUCH DAMAGES.++ END OF TERMS AND CONDITIONS++ How to Apply These Terms to Your New Programs++ If you develop a new program, and you want it to be of the greatest+possible use to the public, the best way to achieve this is to make it+free software which everyone can redistribute and change under these terms.++ To do so, attach the following notices to the program. It is safest+to attach them to the start of each source file to most effectively+convey the exclusion of warranty; and each file should have at least+the "copyright" line and a pointer to where the full notice is found.++ <one line to give the program's name and a brief idea of what it does.>+ Copyright (C) <year> <name of author>++ This program is free software; you can redistribute it and/or modify+ it under the terms of the GNU General Public License as published by+ the Free Software Foundation; either version 2 of the License, or+ (at your option) any later version.++ This program is distributed in the hope that it will be useful,+ but WITHOUT ANY WARRANTY; without even the implied warranty of+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the+ GNU General Public License for more details.++ You should have received a copy of the GNU General Public License along+ with this program; if not, write to the Free Software Foundation, Inc.,+ 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.++Also add information on how to contact you by electronic and paper mail.++If the program is interactive, make it output a short notice like this+when it starts in an interactive mode:++ Gnomovision version 69, Copyright (C) year name of author+ Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.+ This is free software, and you are welcome to redistribute it+ under certain conditions; type `show c' for details.++The hypothetical commands `show w' and `show c' should show the appropriate+parts of the General Public License. Of course, the commands you use may+be called something other than `show w' and `show c'; they could even be+mouse-clicks or menu items--whatever suits your program.++You should also get your employer (if you work as a programmer) or your+school, if any, to sign a "copyright disclaimer" for the program, if+necessary. Here is a sample; alter the names:++ Yoyodyne, Inc., hereby disclaims all copyright interest in the program+ `Gnomovision' (which makes passes at compilers) written by James Hacker.++ <signature of Ty Coon>, 1 April 1989+ Ty Coon, President of Vice++This General Public License does not permit incorporating your program into+proprietary programs. If your program is a subroutine library, you may+consider it more useful to permit linking proprietary applications with the+library. If this is what you want to do, use the GNU Lesser General+Public License instead of this License.
+ fixtures/MyInt1.expr view
@@ -0,0 +1,1 @@+MyInt1 42
+ fixtures/MyInt2.expr view
@@ -0,0 +1,1 @@+MyInt2 42
+ fixtures/MyInt3.expr view
@@ -0,0 +1,1 @@+MyInt3 42
+ fixtures/Positional.expr view
@@ -0,0 +1,1 @@+Positional 12 True 'z'
src/Data/TreeDiff/Class.hs view
@@ -5,29 +5,32 @@ {-# LANGUAGE GADTs #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE TypeOperators #-}+#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 708+{-# LANGUAGE EmptyCase #-}+#endif -- | A 'ToExpr' class. module Data.TreeDiff.Class ( ediff, ediff', ToExpr (..), defaultExprViaShow,- -- * SOP- sopToExpr,+ -- * Generics+ genericToExpr,+ GToExpr, ) where -import Data.Foldable (toList)-import Data.Proxy (Proxy (..))-import Data.TreeDiff.Expr-import Data.List.Compat (uncons)-import Generics.SOP- (All, All2, ConstructorInfo (..), DatatypeInfo (..), FieldInfo (..),- I (..), K (..), NP (..), SOP (..), constructorInfo, hcliftA2, hcmap,- hcollapse, mapIK)-import Generics.SOP.GGP (GCode, GDatatypeInfo, GFrom, gdatatypeInfo, gfrom)-import GHC.Generics (Generic)+import Data.Foldable (toList)+import Data.List.Compat (uncons)+import Data.Proxy (Proxy (..))+import GHC.Generics+ ((:*:) (..), (:+:) (..), Constructor (..), Generic (..), K1 (..), M1 (..),+ Selector (..), U1 (..), V1) import qualified Data.Map as Map +import Data.TreeDiff.Expr+ -- Instances import Control.Applicative (Const (..), ZipList (..)) import Data.Fixed (Fixed, HasResolution)@@ -38,6 +41,10 @@ import Data.Word import Numeric.Natural (Natural) +#ifdef MIN_VERSION_generic_deriving+import Generics.Deriving.Instances ()+#endif+ import qualified Data.Monoid as Mon import qualified Data.Ratio as Ratio import qualified Data.Semigroup as Semi@@ -59,6 +66,7 @@ -- bytestring import qualified Data.ByteString as BS import qualified Data.ByteString.Lazy as LBS+ import qualified Data.ByteString.Short as SBS -- scientific@@ -127,9 +135,9 @@ class ToExpr a where toExpr :: a -> Expr default toExpr- :: (Generic a, All2 ToExpr (GCode a), GFrom a, GDatatypeInfo a)+ :: (Generic a, GToExpr (Rep a)) => a -> Expr- toExpr x = sopToExpr (gdatatypeInfo (Proxy :: Proxy a)) (gfrom x)+ toExpr = genericToExpr listToExpr :: [a] -> Expr listToExpr = Lst . map toExpr@@ -142,32 +150,78 @@ defaultExprViaShow :: Show a => a -> Expr defaultExprViaShow x = App (show x) [] --- | >>> prettyExpr $ sopToExpr (gdatatypeInfo (Proxy :: Proxy String)) (gfrom "foo")--- _:_ 'f' "oo"-sopToExpr :: (All2 ToExpr xss) => DatatypeInfo xss -> SOP I xss -> Expr-sopToExpr di (SOP xss) = hcollapse $ hcliftA2- (Proxy :: Proxy (All ToExpr))- (\ci xs -> K (sopNPToExpr isNewtype ci xs))- (constructorInfo di)- xss- where- isNewtype = case di of- Newtype {} -> True- ADT {} -> False+-------------------------------------------------------------------------------+-- Generics+------------------------------------------------------------------------------- -sopNPToExpr :: All ToExpr xs => Bool -> ConstructorInfo xs -> NP I xs -> Expr-sopNPToExpr _ (Infix cn _ _) xs = App ("_" ++ cn ++ "_") $ hcollapse $- hcmap (Proxy :: Proxy ToExpr) (mapIK toExpr) xs-sopNPToExpr _ (Constructor cn) xs = App cn $ hcollapse $- hcmap (Proxy :: Proxy ToExpr) (mapIK toExpr) xs-sopNPToExpr True (Record cn _) xs = App cn $ hcollapse $- hcmap (Proxy :: Proxy ToExpr) (mapIK toExpr) xs-sopNPToExpr False (Record cn fi) xs = Rec cn $ Map.fromList $ hcollapse $- hcliftA2 (Proxy :: Proxy ToExpr) mk fi xs+class GToExpr f where+ gtoExpr :: f x -> Expr++instance GSumToExpr f => GToExpr (M1 i c f) where+ gtoExpr (M1 x) = gsumToExpr x++class GSumToExpr f where+ gsumToExpr :: f x -> Expr++instance (GSumToExpr f, GSumToExpr g) => GSumToExpr (f :+: g) where+ gsumToExpr (L1 x) = gsumToExpr x+ gsumToExpr (R1 x) = gsumToExpr x++instance GSumToExpr V1 where+#if __GLASGOW_HASKELL__ >= 708+ gsumToExpr x = case x of {}+#else+ gsumToExpr x = x `seq` error "panic: V1 value"+#endif++instance (Constructor c, GProductToExpr f) => GSumToExpr (M1 i c f) where+ gsumToExpr z@(M1 x) = case gproductToExpr x of+ App' exprs -> App cn exprs+ Rec' [] -> App cn []+ Rec' [(_,e)] -> App cn [e]+ Rec' pairs -> Rec cn (Map.fromList pairs)+ where+ cn = conName z++class GProductToExpr f where+ gproductToExpr :: f x -> AppOrRec++instance (GProductToExpr f, GProductToExpr g) => GProductToExpr (f :*: g) where+ gproductToExpr (f :*: g) = gproductToExpr f `combine` gproductToExpr g++instance GProductToExpr U1 where+ gproductToExpr _ = Rec' []++instance (Selector s, GLeafToExpr f) => GProductToExpr (M1 i s f) where+ gproductToExpr z@(M1 x) = case selName z of+ [] -> App' [gleafToExpr x]+ sn -> Rec' [(sn, gleafToExpr x)]++class GLeafToExpr f where+ gleafToExpr :: f x -> Expr++instance ToExpr x => GLeafToExpr (K1 i x) where+ gleafToExpr (K1 x) = toExpr x++data AppOrRec = App' [Expr] | Rec' [(FieldName, Expr)]+ deriving Show++combine :: AppOrRec -> AppOrRec -> AppOrRec+combine (Rec' xs) (Rec' ys) = Rec' (xs ++ ys)+combine xs ys = App' (exprs xs ++ exprs ys) where- mk :: ToExpr x => FieldInfo x -> I x -> K (FieldName, Expr) x- mk (FieldInfo fn) (I x) = K (fn, toExpr x)+ exprs (App' zs) = zs+ exprs (Rec' zs) = map snd zs +-- | Generic 'toExpr'.+--+-- >>> data Foo = Foo Int Char deriving Generic+-- >>> genericToExpr (Foo 42 'x')+-- App "Foo" [App "42" [],App "'x'" []]+--+genericToExpr :: (Generic a, GToExpr (Rep a)) => a -> Expr+genericToExpr = gtoExpr . from+ ------------------------------------------------------------------------------- -- Instances -------------------------------------------------------------------------------@@ -295,11 +349,17 @@ instance ToExpr a => ToExpr (Mon.First a) where instance ToExpr a => ToExpr (Mon.Last a) where +-- ... instance ToExpr a => ToExpr (Semi.Option a) where+ toExpr (Semi.Option x) = App "Option" [toExpr x] instance ToExpr a => ToExpr (Semi.Min a) where+ toExpr (Semi.Min x) = App "Min" [toExpr x] instance ToExpr a => ToExpr (Semi.Max a) where+ toExpr (Semi.Max x) = App "Max" [toExpr x] instance ToExpr a => ToExpr (Semi.First a) where+ toExpr (Semi.First x) = App "First" [toExpr x] instance ToExpr a => ToExpr (Semi.Last a) where+ toExpr (Semi.Last x) = App "Last" [toExpr x] ------------------------------------------------------------------------------- -- containers@@ -470,7 +530,6 @@ ------------------------------------------------------------------------------- -- $setup--- >>> :set -XDeriveGeneric -- >>> :set -XDeriveGeneric -- >>> import Data.Foldable (traverse_) -- >>> import Data.Ratio ((%))
src/Data/TreeDiff/List.hs view
@@ -3,7 +3,6 @@ module Data.TreeDiff.List (diffBy, Edit (..)) where import Data.List.Compat (sortOn)-import qualified Data.MemoTrie as M import qualified Data.Vector as V -- | List edit operations@@ -32,12 +31,23 @@ -- of more obviously correct implementation. -- diffBy :: forall a. (a -> a -> Bool) -> [a] -> [a] -> [Edit a]-diffBy eq xs' ys' = reverse (snd (lcs (V.length xs) (V.length ys)))+diffBy eq xs' ys' = reverse (snd (lcs xn yn)) where+ xn = V.length xs+ yn = V.length ys+ xs = V.fromList xs' ys = V.fromList ys' - lcs = M.memo2 impl+ memo :: V.Vector (Int, [Edit a])+ memo = V.fromList+ [ impl xi yi+ | xi <- [0 .. xn]+ , yi <- [0 .. yn]+ ]++ lcs :: Int -> Int -> (Int, [Edit a])+ lcs xi yi = memo V.! (yi + xi * (yn + 1)) impl :: Int -> Int -> (Int, [Edit a]) impl 0 0 = (0, [])
src/Data/TreeDiff/Pretty.hs view
@@ -28,7 +28,7 @@ import Data.Either (partitionEithers) import Data.TreeDiff.Expr import Numeric (showHex)-import Text.Read (readMaybe)+import Text.Read.Compat (readMaybe) import qualified Data.Map as Map
tests/Tests.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE DeriveGeneric #-} module Main (main) where import Data.Proxy (Proxy (..))@@ -22,7 +22,7 @@ main = defaultMain $ testGroup "tests" [ testProperty "trifecta-pretty roundtrip" roundtripTrifectaPretty , testProperty "parsec-ansi-wl-pprint roundtrip" roundtripParsecAnsiWl- , exFooTests+ , goldenTests ] -------------------------------------------------------------------------------@@ -109,6 +109,44 @@ , fooStr = "Some Name" } -exFooTests :: TestTree-exFooTests = ediffGolden goldenTest "golden exFoo" "fixtures/exfoo.expr" $- return exFoo+newtype MyInt1 = MyInt1 Int+ deriving (Eq, Show, Generic)++newtype MyInt2 = MyInt2 { getMyInt2 :: Int }+ deriving (Eq, Show, Generic)++data MyInt3 = MyInt3 { getMyInt3 :: Int}+ deriving (Eq, Show, Generic)++data Positional = Positional Int Bool Char+ deriving (Eq, Show, Generic)++data Empty+ deriving (Generic)++instance Eq Empty where+ _ == _ = True++instance Show Empty where+ showsPrec _ _ = error "Empty?"++instance ToExpr MyInt1+instance ToExpr MyInt2+instance ToExpr MyInt3+instance ToExpr Positional+instance ToExpr Empty++goldenTests :: TestTree+goldenTests = testGroup "Golden"+ [ ediffGolden goldenTest "exFoo" "fixtures/exfoo.expr" $+ return exFoo+ , ediffGolden goldenTest "MyInt1" "fixtures/MyInt1.expr" $+ return $ MyInt1 42+ , ediffGolden goldenTest "MyInt2" "fixtures/MyInt2.expr" $+ return $ MyInt2 42+ , ediffGolden goldenTest "MyInt3" "fixtures/MyInt3.expr" $+ return $ MyInt3 42+ , ediffGolden goldenTest "Positional" "fixtures/Positional.expr" $+ return $ Positional 12 True 'z'+ ]+
tree-diff.cabal view
@@ -1,9 +1,8 @@-cabal-version: >=1.10-name: tree-diff-version: 0.0.2.1--synopsis: Diffing of (expression) trees.-category: Data, Testing+cabal-version: 2.2+name: tree-diff+version: 0.1+synopsis: Diffing of (expression) trees.+category: Data, Testing description: Common diff algorithm works on list structures: .@@ -27,103 +26,121 @@ @ >>> prettyEditExpr $ ediff (Foo 42 [True, False] "old") (Foo 42 [False, False, True] "new") Foo- {fooBool = [-True, +False, False, +True],- fooInt = 42,- fooString = -"old" +"new"}+ \ {fooBool = [-True, +False, False, +True],+ \ fooInt = 42,+ \ fooString = -"old" +"new"} @-homepage: https://github.com/phadej/tree-diff-bug-reports: https://github.com/phadej/tree-diff/issues-license: BSD3-license-file: LICENSE-author: Oleg Grenrus <oleg.grenrus@iki.fi>-maintainer: Oleg.Grenrus <oleg.grenrus@iki.fi>-copyright: (c) 2017-2018 Oleg Grenrus-build-type: Simple-extra-source-files: README.md ChangeLog.md++homepage: https://github.com/phadej/tree-diff+bug-reports: https://github.com/phadej/tree-diff/issues+license: GPL-2.0-or-later+license-file: LICENSE+author: Oleg Grenrus <oleg.grenrus@iki.fi>+maintainer: Oleg.Grenrus <oleg.grenrus@iki.fi>+copyright: (c) 2017-2019 Oleg Grenrus+build-type: Simple+extra-source-files:+ README.md+ ChangeLog.md+ tested-with:- GHC==7.8.4,- GHC==7.10.3,- GHC==8.0.2,- GHC==8.2.2,- GHC==8.4.4,- GHc==8.6.4+ GHC ==8.8.1 || ==8.6.5 || ==8.4.4 || ==8.2.2 || ==8.0.2 || ==7.10.3 || ==7.8.4 || ==7.6.3 || ==7.4.2 extra-source-files: fixtures/exfoo.expr+ fixtures/MyInt1.expr+ fixtures/MyInt2.expr+ fixtures/MyInt3.expr+ fixtures/Positional.expr source-repository head- type: git- location: https://github.com/phadej/tree-diff.git+ type: git+ location: https://github.com/phadej/tree-diff.git library exposed-modules: Data.TreeDiff- Data.TreeDiff.List- Data.TreeDiff.Tree- Data.TreeDiff.Expr Data.TreeDiff.Class- Data.TreeDiff.Pretty- Data.TreeDiff.Parser+ Data.TreeDiff.Expr Data.TreeDiff.Golden+ Data.TreeDiff.List+ Data.TreeDiff.Parser+ Data.TreeDiff.Pretty Data.TreeDiff.QuickCheck+ Data.TreeDiff.Tree++ -- GHC boot libraries build-depends:- base >=4.7 && <4.13,- aeson >=1.2.1.0 && <1.5,- ansi-wl-pprint >=0.6.8.1 && <0.7,- ansi-terminal >=0.6.3.1 && <0.10,- base-compat >=0.9.3 && <0.11,- bytestring >=0.10.4.0 && <0.11,- containers >=0.5.5.1 && <0.7,- generics-sop >=0.3.1.0 && <0.6,- hashable >=1.2.6.1 && <1.4,- MemoTrie >=0.6.8 && <0.7,- parsec >=3.1.11 && <3.2,- parsers >=0.12.7 && <0.13,- pretty >=1.1.1.1 && <1.2,- QuickCheck >=2.10.0.1 && <2.14,- scientific >=0.3.5.2 && <0.4,- tagged >=0.8.5 && <0.9,- text >=1.2.2.2 && <1.3,- time >=1.4.2 && <1.9,- unordered-containers >=0.2.8.0 && <0.3,- uuid-types >=1.0.3 && <1.1,- vector >=0.12 && <0.13+ , base >=4.5 && <4.13+ , bytestring ^>=0.9.2.1 || ^>=0.10.0.2+ , containers ^>=0.4.2.1 || ^>=0.5.0.0 || ^>=0.6.0.1+ , parsec ^>=3.1.13.0+ , pretty ^>=1.1.1.0+ , text ^>=1.2.3.0+ , time ^>=1.4 || ^>=1.5.0.1 || ^>=1.6.0.1 || ^>=1.8.0.2 - if !impl(ghc >= 8.0)- build-depends:- semigroups >=0.18.3 && <0.20+ build-depends:+ , aeson ^>=1.4.0.0+ , ansi-terminal ^>=0.8.2 || ^>=0.9.1+ , ansi-wl-pprint ^>=0.6.8.2+ , base-compat ^>=0.10.5+ , bytestring-builder ^>=0.10.8.2.0+ , hashable ^>=1.2.7.0 || ^>=1.3.0.0+ , parsers ^>=0.12.10+ , QuickCheck ^>=2.12.6.1 || ^>=2.13.1+ , scientific ^>=0.3.6.2+ , tagged ^>=0.8.6+ , unordered-containers ^>=0.2.8.0+ , uuid-types ^>=1.0.3+ , vector ^>=0.12 - if !impl(ghc >= 7.10)+ if impl(ghc <7.5)+ build-depends: ghc-prim++ if !impl(ghc >=8.0)+ build-depends: semigroups >=0.18.5 && <0.20++ if !impl(ghc >=7.8)+ build-depends: generic-deriving ^>=1.12.4++ if !impl(ghc >=7.10) build-depends:- void >=0.7.2 && <0.8,- nats >=1.1.1 && <1.2,- transformers >=0.3.0.0 && <0.6+ , nats ^>=1.1.2+ , transformers ^>=0.3.0.0 || ^>=0.4.2.0 || ^>=0.5.2.0+ , void ^>=0.7.3 other-extensions:- ConstraintKinds CPP+ ConstraintKinds DefaultSignatures FlexibleContexts GADTs RankNTypes ScopedTypeVariables- hs-source-dirs: src- default-language: Haskell2010+ TypeOperators + hs-source-dirs: src+ default-language: Haskell2010+ test-suite test- default-language: Haskell2010- type: exitcode-stdio-1.0- main-is: Tests.hs- hs-source-dirs: tests- ghc-options: -Wall -threaded+ default-language: Haskell2010+ type: exitcode-stdio-1.0+ main-is: Tests.hs+ hs-source-dirs: tests+ ghc-options: -Wall -threaded build-depends:- base, tree-diff,- base-compat,- QuickCheck,- ansi-terminal,- ansi-wl-pprint,- parsec,- trifecta >=1.7.1.1 && <2.1,- tasty >=0.11.2.5 && <1.3,- tasty-golden >=2.3.1.1 && <2.4,- tasty-quickcheck >=0.9.1 && <0.11+ , ansi-terminal+ , ansi-wl-pprint+ , base+ , base-compat+ , parsec+ , QuickCheck+ , tasty ^>=1.2+ , tasty-golden ^>=2.3.1.1+ , tasty-quickcheck ^>=0.10.1+ , tagged+ , tree-diff+ , trifecta ^>=2++ if impl(ghc <7.5)+ build-depends: ghc-prim