mcs/class/System.Web.Routing/System.Web.Routing/PatternParser.cs

   1 //
   2 // PatternParser.cs
   3 //
   4 // Author:
   5 //      Atsushi Enomoto <atsushi@ximian.com>
   6 //      Marek Habersack <mhabersack@novell.com>
   7 //
   8 // Copyright (C) 2008-2009 Novell Inc. http://novell.com
   9 //
  10
  11 //
  12 // Permission is hereby granted, free of charge, to any person obtaining
  13 // a copy of this software and associated documentation files (the
  14 // "Software"), to deal in the Software without restriction, including
  15 // without limitation the rights to use, copy, modify, merge, publish,
  16 // distribute, sublicense, and/or sell copies of the Software, and to
  17 // permit persons to whom the Software is furnished to do so, subject to
  18 // the following conditions:
  19 //
  20 // The above copyright notice and this permission notice shall be
  21 // included in all copies or substantial portions of the Software.
  22 //
  23 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  24 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  25 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  26 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  27 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  28 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  29 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  30 //
  31 using System;
  32 using System.Collections.Generic;
  33 using System.Security.Permissions;
  34 using System.Text;
  35 using System.Web;
  36 using System.Web.Util;
  37
  38 namespace System.Web.Routing
  39 {
  40         sealed class PatternParser
  41         {
  42                 struct PatternSegment
  43                 {
  44                         public bool AllLiteral;
  45                         public List <PatternToken> Tokens;
  46                 }
  47
  48                 static readonly char[] placeholderDelimiters = { '{', '}' };
  49
  50                 PatternSegment[] segments;
  51                 Dictionary <string, bool> parameterNames;
  52                 PatternToken[] tokens;
  53
  54                 int segmentCount;
  55                 bool haveSegmentWithCatchAll;
  56
  57                 public string Url {
  58                         get;
  59                         private set;
  60                 }
  61
  62                 public PatternParser (string pattern)
  63                 {
  64                         this.Url = pattern;
  65                         Parse ();
  66                 }
  67
  68                 void Parse ()
  69                 {
  70                         string url = Url;
  71
  72                         if (String.IsNullOrEmpty (url))
  73                                 throw new SystemException ("INTERNAL ERROR: it should not try to parse null or empty string");
  74                         if (url [0] == '~' || url [0] == '/')
  75                                 throw new ArgumentException ("Url must not start with '~' or '/'");
  76                         if (url.IndexOf ('?') >= 0)
  77                                 throw new ArgumentException ("Url must not contain '?'");
  78
  79                         string[] parts = url.Split ('/');
  80                         int partsCount = segmentCount = parts.Length;
  81                         var allTokens = new List <PatternToken> ();
  82                         PatternToken tmpToken;
  83
  84                         segments = new PatternSegment [partsCount];
  85                         parameterNames = new Dictionary <string, bool> ();
  86
  87                         for (int i = 0; i < partsCount; i++) {
  88                                 if (haveSegmentWithCatchAll)
  89                                         throw new ArgumentException ("A catch-all parameter can only appear as the last segment of the route URL");
  90
  91                                 int catchAlls = 0;
  92                                 string part = parts [i];
  93                                 int partLength = part.Length;
  94                                 var tokens = new List <PatternToken> ();
  95
  96                                 if (partLength == 0 && i < partsCount - 1)
  97                                         throw new ArgumentException ("Consecutive URL segment separators '/' are not allowed");
  98
  99                                 if (part.IndexOf ("{}") != -1)
 100                                         throw new ArgumentException ("Empty URL parameter name is not allowed");
 101
 102                                 if (i > 0)
 103                                         allTokens.Add (null);
 104
 105                                 if (part.IndexOfAny (placeholderDelimiters) == -1) {
 106                                         // no placeholders here, short-circuit it
 107                                         tmpToken = new PatternToken (PatternTokenType.Literal, part);
 108                                         tokens.Add (tmpToken);
 109                                         allTokens.Add (tmpToken);
 110                                         segments [i].AllLiteral = true;
 111                                         segments [i].Tokens = tokens;
 112                                         continue;
 113                                 }
 114
 115                                 string tmp;
 116                                 int from = 0, start;
 117                                 bool allLiteral = true;
 118                                 while (from < partLength) {
 119                                         start = part.IndexOf ('{', from);
 120                                         if (start >= partLength - 2)
 121                                                 throw new ArgumentException ("Unterminated URL parameter. It must contain matching '}'");
 122
 123                                         if (start < 0) {
 124                                                 if (part.IndexOf ('}', from) >= from)
 125                                                         throw new ArgumentException ("Unmatched URL parameter closer '}'. A corresponding '{' must precede");
 126                                                 tmp = part.Substring (from);
 127                                                 tmpToken = new PatternToken (PatternTokenType.Literal, tmp);
 128                                                 tokens.Add (tmpToken);
 129                                                 allTokens.Add (tmpToken);
 130                                                 from += tmp.Length;
 131                                                 break;
 132                                         }
 133
 134                                         if (from == 0 && start > 0) {
 135                                                 tmpToken = new PatternToken (PatternTokenType.Literal, part.Substring (0, start));
 136                                                 tokens.Add (tmpToken);
 137                                                 allTokens.Add (tmpToken);
 138                                         }
 139
 140                                         int end = part.IndexOf ('}', start + 1);
 141                                         int next = part.IndexOf ('{', start + 1);
 142
 143                                         if (end < 0 || next >= 0 && next < end)
 144                                                 throw new ArgumentException ("Unterminated URL parameter. It must contain matching '}'");
 145                                         if (next == end + 1)
 146                                                 throw new ArgumentException ("Two consecutive URL parameters are not allowed. Split into a different segment by '/', or a literal string.");
 147
 148                                         if (next == -1)
 149                                                 next = partLength;
 150
 151                                         string token = part.Substring (start + 1, end - start - 1);
 152                                         PatternTokenType type;
 153                                         if (token [0] == '*') {
 154                                                 catchAlls++;
 155                                                 haveSegmentWithCatchAll = true;
 156                                                 type = PatternTokenType.CatchAll;
 157                                                 token = token.Substring (1);
 158                                         } else
 159                                                 type = PatternTokenType.Standard;
 160
 161                                         if (!parameterNames.ContainsKey (token))
 162                                                 parameterNames.Add (token, true);
 163
 164                                         tmpToken = new PatternToken (type, token);
 165                                         tokens.Add (tmpToken);
 166                                         allTokens.Add (tmpToken);
 167                                         allLiteral = false;
 168
 169                                         if (end < partLength - 1) {
 170                                                 token = part.Substring (end + 1, next - end - 1);
 171                                                 tmpToken = new PatternToken (PatternTokenType.Literal, token);
 172                                                 tokens.Add (tmpToken);
 173                                                 allTokens.Add (tmpToken);
 174                                                 end += token.Length;
 175                                         }
 176
 177                                         if (catchAlls > 1 || (catchAlls == 1 && tokens.Count > 1))
 178                                                 throw new ArgumentException ("A path segment that contains more than one section, such as a literal section or a parameter, cannot contain a catch-all parameter.");
 179                                         from = end + 1;
 180                                 }
 181
 182                                 segments [i].AllLiteral = allLiteral;
 183                                 segments [i].Tokens = tokens;
 184                         }
 185
 186                         if (allTokens.Count > 0)
 187                                 this.tokens = allTokens.ToArray ();
 188                         allTokens = null;
 189                 }
 190
 191                 RouteValueDictionary AddDefaults (RouteValueDictionary dict, RouteValueDictionary defaults)
 192                 {
 193                         if (defaults != null && defaults.Count > 0) {
 194                                 string key;
 195                                 foreach (var def in defaults) {
 196                                         key = def.Key;
 197                                         if (dict.ContainsKey (key))
 198                                                 continue;
 199                                         dict.Add (key, def.Value);
 200                                 }
 201                         }
 202
 203                         return dict;
 204                 }
 205
 206                 public RouteValueDictionary Match (string path, RouteValueDictionary defaults)
 207                 {
 208                         var ret = new RouteValueDictionary ();
 209                         string url = Url;
 210                         string [] argSegs;
 211                         int argsCount;
 212
 213                         if (String.IsNullOrEmpty (path)) {
 214                                 argSegs = null;
 215                                 argsCount = 0;
 216                         } else {
 217                                 // quick check
 218                                 if (String.Compare (url, path, StringComparison.Ordinal) == 0 && url.IndexOf ('{') < 0)
 219                                         return AddDefaults (ret, defaults);
 220
 221                                 argSegs = path.Split ('/');
 222                                 argsCount = argSegs.Length;
 223                         }
 224
 225                         bool haveDefaults = defaults != null && defaults.Count > 0;
 226
 227                         if (argsCount == 1 && String.IsNullOrEmpty (argSegs [0]))
 228                                 argsCount = 0;
 229
 230                         if (!haveDefaults && ((haveSegmentWithCatchAll && argsCount < segmentCount) || (!haveSegmentWithCatchAll && argsCount != segmentCount)))
 231                                 return null;
 232
 233                         int i = 0;
 234
 235                         foreach (PatternSegment segment in segments) {
 236                                 if (i >= argsCount)
 237                                         break;
 238
 239                                 if (segment.AllLiteral) {
 240                                         if (String.Compare (argSegs [i], segment.Tokens [0].Name, StringComparison.OrdinalIgnoreCase) != 0)
 241                                                 return null;
 242                                         i++;
 243                                         continue;
 244                                 }
 245
 246                                 string pathSegment = argSegs [i];
 247                                 int pathSegmentLength = pathSegment != null ? pathSegment.Length : -1;
 248                                 int pathIndex = 0;
 249                                 PatternTokenType tokenType;
 250                                 List <PatternToken> tokens = segment.Tokens;
 251                                 int tokensCount = tokens.Count;
 252
 253                                 // Process the path segments ignoring the defaults
 254                                 for (int tokenIndex = 0; tokenIndex < tokensCount; tokenIndex++) {
 255                                         var token = tokens [tokenIndex];
 256                                         if (pathIndex > pathSegmentLength - 1)
 257                                                 return null;
 258
 259                                         tokenType = token.Type;
 260                                         var tokenName = token.Name;
 261
 262                                         // Catch-all
 263                                         if (i > segmentCount - 1 || tokenType == PatternTokenType.CatchAll) {
 264                                                 if (tokenType != PatternTokenType.CatchAll)
 265                                                         return null;
 266
 267                                                 StringBuilder sb = new StringBuilder ();
 268                                                 for (int j = i; j < argsCount; j++) {
 269                                                         if (j > i)
 270                                                                 sb.Append ('/');
 271                                                         sb.Append (argSegs [j]);
 272                                                 }
 273
 274                                                 ret.Add (tokenName, sb.ToString ());
 275                                                 break;
 276                                         }
 277
 278                                         // Literal sections
 279                                         if (token.Type == PatternTokenType.Literal) {
 280                                                 int nameLen = tokenName.Length;
 281                                                 if (pathSegmentLength < nameLen || String.Compare (pathSegment, pathIndex, tokenName, 0, nameLen, StringComparison.OrdinalIgnoreCase) != 0)
 282                                                         return null;
 283                                                 pathIndex += nameLen;
 284                                                 continue;
 285                                         }
 286
 287                                         int nextTokenIndex = tokenIndex + 1;
 288                                         if (nextTokenIndex >= tokensCount) {
 289                                                 // Last token
 290                                                 ret.Add (tokenName, pathSegment.Substring (pathIndex));
 291                                                 continue;
 292                                         }
 293
 294                                         // Next token is a literal - greedy matching. It seems .NET
 295                                         // uses a simple and naive algorithm here which finds the
 296                                         // last ocurrence of the next section literal and assigns
 297                                         // everything before that to this token. See the
 298                                         // GetRouteData28 test in RouteTest.cs
 299                                         var nextToken = tokens [nextTokenIndex];
 300                                         string nextTokenName = nextToken.Name;
 301                                         int lastIndex = pathSegment.LastIndexOf (nextTokenName, pathSegmentLength - 1, pathSegmentLength - pathIndex, StringComparison.OrdinalIgnoreCase);
 302                                         if (lastIndex == -1)
 303                                                 return null;
 304
 305                                         int copyLength = lastIndex - pathIndex;
 306                                         string sectionValue = pathSegment.Substring (pathIndex, copyLength);
 307                                         if (String.IsNullOrEmpty (sectionValue))
 308                                                 return null;
 309
 310                                         ret.Add (tokenName, sectionValue);
 311                                         pathIndex += copyLength;
 312                                 }
 313                                 i++;
 314                         }
 315
 316                         // Check the remaining segments, if any, and see if they are required
 317                         //
 318                         // If a segment has more than one section (i.e. there's at least one
 319                         // literal, then it cannot match defaults
 320                         //
 321                         // All of the remaining segments must have all defaults provided and they
 322                         // must not be literals or the match will fail.
 323                         if (i < segmentCount) {
 324                                 if (!haveDefaults)
 325                                         return null;
 326
 327                                 for (;i < segmentCount; i++) {
 328                                         var segment = segments [i];
 329                                         if (segment.AllLiteral)
 330                                                 return null;
 331
 332                                         var tokens = segment.Tokens;
 333                                         if (tokens.Count != 1)
 334                                                 return null;
 335
 336                                         if (!defaults.ContainsKey (tokens [0].Name))
 337                                                 return null;
 338                                 }
 339                         }
 340
 341                         return AddDefaults (ret, defaults);
 342                 }
 343
 344                 public bool BuildUrl (Route route, RequestContext requestContext, RouteValueDictionary userValues, out string value)
 345                 {
 346                         value = null;
 347                         if (requestContext == null)
 348                                 return false;
 349
 350                         RouteData routeData = requestContext.RouteData;
 351                         RouteValueDictionary defaultValues = route != null ? route.Defaults : null;
 352                         RouteValueDictionary ambientValues = routeData.Values;
 353
 354                         if (defaultValues != null && defaultValues.Count == 0)
 355                                 defaultValues = null;
 356                         if (ambientValues != null && ambientValues.Count == 0)
 357                                 ambientValues = null;
 358                         if (userValues != null && userValues.Count == 0)
 359                                 userValues = null;
 360
 361                         // Check URL parameters
 362                         // It is allowed to take ambient values for required parameters if:
 363                         //
 364                         //   - there are no default values provided
 365                         //   - the default values dictionary contains at least one required
 366                         //     parameter value
 367                         //
 368                         bool canTakeFromAmbient;
 369                         if (defaultValues == null)
 370                                 canTakeFromAmbient = true;
 371                         else {
 372                                 canTakeFromAmbient = false;
 373                                 foreach (KeyValuePair <string, bool> de in parameterNames) {
 374                                         if (defaultValues.ContainsKey (de.Key)) {
 375                                                 canTakeFromAmbient = true;
 376                                                 break;
 377                                         }
 378                                 }
 379                         }
 380
 381                         bool allMustBeInUserValues = false;
 382                         foreach (KeyValuePair <string, bool> de in parameterNames) {
 383                                 string parameterName = de.Key;
 384                                 // Is the parameter required?
 385                                 if (defaultValues == null || !defaultValues.ContainsKey (parameterName)) {
 386                                         // Yes, it is required (no value in defaults)
 387                                         // Has the user provided value for it?
 388                                         if (userValues == null || !userValues.ContainsKey (parameterName)) {
 389                                                 if (allMustBeInUserValues)
 390                                                         return false; // partial override => no match
 391
 392                                                 if (!canTakeFromAmbient || ambientValues == null || !ambientValues.ContainsKey (parameterName))
 393                                                         return false; // no value provided => no match
 394                                         } else if (canTakeFromAmbient)
 395                                                 allMustBeInUserValues = true;
 396                                 }
 397                         }
 398
 399                         // Check for non-url parameters
 400                         if (defaultValues != null) {
 401                                 foreach (var de in defaultValues) {
 402                                         string parameterName = de.Key;
 403
 404                                         if (parameterNames.ContainsKey (parameterName))
 405                                                 continue;
 406
 407                                         object parameterValue = null;
 408                                         // Has the user specified value for this parameter and, if
 409                                         // yes, is it the same as the one in defaults?
 410                                         if (userValues != null && userValues.TryGetValue (parameterName, out parameterValue)) {
 411                                                 object defaultValue = de.Value;
 412                                                 if (defaultValue is string && parameterValue is string) {
 413                                                         if (String.Compare ((string)defaultValue, (string)parameterValue, StringComparison.Ordinal) != 0)
 414                                                                 return false; // different value => no match
 415                                                 } else if (defaultValue != parameterValue)
 416                                                         return false; // different value => no match
 417                                         }
 418                                 }
 419                         }
 420
 421                         // Check the constraints
 422                         RouteValueDictionary constraints = route != null ? route.Constraints : null;
 423                         if (constraints != null && constraints.Count > 0) {
 424                                 HttpContextBase context = requestContext.HttpContext;
 425                                 bool invalidConstraint;
 426
 427                                 foreach (var de in constraints) {
 428                                         if (!Route.ProcessConstraintInternal (context, route, de.Value, de.Key, userValues, RouteDirection.UrlGeneration, out invalidConstraint) ||
 429                                             invalidConstraint)
 430                                                 return false; // constraint not met => no match
 431                                 }
 432                         }
 433
 434                         // We're a match, generate the URL
 435                         var ret = new StringBuilder ();
 436                         bool canTrim = true;
 437
 438                         // Going in reverse order, so that we can trim without much ado
 439                         int tokensCount = tokens.Length - 1;
 440                         for (int i = tokensCount; i >= 0; i--) {
 441                                 PatternToken token = tokens [i];
 442                                 if (token == null) {
 443                                         if (i < tokensCount && ret.Length > 0 && ret [0] != '/')
 444                                                 ret.Insert (0, '/');
 445                                         continue;
 446                                 }
 447
 448                                 if (token.Type == PatternTokenType.Literal) {
 449                                         ret.Insert (0, token.Name);
 450                                         continue;
 451                                 }
 452
 453                                 string parameterName = token.Name;
 454                                 object tokenValue;
 455
 456                                 if (userValues.GetValue (parameterName, out tokenValue)) {
 457                                         if (!defaultValues.Has (parameterName, tokenValue)) {
 458                                                 canTrim = false;
 459                                                 if (tokenValue != null)
 460                                                         ret.Insert (0, tokenValue.ToString ());
 461                                                 continue;
 462                                         }
 463
 464                                         if (!canTrim && tokenValue != null)
 465                                                 ret.Insert (0, tokenValue.ToString ());
 466                                         continue;
 467                                 }
 468
 469                                 if (defaultValues.GetValue (parameterName, out tokenValue)) {
 470                                         object ambientTokenValue;
 471                                         if (ambientValues.GetValue (parameterName, out ambientTokenValue))
 472                                                 tokenValue = ambientTokenValue;
 473
 474                                         if (!canTrim && tokenValue != null)
 475                                                 ret.Insert (0, tokenValue.ToString ());
 476                                         continue;
 477                                 }
 478
 479                                 canTrim = false;
 480                                 if (ambientValues.GetValue (parameterName, out tokenValue)) {
 481                                         if (tokenValue != null)
 482                                                 ret.Insert (0, tokenValue.ToString ());
 483                                         continue;
 484                                 }
 485                         }
 486
 487                         // All the values specified in userValues that aren't part of the original
 488                         // URL, the constraints or defaults collections are treated as overflow
 489                         // values - they are appended as query parameters to the URL
 490                         if (userValues != null) {
 491                                 bool first = true;
 492                                 foreach (var de in userValues) {
 493                                         string parameterName = de.Key;
 494
 495                                         if (parameterNames.ContainsKey (parameterName) || defaultValues.Has (parameterName) || constraints.Has (parameterName))
 496                                                 continue;
 497
 498                                         if (first) {
 499                                                 ret.Append ('?');
 500                                                 first = false;
 501                                         } else
 502                                                 ret.Append ('&');
 503
 504                                         object parameterValue = de.Value;
 505                                         ret.Append (Uri.EscapeDataString (parameterName));
 506                                         ret.Append ('=');
 507                                         if (parameterValue != null)
 508                                                 ret.Append (Uri.EscapeDataString (de.Value.ToString ()));
 509                                 }
 510                         }
 511
 512                         value = ret.ToString ();
 513                         return true;
 514                 }
 515         }
 516 }
 517