media_playlist.cc

// Copyright 2016 Google LLC. All rights reserved.
//
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file or at
// https://developers.google.com/open-source/licenses/bsd
 
#include <packager/hls/base/media_playlist.h>
 
#include <algorithm>
#include <cinttypes>
#include <cmath>
#include <cstdint>
#include <filesystem>
#include <iterator>
#include <list>
#include <memory>
#include <optional>
#include <string>
#include <utility>
#include <vector>
 
#include <absl/log/check.h>
#include <absl/log/log.h>
#include <absl/strings/str_format.h>
#include <absl/time/civil_time.h>
#include <absl/time/time.h>
 
#include <packager/file.h>
#include <packager/hls/base/tag.h>
#include <packager/hls_params.h>
#include <packager/macros/logging.h>
#include <packager/media/base/fourccs.h>
#include <packager/media/base/language_utils.h>
#include <packager/media/base/muxer_util.h>
#include <packager/version/version.h>
 
namespace shaka {
namespace hls {
 
namespace {
int32_t GetTimeScale(const MediaInfo& media_info) {
  if (media_info.has_reference_time_scale())
    return media_info.reference_time_scale();
 
  if (media_info.has_video_info())
    return media_info.video_info().time_scale();
 
  if (media_info.has_audio_info())
    return media_info.audio_info().time_scale();
  return 0;
}
 
std::string AdjustVideoCodec(const std::string& codec) {
  // Apple does not like video formats with the parameter sets stored in the
  // samples. It also fails mediastreamvalidator checks and some Apple devices /
  // platforms refused to play.
  // See https://apple.co/30n90DC 1.10 and
  // https://github.com/shaka-project/shaka-packager/issues/587#issuecomment-489182182.
  // Replaced with the corresponding formats with the parameter sets stored in
  // the sample descriptions instead.
  std::string adjusted_codec = codec;
  std::string fourcc = codec.substr(0, 4);
  if (fourcc == "avc3")
    adjusted_codec = "avc1" + codec.substr(4);
  else if (fourcc == "hev1")
    adjusted_codec = "hvc1" + codec.substr(4);
  else if (fourcc == "dvhe")
    adjusted_codec = "dvh1" + codec.substr(4);
  if (adjusted_codec != codec) {
    VLOG(1) << "Adusting video codec string from " << codec << " to "
            << adjusted_codec;
  }
  return adjusted_codec;
}
 
// Duplicated from MpdUtils because:
// 1. MpdUtils header depends on libxml header, which is not in the deps here
// 2. GetLanguage depends on MediaInfo from packager/mpd/
// 3. Moving GetLanguage to LanguageUtils would create a a media => mpd dep.
// TODO(https://github.com/shaka-project/shaka-packager/issues/373): Fix this
// dependency situation and factor this out to a common location.
std::string GetLanguage(const MediaInfo& media_info) {
  std::string lang;
  if (media_info.has_audio_info()) {
    lang = media_info.audio_info().language();
  } else if (media_info.has_text_info()) {
    lang = media_info.text_info().language();
  }
  return LanguageToShortestForm(lang);
}
 
void AppendExtXMap(const MediaInfo& media_info, std::string* out) {
  if (media_info.has_init_segment_url()) {
    Tag tag("#EXT-X-MAP", out);
    tag.AddQuotedString("URI", media_info.init_segment_url().data());
    out->append("\n");
  } else if (media_info.has_media_file_url() && media_info.has_init_range()) {
    // It only makes sense for single segment media to have EXT-X-MAP if
    // there is init_range.
    Tag tag("#EXT-X-MAP", out);
    tag.AddQuotedString("URI", media_info.media_file_url().data());
 
    if (media_info.has_init_range()) {
      const uint64_t begin = media_info.init_range().begin();
      const uint64_t end = media_info.init_range().end();
      const uint64_t length = end - begin + 1;
 
      tag.AddQuotedNumberPair("BYTERANGE", length, '@', begin);
    }
 
    out->append("\n");
  } else {
    // This media info does not need an ext-x-map tag.
  }
}
 
std::string CreatePlaylistHeader(
    const MediaInfo& media_info,
    int32_t target_duration,
    HlsPlaylistType type,
    MediaPlaylist::MediaPlaylistStreamType stream_type,
    uint32_t media_sequence_number,
    int discontinuity_sequence_number,
    std::optional<double> start_time_offset) {
  const std::string version = GetPackagerVersion();
  std::string version_line;
  if (!version.empty()) {
    version_line =
        absl::StrFormat("## Generated with %s version %s\n",
                        GetPackagerProjectUrl().c_str(), version.c_str());
  }
 
  // 6 is required for EXT-X-MAP without EXT-X-I-FRAMES-ONLY.
  std::string header = absl::StrFormat(
      "#EXTM3U\n"
      "#EXT-X-VERSION:6\n"
      "%s"
      "#EXT-X-TARGETDURATION:%d\n",
      version_line.c_str(), target_duration);
 
  switch (type) {
    case HlsPlaylistType::kVod:
      header += "#EXT-X-PLAYLIST-TYPE:VOD\n";
      break;
    case HlsPlaylistType::kEvent:
      header += "#EXT-X-PLAYLIST-TYPE:EVENT\n";
      break;
    case HlsPlaylistType::kLive:
      if (media_sequence_number > 0) {
        absl::StrAppendFormat(&header, "#EXT-X-MEDIA-SEQUENCE:%d\n",
                              media_sequence_number);
      }
      if (discontinuity_sequence_number > 0) {
        absl::StrAppendFormat(&header, "#EXT-X-DISCONTINUITY-SEQUENCE:%d\n",
                              discontinuity_sequence_number);
      }
      break;
    default:
      NOTIMPLEMENTED() << "Unexpected MediaPlaylistType "
                       << static_cast<int>(type);
  }
  if (stream_type ==
      MediaPlaylist::MediaPlaylistStreamType::kVideoIFramesOnly) {
    absl::StrAppendFormat(&header, "#EXT-X-I-FRAMES-ONLY\n");
  }
  if (start_time_offset.has_value()) {
    absl::StrAppendFormat(&header, "#EXT-X-START:TIME-OFFSET=%f\n",
                          start_time_offset.value());
  }
 
  // Put EXT-X-MAP at the end since the rest of the playlist is about the
  // segment and key info.
  AppendExtXMap(media_info, &header);
 
  return header;
}
 
}  // namespace
 
HlsEntry::HlsEntry(HlsEntry::EntryType type) : type_(type) {}
HlsEntry::~HlsEntry() {}
 
class SegmentInfoEntry : public HlsEntry {
 public:
  // If |use_byte_range| true then this will append EXT-X-BYTERANGE
  // after EXTINF.
  // It uses |previous_segment_end_offset| to determine if it has to also
  // specify the start byte offset in the tag.
  // |start_time| is in timescale.
  // |duration_seconds| is duration in seconds.
  SegmentInfoEntry(const std::string& file_name,
                   int64_t start_time,
                   double duration_seconds,
                   bool use_byte_range,
                   uint64_t start_byte_offset,
                   uint64_t segment_file_size,
                   uint64_t previous_segment_end_offset);
 
  std::string ToString() override;
  int64_t start_time() const { return start_time_; }
  double duration_seconds() const { return duration_seconds_; }
  void set_duration_seconds(double duration_seconds) {
    duration_seconds_ = duration_seconds;
  }
 
 private:
  SegmentInfoEntry(const SegmentInfoEntry&) = delete;
  SegmentInfoEntry& operator=(const SegmentInfoEntry&) = delete;
 
  const std::string file_name_;
  const int64_t start_time_;
  double duration_seconds_;
  const bool use_byte_range_;
  const uint64_t start_byte_offset_;
  const uint64_t segment_file_size_;
  const uint64_t previous_segment_end_offset_;
};
 
SegmentInfoEntry::SegmentInfoEntry(const std::string& file_name,
                                   int64_t start_time,
                                   double duration_seconds,
                                   bool use_byte_range,
                                   uint64_t start_byte_offset,
                                   uint64_t segment_file_size,
                                   uint64_t previous_segment_end_offset)
    : HlsEntry(HlsEntry::EntryType::kExtInf),
      file_name_(file_name),
      start_time_(start_time),
      duration_seconds_(duration_seconds),
      use_byte_range_(use_byte_range),
      start_byte_offset_(start_byte_offset),
      segment_file_size_(segment_file_size),
      previous_segment_end_offset_(previous_segment_end_offset) {}
 
std::string SegmentInfoEntry::ToString() {
  std::string result = absl::StrFormat("#EXTINF:%.3f,", duration_seconds_);
 
  if (use_byte_range_) {
    absl::StrAppendFormat(&result, "\n#EXT-X-BYTERANGE:%" PRIu64,
                          segment_file_size_);
    if (previous_segment_end_offset_ + 1 != start_byte_offset_) {
      absl::StrAppendFormat(&result, "@%" PRIu64, start_byte_offset_);
    }
  }
 
  absl::StrAppendFormat(&result, "\n%s", file_name_.c_str());
 
  return result;
}
 
class DiscontinuityEntry : public HlsEntry {
 public:
  DiscontinuityEntry();
 
  std::string ToString() override;
 
 private:
  DiscontinuityEntry(const DiscontinuityEntry&) = delete;
  DiscontinuityEntry& operator=(const DiscontinuityEntry&) = delete;
};
 
DiscontinuityEntry::DiscontinuityEntry()
    : HlsEntry(HlsEntry::EntryType::kExtDiscontinuity) {}
 
std::string DiscontinuityEntry::ToString() {
  return "#EXT-X-DISCONTINUITY";
}
 
ProgramDateTimeEntry::ProgramDateTimeEntry(const absl::Time& program_time)
    : HlsEntry(HlsEntry::EntryType::kProgramDateTime),
      program_time_(program_time) {}
 
std::string ProgramDateTimeEntry::ToString() {
  absl::CivilSecond cs =
      absl::ToCivilSecond(program_time_, absl::UTCTimeZone());
 
  int64_t total_ms = absl::ToUnixMillis(program_time_);
  int ms = static_cast<int>(total_ms % 1000);
  if (ms < 0)
    ms += 1000;  // correction for possible negative times
 
  return absl::StrFormat(
      "#EXT-X-PROGRAM-DATE-TIME:%04d-%02d-%02dT%02d:%02d:%02d.%03dZ", cs.year(),
      cs.month(), cs.day(), cs.hour(), cs.minute(), cs.second(), ms);
}
 
class PlacementOpportunityEntry : public HlsEntry {
 public:
  PlacementOpportunityEntry();
 
  std::string ToString() override;
 
 private:
  PlacementOpportunityEntry(const PlacementOpportunityEntry&) = delete;
  PlacementOpportunityEntry& operator=(const PlacementOpportunityEntry&) =
      delete;
};
 
PlacementOpportunityEntry::PlacementOpportunityEntry()
    : HlsEntry(HlsEntry::EntryType::kExtPlacementOpportunity) {}
 
std::string PlacementOpportunityEntry::ToString() {
  return "#EXT-X-PLACEMENT-OPPORTUNITY";
}
 
EncryptionInfoEntry::EncryptionInfoEntry(MediaPlaylist::EncryptionMethod method,
                                         const std::string& url,
                                         const std::string& key_id,
                                         const std::string& iv,
                                         const std::string& key_format,
                                         const std::string& key_format_versions)
    : HlsEntry(HlsEntry::EntryType::kExtKey),
      method_(method),
      url_(url),
      key_id_(key_id),
      iv_(iv),
      key_format_(key_format),
      key_format_versions_(key_format_versions) {}
 
std::string EncryptionInfoEntry::ToString() {
  return ToString("");
}
 
std::string EncryptionInfoEntry::ToString(std::string tag_name) {
  std::string tag_string;
  if (tag_name.empty())
    tag_name = "#EXT-X-KEY";
  Tag tag(tag_name, &tag_string);
 
  if (method_ == MediaPlaylist::EncryptionMethod::kSampleAes) {
    tag.AddString("METHOD", "SAMPLE-AES");
  } else if (method_ == MediaPlaylist::EncryptionMethod::kAes128) {
    tag.AddString("METHOD", "AES-128");
  } else if (method_ == MediaPlaylist::EncryptionMethod::kSampleAesCenc) {
    tag.AddString("METHOD", "SAMPLE-AES-CTR");
  } else {
    DCHECK(method_ == MediaPlaylist::EncryptionMethod::kNone);
    tag.AddString("METHOD", "NONE");
  }
 
  tag.AddQuotedString("URI", url_);
 
  if (!key_id_.empty()) {
    tag.AddString("KEYID", key_id_);
  }
  if (!iv_.empty()) {
    tag.AddString("IV", iv_);
  }
  if (!key_format_versions_.empty()) {
    tag.AddQuotedString("KEYFORMATVERSIONS", key_format_versions_);
  }
  if (!key_format_.empty()) {
    tag.AddQuotedString("KEYFORMAT", key_format_);
  }
 
  return tag_string;
}
 
MediaPlaylist::MediaPlaylist(const HlsParams& hls_params,
                             const std::string& file_name,
                             const std::string& name,
                             const std::string& group_id)
    : hls_params_(hls_params),
      file_name_(file_name),
      name_(name),
      group_id_(group_id),
      media_sequence_number_(hls_params_.media_sequence_number),
      reference_time_(absl::InfinitePast()) {
  // When there's a forced media_sequence_number, start with discontinuity
  if (media_sequence_number_ > 0)
    entries_.emplace_back(new DiscontinuityEntry());
}
 
MediaPlaylist::~MediaPlaylist() {}
 
void MediaPlaylist::SetStreamTypeForTesting(
    MediaPlaylistStreamType stream_type) {
  stream_type_ = stream_type;
}
 
void MediaPlaylist::SetCodecForTesting(const std::string& codec) {
  codec_ = codec;
}
 
void MediaPlaylist::SetLanguageForTesting(const std::string& language) {
  language_ = language;
}
 
void MediaPlaylist::SetCharacteristicsForTesting(
    const std::vector<std::string>& characteristics) {
  characteristics_ = characteristics;
}
 
void MediaPlaylist::SetIndexForTesting(uint32_t index) {
  media_info_.set_index(index);
}
 
void MediaPlaylist::SetForcedSubtitleForTesting(const bool forced_subtitle) {
  forced_subtitle_ = forced_subtitle;
}
 
void MediaPlaylist::AddEncryptionInfoForTesting(
    MediaPlaylist::EncryptionMethod method,
    const std::string& url,
    const std::string& key_id,
    const std::string& iv,
    const std::string& key_format,
    const std::string& key_format_versions) {
  entries_.emplace_back(new EncryptionInfoEntry(
      method, url, key_id, iv, key_format, key_format_versions));
}
 
bool MediaPlaylist::SetMediaInfo(const MediaInfo& media_info) {
  const int32_t time_scale = GetTimeScale(media_info);
  if (time_scale == 0) {
    LOG(ERROR) << "MediaInfo does not contain a valid timescale.";
    return false;
  }
 
  if (media_info.has_video_info()) {
    stream_type_ = MediaPlaylistStreamType::kVideo;
    codec_ = AdjustVideoCodec(media_info.video_info().codec());
    if (media_info.video_info().has_supplemental_codec() &&
        media_info.video_info().has_compatible_brand()) {
      supplemental_codec_ =
          AdjustVideoCodec(media_info.video_info().supplemental_codec());
      compatible_brand_ = static_cast<media::FourCC>(
          media_info.video_info().compatible_brand());
    }
  } else if (media_info.has_audio_info()) {
    stream_type_ = MediaPlaylistStreamType::kAudio;
    codec_ = media_info.audio_info().codec();
  } else {
    stream_type_ = MediaPlaylistStreamType::kSubtitle;
    codec_ = media_info.text_info().codec();
  }
 
  time_scale_ = time_scale;
  media_info_ = media_info;
  language_ = GetLanguage(media_info);
  use_byte_range_ = !media_info_.has_segment_template_url() &&
                    media_info_.container_type() != MediaInfo::CONTAINER_TEXT;
  characteristics_ =
      std::vector<std::string>(media_info_.hls_characteristics().begin(),
                               media_info_.hls_characteristics().end());
 
  forced_subtitle_ = media_info_.forced_subtitle();
 
  return true;
}
 
void MediaPlaylist::SetSampleDuration(int32_t sample_duration) {
  if (media_info_.has_video_info())
    media_info_.mutable_video_info()->set_frame_duration(sample_duration);
}
 
void MediaPlaylist::AddSegment(const std::string& file_name,
                               int64_t start_time,
                               int64_t duration,
                               uint64_t start_byte_offset,
                               uint64_t size) {
  if (stream_type_ == MediaPlaylistStreamType::kVideoIFramesOnly) {
    if (key_frames_.empty())
      return;
 
    AdjustLastSegmentInfoEntryDuration(key_frames_.front().timestamp);
 
    for (auto iter = key_frames_.begin(); iter != key_frames_.end(); ++iter) {
      // Last entry duration may be adjusted later when the next iframe becomes
      // available.
      const int64_t next_timestamp = std::next(iter) == key_frames_.end()
                                         ? (start_time + duration)
                                         : std::next(iter)->timestamp;
      AddSegmentInfoEntry(file_name, iter->timestamp,
                          next_timestamp - iter->timestamp,
                          iter->start_byte_offset, iter->size);
    }
    key_frames_.clear();
    return;
  }
  return AddSegmentInfoEntry(file_name, start_time, duration, start_byte_offset,
                             size);
}
 
void MediaPlaylist::SetReferenceTime(const absl::Time& reference_time) {
  reference_time_ = reference_time;
}
 
void MediaPlaylist::AddKeyFrame(int64_t timestamp,
                                uint64_t start_byte_offset,
                                uint64_t size) {
  if (stream_type_ != MediaPlaylistStreamType::kVideoIFramesOnly) {
    if (stream_type_ != MediaPlaylistStreamType::kVideo) {
      LOG(WARNING)
          << "I-Frames Only playlist applies to video renditions only.";
      return;
    }
    stream_type_ = MediaPlaylistStreamType::kVideoIFramesOnly;
    use_byte_range_ = true;
  }
  key_frames_.push_back({timestamp, start_byte_offset, size, std::string("")});
}
 
void MediaPlaylist::AddEncryptionInfo(MediaPlaylist::EncryptionMethod method,
                                      const std::string& url,
                                      const std::string& key_id,
                                      const std::string& iv,
                                      const std::string& key_format,
                                      const std::string& key_format_versions) {
  if (!inserted_discontinuity_tag_) {
    // Insert discontinuity tag only for the first EXT-X-KEY, only if there
    // are non-encrypted media segments.
    if (!entries_.empty())
      entries_.emplace_back(new DiscontinuityEntry());
    inserted_discontinuity_tag_ = true;
  }
  entries_.emplace_back(new EncryptionInfoEntry(
      method, url, key_id, iv, key_format, key_format_versions));
}
 
void MediaPlaylist::AddPlacementOpportunity() {
  entries_.emplace_back(new PlacementOpportunityEntry());
}
 
bool MediaPlaylist::WriteToFile(const std::filesystem::path& file_path,
                                bool event_to_vod_on_end_of_stream,
                                bool end_stream) {
  if (!target_duration_set_) {
    SetTargetDuration(ceil(GetLongestSegmentDuration()));
  }
 
  HlsPlaylistType playlist_type = hls_params_.playlist_type;
  if (event_to_vod_on_end_of_stream && end_stream &&
      playlist_type == HlsPlaylistType::kEvent) {
    playlist_type = HlsPlaylistType::kVod;
  }
 
  std::string content = CreatePlaylistHeader(
      media_info_, target_duration_, playlist_type, stream_type_,
      media_sequence_number_, discontinuity_sequence_number_,
      hls_params_.start_time_offset);
 
  for (const auto& entry : entries_)
    absl::StrAppendFormat(&content, "%s\n", entry->ToString().c_str());
 
  if (playlist_type == HlsPlaylistType::kVod) {
    content += "#EXT-X-ENDLIST\n";
  }
 
  if (!File::WriteFileAtomically(file_path.string().c_str(), content)) {
    LOG(ERROR) << "Failed to write playlist to: " << file_path.string();
    return false;
  }
  return true;
}
 
uint64_t MediaPlaylist::MaxBitrate() const {
  if (media_info_.has_bandwidth())
    return media_info_.bandwidth();
  return bandwidth_estimator_.Max();
}
 
uint64_t MediaPlaylist::AvgBitrate() const {
  return bandwidth_estimator_.Estimate();
}
 
double MediaPlaylist::GetLongestSegmentDuration() const {
  return longest_segment_duration_seconds_;
}
 
void MediaPlaylist::SetTargetDuration(int32_t target_duration) {
  if (target_duration_set_) {
    if (target_duration_ == target_duration)
      return;
    VLOG(1) << "Updating target duration from " << target_duration_ << " to "
            << target_duration;
  }
  target_duration_ = target_duration;
  target_duration_set_ = true;
}
 
int MediaPlaylist::GetNumChannels() const {
  return media_info_.audio_info().num_channels();
}
 
int MediaPlaylist::GetEC3JocComplexity() const {
  return media_info_.audio_info().codec_specific_data().ec3_joc_complexity();
}
 
bool MediaPlaylist::GetAC4ImsFlag() const {
  return media_info_.audio_info().codec_specific_data().ac4_ims_flag();
}
 
bool MediaPlaylist::GetAC4CbiFlag() const {
  return media_info_.audio_info().codec_specific_data().ac4_cbi_flag();
}
 
bool MediaPlaylist::GetDisplayResolution(uint32_t* width,
                                         uint32_t* height) const {
  DCHECK(width);
  DCHECK(height);
  if (media_info_.has_video_info()) {
    const double pixel_aspect_ratio =
        media_info_.video_info().pixel_height() > 0
            ? static_cast<double>(media_info_.video_info().pixel_width()) /
                  media_info_.video_info().pixel_height()
            : 1.0;
    *width = static_cast<uint32_t>(media_info_.video_info().width() *
                                   pixel_aspect_ratio);
    *height = media_info_.video_info().height();
    return true;
  }
  return false;
}
 
std::string MediaPlaylist::GetVideoRange() const {
  // Dolby Vision (dvh1 or dvhe) is always HDR.
  if (codec_.find("dvh") == 0)
    return "PQ";
 
  // HLS specification:
  // https://tools.ietf.org/html/draft-pantos-hls-rfc8216bis-02#section-4.4.4.2
  switch (media_info_.video_info().transfer_characteristics()) {
    case 1:
    case 6:
    case 13:
    case 14:
      // Dolby Vision profile 8.4 may have a transfer_characteristics 14, the
      // actual value refers to preferred_transfer_characteristic value in SEI
      // message, using compatible brand as a workaround
      if (!supplemental_codec_.empty() &&
          compatible_brand_ == media::FOURCC_db4g)
        return "HLG";
      else
        return "SDR";
    case 15:
      return "SDR";
    case 16:
      return "PQ";
    case 18:
      return "HLG";
    default:
      // Leave it empty if we do not have the transfer characteristics
      // information.
      return "";
  }
}
 
double MediaPlaylist::GetFrameRate() const {
  if (media_info_.video_info().frame_duration() == 0)
    return 0;
  return static_cast<double>(time_scale_) /
         media_info_.video_info().frame_duration();
}
 
void MediaPlaylist::AddSegmentInfoEntry(const std::string& segment_file_name,
                                        int64_t start_time,
                                        int64_t duration,
                                        uint64_t start_byte_offset,
                                        uint64_t size) {
  if (time_scale_ == 0) {
    LOG(WARNING) << "Timescale is not set and the duration for " << duration
                 << " cannot be calculated. The output will be wrong.";
 
    entries_.emplace_back(new SegmentInfoEntry(
        segment_file_name, 0.0, 0.0, use_byte_range_, start_byte_offset, size,
        previous_segment_end_offset_));
    return;
  }
 
  // In order for the oldest segment to be accessible for at least
  // |time_shift_buffer_depth| seconds, the latest segment should not be in the
  // sliding window since the player could be playing any part of the latest
  // segment. So the current segment duration is added to the sum of segment
  // durations (in the manifest/playlist) after sliding the window.
  SlideWindow();
 
  const double segment_duration_seconds =
      static_cast<double>(duration) / time_scale_;
  longest_segment_duration_seconds_ =
      std::max(longest_segment_duration_seconds_, segment_duration_seconds);
  bandwidth_estimator_.AddBlock(size, segment_duration_seconds);
  current_buffer_depth_ += segment_duration_seconds;
 
  if (!entries_.empty() &&
      entries_.back()->type() == HlsEntry::EntryType::kExtInf) {
    const SegmentInfoEntry* segment_info =
        static_cast<SegmentInfoEntry*>(entries_.back().get());
    if (segment_info->start_time() > start_time) {
      LOG(WARNING)
          << "Insert a discontinuity tag after the segment with start time "
          << segment_info->start_time() << " as the next segment starts at "
          << start_time << ".";
      entries_.emplace_back(new DiscontinuityEntry());
    }
  }
 
  if (hls_params_.add_program_date_time &&
      reference_time_ != absl::InfinitePast()) {
    // See if we need to add a program date time tag. It is added before the
    // first segment, and after every discontinuity.
    bool is_first_segment = true;
    bool is_discontinuity = false;
    if (!entries_.empty()) {
      for (auto it = entries_.rbegin(); it != entries_.rend(); ++it) {
        if ((*it)->type() == HlsEntry::EntryType::kExtInf) {
          is_first_segment = false;
          break;
        }
      }
 
      const auto& last = *entries_.back();
      if (last.type() == HlsEntry::EntryType::kExtDiscontinuity) {
        is_discontinuity = true;
      } else if (entries_.size() >= 2) {
        const auto& second_last = **std::prev(entries_.cend(), 2);
        if (last.type() == HlsEntry::EntryType::kExtKey &&
            second_last.type() == HlsEntry::EntryType::kExtDiscontinuity) {
          is_discontinuity = true;
        }
      }
    }
 
    if (is_first_segment || is_discontinuity) {
      const absl::Time program_time =
          reference_time_ +
          absl::Seconds(static_cast<double>(start_time) / time_scale_);
      entries_.emplace_back(new ProgramDateTimeEntry(program_time));
    }
  }
 
  entries_.emplace_back(new SegmentInfoEntry(
      segment_file_name, start_time, segment_duration_seconds, use_byte_range_,
      start_byte_offset, size, previous_segment_end_offset_));
  previous_segment_end_offset_ = start_byte_offset + size - 1;
}
 
void MediaPlaylist::AdjustLastSegmentInfoEntryDuration(int64_t next_timestamp) {
  if (time_scale_ == 0)
    return;
 
  const double next_timestamp_seconds =
      static_cast<double>(next_timestamp) / time_scale_;
 
  for (auto iter = entries_.rbegin(); iter != entries_.rend(); ++iter) {
    if (iter->get()->type() == HlsEntry::EntryType::kExtInf) {
      SegmentInfoEntry* segment_info =
          reinterpret_cast<SegmentInfoEntry*>(iter->get());
 
      const double segment_duration_seconds =
          next_timestamp_seconds -
          static_cast<double>(segment_info->start_time()) / time_scale_;
      // It could be negative if timestamp messed up.
      if (segment_duration_seconds > 0)
        segment_info->set_duration_seconds(segment_duration_seconds);
      longest_segment_duration_seconds_ =
          std::max(longest_segment_duration_seconds_, segment_duration_seconds);
      break;
    }
  }
}
 
// TODO(kqyang): Right now this class manages the segments including the
// deletion of segments when it is no longer needed. However, this class does
// not have access to the segment file paths, which is already translated to
// segment URLs by HlsNotifier. We have to re-generate segment file paths from
// segment template here in order to delete the old segments.
// To make the pipeline cleaner, we should move all file manipulations including
// segment management to an intermediate layer between HlsNotifier and
// MediaPlaylist.
void MediaPlaylist::SlideWindow() {
  if (hls_params_.time_shift_buffer_depth <= 0.0 ||
      hls_params_.playlist_type != HlsPlaylistType::kLive) {
    return;
  }
  DCHECK_GT(time_scale_, 0);
 
  if (current_buffer_depth_ <= hls_params_.time_shift_buffer_depth)
    return;
 
  // Temporary list to hold the EXT-X-KEYs. For example, this allows us to
  // remove <3> without removing <1> and <2> below (<1> and <2> are moved to the
  // temporary list and added back later).
  //    #EXT-X-KEY   <1>
  //    #EXT-X-KEY   <2>
  //    #EXTINF      <3>
  //    #EXTINF      <4>
  std::list<std::unique_ptr<HlsEntry>> ext_x_keys;
  // Consecutive key entries are either fully removed or not removed at all.
  // Keep track of entry types so we know if it is consecutive key entries.
  HlsEntry::EntryType prev_entry_type = HlsEntry::EntryType::kExtInf;
 
  std::list<std::unique_ptr<HlsEntry>>::iterator last = entries_.begin();
  for (; last != entries_.end(); ++last) {
    HlsEntry::EntryType entry_type = last->get()->type();
    if (entry_type == HlsEntry::EntryType::kExtKey) {
      if (prev_entry_type != HlsEntry::EntryType::kExtKey)
        ext_x_keys.clear();
      ext_x_keys.push_back(std::move(*last));
    } else if (entry_type == HlsEntry::EntryType::kExtDiscontinuity) {
      ++discontinuity_sequence_number_;
    } else {
      DCHECK_EQ(static_cast<int>(entry_type),
                static_cast<int>(HlsEntry::EntryType::kExtInf));
 
      const SegmentInfoEntry& segment_info =
          *reinterpret_cast<SegmentInfoEntry*>(last->get());
      // Remove the current segment only if it falls completely out of time
      // shift buffer range.
      const bool segment_within_time_shift_buffer =
          current_buffer_depth_ - segment_info.duration_seconds() <
          hls_params_.time_shift_buffer_depth;
      if (segment_within_time_shift_buffer)
        break;
      current_buffer_depth_ -= segment_info.duration_seconds();
      RemoveOldSegment(segment_info.start_time());
      media_sequence_number_++;
    }
    prev_entry_type = entry_type;
  }
  entries_.erase(entries_.begin(), last);
  // Add key entries back.
  entries_.insert(entries_.begin(), std::make_move_iterator(ext_x_keys.begin()),
                  std::make_move_iterator(ext_x_keys.end()));
}
 
void MediaPlaylist::RemoveOldSegment(int64_t start_time) {
  if (hls_params_.preserved_segments_outside_live_window == 0)
    return;
  if (stream_type_ == MediaPlaylistStreamType::kVideoIFramesOnly)
    return;
 
  segments_to_be_removed_.push_back(media::GetSegmentName(
      media_info_.segment_template(), start_time, media_sequence_number_ + 1,
      media_info_.bandwidth()));
  while (segments_to_be_removed_.size() >
         hls_params_.preserved_segments_outside_live_window) {
    const std::string& file_name = segments_to_be_removed_.front();
    VLOG(2) << "Deleting " << file_name;
    // DASH and HLS outputs could both be tracking the same files and are in a
    // race to delete them. Delete() returns false if the file does not exist,
    // but we only want to retry if the file does exist (indicating a failure
    // to delete, rather than the file already being gone). GetFileSize()
    // returns >= 0 if the file exists, and < 0 if it does not.
    if (!File::Delete(file_name.c_str()) &&
        File::GetFileSize(file_name.c_str()) >= 0) {
      LOG(WARNING) << "Failed to delete " << file_name << "; Will retry later.";
      break;
    }
    segments_to_be_removed_.pop_front();
  }
}
 
}  // namespace hls
}  // namespace shaka