# deps:
# a@0.1 => b@>=0.2
# a@0.2 => b@~>0.3
# c@0.1 => b@~>0.2

# installed:
# a@0.1
# a@0.2
# b@0.2
# b@0.3
# c@0.1

# user requests:
# \require "a@>=0.1"
# \require "c@~>0.1"

tree = {
  dependencies: {
    "a" => {
      clause: "a@>=0.1",
      versions: {
        "a@0.1" => {
          dependencies: {
            "b" => {
              clause: "b@>=0.2",
              versions: {
                "b@0.2" => {},
                "b@0.3" => {}
              }
            }
          }
        },
        "a@0.2" => {
          dependencies: {
            "b" => {
              clause: "b@~>0.3",
              versions: {
                "b@0.3" => {}
              }
            }
          }
        }
      }
    },
    "c" => {
      clause: "c@~>0.1",
      versions: {
        "c@0.1" => {
          dependencies: {
            "b" => {
              clause: "b@~>0.2",
              versions: {
                "b@0.2" => {}
              }
            }
          }
        }
      }
    }
  }
}

def simplified_deps_tree(version)
  return {} unless version[:dependencies]

  dep_versions = {}

  # For each dependency, generate a deps tree for each available version
  version[:dependencies].each do |p, opts|
    opts[:versions].each do |v, opts2|
      dep_versions[p] ||= {}
      dep_versions[p][v] = simplified_deps_tree(opts2)
    end
  end

  dep_versions
end

def dependencies_array(tree)
  deps_array = []
  tree.each do |pack, versions|
    a = []
    versions.each do |version, deps|
      sub_perms = dependencies_array(deps)
      if sub_perms == []
        a << version
      else
        a += [version].product(*sub_perms)
      end
    end
    deps_array << a
  end

  deps_array
end

def permutate_simplified_tree(tree)
  deps = dependencies_array(simplified_deps_tree(tree))
  p deps

  return deps if deps.size < 2

  rest = deps[1..-1]

  perms = deps[0].product(*rest).map(&:flatten)
  # deps[1..-1].inject(deps[0]){ |m,v| m = m.product(v).map(&:flatten) }
end

perm = permutate_simplified_tree(tree)

def filter_invalid_permutations(perm)
  valid = []
  perm.each do |p|
    versions = {}; invalid = false
    p.each do |ref|
      if ref =~ /(.+)@(.+)/
        name, version = $1, $2
        if versions[name] && versions[name] != version
          invalid = true
          break
        else
          versions[name] = version
        end
      end
    end
    valid << p.uniq unless invalid
  end

  valid
end

p filter_invalid_permutations(perm)