[core] Collection-level immutability

Introduce a second level of immutability, over each of the collections held by a style: sources, images, and layers. Tracking immutability at this level allows us to short-circuit significant portions of the RenderStyle update logic via a simple equality check, greatly improving performance.

13 files changed, 254 insertions, 139 deletions

diff --git a/cmake/core-files.cmake b/cmake/core-files.cmake
index 47a5d16a1b..44e4f40f19 100644
--- a/cmake/core-files.cmake
+++ b/cmake/core-files.cmake
@@ -331,6 +331,7 @@ set(MBGL_CORE_FILES
     include/mbgl/style/transition_options.hpp
     include/mbgl/style/types.hpp
     include/mbgl/style/undefined.hpp
+    src/mbgl/style/collection.hpp
     src/mbgl/style/image.cpp
     src/mbgl/style/image_impl.cpp
     src/mbgl/style/image_impl.hpp
diff --git a/include/mbgl/style/image.hpp b/include/mbgl/style/image.hpp
index 55760ca503..ff3bfedf46 100644
--- a/include/mbgl/style/image.hpp
+++ b/include/mbgl/style/image.hpp
@@ -24,7 +24,7 @@ public:
     bool isSdf() const;
 
     class Impl;
-    Immutable<Impl> impl;
+    Immutable<Impl> baseImpl;
 };
 
 } // namespace style
diff --git a/include/mbgl/util/immutable.hpp b/include/mbgl/util/immutable.hpp
index 2cdce8772d..eb26c0d282 100644
--- a/include/mbgl/util/immutable.hpp
+++ b/include/mbgl/util/immutable.hpp
@@ -115,4 +115,19 @@ Immutable<S> staticImmutableCast(const Immutable<U>& u) {
     return Immutable<S>(std::static_pointer_cast<const S>(u.ptr));
 }
 
+/**
+ * Constrained mutation of an immutable reference. Makes a temporarily-mutable copy of the
+ * input Immutable using the inner type's copy constructor, runs the given callable on the
+ * mutable copy, and then freezes the copy and reassigns it to the input reference.
+ *
+ * Note that other Immutables referring to the same inner instance are not affected; they
+ * continue to referencing the original immutable instance.
+ */
+template <class T, class Fn>
+void mutate(Immutable<T>& immutable, Fn&& fn) {
+    Mutable<T> mut = makeMutable<T>(*immutable);
+    std::forward<Fn>(fn)(*mut);
+    immutable = std::move(mut);
+}
+
 } // namespace mbgl
diff --git a/src/mbgl/renderer/render_style.cpp b/src/mbgl/renderer/render_style.cpp
index a3a7d57527..dc49a20646 100644
--- a/src/mbgl/renderer/render_style.cpp
+++ b/src/mbgl/renderer/render_style.cpp
@@ -41,6 +41,9 @@ RenderStyle::RenderStyle(Scheduler& scheduler_, FileSource& fileSource_)
       glyphAtlas(std::make_unique<GlyphAtlas>(Size{ 2048, 2048 }, fileSource)),
       spriteAtlas(std::make_unique<SpriteAtlas>()),
       lineAtlas(std::make_unique<LineAtlas>(Size{ 256, 512 })),
+      imageImpls(makeMutable<std::vector<Immutable<style::Image::Impl>>>()),
+      sourceImpls(makeMutable<std::vector<Immutable<style::Source::Impl>>>()),
+      layerImpls(makeMutable<std::vector<Immutable<style::Layer::Impl>>>()),
       renderLight(makeMutable<Light::Impl>()),
       observer(&nullObserver) {
     glyphAtlas->setObserver(this);
@@ -55,7 +58,7 @@ void RenderStyle::setObserver(RenderStyleObserver* observer_) {
 std::vector<const RenderLayer*> RenderStyle::getRenderLayers() const {
     std::vector<const RenderLayer*> result;
     result.reserve(renderLayers.size());
-    for (const auto& layer : layerImpls) {
+    for (const auto& layer : *layerImpls) {
         result.push_back(getRenderLayer(layer->id));
     }
     return result;
@@ -189,12 +192,12 @@ void RenderStyle::update(const UpdateParameters& parameters) {
     }
 
     // Update all sources.
-    for (const auto& source : sourceImpls) {
+    for (const auto& source : *sourceImpls) {
         std::vector<Immutable<Layer::Impl>> filteredLayers;
         bool needsRendering = false;
         bool needsRelayout = false;
 
-        for (const auto& layer : layerImpls) {
+        for (const auto& layer : *layerImpls) {
             if (layer->type == LayerType::Background ||
                 layer->type == LayerType::Custom ||
                 layer->source != source->id) {
@@ -262,7 +265,7 @@ RenderData RenderStyle::getRenderData(MapDebugOptions debugOptions, float angle)
         }
     }
 
-    for (auto& layerImpl : layerImpls) {
+    for (auto& layerImpl : *layerImpls) {
         RenderLayer* layer = getRenderLayer(layerImpl->id);
         assert(layer);
 
@@ -277,7 +280,7 @@ RenderData RenderStyle::getRenderData(MapDebugOptions debugOptions, float angle)
                 continue;
             }
             const BackgroundPaintProperties::PossiblyEvaluated& paint = background->evaluated;
-            if (layerImpl.get() == layerImpls[0].get() && paint.get<BackgroundPattern>().from.empty()) {
+            if (layerImpl.get() == layerImpls->at(0).get() && paint.get<BackgroundPattern>().from.empty()) {
                 // This is a solid background. We can use glClear().
                 result.backgroundColor = paint.get<BackgroundColor>() * paint.get<BackgroundOpacity>();
             } else {
@@ -392,7 +395,7 @@ std::vector<Feature> RenderStyle::queryRenderedFeatures(const ScreenLineString&
     }
 
     // Combine all results based on the style layer order.
-    for (const auto& layerImpl : layerImpls) {
+    for (const auto& layerImpl : *layerImpls) {
         const RenderLayer* layer = getRenderLayer(layerImpl->id);
         if (!layer->needsRendering(zoomHistory.lastZoom)) {
             continue;
diff --git a/src/mbgl/renderer/render_style.hpp b/src/mbgl/renderer/render_style.hpp
index ff03b48fdf..ff222f2569 100644
--- a/src/mbgl/renderer/render_style.hpp
+++ b/src/mbgl/renderer/render_style.hpp
@@ -71,9 +71,9 @@ public:
     std::unique_ptr<LineAtlas> lineAtlas;
 
 private:
-    std::vector<Immutable<style::Image::Impl>> imageImpls;
-    std::vector<Immutable<style::Source::Impl>> sourceImpls;
-    std::vector<Immutable<style::Layer::Impl>> layerImpls;
+    Immutable<std::vector<Immutable<style::Image::Impl>>> imageImpls;
+    Immutable<std::vector<Immutable<style::Source::Impl>>> sourceImpls;
+    Immutable<std::vector<Immutable<style::Layer::Impl>>> layerImpls;
 
     std::unordered_map<std::string, std::unique_ptr<RenderSource>> renderSources;
     std::unordered_map<std::string, std::unique_ptr<RenderLayer>> renderLayers;
diff --git a/src/mbgl/renderer/style_diff.cpp b/src/mbgl/renderer/style_diff.cpp
index e250dfa8d5..cd547f2a0b 100644
--- a/src/mbgl/renderer/style_diff.cpp
+++ b/src/mbgl/renderer/style_diff.cpp
@@ -7,22 +7,28 @@
 namespace mbgl {
 
 template <class T, class Eq>
-StyleDifference<T> diff(const std::vector<T>& a, const std::vector<T>& b, const Eq& eq) {
+StyleDifference<T> diff(const Immutable<std::vector<T>>& a,
+                        const Immutable<std::vector<T>>& b,
+                        const Eq& eq) {
+    StyleDifference<T> result;
+
+    if (a == b) {
+        return result;
+    }
+
     std::vector<T> lcs;
 
-    longest_common_subsequence(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(lcs), eq);
+    longest_common_subsequence(a->begin(), a->end(), b->begin(), b->end(), std::back_inserter(lcs), eq);
 
-    auto aIt = a.begin();
-    auto bIt = b.begin();
+    auto aIt = a->begin();
+    auto bIt = b->begin();
     auto lIt = lcs.begin();
 
-    StyleDifference<T> result;
-
-    while (aIt != a.end() || bIt != b.end()) {
-        if (aIt != a.end() && (lIt == lcs.end() || !eq(*lIt, *aIt))) {
+    while (aIt != a->end() || bIt != b->end()) {
+        if (aIt != a->end() && (lIt == lcs.end() || !eq(*lIt, *aIt))) {
             result.removed.emplace((*aIt)->id, *aIt);
             aIt++;
-        } else if (bIt != b.end() && (lIt == lcs.end() || !eq(*lIt, *bIt))) {
+        } else if (bIt != b->end() && (lIt == lcs.end() || !eq(*lIt, *bIt))) {
             result.added.emplace((*bIt)->id, *bIt);
             bIt++;
         } else {
@@ -38,23 +44,23 @@ StyleDifference<T> diff(const std::vector<T>& a, const std::vector<T>& b, const
     return result;
 }
 
-ImageDifference diffImages(const std::vector<ImmutableImage>& a,
-                           const std::vector<ImmutableImage>& b) {
+ImageDifference diffImages(const Immutable<std::vector<ImmutableImage>>& a,
+                           const Immutable<std::vector<ImmutableImage>>& b) {
     return diff(a, b, [] (const ImmutableImage& lhs, const ImmutableImage& rhs) {
         return lhs->id == rhs->id;
     });
 }
 
-SourceDifference diffSources(const std::vector<ImmutableSource>& a,
-                             const std::vector<ImmutableSource>& b) {
+SourceDifference diffSources(const Immutable<std::vector<ImmutableSource>>& a,
+                             const Immutable<std::vector<ImmutableSource>>& b) {
     return diff(a, b, [] (const ImmutableSource& lhs, const ImmutableSource& rhs) {
         return std::tie(lhs->id, lhs->type)
             == std::tie(rhs->id, rhs->type);
     });
 }
 
-LayerDifference diffLayers(const std::vector<ImmutableLayer>& a,
-                           const std::vector<ImmutableLayer>& b) {
+LayerDifference diffLayers(const Immutable<std::vector<ImmutableLayer>>& a,
+                           const Immutable<std::vector<ImmutableLayer>>& b) {
     return diff(a, b, [] (const ImmutableLayer& lhs, const ImmutableLayer& rhs) {
         return std::tie(lhs->id, lhs->type)
             == std::tie(rhs->id, rhs->type);
diff --git a/src/mbgl/renderer/style_diff.hpp b/src/mbgl/renderer/style_diff.hpp
index 285d1e12ed..ef788c380c 100644
--- a/src/mbgl/renderer/style_diff.hpp
+++ b/src/mbgl/renderer/style_diff.hpp
@@ -21,20 +21,20 @@ public:
 using ImmutableImage = Immutable<style::Image::Impl>;
 using ImageDifference = StyleDifference<ImmutableImage>;
 
-ImageDifference diffImages(const std::vector<ImmutableImage>&,
-                           const std::vector<ImmutableImage>&);
+ImageDifference diffImages(const Immutable<std::vector<ImmutableImage>>&,
+                           const Immutable<std::vector<ImmutableImage>>&);
 
 using ImmutableSource = Immutable<style::Source::Impl>;
 using SourceDifference = StyleDifference<ImmutableSource>;
 
-SourceDifference diffSources(const std::vector<ImmutableSource>&,
-                             const std::vector<ImmutableSource>&);
+SourceDifference diffSources(const Immutable<std::vector<ImmutableSource>>&,
+                             const Immutable<std::vector<ImmutableSource>>&);
 
 using ImmutableLayer = Immutable<style::Layer::Impl>;
 using LayerDifference = StyleDifference<ImmutableLayer>;
 
-LayerDifference diffLayers(const std::vector<ImmutableLayer>&,
-                           const std::vector<ImmutableLayer>&);
+LayerDifference diffLayers(const Immutable<std::vector<ImmutableLayer>>&,
+                           const Immutable<std::vector<ImmutableLayer>>&);
 
 bool hasLayoutDifference(const LayerDifference&, const std::string& layerID);
 
diff --git a/src/mbgl/renderer/update_parameters.hpp b/src/mbgl/renderer/update_parameters.hpp
index e35ee80a10..7c44064b0b 100644
--- a/src/mbgl/renderer/update_parameters.hpp
+++ b/src/mbgl/renderer/update_parameters.hpp
@@ -22,9 +22,9 @@ public:
     const bool spriteLoaded;
     const style::TransitionOptions transitionOptions;
     const Immutable<style::Light::Impl> light;
-    const std::vector<Immutable<style::Image::Impl>> images;
-    const std::vector<Immutable<style::Source::Impl>> sources;
-    const std::vector<Immutable<style::Layer::Impl>> layers;
+    const Immutable<std::vector<Immutable<style::Image::Impl>>> images;
+    const Immutable<std::vector<Immutable<style::Source::Impl>>> sources;
+    const Immutable<std::vector<Immutable<style::Layer::Impl>>> layers;
 
     Scheduler& scheduler;
     FileSource& fileSource;
diff --git a/src/mbgl/style/collection.hpp b/src/mbgl/style/collection.hpp
new file mode 100644
index 0000000000..0deb1411b6
--- /dev/null
+++ b/src/mbgl/style/collection.hpp
@@ -0,0 +1,141 @@
+#pragma once
+
+#include <mbgl/util/immutable.hpp>
+#include <mbgl/util/optional.hpp>
+
+#include <memory>
+#include <string>
+
+namespace mbgl {
+namespace style {
+
+/*
+    Manages an ordered collection of elements and their `Immutable<Impl>`s. The latter is
+    itself stored in an Immutable container. Using immutability at the collection level
+    allows us to short-circuit significant portions of the RenderStyle update logic via
+    a simple pointer equality check, greatly improving performance.
+
+    Element types are required to have:
+
+      * An `Impl` inner class type
+      * An `Immutable<Impl> baseImpl` member
+      * A `std::string getID() const` method
+*/
+template <class T>
+class Collection {
+public:
+    using Impl = typename T::Impl;
+    using WrapperVector = std::vector<std::unique_ptr<T>>;
+    using ImmutableVector = Immutable<std::vector<Immutable<Impl>>>;
+
+    Collection();
+
+    std::size_t size() const;
+    T* get(const std::string&) const;
+
+    std::vector<T*> getWrappers() const;
+    ImmutableVector getImpls() const { return impls; }
+
+    auto begin() const { return wrappers.begin(); }
+    auto end() const { return wrappers.end(); }
+
+    void clear();
+
+    T* add(std::unique_ptr<T>, const optional<std::string>& = {});
+    std::unique_ptr<T> remove(const std::string&);
+
+    // Must be called whenever an element of the collection is internally mutated.
+    // Typically, each element permits registration of an observer, and the observer
+    // should call this method.
+    void update(const T&);
+
+private:
+    std::size_t index(const std::string&) const;
+
+    WrapperVector wrappers;
+    ImmutableVector impls;
+};
+
+template <class T>
+Collection<T>::Collection()
+    : impls(makeMutable<std::vector<Immutable<Impl>>>()) {
+}
+
+template <class T>
+std::size_t Collection<T>::size() const {
+    return wrappers.size();
+}
+
+template <class T>
+std::size_t Collection<T>::index(const std::string& id) const {
+    return std::find_if(wrappers.begin(), wrappers.end(), [&](const auto& e) {
+        return e->getID() == id;
+    }) - wrappers.begin();
+}
+
+template <class T>
+T* Collection<T>::get(const std::string& id) const {
+    std::size_t i = index(id);
+    return i < size() ? wrappers[i].get() : nullptr;
+}
+
+template <class T>
+std::vector<T*> Collection<T>::getWrappers() const {
+    std::vector<T*> result;
+    result.reserve(wrappers.size());
+
+    for (auto& wrapper : wrappers) {
+        result.push_back(wrapper.get());
+    }
+
+    return result;
+}
+
+template <class T>
+void Collection<T>::clear() {
+    mutate(impls, [&] (auto& impls_) {
+        impls_.clear();
+    });
+
+    wrappers.clear();
+}
+
+template <class T>
+T* Collection<T>::add(std::unique_ptr<T> wrapper, const optional<std::string>& before) {
+    std::size_t i = before ? index(*before) : size();
+
+    mutate(impls, [&] (auto& impls_) {
+        impls_.emplace(impls_.begin() + i, wrapper->baseImpl);
+    });
+
+    return wrappers.emplace(wrappers.begin() + i, std::move(wrapper))->get();
+}
+
+template <class T>
+std::unique_ptr<T> Collection<T>::remove(const std::string& id) {
+    std::size_t i = index(id);
+
+    if (i >= size()) {
+        return nullptr;
+    }
+
+    auto source = std::move(wrappers[i]);
+
+    mutate(impls, [&] (auto& impls_) {
+        impls_.erase(impls_.begin() + i);
+    });
+
+    wrappers.erase(wrappers.begin() + i);
+
+    return source;
+}
+
+template <class T>
+void Collection<T>::update(const T& wrapper) {
+    mutate(impls, [&] (auto& impls_) {
+        impls_.at(this->index(wrapper.getID())) = wrapper.baseImpl;
+    });
+}
+
+} // namespace style
+} // namespace mbgl
diff --git a/src/mbgl/style/image.cpp b/src/mbgl/style/image.cpp
index 6039c0458c..1747de5fcc 100644
--- a/src/mbgl/style/image.cpp
+++ b/src/mbgl/style/image.cpp
@@ -9,25 +9,25 @@ Image::Image(std::string id,
              PremultipliedImage &&image,
              const float pixelRatio,
              bool sdf)
-    : impl(makeMutable<Impl>(std::move(id), std::move(image), pixelRatio, sdf)) {
+    : baseImpl(makeMutable<Impl>(std::move(id), std::move(image), pixelRatio, sdf)) {
 }
 
 std::string Image::getID() const {
-    return impl->id;
+    return baseImpl->id;
 }
 
 Image::Image(const Image&) = default;
 
 const PremultipliedImage& Image::getImage() const {
-    return impl->image;
+    return baseImpl->image;
 }
 
 bool Image::isSdf() const {
-    return impl->sdf;
+    return baseImpl->sdf;
 }
 
 float Image::getPixelRatio() const {
-    return impl->pixelRatio;
+    return baseImpl->pixelRatio;
 }
 
 } // namespace style
diff --git a/src/mbgl/style/style.cpp b/src/mbgl/style/style.cpp
index 34e1cdeb6f..69a6d401ed 100644
--- a/src/mbgl/style/style.cpp
+++ b/src/mbgl/style/style.cpp
@@ -54,6 +54,8 @@ TransitionOptions Style::getTransitionOptions() const {
 void Style::setJSON(const std::string& json) {
     sources.clear();
     layers.clear();
+    images.clear();
+
     transitionOptions = {};
 
     Parser parser;
@@ -91,12 +93,7 @@ void Style::setJSON(const std::string& json) {
 }
 
 void Style::addSource(std::unique_ptr<Source> source) {
-    // Guard against duplicate source ids
-    auto it = std::find_if(sources.begin(), sources.end(), [&](const auto& existing) {
-        return existing->getID() == source->getID();
-    });
-
-    if (it != sources.end()) {
+    if (sources.get(source->getID())) {
         std::string msg = "Source " + source->getID() + " already exists";
         throw std::runtime_error(msg.c_str());
     }
@@ -104,7 +101,7 @@ void Style::addSource(std::unique_ptr<Source> source) {
     source->setObserver(this);
     source->loadDescription(fileSource);
 
-    sources.emplace_back(std::move(source));
+    sources.add(std::move(source));
 }
 
 struct SourceIdUsageEvaluator {
@@ -131,50 +128,27 @@ std::unique_ptr<Source> Style::removeSource(const std::string& id) {
         return nullptr;
     }
 
-    auto it = std::find_if(sources.begin(), sources.end(), [&](const auto& source) {
-        return source->getID() == id;
-    });
+    std::unique_ptr<Source> source = sources.remove(id);
 
-    if (it == sources.end()) {
-        return nullptr;
+    if (source) {
+        source->setObserver(nullptr);
     }
 
-    auto source = std::move(*it);
-    source->setObserver(nullptr);
-    sources.erase(it);
-
     return source;
 }
 
 std::vector<Layer*> Style::getLayers() {
-    std::vector<Layer*> result;
-    result.reserve(layers.size());
-    for (auto& layer : layers) {
-        result.push_back(layer.get());
-    }
-    return result;
-}
-
-std::vector<std::unique_ptr<Layer>>::const_iterator Style::findLayer(const std::string& id) const {
-    return std::find_if(layers.begin(), layers.end(), [&](const auto& layer) {
-        return layer->baseImpl->id == id;
-    });
+    return layers.getWrappers();
 }
 
 Layer* Style::getLayer(const std::string& id) const {
-    auto it = findLayer(id);
-    return it != layers.end() ? it->get() : nullptr;
+    return layers.get(id);
 }
 
 Layer* Style::addLayer(std::unique_ptr<Layer> layer, optional<std::string> before) {
     // TODO: verify source
 
-    // Guard against duplicate layer ids
-    auto it = std::find_if(layers.begin(), layers.end(), [&](const auto& existing) {
-        return existing->getID() == layer->getID();
-    });
-
-    if (it != layers.end()) {
+    if (layers.get(layer->getID())) {
         throw std::runtime_error(std::string{"Layer "} + layer->getID() + " already exists");
     }
 
@@ -184,25 +158,20 @@ Layer* Style::addLayer(std::unique_ptr<Layer> layer, optional<std::string> befor
 
     layer->setObserver(this);
 
-    return layers.emplace(before ? findLayer(*before) : layers.end(), std::move(layer))->get();
+    return layers.add(std::move(layer), before);
 }
 
 std::unique_ptr<Layer> Style::removeLayer(const std::string& id) {
-    auto it = std::find_if(layers.begin(), layers.end(), [&](const auto& layer) {
-        return layer->baseImpl->id == id;
-    });
-
-    if (it == layers.end())
-        return nullptr;
+    std::unique_ptr<Layer> layer = layers.remove(id);
 
-    auto layer = std::move(*it);
+    if (layer) {
+        layer->setObserver(nullptr);
 
-    if (auto* customLayer = layer->as<CustomLayer>()) {
-        customLayer->impl().deinitialize();
+        if (auto* customLayer = layer->as<CustomLayer>()) {
+            customLayer->impl().deinitialize();
+        }
     }
 
-    layer->setObserver(nullptr);
-    layers.erase(it);
     return layer;
 }
 
@@ -237,20 +206,11 @@ double Style::getDefaultPitch() const {
 }
 
 std::vector<Source*> Style::getSources() {
-    std::vector<Source*> result;
-    result.reserve(sources.size());
-    for (auto& source : sources) {
-        result.push_back(source.get());
-    }
-    return result;
+    return sources.getWrappers();
 }
 
 Source* Style::getSource(const std::string& id) const {
-    const auto it = std::find_if(sources.begin(), sources.end(), [&](const auto& source) {
-        return source->getID() == id;
-    });
-
-    return it != sources.end() ? it->get() : nullptr;
+    return sources.get(id);
 }
 
 bool Style::isLoaded() const {
@@ -272,22 +232,23 @@ bool Style::isLoaded() const {
 }
 
 void Style::addImage(std::unique_ptr<style::Image> image) {
-    std::string id = image->getID();
-    auto it = images.find(id);
-    if (it != images.end() && it->second->getImage().size != image->getImage().size) {
-        Log::Warning(Event::Sprite, "Can't change sprite dimensions for '%s'", id.c_str());
-        return;
+    if (style::Image* existing = images.get(image->getID())) {
+        if (existing->getImage().size != image->getImage().size) {
+            Log::Warning(Event::Sprite, "Can't change sprite dimensions for '%s'", image->getID().c_str());
+            return;
+        }
+        images.remove(image->getID());
     }
-    images[id] = std::move(image);
+
+    images.add(std::move(image));
 }
 
 void Style::removeImage(const std::string& id) {
-    images.erase(id);
+    images.remove(id);
 }
 
 const style::Image* Style::getImage(const std::string& id) const {
-    auto it = images.find(id);
-    return it == images.end() ? nullptr : it->second.get();
+    return images.get(id);
 }
 
 void Style::setObserver(style::Observer* observer_) {
@@ -295,11 +256,13 @@ void Style::setObserver(style::Observer* observer_) {
 }
 
 void Style::onSourceLoaded(Source& source) {
+    sources.update(source);
     observer->onSourceLoaded(source);
     observer->onUpdate(Update::Repaint);
 }
 
 void Style::onSourceChanged(Source& source) {
+    sources.update(source);
     observer->onSourceChanged(source);
 }
 
@@ -312,6 +275,7 @@ void Style::onSourceError(Source& source, std::exception_ptr error) {
 }
 
 void Style::onSourceDescriptionChanged(Source& source) {
+    sources.update(source);
     observer->onSourceDescriptionChanged(source);
     if (!source.loaded) {
         source.loadDescription(fileSource);
@@ -332,7 +296,8 @@ void Style::onSpriteError(std::exception_ptr error) {
     observer->onResourceError(error);
 }
 
-void Style::onLayerChanged(Layer&) {
+void Style::onLayerChanged(Layer& layer) {
+    layers.update(layer);
     observer->onUpdate(Update::Repaint);
 }
 
@@ -350,31 +315,16 @@ const std::string& Style::getGlyphURL() const {
     return glyphURL;
 }
 
-std::vector<Immutable<Image::Impl>> Style::getImageImpls() const {
-    std::vector<Immutable<style::Image::Impl>> result;
-    result.reserve(images.size());
-    for (const auto& image : images) {
-        result.push_back(image.second->impl);
-    }
-    return result;
+Immutable<std::vector<Immutable<Image::Impl>>> Style::getImageImpls() const {
+    return images.getImpls();
 }
 
-std::vector<Immutable<Source::Impl>> Style::getSourceImpls() const {
-    std::vector<Immutable<style::Source::Impl>> result;
-    result.reserve(sources.size());
-    for (const auto& source : sources) {
-        result.push_back(source->baseImpl);
-    }
-    return result;
+Immutable<std::vector<Immutable<Source::Impl>>> Style::getSourceImpls() const {
+    return sources.getImpls();
 }
 
-std::vector<Immutable<Layer::Impl>> Style::getLayerImpls() const {
-    std::vector<Immutable<style::Layer::Impl>> result;
-    result.reserve(layers.size());
-    for (const auto& layer : layers) {
-        result.push_back(layer->baseImpl);
-    }
-    return result;
+Immutable<std::vector<Immutable<Layer::Impl>>> Style::getLayerImpls() const {
+    return layers.getImpls();
 }
 
 } // namespace style
diff --git a/src/mbgl/style/style.hpp b/src/mbgl/style/style.hpp
index a60fee9264..7e8f6f640b 100644
--- a/src/mbgl/style/style.hpp
+++ b/src/mbgl/style/style.hpp
@@ -9,6 +9,7 @@
 #include <mbgl/style/image.hpp>
 #include <mbgl/style/source.hpp>
 #include <mbgl/style/layer.hpp>
+#include <mbgl/style/collection.hpp>
 
 #include <mbgl/util/noncopyable.hpp>
 #include <mbgl/util/optional.hpp>
@@ -75,9 +76,9 @@ public:
 
     const std::string& getGlyphURL() const;
 
-    std::vector<Immutable<Image::Impl>> getImageImpls() const;
-    std::vector<Immutable<Source::Impl>> getSourceImpls() const;
-    std::vector<Immutable<Layer::Impl>> getLayerImpls() const;
+    Immutable<std::vector<Immutable<Image::Impl>>> getImageImpls() const;
+    Immutable<std::vector<Immutable<Source::Impl>>> getSourceImpls() const;
+    Immutable<std::vector<Immutable<Layer::Impl>>> getLayerImpls() const;
 
     void dumpDebugLogs() const;
 
@@ -90,9 +91,9 @@ private:
     std::unique_ptr<SpriteLoader> spriteLoader;
     std::string glyphURL;
 
-    std::unordered_map<std::string, std::unique_ptr<style::Image>> images;
-    std::vector<std::unique_ptr<Source>> sources;
-    std::vector<std::unique_ptr<Layer>> layers;
+    Collection<style::Image> images;
+    Collection<Source> sources;
+    Collection<Layer> layers;
     TransitionOptions transitionOptions;
     std::unique_ptr<Light> light;
 
@@ -103,8 +104,6 @@ private:
     double defaultBearing = 0;
     double defaultPitch = 0;
 
-    std::vector<std::unique_ptr<Layer>>::const_iterator findLayer(const std::string& layerID) const;
-
     // SpriteLoaderObserver implementation.
     void onSpriteLoaded(std::vector<std::unique_ptr<Image>>&&) override;
     void onSpriteError(std::exception_ptr) override;
diff --git a/test/sprite/sprite_atlas.test.cpp b/test/sprite/sprite_atlas.test.cpp
index 3226f19c1b..78a5862475 100644
--- a/test/sprite/sprite_atlas.test.cpp
+++ b/test/sprite/sprite_atlas.test.cpp
@@ -23,7 +23,7 @@ TEST(SpriteAtlas, Basic) {
     auto images = parseSprite(util::read_file("test/fixtures/annotations/emerald.png"),
                               util::read_file("test/fixtures/annotations/emerald.json"));
     for (auto& image : images) {
-        atlas.addImage(image->impl);
+        atlas.addImage(image->baseImpl);
     }
 
     auto metro = *atlas.getIcon("metro");
@@ -63,7 +63,7 @@ TEST(SpriteAtlas, Size) {
     auto images = parseSprite(util::read_file("test/fixtures/annotations/emerald.png"),
                               util::read_file("test/fixtures/annotations/emerald.json"));
     for (auto& image : images) {
-        atlas.addImage(image->impl);
+        atlas.addImage(image->baseImpl);
     }
 
     auto metro = *atlas.getIcon("metro");