[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: trees and test suites -- a proposal

From: Ben Collins-Sussman <sussman_at_collab.net>
Date: 2001-04-18 17:17:27 CEST

Wow, quite a lot of work!

Have you looked at svn_output.py? I'm worried that you've reinvented
a lot of things I've already done.

1. The compare_sets() routine takes two lists and a comparison func,
and decides if the lists are the same, regardless of ordering.

For comparing actual vs. expected output, I'm handing it a list of
output lines and a list of regexps. The 'comparison' func tries to
match a line with a regexp.

2. svn_entry.py loads up an entries file from disk into a hash of
hashes, just like the C function svn_wc_get_entries. The TODO comment
you saw was referring to the fact that I was planning on writing
another comparison func that compared entry objects, and again using
this func with compare_sets().

I'll be working on python stuff later this afternoon... and I'll take
a closer look at your stuff. Maybe your system is better. :)

Sam TH <sam@uchicago.edu> writes:

> --yNb1oOkm5a9FJOVX
> Content-Type: multipart/mixed; boundary="8t9RHnE3ZwKMSgU+"
> Content-Disposition: inline
>
>
> --8t9RHnE3ZwKMSgU+
> Content-Type: text/plain; charset=us-ascii
> Content-Disposition: inline
> Content-Transfer-Encoding: quoted-printable
>
> Well, since Python is so much fun, I decided to take a look at what I
> could do in the test suite. And there I noticed the todo item to
> check the entries file against the desired results. So I decided to
> work on that.
>
> Then, I thought that really, the expected results and the hierarchy of
> entries files were both really trees, and I could just convert them
> all to trees and then compare them. =20
>
> Then I realized that many of the things we want to compare are really
> representations of trees in the filesystem (the disk filesystem, not
> the SVN filesytem). So I figured, why not create a generic tree
> structure, and have lots of mappings to it? =20
>
> So that's what I did.
>
> So, with the history out of the way, here's the details. As I see it,
> there are a large number of different representations of what the
> on-disk filesystem looks like (not even counting the one in the SVN
> filesystem, which the black box testing doesn't see). =20
>
> - The output of svn commands like checkout.
> - The SVN/entries files
> - the CVS/Entries files, for cvs2svn
> - The actual on-disk files
> - The expected results (which may or may not be the same as one of
> the above)
>
> There may be more as well.
>
> So, we should have a generic representation of all of these, and a way
> to transform to that representation. =20
>
> The way I have constructed that representation is with a single python
> class, SVNTreeNode. However, you shouldn't ever have to deal with
> that class at all. The interfaces will look like so:
>
> # create a tree from the expected paths
> exp_tree =3D create_tree_from_paths(greek_paths)
>
> # create a tree from the output
> result_tree =3D create_tree_from_output(output)
>
> # make sure they're the same
> if not(compare_trees(exp_tree, result_tree)):
> print "Eeek!"
>
> I've already written create_tree_from_paths(), and it parses the
> greek_trees variable in xml_tests.py properly. I've also written the
> comparison function, and the rest of the basic infrastructure. Before
> I wrote parsers for the rest, I'd like to make sure that no one has
> serious problems with the way I'm going about this. =20
>
> Attached is svn_tree.py, with the current implementation. =20
> =20
> sam th --- sam_at_uchicago.edu --- http://www.abisource.com/~sam/
> OpenPGP Key: CABD33FC --- http://samth.dyndns.org/key
> DeCSS: http://samth.dyndns.org/decss
>
>
> --8t9RHnE3ZwKMSgU+
> Content-Type: text/plain; charset=us-ascii
> Content-Description: current implementation
> Content-Disposition: attachment; filename="svn_tree.py"
> Content-Transfer-Encoding: quoted-printable
>
> #!/usr/bin/env python
> #
> # svn_tree.py: tools for comparing directory trees
> #
> # Subversion is a tool for revision control.=20
> # See http://subversion.tigris.org for more information.
> # =20
> # =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> # 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.
> #
> ######################################################################
>
> # A node in the directory tree.
> #
> # If CHILDREN is None, then the node is a file.
> # Otherwise, CHILDREN is a list of the nodes making up that
> # directorie's children.
> #
> # NAME is simply the name of the file of directory
>
> class SVNTreeNode:
> def __init__(self, name, children=3DNone):
> self.name =3D name
> self.children =3D children
> def add_child(self, newchild):
> if self.children is None:
> self.children =3D []
> n =3D 0
> for a in self.children:
> if a.name =3D=3D newchild.name:
> n =3D 1
> break
> if n =3D=3D 0:
> self.children.append(newchild)
> elif not (newchild.children is None):
> for i in newchild.children:
> a.add_child(i)
>
> # reserved name of the root of the tree
>
> root_node_name =3D "__SVN_ROOT_NODE"=20
>
> # Exception raised if you screw up in this module.
>
> class SVNTreeError(Exception): pass
>
> # Exception raised if two trees are unequal
>
> class SVNTreeUnequal(Exception): pass
>
> def create_from_path(path):
> """Create and return a new tree, given a path representing a single
> entry into that tree."""
> # internal use only
>
> # get a list of all the names in the path
> # each of these will be a child of the former
> elements =3D path.split("/")
> if len(elements) =3D=3D 0:
> raise SVNTreeError
>
> root_node =3D SVNTreeNode(elements[0], None)
>
> add_elements_as_path(root_node, elements[1:])
>
> return root_node
>
> def add_elements_as_path(top_node, path_list):
> """Add the elements in PATH as if they were a single path below
> TOP_NODE."""
> =20
> # 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.
> #
> # It's sort of hard to describe clearly, but it's quite useful. =20
> =20
> prev_node =3D top_node
> for i in path_list:
> new_node =3D SVNTreeNode(i, None)
> prev_node.add_child(new_node)
> prev_node =3D new_node
>
> def build_tree_from_paths(paths):
> "Take a list of paths, and create a tree from them."
>
> root =3D SVNTreeNode(root_node_name, None)
> =20
> for i in paths:
> root.add_child(create_from_path(i))
>
> return root
>
> def tree_is_greater(a, b):
> "Comparison function for trees. Only compares the names."
> # Interal use only
> if a.name =3D=3D b.name:
> return 0
> if a.name > b.name:
> return 1
> else:
> return -1
> =20
>
> def compare_trees(a, b):
> "Check whether A and B are the same tree"
> try:
> if a.name !=3D b.name:
> print "Error: %s is not the same as %s." % (a.name, b.name)
> raise SVNTreeUnequal
> if a.children is None:
> if b.children is None:
> return 1
> else:
> raise SVNTreeUnequal
> if b.children is None:
> raise SVNTreeUnequal
> a.children.sort(tree_is_greater)
> b.children.sort(tree_is_greater)
> for i in range(max(len(a.children), len(b.children))):
> compare_trees(a.children[i], b.children[i])
> except IndexError:
> print "Error: unequal number of children"
> raise SVNTreeUnequal
> except SVNTreeUnequal:
> if a.name =3D=3D root_node_name:
> return 0
> else:
> print "Unequal at node %s" % a.name
> raise SVNTreeUnequal
> return 1
>
> =20
>
> def dump_tree(n,indent=3D""):
> "Print out a nice representation of the tree."
> # Code partially stolen from Dave Beazley
> if n.children is None:
> tmp_children =3D []
> else:
> tmp_children =3D n.children
>
> if n.name =3D=3D root_node_name:
> print "%s%s" % (indent, "Top of the tree")
> else:
> print "%s%s" % (indent, n.name)
>
> indent =3D indent.replace("-"," ")
> indent =3D indent.replace("+"," ")
> for i in range(len(tmp_children)):
> c =3D tmp_children[i]
> if i =3D=3D len(tmp_children
> )-1:
> dump_tree(c,indent + " +-- ")
> else:
> dump_tree(c,indent + " |-- ")
>
> #########################################
> ## Test code -- to be removed
>
> greek_paths =3D ['iota', 'A', 'A/mu', 'A/B', 'A/B/lambda', 'A/B/E',
> 'A/B/E/alpha', 'A/B/E/beta', 'A/B/F', 'A/C', 'A/D',
> 'A/D/gamma', 'A/D/G', 'A/D/G/pi', 'A/D/G/rho', 'A/D/G/tau',
> 'A/D/H', 'A/D/H/chi', 'A/D/H/psi', 'A/D/H/omega']
>
> greek_paths2 =3D ['iota', 'A', 'A/mu', 'A/B', 'A/B/lambda', 'A/B/E',
> 'A/D/gamma', 'A/D/G', 'A/D/G/pi', 'A/D/G/rho', 'A/D/G/tau',
> 'A/B/E/alpha', 'A/B/E/beta', 'A/B/F', 'A/C', 'A/D',
> 'A/D/H', 'A/D/H/chi', 'A/D/H/psi', 'A/D/H/omega']
>
> greek_paths3 =3D ['iota', 'A', 'A/mu', 'A/B', 'A/B/lambda', 'A/B/E',
> 'A/D/gamma', 'A/D/G', 'A/D/G/pi', 'A/D/G/rho', 'A/D/G/tau',
> 'A/B/E/alpha', 'A/B/E/beta', 'A/B/F', 'A/C', 'A/D',
> 'A/D/H', 'A/D/H/chi', 'A/D/H/psi', 'A/D/H/omegafoo']
>
> test_tree =3D build_tree_from_paths(greek_paths)
> test_tree2 =3D build_tree_from_paths(greek_paths2)
> test_tree3 =3D build_tree_from_paths(greek_paths3)
>
> dump_tree(test_tree)
> dump_tree(test_tree2)
>
> if 1 =3D=3D compare_trees(test_tree, test_tree3):
> print "they are equal"
> else:
> print "they are not equal"
>
> ### End of file.
> # local variables:
> # eval: (load-file "../../../svn-dev.el")
> # end:
> =20
>
> --8t9RHnE3ZwKMSgU+--
>
> --yNb1oOkm5a9FJOVX
> Content-Type: application/pgp-signature
> Content-Disposition: inline
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.0.4 (GNU/Linux)
> Comment: For info see http://www.gnupg.org
>
> iD8DBQE63a4Gt+kM0Mq9M/wRAlAQAJ9C/VqoySuc/ph2oCntGL87TszEVACeMS9F
> rspRV4GIMCTJfQieHtkGStY=
> =kkIq
> -----END PGP SIGNATURE-----
>
> --yNb1oOkm5a9FJOVX--
Received on Sat Oct 21 14:36:29 2006

This is an archived mail posted to the Subversion Dev mailing list.