This file is indexed.

/usr/lib/python3/dist-packages/urwidtrees/tree.py is in python3-urwidtrees 1.0.1.1-1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
# Copyright (C) 2013  Patrick Totzke <patricktotzke@gmail.com>
# This file is released under the GNU GPL, version 3 or a later revision.

import logging


class Tree(object):
    """
    Base class for a tree strucures that can be displayed by :class:`TreeBox`
    widgets. An instance defines a structure by defining local transformations
    on positions. That is, by overwriting

     * `next_sibling_position`
     * `prev_sibling_position`
     * `parent_position`
     * `first_child_position`
     * `last_child_position`

    that compute the next position in the respective direction. Also, they need
    to implement method `__getitem__` that returns a :class:`Widget` for a
    given position.

    The type of objects used as positions may vary in subclasses and is
    deliberately unspecified for the base class.

    This base class already implements methods based on the local
    transformations above. These include :meth:`depth`, :meth:`last_decendant`
    and :meth:`[next|prev]_position <next_position>` that computes
    next/previous positions in depth-first order.
    """
    root = None

    # local helper
    def _get(self, pos):
        """loads widget at given position; handling invalid arguments"""
        res = None, None
        if pos is not None:
            try:
                res = self[pos], pos
            except (IndexError, KeyError):
                pass
        return res

    def _next_of_kin(self, pos):
        """
        looks up the next sibling of the closest ancestor with not-None next
        siblings.
        """
        candidate = None
        parent = self.parent_position(pos)
        if parent is not None:
            candidate = self.next_sibling_position(parent)
            if candidate is None:
                candidate = self._next_of_kin(parent)
        return candidate

    def _last_in_direction(self, starting_pos, direction):
        """
        move in the tree in given direction and return the last position.

        :param starting_pos: position to start at
        :param direction: callable that transforms a position into a position.
        """
        cur_pos = None
        next_pos = starting_pos
        while next_pos is not None:
            cur_pos = next_pos
            next_pos = direction(cur_pos)
        return cur_pos

    def depth(self, pos):
        """determine depth of node at pos"""
        parent = self.parent_position(pos)
        if parent is None:
            return 0
        else:
            return self.depth(parent) + 1

    def is_leaf(self, pos):
        """checks if given position has no children"""
        return self.first_child_position(pos) is None

    def first_ancestor(self, pos):
        """
        position of pos's ancestor with depth 0. Usually, this should return
        the root node, but a :class:`Tree` might represent a forrest - have
        multiple nodes without parent.
        """
        return self._last_in_direction(pos, self.parent_position)

    def last_decendant(self, pos):
        """position of last (in DFO) decendant of pos"""
        return self._last_in_direction(pos, self.last_child_position)

    def last_sibling_position(self, pos):
        """position of last sibling of pos"""
        return self._last_in_direction(pos, self.next_sibling_position)

    def first_sibling_position(self, pos):
        """position of first sibling of pos"""
        return self._last_in_direction(pos, self.prev_sibling_position)

    def next_position(self, pos):
        """returns the next position in depth-first order"""
        candidate = None
        if pos is not None:
            candidate = self.first_child_position(pos)
            if candidate is None:
                candidate = self.next_sibling_position(pos)
                if candidate is None:
                    candidate = self._next_of_kin(pos)
        return candidate

    def prev_position(self, pos):
        """returns the previous position in depth-first order"""
        candidate = None
        if pos is not None:
            prevsib = self.prev_sibling_position(pos)  # is None if first
            if prevsib is not None:
                candidate = self.last_decendant(prevsib)
            else:
                parent = self.parent_position(pos)
                if parent is not None:
                    candidate = parent
        return candidate

    def positions(self, reverse=False):
        """returns a generator that walks the positions of this tree in DFO"""
        def Posgen(reverse):
            if reverse:
                lastrootsib = self.last_sibling_position(self.root)
                current = self.last_decendant(lastrootsib)
                while current is not None:
                    yield current
                    current = self.prev_position(current)
            else:
                current = self.root
                while current is not None:
                    yield current
                    current = self.next_position(current)
        return Posgen(reverse)

    ####################################################################
    # End of high-level helper implementation. The following need to be
    # overwritten by subclasses
    ####################################################################
    def parent_position(self, pos):
        """returns the position of the parent node of the node at `pos`
        or `None` if none exists."""
        return None

    def first_child_position(self, pos):
        """returns the position of the first child of the node at `pos`,
        or `None` if none exists."""
        return None

    def last_child_position(self, pos):
        """returns the position of the last child of the node at `pos`,
        or `None` if none exists."""
        return None

    def next_sibling_position(self, pos):
        """returns the position of the next sibling of the node at `pos`,
        or `None` if none exists."""
        return None

    def prev_sibling_position(self, pos):
        """returns the position of the previous sibling of the node at `pos`,
        or `None` if none exists."""
        return None


class SimpleTree(Tree):
    """
    Walks on a given fixed acyclic structure given as a list of nodes; every
    node is a tuple `(content, children)`, where `content` is a `urwid.Widget`
    to be displayed at that position and `children` is either `None` or a list
    of nodes.

    Positions are lists of integers determining a path from the root node with
    position `(0,)`.
    """
    def __init__(self, treelist):
        self._treelist = treelist
        self.root = (0,) if treelist else None
        Tree.__init__(self)

    # a few local helper methods
    def _get_substructure(self, treelist, pos):
        """recursive helper to look up node-tuple for `pos` in `treelist`"""
        subtree = None
        if len(pos) > 1:
            subtree = self._get_substructure(treelist[pos[0]][1], pos[1:])
        else:
            try:
                subtree = treelist[pos[0]]
            except (IndexError, TypeError):
                pass
        return subtree

    def _get_node(self, treelist, pos):
        """
        look up widget at `pos` of `treelist`; default to None if
        nonexistent.
        """
        node = None
        if pos is not None:
            subtree = self._get_substructure(treelist, pos)
            if subtree is not None:
                node = subtree[0]
        return node

    def _confirm_pos(self, pos):
        """look up widget for pos and default to None"""
        candidate = None
        if self._get_node(self._treelist, pos) is not None:
            candidate = pos
        return candidate

    # Tree API
    def __getitem__(self, pos):
        return self._get_node(self._treelist, pos)

    def parent_position(self, pos):
        parent = None
        if pos is not None:
            if len(pos) > 1:
                parent = pos[:-1]
        return parent

    def first_child_position(self, pos):
        return self._confirm_pos(pos + (0,))

    def last_child_position(self, pos):
        candidate = None
        subtree = self._get_substructure(self._treelist, pos)
        if subtree is not None:
            children = subtree[1]
            if children is not None:
                candidate = pos + (len(children) - 1,)
        return candidate

    def next_sibling_position(self, pos):
        return self._confirm_pos(pos[:-1] + (pos[-1] + 1,))

    def prev_sibling_position(self, pos):
        return pos[:-1] + (pos[-1] - 1,) if (pos[-1] > 0) else None

    # optimizations
    def depth(self, pos):
        """more performant implementation due to specific structure of pos"""
        return len(pos) - 1