1. Things that are linked
  2. Ways things are linked
  3. Common links
  4. Reference groups
  5. Traversing the link map

Link Map

The link map is Imperial's system for representing how all the data in the system connects together. It's both a caching system and a way to represent references (both implicit and explicit). Exchange also uses the links to determine which data of a reference group should be exported and which can be derived from the exported data (so as to reduce duplication in the export).

The cache invalidation system exists for two purposes: reimporting from an altered source (thus changing dynamic data) and allowing applications to alter data at will. In this way, it's a system to make Imperial reactive.

Things that are linked

Ways things are linked

Often times, a link doesn't have equivalent data of the same type on both ends. There is generally some conversion being made. In this case, the link map must be aware of the implications of that conversion. It can be:

For instance, if you query a MIDI-type struct for how many A notes it has, this is irreversible (it cannot recreate the MIDI data from knowing how many A notes it has, though it can perhaps validate it). But if you have a conversion from number to string (with no formatting), it's reversible.

Common links

When writing a description for a binary files, the position information is often implied. That is, it defaults to referencing the previous sister's end (or parent's base if no sister) or 0:b if it's the first struct in the root or a new binary context. In the referential cases, it establishes a link the same as if it was an explicit reference.

When a struct references into another struct which has been cloned, it forces clones of itself in a 1:1 manner. So if B references into A and is cloned in this way, then: A0 and B0 are linked, A1 and B1 are linked, etc. A is also linked to A0..N but A0 has no association with A1 or B1.

Reference groups

When multiple keys (for example) reference a single target, they and the target join what's called a reference group. These groups have special cache invalidation rules compared to the typical 1:1 links.

When a member of the group which is not the target is invalidated, the target is invalidated, but not the other members. When the target is updated, it invalidates all members besides itself. When the target is requested but does not have a value, it can interpret the value from the reference group members only if all members who have a value will convert to the same value (it is an error if they have divergent values, in this situation). When a member does not have a value, they must retrieve it through the target (which can infer it from other members). Similar to this pseudocode:

def target_invalidated_or_updated(target, members):
	for member in members:

def member_invalidated_or_updated(member, target, other_members):

# Note that these following two functions do not cause invalidations.
def get_target_value(target, members):
	if not target.has_value:
		best = 4
		for member in members:
			link = member.link_to[target]
			if member.has_value and not link.is_irreversible:
				value = target.convert_value_from(member)

				if link.is_reversible:
					if target.has_value:
						assert value == target.value
					if best > 1:
						target.value = value
						best = 1
				elif link.is_recoverable:
					if target.has_value:
						# Some sort of insensitive comparison,
						# the type should know what's unimportant.
						assert value.insensitive_equals(target.value)
					if best > 2:
						target.value = value
						best = 2
				elif link.is_lossy:
					if target.has_value:
						# Fuzzy comparison, whatever that means for this type.
						# This is obviously expensive...but it shouldn't come up often.
						assert member.convert_value_from(target).is_similar_to(member.value)
					if best > 3:
						target.value = value
						best = 3

		assert target.has_value

		for member in members:
			if member.has_value and member.link_to[target].is_irreversible:
				# Ensure that deriving irreversible members from the target value
				# we found would create the same value as this member has.
				# TODO: Which comparison is appropriate? Should it be configurable?
				assert member.convert_value_from(target) == member.value

	return target.value

def get_member_value(member, target, other_members):
	if not member.has_value:
		value = get_target_value(target, other_members)
		member.value = member.convert_value(value)
	return member.value

References to references chain rather than get absorbed. For instance, in the case of something like:

static Example {
	a: 1
	b: @this.a
	c: @this.a
	d: @this.b
	e: @this.b
These keys do not enter into a single reference group, but two. {a, b, c} and {b, d, e}. This way, if this were a dynamic and b required some sort of conversion, d and e know to convert from b and not from, for example, c which might convert differently.

Explicit, circular references are disallowed; at least for now. If the are implemented, they should error if the end of the cycle does not convert to the same value as the first. Likely, they could not be lazily evaluated.

Traversing the link map

Imperial Exchange imposes some requirements on the link map, being the flagship product for this tool suite. It needs to be able to determine what data can be exported, what needs to be exported, and the quality of the export. It must also be able to enter the reference groups for each piece of data (if any) so that it can determine which to export and which not to, based on an algorithm defined in its design page.

Thus a node:

Additionally, when converting between types in order to perform the export, this information must be tracked from the declared struct to the final export. For instance, final export png.width which comes from a declared graphic struct's width must be able to look into the reference group of graphic.width and notify the group that it will be necessarily and reversibly exported. If data does not make it to the exported type and cannot be exported otherwise, Exchange will need to print a warning.

What keys need to be exported can be determined by the keys requested by a to_file method which are not requested by the from_file method. Keys which are requested by both are considered transcoder keys, which would generally be declared statically (however, it's not required). The same is true of all keys which are in any pair of un/packing methods. All other keys can be assumed to be optionally exported but this assumption should be overridable.