Merge lp:~spud/spud/unused-schemas into lp:spud

[Fraser Waters]

Compare multiple xml files to one schema to determine what parts of the schema are not used.

[lp:~spud/spud/unused-schemas]

477. By Fraser Waters on 2011-09-07

Bug fix and don't show 'comments'

[Simon Funke (simon-funke)]

This is a very useful feature.
The code looks good;
The diff feature was successfully tested against all flml's in the fluidity test directory.
Documentation will be provided in a later merge.
=> good to go!

review: Approve

[Patrick Farrell (pefarrell)]

Fraser: I have a few comments.

Firstly, 'useage' should be spelled 'usage'.

Secondly, the "Input list" on the top of the gui window is a bit confusing: a list of what?

Thirdly, I expected it to open a directory to find all the flml files beneath, but I can't seem to do that: I can only open a file.

Fourth, it takes a very long time: I suspect that this is some algorithmic flaw. To be honest, I can't see any theoretical reason why this shouldn't take more than, say, 10 seconds; if it's taking longer than this it seems to me that we have the wrong algorithm implemented. Even if it does take very long, the UI freezes while it is working, which will lead users to think that diamond has crashed.

Fifth, can you please make it remember which directory you opened before, instead of defaulting to the cwd?

Finally, I ran it on 1material_shocktube.flml and got no schema usage window. Instead, I got a traceback on the shell:

Traceback (most recent call last):
  File "/usr/lib/python2.7/dist-packages/diamond/interface.py", line 779, in on_finduseage
    useview.UseView(self.s, self.filename)
  File "/usr/lib/python2.7/dist-packages/diamond/useview.py", line 49, in __init__
    self.__update(schema, paths)
  File "/usr/lib/python2.7/dist-packages/diamond/useview.py", line 144, in __update
    self.__set_useage(schemauseage.find_unusedset(schema, paths))
  File "/usr/lib/python2.7/dist-packages/diamond/schemauseage.py", line 81, in find_unusedset
    tree = schema.read(path)
  File "/usr/lib/python2.7/dist-packages/diamond/schema.py", line 504, in read
    doc = etree.parse(xmlfile)
  File "lxml.etree.pyx", line 2942, in lxml.etree.parse (src/lxml/lxml.etree.c:54187)
  File "parser.pxi", line 1528, in lxml.etree._parseDocument (src/lxml/lxml.etree.c:79485)
  File "parser.pxi", line 1557, in lxml.etree._parseDocumentFromURL (src/lxml/lxml.etree.c:79768)
  File "parser.pxi", line 1457, in lxml.etree._parseDocFromFile (src/lxml/lxml.etree.c:78843)
  File "parser.pxi", line 997, in lxml.etree._BaseParser._parseDocFromFile (src/lxml/lxml.etree.c:75698)
  File "parser.pxi", line 564, in lxml.etree._ParserContext._handleParseResultDoc (src/lxml/lxml.etree.c:71739)
  File "parser.pxi", line 645, in lxml.etree._handleParseResult (src/lxml/lxml.etree.c:72614)
  File "parser.pxi", line 583, in lxml.etree._raiseParseError (src/lxml/lxml.etree.c:71927)
IOError: Error reading file '<?xml version='1.0' encoding='utf-8'?>': failed to load external entity "<?xml version='1.0' encoding='utf-8'?>"

[Patrick Farrell (pefarrell)]

Simon: "The diff feature was successfully tested against all flml's in the fluidity test directory. "

The diff feature has nothing to do with this feature/merge request?

[Fraser Waters (fraser-waters08)]

Currently (and this is in the manual) the input file its asking for is a file with a list of paths to check. We figured this is slightly more adaptable than just selecting every .suffix file, but that can be done as well if needs be.

Question four, the algorithm is pretty simple. Make a set of every element in the schema, then open each file and for every element in that file remove it from the set.
(This is slight more efficent than building a new set from each file and than calculating set differences) I can't think of any way this can be improved we HAVE to look at every schema element and we HAVE to look at every element in every file.
The UI freeze is also mentioned in the manual. We'll have to pull that off to another thread and then callback to UI to fix that, can probably be done but I'll have to look up how to do threads and callbacks first.

Final question, that's not the input it was expecting but there should be error handeling around it so that it at least doesn't crash.

[Patrick Farrell (pefarrell)]

Ah, well in that case it is good that I didn't read the manual first, so that I could find where it was counterintuitive :-)

I think we should take in a directory. In practice, this will only ever be run on all the flml files in the tests/ or longtests/ directories, so it makes sense to do it that way.

I made a file

[pef@aislinn:~/src/spud]$ cat /tmp/files
/data/pfarrell/fluidity/trunk/tests/python_diagnostic_field/python.flml

and ran it on that. I got:

Traceback (most recent call last):
  File "/usr/lib/python2.7/dist-packages/diamond/interface.py", line 779, in on_finduseage
    useview.UseView(self.s, self.filename)
  File "/usr/lib/python2.7/dist-packages/diamond/useview.py", line 49, in __init__
    self.__update(schema, paths)
  File "/usr/lib/python2.7/dist-packages/diamond/useview.py", line 144, in __update
    self.__set_useage(schemauseage.find_unusedset(schema, paths))
  File "/usr/lib/python2.7/dist-packages/diamond/useview.py", line 116, in __set_useage
    iter = self.treestore.get_iter(self.mapping[xpath])
KeyError: '/*/*[278]/*/*'

[Fraser Waters (fraser-waters08)]

Could I have that file please? If it's not in the mapping it means somehow usage traversal found it but useview traversal didn't...

If it's always going to be every .suffix in a directory I can change it to that easy enough, give me a few minutes.

[Patrick Farrell (pefarrell)]

While file? I pasted the contents of the list, and the referenced flml file lives in the fluidity trunk (tests/python_diagnostic_field/python.flml).

[Fraser Waters (fraser-waters08)]

Ah I see, sorry not enough coffee in the blood yet. I'll check it out.

[Fraser Waters (fraser-waters08)]

Oki that's fixed, it was just a problem with comment nodes (we were ignoring them at one point and trying to look them up later)

[Patrick Farrell (pefarrell)]

Great. It now works when I call it on fluidity's tests directory. And the results are /very/ interesting. Fantastic work!

Quick query: is it possible to offer a command-line option that only does the schema usage on a specified directory (i.e. doesn't bring up the main interface)?

[Patrick Farrell (pefarrell)]

I did some profiling where I ran it on the tests/ directory, and the results are pretty interesting.

About 2/3 of the runtime is spent in xpath lookups. As a simple first optimisation, I memoised schema.element_children. The runtime of on_finduseage went from 577s to 359s. Not bad for 7 lines of code! And of the 366 seconds of runtime, over 191s of those are still in xpath lookups.

Exercise for the interested reader (i.e. Fraser): identify all the other points where xpath lookups are happening and cache it. I tried memoising schema.tree.xpath, but because the class is written in C, I can't overwrite the function (unfortunately). Caching the usages at

/usr/lib/python2.7/dist-packages/diamond/schemausage.py:31
and
/usr/lib/python2.7/dist-packages/diamond/useview.py:78

would knock off about another ~170s or so.

Here's the profile for the r492:

{method 'xpath' of 'lxml.etree._ElementTree' objects} <- 32 0.051 0.051 /usr/lib/python2.7/dist-packages/diamond/preprocess.py:26(preprocess)
                                                                             1823 0.726 0.726 /usr/lib/python2.7/dist-packages/diamond/schema.py:79(element_children)
                                                                           120235 6.166 6.166 /usr/lib/python2.7/dist-packages/diamond/schema.py:123(valid_children)
                                                                                1 0.000 0.000 /usr/lib/python2.7/dist-packages/diamond/schemausage.py:26(find_fullset)
                                                                           231826 91.364 91.364 /usr/lib/python2.7/dist-packages/diamond/schemausage.py:31(traverse)
                                                                           231826 93.463 93.463 /usr/lib/python2.7/dist-packages/diamond/useview.py:78(__set_treestore)
                                                                                1 0.000 0.000 /usr/lib/python2.7/dist-packages/diamond/useview.py:140(__update)
{method 'xpath' of 'lxml.etree._Element' objects} <- 425764 12.282 12.282 /usr/lib/python2.7/dist-packages/diamond/schema.py:691(assign_xml_nodes)

[Fraser Waters (fraser-waters08)]

command-line option: yes, how about -u [DIR]?

I'm not suprised at those profile results, xpath lookups was my first guess.

[Patrick Farrell (pefarrell)]

Yes, -u is fine. I have got the time down from 577s to 268s -- hopefully you can make further improvements. I've been running it like this:

python -m cProfile -o statfile /usr/bin/diamond test.flml

and then visualising the stats with RunSnakeRun (.deb packages in /scratch/pfarrell)

[Fraser Waters (fraser-waters08)]

-u is in. Also added some caching in other places. The bulk of time is now spent in schema.Read
Next up, async UseView and DiffView and change the manual to match the new UseView behaviour

[Fraser Waters (fraser-waters08)]

And that's all in, DiffView and UseView won't freeze Diamond anymore

[Patrick Farrell (pefarrell)]

"Parseing schema" should be "Parsing schema".

Nice work! Down from 577s to 160s. I told you you could make it faster :-)

Now, for the coup-de-grace: Can you add a -ub (-u, batch) option that doesn't open any GUI or gtk window, but just makes diamond exit with 0 (if all the schema is used) and 1 (if any part of the schema is unused)? I want to add a test that all of the schema is used ... :-)

[Patrick Farrell (pefarrell)]

And while I'm adding last-minute feature requests: can -ub print out to the terminal some readable description of the schema entries that are not used by the tests?

Thanks for all the hard work you have done over the 10 weeks; the whole group and I are very impressed.

[Fraser Waters (fraser-waters08)]

Readable, do you want the schemaname (the /*/*//[58] format) or some kind of named path (Like element (fludity_options)/element *(material_phase)/choice/element *(scalar_field) ).
The later will be better for humans the former for machines.

=== modified file 'diamond/diamond/choice.py'
--- diamond/diamond/choice.py	2011-07-29 09:18:28 +0000
+++ diamond/diamond/choice.py	2011-09-07 14:03:34 +0000
@@ -58,6 +58,10 @@
   def _on_set_attr(self, node, attr, value):
     self.emit("on-set-attr", attr, value)
 
+  def get_attrs(self):
+    """Get all attributes"""
+    return self.get_current_tree().get_attrs()
+
   def set_default_active(self):
     self.active = True
     if self.cardinality == '?' or self.cardinality == '*':

=== modified file 'diamond/diamond/interface.py'
--- diamond/diamond/interface.py	2011-09-07 12:31:36 +0000
+++ diamond/diamond/interface.py	2011-09-07 14:03:34 +0000
@@ -50,6 +50,7 @@
 import datawidget
 import diffview
 import sliceview
+import useview
 
 from lxml import etree
 
@@ -144,6 +145,7 @@
                     "on_slice": self.on_slice,
                     "on_diff": self.on_diff,
                     "on_diffsave": self.on_diffsave,
+                    "on_finduseage": self.on_finduseage,
                     "on_group": self.on_group,
                     "on_ungroup": self.on_ungroup}
 
@@ -773,6 +775,9 @@
     else:
       dialogs.error(self.main_window, "No save to diff against.")
 
+  def on_finduseage(self, widget = None):
+    useview.UseView(self.s, self.filename)
+
   def on_slice(self, widget = None):
     if not self.selected_node.is_sliceable():
       self.statusbar.set_statusbar("Cannot slice on this element.")

=== modified file 'diamond/diamond/schema.py'
--- diamond/diamond/schema.py	2011-08-02 11:29:07 +0000
+++ diamond/diamond/schema.py	2011-09-07 14:03:34 +0000
@@ -55,17 +55,17 @@
                       'interleave': self.cb_group,
                       'name': self.cb_name,
                       'text': self.cb_text,
-		      'anyName' : self.cb_anyname,
-		      'nsName' : self.cb_nsname,
-		      'except' : self.cb_except,
+                      'anyName' : self.cb_anyname,
+                      'nsName' : self.cb_nsname,
+                      'except' : self.cb_except,
                       'ignore' : self.cb_ignore,
                       'notAllowed' : self.cb_notallowed}
-                      
+
     self.lost_eles  = []
     self.added_eles = []
     self.lost_attrs  = []
     self.added_attrs = []
-  
+
     return
 
   def element_children(self, element):
@@ -145,19 +145,12 @@
     if isinstance(eid, tree.Tree) or isinstance(eid, choice.Choice):
       eidtree = eid
       eid = eid.schemaname
-    
-    if eid == ":start":
-      try:
-        node = self.tree.xpath('/t:grammar/t:start', namespaces={'t': 'http://relaxng.org/ns/structure/1.0'})[0]
-      except:
-        debug.deprint("No valid start node found. Are you using a library Relax-NG file like spud_base.rng?", 0)
-        sys.exit(0)
-    else:
-      xpath = self.tree.xpath(eid)
-      if len(xpath) == 0:
-        debug.deprint("Warning: no element with XPath %s" % eid)
-        return None
-      node = xpath[0]
+
+    xpath = self.tree.xpath(eid)
+    if len(xpath) == 0:
+      debug.deprint("Warning: no element with XPath %s" % eid)
+      return None
+    node = xpath[0]
 
     node = self.to_tree(node)
   

=== added file 'diamond/diamond/schemauseage.py'
--- diamond/diamond/schemauseage.py	1970-01-01 00:00:00 +0000
+++ diamond/diamond/schemauseage.py	2011-09-07 14:03:34 +0000
@@ -0,0 +1,102 @@
+#!/usr/bin/env python
+
+#    This file is part of Diamond.
+#
+#    Diamond is free software: you can redistribute it and/or modify
+#    it under the terms of the GNU General Public License as published by
+#    the Free Software Foundation, either version 3 of the License, or
+#    (at your option) any later version.
+#
+#    Diamond is distributed in the hope that it will be useful,
+#    but WITHOUT ANY WARRANTY; without even the implied warranty of
+#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+#    GNU General Public License for more details.
+#
+#    You should have received a copy of the GNU General Public License
+#    along with Diamond.  If not, see <http://www.gnu.org/licenses/>.
+
+from cStringIO import StringIO
+from lxml import etree
+
+from schema import Schema
+
+RELAXNGNS = "http://relaxng.org/ns/structure/1.0"
+RELAXNG = "{" + RELAXNGNS + "}"
+
+def find_fullset(tree):
+  """
+  Given a schema tree pulls out xpaths for every element.
+  """
+
+  def traverse(node):
+
+    if node.tag == RELAXNG + "element" or (node.tag == RELAXNG + "choice" and all(n.tag != RELAXNG + "value" for n in node)):
+      fullset.add(tree.getpath(node))
+
+    elif node.tag == RELAXNG + "ref":
+      node = tree.xpath('/t:grammar/t:define[@name="' + node.get("name") + '"]', namespaces={'t': RELAXNGNS})[0]
+
+    for child in node:
+      traverse(child)
+
+  start = tree.xpath("/t:grammar/t:start", namespaces={'t': RELAXNGNS})[0]
+
+  root = start[0]
+
+  fullset = set()
+  traverse(root)
+  return fullset
+
+def find_useset(tree):
+  """
+  Given a diamond xml tree pulls out scehama paths for every element and attribute.
+  """
+
+  def traverse(node):
+    if node.active:
+      useset.add(node.schemaname)
+
+      for child in node.get_children():
+        traverse(child)
+
+  useset = set()
+  traverse(tree)
+  return useset
+
+def find_unusedset(schema, paths):
+  """
+  Given the a diamond schema and a list of paths to xml files
+  find the unused xpaths.
+  """
+  def traverse(node):
+    if node.active:
+      unusedset.discard(node.schemaname)
+
+      for child in node.get_children():
+        traverse(child)
+
+  unusedset = find_fullset(schema.tree)
+
+  for path in paths:
+    tree = schema.read(path)
+    traverse(tree)
+
+  return unusedset
+
+def strip(tag):
+  return tag[tag.index("}") + 1:]
+
+def node_name(node):
+  """
+  Returns a name for this node.
+  """
+  tagname = node.get("name") if "name" in node.keys() else strip(node.tag)
+  name = None
+
+  for child in node:
+    if child.tag == RELAXNG + "attribute":
+      if "name" in child.keys() and child.get("name") == "name":
+        for grandchild in child:
+          if grandchild.tag == RELAXNG + "value":
+            name = " (" + grandchild.text + ")"
+  return tagname + (name if name else "")

=== modified file 'diamond/diamond/tree.py'
--- diamond/diamond/tree.py	2011-07-30 04:36:33 +0000
+++ diamond/diamond/tree.py	2011-09-07 14:03:34 +0000
@@ -53,7 +53,7 @@
 
     # Any children?
     if children is None:
-      self.children = copy.copy([])
+      self.children = []
     else:
       self.children = children
 
@@ -114,6 +114,10 @@
     (datatype, curval) = self.attrs[attr]
     return curval
 
+  def get_attrs(self):
+    """Get all attributes"""
+    return self.attrs
+
   def set_data(self, data):
     (invalid, data) = self.valid_data(self.datatype, data)
     if invalid:

=== added file 'diamond/diamond/useview.py'
--- diamond/diamond/useview.py	1970-01-01 00:00:00 +0000
+++ diamond/diamond/useview.py	2011-09-07 14:03:34 +0000
@@ -0,0 +1,156 @@
+#!/usr/bin/env python
+
+#    This file is part of Diamond.
+#
+#    Diamond is free software: you can redistribute it and/or modify
+#    it under the terms of the GNU General Public License as published by
+#    the Free Software Foundation, either version 3 of the License, or
+#    (at your option) any later version.
+#
+#    Diamond is distributed in the hope that it will be useful,
+#    but WITHOUT ANY WARRANTY; without even the implied warranty of
+#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+#    GNU General Public License for more details.
+#
+#    You should have received a copy of the GNU General Public License
+#    along with Diamond.  If not, see <http://www.gnu.org/licenses/>.
+
+import gobject
+import gtk
+
+import schemauseage
+
+RELAXNGNS = "http://relaxng.org/ns/structure/1.0"
+RELAXNG = "{" + RELAXNGNS + "}"
+
+class UseView(gtk.Window):
+  def __init__(self, schema, path):
+    gtk.Window.__init__(self)
+    self.__add_controls()
+
+    dialog = gtk.FileChooserDialog(title = "Input list",
+                                   action = gtk.FILE_CHOOSER_ACTION_OPEN,
+                                   buttons = (gtk.STOCK_CANCEL, gtk.RESPONSE_CANCEL, gtk.STOCK_OPEN, gtk.RESPONSE_OK))
+
+    if path:
+      dialog.set_current_folder(path)
+    response = dialog.run()
+    if response != gtk.RESPONSE_OK:
+      dialog.destroy()
+      return
+
+    filename = dialog.get_filename()
+    dialog.destroy()
+
+    paths = [line.strip() for line in open(filename) if line.strip()]
+    if not paths:
+      return
+
+    self.__update(schema, paths)
+    self.show_all()
+
+  def __add_controls(self): 
+    self.set_title("Unused schema entries")
+    self.set_default_size(800, 600)
+
+    scrolledwindow = gtk.ScrolledWindow()
+    scrolledwindow.set_policy(gtk.POLICY_AUTOMATIC, gtk.POLICY_AUTOMATIC)
+
+    self.treeview = gtk.TreeView()
+
+    self.treeview.get_selection().set_mode(gtk.SELECTION_SINGLE)
+
+    # Node column
+    celltext = gtk.CellRendererText()
+    column = gtk.TreeViewColumn("Node", celltext)
+    column.set_cell_data_func(celltext, self.set_celltext)
+
+    self.treeview.append_column(column)
+
+    # 0: The node tag
+    # 1: Used (0 == Not used, 1 = Child not used, 2 = Used)
+    self.treestore = gtk.TreeStore(gobject.TYPE_PYOBJECT, gobject.TYPE_PYOBJECT)
+    self.treeview.set_model(self.treestore)
+    self.treeview.set_enable_search(False)
+
+    scrolledwindow.add(self.treeview)
+    self.add(scrolledwindow)
+
+  def __set_treestore(self, node, iter = None, type = None):
+    if node.tag == RELAXNG + "element":
+      name = schemauseage.node_name(node)
+      if name == "comment":
+        return #early out to skip comment nodes
+
+      tag = name + (type if type else "")
+      child_iter = self.treestore.append(iter, [tag, 2])
+      self.mapping[self.tree.getpath(node)] = self.treestore.get_path(child_iter)
+      type = None
+    elif node.tag == RELAXNG + "choice" and all(n.tag != RELAXNG + "value" for n in node):
+      tag = "choice" + (type if type else "")
+      child_iter = self.treestore.append(iter, [tag, 2])
+      self.mapping[self.tree.getpath(node)] = self.treestore.get_path(child_iter)
+      type = None
+    elif node.tag == RELAXNG + "optional":
+      child_iter = iter
+      type = " ?"
+    elif node.tag == RELAXNG + "oneOrMore":
+      child_iter = iter
+      type = " +"
+    elif node.tag == RELAXNG + "zeroOrMore":
+      child_iter = iter
+      type = " *"
+    elif node.tag == RELAXNG + "ref":
+      node = self.tree.xpath('/t:grammar/t:define[@name="' + node.get("name") + '"]', namespaces={'t': RELAXNGNS})[0]
+      child_iter = iter
+    elif node.tag == RELAXNG + "group" or node.tag == RELAXNG + "interleave":
+      child_iter = iter
+    else:
+      return
+
+    for child in node:
+      self.__set_treestore(child, child_iter, type)
+
+  def __set_useage(self, useage):
+    for xpath in useage:
+      iter = self.treestore.get_iter(self.mapping[xpath])
+      self.treestore.set_value(iter, 1, 0)
+
+  def __floodfill(self, iter, parent = 2):
+    """
+    Floodfill the tree with the correct useage.
+    """
+    if parent == 0: #parent is not used
+      self.treestore.set_value(iter, 1, 0) #color us not used
+
+    useage = self.treestore.get_value(iter, 1)
+
+    child = self.treestore.iter_children(iter)
+    while child is not None:
+      change = self.__floodfill(child, useage)
+      if change != 2 and useage == 2:
+        self.treestore.set(iter, 1, 1)
+      child = self.treestore.iter_next(child)
+
+    return self.treestore.get_value(iter, 1)
+ 
+
+  def __update(self, schema, paths):
+    self.tree = schema.tree
+    self.start = self.tree.xpath('/t:grammar/t:start', namespaces={'t': RELAXNGNS})[0]
+    self.mapping = {}
+
+    self.__set_treestore(self.start[0])
+    self.__set_useage(schemauseage.find_unusedset(schema, paths))
+    self.__floodfill(self.treestore.get_iter_root())
+
+  def set_celltext(self, column, cell, model, iter):
+    tag, useage = model.get(iter, 0, 1)
+    cell.set_property("text", tag)
+
+    if useage == 0:
+      cell.set_property("foreground", "red")
+    elif useage == 1:
+      cell.set_property("foreground", "indianred")
+    else:
+      cell.set_property("foreground", "black")

=== modified file 'diamond/gui/gui.glade'
--- diamond/gui/gui.glade	2011-08-23 12:37:37 +0000
+++ diamond/gui/gui.glade	2011-09-07 14:03:34 +0000
@@ -227,7 +227,7 @@
                         <signal name="activate" handler="on_diff"/>
                       </widget>
                     </child>
-                     <child>
+                    <child>
                       <widget class="GtkMenuItem" id="menuitemDiffSave">
                         <property name="visible">True</property>
                         <property name="label" translatable="yes">Diff against last save</property>
@@ -235,6 +235,13 @@
                       </widget>
                     </child>
                     <child>
+                      <widget class="GtkMenuItem" id="menuitemFindUseage">
+                        <property name="visible">True</property>
+                        <property name="label" translatable="yes">Find schema useage</property>
+                        <signal name="activate" handler="on_finduseage"/>
+                      </widget>
+                    </child>
+                    <child>
                       <widget class="GtkCheckMenuItem" id="display_properties">
                         <property name="visible">True</property>
                         <property name="tooltip" translatable="yes">Display the option properties on the right hand side of the main window.</property>