| | | 1 | | // Licensed to the .NET Foundation under one or more agreements. |
| | | 2 | | // The .NET Foundation licenses this file to you under the MIT license. |
| | | 3 | | |
| | | 4 | | using System; |
| | | 5 | | using System.Collections.Generic; |
| | | 6 | | using System.Collections.ObjectModel; |
| | | 7 | | using CoreWCF.Runtime; |
| | | 8 | | |
| | | 9 | | namespace CoreWCF |
| | | 10 | | { |
| | | 11 | | internal class UriTemplateTrieNode |
| | | 12 | | { |
| | | 13 | | private readonly int _depth; // relative segment depth (root = 0) |
| | | 14 | | private readonly UriTemplatePathPartiallyEquivalentSet _endOfPath; // matches the non-existent segment at the en |
| | | 15 | | private AscendingSortedCompoundSegmentsCollection<UriTemplatePathPartiallyEquivalentSet> _finalCompoundSegment; |
| | | 16 | | private Dictionary<UriTemplateLiteralPathSegment, UriTemplatePathPartiallyEquivalentSet> _finalLiteralSegment; / |
| | | 17 | | private readonly UriTemplatePathPartiallyEquivalentSet _finalVariableSegment; // matches e.g. "{var}" |
| | | 18 | | private AscendingSortedCompoundSegmentsCollection<UriTemplateTrieLocation> _nextCompoundSegment; // all are Afte |
| | | 19 | | private Dictionary<UriTemplateLiteralPathSegment, UriTemplateTrieLocation> _nextLiteralSegment; // all are Befor |
| | | 20 | | private UriTemplateTrieLocation _nextVariableSegment; // is BeforeLiteral; matches e.g. "{var}/" |
| | | 21 | | private UriTemplateTrieLocation _onFailure; // points to parent, at 'after me' |
| | | 22 | | private readonly UriTemplatePathPartiallyEquivalentSet _star; // matches any "extra/path/segments" at the end |
| | | 23 | | |
| | 83 | 24 | | private UriTemplateTrieNode(int depth) |
| | | 25 | | { |
| | 83 | 26 | | _depth = depth; |
| | 83 | 27 | | _nextLiteralSegment = null; |
| | 83 | 28 | | _nextCompoundSegment = null; |
| | 83 | 29 | | _finalLiteralSegment = null; |
| | 83 | 30 | | _finalCompoundSegment = null; |
| | 83 | 31 | | _finalVariableSegment = new UriTemplatePathPartiallyEquivalentSet(depth + 1); |
| | 83 | 32 | | _star = new UriTemplatePathPartiallyEquivalentSet(depth); |
| | 83 | 33 | | _endOfPath = new UriTemplatePathPartiallyEquivalentSet(depth); |
| | 83 | 34 | | } |
| | | 35 | | |
| | | 36 | | public static UriTemplateTrieNode Make(IEnumerable<KeyValuePair<UriTemplate, object>> keyValuePairs, |
| | | 37 | | bool allowDuplicateEquivalentUriTemplates) |
| | | 38 | | { |
| | | 39 | | // given a UTT at MakeReadOnly time, build the trie |
| | | 40 | | // note that root.onFailure == null; |
| | 47 | 41 | | UriTemplateTrieNode root = new UriTemplateTrieNode(0); |
| | 420 | 42 | | foreach (KeyValuePair<UriTemplate, object> kvp in keyValuePairs) |
| | | 43 | | { |
| | 163 | 44 | | Add(root, kvp); |
| | | 45 | | } |
| | | 46 | | |
| | 47 | 47 | | Validate(root, allowDuplicateEquivalentUriTemplates); |
| | 47 | 48 | | return root; |
| | | 49 | | } |
| | | 50 | | |
| | | 51 | | public bool Match(UriTemplateLiteralPathSegment[] wireData, ICollection<UriTemplateTableMatchCandidate> candidat |
| | | 52 | | { |
| | 122 | 53 | | UriTemplateTrieLocation currentLocation = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation |
| | 122 | 54 | | return GetMatch(currentLocation, wireData, candidates); |
| | | 55 | | } |
| | | 56 | | |
| | | 57 | | private static void Add(UriTemplateTrieNode root, KeyValuePair<UriTemplate, object> kvp) |
| | | 58 | | { |
| | | 59 | | // Currently UTT doesn't support teplates with ignoreTrailingSlash == true; thus we |
| | | 60 | | // don't care about supporting it in the trie as well. |
| | 163 | 61 | | UriTemplateTrieNode current = root; |
| | 163 | 62 | | UriTemplate ut = kvp.Key; |
| | 163 | 63 | | bool needProcessingOnFinalNode = (ut._segments.Count == 0) || ut.HasWildcard || |
| | 163 | 64 | | ut._segments[ut._segments.Count - 1].EndsWithSlash; |
| | 692 | 65 | | for (int i = 0; i < ut._segments.Count; ++i) |
| | | 66 | | { |
| | 183 | 67 | | if (i >= ut._firstOptionalSegment) |
| | | 68 | | { |
| | 8 | 69 | | current._endOfPath.Items.Add(kvp); |
| | | 70 | | } |
| | | 71 | | |
| | 183 | 72 | | UriTemplatePathSegment ps = ut._segments[i]; |
| | 183 | 73 | | if (!ps.EndsWithSlash) |
| | | 74 | | { |
| | | 75 | | Fx.Assert(i == ut._segments.Count - 1, "only the last segment can !EndsWithSlash"); |
| | | 76 | | Fx.Assert(!ut.HasWildcard, "path star cannot have !EndsWithSlash"); |
| | 147 | 77 | | switch (ps.Nature) |
| | | 78 | | { |
| | | 79 | | case UriTemplatePartType.Literal: |
| | 123 | 80 | | current.AddFinalLiteralSegment(ps as UriTemplateLiteralPathSegment, kvp); |
| | 123 | 81 | | break; |
| | | 82 | | |
| | | 83 | | case UriTemplatePartType.Compound: |
| | 8 | 84 | | current.AddFinalCompoundSegment(ps as UriTemplateCompoundPathSegment, kvp); |
| | 8 | 85 | | break; |
| | | 86 | | |
| | | 87 | | case UriTemplatePartType.Variable: |
| | 16 | 88 | | current._finalVariableSegment.Items.Add(kvp); |
| | 16 | 89 | | break; |
| | | 90 | | |
| | | 91 | | default: |
| | | 92 | | Fx.Assert("Invalid value as PathSegment.Nature"); |
| | | 93 | | break; |
| | | 94 | | } |
| | | 95 | | } |
| | | 96 | | else |
| | | 97 | | { |
| | | 98 | | Fx.Assert(ps.EndsWithSlash, "ps.EndsWithSlash"); |
| | 36 | 99 | | switch (ps.Nature) |
| | | 100 | | { |
| | | 101 | | case UriTemplatePartType.Literal: |
| | 36 | 102 | | current = current.AddNextLiteralSegment(ps as UriTemplateLiteralPathSegment); |
| | 36 | 103 | | break; |
| | | 104 | | |
| | | 105 | | case UriTemplatePartType.Compound: |
| | 0 | 106 | | current = current.AddNextCompoundSegment(ps as UriTemplateCompoundPathSegment); |
| | 0 | 107 | | break; |
| | | 108 | | |
| | | 109 | | case UriTemplatePartType.Variable: |
| | 0 | 110 | | current = current.AddNextVariableSegment(); |
| | | 111 | | break; |
| | | 112 | | |
| | | 113 | | default: |
| | | 114 | | Fx.Assert("Invalid value as PathSegment.Nature"); |
| | | 115 | | break; |
| | | 116 | | } |
| | | 117 | | } |
| | | 118 | | } |
| | | 119 | | |
| | 163 | 120 | | if (needProcessingOnFinalNode) |
| | | 121 | | { |
| | | 122 | | // if the last segment ended in a slash, there is still more to do |
| | 16 | 123 | | if (ut.HasWildcard) |
| | | 124 | | { |
| | | 125 | | // e.g. "path1/path2/*" |
| | 16 | 126 | | current._star.Items.Add(kvp); |
| | | 127 | | } |
| | | 128 | | else |
| | | 129 | | { |
| | | 130 | | // e.g. "path1/path2/" |
| | 0 | 131 | | current._endOfPath.Items.Add(kvp); |
| | | 132 | | } |
| | | 133 | | } |
| | 147 | 134 | | } |
| | | 135 | | |
| | | 136 | | private static bool CheckMultipleMatches(IList<IList<UriTemplateTrieLocation>> locationsSet, UriTemplateLiteralP |
| | | 137 | | ICollection<UriTemplateTableMatchCandidate> candidates) |
| | | 138 | | { |
| | 0 | 139 | | bool result = false; |
| | 0 | 140 | | for (int i = 0; ((i < locationsSet.Count) && !result); i++) |
| | | 141 | | { |
| | 0 | 142 | | for (int j = 0; j < locationsSet[i].Count; j++) |
| | | 143 | | { |
| | 0 | 144 | | if (GetMatch(locationsSet[i][j], wireData, candidates)) |
| | | 145 | | { |
| | 0 | 146 | | result = true; |
| | | 147 | | } |
| | | 148 | | } |
| | | 149 | | } |
| | | 150 | | |
| | 0 | 151 | | return result; |
| | | 152 | | } |
| | | 153 | | |
| | | 154 | | private static bool GetMatch(UriTemplateTrieLocation location, UriTemplateLiteralPathSegment[] wireData, |
| | | 155 | | ICollection<UriTemplateTableMatchCandidate> candidates) |
| | | 156 | | { |
| | 122 | 157 | | int initialDepth = location.Node._depth; |
| | | 158 | | do |
| | | 159 | | { |
| | 130 | 160 | | if (TryMatch(wireData, location, out UriTemplatePathPartiallyEquivalentSet answer, out SingleLocationOrL |
| | | 161 | | { |
| | 121 | 162 | | if (answer != null) |
| | | 163 | | { |
| | 484 | 164 | | for (int i = 0; i < answer.Items.Count; i++) |
| | | 165 | | { |
| | 121 | 166 | | candidates.Add(new UriTemplateTableMatchCandidate(answer.Items[i].Key, answer.SegmentsCount, |
| | 121 | 167 | | answer.Items[i].Value)); |
| | | 168 | | } |
| | | 169 | | } |
| | | 170 | | |
| | 121 | 171 | | return true; |
| | | 172 | | } |
| | | 173 | | |
| | 9 | 174 | | if (nextStep.IsSingle) |
| | | 175 | | { |
| | 9 | 176 | | location = nextStep.SingleLocation; |
| | | 177 | | } |
| | | 178 | | else |
| | | 179 | | { |
| | | 180 | | Fx.Assert(nextStep.LocationsSet != null, "This should be set to a valid value by TryMatch"); |
| | 0 | 181 | | if (CheckMultipleMatches(nextStep.LocationsSet, wireData, candidates)) |
| | | 182 | | { |
| | 0 | 183 | | return true; |
| | | 184 | | } |
| | 0 | 185 | | location = GetFailureLocationFromLocationsSet(nextStep.LocationsSet); |
| | | 186 | | } |
| | 9 | 187 | | } while ((location != null) && (location.Node._depth >= initialDepth)); |
| | | 188 | | |
| | | 189 | | // we walked the whole trie down and found nothing |
| | 1 | 190 | | return false; |
| | | 191 | | } |
| | | 192 | | |
| | | 193 | | private static bool TryMatch(UriTemplateLiteralPathSegment[] wireUriSegments, UriTemplateTrieLocation currentLoc |
| | | 194 | | out UriTemplatePathPartiallyEquivalentSet success, out SingleLocationOrLocationsSet nextStep) |
| | | 195 | | { |
| | | 196 | | // if returns true, success is set to answer |
| | | 197 | | // if returns false, nextStep is set to next place to look |
| | 130 | 198 | | success = null; |
| | 130 | 199 | | nextStep = new SingleLocationOrLocationsSet(); |
| | | 200 | | |
| | 130 | 201 | | if (wireUriSegments.Length <= currentLocation.Node._depth) |
| | | 202 | | { |
| | | 203 | | Fx.Assert(wireUriSegments.Length == 0 || wireUriSegments[wireUriSegments.Length - 1].EndsWithSlash, |
| | | 204 | | "we should not have traversed this deep into the trie unless the wire path ended in a slash"); |
| | | 205 | | |
| | 1 | 206 | | if (currentLocation.Node._endOfPath.Items.Count != 0) |
| | | 207 | | { |
| | | 208 | | // exact match of e.g. "path1/path2/" |
| | 1 | 209 | | success = currentLocation.Node._endOfPath; |
| | 1 | 210 | | return true; |
| | | 211 | | } |
| | 0 | 212 | | else if (currentLocation.Node._star.Items.Count != 0) |
| | | 213 | | { |
| | | 214 | | // inexact match of e.g. WIRE("path1/path2/") against TEMPLATE("path1/path2/*") |
| | 0 | 215 | | success = currentLocation.Node._star; |
| | 0 | 216 | | return true; |
| | | 217 | | } |
| | | 218 | | else |
| | | 219 | | { |
| | 0 | 220 | | nextStep = new SingleLocationOrLocationsSet(currentLocation.Node._onFailure); |
| | 0 | 221 | | return false; |
| | | 222 | | } |
| | | 223 | | } |
| | | 224 | | else |
| | | 225 | | { |
| | 129 | 226 | | UriTemplateLiteralPathSegment curWireSeg = wireUriSegments[currentLocation.Node._depth]; |
| | 129 | 227 | | bool considerLiteral = false; |
| | 129 | 228 | | bool considerCompound = false; |
| | 129 | 229 | | bool considerVariable = false; |
| | 129 | 230 | | bool considerStar = false; |
| | 129 | 231 | | switch (currentLocation.LocationWithin) |
| | | 232 | | { |
| | | 233 | | case UriTemplateTrieIntraNodeLocation.BeforeLiteral: |
| | 129 | 234 | | considerLiteral = true; |
| | 129 | 235 | | considerCompound = true; |
| | 129 | 236 | | considerVariable = true; |
| | 129 | 237 | | considerStar = true; |
| | 129 | 238 | | break; |
| | | 239 | | case UriTemplateTrieIntraNodeLocation.AfterLiteral: |
| | 0 | 240 | | considerLiteral = false; |
| | 0 | 241 | | considerCompound = true; |
| | 0 | 242 | | considerVariable = true; |
| | 0 | 243 | | considerStar = true; |
| | 0 | 244 | | break; |
| | | 245 | | case UriTemplateTrieIntraNodeLocation.AfterCompound: |
| | 0 | 246 | | considerLiteral = false; |
| | 0 | 247 | | considerCompound = false; |
| | 0 | 248 | | considerVariable = true; |
| | 0 | 249 | | considerStar = true; |
| | 0 | 250 | | break; |
| | | 251 | | case UriTemplateTrieIntraNodeLocation.AfterVariable: |
| | 0 | 252 | | considerLiteral = false; |
| | 0 | 253 | | considerCompound = false; |
| | 0 | 254 | | considerVariable = false; |
| | 0 | 255 | | considerStar = true; |
| | | 256 | | break; |
| | | 257 | | default: |
| | | 258 | | Fx.Assert("bad kind"); |
| | | 259 | | break; |
| | | 260 | | } |
| | | 261 | | |
| | 129 | 262 | | if (curWireSeg.EndsWithSlash) |
| | | 263 | | { |
| | | 264 | | |
| | 9 | 265 | | if (considerLiteral && currentLocation.Node._nextLiteralSegment != null && |
| | 9 | 266 | | currentLocation.Node._nextLiteralSegment.ContainsKey(curWireSeg)) |
| | | 267 | | { |
| | 8 | 268 | | nextStep = new SingleLocationOrLocationsSet(currentLocation.Node._nextLiteralSegment[curWireSeg] |
| | 8 | 269 | | return false; |
| | | 270 | | } |
| | 1 | 271 | | else if (considerCompound && currentLocation.Node._nextCompoundSegment != null && |
| | 1 | 272 | | AscendingSortedCompoundSegmentsCollection<UriTemplateTrieLocation>.Lookup(currentLocation.Node._ |
| | | 273 | | { |
| | 0 | 274 | | nextStep = new SingleLocationOrLocationsSet(compoundLocationsSet); |
| | 0 | 275 | | return false; |
| | | 276 | | } |
| | 1 | 277 | | else if (considerVariable && currentLocation.Node._nextVariableSegment != null && |
| | 1 | 278 | | !curWireSeg.IsNullOrEmpty()) |
| | | 279 | | { |
| | 0 | 280 | | nextStep = new SingleLocationOrLocationsSet(currentLocation.Node._nextVariableSegment); |
| | 0 | 281 | | return false; |
| | | 282 | | } |
| | 1 | 283 | | else if (considerStar && currentLocation.Node._star.Items.Count != 0) |
| | | 284 | | { |
| | | 285 | | // matches e.g. WIRE("path1/path2/path3") and TEMPLATE("path1/*") |
| | 1 | 286 | | success = currentLocation.Node._star; |
| | 1 | 287 | | return true; |
| | | 288 | | } |
| | | 289 | | else |
| | | 290 | | { |
| | 0 | 291 | | nextStep = new SingleLocationOrLocationsSet(currentLocation.Node._onFailure); |
| | 0 | 292 | | return false; |
| | | 293 | | } |
| | | 294 | | } |
| | | 295 | | else |
| | | 296 | | { |
| | | 297 | | Fx.Assert(!curWireSeg.EndsWithSlash, "!curWireSeg.EndsWithSlash"); |
| | | 298 | | Fx.Assert(!curWireSeg.IsNullOrEmpty(), "!curWireSeg.IsNullOrEmpty()"); |
| | | 299 | | |
| | 120 | 300 | | if (considerLiteral && currentLocation.Node._finalLiteralSegment != null && |
| | 120 | 301 | | currentLocation.Node._finalLiteralSegment.ContainsKey(curWireSeg)) |
| | | 302 | | { |
| | | 303 | | // matches e.g. WIRE("path1/path2") and TEMPLATE("path1/path2") |
| | 116 | 304 | | success = currentLocation.Node._finalLiteralSegment[curWireSeg]; |
| | 116 | 305 | | return true; |
| | | 306 | | } |
| | 4 | 307 | | else if (considerCompound && currentLocation.Node._finalCompoundSegment != null && |
| | 4 | 308 | | AscendingSortedCompoundSegmentsCollection<UriTemplatePathPartiallyEquivalentSet>.Lookup(currentL |
| | | 309 | | { |
| | | 310 | | // matches e.g. WIRE("path1/path2") and TEMPLATE("path1/p{var}th2") |
| | | 311 | | // we should take only the highest order match! |
| | | 312 | | Fx.Assert(compoundPathEquivalentSets.Count >= 1, "Lookup is expected to return false otherwise") |
| | | 313 | | Fx.Assert(compoundPathEquivalentSets[0].Count > 0, "Find shouldn't return empty sublists"); |
| | | 314 | | |
| | 1 | 315 | | if (compoundPathEquivalentSets[0].Count == 1) |
| | | 316 | | { |
| | 1 | 317 | | success = compoundPathEquivalentSets[0][0]; |
| | | 318 | | } |
| | | 319 | | else |
| | | 320 | | { |
| | 0 | 321 | | success = new UriTemplatePathPartiallyEquivalentSet(currentLocation.Node._depth + 1); |
| | 0 | 322 | | for (int i = 0; i < compoundPathEquivalentSets[0].Count; i++) |
| | | 323 | | { |
| | 0 | 324 | | success.Items.AddRange(compoundPathEquivalentSets[0][i].Items); |
| | | 325 | | } |
| | | 326 | | } |
| | | 327 | | |
| | 1 | 328 | | return true; |
| | | 329 | | } |
| | 3 | 330 | | else if (considerVariable && currentLocation.Node._finalVariableSegment.Items.Count != 0) |
| | | 331 | | { |
| | | 332 | | // matches e.g. WIRE("path1/path2") and TEMPLATE("path1/{var}") |
| | 1 | 333 | | success = currentLocation.Node._finalVariableSegment; |
| | | 334 | | |
| | 1 | 335 | | return true; |
| | | 336 | | } |
| | 2 | 337 | | else if (considerStar && currentLocation.Node._star.Items.Count != 0) |
| | | 338 | | { |
| | | 339 | | // matches e.g. WIRE("path1/path2") and TEMPLATE("path1/*") |
| | 1 | 340 | | success = currentLocation.Node._star; |
| | | 341 | | |
| | 1 | 342 | | return true; |
| | | 343 | | } |
| | | 344 | | else |
| | | 345 | | { |
| | 1 | 346 | | nextStep = new SingleLocationOrLocationsSet(currentLocation.Node._onFailure); |
| | | 347 | | |
| | 1 | 348 | | return false; |
| | | 349 | | } |
| | | 350 | | } |
| | | 351 | | } |
| | | 352 | | } |
| | | 353 | | |
| | | 354 | | private static UriTemplateTrieLocation GetFailureLocationFromLocationsSet(IList<IList<UriTemplateTrieLocation>> |
| | | 355 | | { |
| | | 356 | | Fx.Assert(locationsSet != null, "Shouldn't be called on null set"); |
| | | 357 | | Fx.Assert(locationsSet.Count > 0, "Shouldn't be called on empty set"); |
| | | 358 | | Fx.Assert(locationsSet[0] != null, "Shouldn't be called on a set with null sub-lists"); |
| | | 359 | | Fx.Assert(locationsSet[0].Count > 0, "Shouldn't be called on a set with empty sub-lists"); |
| | | 360 | | |
| | 0 | 361 | | return locationsSet[0][0].Node._onFailure; |
| | | 362 | | } |
| | | 363 | | |
| | | 364 | | private static void Validate(UriTemplateTrieNode root, bool allowDuplicateEquivalentUriTemplates) |
| | | 365 | | { |
| | | 366 | | // walk the entire tree, and ensure that each PathEquivalentSet is ok (no ambiguous queries), |
| | | 367 | | // verify the compound segments didn't add potentially multiple matches; |
| | | 368 | | // also Assert various data-structure invariants |
| | 47 | 369 | | Queue<UriTemplateTrieNode> nodesQueue = new Queue<UriTemplateTrieNode>(); |
| | | 370 | | |
| | 47 | 371 | | UriTemplateTrieNode current = root; |
| | 36 | 372 | | while (true) |
| | | 373 | | { |
| | | 374 | | // validate all the PathEquivalentSets that live in this node |
| | 83 | 375 | | Validate(current._endOfPath, allowDuplicateEquivalentUriTemplates); |
| | 83 | 376 | | Validate(current._finalVariableSegment, allowDuplicateEquivalentUriTemplates); |
| | 83 | 377 | | Validate(current._star, allowDuplicateEquivalentUriTemplates); |
| | 83 | 378 | | if (current._finalLiteralSegment != null) |
| | | 379 | | { |
| | 324 | 380 | | foreach (KeyValuePair<UriTemplateLiteralPathSegment, UriTemplatePathPartiallyEquivalentSet> kvp in c |
| | | 381 | | { |
| | 123 | 382 | | Validate(kvp.Value, allowDuplicateEquivalentUriTemplates); |
| | | 383 | | } |
| | | 384 | | } |
| | | 385 | | |
| | 83 | 386 | | if (current._finalCompoundSegment != null) |
| | | 387 | | { |
| | 8 | 388 | | IList<IList<UriTemplatePathPartiallyEquivalentSet>> pesLists = current._finalCompoundSegment.Values; |
| | 32 | 389 | | for (int i = 0; i < pesLists.Count; i++) |
| | | 390 | | { |
| | 8 | 391 | | if (!allowDuplicateEquivalentUriTemplates && (pesLists[i].Count > 1)) |
| | | 392 | | { |
| | 0 | 393 | | throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.F |
| | 0 | 394 | | SR.UTTDuplicate, pesLists[i][0].Items[0].Key.ToString(), pesLists[i][1].Items[0].Key.ToS |
| | | 395 | | } |
| | 32 | 396 | | for (int j = 0; j < pesLists[i].Count; j++) |
| | | 397 | | { |
| | 8 | 398 | | Validate(pesLists[i][j], allowDuplicateEquivalentUriTemplates); |
| | | 399 | | } |
| | | 400 | | } |
| | | 401 | | } |
| | | 402 | | |
| | | 403 | | // deal with children of this node |
| | 83 | 404 | | if (current._nextLiteralSegment != null) |
| | | 405 | | { |
| | 96 | 406 | | foreach (KeyValuePair<UriTemplateLiteralPathSegment, UriTemplateTrieLocation> kvp in current._nextLi |
| | | 407 | | { |
| | | 408 | | Fx.Assert(kvp.Value.LocationWithin == UriTemplateTrieIntraNodeLocation.BeforeLiteral, "forward-p |
| | | 409 | | Fx.Assert(kvp.Value.Node._depth == current._depth + 1, "kvp.Value.node.depth == current.depth + |
| | | 410 | | Fx.Assert(kvp.Value.Node._onFailure.Node == current, "back pointer should point back to here"); |
| | | 411 | | Fx.Assert(kvp.Value.Node._onFailure.LocationWithin == UriTemplateTrieIntraNodeLocation.AfterLite |
| | 36 | 412 | | nodesQueue.Enqueue(kvp.Value.Node); |
| | | 413 | | } |
| | | 414 | | } |
| | | 415 | | |
| | 83 | 416 | | if (current._nextCompoundSegment != null) |
| | | 417 | | { |
| | 0 | 418 | | IList<IList<UriTemplateTrieLocation>> locations = current._nextCompoundSegment.Values; |
| | 0 | 419 | | for (int i = 0; i < locations.Count; i++) |
| | | 420 | | { |
| | 0 | 421 | | if (!allowDuplicateEquivalentUriTemplates && (locations[i].Count > 1)) |
| | | 422 | | { |
| | | 423 | | // In the future we might ease up the restrictions and verify if there is realy |
| | | 424 | | // a potential multiple match here; for now we are throwing. |
| | 0 | 425 | | UriTemplate firstTemplate = FindAnyUriTemplate(locations[i][0].Node); |
| | 0 | 426 | | UriTemplate secondTemplate = FindAnyUriTemplate(locations[i][1].Node); |
| | 0 | 427 | | throw DiagnosticUtility.ExceptionUtility.ThrowHelperError(new InvalidOperationException(SR.F |
| | 0 | 428 | | SR.UTTDuplicate, firstTemplate.ToString(), secondTemplate.ToString()))); |
| | | 429 | | } |
| | | 430 | | |
| | 0 | 431 | | for (int j = 0; j < locations[i].Count; j++) |
| | | 432 | | { |
| | 0 | 433 | | UriTemplateTrieLocation location = locations[i][j]; |
| | | 434 | | |
| | | 435 | | Fx.Assert(location.LocationWithin == UriTemplateTrieIntraNodeLocation.BeforeLiteral, "forwar |
| | | 436 | | Fx.Assert(location.Node._depth == current._depth + 1, "kvp.Value.node.depth == current.depth |
| | | 437 | | Fx.Assert(location.Node._onFailure.Node == current, "back pointer should point back to here" |
| | | 438 | | Fx.Assert(location.Node._onFailure.LocationWithin == UriTemplateTrieIntraNodeLocation.AfterC |
| | | 439 | | |
| | 0 | 440 | | nodesQueue.Enqueue(location.Node); |
| | | 441 | | } |
| | | 442 | | } |
| | | 443 | | } |
| | | 444 | | |
| | 83 | 445 | | if (current._nextVariableSegment != null) |
| | | 446 | | { |
| | | 447 | | Fx.Assert(current._nextVariableSegment.LocationWithin == UriTemplateTrieIntraNodeLocation.BeforeLite |
| | | 448 | | Fx.Assert(current._nextVariableSegment.Node._depth == current._depth + 1, "current.nextVariableSegme |
| | | 449 | | Fx.Assert(current._nextVariableSegment.Node._onFailure.Node == current, "back pointer should point b |
| | | 450 | | Fx.Assert(current._nextVariableSegment.Node._onFailure.LocationWithin == UriTemplateTrieIntraNodeLoc |
| | | 451 | | |
| | 0 | 452 | | nodesQueue.Enqueue(current._nextVariableSegment.Node); |
| | | 453 | | } |
| | | 454 | | |
| | | 455 | | // move on to next bit of work |
| | 83 | 456 | | if (nodesQueue.Count == 0) |
| | | 457 | | { |
| | | 458 | | break; |
| | | 459 | | } |
| | | 460 | | |
| | 36 | 461 | | current = nodesQueue.Dequeue(); |
| | | 462 | | } |
| | 47 | 463 | | } |
| | | 464 | | |
| | | 465 | | private static void Validate(UriTemplatePathPartiallyEquivalentSet pes, bool allowDuplicateEquivalentUriTemplate |
| | | 466 | | { |
| | | 467 | | // A set with 0 or 1 items is valid by definition |
| | 380 | 468 | | if (pes.Items.Count < 2) |
| | | 469 | | { |
| | 380 | 470 | | return; |
| | | 471 | | } |
| | | 472 | | |
| | | 473 | | // Assert all paths are partially-equivalent |
| | 0 | 474 | | for (int i = 0; i < pes.Items.Count - 1; ++i) |
| | | 475 | | { |
| | | 476 | | Fx.Assert(pes.Items[i].Key.IsPathPartiallyEquivalentAt(pes.Items[i + 1].Key, pes.SegmentsCount), |
| | | 477 | | "all elements of a PES must be path partially-equivalent"); |
| | | 478 | | } |
| | | 479 | | |
| | | 480 | | // We will check that the queries disambiguate only for templates, which are |
| | | 481 | | // matched completely at the segments count; templates, which are match at |
| | | 482 | | // that point due to terminal defaults, will be ruled out. |
| | 0 | 483 | | UriTemplate[] a = new UriTemplate[pes.Items.Count]; |
| | 0 | 484 | | int arrayIndex = 0; |
| | 0 | 485 | | foreach (KeyValuePair<UriTemplate, object> kvp in pes.Items) |
| | | 486 | | { |
| | 0 | 487 | | if (pes.SegmentsCount < kvp.Key._segments.Count) |
| | | 488 | | { |
| | | 489 | | continue; |
| | | 490 | | } |
| | | 491 | | |
| | | 492 | | Fx.Assert(arrayIndex < a.Length, "We made enough room for all the items"); |
| | | 493 | | |
| | 0 | 494 | | a[arrayIndex++] = kvp.Key; |
| | | 495 | | } |
| | | 496 | | |
| | | 497 | | // Ensure that queries disambiguate (if needed) : |
| | 0 | 498 | | if (arrayIndex > 0) |
| | | 499 | | { |
| | 0 | 500 | | UriTemplateHelpers.DisambiguateSamePath(a, 0, arrayIndex, allowDuplicateEquivalentUriTemplates); |
| | | 501 | | } |
| | 0 | 502 | | } |
| | | 503 | | |
| | | 504 | | private static UriTemplate FindAnyUriTemplate(UriTemplateTrieNode node) |
| | | 505 | | { |
| | 0 | 506 | | while (node != null) |
| | | 507 | | { |
| | 0 | 508 | | if (node._endOfPath.Items.Count > 0) |
| | | 509 | | { |
| | 0 | 510 | | return node._endOfPath.Items[0].Key; |
| | | 511 | | } |
| | | 512 | | |
| | 0 | 513 | | if (node._finalVariableSegment.Items.Count > 0) |
| | | 514 | | { |
| | 0 | 515 | | return node._finalVariableSegment.Items[0].Key; |
| | | 516 | | } |
| | | 517 | | |
| | 0 | 518 | | if (node._star.Items.Count > 0) |
| | | 519 | | { |
| | 0 | 520 | | return node._star.Items[0].Key; |
| | | 521 | | } |
| | | 522 | | |
| | 0 | 523 | | if (node._finalLiteralSegment != null) |
| | | 524 | | { |
| | 0 | 525 | | UriTemplatePathPartiallyEquivalentSet pes = |
| | 0 | 526 | | GetAnyDictionaryValue(node._finalLiteralSegment); |
| | | 527 | | |
| | | 528 | | Fx.Assert(pes.Items.Count > 0, "Otherwise, why creating the dictionary?"); |
| | | 529 | | |
| | 0 | 530 | | return pes.Items[0].Key; |
| | | 531 | | } |
| | | 532 | | |
| | 0 | 533 | | if (node._finalCompoundSegment != null) |
| | | 534 | | { |
| | 0 | 535 | | UriTemplatePathPartiallyEquivalentSet pes = node._finalCompoundSegment.GetAnyValue(); |
| | | 536 | | |
| | | 537 | | Fx.Assert(pes.Items.Count > 0, "Otherwise, why creating the collection?"); |
| | | 538 | | |
| | 0 | 539 | | return pes.Items[0].Key; |
| | | 540 | | } |
| | | 541 | | |
| | 0 | 542 | | if (node._nextLiteralSegment != null) |
| | | 543 | | { |
| | 0 | 544 | | UriTemplateTrieLocation location = |
| | 0 | 545 | | GetAnyDictionaryValue(node._nextLiteralSegment); |
| | 0 | 546 | | node = location.Node; |
| | | 547 | | } |
| | 0 | 548 | | else if (node._nextCompoundSegment != null) |
| | | 549 | | { |
| | 0 | 550 | | UriTemplateTrieLocation location = node._nextCompoundSegment.GetAnyValue(); |
| | 0 | 551 | | node = location.Node; |
| | | 552 | | } |
| | 0 | 553 | | else if (node._nextVariableSegment != null) |
| | | 554 | | { |
| | 0 | 555 | | node = node._nextVariableSegment.Node; |
| | | 556 | | } |
| | | 557 | | else |
| | | 558 | | { |
| | 0 | 559 | | node = null; |
| | | 560 | | } |
| | | 561 | | } |
| | | 562 | | |
| | | 563 | | Fx.Assert("How did we got here without finding a UriTemplate earlier?"); |
| | | 564 | | |
| | 0 | 565 | | return null; |
| | | 566 | | } |
| | | 567 | | |
| | | 568 | | private static T GetAnyDictionaryValue<T>(IDictionary<UriTemplateLiteralPathSegment, T> dictionary) |
| | | 569 | | { |
| | 0 | 570 | | using (IEnumerator<T> valuesEnumerator = dictionary.Values.GetEnumerator()) |
| | | 571 | | { |
| | 0 | 572 | | valuesEnumerator.MoveNext(); |
| | 0 | 573 | | return valuesEnumerator.Current; |
| | | 574 | | } |
| | 0 | 575 | | } |
| | | 576 | | |
| | | 577 | | private void AddFinalCompoundSegment(UriTemplateCompoundPathSegment cps, KeyValuePair<UriTemplate, object> kvp) |
| | | 578 | | { |
| | | 579 | | Fx.Assert(cps != null, "must be - based on the segment nature"); |
| | | 580 | | |
| | 8 | 581 | | if (_finalCompoundSegment == null) |
| | | 582 | | { |
| | 8 | 583 | | _finalCompoundSegment = new AscendingSortedCompoundSegmentsCollection<UriTemplatePathPartiallyEquivalent |
| | | 584 | | } |
| | | 585 | | |
| | 8 | 586 | | UriTemplatePathPartiallyEquivalentSet pes = _finalCompoundSegment.Find(cps); |
| | 8 | 587 | | if (pes == null) |
| | | 588 | | { |
| | 8 | 589 | | pes = new UriTemplatePathPartiallyEquivalentSet(_depth + 1); |
| | 8 | 590 | | _finalCompoundSegment.Add(cps, pes); |
| | | 591 | | } |
| | | 592 | | |
| | 8 | 593 | | pes.Items.Add(kvp); |
| | 8 | 594 | | } |
| | | 595 | | |
| | | 596 | | private void AddFinalLiteralSegment(UriTemplateLiteralPathSegment lps, KeyValuePair<UriTemplate, object> kvp) |
| | | 597 | | { |
| | | 598 | | Fx.Assert(lps != null, "must be - based on the segment nature"); |
| | | 599 | | |
| | 123 | 600 | | if (_finalLiteralSegment != null && _finalLiteralSegment.ContainsKey(lps)) |
| | | 601 | | { |
| | 0 | 602 | | _finalLiteralSegment[lps].Items.Add(kvp); |
| | | 603 | | } |
| | | 604 | | else |
| | | 605 | | { |
| | 123 | 606 | | if (_finalLiteralSegment == null) |
| | | 607 | | { |
| | 39 | 608 | | _finalLiteralSegment = new Dictionary<UriTemplateLiteralPathSegment, UriTemplatePathPartiallyEquival |
| | | 609 | | } |
| | | 610 | | |
| | 123 | 611 | | UriTemplatePathPartiallyEquivalentSet pes = new UriTemplatePathPartiallyEquivalentSet(_depth + 1); |
| | 123 | 612 | | pes.Items.Add(kvp); |
| | 123 | 613 | | _finalLiteralSegment.Add(lps, pes); |
| | | 614 | | } |
| | 123 | 615 | | } |
| | | 616 | | |
| | | 617 | | private UriTemplateTrieNode AddNextCompoundSegment(UriTemplateCompoundPathSegment cps) |
| | | 618 | | { |
| | | 619 | | Fx.Assert(cps != null, "must be - based on the segment nature"); |
| | | 620 | | |
| | 0 | 621 | | if (_nextCompoundSegment == null) |
| | | 622 | | { |
| | 0 | 623 | | _nextCompoundSegment = new AscendingSortedCompoundSegmentsCollection<UriTemplateTrieLocation>(); |
| | | 624 | | } |
| | | 625 | | |
| | 0 | 626 | | UriTemplateTrieLocation nextLocation = _nextCompoundSegment.Find(cps); |
| | 0 | 627 | | if (nextLocation == null) |
| | | 628 | | { |
| | 0 | 629 | | UriTemplateTrieNode nextNode = new UriTemplateTrieNode(_depth + 1); |
| | 0 | 630 | | nextNode._onFailure = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.AfterCompound); |
| | 0 | 631 | | nextLocation = new UriTemplateTrieLocation(nextNode, UriTemplateTrieIntraNodeLocation.BeforeLiteral); |
| | 0 | 632 | | _nextCompoundSegment.Add(cps, nextLocation); |
| | | 633 | | } |
| | | 634 | | |
| | 0 | 635 | | return nextLocation.Node; |
| | | 636 | | } |
| | | 637 | | |
| | | 638 | | private UriTemplateTrieNode AddNextLiteralSegment(UriTemplateLiteralPathSegment lps) |
| | | 639 | | { |
| | | 640 | | Fx.Assert(lps != null, "must be - based on the segment nature"); |
| | | 641 | | |
| | 36 | 642 | | if (_nextLiteralSegment != null && _nextLiteralSegment.ContainsKey(lps)) |
| | | 643 | | { |
| | 0 | 644 | | return _nextLiteralSegment[lps].Node; |
| | | 645 | | } |
| | | 646 | | else |
| | | 647 | | { |
| | 36 | 648 | | if (_nextLiteralSegment == null) |
| | | 649 | | { |
| | 12 | 650 | | _nextLiteralSegment = new Dictionary<UriTemplateLiteralPathSegment, UriTemplateTrieLocation>(); |
| | | 651 | | } |
| | | 652 | | |
| | 36 | 653 | | UriTemplateTrieNode newNode = new UriTemplateTrieNode(_depth + 1); |
| | 36 | 654 | | newNode._onFailure = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.AfterLiteral); |
| | 36 | 655 | | _nextLiteralSegment.Add(lps, new UriTemplateTrieLocation(newNode, UriTemplateTrieIntraNodeLocation.Befor |
| | | 656 | | |
| | 36 | 657 | | return newNode; |
| | | 658 | | } |
| | | 659 | | } |
| | | 660 | | |
| | | 661 | | private UriTemplateTrieNode AddNextVariableSegment() |
| | | 662 | | { |
| | 0 | 663 | | if (_nextVariableSegment != null) |
| | | 664 | | { |
| | 0 | 665 | | return _nextVariableSegment.Node; |
| | | 666 | | } |
| | | 667 | | else |
| | | 668 | | { |
| | 0 | 669 | | UriTemplateTrieNode newNode = new UriTemplateTrieNode(_depth + 1); |
| | 0 | 670 | | newNode._onFailure = new UriTemplateTrieLocation(this, UriTemplateTrieIntraNodeLocation.AfterVariable); |
| | 0 | 671 | | _nextVariableSegment = new UriTemplateTrieLocation(newNode, UriTemplateTrieIntraNodeLocation.BeforeLiter |
| | | 672 | | |
| | 0 | 673 | | return newNode; |
| | | 674 | | } |
| | | 675 | | } |
| | | 676 | | |
| | | 677 | | internal struct SingleLocationOrLocationsSet |
| | | 678 | | { |
| | | 679 | | private readonly IList<IList<UriTemplateTrieLocation>> _locationsSet; |
| | | 680 | | private readonly UriTemplateTrieLocation _singleLocation; |
| | | 681 | | |
| | | 682 | | public SingleLocationOrLocationsSet(UriTemplateTrieLocation singleLocation) |
| | | 683 | | { |
| | 9 | 684 | | IsSingle = true; |
| | 9 | 685 | | _singleLocation = singleLocation; |
| | 9 | 686 | | _locationsSet = null; |
| | 9 | 687 | | } |
| | | 688 | | |
| | | 689 | | public SingleLocationOrLocationsSet(IList<IList<UriTemplateTrieLocation>> locationsSet) |
| | | 690 | | { |
| | 0 | 691 | | IsSingle = false; |
| | 0 | 692 | | _singleLocation = null; |
| | 0 | 693 | | _locationsSet = locationsSet; |
| | 0 | 694 | | } |
| | | 695 | | |
| | 9 | 696 | | public bool IsSingle { get; } |
| | | 697 | | |
| | | 698 | | public IList<IList<UriTemplateTrieLocation>> LocationsSet |
| | | 699 | | { |
| | | 700 | | get |
| | | 701 | | { |
| | | 702 | | Fx.Assert(!IsSingle, "!this.isSingle"); |
| | | 703 | | |
| | 0 | 704 | | return _locationsSet; |
| | | 705 | | } |
| | | 706 | | } |
| | | 707 | | |
| | | 708 | | public UriTemplateTrieLocation SingleLocation |
| | | 709 | | { |
| | | 710 | | get |
| | | 711 | | { |
| | | 712 | | Fx.Assert(IsSingle, "this.isSingle"); |
| | | 713 | | |
| | 9 | 714 | | return _singleLocation; |
| | | 715 | | } |
| | | 716 | | } |
| | | 717 | | } |
| | | 718 | | |
| | | 719 | | internal class AscendingSortedCompoundSegmentsCollection<T> |
| | | 720 | | where T : class |
| | | 721 | | { |
| | | 722 | | private readonly SortedList<UriTemplateCompoundPathSegment, Collection<CollectionItem>> _items; |
| | | 723 | | |
| | 8 | 724 | | public AscendingSortedCompoundSegmentsCollection() |
| | | 725 | | { |
| | 8 | 726 | | _items = new SortedList<UriTemplateCompoundPathSegment, Collection<AscendingSortedCompoundSegmentsCollec |
| | 8 | 727 | | } |
| | | 728 | | |
| | | 729 | | public IList<IList<T>> Values |
| | | 730 | | { |
| | | 731 | | get |
| | | 732 | | { |
| | 8 | 733 | | IList<IList<T>> results = new List<IList<T>>(_items.Count); |
| | 32 | 734 | | for (int i = 0; i < _items.Values.Count; i++) |
| | | 735 | | { |
| | 8 | 736 | | results.Add(new List<T>(_items.Values[i].Count)); |
| | | 737 | | Fx.Assert(results.Count == i + 1, "We are adding item for each values collection"); |
| | 32 | 738 | | for (int j = 0; j < _items.Values[i].Count; j++) |
| | | 739 | | { |
| | 8 | 740 | | results[i].Add(_items.Values[i][j].Value); |
| | | 741 | | Fx.Assert(results[i].Count == j + 1, "We are adding item for each value in the collection"); |
| | | 742 | | } |
| | | 743 | | |
| | | 744 | | Fx.Assert(results[i].Count == _items.Values[i].Count, "We were supposed to add an item for each |
| | | 745 | | } |
| | | 746 | | |
| | | 747 | | Fx.Assert(results.Count == _items.Values.Count, "We were supposed to add a sub-list for each values |
| | | 748 | | |
| | 8 | 749 | | return results; |
| | | 750 | | } |
| | | 751 | | } |
| | | 752 | | |
| | | 753 | | public void Add(UriTemplateCompoundPathSegment segment, T value) |
| | | 754 | | { |
| | 8 | 755 | | int index = _items.IndexOfKey(segment); |
| | 8 | 756 | | if (index == -1) |
| | | 757 | | { |
| | 8 | 758 | | Collection<CollectionItem> subItems = new Collection<CollectionItem> |
| | 8 | 759 | | { |
| | 8 | 760 | | new CollectionItem(segment, value) |
| | 8 | 761 | | }; |
| | 8 | 762 | | _items.Add(segment, subItems); |
| | | 763 | | } |
| | | 764 | | else |
| | | 765 | | { |
| | 0 | 766 | | Collection<CollectionItem> subItems = _items.Values[index]; |
| | 0 | 767 | | subItems.Add(new CollectionItem(segment, value)); |
| | | 768 | | } |
| | 0 | 769 | | } |
| | | 770 | | |
| | | 771 | | public T Find(UriTemplateCompoundPathSegment segment) |
| | | 772 | | { |
| | 8 | 773 | | int index = _items.IndexOfKey(segment); |
| | 8 | 774 | | if (index == -1) |
| | | 775 | | { |
| | 8 | 776 | | return null; |
| | | 777 | | } |
| | | 778 | | |
| | 0 | 779 | | Collection<CollectionItem> subItems = this._items.Values[index]; |
| | 0 | 780 | | for (int i = 0; i < subItems.Count; i++) |
| | | 781 | | { |
| | 0 | 782 | | if (subItems[i].Segment.IsEquivalentTo(segment, false)) |
| | | 783 | | { |
| | 0 | 784 | | return subItems[i].Value; |
| | | 785 | | } |
| | | 786 | | } |
| | | 787 | | |
| | 0 | 788 | | return null; |
| | | 789 | | } |
| | | 790 | | |
| | | 791 | | public IList<IList<T>> Find(UriTemplateLiteralPathSegment wireData) |
| | | 792 | | { |
| | 1 | 793 | | IList<IList<T>> results = new List<IList<T>>(); |
| | 4 | 794 | | for (int i = 0; i < _items.Values.Count; i++) |
| | | 795 | | { |
| | 1 | 796 | | List<T> sameOrderResults = null; |
| | 4 | 797 | | for (int j = 0; j < _items.Values[i].Count; j++) |
| | | 798 | | { |
| | 1 | 799 | | if (_items.Values[i][j].Segment.IsMatch(wireData)) |
| | | 800 | | { |
| | 1 | 801 | | if (sameOrderResults == null) |
| | | 802 | | { |
| | 1 | 803 | | sameOrderResults = new List<T>(); |
| | | 804 | | } |
| | 1 | 805 | | sameOrderResults.Add(_items.Values[i][j].Value); |
| | | 806 | | } |
| | | 807 | | } |
| | | 808 | | |
| | 1 | 809 | | if (sameOrderResults != null) |
| | | 810 | | { |
| | 1 | 811 | | results.Add(sameOrderResults); |
| | | 812 | | } |
| | | 813 | | } |
| | | 814 | | |
| | 1 | 815 | | return results; |
| | | 816 | | } |
| | | 817 | | |
| | | 818 | | public T GetAnyValue() |
| | | 819 | | { |
| | 0 | 820 | | if (_items.Values.Count > 0) |
| | | 821 | | { |
| | | 822 | | Fx.Assert(_items.Values[0].Count > 0, "We are not adding a sub-list unless there is at list one item |
| | | 823 | | |
| | 0 | 824 | | return _items.Values[0][0].Value; |
| | | 825 | | } |
| | | 826 | | else |
| | | 827 | | { |
| | 0 | 828 | | return null; |
| | | 829 | | } |
| | | 830 | | } |
| | | 831 | | |
| | | 832 | | public static bool Lookup(AscendingSortedCompoundSegmentsCollection<T> collection, |
| | | 833 | | UriTemplateLiteralPathSegment wireData, out IList<IList<T>> results) |
| | | 834 | | { |
| | 1 | 835 | | results = collection.Find(wireData); |
| | 1 | 836 | | return (results != null) && (results.Count > 0); |
| | | 837 | | } |
| | | 838 | | |
| | | 839 | | internal struct CollectionItem |
| | | 840 | | { |
| | | 841 | | public CollectionItem(UriTemplateCompoundPathSegment segment, T value) |
| | | 842 | | { |
| | 8 | 843 | | Segment = segment; |
| | 8 | 844 | | Value = value; |
| | 8 | 845 | | } |
| | | 846 | | |
| | 1 | 847 | | public UriTemplateCompoundPathSegment Segment { get; } |
| | | 848 | | |
| | 9 | 849 | | public T Value { get; } |
| | | 850 | | } |
| | | 851 | | } |
| | | 852 | | } |
| | | 853 | | } |