module Sprockets::SourceMapUtils

def bsearch_mappings(mappings, offset, from = 0, to = mappings.size - 1)
  mid = (from + to) / 2
  if from > to
    return from < 1 ? nil : mappings[from-1]
  end
  case compare_source_offsets(offset, mappings[mid][:generated])
  when 0
    mappings[mid]
  when -1
    bsearch_mappings(mappings, offset, from, mid - 1)
  when 1
    bsearch_mappings(mappings, offset, mid + 1, to)
  end
end

def combine_source_maps(first, second)
  return second unless first
  _first  = decode_source_map(first)
  _second = decode_source_map(second)
  new_mappings = []
  _second[:mappings].each do |m|
    first_line = bsearch_mappings(_first[:mappings], m[:original])
    new_mappings << first_line.merge(generated: m[:generated]) if first_line
  end
  _first[:mappings] = new_mappings
  encode_source_map(_first)
end

def compare_source_offsets(a, b)
  diff = a[0] - b[0]
  diff = a[1] - b[1] if diff == 0
  if diff < 0
    -1
  elsif diff > 0
    1
  else
    0
  end
end

def concat_source_maps(a, b)
  return a || b unless a && b
  a, b = make_index_map(a), make_index_map(b)
  if a["sections"].count == 0 || a["sections"].last["map"]["mappings"].empty?
    offset = 0
  else
    offset = a["sections"].last["map"]["mappings"].count(';') + 
             a["sections"].last["offset"]["line"] + 1
  end
  a["sections"] += b["sections"].map do |section|
    {
      "offset" => section["offset"].merge({ "line" => section["offset"]["line"] + offset }),
      "map"    => section["map"].merge({
        "sources" => section["map"]["sources"].map do |source|
          PathUtils.relative_path_from(a["file"], PathUtils.join(File.dirname(b["file"]), source))
        end
      })
    }
  end
  a
end

def decode_source_map(map)
  return nil unless map
  mappings, sources, names = [], [], []
  if map["sections"]
    map["sections"].each do |s|
      mappings += decode_source_map(s["map"])[:mappings].each do |m|
        m[:generated][0] += s["offset"]["line"]
        m[:generated][1] += s["offset"]["column"]
      end
      sources |= s["map"]["sources"]
      names   |= s["map"]["names"]
    end
  else
    mappings = decode_vlq_mappings(map["mappings"], sources: map["sources"], names: map["names"])
    sources  = map["sources"]
    names    = map["names"]
  end
  {
    version:  3,
    file:     map["file"],
    mappings: mappings,
    sources:  sources,
    names:    names
  }
end

def decode_vlq_mappings(str, sources: [], names: [])
  mappings = []
  source_id       = 0
  original_line   = 1
  original_column = 0
  name_id         = 0
  vlq_decode_mappings(str).each_with_index do |group, index|
    generated_column = 0
    generated_line   = index + 1
    group.each do |segment|
      generated_column += segment[0]
      generated = [generated_line, generated_column]
      if segment.size >= 4
        source_id        += segment[1]
        original_line    += segment[2]
        original_column  += segment[3]
        source   = sources[source_id]
        original = [original_line, original_column]
      else
        # TODO: Research this case
        next
      end
      if segment[4]
        name_id += segment[4]
        name     = names[name_id]
      end
      mapping = {source: source, generated: generated, original: original}
      mapping[:name] = name if name
      mappings << mapping
    end
  end
  mappings
end

def encode_source_map(map)
  return nil unless map
  {
    "version"  => map[:version],
    "file"     => map[:file],
    "mappings" => encode_vlq_mappings(map[:mappings], sources: map[:sources], names: map[:names]),
    "sources"  => map[:sources],
    "names"    => map[:names]
  }
end

def encode_vlq_mappings(mappings, sources: nil, names: nil)
  sources ||= mappings.map { |m| m[:source] }.uniq.compact
  names   ||= mappings.map { |m| m[:name] }.uniq.compact
  sources_index = Hash[sources.each_with_index.to_a]
  names_index   = Hash[names.each_with_index.to_a]
  source_id     = 0
  source_line   = 1
  source_column = 0
  name_id       = 0
  by_lines = mappings.group_by { |m| m[:generated][0] }
  ary = (1..(by_lines.keys.max || 1)).map do |line|
    generated_column = 0
    (by_lines[line] || []).map do |mapping|
      group = []
      group << mapping[:generated][1] - generated_column
      group << sources_index[mapping[:source]] - source_id
      group << mapping[:original][0] - source_line
      group << mapping[:original][1] - source_column
      group << names_index[mapping[:name]] - name_id if mapping[:name]
      generated_column = mapping[:generated][1]
      source_id        = sources_index[mapping[:source]]
      source_line      = mapping[:original][0]
      source_column    = mapping[:original][1]
      name_id          = names_index[mapping[:name]] if mapping[:name]
      group
    end
  end
  vlq_encode_mappings(ary)
end

def format_source_map(map, input)
  filename      = input[:filename]
  load_path     = input[:load_path]
  load_paths    = input[:environment].config[:paths]
  mime_exts     = input[:environment].config[:mime_exts]
  pipeline_exts = input[:environment].config[:pipeline_exts]
  file          = PathUtils.split_subpath(load_path, filename)
  {
    "version"  => 3,
    "file"     => file,
    "mappings" => map["mappings"],
    "sources"  => map["sources"].map do |source|
      source = URIUtils.split_file_uri(source)[2] if source.start_with? "file://"
      source = PathUtils.join(File.dirname(filename), source) unless PathUtils.absolute_path?(source)
      _, source = PathUtils.paths_split(load_paths, source) 
      source = PathUtils.relative_path_from(file, source)
      PathUtils.set_pipeline(source, mime_exts, pipeline_exts, :source)
    end,
    "names"    => map["names"]
  }
end

def make_index_map(map)
  return map if map.key? "sections"
  {
    "version"  => map["version"],
    "file"     => map["file"],
    "sections" => [
      {
        "offset" => { "line" => 0, "column" => 0 },
        "map"    => map
      }
    ]
  }
end

def vlq_decode(str)
  result = []
  chars = str.split('')
  while chars.any?
    vlq = 0
    shift = 0
    continuation = true
    while continuation
      char = chars.shift
      raise ArgumentError unless char
      digit = BASE64_VALUES[char]
      continuation = false if (digit & VLQ_CONTINUATION_BIT) == 0
      digit &= VLQ_BASE_MASK
      vlq   += digit << shift
      shift += VLQ_BASE_SHIFT
    end
    result << (vlq & 1 == 1 ? -(vlq >> 1) : vlq >> 1)
  end
  result
end

def vlq_decode_mappings(str)
  mappings = []
  str.split(';').each_with_index do |group, index|
    mappings[index] = []
    group.split(',').each do |segment|
      mappings[index] << vlq_decode(segment)
    end
  end
  mappings
end

def vlq_encode(ary)
  result = []
  ary.each do |n|
    vlq = n < 0 ? ((-n) << 1) + 1 : n << 1
    loop do
      digit  = vlq & VLQ_BASE_MASK
      vlq  >>= VLQ_BASE_SHIFT
      digit |= VLQ_CONTINUATION_BIT if vlq > 0
      result << BASE64_DIGITS[digit]
      break unless vlq > 0
    end
  end
  result.join
end

def vlq_encode_mappings(ary)
  ary.map { |group|
    group.map { |segment|
      vlq_encode(segment)
    }.join(',')
  }.join(';')
end