#include "git-compat-util.h"

#include "gettext.h"

#include "hex-ll.h"

#include "strbuf.h"

#include "urlmatch.h"

#define URL_ALPHA "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

#define URL_DIGIT "0123456789"

#define URL_ALPHADIGIT URL_ALPHA URL_DIGIT

#define URL_SCHEME_CHARS URL_ALPHADIGIT "+.-"

#define URL_HOST_CHARS URL_ALPHADIGIT ".-_[:]" /* IPv6 literals need [:] */

#define URL_UNSAFE_CHARS " <>\"%{}|\\^`" /* plus 0x00-0x1F,0x7F-0xFF */

#define URL_GEN_RESERVED ":/?#[]@"

#define URL_SUB_RESERVED "!$&'()*+,;="

#define URL_RESERVED URL_GEN_RESERVED URL_SUB_RESERVED /* only allowed delims */

static int append_normalized_escapes(struct strbuf *buf,

             const char *from,

             size_t from_len,

             const char *esc_extra,

             const char *esc_ok)

{

  /*

   * Append to strbuf 'buf' characters from string 'from' with length

   * 'from_len' while unescaping characters that do not need to be escaped

   * and escaping characters that do.  The set of characters to escape

   * (the complement of which is unescaped) starts out as the RFC 3986

   * unsafe characters (0x00-0x1F,0x7F-0xFF," <>\"#%{}|\\^`").  If

   * 'esc_extra' is not NULL, those additional characters will also always

   * be escaped.  If 'esc_ok' is not NULL, those characters will be left

   * escaped if found that way, but will not be unescaped otherwise (used

   * for delimiters).  If a %-escape sequence is encountered that is not

   * followed by 2 hexadecimal digits, the sequence is invalid and

   * false (0) will be returned.  Otherwise true (1) will be returned for

   * success.

   *

   * Note that all %-escape sequences will be normalized to UPPERCASE

   * as indicated in RFC 3986.  Unless included in esc_extra or esc_ok

   * alphanumerics and "-._~" will always be unescaped as per RFC 3986.

   */

  while (from_len) {

    int ch = *from++;

    int was_esc = 0;

    from_len--;

    if (ch == '%') {

      if (from_len < 2)

        return 0;

      ch = hex2chr(from);

      if (ch < 0)

        return 0;

      from += 2;

      from_len -= 2;

      was_esc = 1;

    }

    if ((unsigned char)ch <= 0x1F || (unsigned char)ch >= 0x7F ||

        strchr(URL_UNSAFE_CHARS, ch) ||

        (esc_extra && strchr(esc_extra, ch)) ||

        (was_esc && strchr(esc_ok, ch)))

      strbuf_addf(buf, "%%%02X", (unsigned char)ch);

    else

      strbuf_addch(buf, ch);

  }

  return 1;

}

static const char *end_of_token(const char *s, int c, size_t n)

{

  const char *next = memchr(s, c, n);

  if (!next)

    next = s + n;

  return next;

}

static int match_host(const struct url_info *url_info,

          const struct url_info *pattern_info)

{

  const char *url = url_info->url + url_info->host_off;

  const char *pat = pattern_info->url + pattern_info->host_off;

  int url_len = url_info->host_len;

  int pat_len = pattern_info->host_len;

  while (url_len && pat_len) {

    const char *url_next = end_of_token(url, '.', url_len);

    const char *pat_next = end_of_token(pat, '.', pat_len);

    if (pat_next == pat + 1 && pat[0] == '*')

      /* wildcard matches anything */

      ;

    else if ((pat_next - pat) == (url_next - url) &&

       !memcmp(url, pat, url_next - url))

      /* the components are the same */

      ;

    else

      return 0; /* found an unmatch */

    if (url_next < url + url_len)

      url_next++;

    url_len -= url_next - url;

    url = url_next;

    if (pat_next < pat + pat_len)

      pat_next++;

    pat_len -= pat_next - pat;

    pat = pat_next;

  }

  return (!url_len && !pat_len);

}

static char *url_normalize_1(const char *url, struct url_info *out_info, char allow_globs)

{

  /*

   * Normalize NUL-terminated url using the following rules:

   *

   * 1. Case-insensitive parts of url will be converted to lower case

   * 2. %-encoded characters that do not need to be will be unencoded

   * 3. Characters that are not %-encoded and must be will be encoded

   * 4. All %-encodings will be converted to upper case hexadecimal

   * 5. Leading 0s are removed from port numbers

   * 6. If the default port for the scheme is given it will be removed

   * 7. A path part (including empty) not starting with '/' has one added

   * 8. Any dot segments (. or ..) in the path are resolved and removed

   * 9. IPv6 host literals are allowed (but not normalized or validated)

   *

   * The rules are based on information in RFC 3986.

   *

   * Please note this function requires a full URL including a scheme

   * and host part (except for file: URLs which may have an empty host).

   *

   * The return value is a newly allocated string that must be freed

   * or NULL if the url is not valid.

   *

   * If out_info is non-NULL, the url and err fields therein will always

   * be set.  If a non-NULL value is returned, it will be stored in

   * out_info->url as well, out_info->err will be set to NULL and the

   * other fields of *out_info will also be filled in.  If a NULL value

   * is returned, NULL will be stored in out_info->url and out_info->err

   * will be set to a brief, translated, error message, but no other

   * fields will be filled in.

   *

   * This is NOT a URL validation function.  Full URL validation is NOT

   * performed.  Some invalid host names are passed through this function

   * undetected.  However, most all other problems that make a URL invalid

   * will be detected (including a missing host for non file: URLs).

   */

  size_t url_len = strlen(url);

  struct strbuf norm;

  size_t spanned;

  size_t scheme_len, user_off=0, user_len=0, passwd_off=0, passwd_len=0;

  size_t host_off=0, host_len=0, port_off=0, port_len=0, path_off, path_len, result_len;

  const char *slash_ptr, *at_ptr, *colon_ptr, *path_start;

  char *result;

  /*

   * Copy lowercased scheme and :// suffix, %-escapes are not allowed

   * First character of scheme must be URL_ALPHA

   */

  spanned = strspn(url, URL_SCHEME_CHARS);

  if (!spanned || !isalpha(url[0]) || spanned + 3 > url_len ||

      url[spanned] != ':' || url[spanned+1] != '/' || url[spanned+2] != '/') {

    if (out_info) {

      out_info->url = NULL;

      out_info->err = _("invalid URL scheme name or missing '://' suffix");

    }

    return NULL; /* Bad scheme and/or missing "://" part */

  }

  strbuf_init(&norm, url_len);

  scheme_len = spanned;

  spanned += 3;

  url_len -= spanned;

  while (spanned--)

    strbuf_addch(&norm, tolower(*url++));

  /*

   * Copy any username:password if present normalizing %-escapes

   */

  at_ptr = strchr(url, '@');

  slash_ptr = url + strcspn(url, "/?#");

  if (at_ptr && at_ptr < slash_ptr) {

    user_off = norm.len;

    if (at_ptr > url) {

      if (!append_normalized_escapes(&norm, url, at_ptr - url,

                   "", URL_RESERVED)) {

        if (out_info) {

          out_info->url = NULL;

          out_info->err = _("invalid %XX escape sequence");

        }

        strbuf_release(&norm);

        return NULL;

      }

      colon_ptr = strchr(norm.buf + scheme_len + 3, ':');

      if (colon_ptr) {

        passwd_off = (colon_ptr + 1) - norm.buf;

        passwd_len = norm.len - passwd_off;

        user_len = (passwd_off - 1) - (scheme_len + 3);

      } else {

        user_len = norm.len - (scheme_len + 3);

      }

    }

    strbuf_addch(&norm, '@');

    url_len -= (++at_ptr - url);

    url = at_ptr;

  }

  /*

   * Copy the host part excluding any port part, no %-escapes allowed

   */

  if (!url_len || strchr(":/?#", *url)) {

    /* Missing host invalid for all URL schemes except file */

    if (!starts_with(norm.buf, "file:")) {

      if (out_info) {

        out_info->url = NULL;

        out_info->err = _("missing host and scheme is not 'file:'");

      }

      strbuf_release(&norm);

      return NULL;

    }

  } else {

    host_off = norm.len;

  }

  colon_ptr = slash_ptr - 1;

  while (colon_ptr > url && *colon_ptr != ':' && *colon_ptr != ']')

    colon_ptr--;

  if (*colon_ptr != ':') {

    colon_ptr = slash_ptr;

  } else if (!host_off && colon_ptr < slash_ptr && colon_ptr + 1 != slash_ptr) {

    /* file: URLs may not have a port number */

    if (out_info) {

      out_info->url = NULL;

      out_info->err = _("a 'file:' URL may not have a port number");

    }

    strbuf_release(&norm);

    return NULL;

  }

  if (allow_globs)

    spanned = strspn(url, URL_HOST_CHARS "*");

  else

    spanned = strspn(url, URL_HOST_CHARS);

  if (spanned < colon_ptr - url) {

    /* Host name has invalid characters */

    if (out_info) {

      out_info->url = NULL;

      out_info->err = _("invalid characters in host name");

    }

    strbuf_release(&norm);

    return NULL;

  }

  while (url < colon_ptr) {

    strbuf_addch(&norm, tolower(*url++));

    url_len--;

  }

  /*

   * Check the port part and copy if not the default (after removing any

   * leading 0s); no %-escapes allowed

   */

  if (colon_ptr < slash_ptr) {

    /* skip the ':' and leading 0s but not the last one if all 0s */

    url++;

    url += strspn(url, "0");

    if (url == slash_ptr && url[-1] == '0')

      url--;

    if (url == slash_ptr) {

      /* Skip ":" port with no number, it's same as default */

    } else if (slash_ptr - url == 2 &&

         starts_with(norm.buf, "http:") &&

         !strncmp(url, "80", 2)) {

      /* Skip http :80 as it's the default */

    } else if (slash_ptr - url == 3 &&

         starts_with(norm.buf, "https:") &&

         !strncmp(url, "443", 3)) {

      /* Skip https :443 as it's the default */

    } else {

      /*

       * Port number must be all digits with leading 0s removed

       * and since all the protocols we deal with have a 16-bit

       * port number it must also be in the range 1..65535

       * 0 is not allowed because that means "next available"

       * on just about every system and therefore cannot be used

       */

      unsigned long pnum = 0;

      spanned = strspn(url, URL_DIGIT);

      if (spanned < slash_ptr - url) {

        /* port number has invalid characters */

        if (out_info) {

          out_info->url = NULL;

          out_info->err = _("invalid port number");

        }

        strbuf_release(&norm);

        return NULL;

      }

      if (slash_ptr - url <= 5)

        pnum = strtoul(url, NULL, 10);

      if (pnum == 0 || pnum > 65535) {

        /* port number not in range 1..65535 */

        if (out_info) {

          out_info->url = NULL;

          out_info->err = _("invalid port number");

        }

        strbuf_release(&norm);

        return NULL;

      }

      strbuf_addch(&norm, ':');

      port_off = norm.len;

      strbuf_add(&norm, url, slash_ptr - url);

      port_len = slash_ptr - url;

    }

    url_len -= slash_ptr - colon_ptr;

    url = slash_ptr;

  }

  if (host_off)

    host_len = norm.len - host_off - (port_len ? port_len + 1 : 0);

  /*

   * Now copy the path resolving any . and .. segments being careful not

   * to corrupt the URL by unescaping any delimiters, but do add an

   * initial '/' if it's missing and do normalize any %-escape sequences.

   */

  path_off = norm.len;

  path_start = norm.buf + path_off;

  strbuf_addch(&norm, '/');

  if (*url == '/') {

    url++;

    url_len--;

  }

  for (;;) {

    const char *seg_start;

    size_t seg_start_off = norm.len;

    const char *next_slash = url + strcspn(url, "/?#");

    int skip_add_slash = 0;

    /*

     * RFC 3689 indicates that any . or .. segments should be

     * unescaped before being checked for.

     */

    if (!append_normalized_escapes(&norm, url, next_slash - url, "",

                 URL_RESERVED)) {

      if (out_info) {

        out_info->url = NULL;

        out_info->err = _("invalid %XX escape sequence");

      }

      strbuf_release(&norm);

      return NULL;

    }

    seg_start = norm.buf + seg_start_off;

    if (!strcmp(seg_start, ".")) {

      /* ignore a . segment; be careful not to remove initial '/' */

      if (seg_start == path_start + 1) {

        strbuf_setlen(&norm, norm.len - 1);

        skip_add_slash = 1;

      } else {

        strbuf_setlen(&norm, norm.len - 2);

      }

    } else if (!strcmp(seg_start, "..")) {

      /*

       * ignore a .. segment and remove the previous segment;

       * be careful not to remove initial '/' from path

       */

      const char *prev_slash = norm.buf + norm.len - 3;

      if (prev_slash == path_start) {

        /* invalid .. because no previous segment to remove */

        if (out_info) {

          out_info->url = NULL;

          out_info->err = _("invalid '..' path segment");

        }

        strbuf_release(&norm);

        return NULL;

      }

      while (*--prev_slash != '/') {}

      if (prev_slash == path_start) {

        strbuf_setlen(&norm, prev_slash - norm.buf + 1);

        skip_add_slash = 1;

      } else {

        strbuf_setlen(&norm, prev_slash - norm.buf);

      }

    }

    url_len -= next_slash - url;

    url = next_slash;

    /* if the next char is not '/' done with the path */

    if (*url != '/')

      break;

    url++;

    url_len--;

    if (!skip_add_slash)

      strbuf_addch(&norm, '/');

  }

  path_len = norm.len - path_off;

  /*

   * Now simply copy the rest, if any, only normalizing %-escapes and

   * being careful not to corrupt the URL by unescaping any delimiters.

   */

  if (*url) {

    if (!append_normalized_escapes(&norm, url, url_len, "", URL_RESERVED)) {

      if (out_info) {

        out_info->url = NULL;

        out_info->err = _("invalid %XX escape sequence");

      }

      strbuf_release(&norm);

      return NULL;

    }

  }

  result = strbuf_detach(&norm, &result_len);

  if (out_info) {

    out_info->url = result;

    out_info->err = NULL;

    out_info->url_len = result_len;

    out_info->scheme_len = scheme_len;

    out_info->user_off = user_off;

    out_info->user_len = user_len;

    out_info->passwd_off = passwd_off;

    out_info->passwd_len = passwd_len;

    out_info->host_off = host_off;

    out_info->host_len = host_len;

    out_info->port_off = port_off;

    out_info->port_len = port_len;

    out_info->path_off = path_off;

    out_info->path_len = path_len;

  }

  return result;

}

char *url_normalize(const char *url, struct url_info *out_info)

{

  return url_normalize_1(url, out_info, 0);

}

static size_t url_match_prefix(const char *url,

             const char *url_prefix,

             size_t url_prefix_len)

{

  /*

   * url_prefix matches url if url_prefix is an exact match for url or it

   * is a prefix of url and the match ends on a path component boundary.

   * Both url and url_prefix are considered to have an implicit '/' on the

   * end for matching purposes if they do not already.

   *

   * url must be NUL terminated.  url_prefix_len is the length of

   * url_prefix which need not be NUL terminated.

   *

   * The return value is the length of the match in characters (including

   * the final '/' even if it's implicit) or 0 for no match.

   *

   * Passing NULL as url and/or url_prefix will always cause 0 to be

   * returned without causing any faults.

   */

  if (!url || !url_prefix)

    return 0;

  if (!url_prefix_len || (url_prefix_len == 1 && *url_prefix == '/'))

    return (!*url || *url == '/') ? 1 : 0;

  if (url_prefix[url_prefix_len - 1] == '/')

    url_prefix_len--;

  if (strncmp(url, url_prefix, url_prefix_len))

    return 0;

  if ((strlen(url) == url_prefix_len) || (url[url_prefix_len] == '/'))

    return url_prefix_len + 1;

  return 0;

}

static int match_urls(const struct url_info *url,

          const struct url_info *url_prefix,

          struct urlmatch_item *match)

{

  /*

   * url_prefix matches url if the scheme, host and port of url_prefix

   * are the same as those of url and the path portion of url_prefix

   * is the same as the path portion of url or it is a prefix that

   * matches at a '/' boundary.  If url_prefix contains a user name,

   * that must also exactly match the user name in url.

   *

   * If the user, host, port and path match in this fashion, the returned

   * value is the length of the path match including any implicit

   * final '/'.  For example, "http://me@example.com/path" is matched by

   * "http://example.com" with a path length of 1.

   *

   * If there is a match and exactusermatch is not NULL, then

   * *exactusermatch will be set to true if both url and url_prefix

   * contained a user name or false if url_prefix did not have a

   * user name.  If there is no match *exactusermatch is left untouched.

   */

  char usermatched = 0;

  size_t pathmatchlen;

  if (!url || !url_prefix || !url->url || !url_prefix->url)

    return 0;

  /* check the scheme */

  if (url_prefix->scheme_len != url->scheme_len ||

      strncmp(url->url, url_prefix->url, url->scheme_len))

    return 0; /* schemes do not match */

  /* check the user name if url_prefix has one */

  if (url_prefix->user_off) {

    if (!url->user_off || url->user_len != url_prefix->user_len ||

        strncmp(url->url + url->user_off,

          url_prefix->url + url_prefix->user_off,

          url->user_len))

      return 0; /* url_prefix has a user but it's not a match */

    usermatched = 1;

  }

  /* check the host */

  if (!match_host(url, url_prefix))

    return 0; /* host names do not match */

  /* check the port */

  if (url_prefix->port_len != url->port_len ||

      strncmp(url->url + url->port_off,

        url_prefix->url + url_prefix->port_off, url->port_len))

    return 0; /* ports do not match */

  /* check the path */

  pathmatchlen = url_match_prefix(

    url->url + url->path_off,

    url_prefix->url + url_prefix->path_off,

    url_prefix->url_len - url_prefix->path_off);

  if (!pathmatchlen)

    return 0; /* paths do not match */

  if (match) {

    match->hostmatch_len = url_prefix->host_len;

    match->pathmatch_len = pathmatchlen;

    match->user_matched = usermatched;

  }

  return 1;

}

static int cmp_matches(const struct urlmatch_item *a,

           const struct urlmatch_item *b)

{

  if (a->hostmatch_len != b->hostmatch_len)

    return a->hostmatch_len < b->hostmatch_len ? -1 : 1;

  if (a->pathmatch_len != b->pathmatch_len)

    return a->pathmatch_len < b->pathmatch_len ? -1 : 1;

  if (a->user_matched != b->user_matched)

    return b->user_matched ? -1 : 1;

  return 0;

}

int urlmatch_config_entry(const char *var, const char *value,

        const struct config_context *ctx, void *cb)

{

  struct string_list_item *item;

  struct urlmatch_config *collect = cb;

  struct urlmatch_item matched = {0};

  struct url_info *url = &collect->url;

  const char *key, *dot;

  struct strbuf synthkey = STRBUF_INIT;

  int retval;

  int (*select_fn)(const struct urlmatch_item *a, const struct urlmatch_item *b) =

    collect->select_fn ? collect->select_fn : cmp_matches;

  if (!skip_prefix(var, collect->section, &key) || *(key++) != '.') {

    if (collect->cascade_fn)

      return collect->cascade_fn(var, value, ctx, cb);

    return 0; /* not interested */

  }

  dot = strrchr(key, '.');

  if (dot) {

    char *config_url, *norm_url;

    struct url_info norm_info;

    config_url = xmemdupz(key, dot - key);

    norm_url = url_normalize_1(config_url, &norm_info, 1);

    if (norm_url)

      retval = match_urls(url, &norm_info, &matched);

    else if (collect->fallback_match_fn)

      retval = collect->fallback_match_fn(config_url,

                  collect->cb);

    else

      retval = 0;

    free(config_url);

    free(norm_url);

    if (!retval)

      return 0;

    key = dot + 1;

  }

  if (collect->key && strcmp(key, collect->key))

    return 0;

  item = string_list_insert(&collect->vars, key);

  if (!item->util) {

    item->util = xcalloc(1, sizeof(matched));

  } else {

    if (select_fn(&matched, item->util) < 0)

       /*

        * Our match is worse than the old one,

        * we cannot use it.

        */

      return 0;

    /* Otherwise, replace it with this one. */

  }

  memcpy(item->util, &matched, sizeof(matched));

  strbuf_addstr(&synthkey, collect->section);

  strbuf_addch(&synthkey, '.');

  strbuf_addstr(&synthkey, key);

  retval = collect->collect_fn(synthkey.buf, value, ctx, collect->cb);

  strbuf_release(&synthkey);

  return retval;

}

void urlmatch_config_release(struct urlmatch_config *config)

{

  string_list_clear(&config->vars, 1);

}