data-rope (empty) → 0.3
raw patch · 4 files changed
+1325/−0 lines, 4 filesdep +basedep +bytestringdep +bytestring-mmapsetup-changed
Dependencies added: base, bytestring, bytestring-mmap, unix
Files
- Data/Rope.lhs +964/−0
- LICENSE +340/−0
- Setup.hs +3/−0
- data-rope.cabal +18/−0
+ Data/Rope.lhs view
@@ -0,0 +1,964 @@++\begin{code}+{-# OPTIONS -XMagicHash -XUnboxedTuples -XRecordWildCards -XNamedFieldPuns -XNoImplicitPrelude -cpp #-}+{-# LANGUAGE ForeignFunctionInterface #-}+-- | Implementation of the ideas in +-- <http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf>.+-- Inspired also by "Data.Map" and the OCaml version of ropes.+module Data.Rope(+ -- * The 'Rope' type+ Rope,+ -- * Introducing and eliminating 'Rope's+ empty,+ singleton,+ pack,+ unpack,+ fromByteString,+ toByteString,+ -- * Basic interface+ cons,+ snoc,+ append,+ head,+ uncons,+ last,+ tail,+ init,+ null,+ length,+ -- * Transforming 'Rope's+ map,+ reverse,+ intercalate,+ -- * Concatenations+ insert,+ -- * Reducing 'Rope's+ foldl,+ foldl',+ foldr,+ -- * Breaking 'Rope's+ take,+ drop,+ splitAt#,+ splitAt,+ breakByte,+ breaks,+ lines,+ -- * Indexing 'Rope's+ index,+ elemIndex,+ elemIndex',+ elemIndices,+ -- * Input and Output+ readFile,+ hGet,+ hGetLine,+ hGetContents,+ hPut,+ hPutStrLn,+ hPutStr,+ putStrLn,+ putStr, ++ ) where++import Foreign.Storable+import Foreign.ForeignPtr+import qualified Foreign.Concurrent as FC+import Foreign.Marshal.Array+import Foreign.Marshal.Utils+import Foreign.Ptr++import Foreign.C.Types++import qualified Data.ByteString.Internal as B+import Data.String+import Data.Word+import Control.Exception (finally)+#if __GLASGOW_HASKELL__ >=608+import GHC.IO (IO(IO),unsafePerformIO,unsafeInterleaveIO)+import GHC.Base (realWorld#)+import GHC.IO.Handle.Types+--import GHC.IO.Handle.Internals+import GHC.IO.Device as IODevice+#else+import System.IO.Unsafe+#endif+import Data.Maybe+import GHC.Conc (par)++import System.Posix (openFd,closeFd,defaultFileFlags,getFileStatus,+ fileSize,OpenMode(..))++import System.IO (hGetBuf,hPutBuf,hSeek,hTell,+ hPutChar, stdout, hClose)+import System.IO.Posix.MMap.Internal(c_mmap,c_munmap)++import qualified Prelude(length,map,splitAt)+import Prelude hiding (length,null,head,tail,last,init,map,reverse,+ foldl,foldr,+ take,drop,splitAt,lines,+ putStrLn,putStr,readFile)+import Data.Bits hiding(rotateL,rotateR)++\end{code}++Attention, on ne garantit pas necessairement que les deux sous-arbres sont non-vides.+Il faudrait regler ce probleme dans balance.++i0 est le premier indice ou on a le droit d'ecrire.+File sert a ne pas recrire tout un fichier. On l'enleve des qu'on modifie+la @Rope@, par contre. Il faut recrire la fin du fichier quand meme, dans ce cas.+\begin{code}+data Rope=+ Concat { sizeC:: !Int,+ length_:: !Int,+ l::Rope,+ r::Rope }+ | String { contents:: !(ForeignPtr Word8),+ i0:: !(ForeignPtr Int),+ offset:: !Int,+ length_:: !Int }++instance IsString Rope where+ fromString s=pack $ Prelude.map (fromIntegral.fromEnum) s+++instance Show Rope where+ show s="\""++(Prelude.map (toEnum.fromIntegral) $ unpack s)++"\""++{-+instance Show Rope where+ show (s@String{})=show ((Prelude.map (toEnum.fromIntegral) $ unpack s)::String)+ show (Concat{l,r})="Concat { l="++(show l)++"\nr="++(show r)+-}++instance Eq Rope where+ (==) String{contents=ca,offset=oa,length_=la}+ String{contents=cb, offset=ob, length_=lb} =+ + la==lb &&+ (inlinePerformIO $ (withForeignPtr ca $ \pa->+ withForeignPtr cb $ \pb->do+ x<-strncmp (pa`plusPtr`oa) (pb`plusPtr`ob) (fromIntegral la)+ return $ x == 0))+ + (==) a b=+ (length a == length b) &&+ (case (a,b) of+ (Concat{l,r}, _) -> + let (# x,y #)=splitAt# (length l) b in+ x==l && y==r+ (_,Concat{l,r})->+ let (# x,y #)=splitAt# (length l) a in+ x==l && y==r+ _->undefined) -- never happens+ + +instance Ord Rope where+ compare (String{contents=ca,offset=oa,length_=la})+ (String{contents=cb, offset=ob, length_=lb}) =+ + inlinePerformIO $ (withForeignPtr ca $ \pa->withForeignPtr cb $ \pb->do+ x<-strncmp (pa`plusPtr`oa) (pb`plusPtr`ob) (fromIntegral $ min la lb)+ if x==0 then return $ compare la lb else+ return $ compare x 0)+ + compare a_ b_=+ let (a,b)=if length a_<length b_ then (b_,a_) else (a_,b_) in+ case (a,b) of+ (_,Concat{l,r})->+ let (# x,y #)=splitAt# (length l) a in+ case compare x l of+ EQ->compare y r+ ord->ord+ (Concat{l,r},_)->+ let (# x,y #)=splitAt# (length l) b in+ case compare l x of+ EQ->compare r y+ ord->ord+ _->undefined --never happens+++ +-- | leafLen est la taille standard des blocs de feuilles.+leafSize::Int+leafSize=0x10000++\end{code}++Interface basique. Rien \`a dire.++Pour cons et snoc, il ne servirait a rien de rajouter un bout "non utilise"+au debut de la chaine : vu qu'on ecrit toutes les chaines depuis l'offset 0,+si on prend une sous-chaine, c'est que le debut est deja utilise dans une autre+sous-chaine.++\begin{code}++-- | O(log n). Appends the specified byte at the beginning of the 'Rope'.+cons::Word8->Rope->Rope+cons w x=append (singleton w) x+{-# INLINE cons #-}++-- | O(log n). Appends the specified byte at the end of the 'Rope'.+snoc::Rope->Word8->Rope+snoc x w=append x (singleton w)+{-# INLINE snoc #-}++-- | O(log n) First element of the 'Rope'. Raises an error if the argument is empty.+head::Rope->Word8+head (String{contents,offset,length_})+ |length_>0 = inlinePerformIO $ withForeignPtr contents $ \c->peekByteOff c offset+ |otherwise = error "head"+head (Concat{l})=head l++-- | O(log n). Returns the first element of the 'Rope', and the 'Rope' of the+-- remaining elements.+uncons::Rope->Maybe (Word8, Rope)+uncons (s@String{contents,offset,length_})+ | length_<=0 = Nothing+ | otherwise=+ let u=inlinePerformIO $ withForeignPtr contents $ \c->peekByteOff c offset in+ Just (u,s { contents,offset=offset+1,length_=length_-1 })+uncons (c@Concat{l,r,length_})=+ case uncons l of+ Just (x,y)->Just (x,balance $ c { l=y, length_=length_-1 })+ Nothing->uncons r++-- | O(log n). Last element of a 'Rope'.+last::Rope->Word8+last (String{contents,offset,length_})+ | length_<=0 = error "last"+ | otherwise = inlinePerformIO $ withForeignPtr contents $ \c->peekByteOff c $ offset+length_-1+last (Concat{l,r})+ |size r<=0 = last l+ |otherwise = last r+++-- | O(log n) The elements after the head. An error is raised if the 'Rope' is empty.+tail::Rope->Rope+tail (s@String{offset,length_})+ | length_<=0 = error "tail"+ | otherwise = s { offset=offset+1,length_=length_-1 }+tail (c@Concat{l,r})+ | length l<=0 = tail r+ | otherwise = balance $ c { l=tail l }+++-- | O(log n) The elements in the 'Rope' except the last one.+init::Rope->Rope+init (s@String{length_})+ | length_<=0 = error "init"+ | otherwise = s { length_=length_-1 }+init (s@Concat{r})=balance $ s { r=init r }++-- | O(1) Tests whether a 'Rope' is empty.+null::Rope->Bool+null x=length x==0++-- | O(1) Length of a 'Rope'.+length::Rope->Int+length (String{length_})=length_+length (Concat{length_})=length_++size::Rope->Int+size (Concat {sizeC})=sizeC+size _=1++\end{code}++Transformations++\begin{code}++-- | O(n). @'map' f r@ applies @f@ on each element of @r@ and returns the+-- concatenation of the result.+map::(Word8->Word8)->Rope->Rope+map f (String{contents,offset,length_})=+ unsafePerformIO $ withForeignPtr contents $ \c->do+ cont<-mallocForeignPtrBytes leafSize+ withForeignPtr cont $ \p->copyMap p (c`plusPtr`offset) length_+ + i0<-mallocForeignPtr+ withForeignPtr i0 $ \i->poke i length_+ + return $ String { contents=cont,offset=0,length_,i0 }++ where+ copyMap _ _ 0=return ()+ copyMap p p' len=do+ peek p' >>= ((poke p).f)+ copyMap (p`plusPtr`1) (p'`plusPtr`1) $ len-1++map f (Concat{l,r})=append (map f l) (map f r)++-- | O(n) efficient way to reverse a 'Rope'.+reverse::Rope->Rope+reverse (String{contents,offset,length_})=+ unsafePerformIO $ withForeignPtr contents $ \c->do+ cont<-mallocForeignPtrBytes leafSize+ withForeignPtr cont $ \p->+ copyRev (p`plusPtr`(length_-1)) (c`plusPtr`offset) length_+ + i0<-mallocForeignPtr+ withForeignPtr i0 $ \i->poke i length_+ + return $ String { contents=cont,offset=0,length_,i0 }++ where+ copyRev::Ptr Word8->Ptr Word8->Int->IO()+ copyRev _ _ 0=return ()+ copyRev p p' len=do+ peek p' >>= poke p+ copyRev (p`plusPtr`(-1)) (p'`plusPtr`1) $ len-1++reverse (Concat{l,r})=append (reverse r) (reverse l)++-- | O(n) intercalate an element between each element of the list of 'Rope's+-- and concatenates the result.+intercalate::Rope->[Rope]->Rope+intercalate rope list=+ intercalate_ list empty+ where+ intercalate_ [] x=x+ intercalate_ [h] x=append x h+ intercalate_ (h:s) x=intercalate_ s (append (append h rope) x)+++\end{code}++Il n'est pas clair qu'on ne puisse pas faire beaucoup mieux que ce pack.+Par exemple, vu qu'on calcule la taille de la liste, on pourrait sortir un arbre+directement \'equilibr\'e. Vu qu'on ne fait jamais pack avec des 'ByteString's+(sauf ghc quand il compile des IsString), \c ca ne vaut sans doute pas le co\^ut.++Par contre, append est utilise presque partout. Il est crucial que son implementation+soit extremement efficace.++\begin{code}+-- | O(1) The empty 'Rope'+empty::Rope+empty=unsafePerformIO $ do+ contents<-mallocForeignPtrArray leafSize+ i0<-mallocForeignPtr+ withForeignPtr i0 $ \i->poke i (-1)+ return $ String { contents,i0,offset=0,length_=0 }++-- | O(1) Convert a 'Word8' into a 'Rope'+singleton::Word8->Rope+singleton c=unsafePerformIO $ do+ contents<-mallocForeignPtrArray leafSize+ withForeignPtr contents $ \con->poke con c+ i0<-mallocForeignPtr+ withForeignPtr i0 $ \i->poke i 1+ return $ String { contents,i0,offset=0,length_=1 }++-- | O(n) Convert a list of 'Word8' into a 'Rope'+pack::[Word8]->Rope+pack s=+ if Prelude.length s<=leafSize then unsafePerformIO $ do+ contents<-mallocForeignPtrArray leafSize+ i0<-mallocForeignPtr+ withForeignPtr i0 $ \i->poke i $ Prelude.length s+ withForeignPtr contents $ \c->fillPtr c s+ return $ String { contents, i0, offset=0, length_=Prelude.length s }+ else+ let (a,b)=Prelude.splitAt leafSize s in+ append (pack a) (pack b)++ where+ fillPtr::Storable a=>Ptr a->[a]->IO ()+ fillPtr _ []=return ()+ fillPtr ptr (h:t)=do+ poke ptr h+ fillPtr (plusPtr ptr 1) t++++-- | O(n) Inverse conversion+unpack::Rope->[Word8]+unpack (Concat{l,r})=unpack l++unpack r+unpack (String{contents,offset,length_})=+ unsafePerformIO $+ mapM (\i->withForeignPtr contents $+ \c->peek (plusPtr c i)::IO Word8) [offset..(offset+length_-1)]+++-- | O(log n) Concatenates two 'Rope's+append::Rope->Rope->Rope+append sa@(String {}) sb@(String{})+ |length sa + offset sa + length sb <= leafSize = unsafePerformIO $ do+ i0_<-withForeignPtr (i0 sa) $ peek+ let l=length sa+ if i0_<offset sa+l then do+ withForeignPtr (i0 sa) $ \i->poke i $ offset sa+l+length sb+ withForeignPtr (contents sa) $+ \ca->withForeignPtr (contents sb) $+ \cb->copyArray (ca`plusPtr`(l+offset sa)::Ptr Word8) + (cb`plusPtr`(offset sb)) $ length sb+ return $ sa { length_=length sa+length sb }+ else+ return $ Concat { sizeC=3,+ length_=length sa+length sb,+ l=sa,+ r=sb }++ |otherwise=+ Concat { sizeC=3,+ length_=length sa+length sb,+ l=sa,+ r=sb }++append x@String{} y@Concat{sizeC,l}=balance $ y { sizeC=1+sizeC,+ length_=length x+length y,+ l=append x l }+append x y = balance $ Concat { sizeC=size x+size y,+ length_=length x+length y,+ l=x,+ r=y }++++-- | O(log n) @'insert' a i b@ inserts 'Rope' @a@ in 'Rope' @b@ after the @i@th element of @b@.+insert::Rope->Int->Rope->Rope+insert a 0 b=append a b+insert a i (b@String{})=+ balance $ Concat { sizeC=size a+size b,+ length_=length a+length b,+ l=String { contents=contents b,+ i0=i0 b,+ offset=offset b,+ length_=min i $ length b },+ r=append a $ String { contents=contents b,+ i0=i0 b,+ offset=i+offset b,+ length_=max 0 $ (length b)-i }+ }+ +insert a i (b@Concat{})+ |i>=(length $ r b) = balance $ b { r=insert a (i-(length $ r b)) $ r b }+ |otherwise = balance $ b { l=insert a i $ l b}+ ++\end{code}++R\'e\'equilibrage des arbres.++@delta@ et @ratio@ sont des param\`etres exp\'erimentaux. Peut-\^etre faut-il+profiler un peu.++\begin{code}++delta,ratio::Int+delta=5+ratio=2++balance,rotateL,rotateR,singleL,singleR,doubleL,doubleR::Rope->Rope++balance x=case x of+ String{}->x+ Concat{l,r}+ | length l==0 -> r+ | length r==0 -> l+ | size r>=delta*size l -> rotateL x+ | size l>=delta*size r -> rotateR x+ | otherwise->x+ +rotateL x=case x of+ String{}->x+ Concat{r}->case r of+ String{}->x+ Concat{l=rl,r=rr}+ |size rl<ratio*size rr -> singleL x+ |otherwise -> doubleL x++rotateR x=case x of+ String{}->x+ Concat{l}->case l of+ String{}->x+ Concat{l=ll,r=lr}+ |size lr<ratio*size ll -> singleR x+ |otherwise -> doubleR x++++singleL (a@String{})=a+singleL (b@Concat{})=+ case r b of+ d@Concat{}->+ let b'=append (l b) (l d)+ {- Concat { length_=(length $ l b)+(length $ l d),+ sizeC=(size $ l b)+(size $ l d)+1,+ l=l b,+ r=l d } -}+ in+ Concat { length_=length b,+ sizeC=size b,+ r=r d,+ l=b' }+ + _->b++singleR (d@Concat{})=+ case l d of+ b@Concat{}->+ let d'=append (r b) (r d)+ {- Concat { length_=(length $ r b)+(length $ r d),+ sizeC=(size $ r b)+(size $ r d)+1,+ l=r b,+ r=r d } -}+ in+ Concat { length_=length d,+ sizeC=size d,+ r=d',+ l=l b }+ _->d+singleR a=a+ ++doubleL (a@Concat{})=singleL $ a { l=singleR $ l a }+doubleL a=a+doubleR (a@Concat{})=singleR $ a { r=singleL $ r a }+doubleR a=a++\end{code}++Unsafe Stuff++\begin{code}++foreign import ccall unsafe "string.h memchr" memchr::Ptr Word8->Word8->CSize->IO (Ptr Word8)+foreign import ccall unsafe "string.h strncmp" strncmp::Ptr Word8->Ptr Word8->CSize->IO CInt++{-# INLINE inlinePerformIO #-}+inlinePerformIO::IO a->a+#ifdef __GLASGOW_HASKELL__+inlinePerformIO (IO m)=case m realWorld# of (# _, r #)->r+#else+inlinePerformIO=unsafePerformIO+#endif++\end{code}++Indexing Ropes++\begin{code}++-- | O(log n) returns the 'Word8' at given index in the 'Rope'+index::Rope->Int->Char+index c i+ |i>=length c = error $ "index trop grand : "++(show i)++", longueur = "++(show $ length c)+ |otherwise=index_ c i+ where + index_ (String{contents,offset}) i_=+ inlinePerformIO $ withForeignPtr contents $ + \con->do+ x<-peek $ plusPtr con (offset+i_) :: IO Word8+ return $ toEnum $ fromIntegral x+ index_ (Concat{r,l}) i_+ |i_>=length l = index_ r (i_-length l)+ |otherwise = index_ l i_+++-- | O(n) returns the index of the first element equal to the query element. This implementation+-- uses memchr at leaves, and explores the rope in parallel (with 'GHC.Conc.par').++elemIndex::Word8->Rope->Maybe Int+elemIndex w rope=+ elemIndex_ 0 rope+ where+ elemIndex_ i (String{contents,offset,length_})=+ inlinePerformIO $ withForeignPtr contents $ \con->do+ ptr<-memchr (con`plusPtr`offset) w (fromIntegral length_)+ return $ if ptr==nullPtr then Nothing else Just $ i+offset+(ptr`minusPtr`con)+ + elemIndex_ i (Concat{l,r})=+ let sl=elemIndex_ i l+ sr=elemIndex_ (i+length l) r+ in+ (sl`par`sr)`seq`(if isNothing sl then sr else sl)+ ++-- | O(n) Same as 'elemIndex', but explores the 'Rope' sequentially. Useful for+-- 'Rope's loaded lazily with 'readFile'.++elemIndex'::Word8->Rope->Maybe Int+elemIndex' w rope=+ elemIndex_ 0 rope+ where+ elemIndex_ i (String{contents,offset,length_})=+ inlinePerformIO $ withForeignPtr contents $ \con->do+ ptr<-memchr (con`plusPtr`offset) w (fromIntegral length_)+ return $ if ptr==nullPtr then Nothing else Just $ i+offset+(ptr`minusPtr`con)+ + elemIndex_ i (Concat{l,r})=+ case elemIndex_ i l of+ Nothing->elemIndex_ (i+length l) r+ a->a++-- | O(n) returns the list of all positions where the queried elements occurs in the 'Rope'.+-- This implementation uses memchr.++elemIndices::Word8->Rope->[Int]+elemIndices w rope=+ elemIndices_ 0 rope []+ where+ -- loop est une action IO, avec le foreignPtr deja enleve.+ -- Autant dire que ca va tres vite.+ loop::Ptr Word8->CInt->CSize->[Int]->IO [Int]+ loop _ _ 0 l=return l+ loop ptr i len l=do+ ptr'<-memchr ptr w len+ if ptr'==nullPtr then return [] else do+ let off=fromIntegral $ ptr'`minusPtr`ptr+ x<-loop (ptr'`plusPtr`1) (i+off+1) (len-fromIntegral off-1) l+ return $ (fromIntegral $ i+off):x+ + + elemIndices_ i (String{contents,offset,length_}) list=+ inlinePerformIO $ withForeignPtr contents $ \con->+ loop (con`plusPtr`offset) i (fromIntegral length_) list+ + elemIndices_ i (Concat{l,r}) list=+ let sl=elemIndices_ i l sr+ sr=elemIndices_ (i+(fromIntegral $ length l)) r list+ in+ sl++\end{code}++Reducing++\begin{code}++-- | O(n). fold over a 'Rope'.+-- This implementation is not tail-recursive but never pushes more than+-- O(log n) calls on the stack.++foldl::(a->Word8->a)->a->Rope->a+foldl f a (String {contents,offset,length_})=+ unsafePerformIO $ withForeignPtr contents $+ \c->foldlBuf f a (c`plusPtr`offset) length_+ +foldl f a (Concat{l,r})=foldl f (foldl f a l) r++foldlBuf::(a->Word8->a)->a->Ptr Word8->Int->IO a+foldlBuf _ a _ 0=return a+foldlBuf f a p l=do+ c<-peek p+ foldlBuf f (f a c) (p`plusPtr`1) (l-1)++-- | O(n). like 'foldl' but strict.++foldl'::(a->Word8->a)->a->Rope->a+foldl' f a (String {contents,offset,length_})=+ unsafePerformIO $ withForeignPtr contents $+ \c->foldlBuf' f a (c`plusPtr`offset) length_+ +foldl' f a (Concat{l,r})=+ let b=foldl' f a l in b`seq`(foldl' f b r)++foldlBuf'::(a->Word8->a)->a->Ptr Word8->Int->IO a+foldlBuf' _ a _ 0=return a+foldlBuf' f a p l=do+ c<-peek p+ let b=f a c+ b`seq`foldlBuf' f b (p`plusPtr`1) (l-1)+ ++-- | O(n). Right fold. Again not tail-recursive but never uses more than+-- O(log n) on the stack.+foldr::(Word8->a->a)->a->Rope->a+foldr f a (String{contents,offset,length_})=+ unsafePerformIO $ withForeignPtr contents $ + \p->foldrBuf f a (p`plusPtr`offset) length_++foldr f a (Concat{l,r})=foldr f (foldr f a r) l++foldrBuf::(Word8->a->a)->a->Ptr Word8->Int->IO a+foldrBuf _ a _ 0=return a+foldrBuf f a p l=do+ c<-peek $ p`plusPtr`(l-1)+ foldrBuf f (f c a) p (l-1)++\end{code}++Breaking Ropes++\begin{code}++take::Int->Rope->Rope+take i (s@String{length_})=s { length_=min length_ i }+take i (c@Concat{l,r})+ | i==length l = l+ | i<length l = take i l+ | otherwise = c { r=take (i-length l) r }++drop::Int->Rope->Rope+drop i (s@String{offset,length_})=s { offset=offset+(min i length_) }+drop i (c@Concat{l,r})+ | i==length l = r+ | i<length l = c { l=drop i l }+ | otherwise = drop (i-length l) r++splitAt# ::Int->Rope->(# Rope,Rope #)+splitAt# i (s@String{offset,length_})+ | i>=length_ = (# s,empty #)+ | otherwise = (# s { length_=i }, s { offset=offset+i,length_=length_-i} #)+splitAt# i (c@Concat{length_=l0,l,r})+ | i>=l0 = (# c,empty #)+ | i>=length_ l =+ let (# u,v #)=splitAt# (i-length_ l) r in+ (# c { length_=i, r=u }, v #)+ | otherwise = + let (# u,v #)=splitAt# i l in+ (# u, c { length_=i-length_ u, l=v } #)++-- | O(log n). @'splitAt' n xs@ is equivalent to (take n xs, drop n xs), but a little faster.+splitAt::Int->Rope->(Rope,Rope)+splitAt i r=+ let (# u,v #)=splitAt# i r in+ (u,v)++-- | O(n). @'breakByte' c r@ breaks 'Rope' @r@ before the first occurence of @c@.+breakByte::Word8->Rope->(Rope,Rope)+breakByte w rope_=+ let (_,b,c)=breakByte_ rope_ in+ (b,c)+ where+ breakByte_::Rope->(Bool,Rope,Rope)+ breakByte_ x@(String{contents,offset,length_})=+ inlinePerformIO $ withForeignPtr contents $ \con->do+ ptr<-memchr (con`plusPtr`offset) w (fromIntegral length_)+ return $ if ptr==nullPtr then (False, x, empty) else+ (True,+ x { length_=length_-(ptr`minusPtr`con)-1 }, + x { offset=offset+(ptr`minusPtr`con) })+ + breakByte_ (Concat{l,r})=+ case breakByte_ l of+ (True,x,y)->(True,x,append y r)+ (False,x,_)->+ case breakByte_ r of+ (True,x',y')->(True,append x x',y')+ u@(False,_,_)->u++-- | O(n). @'breaks' w r@ breaks 'Rope' @r@ between each occurence of @w@ (non-inclusive).+-- This function is not tail-recursive, uses @memchr@ and constructs the list in parallel+-- using @'par'@.+ +breaks::Word8->Rope->[Rope]+breaks w rope_=+ let (a,_)=lines_ True rope_ in+ a+ where+ lines_::Bool->Rope->([Rope],Maybe Rope)+ lines_ isLast (str@String{contents,offset,length_})=+ if length_<=0 then ([],Nothing) else+ let off=inlinePerformIO $ withForeignPtr contents $ \con->do+ let pcon=con`plusPtr`offset+ ptr<-memchr pcon w (fromIntegral length_)+ if ptr==nullPtr then return Nothing else return $ Just (ptr`minusPtr`pcon)+ in+ case off of+ Nothing-> -- traceShow ("str",isLast, str) $ + if isLast then + if length str>0 then ([str],Nothing) else ([],Nothing)+ else ([], Just str)+ Just diff->+ let line=str { length_=diff }+ (a,b)=lines_ isLast (str{ offset=offset+diff+1,+ length_=length_-diff-1})+ in+ -- traceShow ("line",line:a,b) $+ (line:a,b)+ + lines_ isLast (Concat{l,r})=+ let (ll,x)=lines_ False l+ (lr,y)=lines_ isLast r+ in+ (ll`par`lr)`seq`+ (case lr of+ []->case (x,y) of+ (Just xx, Just yy)->(ll,Just $ append xx yy)+ (Just _, Nothing)->(ll, x)+ (Nothing, _)->(ll, y)+ + h:s->case x of { Nothing->(ll++lr,y); Just xx->(ll++((append xx h):s), y) }+ )+ +-- | O(n). Satisfies @lines r == breaks 0x0a r@.+lines::Rope->[Rope]+lines r=breaks 0x0a r+++\end{code}++Input and Output++\begin{code}++-- | Writes the contents of the 'Rope' on the specified 'Handle'.+hPut::Handle->Rope->IO()+hPut h (String{contents,offset,length_})=+ withForeignPtr contents $ \c->hPutBuf h (c`plusPtr`offset) length_+hPut h (Concat{l,r})=do+ hPut h l+ hPut h r++-- | synonym for 'hPut'.+hPutStr::Handle->Rope->IO()+hPutStr=hPut++-- | like 'hPut', but with a newline character at the end of the output+hPutStrLn::Handle->Rope->IO()+hPutStrLn handle r=do+ hPut handle r+ hPutChar handle '\n'+ +-- | Writes the contents of the 'Rope' on the standard output.+putStr::Rope->IO()+putStr=hPutStr stdout+ +-- | like 'putStr' but with a newline character at the end of the output+putStrLn::Rope->IO()+putStrLn=hPutStrLn stdout+ +-- | fromPtr encapsule un pointeur, un offset et une longueur dans un @Rope@..+fromPtr::ForeignPtr Word8->Int->Int->IO Rope+fromPtr fp offset s+ | s<=leafSize = withForeignPtr fp $ \p->do+ contents<-mallocForeignPtrBytes leafSize+ withForeignPtr contents $ \c->copyArray c (p`plusPtr`offset) s+ + i0<-mallocForeignPtr+ withForeignPtr i0 $ \i->poke i s+ + return $ String { contents,i0,offset=0,length_=s }++ | otherwise = do+ let sl=s`shiftR`1+ sr=sl+s.&.1+ sz=ceiling $ ((fromIntegral s)/(fromIntegral leafSize) :: Double)+ l<-unsafeInterleaveIO $ fromPtr fp offset sl+ r<-unsafeInterleaveIO $ fromPtr fp (offset+sl) sr+ return $ Concat { l,r,length_=s, sizeC=2*sz-1 }++-- | O(n) Conversion from a strict 'ByteString'+fromByteString::B.ByteString->Rope+fromByteString b=+ let (fp,off,len)=B.toForeignPtr b in+ unsafePerformIO $ fromPtr fp off len++-- | O(n) Conversion to a strict 'ByteString'+toByteString::Rope->B.ByteString+toByteString (String{contents,offset,length_})=+ B.fromForeignPtr contents offset length_+ +toByteString (c@Concat{length_=len})=+ B.unsafeCreate len $ \ptr->fill ptr c+ where+ fill p (Concat{l,r})=do+ fill p l+ fill (p`plusPtr`(length_ l)) r+ fill p (String{contents,offset,length_})=+ withForeignPtr contents $ \cc->copyBytes p (cc`plusPtr`offset) length_+ ++-- | Lazy file reading, using @mmap@.+ +readFile::FilePath->IO Rope+readFile file=do+ stat<-getFileStatus file+ let s=fromIntegral $! fileSize stat+ fd<-openFd file ReadOnly Nothing $ defaultFileFlags+ p<-c_mmap s (fromIntegral fd)+ fp<-FC.newForeignPtr p $ do+ _<-c_munmap p s+ closeFd fd+ fromPtr fp 0 (fromIntegral s)++++-- | Strict hGet. The whole rope is constructed.+hGet::Handle->Int->IO Rope+hGet handle length_=do+ position<-hTell handle+ buildRope handle position length_+ +buildRope::Handle->Integer->Int->IO Rope+buildRope handle position len+ | len<=leafSize = do+ + contents<-mallocForeignPtrBytes leafSize+ length_<-withForeignPtr contents $ \c->do+ hSeek handle AbsoluteSeek position+ hGetBuf handle c len+ + i0<-mallocForeignPtr+ withForeignPtr i0 $ \i->poke i len++ + return $ String {contents,length_,offset=0,i0 }+ + | otherwise =+ let a=len`shiftR`1+ b=a+(len.&.1)+ in do+ aa<-buildRope handle position a+ bb<-buildRope handle (position+fromIntegral a) b+ return $ Concat { length_=len,l=aa,r=bb,sizeC=size aa+size bb }+ +-- | Returns the next line in the input 'Handle'. If you need to iterate 'hGetLine',+-- it may be more efficient to first @mmap@ the file using 'readFile', or even load+-- it with then iterate+-- @'breakByte' 0x0a@ : 'hGetLine' allocates a buffer to read the file+-- and may waste most of this space if the lines are shorter than the standard buffer+-- size of this module.+hGetLine::Handle->IO Rope+hGetLine h=+ hGetLine' empty+ + where+ hGetLine' x=do+ contents<-mallocForeignPtrBytes leafSize+ withForeignPtr contents $ \con->do+ l<-hGetBuf h con leafSize+ let readBytes=min l leafSize+ if readBytes<=0 then return x else do+ ptr<-memchr con 0x0a (fromIntegral readBytes)+ if ptr==nullPtr then do+ i0<-mallocForeignPtr+ withForeignPtr i0 $ \i->poke i readBytes+ let y=String { contents,i0,offset=0,length_=readBytes }+ hGetLine' (x`append`y)+ + else do+ + i0<-mallocForeignPtr+ let lineLen=ptr`minusPtr`con+ y=String { contents,i0,offset=0,length_=lineLen }+ withForeignPtr i0 $ \i->poke i lineLen+ hSeek h RelativeSeek (fromIntegral $ lineLen-readBytes+1)+ return $ x`append`y+ +-- | Reads the contents of a file handle strictly, then closes it.++hGetContents::Handle->IO Rope+hGetContents h=finally (hGetContents' empty) (hClose h)++ where+ hGetContents' r=do+ contents<-mallocForeignPtrBytes leafSize+ withForeignPtr contents $ \l->do+ x<-hGetBuf h l leafSize+ i0<-mallocForeignPtr+ withForeignPtr i0 $ \i->poke i x+ let y=String { contents,i0,offset=0,length_=x }++ if x==0 then return r else+ if x<leafSize then return $ r`append`y else+ hGetContents' $ r`append`y+\end{code}+
+ LICENSE view
@@ -0,0 +1,340 @@+ GNU GENERAL PUBLIC LICENSE+ Version 2, June 1991++ Copyright (C) 1989, 1991 Free Software Foundation, Inc.+ 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA+ Everyone is permitted to copy and distribute verbatim copies+ of this license document, but changing it is not allowed.++ Preamble++ 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 Library General Public License instead.) You can apply it to+your programs, too.++ 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.++ 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.++ 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 Library General+Public License instead of this License.
+ Setup.hs view
@@ -0,0 +1,3 @@+import Distribution.Simple++main=defaultMain
+ data-rope.cabal view
@@ -0,0 +1,18 @@+Name: data-rope+Version: 0.3+Synopsis: Ropes, an alternative to (Byte)Strings.+Description: Ropes : an alternative to Strings,+ a time and space-efficient representation of character+ strings.+Category: Data+Maintainer: Pierre-Etienne Meunier <pierreetienne.meunier@gmail.com>+License: GPL+License-file: LICENSE+Build-Type: Simple+Cabal-Version: >=1.6+source-repository head+ type: darcs+ location: http://www.lama.univ-savoie.fr/~meunier/darcs/data-rope+Library+ Build-Depends: base<5, bytestring-mmap, bytestring, unix+ Exposed-modules: Data.Rope