Fixes #1720: spack reindex fails with invalid ref count. (#1867)

* Fixes #1720: spack reindex fails with invalid ref count.

- Database graph wasn't being built properly; dependencies were set up
  incorrectly in the nodes that ended up in the graph on reindex.

- Reworked _add to increment ref count properly and to always build
  bottom-up to make the logic simpler to understand.

* Add checks to ensure DB is a valid merkle tree.

3 files changed, 80 insertions, 49 deletions

diff --git a/lib/spack/spack/database.py b/lib/spack/spack/database.py
index e450b4d424..1adad5e90b 100644
--- a/lib/spack/spack/database.py
+++ b/lib/spack/spack/database.py
@@ -50,7 +50,7 @@ from llnl.util.lock import *
 
 import spack.spec
 from spack.version import Version
-from spack.spec import Spec
+from spack.spec import *
 from spack.error import SpackError
 from spack.repository import UnknownPackageError
 import spack.util.spack_yaml as syaml
@@ -64,6 +64,9 @@ _db_version = Version('0.9.2')
 # Default timeout for spack database locks is 5 min.
 _db_lock_timeout = 60
 
+# Types of dependencies tracked by the database
+_tracked_deps = nobuild
+
 
 def _autospec(function):
     """Decorator that automatically converts the argument of a single-arg
@@ -232,8 +235,6 @@ class Database(object):
                                  spec.format('$_$#'), dname, dhash[:7]))
                     continue
 
-                # defensive copy (not sure everything handles extra
-                # parent links yet)
                 child = data[dhash].spec
                 spec._add_dependency(child, dtypes)
 
@@ -328,7 +329,7 @@ class Database(object):
         self._data = data
 
     def reindex(self, directory_layout):
-        """Build database index from scratch based from a directory layout.
+        """Build database index from scratch based on a directory layout.
 
         Locks the DB if it isn't locked already.
 
@@ -359,9 +360,6 @@ class Database(object):
 
                 # Ask the directory layout to traverse the filesystem.
                 for spec in directory_layout.all_specs():
-                    # Create a spec for each known package and add it.
-                    path = directory_layout.path_for_spec(spec)
-
                     # Try to recover explicit value from old DB, but
                     # default it to False if DB was corrupt.
                     explicit = False
@@ -370,7 +368,7 @@ class Database(object):
                         if old_info is not None:
                             explicit = old_info.explicit
 
-                    self._add(spec, path, directory_layout, explicit=explicit)
+                    self._add(spec, directory_layout, explicit=explicit)
 
                 self._check_ref_counts()
 
@@ -389,10 +387,7 @@ class Database(object):
         counts = {}
         for key, rec in self._data.items():
             counts.setdefault(key, 0)
-            # XXX(deptype): This checks all dependencies, but build
-            #               dependencies might be able to be dropped in the
-            #               future.
-            for dep in rec.spec.dependencies():
+            for dep in rec.spec.dependencies(_tracked_deps):
                 dep_key = dep.dag_hash()
                 counts.setdefault(dep_key, 0)
                 counts[dep_key] += 1
@@ -450,52 +445,62 @@ class Database(object):
             # reindex() takes its own write lock, so no lock here.
             self.reindex(spack.install_layout)
 
-    def _add(self, spec, path, directory_layout=None, explicit=False):
-        """Add an install record for spec at path to the database.
+    def _add(self, spec, directory_layout=None, explicit=False):
+        """Add an install record for this spec to the database.
 
-        This assumes that the spec is not already installed. It
-        updates the ref counts on dependencies of the spec in the DB.
+        Assumes spec is installed in ``layout.path_for_spec(spec)``.
 
-        This operation is in-memory, and does not lock the DB.
+        Also ensures dependencies are present and updated in the DB as
+        either intsalled or missing.
 
         """
-        key = spec.dag_hash()
-        if key in self._data:
-            rec = self._data[key]
-            rec.installed = True
+        if not spec.concrete:
+            raise NonConcreteSpecAddError(
+                "Specs added to DB must be concrete.")
 
-            # TODO: this overwrites a previous install path (when path !=
-            # self._data[key].path), and the old path still has a
-            # dependent in the DB. We could consider re-RPATH-ing the
-            # dependents.  This case is probably infrequent and may not be
-            # worth fixing, but this is where we can discover it.
-            rec.path = path
-
-        else:
-            self._data[key] = InstallRecord(spec, path, True,
-                                            explicit=explicit)
-            for dep in spec.dependencies(('link', 'run')):
-                self._increment_ref_count(dep, directory_layout)
+        for dep in spec.dependencies(_tracked_deps):
+            dkey = dep.dag_hash()
+            if dkey not in self._data:
+                self._add(dep, directory_layout, explicit=False)
 
-    def _increment_ref_count(self, spec, directory_layout=None):
-        """Recursively examine dependencies and update their DB entries."""
         key = spec.dag_hash()
         if key not in self._data:
             installed = False
             path = None
             if directory_layout:
                 path = directory_layout.path_for_spec(spec)
-                installed = os.path.isdir(path)
+                try:
+                    directory_layout.check_installed(spec)
+                    installed = True
+                except DirectoryLayoutError as e:
+                    tty.warn(
+                        'Dependency missing due to corrupt install directory:',
+                        path, str(e))
+
+            # Create a new install record with no deps initially.
+            new_spec = spec.copy(deps=False)
+            self._data[key] = InstallRecord(
+                new_spec, path, installed, ref_count=0, explicit=explicit)
+
+            # Connect dependencies from the DB to the new copy.
+            for name, dep in spec.dependencies_dict(_tracked_deps).iteritems():
+                dkey = dep.spec.dag_hash()
+                new_spec._add_dependency(self._data[dkey].spec, dep.deptypes)
+                self._data[dkey].ref_count += 1
+
+            # Mark concrete once everything is built, and preserve
+            # the original hash of concrete specs.
+            new_spec._mark_concrete()
+            new_spec._hash = key
 
-            self._data[key] = InstallRecord(spec.copy(), path, installed)
-
-            for dep in spec.dependencies(('link', 'run')):
-                self._increment_ref_count(dep)
+        else:
+            # If it is already there, mark it as installed.
+            self._data[key].installed = True
 
-        self._data[key].ref_count += 1
+        self._data[key].explicit = explicit
 
     @_autospec
-    def add(self, spec, path, explicit=False):
+    def add(self, spec, directory_layout, explicit=False):
         """Add spec at path to database, locking and reading DB to sync.
 
         ``add()`` will lock and read from the DB on disk.
@@ -504,7 +509,7 @@ class Database(object):
         # TODO: ensure that spec is concrete?
         # Entire add is transactional.
         with self.write_transaction():
-            self._add(spec, path, explicit=explicit)
+            self._add(spec, directory_layout, explicit=explicit)
 
     def _get_matching_spec_key(self, spec, **kwargs):
         """Get the exact spec OR get a single spec that matches."""
@@ -534,7 +539,7 @@ class Database(object):
 
         if rec.ref_count == 0 and not rec.installed:
             del self._data[key]
-            for dep in spec.dependencies('link'):
+            for dep in spec.dependencies(_tracked_deps):
                 self._decrement_ref_count(dep)
 
     def _remove(self, spec):
@@ -548,7 +553,7 @@ class Database(object):
             return rec.spec
 
         del self._data[key]
-        for dep in rec.spec.dependencies('link'):
+        for dep in rec.spec.dependencies(_tracked_deps):
             self._decrement_ref_count(dep)
 
         # Returns the concrete spec so we know it in the case where a
@@ -657,6 +662,10 @@ class CorruptDatabaseError(SpackError):
     """Raised when errors are found while reading the database."""
 
 
+class NonConcreteSpecAddError(SpackError):
+    """Raised when attemptint to add non-concrete spec to DB."""
+
+
 class InvalidDatabaseVersionError(SpackError):
 
     def __init__(self, expected, found):
diff --git a/lib/spack/spack/package.py b/lib/spack/spack/package.py
index cffc795586..cb7f6b3f39 100644
--- a/lib/spack/spack/package.py
+++ b/lib/spack/spack/package.py
@@ -1053,7 +1053,8 @@ class Package(object):
 
         # note: PARENT of the build process adds the new package to
         # the database, so that we don't need to re-read from file.
-        spack.installed_db.add(self.spec, self.prefix, explicit=explicit)
+        spack.installed_db.add(
+            self.spec, spack.install_layout, explicit=explicit)
 
     def sanity_check_prefix(self):
         """This function checks whether install succeeded."""
diff --git a/lib/spack/spack/test/database.py b/lib/spack/spack/test/database.py
index b114bbacb8..4395f17f97 100644
--- a/lib/spack/spack/test/database.py
+++ b/lib/spack/spack/test/database.py
@@ -124,6 +124,19 @@ class DatabaseTest(MockDatabase):
             self.assertEqual(new_rec.path,      rec.path)
             self.assertEqual(new_rec.installed, rec.installed)
 
+    def _check_merkleiness(self):
+        """Ensure the spack database is a valid merkle graph."""
+        all_specs = spack.installed_db.query(installed=any)
+
+        seen = {}
+        for spec in all_specs:
+            for dep in spec.dependencies():
+                hash_key = dep.dag_hash()
+                if hash_key not in seen:
+                    seen[hash_key] = id(dep)
+                else:
+                    self.assertEqual(seen[hash_key], id(dep))
+
     def _check_db_sanity(self):
         """Utiilty function to check db against install layout."""
         expected = sorted(spack.install_layout.all_specs())
@@ -133,10 +146,17 @@ class DatabaseTest(MockDatabase):
         for e, a in zip(expected, actual):
             self.assertEqual(e, a)
 
+        self._check_merkleiness()
+
     def test_020_db_sanity(self):
         """Make sure query() returns what's actually in the db."""
         self._check_db_sanity()
 
+    def test_025_reindex(self):
+        """Make sure reindex works and ref counts are valid."""
+        spack.installed_db.reindex(spack.install_layout)
+        self._check_db_sanity()
+
     def test_030_db_sanity_from_another_process(self):
         def read_and_modify():
             self._check_db_sanity()  # check that other process can read DB
@@ -203,9 +223,10 @@ class DatabaseTest(MockDatabase):
         self.assertTrue(concrete_spec not in remaining)
 
         # add it back and make sure everything is ok.
-        self.installed_db.add(concrete_spec, "")
+        self.installed_db.add(concrete_spec, spack.install_layout)
         installed = self.installed_db.query()
-        self.assertEqual(len(installed), len(original))
+        self.assertTrue(concrete_spec in installed)
+        self.assertEqual(installed, original)
 
         # sanity check against direcory layout and check ref counts.
         self._check_db_sanity()
@@ -233,7 +254,7 @@ class DatabaseTest(MockDatabase):
         self.assertEqual(self.installed_db.get_record('mpich').ref_count, 1)
 
         # Put the spec back
-        self.installed_db.add(rec.spec, rec.path)
+        self.installed_db.add(rec.spec, spack.install_layout)
 
         # record is present again
         self.assertEqual(