8 files changed, 298 insertions, 3 deletions

diff --git a/platform/darwin/src/MGLCluster.h b/platform/darwin/src/MGLCluster.h
new file mode 100644
index 0000000000..2b99119b26
--- /dev/null
+++ b/platform/darwin/src/MGLCluster.h
@@ -0,0 +1,53 @@
+#import "MGLFoundation.h"
+
+@protocol MGLFeature;
+
+NS_ASSUME_NONNULL_BEGIN
+
+/**
+ An `NSUInteger` constant used to indicate an invalid cluster identifier.
+ This indicates a missing cluster feature.
+ */
+FOUNDATION_EXTERN MGL_EXPORT const NSUInteger MGLClusterIdentifierInvalid;
+
+/**
+ A protocol that feature subclasses (i.e. those already conforming to
+ the `MGLFeature` protocol) conform to if they represent clusters.
+ 
+ Currently the only class that conforms to `MGLCluster` is
+ `MGLPointFeatureCluster` (a subclass of `MGLPointFeature`).
+ 
+ To check if a feature is a cluster, check conformity to `MGLCluster`, for
+ example:
+ 
+ ```swift
+ let shape = try! MGLShape(data: clusterShapeData, encoding: String.Encoding.utf8.rawValue)
+ 
+ guard let pointFeature = shape as? MGLPointFeature else {
+     throw ExampleError.unexpectedFeatureType
+ }
+ 
+ // Check for cluster conformance
+ guard let cluster = pointFeature as? MGLCluster else {
+     throw ExampleError.featureIsNotACluster
+ }
+ 
+ // Currently the only supported class that conforms to `MGLCluster` is
+ // `MGLPointFeatureCluster`
+ guard cluster is MGLPointFeatureCluster else {
+     throw ExampleError.unexpectedFeatureType
+ }
+ ```
+ */
+MGL_EXPORT
+@protocol MGLCluster <MGLFeature>
+
+/** The identifier for the cluster. */
+@property (nonatomic, readonly) NSUInteger clusterIdentifier;
+
+/** The number of points within this cluster */
+@property (nonatomic, readonly) NSUInteger clusterPointCount;
+
+@end
+
+NS_ASSUME_NONNULL_END
diff --git a/platform/darwin/src/MGLFeature.h b/platform/darwin/src/MGLFeature.h
index 8886c8df55..51901d73c0 100644
--- a/platform/darwin/src/MGLFeature.h
+++ b/platform/darwin/src/MGLFeature.h
@@ -6,6 +6,7 @@
 #import "MGLPointAnnotation.h"
 #import "MGLPointCollection.h"
 #import "MGLShapeCollection.h"
+#import "MGLCluster.h"
 
 NS_ASSUME_NONNULL_BEGIN
 
@@ -186,13 +187,28 @@ MGL_EXPORT
  #### Related examples
  See the <a href="https://www.mapbox.com/ios-sdk/maps/examples/runtime-multiple-annotations/">
  Dynamically style interactive points</a> example to learn how to initialize
- `MGLPointFeature` objects and add it them your map.
+ `MGLPointFeature` objects and add them to your map.
  */
 MGL_EXPORT
 @interface MGLPointFeature : MGLPointAnnotation <MGLFeature>
 @end
 
 /**
+ An `MGLPointFeatureCluster` object associates a point shape (with an optional
+ identifier and attributes) and represents a point cluster.
+ 
+ @see `MGLCluster`
+ 
+ #### Related examples
+ See the <a href="https://www.mapbox.com/ios-sdk/maps/examples/clustering/">
+ Clustering point data</a> example to learn how to initialize
+ clusters and add them to your map.
+ */
+MGL_EXPORT
+@interface MGLPointFeatureCluster : MGLPointFeature <MGLCluster>
+@end
+
+/**
  An `MGLPolylineFeature` object associates a polyline shape with an optional
  identifier and attributes.
 
diff --git a/platform/darwin/src/MGLFeature.mm b/platform/darwin/src/MGLFeature.mm
index d24c807625..fbf262af29 100644
--- a/platform/darwin/src/MGLFeature.mm
+++ b/platform/darwin/src/MGLFeature.mm
@@ -1,4 +1,6 @@
+#import "MGLFoundation_Private.h"
 #import "MGLFeature_Private.h"
+#import "MGLCluster.h"
 
 #import "MGLPointAnnotation.h"
 #import "MGLPolyline.h"
@@ -19,6 +21,11 @@
 #import <mbgl/style/conversion/geojson.hpp>
 #import <mapbox/feature.hpp>
 
+// Cluster constants
+static NSString * const MGLClusterIdentifierKey = @"cluster_id";
+static NSString * const MGLClusterCountKey = @"point_count";
+const NSUInteger MGLClusterIdentifierInvalid = NSUIntegerMax;
+
 @interface MGLEmptyFeature ()
 @end
 
@@ -92,6 +99,31 @@ MGL_DEFINE_FEATURE_ATTRIBUTES_GETTER();
 
 @end
 
+@implementation MGLPointFeatureCluster
+
+- (NSUInteger)clusterIdentifier {
+    NSNumber *clusterNumber = MGL_OBJC_DYNAMIC_CAST([self attributeForKey:MGLClusterIdentifierKey], NSNumber);
+    MGLAssert(clusterNumber, @"Clusters should have a cluster_id");
+    
+    if (!clusterNumber) {
+        return MGLClusterIdentifierInvalid;
+    }
+    
+    NSUInteger clusterIdentifier = [clusterNumber unsignedIntegerValue];
+    MGLAssert(clusterIdentifier <= UINT32_MAX, @"Cluster identifiers are 32bit");
+    
+    return clusterIdentifier;
+}
+
+- (NSUInteger)clusterPointCount {
+    NSNumber *count = MGL_OBJC_DYNAMIC_CAST([self attributeForKey:MGLClusterCountKey], NSNumber);
+    MGLAssert(count, @"Clusters should have a point_count");
+    
+    return [count unsignedIntegerValue];
+}
+@end
+
+
 @interface MGLPolylineFeature ()
 @end
 
@@ -318,14 +350,38 @@ MGL_DEFINE_FEATURE_ATTRIBUTES_GETTER();
  */
 template <typename T>
 class GeometryEvaluator {
+private:
+    const mbgl::PropertyMap *shared_properties;
+    
 public:
+    GeometryEvaluator(const mbgl::PropertyMap *properties = nullptr):
+        shared_properties(properties)
+    {}
+    
     MGLShape <MGLFeature> * operator()(const mbgl::EmptyGeometry &) const {
         MGLEmptyFeature *feature = [[MGLEmptyFeature alloc] init];
         return feature;
     }
 
     MGLShape <MGLFeature> * operator()(const mbgl::Point<T> &geometry) const {
-        MGLPointFeature *feature = [[MGLPointFeature alloc] init];
+        Class pointFeatureClass = [MGLPointFeature class];
+        
+        // If we're dealing with a cluster, we should change the class type.
+        // This could be generic and build the subclass at runtime if it turns
+        // out we need to support more than point clusters.
+        if (shared_properties) {
+            auto clusterIt = shared_properties->find("cluster");
+            if (clusterIt != shared_properties->end()) {
+                auto clusterValue = clusterIt->second;
+                if (clusterValue.template is<bool>()) {
+                    if (clusterValue.template get<bool>()) {
+                        pointFeatureClass = [MGLPointFeatureCluster class];
+                    }
+                }
+            }
+        }
+        
+        MGLPointFeature *feature = [[pointFeatureClass alloc] init];
         feature.coordinate = toLocationCoordinate2D(geometry);
         return feature;
     }
@@ -443,7 +499,7 @@ id <MGLFeature> MGLFeatureFromMBGLFeature(const mbgl::Feature &feature) {
         ValueEvaluator evaluator;
         attributes[@(pair.first.c_str())] = mbgl::Value::visit(value, evaluator);
     }
-    GeometryEvaluator<double> evaluator;
+    GeometryEvaluator<double> evaluator(&feature.properties);
     MGLShape <MGLFeature> *shape = mapbox::geometry::geometry<double>::visit(feature.geometry, evaluator);
     if (!feature.id.is<mapbox::feature::null_value_t>()) {
         shape.identifier = mbgl::FeatureIdentifier::visit(feature.id, ValueEvaluator());
diff --git a/platform/darwin/src/MGLFeature_Private.h b/platform/darwin/src/MGLFeature_Private.h
index 9fb1f91820..9b0e16f4b9 100644
--- a/platform/darwin/src/MGLFeature_Private.h
+++ b/platform/darwin/src/MGLFeature_Private.h
@@ -18,6 +18,7 @@ NSArray<MGLShape <MGLFeature> *> *MGLFeaturesFromMBGLFeatures(const std::vector<
 /**
  Returns an `MGLFeature` object converted from the given mbgl::Feature
  */
+MGL_EXPORT
 id <MGLFeature> MGLFeatureFromMBGLFeature(const mbgl::Feature &feature);
 
 /**
diff --git a/platform/darwin/src/MGLFoundation_Private.h b/platform/darwin/src/MGLFoundation_Private.h
index 71737c2cf9..db81bde3de 100644
--- a/platform/darwin/src/MGLFoundation_Private.h
+++ b/platform/darwin/src/MGLFoundation_Private.h
@@ -11,3 +11,9 @@ void MGLInitializeRunLoop();
         (type *)([temp##__LINE__ isKindOfClass:[type class]] ? temp##__LINE__ : nil); \
     })
 
+#define MGL_OBJC_DYNAMIC_CAST_AS_PROTOCOL(object, proto) \
+    ({ \
+        __typeof__( object ) temp##__LINE__ = (object); \
+        (id< proto >)([temp##__LINE__ conformsToProtocol:@protocol( proto )] ? temp##__LINE__ : nil); \
+    })
+
diff --git a/platform/darwin/src/MGLShapeSource.h b/platform/darwin/src/MGLShapeSource.h
index edf8c0a174..b910fb02ce 100644
--- a/platform/darwin/src/MGLShapeSource.h
+++ b/platform/darwin/src/MGLShapeSource.h
@@ -5,6 +5,8 @@
 NS_ASSUME_NONNULL_BEGIN
 
 @protocol MGLFeature;
+@class MGLPointFeature;
+@class MGLPointFeatureCluster;
 @class MGLShape;
 
 /**
@@ -321,6 +323,46 @@ MGL_EXPORT
  */
 - (NSArray<id <MGLFeature>> *)featuresMatchingPredicate:(nullable NSPredicate *)predicate;
 
+/**
+ Returns an array of map features that are the leaves of the specified cluster.
+ ("Leaves" are the original points that belong to the cluster.)
+ 
+ This method supports pagination; you supply an offset (number of features to skip)
+ and a maximum number of features to return.
+ 
+ @param cluster An object of type `MGLPointFeatureCluster` (that conforms to the `MGLCluster` protocol).
+ @param offset Number of features to skip.
+ @param limit The maximum number of features to return
+ 
+ @return An array of objects that conform to the `MGLFeature` protocol.
+ */
+- (NSArray<id <MGLFeature>> *)leavesOfCluster:(MGLPointFeatureCluster *)cluster offset:(NSUInteger)offset limit:(NSUInteger)limit;
+
+/**
+ Returns an array of map features that are the immediate children of the specified
+ cluster *on the next zoom level*. The may include features that also conform to
+ the `MGLCluster` protocol (currently only objects of type `MGLPointFeatureCluster`).
+ 
+ @param cluster An object of type `MGLPointFeatureCluster` (that conforms to the `MGLCluster` protocol).
+ 
+ @return An array of objects that conform to the `MGLFeature` protocol.
+ 
+ @note The returned array may contain the `cluster` that was passed in, if the next
+    zoom level doesn't match the zoom level for expanding that cluster. See
+    `-[MGLShapeSource zoomLevelForExpandingCluster:]`.
+ */
+- (NSArray<id<MGLFeature>> *)childrenOfCluster:(MGLPointFeatureCluster *)cluster;
+
+/**
+ Returns the zoom level at which the given cluster expands.
+ 
+ @param cluster An object of type `MGLPointFeatureCluster` (that conforms to the `MGLCluster` protocol).
+ 
+ @return Zoom level. This should be >= 0; any negative return value should be
+    considered an error.
+ */
+- (double)zoomLevelForExpandingCluster:(MGLPointFeatureCluster *)cluster;
+
 @end
 
 NS_ASSUME_NONNULL_END
diff --git a/platform/darwin/src/MGLShapeSource.mm b/platform/darwin/src/MGLShapeSource.mm
index c960f2a4a7..fc526f9850 100644
--- a/platform/darwin/src/MGLShapeSource.mm
+++ b/platform/darwin/src/MGLShapeSource.mm
@@ -1,10 +1,13 @@
+#import "MGLFoundation_Private.h"
 #import "MGLShapeSource_Private.h"
 
+#import "MGLLoggingConfiguration_Private.h"
 #import "MGLStyle_Private.h"
 #import "MGLMapView_Private.h"
 #import "MGLSource_Private.h"
 #import "MGLFeature_Private.h"
 #import "MGLShape_Private.h"
+#import "MGLCluster.h"
 
 #import "NSPredicate+MGLPrivateAdditions.h"
 #import "NSURL+MGLAdditions.h"
@@ -184,4 +187,106 @@ mbgl::style::GeoJSONOptions MGLGeoJSONOptionsFromDictionary(NSDictionary<MGLShap
     return MGLFeaturesFromMBGLFeatures(features);
 }
 
+#pragma mark - MGLCluster management
+
+- (mbgl::optional<mbgl::FeatureExtensionValue>)featureExtensionValueOfCluster:(MGLShape<MGLCluster> *)cluster extension:(std::string)extension options:(const std::map<std::string, mbgl::Value>)options {
+    mbgl::optional<mbgl::FeatureExtensionValue> extensionValue;
+    
+    // Check parameters
+    if (!self.rawSource || !self.mapView || !cluster) {
+        return extensionValue;
+    }
+
+    auto geoJSON = [cluster geoJSONObject];
+    
+    if (!geoJSON.is<mbgl::Feature>()) {
+        MGLAssert(0, @"cluster geoJSON object is not a feature.");
+        return extensionValue;
+    }
+    
+    auto clusterFeature = geoJSON.get<mbgl::Feature>();
+    
+    extensionValue = self.mapView.renderer->queryFeatureExtensions(self.rawSource->getID(),
+                                                                   clusterFeature,
+                                                                   "supercluster",
+                                                                   extension,
+                                                                   options);
+    return extensionValue;
+}
+
+- (NSArray<id <MGLFeature>> *)leavesOfCluster:(MGLPointFeatureCluster *)cluster offset:(NSUInteger)offset limit:(NSUInteger)limit {
+    const std::map<std::string, mbgl::Value> options = {
+        { "limit", static_cast<uint64_t>(limit) },
+        { "offset", static_cast<uint64_t>(offset) }
+    };
+
+    auto featureExtension = [self featureExtensionValueOfCluster:cluster extension:"leaves" options:options];
+
+    if (!featureExtension) {
+        return @[];
+    }
+    
+    if (!featureExtension->is<mbgl::FeatureCollection>()) {
+        return @[];
+    }
+    
+    std::vector<mbgl::Feature> leaves = featureExtension->get<mbgl::FeatureCollection>();
+    return MGLFeaturesFromMBGLFeatures(leaves);
+}
+
+- (NSArray<id <MGLFeature>> *)childrenOfCluster:(MGLPointFeatureCluster *)cluster {
+    auto featureExtension = [self featureExtensionValueOfCluster:cluster extension:"children" options:{}];
+    
+    if (!featureExtension) {
+        return @[];
+    }
+    
+    if (!featureExtension->is<mbgl::FeatureCollection>()) {
+        return @[];
+    }
+    
+    std::vector<mbgl::Feature> leaves = featureExtension->get<mbgl::FeatureCollection>();
+    return MGLFeaturesFromMBGLFeatures(leaves);
+}
+
+- (double)zoomLevelForExpandingCluster:(MGLPointFeatureCluster *)cluster {
+    auto featureExtension = [self featureExtensionValueOfCluster:cluster extension:"expansion-zoom" options:{}];
+
+    if (!featureExtension) {
+        return -1.0;
+    }
+    
+    if (!featureExtension->is<mbgl::Value>()) {
+        return -1.0;
+    }
+    
+    auto value = featureExtension->get<mbgl::Value>();
+    if (value.is<uint64_t>()) {
+        auto zoom = value.get<uint64_t>();
+        return static_cast<double>(zoom);
+    }
+    
+    return -1.0;
+}
+
+- (void)debugRecursiveLogForFeature:(id <MGLFeature>)feature indent:(NSUInteger)indent {
+    NSString *description = feature.description;
+    
+    // Want our recursive log on a single line
+    NSString *log = [description stringByReplacingOccurrencesOfString:@"\\s+"
+                                                           withString:@" "
+                                                              options:NSRegularExpressionSearch
+                                                                range:NSMakeRange(0, description.length)];
+    
+    printf("%*s%s\n", (int)indent, "", log.UTF8String);
+    
+    MGLPointFeatureCluster *cluster = MGL_OBJC_DYNAMIC_CAST(feature, MGLPointFeatureCluster);
+    
+    if (cluster) {
+        for (id <MGLFeature> child in [self childrenOfCluster:cluster]) {
+            [self debugRecursiveLogForFeature:child indent:indent + 4];
+        }
+    }
+}
+
 @end
diff --git a/platform/darwin/src/MGLShapeSource_Private.h b/platform/darwin/src/MGLShapeSource_Private.h
index fb5b3b3c0d..c7eaf3d0a8 100644
--- a/platform/darwin/src/MGLShapeSource_Private.h
+++ b/platform/darwin/src/MGLShapeSource_Private.h
@@ -12,4 +12,20 @@ namespace mbgl {
 MGL_EXPORT
 mbgl::style::GeoJSONOptions MGLGeoJSONOptionsFromDictionary(NSDictionary<MGLShapeSourceOption, id> *options);
 
+@interface MGLShapeSource (Private)
+
+/**
+ :nodoc:
+ Debug log showing structure of an `MGLFeature`. This method recurses in the case
+ that the feature conforms to `MGLCluster`. This method is used for testing and
+ should be considered experimental, likely to be removed or changed in future
+ releases.
+ 
+ @param feature An object that conforms to the `MGLFeature` protocol.
+ @param indent Used during recursion. Specify 0.
+ */
+
+- (void)debugRecursiveLogForFeature:(id<MGLFeature>)feature indent:(NSUInteger)indent;
+@end
+
 NS_ASSUME_NONNULL_END