Merge branch 'iteration_and_retrieval' into improvements

* iteration_and_retrieval:
  test_performance: module containing benchmarks to get an idea of the achieved throughput
  Removed plenty of mocked tree tests as they cannot work anymore with persistent commands that require stdin AND binary data - not even an adapter would help here. These tests will have to be replaced.
  tree: now reads tress directly by parsing the binary data, allowing it to safe possibly hundreds of command calls
  Refs are now truly dynamic - this costs a little bit of (persistent command) work, but assures refs behave as expected
  persistent command signature changed to also return the hexsha from a possible input ref - the objects pointed to by refs are now baked on demand - perhaps it should change to always be re-retrieved using a property as it is relatively fast - this way refs can always be cached
  test_blob: removed many redundant tests that would fail now as the mock cannot handle the complexity of the command backend
  Implemented git command facility to keep persistent commands for fast object information retrieval
  test: Added time-consuming test which could also be a benchmark in fact - currently it cause hundreds of command invocations which is slow
  cmd: added option to return the process directly, allowing to read the output directly from the output stream
  added Iterable interface to Ref type
  renamed find_all to list_all, changed commit to use iterable interface in preparation for command changes
  Added base for all iteratable objects
  unified name of utils module, recently it was named util and utils in different packages
  tree: renamed content_from_string to _from_string to make it private. Removed tests that were testing that method
  tree: now behaves like a list with string indexing functionality - using a dict as cache is a problem as the tree is ordered, added blobs, trees and traverse method
  test_base: Improved basic object creation as well as set hash tests
  repo.active_branch now returns a Head object, not a string
  IndexObjects are now checking their slots to raise a proper error message in case someone tries to access an unset path or mode - this information cannot be retrieved afterwards as IndexObject information is kept in the object that pointed at them. To find this information, one would have to search all objects which is not feasible
  refs now take repo as first argument and derive from LazyMixin to allow them to dynamically retrieve their objects

1 files changed, 196 insertions, 56 deletions

diff --git a/lib/git/objects/tree.py b/lib/git/objects/tree.py
index 273384a3..abfa9622 100644
--- a/lib/git/objects/tree.py
+++ b/lib/git/objects/tree.py
@@ -7,53 +7,125 @@
 import os
 import blob
 import base
+import binascii
+
+def sha_to_hex(sha):
+    """Takes a string and returns the hex of the sha within"""
+    hexsha = binascii.hexlify(sha)
+    assert len(hexsha) == 40, "Incorrect length of sha1 string: %d" % hexsha
+    return hexsha
 
 class Tree(base.IndexObject):
+	"""
+	Tress represent a ordered list of Blobs and other Trees. Hence it can be 
+	accessed like a list.
+	
+	Tree's will cache their contents after first retrieval to improve efficiency.
+	
+	``Tree as a list``::
+		
+		Access a specific blob using the  
+		tree['filename'] notation.
+		
+		You may as well access by index
+		blob = tree[0]
+		
+		
+	"""
 	
 	type = "tree"
-	__slots__ = "_contents"
+	__slots__ = "_cache"
+	
+	# using ascii codes for comparison 
+	ascii_commit_id = (0x31 << 4) + 0x36		
+	ascii_blob_id = (0x31 << 4) + 0x30
+	ascii_tree_id = (0x34 << 4) + 0x30
 	
-	def __init__(self, repo, id, mode=None, path=None):
+	
+	def __init__(self, repo, id, mode=0, path=None):
 		super(Tree, self).__init__(repo, id, mode, path)
 
 	def _set_cache_(self, attr):
-		if attr == "_contents":
-			# Read the tree contents.
-			self._contents = {}
-			for line in self.repo.git.ls_tree(self.id).splitlines():
-				obj = self.content__from_string(self.repo, line)
-				if obj is not None:
-					self._contents[obj.path] = obj
+		if attr == "_cache":
+			# Set the data when we need it
+			self._cache = self._get_tree_cache()
 		else:
 			super(Tree, self)._set_cache_(attr)
 
-	@staticmethod
-	def content__from_string(repo, text):
+	def _get_tree_cache(self):
 		"""
-		Parse a content item and create the appropriate object
-
-		``repo``
-			is the Repo
-
-		 ``text``
-			is the single line containing the items data in `git ls-tree` format
-
+		Return
+			list(object_instance, ...)
+		
+		``treeish``
+			sha or ref identifying a tree  
+		"""
+		out = list()
+		for obj in self._iter_from_data():
+			if obj is not None:
+				out.append(obj)
+			# END if object was handled
+		# END for each line from ls-tree
+		return out
+		
+		
+	def _iter_from_data(self):
+		"""
+		Reads the binary non-pretty printed representation of a tree and converts
+		it into Blob, Tree or Commit objects.
+		
+		Note: This method was inspired by the parse_tree method in dulwich.
+		
 		Returns
-			``git.Blob`` or ``git.Tree``
+			list(IndexObject, ...)
 		"""
-		try:
-			mode, typ, id, path = text.expandtabs(1).split(" ", 3)
-		except:
-			return None
+		ord_zero = ord('0')
+		data = self.data
+		len_data = len(data)
+		i = 0
+		while i < len_data:
+			mode = 0
+			mode_boundary = i + 6
+			
+			# keep it ascii - we compare against the respective values
+			type_id = (ord(data[i])<<4) + ord(data[i+1])
+			i += 2
+			
+			while data[i] != ' ':
+				# move existing mode integer up one level being 3 bits
+				# and add the actual ordinal value of the character
+				mode = (mode << 3) + (ord(data[i]) - ord_zero)
+				i += 1
+			# END while reading mode
+			
+			# byte is space now, skip it
+			i += 1
+			
+			# parse name, it is NULL separated
+			
+			ns = i
+			while data[i] != '\0':
+				i += 1
+			# END while not reached NULL
+			name = data[ns:i]
+			
+			# byte is NULL, get next 20
+			i += 1
+			sha = data[i:i+20]
+			i = i + 20
+			
+			hexsha = sha_to_hex(sha)
+			if type_id == self.ascii_blob_id:
+				yield blob.Blob(self.repo, hexsha, mode, name)
+			elif type_id == self.ascii_tree_id:
+				yield Tree(self.repo, hexsha, mode, name)
+			elif type_id == self.ascii_commit_id:
+				# todo 
+				yield None
+			else:
+				raise TypeError( "Unknown type found in tree data: %i" % type_id )
+		# END for each byte in data stream
 
-		if typ == "tree":
-			return Tree(repo, id, mode, path)
-		elif typ == "blob":
-			return blob.Blob(repo, id, mode, path)
-		elif typ == "commit":
-			return None 
-		else:
-		  raise(TypeError, "Invalid type: %s" % typ)
 
 	def __div__(self, file):
 		"""
@@ -67,36 +139,104 @@ class Tree(base.IndexObject):
 			<git.Blob "8b1e02c0fb554eed2ce2ef737a68bb369d7527df">
 
 		Returns
-			``git.Blob`` or ``git.Tree`` or ``None`` if not found
+			``git.Blob`` or ``git.Tree``
+		
+		Raise 
+			KeyError if given file or tree does not exist in tree
 		"""
-		return self.get(file)
+		return self[file]
 
 
 	def __repr__(self):
 		return '<git.Tree "%s">' % self.id
+		
+	@classmethod
+	def _iter_recursive(cls, repo, tree, cur_depth, max_depth, predicate ):
+		
+		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 ):
+					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):
+		"""
+		Returns
+			Iterator to traverse the tree recursively up to the given level.
+			The iterator returns Blob and Tree objects
+		
+		``max_depth``
+		
+			if -1, the whole tree will be traversed
+			if 0, only the first level will be traversed which is the same as 
+			the default non-recursive iterator
+			
+		``predicate``
+		
+			If predicate(item) returns True, item will be returned by iterator
+		"""
+		return self._iter_recursive( self.repo, self, 0, max_depth, predicate )
+		
+	@property
+	def trees(self):
+		"""
+		Returns
+			list(Tree, ...) list of trees directly below this tree
+		"""
+		return [ i for i in self if i.type == "tree" ]
+		
+	@property
+	def blobs(self):
+		"""
+		Returns
+			list(Blob, ...) list of blobs directly below this tree
+		"""
+		return [ i for i in self if i.type == "blob" ]
 
-	# Implement the basics of the dict protocol:
-	# directories/trees can be seen as object dicts.
-	def __getitem__(self, key):
-		return self._contents[key]
 
+	# List protocol
+	def __getslice__(self,i,j):
+		return self._cache[i:j]
+		
 	def __iter__(self):
-		return iter(self._contents)
-
+		return iter(self._cache)
+		
 	def __len__(self):
-		return len(self._contents)
-
-	def __contains__(self, key):
-		return key in self._contents
-
-	def get(self, key):
-		return self._contents.get(key)
-
-	def items(self):
-		return self._contents.items()
-
-	def keys(self):
-		return self._contents.keys()
-
-	def values(self):
-		return self._contents.values()
+		return len(self._cache)
+		
+	def __getitem__(self,item):
+		if isinstance(item, int):
+			return self._cache[item]
+		
+		if isinstance(item, basestring):
+			# compatability
+			for obj in self._cache:
+				if obj.path == item:
+					return obj
+			# END for each obj
+			raise KeyError( "Blob or Tree named %s not found" % item )
+		# END index is basestring 
+		
+		raise TypeError( "Invalid index type: %r" % item )
+		
+		
+	def __contains__(self,item):
+		if isinstance(item, base.IndexObject):
+			return item in self._cache
+		
+		# compatability
+		for obj in self._cache:
+			if item == obj.path:
+				return True
+		# END for each item
+		return False
+	
+	def __reversed__(self):
+		return reversed(self._cache)