# Copyright 2013-2022 Lawrence Livermore National Security, LLC and other
# Spack Project Developers. See the top-level COPYRIGHT file for details.
#
# SPDX-License-Identifier: (Apache-2.0 OR MIT)
"""
These tests check Spec DAG operations using dummy packages.
"""
import pytest

import spack.error
import spack.package
import spack.util.hash as hashutil
from spack.dependency import Dependency, all_deptypes, canonical_deptype
from spack.spec import Spec
from spack.util.mock_package import MockPackageMultiRepo


def check_links(spec_to_check):
    for spec in spec_to_check.traverse():
        for dependent in spec.dependents():
            assert dependent.edges_to_dependencies(name=spec.name)

        for dependency in spec.dependencies():
            assert dependency.edges_from_dependents(name=spec.name)


@pytest.fixture()
def saved_deps():
    """Returns a dictionary to save the dependencies."""
    return {}


@pytest.fixture()
def set_dependency(saved_deps, monkeypatch):
    """Returns a function that alters the dependency information
    for a package in the ``saved_deps`` fixture.
    """
    def _mock(pkg_name, spec, deptypes=all_deptypes):
        """Alters dependence information for a package.

        Adds a dependency on <spec> to pkg. Use this to mock up constraints.
        """
        spec = Spec(spec)
        # Save original dependencies before making any changes.
        pkg = spack.repo.get(pkg_name)
        if pkg_name not in saved_deps:
            saved_deps[pkg_name] = (pkg, pkg.dependencies.copy())

        cond = Spec(pkg.name)
        dependency = Dependency(pkg, spec, type=deptypes)
        monkeypatch.setitem(pkg.dependencies, spec.name, {cond: dependency})
    return _mock


@pytest.mark.usefixtures('config')
def test_test_deptype():
    """Ensure that test-only dependencies are only included for specified
packages in the following spec DAG::

        w
       /|
      x y
        |
        z

w->y deptypes are (link, build), w->x and y->z deptypes are (test)

"""
    default = ('build', 'link')
    test_only = ('test',)

    mock_repo = MockPackageMultiRepo()
    x = mock_repo.add_package('x', [], [])
    z = mock_repo.add_package('z', [], [])
    y = mock_repo.add_package('y', [z], [test_only])
    w = mock_repo.add_package('w', [x, y], [test_only, default])

    with spack.repo.use_repositories(mock_repo):
        spec = Spec('w')
        spec.concretize(tests=(w.name,))

        assert ('x' in spec)
        assert ('z' not in spec)


@pytest.mark.usefixtures('config')
def test_installed_deps(monkeypatch, mock_packages):
    """Ensure that concrete specs and their build deps don't constrain solves.

    Preinstall a package ``c`` that has a constrained build dependency on ``d``, then
    install ``a`` and ensure that neither:

      * ``c``'s package constraints, nor
      * the concrete ``c``'s build dependencies

    constrain ``a``'s dependency on ``d``.

    """
    if spack.config.get('config:concretizer') == 'original':
        pytest.xfail('fails with the original concretizer and full hashes')

    # see installed-deps-[abcde] test packages.
    #     a
    #    / \
    #   b   c   b --> d build/link
    #   |\ /|   b --> e build/link
    #   |/ \|   c --> d build
    #   d   e   c --> e build/link
    #
    a, b, c, d, e = ["installed-deps-%s" % s for s in "abcde"]

    # install C, which will force d's version to be 2
    # BUT d is only a build dependency of C, so it won't constrain
    # link/run dependents of C when C is depended on as an existing
    # (concrete) installation.
    c_spec = Spec(c)
    c_spec.concretize()
    assert c_spec[d].version == spack.version.Version('2')

    installed_names = [s.name for s in c_spec.traverse()]

    def _mock_installed(self):
        return self.name in installed_names

    monkeypatch.setattr(Spec, 'installed', _mock_installed)

    # install A, which depends on B, C, D, and E, and force A to
    # use the installed C.  It should *not* force A to use the installed D
    # *if* we're doing a fresh installation.
    a_spec = Spec(a)
    a_spec._add_dependency(c_spec, ("build", "link"))
    a_spec.concretize()
    assert spack.version.Version('2') == a_spec[c][d].version
    assert spack.version.Version('2') == a_spec[e].version
    assert spack.version.Version('3') == a_spec[b][d].version
    assert spack.version.Version('3') == a_spec[d].version


@pytest.mark.usefixtures('config')
def test_specify_preinstalled_dep():
    """Specify the use of a preinstalled package during concretization with a
    transitive dependency that is only supplied by the preinstalled package.
    """
    default = ('build', 'link')

    mock_repo = MockPackageMultiRepo()
    c = mock_repo.add_package('c', [], [])
    b = mock_repo.add_package('b', [c], [default])
    mock_repo.add_package('a', [b], [default])

    with spack.repo.use_repositories(mock_repo):
        b_spec = Spec('b')
        b_spec.concretize()
        for spec in b_spec.traverse():
            setattr(spec.package, 'installed', True)

        a_spec = Spec('a')
        a_spec._add_dependency(b_spec, default)
        a_spec.concretize()

        assert set(x.name for x in a_spec.traverse()) == set(['a', 'b', 'c'])


@pytest.mark.usefixtures('config')
@pytest.mark.parametrize('spec_str,expr_str,expected', [
    ('x ^y@2', 'y@2', True),
    ('x@1', 'y', False),
    ('x', 'y@3', True)
])
def test_conditional_dep_with_user_constraints(spec_str, expr_str, expected):
    """This sets up packages X->Y such that X depends on Y conditionally. It
    then constructs a Spec with X but with no constraints on X, so that the
    initial normalization pass cannot determine whether the constraints are
    met to add the dependency; this checks whether a user-specified constraint
    on Y is applied properly.
    """
    # FIXME: We need to tweak optimization rules to make this test
    # FIXME: not prefer a DAG with fewer nodes wrt more recent
    # FIXME: versions of the package
    if spack.config.get('config:concretizer') == 'clingo':
        pytest.xfail('Clingo optimization rules prefer to trim a node')

    default = ('build', 'link')

    mock_repo = MockPackageMultiRepo()
    y = mock_repo.add_package('y', [], [])
    x_on_y_conditions = {
        y.name: {
            'x@2:': 'y'
        }
    }
    mock_repo.add_package('x', [y], [default], conditions=x_on_y_conditions)

    with spack.repo.use_repositories(mock_repo):
        spec = Spec(spec_str)
        spec.concretize()

    result = expr_str in spec
    assert result is expected, '{0} in {1}'.format(expr_str, spec)


@pytest.mark.usefixtures('mutable_mock_repo', 'config')
class TestSpecDag(object):
    def test_conflicting_package_constraints(self, set_dependency):
        set_dependency('mpileaks', 'mpich@1.0')
        set_dependency('callpath', 'mpich@2.0')

        spec = Spec('mpileaks ^mpich ^callpath ^dyninst ^libelf ^libdwarf')

        # TODO: try to do something to show that the issue was with
        # TODO: the user's input or with package inconsistencies.
        with pytest.raises(spack.spec.UnsatisfiableVersionSpecError):
            spec.normalize()

    def test_preorder_node_traversal(self):
        dag = Spec('mpileaks ^zmpi')
        dag.normalize()

        names = ['mpileaks', 'callpath', 'dyninst', 'libdwarf', 'libelf',
                 'zmpi', 'fake']
        pairs = list(zip([0, 1, 2, 3, 4, 2, 3], names))

        traversal = dag.traverse()
        assert [x.name for x in traversal] == names

        traversal = dag.traverse(depth=True)
        assert [(x, y.name) for x, y in traversal] == pairs

    def test_preorder_edge_traversal(self):
        dag = Spec('mpileaks ^zmpi')
        dag.normalize()

        names = ['mpileaks', 'callpath', 'dyninst', 'libdwarf', 'libelf',
                 'libelf', 'zmpi', 'fake', 'zmpi']
        pairs = list(zip([0, 1, 2, 3, 4, 3, 2, 3, 1], names))

        traversal = dag.traverse(cover='edges')
        assert [x.name for x in traversal] == names

        traversal = dag.traverse(cover='edges', depth=True)
        assert [(x, y.name) for x, y in traversal] == pairs

    def test_preorder_path_traversal(self):
        dag = Spec('mpileaks ^zmpi')
        dag.normalize()

        names = ['mpileaks', 'callpath', 'dyninst', 'libdwarf', 'libelf',
                 'libelf', 'zmpi', 'fake', 'zmpi', 'fake']
        pairs = list(zip([0, 1, 2, 3, 4, 3, 2, 3, 1, 2], names))

        traversal = dag.traverse(cover='paths')
        assert [x.name for x in traversal] == names

        traversal = dag.traverse(cover='paths', depth=True)
        assert [(x, y.name) for x, y in traversal] == pairs

    def test_postorder_node_traversal(self):
        dag = Spec('mpileaks ^zmpi')
        dag.normalize()

        names = ['libelf', 'libdwarf', 'dyninst', 'fake', 'zmpi',
                 'callpath', 'mpileaks']
        pairs = list(zip([4, 3, 2, 3, 2, 1, 0], names))

        traversal = dag.traverse(order='post')
        assert [x.name for x in traversal] == names

        traversal = dag.traverse(depth=True, order='post')
        assert [(x, y.name) for x, y in traversal] == pairs

    def test_postorder_edge_traversal(self):
        dag = Spec('mpileaks ^zmpi')
        dag.normalize()

        names = ['libelf', 'libdwarf', 'libelf', 'dyninst', 'fake', 'zmpi',
                 'callpath', 'zmpi', 'mpileaks']
        pairs = list(zip([4, 3, 3, 2, 3, 2, 1, 1, 0], names))

        traversal = dag.traverse(cover='edges', order='post')
        assert [x.name for x in traversal] == names

        traversal = dag.traverse(cover='edges', depth=True, order='post')
        assert [(x, y.name) for x, y in traversal] == pairs

    def test_postorder_path_traversal(self):
        dag = Spec('mpileaks ^zmpi')
        dag.normalize()

        names = ['libelf', 'libdwarf', 'libelf', 'dyninst', 'fake', 'zmpi',
                 'callpath', 'fake', 'zmpi', 'mpileaks']
        pairs = list(zip([4, 3, 3, 2, 3, 2, 1, 2, 1, 0], names))

        traversal = dag.traverse(cover='paths', order='post')
        assert [x.name for x in traversal] == names

        traversal = dag.traverse(cover='paths', depth=True, order='post')
        assert [(x, y.name) for x, y in traversal] == pairs

    def test_conflicting_spec_constraints(self):
        mpileaks = Spec('mpileaks ^mpich ^callpath ^dyninst ^libelf ^libdwarf')

        # Normalize then add conflicting constraints to the DAG (this is an
        # extremely unlikely scenario, but we test for it anyway)
        mpileaks.normalize()

        mpileaks.edges_to_dependencies(
            name='mpich'
        )[0].spec = Spec('mpich@1.0')

        mpileaks.edges_to_dependencies(
            name='callpath'
        )[0].spec.edges_to_dependencies(
            name='mpich'
        )[0].spec = Spec('mpich@2.0')

        with pytest.raises(spack.spec.InconsistentSpecError):
            mpileaks.flat_dependencies(copy=False)

    def test_normalize_twice(self):
        """Make sure normalize can be run twice on the same spec,
           and that it is idempotent."""
        spec = Spec('mpileaks')
        spec.normalize()
        n1 = spec.copy()

        spec.normalize()
        assert n1 == spec

    def test_normalize_a_lot(self):
        spec = Spec('mpileaks')
        spec.normalize()
        spec.normalize()
        spec.normalize()
        spec.normalize()

    def test_normalize_with_virtual_spec(self, ):
        dag = Spec.from_literal({
            'mpileaks': {
                'callpath': {
                    'dyninst': {
                        'libdwarf': {'libelf': None},
                        'libelf': None
                    },
                    'mpi': None
                },
                'mpi': None
            }
        })
        dag.normalize()

        # make sure nothing with the same name occurs twice
        counts = {}
        for spec in dag.traverse(key=id):
            if spec.name not in counts:
                counts[spec.name] = 0
            counts[spec.name] += 1

        for name in counts:
            assert counts[name] == 1

    def test_dependents_and_dependencies_are_correct(self):
        spec = Spec.from_literal({
            'mpileaks': {
                'callpath': {
                    'dyninst': {
                        'libdwarf': {'libelf': None},
                        'libelf': None
                    },
                    'mpi': None
                },
                'mpi': None
            }
        })

        check_links(spec)
        spec.normalize()
        check_links(spec)

    def test_unsatisfiable_version(self, set_dependency):
        set_dependency('mpileaks', 'mpich@1.0')
        spec = Spec('mpileaks ^mpich@2.0 ^callpath ^dyninst ^libelf ^libdwarf')
        with pytest.raises(spack.spec.UnsatisfiableVersionSpecError):
            spec.normalize()

    def test_unsatisfiable_compiler(self, set_dependency):
        set_dependency('mpileaks', 'mpich%gcc')
        spec = Spec('mpileaks ^mpich%intel ^callpath ^dyninst ^libelf'
                    ' ^libdwarf')
        with pytest.raises(spack.spec.UnsatisfiableCompilerSpecError):
            spec.normalize()

    def test_unsatisfiable_compiler_version(self, set_dependency):
        set_dependency('mpileaks', 'mpich%gcc@4.6')
        spec = Spec('mpileaks ^mpich%gcc@4.5 ^callpath ^dyninst ^libelf'
                    ' ^libdwarf')
        with pytest.raises(spack.spec.UnsatisfiableCompilerSpecError):
            spec.normalize()

    def test_unsatisfiable_architecture(self, set_dependency):
        set_dependency('mpileaks', 'mpich platform=test target=be')
        spec = Spec('mpileaks ^mpich platform=test target=fe ^callpath'
                    ' ^dyninst ^libelf ^libdwarf')
        with pytest.raises(spack.spec.UnsatisfiableArchitectureSpecError):
            spec.normalize()

    @pytest.mark.parametrize('spec_str', [
        'libelf ^mpich', 'libelf ^libdwarf', 'mpich ^dyninst ^libelf'
    ])
    def test_invalid_dep(self, spec_str):
        spec = Spec(spec_str)
        with pytest.raises(spack.error.SpecError):
            spec.concretize()

    def test_equal(self):
        # Different spec structures to test for equality
        flat = Spec.from_literal(
            {'mpileaks ^callpath ^libelf ^libdwarf': None}
        )

        flat_init = Spec.from_literal({
            'mpileaks': {
                'callpath': None,
                'libdwarf': None,
                'libelf': None
            }
        })

        flip_flat = Spec.from_literal({
            'mpileaks': {
                'libelf': None,
                'libdwarf': None,
                'callpath': None
            }
        })

        dag = Spec.from_literal({
            'mpileaks': {
                'callpath': {
                    'libdwarf': {
                        'libelf': None
                    }
                }
            }
        })

        flip_dag = Spec.from_literal({
            'mpileaks': {
                'callpath': {
                    'libelf': {
                        'libdwarf': None
                    }
                }
            }
        })

        # All these are equal to each other with regular ==
        specs = (flat, flat_init, flip_flat, dag, flip_dag)
        for lhs, rhs in zip(specs, specs):
            assert lhs == rhs
            assert str(lhs) == str(rhs)

        # Same DAGs constructed different ways are equal
        assert flat.eq_dag(flat_init)

        # order at same level does not matter -- (dep on same parent)
        assert flat.eq_dag(flip_flat)

        # DAGs should be unequal if nesting is different
        assert not flat.eq_dag(dag)
        assert not flat.eq_dag(flip_dag)
        assert not flip_flat.eq_dag(dag)
        assert not flip_flat.eq_dag(flip_dag)
        assert not dag.eq_dag(flip_dag)

    def test_normalize_mpileaks(self):
        # Spec parsed in from a string
        spec = Spec.from_literal({
            'mpileaks ^mpich ^callpath ^dyninst ^libelf@1.8.11 ^libdwarf': None
        })

        # What that spec should look like after parsing
        expected_flat = Spec.from_literal({
            'mpileaks': {
                'mpich': None,
                'callpath': None,
                'dyninst': None,
                'libelf@1.8.11': None,
                'libdwarf': None
            }
        })

        # What it should look like after normalization
        mpich = Spec('mpich')
        libelf = Spec('libelf@1.8.11')
        expected_normalized = Spec.from_literal({
            'mpileaks': {
                'callpath': {
                    'dyninst': {
                        'libdwarf': {libelf: None},
                        libelf: None
                    },
                    mpich: None
                },
                mpich: None
            },
        })

        # Similar to normalized spec, but now with copies of the same
        # libelf node.  Normalization should result in a single unique
        # node for each package, so this is the wrong DAG.
        non_unique_nodes = Spec.from_literal({
            'mpileaks': {
                'callpath': {
                    'dyninst': {
                        'libdwarf': {'libelf@1.8.11': None},
                        'libelf@1.8.11': None
                    },
                    mpich: None
                },
                mpich: None
            }
        }, normal=False)

        # All specs here should be equal under regular equality
        specs = (spec, expected_flat, expected_normalized, non_unique_nodes)
        for lhs, rhs in zip(specs, specs):
            assert lhs == rhs
            assert str(lhs) == str(rhs)

        # Test that equal and equal_dag are doing the right thing
        assert spec == expected_flat
        assert spec.eq_dag(expected_flat)

        # Normalized has different DAG structure, so NOT equal.
        assert spec != expected_normalized
        assert not spec.eq_dag(expected_normalized)

        # Again, different DAG structure so not equal.
        assert spec != non_unique_nodes
        assert not spec.eq_dag(non_unique_nodes)

        spec.normalize()

        # After normalizing, spec_dag_equal should match the normalized spec.
        assert spec != expected_flat
        assert not spec.eq_dag(expected_flat)

        # verify DAG structure without deptypes.
        assert spec.eq_dag(expected_normalized, deptypes=False)
        assert not spec.eq_dag(non_unique_nodes, deptypes=False)

        assert not spec.eq_dag(expected_normalized, deptypes=True)
        assert not spec.eq_dag(non_unique_nodes, deptypes=True)

    def test_normalize_with_virtual_package(self):
        spec = Spec('mpileaks ^mpi ^libelf@1.8.11 ^libdwarf')
        spec.normalize()

        expected_normalized = Spec.from_literal({
            'mpileaks': {
                'callpath': {
                    'dyninst': {
                        'libdwarf': {'libelf@1.8.11': None},
                        'libelf@1.8.11': None
                    },
                    'mpi': None
                },
                'mpi': None
            }
        })

        assert str(spec) == str(expected_normalized)

    def test_contains(self):
        spec = Spec('mpileaks ^mpi ^libelf@1.8.11 ^libdwarf')
        assert Spec('mpi') in spec
        assert Spec('libelf') in spec
        assert Spec('libelf@1.8.11') in spec
        assert Spec('libelf@1.8.12') not in spec
        assert Spec('libdwarf') in spec
        assert Spec('libgoblin') not in spec
        assert Spec('mpileaks') in spec

    def test_copy_simple(self):
        orig = Spec('mpileaks')
        copy = orig.copy()
        check_links(copy)

        assert orig == copy
        assert orig.eq_dag(copy)
        assert orig._normal == copy._normal
        assert orig._concrete == copy._concrete

        # ensure no shared nodes bt/w orig and copy.
        orig_ids = set(id(s) for s in orig.traverse())
        copy_ids = set(id(s) for s in copy.traverse())
        assert not orig_ids.intersection(copy_ids)

    def test_copy_normalized(self):
        orig = Spec('mpileaks')
        orig.normalize()
        copy = orig.copy()
        check_links(copy)

        assert orig == copy
        assert orig.eq_dag(copy)

        # ensure no shared nodes bt/w orig and copy.
        orig_ids = set(id(s) for s in orig.traverse())
        copy_ids = set(id(s) for s in copy.traverse())
        assert not orig_ids.intersection(copy_ids)

    def test_copy_concretized(self):
        orig = Spec('mpileaks')
        orig.concretize()
        copy = orig.copy()

        check_links(copy)

        assert orig == copy
        assert orig.eq_dag(copy)
        assert orig._normal == copy._normal
        assert orig._concrete == copy._concrete

        # ensure no shared nodes bt/w orig and copy.
        orig_ids = set(id(s) for s in orig.traverse())
        copy_ids = set(id(s) for s in copy.traverse())
        assert not orig_ids.intersection(copy_ids)

    def test_copy_through_spec_build_interface(self):
        """Check that copying dependencies using id(node) as a fast identifier of the
        node works when the spec is wrapped in a SpecBuildInterface object.
        """
        s = Spec('mpileaks').concretized()

        c0 = s.copy()
        assert c0 == s

        # Single indirection
        c1 = s['mpileaks'].copy()
        assert c0 == c1 == s

        # Double indirection
        c2 = s['mpileaks']['mpileaks'].copy()
        assert c0 == c1 == c2 == s

    """
    Here is the graph with deptypes labeled (assume all packages have a 'dt'
    prefix). Arrows are marked with the deptypes ('b' for 'build', 'l' for
    'link', 'r' for 'run').

        use -bl-> top

        top -b->  build1
        top -bl-> link1
        top -r->  run1

        build1 -b->  build2
        build1 -bl-> link2
        build1 -r->  run2

        link1 -bl-> link3

        run1 -bl-> link5
        run1 -r->  run3

        link3 -b->  build2
        link3 -bl-> link4

        run3 -b-> build3
    """

    def test_deptype_traversal(self):
        dag = Spec('dtuse')
        dag.normalize()

        names = ['dtuse', 'dttop', 'dtbuild1', 'dtbuild2', 'dtlink2',
                 'dtlink1', 'dtlink3', 'dtlink4']

        traversal = dag.traverse(deptype=('build', 'link'))
        assert [x.name for x in traversal] == names

    def test_deptype_traversal_with_builddeps(self):
        dag = Spec('dttop')
        dag.normalize()

        names = ['dttop', 'dtbuild1', 'dtbuild2', 'dtlink2',
                 'dtlink1', 'dtlink3', 'dtlink4']

        traversal = dag.traverse(deptype=('build', 'link'))
        assert [x.name for x in traversal] == names

    def test_deptype_traversal_full(self):
        dag = Spec('dttop')
        dag.normalize()

        names = ['dttop', 'dtbuild1', 'dtbuild2', 'dtlink2', 'dtrun2',
                 'dtlink1', 'dtlink3', 'dtlink4', 'dtrun1', 'dtlink5',
                 'dtrun3', 'dtbuild3']

        traversal = dag.traverse(deptype=all)
        assert [x.name for x in traversal] == names

    def test_deptype_traversal_run(self):
        dag = Spec('dttop')
        dag.normalize()

        names = ['dttop', 'dtrun1', 'dtrun3']

        traversal = dag.traverse(deptype='run')
        assert [x.name for x in traversal] == names

    def test_hash_bits(self):
        """Ensure getting first n bits of a base32-encoded DAG hash works."""

        # RFC 4648 base32 decode table
        b32 = dict((j, i) for i, j in enumerate('abcdefghijklmnopqrstuvwxyz'))
        b32.update(dict((j, i) for i, j in enumerate('234567', 26)))

        # some package hashes
        tests = [
            '35orsd4cenv743hg4i5vxha2lzayycby',
            '6kfqtj7dap3773rxog6kkmoweix5gpwo',
            'e6h6ff3uvmjbq3azik2ckr6ckwm3depv',
            'snz2juf4ij7sv77cq3vs467q6acftmur',
            '4eg47oedi5bbkhpoxw26v3oe6vamkfd7',
            'vrwabwj6umeb5vjw6flx2rnft3j457rw']

        for test_hash in tests:
            # string containing raw bits of hash ('1' and '0')
            expected = ''.join([format(b32[c], '#07b').replace('0b', '')
                                for c in test_hash])

            for bits in (1, 2, 3, 4, 7, 8, 9, 16, 64, 117, 128, 160):
                actual_int = hashutil.base32_prefix_bits(test_hash, bits)
                fmt = "#0%sb" % (bits + 2)
                actual = format(actual_int, fmt).replace('0b', '')

                assert expected[:bits] == actual

            with pytest.raises(ValueError):
                hashutil.base32_prefix_bits(test_hash, 161)

            with pytest.raises(ValueError):
                hashutil.base32_prefix_bits(test_hash, 256)

    def test_traversal_directions(self):
        """Make sure child and parent traversals of specs work."""
        # Mock spec - d is used for a diamond dependency
        spec = Spec.from_literal({
            'a': {
                'b': {
                    'c': {'d': None},
                    'e': None
                },
                'f': {
                    'g': {'d': None}
                }
            }
        })

        assert (
            ['a', 'b', 'c', 'd', 'e', 'f', 'g'] ==
            [s.name for s in spec.traverse(direction='children')])

        assert (
            ['g', 'f', 'a'] ==
            [s.name for s in spec['g'].traverse(direction='parents')])

        assert (
            ['d', 'c', 'b', 'a', 'g', 'f'] ==
            [s.name for s in spec['d'].traverse(direction='parents')])

    def test_edge_traversals(self):
        """Make sure child and parent traversals of specs work."""
        # Mock spec - d is used for a diamond dependency
        spec = Spec.from_literal({
            'a': {
                'b': {
                    'c': {'d': None},
                    'e': None
                },
                'f': {
                    'g': {'d': None}
                }
            }
        })

        assert (
            ['a', 'b', 'c', 'd', 'e', 'f', 'g'] ==
            [s.name for s in spec.traverse(direction='children')])

        assert (
            ['g', 'f', 'a'] ==
            [s.name for s in spec['g'].traverse(direction='parents')])

        assert (
            ['d', 'c', 'b', 'a', 'g', 'f'] ==
            [s.name for s in spec['d'].traverse(direction='parents')])

    def test_copy_dependencies(self):
        s1 = Spec('mpileaks ^mpich2@1.1')
        s2 = s1.copy()

        assert '^mpich2@1.1' in s2
        assert '^mpich2' in s2

    def test_construct_spec_with_deptypes(self):
        """Ensure that it is possible to construct a spec with explicit
           dependency types."""
        s = Spec.from_literal({
            'a': {
                'b': {'c:build': None},
                'd': {
                    'e:build,link': {'f:run': None}
                }
            }
        })

        assert s['b'].edges_to_dependencies(
            name='c'
        )[0].deptypes == ('build',)
        assert s['d'].edges_to_dependencies(
            name='e'
        )[0].deptypes == ('build', 'link')
        assert s['e'].edges_to_dependencies(
            name='f'
        )[0].deptypes == ('run',)

        assert s['c'].edges_from_dependents(
            name='b'
        )[0].deptypes == ('build',)
        assert s['e'].edges_from_dependents(
            name='d'
        )[0].deptypes == ('build', 'link')
        assert s['f'].edges_from_dependents(
            name='e'
        )[0].deptypes == ('run',)

    def check_diamond_deptypes(self, spec):
        """Validate deptypes in dt-diamond spec.

        This ensures that concretization works properly when two packages
        depend on the same dependency in different ways.

        """
        assert spec['dt-diamond'].edges_to_dependencies(
            name='dt-diamond-left'
        )[0].deptypes == ('build', 'link')

        assert spec['dt-diamond'].edges_to_dependencies(
            name='dt-diamond-right'
        )[0].deptypes == ('build', 'link')

        assert spec['dt-diamond-left'].edges_to_dependencies(
            name='dt-diamond-bottom'
        )[0].deptypes == ('build',)

        assert spec['dt-diamond-right'].edges_to_dependencies(
            name='dt-diamond-bottom'
        )[0].deptypes == ('build', 'link', 'run')

    def check_diamond_normalized_dag(self, spec):

        dag = Spec.from_literal({
            'dt-diamond': {
                'dt-diamond-left:build,link': {
                    'dt-diamond-bottom:build': None
                },
                'dt-diamond-right:build,link': {
                    'dt-diamond-bottom:build,link,run': None
                },

            }
        })

        assert spec.eq_dag(dag)

    def test_normalize_diamond_deptypes(self):
        """Ensure that dependency types are preserved even if the same thing is
           depended on in two different ways."""
        s = Spec('dt-diamond')
        s.normalize()

        self.check_diamond_deptypes(s)
        self.check_diamond_normalized_dag(s)

    def test_concretize_deptypes(self):
        """Ensure that dependency types are preserved after concretization."""
        s = Spec('dt-diamond')
        s.concretize()
        self.check_diamond_deptypes(s)

    def test_copy_deptypes(self):
        """Ensure that dependency types are preserved by spec copy."""
        s1 = Spec('dt-diamond')
        s1.normalize()
        self.check_diamond_deptypes(s1)
        self.check_diamond_normalized_dag(s1)

        s2 = s1.copy()
        self.check_diamond_normalized_dag(s2)
        self.check_diamond_deptypes(s2)

        s3 = Spec('dt-diamond')
        s3.concretize()
        self.check_diamond_deptypes(s3)

        s4 = s3.copy()
        self.check_diamond_deptypes(s4)

    def test_getitem_query(self):
        s = Spec('mpileaks')
        s.concretize()

        # Check a query to a non-virtual package
        a = s['callpath']

        query = a.last_query
        assert query.name == 'callpath'
        assert len(query.extra_parameters) == 0
        assert not query.isvirtual

        # Check a query to a virtual package
        a = s['mpi']

        query = a.last_query
        assert query.name == 'mpi'
        assert len(query.extra_parameters) == 0
        assert query.isvirtual

        # Check a query to a virtual package with
        # extra parameters after query
        a = s['mpi:cxx,fortran']

        query = a.last_query
        assert query.name == 'mpi'
        assert len(query.extra_parameters) == 2
        assert 'cxx' in query.extra_parameters
        assert 'fortran' in query.extra_parameters
        assert query.isvirtual

    def test_getitem_exceptional_paths(self):
        s = Spec('mpileaks')
        s.concretize()
        # Needed to get a proxy object
        q = s['mpileaks']

        # Test that the attribute is read-only
        with pytest.raises(AttributeError):
            q.libs = 'foo'

        with pytest.raises(AttributeError):
            q.libs

    def test_canonical_deptype(self):
        # special values
        assert canonical_deptype(all) == all_deptypes
        assert canonical_deptype('all') == all_deptypes

        with pytest.raises(ValueError):
            canonical_deptype(None)
        with pytest.raises(ValueError):
            canonical_deptype([None])

        # everything in all_deptypes is canonical
        for v in all_deptypes:
            assert canonical_deptype(v) == (v,)

        # tuples
        assert canonical_deptype(('build',)) == ('build',)
        assert canonical_deptype(
            ('build', 'link', 'run')) == ('build', 'link', 'run')
        assert canonical_deptype(
            ('build', 'link')) == ('build', 'link')
        assert canonical_deptype(
            ('build', 'run')) == ('build', 'run')

        # lists
        assert canonical_deptype(
            ['build', 'link', 'run']) == ('build', 'link', 'run')
        assert canonical_deptype(
            ['build', 'link']) == ('build', 'link')
        assert canonical_deptype(
            ['build', 'run']) == ('build', 'run')

        # sorting
        assert canonical_deptype(
            ('run', 'build', 'link')) == ('build', 'link', 'run')
        assert canonical_deptype(
            ('run', 'link', 'build')) == ('build', 'link', 'run')
        assert canonical_deptype(
            ('run', 'link')) == ('link', 'run')
        assert canonical_deptype(
            ('link', 'build')) == ('build', 'link')

        # can't put 'all' in tuple or list
        with pytest.raises(ValueError):
            canonical_deptype(['all'])
        with pytest.raises(ValueError):
            canonical_deptype(('all',))

        # invalid values
        with pytest.raises(ValueError):
            canonical_deptype('foo')
        with pytest.raises(ValueError):
            canonical_deptype(('foo', 'bar'))
        with pytest.raises(ValueError):
            canonical_deptype(('foo',))

    def test_invalid_literal_spec(self):
        # Can't give type 'build' to a top-level spec
        with pytest.raises(spack.spec.SpecParseError):
            Spec.from_literal({'foo:build': None})

        # Can't use more than one ':' separator
        with pytest.raises(KeyError):
            Spec.from_literal({'foo': {'bar:build:link': None}})

    def test_spec_tree_respect_deptypes(self):
        # Version-test-root uses version-test-pkg as a build dependency
        s = Spec('version-test-root').concretized()
        out = s.tree(deptypes='all')
        assert 'version-test-pkg' in out
        out = s.tree(deptypes=('link', 'run'))
        assert 'version-test-pkg' not in out


def test_synthetic_construction_of_split_dependencies_from_same_package(
        mock_packages, config
):
    # Construct in a synthetic way (i.e. without using the solver)
    # the following spec:
    #
    #          b
    #  build /   \ link,run
    #    c@2.0   c@1.0
    #
    # To demonstrate that a spec can now hold two direct
    # dependencies from the same package
    root = Spec('b').concretized()
    link_run_spec = Spec('c@1.0').concretized()
    build_spec = Spec('c@2.0').concretized()

    root.add_dependency_edge(link_run_spec, deptype='link')
    root.add_dependency_edge(link_run_spec, deptype='run')
    root.add_dependency_edge(build_spec, deptype='build')

    # Check dependencies from the perspective of root
    assert len(root.dependencies()) == 2
    assert all(x.name == 'c' for x in root.dependencies())

    assert '@2.0' in root.dependencies(name='c', deptype='build')[0]
    assert '@1.0' in root.dependencies(name='c', deptype=('link', 'run'))[0]

    # Check parent from the perspective of the dependencies
    assert len(build_spec.dependents()) == 1
    assert len(link_run_spec.dependents()) == 1
    assert build_spec.dependents() == link_run_spec.dependents()
    assert build_spec != link_run_spec


def test_synthetic_construction_bootstrapping(mock_packages, config):
    # Construct the following spec:
    #
    #  b@2.0
    #    | build
    #  b@1.0
    #
    root = Spec('b@2.0').concretized()
    bootstrap = Spec('b@1.0').concretized()

    root.add_dependency_edge(bootstrap, deptype='build')

    assert len(root.dependencies()) == 1
    assert root.dependencies()[0].name == 'b'
    assert root.name == 'b'


def test_addition_of_different_deptypes_in_multiple_calls(mock_packages, config):
    # Construct the following spec:
    #
    #  b@2.0
    #    | build,link,run
    #  b@1.0
    #
    # with three calls and check we always have a single edge
    root = Spec('b@2.0').concretized()
    bootstrap = Spec('b@1.0').concretized()

    for current_deptype in ('build', 'link', 'run'):
        root.add_dependency_edge(bootstrap, deptype=current_deptype)

        # Check edges in dependencies
        assert len(root.edges_to_dependencies()) == 1
        forward_edge = root.edges_to_dependencies(deptype=current_deptype)[0]
        assert current_deptype in forward_edge.deptypes
        assert id(forward_edge.parent) == id(root)
        assert id(forward_edge.spec) == id(bootstrap)

        # Check edges from dependents
        assert len(bootstrap.edges_from_dependents()) == 1
        backward_edge = bootstrap.edges_from_dependents(deptype=current_deptype)[0]
        assert current_deptype in backward_edge.deptypes
        assert id(backward_edge.parent) == id(root)
        assert id(backward_edge.spec) == id(bootstrap)


@pytest.mark.parametrize('c1_deptypes,c2_deptypes', [
    ('link', ('build', 'link')),
    (('link', 'run'), ('build', 'link'))
])
def test_adding_same_deptype_with_the_same_name_raises(
        mock_packages, config, c1_deptypes, c2_deptypes
):
    p = Spec('b@2.0').concretized()
    c1 = Spec('b@1.0').concretized()
    c2 = Spec('b@2.0').concretized()

    p.add_dependency_edge(c1, deptype=c1_deptypes)
    with pytest.raises(spack.error.SpackError):
        p.add_dependency_edge(c2, deptype=c2_deptypes)
