Source: lib/routing/walker.js

  1. /*! @license
  2.  * Shaka Player
  3.  * Copyright 2016 Google LLC
  4.  * SPDX-License-Identifier: Apache-2.0
  5.  */
  7. goog.provide('shaka.routing.Walker');
  9. goog.require('goog.asserts');
  10. goog.require('shaka.routing.Node');
  11. goog.require('shaka.routing.Payload');
  12. goog.require('shaka.util.Destroyer');
  13. goog.require('shaka.util.Error');
  14. goog.require('shaka.util.IDestroyable');
  15. goog.require('shaka.util.PublicPromise');
  16. goog.requireType('shaka.util.AbortableOperation');
  19. /**
  20.  * The walker moves through a graph node-by-node executing asynchronous work
  21.  * as it enters each node.
  22.  *
  23.  * The walker accepts requests for where it should go next. Requests are queued
  24.  * and executed in FIFO order. If the current request can be interrupted, it
  25.  * will be cancelled and the next request started.
  26.  *
  27.  * A request says "I want to change where we are going". When the walker is
  28.  * ready to change destinations, it will resolve the request, allowing the
  29.  * destination to differ based on the current state and not the state when
  30.  * the request was appended.
  31.  *
  32.  * Example (from shaka.Player):
  33.  *  When we unload, we need to either go to the attached or detached state based
  34.  *  on whether or not we have a video element.
  35.  *
  36.  *  When we are asked to unload, we don't know what other pending requests may
  37.  *  be ahead of us (there could be attach requests or detach requests). We need
  38.  *  to wait until its our turn to know if:
  39.  *    - we should go to the attach state because we have a media element
  40.  *    - we should go to the detach state because we don't have a media element
  41.  *
  42.  * The walker allows the caller to specify if a route can or cannot be
  43.  * interrupted. This is to allow potentially dependent routes to wait until
  44.  * other routes have finished.
  45.  *
  46.  * Example (from shaka.Player):
  47.  *  A request to load content depends on an attach request finishing. We don't
  48.  *  want load request to interrupt an attach request. By marking the attach
  49.  *  request as non-interruptible we ensure that calling load before attach
  50.  *  finishes will work.
  51.  *
  52.  * @implements {shaka.util.IDestroyable}
  53.  * @final
  54.  */
  55. shaka.routing.Walker = class {
  56.   /**
  57.    * Create a new walker that starts at |startingAt| and with |startingWith|.
  58.    * The instance of |startingWith| will be the one that the walker holds and
  59.    * uses for its life. No one else should reference it.
  60.    *
  61.    * The per-instance behaviour for the walker is provided via |implementation|
  62.    * which is used to connect this walker with the "outside world".
  63.    *
  64.    * @param {shaka.routing.Node} startingAt
  65.    * @param {shaka.routing.Payload} startingWith
  66.    * @param {shaka.routing.Walker.Implementation} implementation
  67.    */
  68.   constructor(startingAt, startingWith, implementation) {
  69.     /** @private {?shaka.routing.Walker.Implementation} */
  70.     this.implementation_ = implementation;
  72.     /** @private {shaka.routing.Node} */
  73.     this.currentlyAt_ = startingAt;
  75.     /** @private {shaka.routing.Payload} */
  76.     this.currentlyWith_ = startingWith;
  78.     /**
  79.      * When we run out of work to do, we will set this promise so that when
  80.      * new work is added (and this is not null) it can be resolved. The only
  81.      * time when this should be non-null is when we are waiting for more work.
  82.      *
  83.      * @private {?shaka.util.PublicPromise}
  84.      */
  85.     this.waitForWork_ = null;
  87.     /** @private {!Array.<shaka.routing.Walker.Request_>} */
  88.     this.requests_ = [];
  90.     /** @private {?shaka.routing.Walker.ActiveRoute_} */
  91.     this.currentRoute_ = null;
  93.     /** @private {?shaka.util.AbortableOperation} */
  94.     this.currentStep_ = null;
  96.     /**
  97.      * Hold a reference to the main loop's promise so that we know when it has
  98.      * exited. This will determine when |destroy| can resolve. Purposely make
  99.      * the main loop start next interpreter cycle so that the constructor will
  100.      * finish before it starts.
  101.      *
  102.      * @private {!Promise}
  103.      */
  104.     this.mainLoopPromise_ = Promise.resolve().then(() => this.mainLoop_());
  106.     /** @private {!shaka.util.Destroyer} */
  107.     this.destroyer_ = new shaka.util.Destroyer(() => this.doDestroy_());
  108.   }
  110.   /**
  111.    * Get the current routing payload.
  112.    *
  113.    * @return {shaka.routing.Payload}
  114.    */
  115.   getCurrentPayload() {
  116.     return this.currentlyWith_;
  117.   }
  119.   /** @override */
  120.   destroy() {
  121.     return this.destroyer_.destroy();
  122.   }
  124.   /** @private */
  125.   async doDestroy_() {
  126.     // If we are executing a current step, we want to interrupt it so that we
  127.     // can force the main loop to terminate.
  128.     if (this.currentStep_) {
  129.       this.currentStep_.abort();
  130.     }
  132.     // If we are waiting for more work, we want to wake-up the main loop so that
  133.     // it can exit on its own.
  134.     this.unblockMainLoop_();
  136.     // Wait for the main loop to terminate so that an async operation won't
  137.     // try and use state that we released.
  138.     await this.mainLoopPromise_;
  140.     // Any routes that we are not going to finish, we need to cancel. If we
  141.     // don't do this, those listening will be left hanging.
  142.     if (this.currentRoute_) {
  143.       this.currentRoute_.listeners.onCancel();
  144.     }
  145.     for (const request of this.requests_) {
  146.       request.listeners.onCancel();
  147.     }
  149.     // Release anything that could hold references to anything outside of this
  150.     // class.
  151.     this.currentRoute_ = null;
  152.     this.requests_ = [];
  153.     this.implementation_ = null;
  154.   }
  156.   /**
  157.    * Ask the walker to start a new route. When the walker is ready to start a
  158.    * new route, it will call |create| and |create| will provide the walker with
  159.    * a new route to execute.
  160.    *
  161.    * If any previous calls to |startNewRoute| created non-interruptible routes,
  162.    * |create| won't be called until all previous non-interruptible routes have
  163.    * finished.
  164.    *
  165.    * This method will return a collection of listeners that the caller can hook
  166.    * into. Any listener that the caller is interested should be assigned
  167.    * immediately after calling |startNewRoute| or else they could miss the event
  168.    * they want to listen for.
  169.    *
  170.    * @param {function(shaka.routing.Payload):?shaka.routing.Walker.Route} create
  171.    * @return {shaka.routing.Walker.Listeners}
  172.    */
  173.   startNewRoute(create) {
  174.     const listeners = {
  175.       onStart: () => {},
  176.       onEnd: () => {},
  177.       onCancel: () => {},
  178.       onError: (error) => {},
  179.       onSkip: () => {},
  180.       onEnter: () => {},
  181.     };
  183.     this.requests_.push({
  184.       create: create,
  185.       listeners: listeners,
  186.     });
  188.     // If we are in the middle of a step, try to abort it. If this is successful
  189.     // the main loop will error and the walker will enter recovery mode.
  190.     if (this.currentStep_) {
  191.       this.currentStep_.abort();
  192.     }
  194.     // Tell the main loop that new work is available. If the main loop was not
  195.     // blocked, this will be a no-op.
  196.     this.unblockMainLoop_();
  198.     return listeners;
  199.   }
  201.   /**
  202.    * @return {!Promise}
  203.    * @private
  204.    */
  205.   async mainLoop_() {
  206.     while (!this.destroyer_.destroyed()) {
  207.       // eslint-disable-next-line no-await-in-loop
  208.       await this.doOneThing_();
  209.     }
  210.   }
  212.   /**
  213.    * Do one thing to move the walker closer to its destination. This can be:
  214.    *   1. Starting a new route.
  215.    *   2. Taking one more step/finishing a route.
  216.    *   3. Wait for a new route.
  217.    *
  218.    * @return {!Promise}
  219.    * @private
  220.    */
  221.   doOneThing_() {
  222.     if (this.tryNewRoute_()) {
  223.       return Promise.resolve();
  224.     }
  226.     if (this.currentRoute_) {
  227.       return this.takeNextStep_();
  228.     }
  230.     goog.asserts.assert(this.waitForWork_ == null,
  231.         'We should not have a promise yet.');
  233.     // We have no more work to do. We will wait until new work has been provided
  234.     // via request route or until we are destroyed.
  236.     this.implementation_.onIdle(this.currentlyAt_);
  238.     // Wait on a new promise so that we can be resolved by |waitForWork|. This
  239.     // avoids us acting like a busy-wait.
  240.     this.waitForWork_ = new shaka.util.PublicPromise();
  241.     return this.waitForWork_;
  242.   }
  244.   /**
  245.    * Check if the walker can start a new route. There are a couple ways this can
  246.    * happen:
  247.    *  1. We have a new request but no current route
  248.    *  2. We have a new request and our current route can be interrupted
  249.    *
  250.    * @return {boolean}
  251.    *    |true| when a new route was started (regardless of reason) and |false|
  252.    *    when no new route was started.
  253.    *
  254.    * @private
  255.    */
  256.   tryNewRoute_() {
  257.     goog.asserts.assert(
  258.         this.currentStep_ == null,
  259.         'We should never have a current step between taking steps.');
  261.     if (this.requests_.length == 0) {
  262.       return false;
  263.     }
  265.     // If the current route cannot be interrupted, we can't start a new route.
  266.     if (this.currentRoute_ && !this.currentRoute_.interruptible) {
  267.       return false;
  268.     }
  270.     // Stop any previously active routes. Even if we don't pick-up a new route,
  271.     // this route should stop.
  272.     if (this.currentRoute_) {
  273.       this.currentRoute_.listeners.onCancel();
  274.       this.currentRoute_ = null;
  275.     }
  277.     // Create and start the next route. We may not take any steps because it may
  278.     // be interrupted by the next request.
  279.     const request = this.requests_.shift();
  280.     const newRoute = request.create(this.currentlyWith_);
  282.     // Based on the current state of |payload|, a new route may not be
  283.     // possible. In these cases |create| will return |null| to signal that
  284.     // we should just stop the current route and move onto the next request
  285.     // (in the next main loop iteration).
  286.     if (newRoute) {
  287.       request.listeners.onStart();
  289.       // Convert the route created from the request's create method to an
  290.       // active route.
  291.       this.currentRoute_ = {
  292.         node: newRoute.node,
  293.         payload: newRoute.payload,
  294.         interruptible: newRoute.interruptible,
  295.         listeners: request.listeners,
  296.       };
  297.     } else {
  298.       request.listeners.onSkip();
  299.     }
  301.     return true;
  302.   }
  305.   /**
  306.    * Move forward one step on our current route. This assumes that we have a
  307.    * current route. A couple things can happen when moving forward:
  308.    *  1. An error - if an error occurs, it will signal an error occurred,
  309.    *     attempt to recover, and drop the route.
  310.    *  2. Move - if no error occurs, we will move forward. When we arrive at
  311.    *     our destination, it will signal the end and drop the route.
  312.    *
  313.    * In the event of an error or arriving at the destination, we drop the
  314.    * current route. This allows us to pick-up a new route next time the main
  315.    * loop iterates.
  316.    *
  317.    * @return {!Promise}
  318.    * @private
  319.    */
  320.   async takeNextStep_() {
  321.     goog.asserts.assert(
  322.         this.currentRoute_,
  323.         'We need a current route to take the next step.');
  325.     // Figure out where we are supposed to go next.
  326.     this.currentlyAt_ = this.implementation_.getNext(
  327.         this.currentlyAt_,
  328.         this.currentlyWith_,
  329.         this.currentRoute_.node,
  330.         this.currentRoute_.payload);
  332.     this.currentRoute_.listeners.onEnter(this.currentlyAt_);
  334.     // Enter the new node, this is where things can go wrong since it is
  335.     // possible for "supported errors" to occur - errors that the code using
  336.     // the walker can't predict but can recover from.
  337.     try {
  338.       // TODO: This is probably a false-positive.  See eslint/eslint#11687.
  339.       // eslint-disable-next-line require-atomic-updates
  340.       this.currentStep_ = this.implementation_.enterNode(
  341.           /* node= */ this.currentlyAt_,
  342.           /* has= */ this.currentlyWith_,
  343.           /* wants= */ this.currentRoute_.payload);
  345.       await this.currentStep_.promise;
  346.       this.currentStep_ = null;
  348.       // If we are at the end of the route, we need to signal it and clear the
  349.       // route so that we will pick-up a new route next iteration.
  350.       if (this.currentlyAt_ == this.currentRoute_.node) {
  351.         this.currentRoute_.listeners.onEnd();
  352.         this.currentRoute_ = null;
  353.       }
  354.     } catch (error) {
  355.       if (error.code == shaka.util.Error.Code.OPERATION_ABORTED) {
  356.         goog.asserts.assert(
  357.             this.currentRoute_.interruptible,
  358.             'Do not put abortable steps in non-interruptible routes!');
  359.         this.currentRoute_.listeners.onCancel();
  360.       } else {
  361.         // There was an error with this route, so we going to abandon it and
  362.         // resolve the error. We don't reset the payload because the payload may
  363.         // still contain useful information.
  364.         this.currentRoute_.listeners.onError(error);
  365.       }
  367.       // The route and step are done. Clear them before we handle the error or
  368.       // else we may attempt to abort |currentStep_| when handling the error.
  369.       this.currentRoute_ = null;
  370.       this.currentStep_ = null;
  372.       // Still need to handle error because aborting an operation could leave us
  373.       // in an unexpected state.
  374.       this.currentlyAt_ = await this.implementation_.handleError(
  375.           this.currentlyWith_,
  376.           error);
  377.     }
  378.   }
  380.   /**
  381.    * If the main loop is blocked waiting for new work, then resolve the promise
  382.    * so that the next iteration of the main loop can execute.
  383.    *
  384.    * @private
  385.    */
  386.   unblockMainLoop_() {
  387.     if (this.waitForWork_) {
  388.       this.waitForWork_.resolve();
  389.       this.waitForWork_ = null;
  390.     }
  391.   }
  392. };
  394. /**
  395.  * @typedef {{
  396.  *   getNext: function(
  397.  *       shaka.routing.Node,
  398.  *       shaka.routing.Payload,
  399.  *       shaka.routing.Node,
  400.  *       shaka.routing.Payload):shaka.routing.Node,
  401.  *   enterNode: function(
  402.  *       shaka.routing.Node,
  403.  *       shaka.routing.Payload,
  404.  *       shaka.routing.Payload):!shaka.util.AbortableOperation,
  405.  *   handleError: function(
  406.  *       shaka.routing.Payload,
  407.  *       !Error):!Promise.<shaka.routing.Node>,
  408.  *   onIdle: function(shaka.routing.Node)
  409.  * }}
  410.  *
  411.  * @description
  412.  *   There are some parts of the walker that will be per-instance. This type
  413.  *   provides those per-instance parts.
  414.  *
  415.  * @property {function(
  416.  *     shaka.routing.Node,
  417.  *     shaka.routing.Payload,
  418.  *     shaka.routing.Node,
  419.  *     shaka.routing.Payload):shaka.routing.Node getNext
  420.  *   Get the next node that the walker should move to. This method will be
  421.  *   passed (in this order) the current node, current payload, destination
  422.  *   node, and destination payload.
  423.  *
  424.  * @property {function(
  425.  *     shaka.routing.Node,
  426.  *     shaka.routing.Payload,
  427.  *     shaka.routing.Payload):!Promise} enterNode
  428.  *   When the walker moves into a node, it will call |enterNode| and allow the
  429.  *   implementation to change the current payload. This method will be passed
  430.  *   (in this order) the node the walker is entering, the current payload, and
  431.  *   the destination payload. This method should NOT modify the destination
  432.  *   payload.
  433.  *
  434.  * @property {function(
  435.  *     shaka.routing.Payload,
  436.  *     !Error):!Promise.<shaka.routing.Node> handleError
  437.  *   This is the callback for when |enterNode| fails. It is passed the current
  438.  *   payload and the error. If a step is aborted, the error will be
  439.  *   OPERATION_ABORTED. It should reset all external dependences, modify the
  440.  *   payload, and return the new current node. Calls to |handleError| should
  441.  *   always resolve and the walker should always be able to continue operating.
  442.  *
  443.  * @property {function(shaka.routing.Node)} onIdle
  444.  *   This is the callback for when the walker has finished processing all route
  445.  *   requests and needs to wait for more work. |onIdle| will be passed the
  446.  *   current node.  After |onIdle| has been called, the walker will block until
  447.  *   a new request is made, or the walker is destroyed.
  448.  */
  449. shaka.routing.Walker.Implementation;
  451. /**
  452.  * @typedef {{
  453.  *   onStart: function(),
  454.  *   onEnd: function(),
  455.  *   onCancel: function(),
  456.  *   onError: function(!Error),
  457.  *   onSkip: function(),
  458.  *   onEnter: function(shaka.routing.Node)
  459.  * }}
  460.  *
  461.  * @description
  462.  *   The collection of callbacks that the walker will call while executing a
  463.  *   route. By setting these immediately after calling |startNewRoute|
  464.  *   the user can react to route-specific events.
  465.  *
  466.  * @property {function()} onStart
  467.  *   The callback for when the walker has accepted the route and will soon take
  468.  *   the first step unless interrupted. Either |onStart| or |onSkip| will be
  469.  *   called.
  470.  *
  471.  * @property {function()} onEnd
  472.  *   The callback for when the walker has reached the end of the route. For
  473.  *   every route that had |onStart| called, either |onEnd|, |onCancel|, or
  474.  *   |onError| will be called.
  475.  *
  476.  * @property {function()} onCancel
  477.  *   The callback for when the walker is stopping a route before getting to the
  478.  *   end. This will be called either when a new route is interrupting the route,
  479.  *   or the walker is being destroyed mid-route. |onCancel| will only be called
  480.  *   when a route has been interrupted by another route or the walker is being
  481.  *   destroyed.
  482.  *
  483.  * @property {function()} onError
  484.  *   The callback for when the walker failed to execute the route because an
  485.  *   unexpected error occurred. The walker will enter a recovery mode and the
  486.  *   route will be abandoned.
  487.  *
  488.  * @property {function()} onSkip
  489.  *   The callback for when the walker was ready to start the route, but the
  490.  *   create-method returned |null|.
  491.  *
  492.  * @property {function()} onEnter
  493.  *   The callback for when the walker enters a node. This will allow us to
  494.  *   track the progress of the walker within a per-route scope.
  495.  */
  496. shaka.routing.Walker.Listeners;
  498. /**
  499.  * @typedef {{
  500.  *   node: shaka.routing.Node,
  501.  *   payload: shaka.routing.Payload,
  502.  *   interruptible: boolean
  503.  * }}
  504.  *
  505.  * @description
  506.  *   The public description of where the walker should go. This is created
  507.  *   when the callback given to |startNewRoute| is called by the walker.
  508.  *
  509.  * @property {shaka.routing.Node} node
  510.  *   The node that the walker should move towards. This will be passed to
  511.  *   |shaka.routing.Walker.Implementation.getNext| to help determine where to
  512.  *   go next.
  513.  *
  514.  * @property {shaka.routing.Payload| payload
  515.  *   The payload that the walker should have once it arrives at |node|. This
  516.  *   will be passed to the |shaka.routing.Walker.Implementation.getNext| to
  517.  *   help determine where to go next.
  518.  *
  519.  * @property {boolean} interruptible
  520.  *   Whether or not this route can be interrupted by another request. When
  521.  *   |true| this route will be interrupted so that a pending request can be
  522.  *   resolved. When |false|, the route will be allowed to finished before
  523.  *   resolving the next request.
  524.  */
  525. shaka.routing.Walker.Route;
  527. /**
  528.  * @typedef {{
  529.  *   node: shaka.routing.Node,
  530.  *   payload: shaka.routing.Payload,
  531.  *   interruptible: boolean,
  532.  *   listeners: shaka.routing.Walker.Listeners
  533.  * }}
  534.  *
  535.  * @description
  536.  *   The active route is the walker's internal representation of a route. It
  537.  *   is the union of |shaka.routing.Walker.Request_| and the
  538.  *   |shaka.routing.Walker.Route| created by |shaka.routing.Walker.Request_|.
  539.  *
  540.  * @property {shaka.routing.Node} node
  541.  *   The node that the walker should move towards. This will be passed to
  542.  *   |shaka.routing.Walker.Implementation.getNext| to help determine where to
  543.  *   go next.
  544.  *
  545.  * @property {shaka.routing.Payload| payload
  546.  *   The payload that the walker should have once it arrives at |node|. This
  547.  *   will be passed to the |shaka.routing.Walker.Implementation.getNext| to
  548.  *   help determine where to go next.
  549.  *
  550.  * @property {boolean} interruptible
  551.  *   Whether or not this route can be interrupted by another request. When
  552.  *   |true| this route will be interrupted so that a pending request can be
  553.  *   resolved. When |false|, the route will be allowed to finished before
  554.  *   resolving the next request.
  555.  *
  556.  * @property {shaka.routing.Walker.Listeners} listeners
  557.  *   The listeners that the walker can used to communicate with whoever
  558.  *   requested the route.
  559.  *
  560.  * @private
  561.  */
  562. shaka.routing.Walker.ActiveRoute_;
  564. /**
  565.  * @typedef {{
  566.  *   create: function(shaka.routing.Payload):?shaka.routing.Walker.Route,
  567.  *   listeners: shaka.routing.Walker.Listeners
  568.  * }}
  569.  *
  570.  * @description
  571.  *   The request is how users can talk to the walker. They can give the walker
  572.  *   a request and when the walker is ready, it will resolve the request by
  573.  *   calling |create|.
  574.  *
  575.  * @property {
  576.  *     function(shaka.routing.Payload):?shaka.routing.Walker.Route} create
  577.  *   The function called when the walker is ready to start a new route. This can
  578.  *   return |null| to say that the request was not possible and should be
  579.  *   skipped.
  580.  *
  581.  * @property {shaka.routing.Walker.Listeners} listeners
  582.  *   The collection of callbacks that the walker will use to talk to whoever
  583.  *   provided the request.
  584.  *
  585.  * @private
  586.  */
  587. shaka.routing.Walker.Request_;