Add algorithm for processing constraints for video content capture.

content/renderer/media/media_stream_constraints_util_video_content.cc

+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "content/renderer/media/media_stream_constraints_util_video_content.h"
+
+#include <cmath>
+#include <utility>
+#include <vector>
+
+#include "content/renderer/media/media_stream_constraints_util_sets.h"
+#include "content/renderer/media/media_stream_video_source.h"
+#include "media/base/limits.h"
+#include "third_party/WebKit/public/platform/WebMediaConstraints.h"
+#include "third_party/WebKit/public/platform/WebString.h"
+
+namespace content {
+
+namespace {
+
+using Point = ResolutionSet::Point;
+
+// Hard upper- and lower-bound frame rates for tab/desktop capture.

[hta - Chromium, 2017/03/08 13:34:08]

Nit: Dashes shouldn't be here. "Hard upper and lower bounds for the frame rates
for tab/desktop capture".

[Guido Urdaneta, 2017/03/09 14:38:38]

Done.

+constexpr double kMaxScreenCastFrameRate = 120.0;
+constexpr double kMinScreenCastFrameRate = 1.0 / 60.0;
+
+constexpr double kDefaultFrameRate = MediaStreamVideoSource::kDefaultFrameRate;
+
+constexpr int kMinScreenCastDimension = 1;
+constexpr int kMaxScreenCastDimension = media::limits::kMaxDimension - 1;

[hta - Chromium, 2017/03/08 13:34:08]

Still wonder why you do -1 on this number so that it's 32766 rather than 32767
(and if it matters).

[Guido Urdaneta, 2017/03/09 14:38:38]

The actual limit  is kMaxDimension-1. 
See
https://cs.chromium.org/chromium/src/media/capture/video_capture_types.cc?typ...
For some reason, a format is valid only if its dimensions are less than (not <=)
kMaxDimension.

+constexpr double kMinScreenCastAspectRatio =
+    static_cast<double>(kMinScreenCastDimension) /
+    static_cast<double>(kMaxScreenCastDimension);
+constexpr double kMaxScreenCastAspectRatio =
+    static_cast<double>(kMaxScreenCastDimension) /
+    static_cast<double>(kMinScreenCastDimension);
+
+using StringSet = DiscreteSet<std::string>;
+StringSet StringSetFromConstraint(const blink::StringConstraint& constraint) {
+  if (!constraint.hasExact())
+    return StringSet::UniversalSet();
+
+  std::vector<std::string> elements;
+  for (const auto& entry : constraint.exact())
+    elements.push_back(entry.ascii());
+
+  return StringSet(std::move(elements));
+}
+
+using BoolSet = DiscreteSet<bool>;
+BoolSet BoolSetFromConstraint(const blink::BooleanConstraint& constraint) {
+  if (!constraint.hasExact())
+    return BoolSet::UniversalSet();
+
+  return BoolSet({constraint.exact()});
+}
+
+using DoubleRangeSet = NumericRangeSet<double>;
+
+class VideoContentCaptureCandidates {
+ public:
+  VideoContentCaptureCandidates()
+      : device_id_set(StringSet::UniversalSet()),
+        noise_reduction_set(BoolSet::UniversalSet()) {}
+  explicit VideoContentCaptureCandidates(
+      const blink::WebMediaTrackConstraintSet& constraint_set)
+      : resolution_set(ResolutionSet::FromConstraintSet(constraint_set)),
+        frame_rate_set(
+            DoubleRangeSet::FromConstraint(constraint_set.frameRate)),
+        device_id_set(StringSetFromConstraint(constraint_set.deviceId)),
+        noise_reduction_set(
+            BoolSetFromConstraint(constraint_set.googNoiseReduction)) {}
+
+  VideoContentCaptureCandidates(VideoContentCaptureCandidates&& other) =
+      default;
+  VideoContentCaptureCandidates& operator=(
+      VideoContentCaptureCandidates&& other) = default;
+
+  bool IsEmpty() const {
+    return resolution_set.IsEmpty() || frame_rate_set.IsEmpty() ||
+           device_id_set.IsEmpty() || noise_reduction_set.IsEmpty();
+  }
+
+  VideoContentCaptureCandidates Intersection(
+      const VideoContentCaptureCandidates& other) {
+    VideoContentCaptureCandidates intersection;
+    intersection.resolution_set =
+        resolution_set.Intersection(other.resolution_set);
+    intersection.frame_rate_set =
+        frame_rate_set.Intersection(other.frame_rate_set);
+    intersection.device_id_set =
+        device_id_set.Intersection(other.device_id_set);
+    intersection.noise_reduction_set =
+        noise_reduction_set.Intersection(other.noise_reduction_set);
+    return intersection;
+  }
+
+  ResolutionSet resolution_set;
+  DoubleRangeSet frame_rate_set;
+  StringSet device_id_set;
+  BoolSet noise_reduction_set;
+};
+
+media::ResolutionChangePolicy SelectResolutionPolicyFromCandidates(
+    const ResolutionSet& resolution_set,
+    const blink::WebMediaTrackConstraintSet& basic_constraint_set,
+    int min_height_capability,
+    int max_height_capability,
+    int min_width_capability,
+    int max_width_capability) {
+  double min_aspect_ratio_capability =
+      static_cast<double>(min_width_capability) /
+      static_cast<double>(max_height_capability);
+  double max_aspect_ratio_capability =
+      static_cast<double>(max_width_capability) /
+      static_cast<double>(min_height_capability);
+  bool can_adjust_height = !basic_constraint_set.height.hasIdeal() &&
+                           resolution_set.min_height() <= min_height_capability;
+
+  bool can_adjust_width = !basic_constraint_set.width.hasIdeal() &&
+                          resolution_set.min_width() <= min_width_capability;
+
+  bool can_adjust_aspect_ratio =
+      !basic_constraint_set.aspectRatio.hasIdeal() &&

[hta - Chromium, 2017/03/08 13:34:08]

Here (and above) you're saying that if ideal is specified, the ability to adjust
resolution is gone.
This may be at odds with intention of "ideal", which is "you're free to vary,
but prefer this".

It may be the right thing to do for now, but the discrepancy (if there is one)
needs mentioning in a comment.

[Guido Urdaneta, 2017/03/09 14:38:38]

After looking at what the policies actually do, using a new algorithm and added
a separate test for this.
Note that I decided to copy code from WebContentsCaptureMachine and added a TODO
to make the code shareable.
The copied code is simple enough that it was easier to copy it than to make an
alternative "simple" implementation that required to be synced with
WebContentsCaptureMachine anyway.
WDYT?

+      resolution_set.min_aspect_ratio() <= min_aspect_ratio_capability &&
+      resolution_set.max_aspect_ratio() >= max_aspect_ratio_capability;
+  if (can_adjust_height && can_adjust_width) {
+    return can_adjust_aspect_ratio
+               ? media::RESOLUTION_POLICY_ANY_WITHIN_LIMIT
+               : media::RESOLUTION_POLICY_FIXED_ASPECT_RATIO;
+  }
+
+  return media::RESOLUTION_POLICY_FIXED_RESOLUTION;
+}
+
+int RoundToInt(double d) {
+  return static_cast<int>(std::round(d));
+}
+
+gfx::Size ToGfxSize(const Point& point) {
+  return gfx::Size(RoundToInt(point.width()), RoundToInt(point.height()));
+}
+
+double SelectFrameRateFromCandidates(
+    const DoubleRangeSet& candidate_set,
+    const blink::WebMediaTrackConstraintSet& basic_constraint_set) {
+  double frame_rate = basic_constraint_set.frameRate.hasIdeal()
+                          ? basic_constraint_set.frameRate.ideal()
+                          : kDefaultFrameRate;
+  if (frame_rate > candidate_set.Max())
+    frame_rate = candidate_set.Max();
+  else if (frame_rate < candidate_set.Min())
+    frame_rate = candidate_set.Min();
+
+  return frame_rate;
+}
+
+media::VideoCaptureParams SelectVideoCaptureParamsFromCandidates(
+    const VideoContentCaptureCandidates& candidates,
+    const blink::WebMediaTrackConstraintSet& basic_constraint_set) {
+  double requested_frame_rate = SelectFrameRateFromCandidates(
+      candidates.frame_rate_set, basic_constraint_set);
+  Point requested_resolution =
+      candidates.resolution_set.SelectClosestPointToIdeal(basic_constraint_set);
+  media::VideoCaptureParams params;
+  params.requested_format = media::VideoCaptureFormat(
+      ToGfxSize(requested_resolution), static_cast<float>(requested_frame_rate),
+      media::PIXEL_FORMAT_I420);
+  params.resolution_change_policy = SelectResolutionPolicyFromCandidates(
+      candidates.resolution_set, basic_constraint_set, kMinScreenCastDimension,
+      params.requested_format.frame_size.height(), kMinScreenCastDimension,
+      params.requested_format.frame_size.width());
+  DCHECK(params.IsValid());
+
+  return params;
+}
+
+std::string SelectDeviceIDFromCandidates(
+    const StringSet& candidates,
+    const blink::WebMediaTrackConstraintSet& basic_constraint_set) {
+  DCHECK(!candidates.IsEmpty());
+  if (basic_constraint_set.deviceId.hasIdeal()) {
+    std::string ideal_value =

[hta - Chromium, 2017/03/08 13:34:08]

Should you loop over deviceId.ideal() here?

for (const auto it : basic_constraint_set.deviceId.ideal()) {
   if (candidates.Contains(it->ascii())
      return it->ascii();
}

or something like that.
{id: ideal: ["foo", "bar"]} is allowed by the WebIDL syntax.

[Guido Urdaneta, 2017/03/09 14:38:38]

Done. Also added test for this.

+        basic_constraint_set.deviceId.ideal().begin()->ascii();
+    if (candidates.Contains(ideal_value)) {
+      return ideal_value;
+    }
+  }
+
+  if (candidates.is_universal()) {
+    return std::string();
+  }
+
+  return candidates.FirstElement();
+}
+
+rtc::Optional<bool> SelectNoiseReductionFromCandidates(
+    const BoolSet& candidates,
+    const blink::WebMediaTrackConstraintSet& basic_constraint_set) {
+  DCHECK(!candidates.IsEmpty());
+  if (basic_constraint_set.googNoiseReduction.hasIdeal() &&
+      candidates.Contains(basic_constraint_set.googNoiseReduction.ideal())) {
+    return rtc::Optional<bool>(basic_constraint_set.googNoiseReduction.ideal());
+  }
+
+  if (candidates.is_universal())
+    return rtc::Optional<bool>();
+
+  return rtc::Optional<bool>(candidates.FirstElement());
+}
+
+VideoContentCaptureSourceSelectionResult SelectResultFromCandidates(
+    const VideoContentCaptureCandidates& candidates,
+    const blink::WebMediaTrackConstraintSet& basic_constraint_set) {
+  VideoContentCaptureSourceSelectionResult result;
+  result.failed_constraint_name = nullptr;
+  result.capture_params =
+      SelectVideoCaptureParamsFromCandidates(candidates, basic_constraint_set);
+  result.device_id = SelectDeviceIDFromCandidates(candidates.device_id_set,
+                                                  basic_constraint_set);
+  result.noise_reduction = SelectNoiseReductionFromCandidates(
+      candidates.noise_reduction_set, basic_constraint_set);
+  return result;
+}
+
+VideoContentCaptureSourceSelectionResult UnsatisfiedConstraintsResult(
+    const VideoContentCaptureCandidates& candidates,
+    const blink::WebMediaTrackConstraintSet& constraint_set) {
+  DCHECK(candidates.IsEmpty());
+  VideoContentCaptureSourceSelectionResult result;
+  if (candidates.resolution_set.IsHeightEmpty()) {
+    result.failed_constraint_name = constraint_set.height.name();

[hta - Chromium, 2017/03/08 13:34:08]

Would it be as clear to have a constructor for result that took the failed
constraint name as a parameter, and do

return VideoContentCaptureSourceSelectionResult(constraint_set.height.name())

here?
If doing that, can you avoid having the parameterless constructor, and make
failed_constraint_name be an accessor to a private field?

Is there anything else you really need to have changeable, as opposed to being
able to pass it in as a constructor parameters?

[Guido Urdaneta, 2017/03/09 14:38:38]

Done.

+  } else if (candidates.resolution_set.IsWidthEmpty()) {
+    result.failed_constraint_name = constraint_set.width.name();
+  } else if (candidates.resolution_set.IsAspectRatioEmpty()) {
+    result.failed_constraint_name = constraint_set.aspectRatio.name();
+  } else if (candidates.frame_rate_set.IsEmpty()) {
+    result.failed_constraint_name = constraint_set.frameRate.name();
+  } else if (candidates.noise_reduction_set.IsEmpty()) {
+    result.failed_constraint_name = constraint_set.googNoiseReduction.name();
+  } else {
+    DCHECK(candidates.device_id_set.IsEmpty());
+    result.failed_constraint_name = constraint_set.frameRate.name();

[hta - Chromium, 2017/03/08 13:34:08]

This choice seems odd - checking on device_id_iset and then returning
"frameRate".

[Guido Urdaneta, 2017/03/09 14:38:38]

Fixed. In practice this can't be reached because any string is currently
accepted as device_id, as there is no way to have an enumeration of valid device
IDs here.
This is the reason it wasn't caught by an Overconstrained test (there is no way
to overconstrain the ID at this stage).
If an invalid device ID is given, that is handled at a later stage.

+  }
+
+  return result;
+}
+
+}  // namespace
+
+VideoContentCaptureSourceSelectionResult::
+    VideoContentCaptureSourceSelectionResult()
+    : failed_constraint_name("") {}
+VideoContentCaptureSourceSelectionResult::
+    VideoContentCaptureSourceSelectionResult(
+        const VideoContentCaptureSourceSelectionResult& other) = default;
+VideoContentCaptureSourceSelectionResult::
+    VideoContentCaptureSourceSelectionResult(
+        VideoContentCaptureSourceSelectionResult&& other) = default;
+VideoContentCaptureSourceSelectionResult::
+    ~VideoContentCaptureSourceSelectionResult() = default;
+VideoContentCaptureSourceSelectionResult&
+VideoContentCaptureSourceSelectionResult::operator=(
+    const VideoContentCaptureSourceSelectionResult& other) = default;
+VideoContentCaptureSourceSelectionResult&
+VideoContentCaptureSourceSelectionResult::operator=(
+    VideoContentCaptureSourceSelectionResult&& other) = default;
+
+bool VideoContentCaptureSourceSelectionResult::HasValue() const {
+  return failed_constraint_name == nullptr;
+}
+
+int VideoContentCaptureSourceSelectionResult::Height() const {
+  DCHECK(HasValue());
+  return capture_params.requested_format.frame_size.height();
+}
+
+int VideoContentCaptureSourceSelectionResult::Width() const {
+  DCHECK(HasValue());
+  return capture_params.requested_format.frame_size.width();
+}
+
+float VideoContentCaptureSourceSelectionResult::FrameRate() const {
+  DCHECK(HasValue());
+  return capture_params.requested_format.frame_rate;
+}
+
+media::ResolutionChangePolicy
+VideoContentCaptureSourceSelectionResult::ResolutionChangePolicy() const {
+  DCHECK(HasValue());
+  return capture_params.resolution_change_policy;
+}
+
+VideoContentCaptureSourceSelectionResult
+SelectVideoContentCaptureSourceSettings(
+    const blink::WebMediaConstraints& constraints) {
+  VideoContentCaptureCandidates candidates;
+  candidates.resolution_set =
+      ResolutionSet(kMinScreenCastDimension, kMaxScreenCastDimension,
+                    kMinScreenCastDimension, kMaxScreenCastDimension,
+                    kMinScreenCastAspectRatio, kMaxScreenCastAspectRatio);
+  candidates.frame_rate_set =
+      DoubleRangeSet(kMinScreenCastFrameRate, kMaxScreenCastFrameRate);
+  // candidates.device_id_set and candidates.noise_reduction_set are
+  // automatically initialized with the universal set.
+
+  candidates = candidates.Intersection(
+      VideoContentCaptureCandidates(constraints.basic()));
+  if (candidates.IsEmpty())
+    return UnsatisfiedConstraintsResult(candidates, constraints.basic());
+
+  for (const auto& advanced_set : constraints.advanced()) {
+    VideoContentCaptureCandidates advanced_candidates(advanced_set);
+    VideoContentCaptureCandidates intersection =
+        candidates.Intersection(advanced_candidates);
+    if (!intersection.IsEmpty())
+      candidates = std::move(intersection);
+  }
+
+  DCHECK(!candidates.IsEmpty());
+  return SelectResultFromCandidates(candidates, constraints.basic());
+}
+
+}  // namespace content