Merge Two YAML Configuration Trees with Per-Node Merge Rules

You are given two configuration trees, each parsed from a YAML file: a base tree and an overlay tree. Implement a function that merges them into a single tree.

After parsing, every node is a mapping (string keys to child nodes), a list of nodes, or a scalar (a string, number, boolean or null). The merge behavior is decided node by node: each node can have its own merge rule, and there are many rules. Walk both trees together and, at every pair of corresponding nodes, find the rule that applies and carry it out.

The original statement described a long list of rules through lengthy worked examples, and that exact list was not preserved. Practice with the representative set below, and treat it as open-ended: adding a new rule should not require rewriting the traversal.

Rules arrive as a table keyed by node path, for example {"service.env": "merge_by_key:name"}. A node with no entry in the table uses merge when both sides are mappings and replace otherwise.

Node = dict | list | str | int | float | bool | None

def merge_trees(base: Node, overlay: Node, rules: dict[str, str]) -> Node:
 ...

Example

Base file:

service:
 name: api
 replicas: 2
 ports: [80]
 env:
 - name: LOG_LEVEL
 value: info
 - name: REGION
 value: us-east

Overlay file:

service:
 replicas: 5
 ports: [443]
 env:
 - name: LOG_LEVEL
 value: debug
 - name: FEATURE_FLAG
 value: enabled

Rules: {"service.ports": "append", "service.env": "merge_by_key:name"}

Merged result:

service:
 name: api
 replicas: 5
 ports: [80, 443]
 env:
 - name: LOG_LEVEL
 value: debug
 - name: REGION
 value: us-east
 - name: FEATURE_FLAG
 value: enabled

Constraints and Clarifications

• A path joins mapping keys from the root with dots, such as service.env. Every item of a list shares the list's path followed by [], so service.env[].value addresses the value field of each item in service.env. The root's path is the empty string.
• A rule only decides how a node that exists on both sides is combined. A key present on only one side is copied into the result unchanged.
• In a merged mapping, the base keys come first in base order, followed by the overlay-only keys in overlay order.

Clarifying Questions

• How are rules attached in the real input: by exact path, by key name anywhere in the tree, by wildcard patterns, or by markers inside the YAML files themselves? If two of them match the same node, which wins?
• What should happen when the two sides of a path have different types, such as a mapping in the base and a scalar in the overlay, or when a rule meets node types it does not support: fail, or let the overlay win?
• Does an explicit null in the overlay set the value to null, or remove the key?
• For merge_by_key, what if an item lacks the key field, or two items on the same side share a key value?
• May the input trees be modified in place, or must the result be a new tree?