[Boost-commit] svn:boost r79773 - trunk/tools/build/v2/test

Subject: [Boost-commit] svn:boost r79773 - trunk/tools/build/v2/test
From: jurko.gospodnetic_at_[hidden]
Date: 2012-07-27 18:40:49

Author: jurko
Date: 2012-07-27 18:40:48 EDT (Fri, 27 Jul 2012)
New Revision: 79773
URL: http://svn.boost.org/trac/boost/changeset/79773

Log:
Refactored internal Boost Build testing system's file system content modeling tree data structure. Used to be based on some old svn_tree.py Subversion project source code. Now unused parts removed and the svn_tree.py module merged into tree.py. Trees_difference class renamed to TreeDifference and corresponding factory function to tree_difference. Now correctly recognizes and reports files being converted to folders and vice versa.
Removed:
   trunk/tools/build/v2/test/svn_tree.py
Text files modified: 
   trunk/tools/build/v2/test/BoostBuild.py |     2                                         
   trunk/tools/build/v2/test/tree.py       |   268 ++++++++++++++++++++++++++++----------- 
   2 files changed, 195 insertions(+), 75 deletions(-)

Modified: trunk/tools/build/v2/test/BoostBuild.py
==============================================================================
--- trunk/tools/build/v2/test/BoostBuild.py	(original)
+++ trunk/tools/build/v2/test/BoostBuild.py	2012-07-27 18:40:48 EDT (Fri, 27 Jul 2012)
@@ -476,7 +476,7 @@
             self.last_build_timestamp = self.__get_current_file_timestamp()
 
         self.tree = tree.build_tree(self.workdir)
-        self.difference = tree.trees_difference(self.previous_tree, self.tree)
+        self.difference = tree.tree_difference(self.previous_tree, self.tree)
         if self.difference.empty():
             # If nothing has been changed by this build and sufficient time has
             # passed since the last build that actually changed something,

Deleted: trunk/tools/build/v2/test/svn_tree.py
==============================================================================
--- trunk/tools/build/v2/test/svn_tree.py	2012-07-27 18:40:48 EDT (Fri, 27 Jul 2012)
+++ (empty file)
@@ -1,668 +0,0 @@
-#!/usr/bin/env python
-#
-#  tree.py: tools for comparing directory trees
-#
-#  Subversion is a tool for revision control.
-#  See http://subversion.tigris.org for more information.
-#
-# ====================================================================
-# Copyright (c) 2001 Sam Tobin-Hochstadt.  All rights reserved.
-#
-# This software is licensed as described in the file COPYING, which
-# you should have received as part of this distribution.  The terms
-# are also available at http://subversion.tigris.org/license-1.html.
-# If newer versions of this license are posted there, you may use a
-# newer version instead, at your option.
-#
-######################################################################
-
-# This file was modified by Vladimir Prus to store modification times in tree
-# nodes.
-
-import re
-import string
-import os.path
-import os
-import stat
-
-
-#========================================================================
-
-# ===>  Overview of our Datastructures  <===
-
-# The general idea here is that many, many things can be represented by
-# a tree structure:
-
-#   - a working copy's structure and contents
-#   - the output of 'svn status'
-#   - the output of 'svn checkout/update'
-#   - the output of 'svn commit'
-
-# The idea is that a test function creates a "expected" tree of some
-# kind, and is then able to compare it to an "actual" tree that comes
-# from running the Subversion client.  This is what makes a test
-# automated; if an actual and expected tree match exactly, then the test
-# has passed.  (See compare_trees() below.)
-
-# The SVNTreeNode class is the fundamental data type used to build tree
-# structures.  The class contains a method for "dropping" a new node
-# into an ever-growing tree structure. (See also create_from_path()).
-
-# We have four parsers in this file for the four use cases listed above:
-# each parser examines some kind of input and returns a tree of
-# SVNTreeNode objects.  (See build_tree_from_checkout(),
-# build_tree_from_commit(), build_tree_from_status(), and
-# build_tree_from_wc()).  These trees are the "actual" trees that result
-# from running the Subversion client.
-
-# Also necessary, of course, is a convenient way for a test to create an
-# "expected" tree.  The test *could* manually construct and link a bunch
-# of SVNTreeNodes, certainly.  But instead, all the tests are using the
-# build_generic_tree() routine instead.
-
-# build_generic_tree() takes a specially-formatted list of lists as
-# input, and returns a tree of SVNTreeNodes.  The list of lists has this
-# structure:
-
-#   [ ['/full/path/to/item', 'text contents', {prop-hash}, {att-hash}],
-#     [...],
-#     [...],
-#     ...   ]
-
-# You can see that each item in the list essentially defines an
-# SVNTreeNode.  build_generic_tree() instantiates a SVNTreeNode for each
-# item, and then drops it into a tree by parsing each item's full path.
-
-# So a typical test routine spends most of its time preparing lists of
-# this format and sending them to build_generic_tree(), rather than
-# building the "expected" trees directly.
-
-#   ### Note: in the future, we'd like to remove this extra layer of
-#   ### abstraction.  We'd like the SVNTreeNode class to be more
-#   ### directly programmer-friendly, providing a number of accessor
-#   ### routines, so that tests can construct trees directly.
-
-# The first three fields of each list-item are self-explanatory.  It's
-# the fourth field, the "attribute" hash, that needs some explanation.
-# The att-hash is used to place extra information about the node itself,
-# depending on the parsing context:
-
-#   - in the 'svn co/up' use-case, each line of output starts with two
-#     characters from the set of (A, D, G, U, C, _).  This status code
-#     is stored in a attribute named 'status'.
-
-#   - in the 'svn ci/im' use-case, each line of output starts with one
-#      of the words (Adding, Deleting, Sending).  This verb is stored in
-#      an attribute named 'verb'.
-
-#   - in the 'svn status' use-case (which is always run with the -v
-#     (--verbose) flag), each line of output contains a working revision
-#     number and a two-letter status code similar to the 'svn co/up'
-#     case.  The repository revision is also printed.  All of this
-#     information is stored in attributes named 'wc_rev', 'status', and
-#     'repos_rev', respectively.
-
-#   - in the working-copy use-case, the att-hash is ignored.
-
-
-# Finally, one last explanation: the file 'actions.py' contain a number
-# of helper routines named 'run_and_verify_FOO'.  These routines take
-# one or more "expected" trees as input, then run some svn subcommand,
-# then push the output through an appropriate parser to derive an
-# "actual" tree.  Then it runs compare_trees() and returns the result.
-# This is why most tests typically end with a call to
-# run_and_verify_FOO().
-
-
-
-
-# A node in a tree.
-#
-# If CHILDREN is None, then the node is a file.  Otherwise, CHILDREN
-# is a list of the nodes making up that directory's children.
-#
-# NAME is simply the name of the file or directory.  CONTENTS is a
-# string that contains the file's contents (if a file), PROPS are
-# properties attached to files or dirs, and ATTS is a dictionary of
-# other metadata attached to the node.
-
-class SVNTreeNode:
-
-  def __init__(self, name, children=None, contents=None, props={}, atts={}):
-    self.name = name
-    self.mtime = 0
-    self.children = children
-    self.contents = contents
-    self.props = props
-    self.atts = atts
-    self.path = name
-
-# TODO: Check to make sure contents and children are mutually exclusive
-
-  def add_child(self, newchild):
-    if self.children is None:  # if you're a file,
-      self.children = []     # become an empty dir.
-    child_already_exists = 0
-    for a in self.children:
-      if a.name == newchild.name:
-        child_already_exists = 1
-        break
-    if child_already_exists == 0:
-      self.children.append(newchild)
-      newchild.path = os.path.join (self.path, newchild.name)
-
-    # If you already have the node,
-    else:
-      if newchild.children is None:
-        # this is the 'end' of the chain, so copy any content here.
-        a.contents = newchild.contents
-        a.props = newchild.props
-        a.atts = newchild.atts
-        a.path = os.path.join (self.path, newchild.name)
-      else:
-        # try to add dangling children to your matching node
-        for i in newchild.children:
-          a.add_child(i)
-
-
-  def pprint(self):
-    print " * Node name:  ", self.name
-    print "    Path:      ", self.path
-    print "    Contents:  ", self.contents
-    print "    Properties:", self.props
-    print "    Attributes:", self.atts
-    ### FIXME: I'd like to be able to tell the difference between
-    ### self.children is None (file) and self.children == [] (empty
-    ### diretory), but it seems that most places that construct
-    ### SVNTreeNode objects don't even try to do that.  --xbc
-    if self.children is not None:
-      print "    Children:  ", len(self.children)
-    else:
-      print "    Children: is a file."
-
-# reserved name of the root of the tree
-
-root_node_name = "__SVN_ROOT_NODE"
-
-# Exception raised if you screw up in this module.
-
-class SVNTreeError(Exception): pass
-
-# Exception raised if two trees are unequal
-
-class SVNTreeUnequal(Exception): pass
-
-# Exception raised if one node is file and other is dir
-
-class SVNTypeMismatch(Exception): pass
-
-# Exception raised if get_child is passed a file.
-
-class SVNTreeIsNotDirectory(Exception): pass
-
-
-# Some attributes 'stack' on each other if the same node is added
-# twice to a tree.  Place all such special cases in here.
-def attribute_merge(orighash, newhash):
-  "Merge the attributes in NEWHASH into ORIGHASH."
-
-  if orighash.has_key('verb') and newhash.has_key('verb'):
-    # Special case: if a commit reports a node as "deleted", then
-    # "added", it's a replacment.
-    if orighash['verb'] == "Deleting":
-      if newhash['verb'] == "Adding":
-        orighash['verb'] = "Replacing"
-
-  # Add future stackable attributes here...
-
-  return orighash
-
-
-# helper func
-def add_elements_as_path(top_node, element_list):
-  """Add the elements in ELEMENT_LIST as if they were a single path
-  below TOP_NODE."""
-
-  # The idea of this function is to take a list like so:
-  # ['A', 'B', 'C'] and a top node, say 'Z', and generate a tree
-  # like this:
-  #
-  #             Z -> A -> B -> C
-  #
-  # where 1 -> 2 means 2 is a child of 1.
-  #
-
-  prev_node = top_node
-  for i in element_list:
-    new_node = SVNTreeNode(i, None)
-    prev_node.add_child(new_node)
-    prev_node = new_node
-
-
-# Sorting function -- sort 2 nodes by their names.
-def node_is_greater(a, b):
-  "Sort the names of two nodes."
-  # Interal use only
-  if a.name == b.name:
-    return 0
-  if a.name > b.name:
-    return 1
-  else:
-    return -1
-
-
-# Helper for compare_trees
-def compare_file_nodes(a, b):
-  """Compare two nodes' names, contents, and properties, ignoring
-  children.  Return 0 if the same, 1 otherwise."""
-  if a.name != b.name:
-    return 1
-  if a.contents != b.contents:
-    return 1
-  if a.props != b.props:
-    return 1
-  if a.atts != b.atts:
-    return 1
-
-
-# Internal utility used by most build_tree_from_foo() routines.
-#
-# (Take the output and .add_child() it to a root node.)
-
-def create_from_path(path, contents=None, props={}, atts={}):
-  """Create and return a linked list of treenodes, given a PATH
-  representing a single entry into that tree.  CONTENTS and PROPS are
-  optional arguments that will be deposited in the tail node."""
-
-  # get a list of all the names in the path
-  # each of these will be a child of the former
-  elements = path.split("/")
-  if len(elements) == 0:
-    raise SVNTreeError
-
-  root_node = SVNTreeNode(elements[0], None)
-
-  add_elements_as_path(root_node, elements[1:])
-
-  # deposit contents in the very last node.
-  node = root_node
-  while 1:
-    if node.children is None:
-      node.contents = contents
-      node.props = props
-      node.atts = atts
-      break
-    node = node.children[0]
-
-  return root_node
-
-
-# helper for handle_dir(), which is a helper for build_tree_from_wc()
-def get_props(path):
-  "Return a hash of props for PATH, using the svn client."
-
-  # It's not kosher to look inside SVN/ and try to read the internal
-  # property storage format.  Instead, we use 'svn proplist'.  After
-  # all, this is the only way the user can retrieve them, so we're
-  # respecting the black-box paradigm.
-
-  props = {}
-  output, errput = main.run_svn(1, "proplist", path, "--verbose")
-
-  for line in output:
-    name, value = line.split(' : ')
-    name = string.strip(name)
-    value = string.strip(value)
-    props[name] = value
-
-  return props
-
-
-# helper for handle_dir(), which helps build_tree_from_wc()
-def get_text(path):
-  "Return a string with the textual contents of a file at PATH."
-
-  # sanity check
-  if not os.path.isfile(path):
-    return None
-
-  fp = open(path, 'r')
-  contents = fp.read()
-  fp.close()
-  return contents
-
-
-# main recursive helper for build_tree_from_wc()
-def handle_dir(path, current_parent, load_props, ignore_svn):
-
-  # get a list of all the files
-  all_files = os.listdir(path)
-  files = []
-  dirs = []
-
-  # put dirs and files in their own lists, and remove SVN dirs
-  for f in all_files:
-    f = os.path.join(path, f)
-    if (os.path.isdir(f) and os.path.basename(f) != 'SVN'):
-      dirs.append(f)
-    elif os.path.isfile(f):
-      files.append(f)
-
-  # add each file as a child of CURRENT_PARENT
-  for f in files:
-    fcontents = get_text(f)
-    if load_props:
-      fprops = get_props(f)
-    else:
-      fprops = {}
-    c = SVNTreeNode(os.path.basename(f), None,
-                                         fcontents, fprops)
-    c.mtime = os.stat(f).st_mtime
-    current_parent.add_child(c)
-
-  # for each subdir, create a node, walk its tree, add it as a child
-  for d in dirs:
-    if load_props:
-      dprops = get_props(d)
-    else:
-      dprops = {}
-    new_dir_node = SVNTreeNode(os.path.basename(d), [], None, dprops)
-    handle_dir(d, new_dir_node, load_props, ignore_svn)
-    new_dir_node.mtime = os.stat(f).st_mtime
-    current_parent.add_child(new_dir_node)
-
-def get_child(node, name):
-  """If SVNTreeNode NODE contains a child named NAME, return child;
-  else, return None. If SVNTreeNode is not a directory, raise a
-  SVNTreeIsNotDirectory exception"""
-  if node.children == None:
-    raise SVNTreeIsNotDirectory
-  for n in node.children:
-    if (name == n.name):
-      return n
-  return None
-
-
-# Helper for compare_trees
-def default_singleton_handler(a, baton):
-  "Printing SVNTreeNode A's name, then raise SVNTreeUnequal."
-  print "Got singleton", a.name
-  a.pprint()
-  raise SVNTreeUnequal
-
-
-###########################################################################
-###########################################################################
-# EXPORTED ROUTINES ARE BELOW
-
-
-# Main tree comparison routine!
-
-def compare_trees(a, b,
-                  singleton_handler_a = None,
-                  a_baton = None,
-                  singleton_handler_b = None,
-                  b_baton = None):
-  """Compare SVNTreeNodes A and B, expressing differences using FUNC_A
-  and FUNC_B.  FUNC_A and FUNC_B are functions of two arguments (a
-  SVNTreeNode and a context baton), and may raise exception
-  SVNTreeUnequal.  Their return value is ignored.
-
-  If A and B are both files, then return 0 if their contents,
-  properties, and names are all the same; else raise a SVNTreeUnequal.
-  If A is a file and B is a directory, raise a SVNTypeMismatch; same
-  vice-versa.  If both are directories, then for each entry that
-  exists in both, call compare_trees on the two entries; otherwise, if
-  the entry exists only in A, invoke FUNC_A on it, and likewise for
-  B with FUNC_B."""
-
-  def display_nodes(a, b):
-    'Display two nodes, expected and actual.'
-    print "============================================================="
-    print "Expected", b.name, "and actual", a.name, "are different!"
-    print "============================================================="
-    print "EXPECTED NODE TO BE:"
-    print "============================================================="
-    b.pprint()
-    print "============================================================="
-    print "ACTUAL NODE FOUND:"
-    print "============================================================="
-    a.pprint()
-
-  # Setup singleton handlers
-  if (singleton_handler_a is None):
-    singleton_handler_a = default_singleton_handler
-  if (singleton_handler_b is None):
-    singleton_handler_b = default_singleton_handler
-
-  try:
-    # A and B are both files.
-    if ((a.children is None) and (b.children is None)):
-      if compare_file_nodes(a, b):
-        display_nodes(a, b)
-        raise main.SVNTreeUnequal
-    # One is a file, one is a directory.
-    elif (((a.children is None) and (b.children is not None))
-          or ((a.children is not None) and (b.children is None))):
-      display_nodes(a, b)
-      raise main.SVNTypeMismatch
-    # They're both directories.
-    else:
-      # First, compare the directories' two hashes.
-      if (a.props != b.props) or (a.atts != b.atts):
-        display_nodes(a, b)
-        raise main.SVNTreeUnequal
-
-      accounted_for = []
-      # For each child of A, check and see if it's in B.  If so, run
-      # compare_trees on the two children and add b's child to
-      # accounted_for.  If not, run FUNC_A on the child.  Next, for each
-      # child of B, check and see if it's in accounted_for.  If it is,
-      # do nothing. If not, run FUNC_B on it.
-      for a_child in a.children:
-        b_child = get_child(b, a_child.name)
-        if b_child:
-          accounted_for.append(b_child)
-          compare_trees(a_child, b_child,
-                        singleton_handler_a, a_baton,
-                        singleton_handler_b, b_baton)
-        else:
-          singleton_handler_a(a_child, a_baton)
-      for b_child in b.children:
-        if (b_child not in accounted_for):
-          singleton_handler_b(b_child, b_baton)
-      return 0
-  except SVNTypeMismatch:
-    print 'Unequal Types: one Node is a file, the other is a directory'
-    raise SVNTreeUnequal
-  except SVNTreeIsNotDirectory:
-    print "Error: Foolish call to get_child."
-    sys.exit(1)
-  except IndexError:
-    print "Error: unequal number of children"
-    raise SVNTreeUnequal
-  except SVNTreeUnequal:
-    if a.name == root_node_name:
-      return 1
-    else:
-      print "Unequal at node %s" % a.name
-      raise SVNTreeUnequal
-  return 0
-
-
-
-
-# Visually show a tree's structure
-
-def dump_tree(n,indent=""):
-  "Print out a nice representation of the tree's structure."
-
-  # Code partially stolen from Dave Beazley.
-  if n.children is None:
-    tmp_children = []
-  else:
-    tmp_children = n.children
-
-  if n.name == root_node_name:
-    print "%s%s" % (indent, "ROOT")
-  else:
-    print "%s%s" % (indent, n.name)
-
-  indent = indent.replace("-", " ")
-  indent = indent.replace("+", " ")
-  for i in range(len(tmp_children)):
-    c = tmp_children[i]
-    if i == len(tmp_children) - 1:
-      dump_tree(c,indent + "  +-- ")
-    else:
-      dump_tree(c,indent + "  |-- ")
-
-
-###################################################################
-###################################################################
-# PARSERS that return trees made of SVNTreeNodes....
-
-
-###################################################################
-# Build an "expected" static tree from a list of lists
-
-
-# Create a list of lists, of the form:
-#
-#  [ [path, contents, props, atts], ... ]
-#
-#  and run it through this parser.  PATH is a string, a path to the
-#  object.  CONTENTS is either a string or None, and PROPS and ATTS are
-#  populated dictionaries or {}.  Each CONTENTS/PROPS/ATTS will be
-#  attached to the basename-node of the associated PATH.
-
-def build_generic_tree(nodelist):
-  "Given a list of lists of a specific format, return a tree."
-
-  root = SVNTreeNode(root_node_name)
-
-  for list in nodelist:
-    new_branch = create_from_path(list[0], list[1], list[2], list[3])
-    root.add_child(new_branch)
-
-  return root
-
-
-####################################################################
-# Build trees from different kinds of subcommand output.
-
-
-# Parse co/up output into a tree.
-#
-#   Tree nodes will contain no contents, and only one 'status' att.
-
-def build_tree_from_checkout(lines):
-  "Return a tree derived by parsing the output LINES from 'co' or 'up'."
-
-  root = SVNTreeNode(root_node_name)
-  rm = re.compile ('^([MAGCUD_ ][MAGCUD_ ]) (.+)')
-
-  for line in lines:
-    match = rm.search(line)
-    if match and match.groups():
-      new_branch = create_from_path(match.group(2), None, {},
-                                    {'status' : match.group(1)})
-      root.add_child(new_branch)
-
-  return root
-
-
-# Parse ci/im output into a tree.
-#
-#   Tree nodes will contain no contents, and only one 'verb' att.
-
-def build_tree_from_commit(lines):
-  "Return a tree derived by parsing the output LINES from 'ci' or 'im'."
-
-  # Lines typically have a verb followed by whitespace then a path.
-  root = SVNTreeNode(root_node_name)
-  rm1 = re.compile ('^(\w+)\s+(.+)')
-  rm2 = re.compile ('^Transmitting')
-
-  for line in lines:
-    match = rm2.search(line)
-    if not match:
-      match = rm1.search(line)
-      if match and match.groups():
-        new_branch = create_from_path(match.group(2), None, {},
-                                      {'verb' : match.group(1)})
-        root.add_child(new_branch)
-
-  return root
-
-
-# Parse status output into a tree.
-#
-#   Tree nodes will contain no contents, and these atts:
-#
-#          'status', 'wc_rev', 'repos_rev'
-#             ... and possibly 'locked', 'copied', IFF columns non-empty.
-#
-
-def build_tree_from_status(lines):
-  "Return a tree derived by parsing the output LINES from 'st'."
-
-  root = SVNTreeNode(root_node_name)
-  rm = re.compile ('^.+\:.+(\d+)')
-  lastline = string.strip(lines.pop())
-  match = rm.search(lastline)
-  if match and match.groups():
-    repos_rev = match.group(1)
-  else:
-    repos_rev = '?'
-
-  # Try http://www.wordsmith.org/anagram/anagram.cgi?anagram=ACDRMGU
-  rm = re.compile ('^([MACDRUG_ ][MACDRUG_ ])(.)(.)   .   [^0-9-]+(\d+|-)(.{23})(.+)')
-  for line in lines:
-    match = rm.search(line)
-    if match and match.groups():
-      if match.group(5) != '-': # ignore items that only exist on repos
-        atthash = {'status' : match.group(1),
-                   'wc_rev' : match.group(4),
-                   'repos_rev' : repos_rev}
-        if match.group(2) != ' ':
-          atthash['locked'] = match.group(2)
-        if match.group(3) != ' ':
-          atthash['copied'] = match.group(3)
-        new_branch = create_from_path(match.group(6), None, {}, atthash)
-
-      root.add_child(new_branch)
-
-  return root
-
-
-####################################################################
-# Build trees by looking at the working copy
-
-
-#   The reason the 'load_props' flag is off by default is because it
-#   creates a drastic slowdown -- we spawn a new 'svn proplist'
-#   process for every file and dir in the working copy!
-
-
-def build_tree_from_wc(wc_path, load_props=0, ignore_svn=1):
-    """Takes WC_PATH as the path to a working copy.  Walks the tree below
-    that path, and creates the tree based on the actual found
-    files.  If IGNORE_SVN is true, then exclude SVN dirs from the tree.
-    If LOAD_PROPS is true, the props will be added to the tree."""
-
-    root = SVNTreeNode(root_node_name, None)
-
-    # if necessary, store the root dir's props in the root node.
-    if load_props:
-      root.props = get_props(wc_path)
-
-    # Walk the tree recursively
-    handle_dir(os.path.normpath(wc_path), root, load_props, ignore_svn)
-
-    return root
-
-### End of file.
-# local variables:
-# eval: (load-file "../../../../../tools/dev/svn-dev.el")
-# end:

Modified: trunk/tools/build/v2/test/tree.py
==============================================================================
--- trunk/tools/build/v2/test/tree.py	(original)
+++ trunk/tools/build/v2/test/tree.py	2012-07-27 18:40:48 EDT (Fri, 27 Jul 2012)
@@ -1,15 +1,90 @@
 # Copyright 2003 Dave Abrahams
 # Copyright 2001, 2002 Vladimir Prus
+# Copyright 2012 Jurko Gospodnetic
 # Distributed under the Boost Software License, Version 1.0.
 # (See accompanying file LICENSE_1_0.txt or copy at
 # http://www.boost.org/LICENSE_1_0.txt)
 
-# This file is based in part on the content of svn_tree.py.
+###############################################################################
+#
+# Based in part on an old Subversion tree.py source file (tools for comparing
+# directory trees). See http://subversion.tigris.org for more information.
+#
+# Copyright (c) 2001 Sam Tobin-Hochstadt.  All rights reserved.
+#
+# This software is licensed as described in the file COPYING, which you should
+# have received as part of this distribution. The terms are also available at
+# http://subversion.tigris.org/license-1.html. If newer versions of this
+# license are posted there, you may use a newer version instead, at your
+# option.
+#
+###############################################################################
+
+import os
+import os.path
+import stat
+import sys
+
+
+class TreeNode:
+    """
+      Fundamental data type used to build file system tree structures.
+
+      If CHILDREN is None, then the node represents a file. Otherwise, CHILDREN
+    is a list of the nodes representing that directory's children.
+
+      NAME is simply the name of the file or directory. CONTENTS is a string
+    holding the file's contents (if a file).
+
+    """
+
+    def __init__(self, name, children=None, contents=None):
+        assert children is None or contents is None
+        self.name = name
+        self.mtime = 0
+        self.children = children
+        self.contents = contents
+        self.path = name
+
+    def add_child(self, newchild):
+        assert not self.is_file()
+        for a in self.children:
+            if a.name == newchild.name:
+                if newchild.is_file():
+                    a.contents = newchild.contents
+                    a.path = os.path.join(self.path, newchild.name)
+                else:
+                    for i in newchild.children:
+                        a.add_child(i)
+                break
+        else:
+            self.children.append(newchild)
+            newchild.path = os.path.join(self.path, newchild.name)
 
-import svn_tree;
+    def get_child(self, name):
+        """
+          If the given TreeNode directory NODE contains a child named NAME,
+        return the child; else, return None.
+
+        """
+        for n in self.children:
+            if n.name == name:
+                return n
+
+    def is_file(self):
+        return self.children is None
+
+    def pprint(self):
+        print(" * Node name: %s" % self.name)
+        print("    Path:     %s" % self.path)
+        print("    Contents: %s" % self.contents)
+        if self.is_file():
+            print("    Children: is a file.")
+        else:
+            print("    Children: %d" % len(self.children))
 
-class Trees_difference:
 
+class TreeDifference:
     def __init__(self):
         self.added_files = []
         self.removed_files = []
@@ -23,94 +98,139 @@
         self.touched_files.extend(other.touched_files)
 
     def ignore_directories(self):
-        """Removes directories for list of found differences"""
+        """Removes directories from our lists of found differences."""
         not_dir = lambda x : x[-1] != "/"
         self.added_files = filter(not_dir, self.added_files)
         self.removed_files = filter(not_dir, self.removed_files)
         self.modified_files = filter(not_dir, self.modified_files)
         self.touched_files = filter(not_dir, self.touched_files)
 
-    def pprint(self, f=None):
-        print >> f, "Added files   :", self.added_files
-        print >> f, "Removed files :", self.removed_files
-        print >> f, "Modified files:", self.modified_files
-        print >> f, "Touched files :", self.touched_files
+    def pprint(self, file=sys.stdout):
+        file.write("Added files   : %s\n" % self.added_files)
+        file.write("Removed files : %s\n" % self.removed_files)
+        file.write("Modified files: %s\n" % self.modified_files)
+        file.write("Touched files : %s\n" % self.touched_files)
 
     def empty(self):
-        return (not self.added_files and not self.removed_files and
-            not self.modified_files and not self.touched_files)
+        return not (self.added_files or self.removed_files or
+            self.modified_files or self.touched_files)
 
-def build_tree(dir):
-    return svn_tree.build_tree_from_wc(dir, load_props=0, ignore_svn=1)
 
-def trees_difference(a, b, current_name=""):
-    """Compare SVNTreeNodes A and B, and create Trees_difference class."""
+def build_tree(path):
+    """
+      Takes PATH as the folder path, walks the file system below that path, and
+    creates a tree structure based on any files and folders found there.
 
-    assert a.name == b.name
+      All root nodes have an empty name to avoid being displayed when listing
+    differences between two
+    """
+    root = TreeNode("__ROOT_TREE_NODE__", children=[])
+    _handle_dir(os.path.normpath(path), root)
+    return root
+
+
+def tree_difference(a, b):
+    """Compare TreeNodes A and B, and create a TreeDifference instance."""
+    return _do_tree_difference(a, b, "", True)
 
-    result = Trees_difference()
-    try:
-        # A and B are both files.
-        if a.children is None and b.children is None:
-            assert a.name == b.name
-            if svn_tree.compare_file_nodes(a, b):
-                result.modified_files.append(current_name)
-            elif a.mtime != b.mtime:
-                result.touched_files.append(current_name)
-
-        # One is a file, one is a directory.
-        # This case has been disabled because svn_tree does not distinguish
-        # empty directories from files, at least on Cygwin.
-        elif 0 and bool(a.children is None) != bool(b.children is None):
-            a.pprint()
-            b.pprint()
-            raise svn_tree.SVNTypeMismatch
-        # They are both directories.
-        else:
-            # accounted_for holds children present in both trees.
-            accounted_for = []
-            for a_child in (a.children or []):
-                b_child = svn_tree.get_child(b, a_child.name)
-                if b_child:
-                    accounted_for.append(b_child)
-                    if current_name:
-                        result.append(trees_difference(a_child, b_child, current_name + "/" + a_child.name))
-                    else:
-                        result.append(trees_difference(a_child, b_child, a_child.name))
-                else:
-                    if current_name:
-                        result.removed_files.append(current_name + "/" + a_child.name)
-                    else:
-                        result.removed_files.append(a_child.name)
-            for b_child in (b.children or []):
-                if (b_child not in accounted_for):
-                    result.added_files.extend(traverse_tree(b_child, current_name))
-
-    except svn_tree.SVNTypeMismatch:
-        print("Unequal Types: one Node is a file, the other is a directory")
-        raise svn_tree.SVNTreeUnequal
-    except svn_tree.SVNTreeIsNotDirectory:
-        print("Error: Foolish call to get_child.")
-        sys.exit(1)
-    except IndexError:
-        print("Error: unequal number of children")
-        raise svn_tree.SVNTreeUnequal
-    return result
 
-def dump_tree(t):
-    svn_tree.dump_tree(t)
+def _do_tree_difference(a, b, parent_path, root=False):
+    """Internal recursive worker function for tree_difference()."""
 
-def traverse_tree(t, parent_name=""):
-    """Returns the list of all names in tree."""
-    if parent_name:
-        full_node_name = parent_name + "/" + t.name
+    # We do not want to list root node names.
+    if root:
+        assert not parent_path
+        assert not a.is_file()
+        assert not b.is_file()
+        full_path = ""
     else:
-        full_node_name = t.name
+        assert a.name == b.name
+        full_path = parent_path + a.name
+    result = TreeDifference()
+
+    # A and B are both files.
+    if a.is_file() and b.is_file():
+        if a.contents != b.contents:
+            result.modified_files.append(full_path)
+        elif a.mtime != b.mtime:
+            result.touched_files.append(full_path)
+        return result
+
+    # Directory converted to file.
+    if not a.is_file() and b.is_file():
+        result.removed_files.extend(_traverse_tree(a, parent_path))
+        result.added_files.append(full_path)
+
+    # File converted to directory.
+    elif a.is_file() and not b.is_file():
+        result.removed_files.append(full_path)
+        result.added_files.extend(_traverse_tree(b, parent_path))
 
-    if t.children is None:
+    # A and B are both directories.
+    else:
+        if full_path:
+            full_path += "/"
+        accounted_for = []  # Children present in both trees.
+        for a_child in a.children:
+            b_child = b.get_child(a_child.name)
+            if b_child:
+                accounted_for.append(b_child)
+                result.append(_do_tree_difference(a_child, b_child, full_path))
+            else:
+                result.removed_files.append(full_path + a_child.name)
+        for b_child in b.children:
+            if b_child not in accounted_for:
+                result.added_files.extend(_traverse_tree(b_child, full_path))
+
+    return result
+
+
+def _traverse_tree(t, parent_path):
+    """Returns a list of all names in a tree."""
+    assert not parent_path or parent_path[-1] == "/"
+    full_node_name = parent_path + t.name
+    if t.is_file():
         result = [full_node_name]
     else:
-        result = [full_node_name + "/"]
+        name_prefix = full_node_name + "/"
+        result = [name_prefix]
         for i in t.children:
-            result.extend(traverse_tree(i, full_node_name))
+            result.extend(_traverse_tree(i, name_prefix))
     return result
+
+
+def _get_text(path):
+    """Return a string with the textual contents of a file at PATH."""
+    fp = open(path, 'r')
+    try:
+        return fp.read()
+    finally:
+        fp.close()
+
+
+def _handle_dir(path, current_parent):
+    """Main recursive worker function for build_tree()."""
+    files = []
+    dirs = []
+
+    # List files & folders.
+    for f in os.listdir(path):
+        f = os.path.join(path, f)
+        if os.path.isdir(f):
+            dirs.append(f)
+        elif os.path.isfile(f):
+            files.append(f)
+
+    # Add each file as a child of CURRENT_PARENT.
+    for f in files:
+        fcontents = _get_text(f)
+        c = TreeNode(os.path.basename(f), contents=fcontents)
+        c.mtime = os.stat(f).st_mtime
+        current_parent.add_child(c)
+
+    # For each subdir, create a node, walk its tree, add it as a child.
+    for d in dirs:
+        new_dir_node = TreeNode(os.path.basename(d), children=[])
+        _handle_dir(d, new_dir_node)
+        new_dir_node.mtime = os.stat(f).st_mtime
+        current_parent.add_child(new_dir_node)