Coding 2021-06-28
So, I realized that if I come up with an invariant that enforces similarity to the old workflow, there's a chance that gives similar performance guarantees as well. I did this by splitting up the functions to add an Action and to define inputs for it, but only allowing adding inputs to the last Action that was added. This discards some properties of the old system that I don't think I cared about, but it simplifies cycle checking to the case of "does this Target depend on the latest Action?" which is constant-time. This is because, to get cycles longer than a single Action, Target pair, we need to do something like:
- add Action A
- add Target 1 as a child of A
- add Action B
- make B require 1 (allowed)
- add Target 2 as a child of B
- make A require 2 (not allowed)
The last step is not allowed because A is not the most recent Action. I don't think there's any way to arrange these so that all requirements are added at a valid time.
Anyway, I'll have to see whether I agree with this reasoning later, because I'm kind of sleepy and that took a lot of effort to articulate.
Good night.