Rewrote substantial portion to make things cleaner

git-svn-id: http://svn.savannah.nongnu.org/svn/rdiff-backup/trunk@63 2b77aa54-bcbc-44c9-a7ec-4f6cf2b41109

2 files changed, 450 insertions, 344 deletions

diff --git a/rdiff-backup/rdiff_backup/restore.py b/rdiff-backup/rdiff_backup/restore.py
index 6e51b81..75dfec0 100644
--- a/rdiff-backup/rdiff_backup/restore.py
+++ b/rdiff-backup/rdiff_backup/restore.py
@@ -10,124 +10,73 @@ import tempfile
 class RestoreError(Exception): pass
 
 class Restore:
-	def RestoreFile(rest_time, rpbase, mirror_rel_index, inclist, rptarget):
-		"""Non-recursive restore function
+	def Restore(inc_rpath, mirror, target, rest_time):
+		"""Recursively restore inc_rpath and mirror to target at rest_time
 
-		rest_time is the time in seconds to restore to,
-		rpbase is the base name of the file being restored,
-		mirror_rel_index is the same as in RestoreRecursive,
-		inclist is a list of rpaths containing all the relevant increments,
-		and rptarget is the rpath that will be written with the restored file.
-
-		"""
-		if not inclist and not (rpbase and rpbase.lstat()):
-			return # no increments were applicable
-		Log("Restoring %s with increments %s to %s" %
-			(rpbase and rpbase.path,
-			 Restore.inclist2str(inclist), rptarget.path), 5)
-
-		if (Globals.preserve_hardlinks and
-			Hardlink.restore_link(mirror_rel_index, rptarget)):
-			RPath.copy_attribs(inclist and inclist[-1] or rpbase, rptarget)
-			return
-
-		if not inclist or inclist[0].getinctype() == "diff":
-			assert rpbase and rpbase.lstat(), \
-				   "No base to go with incs %s" % Restore.inclist2str(inclist)
-			RPath.copy_with_attribs(rpbase, rptarget)
-		for inc in inclist: Restore.applyinc(inc, rptarget)
-
-	def inclist2str(inclist):
-		"""Return string version of inclist for logging"""
-		return ",".join(map(lambda x: x.path, inclist))
-
-	def sortincseq(rest_time, inclist):
-		"""Sort the inc sequence, and throw away irrelevant increments"""
-		incpairs = map(lambda rp: (Time.stringtotime(rp.getinctime()), rp),
-					   inclist)
-		# Only consider increments at or after the time being restored
-		incpairs = filter(lambda pair: pair[0] >= rest_time, incpairs)
-
-		# Now throw away older unnecessary increments
-		incpairs.sort()
-		i = 0
-		while(i < len(incpairs)):
-			# Only diff type increments require later versions
-			if incpairs[i][1].getinctype() != "diff": break
-			i = i+1
-		incpairs = incpairs[:i+1]
-
-		# Return increments in reversed order (latest first)
-		incpairs.reverse()
-		return map(lambda pair: pair[1], incpairs)
-
-	def applyinc(inc, target):
-		"""Apply increment rp inc to targetrp target"""
-		Log("Applying increment %s to %s" % (inc.path, target.path), 6)
-		inctype = inc.getinctype()
-		if inctype == "diff":
-			if not target.lstat():
-				raise RestoreError("Bad increment sequence at " + inc.path)
-			Rdiff.patch_action(target, inc,
-							   delta_compressed = inc.isinccompressed()
-							   ).execute()
-		elif inctype == "dir":
-			if not target.isdir():
-				if target.lstat():
-					raise RestoreError("File %s already exists" % target.path)
-				target.mkdir()
-		elif inctype == "missing": return
-		elif inctype == "snapshot":
-			if inc.isinccompressed():
-				target.write_from_fileobj(inc.open("rb", compress = 1))
-			else: RPath.copy(inc, target)
-		else: raise RestoreError("Unknown inctype %s" % inctype)
-		RPath.copy_attribs(inc, target)
-
-	def RestoreRecursive(rest_time, mirror_base, mirror_rel_index,
-						 baseinc_tup, target_base):
-		"""Recursive restore function.
+		Like restore_recusive below, but with a more friendly
+		interface (it converts to DSRPaths if necessary, finds the inc
+		files with the appropriate base, and makes rid).
 
 		rest_time is the time in seconds to restore to;
 
-		mirror_base is an rpath of the mirror directory corresponding
-		to the one to be restored;
+		inc_rpath should not be the name of an increment file, but the
+		increment file shorn of its suffixes and thus should have the
+		same index as mirror.
 
-		mirror_rel_index is the index of the mirror_base relative to
-		the root of the mirror directory.  (The mirror_base itself
-		always has index (), as its index must match that of
-		target_base.)
+		"""
+		if not isinstance(mirror, DSRPath):
+			mirror = DSRPath(source = 1, mirror)
+		if not isinstance(target, DSRPath):
+			target = DSRPath(source = None, target)
+
+		dirname, basename = inc_rpath.dirsplit()
+		parent_dir = RPath(inc_rpath.conn, dirname, ())
+		index = inc_rpath.index
+
+		if inc_rpath.index:
+			get_inc_ext = lambda filename: \
+						  RPath(inc_rpath.conn, inc_rpath.base,
+								inc_rpath.index[:-1] + (filename,))
+		else: get_inc_ext = lambda filename: \
+							RPath(inc_rpath.conn, os.join(dirname, filename))
+
+		inc_list = []
+		for filename in parent_dir.listdir():
+			inc = get_inc_ext(filename)
+			if inc.getincbase_str() == basename: inc_list.append(inc)
+
+		rid = RestoreIncrementData(index, inc_rpath, inc_list)
+		rid.sortincseq(rest_time)
+		Restore.restore_recursive(index, mirror, rid, target, rest_time)
+
+	def restore_recursive(index, mirror, rid, target, time):
+		"""Recursive restore function.
 
-		baseinc_tup is the inc tuple (incdir, list of incs) to be
-		restored;
+		rid is a RestoreIncrementData object whose inclist is already
+		sortedincseq'd, and target is the dsrp to restore to.
 
-		and target_base in the dsrp of the target directory.
+		Note that target may have a different index than mirror and
+		rid, because we may be restoring a file whose index is, say
+		('foo','bar') to a target whose path does not contain
+		"foo/bar".
 
 		"""
-		assert isinstance(target_base, DSRPath)
-		baseinc_tup = IndexedTuple(baseinc_tup.index, (baseinc_tup[0],
-						  Restore.sortincseq(rest_time, baseinc_tup[1])))
-
-		collated = Restore.yield_collated_tuples((), mirror_base,
-										   baseinc_tup, target_base, rest_time)
-		mirror_finalizer = DestructiveStepping.Finalizer()
-		target_finalizer = DestructiveStepping.Finalizer()
-
-		for mirror, inc_tup, target in collated:
-			inclist = inc_tup and inc_tup[1] or []
-			DestructiveStepping.initialize(target, None)
-			Restore.RestoreFile(rest_time, mirror, mirror_rel_index,
-								inclist, target)
-			target_finalizer(target)
-			if mirror: mirror_finalizer(mirror)
-		target_finalizer.getresult()
-		mirror_finalizer.getresult()			
-
-	def yield_collated_tuples(index, mirrorrp, inc_tup, target, rest_time):
-		"""Iterate collated tuples starting with given args
-
-		A collated tuple is an IndexedTuple (mirrorrp, inc_tuple, target).
-		inc_tuple is itself an IndexedTuple.  target is an rpath where
+		assert isinstance(mirror, DSRPath) and isinstance(target, DSRPath)
+		assert mirror.index == rid.index
+
+		mirror_finalizer = DestructiveSteppingFinalizer()
+		target_finalizer = DestructiveSteppingFinalizer()
+		for rcd in Restore.yield_rcds(rid.index, mirror, rid, target, time):
+			rcd.RestoreFile()
+			if rcd.mirror: mirror_finalizer(rcd.mirror)
+			target_finalizer(rcd.target)
+		target_finalizer.Finish()
+		mirror_finalizer.Finish()
+
+	def yield_rcds(index, mirrorrp, rid, target, rest_time):
+		"""Iterate RestoreCombinedData objects starting with given args
+
+		rid is a RestoreCombinedData object.  target is an rpath where
 		the created file should go.
 
 		In this case the "mirror" directory is treated as the source,
@@ -138,47 +87,40 @@ class Restore:
 		select_result = Globals.select_mirror.Select(target)
 		if select_result == 0: return
 
-		inc_base = inc_tup and inc_tup[0]
 		if mirrorrp and (not Globals.select_source.Select(mirrorrp) or
 						 DestructiveStepping.initialize(mirrorrp, None)):
 			mirrorrp = None
-		collated_tuple = IndexedTuple(index, (mirrorrp, inc_tup, target))
-		if mirrorrp and mirrorrp.isdir() or inc_base and inc_base.isdir():
-			depth_tuples = Restore.yield_collated_tuples_dir(index, mirrorrp,
-									   			  inc_tup, target, rest_time)
-		else: depth_tuples = None
+		rcd = RestoreCombinedData(rid, mirrorrp, target)
+
+		if mirrorrp and mirrorrp.isdir() or rid and rid.inc_rpath.isdir():
+			sub_rcds = Restore.yield_sub_rcds(index, mirrorrp, rid,
+											  target, rest_time)
+		else: sub_rcds = None
 
 		if select_result == 1:
-			yield collated_tuple
-			if depth_tuples:
-				for tup in depth_tuples: yield tup
+			yield rcd
+			if sub_rcds:
+				for sub_rcd in sub_rcds: yield sub_rcd
 		elif select_result == 2:
-			if depth_tuples:
-				try: first = depth_tuples.next()
+			if sub_rcds:
+				try: first = sub_rcds.next()
 				except StopIteration: return # no tuples found inside, skip
-				yield collated_tuple
+				yield rcd
 				yield first
-				for tup in depth_tuples: yield tup
+				for sub_rcd in sub_rcds: yield sub_rcd
 
-	def yield_collated_tuples_dir(index, mirrorrp, inc_tup, target, rest_time):
+	def yield_collated_tuples_dir(index, mirrorrp, rid, target, rest_time):
 		"""Yield collated tuples from inside given args"""
 		if not Restore.check_dir_exists(mirrorrp, inc_tup): return
-		if mirrorrp and mirrorrp.isdir():
-			dirlist = mirrorrp.listdir()
-			dirlist.sort()
-			mirror_list = map(lambda x: IndexedTuple(x, (mirrorrp.append(x),)),
-							  dirlist)
-		else: mirror_list = []
-		inc_list = Restore.get_inc_tuples(inc_tup, rest_time)
-
-		for indexed_tup in RORPIter.CollateIterators(iter(mirror_list),
-													 iter(inc_list)):
-			filename = indexed_tup.index
-			new_inc_tup = indexed_tup[1]
-			new_mirrorrp = indexed_tup[0] and indexed_tup[0][0]
-			for new_col_tup in Restore.yield_collated_tuples(
-				index + (filename,), new_mirrorrp, new_inc_tup,
-				target.append(filename), rest_time): yield new_col_tup
+		mirror_iter = Restore.yield_mirrorrps(mirrorrp)
+		rid_iter = Restore.get_rids(rid, rest_time)
+
+		for indexed_tup in RORPIter.CollateIterators(mirror_iter, rid_iter):
+			index = indexed_tup.index
+			new_mirrorrp, new_rid = indexed_tup
+			for rcd in Restore.yield_collated_tuples(index, new_mirrorrp,
+				     new_rid, target.new_index(index), rest_time):
+				yield rcd
 
 	def check_dir_exists(mirrorrp, inc_tuple):
 		"""Return true if target should be a directory"""
@@ -188,56 +130,167 @@ class Restore:
 		elif mirrorrp: return mirrorrp.isdir() # if no incs, copy mirror
 		else: return None
 
-	def get_inc_tuples(inc_tuple, rest_time):
-		"""Return list of inc tuples in given rpath of increment directory
+	def yield_mirrorrps(mirrorrp):
+		"""Yield mirrorrps underneath given mirrorrp"""
+		if mirrorrp and mirrorrp.isdir():
+			dirlist = mirrorrp.listdir()
+			dirlist.sort()
+			for filename in dirlist: yield mirrorrp.append(filename)
+
+	def yield_rids(rid, rest_time):
+		"""Yield RestoreIncrementData objects within given rid dir
 
-		An increment tuple is an IndexedTuple (pair).  The second
-		element in the pair is a list of increments with the same
-		base.  The first element is the rpath of the corresponding
-		base.  Usually this base is a directory, otherwise it is
-		ignored.  If there are increments whose corresponding base
+		If the rid doesn't correspond to a directory, don't yield any
+		elements.  If there are increments whose corresponding base
 		doesn't exist, the first element will be None.  All the rpaths
 		involved correspond to files in the increment directory.
 
 		"""
-		if not inc_tuple: return []
-		oldindex, incdir = inc_tuple.index, inc_tuple[0]
-		if not incdir.isdir(): return []
-		inc_list_dict = {} # Index tuple lists by index
-		dirlist = incdir.listdir()		
+		if not rid or not rid.inc_rpath or not rid.inc_rpath.isdir(): return
+		rid_dict = {} # dictionary of basenames:rids
+		dirlist = rid.inc_rpath.listdir()		
 
-		def affirm_dict_indexed(index):
-			"""Make sure the inc_list_dict has given index"""
-			if not inc_list_dict.has_key(index):
-				inc_list_dict[index] = [None, []]
+		def affirm_dict_indexed(basename):
+			"""Make sure the rid dictionary has given basename as key"""
+			if not inc_list_dict.has_key(basename):
+				rid_dict[basename] = RestoreIncrementData(
+					rid.index + (basename,), None, []) # init with empty rid
 
 		def add_to_dict(filename):
 			"""Add filename to the inc tuple dictionary"""
-			rp = incdir.append(filename)
+			rp = rid.inc_rpath.append(filename)
 			if rp.isincfile():
 				basename = rp.getincbase_str()
 				affirm_dict_indexed(basename)
-				inc_list_dict[basename][1].append(rp)
+				rid_dict[basename].inc_list.append(rp)
 			elif rp.isdir():
 				affirm_dict_indexed(filename)
-				inc_list_dict[filename][0] = rp
-
-		def index2tuple(index):
-			"""Return inc_tuple version of dictionary entry by index
-
-			Also runs sortincseq to sort the increments and remove
-			irrelevant ones.  This is done here so we can avoid
-			descending into .missing directories.
-
-			"""
-			incbase, inclist = inc_list_dict[index]
-			inclist = Restore.sortincseq(rest_time, inclist)
-			if not inclist: return None # no relevant increments, so ignore
-			return IndexedTuple(index, (incbase, inclist))
+				rid_dict[filename].inc_rpath = rp
 
 		for filename in dirlist: add_to_dict(filename)
 		keys = inc_list_dict.keys()
 		keys.sort()
-		return filter(lambda x: x, map(index2tuple, keys))
+
+		# sortincseq now to avoid descending .missing directories later
+		for key in keys:
+			rid = rid_dict[key]
+			if rid.inc_rpath or rid.inc_list:
+				rid.sortincseq(rest_time)
+				yield rid
 
 MakeStatic(Restore)
+
+
+class RestoreIncrementData:
+	"""Contains information about a specific index from the increments dir
+
+	This is just a container class, used because it would be easier to
+	work with than an IndexedTuple.
+
+	"""
+	def __init__(self, index, inc_rpath, inc_list):
+		self.index = index
+		self.inc_rpath = inc_rpath
+		self.inc_list = inc_list
+
+	def sortincseq(self, rest_time):
+		"""Sort self.inc_list sequence, throwing away irrelevant increments"""
+		incpairs = map(lambda rp: (Time.stringtotime(rp.getinctime()), rp),
+					   self.inc_list)
+		# Only consider increments at or after the time being restored
+		incpairs = filter(lambda pair: pair[0] >= rest_time, incpairs)
+
+		# Now throw away older unnecessary increments
+		incpairs.sort()
+		i = 0
+		while(i < len(incpairs)):
+			# Only diff type increments require later versions
+			if incpairs[i][1].getinctype() != "diff": break
+			i = i+1
+		incpairs = incpairs[:i+1]
+
+		# Return increments in reversed order (latest first)
+		incpairs.reverse()
+		self.inc_list = map(lambda pair: pair[1], incpairs)
+
+
+class RestoreCombinedData:
+	"""Combine index information from increment and mirror directories
+
+	This is similar to RestoreIncrementData but has mirror information
+	also.
+
+	"""
+	def __init__(self, rid, mirror, target):
+		"""Init - set values from one or both if they exist
+
+		mirror and target are DSRPaths of the corresponding files in
+		the mirror and target directory respectively.  rid is a
+		RestoreIncrementData as defined above
+
+		"""
+		if rid:
+			self.index = rid.index
+			self.inc_rpath = rid.inc_rpath
+			self.inc_list = rid.inc_list
+			if mirror:
+				self.mirror = mirror
+				assert mirror.index == self.index
+		elif mirror:
+			self.index = mirror.index
+			self.mirror = mirror
+		else: assert None, "neither rid nor mirror given"
+		self.target = target
+
+	def RestoreFile(self):
+		"""Non-recursive restore function """
+		if not self.inc_list and not (self.mirror and self.mirror.lstat()):
+			return # no increments were applicable
+		self.log()
+
+		if self.restore_hardlink(): return
+
+		if not inclist or inclist[0].getinctype() == "diff":
+			assert self.mirror and self.mirror.lstat(), \
+				   "No base to go with incs for %s" % self.target.path
+			RPath.copy_with_attribs(self.mirror, self.target)
+		for inc in self.inc_list: self.applyinc(inc, self.target)
+
+	def log(self)
+		"""Log current restore action"""
+		inc_string = ','.join(map(lambda x: x.path, self.inc_list))
+		Log("Restoring %s with increments %s to %s" %
+			(self.mirror and self.mirror.path,
+			 inc_string, self.target.path), 5)
+
+	def restore_hardlink(self):
+		"""Hard link target and return true if hard linking appropriate"""
+		if (Globals.preserve_hardlinks and
+			Hardlink.restore_link(self.index, self.target)):
+			RPath.copy_attribs(self.inc_list and inc_list[-1] or
+							   self.mirror, self.target)
+			return 1
+		return None
+
+	def applyinc(self, inc, target):
+		"""Apply increment rp inc to targetrp target"""
+		Log("Applying increment %s to %s" % (inc.path, target.path), 6)
+		inctype = inc.getinctype()
+		if inctype == "diff":
+			if not target.lstat():
+				raise RestoreError("Bad increment sequence at " + inc.path)
+			Rdiff.patch_action(target, inc,
+							   delta_compressed = inc.isinccompressed()
+							   ).execute()
+		elif inctype == "dir":
+			if not target.isdir():
+				if target.lstat():
+					raise RestoreError("File %s already exists" % target.path)
+				target.mkdir()
+		elif inctype == "missing": return
+		elif inctype == "snapshot":
+			if inc.isinccompressed():
+				target.write_from_fileobj(inc.open("rb", compress = 1))
+			else: RPath.copy(inc, target)
+		else: raise RestoreError("Unknown inctype %s" % inctype)
+		RPath.copy_attribs(inc, target)
diff --git a/rdiff-backup/src/restore.py b/rdiff-backup/src/restore.py
index 6e51b81..75dfec0 100644
--- a/rdiff-backup/src/restore.py
+++ b/rdiff-backup/src/restore.py
@@ -10,124 +10,73 @@ import tempfile
 class RestoreError(Exception): pass
 
 class Restore:
-	def RestoreFile(rest_time, rpbase, mirror_rel_index, inclist, rptarget):
-		"""Non-recursive restore function
+	def Restore(inc_rpath, mirror, target, rest_time):
+		"""Recursively restore inc_rpath and mirror to target at rest_time
 
-		rest_time is the time in seconds to restore to,
-		rpbase is the base name of the file being restored,
-		mirror_rel_index is the same as in RestoreRecursive,
-		inclist is a list of rpaths containing all the relevant increments,
-		and rptarget is the rpath that will be written with the restored file.
-
-		"""
-		if not inclist and not (rpbase and rpbase.lstat()):
-			return # no increments were applicable
-		Log("Restoring %s with increments %s to %s" %
-			(rpbase and rpbase.path,
-			 Restore.inclist2str(inclist), rptarget.path), 5)
-
-		if (Globals.preserve_hardlinks and
-			Hardlink.restore_link(mirror_rel_index, rptarget)):
-			RPath.copy_attribs(inclist and inclist[-1] or rpbase, rptarget)
-			return
-
-		if not inclist or inclist[0].getinctype() == "diff":
-			assert rpbase and rpbase.lstat(), \
-				   "No base to go with incs %s" % Restore.inclist2str(inclist)
-			RPath.copy_with_attribs(rpbase, rptarget)
-		for inc in inclist: Restore.applyinc(inc, rptarget)
-
-	def inclist2str(inclist):
-		"""Return string version of inclist for logging"""
-		return ",".join(map(lambda x: x.path, inclist))
-
-	def sortincseq(rest_time, inclist):
-		"""Sort the inc sequence, and throw away irrelevant increments"""
-		incpairs = map(lambda rp: (Time.stringtotime(rp.getinctime()), rp),
-					   inclist)
-		# Only consider increments at or after the time being restored
-		incpairs = filter(lambda pair: pair[0] >= rest_time, incpairs)
-
-		# Now throw away older unnecessary increments
-		incpairs.sort()
-		i = 0
-		while(i < len(incpairs)):
-			# Only diff type increments require later versions
-			if incpairs[i][1].getinctype() != "diff": break
-			i = i+1
-		incpairs = incpairs[:i+1]
-
-		# Return increments in reversed order (latest first)
-		incpairs.reverse()
-		return map(lambda pair: pair[1], incpairs)
-
-	def applyinc(inc, target):
-		"""Apply increment rp inc to targetrp target"""
-		Log("Applying increment %s to %s" % (inc.path, target.path), 6)
-		inctype = inc.getinctype()
-		if inctype == "diff":
-			if not target.lstat():
-				raise RestoreError("Bad increment sequence at " + inc.path)
-			Rdiff.patch_action(target, inc,
-							   delta_compressed = inc.isinccompressed()
-							   ).execute()
-		elif inctype == "dir":
-			if not target.isdir():
-				if target.lstat():
-					raise RestoreError("File %s already exists" % target.path)
-				target.mkdir()
-		elif inctype == "missing": return
-		elif inctype == "snapshot":
-			if inc.isinccompressed():
-				target.write_from_fileobj(inc.open("rb", compress = 1))
-			else: RPath.copy(inc, target)
-		else: raise RestoreError("Unknown inctype %s" % inctype)
-		RPath.copy_attribs(inc, target)
-
-	def RestoreRecursive(rest_time, mirror_base, mirror_rel_index,
-						 baseinc_tup, target_base):
-		"""Recursive restore function.
+		Like restore_recusive below, but with a more friendly
+		interface (it converts to DSRPaths if necessary, finds the inc
+		files with the appropriate base, and makes rid).
 
 		rest_time is the time in seconds to restore to;
 
-		mirror_base is an rpath of the mirror directory corresponding
-		to the one to be restored;
+		inc_rpath should not be the name of an increment file, but the
+		increment file shorn of its suffixes and thus should have the
+		same index as mirror.
 
-		mirror_rel_index is the index of the mirror_base relative to
-		the root of the mirror directory.  (The mirror_base itself
-		always has index (), as its index must match that of
-		target_base.)
+		"""
+		if not isinstance(mirror, DSRPath):
+			mirror = DSRPath(source = 1, mirror)
+		if not isinstance(target, DSRPath):
+			target = DSRPath(source = None, target)
+
+		dirname, basename = inc_rpath.dirsplit()
+		parent_dir = RPath(inc_rpath.conn, dirname, ())
+		index = inc_rpath.index
+
+		if inc_rpath.index:
+			get_inc_ext = lambda filename: \
+						  RPath(inc_rpath.conn, inc_rpath.base,
+								inc_rpath.index[:-1] + (filename,))
+		else: get_inc_ext = lambda filename: \
+							RPath(inc_rpath.conn, os.join(dirname, filename))
+
+		inc_list = []
+		for filename in parent_dir.listdir():
+			inc = get_inc_ext(filename)
+			if inc.getincbase_str() == basename: inc_list.append(inc)
+
+		rid = RestoreIncrementData(index, inc_rpath, inc_list)
+		rid.sortincseq(rest_time)
+		Restore.restore_recursive(index, mirror, rid, target, rest_time)
+
+	def restore_recursive(index, mirror, rid, target, time):
+		"""Recursive restore function.
 
-		baseinc_tup is the inc tuple (incdir, list of incs) to be
-		restored;
+		rid is a RestoreIncrementData object whose inclist is already
+		sortedincseq'd, and target is the dsrp to restore to.
 
-		and target_base in the dsrp of the target directory.
+		Note that target may have a different index than mirror and
+		rid, because we may be restoring a file whose index is, say
+		('foo','bar') to a target whose path does not contain
+		"foo/bar".
 
 		"""
-		assert isinstance(target_base, DSRPath)
-		baseinc_tup = IndexedTuple(baseinc_tup.index, (baseinc_tup[0],
-						  Restore.sortincseq(rest_time, baseinc_tup[1])))
-
-		collated = Restore.yield_collated_tuples((), mirror_base,
-										   baseinc_tup, target_base, rest_time)
-		mirror_finalizer = DestructiveStepping.Finalizer()
-		target_finalizer = DestructiveStepping.Finalizer()
-
-		for mirror, inc_tup, target in collated:
-			inclist = inc_tup and inc_tup[1] or []
-			DestructiveStepping.initialize(target, None)
-			Restore.RestoreFile(rest_time, mirror, mirror_rel_index,
-								inclist, target)
-			target_finalizer(target)
-			if mirror: mirror_finalizer(mirror)
-		target_finalizer.getresult()
-		mirror_finalizer.getresult()			
-
-	def yield_collated_tuples(index, mirrorrp, inc_tup, target, rest_time):
-		"""Iterate collated tuples starting with given args
-
-		A collated tuple is an IndexedTuple (mirrorrp, inc_tuple, target).
-		inc_tuple is itself an IndexedTuple.  target is an rpath where
+		assert isinstance(mirror, DSRPath) and isinstance(target, DSRPath)
+		assert mirror.index == rid.index
+
+		mirror_finalizer = DestructiveSteppingFinalizer()
+		target_finalizer = DestructiveSteppingFinalizer()
+		for rcd in Restore.yield_rcds(rid.index, mirror, rid, target, time):
+			rcd.RestoreFile()
+			if rcd.mirror: mirror_finalizer(rcd.mirror)
+			target_finalizer(rcd.target)
+		target_finalizer.Finish()
+		mirror_finalizer.Finish()
+
+	def yield_rcds(index, mirrorrp, rid, target, rest_time):
+		"""Iterate RestoreCombinedData objects starting with given args
+
+		rid is a RestoreCombinedData object.  target is an rpath where
 		the created file should go.
 
 		In this case the "mirror" directory is treated as the source,
@@ -138,47 +87,40 @@ class Restore:
 		select_result = Globals.select_mirror.Select(target)
 		if select_result == 0: return
 
-		inc_base = inc_tup and inc_tup[0]
 		if mirrorrp and (not Globals.select_source.Select(mirrorrp) or
 						 DestructiveStepping.initialize(mirrorrp, None)):
 			mirrorrp = None
-		collated_tuple = IndexedTuple(index, (mirrorrp, inc_tup, target))
-		if mirrorrp and mirrorrp.isdir() or inc_base and inc_base.isdir():
-			depth_tuples = Restore.yield_collated_tuples_dir(index, mirrorrp,
-									   			  inc_tup, target, rest_time)
-		else: depth_tuples = None
+		rcd = RestoreCombinedData(rid, mirrorrp, target)
+
+		if mirrorrp and mirrorrp.isdir() or rid and rid.inc_rpath.isdir():
+			sub_rcds = Restore.yield_sub_rcds(index, mirrorrp, rid,
+											  target, rest_time)
+		else: sub_rcds = None
 
 		if select_result == 1:
-			yield collated_tuple
-			if depth_tuples:
-				for tup in depth_tuples: yield tup
+			yield rcd
+			if sub_rcds:
+				for sub_rcd in sub_rcds: yield sub_rcd
 		elif select_result == 2:
-			if depth_tuples:
-				try: first = depth_tuples.next()
+			if sub_rcds:
+				try: first = sub_rcds.next()
 				except StopIteration: return # no tuples found inside, skip
-				yield collated_tuple
+				yield rcd
 				yield first
-				for tup in depth_tuples: yield tup
+				for sub_rcd in sub_rcds: yield sub_rcd
 
-	def yield_collated_tuples_dir(index, mirrorrp, inc_tup, target, rest_time):
+	def yield_collated_tuples_dir(index, mirrorrp, rid, target, rest_time):
 		"""Yield collated tuples from inside given args"""
 		if not Restore.check_dir_exists(mirrorrp, inc_tup): return
-		if mirrorrp and mirrorrp.isdir():
-			dirlist = mirrorrp.listdir()
-			dirlist.sort()
-			mirror_list = map(lambda x: IndexedTuple(x, (mirrorrp.append(x),)),
-							  dirlist)
-		else: mirror_list = []
-		inc_list = Restore.get_inc_tuples(inc_tup, rest_time)
-
-		for indexed_tup in RORPIter.CollateIterators(iter(mirror_list),
-													 iter(inc_list)):
-			filename = indexed_tup.index
-			new_inc_tup = indexed_tup[1]
-			new_mirrorrp = indexed_tup[0] and indexed_tup[0][0]
-			for new_col_tup in Restore.yield_collated_tuples(
-				index + (filename,), new_mirrorrp, new_inc_tup,
-				target.append(filename), rest_time): yield new_col_tup
+		mirror_iter = Restore.yield_mirrorrps(mirrorrp)
+		rid_iter = Restore.get_rids(rid, rest_time)
+
+		for indexed_tup in RORPIter.CollateIterators(mirror_iter, rid_iter):
+			index = indexed_tup.index
+			new_mirrorrp, new_rid = indexed_tup
+			for rcd in Restore.yield_collated_tuples(index, new_mirrorrp,
+				     new_rid, target.new_index(index), rest_time):
+				yield rcd
 
 	def check_dir_exists(mirrorrp, inc_tuple):
 		"""Return true if target should be a directory"""
@@ -188,56 +130,167 @@ class Restore:
 		elif mirrorrp: return mirrorrp.isdir() # if no incs, copy mirror
 		else: return None
 
-	def get_inc_tuples(inc_tuple, rest_time):
-		"""Return list of inc tuples in given rpath of increment directory
+	def yield_mirrorrps(mirrorrp):
+		"""Yield mirrorrps underneath given mirrorrp"""
+		if mirrorrp and mirrorrp.isdir():
+			dirlist = mirrorrp.listdir()
+			dirlist.sort()
+			for filename in dirlist: yield mirrorrp.append(filename)
+
+	def yield_rids(rid, rest_time):
+		"""Yield RestoreIncrementData objects within given rid dir
 
-		An increment tuple is an IndexedTuple (pair).  The second
-		element in the pair is a list of increments with the same
-		base.  The first element is the rpath of the corresponding
-		base.  Usually this base is a directory, otherwise it is
-		ignored.  If there are increments whose corresponding base
+		If the rid doesn't correspond to a directory, don't yield any
+		elements.  If there are increments whose corresponding base
 		doesn't exist, the first element will be None.  All the rpaths
 		involved correspond to files in the increment directory.
 
 		"""
-		if not inc_tuple: return []
-		oldindex, incdir = inc_tuple.index, inc_tuple[0]
-		if not incdir.isdir(): return []
-		inc_list_dict = {} # Index tuple lists by index
-		dirlist = incdir.listdir()		
+		if not rid or not rid.inc_rpath or not rid.inc_rpath.isdir(): return
+		rid_dict = {} # dictionary of basenames:rids
+		dirlist = rid.inc_rpath.listdir()		
 
-		def affirm_dict_indexed(index):
-			"""Make sure the inc_list_dict has given index"""
-			if not inc_list_dict.has_key(index):
-				inc_list_dict[index] = [None, []]
+		def affirm_dict_indexed(basename):
+			"""Make sure the rid dictionary has given basename as key"""
+			if not inc_list_dict.has_key(basename):
+				rid_dict[basename] = RestoreIncrementData(
+					rid.index + (basename,), None, []) # init with empty rid
 
 		def add_to_dict(filename):
 			"""Add filename to the inc tuple dictionary"""
-			rp = incdir.append(filename)
+			rp = rid.inc_rpath.append(filename)
 			if rp.isincfile():
 				basename = rp.getincbase_str()
 				affirm_dict_indexed(basename)
-				inc_list_dict[basename][1].append(rp)
+				rid_dict[basename].inc_list.append(rp)
 			elif rp.isdir():
 				affirm_dict_indexed(filename)
-				inc_list_dict[filename][0] = rp
-
-		def index2tuple(index):
-			"""Return inc_tuple version of dictionary entry by index
-
-			Also runs sortincseq to sort the increments and remove
-			irrelevant ones.  This is done here so we can avoid
-			descending into .missing directories.
-
-			"""
-			incbase, inclist = inc_list_dict[index]
-			inclist = Restore.sortincseq(rest_time, inclist)
-			if not inclist: return None # no relevant increments, so ignore
-			return IndexedTuple(index, (incbase, inclist))
+				rid_dict[filename].inc_rpath = rp
 
 		for filename in dirlist: add_to_dict(filename)
 		keys = inc_list_dict.keys()
 		keys.sort()
-		return filter(lambda x: x, map(index2tuple, keys))
+
+		# sortincseq now to avoid descending .missing directories later
+		for key in keys:
+			rid = rid_dict[key]
+			if rid.inc_rpath or rid.inc_list:
+				rid.sortincseq(rest_time)
+				yield rid
 
 MakeStatic(Restore)
+
+
+class RestoreIncrementData:
+	"""Contains information about a specific index from the increments dir
+
+	This is just a container class, used because it would be easier to
+	work with than an IndexedTuple.
+
+	"""
+	def __init__(self, index, inc_rpath, inc_list):
+		self.index = index
+		self.inc_rpath = inc_rpath
+		self.inc_list = inc_list
+
+	def sortincseq(self, rest_time):
+		"""Sort self.inc_list sequence, throwing away irrelevant increments"""
+		incpairs = map(lambda rp: (Time.stringtotime(rp.getinctime()), rp),
+					   self.inc_list)
+		# Only consider increments at or after the time being restored
+		incpairs = filter(lambda pair: pair[0] >= rest_time, incpairs)
+
+		# Now throw away older unnecessary increments
+		incpairs.sort()
+		i = 0
+		while(i < len(incpairs)):
+			# Only diff type increments require later versions
+			if incpairs[i][1].getinctype() != "diff": break
+			i = i+1
+		incpairs = incpairs[:i+1]
+
+		# Return increments in reversed order (latest first)
+		incpairs.reverse()
+		self.inc_list = map(lambda pair: pair[1], incpairs)
+
+
+class RestoreCombinedData:
+	"""Combine index information from increment and mirror directories
+
+	This is similar to RestoreIncrementData but has mirror information
+	also.
+
+	"""
+	def __init__(self, rid, mirror, target):
+		"""Init - set values from one or both if they exist
+
+		mirror and target are DSRPaths of the corresponding files in
+		the mirror and target directory respectively.  rid is a
+		RestoreIncrementData as defined above
+
+		"""
+		if rid:
+			self.index = rid.index
+			self.inc_rpath = rid.inc_rpath
+			self.inc_list = rid.inc_list
+			if mirror:
+				self.mirror = mirror
+				assert mirror.index == self.index
+		elif mirror:
+			self.index = mirror.index
+			self.mirror = mirror
+		else: assert None, "neither rid nor mirror given"
+		self.target = target
+
+	def RestoreFile(self):
+		"""Non-recursive restore function """
+		if not self.inc_list and not (self.mirror and self.mirror.lstat()):
+			return # no increments were applicable
+		self.log()
+
+		if self.restore_hardlink(): return
+
+		if not inclist or inclist[0].getinctype() == "diff":
+			assert self.mirror and self.mirror.lstat(), \
+				   "No base to go with incs for %s" % self.target.path
+			RPath.copy_with_attribs(self.mirror, self.target)
+		for inc in self.inc_list: self.applyinc(inc, self.target)
+
+	def log(self)
+		"""Log current restore action"""
+		inc_string = ','.join(map(lambda x: x.path, self.inc_list))
+		Log("Restoring %s with increments %s to %s" %
+			(self.mirror and self.mirror.path,
+			 inc_string, self.target.path), 5)
+
+	def restore_hardlink(self):
+		"""Hard link target and return true if hard linking appropriate"""
+		if (Globals.preserve_hardlinks and
+			Hardlink.restore_link(self.index, self.target)):
+			RPath.copy_attribs(self.inc_list and inc_list[-1] or
+							   self.mirror, self.target)
+			return 1
+		return None
+
+	def applyinc(self, inc, target):
+		"""Apply increment rp inc to targetrp target"""
+		Log("Applying increment %s to %s" % (inc.path, target.path), 6)
+		inctype = inc.getinctype()
+		if inctype == "diff":
+			if not target.lstat():
+				raise RestoreError("Bad increment sequence at " + inc.path)
+			Rdiff.patch_action(target, inc,
+							   delta_compressed = inc.isinccompressed()
+							   ).execute()
+		elif inctype == "dir":
+			if not target.isdir():
+				if target.lstat():
+					raise RestoreError("File %s already exists" % target.path)
+				target.mkdir()
+		elif inctype == "missing": return
+		elif inctype == "snapshot":
+			if inc.isinccompressed():
+				target.write_from_fileobj(inc.open("rb", compress = 1))
+			else: RPath.copy(inc, target)
+		else: raise RestoreError("Unknown inctype %s" % inctype)
+		RPath.copy_attribs(inc, target)