|
// 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.Immutable;
using System.Diagnostics;
using System.Linq;
using Microsoft.CodeAnalysis.EmbeddedLanguages.Common;
using Microsoft.CodeAnalysis.EmbeddedLanguages.VirtualChars;
using Microsoft.CodeAnalysis.PooledObjects;
using Microsoft.CodeAnalysis.Text;
using Roslyn.Utilities;
namespace Microsoft.CodeAnalysis.Features.EmbeddedLanguages.Json
{
using static EmbeddedSyntaxHelpers;
using static JsonHelpers;
using JsonNodeOrToken = EmbeddedSyntaxNodeOrToken<JsonKind, JsonNode>;
using JsonToken = EmbeddedSyntaxToken<JsonKind>;
using JsonTrivia = EmbeddedSyntaxTrivia<JsonKind>;
using JsonSeparatedList = EmbeddedSeparatedSyntaxNodeList<JsonKind, JsonNode, JsonValueNode>;
/// <summary>
/// Parser used for reading in a sequence of <see cref="VirtualChar"/>s, and producing a <see
/// cref="JsonTree"/> out of it. Parsing will always succeed (except in the case of a
/// stack-overflow) and will consume the entire sequence of chars. General roslyn syntax
/// principles are held to (i.e. immutable, fully representative, etc.).
/// <para>
/// The parser always parses out the same tree regardless of input. *However*, depending on the
/// flags passed to it, it may return a different set of *diagnostics*. Specifically, the
/// parser supports json.net parsing and strict RFC8259 (https://tools.ietf.org/html/rfc8259).
/// As such, the parser supports a superset of both, but then does a pass at the end to produce
/// appropriate diagnostics.
/// </para>
/// </summary>
/// <remarks>
/// Note: the json structure we parse out is actually very simple. It's effectively all lists
/// of <see cref="JsonValueNode"/> values. We just treat almost everything as a 'value'. For
/// example, a <see cref="JsonPropertyNode"/> (i.e. <c>"x" = 0</c>) is a 'value'. As such, it
/// can show up in arrays (i.e. <c>["x" = 0, "y" = 1]</c>). This is not legal, but it greatly
/// simplifies parsing. Effectively, we just have recursive list parsing, where we accept any
/// sort of value in any sort of context. A later pass will then report errors for the wrong
/// sorts of values showing up in incorrect contexts.
/// <para>
/// Note: We also treat commas (<c>,</c>) as being a 'value' on its own. This simplifies parsing
/// by allowing us to not have to represent Lists and SeparatedLists. It also helps model
/// things that are supported in json.net (like <c>[1,,2]</c>). Our post-parsing pass will
/// then ensure that these comma-values only show up in the right contexts.
/// </para>
/// </remarks>
[NonCopyable]
internal partial struct JsonParser
{
private static readonly string s_closeBracketExpected = string.Format(FeaturesResources._0_expected, ']');
private static readonly string s_closeBraceExpected = string.Format(FeaturesResources._0_expected, '}');
private static readonly string s_openParenExpected = string.Format(FeaturesResources._0_expected, '(');
private static readonly string s_closeParenExpected = string.Format(FeaturesResources._0_expected, ')');
private static readonly string s_commaExpected = string.Format(FeaturesResources._0_expected, ',');
private JsonLexer _lexer;
private JsonToken _currentToken;
private int _recursionDepth;
// Fields used to keep track of what types of json values we're in. They're used for error
// recovery, specifically with respect to encountering unexpected tokens while parsing out a
// sequence of values. For example, if we have: ```{ a: [1, 2, }```, we will mark that
// we're both in an object and in an array. When we then encounter the errant ```}```,
// we'll see that we were in an object, and thus should stop parsing out the sequence for
// the array so that the ```}``` can be consume by the object we were in. However, if we
// just had ```[1, 2, }```, we would not be in an object, and we would just consume the
// ```}``` as a bogus value inside the array.
//
// This approach of keeping track of the parse contexts we're in, and using them to
// determine if we should consume or pop-out when encountering an error token, mirrors the
// same approach that we use in the C# and TS/JS parsers.
private bool _inObject;
private bool _inArray;
private bool _inConstructor;
private JsonParser(VirtualCharSequence text) : this()
{
_lexer = new JsonLexer(text);
// Get the first token.
ConsumeCurrentToken();
}
/// <summary>
/// Returns the latest token the lexer has produced, and then asks the lexer to
/// produce the next token after that.
/// </summary>
private JsonToken ConsumeCurrentToken()
{
var previous = _currentToken;
_currentToken = _lexer.ScanNextToken();
return previous;
}
/// <summary>
/// Given an input text, parses out a fully representative syntax tree and list of
/// diagnostics. Parsing should always succeed, except in the case of the stack
/// overflowing.
/// </summary>
public static JsonTree? TryParse(VirtualCharSequence text, JsonOptions options)
{
try
{
if (text.IsDefaultOrEmpty)
return null;
return new JsonParser(text).ParseTree(options);
}
catch (InsufficientExecutionStackException)
{
return null;
}
}
private JsonTree ParseTree(JsonOptions options)
{
var arraySequence = this.ParseSequence();
Debug.Assert(_lexer.Position == _lexer.Text.Length);
Debug.Assert(_currentToken.Kind == JsonKind.EndOfFile);
var root = new JsonCompilationUnit(arraySequence, _currentToken);
// There are three forms of diagnostics we can detect. The first were generated directly when parsing and
// relate to unknown tokens encountered or tokens that were needed but not found. The second relates to a
// set of grammar check rules that apply to both strict and non-strict json. The last is the specific
// strict/loose checks we perform. We look for all three forms, but only report the first issue we found.
// We want to avoid reporting a ton of cascaded errors.
var diagnostic1 = GetFirstDiagnostic(root);
var diagnostic2 = CheckTopLevel(_lexer.Text, root);
var diagnostic3 = options.HasFlag(JsonOptions.Strict)
? StrictSyntaxChecker.CheckRootSyntax(root, options)
: JsonNetSyntaxChecker.CheckSyntax(root);
var diagnostic = Earliest(Earliest(diagnostic1, diagnostic2), diagnostic3);
return new JsonTree(_lexer.Text, root, diagnostic == null
? ImmutableArray<EmbeddedDiagnostic>.Empty
: ImmutableArray.Create(diagnostic.Value));
}
private static EmbeddedDiagnostic? Earliest(EmbeddedDiagnostic? d1, EmbeddedDiagnostic? d2)
{
if (d1 == null)
return d2;
if (d2 == null)
return d1;
return d1.Value.Span.Start <= d2.Value.Span.Start ? d1 : d2;
}
/// <summary>
/// Checks for errors in json for both json.net and strict mode.
/// </summary>
private static EmbeddedDiagnostic? CheckTopLevel(
VirtualCharSequence text, JsonCompilationUnit compilationUnit)
{
var sequence = compilationUnit.Sequence;
if (sequence.IsEmpty)
{
// json is not allowed to be just whitespace.
//
// Note: we always have at least some content (either real nodes in the tree) or trivia on the EOF token
// as we only parse when we have a non-empty sequence of virtual chars to begin with.
if (text.Length > 0 &&
compilationUnit.EndOfFileToken.LeadingTrivia.All(
t => t.Kind is JsonKind.WhitespaceTrivia or JsonKind.EndOfLineTrivia))
{
return new EmbeddedDiagnostic(FeaturesResources.Syntax_error, GetSpan(text));
}
return null;
}
else if (sequence.Length >= 2)
{
// the top level can't have more than one actual value.
var firstToken = GetFirstToken(sequence[1]);
return new EmbeddedDiagnostic(
string.Format(FeaturesResources._0_unexpected, firstToken.VirtualChars[0]),
firstToken.GetSpan());
}
else
{
var child = sequence.Single();
// Commas should never show up in the top level sequence.
if (child.Kind == JsonKind.CommaValue)
{
var emptyValue = (JsonCommaValueNode)child;
return new EmbeddedDiagnostic(
string.Format(FeaturesResources._0_unexpected, ','),
emptyValue.CommaToken.GetSpan());
}
else if (child.Kind == JsonKind.Property)
{
var propertyValue = (JsonPropertyNode)child;
return new EmbeddedDiagnostic(
string.Format(FeaturesResources._0_unexpected, ':'),
propertyValue.ColonToken.GetSpan());
}
return CheckSyntax(child);
}
static EmbeddedDiagnostic? CheckSyntax(JsonNode node)
{
var diagnostic = node.Kind switch
{
JsonKind.Array => CheckArray((JsonArrayNode)node),
JsonKind.Object => CheckObject((JsonObjectNode)node),
_ => null,
};
return Earliest(diagnostic, CheckChildren(node));
}
static EmbeddedDiagnostic? CheckChildren(JsonNode node)
{
foreach (var child in node)
{
if (child.IsNode)
{
var diagnostic = CheckSyntax(child.Node);
if (diagnostic != null)
return diagnostic;
}
}
return null;
}
static EmbeddedDiagnostic? CheckArray(JsonArrayNode node)
{
foreach (var child in node.Sequence)
{
if (child.Kind == JsonKind.Property)
{
return new EmbeddedDiagnostic(
FeaturesResources.Properties_not_allowed_in_an_array,
((JsonPropertyNode)child).ColonToken.GetSpan());
}
}
return null;
}
static EmbeddedDiagnostic? CheckObject(JsonObjectNode node)
{
foreach (var child in node.Sequence)
{
if (child is JsonLiteralNode { LiteralToken.Kind: JsonKind.StringToken })
{
return new EmbeddedDiagnostic(
FeaturesResources.Property_name_must_be_followed_by_a_colon,
child.GetSpan());
}
}
return null;
}
}
private static JsonToken GetFirstToken(JsonNodeOrToken nodeOrToken)
=> nodeOrToken.IsNode ? GetFirstToken(nodeOrToken.Node.ChildAt(0)) : nodeOrToken.Token;
private static EmbeddedDiagnostic? GetFirstDiagnostic(JsonNode node)
{
foreach (var child in node)
{
var diagnostic = GetFirstDiagnostic(child);
if (diagnostic != null)
return diagnostic;
}
return null;
}
private static EmbeddedDiagnostic? GetFirstDiagnostic(JsonNodeOrToken child)
=> child.IsNode
? GetFirstDiagnostic(child.Node)
: GetFirstDiagnostic(child.Token);
private static EmbeddedDiagnostic? GetFirstDiagnostic(JsonToken token)
=> GetFirstDiagnostic(token.LeadingTrivia) ?? token.Diagnostics.FirstOrNull() ?? GetFirstDiagnostic(token.TrailingTrivia);
private static EmbeddedDiagnostic? GetFirstDiagnostic(ImmutableArray<JsonTrivia> list)
{
foreach (var trivia in list)
{
var diagnostic = trivia.Diagnostics.FirstOrNull();
if (diagnostic != null)
return diagnostic;
}
return null;
}
private ImmutableArray<JsonValueNode> ParseSequence()
{
try
{
_recursionDepth++;
StackGuard.EnsureSufficientExecutionStack(_recursionDepth);
return ParseSequenceWorker();
}
finally
{
_recursionDepth--;
}
}
private ImmutableArray<JsonValueNode> ParseSequenceWorker()
{
using var _ = ArrayBuilder<JsonValueNode>.GetInstance(out var result);
while (ShouldConsumeSequenceElement())
result.Add(ParseValue());
return result.ToImmutable();
}
private JsonSeparatedList ParseCommaSeparatedSequence()
{
try
{
_recursionDepth++;
StackGuard.EnsureSufficientExecutionStack(_recursionDepth);
return ParseCommaSeparatedSequenceWorker();
}
finally
{
_recursionDepth--;
}
}
private JsonSeparatedList ParseCommaSeparatedSequenceWorker()
{
using var _ = ArrayBuilder<JsonNodeOrToken>.GetInstance(out var result);
var allProperties = true;
while (ShouldConsumeSequenceElement())
{
var value = ParseValue();
allProperties = allProperties && value.Kind == JsonKind.Property;
result.Add(value);
// Try to consume a comma. If we don't see one, consume an empty one as a placeholder. Create a
// diagnostic message depending on if we've seen only properties before this point. If not, don't give
// a message about a missing comma. Instead, we'll give a specific message that we didn't get a
// property when we expected one.
if (ShouldConsumeSequenceElement())
result.Add(ConsumeToken(JsonKind.CommaToken, allProperties ? s_commaExpected : null));
}
return new JsonSeparatedList(result.ToImmutable());
}
private readonly bool ShouldConsumeSequenceElement()
=> _currentToken.Kind switch
{
JsonKind.EndOfFile => false,
JsonKind.CloseBraceToken => !_inObject,
JsonKind.CloseBracketToken => !_inArray,
JsonKind.CloseParenToken => !_inConstructor,
_ => true
};
private JsonValueNode ParseValue()
{
try
{
_recursionDepth++;
StackGuard.EnsureSufficientExecutionStack(_recursionDepth);
return _currentToken.Kind switch
{
JsonKind.OpenBraceToken => ParseObject(),
JsonKind.OpenBracketToken => ParseArray(),
JsonKind.CommaToken => ParseCommaValue(),
_ => ParseLiteralOrPropertyOrConstructor(),
};
}
finally
{
_recursionDepth--;
}
}
private static void SplitLiteral(JsonToken literalToken, out JsonToken minusToken, out JsonToken newLiteralToken)
{
minusToken = CreateToken(
JsonKind.MinusToken, literalToken.LeadingTrivia,
literalToken.VirtualChars.GetSubSequence(new TextSpan(0, 1)),
ImmutableArray<JsonTrivia>.Empty);
newLiteralToken = CreateToken(
literalToken.Kind,
ImmutableArray<JsonTrivia>.Empty,
literalToken.VirtualChars.GetSubSequence(TextSpan.FromBounds(1, literalToken.VirtualChars.Length)),
literalToken.TrailingTrivia,
literalToken.Diagnostics);
}
private JsonPropertyNode ParseProperty(JsonToken stringLiteralOrText)
{
Debug.Assert(_currentToken.Kind == JsonKind.ColonToken);
// Kind could be anything else we might have parsed as a value (for example, an integer/boolean literal).
if (stringLiteralOrText.Kind != JsonKind.StringToken)
stringLiteralOrText = stringLiteralOrText.With(kind: JsonKind.TextToken);
var colonToken = ConsumeCurrentToken();
// Newtonsoft allows "{ a: , }" as a legal property. In that case, synthesize a missing value and allow the
// comma to be parsed as the next value in the sequence. The strict pass will error if it sees this missing
// comma-value as the value of a property.
if (_currentToken.Kind == JsonKind.CommaToken)
{
return new JsonPropertyNode(
stringLiteralOrText, colonToken,
new JsonCommaValueNode(CreateMissingToken(JsonKind.CommaToken)));
}
else if (_currentToken.Kind == JsonKind.EndOfFile)
{
return new JsonPropertyNode(
stringLiteralOrText, colonToken,
new JsonCommaValueNode(CreateMissingToken(JsonKind.CommaToken).AddDiagnosticIfNone(new EmbeddedDiagnostic(
FeaturesResources.Missing_property_value,
GetTokenStartPositionSpan(_currentToken)))));
}
var value = ParseValue();
if (value.Kind == JsonKind.Property)
{
// It's always illegal to have something like ```"a" : "b" : 1```
var nestedProperty = (JsonPropertyNode)value;
value = new JsonPropertyNode(
nestedProperty.NameToken,
nestedProperty.ColonToken.AddDiagnosticIfNone(new EmbeddedDiagnostic(
FeaturesResources.Nested_properties_not_allowed,
nestedProperty.ColonToken.GetSpan())),
nestedProperty.Value);
}
return new JsonPropertyNode(stringLiteralOrText, colonToken, value);
}
private JsonValueNode ParseLiteralOrPropertyOrConstructor()
{
var textToken = ConsumeCurrentToken();
return _currentToken.Kind == JsonKind.ColonToken
? ParseProperty(textToken)
: ParseLiteralOrTextOrConstructor(textToken);
}
private JsonValueNode ParseLiteralOrTextOrConstructor(JsonToken token)
{
if (token.Kind == JsonKind.StringToken)
return new JsonLiteralNode(token);
// Look for constructors (a json.net extension). We'll report them as an error
// in strict model.
if (Matches(token, "new"))
return ParseConstructor(token);
// Check for certain literal values. Some of these (like NaN) are json.net only.
// We'll check for these later in the strict-mode pass.
Debug.Assert(token.VirtualChars.Length > 0);
if (TryMatch(token, "NaN", JsonKind.NaNLiteralToken, out var newKind) ||
TryMatch(token, "null", JsonKind.NullLiteralToken, out newKind) ||
TryMatch(token, "true", JsonKind.TrueLiteralToken, out newKind) ||
TryMatch(token, "false", JsonKind.FalseLiteralToken, out newKind) ||
TryMatch(token, "Infinity", JsonKind.InfinityLiteralToken, out newKind) ||
TryMatch(token, "undefined", JsonKind.UndefinedLiteralToken, out newKind))
{
return new JsonLiteralNode(token.With(kind: newKind));
}
if (Matches(token, "-Infinity"))
{
SplitLiteral(token, out var minusToken, out var newLiteralToken);
return new JsonNegativeLiteralNode(
minusToken, newLiteralToken.With(kind: JsonKind.InfinityLiteralToken));
}
var firstChar = token.VirtualChars[0];
if (firstChar == '-' || firstChar == '.' || IsDigit(firstChar))
return new JsonLiteralNode(token.With(kind: JsonKind.NumberToken));
return new JsonTextNode(
token.With(kind: JsonKind.TextToken).AddDiagnosticIfNone(new EmbeddedDiagnostic(
string.Format(FeaturesResources._0_unexpected, firstChar.ToString()),
firstChar.Span)));
}
private JsonConstructorNode ParseConstructor(JsonToken token)
{
var savedInConstructor = _inConstructor;
_inConstructor = true;
var result = new JsonConstructorNode(
token.With(kind: JsonKind.NewKeyword),
ConsumeToken(JsonKind.TextToken, FeaturesResources.Name_expected),
ConsumeToken(JsonKind.OpenParenToken, s_openParenExpected),
ParseSequence(),
ConsumeToken(JsonKind.CloseParenToken, s_closeParenExpected));
_inConstructor = savedInConstructor;
return result;
}
private static bool TryMatch(JsonToken token, string val, JsonKind kind, out JsonKind newKind)
{
if (Matches(token, val))
{
newKind = kind;
return true;
}
newKind = default;
return false;
}
private static bool Matches(JsonToken token, string val)
{
var chars = token.VirtualChars;
if (chars.Length != val.Length)
return false;
for (var i = 0; i < val.Length; i++)
{
if (chars[i] != val[i])
return false;
}
return true;
}
private static bool IsDigit(VirtualChar ch)
=> ch.Value is >= '0' and <= '9';
private JsonCommaValueNode ParseCommaValue()
=> new(ConsumeCurrentToken());
private JsonArrayNode ParseArray()
{
var savedInArray = _inArray;
_inArray = true;
var result = new JsonArrayNode(
ConsumeCurrentToken(),
ParseSequence(),
ConsumeToken(JsonKind.CloseBracketToken, s_closeBracketExpected));
_inArray = savedInArray;
return result;
}
private JsonObjectNode ParseObject()
{
var savedInObject = _inObject;
_inObject = true;
var result = new JsonObjectNode(
ConsumeCurrentToken(),
ParseCommaSeparatedSequence(),
ConsumeToken(JsonKind.CloseBraceToken, s_closeBraceExpected));
_inObject = savedInObject;
return result;
}
private JsonToken ConsumeToken(JsonKind kind, string? error)
{
if (_currentToken.Kind == kind)
return ConsumeCurrentToken();
var result = CreateMissingToken(kind);
if (error == null)
return result;
return result.AddDiagnosticIfNone(new EmbeddedDiagnostic(error, GetTokenStartPositionSpan(_currentToken)));
}
private readonly TextSpan GetTokenStartPositionSpan(JsonToken token)
=> token.Kind == JsonKind.EndOfFile
? new TextSpan(_lexer.Text.Last().Span.End, 0)
: new TextSpan(token.VirtualChars[0].Span.Start, 0);
}
}
|