-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Implementation of the standard diff algorithm in Haskell.
--   
--   Time complexity is O(ND) (input length * number of differences). Space
--   complexity is O(D^2). Includes utilities for pretty printing.
@package Diff
@version 2.0.1


-- | This is an implementation of the diff algorithm as described in
--   <a><i>An &lt;math&gt; Difference Algorithm and Its Variations
--   (1986)</i> by Eugene W. Myers</a>. For inputs of size &lt;math&gt;
--   with the number of differences &lt;math&gt; it has &lt;math&gt; time
--   and &lt;math&gt; space complexity.
--   
--   <h2>Algorithm overview</h2>
--   
--   Finding the shortest edit script (SES) from a list &lt;math&gt; to a
--   list &lt;math&gt; is modelled as a shortest-path search on an <i>edit
--   graph</i>: an &lt;math&gt; grid of nodes &lt;math&gt;, where
--   &lt;math&gt; and &lt;math&gt; are the lengths of &lt;math&gt; and
--   &lt;math&gt; respectively, with &lt;math&gt; increasing rightward and
--   &lt;math&gt; increasing downward. Each node represents the state of
--   having consumed &lt;math&gt; elements of &lt;math&gt; and &lt;math&gt;
--   elements of &lt;math&gt;. Three types of move are possible:
--   
--   <ul>
--   <li>A <i>rightward</i> move &lt;math&gt; represents <i>deleting</i>
--   &lt;math&gt; and costs one edit.</li>
--   <li>A <i>downward</i> move &lt;math&gt; represents <i>inserting</i>
--   &lt;math&gt; and costs one edit.</li>
--   <li>A <i>diagonal</i> move &lt;math&gt; is free (zero edit cost) and
--   is only available when &lt;math&gt;.</li>
--   </ul>
--   
--   The SES corresponds to a path from &lt;math&gt; to &lt;math&gt; that
--   minimises the number of non-diagonal moves.
--   
--   Both input lists are 0-indexed, which leads to a slightly different
--   interpretation of the edit graph than in the original paper. In the
--   paper, each node represents the state of the traversal <i>after</i> an
--   edit, so a move is the edit that <i>produced</i> that node. Here, each
--   node represents the state <i>before</i> an edit, so a move is the edit
--   performed <i>on</i> that node to yield its successor. This distinction
--   is only relevant when reading the implementation alongside the paper.
--   
--   <h3>K-diagonals and the wave front</h3>
--   
--   Every node &lt;math&gt; lies on the <i>k-diagonal</i> &lt;math&gt;.
--   After exactly &lt;math&gt; non-diagonal moves, every reachable node
--   lies on one of at most &lt;math&gt; k-diagonals &lt;math&gt;. On each
--   diagonal it suffices to track only the <i>furthest-reaching</i> node
--   (the one with the largest &lt;math&gt;), collapsing the
--   two-dimensional grid to a one-dimensional <i>wave front</i> indexed by
--   &lt;math&gt;.
--   
--   The algorithm performs a breadth-first search over &lt;math&gt;,
--   advancing the wave front by one edit at a time until a node reaches
--   the goal &lt;math&gt;. The edit trace stored in that node is the SES,
--   which <a>getDiffBy</a> reconstructs into a <a>PolyDiff</a> list. The
--   term <i>trace</i> here differs from the paper, where it denotes the
--   sequence of k-diagonals visited by the SES path; that structure is not
--   materialised in this implementation.
module Data.Algorithm.Diff

-- | This is <a>PolyDiff</a> specialized so both sides are the same type.
type Diff a = PolyDiff a a

-- | A value tagged with which of two input sequences it came from. The
--   type parameters <tt>a</tt> and <tt>b</tt> may differ, which is useful
--   when comparing sequences of different element types via a custom
--   equality predicate.
--   
--   Each constructor corresponds to one outcome for a position in the
--   aligned sequences:
--   
--   <ul>
--   <li><a>First</a> — the element exists only in the <i>first</i> input
--   (a deletion).</li>
--   <li><a>Second</a> — the element exists only in the <i>second</i> input
--   (an insertion).</li>
--   <li><a>Both</a> — the element is common to both inputs. Both the left
--   and right values are retained so that the original elements can be
--   recovered even when equality ignores some fields.</li>
--   </ul>
data PolyDiff a b
First :: a -> PolyDiff a b
Second :: b -> PolyDiff a b
Both :: a -> b -> PolyDiff a b

-- | Takes two lists and returns a list of differences between them. This
--   is <a>getDiffBy</a> with <a>==</a> used as predicate.
--   
--   <pre>
--   &gt; getDiff ["a","b","c","d","e"] ["a","c","d","f"]
--   [Both "a" "a",First "b",Both "c" "c",Both "d" "d",First "e",Second "f"]
--   &gt; getDiff "abcde" "acdf"
--   [Both 'a' 'a',First 'b',Both 'c' 'c',Both 'd' 'd',First 'e',Second 'f']
--   </pre>
getDiff :: Eq a => [a] -> [a] -> [Diff a]

-- | A form of <a>getDiff</a> with no <a>Eq</a> constraint. Instead, an
--   equality predicate is taken as the first argument.
getDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff a b]

-- | Takes two lists and returns a list of differences between them,
--   grouped into chunks. This is <a>getGroupedDiffBy</a> with <a>==</a>
--   used as predicate.
--   
--   <pre>
--   &gt; getGroupedDiff "abcde" "acdf"
--   [Both "a" "a",First "b",Both "cd" "cd",First "e",Second "f"]
--   </pre>
getGroupedDiff :: Eq a => [a] -> [a] -> [Diff [a]]

-- | Like <a>getGroupedDiff</a> but accepts a custom equality predicate.
--   
--   Postcondition: the output list is guaranteed to be <i>chunked</i>.
--   i.e. no two adjacent elements share the same constructor.
getGroupedDiffBy :: (a -> b -> Bool) -> [a] -> [b] -> [PolyDiff [a] [b]]
instance GHC.Classes.Eq Data.Algorithm.Diff.DI
instance GHC.Classes.Eq Data.Algorithm.Diff.DL
instance GHC.Internal.Show.Show Data.Algorithm.Diff.DI
instance GHC.Internal.Show.Show Data.Algorithm.Diff.DL


-- | Generates a grouped diff with merged runs, and outputs them in the
--   manner of <tt>diff -u</tt>.
module Data.Algorithm.DiffContext

-- | A diff consisting of disjoint <a>Hunk</a>s.
type ContextDiff c = [Hunk c]

-- | A <a>Hunk</a> is a list of adjacent <a>Diff</a>s.
--   
--   No two consecutive elements in a <a>Hunk</a> are both applications of
--   <a>First</a>, <a>Second</a>, or <a>Both</a>, i.e. the list does not
--   stutter on <a>Diff</a> constructors.
type Hunk c = [Diff [c]]

-- | <pre>
--   &gt; let textA = ["a","b","c","d","e","f","g","h","i","j","k"]
--   &gt; let textB = ["a","b","d","e","f","g","h","i","j"]
--   &gt; let diff = getContextDiff (Just 2) textA textB
--   &gt; prettyContextDiff (text "file1") (text "file2") (text . unnumber) diff
--   --- file1
--   +++ file2
--   @@ -1,5 +1,4 @@
--    a
--    b
--   -c
--    d
--    e
--   @@ -9,3 +8,2 @@
--    i
--    j
--   -k
--   </pre>
getContextDiff :: Eq a => Maybe ContextSize -> [a] -> [a] -> ContextDiff (Numbered a)

-- | Pretty print a ContextDiff in the manner of diff -u.
prettyContextDiff :: Doc -> Doc -> (Numbered c -> Doc) -> ContextDiff (Numbered c) -> Doc

-- | Pretty print without line numbers.
prettyContextDiffOld :: Doc -> Doc -> (c -> Doc) -> ContextDiff c -> Doc

-- | Create a diff of separate <a>Hunk</a>s, each containing a sequence of
--   differing elements surrounded by common elements for context.
--   
--   The context size determines when to merge adjacent hunks: two hunks
--   are merged when the number of common elements between them does not
--   exceed twice the context size. Furthermore, if <tt>contextSize</tt> is
--   <a>Nothing</a> a single hunk with the whole diff is produced.
getContextDiffNumbered :: Eq a => Maybe ContextSize -> [Numbered a] -> [Numbered a] -> ContextDiff (Numbered a)
data Numbered a
Numbered :: Int -> a -> Numbered a
numbered :: [a] -> [Numbered a]
unnumber :: Numbered a -> a

-- | If for some reason you need the line numbers stripped from the result
--   of <a>getContextDiff</a> for backwards compatibility.
unNumberContextDiff :: ContextDiff (Numbered a) -> ContextDiff a
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Algorithm.DiffContext.Numbered a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Algorithm.DiffContext.Numbered a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Algorithm.DiffContext.Numbered a)


-- | Generates a string output that is similar to diff normal mode.
module Data.Algorithm.DiffOutput

-- | Converts <a>Diff</a>s to <a>DiffOperation</a>s. <a>First</a> and
--   <a>Second</a> ocurrances are converted to <a>Addition</a> and
--   <a>Deletion</a>, respectively, while consecutive ocurrances of them
--   are replaced by a <a>Change</a>.
diffToLineRanges :: [Diff [String]] -> [DiffOperation LineRange]

-- | Pretty print the differences. The output is similar to the output of
--   the <tt>diff</tt> utility.
--   
--   <pre>
--   &gt; putStr (ppDiff (getGroupedDiff ["a","b","c","d","e"] ["a","c","d","f"]))
--   2d1
--   &lt; b
--   5c4
--   &lt; e
--   ---
--   &gt; f
--   </pre>
ppDiff :: [Diff [String]] -> String

-- | Pretty print of diff operations.
prettyDiffs :: [DiffOperation LineRange] -> Doc

-- | Parse pretty printed <a>Diff</a>s as <a>DiffOperation</a>s.
parsePrettyDiffs :: String -> [DiffOperation LineRange]

-- | Line number alias. Always non-negative.
type LineNo = Int

-- | Line Range: start, end and contents.
--   
--   The following invariants hold:
--   
--   <pre>
--   snd lrNumbers &gt;= fst lrNumbers
--   snd lrNumbers - fst lrNumbers + 1 == length lrContents
--   </pre>
--   
--   which imply <tt>lrContents</tt> cannot be empty.
data LineRange
LineRange :: (LineNo, LineNo) -> [String] -> LineRange
[lrNumbers] :: LineRange -> (LineNo, LineNo)
[lrContents] :: LineRange -> [String]

-- | Smart constructor for <a>LineRange</a> that computes the end line from
--   the start line and the content length, guaranteeing that its content
--   length and range match.
mkLineRange :: Int -> [String] -> LineRange

-- | Diff operation representing changes to apply.
data DiffOperation a

-- | Element deleted on the left input, line number preceding the deleted
--   lines in the right input.
Deletion :: a -> LineNo -> DiffOperation a

-- | Element added from the right input, line number preceding the added
--   lines in the left input.
Addition :: a -> LineNo -> DiffOperation a

-- | Element changed from the left input to the right input.
Change :: a -> a -> DiffOperation a
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Algorithm.DiffOutput.DiffOperation a)
instance GHC.Classes.Eq Data.Algorithm.DiffOutput.LineRange
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Algorithm.DiffOutput.DiffOperation a)
instance GHC.Classes.Ord Data.Algorithm.DiffOutput.LineRange
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Algorithm.DiffOutput.DiffOperation a)
instance GHC.Internal.Read.Read Data.Algorithm.DiffOutput.LineRange
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Algorithm.DiffOutput.DiffOperation a)
instance GHC.Internal.Show.Show Data.Algorithm.DiffOutput.LineRange
