Yi.Rope

This module defines a rope data structure for use in Yi. This specific implementation uses a fingertree over Text.

In contrast to our old implementation, we can now reap all the benefits of Text: automatic unicode handling and blazing fast implementation on underlying strings. This frees us from a lot of book-keeping. We don't lose out on not using ByteString directly because the old implementation encoded it into UTF8 anyway, making it unsuitable for storing anything but text.

Documentation

data YiString

A YiString is a FingerTree with cached column and line counts over chunks of Text.

Instances

Eq YiString

Show YiString

IsString YiString

Binary YiString

To serialise a YiString, we turn it into a regular String first.

NFData YiString

Conversions to YiString

fromString :: String -> YiString

See fromText.

fromText :: Text -> YiString

Converts a Text into a YiString using defaultChunkSize-sized chunks for the underlying tree.

fromString' :: Int -> String -> YiString

See fromText'.

fromText' :: Int -> Text -> YiString

This is like fromText but it allows the user to specify the chunk size to be used. Uses defaultChunkSize if the given size is <= 0.

Conversions from YiString

toString :: YiString -> String

See toText.

toReverseString :: YiString -> String

See toReverseText.

toText :: YiString -> Text

Consider whether you really need to use this!

toReverseText :: YiString -> Text

Spits out the underlying string, reversed.

Note that this is actually slightly faster than manually unrolling the tree from the end, reverseing each chunk and concating, at least with -O2 which you really need to be using with Text anyway.

List-like functions

null :: YiString -> Bool

Checks if the given YiString is actually empty.

empty :: YiString

Creates an empty YiString.

take :: Int -> YiString -> YiString

Takes the first n given characters.

drop :: Int -> YiString -> YiString

Drops the first n characters.

length :: YiString -> Int

Length of the whole underlying string.

Amortized constant time.

reverse :: YiString -> YiString

Reverse the whole underlying string.

This involves reversing the order of the chunks as well as content of the chunks. We use a little optimisation here that re-uses the content of each chunk but this exposes a potential problem: after many transformations, our chunks size might become quite varied (but never more than the default size), perhaps we should periodically rechunk the tree to recover nice sizes?

countNewLines :: YiString -> Int

Count the number of newlines in the underlying string. This is actually amortized constant time as we cache this information in the underlying tree.

lines :: YiString -> [YiString]

This is like lines' but it does *not* preserve newlines.

Specifically, we just strip the newlines from the result of lines'.

This behaves slightly differently than the old split: the number of resulting strings here is equal to the number of newline characters in the underlying string. This is much more consistent than the old behaviour which blindly used ByteStrings split and stitched the result back together which was inconsistent with the rest of the interface which worked with number of newlines.

lines' :: YiString -> [YiString]

Splits the YiString into a list of YiString each containing a line.

Note that in old implementation this allowed an arbitrary character to split on. If you want to do that, manually convert toText and use splitOn to suit your needs. This case is optimised for newlines only which seems to have been the only use of the original function.

The newlines are preserved so this should hold:

'toText' . 'concat' . 'lines'' ≡ 'toText'

but the underlying structure might change: notably, chunks will most likely change sizes.

splitAt :: Int -> YiString -> (YiString, YiString)

Splits the string at given character position.

If position <= 0 then the left string is empty and the right string contains everything else.

If position >= length of the string then the left string contains everything and the right string is empty.

Implementation note: the way this works is by splitting the underlying finger at a closest chunk that goes *over* the given position (see split). This either results in a perfect split at which point we're done or more commonly, it leaves as few characters short and we need to take few characters from the first chunk of the right side of the split. We do precisely that.

All together, this split is only as expensive as underlying split, the cost of splitting a chunk into two and the cost consing and snocing one chunk to each string. As the chunks are short, the split fairly cheap and cons/snoc constant time, this turns out pretty fast all together.

splitAtLine :: Int -> YiString -> (YiString, YiString)

Splits the underlying string before the given line number. Zero-indexed lines.

Splitting at line <= 0 gives you an empty string. Splitting at n > 0 gives you the first n lines.

Also see splitAtLine'.

append :: YiString -> YiString -> YiString

Append two YiStrings.

concat :: [YiString] -> YiString

Concat a list of YiStrings.

IO

readFile :: FilePath -> IO YiString

writeFile :: FilePath -> YiString -> IO ()