1
0
Fork
You've already forked mpath
0

Empty results from resolve can be incorrectly sized #31

Closed
opened 2026年07月02日 01:53:54 +02:00 by UserCurt · 8 comments

There are circumstances where resolve should return an empty result. However, the size of the returned array can be incorrect. There are two main circumstances:

First, if the supplied input is empty, resolve will always return a ×ばつ0

  • Expected result: An empty array of the same size

Second, if the supplied input is not empty but the path yields no results, resolve will always return either a:

  • ×ばつ0 if there is at least one DotSet and DotGlob where the N is the length of the DotSet most closest to but preceding the first DotGlob
  • ×ばつ1 otherwise
  • Expected result: An empty array where the only zero dimensions should be those corresponding to segments with no dot matches

Both circumstances can violate the contract where repeated application of resolve should not effect result if all or all but the first use the default BundlingAlgorithm="shrink".

data.A = struct(X=1, Y=2);
mp = mpath.Pointer("/A/*/*");
r1 = mp.resolve(data);
r2 = r1.resolve(data);
size(r1) % [0 1]
size(r2) % [0 0]

In this example, the size of r1 is expected to be ×ばつ0, and the size of r2 is expected to match the size of r1.

Additional examples, each expected ×ばつ0:

mpath.resolve(data, "/A/*/*") % ×ばつ1
mpath.resolve(data, "/A/{X,Y}/*") % ×ばつ0
mpath.resolve(data, "/A/*/{X,Y}") % ×ばつ1
mpath.resolve(data, "/A/{X,Y}/{X,Y}") % ×ばつ1

This issue report may involve two related bugs

  • Size returned by resolve should be zero along dimensions corresponding to segments failing to produce matches
  • Size returned by resolve should retain the original size if empty

In the current implementation, reshapeResolvedResult specially treats all-null data-derived matcher results via emptyAllNullDataMatcherResult. That helper does not run the normal dimension assignment logic and currently only special-cases the first DotGlob and a preceding DotSet, so it cannot express general empty shape semantics.

There are circumstances where `resolve` should return an empty result. However, the size of the returned array can be incorrect. There are two main circumstances: First, if the supplied input is empty, `resolve` will always return a ×ばつ0 - Expected result: An empty array of the same size Second, if the supplied input is not empty but the path yields no results, `resolve` will always return either a: - ×ばつ0 if there is at least one `DotSet` and `DotGlob` where the N is the length of the `DotSet` most closest to but preceding the first `DotGlob` - ×ばつ1 otherwise - Expected result: An empty array where the only zero dimensions should be those corresponding to segments with no dot matches Both circumstances can violate the contract where repeated application of `resolve` should not effect result if all or all but the first use the default `BundlingAlgorithm="shrink"`. ```matlab data.A = struct(X=1, Y=2); mp = mpath.Pointer("/A/*/*"); r1 = mp.resolve(data); r2 = r1.resolve(data); size(r1) % [0 1] size(r2) % [0 0] ``` In this example, the size of `r1` is expected to be ×ばつ0, and the size of `r2` is expected to match the size of `r1`. Additional examples, each expected ×ばつ0: ```matlab mpath.resolve(data, "/A/*/*") % ×ばつ1 mpath.resolve(data, "/A/{X,Y}/*") % ×ばつ0 mpath.resolve(data, "/A/*/{X,Y}") % ×ばつ1 mpath.resolve(data, "/A/{X,Y}/{X,Y}") % ×ばつ1 ``` This issue report may involve two related bugs - Size returned by `resolve` should be zero along dimensions corresponding to segments failing to produce matches - Size returned by `resolve` should retain the original size if empty --- In the current implementation, `reshapeResolvedResult` specially treats all-null data-derived matcher results via `emptyAllNullDataMatcherResult`. That helper does not run the normal dimension assignment logic and currently only special-cases the first `DotGlob` and a preceding `DotSet`, so it cannot express general empty shape semantics.
Author
Owner
Copy link

This issue was partially addressed by 220f030. This commit fixes degenerate cases involving multi-member matching dot operations (e.g., DotSet, DotGlob): /A/*/*, /A/{X,Y}/*, /A/*/{X,Y} (with or without explicit # dimensions). Some things were not addressed:

  • DotExact selecting members that do not exist
  • Comma-separated-list selector selecting outputs that do not exist
  • Cases where listLength is zero.

Regarding DotExact, a few options are considered:

  1. Fallback to empty shape such as 0x1 when there are not matches for DotExact.
  2. Treat DotExact segments as dimension-bearing (either automatically with lower priority or by the user). These will behave similar to multi-member matching dot operations where they will be non-zero in size if they match a member and zero in size if they do not. A drawback is that if the user has a typo early on in a long path containing many DotExact instances, the result will contain many degenerate dimensions.
  3. A variant of option two is to make it so only the first non-matching instance of DotExact will be the degenerate empty dimension, and dimensions of subsequent instances dimensions will remain singleton. This should be equivalent to making the first unassigned singleton dimension zero in size and would be similar to a middle ground between the two.
This issue was partially addressed by `220f030`. This commit fixes degenerate cases involving multi-member matching dot operations (e.g., `DotSet`, `DotGlob`): `/A/*/*`, `/A/{X,Y}/*`, `/A/*/{X,Y}` (with or without explicit `#` dimensions). Some things were not addressed: - `DotExact` selecting members that do not exist - Comma-separated-list selector selecting outputs that do not exist - Cases where `listLength` is zero. Regarding `DotExact`, a few options are considered: 1. Fallback to empty shape such as `0x1` when there are not matches for `DotExact`. 2. Treat `DotExact` segments as dimension-bearing (either automatically with lower priority or by the user). These will behave similar to multi-member matching dot operations where they will be non-zero in size if they match a member and zero in size if they do not. A drawback is that if the user has a typo early on in a long path containing many `DotExact` instances, the result will contain many degenerate dimensions. 3. A variant of option two is to make it so only the first non-matching instance of `DotExact` will be the degenerate empty dimension, and dimensions of subsequent instances dimensions will remain singleton. This should be equivalent to making the first unassigned singleton dimension zero in size and would be similar to a middle ground between the two.
Author
Owner
Copy link

This issue has been partially addressed even further by 5d4208d. This commit fixed an incorrect assumption made on chunk validity which had ramifications on output shaping.

In this commit, missing DotExact behavior is now closer to expected. Each DotExact is assigned a dimension but using a lower priority than other operations, which will rarely present itself to users except in degenerate cases. With MissingPolicy="omit", the corresponding dimension to each DotExact will be size 1 if it exists or size 0 if it does not exist. If the MissingPolicy is "missing" or "retain", the size will remain 1.

Remaining work to tackle for addressing this issue:

  • listLength returning 0
  • CSL selectors being out of bounds
This issue has been partially addressed even further by `5d4208d`. This commit fixed an incorrect assumption made on chunk validity which had ramifications on output shaping. In this commit, missing `DotExact` behavior is now closer to expected. Each `DotExact` is assigned a dimension but using a lower priority than other operations, which will rarely present itself to users except in degenerate cases. With `MissingPolicy="omit"`, the corresponding dimension to each `DotExact` will be size 1 if it exists or size 0 if it does not exist. If the `MissingPolicy` is `"missing"` or `"retain"`, the size will remain 1. Remaining work to tackle for addressing this issue: - `listLength` returning 0 - CSL selectors being out of bounds
Author
Owner
Copy link

This issue was further partially addressed by ae4bc50. All-null shape no longer uses first degenerate column as dictator of shape but now considers each branch independently.

Example:

data = struct(A=struct(B=struct()), X=struct());
result = mpath.resolve(data, "/{A,X}/B/C", MissingPolicy="omit");

/B exists only in the /A branch but not the /X branch, while /C exists in neither branch. This previously returned ×ばつ0, while it now returns the expected ×ばつ0.

Additional shaping issues

There same additional circumstance identified as returning an invalid shape when the result is empty.

Leading data-derived matcher

data = struct();
mpath.resolve(data, "/*#2", MissingPolicy="omit") % returns ×ばつ1; expected ×ばつ0
mpath.resolve(data, "/*/{X,Y}", MissingPolicy="omit") % returns ×ばつ1; expected ×ばつ2

CSL selector before an all-null suffix

data = struct(A=struct());
mpath.resolve(data, "/A/Missing/{X,Y}", MissingPolicy="omit") % returns ×ばつ0, correct
mpath.resolve(data, "/A<1>/Missing/{X,Y}", MissingPolicy="omit") % returns ×ばつ1; expected: ×ばつ0

This issue does not present itself with select-all CSL selectors.

data = repmat(struct(A=struct()), 1, 2);
mpath.resolve(data, "/A<:>/Missing/{X,Y}", MissingPolicy="omit") % returns ×ばつ0

Non-traversable parent types

data = struct(A=1);
mpath.resolve(data, "/A#1/{Y}#2", MissingPolicy="omit") % returns: ×ばつ1

The intended behavior may depend on decided semantics on attempts to traverse parents that are non-traversable, which is considered in issue #32.

Remaining cases to be addressed

  • Leading data-derived matcher
  • CSL selector before an all-null suffix
  • Zero listLength
  • Empty or out-of-range CSL selectors
  • Non-traversable parent types #32
This issue was further partially addressed by `ae4bc50`. All-null shape no longer uses first degenerate column as dictator of shape but now considers each branch independently. Example: ```matlab data = struct(A=struct(B=struct()), X=struct()); result = mpath.resolve(data, "/{A,X}/B/C", MissingPolicy="omit"); ```` `/B` exists only in the `/A` branch but not the `/X` branch, while `/C` exists in neither branch. This previously returned ×ばつ0, while it now returns the expected ×ばつ0. ## Additional shaping issues There same additional circumstance identified as returning an invalid shape when the result is empty. ### Leading data-derived matcher ```matlab data = struct(); mpath.resolve(data, "/*#2", MissingPolicy="omit") % returns ×ばつ1; expected ×ばつ0 mpath.resolve(data, "/*/{X,Y}", MissingPolicy="omit") % returns ×ばつ1; expected ×ばつ2 ``` ### CSL selector before an all-null suffix ```matlab data = struct(A=struct()); mpath.resolve(data, "/A/Missing/{X,Y}", MissingPolicy="omit") % returns ×ばつ0, correct mpath.resolve(data, "/A<1>/Missing/{X,Y}", MissingPolicy="omit") % returns ×ばつ1; expected: ×ばつ0 ``` This issue does not present itself with select-all CSL selectors. ```matlab data = repmat(struct(A=struct()), 1, 2); mpath.resolve(data, "/A<:>/Missing/{X,Y}", MissingPolicy="omit") % returns ×ばつ0 ``` ### Non-traversable parent types ```matlab data = struct(A=1); mpath.resolve(data, "/A#1/{Y}#2", MissingPolicy="omit") % returns: ×ばつ1 ``` The intended behavior may depend on decided semantics on attempts to traverse parents that are non-traversable, which is considered in issue #32. ## Remaining cases to be addressed - Leading data-derived matcher - CSL selector before an all-null suffix - Zero `listLength` - Empty or out-of-range CSL selectors - Non-traversable parent types #32
Author
Owner
Copy link

Commit b2c3296 further continues to address this issue. Behavior used to differ whether a data-derived matcher was leading segment or not, where leading segments would fallback to returning ×ばつ1 result. Now both leading and non-leading are handled by the same code.

For example:

data = struct();
mpath.resolve(data, "/*#2", MissingPolicy="omit") % now returns ×ばつ0
mpath.resolve(data, "/*/{X,Y}", MissingPolicy="omit") % now returns ×ばつ2
mpath.resolve(data, "/*#2/{X,Y}#1", MissingPolicy="omit") % now returns ×ばつ0
Commit `b2c3296` further continues to address this issue. Behavior used to differ whether a data-derived matcher was leading segment or not, where leading segments would fallback to returning ×ばつ1` result. Now both leading and non-leading are handled by the same code. For example: ```matlab data = struct(); mpath.resolve(data, "/*#2", MissingPolicy="omit") % now returns ×ばつ0 mpath.resolve(data, "/*/{X,Y}", MissingPolicy="omit") % now returns ×ばつ2 mpath.resolve(data, "/*#2/{X,Y}#1", MissingPolicy="omit") % now returns ×ばつ0 ```
Author
Owner
Copy link

Further progress with commit 6a23455: Metadata is now used for the case where there is valid scalar CSL selectors before a later all-null suffix rather than having a special case early exit. This change is intentionally limited to scalar selectors that are concrete on every aligned branch.

data = repmat(struct(A=struct()), 1, 2);
mpath.resolve(data, "/A<1>/Missing/{X,Y}", MissingPolicy="omit") % was ×ばつ1, now ×ばつ0
mpath.resolve(data, "/A<2>/Missing/{X,Y}", MissingPolicy="omit") % was ×ばつ1, now ×ばつ0
data = struct(A=repmat(struct(B=struct()), 1, 2));
mpath.resolve(data, "/A<1>/B<2>/Missing/{X,Y}", MissingPolicy="omit") % was ×ばつ1, now ×ばつ0

Remaining work:

  • Zero for listLength
  • Empty or out-of-range CSL selection
  • Define shape semantics for selectors reached only on some branches or different number of selectors across multiple brancher
  • Decide whether CSL selectors after missing branches contribute degenerate dimensions
  • Decide whether unresolved scalar CSL selectors are assigned (low-priority) dimensions to contribute to degenerate dimensions (similar to DotExact not existing)
  • Non-traversable parent types #32
Further progress with commit `6a23455`: Metadata is now used for the case where there is valid scalar CSL selectors before a later all-null suffix rather than having a special case early exit. This change is intentionally limited to scalar selectors that are concrete on every aligned branch. ```matlab data = repmat(struct(A=struct()), 1, 2); mpath.resolve(data, "/A<1>/Missing/{X,Y}", MissingPolicy="omit") % was ×ばつ1, now ×ばつ0 mpath.resolve(data, "/A<2>/Missing/{X,Y}", MissingPolicy="omit") % was ×ばつ1, now ×ばつ0 data = struct(A=repmat(struct(B=struct()), 1, 2)); mpath.resolve(data, "/A<1>/B<2>/Missing/{X,Y}", MissingPolicy="omit") % was ×ばつ1, now ×ばつ0 ``` Remaining work: - Zero for `listLength` - Empty or out-of-range CSL selection - Define shape semantics for selectors reached only on some branches or different number of selectors across multiple brancher - Decide whether CSL selectors after missing branches contribute degenerate dimensions - Decide whether unresolved scalar CSL selectors are assigned (low-priority) dimensions to contribute to degenerate dimensions (similar to `DotExact` not existing) - Non-traversable parent types #32
Author
Owner
Copy link

Much of the remaining work has been addressed now in 05aca75: Empty-result shaping now handles zero listLength and also unresolved, out-of-range, or partially concrete CSL selectors. Implicit (generated) singleton CSL boundaries stay non-shaping.

What remains to tackle is non-traversable paths and is coupled to issue #32.

Much of the remaining work has been addressed now in `05aca75`: Empty-result shaping now handles zero `listLength` and also unresolved, out-of-range, or partially concrete CSL selectors. Implicit (generated) singleton CSL boundaries stay non-shaping. What remains to tackle is non-traversable paths and is coupled to issue #32.
Author
Owner
Copy link

Further addressed by 9c247dc where empty CSL selection and DotSet now give correct empty shape rather than ×ばつ1.

Further addressed by `9c247dc` where empty CSL selection and `DotSet` now give correct empty shape rather than ×ばつ1.
Author
Owner
Copy link

Completed by af551a2. Final hardcoded ×ばつ1 fallback has been removed. Code now distinguishes reached failures from unreached nominal suffixes for empty shapes.

Completed by `af551a2`. Final hardcoded ×ばつ1 fallback has been removed. Code now distinguishes reached failures from unreached nominal suffixes for empty shapes.
Sign in to join this conversation.
No Branch/Tag specified
main
dev
functional
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference
UserCurt/mpath#31
Reference in a new issue
UserCurt/mpath
No description provided.
Delete branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?