urlmatch.c

   1 #include "cache.h"
   2 #include "urlmatch.h"
   3
   4 #define URL_ALPHA "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
   5 #define URL_DIGIT "0123456789"
   6 #define URL_ALPHADIGIT URL_ALPHA URL_DIGIT
   7 #define URL_SCHEME_CHARS URL_ALPHADIGIT "+.-"
   8 #define URL_HOST_CHARS URL_ALPHADIGIT ".-[:]" /* IPv6 literals need [:] */
   9 #define URL_UNSAFE_CHARS " <>\"%{}|\\^`" /* plus 0x00-0x1F,0x7F-0xFF */
  10 #define URL_GEN_RESERVED ":/?#[]@"
  11 #define URL_SUB_RESERVED "!$&'()*+,;="
  12 #define URL_RESERVED URL_GEN_RESERVED URL_SUB_RESERVED /* only allowed delims */
  13
  14 static int append_normalized_escapes(struct strbuf *buf,
  15                                      const char *from,
  16                                      size_t from_len,
  17                                      const char *esc_extra,
  18                                      const char *esc_ok)
  19 {
  20         /*
  21          * Append to strbuf 'buf' characters from string 'from' with length
  22          * 'from_len' while unescaping characters that do not need to be escaped
  23          * and escaping characters that do.  The set of characters to escape
  24          * (the complement of which is unescaped) starts out as the RFC 3986
  25          * unsafe characters (0x00-0x1F,0x7F-0xFF," <>\"#%{}|\\^`").  If
  26          * 'esc_extra' is not NULL, those additional characters will also always
  27          * be escaped.  If 'esc_ok' is not NULL, those characters will be left
  28          * escaped if found that way, but will not be unescaped otherwise (used
  29          * for delimiters).  If a %-escape sequence is encountered that is not
  30          * followed by 2 hexadecimal digits, the sequence is invalid and
  31          * false (0) will be returned.  Otherwise true (1) will be returned for
  32          * success.
  33          *
  34          * Note that all %-escape sequences will be normalized to UPPERCASE
  35          * as indicated in RFC 3986.  Unless included in esc_extra or esc_ok
  36          * alphanumerics and "-._~" will always be unescaped as per RFC 3986.
  37          */
  38
  39         while (from_len) {
  40                 int ch = *from++;
  41                 int was_esc = 0;
  42
  43                 from_len--;
  44                 if (ch == '%') {
  45                         if (from_len < 2)
  46                                 return 0;
  47                         ch = hex2chr(from);
  48                         if (ch < 0)
  49                                 return 0;
  50                         from += 2;
  51                         from_len -= 2;
  52                         was_esc = 1;
  53                 }
  54                 if ((unsigned char)ch <= 0x1F || (unsigned char)ch >= 0x7F ||
  55                     strchr(URL_UNSAFE_CHARS, ch) ||
  56                     (esc_extra && strchr(esc_extra, ch)) ||
  57                     (was_esc && strchr(esc_ok, ch)))
  58                         strbuf_addf(buf, "%%%02X", (unsigned char)ch);
  59                 else
  60                         strbuf_addch(buf, ch);
  61         }
  62
  63         return 1;
  64 }
  65
  66 static const char *end_of_token(const char *s, int c, size_t n)
  67 {
  68         const char *next = memchr(s, c, n);
  69         if (!next)
  70                 next = s + n;
  71         return next;
  72 }
  73
  74 static int match_host(const struct url_info *url_info,
  75                       const struct url_info *pattern_info)
  76 {
  77         const char *url = url_info->url + url_info->host_off;
  78         const char *pat = pattern_info->url + pattern_info->host_off;
  79         int url_len = url_info->host_len;
  80         int pat_len = pattern_info->host_len;
  81
  82         while (url_len && pat_len) {
  83                 const char *url_next = end_of_token(url, '.', url_len);
  84                 const char *pat_next = end_of_token(pat, '.', pat_len);
  85
  86                 if (pat_next == pat + 1 && pat[0] == '*')
  87                         /* wildcard matches anything */
  88                         ;
  89                 else if ((pat_next - pat) == (url_next - url) &&
  90                          !memcmp(url, pat, url_next - url))
  91                         /* the components are the same */
  92                         ;
  93                 else
  94                         return 0; /* found an unmatch */
  95
  96                 if (url_next < url + url_len)
  97                         url_next++;
  98                 url_len -= url_next - url;
  99                 url = url_next;
 100                 if (pat_next < pat + pat_len)
 101                         pat_next++;
 102                 pat_len -= pat_next - pat;
 103                 pat = pat_next;
 104         }
 105
 106         return (!url_len && !pat_len);
 107 }
 108
 109 static char *url_normalize_1(const char *url, struct url_info *out_info, char allow_globs)
 110 {
 111         /*
 112          * Normalize NUL-terminated url using the following rules:
 113          *
 114          * 1. Case-insensitive parts of url will be converted to lower case
 115          * 2. %-encoded characters that do not need to be will be unencoded
 116          * 3. Characters that are not %-encoded and must be will be encoded
 117          * 4. All %-encodings will be converted to upper case hexadecimal
 118          * 5. Leading 0s are removed from port numbers
 119          * 6. If the default port for the scheme is given it will be removed
 120          * 7. A path part (including empty) not starting with '/' has one added
 121          * 8. Any dot segments (. or ..) in the path are resolved and removed
 122          * 9. IPv6 host literals are allowed (but not normalized or validated)
 123          *
 124          * The rules are based on information in RFC 3986.
 125          *
 126          * Please note this function requires a full URL including a scheme
 127          * and host part (except for file: URLs which may have an empty host).
 128          *
 129          * The return value is a newly allocated string that must be freed
 130          * or NULL if the url is not valid.
 131          *
 132          * If out_info is non-NULL, the url and err fields therein will always
 133          * be set.  If a non-NULL value is returned, it will be stored in
 134          * out_info->url as well, out_info->err will be set to NULL and the
 135          * other fields of *out_info will also be filled in.  If a NULL value
 136          * is returned, NULL will be stored in out_info->url and out_info->err
 137          * will be set to a brief, translated, error message, but no other
 138          * fields will be filled in.
 139          *
 140          * This is NOT a URL validation function.  Full URL validation is NOT
 141          * performed.  Some invalid host names are passed through this function
 142          * undetected.  However, most all other problems that make a URL invalid
 143          * will be detected (including a missing host for non file: URLs).
 144          */
 145
 146         size_t url_len = strlen(url);
 147         struct strbuf norm;
 148         size_t spanned;
 149         size_t scheme_len, user_off=0, user_len=0, passwd_off=0, passwd_len=0;
 150         size_t host_off=0, host_len=0, port_off=0, port_len=0, path_off, path_len, result_len;
 151         const char *slash_ptr, *at_ptr, *colon_ptr, *path_start;
 152         char *result;
 153
 154         /*
 155          * Copy lowercased scheme and :// suffix, %-escapes are not allowed
 156          * First character of scheme must be URL_ALPHA
 157          */
 158         spanned = strspn(url, URL_SCHEME_CHARS);
 159         if (!spanned || !isalpha(url[0]) || spanned + 3 > url_len ||
 160             url[spanned] != ':' || url[spanned+1] != '/' || url[spanned+2] != '/') {
 161                 if (out_info) {
 162                         out_info->url = NULL;
 163                         out_info->err = _("invalid URL scheme name or missing '://' suffix");
 164                 }
 165                 return NULL; /* Bad scheme and/or missing "://" part */
 166         }
 167         strbuf_init(&norm, url_len);
 168         scheme_len = spanned;
 169         spanned += 3;
 170         url_len -= spanned;
 171         while (spanned--)
 172                 strbuf_addch(&norm, tolower(*url++));
 173
 174
 175         /*
 176          * Copy any username:password if present normalizing %-escapes
 177          */
 178         at_ptr = strchr(url, '@');
 179         slash_ptr = url + strcspn(url, "/?#");
 180         if (at_ptr && at_ptr < slash_ptr) {
 181                 user_off = norm.len;
 182                 if (at_ptr > url) {
 183                         if (!append_normalized_escapes(&norm, url, at_ptr - url,
 184                                                        "", URL_RESERVED)) {
 185                                 if (out_info) {
 186                                         out_info->url = NULL;
 187                                         out_info->err = _("invalid %XX escape sequence");
 188                                 }
 189                                 strbuf_release(&norm);
 190                                 return NULL;
 191                         }
 192                         colon_ptr = strchr(norm.buf + scheme_len + 3, ':');
 193                         if (colon_ptr) {
 194                                 passwd_off = (colon_ptr + 1) - norm.buf;
 195                                 passwd_len = norm.len - passwd_off;
 196                                 user_len = (passwd_off - 1) - (scheme_len + 3);
 197                         } else {
 198                                 user_len = norm.len - (scheme_len + 3);
 199                         }
 200                 }
 201                 strbuf_addch(&norm, '@');
 202                 url_len -= (++at_ptr - url);
 203                 url = at_ptr;
 204         }
 205
 206
 207         /*
 208          * Copy the host part excluding any port part, no %-escapes allowed
 209          */
 210         if (!url_len || strchr(":/?#", *url)) {
 211                 /* Missing host invalid for all URL schemes except file */
 212                 if (strncmp(norm.buf, "file:", 5)) {
 213                         if (out_info) {
 214                                 out_info->url = NULL;
 215                                 out_info->err = _("missing host and scheme is not 'file:'");
 216                         }
 217                         strbuf_release(&norm);
 218                         return NULL;
 219                 }
 220         } else {
 221                 host_off = norm.len;
 222         }
 223         colon_ptr = slash_ptr - 1;
 224         while (colon_ptr > url && *colon_ptr != ':' && *colon_ptr != ']')
 225                 colon_ptr--;
 226         if (*colon_ptr != ':') {
 227                 colon_ptr = slash_ptr;
 228         } else if (!host_off && colon_ptr < slash_ptr && colon_ptr + 1 != slash_ptr) {
 229                 /* file: URLs may not have a port number */
 230                 if (out_info) {
 231                         out_info->url = NULL;
 232                         out_info->err = _("a 'file:' URL may not have a port number");
 233                 }
 234                 strbuf_release(&norm);
 235                 return NULL;
 236         }
 237
 238         if (allow_globs)
 239                 spanned = strspn(url, URL_HOST_CHARS "*");
 240         else
 241                 spanned = strspn(url, URL_HOST_CHARS);
 242
 243         if (spanned < colon_ptr - url) {
 244                 /* Host name has invalid characters */
 245                 if (out_info) {
 246                         out_info->url = NULL;
 247                         out_info->err = _("invalid characters in host name");
 248                 }
 249                 strbuf_release(&norm);
 250                 return NULL;
 251         }
 252         while (url < colon_ptr) {
 253                 strbuf_addch(&norm, tolower(*url++));
 254                 url_len--;
 255         }
 256
 257
 258         /*
 259          * Check the port part and copy if not the default (after removing any
 260          * leading 0s); no %-escapes allowed
 261          */
 262         if (colon_ptr < slash_ptr) {
 263                 /* skip the ':' and leading 0s but not the last one if all 0s */
 264                 url++;
 265                 url += strspn(url, "0");
 266                 if (url == slash_ptr && url[-1] == '0')
 267                         url--;
 268                 if (url == slash_ptr) {
 269                         /* Skip ":" port with no number, it's same as default */
 270                 } else if (slash_ptr - url == 2 &&
 271                            !strncmp(norm.buf, "http:", 5) &&
 272                            !strncmp(url, "80", 2)) {
 273                         /* Skip http :80 as it's the default */
 274                 } else if (slash_ptr - url == 3 &&
 275                            !strncmp(norm.buf, "https:", 6) &&
 276                            !strncmp(url, "443", 3)) {
 277                         /* Skip https :443 as it's the default */
 278                 } else {
 279                         /*
 280                          * Port number must be all digits with leading 0s removed
 281                          * and since all the protocols we deal with have a 16-bit
 282                          * port number it must also be in the range 1..65535
 283                          * 0 is not allowed because that means "next available"
 284                          * on just about every system and therefore cannot be used
 285                          */
 286                         unsigned long pnum = 0;
 287                         spanned = strspn(url, URL_DIGIT);
 288                         if (spanned < slash_ptr - url) {
 289                                 /* port number has invalid characters */
 290                                 if (out_info) {
 291                                         out_info->url = NULL;
 292                                         out_info->err = _("invalid port number");
 293                                 }
 294                                 strbuf_release(&norm);
 295                                 return NULL;
 296                         }
 297                         if (slash_ptr - url <= 5)
 298                                 pnum = strtoul(url, NULL, 10);
 299                         if (pnum == 0 || pnum > 65535) {
 300                                 /* port number not in range 1..65535 */
 301                                 if (out_info) {
 302                                         out_info->url = NULL;
 303                                         out_info->err = _("invalid port number");
 304                                 }
 305                                 strbuf_release(&norm);
 306                                 return NULL;
 307                         }
 308                         strbuf_addch(&norm, ':');
 309                         port_off = norm.len;
 310                         strbuf_add(&norm, url, slash_ptr - url);
 311                         port_len = slash_ptr - url;
 312                 }
 313                 url_len -= slash_ptr - colon_ptr;
 314                 url = slash_ptr;
 315         }
 316         if (host_off)
 317                 host_len = norm.len - host_off - (port_len ? port_len + 1 : 0);
 318
 319
 320         /*
 321          * Now copy the path resolving any . and .. segments being careful not
 322          * to corrupt the URL by unescaping any delimiters, but do add an
 323          * initial '/' if it's missing and do normalize any %-escape sequences.
 324          */
 325         path_off = norm.len;
 326         path_start = norm.buf + path_off;
 327         strbuf_addch(&norm, '/');
 328         if (*url == '/') {
 329                 url++;
 330                 url_len--;
 331         }
 332         for (;;) {
 333                 const char *seg_start;
 334                 size_t seg_start_off = norm.len;
 335                 const char *next_slash = url + strcspn(url, "/?#");
 336                 int skip_add_slash = 0;
 337
 338                 /*
 339                  * RFC 3689 indicates that any . or .. segments should be
 340                  * unescaped before being checked for.
 341                  */
 342                 if (!append_normalized_escapes(&norm, url, next_slash - url, "",
 343                                                URL_RESERVED)) {
 344                         if (out_info) {
 345                                 out_info->url = NULL;
 346                                 out_info->err = _("invalid %XX escape sequence");
 347                         }
 348                         strbuf_release(&norm);
 349                         return NULL;
 350                 }
 351
 352                 seg_start = norm.buf + seg_start_off;
 353                 if (!strcmp(seg_start, ".")) {
 354                         /* ignore a . segment; be careful not to remove initial '/' */
 355                         if (seg_start == path_start + 1) {
 356                                 strbuf_setlen(&norm, norm.len - 1);
 357                                 skip_add_slash = 1;
 358                         } else {
 359                                 strbuf_setlen(&norm, norm.len - 2);
 360                         }
 361                 } else if (!strcmp(seg_start, "..")) {
 362                         /*
 363                          * ignore a .. segment and remove the previous segment;
 364                          * be careful not to remove initial '/' from path
 365                          */
 366                         const char *prev_slash = norm.buf + norm.len - 3;
 367                         if (prev_slash == path_start) {
 368                                 /* invalid .. because no previous segment to remove */
 369                                 if (out_info) {
 370                                         out_info->url = NULL;
 371                                         out_info->err = _("invalid '..' path segment");
 372                                 }
 373                                 strbuf_release(&norm);
 374                                 return NULL;
 375                         }
 376                         while (*--prev_slash != '/') {}
 377                         if (prev_slash == path_start) {
 378                                 strbuf_setlen(&norm, prev_slash - norm.buf + 1);
 379                                 skip_add_slash = 1;
 380                         } else {
 381                                 strbuf_setlen(&norm, prev_slash - norm.buf);
 382                         }
 383                 }
 384                 url_len -= next_slash - url;
 385                 url = next_slash;
 386                 /* if the next char is not '/' done with the path */
 387                 if (*url != '/')
 388                         break;
 389                 url++;
 390                 url_len--;
 391                 if (!skip_add_slash)
 392                         strbuf_addch(&norm, '/');
 393         }
 394         path_len = norm.len - path_off;
 395
 396
 397         /*
 398          * Now simply copy the rest, if any, only normalizing %-escapes and
 399          * being careful not to corrupt the URL by unescaping any delimiters.
 400          */
 401         if (*url) {
 402                 if (!append_normalized_escapes(&norm, url, url_len, "", URL_RESERVED)) {
 403                         if (out_info) {
 404                                 out_info->url = NULL;
 405                                 out_info->err = _("invalid %XX escape sequence");
 406                         }
 407                         strbuf_release(&norm);
 408                         return NULL;
 409                 }
 410         }
 411
 412
 413         result = strbuf_detach(&norm, &result_len);
 414         if (out_info) {
 415                 out_info->url = result;
 416                 out_info->err = NULL;
 417                 out_info->url_len = result_len;
 418                 out_info->scheme_len = scheme_len;
 419                 out_info->user_off = user_off;
 420                 out_info->user_len = user_len;
 421                 out_info->passwd_off = passwd_off;
 422                 out_info->passwd_len = passwd_len;
 423                 out_info->host_off = host_off;
 424                 out_info->host_len = host_len;
 425                 out_info->port_off = port_off;
 426                 out_info->port_len = port_len;
 427                 out_info->path_off = path_off;
 428                 out_info->path_len = path_len;
 429         }
 430         return result;
 431 }
 432
 433 char *url_normalize(const char *url, struct url_info *out_info)
 434 {
 435         return url_normalize_1(url, out_info, 0);
 436 }
 437
 438 static size_t url_match_prefix(const char *url,
 439                                const char *url_prefix,
 440                                size_t url_prefix_len)
 441 {
 442         /*
 443          * url_prefix matches url if url_prefix is an exact match for url or it
 444          * is a prefix of url and the match ends on a path component boundary.
 445          * Both url and url_prefix are considered to have an implicit '/' on the
 446          * end for matching purposes if they do not already.
 447          *
 448          * url must be NUL terminated.  url_prefix_len is the length of
 449          * url_prefix which need not be NUL terminated.
 450          *
 451          * The return value is the length of the match in characters (including
 452          * the final '/' even if it's implicit) or 0 for no match.
 453          *
 454          * Passing NULL as url and/or url_prefix will always cause 0 to be
 455          * returned without causing any faults.
 456          */
 457         if (!url || !url_prefix)
 458                 return 0;
 459         if (!url_prefix_len || (url_prefix_len == 1 && *url_prefix == '/'))
 460                 return (!*url || *url == '/') ? 1 : 0;
 461         if (url_prefix[url_prefix_len - 1] == '/')
 462                 url_prefix_len--;
 463         if (strncmp(url, url_prefix, url_prefix_len))
 464                 return 0;
 465         if ((strlen(url) == url_prefix_len) || (url[url_prefix_len] == '/'))
 466                 return url_prefix_len + 1;
 467         return 0;
 468 }
 469
 470 static int match_urls(const struct url_info *url,
 471                       const struct url_info *url_prefix,
 472                       struct urlmatch_item *match)
 473 {
 474         /*
 475          * url_prefix matches url if the scheme, host and port of url_prefix
 476          * are the same as those of url and the path portion of url_prefix
 477          * is the same as the path portion of url or it is a prefix that
 478          * matches at a '/' boundary.  If url_prefix contains a user name,
 479          * that must also exactly match the user name in url.
 480          *
 481          * If the user, host, port and path match in this fashion, the returned
 482          * value is the length of the path match including any implicit
 483          * final '/'.  For example, "http://me@example.com/path" is matched by
 484          * "http://example.com" with a path length of 1.
 485          *
 486          * If there is a match and exactusermatch is not NULL, then
 487          * *exactusermatch will be set to true if both url and url_prefix
 488          * contained a user name or false if url_prefix did not have a
 489          * user name.  If there is no match *exactusermatch is left untouched.
 490          */
 491         char usermatched = 0;
 492         size_t pathmatchlen;
 493
 494         if (!url || !url_prefix || !url->url || !url_prefix->url)
 495                 return 0;
 496
 497         /* check the scheme */
 498         if (url_prefix->scheme_len != url->scheme_len ||
 499             strncmp(url->url, url_prefix->url, url->scheme_len))
 500                 return 0; /* schemes do not match */
 501
 502         /* check the user name if url_prefix has one */
 503         if (url_prefix->user_off) {
 504                 if (!url->user_off || url->user_len != url_prefix->user_len ||
 505                     strncmp(url->url + url->user_off,
 506                             url_prefix->url + url_prefix->user_off,
 507                             url->user_len))
 508                         return 0; /* url_prefix has a user but it's not a match */
 509                 usermatched = 1;
 510         }
 511
 512         /* check the host */
 513         if (!match_host(url, url_prefix))
 514                 return 0; /* host names do not match */
 515
 516         /* check the port */
 517         if (url_prefix->port_len != url->port_len ||
 518             strncmp(url->url + url->port_off,
 519                     url_prefix->url + url_prefix->port_off, url->port_len))
 520                 return 0; /* ports do not match */
 521
 522         /* check the path */
 523         pathmatchlen = url_match_prefix(
 524                 url->url + url->path_off,
 525                 url_prefix->url + url_prefix->path_off,
 526                 url_prefix->url_len - url_prefix->path_off);
 527         if (!pathmatchlen)
 528                 return 0; /* paths do not match */
 529
 530         if (match) {
 531                 match->hostmatch_len = url_prefix->host_len;
 532                 match->pathmatch_len = pathmatchlen;
 533                 match->user_matched = usermatched;
 534         }
 535
 536         return 1;
 537 }
 538
 539 static int cmp_matches(const struct urlmatch_item *a,
 540                        const struct urlmatch_item *b)
 541 {
 542         if (a->hostmatch_len != b->hostmatch_len)
 543                 return a->hostmatch_len < b->hostmatch_len ? -1 : 1;
 544         if (a->pathmatch_len != b->pathmatch_len)
 545                 return a->pathmatch_len < b->pathmatch_len ? -1 : 1;
 546         if (a->user_matched != b->user_matched)
 547                 return b->user_matched ? -1 : 1;
 548         return 0;
 549 }
 550
 551 int urlmatch_config_entry(const char *var, const char *value, void *cb)
 552 {
 553         struct string_list_item *item;
 554         struct urlmatch_config *collect = cb;
 555         struct urlmatch_item matched = {0};
 556         struct url_info *url = &collect->url;
 557         const char *key, *dot;
 558         struct strbuf synthkey = STRBUF_INIT;
 559         int retval;
 560         int (*select_fn)(const struct urlmatch_item *a, const struct urlmatch_item *b) =
 561                 collect->select_fn ? collect->select_fn : cmp_matches;
 562
 563         if (!skip_prefix(var, collect->section, &key) || *(key++) != '.') {
 564                 if (collect->cascade_fn)
 565                         return collect->cascade_fn(var, value, cb);
 566                 return 0; /* not interested */
 567         }
 568         dot = strrchr(key, '.');
 569         if (dot) {
 570                 char *config_url, *norm_url;
 571                 struct url_info norm_info;
 572
 573                 config_url = xmemdupz(key, dot - key);
 574                 norm_url = url_normalize_1(config_url, &norm_info, 1);
 575                 if (norm_url)
 576                         retval = match_urls(url, &norm_info, &matched);
 577                 else if (collect->fallback_match_fn)
 578                         retval = collect->fallback_match_fn(config_url,
 579                                                             collect->cb);
 580                 else
 581                         retval = 0;
 582                 free(config_url);
 583                 free(norm_url);
 584                 if (!retval)
 585                         return 0;
 586                 key = dot + 1;
 587         }
 588
 589         if (collect->key && strcmp(key, collect->key))
 590                 return 0;
 591
 592         item = string_list_insert(&collect->vars, key);
 593         if (!item->util) {
 594                 item->util = xcalloc(1, sizeof(matched));
 595         } else {
 596                 if (select_fn(&matched, item->util) < 0)
 597                          /*
 598                           * Our match is worse than the old one,
 599                           * we cannot use it.
 600                           */
 601                         return 0;
 602                 /* Otherwise, replace it with this one. */
 603         }
 604
 605         memcpy(item->util, &matched, sizeof(matched));
 606         strbuf_addstr(&synthkey, collect->section);
 607         strbuf_addch(&synthkey, '.');
 608         strbuf_addstr(&synthkey, key);
 609         retval = collect->collect_fn(synthkey.buf, value, collect->cb);
 610
 611         strbuf_release(&synthkey);
 612         return retval;
 613 }