Package org.variantsync.diffdetective.variation.tree

Class VariationNode<T extends VariationNode<T,L>,L extends Label>

java.lang.Object
org.variantsync.diffdetective.variation.tree.VariationNode<T,L>
Type Parameters:
T - the derived type (the type extending this class)
L - The type of label stored in this tree.
All Implemented Interfaces:
HasNodeType
Direct Known Subclasses:
Projection, VariationTreeNode
public abstract class VariationNode<T extends VariationNode<T,L>,L extends Label> extends Object implements HasNodeType
A base class for views of a node in a variation tree.

Provides common methods for querying variation trees and changing their structure. This class doesn't provide mutation methods for attributes which may be shared between different underlying nodes (for example a projection of a DiffNode). Most prominently, there are no methods to change the type or the label of this node.

There are many methods which are not abstract. These are convenience methods or algorithms acting on variation nodes where a separate class may be undesirable (for example because they are quite common or because the calling syntax node.algorithm() makes more sense than the alternative Algorithm.run(node)).

Author:
Benjamin Moosherr
See Also:

  • Constructor Details

    • VariationNode

      public VariationNode()

  • Method Details

    • upCast

      public abstract T upCast()
      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).

    • downCast

      public VariationNode<T,L> downCast()
      Returns this instance as a VariationNode. This is only useful for accessing private members inside of VariationNode. These can't be accessed if the type of the variable of this instance is T so a down cast is required. This function only exists to document this necessity and make it more readable.

    • getNodeType

      public abstract 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).
      Specified by:
      getNodeType in interface HasNodeType
      See Also:

    • getLabel

      public abstract L getLabel()
      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 getFormula(). In either case, this label may be an arbitrary value, selected according to the needs of the user of this class.

    • getLineRange

      public abstract LineRange getLineRange()
      Returns the range of line numbers of this node's corresponding source code.
      See Also:

    • setLineRange

      public abstract void setLineRange(LineRange lineRange)
      Sets the range of line numbers of this node's corresponding source code.
      See Also:

    • getParent

      public abstract T getParent()
      Returns the parent of this node, or null if this node doesn't have a parent.
      See Also:

    • getChildren

      public abstract List<T> getChildren()
      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)) }

      See Also:

    • isRoot

      public boolean isRoot()
      Returns true iff this node has no parent.
      See Also:

    • isLeaf

      public boolean isLeaf()
      Returns true iff this node has no children.
      See Also:

    • getChildCount

      public int getChildCount()
      Returns the number of child nodes.

      Note: This is O(n) for Projection.

      See Also:

    • getDepth

      public int getDepth()
      Computes the length of the path from the root node to this node.

    • getIfNode

      public T getIfNode()
      Returns the first if node in the path from this node upwards to the root.

    • isChild

      public boolean isChild(T child)
      Returns true iff this node is the parent of the given node.
      See Also:

    • indexOfChild

      public int indexOfChild(T child)
      Returns the index of the given child in the list of children of this node. Returns -1 if the given node is not a child of this node.

      Warning: If this is a Projection, then the returned index may be different to the index returned by DiffNode.indexOfChild(org.variantsync.diffdetective.variation.diff.DiffNode<L>, org.variantsync.diffdetective.variation.diff.Time).

      See Also:

    • addChild

      public abstract void addChild(T child)
      The same as insertChild(T,int) but puts the node at the end of the children list instead of inserting it at a specific index.
      Throws:
      IllegalArgumentException - if child already has a parent
      See Also:

    • insertChild

      public abstract void insertChild(T child, int index)
      Adds a child before the given index to the children list of this node and sets its parent to this node.

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

      Throws:
      IllegalArgumentException - if child already has a parent
      See Also:

    • addChildren

      public void addChildren(Collection<T> children)
      Adds the given nodes in traversal order as children using addChild(T). *
      Throws:
      IllegalArgumentException - if any child of children already has a parent

    • removeChild

      public abstract void removeChild(T child)
      Removes the given node from this node's children list and sets the parent of child to null.
      Throws:
      IllegalArgumentException - if childe is not a child of this node
      See Also:

    • removeChildren

      public void removeChildren(Collection<T> childrenToRemove)
      Removes the given nodes from the children list using removeChild(T).
      Throws:
      IllegalArgumentException - if any child in childrenToRemove is not a child of this node
      See Also:

    • removeAllChildren

      public abstract void removeAllChildren()
      Removes all children of this node and sets their parent to null. Afterwards, this node will have no children.

    • addBelow

      public void addBelow(T parent)
      Adds this subtree below the given parent. Inverse of drop().
      Throws:
      IllegalArgumentException - if this node already has a parent
      See Also:

    • drop

      public void drop()
      Removes this subtree from its parents by removing it as child from its parent and settings the parent of this node to null. Inverse of addBelow(T).
      See Also:

    • stealChildrenOf

      public void stealChildrenOf(T other)
      Removes all children from the given node and adds them as children to this node. The order of the children is preserved. The given node will have no children afterwards.
      Parameters:
      other - The node whose children should be stolen.
      See Also:

    • getFormula

      public abstract org.prop4j.Node getFormula()
      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).

    • getFeatureMappingClauses

      private List<org.prop4j.Node> getFeatureMappingClauses()
      Same as getFeatureMapping() but returns a list of formulas representing a conjunction.

    • getFeatureMapping

      public org.prop4j.Node getFeatureMapping()
      Returns the full feature mapping formula of this node.

      The feature mapping of an NodeType.IF node is its direct feature mapping. The feature mapping of NodeType.ELSE and NodeType.ELIF nodes is determined by all formulas in the respective if-elif-else chain. The feature mapping of an artifact node is the feature mapping of its parent. See Equation (1) in our paper.

      Returns:
      the feature mapping of this node

    • getPresenceConditionClauses

      private List<org.prop4j.Node> getPresenceConditionClauses()
      Returns the presence condition clauses of this node.
      Returns:
      a list representing a conjunction (i.e., all clauses should be combined with boolean AND)
      See Also:

    • getPresenceCondition

      public org.prop4j.Node getPresenceCondition()
      Returns the presence condition of this node. See Equation (2) in our paper.

    • forAllPreorder

      public void forAllPreorder(Consumer<T> action)
      Traverses all nodes in this subtree in preorder.

    • forMeAndMyAncestors

      public void forMeAndMyAncestors(Consumer<T> action)

    • anyMatch

      public boolean anyMatch(Predicate<? super T> condition)
      Checks whether any node in this subtree satisfies the given condition. The condition might not be invoked on every node in case a node is found.
      Parameters:
      condition - A condition to check on each node.
      Returns:
      True iff the given condition returns true for at least one node in this tree.

    • toVariationTree

      public VariationTreeNode<L> toVariationTree()
      Returns a copy of this variation tree in a concrete variation tree implementation. If the type parameter T of this class is VariationTreeNode then this is effectively a deep copy.

    • toVariationTree

      public VariationTreeNode<L> toVariationTree(Map<? super T,VariationTreeNode<L>> oldToNew)
      Returns a copy of this variation tree in a concrete variation tree implementation. If the type parameter T of this class is VariationTreeNode then this is effectively a deep copy.

      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.

    • assertConsistency

      public void assertConsistency()
      Checks that this node satisfies some easy to check invariants. In particular, this method checks that
      • if-chains are nested correctly,
      • the root is an NodeType.IF with the feature mapping "true",
      • the feature mapping is null iff isConditionalAnnotation is false and
      • all edges are well-formed (e.g., edges can be inconsistent because edges are double-linked).

      Some invariants are not checked. These include

      • There should be no cycles and
      • getID() should be unique in the whole variation tree.
      Throws:
      AssertionError - when an inconsistency is detected.
      See Also:

    • getID

      public abstract int getID()
      Returns an integer that uniquely identifies this node within its tree.

      Some attributes may be recovered from this ID but this depends on the derived class. For example VariationTreeNode.fromID(int, L) can recover getNodeType() and the start line number. Beware that Projection returns DiffNode.getID() so this id is not fully compatible with VariationTreeNode.getID().

    • printSourceCode

      public void printSourceCode(StringBuilder output)
      Unparses the labels of this subtree into output.

      This method assumes that all labels of this subtree represent source code lines.

    • isSameAs

      public boolean isSameAs(VariationNode<T,L> other)
      Returns true if this subtree is exactly equal to other. This check uses equality checks instead of identity.

    • shallowIsSameAs

      protected boolean shallowIsSameAs(VariationNode<T,L> other)
      Returns true if this node is exactly equal to other without checking any children. This check uses equality checks instead of identity.