Spork's current structural representation in PCS is insufficiently granular

[slarse]

There are some problems with the granularity of the PCS representation of the Spoon ASTs. In particular, involved nodes such as methods that have many types of children can have different children interfere with each other. For example, take this method.

int div(int numerator, int denominator) throws ArithmeticException {
    return numerator / denominator;
}

Currently, for each node, Spork just gets its direct children as the child list. This is fine for simple nodes, but with this method node there's a problem.

The direct children of the method node (not counting content such as modifiers and method name) are the return type, the parameters, the thrown types and the body. Now, if we simply represent this method node's child list like this:

int, int numerator, int denominator, ArithmeticException, { return numerator / denominator }, it makes unrelated syntactical elements adjacent to each other, such as the end of the parameter list and the beginning of the thrown types list. If we create two derivatives of the above method, adding a parameter in one and adding a thrown type in the other, there's an insert/insert conflict across syntactical boundaries.

int div(int numerator, int denominator) throws SomeOtherException, ArithmeticException {
    return numerator / denominator;
}

int div(int numerator, int denominator, int uselessParameter) throws ArithmeticException {
    return numerator / denominator;
}

Here, one child list will read ... int denominator, SomeOtherException, ArithmeticException, and the other int denominator, int uselessParameter, ArithmeticException, creating an insert/insert conflict. This is not great.

A solution to this problem is to add intermediate virtual nodes where necessary. For example, a method node should not have its parameters as direct children, but should instead have a parameters node which in turn has the parameter list as children. Spoon's roles can be used to determine where to put which thing.

Only nodes where this is a problem should have intermediate virtual nodes added, as otherwise the PCS representation will absolutely explode in size.

[monperrus]

A solution to this problem is to add intermediate virtual nodes where necessary. For example, a

method node should not have its parameters as direct children, but should instead have a parameters node which in turn has the parameter list as children. FYI, this is a design pattern we have used in Gumtree-Spoon several times. Maybe we should use it systematically.

[slarse]

FYI, this is a design pattern we have used in Gumtree-Spoon several times. Maybe we should use it systematically.

Probably something to that effect. I just realized this was a problem yesterday, can't believe I haven't considered this before. In theory, Spork could adopt the exact representation used in Gumtree-Spoon, even putting content values such as modifiers into the core merge. This is probably not desirable, however, as adding nodes to the core merge algorithm carries a heavy runtime cost. I tried introducing virtual nodes for all children of all elements, but this leads to a pretty massive performance hit with runtimes increasing by ~50%.

Instead, I have implemented a fix in #133 , which introduces virtual nodes for a select few elements. It's very easy to tune, introducing virtual nodes to a new type of CtElement is as simple as adding the appropriate interface to a list. This will also automatically adjust to changes in the Spoon metamodel as the virtual nodes are created dynamically based on what roles are available for the selected interfaces. Spork then creates intermediate virtual nodes which are only present during the merge process, and "collapses" the virtual nodes when interpreting the PCS triples into a tree.