Merge branch 'cb/filter-branch-prune-empty-degenerate-merges'
[git] / 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                             !isxdigit((unsigned char)from[0]) ||
47                             !isxdigit((unsigned char)from[1]))
48                                 return 0;
49                         ch = hexval_table[(unsigned char)*from++] << 4;
50                         ch |= hexval_table[(unsigned char)*from++];
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 char *url_normalize(const char *url, struct url_info *out_info)
67 {
68         /*
69          * Normalize NUL-terminated url using the following rules:
70          *
71          * 1. Case-insensitive parts of url will be converted to lower case
72          * 2. %-encoded characters that do not need to be will be unencoded
73          * 3. Characters that are not %-encoded and must be will be encoded
74          * 4. All %-encodings will be converted to upper case hexadecimal
75          * 5. Leading 0s are removed from port numbers
76          * 6. If the default port for the scheme is given it will be removed
77          * 7. A path part (including empty) not starting with '/' has one added
78          * 8. Any dot segments (. or ..) in the path are resolved and removed
79          * 9. IPv6 host literals are allowed (but not normalized or validated)
80          *
81          * The rules are based on information in RFC 3986.
82          *
83          * Please note this function requires a full URL including a scheme
84          * and host part (except for file: URLs which may have an empty host).
85          *
86          * The return value is a newly allocated string that must be freed
87          * or NULL if the url is not valid.
88          *
89          * If out_info is non-NULL, the url and err fields therein will always
90          * be set.  If a non-NULL value is returned, it will be stored in
91          * out_info->url as well, out_info->err will be set to NULL and the
92          * other fields of *out_info will also be filled in.  If a NULL value
93          * is returned, NULL will be stored in out_info->url and out_info->err
94          * will be set to a brief, translated, error message, but no other
95          * fields will be filled in.
96          *
97          * This is NOT a URL validation function.  Full URL validation is NOT
98          * performed.  Some invalid host names are passed through this function
99          * undetected.  However, most all other problems that make a URL invalid
100          * will be detected (including a missing host for non file: URLs).
101          */
102
103         size_t url_len = strlen(url);
104         struct strbuf norm;
105         size_t spanned;
106         size_t scheme_len, user_off=0, user_len=0, passwd_off=0, passwd_len=0;
107         size_t host_off=0, host_len=0, port_len=0, path_off, path_len, result_len;
108         const char *slash_ptr, *at_ptr, *colon_ptr, *path_start;
109         char *result;
110
111         /*
112          * Copy lowercased scheme and :// suffix, %-escapes are not allowed
113          * First character of scheme must be URL_ALPHA
114          */
115         spanned = strspn(url, URL_SCHEME_CHARS);
116         if (!spanned || !isalpha(url[0]) || spanned + 3 > url_len ||
117             url[spanned] != ':' || url[spanned+1] != '/' || url[spanned+2] != '/') {
118                 if (out_info) {
119                         out_info->url = NULL;
120                         out_info->err = _("invalid URL scheme name or missing '://' suffix");
121                 }
122                 return NULL; /* Bad scheme and/or missing "://" part */
123         }
124         strbuf_init(&norm, url_len);
125         scheme_len = spanned;
126         spanned += 3;
127         url_len -= spanned;
128         while (spanned--)
129                 strbuf_addch(&norm, tolower(*url++));
130
131
132         /*
133          * Copy any username:password if present normalizing %-escapes
134          */
135         at_ptr = strchr(url, '@');
136         slash_ptr = url + strcspn(url, "/?#");
137         if (at_ptr && at_ptr < slash_ptr) {
138                 user_off = norm.len;
139                 if (at_ptr > url) {
140                         if (!append_normalized_escapes(&norm, url, at_ptr - url,
141                                                        "", URL_RESERVED)) {
142                                 if (out_info) {
143                                         out_info->url = NULL;
144                                         out_info->err = _("invalid %XX escape sequence");
145                                 }
146                                 strbuf_release(&norm);
147                                 return NULL;
148                         }
149                         colon_ptr = strchr(norm.buf + scheme_len + 3, ':');
150                         if (colon_ptr) {
151                                 passwd_off = (colon_ptr + 1) - norm.buf;
152                                 passwd_len = norm.len - passwd_off;
153                                 user_len = (passwd_off - 1) - (scheme_len + 3);
154                         } else {
155                                 user_len = norm.len - (scheme_len + 3);
156                         }
157                 }
158                 strbuf_addch(&norm, '@');
159                 url_len -= (++at_ptr - url);
160                 url = at_ptr;
161         }
162
163
164         /*
165          * Copy the host part excluding any port part, no %-escapes allowed
166          */
167         if (!url_len || strchr(":/?#", *url)) {
168                 /* Missing host invalid for all URL schemes except file */
169                 if (strncmp(norm.buf, "file:", 5)) {
170                         if (out_info) {
171                                 out_info->url = NULL;
172                                 out_info->err = _("missing host and scheme is not 'file:'");
173                         }
174                         strbuf_release(&norm);
175                         return NULL;
176                 }
177         } else {
178                 host_off = norm.len;
179         }
180         colon_ptr = slash_ptr - 1;
181         while (colon_ptr > url && *colon_ptr != ':' && *colon_ptr != ']')
182                 colon_ptr--;
183         if (*colon_ptr != ':') {
184                 colon_ptr = slash_ptr;
185         } else if (!host_off && colon_ptr < slash_ptr && colon_ptr + 1 != slash_ptr) {
186                 /* file: URLs may not have a port number */
187                 if (out_info) {
188                         out_info->url = NULL;
189                         out_info->err = _("a 'file:' URL may not have a port number");
190                 }
191                 strbuf_release(&norm);
192                 return NULL;
193         }
194         spanned = strspn(url, URL_HOST_CHARS);
195         if (spanned < colon_ptr - url) {
196                 /* Host name has invalid characters */
197                 if (out_info) {
198                         out_info->url = NULL;
199                         out_info->err = _("invalid characters in host name");
200                 }
201                 strbuf_release(&norm);
202                 return NULL;
203         }
204         while (url < colon_ptr) {
205                 strbuf_addch(&norm, tolower(*url++));
206                 url_len--;
207         }
208
209
210         /*
211          * Check the port part and copy if not the default (after removing any
212          * leading 0s); no %-escapes allowed
213          */
214         if (colon_ptr < slash_ptr) {
215                 /* skip the ':' and leading 0s but not the last one if all 0s */
216                 url++;
217                 url += strspn(url, "0");
218                 if (url == slash_ptr && url[-1] == '0')
219                         url--;
220                 if (url == slash_ptr) {
221                         /* Skip ":" port with no number, it's same as default */
222                 } else if (slash_ptr - url == 2 &&
223                            !strncmp(norm.buf, "http:", 5) &&
224                            !strncmp(url, "80", 2)) {
225                         /* Skip http :80 as it's the default */
226                 } else if (slash_ptr - url == 3 &&
227                            !strncmp(norm.buf, "https:", 6) &&
228                            !strncmp(url, "443", 3)) {
229                         /* Skip https :443 as it's the default */
230                 } else {
231                         /*
232                          * Port number must be all digits with leading 0s removed
233                          * and since all the protocols we deal with have a 16-bit
234                          * port number it must also be in the range 1..65535
235                          * 0 is not allowed because that means "next available"
236                          * on just about every system and therefore cannot be used
237                          */
238                         unsigned long pnum = 0;
239                         spanned = strspn(url, URL_DIGIT);
240                         if (spanned < slash_ptr - url) {
241                                 /* port number has invalid characters */
242                                 if (out_info) {
243                                         out_info->url = NULL;
244                                         out_info->err = _("invalid port number");
245                                 }
246                                 strbuf_release(&norm);
247                                 return NULL;
248                         }
249                         if (slash_ptr - url <= 5)
250                                 pnum = strtoul(url, NULL, 10);
251                         if (pnum == 0 || pnum > 65535) {
252                                 /* port number not in range 1..65535 */
253                                 if (out_info) {
254                                         out_info->url = NULL;
255                                         out_info->err = _("invalid port number");
256                                 }
257                                 strbuf_release(&norm);
258                                 return NULL;
259                         }
260                         strbuf_addch(&norm, ':');
261                         strbuf_add(&norm, url, slash_ptr - url);
262                         port_len = slash_ptr - url;
263                 }
264                 url_len -= slash_ptr - colon_ptr;
265                 url = slash_ptr;
266         }
267         if (host_off)
268                 host_len = norm.len - host_off;
269
270
271         /*
272          * Now copy the path resolving any . and .. segments being careful not
273          * to corrupt the URL by unescaping any delimiters, but do add an
274          * initial '/' if it's missing and do normalize any %-escape sequences.
275          */
276         path_off = norm.len;
277         path_start = norm.buf + path_off;
278         strbuf_addch(&norm, '/');
279         if (*url == '/') {
280                 url++;
281                 url_len--;
282         }
283         for (;;) {
284                 const char *seg_start;
285                 size_t seg_start_off = norm.len;
286                 const char *next_slash = url + strcspn(url, "/?#");
287                 int skip_add_slash = 0;
288
289                 /*
290                  * RFC 3689 indicates that any . or .. segments should be
291                  * unescaped before being checked for.
292                  */
293                 if (!append_normalized_escapes(&norm, url, next_slash - url, "",
294                                                URL_RESERVED)) {
295                         if (out_info) {
296                                 out_info->url = NULL;
297                                 out_info->err = _("invalid %XX escape sequence");
298                         }
299                         strbuf_release(&norm);
300                         return NULL;
301                 }
302
303                 seg_start = norm.buf + seg_start_off;
304                 if (!strcmp(seg_start, ".")) {
305                         /* ignore a . segment; be careful not to remove initial '/' */
306                         if (seg_start == path_start + 1) {
307                                 strbuf_setlen(&norm, norm.len - 1);
308                                 skip_add_slash = 1;
309                         } else {
310                                 strbuf_setlen(&norm, norm.len - 2);
311                         }
312                 } else if (!strcmp(seg_start, "..")) {
313                         /*
314                          * ignore a .. segment and remove the previous segment;
315                          * be careful not to remove initial '/' from path
316                          */
317                         const char *prev_slash = norm.buf + norm.len - 3;
318                         if (prev_slash == path_start) {
319                                 /* invalid .. because no previous segment to remove */
320                                 if (out_info) {
321                                         out_info->url = NULL;
322                                         out_info->err = _("invalid '..' path segment");
323                                 }
324                                 strbuf_release(&norm);
325                                 return NULL;
326                         }
327                         while (*--prev_slash != '/') {}
328                         if (prev_slash == path_start) {
329                                 strbuf_setlen(&norm, prev_slash - norm.buf + 1);
330                                 skip_add_slash = 1;
331                         } else {
332                                 strbuf_setlen(&norm, prev_slash - norm.buf);
333                         }
334                 }
335                 url_len -= next_slash - url;
336                 url = next_slash;
337                 /* if the next char is not '/' done with the path */
338                 if (*url != '/')
339                         break;
340                 url++;
341                 url_len--;
342                 if (!skip_add_slash)
343                         strbuf_addch(&norm, '/');
344         }
345         path_len = norm.len - path_off;
346
347
348         /*
349          * Now simply copy the rest, if any, only normalizing %-escapes and
350          * being careful not to corrupt the URL by unescaping any delimiters.
351          */
352         if (*url) {
353                 if (!append_normalized_escapes(&norm, url, url_len, "", URL_RESERVED)) {
354                         if (out_info) {
355                                 out_info->url = NULL;
356                                 out_info->err = _("invalid %XX escape sequence");
357                         }
358                         strbuf_release(&norm);
359                         return NULL;
360                 }
361         }
362
363
364         result = strbuf_detach(&norm, &result_len);
365         if (out_info) {
366                 out_info->url = result;
367                 out_info->err = NULL;
368                 out_info->url_len = result_len;
369                 out_info->scheme_len = scheme_len;
370                 out_info->user_off = user_off;
371                 out_info->user_len = user_len;
372                 out_info->passwd_off = passwd_off;
373                 out_info->passwd_len = passwd_len;
374                 out_info->host_off = host_off;
375                 out_info->host_len = host_len;
376                 out_info->port_len = port_len;
377                 out_info->path_off = path_off;
378                 out_info->path_len = path_len;
379         }
380         return result;
381 }
382
383 static size_t url_match_prefix(const char *url,
384                                const char *url_prefix,
385                                size_t url_prefix_len)
386 {
387         /*
388          * url_prefix matches url if url_prefix is an exact match for url or it
389          * is a prefix of url and the match ends on a path component boundary.
390          * Both url and url_prefix are considered to have an implicit '/' on the
391          * end for matching purposes if they do not already.
392          *
393          * url must be NUL terminated.  url_prefix_len is the length of
394          * url_prefix which need not be NUL terminated.
395          *
396          * The return value is the length of the match in characters (including
397          * the final '/' even if it's implicit) or 0 for no match.
398          *
399          * Passing NULL as url and/or url_prefix will always cause 0 to be
400          * returned without causing any faults.
401          */
402         if (!url || !url_prefix)
403                 return 0;
404         if (!url_prefix_len || (url_prefix_len == 1 && *url_prefix == '/'))
405                 return (!*url || *url == '/') ? 1 : 0;
406         if (url_prefix[url_prefix_len - 1] == '/')
407                 url_prefix_len--;
408         if (strncmp(url, url_prefix, url_prefix_len))
409                 return 0;
410         if ((strlen(url) == url_prefix_len) || (url[url_prefix_len] == '/'))
411                 return url_prefix_len + 1;
412         return 0;
413 }
414
415 int match_urls(const struct url_info *url,
416                const struct url_info *url_prefix,
417                int *exactusermatch)
418 {
419         /*
420          * url_prefix matches url if the scheme, host and port of url_prefix
421          * are the same as those of url and the path portion of url_prefix
422          * is the same as the path portion of url or it is a prefix that
423          * matches at a '/' boundary.  If url_prefix contains a user name,
424          * that must also exactly match the user name in url.
425          *
426          * If the user, host, port and path match in this fashion, the returned
427          * value is the length of the path match including any implicit
428          * final '/'.  For example, "http://me@example.com/path" is matched by
429          * "http://example.com" with a path length of 1.
430          *
431          * If there is a match and exactusermatch is not NULL, then
432          * *exactusermatch will be set to true if both url and url_prefix
433          * contained a user name or false if url_prefix did not have a
434          * user name.  If there is no match *exactusermatch is left untouched.
435          */
436         int usermatched = 0;
437         int pathmatchlen;
438
439         if (!url || !url_prefix || !url->url || !url_prefix->url)
440                 return 0;
441
442         /* check the scheme */
443         if (url_prefix->scheme_len != url->scheme_len ||
444             strncmp(url->url, url_prefix->url, url->scheme_len))
445                 return 0; /* schemes do not match */
446
447         /* check the user name if url_prefix has one */
448         if (url_prefix->user_off) {
449                 if (!url->user_off || url->user_len != url_prefix->user_len ||
450                     strncmp(url->url + url->user_off,
451                             url_prefix->url + url_prefix->user_off,
452                             url->user_len))
453                         return 0; /* url_prefix has a user but it's not a match */
454                 usermatched = 1;
455         }
456
457         /* check the host and port */
458         if (url_prefix->host_len != url->host_len ||
459             strncmp(url->url + url->host_off,
460                     url_prefix->url + url_prefix->host_off, url->host_len))
461                 return 0; /* host names and/or ports do not match */
462
463         /* check the path */
464         pathmatchlen = url_match_prefix(
465                 url->url + url->path_off,
466                 url_prefix->url + url_prefix->path_off,
467                 url_prefix->url_len - url_prefix->path_off);
468
469         if (pathmatchlen && exactusermatch)
470                 *exactusermatch = usermatched;
471         return pathmatchlen;
472 }
473
474 int urlmatch_config_entry(const char *var, const char *value, void *cb)
475 {
476         struct string_list_item *item;
477         struct urlmatch_config *collect = cb;
478         struct urlmatch_item *matched;
479         struct url_info *url = &collect->url;
480         const char *key, *dot;
481         struct strbuf synthkey = STRBUF_INIT;
482         size_t matched_len = 0;
483         int user_matched = 0;
484         int retval;
485
486         if (!skip_prefix(var, collect->section, &key) || *(key++) != '.') {
487                 if (collect->cascade_fn)
488                         return collect->cascade_fn(var, value, cb);
489                 return 0; /* not interested */
490         }
491         dot = strrchr(key, '.');
492         if (dot) {
493                 char *config_url, *norm_url;
494                 struct url_info norm_info;
495
496                 config_url = xmemdupz(key, dot - key);
497                 norm_url = url_normalize(config_url, &norm_info);
498                 free(config_url);
499                 if (!norm_url)
500                         return 0;
501                 matched_len = match_urls(url, &norm_info, &user_matched);
502                 free(norm_url);
503                 if (!matched_len)
504                         return 0;
505                 key = dot + 1;
506         }
507
508         if (collect->key && strcmp(key, collect->key))
509                 return 0;
510
511         item = string_list_insert(&collect->vars, key);
512         if (!item->util) {
513                 matched = xcalloc(1, sizeof(*matched));
514                 item->util = matched;
515         } else {
516                 matched = item->util;
517                 /*
518                  * Is our match shorter?  Is our match the same
519                  * length, and without user while the current
520                  * candidate is with user?  Then we cannot use it.
521                  */
522                 if (matched_len < matched->matched_len ||
523                     ((matched_len == matched->matched_len) &&
524                      (!user_matched && matched->user_matched)))
525                         return 0;
526                 /* Otherwise, replace it with this one. */
527         }
528
529         matched->matched_len = matched_len;
530         matched->user_matched = user_matched;
531         strbuf_addstr(&synthkey, collect->section);
532         strbuf_addch(&synthkey, '.');
533         strbuf_addstr(&synthkey, key);
534         retval = collect->collect_fn(synthkey.buf, value, collect->cb);
535
536         strbuf_release(&synthkey);
537         return retval;
538 }