Problem

The AST nodes produced by the ClojureScript analyzer have a :children key to allow generic traversals. Unfortunately, this key is currently a denormalized view of child ast nodes.

For example, an :if node has :test, :then, and :else keys whose values are also contained in :children. This presents some difficulty when writing AST transformations because every transform function must be aware of this duplication. To correctly replace the :test of an :if node, you must also replace the first element of the :children vector.

Discussion

• https://groups.google.com/d/topic/clojure-dev/vZLVKmKX0oc/discussion
• https://docs.google.com/document/d/1DRN-tBIqhqVVyoHIDs7CMkduBFk-vqd_958ojeIBLHQ/edit
• http://dev.clojure.org/jira/browse/CLJS-289

Design

• Solution must retain "AST is just data" property. ie No API should be required to interpret it
• Idea: store :children as keys into the AST map
  • would be nice: (defn children [ast] ((apply juxt (:children ast)) ast))
    • but need to handle implicit do blocks: (defn children [ast](mapcat #(if (coll? %) % [%]) ((apply juxt (:children ast)) ast)))
  • ticket: http://dev.clojure.org/jira/browse/CLJS-289
  • outstanding issue: interleaved bindings
• Alternate idea: all child nodes are moved from the top level into a map in :children
  • For "if" this would change {:op :if :env {env} :test test-expr :then then-expr :else else-expr :children [test-expr then-expr else-expr]} into {:op :if :env {env} :children {:test test-expr :then then-expr :else else-expr}} 
  • This idea doesn't address blocks or bindings.
  • dnolen: What about forms like let where :children is a bit complex?

  •  

    :children (into (vec (map :init bes))

                         (conj (vec statements) ret)) 

     

     

    acohen: I think that should become: {:op :let :children {:init [inits] :statements [statements] :ret ret}

     We might want to discuss whether the inits are truly a child here, at the moment I think they are though.

    

     

     
    dnolen: So if a :children value entry is a vector it's something you need to iterate over? What about :ret? So you'll always need to look at :children if you want to know :ret?

    

      
    acohen: Yes, if :children entry is a seq, it must be a seq of nodes. For :let, I forgot that this is something else I changed in CinC. I made bindings an :op.

    So it should actually look like:

    {:op :let 

     :children {:inits [{:op :binding :name x :children {:init init-expr}} 

                        ...] 

                :statements [{...} ...] 

                :ret ret}}

     

    dnolen: What about :ret? So you'll always need to look at :children if you want to know :ret?

     

    acohen: Yep, that's right. Tree traversal would _always_ go through :children, rather than having this separation of "syntax-aware walkers go through the nodes that they know the names of" and "generic walkers go through :children"

    
    

    bbloom: I think this approach suffers another issue: Generic walkers might need to know evaluation order. I should be able to post-walk the :childrens nodes to get a strict top-to-bottom, inside-out, left-to-right sequence of nodes, ignoring conditional and repeated evaluation. Otherwise, I need knowledge of nodes to tell if side effects from :init may happen before those from :statements

    
    

    acohen: Can we mandate that the children map be a map-like structure that preserves order?