From db22cd83e559eaea93eade9ee95932f931002899 Mon Sep 17 00:00:00 2001 From: Kirill Osenkov Date: Fri, 2 Feb 2018 15:30:21 -0800 Subject: Add Completion, BraceCompletion, PatternMatcher and ILoggingServiceInternal. --- .../Language/Completion/AsyncCompletionBroker.cs | 319 ++++++++++ .../Language/Completion/AsyncCompletionSession.cs | 555 +++++++++++++++++ .../Impl/Language/Completion/CompletionModel.cs | 299 +++++++++ .../Language/Completion/CompletionUtilities.cs | 119 ++++ .../Completion/DefaultCompletionService.cs | 238 ++++++++ .../Completion/PrioritizedTaskScheduler.cs | 65 ++ .../Completion/SelectDownCommandHandler.cs | 40 ++ .../Completion/SelectPageDownCommandHandler.cs | 40 ++ .../Completion/SelectPageUpCommandHandler.cs | 40 ++ .../Language/Completion/SelectUpCommandHandler.cs | 40 ++ ...crosoft.VisualStudio.Text.Implementation.csproj | 14 +- ...crosoft.VisualStudio.Text.Implementation.nuspec | 29 - .../Internal/TextLogic/ILoggingServiceInternal.cs | 89 +++ src/Text/Def/TextLogic/TextLogic.csproj | 2 +- .../BraceCompletion/BraceCompletionAggregator.cs | 441 ++++++++++++++ .../BraceCompletionAggregatorFactory.cs | 75 +++ .../BraceCompletionDefaultSession.cs | 430 +++++++++++++ .../Impl/BraceCompletion/BraceCompletionManager.cs | 488 +++++++++++++++ .../Impl/BraceCompletion/BraceCompletionStack.cs | 335 +++++++++++ .../IBraceCompletionAdornmentService.cs | 22 + .../IBraceCompletionAdornmentServiceFactory.cs | 20 + .../BraceCompletion/IBraceCompletionAggregator.cs | 43 ++ .../IBraceCompletionAggregatorFactory.cs | 28 + .../BraceCompletion/IBraceCompletionMetadata.cs | 32 + .../Impl/BraceCompletion/IBraceCompletionStack.cs | 42 ++ src/Text/Impl/BraceCompletion/PlainTextDefaults.cs | 26 + src/Text/Impl/BraceCompletion/Strings.Designer.cs | 81 +++ src/Text/Impl/BraceCompletion/Strings.resx | 126 ++++ .../PatternMatching/AllLowerCamelCaseMatcher.cs | 263 ++++++++ src/Text/Impl/PatternMatching/ArraySlice.cs | 83 +++ src/Text/Impl/PatternMatching/CamelCaseResult.cs | 90 +++ .../PatternMatching/CaseInsensitiveComparison.cs | 74 +++ .../PatternMatching/ContainerPatternMatcher.cs | 121 ++++ src/Text/Impl/PatternMatching/EditDistance.cs | 669 +++++++++++++++++++++ .../Impl/PatternMatching/PatternMatchExtensions.cs | 139 +++++ .../PatternMatching/PatternMatchMergeStrategy.cs | 25 + .../PatternMatcher.PatternSegment.cs | 117 ++++ .../PatternMatching/PatternMatcher.TextChunk.cs | 44 ++ src/Text/Impl/PatternMatching/PatternMatcher.cs | 610 +++++++++++++++++++ .../Impl/PatternMatching/PatternMatcherFactory.cs | 44 ++ .../Impl/PatternMatching/SimplePatternMatcher.cs | 60 ++ src/Text/Impl/PatternMatching/StringBreaker.cs | 312 ++++++++++ .../PatternMatching/StringBreaks.EncodedSpans.cs | 30 + src/Text/Impl/PatternMatching/Utilities.cs | 33 + .../Impl/PatternMatching/WordSimilarityChecker.cs | 199 ++++++ 45 files changed, 6960 insertions(+), 31 deletions(-) create mode 100644 src/Language/Impl/Language/Completion/AsyncCompletionBroker.cs create mode 100644 src/Language/Impl/Language/Completion/AsyncCompletionSession.cs create mode 100644 src/Language/Impl/Language/Completion/CompletionModel.cs create mode 100644 src/Language/Impl/Language/Completion/CompletionUtilities.cs create mode 100644 src/Language/Impl/Language/Completion/DefaultCompletionService.cs create mode 100644 src/Language/Impl/Language/Completion/PrioritizedTaskScheduler.cs create mode 100644 src/Language/Impl/Language/Completion/SelectDownCommandHandler.cs create mode 100644 src/Language/Impl/Language/Completion/SelectPageDownCommandHandler.cs create mode 100644 src/Language/Impl/Language/Completion/SelectPageUpCommandHandler.cs create mode 100644 src/Language/Impl/Language/Completion/SelectUpCommandHandler.cs delete mode 100644 src/Microsoft.VisualStudio.Text.Implementation.nuspec create mode 100644 src/Text/Def/Internal/TextLogic/ILoggingServiceInternal.cs create mode 100644 src/Text/Impl/BraceCompletion/BraceCompletionAggregator.cs create mode 100644 src/Text/Impl/BraceCompletion/BraceCompletionAggregatorFactory.cs create mode 100644 src/Text/Impl/BraceCompletion/BraceCompletionDefaultSession.cs create mode 100644 src/Text/Impl/BraceCompletion/BraceCompletionManager.cs create mode 100644 src/Text/Impl/BraceCompletion/BraceCompletionStack.cs create mode 100644 src/Text/Impl/BraceCompletion/IBraceCompletionAdornmentService.cs create mode 100644 src/Text/Impl/BraceCompletion/IBraceCompletionAdornmentServiceFactory.cs create mode 100644 src/Text/Impl/BraceCompletion/IBraceCompletionAggregator.cs create mode 100644 src/Text/Impl/BraceCompletion/IBraceCompletionAggregatorFactory.cs create mode 100644 src/Text/Impl/BraceCompletion/IBraceCompletionMetadata.cs create mode 100644 src/Text/Impl/BraceCompletion/IBraceCompletionStack.cs create mode 100644 src/Text/Impl/BraceCompletion/PlainTextDefaults.cs create mode 100644 src/Text/Impl/BraceCompletion/Strings.Designer.cs create mode 100644 src/Text/Impl/BraceCompletion/Strings.resx create mode 100644 src/Text/Impl/PatternMatching/AllLowerCamelCaseMatcher.cs create mode 100644 src/Text/Impl/PatternMatching/ArraySlice.cs create mode 100644 src/Text/Impl/PatternMatching/CamelCaseResult.cs create mode 100644 src/Text/Impl/PatternMatching/CaseInsensitiveComparison.cs create mode 100644 src/Text/Impl/PatternMatching/ContainerPatternMatcher.cs create mode 100644 src/Text/Impl/PatternMatching/EditDistance.cs create mode 100644 src/Text/Impl/PatternMatching/PatternMatchExtensions.cs create mode 100644 src/Text/Impl/PatternMatching/PatternMatchMergeStrategy.cs create mode 100644 src/Text/Impl/PatternMatching/PatternMatcher.PatternSegment.cs create mode 100644 src/Text/Impl/PatternMatching/PatternMatcher.TextChunk.cs create mode 100644 src/Text/Impl/PatternMatching/PatternMatcher.cs create mode 100644 src/Text/Impl/PatternMatching/PatternMatcherFactory.cs create mode 100644 src/Text/Impl/PatternMatching/SimplePatternMatcher.cs create mode 100644 src/Text/Impl/PatternMatching/StringBreaker.cs create mode 100644 src/Text/Impl/PatternMatching/StringBreaks.EncodedSpans.cs create mode 100644 src/Text/Impl/PatternMatching/Utilities.cs create mode 100644 src/Text/Impl/PatternMatching/WordSimilarityChecker.cs (limited to 'src') diff --git a/src/Language/Impl/Language/Completion/AsyncCompletionBroker.cs b/src/Language/Impl/Language/Completion/AsyncCompletionBroker.cs new file mode 100644 index 0000000..c7c1268 --- /dev/null +++ b/src/Language/Impl/Language/Completion/AsyncCompletionBroker.cs @@ -0,0 +1,319 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Threading.Tasks; +using Microsoft.VisualStudio.Language.Intellisense; +using Microsoft.VisualStudio.Text; +using Microsoft.VisualStudio.Text.Editor; +using System.Collections.Immutable; +using Microsoft.VisualStudio.Threading; +using Microsoft.VisualStudio.Utilities; +using Microsoft.VisualStudio.Text.Utilities; + +#if NET46 +using System.ComponentModel.Composition; +#else +using System.Composition; +#endif + +namespace Microsoft.VisualStudio.Language.Intellisense.Implementation +{ + [Export(typeof(IAsyncCompletionBroker))] + internal class AsyncCompletionBroker : IAsyncCompletionBroker + { + [Import] + private JoinableTaskContext JtContext { get; set; } + + [Import(AllowDefault = true)] + internal ILoggingServiceInternal Logger { get; set; } + + [Import(AllowDefault = true)] + internal ITextDocumentFactoryService TextDocumentFactoryService { get; set; } + + [Import] + private IGuardedOperations GuardedOperation { get; set; } + + [Import] + private IContentTypeRegistryService ContentTypeRegistryService { get; set; } + + [ImportMany] + private IEnumerable> UnorderedUiFactories { get; set; } + + [ImportMany] + private IEnumerable> UnorderedCompletionItemSources { get; set; } + + [ImportMany] + private IEnumerable> UnorderedCompletionServices { get; set; } + + private IList> _orderedUiFactories; + internal IList> OrderedUiFactories + => _orderedUiFactories ?? (_orderedUiFactories = Orderer.Order(UnorderedUiFactories)); + + private IList> _orderedCompletionItemSources; + internal IList> OrderedCompletionItemSources + => _orderedCompletionItemSources ?? (_orderedCompletionItemSources = Orderer.Order(UnorderedCompletionItemSources)); + + private IList> _orderedCompletionServices; + internal IList> OrderedCompletionServices + => _orderedCompletionServices ?? (_orderedCompletionServices = Orderer.Order(UnorderedCompletionServices)); + + private ImmutableDictionary> _commitCharacters = ImmutableDictionary>.Empty; + private ImmutableDictionary> _cachedCompletionItemSources = ImmutableDictionary>.Empty; + private ImmutableDictionary _cachedCompletionServices = ImmutableDictionary.Empty; + private ImmutableDictionary _cachedUiFactories = ImmutableDictionary.Empty; + bool firstRun = true; // used only for diagnostics + private bool _firstInvocationReported; // used for "time to code" + + void IAsyncCompletionBroker.Dismiss(ITextView view) + { + var session = GetSession(view); + if (session == null) + { + return; + } + view.Properties.RemoveProperty(typeof(IAsyncCompletionSession)); + session.DismissAndHide(); + } + + void IAsyncCompletionBroker.Commit(ITextView view, string edit) + { + var session = GetSession(view); + if (session == null) + { + return; + } + + session.Commit(edit); + ((IAsyncCompletionBroker)this).Dismiss(view); + } + + void IAsyncCompletionBroker.OpenOrUpdate(ITextView view, ITrackingSpan trackedEdit, CompletionTrigger trigger, SnapshotPoint triggerLocation) + { + var session = GetSession(view); + if (session == null) + { + // Either the session was dismissed, or Begin was not called yet. + // what would be a good way to tell the two apart? + // throw new InvalidOperationException("No completion session available for this view. Call Begin first."); + return; + } + session.OpenOrUpdate(view, trackedEdit, trigger, triggerLocation); + } + + void IAsyncCompletionBroker.TriggerCompletion(ITextView view, SnapshotPoint triggerLocation) + { + var session = GetSession(view); + if (session != null) + { + // Session already exists. + return; + } + + // TODO: Handle the race condition: two consecutive OpenAsync. Both create completion + // not knowing of one another. The second invocation should use the if-block. + + var sourcesWithLocations = CompletionUtilities.GetCompletionSourcesWithMappedLocations(view, triggerLocation, GetCompletionItemSources); + if (!sourcesWithLocations.Any()) + { + // There is no completion source available for this buffer + return; + } + + var buffers = CompletionUtilities.GetBuffersForTriggerPoint(view, triggerLocation).ToImmutableArray(); + var service = buffers + .Select(b => GetCompletionService(b.ContentType)) + .FirstOrDefault(s => s != null); + + if (service == null) + { + // There is no modern completion service available for this buffer + return; + } + + var uiFactory = buffers + .Select(b => GetUiFactory(b.ContentType)) + .FirstOrDefault(s => s != null); + + if (firstRun) + { + System.Diagnostics.Debug.Assert(uiFactory != null, $"No instance of {nameof(ICompletionUIProvider)} is loaded. The prototype completion will work without the UI."); + firstRun = false; + } + session = new AsyncCompletionSession(JtContext.Factory, uiFactory, sourcesWithLocations, service, this, view); + view.Properties.AddProperty(typeof(IAsyncCompletionSession), session); + view.Closed += TextView_Closed; + + // Additionally, emulate the legacy completion telemetry + emulateLegacyCompletionTelemetry(buffers.FirstOrDefault()?.ContentType, view); + } + + private ImmutableArray GetCompletionItemSources(IContentType contentType) + { + if (_cachedCompletionItemSources.TryGetValue(contentType, out var cachedSources)) + { + return cachedSources; + } + + ImmutableArray result = ImmutableArray.Empty; + foreach (var item in OrderedCompletionItemSources) + { + if (item.Metadata.ContentTypes.Any(n => contentType.IsOfType(n))) + { + result = result.Add(item.Value); + } + } + _cachedCompletionItemSources = _cachedCompletionItemSources.Add(contentType, result); + return result; + } + + private IAsyncCompletionService GetCompletionService(IContentType contentType) + { + if (_cachedCompletionServices.TryGetValue(contentType, out var service)) + { + return service; + } + + IAsyncCompletionService bestService = GuardedOperation.InvokeBestMatchingFactory( + providerHandles: OrderedCompletionServices, + getter: n => n, + dataContentType: contentType, + contentTypeRegistryService: ContentTypeRegistryService, + errorSource: this); + + _cachedCompletionServices = _cachedCompletionServices.Add(contentType, bestService); + return bestService; + } + + private ICompletionUIProvider GetUiFactory(IContentType contentType) + { + if (_cachedUiFactories.TryGetValue(contentType, out var factory)) + { + return factory; + } + + ICompletionUIProvider bestFactory = GuardedOperation.InvokeBestMatchingFactory( + providerHandles: OrderedUiFactories, + getter: n => n, + dataContentType: contentType, + contentTypeRegistryService: ContentTypeRegistryService, + errorSource: this); + + _cachedUiFactories = _cachedUiFactories.Add(contentType, bestFactory); + return bestFactory; + } + + private void TextView_Closed(object sender, EventArgs e) + { + ((IAsyncCompletionBroker)this).Dismiss((ITextView)sender); + try + { + Task.Run(async () => + { + await Task.WhenAll(OrderedCompletionItemSources + .Where(n => n.IsValueCreated) + .Select(n => n.Value) + .Select(n => n.HandleViewClosedAsync((ITextView)sender))); + }); + } + catch + { + + } + } + + bool IAsyncCompletionBroker.IsCompletionActive(ITextView view) + { + return view.Properties.ContainsProperty(typeof(IAsyncCompletionSession)); + } + + bool IAsyncCompletionBroker.ShouldCommitCompletion(ITextView view, string edit, SnapshotPoint triggerLocation) + { + if (!((IAsyncCompletionBroker)this).IsCompletionActive(view)) + { + return false; + } + + foreach (var contentType in CompletionUtilities.GetBuffersForTriggerPoint(view, triggerLocation).Select(b => b.ContentType)) + { + if (TryGetKnownCommitCharacters(contentType, out var commitChars)) + { + if (commitChars.Contains(edit[0].ToString())) + { + if (GetSession(view).ShouldCommit(view, edit, triggerLocation)) + return true; + } + } + } + return false; + } + + private bool TryGetKnownCommitCharacters(IContentType contentType, out ImmutableArray commitChars) + { + if (_commitCharacters.TryGetValue(contentType, out commitChars)) + { + return commitChars.Any(); + } + var commitCharsBuilder = ImmutableArray.CreateBuilder(); + foreach (var source in GetCompletionItemSources(contentType)) + { + commitCharsBuilder.AddRange(source.GetPotentialCommitCharacters()); + } + commitChars = commitCharsBuilder.Distinct().ToImmutableArray(); + _commitCharacters = _commitCharacters.Add(contentType, commitChars); + return commitChars.Any(); + } + + bool IAsyncCompletionBroker.ShouldTriggerCompletion(ITextView view, string edit, SnapshotPoint triggerLocation) + { + var sourcesWithLocations = CompletionUtilities.GetCompletionSourcesWithMappedLocations(view, triggerLocation, GetCompletionItemSources); + return sourcesWithLocations.Any(p => p.Key.ShouldTriggerCompletion(edit, p.Value)); + } + + private IAsyncCompletionSession GetSession(ITextView view) + { + if (view.Properties.TryGetProperty(typeof(IAsyncCompletionSession), out IAsyncCompletionSession property)) + { + return property; + } + return null; + } + + void IAsyncCompletionBroker.SelectUp(ITextView view) => GetSession(view)?.SelectUp(); + void IAsyncCompletionBroker.SelectDown(ITextView view) => GetSession(view)?.SelectDown(); + void IAsyncCompletionBroker.SelectPageUp(ITextView view) => GetSession(view)?.SelectPageUp(); + void IAsyncCompletionBroker.SelectPageDown(ITextView view) => GetSession(view)?.SelectPageDown(); + + // Helper methods for telemetry + internal string GetItemSourceName(IAsyncCompletionItemSource source) => OrderedCompletionItemSources.FirstOrDefault(n => n.Value == source)?.Metadata.Name ?? string.Empty; + internal string GetCompletionServiceName(IAsyncCompletionService service) => OrderedCompletionServices.FirstOrDefault(n => n.Value == service)?.Metadata.Name ?? string.Empty; + + // Partiy with legacy telemetry + private void emulateLegacyCompletionTelemetry(IContentType contentType, ITextView view) + { + if (Logger == null || _firstInvocationReported) + return; + + string GetFileExtension(ITextBuffer buffer) + { + var documentFactoryService = TextDocumentFactoryService; + if (buffer != null && documentFactoryService != null) + { + ITextDocument currentDocument = null; + documentFactoryService.TryGetTextDocument(buffer, out currentDocument); + if (currentDocument != null && currentDocument.FilePath != null) + { + return System.IO.Path.GetExtension(currentDocument.FilePath); + } + } + return null; + } + var fileExtension = GetFileExtension(view.TextBuffer) ?? "Unknown"; + var reportedContentType = contentType?.ToString() ?? "Unknown"; + + _firstInvocationReported = true; + Logger.PostEvent(TelemetryEventType.Operation, "VS/Editor/IntellisenseFirstRun/Opened", TelemetryResult.Success, + ("VS.Editor.IntellisenseFirstRun.Opened.ContentType", reportedContentType), + ("VS.Editor.IntellisenseFirstRun.Opened.FileExtension", fileExtension)); + } + } +} diff --git a/src/Language/Impl/Language/Completion/AsyncCompletionSession.cs b/src/Language/Impl/Language/Completion/AsyncCompletionSession.cs new file mode 100644 index 0000000..0bfbdb6 --- /dev/null +++ b/src/Language/Impl/Language/Completion/AsyncCompletionSession.cs @@ -0,0 +1,555 @@ +using System; +using System.Collections.Generic; +using System.Collections.Immutable; +using System.Diagnostics; +using System.Linq; +using System.Threading; +using System.Threading.Tasks; +using Microsoft.VisualStudio.Language.Intellisense; +using Microsoft.VisualStudio.Text; +using Microsoft.VisualStudio.Text.Editor; +using Microsoft.VisualStudio.Text.Utilities; +using Microsoft.VisualStudio.Threading; + +namespace Microsoft.VisualStudio.Language.Intellisense.Implementation +{ + /// + /// Holds a state of the session + /// and a reference to the UI element + /// + internal class AsyncCompletionSession : IAsyncCompletionSession + { + // Available data and services + // TODO: consider storing MappingPoint instead of SnapshotPoint + private readonly IDictionary _completionProviders; + private readonly IAsyncCompletionService _completionService; + private readonly JoinableTaskFactory _jtf; + private readonly ICompletionUIProvider _uiFactory; + private readonly IAsyncCompletionBroker _broker; + private readonly ITextView _view; + private readonly TelemetryData _telemetryData; + + // Presentation: + ICompletionUI _gui; // Must be accessed from GUI thread + const int FirstIndex = 0; + readonly int PageStepSize; + + // Computation state machine + private ModelComputation _computation; + private readonly CancellationTokenSource _computationCancellation = new CancellationTokenSource(); + int _lastFilteringTaskId; + + // When set, UI will no longer be updated + private bool _isDismissed; + // When set, we won't send dismissed telemetry + private bool _committed; + + public AsyncCompletionSession(JoinableTaskFactory jtf, ICompletionUIProvider uiFactory, IDictionary providers, IAsyncCompletionService service, AsyncCompletionBroker broker, ITextView view) + { + _jtf = jtf; + _uiFactory = uiFactory; + _broker = broker; + _completionProviders = providers; + _completionService = service; + _view = view; + _telemetryData = new TelemetryData(broker); + PageStepSize = uiFactory?.ResultsPerPage ?? 1; + _view.Caret.PositionChanged += OnCaretPositionChanged; + } + + public void Commit(string edit) + { + var lastModel = _computation.WaitAndGetResult(); + + if (lastModel.UseSuggestionMode && !String.IsNullOrEmpty(edit)) + return; // In suggestion mode, allow only explicit commits (click, tab, e.g. not tied to a text change) + else if (lastModel.SelectSuggestionMode && lastModel.SuggestionIsEmpty) + return; // In suggestion mode, don't commit empty suggestion (suggestion item temporarily shows description of suggestion mode) + else if (lastModel.SelectSuggestionMode && !lastModel.SuggestionIsEmpty) + Commit(edit, lastModel.SuggestionModeItem.CompletionItem); + else if (!lastModel.PresentedItems.Any()) + return; // There is nothing to commit + else + Commit(edit, lastModel.PresentedItems.ElementAt(lastModel.SelectedIndex).CompletionItem); + } + + public void Commit(string edit, CompletionItem itemToCommit) + { + var lastModel = _computation.WaitAndGetResult(); + + // TODO: ensure we are on the UI thread + + _telemetryData.UiStopwatch.Restart(); + if (itemToCommit.CustomCommit) + { + // Pass appropriate buffer to the item's provider + var buffer = _completionProviders[itemToCommit.Source].Snapshot.TextBuffer; + itemToCommit.Source.CustomCommit(_view, buffer, itemToCommit, lastModel.ApplicableSpan, edit); + } + else + { + var buffer = _view.TextBuffer; + var bufferEdit = buffer.CreateEdit(); + bufferEdit.Replace(lastModel.ApplicableSpan.GetSpan(buffer.CurrentSnapshot), itemToCommit.InsertText + edit); + bufferEdit.Apply(); + } + _telemetryData.UiStopwatch.Stop(); + _telemetryData.RecordCommitAndSend(_telemetryData.UiStopwatch.ElapsedMilliseconds, itemToCommit, edit); + _committed = true; + } + + void IAsyncCompletionSession.DismissAndHide() + { + // TODO: protect from race conditions when we get two Dismiss requests + _isDismissed = true; + _view.Caret.PositionChanged -= OnCaretPositionChanged; + _computationCancellation.Cancel(); + + if (!_committed) + _telemetryData.RecordDismissedAndSend(); + + if (_gui == null) + return; // nothing to hide + + // TODO: ensure we are on the UI thread + _gui.FiltersChanged -= OnFiltersChanged; + _gui.CompletionItemCommitted -= OnItemCommitted; + _gui.Hide(); + _gui.Dispose(); + } + + public void OpenOrUpdate(ITextView view, ITrackingSpan trackedEdit, CompletionTrigger trigger, SnapshotPoint triggerLocation) + { + if (_computation == null) + { + _computation = new ModelComputation(PrioritizedTaskScheduler.AboveNormalInstance, _computationCancellation.Token); + _computation.Enqueue((model, token) => GetInitialModel(view, trackedEdit, trigger, triggerLocation, token)); + } + + var taskId = Interlocked.Increment(ref _lastFilteringTaskId); + _computation.Enqueue((model, token) => UpdateSnapshot(model, trigger, triggerLocation, token, taskId), UpdateUI); + } + + public void SelectDown() + { + _computation.Enqueue((model, token) => UpdateSelectedItem(model, +1, token), UpdateUI); + } + + public void SelectPageDown() + { + _computation.Enqueue((model, token) => UpdateSelectedItem(model, +PageStepSize, token), UpdateUI); + } + + public void SelectUp() + { + _computation.Enqueue((model, token) => UpdateSelectedItem(model, -1, token), UpdateUI); + } + + public void SelectPageUp() + { + _computation.Enqueue((model, token) => UpdateSelectedItem(model, -PageStepSize, token), UpdateUI); + } + + private void OnFiltersChanged(object sender, CompletionFilterChangedEventArgs e) + { + var taskId = Interlocked.Increment(ref _lastFilteringTaskId); + _computation.Enqueue((model, token) => UpdateFilters(model, e.Filters, token, taskId), UpdateUI); + } + + private void OnItemCommitted(object sender, CompletionItemCommittedEventArgs e) + { + Commit(String.Empty, e.Item); + _broker.Dismiss(_view); + } + + /// + /// Monitors when user scrolled outside of the completion area. + /// Note that this event is not raised during regular typing + /// Also note that typing stretches the completion area + /// + private void OnCaretPositionChanged(object sender, CaretPositionChangedEventArgs e) + { + // http://source.roslyn.io/#Microsoft.CodeAnalysis.EditorFeatures/Implementation/IntelliSense/Completion/Controller_CaretPositionChanged.cs,40 + // enqueue a task to see if the caret is still within the broundary + _computation.Enqueue((model, token) => HandleCaretPositionChanged(model, e.NewPosition), UpdateUI); + } + + private async Task UpdateUI(CompletionModel model) + { + if (_uiFactory == null) return; + await _jtf.SwitchToMainThreadAsync(); + + if (_isDismissed) + return; + + _telemetryData.UiStopwatch.Restart(); + if (_gui == null) + { + _gui = _uiFactory.GetUI(_view); + _gui.Open(new CompletionPresentation(model.PresentedItems, model.Filters, model.ApplicableSpan, model.UseSoftSelection, model.UseSuggestionMode, model.SelectSuggestionMode, model.SelectedIndex, model.SuggestionModeItem)); + _gui.FiltersChanged += OnFiltersChanged; + _gui.CompletionItemCommitted += OnItemCommitted; + } + else + { + _gui.Update(new CompletionPresentation(model.PresentedItems, model.Filters, model.ApplicableSpan, model.UseSoftSelection, model.UseSuggestionMode, model.SelectSuggestionMode, model.SelectedIndex, model.SuggestionModeItem)); + } + _telemetryData.UiStopwatch.Stop(); + _telemetryData.RecordRendering(_telemetryData.UiStopwatch.ElapsedMilliseconds); + + await TaskScheduler.Default; + } + + /// + /// Creates a new model and populates it with initial data + /// + private async Task GetInitialModel(ITextView view, ITrackingSpan trackedEdit, CompletionTrigger trigger, SnapshotPoint triggerLocation, CancellationToken token) + { + _telemetryData.ComputationStopwatch.Restart(); + // Map the trigger location to respective view for each completion provider + var nestedResults = await Task.WhenAll(_completionProviders.Select(p => p.Key.GetCompletionContextAsync(trigger, p.Value))); + var originalCompletionItems = nestedResults.SelectMany(n => n.Items).ToImmutableArray(); + + var availableFilters = nestedResults + .SelectMany(n => n.Items) + .SelectMany(n => n.Filters) + .Distinct() + .Select(n => new CompletionFilterWithState(n, true)) + .ToImmutableArray(); + + // Note: do not use the tracked edit from the editor. Exclusively rely on data from the completion providers + var spans = nestedResults + .Select(n => n.ApplicableToSpan) + .Select(s => view.BufferGraph.CreateMappingSpan(s, SpanTrackingMode.EdgeNegative)) + .Select(s => new SnapshotSpan( + s.Start.GetPoint(triggerLocation.Snapshot, PositionAffinity.Predecessor).Value, + s.End.GetPoint(triggerLocation.Snapshot, PositionAffinity.Predecessor).Value)); + + var extent = new SnapshotSpan( + spans.Min(n => n.Start), + spans.Max(n => n.End)); + var applicableSpan = triggerLocation.Snapshot.CreateTrackingSpan(extent, SpanTrackingMode.EdgeInclusive); + + var useSoftSelection = nestedResults.Any(n => n.UseSoftSelection); + var useSuggestionMode = nestedResults.Any(n => n.UseSuggestionMode); + var suggestionModeDescription = nestedResults.FirstOrDefault(n => !String.IsNullOrEmpty(n.SuggestionModeDescription)).SuggestionModeDescription ?? String.Empty; + + _telemetryData.ComputationStopwatch.Stop(); + _telemetryData.RecordInitialModel(_telemetryData.ComputationStopwatch.ElapsedMilliseconds, _completionProviders.Keys, originalCompletionItems.Length, _completionService); + + return new CompletionModel(originalCompletionItems, applicableSpan, triggerLocation.Snapshot, availableFilters, useSoftSelection, useSuggestionMode, suggestionModeDescription); + } + + /// + /// User has moved the caret. Ensure that the caret is still within the applicable span. If not, dismiss the session. + /// + /// + private async Task HandleCaretPositionChanged(CompletionModel model, CaretPosition caretPosition) + { + if (!(model.ApplicableSpan.GetSpan(caretPosition.VirtualBufferPosition.Position.Snapshot).IntersectsWith(new SnapshotSpan(caretPosition.VirtualBufferPosition.Position, 0)))) + { + await _jtf.SwitchToMainThreadAsync(); + _broker.Dismiss(_view); + } + return model; + } + + /// + /// User has typed + /// + private async Task UpdateSnapshot(CompletionModel model, CompletionTrigger trigger, SnapshotPoint triggerLocation, CancellationToken token, int thisId) + { + // Filtering got preempted, so store the most recent snapshot for the next time we filter + if (token.IsCancellationRequested || thisId != _lastFilteringTaskId) + return model.WithSnapshot(triggerLocation.Snapshot); + + // Dismiss if we are outside of the applicable span + // TODO: dismiss if applicable span was reduced to zero AND moved again (e.g. first backspace keeps completion open, second backspace closes it) + if (triggerLocation < model.ApplicableSpan.GetStartPoint(triggerLocation.Snapshot) || triggerLocation > model.ApplicableSpan.GetEndPoint(triggerLocation.Snapshot)) + { + await _jtf.SwitchToMainThreadAsync(); + _broker.Dismiss(_view); // We need to dismiss through the broker, so that it updates its state. + return model; + } + + _telemetryData.ComputationStopwatch.Restart(); + + var filteredCompletion = await _completionService.UpdateCompletionListAsync( + model.AllItems, + trigger, + triggerLocation.Snapshot, + model.ApplicableSpan, + model.Filters); + + if (model.UseSuggestionMode) + { + var filterText = model.ApplicableSpan.GetText(triggerLocation.Snapshot); + CompletionItemWithHighlight suggestionModeItem; + if (String.IsNullOrWhiteSpace(filterText)) + { + suggestionModeItem = new CompletionItemWithHighlight(new CompletionItem(model.SuggestionModeDescription, null), ImmutableArray.Empty); + model = model.WithEmptySuggestionItem(suggestionModeItem); + } + else + { + suggestionModeItem = new CompletionItemWithHighlight(new CompletionItem(filterText, null), ImmutableArray.Create(new Span(0, filterText.Length))); + model = model.WithSuggestionItem(suggestionModeItem); + } + } + + _telemetryData.ComputationStopwatch.Stop(); + _telemetryData.RecordProcessing(_telemetryData.ComputationStopwatch.ElapsedMilliseconds, filteredCompletion.Items.Count()); + + // TODO: if filtered completion has no items to display, + // reuse previous filtered completion, but with soft selection + return model.WithSnapshot(triggerLocation.Snapshot).WithPresentedItems(filteredCompletion.Items, filteredCompletion.SelectedItemIndex); + } + + /// + /// User has changed a filter + /// + private async Task UpdateFilters(CompletionModel model, ImmutableArray filters, CancellationToken token, int thisId) + { + _telemetryData.RecordChangingFilters(); + + // Filtering got preempted, so store the most updated filters for the next time we filter + if (token.IsCancellationRequested || thisId != _lastFilteringTaskId) + return model.WithFilters(filters); + + var filteredCompletion = await _completionService.UpdateCompletionListAsync( + model.AllItems, + new CompletionTrigger(CompletionTriggerReason.FilterChange), + model.Snapshot, + model.ApplicableSpan, + filters); + + return model.WithFilters(filters).WithPresentedItems(filteredCompletion.Items, filteredCompletion.SelectedItemIndex); + } + +#pragma warning disable CS1998 // Async method lacks 'await' operators and will run synchronously + /// + /// User is scrolling the list + /// + private async Task UpdateSelectedItem(CompletionModel model, int offset, CancellationToken token) +#pragma warning restore CS1998 // Async method lacks 'await' operators and will run synchronously + { + _telemetryData.RecordScrolling(); + + if (!model.PresentedItems.Any()) + { + // No-op if there are no items + if (model.UseSuggestionMode) + { + // Unless there is a suggestion mode item. Select it. + return model.WithSuggestionItemSelected(); + } + return model; + } + + var lastIndex = model.PresentedItems.Count() - 1; + var currentIndex = model.SelectSuggestionMode ? -1 : model.SelectedIndex; + + if (offset > 0) // Scrolling down. Stop at last index then go to first index. + { + if (currentIndex == lastIndex) + { + if (model.UseSuggestionMode) + return model.WithSuggestionItemSelected(); + else + return model.WithSelectedIndex(FirstIndex); + } + var newIndex = currentIndex + offset; + return model.WithSelectedIndex(Math.Min(newIndex, lastIndex)); + } + else // Scrolling up. Stop at first index then go to last index. + { + if (currentIndex < FirstIndex) + { + // Suggestion mode item is selected. Go to the last item. + return model.WithSelectedIndex(lastIndex); + } + else if (currentIndex == FirstIndex) + { + // The first item is selected. If there is a suggestion, select it. + if (model.UseSuggestionMode) + return model.WithSuggestionItemSelected(); + else + return model.WithSelectedIndex(lastIndex); + } + var newIndex = currentIndex + offset; + return model.WithSelectedIndex(Math.Max(newIndex, FirstIndex)); + } + } + + /// + /// This method creates a mapping point from the top-buffer trigger location + /// then iterates through completion item sources pertinent to this session. + /// It maps triggerLocation to each source's buffer + /// Ensures that we work only with sources applicable to current location + /// and returns whether any source would like to commit completion + /// + public bool ShouldCommit(ITextView view, string edit, SnapshotPoint triggerLocation) + { + var mappingPoint = view.BufferGraph.CreateMappingPoint(triggerLocation, PointTrackingMode.Negative); + return _completionProviders + .Select(p => (p, mappingPoint.GetPoint(p.Value.Snapshot.TextBuffer, PositionAffinity.Predecessor))) + .Where(n => n.Item2.HasValue) + .Any(n => n.Item1.Key.ShouldCommitCompletion(edit, n.Item2.Value)); + // Remove previous line and uncomment the following lines to get the specific IAsyncCompletionItemSource that wanted to commit + /* + .Where(n => n.Item1.Key.ShouldCommitCompletion(edit, n.Item2.Value)) + .Select(n => n.Item1.Key) + .FirstOrDefault(); + */ + } + + private class TelemetryData + { + // Constants + internal const string CommitEvent = "VS/Editor/Completion/Committed"; + internal const string DismissedEvent = "VS/Editor/Completion/Dismissed"; + + // Collected data + internal string InitialItemSources { get; private set; } + internal int InitialItemCount { get; private set; } + internal long InitialModelDuration { get; private set; } + + internal string CompletionService { get; private set; } + internal long TotalProcessingDuration { get; private set; } + internal int TotalProcessingCount { get; private set; } + + internal long InitialRenderingDuration { get; private set; } + internal long TotalRenderingDuration { get; private set; } + internal int TotalRenderingCount { get; private set; } + + internal bool UserEverScrolled { get; private set; } + internal bool UserEverSetFilters { get; private set; } + internal bool UserLastScrolled { get; private set; } + internal int LastItemCount { get; private set; } + + // Property names + internal const string InitialItemSourcesProperty = "Property.InitialData.Sources"; + internal const string InitialItemCountProperty = "Property.ItemCount.Initial"; + internal const string InitialModelDurationProperty = "Property.InitialData.Duration"; + internal const string CompletionServiceProperty = "Property.Processing.Service"; + internal const string TotalProcessingDurationProperty = "Property.Processing.TotalDuration"; + internal const string TotalProcessingCountProperty = "Property.Processing.TotalCount"; + internal const string InitialRenderingDurationProperty = "Property.Rendering.InitialDuration"; + internal const string TotalRenderingDurationProperty = "Property.Rendering.TotalDuration"; + internal const string TotalRenderingCountProperty = "Property.Rendering.TotalCount"; + internal const string UserEverScrolledProperty = "Property.UserScrolled.Session"; + internal const string UserEverSetFiltersProperty = "Property.UserSetFilters.Session"; + internal const string UserLastScrolledProperty = "Property.UserScrolled.Last"; + internal const string LastItemCountProperty = "Property.ItemCount.Final"; + internal const string CustomCommitProperty = "Property.Commit.CustomCommit"; + internal const string CommittedItemSourceProperty = "Property.Commit.ItemSource"; + internal const string CommitDurationProperty = "Property.Commit.Duration"; + internal const string CommitTriggerProperty = "Property.Commit.Trigger"; + + /// + /// Tracks time spent on the worker thread - getting data, filtering and sorting + /// + internal Stopwatch ComputationStopwatch { get; } + + /// + /// Tracks time spent on the UI thread - either rendering or committing + /// + internal Stopwatch UiStopwatch { get; } + + private readonly AsyncCompletionBroker _broker; + private readonly ILoggingServiceInternal _logger; + + public TelemetryData(AsyncCompletionBroker broker) + { + ComputationStopwatch = new Stopwatch(); + UiStopwatch = new Stopwatch(); + _broker = broker; + _logger = broker.Logger; + } + + internal string GetItemSourceName(IAsyncCompletionItemSource source) => _broker.GetItemSourceName(source); + internal string GetCompletionServiceName(IAsyncCompletionService service) => _broker.GetCompletionServiceName(service); + + internal void RecordInitialModel(long processingTime, ICollection sources, int initialItemCount, IAsyncCompletionService service) + { + InitialItemCount = initialItemCount; + InitialItemSources = String.Join(" ", sources.Select(n => _broker.GetItemSourceName(n))); + InitialModelDuration = processingTime; + CompletionService = _broker.GetCompletionServiceName(service); // Service does not participate in getting the initial model, but this is a good place to get this data + } + + internal void RecordProcessing(long processingTime, int itemCount) + { + UserLastScrolled = false; + TotalProcessingCount++; + TotalProcessingDuration += processingTime; + LastItemCount = itemCount; + } + + internal void RecordRendering(long processingTime) + { + if (TotalRenderingCount == 0) + InitialRenderingDuration = processingTime; + TotalRenderingCount++; + TotalRenderingDuration += processingTime; + } + + internal void RecordScrolling() + { + UserEverScrolled = true; + UserLastScrolled = true; + } + + internal void RecordChangingFilters() + { + UserEverSetFilters = true; + } + + internal void RecordCommitAndSend(long commitDuration, CompletionItem committedItem, string edit) + { + _logger?.PostEvent(TelemetryEventType.Operation, + TelemetryData.CommitEvent, + TelemetryResult.Success, + (InitialItemSourcesProperty, InitialItemSources ?? string.Empty), + (InitialItemCountProperty, InitialItemCount), + (InitialModelDurationProperty, InitialModelDuration), + (CompletionServiceProperty, CompletionService), + (TotalProcessingDurationProperty, TotalProcessingDuration), + (TotalProcessingCountProperty, TotalProcessingCount), + (InitialRenderingDurationProperty, InitialRenderingDuration), + (TotalRenderingDurationProperty, TotalRenderingDuration), + (TotalRenderingCountProperty, TotalRenderingCount), + (UserEverScrolledProperty, UserEverScrolled), + (UserEverSetFiltersProperty, UserEverSetFilters), + (UserLastScrolledProperty, UserLastScrolled), + (LastItemCountProperty, LastItemCount), + (CustomCommitProperty, committedItem.CustomCommit), + (CommittedItemSourceProperty, GetItemSourceName(committedItem.Source)), + (CommitDurationProperty, commitDuration), + (CommitTriggerProperty, edit ?? string.Empty) + ); + } + + internal void RecordDismissedAndSend() + { + _logger?.PostEvent(TelemetryEventType.Operation, + TelemetryData.DismissedEvent, + TelemetryResult.Success, + (InitialItemSourcesProperty, InitialItemSources ?? string.Empty), + (InitialItemCountProperty, InitialItemCount), + (InitialModelDurationProperty, InitialModelDuration), + (CompletionServiceProperty, CompletionService), + (LastItemCountProperty, LastItemCount), + (TotalProcessingDurationProperty, TotalProcessingDuration), + (TotalProcessingCountProperty, TotalProcessingCount), + (InitialRenderingDurationProperty, InitialRenderingDuration), + (TotalRenderingDurationProperty, TotalRenderingDuration), + (TotalRenderingCountProperty, TotalRenderingCount), + (UserEverScrolledProperty, UserEverScrolled), + (UserEverSetFiltersProperty, UserEverSetFilters), + (UserLastScrolledProperty, UserLastScrolled) + ); + } + } + } +} diff --git a/src/Language/Impl/Language/Completion/CompletionModel.cs b/src/Language/Impl/Language/Completion/CompletionModel.cs new file mode 100644 index 0000000..7fd95ac --- /dev/null +++ b/src/Language/Impl/Language/Completion/CompletionModel.cs @@ -0,0 +1,299 @@ +using System; +using System.Collections.Generic; +using System.Collections.Immutable; +using System.Linq; +using System.Threading; +using System.Threading.Tasks; +using Microsoft.VisualStudio.Language.Intellisense; +using Microsoft.VisualStudio.Text; + +namespace Microsoft.VisualStudio.Language.Intellisense.Implementation +{ + class CompletionModel + { + /// + /// All items, as provided by completion item sources. + /// + public readonly ImmutableArray AllItems; + + /// + /// Span pertinent to this completion model. + /// + public readonly ITrackingSpan ApplicableSpan; + + /// + /// Snapshot pertinent to this completion model. + /// + public readonly ITextSnapshot Snapshot; + + /// + /// Filters involved in this completion model, including their availability and selection state. + /// + public readonly ImmutableArray Filters; + + /// + /// Items to be displayed in the UI. + /// + public readonly IEnumerable PresentedItems; + + /// + /// Index of item to select. Use -1 to select nothing, when suggestion mode item should be selected. + /// + public readonly int SelectedIndex; + + /// + /// Whether selection should be displayed as soft selection. + /// + public readonly bool UseSoftSelection; + + /// + /// Whether suggestion mode item should be visible. + /// + public readonly bool UseSuggestionMode; + + /// + /// Whether suggestion mode item should be selected. + /// + public readonly bool SelectSuggestionMode; + + /// + /// Text to display in place of suggestion mode when filtered text is empty. + /// + public readonly string SuggestionModeDescription; + + /// + /// Item to display as suggestion mode item + /// + public readonly CompletionItemWithHighlight SuggestionModeItem; + + /// + /// When true, committing the suggestion mode item is a no-op. + /// + public readonly bool SuggestionIsEmpty; + + /// + /// Constructor for the initial model + /// + public CompletionModel(ImmutableArray originalItems, ITrackingSpan applicableSpan, ITextSnapshot snapshot, ImmutableArray filters, bool useSoftSelection, bool useSuggestionMode, string suggestionModeDescription) + { + AllItems = originalItems; + ApplicableSpan = applicableSpan; + Snapshot = snapshot; + Filters = filters; + SelectedIndex = 0; + UseSoftSelection = useSoftSelection; + UseSuggestionMode = useSuggestionMode; + SelectSuggestionMode = useSuggestionMode; + SuggestionModeDescription = suggestionModeDescription; + SuggestionModeItem = CompletionItemWithHighlight.Empty; + } + + /// + /// Private constructor for the With* methods + /// + private CompletionModel(ImmutableArray originalItems, ITrackingSpan applicableSpan, ITextSnapshot snapshot, ImmutableArray filters, IEnumerable presentedItems, bool useSoftSelection, bool useSuggestionMode, string suggestionModeDescription, int selectedIndex, bool selectSuggestionMode, CompletionItemWithHighlight suggestionModeItem, bool suggestionIsEmpty) + { + AllItems = originalItems; + ApplicableSpan = applicableSpan; + Snapshot = snapshot; + Filters = filters; + PresentedItems = presentedItems; + SelectedIndex = selectedIndex; + UseSoftSelection = useSoftSelection; + UseSuggestionMode = useSuggestionMode; + SelectSuggestionMode = selectSuggestionMode; + SuggestionModeDescription = suggestionModeDescription; + SuggestionModeItem = suggestionModeItem; + SuggestionIsEmpty = suggestionIsEmpty; + } + + public CompletionModel WithPresentedItems(IEnumerable newPresentedItems, int newSelectedIndex) + { + return new CompletionModel( + originalItems: AllItems, + applicableSpan: ApplicableSpan, + snapshot: Snapshot, + filters: Filters, + presentedItems: newPresentedItems, // Updated + useSoftSelection: UseSoftSelection, + useSuggestionMode: UseSuggestionMode, + suggestionModeDescription: SuggestionModeDescription, + selectedIndex: newSelectedIndex, // Updated + selectSuggestionMode: SelectSuggestionMode, + suggestionModeItem: SuggestionModeItem, + suggestionIsEmpty: SuggestionIsEmpty + ); + } + + public CompletionModel WithSnapshot(ITextSnapshot newSnapshot) + { + return new CompletionModel( + originalItems: AllItems, + applicableSpan: ApplicableSpan, + snapshot: newSnapshot, // Updated + filters: Filters, + presentedItems: PresentedItems, + useSoftSelection: UseSoftSelection, + useSuggestionMode: UseSuggestionMode, + suggestionModeDescription: SuggestionModeDescription, + selectedIndex: SelectedIndex, + selectSuggestionMode: SelectSuggestionMode, + suggestionModeItem: SuggestionModeItem, + suggestionIsEmpty: SuggestionIsEmpty + ); + } + + public CompletionModel WithFilters(ImmutableArray newFilters) + { + return new CompletionModel( + originalItems: AllItems, + applicableSpan: ApplicableSpan, + snapshot: Snapshot, + filters: newFilters, // Updated + presentedItems: PresentedItems, + useSoftSelection: UseSoftSelection, + useSuggestionMode: UseSuggestionMode, + suggestionModeDescription: SuggestionModeDescription, + selectedIndex: SelectedIndex, + selectSuggestionMode: SelectSuggestionMode, + suggestionModeItem: SuggestionModeItem, + suggestionIsEmpty: SuggestionIsEmpty + ); + } + + public CompletionModel WithSelectedIndex(int newIndex) + { + return new CompletionModel( + originalItems: AllItems, + applicableSpan: ApplicableSpan, + snapshot: Snapshot, + filters: Filters, + presentedItems: PresentedItems, + useSoftSelection: false, // Explicit selection and soft selection are mutually exclusive + useSuggestionMode: UseSuggestionMode, + suggestionModeDescription: SuggestionModeDescription, + selectedIndex: newIndex, // Updated + selectSuggestionMode: false, // Explicit selection of regular item + suggestionModeItem: SuggestionModeItem, + suggestionIsEmpty: SuggestionIsEmpty + ); + } + + public CompletionModel WithSuggestionItemSelected() + { + return new CompletionModel( + originalItems: AllItems, + applicableSpan: ApplicableSpan, + snapshot: Snapshot, + filters: Filters, + presentedItems: PresentedItems, + useSoftSelection: false, // Explicit selection and soft selection are mutually exclusive + useSuggestionMode: UseSuggestionMode, + suggestionModeDescription: SuggestionModeDescription, + selectedIndex: -1, // Deselect regular item + selectSuggestionMode: true, // Explicit selection of suggestion item + suggestionModeItem: SuggestionModeItem, + suggestionIsEmpty: SuggestionIsEmpty + ); + } + + internal CompletionModel WithSuggestionItem(CompletionItemWithHighlight newSuggestionModeItem) + { + return new CompletionModel( + originalItems: AllItems, + applicableSpan: ApplicableSpan, + snapshot: Snapshot, + filters: Filters, + presentedItems: PresentedItems, + useSoftSelection: UseSoftSelection, + useSuggestionMode: UseSuggestionMode, + suggestionModeDescription: SuggestionModeDescription, + selectedIndex: SelectedIndex, + selectSuggestionMode: SelectSuggestionMode, + suggestionModeItem: newSuggestionModeItem, // Updated + suggestionIsEmpty: false // This method guarantees that the suggestion is not empty + ); + } + + internal CompletionModel WithEmptySuggestionItem(CompletionItemWithHighlight newSuggestionModeItem) + { + return new CompletionModel( + originalItems: AllItems, + applicableSpan: ApplicableSpan, + snapshot: Snapshot, + filters: Filters, + presentedItems: PresentedItems, + useSoftSelection: UseSoftSelection, + useSuggestionMode: UseSuggestionMode, + suggestionModeDescription: SuggestionModeDescription, + selectedIndex: SelectedIndex, + selectSuggestionMode: SelectSuggestionMode, + suggestionModeItem: newSuggestionModeItem, // Updated + suggestionIsEmpty: true // This method guarantees that the suggestion is empty + ); + } + } + + class ModelComputation + { + Task _lastTask = Task.FromResult(default(TModel)); + private Task _notifyUITask = Task.CompletedTask; + private readonly TaskScheduler _computationTaskScheduler; + private readonly CancellationToken _token; + private readonly CancellationTokenSource _uiCancellation; + + public ModelComputation(TaskScheduler computationTaskScheduler, CancellationToken token) + { + _computationTaskScheduler = computationTaskScheduler; + _token = token; + _uiCancellation = new CancellationTokenSource(); + } + + /// + /// Schedules work to be done on the background, + /// potentially preempted by another piece of work scheduled in the future. + /// + public void Enqueue(Func> transformation) + { + Enqueue(transformation, null); + } + + /// + /// Schedules work to be done on the background, + /// potentially preempted by another piece of work scheduled in the future, + /// followed by a single piece of work that will execute once all background work is completed. + /// + public void Enqueue(Func> transformation, Func updateUI) + { + // This method is based on Roslyn's ModelComputation.ChainTaskAndNotifyControllerWhenFinished + var nextTask = _lastTask.ContinueWith(t => transformation(t.Result, _token), _computationTaskScheduler).Unwrap(); + _lastTask = nextTask; + + _notifyUITask = Task.Factory.ContinueWhenAll( + new[] { _notifyUITask, nextTask }, + async existingTasks => + { + if (existingTasks.All(t => t.Status == TaskStatus.RanToCompletion)) + { + if (nextTask == _lastTask && updateUI != null) + { + await updateUI(nextTask.Result); + } + } + }, + _uiCancellation.Token + ); + } + + /// + /// Blocks, waiting for all background work to finish. + /// Ignores the last piece of work a.k.a. "updateUI" + /// + public TModel WaitAndGetResult() + { + _uiCancellation.Cancel(); + _lastTask.Wait(); + return _lastTask.Result; + } + } +} diff --git a/src/Language/Impl/Language/Completion/CompletionUtilities.cs b/src/Language/Impl/Language/Completion/CompletionUtilities.cs new file mode 100644 index 0000000..613ff70 --- /dev/null +++ b/src/Language/Impl/Language/Completion/CompletionUtilities.cs @@ -0,0 +1,119 @@ +using System; +using System.Collections.Generic; +using System.Collections.Immutable; +using System.Linq; +using Microsoft.VisualStudio.Language.Intellisense; +using Microsoft.VisualStudio.Text; +using Microsoft.VisualStudio.Text.Editor; +using Microsoft.VisualStudio.Utilities; + +namespace Microsoft.VisualStudio.Language.Intellisense.Implementation +{ + internal static class CompletionUtilities + { + + internal static IEnumerable GetBuffersForTriggerPoint(ITextView view, SnapshotPoint point) + { + // We are looking at the buffer to the left of the caret. + return view.BufferGraph.GetTextBuffers(n => + view.BufferGraph.MapDownToBuffer(point, PointTrackingMode.Negative, n, PositionAffinity.Predecessor) != null); + } + + internal static IDictionary GetCompletionSourcesWithMappedLocations(ITextView view, SnapshotPoint originalPoint, Func> getCompletionItemSources) + { + // This method is created based on EditorCommandHandlerService.GetOrderedBuffersAndCommandHandlers + + // This method creates a collection of IAsyncCompletionItemSource, SnapshotPoint pairs + // that where the SnapshotPoint is originalPoint translated to the buffer pertinent to the IAsyncCompletionItemSource + // The collection is a dictionary such that each completion item source appears only once. + + // A general idea is that command handlers matching more specifically content type of buffers higher in the buffer + // graph should be executed before those matching buffers lower in the graph or less specific content types. + + // So for example in a projection scenario (projection buffer containing C# buffer), 3 command handlers + // matching "projection", "CSharp" and "any" content types will be ordered like this: + // 1. command handler matching "projection" content type is executed on the projection buffer + // 2. command handler matching "CSharp" content type is executed on the C# buffer + // 3. command handler matching "any" content type is executed on the projection buffer + + // The ordering algorithm is as follows: + // 1. Create an ordered list of all affected buffers in the buffer graph (TODO: this should be an extensibility point) + // by mapping caret position down and up the buffer graph. In a typical projection scenario + // (projection buffer containing C# buffer) that will produce (projection buffer, C# buffer) sequence. + // 2. Create an ordered list of all content types in those buffers from most to least specific while + // resolving ties (such as between "projection" and "text" content types) per buffer order. Again, in + // a projection scenario that will result in "projection, CSharp, text, any" sequence. + // 3. Now for each content type in the list and for each buffer in the buffer list find all command handlers + // matching that content type (exactly) and pair them with buffers. That will result in aforementioned + // list of (buffer, handler) pairs. + + var sortedContentTypes = new SortedSet(ContentTypeComparer.Instance); + var result = new Dictionary(); + + var mappedPoints = GetPointsOnAvailableBuffers(view, originalPoint); + foreach (var mappedPoint in mappedPoints) + { + AddContentTypeHierarchy(sortedContentTypes, mappedPoint.Snapshot.ContentType); + } + + foreach (var contentType in sortedContentTypes) + { + foreach (var mappedPoint in mappedPoints) + { + if (mappedPoint.Snapshot.ContentType.IsOfType(contentType.TypeName)) + { + foreach (var source in getCompletionItemSources(contentType)) + { + if (!result.ContainsKey(source)) + result.Add(source, mappedPoint); + } + } + } + } + return result; + } + + private static IEnumerable GetPointsOnAvailableBuffers(ITextView view, SnapshotPoint point) + { + var mappingPoint = view.BufferGraph.CreateMappingPoint(point, PointTrackingMode.Negative); + var buffers = view.BufferGraph.GetTextBuffers(b => mappingPoint.GetPoint(b, PositionAffinity.Predecessor) != null); + var pointsInBuffers = buffers.Select(b => mappingPoint.GetPoint(b, PositionAffinity.Predecessor).Value); + return pointsInBuffers; + } + + private static void AddContentTypeHierarchy(SortedSet sortedContentTypes, IContentType contentType) + { + sortedContentTypes.Add(contentType); + + foreach (var baseContentType in contentType.BaseTypes) + { + AddContentTypeHierarchy(sortedContentTypes, baseContentType); + } + } + + /// + /// Custom comparer for sorting content types + /// + private class ContentTypeComparer : IComparer + { + public static ContentTypeComparer Instance = new ContentTypeComparer(); + + public int Compare(IContentType x, IContentType y) + { + if (x == y) + { + return 0; + } + + // If x is of type y (e.g. "code" is of type "text") that means it's more specific and so + // consider it less than y (to order higher than y). + if (x.IsOfType(y.TypeName)) + { + return -1; + } + + return 1; + } + } + } +} diff --git a/src/Language/Impl/Language/Completion/DefaultCompletionService.cs b/src/Language/Impl/Language/Completion/DefaultCompletionService.cs new file mode 100644 index 0000000..90a66ec --- /dev/null +++ b/src/Language/Impl/Language/Completion/DefaultCompletionService.cs @@ -0,0 +1,238 @@ +using System.Collections.Generic; +using System.Linq; +using System.Threading.Tasks; +using Microsoft.VisualStudio.Language.Intellisense; +using System.Collections.Immutable; +using Microsoft.VisualStudio.Text; +using Microsoft.VisualStudio.Text.PatternMatching; +using Microsoft.VisualStudio.Utilities; +using Microsoft.VisualStudio.Core.Imaging; +using System; + +#if NET46 +using System.ComponentModel.Composition; +#else +using System.Composition; +using Microsoft.VisualStudio.Text.Editor; +#endif + +namespace Microsoft.VisualStudio.Language.Intellisense.Implementation +{ + [Export(typeof(IAsyncCompletionService))] + [Name("Default completion service")] + [ContentType("text")] + public class DefaultCompletionService : IAsyncCompletionService + { + [Import] + public IPatternMatcherFactory PatternMatcherFactory { get; set; } + +#pragma warning disable CS1998 // Async method lacks 'await' operators and will run synchronously + async Task IAsyncCompletionService.UpdateCompletionListAsync(IEnumerable originalList, CompletionTrigger trigger, ITextSnapshot snapshot, ITrackingSpan applicableSpan, ImmutableArray filters) +#pragma warning restore CS1998 // Async method lacks 'await' operators and will run synchronously + { + // Filter by text + var filterText = applicableSpan.GetText(snapshot); + if (string.IsNullOrWhiteSpace(filterText)) + { + // There is no text filtering. Just apply user filters, sort alphabetically and return. + var listFiltered = originalList; + if (filters.Any(n => n.IsSelected)) + { + listFiltered = originalList.Where(n => ShouldBeInCompletionList(n, filters)); + } + var listSorted = listFiltered.OrderBy(n => n.SortText); + var listHighlighted = listSorted.Select(n => new CompletionItemWithHighlight(n)); + return new CompletionList(listHighlighted, 0, filters); + } + + // Pattern matcher not only filters, but also provides a way to order the results by their match quality. + // The relevant CompletionItem is match.Item1, its PatternMatch is match.Item2 + var patternMatcher = PatternMatcherFactory.CreatePatternMatcher( + filterText, + new PatternMatcherCreationOptions(System.Globalization.CultureInfo.CurrentCulture, PatternMatcherCreationFlags.IncludeMatchedSpans)); + + var matches = originalList + // Perform pattern matching + .Select(completionItem => (completionItem, patternMatcher.TryMatch(completionItem.FilterText))) + // Pick only items that were matched, unless length of filter text is 1 + .Where(n => (filterText.Length == 1 || n.Item2.HasValue)); + + // See which filters might be enabled based on the typed code + var textFilteredFilters = matches.SelectMany(n => n.Item1.Filters).Distinct(); + + // When no items are available for a given filter, it becomes unavailable + var updatedFilters = ImmutableArray.CreateRange(filters.Select(n => n.WithAvailability(textFilteredFilters.Contains(n.Filter)))); + + // Filter by user-selected filters. The value on availableFiltersWithSelectionState conveys whether the filter is selected. + var filterFilteredList = matches; + if (filters.Any(n => n.IsSelected)) + { + filterFilteredList = matches.Where(n => ShouldBeInCompletionList(n.Item1, filters)); + } + + // Order the list alphabetically and select the best match + var sortedList = filterFilteredList.OrderBy(n => n.Item1.SortText); + var bestMatch = filterFilteredList.OrderByDescending(n => n.Item2.HasValue).ThenBy(n => n.Item2).FirstOrDefault(); + var listWithHighlights = sortedList.Select(n => n.Item2.HasValue ? new CompletionItemWithHighlight(n.Item1, n.Item2.Value.MatchedSpans) : new CompletionItemWithHighlight(n.Item1)).ToImmutableArray(); + + int selectedItemIndex = 0; + for (int i = 0; i < listWithHighlights.Length; i++) + { + if (listWithHighlights[i].CompletionItem == bestMatch.Item1) + { + selectedItemIndex = i; + break; + } + } + + return new CompletionList(listWithHighlights, selectedItemIndex, updatedFilters); + } + + #region Filtering + + public static bool ShouldBeInCompletionList( + CompletionItem item, + ImmutableArray filtersWithState) + { + foreach (var filterWithState in filtersWithState.Where(n => n.IsSelected)) + { + if (item.Filters.Any(n => n == filterWithState.Filter)) + { + return true; + } + } + return false; + } + + #endregion + } + +#if DEBUG + [Export(typeof(IAsyncCompletionItemSource))] + [Name("Debug completion item source")] + [Order(After = "default")] + [ContentType("any")] + public class DebugCompletionItemSource : IAsyncCompletionItemSource + { + private static readonly ImageId Icon1 = new ImageId(new Guid("{ae27a6b0-e345-4288-96df-5eaf394ee369}"), 666); + private static readonly CompletionFilter Filter1 = new CompletionFilter("Diagnostic", "d", Icon1); + private static readonly ImageId Icon2 = new ImageId(new Guid("{ae27a6b0-e345-4288-96df-5eaf394ee369}"), 2852); + private static readonly CompletionFilter Filter2 = new CompletionFilter("Snippets", "s", Icon2); + private static readonly ImageId Icon3 = new ImageId(new Guid("{ae27a6b0-e345-4288-96df-5eaf394ee369}"), 473); + private static readonly CompletionFilter Filter3 = new CompletionFilter("Class", "c", Icon3); + private static readonly ImmutableArray FilterCollection1 = ImmutableArray.Create(Filter1); + private static readonly ImmutableArray FilterCollection2 = ImmutableArray.Create(Filter2); + private static readonly ImmutableArray FilterCollection3 = ImmutableArray.Create(Filter3); + private static readonly ImmutableArray commitCharacters = ImmutableArray.Create(" ", ";", "\t", ".", "<", "(", "["); + + void IAsyncCompletionItemSource.CustomCommit(Text.Editor.ITextView view, ITextBuffer buffer, CompletionItem item, ITrackingSpan applicableSpan, string commitCharacter) + { + throw new System.NotImplementedException(); + } + + async Task IAsyncCompletionItemSource.GetCompletionContextAsync(CompletionTrigger trigger, SnapshotPoint triggerLocation) + { + var charBeforeCaret = triggerLocation.Subtract(1).GetChar(); + SnapshotSpan applicableSpan; + if (commitCharacters.Contains(charBeforeCaret.ToString())) + { + // skip this character. the applicable span starts later + applicableSpan = new SnapshotSpan(triggerLocation, 0); + } + else + { + // include this character. the applicable span starts here + applicableSpan = new SnapshotSpan(triggerLocation - 1, 1); + } + return await Task.FromResult(new CompletionContext( + ImmutableArray.Create( + new CompletionItem("SampleItem<>", "SampleItem", "SampleItem<>", "SampleItem", this, FilterCollection1, false, Icon1), + new CompletionItem("AnotherItem🐱‍👤", "AnotherItem", "AnotherItem", "AnotherItem", this, FilterCollection1, false, Icon1), + new CompletionItem("Aaaaa", "Aaaaa", "Aaaaa", "Aaaaa", this, FilterCollection2, false, Icon2), + new CompletionItem("Bbbbb", "Bbbbb", "Bbbbb", "Bbbbb", this, FilterCollection2, false, Icon2), + new CompletionItem("Ccccc", "Ccccc", "Ccccc", "Ccccc", this, FilterCollection2, false, Icon2), + new CompletionItem("Ddddd", "Ddddd", "Ddddd", "Ddddd", this, FilterCollection2, false, Icon2), + new CompletionItem("Eeee", "Eeee", "Eeee", "Eeee", this, FilterCollection2, false, Icon2), + new CompletionItem("Ffffff", "Ffffff", "Ffffff", "Ffffff", this, FilterCollection2, false, Icon2), + new CompletionItem("Ggggggg", "Ggggggg", "Ggggggg", "Ggggggg", this, FilterCollection2, false, Icon2), + new CompletionItem("Hhhhh", "Hhhhh", "Hhhhh", "Hhhhh", this, FilterCollection2, false, Icon2), + new CompletionItem("Iiiii", "Iiiii", "Iiiii", "Iiiii", this, FilterCollection2, false, Icon2), + new CompletionItem("Jjjjj", "Jjjjj", "Jjjjj", "Jjjjj", this, FilterCollection3, false, Icon3), + new CompletionItem("kkkkk", "kkkkk", "kkkkk", "kkkkk", this, FilterCollection3, false, Icon3), + new CompletionItem("llllol", "llllol", "llllol", "llllol", this, FilterCollection3, false, Icon3), + new CompletionItem("mmmmm", "mmmmm", "mmmmm", "mmmmm", this, FilterCollection3, false, Icon3), + new CompletionItem("nnNnnn", "nnNnnn", "nnNnnn", "nnNnnn", this, FilterCollection3, false, Icon3), + new CompletionItem("oOoOOO", "oOoOOO", "oOoOOO", "oOoOOO", this, FilterCollection3, false, Icon3) + ), applicableSpan));//, true, true, "Suggestion mode description!")); + } + + async Task IAsyncCompletionItemSource.GetDescriptionAsync(CompletionItem item) + { + return await Task.FromResult("This is a tooltip for " + item.DisplayText); + } + + ImmutableArray IAsyncCompletionItemSource.GetPotentialCommitCharacters() => commitCharacters; + +#pragma warning disable CS1998 // Async method lacks 'await' operators and will run synchronously + async Task IAsyncCompletionItemSource.HandleViewClosedAsync(Text.Editor.ITextView view) +#pragma warning restore CS1998 // Async method lacks 'await' operators and will run synchronously + { + return; + } + + bool IAsyncCompletionItemSource.ShouldCommitCompletion(string typedChar, SnapshotPoint location) + { + return true; + } + + bool IAsyncCompletionItemSource.ShouldTriggerCompletion(string typedChar, SnapshotPoint location) + { + return true; + } + } + + [Export(typeof(IAsyncCompletionItemSource))] + [Name("Debug HTML completion item source")] + [Order(After = "default")] + [ContentType("RazorCSharp")] + public class DebugHtmlCompletionItemSource : IAsyncCompletionItemSource + { + void IAsyncCompletionItemSource.CustomCommit(Text.Editor.ITextView view, ITextBuffer buffer, CompletionItem item, ITrackingSpan applicableSpan, string commitCharacter) + { + throw new System.NotImplementedException(); + } + + async Task IAsyncCompletionItemSource.GetCompletionContextAsync(CompletionTrigger trigger, SnapshotPoint triggerLocation) + { + return await Task.FromResult(new CompletionContext(ImmutableArray.Create(new CompletionItem("html", this), new CompletionItem("head", this), new CompletionItem("body", this), new CompletionItem("header", this)), new SnapshotSpan(triggerLocation, 0))); + } + + async Task IAsyncCompletionItemSource.GetDescriptionAsync(CompletionItem item) + { + return await Task.FromResult(item.DisplayText); + } + + ImmutableArray IAsyncCompletionItemSource.GetPotentialCommitCharacters() + { + return ImmutableArray.Create(" ", ">", "=", "\t"); + } + +#pragma warning disable CS1998 // Async method lacks 'await' operators and will run synchronously + async Task IAsyncCompletionItemSource.HandleViewClosedAsync(Text.Editor.ITextView view) +#pragma warning restore CS1998 // Async method lacks 'await' operators and will run synchronously + { + return; + } + + bool IAsyncCompletionItemSource.ShouldCommitCompletion(string typedChar, SnapshotPoint location) + { + return true; + } + + bool IAsyncCompletionItemSource.ShouldTriggerCompletion(string typedChar, SnapshotPoint location) + { + return true; + } + } +#endif +} diff --git a/src/Language/Impl/Language/Completion/PrioritizedTaskScheduler.cs b/src/Language/Impl/Language/Completion/PrioritizedTaskScheduler.cs new file mode 100644 index 0000000..8dd5394 --- /dev/null +++ b/src/Language/Impl/Language/Completion/PrioritizedTaskScheduler.cs @@ -0,0 +1,65 @@ +using System.Collections.Concurrent; +using System.Collections.Generic; +using System.Diagnostics; +using System.Threading; +using System.Threading.Tasks; + +namespace Microsoft.VisualStudio.Language.Intellisense.Implementation +{ + /// + /// Clone of Roslyn's PrioritizedTaskScheduler + /// + internal class PrioritizedTaskScheduler : TaskScheduler + { + public static readonly TaskScheduler AboveNormalInstance = new PrioritizedTaskScheduler(ThreadPriority.AboveNormal); + + private readonly Thread _thread; + private readonly BlockingCollection _tasks = new BlockingCollection(); + + private PrioritizedTaskScheduler(ThreadPriority priority) + { + _thread = new Thread(ThreadStart) + { + Priority = priority, + IsBackground = true, + Name = this.GetType().Name + "-" + priority, + }; + + _thread.Start(); + } + + private void ThreadStart() + { + while (true) + { + var task = _tasks.Take(); + bool ret = this.TryExecuteTask(task); + Debug.Assert(ret); + } + } + + protected override void QueueTask(Task task) + { + _tasks.Add(task); + } + + // A class derived from TaskScheduler implements this function to support inline execution + // of a task on a thread that initiates a wait on that task object. + protected override bool TryExecuteTaskInline(Task task, bool taskWasPreviouslyQueued) + { + // NOTE(cyrusn): There is no race condition here. While our dedicated thread may try to + // call "TryExecuteTask" on this task above *and* we allow another "Wait"ing thread to + // execute it, the TPL ensures that only one will ever get a go. And, since we have no + // ordering guarantees (or other constraints) we're happy to let some other thread try + // to execute this task. It means less work for us, and it makes that other thread not + // be blocked. + return this.TryExecuteTask(task); + } + + protected override IEnumerable GetScheduledTasks() + { + // NOTE(cyrusn): This method is only for debugging purposes. + return _tasks.ToArray(); + } + } +} diff --git a/src/Language/Impl/Language/Completion/SelectDownCommandHandler.cs b/src/Language/Impl/Language/Completion/SelectDownCommandHandler.cs new file mode 100644 index 0000000..6d38a74 --- /dev/null +++ b/src/Language/Impl/Language/Completion/SelectDownCommandHandler.cs @@ -0,0 +1,40 @@ +using System.ComponentModel.Composition; +using Microsoft.VisualStudio.Commanding; +using Microsoft.VisualStudio.Language.Intellisense; +using Microsoft.VisualStudio.Text.Editor.Commanding.Commands; +using Microsoft.VisualStudio.Utilities; + +namespace Microsoft.VisualStudio.Language.Intellisense.Implementation +{ + /// + /// Reacts to the down arrow command and attempts to scroll the completion list. + /// + [Name(nameof(SelectDownCommandHandler))] + [ContentType("any")] + [Export(typeof(ICommandHandler))] + internal sealed class SelectDownCommandHandler : ICommandHandler + { + [Import] + IAsyncCompletionBroker broker; + + // TODO: Localize + string INamed.DisplayName => "Handler for down arrow in completion"; + + bool ICommandHandler.ExecuteCommand(DownKeyCommandArgs args, CommandExecutionContext executionContext) + { + if (broker.IsCompletionActive(args.TextView)) + { + broker.SelectDown(args.TextView); + return true; + } + return false; + } + + CommandState ICommandHandler.GetCommandState(DownKeyCommandArgs args) + { + return broker.IsCompletionActive(args.TextView) + ? CommandState.Available + : CommandState.Unspecified; + } + } +} diff --git a/src/Language/Impl/Language/Completion/SelectPageDownCommandHandler.cs b/src/Language/Impl/Language/Completion/SelectPageDownCommandHandler.cs new file mode 100644 index 0000000..c9b0cda --- /dev/null +++ b/src/Language/Impl/Language/Completion/SelectPageDownCommandHandler.cs @@ -0,0 +1,40 @@ +using System.ComponentModel.Composition; +using Microsoft.VisualStudio.Commanding; +using Microsoft.VisualStudio.Language.Intellisense; +using Microsoft.VisualStudio.Text.Editor.Commanding.Commands; +using Microsoft.VisualStudio.Utilities; + +namespace Microsoft.VisualStudio.Language.Intellisense.Implementation +{ + /// + /// Reacts to the page down command and attempts to scroll the completion list. + /// + [Name(nameof(SelectPageDownCommandHandler))] + [ContentType("any")] + [Export(typeof(ICommandHandler))] + internal sealed class SelectPageDownCommandHandler : ICommandHandler + { + [Import] + IAsyncCompletionBroker broker; + + // TODO: Localize + string INamed.DisplayName => "Handler for page down in completion"; + + bool ICommandHandler.ExecuteCommand(PageDownKeyCommandArgs args, CommandExecutionContext executionContext) + { + if (broker.IsCompletionActive(args.TextView)) + { + broker.SelectPageDown(args.TextView); + return true; + } + return false; + } + + CommandState ICommandHandler.GetCommandState(PageDownKeyCommandArgs args) + { + return broker.IsCompletionActive(args.TextView) + ? CommandState.Available + : CommandState.Unspecified; + } + } +} diff --git a/src/Language/Impl/Language/Completion/SelectPageUpCommandHandler.cs b/src/Language/Impl/Language/Completion/SelectPageUpCommandHandler.cs new file mode 100644 index 0000000..49af033 --- /dev/null +++ b/src/Language/Impl/Language/Completion/SelectPageUpCommandHandler.cs @@ -0,0 +1,40 @@ +using System.ComponentModel.Composition; +using Microsoft.VisualStudio.Commanding; +using Microsoft.VisualStudio.Language.Intellisense; +using Microsoft.VisualStudio.Text.Editor.Commanding.Commands; +using Microsoft.VisualStudio.Utilities; + +namespace Microsoft.VisualStudio.Language.Intellisense.Implementation +{ + /// + /// Reacts to the page up command and attempts to scroll the completion list. + /// + [Name(nameof(SelectPageUpCommandHandler))] + [ContentType("any")] + [Export(typeof(ICommandHandler))] + internal sealed class SelectPageUpCommandHandler : ICommandHandler + { + [Import] + IAsyncCompletionBroker broker; + + // TODO: Localize + string INamed.DisplayName => "Handler for page down in completion"; + + bool ICommandHandler.ExecuteCommand(PageUpKeyCommandArgs args, CommandExecutionContext executionContext) + { + if (broker.IsCompletionActive(args.TextView)) + { + broker.SelectPageUp(args.TextView); + return true; + } + return false; + } + + CommandState ICommandHandler.GetCommandState(PageUpKeyCommandArgs args) + { + return broker.IsCompletionActive(args.TextView) + ? CommandState.Available + : CommandState.Unspecified; + } + } +} diff --git a/src/Language/Impl/Language/Completion/SelectUpCommandHandler.cs b/src/Language/Impl/Language/Completion/SelectUpCommandHandler.cs new file mode 100644 index 0000000..d31e71e --- /dev/null +++ b/src/Language/Impl/Language/Completion/SelectUpCommandHandler.cs @@ -0,0 +1,40 @@ +using System.ComponentModel.Composition; +using Microsoft.VisualStudio.Commanding; +using Microsoft.VisualStudio.Language.Intellisense; +using Microsoft.VisualStudio.Text.Editor.Commanding.Commands; +using Microsoft.VisualStudio.Utilities; + +namespace Microsoft.VisualStudio.Language.Intellisense.Implementation +{ + /// + /// Reacts to the up arrow command and attempts to scroll the completion list. + /// + [Name(nameof(SelectUpCommandHandler))] + [ContentType("any")] + [Export(typeof(ICommandHandler))] + internal sealed class SelectUpCommandHandler : ICommandHandler + { + [Import] + IAsyncCompletionBroker broker; + + // TODO: Localize + string INamed.DisplayName => "Handler for down arrow in completion"; + + bool ICommandHandler.ExecuteCommand(UpKeyCommandArgs args, CommandExecutionContext executionContext) + { + if (broker.IsCompletionActive(args.TextView)) + { + broker.SelectUp(args.TextView); + return true; + } + return false; + } + + CommandState ICommandHandler.GetCommandState(UpKeyCommandArgs args) + { + return broker.IsCompletionActive(args.TextView) + ? CommandState.Available + : CommandState.Unspecified; + } + } +} diff --git a/src/Microsoft.VisualStudio.Text.Implementation.csproj b/src/Microsoft.VisualStudio.Text.Implementation.csproj index 7364610..c766baa 100644 --- a/src/Microsoft.VisualStudio.Text.Implementation.csproj +++ b/src/Microsoft.VisualStudio.Text.Implementation.csproj @@ -5,9 +5,10 @@ true key.snk false - 15.0.10-pre + 15.0.11-pre 15.0.0.0 15.8.173-preview-g3a2638b5fc + 15.6.289-preview-g5a23388e08 @@ -41,6 +42,11 @@ True Strings.resx + + True + True + Strings.resx + True True @@ -74,6 +80,11 @@ Strings.Designer.cs Microsoft.VisualStudio.Text.Implementation + + ResXFileCodeGenerator + Strings.Designer.cs + Microsoft.VisualStudio.Text.BraceCompletion.Implementation + ResXFileCodeGenerator Strings.Designer.cs @@ -114,6 +125,7 @@ + diff --git a/src/Microsoft.VisualStudio.Text.Implementation.nuspec b/src/Microsoft.VisualStudio.Text.Implementation.nuspec deleted file mode 100644 index 79b2c7d..0000000 --- a/src/Microsoft.VisualStudio.Text.Implementation.nuspec +++ /dev/null @@ -1,29 +0,0 @@ - - - - Microsoft.VisualStudio.Text.Implementation - 15.0.10-pre - Microsoft - Microsoft - false - https://github.com/Microsoft/vs-editor-api/blob/367d01a0b186f034178c5d5338c436e203eff8b4/LICENSE - https://github.com/Microsoft/vs-editor-api - Microsoft® Visual Studio® Editor Platform - © Microsoft Corporation. All rights reserved. - - - - - - - - - - - - - - - - - \ No newline at end of file diff --git a/src/Text/Def/Internal/TextLogic/ILoggingServiceInternal.cs b/src/Text/Def/Internal/TextLogic/ILoggingServiceInternal.cs new file mode 100644 index 0000000..e78084b --- /dev/null +++ b/src/Text/Def/Internal/TextLogic/ILoggingServiceInternal.cs @@ -0,0 +1,89 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain internal APIs that are subject to change without notice. +// Use at your own risk. +// + +using System.Collections.Generic; +using System; + +namespace Microsoft.VisualStudio.Text.Utilities +{ + /// + /// Allows code in src/Platform to log events. + /// + /// + /// For example, the VS Provider of this inserts data points into the telemetry data stream. + /// + public interface ILoggingServiceInternal + { + /// + /// Post the event named to the telemetry stream. Additional properties can be appended as name/value pairs in . + /// + void PostEvent(string key, params object[] namesAndProperties); + + /// + /// Post the event named to the telemetry stream. Additional properties can be appended as name/value pairs in . + /// + void PostEvent(string key, IReadOnlyList namesAndProperties); + + void PostEvent( + TelemetryEventType eventType, + string eventName, + TelemetryResult result = TelemetryResult.Success, + params (string name, object property)[] namesAndProperties); + + void PostEvent( + TelemetryEventType eventType, + string eventName, + TelemetryResult result, + IReadOnlyList<(string name, object property)> namesAndProperties); + + /// + /// Creates and posts a FaultEvent. + /// + /// + /// An event name following data model schema. + /// It requires that event name is a unique, not null or empty string. + /// It consists of 3 parts and must follows pattern [product]/[featureName]/[entityName]. FeatureName could be a one-level feature or feature hierarchy delimited by "/". + /// For examples, + /// vs/platform/opensolution; + /// vs/platform/editor/lightbulb/fixerror; + /// + /// Fault description + /// Exception instance + /// Additional information to be added to Watson's ErrorInformation.txt file. + /// + /// Gets or sets a value indicating whether we sample this event locally. Affects Watson only. + /// If false, will not send to Watson: only sends the telemetry event to AI and doesn't call callback. + /// Changing this will force the event to send to Watson. Be careful because it can have big perf impact. + /// If unchanged, it will be set according to the default sample rate. + /// + void PostFault( + string eventName, + string description, + Exception exceptionObject, + string additionalErrorInfo, + bool? isIncludedInWatsonSample); + + /// + /// Adjust the counter associated with and by . + /// + /// + /// Counters start at 0. + /// No information is sent over the wire until the is called. + /// + void AdjustCounter(string key, string name, int delta = 1); + + /// + /// Post all of the counters. + /// + /// + /// The counters are logged as if PostEvent had been called for each key with a list counter names and values. + /// The counters are cleared as a side-effect of this call. + /// + void PostCounters(); + } +} diff --git a/src/Text/Def/TextLogic/TextLogic.csproj b/src/Text/Def/TextLogic/TextLogic.csproj index 522d638..f7b3b78 100644 --- a/src/Text/Def/TextLogic/TextLogic.csproj +++ b/src/Text/Def/TextLogic/TextLogic.csproj @@ -15,7 +15,7 @@ - + diff --git a/src/Text/Impl/BraceCompletion/BraceCompletionAggregator.cs b/src/Text/Impl/BraceCompletion/BraceCompletionAggregator.cs new file mode 100644 index 0000000..fa25233 --- /dev/null +++ b/src/Text/Impl/BraceCompletion/BraceCompletionAggregator.cs @@ -0,0 +1,441 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + using Microsoft.VisualStudio.Text.Editor; + using Microsoft.VisualStudio.Utilities; + using System; + using System.Collections.Generic; + using System.Diagnostics; + using System.Linq; + + /// + /// This class combines IBraceCompletionSessionProvider, IBraceCompletionContextProvider, and IBraceCompletionDefaultProvider + /// session providers. The aggregator will create a session using the best match with the following priorities. + /// + /// 1. OpeningBrace + /// 2. ContentType + /// 3. Provider type: SessionProviders > ContextProviders > DefaultProviders + /// + internal sealed class BraceCompletionAggregator : IBraceCompletionAggregator + { + #region Private Members + + private BraceCompletionAggregatorFactory _factory; + private Dictionary> _contentTypeCache; + private Dictionary>> _providerCache; + + private string _openingBraces; + private string _closingBraces; + + #endregion + + #region Constructors + + public BraceCompletionAggregator(BraceCompletionAggregatorFactory factory) + { + _factory = factory; + + Init(); + } + + #endregion + + #region IBraceCompletionAggregator + + /// + /// Attempt to create a session using the provider that best matches the buffer content type for + /// the given opening brace. This is called only for appropriate buffers in the view's buffer graph. + /// + public bool TryCreateSession(ITextView textView, SnapshotPoint openingPoint, char openingBrace, out IBraceCompletionSession session) + { + ITextBuffer buffer = openingPoint.Snapshot.TextBuffer; + IContentType bufferContentType = buffer.ContentType; + + List contentTypes; + if (_contentTypeCache.TryGetValue(openingBrace, out contentTypes)) + { + foreach (IContentType providerContentType in contentTypes) + { + // find a matching content type + if (bufferContentType.IsOfType(providerContentType.TypeName)) + { + // try all providers for that type + List providersForBrace; + if (_providerCache[openingBrace].TryGetValue(providerContentType, out providersForBrace)) + { + foreach (ProviderHelper provider in providersForBrace) + { + IBraceCompletionSession curSession = null; + if (provider.TryCreate(_factory, textView, openingPoint, openingBrace, out curSession)) + { + session = curSession; + return true; + } + } + } + + // only try the best match + break; + } + } + } + + session = null; + return false; + } + + /// + /// Checks the content type against the providers. + /// + /// True if providers exist for the given content type. + public bool IsSupportedContentType(IContentType contentType, char openingBrace) + { + List contentTypes = null; + if (_contentTypeCache.TryGetValue(openingBrace, out contentTypes)) + { + // check if any types match + return contentTypes.Any(t => contentType.IsOfType(t.TypeName)); + } + + return false; + } + + /// + /// Gives a string containing all opening brace chars that have providers + /// + public string OpeningBraces + { + get + { + return _openingBraces; + } + } + + /// + /// Gives a string containing all closing brace chars that have providers + /// + public string ClosingBraces + { + get + { + return _closingBraces; + } + } + + #endregion + + #region Private Helpers + + private static char GetClosingBrace(IBraceCompletionMetadata metadata, char openingBrace) + { + IEnumerator opening = metadata.OpeningBraces.GetEnumerator(); + IEnumerator closing = metadata.ClosingBraces.GetEnumerator(); + + while (opening.MoveNext() && closing.MoveNext()) + { + if (opening.Current == openingBrace) + { + return closing.Current; + } + } + + // This should never happen since we find the metadata based on the opening char + Debug.Fail("Unable to find the given brace in the provider metadata"); + return ' '; + } + + // basic checks to avoid incorrect behavior such as char c = '\''' + private static bool AllowDefaultSession(SnapshotPoint openingPoint, char openingBrace, char closingBrace) + { + // avoid opening a new session next to the same char + if (openingBrace == closingBrace && openingPoint.Position > 0) + { + char prevChar = openingPoint.Subtract(1).GetChar(); + if (openingBrace.Equals(prevChar)) + { + return false; + } + } + + return true; + } + + /// + /// Build the _providerCache + /// Each opening brace is a key with a value of the providers and metadata in a + /// sorted list. The list is order from most specific to least specific content + /// types with the provider type sorted secondary. + /// + private void Init() + { + HashSet closing = new HashSet(); + _providerCache = new Dictionary>>(); + _contentTypeCache = new Dictionary>(); + + List providerHelpers = new List(); + providerHelpers.AddRange(_factory.SessionProviders.Select(p => new ProviderHelper(p))); + providerHelpers.AddRange(_factory.ContextProviders.Select(p => new ProviderHelper(p))); + providerHelpers.AddRange(_factory.DefaultProviders.Select(p => new ProviderHelper(p))); + + // build the cache + // opening brace -> content type -> provider + foreach (ProviderHelper providerHelper in providerHelpers) + { + foreach (char closeChar in providerHelper.Metadata.ClosingBraces) + { + closing.Add(closeChar); + } + + foreach (char openingBrace in providerHelper.Metadata.OpeningBraces) + { + // opening brace level + Dictionary> providersForBrace; + if (!_providerCache.TryGetValue(openingBrace, out providersForBrace)) + { + providersForBrace = new Dictionary>(); + _providerCache.Add(openingBrace, providersForBrace); + } + + // convert the type names into IContentTypes for the cache + foreach (IContentType contentType in providerHelper.Metadata.ContentTypes.Select((typeName) + => _factory.ContentTypeRegistryService.GetContentType(typeName)) + .Where((t) => t != null)) + { + // content type level + List curProviders; + if (!providersForBrace.TryGetValue(contentType, out curProviders)) + { + curProviders = new List(); + providersForBrace.Add(contentType, curProviders); + } + + curProviders.Add(providerHelper); + } + + Debug.Assert(providersForBrace != null && providersForBrace.Count > 0, "providersForBrace should not be empty"); + } + } + + _openingBraces = String.Join(String.Empty, _providerCache.Keys); + _closingBraces = String.Join(String.Empty, closing); + + // sort caches + foreach (KeyValuePair>> cache in _providerCache) + { + // sort the list of content types so the most specific ones are first + _contentTypeCache.Add(cache.Key, SortContentTypes(cache.Value.Keys.ToList())); + + Debug.Assert(!_contentTypeCache[cache.Key].Any(t => + _contentTypeCache[cache.Key].Where(tt => + tt.TypeName.Equals(t.TypeName, StringComparison.OrdinalIgnoreCase)).Count() != 1), + "duplicate content types"); + + // sort the providers by type + foreach (IContentType t in cache.Value.Keys) + { + cache.Value[t].Sort(); + } + } + } + + /// + /// Sorts content types by most specific to least specific. + /// This checks the type against all others until it finds one that it is + /// a type of. List.Sort() does not work here since most types are unrelated. + /// + private List SortContentTypes(List contentTypes) + { + List sorted = new List(contentTypes.Count); + + foreach (IContentType contentType in contentTypes) + { + int i; // sorted pos + bool added = false; + + for (i = 0; i < sorted.Count; i++) + { + if (contentType.IsOfType(sorted[i].TypeName)) + { + sorted.Insert(i, contentType); + added = true; + break; + } + } + + if (!added) + { + // the type was unrelated to all others, add it at the end + sorted.Add(contentType); + } + } + + return sorted; + } + + /// + /// A private helper class to wrap lazy instances of Session, Context, and Default providers into one type. + /// + private class ProviderHelper : IComparable + { + private Lazy _sessionPair; + private Lazy _contextPair; + private Lazy _defaultPair; + + public ProviderHelper(Lazy sessionPair) + { + _sessionPair = sessionPair; + } + + public ProviderHelper(Lazy contextPair) + { + _contextPair = contextPair; + } + + public ProviderHelper(Lazy defaultPair) + { + _defaultPair = defaultPair; + } + + public bool IsSession + { + get + { + return _sessionPair != null; + } + } + + public bool IsContext + { + get + { + return _contextPair != null; + } + } + + public bool IsDefault + { + get + { + return _defaultPair != null; + } + } + + public IBraceCompletionMetadata Metadata + { + get + { + if (IsSession) + { + return _sessionPair.Metadata; + } + + if (IsContext) + { + return _contextPair.Metadata; + } + + return _defaultPair.Metadata; + } + } + + // Create the session + public bool TryCreate(BraceCompletionAggregatorFactory factory, ITextView textView, SnapshotPoint openingPoint, char openingBrace, out IBraceCompletionSession session) + { + char closingBrace = GetClosingBrace(Metadata, openingBrace); + + if (IsSession) + { + bool created = false; + IBraceCompletionSession currentSession = null; + + factory.GuardedOperations.CallExtensionPoint(() => + { + created = _sessionPair.Value.TryCreateSession(textView, openingPoint, openingBrace, closingBrace, out currentSession); + }); + + if (created) + { + session = currentSession; + return true; + } + + session = null; + return false; + } + else if (IsContext) + { + // Get a language specific context and add it to a default session. + IBraceCompletionContext context = null; + + // check AllowDefaultSession to avoid starting a new "" session next to a " + if (AllowDefaultSession(openingPoint, openingBrace, closingBrace)) + { + bool created = false; + + factory.GuardedOperations.CallExtensionPoint(() => + { + created = _contextPair.Value.TryCreateContext(textView, openingPoint, openingBrace, closingBrace, out context); + }); + + if (created) + { + session = new BraceCompletionDefaultSession(textView, openingPoint.Snapshot.TextBuffer, openingPoint, openingBrace, + closingBrace, factory.UndoManager, factory.EditorOperationsFactoryService, context); + + return true; + } + } + + session = null; + return false; + } + else if (IsDefault) + { + // perform some basic checks on the buffer before going in + if (AllowDefaultSession(openingPoint, openingBrace, closingBrace)) + { + session = new BraceCompletionDefaultSession(textView, openingPoint.Snapshot.TextBuffer, openingPoint, openingBrace, + closingBrace, factory.UndoManager, factory.EditorOperationsFactoryService); + + return true; + } + } + + session = null; + return false; + } + + // Sort order: Session -> Context -> Default + public int CompareTo(ProviderHelper other) + { + if (IsSession && !other.IsSession) + { + return -1; + } + else if (other.IsSession) + { + return 1; + } + else if (IsContext && !other.IsContext) + { + return -1; + } + else if (other.IsContext) + { + return 1; + } + + // both providers are the same type + return 0; + } + } + + #endregion + } +} diff --git a/src/Text/Impl/BraceCompletion/BraceCompletionAggregatorFactory.cs b/src/Text/Impl/BraceCompletion/BraceCompletionAggregatorFactory.cs new file mode 100644 index 0000000..b2179b3 --- /dev/null +++ b/src/Text/Impl/BraceCompletion/BraceCompletionAggregatorFactory.cs @@ -0,0 +1,75 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + using Microsoft.VisualStudio.Text.Operations; + using Microsoft.VisualStudio.Text.Utilities; + using Microsoft.VisualStudio.Utilities; + using System; + using System.Collections.Generic; + using System.ComponentModel.Composition; + using System.Linq; + + [Export(typeof(IBraceCompletionAggregatorFactory))] + internal class BraceCompletionAggregatorFactory : IBraceCompletionAggregatorFactory + { + #region Internal Properties + + internal IEnumerable> SessionProviders { get; private set; } + internal IEnumerable> ContextProviders { get; private set; } + internal IEnumerable> DefaultProviders { get; private set; } + internal IContentTypeRegistryService ContentTypeRegistryService { get; private set; } + internal ITextBufferUndoManagerProvider UndoManager { get; private set; } + internal IEditorOperationsFactoryService EditorOperationsFactoryService { get; private set; } + internal GuardedOperations GuardedOperations { get; private set; } + + #endregion + + #region Constructors + + [ImportingConstructor] + public BraceCompletionAggregatorFactory( + [ImportMany(typeof(IBraceCompletionSessionProvider))]IEnumerable> sessionProviders, + [ImportMany(typeof(IBraceCompletionContextProvider))]IEnumerable> contextProviders, + [ImportMany(typeof(IBraceCompletionDefaultProvider))]IEnumerable> defaultProviders, + IContentTypeRegistryService contentTypeRegistryService, + ITextBufferUndoManagerProvider undoManager, + IEditorOperationsFactoryService editorOperationsFactoryService, + GuardedOperations guardedOperations) + { + SessionProviders = sessionProviders; + ContextProviders = contextProviders; + DefaultProviders = defaultProviders; + ContentTypeRegistryService = contentTypeRegistryService; + UndoManager = undoManager; + EditorOperationsFactoryService = editorOperationsFactoryService; + GuardedOperations = guardedOperations; + } + + #endregion + + #region IBraceCompletionAggregatorFactory + + public IBraceCompletionAggregator CreateAggregator() + { + return new BraceCompletionAggregator(this); + } + + public IEnumerable ContentTypes + { + get + { + return DefaultProviders.SelectMany(export => export.Metadata.ContentTypes) + .Concat(ContextProviders.SelectMany(export => export.Metadata.ContentTypes)) + .Concat(SessionProviders.SelectMany(export => export.Metadata.ContentTypes)); + } + } + + #endregion + } +} diff --git a/src/Text/Impl/BraceCompletion/BraceCompletionDefaultSession.cs b/src/Text/Impl/BraceCompletion/BraceCompletionDefaultSession.cs new file mode 100644 index 0000000..6877b4e --- /dev/null +++ b/src/Text/Impl/BraceCompletion/BraceCompletionDefaultSession.cs @@ -0,0 +1,430 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + using Microsoft.VisualStudio.Text; + using Microsoft.VisualStudio.Text.BraceCompletion; + using Microsoft.VisualStudio.Text.Editor; + using Microsoft.VisualStudio.Text.Operations; + using System.Diagnostics; + + /// + /// BraceCompletionDefaultSession is a language neutral brace completion session + /// capable of handling the default behaviors. Language specific behaviors + /// and formatting are handled by the optional IBraceCompletionContext. + /// + internal class BraceCompletionDefaultSession : IBraceCompletionSession + { + #region Private Members + + private char _openingBrace; + private char _closingBrace; + private ITrackingPoint _openingPoint; + private ITrackingPoint _closingPoint; + private ITextBuffer _subjectBuffer; + private ITextView _textView; + private IBraceCompletionContext _context; + private ITextBufferUndoManagerProvider _undoManager; + private ITextUndoHistory _undoHistory; + private IEditorOperations _editorOperations; + + #endregion + + #region Constructors + + /// + /// Default session with no context + /// + public BraceCompletionDefaultSession(ITextView textView, ITextBuffer subjectBuffer, + SnapshotPoint openingPoint, char openingBrace, char closingBrace, + ITextBufferUndoManagerProvider undoManager, IEditorOperationsFactoryService editorOperationsFactoryService) + : this(textView, subjectBuffer, openingPoint, openingBrace, closingBrace, undoManager, editorOperationsFactoryService, context: null) + { + + } + + /// + /// Default session with a language specific context + /// + public BraceCompletionDefaultSession(ITextView textView, ITextBuffer subjectBuffer, + SnapshotPoint openingPoint, char openingBrace, char closingBrace, ITextBufferUndoManagerProvider undoManager, + IEditorOperationsFactoryService editorOperationsFactoryService, IBraceCompletionContext context) + { + _textView = textView; + _subjectBuffer = subjectBuffer; + _openingBrace = openingBrace; + _closingBrace = closingBrace; + _closingPoint = SubjectBuffer.CurrentSnapshot.CreateTrackingPoint(openingPoint.Position, PointTrackingMode.Positive); + _context = context; + _undoManager = undoManager; + _undoHistory = undoManager.GetTextBufferUndoManager(_textView.TextBuffer).TextBufferUndoHistory; + _editorOperations = editorOperationsFactoryService.GetEditorOperations(_textView); + } + + #endregion + + #region IBraceCompletionSession Methods + + public void Start() + { + // this is where the caret should go after the change + SnapshotPoint pos = _textView.Caret.Position.BufferPosition; + ITrackingPoint beforeTrackingPoint = pos.Snapshot.CreateTrackingPoint(pos.Position, PointTrackingMode.Negative); + + ITextSnapshot snapshot = _subjectBuffer.CurrentSnapshot; + SnapshotPoint closingSnapshotPoint = _closingPoint.GetPoint(snapshot); + + if (closingSnapshotPoint.Position < 1) + { + Debug.Fail("The closing point was not found at the expected position."); + EndSession(); + return; + } + + SnapshotPoint openingSnapshotPoint = closingSnapshotPoint.Subtract(1); + + if (openingSnapshotPoint.GetChar() != OpeningBrace) + { + Debug.Fail("The opening brace was not found at the expected position."); + EndSession(); + return; + } + + _openingPoint = SubjectBuffer.CurrentSnapshot.CreateTrackingPoint(openingSnapshotPoint, PointTrackingMode.Positive); + + using (ITextUndoTransaction undo = CreateUndoTransaction()) + { + // insert the closing brace + using (ITextEdit edit = _subjectBuffer.CreateEdit()) + { + edit.Insert(closingSnapshotPoint, _closingBrace.ToString()); + + if (edit.HasFailedChanges) + { + Debug.Fail("Unable to insert closing brace"); + + // exit without setting the closing point which will take us off the stack + edit.Cancel(); + undo.Cancel(); + return; + } + else + { + snapshot = edit.Apply(); + } + } + + SnapshotPoint beforePoint = beforeTrackingPoint.GetPoint(_textView.TextSnapshot); + + // switch from positive to negative tracking so it stays against the closing brace + _closingPoint = SubjectBuffer.CurrentSnapshot.CreateTrackingPoint(_closingPoint.GetPoint(snapshot), PointTrackingMode.Negative); + + Debug.Assert(_closingPoint.GetPoint(snapshot).Position > 0 && (new SnapshotSpan(_closingPoint.GetPoint(snapshot).Subtract(1), 1)) + .GetText().Equals(_closingBrace.ToString()), "The closing point does not match the closing brace character"); + + // move the caret back between the braces + _textView.Caret.MoveTo(beforePoint); + + if (_context != null) + { + // allow the context to do extra formatting + _context.Start(this); + } + + undo.Complete(); + } + } + + public void PreBackspace(out bool handledCommand) + { + handledCommand = false; + + SnapshotPoint? caretPos = CaretPosition; + ITextSnapshot snapshot = SubjectBuffer.CurrentSnapshot; + + if (caretPos.HasValue && caretPos.Value.Position > 0 && (caretPos.Value.Position - 1) == _openingPoint.GetPoint(snapshot).Position + && !HasForwardTyping) + { + using (ITextUndoTransaction undo = CreateUndoTransaction()) + { + using (ITextEdit edit = SubjectBuffer.CreateEdit()) + { + SnapshotSpan span = new SnapshotSpan(_openingPoint.GetPoint(snapshot), _closingPoint.GetPoint(snapshot)); + + edit.Delete(span); + + if (edit.HasFailedChanges) + { + edit.Cancel(); + undo.Cancel(); + Debug.Fail("Unable to clear braces"); + // just let this backspace proceed normally + } + else + { + // handle the command so the backspace does + // not go through since we've already cleared the braces + handledCommand = true; + edit.Apply(); + undo.Complete(); + EndSession(); + } + } + } + } + } + + public void PostBackspace() + { + + } + + public void PreOverType(out bool handledCommand) + { + handledCommand = false; + + // AllowOverType may make changes to the buffer such as for completing intellisense + if (!HasForwardTyping && (_context == null || _context.AllowOverType(this))) + { + SnapshotPoint? caretPos = CaretPosition; + SnapshotPoint closingSnapshotPoint = _closingPoint.GetPoint(SubjectBuffer.CurrentSnapshot); + + Debug.Assert(caretPos.HasValue && caretPos.Value.Position < closingSnapshotPoint.Position); + + // ensure that we are within the session before clearing + if (caretPos.HasValue && caretPos.Value.Position < closingSnapshotPoint.Position && closingSnapshotPoint.Position > 0) + { + using (ITextUndoTransaction undo = CreateUndoTransaction()) + { + _editorOperations.AddBeforeTextBufferChangePrimitive(); + + SnapshotSpan span = new SnapshotSpan(caretPos.Value, closingSnapshotPoint.Subtract(1)); + + using (ITextEdit edit = _subjectBuffer.CreateEdit()) + { + edit.Delete(span); + + if (edit.HasFailedChanges) + { + Debug.Fail("Unable to clear closing brace"); + edit.Cancel(); + undo.Cancel(); + } + else + { + handledCommand = true; + + edit.Apply(); + + MoveCaretToClosingPoint(); + + _editorOperations.AddAfterTextBufferChangePrimitive(); + + undo.Complete(); + } + } + } + } + } + } + + public void PostOverType() + { + + } + + public void PreTab(out bool handledCommand) + { + handledCommand = false; + + if (!HasForwardTyping) + { + handledCommand = true; + + using (ITextUndoTransaction undo = CreateUndoTransaction()) + { + _editorOperations.AddBeforeTextBufferChangePrimitive(); + + MoveCaretToClosingPoint(); + + _editorOperations.AddAfterTextBufferChangePrimitive(); + + undo.Complete(); + } + } + } + + public void PreReturn(out bool handledCommand) + { + handledCommand = false; + } + + public void PostReturn() + { + if (_context != null && CaretPosition.HasValue) + { + SnapshotPoint closingSnapshotPoint = _closingPoint.GetPoint(SubjectBuffer.CurrentSnapshot); + + if (closingSnapshotPoint.Position > 0 && HasNoForwardTyping(CaretPosition.Value, closingSnapshotPoint.Subtract(1))) + { + _context.OnReturn(this); + } + } + } + + public void Finish() + { + if (_context != null) + { + _context.Finish(this); + } + } + + #endregion + + #region Unused IBraceCompletionSession Methods + + public void PostTab() { } + + public void PreDelete(out bool handledCommand) + { + handledCommand = false; + } + + public void PostDelete() { } + + #endregion + + #region IBraceCompletionSession Properties + + public ITextBuffer SubjectBuffer + { + get { return _subjectBuffer; } + } + + public ITextView TextView + { + get { return _textView; } + } + + public char ClosingBrace + { + get { return _closingBrace; } + } + + public ITrackingPoint ClosingPoint + { + get { return _closingPoint; } + } + + public char OpeningBrace + { + get { return _openingBrace; } + } + + public ITrackingPoint OpeningPoint + { + get { return _openingPoint; } + } + + #endregion + + #region Private Helpers + + private void EndSession() + { + // set the points to null to get off the stack + // the stack will determine that the current point + // is not contained within the session if either are null + _openingPoint = null; + _closingPoint = null; + } + + private SnapshotPoint? CaretPosition + { + get + { + return GetCaretPoint(SubjectBuffer); + } + } + + // get the caret position within the given buffer + private SnapshotPoint? GetCaretPoint(ITextBuffer buffer) + { + return _textView.Caret.Position.Point.GetPoint(buffer, PositionAffinity.Predecessor); + } + + // check if there any typing between the caret the closing point + private bool HasForwardTyping + { + get + { + SnapshotPoint closingSnapshotPoint = _closingPoint.GetPoint(SubjectBuffer.CurrentSnapshot); + + if (closingSnapshotPoint.Position > 0) + { + SnapshotPoint? caretPos = CaretPosition; + + if (caretPos.HasValue && !HasNoForwardTyping(caretPos.Value, closingSnapshotPoint.Subtract(1))) + { + return true; + } + } + + return false; + } + } + + // verify that there is only whitespace between the two given points + private static bool HasNoForwardTyping(SnapshotPoint caretPoint, SnapshotPoint endPoint) + { + Debug.Assert(caretPoint.Snapshot == endPoint.Snapshot, "snapshots do not match"); + + if (caretPoint.Snapshot == endPoint.Snapshot) + { + if (caretPoint == endPoint) + { + return true; + } + + if (caretPoint.Position < endPoint.Position) + { + SnapshotSpan span = new SnapshotSpan(caretPoint, endPoint); + + return string.IsNullOrWhiteSpace(span.GetText()); + } + } + + return false; + } + + private ITextUndoTransaction CreateUndoTransaction() + { + return _undoHistory.CreateTransaction(Strings.BraceCompletionUndo); + } + + + private void MoveCaretToClosingPoint() + { + SnapshotPoint closingSnapshotPoint = _closingPoint.GetPoint(SubjectBuffer.CurrentSnapshot); + + // find the position just after the closing brace in the view's text buffer + SnapshotPoint? afterBrace = _textView.BufferGraph.MapUpToBuffer(closingSnapshotPoint, + PointTrackingMode.Negative, PositionAffinity.Predecessor, _textView.TextBuffer); + + Debug.Assert(afterBrace.HasValue, "Unable to move caret to closing point"); + + if (afterBrace.HasValue) + { + _textView.Caret.MoveTo(afterBrace.Value); + } + } + + #endregion + } +} diff --git a/src/Text/Impl/BraceCompletion/BraceCompletionManager.cs b/src/Text/Impl/BraceCompletion/BraceCompletionManager.cs new file mode 100644 index 0000000..7cfe59c --- /dev/null +++ b/src/Text/Impl/BraceCompletion/BraceCompletionManager.cs @@ -0,0 +1,488 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + using Microsoft.VisualStudio.Text.Editor; + using Microsoft.VisualStudio.Text.Utilities; + using System; + using System.Diagnostics; + + /// + /// A per view manager for brace completion. This is called by the command filter in the + /// editor pkg. + /// + internal sealed class BraceCompletionManager : IBraceCompletionManager + { + #region Private Members + + private readonly IBraceCompletionStack _stack; + private readonly IBraceCompletionAggregatorFactory _sessionFactory; + private readonly IBraceCompletionAggregator _sessionAggregator; + private readonly ITextView _textView; + private readonly GuardedOperations _guardedOperations; + + private bool _braceCompletionEnabled; + + private IBraceCompletionSession _postSession; + private IBraceCompletionSession _waitingSession; + private SnapshotPoint? _waitingSessionOpeningPoint; + + #endregion + + #region Constructors + + internal BraceCompletionManager(ITextView textView, IBraceCompletionStack stack, IBraceCompletionAggregatorFactory sessionFactory, GuardedOperations guardedOperations) + { + _textView = textView; + _stack = stack; + _sessionFactory = sessionFactory; + _guardedOperations = guardedOperations; + _sessionAggregator = sessionFactory.CreateAggregator(); + + GetOptions(); + RegisterEvents(); + } + + #endregion + + #region IBraceCompletionManager + + public bool Enabled + { + get + { + return _braceCompletionEnabled; + } + } + + public string ClosingBraces + { + get + { + return _sessionAggregator.ClosingBraces; + } + } + + public bool HasActiveSessions + { + get { return _stack.TopSession != null; } + } + + public string OpeningBraces + { + get + { + return _sessionAggregator.OpeningBraces; + } + } + + public void PreTypeChar(char character, out bool handledCommand) + { + bool handled = false; + + bool hasSelection = HasSelection; + + Debug.Assert(_postSession == null, "_postSession should have been cleared"); + + // give the existing session a chance to handle the character first + + if (_stack.TopSession != null && !hasSelection) + { + IBraceCompletionSession session = _stack.TopSession; + + // check for an existing session first + _guardedOperations.CallExtensionPoint(() => + { + if (session.ClosingBrace.Equals(character) && IsCaretOnBuffer(session.SubjectBuffer)) + { + session.PreOverType(out handled); + + if (!handled) + { + _postSession = session; + } + } + }); + } + + handledCommand = handled; + + // otherwise check if this starts a new session + if (_postSession == null && !handled && Enabled && !hasSelection + && _sessionAggregator.OpeningBraces.IndexOf(character) > -1 && !HasForwardTypingOnLine) + { + SnapshotPoint? openingPoint = _textView.Caret.Position.Point.GetInsertionPoint((b => _sessionAggregator.IsSupportedContentType(b.ContentType, character))); + + if (openingPoint.HasValue) + { + IBraceCompletionSession session = null; + if (_sessionAggregator.TryCreateSession(_textView, openingPoint.Value, character, out session)) + { + // add the session after the current keystroke completes + _waitingSession = session; + _waitingSessionOpeningPoint = openingPoint; + } + } + } + } + + public void PostTypeChar(char character) + { + // check for any waiting sessions + if (_waitingSession != null) + { + // Verify the session is still valid before starting it + // and inserting the closing brace. + if (ValidateStart(_waitingSessionOpeningPoint, character)) + { + _stack.PushSession(_waitingSession); + } + + _waitingSession = null; + _waitingSessionOpeningPoint = null; + } + else if (_postSession != null) + { + _guardedOperations.CallExtensionPoint(() => + { + if (_postSession.ClosingBrace.Equals(character)) + { + _postSession.PostOverType(); + } + }); + + _postSession = null; + } + } + + public void PreTab(out bool handledCommand) + { + bool handled = false; + + Debug.Assert(_postSession == null, "_postSession should have been cleared"); + + // tab should only be handled by brace completion if there is no selection and both braces on the same line still + if (_stack.TopSession != null && !HasSelection) + { + IBraceCompletionSession session = _stack.TopSession; + + _guardedOperations.CallExtensionPoint(() => + { + if (IsSingleLine(session.OpeningPoint, session.ClosingPoint)) + { + session.PreTab(out handled); + + if (!handled) + { + _postSession = session; + } + } + }); + } + + handledCommand = handled; + } + + public void PostTab() + { + if (_postSession != null) + { + _guardedOperations.CallExtensionPoint(() => + { + _postSession.PostTab(); + }); + + _postSession = null; + } + } + + public void PreBackspace(out bool handledCommand) + { + bool handled = false; + + Debug.Assert(_postSession == null, "_postSession should have been cleared"); + + if (_stack.TopSession != null && !HasSelection) + { + IBraceCompletionSession session = _stack.TopSession; + + _guardedOperations.CallExtensionPoint(() => + { + if (session.OpeningPoint != null && session.ClosingPoint != null) + { + session.PreBackspace(out handled); + + if (!handled) + { + _postSession = session; + } + } + }); + } + + handledCommand = handled; + } + + public void PostBackspace() + { + if (_postSession != null) + { + _guardedOperations.CallExtensionPoint(() => + { + _postSession.PostBackspace(); + }); + + _postSession = null; + } + } + + public void PreDelete(out bool handledCommand) + { + bool handled = false; + + Debug.Assert(_postSession == null, "_postSession should have been cleared"); + + if (_stack.TopSession != null && !HasSelection) + { + IBraceCompletionSession session = _stack.TopSession; + + _guardedOperations.CallExtensionPoint(() => + { + if (session.OpeningPoint != null && session.ClosingPoint != null) + { + session.PreDelete(out handled); + + if (!handled) + { + _postSession = session; + } + } + }); + } + + handledCommand = handled; + } + + public void PostDelete() + { + if (_postSession != null) + { + _guardedOperations.CallExtensionPoint(() => + { + _postSession.PostDelete(); + }); + + _postSession = null; + } + } + + public void PreReturn(out bool handledCommand) + { + bool handled = false; + + Debug.Assert(_postSession == null, "_postSession should have been cleared"); + + if (_stack.TopSession != null && !HasSelection) + { + IBraceCompletionSession session = _stack.TopSession; + + _guardedOperations.CallExtensionPoint(() => + { + if (IsSingleLine(session.OpeningPoint, session.ClosingPoint)) + { + session.PreReturn(out handled); + + if (!handled) + { + _postSession = session; + } + } + }); + } + + handledCommand = handled; + } + + public void PostReturn() + { + if (_postSession != null) + { + _guardedOperations.CallExtensionPoint(() => + { + _postSession.PostReturn(); + }); + + _postSession = null; + } + } + + #endregion + + #region Events/Options + + private void RegisterEvents() + { + _textView.Closed += textView_Closed; + _textView.Options.OptionChanged += Options_OptionChanged; + } + + private void textView_Closed(object sender, EventArgs e) + { + UnregisterEvents(); + } + + private void UnregisterEvents() + { + _textView.Closed -= textView_Closed; + _textView.Options.OptionChanged -= Options_OptionChanged; + } + + private void Options_OptionChanged(object sender, EditorOptionChangedEventArgs e) + { + GetOptions(); + } + + private void GetOptions() + { + bool beforeEnabled = _braceCompletionEnabled; + + _braceCompletionEnabled = _textView.Options.GetOptionValue(DefaultTextViewOptions.BraceCompletionEnabledOptionId); + + // if completion was disabled, clear out the stack + if (beforeEnabled && !_braceCompletionEnabled) + { + _waitingSession = null; + _postSession = null; + _stack.Clear(); + } + } + + #endregion + + #region Private Helpers + + private bool IsCaretOnBuffer(ITextBuffer buffer) + { + return _textView.Caret.Position.Point.GetPoint(buffer, PositionAffinity.Successor).HasValue; + } + + private bool HasSelection + { + get + { + return !_textView.Selection.IsEmpty; + } + } + + // Determine if the line has text on it apart from any active braces in this view + private bool HasForwardTypingOnLine + { + get + { + SnapshotPoint start = _textView.Caret.Position.BufferPosition; + SnapshotPoint end = _textView.Caret.ContainingTextViewLine.End; + + if (start != end) + { + // if we have an active session use that brace as the end + if (_stack.TopSession != null) + { + ITrackingPoint closingPoint = null; + IBraceCompletionSession session = _stack.TopSession; + + _guardedOperations.CallExtensionPoint(() => + { + // only set these if they are on the same buffer + if (session.OpeningPoint != null && session.ClosingPoint != null + && session.OpeningPoint.TextBuffer == session.ClosingPoint.TextBuffer) + { + closingPoint = session.ClosingPoint; + } + }); + + if (closingPoint != null) + { + SnapshotPoint? innerBraceEnd = closingPoint.GetPoint(closingPoint.TextBuffer.CurrentSnapshot); + + if (innerBraceEnd.HasValue && _stack.TopSession.SubjectBuffer != _textView.TextBuffer) + { + // map the closing point to the text buffer for the check + innerBraceEnd = _textView.BufferGraph.MapUpToBuffer(innerBraceEnd.Value, + closingPoint.TrackingMode, PositionAffinity.Predecessor, _textView.TextBuffer); + } + + if (innerBraceEnd.HasValue && innerBraceEnd.Value.Position <= end && innerBraceEnd.Value.Position > 0) + { + end = innerBraceEnd.Value.Subtract(1); + } + } + } + + // check if we aren't the last closing brace + if (start == end) + { + return false; + } + else if (start < end) + { + SnapshotSpan span = new SnapshotSpan(start, end); + + if (!span.IsEmpty) + { + return !string.IsNullOrWhiteSpace(span.GetText()); + } + } + else + { + Debug.Fail("unable to check for forward typing"); + // shouldn't happen, but if it does count it as forward typing to avoid + // further action + return true; + } + } + + return false; + } + } + + private bool IsSingleLine(ITrackingPoint openingPoint, ITrackingPoint closingPoint) + { + if (openingPoint != null && closingPoint != null) + { + ITextSnapshot snapshot = openingPoint.TextBuffer.CurrentSnapshot; + + return openingPoint.GetPoint(snapshot).GetContainingLine().End.Position >= closingPoint.GetPoint(snapshot).Position; + } + + return false; + } + + // Verify that we are about to insert the closing brace right after the opening one + private bool ValidateStart(SnapshotPoint? openingPoint, char openingChar) + { + if (openingPoint.HasValue) + { + ITextBuffer subjectBuffer = openingPoint.Value.Snapshot.TextBuffer; + + // Get the position based on the predecessor which should be the opening brace + SnapshotPoint? caretPosition = _textView.Caret.Position.Point.GetPoint(subjectBuffer, PositionAffinity.Predecessor); + + // verify that the opening brace is right behind the caret + if (caretPosition.HasValue && caretPosition.Value.Position > 0) + { + SnapshotPoint openingBrace = caretPosition.Value.Subtract(1); + return (openingBrace.GetChar() == openingChar); + } + } + + return false; + } + + #endregion + } +} diff --git a/src/Text/Impl/BraceCompletion/BraceCompletionStack.cs b/src/Text/Impl/BraceCompletion/BraceCompletionStack.cs new file mode 100644 index 0000000..311d493 --- /dev/null +++ b/src/Text/Impl/BraceCompletion/BraceCompletionStack.cs @@ -0,0 +1,335 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + using Microsoft.VisualStudio.Text; + using Microsoft.VisualStudio.Text.BraceCompletion; + using Microsoft.VisualStudio.Text.Editor; + using Microsoft.VisualStudio.Text.Utilities; + using System; + using System.Collections.Generic; + using System.Collections.ObjectModel; + + /// + /// Represents the stack of active brace completion sessions. + /// The stack handles removing sessions no longer in focus as + /// well as marking the inner most closing brace with the + /// adornment. + /// + internal class BraceCompletionStack : IBraceCompletionStack + { + #region Private Members + private Stack _stack; + + private ITextView _textView; + private ITextBuffer _currentSubjectBuffer; + + private IBraceCompletionAdornmentServiceFactory _adornmentServiceFactory; + private IBraceCompletionAdornmentService _adornmentService; + private GuardedOperations _guardedOperations; + #endregion + + #region Constructors + public BraceCompletionStack(ITextView textView, IBraceCompletionAdornmentServiceFactory adornmentFactory, GuardedOperations guardedOperations) + { + _adornmentServiceFactory = adornmentFactory; + _stack = new Stack(); + + _textView = textView; + _guardedOperations = guardedOperations; + + RegisterEvents(); + } + #endregion + + #region IBraceCompletionStack + public IBraceCompletionSession TopSession + { + get + { + return (_stack.Count > 0 ? _stack.Peek() : null); + } + } + + public void PushSession(IBraceCompletionSession session) + { + ITextView view = null; + ITextBuffer buffer = null; + + _guardedOperations.CallExtensionPoint(() => + { + view = session.TextView; + buffer = session.SubjectBuffer; + }); + + if (view != null && buffer != null) + { + SetCurrentBuffer(buffer); + bool validStart = false; + + // start the session to add the closing brace + _guardedOperations.CallExtensionPoint(() => + { + session.Start(); + + // verify the session is valid before going on. + // some sessions may want to leave the stack at this point + validStart = (session.OpeningPoint != null && session.ClosingPoint != null); + }); + + if (validStart) + { + // highlight the brace + ITrackingPoint closingPoint = null; + _guardedOperations.CallExtensionPoint(() => + { + closingPoint = session.ClosingPoint; + }); + + HighlightSpan(closingPoint); + + // put it on the stack for tracking + _stack.Push(session); + } + } + } + + public ReadOnlyObservableCollection Sessions + { + get + { + return new ReadOnlyObservableCollection(new ObservableCollection(_stack)); + } + } + + public void RemoveOutOfRangeSessions(SnapshotPoint point) + { + bool updateHighlightSpan = false; + + while (_stack.Count > 0 && !Contains(TopSession, point)) + { + updateHighlightSpan = true; + + // remove the session and call Finish + PopSession(); + } + + if (updateHighlightSpan) + { + HighlightSpan(TopSession != null ? TopSession.ClosingPoint : null); + } + } + + public void Clear() + { + while (_stack.Count > 0) + { + PopSession(); + } + + SetCurrentBuffer(null); + HighlightSpan(null); + } + + #endregion + + #region Events + + private void RegisterEvents() + { + if (_adornmentServiceFactory != null) + { + _adornmentService = _adornmentServiceFactory.GetOrCreateService(_textView); + } + + _textView.Caret.PositionChanged += Caret_PositionChanged; + _textView.Closed += TextView_Closed; + } + + private void UnregisterEvents() + { + _textView.Caret.PositionChanged -= Caret_PositionChanged; + _textView.Closed -= TextView_Closed; + + // unhook subject buffer + SetCurrentBuffer(null); + + _textView = null; + } + + public void ConnectSubjectBuffer(ITextBuffer subjectBuffer) + { + subjectBuffer.PostChanged += SubjectBuffer_PostChanged; + } + + public void DisconnectSubjectBuffer(ITextBuffer subjectBuffer) + { + subjectBuffer.PostChanged -= SubjectBuffer_PostChanged; + } + + private void TextView_Closed(object sender, EventArgs e) + { + UnregisterEvents(); + } + + // Remove any sessions that no longer contain the caret + private void Caret_PositionChanged(object sender, CaretPositionChangedEventArgs e) + { + if (_stack.Count > 0) + { + // use the new position if possible, otherwise map to the subject buffer + if (_currentSubjectBuffer != null && e.TextView.TextBuffer != _currentSubjectBuffer) + { + SnapshotPoint? newPosition = e.NewPosition.Point.GetPoint(_currentSubjectBuffer, PositionAffinity.Successor); + + if (newPosition.HasValue) + { + RemoveOutOfRangeSessions(newPosition.Value); + } + else + { + // caret is no longer in the subject buffer. probably + // moved to different buffer in the same view. + // clear all tracks + _stack.Clear(); + } + } + else + { + RemoveOutOfRangeSessions(e.NewPosition.BufferPosition); + } + } + } + + // Verify that the top most session is still valid after a buffer change + // This handles any issues that could result from text being replaced + // or multi view scenarios where the caret is not being moved in the + // current view. + private void SubjectBuffer_PostChanged(object sender, EventArgs e) + { + bool updateHighlightSpan = false; + + // only check the top most session + // outer sessions could become invalid while the inner most + // sessions stay valid, but there is no reason to check them every time + while (_stack.Count > 0 && !IsSessionValid(TopSession)) + { + updateHighlightSpan = true; + _stack.Pop().Finish(); + } + + if (updateHighlightSpan) + { + ITrackingPoint closingPoint = null; + + if (TopSession != null) + { + _guardedOperations.CallExtensionPoint(() => closingPoint = TopSession.ClosingPoint); + } + + HighlightSpan(closingPoint); + } + } + + private bool IsSessionValid(IBraceCompletionSession session) + { + bool isValid = false; + + _guardedOperations.CallExtensionPoint(() => + { + if (session.ClosingPoint != null && session.OpeningPoint != null && session.SubjectBuffer != null) + { + ITextSnapshot snapshot = session.SubjectBuffer.CurrentSnapshot; + SnapshotPoint closingSnapshotPoint = session.ClosingPoint.GetPoint(snapshot); + SnapshotPoint openingSnapshotPoint = session.OpeningPoint.GetPoint(snapshot); + + // Verify that the closing and opening points still match the expected braces + isValid = closingSnapshotPoint.Position > 1 + && openingSnapshotPoint.Position <= (closingSnapshotPoint.Position - 2) + && openingSnapshotPoint.GetChar() == session.OpeningBrace + && closingSnapshotPoint.Subtract(1).GetChar() == session.ClosingBrace; + } + }); + + return isValid; + } + + #endregion + + #region Private Helpers + + private void SetCurrentBuffer(ITextBuffer buffer) + { + // Connect to the subject buffer of the session + if (_currentSubjectBuffer != buffer) + { + if (_currentSubjectBuffer != null) + { + DisconnectSubjectBuffer(_currentSubjectBuffer); + } + + _currentSubjectBuffer = buffer; + + if (_currentSubjectBuffer != null) + { + ConnectSubjectBuffer(_currentSubjectBuffer); + } + } + } + + private void PopSession() + { + IBraceCompletionSession session = _stack.Pop(); + ITextBuffer nextSubjectBuffer = null; + + _guardedOperations.CallExtensionPoint(() => + { + // call finish to allow the session to do any cleanup + session.Finish(); + + if (TopSession != null) + { + nextSubjectBuffer = TopSession.SubjectBuffer; + } + }); + + SetCurrentBuffer(nextSubjectBuffer); + } + + private void HighlightSpan(ITrackingPoint point) + { + if (_adornmentService != null) + { + _adornmentService.Point = point; + } + } + + private bool Contains(IBraceCompletionSession session, SnapshotPoint point) + { + bool contains = false; + + _guardedOperations.CallExtensionPoint(() => + { + // remove any sessions with nulls, if they decide they need to get off the stack + // they can do it this way. + if (session.OpeningPoint != null && session.ClosingPoint != null + && session.OpeningPoint.TextBuffer == session.ClosingPoint.TextBuffer + && point.Snapshot.TextBuffer == session.OpeningPoint.TextBuffer) + { + ITextSnapshot snapshot = point.Snapshot; + + contains = session.OpeningPoint.GetPosition(snapshot) < point.Position + && session.ClosingPoint.GetPosition(snapshot) > point.Position; + } + }); + + return contains; + } + #endregion + } +} diff --git a/src/Text/Impl/BraceCompletion/IBraceCompletionAdornmentService.cs b/src/Text/Impl/BraceCompletion/IBraceCompletionAdornmentService.cs new file mode 100644 index 0000000..dbbbe4f --- /dev/null +++ b/src/Text/Impl/BraceCompletion/IBraceCompletionAdornmentService.cs @@ -0,0 +1,22 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + using System; + + internal interface IBraceCompletionAdornmentService + { + /// + /// Gets or sets the tracking point used by the brace completion adornment + /// to indicate the closing brace. The adornment span is length one + /// with the given point as the end. + /// + /// Setting the tracking point to null clears the adornment. + ITrackingPoint Point { get; set; } + } +} diff --git a/src/Text/Impl/BraceCompletion/IBraceCompletionAdornmentServiceFactory.cs b/src/Text/Impl/BraceCompletion/IBraceCompletionAdornmentServiceFactory.cs new file mode 100644 index 0000000..2bc8f4f --- /dev/null +++ b/src/Text/Impl/BraceCompletion/IBraceCompletionAdornmentServiceFactory.cs @@ -0,0 +1,20 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + using Microsoft.VisualStudio.Text.Editor; + + internal interface IBraceCompletionAdornmentServiceFactory + { + /// + /// Creates an IBraceCompletionAdornmentService for the given text view. + /// + /// Only one IBraceCompletionAdornmentService will exist per view. + IBraceCompletionAdornmentService GetOrCreateService(ITextView textView); + } +} diff --git a/src/Text/Impl/BraceCompletion/IBraceCompletionAggregator.cs b/src/Text/Impl/BraceCompletion/IBraceCompletionAggregator.cs new file mode 100644 index 0000000..2fd2f6e --- /dev/null +++ b/src/Text/Impl/BraceCompletion/IBraceCompletionAggregator.cs @@ -0,0 +1,43 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + using Microsoft.VisualStudio.Text.Editor; + using Microsoft.VisualStudio.Utilities; + + internal interface IBraceCompletionAggregator + { + /// + /// A unique list of all opening braces that have providers. + /// + string OpeningBraces { get; } + + /// + /// A unique list of all closing braces that have providers + /// + string ClosingBraces { get; } + + /// + /// Checks if a provider exists for the content type and opening brace. + /// + /// buffer content type + /// opening brace character + /// True if there is a matching provider + bool IsSupportedContentType(IContentType contentType, char openingBrace); + + /// + /// Creates a session using the best provider for the buffer content type and opening brace. + /// + /// current text view + /// current caret point + /// opening brace chraracter + /// Session created by the provider. + /// True if the provider created a session. + bool TryCreateSession(ITextView textView, SnapshotPoint openingPoint, char openingBrace, out IBraceCompletionSession session); + } +} diff --git a/src/Text/Impl/BraceCompletion/IBraceCompletionAggregatorFactory.cs b/src/Text/Impl/BraceCompletion/IBraceCompletionAggregatorFactory.cs new file mode 100644 index 0000000..50bc7d2 --- /dev/null +++ b/src/Text/Impl/BraceCompletion/IBraceCompletionAggregatorFactory.cs @@ -0,0 +1,28 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +using Microsoft.VisualStudio.Text.Operations; +using Microsoft.VisualStudio.Utilities; +using System; +using System.Collections.Generic; +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + internal interface IBraceCompletionAggregatorFactory + { + /// + /// Creates a brace completion aggregator to simplify + /// creating a session that best matches the buffer + /// content type. + /// + IBraceCompletionAggregator CreateAggregator(); + + /// + /// Gives an IEnumerable of all content types with providers. + /// + IEnumerable ContentTypes { get; } + } +} diff --git a/src/Text/Impl/BraceCompletion/IBraceCompletionMetadata.cs b/src/Text/Impl/BraceCompletion/IBraceCompletionMetadata.cs new file mode 100644 index 0000000..07fe487 --- /dev/null +++ b/src/Text/Impl/BraceCompletion/IBraceCompletionMetadata.cs @@ -0,0 +1,32 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + using System.Collections.Generic; + + /// + /// Metadata for IBraceCompletionSessionProvider exports + /// + public interface IBraceCompletionMetadata + { + /// + /// List of opening tokens. + /// + IEnumerable OpeningBraces { get; } + + /// + /// List of closing tokens. + /// + IEnumerable ClosingBraces { get; } + + /// + /// Supported content types. + /// + IEnumerable ContentTypes { get; } + } +} diff --git a/src/Text/Impl/BraceCompletion/IBraceCompletionStack.cs b/src/Text/Impl/BraceCompletion/IBraceCompletionStack.cs new file mode 100644 index 0000000..2135df5 --- /dev/null +++ b/src/Text/Impl/BraceCompletion/IBraceCompletionStack.cs @@ -0,0 +1,42 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + using Microsoft.VisualStudio.Text; + using Microsoft.VisualStudio.Text.BraceCompletion; + using System.Collections.ObjectModel; + + internal interface IBraceCompletionStack + { + /// + /// Gets the top most session in the stack. + /// + IBraceCompletionSession TopSession { get; } + + /// + /// Adds a session to the top of the stack. + /// + void PushSession(IBraceCompletionSession session); + + /// + /// Gets the list of sessions in the stack, ordered from bottom to top. + /// + ReadOnlyObservableCollection Sessions { get; } + + /// + /// Remove all sessions which do not contain the given point. + /// + /// current caret point + void RemoveOutOfRangeSessions(SnapshotPoint point); + + /// + /// Remove all sessions from the stack. + /// + void Clear(); + } +} diff --git a/src/Text/Impl/BraceCompletion/PlainTextDefaults.cs b/src/Text/Impl/BraceCompletion/PlainTextDefaults.cs new file mode 100644 index 0000000..c930208 --- /dev/null +++ b/src/Text/Impl/BraceCompletion/PlainTextDefaults.cs @@ -0,0 +1,26 @@ +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// Licensed under the MIT License. See License.txt in the project root for license information. +// +// This file contain implementations details that are subject to change without notice. +// Use at your own risk. +// +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation +{ + using Microsoft.VisualStudio.Utilities; + using System.ComponentModel.Composition; + + /// + /// Sets the default braces to auto complete on plain text files + /// + [Export(typeof(IBraceCompletionDefaultProvider))] + [BracePair('(', ')')] + [BracePair('"', '"')] + [BracePair('{', '}')] + [BracePair('[', ']')] + [ContentType("plaintext")] + internal sealed class PlainTextDefaults : IBraceCompletionDefaultProvider + { + + } +} diff --git a/src/Text/Impl/BraceCompletion/Strings.Designer.cs b/src/Text/Impl/BraceCompletion/Strings.Designer.cs new file mode 100644 index 0000000..f22f533 --- /dev/null +++ b/src/Text/Impl/BraceCompletion/Strings.Designer.cs @@ -0,0 +1,81 @@ +//------------------------------------------------------------------------------ +// +// This code was generated by a tool. +// Runtime Version:4.0.30319.17634 +// +// Changes to this file may cause incorrect behavior and will be lost if +// the code is regenerated. +// +//------------------------------------------------------------------------------ + +namespace Microsoft.VisualStudio.Text.BraceCompletion.Implementation { + using System; + + + /// + /// A strongly-typed resource class, for looking up localized strings, etc. + /// + // This class was auto-generated by the StronglyTypedResourceBuilder + // class via a tool like ResGen or Visual Studio. + // To add or remove a member, edit your .ResX file then rerun ResGen + // with the /str option, or rebuild your VS project. + [global::System.CodeDom.Compiler.GeneratedCodeAttribute("System.Resources.Tools.StronglyTypedResourceBuilder", "4.0.0.0")] + [global::System.Diagnostics.DebuggerNonUserCodeAttribute()] + [global::System.Runtime.CompilerServices.CompilerGeneratedAttribute()] + internal class Strings { + + private static global::System.Resources.ResourceManager resourceMan; + + private static global::System.Globalization.CultureInfo resourceCulture; + + [global::System.Diagnostics.CodeAnalysis.SuppressMessageAttribute("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")] + internal Strings() { + } + + /// + /// Returns the cached ResourceManager instance used by this class. + /// + [global::System.ComponentModel.EditorBrowsableAttribute(global::System.ComponentModel.EditorBrowsableState.Advanced)] + internal static global::System.Resources.ResourceManager ResourceManager { + get { + if (object.ReferenceEquals(resourceMan, null)) { + global::System.Resources.ResourceManager temp = new global::System.Resources.ResourceManager("Microsoft.VisualStudio.Text.BraceCompletion.Implementation.Strings", typeof(Strings).Assembly); + resourceMan = temp; + } + return resourceMan; + } + } + + /// + /// Overrides the current thread's CurrentUICulture property for all + /// resource lookups using this strongly typed resource class. + /// + [global::System.ComponentModel.EditorBrowsableAttribute(global::System.ComponentModel.EditorBrowsableState.Advanced)] + internal static global::System.Globalization.CultureInfo Culture { + get { + return resourceCulture; + } + set { + resourceCulture = value; + } + } + + /// + /// Looks up a localized string similar to Brace completion undo. + /// + internal static string BraceCompletionUndo { + get { + return ResourceManager.GetString("BraceCompletionUndo", resourceCulture); + } + } + + /// + /// Looks up a localized string similar to Auto Completed Brace. + /// + internal static string ClosingBraceColorDefinitionName { + get { + return ResourceManager.GetString("ClosingBraceColorDefinitionName", resourceCulture); + } + } + } +} diff --git a/src/Text/Impl/BraceCompletion/Strings.resx b/src/Text/Impl/BraceCompletion/Strings.resx new file mode 100644 index 0000000..94bf832 --- /dev/null +++ b/src/Text/Impl/BraceCompletion/Strings.resx @@ -0,0 +1,126 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + text/microsoft-resx + + + 2.0 + + + System.Resources.ResXResourceReader, System.Windows.Forms, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089 + + + System.Resources.ResXResourceWriter, System.Windows.Forms, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089 + + + Brace completion undo + + + Auto Completed Brace + + \ No newline at end of file diff --git a/src/Text/Impl/PatternMatching/AllLowerCamelCaseMatcher.cs b/src/Text/Impl/PatternMatching/AllLowerCamelCaseMatcher.cs new file mode 100644 index 0000000..adfacc8 --- /dev/null +++ b/src/Text/Impl/PatternMatching/AllLowerCamelCaseMatcher.cs @@ -0,0 +1,263 @@ +// 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.Generic; +using System.Collections.Immutable; +using Microsoft.VisualStudio.Text; +using Microsoft.VisualStudio.Text.Utilities; +using TextSpan = Microsoft.VisualStudio.Text.Span; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + internal partial class PatternMatcher + { + /// + /// Encapsulated matches responsible for matching an all lowercase pattern against + /// a candidate using CamelCase matching. i.e. this code is responsible for finding the + /// match between "cofipro" and "CodeFixProvider". + /// + private struct AllLowerCamelCaseMatcher + { + private readonly bool _includeMatchedSpans; + private readonly string _candidate; + private readonly StringBreaks _candidateHumps; + private readonly TextChunk _patternChunk; + private readonly string _patternText; + + public AllLowerCamelCaseMatcher(bool includeMatchedSpans, string candidate, StringBreaks candidateHumps, TextChunk patternChunk) + { + _includeMatchedSpans = includeMatchedSpans; + _candidate = candidate; + _candidateHumps = candidateHumps; + _patternChunk = patternChunk; + _patternText = _patternChunk.Text; + } + + /// + /// Returns null if no match was found, 1 if a contiguous match was found, 2 if a + /// match as found that starts at the beginning of the candidate, and 3 if a contiguous + /// match was found that starts at the beginning of the candidate. + /// + /// If this is a container match, we might be looking at a chunk that is actually offset in the original string. Add chunkOffset to the start of any span created. + public PatternMatchKind? TryMatch(int chunkOffset, out ImmutableArray matchedSpans) + { + // We have something like cofipro and we want to match CodeFixProvider. + // + // Note that this is incredibly ambiguous. We'd also want this to match + // CorporateOfficePartsRoom So, for example, if we were to consume the "co" + // as matching "Corporate", then "f" wouldn't match any camel hump. So we + // basically have to branch out and try all options at every character + // in the pattern chunk. + + var result = TryMatch( + patternIndex: 0, candidateHumpIndex: 0, contiguous: null, chunkOffset: chunkOffset); + + if (result == null) + { + matchedSpans = ImmutableArray.Empty; + return null; + } + + matchedSpans = _includeMatchedSpans && result.Value.MatchedSpansInReverse != null + ? new NormalizedSpanCollection(result.Value.MatchedSpansInReverse).ToImmutableArray() + : ImmutableArray.Empty; + + result?.Free(); + return GetKind(result.Value); + } + + private PatternMatchKind GetKind(CamelCaseResult result) + => PatternMatcher.GetCamelCaseKind(result, _candidateHumps); + + private CamelCaseResult? TryMatch( + int patternIndex, int candidateHumpIndex, bool? contiguous, int chunkOffset) + { + if (patternIndex == _patternText.Length) + { + // We hit the end. So we were able to match against this candidate. + // We are contiguous if our contiguous tracker was not set to false. + var matchedSpansInReverse = _includeMatchedSpans ? ArrayBuilder.GetInstance() : null; + return new CamelCaseResult( + fromStart: false, + contiguous: contiguous != false, + toEnd: false, + matchCount: 0, + matchedSpansInReverse: matchedSpansInReverse, + chunkOffset: chunkOffset); + } + + var bestResult = default(CamelCaseResult?); + + // Look for a hump in the candidate that matches the current letter we're on. + var patternCharacter = _patternText[patternIndex]; + for (int humpIndex = candidateHumpIndex, n = _candidateHumps.GetCount(); humpIndex < n; humpIndex++) + { + // If we've been contiguous, but we jumped past a hump, then we're no longer contiguous. + if (contiguous.HasValue && contiguous.Value) + { + contiguous = humpIndex == candidateHumpIndex; + } + + var candidateHump = _candidateHumps[humpIndex]; + if (char.ToLower(_candidate[candidateHump.Start]) == patternCharacter) + { + // Found a hump in the candidate string that matches the current pattern + // character we're on. i.e. we matched the c in cofipro against the C in + // CodeFixProvider. + // + // Now, for each subsequent character, we need to both try to consume it + // as part of the current hump, or see if it should match the next hump. + // + // Note, if the candidate is something like CodeFixProvider and our pattern + // is cofipro, and we've matched the 'f' against the 'F', then the max of + // the pattern we'll want to consume is "fip" against "Fix". We don't want + // consume parts of the pattern once we reach the next hump. + + // We matched something. If this was our first match, consider ourselves + // contiguous. + var localContiguous = contiguous == null ? true : contiguous.Value; + + var result = TryConsumePatternOrMatchNextHump( + patternIndex, humpIndex, localContiguous, chunkOffset); + + if (result == null) + { + continue; + } + + if (UpdateBestResultIfBetter(result.Value, ref bestResult, matchSpanToAdd: null)) + { + // We found the best result so far. We can stop immediately. + break; + } + } + } + + return bestResult; + } + + private CamelCaseResult? TryConsumePatternOrMatchNextHump( + int patternIndex, int humpIndex, bool contiguous, int chunkOffset) + { + var bestResult = default(CamelCaseResult?); + + var candidateHump = _candidateHumps[humpIndex]; + + var maxPatternHumpLength = _patternText.Length - patternIndex; + var maxCandidateHumpLength = candidateHump.Length; + + var maxHumpMatchLength = Math.Min(maxPatternHumpLength, maxCandidateHumpLength); + for (var possibleHumpMatchLength = 1; possibleHumpMatchLength <= maxHumpMatchLength; possibleHumpMatchLength++) + { + if (!LowercaseSubstringsMatch( + _candidate, candidateHump.Start, + _patternText, patternIndex, possibleHumpMatchLength)) + { + // Stop trying to consume once the pattern contents no longer matches + // against the current candidate hump. + break; + } + + // The pattern substring 'f' has matched against 'F', or 'fi' has matched + // against 'Fi'. recurse and let the rest of the pattern match the remainder + // of the candidate. + + var resultOpt = TryMatch( + patternIndex + possibleHumpMatchLength, humpIndex + 1, contiguous, chunkOffset); + + if (resultOpt == null) + { + // Didn't match. Try the next longer pattern chunk. + continue; + } + + var result = resultOpt.Value; + // If this is our first hump add a 'from start' bonus. + if (humpIndex == 0) + { + result = result.WithFromStart(true); + } + + // If this is our last hump, add a 'to end' bonus. + if (humpIndex == _candidateHumps.GetCount() - 1) + { + result = result.WithToEnd(true); + } + + // This is the span of the hump of the candidate we matched. + var matchSpanToAdd = new TextSpan(chunkOffset + candidateHump.Start, possibleHumpMatchLength); + if (UpdateBestResultIfBetter(result, ref bestResult, matchSpanToAdd)) + { + // We found the best result so far. We can stop immediately. + break; + } + } + + return bestResult; + } + + /// + /// Updates the currently stored 'best result' if the current result is better. + /// Returns 'true' if no further work is required and we can break early, or + /// 'false' if we need to keep on going. + /// + /// If 'weight' is better than 'bestWeight' and matchSpanToAdd is not null, then + /// matchSpanToAdd will be added to matchedSpansInReverse. + /// + private bool UpdateBestResultIfBetter( + CamelCaseResult result, ref CamelCaseResult? bestResult, TextSpan? matchSpanToAdd) + { + if (matchSpanToAdd != null) + { + result = result.WithAddedMatchedSpan(matchSpanToAdd.Value); + } + + if (!IsBetter(result, bestResult)) + { + // Even though we matched this current candidate hump we failed to match + // the remainder of the pattern. Continue to the next candidate hump + // to see if our pattern character will match it and potentially succeed. + result.Free(); + + // We need to keep going. + return false; + } + + // This was result was better than whatever previous best result we had was. + // Free and overwrite the existing best results, and keep going. + bestResult?.Free(); + bestResult = result; + + // We found a path that allowed us to match everything contiguously + // from the beginning. This is the best match possible. So we can + // just break out now and return this result. + return GetKind(result) == PatternMatchKind.CamelCaseExact; + } + + private bool IsBetter(CamelCaseResult result, CamelCaseResult? currentBestResult) + { + if (currentBestResult == null) + { + // We have no current best. So this result is the best. + return true; + } + + return GetKind(result) < GetKind(currentBestResult.Value); + } + + private bool LowercaseSubstringsMatch( + string s1, int start1, string s2, int start2, int length) + { + for (var i = 0; i < length; i++) + { + if (char.ToLower(s1[start1 + i]) != char.ToLower(s2[start2 + i])) + { + return false; + } + } + + return true; + } + } + } +} diff --git a/src/Text/Impl/PatternMatching/ArraySlice.cs b/src/Text/Impl/PatternMatching/ArraySlice.cs new file mode 100644 index 0000000..6e7455e --- /dev/null +++ b/src/Text/Impl/PatternMatching/ArraySlice.cs @@ -0,0 +1,83 @@ +// 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.Diagnostics; +using TextSpan = Microsoft.VisualStudio.Text.Span; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + internal struct ArraySlice + { + private readonly T[] _array; + private int _start; + private int _length; + + public int Length => _length; + + public ArraySlice(T[] array) : this(array, 0, array.Length) + { + } + + public ArraySlice(T[] array, TextSpan span) : this(array, span.Start, span.Length) + { + } + + public ArraySlice(T[] array, int start, int length) : this() + { + _array = array; + SetStartAndLength(start, length); + } + + public T this[int i] + { + get + { + Debug.Assert(i < _length); + return _array[i + _start]; + } + } + + private void SetStartAndLength(int start, int length) + { + if (start < 0) + { + throw new ArgumentException(nameof(start), $"{start} < {0}"); + } + + if (start > _array.Length) + { + throw new ArgumentException(nameof(start), $"{start} > {_array.Length}"); + } + + CheckLength(start, length); + + _start = start; + _length = length; + } + + private void CheckLength(int start, int length) + { + if (length < 0) + { + throw new ArgumentException(nameof(length), $"{length} < {0}"); + } + + if (start + length > _array.Length) + { + throw new ArgumentException(nameof(start), $"{start} + {length} > {_array.Length}"); + } + } + + public void MoveStartForward(int amount) + { + SetStartAndLength(_start + amount, _length - amount); + } + + public void SetLength(int length) + { + CheckLength(_start, length); + _length = length; + } + } +} + diff --git a/src/Text/Impl/PatternMatching/CamelCaseResult.cs b/src/Text/Impl/PatternMatching/CamelCaseResult.cs new file mode 100644 index 0000000..f67572b --- /dev/null +++ b/src/Text/Impl/PatternMatching/CamelCaseResult.cs @@ -0,0 +1,90 @@ +// 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.Diagnostics; +using Microsoft.VisualStudio.Text.Utilities; +using TextSpan = Microsoft.VisualStudio.Text.Span; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + internal partial class PatternMatcher + { + private struct CamelCaseResult + { + public readonly bool FromStart; + public readonly bool Contiguous; + public readonly bool ToEnd; + public readonly int MatchCount; + public readonly ArrayBuilder MatchedSpansInReverse; + public readonly int ChunkOffset; + + public CamelCaseResult(bool fromStart, bool contiguous, bool toEnd, int matchCount, ArrayBuilder matchedSpansInReverse, int chunkOffset) + { + FromStart = fromStart; + Contiguous = contiguous; + ToEnd = toEnd; + MatchCount = matchCount; + MatchedSpansInReverse = matchedSpansInReverse; + ChunkOffset = chunkOffset; + + Debug.Assert(matchedSpansInReverse == null || matchedSpansInReverse.Count == matchCount); + } + + public void Free() + { + MatchedSpansInReverse?.Free(); + } + + public CamelCaseResult WithFromStart(bool fromStart) + => new CamelCaseResult(fromStart, Contiguous, ToEnd, MatchCount, MatchedSpansInReverse, ChunkOffset); + + public CamelCaseResult WithToEnd(bool toEnd) + => new CamelCaseResult(FromStart, Contiguous, toEnd, MatchCount, MatchedSpansInReverse, ChunkOffset); + + public CamelCaseResult WithAddedMatchedSpan(TextSpan value) + { + MatchedSpansInReverse?.Add(value); + return new CamelCaseResult(FromStart, Contiguous, ToEnd, MatchCount + 1, MatchedSpansInReverse, ChunkOffset); + } + } + + private static PatternMatchKind GetCamelCaseKind(CamelCaseResult result, StringBreaks candidateHumps) + { + /* CamelCase PatternMatchKind truth table: + * | FromStart | ToEnd | Contiguous || PatternMatchKind | + * | True | True | True || CamelCaseExact | + * | True | True | False || CamelCaseNonContiguousPrefix | + * | True | False | True || CamelCasePrefix | + * | True | False | False || CamelCaseNonContiguousPrefix | + * | False | True | True || CamelCaseSubstring | + * | False | True | False || CamelCaseNonContiguousSubstring | + * | False | False | True || CamelCaseSubstring | + * | False | False | False || CamelCaseNonContiguousSubstring | + */ + + if (result.FromStart) + { + if (result.Contiguous) + { + // We contiguously matched humps from the start of this candidate. If we + // matched all the humps, then this was an exact match, otherwise it was a + // contiguous prefix match + return result.ToEnd + ? PatternMatchKind.CamelCaseExact + : PatternMatchKind.CamelCasePrefix; + } + else + { + return PatternMatchKind.CamelCaseNonContiguousPrefix; + } + } + else + { + // We didn't match from the start. Distinguish between a match whose humps are all + // contiguous, and one that isn't. + return result.Contiguous + ? PatternMatchKind.CamelCaseSubstring + : PatternMatchKind.CamelCaseNonContiguousSubstring; + } + } + } +} diff --git a/src/Text/Impl/PatternMatching/CaseInsensitiveComparison.cs b/src/Text/Impl/PatternMatching/CaseInsensitiveComparison.cs new file mode 100644 index 0000000..6433ca7 --- /dev/null +++ b/src/Text/Impl/PatternMatching/CaseInsensitiveComparison.cs @@ -0,0 +1,74 @@ +// 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.Diagnostics; +using System.Globalization; +using System.Text; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + /// + /// Case-insensitive operations (mostly comparison) on unicode strings. + /// + public static class CaseInsensitiveComparison + { + // PERF: Cache a TextInfo for Unicode ToLower since this will be accessed very frequently + private static readonly TextInfo s_unicodeCultureTextInfo = GetUnicodeCulture().TextInfo; + + private static CultureInfo GetUnicodeCulture() + { + try + { + // We use the "en" culture to get the Unicode ToLower mapping, as it implements + // a much more recent Unicode version (6.0+) than the invariant culture (1.0), + // and it matches the Unicode version used for character categorization. + return new CultureInfo("en"); + } + catch (ArgumentException) // System.Globalization.CultureNotFoundException not on all platforms + { + // If "en" is not available, fall back to the invariant culture. Although it has bugs + // specific to the invariant culture (e.g. being version-locked to Unicode 1.0), at least + // we can rely on it being present on all platforms. + return CultureInfo.InvariantCulture; + } + } + + /// + /// ToLower implements the Unicode lowercase mapping + /// as described in ftp://ftp.unicode.org/Public/UNIDATA/UnicodeData.txt. + /// VB uses these mappings for case-insensitive comparison. + /// + /// + /// If is upper case, then this returns its Unicode lower case equivalent. Otherwise, is returned unmodified. + public static char ToLower(char c) + { + // PERF: This is a very hot code path in VB, optimize for ASCII + + // Perform a range check with a single compare by using unsigned arithmetic + if (unchecked((uint)(c - 'A')) <= ('Z' - 'A')) + { + return (char)(c | 0x20); + } + + if (c < 0xC0) // Covers ASCII (U+0000 - U+007F) and up to the next upper-case codepoint (Latin Capital Letter A with Grave) + { + return c; + } + + return ToLowerNonAscii(c); + } + + private static char ToLowerNonAscii(char c) + { + if (c == '\u0130') + { + // Special case Turkish I (LATIN CAPITAL LETTER I WITH DOT ABOVE) + // This corrects for the fact that the invariant culture only supports Unicode 1.0 + // and therefore does not "know about" this character. + return 'i'; + } + + return s_unicodeCultureTextInfo.ToLower(c); + } + } +} diff --git a/src/Text/Impl/PatternMatching/ContainerPatternMatcher.cs b/src/Text/Impl/PatternMatching/ContainerPatternMatcher.cs new file mode 100644 index 0000000..6048e0f --- /dev/null +++ b/src/Text/Impl/PatternMatching/ContainerPatternMatcher.cs @@ -0,0 +1,121 @@ +// 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.Generic; +using System.Globalization; +using System.Linq; +using Microsoft.VisualStudio.Text.Utilities; +using Microsoft.VisualStudio.Utilities; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + internal partial class PatternMatcher + { + private sealed partial class ContainerPatternMatcher : PatternMatcher + { + private readonly PatternSegment[] _patternSegments; + private readonly char[] _containerSplitCharacters; + + /// + /// Creates a new ContainerPatternMatcher. + /// + /// The pattern itself needs to be split up, to match against candidates. Suppose the user searches for Apple.Banana.Charlie using A.B.C, + /// the compiler recognizes that these are namespaces, splits the pattern up and passes in { "A", "B", "C" }. + /// What characters should candidates be split on. In the above example, it would be { '.' } + /// Important for some string operations. + /// Do we tolerate mis-spellings? + /// Does a match not at a camel-case boundary count? (e.g. Does AppleBanana match 'ppl' as a search string? + /// Do we want to get spans back (performance impacting). + public ContainerPatternMatcher( + string[] patternParts, IReadOnlyCollection containerSplitCharacters, + CultureInfo culture, + bool allowFuzzyMatching = false, + bool allowSimpleSubstringMatching = false, + bool includeMatchedSpans = false) + : base(includeMatchedSpans, culture, allowFuzzyMatching, allowSimpleSubstringMatching) + { + _containerSplitCharacters = containerSplitCharacters.ToArray(); + + _patternSegments = patternParts + .Select(text => new PatternSegment(text.Trim(), allowFuzzyMatching: allowFuzzyMatching)) + .ToArray(); + + _invalidPattern = _patternSegments.Length == 0 || _patternSegments.Any(s => s.IsInvalid); + } + + public override void Dispose() + { + base.Dispose(); + + foreach (var segment in _patternSegments) + { + segment.Dispose(); + } + } + + public override PatternMatch? TryMatch(string candidate) + { + if (SkipMatch(candidate)) + { + return null; + } + + var match = TryMatch(candidate, fuzzyMatch: false); + if (!match.HasValue) + { + match = TryMatch(candidate, fuzzyMatch: true); + } + + return match; + } + + private PatternMatch? TryMatch(string candidate, bool fuzzyMatch) + { + if (fuzzyMatch && !_allowFuzzyMatching) + { + return null; + } + + var containerParts = candidate.Split(_containerSplitCharacters, StringSplitOptions.RemoveEmptyEntries); + var patternSegmentCount = _patternSegments.Length; + var containerPartCount = containerParts.Length; + + if (patternSegmentCount > containerPartCount) + { + // There weren't enough container parts to match against the pattern parts. + // So this definitely doesn't match. + return null; + } + + // So far so good. Now break up the container for the candidate and check if all + // the dotted parts match up correctly. + + PatternMatch? match = null, result = null; + + for (int i = patternSegmentCount - 1, j = containerPartCount - 1; + i >= 0; + i--, j--) + { + var segment = _patternSegments[i]; + var containerName = containerParts[j]; + + // Add up the lengths of all the container parts before this one, as well is the split characters that were removed. + int containerOffset = j; + for (int k = 0; k < j; k++) + containerOffset += containerParts[k].Length; + + result = MatchPatternSegment(containerName, segment, fuzzyMatch, containerOffset); + if (!result.HasValue) + { + // This container didn't match the pattern piece. So there's no match at all. + return null; + } + + match = match?.Merge(result.Value, PatternMatchMergeStrategy.Container) ?? result; + } + + return match; + } + } + } +} diff --git a/src/Text/Impl/PatternMatching/EditDistance.cs b/src/Text/Impl/PatternMatching/EditDistance.cs new file mode 100644 index 0000000..5eb25d2 --- /dev/null +++ b/src/Text/Impl/PatternMatching/EditDistance.cs @@ -0,0 +1,669 @@ +// 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.Generic; +using System.Diagnostics; +using System.Text; +using System.Threading; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + /// + /// NOTE: Only use if you truly need an edit distance. + /// + /// Implementation of the Damerau-Levenshtein edit distance algorithm from: + /// An Extension of the String-to-String Correction Problem: + /// Published in Journal of the ACM (JACM) + /// Volume 22 Issue 2, April 1975. + /// + /// Important, unlike many edit distance algorithms out there, this one implements a true metric + /// that satisfies the triangle inequality. (Unlike the "Optimal String Alignment" or "Restricted + /// string edit distance" solutions which do not). This means this edit distance can be used in + /// other domains that require the triangle inequality (like BKTrees). + /// + /// Specifically, this implementation satisfies the following inequality: D(x, y) + D(y, z) >= D(x, z) + /// (where D is the edit distance). + /// + internal class EditDistance : IDisposable + { + // Our edit distance algorithm makes use of an 'infinite' value. A value so high that it + // could never participate in an edit distance (and effectively means the path through it + // is dead). + // + // We do *not* represent this with "int.MaxValue" due to the presence of certain addition + // operations in the edit distance algorithm. These additions could cause int.MaxValue + // to roll over to a very negative value (which would then look like the lowest cost + // path). + // + // So we pick a value that is both effectively larger than any possible edit distance, + // and also has no chance of overflowing. + private const int Infinity = int.MaxValue >> 1; + + public const int BeyondThreshold = int.MaxValue; + + private string _source; + private char[] _sourceLowerCaseCharacters; + + public EditDistance(string text) + { + _source = text ?? throw new ArgumentNullException(nameof(text)); + _sourceLowerCaseCharacters = ConvertToLowercaseArray(text); + } + + private static char[] ConvertToLowercaseArray(string text) + { + var array = ArrayPool.GetArray(text.Length); + for (int i = 0; i < text.Length; i++) + { + array[i] = CaseInsensitiveComparison.ToLower(text[i]); + } + + return array; + } + + public void Dispose() + { + ArrayPool.ReleaseArray(_sourceLowerCaseCharacters); + _source = null; + _sourceLowerCaseCharacters = null; + } + + public static int GetEditDistance(string source, string target, int threshold = int.MaxValue) + { + using (var editDistance = new EditDistance(source)) + { + return editDistance.GetEditDistance(target, threshold); + } + } + + public static int GetEditDistance(char[] source, char[] target, int threshold = int.MaxValue) + { + return GetEditDistance(new ArraySlice(source), new ArraySlice(target), threshold); + } + + public int GetEditDistance(string target, int threshold = int.MaxValue) + { + if (_sourceLowerCaseCharacters == null) + { + throw new ObjectDisposedException(nameof(EditDistance)); + } + + var targetLowerCaseCharacters = ConvertToLowercaseArray(target); + try + { + return GetEditDistance( + new ArraySlice(_sourceLowerCaseCharacters, 0, _source.Length), + new ArraySlice(targetLowerCaseCharacters, 0, target.Length), + threshold); + } + finally + { + ArrayPool.ReleaseArray(targetLowerCaseCharacters); + } + } + + private const int MaxMatrixPoolDimension = 64; + private static readonly ThreadLocal t_matrixPool = + new ThreadLocal(() => InitializeMatrix(new int[MaxMatrixPoolDimension, MaxMatrixPoolDimension])); + + private static ThreadLocal> t_dictionaryPool = + new ThreadLocal>(() => new Dictionary()); + + private static int[,] GetMatrix(int width, int height) + { + if (width > MaxMatrixPoolDimension || height > MaxMatrixPoolDimension) + { + return InitializeMatrix(new int[width, height]); + } + + return t_matrixPool.Value; + } + + private static int[,] InitializeMatrix(int[,] matrix) + { + // All matrices share the following in common: + // + // ------------------ + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 7 + // |∞ 1 + // |∞ 2 + // |∞ 3 + // |∞ 4 + // |∞ 5 + // |∞ 6 + // |∞ 7 + // + // So we initialize this once when the matrix is created. For pooled arrays we only + // have to do this once, and it will retain this layout for all future computations. + + + var width = matrix.GetLength(0); + var height = matrix.GetLength(1); + + for (int i = 0; i < width; i++) + { + matrix[i, 0] = Infinity; + + if (i < width - 1) + { + matrix[i + 1, 1] = i; + } + } + + for (int j = 0; j < height; j++) + { + matrix[0, j] = Infinity; + + if (j < height - 1) + { + matrix[1, j + 1] = j; + } + } + + return matrix; + } + + public static int GetEditDistance(ArraySlice source, ArraySlice target, int threshold = int.MaxValue) + { + return source.Length <= target.Length + ? GetEditDistanceWorker(source, target, threshold) + : GetEditDistanceWorker(target, source, threshold); + } + + private static int GetEditDistanceWorker(ArraySlice source, ArraySlice target, int threshold) + { + // Note: sourceLength will always be smaller or equal to targetLength. + // + // Also Note: sourceLength and targetLength values will mutate and represent the lengths + // of the portions of the arrays we want to compare. However, even after mutation, hte + // invariant htat sourceLength is <= targetLength will remain. + Debug.Assert(source.Length <= target.Length); + + // First: + // Determine the common prefix/suffix portions of the strings. We don't even need to + // consider them as they won't add anything to the edit cost. + while (source.Length > 0 && source[source.Length - 1] == target[target.Length - 1]) + { + source.SetLength(source.Length - 1); + target.SetLength(target.Length - 1); + } + + while (source.Length > 0 && source[0] == target[0]) + { + source.MoveStartForward(amount: 1); + target.MoveStartForward(amount: 1); + } + + // 'sourceLength' and 'targetLength' are now the lengths of the substrings of our strings that we + // want to compare. 'startIndex' is the starting point of the substrings in both array. + // + // If we've matched all of the 'source' string in the prefix and suffix of 'target'. then the edit + // distance is just whatever operations we have to create the remaining target substring. + // + // Note: we don't have to check if targetLength is 0. That's because targetLength being zero would + // necessarily mean that sourceLength is 0. + var sourceLength = source.Length; + var targetLength = target.Length; + if (sourceLength == 0) + { + return targetLength <= threshold ? targetLength : BeyondThreshold; + } + + // The is the minimum number of edits we'd have to make. i.e. if 'source' and + // 'target' are the same length, then we might not need to make any edits. However, + // if target has length 10 and source has length 7, then we're going to have to + // make at least 3 edits no matter what. + var minimumEditCount = targetLength - sourceLength; + Debug.Assert(minimumEditCount >= 0); + + // If the number of edits we'd have to perform is greater than our threshold, then + // there's no point in even continuing. + if (minimumEditCount > threshold) + { + return BeyondThreshold; + } + + // Say we want to find the edit distance between "sunday" and "saturday". Our initial + // matrix will be: + // + // (Note: for purposes of this explanation we will not be trimming off the common + // prefix/suffix of the strings. That optimization does not affect any of the + // remainder of the explanation). + // + // s u n d a y + // ---------------- + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 + // s |∞ 1 + // a |∞ 2 + // t |∞ 3 + // u |∞ 4 + // r |∞ 5 + // d |∞ 6 + // a |∞ 7 + // y |∞ 8 + // + // Note that the matrix will always be square, or a rectangle that is taller htan it is + // longer. Our 'source' is at the top, and our 'target' is on the left. The edit distance + // between any prefix of 'source' and any prefix of 'target' can then be found in + // the unfilled area of the matrix. Specifically, if we have source.substring(0, m) and + // target.substring(0, n), then the edit distance for them can be found at matrix position + // (m+1, n+1). This is why the 1'th row and 1'th column can be prefilled. They represent + // the cost to go from the empty target to the full source or the empty source to the full + // target (respectively). So, if we wanted to know the edit distance between "sun" and + // "sat", we'd look at (3+1, 3+1). It then follows that our final edit distance between + // the full source and target is in the lower right corner of this matrix. + // + // If we fill out the matrix fully we'll get: + // + // s u n d a y <-- source + // ---------------- + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 + // s |∞ 1 0 1 2 3 4 5 + // a |∞ 2 1 1 2 3 3 4 + // t |∞ 3 2 2 2 3 4 4 + // u |∞ 4 3 2 3 3 4 5 + // r |∞ 5 4 3 3 4 4 5 + // d |∞ 6 5 4 4 3 4 5 + // a |∞ 7 6 5 5 4 3 4 + // y |∞ 8 7 6 6 5 4 3 <-- + // ^ + // | + // + // So in this case, the edit distance is 3. Or, specifically, the edits: + // + // Sunday -> Replace("n", "r") -> + // Surday -> Insert("a") -> + // Saurday -> Insert("t") -> + // Saturday + // + // + // Now: in the case where we want to know what the edit distance actually is (for example + // when making a BKTree), we must fill out this entire array to get the true edit distance. + // + // However, in some cases we can do a bit better. For example, if a client only wants to + // the edit distance *when the edit distance will be less than some threshold* then we do + // not need to examine the entire matrix. We only want to examine until the point where + // we realize that, no matter what, our final edit distance will be more than that threshold + // (at which point we can return early). + // + // Some things are trivially easy to check. First, the edit distance between two strings is at + // *best* the difference of their lengths. i.e. if i have "aa" and "aaaaa" then the edit + // distance is 3 (the difference of 5 and 2). If our threshold is less then 3 then there + // is no way these two strings could match. So we can leave early if we can tell it would + // simply be impossible to get an edit distance within the specified threshold. + // + // Second, let's look at our matrix again: + // + // s u n d a y + // ---------------- + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 + // s |∞ 1 + // a |∞ 2 + // t |∞ 3 + // u |∞ 4 + // r |∞ 5 + // d |∞ 6 + // a |∞ 7 + // y |∞ 8 * + // + // We want to know what the value is at *, and we want to stop as early as possible if it + // is greater than our threshold. + // + // Given the edit distance rules we observe edit distance at any point (i,j) in the matrix will + // always be greater than or equal to the value in (i-1, j-1). i.e. the edit distance of + // any two strings is going to be *at best* equal to the edit distance of those two strings + // without their final characters. If their final characters are the same, they'll ahve the + // same edit distance. If they are different, the edit distance will be greater. Given + // that we know the final edit distance is in the lower right, we can discover something + // useful in the matrix. + // + // s u n d a y + // ---------------- + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 + // s |∞ 1 + // a |∞ 2 + // t |∞ 3 ` + // u |∞ 4 ` + // r |∞ 5 ` + // d |∞ 6 ` + // a |∞ 7 ` + // y |∞ 8 * + // + // The slashes are the "bottom" diagonal leading to the lower right. The value in the + // lower right will be strictly equal to or greater than any value on this diagonal. + // Thus, if that value exceeds the threshold, we know we can stop immediately as the + // total edit distance must be greater than the threshold. + // + // We can use similar logic to avoid even having to examine more of the matrix when we + // have a threshold. First, consider the same diagonal. + // + // s u n d a y + // ---------------- + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 + // s |∞ 1 + // a |∞ 2 + // t |∞ 3 ` + // u |∞ 4 ` x + // r |∞ 5 ` | + // d |∞ 6 ` | + // a |∞ 7 ` | + // y |∞ 8 * + // + // And then consider a point above that diagonal (indicated by x). In the example + // above, the edit distance to * from 'x' will be (x+4). If, for example, threshold + // was '2', then it would be impossible for the path from 'x' to provide a good + // enough edit distance *ever*. Similarly: + // + // s u n d a y + // ---------------- + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 + // s |∞ 1 + // a |∞ 2 + // t |∞ 3 ` + // u |∞ 4 ` + // r |∞ 5 ` + // d |∞ 6 ` + // a |∞ 7 ` + // y |∞ 8 y - - * + // + // Here we see that the final edit distance will be "y+3". Again, if the edit + // distance threshold is less than 3, then no path from y will provide a good + // enough edit distance. + // + // So, if we had an edit distance threshold of 3, then the range around that + // bottom diagonal that we should consider checking is: + // + // s u n d a y + // ---------------- + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 + // s |∞ 1 | | + // a |∞ 2 | | | + // t |∞ 3 ` | | | + // u |∞ 4 - ` | | | + // r |∞ 5 - - ` | | | + // d |∞ 6 - - - ` | | + // a |∞ 7 - - - ` | + // y |∞ 8 - - - * + // + // Now, also consider that it will take a minimum of targetLength-sourceLength edits + // just to move to the lower diagonal from the upper diagonal. That leaves + // 'threshold - (targetLength - sourceLength)' edits remaining. In this example, that + // means '3 - (8 - 6)' = 1. Because of this our lower diagonal offset is capped at: + // + // s u n d a y + // ---------------- + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 + // s |∞ 1 | | + // a |∞ 2 | | | + // t |∞ 3 ` | | | + // u |∞ 4 - ` | | | + // r |∞ 5 - ` | | | + // d |∞ 6 - ` | | + // a |∞ 7 - ` | + // y |∞ 8 - * + // + // If we mark the upper diagonal appropriately we see the matrix as: + // + // s u n d a y + // ---------------- + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 + // s |∞ 1 ` | + // a |∞ 2 ` | + // t |∞ 3 ` ` | + // u |∞ 4 - ` ` | + // r |∞ 5 - ` ` | + // d |∞ 6 - ` ` + // a |∞ 7 - ` + // y |∞ 8 - * + // + // Or, effectively, we only need to examine 'threshold - (targetLength - sourceLength)' + // above and below the diagonals. + // + // In practice, when a threshold is provided it is normally capped at '2'. Given that, + // the most around the diagonal we'll ever have to check is +/- 2 elements. i.e. with + // strings of length 10 we'd only check: + // + // a b c d e f g h i j + // ------------------------ + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 7 8 9 10 + // m |∞ 1 * * * + // n |∞ 2 * * * * + // o |∞ 3 * * * * * + // p |∞ 4 * * * * * + // q |∞ 5 * * * * * + // r |∞ 6 * * * * * + // s |∞ 7 * * * * * + // t |∞ 8 * * * * * + // u |∞ 9 * * * * + // v |∞10 * * * + // + // or 10+18+16=44. Or only 44%. if our threshold is two and our strings differ by length + // 2 then we have: + // + // a b c d e f g h + // -------------------- + // |∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ + // |∞ 0 1 2 3 4 5 6 7 8 + // m |∞ 1 * + // n |∞ 2 * * + // o |∞ 3 * * * + // p |∞ 4 * * * + // q |∞ 5 * * * + // r |∞ 6 * * * + // s |∞ 7 * * * + // t |∞ 8 * * * + // u |∞ 9 * * + // v |∞10 * + // + // Then we examine 8+8+8=24 out of 80, or only 30% of the matrix. As the strings + // get larger, the savings increase as well. + + // -------------------------------------------------------------------------------- + + // The highest cost it can be to convert a source to target is targetLength. i.e. + // changing all the characters in source to target (which would be be 'sourceLength' + // changes), and then adding all the missing characters in 'target' (which is + // 'targetLength' - 'sourceLength' changes). Combined that's 'targetLength'. + // + // So we can just cap our threshold here. This makes some of the walking code + // below simpler. + threshold = Math.Min(threshold, targetLength); + + var offset = threshold - minimumEditCount; + Debug.Assert(offset >= 0); + + var matrix = GetMatrix(sourceLength + 2, targetLength + 2); + + var characterToLastSeenIndex_inSource = t_dictionaryPool.Value; + characterToLastSeenIndex_inSource.Clear(); + + for (int i = 1; i <= sourceLength; i++) + { + var lastMatchIndex_inTarget = 0; + var sourceChar = source[i - 1]; + + // Determinethe portion of the column we actually want to examine. + var jStart = Math.Max(1, i - offset); + var jEnd = Math.Min(targetLength, i + minimumEditCount + offset); + + // If we're examining only a subportion of the column, then we need to make sure + // that the values outside that range are set to Infinity. That way we don't + // consider them when we look through edit paths from above (for this column) or + // from the left (for the next column). + if (jStart > 1) + { + matrix[i + 1, jStart] = Infinity; + } + + if (jEnd < targetLength) + { + matrix[i + 1, jEnd + 2] = Infinity; + } + + for (int j = jStart; j <= jEnd; j++) + { + var targetChar = target[j - 1]; + + var i1 = GetValue(characterToLastSeenIndex_inSource, targetChar); + var j1 = lastMatchIndex_inTarget; + + var matched = sourceChar == targetChar; + if (matched) + { + lastMatchIndex_inTarget = j; + } + + matrix[i + 1, j + 1] = Min( + matrix[i, j] + (matched ? 0 : 1), + matrix[i + 1, j] + 1, + matrix[i, j + 1] + 1, + matrix[i1, j1] + (i - i1 - 1) + 1 + (j - j1 - 1)); + } + + characterToLastSeenIndex_inSource[sourceChar] = i; + + // Recall that minimumEditCount is simply the difference in length of our two + // strings. So matrix[i+1,i+1] is the cost for the upper-left diagonal of the + // matrix. matrix[i+1,i+1+minimumEditCount] is the cost for the lower right diagonal. + // Here we are simply getting the lowest cost edit of hese two substrings so far. + // If this lowest cost edit is greater than our threshold, then there is no need + // to proceed. + if (matrix[i + 1, i + minimumEditCount + 1] > threshold) + { + return BeyondThreshold; + } + } + + return matrix[sourceLength + 1, targetLength + 1]; + } + + private static string ToString(int[,] matrix, int width, int height) + { + var sb = new StringBuilder(); + for (var j = 0; j < height; j++) + { + for (var i = 0; i < width; i++) + { + var v = matrix[i + 2, j + 2]; + sb.Append((v == Infinity ? "∞" : v.ToString()) + " "); + } + sb.AppendLine(); + } + + return sb.ToString().Trim(); + } + + private static int GetValue(Dictionary da, char c) + { + return da.TryGetValue(c, out var value) ? value : 0; + } + + private static int Min(int v1, int v2, int v3, int v4) + { + Debug.Assert(v1 >= 0); + Debug.Assert(v2 >= 0); + Debug.Assert(v3 >= 0); + Debug.Assert(v4 >= 0); + + var min = v1; + if (v2 < min) + { + min = v2; + } + + if (v3 < min) + { + min = v3; + } + + if (v4 < min) + { + min = v4; + } + + Debug.Assert(min >= 0); + return min; + } + + private static void SetValue(int[,] matrix, int i, int j, int val) + { + // Matrix is -1 based, so we add 1 to both i and j to make it + // possible to index into the actual storage. + matrix[i + 1, j + 1] = val; + } + } + + internal class SimplePool where T : class + { + private readonly object _gate = new object(); + private readonly Stack _values = new Stack(); + private readonly Func _allocate; + + public SimplePool(Func allocate) + { + _allocate = allocate; + } + + public T Allocate() + { + lock (_gate) + { + if (_values.Count > 0) + { + return _values.Pop(); + } + + return _allocate(); + } + } + + public void Free(T value) + { + lock (_gate) + { + _values.Push(value); + } + } + } + + internal static class ArrayPool + { + private const int MaxPooledArraySize = 256; + + // Keep around a few arrays of size 256 that we can use for operations without + // causing lots of garbage to be created. If we do compare items larger than + // that, then we will just allocate and release those arrays on demand. + private static SimplePool s_pool = new SimplePool(() => new T[MaxPooledArraySize]); + + public static T[] GetArray(int size) + { + if (size <= MaxPooledArraySize) + { + var array = s_pool.Allocate(); + Array.Clear(array, 0, array.Length); + return array; + } + + return new T[size]; + } + + public static void ReleaseArray(T[] array) + { + if (array.Length <= MaxPooledArraySize) + { + s_pool.Free(array); + } + } + } +} diff --git a/src/Text/Impl/PatternMatching/PatternMatchExtensions.cs b/src/Text/Impl/PatternMatching/PatternMatchExtensions.cs new file mode 100644 index 0000000..55ca719 --- /dev/null +++ b/src/Text/Impl/PatternMatching/PatternMatchExtensions.cs @@ -0,0 +1,139 @@ +using System; +using System.Collections.Generic; +using System.Collections.Immutable; +using System.Linq; +using System.Text; +using System.Threading.Tasks; +using Microsoft.VisualStudio.Text.Utilities; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + internal static class PatternMatchExtensions + { + private static ImmutableArray MergeSpans(PatternMatch match1, PatternMatch match2) + { + var collection1 = new NormalizedSpanCollection(match1.MatchedSpans); + var collection2 = new NormalizedSpanCollection(match2.MatchedSpans); + + var builder = ArrayBuilder.GetInstance(); + builder.AddRange(NormalizedSpanCollection.Union(collection1, (collection2))); + return builder.ToImmutable(); + } + + public static PatternMatch Merge(this PatternMatch match1, PatternMatch match2, PatternMatchMergeStrategy strategy) + { + PatternMatchKind kind; + if (strategy == PatternMatchMergeStrategy.Simple) + { + // Do some intelligent merging, since both matches came from the same string. + kind = MergeMatchKinds(match1.Kind, match2.Kind); + } + else + { + // Give the worst kind of match, since these are relating to different containers. + kind = match1.Kind.CompareTo(match2.Kind) > 0 ? match1.Kind : match2.Kind; + } + + // Give punctuation stripped if either has it stripped + var punctuation = match1.IsPunctuationStripped || match2.IsPunctuationStripped; + + // Give case sensitivity only if both are case sensitive + var caseSensitive = match1.IsCaseSensitive && match2.IsCaseSensitive; + + // Give spans from both + var spans = MergeSpans(match1, match2); + + return new PatternMatch(kind, punctuation, caseSensitive, spans); + } + + private static PatternMatchKind MergeMatchKinds(PatternMatchKind kind1, PatternMatchKind kind2) + { + // Ensure ordering for simpler processing below. + if (kind2 < kind1) + { + return MergeMatchKinds(kind2, kind1); + } + + // Guess the match kind. Unfortunately we can't assume contiguity. It is hard to guess when dealing with Exact, Fuzzy, + // and multiple prefixes, so assume that if you have an exact match, the other merged thing must be redundant. + // The only exception is fuzzy (which degrades everything) since the match obviously missed somehow. + // + // Kinds: + // Exact (E), Prefix (P), Substring (S), CamelCaseExact (CE), CamelCasePrefix (CP), CamelCaseNonContiguousPrefix (NP) + // CamelCaseSubstring (CS), CamelCaseNonContiguousSubstring(NS ), Fuzzy (F) + // + // Mapping: + // In |E |P |S |CE |CP |NP |CS |NS |F + // ___________________________________ + // E |E E E E E E E E F + // P | P NP CE CP NP NP NP F + // S | NS CE NP NP NS NS F + // CE | CE CE CE CE CE F + // CP | CP NP NP NP F + // NP | NP NP NP F + // CS | NS NS F + // NS | NS F + // F | F + // + // See PatternMatchingUnitTests.MatchMultiWordPatterns_MatchKindMerge for examples. There's a bunch. + + if (kind1 == PatternMatchKind.Fuzzy || kind2 == PatternMatchKind.Fuzzy) + { + return PatternMatchKind.Fuzzy; + } + else if (kind1 == PatternMatchKind.Exact || kind2 == PatternMatchKind.Exact) + { + return PatternMatchKind.Exact; + } + else if (kind1 == PatternMatchKind.CamelCaseExact || kind2 == PatternMatchKind.CamelCaseExact) + { + return PatternMatchKind.CamelCaseExact; + } + else if (kind1 == PatternMatchKind.CamelCaseNonContiguousPrefix || kind2 == PatternMatchKind.CamelCaseNonContiguousPrefix) + { + return PatternMatchKind.CamelCaseNonContiguousPrefix; + } + else + { + // Ok, we have to actually think about this one. We can assume that kind1 <= kind2 here. + // + //Reduced manifest from above: + // In |P |S |CP |CS |NS + // ____________________ + // P |P NP CP NP NP + // S | NS NP NS NS + // CP | CP NP NP + // CS | NS NS + // NS | NS + switch (kind1) + { + case PatternMatchKind.Prefix: + if (kind2 == PatternMatchKind.Prefix) + { + return PatternMatchKind.Prefix; + } + else if (kind2 == PatternMatchKind.CamelCasePrefix) + { + return PatternMatchKind.CamelCasePrefix; + } + return PatternMatchKind.CamelCaseNonContiguousPrefix; + case PatternMatchKind.Substring: + if (kind2 == PatternMatchKind.CamelCasePrefix) + { + return PatternMatchKind.CamelCaseNonContiguousPrefix; + } + return PatternMatchKind.CamelCaseNonContiguousSubstring; + case PatternMatchKind.CamelCasePrefix: + if (kind2 == PatternMatchKind.CamelCasePrefix) + { + return PatternMatchKind.CamelCasePrefix; + } + return PatternMatchKind.CamelCaseNonContiguousPrefix; + default: + // Handles CamelCaseSubstring and CamelCaseNonContiguousSubstring + return PatternMatchKind.CamelCaseNonContiguousSubstring; + } + } + } + } +} diff --git a/src/Text/Impl/PatternMatching/PatternMatchMergeStrategy.cs b/src/Text/Impl/PatternMatching/PatternMatchMergeStrategy.cs new file mode 100644 index 0000000..0374736 --- /dev/null +++ b/src/Text/Impl/PatternMatching/PatternMatchMergeStrategy.cs @@ -0,0 +1,25 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; +using System.Threading.Tasks; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + /// + /// This indicates how matches should be merged together when multiple matches are found, and only one can be returned. + /// + internal enum PatternMatchMergeStrategy + { + /// + /// Indicates that matches were found in a single string and should be merged as intelligently as possible to report best results. + /// + Simple, + + /// + /// Indicates a container match, which means matches are all from distinct parts of the original string, and should be merged with + /// a take-the-worst policy. + /// + Container + } +} diff --git a/src/Text/Impl/PatternMatching/PatternMatcher.PatternSegment.cs b/src/Text/Impl/PatternMatching/PatternMatcher.PatternSegment.cs new file mode 100644 index 0000000..392eaad --- /dev/null +++ b/src/Text/Impl/PatternMatching/PatternMatcher.PatternSegment.cs @@ -0,0 +1,117 @@ +// 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; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + internal partial class PatternMatcher + { + /// + /// First we break up the pattern given by dots. Each portion of the pattern between the + /// dots is a 'Segment'. The 'Segment' contains information about the entire section of + /// text between the dots, as well as information about any individual 'Words' that we + /// can break the segment into. + /// + private struct PatternSegment : IDisposable + { + // Information about the entire piece of text between the dots. For example, if the + // text between the dots is 'Get-Keyword', then TotalTextChunk.Text will be 'Get-Keyword' and + // TotalTextChunk.CharacterSpans will correspond to 'G', 'et', 'K' and 'eyword'. + public readonly TextChunk TotalTextChunk; + + // Information about the subwords compromising the total word. For example, if the + // text between the dots is 'Get-Keyword', then the subwords will be 'Get' and 'Keyword' + // Those individual words will have CharacterSpans of ('G' and 'et') and ('K' and 'eyword') + // respectively. + public readonly TextChunk[] SubWordTextChunks; + + public PatternSegment(string text, bool allowFuzzyMatching) + { + this.TotalTextChunk = new TextChunk(text, allowFuzzyMatching); + this.SubWordTextChunks = BreakPatternIntoSubWords(text, allowFuzzyMatching); + } + + public void Dispose() + { + this.TotalTextChunk.Dispose(); + foreach (var chunk in this.SubWordTextChunks) + { + chunk.Dispose(); + } + } + + public bool IsInvalid => this.SubWordTextChunks.Length == 0; + + private static int CountTextChunks(string pattern) + { + int count = 0; + int wordLength = 0; + + for (int i = 0; i < pattern.Length; i++) + { + if (IsWordChar(pattern[i])) + { + wordLength++; + } + else + { + if (wordLength > 0) + { + count++; + wordLength = 0; + } + } + } + + if (wordLength > 0) + { + count++; + } + + return count; + } + + private static TextChunk[] BreakPatternIntoSubWords(string pattern, bool allowFuzzyMatching) + { + int partCount = CountTextChunks(pattern); + + if (partCount == 0) + { + return Array.Empty(); + } + + var result = new TextChunk[partCount]; + int resultIndex = 0; + int wordStart = 0; + int wordLength = 0; + + for (int i = 0; i < pattern.Length; i++) + { + var ch = pattern[i]; + if (IsWordChar(ch)) + { + if (wordLength++ == 0) + { + wordStart = i; + } + } + else + { + if (wordLength > 0) + { + result[resultIndex++] = new TextChunk(pattern.Substring(wordStart, wordLength), allowFuzzyMatching); + wordLength = 0; + } + } + } + + if (wordLength > 0) + { + result[resultIndex++] = new TextChunk(pattern.Substring(wordStart, wordLength), allowFuzzyMatching); + } + + return result; + } + } + } +} diff --git a/src/Text/Impl/PatternMatching/PatternMatcher.TextChunk.cs b/src/Text/Impl/PatternMatching/PatternMatcher.TextChunk.cs new file mode 100644 index 0000000..e498407 --- /dev/null +++ b/src/Text/Impl/PatternMatching/PatternMatcher.TextChunk.cs @@ -0,0 +1,44 @@ +// 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; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + internal partial class PatternMatcher + { + /// + /// Information about a chunk of text from the pattern. The chunk is a piece of text, with + /// cached information about the character spans within in. Character spans separate out + /// capitalized runs and lowercase runs. i.e. if you have AAbb, then there will be two + /// character spans, one for AA and one for BB. + /// + private struct TextChunk : IDisposable + { + public readonly string Text; + + /// + /// Character spans separate out + /// capitalized runs and lowercase runs. i.e. if you have AAbb, then there will be two + /// character spans, one for AA and one for BB. + /// + public readonly StringBreaks CharacterSpans; + + public readonly WordSimilarityChecker SimilarityChecker; + + public TextChunk(string text, bool allowFuzzingMatching) + { + this.Text = text; + this.CharacterSpans = StringBreaker.BreakIntoCharacterParts(text); + this.SimilarityChecker = allowFuzzingMatching + ? WordSimilarityChecker.Allocate(text, substringsAreSimilar: false) + : null; + } + + public void Dispose() + { + this.CharacterSpans.Dispose(); + this.SimilarityChecker?.Free(); + } + } + } +} diff --git a/src/Text/Impl/PatternMatching/PatternMatcher.cs b/src/Text/Impl/PatternMatching/PatternMatcher.cs new file mode 100644 index 0000000..f781db3 --- /dev/null +++ b/src/Text/Impl/PatternMatching/PatternMatcher.cs @@ -0,0 +1,610 @@ +// 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.Generic; +using System.Collections.Immutable; +using System.Diagnostics.Contracts; +using System.Globalization; +using Microsoft.VisualStudio.Text; +using Microsoft.VisualStudio.Text.Utilities; +using Microsoft.VisualStudio.Utilities; +using TextSpan = Microsoft.VisualStudio.Text.Span; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + /// + /// The pattern matcher is thread-safe. However, it maintains an internal cache of + /// information as it is used. Therefore, you should not keep it around forever and should get + /// and release the matcher appropriately once you no longer need it. + /// Also, while the pattern matcher is culture aware, it uses the culture specified in the + /// constructor. + /// + internal abstract partial class PatternMatcher : IDisposable, IPatternMatcher + { + public const int NoBonus = 0; + public const int CamelCaseContiguousBonus = 1; + public const int CamelCaseMatchesFromStartBonus = 2; + public const int CamelCaseMaxWeight = CamelCaseContiguousBonus + CamelCaseMatchesFromStartBonus; + + private readonly object _gate = new object(); + + private readonly bool _includeMatchedSpans; + private readonly bool _allowFuzzyMatching; + private readonly bool _allowSimpleSubstringMatching; + + private readonly Dictionary _stringToWordSpans = new Dictionary(); + private static readonly Func _breakIntoWordSpans = StringBreaker.BreakIntoWordParts; + + // PERF: Cache the culture's compareInfo to avoid the overhead of asking for them repeatedly in inner loops + private readonly CompareInfo _compareInfo; + + private bool _invalidPattern; + /// + /// Construct a new PatternMatcher using the specified culture. + /// + /// The culture to use for string searching and comparison. + /// Whether or not the matching parts of the candidate should be supplied in results. + /// Whether or not close matches should count as matches. + protected PatternMatcher( + bool includeMatchedSpans, + CultureInfo culture, + bool allowFuzzyMatching = false, + bool allowSimpleSubstringMatching = false) + { + culture = culture ?? CultureInfo.CurrentCulture; + _compareInfo = culture.CompareInfo; + _includeMatchedSpans = includeMatchedSpans; + _allowFuzzyMatching = allowFuzzyMatching; + _allowSimpleSubstringMatching = allowSimpleSubstringMatching; + } + + public virtual void Dispose() + { + foreach (var kvp in _stringToWordSpans) + { + kvp.Value.Dispose(); + } + + _stringToWordSpans.Clear(); + } + + public static PatternMatcher CreateSimplePatternMatcher( + string pattern, + CultureInfo culture = null, + bool includeMatchedSpans = false, + bool allowFuzzyMatching = false, + bool allowSimpleSubstringMatching = false) + { + return new SimplePatternMatcher(pattern, culture, includeMatchedSpans, allowFuzzyMatching, allowSimpleSubstringMatching); + } + + public static PatternMatcher CreateContainerPatternMatcher( + string[] patternParts, + IReadOnlyCollection containerSplitCharacters, + CultureInfo culture = null, + bool allowFuzzyMatching = false, + bool allowSimpleSubstringMatching = false, + bool includeMatchedSpans = false) + { + return new ContainerPatternMatcher( + patternParts, containerSplitCharacters, culture, allowFuzzyMatching, allowSimpleSubstringMatching, includeMatchedSpans); + } + + internal static (string name, string containerOpt) GetNameAndContainer(string pattern) + { + var dotIndex = pattern.LastIndexOf('.'); + var containsDots = dotIndex >= 0; + return containsDots + ? (name: pattern.Substring(dotIndex + 1), containerOpt: pattern.Substring(0, dotIndex)) + : (name: pattern, containerOpt: null); + } + + public abstract PatternMatch? TryMatch(string candidate); + + private bool SkipMatch(string candidate) + => _invalidPattern || string.IsNullOrWhiteSpace(candidate); + + private StringBreaks GetWordSpans(string word) + { + lock (_gate) + { + return _stringToWordSpans.GetOrAdd(word, _breakIntoWordSpans); + } + } + + private static bool ContainsUpperCaseLetter(string pattern) + { + // Expansion of "foreach(char ch in pattern)" to avoid a CharEnumerator allocation + for (int i = 0; i < pattern.Length; i++) + { + if (char.IsUpper(pattern[i])) + { + return true; + } + } + + return false; + } + + private PatternMatch? MatchPatternChunk( + string candidate, + TextChunk patternChunk, + bool punctuationStripped, + bool fuzzyMatch, + int chunkOffset) + { + return fuzzyMatch + ? FuzzyMatchPatternChunk(candidate, patternChunk, punctuationStripped) + : NonFuzzyMatchPatternChunk(candidate, patternChunk, punctuationStripped, chunkOffset); + } + + private PatternMatch? FuzzyMatchPatternChunk( + string candidate, + TextChunk patternChunk, + bool punctuationStripped) + { + if (patternChunk.SimilarityChecker.AreSimilar(candidate)) + { + return new PatternMatch( + PatternMatchKind.Fuzzy, punctuationStripped, isCaseSensitive: false); + } + + return null; + } + + private PatternMatch? NonFuzzyMatchPatternChunk( + string candidate, + TextChunk patternChunk, + bool punctuationStripped, + int chunkOffset) + { + int caseInsensitiveIndex = _compareInfo.IndexOf(candidate, patternChunk.Text, CompareOptions.IgnoreCase); + + if (caseInsensitiveIndex == 0) + { + if (patternChunk.Text.Length == candidate.Length) + { + // a) Check if the part matches the candidate entirely, in an case insensitive or + // sensitive manner. If it does, return that there was an exact match. + return new PatternMatch( + PatternMatchKind.Exact, punctuationStripped, isCaseSensitive: candidate == patternChunk.Text, + matchedSpans: GetMatchedSpans(chunkOffset, candidate.Length)); + } + else + { + // b) Check if the part is a prefix of the candidate, in a case insensitive or sensitive + // manner. If it does, return that there was a prefix match. + return new PatternMatch( + PatternMatchKind.Prefix, punctuationStripped, isCaseSensitive: _compareInfo.IsPrefix(candidate, patternChunk.Text), + matchedSpans: GetMatchedSpans(chunkOffset, patternChunk.Text.Length)); + } + } + // b++) If the part is a case insensitive substring match, but not a prefix, and the caller + // requested simple substring matches, return that there was a substring match. + // This covers the case of non camel case naming conventions, for example matching + // 'afxsettingsstore.h' when user types 'store.h' + else if (caseInsensitiveIndex > 0 && _allowSimpleSubstringMatching) + { + return new PatternMatch( + PatternMatchKind.Substring, punctuationStripped, + isCaseSensitive: PartStartsWith( + candidate, new TextSpan(caseInsensitiveIndex, patternChunk.Text.Length), + patternChunk.Text, CompareOptions.None), + matchedSpans: GetMatchedSpans(chunkOffset + caseInsensitiveIndex, patternChunk.Text.Length)); + } + + var isLowercase = !ContainsUpperCaseLetter(patternChunk.Text); + if (isLowercase) + { + if (caseInsensitiveIndex > 0) + { + // c) If the part is entirely lowercase, then check if it is contained anywhere in the + // candidate in a case insensitive manner. If so, return that there was a substring + // match. + // + // Note: We only have a substring match if the lowercase part is prefix match of some + // word part. That way we don't match something like 'Class' when the user types 'a'. + // But we would match 'FooAttribute' (since 'Attribute' starts with 'a'). + // + // Also, if we matched at location right after punctuation, then this is a good + // substring match. i.e. if the user is testing mybutton against _myButton + // then this should hit. As we really are finding the match at the beginning of + // a word. + if (char.IsPunctuation(candidate[caseInsensitiveIndex - 1]) || + char.IsPunctuation(patternChunk.Text[0])) + { + return new PatternMatch( + PatternMatchKind.Substring, punctuationStripped, + isCaseSensitive: PartStartsWith( + candidate, new TextSpan(caseInsensitiveIndex, patternChunk.Text.Length), + patternChunk.Text, CompareOptions.None), + matchedSpans: GetMatchedSpans(chunkOffset + caseInsensitiveIndex, patternChunk.Text.Length)); + } + + var wordSpans = GetWordSpans(candidate); + for (int i = 0, n = wordSpans.GetCount(); i < n; i++) + { + var span = wordSpans[i]; + if (PartStartsWith(candidate, span, patternChunk.Text, CompareOptions.IgnoreCase)) + { + return new PatternMatch(PatternMatchKind.Substring, punctuationStripped, + isCaseSensitive: PartStartsWith(candidate, span, patternChunk.Text, CompareOptions.None), + matchedSpans: GetMatchedSpans(chunkOffset + span.Start, patternChunk.Text.Length)); + } + } + } + } + else + { + // d) If the part was not entirely lowercase, then check if it is contained in the + // candidate in a case *sensitive* manner. If so, return that there was a substring + // match. + var caseSensitiveIndex = _compareInfo.IndexOf(candidate, patternChunk.Text); + if (caseSensitiveIndex > 0) + { + return new PatternMatch( + PatternMatchKind.Substring, punctuationStripped, isCaseSensitive: true, + matchedSpans: GetMatchedSpans(chunkOffset + caseSensitiveIndex, patternChunk.Text.Length)); + } + } + + var match = TryCamelCaseMatch( + candidate, patternChunk, punctuationStripped, isLowercase, chunkOffset); + if (match.HasValue) + { + return match.Value; + } + + if (isLowercase) + { + // g) The word is all lower case. Is it a case insensitive substring of the candidate + // starting on a part boundary of the candidate? + + // We could check every character boundary start of the candidate for the pattern. + // However, that's an m * n operation in the worst case. Instead, find the first + // instance of the pattern substring, and see if it starts on a capital letter. + // It seems unlikely that the user will try to filter the list based on a substring + // that starts on a capital letter and also with a lowercase one. (Pattern: fogbar, + // Candidate: quuxfogbarFogBar). + if (patternChunk.Text.Length < candidate.Length) + { + if (caseInsensitiveIndex != -1 && char.IsUpper(candidate[caseInsensitiveIndex])) + { + return new PatternMatch( + PatternMatchKind.Substring, punctuationStripped, isCaseSensitive: false, + matchedSpans: GetMatchedSpans(chunkOffset + caseInsensitiveIndex, patternChunk.Text.Length)); + } + } + } + + return null; + } + + private ImmutableArray GetMatchedSpans(int start, int length) + => _includeMatchedSpans ? ImmutableArray.Create(new TextSpan(start, length)) : ImmutableArray.Empty; + + private static bool ContainsSpaceOrAsterisk(string text) + { + for (int i = 0; i < text.Length; i++) + { + char ch = text[i]; + if (ch == ' ' || ch == '*') + { + return true; + } + } + + return false; + } + + /// + /// Internal helper for MatchPatternInternal + /// + /// + /// PERF: Designed to minimize allocations in common cases. + /// If there's no match, then null is returned. + /// If there's a single match, or the caller only wants the first match, then it is returned (as a Nullable) + /// If there are multiple matches they are merged. + /// + /// The word being tested. + /// The segment of the pattern to check against the candidate. + /// If a fuzzy match should be performed + /// Index of segment[0] in candidate, used to merge matches together. + /// Returns a match if found. Otherwise it is null. + private PatternMatch? MatchPatternSegment( + string candidate, + PatternSegment segment, + bool fuzzyMatch, + int segmentOffset) + { + + if (fuzzyMatch && !_allowFuzzyMatching) + { + return null; + } + + // First check if the segment matches as is. This is also useful if the segment contains + // characters we would normally strip when splitting into parts that we also may want to + // match in the candidate. For example if the segment is "@int" and the candidate is + // "@int", then that will show up as an exact match here. + // + // Note: if the segment contains a space or an asterisk then we must assume that it's a + // multi-word segment. + PatternMatch? match = null; + if (!ContainsSpaceOrAsterisk(segment.TotalTextChunk.Text)) + { + match = MatchPatternChunk( + candidate, segment.TotalTextChunk, punctuationStripped: false, fuzzyMatch: fuzzyMatch, chunkOffset: segmentOffset); + if (match != null) + { + return match; + } + } + + // The logic for pattern matching is now as follows: + // + // 1) Break the segment passed in into words. Breaking is rather simple and a + // good way to think about it that if gives you all the individual alphanumeric words + // of the pattern. + // + // 2) For each word try to match the word against the candidate value. + // + // 3) Matching is as follows: + // + // a) Check if the word matches the candidate entirely, in an case insensitive or + // sensitive manner. If it does, return that there was an exact match. + // + // b) Check if the word is a prefix of the candidate, in a case insensitive or + // sensitive manner. If it does, return that there was a prefix match. + // + // c) If the word is entirely lowercase, then check if it is contained anywhere in the + // candidate in a case insensitive manner. If so, return that there was a substring + // match. + // + // Note: We only have a substring match if the lowercase part is prefix match of + // some word part. That way we don't match something like 'Class' when the user + // types 'a'. But we would match 'FooAttribute' (since 'Attribute' starts with + // 'a'). + // + // d) If the word was not entirely lowercase, then check if it is contained in the + // candidate in a case *sensitive* manner. If so, return that there was a substring + // match. + // + // e) If the word was entirely lowercase, then attempt a special lower cased camel cased + // match. i.e. cofipro would match CodeFixProvider. + // + // f) If the word was not entirely lowercase, then attempt a normal camel cased match. + // i.e. CoFiPro would match CodeFixProvider, but CofiPro would not. + // + // g) The word is all lower case. Is it a case insensitive substring of the candidate starting + // on a part boundary of the candidate? + // + // 4) Merge matches back together using the Simple strategy. + // + // Only if all words have some sort of match is the pattern considered matched. + + int chunkOffset = segmentOffset; + var subWordTextChunks = segment.SubWordTextChunks; + foreach (var subWordTextChunk in subWordTextChunks) + { + // Try to match the candidate with this word + var result = MatchPatternChunk( + candidate, subWordTextChunk, punctuationStripped: true, fuzzyMatch: fuzzyMatch, chunkOffset: chunkOffset); + if (result == null) + { + return null; + } + + match = match?.Merge(result.Value, PatternMatchMergeStrategy.Simple) ?? result.Value; + } + + return match; + } + + private static bool IsWordChar(char ch) + => char.IsLetterOrDigit(ch) || ch == '_'; + + /// + /// Do the two 'parts' match? i.e. Does the candidate part start with the pattern part? + /// + /// The candidate text + /// The span within the text + /// The pattern text + /// The span within the text + /// Options for doing the comparison (case sensitive or not) + /// True if the span identified by within starts with + /// the span identified by within . + private bool PartStartsWith(string candidate, TextSpan candidatePart, string pattern, TextSpan patternPart, CompareOptions compareOptions) + { + if (patternPart.Length > candidatePart.Length) + { + // Pattern part is longer than the candidate part. There can never be a match. + return false; + } + + return _compareInfo.Compare(candidate, candidatePart.Start, patternPart.Length, pattern, patternPart.Start, patternPart.Length, compareOptions) == 0; + } + + /// + /// Does the given part start with the given pattern? + /// + /// The candidate text + /// The span within the text + /// The pattern text + /// Options for doing the comparison (case sensitive or not) + /// True if the span identified by within starts with + private bool PartStartsWith(string candidate, TextSpan candidatePart, string pattern, CompareOptions compareOptions) + => PartStartsWith(candidate, candidatePart, pattern, new TextSpan(0, pattern.Length), compareOptions); + + private PatternMatch? TryCamelCaseMatch( + string candidate, TextChunk patternChunk, + bool punctuationStripped, bool isLowercase, + int chunkOffset) + { + if (isLowercase) + { + // e) If the word was entirely lowercase, then attempt a special lower cased camel cased + // match. i.e. cofipro would match CodeFixProvider. + var candidateParts = GetWordSpans(candidate); + var camelCaseKind = TryAllLowerCamelCaseMatch( + candidate, candidateParts, patternChunk, out var matchedSpans, chunkOffset); + if (camelCaseKind.HasValue) + { + return new PatternMatch( + camelCaseKind.Value, punctuationStripped, isCaseSensitive: false, + matchedSpans: matchedSpans); + } + } + else + { + // f) If the word was not entirely lowercase, then attempt a normal camel cased match. + // i.e. CoFiPro would match CodeFixProvider, but CofiPro would not. + if (patternChunk.CharacterSpans.GetCount() > 0) + { + var candidateHumps = GetWordSpans(candidate); + var camelCaseKind = TryUpperCaseCamelCaseMatch(candidate, candidateHumps, patternChunk, CompareOptions.None, out var matchedSpans, chunkOffset); + if (camelCaseKind.HasValue) + { + return new PatternMatch( + camelCaseKind.Value, punctuationStripped, isCaseSensitive: true, + matchedSpans: matchedSpans); + } + + camelCaseKind = TryUpperCaseCamelCaseMatch(candidate, candidateHumps, patternChunk, CompareOptions.IgnoreCase, out matchedSpans, chunkOffset); + if (camelCaseKind.HasValue) + { + return new PatternMatch( + camelCaseKind.Value, punctuationStripped, isCaseSensitive: false, + matchedSpans: matchedSpans); + } + } + } + + return null; + } + + private PatternMatchKind? TryAllLowerCamelCaseMatch( + string candidate, + StringBreaks candidateParts, + TextChunk patternChunk, + out ImmutableArray matchedSpans, + int chunkOffset) + { + var matcher = new AllLowerCamelCaseMatcher(_includeMatchedSpans, candidate, candidateParts, patternChunk); + return matcher.TryMatch(chunkOffset, out matchedSpans); + } + + private PatternMatchKind? TryUpperCaseCamelCaseMatch( + string candidate, + StringBreaks candidateHumps, + TextChunk patternChunk, + CompareOptions compareOption, + out ImmutableArray matchedSpans, + int chunkOffset) + { + var patternHumps = patternChunk.CharacterSpans; + + // Note: we may have more pattern parts than candidate parts. This is because multiple + // pattern parts may match a candidate part. For example "SiUI" against "SimpleUI". + // We'll have 3 pattern parts Si/U/I against two candidate parts Simple/UI. However, U + // and I will both match in UI. + + int currentCandidateHump = 0; + int currentPatternHump = 0; + int? firstMatch = null; + int? lastMatch = null; + bool? contiguous = null; + + var patternHumpCount = patternHumps.GetCount(); + var candidateHumpCount = candidateHumps.GetCount(); + + var matchSpans = ArrayBuilder.GetInstance(); + while (true) + { + // Let's consider our termination cases + if (currentPatternHump == patternHumpCount) + { + Contract.Requires(firstMatch.HasValue); + Contract.Requires(contiguous.HasValue); + + var matchCount = matchSpans.Count; + matchedSpans = _includeMatchedSpans + ? new NormalizedSpanCollection(matchSpans).ToImmutableArray() + : ImmutableArray.Empty; + matchSpans.Free(); + + var camelCaseResult = new CamelCaseResult( + fromStart: firstMatch == 0, + contiguous: contiguous.Value, + toEnd: lastMatch == candidateHumpCount - 1, + matchCount: matchCount, + matchedSpansInReverse: null, + chunkOffset: chunkOffset + ); + return GetCamelCaseKind(camelCaseResult, candidateHumps); + } + else if (currentCandidateHump == candidateHumpCount) + { + // No match, since we still have more of the pattern to hit + matchedSpans = ImmutableArray.Empty; + matchSpans.Free(); + return null; + } + + var candidateHump = candidateHumps[currentCandidateHump]; + bool gotOneMatchThisCandidate = false; + + // Consider the case of matching SiUI against SimpleUIElement. The candidate parts + // will be Simple/UI/Element, and the pattern parts will be Si/U/I. We'll match 'Si' + // against 'Simple' first. Then we'll match 'U' against 'UI'. However, we want to + // still keep matching pattern parts against that candidate part. + for (; currentPatternHump < patternHumpCount; currentPatternHump++) + { + var patternChunkCharacterSpan = patternHumps[currentPatternHump]; + + if (gotOneMatchThisCandidate) + { + // We've already gotten one pattern part match in this candidate. We will + // only continue trying to consume pattern parts if the last part and this + // part are both upper case. + if (!char.IsUpper(patternChunk.Text[patternHumps[currentPatternHump - 1].Start]) || + !char.IsUpper(patternChunk.Text[patternHumps[currentPatternHump].Start])) + { + break; + } + } + + if (!PartStartsWith(candidate, candidateHump, patternChunk.Text, patternChunkCharacterSpan, compareOption)) + { + break; + } + + matchSpans.Add(new TextSpan(chunkOffset + candidateHump.Start, patternChunkCharacterSpan.Length)); + gotOneMatchThisCandidate = true; + + firstMatch = firstMatch ?? currentCandidateHump; + lastMatch = currentCandidateHump; + + // If we were contiguous, then keep that value. If we weren't, then keep that + // value. If we don't know, then set the value to 'true' as an initial match is + // obviously contiguous. + contiguous = contiguous ?? true; + + candidateHump = new TextSpan(candidateHump.Start + patternChunkCharacterSpan.Length, candidateHump.Length - patternChunkCharacterSpan.Length); + } + + // Check if we matched anything at all. If we didn't, then we need to unset the + // contiguous bit if we currently had it set. + // If we haven't set the bit yet, then that means we haven't matched anything so + // far, and we don't want to change that. + if (!gotOneMatchThisCandidate && contiguous.HasValue) + { + contiguous = false; + } + + // Move onto the next candidate. + currentCandidateHump++; + } + } + } +} diff --git a/src/Text/Impl/PatternMatching/PatternMatcherFactory.cs b/src/Text/Impl/PatternMatching/PatternMatcherFactory.cs new file mode 100644 index 0000000..ccf1625 --- /dev/null +++ b/src/Text/Impl/PatternMatching/PatternMatcherFactory.cs @@ -0,0 +1,44 @@ +using System; +using System.ComponentModel.Composition; +using System.Linq; +using static Microsoft.VisualStudio.Text.PatternMatching.PatternMatcherCreationFlags; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + [Export(typeof(IPatternMatcherFactory))] + internal class PatternMatcherFactory : IPatternMatcherFactory + { + public IPatternMatcher CreatePatternMatcher(string pattern, PatternMatcherCreationOptions creationOptions) + { + if (string.IsNullOrWhiteSpace(pattern)) + { + throw new ArgumentException("A non-empty pattern is required to create a pattern matcher", nameof(pattern)); + } + + if (creationOptions == null) + { + throw new ArgumentNullException(nameof(creationOptions)); + } + + if (creationOptions.ContainerSplitCharacters == null) + { + return PatternMatcher.CreateSimplePatternMatcher( + pattern, + creationOptions.CultureInfo, + creationOptions.Flags.HasFlag(IncludeMatchedSpans), + creationOptions.Flags.HasFlag(AllowFuzzyMatching), + creationOptions.Flags.HasFlag(AllowSimpleSubstringMatching)); + } + else + { + return PatternMatcher.CreateContainerPatternMatcher( + pattern.Split(creationOptions.ContainerSplitCharacters.ToArray()), + creationOptions.ContainerSplitCharacters, + creationOptions.CultureInfo, + creationOptions.Flags.HasFlag(AllowFuzzyMatching), + creationOptions.Flags.HasFlag(AllowSimpleSubstringMatching), + creationOptions.Flags.HasFlag(IncludeMatchedSpans)); + } + } + } +} diff --git a/src/Text/Impl/PatternMatching/SimplePatternMatcher.cs b/src/Text/Impl/PatternMatching/SimplePatternMatcher.cs new file mode 100644 index 0000000..db0e83d --- /dev/null +++ b/src/Text/Impl/PatternMatching/SimplePatternMatcher.cs @@ -0,0 +1,60 @@ +// 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.Globalization; +using Microsoft.VisualStudio.Text.Utilities; +using Microsoft.VisualStudio.Utilities; +using TextSpan = Microsoft.VisualStudio.Text.Span; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + internal partial class PatternMatcher + { + private sealed partial class SimplePatternMatcher : PatternMatcher + { + private readonly PatternSegment _fullPatternSegment; + + public SimplePatternMatcher( + string pattern, + CultureInfo culture, + bool includeMatchedSpans, + bool allowFuzzyMatching, + bool allowSimpleSubstringMatching = false) + : base(includeMatchedSpans, culture, allowFuzzyMatching, allowSimpleSubstringMatching) + { + pattern = pattern.Trim(); + + _fullPatternSegment = new PatternSegment(pattern, allowFuzzyMatching); + _invalidPattern = _fullPatternSegment.IsInvalid; + } + + public override void Dispose() + { + base.Dispose(); + _fullPatternSegment.Dispose(); + } + + /// + /// Determines if a given candidate string matches under a multiple word query text, as you + /// would find in features like Navigate To. + /// + /// If this was a match, a set of match types that occurred while matching the + /// patterns. If it was not a match, it returns null. + public override PatternMatch? TryMatch(string candidate) + { + if (SkipMatch(candidate)) + { + return null; + } + + var match = MatchPatternSegment(candidate, _fullPatternSegment, fuzzyMatch: false, segmentOffset: 0); + + if (!match.HasValue && _allowFuzzyMatching) + { + match = MatchPatternSegment(candidate, _fullPatternSegment, fuzzyMatch: true, segmentOffset: 0); + } + + return match; + } + } + } +} diff --git a/src/Text/Impl/PatternMatching/StringBreaker.cs b/src/Text/Impl/PatternMatching/StringBreaker.cs new file mode 100644 index 0000000..343953c --- /dev/null +++ b/src/Text/Impl/PatternMatching/StringBreaker.cs @@ -0,0 +1,312 @@ +// 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.Generic; +using System.Diagnostics; +using Microsoft.VisualStudio.Text.Utilities; +using TextSpan = Microsoft.VisualStudio.Text.Span; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + /// + /// Values returned from routines. + /// Optimized for short strings with a handful of spans. + /// Each span is encoded in two bitfields 'gap' and 'length' and these + /// bitfields are stored in a 32-bit bitmap. + /// Falls back to a if the encoding won't work. + /// + internal partial struct StringBreaks : IDisposable + { + private readonly ArrayBuilder _spans; + private readonly EncodedSpans _encodedSpans; + + // These two values may be adjusted. The remaining constants are + // derived from them. The values are chosen to minimize the number + // of fallbacks during normal typing. With 5 total bits per span, we + // can encode up to 6 spans, each as long as 15 chars with 0 or 1 char + // gap. This is sufficient for the vast majority of framework symbols. + private const int BitsForGap = 1; + private const int BitsForLength = 4; + + private const int BitsPerEncodedSpan = BitsForGap + BitsForLength; + private const int MaxShortSpans = 32 / BitsPerEncodedSpan; + private const int MaxGap = (1 << BitsForGap) - 1; + private const int MaxLength = (1 << BitsForLength) - 1; + + public static StringBreaks Create(string text, Func spanGenerator) + { + Debug.Assert(text != null); + Debug.Assert(spanGenerator != null); + return TryEncodeSpans(text, spanGenerator, out var encodedSpans) + ? new StringBreaks(encodedSpans) + : new StringBreaks(CreateFallbackList(text, spanGenerator)); + } + + private static bool TryEncodeSpans(string text, Func spanGenerator, out EncodedSpans encodedSpans) + { + encodedSpans = default(EncodedSpans); + for (int start = 0, b = 0; start < text.Length;) + { + var span = spanGenerator(text, start); + if (span.IsEmpty) + { + // All done + break; + } + + int gap = span.Start - start; + Debug.Assert(gap >= 0, "Bad generator."); + + if (b >= MaxShortSpans || + span.Length > MaxLength || + gap > MaxGap) + { + // Too many spans, or span cannot be encoded. + return false; + } + + encodedSpans[b++] = Encode(gap, span.Length); + start = span.End; + } + + return true; + } + + private static ArrayBuilder CreateFallbackList(string text, Func spanGenerator) + { + var list = ArrayBuilder.GetInstance(); + for (int start = 0; start < text.Length;) + { + var span = spanGenerator(text, start); + if (span.IsEmpty) + { + // All done + break; + } + + Debug.Assert(span.Start >= start, "Bad generator."); + + list.Add(span); + start = span.End; + } + + return list; + } + + private StringBreaks(EncodedSpans encodedSpans) + { + _encodedSpans = encodedSpans; + _spans = null; + } + + private StringBreaks(ArrayBuilder spans) + { + _encodedSpans = default(EncodedSpans); + _spans = spans; + } + + public void Dispose() + { + _spans?.Free(); + } + + public int GetCount() + { + if (_spans != null) + { + return _spans.Count; + } + + int i; + for (i = 0; i < MaxShortSpans; i++) + { + if (_encodedSpans[i] == 0) + { + break; + } + } + + return i; + } + + public TextSpan this[int index] + { + get + { + if (index < 0) + { + throw new IndexOutOfRangeException(nameof(index)); + } + + if (_spans != null) + { + return _spans[index]; + } + + for (int i = 0, start = 0; i < MaxShortSpans; i++) + { + byte b = _encodedSpans[i]; + if (b == 0) + { + break; + } + + start += DecodeGap(b); + int length = DecodeLength(b); + if (i == index) + { + return new TextSpan(start, length); + } + + start += length; + } + + throw new IndexOutOfRangeException(nameof(index)); + } + } + + private static byte Encode(int gap, int length) + { + Debug.Assert(gap >= 0 && gap <= MaxGap); + Debug.Assert(length >= 0 && length <= MaxLength); + return unchecked((byte)((gap << BitsForLength) | length)); + } + + private static int DecodeLength(byte b) => b & MaxLength; + + private static int DecodeGap(byte b) => b >> BitsForLength; + } + + internal static class StringBreaker + { + /// + /// Breaks an identifier string into constituent parts. + /// + public static StringBreaks BreakIntoCharacterParts(string identifier) + => StringBreaks.Create(identifier, s_characterPartsGenerator); + + /// + /// Breaks an identifier string into constituent parts. + /// + public static StringBreaks BreakIntoWordParts(string identifier) + => StringBreaks.Create(identifier, s_wordPartsGenerator); + + private static readonly Func s_characterPartsGenerator = (identifier, start) => GenerateSpan(identifier, start, word: false); + + private static readonly Func s_wordPartsGenerator = (identifier, start) => GenerateSpan(identifier, start, word: true); + + public static TextSpan GenerateSpan(string identifier, int wordStart, bool word) + { + for (int i = wordStart + 1; i < identifier.Length; i++) + { + var lastIsDigit = char.IsDigit(identifier[i - 1]); + var currentIsDigit = char.IsDigit(identifier[i]); + + var transitionFromLowerToUpper = TransitionFromLowerToUpper(identifier, word, i); + var transitionFromUpperToLower = TransitionFromUpperToLower(identifier, word, i, wordStart); + + if (char.IsPunctuation(identifier[i - 1]) || + char.IsPunctuation(identifier[i]) || + lastIsDigit != currentIsDigit || + transitionFromLowerToUpper || + transitionFromUpperToLower) + { + if (!IsAllPunctuation(identifier, wordStart, i)) + { + return new TextSpan(wordStart, i - wordStart); + } + + wordStart = i; + } + } + + if (!IsAllPunctuation(identifier, wordStart, identifier.Length)) + { + return new TextSpan(wordStart, identifier.Length - wordStart); + } + + return default(TextSpan); + } + + private static bool IsAllPunctuation(string identifier, int start, int end) + { + for (int i = start; i < end; i++) + { + var ch = identifier[i]; + + // We don't consider _ as punctuation as there may be things with that name. + if (!char.IsPunctuation(ch) || ch == '_') + { + return false; + } + } + + return true; + } + + private static bool TransitionFromUpperToLower(string identifier, bool word, int index, int wordStart) + { + if (word) + { + // Cases this supports: + // 1) IDisposable -> I, Disposable + // 2) UIElement -> UI, Element + // 3) HTMLDocument -> HTML, Document + // + // etc. + if (index != wordStart && + index + 1 < identifier.Length) + { + var currentIsUpper = char.IsUpper(identifier[index]); + var nextIsLower = char.IsLower(identifier[index + 1]); + if (currentIsUpper && nextIsLower) + { + // We have a transition from an upper to a lower letter here. But we only + // want to break if all the letters that preceded are uppercase. i.e. if we + // have "Foo" we don't want to break that into "F, oo". But if we have + // "IFoo" or "UIFoo", then we want to break that into "I, Foo" and "UI, + // Foo". i.e. the last uppercase letter belongs to the lowercase letters + // that follows. Note: this will make the following not split properly: + // "HELLOthere". However, these sorts of names do not show up in .Net + // programs. + for (int i = wordStart; i < index; i++) + { + if (!char.IsUpper(identifier[i])) + { + return false; + } + } + + return true; + } + } + } + + return false; + } + + private static bool TransitionFromLowerToUpper(string identifier, bool word, int index) + { + var lastIsUpper = char.IsUpper(identifier[index - 1]); + var currentIsUpper = char.IsUpper(identifier[index]); + + // See if the casing indicates we're starting a new word. Note: if we're breaking on + // words, then just seeing an upper case character isn't enough. Instead, it has to + // be uppercase and the previous character can't be uppercase. + // + // For example, breaking "AddMetadata" on words would make: Add Metadata + // + // on characters would be: A dd M etadata + // + // Break "AM" on words would be: AM + // + // on characters would be: A M + // + // We break the search string on characters. But we break the symbol name on words. + var transition = word + ? (currentIsUpper && !lastIsUpper) + : currentIsUpper; + return transition; + } + } +} diff --git a/src/Text/Impl/PatternMatching/StringBreaks.EncodedSpans.cs b/src/Text/Impl/PatternMatching/StringBreaks.EncodedSpans.cs new file mode 100644 index 0000000..19284df --- /dev/null +++ b/src/Text/Impl/PatternMatching/StringBreaks.EncodedSpans.cs @@ -0,0 +1,30 @@ +// 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.Diagnostics; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + internal partial struct StringBreaks + { + private struct EncodedSpans + { + private const uint Mask = (1u << BitsPerEncodedSpan) - 1u; + private uint _value; + + public byte this[int index] + { + get + { + Debug.Assert(index >= 0 && index < MaxShortSpans); + return (byte)((_value >> (index * BitsPerEncodedSpan)) & Mask); + } + set + { + Debug.Assert(index >= 0 && index < MaxShortSpans); + int shift = index * BitsPerEncodedSpan; + _value = (_value & ~(Mask << shift)) | ((uint)value << shift); + } + } + } + } +} diff --git a/src/Text/Impl/PatternMatching/Utilities.cs b/src/Text/Impl/PatternMatching/Utilities.cs new file mode 100644 index 0000000..d224798 --- /dev/null +++ b/src/Text/Impl/PatternMatching/Utilities.cs @@ -0,0 +1,33 @@ +using System; +using System.Collections.Generic; +using System.Linq; +using System.Text; +using System.Threading.Tasks; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + internal static class Utilities + { + internal static V GetOrAdd(this IDictionary dictionary, K key, Func function) + { + V value; + if (!dictionary.TryGetValue(key, out value)) + { + value = function(key); + dictionary.Add(key, value); + } + + return value; + } + + internal static V GetOrAdd(this IDictionary dictionary, K key, Func function) + { + return dictionary.GetOrAdd(key, (obj) => function()); + } + + internal static bool IsWordChar(char ch, bool verbatimIdentifierPrefixIsWordCharacter) + { + return char.IsLetterOrDigit(ch) || ch == '_' || (verbatimIdentifierPrefixIsWordCharacter && ch == '@'); + } + } +} diff --git a/src/Text/Impl/PatternMatching/WordSimilarityChecker.cs b/src/Text/Impl/PatternMatching/WordSimilarityChecker.cs new file mode 100644 index 0000000..d049e6b --- /dev/null +++ b/src/Text/Impl/PatternMatching/WordSimilarityChecker.cs @@ -0,0 +1,199 @@ +using System; +using System.Collections.Generic; +using System.ComponentModel.Composition; +using System.Diagnostics; +using System.Text; +using Microsoft.VisualStudio.Text.PatternMatching; + +namespace Microsoft.VisualStudio.Text.PatternMatching.Implementation +{ + internal class WordSimilarityChecker + { + private struct CacheResult + { + public readonly string CandidateText; + public readonly bool AreSimilar; + public readonly double SimilarityWeight; + + public CacheResult(string candidate, bool areSimilar, double similarityWeight) + { + CandidateText = candidate; + AreSimilar = areSimilar; + SimilarityWeight = similarityWeight; + } + } + + // Cache the result of the last call to AreSimilar. We'll often be called with the same + // value multiple times in a row, so we can avoid expensive computation by returning the + // same value immediately. + private CacheResult _lastAreSimilarResult; + + private string _source; + private EditDistance _editDistance; + private int _threshold; + + /// + /// Whether or words should be considered similar if one is contained within the other + /// (regardless of edit distance). For example if is true then IService would be considered + /// similar to IServiceFactory despite the edit distance being quite high at 7. + /// + private bool _substringsAreSimilar; + + private static readonly object s_poolGate = new object(); + private static readonly Stack s_pool = new Stack(); + + public static WordSimilarityChecker Allocate(string text, bool substringsAreSimilar) + { + WordSimilarityChecker checker; + lock (s_poolGate) + { + checker = s_pool.Count > 0 + ? s_pool.Pop() + : new WordSimilarityChecker(); + } + + checker.Initialize(text, substringsAreSimilar); + return checker; + } + + private WordSimilarityChecker() + { + } + + private void Initialize(string text, bool substringsAreSimilar) + { + _source = text ?? throw new ArgumentNullException(nameof(text)); + _threshold = GetThreshold(_source); + _editDistance = new EditDistance(text); + _substringsAreSimilar = substringsAreSimilar; + } + + public void Free() + { + _editDistance?.Dispose(); + _source = null; + _editDistance = null; + _lastAreSimilarResult = default(CacheResult); + lock (s_poolGate) + { + s_pool.Push(this); + } + } + + public static bool AreSimilar(string originalText, string candidateText) + => AreSimilar(originalText, candidateText, substringsAreSimilar: false); + + public static bool AreSimilar(string originalText, string candidateText, bool substringsAreSimilar) + => AreSimilar(originalText, candidateText, substringsAreSimilar, out var unused); + + public static bool AreSimilar(string originalText, string candidateText, out double similarityWeight) + { + return AreSimilar( + originalText, candidateText, + substringsAreSimilar: false, similarityWeight: out similarityWeight); + } + + /// + /// Returns true if 'originalText' and 'candidateText' are likely a misspelling of each other. + /// Returns false otherwise. If it is a likely misspelling a similarityWeight is provided + /// to help rank the match. Lower costs mean it was a better match. + /// + public static bool AreSimilar(string originalText, string candidateText, bool substringsAreSimilar, out double similarityWeight) + { + var checker = Allocate(originalText, substringsAreSimilar); + var result = checker.AreSimilar(candidateText, out similarityWeight); + checker.Free(); + + return result; + } + + internal static int GetThreshold(string value) + => value.Length <= 4 ? 1 : 2; + + public bool AreSimilar(string candidateText) + => AreSimilar(candidateText, out var similarityWeight); + + public bool AreSimilar(string candidateText, out double similarityWeight) + { + if (_source.Length < 3) + { + // If we're comparing strings that are too short, we'll find + // far too many spurious hits. Don't even bother in this case. + similarityWeight = double.MaxValue; + return false; + } + + if (_lastAreSimilarResult.CandidateText == candidateText) + { + similarityWeight = _lastAreSimilarResult.SimilarityWeight; + return _lastAreSimilarResult.AreSimilar; + } + + var result = AreSimilarWorker(candidateText, out similarityWeight); + _lastAreSimilarResult = new CacheResult(candidateText, result, similarityWeight); + return result; + } + + private bool AreSimilarWorker(string candidateText, out double similarityWeight) + { + similarityWeight = double.MaxValue; + + // If the two strings differ by more characters than the cost threshold, then there's + // no point in even computing the edit distance as it would necessarily take at least + // that many additions/deletions. + if (Math.Abs(_source.Length - candidateText.Length) <= _threshold) + { + similarityWeight = _editDistance.GetEditDistance(candidateText, _threshold); + } + + if (similarityWeight > _threshold) + { + // it had a high cost. However, the string the user typed was contained + // in the string we're currently looking at. That's enough to consider it + // although we place it just at the threshold (i.e. it's worse than all + // other matches). + if (_substringsAreSimilar && candidateText.IndexOf(_source, StringComparison.OrdinalIgnoreCase) >= 0) + { + similarityWeight = _threshold; + } + else + { + return false; + } + } + + Debug.Assert(similarityWeight <= _threshold); + + similarityWeight += Penalty(candidateText, _source); + return true; + } + + private static double Penalty(string candidateText, string originalText) + { + int lengthDifference = Math.Abs(originalText.Length - candidateText.Length); + if (lengthDifference != 0) + { + // For all items of the same edit cost, we penalize those that are + // much longer than the original text versus those that are only + // a little longer. + // + // Note: even with this penalty, all matches of cost 'X' will all still + // cost less than matches of cost 'X + 1'. i.e. the penalty is in the + // range [0, 1) and only serves to order matches of the same cost. + // + // Here's the relation of the first few values of length diff and penalty: + // LengthDiff -> Penalty + // 1 -> .5 + // 2 -> .66 + // 3 -> .75 + // 4 -> .8 + // And so on and so forth. + double penalty = 1.0 - (1.0 / (lengthDifference + 1)); + return penalty; + } + + return 0; + } + } +} + -- cgit v1.2.3