[pygccxml-commit] source/pyplusplus/experimental treerange.py,NONE,1.1 filters.py,1.2,1.3 selection.py,1.2,1.3 declwrapper.py,1.2,1.3

[Matthias B. <mb...@us...>]

Update of /cvsroot/pygccxml/source/pyplusplus/experimental
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv12314

Modified Files:
	filters.py selection.py declwrapper.py 
Added Files:
	treerange.py 
Log Message:
Added the TreeRange class that serves as an iterator over selected parts of the declaration tree. The filters can now specify a range they operate on (instead of what I was calling 'parent constraints'). With this change it is now possible to concatenate queries no matter if it was a query that returned a single result or multiple results. The TreeRange will also ease the distinction of local vs global search (even on node by node basis). Currently, the default is still global search, I'll change that asap.

--- NEW FILE: treerange.py ---
# Copyright 2006 Roman Yakovenko.
# 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)
#
# Initial author: Matthias Baas

"""This module contains the TreeRange class.
"""

# TreeRange
class TreeRange:
    """This class represents a part of a tree.

    A B{simple tree range} is defined by a I{parent} node and a boolean
    flag I{recursive}. The immediate children of the parent node are
    always contained in the range (the parent itself is excluded). If
    the boolean flag is True then all grand-children of the parent
    node are also contained in the range.

    A B{compound range} is one that contains more than one simple ranges.

    The purpose of this class is to provide an iterator that yields
    parts of a declaration tree. This iteration is used when particular
    declarations are queried.
    By calling the L{union()} and L{intersection()} methods, a range
    can be created that restricts the search to particular areas of the
    tree. This can be used to exploit a priori knowledge about the filter
    function when it is known that a filter will never match a node outside
    a particular range.

    A tree range can itself be a tree of ranges. For example, consider the
    case when only the direct children of a node are contained in a range
    and you make a union() operation with a range that lies beneath that
    node. In this case, the sub range will be a children of the first range.
    A range object can only have sub ranges when its recursive flag is set
    to False, otherwise all possible sub ranges are already contained
    in that range anyway.
    """
    
    def __init__(self, parent, recursive, subranges=None):
        """Constructor.
        """

        if subranges==None:
            subranges = []

        # Parent node
        # (None is only allowed in the root)
        self.parent = parent
        # Recursive flag 
        self.recursive = recursive
        # A list of sub ranges. The list items are TreeRange objects.
        # The sub ranges must be disjoint!
        # The list must be empty when recursive is True!
        self.subranges = subranges

    def __str__(self):
        return "<TreeRange: parent:%s recursive:%s #subranges:%d>"%(self.parent, self.recursive, len(self.subranges))

    def __iter__(self):
        """The same as iterNodes()."""
        return self.iterNodes()

    # iterNodes
    def iterNodes(self):
        """Iterate over all nodes within this range.

        yields the individual nodes (declaration_t objects).
        """
        if self.parent!=None:
            for node in self._iterdecls(self.parent, self.recursive):
                yield node

        for sr in self.subranges:
            for node in sr.iterNodes():
                yield node

    # _iterdecls
    def _iterdecls(self, parent, recursive):
        """Depth first iteration over a declaration (sub) tree.
        
        Iterates over the children of parent. If recursive is set to True
        the iteration also includes the grand-children.
        The parent itself is not returned.

        @param parent: Starting node
        @param recursive: Determines whether the method also yields children nodes 
        @type recursive: bool
        """

        children = getattr(parent, "declarations", [])
        for ch in children:
            yield ch
            if recursive:
                for node in self._iterdecls(ch, True):
                    yield node

    # iterRanges
    def iterRanges(self):
        """Iterate over the simple ranges within this range.

        The ranges are iterated from bottom to top.
        """

        for sr in self.subranges:
            for r in sr.iterRanges():
                yield r

        if self.parent!=None:
            yield self.parent, self.recursive
            

    # intersect
    def intersect(self, other):
        """Return the intersection of self and other.

        Update the current tree and return the new root.

        @param other: A simple range (parent, recursive).
        @type other: 2-tuple
        @returns: The new root node.
        @rtype: TreeRange        
        """

        res = self
        for rng in other.iterRanges():
            res = res._simpleIntersect(rng)

        return res

    def _simpleIntersect(self, simplerange):
        """Return the intersection of self and other.

        Update the current tree and return the new root.

        @param simplerange: A simple range (parent, recursive).
        @type simplerange: 2-tuple
        @returns: The new root node.
        @rtype: TreeRange        
        """
        otherparent, otherrecursive = simplerange
        
        if self.parent!=None:
            rs = self._rangeRelationship(self.parent, otherparent)
            # disjoint?
            if rs==0:
                self.parent = None
                self.recursive = False
                self.subranges = []
                return self
            # otherparent==parent?
            elif rs==3:
                if not otherrecursive:
                    self.recursive = False
                    self.subranges = []
                return self
            # parent below otherparent?
            elif rs==2:
                if not otherrecursive:
                    self.parent = None
                    self.recursive = False
                    self.subranges = []
                return self
            # otherparent below parent
            else:
                if self.recursive:
                    self.parent = otherparent
                    self.recursive = otherrecursive
                    self.subranges = []
                    return self

                self.parent = None

                # go on as if parent was None in the first place
            
        # newsub receives all sub ranges that are below otherparent
        # (these will survive)
        newsub = []
        for sr in self.subranges:
            rs = self._rangeRelationship(sr.parent, otherparent)
            # sr parent == otherparent?
            if rs==3:
                if not otherrecursive:
                    sr.subranges = []
                    sr.recursive = False
                return sr
            # otherparent below sr.parent?
            elif rs==1:
                return sr._simpleIntersect(simplerange)
            # sr.parent below otherparent?
            elif rs==2:
                if otherrecursive:
                    newsub.append(sr)

        self.subranges = newsub
        return self

    # union
    def union(self, other):
        """Return the union of self and other.

        Update the current tree and return the new root.
        
        @param other: Another TreeRange object
        @type other: TreeRange
        @returns: The new root node.
        @rtype: TreeRange
        """
        res = self
        for rng in other.iterRanges():
            res = res._simpleUnion(rng)

        return res
    
    def _simpleUnion(self, simplerange):
        """Return the union of self and a simple range.

        Update the current tree and return the new root.
        
        @param simplerange: A simple range (parent, recursive).
        @type simplerange: 2-tuple
        @returns: The new root node.
        @rtype: TreeRange
        """
        otherparent, otherrecursive = simplerange

        if self.parent!=None:
            rs = self._rangeRelationship(self.parent, otherparent)
            # disjoint?
            if rs==0:
                otherrange = TreeRange(otherparent, otherrecursive, [])
                root = TreeRange(None, False, [self, otherrange])
                return root
            # otherparent==parent?
            elif rs==3:
                if otherrecursive:
                    self.recursive = True
                    self.subranges = []
                return self
            # parent below otherparent?
            elif rs==2:
                if otherrecursive:
                    self.parent = otherparent
                    self.recursive = True
                    self.subranges = []
                    return self
                else:
                    rng = TreeRange(otherparent, False, [self])
                    return rng
            # otherparent below parent
            else:
                # Are we already recursive? Then self already contains other...
                if self.recursive:
                    return self
                
            # if we get here, otherparent is below parent and self is not
            # recursive. This is treated as if parent was None

        # newsub receives all sub ranges that are below otherparent
        # (these will become the new sub range of other)
        newsub = []
        for i,sr in enumerate(self.subranges):
            rs = self._rangeRelationship(sr.parent, otherparent)
            # sr parent == otherparent?
            if rs==3:
                if otherrecursive:
                    sr.recursive = True
                    sr.subranges = []
                return self
            # otherparent below sr.parent?
            elif rs==1:
                del self.subranges[i]
                newsr = sr._simpleUnion(simplerange)
                # if a new TreeRange with empty parent was created, then
                # pull the subranges to this level
                if newsr.parent==None:
                    self.subranges.extend(newsr.subranges)
                else:
                    self.subranges.append(newsr)
                return self
            # sr.parent below otherparent?
            elif rs==2:
                newsub.append(sr)

        # other will become a new sub range
        rng = TreeRange(otherparent, otherrecursive, [])

        # Was other above some previous sub ranges? Then move those sub ranges
        # below other...
        if len(newsub)>0:
            for sr in newsub:
                self.subranges.remove(sr)
            rng.subranges = newsub

        self.subranges.append(rng)
        return self


    def _rangeRelationship(self, parent1, parent2):
        """Determines the relationship between two nodes.
        
        @returns: Returns the relationship as an integer value:
           - 0: The sub trees rooted at parent1 and parent2 are disjoint
           - 1: parent2 is below parent1
           - 2: parent1 is below parent2
           - 3: parent1 and parent2 are the same
        @rtype: int
        """
        path1 = self._rootPath(parent1)
        path2 = self._rootPath(parent2)
        res = 0
        if parent1 in path2:
            res |= 0x01
        if parent2 in path1:
            res |= 0x02
        return res

    def _rootPath(self, node):
        """Returns a list with all nodes from node to the root (including node).

        @precondition: node must have a parent attribute
        @returns: Returns a list of nodes
        @rtype: list
        """
        res = []
        while node!=None:
            res.append(node)
            node = node.parent
        return res

######################################################################

if __name__=="__main__":

    class DummyNode:
        def __init__(self, id, parent=None):
            self.id = id
            self.parent = parent
            self.declarations = []
            if parent!=None:
                self.parent.declarations.append(self)

        def __str__(self):
            return "<Node %d>"%self.id

    root = DummyNode(0)
    n1 = DummyNode(1, root)
    n2 = DummyNode(2, n1)
    n3 = DummyNode(3, n1)
    n4 = DummyNode(4, root)
    n5 = DummyNode(5, n4)
    n6 = DummyNode(6, n2)

    tr = TreeRange(root, False)
    tr = tr.union((n4,True))
    print tr
    for r in tr.iterRanges():
        print r
    for n in tr:
        print n

Index: filters.py
===================================================================
RCS file: /cvsroot/pygccxml/source/pyplusplus/experimental/filters.py,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** filters.py	14 Mar 2006 18:08:57 -0000	1.2
--- filters.py	14 Mar 2006 22:48:53 -0000	1.3
***************
*** 12,15 ****
--- 12,16 ----
  from pygccxml.declarations import *
  from decltypes import *
+ from treerange import TreeRange
  
  # _StringMatcher
***************
*** 78,84 ****
--- 79,97 ----
          return OrFilter([self, other])
  
+     def filterRange(self):
+         """Return the range of the filter.
+ 
+         A return value of none means the filter's range is unlimited.
+ 
+         @returns: Filter range or None
+         @rtype: TreeRange
+         """
+         return None
+         
      def parentConstraints(self):
          """Return the parent constraints.
  
+         *** obsolete ***
+ 
          A filter can use this method to indicate that it will always
          return False if the parent is not a particular node.
***************
*** 138,169 ****
          return True
  
!     def parentConstraints(self):
!         parent = None
!         recursive = None
          for f in self.filters:
!             res = f.parentConstraints()
!             # No constraints? Then go on with the next filter...
!             if res==None:
!                 continue
!             # One individual filter always fails?
!             # Then this filter fails as well...
!             if res==[]:
!                 return []
!             # Check if the individual constraints are conflicting...
!             for p,r in res:
!                 if parent==None:
!                     parent = p
!                     recursive = r
                  else:
!                     if p==parent:
!                         # recursive only remains True if r is also True
!                         recursive = recursive & r
!                     else:
!                         # Two different parents => This filter will always fail
!                         return []
!         if parent==None:
!             return None
!         else:
!             return [parent, recursive]
  
  # OrFilter
--- 151,165 ----
          return True
  
!     def filterRange(self):
!         res = None
          for f in self.filters:
!             rng = f.filterRange()
!             if rng!=None:
!                 if res==None:
!                     res = rng
                  else:
!                     res = res.intersect(rng)
!         return res
! 
  
  # OrFilter
***************
*** 184,207 ****
          return False
  
!     def parentConstraints(self):
!         remove = []
!         constraints = []
          for f in self.filters:
!             res = f.parentConstraints()
!             if res==[]:
!                 remove.append(f)
!                 continue
!             if res!=None:
!                 constraints.extend(res)
! 
!         # Remove all filters that always return False
!         for f in remove:
!             self.filters.remove(f)
! 
!         if constraints==[]:
!             return None
!         else:
!             return constraints
!             
  
  # NotFilter
--- 180,195 ----
          return False
  
!     def filterRange(self):
!         res = None
          for f in self.filters:
!             rng = f.filterRange()
!             if rng==None:
!                 return None
!             if res==None:
!                 res = rng
!             else:
!                 res = res.union(rng)
!         return res
!            
  
  # NotFilter
***************
*** 219,222 ****
--- 207,215 ----
          return not self.filter(decl)
  
+     def filterRange(self):
+         # TreeRange does not support a NOT operation, so extend the
+         # range to full range
+         return None
+ 
  
  # NameFilter
***************
*** 250,253 ****
--- 243,264 ----
          return self.matcher.match(full_name(decl))
  
+ # ParentFilter
+ class ParentFilter(FilterBase):
+     """Filter by parent node.
+     """
+     def __init__(self, parent, grandparents=False):
+         FilterBase.__init__(self)
+         self.parent = parent
+         self.recursive = grandparents
+ 
+     def __str__(self):
+         return "parent=='%s'"%self.parent.name
+ 
+     def __call__(self, decl):
+         return decl.parent==self.parent
+ 
+     def filterRange(self):
+         return TreeRange(self.parent, self.recursive)
+ 
  # RetValFilter
  class RetValFilter(FilterBase):

Index: selection.py
===================================================================
RCS file: /cvsroot/pygccxml/source/pyplusplus/experimental/selection.py,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** selection.py	14 Mar 2006 18:06:43 -0000	1.2
--- selection.py	14 Mar 2006 22:48:53 -0000	1.3
***************
*** 9,65 ****
  """
  
! # iterdecls
! def iterdecls(rootdecl, recursive=True):
!    """Depth first iteration over one or more declaration trees.
!    rootdecl can be either a single declaration, a list of declarations
!    or None. A declaration must be an object derived from the declaration_t
!    class.
!    """
!    if rootdecl==None:
!       return
! 
!    if type(rootdecl) is not list:
!       rootdecl = [rootdecl]
! 
!    for root in rootdecl:
!       yield root
!       if recursive:
!          children = getattr(root, "declarations", None)
!          for node in iterdecls(children):
!             yield node
  
  # select
  def select(root, filter):
!    """Select declarations based on a filter function.
  
!    filter must accept a declaration as argument and return a boolean
!    indicating whether the declaration matches the filter or not.
  
!    @param root: Root of the declaration tree
!    @type root: declaration_t
!    @param filter: A filter that either accepts or rejects a declaration
!    @type filter: callable
!    """
  
!    parents = None
!    # First check for the parentConstraints() method so that also
!    # regular functions can be passed
!    if hasattr(filter, "parentConstraints"):
!        parents = filter.parentConstraints()
!        # Does the filter always return False?
!        if parents==[]:
!            return []
  
!    # No constraints on the parent? Then use the root and walk the entire tree
!    if parents==None:
!        parents = [(root, True)]
  
!    res = []
!    for parent,recursive in parents:
!        for decl in iterdecls(parent):
!            if filter(decl):
!                res.append(decl)
  
!    return res
  
  
--- 9,49 ----
  """
  
! from treerange import TreeRange
  
  # select
  def select(root, filter):
!     """Select declarations based on a filter function.
  
!     filter must accept a declaration as argument and return a boolean
!     indicating whether the declaration matches the filter or not.
  
!     @param root: The node(s) under which to search
!     @type root: declaration_t or list of declaration_t
!     @param filter: A filter that either accepts or rejects a declaration
!     @type filter: callable
!     """
  
!     if type(root)!=list:
!         root = [root]
  
!     rng = TreeRange(root[0],True)
!     for node in root[1:]:
!         rng = rng.union(TreeRange(node,True))
  
!     parents = None
!     # First check for the filterRange() method so that also
!     # regular functions can be passed
!     if hasattr(filter, "filterRange"):
!         frng = filter.filterRange()
!         if frng!=None:
!             rng = rng.intersect(frng)
  
!     # Match the declarations...
!     res = []
!     for decl in rng:
!         if filter(decl):
!             res.append(decl)
! 
!     return res
  
  

Index: declwrapper.py
===================================================================
RCS file: /cvsroot/pygccxml/source/pyplusplus/experimental/declwrapper.py,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** declwrapper.py	14 Mar 2006 18:10:48 -0000	1.2
--- declwrapper.py	14 Mar 2006 22:48:53 -0000	1.3
***************
*** 391,398 ****
              decls = []
          else:
!             if len(self.decl_handles)!=1:
!                 print "***WARNING***: len(decl_handles) != 1"
!             root = self.decl_handles[0]
!             decls = selection.select(root, filter)
          
          res = IDecl(decls)
--- 391,395 ----
              decls = []
          else:
!             decls = selection.select(self.decl_handles, filter)
          
          res = IDecl(decls)