Re: [PATCH v2 03/10] pylibfdt: Add NodeTree live tree representation

[David Gibson <david@gibson.dropbear.id.au>]

[-- Attachment #1: Type: text/plain, Size: 17100 bytes --]

On Wed, Oct 28, 2026 at 02:46:52PM -0700, Douglas Anderson wrote:
> Add `NodeTree`, an in-memory live tree representation of a devicetree
> node and its subtree, to `pylibfdt`:
> 
> - `NodeTree.unflatten(fdt, offset=0)` builds a `NodeTree` hierarchy from
>   an `FdtRo` instance.
> - `NodeTree.flatten(mem_rsv=(), boot_cpuid_phys=0)` serializes a root
>   `NodeTree` back into a packed FDT blob via `FdtSw`.
> - `get_node()`, `create_path()`, and `walk()` provide path lookup,
>   intermediate node creation, and pre-order traversal.
> - `get_str()`, `set_str()`, `get_stringlist()`, `set_stringlist()`,
>   `get_u32()`, `set_u32()`, `get_u32_list()`, and `set_u32_list()`
>   provide typed property access and mutation (updating
>   `Property.as_str()` and `Property.as_stringlist()` so empty `b''`
>   properties raise `ValueError` or return `[]` rather than
>   `IndexError`).
> 
> Add unit tests in `tests/pylibfdt_tests.py` covering `NodeTree`
> unflatten/flatten round-tripping and helper methods.

Thanks for splitting this out as suggested.  However, on
consideration, I don't think it really belongs in pylibfdt: the "f" in
there refers to "flattened" and this is, explicitly, a non-flattened
data structure.

I have sometimes thought about adding a library for handling
non-flattened trees, although I wasn't thinking something Python
specific.

I think for now let's move this to its own Python file / module.

> Assisted-by: Gemini:gemini-pro-prerelease
> Signed-off-by: Douglas Anderson <dianders@chromium.org>
> ---
> 
> Changes in v2:
> - Split NodeTree live tree representation out of fdtfactor into
>   pylibfdt (David Gibson)
> 
>  pylibfdt/libfdt.i       | 262 +++++++++++++++++++++++++++++++++++++++-
>  tests/pylibfdt_tests.py |  54 +++++++++
>  2 files changed, 315 insertions(+), 1 deletion(-)
> 
> diff --git a/pylibfdt/libfdt.i b/pylibfdt/libfdt.i
> index 0db7110b4a38..f511c61746e3 100644
> --- a/pylibfdt/libfdt.i
> +++ b/pylibfdt/libfdt.i
> @@ -929,7 +929,7 @@ class Property(bytearray):
>  
>      def as_str(self):
>          """Unicode is supported by decoding from UTF-8"""
> -        if self[-1] != 0:
> +        if not self or self[-1] != 0:
>              raise ValueError('Property lacks nul termination')
>          if 0 in self[:-1]:
>              raise ValueError('Property contains embedded nul characters')
> @@ -937,6 +937,8 @@ class Property(bytearray):
>  
>      def as_stringlist(self):
>          """Unicode is supported by decoding from UTF-8"""
> +        if not self:
> +            return []

The two hunks above are good fixes, but unrelated to the bulk of the patch.

>          if self[-1] != 0:
>              raise ValueError('Property lacks nul termination')
>          parts = self[:-1].split(b'\x00')
> @@ -1210,6 +1212,264 @@ class NodeAdder():
>  
>      def __exit__(self, type, value, traceback):
>          self._fdt.end_node()
> +
> +
> +class NodeTree:

Maybe class DeviceTree?  The "node" doesn't really add any useful
information.

> +    """In-memory live tree representation of a devicetree node and its subtree.
> +
> +    Attributes:
> +        props: Dict mapping property name (str) to raw property value (bytes).
> +        children: Dict mapping child node name (str) to child NodeTree.
> +    """
> +
> +    def __init__(self):
> +        self.props = {}
> +        self.children = {}
> +
> +    @classmethod
> +    def unflatten(cls, fdt, offset=0):
> +        """Unflatten an FdtRo subtree starting at `offset` into a NodeTree.
> +
> +        Args:
> +            fdt: An `FdtRo` (or `Fdt`) instance.
> +            offset: Starting node offset (default 0 for the root node).
> +
> +        Returns:
> +            A `NodeTree` representing the node at `offset` and its descendants.
> +        """
> +        node = cls()
> +        for prop in fdt.properties(offset):
> +            node.props[prop.name] = bytes(prop)

Since we already rely on class Property from libfdt.i, it seems like
it would be a little more natural to have the dictionary values be
class Property instances.  Yes, that technically has some redundant
storage of the property names, but we're not particularly concerned
about optimisation for this Python library.  Plus, Python's
assign-by-reference should mean it's generally just a duplicated
pointer, not a whole duplicated string.

> +        for suboff in fdt.subnodes(offset):
> +            node.children[fdt.get_name(suboff)] = cls.unflatten(fdt, suboff)
> +        return node
> +
> +    def _flatten_subtree(self, sw, name):
> +        """Recursively write this NodeTree and its children into an FdtSw.
> +
> +        Args:
> +            sw: An `FdtSw` sequential-write instance.
> +            name: Node name for this subtree (empty string `''` for root).
> +        """
> +        with sw.add_node(name):
> +            for prop_name, val in self.props.items():
> +                sw.property(prop_name, bytes(val))
> +            for child_name, child_node in self.children.items():
> +                child_node._flatten_subtree(sw, child_name)
> +
> +    def flatten(self, mem_rsv=(), boot_cpuid_phys=0):
> +        """Serialize this root NodeTree into a packed FDT byte string.
> +
> +        Args:
> +            mem_rsv: Iterable of (address, size) tuples for the FDT memory
> +                reservation block.
> +            boot_cpuid_phys: Physical boot CPU ID for the FDT header.
> +
> +        Returns:
> +            Serialized FDT blob as `bytes`.
> +        """
> +        sw = FdtSw()
> +        for addr, size in mem_rsv:
> +            sw.add_reservemap_entry(addr, size)
> +        sw.finish_reservemap()
> +        self._flatten_subtree(sw, '')
> +        fdt = sw.as_fdt()
> +        fdt_set_boot_cpuid_phys(fdt._fdt, boot_cpuid_phys)
> +        fdt.pack()

For better symmetry with unflatten(), I'd suggest returning the Fdt
object here, leaving the conversion to a bytearray to the caller.

> +        return bytes(fdt.as_bytearray())
> +
> +    def get_node(self, path):
> +        """Look up a descendant NodeTree by path without modifying the tree.
> +
> +        Follows the slash-separated node names in `path` starting from `self`
> +        (leading, trailing, and repeated `'/'` characters are ignored, so
> +        `'/soc/i2c@4000'` and `'soc/i2c@4000'` behave identically, and `''` or
> +        `'/'` returns `self`). If any component along `path` is not present in
> +        `children`, returns `None`.
> +
> +        Args:
> +            path: Slash-separated node path starting from `self` (e.g.
> +                `'/soc/i2c@4000'` or `'soc/i2c@4000'`).
> +
> +        Returns:
> +            The `NodeTree` at `path`, or `None` if not found.
> +        """
> +        node = self
> +        for part in path.split('/'):
> +            if not part:
> +                continue
> +            node = node.children.get(part)
> +            if node is None:
> +                return None
> +        return node
> +
> +    def create_path(self, path):
> +        """Return the descendant NodeTree at `path`, creating missing nodes.
> +
> +        Looks up a child or deeper descendant `NodeTree` by following the
> +        slash-separated node names in `path` starting from `self` (leading,
> +        trailing, and repeated `'/'` characters are ignored, so
> +        `'/soc/i2c@4000'` and `'soc/i2c@4000'` behave identically). If any
> +        node along `path` does not exist yet in `children`, a new empty
> +        `NodeTree` is created for it automatically (similar to `mkdir -p`).
> +        Passing `''` or `'/'` returns `self`.

Reference get_path() rather than repeating this useful, but wordy,
description.

> +
> +        Example:
> +            root = NodeTree()
> +            # Automatically creates root.children['soc'] and
> +            # root.children['soc'].children['i2c@4000'], and returns the
> +            # 'i2c@4000' NodeTree.
> +            i2c = root.create_path('/soc/i2c@4000')
> +            i2c.set_str('status', 'okay')
> +
> +        Args:
> +            path: Slash-separated node path starting from `self` (e.g.
> +                `'/soc/i2c@4000'` or `'soc/i2c@4000'`).
> +
> +        Returns:
> +            The `NodeTree` instance at `path`.
> +        """
> +        node = self
> +        for part in path.split('/'):
> +            if not part:
> +                continue
> +            if part not in node.children:
> +                node.children[part] = type(self)()
> +            node = node.children[part]
> +        return node
> +
> +    def walk(self, path=''):
> +        """Yield `(path, node)` pairs for this subtree in pre-order.
> +
> +        Args:
> +            path: Path prefix for `self` (defaults to `''` for the root node,
> +                producing paths like `''`, `'/soc'`, `'/soc/i2c@4000'`).
> +
> +        Yields:
> +            Tuple of `(path, node)` for `self` followed recursively by each
> +            descendant `NodeTree`.
> +        """
> +        prefix = path.rstrip('/')
> +        yield path, self
> +        for name, child in self.children.items():
> +            yield from child.walk(f'{prefix}/{name}')
> +
> +    def get_str(self, name):
> +        """Return property `name` decoded as a NUL-terminated UTF-8 string.
> +
> +        Args:
> +            name: Property name to look up in `self.props`.
> +
> +        Returns:
> +            Decoded string value (without the trailing NUL byte).
> +
> +        Raises:
> +            KeyError: If `name` is not in `self.props`.
> +            ValueError: If the property value is not a single NUL-terminated
> +                UTF-8 string.
> +        """
> +        return Property(name, self.props[name]).as_str()
> +
> +    def set_str(self, name, val):
> +        """Set property `name` to a NUL-terminated UTF-8 string.
> +
> +        Args:
> +            name: Property name to set in `self.props`.
> +            val: String value to encode as UTF-8 with a trailing NUL byte.
> +
> +        Raises:
> +            ValueError: If `val` contains embedded NUL characters.
> +        """
> +        if '\x00' in val:
> +            raise ValueError('String value contains embedded nul characters')
> +        self.props[name] = val.encode('utf-8') + b'\x00'
> +
> +    def get_stringlist(self, name):
> +        """Return property `name` decoded as a list of NUL-separated strings.
> +
> +        Args:
> +            name: Property name to look up in `self.props`.
> +
> +        Returns:
> +            List of decoded UTF-8 strings (`[]` if the property is empty).
> +
> +        Raises:
> +            KeyError: If `name` is not in `self.props`.
> +            ValueError: If a non-empty property lacks NUL termination.
> +        """
> +        return Property(name, self.props[name]).as_stringlist()
> +
> +    def set_stringlist(self, name, vals):
> +        """Set property `name` to a NUL-separated list of UTF-8 strings.
> +
> +        Args:
> +            name: Property name to set in `self.props`.
> +            vals: Iterable of strings to encode as NUL-terminated UTF-8.
> +
> +        Raises:
> +            ValueError: If any string in `vals` contains embedded NUL
> +                characters.
> +        """
> +        vals = list(vals)
> +        if any('\x00' in v for v in vals):
> +            raise ValueError('String value contains embedded nul characters')
> +        self.props[name] = b''.join(v.encode('utf-8') + b'\x00' for v in vals)
> +
> +    def get_u32(self, name):
> +        """Return property `name` decoded as a single big-endian uint32 cell.
> +
> +        Args:
> +            name: Property name to look up in `self.props`.
> +
> +        Returns:
> +            Integer value of the 32-bit cell.
> +
> +        Raises:
> +            KeyError: If `name` is not in `self.props`.
> +            ValueError: If the property length is not 4 bytes.
> +        """
> +        raw = self.props[name]
> +        if len(raw) != 4:
> +            raise ValueError(f'Property {name!r} length {len(raw)} != 4')
> +        return Property(name, raw).as_uint32()
> +
> +    def set_u32(self, name, val):
> +        """Set property `name` to a single big-endian uint32 cell.
> +
> +        Args:
> +            name: Property name to set in `self.props`.
> +            val: Unsigned 32-bit integer value.
> +        """
> +        self.props[name] = struct.pack('>I', val)
> +
> +    def get_u32_list(self, name):
> +        """Return property `name` decoded as a list of big-endian uint32 cells.
> +
> +        Args:
> +            name: Property name to look up in `self.props`.
> +
> +        Returns:
> +            List of 32-bit unsigned integers.
> +
> +        Raises:
> +            KeyError: If `name` is not in `self.props`.
> +            ValueError: If the property length is not a multiple of 4 bytes.
> +        """
> +        raw = self.props[name]
> +        if len(raw) % 4 != 0:
> +            raise ValueError(
> +                f'Property {name!r} length {len(raw)} is not a multiple of 4'
> +            )
> +        return Property(name, raw).as_uint32_list()
> +
> +    def set_u32_list(self, name, vals):
> +        """Set property `name` to a sequence of big-endian uint32 cells.
> +
> +        Args:
> +            name: Property name to set in `self.props`.
> +            vals: Sequence of unsigned 32-bit integer values.
> +        """
> +        self.props[name] = struct.pack(f'>{len(vals)}I', *vals)
>  %}
>  
>  %rename(fdt_property) fdt_property_func;
> diff --git a/tests/pylibfdt_tests.py b/tests/pylibfdt_tests.py
> index 2a0509c7802e..569eb698a86f 100644
> --- a/tests/pylibfdt_tests.py
> +++ b/tests/pylibfdt_tests.py
> @@ -697,6 +697,60 @@ class PyLibfdtRoTests(unittest.TestCase):
>          self.assertEqual(b'this is a placeholder string\0string2\0',
>                           self.fdt.getprop(node, 'placeholder'))
>  
> +    def testNodeTreeRoundTrip(self):
> +        """Test unflattening and flattening a tree via NodeTree"""
> +        tree = libfdt.NodeTree.unflatten(self.fdt)
> +        rsvmap = self.fdt.get_mem_rsv_list()
> +        cpuid = self.fdt.boot_cpuid_phys()
> +        blob = tree.flatten(rsvmap, cpuid)
> +
> +        fdt2 = libfdt.FdtRo(blob)
> +        self.assertEqual(rsvmap, fdt2.get_mem_rsv_list())
> +        self.assertEqual(cpuid, fdt2.boot_cpuid_phys())
> +
> +        tree2 = libfdt.NodeTree.unflatten(fdt2)
> +        nodes1 = [(path, n.props, list(n.children.keys()))
> +                  for path, n in tree.walk()]
> +        nodes2 = [(path, n.props, list(n.children.keys()))
> +                  for path, n in tree2.walk()]
> +        self.assertEqual(nodes1, nodes2)
> +
> +    def testNodeTreeHelpers(self):
> +        """Test NodeTree navigation and typed property helpers"""
> +        root = libfdt.NodeTree()
> +        self.assertIs(root, root.get_node(''))
> +        self.assertIs(root, root.get_node('/'))
> +        self.assertIsNone(root.get_node('/soc/i2c@4000'))
> +
> +        i2c = root.create_path('/soc/i2c@4000')
> +        self.assertIs(i2c, root.get_node('/soc/i2c@4000'))
> +        self.assertIs(i2c, root.get_node('soc/i2c@4000'))
> +        self.assertEqual(['', '/soc', '/soc/i2c@4000'],
> +                         [path for path, _ in root.walk()])
> +        self.assertEqual(['/', '/soc', '/soc/i2c@4000'],
> +                         [path for path, _ in root.walk('/')])
> +
> +        i2c.set_str('status', 'okay')
> +        self.assertEqual('okay', i2c.get_str('status'))
> +        with self.assertRaises(ValueError):
> +            i2c.set_str('status', 'ok\x00ay')
> +
> +        i2c.set_stringlist('compatible', ['vendor,i2c', 'generic,i2c'])
> +        self.assertEqual(['vendor,i2c', 'generic,i2c'],
> +                         i2c.get_stringlist('compatible'))
> +        with self.assertRaises(ValueError):
> +            i2c.set_stringlist('compatible', ['vendor\x00,i2c'])
> +        i2c.set_stringlist('empty-list', [])
> +        self.assertEqual([], i2c.get_stringlist('empty-list'))
> +        with self.assertRaises(ValueError):
> +            i2c.get_str('empty-list')
> +
> +        i2c.set_u32('#address-cells', 1)
> +        self.assertEqual(1, i2c.get_u32('#address-cells'))
> +
> +        i2c.set_u32_list('reg', [0x4000, 0x100])
> +        self.assertEqual([0x4000, 0x100], i2c.get_u32_list('reg'))
> +
>  
>  if __name__ == "__main__":
>      unittest.main()
> -- 
> 2.56.0.313.g2479322e68-goog
> 
> 

-- 
David Gibson (he or they)	| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you, not the other way
				| around.
http://www.ozlabs.org/~dgibson

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]