|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
using System.Buffers;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Linq;
using System.Runtime.CompilerServices;
using Microsoft.AspNetCore.Http;
namespace Microsoft.AspNetCore.Routing.Matching;
/// <summary>
/// Represents a set of <see cref="Endpoint"/> candidates that have been matched
/// by the routing system. Used by implementations of <see cref="EndpointSelector"/>
/// and <see cref="IEndpointSelectorPolicy"/>.
/// </summary>
public sealed class CandidateSet
{
internal CandidateState[] Candidates;
/// <summary>
/// <para>
/// Initializes a new instances of the <see cref="CandidateSet"/> class with the provided <paramref name="endpoints"/>,
/// <paramref name="values"/>, and <paramref name="scores"/>.
/// </para>
/// <para>
/// The constructor is provided to enable unit tests of implementations of <see cref="EndpointSelector"/>
/// and <see cref="IEndpointSelectorPolicy"/>.
/// </para>
/// </summary>
/// <param name="endpoints">The list of endpoints, sorted in descending priority order.</param>
/// <param name="values">The list of <see cref="RouteValueDictionary"/> instances.</param>
/// <param name="scores">The list of endpoint scores. <see cref="CandidateState.Score"/>.</param>
public CandidateSet(Endpoint[] endpoints, RouteValueDictionary[] values, int[] scores)
{
ArgumentNullException.ThrowIfNull(endpoints);
ArgumentNullException.ThrowIfNull(values);
ArgumentNullException.ThrowIfNull(scores);
if (endpoints.Length != values.Length || endpoints.Length != scores.Length)
{
throw new ArgumentException($"The provided {nameof(endpoints)}, {nameof(values)}, and {nameof(scores)} must have the same length.");
}
Candidates = new CandidateState[endpoints.Length];
for (var i = 0; i < endpoints.Length; i++)
{
Candidates[i] = new CandidateState(endpoints[i], values[i], scores[i]);
}
}
// Used in tests.
internal CandidateSet(Candidate[] candidates)
{
Candidates = new CandidateState[candidates.Length];
for (var i = 0; i < candidates.Length; i++)
{
Candidates[i] = new CandidateState(candidates[i].Endpoint, candidates[i].Score);
}
}
internal CandidateSet(CandidateState[] candidates)
{
Candidates = candidates;
}
/// <summary>
/// Gets the count of candidates in the set.
/// </summary>
public int Count => Candidates.Length;
/// <summary>
/// Gets the <see cref="CandidateState"/> associated with the candidate <see cref="Endpoint"/>
/// at <paramref name="index"/>.
/// </summary>
/// <param name="index">The candidate index.</param>
/// <returns>
/// A reference to the <see cref="CandidateState"/>. The result is returned by reference.
/// </returns>
public ref CandidateState this[int index]
{
// Note that this is a ref-return because of performance.
// We don't want to copy these fat structs if it can be avoided.
// PERF: Force inlining
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get
{
// Friendliness for inlining
if ((uint)index >= Count)
{
ThrowIndexArgumentOutOfRangeException();
}
return ref Candidates[index];
}
}
/// <summary>
/// Gets a value which indicates where the <see cref="Http.Endpoint"/> is considered
/// a valid candidate for the current request.
/// </summary>
/// <param name="index">The candidate index.</param>
/// <returns>
/// <c>true</c> if the candidate at position <paramref name="index"/> is considered valid
/// for the current request, otherwise <c>false</c>.
/// </returns>
public bool IsValidCandidate(int index)
{
// Friendliness for inlining
if ((uint)index >= Count)
{
ThrowIndexArgumentOutOfRangeException();
}
return IsValidCandidate(ref Candidates[index]);
}
internal static bool IsValidCandidate(ref CandidateState candidate)
{
return candidate.Score >= 0;
}
/// <summary>
/// Sets the validity of the candidate at the provided index.
/// </summary>
/// <param name="index">The candidate index.</param>
/// <param name="value">
/// The value to set. If <c>true</c> the candidate is considered valid for the current request.
/// </param>
public void SetValidity(int index, bool value)
{
// Friendliness for inlining
if ((uint)index >= Count)
{
ThrowIndexArgumentOutOfRangeException();
}
ref var original = ref Candidates[index];
SetValidity(ref original, value);
}
internal static void SetValidity(ref CandidateState candidate, bool value)
{
var originalScore = candidate.Score;
var score = originalScore >= 0 ^ value ? ~originalScore : originalScore;
candidate = new CandidateState(candidate.Endpoint, candidate.Values, score);
}
/// <summary>
/// Replaces the <see cref="Endpoint"/> at the provided <paramref name="index"/> with the
/// provided <paramref name="endpoint"/>.
/// </summary>
/// <param name="index">The candidate index.</param>
/// <param name="endpoint">
/// The <see cref="Endpoint"/> to replace the original <see cref="Endpoint"/> at
/// the <paramref name="index"/>. If <paramref name="endpoint"/> is <c>null</c>. the candidate will be marked
/// as invalid.
/// </param>
/// <param name="values">
/// The <see cref="RouteValueDictionary"/> to replace the original <see cref="RouteValueDictionary"/> at
/// the <paramref name="index"/>.
/// </param>
public void ReplaceEndpoint(int index, Endpoint? endpoint, RouteValueDictionary? values)
{
// Friendliness for inlining
if ((uint)index >= Count)
{
ThrowIndexArgumentOutOfRangeException();
}
// CandidateState allows a null-valued endpoint. However a validate candidate should never have a null endpoint
// We'll make lives easier for matcher policies by declaring it as non-null.
Candidates[index] = new CandidateState(endpoint!, values, Candidates[index].Score);
if (endpoint == null)
{
SetValidity(index, false);
}
}
/// <summary>
/// Replaces the <see cref="Endpoint"/> at the provided <paramref name="index"/> with the
/// provided <paramref name="endpoints"/>.
/// </summary>
/// <param name="index">The candidate index.</param>
/// <param name="endpoints">
/// The list of endpoints <see cref="Endpoint"/> to replace the original <see cref="Endpoint"/> at
/// the <paramref name="index"/>. If <paramref name="endpoints"/> is empty, the candidate will be marked
/// as invalid.
/// </param>
/// <param name="comparer">
/// The endpoint comparer used to order the endpoints. Can be retrieved from the service provider as
/// type <see cref="EndpointMetadataComparer"/>.
/// </param>
/// <remarks>
/// <para>
/// This method supports replacing a dynamic endpoint with a collection of endpoints, and relying on
/// <see cref="IEndpointSelectorPolicy"/> implementations to disambiguate further.
/// </para>
/// <para>
/// The endpoint being replace should have a unique score value. The score is the combination of route
/// patter precedence, order, and policy metadata evaluation. A dynamic endpoint will not function
/// correctly if other endpoints exist with the same score.
/// </para>
/// </remarks>
public void ExpandEndpoint(int index, IReadOnlyList<Endpoint> endpoints, IComparer<Endpoint> comparer)
{
// Friendliness for inlining
if ((uint)index >= Count)
{
ThrowIndexArgumentOutOfRangeException();
}
if (endpoints == null)
{
ThrowArgumentNullException(nameof(endpoints));
}
if (comparer == null)
{
ThrowArgumentNullException(nameof(comparer));
}
// First we need to verify that the score of what we're replacing is unique.
ValidateUniqueScore(index);
switch (endpoints.Count)
{
case 0:
ReplaceEndpoint(index, null, null);
break;
case 1:
ReplaceEndpoint(index, endpoints[0], Candidates[index].Values);
break;
default:
var score = GetOriginalScore(index);
var values = Candidates[index].Values;
// Adding candidates requires expanding the array and computing new score values for the new candidates.
var original = Candidates;
var candidates = new CandidateState[original.Length - 1 + endpoints.Count];
Candidates = candidates;
// Since the new endpoints have an unknown ordering relationship to each other, we need to:
// - order them
// - assign scores
// - offset everything that comes after
//
// If the inputs look like:
//
// score 0: A1
// score 0: A2
// score 1: B
// score 2: C <-- being expanded
// score 3: D
//
// Then the result should look like:
//
// score 0: A1
// score 0: A2
// score 1: B
// score 2: `C1
// score 3: `C2
// score 4: D
// Candidates before index can be copied unchanged.
for (var i = 0; i < index; i++)
{
candidates[i] = original[i];
}
var buffer = endpoints.ToArray();
Array.Sort<Endpoint>(buffer, comparer);
// Add the first new endpoint with the current score
candidates[index] = new CandidateState(buffer[0], values, score);
var scoreOffset = 0;
for (var i = 1; i < buffer.Length; i++)
{
var cmp = comparer.Compare(buffer[i - 1], buffer[i]);
// This should not be possible. This would mean that sorting is wrong.
Debug.Assert(cmp <= 0);
if (cmp == 0)
{
// Score is unchanged.
}
else if (cmp < 0)
{
// Endpoint is lower priority, higher score.
scoreOffset++;
}
Candidates[i + index] = new CandidateState(buffer[i], values, score + scoreOffset);
}
for (var i = index + 1; i < original.Length; i++)
{
Candidates[i + endpoints.Count - 1] = new CandidateState(original[i].Endpoint, original[i].Values, original[i].Score + scoreOffset);
}
break;
}
}
// Returns the *positive* score value. Score is used to track valid/invalid which can cause it to be negative.
//
// This is the original score and used to determine if there are ambiguities.
private int GetOriginalScore(int index)
{
var score = Candidates[index].Score;
return score >= 0 ? score : ~score;
}
private void ValidateUniqueScore(int index)
{
var score = GetOriginalScore(index);
var count = 0;
var candidates = Candidates;
for (var i = 0; i < candidates.Length; i++)
{
if (GetOriginalScore(i) == score)
{
count++;
}
}
Debug.Assert(count > 0);
if (count > 1)
{
// Uh-oh. We don't allow duplicates with ExpandEndpoint because that will do unpredictable things.
var duplicates = new List<Endpoint>();
for (var i = 0; i < candidates.Length; i++)
{
if (GetOriginalScore(i) == score)
{
duplicates.Add(candidates[i].Endpoint!);
}
}
var message =
$"Using {nameof(ExpandEndpoint)} requires that the replaced endpoint have a unique priority. " +
$"The following endpoints were found with the same priority:" + Environment.NewLine +
string.Join(Environment.NewLine, duplicates.Select(e => e.DisplayName));
throw new InvalidOperationException(message);
}
}
[DoesNotReturn]
private static void ThrowIndexArgumentOutOfRangeException()
{
throw new ArgumentOutOfRangeException("index");
}
[DoesNotReturn]
private static void ThrowArgumentNullException(string parameter)
{
throw new ArgumentNullException(parameter);
}
}
|