Add utility set classes to support getUserMedia constraint proccessing.

content/renderer/media/media_stream_constraints_util_sets.h

+// 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.
+
+#ifndef CONTENT_RENDERER_MEDIA_MEDIA_STREAM_CONSTRAINTS_UTIL_SETS_H_
+#define CONTENT_RENDERER_MEDIA_MEDIA_STREAM_CONSTRAINTS_UTIL_SETS_H_
+
+#include <algorithm>
+#include <limits>
+#include <utility>
+#include <vector>
+
+#include "base/gtest_prod_util.h"
+#include "base/logging.h"
+#include "content/common/content_export.h"
+#include "media/base/limits.h"
+
+namespace blink {
+struct WebMediaTrackConstraintSet;
+}
+
+namespace content {
+
+// This class template represents a set of candidates suitable for a numeric
+// range-based constraint.
+template <typename T>
+class NumericRangeSet {
+ public:
+  NumericRangeSet() : min_(0), max_(DefaultMax()) {}
+  NumericRangeSet(T min, T max) : min_(min), max_(max) {}
+  NumericRangeSet(const NumericRangeSet& other) = default;
+  NumericRangeSet& operator=(const NumericRangeSet& other) = default;
+  ~NumericRangeSet() = default;
+
+  T Min() const { return min_; }
+  T Max() const { return max_; }
+  bool IsEmpty() const { return max_ < min_; }
+
+  NumericRangeSet Intersection(const NumericRangeSet& other) const {
+    return NumericRangeSet(std::max(min_, other.min_),
+                           std::min(max_, other.max_));
+  }
+
+  // Creates a NumericRangeSet based on the minimum and maximum values of
+  // |constraint|.
+  template <typename ConstraintType>
+  static auto FromConstraint(ConstraintType constraint)
+      -> NumericRangeSet<decltype(constraint.min())> {
+    return NumericRangeSet<decltype(constraint.min())>(
+        ConstraintHasMin(constraint) ? ConstraintMin(constraint) : 0,
+        ConstraintHasMax(constraint) ? ConstraintMax(constraint)
+                                     : DefaultMax());
+  }
+
+ private:
+  static inline T DefaultMax() {
+    return std::numeric_limits<T>::has_infinity
+               ? std::numeric_limits<T>::infinity()
+               : std::numeric_limits<T>::max();
+  }
+  T min_;
+  T max_;
+};
+
+// This class defines a set of discrete elements suitable for resolving
+// constraints with a countable number of choices not suitable to be constrained
+// by range such as strings, booleans and certain constraints of type long.

[hta - Chromium, 2017/03/03 11:02:36]

Better language: "... not suitable to be constrained by a range. Examples are
strings..."

[Guido Urdaneta, 2017/03/06 11:08:23]

Done.

+// The set of elements of an unconstrained set is application defined.

[hta - Chromium, 2017/03/03 11:02:36]

I don't understand what this sentence tries to say. Delete?

[hbos_chromium, 2017/03/03 16:01:42]

The unconstrained set is a set that conceptually contains all elements in the
universe (https://en.wikipedia.org/wiki/Universe_(mathematics)), represented by
a bool instead of filling up the vector with all elements. Would it be more
appropriate to call it "the universal set"?

Replace the last sentence by a comment explaining that the
unconstrained/universal set represents a set containing any possible element.

[Guido Urdaneta, 2017/03/06 11:08:23]

Addressed following hbos' suggestion.

[Guido Urdaneta, 2017/03/06 11:08:23]

Done.

+template <typename T>
+class DiscreteSet {
+ public:
+  // Creates an unconstrained set.
+  DiscreteSet() : is_unconstrained_(true) {}

[hbos_chromium, 2017/03/03 16:01:42]

I would prefer a static function similar to EmptySet() for the
unconstrained/universal set.

[Guido Urdaneta, 2017/03/06 11:08:23]

Done.
Also renamed is_unconstrained to is_universal.

+  // Creates a set containing the elements in |elements|.
+  // It is the responsibility of the caller to ensure that |elements| is not
+  // equivalent to the unconstrained set and that |elements| has no repeated
+  // values. Takes ownership of |elements|.
+  explicit DiscreteSet(std::vector<T> elements)
+      : is_unconstrained_(false), elements_(std::move(elements)) {}
+  // Creates an empty set;
+  static DiscreteSet EmptySet() { return DiscreteSet(std::vector<T>()); }
+
+  DiscreteSet(const DiscreteSet& other) = default;

[hta - Chromium, 2017/03/03 11:02:36]

C++ query: Is there any code-generation effect from declaring all these
defaults? I thought they'd be declared by default as long as there's no
restricted members in the class.

If the point is to make it explicit that the class has them, that's a valid
reason, but it looks odd to me.

[Guido Urdaneta, 2017/03/06 11:08:23]

This is intended. I want the class to be copyable and movable. If nothing is
declared, only copy constructors are generated. If only the move constructors
are declared, then it's move only. So all the defaults are required.

+  DiscreteSet& operator=(const DiscreteSet& other) = default;
+  DiscreteSet(DiscreteSet&& other) = default;
+  DiscreteSet& operator=(DiscreteSet&& other) = default;
+  ~DiscreteSet() = default;
+
+  bool Contains(const T& value) const {
+    return is_unconstrained_ ||
+           std::find(elements_.begin(), elements_.end(), value) !=
+               elements_.end();
+  }
+
+  bool IsEmpty() const { return !is_unconstrained_ && elements_.empty(); }
+
+  bool IsNonEmptyFinite() const { return !elements_.empty(); }
+
+  DiscreteSet Intersection(const DiscreteSet& other) const {
+    if (is_unconstrained_)
+      return other;
+    if (other.is_unconstrained_)
+      return *this;
+    if (IsEmpty() || other.IsEmpty())
+      return EmptySet();
+
+    // Both sets are finite and nonempty.

[hta - Chromium, 2017/03/03 11:02:36]

s/finite/constrained/

[Guido Urdaneta, 2017/03/06 11:08:23]

Done.
Changed the wording to both sets have explicit elements.

+    std::vector<T> intersection;
+    for (const auto& entry : elements_) {
+      auto it =
+          std::find(other.elements_.begin(), other.elements_.end(), entry);
+      if (it != other.elements_.end()) {
+        intersection.push_back(entry);
+      }
+    }
+    return DiscreteSet(std::move(intersection));

[hbos_chromium, 2017/03/03 16:01:42]

std::set would yield O(n log n) instead of O(n^2) but that would only matter for
larger sets.

[Guido Urdaneta, 2017/03/06 11:08:23]

Yes. For small sets vector is faster and makes it easier to designate the first
element as "default".
If it becomes a problem, we can change it.
I expect these sets to have few elements, with 0 and 1 being common sizes.

+  }
+
+  // Returns a copy of the first element in the set. This is useful as a simple
+  // tie-breaker rule.

[hbos_chromium, 2017/03/03 16:01:42]

Add a comment saying that this is not applicable to the unconstrained/universal
set.

[Guido Urdaneta, 2017/03/06 11:08:23]

Done.

+  T FirstElement() const {
+    DCHECK(IsNonEmptyFinite());
+    return elements_[0];
+  }
+
+  bool is_unconstrained() const { return is_unconstrained_; }
+
+ private:
+  bool is_unconstrained_;
+  std::vector<T> elements_;

[hta - Chromium, 2017/03/03 11:02:36]

Query: Would this work with std::set<>?

In that case, the only difference between DiscreteSet() and set<> seems to be
the FirstElement operator and the ability to have "anything goes" sets.

[hbos_chromium, 2017/03/03 16:01:42]

(In that case this could be represented by an Optional<std::set<T>> and an
Intersection function, but I think a class yields clearer code than "has
value".)

[Guido Urdaneta, 2017/03/06 11:08:23]

Acknowledged.

[Guido Urdaneta, 2017/03/06 11:08:23]

This type is basically a wrapper over std::vector to have a convenient API to do
intersection, get a default value (first element) and check if it's empty or
unconstrained/universal.

When I upload the algorithm for video content the reason for the API will be
clearer, but it goes roughly like this:

Set set(FromConstraints(constraints.basic().someConstraint))
if (set.IsEmpty())
   Overconstrained();

for (auto a : constraints.advanced()) {
   Set intersection = set.Intersection(FromConstraints(a));
   if (!intersection.IsEmpty()) {
     set = std::move(intersection);
   }
}

if (basic.hasIdeal() && set.Contains(ideal))
   return ideal;

if (set.is_universal())
   return kDefaultValue;

return set.FirstValue();


set<> does not give us that nice API to express SelectSettings so directly.

We might also need a Subset or Superset function to deal with device
capabilities, but the current version is good enough to start the review.
Also, if we decide to implement more complex discrete sets (e.g., migrate the
algorithm for device sources to this), we can redefine GetFirstElement to
implement any tie-breaker we want, or we can define additional methods if
needed.

+};
+
+// This class represents a set of (height, width) screen resolution candidates
+// determined by width, height and aspect-ratio constraints.
+class CONTENT_EXPORT ResolutionSet {
+ public:
+  static constexpr int kMinConstrainedDimension = 1;
+  static constexpr int kMaxConstrainedDimension =
+      media::limits::kMaxDimension - 1;

[hta - Chromium, 2017/03/03 11:02:36]

kMaxDimension is already 32767 - I think you're using kMaxConstrainedDimension+1
as a flag value saying "very high" - if so, add a comment here saying that - or
better, make a new constant with that value and a descriptive name, such as
"kNotReallyConstrainedOnMaxDimension" (that's a bad name!!!)

[Guido Urdaneta, 2017/03/06 11:08:23]

Got rid of all the "Constrained" constants and methods.
Sets now support aspect ratio from 0 to Inf, and dimensions from 0 to MaxInt.
Clamping values to actual supported resolutions will be the responsibility of
the SelectSettings implementations.

+  static constexpr int kMinConstrainedAspectRatio =
+      static_cast<double>(kMinConstrainedDimension) /
+      static_cast<double>(kMaxConstrainedDimension);
+  static constexpr int kMaxConstrainedAspectRatio =
+      static_cast<double>(kMaxConstrainedDimension) /
+      static_cast<double>(kMinConstrainedDimension);

[hbos_chromium, 2017/03/03 16:01:42]

Doesn't it make more sense to use max and min (not -1)? Is it important to be
able to say that if you constrain it to the max value it's not constrained
because it is the maximum? I think we should cover the full range of possible
values.

[Guido Urdaneta, 2017/03/06 11:08:23]

I think you're right. The class now just supports the full range and there is no
concept of "constrained" anymore. It's just a set.
No special universal or unconstrained set is needed either, since the set of
supported values is determined by the ranges, just like NumericRangeSet.

+
+  // Helper class that represents (height, width) points on a plane.
+  class Point {

[hta - Chromium, 2017/03/03 11:02:36]

I'm not sure of the value of another point class.
We already have, for instance, gfx::Point with many of the same properties.

[hbos_chromium, 2017/03/03 16:01:42]

Point uses int. There is gfx::PointF and gfx::Vector2dF both using float (not
double). The vector would be appropriate considering the vector operations.
Prefer gfx::Vector2dF over this.

[Guido Urdaneta, 2017/03/06 11:08:22]

I prefer to keep this class (at least for one more iteration) because it's a
pair of doubles.
gfx::Vector2dF would be a reasonable replacement, but it uses float. Single
precision requires a lot more care with the math due to the low precision. Since
we generate just a few values, there is no significant performance or space
penalty for using doubles.

Note that I reimplemented using gfx::Vector2dF and using a tolerance of 1e-4 one
test fails. A second test starts failing at 1e-8.
With doubles this happens at 1e-8 and 1e-16, respectively, which means double
provides much more stable results.

Although the tests include plenty of comparisons with computed values that have
errors, it is far from comprehensive in that regard. If we have tests that fail
with 1e-4, it would be prudent to use 0.01 or even 0.1 in production (which is
kind of large), or spend more time thinking about floating point.

The only thing Point "duplicates" with respect to Vector2dF is +,-,==,!= and
Dot, which are all one-liners (we can get rid of !=, which is used only in
testing). I think reducing our floating-point worries is worth duplicating four
one-liners. WDYT?

[Guido Urdaneta, 2017/03/06 11:08:23]

See reply to hbos.

+   public:
+    // Creates a (|height|, |width|) point. |height| and |width| must be finite.
+    Point(double height, double width);
+    Point(const Point& other);
+    Point& operator=(const Point& other);
+    ~Point();
+
+    // Accessors.
+    double height() const { return height_; }
+    double width() const { return width_; }
+    double AspectRatio() const { return width_ / height_; }

[hbos_chromium, 2017/03/03 16:01:42]

Watch out for divide by zero?

[Guido Urdaneta, 2017/03/06 11:08:22]

divide by zero is fine in most cases. NaN (0/0 or Inf/Inf) is a greater concern,
but the code handles it OK.
There is a new test with extreme ideal values that exercises this kind of thing
to a greater extent.

+
+    // Exact equality/inequality operators.
+    bool operator==(const Point& other) const;
+    bool operator!=(const Point& other) const;
+
+    // Returns true if both coordinates of this point and |other| are
+    // approximately equal.
+    bool IsApproximatelyEqualTo(const Point& other) const;
+
+    // Vector-style addition and subtraction operators.
+    Point operator+(const Point& other) const;
+    Point operator-(const Point& other) const;
+
+    // Returns the dot product between |p1| and |p2|.
+    static double Dot(const Point& p1, const Point& p2);
+
+    // Returns the square Euclidean distance from |p1| to |p2|.

[hta - Chromium, 2017/03/03 11:02:36]

Does it return the square of the distance or the distance?
If the latter, remove "square".

[hbos_chromium, 2017/03/03 16:01:42]

It's the square, so the function should be renamed DistanceToPointSquared.

[Guido Urdaneta, 2017/03/06 11:08:22]

Renamed.

[Guido Urdaneta, 2017/03/06 11:08:23]

Square Euclidean is still a distance :)
But renamed anyway to SquareEuclideanDistance. 
DistanceToPoint was a bad name anyway (it was originally a nonstatic method)

+    static double DistanceToPoint(const Point& p1, const Point& p2);
+
+    // Returns the point in the line segment determined by |s1| and |s2| that
+    // is closest to |p|.
+    static Point ClosestPointInSegment(const Point& p,
+                                       const Point& s1,
+                                       const Point& s2);
+
+   private:
+    double height_;
+    double width_;

[hbos_chromium, 2017/03/03 16:01:42]

The point has no width and height, only coordinates, x and y are better names
for that I think.

[Guido Urdaneta, 2017/03/06 11:08:23]

I like height and width better to avoid confusion with aspect ratios and other
code where it's more convenient to think of the points as screen resolutions.
Although the Point class has generic 2D-vector operations, that's just a
byproduct of the approach chosen to solve the problem of distance to ideal. If
we were to change the algorithm, the Point class might not need to be so much
like a vector, but it would still have width, height and aspect ratio.

Perhaps we should hide the vector-like operations in the .cc file, even at the
cost of direct testability. 

[hbos_chromium, 2017/03/08 21:03:00]

The way I see it is: Input to the algorithm is width and height but this class
is used as a point, with distance calculations, line segments, polygons and
vector math, it's fairly generic. It's even named Point.

But this is nitty. If you want to keep it as-is could you add a TODO saying if a
Vector2dD becomes available use that instead?

+  };
+
+  ResolutionSet();  // Creates an unconstrained candidate set.
+  ResolutionSet(int min_height,
+                int max_height,
+                int min_width,
+                int max_width,
+                double min_aspect_ratio,
+                double max_aspect_ratio);
+  ResolutionSet(const ResolutionSet& other);
+  ResolutionSet& operator=(const ResolutionSet& other);
+  ~ResolutionSet();
+
+  // Getters.
+  int min_height() const { return min_height_; }
+  int max_height() const { return max_height_; }
+  int min_width() const { return min_width_; }
+  int max_width() const { return max_width_; }
+  double min_aspect_ratio() const { return min_aspect_ratio_; }
+  double max_aspect_ratio() const { return max_aspect_ratio_; }
+
+  // Returns true if this set is empty.
+  bool IsEmpty() const;
+
+  // These functions return true if a particular constraint causes the set to
+  // be empty.
+  bool IsHeightEmpty() const;
+  bool IsWidthEmpty() const;
+  bool IsAspectRatioEmpty() const;
+
+  // These functions return true if a particular variable is constrained.
+  // MinHeight and MinWidth are unconstrained if their value is less than
+  // kMinValidDimension.
+  // MaxHeight and MaxWidth are unconstrained if their value is greater than
+  // kMaxValidDimension.
+  // MinAspectRatio is unconstrained if its value is 0.0 or less.
+  // MaxAspectRatio is unconstrained if its value is positive infinity.
+  bool HasMinHeight() const;
+  bool HasMaxHeight() const;
+  bool HasMinWidth() const;
+  bool HasMaxWidth() const;
+  bool HasMinAspectRatio() const;
+  bool HasMaxAspectRatio() const;
+
+  // These functions return true if a particular variable is unconstrained on
+  // both ends.
+  bool IsHeightUnconstrained() const;
+  bool IsWidthUnconstrained() const;
+  bool IsAspectRatioUnconstrained() const;
+
+  // Returns true if the point (height, width) is included in this set.
+  bool ContainsPoint(int height, int width) const;
+  bool ContainsPoint(const Point& point) const;
+
+  // Returns a new set with the intersection of |*this| and |other|.
+  ResolutionSet Intersection(const ResolutionSet& other) const;
+
+  // Returns the closest point in this set to |point|. If |point| is included in
+  // this set, Point is returned. If this set is empty, behavior is undefined.
+  Point ClosestPointTo(const Point& point) const;
+
+  // Returns a point in this (nonempty) set closest to the ideal values for the
+  // height, width and aspectRatio constraints in |constraint_set|.
+  // Note that this function ignores all the other data in |constraint_set|.
+  // Only the ideal height, width and aspect ratio are used, and from now on
+  // referred to as |ideal_height|, |ideal_width| and |ideal_aspect_ratio|
+  // respectively.
+  //
+  // * If all three ideal values are given, |ideal_aspect_ratio| is ignored and
+  //   the point closest to (|ideal_height|, |ideal_width|) is returned.

[hbos_chromium, 2017/03/03 16:01:42]

It doesn't matter but it surprised/confused me at first: Why heigh-width
Cartesian space and not width-height?
If point (width,height) is replaced by vector (x,y) then it should be
width-height aka x-y space instead of y-x or else it would be confusing.

[Guido Urdaneta, 2017/03/06 11:08:23]

Because it is easier to think of aspectRatio as a line of the form
  width = aspectRatio * height, 
and have the min aspectRatio be the line below and the max aspectRatio the line
above in the Cartesian plane.

The difficulty of thinking of aspect ratio as the inverse of the slope of the
lines that make up the polygon is a lot worse than having height on the X axis. 
Also, although having width on the X axis sounds natural because that's how it
is on a screen, such a Cartesian plane would not really mimic a screen, but a
set of screen sizes.

[hbos_chromium, 2017/03/08 21:03:00]

Acknowledged.

If this at any point is replaced by a vector class (x,y) then you could
translate "width, height" to p = (height, width) and continue to use y =
aspectRatio * x for lines.

+  // * If two ideal values are given, they are used to determine a single ideal
+  //   point, which can be one of:
+  //    - (|ideal_height|, |ideal_width|),
+  //    - (|ideal_height|, |ideal_height|*|ideal_aspect_ratio|), or
+  //    - (|ideal_width| / |ideal_aspect_ratio|, |ideal_width|).
+  //   The point in the set closest to the ideal point is returned.
+  // * If a single ideal value is given, a point in the set closest to the line
+  //   defined by the ideal value is returned. If there is more than one point
+  //   closest to the ideal line, the following tie-breaker rules are used:
+  //  - If |ideal_height| is provided, the point closest to
+  //      (|ideal_height|, |ideal_height| * kDefaultAspectRatio).
+  //  - If |ideal_width| is provided, the point closest to
+  //      (|ideal_width| / kDefaultAspectRatio, |ideal_width|).
+  //  - If |ideal_aspect_ratio| is provided, the point with largest area among
+  //    the points closest to
+  //      (kDefaultHeight, kDefaultHeight * aspect_ratio) and
+  //      (kDefaultWidth / aspect_ratio, kDefaultWidth),
+  //    where aspect_ratio is |ideal_aspect_ratio| if the ideal line intersects
+  //    the set, and the closest aspect ratio to |ideal_aspect_ratio| among the
+  //    points in the set if no point in the set has an aspect ratio equal to
+  //    |ideal_aspect_ratio|.
+  // * If no ideal value is given, proceed as if only |ideal_aspect_ratio| was
+  //   provided with a value of kDefaultAspectRatio.
+  //
+  // This is intended to support the implementation of the spec algorithm for
+  // selection of track settings, as defined in
+  // https://w3c.github.io/mediacapture-main/#dfn-selectsettings.
+  //
+  // The main difference between this algorithm and the spec is that when ideal
+  // values are provided, the spec mandates finding a point that minimizes the
+  // sum of custom relative distances for each provided ideal value, while this
+  // algorithm minimizes either the Euclidean distance (sum of square distances)
+  // on a height-width plane for the cases where two or three ideal values are
+  // provided, or the absolute distance for the case with one ideal value.
+  // Also, in the case with three ideal values, this algorithm ignores the
+  // distance to the ideal aspect ratio.
+  // In most cases the difference in the final result should be negligible.
+  // The reason to follow this approach is that optimization in the worst case
+  // is reduced to projection of a point on line segment, which is a simple
+  // operation that provides exact results. Using the distance function of the
+  // spec, which is not continuous, would require complex optimization methods
+  // that do not necessarily guarantee finding the real optimal value.
+  //
+  // This function has undefined behavior if this set is empty.
+  Point SelectClosestPointToIdeal(
+      const blink::WebMediaTrackConstraintSet& constraint_set) const;
+
+  // Utilities that return ResolutionCandidateSets constrained on a specific

[hta - Chromium, 2017/03/03 11:02:36]

They return |ResolutionSet|s, not ResolutionCandidateSets. Leftover from rename?

[Guido Urdaneta, 2017/03/06 11:08:23]

Indeed a leftover. Done.

+  // variable.
+  static ResolutionSet FromHeight(int min, int max);
+  static ResolutionSet FromExactHeight(int value);
+  static ResolutionSet FromWidth(int min, int max);
+  static ResolutionSet FromExactWidth(int value);
+  static ResolutionSet FromAspectRatio(double min, double max);
+  static ResolutionSet FromExactAspectRatio(double value);
+
+  // Returns a ResolutionCandidateSet initialized with |constraint_set|'s
+  // width, height and aspectRatio constraints.
+  static ResolutionSet FromConstraintSet(
+      const blink::WebMediaTrackConstraintSet& constraint_set);
+
+ private:
+  FRIEND_TEST_ALL_PREFIXES(MediaStreamConstraintsUtilSetsTest,
+                           ResolutionVertices);
+
+  // Returns a list of the vertices defined by the constraints on a height-width
+  // Cartesian plane.
+  // If the list is empty, the set is empty.
+  // If the list contains a single point, the set contains a single point.
+  // If the list contains two points, the set is composed of points on a line
+  // segment.
+  // If the list contains three to six points, they are the vertices of a
+  // convex polygon containing all valid points in the set. Each pair of
+  // consecutive vertices (modulo the size of the list) corresponds to a side of
+  // the polygon, with the vertices given in counterclockwise order.
+  // The list cannot contain more than six points.
+  std::vector<Point> ComputeVertices() const;
+
+  // Adds |point| to |vertices| if |point| is included in this candidate set.
+  void TryAddVertex(std::vector<ResolutionSet::Point>* vertices,
+                    const ResolutionSet::Point& point) const;
+
+  // Returns the vertices of the set that have the property accessed
+  // by |accessor| closest to |value|. The returned vector always has one or two
+  // elements. Behavior is undefined if the set is empty.
+  std::vector<Point> GetClosestVertices(double (Point::*accessor)() const,
+                                        double value) const;
+
+  // Implements SelectClosestPointToIdeal() for the case when only the ideal
+  // aspect ratio is provided.
+  Point SelectClosestPointToIdealAspectRatio(double ideal_aspect_ratio) const;
+
+  int min_height_;
+  int max_height_;
+  int min_width_;
+  int max_width_;
+  double min_aspect_ratio_;
+  double max_aspect_ratio_;
+};
+
+// Scalar multiplication for Points.
+ResolutionSet::Point CONTENT_EXPORT operator*(double d,
+                                              const ResolutionSet::Point& p);
+
+}  // namespace content
+
+#endif  // CONTENT_RENDERER_MEDIA_MEDIA_STREAM_CONSTRAINTS_UTIL_SETS_H_