3956162881

Build Type

push

github

Committed by Michael Howitz

Commit Message

Update to deprecation warning free releases.

Run Details

4401 of 7036 branches covered (62.55%)

Branch coverage included in aggregate %.

27161 of 31488 relevant lines covered (86.26%)

0.86 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

87.55

/src/ZTUtils/Tree.py

##############################################################################
#
# Copyright (c) 2002 Zope Foundation and Contributors.
#
# This software is subject to the provisions of the Zope Public License,
# Version 2.1 (ZPL).  A copy of the ZPL should accompany this distribution.
# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
# FOR A PARTICULAR PURPOSE
#
##############################################################################
"""Tree manipulation classes
"""

import base64
import zlib

from Acquisition import Explicit
from ComputedAttribute import ComputedAttribute


class TreeNode(Explicit):
    __allow_access_to_unprotected_subobjects__ = 1
    state = 0  # leaf
    height = 1
    size = 1

    def __init__(self):
        self._child_list = []

    def _add_child(self, child):
        'Add a child which already has all of its children.'
        self._child_list.append(child)
        self.height = max(self.height, child.height + 1)
        self.size = self.size + child.size

    def flat(self):
        'Return a flattened preorder list of tree nodes'
        items = []
        self.walk(items.append)
        return items

    def walk(self, f, data=None):
        'Preorder walk this tree, passing each node to a function'
        if data is None:
            f(self)
        else:
            f(self, data)
        for child in self._child_list:
            child.__of__(self).walk(f, data)

    def _depth(self):
        return self.__parent__.depth + 1

    depth = ComputedAttribute(_depth, 1)

    def __getitem__(self, index):
        return self._child_list[index].__of__(self)

    def __len__(self):
        return len(self._child_list)


_marker = []


class TreeMaker:
    '''Class for mapping a hierarchy of objects into a tree of nodes.'''

    __allow_access_to_unprotected_subobjects__ = 1

    _id = 'tpId'
    _assume_children = False
    _expand_root = True
    _values = 'tpValues'
    _values_filter = None
    _values_function = None
    _state_function = None

    _cached_children = None

    def setIdAttr(self, id):
        """Set the attribute or method name called to get a unique Id.

        The id attribute or method is used to get a unique id for every
        node in the tree, so that the state of the tree can be encoded
        as a string using Tree.encodeExpansion(). The returned id should
        be unique and stable across Zope requests.

        If the attribute or method isn't found on an object, either
        the objects persistence Id or the result of id() on the object
        is used instead.
        """
        self._id = id

    def setExpandRoot(self, expand):
        """Set wether or not to expand the root node by default.

        When no expanded flag or mapping is passed to .tree(), assume the root
        node is expanded, and leave all subnodes closed.

        The default is to expand the root node.
        """
        self._expand_root = expand and True or False

    def setAssumeChildren(self, assume):
        """Set wether or not to assume nodes have children.

        When a node is not expanded, when assume children is set, don't
        determine if it is a leaf node, but assume it can be opened. Use this
        when determining the children for a node is expensive.

        The default is to not assume there are children.
        """
        self._assume_children = assume and True or False

    def setChildAccess(self, attrname=_marker, filter=_marker,
                       function=_marker):
        '''Set the criteria for fetching child nodes.

        Child nodes can be accessed through either an attribute name
        or callback function.  Children fetched by attribute name can
        be filtered through a callback function.
        '''
        if function is _marker:
            self._values_function = None
            if attrname is not _marker:
                self._values = str(attrname)
            if filter is not _marker:
                self._values_filter = filter
        else:
            self._values_function = function

    def setStateFunction(self, function):
        """Set the expansion state function.

        This function will be called to determine if a node should be open or
        collapsed, or should be treated as a leaf node. The function is passed
        the current object, and the intended state for that object. It should
        return the actual state the object should be in. State is encoded as an
        integer, meaning:

            -1: Node closed. Children will not be processed.
             0: Leaf node, cannot be opened or closed, no children are
                processed.
             1: Node opened. Children will be processed as part of the tree.
        """
        self._state_function = function

    def getId(self, object):
        id_attr = self._id
        if hasattr(object, id_attr):
            obid = getattr(object, id_attr)
            if not simple_type(obid):
                obid = obid()
            return obid
        if hasattr(object, '_p_oid'):
            return str(object._p_oid)
        return id(object)

    def node(self, object):
        node = TreeNode()
        node.object = object
        node.id = b2a(self.getId(object))
        return node

    def hasChildren(self, object):
        if self._assume_children:
            return 1
        # Cache generated children for a subsequent call to getChildren
        self._cached_children = (object, self.getChildren(object))
        return not not self._cached_children[1]

    def filterChildren(self, children):
        if self._values_filter:
            return self._values_filter(children)
        return children

    def getChildren(self, object):
        # Check and clear cache first
        if self._cached_children is not None:
            ob, children = self._cached_children
            self._cached_children = None
            if ob is object:
                return children

        if self._values_function is not None:
            return self._values_function(object)

        children = getattr(object, self._values)
        if not isinstance(children, (list, tuple)):
            # Assume callable; result not useful anyway otherwise.
            children = children()

        return self.filterChildren(children)

    def tree(self, root, expanded=None, subtree=0):
        '''Create a tree from root, with specified nodes expanded.

        "expanded" must be false, true, or a mapping.
        Each key of the mapping is the id of a top-level expanded
        node, and each value is the "expanded" value for the
        children of that node.
        '''
        node = self.node(root)
        child_exp = expanded
        if not simple_type(expanded):
            # Assume a mapping
            expanded = node.id in expanded
            child_exp = child_exp.get(node.id)

        expanded = expanded or (not subtree and self._expand_root)
        # Set state to 0 (leaf), 1 (opened), or -1 (closed)
        state = self.hasChildren(root) and (expanded or -1)
        if self._state_function is not None:
            state = self._state_function(node.object, state)
        node.state = state
        if state > 0:
            for child in self.getChildren(root):
                node._add_child(self.tree(child, child_exp, 1))

        if not subtree:
            node.depth = 0
        return node


_SIMPLE_TYPES = {type(''), type(b''), type(0), type(0.0), type(None)}


def simple_type(ob):
    return type(ob) in _SIMPLE_TYPES


def b2a(s):
    '''Encode a bytes/string as a cookie- and url-safe string.

    Encoded string use only alphanumeric characters, and "._-".
    '''
    if not isinstance(s, bytes):
        s = str(s)
        if isinstance(s, str):
            s = s.encode('utf-8')
    return base64.urlsafe_b64encode(s)


def a2b(s):
    '''Decode a b2a-encoded value to bytes.'''
    if not isinstance(s, bytes):
        if isinstance(s, str):
            s = s.encode('ascii')
    return base64.urlsafe_b64decode(s)


def encodeExpansion(nodes, compress=1):
    '''Encode the expanded node ids of a tree into bytes.

    Accepts a list of nodes, such as that produced by root.flat().
    Marks each expanded node with an expansion_number attribute.
    Since node ids are encoded, the resulting string is safe for
    use in cookies and URLs.
    '''
    steps = []
    last_depth = -1
    for n, node in enumerate(nodes):
        if node.state <= 0:
            continue
        dd = last_depth - node.depth + 1
        last_depth = node.depth
        if dd > 0:
            steps.append('_' * dd)
        steps.append(node.id)  # id is bytes
        node.expansion_number = n
    result = b':'.join(steps)
    if compress and len(result) > 2:
        zresult = b':' + b2a(zlib.compress(result, 9))
        if len(zresult) < len(result):
            result = zresult
    return result


def decodeExpansion(s, nth=None, maxsize=8192):
    '''Decode an expanded node map from bytes.

    If nth is an integer, also return the (map, key) pair for the nth entry.
    '''
    if len(s) > maxsize:  # Set limit to avoid DoS attacks.
        raise ValueError('Encoded node map too large')

    if s.startswith(b':'):  # Compressed state
        dec = zlib.decompressobj()
        s = dec.decompress(a2b(s[1:]), maxsize)
        if dec.unconsumed_tail:
            raise ValueError('Encoded node map too large')
        del dec

    map = m = {}
    mstack = []
    pop = 0
    nth_pair = None
    if nth is not None:
        nth_pair = (None, None)
    obid = None
    for step in s.split(b':'):
        if step.startswith(b'_'):
            pop = len(step) - 1
            continue
        if pop < 0:
            mstack.append(m)
            m[obid] = {}
            m = m[obid]
        elif map:
            m[obid] = None
        if len(step) == 0:
            return map
        obid = step
        if pop > 0:
            m = mstack[-pop]
            del mstack[-pop:]
        pop = -1
        if nth == 0:
            nth_pair = (m, obid)
            nth = None
        elif nth is not None:
            nth = nth - 1
    m[obid] = None
    if nth == 0:
        return map, (m, obid)
    if nth_pair is not None:
        return map, nth_pair
    return map

1	##############################################################################
2	#
3	# Copyright (c) 2002 Zope Foundation and Contributors.
4	#
5	# This software is subject to the provisions of the Zope Public License,
6	# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
7	# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
8	# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
9	# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
10	# FOR A PARTICULAR PURPOSE
11	#
12	##############################################################################
13	"""Tree manipulation classes	1✔
14	"""
15
16	import base64	1✔
17	import zlib	1✔
18
19	from Acquisition import Explicit	1✔
20	from ComputedAttribute import ComputedAttribute	1✔
21
22
23	class TreeNode(Explicit):	1✔
24	__allow_access_to_unprotected_subobjects__ = 1	1✔
25	state = 0 # leaf	1✔
26	height = 1	1✔
27	size = 1	1✔
28
29	def __init__(self):	1✔
30	self._child_list = []	1✔
31
32	def _add_child(self, child):	1✔
33	'Add a child which already has all of its children.'
34	self._child_list.append(child)	1✔
35	self.height = max(self.height, child.height + 1)	1✔
36	self.size = self.size + child.size	1✔
37
38	def flat(self):	1✔
39	'Return a flattened preorder list of tree nodes'
40	items = []	1✔
41	self.walk(items.append)	1✔
42	return items	1✔
43
44	def walk(self, f, data=None):	1✔
45	'Preorder walk this tree, passing each node to a function'
46	if data is None:	1✔
47	f(self)	1✔
48	else:
49	f(self, data)	1✔
50	for child in self._child_list:	1✔
51	child.__of__(self).walk(f, data)	1✔
52
53	def _depth(self):	1✔
54	return self.__parent__.depth + 1	1✔
55
56	depth = ComputedAttribute(_depth, 1)	1✔
57
58	def __getitem__(self, index):	1✔
59	return self._child_list[index].__of__(self)	1✔
60
61	def __len__(self):	1✔
62	return len(self._child_list)	1✔
63
64
65	_marker = []	1✔
66
67
68	class TreeMaker:	1✔
69	'''Class for mapping a hierarchy of objects into a tree of nodes.'''
70
71	__allow_access_to_unprotected_subobjects__ = 1	1✔
72
73	_id = 'tpId'	1✔
74	_assume_children = False	1✔
75	_expand_root = True	1✔
76	_values = 'tpValues'	1✔
77	_values_filter = None	1✔
78	_values_function = None	1✔
79	_state_function = None	1✔
80
81	_cached_children = None	1✔
82
83	def setIdAttr(self, id):	1✔
84	"""Set the attribute or method name called to get a unique Id.
85
86	The id attribute or method is used to get a unique id for every
87	node in the tree, so that the state of the tree can be encoded
88	as a string using Tree.encodeExpansion(). The returned id should
89	be unique and stable across Zope requests.
90
91	If the attribute or method isn't found on an object, either
92	the objects persistence Id or the result of id() on the object
93	is used instead.
94	"""
95	self._id = id	1✔
96
97	def setExpandRoot(self, expand):	1✔
98	"""Set wether or not to expand the root node by default.
99
100	When no expanded flag or mapping is passed to .tree(), assume the root
101	node is expanded, and leave all subnodes closed.
102
103	The default is to expand the root node.
104	"""
105	self._expand_root = expand and True or False	1✔
106
107	def setAssumeChildren(self, assume):	1✔
108	"""Set wether or not to assume nodes have children.
109
110	When a node is not expanded, when assume children is set, don't
111	determine if it is a leaf node, but assume it can be opened. Use this
112	when determining the children for a node is expensive.
113
114	The default is to not assume there are children.
115	"""
116	self._assume_children = assume and True or False	1✔
117
118	def setChildAccess(self, attrname=_marker, filter=_marker,	1✔
119	function=_marker):
120	'''Set the criteria for fetching child nodes.
121
122	Child nodes can be accessed through either an attribute name
123	or callback function. Children fetched by attribute name can
124	be filtered through a callback function.
125	'''
126	if function is _marker:	1✔
127	self._values_function = None	1✔
128	if attrname is not _marker:	1✔
129	self._values = str(attrname)	1✔
130	if filter is not _marker:	1✔
131	self._values_filter = filter	1✔
132	else:
133	self._values_function = function	1✔
134
135	def setStateFunction(self, function):	1✔
136	"""Set the expansion state function.
137
138	This function will be called to determine if a node should be open or
139	collapsed, or should be treated as a leaf node. The function is passed
140	the current object, and the intended state for that object. It should
141	return the actual state the object should be in. State is encoded as an
142	integer, meaning:
143
144	-1: Node closed. Children will not be processed.
145	0: Leaf node, cannot be opened or closed, no children are
146	processed.
147	1: Node opened. Children will be processed as part of the tree.
148	"""
149	self._state_function = function	1✔
150
151	def getId(self, object):	1✔
152	id_attr = self._id	1✔
153	if hasattr(object, id_attr):	1✔
154	obid = getattr(object, id_attr)	1✔
155	if not simple_type(obid):	1✔
156	obid = obid()	1✔
157	return obid	1✔
158	if hasattr(object, '_p_oid'):	1✔
159	return str(object._p_oid)	1✔
160	return id(object)	1✔
161
162	def node(self, object):	1✔
163	node = TreeNode()	1✔
164	node.object = object	1✔
165	node.id = b2a(self.getId(object))	1✔
166	return node	1✔
167
168	def hasChildren(self, object):	1✔
169	if self._assume_children:	1✔
170	return 1	1✔
171	# Cache generated children for a subsequent call to getChildren
172	self._cached_children = (object, self.getChildren(object))	1✔
173	return not not self._cached_children[1]	1✔
174
175	def filterChildren(self, children):	1✔
176	if self._values_filter:	1✔
177	return self._values_filter(children)	1✔
178	return children	1✔
179
180	def getChildren(self, object):	1✔
181	# Check and clear cache first
182	if self._cached_children is not None:	1✔
183	ob, children = self._cached_children	1✔
184	self._cached_children = None	1✔
185	if ob is object:	1✔
186	return children	1✔
187
188	if self._values_function is not None:	1✔
189	return self._values_function(object)	1✔
190
191	children = getattr(object, self._values)	1✔
192	if not isinstance(children, (list, tuple)):	1✔
193	# Assume callable; result not useful anyway otherwise.
194	children = children()	1✔
195
196	return self.filterChildren(children)	1✔
197
198	def tree(self, root, expanded=None, subtree=0):	1✔
199	'''Create a tree from root, with specified nodes expanded.
200
201	"expanded" must be false, true, or a mapping.
202	Each key of the mapping is the id of a top-level expanded
203	node, and each value is the "expanded" value for the
204	children of that node.
205	'''
206	node = self.node(root)	1✔
207	child_exp = expanded	1✔
208	if not simple_type(expanded):	1✔
209	# Assume a mapping
210	expanded = node.id in expanded	1✔
211	child_exp = child_exp.get(node.id)	1✔
212
213	expanded = expanded or (not subtree and self._expand_root)	1✔
214	# Set state to 0 (leaf), 1 (opened), or -1 (closed)
215	state = self.hasChildren(root) and (expanded or -1)	1✔
216	if self._state_function is not None:	1✔
217	state = self._state_function(node.object, state)	1✔
218	node.state = state	1✔
219	if state > 0:	1✔
220	for child in self.getChildren(root):	1✔
221	node._add_child(self.tree(child, child_exp, 1))	1✔
222
223	if not subtree:	1✔
224	node.depth = 0	1✔
225	return node	1✔
226
227
228	_SIMPLE_TYPES = {type(''), type(b''), type(0), type(0.0), type(None)}	1✔
229
230
231	def simple_type(ob):	1✔
232	return type(ob) in _SIMPLE_TYPES	1✔
233
234
235	def b2a(s):	1✔
236	'''Encode a bytes/string as a cookie- and url-safe string.
237
238	Encoded string use only alphanumeric characters, and "._-".
239	'''
240	if not isinstance(s, bytes):	1✔
241	s = str(s)	1✔
242	if isinstance(s, str):	1!
243	s = s.encode('utf-8')	1✔
244	return base64.urlsafe_b64encode(s)	1✔
245
246
247	def a2b(s):	1✔
248	'''Decode a b2a-encoded value to bytes.'''
249	if not isinstance(s, bytes):	1!
250	if isinstance(s, str):	×
251	s = s.encode('ascii')	×
252	return base64.urlsafe_b64decode(s)	1✔
253
254
255	def encodeExpansion(nodes, compress=1):	1✔
256	'''Encode the expanded node ids of a tree into bytes.
257
258	Accepts a list of nodes, such as that produced by root.flat().
259	Marks each expanded node with an expansion_number attribute.
260	Since node ids are encoded, the resulting string is safe for
261	use in cookies and URLs.
262	'''
263	steps = []	1✔
264	last_depth = -1	1✔
265	for n, node in enumerate(nodes):	1✔
266	if node.state <= 0:	1✔
267	continue	1✔
268	dd = last_depth - node.depth + 1	1✔
269	last_depth = node.depth	1✔
270	if dd > 0:	1!
271	steps.append('_' * dd)	×
272	steps.append(node.id) # id is bytes	1✔
273	node.expansion_number = n	1✔
274	result = b':'.join(steps)	1✔
275	if compress and len(result) > 2:	1!
276	zresult = b':' + b2a(zlib.compress(result, 9))	1✔
277	if len(zresult) < len(result):	1!
278	result = zresult	×
279	return result	1✔
280
281
282	def decodeExpansion(s, nth=None, maxsize=8192):	1✔
283	'''Decode an expanded node map from bytes.
284
285	If nth is an integer, also return the (map, key) pair for the nth entry.
286	'''
287	if len(s) > maxsize: # Set limit to avoid DoS attacks.	1✔
288	raise ValueError('Encoded node map too large')	1✔
289
290	if s.startswith(b':'): # Compressed state	1✔
291	dec = zlib.decompressobj()	1✔
292	s = dec.decompress(a2b(s[1:]), maxsize)	1✔
293	if dec.unconsumed_tail:	1!
294	raise ValueError('Encoded node map too large')	1✔
295	del dec	×
296
297	map = m = {}	1✔
298	mstack = []	1✔
299	pop = 0	1✔
300	nth_pair = None	1✔
301	if nth is not None:	1!
302	nth_pair = (None, None)	×
303	obid = None	1✔
304	for step in s.split(b':'):	1✔
305	if step.startswith(b'_'):	1!
306	pop = len(step) - 1	×
307	continue	×
308	if pop < 0:	1✔
309	mstack.append(m)	1✔
310	m[obid] = {}	1✔
311	m = m[obid]	1✔
312	elif map:	1!
313	m[obid] = None	×
314	if len(step) == 0:	1!
315	return map	×
316	obid = step	1✔
317	if pop > 0:	1!
318	m = mstack[-pop]	×
319	del mstack[-pop:]	×
320	pop = -1	1✔
321	if nth == 0:	1!
322	nth_pair = (m, obid)	×
323	nth = None	×
324	elif nth is not None:	1!
325	nth = nth - 1	×
326	m[obid] = None	1✔
327	if nth == 0:	1!
328	return map, (m, obid)	×
329	if nth_pair is not None:	1!
330	return map, nth_pair	×
331	return map	1✔

zopefoundation / Zope / 3956162881

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous