1 %  Copyright (C) 2002-2003 David Roundy
    2 %
    3 %  This program is free software; you can redistribute it and/or modify
    4 %  it under the terms of the GNU General Public License as published by
    5 %  the Free Software Foundation; either version 2, or (at your option)
    6 %  any later version.
    7 %
    8 %  This program is distributed in the hope that it will be useful,
    9 %  but WITHOUT ANY WARRANTY; without even the implied warranty of
   10 %  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   11 %  GNU General Public License for more details.
   12 %
   13 %  You should have received a copy of the GNU General Public License
   14 %  along with this program; see the file COPYING.  If not, write to
   15 %  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
   16 %  Boston, MA 02110-1301, USA.
   17 
   18 
   19 \section{Patch relationships}
   20 
   21 \begin{code}
   22 {-# OPTIONS_GHC -cpp -fglasgow-exts #-}
   23 {-# LANGUAGE CPP #-}
   24 -- , GADTs, PatternGuards #-}
   25 
   26 #include "gadts.h"
   27 
   28 module Darcs.Patch.Core
   29        ( Patch(..), Named(..),
   30          join_patchesFL, concatFL, flattenFL,
   31          nullP, is_null_patch, infopatch,
   32          n_fn,
   33          adddeps, namepatch, anonymous,
   34          merger_undo, is_merger,
   35          getdeps,
   36          patch2patchinfo, patchname, patchcontents,
   37        )
   38        where
   39 
   40 import Prelude hiding ( pi )
   41 import Darcs.Patch.Info ( PatchInfo, patchinfo, make_filename )
   42 import Darcs.Patch.Patchy ( Patchy )
   43 import Darcs.Ordered
   44 import Darcs.Patch.Prim ( Prim(..), FromPrim(..), Effect(effect, effectRL), n_fn )
   45 #include "impossible.h"
   46 
   47 data Patch C(x y) where
   48     PP :: Prim C(x y) -> Patch C(x y)
   49     ComP :: FL Patch C(x y) -> Patch C(x y)
   50     Merger :: Patch C(x y)
   51            -> RL Patch C(x b)
   52            -> Patch C(c b)
   53            -> Patch C(c d)
   54            -> Patch C(x y)
   55     Regrem :: Patch C(x y)
   56            -> RL Patch C(x b)
   57            -> Patch C(c b)
   58            -> Patch C(c a)
   59            -> Patch C(y x)
   60 
   61 instance FromPrim Patch where
   62     fromPrim = PP
   63 
   64 data Named p C(x y) where
   65     NamedP :: !PatchInfo -> ![PatchInfo] -> !(p C(x y)) -> Named p C(x y)
   66 
   67 instance Effect p => Effect (Named p) where
   68     effect (NamedP _ _ p) = effect p
   69     effectRL (NamedP _ _ p) = effectRL p
   70 
   71 is_null_patch :: Patch C(x y) -> Bool
   72 is_null_patch (ComP ps) = and $ mapFL is_null_patch ps
   73 is_null_patch _ = False
   74 
   75 nullP :: Patch C(x y) -> EqCheck C(x y)
   76 nullP (ComP NilFL) = IsEq
   77 nullP (ComP (x:>:xs)) | IsEq <- nullP x = nullP (ComP xs)
   78 nullP _ = NotEq
   79 
   80 is_merger :: Patch C(a b) -> Bool
   81 is_merger (Merger _ _ _ _) = True
   82 is_merger (Regrem _ _ _ _) = True
   83 is_merger _ = False
   84 
   85 merger_undo :: Patch C(x y) -> Patch C(x y)
   86 merger_undo (Merger undo _ _ _) = undo
   87 merger_undo _ = impossible                                                                                                    
   88 \end{code}
   89 
   90 %Another nice thing to be able to do with composite patches is to `flatten'
   91 %them, that is, turn them into a simple list of patches (appropriately
   92 %ordered, of course), with all nested compositeness unnested.
   93 
   94 \begin{code}
   95 {- INLINE flattenFL -}
   96 flattenFL :: Patch C(x y) -> FL Patch C(x y)
   97 flattenFL (ComP ps) = concatFL (mapFL_FL flattenFL ps)
   98 flattenFL (PP Identity) = NilFL
   99 flattenFL p = p :>: NilFL
  100 
  101 join_patchesFL :: FL Patch C(x y) -> Patch C(x y)
  102 join_patchesFL ps = ComP $! ps
  103 
  104 infopatch :: Patchy p => PatchInfo -> p C(x y) -> Named p C(x y)
  105 adddeps :: Named p C(x y) -> [PatchInfo] -> Named p C(x y)
  106 getdeps :: Named p C(x y) -> [PatchInfo]
  107 
  108 namepatch :: Patchy p => String -> String -> String -> [String] -> p C(x y) -> IO (Named p C(x y))
  109 namepatch date name author desc p
  110     | '\n' `elem` name = error "Patch names cannot contain newlines."
  111     | otherwise = do pinf <- patchinfo date name author desc
  112                      return $ NamedP pinf [] p
  113 
  114 anonymous :: Patchy p => p C(x y) -> IO (Named p C(x y))
  115 anonymous p = namepatch "today" "anonymous" "unknown" ["anonymous"] p
  116 
  117 infopatch pi p = NamedP pi [] p
  118 adddeps (NamedP pi _ p) ds = NamedP pi ds p
  119 getdeps (NamedP _ ds _) = ds
  120 
  121 patch2patchinfo :: Named p C(x y) -> PatchInfo
  122 patch2patchinfo (NamedP i _ _) = i
  123 
  124 patchname :: Named p C(x y) -> String
  125 patchname (NamedP i _ _) = make_filename i
  126 
  127 patchcontents :: Named p C(x y) -> p C(x y)
  128 patchcontents (NamedP _ _ p) = p
  129 \end{code}
  130 
  131 The simplest relationship between two patches is that of ``sequential''
  132 patches, which means that the context of the second patch (the one on the
  133 left) consists of the first patch (on the right) plus the context of the
  134 first patch.  The composition of two patches (which is also a patch) refers
  135 to the patch which is formed by first applying one and then the other.  The
  136 composition of two patches, $P_1$ and $P_2$ is represented as $P_2P_1$,
  137 where $P_1$ is to be applied first, then $P_2$\footnote{This notation is
  138 inspired by the notation of matrix multiplication or the application of
  139 operators upon a Hilbert space.  In the algebra of patches, there is
  140 multiplication (i.e.\ composition), which is associative but not
  141 commutative, but no addition or subtraction.}
  142 
  143 There is one other very useful relationship that two patches can have,
  144 which is to be parallel patches, which means that the two patches have an
  145 identical context (i.e.\ their representation applies to identical trees).
  146 This is represented by $P_1\parallel P_2$.  Of course, two patches may also
  147 have no simple relationship to one another.  In that case, if you want to
  148 do something with them, you'll have to manipulate them with respect to
  149 other patches until they are either in sequence or in parallel.
  150 
  151 The most fundamental and simple property of patches is that they must be
  152 invertible.  The inverse of a patch is described by: $P^{ -1}$.  In the
  153 darcs implementation, the inverse is required to be computable from
  154 knowledge of the patch only, without knowledge of its context, but that
  155 (although convenient) is not required by the theory of patches.
  156 \begin{dfn}
  157 The inverse of patch $P$ is $P^{ -1}$, which is the ``simplest'' patch for
  158 which the composition \( P^{ -1} P \) makes no changes to the tree.
  159 \end{dfn}
  160 Using this definition, it is trivial to prove the following theorem
  161 relating to the inverse of a composition of two patches.
  162 \begin{thm} The inverse of the composition of two patches is
  163 \[ (P_2 P_1)^{ -1} = P_1^{ -1} P_2^{ -1}. \]
  164 \end{thm}
  165 Moreover, it is possible to show that the right inverse of a patch is equal
  166 to its left inverse.  In this respect, patches continue to be analogous to
  167 square matrices, and indeed the proofs relating to these properties of the
  168 inverse are entirely analogous to the proofs in the case of matrix
  169 multiplication.  The compositions proofs can also readily be extended to
  170 the composition of more than two patches.
  171 \begin{code}
  172 
  173 \end{code}