Files
dotnet-bot adf899c629 Adding System.Data..., System.ServiceModel..., and System.Web...
Adding reference source for
System.Data
System.Data.DataSetExtensions
System.Data.Entity
System.Data.Entity.Design
System.Data.Linq
System.Data.SqlXml
System.ServiceModel
System.ServiceModel.Activation
System.ServiceModel.Activities
System.ServiceModel.Channels
System.ServiceModel.Discovery
System.ServiceModel.Internals
System.ServiceModel.Routing
System.ServiceModel.WasHosting
System.ServiceModel.Web
System.Web
System.Web.ApplicationServices
System.Web.DynamicData
System.Web.Entity
System.Web.Entity.Design
System.Web.Extensions
System.Web.Mobile
System.Web.Routing
System.Web.Services
System.Xml
System.Xml.Linq
2016-05-03 00:07:37 +02:00

609 lines
25 KiB
C#

//----------------------------------------------------------------
// Copyright (c) Microsoft Corporation. All rights reserved.
//----------------------------------------------------------------
namespace System
{
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Collections.Specialized;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Runtime;
using System.ServiceModel;
using System.Runtime.CompilerServices;
// this class is thread-safe
[TypeForwardedFrom("System.ServiceModel.Web, Version=3.5.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35")]
public class UriTemplateTable
{
Uri baseAddress;
string basePath;
Dictionary<string, FastPathInfo> fastPathTable; // key is uri.PathAndQuery, fastPathTable may be null
bool noTemplateHasQueryPart;
int numSegmentsInBaseAddress;
Uri originalUncanonicalizedBaseAddress;
UriTemplateTrieNode rootNode;
UriTemplatesCollection templates;
object thisLock;
bool addTrailingSlashToBaseAddress;
public UriTemplateTable()
: this(null, null, true)
{
}
public UriTemplateTable(IEnumerable<KeyValuePair<UriTemplate, object>> keyValuePairs)
: this(null, keyValuePairs, true)
{
}
public UriTemplateTable(Uri baseAddress)
: this(baseAddress, null, true)
{
}
internal UriTemplateTable(Uri baseAddress, bool addTrailingSlashToBaseAddress)
: this(baseAddress, null, addTrailingSlashToBaseAddress)
{
}
public UriTemplateTable(Uri baseAddress, IEnumerable<KeyValuePair<UriTemplate, object>> keyValuePairs)
: this(baseAddress, keyValuePairs, true)
{
}
internal UriTemplateTable(Uri baseAddress, IEnumerable<KeyValuePair<UriTemplate, object>> keyValuePairs, bool addTrailingSlashToBaseAddress)
{
if (baseAddress != null && !baseAddress.IsAbsoluteUri)
{
throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("baseAddress", SR.GetString(
SR.UTTMustBeAbsolute));
}
this.addTrailingSlashToBaseAddress = addTrailingSlashToBaseAddress;
this.originalUncanonicalizedBaseAddress = baseAddress;
if (keyValuePairs != null)
{
this.templates = new UriTemplatesCollection(keyValuePairs);
}
else
{
this.templates = new UriTemplatesCollection();
}
this.thisLock = new object();
this.baseAddress = baseAddress;
NormalizeBaseAddress();
}
public Uri BaseAddress
{
get
{
return this.baseAddress;
}
set
{
if (value == null)
{
throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("value");
}
lock (this.thisLock)
{
if (this.IsReadOnly)
{
throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(
SR.GetString(SR.UTTCannotChangeBaseAddress)));
}
else
{
if (!value.IsAbsoluteUri)
{
throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument("value", SR.GetString(
SR.UTTBaseAddressMustBeAbsolute));
}
else
{
this.originalUncanonicalizedBaseAddress = value;
this.baseAddress = value;
NormalizeBaseAddress();
}
}
}
}
}
public Uri OriginalBaseAddress
{
get
{
return this.originalUncanonicalizedBaseAddress;
}
}
public bool IsReadOnly
{
get
{
return this.templates.IsFrozen;
}
}
public IList<KeyValuePair<UriTemplate, object>> KeyValuePairs
{
get
{
return this.templates;
}
}
public void MakeReadOnly(bool allowDuplicateEquivalentUriTemplates)
{
// idempotent
lock (this.thisLock)
{
if (!this.IsReadOnly)
{
this.templates.Freeze();
Validate(allowDuplicateEquivalentUriTemplates);
ConstructFastPathTable();
}
}
}
public Collection<UriTemplateMatch> Match(Uri uri)
{
if (uri == null)
{
throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgumentNull("uri");
}
if (!uri.IsAbsoluteUri)
{
return None();
}
this.MakeReadOnly(true);
// Matching path :
Collection<String> relativeSegments;
IList<UriTemplateTableMatchCandidate> candidates;
if (!FastComputeRelativeSegmentsAndLookup(uri, out relativeSegments, out candidates))
{
return None();
}
// Matching query :
NameValueCollection queryParameters = null;
if (!this.noTemplateHasQueryPart && AtLeastOneCandidateHasQueryPart(candidates))
{
Collection<UriTemplateTableMatchCandidate> nextCandidates = new Collection<UriTemplateTableMatchCandidate>();
Fx.Assert(nextCandidates.Count == 0, "nextCandidates should be empty");
// then deal with query
queryParameters = UriTemplateHelpers.ParseQueryString(uri.Query);
bool mustBeEspeciallyInteresting = NoCandidateHasQueryLiteralRequirementsAndThereIsAnEmptyFallback(candidates);
for (int i = 0; i < candidates.Count; i++)
{
if (UriTemplateHelpers.CanMatchQueryInterestingly(candidates[i].Template, queryParameters, mustBeEspeciallyInteresting))
{
nextCandidates.Add(candidates[i]);
}
}
if (nextCandidates.Count > 1)
{
Fx.Assert(AllEquivalent(nextCandidates, 0, nextCandidates.Count), "demux algorithm problem, multiple non-equivalent matches");
}
if (nextCandidates.Count == 0)
{
for (int i = 0; i < candidates.Count; i++)
{
if (UriTemplateHelpers.CanMatchQueryTrivially(candidates[i].Template))
{
nextCandidates.Add(candidates[i]);
}
}
}
if (nextCandidates.Count == 0)
{
return None();
}
if (nextCandidates.Count > 1)
{
Fx.Assert(AllEquivalent(nextCandidates, 0, nextCandidates.Count), "demux algorithm problem, multiple non-equivalent matches");
}
candidates = nextCandidates;
}
// Verifying that we have not broken the allowDuplicates settings because of terminal defaults
// This situation can be caused when we are hosting ".../" and ".../{foo=xyz}" in the same
// table. They are not equivalent; yet they reside together in the same path partially-equivalent
// set. If we hit a uri that ends up in that particular end-of-path set, we want to provide the
// user only the 'best' match and not both; thus preventing inconsistancy between the MakeReadonly
// settings and the matching results. We will assume that the 'best' matches will be the ones with
// the smallest number of segments - this will prefer ".../" over ".../{x=1}[/...]".
if (NotAllCandidatesArePathFullyEquivalent(candidates))
{
Collection<UriTemplateTableMatchCandidate> nextCandidates = new Collection<UriTemplateTableMatchCandidate>();
int minSegmentsCount = -1;
for (int i = 0; i < candidates.Count; i++)
{
UriTemplateTableMatchCandidate candidate = candidates[i];
if (minSegmentsCount == -1)
{
minSegmentsCount = candidate.Template.segments.Count;
nextCandidates.Add(candidate);
}
else if (candidate.Template.segments.Count < minSegmentsCount)
{
minSegmentsCount = candidate.Template.segments.Count;
nextCandidates.Clear();
nextCandidates.Add(candidate);
}
else if (candidate.Template.segments.Count == minSegmentsCount)
{
nextCandidates.Add(candidate);
}
}
Fx.Assert(minSegmentsCount != -1, "At least the first entry in the list should be kept");
Fx.Assert(nextCandidates.Count >= 1, "At least the first entry in the list should be kept");
Fx.Assert(nextCandidates[0].Template.segments.Count == minSegmentsCount, "Trivial");
candidates = nextCandidates;
}
// Building the actual result
Collection<UriTemplateMatch> actualResults = new Collection<UriTemplateMatch>();
for (int i = 0; i < candidates.Count; i++)
{
UriTemplateTableMatchCandidate candidate = candidates[i];
UriTemplateMatch match = candidate.Template.CreateUriTemplateMatch(this.originalUncanonicalizedBaseAddress,
uri, candidate.Data, candidate.SegmentsCount, relativeSegments, queryParameters);
actualResults.Add(match);
}
return actualResults;
}
public UriTemplateMatch MatchSingle(Uri uri)
{
Collection<UriTemplateMatch> c = this.Match(uri);
if (c.Count == 0)
{
return null;
}
if (c.Count == 1)
{
return c[0];
}
throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new UriTemplateMatchException(SR.GetString(
SR.UTTMultipleMatches)));
}
[SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode", Justification = "This method is called within a Debug assert")]
static bool AllEquivalent(IList<UriTemplateTableMatchCandidate> list, int a, int b)
{
for (int i = a; i < b - 1; ++i)
{
if (!list[i].Template.IsPathPartiallyEquivalentAt(list[i + 1].Template, list[i].SegmentsCount))
{
return false;
}
if (!list[i].Template.IsQueryEquivalent(list[i + 1].Template))
{
return false;
}
}
return true;
}
static bool AtLeastOneCandidateHasQueryPart(IList<UriTemplateTableMatchCandidate> candidates)
{
for (int i = 0; i < candidates.Count; i++)
{
if (!UriTemplateHelpers.CanMatchQueryTrivially(candidates[i].Template))
{
return true;
}
}
return false;
}
static bool NoCandidateHasQueryLiteralRequirementsAndThereIsAnEmptyFallback(
IList<UriTemplateTableMatchCandidate> candidates)
{
bool thereIsAmEmptyFallback = false;
for (int i = 0; i < candidates.Count; i++)
{
if (UriTemplateHelpers.HasQueryLiteralRequirements(candidates[i].Template))
{
return false;
}
if (candidates[i].Template.queries.Count == 0)
{
thereIsAmEmptyFallback = true;
}
}
return thereIsAmEmptyFallback;
}
static Collection<UriTemplateMatch> None()
{
return new Collection<UriTemplateMatch>();
}
static bool NotAllCandidatesArePathFullyEquivalent(IList<UriTemplateTableMatchCandidate> candidates)
{
if (candidates.Count <= 1)
{
return false;
}
int segmentsCount = -1;
for (int i = 0; i < candidates.Count; i++)
{
if (segmentsCount == -1)
{
segmentsCount = candidates[i].Template.segments.Count;
}
else if (segmentsCount != candidates[i].Template.segments.Count)
{
return true;
}
}
return false;
}
bool ComputeRelativeSegmentsAndLookup(Uri uri,
ICollection<string> relativePathSegments, // add to this
ICollection<UriTemplateTableMatchCandidate> candidates) // matched candidates
{
string[] uriSegments = uri.Segments;
int numRelativeSegments = uriSegments.Length - this.numSegmentsInBaseAddress;
Fx.Assert(numRelativeSegments >= 0, "bad num segments");
UriTemplateLiteralPathSegment[] uSegments = new UriTemplateLiteralPathSegment[numRelativeSegments];
for (int i = 0; i < numRelativeSegments; ++i)
{
string seg = uriSegments[i + this.numSegmentsInBaseAddress];
// compute representation for matching
UriTemplateLiteralPathSegment lps = UriTemplateLiteralPathSegment.CreateFromWireData(seg);
uSegments[i] = lps;
// compute representation to project out into results
string relPathSeg = Uri.UnescapeDataString(seg);
if (lps.EndsWithSlash)
{
Fx.Assert(relPathSeg.EndsWith("/", StringComparison.Ordinal), "problem with relative path segment");
relPathSeg = relPathSeg.Substring(0, relPathSeg.Length - 1); // trim slash
}
relativePathSegments.Add(relPathSeg);
}
return rootNode.Match(uSegments, candidates);
}
void ConstructFastPathTable()
{
this.noTemplateHasQueryPart = true;
foreach (KeyValuePair<UriTemplate, object> kvp in this.templates)
{
UriTemplate ut = kvp.Key;
if (!UriTemplateHelpers.CanMatchQueryTrivially(ut))
{
this.noTemplateHasQueryPart = false;
}
if (ut.HasNoVariables && !ut.HasWildcard)
{
// eligible for fast path
if (this.fastPathTable == null)
{
this.fastPathTable = new Dictionary<string, FastPathInfo>();
}
Uri uri = ut.BindByPosition(this.originalUncanonicalizedBaseAddress);
string uriPath = UriTemplateHelpers.GetUriPath(uri);
if (this.fastPathTable.ContainsKey(uriPath))
{
// nothing to do, we've already seen it
}
else
{
FastPathInfo fpInfo = new FastPathInfo();
if (ComputeRelativeSegmentsAndLookup(uri, fpInfo.RelativePathSegments,
fpInfo.Candidates))
{
fpInfo.Freeze();
this.fastPathTable.Add(uriPath, fpInfo);
}
}
}
}
}
// this method checks the literal cache for a match if none, goes through the slower path of cracking the segments
bool FastComputeRelativeSegmentsAndLookup(Uri uri, out Collection<string> relativePathSegments,
out IList<UriTemplateTableMatchCandidate> candidates)
{
// Consider fast-path and lookup
// return false if not under base uri
string uriPath = UriTemplateHelpers.GetUriPath(uri);
FastPathInfo fpInfo = null;
if ((this.fastPathTable != null) && this.fastPathTable.TryGetValue(uriPath, out fpInfo))
{
relativePathSegments = fpInfo.RelativePathSegments;
candidates = fpInfo.Candidates;
VerifyThatFastPathAndSlowPathHaveSameResults(uri, relativePathSegments, candidates);
return true;
}
else
{
relativePathSegments = new Collection<string>();
candidates = new Collection<UriTemplateTableMatchCandidate>();
return SlowComputeRelativeSegmentsAndLookup(uri, uriPath, relativePathSegments, candidates);
}
}
void NormalizeBaseAddress()
{
if (this.baseAddress != null)
{
// ensure trailing slash on baseAddress, so that IsBaseOf will work later
UriBuilder ub = new UriBuilder(this.baseAddress);
if (this.addTrailingSlashToBaseAddress && !ub.Path.EndsWith("/", StringComparison.Ordinal))
{
ub.Path = ub.Path + "/";
}
ub.Host = "localhost"; // always normalize to localhost
ub.Port = -1;
ub.UserName = null;
ub.Password = null;
ub.Path = ub.Path.ToUpperInvariant();
ub.Scheme = Uri.UriSchemeHttp;
this.baseAddress = ub.Uri;
basePath = UriTemplateHelpers.GetUriPath(this.baseAddress);
}
}
bool SlowComputeRelativeSegmentsAndLookup(Uri uri, string uriPath, Collection<string> relativePathSegments,
ICollection<UriTemplateTableMatchCandidate> candidates)
{
// ensure 'under' the base address
if (uriPath.Length < basePath.Length)
{
return false;
}
if (!uriPath.StartsWith(basePath, StringComparison.OrdinalIgnoreCase))
{
return false;
}
else
{
// uriPath StartsWith basePath, but this check is not enough - basePath 'service1' should not match with uriPath 'service123'
// make sure that after the match the next character is /, this is to avoid a uriPath of the form /service12/ matching with a basepath of the form /service1
if (uriPath.Length > basePath.Length && !basePath.EndsWith("/", StringComparison.Ordinal) && uriPath[basePath.Length] != '/')
{
return false;
}
}
return ComputeRelativeSegmentsAndLookup(uri, relativePathSegments, candidates);
}
void Validate(bool allowDuplicateEquivalentUriTemplates)
{
if (this.baseAddress == null)
{
throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(
SR.UTTBaseAddressNotSet)));
}
this.numSegmentsInBaseAddress = this.baseAddress.Segments.Length;
if (this.templates.Count == 0)
{
throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(
SR.UTTEmptyKeyValuePairs)));
}
// build the trie and
// validate that forall Uri u, at most one UriTemplate is a best match for u
rootNode = UriTemplateTrieNode.Make(this.templates, allowDuplicateEquivalentUriTemplates);
}
[Conditional("DEBUG")]
void VerifyThatFastPathAndSlowPathHaveSameResults(Uri uri, Collection<string> fastPathRelativePathSegments,
IList<UriTemplateTableMatchCandidate> fastPathCandidates)
{
Collection<string> slowPathRelativePathSegments = new Collection<string>();
List<UriTemplateTableMatchCandidate> slowPathCandidates = new List<UriTemplateTableMatchCandidate>();
if (!SlowComputeRelativeSegmentsAndLookup(uri, UriTemplateHelpers.GetUriPath(uri),
slowPathRelativePathSegments, slowPathCandidates))
{
Fx.Assert("fast path yielded a result but slow path yielded no result");
}
// compare results
if (fastPathRelativePathSegments.Count != slowPathRelativePathSegments.Count)
{
Fx.Assert("fast path yielded different number of segments from slow path");
}
for (int i = 0; i < fastPathRelativePathSegments.Count; ++i)
{
if (fastPathRelativePathSegments[i] != slowPathRelativePathSegments[i])
{
Fx.Assert("fast path yielded different segments from slow path");
}
}
if (fastPathCandidates.Count != slowPathCandidates.Count)
{
Fx.Assert("fast path yielded different number of candidates from slow path");
}
for (int i = 0; i < fastPathCandidates.Count; i++)
{
if (!slowPathCandidates.Contains(fastPathCandidates[i]))
{
Fx.Assert("fast path yielded different candidates from slow path");
}
}
}
class FastPathInfo
{
FreezableCollection<UriTemplateTableMatchCandidate> candidates;
FreezableCollection<string> relativePathSegments;
public FastPathInfo()
{
this.relativePathSegments = new FreezableCollection<string>();
this.candidates = new FreezableCollection<UriTemplateTableMatchCandidate>();
}
public Collection<UriTemplateTableMatchCandidate> Candidates
{
get
{
return this.candidates;
}
}
public Collection<string> RelativePathSegments
{
get
{
return this.relativePathSegments;
}
}
public void Freeze()
{
this.relativePathSegments.Freeze();
this.candidates.Freeze();
}
}
class UriTemplatesCollection : FreezableCollection<KeyValuePair<UriTemplate, object>>
{
public UriTemplatesCollection()
: base()
{
}
[SuppressMessage("Microsoft.Usage", "CA2214:DoNotCallOverridableMethodsInConstructors", Justification = "This is a private class; virtual methods cannot be overriden")]
public UriTemplatesCollection(IEnumerable<KeyValuePair<UriTemplate, object>> keyValuePairs)
: base()
{
foreach (KeyValuePair<UriTemplate, object> kvp in keyValuePairs)
{
ThrowIfInvalid(kvp.Key, "keyValuePairs");
base.Add(kvp);
}
}
protected override void InsertItem(int index, KeyValuePair<UriTemplate, object> item)
{
ThrowIfInvalid(item.Key, "item");
base.InsertItem(index, item);
}
protected override void SetItem(int index, KeyValuePair<UriTemplate, object> item)
{
ThrowIfInvalid(item.Key, "item");
base.SetItem(index, item);
}
static void ThrowIfInvalid(UriTemplate template, string argName)
{
if (template == null)
{
throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument(argName,
SR.GetString(SR.UTTNullTemplateKey));
}
if (template.IgnoreTrailingSlash)
{
throw DiagnosticUtility.ExceptionUtility.ThrowHelperArgument(argName,
SR.GetString(SR.UTTInvalidTemplateKey, template));
}
}
}
}
}