Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Start phasing out ibids. Other marshal improvements #2886

Merged
merged 1 commit into from
Apr 15, 2021

Conversation

erights
Copy link
Member

@erights erights commented Apr 15, 2021

Turning on the commented out instrumentation and running yarn test over all of agoric-sdk there is only this one case where the output without ibids is larger than the output with ibids. It seems to be from one of the swingset tests but I'm not sure which. Even in this unusual case, the expansion is less than 2x.

Expansion 478 / 262 = 1.8244274809160306 }
 [{"@qclass":"slot","index":0},[{"brand":{"@qclass":"slot","iface":"Alleged: moola brand","index":1},"value":{"@qclass":"bigint","digits":"200"}},{"brand":{"@qclass":"slot","index":1},"value":{"@qclass":"bigint","digits":"200"}},{"brand":{"@qclass":"slot","index":1},"value":{"@qclass":"bigint","digits":"200"}},{"brand":{"@qclass":"slot","index":1},"value":{"@qclass":"bigint","digits":"200"}},{"brand":{"@qclass":"slot","index":1},"value":{"@qclass":"bigint","digits":"200"}}]] 
 [{"@qclass":"slot","index":0},[{"brand":{"@qclass":"slot","iface":"Alleged: moola brand","index":1},"value":{"@qclass":"bigint","digits":"200"}},{"@qclass":"ibid","index":3},{"@qclass":"ibid","index":3},{"@qclass":"ibid","index":3},{"@qclass":"ibid","index":3}]] 

This PR adds a new cyclePolicy of 'noIbids'. Serialization is now also parameterized by a cyclePolicy in addition to unserialization. The default unserialization policy remains 'forbidCycles'. The default serialization policy is 'noIbids' which never encodes and ibid, but does detect and reject cycles during serialization, preventing unbounded recursion.

marshal now deals with convertSlotToVal more like the way it has always dealt with convertValToSlot --- it uses its own internal bookkeeping to avoid asking these external functions redundant questions. Previously, if a slot would have been repeated, the serialization side would instead encode it with an ibid. But the unserialization side did not insist on that. If the same slot number appeared in the encoding multiple times, the unserialization would call convertSlotToVal redundantly, possibly producing different vals for different occurrences of the same slot number. This PR eliminates that hazard.

Without ibids, we should now have the invariant that sameStructure(x, y) implies that
serialize(x).body === serialize(y).body. In other word, with respect to the sameStructure equivalence class, serialize should now be canonical. Our pass-by-copy superstructure cannot have cycles. And it always has tree semantics whether it is originally a DAG or not. It will always unserialize to a tree.

This PR expands complexity a bit in order to deal with the transition to an ibid-less world without breaking anything. Once we're on the other side of that, a lot of this will become simpler.

Attn @cwebber

@erights erights self-assigned this Apr 15, 2021
@erights erights requested review from michaelfig, warner and FUDCo April 15, 2021 06:02
@FUDCo
Copy link
Contributor

FUDCo commented Apr 15, 2021

marshal now deals with convertSlotToVal more like the way it has always dealt with convertValToSlot --- it uses its own internal bookkeeping to avoid asking these external functions redundant questions. Previously, if a slot would have been repeated, the serialization side would instead encode it with an ibid. But the unserialization side did not insist on that. If the same slot number appeared in the encoding multiple times, the unserialization would call convertSlotToVal redundantly, possibly producing different vals for different occurrences of the same slot number. This PR eliminates that hazard.

The SwingSet kernel should be quite happy with repeated slot references.

Copy link
Contributor

@FUDCo FUDCo left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ibid-ibid-ibid-ibid that's all folks!

@erights erights force-pushed the schematize-marshal branch from 9bb2da5 to bad9fe5 Compare April 15, 2021 21:34
@erights erights merged commit 39388bc into master Apr 15, 2021
@erights erights deleted the schematize-marshal branch April 15, 2021 22:24
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants