Source: lib/media/segment_index.js

  1. /*! @license
  2. * Shaka Player
  3. * Copyright 2016 Google LLC
  4. * SPDX-License-Identifier: Apache-2.0
  5. */
  6. goog.provide('shaka.media.MetaSegmentIndex');
  7. goog.provide('shaka.media.SegmentIndex');
  8. goog.provide('shaka.media.SegmentIterator');
  9. goog.require('goog.asserts');
  10. goog.require('shaka.log');
  11. goog.require('shaka.media.SegmentReference');
  12. goog.require('shaka.util.IReleasable');
  13. goog.require('shaka.util.Timer');
  14. /**
  15. * SegmentIndex.
  16. *
  17. * @implements {shaka.util.IReleasable}
  18. * @implements {Iterable.<!shaka.media.SegmentReference>}
  19. * @export
  20. */
  21. shaka.media.SegmentIndex = class {
  22. /**
  23. * @param {!Array.<!shaka.media.SegmentReference>} references The list of
  24. * SegmentReferences, which must be sorted first by their start times
  25. * (ascending) and second by their end times (ascending).
  26. */
  27. constructor(references) {
  28. if (goog.DEBUG) {
  29. shaka.media.SegmentIndex.assertCorrectReferences_(references);
  30. }
  31. /** @protected {!Array.<!shaka.media.SegmentReference>} */
  32. this.references = references;
  33. /** @private {shaka.util.Timer} */
  34. this.timer_ = null;
  35. /**
  36. * The number of references that have been removed from the front of the
  37. * array. Used to create stable positions in the find/get APIs.
  38. *
  39. * @protected {number}
  40. */
  41. this.numEvicted_ = 0;
  42. /** @private {boolean} */
  43. this.immutable_ = false;
  44. }
  45. /**
  46. * Get immutability
  47. *
  48. * @return {boolean}
  49. */
  50. getIsImmutable() {
  51. return this.immutable_;
  52. }
  53. /**
  54. * Get number of references
  55. * @protected
  56. * @return {number}
  57. */
  58. getNumReferences() {
  59. return this.references.length;
  60. }
  61. /**
  62. * @override
  63. * @export
  64. */
  65. release() {
  66. if (this.immutable_) {
  67. return;
  68. }
  69. this.references = [];
  70. if (this.timer_) {
  71. this.timer_.stop();
  72. }
  73. this.timer_ = null;
  74. }
  75. /**
  76. * Marks the index as immutable. Segments cannot be added or removed after
  77. * this point. This doesn't affect the references themselves. This also
  78. * makes the destroy/release methods do nothing.
  79. *
  80. * This is mainly for testing.
  81. *
  82. * @export
  83. */
  84. markImmutable() {
  85. this.immutable_ = true;
  86. }
  87. /**
  88. * Iterates over all top-level segment references in this segment index.
  89. * @param {function(!shaka.media.SegmentReference)} fn
  90. */
  91. forEachTopLevelReference(fn) {
  92. for (const reference of this.references) {
  93. fn(reference);
  94. }
  95. }
  96. /**
  97. * Return the earliest reference, or null if empty.
  98. * @return {shaka.media.SegmentReference}
  99. */
  100. earliestReference() {
  101. return this.references[0] || null;
  102. }
  103. /**
  104. * Drop the first N references.
  105. * Used in early HLS synchronization, and does not count as eviction.
  106. * @param {number} n
  107. */
  108. dropFirstReferences(n) {
  109. this.references.splice(0, n);
  110. }
  111. /**
  112. * Finds the position of the segment for the given time, in seconds, relative
  113. * to the start of the presentation. Returns the position of the segment
  114. * with the largest end time if more than one segment is known for the given
  115. * time.
  116. *
  117. * @param {number} time
  118. * @return {?number} The position of the segment, or null if the position of
  119. * the segment could not be determined.
  120. * @export
  121. */
  122. find(time) {
  123. // For live streams, searching from the end is faster. For VOD, it balances
  124. // out either way. In both cases, references.length is small enough that
  125. // the difference isn't huge.
  126. const lastReferenceIndex = this.references.length - 1;
  127. for (let i = lastReferenceIndex; i >= 0; --i) {
  128. const r = this.references[i];
  129. const start = r.startTime;
  130. // A rounding error can cause /time/ to equal e.endTime or fall in between
  131. // the references by a fraction of a second. To account for this, we use
  132. // the start of the next segment as /end/, unless this is the last
  133. // reference, in which case we use its end time as /end/.
  134. const end = i < lastReferenceIndex ?
  135. this.references[i + 1].startTime : r.endTime;
  136. // Note that a segment ends immediately before the end time.
  137. if ((time >= start) && (time < end)) {
  138. return i + this.numEvicted_;
  139. }
  140. }
  141. if (this.references.length && time < this.references[0].startTime) {
  142. return this.numEvicted_;
  143. }
  144. return null;
  145. }
  146. /**
  147. * Gets the SegmentReference for the segment at the given position.
  148. *
  149. * @param {number} position The position of the segment as returned by find().
  150. * @return {shaka.media.SegmentReference} The SegmentReference, or null if
  151. * no such SegmentReference exists.
  152. * @export
  153. */
  154. get(position) {
  155. if (this.references.length == 0) {
  156. return null;
  157. }
  158. const index = position - this.numEvicted_;
  159. if (index < 0 || index >= this.references.length) {
  160. return null;
  161. }
  162. return this.references[index];
  163. }
  164. /**
  165. * Offset all segment references by a fixed amount.
  166. *
  167. * @param {number} offset The amount to add to each segment's start and end
  168. * times.
  169. * @export
  170. */
  171. offset(offset) {
  172. if (!this.immutable_) {
  173. for (const ref of this.references) {
  174. ref.offset(offset);
  175. }
  176. }
  177. }
  178. /**
  179. * Merges the given SegmentReferences. Supports extending the original
  180. * references only. Will replace old references with equivalent new ones, and
  181. * keep any unique old ones.
  182. *
  183. * Used, for example, by the DASH and HLS parser, where manifests may not list
  184. * all available references, so we must keep available references in memory to
  185. * fill the availability window.
  186. *
  187. * @param {!Array.<!shaka.media.SegmentReference>} references The list of
  188. * SegmentReferences, which must be sorted first by their start times
  189. * (ascending) and second by their end times (ascending).
  190. */
  191. merge(references) {
  192. if (goog.DEBUG) {
  193. shaka.media.SegmentIndex.assertCorrectReferences_(references);
  194. }
  195. if (this.immutable_) {
  196. return;
  197. }
  198. if (!references.length) {
  199. return;
  200. }
  201. // Partial segments are used for live edge, and should be removed when they
  202. // get older. Remove the old SegmentReferences after the first new
  203. // reference's start time.
  204. // Use times rounded to the millisecond for filtering purposes, so that
  205. // tiny rounding errors will not result in duplicate segments in the index.
  206. const firstStartTime = Math.round(references[0].startTime * 1000) / 1000;
  207. this.references = this.references.filter((r) => {
  208. return (Math.round(r.startTime * 1000) / 1000) < firstStartTime;
  209. });
  210. this.references.push(...references);
  211. if (goog.DEBUG) {
  212. shaka.media.SegmentIndex.assertCorrectReferences_(this.references);
  213. }
  214. }
  215. /**
  216. * Merges the given SegmentReferences and evicts the ones that end before the
  217. * given time. Supports extending the original references only.
  218. * Will not replace old references or interleave new ones.
  219. * Used, for example, by the DASH and HLS parser, where manifests may not list
  220. * all available references, so we must keep available references in memory to
  221. * fill the availability window.
  222. *
  223. * @param {!Array.<!shaka.media.SegmentReference>} references The list of
  224. * SegmentReferences, which must be sorted first by their start times
  225. * (ascending) and second by their end times (ascending).
  226. * @param {number} windowStart The start of the availability window to filter
  227. * out the references that are no longer available.
  228. * @export
  229. */
  230. mergeAndEvict(references, windowStart) {
  231. // Filter out the references that are no longer available to avoid
  232. // repeatedly evicting them and messing up eviction count.
  233. references = references.filter((r) => {
  234. return r.endTime > windowStart &&
  235. (this.references.length == 0 ||
  236. r.endTime > this.references[0].startTime);
  237. });
  238. const oldFirstRef = this.references[0];
  239. this.merge(references);
  240. const newFirstRef = this.references[0];
  241. if (oldFirstRef) {
  242. // We don't compare the actual ref, since the object could legitimately be
  243. // replaced with an equivalent. Even the URIs could change due to
  244. // load-balancing actions taken by the server. However, if the time
  245. // changes, its not an equivalent reference.
  246. goog.asserts.assert(oldFirstRef.startTime == newFirstRef.startTime,
  247. 'SegmentIndex.merge should not change the first reference time!');
  248. }
  249. this.evict(windowStart);
  250. }
  251. /**
  252. * Removes all SegmentReferences that end before the given time.
  253. *
  254. * @param {number} time The time in seconds.
  255. * @export
  256. */
  257. evict(time) {
  258. if (this.immutable_) {
  259. return;
  260. }
  261. const oldSize = this.references.length;
  262. this.references = this.references.filter((ref) => ref.endTime > time);
  263. const newSize = this.references.length;
  264. const diff = oldSize - newSize;
  265. // Tracking the number of evicted refs will keep their "positions" stable
  266. // for the caller.
  267. this.numEvicted_ += diff;
  268. }
  269. /**
  270. * Drops references that start after windowEnd, or end before windowStart,
  271. * and contracts the last reference so that it ends at windowEnd.
  272. *
  273. * Do not call on the last period of a live presentation (unknown duration).
  274. * It is okay to call on the other periods of a live presentation, where the
  275. * duration is known and another period has been added.
  276. *
  277. * @param {number} windowStart
  278. * @param {?number} windowEnd
  279. * @param {boolean=} isNew Whether this is a new SegmentIndex and we shouldn't
  280. * update the number of evicted elements.
  281. * @export
  282. */
  283. fit(windowStart, windowEnd, isNew = false) {
  284. goog.asserts.assert(windowEnd != null,
  285. 'Content duration must be known for static content!');
  286. goog.asserts.assert(windowEnd != Infinity,
  287. 'Content duration must be finite for static content!');
  288. if (this.immutable_) {
  289. return;
  290. }
  291. // Trim out references we will never use.
  292. while (this.references.length) {
  293. const lastReference = this.references[this.references.length - 1];
  294. if (lastReference.startTime >= windowEnd) {
  295. this.references.pop();
  296. } else {
  297. break;
  298. }
  299. }
  300. while (this.references.length) {
  301. const firstReference = this.references[0];
  302. if (firstReference.endTime <= windowStart) {
  303. this.references.shift();
  304. if (!isNew) {
  305. this.numEvicted_++;
  306. }
  307. } else {
  308. break;
  309. }
  310. }
  311. if (this.references.length == 0) {
  312. return;
  313. }
  314. // Adjust the last SegmentReference.
  315. const lastReference = this.references[this.references.length - 1];
  316. this.references[this.references.length - 1] =
  317. new shaka.media.SegmentReference(
  318. lastReference.startTime,
  319. /* endTime= */ windowEnd,
  320. lastReference.getUrisInner,
  321. lastReference.startByte,
  322. lastReference.endByte,
  323. lastReference.initSegmentReference,
  324. lastReference.timestampOffset,
  325. lastReference.appendWindowStart,
  326. lastReference.appendWindowEnd,
  327. lastReference.partialReferences,
  328. lastReference.tilesLayout,
  329. lastReference.tileDuration,
  330. lastReference.syncTime,
  331. lastReference.status,
  332. lastReference.aes128Key,
  333. );
  334. this.references[this.references.length - 1].discontinuitySequence =
  335. lastReference.discontinuitySequence;
  336. }
  337. /**
  338. * Updates the references every so often. Stops when the references list
  339. * returned by the callback is null.
  340. *
  341. * @param {number} interval The interval in seconds.
  342. * @param {function():Array.<shaka.media.SegmentReference>} updateCallback
  343. * @export
  344. */
  345. updateEvery(interval, updateCallback) {
  346. goog.asserts.assert(!this.timer_, 'SegmentIndex timer already started!');
  347. if (this.immutable_) {
  348. return;
  349. }
  350. if (this.timer_) {
  351. this.timer_.stop();
  352. }
  353. this.timer_ = new shaka.util.Timer(() => {
  354. const references = updateCallback();
  355. if (references) {
  356. this.references.push(...references);
  357. } else {
  358. this.timer_.stop();
  359. this.timer_ = null;
  360. }
  361. });
  362. this.timer_.tickEvery(interval);
  363. }
  364. /** @return {!shaka.media.SegmentIterator} */
  365. [Symbol.iterator]() {
  366. const iter = this.getIteratorForTime(0);
  367. goog.asserts.assert(iter != null, 'Iterator for 0 should never be null!');
  368. return iter;
  369. }
  370. /**
  371. * Returns a new iterator that initially points to the segment that contains
  372. * the given time, or the nearest independent segment before it.
  373. *
  374. * Like the normal iterator, next() must be called first to get to the first
  375. * element. Returns null if we do not find a segment at the
  376. * requested time.
  377. *
  378. * The first segment returned by the iterator _MUST_ be an independent
  379. * segment. Assumes that only partial references can be dependent, based on
  380. * RFC 8216 rev 13, section 8.1: "Each (non-Partial) Media Segment in a Media
  381. * Playlist will contain at least one independent frame."
  382. *
  383. * @param {number} time
  384. * @return {?shaka.media.SegmentIterator}
  385. * @export
  386. */
  387. getIteratorForTime(time) {
  388. let index = this.find(time);
  389. if (index == null) {
  390. return null;
  391. } else {
  392. index--;
  393. }
  394. // +1 so we can get the element we'll eventually point to so we can see if
  395. // we need to use a partial segment index.
  396. const ref = this.get(index + 1);
  397. let partialSegmentIndex = -1;
  398. if (ref && ref.hasPartialSegments()) {
  399. // Look for a partial SegmentReference.
  400. for (let i = ref.partialReferences.length - 1; i >= 0; --i) {
  401. let r = ref.partialReferences[i];
  402. // Note that a segment ends immediately before the end time.
  403. if ((time >= r.startTime) && (time < r.endTime)) {
  404. // Find an independent partial segment by moving backwards.
  405. while (i && !r.isIndependent()) {
  406. i--;
  407. r = ref.partialReferences[i];
  408. }
  409. if (!r.isIndependent()) {
  410. shaka.log.alwaysError('No independent partial segment found!');
  411. return null;
  412. }
  413. // Call to next() should move the partial segment, not the full
  414. // segment.
  415. index++;
  416. partialSegmentIndex = i - 1;
  417. break;
  418. }
  419. }
  420. }
  421. return new shaka.media.SegmentIterator(this, index, partialSegmentIndex);
  422. }
  423. /**
  424. * @return {boolean}
  425. */
  426. isEmpty() {
  427. return this.getNumReferences() == 0;
  428. }
  429. /**
  430. * Create a SegmentIndex for a single segment of the given start time and
  431. * duration at the given URIs.
  432. *
  433. * @param {number} startTime
  434. * @param {number} duration
  435. * @param {!Array.<string>} uris
  436. * @return {!shaka.media.SegmentIndex}
  437. * @export
  438. */
  439. static forSingleSegment(startTime, duration, uris) {
  440. const reference = new shaka.media.SegmentReference(
  441. /* startTime= */ startTime,
  442. /* endTime= */ startTime + duration,
  443. /* getUris= */ () => uris,
  444. /* startByte= */ 0,
  445. /* endByte= */ null,
  446. /* initSegmentReference= */ null,
  447. /* presentationTimeOffset= */ startTime,
  448. /* appendWindowStart= */ startTime,
  449. /* appendWindowEnd= */ startTime + duration);
  450. return new shaka.media.SegmentIndex([reference]);
  451. }
  452. };
  453. if (goog.DEBUG) {
  454. /**
  455. * Asserts that the given SegmentReferences are sorted.
  456. *
  457. * @param {!Array.<shaka.media.SegmentReference>} references
  458. * @private
  459. */
  460. shaka.media.SegmentIndex.assertCorrectReferences_ = (references) => {
  461. goog.asserts.assert(references.every((r2, i) => {
  462. if (i == 0) {
  463. return true;
  464. }
  465. const r1 = references[i - 1];
  466. if (r1.startTime < r2.startTime) {
  467. return true;
  468. } else if (r1.startTime > r2.startTime) {
  469. return false;
  470. } else {
  471. if (r1.endTime <= r2.endTime) {
  472. return true;
  473. } else {
  474. return false;
  475. }
  476. }
  477. }), 'SegmentReferences are incorrect');
  478. };
  479. }
  480. /**
  481. * An iterator over a SegmentIndex's references.
  482. *
  483. * @implements {Iterator.<shaka.media.SegmentReference>}
  484. * @export
  485. */
  486. shaka.media.SegmentIterator = class {
  487. /**
  488. * @param {shaka.media.SegmentIndex} segmentIndex
  489. * @param {number} index
  490. * @param {number} partialSegmentIndex
  491. */
  492. constructor(segmentIndex, index, partialSegmentIndex) {
  493. /** @private {shaka.media.SegmentIndex} */
  494. this.segmentIndex_ = segmentIndex;
  495. /** @private {number} */
  496. this.currentPosition_ = index;
  497. /** @private {number} */
  498. this.currentPartialPosition_ = partialSegmentIndex;
  499. }
  500. /**
  501. * @return {number}
  502. * @export
  503. */
  504. currentPosition() {
  505. return this.currentPosition_;
  506. }
  507. /**
  508. * @return {shaka.media.SegmentReference}
  509. * @export
  510. */
  511. current() {
  512. let ref = this.segmentIndex_.get(this.currentPosition_);
  513. // When we advance past the end of partial references in next(), then add
  514. // new references in merge(), the pointers may not make sense any more.
  515. // This adjusts the invalid pointer values to point to the next newly added
  516. // segment or partial segment.
  517. if (ref && ref.hasPartialSegments() && ref.getUris().length &&
  518. this.currentPartialPosition_ >= ref.partialReferences.length) {
  519. this.currentPosition_++;
  520. this.currentPartialPosition_ = 0;
  521. ref = this.segmentIndex_.get(this.currentPosition_);
  522. }
  523. // If the regular segment contains partial segments, get the current
  524. // partial SegmentReference.
  525. if (ref && ref.hasPartialSegments()) {
  526. const partial = ref.partialReferences[this.currentPartialPosition_];
  527. return partial;
  528. }
  529. return ref;
  530. }
  531. /**
  532. * @override
  533. * @export
  534. */
  535. next() {
  536. const ref = this.segmentIndex_.get(this.currentPosition_);
  537. if (ref && ref.hasPartialSegments()) {
  538. // If the regular segment contains partial segments, move to the next
  539. // partial SegmentReference.
  540. this.currentPartialPosition_++;
  541. // If the current regular segment has been published completely (has a
  542. // valid Uri), and we've reached the end of its partial segments list,
  543. // move to the next regular segment.
  544. // If the Partial Segments list is still on the fly, do not move to
  545. // the next regular segment.
  546. if (ref.getUris().length &&
  547. this.currentPartialPosition_ == ref.partialReferences.length) {
  548. this.currentPosition_++;
  549. this.currentPartialPosition_ = 0;
  550. }
  551. } else {
  552. // If the regular segment doesn't contain partial segments, move to the
  553. // next regular segment.
  554. this.currentPosition_++;
  555. this.currentPartialPosition_ = 0;
  556. }
  557. const res = this.current();
  558. return {
  559. 'value': res,
  560. 'done': !res,
  561. };
  562. }
  563. };
  564. /**
  565. * A meta-SegmentIndex composed of multiple other SegmentIndexes.
  566. * Used in constructing multi-Period Streams for DASH.
  567. *
  568. * @extends shaka.media.SegmentIndex
  569. * @implements {shaka.util.IReleasable}
  570. * @implements {Iterable.<!shaka.media.SegmentReference>}
  571. * @export
  572. */
  573. shaka.media.MetaSegmentIndex = class extends shaka.media.SegmentIndex {
  574. /** */
  575. constructor() {
  576. super([]);
  577. /** @private {!Array.<!shaka.media.SegmentIndex>} */
  578. this.indexes_ = [];
  579. }
  580. /**
  581. * Append a SegmentIndex to this MetaSegmentIndex. This effectively stitches
  582. * the underlying Stream onto the end of the multi-Period Stream represented
  583. * by this MetaSegmentIndex.
  584. *
  585. * @param {!shaka.media.SegmentIndex} segmentIndex
  586. */
  587. appendSegmentIndex(segmentIndex) {
  588. goog.asserts.assert(
  589. this.indexes_.length == 0 || segmentIndex.numEvicted_ == 0,
  590. 'Should not append a new segment index with already-evicted segments');
  591. this.indexes_.push(segmentIndex);
  592. }
  593. /**
  594. * Create a clone of this MetaSegmentIndex containing all the same indexes.
  595. *
  596. * @return {!shaka.media.MetaSegmentIndex}
  597. */
  598. clone() {
  599. const clone = new shaka.media.MetaSegmentIndex();
  600. // Be careful to clone the Array. We don't want to share the reference with
  601. // our clone and affect each other accidentally.
  602. clone.indexes_ = this.indexes_.slice();
  603. return clone;
  604. }
  605. /**
  606. * @override
  607. * @export
  608. */
  609. release() {
  610. for (const index of this.indexes_) {
  611. index.release();
  612. }
  613. this.indexes_ = [];
  614. }
  615. /**
  616. * @override
  617. * @export
  618. */
  619. find(time) {
  620. let numPassedInEarlierIndexes = 0;
  621. for (const index of this.indexes_) {
  622. const position = index.find(time);
  623. if (position != null) {
  624. return position + numPassedInEarlierIndexes;
  625. }
  626. numPassedInEarlierIndexes += index.numEvicted_ +
  627. index.getNumReferences();
  628. }
  629. return null;
  630. }
  631. /**
  632. * @override
  633. * @export
  634. */
  635. get(position) {
  636. let numPassedInEarlierIndexes = 0;
  637. let sawSegments = false;
  638. for (const index of this.indexes_) {
  639. goog.asserts.assert(
  640. !sawSegments || index.numEvicted_ == 0,
  641. 'Should not see evicted segments after available segments');
  642. const reference = index.get(position - numPassedInEarlierIndexes);
  643. if (reference) {
  644. return reference;
  645. }
  646. const num = index.getNumReferences();
  647. numPassedInEarlierIndexes += index.numEvicted_ + num;
  648. sawSegments = sawSegments || num != 0;
  649. }
  650. return null;
  651. }
  652. /**
  653. * @override
  654. * @export
  655. */
  656. offset(offset) {
  657. // offset() is only used by HLS, and MetaSegmentIndex is only used for DASH.
  658. goog.asserts.assert(
  659. false, 'offset() should not be used in MetaSegmentIndex!');
  660. }
  661. /**
  662. * @override
  663. * @export
  664. */
  665. merge(references) {
  666. // merge() is only used internally by the DASH and HLS parser on
  667. // SegmentIndexes, but never on MetaSegmentIndex.
  668. goog.asserts.assert(
  669. false, 'merge() should not be used in MetaSegmentIndex!');
  670. }
  671. /**
  672. * @override
  673. * @export
  674. */
  675. evict(time) {
  676. // evict() is only used internally by the DASH and HLS parser on
  677. // SegmentIndexes, but never on MetaSegmentIndex.
  678. goog.asserts.assert(
  679. false, 'evict() should not be used in MetaSegmentIndex!');
  680. }
  681. /**
  682. * @override
  683. * @export
  684. */
  685. mergeAndEvict(references, windowStart) {
  686. // mergeAndEvict() is only used internally by the DASH and HLS parser on
  687. // SegmentIndexes, but never on MetaSegmentIndex.
  688. goog.asserts.assert(
  689. false, 'mergeAndEvict() should not be used in MetaSegmentIndex!');
  690. }
  691. /**
  692. * @override
  693. * @export
  694. */
  695. fit(windowStart, windowEnd) {
  696. // fit() is only used internally by manifest parsers on SegmentIndexes, but
  697. // never on MetaSegmentIndex.
  698. goog.asserts.assert(false, 'fit() should not be used in MetaSegmentIndex!');
  699. }
  700. /**
  701. * @override
  702. * @export
  703. */
  704. updateEvery(interval, updateCallback) {
  705. // updateEvery() is only used internally by the DASH parser on
  706. // SegmentIndexes, but never on MetaSegmentIndex.
  707. goog.asserts.assert(
  708. false, 'updateEvery() should not be used in MetaSegmentIndex!');
  709. }
  710. };