Repository: omni-us/jsonargparse

Issue:
Incorrect instantiation order with nested dependency injection
<!-- If you like this project, please ⭐ star it https://github.com/omni-us/jsonargparse/ -->

## 🐛 Bug report
First of all, this is a really cool project, and I am enjoying it a lot 👍 .
This might be quite niche to be honest, but I encountered unexpected behavior when working on nested classes.
In my use case, the user can choose from multiple loss classes (`Strategy` in the example), which on their own have another nested dependency injection (`NestedStrategy`).
Furthermore, some arguments of the loss are linked to (`StrategyParameter`) and the nested strategy has also arguments provided from somewhere else (`NestedParameter`).

Now in this setting I found that the instantiation order induced by the topological sort of the dependency graph does not enforce that `NestedParameter` is instantiated before `Strategy`.
But when instantiating the `Strategy` object, all actions which target the nested strategy are triggered too.
So in particular the link
```python
parser.link_arguments(
        "nested_param",
        "root.strategy.init_args.nested.init_args.nested_param",
        apply_on="instantiate",
        compute_fn=compute_fn,
    )
```
is triggered however before `NestedStrategy` was instantiated and so the compute_fn is called with the `Namespace` object.

I am not sure whether the graph should contain the dependency or the instantiation logic should not instantiate the actions leading to the nested class?
In `ActionLink.apply_instantiation_links` there is this predicate `is_nested_instantiation_link` (returning False) which hints at the second case being true?

This is how the dependency graph looks like as constructed in `ActionLink.instantiation_order`:
```mermaid
stateDiagram-v2
    nested_param --> root.strategy.init_args.nested,
    param --> root.strategy
```

### To reproduce
I tried to keep the example as small as possible.
We have two dependency injected classes `Strategy` and `NestedStrategy` and two objects which are used for linking `StrategyParameter` and `NestedParameter`.

```python
from jsonargparse import ArgumentParser

class NestedStrategy:

    def __init__(self, nested_param: str):
        self.nested_param = nested_param


class Strategy:

    def __init__(self, param: str, nested: NestedStrategy):
        self.param = param
        self.nested = nested


class Root:

    def __init__(self, strategy: Strategy):
        self.strategy = strategy


class NestedParameter:
    def __init__(self, something_else: str):
        self._something_else = something_else


class StrategyParameter:

    def __init__(self, something: str):
        self.something = something


def compute_fn(nested_param: NestedParameter):
    assert isinstance(
        nested_param, NestedParameter
    ), f"Got wrong type {type(nested_param)}"
    return nested_param


if __name__ == "__main__":
    parser = ArgumentParser()

    parser.add_class_arguments(Root, "root")
    parser.add_class_arguments(NestedParameter, "nested_param")
    parser.add_class_arguments(StrategyParameter, "param")
    parser.link_arguments(
        "nested_param",
        "root.strategy.init_args.nested.init_args.nested_param",
        apply_on="instantiate",
        compute_fn=compute_fn,
    )
    parser.link_arguments(
        "param.param", "root.strategy.init_args.param", apply_on="instantiate"
    )
    parser.add_argument("--config", action="config")
    cfg = parser.parse_args(["--config", "config.yaml"])
    init_cfg = parser.instantiate_classes(cfg)
```

```yaml
root:
  strategy:
    class_path: Strategy
    init_args:
      nested:
        class_path: NestedStrategy
nested_param:
  something_else: "Something Else"

param:
  something: "something"

```

#### Output
```
ValueError: Call to compute_fn of link 'compute_fn(nested_param) --> root.strategy.init_args.nested.init_args.nested_param' with args (Namespace(something_else='Something Else')) failed: Got wrong type. Expected NestedParameter but got <class 'jsonargparse._namespace.Namespace'>
```


### Expected behavior

The `NestedParameter` class is instantiated before passed as parameter to the `compute_fn`.
Note, the `compute_fn` is only to showcase the problem but not necessary to reproduce the bug.

### Environment

- jsonargparse version: jsonargparse 4.34.0
- Python version: Python 3.10.14
- How jsonargparse was installed: pip
- OS: macOS

Hints from issue comments:
@mauvilsa: Thank you for reporting! I will look at it.@jkrude: Any updates on this issue? I have run into it multiple times by now. Let me know if I can help to fix it.@mauvilsa: I did have a look at this. I noticed that when adding links an directed acyclic graph (DAG) is used to check that the links make sense. But during instantiation a DAG is not used to determine the order. Adding the DAG to the instantiation is a complex task. I haven't had time to work on it. If you want to help, you could take a look at the code and maybe describe here a potential proposal on how to implement it. But as I said, it is not simple.

I do wonder why only you have reported this problem. It is quite an obvious bug, but it seems in practice it doesn't happen often.@jkrude: Thanks for the quick response. Correct me if I am wrong, but the topological sort of the constructed DAG *is* used to determine the instantiation order of components in `instantiate_classes` [here](https://github.com/omni-us/jsonargparse/blob/2285c1a21eb455f0a702da552e84493778ad4d83/jsonargparse/_core.py#L1199) right?
First, to clarify here is how I understand what happens in my example:

In my example, the call to `ActionLink.instantiation_order(self)` results in the induced action-link-order of  
`[param, root.strategy, nested_param, root.strategy.init_args.nested]`, 
notice how `root.strategy` comes before `root.strategy.init_args.nested`.

Based on the action-link-order, the components are reordered to 
`['param.something', 'param', 'root.strategy', 'nested_param.something_else', 'nested_param', 'root']`.

Following this order, the `param.something` and `param` (e.g., the class `StrategyParameter`) are instantiated first.
Secondly, the component  `root.strategy` is instantiated, e.g., the class `Strategy`.

Before the class itself is instantiated, `apply_instantiation_links` is called with  `target='root.strategy'`.
Here, the relevant action-links are filtered out. In my example, those are:
`['compute_fn(nested_param) --> root.strategy.init_args.nested.init_args.nested_param', 'param.param --> root.strategy.init_args.param']`.

At this point inside `apply_instantiation_links`, it is assumed that the sources for each action-link are already instantiated.
And thus in line [361](https://github.com/omni-us/jsonargparse/blob/2285c1a21eb455f0a702da552e84493778ad4d83/jsonargparse/_link_arguments.py#L361) the error is triggered as `nested_param` is not yet instantiated.

In general, this looks like:
- Instantiate classes `instantiate_classes`
	- Sort components by length-of split-key -> ensures that `root.strategy` is instantiated before `root`
	- Sort by action links via topological sort
	- Instantiate individual components
		- Instantiate all action-links `ActionLink.apply_instantiation_links(self, cfg, target=component.dest)`
			- Filter for `target_key == target or target_key.startswith(f"{target}.")` -> 'root.strategy.init_args.nested.init_args.nested_param' starts with 'root.strategy'
		- Instantiate the component itself -> triggers recursive call to `instantiate_classes` for subcomponents -> instantiates `root.strategy.init_args.nested`

If I understand this quite complex logic correctly, there are at least three rules we have to consider:
1. Instantiate action-sources before action-targets
2. Instantiate subcomponents before parent-components
3. Instantiate action-link-sources of subcomponents before instantiating parent-components.

The last rule is the critical in our case, which is not enforced by any mechanism.

Looking at the logic described above, we need to make sure that the sources of action-links to `root.strategy` were instantiated before, e.g., that `nested_param` was instantiated.
In this case, I would argue for an additional dependency in our action-link-DAG, adding an edge between a classes' `init_args` and itself.
So the expected graph would look like:
```mermaid
stateDiagram-v2
    nested_param --> root.strategy.init_args.nested
    root.strategy.init_args.nested --> root.strategy
    param --> root.strategy
```
Instead of the one posted above.
This should guarantee the component initialization of:
['param.something', 'param', 'nested_param.something_else', 'nested_param', 'root.strategy', 'root']

I hope you made it this far and this rather long description makes some sense :)@mauvilsa: > Thanks for the quick response. Correct me if I am wrong, but the topological sort of the constructed DAG _is_ used to determine the instantiation order of components in `instantiate_classes` [here](https://github.com/omni-us/jsonargparse/blob/2285c1a21eb455f0a702da552e84493778ad4d83/jsonargparse/_core.py#L1199) right?

Oh, you are right. Not sure why I had this in mind. I must have gotten confused with something else. I will take another look.@mauvilsa: I created pull request #662 with hopefully the fix. Please review and test.

The code snippet above had some issues so I had to change it a bit. See the test https://github.com/omni-us/jsonargparse/pull/662/files#diff-911b02ee18fa5c88fe775f9d0de98b387b537757ec95af835f485649ed3a86f7@jkrude: Awesome, that fixes my issue 👍. Sorry for the malformed example ^^@mauvilsa: Thank you for the great analysis! Certainly made fixing it way easier.

Solution patch:
diff --git a/CHANGELOG.rst b/CHANGELOG.rst
index 38345d18..19c2a294 100644
--- a/CHANGELOG.rst
+++ b/CHANGELOG.rst
@@ -21,6 +21,11 @@ Added
   ``add_argument`` (`#661
   <https://github.com/omni-us/jsonargparse/pull/661>`__).
 
+Fixed
+^^^^^
+- Incorrect instantiation order when instantiation targets share a parent (`#662
+  <https://github.com/omni-us/jsonargparse/pull/662>`__).
+
 
 v4.36.0 (2025-01-17)
 --------------------
diff --git a/jsonargparse/_link_arguments.py b/jsonargparse/_link_arguments.py
index 96b50a0a..2c08b0ba 100644
--- a/jsonargparse/_link_arguments.py
+++ b/jsonargparse/_link_arguments.py
@@ -18,7 +18,7 @@
     _find_parent_action,
     filter_default_actions,
 )
-from ._namespace import Namespace, split_key_leaf
+from ._namespace import Namespace, split_key, split_key_leaf
 from ._parameter_resolvers import get_signature_parameters
 from ._type_checking import ArgumentGroup, ArgumentParser
 
@@ -81,7 +81,10 @@ def add_edge(self, source, target):
         for node in [source, target]:
             if node not in self.nodes:
                 self.nodes.append(node)
-        self.edges_dict[self.nodes.index(source)].append(self.nodes.index(target))
+        source_targets_list = self.edges_dict[self.nodes.index(source)]
+        target_index = self.nodes.index(target)
+        if target_index not in source_targets_list:
+            source_targets_list.append(target_index)
 
     def get_topological_order(self):
         exploring = [False] * len(self.nodes)
@@ -97,7 +100,7 @@ def topological_sort(self, source, exploring, visited, order):
         for target in self.edges_dict[source]:
             if exploring[target]:
                 raise ValueError(
-                    f"Graph has cycles, found while checking {self.nodes[source]} --> " + self.nodes[target]
+                    f"Graph has cycles, found while checking {self.nodes[source]} --> {self.nodes[target]}"
                 )
             elif not visited[target]:
                 self.topological_sort(target, exploring, visited, order)
@@ -406,11 +409,27 @@ def set_target_value(action: "ActionLink", value: Any, cfg: Namespace, logger) -
     def instantiation_order(parser):
         actions = get_link_actions(parser, "instantiate")
         if actions:
+            targets = set()
             graph = DirectedGraph()
+
+            # Add instantiation links as edges
             for action in actions:
                 target = re.sub(r"\.init_args$", "", split_key_leaf(action.target[0])[0])
                 for _, source_action in action.source:
                     graph.add_edge(source_action.dest, target)
+                targets.add(target)
+
+            # Add instantiation target prefixes as edges
+            targets = sorted(targets, key=lambda x: len(split_key(x)))
+            seen_targets = {targets[0]}
+            for target in targets[1:]:
+                parts = [x.replace("|", ".") for x in target.replace("init_args.", "init_args|").split(".")]
+                for num in range(len(parts) - 1):
+                    target_prefix = ".".join(parts[: num + 1])
+                    if target_prefix in seen_targets:
+                        graph.add_edge(target, target_prefix)
+                seen_targets.add(target)
+
             return graph.get_topological_order()
         return []
 
diff --git a/jsonargparse/_signatures.py b/jsonargparse/_signatures.py
index b16ebddf..48d27e72 100644
--- a/jsonargparse/_signatures.py
+++ b/jsonargparse/_signatures.py
@@ -351,9 +351,11 @@ def _add_signature_parameter(
             annotation = Any
             default = None if is_required else default
             is_required = False
+        is_required_link_target = False
         if is_required and linked_targets is not None and name in linked_targets:
             default = None
             is_required = False
+            is_required_link_target = True
         if (
             kind in {kinds.VAR_POSITIONAL, kinds.VAR_KEYWORD}
             or (not is_required and name[0] == "_")
@@ -371,7 +373,7 @@ def _add_signature_parameter(
             kwargs["help"] = param.doc
         if not is_required:
             kwargs["default"] = default
-            if default is None and not is_optional(annotation, object):
+            if default is None and not is_optional(annotation, object) and not is_required_link_target:
                 annotation = Optional[annotation]
         elif not as_positional:
             kwargs["required"] = True


Test patch:
diff --git a/jsonargparse_tests/test_link_arguments.py b/jsonargparse_tests/test_link_arguments.py
index 2b341545..fbbd1707 100644
--- a/jsonargparse_tests/test_link_arguments.py
+++ b/jsonargparse_tests/test_link_arguments.py
@@ -826,6 +826,80 @@ def test_on_instantiate_within_deeper_subclass(parser, caplog):
     assert "Applied link 'encoder.output_channels --> decoder.init_args.input_channels'" in caplog.text
 
 
+class SourceA:
+    def __init__(self, param_a: str):
+        self.attr_a = param_a
+
+
+class SourceB:
+    def __init__(self, param_b: str):
+        self.attr_b = param_b
+
+
+class HierarchyGrandchild:
+    def __init__(self, param_grandchild: str):
+        self.attr_grandchild = param_grandchild
+
+
+class HierarchyChild:
+    def __init__(self, param_child: str, grandchild: HierarchyGrandchild):
+        self.attr_child = param_child
+        self.grandchild = grandchild
+
+
+class HierarchyRoot:
+    def __init__(self, child: HierarchyChild):
+        self.child = child
+
+
+def get_source_a_attr(source_a):
+    assert isinstance(source_a, SourceA)
+    return source_a.attr_a
+
+
+def test_on_instantiate_targets_share_parent(parser):
+    config = {
+        "source_a": {
+            "param_a": "value a",
+        },
+        "source_b": {
+            "param_b": "value b",
+        },
+        "root": {
+            "child": {
+                "class_path": "HierarchyChild",
+                "init_args": {
+                    "grandchild": {
+                        "class_path": "HierarchyGrandchild",
+                    },
+                },
+            },
+        },
+    }
+    parser.add_argument("--config", action="config")
+    parser.add_class_arguments(SourceA, "source_a")
+    parser.add_class_arguments(SourceB, "source_b")
+    parser.add_class_arguments(HierarchyRoot, "root")
+    parser.link_arguments(
+        "source_a",
+        "root.child.init_args.grandchild.init_args.param_grandchild",
+        apply_on="instantiate",
+        compute_fn=get_source_a_attr,
+    )
+    parser.link_arguments("source_b.attr_b", "root.child.init_args.param_child", apply_on="instantiate")
+    cfg = parser.parse_args([f"--config={json.dumps(config)}"])
+    init = parser.instantiate_classes(cfg)
+    assert isinstance(init.source_a, SourceA)
+    assert isinstance(init.source_b, SourceB)
+    assert isinstance(init.root, HierarchyRoot)
+    assert isinstance(init.root.child, HierarchyChild)
+    assert isinstance(init.root.child.grandchild, HierarchyGrandchild)
+    assert init.source_a.attr_a == "value a"
+    assert init.root.child.grandchild.attr_grandchild is init.source_a.attr_a
+    assert init.source_b.attr_b == "value b"
+    assert init.root.child.attr_child is init.source_b.attr_b
+
+
 # link creation failures