1 files changed, 89 insertions, 5 deletions

diff --git a/kernel/src/device_tree.rs b/kernel/src/device_tree.rs
index 04f873c..d843234 100644
--- a/kernel/src/device_tree.rs
+++ b/kernel/src/device_tree.rs
@@ -1,9 +1,10 @@
 //! Support for the DeviceTree format.
 
-use core::{iter, slice};
-
+use crate::collections::stack_linked_list::StackLinkedList;
 use bstr::BStr;
 use contracts::requires;
+use core::{fmt, iter, slice};
+use either::Either;
 
 /// A reference to a flattened DeviceTree (DTB) in memory.
 #[derive(Debug)]
@@ -94,10 +95,22 @@ impl<'dt> FlattenedDeviceTree<'dt> {
         Ok(&out[..i])
     }
 
+    /// Iterates over the properties stored in the DeviceTree, only allocating memory on the stack.
+    pub fn for_each_property<'iter: 'dt, E>(
+        &'iter self,
+        mut func: impl for<'a> FnMut(FdtNodePath<'dt, 'a>, &'dt BStr, &'dt BStr) -> Result<(), E>,
+    ) -> Result<(), Either<DeviceTreeError, E>> {
+        for_each_property(
+            &mut self.struct_events().peekable(),
+            &mut func,
+            StackLinkedList::NIL,
+        )
+    }
+
     /// Returns an iterator over the events in the flattened DeviceTree's structure block.
-    pub fn struct_events(
-        &self,
-    ) -> impl '_ + Iterator<Item = Result<FdtStructEvent, DeviceTreeError>> {
+    pub fn struct_events<'iter: 'dt>(
+        &'iter self,
+    ) -> impl 'iter + Iterator<Item = Result<FdtStructEvent<'dt>, DeviceTreeError>> {
         let mut ptr = self.struct_block;
         iter::from_fn(move || loop {
             break match u32::from_be(ptr[0]) {
@@ -185,6 +198,46 @@ pub enum DeviceTreeError {
     InvalidDeviceTree,
     InvalidTokenType(u32),
     StringMissingNulTerminator(u32),
+
+    UnexpectedEndOfStructBlock,
+    UnexpectedEvent,
+}
+
+fn for_each_property<'dt, E>(
+    events: &mut iter::Peekable<impl Iterator<Item = Result<FdtStructEvent<'dt>, DeviceTreeError>>>,
+    func: &mut impl for<'a> FnMut(FdtNodePath<'dt, 'a>, &'dt BStr, &'dt BStr) -> Result<(), E>,
+    node: StackLinkedList<&'dt BStr>,
+) -> Result<(), Either<DeviceTreeError, E>> {
+    // Read the first event, which should be the BeginNode starting the node we're trying to read.
+    let event = events
+        .next()
+        .ok_or(Either::Left(DeviceTreeError::UnexpectedEndOfStructBlock))?
+        .map_err(Either::Left)?;
+    let FdtStructEvent::BeginNode(node_name) = event else {
+        return Err(Either::Left(DeviceTreeError::UnexpectedEvent));
+    };
+    let node = node.cons(node_name);
+
+    // Parse properties and subnodes until we get to the end.
+    loop {
+        if matches!(events.peek(), Some(Ok(FdtStructEvent::BeginNode(_)))) {
+            for_each_property(events, func, node)?;
+        } else {
+            let event = events
+                .next()
+                .ok_or(Either::Left(DeviceTreeError::UnexpectedEndOfStructBlock))?
+                .map_err(Either::Left)?;
+            match event {
+                FdtStructEvent::BeginNode(_) => {
+                    return Err(Either::Left(DeviceTreeError::UnexpectedEvent))
+                }
+                FdtStructEvent::EndNode => break Ok(()),
+                FdtStructEvent::Prop(prop, value) => {
+                    func(FdtNodePath(node), prop, value).map_err(Either::Right)?
+                }
+            }
+        }
+    }
 }
 
 /// The flattened DeviceTree header.
@@ -222,3 +275,34 @@ pub enum FdtStructEvent<'dt> {
     EndNode,
     Prop(&'dt BStr, &'dt BStr),
 }
+
+/// The path to a node. Note that the list this contains is in _reverse_ order.
+#[derive(Debug, Eq, PartialEq)]
+pub struct FdtNodePath<'dt, 'list>(pub StackLinkedList<'list, &'dt BStr>);
+
+impl<'dt, 'list> fmt::Display for FdtNodePath<'dt, 'list> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        match (self.0).0 {
+            Some((hd, tl)) => write!(fmt, "{}{}/", FdtNodePath(*tl), hd),
+            None => Ok(()),
+        }
+    }
+}
+
+impl<'dt, 'list, U> PartialEq<[U]> for FdtNodePath<'dt, 'list>
+where
+    &'dt BStr: PartialEq<U>,
+{
+    fn eq(&self, other: &[U]) -> bool {
+        self.0.iter().eq(other.iter().rev())
+    }
+}
+
+impl<'dt, 'list, U, const N: usize> PartialEq<[U; N]> for FdtNodePath<'dt, 'list>
+where
+    &'dt BStr: PartialEq<U>,
+{
+    fn eq(&self, other: &[U; N]) -> bool {
+        self.0.iter().eq(other.iter().rev())
+    }
+}