|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using Microsoft.CodeAnalysis.Text;
namespace Microsoft.CodeAnalysis.Differencing;
// Based on general algorithm described in
// "Change Detection in Hierarchically Structured Information"
// by Sudarshan S. Chawathe, Anand Rajaraman, Hector Garcia-Molina, and Jennifer Widom.
/// <summary>
/// Implements a tree differencing algorithm.
/// </summary>
/// <remarks>
/// Subclasses define relationships among tree nodes, and parameters to the differencing algorithm.
/// </remarks>
/// <typeparam name="TNode">Tree node.</typeparam>
public abstract class TreeComparer<TNode>
{
protected TreeComparer()
{
}
/// <summary>
/// Returns an edit script that transforms <paramref name="oldRoot"/> to <paramref name="newRoot"/>.
/// </summary>
public EditScript<TNode> ComputeEditScript(TNode oldRoot, TNode newRoot)
=> new Match<TNode>(oldRoot, newRoot, this, knownMatches: null).GetTreeEdits();
/// <summary>
/// Returns a match map of <paramref name="oldRoot"/> descendants to <paramref name="newRoot"/> descendants.
/// </summary>
public Match<TNode> ComputeMatch(TNode oldRoot, TNode newRoot, IEnumerable<KeyValuePair<TNode, TNode>>? knownMatches = null)
=> new(oldRoot, newRoot, this, knownMatches);
/// <summary>
/// Calculates the distance [0..1] of two nodes.
/// </summary>
/// <remarks>
/// The more similar the nodes the smaller the distance.
///
/// Used to determine whether two nodes of the same label match.
/// Even if 0 is returned the nodes might be slightly different.
/// </remarks>
public abstract double GetDistance(TNode oldNode, TNode newNode);
/// <summary>
/// Returns true if the specified nodes have equal values.
/// </summary>
/// <remarks>
/// Called with matching nodes (<paramref name="oldNode"/>, <paramref name="newNode"/>).
/// Return true if the values of the nodes are the same, or their difference is not important.
/// </remarks>
public abstract bool ValuesEqual(TNode oldNode, TNode newNode);
/// <summary>
/// The number of distinct labels used in the tree.
/// </summary>
protected internal abstract int LabelCount { get; }
/// <summary>
/// Returns an integer label corresponding to the given node.
/// </summary>
/// <remarks>Returned value must be within [0, LabelCount).</remarks>
protected internal abstract int GetLabel(TNode node);
/// <summary>
/// Returns N > 0 if the node with specified label can't change its N-th ancestor node, zero otherwise.
/// </summary>
/// <remarks>
/// 1st ancestor is the node's parent node.
/// 2nd ancestor is the node's grandparent node.
/// etc.
/// </remarks>
protected internal abstract int TiedToAncestor(int label);
/// <summary>
/// May return null if the <paramref name="node"/> is a leaf.
/// </summary>
protected internal abstract IEnumerable<TNode>? GetChildren(TNode node);
/// <summary>
/// Enumerates all descendant nodes of the given node in depth-first prefix order.
/// </summary>
protected internal abstract IEnumerable<TNode> GetDescendants(TNode node);
/// <summary>
/// Returns a parent for the specified node.
/// </summary>
protected internal abstract bool TryGetParent(TNode node, [MaybeNullWhen(false)] out TNode parent);
internal TNode GetParent(TNode node)
{
var hasParent = TryGetParent(node, out var parent);
Debug.Assert(hasParent);
return parent!;
}
internal bool TryGetAncestor(TNode node, int level, [MaybeNullWhen(false)] out TNode ancestor)
{
while (level > 0)
{
if (TryGetParent(node, out var parent))
{
node = parent;
}
else
{
ancestor = default;
return false;
}
level--;
}
ancestor = node;
return true;
}
/// <summary>
/// Return true if specified nodes belong to the same tree.
/// </summary>
protected internal abstract bool TreesEqual(TNode oldNode, TNode newNode);
/// <summary>
/// Returns the position of the node.
/// </summary>
protected internal abstract TextSpan GetSpan(TNode node);
}
|