Collaborative Editor

Collaborative editor patterns that I try to code could be of many kinds. There are string manipulation algorithms, CRDTs and even LLM inference. So even though a full-fledged editor is not in scope here, many algorithms like these can be explored and a functional editor can be created.

The developing code is in this repository.

Please note that this is a random collection of algorithms that eventually could be part of a simple editor. There are too many books and papers that deal with a multitude of algorithms.

Terminal User Interface

These TUIs or terminal UIs are simpler than implementing an editor using UI toolkits like GTK or QT. Light weight TUIs are all the rage now because of their adoption by AI agents and other emulators like Ghostty and OpenTUI

I show here the simplest UI one could create using OCaml’s Format module which supports semantics tags.

image-title-here

open Types
open Buffer
open Format

(* https://hal.science/hal-01503081/file/format-unraveled.pdf *)
module type Widget = sig
    val render : Area.t  -> ?custom_formatter:Format.formatter -> Types.t-> unit
end

(* https://ocaml.org/manual/5.0/api/Format_tutorial.html#1_Refinementonhovboxes *)
module Widget = struct
   type Format.stag += Highlight

   let tui_stag_functions (area : Types.Area.t) = {
     Format.mark_open_stag = (fun stag ->
       match stag with
       | Format.String_tag s ->
                (match s with
                | s when String.equal s "Highlight"
                        ->   "\x1b[48;5;162m\x1b[38;5;255m";
                | _ -> String.empty)
       | _ -> String.empty
     );
     Format.mark_close_stag = (fun _ ->  "\x1b[0m");
     Format.print_open_stag = (fun _ -> ());
     Format.print_close_stag = (fun _ -> ());
   }

   let pp_linebreak ppf () = Format.pp_print_break ppf Format.pp_infinity 0

   let render_styled_text area =
     Format.pp_set_tags Format.std_formatter true;
     Format.pp_set_formatter_stag_functions Format.std_formatter (tui_stag_functions area);

     pp_linebreak Format.std_formatter ();
     Format.printf "@.";
     pp_linebreak Format.std_formatter ();
     Format.printf "@{<Highlight>Collaborative editor.@}@.@";
     pp_linebreak Format.std_formatter ()



   let render area ?( custom_formatter = Format.std_formatter) buf =
           (* print_string "\x1b[43;30mHello World!\x1b[0m\n"; *)

           render_styled_text area
end

<Highlight> is considered a semantics tag that is replaced by an ASCII color code. While this is a useful feature more sophisticated Terminal UI widgets need a better design.

Terminal Type( TTY )

This part of the code is reusable and is part of the Unix module. I chose the simplest possible mode to create my Terminal User Interface on my Mac system.

let change_mode ()=
     let enable_raw_mode () =
       let stdin_fd = Unix.descr_of_in_channel stdin in
       let termios = Unix.tcgetattr stdin_fd in
       let new_termios =
         Unix.
           { termios with c_icanon = false; c_echo = false; c_vmin = 0; c_vtime = 1 }
       in
       Unix.tcsetattr stdin_fd Unix.TCSAFLUSH new_termios;
       termios
    in enable_raw_mode()

Effect Handlers are a new OCaml feature

I will add some sections like this to explain the reason for experimenting with new paradigms like effect handlers. In many cases the code is too dense and will seem complicated when new techniques are introduced needlessly but Effect handlers are interesting to learn. Application though should be selective. There will be many usecases for these in the future.

So the following is an experiment in the sense that the code quality will be fixed only later. So, for example, global references are used to complete the code even though they are unnecessary.

Breaking paragraphs into lines

The title describes the essence of one such algorithm( Plass and Knuth ) to break paragraphs.

open Stdlib
open Effect.Deep
open Effect

type entry = {
  first : int;
  last : int;
  mutable next : int;
  mutable score  : int}


let gl = ref []

let is_space= function ' ' -> true | _ -> false

let rec printlist l =
  match l with
  | hd  ::tl ->
  Printf.printf " %d %d %d %d\n" hd.first hd.last hd.next hd.score;
  printlist tl
  | []  -> ()

let final_state l (start, idx) =

  (* let e = {first = start; last = idx; next = -1; score = -1} in *)
  (*  l := !l @ [e]; *)
  let e = {first = -1; last = -1; next = -1; score = 0} in
   l := !l @ [e];
  Printf.printf " Final state %d %d\n" start idx;
  Printf.printf " Size of list is %d\n" (List.length !l);
  l

type _ Effect.t += Skipping_spaces :  (int * int ) -> unit Effect.t

let parabreak l text ideal_width max_width  =
  Printf.printf " parabreak\n";
  let start = ref 0 in
  let idx,_ =
  String.fold_left (fun (idx,word_or_space) c ->
                       match (is_space c, word_or_space)  with
                       | (true,true)
                           ->
                           Printf.printf "Space at index %d, skipping\n" idx;

                           if !start < idx then
                                perform (Skipping_spaces (!start,idx)  );

                           start := idx + 1;
                           (idx + 1,false);
                       | (true,false)
                           -> Printf.printf "No Space at index %d, skipping\n" idx;
                           (idx + 1,false) 
                       | (false,_)
                           ->
                           (idx + 1,true)) (0,false) text
 in

                           if !start < idx then
                                Printf.printf "Final - Skipping spaces %d %d\n" !start idx;
                                perform (Skipping_spaces (!start,idx));
                           final_state l (!start,idx)
let effective text l =
  match_with (fun () -> parabreak l text 10 29)
    ()
  { effc = (fun (type c) (eff1: c Effect.t) ->
      match eff1 with
      | Skipping_spaces (s,s1) -> Some (fun (k: (c,_) continuation) ->
              Printf.printf "Skipping spaces \"%d %d\"\n" s s1;

              let e = {first = s; last = s1; next = -1; score = -1} in
              l := !l @ [e];
              continue k ()
          )
      | _ -> None
  );
  exnc = (function
        | e -> raise e
  );
  (* retc = fun _ -> failwith "Fatal error" *)
  (* retc = (fun res -> Printf.printf "Computation returned %d: \n" (List.length !l)) *)

  retc = (fun _ ->  l)

 }


let rec plassbreak indent  idx idealwidth maxwidth =

    let jdx = ref( idx + 1 ) in
    let lastrecord = List.nth !gl idx in
    let llen    = ref (lastrecord.last - lastrecord.first) in
    let bscore  = idealwidth - !llen in
    let bscore  = ref (bscore * bscore) in
    let btail   = ref !jdx in
    let rec loop_while j_dx =
      if j_dx < (List.length !gl) then(
         Printf.printf "llen: %d, bscore: %d, btail: %d\n" !llen !bscore !btail;
         let {first; last; next; score} = List.nth !gl j_dx in
            let wwidth  = last - first in
            if ((!llen + wwidth) < maxwidth) then(

              let lscore  = ref (idealwidth - (!llen + wwidth)) in
              lscore      := !lscore * !lscore;
              llen        := !llen + wwidth + 1;

              if score = -1 then
                begin
                plassbreak  (indent + 1) j_dx idealwidth maxwidth;
                end;

                let score1 = List.nth !gl !jdx in
                if ((!lscore + score1.score) < !bscore) then(
                  bscore  := !lscore + score1.score;
                  btail   := !jdx;
                );
                loop_while (j_dx + 1)
            )else ()
     )else ()
    in
    loop_while !jdx;
  let record = List.nth !gl idx in
  record.score <- !bscore;
  record.next <- !btail;
  if (record.next + 1) = List.length !gl then(
       record.score <- 0;
  )
  
let rec loop_while line text lines idx next acc =
    if acc > next || (acc + 1) >= List.length !gl then
    (
        line
    )
    else
        let {first; last; _} = List.nth lines acc in
        if (last - first) <= 0 then
        (
            line;
        )
        else(
            let new_line =
                line ^ (if acc == idx then "" else " ") ^
                String.sub text first (last - first)
            in
            loop_while  new_line text lines idx next (acc + 1)
        )


let  layout text idealwidth maxwidth =

 let rec loop idx lines line =
    if (idx < (List.length !gl - 1))  then

        let entry = List.nth lines idx in
        let line = loop_while line text lines idx entry.next idx in
        let line =
        if (String.length line < maxwidth)
        then
        (
            let line = line ^ String.make (maxwidth - String.length line) ' ' in
            line
        )else line
        in
        let line = Bytes.of_string line in
        let _ = Bytes.set line idealwidth '+' in
        let line = Bytes.to_string line ^ "|" in
        Printf.printf " %s \n" line;
        loop entry.next !gl ""
    in
    loop 0 !gl ""

(* read the entire file *)
let read_file() =
  let contents = In_channel.with_open_text "/Users/anu/Documents/go/testwiki.txt" In_channel.input_all in
  contents

let pbreak_main =
  try
      let l = ref [] in
      let file_contents = read_file() in

      let l1 = effective  file_contents l in
      gl := !l1;

      let _ =  plassbreak 0 0 10 29 in
      Printf.printf "Global list %d\n" (List.length !gl) ;
      printlist !gl;

      let _ = layout file_contents 10 20 in

      ()


  with
  | exn -> Printf.printf "Unhandled exception: %s\n" (Printexc.to_string exn)

Validation of the algorithm

The test is the only validation now. The algorithm is not verified based on the original reference to the algorithm. This OCaml code is ported from C++. There is a single bug that increases the score and as a consequence breaks the paragraph at the wrong position. But even otherwise the breaks don’t seem to be perfect.

This has to be surely improved when used by an editor. That is a task for the future.

The first +
first know+
known use +
use of +
of the +
the terms.+
terms. +
Written on October 1, 2024