Make install() de-duplication and component replacements work across NormalizedComponent+Component.

7 files changed, 402 insertions, 490 deletions

diff --git a/include/fruit/component.h b/include/fruit/component.h
index d290d0b..1bb1c36 100644
--- a/include/fruit/component.h
+++ b/include/fruit/component.h
@@ -649,10 +649,6 @@ public:
    * In the example above, if getFooComponent didn't install getDependencyComponent, when a test creates an
    * injector for getBarComponentWithFakeDependency it would not install getFakeDependencyComponent.
    *
-   * Unlike bindings, when creating an injector from a NormalizedComponent and a Component the replacements in the
-   * NormalizedComponent do *not* affect the install()s in the Component and vice versa.
-   * If you want a replacement to apply to both, you should add it in both.
-   *
    * Replacements can also be chained, for example:
    *
    * fruit::Component<...> getRootComponent() {
diff --git a/include/fruit/impl/normalized_component_storage/binding_normalization.h b/include/fruit/impl/normalized_component_storage/binding_normalization.h
index ecb62cf..38b05b7 100644
--- a/include/fruit/impl/normalized_component_storage/binding_normalization.h
+++ b/include/fruit/impl/normalized_component_storage/binding_normalization.h
@@ -45,6 +45,15 @@ public:
   using BindingCompressionInfoMap =
       HashMapWithArenaAllocator<TypeId, NormalizedComponentStorage::CompressedBindingUndoInfo>;
 
+  using LazyComponentWithNoArgs = ComponentStorageEntry::LazyComponentWithNoArgs;
+  using LazyComponentWithArgs = ComponentStorageEntry::LazyComponentWithArgs;
+
+  using LazyComponentWithNoArgsSet = NormalizedComponentStorage::LazyComponentWithNoArgsSet;
+  using LazyComponentWithArgsSet = NormalizedComponentStorage::LazyComponentWithArgsSet;
+
+  using LazyComponentWithNoArgsReplacementMap = NormalizedComponentStorage::LazyComponentWithNoArgsReplacementMap;
+  using LazyComponentWithArgsReplacementMap = NormalizedComponentStorage::LazyComponentWithArgsReplacementMap;
+
   /**
    * Normalizes the toplevel entries and performs binding compression.
    * This does *not* keep track of what binding compressions were performed, so they can't be undone. When we might need
@@ -67,47 +76,24 @@ public:
       FixedSizeVector<ComponentStorageEntry>&& toplevel_entries,
       FixedSizeAllocator::FixedSizeAllocatorData& fixed_size_allocator_data,
       MemoryPool& memory_pool,
+      MemoryPool& memory_pool_for_fully_expanded_components_maps,
+      MemoryPool& memory_pool_for_component_replacements_maps,
       const std::vector<TypeId, ArenaAllocator<TypeId>>& exposed_types,
       std::vector<ComponentStorageEntry, ArenaAllocator<ComponentStorageEntry>>& bindings_vector,
       std::unordered_map<TypeId, NormalizedMultibindingSet>& multibindings,
-      BindingCompressionInfoMap& bindingCompressionInfoMap);
+      BindingCompressionInfoMap& bindingCompressionInfoMap,
+      LazyComponentWithNoArgsSet& fully_expanded_components_with_no_args,
+      LazyComponentWithArgsSet& fully_expanded_components_with_args,
+      LazyComponentWithNoArgsReplacementMap& component_with_no_args_replacements,
+      LazyComponentWithArgsReplacementMap& component_with_args_replacements);
 
-  /**
-   * - FindNormalizedBinding should have a
-   *   NormalizedBindingItr operator()(TypeId)
-   *   that returns a NormalizedBindingItr describing whether the binding is present in a base component (if any).
-   * - IsValidItr should have a
-   *   bool operator()(NormalizedBindingItr)
-   * - IsNormalizedBindingItrForConstructedObject should have a
-   *   bool operator()(NormalizedBindingItr)
-   *   (that can only be used when IsValidItr returns true)
-   * - GetObjectPtr should have a
-   *   ComponentStorageEntry::BindingForConstructedObject::object_ptr_t operator()(NormalizedBindingItr)
-   *   (that can only be used when IsNormalizedBindingItrForConstructedObject returns true)
-   * - GetCreate should have a
-   *   ComponentStorageEntry::BindingForObjectToConstruct::create_t operator()(NormalizedBindingItr)
-   *   (that can only be used when IsNormalizedBindingItrForConstructedObject returns false).
-   */
-  template <
-      typename FindNormalizedBinding,
-      typename IsValidItr,
-      typename IsNormalizedBindingItrForConstructedObject,
-      typename GetObjectPtr,
-      typename GetCreate>
   static void normalizeBindingsAndAddTo(
       FixedSizeVector<ComponentStorageEntry>&& toplevel_entries,
       MemoryPool& memory_pool,
-      const FixedSizeAllocator::FixedSizeAllocatorData& base_fixed_size_allocator_data,
-      const std::unordered_map<TypeId, NormalizedMultibindingSet>& base_multibindings,
-      const NormalizedComponentStorage::BindingCompressionInfoMap& base_binding_compression_info_map,
+      const NormalizedComponentStorage& base_normalized_component,
       FixedSizeAllocator::FixedSizeAllocatorData& fixed_size_allocator_data,
       std::vector<ComponentStorageEntry, ArenaAllocator<ComponentStorageEntry>>& new_bindings_vector,
-      std::unordered_map<TypeId, NormalizedMultibindingSet>& multibindings,
-      FindNormalizedBinding find_normalized_binding,
-      IsValidItr is_valid_itr,
-      IsNormalizedBindingItrForConstructedObject is_normalized_binding_itr_for_constructed_object,
-      GetObjectPtr get_object_ptr,
-      GetCreate get_create);
+      std::unordered_map<TypeId, NormalizedMultibindingSet>& multibindings);
 
 private:
 
@@ -129,46 +115,16 @@ private:
 
   /**
    * Normalizes the toplevel entries (but doesn't perform binding compression).
-   * - HandleCompressedBinding should have an operator()(ComponentStorageEntry&) that will be called for each
-   *   COMPRESSED_BINDING entry.
-   * - HandleMultibinding should have an
-   *   operator()(ComponentStorageEntry& multibinding_entry, ComponentStorageEntry& multibinding_vector_creator_entry)
-   *   that will be called for each multibinding entry.
-   * - FindNormalizedBinding should have a
-   *   NormalizedBindingItr operator()(TypeId)
-   *   that returns a NormalizedBindingItr describing whether the binding is present in a base component (if any).
-   * - IsValidItr should have a
-   *   bool operator()(NormalizedBindingItr)
-   * - IsNormalizedBindingItrForConstructedObject should have a
-   *   bool operator()(NormalizedBindingItr)
-   *   (that can only be used when IsValidItr returns true)
-   * - GetObjectPtr should have a
-   *   ComponentStorageEntry::BindingForConstructedObject::object_ptr_t operator()(NormalizedBindingItr)
-   *   (that can only be used when IsNormalizedBindingItrForConstructedObject returns true)
-   * - GetCreate should have a
-   *   ComponentStorageEntry::BindingForObjectToConstruct::create_t operator()(NormalizedBindingItr)
-   *   (that can only be used when IsNormalizedBindingItrForConstructedObject returns false).
    */
-  template <
-      typename HandleCompressedBinding,
-      typename HandleMultibinding,
-      typename FindNormalizedBinding,
-      typename IsValidItr,
-      typename IsNormalizedBindingItrForConstructedObject,
-      typename GetObjectPtr,
-      typename GetCreate>
+  template <typename... Functors>
   static void normalizeBindings(
       FixedSizeVector<ComponentStorageEntry>&& toplevel_entries,
       FixedSizeAllocator::FixedSizeAllocatorData& fixed_size_allocator_data,
       MemoryPool& memory_pool,
+      MemoryPool& memory_pool_for_fully_expanded_components_maps,
+      MemoryPool& memory_pool_for_component_replacements_maps,
       HashMapWithArenaAllocator<TypeId, ComponentStorageEntry>& binding_data_map,
-      HandleCompressedBinding handle_compressed_binding,
-      HandleMultibinding handle_multibinding,
-      FindNormalizedBinding find_normalized_binding,
-      IsValidItr is_valid_itr,
-      IsNormalizedBindingItrForConstructedObject is_normalized_binding_itr_for_constructed_object,
-      GetObjectPtr get_object_ptr,
-      GetCreate get_create);
+      Functors... functors);
 
   struct BindingCompressionInfo {
     TypeId i_type_id;
@@ -181,15 +137,26 @@ private:
    *   with (c_type_id, undo_info) for each binding compression that was applied (and that therefore might need to be
    *   undone later).
    */
-  template <typename SaveCompressedBindingUndoInfo>
+  template <
+      typename SaveCompressedBindingUndoInfo,
+      typename SaveFullyExpandedComponentsWithNoArgs,
+      typename SaveFullyExpandedComponentsWithArgs,
+      typename SaveComponentReplacementsWithNoArgs,
+      typename SaveComponentReplacementsWithArgs>
   static void normalizeBindingsWithBindingCompression(
       FixedSizeVector<ComponentStorageEntry>&& toplevel_entries,
       FixedSizeAllocator::FixedSizeAllocatorData& fixed_size_allocator_data,
       MemoryPool& memory_pool,
+      MemoryPool& memory_pool_for_fully_expanded_components_maps,
+      MemoryPool& memory_pool_for_component_replacements_maps,
       const std::vector<TypeId, ArenaAllocator<TypeId>>& exposed_types,
       std::vector<ComponentStorageEntry, ArenaAllocator<ComponentStorageEntry>>& bindings_vector,
       std::unordered_map<TypeId, NormalizedMultibindingSet>& multibindings,
-      SaveCompressedBindingUndoInfo save_compressed_binding_undo_info);
+      SaveCompressedBindingUndoInfo save_compressed_binding_undo_info,
+      SaveFullyExpandedComponentsWithNoArgs save_fully_expanded_components_with_no_args,
+      SaveFullyExpandedComponentsWithArgs save_fully_expanded_components_with_args,
+      SaveComponentReplacementsWithNoArgs save_component_replacements_with_no_args,
+      SaveComponentReplacementsWithArgs save_component_replacements_with_args);
 
   /**
    * bindingCompressionInfoMap is an output parameter. This function will store information on all performed binding
@@ -208,47 +175,16 @@ private:
       const std::vector<TypeId, ArenaAllocator<TypeId>>& exposed_types,
       SaveCompressedBindingUndoInfo save_compressed_binding_undo_info);
 
-  using LazyComponentWithNoArgs = ComponentStorageEntry::LazyComponentWithNoArgs;
-  using LazyComponentWithArgs = ComponentStorageEntry::LazyComponentWithArgs;
-
-  struct HashLazyComponentWithNoArgs {
-    std::size_t operator()(const LazyComponentWithNoArgs& x) const {
-      return x.hashCode();
-    }
-  };
-
-  struct LazyComponentWithArgsEqualTo {
-    bool operator()(const LazyComponentWithArgs& x, const LazyComponentWithArgs& y) const {
-      return *x.component == *y.component;
-    }
-  };
-
-  struct HashLazyComponentWithArgs {
-    std::size_t operator()(const LazyComponentWithArgs& x) const {
-      return x.component->hashCode();
-    }
-  };
-
-  using LazyComponentWithNoArgsSet =
-      HashSetWithArenaAllocator<LazyComponentWithNoArgs, HashLazyComponentWithNoArgs, std::equal_to<LazyComponentWithNoArgs>>;
-  using LazyComponentWithArgsSet =
-      HashSetWithArenaAllocator<LazyComponentWithArgs, HashLazyComponentWithArgs, LazyComponentWithArgsEqualTo>;
+  static void handlePreexistingLazyComponentWithArgsReplacement(
+      ComponentStorageEntry& replaced_component_entry,
+      const ComponentStorageEntry& preexisting_replacement,
+      ComponentStorageEntry& new_replacement);
 
-  static LazyComponentWithNoArgsSet createLazyComponentWithNoArgsSet(MemoryPool& memory_pool);
-  static LazyComponentWithArgsSet createLazyComponentWithArgsSet(MemoryPool& memory_pool);
+  static void handlePreexistingLazyComponentWithNoArgsReplacement(
+      ComponentStorageEntry& replaced_component_entry,
+      const ComponentStorageEntry& preexisting_replacement,
+      ComponentStorageEntry& new_replacement);
 
-  using LazyComponentWithNoArgsReplacementMap =
-      HashMapWithArenaAllocator<LazyComponentWithNoArgs, ComponentStorageEntry, HashLazyComponentWithNoArgs, std::equal_to<LazyComponentWithNoArgs>>;
-  using LazyComponentWithArgsReplacementMap =
-      HashMapWithArenaAllocator<LazyComponentWithArgs, ComponentStorageEntry, HashLazyComponentWithArgs, LazyComponentWithArgsEqualTo>;
-
-  static LazyComponentWithNoArgsReplacementMap createLazyComponentWithNoArgsReplacementMap(MemoryPool& memory_pool);
-  static LazyComponentWithArgsReplacementMap createLazyComponentWithArgsReplacementMap(MemoryPool& memory_pool);
-
-  /**
-   * This struct groups all data structures available during binding normalization, to avoid mentioning them in all
-   * handle*Binding functions below.
-   */
   template <
       typename HandleCompressedBinding,
       typename HandleMultibinding,
@@ -256,53 +192,143 @@ private:
       typename IsValidItr,
       typename IsNormalizedBindingItrForConstructedObject,
       typename GetObjectPtr,
-      typename GetCreate>
-  struct BindingNormalizationContext {
-    FixedSizeAllocator::FixedSizeAllocatorData& fixed_size_allocator_data;
-    MemoryPool& memory_pool;
-    HashMapWithArenaAllocator<TypeId, ComponentStorageEntry>& binding_data_map;
+      typename GetCreate,
+      typename IsComponentWithNoArgsAlreadyExpandedInNormalizedComponent,
+      typename IsComponentWithArgsAlreadyExpandedInNormalizedComponent,
+      typename SaveFullyExpandedComponentsWithNoArgs,
+      typename SaveFullyExpandedComponentsWithArgs,
+      typename GetComponentWithNoArgsReplacementInNormalizedComponent,
+      typename GetComponentWithArgsReplacementInNormalizedComponent,
+      typename IsLazyComponentWithNoArgsIteratorValid,
+      typename IsLazyComponentWithArgsIteratorValid,
+      typename DereferenceLazyComponentWithNoArgsIterator,
+      typename DereferenceLazyComponentWithArgsIterator,
+      typename SaveComponentReplacementsWithNoArgs,
+      typename SaveComponentReplacementsWithArgs>
+  struct BindingNormalizationFunctors {
+
+    /**
+     * This should have an operator()(ComponentStorageEntry&) that will be called for each COMPRESSED_BINDING entry.
+     */
     HandleCompressedBinding handle_compressed_binding;
+
+    /**
+     * This should have an
+     * operator()(ComponentStorageEntry& multibinding_entry, ComponentStorageEntry& multibinding_vector_creator_entry)
+     * that will be called for each multibinding entry.
+     */
     HandleMultibinding handle_multibinding;
+
+    /**
+     * This should have a
+     * NormalizedBindingItr operator()(TypeId)
+     * that returns a NormalizedBindingItr describing whether the binding is present in a base component (if any).
+     */
     FindNormalizedBinding find_normalized_binding;
+
+    /**
+     * This should have a
+     * bool operator()(NormalizedBindingItr)
+     */
     IsValidItr is_valid_itr;
+
+    /**
+     * This should have a
+     * bool operator()(NormalizedBindingItr)
+     * (that can only be used when IsValidItr returns true).
+     */
     IsNormalizedBindingItrForConstructedObject is_normalized_binding_itr_for_constructed_object;
+
+    /**
+     * This should have a
+     * ComponentStorageEntry::BindingForConstructedObject::object_ptr_t operator()(NormalizedBindingItr)
+     * (that can only be used when IsNormalizedBindingItrForConstructedObject returns true).
+     */
     GetObjectPtr get_object_ptr;
+
+    /**
+     * This should have a
+     * ComponentStorageEntry::BindingForObjectToConstruct::create_t operator()(NormalizedBindingItr)
+     * (that can only be used when IsNormalizedBindingItrForConstructedObject returns false).
+     */
     GetCreate get_create;
 
+    IsComponentWithNoArgsAlreadyExpandedInNormalizedComponent is_component_with_no_args_already_expanded_in_normalized_component;
+    IsComponentWithArgsAlreadyExpandedInNormalizedComponent is_component_with_args_already_expanded_in_normalized_component;
+    SaveFullyExpandedComponentsWithNoArgs save_fully_expanded_components_with_no_args;
+    SaveFullyExpandedComponentsWithArgs save_fully_expanded_components_with_args;
+
+    /**
+     * Gets a LazyComponentWithNoArgsIterator pointing to the replacement for the given lazy component in the normalized
+     * component (if any).
+     */
+    GetComponentWithNoArgsReplacementInNormalizedComponent get_component_with_no_args_replacement_in_normalized_component;
+
+    /**
+     * Gets a LazyComponentWithArgsIterator pointing to the replacement for the given lazy component in the normalized
+     * component (if any).
+     */
+    GetComponentWithArgsReplacementInNormalizedComponent get_component_with_args_replacement_in_normalized_component;
+
+    IsLazyComponentWithNoArgsIteratorValid is_lazy_component_with_no_args_iterator_valid;
+    IsLazyComponentWithArgsIteratorValid is_lazy_component_with_args_iterator_valid;
+
+    DereferenceLazyComponentWithNoArgsIterator dereference_lazy_component_with_no_args_iterator;
+    DereferenceLazyComponentWithArgsIterator dereference_lazy_component_with_args_iterator;
+
+    SaveComponentReplacementsWithNoArgs save_component_replacements_with_no_args;
+    SaveComponentReplacementsWithArgs save_component_replacements_with_args;
+  };
+
+  /**
+   * This struct groups all data structures available during binding normalization, to avoid mentioning them in all
+   * handle*Binding functions below.
+   */
+  template <typename... Functors>
+  struct BindingNormalizationContext {
+    FixedSizeAllocator::FixedSizeAllocatorData& fixed_size_allocator_data;
+    MemoryPool& memory_pool;
+    MemoryPool& memory_pool_for_fully_expanded_components_maps;
+    MemoryPool& memory_pool_for_component_replacements_maps;
+    HashMapWithArenaAllocator<TypeId, ComponentStorageEntry>& binding_data_map;
+    BindingNormalizationFunctors<Functors...> functors;
+
     // These are in reversed order (note that toplevel_entries must also be in reverse order).
     std::vector<ComponentStorageEntry, ArenaAllocator<ComponentStorageEntry>> entries_to_process;
 
     // These sets contain the lazy components whose expansion has already completed.
     LazyComponentWithNoArgsSet fully_expanded_components_with_no_args =
-        createLazyComponentWithNoArgsSet(memory_pool);
+        NormalizedComponentStorage::createLazyComponentWithNoArgsSet(
+            20 /* capacity */, memory_pool_for_fully_expanded_components_maps);
     LazyComponentWithArgsSet fully_expanded_components_with_args =
-        createLazyComponentWithArgsSet(memory_pool);
+        NormalizedComponentStorage::createLazyComponentWithArgsSet(
+            20 /* capacity */, memory_pool_for_fully_expanded_components_maps);
 
     // These sets contain the elements with kind *_END_MARKER in entries_to_process.
     // For component with args, these sets do *not* own the objects, entries_to_process does.
     LazyComponentWithNoArgsSet components_with_no_args_with_expansion_in_progress =
-        createLazyComponentWithNoArgsSet(memory_pool);
+        NormalizedComponentStorage::createLazyComponentWithNoArgsSet(
+            20 /* capacity */, memory_pool);
     LazyComponentWithArgsSet components_with_args_with_expansion_in_progress =
-        createLazyComponentWithArgsSet(memory_pool);
+        NormalizedComponentStorage::createLazyComponentWithArgsSet(
+            20 /* capacity */, memory_pool);
 
     // These sets contain Component replacements, as mappings componentToReplace->replacementComponent.
     LazyComponentWithNoArgsReplacementMap component_with_no_args_replacements =
-        createLazyComponentWithNoArgsReplacementMap(memory_pool);
+        NormalizedComponentStorage::createLazyComponentWithNoArgsReplacementMap(
+            20 /* capacity */, memory_pool_for_component_replacements_maps);
     LazyComponentWithArgsReplacementMap component_with_args_replacements =
-        createLazyComponentWithArgsReplacementMap(memory_pool);
+        NormalizedComponentStorage::createLazyComponentWithArgsReplacementMap(
+            20 /* capacity */, memory_pool_for_component_replacements_maps);
 
     BindingNormalizationContext(
         FixedSizeVector<ComponentStorageEntry>& toplevel_entries,
         FixedSizeAllocator::FixedSizeAllocatorData& fixed_size_allocator_data,
         MemoryPool& memory_pool,
+        MemoryPool& memory_pool_for_fully_expanded_components_maps,
+        MemoryPool& memory_pool_for_component_replacements_maps,
         HashMapWithArenaAllocator<TypeId, ComponentStorageEntry>& binding_data_map,
-        HandleCompressedBinding handle_compressed_binding,
-        HandleMultibinding handle_multibinding,
-        FindNormalizedBinding find_normalized_binding,
-        IsValidItr is_valid_itr,
-        IsNormalizedBindingItrForConstructedObject is_normalized_binding_itr_for_constructed_object,
-        GetObjectPtr get_object_ptr,
-        GetCreate get_create);
+        BindingNormalizationFunctors<Functors...> functors);
 
     BindingNormalizationContext(const BindingNormalizationContext&) = delete;
     BindingNormalizationContext(BindingNormalizationContext&&) = delete;
diff --git a/include/fruit/impl/normalized_component_storage/binding_normalization.templates.h b/include/fruit/impl/normalized_component_storage/binding_normalization.templates.h
index 920be84..3111e13 100644
--- a/include/fruit/impl/normalized_component_storage/binding_normalization.templates.h
+++ b/include/fruit/impl/normalized_component_storage/binding_normalization.templates.h
@@ -31,65 +31,29 @@ using namespace fruit::impl;
 namespace fruit {
 namespace impl {
 
-template <
-    typename HandleCompressedBinding,
-    typename HandleMultibinding,
-    typename FindNormalizedBinding,
-    typename IsValidItr,
-    typename IsNormalizedBindingItrForConstructedObject,
-    typename GetObjectPtr,
-    typename GetCreate>
-BindingNormalization::BindingNormalizationContext<
-      HandleCompressedBinding,
-      HandleMultibinding,
-      FindNormalizedBinding,
-      IsValidItr,
-      IsNormalizedBindingItrForConstructedObject,
-      GetObjectPtr,
-      GetCreate>::BindingNormalizationContext(
+template <typename... Functors>
+BindingNormalization::BindingNormalizationContext<Functors...>::BindingNormalizationContext(
     FixedSizeVector<ComponentStorageEntry>& toplevel_entries,
     FixedSizeAllocator::FixedSizeAllocatorData& fixed_size_allocator_data,
     MemoryPool& memory_pool,
+    MemoryPool& memory_pool_for_fully_expanded_components_maps,
+    MemoryPool& memory_pool_for_component_replacements_maps,
     HashMapWithArenaAllocator<TypeId, ComponentStorageEntry>& binding_data_map,
-    HandleCompressedBinding handle_compressed_binding,
-    HandleMultibinding handle_multibinding,
-    FindNormalizedBinding find_normalized_binding,
-    IsValidItr is_valid_itr,
-    IsNormalizedBindingItrForConstructedObject is_normalized_binding_itr_for_constructed_object,
-    GetObjectPtr get_object_ptr,
-    GetCreate get_create)
+    BindingNormalizationFunctors<Functors...> functors)
   : fixed_size_allocator_data(fixed_size_allocator_data),
     memory_pool(memory_pool),
+    memory_pool_for_fully_expanded_components_maps(memory_pool_for_fully_expanded_components_maps),
+    memory_pool_for_component_replacements_maps(memory_pool_for_component_replacements_maps),
     binding_data_map(binding_data_map),
-    handle_compressed_binding(handle_compressed_binding),
-    handle_multibinding(handle_multibinding),
-    find_normalized_binding(find_normalized_binding),
-    is_valid_itr(is_valid_itr),
-    is_normalized_binding_itr_for_constructed_object(is_normalized_binding_itr_for_constructed_object),
-    get_object_ptr(get_object_ptr),
-    get_create(get_create),
+    functors(functors),
     entries_to_process(
         toplevel_entries.begin(), toplevel_entries.end(), ArenaAllocator<ComponentStorageEntry>(memory_pool)) {
 
   toplevel_entries.clear();
 }
 
-template <
-    typename HandleCompressedBinding,
-    typename HandleMultibinding,
-    typename FindNormalizedBinding,
-    typename IsValidItr,
-    typename IsNormalizedBindingItrForConstructedObject,
-    typename GetObjectPtr,
-    typename GetCreate>
-BindingNormalization::BindingNormalizationContext<
-      HandleCompressedBinding,
-      HandleMultibinding,
-      FindNormalizedBinding,
-      IsValidItr,
-      IsNormalizedBindingItrForConstructedObject,
-      GetObjectPtr,
-      GetCreate>::~BindingNormalizationContext() {
+template <typename... Functors>
+BindingNormalization::BindingNormalizationContext<Functors...>::~BindingNormalizationContext() {
   FruitAssert(components_with_no_args_with_expansion_in_progress.empty());
   FruitAssert(components_with_args_with_expansion_in_progress.empty());
 
@@ -110,48 +74,28 @@ BindingNormalization::BindingNormalizationContext<
   }
 }
 
-template <
-    typename HandleCompressedBinding,
-    typename HandleMultibinding,
-    typename FindNormalizedBinding,
-    typename IsValidItr,
-    typename IsNormalizedBindingItrForConstructedObject,
-    typename GetObjectPtr,
-    typename GetCreate>
+template <typename... Functors>
 void BindingNormalization::normalizeBindings(
     FixedSizeVector<ComponentStorageEntry>&& toplevel_entries,
     FixedSizeAllocator::FixedSizeAllocatorData& fixed_size_allocator_data,
     MemoryPool& memory_pool,
+    MemoryPool& memory_pool_for_fully_expanded_components_maps,
+    MemoryPool& memory_pool_for_component_replacements_maps,
     HashMapWithArenaAllocator<TypeId, ComponentStorageEntry>& binding_data_map,
-    HandleCompressedBinding handle_compressed_binding,
-    HandleMultibinding handle_multibinding,
-    FindNormalizedBinding find_normalized_binding,
-    IsValidItr is_valid_itr,
-    IsNormalizedBindingItrForConstructedObject is_normalized_binding_itr_for_constructed_object,
-    GetObjectPtr get_object_ptr,
-    GetCreate get_create) {
+    Functors... functors) {
 
   FruitAssert(binding_data_map.empty());
 
-  BindingNormalizationContext<
-      HandleCompressedBinding,
-      HandleMultibinding,
-      FindNormalizedBinding,
-      IsValidItr,
-      IsNormalizedBindingItrForConstructedObject,
-      GetObjectPtr,
-      GetCreate> context(
-          toplevel_entries,
-          fixed_size_allocator_data,
-          memory_pool,
-          binding_data_map,
-          handle_compressed_binding,
-          handle_multibinding,
-          find_normalized_binding,
-          is_valid_itr,
-          is_normalized_binding_itr_for_constructed_object,
-          get_object_ptr,
-          get_create);
+  using Context = BindingNormalizationContext<Functors...>;
+
+  Context context(
+      toplevel_entries,
+      fixed_size_allocator_data,
+      memory_pool,
+      memory_pool_for_fully_expanded_components_maps,
+      memory_pool_for_component_replacements_maps,
+      binding_data_map,
+      BindingNormalizationFunctors<Functors...>{functors...});
 
   // When we expand a lazy component, instead of removing it from the stack we change its kind (in entries_to_process)
   // to one of the *_END_MARKER kinds. This allows to keep track of the "call stack" for the expansion.
@@ -215,6 +159,11 @@ void BindingNormalization::normalizeBindings(
       FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
     }
   }
+
+  context.functors.save_fully_expanded_components_with_no_args(context.fully_expanded_components_with_no_args);
+  context.functors.save_fully_expanded_components_with_args(context.fully_expanded_components_with_args);
+  context.functors.save_component_replacements_with_no_args(context.component_with_no_args_replacements);
+  context.functors.save_component_replacements_with_args(context.component_with_args_replacements);
 }
 
 template <typename... Params>
@@ -225,10 +174,10 @@ FRUIT_ALWAYS_INLINE inline void BindingNormalization::handleBindingForConstructe
 
   context.entries_to_process.pop_back();
 
-  auto itr = context.find_normalized_binding(entry.type_id);
-  if (context.is_valid_itr(itr)) {
-    if (!context.is_normalized_binding_itr_for_constructed_object(itr)
-        || context.get_object_ptr(itr) != entry.binding_for_constructed_object.object_ptr) {
+  auto itr = context.functors.find_normalized_binding(entry.type_id);
+  if (context.functors.is_valid_itr(itr)) {
+    if (!context.functors.is_normalized_binding_itr_for_constructed_object(itr)
+        || context.functors.get_object_ptr(itr) != entry.binding_for_constructed_object.object_ptr) {
       printMultipleBindingsError(entry.type_id);
       FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
     }
@@ -265,10 +214,10 @@ FRUIT_ALWAYS_INLINE inline void BindingNormalization::handleBindingForObjectToCo
   FruitAssert(entry.kind == ComponentStorageEntry::Kind::BINDING_FOR_OBJECT_TO_CONSTRUCT_THAT_NEEDS_ALLOCATION);
   context.entries_to_process.pop_back();
 
-  auto itr = context.find_normalized_binding(entry.type_id);
-  if (context.is_valid_itr(itr)) {
-    if (context.is_normalized_binding_itr_for_constructed_object(itr)
-        || context.get_create(itr) != entry.binding_for_object_to_construct.create) {
+  auto itr = context.functors.find_normalized_binding(entry.type_id);
+  if (context.functors.is_valid_itr(itr)) {
+    if (context.functors.is_normalized_binding_itr_for_constructed_object(itr)
+        || context.functors.get_create(itr) != entry.binding_for_object_to_construct.create) {
       printMultipleBindingsError(entry.type_id);
       FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
     }
@@ -300,10 +249,10 @@ FRUIT_ALWAYS_INLINE inline void BindingNormalization::handleBindingForObjectToCo
   FruitAssert(entry.kind == ComponentStorageEntry::Kind::BINDING_FOR_OBJECT_TO_CONSTRUCT_THAT_NEEDS_NO_ALLOCATION);
   context.entries_to_process.pop_back();
 
-  auto itr = context.find_normalized_binding(entry.type_id);
-  if (context.is_valid_itr(itr)) {
-    if (context.is_normalized_binding_itr_for_constructed_object(itr)
-        || context.get_create(itr) != entry.binding_for_object_to_construct.create) {
+  auto itr = context.functors.find_normalized_binding(entry.type_id);
+  if (context.functors.is_valid_itr(itr)) {
+    if (context.functors.is_normalized_binding_itr_for_constructed_object(itr)
+        || context.functors.get_create(itr) != entry.binding_for_object_to_construct.create) {
       printMultipleBindingsError(entry.type_id);
       FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
     }
@@ -334,7 +283,7 @@ FRUIT_ALWAYS_INLINE inline void BindingNormalization::handleCompressedBinding(
   ComponentStorageEntry entry = context.entries_to_process.back();
   FruitAssert(entry.kind == ComponentStorageEntry::Kind::COMPRESSED_BINDING);
   context.entries_to_process.pop_back();
-  context.handle_compressed_binding(entry);
+  context.functors.handle_compressed_binding(entry);
 }
 
 template <typename... Params>
@@ -349,7 +298,7 @@ void BindingNormalization::handleMultibinding(
   ComponentStorageEntry vector_creator_entry = std::move(context.entries_to_process.back());
   context.entries_to_process.pop_back();
   FruitAssert(vector_creator_entry.kind == ComponentStorageEntry::Kind::MULTIBINDING_VECTOR_CREATOR);
-  context.handle_multibinding(entry, vector_creator_entry);
+  context.functors.handle_multibinding(entry, vector_creator_entry);
 }
 
 template <typename... Params>
@@ -367,7 +316,7 @@ void BindingNormalization::handleMultibindingVectorCreator(
               == ComponentStorageEntry::Kind::MULTIBINDING_FOR_OBJECT_TO_CONSTRUCT_THAT_NEEDS_ALLOCATION
           || multibinding_entry.kind
               == ComponentStorageEntry::Kind::MULTIBINDING_FOR_OBJECT_TO_CONSTRUCT_THAT_NEEDS_NO_ALLOCATION);
-  context.handle_multibinding(multibinding_entry, entry);
+  context.functors.handle_multibinding(multibinding_entry, entry);
 }
 
 template <typename... Params>
@@ -411,51 +360,37 @@ void BindingNormalization::handleReplacedLazyComponentWithArgs(BindingNormalizat
       || replacement_component_entry.kind == ComponentStorageEntry::Kind::REPLACEMENT_LAZY_COMPONENT_WITH_ARGS);
 
   if (context.components_with_args_with_expansion_in_progress.count(entry.lazy_component_with_args) != 0
-      || context.fully_expanded_components_with_args.count(entry.lazy_component_with_args) != 0) {
+      || context.fully_expanded_components_with_args.count(entry.lazy_component_with_args) != 0
+      || context.functors.is_component_with_args_already_expanded_in_normalized_component(
+          entry.lazy_component_with_args)) {
     printComponentReplacementFailedBecauseTargetAlreadyExpanded(replaced_component_entry, replacement_component_entry);
     FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
   }
 
+  auto replacement_in_normalized_component_itr =
+      context.functors.get_component_with_args_replacement_in_normalized_component(
+          replaced_component_entry.lazy_component_with_args);
+  if (context.functors.is_lazy_component_with_args_iterator_valid(replacement_in_normalized_component_itr)) {
+    handlePreexistingLazyComponentWithArgsReplacement(
+        replaced_component_entry,
+        context.functors.dereference_lazy_component_with_args_iterator(replacement_in_normalized_component_itr),
+        replacement_component_entry);
+    return;
+  }
+
   ComponentStorageEntry& replacement_component_entry_in_map =
       context.component_with_args_replacements[replaced_component_entry.lazy_component_with_args];
-  if (replacement_component_entry_in_map.type_id.type_info == nullptr) {
-    // We just inserted replaced_component_entry.lazy_component_with_args in the map, so it's now owned by the
-    // map.
-    replacement_component_entry_in_map = replacement_component_entry;
-  } else {
-    // The map already contained a replacement component, we must check that they are consistent.
-    switch (replacement_component_entry.kind) { // LCOV_EXCL_BR_LINE
-    case ComponentStorageEntry::Kind::REPLACEMENT_LAZY_COMPONENT_WITH_NO_ARGS:
-      if (replacement_component_entry_in_map.kind != ComponentStorageEntry::Kind::REPLACEMENT_LAZY_COMPONENT_WITH_NO_ARGS
-          || replacement_component_entry_in_map.lazy_component_with_no_args.erased_fun
-              != replacement_component_entry.lazy_component_with_no_args.erased_fun) {
-        printIncompatibleComponentReplacementsError(
-            replaced_component_entry, replacement_component_entry, replacement_component_entry_in_map);
-        FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
-      }
-
-      // Duplicate but consistent replacement, we'll ignore it.
-      replaced_component_entry.lazy_component_with_args.destroy();
-      break;
-
-    case ComponentStorageEntry::Kind::REPLACEMENT_LAZY_COMPONENT_WITH_ARGS:
-      if (replacement_component_entry_in_map.kind != ComponentStorageEntry::Kind::REPLACEMENT_LAZY_COMPONENT_WITH_ARGS
-          || !(*replacement_component_entry_in_map.lazy_component_with_args.component
-              == *replacement_component_entry.lazy_component_with_args.component)) {
-        printIncompatibleComponentReplacementsError(
-            replaced_component_entry, replacement_component_entry, replacement_component_entry_in_map);
-        FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
-      }
-
-      // Duplicate but consistent replacement, we'll ignore it.
-      replaced_component_entry.lazy_component_with_args.destroy();
-      replacement_component_entry.lazy_component_with_args.destroy();
-      break;
-
-    default:
-      FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
-    }
+  if (replacement_component_entry_in_map.type_id.type_info != nullptr) {
+    handlePreexistingLazyComponentWithArgsReplacement(
+        replaced_component_entry,
+        replacement_component_entry_in_map,
+        replacement_component_entry);
+    return;
   }
+
+  // We just inserted replaced_component_entry.lazy_component_with_args in the map, so it's now owned by the
+  // map.
+  replacement_component_entry_in_map = replacement_component_entry;
 }
 
 template <typename... Params>
@@ -473,49 +408,37 @@ void BindingNormalization::handleReplacedLazyComponentWithNoArgs(BindingNormaliz
       || replacement_component_entry.kind == ComponentStorageEntry::Kind::REPLACEMENT_LAZY_COMPONENT_WITH_ARGS);
 
   if (context.components_with_no_args_with_expansion_in_progress.count(entry.lazy_component_with_no_args) != 0
-      || context.fully_expanded_components_with_no_args.count(entry.lazy_component_with_no_args) != 0) {
+      || context.fully_expanded_components_with_no_args.count(entry.lazy_component_with_no_args) != 0
+      || context.functors.is_component_with_no_args_already_expanded_in_normalized_component(
+          entry.lazy_component_with_no_args)) {
     printComponentReplacementFailedBecauseTargetAlreadyExpanded(replaced_component_entry, replacement_component_entry);
     FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
   }
 
+  auto replacement_in_normalized_component_itr =
+      context.functors.get_component_with_no_args_replacement_in_normalized_component(
+          replaced_component_entry.lazy_component_with_no_args);
+  if (context.functors.is_lazy_component_with_no_args_iterator_valid(replacement_in_normalized_component_itr)) {
+    handlePreexistingLazyComponentWithNoArgsReplacement(
+        replaced_component_entry,
+        context.functors.dereference_lazy_component_with_no_args_iterator(replacement_in_normalized_component_itr),
+        replacement_component_entry);
+    return;
+  }
+
   ComponentStorageEntry& replacement_component_entry_in_map =
       context.component_with_no_args_replacements[replaced_component_entry.lazy_component_with_no_args];
-  if (replacement_component_entry_in_map.type_id.type_info == nullptr) {
-    // We just inserted replaced_component_entry.lazy_component_with_args in the map, so it's now owned by the
-    // map.
-    replacement_component_entry_in_map = replacement_component_entry;
-  } else {
-    // The map already contained a replacement component, we must check that they are consistent.
-    switch (replacement_component_entry.kind) { // LCOV_EXCL_BR_LINE
-    case ComponentStorageEntry::Kind::REPLACEMENT_LAZY_COMPONENT_WITH_NO_ARGS:
-      if (replacement_component_entry_in_map.kind != ComponentStorageEntry::Kind::REPLACEMENT_LAZY_COMPONENT_WITH_NO_ARGS
-          || replacement_component_entry_in_map.lazy_component_with_no_args.erased_fun
-              != replacement_component_entry.lazy_component_with_no_args.erased_fun) {
-        printIncompatibleComponentReplacementsError(
-            replaced_component_entry, replacement_component_entry, replacement_component_entry_in_map);
-        FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
-      }
-
-      // Duplicate but consistent replacement, we'll ignore it.
-      break;
-
-    case ComponentStorageEntry::Kind::REPLACEMENT_LAZY_COMPONENT_WITH_ARGS:
-      if (replacement_component_entry_in_map.kind != ComponentStorageEntry::Kind::REPLACEMENT_LAZY_COMPONENT_WITH_ARGS
-          || !(*replacement_component_entry_in_map.lazy_component_with_args.component
-              == *replacement_component_entry.lazy_component_with_args.component)) {
-        printIncompatibleComponentReplacementsError(
-            replaced_component_entry, replacement_component_entry, replacement_component_entry_in_map);
-        FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
-      }
-
-      // Duplicate but consistent replacement, we'll ignore it.
-      replacement_component_entry.lazy_component_with_args.destroy();
-      break;
-
-    default:
-      FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
-    }
+  if (replacement_component_entry_in_map.type_id.type_info != nullptr) {
+    handlePreexistingLazyComponentWithNoArgsReplacement(
+        replaced_component_entry,
+        replacement_component_entry_in_map,
+        replacement_component_entry);
+    return;
   }
+
+  // We just inserted replaced_component_entry.lazy_component_with_args in the map, so it's now owned by the
+  // map.
+  replacement_component_entry_in_map = replacement_component_entry;
 }
 
 template <typename... Params>
@@ -549,13 +472,25 @@ FRUIT_ALWAYS_INLINE inline void BindingNormalization::handleLazyComponentWithArg
     BindingNormalizationContext<Params...>& context) {
   ComponentStorageEntry entry = context.entries_to_process.back();
   FruitAssert(entry.kind == ComponentStorageEntry::Kind::LAZY_COMPONENT_WITH_ARGS);
-  if (context.fully_expanded_components_with_args.count(entry.lazy_component_with_args)) {
+  if (context.fully_expanded_components_with_args.count(entry.lazy_component_with_args)
+      || context.functors.is_component_with_args_already_expanded_in_normalized_component(
+          entry.lazy_component_with_args)) {
     // This lazy component was already inserted, skip it.
     entry.lazy_component_with_args.destroy();
     context.entries_to_process.pop_back();
     return;
   }
 
+  auto replacement_component_in_normalized_component_itr =
+      context.functors.get_component_with_args_replacement_in_normalized_component(entry.lazy_component_with_args);
+  if (context.functors.is_lazy_component_with_args_iterator_valid(replacement_component_in_normalized_component_itr)) {
+    entry.lazy_component_with_args.destroy();
+    performComponentReplacement(context,
+                                context.functors.dereference_lazy_component_with_args_iterator(
+                                    replacement_component_in_normalized_component_itr));
+    return;
+  }
+
   auto replacement_component_itr = context.component_with_args_replacements.find(entry.lazy_component_with_args);
   if (replacement_component_itr != context.component_with_args_replacements.end()) {
     entry.lazy_component_with_args.destroy();
@@ -589,12 +524,24 @@ FRUIT_ALWAYS_INLINE inline void BindingNormalization::handleLazyComponentWithNoA
     BindingNormalizationContext<Params...>& context) {
   ComponentStorageEntry entry = context.entries_to_process.back();
   FruitAssert(entry.kind == ComponentStorageEntry::Kind::LAZY_COMPONENT_WITH_NO_ARGS);
-  if (context.fully_expanded_components_with_no_args.count(entry.lazy_component_with_no_args)) {
+
+  if (context.fully_expanded_components_with_no_args.count(entry.lazy_component_with_no_args)
+      || context.functors.is_component_with_no_args_already_expanded_in_normalized_component(
+          entry.lazy_component_with_no_args)) {
     // This lazy component was already inserted, skip it.
     context.entries_to_process.pop_back();
     return;
   }
 
+  auto replacement_component_in_normalized_component_itr =
+      context.functors.get_component_with_no_args_replacement_in_normalized_component(entry.lazy_component_with_no_args);
+  if (context.functors.is_lazy_component_with_no_args_iterator_valid(replacement_component_in_normalized_component_itr)) {
+    performComponentReplacement(context,
+                                context.functors.dereference_lazy_component_with_no_args_iterator(
+                                    replacement_component_in_normalized_component_itr));
+    return;
+  }
+
   auto replacement_component_itr = context.component_with_no_args_replacements.find(entry.lazy_component_with_no_args);
   if (replacement_component_itr != context.component_with_no_args_replacements.end()) {
     performComponentReplacement(context, replacement_component_itr->second);
@@ -622,125 +569,6 @@ FRUIT_ALWAYS_INLINE inline void BindingNormalization::handleLazyComponentWithNoA
   context.entries_to_process.back().lazy_component_with_no_args.addBindings(context.entries_to_process);
 }
 
-template <
-    typename FindNormalizedBinding,
-    typename IsValidItr,
-    typename IsNormalizedBindingItrForConstructedObject,
-    typename GetObjectPtr,
-    typename GetCreate>
-void BindingNormalization::normalizeBindingsAndAddTo(
-    FixedSizeVector<ComponentStorageEntry>&& toplevel_entries,
-    MemoryPool& memory_pool,
-    const FixedSizeAllocator::FixedSizeAllocatorData& base_fixed_size_allocator_data,
-    const std::unordered_map<TypeId, NormalizedMultibindingSet>& base_multibindings,
-    const NormalizedComponentStorage::BindingCompressionInfoMap& base_binding_compression_info_map,
-    FixedSizeAllocator::FixedSizeAllocatorData& fixed_size_allocator_data,
-    std::vector<ComponentStorageEntry, ArenaAllocator<ComponentStorageEntry>>& new_bindings_vector,
-    std::unordered_map<TypeId, NormalizedMultibindingSet>& multibindings,
-    FindNormalizedBinding find_normalized_binding,
-    IsValidItr is_valid_itr,
-    IsNormalizedBindingItrForConstructedObject is_normalized_binding_itr_for_constructed_object,
-    GetObjectPtr get_object_ptr,
-    GetCreate get_create) {
-
-  multibindings = base_multibindings;
-
-  fixed_size_allocator_data = base_fixed_size_allocator_data;
-
-  multibindings_vector_t multibindings_vector =
-      multibindings_vector_t(ArenaAllocator<multibindings_vector_elem_t>(memory_pool));
-
-  HashMapWithArenaAllocator<TypeId, ComponentStorageEntry> binding_data_map =
-      createHashMapWithArenaAllocator<TypeId, ComponentStorageEntry>(memory_pool);
-
-  normalizeBindings(
-      std::move(toplevel_entries),
-      fixed_size_allocator_data,
-      memory_pool,
-      binding_data_map,
-      [](ComponentStorageEntry) {},
-      [&multibindings_vector](ComponentStorageEntry multibinding,
-                              ComponentStorageEntry multibinding_vector_creator) {
-        multibindings_vector.emplace_back(multibinding, multibinding_vector_creator);
-      },
-      find_normalized_binding,
-      is_valid_itr,
-      is_normalized_binding_itr_for_constructed_object,
-      get_object_ptr,
-      get_create);
-
-  // Copy the normalized bindings into the result vector.
-  new_bindings_vector.clear();
-  new_bindings_vector.reserve(binding_data_map.size());
-  for (auto& p : binding_data_map) {
-    new_bindings_vector.push_back(p.second);
-  }
-
-  // Determine what binding compressions must be undone.
-
-  HashSetWithArenaAllocator<TypeId> binding_compressions_to_undo =
-      createHashSetWithArenaAllocator<TypeId>(memory_pool);
-  for (const ComponentStorageEntry& entry : new_bindings_vector) {
-    switch (entry.kind) { // LCOV_EXCL_BR_LINE
-    case ComponentStorageEntry::Kind::BINDING_FOR_CONSTRUCTED_OBJECT:
-      break;
-
-    case ComponentStorageEntry::Kind::BINDING_FOR_OBJECT_TO_CONSTRUCT_THAT_NEEDS_NO_ALLOCATION:
-    case ComponentStorageEntry::Kind::BINDING_FOR_OBJECT_TO_CONSTRUCT_THAT_NEEDS_ALLOCATION:
-    case ComponentStorageEntry::Kind::BINDING_FOR_OBJECT_TO_CONSTRUCT_WITH_UNKNOWN_ALLOCATION:
-      {
-        const BindingDeps *entry_deps = entry.binding_for_object_to_construct.deps;
-        for (std::size_t i = 0; i < entry_deps->num_deps; ++i) {
-          auto binding_compression_itr =
-              base_binding_compression_info_map.find(entry_deps->deps[i]);
-          if (binding_compression_itr != base_binding_compression_info_map.end()
-              && binding_compression_itr->second.i_type_id != entry.type_id) {
-            // The binding compression for `p.second.getDeps()->deps[i]' must be undone because something
-            // different from binding_compression_itr->iTypeId is now bound to it.
-            binding_compressions_to_undo.insert(entry_deps->deps[i]);
-          }
-        }
-      }
-      break;
-
-    default:
-#ifdef FRUIT_EXTRA_DEBUG
-      std::cerr << "Unexpected kind: " << (std::size_t)entry.kind << std::endl;
-#endif
-      FRUIT_UNREACHABLE; // LCOV_EXCL_LINE
-      break;
-    }
-  }
-
-  // Step 3: undo any binding compressions that can no longer be applied.
-  for (TypeId cTypeId : binding_compressions_to_undo) {
-    auto binding_compression_itr = base_binding_compression_info_map.find(cTypeId);
-    FruitAssert(binding_compression_itr != base_binding_compression_info_map.end());
-    FruitAssert(is_valid_itr(find_normalized_binding(binding_compression_itr->second.i_type_id)));
-
-    ComponentStorageEntry c_binding;
-    c_binding.type_id = cTypeId;
-    c_binding.kind = ComponentStorageEntry::Kind::BINDING_FOR_OBJECT_TO_CONSTRUCT_WITH_UNKNOWN_ALLOCATION;
-    c_binding.binding_for_object_to_construct = binding_compression_itr->second.c_binding;
-
-    ComponentStorageEntry i_binding;
-    i_binding.type_id = binding_compression_itr->second.i_type_id;
-    i_binding.kind = ComponentStorageEntry::Kind::BINDING_FOR_OBJECT_TO_CONSTRUCT_THAT_NEEDS_NO_ALLOCATION;
-    i_binding.binding_for_object_to_construct = binding_compression_itr->second.i_binding;
-
-    new_bindings_vector.push_back(std::move(c_binding));
-    // This TypeId is already in normalized_component.bindings, we overwrite it here.
-    new_bindings_vector.push_back(std::move(i_binding));
-
-#ifdef FRUIT_EXTRA_DEBUG
-    std::cout << "InjectorStorage: undoing binding compression for: " << binding_compression_itr->second.i_type_id << "->" << cTypeId << std::endl;
-#endif
-  }
-
-  // Step 4: Add multibindings.
-  BindingNormalization::addMultibindings(multibindings, fixed_size_allocator_data, multibindings_vector);
-}
-
 template <typename SaveCompressedBindingUndoInfo>
 std::vector<ComponentStorageEntry, ArenaAllocator<ComponentStorageEntry>> BindingNormalization::performBindingCompression(
     HashMapWithArenaAllocator<TypeId, ComponentStorageEntry>&& binding_data_map,
@@ -847,21 +675,34 @@ std::vector<ComponentStorageEntry, ArenaAllocator<ComponentStorageEntry>> Bindin
   return result;
 }
 
-template <typename SaveCompressedBindingUndoInfo>
+template <
+    typename SaveCompressedBindingUndoInfo,
+    typename SaveFullyExpandedComponentsWithNoArgs,
+    typename SaveFullyExpandedComponentsWithArgs,
+    typename SaveComponentReplacementsWithNoArgs,
+    typename SaveComponentReplacementsWithArgs>
 void BindingNormalization::normalizeBindingsWithBindingCompression(
     FixedSizeVector<ComponentStorageEntry>&& toplevel_entries,
     FixedSizeAllocator::FixedSizeAllocatorData& fixed_size_allocator_data,
     MemoryPool& memory_pool,
+    MemoryPool& memory_pool_for_fully_expanded_components_maps,
+    MemoryPool& memory_pool_for_component_replacements_maps,
     const std::vector<TypeId, ArenaAllocator<TypeId>>& exposed_types,
     std::vector<ComponentStorageEntry, ArenaAllocator<ComponentStorageEntry>>& bindings_vector,
     std::unordered_map<TypeId, NormalizedMultibindingSet>& multibindings,
-    SaveCompressedBindingUndoInfo save_compressed_binding_undo_info) {
+    SaveCompressedBindingUndoInfo save_compressed_binding_undo_info,
+    SaveFullyExpandedComponentsWithNoArgs save_fully_expanded_components_with_no_args,
+    SaveFullyExpandedComponentsWithArgs save_fully_expanded_components_with_args,
+    SaveComponentReplacementsWithNoArgs save_component_replacements_with_no_args,
+    SaveComponentReplacementsWithArgs save_component_replacements_with_args) {
 
   HashMapWithArenaAllocator<TypeId, ComponentStorageEntry> binding_data_map =
-      createHashMapWithArenaAllocator<TypeId, ComponentStorageEntry>(memory_pool);
+      createHashMapWithArenaAllocator<TypeId, ComponentStorageEntry>(
+          20 /* capacity */, memory_pool);
   // CtypeId -> (ItypeId, bindingData)
   HashMapWithArenaAllocator<TypeId, BindingNormalization::BindingCompressionInfo> compressed_bindings_map =
-      createHashMapWithArenaAllocator<TypeId, BindingCompressionInfo>(memory_pool);
+      createHashMapWithArenaAllocator<TypeId, BindingCompressionInfo>(
+          20 /* capacity */, memory_pool);
 
   multibindings_vector_t multibindings_vector =
       multibindings_vector_t(ArenaAllocator<multibindings_vector_elem_t>(memory_pool));
@@ -872,6 +713,8 @@ void BindingNormalization::normalizeBindingsWithBindingCompression(
       std::move(toplevel_entries),
       fixed_size_allocator_data,
       memory_pool,
+      memory_pool_for_fully_expanded_components_maps,
+      memory_pool_for_component_replacements_maps,
       binding_data_map,
       [&compressed_bindings_map](ComponentStorageEntry entry) {
         BindingCompressionInfo& compression_info = compressed_bindings_map[entry.compressed_binding.c_type_id];
@@ -886,7 +729,19 @@ void BindingNormalization::normalizeBindingsWithBindingCompression(
       [](DummyIterator) { return false; },
       [](DummyIterator) { return false; },
       [](DummyIterator) { return nullptr; },
-      [](DummyIterator) { return nullptr; });
+      [](DummyIterator) { return nullptr; },
+      [](const LazyComponentWithNoArgs&) { return false; },
+      [](const LazyComponentWithArgs&) { return false; },
+      save_fully_expanded_components_with_no_args,
+      save_fully_expanded_components_with_args,
+      [](const LazyComponentWithNoArgs&) { return (ComponentStorageEntry*) nullptr; },
+      [](const LazyComponentWithArgs&) { return (ComponentStorageEntry*) nullptr; },
+      [](ComponentStorageEntry*) { return false; },
+      [](ComponentStorageEntry*) { return false; },
+      [](ComponentStorageEntry* p) { return *p; },
+      [](ComponentStorageEntry* p) { return *p; },
+      save_component_replacements_with_no_args,
+      save_component_replacements_with_args);
 
   bindings_vector =
       BindingNormalization::performBindingCompression(
@@ -903,38 +758,6 @@ void BindingNormalization::normalizeBindingsWithBindingCompression(
       multibindings_vector);
 }
 
-inline BindingNormalization::LazyComponentWithNoArgsSet BindingNormalization::createLazyComponentWithNoArgsSet(
-    MemoryPool& memory_pool)  {
-  return createHashSetWithArenaAllocatorAndCustomFunctors<LazyComponentWithNoArgs>(
-      memory_pool,
-      HashLazyComponentWithNoArgs(),
-      std::equal_to<LazyComponentWithNoArgs>());
-}
-
-inline BindingNormalization::LazyComponentWithArgsSet BindingNormalization::createLazyComponentWithArgsSet(
-    MemoryPool& memory_pool) {
-  return createHashSetWithArenaAllocatorAndCustomFunctors<LazyComponentWithArgs>(
-      memory_pool,
-      HashLazyComponentWithArgs(),
-      LazyComponentWithArgsEqualTo());
-}
-
-inline BindingNormalization::LazyComponentWithNoArgsReplacementMap
-    BindingNormalization::createLazyComponentWithNoArgsReplacementMap(MemoryPool& memory_pool) {
-  return createHashMapWithArenaAllocatorAndCustomFunctors<LazyComponentWithNoArgs, ComponentStorageEntry>(
-      memory_pool,
-      HashLazyComponentWithNoArgs(),
-      std::equal_to<LazyComponentWithNoArgs>());
-}
-
-inline BindingNormalization::LazyComponentWithArgsReplacementMap
-    BindingNormalization::createLazyComponentWithArgsReplacementMap(MemoryPool& memory_pool) {
-  return createHashMapWithArenaAllocatorAndCustomFunctors<LazyComponentWithArgs, ComponentStorageEntry>(
-      memory_pool,
-      HashLazyComponentWithArgs(),
-      LazyComponentWithArgsEqualTo());
-}
-
 
 } // namespace impl
 } // namespace fruit
diff --git a/include/fruit/impl/normalized_component_storage/normalized_component_storage.defn.h b/include/fruit/impl/normalized_component_storage/normalized_component_storage.defn.h
index 76be050..d67af7a 100644
--- a/include/fruit/impl/normalized_component_storage/normalized_component_storage.defn.h
+++ b/include/fruit/impl/normalized_component_storage/normalized_component_storage.defn.h
@@ -22,18 +22,42 @@
 namespace fruit {
 namespace impl {
 
-inline NormalizedComponentStorage& NormalizedComponentStorage::operator=(NormalizedComponentStorage&& other) {
-  bindings = std::move(other.bindings);
-  multibindings = std::move(other.multibindings);
-  fixed_size_allocator_data = std::move(other.fixed_size_allocator_data);
+inline NormalizedComponentStorage::LazyComponentWithNoArgsSet NormalizedComponentStorage::createLazyComponentWithNoArgsSet(
+    size_t capacity, MemoryPool& memory_pool)  {
+  return createHashSetWithArenaAllocatorAndCustomFunctors<LazyComponentWithNoArgs>(
+      capacity,
+      memory_pool,
+      NormalizedComponentStorage::HashLazyComponentWithNoArgs(),
+      std::equal_to<LazyComponentWithNoArgs>());
+}
 
-  // We must destroy `bindingCompressionInfoMap` before its memory pool, so we clear it explicitly.
-  bindingCompressionInfoMap = std::unique_ptr<BindingCompressionInfoMap>();
-  bindingCompressionInfoMap = std::move(other.bindingCompressionInfoMap);
+inline NormalizedComponentStorage::LazyComponentWithArgsSet NormalizedComponentStorage::createLazyComponentWithArgsSet(
+    size_t capacity, MemoryPool& memory_pool) {
+  return createHashSetWithArenaAllocatorAndCustomFunctors<LazyComponentWithArgs>(
+      capacity,
+      memory_pool,
+      NormalizedComponentStorage::HashLazyComponentWithArgs(),
+      NormalizedComponentStorage::LazyComponentWithArgsEqualTo());
+}
 
-  bindingCompressionInfoMapMemoryPool = std::move(other.bindingCompressionInfoMapMemoryPool);
+inline NormalizedComponentStorage::LazyComponentWithNoArgsReplacementMap
+    NormalizedComponentStorage::createLazyComponentWithNoArgsReplacementMap(
+        size_t capacity, MemoryPool& memory_pool) {
+  return createHashMapWithArenaAllocatorAndCustomFunctors<LazyComponentWithNoArgs, ComponentStorageEntry>(
+      capacity,
+      memory_pool,
+      NormalizedComponentStorage::HashLazyComponentWithNoArgs(),
+      std::equal_to<LazyComponentWithNoArgs>());
+}
 
-  return *this;
+inline NormalizedComponentStorage::LazyComponentWithArgsReplacementMap
+    NormalizedComponentStorage::createLazyComponentWithArgsReplacementMap(
+        size_t capacity, MemoryPool& memory_pool) {
+  return createHashMapWithArenaAllocatorAndCustomFunctors<LazyComponentWithArgs, ComponentStorageEntry>(
+      capacity,
+      memory_pool,
+      NormalizedComponentStorage::HashLazyComponentWithArgs(),
+      NormalizedComponentStorage::LazyComponentWithArgsEqualTo());
 }
 
 } // namespace impl
diff --git a/include/fruit/impl/normalized_component_storage/normalized_component_storage.h b/include/fruit/impl/normalized_component_storage/normalized_component_storage.h
index 47ec1d1..caa0e32 100644
--- a/include/fruit/impl/normalized_component_storage/normalized_component_storage.h
+++ b/include/fruit/impl/normalized_component_storage/normalized_component_storage.h
@@ -55,6 +55,43 @@ public:
   using BindingCompressionInfoMap = HashMapWithArenaAllocator<TypeId, CompressedBindingUndoInfo>;
   using BindingCompressionInfoMapAllocator = BindingCompressionInfoMap::allocator_type;
 
+  using LazyComponentWithNoArgs = ComponentStorageEntry::LazyComponentWithNoArgs;
+  using LazyComponentWithArgs = ComponentStorageEntry::LazyComponentWithArgs;
+
+  struct HashLazyComponentWithNoArgs {
+    std::size_t operator()(const LazyComponentWithNoArgs& x) const {
+      return x.hashCode();
+    }
+  };
+
+  struct LazyComponentWithArgsEqualTo {
+    bool operator()(const LazyComponentWithArgs& x, const LazyComponentWithArgs& y) const {
+      return *x.component == *y.component;
+    }
+  };
+
+  struct HashLazyComponentWithArgs {
+    std::size_t operator()(const LazyComponentWithArgs& x) const {
+      return x.component->hashCode();
+    }
+  };
+
+  using LazyComponentWithNoArgsSet =
+      HashSetWithArenaAllocator<LazyComponentWithNoArgs, HashLazyComponentWithNoArgs, std::equal_to<LazyComponentWithNoArgs>>;
+  using LazyComponentWithArgsSet =
+      HashSetWithArenaAllocator<LazyComponentWithArgs, HashLazyComponentWithArgs, LazyComponentWithArgsEqualTo>;
+
+  using LazyComponentWithNoArgsReplacementMap =
+      HashMapWithArenaAllocator<LazyComponentWithNoArgs, ComponentStorageEntry, NormalizedComponentStorage::HashLazyComponentWithNoArgs, std::equal_to<LazyComponentWithNoArgs>>;
+  using LazyComponentWithArgsReplacementMap =
+      HashMapWithArenaAllocator<LazyComponentWithArgs, ComponentStorageEntry, NormalizedComponentStorage::HashLazyComponentWithArgs, NormalizedComponentStorage::LazyComponentWithArgsEqualTo>;
+
+  static LazyComponentWithNoArgsSet createLazyComponentWithNoArgsSet(size_t capacity, MemoryPool& memory_pool);
+  static LazyComponentWithArgsSet createLazyComponentWithArgsSet(size_t capacity, MemoryPool& memory_pool);
+
+  static LazyComponentWithNoArgsReplacementMap createLazyComponentWithNoArgsReplacementMap(size_t capacity, MemoryPool& memory_pool);
+  static LazyComponentWithArgsReplacementMap createLazyComponentWithArgsReplacementMap(size_t capacity, MemoryPool& memory_pool);
+
 private:
   // A graph with types as nodes (each node stores the BindingData for the type) and dependencies as edges.
   // For types that have a constructed object already, the corresponding node is stored as terminal node.
@@ -66,21 +103,34 @@ private:
   // Contains data on the set of types that can be allocated using this component.
   FixedSizeAllocator::FixedSizeAllocatorData fixed_size_allocator_data;
 
-  // The MemoryPool used to allocate bindingCompressionInfoMap.
-  MemoryPool bindingCompressionInfoMapMemoryPool;
+  // The MemoryPool used to allocate bindingCompressionInfoMap, fully_expanded_components_with_no_args and
+  // fully_expanded_components_with_args.
+  MemoryPool normalized_component_memory_pool;
 
   // Stores information on binding compression that was performed in bindings of this object.
   // See also the documentation for BindingCompressionInfoMap.
-  // We hold this via a unique_ptr to avoid including Boost's hashmap implementation.
-  std::unique_ptr<BindingCompressionInfoMap> bindingCompressionInfoMap;
+  BindingCompressionInfoMap binding_compression_info_map;
+
+  LazyComponentWithNoArgsSet fully_expanded_components_with_no_args;
+  LazyComponentWithArgsSet fully_expanded_components_with_args;
+
+  LazyComponentWithNoArgsReplacementMap component_with_no_args_replacements;
+  LazyComponentWithArgsReplacementMap component_with_args_replacements;
   
   friend class InjectorStorage;
-  
+  friend class BindingNormalization;
+
 public:
   using Graph = SemistaticGraph<TypeId, NormalizedBinding>;
 
   NormalizedComponentStorage() = delete;
 
+  NormalizedComponentStorage(NormalizedComponentStorage&&) = delete;
+  NormalizedComponentStorage(const NormalizedComponentStorage&) = delete;
+
+  NormalizedComponentStorage& operator=(NormalizedComponentStorage&&) = delete;
+  NormalizedComponentStorage& operator=(const NormalizedComponentStorage&) = delete;
+
   // These are just used as tags to select the desired constructor.
   struct WithUndoableCompression {};
   struct WithPermanentCompression {};
@@ -103,12 +153,7 @@ public:
       MemoryPool& memory_pool,
       WithPermanentCompression);
 
-  NormalizedComponentStorage(NormalizedComponentStorage&&) = delete;
-  NormalizedComponentStorage(const NormalizedComponentStorage&) = delete;
-  
-  NormalizedComponentStorage& operator=(NormalizedComponentStorage&&);
-  NormalizedComponentStorage& operator=(const NormalizedComponentStorage&) = delete;
-  
+
   // We don't use the default destructor because that will require the inclusion of
   // the Boost's hashmap header. We define this in the cpp file instead.
   ~NormalizedComponentStorage();
diff --git a/include/fruit/impl/util/hash_helpers.defn.h b/include/fruit/impl/util/hash_helpers.defn.h
index b5c9898..1f3b4f3 100644
--- a/include/fruit/impl/util/hash_helpers.defn.h
+++ b/include/fruit/impl/util/hash_helpers.defn.h
@@ -34,20 +34,15 @@ inline HashSet<T> createHashSet(size_t capacity) {
 }
 
 template <typename T>
-inline HashSetWithArenaAllocator<T> createHashSetWithArenaAllocator(MemoryPool& memory_pool) {
-  return createHashSetWithArenaAllocator<T>(10, memory_pool);
-}
-
-template <typename T>
 inline HashSetWithArenaAllocator<T> createHashSetWithArenaAllocator(size_t capacity, MemoryPool& memory_pool) {
   return HashSetWithArenaAllocator<T>(capacity, std::hash<T>(), std::equal_to<T>(), ArenaAllocator<T>(memory_pool));
 }
 
 template <typename T, typename Hasher, typename EqualityComparator>
 inline HashSetWithArenaAllocator<T, Hasher, EqualityComparator> createHashSetWithArenaAllocatorAndCustomFunctors(
-    MemoryPool& memory_pool, Hasher hasher, EqualityComparator equality_comparator) {
+    size_t capacity, MemoryPool& memory_pool, Hasher hasher, EqualityComparator equality_comparator) {
   return HashSetWithArenaAllocator<T, Hasher, EqualityComparator>(
-      10, hasher, equality_comparator, ArenaAllocator<T>(memory_pool));
+      capacity, hasher, equality_comparator, ArenaAllocator<T>(memory_pool));
 }
 
 template <typename Key, typename Value>
@@ -62,8 +57,9 @@ inline HashMap<Key, Value> createHashMap(size_t capacity) {
 
 template <typename Key, typename Value>
 inline HashMapWithArenaAllocator<Key, Value> createHashMapWithArenaAllocator(
-    MemoryPool& memory_pool) {
+    std::size_t capacity, MemoryPool& memory_pool) {
   return createHashMapWithArenaAllocatorAndCustomFunctors<Key, Value>(
+      capacity,
       memory_pool,
       std::hash<Key>(),
       std::equal_to<Key>());
@@ -71,9 +67,9 @@ inline HashMapWithArenaAllocator<Key, Value> createHashMapWithArenaAllocator(
 
 template <typename Key, typename Value, typename Hasher, typename EqualityComparator>
 inline HashMapWithArenaAllocator<Key, Value, Hasher, EqualityComparator> createHashMapWithArenaAllocatorAndCustomFunctors(
-    MemoryPool& memory_pool, Hasher hasher, EqualityComparator equality_comparator) {
+    size_t capacity, MemoryPool& memory_pool, Hasher hasher, EqualityComparator equality_comparator) {
   return HashMapWithArenaAllocator<Key, Value, Hasher, EqualityComparator>(
-      10 /* capacity */, hasher, equality_comparator, ArenaAllocator<std::pair<const Key, Value>>(memory_pool));
+      capacity, hasher, equality_comparator, ArenaAllocator<std::pair<const Key, Value>>(memory_pool));
 }
 
 
diff --git a/include/fruit/impl/util/hash_helpers.h b/include/fruit/impl/util/hash_helpers.h
index 1e15156..ab49124 100644
--- a/include/fruit/impl/util/hash_helpers.h
+++ b/include/fruit/impl/util/hash_helpers.h
@@ -73,11 +73,12 @@ template <typename T>
 HashSet<T> createHashSet(size_t capacity);
 
 template <typename T>
-HashSetWithArenaAllocator<T> createHashSetWithArenaAllocator(size_t capacity, MemoryPool& memory_pool);
+HashSetWithArenaAllocator<T> createHashSetWithArenaAllocator(
+    size_t capacity, MemoryPool& memory_pool);
 
 template <typename T, typename Hasher, typename EqualityComparator>
 HashSetWithArenaAllocator<T, Hasher, EqualityComparator> createHashSetWithArenaAllocatorAndCustomFunctors(
-    MemoryPool& memory_pool, Hasher, EqualityComparator);
+    size_t capacity, MemoryPool& memory_pool, Hasher, EqualityComparator);
 
 template <typename Key, typename Value>
 HashMap<Key, Value> createHashMap();
@@ -86,11 +87,12 @@ template <typename Key, typename Value>
 HashMap<Key, Value> createHashMap(size_t capacity);
 
 template <typename Key, typename Value>
-HashMapWithArenaAllocator<Key, Value> createHashMapWithArenaAllocator(MemoryPool& memory_pool);
+HashMapWithArenaAllocator<Key, Value> createHashMapWithArenaAllocator(
+    size_t capacity, MemoryPool& memory_pool);
 
 template <typename Key, typename Value, typename Hasher, typename EqualityComparator>
 HashMapWithArenaAllocator<Key, Value, Hasher, EqualityComparator> createHashMapWithArenaAllocatorAndCustomFunctors(
-    MemoryPool& memory_pool, Hasher, EqualityComparator);
+    size_t capacity, MemoryPool& memory_pool, Hasher, EqualityComparator);
 
 } // namespace impl
 } // namespace fruit