-
Enhancement
-
Resolution: Unresolved
-
P4
-
repo-valhalla
A refinement to the implementation to support recursively-typed value class: https://github.com/openjdk/valhalla/pull/802#issuecomment-1295376613
Two values x, y are substitutable if and only if, for every access path x.a.b.c, y.a.b.c also exists (and vice versa), and moreover the two values of those two accesses are themselves substitutable. (The call .getClass() is one possible path; the rest of the paths are field references, regardless of access protection.) This definition can be simplified by stipulating that only paths .a.b.c which end in a non-value object (primitive, null, id-object) are significant; the equivalence is the same.
In the case of a deeply nested (probably recursively-typed) value, the number of such paths maybe exponentially large (compared with the number of object "nodes"). So a naive exploration of all paths will be infeasible. For example, a "ladder" of binary nodes where both sides of each "rung" points to the same "ladder" of one less depth, will have 2^D complexity of enumerating all paths.
And cyclic value graphs (which must involve recursive types) have an infinite number of paths, which is even scarier.
That said, this is a known problem with known solutions. (It is the DFA minimization problem in disguise, aka the RE equivalence problem, and also the type structural equivalence problem which the Algol designers inflicted on themselves.) In practice, in most cases, the naive algorithm will do fine.
https://www.ics.uci.edu/~goodrich/teach/cs162/notes/rm.pdf
https://cs.uwaterloo.ca/~dberry/FTP_SITE/reprints.journals.conferences/BerrySchwartz1979TypeEquiv.pdf
Two values x, y are substitutable if and only if, for every access path x.a.b.c, y.a.b.c also exists (and vice versa), and moreover the two values of those two accesses are themselves substitutable. (The call .getClass() is one possible path; the rest of the paths are field references, regardless of access protection.) This definition can be simplified by stipulating that only paths .a.b.c which end in a non-value object (primitive, null, id-object) are significant; the equivalence is the same.
In the case of a deeply nested (probably recursively-typed) value, the number of such paths maybe exponentially large (compared with the number of object "nodes"). So a naive exploration of all paths will be infeasible. For example, a "ladder" of binary nodes where both sides of each "rung" points to the same "ladder" of one less depth, will have 2^D complexity of enumerating all paths.
And cyclic value graphs (which must involve recursive types) have an infinite number of paths, which is even scarier.
That said, this is a known problem with known solutions. (It is the DFA minimization problem in disguise, aka the RE equivalence problem, and also the type structural equivalence problem which the Algol designers inflicted on themselves.) In practice, in most cases, the naive algorithm will do fine.
https://www.ics.uci.edu/~goodrich/teach/cs162/notes/rm.pdf
https://cs.uwaterloo.ca/~dberry/FTP_SITE/reprints.journals.conferences/BerrySchwartz1979TypeEquiv.pdf
- relates to
-
-
- Resolved
-