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. | Rule | Applies to | Result | | --- | --- | --- | | `merge` | two mappings | Keys present on one side only are copied. Keys present on both sides are merged recursively, each under its own rule. | | `replace` | any two nodes | The overlay node. | | `keep` | any two nodes | The base node. | | `append` | two lists | The base items followed by the overlay items. | | `merge_by_key:<field>` | two lists of mappings | Items whose `<field>` values are equal are merged recursively. Base items keep their order; overlay items with no match follow, in overlay order. | 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. ```python Node = dict | list | str | int | float | bool | None def merge_trees(base: Node, overlay: Node, rules: dict[str, str]) -> Node: ... ``` **Example** Base file: ```yaml service: name: api replicas: 2 ports: [80] env: - name: LOG_LEVEL value: info - name: REGION value: us-east ``` Overlay file: ```yaml 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: ```yaml service: name: api replicas: 5 ports: [80, 443] env: - name: LOG_LEVEL value: debug - name: REGION value: us-east - name: FEATURE_FLAG value: enabled ``` ```hint Keep the walk and the rules apart Write the recursive walk so that it never needs to know what any particular rule does. Work out what information a rule needs from the walk in order to do its job. ``` ```hint Who decides whether to descend? Some rules need the children of a node merged one by one, and others produce their result without looking inside. Decide which part of your code should make that call. ``` ### 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? ### What a Strong Answer Covers - Turns the long statement and its examples into a precise rule table, including defaults, before coding, and checks the design against every example - A depth-first merge that carries the current path, looks up the rule at each pair of nodes and dispatches through a registry, so a new rule touches one place - Correct handling of one-sided keys, list items matched by a key field, result ordering, and type mismatches, with error messages that name the path - A result that neither modifies the input trees nor shares mutable nodes with them - Running time linear in the number of nodes, awareness of the recursion depth limit, and tests drawn from the examples plus edge cases ### Follow-up Questions - Rules may now be patterns such as `*.env` or `services.*.ports`. How do you match them efficiently, and which rule wins when two patterns match one node? - Three files are layered: defaults, an environment file and a local override. Does merging them pairwise give the same result for either grouping? - Users ask which file each value in the result came from. How would you record that? - Add a `delete` rule, and let the overlay file request a rule for one of its own nodes. What changes in your design?