Package org.variantsync.diffdetective.variation.tree

Class VariationTreeNode<L extends Label>

java.lang.Object

org.variantsync.diffdetective.variation.tree.VariationNode<VariationTreeNode<L>,L>

org.variantsync.diffdetective.variation.tree.VariationTreeNode<L>

All Implemented Interfaces:

HasNodeType

public class VariationTreeNode<L extends Label>
extends VariationNode<VariationTreeNode<L>,L>

A single node in a variation tree.

A variation tree is a representation of source code in a software product line. Each node in such a tree is either an artifact or a mapping node. Artifacts represent source code which may be reused in multiple variants. In contrast, mappings do not contain source code of a specific variant. They store information about which variants contain the artifacts it has as children in the form of a feature mapping.

See definition 2.2 of our ESEC/FSE'22 paper for a mathematical formalization or variation trees. In contrast to this formalization, this implementation optimizes for variation trees obtained from source code annotated with the C preprocessor syntax. This mostly means that there is the additional NodeType.ELIF node type.

This class contains references to all of its children and its parent so all connected nodes of a variation tree can be reached through each node of the variation tree. Nevertheless, most of the time only node itself or its subtree (the reflexive hull of getChildren()) is meant when when referencing a VariationTreeNode. Use VariationTree to unambiguously refer to a whole variation tree.

If possible, algorithms should be using VariationNode instead of this concrete implementation. This allows the usage of a projection of a DiffNode instead of a concrete variation node.

To compare two variation trees use VariationDiff which uses the aforementioned DiffNodes.

Author:

Benjamin Moosherr

See Also:

• VariationTree
• VariationDiff
• DiffNode

Field Summary

Fields

Modifier and Type	Field	Description
private final List<VariationTreeNode<L>>	childOrder	The list for maintaining the order of all children of this node.
private org.prop4j.Node	featureMapping	The direct feature mapping of this node.
private VariationLabel<L>	label	The label together with the node type of this node, which determines the type of the represented element in the diff (e.g., mapping or artifact).
private LineRange	lineRange	The range of line numbers of this node's corresponding source code.
private VariationTreeNode<L>	parent	The parent of this node.

Constructor Summary

Constructors

Constructor	Description
VariationTreeNode(NodeType nodeType, org.prop4j.Node featureMapping, LineRange lineRange, L label)	Creates a new node of a variation tree.

Method Summary

Modifier and Type	Method	Description
void	addChild(VariationTreeNode<L> child)	The same as VariationNode.insertChild(T,int) but puts the node at the end of the children list instead of inserting it at a specific index.
static <L extends Label> VariationTreeNode<L>	createArtifact(LineRange lineRange, L label)	Convenience constructor for creating an artifact node of a VariationTree.
static <L extends Label> VariationTreeNode<L>	createRoot(L label)	Convenience constructor for creating the root of a VariationTree.
VariationTreeNode<L>	deepCopy()	Creates a deep copy of this node.
VariationTreeNode<L>	deepCopy(Map<VariationTreeNode<L>,VariationTreeNode<L>> oldToNew)	Creates a deep copy of this node.
static <L extends Label> VariationTreeNode<L>	fromID(int id, L label)	Reconstructs a node from the given id and label.
List<VariationTreeNode<L>>	getChildren()	Returns an unmodifiable list representing the children of this node.
org.prop4j.Node	getFormula()	Returns the formula that is stored in this node.
int	getID()	Returns an integer that uniquely identifiers this node within its variation tree.
L	getLabel()	Returns the label of this node.
LineRange	getLineRange()	Returns the range of line numbers of this node's corresponding source code.
NodeType	getNodeType()	Returns the node type of this node which determines the type of the represented element in the variation tree (e.g., mapping or artifact).
VariationTreeNode<L>	getParent()	Returns the parent of this node, or null if this node doesn't have a parent.
void	insertChild(VariationTreeNode<L> child, int index)	Adds a child before the given index to the children list of this node and sets its parent to this node.
void	removeAllChildren()	Removes all children of this node and sets their parent to null.
void	removeChild(VariationTreeNode<L> child)	Removes the given node from this node's children list and sets the parent of child to null.
void	setLabel(L newLabel)	Replaces the current label by newLabelLines.
void	setLineRange(LineRange lineRange)	Sets the range of line numbers of this node's corresponding source code.
private void	setParent(VariationTreeNode<L> newParent)	Sets newParent as the new parent of this node.
String	toString()
VariationTreeNode<L>	upCast()	Returns this instance as the derived class type T.

Methods inherited from class org.variantsync.diffdetective.variation.tree.VariationNode

addBelow, addChildren, anyMatch, assertConsistency, downCast, drop, forAllPreorder, forMeAndMyAncestors, getChildCount, getDepth, getFeatureMapping, getIfNode, getPresenceCondition, indexOfChild, isChild, isLeaf, isRoot, isSameAs, printSourceCode, removeChildren, shallowIsSameAs, stealChildrenOf, toVariationTree, toVariationTree

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface org.variantsync.diffdetective.variation.tree.HasNodeType

isAnnotation, isArtifact, isConditionalAnnotation, isElif, isElse, isIf

Field Details

label

private VariationLabel<L extends Label> label

The label together with the node type of this node, which determines the type of the represented element in the diff (e.g., mapping or artifact).

lineRange

private LineRange lineRange

The range of line numbers of this node's corresponding source code.

featureMapping

private org.prop4j.Node featureMapping

The direct feature mapping of this node.

This is null iff HasNodeType.isConditionalAnnotation() is false.

parent

private VariationTreeNode<L extends Label> parent

The parent of this node. It's null iff this node doesn't have a parent.

Invariant: Iff parent != null then parent.childOrder.contains(this).

childOrder

private final List<VariationTreeNode<L extends Label>> childOrder

The list for maintaining the order of all children of this node.

See Also:

• parent

Constructor Details

VariationTreeNode

public VariationTreeNode(NodeType nodeType,
 org.prop4j.Node featureMapping,
 LineRange lineRange,
 L label)

Creates a new node of a variation tree. The newly created node is not connected to any other nodes. The new node takes ownership of the given label without copying it. Beware of any further modifications to this list.

Parameters:

nodeType - the type of this node

featureMapping - the direct feature mapping of this node, has be non null iff nodeType.isConditionalAnnotation is true

lineRange - the line range of the code of label

label - a list of lines used as label

See Also:

• addChild(org.variantsync.diffdetective.variation.tree.VariationTreeNode<L>)
• VariationNode.addBelow(T)

Method Details

createRoot

public static <L extends Label>
VariationTreeNode<L> createRoot(L label)

Convenience constructor for creating the root of a VariationTree.

The newly created root has no children yet.

The root is a neutral annotation (i.e., its type if NodeType.IF and its feature mapping is "true"). The label of this node is empty and therefore the line numbers are invalid.

See Also:

• addChild(org.variantsync.diffdetective.variation.tree.VariationTreeNode<L>)

createArtifact

public static <L extends Label>
VariationTreeNode<L> createArtifact(LineRange lineRange,
 L label)

Convenience constructor for creating an artifact node of a VariationTree.

Parameters:

lineRange - the line range of the code of label

label - a list of lines used as label

See Also:

• VariationNode.addBelow(T)

upCast

public VariationTreeNode<L> upCast()

Description copied from class: VariationNode

Returns this instance as the derived class type T. The deriving class will only have to return this here but this can't be implemented in the base class. If some derived class can't implement this method by returning this, it probably violates the requirements for the type parameter T (namely that it' the derived class itself).

Specified by:

upCast in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

getNodeType

public NodeType getNodeType()

Description copied from class: VariationNode

Returns the node type of this node which determines the type of the represented element in the variation tree (e.g., mapping or artifact).

Specified by:

getNodeType in interface HasNodeType

Specified by:

getNodeType in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

See Also:

• HasNodeType

getLabel

public L getLabel()

Description copied from class: VariationNode

Returns the label of this node.

If HasNodeType.isArtifact() is true this may represent the source code of this artifact. Otherwise it may represent the preprocessor expression which was parsed to obtain VariationNode.getFormula(). In either case, this label may be an arbitrary value, selected according to the needs of the user of this class.

Specified by:

getLabel in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

setLabel

public void setLabel(L newLabel)

Replaces the current label by newLabelLines.

See Also:

• getLabel()

getLineRange

public LineRange getLineRange()

Description copied from class: VariationNode

Returns the range of line numbers of this node's corresponding source code.

Specified by:

getLineRange in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

See Also:

• VariationNode.setLineRange(LineRange)

setLineRange

public void setLineRange(LineRange lineRange)

Description copied from class: VariationNode

Sets the range of line numbers of this node's corresponding source code.

Specified by:

setLineRange in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

See Also:

• VariationNode.getLineRange()

getParent

public VariationTreeNode<L> getParent()

Description copied from class: VariationNode

Returns the parent of this node, or null if this node doesn't have a parent.

Specified by:

getParent in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

See Also:

• VariationNode.drop()
• VariationNode.addBelow(T)

setParent

private void setParent(VariationTreeNode<L> newParent)

Sets newParent as the new parent of this node.

This node must not have a parent yet.

getChildren

public List<VariationTreeNode<L>> getChildren()

Description copied from class: VariationNode

Returns an unmodifiable list representing the children of this node.

The following invariant has to hold for all nodes: for (var child : node.getChildren()) { Assert.assertTrue(node == child.getParent(node)) }

Specified by:

getChildren in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

See Also:

• VariationNode.isChild(T)
• VariationNode.addChild(T)
• VariationNode.removeChild(T)

addChild

public void addChild(VariationTreeNode<L> child)

Description copied from class: VariationNode

The same as VariationNode.insertChild(T,int) but puts the node at the end of the children list instead of inserting it at a specific index.

Specified by:

addChild in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

See Also:

• VariationNode.getChildren()

insertChild

public void insertChild(VariationTreeNode<L> child,
 int index)

Description copied from class: VariationNode

Adds a child before the given index to the children list of this node and sets its parent to this node.

When calling VariationNode.indexOfChild(T) with child the returned index will be index as long as the children list isn't modified.

Specified by:

insertChild in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

See Also:

• VariationNode.addChildren(java.util.Collection<T>)

removeChild

public void removeChild(VariationTreeNode<L> child)

Description copied from class: VariationNode

Removes the given node from this node's children list and sets the parent of child to null.

Specified by:

removeChild in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

See Also:

• VariationNode.removeChildren(java.util.Collection<T>)
• VariationNode.getChildren()

removeAllChildren

public void removeAllChildren()

Description copied from class: VariationNode

Removes all children of this node and sets their parent to null. Afterwards, this node will have no children.

Specified by:

removeAllChildren in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

getFormula

public org.prop4j.Node getFormula()

Description copied from class: VariationNode

Returns the formula that is stored in this node. The formula is not null for mapping nodes with annotations and null otherwise (NodeType.ARTIFACT, NodeType.ELSE).

If the type parameter T of this class is not a concrete variation tree, then the returned formula should be treated as unmodifiable to prevent undesired side effects (e.g., to DiffNodes).

Specified by:

getFormula in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

getID

public int getID()

Returns an integer that uniquely identifiers this node within its variation tree.

From the returned id a new node with all essential attributes (node type and start line number) can be reconstructed by using <L>fromID(int,L).

Note that this encoding assumes that line numbers fit into 26 bits.

Specified by:

getID in class VariationNode<VariationTreeNode<L extends Label>,L extends Label>

fromID

public static <L extends Label>
VariationTreeNode<L> fromID(int id,
 L label)

Reconstructs a node from the given id and label. The almost-inverse function is getID() but the conversion is not lossless.

Parameters:

id - the id from which to reconstruct the node

label - the label the node should have

Returns:

the reconstructed node

deepCopy

public VariationTreeNode<L> deepCopy()

Creates a deep copy of this node.

deepCopy

public VariationTreeNode<L> deepCopy(Map<VariationTreeNode<L>,VariationTreeNode<L>> oldToNew)

Creates a deep copy of this node.

The map oldToNew should be empty as it will be filled by this method. After the method call, the map keys will contain all nodes in this node's subtree (including this node). The corresponding values will be the nodes in the returned node's subtree (including the returned node), where each pair (k, v) denotes that v was cloned from k.

Parameters:

oldToNew - A map that memorizes the translation of individual nodes.

Returns:

A deep copy of this tree.

toString

public String toString()

Overrides:

toString in class Object