Repository: opendilab/treevalue (language: python)

Issue:
Something is wrong when the inherit value is missing.
- [x] I have marked all applicable categories:
    + [ ] installation bug
    + [ ] exception-raising bug
    + [ ] data model bug
    + [ ] tree utils bug
    + [x] function treelize bug (including method and classmethod)
    + [ ] code design/refactor
    + [ ] documentation request
    + [ ] new feature request
- [x] I have visited the [readme](https://github.com/opendilab/treevalue/blob/main/README.md) and [doc](https://opendilab.github.io/treevalue/main/index.html)
- [x] I have searched through the [issue tracker](https://github.com/opendilab/treevalue/issues) and [pr tracker](https://github.com/opendilab/treevalue/pulls)
- [x] I have mentioned version numbers, operating system and environment, where applicable:

```python
import sys

import treevalue

print(treevalue.__version__, sys.version, sys.platform)
```

Version 1.0.0, python 3.9.6 (should be independent of python's version)

The following code

python
```
from treevalue import func_treelize, FastTreeValue


@func_treelize(mode='outer', missing=lambda: [])
def append(arr: list, *args):
    print(arr, args)
    for item in args:
        if item:
            arr.append(item)
    return arr


t0 = FastTreeValue({})
t1 = FastTreeValue({'a': 2, 'x': {'c': 4, 'd': 9}})
t2 = FastTreeValue({'a': 4, 'b': 48, 'x': {'d': 54}})
t3 = FastTreeValue({'b': -12, 'x': 7, 'y': {'e': 3, 'f': 4}})

tr = append(t0, t1, t2, t3)
```

`treevalue graph`'s dumped graph is

![test_graph_10](https://user-images.githubusercontent.com/20508435/140470107-a8500fd1-3467-4535-9e43-93c89e244c04.png)

tr.x's value is obviously incorrect.




Discussion / hints:
The following code can also recurrence the bug

```python
t0 = FastTreeValue({})
t1 = FastTreeValue({'a': 2, 'b': 7, 'x': {'c': 4, 'd': 9}})
t2 = FastTreeValue({'a': 4, 'b': 48, 'x': {'c': -11, 'd': 54}})
t3 = FastTreeValue({'a': 9, 'b': -12, 'x': {'c': 3, 'd': 4}})

tr = append(t0, t1, t2, t3)
```

Fix patch:
diff --git a/treevalue/tree/func/cfunc.pyx b/treevalue/tree/func/cfunc.pyx
index 0ad9a0bec3..3c6f0a36a3 100644
--- a/treevalue/tree/func/cfunc.pyx
+++ b/treevalue/tree/func/cfunc.pyx
@@ -12,6 +12,8 @@ from ..common.storage cimport TreeStorage
 from ..tree.structural cimport _c_subside, _c_rise
 from ..tree.tree cimport TreeValue
 
+_VALUE_IS_MISSING = SingletonMark('value_is_missing')
+
 cdef object _c_func_treelize_run(object func, list args, dict kwargs,
                                  _e_tree_mode mode, bool inherit, bool allow_missing, object missing_func):
     cdef list ck_args = []
@@ -33,8 +35,24 @@ cdef object _c_func_treelize_run(object func, list args, dict kwargs,
         else:
             ck_kwargs.append((k, v, False))
 
+    cdef list _a_args
+    cdef dict _a_kwargs
     if not has_tree:
-        return func(*args, **kwargs)
+        _a_args = []
+        for v in args:
+            if v is not _VALUE_IS_MISSING:
+                _a_args.append(v)
+            else:
+                _a_args.append(missing_func())
+
+        _a_kwargs = {}
+        for k, v in kwargs.items():
+            if v is not _VALUE_IS_MISSING:
+                _a_kwargs[k] = v
+            else:
+                _a_kwargs[k] = missing_func()
+
+        return func(*_a_args, **_a_kwargs)
 
     cdef dict _d_res = {}
     cdef str ak
@@ -51,7 +69,7 @@ cdef object _c_func_treelize_run(object func, list args, dict kwargs,
                     _l_args.append(av[k])
                 except KeyError:
                     if allow_missing:
-                        _l_args.append(missing_func())
+                        _l_args.append(_VALUE_IS_MISSING)
                     else:
                         raise KeyError("Missing is off, key {key} not found in {item}.".format(
                             key=repr(k), item=repr(av),
@@ -71,7 +89,7 @@ cdef object _c_func_treelize_run(object func, list args, dict kwargs,
                     _d_kwargs[ak] = av[k]
                 except KeyError:
                     if allow_missing:
-                        _d_kwargs[ak] = missing_func()
+                        _d_kwargs[ak] = _VALUE_IS_MISSING
                     else:
                         raise KeyError("Missing is off, key {key} not found in {item}.".format(
                             key=repr(k), item=repr(av),


Test patch:
diff --git a/test/tree/func/test_func.py b/test/tree/func/test_func.py
index bdce667d6f..124b2342ad 100644
--- a/test/tree/func/test_func.py
+++ b/test/tree/func/test_func.py
@@ -217,3 +217,43 @@ def plus(cls, x, y):
                 return x + y
 
         assert MyTreeValue.plus(TreeValue({'a': 1, 'b': 2}), 2) == MyTreeValue({'a': 3, 'b': 4})
+
+    def test_missing(self):
+        @func_treelize(mode='outer', missing=lambda: [])
+        def append(arr: list, *args):
+            for item in args:
+                if item:
+                    arr.append(item)
+            return arr
+
+        t0 = TreeValue({})
+        t1 = TreeValue({'a': 2, 'b': 7, 'x': {'c': 4, 'd': 9}})
+        t2 = TreeValue({'a': 4, 'b': 48, 'x': {'c': -11, 'd': 54}})
+        t3 = TreeValue({'a': 9, 'b': -12, 'x': {'c': 3, 'd': 4}})
+
+        assert append(t0, t1, t2, t3) == TreeValue({
+            'a': [2, 4, 9],
+            'b': [7, 48, -12],
+            'x': {
+                'c': [4, -11, 3],
+                'd': [9, 54, 4],
+            }
+        })
+
+        t0 = TreeValue({})
+        t1 = TreeValue({'a': 2, 'x': {'c': 4, 'd': 9}})
+        t2 = TreeValue({'a': 4, 'b': 48, 'x': {'d': 54}})
+        t3 = TreeValue({'b': -12, 'x': 7, 'y': {'e': 3, 'f': 4}})
+
+        assert append(t0, t1, t2, t3) == TreeValue({
+            'a': [2, 4],
+            'b': [48, -12],
+            'x': {
+                'c': [4, 7],
+                'd': [9, 54, 7],
+            },
+            'y': {
+                'e': [3],
+                'f': [4],
+            },
+        })