[Feature Request] Improved tracing algorithm in serde_reflection::trace_type

[jerel]

🚀 Feature Request

serde_reflection::trace_type relies on a few ideas and heuristics that it might be time to revisit.

Notably, we use the current table of formats tracer.registry to guide the tracing in most decision points -- with the exception of tracer.incomplete_enums that is also used to decide how to trace enum variants.

This approach was a natural starting point but it is not ideal in the long run for a few reasons:

Calling trace_value before trace_type may update the registry in an incomplete way and defeat further tracing with trace_type. We don't have an easy way to detect non-termination if the base case of enums is not the first variant. We cannot call trace_type_once<T> repeatedly and hope to make progress in finding variants that are deeper that T. (For instance, after one tracing call on struct T(option<S>) we are not going to look into S ever again because it has a format: https://github.com/novifinancial/serde-reflection/blob/master/serde-reflection/src/de.rs#L199)

Moving this issue across from https://github.com/novifinancial/serde-reflection/issues/104

[jerel]

@ma2bd do you have any further thoughts on this algorithm? The workaround that I've been using to explicitly trace enums is getting quite unwieldy in our large codebase so I have motivation to make serde-reflection trace enums fully. I wanted to check if you had any plans for implementation before I took a shot at it.

[ma2bd]

Hi @jerel , Sorry for the lag. I eventually kinda gave up on improving tracing. From the top of my head, the main difficulties are:

• The fact that trace_value influences trace_type is at the same time surprising and useful (e.g. when trace_type would have failed to produce a correct default value). Note that technically, one can use trace_value to create a set of "samples" then discard the registry and start a new one with trace_type (but keeping the samples).
• We can only restart tracing from the top (see trace_type). Consider nested enums: enum A { ... SomethingUsingB(.. B ..) } and enum B { .. many variants .. }. To efficiently trace B when A is the top user type, one would have to repeatedly force the same path from A to B until all the variants of B are covered. This path from A to B could be quite complex and would need to be recorded in a Rust datatype so that it can be replayed. (Also, the first path found from A to B might not be the shortest.) Intuitively, this feels like a lot of code. In very nested data types, the tracing could also end up slower than the current approach (although the current approach would probably still be available by tracing B enums first).