Deterministic dispose

[jterbraak]

This pull request attaches the lifecycle of a Nut to its parent to make the unsubscriptions deterministic again. It also limits all lifecycle management to either the root of the application of useDyn which simplifies fixed and the Semigroup instance a lot.

I got a bit sidetracked and also removed beacons and replaced it with a system of regions which track the start and end of dynamic regions.

[mikesol]

I just tested it out. In general it looks great. I'd be comfortable merging now if you feel it's in a good place. The implementation is better than the previous one, and as all the tests passed, I'm inclined to go with it.

[mikesol]

Ah nevermind, I ran the tests on the wrong branch 🤣 Nvm my previous comment then, I now see where the WIP is at. Still looks good! I see that portal is commented out, but otherwise the approach looks solid. I'm happy to review once it makes sense to jump in!

[jterbraak]

This PR implements a beamRegion effect that replaces all attributeDyn... effects in DOMInterpret. This effect takes 3 Anchors and moves the elements "between" the first and second Anchor "after" the last Anchor. Because Anchor includes Nodes and ParentNodes we'll have to define "between" and "after".

• between: A region is the collection of elements after the beginning up and including the end. The beginning is never included in the collection. This means that when begin and end point to the same Node the collection is empty.
• after: This is more straightforward: for Nodes it's simply after the Node and for ParentNode its before the first child Node.

For portals there is a new effect called bufferPortal which creates a ParentNode detached from the display. The portal hook makes a Nut attach onto that ParentNode and tracks the end Anchor. It then beams the content out of the buffer when the portaled Nut is attached and back into the buffer when the Nut is disposed, making it ready for reuse.

Under the hood FullDOMInterpret uses after and prepend to efficiently move the collected nodes. To collect the Nodes we simply iterate from the beginning(via firstChild or nextSibling) until we find the end Node via referential equality. For bufferPortal createDocumentFragment is used.

To track the begin and end of a collection of elements a Region system is implemented. For this system we need the Bound and Bump effect.

• Bound hides how the Anchor is determined. Typically a region needs to check if it has any elements of its own and defers to the parent when it has none. Otherwise we just return the last element of the region.
• Bump signals to the parent that the endpoint of the region has changed. This can cascade up a tree of regions when the child region was the last one or the parent is now empty.

Additionally there are two types of region. A Region which supports all actions useDyn expects and StaticRegion which only supports the actions a static element would need. The implementation of StaticRegion is very simple and I hope this means faster(no benchmarks). One can convert one into the other when necessary so I don't know if that performance claim holds.

[jterbraak]

The core of the Region system are RegionSpans. They manage sibling Regions and coordinate the insert, bump, move and remove actions. They also provide a Bound implementation which lets Regions determine their begin and end Anchors for beamRegion. The actual structure of the RegionSpan is just an array of regions. All regions track their indices by using a reference that gets updated on every insert/splice. The begin of a Region is defined as the end of the previous region. A dummy region is inserted at the start which contains the information provided by the parent. This makes the whole ix - 1 dance work out but we will have to correct the indices for this at some points(see insertManaged and newSpan->sendTo). The end of a region is stored in a SharedBound. As the name suggests this bound can be shared among multiple adjacent regions. The end is set by region pointed to by the owner field. All following empty regions use the same SharedBound. The last region using the SharedBound is pointed to by the extent field. For a non-empty regions this works out to: begin is the end of the previous region, if it is empty this does not matter because we read the end of the first non-empty region which is shared with the empty one. For an empty region we do the same, we find the end of the first non-empty region, read our own end which would be the same SharedBound leading to the begin and end pointing to the same Node signalling an empty collection to beamRegion. To split a SharedBound we can use the owner and extent pointer to find all empty regions using that bound. Then we create a new SharedBound and update all following regions. The inverse happens when the region signals a clear. The we extend the preceding SharedBound and update the following regions. The implementation detects if updating the preceding or following regions would be cheaper and uses that strategy.

[jterbraak]

That should be the last issue fixed.

One thing we might want to add is some way of only partially disposing child elements. All dispose effects would still have to run but most removeElement and removeText calls are not needed as long as the first ancestor is removed. That way we can save a lot of DOM operations.

[mikesol]

Does element removal run when a dyn is removed? For example, when a switcher is switched out, does it result in a bunch of cascading removals from the DOM, or just the top-level one? If it's just the top-level one, I think we can wait with partial removal, as it would only kick in when we remove an entire Deku app, which is rare. Otherwise, IMO we should make partial removal part of the PR to avoid a performance regression.

[mikesol]

@jterbraak would it work to add a new field to PSR needsDeferredRemoval that is set to false unless the PSR is coming from a dyn, a portal, or the top-level? Meaning that in elementify and fixed it'd be false.

Then, we can check for that, and only trigger the effect, ie:

when (un PSR psr).needsDeferredRemoval do
    runEffectFn2 deferO psr do
      runEffectFn1 (un DOMInterpret di).removeElement elt

In elementify and text when we need deferred removal.

[mikesol]

@jterbraak nice work, and thanks for adding that failing test! It's great to keep adding those, it'll make the framework a lot more resilient 👍

[mikesol]

I just checked out the failing test. Do you have intuition for why it's failing? I did a bit of snooping, and I see that handleRemove is not called. It could have to do with how switcher is defined, which is a bit hacky, perhaps it fails to correctly account for this corner case where the remove action is also pure.

[mikesol]

I had to remind myself why the definition of switcher is so thorny.

• useSplit is used to guarantee that ctr1 is always called before ctr2 in the same frame (so remove is always called before creating something)
• because useSplit shaves off the pure events (a consequence of memoization, the same thing happens with useRant), we need to recover the initial events, which useDeflect is for.

I'm pretty sure I never assigned the useSplit part to remove because I didn't imagine folks removing during the pure stage, but it's possible & should be accommodated.

That said, when I try to change it to:

switcher :: forall a. (a -> Nut) -> Poll a -> Nut
switcher f poll = Deku.do
  { first: ctr1, second: ctr2 } <- useSplit (counter poll)
  dctr <- useDeflect (counter poll)
  { value } <- useDynAtBeginningWith (ctr2 <|> dctr) $ dynOptions
    { remove = \(oldV /\ _) -> filterMap
        (\(newV /\ _) -> if newV == oldV + 1 then Just unit else Nothing)
        (ctr1 <|> dctr)
    }

  f (snd value)
  where
  counter = mapAccum fn 0
    where
    fn a b = (a + 1) /\ (a /\ b)

It still bugs out, but now in the region system:

● deku › framework tests › pure switcher works

    TypeError: Cannot read properties of undefined (reading 'end')

      277 |   ix <- region.ix
      278 |   prev <- runSTFn2 index (ix - 1) children
    > 279 |   sbound <- ST.read prev.end
          |                     ^
      280 |   sbound.bound
      281 |
      282 | -- | Determines the whether the final `Bound`, determines the final `Bound` and runs the `Bump` effect on it.

      at prev (deku-core/src/Deku/Internal/Region.purs:279:21)

If we can change the definition of switcher to something more sane, that'd be nice & could even fix the bug!

[mikesol]

@jterbraak for switcher, one idea is to hack together a poll that functions (in pseudocode) sort of like:

  \x -> do
    diffusingRef <- Ref.new true
    recepticleRef <- Ref.new List.Nil
    let
      eff = mkEffectFn1 \i -> do
        diffusing <- Ref.read diffusingRef
        if diffusing then runEffectFn1 eff' i
        else Ref.modify_ (i : _) recepticleRef
    let
      handleEvent :: EffectFn1 (Event.Event a) Unit
      handleEvent = mkEffectFn1 \y -> do
        uu <- runEffectFn2 Event.subscribeO y eff
        void $ liftST $ runSTFn1 def $ mkEffectFn1 \_ -> uu

    bang <- liftST $ Event.create
    runEffectFn1 handleEvent (UPoll.sample x bang.event)
    Ref.write false diffusingRef
    bang.push identity
    recepticle <- Ref.read recepticleRef
    Ref.write true diffusingRef
    for_ (List.head recepticle) \v -> runEffectFn1 eff' v

So basically, it's a poll that shaves off all but the last pure element (List.head recepticle ... just realized I spelled receptacle wrong in the code 🤦). It likely fixes the problem, although ofc it ain't pretty.

[jterbraak]

@mikesol

It still bugs out, but now in the region system:

There were no checks on the lifetime of the element for removal. I.e. it was possible to remove the dyn element before it was initialized. Should be fixed with febc82c.

For the switcher dilemma I would guess what we really want is an extension of the useDynWith interface to listen to the changes of siblings. 502d178 is an implementation of that. Downside of that is that we would have to either break compatibility or add a new useDyn variant.

[mikesol]

For the switcher dilemma I would guess what we really want is an extension of the useDynWith interface to listen to the changes of siblings. 502d178 is an implementation of that. Downside of that is that we would have to either break compatibility or add a new useDyn variant.

Looks reasonable!

Would we want to do a similar thing for sendTo? ie

sendTo :: Poll (Tuple Int Int) -> value -> Poll Int -- a poll with from->to

Also, what's the semantic value of Maybe Int as opposed to Int in remove?

[mikesol]

@jterbraak I answered my own question, I see that it's pushing the initial position.

Is it correct that the Poll (Maybe Int) rebroadcasts the position of the incoming poll?

[mikesol]

Adding a note here mostly as a note to self.

One problem with the current interface is that it creates confusion about when polls will be subscribed to. dynOptions.sendTo and dynOptions.remove are producers of polls where a poll is produced & subscribed to for every Nut created within a dyn. That leads to the overwrought definition of switcher in current main.

The proposal in 502d178 is still a producer of polls, but one that can "inherit" the temporality of the poll driving the dyn through the new argument Poll (Maybe Int).

One issue here is that the ornate structure is compensating for the fact that Nuts in a dyn are not indexible by anything other than their position. If tracking position was easy, we could make dyn options { remove: Poll Int, sendTo:Poll (Tuple Int Int)}. But asking users of Deku to track position is really brittle, and tracking it internally is a recipe for disaster - it'd require a loop across all dyns every time something moved, which for 10k dyns would be quite slow.

So I'm still mulling, & no fully formed opinion yet, but I'm mostly trying to weigh ergonomics against performance. The current solution proposed in 502d178 is quite nice, but there may be others we can consider as well.

[jterbraak]

Another solution would be to revive useMemo where the actual subscription of the original Poll happens after useDyn subscribes.

useMemo :: forall x. Poll x -> Hook (Poll x)
useMemo xs cont = Nut $ mkEffectFn2 \psr di -> do
  memoed <- Poll.create
  runEffectFn2 (coerce $ cont memoed.poll) 
  runEffectFn3 pump psr xs $ mkEffectFn1 memoed.push

With this the signals of construct and destruct would always be in lockstep. I never liked this approach because it makes my head spin in what order the subscriptions happen and it undoes the optimizations of Poll.

Making the elements track their own positions is probably not worth it. The current implementation provides position to the elements but that is already known anyway because it is necessary in the array-based RegionSpan implementation. A better tree-based approach would make this far more costly. When I get around to implementing that I would make position as lazy as possible, only calculating it when the element actually subscribes to the Poll. For the current implementation I would rather give Poll Unit as a signal for siblings than tracking positions with Maybe Int and Tuple Int Int(or Tuple (Maybe Int) (Maybe Int)).

[mikesol]

Slept on it again 🛌

My gut feeling is that there are two issues with the proposed "signalling" Poll in remove.

1. Its main use case is facilitating the internal implementation of switcher, so I'm not sure if it has many benefits in the public API.
2. The signalling poll is achievable using other Deku/Hyrule primitives.

I put together a small PR that makes a useSkimmed via the strategy I describe above. It skims off all but the first pure value of a poll. That simplifies switcher without needing an API change. How does it look to you?

[mikesol]

Nice! I think we're good to go! Is there anything you wanna do before merge?

[jterbraak]

No, I think we're done here. There's always stuff to do but I can improve the implementation in future PR's.