Traversal generates all permutations of a step output

[flyingsilverfin]

Usage and product changes

We implement cartesian permutations within each Sorted step: whenever an intersection is found, we check if we need to produce cartesian answers in any of the variables attached to the intersection variable. If so, we set up a CartesianIterator, which finishes generating all answer within that intersection, before returning to the intersection-based step execution.

We also add Display traits for VariableValue and all inner Concept types.

Algorithm

This applies for a Step that utilises N-way intersection/join over Sorted iterators.

1. Whenever an intersection on the intersection variable is found, we advance all participating Sorted iterators.
2. If any of the participating iterators has more answers that have the same intersection variable value, we create a CartesianIterator
3. The CartesianIterator extracts all iterators that are going to contribute to the Cartesian Product (ie. any that still have the same intersection variable value after being moved forward)
4. We compute next CartesianIterator answers long as they exist within this intersection. The cartesian iterator does a simple backtrack + reopen iterators in a fixed order to generate answers within the intersection variable value.
5. We write CartesianIterator answers into the output batch until there are no more, then we advance the intersection point and search for the next intersection.

Note: because we don't have seek implemented yet, the "reopen iterators at intersection variable value" does a naiive reopen + advance until we find the intersection variable value.

This algorithm is dependent on the storage iterators providing a deterministic ordering within each intersection variable value

[vaticle-bot]

PR Review Checklist

Do not edit the content of this comment. The PR reviewer should simply update this comment by ticking each review item below, as they get completed.

---

Trivial Change

• [ ] This change is trivial and does not require a code or architecture review.

Code

• [ ] Packages, classes, and methods have a single domain of responsibility.
• [ ] Packages, classes, and methods are grouped into cohesive and consistent domain model.
• [ ] The code is canonical and the minimum required to achieve the goal.
• [ ] Modules, libraries, and APIs are easy to use, robust (foolproof and not errorprone), and tested.
• [ ] Logic and naming has clear narrative that communicates the accurate intent and responsibility of each module (e.g. method, class, etc.).
• [ ] The code is algorithmically efficient and scalable for the whole application.

Architecture

• [ ] Any required refactoring is completed, and the architecture does not introduce technical debt incidentally.
• [ ] Any required build and release automations are updated and/or implemented.
• [ ] Any new components follows a consistent style with respect to the pre-existing codebase.
• [ ] The architecture intuitively reflects the application domain, and is easy to understand.
• [ ] The architecture has a well-defined hierarchy of encapsulated components.
• [ ] The architecture is extensible and scalable.