svntest/tree.py

   1 #
   2 #  tree.py: tools for comparing directory trees
   3 #
   4 #  Subversion is a tool for revision control.
   5 #  See http://subversion.tigris.org for more information.
   6 #
   7 # ====================================================================
   8 #    Licensed to the Apache Software Foundation (ASF) under one
   9 #    or more contributor license agreements.  See the NOTICE file
  10 #    distributed with this work for additional information
  11 #    regarding copyright ownership.  The ASF licenses this file
  12 #    to you under the Apache License, Version 2.0 (the
  13 #    "License"); you may not use this file except in compliance
  14 #    with the License.  You may obtain a copy of the License at
  15 #
  16 #      http://www.apache.org/licenses/LICENSE-2.0
  17 #
  18 #    Unless required by applicable law or agreed to in writing,
  19 #    software distributed under the License is distributed on an
  20 #    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  21 #    KIND, either express or implied.  See the License for the
  22 #    specific language governing permissions and limitations
  23 #    under the License.
  24 ######################################################################
  25
  26 import re
  27 import os
  28 import sys
  29 if sys.version_info[0] >= 3:
  30   # Python >=3.0
  31   from io import StringIO
  32 else:
  33   # Python <3.0
  34   from cStringIO import StringIO
  35 from xml.dom.minidom import parseString
  36 import base64
  37 import logging
  38
  39 import svntest
  40
  41 logger = logging.getLogger()
  42
  43 # Tree Exceptions.
  44
  45 # All tree exceptions should inherit from SVNTreeError
  46 class SVNTreeError(svntest.Failure):
  47   "Exception raised if you screw up in the tree module."
  48   pass
  49
  50 class SVNTreeUnequal(SVNTreeError):
  51   "Exception raised if two trees are unequal."
  52   pass
  53
  54 class SVNTypeMismatch(SVNTreeError):
  55   "Exception raised if one node is file and other is dir"
  56   pass
  57
  58 #========================================================================
  59
  60 # ===>  Overview of our Datastructures  <===
  61
  62 # The general idea here is that many, many things can be represented by
  63 # a tree structure:
  64
  65 #   - a working copy's structure and contents
  66 #   - the output of 'svn status'
  67 #   - the output of 'svn checkout/update'
  68 #   - the output of 'svn commit'
  69
  70 # The idea is that a test function creates a "expected" tree of some
  71 # kind, and is then able to compare it to an "actual" tree that comes
  72 # from running the Subversion client.  This is what makes a test
  73 # automated; if an actual and expected tree match exactly, then the test
  74 # has passed.  (See compare_trees() below.)
  75
  76 # The SVNTreeNode class is the fundamental data type used to build tree
  77 # structures.  The class contains a method for "dropping" a new node
  78 # into an ever-growing tree structure. (See also create_from_path()).
  79
  80 # We have four parsers in this file for the four use cases listed above:
  81 # each parser examines some kind of input and returns a tree of
  82 # SVNTreeNode objects.  (See build_tree_from_checkout(),
  83 # build_tree_from_commit(), build_tree_from_status(), and
  84 # build_tree_from_wc()).  These trees are the "actual" trees that result
  85 # from running the Subversion client.
  86
  87 # Also necessary, of course, is a convenient way for a test to create an
  88 # "expected" tree.  The test *could* manually construct and link a bunch
  89 # of SVNTreeNodes, certainly.  But instead, all the tests are using the
  90 # build_generic_tree() routine instead.
  91
  92 # build_generic_tree() takes a specially-formatted list of lists as
  93 # input, and returns a tree of SVNTreeNodes.  The list of lists has this
  94 # structure:
  95
  96 #   [ ['/full/path/to/item', 'text contents', {prop-hash}, {att-hash}],
  97 #     [...],
  98 #     [...],
  99 #     ...   ]
 100
 101 # You can see that each item in the list essentially defines an
 102 # SVNTreeNode.  build_generic_tree() instantiates a SVNTreeNode for each
 103 # item, and then drops it into a tree by parsing each item's full path.
 104
 105 # So a typical test routine spends most of its time preparing lists of
 106 # this format and sending them to build_generic_tree(), rather than
 107 # building the "expected" trees directly.
 108
 109 #   ### Note: in the future, we'd like to remove this extra layer of
 110 #   ### abstraction.  We'd like the SVNTreeNode class to be more
 111 #   ### directly programmer-friendly, providing a number of accessor
 112 #   ### routines, so that tests can construct trees directly.
 113
 114 # The first three fields of each list-item are self-explanatory.  It's
 115 # the fourth field, the "attribute" hash, that needs some explanation.
 116 # The att-hash is used to place extra information about the node itself,
 117 # depending on the parsing context:
 118
 119 #   - in the 'svn co/up' use-case, each line of output starts with two
 120 #     characters from the set of (A, D, G, U, C, _) or 'Restored'.  The
 121 #     status code is stored in a attribute named 'status'.  In the case
 122 #     of a restored file, the word 'Restored' is stored in an attribute
 123 #     named 'verb'.
 124
 125 #   - in the 'svn ci/im' use-case, each line of output starts with one
 126 #      of the words (Adding, Deleting, Sending).  This verb is stored in
 127 #      an attribute named 'verb'.
 128
 129 #   - in the 'svn status' use-case (which is always run with the -v
 130 #     (--verbose) flag), each line of output contains a working revision
 131 #     number and a two-letter status code similar to the 'svn co/up'
 132 #     case.  This information is stored in attributes named 'wc_rev'
 133 #     and 'status'.  The repository revision is also printed, but it
 134 #     is ignored.
 135
 136 #   - in the working-copy use-case, the att-hash is ignored.
 137
 138
 139 # Finally, one last explanation: the file 'actions.py' contain a number
 140 # of helper routines named 'run_and_verify_FOO'.  These routines take
 141 # one or more "expected" trees as input, then run some svn subcommand,
 142 # then push the output through an appropriate parser to derive an
 143 # "actual" tree.  Then it runs compare_trees() and raises an exception
 144 # on failure.  This is why most tests typically end with a call to
 145 # run_and_verify_FOO().
 146
 147
 148
 149 #========================================================================
 150
 151 # A node in a tree.
 152 #
 153 # If CHILDREN is None, then the node is a file.  Otherwise, CHILDREN
 154 # is a list of the nodes making up that directory's children.
 155 #
 156 # NAME is simply the name of the file or directory.  CONTENTS is a
 157 # string that contains the file's contents (if a file), PROPS are
 158 # properties attached to files or dirs, and ATTS is a dictionary of
 159 # other metadata attached to the node.
 160
 161 class SVNTreeNode:
 162
 163   def __init__(self, name, children=None, contents=None, props={}, atts={}):
 164     self.name = name
 165     self.children = children
 166     self.contents = contents
 167     self.props = props
 168     self.atts = atts
 169     self.path = name
 170
 171 # TODO: Check to make sure contents and children are mutually exclusive
 172
 173   def add_child(self, newchild):
 174     child_already_exists = 0
 175     if self.children is None:  # if you're a file,
 176       self.children = []     # become an empty dir.
 177     else:
 178       for a in self.children:
 179         if a.name == newchild.name:
 180           child_already_exists = 1
 181           break
 182
 183     if child_already_exists:
 184       if newchild.children is None:
 185         # this is the 'end' of the chain, so copy any content here.
 186         a.contents = newchild.contents
 187         a.props = newchild.props
 188         a.atts = newchild.atts
 189         a.path = os.path.join(self.path, newchild.name)
 190       else:
 191         # try to add dangling children to your matching node
 192         for i in newchild.children:
 193           a.add_child(i)
 194     else:
 195       self.children.append(newchild)
 196       newchild.path = os.path.join(self.path, newchild.name)
 197
 198
 199   def pprint(self, stream = sys.stdout):
 200     "Pretty-print the meta data for this node to STREAM."
 201     stream.write(" * Node name:   %s\n" % self.name)
 202     stream.write("    Path:       %s\n" % self.path)
 203     mime_type = self.props.get("svn:mime-type")
 204     if not mime_type or mime_type.startswith("text/"):
 205       if self.children is not None:
 206         stream.write("    Contents:   N/A (node is a directory)\n")
 207       else:
 208         stream.write("    Contents:   %s\n" % self.contents)
 209     else:
 210       stream.write("    Contents:   %d bytes (binary)\n" % len(self.contents))
 211     stream.write("    Properties: %s\n" % self.props)
 212     stream.write("    Attributes: %s\n" % self.atts)
 213     ### FIXME: I'd like to be able to tell the difference between
 214     ### self.children is None (file) and self.children == [] (empty
 215     ### directory), but it seems that most places that construct
 216     ### SVNTreeNode objects don't even try to do that.  --xbc
 217     ###
 218     ### See issue #1611 about this problem.  -kfogel
 219     if self.children is not None:
 220       stream.write("    Children:   %s\n" % len(self.children))
 221     else:
 222       stream.write("    Children:  None (node is probably a file)\n")
 223     stream.flush()
 224
 225   def get_printable_path(self):
 226     """Remove some occurrences of root_node_name = "__SVN_ROOT_NODE",
 227     it is in the way when matching for a subtree, and looks bad."""
 228     path = self.path
 229     if path.startswith(root_node_name + os.sep):
 230       path = path[len(root_node_name + os.sep):]
 231     return path
 232
 233   def print_script(self, stream = sys.stdout, subtree = "", prepend="\n  ",
 234                    drop_empties = True):
 235     """Python-script-print the meta data for this node to STREAM.
 236     Print only those nodes whose path string starts with the string SUBTREE,
 237     and print only the part of the path string that remains after SUBTREE.
 238     PREPEND is a string prepended to each node printout (does the line
 239     feed if desired, don't include a comma in PREPEND).
 240     If DROP_EMPTIES is true, all dir nodes that have no data set in them
 241     (no props, no atts) and that have children (so they are included
 242     implicitly anyway) are not printed.
 243     Return 1 if this node was printed, 0 otherwise (added up by
 244     dump_tree_script())"""
 245
 246     # figure out if this node would be obsolete to print.
 247     if drop_empties and len(self.props) < 1 and len(self.atts) < 1 and \
 248        self.contents is None and self.children is not None:
 249       return 0
 250
 251     path = self.get_printable_path()
 252
 253     # remove the subtree path, skip this node if necessary.
 254     if path.startswith(subtree):
 255       path = path[len(subtree):]
 256     else:
 257       return 0
 258
 259     if path.startswith(os.sep):
 260       path = path[1:]
 261
 262     line = prepend
 263     line += "%-20s: Item(" % ("'%s'" % path.replace(os.sep, '/'))
 264     comma = False
 265
 266     mime_type = self.props.get("svn:mime-type")
 267     if not mime_type or mime_type.startswith("text/"):
 268       if self.contents is not None:
 269         # Escape some characters for nicer script and readability.
 270         # (This is error output. I guess speed is no consideration here.)
 271         line += "contents=\"%s\"" % (self.contents
 272                                      .replace('\n','\\n')
 273                                      .replace('"','\\"')
 274                                      .replace('\r','\\r')
 275                                      .replace('\t','\\t'))
 276         comma = True
 277     else:
 278       line += 'content is binary data'
 279       comma = True
 280
 281     if self.props:
 282       if comma:
 283         line += ", "
 284       line += "props={"
 285       comma = False
 286
 287       for name in self.props:
 288         if comma:
 289           line += ", "
 290         line += "'%s':'%s'" % (name, self.props[name])
 291         comma = True
 292
 293       line += "}"
 294       comma = True
 295
 296     for name in self.atts:
 297       if comma:
 298         line += ", "
 299       line += "%s='%s'" % (name, self.atts[name])
 300       comma = True
 301
 302     line += "),"
 303     stream.write("%s" % line)
 304     stream.flush()
 305     return 1
 306
 307
 308   def __str__(self):
 309     s = StringIO()
 310     self.pprint(s)
 311     return s.getvalue()
 312
 313
 314   def __cmp__(self, other):
 315     """Define a simple ordering of two nodes without regard to their full
 316     path (i.e. position in the tree). This can be used for sorting the
 317     children within a directory."""
 318     return cmp(self.name, other.name)
 319
 320   def as_state(self, prefix=None):
 321     """Return an svntest.wc.State instance that is equivalent to this tree."""
 322     root = self
 323     if self.path == root_node_name:
 324       assert prefix is None
 325       wc_dir = ''
 326       while True:
 327         if root is not self:  # don't prepend ROOT_NODE_NAME
 328           wc_dir = os.path.join(wc_dir, root.name)
 329         if root.contents or root.props or root.atts:
 330           break
 331         if not root.children or len(root.children) != 1:
 332           break
 333         root = root.children[0]
 334       state = svntest.wc.State(wc_dir, { })
 335       if root.contents or root.props or root.atts:
 336         state.add({'': root.as_item()})
 337       prefix = wc_dir
 338     else:
 339       assert prefix is not None
 340
 341       path = self.path
 342       if path.startswith(root_node_name):
 343         path = path[len(root_node_name)+1:]
 344       # prefix should only be set on a recursion, which means a child,
 345       # which means this path better not be the same as the prefix.
 346       assert path != prefix, 'not processing a child of the root'
 347       l = len(prefix)
 348       if l > 0:
 349         assert path[:l] == prefix, \
 350             '"%s" is not a prefix of "%s"' % (prefix, path)
 351         # return the portion after the separator
 352         path = path[l+1:].replace(os.sep, '/')
 353
 354       state = svntest.wc.State('', {
 355           path: self.as_item()
 356           })
 357
 358     if root.children:
 359       for child in root.children:
 360         state.add_state('', child.as_state(prefix))
 361
 362     return state
 363
 364   def as_item(self):
 365     return svntest.wc.StateItem(self.contents,
 366                                 self.props,
 367                                 self.atts.get('status'),
 368                                 self.atts.get('verb'),
 369                                 self.atts.get('wc_rev'),
 370                                 self.atts.get('locked'),
 371                                 self.atts.get('copied'),
 372                                 self.atts.get('switched'),
 373                                 self.atts.get('writelocked'),
 374                                 self.atts.get('treeconflict'))
 375
 376   def recurse(self, function):
 377     results = []
 378     results += [ function(self) ]
 379     if self.children:
 380       for child in self.children:
 381         results += child.recurse(function)
 382     return results
 383
 384   def find_node(self, path):
 385     if self.get_printable_path() == path:
 386       return self
 387     if self.children:
 388       for child in self.children:
 389         result = child.find_node(path)
 390         if result:
 391           return result
 392     return None
 393
 394 # reserved name of the root of the tree
 395 root_node_name = "__SVN_ROOT_NODE"
 396
 397
 398 # helper func
 399 def add_elements_as_path(top_node, element_list):
 400   """Add the elements in ELEMENT_LIST as if they were a single path
 401   below TOP_NODE."""
 402
 403   # The idea of this function is to take a list like so:
 404   # ['A', 'B', 'C'] and a top node, say 'Z', and generate a tree
 405   # like this:
 406   #
 407   #             Z -> A -> B -> C
 408   #
 409   # where 1 -> 2 means 2 is a child of 1.
 410   #
 411
 412   prev_node = top_node
 413   for i in element_list:
 414     new_node = SVNTreeNode(i, None)
 415     prev_node.add_child(new_node)
 416     prev_node = new_node
 417
 418
 419 # Helper for compare_trees
 420 def compare_file_nodes(a, b):
 421   """Compare two nodes, A (actual) and B (expected). Compare their names,
 422   contents, properties and attributes, ignoring children.  Return 0 if the
 423   same, 1 otherwise."""
 424   if a.name != b.name:
 425     return 1
 426   if a.contents != b.contents:
 427     return 1
 428   if a.props != b.props:
 429     return 1
 430   if a.atts == b.atts:
 431     # No fixes necessary
 432     return 0
 433
 434   # Fix a pre-WC-NG assumptions in our testsuite
 435   if (b.atts == {'status': 'A ', 'wc_rev': '0'})     \
 436      and (a.atts == {'status': 'A ', 'wc_rev': '-'}):
 437     return 0
 438   return 1
 439
 440 # Helper for compare_trees
 441 def compare_dir_nodes(a, b):
 442   """Compare two nodes, A (actual) and B (expected). Compare their names,
 443   properties and attributes, ignoring children.  Return 0 if the
 444   same, 1 otherwise."""
 445   if a.name != b.name:
 446     return 1
 447   if (a.props != b.props):
 448     return 1
 449   if (a.atts == b.atts):
 450     # No fixes necessary
 451     return 0
 452
 453   # Fix a pre-WC-NG assumptions in our testsuite
 454   if (b.atts == {'status': 'A ', 'wc_rev': '0'})     \
 455      and (a.atts == {'status': 'A ', 'wc_rev': '-'}):
 456     return 0
 457   return 1
 458
 459
 460 # Internal utility used by most build_tree_from_foo() routines.
 461 #
 462 # (Take the output and .add_child() it to a root node.)
 463
 464 def create_from_path(path, contents=None, props={}, atts={}):
 465   """Create and return a linked list of treenodes, given a PATH
 466   representing a single entry into that tree.  CONTENTS and PROPS are
 467   optional arguments that will be deposited in the tail node."""
 468
 469   # get a list of all the names in the path
 470   # each of these will be a child of the former
 471   if os.sep != "/":
 472     path = path.replace(os.sep, "/")
 473   elements = path.split("/")
 474   if len(elements) == 0:
 475     ### we should raise a less generic error here. which?
 476     raise SVNTreeError
 477
 478   root_node = None
 479
 480   # if this is Windows: if the path contains a drive name (X:), make it
 481   # the root node.
 482   if os.name == 'nt':
 483     m = re.match("([a-zA-Z]:)(.+)", elements[0])
 484     if m:
 485       root_node = SVNTreeNode(m.group(1), None)
 486       elements[0] = m.group(2)
 487       add_elements_as_path(root_node, elements[0:])
 488
 489   if not root_node:
 490     root_node = SVNTreeNode(elements[0], None)
 491     add_elements_as_path(root_node, elements[1:])
 492
 493   # deposit contents in the very last node.
 494   node = root_node
 495   while True:
 496     if node.children is None:
 497       node.contents = contents
 498       node.props = props
 499       node.atts = atts
 500       break
 501     node = node.children[0]
 502
 503   return root_node
 504
 505
 506 eol_re = re.compile(r'(\r\n|\r)')
 507
 508 # helper for build_tree_from_wc()
 509 def get_props(paths):
 510   """Return a hash of hashes of props for PATHS, using the svn client. Convert
 511      each embedded end-of-line to a single LF character."""
 512
 513   # It's not kosher to look inside .svn/ and try to read the internal
 514   # property storage format.  Instead, we use 'svn proplist'.  After
 515   # all, this is the only way the user can retrieve them, so we're
 516   # respecting the black-box paradigm.
 517
 518   files = {}
 519   exit_code, output, errput = svntest.main.run_svn(1,
 520                                                    "proplist",
 521                                                    "--verbose",
 522                                                    "--xml",
 523                                                    *paths)
 524
 525   output = (line for line in output if not line.startswith('DBG:'))
 526   dom = parseString(''.join(output))
 527   target_nodes = dom.getElementsByTagName('target')
 528   for target_node in target_nodes:
 529     filename = target_node.attributes['path'].nodeValue
 530     file_props = {}
 531     for property_node in target_node.getElementsByTagName('property'):
 532       name = property_node.attributes['name'].nodeValue
 533       if property_node.hasChildNodes():
 534         text_node = property_node.firstChild
 535         value = text_node.nodeValue
 536       else:
 537         value = ''
 538       try:
 539         encoding = property_node.attributes['encoding'].nodeValue
 540         if encoding == 'base64':
 541           value = base64.b64decode(value)
 542         else:
 543           raise Exception("Unknown encoding '%s' for file '%s' property '%s'"
 544                           % (encoding, filename, name,))
 545       except KeyError:
 546         pass
 547       # If the property value contained a CR, or if under Windows an
 548       # "svn:*" property contains a newline, then the XML output
 549       # contains a CR character XML-encoded as '&#13;'.  The XML
 550       # parser converts it back into a CR character.  So again convert
 551       # all end-of-line variants into a single LF:
 552       value = eol_re.sub('\n', value)
 553       file_props[name] = value
 554     files[filename] = file_props
 555
 556   dom.unlink()
 557   return files
 558
 559
 560 ### ridiculous function. callers should do this one line themselves.
 561 def get_text(path):
 562   "Return a string with the textual contents of a file at PATH."
 563
 564   # sanity check
 565   if not os.path.isfile(path):
 566     return None
 567
 568   return open(path, 'r').read()
 569
 570
 571 def get_child(node, name):
 572   """If SVNTreeNode NODE contains a child named NAME, return child;
 573   else, return None. If SVNTreeNode is not a directory, exit completely."""
 574   if node.children == None:
 575     logger.error("Foolish call to get_child.")
 576     sys.exit(1)
 577   for n in node.children:
 578     if name == n.name:
 579       return n
 580   return None
 581
 582
 583 # Helper for compare_trees
 584 def default_singleton_handler(node, description):
 585   """Print SVNTreeNode NODE's name, describing it with the string
 586   DESCRIPTION, then raise SVNTreeUnequal."""
 587   logger.warn("Couldn't find node '%s' in %s tree" % (node.name, description))
 588   logger.warn(str(node))
 589   raise SVNTreeUnequal
 590
 591 # A test helper function implementing the singleton_handler_a API.
 592 def detect_conflict_files(node, extra_files):
 593   """NODE has been discovered, an extra file on disk.  Verify that it
 594   matches one of the regular expressions in the EXTRA_FILES list.  If
 595   it matches, remove the match from the list.  If it doesn't match,
 596   raise an exception."""
 597
 598   for pattern in extra_files:
 599     mo = re.match(pattern, node.name)
 600     if mo:
 601       extra_files.pop(extra_files.index(pattern)) # delete pattern from list
 602       break
 603   else:
 604     msg = "Encountered unexpected disk path '" + node.name + "'"
 605     logger.warn(msg)
 606     logger.warn(str(node))
 607     raise SVNTreeUnequal(msg)
 608
 609 ###########################################################################
 610 ###########################################################################
 611 # EXPORTED ROUTINES ARE BELOW
 612
 613
 614 # Main tree comparison routine!
 615
 616 def compare_trees(label,
 617                   a, b,
 618                   singleton_handler_a = None,
 619                   a_baton = None,
 620                   singleton_handler_b = None,
 621                   b_baton = None):
 622   """Compare SVNTreeNodes A (actual) and B (expected), expressing
 623   differences using FUNC_A and FUNC_B.  FUNC_A and FUNC_B are
 624   functions of two arguments (a SVNTreeNode and a context baton), and
 625   may raise exception SVNTreeUnequal, in which case they use the
 626   string LABEL to describe the error (their return value is ignored).
 627   LABEL is typically "output", "disk", "status", or some other word
 628   that labels the trees being compared.
 629
 630   If A and B are both files, then return if their contents,
 631   properties, and names are all the same; else raise a SVNTreeUnequal.
 632   If A is a file and B is a directory, raise a SVNTreeUnequal; same
 633   vice-versa.  If both are directories, then for each entry that
 634   exists in both, call compare_trees on the two entries; otherwise, if
 635   the entry exists only in A, invoke FUNC_A on it, and likewise for
 636   B with FUNC_B."""
 637
 638   def display_nodes(a, b):
 639     'Display two nodes, expected and actual.'
 640     o = StringIO()
 641     o.write("=============================================================\n")
 642     o.write("Expected '%s' and actual '%s' in %s tree are different!\n"
 643                 % (b.name, a.name, label))
 644     o.write("=============================================================\n")
 645     o.write("EXPECTED NODE TO BE:\n")
 646     o.write("=============================================================\n")
 647     b.pprint(o)
 648     o.write("=============================================================\n")
 649     o.write("ACTUAL NODE FOUND:\n")
 650     o.write("=============================================================\n")
 651     a.pprint(o)
 652     logger.warn(o.getvalue())
 653     o.close()
 654
 655   # Setup singleton handlers
 656   if singleton_handler_a is None:
 657     singleton_handler_a = default_singleton_handler
 658     a_baton = "expected " + label
 659   if singleton_handler_b is None:
 660     singleton_handler_b = default_singleton_handler
 661     b_baton = "actual " + label
 662
 663   try:
 664     # A and B are both files.
 665     if (a.children is None) and (b.children is None):
 666       if compare_file_nodes(a, b):
 667         display_nodes(a, b)
 668         raise SVNTreeUnequal
 669     # One is a file, one is a directory.
 670     elif (((a.children is None) and (b.children is not None))
 671           or ((a.children is not None) and (b.children is None))):
 672       display_nodes(a, b)
 673       raise SVNTypeMismatch
 674     # They're both directories.
 675     else:
 676       if compare_dir_nodes(a, b):
 677         display_nodes(a, b)
 678         raise SVNTreeUnequal
 679
 680       accounted_for = []
 681       # For each child of A, check and see if it's in B.  If so, run
 682       # compare_trees on the two children and add b's child to
 683       # accounted_for.  If not, run FUNC_A on the child.  Next, for each
 684       # child of B, check and see if it's in accounted_for.  If it is,
 685       # do nothing. If not, run FUNC_B on it.
 686       for a_child in a.children:
 687         b_child = get_child(b, a_child.name)
 688         if b_child:
 689           accounted_for.append(b_child)
 690           compare_trees(label, a_child, b_child,
 691                         singleton_handler_a, a_baton,
 692                         singleton_handler_b, b_baton)
 693         else:
 694           singleton_handler_a(a_child, a_baton)
 695       for b_child in b.children:
 696         if b_child not in accounted_for:
 697           singleton_handler_b(b_child, b_baton)
 698   except SVNTypeMismatch:
 699     logger.warn('Unequal Types: one Node is a file, the other is a directory')
 700     raise SVNTreeUnequal
 701   except IndexError:
 702     logger.warn("Error: unequal number of children")
 703     raise SVNTreeUnequal
 704   except SVNTreeUnequal:
 705     if a.name != root_node_name:
 706       logger.warn("Unequal at node %s" % a.name)
 707     raise
 708
 709
 710
 711 # Visually show a tree's structure
 712
 713 def _dump_tree(n,indent="",stream=sys.stdout):
 714   """Print out a nice representation of the structure of the tree in
 715   the SVNTreeNode N. Prefix each line with the string INDENT."""
 716
 717   # Code partially stolen from Dave Beazley
 718   tmp_children = sorted(n.children or [])
 719
 720   if n.name == root_node_name:
 721     stream.write("%s%s\n" % (indent, "ROOT"))
 722   else:
 723     stream.write("%s%s\n" % (indent, n.name))
 724
 725   indent = indent.replace("-", " ")
 726   indent = indent.replace("+", " ")
 727   for i in range(len(tmp_children)):
 728     c = tmp_children[i]
 729     if i == len(tmp_children)-1:
 730       _dump_tree(c,indent + "  +-- ",stream)
 731     else:
 732       _dump_tree(c,indent + "  |-- ",stream)
 733
 734
 735 def dump_tree(n):
 736     output = StringIO()
 737     _dump_tree(n,stream=output)
 738     logger.warn(output.getvalue())
 739     output.close()
 740
 741
 742 def dump_tree_script__crawler(n, subtree="", stream=sys.stdout):
 743   "Helper for dump_tree_script. See that comment."
 744   count = 0
 745
 746   # skip printing the root node.
 747   if n.name != root_node_name:
 748     count += n.print_script(stream, subtree)
 749
 750   for child in n.children or []:
 751     count += dump_tree_script__crawler(child, subtree, stream)
 752
 753   return count
 754
 755
 756 def dump_tree_script(n, subtree="", stream=sys.stdout, wc_varname='wc_dir'):
 757   """Print out a python script representation of the structure of the tree
 758   in the SVNTreeNode N. Print only those nodes whose path string starts
 759   with the string SUBTREE, and print only the part of the path string
 760   that remains after SUBTREE.
 761   The result is printed to STREAM.
 762   The WC_VARNAME is inserted in the svntest.wc.State(wc_dir,{}) call
 763   that is printed out (this is used by factory.py)."""
 764
 765   stream.write("svntest.wc.State(" + wc_varname + ", {")
 766   count = dump_tree_script__crawler(n, subtree, stream)
 767   if count > 0:
 768     stream.write('\n')
 769   stream.write("})")
 770
 771
 772 ###################################################################
 773 ###################################################################
 774 # PARSERS that return trees made of SVNTreeNodes....
 775
 776
 777 ###################################################################
 778 # Build an "expected" static tree from a list of lists
 779
 780
 781 # Create a list of lists, of the form:
 782 #
 783 #  [ [path, contents, props, atts], ... ]
 784 #
 785 #  and run it through this parser.  PATH is a string, a path to the
 786 #  object.  CONTENTS is either a string or None, and PROPS and ATTS are
 787 #  populated dictionaries or {}.  Each CONTENTS/PROPS/ATTS will be
 788 #  attached to the basename-node of the associated PATH.
 789
 790 def build_generic_tree(nodelist):
 791   "Given a list of lists of a specific format, return a tree."
 792
 793   root = SVNTreeNode(root_node_name)
 794
 795   for list in nodelist:
 796     new_branch = create_from_path(list[0], list[1], list[2], list[3])
 797     root.add_child(new_branch)
 798
 799   return root
 800
 801
 802 ####################################################################
 803 # Build trees from different kinds of subcommand output.
 804
 805
 806 # Parse co/up output into a tree.
 807 #
 808 #   Tree nodes will contain no contents, a 'status' att, and a
 809 #   'treeconflict' att.
 810
 811 def build_tree_from_checkout(lines, include_skipped=True):
 812   "Return a tree derived by parsing the output LINES from 'co' or 'up'."
 813
 814   return svntest.wc.State.from_checkout(lines, include_skipped).old_tree()
 815
 816
 817 # Parse ci/im output into a tree.
 818 #
 819 #   Tree nodes will contain no contents, and only one 'verb' att.
 820
 821 def build_tree_from_commit(lines):
 822   "Return a tree derived by parsing the output LINES from 'ci' or 'im'."
 823
 824   return svntest.wc.State.from_commit(lines).old_tree()
 825
 826
 827 # Parse status output into a tree.
 828 #
 829 #   Tree nodes will contain no contents, and these atts:
 830 #
 831 #          'status', 'wc_rev',
 832 #             ... and possibly 'locked', 'copied', 'switched',
 833 #             'writelocked' and 'treeconflict',
 834 #             IFF columns non-empty.
 835 #
 836
 837 def build_tree_from_status(lines):
 838   "Return a tree derived by parsing the output LINES from 'st -vuq'."
 839
 840   return svntest.wc.State.from_status(lines).old_tree()
 841
 842
 843 # Parse merge "skipped" output
 844
 845 def build_tree_from_skipped(lines):
 846
 847   return svntest.wc.State.from_skipped(lines).old_tree()
 848
 849
 850 def build_tree_from_diff_summarize(lines):
 851   "Build a tree from output of diff --summarize"
 852
 853   return svntest.wc.State.from_summarize(lines).old_tree()
 854
 855
 856 ####################################################################
 857 # Build trees by looking at the working copy
 858
 859
 860 #   The reason the 'load_props' flag is off by default is because it
 861 #   creates a drastic slowdown -- we spawn a new 'svn proplist'
 862 #   process for every file and dir in the working copy!
 863
 864
 865 def build_tree_from_wc(wc_path, load_props=0, ignore_svn=1):
 866     """Takes WC_PATH as the path to a working copy.  Walks the tree below
 867     that path, and creates the tree based on the actual found
 868     files.  If IGNORE_SVN is true, then exclude SVN admin dirs from the tree.
 869     If LOAD_PROPS is true, the props will be added to the tree."""
 870
 871     return svntest.wc.State.from_wc(wc_path, load_props, ignore_svn).old_tree()