|
// 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;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using Microsoft.CodeAnalysis.Collections;
using Microsoft.CodeAnalysis.Formatting.Rules;
using Microsoft.CodeAnalysis.Shared.Collections;
using Microsoft.CodeAnalysis.Shared.Utilities;
using Microsoft.CodeAnalysis.Text;
using Roslyn.Utilities;
namespace Microsoft.CodeAnalysis.Formatting;
/// <summary>
/// this class maintain contextual information such as
/// indentation of current position, based token to follow in current position and etc.
/// </summary>
internal sealed partial class FormattingContext
{
private readonly AbstractFormatEngine _engine;
// interval tree for inseparable regions (Span to indentation data)
// due to dependencies, each region defined in the data can't be formatted independently.
private readonly ContextMutableIntervalTree<RelativeIndentationData, FormattingContextIntervalIntrospector> _relativeIndentationTree;
// interval tree for each operations.
// given a span in the tree, it returns data (indentation, anchor delta, etc) to be applied for the span
private readonly ContextMutableIntervalTree<IndentationData, FormattingContextIntervalIntrospector> _indentationTree;
private readonly ContextMutableIntervalTree<SuppressWrappingData, SuppressIntervalIntrospector> _suppressWrappingTree;
private readonly ContextMutableIntervalTree<SuppressSpacingData, SuppressIntervalIntrospector> _suppressSpacingTree;
private readonly ContextMutableIntervalTree<SuppressSpacingData, SuppressIntervalIntrospector> _suppressFormattingTree;
private readonly ContextMutableIntervalTree<AnchorData, FormattingContextIntervalIntrospector> _anchorTree;
// anchor token to anchor data map.
// unlike anchorTree that would return anchor data for given span in the tree, it will return
// anchorData based on key which is anchor token.
private readonly SegmentedDictionary<SyntaxToken, AnchorData> _anchorBaseTokenMap = [];
// hashset to prevent duplicate entries in the trees.
private readonly HashSet<TextSpan> _indentationMap = [];
private readonly HashSet<TextSpan> _suppressWrappingMap = [];
private readonly HashSet<TextSpan> _suppressSpacingMap = [];
private readonly HashSet<TextSpan> _suppressFormattingMap = [];
private readonly HashSet<TextSpan> _anchorMap = [];
// used for selection based formatting case. it contains operations that will define
// what indentation to use as a starting indentation. (we always use 0 for formatting whole tree case)
private List<IndentBlockOperation> _initialIndentBlockOperations = [];
public FormattingContext(AbstractFormatEngine engine, TokenStream tokenStream)
{
Contract.ThrowIfNull(engine);
Contract.ThrowIfNull(tokenStream);
_engine = engine;
TokenStream = tokenStream;
_relativeIndentationTree = new ContextMutableIntervalTree<RelativeIndentationData, FormattingContextIntervalIntrospector>(new FormattingContextIntervalIntrospector());
_indentationTree = new ContextMutableIntervalTree<IndentationData, FormattingContextIntervalIntrospector>(new FormattingContextIntervalIntrospector());
_suppressWrappingTree = new ContextMutableIntervalTree<SuppressWrappingData, SuppressIntervalIntrospector>(new SuppressIntervalIntrospector());
_suppressSpacingTree = new ContextMutableIntervalTree<SuppressSpacingData, SuppressIntervalIntrospector>(new SuppressIntervalIntrospector());
_suppressFormattingTree = new ContextMutableIntervalTree<SuppressSpacingData, SuppressIntervalIntrospector>(new SuppressIntervalIntrospector());
_anchorTree = new ContextMutableIntervalTree<AnchorData, FormattingContextIntervalIntrospector>(new FormattingContextIntervalIntrospector());
}
public void Initialize(
ChainedFormattingRules formattingRules,
SyntaxToken startToken,
SyntaxToken endToken,
CancellationToken cancellationToken)
{
var rootNode = this.TreeData.Root;
if (TokenStream.IsFormattingWholeDocument)
{
// if we are trying to format whole document, there is no reason to get initial context. just set
// initial indentation.
var data = new SimpleIndentationData(rootNode.FullSpan, indentation: 0);
_indentationTree.AddIntervalInPlace(data);
_indentationMap.Add(data.TextSpan);
return;
}
var initialContextFinder = new InitialContextFinder(TokenStream, formattingRules, rootNode);
var (indentOperations, suppressOperations) = initialContextFinder.Do(startToken, endToken);
if (indentOperations != null)
{
var indentationOperations = indentOperations;
var initialOperation = indentationOperations[0];
var baseIndentationFinder = new BottomUpBaseIndentationFinder(
formattingRules,
Options.TabSize,
Options.IndentationSize,
TokenStream,
_engine.HeaderFacts);
var initialIndentation = baseIndentationFinder.GetIndentationOfCurrentPosition(
rootNode,
initialOperation,
TokenStream.GetCurrentColumn, cancellationToken);
var data = new SimpleIndentationData(initialOperation.TextSpan, initialIndentation);
_indentationTree.AddIntervalInPlace(data);
_indentationMap.Add(data.TextSpan);
// hold onto initial operations
_initialIndentBlockOperations = indentationOperations;
}
foreach (var suppressOperation in suppressOperations)
this.AddInitialSuppressOperation(suppressOperation);
}
public void AddIndentBlockOperations(
SegmentedList<IndentBlockOperation> operations,
CancellationToken cancellationToken)
{
Contract.ThrowIfNull(operations);
// if there is no initial block operations
if (_initialIndentBlockOperations.Count <= 0)
{
// sort operations and add them to interval tree
operations.Sort(CommonFormattingHelpers.IndentBlockOperationComparer);
operations.Do(o =>
{
cancellationToken.ThrowIfCancellationRequested();
this.AddIndentBlockOperation(o);
});
return;
}
var baseSpan = _initialIndentBlockOperations[0].TextSpan;
// indentation tree must build up from inputs that are in right order except initial indentation.
// merge indentation operations from two places (initial operations for current selection, and nodes inside of selections)
// sort it in right order and apply them to tree
var count = _initialIndentBlockOperations.Count - 1 + operations.Count;
var mergedList = new List<IndentBlockOperation>(count);
// initial operations are already sorted, just add, no need to filter
for (var i = 1; i < _initialIndentBlockOperations.Count; i++)
{
mergedList.Add(_initialIndentBlockOperations[i]);
}
for (var i = 0; i < operations.Count; i++)
{
cancellationToken.ThrowIfCancellationRequested();
// filter out operations whose position is before the base indentation
var operationSpan = operations[i].TextSpan;
if (operationSpan.Start < baseSpan.Start ||
operationSpan.Contains(baseSpan))
{
continue;
}
mergedList.Add(operations[i]);
}
mergedList.Sort(CommonFormattingHelpers.IndentBlockOperationComparer);
mergedList.Do(o =>
{
cancellationToken.ThrowIfCancellationRequested();
this.AddIndentBlockOperation(o);
});
}
public void AddIndentBlockOperation(IndentBlockOperation operation)
{
var intervalTreeSpan = operation.TextSpan;
// don't add stuff if it is empty
if (intervalTreeSpan.IsEmpty ||
_indentationMap.Contains(intervalTreeSpan))
{
return;
}
// relative indentation case where indentation depends on other token
if (operation.IsRelativeIndentation)
{
Func<FormattingContext, IndentBlockOperation, SyntaxToken> effectiveBaseTokenGetter = operation.Option.IsOn(IndentBlockOption.RelativeToFirstTokenOnBaseTokenLine)
? static (self, operation) => self.TokenStream.FirstTokenOfBaseTokenLine(operation.BaseToken)
: static (self, operation) => operation.BaseToken;
Func<FormattingContext, IndentBlockOperation, SyntaxToken, int> relativeIndentationDeltaGetter = static (self, operation, effectiveBaseToken) =>
{
var baseIndentationDelta = operation.GetAdjustedIndentationDelta(self._engine.HeaderFacts, self.TreeData.Root, effectiveBaseToken);
return baseIndentationDelta * self.Options.IndentationSize;
};
// baseIndentation is calculated for the adjusted token if option is RelativeToFirstTokenOnBaseTokenLine
Func<FormattingContext, SyntaxToken, int> relativeIndentationBaseIndentationGetter =
static (self, effectiveBaseToken) => self.TokenStream.GetCurrentColumn(effectiveBaseToken);
// set new indentation
var inseparableRegionStartingPosition = effectiveBaseTokenGetter(this, operation).FullSpan.Start;
var relativeIndentationData = new RelativeIndentationData(this, inseparableRegionStartingPosition, intervalTreeSpan, operation, effectiveBaseTokenGetter, relativeIndentationDeltaGetter, relativeIndentationBaseIndentationGetter);
_indentationTree.AddIntervalInPlace(relativeIndentationData);
_relativeIndentationTree.AddIntervalInPlace(relativeIndentationData);
_indentationMap.Add(intervalTreeSpan);
return;
}
// absolute position case
if (operation.Option.IsOn(IndentBlockOption.AbsolutePosition))
{
_indentationTree.AddIntervalInPlace(new SimpleIndentationData(intervalTreeSpan, operation.IndentationDeltaOrPosition));
_indentationMap.Add(intervalTreeSpan);
return;
}
// regular indentation case where indentation is based on its previous indentation
var indentationData = _indentationTree.GetSmallestContainingInterval(operation.TextSpan.Start, 0);
if (indentationData == null)
{
// no previous indentation
var indentation = operation.IndentationDeltaOrPosition * Options.IndentationSize;
_indentationTree.AddIntervalInPlace(new SimpleIndentationData(intervalTreeSpan, indentation));
_indentationMap.Add(intervalTreeSpan);
return;
}
// get indentation based on its previous indentation
if (indentationData is not AdjustedIndentationData { BaseIndentationData: var baseIndentationData, Adjustment: var totalAdjustment })
{
(baseIndentationData, totalAdjustment) = (indentationData, 0);
}
totalAdjustment += operation.IndentationDeltaOrPosition * Options.IndentationSize;
IndentationData derived;
if (totalAdjustment == 0)
{
derived = baseIndentationData.WithTextSpan(intervalTreeSpan);
}
else if (baseIndentationData is SimpleIndentationData { Indentation: var baseIndentation })
{
derived = new SimpleIndentationData(intervalTreeSpan, baseIndentation + totalAdjustment);
}
else
{
derived = new AdjustedIndentationData(intervalTreeSpan, baseIndentationData, totalAdjustment);
}
// set new indentation
_indentationTree.AddIntervalInPlace(derived);
_indentationMap.Add(intervalTreeSpan);
}
public void AddInitialSuppressOperation(SuppressOperation operation)
{
// don't add stuff if it is empty
if (operation.TextSpan.IsEmpty)
return;
var onSameLine = TokenStream.TwoTokensOriginallyOnSameLine(operation.StartToken, operation.EndToken);
AddSuppressOperation(operation, onSameLine);
}
public void AddSuppressOperations(
SegmentedList<SuppressOperation> operations,
CancellationToken cancellationToken)
{
// TODO: think about a way to figure out whether it is already suppressed and skip the expensive check below.
foreach (var operation in operations)
{
cancellationToken.ThrowIfCancellationRequested();
// if an operation contains elastic trivia itself and the operation is not marked to ignore the elastic trivia
// ignore the operation
if (operation.ContainsElasticTrivia(TokenStream) && !operation.Option.IsOn(SuppressOption.IgnoreElasticWrapping))
continue;
var onSameLine = TokenStream.TwoTokensOriginallyOnSameLine(operation.StartToken, operation.EndToken);
AddSuppressOperation(operation, onSameLine);
}
}
private void AddSuppressOperation(SuppressOperation operation, bool onSameLine)
{
AddSpacingSuppressOperation(operation, onSameLine);
AddFormattingSuppressOperation(operation);
AddWrappingSuppressOperation(operation, onSameLine);
}
private void AddSpacingSuppressOperation(SuppressOperation operation, bool twoTokensOnSameLine)
{
// don't add stuff if it is empty
if (operation.TextSpan.IsEmpty)
{
return;
}
// we might need to merge bits with enclosing suppress flag
var option = operation.Option;
if (!option.IsMaskOn(SuppressOption.NoSpacing) || _suppressSpacingMap.Contains(operation.TextSpan))
{
return;
}
if (!(option.IsOn(SuppressOption.NoSpacingIfOnSingleLine) && twoTokensOnSameLine) &&
!(option.IsOn(SuppressOption.NoSpacingIfOnMultipleLine) && !twoTokensOnSameLine))
{
return;
}
var data = new SuppressSpacingData(operation.TextSpan);
_suppressSpacingMap.Add(operation.TextSpan);
_suppressSpacingTree.AddIntervalInPlace(data);
}
private void AddFormattingSuppressOperation(SuppressOperation operation)
{
// don't add stuff if it is empty
if (operation.TextSpan.IsEmpty)
{
return;
}
// we might need to merge bits with enclosing suppress flag
var option = operation.Option;
if (!option.IsOn(SuppressOption.DisableFormatting) || _suppressFormattingMap.Contains(operation.TextSpan))
{
return;
}
var data = new SuppressSpacingData(operation.TextSpan);
_suppressFormattingMap.Add(operation.TextSpan);
_suppressFormattingTree.AddIntervalInPlace(data);
}
private void AddWrappingSuppressOperation(SuppressOperation operation, bool twoTokensOnSameLine)
{
// don't add stuff if it is empty
if (operation.TextSpan.IsEmpty)
{
return;
}
var option = operation.Option;
if (!option.IsMaskOn(SuppressOption.NoWrapping) || _suppressWrappingMap.Contains(operation.TextSpan))
{
return;
}
if (!(option.IsOn(SuppressOption.NoWrappingIfOnSingleLine) && twoTokensOnSameLine) &&
!(option.IsOn(SuppressOption.NoWrappingIfOnMultipleLine) && !twoTokensOnSameLine))
{
return;
}
var ignoreElastic = option.IsMaskOn(SuppressOption.IgnoreElasticWrapping) ||
!operation.ContainsElasticTrivia(TokenStream);
var data = new SuppressWrappingData(operation.TextSpan, ignoreElastic: ignoreElastic);
_suppressWrappingMap.Add(operation.TextSpan);
_suppressWrappingTree.AddIntervalInPlace(data);
}
public void AddAnchorIndentationOperation(AnchorIndentationOperation operation)
{
// don't add stuff if it is empty
if (operation.TextSpan.IsEmpty ||
_anchorMap.Contains(operation.TextSpan) ||
_anchorBaseTokenMap.ContainsKey(operation.AnchorToken))
{
return;
}
// If the indentation changes on a line which other code is anchored to, adjust those other lines to reflect
// the same change in indentation. Note that we anchor to the first token on a line to account for common
// cases like the following code, where the `{` token is anchored to the `(` token of `()`:
//
// ↓ this space can be removed, which moves `(` one character to the left
// var x = Method( () =>
// {
// ↑ this `{` anchors to `var` instead of `(`, which prevents it from moving when `(` is moved
// });
//
// The calculation of true anchor token (which is always the first token on a line) is delayed to account
// for cases where the original anchor token is moved to a new line during a formatting operation.
var anchorToken = TokenStream.FirstTokenOfBaseTokenLine(operation.AnchorToken);
var originalSpace = TokenStream.GetOriginalColumn(anchorToken);
var data = new AnchorData(operation, anchorToken, originalSpace);
_anchorTree.AddIntervalInPlace(data);
_anchorBaseTokenMap.Add(operation.AnchorToken, data);
_anchorMap.Add(operation.TextSpan);
}
[Conditional("DEBUG")]
private static void DebugCheckEmpty<T, TIntrospector>(ContextMutableIntervalTree<T, TIntrospector> tree, TextSpan textSpan)
where TIntrospector : struct, IIntervalIntrospector<T>
{
var intervals = tree.GetIntervalsThatContain(textSpan.Start, textSpan.Length);
Contract.ThrowIfFalse(intervals.Length == 0);
}
public int GetBaseIndentation(SyntaxToken token)
=> GetBaseIndentation(token.SpanStart);
public int GetBaseIndentation(int position)
{
var indentationData = _indentationTree.GetSmallestContainingInterval(position, 0);
if (indentationData == null)
{
DebugCheckEmpty(_indentationTree, new TextSpan(position, 0));
return 0;
}
return indentationData.Indentation;
}
public IEnumerable<IndentBlockOperation> GetAllRelativeIndentBlockOperations()
=> _relativeIndentationTree.Algorithms.GetIntervalsThatIntersectWith(this.TreeData.StartPosition, this.TreeData.EndPosition, new FormattingContextIntervalIntrospector()).Select(i => i.Operation);
public bool TryGetEndTokenForRelativeIndentationSpan(SyntaxToken token, int maxChainDepth, out SyntaxToken endToken, CancellationToken cancellationToken)
{
endToken = default;
var depth = 0;
while (true)
{
cancellationToken.ThrowIfCancellationRequested();
if (depth++ > maxChainDepth)
{
return false;
}
var span = token.Span;
var indentationData = _relativeIndentationTree.GetSmallestContainingInterval(span.Start, 0);
if (indentationData == null)
{
// this means the given token is not inside of inseparable regions
endToken = token;
return true;
}
// recursively find the end token outside of inseparable regions
token = indentationData.EndToken.GetNextToken(includeZeroWidth: true);
if (token.RawKind == 0)
{
// reached end of tree
return true;
}
}
}
private AnchorData? GetAnchorData(SyntaxToken token)
{
var span = token.Span;
var anchorData = _anchorTree.GetSmallestContainingInterval(span.Start, 0);
if (anchorData == null)
{
// no anchor
DebugCheckEmpty(_anchorTree, new TextSpan(span.Start, 0));
return null;
}
return anchorData;
}
public int GetAnchorDeltaFromOriginalColumn(SyntaxToken token)
{
var anchorData = GetAnchorData(token);
if (anchorData == null)
{
return 0;
}
var currentColumn = TokenStream.GetCurrentColumn(anchorData.AnchorToken);
return currentColumn - anchorData.OriginalColumn;
}
public SyntaxToken GetAnchorToken(SyntaxToken token)
{
var anchorData = GetAnchorData(token);
if (anchorData == null)
{
return default;
}
return anchorData.AnchorToken;
}
public int GetDeltaFromPreviousChangesMap(SyntaxToken token, Dictionary<SyntaxToken, int> previousChangesMap)
{
// no changes
if (!previousChangesMap.TryGetValue(token, out var value))
{
return 0;
}
var currentColumn = TokenStream.GetCurrentColumn(token);
return currentColumn - value;
}
public SyntaxToken GetEndTokenForAnchorSpan(TokenData tokenData)
{
// consider situation like below
//
// var q = from c in cs
// where c > 1
// +
// 2;
//
// if alignment operation moves "where" to align with "from"
// we want to move "+" and "2" along with it (anchor operation)
//
// below we are trying to figure out up to which token ("2" in the above example)
// we should apply the anchor operation
var baseAnchorData = FindAnchorSpanOnSameLineAfterToken(tokenData);
if (baseAnchorData == null)
{
return default;
}
// our anchor operation is very flexible so it not only let one anchor to contain others, it also
// let anchors to overlap each other for whatever reasons
// below, we will try to flat the overlapped anchor span, and find the last position (token) of that span
// find other anchors overlapping with current anchor span
var anchorData = _anchorTree.GetIntervalsThatOverlapWith(baseAnchorData.TextSpan.Start, baseAnchorData.TextSpan.Length);
// among those anchors find the biggest end token
var lastEndToken = baseAnchorData.EndToken;
foreach (var interval in anchorData)
{
// anchor token is not in scope, move to next
if (!baseAnchorData.TextSpan.IntersectsWith(interval.AnchorToken.Span))
{
continue;
}
if (interval.EndToken.Span.End < lastEndToken.Span.End)
{
continue;
}
lastEndToken = interval.EndToken;
}
return lastEndToken;
}
private AnchorData? FindAnchorSpanOnSameLineAfterToken(TokenData tokenData)
{
// every token after given token on same line is implicitly dependent to the token.
// check whether one of them is an anchor token.
AnchorData? lastBaseAnchorData = null;
while (tokenData.IndexInStream >= 0)
{
if (_anchorBaseTokenMap.TryGetValue(tokenData.Token, out var tempAnchorData))
{
lastBaseAnchorData = tempAnchorData;
}
// tokenPairIndex is always 0 <= ... < TokenCount - 1
var tokenPairIndex = tokenData.IndexInStream;
if (TokenStream.TokenCount - 1 <= tokenPairIndex ||
TokenStream.GetTriviaData(tokenPairIndex).SecondTokenIsFirstTokenOnLine)
{
return lastBaseAnchorData;
}
tokenData = tokenData.GetNextTokenData();
}
return lastBaseAnchorData;
}
public bool IsWrappingSuppressed(TextSpan textSpan, bool containsElasticTrivia)
{
if (IsFormattingDisabled(textSpan))
{
return true;
}
// use edge exclusive version of GetSmallestContainingInterval
var data = _suppressWrappingTree.GetSmallestEdgeExclusivelyContainingInterval(textSpan.Start, textSpan.Length);
if (data == null)
{
return false;
}
if (containsElasticTrivia && !data.IgnoreElastic)
{
return false;
}
return true;
}
public bool IsSpacingSuppressed(TextSpan textSpan, bool containsElasticTrivia)
{
if (IsFormattingDisabled(textSpan))
{
return true;
}
// For spaces, never ignore elastic trivia because that can
// generate incorrect code
if (containsElasticTrivia)
{
return false;
}
// use edge exclusive version of GetSmallestContainingInterval
var data = _suppressSpacingTree.GetSmallestEdgeExclusivelyContainingInterval(textSpan.Start, textSpan.Length);
if (data == null)
{
return false;
}
return true;
}
public bool IsSpacingSuppressed(int pairIndex)
{
var token1 = TokenStream.GetToken(pairIndex);
var token2 = TokenStream.GetToken(pairIndex + 1);
var spanBetweenTwoTokens = TextSpan.FromBounds(token1.SpanStart, token2.Span.End);
// this version of SpacingSuppressed will be called after all basic space operations are done.
// so no more elastic trivia should have left out
return IsSpacingSuppressed(spanBetweenTwoTokens, containsElasticTrivia: false);
}
public bool IsFormattingDisabled(TextSpan textSpan)
=> _suppressFormattingTree.HasIntervalThatIntersectsWith(textSpan.Start, textSpan.Length);
public bool IsFormattingDisabled(int pairIndex)
{
var token1 = TokenStream.GetToken(pairIndex);
var token2 = TokenStream.GetToken(pairIndex + 1);
var spanBetweenTwoTokens = TextSpan.FromBounds(token1.SpanStart, token2.Span.End);
return IsFormattingDisabled(spanBetweenTwoTokens);
}
public SyntaxFormattingOptions Options => _engine.Options;
public TreeData TreeData => _engine.TreeData;
public TokenStream TokenStream { get; }
}
|