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