[PATCH 0/2] dtc: Fix deletes within a section and before a redefinition

[PATCH 0/2] dtc: Fix deletes within a section and before a redefinition

[Simon Glass]

A /delete-property/ or /delete-node/ in the first section of a dts, or
in a node which a later section adds, is ignored and leaves its
placeholder in the tree, where it can show up as a bogus duplicate. A
node which is deleted and then defined again also returns to its old
place, with its old subnodes in their old order.

The first patch applies each delete within its own section and keeps
the placeholders out of the tree. The second removes deleted entries
from the tree, so that a node defined again comes after the existing
ones.

Note that the second patch changes the output of existing dts files
which delete and then redefine a node or property. That patch explains
why this seems the better behaviour.


Simon Glass (2):
  dtc: Apply deletes in the section which has them
  dtc: Remove a deleted node or property from the tree

 dtc-parser.y                            |   1 +
 dtc.h                                   |   1 +
 livetree.c                              | 112 ++++++++++++++++++---
 tests/delete_in_section.dts             | 125 ++++++++++++++++++++++++
 tests/delete_in_section_badref.dts      |  11 +++
 tests/delete_in_section_labels.dts      |  28 ++++++
 tests/delete_in_section_labels_ref.dts  |   9 ++
 tests/delete_in_section_overlay.dts     |  21 ++++
 tests/delete_in_section_overlay_ref.dts |   9 ++
 tests/delete_in_section_ref.dts         |  44 +++++++++
 tests/delete_readd_order.dts            |  57 +++++++++++
 tests/delete_readd_order_ref.dts        |  28 ++++++
 tests/run_tests.sh                      |  27 +++++
 13 files changed, 461 insertions(+), 12 deletions(-)
 create mode 100644 tests/delete_in_section.dts
 create mode 100644 tests/delete_in_section_badref.dts
 create mode 100644 tests/delete_in_section_labels.dts
 create mode 100644 tests/delete_in_section_labels_ref.dts
 create mode 100644 tests/delete_in_section_overlay.dts
 create mode 100644 tests/delete_in_section_overlay_ref.dts
 create mode 100644 tests/delete_in_section_ref.dts
 create mode 100644 tests/delete_readd_order.dts
 create mode 100644 tests/delete_readd_order_ref.dts

---
base-commit: f99e3af0ecb67a9085478a9b8ddbcc25aa64931d
branch: delete-markers2

-- 
2.43.0

[PATCH 1/2] dtc: Apply deletes in the section which has them

[Simon Glass]

The parser holds each /delete-property/ and /delete-node/ as a
placeholder entry, flagged as deleted, among the node's properties or
children. It only takes effect when merge_nodes() merges its section
into an earlier one. In the first section of a dts it is ignored, so
'a; /delete-property/ a;' leaves 'a' in the tree. The same happens in
any node which a later section adds, since merge_nodes() attaches a new
child as it is. An ignored /delete-node/ also leaves its placeholder in
the tree, which then shows up as '(null): Duplicate node name'

Apply each delete when its node is built, by dropping the earlier
entries of the same name from that node. Nothing can refer to the node
yet, so they can be unlinked rather than flagged as deleted. Keep the
placeholder, so that merging the node into an earlier definition still
deletes there too.

When a node joins the tree without being merged, as the first section,
as a new child in merge_nodes() or as an overlay fragment, drop its
placeholders, since there is nothing earlier for them to delete. This
keeps placeholders and entries deleted within a section out of the tree,
so that nothing which walks the tree has to skip them.

Duplicate entries within a section are still reported as errors, since
nothing is merged.

Closes: https://github.com/dgibson/dtc/issues/37
Assisted-by: Claude:claude-opus-5-5
Signed-off-by: Simon Glass <sjg@chromium.org>
---

 dtc-parser.y                            |   1 +
 dtc.h                                   |   1 +
 livetree.c                              |  69 ++++++++++++-
 tests/delete_in_section.dts             | 125 ++++++++++++++++++++++++
 tests/delete_in_section_badref.dts      |  11 +++
 tests/delete_in_section_labels.dts      |  28 ++++++
 tests/delete_in_section_labels_ref.dts  |   9 ++
 tests/delete_in_section_overlay.dts     |  21 ++++
 tests/delete_in_section_overlay_ref.dts |   9 ++
 tests/delete_in_section_ref.dts         |  44 +++++++++
 tests/run_tests.sh                      |  21 ++++
 11 files changed, 338 insertions(+), 1 deletion(-)
 create mode 100644 tests/delete_in_section.dts
 create mode 100644 tests/delete_in_section_badref.dts
 create mode 100644 tests/delete_in_section_labels.dts
 create mode 100644 tests/delete_in_section_labels_ref.dts
 create mode 100644 tests/delete_in_section_overlay.dts
 create mode 100644 tests/delete_in_section_overlay_ref.dts
 create mode 100644 tests/delete_in_section_ref.dts

diff --git a/dtc-parser.y b/dtc-parser.y
index e47f80d..0282f7b 100644
--- a/dtc-parser.y
+++ b/dtc-parser.y
@@ -160,6 +160,7 @@ dt_ref: DT_LABEL_REF | DT_PATH_REF;
 devicetree:
 	  '/' nodedef
 		{
+			drop_delete_placeholders($2);
 			$$ = name_node($2, "");
 		}
 	| devicetree '/' nodedef
diff --git a/dtc.h b/dtc.h
index 473552e..3e5109d 100644
--- a/dtc.h
+++ b/dtc.h
@@ -277,6 +277,7 @@ struct node *omit_node_if_unused(struct node *node);
 struct node *reference_node(struct node *node);
 struct node *chain_node(struct node *first, struct node *list);
 struct node *merge_nodes(struct node *old_node, struct node *new_node);
+void drop_delete_placeholders(struct node *node);
 struct node *add_orphan_node(struct node *old_node, struct node *new_node, char *ref);
 
 void add_property(struct node *node, struct property *prop);
diff --git a/livetree.c b/livetree.c
index abe73de..b474a05 100644
--- a/livetree.c
+++ b/livetree.c
@@ -85,6 +85,68 @@ struct property *reverse_properties(struct property *first)
 	return head;
 }
 
+/*
+ * The parser holds each /delete-property/ and /delete-node/ as a placeholder
+ * entry, flagged as deleted, among the node's properties or children. Apply
+ * each one by dropping the earlier entries of the same name in the node. The
+ * placeholders stay, so that merging the node into an earlier definition
+ * deletes there too
+ */
+static void apply_deletes(struct node *node)
+{
+	struct property *prop, **pp;
+	struct node *child, **np;
+
+	for (prop = node->proplist; prop; prop = prop->next) {
+		if (!prop->deleted)
+			continue;
+		for (pp = &node->proplist; *pp != prop;) {
+			if (streq((*pp)->name, prop->name))
+				*pp = (*pp)->next;
+			else
+				pp = &(*pp)->next;
+		}
+	}
+
+	for (child = node->children; child; child = child->next_sibling) {
+		if (!child->deleted)
+			continue;
+		for (np = &node->children; *np != child;) {
+			if (streq((*np)->name, child->name))
+				*np = (*np)->next_sibling;
+			else
+				np = &(*np)->next_sibling;
+		}
+	}
+}
+
+/*
+ * Drop the /delete-property/ and /delete-node/ placeholders from a subtree
+ * which joins the tree without being merged, since there is nothing earlier
+ * for them to delete
+ */
+void drop_delete_placeholders(struct node *node)
+{
+	struct property **pp = &node->proplist;
+	struct node **np = &node->children;
+
+	while (*pp) {
+		if ((*pp)->deleted)
+			*pp = (*pp)->next;
+		else
+			pp = &(*pp)->next;
+	}
+
+	while (*np) {
+		if ((*np)->deleted) {
+			*np = (*np)->next_sibling;
+		} else {
+			drop_delete_placeholders(*np);
+			np = &(*np)->next_sibling;
+		}
+	}
+}
+
 struct node *build_node(struct property *proplist, struct node *children,
 			struct srcpos *srcpos)
 {
@@ -100,6 +162,7 @@ struct node *build_node(struct property *proplist, struct node *children,
 	for_each_child(new, child) {
 		child->parent = new;
 	}
+	apply_deletes(new);
 
 	return new;
 }
@@ -212,8 +275,10 @@ struct node *merge_nodes(struct node *old_node, struct node *new_node)
 		}
 
 		/* if no collision occurred, add child to the old node. */
-		if (new_child)
+		if (new_child) {
+			drop_delete_placeholders(new_child);
 			add_child(old_node, new_child);
+		}
 	}
 
 	old_node->srcpos = srcpos_extend(old_node->srcpos, new_node->srcpos);
@@ -245,6 +310,8 @@ struct node * add_orphan_node(struct node *dt, struct node *new_node, char *ref)
 		p = build_property("target", d, NULL);
 	}
 
+	drop_delete_placeholders(new_node);
+
 	xasprintf(&name, "fragment@%u",
 			next_orphan_fragment++);
 	name_node(new_node, "__overlay__");
diff --git a/tests/delete_in_section.dts b/tests/delete_in_section.dts
new file mode 100644
index 0000000..e742e79
--- /dev/null
+++ b/tests/delete_in_section.dts
@@ -0,0 +1,125 @@
+/dts-v1/;
+
+/*
+ * Delete properties and nodes defined earlier in the same section. This is
+ * the first section, so nothing is merged into an earlier one
+ */
+
+/ {
+	#address-cells = <1>;
+	#size-cells = <0>;
+
+	gone-prop;
+	/delete-property/ gone-prop;
+	kept-prop;
+	again-prop = "old";
+	/delete-property/ again-prop;
+	again-prop = "new";
+	both-prop;
+
+	/* Deleted and added again here, then changed by a later section */
+	redel-prop = "old";
+	/delete-property/ redel-prop;
+	redel-prop = "new";
+	reset-prop = "old";
+	/delete-property/ reset-prop;
+	reset-prop = "new";
+
+	gone-node {
+	};
+	/delete-node/ gone-node;
+
+	again-node {
+		old;
+	};
+	/delete-node/ again-node;
+	again-node {
+		new;
+	};
+
+	lbl: node {
+		inner-prop;
+		/delete-property/ inner-prop;
+
+		inner-node {
+		};
+		/delete-node/ inner-node;
+	};
+
+	redel-node {
+		old;
+	};
+	/delete-node/ redel-node;
+	redel-node {
+		new;
+	};
+
+	remerge-node {
+		old;
+	};
+	/delete-node/ remerge-node;
+	remerge-node {
+		new;
+	};
+
+	/* Checks must not see what is deleted here */
+	named-node {
+		name = "other";
+		/delete-property/ name;
+	};
+
+	bus {
+		#address-cells = <1>;
+		#size-cells = <0>;
+
+		child@1 {
+			reg = <1>;
+		};
+		/delete-node/ child@1;
+	};
+
+	/* Deleted here, then added again by a later section */
+	readd@1 {
+		reg = <1>;
+		old;
+	};
+	/delete-node/ readd@1;
+	/delete-node/ placeholder@2;
+};
+
+/* Delete within nodes which a later section adds, and within the merge */
+
+/ {
+	both-prop = "new";
+	/delete-property/ both-prop;
+	/delete-property/ redel-prop;
+	reset-prop = "later";
+
+	new-node {
+		new-prop;
+		/delete-property/ new-prop;
+		kept;
+	};
+
+	/delete-node/ redel-node;
+
+	remerge-node {
+		later;
+	};
+
+	readd@1 {
+		reg = <1>;
+		later;
+	};
+
+	placeholder@2 {
+		reg = <2>;
+	};
+};
+
+&lbl {
+	child {
+		child-prop;
+		/delete-property/ child-prop;
+	};
+};
diff --git a/tests/delete_in_section_badref.dts b/tests/delete_in_section_badref.dts
new file mode 100644
index 0000000..79a40e4
--- /dev/null
+++ b/tests/delete_in_section_badref.dts
@@ -0,0 +1,11 @@
+/dts-v1/;
+
+/* A reference to a node deleted in the same section has nothing to refer to */
+
+/ {
+	ref = <&gone>;
+
+	gone: node {
+	};
+	/delete-node/ node;
+};
diff --git a/tests/delete_in_section_labels.dts b/tests/delete_in_section_labels.dts
new file mode 100644
index 0000000..fbde838
--- /dev/null
+++ b/tests/delete_in_section_labels.dts
@@ -0,0 +1,28 @@
+/dts-v1/;
+
+/*
+ * A label moves to the new definition of a node deleted in the same
+ * section, and labels on deleted nodes stay out of __symbols__
+ */
+
+/ {
+	ref = <&moved>;
+
+	moved: node {
+		old;
+	};
+	/delete-node/ node;
+	moved: node {
+		new;
+	};
+
+	gone: gone-node {
+	};
+	/delete-node/ gone-node;
+};
+
+/ {
+	later: later-node {
+	};
+	/delete-node/ later-node;
+};
diff --git a/tests/delete_in_section_labels_ref.dts b/tests/delete_in_section_labels_ref.dts
new file mode 100644
index 0000000..5d8cf38
--- /dev/null
+++ b/tests/delete_in_section_labels_ref.dts
@@ -0,0 +1,9 @@
+/dts-v1/;
+
+/ {
+	ref = <&moved>;
+
+	moved: node {
+		new;
+	};
+};
diff --git a/tests/delete_in_section_overlay.dts b/tests/delete_in_section_overlay.dts
new file mode 100644
index 0000000..e3e8f71
--- /dev/null
+++ b/tests/delete_in_section_overlay.dts
@@ -0,0 +1,21 @@
+/dts-v1/;
+/plugin/;
+
+/* Delete within the fragments of an overlay */
+
+&target {
+	a;
+	/delete-property/ a;
+	b;
+	/delete-property/ c;
+
+	gone {
+	};
+	/delete-node/ gone;
+	/delete-node/ d;
+};
+
+&{/path} {
+	p;
+	/delete-property/ p;
+};
diff --git a/tests/delete_in_section_overlay_ref.dts b/tests/delete_in_section_overlay_ref.dts
new file mode 100644
index 0000000..48f36b3
--- /dev/null
+++ b/tests/delete_in_section_overlay_ref.dts
@@ -0,0 +1,9 @@
+/dts-v1/;
+/plugin/;
+
+&target {
+	b;
+};
+
+&{/path} {
+};
diff --git a/tests/delete_in_section_ref.dts b/tests/delete_in_section_ref.dts
new file mode 100644
index 0000000..20d459a
--- /dev/null
+++ b/tests/delete_in_section_ref.dts
@@ -0,0 +1,44 @@
+/dts-v1/;
+
+/ {
+	#address-cells = <1>;
+	#size-cells = <0>;
+	kept-prop;
+	again-prop = "new";
+	reset-prop = "later";
+
+	again-node {
+		new;
+	};
+
+	lbl: node {
+		child {
+		};
+	};
+
+	remerge-node {
+		new;
+		later;
+	};
+
+	named-node {
+	};
+
+	bus {
+		#address-cells = <1>;
+		#size-cells = <0>;
+	};
+
+	new-node {
+		kept;
+	};
+
+	readd@1 {
+		reg = <1>;
+		later;
+	};
+
+	placeholder@2 {
+		reg = <2>;
+	};
+};
diff --git a/tests/run_tests.sh b/tests/run_tests.sh
index 842b543..2650df6 100755
--- a/tests/run_tests.sh
+++ b/tests/run_tests.sh
@@ -725,6 +725,27 @@ dtc_tests () {
     run_dtc_test -I dts -O dts -o delete_reinstate_multilabel.dts.test.dts "$SRCDIR/delete_reinstate_multilabel.dts"
     run_wrap_test cmp delete_reinstate_multilabel.dts.test.dts "$SRCDIR/delete_reinstate_multilabel_ref.dts"
 
+    # Check deletes within the section which has them
+    run_dtc_test -E reg_format -E avoid_unnecessary_addr_size -I dts -O dtb \
+	-o delete_in_section.test.dtb "$SRCDIR/delete_in_section.dts"
+    run_dtc_test -I dts -O dtb -o delete_in_section_ref.test.dtb \
+	"$SRCDIR/delete_in_section_ref.dts"
+    run_test dtbs_equal_ordered delete_in_section.test.dtb delete_in_section_ref.test.dtb
+    run_dtc_test -@ -I dts -O dtb -o delete_in_section_labels.test.dtb \
+	"$SRCDIR/delete_in_section_labels.dts"
+    run_dtc_test -@ -I dts -O dtb -o delete_in_section_labels_ref.test.dtb \
+	"$SRCDIR/delete_in_section_labels_ref.dts"
+    run_test dtbs_equal_ordered delete_in_section_labels.test.dtb \
+	delete_in_section_labels_ref.test.dtb
+    run_dtc_test -I dts -O dtb -o delete_in_section_overlay.test.dtb \
+	"$SRCDIR/delete_in_section_overlay.dts"
+    run_dtc_test -I dts -O dtb -o delete_in_section_overlay_ref.test.dtb \
+	"$SRCDIR/delete_in_section_overlay_ref.dts"
+    run_test dtbs_equal_ordered delete_in_section_overlay.test.dtb \
+	delete_in_section_overlay_ref.test.dtb
+    run_sh_test "$SRCDIR/dtc-checkfails.sh" phandle_references \
+	-n duplicate_node_names -- -I dts -O dtb "$SRCDIR/delete_in_section_badref.dts"
+
     # Check some checks
     check_tests "$SRCDIR/dup-nodename.dts" duplicate_node_names
     check_tests "$SRCDIR/dup-propname.dts" duplicate_property_names
-- 
2.43.0

[PATCH 2/2] dtc: Remove a deleted node or property from the tree

[Simon Glass]

Deleting a node or property only flags it as deleted, leaving it in
place. If a later section adds it again, merge_nodes() finds the flagged
entry and revives it where it was, along with its subnodes, which come
back in their old order before any new ones. So deleting a node in
order to redefine it does not give the order which the source shows.

Unlink a node or property from its parent when deleting it, so that
adding it again creates a new entry after the existing ones. Nothing
deleted then stays in the tree while parsing, so merge_nodes() has
nothing to revive and can skip deleted entries like everything else.

Leave the node's next_sibling alone, since fixup_omit_unused_nodes()
deletes nodes while walking over their siblings.

Note that this changes the output of existing dts files. When a dts
deletes a node or property and then defines it again, the new definition
now comes after its siblings instead of taking the old one's place, and
its subnodes come in the order of the new definition alone.

This is the better behaviour because:

- Deleting is how a dts says to start again. A dts which wants to keep a
  node's place can override the node without deleting it, since merging
  already updates a node in place
- Node order can matter. In issue 174, U-Boot's binman builds an image
  from a node which is deleted and defined again, yet the image comes
  out in the old order. The only workaround is to define the nodes in
  the wanted order before including the file which defines them
- It matches the previous patch, in which a node deleted and defined
  again within a section, or deleted in the first section and defined
  by a later one, already comes out where the new definition is

Closes: https://github.com/dgibson/dtc/issues/174
Assisted-by: Claude:claude-opus-5-5
Signed-off-by: Simon Glass <sjg@chromium.org>
---

 livetree.c                       | 43 ++++++++++++++++++------
 tests/delete_readd_order.dts     | 57 ++++++++++++++++++++++++++++++++
 tests/delete_readd_order_ref.dts | 28 ++++++++++++++++
 tests/run_tests.sh               |  6 ++++
 4 files changed, 123 insertions(+), 11 deletions(-)
 create mode 100644 tests/delete_readd_order.dts
 create mode 100644 tests/delete_readd_order_ref.dts

diff --git a/livetree.c b/livetree.c
index b474a05..6609e4e 100644
--- a/livetree.c
+++ b/livetree.c
@@ -208,8 +208,6 @@ struct node *merge_nodes(struct node *old_node, struct node *new_node)
 	struct node *new_child, *old_child;
 	struct label *l;
 
-	old_node->deleted = 0;
-
 	/* Add new node labels to old node */
 	for_each_label_withdel(new_node->labels, l)
 		add_label(&old_node->labels, l->label);
@@ -229,14 +227,13 @@ struct node *merge_nodes(struct node *old_node, struct node *new_node)
 		}
 
 		/* Look for a collision, set new value if there is */
-		for_each_property_withdel(old_node, old_prop) {
+		for_each_property(old_node, old_prop) {
 			if (streq(old_prop->name, new_prop->name)) {
 				/* Add new labels to old property */
 				for_each_label_withdel(new_prop->labels, l)
 					add_label(&old_prop->labels, l->label);
 
 				old_prop->val = new_prop->val;
-				old_prop->deleted = 0;
 				srcpos_free(old_prop->srcpos);
 				old_prop->srcpos = new_prop->srcpos;
 				free(new_prop);
@@ -266,7 +263,7 @@ struct node *merge_nodes(struct node *old_node, struct node *new_node)
 		}
 
 		/* Search for a collision.  Merge if there is */
-		for_each_child_withdel(old_node, old_child) {
+		for_each_child(old_node, old_child) {
 			if (streq(old_child->name, new_child->name)) {
 				merge_nodes(old_child, new_child);
 				new_child = NULL;
@@ -346,14 +343,18 @@ void add_property(struct node *node, struct property *prop)
 
 void delete_property_by_name(struct node *node, char *name)
 {
-	struct property *prop = node->proplist;
+	struct property **pp = &node->proplist;
+
+	while (*pp) {
+		if (streq((*pp)->name, name)) {
+			struct property *prop = *pp;
 
-	while (prop) {
-		if (streq(prop->name, name)) {
+			/* Unlink it, so that adding it again starts afresh */
+			*pp = prop->next;
 			delete_property(prop);
 			return;
 		}
-		prop = prop->next;
+		pp = &(*pp)->next;
 	}
 }
 
@@ -390,19 +391,39 @@ void delete_node_by_name(struct node *parent, char *name)
 	}
 }
 
-void delete_node(struct node *node)
+static void delete_subtree(struct node *node)
 {
 	struct property *prop;
 	struct node *child;
 
 	node->deleted = 1;
 	for_each_child(node, child)
-		delete_node(child);
+		delete_subtree(child);
 	for_each_property(node, prop)
 		delete_property(prop);
 	delete_labels(&node->labels);
 }
 
+void delete_node(struct node *node)
+{
+	struct node **np;
+
+	/*
+	 * Unlink the node, so that adding it again starts afresh. Leave its
+	 * next_sibling alone, since a walk over its siblings may be at it
+	 */
+	if (node->parent) {
+		for (np = &node->parent->children; *np;
+		     np = &(*np)->next_sibling) {
+			if (*np == node) {
+				*np = node->next_sibling;
+				break;
+			}
+		}
+	}
+	delete_subtree(node);
+}
+
 void append_to_property(struct node *node,
 			char *name, const void *data, int len,
 			enum markertype type)
diff --git a/tests/delete_readd_order.dts b/tests/delete_readd_order.dts
new file mode 100644
index 0000000..91a5fa7
--- /dev/null
+++ b/tests/delete_readd_order.dts
@@ -0,0 +1,57 @@
+/dts-v1/;
+
+/*
+ * Delete properties and nodes in a later section and add them again. They
+ * come back as new entries after the existing ones, rather than returning
+ * to their old places along with their old subnodes
+ */
+
+/ {
+	first-prop;
+	moved-prop;
+	last-prop;
+
+	parent {
+		images {
+			old-image {
+			};
+			kept-image {
+				old;
+			};
+		};
+
+		other {
+		};
+	};
+
+	gone: gone-node {
+		old;
+	};
+
+	last-node {
+	};
+};
+
+/ {
+	/delete-property/ moved-prop;
+	moved-prop;
+
+	parent {
+		/delete-node/ images;
+		images {
+			new-image {
+			};
+			kept-image {
+				new;
+			};
+		};
+	};
+};
+
+/delete-node/ &gone;
+
+/ {
+	gone-node {
+		new;
+	};
+};
diff --git a/tests/delete_readd_order_ref.dts b/tests/delete_readd_order_ref.dts
new file mode 100644
index 0000000..7c86d0f
--- /dev/null
+++ b/tests/delete_readd_order_ref.dts
@@ -0,0 +1,28 @@
+/dts-v1/;
+
+/ {
+	first-prop;
+	last-prop;
+	moved-prop;
+
+	parent {
+		other {
+		};
+
+		images {
+			new-image {
+			};
+
+			kept-image {
+				new;
+			};
+		};
+	};
+
+	last-node {
+	};
+
+	gone-node {
+		new;
+	};
+};
diff --git a/tests/run_tests.sh b/tests/run_tests.sh
index 2650df6..8813846 100755
--- a/tests/run_tests.sh
+++ b/tests/run_tests.sh
@@ -746,6 +746,12 @@ dtc_tests () {
     run_sh_test "$SRCDIR/dtc-checkfails.sh" phandle_references \
 	-n duplicate_node_names -- -I dts -O dtb "$SRCDIR/delete_in_section_badref.dts"
 
+    run_dtc_test -I dts -O dtb -o delete_readd_order.test.dtb \
+	"$SRCDIR/delete_readd_order.dts"
+    run_dtc_test -I dts -O dtb -o delete_readd_order_ref.test.dtb \
+	"$SRCDIR/delete_readd_order_ref.dts"
+    run_test dtbs_equal_ordered delete_readd_order.test.dtb delete_readd_order_ref.test.dtb
+
     # Check some checks
     check_tests "$SRCDIR/dup-nodename.dts" duplicate_node_names
     check_tests "$SRCDIR/dup-propname.dts" duplicate_property_names
-- 
2.43.0

Re: [PATCH 1/2] dtc: Apply deletes in the section which has them

[Herve Codina]

Hi Simon,

On Mon, 26 Oct 2026 11:35:19 -0600
Simon Glass <sjg@chromium.org> wrote:

> The parser holds each /delete-property/ and /delete-node/ as a
> placeholder entry, flagged as deleted, among the node's properties or
> children. It only takes effect when merge_nodes() merges its section
> into an earlier one. In the first section of a dts it is ignored, so
> 'a; /delete-property/ a;' leaves 'a' in the tree. The same happens in
> any node which a later section adds, since merge_nodes() attaches a new
> child as it is. An ignored /delete-node/ also leaves its placeholder in
> the tree, which then shows up as '(null): Duplicate node name'
> 
> Apply each delete when its node is built, by dropping the earlier
> entries of the same name from that node. Nothing can refer to the node
> yet, so they can be unlinked rather than flagged as deleted. Keep the
> placeholder, so that merging the node into an earlier definition still
> deletes there too.
> 
> When a node joins the tree without being merged, as the first section,
> as a new child in merge_nodes() or as an overlay fragment, drop its
> placeholders, since there is nothing earlier for them to delete. This
> keeps placeholders and entries deleted within a section out of the tree,
> so that nothing which walks the tree has to skip them.
> 
> Duplicate entries within a section are still reported as errors, since
> nothing is merged.
> 
> Closes: https://github.com/dgibson/dtc/issues/37
> Assisted-by: Claude:claude-opus-5-5
> Signed-off-by: Simon Glass <sjg@chromium.org>
> ---
> 

LGTM.

Reviewed-by: Herve Codina <herve.codina@bootlin.com>

Best regards,
Hervé

Re: [PATCH 2/2] dtc: Remove a deleted node or property from the tree

[Herve Codina]

Hi Simon,

On Mon, 26 Oct 2026 11:35:20 -0600
Simon Glass <sjg@chromium.org> wrote:

> Deleting a node or property only flags it as deleted, leaving it in
> place. If a later section adds it again, merge_nodes() finds the flagged
> entry and revives it where it was, along with its subnodes, which come
> back in their old order before any new ones. So deleting a node in
> order to redefine it does not give the order which the source shows.
> 
> Unlink a node or property from its parent when deleting it, so that
> adding it again creates a new entry after the existing ones. Nothing
> deleted then stays in the tree while parsing, so merge_nodes() has
> nothing to revive and can skip deleted entries like everything else.
> 
> Leave the node's next_sibling alone, since fixup_omit_unused_nodes()
> deletes nodes while walking over their siblings.
> 
> Note that this changes the output of existing dts files. When a dts
> deletes a node or property and then defines it again, the new definition
> now comes after its siblings instead of taking the old one's place, and
> its subnodes come in the order of the new definition alone.

Yes, makes sense.

> 
> This is the better behaviour because:
> 
> - Deleting is how a dts says to start again. A dts which wants to keep a
>   node's place can override the node without deleting it, since merging
>   already updates a node in place
> - Node order can matter. In issue 174, U-Boot's binman builds an image
>   from a node which is deleted and defined again, yet the image comes
>   out in the old order. The only workaround is to define the nodes in
>   the wanted order before including the file which defines them
> - It matches the previous patch, in which a node deleted and defined
>   again within a section, or deleted in the first section and defined
>   by a later one, already comes out where the new definition is
> 
> Closes: https://github.com/dgibson/dtc/issues/174
> Assisted-by: Claude:claude-opus-5-5
> Signed-off-by: Simon Glass <sjg@chromium.org>
> ---

LGTM.

Reviewed-by: Herve Codina <herve.codina@bootlin.com>

Best regards,
Hervé

Re: [PATCH 1/2] dtc: Apply deletes in the section which has them

[David Gibson]

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

On Mon, Oct 26, 2026 at 11:35:19AM -0600, Simon Glass wrote:
> The parser holds each /delete-property/ and /delete-node/ as a
> placeholder entry, flagged as deleted, among the node's properties or
> children. It only takes effect when merge_nodes() merges its section
> into an earlier one. In the first section of a dts it is ignored, so
> 'a; /delete-property/ a;' leaves 'a' in the tree. The same happens in
> any node which a later section adds, since merge_nodes() attaches a new
> child as it is. An ignored /delete-node/ also leaves its placeholder in
> the tree, which then shows up as '(null): Duplicate node name'
> 
> Apply each delete when its node is built, by dropping the earlier
> entries of the same name from that node. Nothing can refer to the node
> yet, so they can be unlinked rather than flagged as deleted. Keep the
> placeholder, so that merging the node into an earlier definition still
> deletes there too.
> 
> When a node joins the tree without being merged, as the first section,
> as a new child in merge_nodes() or as an overlay fragment, drop its
> placeholders, since there is nothing earlier for them to delete. This
> keeps placeholders and entries deleted within a section out of the tree,
> so that nothing which walks the tree has to skip them.
> 
> Duplicate entries within a section are still reported as errors, since
> nothing is merged.
> 
> Closes: https://github.com/dgibson/dtc/issues/37
> Assisted-by: Claude:claude-opus-5-5
> Signed-off-by: Simon Glass <sjg@chromium.org>

I think this is an improvement over the current situation, hence,

Reviewed-by: David Gibson <david@gibson.dropbear.id.au>

However, there are some semantics that could do with tweaking further
in future.

> diff --git a/dtc-parser.y b/dtc-parser.y
> index e47f80d..0282f7b 100644
> --- a/dtc-parser.y
> +++ b/dtc-parser.y
> @@ -160,6 +160,7 @@ dt_ref: DT_LABEL_REF | DT_PATH_REF;
>  devicetree:
>  	  '/' nodedef
>  		{
> +			drop_delete_placeholders($2);
>  			$$ = name_node($2, "");
>  		}
>  	| devicetree '/' nodedef
> diff --git a/dtc.h b/dtc.h
> index 473552e..3e5109d 100644
> --- a/dtc.h
> +++ b/dtc.h
> @@ -277,6 +277,7 @@ struct node *omit_node_if_unused(struct node *node);
>  struct node *reference_node(struct node *node);
>  struct node *chain_node(struct node *first, struct node *list);
>  struct node *merge_nodes(struct node *old_node, struct node *new_node);
> +void drop_delete_placeholders(struct node *node);
>  struct node *add_orphan_node(struct node *old_node, struct node *new_node, char *ref);
>  
>  void add_property(struct node *node, struct property *prop);
> diff --git a/livetree.c b/livetree.c
> index abe73de..b474a05 100644
> --- a/livetree.c
> +++ b/livetree.c
> @@ -85,6 +85,68 @@ struct property *reverse_properties(struct property *first)
>  	return head;
>  }
>  
> +/*
> + * The parser holds each /delete-property/ and /delete-node/ as a placeholder
> + * entry, flagged as deleted, among the node's properties or children. Apply
> + * each one by dropping the earlier entries of the same name in the node. The
> + * placeholders stay, so that merging the node into an earlier definition
> + * deletes there too
> + */
> +static void apply_deletes(struct node *node)
> +{
> +	struct property *prop, **pp;
> +	struct node *child, **np;
> +
> +	for (prop = node->proplist; prop; prop = prop->next) {
> +		if (!prop->deleted)
> +			continue;
> +		for (pp = &node->proplist; *pp != prop;) {
> +			if (streq((*pp)->name, prop->name))
> +				*pp = (*pp)->next;
> +			else
> +				pp = &(*pp)->next;
> +		}

This leaks, but that's more or less accepted practice in dtc.

> +	}
> +
> +	for (child = node->children; child; child = child->next_sibling) {
> +		if (!child->deleted)
> +			continue;
> +		for (np = &node->children; *np != child;) {
> +			if (streq((*np)->name, child->name))
> +				*np = (*np)->next_sibling;
> +			else
> +				np = &(*np)->next_sibling;
> +		}
> +	}
> +}
> +
> +/*
> + * Drop the /delete-property/ and /delete-node/ placeholders from a subtree
> + * which joins the tree without being merged, since there is nothing earlier

I find this description a bit confusing.  I think the salient point is
that this is called on a subtree that's the first in the list of
things to be merged.

> + * for them to delete
> + */
> +void drop_delete_placeholders(struct node *node)
> +{
> +	struct property **pp = &node->proplist;
> +	struct node **np = &node->children;
> +
> +	while (*pp) {
> +		if ((*pp)->deleted)
> +			*pp = (*pp)->next;
> +		else
> +			pp = &(*pp)->next;
> +	}
> +
> +	while (*np) {
> +		if ((*np)->deleted) {
> +			*np = (*np)->next_sibling;
> +		} else {
> +			drop_delete_placeholders(*np);
> +			np = &(*np)->next_sibling;
> +		}
> +	}
> +}
> +
>  struct node *build_node(struct property *proplist, struct node *children,
>  			struct srcpos *srcpos)
>  {
> @@ -100,6 +162,7 @@ struct node *build_node(struct property *proplist, struct node *children,
>  	for_each_child(new, child) {
>  		child->parent = new;
>  	}
> +	apply_deletes(new);
>  
>  	return new;
>  }
> @@ -212,8 +275,10 @@ struct node *merge_nodes(struct node *old_node, struct node *new_node)
>  		}
>  
>  		/* if no collision occurred, add child to the old node. */
> -		if (new_child)
> +		if (new_child) {
> +			drop_delete_placeholders(new_child);

I think this is only correct if merges are always applied left to
right.  I think that's the case, but it's not terribly obvious right
here.  It effectively makes the merge operation non-associative, which
might be confusing.

>  			add_child(old_node, new_child);
> +		}
>  	}
>  
>  	old_node->srcpos = srcpos_extend(old_node->srcpos, new_node->srcpos);
> @@ -245,6 +310,8 @@ struct node * add_orphan_node(struct node *dt, struct node *new_node, char *ref)
>  		p = build_property("target", d, NULL);
>  	}
>  
> +	drop_delete_placeholders(new_node);
> +

Dropping placeholders here is semantically consistent, but possibly
risky.  Accepting a fragment with /delete/s without error might give
the impression that those deletes will take effect when the overlay is
applied, but that's not the case (runtime overlays have no mechanism
for encoding deletes).

I think it would be preferable to give an error if a fragment has any
unapplied delete markers.

>  	xasprintf(&name, "fragment@%u",
>  			next_orphan_fragment++);
>  	name_node(new_node, "__overlay__");
> diff --git a/tests/delete_in_section.dts b/tests/delete_in_section.dts
> new file mode 100644
> index 0000000..e742e79
> --- /dev/null
> +++ b/tests/delete_in_section.dts
> @@ -0,0 +1,125 @@
> +/dts-v1/;
> +
> +/*
> + * Delete properties and nodes defined earlier in the same section. This is
> + * the first section, so nothing is merged into an earlier one
> + */
> +
> +/ {
> +	#address-cells = <1>;
> +	#size-cells = <0>;
> +
> +	gone-prop;
> +	/delete-property/ gone-prop;
> +	kept-prop;
> +	again-prop = "old";
> +	/delete-property/ again-prop;
> +	again-prop = "new";
> +	both-prop;
> +
> +	/* Deleted and added again here, then changed by a later section */
> +	redel-prop = "old";
> +	/delete-property/ redel-prop;
> +	redel-prop = "new";
> +	reset-prop = "old";
> +	/delete-property/ reset-prop;
> +	reset-prop = "new";
> +
> +	gone-node {
> +	};
> +	/delete-node/ gone-node;
> +
> +	again-node {
> +		old;
> +	};
> +	/delete-node/ again-node;
> +	again-node {
> +		new;
> +	};
> +
> +	lbl: node {
> +		inner-prop;
> +		/delete-property/ inner-prop;
> +
> +		inner-node {
> +		};
> +		/delete-node/ inner-node;
> +	};
> +
> +	redel-node {
> +		old;
> +	};
> +	/delete-node/ redel-node;
> +	redel-node {
> +		new;
> +	};
> +
> +	remerge-node {
> +		old;
> +	};
> +	/delete-node/ remerge-node;
> +	remerge-node {
> +		new;
> +	};
> +
> +	/* Checks must not see what is deleted here */
> +	named-node {
> +		name = "other";
> +		/delete-property/ name;
> +	};
> +
> +	bus {
> +		#address-cells = <1>;
> +		#size-cells = <0>;
> +
> +		child@1 {
> +			reg = <1>;
> +		};
> +		/delete-node/ child@1;
> +	};
> +
> +	/* Deleted here, then added again by a later section */
> +	readd@1 {
> +		reg = <1>;
> +		old;
> +	};
> +	/delete-node/ readd@1;
> +	/delete-node/ placeholder@2;

I feel like not throwing an error on deletes of things that don't
exist is a footgun.

> +};
> +
> +/* Delete within nodes which a later section adds, and within the merge */
> +
> +/ {
> +	both-prop = "new";
> +	/delete-property/ both-prop;
> +	/delete-property/ redel-prop;
> +	reset-prop = "later";
> +
> +	new-node {
> +		new-prop;
> +		/delete-property/ new-prop;
> +		kept;
> +	};
> +
> +	/delete-node/ redel-node;
> +
> +	remerge-node {
> +		later;
> +	};
> +
> +	readd@1 {
> +		reg = <1>;
> +		later;
> +	};
> +
> +	placeholder@2 {
> +		reg = <2>;
> +	};
> +};
> +
> +&lbl {
> +	child {
> +		child-prop;
> +		/delete-property/ child-prop;
> +	};
> +};
> diff --git a/tests/delete_in_section_badref.dts b/tests/delete_in_section_badref.dts
> new file mode 100644
> index 0000000..79a40e4
> --- /dev/null
> +++ b/tests/delete_in_section_badref.dts
> @@ -0,0 +1,11 @@
> +/dts-v1/;
> +
> +/* A reference to a node deleted in the same section has nothing to refer to */
> +
> +/ {
> +	ref = <&gone>;
> +
> +	gone: node {
> +	};
> +	/delete-node/ node;
> +};
> diff --git a/tests/delete_in_section_labels.dts b/tests/delete_in_section_labels.dts
> new file mode 100644
> index 0000000..fbde838
> --- /dev/null
> +++ b/tests/delete_in_section_labels.dts
> @@ -0,0 +1,28 @@
> +/dts-v1/;
> +
> +/*
> + * A label moves to the new definition of a node deleted in the same
> + * section, and labels on deleted nodes stay out of __symbols__
> + */
> +
> +/ {
> +	ref = <&moved>;
> +
> +	moved: node {
> +		old;
> +	};
> +	/delete-node/ node;
> +	moved: node {
> +		new;
> +	};
> +
> +	gone: gone-node {
> +	};
> +	/delete-node/ gone-node;
> +};
> +
> +/ {
> +	later: later-node {
> +	};
> +	/delete-node/ later-node;
> +};
> diff --git a/tests/delete_in_section_labels_ref.dts b/tests/delete_in_section_labels_ref.dts
> new file mode 100644
> index 0000000..5d8cf38
> --- /dev/null
> +++ b/tests/delete_in_section_labels_ref.dts
> @@ -0,0 +1,9 @@
> +/dts-v1/;
> +
> +/ {
> +	ref = <&moved>;
> +
> +	moved: node {
> +		new;
> +	};
> +};
> diff --git a/tests/delete_in_section_overlay.dts b/tests/delete_in_section_overlay.dts
> new file mode 100644
> index 0000000..e3e8f71
> --- /dev/null
> +++ b/tests/delete_in_section_overlay.dts
> @@ -0,0 +1,21 @@
> +/dts-v1/;
> +/plugin/;
> +
> +/* Delete within the fragments of an overlay */
> +
> +&target {
> +	a;
> +	/delete-property/ a;
> +	b;
> +	/delete-property/ c;
> +
> +	gone {
> +	};
> +	/delete-node/ gone;
> +	/delete-node/ d;
> +};
> +
> +&{/path} {
> +	p;
> +	/delete-property/ p;
> +};
> diff --git a/tests/delete_in_section_overlay_ref.dts b/tests/delete_in_section_overlay_ref.dts
> new file mode 100644
> index 0000000..48f36b3
> --- /dev/null
> +++ b/tests/delete_in_section_overlay_ref.dts
> @@ -0,0 +1,9 @@
> +/dts-v1/;
> +/plugin/;
> +
> +&target {
> +	b;
> +};
> +
> +&{/path} {
> +};
> diff --git a/tests/delete_in_section_ref.dts b/tests/delete_in_section_ref.dts
> new file mode 100644
> index 0000000..20d459a
> --- /dev/null
> +++ b/tests/delete_in_section_ref.dts
> @@ -0,0 +1,44 @@
> +/dts-v1/;
> +
> +/ {
> +	#address-cells = <1>;
> +	#size-cells = <0>;
> +	kept-prop;
> +	again-prop = "new";
> +	reset-prop = "later";
> +
> +	again-node {
> +		new;
> +	};
> +
> +	lbl: node {
> +		child {
> +		};
> +	};
> +
> +	remerge-node {
> +		new;
> +		later;
> +	};
> +
> +	named-node {
> +	};
> +
> +	bus {
> +		#address-cells = <1>;
> +		#size-cells = <0>;
> +	};
> +
> +	new-node {
> +		kept;
> +	};
> +
> +	readd@1 {
> +		reg = <1>;
> +		later;
> +	};
> +
> +	placeholder@2 {
> +		reg = <2>;
> +	};
> +};
> diff --git a/tests/run_tests.sh b/tests/run_tests.sh
> index 842b543..2650df6 100755
> --- a/tests/run_tests.sh
> +++ b/tests/run_tests.sh
> @@ -725,6 +725,27 @@ dtc_tests () {
>      run_dtc_test -I dts -O dts -o delete_reinstate_multilabel.dts.test.dts "$SRCDIR/delete_reinstate_multilabel.dts"
>      run_wrap_test cmp delete_reinstate_multilabel.dts.test.dts "$SRCDIR/delete_reinstate_multilabel_ref.dts"
>  
> +    # Check deletes within the section which has them
> +    run_dtc_test -E reg_format -E avoid_unnecessary_addr_size -I dts -O dtb \
> +	-o delete_in_section.test.dtb "$SRCDIR/delete_in_section.dts"
> +    run_dtc_test -I dts -O dtb -o delete_in_section_ref.test.dtb \
> +	"$SRCDIR/delete_in_section_ref.dts"
> +    run_test dtbs_equal_ordered delete_in_section.test.dtb delete_in_section_ref.test.dtb
> +    run_dtc_test -@ -I dts -O dtb -o delete_in_section_labels.test.dtb \
> +	"$SRCDIR/delete_in_section_labels.dts"
> +    run_dtc_test -@ -I dts -O dtb -o delete_in_section_labels_ref.test.dtb \
> +	"$SRCDIR/delete_in_section_labels_ref.dts"
> +    run_test dtbs_equal_ordered delete_in_section_labels.test.dtb \
> +	delete_in_section_labels_ref.test.dtb
> +    run_dtc_test -I dts -O dtb -o delete_in_section_overlay.test.dtb \
> +	"$SRCDIR/delete_in_section_overlay.dts"
> +    run_dtc_test -I dts -O dtb -o delete_in_section_overlay_ref.test.dtb \
> +	"$SRCDIR/delete_in_section_overlay_ref.dts"
> +    run_test dtbs_equal_ordered delete_in_section_overlay.test.dtb \
> +	delete_in_section_overlay_ref.test.dtb
> +    run_sh_test "$SRCDIR/dtc-checkfails.sh" phandle_references \
> +	-n duplicate_node_names -- -I dts -O dtb "$SRCDIR/delete_in_section_badref.dts"
> +
>      # Check some checks
>      check_tests "$SRCDIR/dup-nodename.dts" duplicate_node_names
>      check_tests "$SRCDIR/dup-propname.dts" duplicate_property_names
> -- 
> 2.43.0
> 
> 

-- 
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 --]