1# This file is Copyright 2019 Volatility Foundation and licensed under the Volatility Software License 1.0
2# which is available at https://www.volatilityfoundation.org/license/vsl-v1.0
3#
4"""Renderers.
5
6Renderers display the unified output format in some manner (be it text
7or file or graphical output
8"""
9import collections
10import datetime
11from typing import Any, Callable, Iterable, List, Optional, Tuple, TypeVar, Union
12
13from volatility.framework import interfaces
14from volatility.framework.interfaces import renderers
15
16
17class UnreadableValue(interfaces.renderers.BaseAbsentValue):
18    """Class that represents values which are empty because the data cannot be
19    read."""
20
21
22class UnparsableValue(interfaces.renderers.BaseAbsentValue):
23    """Class that represents values which are empty because the data cannot be
24    interpreted correctly."""
25
26
27class NotApplicableValue(interfaces.renderers.BaseAbsentValue):
28    """Class that represents values which are empty because they don't make
29    sense for this node."""
30
31
32class NotAvailableValue(interfaces.renderers.BaseAbsentValue):
33    """Class that represents values which cannot be provided now (but might in
34    a future run)
35
36    This might occur when information packed with volatility (such as
37    symbol information) is not available, but a future version or a
38    different run may later have that information available (ie, it
39    could be applicable, but we can't get it and it's not because it's
40    unreadable or unparsable). Unreadable and Unparsable should be used
41    in preference, and only if neither fits should this be used.
42    """
43
44
45class TreeNode(interfaces.renderers.TreeNode):
46    """Class representing a particular node in a tree grid."""
47
48    def __init__(self, path: str, treegrid: 'TreeGrid', parent: Optional['TreeNode'],
49                 values: List[interfaces.renderers.BaseTypes]) -> None:
50        if not isinstance(treegrid, TreeGrid):
51            raise TypeError("Treegrid must be an instance of TreeGrid")
52        self._treegrid = treegrid
53        self._parent = parent
54        self._path = path
55        self._validate_values(values)
56        self._values = treegrid.RowStructure(*values)  # type: ignore
57
58    def __repr__(self) -> str:
59        return "<TreeNode [{}] - {}>".format(self.path, self._values)
60
61    def __getitem__(self, item: Union[int, slice]) -> Any:
62        return self._treegrid.children(self).__getitem__(item)
63
64    def __len__(self) -> int:
65        return len(self._treegrid.children(self))
66
67    def _validate_values(self, values: List[interfaces.renderers.BaseTypes]) -> None:
68        """A function for raising exceptions if a given set of values is
69        invalid according to the column properties."""
70        if not (isinstance(values, collections.Sequence) and len(values) == len(self._treegrid.columns)):
71            raise TypeError(
72                "Values must be a list of objects made up of simple types and number the same as the columns")
73        for index in range(len(self._treegrid.columns)):
74            column = self._treegrid.columns[index]
75            val = values[index]
76            if not isinstance(val, (column.type, interfaces.renderers.BaseAbsentValue)):
77                raise TypeError(
78                    "Values item with index {} is the wrong type for column {} (got {} but expected {})".format(
79                        index, column.name, type(val), column.type))
80            # TODO: Consider how to deal with timezone naive/aware datetimes (and alert plugin uses to be precise)
81            # if isinstance(val, datetime.datetime):
82            #     tznaive = val.tzinfo is None or val.tzinfo.utcoffset(val) is None
83
84    @property
85    def values(self) -> Iterable[interfaces.renderers.BaseTypes]:
86        """Returns the list of values from the particular node, based on column
87        index."""
88        return self._values
89
90    @property
91    def path(self) -> str:
92        """Returns a path identifying string.
93
94        This should be seen as opaque by external classes, Parsing of
95        path locations based on this string are not guaranteed to remain
96        stable.
97        """
98        return self._path
99
100    @property
101    def parent(self) -> Optional['TreeNode']:
102        """Returns the parent node of this node or None."""
103        return self._parent
104
105    @property
106    def path_depth(self) -> int:
107        """Return the path depth of the current node."""
108        return len(self.path.split(TreeGrid.path_sep))
109
110    def path_changed(self, path: str, added: bool = False) -> None:
111        """Updates the path based on the addition or removal of a node higher
112        up in the tree.
113
114        This should only be called by the containing TreeGrid and
115        expects to only be called for affected nodes.
116        """
117        components = self._path.split(TreeGrid.path_sep)
118        changed = path.split(TreeGrid.path_sep)
119        changed_index = len(changed) - 1
120        if int(components[changed_index]) >= int(changed[-1]):
121            components[changed_index] = str(int(components[changed_index]) + (1 if added else -1))
122        self._path = TreeGrid.path_sep.join(components)
123
124
125class TreeGrid(interfaces.renderers.TreeGrid):
126    """Class providing the interface for a TreeGrid (which contains TreeNodes)
127
128    The structure of a TreeGrid is designed to maintain the structure of the tree in a single object.
129    For this reason each TreeNode does not hold its children, they are managed by the top level object.
130    This leaves the Nodes as simple data carries and prevents them being used to manipulate the tree as a whole.
131    This is a data structure, and is not expected to be modified much once created.
132
133    Carrying the children under the parent makes recursion easier, but then every node is its own little tree
134    and must have all the supporting tree functions.  It also allows for a node to be present in several different trees,
135    and to create cycles.
136    """
137
138    path_sep = "|"
139
140    def __init__(self, columns: List[Tuple[str, interfaces.renderers.BaseTypes]],
141                 generator: Optional[Iterable[Tuple[int, Tuple]]]) -> None:
142        """Constructs a TreeGrid object using a specific set of columns.
143
144        The TreeGrid itself is a root element, that can have children but no values.
145        The TreeGrid does *not* contain any information about formatting,
146        these are up to the renderers and plugins.
147
148        Args:
149            columns: A list of column tuples made up of (name, type).
150            generator: An iterable containing row for a tree grid, each row contains a indent level followed by the values for each column in order.
151        """
152        self._populated = False
153        self._row_count = 0
154        self._children = []  # type: List[TreeNode]
155        converted_columns = []  # type: List[interfaces.renderers.Column]
156        if len(columns) < 1:
157            raise ValueError("Columns must be a list containing at least one column")
158        for (name, column_type) in columns:
159            is_simple_type = issubclass(column_type, self.base_types)
160            if not is_simple_type:
161                raise TypeError("Column {}'s type is not a simple type: {}".format(name,
162                                                                                   column_type.__class__.__name__))
163            converted_columns.append(interfaces.renderers.Column(name, column_type))
164        self.RowStructure = collections.namedtuple("RowStructure",
165                                                   [self.sanitize_name(column.name) for column in converted_columns])
166        self._columns = converted_columns
167        if generator is None:
168            generator = []
169        generator = iter(generator)
170
171        self._generator = generator
172
173    @staticmethod
174    def sanitize_name(text: str) -> str:
175        output = ""
176        for letter in text.lower():
177            if letter != ' ':
178                output += (letter if letter in 'abcdefghiljklmnopqrstuvwxyz_0123456789' else '_')
179        return output
180
181    def populate(self, function: interfaces.renderers.VisitorSignature = None, initial_accumulator: Any = None) -> None:
182        """Populates the tree by consuming the TreeGrid's construction
183        generator Func is called on every node, so can be used to create output
184        on demand.
185
186        This is equivalent to a one-time visit.
187        """
188        accumulator = initial_accumulator
189        if function is None:
190
191            def function(_x: interfaces.renderers.TreeNode, _y: Any) -> Any:
192                return None
193
194        if not self.populated:
195            prev_nodes = []  # type: List[TreeNode]
196            for (level, item) in self._generator:
197                parent_index = min(len(prev_nodes), level)
198                parent = prev_nodes[parent_index - 1] if parent_index > 0 else None
199                treenode = self._append(parent, item)
200                prev_nodes = prev_nodes[0:parent_index] + [treenode]
201                if function is not None:
202                    accumulator = function(treenode, accumulator)
203                self._row_count += 1
204        self._populated = True
205
206    @property
207    def populated(self):
208        """Indicates that population has completed and the tree may now be
209        manipulated separately."""
210        return self._populated
211
212    @property
213    def columns(self) -> List[interfaces.renderers.Column]:
214        """Returns the available columns and their ordering and types."""
215        return self._columns
216
217    @property
218    def row_count(self) -> int:
219        """Returns the number of rows populated."""
220        return self._row_count
221
222    def children(self, node) -> List[interfaces.renderers.TreeNode]:
223        """Returns the subnodes of a particular node in order."""
224        return [node for node, _ in self._find_children(node)]
225
226    def _find_children(self, node):
227        """Returns the children list associated with a particular node.
228
229        Returns None if the node does not exist
230        """
231        children = self._children
232        try:
233            if node is not None:
234                for path_component in node.path.split(self.path_sep):
235                    _, children = children[int(path_component)]
236        except IndexError:
237            return []
238        return children
239
240    def values(self, node):
241        """Returns the values for a particular node.
242
243        The values returned are mutable,
244        """
245        if node is None:
246            raise TypeError("Node must be a valid node within the TreeGrid")
247        return node.values
248
249    def _append(self, parent, values):
250        """Adds a new node at the top level if parent is None, or under the
251        parent node otherwise, after all other children."""
252        children = self.children(parent)
253        return self._insert(parent, len(children), values)
254
255    def _insert(self, parent, position, values):
256        """Inserts an element into the tree at a specific position."""
257        parent_path = ""
258        children = self._find_children(parent)
259        if parent is not None:
260            parent_path = parent.path + self.path_sep
261        newpath = parent_path + str(position)
262        tree_item = TreeNode(newpath, self, parent, values)
263        for node, _ in children[position:]:
264            self.visit(node, lambda child, _: child.path_changed(newpath, True), None)
265        children.insert(position, (tree_item, []))
266        return tree_item
267
268    def is_ancestor(self, node, descendant):
269        """Returns true if descendent is a child, grandchild, etc of node."""
270        return descendant.path.startswith(node.path)
271
272    def max_depth(self):
273        """Returns the maximum depth of the tree."""
274        return self.visit(None, lambda n, a: max(a, self.path_depth(n)), 0)
275
276    _T = TypeVar("_T")
277
278    def visit(self,
279              node: Optional[interfaces.renderers.TreeNode],
280              function: Callable[[interfaces.renderers.TreeNode, _T], _T],
281              initial_accumulator: _T,
282              sort_key: Optional[interfaces.renderers.ColumnSortKey] = None):
283        """Visits all the nodes in a tree, calling function on each one.
284
285        function should have the signature function(node, accumulator) and return new_accumulator
286        If accumulators are not needed, the function must still accept a second parameter.
287
288        The order of that the nodes are visited is always depth first, however, the order children are traversed can
289        be set based on a sort_key function which should accept a node's values and return something that can be
290        sorted to receive the desired order (similar to the sort/sorted key).
291
292        We use the private _find_children function so that we don't have to re-traverse the tree
293        for every node we descend further down
294        """
295        if not self.populated:
296            self.populate()
297
298        # Find_nodes is path dependent, whereas _visit is not
299        # So in case the function modifies the node's path, find the nodes first
300        children = self._find_children(node)
301        accumulator = initial_accumulator
302        # We split visit into two, so that we don't have to keep calling find_children to traverse the tree
303        if node is not None:
304            accumulator = function(node, initial_accumulator)
305        if children is not None:
306            if sort_key is not None:
307                sort_key_not_none = sort_key  # Only necessary because of mypy
308                children = sorted(children, key = lambda x: sort_key_not_none(x[0].values))
309                if not sort_key.ascending:
310                    children = reversed(children)
311            accumulator = self._visit(children, function, accumulator, sort_key)
312        return accumulator
313
314    def _visit(self,
315               list_of_children: List['TreeNode'],
316               function: Callable,
317               accumulator: _T,
318               sort_key: Optional[interfaces.renderers.ColumnSortKey] = None) -> _T:
319        """Visits all the nodes in a tree, calling function on each one."""
320        if list_of_children is not None:
321            for n, children in list_of_children:
322                accumulator = function(n, accumulator)
323                if sort_key is not None:
324                    sort_key_not_none = sort_key  # Only necessary because of mypy
325                    children = sorted(children, key = lambda x: sort_key_not_none(x[0].values))
326                    if not sort_key.ascending:
327                        children = reversed(children)
328                accumulator = self._visit(children, function, accumulator, sort_key)
329        return accumulator
330
331
332class ColumnSortKey(interfaces.renderers.ColumnSortKey):
333
334    def __init__(self, treegrid: TreeGrid, column_name: str, ascending: bool = True) -> None:
335        _index = None
336        self._type = None
337        self.ascending = ascending
338        for i in range(len(treegrid.columns)):
339            column = treegrid.columns[i]
340            if column.name.lower() == column_name.lower():
341                _index = i
342                self._type = column.type
343        if _index is None:
344            raise ValueError("Column not found in TreeGrid columns: {}".format(column_name))
345        self._index = _index
346
347    def __call__(self, values: List[Any]) -> Any:
348        """The key function passed as the sort key."""
349        value = values[self._index]
350        if isinstance(value, interfaces.renderers.BaseAbsentValue):
351            if self._type == datetime.datetime:
352                value = datetime.datetime.min
353            elif self._type in [int, float]:
354                value = -1
355            elif self._type == bool:
356                value = False
357            elif self._type in [str, renderers.Disassembly]:
358                value = "-"
359            elif self._type == bytes:
360                value = b""
361        return value
362