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

807 lines
38 KiB
C#

//----------------------------------------------------------------
// Copyright (c) Microsoft Corporation. All rights reserved.
//----------------------------------------------------------------
namespace System
{
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Runtime;
using System.ServiceModel;
class UriTemplateTrieNode
{
int depth; // relative segment depth (root = 0)
UriTemplatePathPartiallyEquivalentSet endOfPath; // matches the non-existent segment at the end of a slash-terminated path
AscendingSortedCompoundSegmentsCollection<UriTemplatePathPartiallyEquivalentSet> finalCompoundSegment; // matches e.g. "{var}.{var}"
Dictionary<UriTemplateLiteralPathSegment, UriTemplatePathPartiallyEquivalentSet> finalLiteralSegment; // matches e.g. "segmentThatDoesntEndInSlash"
UriTemplatePathPartiallyEquivalentSet finalVariableSegment; // matches e.g. "{var}"
AscendingSortedCompoundSegmentsCollection<UriTemplateTrieLocation> nextCompoundSegment; // all are AfterLiteral; matches e.g. "{var}.{var}/"
Dictionary<UriTemplateLiteralPathSegment, UriTemplateTrieLocation> nextLiteralSegment; // all are BeforeLiteral; matches e.g. "path/"
UriTemplateTrieLocation nextVariableSegment; // is BeforeLiteral; matches e.g. "{var}/"
UriTemplateTrieLocation onFailure; // points to parent, at 'after me'
UriTemplatePathPartiallyEquivalentSet star; // matches any "extra/path/segments" at the end
UriTemplateTrieNode(int depth)
{
this.depth = depth;
this.nextLiteralSegment = null;
this.nextCompoundSegment = null;
this.finalLiteralSegment = null;
this.finalCompoundSegment = null;
this.finalVariableSegment = new UriTemplatePathPartiallyEquivalentSet(depth + 1);
this.star = new UriTemplatePathPartiallyEquivalentSet(depth);
this.endOfPath = new UriTemplatePathPartiallyEquivalentSet(depth);
}
public static UriTemplateTrieNode Make(IEnumerable<KeyValuePair<UriTemplate, object>> keyValuePairs,
bool allowDuplicateEquivalentUriTemplates)
{
// given a UTT at MakeReadOnly time, build the trie
// note that root.onFailure == null;
UriTemplateTrieNode root = new UriTemplateTrieNode(0);
foreach (KeyValuePair<UriTemplate, object> kvp in keyValuePairs)
{
Add(root, kvp);
}
Validate(root, allowDuplicateEquivalentUriTemplates);
return root;
}
public bool Match(UriTemplateLiteralPathSegment[] wireData, ICollection<UriTemplateTableMatchCandidate> candidates)
{
UriTemplateTrieLocation currentLocation = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.BeforeLiteral);
return GetMatch(currentLocation, wireData, candidates);
}
static void Add(UriTemplateTrieNode root, KeyValuePair<UriTemplate, object> kvp)
{
// Currently UTT doesn't support teplates with ignoreTrailingSlash == true; thus we
// don't care about supporting it in the trie as well.
UriTemplateTrieNode current = root;
UriTemplate ut = kvp.Key;
bool needProcessingOnFinalNode = ((ut.segments.Count == 0) || ut.HasWildcard ||
ut.segments[ut.segments.Count - 1].EndsWithSlash);
for (int i = 0; i < ut.segments.Count; ++i)
{
if (i >= ut.firstOptionalSegment)
{
current.endOfPath.Items.Add(kvp);
}
UriTemplatePathSegment ps = ut.segments[i];
if (!ps.EndsWithSlash)
{
Fx.Assert(i == ut.segments.Count - 1, "only the last segment can !EndsWithSlash");
Fx.Assert(!ut.HasWildcard, "path star cannot have !EndsWithSlash");
switch (ps.Nature)
{
case UriTemplatePartType.Literal:
current.AddFinalLiteralSegment(ps as UriTemplateLiteralPathSegment, kvp);
break;
case UriTemplatePartType.Compound:
current.AddFinalCompoundSegment(ps as UriTemplateCompoundPathSegment, kvp);
break;
case UriTemplatePartType.Variable:
current.finalVariableSegment.Items.Add(kvp);
break;
default:
Fx.Assert("Invalid value as PathSegment.Nature");
break;
}
}
else
{
Fx.Assert(ps.EndsWithSlash, "ps.EndsWithSlash");
switch (ps.Nature)
{
case UriTemplatePartType.Literal:
current = current.AddNextLiteralSegment(ps as UriTemplateLiteralPathSegment);
break;
case UriTemplatePartType.Compound:
current = current.AddNextCompoundSegment(ps as UriTemplateCompoundPathSegment);
break;
case UriTemplatePartType.Variable:
current = current.AddNextVariableSegment();
break;
default:
Fx.Assert("Invalid value as PathSegment.Nature");
break;
}
}
}
if (needProcessingOnFinalNode)
{
// if the last segment ended in a slash, there is still more to do
if (ut.HasWildcard)
{
// e.g. "path1/path2/*"
current.star.Items.Add(kvp);
}
else
{
// e.g. "path1/path2/"
current.endOfPath.Items.Add(kvp);
}
}
}
static bool CheckMultipleMatches(IList<IList<UriTemplateTrieLocation>> locationsSet, UriTemplateLiteralPathSegment[] wireData,
ICollection<UriTemplateTableMatchCandidate> candidates)
{
bool result = false;
for (int i = 0; ((i < locationsSet.Count) && !result); i++)
{
for (int j = 0; j < locationsSet[i].Count; j++)
{
if (GetMatch(locationsSet[i][j], wireData, candidates))
{
result = true;
}
}
}
return result;
}
static bool GetMatch(UriTemplateTrieLocation location, UriTemplateLiteralPathSegment[] wireData,
ICollection<UriTemplateTableMatchCandidate> candidates)
{
int initialDepth = location.node.depth;
SingleLocationOrLocationsSet nextStep;
UriTemplatePathPartiallyEquivalentSet answer;
do
{
if (TryMatch(wireData, location, out answer, out nextStep))
{
if (answer != null)
{
for (int i = 0; i < answer.Items.Count; i++)
{
candidates.Add(new UriTemplateTableMatchCandidate(answer.Items[i].Key, answer.SegmentsCount,
answer.Items[i].Value));
}
}
return true;
}
if (nextStep.IsSingle)
{
location = nextStep.SingleLocation;
}
else
{
Fx.Assert(nextStep.LocationsSet != null, "This should be set to a valid value by TryMatch");
if (CheckMultipleMatches(nextStep.LocationsSet, wireData, candidates))
{
return true;
}
location = GetFailureLocationFromLocationsSet(nextStep.LocationsSet);
}
} while ((location != null) && (location.node.depth >= initialDepth));
// we walked the whole trie down and found nothing
return false;
}
static bool TryMatch(UriTemplateLiteralPathSegment[] wireUriSegments, UriTemplateTrieLocation currentLocation,
out UriTemplatePathPartiallyEquivalentSet success, out SingleLocationOrLocationsSet nextStep)
{
// if returns true, success is set to answer
// if returns false, nextStep is set to next place to look
success = null;
nextStep = new SingleLocationOrLocationsSet();
if (wireUriSegments.Length <= currentLocation.node.depth)
{
Fx.Assert(wireUriSegments.Length == 0 || wireUriSegments[wireUriSegments.Length - 1].EndsWithSlash,
"we should not have traversed this deep into the trie unless the wire path ended in a slash");
if (currentLocation.node.endOfPath.Items.Count != 0)
{
// exact match of e.g. "path1/path2/"
success = currentLocation.node.endOfPath;
return true;
}
else if (currentLocation.node.star.Items.Count != 0)
{
// inexact match of e.g. WIRE("path1/path2/") against TEMPLATE("path1/path2/*")
success = currentLocation.node.star;
return true;
}
else
{
nextStep = new SingleLocationOrLocationsSet(currentLocation.node.onFailure);
return false;
}
}
else
{
UriTemplateLiteralPathSegment curWireSeg = wireUriSegments[currentLocation.node.depth];
bool considerLiteral = false;
bool considerCompound = false;
bool considerVariable = false;
bool considerStar = false;
switch (currentLocation.locationWithin)
{
case UriTemplateTrieIntraNodeLocation.BeforeLiteral:
considerLiteral = true;
considerCompound = true;
considerVariable = true;
considerStar = true;
break;
case UriTemplateTrieIntraNodeLocation.AfterLiteral:
considerLiteral = false;
considerCompound = true;
considerVariable = true;
considerStar = true;
break;
case UriTemplateTrieIntraNodeLocation.AfterCompound:
considerLiteral = false;
considerCompound = false;
considerVariable = true;
considerStar = true;
break;
case UriTemplateTrieIntraNodeLocation.AfterVariable:
considerLiteral = false;
considerCompound = false;
considerVariable = false;
considerStar = true;
break;
default:
Fx.Assert("bad kind");
break;
}
if (curWireSeg.EndsWithSlash)
{
IList<IList<UriTemplateTrieLocation>> compoundLocationsSet;
if (considerLiteral && currentLocation.node.nextLiteralSegment != null &&
currentLocation.node.nextLiteralSegment.ContainsKey(curWireSeg))
{
nextStep = new SingleLocationOrLocationsSet(currentLocation.node.nextLiteralSegment[curWireSeg]);
return false;
}
else if (considerCompound && currentLocation.node.nextCompoundSegment != null &&
AscendingSortedCompoundSegmentsCollection<UriTemplateTrieLocation>.Lookup(currentLocation.node.nextCompoundSegment, curWireSeg, out compoundLocationsSet))
{
nextStep = new SingleLocationOrLocationsSet(compoundLocationsSet);
return false;
}
else if (considerVariable && currentLocation.node.nextVariableSegment != null &&
!curWireSeg.IsNullOrEmpty())
{
nextStep = new SingleLocationOrLocationsSet(currentLocation.node.nextVariableSegment);
return false;
}
else if (considerStar && currentLocation.node.star.Items.Count != 0)
{
// matches e.g. WIRE("path1/path2/path3") and TEMPLATE("path1/*")
success = currentLocation.node.star;
return true;
}
else
{
nextStep = new SingleLocationOrLocationsSet(currentLocation.node.onFailure);
return false;
}
}
else
{
IList<IList<UriTemplatePathPartiallyEquivalentSet>> compoundPathEquivalentSets;
Fx.Assert(!curWireSeg.EndsWithSlash, "!curWireSeg.EndsWithSlash");
Fx.Assert(!curWireSeg.IsNullOrEmpty(), "!curWireSeg.IsNullOrEmpty()");
if (considerLiteral && currentLocation.node.finalLiteralSegment != null &&
currentLocation.node.finalLiteralSegment.ContainsKey(curWireSeg))
{
// matches e.g. WIRE("path1/path2") and TEMPLATE("path1/path2")
success = currentLocation.node.finalLiteralSegment[curWireSeg];
return true;
}
else if (considerCompound && currentLocation.node.finalCompoundSegment != null &&
AscendingSortedCompoundSegmentsCollection<UriTemplatePathPartiallyEquivalentSet>.Lookup(currentLocation.node.finalCompoundSegment, curWireSeg, out compoundPathEquivalentSets))
{
// matches e.g. WIRE("path1/path2") and TEMPLATE("path1/p{var}th2")
// we should take only the highest order match!
Fx.Assert(compoundPathEquivalentSets.Count >= 1, "Lookup is expected to return false otherwise");
Fx.Assert(compoundPathEquivalentSets[0].Count > 0, "Find shouldn't return empty sublists");
if (compoundPathEquivalentSets[0].Count == 1)
{
success = compoundPathEquivalentSets[0][0];
}
else
{
success = new UriTemplatePathPartiallyEquivalentSet(currentLocation.node.depth + 1);
for (int i = 0; i < compoundPathEquivalentSets[0].Count; i++)
{
success.Items.AddRange(compoundPathEquivalentSets[0][i].Items);
}
}
return true;
}
else if (considerVariable && currentLocation.node.finalVariableSegment.Items.Count != 0)
{
// matches e.g. WIRE("path1/path2") and TEMPLATE("path1/{var}")
success = currentLocation.node.finalVariableSegment;
return true;
}
else if (considerStar && currentLocation.node.star.Items.Count != 0)
{
// matches e.g. WIRE("path1/path2") and TEMPLATE("path1/*")
success = currentLocation.node.star;
return true;
}
else
{
nextStep = new SingleLocationOrLocationsSet(currentLocation.node.onFailure);
return false;
}
}
}
}
static UriTemplateTrieLocation GetFailureLocationFromLocationsSet(IList<IList<UriTemplateTrieLocation>> locationsSet)
{
Fx.Assert(locationsSet != null, "Shouldn't be called on null set");
Fx.Assert(locationsSet.Count > 0, "Shouldn't be called on empty set");
Fx.Assert(locationsSet[0] != null, "Shouldn't be called on a set with null sub-lists");
Fx.Assert(locationsSet[0].Count > 0, "Shouldn't be called on a set with empty sub-lists");
return locationsSet[0][0].node.onFailure;
}
static void Validate(UriTemplateTrieNode root, bool allowDuplicateEquivalentUriTemplates)
{
// walk the entire tree, and ensure that each PathEquivalentSet is ok (no ambiguous queries),
// verify thst compound segments didn't add potentialy multiple matchs;
// also Assert various data-structure invariants
Queue<UriTemplateTrieNode> nodesQueue = new Queue<UriTemplateTrieNode>();
UriTemplateTrieNode current = root;
while (true)
{
// validate all the PathEquivalentSets that live in this node
Validate(current.endOfPath, allowDuplicateEquivalentUriTemplates);
Validate(current.finalVariableSegment, allowDuplicateEquivalentUriTemplates);
Validate(current.star, allowDuplicateEquivalentUriTemplates);
if (current.finalLiteralSegment != null)
{
foreach (KeyValuePair<UriTemplateLiteralPathSegment, UriTemplatePathPartiallyEquivalentSet> kvp in current.finalLiteralSegment)
{
Validate(kvp.Value, allowDuplicateEquivalentUriTemplates);
}
}
if (current.finalCompoundSegment != null)
{
IList<IList<UriTemplatePathPartiallyEquivalentSet>> pesLists = current.finalCompoundSegment.Values;
for (int i = 0; i < pesLists.Count; i++)
{
if (!allowDuplicateEquivalentUriTemplates && (pesLists[i].Count > 1))
{
throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(
SR.UTTDuplicate, pesLists[i][0].Items[0].Key.ToString(), pesLists[i][1].Items[0].Key.ToString())));
}
for (int j = 0; j < pesLists[i].Count; j++)
{
Validate(pesLists[i][j], allowDuplicateEquivalentUriTemplates);
}
}
}
// deal with children of this node
if (current.nextLiteralSegment != null)
{
foreach (KeyValuePair<UriTemplateLiteralPathSegment, UriTemplateTrieLocation> kvp in current.nextLiteralSegment)
{
Fx.Assert(kvp.Value.locationWithin == UriTemplateTrieIntraNodeLocation.BeforeLiteral, "forward-pointers should always point to a BeforeLiteral location");
Fx.Assert(kvp.Value.node.depth == current.depth + 1, "kvp.Value.node.depth == current.depth + 1");
Fx.Assert(kvp.Value.node.onFailure.node == current, "back pointer should point back to here");
Fx.Assert(kvp.Value.node.onFailure.locationWithin == UriTemplateTrieIntraNodeLocation.AfterLiteral, "back-pointer should be AfterLiteral");
nodesQueue.Enqueue(kvp.Value.node);
}
}
if (current.nextCompoundSegment != null)
{
IList<IList<UriTemplateTrieLocation>> locations = current.nextCompoundSegment.Values;
for (int i = 0; i < locations.Count; i++)
{
if (!allowDuplicateEquivalentUriTemplates && (locations[i].Count > 1))
{
// In the future we might ease up the restrictions and verify if there is realy
// a potential multiple match here; for now we are throwing.
UriTemplate firstTemplate = FindAnyUriTemplate(locations[i][0].node);
UriTemplate secondTemplate = FindAnyUriTemplate(locations[i][1].node);
throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.GetString(
SR.UTTDuplicate, firstTemplate.ToString(), secondTemplate.ToString())));
}
for (int j = 0; j < locations[i].Count; j++)
{
UriTemplateTrieLocation location = locations[i][j];
Fx.Assert(location.locationWithin == UriTemplateTrieIntraNodeLocation.BeforeLiteral, "forward-pointers should always point to a BeforeLiteral location");
Fx.Assert(location.node.depth == current.depth + 1, "kvp.Value.node.depth == current.depth + 1");
Fx.Assert(location.node.onFailure.node == current, "back pointer should point back to here");
Fx.Assert(location.node.onFailure.locationWithin == UriTemplateTrieIntraNodeLocation.AfterCompound, "back-pointer should be AfterCompound");
nodesQueue.Enqueue(location.node);
}
}
}
if (current.nextVariableSegment != null)
{
Fx.Assert(current.nextVariableSegment.locationWithin == UriTemplateTrieIntraNodeLocation.BeforeLiteral, "forward-pointers should always point to a BeforeLiteral location");
Fx.Assert(current.nextVariableSegment.node.depth == current.depth + 1, "current.nextVariableSegment.node.depth == current.depth + 1");
Fx.Assert(current.nextVariableSegment.node.onFailure.node == current, "back pointer should point back to here");
Fx.Assert(current.nextVariableSegment.node.onFailure.locationWithin == UriTemplateTrieIntraNodeLocation.AfterVariable, "back-pointer should be AfterVariable");
nodesQueue.Enqueue(current.nextVariableSegment.node);
}
// move on to next bit of work
if (nodesQueue.Count == 0)
{
break;
}
current = nodesQueue.Dequeue();
}
}
static void Validate(UriTemplatePathPartiallyEquivalentSet pes, bool allowDuplicateEquivalentUriTemplates)
{
// A set with 0 or 1 items is valid by definition
if (pes.Items.Count < 2)
{
return;
}
// Assert all paths are partially-equivalent
for (int i = 0; i < pes.Items.Count - 1; ++i)
{
Fx.Assert(pes.Items[i].Key.IsPathPartiallyEquivalentAt(pes.Items[i + 1].Key, pes.SegmentsCount),
"all elements of a PES must be path partially-equivalent");
}
// We will check that the queries disambiguate only for templates, which are
// matched completely at the segments count; templates, which are match at
// that point due to terminal defaults, will be ruled out.
UriTemplate[] a = new UriTemplate[pes.Items.Count];
int arrayIndex = 0;
foreach (KeyValuePair<UriTemplate, object> kvp in pes.Items)
{
if (pes.SegmentsCount < kvp.Key.segments.Count)
{
continue;
}
Fx.Assert(arrayIndex < a.Length, "We made enough room for all the items");
a[arrayIndex++] = kvp.Key;
}
// Ensure that queries disambiguate (if needed) :
if (arrayIndex > 0)
{
UriTemplateHelpers.DisambiguateSamePath(a, 0, arrayIndex, allowDuplicateEquivalentUriTemplates);
}
}
static UriTemplate FindAnyUriTemplate(UriTemplateTrieNode node)
{
while (node != null)
{
if (node.endOfPath.Items.Count > 0)
{
return node.endOfPath.Items[0].Key;
}
if (node.finalVariableSegment.Items.Count > 0)
{
return node.finalVariableSegment.Items[0].Key;
}
if (node.star.Items.Count > 0)
{
return node.star.Items[0].Key;
}
if (node.finalLiteralSegment != null)
{
UriTemplatePathPartiallyEquivalentSet pes =
GetAnyDictionaryValue<UriTemplatePathPartiallyEquivalentSet>(node.finalLiteralSegment);
Fx.Assert(pes.Items.Count > 0, "Otherwise, why creating the dictionary?");
return pes.Items[0].Key;
}
if (node.finalCompoundSegment != null)
{
UriTemplatePathPartiallyEquivalentSet pes = node.finalCompoundSegment.GetAnyValue();
Fx.Assert(pes.Items.Count > 0, "Otherwise, why creating the collection?");
return pes.Items[0].Key;
}
if (node.nextLiteralSegment != null)
{
UriTemplateTrieLocation location =
GetAnyDictionaryValue<UriTemplateTrieLocation>(node.nextLiteralSegment);
node = location.node;
}
else if (node.nextCompoundSegment != null)
{
UriTemplateTrieLocation location = node.nextCompoundSegment.GetAnyValue();
node = location.node;
}
else if (node.nextVariableSegment != null)
{
node = node.nextVariableSegment.node;
}
else
{
node = null;
}
}
Fx.Assert("How did we got here without finding a UriTemplate earlier?");
return null;
}
static T GetAnyDictionaryValue<T>(IDictionary<UriTemplateLiteralPathSegment, T> dictionary)
{
using (IEnumerator<T> valuesEnumerator = dictionary.Values.GetEnumerator())
{
valuesEnumerator.MoveNext();
return valuesEnumerator.Current;
}
}
void AddFinalCompoundSegment(UriTemplateCompoundPathSegment cps, KeyValuePair<UriTemplate, object> kvp)
{
Fx.Assert(cps != null, "must be - based on the segment nature");
if (this.finalCompoundSegment == null)
{
this.finalCompoundSegment = new AscendingSortedCompoundSegmentsCollection<UriTemplatePathPartiallyEquivalentSet>();
}
UriTemplatePathPartiallyEquivalentSet pes = this.finalCompoundSegment.Find(cps);
if (pes == null)
{
pes = new UriTemplatePathPartiallyEquivalentSet(this.depth + 1);
this.finalCompoundSegment.Add(cps, pes);
}
pes.Items.Add(kvp);
}
void AddFinalLiteralSegment(UriTemplateLiteralPathSegment lps, KeyValuePair<UriTemplate, object> kvp)
{
Fx.Assert(lps != null, "must be - based on the segment nature");
if (this.finalLiteralSegment != null && this.finalLiteralSegment.ContainsKey(lps))
{
this.finalLiteralSegment[lps].Items.Add(kvp);
}
else
{
if (this.finalLiteralSegment == null)
{
this.finalLiteralSegment = new Dictionary<UriTemplateLiteralPathSegment, UriTemplatePathPartiallyEquivalentSet>();
}
UriTemplatePathPartiallyEquivalentSet pes = new UriTemplatePathPartiallyEquivalentSet(this.depth + 1);
pes.Items.Add(kvp);
this.finalLiteralSegment.Add(lps, pes);
}
}
UriTemplateTrieNode AddNextCompoundSegment(UriTemplateCompoundPathSegment cps)
{
Fx.Assert(cps != null, "must be - based on the segment nature");
if (this.nextCompoundSegment == null)
{
this.nextCompoundSegment = new AscendingSortedCompoundSegmentsCollection<UriTemplateTrieLocation>();
}
UriTemplateTrieLocation nextLocation = this.nextCompoundSegment.Find(cps);
if (nextLocation == null)
{
UriTemplateTrieNode nextNode = new UriTemplateTrieNode(this.depth + 1);
nextNode.onFailure = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.AfterCompound);
nextLocation = new UriTemplateTrieLocation(nextNode, UriTemplateTrieIntraNodeLocation.BeforeLiteral);
this.nextCompoundSegment.Add(cps, nextLocation);
}
return nextLocation.node;
}
UriTemplateTrieNode AddNextLiteralSegment(UriTemplateLiteralPathSegment lps)
{
Fx.Assert(lps != null, "must be - based on the segment nature");
if (this.nextLiteralSegment != null && this.nextLiteralSegment.ContainsKey(lps))
{
return this.nextLiteralSegment[lps].node;
}
else
{
if (this.nextLiteralSegment == null)
{
this.nextLiteralSegment = new Dictionary<UriTemplateLiteralPathSegment, UriTemplateTrieLocation>();
}
UriTemplateTrieNode newNode = new UriTemplateTrieNode(this.depth + 1);
newNode.onFailure = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.AfterLiteral);
this.nextLiteralSegment.Add(lps, new UriTemplateTrieLocation(newNode, UriTemplateTrieIntraNodeLocation.BeforeLiteral));
return newNode;
}
}
UriTemplateTrieNode AddNextVariableSegment()
{
if (this.nextVariableSegment != null)
{
return this.nextVariableSegment.node;
}
else
{
UriTemplateTrieNode newNode = new UriTemplateTrieNode(this.depth + 1);
newNode.onFailure = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.AfterVariable);
this.nextVariableSegment = new UriTemplateTrieLocation(newNode, UriTemplateTrieIntraNodeLocation.BeforeLiteral);
return newNode;
}
}
struct SingleLocationOrLocationsSet
{
readonly bool isSingle;
readonly IList<IList<UriTemplateTrieLocation>> locationsSet;
readonly UriTemplateTrieLocation singleLocation;
public SingleLocationOrLocationsSet(UriTemplateTrieLocation singleLocation)
{
this.isSingle = true;
this.singleLocation = singleLocation;
this.locationsSet = null;
}
public SingleLocationOrLocationsSet(IList<IList<UriTemplateTrieLocation>> locationsSet)
{
this.isSingle = false;
this.singleLocation = null;
this.locationsSet = locationsSet;
}
public bool IsSingle
{
get
{
return this.isSingle;
}
}
public IList<IList<UriTemplateTrieLocation>> LocationsSet
{
get
{
Fx.Assert(!this.isSingle, "!this.isSingle");
return this.locationsSet;
}
}
public UriTemplateTrieLocation SingleLocation
{
get
{
Fx.Assert(this.isSingle, "this.isSingle");
return this.singleLocation;
}
}
}
class AscendingSortedCompoundSegmentsCollection<T>
where T : class
{
SortedList<UriTemplateCompoundPathSegment, Collection<CollectionItem>> items;
public AscendingSortedCompoundSegmentsCollection()
{
this.items = new SortedList<UriTemplateCompoundPathSegment, Collection<AscendingSortedCompoundSegmentsCollection<T>.CollectionItem>>();
}
public IList<IList<T>> Values
{
get
{
IList<IList<T>> results = new List<IList<T>>(this.items.Count);
for (int i = 0; i < this.items.Values.Count; i++)
{
results.Add(new List<T>(this.items.Values[i].Count));
Fx.Assert(results.Count == i + 1, "We are adding item for each values collection");
for (int j = 0; j < this.items.Values[i].Count; j++)
{
results[i].Add(this.items.Values[i][j].Value);
Fx.Assert(results[i].Count == j + 1, "We are adding item for each value in the collection");
}
Fx.Assert(results[i].Count == this.items.Values[i].Count, "We were supposed to add an item for each value in the collection");
}
Fx.Assert(results.Count == this.items.Values.Count, "We were supposed to add a sub-list for each values collection");
return results;
}
}
public void Add(UriTemplateCompoundPathSegment segment, T value)
{
int index = this.items.IndexOfKey(segment);
if (index == -1)
{
Collection<CollectionItem> subItems = new Collection<CollectionItem>();
subItems.Add(new CollectionItem(segment, value));
this.items.Add(segment, subItems);
}
else
{
Collection<CollectionItem> subItems = this.items.Values[index];
subItems.Add(new CollectionItem(segment, value));
}
}
public T Find(UriTemplateCompoundPathSegment segment)
{
int index = this.items.IndexOfKey(segment);
if (index == -1)
{
return null;
}
Collection<CollectionItem> subItems = this.items.Values[index];
for (int i = 0; i < subItems.Count; i++)
{
if (subItems[i].Segment.IsEquivalentTo(segment, false))
{
return subItems[i].Value;
}
}
return null;
}
public IList<IList<T>> Find(UriTemplateLiteralPathSegment wireData)
{
IList<IList<T>> results = new List<IList<T>>();
for (int i = 0; i < this.items.Values.Count; i++)
{
List<T> sameOrderResults = null;
for (int j = 0; j < this.items.Values[i].Count; j++)
{
if (this.items.Values[i][j].Segment.IsMatch(wireData))
{
if (sameOrderResults == null)
{
sameOrderResults = new List<T>();
}
sameOrderResults.Add(this.items.Values[i][j].Value);
}
}
if (sameOrderResults != null)
{
results.Add(sameOrderResults);
}
}
return results;
}
public T GetAnyValue()
{
if (this.items.Values.Count > 0)
{
Fx.Assert(this.items.Values[0].Count > 0, "We are not adding a sub-list unless there is at list one item");
return this.items.Values[0][0].Value;
}
else
{
return null;
}
}
public static bool Lookup(AscendingSortedCompoundSegmentsCollection<T> collection,
UriTemplateLiteralPathSegment wireData, out IList<IList<T>> results)
{
results = collection.Find(wireData);
return ((results != null) && (results.Count > 0));
}
struct CollectionItem
{
UriTemplateCompoundPathSegment segment;
T value;
public CollectionItem(UriTemplateCompoundPathSegment segment, T value)
{
this.segment = segment;
this.value = value;
}
public UriTemplateCompoundPathSegment Segment
{
get
{
return this.segment;
}
}
public T Value
{
get
{
return this.value;
}
}
}
}
}
}