Content with multiple carets/selections

Multi-Caret-Selection-TextContent.purs

module Something where

-- Let's say we have a content type, like a String
type Content = String

{-
Now let's say we want to add a cursor/caret to that data type
so that we can add/remove characters to the String at
the position of that cursor.

We don't want to use store both the content and a position/index that
represents where in that data structure our cursor is because we don't have a type
whose instance is always within the bounds of the content/data structure:
-}
type IndexOutOfBoundsExample = { content :: Content, cursorPos :: Int }
-- cursorPos < 0 == runtime exception
-- (length content) < cursorPos == runtime exception

-- So, we choose to model our cursor position within the data type itself:

type ContentWithCursor =
  { before :: Content -- reversed
  , after :: Content
  }

-- Syntax: '|' represents the caret
"abcd|efgh" == { before: "dcba", after: "efgh"}

{-
Great! However, now we want to have multiple cursors
so that we can add/remove characters at various points in the content
at the same time. How might we do this?
-}
-- Syntax: '^' represents the first caret
-- Syntax: '*' represents the second caret
"ab^cdef*gh" = { before: "ba"
               , middle: "cdef"
               , after: "gh"
               }
"ab*cdef^gh" = { before: "ba"
               , middle: "cdef"
               , after: "gh"
               }
"abc^*defgh" = { before: "cba"
               , after: "defgh"
               }

{-
Hmm... At least two problems arise:
1. The first and second examples don't let us distinguish between
    which caret is which. If we want to add at one place and delete at another,
    at which point would we do the addition and the deletion?
2. When both carets are at the same place, it looks no different than
    when we have just one caret.

Putting this into different terms, we should be able to
- distinguish between two carets when they are at two separate positions
within the content AND when they share the same position.

Ideally, we'd distinguish between two carets by referring to their names,
which should be unique to the data structure.

We'll start by solving the first half (when they are in two separate positions)
We'll re-use the same data structure we used from the selection code
but call it by its real name: PointedList.
-}
type CaretName = String
newtype Caret = Caret CaretName -- name of caret
type PointedList beforeAfter focus =
  { before :: beforeAfter
  , focus :: focus
  , after :: beforeAfter
  }

type Content = String -- the normal content
type Caret = String -- An empty string == a caret

-- This should look familiar:
-- PointedList String Caret
"|"                   == { before: "", focus: Caret "caret-name", after: "" }
"a" | "b"             == { before: "a", focus: Caret "caret-name", after: "b" }

-- When we want to add another caret, we
-- - nest a PointedList within another PointedList at the outer one's "focus" field
-- - flip the `beforeAfter` and `focus` types of the inner PointedList

-- PointedList String (PointedList Caret String)
"a" | "b" | "c"       == { before: "a"
                         , focus: { before: Caret "first"
                                    , focus: "b"
                                  , after: Caret "second"
                                  }
                         , after: "c"
                         }
-- We can also handle situations where one caret is at the end but
-- another is not. Note: this only works because String can be a Monoid.
| "a" | "b"
-- is the same as...
"" | "a" | "b"        == { before: "" -- empty content
                         , focus:
                            { before: Caret "first"
                               , focus: "a"
                            , after: Caret "second"
                            }
                         , after: "b"
                         }

-- Before going any further, let's determine what the type of
-- these instances should be.

-- If first/last content surrounds all carets, we start with the pointed list...
-- PointedList BeforeAfter_OutsideType Focus_InsideType
"a|b"       == PointedList Content Caret
"a|b|c"     == PointedList Content (PointedList Caret Content)
"a|b|c|d"   == PointedList Content (PointedList Caret (PointedList Content Caret)))
"a|b|c|d|e" == PointedList Content (PointedList Caret (PointedList Content (PointedList Caret Content)))

"|a|"       == PointedList Caret Content
"|a|b|"     == PointedList Caret (PointedList Content Caret)
"|a|b|c|"   == PointedList Caret (PointedList Content (PointedList Caret Content))
"|a|b|c|e|" == PointedList Caret (PointedList Content (PointedList Caret (PointedList Content Caret)))

-- Which leads to a recursive data type
-- This is the clearer version
data RecursiveFlip a b
  = Final (PointedList' a b a)
  | Recursive (PointedList' a (RecursiveFlip b a) a)

-- This is the compressed version
newtype RecursiveFlip a b
  = RecursiveFlip (PointedList' a (Either b (RecursiveFlip b a)) a)

-- Since we can start with either one depending on which we're using,
-- we'll use an Either to represent this:
type ContentWithMultiCarets =
    Either (RecursiveFlip Content Caret) (RecursiveFlip Caret Content)

-- Looking at our examples again using the compressed version...
"|"                   == Left { before: "", focus: Caret "caret-name", after: "" }
"a" | "b"             == Left { before: "a", focus: Caret "caret-name", after: "b" }
"a" | "b" | "c"       == Left { before: "a"
                         , focus: Left { before: Caret "first"
                                         , focus: "b"
                                       , after: Caret "second"
                                       }
                         , after: "c"
                         }
"a" | "b" | "c" | "d" == Left { before: "a"
                         , focus: Right { before: Caret "first"
                                         , focus: Left { before: "b"
                                                       , focus: Caret "second"
                                                       , after: "c"
                                                       }
                                       , after: Caret "third"
                                       }
                         , after: "d"
                         }
{-
This seems to satisfy the first condition.

Let's continue with the second condition: when two carets share the same
location. Our solution still needs to guarantee that we can distinguish
one caret from another. To support this, we need to use a set-like type

In addition, we should store a set of all the caret names used in
a given content to insure we aren't adding a name that is already somewhere
in the document. This set should not be empty.
-}
data MultiCaret = MultiCaret (NonEmpty Set Caret)

type ContentWithMultiCarets =
    Either (RecursiveFlip Content MultiCaret) (RecursiveFlip MultiCaret Content)

-- Guarantees that there is always at least one caret somwhere in the document
newtype Checked_MultiCaretDocument = Checked_MultiCaretDocument
  { allCarets :: NonEmpty Set Caret
  , content :: MultiCaretDocument
  }

{-
Adding a caret will check whether the name already exists in the set
and if so, will add it to the correct position

Removing a caret will check whether the name already exists in the set
and if so, will remove it from the correct spot

We have now defined a type that
- can store content
- can have multiple carets
    - that are at always-valid positions within that content
    - that can be distinguished from one another by unique names
    - that can be at the same position as 0 or more other carets.
    - that enables easily adding/removing carets freely.

-}

--
--
-- SELECTION
--
--

{-
Great! Now let's add the ability to select content within the document
using this type. So, we have either a caret or a selection,
but we can't have both at the same time. How might we do this?

A selection should store the content which it selects and tag that
part with its name. In the case of a caret, we can use an empty selection.

Starting from a much simpler example where there is only one caret/selection:
-}

-- Syntax: '|' represents the caret
-- Syntax: '[selection]' represents a selection
"abcd|efgh" == { before: "dcba", selection: "", after: "efgh"}
"abc[de]fgh" == { before: "cba", selection: "de", after: "fgh"}

-- To support this, we need to augment our Caret type to include content
-- Since this can be both a caret/selection, we'll rename it as such
type Content = String
type CSName = String
type CaretSelection
  = { name :: String
    , content :: Content
    }

{-
Similarly, we should be able to have two selections within the same content
at the same time.
-}

-- Syntax: '|' represents a caret
-- Syntax: '[selection1]' represents the first selection
-- Syntax: '{selection2}' represents the second selection

-- These situations can be done easily enough...
  -- Two carets that are not overlapping
  "ab" | "cdefg" | "hijklmnopqr" -- and vice versa
  -- Two selections that are not overlapping
  "a" [ "bc" ] "d" { "efghijkl" } "mnopqr" -- and vice versa
  -- a caret and a selection that are not overlapping
  "ab" | "cd" { "efghijkl" } "mnopqr" -- and vice versa

-- However, these selections present a problem....
  -- selection inside a selection
  "abcd" { "efg" [ "hi" ] "jkl" } "mnopqr" -- and vice versa
  -- a caret inside a selection
  "abcd" { "efgh" | "ijkl" } "mnopqr"
  -- one selection shares a portion of the other
  "ab" [ "cd" { "efg" ] "hijkl" } "mnopqr" -- and vice versa

{-
The problem with two selections overlapping or containing one another
is that it risks the chance of duplicating data. If one selection
deletes or adds something and another one does not, the content's
state might get out of sync between the two.

So, how do we solve this problem now?

Essentially, we're storing 4 things
- the name of the caret/selection, which distinguishes it from other caret/selection
- the boundaries of the selection: where it starts and ends
- the content of a selection, whether that be the entire thing or a fragment
    (this is no different from the caret as before)

Lastly, we can also store the "type" of a selection:
  - A selection can be bound to a caret, such that one boundary is the caret
      and the other boundary (the anchor) is where the caret initially was
      when the selection started. When "resizing" the selection,
      one only moves the caret whereas the anchor stays put.
      - In this situation, the direction of the selection (whether
        the caret starts or ends the selection) matters.
  - A selection unbounded by a caret, such that each boundary
      is independent from another. When "resizing" the selection,
      one can move either boundary.


If we map each one of these things on a new 'plane', we can see their interaction
-}
"a b c d e f g h i j k l" -- Text
" [   <   {     }   > ]"  -- Selections & their boundaries
" a   _   c     a   _ c"  -- anchor/caret or unbounded

-- Encoding this as an instance of a pseudo type, we get this:
"a"
  [ { "bc", [bounded1-frag-start-caretEnds] }
  , { "de", [bounded1-frag-middle, unbounded-frag-start] }
  , { "fgh", [ bounded1-frag-middle, unbounded-frag-middle
             , bounded2-whole-caretStarts
             ] }
  , { "ij", [bounded1-frag-middle, unbounded-frag-end] }
  , { "k", [bounded1-frag-end-caretEnds] }
  ]
"l"

{-
We are essentially "tagging" some content with positional info
This "positional info" is a collection of the 4 things above. However,
how should we define our types so as to make impossible states impossible?

Let's define 3 properties:
- In certain circumstances, a caret can become a bounded selection
- In certain circumstances, a bounded selection can become a Caret
- In all circumstances, an unbounded selection must always remain an unbounded selection
    This is to prevent an unbounded selection that selects nothing from becoming
    a caret or from defining how a selection's boundary should be updated.

In other words,
  if
    "=>" means "can transform into"
    "/=>" means "can never transform into"

    "bs_start" means "bounded selection, caret starts"
    "bs_end" means "bounded selection, caret ends"

  then
    // when caret is moved and anchor is not dropped
    caret => caret

    // when caret is moved and anchor is dropped
    caret => bs_start
    caret => bs_end

    // when caret is moved but the boundaries have not swapped
    bs_end   => bs_end
    bs_start => bs_start

    // when caret is moved to the anchor
    bs_end   => caret
    bs_start => caret

    // when caret is moved beyond the anchor
    bs_end   => bs_start
    bs_start => bs_end

    // when one of its boundaries is moved
    unbounded selection => unbounded selection

    // a list of impossible states
    unbounded selection /=> caret
    unbounded selection /=> bs_end
    unbounded selection /=> bs_start

In addition, we need to define one other property to make
impossible states impossible:

- This is the ideal fragmented selection 'layout':
      selection "same name" fragmented Start
      selection "same name" fragmented Middle -- if needed
      ....
      selection "same name" fragmented Middle -- if needed
      selection "same name" fragmented End

(The following properties are explained and shown how they can break at runtime)

- Therefore, all instances of fragmented selections must
  1. share the same name
      selection fragmented "name1" start
      selection fragmented "name1" middle

      -- "name1" misspelled! we never know when the selection ends
      selection fragmented "name2" end

  2. maintain the start/middle/end order of a fragment
      selection fragmented "name1" start
      selection fragmented "name1" middle

      -- wrong fragment type used!
      selection fragmented "name1" start

- In addition, bounded fragmented selections must
  3. only store "caret starts" / "caret ends" once

      -- which boundary is the caret?
      selection "same name" caretStarts fragmented Start
      selection "same name" caretEnds fragmented End

Each of the three cases requires runtime checking to insure that a state is possible.

### CONCLUSION

Due to the possibility of overlapping selections, we can
  either duplicate the content and not duplicate the positional info
  or not duplicate the content and duplicate positional info.

As soon as the overlapping nature of selection is removed, it is possible
  to store the content and multiple carets/selections once and not
  risk data corruption.

Thus, we can make a choice that has different tradeoffs:
- Store the content and caret/selection positions separately
    Pros:
      - types are generally simpler
      - adding a new caret or selection is easy
    Cons:
      - runtime checking required to insure positions are within bounds
      - each position must be updated separately

- Store content and caret/selection positions as part of data structure
    Pros:
      - If using one caret/selection or multiple carets but no selections,
          compiler guarantees valid position
    Cons:
      - deals with more complicated types
      - potential performance decrease (supposed, but not verified)
          When moving caret to an absolute position within the content,
          data must be moved from one side to another. This may be
          expensive depending on the content's type. Moreover, if
          using multiple caret/selections, the code might need to
          go into and out of nested parts of the data structure
      - If using multiple caret/selections, only runtime can check positions
      - higher dimensions of content (e.g. 2D, 3D, etc.) might further
        reduce the performance of this concept.
-}