ProtectedcleanCounter for generating unique group IDs
ProtectedgroupA history of oldGroups (keys) that got merged into newGroups (values). Needed to dereference removed groups still used in a pin.
ProtectedgroupMaps group ID to the expressions its value has to satisfy - read through getExpressions.
ProtectedgroupMaps group ID to what the group is pinned to (if anything) - read through pinOf.
ProtectedgroupMaps group ID to the term types its value may have - read through rangeOf.
ProtectedgroupMaps group ID to the values in it - read through valuesOf and groupEntries.
Protected ReadonlymeetMeets the two pins a group is asked to carry at once, reporting false when no value
satisfies both
ProtectedstaticStatic expression validations where no variable group is involved. These occur when an expression must equal a concrete term.
Protected ReadonlytoProtectedvalueMaps a value to the group it is in - read through groupOf.
The state the set is in, as a stamp that no two states of any two sets share.
Every method that writes anything moves it on (touch), so a memo taken off the set is valid for exactly as long as this is what it was taken at - which is a check the memo cannot forget to make, there being nothing to invalidate.
PrivateassertAsserts that every value of the group equals the term.
A triple term is not pinned but decomposed: the group takes the shape of one, and each position is
asserted onto the group that position is - the same unification the rest of the mapping head goes
through. Three things come with that: a second triple term on the group unifies with the first rather
than being reported unequal, every position is held to the range it can have, and the occurs check
refuses ?y ≡ <<( ... ?y )>>.
The group to assert on
The term every value of the group equals
false on a contradiction, after which the solver holds no meaningful state
Gives a group the shape of a triple term, creating an anonymous group per position where it has none.
The group to shape
the group per position, or false when the group cannot hold a triple term
ProtectedcarriesA pinned group still constrains its last remaining member, so it survives remove.
The group to check
whether it is pinned
The positions of the shape a group is pinned to.
The group to look up
the group per position, or undefined when it is not pinned to a shape
Resets the solver to its initial state. Call this before processing a new triple pattern.
A copy that shares no state with this one, so that either may be mutated on its own.
the copy
ProtectedcopyCopies the state of this set into target, which subclasses extend with the state they add.
The set to copy into
ProtectedcreateCreates a group holding no values at all, which is only reachable through whatever a subclass makes point at it - the positions of a triple pin, for datastructures/TermClusterSet!TermClusterSet.
the new group
ProtectedcreateProtecteddropDeletes a group and every value in it, which subclasses extend with the state they add.
The group to drop
Gets the cluster information for a variable.
The variable to look up
the term its cluster is bound to (if any), the other variables in the cluster, and the group ID
Gets all expressions that must equal the given variable's value.
The variable to look up
the expressions
Gets or creates a group for a variable, registering its range when the group is new.
The variable to get/create a group for
the group ID
Gets all expression-to-term equality checks with no variable involved.
the expression-term pairs to validate
Every group and its values, in the order the groups were created.
the pairs
ProtectedhandleNarrows the group of a variable to the range that variable carries.
The variable whose range to register
Whether the group exists at all - a group nothing points at any more does not.
The group to check
whether it exists
ProtectedisA group a live pin points at survives however few members it has: it is a position of a shape, and dropping it would leave that shape naming a group that is no longer there.
The group to check
whether it is worth keeping
The variables of the mapping in a group, as against the user query variables the rewriting binds from them.
The group to look up
its mapping variables, ordered by sortClusters so that the first is the one every rewrite names the group by
ProtectedmergeMerges two groups by id, which is what a group nothing names can be merged by - the values-only half of a merge, whatever else a subclass hangs off a group being migrated by migrateGroupData.
One group
The other
the ids involved, or undefined when the two ids are the same group
Merges the groups of two mapping variables.
the ids involved, or undefined when both were already in one group
ProtectedmigrateCarries the expressions of the disappearing group over - it is no longer reachable, so the constraints it holds would otherwise be lost. Ranges and terms are merged by TermClusterSet itself.
The group disappearing
The group surviving
Narrows what terms a group's value may have.
The group to narrow
The term types to narrow it to
false when nothing is left for it to be, or when its pin is not one of those terms
The pin of a group.
The group to look up
what it is pinned to, or undefined when nothing fixes its value
The term types a group's value may have.
The group to look up
its range, the top of the lattice when nothing narrowed it
Registers an equality constraint between two terms, variables or expressions - the main entry point for adding constraints.
Term, variable, or expression (typically from the mapping head)
Term or variable (typically from the triple pattern)
ProtectedregisterRegisters an expression the group's value has to equal.
TODO: narrow the group by what the expression can produce - the term type an operator returns is a range like any other, and one that no longer meets the group's is a contradiction the rewriting currently leaves to evaluation.
The group ID
The expression every value of the group equals
ProtectedregisterRegisters a concrete term binding to a group: the throwing wrapper around assertTerm the unfolding needs, a group asked to be two terms at once matching nothing at all.
The group ID
The term to bind, a triple term included
The term every value of the group equals, reading a shape back as the triple term it stands for.
Every position is whatever fixes it, or else the mapping variable naming it - the same variable the
mapping body binds, which is what lets the BIND(<<( ?mi_s ?mi_p ?mi_o )>> AS ?uq_o) this feeds name
values the subselect really projects.
The group to look up
the term, or undefined when nothing fixes the group, or when a position of its shape is fixed
by nothing and named by nothing
Dereferences a group id through the merge history.
The id to resolve
the group it has become, or itself when it is still its own group
Pins a term onto a group.
The group to pin
The term every value of it equals
false when the group already carries something incompatible, which leaves the set in a state
no caller may read
Sorts the variables within each cluster, mapping variables first and by name within each of the two.
The mapping variables coming first is what resolvedTermOf and the rewriting read a cluster by:
the first variable of a cluster is the one the subselect really projects, so a user query variable
landing there would name a variable nothing binds. It is ordered on isUserQueryVar rather than
left to the names, which only happen to sort that way while the prefixes both start where they do.
Sorts the lists in place, which is a write like any other: what a group's first value is decides what every read of it names, so the stamp has to move on even though the members themselves do not change.
The term a group is pinned to.
The group to look up
the term, or undefined when nothing pins it, or a shape does instead
ProtectedtouchMoves revision on, invalidating whatever was memoised off the state the set was just in.
Called by the method that writes rather than by whoever asked for the write, so that a caller has
nothing to remember. Most of the calls sit on the choke points the writes of this class pass through -
clear, copyInto, createEmptyGroup, remove, dropGroup,
mergeGroupIds - which is what a subclass extending one of them inherits rather than has to
repeat, and what makes createGroup and every super-chaining override safe without a call of their
own.
A subclass writing state no ancestor writes owes a call here on its own account, since no choke
point of this class covers it. Those are narrowRange and resolveAllConstraints on
datastructures/TermClusterSet!TermClusterSet, assertTermTypeRange on
datastructures/AssertionClusterSet!AssertionClusterSet, and sortClusters,
registerExpressionToGroup and the static-validation branch of register on ClusterSolver!ClusterSolver
Unifies two groups by id - the merge mergeGroups is, for the groups no value names.
One group
The other
false when the two cannot hold the same value
The values of a group.
The group to read
its values, empty when the group does not exist
Solver for determining variable equality clusters during query rewriting.
When rewriting a triple pattern against a mapping head, variables from both sides may need to be unified. The solver tracks which variables are equivalent, what concrete terms they may be bound to, and which expressions their value has to satisfy.
Since a triple term the mapping head writes is a shape whose three positions are groups in their own right (assertTerm) rather than a value a group is pinned to, the structure is a DAG, which resolvedTermOf reads a term back off and the occurs check of TermClusterSet keeps well founded.
Example