class Addressable::Template

# File lib/addressable/template.rb, line 236
def initialize(pattern)
  if !pattern.respond_to?(:to_str)
    raise TypeError, "Can't convert #{pattern.class} into String."
  end
  @pattern = pattern.to_str.dup.freeze
end

# File lib/addressable/template.rb, line 276
def ==(template)
  return false unless template.kind_of?(Template)
  return self.pattern == template.pattern
end

# File lib/addressable/template.rb, line 603
def expand(mapping, processor=nil, normalize_values=true)
  result = self.pattern.dup
  mapping = normalize_keys(mapping)
  result.gsub!( EXPRESSION ) do |capture|
    transform_capture(mapping, capture, processor, normalize_values)
  end
  return Addressable::URI.parse(result)
end

# File lib/addressable/template.rb, line 344
def extract(uri, processor=nil)
  match_data = self.match(uri, processor)
  return (match_data ? match_data.mapping : nil)
end

# File lib/addressable/template.rb, line 247
def freeze
  self.variables
  self.variable_defaults
  self.named_captures
  super
end

# File lib/addressable/template.rb, line 262
def inspect
  sprintf("#<%s:%#0x PATTERN:%s>",
    self.class.to_s, self.object_id, self.pattern)
end

# File lib/addressable/template.rb, line 415
def match(uri, processor=nil)
  unless uri.is_a?(Addressable::URI)
    begin
      uri = Addressable::URI.parse(uri)
    rescue Addressable::URI::InvalidURIError
      # Per the documented contract, match returns nil for any input
      # that doesn't match the template - including a string that
      # isn't even a valid URI.
      return nil
    end
  end
  mapping = {}

  # First, we need to process the pattern, and extract the values.
  expansions, expansion_regexp =
    parse_template_pattern(pattern, processor)

  matched = uri.to_str.match(expansion_regexp)
  return nil unless matched
  unparsed_values = matched.captures

  if uri.to_str == pattern
    return Addressable::Template::MatchData.new(uri, self, mapping)
  elsif expansions.size > 0
    index = 0
    expansions.each do |expansion|
      _, operator, varlist = *expansion.match(EXPRESSION)
      varlist.split(',').each do |varspec|
        _, name, modifier = *varspec.match(VARSPEC)
        mapping[name] ||= nil
        case operator
        when nil, '+', '#', '/', '.'
          unparsed_value = unparsed_values[index]
          name = varspec[VARSPEC, 1]
          value = unparsed_value
          value = value.split(JOINERS[operator]) if value && modifier == '*'
        when ';', '?', '&'
          if modifier == '*'
            if unparsed_values[index]
              value = unparsed_values[index].split(JOINERS[operator])
              value = value.inject({}) do |acc, v|
                key, val = v.split('=')
                val = "" if val.nil?
                acc[key] = val
                acc
              end
            end
          else
            if (unparsed_values[index])
              name, value = unparsed_values[index].split('=')
              value = "" if value.nil?
            end
          end
        end
        if processor != nil && processor.respond_to?(:restore)
          value = processor.restore(name, value)
        end
        if processor == nil
          if value.is_a?(Hash)
            value = value.inject({}){|acc, (k, v)|
              acc[Addressable::URI.unencode_component(k)] =
                Addressable::URI.unencode_component(v)
              acc
            }
          elsif value.is_a?(Array)
            value = value.map{|v| Addressable::URI.unencode_component(v) }
          else
            value = Addressable::URI.unencode_component(value)
          end
        end
        if !mapping.has_key?(name) || mapping[name].nil?
          # Doesn't exist, set to value (even if value is nil)
          mapping[name] = value
        end
        index = index + 1
      end
    end
    return Addressable::Template::MatchData.new(uri, self, mapping)
  else
    return nil
  end
end

# File lib/addressable/template.rb, line 663
def named_captures
  self.to_regexp.named_captures
end

# File lib/addressable/template.rb, line 536
def partial_expand(mapping, processor=nil, normalize_values=true)
  result = self.pattern.dup
  mapping = normalize_keys(mapping)
  result.gsub!( EXPRESSION ) do |capture|
    transform_partial_capture(mapping, capture, processor, normalize_values)
  end
  return Addressable::Template.new(result)
end

# File lib/addressable/template.rb, line 653
def source
  self.to_regexp.source
end

# File lib/addressable/template.rb, line 642
def to_regexp
  _, source = parse_template_pattern(pattern)
  Regexp.new(source)
end

# File lib/addressable/template.rb, line 630
def variable_defaults
  @variable_defaults ||=
    Hash[*ordered_variable_defaults.reject { |k, v| v.nil? }.flatten]
end

# File lib/addressable/template.rb, line 619
def variables
  @variables ||= ordered_variable_defaults.map { |var, val| var }.uniq
end

# File lib/addressable/template.rb, line 1019
def absorbed_by?(following, operator, varspecs)
  last = following[2].split(',').last
  case following[1]
  when '+'
    # An unexploded last variable matches any characters that an
    # expression can, and can end anywhere.
    last[VARSPEC, 2] != '*'
  when nil
    if last[VARSPEC, 2] == '*'
      # Matches any unreserved characters and commas.
      operator.nil? || operator == '.'
    elsif following[2] == last
      # Matches any unreserved characters.
      operator == '.' || (operator.nil? && varspecs.size == 1 &&
        varspecs.first[VARSPEC, 2] != '*')
    else
      false
    end
  else
    false
  end
end

# File lib/addressable/template.rb, line 979
def expression_followers(escaped_pattern)
  expressions = escaped_pattern.to_enum(:scan, EXPRESSION).map do
    Regexp.last_match
  end
  expressions.each_with_index.map do |current, index|
    following = expressions[index + 1]
    following = nil unless following && following.begin(0) == current.end(0)
    # Expressions can match nothing, so look past any that can't start
    # with a comma.
    position = current.end(0)
    comma = expressions[(index + 1)..-1].any? do |later|
      break false unless later.begin(0) == position
      position = later.end(0)
      may_start_with_comma?(later[1], later[2])
    end
    [following, comma || escaped_pattern[position] == ',']
  end
end

# File lib/addressable/template.rb, line 873
def join_values(operator, return_value)
  leader = LEADERS.fetch(operator, '')
  joiner = JOINERS.fetch(operator, ',')
  case operator
  when '&', '?'
    leader + return_value.map{|k,v|
      if v.is_a?(Array) && v.first =~ /=/
        v.join(joiner)
      elsif v.is_a?(Array)
        v.map{|inner_value| "#{k}=#{inner_value}"}.join(joiner)
      else
        "#{k}=#{v}"
      end
    }.join(joiner)
  when ';'
    return_value.map{|k,v|
      if v.is_a?(Array) && v.first =~ /=/
        ';' + v.join(";")
      elsif v.is_a?(Array)
        ';' + v.map{|inner_value| "#{k}=#{inner_value}"}.join(";")
      else
        v && v != '' ?  ";#{k}=#{v}" : ";#{k}"
      end
    }.join
  else
    leader + return_value.map{|k,v| v}.join(joiner)
  end
end

# File lib/addressable/template.rb, line 1005
def may_start_with_comma?(operator, varlist)
  return false unless LEADERS.fetch(operator, '').empty?
  operator == '+' || !(varlist =~ VARSPEC && $2 != '*')
end

# File lib/addressable/template.rb, line 936
def normalize_keys(mapping)
  return mapping.inject({}) do |accu, pair|
    name, value = pair
    if Symbol === name
      name = name.to_s
    elsif name.respond_to?(:to_str)
      name = name.to_str
    else
      raise TypeError,
        "Can't convert #{name.class} into String."
    end
    accu[name] = value
    accu
  end
end

# File lib/addressable/template.rb, line 910
def normalize_value(value)
  # Handle unicode normalization
  if value.respond_to?(:to_ary)
    value = value.to_ary.map { |val| normalize_value(val) }
  elsif value.kind_of?(Hash)
    value = value.inject({}) { |acc, (k, v)|
      acc[normalize_value(k)] = normalize_value(v)
      acc
    }
  else
    value = value.to_s if !value.kind_of?(String)
    if value.encoding != Encoding::UTF_8
      value = value.dup.force_encoding(Encoding::UTF_8)
    end
    value = value.unicode_normalize(:nfc)
  end
  value
end

# File lib/addressable/template.rb, line 668
def ordered_variable_defaults
  @ordered_variable_defaults ||= begin
    expansions, _ = parse_template_pattern(pattern)
    expansions.flat_map do |capture|
      _, _, varlist = *capture.match(EXPRESSION)
      varlist.split(',').map do |varspec|
        varspec[VARSPEC, 1]
      end
    end
  end
end

# File lib/addressable/template.rb, line 1051
def parse_new_template_pattern(pattern, processor = nil)
  # Escape the pattern. The two gsubs restore the escaped curly braces
  # back to their original form. Basically, escape everything that isn't
  # within an expansion.
  escaped_pattern = Regexp.escape(
    pattern
  ).gsub(/\\\{(.*?)\\\}/) do |escaped|
    escaped.gsub(/\\(.)/, "\\1")
  end

  expansions = []
  # Processor patterns can match anything, so they get 2.9.0's choices.
  plain_processor = !(processor && processor.respond_to?(:match))
  followers = expression_followers(escaped_pattern)

  # Create a regular expression that captures the values of the
  # variables in the URI.
  regexp_string = escaped_pattern.gsub( EXPRESSION ) do |expansion|

    index = expansions.size
    expansions << expansion
    _, operator, varlist = *expansion.match(EXPRESSION)
    leader = Regexp.escape(LEADERS.fetch(operator, ''))
    joiner = Regexp.escape(JOINERS.fetch(operator, ','))
    varspecs = varlist.split(',')
    results = varspecs.map do |varspec|
      name = varspec[VARSPEC, 1]
      processor && processor.respond_to?(:match) ? processor.match(name) : nil
    end
    # Without processor patterns, any variable in the expression can take
    # the characters that an earlier variable leaves, which lets the
    # variables after the first one have fewer choices below.
    plain = results.compact.empty?
    explodes = varspecs.map { |varspec| varspec[VARSPEC, 2] == '*' }
    first_explode = explodes.index(true)
    not_after_value =
      "(?<![#{Addressable::URI::CharacterClasses::UNRESERVED}])"
    combined = varspecs.each_with_index.map do |varspec, position|
      _, name, modifier = *varspec.match(VARSPEC)

      result = results[position]
      if result
        "(?<#{name}>#{ result })"
      else
        group = case operator
        when '+'
          "#{ RESERVED }*?"
        when '#'
          "#{ RESERVED }*?"
        when '/'
          "#{ UNRESERVED }*?"
        when '.'
          "#{ UNRESERVED.gsub('\.', '') }*?"
        when ';'
          # The same strings, tried in the same order, as 2.9.0's
          # "U*=?U*?", but a name without "=" can only match one way.
          "(?:#{UNRESERVED}*=#{UNRESERVED}*?|#{UNRESERVED}*)"
        when '?'
          "#{ UNRESERVED }*=#{ UNRESERVED }*?"
        when '&'
          "#{ UNRESERVED }*=#{ UNRESERVED }*?"
        else
          "#{ UNRESERVED }*?"
        end
        if modifier == '*'
          # The ; ? and & members match the same strings, in the same
          # order of preference, as 2.9.0's members joined by an optional
          # joiner, but each character can only belong to one member.
          seg = case operator
                when '+', '#' then "#{RESERVED_NO_COMMA}*+"
                when ';' then "(?:#{UNRESERVED}|=)*"
                when '?', '&'
                  "#{UNRESERVED}*=(?:#{UNRESERVED}*=)*#{UNRESERVED}*?"
                else group
                end
          # The joiner between exploded members must be mandatory. With
          # an optional joiner, a run of members can be partitioned in
          # exponentially many ways, which backtracks catastrophically on
          # engines without match memoization (MRI < 3.2, JRuby,
          # TruffleRuby).
          value = "#{seg}(?:#{joiner}#{seg})*"
        end
        if plain && first_explode && position > first_explode &&
            (operator == '+' || operator == '#' || operator == ';')
          # Exploded values were tried longest first, so whatever this
          # variable could match after the first exploded one, that one
          # already tried matching itself. Only the last unexploded + or
          # # variable can stop inside a member, where an exploded
          # variable can't. As in 2.9.0, a variable is the last one if
          # its varspec is the same as the last varspec.
          if operator == ';'
            "(?<#{name}>)"
          elsif modifier != '*' && varspec == varspecs.last
            "(?<#{name}>#{RESERVED_NO_COMMA}*?)?"
          else
            # 2.9.0 skipped the variable when it couldn't be empty.
            "(?:(?<#{name}>)(?!#{RESERVED_NO_COMMA}))?"
          end
        elsif plain && modifier == '*' && explodes[(position + 1)..-1].any? &&
            (operator.nil? || operator == '/' || operator == '.')
          # Exploded values were tried shortest first, and a later
          # exploded variable can match whatever this one leaves, so once
          # a split fails, every split where this variable is longer
          # fails too. Of the values tried, only the leading joiners are
          # shorter than every value tried before them.
          "(?<#{name}>(?:#{joiner})*)"
        elsif plain && position > 0 && explodes[position - 1] &&
            (operator == '?' || operator == '&')
          # Whatever this variable could match after an exploded one,
          # that one already tried matching itself, unless it couldn't:
          # an exploded member can't be empty, so this variable may only
          # start right after an empty one.
          "(?<#{name}>(?<=#{leader}#{joiner}|#{joiner}#{joiner})" \
            "#{value || group})?"
        elsif operator == ';' && plain && position > 0
          # Values were tried longest first, and splitting an earlier
          # variable's run of characters with this one never gave a
          # different result, so this one may only start after that run.
          "(?<#{name}>(?:#{not_after_value}#{value || group})?)"
        elsif modifier == '*'
          "(?<#{name}>#{value})?"
        elsif varspecs.size > 1 && (operator == '+' || operator == '#') &&
              varspec != varspecs.last
          "(?<#{name}>#{RESERVED_NO_COMMA}*+)?"
        elsif plain && position < varspecs.size - 1 &&
              (operator.nil? || operator == '/' || operator == '.')
          # Values were tried shortest first, so a run of characters
          # without a joiner went to a later variable. The only other
          # value that could change the result is the whole run up to the
          # next joiner.
          "(?<#{name}>(?:#{group}(?=#{joiner}))??)"
        else
          "(?<#{name}>#{group})?"
        end
      end
    end
    following, comma_follows = followers[index]
    single = varspecs.size == 1 && varspecs.first[VARSPEC, 2] != '*'
    if plain_processor && following &&
        absorbed_by?(following, operator, varspecs)
      # Each expression tried its empty alternative first. When the next
      # one follows it directly and can match anything it could, followed
      # by anything the next one could match on its own, every other
      # choice ends where the empty one can also end, so the empty
      # alternative always gave the first match.
      leader = "(?!)#{leader}"
      combined = combined.join("#{joiner}?")
    elsif plain_processor && single && following &&
        following[1].nil? && following[2] =~ VARSPEC && $2 != '*' &&
        (operator == '+' || operator == '#')
      # Values were tried shortest first, and the next expression can
      # match any unreserved characters, so the value only needs to end
      # after a character that the next expression couldn't match.
      combined = "(?<#{varspecs.first[VARSPEC, 1]}>" \
        "#{RESERVED}*?#{not_after_value})?"
    elsif plain && varspecs.size > 1 &&
        (operator == '+' || operator == '#') &&
        !comma_follows &&
        varspecs.none? { |varspec| varspec[VARSPEC, 2] == '*' } &&
        !varspecs[0...-1].include?(varspecs.last)
      # 2.9.0 tried each value with the joiner after it first, then the
      # value on its own, then skipping the variable, and every other
      # choice gave a value to a later variable that an earlier one had
      # already been tried with. A variable after a skipped one is
      # skipped too. Stopping before a joiner is left out, so this is
      # only used when no joiner can follow the expression. As in 2.9.0,
      # a variable is the last one if its varspec is the same as the
      # last varspec.
      nested = varspecs[0...-1].reverse.inject("") do |inner, varspec|
        "(?:(?<#{varspec[VARSPEC, 1]}>#{RESERVED_NO_COMMA}*+)" \
          "#{joiner}?+#{inner}|(?=#{RESERVED_NO_COMMA}))"
      end
      combined = nested + combined.last
    else
      combined = combined.join("#{joiner}?")
    end
    "(?:|#{leader}#{combined})"
  end

  # Ensure that the regular expression matches the whole URI.
  regexp_string = "\\A#{regexp_string}\\z"
  return expansions, Regexp.new(regexp_string)
end

# File lib/addressable/template.rb, line 962
def parse_template_pattern(pattern, processor = nil)
  if processor.nil? && pattern == @pattern
    @cached_template_parse ||=
      parse_new_template_pattern(pattern, processor)
  else
    parse_new_template_pattern(pattern, processor)
  end
end

# File lib/addressable/template.rb, line 765
def transform_capture(mapping, capture, processor=nil,
                      normalize_values=true)
  _, operator, varlist = *capture.match(EXPRESSION)
  return_value = varlist.split(',').inject([]) do |acc, varspec|
    _, name, modifier = *varspec.match(VARSPEC)
    value = mapping[name]
    unless value == nil || value == {}
      allow_reserved = %w(+ #).include?(operator)
      # Common primitives where the .to_s output is well-defined
      if Numeric === value || Symbol === value ||
          value == true || value == false
        value = value.to_s
      end
      length = modifier.gsub(':', '').to_i if modifier =~ /^:\d+/

      unless (Hash === value) ||
        value.respond_to?(:to_ary) || value.respond_to?(:to_str)
        raise TypeError,
          "Can't convert #{value.class} into String or Array."
      end

      value = normalize_value(value) if normalize_values

      if processor == nil || !processor.respond_to?(:transform)
        # Handle percent escaping
        if allow_reserved
          encode_map =
            Addressable::URI::CharacterClasses::RESERVED +
            Addressable::URI::CharacterClasses::UNRESERVED
        else
          encode_map = Addressable::URI::CharacterClasses::UNRESERVED
        end
        if value.kind_of?(Array)
          transformed_value = value.map do |val|
            if length
              Addressable::URI.encode_component(val[0...length], encode_map)
            else
              Addressable::URI.encode_component(val, encode_map)
            end
          end
          unless modifier == "*"
            transformed_value = transformed_value.join(',')
          end
        elsif value.kind_of?(Hash)
          transformed_value = value.map do |key, val|
            if modifier == "*"
              "#{
                Addressable::URI.encode_component( key, encode_map)
              }=#{
                Addressable::URI.encode_component( val, encode_map)
              }"
            else
              "#{
                Addressable::URI.encode_component( key, encode_map)
              },#{
                Addressable::URI.encode_component( val, encode_map)
              }"
            end
          end
          unless modifier == "*"
            transformed_value = transformed_value.join(',')
          end
        else
          if length
            transformed_value = Addressable::URI.encode_component(
              value[0...length], encode_map)
          else
            transformed_value = Addressable::URI.encode_component(
              value, encode_map)
          end
        end
      end

      # Process, if we've got a processor
      if processor != nil
        if processor.respond_to?(:validate)
          if !processor.validate(name, value)
            display_value = value.kind_of?(Array) ? value.inspect : value
            raise InvalidTemplateValueError,
              "#{name}=#{display_value} is an invalid template value."
          end
        end
        if processor.respond_to?(:transform)
          transformed_value = processor.transform(name, value)
          if normalize_values
            transformed_value = normalize_value(transformed_value)
          end
        end
      end
      acc << [name, transformed_value]
    end
    acc
  end
  return "" if return_value.empty?
  join_values(operator, return_value)
end

# File lib/addressable/template.rb, line 706
def transform_partial_capture(mapping, capture, processor = nil,
                              normalize_values = true)
  _, operator, varlist = *capture.match(EXPRESSION)

  vars = varlist.split(",")

  if operator == "?"
    # partial expansion of form style query variables sometimes requires a
    # slight reordering of the variables to produce a valid url.
    first_to_expand = vars.find { |varspec|
      _, name, _ =  *varspec.match(VARSPEC)
      mapping.key?(name) && !mapping[name].nil?
    }

    vars = [first_to_expand] + vars.reject {|varspec| varspec == first_to_expand}  if first_to_expand
  end

  vars.
    inject("".dup) do |acc, varspec|
      _, name, _ =  *varspec.match(VARSPEC)
      next_val = if mapping.key? name
                   transform_capture(mapping, "{#{operator}#{varspec}}",
                                     processor, normalize_values)
                 else
                   "{#{operator}#{varspec}}"
                 end
      # If we've already expanded at least one '?' operator with non-empty
      # value, change to '&'
      operator = "&" if (operator == "?") && (next_val != "")
      acc << next_val
  end
end