|
// 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.
#nullable disable
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;
using Microsoft.CodeAnalysis;
namespace Microsoft.VisualStudio.LanguageServices.Implementation.CodeModel
{
internal partial class AbstractCodeModelService
{
protected abstract AbstractCodeModelEventCollector CreateCodeModelEventCollector();
protected abstract class AbstractCodeModelEventCollector
{
private const int MaxChildDelta = 5;
protected readonly AbstractCodeModelService CodeModelService;
protected AbstractCodeModelEventCollector(AbstractCodeModelService codeModelService)
=> this.CodeModelService = codeModelService;
protected abstract void CollectCore(SyntaxNode oldRoot, SyntaxNode newRoot, CodeModelEventQueue eventQueue);
protected abstract void EnqueueAddEvent(SyntaxNode node, SyntaxNode parent, CodeModelEventQueue eventQueue);
protected abstract void EnqueueRemoveEvent(SyntaxNode node, SyntaxNode parent, CodeModelEventQueue eventQueue);
protected abstract void EnqueueChangeEvent(SyntaxNode node, SyntaxNode parent, CodeModelEventType eventType, CodeModelEventQueue eventQueue);
public Queue<CodeModelEvent> Collect(SyntaxTree oldTree, SyntaxTree newTree)
{
var queue = new Queue<CodeModelEvent>();
var eventQueue = new CodeModelEventQueue(queue);
CollectCore(oldTree.GetRoot(CancellationToken.None), newTree.GetRoot(CancellationToken.None), eventQueue);
return queue;
}
protected delegate bool NodeComparison<TNode, TParent>(
TNode oldNode, TNode newNode,
TParent newNodeParent,
CodeModelEventQueue eventQueue)
where TNode : SyntaxNode
where TParent : SyntaxNode;
protected enum DeclarationChange { WholeDeclaration, NameOnly }
protected bool CompareChildren<TNode, TParent>(
NodeComparison<TNode, TParent> compare,
IReadOnlyList<TNode> oldChildren,
IReadOnlyList<TNode> newChildren,
TParent newNodeParent,
CodeModelEventType eventType,
CodeModelEventQueue eventQueue)
where TNode : SyntaxNode
where TParent : SyntaxNode
{
var oldCount = oldChildren.Count;
var newCount = newChildren.Count;
if (oldCount == newCount)
{
return FindDifferentChild(compare, oldChildren, newChildren, newNodeParent, eventQueue);
}
else if (Math.Abs(oldCount - newCount) > MaxChildDelta)
{
// We got two discrepancies, enqueue element changed node for containing node
EnqueueChangeEvent(newNodeParent, null, eventType, eventQueue);
}
else
{
if (oldCount > newCount)
{
FindRemovedChild(compare, oldChildren, newChildren, newNodeParent, oldCount - newCount, eventQueue);
}
else
{
FindAddedChild(compare, oldChildren, newChildren, newNodeParent, newCount - oldCount, eventQueue);
}
}
return false;
}
protected DeclarationChange CompareRenamedDeclarations<TNode, TParent>(
NodeComparison<TNode, TParent> compare,
IReadOnlyList<TNode> oldChildren,
IReadOnlyList<TNode> newChildren,
SyntaxNode oldNode,
SyntaxNode newNode,
TParent newNodeParent,
CodeModelEventQueue eventQueue)
where TNode : SyntaxNode
where TParent : SyntaxNode
{
var oldCount = oldChildren.Count;
var newCount = newChildren.Count;
if (oldCount == newCount)
{
// We now check the children of the old and new types against each other. If any of them have changed,
// it means that the old type has essentially been removed and a new one added.
for (var i = 0; i < oldCount; i++)
{
if (!compare(oldChildren[i], newChildren[i], newNodeParent, null))
{
EnqueueRemoveEvent(oldNode, newNodeParent, eventQueue);
EnqueueAddEvent(newNode, newNodeParent, eventQueue);
// Report that the whole declaration has changed
return DeclarationChange.WholeDeclaration;
}
}
// The children are all the same, so only the name has changed.
return DeclarationChange.NameOnly;
}
else
{
// Since the number of members is different, essentially the old type has been removed, and a new one added.
EnqueueRemoveEvent(oldNode, newNodeParent, eventQueue);
EnqueueAddEvent(newNode, newNodeParent, eventQueue);
// Report that the whole declaration has changed
return DeclarationChange.WholeDeclaration;
}
}
// Finds the child node which is different OR enqueues a unknown on containing node.
private bool FindDifferentChild<TNode, TParent>(
NodeComparison<TNode, TParent> compare,
IReadOnlyList<TNode> oldChildren,
IReadOnlyList<TNode> newChildren,
TParent newNodeParent,
CodeModelEventQueue eventQueue)
where TNode : SyntaxNode
where TParent : SyntaxNode
{
Debug.Assert(oldChildren.Count == newChildren.Count);
var eventCount = eventQueue != null
? eventQueue.Count
: 0;
var hasChanges = false;
// Find first child that is different.
int i;
for (i = 0; i < oldChildren.Count; i++)
{
if (!compare(oldChildren[i], newChildren[i], newNodeParent, eventQueue))
{
hasChanges = true;
i++;
break;
}
}
// Look for a second different child. If there is one, we'll throw away any events from
// the first different child and enqueue an unknown event on the containing node.
for (; i < oldChildren.Count; i++)
{
if (!compare(oldChildren[i], newChildren[i], newNodeParent, null))
{
// rollback any events added by the first difference
if (eventQueue != null)
{
while (eventQueue.Count > eventCount)
{
eventQueue.Discard();
}
}
EnqueueChangeEvent(newNodeParent, null, CodeModelEventType.Unknown, eventQueue);
return false;
}
}
return !hasChanges;
}
private void FindAddedChild<TNode, TParent>(
NodeComparison<TNode, TParent> compare,
IReadOnlyList<TNode> oldChildren,
IReadOnlyList<TNode> newChildren,
TParent newNodeParent,
int delta,
CodeModelEventQueue eventQueue)
where TNode : SyntaxNode
where TParent : SyntaxNode
{
Debug.Assert(oldChildren.Count + delta == newChildren.Count);
// The strategy is to assume that all of the added children are contiguous.
// If that turns out not to be the case, an unknown change event is raised
// for the containing node.
var firstAdded = -1;
// Look for the first different child. If there is one, track that index as
// the first added node.
int oldIndex, newIndex;
for (oldIndex = 0, newIndex = 0; newIndex < newChildren.Count; oldIndex++, newIndex++)
{
if (oldIndex >= oldChildren.Count || !compare(oldChildren[oldIndex], newChildren[newIndex], newNodeParent, null))
{
firstAdded = newIndex;
newIndex += delta;
break;
}
}
// Look for a second different child. If there is one, we'll throw away any events from
// the first different child and enqueue an unknown event on the containing node.
for (; newIndex < newChildren.Count; oldIndex++, newIndex++)
{
if (!compare(oldChildren[oldIndex], newChildren[newIndex], newNodeParent, null))
{
EnqueueChangeEvent(newNodeParent, null, CodeModelEventType.Unknown, eventQueue);
return;
}
}
if (firstAdded >= 0)
{
for (var i = 0; i < delta; i++)
{
EnqueueAddEvent(newChildren[firstAdded + i], newNodeParent, eventQueue);
}
}
}
private void FindRemovedChild<TNode, TParent>(
NodeComparison<TNode, TParent> compare,
IReadOnlyList<TNode> oldChildren,
IReadOnlyList<TNode> newChildren,
TParent newNodeParent,
int delta,
CodeModelEventQueue eventQueue)
where TNode : SyntaxNode
where TParent : SyntaxNode
{
Debug.Assert(oldChildren.Count - delta == newChildren.Count);
// The strategy is to assume that all of the removed children are contiguous.
// If that turns out not to be the case, an unknown change event is raised
// for the containing node.
var firstRemoved = -1;
// Look for the first different child. If there is one, track that index as
// the first added node.
int oldIndex, newIndex;
for (oldIndex = 0, newIndex = 0; oldIndex < oldChildren.Count; oldIndex++, newIndex++)
{
if (newIndex >= newChildren.Count || !compare(oldChildren[oldIndex], newChildren[newIndex], newNodeParent, null))
{
firstRemoved = oldIndex;
oldIndex += delta;
break;
}
}
// Look for a second different child. If there is one, we'll throw away any events from
// the first different child and enqueue an unknown event on the containing node.
for (; oldIndex < oldChildren.Count; oldIndex++, newIndex++)
{
if (!compare(oldChildren[oldIndex], newChildren[newIndex], newNodeParent, null))
{
EnqueueChangeEvent(newNodeParent, null, CodeModelEventType.Unknown, eventQueue);
return;
}
}
if (firstRemoved >= 0)
{
for (var i = 0; i < delta; i++)
{
EnqueueRemoveEvent(oldChildren[firstRemoved + i], newNodeParent, eventQueue);
}
}
}
}
}
}
|