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


-- | Map file locations across diffs
--   
--   See <a>DiffLoc</a>.
@package diff-loc
@version 0.1.0.0


-- | Interfaces of structures used to implement <a>ADiff</a>.
module DiffLoc.Shift

-- | Shift algebra.
--   
--   <b>Laws:</b>
--   
--   <pre>
--   <a>src</a> &lt;$&gt;   <a>shiftR</a> r s   =     <a>shiftBlock</a> r (<a>src</a> s)
--   <a>tgt</a> &lt;$&gt;   <a>shiftR</a> r s   =     <a>shiftBlock</a> r (<a>tgt</a> s)
--   <a>src</a> &lt;$&gt; <a>coshiftR</a> r s   =   <a>coshiftBlock</a> r (<a>src</a> s)
--   <a>tgt</a> &lt;$&gt; <a>coshiftR</a> r s   =   <a>coshiftBlock</a> r (<a>tgt</a> s)
--   
--   <a>shiftBlock</a> r b = Just d   &lt;==&gt;   <a>coshiftBlock</a> r d = Just b
--   <a>shiftR</a>     r s = Just z   &lt;==&gt;   <a>coshiftR</a>     r z = Just s
--   
--   <a>shiftR</a> r s = Just z  &amp;&amp;  <a>shiftR</a> s r = Just q   ==&gt;
--     z <a>&lt;&gt;</a> r  =  q <a>&lt;&gt;</a> s
--   
--   <a>coshiftR</a> r s = Just z  &amp;&amp;  <a>coshiftR</a> s r = Just q   ==&gt;
--     r <a>&lt;&gt;</a> z  =  s <a>&lt;&gt;</a> q
--   </pre>
--   
--   <b>Duality laws:</b>
--   
--   <pre>
--   src = tgt . <a>dual</a>
--   tgt = src . <a>dual</a>
--   shiftBlock = coshiftBlock . <a>dual</a>
--   coshiftBlock = shiftBlock . <a>dual</a>
--   coshiftR = shiftR . <a>dual</a>
--   shiftR = coshiftR . <a>dual</a>
--   </pre>
class (Semigroup r, BlockOrder (Block r)) => Shift r where {
    type Block r :: Type;
}
src :: Shift r => r -> Block r
tgt :: Shift r => r -> Block r
shiftBlock :: Shift r => r -> Block r -> Maybe (Block r)
coshiftBlock :: Shift r => r -> Block r -> Maybe (Block r)
shiftR :: Shift r => r -> r -> Maybe r
coshiftR :: Shift r => r -> r -> Maybe r
dual :: Shift r => r -> r

-- | Partial ordering of interval-like things.
class BlockOrder b
precedes :: BlockOrder b => b -> b -> Bool

-- | Precedes but not adjacent, provided you have a notion of adjacence.
--   Otherwise it's fine to equate this with precedes.
distantlyPrecedes :: BlockOrder b => b -> b -> Bool

-- | <i>Action d'un Monoïde Ordonné.</i> Ordered monoid actions.
--   
--   <ul>
--   <li>An ordered set of points <tt>Ord p</tt>.</li>
--   <li>An ordered monoid of translations (or "vectors") <tt>(Ord (Trans
--   p), Monoid (<a>Trans</a> p))</tt>.</li>
--   </ul>
--   
--   In addition to the <a>Ord</a> and <a>Monoid</a> laws, ordered monoids
--   must have a monotone <tt>(<a>&lt;&gt;</a>)</tt>:
--   
--   <pre>
--   v &lt;= v'   ==&gt;    w &lt;= w'   =&gt;   (v <a>&lt;&gt;</a> w) &lt;= (v' <a>&lt;&gt;</a> w')
--   </pre>
--   
--   <ul>
--   <li>Points can be translated along vectors using
--   <tt>(<a>.+</a>)</tt>.</li>
--   <li>Given two ordered points <tt>i &lt;= j</tt>, <tt>j <a>.-.?</a>
--   i</tt> finds a vector <tt>n</tt> such that <tt>i + n = j</tt>.</li>
--   </ul>
--   
--   In other words, we only require the existence of "positive"
--   translations (this is unlike affine spaces, where translations exist
--   between any two points). This makes it possible to implement this
--   class for line-column locations (<a>DiffLoc.Colline</a>), where
--   translations are not invertible.
--   
--   <tt>(<a>.-.?</a>)</tt> is not part of a standard definition of ordered
--   monoid actions. Feel free to suggest a better name for this structure
--   or a way to not depend on this operation.
--   
--   <b>Laws:</b>
--   
--   <pre>
--                 (x <a>.+</a> v) <a>.+</a> w  =  x <a>.+</a> (v <a>&lt;&gt;</a> w)
--   x <a>&lt;=</a> y  ==&gt;  x <a>.+</a> (y <a>.-.</a> x)  =  y
--                (x <a>.+</a> v) <a>.-.</a> x  =  x
--   </pre>
class (Ord p, Ord (Trans p), Monoid (Trans p)) => Amor p where {
    
    -- | Type of translations between points of <tt>p</tt>.
    type Trans p :: Type;
}

-- | Translate a point.
(.+) :: Amor p => p -> Trans p -> p

-- | Translation between two points. <tt>j .-.? i</tt> must be defined
--   (<a>Just</a>) if <tt>i &lt;= j</tt>,
--   
--   There is an unsafe wrapper <tt>(<a>.-.</a>)</tt> in
--   <a>DiffLoc.Unsafe</a>.
(.-.?) :: Amor p => p -> p -> Maybe (Trans p)
infixr 6 .+

-- | Extend <a>Amor</a> with an "origin" point from which vectors can be
--   drawn to all points. To make the interface slightly more general, only
--   the partial application <tt>(origin .-.)</tt> needs to be supplied.
--   
--   <b>Laws:</b>
--   
--   <pre>
--   <a>origin</a> &lt;= x
--   </pre>
class Amor p => Origin p
origin :: Origin p => p

-- | Find the vector from the origin to this point.
--   
--   <pre>
--   x &lt;= y   <a>=</a>   fromOrigin x &lt;= fromOrigin y
--   
--   <a>ofOrigin</a> (<a>fromOrigin</a> x) = x
--   <a>fromOrigin</a> (<a>ofOrigin</a> v) = v
--   
--   <a>fromOrigin</a> (x .+ v)  =   <a>fromOrigin</a> x &lt;&gt; v
--   </pre>
fromOrigin :: Origin p => p -> Trans p

-- | Translate the origin along a vector.
--   
--   <pre>
--   x &lt;= y   <a>=</a>   ofOrigin x &lt;= ofOrigin y
--   
--   <a>ofOrigin</a> x <a>.+</a> v             =   <a>ofOrigin</a> (x <a>.+</a> v)
--   <a>ofOrigin</a> x <a>.-.</a> <a>ofOrigin</a> y   =   x <a>.-.</a> y
--   </pre>
ofOrigin :: Origin p => Trans p -> p


-- | Indices and offsets.
module DiffLoc.Index

-- | One-dimensional indices.
newtype Plain a
Plain :: a -> Plain a

-- | One-dimensional indices with an origin (an initial index). Indices
--   must be greater than the origin, hence the constructor is hidden.
--   
--   Use <a>indexFromM</a> to construct indices, with
--   <tt>TypeApplications</tt> to make the indexing scheme explicit, and
--   <a>fromIndex</a> to destruct them.
--   
--   <pre>
--   (origin :: IndexFrom n a) &lt;= i    -- for all i
--   </pre>
data IndexFrom (n :: Nat) a

-- | Constructor for <a>IndexFrom</a>.
--   
--   See also <a>indexFrom</a> in <a>DiffLoc.Unsafe</a>, a variant of
--   <a>indexFromM</a> that throws errors instead of using <tt>Maybe</tt>.
indexFromM :: forall n a. (KnownNat n, Num a, Ord a) => a -> Maybe (IndexFrom n a)

-- | <a>indexFromM</a> specialized to 0-indexing.
indexFromM0 :: forall a. (Num a, Ord a) => a -> Maybe (IndexFrom 0 a)

-- | <a>indexFromM</a> specialized to 1-indexing.
indexFromM1 :: forall a. (Num a, Ord a) => a -> Maybe (IndexFrom 1 a)

-- | Destructor for <a>IndexFrom</a>.
fromIndex :: forall n a. IndexFrom n a -> a

-- | <a>fromIndex</a> specialized to 0-indexing.
fromIndex0 :: IndexFrom 0 a -> a

-- | <a>fromIndex</a> specialized to 1-indexing.
fromIndex1 :: IndexFrom 1 a -> a

-- | Convert from one-indexing to zero-indexing.
zeroIndex :: Num a => IndexFrom 1 a -> IndexFrom 0 a

-- | Convert from zero-indexing to one-indexing.
oneIndex :: Num a => IndexFrom 0 a -> IndexFrom 1 a

-- | Type of nonnegative offsets.
data Offset a

-- | Construct a nonnegative <a>Offset</a>.
--   
--   See also <a>offset</a> in <a>DiffLoc.Unsafe</a>, a variant of
--   <a>offsetM</a> that throws errors instead of using <tt>Maybe</tt>.
offsetM :: (Num a, Ord a) => a -> Maybe (Offset a)

-- | Unwrap <a>Offset</a>.
fromOffset :: Offset a -> a
instance GHC.Show.Show a => GHC.Show.Show (DiffLoc.Index.Plain a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (DiffLoc.Index.Plain a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (DiffLoc.Index.Plain a)
instance (GHC.Num.Num a, GHC.Classes.Ord a) => DiffLoc.Shift.Amor (DiffLoc.Index.IndexFrom n a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (DiffLoc.Index.IndexFrom n a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (DiffLoc.Index.IndexFrom n a)
instance GHC.Num.Num a => GHC.Base.Monoid (DiffLoc.Index.Offset a)
instance GHC.Num.Num a => GHC.Base.Semigroup (DiffLoc.Index.Offset a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (DiffLoc.Index.Offset a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (DiffLoc.Index.Offset a)
instance (GHC.Num.Num a, GHC.Classes.Ord a) => DiffLoc.Shift.Amor (DiffLoc.Index.Plain a)
instance GHC.Show.Show a => GHC.Show.Show (DiffLoc.Index.Offset a)
instance GHC.Show.Show a => GHC.Show.Show (DiffLoc.Index.IndexFrom n a)
instance (GHC.Num.Num a, GHC.Classes.Ord a, GHC.TypeNats.KnownNat n) => DiffLoc.Shift.Origin (DiffLoc.Index.IndexFrom n a)


-- | Mapping intervals across diffs
module DiffLoc.Diff

-- | A diff represents a transformation from one file to another.
--   
--   Example diff between "abcdefgh" and "appcfgzzh":
--   
--   <pre>
--   source ab cdefg  h
--        -  b  de
--        +  pp     zz
--   target appc  fgzzh
--   </pre>
--   
--   It consists of three replacements:
--   
--   <ol>
--   <li>replace "b" with "pp" at location 1, <tt>mkReplace 1 1
--   2</tt>;</li>
--   <li>replace "de" with "" at location 3, <tt>mkReplace 3 2 0</tt>;</li>
--   <li>replace "" with "zz" at location 7, <tt>mkReplace 7 0 2</tt>.</li>
--   </ol>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     let d :: Diff N
--         d = addDiff (Replace 1 (offset 1) (offset 2))  -- at location 1, replace "b" (length 1) with "pp" (length 2)
--           $ addDiff (Replace 3 (offset 2) (offset 0))  -- at location 3, replace "de" with ""
--           $ addDiff (Replace 7 (offset 0) (offset 2))  -- at location 7, replace "" with "zz"
--           $ emptyDiff
--     -- N.B.: replacements should be inserted right to left.
--   :}
--   </pre>
--   
--   <a>ADiff</a> is an abstract representation to be instantiated with a
--   concrete representation of atomic replacements.
--   
--   <h2><b>Internal details</b></h2>
--   
--   Internally, a diff is a sequence of <i>disjoint</i> and
--   <i>nonempty</i> replacements, <i>ordered</i> by their source
--   locations. The monoid annotation in the fingertree gives the endpoints
--   of the replacements.
data ADiff r

-- | The empty diff.
emptyDiff :: Semigroup r => ADiff r

-- | Add a replacement to a diff. The replacement is performed <i>after</i>
--   the diff.
--   
--   <h3>Properties</h3>
--   
--   <pre>
--   not (isZeroLength x) ==&gt; mapDiff (addDiff r d) x == (shiftBlock r &lt;=&lt; mapDiff (d :: Diff N)) x
--   </pre>
--   
--   <pre>
--   not (isZeroLength x) ==&gt; comapDiff (addDiff r d) x == (comapDiff d &lt;=&lt; coshiftBlock (r :: Replace N)) x
--   </pre>
addDiff :: forall r. Shift r => r -> ADiff r -> ADiff r

-- | Translate a span in the source of a diff to a span in its target.
--   <tt>Nothing</tt> if the span overlaps with a replacement.
--   
--   For exaple, given the following <a>ADiff</a> (or <a>Replace</a>) from
--   "aAacCc" to "aAabbbcCc":
--   
--   <pre>
--   source aAa   cCc
--        - 
--        +    bbb
--   target aAabbbcCc
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; r0 = Replace 3 (offset 0) (offset 3) :: Replace N
--   
--   &gt;&gt;&gt; d0 = addDiff r0 emptyDiff
--   </pre>
--   
--   The span of "A" remains unchanged.
--   
--   <pre>
--   &gt;&gt;&gt; mapDiff d0 (1 :.. offset 1)
--   Just (1 :.. offset 1)
--   
--   &gt;&gt;&gt; shiftBlock r0 (1 :.. offset 1)
--   Just (1 :.. offset 1)
--   
--   &gt;&gt;&gt; comapDiff d0 (1 :.. offset 1)
--   Just (1 :.. offset 1)
--   
--   &gt;&gt;&gt; coshiftBlock r0 (1 :.. offset 1)
--   Just (1 :.. offset 1)
--   </pre>
--   
--   The span of "C" is shifted by 3 characters.
--   
--   <pre>
--   &gt;&gt;&gt; mapDiff d0 (4 :.. offset 1)
--   Just (7 :.. offset 1)
--   
--   &gt;&gt;&gt; shiftBlock r0 (4 :.. offset 1)
--   Just (7 :.. offset 1)
--   
--   &gt;&gt;&gt; comapDiff d0 (7 :.. offset 1)
--   Just (4 :.. offset 1)
--   
--   &gt;&gt;&gt; coshiftBlock r0 (7 :.. offset 1)
--   Just (4 :.. offset 1)
--   </pre>
--   
--   The span of "ac" overlaps with the replacement, so the mapping is
--   undefined.
--   
--   <pre>
--   &gt;&gt;&gt; mapDiff d0 (2 :.. offset 2)
--   Nothing
--   
--   &gt;&gt;&gt; shiftBlock r0 (2 :.. offset 2)
--   Nothing
--   
--   &gt;&gt;&gt; comapDiff d0 (2 :.. offset 5)
--   Nothing
--   
--   &gt;&gt;&gt; coshiftBlock r0 (2 :.. offset 5)
--   Nothing
--   </pre>
--   
--   <h3>Properties</h3>
--   
--   <pre>
--   \(FSN d s) -&gt; not (isZeroLength s) ==&gt; partialSemiInverse (mapDiff d) (comapDiff d) s
--   </pre>
--   
--   <pre>
--   \(FSN d s) -&gt; not (isZeroLength s) ==&gt; partialSemiInverse (comapDiff d) (mapDiff d) s
--   </pre>
--   
--   where <tt>partialSemiInverse f g x</tt> is the property
--   
--   <pre>
--   if   f x == Just y   -- for some y
--   then g y == Just x
--   </pre>
mapDiff :: Shift r => ADiff r -> Block r -> Maybe (Block r)

-- | Translate a span in the target of a diff to a span in its source.
--   <tt>Nothing</tt> if the span overlaps with a replacement.
--   
--   See also <a>mapDiff</a>.
comapDiff :: Shift r => ADiff r -> Block r -> Maybe (Block r)

-- | <pre>
--   <a>listToDiff</a> = foldr <a>addDiff</a> <a>emptyDiff</a>
--   </pre>
listToDiff :: Shift r => [r] -> ADiff r
instance GHC.Show.Show r => GHC.Show.Show (DiffLoc.Diff.R r)
instance GHC.Classes.Eq r => GHC.Classes.Eq (DiffLoc.Diff.R r)
instance GHC.Classes.Eq r => GHC.Classes.Eq (DiffLoc.Diff.ADiff r)
instance GHC.Show.Show r => GHC.Show.Show (DiffLoc.Diff.ADiff r)
instance GHC.Base.Semigroup r => Data.FingerTree.Measured (GHC.Maybe.Maybe r) (DiffLoc.Diff.R r)


-- | Line-column locations and its offset monoid.
module DiffLoc.Colline

-- | Line and column coordinates.
--   
--   The generalization over types of line and column numbers frees us from
--   any specific indexing scheme, notably whether columns are zero- or
--   one-indexed.
--   
--   <h3>Example</h3>
--   
--   <pre>
--   abc
--   de
--   fgh
--   </pre>
--   
--   Assuming the lines and columns are both 1-indexed, <tt>"b"</tt> is at
--   location <tt>(Colline 1 2)</tt> and <tt>"h"</tt> is at location
--   <tt>(Colline 3 3)</tt>.
data Colline l c
Colline :: !l -> !c -> Colline l c

-- | The space between two <a>Colline</a>s.
--   
--   This type represents offsets between text locations <tt>x &lt;= y</tt>
--   as the number of newlines inbetween and the number of characters from
--   the last new line to <tt>y</tt>, if there is at least one newline, or
--   the number of characters from <tt>x</tt> to <tt>y</tt>.
--   
--   <h3>Example</h3>
--   
--   <pre>
--   abc
--   de
--   fgh
--   </pre>
--   
--   <ul>
--   <li>The offset from <tt>"b"</tt> to <tt>"h"</tt> is <tt>Vallee 2
--   2</tt> (two newlines to reach line 3, and from the beginning of that
--   line, advance two characters to reach h).</li>
--   <li>The offset from <tt>"b"</tt> to <tt>"c"</tt> is <tt>Vallee 0
--   1</tt> (advance one character).</li>
--   </ul>
--   
--   The offset from <tt>"b"</tt> to <tt>"h"</tt> is actually the same as
--   from <tt>"a"</tt> to <tt>"h"</tt> and from <tt>"c"</tt> to
--   <tt>"h"</tt>. Line-column offsets are thus not invertible. This was
--   one of the main constraints in the design of the <a>Amor</a> class.
data Vallee dl dc
Vallee :: !dl -> !dc -> Vallee dl dc

-- | Sans commentaire.
type Vallée = Vallee
instance (GHC.Show.Show l, GHC.Show.Show c) => GHC.Show.Show (DiffLoc.Colline.Colline l c)
instance (GHC.Classes.Ord l, GHC.Classes.Ord c) => GHC.Classes.Ord (DiffLoc.Colline.Colline l c)
instance (GHC.Classes.Eq l, GHC.Classes.Eq c) => GHC.Classes.Eq (DiffLoc.Colline.Colline l c)
instance (GHC.Show.Show dl, GHC.Show.Show dc) => GHC.Show.Show (DiffLoc.Colline.Vallee dl dc)
instance (GHC.Classes.Ord dl, GHC.Classes.Ord dc) => GHC.Classes.Ord (DiffLoc.Colline.Vallee dl dc)
instance (GHC.Classes.Eq dl, GHC.Classes.Eq dc) => GHC.Classes.Eq (DiffLoc.Colline.Vallee dl dc)
instance (GHC.Base.Monoid l, GHC.Classes.Eq l, GHC.Base.Semigroup c) => GHC.Base.Semigroup (DiffLoc.Colline.Vallee l c)
instance (GHC.Base.Monoid l, GHC.Classes.Eq l, GHC.Base.Monoid c) => GHC.Base.Monoid (DiffLoc.Colline.Vallee l c)
instance (DiffLoc.Shift.Amor l, DiffLoc.Shift.Origin c) => DiffLoc.Shift.Amor (DiffLoc.Colline.Colline l c)
instance (DiffLoc.Shift.Origin l, DiffLoc.Shift.Origin c) => DiffLoc.Shift.Origin (DiffLoc.Colline.Colline l c)


-- | Unsafe functions that will throw errors if misused.
module DiffLoc.Unsafe

-- | An unsafe variant of <tt>(<a>.-.?</a>)</tt> which throws an exception
--   on <tt>Nothing</tt>. This operator may appear in class laws, imposing
--   an implicit requirement that its operands must be ordered.
(.-.) :: HasCallStack => Amor p => p -> p -> Trans p
infixl 6 .-.

-- | Constructor for <a>IndexFrom</a>. The index must be greater than the
--   origin, otherwise an error is raised.
--   
--   <pre>
--   origin &lt;= indexFrom i
--   </pre>
indexFrom :: forall n a. (HasCallStack, KnownNat n, Num a, Ord a) => a -> IndexFrom n a

-- | <a>indexFrom</a> specialized to 0-indexing.
indexFrom0 :: (HasCallStack, Num a, Ord a) => a -> IndexFrom 0 a

-- | <a>indexFrom</a> specialized to 1-indexing.
indexFrom1 :: (HasCallStack, Num a, Ord a) => a -> IndexFrom 1 a

-- | Construct an <a>Offset</a>. The offset must be nonnegative, otherwise
--   an error is raised.
offset :: (HasCallStack, Num a, Ord a) => a -> Offset a


-- | <a>Interval</a> implements <a>Shift</a>.
module DiffLoc.Interval

-- | <tt>(i <a>:..</a> n)</tt> represents a span of text between index
--   <tt>i</tt> and index <tt>i+n</tt>.
--   
--   The type of indices <tt>p</tt> is expected to be an instance of
--   <a>Amor</a>.
--   
--   The length <tt>n</tt> in an interval <tt>(i :.. n)</tt> may be zero.
--   
--   The elements of the interval can be thought of as indexing the
--   interstices <i>between</i> characters. A span of length zero is a
--   single interstice between two characters, where some chunk of text may
--   be inserted.
--   
--   Example: drawing of <tt>1 :.. 2</tt> in "abcde".
--   
--   <pre>
--    a b c d e
--   0 1 2 3 4 5
--     ^b+c+ length = 2
--     ^
--     ^ start = 1
--   </pre>
data Interval p
(:..) :: !p -> !Trans p -> Interval p
infixl 3 :..

-- | Does the interval have length zero?
isZeroLength :: (Eq (Trans p), Monoid (Trans p)) => Interval p -> Bool

-- | A minimalistic representation of text replacements.
--   
--   A replacement <tt><a>Replace</a> i n m</tt> is given by a start
--   location <tt>i</tt>, the length <tt>n</tt> of the interval to replace
--   (source) and the length <tt>m</tt> of its replacement (target). This
--   representation does not keep track of the actual data being inserted.
--   
--   This may overapproximate the underlying text replacement, with
--   intervals being wider than necessary. For example, the transformation
--   from "abc" to "ac" could be represented by <tt>mkReplace 1 1 0</tt>
--   (replace "b" with "" at location 1), and also by <tt>mkReplace 0 2
--   1</tt> (replace "ab" with "a" at location 0).
--   
--   <pre>
--   source   abc   abc
--        -    b    ab
--        +         a
--   target   a c   a c
--   </pre>
--   
--   Insertions are replacements with source intervals of length zero.
--   Deletions are replacements with target intervals of length zero.
data Replace p
Replace :: !p -> !Trans p -> !Trans p -> Replace p
instance (GHC.Classes.Eq p, GHC.Classes.Eq (DiffLoc.Shift.Trans p)) => GHC.Classes.Eq (DiffLoc.Interval.Interval p)
instance (GHC.Show.Show p, GHC.Show.Show (DiffLoc.Shift.Trans p)) => GHC.Show.Show (DiffLoc.Interval.Interval p)
instance (GHC.Classes.Eq p, GHC.Classes.Eq (DiffLoc.Shift.Trans p)) => GHC.Classes.Eq (DiffLoc.Interval.Replace p)
instance (GHC.Show.Show p, GHC.Show.Show (DiffLoc.Shift.Trans p)) => GHC.Show.Show (DiffLoc.Interval.Replace p)
instance DiffLoc.Shift.Amor p => GHC.Base.Semigroup (DiffLoc.Interval.Replace p)
instance DiffLoc.Shift.Amor p => DiffLoc.Shift.Shift (DiffLoc.Interval.Replace p)
instance DiffLoc.Shift.Amor p => DiffLoc.Shift.BlockOrder (DiffLoc.Interval.Interval p)


-- | Basic configurations to get started.
module DiffLoc.Starter

-- | A shorthand for the common use case of <a>Diff</a>.
type Diff p = ADiff (Replace p)

-- | Integers.
type Z = Plain :$: Int

-- | Natural numbers.
type N = IndexFrom 0 :$: Int

-- | Positive numbers.
type N' = IndexFrom 1 :$: Int

-- | A trick to reduce noise by hiding newtype wrapper constructors. This
--   makes the documentation more palatable.
--   
--   <pre>
--   &gt;&gt;&gt; show (NoShow (Plain 3) :: Plain :$: Int)
--   "3"
--   
--   &gt;&gt;&gt; show (Colline 4 2 :.. Vallee (offset 3) (offset 3) :: Interval (Colline N N))
--   "Colline 4 2 :.. Vallee (offset 3) (offset 3)"
--   </pre>
newtype f :$: x
NoShow :: f x -> (:$:) f x
instance DiffLoc.Shift.Origin (f x) => DiffLoc.Shift.Origin (f DiffLoc.Starter.:$: x)
instance DiffLoc.Shift.Amor (f x) => DiffLoc.Shift.Amor (f DiffLoc.Starter.:$: x)
instance GHC.Base.Monoid (f x) => GHC.Base.Monoid (f DiffLoc.Starter.:$: x)
instance GHC.Base.Semigroup (f x) => GHC.Base.Semigroup (f DiffLoc.Starter.:$: x)
instance GHC.Classes.Ord (f x) => GHC.Classes.Ord (f DiffLoc.Starter.:$: x)
instance GHC.Classes.Eq (f x) => GHC.Classes.Eq (f DiffLoc.Starter.:$: x)
instance GHC.Show.Show a => GHC.Show.Show (DiffLoc.Index.Plain DiffLoc.Starter.:$: a)
instance GHC.Show.Show a => GHC.Show.Show (DiffLoc.Index.IndexFrom n DiffLoc.Starter.:$: a)
instance GHC.Show.Show a => GHC.Show.Show (DiffLoc.Index.Offset DiffLoc.Starter.:$: a)
instance GHC.Num.Num a => GHC.Num.Num (DiffLoc.Index.Plain DiffLoc.Starter.:$: a)
instance (GHC.Num.Num a, GHC.Classes.Ord a, GHC.TypeNats.KnownNat n) => GHC.Num.Num (DiffLoc.Index.IndexFrom n DiffLoc.Starter.:$: a)
instance (GHC.Num.Num a, GHC.Classes.Ord a) => GHC.Num.Num (DiffLoc.Index.Offset DiffLoc.Starter.:$: a)


-- | <h1>Example</h1>
--   
--   You have a diff between two versions of a file. Given a source
--   location in one version, find the corresponding location in the other
--   version.
--   
--   For example, here is a diff <tt>d</tt> between a source string
--   "abcdefgh" and a target string "appcfgzzh", with deletions and
--   insertions in the middle:
--   
--   <pre>
--    ab cdefg  h
--   - b  de
--   + pp     zz
--    appc  fgzzh
--   </pre>
--   
--   Diffs are represented by the type <a>Diff</a>. Only locations and
--   lengths are recorded, not the actual characters.
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     let d :: Diff N
--         d = addDiff (Replace 1 (offset 1) (offset 2))  -- at location 1, replace "b" (length 1) with "pp" (length 2)
--           $ addDiff (Replace 3 (offset 2) (offset 0))  -- at location 3, replace "de" with ""
--           $ addDiff (Replace 7 (offset 0) (offset 2))  -- at location 7, replace "" with "zz"
--           $ emptyDiff
--     -- N.B.: replacements should be inserted right to left, starting from 'emptyDiff'.
--   :}
--   </pre>
--   
--   The span <tt>s</tt> of "fg" in the first string starts at location 5
--   and has length 2.
--   
--   <pre>
--   &gt;&gt;&gt; let s = 5 :.. offset 2 :: Interval N
--   </pre>
--   
--   <pre>
--    a b c d e f g h
--   0 1 2 3 4 5 6 7 8
--             ^f+g+ length 2
--             ^
--             start 5
--   </pre>
--   
--   After applying the diff, the resulting span has been shifted to
--   location 4.
--   
--   <pre>
--   &gt;&gt;&gt; mapDiff d (5 :.. offset 2)
--   Just (4 :.. offset 2)
--   </pre>
--   
--   <pre>
--    a p p c f g q q h
--   0 1 2 3 4 5 6 7 8 9
--           ^f+g+ length 2
--           ^
--           start 4
--   </pre>
--   
--   Conversely, we can map spans from the target string to the source
--   string of the diff:
--   
--   <pre>
--   &gt;&gt;&gt; comapDiff d (4 :.. offset 2)
--   Just (5 :.. offset 2)
--   </pre>
--   
--   If part of the input span is modified by the diff, there is no
--   corresponding output span.
--   
--   <pre>
--   &gt;&gt;&gt; mapDiff d (1 :.. offset 2)  -- "bc" contains "b" which is edited by the diff
--   Nothing
--   </pre>
module DiffLoc