Package org.variantsync.diffdetective.variation.diff

Class DiffNode<L extends Label>

java.lang.Object
org.variantsync.diffdetective.variation.diff.DiffNode<L>
Type Parameters:
L - The type of label stored in this node.
All Implemented Interfaces:
HasNodeType
public class DiffNode<L extends Label> extends Object implements HasNodeType
Implementation of a node in a VariationDiff. A DiffNode represents a single node within a variation tree diff (according to our ESEC/FSE'22 paper), but is specialized to the target domain of preprocessor-based software product lines. Thus, opposed to the generic mathematical model of variation tree diffs, a DiffNode always stores lines of text, line numbers, and child ordering information as its label. Each DiffNode may be edited according to its DiffType and represents a source code element according to its NodeType. DiffNode's store parent and child information to build a graph.
Author:
Paul Bittner, Sören Viegener, Benjamin Moosherr

  • Field Details

    • diffType

      public DiffType diffType
      The diff type of this node, which determines if this node represents an inserted, removed, or unchanged element in a diff.

    • label

      public final 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).

    • from

      private DiffLineNumber from

    • to

      private DiffLineNumber to

    • featureMapping

      private org.prop4j.Node featureMapping

    • stateBefore

      private final DiffNode.TimeDependentState<L extends Label> stateBefore

    • stateAfter

      private final DiffNode.TimeDependentState<L extends Label> stateAfter

  • Constructor Details

    • DiffNode

      public DiffNode(DiffType diffType, NodeType nodeType, DiffLineNumber fromLines, DiffLineNumber toLines, org.prop4j.Node featureMapping, L label)
      Creates a DiffNode with the given parameters.
      Parameters:
      diffType - The type of change made to this node.
      nodeType - The type of this node (i.e., mapping or artifact).
      fromLines - The starting line number of the corresponding text.
      toLines - The ending line number of the corresponding text.
      featureMapping - The formula stored in this node. Should be null for artifact nodes.
      label - The label of this node.

    • DiffNode

      public DiffNode(DiffType diffType, DiffLineNumber fromLines, DiffLineNumber toLines, org.prop4j.Node featureMapping, VariationLabel<L> label)
      Creates a DiffNode with the given parameters.
      Parameters:
      diffType - The type of change made to this node.
      fromLines - The starting line number of the corresponding text.
      toLines - The ending line number of the corresponding text.
      featureMapping - The formula stored in this node. Should be null for artifact nodes.
      label - The label and type of this node.

  • Method Details

    • at

      private DiffNode.TimeDependentState<L> at(Time time)

    • createRoot

      public static <L extends Label> DiffNode<L> createRoot(L label)
      Creates a new root node. The root is a neutral annotation (i.e., its feature mapping is "true").

    • createArtifact

      public static DiffNode<DiffLinesLabel> createArtifact(DiffType diffType, DiffLineNumber fromLines, DiffLineNumber toLines, String code)
      Creates an artifact node with the given parameters. For parameter descriptions, see DiffNode(DiffType, NodeType, DiffLineNumber, DiffLineNumber, Node, L). The code parameter will be set as the node's label by splitting it into lines.

    • createArtifact

      public static <L extends Label> DiffNode<L> createArtifact(DiffType diffType, DiffLineNumber fromLines, DiffLineNumber toLines, L label)
      The same as createArtifact(DiffType, DiffLineNumber, DiffLineNumber, String) but with a generic label.

    • getLabel

      public L getLabel()
      Returns the lines in the diff that are represented by this DiffNode as a single text.

    • setLabel

      public void setLabel(L newLabel)
      Sets the lines in the diff that are represented by this DiffNode to the given code. Lines are identified by linebreak characters.

    • getIfNode

      public DiffNode<L> getIfNode(Time time)
      Gets the first if node in the path from the root to this node at the time time.
      Returns:
      The first if node in the path to the root at the time time

    • getDepth

      public int getDepth(Time time)
      Gets the length of the path from the root to this node at the time time.
      Returns:
      the depth of the this node in the diff tree at the time time

    • beforePathEqualsAfterPath

      public boolean beforePathEqualsAfterPath()
      Returns true iff the path's in parent direction following the before parent and after parent are the very same.

    • getTotalNumberOfChildren

      public int getTotalNumberOfChildren()
      Returns the number of unique child nodes.

    • getChangeAmount

      public int getChangeAmount(Time time)
      Gets the amount of nodes on the path from the root to this node which only exist at the time time.

    • addBelow

      public void addBelow(DiffNode<L> newBeforeParent, DiffNode<L> newAfterParent)
      Adds this subtree below the given parents. Inverse of drop.
      Parameters:
      newBeforeParent - Node that should be this node's before parent. May be null.
      newAfterParent - Node that should be this node's after parent. May be null.

    • drop

      public void drop()
      Removes this subtree from its parents. Inverse of addBelow.

    • drop

      public void drop(Time time)
      Removes this subtree from its parents at the time time.

    • indexOfChild

      public int indexOfChild(DiffNode<L> child, Time time)
      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.

    • insertChild

      public void insertChild(DiffNode<L> child, int index, Time time)
      Insert child as child at the time time at the position index.

    • addChild

      public void addChild(DiffNode<L> child, Time time)
      The same as insertChild(org.variantsync.diffdetective.variation.diff.DiffNode<L>, int, org.variantsync.diffdetective.variation.diff.Time) but puts the node at the end of the children list instead of inserting it at a specific index.

    • addChildren

      public void addChildren(Collection<DiffNode<L>> children, Time time)
      Adds all given nodes at the time time as children using addChild(org.variantsync.diffdetective.variation.diff.DiffNode<L>, org.variantsync.diffdetective.variation.diff.Time).
      Parameters:
      children - Nodes to add as children.
      time - whether to add children before or after the edit

    • removeChild

      public void removeChild(DiffNode<L> child, Time time)
      Removes the given node from this node's children before or after the edit. The node might still remain a child after or before the edit.
      Parameters:
      child - the child to remove
      time - whether child should be removed before or after the edit

    • removeChildren

      public void removeChildren(Collection<DiffNode<L>> childrenToRemove)
      Removes all given children for all times. None of the given nodes will be a child, neither before nor after the edit, afterwards.
      Parameters:
      childrenToRemove - Nodes that should not be children of this node anymore.

    • removeChildren

      public List<DiffNode<L>> removeChildren(Time time)
      Removes all children before or after the edit. Afterwards, this node will have no children at the given time.
      Parameters:
      time - whether to remove all children before or after the edit
      Returns:
      All removed children.

    • stealChildrenOf

      public void stealChildrenOf(Time time, DiffNode<L> other)
      Removes all children from the given node and adds them as children to this node at the given time. The given node will have no children afterwards at the given time.
      Parameters:
      other - The node whose children should be stolen for the given time.

    • stealChildrenOf

      public void stealChildrenOf(DiffNode<L> other)
      Removes all children from the given node and adds them as children to this node (at all times). The given node will have no children afterwards.
      Parameters:
      other - The node whose children should be stolen.

    • split

      public DiffNode<L> split(Time time)
      Splits an unmodified node into a removed and an added node. Only one new node is created. Depending on time, this is changed into DiffType.ADD for Time.BEFORE or DiffType.REM for Time.AFTER.
      Parameters:
      time - decides which node is created
      Returns:
      the new node that exists at time time.

    • join

      public void join(DiffNode<L> other)
      Merges other into this node. other is removed from the graph and this node inherits all of its edges. This node and other need to be compatible (exist at different times and have the same node type and compatible labels).

      Both this and other must not be the root.

      Parameters:
      other - the node which is removed from the graph

    • replaceChild

      public void replaceChild(DiffNode<L> oldChild, DiffNode<L> newChild, Time time)
      Replaces a child of this node with another node.

      If oldChild is not a child of this node, nothing happens.

      Parameters:
      oldChild - the child that is removed
      newChild - the child that is inserted
      time - at which the child relation is changed

    • getParent

      public DiffNode<L> getParent(Time time)
      Returns the parent of this node before or after the edit.

    • getFromLine

      public DiffLineNumber getFromLine()
      Returns the starting line number of this node's corresponding text block.

    • setFromLine

      public void setFromLine(DiffLineNumber from)

    • getToLine

      public DiffLineNumber getToLine()
      Returns the end line number of this node's corresponding text block. The line number is exclusive (i.e., it points 1 behind the last included line).

    • setToLine

      public void setToLine(DiffLineNumber to)

    • getLinesInDiff

      public LineRange getLinesInDiff()
      Returns the range of line numbers of this node's corresponding source code in the text-based diff.
      See Also:

    • getLinesAtTime

      public LineRange getLinesAtTime(Time time)
      Returns the range of line numbers of this node's corresponding source code before or after the edit.

    • setLinesAtTime

      public void setLinesAtTime(LineRange lineRange, Time time)
      Returns the range of line numbers of this node's corresponding source code before or after the edit.

    • getFormula

      public org.prop4j.Node getFormula()
      Returns the formula that is stored in this node. The formula is null for artifact nodes (i.e., NodeType.ARTIFACT). The formula is not null for mapping nodes
      See Also:

    • setFormula

      public void setFormula(org.prop4j.Node featureMapping)

    • getChildOrder

      public List<DiffNode<L>> getChildOrder(Time time)
      Returns the order of the children at time.

    • getAllChildrenStream

      public Stream<DiffNode<L>> getAllChildrenStream()
      Returns an efficient stream representation of all direct children without duplicates. In particular, children which are both before and after children of this node are only contained once. The order of the children is unspecified.

    • getAllChildren

      public Iterable<DiffNode<L>> getAllChildren()
      Returns an efficient iterable representation of all direct children without duplicates. Note: The returned iterable can only be traversed once.
      See Also:

    • getAllChildrenSet

      public Set<DiffNode<L>> getAllChildrenSet()
      Returns a new set with all children of this node without duplicates.
      See Also:

    • getFeatureMapping

      public org.prop4j.Node getFeatureMapping(Time time)
      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 (+ its extension to time for variation tree diffs described in Section 3.1).
      Parameters:
      time - Whether to return the feature mapping clauses before or after the edit.
      Returns:
      The feature mapping of this node for the given parent edges.

    • getPresenceCondition

      public org.prop4j.Node getPresenceCondition(Time time)
      Returns the presence condition of this node before or after the edit. See Equation (2) in our paper (+ its extension to time for variation tree diffs described in Section 3.1).
      Parameters:
      time - Whether to return the presence condition before or after the edit.
      Returns:
      The presence condition of this node for the given parent edges.

    • isChild

      public boolean isChild(DiffNode<L> child)
      Returns true iff this node is the before or after parent of the given node.

    • isChild

      public boolean isChild(DiffNode<L> child, Time time)
      Returns true iff this node is the parent of the given node at the given time.

    • isLeaf

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

    • isRem

      public boolean isRem()
      Returns true iff this node represents a removed element.
      See Also:

    • isNon

      public boolean isNon()
      Returns true iff this node represents an unchanged element.
      See Also:

    • isAdd

      public boolean isAdd()
      Returns true iff this node represents an inserted element.
      See Also:

    • getDiffType

      public DiffType getDiffType()
      Returns the diff type of this node.

    • getNodeType

      public NodeType getNodeType()
      Description copied from interface: HasNodeType
      Returns the type of this node.
      Specified by:
      getNodeType in interface HasNodeType

    • isRoot

      public boolean isRoot()
      Returns true if this node is a root node (has no parents).

    • getID

      public int getID()
      Returns:
      An integer that uniquely identifiers this DiffNode within its patch. From the returned id a new node with all essential attributes reconstructed can be obtained by using fromID(int, java.lang.String). Note that only 26 bits of the line number are encoded, so if the line number is bigger than 2^26, this id will no longer be unique.

    • fromID

      public static DiffNode<DiffLinesLabel> fromID(int id, String label)
      Reconstructs a node from the given id and sets the given label. An id uniquely determines a node's getNodeType(), diffType, and line number in the diff. 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 DiffNode.

    • assertConsistency

      public void assertConsistency()
      Checks that the VariationDiff is in a valid state. In particular, this method checks that all edges are well-formed (e.g., edges can be inconsistent because edges are double-linked). This method also checks that a node with exactly one parent was edited, and that a node with exactly two parents was not edited. To check all children recursively, use VariationDiff.assertConsistency().
      Throws:
      AssertionError - when an inconsistency is detected.
      See Also:

    • projection

      public Projection<L> projection(Time time)
      Returns a view of this DiffNode as a variation node at the time time.

      See the project function in section 3.1 of our paper.

    • unchangedFlat

      public static <T extends VariationNode<T, L>, L extends Label> DiffNode<L> unchangedFlat(VariationNode<T,L> variationNode)
      Transforms a VariationNode into a DiffNode by diffing variationNode to itself. Acts on only the given node and does not perform recursive translations.

    • unchanged

      public static <T extends VariationNode<T, L1>, L1 extends Label, L2 extends Label> DiffNode<L2> unchanged(Function<? super T,DiffNode<L2>> convert, VariationNode<T,L1> variationNode)
      Transforms a VariationNode into a DiffNode by diffing variationNode to itself. Recursively translates all children. This is the inverse of projection(org.variantsync.diffdetective.variation.diff.Time) iff the original DiffNode wasn't modified (all node had a diff type of DiffType.NON).
      Parameters:
      convert - A function to translate single nodes (without their hierarchy).

    • deepCopy

      public DiffNode<L> deepCopy()

    • deepCopy

      public DiffNode<L> deepCopy(HashMap<DiffNode<L>,DiffNode<L>> oldToNew)

    • shallowCopy

      public DiffNode<L> shallowCopy()

    • makeUnchanged

      public void makeUnchanged()
      Turns this node into a node with DiffType DiffType.NON. To retain consistency of the variation diff, this node will also ensure that this node will have a parent at all times. To this end, the parent of this node will also be made unchanged if necessary, potentially making some or all ancestors of this node unchanged recursively. This method has no effect when this node is already unchanged.

    • unchanged

      public static <T extends VariationNode<T, L>, L extends Label> DiffNode<L> unchanged(VariationNode<T,L> variationNode)
      Transforms a VariationNode into a DiffNode by diffing variationNode to itself. Recursively translates all children. This is the inverse of projection(org.variantsync.diffdetective.variation.diff.Time) iff the original DiffNode wasn't modified (all node had a diff type of DiffType.NON).

    • isSameAs

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

    • isSameAs

      private static <L extends Label> boolean isSameAs(DiffNode<L> a, DiffNode<L> b, Set<DiffNode<L>> visited)

    • isSameAsIgnoringLineNumbers

      public boolean isSameAsIgnoringLineNumbers(DiffNode<L> other)
      Returns true if this subtree is exactly equal to other except for line numbers and other metadata in labels. This equality is a weaker equality than isSameAs(DiffNode) (i.e., whenever isSameAs returns true, so does isSameAsIgnoringLineNumbers). Labels of DiffNodes are compared via Label.observablyEqual(Label, Label). This check uses equality checks instead of identity.

    • isSameAsIgnoringLineNumbers

      private static <L extends Label> boolean isSameAsIgnoringLineNumbers(DiffNode<L> a, DiffNode<L> b, Set<DiffNode<L>> visited)

    • toString

      public String toString()
      Overrides:
      toString in class Object