Arbitrary Annotations over rope

[ChrisPenner]

Hey there folks; Chris from Rasa here;

I've been toying with an idea lately, it's a little long winded but I'm curious to hear your thoughts on it. I've been fiddling around with some ideas to allow me to annotate Text in the Rasa text editor with arbitrary tags efficiently. Some examples of tags would be the color to display the text, whether it's highlighted or selected, etc. I want to keep the annotations with the text itself (in the rope) so that as text is mutated and moved around the annotations stay in sync for the most part. The plan is to store them directly in the rope so that alongside the T.Text in the rope there's also an arbitrary a which holds annotations about the current chunk. For instance one example could be:

data SelectStatus = Selected | UnSelected
  deriving (Show, Eq)

-- Here's a `Chunk SelectStatus` with its annotation
Chunk { chunkSize=5
, _fromChunk="hello"
, _annotation=Selected
}

From here the traditional Rope tooling works exactly the same, but we can provide special instances of Measured for the underlying FingerTree to track info about the annotations as well.

For instance one thing I'd like to do is group all the text in a buffer into a list grouped by consecutive selected or unselected chunks. Traditionally you'd do this with a groupBy, but this would be O(n) where n is number of chunks over this tree; we can utilize the measure of the tree to get this number down.

Here's a Monoid which tracks accumulates the count of times the SelectStatus changes, which
provides a monotonically increasing accumulation which we can leverage in the FingerTree to do
efficient groupings of the underlying chunks;

-- | 'Flux' is a monoid which counts the number of times an element changes
-- values (according to its Eq instance)
-- This is useful for gaining associativity (and its associated performance improvements)
-- for tasks where you'd otherwise use `group` or `groupBy`
data Flux a = Flux
  -- We keep track of the last value we saw on the left and right sides of the accumulated
  -- sequence; `Nothing` is used in the identity case meaning no elements have yet
  -- been encountered
  { sides :: Maybe (a, a)
  -- We have a counter which increments each time we mappend another Flux who's
  -- left doesn't match our right or vice versa depending on which side it is mappended onto.
  , getFlux :: Int
  } deriving (Show, Eq)


-- | Embed a single value into a Flux;
-- number of changes starts at 0.
flux :: a -> Flux a
flux a = Flux (Just (a, a)) 0

instance (Eq a) => Monoid (Flux a) where
  mempty = Flux Nothing 0
  Flux Nothing _ `mappend` f = f
  f `mappend` Flux Nothing _ = f
  Flux (Just (l, r)) n `mappend` Flux (Just (l', r')) n'
    | r == l' = Flux (Just (l, r')) (n + n')
    | otherwise = Flux (Just (l, r')) (n + n' + 1)

-- Now that it's set up, we can try it out!

-- > getFlux $ foldMap flux ["a", "b", "b", "a"]
-- 2
-- > getFlux $ foldMap flux ["a", "b", "b", "a", "c", "c", "c"]
-- 3

Now we can leverage this against a FingerTree to get the desired chunked list:

-- Instance of measured which carries the Flux Monoid in addition to Size
instance Measured (Flux SelectStatus, Size) (Chunk SelectStatus) where
  measure (Chunk sz txt annotation) = (flux annotation, Size sz (countNewLines txt))

mkChunk :: T.Text -> a -> Chunk a
mkChunk txt ann = Chunk (T.length txt) txt ann

groupTree :: FingerTree (Flux SelectStatus, Size) (Chunk SelectStatus) -> [(T.Text, SelectStatus)]
groupTree tree =
  case split ((>0) . getFlux . fst) tree of
    (FT.null -> True, _) -> []
    (grouped, rest) -> foldr1 collapse grouped : groupTree rest
  where
    collapse (Chunk _ txt ann) (Chunk _ txt' _) = (txt <> txt', ann)

Now we can collect cohesive chunks of text according to some criteria:

someText :: FingerTree (Flux SelectStatus, Size) (Chunk SelectStatus)
someText = fromList [mkChunk "selected!" Selected,  mkChunk "not selected" UnSelected, mkChunk "yup" Selected, mkChunk ", am selected" Selected]

-- Try it out:
> groupTree someText
[("selected!", Selected), ("not selected", Unselected), ("yup, am selected", Selected)]

Not necessarily suggesting this gets added to yi-rope, but I think there's potential for this to be pretty useful. It does make simple things like inserting text require either a default value for the annotation or for one to be provided. A version of rope without any annotations would of course still need to exist.

Regardless I'll probably be forking yi-rope to add this functionality if only for use in Rasa, so I figured I'd check in with you folks to see what you think and whether you have any ideas or tips.

Of course this wouldn't be limited to the Flux Monoid over the annotations, it would just be nice to be able to track arbitrary annotations.

Performance would be very slightly negatively affected, since chunks MUST be split whenever one of the annotations changes values, but I don't think it would be noticeable unless your annotation alternates extremely often.

Cheers!

[Fuuzetsu]

I don't know how to unmark github notification; please ping me and I'll get back to you this weekend

[ChrisPenner]

Sorry; a little late on the ping. Cheers! @Fuuzetsu

[Fuuzetsu]

I think it'd be OK to have YiChunk a in this package; default use then just becomes YiChunk () and YiString () which should have no real overhead. We can add SPECIALIZE pragmas for that case too. Constraint would be Monoid a for mempty. You can then write groupTree in rasa (possibly with extra exports from yi-rope so you can get at the guts).