src/Darcs/Patch/Core.lhs

   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.FileName ( fn2fp, fp2fn, norm_path )
  42 import Darcs.Patch.Info ( PatchInfo, patchinfo, make_filename )
  43 import Darcs.Patch.Patchy ( Patchy )
  44 import Darcs.Ordered
  45 import Darcs.Patch.Prim ( Prim(..), FromPrim(..), Effect(effect, effectRL) )
  46 #include "impossible.h"
  47
  48 data Patch C(x y) where
  49     PP :: Prim C(x y) -> Patch C(x y)
  50     ComP :: FL Patch C(x y) -> Patch C(x y)
  51     Merger :: Patch C(x y)
  52            -> RL Patch C(x b)
  53            -> Patch C(c b)
  54            -> Patch C(c d)
  55            -> Patch C(x y)
  56     Regrem :: Patch C(x y)
  57            -> RL Patch C(x b)
  58            -> Patch C(c b)
  59            -> Patch C(c a)
  60            -> Patch C(y x)
  61
  62 instance FromPrim Patch where
  63     fromPrim = PP
  64
  65 data Named p C(x y) where
  66     NamedP :: !PatchInfo -> ![PatchInfo] -> !(p C(x y)) -> Named p C(x y)
  67
  68 instance Effect p => Effect (Named p) where
  69     effect (NamedP _ _ p) = effect p
  70     effectRL (NamedP _ _ p) = effectRL p
  71
  72 is_null_patch :: Patch C(x y) -> Bool
  73 is_null_patch (ComP ps) = and $ mapFL is_null_patch ps
  74 is_null_patch _ = False
  75
  76 nullP :: Patch C(x y) -> EqCheck C(x y)
  77 nullP (ComP NilFL) = IsEq
  78 nullP (ComP (x:>:xs)) | IsEq <- nullP x = nullP (ComP xs)
  79 nullP _ = NotEq
  80
  81 is_merger :: Patch C(a b) -> Bool
  82 is_merger (Merger _ _ _ _) = True
  83 is_merger (Regrem _ _ _ _) = True
  84 is_merger _ = False
  85
  86 merger_undo :: Patch C(x y) -> Patch C(x y)
  87 merger_undo (Merger undo _ _ _) = undo
  88 merger_undo _ = impossible
  89 \end{code}
  90
  91 %Another nice thing to be able to do with composite patches is to `flatten'
  92 %them, that is, turn them into a simple list of patches (appropriately
  93 %ordered, of course), with all nested compositeness unnested.
  94
  95 \begin{code}
  96 {- INLINE flattenFL -}
  97 flattenFL :: Patch C(x y) -> FL Patch C(x y)
  98 flattenFL (ComP ps) = concatFL (mapFL_FL flattenFL ps)
  99 flattenFL (PP Identity) = NilFL
 100 flattenFL p = p :>: NilFL
 101
 102 \end{code}
 103
 104 \begin{code}
 105 join_patchesFL :: FL Patch C(x y) -> Patch C(x y)
 106 join_patchesFL ps = ComP $! ps
 107
 108 infopatch :: Patchy p => PatchInfo -> p C(x y) -> Named p C(x y)
 109 adddeps :: Named p C(x y) -> [PatchInfo] -> Named p C(x y)
 110 getdeps :: Named p C(x y) -> [PatchInfo]
 111
 112 namepatch :: Patchy p => String -> String -> String -> [String] -> p C(x y) -> IO (Named p C(x y))
 113 namepatch date name author desc p
 114     | '\n' `elem` name = error "Patch names cannot contain newlines."
 115     | otherwise = do pinf <- patchinfo date name author desc
 116                      return $ NamedP pinf [] p
 117
 118 anonymous :: Patchy p => p C(x y) -> IO (Named p C(x y))
 119 anonymous p = namepatch "today" "anonymous" "unknown" ["anonymous"] p
 120
 121 infopatch pi p = NamedP pi [] p
 122 adddeps (NamedP pi _ p) ds = NamedP pi ds p
 123 getdeps (NamedP _ ds _) = ds
 124
 125 patch2patchinfo :: Named p C(x y) -> PatchInfo
 126 patch2patchinfo (NamedP i _ _) = i
 127
 128 patchname :: Named p C(x y) -> String
 129 patchname (NamedP i _ _) = make_filename i
 130
 131 patchcontents :: Named p C(x y) -> p C(x y)
 132 patchcontents (NamedP _ _ p) = p
 133 \end{code}
 134
 135 \begin{code}
 136 n_fn :: FilePath -> FilePath
 137 n_fn f = "./"++(fn2fp $ norm_path $ fp2fn f)
 138 \end{code}
 139
 140 The simplest relationship between two patches is that of ``sequential''
 141 patches, which means that the context of the second patch (the one on the
 142 left) consists of the first patch (on the right) plus the context of the
 143 first patch.  The composition of two patches (which is also a patch) refers
 144 to the patch which is formed by first applying one and then the other.  The
 145 composition of two patches, $P_1$ and $P_2$ is represented as $P_2P_1$,
 146 where $P_1$ is to be applied first, then $P_2$\footnote{This notation is
 147 inspired by the notation of matrix multiplication or the application of
 148 operators upon a Hilbert space.  In the algebra of patches, there is
 149 multiplication (i.e.\ composition), which is associative but not
 150 commutative, but no addition or subtraction.}
 151
 152 There is one other very useful relationship that two patches can have,
 153 which is to be parallel patches, which means that the two patches have an
 154 identical context (i.e.\ their representation applies to identical trees).
 155 This is represented by $P_1\parallel P_2$.  Of course, two patches may also
 156 have no simple relationship to one another.  In that case, if you want to
 157 do something with them, you'll have to manipulate them with respect to
 158 other patches until they are either in sequence or in parallel.
 159
 160 The most fundamental and simple property of patches is that they must be
 161 invertible.  The inverse of a patch is described by: $P^{ -1}$.  In the
 162 darcs implementation, the inverse is required to be computable from
 163 knowledge of the patch only, without knowledge of its context, but that
 164 (although convenient) is not required by the theory of patches.
 165 \begin{dfn}
 166 The inverse of patch $P$ is $P^{ -1}$, which is the ``simplest'' patch for
 167 which the composition \( P^{ -1} P \) makes no changes to the tree.
 168 \end{dfn}
 169 Using this definition, it is trivial to prove the following theorem
 170 relating to the inverse of a composition of two patches.
 171 \begin{thm} The inverse of the composition of two patches is
 172 \[ (P_2 P_1)^{ -1} = P_1^{ -1} P_2^{ -1}. \]
 173 \end{thm}
 174 Moreover, it is possible to show that the right inverse of a patch is equal
 175 to its left inverse.  In this respect, patches continue to be analogous to
 176 square matrices, and indeed the proofs relating to these properties of the
 177 inverse are entirely analogous to the proofs in the case of matrix
 178 multiplication.  The compositions proofs can also readily be extended to
 179 the composition of more than two patches.
 180 \begin{code}
 181
 182 \end{code}