class Sass::Selector::Sequence

def _eql?(other)
  other.members.reject {|m| m == "\n"}.eql?(self.members.reject {|m| m == "\n"})
end

def _hash
  members.reject {|m| m == "\n"}.hash
end

def _sources(seq)
  s = Set.new
  seq.map {|sseq_or_op| s.merge sseq_or_op.sources if sseq_or_op.is_a?(SimpleSequence)}
  s
end

def _superselector?(seq1, seq2)
  seq1 = seq1.reject {|e| e == "\n"}
  seq2 = seq2.reject {|e| e == "\n"}
  # Selectors with leading or trailing operators are neither
  # superselectors nor subselectors.
  return if seq1.last.is_a?(String) || seq2.last.is_a?(String) ||
    seq1.first.is_a?(String) || seq2.first.is_a?(String)
  # More complex selectors are never superselectors of less complex ones
  return if seq1.size > seq2.size
  return seq1.first.superselector?(seq2.last) if seq1.size == 1
  _, si = Sass::Util.enum_with_index(seq2).find do |e, i|
    return if i == seq2.size - 1
    next if e.is_a?(String)
    seq1.first.superselector?(e)
  end
  return unless si
  if seq1[1].is_a?(String)
    return unless seq2[si+1].is_a?(String)
    # .foo ~ .bar is a superselector of .foo + .bar
    return unless seq1[1] == "~" ? seq2[si+1] != ">" : seq1[1] == seq2[si+1]
    return _superselector?(seq1[2..-1], seq2[si+2..-1])
  elsif seq2[si+1].is_a?(String)
    return unless seq2[si+1] == ">"
    return _superselector?(seq1[1..-1], seq2[si+2..-1])
  else
    return _superselector?(seq1[1..-1], seq2[si+1..-1])
  end
end

def add_sources!(sources)
  members.map! {|m| m.is_a?(SimpleSequence) ? m.with_more_sources(sources) : m}
end

def chunks(seq1, seq2)
  chunk1 = []
  chunk1 << seq1.shift until yield seq1
  chunk2 = []
  chunk2 << seq2.shift until yield seq2
  return [] if chunk1.empty? && chunk2.empty?
  return [chunk2] if chunk1.empty?
  return [chunk1] if chunk2.empty?
  [chunk1 + chunk2, chunk2 + chunk1]
end

def do_extend(extends, parent_directives, seen = Set.new)
  extended_not_expanded = members.map do |sseq_or_op|
    next [[sseq_or_op]] unless sseq_or_op.is_a?(SimpleSequence)
    extended = sseq_or_op.do_extend(extends, parent_directives, seen)
    choices = extended.map {|seq| seq.members}
    choices.unshift([sseq_or_op]) unless extended.any? {|seq| seq.superselector?(sseq_or_op)}
    choices
  end
  weaves = Sass::Util.paths(extended_not_expanded).map {|path| weave(path)}
  Sass::Util.flatten(trim(weaves), 1).map {|p| Sequence.new(p)}
end

def extended_not_expanded_to_s(extended_not_expanded)
  extended_not_expanded.map do |choices|
    choices = choices.map do |sel|
      next sel.first.to_s if sel.size == 1
      "#{sel.join ' '}"
    end
    next choices.first if choices.size == 1 && !choices.include?(' ')
    "(#{choices.join ', '})"
  end.join ' '
end

def filename=(filename)
  members.each {|m| m.filename = filename if m.is_a?(SimpleSequence)}
  filename
end

def group_selectors(seq)
  newseq = []
  tail = seq.dup
  until tail.empty?
    head = []
    begin
      head << tail.shift
    end while !tail.empty? && head.last.is_a?(String) || tail.first.is_a?(String)
    newseq << head
  end
  return newseq
end

def initialize(seqs_and_ops)
  @members = seqs_and_ops
end

def inspect
  members.map {|m| m.inspect}.join(" ")
end

def line=(line)
  members.each {|m| m.line = line if m.is_a?(SimpleSequence)}
  line
end

def merge_final_ops(seq1, seq2, res = [])
  ops1, ops2 = [], []
  ops1 << seq1.pop while seq1.last.is_a?(String)
  ops2 << seq2.pop while seq2.last.is_a?(String)
  # Not worth the headache of trying to preserve newlines here. The most
  # important use of newlines is at the beginning of the selector to wrap
  # across lines anyway.
  ops1.reject! {|o| o == "\n"}
  ops2.reject! {|o| o == "\n"}
  return res if ops1.empty? && ops2.empty?
  if ops1.size > 1 || ops2.size > 1
    # If there are multiple operators, something hacky's going on. If one
    # is a supersequence of the other, use that, otherwise give up.
    lcs = Sass::Util.lcs(ops1, ops2)
    return unless lcs == ops1 || lcs == ops2
    res.unshift *(ops1.size > ops2.size ? ops1 : ops2).reverse
    return res
  end
  # This code looks complicated, but it's actually just a bunch of special
  # cases for interactions between different combinators.
  op1, op2 = ops1.first, ops2.first
  if op1 && op2
    sel1 = seq1.pop
    sel2 = seq2.pop
    if op1 == '~' && op2 == '~'
      if sel1.superselector?(sel2)
        res.unshift sel2, '~'
      elsif sel2.superselector?(sel1)
        res.unshift sel1, '~'
      else
        merged = sel1.unify(sel2.members, sel2.subject?)
        res.unshift [
          [sel1, '~', sel2, '~'],
          [sel2, '~', sel1, '~'],
          ([merged, '~'] if merged)
        ].compact
      end
    elsif (op1 == '~' && op2 == '+') || (op1 == '+' && op2 == '~')
      if op1 == '~'
        tilde_sel, plus_sel = sel1, sel2
      else
        tilde_sel, plus_sel = sel2, sel1
      end
      if tilde_sel.superselector?(plus_sel)
        res.unshift plus_sel, '+'
      else
        merged = plus_sel.unify(tilde_sel.members, tilde_sel.subject?)
        res.unshift [
          [tilde_sel, '~', plus_sel, '+'],
          ([merged, '+'] if merged)
        ].compact
      end
    elsif op1 == '>' && %w[~ +].include?(op2)
      res.unshift sel2, op2
      seq1.push sel1, op1
    elsif op2 == '>' && %w[~ +].include?(op1)
      res.unshift sel1, op1
      seq2.push sel2, op2
    elsif op1 == op2
      return unless merged = sel1.unify(sel2.members, sel2.subject?)
      res.unshift merged, op1
    else
      # Unknown selector combinators can't be unified
      return
    end
    return merge_final_ops(seq1, seq2, res)
  elsif op1
    seq2.pop if op1 == '>' && seq2.last && seq2.last.superselector?(seq1.last)
    res.unshift seq1.pop, op1
    return merge_final_ops(seq1, seq2, res)
  else # op2
    seq1.pop if op2 == '>' && seq1.last && seq1.last.superselector?(seq2.last)
    res.unshift seq2.pop, op2
    return merge_final_ops(seq1, seq2, res)
  end
end

def merge_initial_ops(seq1, seq2)
  ops1, ops2 = [], []
  ops1 << seq1.shift while seq1.first.is_a?(String)
  ops2 << seq2.shift while seq2.first.is_a?(String)
  newline = false
  newline ||= !!ops1.shift if ops1.first == "\n"
  newline ||= !!ops2.shift if ops2.first == "\n"
  # If neither sequence is a subsequence of the other, they cannot be
  # merged successfully
  lcs = Sass::Util.lcs(ops1, ops2)
  return unless lcs == ops1 || lcs == ops2
  return (newline ? ["\n"] : []) + (ops1.size > ops2.size ? ops1 : ops2)
end

def parent_superselector?(seq1, seq2)
  base = Sass::Selector::SimpleSequence.new([Sass::Selector::Placeholder.new('<temp>')], false)
  _superselector?(seq1 + [base], seq2 + [base])
end

def path_has_two_subjects?(path)
  subject = false
  path.each do |sseq_or_op|
    next unless sseq_or_op.is_a?(SimpleSequence)
    next unless sseq_or_op.subject?
    return true if subject
    subject = true
  end
  false
end

def resolve_parent_refs(super_seq)
  members = @members.dup
  nl = (members.first == "\n" && members.shift)
  unless members.any? do |seq_or_op|
      seq_or_op.is_a?(SimpleSequence) && seq_or_op.members.first.is_a?(Parent)
    end
    old_members, members = members, []
    members << nl if nl
    members << SimpleSequence.new([Parent.new], false)
    members += old_members
  end
  Sequence.new(
    members.map do |seq_or_op|
      next seq_or_op unless seq_or_op.is_a?(SimpleSequence)
      seq_or_op.resolve_parent_refs(super_seq)
    end.flatten)
end

def subweave(seq1, seq2)
  return [seq2] if seq1.empty?
  return [seq1] if seq2.empty?
  seq1, seq2 = seq1.dup, seq2.dup
  return unless init = merge_initial_ops(seq1, seq2)
  return unless fin = merge_final_ops(seq1, seq2)
  seq1 = group_selectors(seq1)
  seq2 = group_selectors(seq2)
  lcs = Sass::Util.lcs(seq2, seq1) do |s1, s2|
    next s1 if s1 == s2
    next unless s1.first.is_a?(SimpleSequence) && s2.first.is_a?(SimpleSequence)
    next s2 if parent_superselector?(s1, s2)
    next s1 if parent_superselector?(s2, s1)
  end
  diff = [[init]]
  until lcs.empty?
    diff << chunks(seq1, seq2) {|s| parent_superselector?(s.first, lcs.first)} << [lcs.shift]
    seq1.shift
    seq2.shift
  end
  diff << chunks(seq1, seq2) {|s| s.empty?}
  diff += fin.map {|sel| sel.is_a?(Array) ? sel : [sel]}
  diff.reject! {|c| c.empty?}
  Sass::Util.paths(diff).map {|p| p.flatten}.reject {|p| path_has_two_subjects?(p)}
end

def superselector?(sseq)
  return false unless members.size == 1
  members.last.superselector?(sseq)
end

def to_a
  ary = @members.map {|seq_or_op| seq_or_op.is_a?(SimpleSequence) ? seq_or_op.to_a : seq_or_op}
  Sass::Util.intersperse(ary, " ").flatten.compact
end

def trim(seqses)
  # This is n^2 on the sequences, but only comparing between
  # separate sequences should limit the quadratic behavior.
  seqses.map do |seqs1|
    seqs1.reject do |seq1|
      min_spec = 0
      _sources(seq1).map {|seq| min_spec += seq.specificity}
      seqses.any? do |seqs2|
        next if seqs1.equal?(seqs2)
        # Second Law of Extend: the specificity of a generated selector
        # should never be less than the specificity of the extending
        # selector.
        #
        # See https://github.com/nex3/sass/issues/324.
        seqs2.any? {|seq2| _specificity(seq2) >= min_spec && _superselector?(seq2, seq1)}
      end
    end
  end
end

def weave(path)
  # This function works by moving through the selector path left-to-right,
  # building all possible prefixes simultaneously. These prefixes are
  # `befores`, while the remaining parenthesized suffixes is `afters`.
  befores = [[]]
  afters = path.dup
  until afters.empty?
    current = afters.shift.dup
    last_current = [current.pop]
    befores = Sass::Util.flatten(befores.map do |before|
        next [] unless sub = subweave(before, current)
        sub.map {|seqs| seqs + last_current}
      end, 1)
  end
  return befores
end