jack-html implementation details

Table of content

Summary

In this post, we show how jack-html processes the following component 

'(:div/foo.bar
  "A"
  (:p (@ :class "baz") "B" (:hr) "C")
  ("D" "E" "F"))

in order to return the following string 

"<div id=\"foo\" class=\"bar\">A<p class=\"baz\">B<hr />C</p>DEF</div>"

that we can use to produce this following html snippet: 

<div id="foo" class="bar">
  A
  <p class="baz">B<hr />C</p>
  DEF
</div>

Description of the program

In this section we call input-tree the data structure jack-html receives as input.

For instance, in the form 

(jack-html '(:div.foo (:p "bar-1" (:span "baz") "bar-2")))

the data structure 

'(:div.foo (:p "bar-1" (:span "baz") "bar-2"))

is the input-tree.

With that said, let's describe our program.

While traversing input-tree (DFS algorithm), we builds a tree containing a left part and a right part that represents the html string to be returned at the end of the traversal.

While the left part of this tree is always a string, the right part can grow recursively by dividing it into two parts (left and right).

In the following example, we can see the successive states of the this tree when input-tree is '(:div.foo (:p "bar-1" (:span "baz") "bar-2")): 

(:left ""
 :right "")

(:left "<div class=\"foo\">"
 :right "</div>")

(:left "<div class=\"foo\"><p>"
 :right "</p></div>")

(:left "<div class=\"foo\"><p>bar-1"
 :right "</p></div>")

(:left "<div class=\"foo\"><p>bar-1<span>"
 :right (:left "</span>"
         :right "</p></div>"))

(:left "<div class=\"foo\"><p>bar-1<span>baz"
 :right (:left "</span>"
         :right "</p></div>"))

(:left "<div class=\"foo\"><p>bar-1<span>baz</span>"
 :right "</p></div>")

(:left "<div class=\"foo\"><p>bar-1<span>baz</span>bar-2"
 :right "</p></div>")

When we have completly traversed input-tree, we return the concatenation of the left part and the right part of tree.

Specifically, at the beginning of the programs we set the variables tree, rest, comps and comp that define the state of the program.

tree is the tree we build a each iteration that contains the elements needed to construct the final returned value.

rest is the stack that contains the parts of input-tree left out to be processed later.

comps is the current list of components being treated. Components in comps are at the same level in input-tree.

comp is the current component (always equal to the first element of comps) that determines how we must update the state (tree, rest and comps) of the program at each iteration:

  1. when comp is nil, we ignore this component and follow the traversal with the cdr of comps,

  2. when comp is a string or a number, we update tree by appending comp (as a string) to the left part of tree, the right part staying the same,

  3. when comp is a list of components we put them at the same level of the cdr of comps, specifically we set comps to be (append comp (cdr comps)),

  4. when comp is a tag component, two cases must be distinguished according to the value of (cdr comps):

    1. if (cdr comps) is non-nil:

      • we update tree according to the value returned by jack-tag and by dividing the right part of tree into two parts,

      • we push the components (cdr comps) on the stack rest and,

      • the components to be treated in the next iteration are the children of the tag component comp (which can be either (cdr comp) or (cddr comp)), so comps should be set to contains those children only, but as we need to remember that once those children has been treated we have to treat the element added to the stack rest, we also append to comps the keyword :rest,

    2. if (cdr comps) is nil:

      • it means that there is no part of input-tree to be added to the stack rest at this iteration, so rest stays unchanged,

      • we just update tree according to the value returned by jack-tag (without dividing the right part of tree) and,

      • the components to be treated in the next iteration are the children of the tag component comp (which can be either (cdr comp) or (cddr comp)), so comps is set to be those children,

  5. when comp is the keyword :rest, that means we have completed the traversal of a part of input-tree, so:

    1. we update tree accordingly by appending the left part of the right part of tree to its left part, and we set its right part to be the right part of the right part of tree,

    2. now we have to treat the most recently added list of components in the stack rest. To do so, we set comps to be the first element of rest and remove that first element from rest (this can be done like this (setq comps (pop rest))),

  6. when comp is any other object, we skip it or we raise an error depending on the variable jack-html-raise-error-p.

Finally, when comp is nil and (cdr comps) too, it means that we have completly traversed input-tree, no more iterations are needed and we return the concatenation of the left part and the right part of tree.

Running the program step by step

Let's go through each iteration that the following evaluation implies by printing out and commenting the successive states of our program: 

(jack-html
 '(:div/foo.bar
   "A"
   (:p (@ :class "baz") "B" (:hr) "C")
   ("D" "E" "F")))

input-tree, tree, rest, comps and comp have the same meaning as in the previous section.

And, each state of the program is representing as a plist where:

  • :tree hold the value of tree,

  • :rest the value of rest,

  • :comps the value of comps and,

  • :comp the value of comp.

First the state is initialized like this (before entering in the while loop): 

(:tree (:left ""
        :right "")
 :rest nil
 :comps ((:div/foo.bar
          "A"
          (:p (@ :class "baz") "B" (:hr) "C")
          ("D" "E" "F")))
 :comp (:div/foo.bar
        "A"
        (:p (@ :class "baz") "B" (:hr) "C")
        ("D" "E" "F")))

As comp (equal to (:div/foo.bar ...)) is a tag component, and is the only component in comps:

  1. tree is updated with the left part and right part of the tag returned by jack-tag function,

  2. rest stack stays nil,

  3. the components of input-tree that should be treated in the next iteration are the children of the tag comp, which are the components at the same level of the string component "A", specifically, the new value of comps is cdr of the current comp,

so the new state is: 

(:tree (:left "<div id=\"foo\" class=\"bar\">"
        :right "</div>")
 :rest nil
 :comps ("A"
         (:p (@ :class "baz") "B" (:hr) "C")
         ("D" "E" "F"))
 :comp "A")

As comp (equal to "A") is a string component,

  1. we append "A" to the left part of tree,

  2. and we iterate on the cdr of the current comps (it means on the next components at the same level of "A" component),

so the new state is: 

(:tree (:left "<div id=\"foo\" class=\"bar\">A"
        :right "</div>")
 :rest nil
 :comps ((:p (@ :class "baz") "B" (:hr) "C")
         ("D" "E" "F"))
 :comp (:p (@ :class "baz") "B" (:hr) "C"))

As comp (equal to (:p (@ :class "baz") ...)) is a tag component but not the only components in comps:

  1. tree is updated with the left part being the concatenation of its current left part and the left part of the tag returned by jack-tag, and the right part is a subtree with its left part being the right part of the tag return by jack-tag and the right part being its current right part,

  2. we push the cdr of comps to the stack rest in order to treat it after,

  3. the components to be treated in the next iteration are the children of the tag component comp (which are the components at the same level of the string component "B"), so comps should be set to contains those children only, but as we need to remember that once those children has been treated we have to treat the element added to the stack rest, we also append to comps the keyword :rest,

so the new state is: 

(:tree (:left "<div id=\"foo\" class=\"bar\">A<p class=\"baz\">"
        :right (:left "</p>"
                :right "</div>"))
 :rest ((("D" "E" "F")))
 :comps ("B" (:hr) "C" :rest)
 :comp "B")

As comp (equal to "B") is a string component, we do the same thing we did before for the string component "A" (note that the right part of tree and rest are unchanged).

So the new state is: 

(:tree (:left "<div id=\"foo\" class=\"bar\">A<p class=\"baz\">B"
        :right (:left "</p>"
                :right "</div>"))
 :rest ((("D" "E" "F")))
 :comps ((:hr) "C" :rest)
 :comp (:hr))

As comp (equal to (:hr)) is a tag component but not the only components in comps:

  1. tree is updated with the left part being the concatenation of its current left part and the left part of the tag returned by jack-tag, and the right part is a subtree with its left part being the empty string "" (because (:hr) is a void tag) and the right part being its current right part,

  2. we push the cdr of comps to the stack rest in order to treat it after,

  3. because (:hr) has no children, comps is the empty list to which we append the keyword :rest (for the same reason as before),

so the new state is: 

(:tree (:left "<div id=\"foo\" class=\"bar\">A<p class=\"baz\">B<hr />"
        :right (:left ""
                :right (:left "</p>"
                        :right "</div>")))
 :rest (("C" :rest) (("D" "E" "F")))
 :comps (:rest)
 :comp :rest)

As comp is equal to the keyword :rest,

  1. we update tree by appending the left part of the right part of tree to its left part, and we set its right part to be the right part of the right part of tree,

  2. we set comps to be the most recently added list of components in the stack rest that we also remove from the stack,

so the new state is: 

(:tree (:left "<div id=\"foo\" class=\"bar\">A<p class=\"baz\">B<hr />"
        :right (:left "</p>"
                :right "</div>"))
 :rest ((("D" "E" "F")))
 :comps ("C" :rest)
 :comp "C")

As comp (equal to "C") is a string component, we do the same thing we did before for the string components "A" and "B" (note that the right part of tree and rest are unchanged).

So the new state is: 

(:tree (:left "<div id=\"foo\" class=\"bar\">A<p class=\"baz\">B<hr />C"
        :right (:left "</p>"
                :right "</div>"))
 :rest ((("D" "E" "F")))
 :comps (:rest)
 :comp :rest)

As comp is equal to the keyword :rest,

  1. we update tree by appending the left part of the right part of tree to its left part, and we set its right part to be the right part of the right part of tree,

  2. we set comps to be the most recently added list of components in the stack rest that we also remove from the stack,

so the new state is: 

(:tree (:left "<div id=\"foo\" class=\"bar\">A<p class=\"baz\">B<hr />C</p>"
        :right "</div>")
 :rest nil
 :comps (("D" "E" "F"))
 :comp ("D" "E" "F"))

As comp (equal to ("D" "E" "F")) is a list of components, we put them at the same level of the cdr of comps, specifically we set comps to be (append comp (cdr comps)). Note that tree is unchanged.

So the new state is: 

(:tree (:left "<div id=\"foo\" class=\"bar\">A<p class=\"baz\">B<hr />C</p>"
        :right "</div>")
 :rest nil
 :comps ("D" "E" "F")
 :comp "D")

As comp (equal to "D") is a string component, we do the same thing we did before for the string components "A", "B" and "C" (note that the right part of tree and rest are unchanged).

So the new state is: 

(:tree (:left "<div id=\"foo\" class=\"bar\">A<p class=\"baz\">B<hr />C</p>D"
        :right "</div>")
 :rest nil
 :comps ("E" "F")
 :comp "E")

As comp (equal to "E") is a string component, we do the same thing we did before for the string components "A", "B", "C" and "D" (note that the right part of tree and rest are unchanged).

So the new state is: 

(:tree
 (:left "<div id=\"foo\" class=\"bar\">A<p class=\"baz\">B<hr />C</p>DE"
  :right "</div>")
 :rest nil
 :comps ("F")
 :comp "F")

As comp (equal to "F") is a string component, we do the same thing we did before for the string components "A", "B", "C", "D" and "F" (note that the right part of tree and rest are unchanged).

So the new state is: 

(:tree (:left "<div id=\"foo\" class=\"bar\">A<p class=\"baz\">B<hr />C</p>DEF"
        :right "</div>")
 :rest nil
 :comps nil
 :comp nil)

At that point, as comp is nil and (cdr comps) too, we get out of the loop.

That means that we have completely traversed input-tree.

And now tree contains all the data we need to produce the html string.

Eventually, we return the concatenation of the left part and the right part of tree. 

"<div id=\"foo\" class=\"bar\">A<p class=\"baz\">B<hr />C</p>DEF</div>"
PREVRANDOMNEXT