<commit_before>﻿// Copyright (c) Microsoft.  All Rights Reserved.  Licensed under the Apache License, Version 2.0.  See License.txt in the project root for license information.

using System;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Linq;
using System.Text.RegularExpressions;
using Microsoft.CodeAnalysis.EmbeddedLanguages.Common;
using Microsoft.CodeAnalysis.EmbeddedLanguages.VirtualChars;
using Microsoft.CodeAnalysis.PooledObjects;
using Microsoft.CodeAnalysis.Text;

namespace Microsoft.CodeAnalysis.EmbeddedLanguages.RegularExpressions
{
    using static EmbeddedSyntaxHelpers;
    using static RegexHelpers;

    using RegexNodeOrToken = EmbeddedSyntaxNodeOrToken<RegexKind, RegexNode>;
    using RegexToken = EmbeddedSyntaxToken<RegexKind>;
    using RegexTrivia = EmbeddedSyntaxTrivia<RegexKind>;

    internal partial struct RegexParser
    {
        private readonly ImmutableDictionary<string, TextSpan> _captureNamesToSpan;
        private readonly ImmutableDictionary<int, TextSpan> _captureNumbersToSpan;

        private RegexLexer _lexer;
        private RegexOptions _options;
        private RegexToken _currentToken;
        private int _recursionDepth;

        private RegexParser(
            ImmutableArray<VirtualChar> text, RegexOptions options,
            ImmutableDictionary<string, TextSpan> captureNamesToSpan,
            ImmutableDictionary<int, TextSpan> captureNumbersToSpan) : this()
        {
            _lexer = new RegexLexer(text);
            _options = options;

            _captureNamesToSpan = captureNamesToSpan;
            _captureNumbersToSpan = captureNumbersToSpan;

            // Get the first token.  It is allowed to have trivia on it.
            ConsumeCurrentToken(allowTrivia: true);
        }

        /// <summary>
        /// Returns the latest token the lexer has produced, and then asks the lexer to 
        /// produce the next token after that.
        /// </summary>
        /// <param name="allowTrivia">Whether or not trivia is allowed on the next token
        /// produced.  In the .net parser trivia is only allowed on a few constructs,
        /// and our parser mimics that behavior.  Note that even if trivia is allowed,
        /// the type of trivia that can be scanned depends on the current RegexOptions.
        /// For example, if <see cref="RegexOptions.IgnorePatternWhitespace"/> is currently
        /// enabled, then '#...' comments are allowed.  Otherwise, only '(?#...)' comments
        /// are allowed.</param>
        private RegexToken ConsumeCurrentToken(bool allowTrivia)
        {
            var previous = _currentToken;
            _currentToken = _lexer.ScanNextToken(allowTrivia, _options);
            return previous;
        }

        /// <summary>
        /// Given an input text, and set of options, 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 RegexTree TryParse(ImmutableArray<VirtualChar> text, RegexOptions options)
        {
            try
            {
                // Parse the tree once, to figure out the capture groups.  These are needed
                // to then parse the tree again, as the captures will affect how we interpret
                // certain things (i.e. escape references) and what errors will be reported.
                //
                // This is necessary as .net regexes allow references to *future* captures.
                // As such, we don't know when we're seeing a reference if it's to something
                // that exists or not.
                var tree1 = new RegexParser(text, options,
                    ImmutableDictionary<string, TextSpan>.Empty,
                    ImmutableDictionary<int, TextSpan>.Empty).ParseTree();

                var analyzer = new CaptureInfoAnalyzer(text);
                var (captureNames, captureNumbers) = analyzer.Analyze(tree1.Root, options);

                var tree2 = new RegexParser(
                    text, options, captureNames, captureNumbers).ParseTree();
                return tree2;
            }
            catch (Exception e) when (StackGuard.IsInsufficientExecutionStackException(e))
            {
                return null;
            }
        }

        private RegexTree ParseTree()
        {
            // Most callers to ParseAlternatingSequences are from group constructs.  As those
            // constructs will have already consumed the open paren, they don't want this sub-call
            // to consume through close-paren tokens as they want that token for themselves.
            // However, we're the topmost call and have not consumed an open paren.  And, we want
            // this call to consume all the way to the end, eating up excess close-paren tokens that
            // are encountered.
            var expression = this.ParseAlternatingSequences(consumeCloseParen: true);
            Debug.Assert(_lexer.Position == _lexer.Text.Length);
            Debug.Assert(_currentToken.Kind == RegexKind.EndOfFile);

            var root = new RegexCompilationUnit(expression, _currentToken);

            var diagnostics = ArrayBuilder<EmbeddedDiagnostic>.GetInstance();
            CollectDiagnostics(root, diagnostics);

            return new RegexTree(
                _lexer.Text, root, diagnostics.ToImmutableAndFree(),
                _captureNamesToSpan, _captureNumbersToSpan);
        }

        private static void CollectDiagnostics(RegexNode node, ArrayBuilder<EmbeddedDiagnostic> diagnostics)
        {
            foreach (var child in node)
            {
                if (child.IsNode)
                {
                    CollectDiagnostics(child.Node, diagnostics);
                }
                else
                {
                    var token = child.Token;
                    foreach (var trivia in token.LeadingTrivia)
                    {
                        AddUniqueDiagnostics(trivia.Diagnostics, diagnostics);
                    }

                    // We never place trailing trivia on regex tokens.
                    Debug.Assert(token.TrailingTrivia.IsEmpty);
                    AddUniqueDiagnostics(token.Diagnostics, diagnostics);
                }
            }
        }

        /// <summary>
        /// It's very common to have duplicated diagnostics.  For example, consider "((". This will
        /// have two 'missing )' diagnostics, both at the end.  Reporting both isn't helpful, so we
        /// filter duplicates out here.
        /// </summary>
        private static void AddUniqueDiagnostics(ImmutableArray<EmbeddedDiagnostic> from, ArrayBuilder<EmbeddedDiagnostic> to)
        {
            foreach (var diagnostic in from)
            {
                if (!to.Contains(diagnostic))
                {
                    to.Add(diagnostic);
                }
            }
        }

        private RegexExpressionNode ParseAlternatingSequences(bool consumeCloseParen)
        {
            try
            {
                _recursionDepth++;
                StackGuard.EnsureSufficientExecutionStack(_recursionDepth);
                return ParseAlternatingSequencesWorker(consumeCloseParen);
            }
            finally
            {
                _recursionDepth--;
            }
        }

        /// <summary>
        /// Parses out code of the form: ...|...|...
        /// This is the type of code you have at the top level of a regex, or inside any grouping
        /// contruct.  Note that sequences can be empty in .net regex.  i.e. the following is legal:
        /// 
        ///     ...||...
        /// 
        /// An empty sequence just means "match at every position in the test string".
        /// </summary>
        private RegexExpressionNode ParseAlternatingSequencesWorker(bool consumeCloseParen)
        {<commit_msg>Use a 'set' so we have linear and not quadratic complexity.<commit_after>﻿// Copyright (c) Microsoft.  All Rights Reserved.  Licensed under the Apache License, Version 2.0.  See License.txt in the project root for license information.

using System;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Linq;
using System.Text.RegularExpressions;
using Microsoft.CodeAnalysis.EmbeddedLanguages.Common;
using Microsoft.CodeAnalysis.EmbeddedLanguages.VirtualChars;
using Microsoft.CodeAnalysis.PooledObjects;
using Microsoft.CodeAnalysis.Text;

namespace Microsoft.CodeAnalysis.EmbeddedLanguages.RegularExpressions
{
    using System.Collections.Generic;
    using static EmbeddedSyntaxHelpers;
    using static RegexHelpers;

    using RegexNodeOrToken = EmbeddedSyntaxNodeOrToken<RegexKind, RegexNode>;
    using RegexToken = EmbeddedSyntaxToken<RegexKind>;
    using RegexTrivia = EmbeddedSyntaxTrivia<RegexKind>;

    internal partial struct RegexParser
    {
        private readonly ImmutableDictionary<string, TextSpan> _captureNamesToSpan;
        private readonly ImmutableDictionary<int, TextSpan> _captureNumbersToSpan;

        private RegexLexer _lexer;
        private RegexOptions _options;
        private RegexToken _currentToken;
        private int _recursionDepth;

        private RegexParser(
            ImmutableArray<VirtualChar> text, RegexOptions options,
            ImmutableDictionary<string, TextSpan> captureNamesToSpan,
            ImmutableDictionary<int, TextSpan> captureNumbersToSpan) : this()
        {
            _lexer = new RegexLexer(text);
            _options = options;

            _captureNamesToSpan = captureNamesToSpan;
            _captureNumbersToSpan = captureNumbersToSpan;

            // Get the first token.  It is allowed to have trivia on it.
            ConsumeCurrentToken(allowTrivia: true);
        }

        /// <summary>
        /// Returns the latest token the lexer has produced, and then asks the lexer to 
        /// produce the next token after that.
        /// </summary>
        /// <param name="allowTrivia">Whether or not trivia is allowed on the next token
        /// produced.  In the .net parser trivia is only allowed on a few constructs,
        /// and our parser mimics that behavior.  Note that even if trivia is allowed,
        /// the type of trivia that can be scanned depends on the current RegexOptions.
        /// For example, if <see cref="RegexOptions.IgnorePatternWhitespace"/> is currently
        /// enabled, then '#...' comments are allowed.  Otherwise, only '(?#...)' comments
        /// are allowed.</param>
        private RegexToken ConsumeCurrentToken(bool allowTrivia)
        {
            var previous = _currentToken;
            _currentToken = _lexer.ScanNextToken(allowTrivia, _options);
            return previous;
        }

        /// <summary>
        /// Given an input text, and set of options, 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 RegexTree TryParse(ImmutableArray<VirtualChar> text, RegexOptions options)
        {
            try
            {
                // Parse the tree once, to figure out the capture groups.  These are needed
                // to then parse the tree again, as the captures will affect how we interpret
                // certain things (i.e. escape references) and what errors will be reported.
                //
                // This is necessary as .net regexes allow references to *future* captures.
                // As such, we don't know when we're seeing a reference if it's to something
                // that exists or not.
                var tree1 = new RegexParser(text, options,
                    ImmutableDictionary<string, TextSpan>.Empty,
                    ImmutableDictionary<int, TextSpan>.Empty).ParseTree();

                var analyzer = new CaptureInfoAnalyzer(text);
                var (captureNames, captureNumbers) = analyzer.Analyze(tree1.Root, options);

                var tree2 = new RegexParser(
                    text, options, captureNames, captureNumbers).ParseTree();
                return tree2;
            }
            catch (Exception e) when (StackGuard.IsInsufficientExecutionStackException(e))
            {
                return null;
            }
        }

        private RegexTree ParseTree()
        {
            // Most callers to ParseAlternatingSequences are from group constructs.  As those
            // constructs will have already consumed the open paren, they don't want this sub-call
            // to consume through close-paren tokens as they want that token for themselves.
            // However, we're the topmost call and have not consumed an open paren.  And, we want
            // this call to consume all the way to the end, eating up excess close-paren tokens that
            // are encountered.
            var expression = this.ParseAlternatingSequences(consumeCloseParen: true);
            Debug.Assert(_lexer.Position == _lexer.Text.Length);
            Debug.Assert(_currentToken.Kind == RegexKind.EndOfFile);

            var root = new RegexCompilationUnit(expression, _currentToken);

            var seenDiagnostics = new HashSet<EmbeddedDiagnostic>();
            var diagnostics = ArrayBuilder<EmbeddedDiagnostic>.GetInstance();
            CollectDiagnostics(root, seenDiagnostics, diagnostics);

            return new RegexTree(
                _lexer.Text, root, diagnostics.ToImmutableAndFree(),
                _captureNamesToSpan, _captureNumbersToSpan);
        }

        private static void CollectDiagnostics(
            RegexNode node, HashSet<EmbeddedDiagnostic> seenDiagnostics, ArrayBuilder<EmbeddedDiagnostic> diagnostics)
        {
            foreach (var child in node)
            {
                if (child.IsNode)
                {
                    CollectDiagnostics(child.Node, seenDiagnostics, diagnostics);
                }
                else
                {
                    var token = child.Token;
                    foreach (var trivia in token.LeadingTrivia)
                    {
                        AddUniqueDiagnostics(seenDiagnostics, trivia.Diagnostics, diagnostics);
                    }

                    // We never place trailing trivia on regex tokens.
                    Debug.Assert(token.TrailingTrivia.IsEmpty);
                    AddUniqueDiagnostics(seenDiagnostics, token.Diagnostics, diagnostics);
                }
            }
        }

        /// <summary>
        /// It's very common to have duplicated diagnostics.  For example, consider "((". This will
        /// have two 'missing )' diagnostics, both at the end.  Reporting both isn't helpful, so we
        /// filter duplicates out here.
        /// </summary>
        private static void AddUniqueDiagnostics(
            HashSet<EmbeddedDiagnostic> seenDiagnostics, ImmutableArray<EmbeddedDiagnostic> from, ArrayBuilder<EmbeddedDiagnostic> to)
        {
            foreach (var diagnostic in from)
            {
                if (!seenDiagnostics.Add(diagnostic))
                {
                    to.Add(diagnostic);
                }
            }
        }

        private RegexExpressionNode ParseAlternatingSequences(bool consumeCloseParen)
        {
            try
            {
                _recursionDepth++;
                StackGuard.EnsureSufficientExecutionStack(_recursionDepth);
                return ParseAlternatingSequencesWorker(consumeCloseParen);
            }
            finally
            {
                _recursionDepth--;
            }
        }

        /// <summary>
        /// Parses out code of the form: ...|...|...
        /// This is the type of code you have at the top level of a regex, or inside any grouping
        /// contruct.  Note that sequences can be empty in .net regex.  i.e. the following is legal:
        /// 
        ///     ...||...
        /// 
        /// An empty sequence just means "match at every position in the test string".
        /// </summary>
        private RegexExpressionNode ParseAlternatingSequencesWorker(bool consumeCloseParen)
        {
{'fraction_non_alphanumeric': 0.07450138079165389, 'fraction_numerical': 0.000736422215403498, 'mean_word_length': 1.9346299297676932, 'pattern_counts': {'":': 0, '<': 58, '<?xml version=': 0, '>': 58, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '833291', 'n_tokens_mistral': 4049, 'n_tokens_neox': 3814, 'n_words': 1260}