Implementing VDOM in Elm

What if Elm didn’t ship with a VDOM library? No HTML or SVG? You might be tempted that it wouldn’t be very useful, but we can implement it ourselves using pure elm and ports. Ports? You heard right, good old trusty ports.

Simplest thing possible

So how can we render stuff? Well let’s make a simple program to test:

module Main exposing (main)

import MyHtml exposing (Html, program, div, text, href, a)

import Time


type Msg
    = Tick Float

update : Msg -> Int -> (Int, Cmd Msg)
update msg model =
    case msg of
        Tick t ->
            ( t, Cmd.none )

view : Int -> Html Msg
view model =
    div [] 
        [ text (model |> toString)
        , a [href "https://google.com"] [ text "GOOGLE IT"] 
        ]

main =
    program
        { init = ( 0, Cmd.none )
        , update = update
        , subscriptions = \model -> Time.every Time.second Tick
        , view = view
        }

Looks pretty standard except for the funny import. Well, what does that look like?

port module MyHtml exposing (program, Html, Attribute, div, text, a, href)


type Html msg
    = Node String (List (Attribute msg)) (List (Html msg))
    | Text String


type Attribute msg
    = Attr String String
    | Property String Json.Value

First, we defined some types to represent our HTML tree. Note that this is by no means complete, but can be easily extended to support things like SVG.

init : ( model, Cmd msg ) -> (model -> Html msg) -> ( model, Cmd msg )
init userInit userView =
    let
        ( initModel, initCmd ) =
            userInit
    in
    ( initModel, Cmd.batch [ render (userView initModel), initCmd ] )


update :
    (msg -> model -> ( model, Cmd msg ))
    -> (model -> Html msg)
    -> msg
    -> model
    -> ( model, Cmd msg )
update userUpdate userView msg model =
    let
        ( newModel, newCmd ) =
            userUpdate msg model
    in
    ( newModel, Cmd.batch [ render (userView newModel), newCmd ] )


program userProgram =
    Platform.program
        { init = init userProgram.init userProgram.view
        , update = update userProgram.update userProgram.view
        , subscriptions = userProgram.subscriptions
        }

Next let’s define our program function. We’re essentially wrapping the users program, but on both init and update we’re adding an extra Cmd in to the mix:

render : Html msg -> Cmd msg
render =
    encodeHtml >> renderPort

port renderPort : Json.Value -> Cmd msg


encodeHtml html =
    case html of
        Node name attrs children ->
            Json.object
                [ ( "type", Json.string "node" )
                , ( "name", Json.string name )
                , ( "attributes", Json.list (List.map encodeAttr attrs) )
                , ( "children", Json.list (List.map encodeHtml children) )
                ]

        Text str ->
            Json.object [ ( "type", Json.string "text" ), ( "value", Json.string str ) ]


encodeAttr attr =
    case attr of
        Attr key val ->
            Json.object [ ( "type", Json.string "attribute" ), ( "key", Json.string key ), ( "value", Json.string val ) ]

        Property key val ->
            Json.object [ ( "type", Json.string "property" ), ( "key", Json.string key ), ( "value", val ) ]

So here we have encoded our HTML structure into JSON and sent it over a port. I’ll spare you from future encoders, but they all look follow this same pattern. Let’s see what the JavaScript side looks like:

<div id="output"></div>
<script>
    var app = Elm.Main.worker()
    app.ports.renderPort.subscribe(function(html) {
      const output = document.getElementById("output");
      while (output.firstChild) {
        output.removeChild(output.firstChild);
      }
      render(html, output);
    });

    function render(struct, out) {
       switch(struct.type) {

         case "node":
           var el = document.createElement(struct.name);
           struct.attributes.forEach(attr => {
             switch(attr.type) {

               case "attribute":
                 return el.setAttribute(attr.key, attr.value);

               case "property":
                 return el[attr.key] = attr.value;
             }
           });
           out.appendChild(el);
           struct.children.forEach(child => render(child, el));
           break;

         case "text":
           var el = document.createTextNode(struct.value);
           out.appendChild(el);
           break;
       }
    }
</script>

So whenever the renderPort triggers, we remove all contents from our destination node and use DOM apis to build the whole structure. Note that in DOM apis there are two flavors of attribute - actual atttributes that need to be set with setAttribute and properties that have specialised setters.

Does it work? Check it out:

Supporting events

Alright, we managed to get something on the screen, but we want to build a real app and so we need to support events coming in. We’ll need to modify our approach a bit.

Let’s make a little counter app to demo this:

module Main exposing (main)

import MyHtml exposing (Html, program, div, text, href, a, onClick)

type Msg
    = Inc
    | Dec


main =
    program
        { init = ( 0, Cmd.none )
        , update =
            \msg model ->
                case msg of
                    Inc ->
                        ( model + 1, Cmd.none )

                    Dec ->
                        ( model - 1, Cmd.none )
        , subscriptions = \model -> Sub.none
        , view =
            \model ->
                div []
                    [ text (model |> toString)
                    , a [ onClick Inc ] [ text "+" ]
                    , a [ onClick Dec ] [ text "-" ]
                    ]

Event handlers in Elm are Json.Decode.Decoders that transform JavaScript event objects into the users custom msg type. But Json.Decode.Decoders are really functions under the hood.

Now a bit of trouble presents itself. We can’t encode JSON Decoders into Json.Value objects and send them over ports. So how can we set up event listeners?

To solve this, we need to build up a dispatcher, which we can store in our model. So let’s make our own model, that will wrap the users model:

import Dict exposing (Dict)

type alias PrivateModel model msg =
    { userModel : model
    , handlers : Dict String (Decoder msg)
    }

The handlers key is a dispatcher datastructure: it holds the decoders the user specified stored under string keys. But where do those come from? We’ll use a simple trick and compute a path through the DOM tree as their key. So for example the Inc onClick handler above, would have the key path div.0.a:click.

Next, we’ll introduce a new representation, which we’ll call SafeHtml. This is exactly the same as Html msg, except it drops the type variable and inside the coresponding SafeAttribute stores these key strings instead of the decoders. Note that we will only expose Html msg to the user of our library, SafeHtml is an implementation detail. We also add a new constructor for creating event listeners:

type Node handler
    = Node String (List (NodeAttribute handler)) (List (Node handler))
    | Text String


type NodeAttribute handler
    = Attr String String
    | Property String Json.Value
    | Event String Options handler


type alias Options =
    { preventDefault : Bool
    , stopPropagation : Bool
    }


type alias Html msg =
    Node (Json.Decode.Decoder msg)


type alias Attribute msg =
    NodeAttribute (Json.Decode.Decoder msg)

type alias SafeHtml =
    Node String


type alias SafeAttribute =
    NodeAttribute String

We also update our encoders to only support SafeHtml.

Now we have the key data modeling pieces in hand. We now need a function that will take a Html msg and give us back both a handlers dispatcher and a SafeHtml tree that we can use for rendering:

extractListeners : String -> Html msg -> ( Dict String (Decoder msg), SafeHtml )
extractListeners prefix html =
    case html of
        Node name attrs children ->
            let
                key =
                    prefix ++ "." ++ name

                safeAttrs =
                    List.map (makeAttrSafe key) attrs

                listeners =
                    List.filterMap getListener attrs

                kids =
                    List.indexedMap (\index -> extractListeners (key ++ "." ++ toString index)) children

                childListeners =
                    List.foldr (\( a, _ ) b -> Dict.union a b) Dict.empty kids
            in
            ( List.foldr (\( k, fn ) d -> Dict.insert (key ++ ":" ++ k) fn d) childListeners listeners
            , Node name safeAttrs (List.map Tuple.second kids)
            )

        Text s ->
            ( Dict.empty, Text s )


makeAttrSafe : String -> Attribute msg -> SafeAttribute
makeAttrSafe prefix attr =
    case attr of
        Event key options tagger ->
            Event key options (prefix ++ ":" ++ key)

        Attr k v ->
            Attr k v

        Property k v ->
            Property k v


getListener : Attribute msg -> Maybe ( String, Decoder msg )
getListener attr =
    case attr of
        Event key _ tagger ->
            Just ( key, tagger )

        _ ->
            Nothing

Now let’s build it and use it:

subscriptions : (model -> Sub msg) -> PrivateModel model msg -> Sub (Maybe msg)
subscriptions userSubscribtions model =
    let
        eventDispatcher ( key, event ) =
            Dict.get key model.handlers
                |> Maybe.andThen
                    (\decoder ->
                        Json.Decode.decodeValue decoder event
                            |> Result.toMaybe
                    )
    in
    Sub.batch [ eventPort eventDispatcher, Sub.map Just (userSubscribtions model.userModel) ]

port eventPort : (( String, Json.Value ) -> msg) -> Sub msg


init : ( model, Cmd msg ) -> (model -> Html msg) -> ( PrivateModel model msg, Cmd (Maybe msg) )
init userInit userView =
    let
        ( initModel, initCmd ) =
            userInit

        ( handlers, safeView ) =
            extractListeners "" (userView initModel)
    in
    ( { userModel = initModel
      , handlers = handlers
      }
    , Cmd.batch [ render safeView, Cmd.map Just initCmd ]
    )



update :
    (msg -> model -> ( model, Cmd msg ))
    -> (model -> Html msg)
    -> Maybe msg
    -> PrivateModel model msg
    -> ( PrivateModel model msg, Cmd (Maybe msg) )
update userUpdate view maybeMsg model =
    case maybeMsg of
        Just msg ->
            let
                ( newModel, newCmd ) =
                    userUpdate msg model.userModel

                ( handlers, safeView ) =
                    extractListeners "" (view newModel)
            in
            ( { userModel = newModel, handlers = handlers }
            , Cmd.batch [ render safeView, Cmd.map Just newCmd ]
            )

        Nothing ->
            ( model, Cmd.none )


program userProgram =
    Platform.program
        { init = init userProgram.init userProgram.view
        , update = update userProgram.update userProgram.view
        , subscriptions = subscriptions userProgram.subscriptions
        }

To handle the posibility that our dispatcher somehow gets out of sync with the DOM, we have to wrap the users message in a maybe. In the subscriptions call, we use the dispatcher to transform an incoming message (which is in the form of a (keyPath, eventObject) tuple) into the message the user expects. We handle the maybe in the new update function by simply ignoring the Nothing case. In both update and init we now call our extractListeners function to build up the dispatcher data structure.

And here’s the updated JavaScript:

function render(struct, out, port) {
   switch(struct.type) {
     case "node":
       var el = document.createElement(struct.name);
       struct.attributes.forEach(attr => {
         switch(attr.type) {
           case "attribute":
             return el.setAttribute(attr.key, attr.value);

           case "property":
             return el[attr.key] = attr.value;

           case "event":
             return el.addEventListener(attr.key, e => {
               port.send([attr.value, e]);
               if (attr.stopPropagation) {
                 e.stopPropagation();
               }
               if (attr.preventDefault) {
                 e.preventDefault();
               }
             });
         }
       });
       out.appendChild(el);
       struct.children.forEach(child => render(child, el, port));
       return;

     case "text":
       var el = document.createTextNode(struct.value);
       out.appendChild(el);
       return;
   }
}

var app = Elm.Main.worker()
app.ports.renderPort.subscribe(function(html) {
  const output = document.getElementById("output");
  while (output.firstChild) {
    output.removeChild(output.firstChild);
  }
  render(html, output, app.ports.eventPort);
});

And that’s basically all it takes to get events coming back in:

Making it Virtual

You may have noticed that we are re-rendering the entire DOM tree on every update. This is both not efficient and also potentially wrong, as it will lose focus on input elements and the like. The solution is to diff a new rendered view with the current one. This would create a bunch of patches that can then be applied to the real DOM for efficient updates.

The nice thing is that all but the application of patches can be done in Elm. So let’s get started.

First let’s look at describing changes between SafeHtml structures.

type Change
    = Change Patch
    | At Int Change
    | Batch (List Change)


type Patch
    = Redraw SafeHtml
    | Facts (List ( Bool, SafeAttribute ))
    | TextChange String
    | Remove
    | Insert SafeHtml

encodeChange : Change -> Json.Value   
encodeChange change = ...

encodePatch : Patch -> Json.Value
encodePatch patch = ...

I’ve spared you the implementation of the decoders in the interest of brevity. They look just the same as the other decoders.

Now let’s take a look at how we might apply these changes to the existing DOM:

function render(struct, port) {
   switch(struct.type) {
     case "node":
       var el = document.createElement(struct.name);
       applyFacts(struct.attributes, el, port)
       struct.children.forEach(child => el.appendChild(render(child, port)));
       return el;
     case "text":
       return document.createTextNode(struct.value);
   }
}

function applyChange(change, element, port) {
  switch(change.type) {
    case "change":
      return applyPatch(change.patch, element, port);
    case "at":
      return applyChange(change.change, element.childNodes[change.index], port);
    case "batch":
      return change.changes.forEach(c => applyChange(c, element, port));

  }
}

function applyPatch(patch, out, port) {
    switch(patch.type) {
      case "facts":
        return applyFacts(patch.facts, out, port);
      case "text":
        out.nodeValue = patch.value;
        return;
      case "redraw":
        return out.parentNode.replaceChild(render(patch.value, port), out);
      case "insert":
        return out.appendChild(render(patch.value, port));
      case "remove":
        return out.parentNode.removeChild(out);
    }
}

function applyFacts(facts, el, port) {
  facts.forEach(attr => {
    switch(attr.type) {
      case "attribute":
        return attr.value == null ? 
          el.removeAttribute(attr.key) : 
          el.setAttribute(attr.key, attr.value);
      case "property":
        if (attr.value == null) {
          delete el[attr.key];
          return;
        } else {
          el[attr.key] = attr.value;
          return;
        }
      case "event":
       if (attr.value == null) { 
         el.removeEventListener(attr.key, el[attr.value]);
         delete el[attr.value];
       } else {
         const handler = e => {
           port.send([attr.value, e]);
           if (attr.stopPropagation) {
             e.stopPropagation();
           }
           if (attr.preventDefault) {
             e.preventDefault();
           }
         };
         el.addEventListener(attr.key, handler);
         // store a reference to the function so we can remove the handler
         el['handler-' + attr.value] = handler;
       }
     }
  });
}

var app = Elm.Main.worker();

app.ports.renderPort.subscribe(function(change) {
  const output = document.getElementById("output");
  applyChange(change, output, app.ports.eventPort);
});

This might seem like a lot of code, but it’s fairly simple. The Change datastructure allows to find the node that should change (that’s what the At constructor is for). Then we apply one of the 5 possible changes. Note that there are more possible mutations that could increase efficiency, like a reorder change, but we’ve done only these for simplicity. Facts is a term used in Elm’s virtual dom to refer to attributes, properties and event listeners.

Ok, let’s try to get something on the screen:

initialRender : SafeHtml -> Cmd (Maybe msg)
initialRender =
    Insert >> Change >> encodeChange >> renderPort

type alias PrivateModel model msg =
    { userModel : model
    , handlers : Dict String (Decoder msg)
    , view : SafeHtml
    }

init : ( model, Cmd msg ) -> (model -> Html msg) -> ( PrivateModel model msg, Cmd (Maybe msg) )
init userInit userView =
    let
        ( initModel, initCmd ) =
            userInit

        ( handlers, safeView ) =
            extractListeners "" (userView initModel)
    in
    ( { userModel = initModel
      , handlers = handlers
      , view = safeView
      }
    , Cmd.batch [ initialRender safeView, Cmd.map Just initCmd ]
    )

Note that we store a reference to the current view. Let’s do some diffing against it:

wrapAt : Int -> List Change -> List Change
wrapAt i changes =
    case changes of
        [] ->
            []

        list ->
            [ At i (batchIfNecessary changes) ]


batchIfNecessary : List Change -> Change
batchIfNecessary changes =
    case changes of
        [] ->
            -- This should never happen
            Batch []


        x :: [] ->
            x

        list ->
            Batch list


diff : SafeHtml -> SafeHtml -> List Change
diff before after =
    if before == after then
        []
    else
        case ( before, after ) of
            ( Text bstr, Text astr ) ->
                [ Change (TextChange astr) ]

            ( Node bName bAttrs bChildren, Node aName aAttrs aChildren ) ->
                if aName == bName then
                    let
                        attrsDiff =
                            if aAttrs == bAttrs then
                                []
                            else
                                List.map2 diffAttrs bAttrs aAttrs |> List.concat |> Facts |> Change |> List.singleton

                        childrenDiff =
                            if bChildren == aChildren then
                                []
                            else
                                diffChildren 0 bChildren aChildren
                    in
                    [ batchIfNecessary (attrsDiff ++ childrenDiff) ]
                else
                    [ Change (Redraw after) ]

            _ ->
                [ Change (Redraw after) ]


diffAttrs : SafeAttribute -> SafeAttribute -> List ( Bool, SafeAttribute )
diffAttrs before after =
    if before == after then
        []
    else
        [ ( False, before ), ( True, after ) ]


diffChildren : List SafeHtml -> List SafeHtml -> List Change
diffChildren index before after =
    case ( before, after ) of
        ( [], [] ) ->
            []

        ( b :: efore, [] ) ->
            At index (Change Remove) :: diffChildren (index + 1) efore after

        ( [], a :: fter ) ->
            Change (Insert a) :: diffChildren (index + 1) before fter

        ( b :: efore, a :: fter ) ->
            case diff b a of
                [] ->
                    diffChildren (index + 1) efore fter

                diffs ->
                    At index (batchIfNecessary diffs) :: diffChildren (index + 1) efore fter

Again a fair amount of code, but the idea is pretty simple - we traverse both trees simultaneously and record changes as we see them. This code could be made more sophisticated/performant, but I tried to not make it too complicated.

I also tried to remove pointless wrapping structures, so that the changes output is easy on the eyes.

OK, let’s get the diffing wired up into our update function:

render : SafeHtml -> SafeHtml -> Cmd msg -> Cmd (Maybe msg)
render before after cmd =
    case diff before after of
        [] ->
            Cmd.map Just cmd

        changes ->
            changes
                |> batchIfNecessary
                |> At 0
                |> encodeChange
                |> renderPort
                |> (\renderCmd -> Cmd.batch [ renderCmd, Cmd.map Just cmd ])

update :
    (msg -> model -> ( model, Cmd msg ))
    -> (model -> Html msg)
    -> Maybe msg
    -> PrivateModel model msg
    -> ( PrivateModel model msg, Cmd (Maybe msg) )
update userUpdate view maybeMsg model =
    case maybeMsg of
        Just msg ->
            let
                ( newModel, newCmd ) =
                    userUpdate msg model.userModel

                ( handlers, safeView ) =
                    extractListeners "" (view newModel)
            in
            ( { userModel = newModel, handlers = handlers, view = safeView }, render model.view safeView newCmd )

        Nothing ->
            ( model, Cmd.none )

And that’s basically it:

I’ve prepared a Gist version for easier reading of the completed source code.

Discussion

Now all this is neat, but so what? I wrote this for a few reasons:

• It’s meant as a bit more advanced tutorial on some cool ports techniques.
• You are not tied to the built in rendering system. If you want to build your own rendering engine in Elm, I’ve just shown you how. I hope this can encourage some experimentation with cool techniques. One of the popular ones these days is to not diff against a Virtual DOM, but against the real DOM. You can try that pretty easily.
• You can customise the way the rendering works. Need a crazy component (say a map library) to work within your tree? All you need to do is implement a new Node constructor.
• After reading this, you should be much better equiped to go and read the real implementation. It’s much harder to read, but most of the concepts are the same.

However, a few caveats are in order.

1. This will not beat the native version in performance anytime soon. We need to convert all of the Elm datastructures into native JS ones and that is pretty costly.
2. I’ve not widely tested this. It’s meant as educational material, not a production ready library.

Hope you enjoy playing with it. Let me know on the Elm slack if you can use this for some cool experiments :)

Coupling

Today I was debugging some code. I spent the whole day on it, I ended up writing only 2 lines of code to fix the problem. Where did I spend all of my time? Trying to understand what the code did and how information actually travelled through the system. I’d like to discuss a few ways software systems communicate information and the impact of those choices on the maintainability of that software.

Criteria

We can abstract away and say that each method of communication introduces some degree of coupling - that is how much the two software components depend on each other.

Coupling has a few advantages and disadvantages. Loose coupling allows components to be more easily taken apart and reused with other components, decreasing the amount and complexity of doing that. Tight coupling on the other hand tends to be logically simpler.

Method calls

The simplest method is for one object to call methods on another object. This usually adds incredibly tight coupling making rewriting of both components necessary. Sometimes this also induces circular dependency issues, when object A needs to call methods of object B who needs to call methods on object A.

The principal method of reducing coupling is a variant of Duck Typing: where component A doesn’t need to know or care anything about the exact type or implementation details of object B as long as object B can understand some methods that object A requires.

There are many variations of this idea e.g.: contracts, interfaces or protocols.

Method calls, unlike all of the remaining techniques holds a unique advantage: when reading the code, you can easily work out the flow within your program (there are still asynchronous issues, but at least it is clear which code will handle the future). All you need to know is the type of the variable and the method name, and then you can usually easily see the code responsible. Furthermore support in debugging tools is usually excellent.

Events; Callbacks

This technique works by having object A have a method that allows object B to subscribe its method to be called by object A whenever it decides to do so. In pseudocode:

window = new Window # window has a method called display
button  = new Button("Click to see a window")
button.onClick(window.display)
# when the user clicks the button, the method window.display will be called

Events can have various implementations that are better or worse. You can have very direct event distribution methods like the pseudocode above, or you can have quite indirect ones, like a global Notification Center object that all other components subscribe to or even a remote web service communicating with different components. The direct method we can see above is almost as good as method calls as we can see which object is talking to which object, the only thing that becomes more complicated is when does the call occur.

However when there is some central delivery mechanism (or perhaps code relies on bubbling mechanisms or similar), it becomes increasingly difficult to figure out what code is going to handle it. If you see code like:

NotificationCenter.broadcast(myEventNameVariable, eventPayload)

It takes quite a while to find the relevant code that responds to that. What is also implicit in these systems is that where using methods you would have code like this:

 class A
   method doSomethingWithMethods()
      b.foo()
      c.bar()
      d.bum()

class B
   method foo()
     doFoo()

class C
   method bar()
     doBar()

class D
   method bum()
     doBum()

With events you can rewrite that as:

 class A
   method doSomethingWithEvents()
      NotificationCenter.broadcast('somethingDone')

class B
   NotificationCenter.on('somethingDone', doFoo())

class C
   NotificationCenter.on('somethingDone', doBar())

class D
    NotificationCenter.on('somethingDone', doBum())

As you can see, with the first code we can clearly see that calling A.doSomethingWithMethods will first execute A.doFoo then B.doBar and finally C.doBum, with events we, by looking at A.doSomethingWithEvents we have no idea what is going to happen. We have to do a global search through our codebase to find all the places that the event string occurs. We have no guarantee in which order will the methods be executed. Furthermore, when in the first case we get an error on line 3 of method A, we know that object B is likely innocent, the likely culprit is object C. In the second case we will be lucky if we can trace it to object A at all, let alone have an idea to which of the listeners belongs the blame.

When should one use such a system then? In highly decoupled systems or as an alternative to local events. As such bubbling is often a good solution, as a component for which tighter coupling is appropriate can subscribe directly to the object, whereas a loose component can subscribe at the top-level. (e.g. I want to make a backup whenever the user saves something, but I have a fully generic backup solution, therefore I could subscribe to a top-level backup event as I don’t care if the file being saved is a text document or a video file.)

Value observing; binding

Some languages support adding observers to variables - whenever a variable on a object changes, some object can run some code in response. If this is doubled, then it is called binding, where changing one variable automatically changes the value of another.

This looks like a really nice idea and typically allows for impressive demos where very little code can achieve a lot. But when you have a large and complex system, you start to believe that value-observing is a terrible idea - especially between objects. In most mutable languages we are used to assigning to variables all the time and it is generally considered fairly safe (except for loosing the previous value). Often we spend significant time debugging code until we realize that actually assigning to a variable triggered some code that triggered an asynchronous request that causes a logic error. Perhaps this technique could be more tolerable if the variable had to explicitly declare itself observable before this started working.

My recommendation: don’t use value-observing other then inside the same object, and prefer easier to understand method such as setters and getters.

Conclusion

Consider the ease of debugging later when writing your code. Don’t just add observers all over the place because it looks easier than defining a bunch of methods. Just because you made a brand-new notification service doesn’t mean you need to use it for two halves of the same component. That’s like two people in the same room sending each other text messages: possible, but awkward.