Documentation
¶
Overview ¶
Package util contains some utility functions and algorithms which are useful for type unification.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Extract ¶
Extract takes a solved type out of a unification variable data slot, and returns it from the input container type. If there is no contained unification variable, or no type in the unification variable data field, then this simply returns the input type without modification. Fields in the type tree that do not need to be copied, are not. If in any doubt copy the result. We *never* copy the actual unification variable itself. We keep the pointer! This public function looks at the whole type recursively, and will first extract any child unification variables before finishing at the top. This was written based on the realization that something of this shape was needed after looking at post-unification unification variables and realizing that the data needed to be "bubbled upwards". It turns out the GHC Haskell has a similar function for this which is called "zonk". "zonk" is the name which it uses for this transformation, whimsically claiming that "zonk" is named "after the sound it makes". (Thanks to Sam for the fun trivia!) TODO: Untested alternate version that copies everything if anything changes.
func OccursCheck ¶
OccursCheck determines if elem exists inside of this type. This is important so that we can avoid infinite self-referential types. If we find that it does occur, then we error. This: `?1 occurs-in [[?2]]` is what we're doing here! This function panics if you pass in a nil type, a malformed type, or an elem is nil or that has a .Data field that is populated. This is because if ?0 is equal to []?1, then to prevent infinite types, it does not suffice to check that ?0 does not occur in the list ([]?1), we must also check that []?1 does not occur. That check is harder (and slower) to implement. So we just don't implement it, and we ask the caller to only call OccursCheck in the easy case where ?0 is not yet equal to anything else.
func Unify ¶
Unify takes two types and tries to make them equivalent. If they are both basic types without any unification variables, then we compare them directly, and this is equivalent to running the *types.Type Cmp method. This function works by drawing conclusions from the assertion that the two sides are equal: that a variable on the left must be equal to the sub-trees at the same position on the right, and similarly for variables on the right. This may modify the input types, copy them before use if this is an issue. If you only want to do a compare, you can safely use UnifyCmp.
func UnifyCmp ¶
UnifyCmp is like the standard *types.Type Cmp() except that it allows either type to include unification variables. It returns nil if the two types are consistent, identical, and don't contain any remaining unification variables. This function copies the input types, so this can be use safely without side effects from the underlying Unify operation. In the simple case where neither type contains unification variables, this is a more expensive version of typ1.Cmp(typ2). It is not necessarily valid at this time to call this if both sides contain unification variables. In that situation, this implementation will panic. It does not matter which side is the one that contains unification variables, as long as both of them don't. The textbook terminology is that we're checking that the "scrutinee" (the type which cannot contain unification variables) "matches" the "type pattern" (the type which can contain unification variables). Thanks to Sam for that information. TODO: It's possible that this could be useful with both sides containing unification variables, but keep this panic in until we find that case and add tests for it.
func UnifyCopy ¶
UnifyCopy copies a type, but preserves any unification variables (the .Uni) it encounters. It panics if it encounters an invalid or partial type struct.
func Unpack ¶
Unpack takes a solved type out of a unification variable data slot, and unpacks it over that unification variable to turn the type into a normal one. This returns false if no action was taken, or true if it modified the input. This public function looks at the whole type recursively, and will first unpack any child unification variables before finishing at the top.
Types ¶
This section is empty.
Source Files