RFC: Parallel states - Proof of Concept code

christopherthielen commented 10 years ago

Plunkr: http://plnkr.co/edit/IgePmCtVnojo19i3y6Ab?p=preview Updated Plunkr: http://plnkr.co/edit/YhQyPV?p=preview (2014-02-24, read comments posted on 2014-02-24) Ui-Router Fork: https://github.com/christopherthielen/ui-router

I have a "Tabs" use case for Parallel States in each tab. Basically, my company has an non-angular application which users sit in all day long. There are multiple components, each of which lives in a separate tab, and each of which has its own complex nested state. Users switch back and forth between tabs to perform their job.

For a semi-theoretical example, let's say there are three tabs. Tab 1 is always an inbox, calendar, and task list. Tab 2 allows the user to create, view and update records and follow workflows. Tab 3 is swapped out with a variety of tools that do business work, such as billing or requisitions. Tabs operate independently, but the user needs to refer back to related data in tabs 1 and 2.

I want routing/url management, however if the user bookmarks a URL, I only care about bookmarking that particular tab. I do not need the state of all 3 tabs stored in the URL; I only need the state of the current tab reflected.

I have developed a proof-of-concept that shows how this could be implemented in ui-router. In my proof-of-concept, a ui-view may be tagged with "parallel-state" and multiple ui-view(s) may be added to the parent state's template. When a state transition occurs between the parallel branches, the "exited" state's locals and DOM is retained.

The plunkr demonstrates the parallel routes, via a tabbed UI. Click around in the UI (select "Show inactive tabs" to get a better idea of what is happening)

I'd like to hear comments and opinions about the approach. I'm new to ui-router, so I'm sure I might have leaked or misused some abstractions that I didn't understand. I have not yet tested or accounted for all ui-router functionality, like state parameters and resolves.
However, does this look like a reasonable approach to parallel routes?

I'd reference the other parallel state issues, if I knew how. https://github.com/angular-ui/ui-router/issues/475 https://github.com/angular-ui/ui-router/issues/562 https://github.com/angular-ui/ui-router/issues/63 https://github.com/angular-ui/ui-router/issues/863

timothyjlaurent commented 10 years ago

+1 can't wait for it, either! On Apr 20, 2014 4:15 PM, "Tim Kindberg" notifications@github.com wrote:

I'm still really excited about this! Hope we can get this fully baked soon.

— Reply to this email directly or view it on GitHubhttps://github.com/angular-ui/ui-router/issues/894#issuecomment-40907512 .

gabrielmaldi commented 10 years ago

I don't mean to spam everybody watching this, but I just wanted to say that this would be a great improvement to an already awesome project! I opened a similar issue a couple of days ago and @timkindberg pointed me in the right direction. Probably there are a lot more devs out there who would take advantage of this. I just finished reading through the whole PR and think you guys are coming up with something very nice!

christopherthielen commented 10 years ago

Last night I woke up from a dream, thought "maybe deepStateRedirect is just a special form of abstract: true", then fell back asleep.

abstract: "deepStateRedirect" or abstract: { deepStateRedirect: true }

@nateabele @timkindberg ?

timkindberg commented 10 years ago

Hmm I understand the logic but seems a bit weird to mix those concepts.

christopherthielen commented 10 years ago

I was thinking for tabs, we don't really ever want to activate "the tab" itself, rather we want to activate a substate. It seemed to be a specialized version of the "abstract state with default child state" concept from https://github.com/angular-ui/ui-router/issues/27 or https://github.com/angular-ui/ui-router/issues/948#issuecomment-37485400

nateabele commented 10 years ago

brb, reading academic papers about finite automata.

DylanLukes commented 10 years ago

Here's my two cents from a math perspective:

All of these proposed changes are adding layers of specialized behavior. What would be more ideal would be a conceptual rebuilding that allows for arbitrary state-network topologies. Here's how I would do it.

Here's a small outline of how this proceeds, because it's difficult to build up linearly and might be a bit confusing on first read:

States and Transitions
Cursors (ui-views)
State Traversal References (ui-strefs)
Wildcard/Multi-source Transitions
Generalizing Transitions' from and to
Controllers and Data

States (`ui-state`) and Transitions (`ui-sref`... sort of)

States are modeled as a directed graph (or category if you prefer). Each state-node has a unique identifier, and a url format. The key here is that the actual state is not contained in the state-node itself. It can't be for reasons that will shortly become clear.

State transitions are declared via from-to relationships, rather than parent-child relations. It's worth noting that this fully generalizes the parent-child pattern. Conceptually, the graph contains directed edges to a failure node for every transition that is not explicitly defined. Realistically, this is a failover case.

We can incorporate virtual states easily in this model, which I'll get to once I discuss traversal paths.

Usage might look like this. Note that I'm also pulling the tempting behavior out, and allowing for functions as from, to arguments. A string argument should be implicitly parsed as a predicate, so the from field for tiddlywink is identical to just writing from: "foo". We don't actually have to explicitly build the graph, so this is fine.

$stateProvider
    .state("foo", {
        url: "/foo"

    })
    .state("bar", {
       url: _.partial(_.template, "/bar/{{x}}/{{y}}")
    })
    ...
    .transition("tiddlywink" {
        from: function (stateId) { return stateId == "foo"; } 
        to:   "bar",
        eager: false,
        on: function(cursor, from, to) { ... } 
    },

The eager attribute designates whether a transition should be forced to actually result in redisplay. The relevance of this will be seen shortly.

Cursors (`ui-view`), traversal paths (`ui-stref`)

Conceptually, a ui-view can be seen as a "cursor" containing a stack of transitions. Note that it's a stack of transitions, not states! There might be multiple valid transitions from one edge to another.

As it stands, ui-srefs refer to a state, and when one is activated, the unique transition to that state is applied. Let's introduce a new concept, generalizing ui-sref, called a ui-stref. We will soon elaborate on how to implement ui-sref (and virtual states!) by allowing wildcard transitions.

A ui-stref is an attribute containing a list of state transition IDs. Activating a ui-stref attempt to apply each state transition in turn. Until the final state is reached, transitions are applied as a "dry run". If any errors or invalid transitions are found, the entire transition is rolled back to the last eager: true transition. eager means that redisplay must be forced before applying the next transition in the ui-stref. It's similar to a Prolog cut (!). Clearly, this is somewhat unsafe behavior, but it has its uses.

Each ui-view is in essence a cursor traversing this tree, that keeps track of the transitions it's followed through the state graph. This allows for unrestricted nesting and recursion of states. While these can be abused, they are also very powerful and useful.

Multi-source and Wildcard transitions

Clearly, a transition isn't immediately that useful if it's only valid from a single state. For most menus and such, we wish to jump to the root state for the menu items, then traverse to the desired state. We can model this using multi-source and wildcard transitions. A wildcard transition is defined as follows:

    $stateProvider.transition("knickknack", {
        from: "*", 
        to: "someState",
        via: ["transition1", "transition2", ..., "transitionN"]
    })

Going back to looking at ui-views as cursors, a wildcard essentially unravels the cursor's traversal history and resets it. from: "*" is shorthand for from: function() { return true; }. The via parameter designates what to reset the traversal to. "transition1" must be valid from the root state, and the final transition must be valid for the to destination.

For multi-source transitions, just provide an array of source states to to.

Aside: Generalizing `from` and `to`

We can actually reasonably generalize from and to entirely to incorporate all of the previously described behaviors succinctly.

from is a predicate. The current state is already known, so from must simply decide whether the transition can be applied in the first place. So for shorthand we have:

from: "foo" ⇒ from: function(s) { return s == "foo" }
from: ["foo", "bar", ...] ⇒ from: _.partial(_.contains, ["foo", "bar", ...])
from: "*" ⇒ from: _.constant(true)

to is a decision. Once the from predicate has passed, we must now select the destination. This is easy when we have a simple to (i.e. just a destination state). For any more complicated cases with multiple potential destinations, we cannot make a decision without more information. So, we might allow to's to accept a function of the cursor and the current states data.

Abstract States

Abstract states fit nicely into the above description. They're just wildcard states with a special to function, which "forwards" using data stored in the cursor. Think of the cursor as putting itself in a box, stamping a label on it ("this is where I want to go") and letting itself go into the system. A virtual state must send a cursor onward based on where it wants to go, or a rollback occurs.

When an stref is activated, the entire path should be stored on the cursor as pending and iterated through part by part. The remaining portion of the path should be passed into the to function in some manner to enable this behavior.

Aside: an eager transition into a virtual state could be potentially nasty. Thus, eager transitions can't apply until the transition actually completes.

Controllers and Data (and finally enabling parallel states!)

Logically, it makes sense for each state to potentially have a controller, and for each cursor to be mandated to have one. The remaining difficult issue in this model is handling how state parameters and miscellaneous data are resolved. Some data should be carried along with the cursor, while other data should remain in a particular state.

Moreover, some data is only relevant to a particular cursor/state pairing. I think the proper way to handle this is to inject services into these controllers and centralize storage of state/cursor data. As with most mathematically informed models, data-state is where things start getting a bit tough.

Anyhow, I hope this has been an interesting proposition. I'm going to try to implement a proof of concept to demonstrate how this works, which I'll post here when finished.

Cheers, :beer:

CMCDragonkai commented 10 years ago

Brilliant! I was just getting into FSMs and was thinking state manipulation should be like a graph. Btw the state data and state parameters give way to a state history that stores more than just the state names but transient state information hence the ability to have widgets that remember themselves. Furthermore I would suggest to make state transitions as promises, so they can be processed asynchronously. Another thing is guards, so you can move any transition logic out of the controllers but into bootstrapping phase. This means things like preloading resources before a state is transitioned to and authentication logic, such as saying that the user must have an authenticated session or authorised permissions to be allowed to change state. Then the logging of where the user went and how they used the GUI becomes easier which kind of incorporates AOP. Lastly any state transition should be hooked up to an eventbus, which allows you to listen for state transitions and potentially trigger state transitions, thus creating an event driven fsm.

nateabele commented 10 years ago

@DylanLukes You are my new favorite person. This is a fantastic write-up, and parts of it track very closely with my thinking on this. Some of the above, however, doesn't quite square with ui-router's architecture. Two examples: (1) states have a 1:n relationship with views, where n >= 0, and (2) the design intentionally eschews the rigor of an FSM, and though we lose some benefits by doing so, I think we can regain them by coming at it the problems it solves from a slightly different angle. In any case, I very much look forward to your proof of concept.

@christopherthielen The above write-up represents parts of why I've been waffling on this for so long. There are many parts of ui-router's design that are deeply, fundamentally wrong, and it's taken a great deal of time and pain to rectify them. In fact, I am currently in the process of finalizing my second attempt at a full rewrite of ui-router's internal architecture. None of the parallel-state proposals currently on the table feel completely right, and I'm pretty wary of repeating the mistakes of the past. On the other hand, none of what we're facing are new problems. I'm fairly confident that there is One True Way™ here, and it probably exists in an academic paper from 10+ years ago.

Regarding the rewrite, one of the design goals was to make transitions fully atomic, such that failure could safely occur at any point in the transition process without leaving the application in an inconsistent state. Considering the above, I believe this will be a useful primitive to build off of once we are ready for a final parallel-state implementation. It's not ready for prime-time, but parts of the API very closely mirror the above:

$transitionProvider.on({ from: "home", to: "somewhere.else" }, function($transition$, $http) {
  // ...
});

$transitionProvider.onEnter({ from: "home", to: "somewhere.else" }, function($transition$, $http) {
  // ...
});

$transitionProvider.onExit({ from: "home", to: "somewhere.else" }, function($transition$, $http) {
  // ...
});

$transitionProvider.onSuccess({ from: "home", to: "somewhere.else" }, function($transition$, $http) {
  // ...
});

$transitionProvider.onError({ from: "home", to: "somewhere.else" }, function($transition$, $http) {
  // ...
});

Anyway, hopefully that makes things a little bit more clear about where we're headed. Sorry for not being better about feedback up till now.

Furthermore I would suggest to make state transitions as promises, so they can be processed asynchronously.

@CMCDragonkai I don't follow. State transitions already are promises.

CMCDragonkai commented 10 years ago

Yep I know. Just for with regards to Dylan's ideas.

DylanLukes commented 10 years ago

A few more thoughts (skip to the bottom for the more interesting ones):

Yes, my design definitely loses the rigor. It essentially allows you to defer the actual construction of a state-tree/graph and handle it dynamically. I should qualify that: I don't think that's actually useful for most real world use-cases. What I'm concerned with is providing a set of fundamental pieces that can be linked up and sugared into routers optimized for different topologies by imposing certain constraints. For example:

Hierarchical (Tree) Routing

The constraints here are that there cannot be any explicit(!) backwards transitions, states must be 1:N with respect to their outgoing transitions, and have a unique incoming transition. Of course, in reality we do traverse the tree backwards. I think it's more intuitive to model backwards transitioning by roll-backs. Moreover, we often do things like jump from one branch to another while implicitly traversing back to the common ancestor and then back down...

Linear/Cyclic Routing

This one's actually more common than you'd think: slide-shows. You can look at it as a special case of tree-shaped routing, in which case the "roll-back" behavior is better elucidated. Working with a slide-show, there are stateful effects within each slide, which are entirely rolled back when the presenter goes back to a previous slide. We don't actually need to allow for state *in the slides* to have "sticky" behavior: slides stay the way they were when last visited. We just need to add one link from the last slide to the first, and keep the state in the traversal itself. Of course, this can lead to some technical inefficiency as a jump back one slide actually incurs N forward traversals (where N is the length of the slideshow), but that should be optimized out anyhow (sparse traversals? partially deferred evaluation?).

Composite Routing

This is what motivated me to start thinking about this problem. I have an application I'm building (with ui-router of course) which contains tabs, each of which contains instances of sub-applications with distinct routing schemes (one is a presentation tool, another is a sort of contact book, etc). By imposing any of the above sets of constraints too harshly, it becomes difficult to compose them nicely. So, I think the solution is to abstract away the constraints and right interoperable components that can be used to define both. A couple visualizations: a tree with cyclic "fruit", a cycle with trees growing from its elements, and so forth. And what about direct products of cycles?

Going from those visualizations, an FSM seems like the best initial choice. However, for maximum flexibility, we want to be able to name the transitions, and have a dynamically generated set of transitions. This entirely precludes an actual FSM structure.

So, also, I'm not sure Promises are actually the right mechanism here. I've been thinking about how to represent traversals and, of course, my first thought was a chain of promises. However, you end up needing the resolved values of those promises later, so they basically just act like lazy thunks. Moreover, you can't roll back a stateful promise. So... here's some thoughts on managing state:

Traversals as Scope

This is actually really intuitive. The traversal chain is a stack. On just about any computer, the currently active program only gets at its state via whatever it has in scope. So, let's treat a traversal as a sort of dynamic scope (angular provides a lexical/static scope).

As for implementation, I think the traversal chain should have a global object with each field mapped to a sparse "stack" tracking the history of values in scope. This enables roll-backs as well. The only problem is that this basically means we can't allow any mutable values in scope state at all. They can't be rolled-back, and will pose some serious issues. We can get around this by keeping "references" or "tokens" to be used with other services, but those services themselves are under no obligation to comply.

So, as it stands I'm actively thinking about the state issue here and a sane, but functional (read: practical, pun intended) way of managing it all...

Edit: We also need a way of having "sticky" states that don't lose their state when rolled back... I think these are best modeled by states which have back or self edges. So, we can "go back" without rolling them back. The implication, theoretically, is that to "go back" through or from any sticky state to another state, every state along the way must be sticky (there must be back-edges all the way). Food for thought.

DylanLukes commented 10 years ago

Some further stuff that's concerning me:

Allowing cycles makes moving "up" or "back" a very non-trivial problem. You have to know in advance how to do so... I'm worried going back through the current path step by step might not be good enough.
I think I might actually need to make the state-graph defined statically. What might work as a substitute for dynamic addition is embedding graphs inside other ones. But again, this doesn't play nicely with backtracking. And there are definite needs for dynamic behavior: parameterized states, tabs, etc...

Edit: dynamic behavior could possibly be embedded in the traversal chain via scoped values, assuming these are available to future traversals. Then the behavior is dynamic, but constrained to being a result of previously scoped values (user input categorically falls within the purview of the active state). So, maybe only the tip of the traversal chain actually needs side-effecting behavior :).

DylanLukes commented 10 years ago

Just finalized the core data structure for my proof-of-concept. It's basically a generic graph with the following features:

Edges may have arbitrary data associated with them. They contain source/target references, but these are just a convenience and not strictly necessary. I'll probably remove these fields and make them internal lookups hidden behind properties to try to reduce the risk of shooting yourself in the foot by modifying edges.
Nodes may be literally any data type. They don't have any graph state in them at all. However, uniqueness is enforced (modulo ES6 egal).
DAG structure is enforced by a naive implementation of the Pearce-Kelley online toposort. In other words, if you try to create a cycle you get an exception.

I've decided to go with DAG's for the routing topologies as they're a good compromise between fully dynamic states/transitions and strict hierarchical routing. As my code is written in TypeScript compiled to ES6, that'll be a prereq, though it all works fine with es6-shim so far.

Oh, and it plays nice with D3 :). Some example "exotic" routing topologies:

ashaffer commented 10 years ago

@christopherthielen and anyone else using your parallel state implementation: There is a small bug in your patch. When you define parallelSupport, you do so in the provider which uses the provider's injector to invoke onEnter/onExit hooks. This causes you to be unable to inject services in the normal way in these hooks.

christopherthielen commented 10 years ago

@ashaffer thanks! I moved parallelSupport inside $get and injected the $injector there.

davereed commented 10 years ago

@christopherthielen I just started following this so forgive me. Based on your demo it looks like your back button history states simply follow the users click sequence. Is there a plan to adapt this so that each tab or parallel state gets its own history stack? It sounded like @DylanLukes was sort of describing this but I wasn't sure. It seems like it would be useful if there was an option so that a back button wouldn't jump you between different tabs but rather would just back off the history for the particular state you have currently active.

I am curious if this is a planned feature or would I have to modify it to do this?

christopherthielen commented 10 years ago

@davereed sorry, that's outside the scope of this experiment. The back button drives the browser URL (which then drives state). The state machine itself doesn't really have a history capability yet. See issue #92

ashaffer commented 10 years ago

I've modified @christopherthielen's code to invert the meaning of parallel in a separate branch. If anyone else needs it, it's available here:

https://github.com/weo-edu/ui-router/tree/issue-894-inverted-parallel

christopherthielen commented 10 years ago

@ashaffer I'm curious as to how you're defining your states, with the "inverse" paradigm. Do you have one modal state marked as parallel?

ashaffer commented 10 years ago

@christopherthielen Ya, I just stick parallel: true on my modal states.

christopherthielen commented 10 years ago

Hey all,

Since it looks like this implementation of "parallel states" isn't going to make it into mainline UI-Router, I have refactored my code into a separate project that plugs into the stock UI-Router (using a few hacks like hijacking the to/from paths).

For anyone using my fork to implement parallel states, I won't be maintaining the fork. My new project is here: https://github.com/christopherthielen/ui-router-extras

http://christopherthielen.github.io/ui-router-extras/

snekbaev commented 10 years ago

Hi, @christopherthielen thank you very much! I was waiting if it will be integrated, but no matter what planning on using it in near several weeks. Thanks again!

timkindberg commented 10 years ago

@christopherthielen Hi Chris, thanks for refactoring to work more like a plugin. I'm glad people can use this right away. Love it!!

christopherthielen commented 10 years ago

@timkindberg Thanks for the sentiment! I'm a little bummed this feature wasn't destined for main-line UI-Router, but glad that I was able to hack it into an addon. When it comes time to implement something like this in main-line, I'm happy to help work on it.

apreg commented 10 years ago

@christopherthielen I'm eager to digest all the new features your plugin provides but at first sight it reminds me to some of the things from Ian Horrocks' statechart like history mechanism or concurrent states. Am I right about this? Anyway, it's great work.

angular-ui / ui-router