Merge branch 'index' into improvements

* index:
  Removed index test marker for custom commits as this boils down to a good way to add files to the index/remove them and make commits which are possibly customized with custom parents
  index writing now creates a sha on the content making it possible to write valid indices after manually removing or altering entriesgst
  Implemented merge/resolve handling , but realized that index writing is not yet working properly as it is sha1 checked as well. This explains what my 20 byte 'extension_data' actually is ;)
  index: Added write_tree method including test
  index.iter_blobs method added including tests ( which have been improved generally for more coverage )
  tree.traverse: Added prune functionality - previously the predciate did both, pruning and preventing to return items
  Improved testing of index against trees, tests succeed with next commit
  Initial version of merge including tests for one-way, two-way and tree-way merge
  index writing added including simple test, improved docs of IndexEntry
  improved IndexEntry type and added test for parsing of the stage
  Improved tuple access of EntryIndex class including test, stage and type access still needs to be decoded though
  Added initial version of the index reading from file - IndexEntry interface is to be improved though, writing needs to be implemented as well
  Added frame for index implementation and testing

10 files changed, 703 insertions, 22 deletions

diff --git a/TODO b/TODO
index f1b49a0c..afda659a 100644
--- a/TODO
+++ b/TODO
@@ -26,7 +26,10 @@ Object
   It would be good to improve things there as cat-file keeps all the data in a buffer
   before it writes it. Hence it does not write to a stream directly, which can be 
   bad if files are large, say 1GB :).
-
+* Effectively Objects only store hexsha's in their id attributes, so in fact 
+  it should be renamed to 'sha'. There was a time when references where allowed as 
+  well, but now objects will be 'baked' to the actual sha to assure comparisons work.
+  
 Config
 ------
 * Expand .get* methods of GitConfigParser to support default value. If it is not None, 
@@ -46,12 +49,13 @@ Overhaul docs - check examples, check looks, improve existing docs
 
 Index
 -----
-* Index class required for special handling ? Probably considering what I want 
-  to do ! Dulwich can already write the index, and read trees, although it 
-  could be improved as well and could possibly be made faster unless we want 
-  to use the c modules ( not for now )
-* Index Merge ( merge two trees into the index to quickly see conflicts ). 
-  Its possible to write it into a separate index file that can be read separately.
+* write_tree should write a tree directly, which would require ability to create
+  objects in the first place. Should be rather simple as it is 
+  "tree" bytes datablock | sha1sum and zipped.
+  Currently we use some file swapping and the git command to do it which probably 
+  is much slower. The thing is that properly writing a tree from an index involves
+  creating several tree objects, so in the end it might be slower. 
+  Hmm, probably its okay to use the command unless we go c(++)
 
 Remote
 ------
@@ -74,8 +78,6 @@ Tree
 * Should return submodules during iteration ( identifies as commit )
 * Work through test and check for test-case cleanup and completeness ( what about
   testing whether it raises on invalid input ? ). See 6dc7799d44e1e5b9b77fd19b47309df69ec01a99
-* Derive from Iterable, simple pipe it through to Commit objects and iterate using 
-  commit.tree.
   
 Testing
 -------
@@ -84,5 +86,5 @@ Testing
   as forking a shared repo in a tmp directory. In that moment, we probably want to 
   facility committing and checkouts as well.
   - Use these tests for git-remote as we need to test push
-
-
+  - Also assure that the test-case setup is a bit more consistent ( Derive from TestCase, possibly
+    make repo a class member instead of an instance member
diff --git a/lib/git/__init__.py b/lib/git/__init__.py
index 75ce887b..e3043dc9 100644
--- a/lib/git/__init__.py
+++ b/lib/git/__init__.py
@@ -19,7 +19,7 @@ from git.cmd import Git
 from git.repo import Repo
 from git.stats import Stats
 from git.remote import Remote
-
+from git.index import *
 
 __all__ = [ name for name, obj in locals().items()
 			if not (name.startswith('_') or inspect.ismodule(obj)) ]
diff --git a/lib/git/errors.py b/lib/git/errors.py
index e9a637c0..18c58073 100644
--- a/lib/git/errors.py
+++ b/lib/git/errors.py
@@ -27,6 +27,6 @@ class GitCommandError(Exception):
 		self.command = command
 
 	def __str__(self):
-		return repr("%s returned exit status %d" %
-					(str(self.command), self.status))
+		return repr("'%s' returned exit status %d: %r" %
+					(' '.join(self.command), self.status, str(self.stderr)))
 
diff --git a/lib/git/index.py b/lib/git/index.py
new file mode 100644
index 00000000..9a55da15
--- /dev/null
+++ b/lib/git/index.py
@@ -0,0 +1,510 @@
+# index.py
+# Copyright (C) 2008, 2009 Michael Trier (mtrier@gmail.com) and contributors
+#
+# This module is part of GitPython and is released under
+# the BSD License: http://www.opensource.org/licenses/bsd-license.php
+"""
+Module containing Index implementation, allowing to perform all kinds of index
+manipulations such as querying and merging.
+"""
+import struct
+import binascii
+import mmap
+import objects
+import tempfile
+import os
+import stat
+from git.objects import Blob, Tree
+from git.utils import SHA1Writer
+
+class _TemporaryFileSwap(object):
+	"""
+	Utility class moving a file to a temporary location within the same directory
+	and moving it back on to where on object deletion.
+	"""
+	__slots__ = ("file_path", "tmp_file_path")
+	
+	def __init__(self, file_path):
+		self.file_path = file_path
+		self.tmp_file_path = self.file_path + tempfile.mktemp('','','')
+		os.rename(self.file_path, self.tmp_file_path)
+		
+	def __del__(self):
+		if os.path.isfile(self.tmp_file_path):
+			os.rename(self.tmp_file_path, self.file_path)
+	
+
+class IndexEntry(tuple):
+	"""
+	Allows convenient access to IndexEntry data without completely unpacking it.
+	
+	Attributes usully accessed often are cached in the tuple whereas others are 
+	unpacked on demand.
+	
+	See the properties for a mapping between names and tuple indices.
+	"""
+	@property
+	def ctime(self):
+		"""
+		Returns
+			Tuple(int_time_seconds_since_epoch, int_nano_seconds) of the 
+			file's creation time
+		"""
+		return struct.unpack(">LL", self[0])
+		
+	@property
+	def mtime(self):
+		"""
+		See ctime property, but returns modification time
+		"""
+		return struct.unpack(">LL", self[1])
+	
+	@property
+	def dev(self):
+		"""
+		Device ID
+		"""
+		return self[2] 
+	
+	@property
+	def inode(self):
+		"""
+		Inode ID
+		"""
+		return self[3]
+		
+	@property
+	def mode(self):
+		"""
+		File Mode, compatible to stat module constants
+		"""
+		return self[4]
+		
+	@property
+	def uid(self):
+		"""
+		User ID
+		"""
+		return self[5]
+		
+	@property
+	def gid(self):
+		"""
+		Group ID
+		"""
+		return self[6]
+
+	@property
+	def size(self):
+		"""
+		Uncompressed size of the blob
+		
+		Note
+			Will be 0 if the stage is not 0 ( hence it is an unmerged entry )
+		"""
+		return self[7]
+		
+	@property
+	def sha(self):
+		"""
+		hex sha of the blob
+		"""
+		return self[8]
+		
+	@property
+	def stage(self):
+		"""
+		Stage of the entry, either:
+			0 = default stage
+			1 = stage before a merge or common ancestor entry in case of a 3 way merge
+			2 = stage of entries from the 'left' side of the merge
+			3 = stage of entries from the right side of the merge
+		Note:
+			For more information, see http://www.kernel.org/pub/software/scm/git/docs/git-read-tree.html
+		"""
+		return self[9]
+
+	@property
+	def path(self):
+		return self[10]
+		
+		
+	@classmethod
+	def from_blob(cls, blob):
+		"""
+		Returns
+			Minimal entry resembling the given blob objecft
+		"""
+		time = struct.pack(">LL", 0, 0)
+		return IndexEntry((time, time, 0, 0, blob.mode, 0, 0, blob.size, blob.id, 0, blob.path))
+
+
+class Index(object):
+	"""
+	Implements an Index that can be manipulated using a native implementation in 
+	order to save git command function calls wherever possible.
+	
+	It provides custom merging facilities allowing to merge without actually changing
+	your index or your working tree. This way you can perform own test-merges based
+	on the index only without having to deal with the working copy. This is useful 
+	in case of partial working trees.
+	
+	``Entries``
+	The index contains an entries dict whose keys are tuples of type IndexEntry
+	to facilitate access.
+	"""
+	__slots__ = ( "repo", "version", "entries", "_extension_data" )
+	_VERSION = 2			# latest version we support
+	S_IFGITLINK	= 0160000
+	
+	def __init__(self, repo, stream = None):
+		"""
+		Initialize this Index instance, optionally from the given ``stream``
+		"""
+		self.repo = repo
+		self.entries = dict()
+		self.version = self._VERSION
+		self._extension_data = ''
+		if stream is not None:
+			self._read_from_stream(stream)
+	
+	@classmethod
+	def _read_entry(cls, stream):
+		"""Return: One entry of the given stream"""
+		beginoffset = stream.tell()
+		ctime = struct.unpack(">8s", stream.read(8))[0]
+		mtime = struct.unpack(">8s", stream.read(8))[0]
+		(dev, ino, mode, uid, gid, size, sha, flags) = \
+			struct.unpack(">LLLLLL20sH", stream.read(20 + 4 * 6 + 2))
+		path_size = flags & 0x0fff
+		path = stream.read(path_size)
+		
+		real_size = ((stream.tell() - beginoffset + 8) & ~7)
+		data = stream.read((beginoffset + real_size) - stream.tell())
+		return IndexEntry((ctime, mtime, dev, ino, mode, uid, gid, size, 
+				binascii.hexlify(sha), flags >> 12, path))
+		
+	@classmethod
+	def _read_header(cls, stream):
+		"""Return tuple(version_long, num_entries) from the given stream"""
+		type_id = stream.read(4)
+		if type_id != "DIRC":
+			raise AssertionError("Invalid index file header: %r" % type_id)
+		version, num_entries = struct.unpack(">LL", stream.read(4 * 2))
+		assert version in (1, 2)
+		return version, num_entries
+		
+	def _read_from_stream(self, stream):
+		"""
+		Initialize this instance with index values read from the given stream
+		
+		Note
+			We explicitly do not clear the entries dict here to allow for reading 
+			multiple chunks from multiple streams into the same Index instance
+		"""
+		self.version, num_entries = self._read_header(stream)
+		count = 0
+		while count < num_entries:
+			entry = self._read_entry(stream)
+			self.entries[(entry.path, entry.stage)] = entry
+			count += 1
+		# END for each entry
+		
+		# the footer contains extension data and a sha on the content so far
+		# Keep the extension footer,and verify we have a sha in the end
+		self._extension_data = stream.read(~0)
+		assert len(self._extension_data) > 19, "Index Footer was not at least a sha on content as it was only %i bytes in size" % len(self._extension_data)
+		
+		content_sha = self._extension_data[-20:]
+		
+		# truncate the sha in the end as we will dynamically create it anyway 
+		self._extension_data = self._extension_data[:-20]
+		
+	
+	@classmethod
+	def from_file(cls, repo, file_path):
+		"""
+		Returns
+			Index instance as recreated from the given stream.
+		
+		``repo``
+			Repository the index is related to
+		
+		``file_pa ``
+			File path pointing to git index file
+			
+		Note
+			Reading is based on the dulwich project.
+		"""
+		fp = open(file_path, "r")
+		
+		# try memory map for speed
+		stream = fp
+		try:
+			stream = mmap.mmap(fp.fileno(), 0, access=mmap.ACCESS_READ)
+		except Exception:
+			pass
+		# END memory mapping
+		
+		try:
+			return cls(repo, stream)
+		finally:
+			fp.close()
+		
+	
+	@classmethod
+	def to_file(cls, index, file_path):
+		"""
+		Write the index data to the given file path.
+		
+		``index``
+			Index you wish to write.
+			
+		``file_path``
+			Path at which to write the index data. Please note that missing directories
+			will lead to an exception to be thrown.
+			
+		Raise 
+			IOError if the file could not be written
+		"""
+		fp = open(file_path, "w")
+		try:
+			return index.write(fp)
+		finally:
+			fp.close()
+		# END exception handling
+		
+
+	@classmethod
+	def _write_cache_entry(cls, stream, entry):
+		"""
+		Write an IndexEntry to a stream
+		"""
+		beginoffset = stream.tell()
+		stream.write(entry[0])			# ctime
+		stream.write(entry[1])			# mtime
+		path = entry[10]
+		plen = len(path) & 0x0fff		# path length
+		assert plen == len(path), "Path %s too long to fit into index" % entry[10]
+		flags = plen | (entry[9] << 12)# stage and path length are 2 byte flags
+		stream.write(struct.pack(">LLLLLL20sH", entry[2], entry[3], entry[4], 
+									entry[5], entry[6], entry[7], binascii.unhexlify(entry[8]), flags))
+		stream.write(path)
+		real_size = ((stream.tell() - beginoffset + 8) & ~7)
+		stream.write("\0" * ((beginoffset + real_size) - stream.tell()))
+
+	def write(self, stream):
+		"""
+		Write the current state to the given stream
+		
+		``stream``
+			File-like object
+		
+		Returns
+			self
+		
+		Note
+			Index writing based on the dulwich implementation
+		"""
+		stream = SHA1Writer(stream)
+		
+		# header
+		stream.write("DIRC")
+		stream.write(struct.pack(">LL", self.version, len(self.entries)))
+		
+		# body
+		entries_sorted = self.entries.values()
+		entries_sorted.sort(key=lambda e: (e[10], e[9]))		# use path/stage as sort key
+		for entry in entries_sorted:
+			self._write_cache_entry(stream, entry)
+		# END for each entry
+		
+		# write previously cached extensions data
+		stream.write(self._extension_data)
+		
+		# write the sha over the content
+		stream.write_sha()
+		
+	
+	@classmethod
+	def from_tree(cls, repo, *treeish, **kwargs):
+		"""
+		Merge the given treeish revisions into a new index which is returned.
+		The original index will remain unaltered
+		
+		``repo``
+			The repository treeish are located in.
+			
+		``*treeish``
+			One, two or three Tree Objects or Commits. The result changes according to the 
+			amount of trees.
+			If 1 Tree is given, it will just be read into a new index
+			If 2 Trees are given, they will be merged into a new index using a 
+			 two way merge algorithm. Tree 1 is the 'current' tree, tree 2 is the 'other'
+			 one. It behaves like a fast-forward.
+			If 3 Trees are given, a 3-way merge will be performed with the first tree
+			 being the common ancestor of tree 2 and tree 3. Tree 2 is the 'current' tree, 
+			 tree 3 is the 'other' one
+			 
+		``**kwargs``
+			Additional arguments passed to git-read-tree
+			
+		Note:
+			In the three-way merge case, --aggressive will be specified to automatically
+			resolve more cases in a commonly correct manner. Specify trivial=True as kwarg
+			to override that.
+			
+			As the underlying git-read-tree command takes into account the current index, 
+			it will be temporarily moved out of the way to assure there are no unsuspected
+			interferences.
+		"""
+		if len(treeish) == 0 or len(treeish) > 3:
+			raise ValueError("Please specify between 1 and 3 treeish, got %i" % len(treeish))
+		
+		arg_list = list()
+		# ignore that working tree and index possibly are out of date
+		if len(treeish)>1:
+			# drop unmerged entries when reading our index and merging
+			arg_list.append("--reset")	
+			# handle non-trivial cases the way a real merge does
+			arg_list.append("--aggressive")	
+		# END merge handling
+		
+		# tmp file created in git home directory to be sure renaming 
+		# works - /tmp/ dirs could be on another device
+		tmp_index = tempfile.mktemp('','',repo.path)
+		arg_list.append("--index-output=%s" % tmp_index)
+		arg_list.extend(treeish)
+		
+		# move current index out of the way - otherwise the merge may fail
+		# as it considers existing entries. moving it essentially clears the index.
+		# Unfortunately there is no 'soft' way to do it.
+		# The _TemporaryFileSwap assure the original file get put back
+		index_handler = _TemporaryFileSwap(os.path.join(repo.path, 'index'))
+		try:
+			repo.git.read_tree(*arg_list, **kwargs)
+			index = cls.from_file(repo, tmp_index)
+		finally:
+			if os.path.exists(tmp_index):
+				os.remove(tmp_index)
+		# END index merge handling
+		
+		return index
+	
+	@classmethod
+	def _index_mode_to_tree_index_mode(cls, index_mode):
+		"""
+		Cleanup a index_mode value.
+		This will return a index_mode that can be stored in a tree object.
+		
+		``index_mode``
+			Index_mode to clean up.
+		"""
+		if stat.S_ISLNK(index_mode):
+			return stat.S_IFLNK
+		elif stat.S_ISDIR(index_mode):
+			return stat.S_IFDIR
+		elif stat.S_IFMT(index_mode) == cls.S_IFGITLINK:
+			return cls.S_IFGITLINK
+		ret = stat.S_IFREG | 0644
+		ret |= (index_mode & 0111)
+		return ret
+	
+	def iter_blobs(self, predicate = lambda t: True):
+		"""
+		Returns
+			Iterator yielding tuples of Blob objects and stages, tuple(stage, Blob)
+			
+		``predicate``
+			Function(t) returning True if tuple(stage, Blob) should be yielded by the 
+			iterator
+		"""
+		for entry in self.entries.itervalues():
+			mode = self._index_mode_to_tree_index_mode(entry.mode)
+			blob = Blob(self.repo, entry.sha, mode, entry.path)
+			blob.size = entry.size
+			output = (entry.stage, blob)
+			if predicate(output):
+				yield output
+		# END for each entry 
+	
+	def unmerged_blobs(self):
+		"""
+		Returns
+			Iterator yielding dict(path : list( tuple( stage, Blob, ...))), being 
+			a dictionary associating a path in the index with a list containing 
+			stage/blob pairs
+			
+		Note:
+			Blobs that have been removed in one side simply do not exist in the 
+			given stage. I.e. a file removed on the 'other' branch whose entries
+			are at stage 3 will not have a stage 3 entry.
+		"""
+		is_unmerged_blob = lambda t: t[0] != 0
+		path_map = dict()
+		for stage, blob in self.iter_blobs(is_unmerged_blob):
+			path_map.setdefault(blob.path, list()).append((stage, blob))
+		# END for each unmerged blob
+		
+		return path_map
+	
+	def resolve_blobs(self, iter_blobs):
+		"""
+		Resolve the blobs given in blob iterator. This will effectively remove the 
+		index entries of the respective path at all non-null stages and add the given 
+		blob as new stage null blob.
+		
+		For each path there may only be one blob, otherwise a ValueError will be raised
+		claiming the path is already at stage 0.
+		
+		Raise
+			ValueError if one of the blobs already existed at stage 0
+		
+		Returns:
+			self
+		"""
+		for blob in iter_blobs:
+			stage_null_key = (blob.path, 0)
+			if stage_null_key in self.entries:
+				raise ValueError( "Blob %r already at stage 0" % blob )
+			# END assert blob is not stage 0 already 
+			
+			# delete all possible stages
+			for stage in (1, 2, 3):
+				try:
+					del( self.entries[(blob.path, stage)] )
+				except KeyError:
+					pass 
+				# END ignore key errors
+			# END for each possible stage
+			
+			self.entries[stage_null_key] = IndexEntry.from_blob(blob) 
+		# END for each blob
+		
+		return self
+	
+	def write_tree(self):
+		"""
+		Writes the Index in self to a corresponding Tree file into the repository
+		object database and returns it as corresponding Tree object.
+		
+		Returns
+			Tree object representing this index
+		"""
+		index_path = os.path.join(self.repo.path, "index")
+		tmp_index_mover = _TemporaryFileSwap(index_path)
+		
+		self.to_file(self, index_path)
+		
+		try:
+			tree_sha = self.repo.git.write_tree()
+		finally:
+			# remove our index file so that the original index can move back into place
+			# On linux it will silently overwrite, on windows it won't
+			if os.path.isfile(index_path):
+				os.remove(index_path)
+			# END remove our own index file beforehand
+		# END write tree handling 
+		return Tree(self.repo, tree_sha, 0, '')
+		
+	
diff --git a/lib/git/objects/tree.py b/lib/git/objects/tree.py
index c35c075e..92aae881 100644
--- a/lib/git/objects/tree.py
+++ b/lib/git/objects/tree.py
@@ -152,22 +152,21 @@ class Tree(base.IndexObject, diff.Diffable):
 		return '<git.Tree "%s">' % self.id
 		
 	@classmethod
-	def _iter_recursive(cls, repo, tree, cur_depth, max_depth, predicate ):
+	def _iter_recursive(cls, repo, tree, cur_depth, max_depth, predicate, prune ):
 		
 		for obj in tree:
 			# adjust path to be complete
 			obj.path = os.path.join(tree.path, obj.path)
-			if not predicate(obj):
-				continue
-			yield obj
-			if obj.type == "tree" and ( max_depth < 0 or cur_depth+1 <= max_depth ):
-				for recursive_obj in cls._iter_recursive( repo, obj, cur_depth+1, max_depth, predicate ):
+			if predicate(obj):
+				yield obj
+			if obj.type == "tree" and ( max_depth < 0 or cur_depth+1 <= max_depth ) and not prune(obj):
+				for recursive_obj in cls._iter_recursive( repo, obj, cur_depth+1, max_depth, predicate, prune ):
 					yield recursive_obj
 				# END for each recursive object
 			# END if we may enter recursion
 		# END for each object
 		
-	def traverse(self, max_depth=-1, predicate = lambda i: True):
+	def traverse(self, max_depth=-1, predicate = lambda i: True, prune = lambda t: False):
 		"""
 		Returns
 		
@@ -183,8 +182,13 @@ class Tree(base.IndexObject, diff.Diffable):
 		``predicate``
 		
 			If predicate(item) returns True, item will be returned by iterator
+			
+		``prune``
+			
+			If prune(tree) returns True, the traversal will not continue into the 
+			given tree object.
 		"""
-		return self._iter_recursive( self.repo, self, 0, max_depth, predicate )
+		return self._iter_recursive( self.repo, self, 0, max_depth, predicate, prune )
 		
 	@property
 	def trees(self):
diff --git a/lib/git/utils.py b/lib/git/utils.py
index 2aa8d33e..cdc7c55b 100644
--- a/lib/git/utils.py
+++ b/lib/git/utils.py
@@ -6,6 +6,58 @@
 
 import os
 
+try:
+    import hashlib
+except ImportError:
+    import sha
+
+def make_sha(source=''):
+    """
+    A python2.4 workaround for the sha/hashlib module fiasco
+    
+	Note
+		From the dulwich project
+	"""
+    try:
+        return hashlib.sha1(source)
+    except NameError:
+        sha1 = sha.sha(source)
+        return sha1
+
+
+class SHA1Writer(object):
+    """
+    Wrapper around a file-like object that remembers the SHA1 of 
+    the data written to it. It will write a sha when the stream is closed
+    or if the asked for explicitly usign write_sha.
+    
+    Note:
+    	Based on the dulwich project
+    """
+    __slots__ = ("f", "sha1")
+    
+    def __init__(self, f):
+        self.f = f
+        self.sha1 = make_sha("")
+
+    def write(self, data):
+        self.sha1.update(data)
+        self.f.write(data)
+
+    def write_sha(self):
+        sha = self.sha1.digest()
+        self.f.write(sha)
+        return sha
+
+    def close(self):
+        sha = self.write_sha()
+        self.f.close()
+        return sha
+
+    def tell(self):
+        return self.f.tell()
+
+
 class LazyMixin(object):
 	"""
 	Base class providing an interface to lazily retrieve attribute values upon 
diff --git a/test/fixtures/index b/test/fixtures/index
new file mode 100644
index 00000000..40914bac
--- /dev/null
+++ b/test/fixtures/index
diff --git a/test/fixtures/index_merge b/test/fixtures/index_merge
new file mode 100644
index 00000000..2a743455
--- /dev/null
+++ b/test/fixtures/index_merge
diff --git a/test/git/test_index.py b/test/git/test_index.py
new file mode 100644
index 00000000..4c17f5e5
--- /dev/null
+++ b/test/git/test_index.py
@@ -0,0 +1,108 @@
+# test_index.py
+# Copyright (C) 2008, 2009 Michael Trier (mtrier@gmail.com) and contributors
+#
+# This module is part of GitPython and is released under
+# the BSD License: http://www.opensource.org/licenses/bsd-license.php
+
+from test.testlib import *
+from git import *
+import inspect
+import os
+import tempfile
+
+class TestTree(TestCase):
+	
+	@classmethod
+	def setUpAll(cls):
+		cls.repo = Repo(GIT_REPO)
+		
+	def test_base(self):
+		# read from file
+		index = Index.from_file(self.repo, fixture_path("index"))
+		assert index.entries
+		assert index.version > 0
+		
+		# test entry
+		last_val = None
+		entry = index.entries.itervalues().next()
+		for attr in ("path","ctime","mtime","dev","inode","mode","uid",
+								"gid","size","sha","stage"):
+			val = getattr(entry, attr)
+		# END for each method
+		
+		# test stage
+		index_merge = Index.from_file(self.repo, fixture_path("index_merge"))
+		assert len(index_merge.entries) == 106
+		assert len(list(e for e in index_merge.entries.itervalues() if e.stage != 0 ))
+		
+		# write the data - it must match the original
+		index_output = os.tmpfile()
+		index_merge.write(index_output)
+		
+		index_output.seek(0)
+		assert index_output.read() == fixture("index_merge")
+		
+		tmpfile = tempfile.mktemp()
+		Index.to_file(index_merge, tmpfile)
+		assert os.path.isfile(tmpfile)
+		os.remove(tmpfile)
+	
+	def _cmp_tree_index(self, tree, index):
+		# fail unless both objects contain the same paths and blobs
+		if isinstance(tree, str):
+			tree = self.repo.commit(tree).tree
+		
+		num_blobs = 0
+		for blob in tree.traverse(predicate = lambda e: e.type == "blob"):
+			assert (blob.path,0) in index.entries
+			num_blobs += 1
+		# END for each blob in tree
+		assert num_blobs == len(index.entries)
+	
+	def test_from_tree(self):
+		common_ancestor_sha = "5117c9c8a4d3af19a9958677e45cda9269de1541"
+		cur_sha = "4b43ca7ff72d5f535134241e7c797ddc9c7a3573"
+		other_sha = "39f85c4358b7346fee22169da9cad93901ea9eb9"
+		
+		# simple index from tree 
+		base_index = Index.from_tree(self.repo, common_ancestor_sha)
+		assert base_index.entries
+		self._cmp_tree_index(common_ancestor_sha, base_index)
+		
+		# merge two trees - its like a fast-forward
+		two_way_index = Index.from_tree(self.repo, common_ancestor_sha, cur_sha)
+		assert two_way_index.entries
+		self._cmp_tree_index(cur_sha, two_way_index)
+		
+		# merge three trees - here we have a merge conflict
+		three_way_index = Index.from_tree(self.repo, common_ancestor_sha, cur_sha, other_sha)
+		assert len(list(e for e in three_way_index.entries.values() if e.stage != 0))
+		
+		
+		# ITERATE BLOBS
+		merge_required = lambda t: t[0] != 0
+		merge_blobs = list(three_way_index.iter_blobs(merge_required))
+		assert merge_blobs
+		assert merge_blobs[0][0] in (1,2,3)
+		assert isinstance(merge_blobs[0][1], Blob)
+		
+		
+		# writing a tree should fail with an unmerged index
+		self.failUnlessRaises(GitCommandError, three_way_index.write_tree)
+		
+		# removed unmerged entries
+		unmerged_blob_map = three_way_index.unmerged_blobs()
+		assert unmerged_blob_map
+		
+		# pick the first blob at the first stage we find and use it as resolved version
+		three_way_index.resolve_blobs( l[0][1] for l in unmerged_blob_map.itervalues() )
+		tree = three_way_index.write_tree()
+		assert isinstance(tree, Tree)
+		num_blobs = 0
+		for blob in tree.traverse(predicate=lambda item: item.type == "blob"):
+			assert (blob.path,0) in three_way_index.entries
+			num_blobs += 1
+		# END for each blob
+		assert num_blobs == len(three_way_index.entries)
+	
+	
diff --git a/test/git/test_tree.py b/test/git/test_tree.py
index dafb6f3f..b359e2d2 100644
--- a/test/git/test_tree.py
+++ b/test/git/test_tree.py
@@ -35,6 +35,11 @@ class TestTree(TestCase):
 		trees = list(root.traverse(predicate = trees_only))
 		assert len(trees) == len(list( i for i in root.traverse() if trees_only(i) ))
 		
+		# test prune
+		lib_folder = lambda t: t.path == "lib"
+		pruned_trees = list(root.traverse(predicate = trees_only,prune = lib_folder))
+		assert len(pruned_trees) < len(trees)
+		
 		# trees and blobs
 		assert len(set(trees)|set(root.trees)) == len(trees)
 		assert len(set(b for b in root if isinstance(b, Blob)) | set(root.blobs)) == len( root.blobs )