<< Back to previous view

[CLJS-289] Represent ast :children as a vector of keys Created: 31/May/12  Updated: 27/Jul/13  Resolved: 05/Jun/12

Status: Closed
Project: ClojureScript
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Major
Reporter: Brandon Bloom Assignee: Unassigned
Resolution: Declined Votes: 0
Labels: patch, patch,

Attachments: Text File children-keys.patch    
Patch: Code


See discussion here: https://groups.google.com/d/topic/clojure-dev/vZLVKmKX0oc/discussion

Summary: Duplication of ast nodes in various keys and in :children is problematic for some users. In particular, it doesn't play nicely with printing. A solution is needed which preserves "The AST is data. Period."

The attached patch makes no changes to how the sub nodes are currently stored outside of the :children key. Instead, it replaces :children values with a vector of keys into the main ast node. This preserves child ordering and allows a children function to be defined as:

(defn children [ast]
(mapcat #(if (coll? %) % [%]) ((apply juxt (:children ast)) ast)))

The attached patch has two caveats: 1) Many (but not all?) blocks will now be present in the children hierarchy as 'do forms. 2) Interleaved forms are intentionally bugged with respect to ordering. The :children vector for those forms match the actual behavior, not the expected behavior. This can be fixed along with http://dev.clojure.org/jira/browse/CLJS-288

Comment by David Nolen [ 03/Jun/12 10:00 AM ]

the result of the discussion did not end with agreement on representing :children as a vector of keys

Comment by Brandon Bloom [ 03/Jun/12 11:24 AM ]

I realize that, but it was one approach suggested and seemed entirely viable, so I tried it. From what I can tell, it seems like a solution that meets all of the criteria that came up during the discussion.

Did I overlook a requirement?

Who is currently using :children and could weigh in on whether or not this still meets their needs?

Comment by Jonas Enlund [ 03/Jun/12 11:52 AM ]

I'm using :children and I don't think this patch (currently) meets my needs. At least {:op :let ...} is broken IMO. (something like `(map :init bes)` is missing from the patch)

Comment by Brandon Bloom [ 03/Jun/12 12:09 PM ]

Ah OK, you're right. It's the same problem there that I ran into with :statements and analyze-block: There is a pseudo AST node that needs to be traversed down into.

The easy fix for that here would be to merge {:children [:init]} into each binding, but the binding hash will be missing :op and :form. For analyze-block, I was able to use :op :do and :form (list 'do ...), but there isn't an obvious analogy here without inventing a :binding op or relaxing the requirement for :op and :form.

Interestingly, each successive binding can be treated as a single nested binding. What if we defined let as a macro which expands to a series of let1 forms? (let [x 1 y 2] (* x y)) --> (let1 [x 1] (let1 [y 2] (* x y))

That may increase the depth of the AST, but it would really simplify traversal into binding clauses. Each let op would have :name, :init, and children as [:init].

In general, it may be worth while to consider doing the same thing with the various analyze-blocks situations, such that 'do is the only place multiple statements can occur.

Comment by Brandon Bloom [ 03/Jun/12 12:16 PM ]

Er, I mean: a hypothetical let1 op would have children [:init :statements :ret]

However, if you also expanded the implicit do blocks, you'd be able to simplify to [:init :body] or something like that.

Comment by Brandon Bloom [ 03/Jun/12 12:34 PM ]

Forgive me for repeatedly commenting, but it also occurs to me that you can change 'do to a macro which expands to a series of 'do2 forms:

(do x y z) --> (do2 x (do2 y z)) or (do2 (do2 x y) z)

That do2 op could have children [:left :right] and all other :statements and :ret children could be simplified down to 'do2 expansions.

With that in mind, the children fn becomes simply (defn children [ast] ((apply juxt (:children ast)) ast)) and a lot of analyze and emit code gets much simpler by not having to map over many collections all over the place.

Kinda a wild idea and probably not the right forum for it, but worth suggesting. Thoughts?

Comment by David Nolen [ 04/Jun/12 11:35 AM ]

I see little benefit to changing core macros. I also see no problem with creating a :binding ast node.

Comment by Jonas Enlund [ 05/Jun/12 12:44 AM ]

Every node (i.e. an map with :op, :form and :env keys, called an "Expression Object" in the docstring for analyze) in ClojureScript corresponds to a self-contained expression. A binding form is not self-contained, it is a part of the let expression.

Another similar example is functions. There is a node {:op :fn ...} but there is no {:op :fn-method} even thou there are maps under the :methods key describing function methods. The same argument goes for this: A function method is not self-contained, it is part of the function and should not be a node.

The nodes (expression objects) which make up the ClojureScript AST seems to be really well thought out and I would be careful in making the proposed change.

Comment by David Nolen [ 05/Jun/12 8:09 AM ]

Agreed I think it's far too early to have a ticket for this. Confluence page first.

Comment by Brandon Bloom [ 29/Aug/12 12:09 AM ]

Design page here: http://dev.clojure.org/display/design/AST+children

Generated at Wed Apr 16 20:27:45 CDT 2014 using JIRA 4.4#649-r158309.