refactor(interpreter-rete): recipe hashing

Use isomorphism-aware hashing to speed up RecipeRecognizer.

Due to possibly cyclic (recursive) recipes, we can't recursively turn recipes
into a canonical form. Recipes referring to already canonical (non-recurisve, or
recursive and entirely canonicalized) recipes can be hashed, while recursive
recipes in the middle of caninicalization still have to be compared more slowly
by their contents.

To keep the list of recipes compared by contents small, recipes are assigned a
hash code whenever possible.

We keep the equivalence class IDs for recipes, as there might be hash code
clashes, as well as recursive recipes that only later get assigned a hash code.

Also fixes a concurrency problem with equivalence class IDs by using an
AtomicLong.

Also reworks recipe instantiation, as now recipes might be canonicalized before
they are instantiated.

4 files changed, 338 insertions, 220 deletions

diff --git a/subprojects/interpreter-rete-recipes/src/main/java/tools/refinery/interpreter/rete/recipes/helper/RecipeRecognizer.java b/subprojects/interpreter-rete-recipes/src/main/java/tools/refinery/interpreter/rete/recipes/helper/RecipeRecognizer.java
index ed551b6e..ad203316 100644
--- a/subprojects/interpreter-rete-recipes/src/main/java/tools/refinery/interpreter/rete/recipes/helper/RecipeRecognizer.java
+++ b/subprojects/interpreter-rete-recipes/src/main/java/tools/refinery/interpreter/rete/recipes/helper/RecipeRecognizer.java
@@ -1,5 +1,6 @@
 /*******************************************************************************
  * Copyright (c) 2010-2016, Gabor Bergmann, Istvan Rath and Daniel Varro
+ * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
  * This program and the accompanying materials are made available under the
  * terms of the Eclipse Public License v. 2.0 which is available at
  * http://www.eclipse.org/legal/epl-v20.html.
@@ -9,16 +10,15 @@
 package tools.refinery.interpreter.rete.recipes.helper;
 
 import org.eclipse.emf.common.util.EList;
-import org.eclipse.emf.ecore.EAttribute;
-import org.eclipse.emf.ecore.EClass;
-import org.eclipse.emf.ecore.EObject;
-import org.eclipse.emf.ecore.EStructuralFeature;
+import org.eclipse.emf.ecore.*;
 import org.eclipse.emf.ecore.util.EcoreUtil;
+import org.jetbrains.annotations.Nullable;
 import tools.refinery.interpreter.rete.recipes.RecipesPackage;
 import tools.refinery.interpreter.rete.recipes.ReteNodeRecipe;
 import tools.refinery.interpreter.matchers.context.IQueryRuntimeContext;
 
 import java.util.*;
+import java.util.concurrent.atomic.AtomicLong;
 
 /**
  * Stores a set of known <em>canonical</em> recipes, each representing a disjoint equivalence class of recipes, modulo
@@ -26,179 +26,312 @@ import java.util.*;
  *
  * @author Gabor Bergmann
  * @since 1.3
- *
  */
 public class RecipeRecognizer {
-    private static long nextRecipeEquivalenceClassID = 0;
-
-    /**
-     * if EcoreUtil.equals(recipe1, recipe2), only one of them will be included here
-     */
-    Map<EClass, Set<ReteNodeRecipe>> canonicalRecipesByClass = new HashMap<>();
-    Map<Long, ReteNodeRecipe> canonicalRecipeByEquivalenceClassID = new HashMap<>();
-
-    private IQueryRuntimeContext runtimeContext;
-
-    /**
-     * @param can be null; if provided, further equivalences can be detected based on {@link IQueryRuntimeContext#wrapElement(Object)}
-     * @since 1.6
-     */
-    public RecipeRecognizer(IQueryRuntimeContext runtimeContext) {
-        this.runtimeContext = runtimeContext;
-    }
-    public RecipeRecognizer() {
-        this(null);
-    }
-
-    /**
-     * Recognizes when an equivalent canonical recipe is already known.
-     *
-     * @return an equivalent canonical recipe, or the null if no known equivalent found
-     */
-    public ReteNodeRecipe peekCanonicalRecipe(final ReteNodeRecipe recipe) {
-        // equivalence class already known
-        for (Long classID : recipe.getEquivalenceClassIDs()) {
-            ReteNodeRecipe knownRecipe = canonicalRecipeByEquivalenceClassID.get(classID);
-            if (knownRecipe != null)
-                return knownRecipe;
-        }
-
-        // equivalence class not known, but maybe equivalent recipe still
-        // available
-        Collection<ReteNodeRecipe> sameClassRecipes = getSameClassCanonicalRecipes(recipe);
-        for (ReteNodeRecipe knownRecipe : sameClassRecipes) {
-            if (isEquivalentRecipe(recipe, knownRecipe)) {
-                // FOUND EQUIVALENT RECIPE
-                recipe.getEquivalenceClassIDs().add(knownRecipe.getEquivalenceClassIDs().get(0));
-                return knownRecipe;
-            }
-        }
-
-        return null;
-    }
-
-    /**
-     * This recipe will be remembered as a canonical recipe. Method maintains both internal data structures and the
-     * equivalence class attribute of the recipe. PRECONDITION: {@link #peekCanonicalRecipe(ReteNodeRecipe)} must return
-     * null or the recipe itself
-     */
-    public void makeCanonical(final ReteNodeRecipe recipe) {
-        // this is a canonical recipe, chosen representative of its new
-        // equivalence class
-        if (recipe.getEquivalenceClassIDs().isEmpty()) {
-            recipe.getEquivalenceClassIDs().add(nextRecipeEquivalenceClassID++);
-        }
-        for (Long classID : recipe.getEquivalenceClassIDs()) {
-            canonicalRecipeByEquivalenceClassID.put(classID, recipe);
-        }
-        getSameClassCanonicalRecipes(recipe).add(recipe);
-    }
-
-    /**
-     * Ensures that there is an equivalent canonical recipe; if none is known yet, this recipe will be remembered as
-     * canonical.
-     *
-     * @return an equivalent canonical recipe; the argument recipe itself (which is made canonical) if no known
-     *         equivalent found
-     */
-    public ReteNodeRecipe canonicalizeRecipe(final ReteNodeRecipe recipe) {
-        ReteNodeRecipe knownRecipe = peekCanonicalRecipe(recipe);
-        if (knownRecipe == null) {
-            knownRecipe = recipe;
-            makeCanonical(recipe);
-        }
-        return knownRecipe;
-    }
-
-    /**
-     * @return true iff recipe is a canonical recipe
-     */
-    public boolean isKnownCanonicalRecipe(final ReteNodeRecipe recipe) {
-        if (recipe.getEquivalenceClassIDs().isEmpty()) {
-            return false;
-        }
-        ReteNodeRecipe knownRecipe = canonicalRecipeByEquivalenceClassID.get(recipe.getEquivalenceClassIDs().get(0));
-        return recipe == knownRecipe;
-    }
-
-    private Set<ReteNodeRecipe> getSameClassCanonicalRecipes(final ReteNodeRecipe recipe) {
-        Set<ReteNodeRecipe> sameClassRecipes = canonicalRecipesByClass.get(recipe.eClass());
-        if (sameClassRecipes == null) {
-            sameClassRecipes = new HashSet<>();
-            canonicalRecipesByClass.put(recipe.eClass(), sameClassRecipes);
-        }
-        return sameClassRecipes;
-    }
-
-    private boolean isEquivalentRecipe(ReteNodeRecipe recipe, ReteNodeRecipe knownRecipe) {
-        return new EqualityHelper(runtimeContext).equals(recipe, knownRecipe);
-    }
-
-    // TODO reuse in more cases later, e.g. switching join node parents, etc.
-    private static class EqualityHelper extends EcoreUtil.EqualityHelper {
-
-
-
-
-        private static final long serialVersionUID = -8841971394686015188L;
-
-        private static final EAttribute RETE_NODE_RECIPE_EQUIVALENCE_CLASS_IDS =
-                RecipesPackage.eINSTANCE.getReteNodeRecipe_EquivalenceClassIDs();
-        private static final EAttribute CONSTANT_RECIPE_CONSTANT_VALUES =
-                RecipesPackage.eINSTANCE.getConstantRecipe_ConstantValues();
-        private static final EAttribute DISCRIMINATOR_BUCKET_RECIPE_BUCKET_KEY =
-                RecipesPackage.eINSTANCE.getDiscriminatorBucketRecipe_BucketKey();
-
-        private IQueryRuntimeContext runtimeContext;
-
-        public EqualityHelper(IQueryRuntimeContext runtimeContext) {
-            this.runtimeContext = runtimeContext;
-        }
-
-        @Override
-        protected boolean haveEqualFeature(EObject eObject1, EObject eObject2, EStructuralFeature feature) {
-            // ignore differences in this attribute, as it may only be assigned
-            // after the equivalence check
-            if (RETE_NODE_RECIPE_EQUIVALENCE_CLASS_IDS.equals(feature))
-                return true;
-
-            if (runtimeContext != null) {
-                // constant values
-                if (/*CONSTANT_RECIPE_CONSTANT_VALUES.equals(feature) ||*/ DISCRIMINATOR_BUCKET_RECIPE_BUCKET_KEY.equals(feature)) {
-                    // use runtime context to map to canonical wrapped form
-                    // this is costly for constant recipes (TODO improve this), but essential for discriminator buckets
-
-                    Object val1 = eObject1.eGet(feature);
-                    Object val2 = eObject2.eGet(feature);
-
-                    if (val1 != null && val2 != null) {
-                        return runtimeContext.wrapElement(val1).equals(runtimeContext.wrapElement(val2));
-                    } else {
-                        return val1 == null && val2 == null;
-                    }
-
-                }
-            }
-
-            // fallback to general comparison
-            return super.haveEqualFeature(eObject1, eObject2, feature);
-        }
-
-        @Override
-        public boolean equals(EObject eObject1, EObject eObject2) {
-            // short-circuit if already known to be equivalent
-            if (eObject1 instanceof ReteNodeRecipe) {
-                if (eObject2 instanceof ReteNodeRecipe) {
-                    EList<Long> eqClassIDs1 = ((ReteNodeRecipe) eObject1).getEquivalenceClassIDs();
-                    EList<Long> eqClassIDs2 = ((ReteNodeRecipe) eObject2).getEquivalenceClassIDs();
-
-                    if (!Collections.disjoint(eqClassIDs1, eqClassIDs2))
-                        return true;
-                }
-            }
-
-            // fallback to general comparison
-            return super.equals(eObject1, eObject2);
-        }
-    }
+        private static final AtomicLong nextRecipeEquivalenceClassID = new AtomicLong(0);
+
+        /**
+         * if EcoreUtil.equals(recipe1, recipe2), only one of them will be included here
+         */
+        Map<Long, Set<ReteNodeRecipe>> canonicalRecipesByHashCode = new HashMap<>();
+        Map<Long, ReteNodeRecipe> canonicalRecipeByEquivalenceClassID = new HashMap<>();
+        Set<ReteNodeRecipe> canonicalRecipesWithoutHashCode = new LinkedHashSet<>();
+
+        private final IQueryRuntimeContext runtimeContext;
+
+        /**
+         * @param runtimeContext can be null; if provided, further equivalences can be detected based on
+         *                       {@link IQueryRuntimeContext#wrapElement(Object)}
+         * @since 1.6
+         */
+        public RecipeRecognizer(IQueryRuntimeContext runtimeContext) {
+                this.runtimeContext = runtimeContext;
+        }
+
+        public RecipeRecognizer() {
+                this(null);
+        }
+
+        /**
+         * Recognizes when an equivalent canonical recipe is already known.
+         *
+         * @return an equivalent canonical recipe, or the null if no known equivalent found
+         */
+        public ReteNodeRecipe peekCanonicalRecipe(final ReteNodeRecipe recipe) {
+                var recipeByEquivalenceClass = getRecipeByEquivalenceClass(recipe);
+                if (recipeByEquivalenceClass != null) {
+                        return recipeByEquivalenceClass;
+                }
+
+                var hashCode = computeHashCode(recipe);
+                if (hashCode != null) {
+                        var recipeByHashCode = getRecipeByHashCode(recipe, hashCode);
+                        if (recipeByHashCode != null) {
+                                return recipeByHashCode;
+                        }
+                }
+
+                // If we already designated {@code recipe} as canonical during a recursive call in {@code computeHashCode},
+                // it will be found here, and we will move it to {@code canonicalRecipesByHashCode}. This could be improved by
+                // checking whether {@code recipe} is already canonical explicitly if there are many recursive patterns.
+                return getRecipeAndAssignHashCode(recipe, hashCode);
+        }
+
+        @Nullable
+        private ReteNodeRecipe getRecipeByEquivalenceClass(ReteNodeRecipe recipe) {
+                for (Long classID : recipe.getEquivalenceClassIDs()) {
+                        ReteNodeRecipe knownRecipe = canonicalRecipeByEquivalenceClassID.get(classID);
+                        if (knownRecipe != null) {
+                                return knownRecipe;
+                        }
+                }
+                return null;
+        }
+
+        @Nullable
+        private ReteNodeRecipe getRecipeByHashCode(ReteNodeRecipe recipe, Long hashCode) {
+                var equivalentRecipesByHashCode = canonicalRecipesByHashCode.get(hashCode);
+                if (equivalentRecipesByHashCode != null) {
+                        for (ReteNodeRecipe knownRecipe : equivalentRecipesByHashCode) {
+                                if (isEquivalentRecipe(recipe, knownRecipe)) {
+                                        // FOUND EQUIVALENT RECIPE
+                                        recipe.getEquivalenceClassIDs().add(knownRecipe.getEquivalenceClassIDs().get(0));
+                                        return knownRecipe;
+                                }
+                        }
+                }
+                return null;
+        }
+
+        @Nullable
+        private ReteNodeRecipe getRecipeAndAssignHashCode(ReteNodeRecipe recipe, Long hashCode) {
+                var iterator = canonicalRecipesWithoutHashCode.iterator();
+                while (iterator.hasNext()) {
+                        var knownRecipe = iterator.next();
+                        if (isEquivalentRecipe(recipe, knownRecipe)) {
+                                // FOUND EQUIVALENT RECIPE
+                                recipe.getEquivalenceClassIDs().add(knownRecipe.getEquivalenceClassIDs().get(0));
+                                var cachedHashCode = knownRecipe.getCachedHashCode();
+                                if (cachedHashCode != null && !cachedHashCode.equals(hashCode)) {
+                                        throw new AssertionError("Cached recipe %s already had hash code %s"
+                                                        .formatted(knownRecipe, cachedHashCode));
+                                }
+                                if (hashCode != null) {
+                                        knownRecipe.setCachedHashCode(hashCode);
+                                        addHashCodeRepresentative(hashCode, knownRecipe);
+                                        iterator.remove();
+                                }
+                                return knownRecipe;
+                        }
+                }
+                return null;
+        }
+
+        private final Deque<EObject> hashCodeStack = new ArrayDeque<>();
+
+        private Long computeHashCode(Object object) {
+                if (object instanceof List<?> list) {
+                        return computeListHashCode(list);
+                }
+                if (object instanceof ReteNodeRecipe recipe) {
+                        return ensureRecipeHashCode(recipe);
+                }
+                if (object instanceof EObject eObject) {
+                        return computeEObjectHashCode(eObject);
+                }
+                return (long) Objects.hashCode(object);
+        }
+
+        private Long computeHashCodeOrEquivalenceClassId(Object object) {
+                if (object instanceof ReteNodeRecipe recipe) {
+                        var equivalenceClassIDs = recipe.getEquivalenceClassIDs();
+                        if (!equivalenceClassIDs.isEmpty()) {
+                                return equivalenceClassIDs.get(0);
+                        }
+                        if (hashCodeStack.contains(recipe)) {
+                                return null;
+                        }
+                        var canonicalRecipe = canonicalizeRecipe(recipe);
+                        return canonicalRecipe.getEquivalenceClassIDs().get(0);
+                } else {
+                        return computeHashCode(object);
+                }
+        }
+
+        private Long computeListHashCode(List<?> list) {
+                long result = 1;
+                for (var item : list) {
+                        var update = computeHashCodeOrEquivalenceClassId(item);
+                        if (update == null) {
+                                return null;
+                        }
+                        result = result * 37 + update;
+                }
+                return result;
+        }
+
+        private Long ensureRecipeHashCode(ReteNodeRecipe recipe) {
+                var hashCode = recipe.getCachedHashCode();
+                if (hashCode != null) {
+                        return hashCode;
+                }
+                hashCode = computeEObjectHashCode(recipe);
+                if (hashCode == null) {
+                        return null;
+                }
+                recipe.setCachedHashCode(hashCode);
+                return hashCode;
+        }
+
+        private Long computeEObjectHashCode(EObject eObject) {
+                if (hashCodeStack.contains(eObject)) {
+                        return null;
+                }
+                hashCodeStack.addLast(eObject);
+                try {
+                        long result = eObject.eClass().hashCode();
+                        for (var feature : eObject.eClass().getEAllStructuralFeatures()) {
+                                if (eObject instanceof ReteNodeRecipe && (
+                                                RecipesPackage.Literals.RETE_NODE_RECIPE__EQUIVALENCE_CLASS_IDS.equals(feature) ||
+                                                                RecipesPackage.Literals.RETE_NODE_RECIPE__CACHED_HASH_CODE.equals(feature) ||
+                                                                RecipesPackage.Literals.RETE_NODE_RECIPE__CONSTRUCTED.equals(feature))) {
+                                        continue;
+                                }
+                                var value = eObject.eGet(feature);
+                                var update = computeHashCodeOrEquivalenceClassId(value);
+                                if (update == null) {
+                                        return null;
+                                }
+                                result = result * 37 + update;
+                        }
+                        return result;
+                } finally {
+                        hashCodeStack.removeLast();
+                }
+        }
+
+        private void addHashCodeRepresentative(Long hashCode, ReteNodeRecipe recipe) {
+                canonicalRecipesByHashCode.computeIfAbsent(hashCode, ignored -> new LinkedHashSet<>()).add(recipe);
+        }
+
+        /**
+         * This recipe will be remembered as a canonical recipe. Method maintains both internal data structures and the
+         * equivalence class attribute of the recipe. PRECONDITION: {@link #peekCanonicalRecipe(ReteNodeRecipe)} must
+         * return null or the recipe itself
+         */
+        public void makeCanonical(final ReteNodeRecipe recipe) {
+                // this is a canonical recipe, chosen representative of its new
+                // equivalence class
+                if (recipe.getEquivalenceClassIDs().isEmpty()) {
+                        recipe.getEquivalenceClassIDs().add(nextRecipeEquivalenceClassID.getAndIncrement());
+                }
+                for (Long classID : recipe.getEquivalenceClassIDs()) {
+                        canonicalRecipeByEquivalenceClassID.put(classID, recipe);
+                }
+                var hashCode = computeHashCode(recipe);
+                if (hashCode == null) {
+                        canonicalRecipesWithoutHashCode.add(recipe);
+                } else {
+                        addHashCodeRepresentative(hashCode, recipe);
+                }
+        }
+
+        /**
+         * Ensures that there is an equivalent canonical recipe; if none is known yet, this recipe will be remembered as
+         * canonical.
+         *
+         * @return an equivalent canonical recipe; the argument recipe itself (which is made canonical) if no known
+         * equivalent found
+         */
+        public ReteNodeRecipe canonicalizeRecipe(final ReteNodeRecipe recipe) {
+                ReteNodeRecipe knownRecipe = peekCanonicalRecipe(recipe);
+                if (knownRecipe == null) {
+                        knownRecipe = recipe;
+                        makeCanonical(recipe);
+                }
+                return knownRecipe;
+        }
+
+        /**
+         * @return true iff recipe is a canonical recipe
+         */
+        public boolean isKnownCanonicalRecipe(final ReteNodeRecipe recipe) {
+                if (recipe.getEquivalenceClassIDs().isEmpty()) {
+                        return false;
+                }
+                ReteNodeRecipe knownRecipe = canonicalRecipeByEquivalenceClassID.get(recipe.getEquivalenceClassIDs().get(0));
+                return recipe == knownRecipe;
+        }
+
+        private boolean isEquivalentRecipe(ReteNodeRecipe recipe, ReteNodeRecipe knownRecipe) {
+                return new EqualityHelper(runtimeContext).equals(recipe, knownRecipe);
+        }
+
+        // TODO reuse in more cases later, e.g. switching join node parents, etc.
+        private static class EqualityHelper extends EcoreUtil.EqualityHelper {
+                private static final long serialVersionUID = -8841971394686015188L;
+
+                private static final EAttribute RETE_NODE_RECIPE_EQUIVALENCE_CLASS_IDS =
+                                RecipesPackage.eINSTANCE.getReteNodeRecipe_EquivalenceClassIDs();
+                private static final EAttribute RETE_NODE_RECIPE_CACHED_HASH_CODE =
+                                RecipesPackage.eINSTANCE.getReteNodeRecipe_CachedHashCode();
+                private static final EAttribute RETE_NODE_RECIPE_CONSTRUCTED =
+                                RecipesPackage.eINSTANCE.getReteNodeRecipe_Constructed();
+                private static final EAttribute DISCRIMINATOR_BUCKET_RECIPE_BUCKET_KEY =
+                                RecipesPackage.eINSTANCE.getDiscriminatorBucketRecipe_BucketKey();
+
+                private final IQueryRuntimeContext runtimeContext;
+
+                public EqualityHelper(IQueryRuntimeContext runtimeContext) {
+                        this.runtimeContext = runtimeContext;
+                }
+
+                @Override
+                protected boolean haveEqualFeature(EObject eObject1, EObject eObject2, EStructuralFeature feature) {
+                        // ignore differences in this attribute, as it may only be assigned
+                        // after the equivalence check
+                        if (RETE_NODE_RECIPE_EQUIVALENCE_CLASS_IDS.equals(feature) ||
+                                        RETE_NODE_RECIPE_CACHED_HASH_CODE.equals(feature) ||
+                                        RETE_NODE_RECIPE_CONSTRUCTED.equals(feature))
+                                return true;
+
+                        if (runtimeContext != null) {
+                                // constant values
+                                if (DISCRIMINATOR_BUCKET_RECIPE_BUCKET_KEY.equals(feature)) {
+                                        // use runtime context to map to canonical wrapped form
+                                        // this is costly for constant recipes (TODO improve this), but essential for discriminator buckets
+
+                                        Object val1 = eObject1.eGet(feature);
+                                        Object val2 = eObject2.eGet(feature);
+
+                                        if (val1 != null && val2 != null) {
+                                                return runtimeContext.wrapElement(val1).equals(runtimeContext.wrapElement(val2));
+                                        } else {
+                                                return val1 == null && val2 == null;
+                                        }
+
+                                }
+                        }
+
+                        // fallback to general comparison
+                        return super.haveEqualFeature(eObject1, eObject2, feature);
+                }
+
+                @Override
+                public boolean equals(EObject eObject1, EObject eObject2) {
+                        // short-circuit if already known to be equivalent
+                        if (eObject1 instanceof ReteNodeRecipe) {
+                                if (eObject2 instanceof ReteNodeRecipe) {
+                                        EList<Long> eqClassIDs1 = ((ReteNodeRecipe) eObject1).getEquivalenceClassIDs();
+                                        EList<Long> eqClassIDs2 = ((ReteNodeRecipe) eObject2).getEquivalenceClassIDs();
+
+                                        if (!Collections.disjoint(eqClassIDs1, eqClassIDs2))
+                                                return true;
+                                }
+                        }
+
+                        // fallback to general comparison
+                        return super.equals(eObject1, eObject2);
+                }
+        }
 }
diff --git a/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore b/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore
index a4617833..6b8f10ea 100644
--- a/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore
+++ b/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore
@@ -31,6 +31,8 @@
         <details key="documentation" value="If two recipes were found equivalent, a matching equivalence ID can be assigned to them by {@link RecipeRecognizer}. &#xD;&#xA;If two recipes share (at least one) equivalence ID, they are known to be equivalent.&#xD;&#xA;&#xD;&#xA;&lt;p>&#xD;&#xA;A difference in this attribute only does not preclude two recipe elements to be considered equal. &#xD;&#xA;If they are shown to be equivalent using deeper analysis, equivalence ids can be set so that the equivalence is recognized more easily the next time.&#xD;&#xA;&#xD;&#xA;@since 1.3"/>
       </eAnnotations>
     </eStructuralFeatures>
+    <eStructuralFeatures xsi:type="ecore:EAttribute" name="cachedHashCode" eType="ecore:EDataType http://www.eclipse.org/emf/2002/Ecore#//ELongObject"/>
+    <eStructuralFeatures xsi:type="ecore:EAttribute" name="constructed" eType="ecore:EDataType http://www.eclipse.org/emf/2002/Ecore#//EBoolean"/>
   </eClassifiers>
   <eClassifiers xsi:type="ecore:EClass" name="SingleParentNodeRecipe" abstract="true"
       eSuperTypes="#//ReteNodeRecipe">
diff --git a/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel b/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel
index 89ff6e3a..f7dc7a4e 100644
--- a/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel
+++ b/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel
@@ -2,10 +2,11 @@
 <genmodel:GenModel xmi:version="2.0" xmlns:xmi="http://www.omg.org/XMI" xmlns:ecore="http://www.eclipse.org/emf/2002/Ecore"
     xmlns:genmodel="http://www.eclipse.org/emf/2002/GenModel" copyrightText="Copyright (c) 2004-2014 Gabor Bergmann and Daniel Varro&#xA;Copyright (c) 2023 The Refinery Authors &lt;https://refinery.tools>&#xA;This program and the accompanying materials are made available under the&#xA;terms of the Eclipse Public License v. 2.0 which is available at&#xA;http://www.eclipse.org/legal/epl-v20.html.&#xA;&#xA;SPDX-License-Identifier: EPL-2.0"
     modelDirectory="/tools.refinery.refinery-interpreter-rete-recipes/src/main/emf-gen"
-    modelPluginID="tools.refinery.refinery-interpreter-rete-recipes" runtimeJar="true" forceOverwrite="true"
-    modelName="Rete-recipes" updateClasspath="false" nonNLSMarkers="true" rootExtendsClass="org.eclipse.emf.ecore.impl.MinimalEObjectImpl$Container"
-    testsDirectory="" importerID="org.eclipse.emf.importer.ecore" containmentProxies="true"
-    complianceLevel="7.0" language="en" operationReflection="true">
+    modelPluginID="tools.refinery.refinery-interpreter-rete-recipes" runtimeJar="true"
+    forceOverwrite="true" modelName="Rete-recipes" updateClasspath="false" nonNLSMarkers="true"
+    rootExtendsClass="org.eclipse.emf.ecore.impl.MinimalEObjectImpl$Container" testsDirectory=""
+    importerID="org.eclipse.emf.importer.ecore" containmentProxies="true" complianceLevel="7.0"
+    language="en" operationReflection="true">
   <genAnnotations source="http://www.eclipse.org/emf/2002/GenModel/exporter/org.eclipse.xsd.ecore.exporter">
     <genAnnotations source="selectedPackages">
       <details key="http://www.eclipse.org/emf/2002/Ecore" value="Ecore.xsd"/>
@@ -32,6 +33,8 @@
     <genClasses image="false" ecoreClass="recipes.ecore#//ReteNodeRecipe">
       <genFeatures createChild="false" ecoreFeature="ecore:EAttribute recipes.ecore#//ReteNodeRecipe/traceInfo"/>
       <genFeatures createChild="false" ecoreFeature="ecore:EAttribute recipes.ecore#//ReteNodeRecipe/equivalenceClassIDs"/>
+      <genFeatures createChild="false" ecoreFeature="ecore:EAttribute recipes.ecore#//ReteNodeRecipe/cachedHashCode"/>
+      <genFeatures createChild="false" ecoreFeature="ecore:EAttribute recipes.ecore#//ReteNodeRecipe/constructed"/>
       <genOperations ecoreOperation="recipes.ecore#//ReteNodeRecipe/getArity" body="throw new &lt;%java.lang.UnsupportedOperationException%>();"/>
     </genClasses>
     <genClasses image="false" ecoreClass="recipes.ecore#//SingleParentNodeRecipe">
diff --git a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/NodeProvisioner.java b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/NodeProvisioner.java
index 0a68f449..e7901822 100644
--- a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/NodeProvisioner.java
+++ b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/NodeProvisioner.java
@@ -1,5 +1,6 @@
 /*******************************************************************************
  * Copyright (c) 2004-2008 Gabor Bergmann and Daniel Varro
+ * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
  * This program and the accompanying materials are made available under the
  * terms of the Eclipse Public License v. 2.0 which is available at
  * http://www.eclipse.org/legal/epl-v20.html.
@@ -74,49 +75,28 @@ public class NodeProvisioner {
     public synchronized Address<? extends Node> getOrCreateNodeByRecipe(RecipeTraceInfo recipeTrace) {
         ReteNodeRecipe recipe = recipeTrace.getRecipe();
         Address<? extends Node> result = getNodesByRecipe().get(recipe);
-        if (result != null) {
-            // NODE ALREADY CONSTRUCTED FOR RECIPE, only needs to add trace
-            if (getRecipeTraces().add(recipeTrace))
-                result.getNodeCache().assignTraceInfo(recipeTrace);
-        } else {
+        if (result == null) {
             // No node for this recipe object - but equivalent recipes still
             // reusable
             ReteNodeRecipe canonicalRecipe = recognizer.canonicalizeRecipe(recipe);
-            if (canonicalRecipe != recipe) {
-                // FOUND EQUIVALENT RECIPE
-                result = getNodesByRecipe().get(canonicalRecipe);
-                if (result != null) {
-                    // NODE ALREADY CONSTRUCTED FOR EQUIVALENT RECIPE
-                    recipeTrace.shadowWithEquivalentRecipe(canonicalRecipe);
-                    getNodesByRecipe().put(recipe, result);
-                    if (getRecipeTraces().add(recipeTrace))
-                        result.getNodeCache().assignTraceInfo(recipeTrace);
-                    // Bug 491922: ensure that recipe shadowing propagates to
-                    // parent traces
-                    // note that if equivalentRecipes() becomes more
-                    // sophisticated
-                    // and considers recipes with different parents, this might
-                    // have to be changed
-                    ensureParents(recipeTrace);
-                } else {
-                    // CONSTRUCTION IN PROGRESS FOR EQUIVALENT RECIPE
-                    if (recipe instanceof IndexerRecipe) {
-                        // this is allowed for indexers;
-                        // go on with the construction, as the same indexer node
-                        // will be obtained anyways
-                    } else {
-                        throw new IllegalStateException(
-                                "This should not happen: " + "non-indexer nodes are are supposed to be constructed "
-                                        + "as soon as they are designated as canonical recipes");
-                    }
-                }
-            }
-            if (result == null) {
-                // MUST INSTANTIATE NEW NODE FOR RECIPE
-                final Node freshNode = instantiateNodeForRecipe(recipeTrace, recipe);
-                result = reteContainer.makeAddress(freshNode);
-            }
+                        result = getNodesByRecipe().get(canonicalRecipe);
+                        if (result == null) {
+                                if (canonicalRecipe.isConstructed()) {
+                                        throw new IllegalStateException(
+                                                        "Already constructed node is missing for canonical recipe " + canonicalRecipe);
+                                }
+                                canonicalRecipe.setConstructed(true);
+                                final Node freshNode = instantiateNodeForRecipe(recipeTrace, canonicalRecipe);
+                                result = reteContainer.makeAddress(freshNode);
+                        }
+                        if (canonicalRecipe != recipe) {
+                                recipeTrace.shadowWithEquivalentRecipe(canonicalRecipe);
+                                getNodesByRecipe().put(recipe, result);
+                        }
         }
+                if (getRecipeTraces().add(recipeTrace)) {
+                        result.getNodeCache().assignTraceInfo(recipeTrace);
+                }
         return result;
     }