Merged changes to implement re-use of identical files from the previous (new-style) generation.

10 files changed, 1143 insertions, 194 deletions

diff --git a/obnam/__init__.py b/obnam/__init__.py
index 50a8ce4f..05d6936c 100644
--- a/obnam/__init__.py
+++ b/obnam/__init__.py
@@ -45,6 +45,7 @@ import walk
 
 from app import Application
 from oper import Operation, OperationFactory
+from store import Store
 
 from oper_backup import Backup
 from oper_forget import Forget
diff --git a/obnam/app.py b/obnam/app.py
index f1b5a416..0d517462 100644
--- a/obnam/app.py
+++ b/obnam/app.py
@@ -41,7 +41,8 @@ class Application:
         self._exclusion_strings = []
         self._exclusion_regexps = []
         self._filelist = None
-        self._host = None
+        self._prev_gen = None
+        self._store = obnam.Store(self._context)
         
         # When we traverse the file system tree while making a backup,
         # we process children before the parent. This is necessary for
@@ -60,32 +61,14 @@ class Application:
         """Get the context for the backup application."""
         return self._context
 
-    def get_host(self):
-        """Return currently active host object, or None if none is active."""
-        return self._host
+    def get_store(self):
+        """Get the Store for the backup application."""
+        return self._store
 
     def load_host(self):
         """Load the host block into memory."""
-        if not self._host:
-            host_block = obnam.io.get_host_block(self._context)
-            if host_block:
-                self._host = obnam.obj.create_host_from_block(host_block)
-            else:
-                id = self._context.config.get("backup", "host-id")
-                self._host = obnam.obj.HostBlockObject(host_id=id)
-        return self._host
-
-    def load_maps(self):
-        """Load non-content map blocks."""
-        ids = self._host.get_map_block_ids()
-        logging.info("Decoding %d mapping blocks" % len(ids))
-        obnam.io.load_maps(self._context, self._context.map, ids)
-
-    def load_content_maps(self):
-        """Load content map blocks."""
-        ids = self._host.get_contmap_block_ids()
-        logging.info("Decoding %d content mapping blocks" % len(ids))
-        obnam.io.load_maps(self._context, self._context.contmap, ids)
+        self.get_store().fetch_host_block()
+        return self.get_store().get_host_block()
 
     def get_exclusion_regexps(self):
         """Return list of regexp to exclude things from backup."""
@@ -132,6 +115,59 @@ class Application:
             else:
                 i += 1
 
+    def file_is_unchanged(self, stat1, stat2):
+        """Is a file unchanged from the previous generation?
+        
+        Given the stat results from the previous generation and the
+        current file, return True if the file is identical from the
+        previous generation (i.e., no new data to back up).
+        
+        """
+        
+        fields = ("mode", "dev", "nlink", "uid", "gid", "size", "mtime")
+        for field in fields:
+            field = "st_" + field
+            if getattr(stat1, field) != getattr(stat2, field):
+                return False
+        return True
+
+    def filegroup_is_unchanged(self, dirname, fg, filenames, stat=os.stat):
+        """Is a filegroup unchanged from the previous generation?
+        
+        Given a filegroup and a list of files in the given directory,
+        return True if all files in the filegroup are unchanged from
+        the previous generation.
+        
+        The optional stat argument can be used by unit tests to
+        override the use of os.stat.
+        
+        """
+        
+        for old_name in fg.get_names():
+            if old_name not in filenames:
+                return False    # file has been deleted
+
+            old_stat = fg.get_stat(old_name)
+            new_stat = stat(os.path.join(dirname, old_name))
+            if not self.file_is_unchanged(old_stat, new_stat):
+                return False    # file has changed
+
+        return True             # everything seems to be as before
+
+    def dir_is_unchanged(self, old, new):
+        """Has a directory changed since the previous generation?
+        
+        Return True if a directory, or its files or subdirectories,
+        has changed since the previous generation.
+        
+        """
+        
+        return (old.get_name() == new.get_name() and
+                self.file_is_unchanged(old.get_stat(), new.get_stat()) and
+                sorted(old.get_dirrefs()) == sorted(new.get_dirrefs()) and
+                sorted(old.get_filegrouprefs()) == 
+                    sorted(new.get_filegrouprefs()))
+
     def set_prevgen_filelist(self, filelist):
         """Set the Filelist object from the previous generation.
         
@@ -145,6 +181,14 @@ class Application:
         
         self._filelist = filelist
 
+    def get_previous_generation(self):
+        """Get the previous generation for a backup run."""
+        return self._prev_gen
+
+    def set_previous_generation(self, gen):
+        """Set the previous generation for a backup run."""
+        self._prev_gen = gen
+
     def find_file_by_name(self, filename):
         """Find a backed up file given its filename.
         
@@ -165,13 +209,6 @@ class Application:
         
         return None
 
-    def enqueue(self, objs):
-        """Push objects to the object queue."""
-        for obj in objs:
-            obnam.io.enqueue_object(self._context, self._context.oq,
-                                    self._context.map, obj.get_id(), 
-                                    obj.encode(), True)
-
     def compute_signature(self, filename):
         """Compute rsync signature for a filename.
         
@@ -183,19 +220,94 @@ class Application:
         sigdata = obnam.rsync.compute_signature(self._context, filename)
         id = obnam.obj.object_id_new()
         sig = obnam.obj.SignatureObject(id=id, sigdata=sigdata)
-        self.enqueue([sig])
+        self.get_store().queue_object(sig)
         return sig
 
+    def find_unchanged_filegroups(self, dirname, filegroups, filenames, 
+                                  stat=os.stat):
+        """Return list of filegroups that are unchanged.
+        
+        The filenames and stat arguments have the same meaning as 
+        for the filegroup_is_unchanged method.
+        
+        """
+        
+        unchanged = []
+        
+        for filegroup in filegroups:
+            if self.filegroup_is_unchanged(dirname, filegroup, filenames, 
+                                           stat=stat):
+                unchanged.append(filegroup)
+        
+        return unchanged
+
+    def get_file_in_previous_generation(self, pathname):
+        """Return non-directory file in previous generation, or None."""
+        gen = self.get_previous_generation()
+        if gen:
+            return self.get_store().lookup_file(gen, pathname)
+        else:
+            return None
+
+    def _reuse_existing(self, old_file):
+        return (old_file.first_string_by_kind(obnam.cmp.CONTREF),
+                old_file.first_string_by_kind(obnam.cmp.SIGREF),
+                old_file.first_string_by_kind(obnam.cmp.DELTAREF))
+
+    def _get_old_sig(self, old_file):
+        old_sigref = old_file.first_string_by_kind(obnam.cmp.SIGREF)
+        if not old_sigref:
+            return None
+        old_sig = self.get_store().get_object(old_sigref)
+        if not old_sig:
+            return None
+        return old_sig.first_string_by_kind(obnam.cmp.SIGDATA)
+
+    def _compute_delta(self, old_file, filename):
+        old_sig_data = self._get_old_sig(old_file)
+        if old_sig_data:
+            old_contref = old_file.first_string_by_kind(obnam.cmp.CONTREF)
+            old_deltaref = old_file.first_string_by_kind(obnam.cmp.DELTAREF)
+            deltapart_ids = obnam.rsync.compute_delta(self.get_context(),
+                                                      old_sig_data, filename)
+            delta_id = obnam.obj.object_id_new()
+            delta = obnam.obj.DeltaObject(id=delta_id, 
+                                          deltapart_refs=deltapart_ids, 
+                                          cont_ref=old_contref, 
+                                          delta_ref=old_deltaref)
+            self.get_store().queue_object(delta)
+            
+            sig = self.compute_signature(filename)
+
+            return None, sig.get_id(), delta.get_id()
+        else:
+            return self._backup_new(filename)
+
+    def _backup_new(self, filename):
+        contref = obnam.io.create_file_contents_object(self._context, 
+                                                       filename)
+        sig = self.compute_signature(filename)
+        sigref = sig.get_id()
+        deltaref = None
+        return contref, sigref, deltaref
+
     def add_to_filegroup(self, fg, filename):
         """Add a file to a filegroup."""
         self._context.progress.update_current_action(filename)
         st = os.stat(filename)
         if stat.S_ISREG(st.st_mode):
-            contref = obnam.io.create_file_contents_object(self._context, 
-                                                           filename)
-            sig = self.compute_signature(filename)
-            sigref = sig.get_id()
-            deltaref = None
+            unsolved = obnam.io.unsolve(self.get_context(), filename)
+            old_file = self.get_file_in_previous_generation(unsolved)
+            if old_file:
+                old_st = old_file.first_by_kind(obnam.cmp.STAT)
+                old_st = obnam.cmp.parse_stat_component(old_st)
+                if self.file_is_unchanged(old_st, st):
+                    contref, sigref, deltaref = self._reuse_existing(old_file)
+                else:
+                    contref, sigref, deltaref = self._compute_delta(old_file,
+                                                                    filename)
+            else:
+                contref, sigref, deltaref = self._backup_new(filename)
         else:
             contref = None
             sigref = None
@@ -217,12 +329,53 @@ class Application:
                 list.append(obnam.obj.FileGroupObject(id=id))
             self.add_to_filegroup(list[-1], filename)
                 
-        self.enqueue(list)
+        self.get_store().queue_objects(list)
         return list
 
     def _make_absolute(self, basename, relatives):
         return [os.path.join(basename, name) for name in relatives]
 
+    def get_dir_in_previous_generation(self, dirname):
+        """Return directory in previous generation, or None."""
+        gen = self.get_previous_generation()
+        if gen:
+            return self.get_store().lookup_dir(gen, dirname)
+        else:
+            return None
+
+    def select_files_to_back_up(self, dirname, filenames, stat=os.stat):
+        """Select files to backup in a directory, compared to previous gen.
+        
+        Look up the directory in the previous generation, and see which
+        files need backing up compared to that generation.
+        
+        Return list of unchanged filegroups, plus list of filenames
+        that need backing up.
+        
+        """
+
+        unsolved = obnam.io.unsolve(self.get_context(), dirname)
+        logging.debug("Selecting files to backup in %s (unsolved)" % unsolved)
+        logging.debug("There are %d filenames currently" % len(filenames)) 
+               
+        filenames = filenames[:]
+        old_dir = self.get_dir_in_previous_generation(unsolved)
+        if old_dir:
+            logging.debug("Found directory in previous generation")
+            old_groups = [self.get_store().get_object(id)
+                          for id in old_dir.get_filegrouprefs()]
+            filegroups = self.find_unchanged_filegroups(dirname, old_groups,
+                                                        filenames,
+                                                        stat=stat)
+            for fg in filegroups:
+                for name in fg.get_names():
+                    filenames.remove(name)
+    
+            return filegroups, filenames
+        else:
+            logging.debug("Did not find directory in previous generation")
+            return [], filenames
+
     def backup_one_dir(self, dirname, subdirs, filenames):
         """Back up non-recursively one directory.
         
@@ -232,9 +385,15 @@ class Application:
         directory.
 
         """
-
+        
+        logging.debug("Backing up non-recursively: %s" % dirname)
+        filegroups, filenames = self.select_files_to_back_up(dirname, 
+                                                             filenames)
+        logging.debug("Selected %d existing file groups, %d filenames" %
+                      (len(filegroups), len(filenames)))
         filenames = self._make_absolute(dirname, filenames)
-        filegroups = self.make_filegroups(filenames)
+
+        filegroups += self.make_filegroups(filenames)
         filegrouprefs = [fg.get_id() for fg in filegroups]
 
         dirrefs = [subdir.get_id() for subdir in subdirs]
@@ -245,9 +404,15 @@ class Application:
                                   dirrefs=dirrefs,
                                   filegrouprefs=filegrouprefs)
 
-
-        self.enqueue([dir])
-        return dir
+        unsolved = obnam.io.unsolve(self.get_context(), dirname)
+        old_dir = self.get_dir_in_previous_generation(unsolved)
+        if old_dir and self.dir_is_unchanged(old_dir, dir):
+            logging.debug("Dir is unchanged: %s" % dirname)
+            return old_dir
+        else:
+            logging.debug("Dir has changed: %s" % dirname)
+            self.get_store().queue_object(dir)
+            return dir
 
     def backup_one_root(self, root):
         """Backup one root for the next generation."""
@@ -300,60 +465,5 @@ class Application:
         gen = obnam.obj.GenerationObject(id=obnam.obj.object_id_new(),
                                          dirrefs=dirrefs, start=start,
                                          end=end)
-        self.enqueue([gen])
+        self.get_store().queue_object(gen)
         return gen
-
-    def _update_map_helper(self, map):
-        """Create new mapping blocks of a given kind, and upload them.
-        
-        Return list of block ids for the new blocks.
-
-        """
-
-        if obnam.map.get_new(map):
-            id = self._context.be.generate_block_id()
-            logging.debug("Creating mapping block %s" % id)
-            block = obnam.map.encode_new_to_block(map, id)
-            self._context.be.upload_block(id, block, True)
-            return [id]
-        else:
-            logging.debug("No new mappings, no new mapping block")
-            return []
-
-    def update_maps(self):
-        """Create new object mapping blocks and upload them."""
-        logging.debug("Creating new mapping block for normal mappings")
-        return self._update_map_helper(self._context.map)
-
-    def update_content_maps(self):
-        """Create new content object mapping blocks and upload them."""
-        logging.debug("Creating new mapping block for content mappings")
-        return self._update_map_helper(self._context.contmap)
-
-    def finish(self, new_gens):
-        """Finish a backup operation by updating maps and uploading host block.
-        
-        This also removes the host block that has been load. In other
-        words, if you want to continue using the application for anything
-        that requires the host block, you have to call load_host again.
-        
-        """
-
-        obnam.io.flush_all_object_queues(self._context)
-    
-        logging.info("Creating new mapping blocks")
-        host = self.get_host()
-        map_ids = host.get_map_block_ids() + self.update_maps()
-        contmap_ids = (host.get_contmap_block_ids() + 
-                       self.update_content_maps())
-        
-        logging.info("Creating new host block")
-        gen_ids = (host.get_generation_ids() + 
-                   [gen.get_id() for gen in new_gens])
-        host2 = obnam.obj.HostBlockObject(host_id=host.get_id(), 
-                                          gen_ids=gen_ids, 
-                                          map_block_ids=map_ids,
-                                          contmap_block_ids=contmap_ids)
-        obnam.io.upload_host_block(self._context, host2.encode())
-        
-        self._host = None
diff --git a/obnam/appTests.py b/obnam/appTests.py
index 24a982fb..4e6629f0 100644
--- a/obnam/appTests.py
+++ b/obnam/appTests.py
@@ -34,9 +34,6 @@ class ApplicationTests(unittest.TestCase):
         context = obnam.context.Context()
         self.app = obnam.Application(context)
 
-    def testHasNoHostBlockInitially(self):
-        self.failUnlessEqual(self.app.get_host(), None)
-
     def testReturnsEmptyExclusionListInitially(self):
         self.failUnlessEqual(self.app.get_exclusion_regexps(), [])
 
@@ -71,6 +68,13 @@ class ApplicationTests(unittest.TestCase):
         self.app.prune(dirname, dirnames, filenames)
         self.failUnlessEqual(dirnames, ["subdir"])
 
+    def testSetsPreviousGenerationToNoneInitially(self):
+        self.failUnlessEqual(self.app.get_previous_generation(), None)
+
+    def testSetsPreviousGenerationCorrectly(self):
+        self.app.set_previous_generation("pink")
+        self.failUnlessEqual(self.app.get_previous_generation(), "pink")
+
 
 class ApplicationLoadHostBlockTests(unittest.TestCase):
 
@@ -144,6 +148,388 @@ class ApplicationMakeFileGroupsTests(unittest.TestCase):
         self.failIf("/" in fg.get_names()[0])
 
 
+class ApplicationUnchangedFileRecognitionTests(unittest.TestCase):
+
+    def setUp(self):
+        context = obnam.context.Context()
+        self.app = obnam.Application(context)
+
+    def testSameFileWhenStatIsIdentical(self):
+        st = obnam.utils.make_stat_result()
+        self.failUnless(self.app.file_is_unchanged(st, st))
+
+    def testSameFileWhenIrrelevantFieldsChange(self):
+        st1 = obnam.utils.make_stat_result()
+        st2 = obnam.utils.make_stat_result(st_ino=42,
+                                           st_atime=42,
+                                           st_blocks=42,
+                                           st_blksize=42,
+                                           st_rdev=42)
+        self.failUnless(self.app.file_is_unchanged(st1, st2))
+
+    def testChangedFileWhenDevChanges(self):
+        st1 = obnam.utils.make_stat_result()
+        st2 = obnam.utils.make_stat_result(st_dev=42)
+        self.failIf(self.app.file_is_unchanged(st1, st2))
+
+    def testChangedFileWhenModeChanges(self):
+        st1 = obnam.utils.make_stat_result()
+        st2 = obnam.utils.make_stat_result(st_mode=42)
+        self.failIf(self.app.file_is_unchanged(st1, st2))
+
+    def testChangedFileWhenNlinkChanges(self):
+        st1 = obnam.utils.make_stat_result()
+        st2 = obnam.utils.make_stat_result(st_nlink=42)
+        self.failIf(self.app.file_is_unchanged(st1, st2))
+
+    def testChangedFileWhenUidChanges(self):
+        st1 = obnam.utils.make_stat_result()
+        st2 = obnam.utils.make_stat_result(st_uid=42)
+        self.failIf(self.app.file_is_unchanged(st1, st2))
+
+    def testChangedFileWhenGidChanges(self):
+        st1 = obnam.utils.make_stat_result()
+        st2 = obnam.utils.make_stat_result(st_gid=42)
+        self.failIf(self.app.file_is_unchanged(st1, st2))
+
+    def testChangedFileWhenSizeChanges(self):
+        st1 = obnam.utils.make_stat_result()
+        st2 = obnam.utils.make_stat_result(st_size=42)
+        self.failIf(self.app.file_is_unchanged(st1, st2))
+
+    def testChangedFileWhenMtimeChanges(self):
+        st1 = obnam.utils.make_stat_result()
+        st2 = obnam.utils.make_stat_result(st_mtime=42)
+        self.failIf(self.app.file_is_unchanged(st1, st2))
+
+
+class ApplicationUnchangedFileGroupTests(unittest.TestCase):
+
+    def setUp(self):
+        context = obnam.context.Context()
+        self.app = obnam.Application(context)
+        self.dir = "dirname"
+        self.stats = {
+            "dirname/pink": obnam.utils.make_stat_result(st_mtime=42),
+            "dirname/pretty": obnam.utils.make_stat_result(st_mtime=105),
+        }
+
+    def mock_stat(self, filename):
+        self.failUnless(filename.startswith(self.dir))
+        return self.stats[filename]
+
+    def mock_filegroup(self, filenames):
+        fg = obnam.obj.FileGroupObject(id=obnam.obj.object_id_new())
+        for filename in filenames:
+            st = self.mock_stat(os.path.join(self.dir, filename))
+            fg.add_file(filename, st, None, None, None)
+        return fg
+
+    def testSameFileGroupWhenAllFilesAreIdentical(self):
+        filenames = ["pink", "pretty"]
+        fg = self.mock_filegroup(filenames)
+        self.failUnless(self.app.filegroup_is_unchanged(self.dir, fg, 
+                                                        filenames,
+                                                        stat=self.mock_stat))
+
+    def testChangedFileGroupWhenFileHasChanged(self):
+        filenames = ["pink", "pretty"]
+        fg = self.mock_filegroup(filenames)
+        self.stats["dirname/pink"] = obnam.utils.make_stat_result(st_mtime=1)
+        self.failIf(self.app.filegroup_is_unchanged(self.dir, fg, filenames,
+                                                    stat=self.mock_stat))
+
+    def testChangedFileGroupWhenFileHasBeenRemoved(self):
+        filenames = ["pink", "pretty"]
+        fg = self.mock_filegroup(filenames)
+        self.failIf(self.app.filegroup_is_unchanged(self.dir, fg, 
+                                                    filenames[:1],
+                                                    stat=self.mock_stat))
+
+
+class ApplicationUnchangedDirTests(unittest.TestCase):
+
+    def setUp(self):
+        context = obnam.context.Context()
+        self.app = obnam.Application(context)
+
+    def make_dir(self, name, dirrefs, filegrouprefs, stat=None):
+        if stat is None:
+            stat = obnam.utils.make_stat_result()
+        return obnam.obj.DirObject(id=obnam.obj.object_id_new(),
+                                   name=name,
+                                   stat=stat,
+                                   dirrefs=dirrefs,
+                                   filegrouprefs=filegrouprefs)
+
+    def testSameDirWhenNothingHasChanged(self):
+        dir = self.make_dir("name", [], ["pink", "pretty"])
+        self.failUnless(self.app.dir_is_unchanged(dir, dir))
+
+    def testChangedDirWhenFileGroupHasBeenRemoved(self):
+        dir1 = self.make_dir("name", [], ["pink", "pretty"])
+        dir2 = self.make_dir("name", [], ["pink"])
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testChangedDirWhenFileGroupHasBeenAdded(self):
+        dir1 = self.make_dir("name", [], ["pink"])
+        dir2 = self.make_dir("name", [], ["pink", "pretty"])
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testChangedDirWhenDirHasBeenRemoved(self):
+        dir1 = self.make_dir("name", ["pink", "pretty"], [])
+        dir2 = self.make_dir("name", ["pink"], [])
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testChangedDirWhenDirHasBeenAdded(self):
+        dir1 = self.make_dir("name", ["pink"], [])
+        dir2 = self.make_dir("name", ["pink", "pretty"], [])
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testChangedDirWhenNameHasChanged(self):
+        dir1 = self.make_dir("name1", [], [])
+        dir2 = self.make_dir("name2", [], [])
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testSameDirWhenIrrelevantStatFieldsHaveChanged(self):
+        stat = obnam.utils.make_stat_result(st_ino=42,
+                                            st_atime=42,
+                                            st_blocks=42,
+                                            st_blksize=42,
+                                            st_rdev=42)
+
+        dir1 = self.make_dir("name", [], [])
+        dir2 = self.make_dir("name", [], [], stat=stat)
+        self.failUnless(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testChangedDirWhenDevHasChanged(self):
+        dir1 = self.make_dir("name1", [], [])
+        dir2 = self.make_dir("name2", [], [],
+                             stat=obnam.utils.make_stat_result(st_dev=105))
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testChangedDirWhenModeHasChanged(self):
+        dir1 = self.make_dir("name1", [], [])
+        dir2 = self.make_dir("name2", [], [],
+                             stat=obnam.utils.make_stat_result(st_mode=105))
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testChangedDirWhenNlinkHasChanged(self):
+        dir1 = self.make_dir("name1", [], [])
+        dir2 = self.make_dir("name2", [], [],
+                             stat=obnam.utils.make_stat_result(st_nlink=105))
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testChangedDirWhenUidHasChanged(self):
+        dir1 = self.make_dir("name1", [], [])
+        dir2 = self.make_dir("name2", [], [],
+                             stat=obnam.utils.make_stat_result(st_uid=105))
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testChangedDirWhenGidHasChanged(self):
+        dir1 = self.make_dir("name1", [], [])
+        dir2 = self.make_dir("name2", [], [],
+                             stat=obnam.utils.make_stat_result(st_gid=105))
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testChangedDirWhenSizeHasChanged(self):
+        dir1 = self.make_dir("name1", [], [])
+        dir2 = self.make_dir("name2", [], [],
+                             stat=obnam.utils.make_stat_result(st_size=105))
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+    def testChangedDirWhenMtimeHasChanged(self):
+        dir1 = self.make_dir("name1", [], [])
+        dir2 = self.make_dir("name2", [], [],
+                             stat=obnam.utils.make_stat_result(st_mtime=105))
+        self.failIf(self.app.dir_is_unchanged(dir1, dir2))
+
+
+class ApplicationFindUnchangedFilegroupsTests(unittest.TestCase):
+
+    def setUp(self):
+        context = obnam.context.Context()
+        self.app = obnam.Application(context)
+        self.dirname = "dirname"
+        self.stats = {
+            "dirname/pink": obnam.utils.make_stat_result(st_mtime=42),
+            "dirname/pretty": obnam.utils.make_stat_result(st_mtime=105),
+        }
+        self.names = ["pink", "pretty"]
+        self.pink = self.mock_filegroup(["pink"])
+        self.pretty = self.mock_filegroup(["pretty"])
+        self.groups = [self.pink, self.pretty]
+
+    def mock_filegroup(self, filenames):
+        fg = obnam.obj.FileGroupObject(id=obnam.obj.object_id_new())
+        for filename in filenames:
+            st = self.mock_stat(os.path.join(self.dirname, filename))
+            fg.add_file(filename, st, None, None, None)
+        return fg
+
+    def mock_stat(self, filename):
+        return self.stats[filename]
+
+    def find(self, filegroups, filenames):
+        return self.app.find_unchanged_filegroups(self.dirname, filegroups, 
+                                                  filenames,
+                                                  stat=self.mock_stat)
+
+    def testReturnsEmptyListForEmptyListOfGroups(self):
+        self.failUnlessEqual(self.find([], self.names), [])
+
+    def testReturnsEmptyListForEmptyListOfFilenames(self):
+        self.failUnlessEqual(self.find(self.groups, []), [])
+
+    def testReturnsPinkGroupWhenPrettyIsChanged(self):
+        self.stats["dirname/pretty"] = obnam.utils.make_stat_result()
+        self.failUnlessEqual(self.find(self.groups, self.names), [self.pink])
+
+    def testReturnsPrettyGroupWhenPinkIsChanged(self):
+        self.stats["dirname/pink"] = obnam.utils.make_stat_result()
+        self.failUnlessEqual(self.find(self.groups, self.names), [self.pretty])
+
+    def testReturnsPinkAndPrettyWhenBothAreUnchanged(self):
+        self.failUnlessEqual(set(self.find(self.groups, self.names)),
+                             set(self.groups))
+
+    def testReturnsEmptyListWhenEverythingIsChanged(self):
+        self.stats["dirname/pink"] = obnam.utils.make_stat_result()
+        self.stats["dirname/pretty"] = obnam.utils.make_stat_result()
+        self.failUnlessEqual(self.find(self.groups, self.names), [])
+
+
+class ApplicationGetDirInPreviousGenerationTests(unittest.TestCase):
+
+    class MockStore:
+    
+        def __init__(self):
+            self.dict = {
+                "pink": obnam.obj.DirObject(id="id", name="pink"),
+            }
+    
+        def lookup_dir(self, gen, pathname):
+            return self.dict.get(pathname, None)
+
+    def setUp(self):
+        context = obnam.context.Context()
+        self.app = obnam.Application(context)
+        self.app._store = self.MockStore()
+        self.app.set_previous_generation("prevgen")
+
+    def testReturnsNoneIfDirectoryDidNotExist(self):
+        self.failUnlessEqual(self.app.get_dir_in_previous_generation("xx"),
+                             None)
+
+    def testReturnsDirObjectIfDirectoryDidExist(self):
+        dir = self.app.get_dir_in_previous_generation("pink")
+        self.failUnlessEqual(dir.get_name(), "pink")
+
+
+class ApplicationGetFileInPreviousGenerationTests(unittest.TestCase):
+
+    class MockStore:
+    
+        def __init__(self):
+            self.dict = {
+                "pink": obnam.cmp.Component(obnam.cmp.FILE, [])
+            }
+    
+        def lookup_file(self, gen, pathname):
+            return self.dict.get(pathname, None)
+
+    def setUp(self):
+        context = obnam.context.Context()
+        self.app = obnam.Application(context)
+        self.app._store = self.MockStore()
+        self.app.set_previous_generation("prevgen")
+
+    def testReturnsNoneIfPreviousGenerationIsUnset(self):
+        self.app.set_previous_generation(None)
+        self.failUnlessEqual(self.app.get_file_in_previous_generation("xx"),
+                             None)
+
+    def testReturnsNoneIfFileDidNotExist(self):
+        self.failUnlessEqual(self.app.get_file_in_previous_generation("xx"),
+                             None)
+
+    def testReturnsFileComponentIfFileDidExist(self):
+        cmp = self.app.get_file_in_previous_generation("pink")
+        self.failUnlessEqual(cmp.get_kind(), obnam.cmp.FILE)
+
+
+class ApplicationSelectFilesToBackUpTests(unittest.TestCase):
+
+    class MockStore:
+    
+        def __init__(self, objs):
+            self._objs = objs
+    
+        def get_object(self, id):
+            for obj in self._objs:
+                if obj.get_id() == id:
+                    return obj
+            return None
+
+    def setUp(self):
+        self.dirname = "dirname"
+        self.stats = {
+            "dirname/pink": obnam.utils.make_stat_result(st_mtime=42),
+            "dirname/pretty": obnam.utils.make_stat_result(st_mtime=105),
+        }
+        self.names = ["pink", "pretty"]
+        self.pink = self.mock_filegroup(["pink"])
+        self.pretty = self.mock_filegroup(["pretty"])
+        self.groups = [self.pink, self.pretty]
+
+        self.dir = obnam.obj.DirObject(id="id", name=self.dirname,
+                                       filegrouprefs=[x.get_id() 
+                                                      for x in self.groups])
+
+        store = self.MockStore(self.groups + [self.dir])
+
+        context = obnam.context.Context()
+        self.app = obnam.Application(context)
+        self.app._store = store
+        self.app.get_dir_in_previous_generation = self.mock_get_dir_in_prevgen
+
+    def mock_get_dir_in_prevgen(self, dirname):
+        if dirname == self.dirname:
+            return self.dir
+        else:
+            return None
+
+    def mock_filegroup(self, filenames):
+        fg = obnam.obj.FileGroupObject(id=obnam.obj.object_id_new())
+        for filename in filenames:
+            st = self.mock_stat(os.path.join(self.dirname, filename))
+            fg.add_file(filename, st, None, None, None)
+        return fg
+
+    def mock_stat(self, filename):
+        return self.stats[filename]
+
+    def select(self):
+        return self.app.select_files_to_back_up(self.dirname, self.names,
+                                                stat=self.mock_stat)
+
+    def testReturnsNoOldGroupsIfDirectoryDidNotExist(self):
+        self.dir = None
+        self.failUnlessEqual(self.select(), ([], self.names))
+
+    def testReturnsNoOldGroupsIfEverythingIsChanged(self):
+        self.stats["dirname/pink"] = obnam.utils.make_stat_result()
+        self.stats["dirname/pretty"] = obnam.utils.make_stat_result()
+        self.failUnlessEqual(self.select(), ([], self.names))
+
+    def testReturnsOneGroupAndOneFileWhenJustOneIsChanged(self):
+        self.stats["dirname/pink"] = obnam.utils.make_stat_result()
+        self.failUnlessEqual(self.select(), ([self.pretty], ["pink"]))
+
+    def testReturnsBothGroupsWhenNothingIsChanged(self):
+        self.failUnlessEqual(self.select(), (self.groups, []))
+
+
 class ApplicationFindFileByNameTests(unittest.TestCase):
 
     def setUp(self):
@@ -350,86 +736,3 @@ class ApplicationBackupTests(unittest.TestCase):
         gen = self.app.backup([self.abs("pink"), self.abs("pretty")])
         self.failIfEqual(gen.get_start_time(), None)
         self.failIfEqual(gen.get_end_time(), None)
-
-
-class ApplicationMapTests(unittest.TestCase):
-
-    def setUp(self):
-        # First, set up two mappings.
-
-        context = obnam.context.Context()
-        context.cache = obnam.cache.Cache(context.config)
-        context.be = obnam.backend.init(context.config, context.cache)
-
-        obnam.map.add(context.map, "pink", "pretty")
-        obnam.map.add(context.contmap, "black", "beautiful")
-
-        map_id = context.be.generate_block_id()
-        map_block = obnam.map.encode_new_to_block(context.map, map_id)
-        context.be.upload_block(map_id, map_block, True)
-
-        contmap_id = context.be.generate_block_id()
-        contmap_block = obnam.map.encode_new_to_block(context.contmap, 
-                                                      contmap_id)
-        context.be.upload_block(contmap_id, contmap_block, True)
-
-        host_id = context.config.get("backup", "host-id")
-        host = obnam.obj.HostBlockObject(host_id=host_id,
-                                         map_block_ids=[map_id],
-                                         contmap_block_ids=[contmap_id])
-        obnam.io.upload_host_block(context, host.encode())
-
-        # Then set up the real context and app.
-
-        self.context = obnam.context.Context()
-        self.context.cache = obnam.cache.Cache(self.context.config)
-        self.context.be = obnam.backend.init(self.context.config, 
-                                             self.context.cache)
-        self.app = obnam.Application(self.context)
-        self.app.load_host()
-
-    def testHasNoMapsLoadedByDefault(self):
-        self.failUnlessEqual(obnam.map.count(self.context.map), 0)
-
-    def testHasNoContentMapsLoadedByDefault(self):
-        self.failUnlessEqual(obnam.map.count(self.context.contmap), 0)
-
-    def testLoadsMapsWhenRequested(self):
-        self.app.load_maps()
-        self.failUnlessEqual(obnam.map.count(self.context.map), 1)
-
-    def testLoadsContentMapsWhenRequested(self):
-        self.app.load_content_maps()
-        self.failUnlessEqual(obnam.map.count(self.context.contmap), 1)
-
-    def testAddsNoNewMapsWhenNothingHasChanged(self):
-        self.app.update_maps()
-        self.failUnlessEqual(obnam.map.count(self.context.map), 0)
-
-    def testAddsANewMapsWhenSomethingHasChanged(self):
-        obnam.map.add(self.context.map, "pink", "pretty")
-        self.app.update_maps()
-        self.failUnlessEqual(obnam.map.count(self.context.map), 1)
-
-    def testAddsNoNewContentMapsWhenNothingHasChanged(self):
-        self.app.update_content_maps()
-        self.failUnlessEqual(obnam.map.count(self.context.contmap), 0)
-
-    def testAddsANewContentMapsWhenSomethingHasChanged(self):
-        obnam.map.add(self.context.contmap, "pink", "pretty")
-        self.app.update_content_maps()
-        self.failUnlessEqual(obnam.map.count(self.context.contmap), 1)
-
-
-class ApplicationFinishTests(unittest.TestCase):
-
-    def testRemovesHostObject(self):
-        self.context = obnam.context.Context()
-        self.context.cache = obnam.cache.Cache(self.context.config)
-        self.context.be = obnam.backend.init(self.context.config, 
-                                             self.context.cache)
-        self.app = obnam.Application(self.context)
-        self.app.load_host()
-
-        self.app.finish([])
-        self.failUnlessEqual(self.app.get_host(), None)
diff --git a/obnam/cmp.py b/obnam/cmp.py
index ac02355d..d83092eb 100644
--- a/obnam/cmp.py
+++ b/obnam/cmp.py
@@ -111,7 +111,8 @@ class Component:
 
     def __init__(self, kind, value):
         self.kind = kind
-        assert type(value) in [type(""), type([])]
+        assert type(value) in [type(""), type([])], \
+               "Value type is %s instead of string or list" % type(value)
         if type(value) == type(""):
             self.str = value
             self.subcomponents = []
diff --git a/obnam/oper_backup.py b/obnam/oper_backup.py
index 7265c6ef..a9a5240d 100644
--- a/obnam/oper_backup.py
+++ b/obnam/oper_backup.py
@@ -34,12 +34,17 @@ class Backup(obnam.Operation):
         logging.info("Getting and decoding host block")
         app = self.get_application()
         host = app.load_host()
-        app.load_maps()
+        app.get_store().load_maps()
         # We don't need to load in file data, therefore we don't load
         # the content map blocks.
-    
+
+        old_gen_ids = host.get_generation_ids()
+        if old_gen_ids:
+            prev_gen = app.get_store().get_object(old_gen_ids[-1])
+            app.set_previous_generation(prev_gen)
+                
         gen = app.backup(roots)
         
-        app.finish([gen])
+        app.get_store().commit_host_block([gen])
     
         logging.info("Backup done")
diff --git a/obnam/oper_forget.py b/obnam/oper_forget.py
index b901da5c..40d98f41 100644
--- a/obnam/oper_forget.py
+++ b/obnam/oper_forget.py
@@ -40,8 +40,8 @@ class Forget(obnam.Operation):
         map_block_ids = host.get_map_block_ids()    
         contmap_block_ids = host.get_contmap_block_ids()    
     
-        app.load_maps()
-        app.load_content_maps()
+        app.get_store().load_maps()
+        app.get_store().load_content_maps()
     
         logging.debug("forget: Forgetting each id")
         for id in forgettable_ids:
diff --git a/obnam/oper_restore.py b/obnam/oper_restore.py
index 31129791..a4a161e1 100644
--- a/obnam/oper_restore.py
+++ b/obnam/oper_restore.py
@@ -197,8 +197,8 @@ class Restore(obnam.Operation):
         context = app.get_context()
         host = app.load_host()
     
-        app.load_maps()
-        app.load_content_maps()
+        app.get_store().load_maps()
+        app.get_store().load_content_maps()
     
         logging.debug("Getting generation object")    
         gen = obnam.io.get_object(context, gen_id)
diff --git a/obnam/oper_show_generations.py b/obnam/oper_show_generations.py
index db20eb2f..e22d9510 100644
--- a/obnam/oper_show_generations.py
+++ b/obnam/oper_show_generations.py
@@ -90,7 +90,7 @@ class ShowGenerations(obnam.Operation):
         app = self.get_application()
         context = app.get_context()
         host = app.load_host()
-        app.load_maps()
+        app.get_store().load_maps()
     
         for gen_id in gen_ids:
             gen = obnam.io.get_object(context, gen_id)
diff --git a/obnam/store.py b/obnam/store.py
new file mode 100644
index 00000000..905e66f8
--- /dev/null
+++ b/obnam/store.py
@@ -0,0 +1,228 @@
+# Copyright (C) 2008  Lars Wirzenius <liw@iki.fi>
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License along
+# with this program; if not, write to the Free Software Foundation, Inc.,
+# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+
+
+"""Abstraction for storing backup data, for Obnam."""
+
+
+import logging
+import os
+
+import obnam
+
+
+class ObjectNotFoundInStore(obnam.exception.ObnamException):
+
+    def __init__(self, id):
+        self._msg = "Object %s not found in store" % id
+
+
+class Store:
+
+    def __init__(self, context):
+        self._context = context
+        self._host = None
+
+    def get_host_block(self):
+        """Return current host block, or None if one is not known.
+        
+        You must call fetch_host_block to fetch the host block first.
+        
+        """
+
+        return self._host
+
+    def fetch_host_block(self):
+        """Fetch host block from store, if one exists.
+        
+        If a host block does not exist, it is not an error. A new
+        host block is then created.
+        
+        """
+        
+        if not self._host:
+            host_block = obnam.io.get_host_block(self._context)
+            if host_block:
+                self._host = obnam.obj.create_host_from_block(host_block)
+            else:
+                id = self._context.config.get("backup", "host-id")
+                self._host = obnam.obj.HostBlockObject(host_id=id)
+        return self._host
+
+
+    def load_maps(self):
+        """Load non-content map blocks."""
+        ids = self._host.get_map_block_ids()
+        logging.info("Decoding %d mapping blocks" % len(ids))
+        obnam.io.load_maps(self._context, self._context.map, ids)
+
+    def load_content_maps(self):
+        """Load content map blocks."""
+        ids = self._host.get_contmap_block_ids()
+        logging.info("Decoding %d content mapping blocks" % len(ids))
+        obnam.io.load_maps(self._context, self._context.contmap, ids)
+
+    def _update_map_helper(self, map):
+        """Create new mapping blocks of a given kind, and upload them.
+        
+        Return list of block ids for the new blocks.
+
+        """
+
+        if obnam.map.get_new(map):
+            id = self._context.be.generate_block_id()
+            logging.debug("Creating mapping block %s" % id)
+            block = obnam.map.encode_new_to_block(map, id)
+            self._context.be.upload_block(id, block, True)
+            return [id]
+        else:
+            logging.debug("No new mappings, no new mapping block")
+            return []
+
+    def update_maps(self):
+        """Create new object mapping blocks and upload them."""
+        logging.debug("Creating new mapping block for normal mappings")
+        return self._update_map_helper(self._context.map)
+
+    def update_content_maps(self):
+        """Create new content object mapping blocks and upload them."""
+        logging.debug("Creating new mapping block for content mappings")
+        return self._update_map_helper(self._context.contmap)
+
+    def commit_host_block(self, new_generations):
+        """Commit the current host block to the store.
+        
+        If no host block exists, create one. If one already exists,
+        update it with new info.
+        
+        NOTE that after this operation the host block has changed,
+        and you need to call get_host_block again.
+        
+        """
+
+        obnam.io.flush_all_object_queues(self._context)
+    
+        logging.info("Creating new mapping blocks")
+        host = self.get_host_block()
+        map_ids = host.get_map_block_ids() + self.update_maps()
+        contmap_ids = (host.get_contmap_block_ids() + 
+                       self.update_content_maps())
+        
+        logging.info("Creating new host block")
+        gen_ids = (host.get_generation_ids() + 
+                   [gen.get_id() for gen in new_generations])
+        host2 = obnam.obj.HostBlockObject(host_id=host.get_id(), 
+                                          gen_ids=gen_ids, 
+                                          map_block_ids=map_ids,
+                                          contmap_block_ids=contmap_ids)
+        obnam.io.upload_host_block(self._context, host2.encode())
+
+        self._host = host2
+
+    def queue_object(self, object):
+        """Queue an object for upload to the store.
+        
+        It won't necessarily be committed (i.e., uploaded, etc) until
+        you call commit_host_block. Until it is committed, you may not
+        call get_object on it.
+        
+        """
+        
+        obnam.io.enqueue_object(self._context, self._context.oq,
+                                self._context.map, object.get_id(), 
+                                object.encode(), True)
+
+    def queue_objects(self, objects):
+        """Queue a list of objects for upload to the store.
+        
+        See queue_object for information about what queuing means.
+        
+        """
+        
+        for object in objects:
+            self.queue_object(object)
+
+    def get_object(self, id):
+        """Get an object from the store.
+        
+        If the object cannot be found, raise an exception.
+        
+        """
+
+        object = obnam.io.get_object(self._context, id)
+        if object:
+            return object
+        raise ObjectNotFoundInStore(id)
+
+    def parse_pathname(self, pathname):
+        """Return list of components in pathname."""
+
+        list = []
+        while pathname:
+            dirname = os.path.dirname(pathname)
+            basename = os.path.basename(pathname)
+            if basename:
+                list.insert(0, basename)
+            elif dirname == os.sep:
+                list.insert(0, "/")
+                dirname = ""
+            pathname = dirname
+
+        return list
+
+    def _lookup_dir_from_refs(self, dirrefs, parts):
+        for ref in dirrefs:
+            dir = self.get_object(ref)
+            if dir.get_name() == parts[0]:
+                parts = parts[1:]
+                if parts:
+                    dirrefs = dir.get_dirrefs()
+                    return self._lookup_dir_from_refs(dirrefs, parts)
+                else:
+                    return dir
+        return None
+
+    def lookup_dir(self, generation, pathname):
+        """Return a DirObject that corresponds to pathname in a generation.
+        
+        Look up the directory in the generation. If it does not exist,
+        return None.
+        
+        """
+
+        parts = self.parse_pathname(pathname)
+        return self._lookup_dir_from_refs(generation.get_dirrefs(), parts)
+
+    def lookup_file(self, generation, pathname):
+        """Find a non-directory thingy in a generation.
+        
+        Return a FILE component that corresponds to the filesystem entity
+        in question. If not found, return None.
+        
+        """
+
+        dirname = os.path.dirname(pathname)
+        if dirname:
+            dir = self.lookup_dir(generation, dirname)
+            if dir:
+                basename = os.path.basename(pathname)
+                for id in dir.get_filegrouprefs():
+                    fg = self.get_object(id)
+                    file = fg.get_file(basename)
+                    if file:
+                        return file
+        
+        return None
diff --git a/obnam/storeTests.py b/obnam/storeTests.py
new file mode 100644
index 00000000..24113268
--- /dev/null
+++ b/obnam/storeTests.py
@@ -0,0 +1,301 @@
+# Copyright (C) 2008  Lars Wirzenius <liw@iki.fi>
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License along
+# with this program; if not, write to the Free Software Foundation, Inc.,
+# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+
+
+"""Unit tests for abstraction for storing backup data, for Obnam."""
+
+
+import os
+import shutil
+import socket
+import tempfile
+import unittest
+
+import obnam
+
+
+class StoreTests(unittest.TestCase):
+
+    def setUp(self):
+        context = obnam.context.Context()
+        context.cache = obnam.cache.Cache(context.config)
+        context.be = obnam.backend.init(context.config, context.cache)
+        self.store = obnam.Store(context)
+
+    def tearDown(self):
+        shutil.rmtree(self.store._context.config.get("backup", "store"),
+                      ignore_errors=True)
+        shutil.rmtree(self.store._context.config.get("backup", "cache"),
+                      ignore_errors=True)
+
+    def testReturnsNoneWhenNoHostBlockExists(self):
+        self.failUnlessEqual(self.store.get_host_block(), None)
+
+    def testReturnsAnActualHostBlockAfterFetch(self):
+        self.store.fetch_host_block()
+        host = self.store.get_host_block()
+        self.failUnless(isinstance(host, obnam.obj.HostBlockObject))
+
+    def testReturnsActualHostBlockWhenOneExists(self):
+        self.store.fetch_host_block()
+        self.store.commit_host_block([])
+        
+        context = obnam.context.Context()
+        context.be = obnam.backend.init(context.config, context.cache)
+        store = obnam.Store(context)
+        store.fetch_host_block()
+        host = store.get_host_block()
+        self.failUnless(isinstance(host, obnam.obj.HostBlockObject))
+
+    def testReplacesHostObjectInMemory(self):
+        self.store.fetch_host_block()
+        host = self.store.get_host_block()
+        self.store.commit_host_block([])
+        self.failIfEqual(self.store.get_host_block(), host)
+
+    def testCreatesNewHostBlockWhenNoneExists(self):
+        self.store.fetch_host_block()
+        host = self.store.get_host_block()
+        self.failUnlessEqual(host.get_id(), socket.gethostname())
+        self.failUnlessEqual(host.get_generation_ids(), [])
+        self.failUnlessEqual(host.get_map_block_ids(), [])
+        self.failUnlessEqual(host.get_contmap_block_ids(), [])
+
+    def testLoadsActualHostBlockWhenOneExists(self):
+        context = obnam.context.Context()
+        cache = obnam.cache.Cache(context.config)
+        context.be = obnam.backend.init(context.config, context.cache)
+        host_id = context.config.get("backup", "host-id")
+        temp = obnam.obj.HostBlockObject(host_id=host_id,
+                                         gen_ids=["pink", "pretty"])
+        obnam.io.upload_host_block(context, temp.encode())
+        
+        self.store.fetch_host_block()
+        host = self.store.get_host_block()
+        self.failUnlessEqual(host.get_generation_ids(), ["pink", "pretty"])
+
+    def testGettingNonExistentObjectRaisesException(self):
+        self.failUnlessRaises(obnam.exception.ObnamException,
+                              self.store.get_object, "pink")
+
+    def testAddsObjectToStore(self):
+        o = obnam.obj.GenerationObject(id="pink")
+        self.store.fetch_host_block()
+        self.store.queue_object(o)
+        self.store.commit_host_block([])
+        
+        context2 = obnam.context.Context()
+        context2.cache = obnam.cache.Cache(context2.config)
+        context2.be = obnam.backend.init(context2.config, context2.cache)
+        store2 = obnam.Store(context2)
+        store2.fetch_host_block()
+        store2.load_maps()
+        self.failUnless(store2.get_object(o.get_id()))
+
+    def mock_queue_object(self, object):
+        self.queued_objects.append(object)
+        
+    def testAddsSeveralObjectsToStore(self):
+        objs = [None, True, False]
+        self.queued_objects = []
+        self.store.queue_object = self.mock_queue_object
+        self.store.queue_objects(objs)
+        self.failUnlessEqual(objs, self.queued_objects)
+
+
+class StoreMapTests(unittest.TestCase):
+
+    def setUp(self):
+        # First, set up two mappings.
+
+        context = obnam.context.Context()
+        context.cache = obnam.cache.Cache(context.config)
+        context.be = obnam.backend.init(context.config, context.cache)
+
+        obnam.map.add(context.map, "pink", "pretty")
+        obnam.map.add(context.contmap, "black", "beautiful")
+
+        map_id = context.be.generate_block_id()
+        map_block = obnam.map.encode_new_to_block(context.map, map_id)
+        context.be.upload_block(map_id, map_block, True)
+
+        contmap_id = context.be.generate_block_id()
+        contmap_block = obnam.map.encode_new_to_block(context.contmap, 
+                                                      contmap_id)
+        context.be.upload_block(contmap_id, contmap_block, True)
+
+        host_id = context.config.get("backup", "host-id")
+        host = obnam.obj.HostBlockObject(host_id=host_id,
+                                         map_block_ids=[map_id],
+                                         contmap_block_ids=[contmap_id])
+        obnam.io.upload_host_block(context, host.encode())
+
+        # Then set up the real context and app.
+
+        self.context = obnam.context.Context()
+        self.context.cache = obnam.cache.Cache(self.context.config)
+        self.context.be = obnam.backend.init(self.context.config, 
+                                             self.context.cache)
+        self.store = obnam.Store(self.context)
+        self.store.fetch_host_block()
+
+    def tearDown(self):
+        shutil.rmtree(self.store._context.config.get("backup", "store"),
+                      ignore_errors=True)
+        shutil.rmtree(self.store._context.config.get("backup", "cache"),
+                      ignore_errors=True)
+
+    def testHasNoMapsLoadedByDefault(self):
+        self.failUnlessEqual(obnam.map.count(self.context.map), 0)
+
+    def testHasNoContentMapsLoadedByDefault(self):
+        self.failUnlessEqual(obnam.map.count(self.context.contmap), 0)
+
+    def testLoadsMapsWhenRequested(self):
+        self.store.load_maps()
+        self.failUnlessEqual(obnam.map.count(self.context.map), 1)
+
+    def testLoadsContentMapsWhenRequested(self):
+        self.store.load_content_maps()
+        self.failUnlessEqual(obnam.map.count(self.context.contmap), 1)
+
+    def testAddsNoNewMapsWhenNothingHasChanged(self):
+        self.store.update_maps()
+        self.failUnlessEqual(obnam.map.count(self.context.map), 0)
+
+    def testAddsANewMapsWhenSomethingHasChanged(self):
+        obnam.map.add(self.context.map, "pink", "pretty")
+        self.store.update_maps()
+        self.failUnlessEqual(obnam.map.count(self.context.map), 1)
+
+    def testAddsNoNewContentMapsWhenNothingHasChanged(self):
+        self.store.update_content_maps()
+        self.failUnlessEqual(obnam.map.count(self.context.contmap), 0)
+
+    def testAddsANewContentMapsWhenSomethingHasChanged(self):
+        obnam.map.add(self.context.contmap, "pink", "pretty")
+        self.store.update_content_maps()
+        self.failUnlessEqual(obnam.map.count(self.context.contmap), 1)
+
+
+class StorePathnameParserTests(unittest.TestCase):
+
+    def setUp(self):
+        context = obnam.context.Context()
+        self.store = obnam.Store(context)
+
+    def testReturnsRootForRoot(self):
+        self.failUnlessEqual(self.store.parse_pathname("/"), ["/"])
+
+    def testReturnsDotForDot(self):
+        self.failUnlessEqual(self.store.parse_pathname("."), ["."])
+
+    def testReturnsItselfForSingleElement(self):
+        self.failUnlessEqual(self.store.parse_pathname("foo"), ["foo"])
+
+    def testReturnsListOfPartsForMultipleElements(self):
+        self.failUnlessEqual(self.store.parse_pathname("foo/bar"), 
+                             ["foo", "bar"])
+
+    def testReturnsListOfPartsFromRootForAbsolutePathname(self):
+        self.failUnlessEqual(self.store.parse_pathname("/foo/bar"), 
+                             ["/", "foo", "bar"])
+
+    def testIgnoredTrailingSlashIfNotRoot(self):
+        self.failUnlessEqual(self.store.parse_pathname("foo/bar/"), 
+                             ["foo", "bar"])
+
+
+class StoreLookupTests(unittest.TestCase):
+
+    def create_data_dir(self):
+        dirname = tempfile.mkdtemp()
+        file(os.path.join(dirname, "file1"), "w").close()
+        os.mkdir(os.path.join(dirname, "dir1"))
+        os.mkdir(os.path.join(dirname, "dir1", "dir2"))
+        file(os.path.join(dirname, "dir1", "dir2", "file2"), "w").close()
+        return dirname
+
+    def create_context(self):
+        context = obnam.context.Context()
+        context.cache = obnam.cache.Cache(context.config)
+        context.be = obnam.backend.init(context.config, context.cache)
+        return context
+
+    def setUp(self):
+        self.datadir = self.create_data_dir()
+        self.dirbasename = os.path.basename(self.datadir)
+
+        app = obnam.Application(self.create_context())
+        app.load_host()
+        gen = app.backup([self.datadir])
+        app.get_store().commit_host_block([gen])
+        
+        self.store = obnam.Store(self.create_context())
+        self.store.fetch_host_block()
+        self.store.load_maps()
+        gen_ids = self.store.get_host_block().get_generation_ids()
+        self.gen = self.store.get_object(gen_ids[0])
+
+    def tearDown(self):
+        shutil.rmtree(self.datadir)
+        shutil.rmtree(self.store._context.config.get("backup", "store"))
+
+    def testFindsBackupRoot(self):
+        dir = self.store.lookup_dir(self.gen, self.dirbasename)
+        self.failUnless(dir.get_name(), self.dirbasename)
+
+    def testFindsFirstSubdir(self):
+        pathname = os.path.join(self.dirbasename, "dir1")
+        dir = self.store.lookup_dir(self.gen, pathname)
+        self.failUnless(dir.get_name(), "dir1")
+
+    def testFindsSecondSubdir(self):
+        pathname = os.path.join(self.dirbasename, "dir1", "dir2")
+        dir = self.store.lookup_dir(self.gen, pathname)
+        self.failUnless(dir.get_name(), "dir2")
+
+    def testDoesNotFindNonExistentDir(self):
+        self.failUnlessEqual(self.store.lookup_dir(self.gen, "notexist"),
+                             None)
+
+    def testDoesNotFindNonExistentFileInSubDirectory(self):
+        pathname = os.path.join(self.dirbasename, "dir1", "notexist")
+        file = self.store.lookup_file(self.gen, pathname)
+        self.failUnlessEqual(file, None)
+
+    def testDoesNotFindNonExistentFileInSubSubDirectory(self):
+        pathname = os.path.join(self.dirbasename, "dir1", "dir2", "notexist")
+        file = self.store.lookup_file(self.gen, pathname)
+        self.failUnlessEqual(file, None)
+
+    def testDoesNotFindNonExistentFileInRoot(self):
+        pathname = os.path.join(self.dirbasename, "notexist")
+        file = self.store.lookup_file(self.gen, pathname)
+        self.failUnlessEqual(file, None)
+
+    def filename(self, file):
+        return file.first_string_by_kind(obnam.cmp.FILENAME)
+
+    def testFindsFileInRootDirectory(self):
+        pathname = os.path.join(self.dirbasename, "file1")
+        file = self.store.lookup_file(self.gen, pathname)
+        self.failUnlessEqual(self.filename(file), "file1")
+
+    def testFindsFileInSubDirectory(self):
+        pathname = os.path.join(self.dirbasename, "dir1", "dir2", "file2")
+        file = self.store.lookup_file(self.gen, pathname)
+        self.failUnlessEqual(self.filename(file), "file2")