[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.

4 files changed, 193 insertions, 103 deletions

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;