]> git.lizzy.rs Git - minetest.git/blobdiff - src/craftdef.cpp
Report collisionMoveSimple for client and server. (#13105)
[minetest.git] / src / craftdef.cpp
index 143c295f59e22cf18862dd19e48995f6ff9daeac..eb703fdbee4251fad6ffc5b5a7663ae8adb7bf81 100644 (file)
@@ -1,6 +1,6 @@
 /*
 Minetest
-Copyright (C) 2011 celeron55, Perttu Ahola <celeron55@gmail.com>
+Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>
 
 This program is free software; you can redistribute it and/or modify
 it under the terms of the GNU Lesser General Public License as published by
@@ -22,12 +22,62 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include "irrlichttypes.h"
 #include "log.h"
 #include <sstream>
-#include <set>
+#include <unordered_set>
 #include <algorithm>
 #include "gamedef.h"
 #include "inventory.h"
 #include "util/serialize.h"
-#include "strfnd.h"
+#include "util/string.h"
+#include "util/numeric.h"
+#include "util/strfnd.h"
+#include "exceptions.h"
+
+inline bool isGroupRecipeStr(const std::string &rec_name)
+{
+       return str_starts_with(rec_name, std::string("group:"));
+}
+
+static bool hasGroupItem(const std::vector<std::string> &recipe)
+{
+       for (const auto &item : recipe) {
+               if (isGroupRecipeStr(item))
+                       return true;
+       }
+       return false;
+}
+
+inline u64 getHashForString(const std::string &recipe_str)
+{
+       /*errorstream << "Hashing craft string  \"" << recipe_str << '"';*/
+       return murmur_hash_64_ua(recipe_str.data(), recipe_str.length(), 0xdeadbeef);
+}
+
+static u64 getHashForGrid(CraftHashType type, const std::vector<std::string> &grid_names)
+{
+       switch (type) {
+               case CRAFT_HASH_TYPE_ITEM_NAMES: {
+                       std::ostringstream os;
+                       bool is_first = true;
+                       for (const std::string &grid_name : grid_names) {
+                               if (!grid_name.empty()) {
+                                       os << (is_first ? "" : "\n") << grid_name;
+                                       is_first = false;
+                               }
+                       }
+                       return getHashForString(os.str());
+               } case CRAFT_HASH_TYPE_COUNT: {
+                       u64 cnt = 0;
+                       for (const std::string &grid_name : grid_names)
+                               if (!grid_name.empty())
+                                       cnt++;
+                       return cnt;
+               } case CRAFT_HASH_TYPE_UNHASHED:
+                       return 0;
+       }
+       // invalid CraftHashType
+       assert(false);
+       return 0;
+}
 
 // Check if input matches recipe
 // Takes recipe groups into account
@@ -35,22 +85,22 @@ static bool inputItemMatchesRecipe(const std::string &inp_name,
                const std::string &rec_name, IItemDefManager *idef)
 {
        // Exact name
-       if(inp_name == rec_name)
+       if (inp_name == rec_name)
                return true;
 
        // Group
-       if(rec_name.substr(0,6) == "group:" && idef->isKnown(inp_name)){
+       if (isGroupRecipeStr(rec_name) && idef->isKnown(inp_name)) {
                const struct ItemDefinition &def = idef->get(inp_name);
                Strfnd f(rec_name.substr(6));
                bool all_groups_match = true;
-               do{
+               do {
                        std::string check_group = f.next(",");
-                       if(itemgroup_get(def.groups, check_group) == 0){
+                       if (itemgroup_get(def.groups, check_group) == 0) {
                                all_groups_match = false;
                                break;
                        }
-               }while(!f.atend());
-               if(all_groups_match)
+               } while (!f.at_end());
+               if (all_groups_match)
                        return true;
        }
 
@@ -71,11 +121,9 @@ static std::vector<std::string> craftGetItemNames(
                const std::vector<std::string> &itemstrings, IGameDef *gamedef)
 {
        std::vector<std::string> result;
-       for(std::vector<std::string>::const_iterator
-                       i = itemstrings.begin();
-                       i != itemstrings.end(); i++)
-       {
-               result.push_back(craftGetItemName(*i, gamedef));
+       result.reserve(itemstrings.size());
+       for (const auto &itemstring : itemstrings) {
+               result.push_back(craftGetItemName(itemstring, gamedef));
        }
        return result;
 }
@@ -85,11 +133,9 @@ static std::vector<std::string> craftGetItemNames(
                const std::vector<ItemStack> &items, IGameDef *gamedef)
 {
        std::vector<std::string> result;
-       for(std::vector<ItemStack>::const_iterator
-                       i = items.begin();
-                       i != items.end(); i++)
-       {
-               result.push_back(i->name);
+       result.reserve(items.size());
+       for (const auto &item : items) {
+               result.push_back(item.name);
        }
        return result;
 }
@@ -99,11 +145,10 @@ static std::vector<ItemStack> craftGetItems(
                const std::vector<std::string> &items, IGameDef *gamedef)
 {
        std::vector<ItemStack> result;
-       for(std::vector<std::string>::const_iterator
-                       i = items.begin();
-                       i != items.end(); i++)
-       {
-               result.push_back(ItemStack(std::string(*i),(u16)1,(u16)0,"",gamedef->getItemDefManager()));
+       result.reserve(items.size());
+       for (const auto &item : items) {
+               result.emplace_back(std::string(item), (u16)1,
+                       (u16)0, gamedef->getItemDefManager());
        }
        return result;
 }
@@ -117,32 +162,25 @@ static bool craftGetBounds(const std::vector<std::string> &items, unsigned int w
        bool success = false;
        unsigned int x = 0;
        unsigned int y = 0;
-       for(std::vector<std::string>::const_iterator
-                       i = items.begin();
-                       i != items.end(); i++)
-       {
-               if(*i != "")  // Is this an actual item?
-               {
-                       if(!success)
-                       {
+       for (const std::string &item : items) {
+               // Is this an actual item?
+               if (!item.empty()) {
+                       if (!success) {
                                // This is the first nonempty item
                                min_x = max_x = x;
                                min_y = max_y = y;
                                success = true;
-                       }
-                       else
-                       {
-                               if(x < min_x) min_x = x;
-                               if(x > max_x) max_x = x;
-                               if(y < min_y) min_y = y;
-                               if(y > max_y) max_y = y;
+                       } else {
+                               if (x < min_x) min_x = x;
+                               if (x > max_x) max_x = x;
+                               if (y < min_y) min_y = y;
+                               if (y > max_y) max_y = y;
                        }
                }
 
                // Step coordinate
                x++;
-               if(x == width)
-               {
+               if (x == width) {
                        x = 0;
                        y++;
                }
@@ -150,32 +188,12 @@ static bool craftGetBounds(const std::vector<std::string> &items, unsigned int w
        return success;
 }
 
-#if 0
-// This became useless when group support was added to shapeless recipes
-// Convert a list of item names to a multiset
-static std::multiset<std::string> craftMakeMultiset(const std::vector<std::string> &names)
-{
-       std::multiset<std::string> set;
-       for(std::vector<std::string>::const_iterator
-                       i = names.begin();
-                       i != names.end(); i++)
-       {
-               if(*i != "")
-                       set.insert(*i);
-       }
-       return set;
-}
-#endif
-
 // Removes 1 from each item stack
 static void craftDecrementInput(CraftInput &input, IGameDef *gamedef)
 {
-       for(std::vector<ItemStack>::iterator
-                       i = input.items.begin();
-                       i != input.items.end(); i++)
-       {
-               if(i->count != 0)
-                       i->remove(1);
+       for (auto &item : input.items) {
+               if (item.count != 0)
+                       item.remove(1);
        }
 }
 
@@ -183,11 +201,11 @@ static void craftDecrementInput(CraftInput &input, IGameDef *gamedef)
 // Example: if replacements contains the pair ("bucket:bucket_water", "bucket:bucket_empty"),
 //   a water bucket will not be removed but replaced by an empty bucket.
 static void craftDecrementOrReplaceInput(CraftInput &input,
+               std::vector<ItemStack> &output_replacements,
                const CraftReplacements &replacements,
                IGameDef *gamedef)
 {
-       if(replacements.pairs.empty())
-       {
+       if (replacements.pairs.empty()) {
                craftDecrementInput(input, gamedef);
                return;
        }
@@ -195,37 +213,31 @@ static void craftDecrementOrReplaceInput(CraftInput &input,
        // Make a copy of the replacements pair list
        std::vector<std::pair<std::string, std::string> > pairs = replacements.pairs;
 
-       for(std::vector<ItemStack>::iterator
-                       i = input.items.begin();
-                       i != input.items.end(); i++)
-       {
-               if(i->count == 1)
-               {
-                       // Find an appropriate replacement
-                       bool found_replacement = false;
-                       for(std::vector<std::pair<std::string, std::string> >::iterator
-                                       j = pairs.begin();
-                                       j != pairs.end(); j++)
-                       {
-                               ItemStack from_item;
-                               from_item.deSerialize(j->first, gamedef->idef());
-                               if(i->name == from_item.name)
-                               {
-                                       i->deSerialize(j->second, gamedef->idef());
+       for (auto &item : input.items) {
+               // Find an appropriate replacement
+               bool found_replacement = false;
+               for (auto j = pairs.begin(); j != pairs.end(); ++j) {
+                       if (inputItemMatchesRecipe(item.name, j->first, gamedef->idef())) {
+                               if (item.count == 1) {
+                                       item.deSerialize(j->second, gamedef->idef());
                                        found_replacement = true;
                                        pairs.erase(j);
                                        break;
                                }
+
+                               ItemStack rep;
+                               rep.deSerialize(j->second, gamedef->idef());
+                               item.remove(1);
+                               found_replacement = true;
+                               pairs.erase(j);
+                               output_replacements.push_back(rep);
+                               break;
+
                        }
-                       // No replacement was found, simply decrement count to zero
-                       if(!found_replacement)
-                               i->remove(1);
-               }
-               else if(i->count >= 2)
-               {
-                       // Ignore replacements for items with count >= 2
-                       i->remove(1);
                }
+               // No replacement was found, simply decrement count by one
+               if (!found_replacement && item.count > 0)
+                       item.remove(1);
        }
 }
 
@@ -234,24 +246,19 @@ static std::string craftDumpMatrix(const std::vector<std::string> &items,
                unsigned int width)
 {
        std::ostringstream os(std::ios::binary);
-       os<<"{ ";
+       os << "{ ";
        unsigned int x = 0;
-       for(std::vector<std::string>::const_iterator
-                       i = items.begin();
-                       i != items.end(); i++, x++)
-       {
-               if(x == width)
-               {
-                       os<<"; ";
+       for(std::vector<std::string>::size_type i = 0;
+                       i < items.size(); i++, x++) {
+               if (x == width) {
+                       os << "; ";
                        x = 0;
+               } else if (x != 0) {
+                       os << ",";
                }
-               else if(x != 0)
-               {
-                       os<<",";
-               }
-               os<<"\""<<(*i)<<"\"";
+               os << '"' << items[i] << '"';
        }
-       os<<" }";
+       os << " }";
        return os.str();
 }
 
@@ -260,24 +267,19 @@ std::string craftDumpMatrix(const std::vector<ItemStack> &items,
                unsigned int width)
 {
        std::ostringstream os(std::ios::binary);
-       os<<"{ ";
+       os << "{ ";
        unsigned int x = 0;
-       for(std::vector<ItemStack>::const_iterator
-                       i = items.begin();
-                       i != items.end(); i++, x++)
-       {
-               if(x == width)
-               {
-                       os<<"; ";
+       for (std::vector<ItemStack>::size_type i = 0;
+                       i < items.size(); i++, x++) {
+               if (x == width) {
+                       os << "; ";
                        x = 0;
+               } else if (x != 0) {
+                       os << ",";
                }
-               else if(x != 0)
-               {
-                       os<<",";
-               }
-               os<<"\""<<(i->getItemString())<<"\"";
+               os << '"' << (items[i].getItemString()) << '"';
        }
-       os<<" }";
+       os << " }";
        return os.str();
 }
 
@@ -286,10 +288,20 @@ std::string craftDumpMatrix(const std::vector<ItemStack> &items,
        CraftInput
 */
 
+bool CraftInput::empty() const
+{
+       for (const auto &item : items) {
+               if (!item.empty())
+                       return false;
+       }
+       return true;
+}
+
 std::string CraftInput::dump() const
 {
        std::ostringstream os(std::ios::binary);
-       os<<"(method="<<((int)method)<<", items="<<craftDumpMatrix(items, width)<<")";
+       os << "(method=" << ((int)method) << ", items="
+               << craftDumpMatrix(items, width) << ")";
        return os.str();
 }
 
@@ -300,7 +312,7 @@ std::string CraftInput::dump() const
 std::string CraftOutput::dump() const
 {
        std::ostringstream os(std::ios::binary);
-       os<<"(item=\""<<item<<"\", time="<<time<<")";
+       os << "(item=\"" << item << "\", time=" << time << ")";
        return os.str();
 }
 
@@ -313,90 +325,33 @@ std::string CraftReplacements::dump() const
        std::ostringstream os(std::ios::binary);
        os<<"{";
        const char *sep = "";
-       for(std::vector<std::pair<std::string, std::string> >::const_iterator
-                       i = pairs.begin();
-                       i != pairs.end(); i++)
-       {
-               os<<sep<<"\""<<(i->first)<<"\"=>\""<<(i->second)<<"\"";
+       for (const auto &repl_p : pairs) {
+               os << sep
+                       << '"' << (repl_p.first)
+                       << "\"=>\"" << (repl_p.second) << '"';
                sep = ",";
        }
-       os<<"}";
+       os << "}";
        return os.str();
 }
 
-void CraftReplacements::serialize(std::ostream &os) const
-{
-       writeU16(os, pairs.size());
-       for(u32 i=0; i<pairs.size(); i++)
-       {
-               os<<serializeString(pairs[i].first);
-               os<<serializeString(pairs[i].second);
-       }
-}
-
-void CraftReplacements::deSerialize(std::istream &is)
-{
-       pairs.clear();
-       u32 count = readU16(is);
-       for(u32 i=0; i<count; i++)
-       {
-               std::string first = deSerializeString(is);
-               std::string second = deSerializeString(is);
-               pairs.push_back(std::make_pair(first, second));
-       }
-}
-
 /*
-       CraftDefinition
+       CraftDefinitionShaped
 */
 
-void CraftDefinition::serialize(std::ostream &os) const
+CraftDefinitionShaped::CraftDefinitionShaped(
+               const std::string &output_,
+               unsigned int width_,
+               const std::vector<std::string> &recipe_,
+               const CraftReplacements &replacements_):
+       output(output_), width(width_), recipe(recipe_), replacements(replacements_)
 {
-       writeU8(os, 1); // version
-       os<<serializeString(getName());
-       serializeBody(os);
-}
-
-CraftDefinition* CraftDefinition::deSerialize(std::istream &is)
-{
-       int version = readU8(is);
-       if(version != 1) throw SerializationError(
-                       "unsupported CraftDefinition version");
-       std::string name = deSerializeString(is);
-       CraftDefinition *def = NULL;
-       if(name == "shaped")
-       {
-               def = new CraftDefinitionShaped;
-       }
-       else if(name == "shapeless")
-       {
-               def = new CraftDefinitionShapeless;
-       }
-       else if(name == "toolrepair")
-       {
-               def = new CraftDefinitionToolRepair;
-       }
-       else if(name == "cooking")
-       {
-               def = new CraftDefinitionCooking;
-       }
-       else if(name == "fuel")
-       {
-               def = new CraftDefinitionFuel;
-       }
+       if (hasGroupItem(recipe))
+               priority = PRIORITY_SHAPED_AND_GROUPS;
        else
-       {
-               infostream<<"Unknown CraftDefinition name=\""<<name<<"\""<<std::endl;
-                throw SerializationError("Unknown CraftDefinition name");
-       }
-       def->deSerializeBody(is, version);
-       return def;
+               priority = PRIORITY_SHAPED;
 }
 
-/*
-       CraftDefinitionShaped
-*/
-
 std::string CraftDefinitionShaped::getName() const
 {
        return "shaped";
@@ -404,57 +359,64 @@ std::string CraftDefinitionShaped::getName() const
 
 bool CraftDefinitionShaped::check(const CraftInput &input, IGameDef *gamedef) const
 {
-       if(input.method != CRAFT_METHOD_NORMAL)
+       if (input.method != CRAFT_METHOD_NORMAL)
                return false;
 
        // Get input item matrix
        std::vector<std::string> inp_names = craftGetItemNames(input.items, gamedef);
        unsigned int inp_width = input.width;
-       if(inp_width == 0)
+       if (inp_width == 0)
                return false;
-       while(inp_names.size() % inp_width != 0)
-               inp_names.push_back("");
+       while (inp_names.size() % inp_width != 0)
+               inp_names.emplace_back("");
 
        // Get input bounds
-       unsigned int inp_min_x=0, inp_max_x=0, inp_min_y=0, inp_max_y=0;
-       if(!craftGetBounds(inp_names, inp_width, inp_min_x, inp_max_x, inp_min_y, inp_max_y))
+       unsigned int inp_min_x = 0, inp_max_x = 0, inp_min_y = 0, inp_max_y = 0;
+       if (!craftGetBounds(inp_names, inp_width, inp_min_x, inp_max_x,
+                       inp_min_y, inp_max_y))
                return false;  // it was empty
 
+       std::vector<std::string> rec_names;
+       if (hash_inited)
+               rec_names = recipe_names;
+       else
+               rec_names = craftGetItemNames(recipe, gamedef);
+
        // Get recipe item matrix
-       std::vector<std::string> rec_names = craftGetItemNames(recipe, gamedef);
        unsigned int rec_width = width;
-       if(rec_width == 0)
+       if (rec_width == 0)
                return false;
-       while(rec_names.size() % rec_width != 0)
-               rec_names.push_back("");
+       while (rec_names.size() % rec_width != 0)
+               rec_names.emplace_back("");
 
        // Get recipe bounds
        unsigned int rec_min_x=0, rec_max_x=0, rec_min_y=0, rec_max_y=0;
-       if(!craftGetBounds(rec_names, rec_width, rec_min_x, rec_max_x, rec_min_y, rec_max_y))
+       if (!craftGetBounds(rec_names, rec_width, rec_min_x, rec_max_x,
+                       rec_min_y, rec_max_y))
                return false;  // it was empty
 
        // Different sizes?
-       if(inp_max_x - inp_min_x != rec_max_x - rec_min_x)
-               return false;
-       if(inp_max_y - inp_min_y != rec_max_y - rec_min_y)
+       if (inp_max_x - inp_min_x != rec_max_x - rec_min_x ||
+                       inp_max_y - inp_min_y != rec_max_y - rec_min_y)
                return false;
 
        // Verify that all item names in the bounding box are equal
        unsigned int w = inp_max_x - inp_min_x + 1;
        unsigned int h = inp_max_y - inp_min_y + 1;
-       for(unsigned int y=0; y<h; y++)
-       for(unsigned int x=0; x<w; x++)
-       {
-               unsigned int inp_x = inp_min_x + x;
-               unsigned int inp_y = inp_min_y + y;
-               unsigned int rec_x = rec_min_x + x;
-               unsigned int rec_y = rec_min_y + y;
-
-               if(!inputItemMatchesRecipe(
-                               inp_names[inp_y * inp_width + inp_x],
-                               rec_names[rec_y * rec_width + rec_x], gamedef->idef())
-               ){
-                       return false;
+
+       for (unsigned int y=0; y < h; y++) {
+               unsigned int inp_y = (inp_min_y + y) * inp_width;
+               unsigned int rec_y = (rec_min_y + y) * rec_width;
+
+               for (unsigned int x=0; x < w; x++) {
+                       unsigned int inp_x = inp_min_x + x;
+                       unsigned int rec_x = rec_min_x + x;
+
+                       if (!inputItemMatchesRecipe(
+                                       inp_names[inp_y + inp_x],
+                                       rec_names[rec_y + rec_x], gamedef->idef())) {
+                               return false;
+                       }
                }
        }
 
@@ -471,47 +433,61 @@ CraftInput CraftDefinitionShaped::getInput(const CraftOutput &output, IGameDef *
        return CraftInput(CRAFT_METHOD_NORMAL,width,craftGetItems(recipe,gamedef));
 }
 
-void CraftDefinitionShaped::decrementInput(CraftInput &input, IGameDef *gamedef) const
+void CraftDefinitionShaped::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
+        IGameDef *gamedef) const
 {
-       craftDecrementOrReplaceInput(input, replacements, gamedef);
+       craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 }
 
-std::string CraftDefinitionShaped::dump() const
+u64 CraftDefinitionShaped::getHash(CraftHashType type) const
 {
-       std::ostringstream os(std::ios::binary);
-       os<<"(shaped, output=\""<<output
-               <<"\", recipe="<<craftDumpMatrix(recipe, width)
-               <<", replacements="<<replacements.dump()<<")";
-       return os.str();
+       assert(hash_inited); // Pre-condition
+       assert((type == CRAFT_HASH_TYPE_ITEM_NAMES)
+               || (type == CRAFT_HASH_TYPE_COUNT)); // Pre-condition
+
+       std::vector<std::string> rec_names = recipe_names;
+       std::sort(rec_names.begin(), rec_names.end());
+       return getHashForGrid(type, rec_names);
 }
 
-void CraftDefinitionShaped::serializeBody(std::ostream &os) const
+void CraftDefinitionShaped::initHash(IGameDef *gamedef)
 {
-       os<<serializeString(output);
-       writeU16(os, width);
-       writeU16(os, recipe.size());
-       for(u32 i=0; i<recipe.size(); i++)
-               os<<serializeString(recipe[i]);
-       replacements.serialize(os);
+       if (hash_inited)
+               return;
+       hash_inited = true;
+       recipe_names = craftGetItemNames(recipe, gamedef);
+
+       if (hasGroupItem(recipe_names))
+               hash_type = CRAFT_HASH_TYPE_COUNT;
+       else
+               hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 }
 
-void CraftDefinitionShaped::deSerializeBody(std::istream &is, int version)
-{
-       if(version != 1) throw SerializationError(
-                       "unsupported CraftDefinitionShaped version");
-       output = deSerializeString(is);
-       width = readU16(is);
-       recipe.clear();
-       u32 count = readU16(is);
-       for(u32 i=0; i<count; i++)
-               recipe.push_back(deSerializeString(is));
-       replacements.deSerialize(is);
+std::string CraftDefinitionShaped::dump() const
+{
+       std::ostringstream os(std::ios::binary);
+       os << "(shaped, output=\"" << output
+               << "\", recipe=" << craftDumpMatrix(recipe, width)
+               << ", replacements=" << replacements.dump() << ")";
+       return os.str();
 }
 
 /*
        CraftDefinitionShapeless
 */
 
+CraftDefinitionShapeless::CraftDefinitionShapeless(
+               const std::string &output_,
+               const std::vector<std::string> &recipe_,
+               const CraftReplacements &replacements_):
+       output(output_), recipe(recipe_), replacements(replacements_)
+{
+       if (hasGroupItem(recipe))
+               priority = PRIORITY_SHAPELESS_AND_GROUPS;
+       else
+               priority = PRIORITY_SHAPELESS;
+}
+
 std::string CraftDefinitionShapeless::getName() const
 {
        return "shapeless";
@@ -519,48 +495,51 @@ std::string CraftDefinitionShapeless::getName() const
 
 bool CraftDefinitionShapeless::check(const CraftInput &input, IGameDef *gamedef) const
 {
-       if(input.method != CRAFT_METHOD_NORMAL)
+       if (input.method != CRAFT_METHOD_NORMAL)
                return false;
-       
+
        // Filter empty items out of input
        std::vector<std::string> input_filtered;
-       for(std::vector<ItemStack>::const_iterator
-                       i = input.items.begin();
-                       i != input.items.end(); i++)
-       {
-               if(i->name != "")
-                       input_filtered.push_back(i->name);
+       for (const auto &item : input.items) {
+               if (!item.name.empty())
+                       input_filtered.push_back(item.name);
        }
 
        // If there is a wrong number of items in input, no match
-       if(input_filtered.size() != recipe.size()){
+       if (input_filtered.size() != recipe.size()) {
                /*dstream<<"Number of input items ("<<input_filtered.size()
                                <<") does not match recipe size ("<<recipe.size()<<") "
                                <<"of recipe with output="<<output<<std::endl;*/
                return false;
        }
 
-       // Try with all permutations of the recipe
-       std::vector<std::string> recipe_copy = recipe;
-       // Start from the lexicographically first permutation (=sorted)
-       std::sort(recipe_copy.begin(), recipe_copy.end());
-       //while(std::prev_permutation(recipe_copy.begin(), recipe_copy.end())){}
-       do{
+       std::vector<std::string> recipe_copy;
+       if (hash_inited)
+               recipe_copy = recipe_names;
+       else {
+               recipe_copy = craftGetItemNames(recipe, gamedef);
+               std::sort(recipe_copy.begin(), recipe_copy.end());
+       }
+
+       // Try with all permutations of the recipe,
+       // start from the lexicographically first permutation (=sorted),
+       // recipe_names is pre-sorted
+       do {
                // If all items match, the recipe matches
                bool all_match = true;
                //dstream<<"Testing recipe (output="<<output<<"):";
-               for(size_t i=0; i<recipe.size(); i++){
+               for (size_t i=0; i<recipe.size(); i++) {
                        //dstream<<" ("<<input_filtered[i]<<" == "<<recipe_copy[i]<<")";
-                       if(!inputItemMatchesRecipe(input_filtered[i], recipe_copy[i],
-                                       gamedef->idef())){
+                       if (!inputItemMatchesRecipe(input_filtered[i], recipe_copy[i],
+                                       gamedef->idef())) {
                                all_match = false;
                                break;
                        }
                }
                //dstream<<" -> match="<<all_match<<std::endl;
-               if(all_match)
+               if (all_match)
                        return true;
-       }while(std::next_permutation(recipe_copy.begin(), recipe_copy.end()));
+       } while (std::next_permutation(recipe_copy.begin(), recipe_copy.end()));
 
        return false;
 }
@@ -572,48 +551,56 @@ CraftOutput CraftDefinitionShapeless::getOutput(const CraftInput &input, IGameDe
 
 CraftInput CraftDefinitionShapeless::getInput(const CraftOutput &output, IGameDef *gamedef) const
 {
-       return CraftInput(CRAFT_METHOD_NORMAL,0,craftGetItems(recipe,gamedef));
+       return CraftInput(CRAFT_METHOD_NORMAL, 0, craftGetItems(recipe, gamedef));
 }
 
-void CraftDefinitionShapeless::decrementInput(CraftInput &input, IGameDef *gamedef) const
+void CraftDefinitionShapeless::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
+       IGameDef *gamedef) const
 {
-       craftDecrementOrReplaceInput(input, replacements, gamedef);
+       craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 }
 
-std::string CraftDefinitionShapeless::dump() const
+u64 CraftDefinitionShapeless::getHash(CraftHashType type) const
 {
-       std::ostringstream os(std::ios::binary);
-       os<<"(shapeless, output=\""<<output
-               <<"\", recipe="<<craftDumpMatrix(recipe, recipe.size())
-               <<", replacements="<<replacements.dump()<<")";
-       return os.str();
+       assert(hash_inited); // Pre-condition
+       assert(type == CRAFT_HASH_TYPE_ITEM_NAMES
+               || type == CRAFT_HASH_TYPE_COUNT); // Pre-condition
+       return getHashForGrid(type, recipe_names);
 }
 
-void CraftDefinitionShapeless::serializeBody(std::ostream &os) const
+void CraftDefinitionShapeless::initHash(IGameDef *gamedef)
 {
-       os<<serializeString(output);
-       writeU16(os, recipe.size());
-       for(u32 i=0; i<recipe.size(); i++)
-               os<<serializeString(recipe[i]);
-       replacements.serialize(os);
+       if (hash_inited)
+               return;
+       hash_inited = true;
+       recipe_names = craftGetItemNames(recipe, gamedef);
+       std::sort(recipe_names.begin(), recipe_names.end());
+
+       if (hasGroupItem(recipe_names))
+               hash_type = CRAFT_HASH_TYPE_COUNT;
+       else
+               hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 }
 
-void CraftDefinitionShapeless::deSerializeBody(std::istream &is, int version)
+std::string CraftDefinitionShapeless::dump() const
 {
-       if(version != 1) throw SerializationError(
-                       "unsupported CraftDefinitionShapeless version");
-       output = deSerializeString(is);
-       recipe.clear();
-       u32 count = readU16(is);
-       for(u32 i=0; i<count; i++)
-               recipe.push_back(deSerializeString(is));
-       replacements.deSerialize(is);
+       std::ostringstream os(std::ios::binary);
+       os << "(shapeless, output=\"" << output
+               << "\", recipe=" << craftDumpMatrix(recipe, recipe.size())
+               << ", replacements=" << replacements.dump() << ")";
+       return os.str();
 }
 
 /*
        CraftDefinitionToolRepair
 */
 
+CraftDefinitionToolRepair::CraftDefinitionToolRepair(float additional_wear_):
+       additional_wear(additional_wear_)
+{
+       priority = PRIORITY_TOOLREPAIR;
+}
+
 static ItemStack craftToolRepair(
                const ItemStack &item1,
                const ItemStack &item2,
@@ -621,10 +608,9 @@ static ItemStack craftToolRepair(
                IGameDef *gamedef)
 {
        IItemDefManager *idef = gamedef->idef();
-       if(item1.count != 1 || item2.count != 1 || item1.name != item2.name
+       if (item1.count != 1 || item2.count != 1 || item1.name != item2.name
                        || idef->get(item1.name).type != ITEM_TOOL
-                       || idef->get(item2.name).type != ITEM_TOOL)
-       {
+                       || itemgroup_get(idef->get(item1.name).groups, "disable_repair") == 1) {
                // Failure
                return ItemStack();
        }
@@ -633,9 +619,9 @@ static ItemStack craftToolRepair(
        s32 item2_uses = 65536 - (u32) item2.wear;
        s32 new_uses = item1_uses + item2_uses;
        s32 new_wear = 65536 - new_uses + floor(additional_wear * 65536 + 0.5);
-       if(new_wear >= 65536)
+       if (new_wear >= 65536)
                return ItemStack();
-       if(new_wear < 0)
+       if (new_wear < 0)
                new_wear = 0;
 
        ItemStack repaired = item1;
@@ -650,21 +636,17 @@ std::string CraftDefinitionToolRepair::getName() const
 
 bool CraftDefinitionToolRepair::check(const CraftInput &input, IGameDef *gamedef) const
 {
-       if(input.method != CRAFT_METHOD_NORMAL)
+       if (input.method != CRAFT_METHOD_NORMAL)
                return false;
 
        ItemStack item1;
        ItemStack item2;
-       for(std::vector<ItemStack>::const_iterator
-                       i = input.items.begin();
-                       i != input.items.end(); i++)
-       {
-               if(!i->empty())
-               {
-                       if(item1.empty())
-                               item1 = *i;
-                       else if(item2.empty())
-                               item2 = *i;
+       for (const auto &item : input.items) {
+               if (!item.empty()) {
+                       if (item1.empty())
+                               item1 = item;
+                       else if (item2.empty())
+                               item2 = item;
                        else
                                return false;
                }
@@ -677,16 +659,12 @@ CraftOutput CraftDefinitionToolRepair::getOutput(const CraftInput &input, IGameD
 {
        ItemStack item1;
        ItemStack item2;
-       for(std::vector<ItemStack>::const_iterator
-                       i = input.items.begin();
-                       i != input.items.end(); i++)
-       {
-               if(!i->empty())
-               {
-                       if(item1.empty())
-                               item1 = *i;
-                       else if(item2.empty())
-                               item2 = *i;
+       for (const auto &item : input.items) {
+               if (!item.empty()) {
+                       if (item1.empty())
+                               item1 = item;
+                       else if (item2.empty())
+                               item2 = item;
                }
        }
        ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
@@ -696,11 +674,12 @@ CraftOutput CraftDefinitionToolRepair::getOutput(const CraftInput &input, IGameD
 CraftInput CraftDefinitionToolRepair::getInput(const CraftOutput &output, IGameDef *gamedef) const
 {
        std::vector<ItemStack> stack;
-       stack.push_back(ItemStack());
-       return CraftInput(CRAFT_METHOD_COOKING,additional_wear,stack);
+       stack.emplace_back();
+       return CraftInput(CRAFT_METHOD_COOKING, additional_wear, stack);
 }
 
-void CraftDefinitionToolRepair::decrementInput(CraftInput &input, IGameDef *gamedef) const
+void CraftDefinitionToolRepair::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
+       IGameDef *gamedef) const
 {
        craftDecrementInput(input, gamedef);
 }
@@ -708,26 +687,27 @@ void CraftDefinitionToolRepair::decrementInput(CraftInput &input, IGameDef *game
 std::string CraftDefinitionToolRepair::dump() const
 {
        std::ostringstream os(std::ios::binary);
-       os<<"(toolrepair, additional_wear="<<additional_wear<<")";
+       os << "(toolrepair, additional_wear=" << additional_wear << ")";
        return os.str();
 }
 
-void CraftDefinitionToolRepair::serializeBody(std::ostream &os) const
-{
-       writeF1000(os, additional_wear);
-}
-
-void CraftDefinitionToolRepair::deSerializeBody(std::istream &is, int version)
-{
-       if(version != 1) throw SerializationError(
-                       "unsupported CraftDefinitionToolRepair version");
-       additional_wear = readF1000(is);
-}
-
 /*
        CraftDefinitionCooking
 */
 
+CraftDefinitionCooking::CraftDefinitionCooking(
+               const std::string &output_,
+               const std::string &recipe_,
+               float cooktime_,
+               const CraftReplacements &replacements_):
+       output(output_), recipe(recipe_), cooktime(cooktime_), replacements(replacements_)
+{
+       if (isGroupRecipeStr(recipe))
+               priority = PRIORITY_SHAPELESS_AND_GROUPS;
+       else
+               priority = PRIORITY_SHAPELESS;
+}
+
 std::string CraftDefinitionCooking::getName() const
 {
        return "cooking";
@@ -735,29 +715,28 @@ std::string CraftDefinitionCooking::getName() const
 
 bool CraftDefinitionCooking::check(const CraftInput &input, IGameDef *gamedef) const
 {
-       if(input.method != CRAFT_METHOD_COOKING)
+       if (input.method != CRAFT_METHOD_COOKING)
                return false;
 
        // Filter empty items out of input
        std::vector<std::string> input_filtered;
-       for(std::vector<ItemStack>::const_iterator
-                       i = input.items.begin();
-                       i != input.items.end(); i++)
-       {
-               if(i->name != "")
-                       input_filtered.push_back(i->name);
+       for (const auto &item : input.items) {
+               const std::string &name = item.name;
+               if (!name.empty())
+                       input_filtered.push_back(name);
        }
 
        // If there is a wrong number of items in input, no match
-       if(input_filtered.size() != 1){
+       if (input_filtered.size() != 1) {
                /*dstream<<"Number of input items ("<<input_filtered.size()
                                <<") does not match recipe size (1) "
                                <<"of cooking recipe with output="<<output<<std::endl;*/
                return false;
        }
-       
+
        // Check the single input item
-       return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
+       std::string rec_name = craftGetItemName(recipe, gamedef);
+       return inputItemMatchesRecipe(input_filtered[0], rec_name, gamedef->idef());
 }
 
 CraftOutput CraftDefinitionCooking::getOutput(const CraftInput &input, IGameDef *gamedef) const
@@ -772,43 +751,66 @@ CraftInput CraftDefinitionCooking::getInput(const CraftOutput &output, IGameDef
        return CraftInput(CRAFT_METHOD_COOKING,cooktime,craftGetItems(rec,gamedef));
 }
 
-void CraftDefinitionCooking::decrementInput(CraftInput &input, IGameDef *gamedef) const
+void CraftDefinitionCooking::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
+       IGameDef *gamedef) const
 {
-       craftDecrementOrReplaceInput(input, replacements, gamedef);
+       craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 }
 
-std::string CraftDefinitionCooking::dump() const
+u64 CraftDefinitionCooking::getHash(CraftHashType type) const
 {
-       std::ostringstream os(std::ios::binary);
-       os<<"(cooking, output=\""<<output
-               <<"\", recipe=\""<<recipe
-               <<"\", cooktime="<<cooktime<<")"
-               <<", replacements="<<replacements.dump()<<")";
-       return os.str();
+       if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
+               return getHashForString(recipe_name);
+       }
+
+       if (type == CRAFT_HASH_TYPE_COUNT) {
+               return 1;
+       }
+
+       // illegal hash type for this CraftDefinition (pre-condition)
+       assert(false);
+       return 0;
 }
 
-void CraftDefinitionCooking::serializeBody(std::ostream &os) const
+void CraftDefinitionCooking::initHash(IGameDef *gamedef)
 {
-       os<<serializeString(output);
-       os<<serializeString(recipe);
-       writeF1000(os, cooktime);
-       replacements.serialize(os);
+       if (hash_inited)
+               return;
+       hash_inited = true;
+       recipe_name = craftGetItemName(recipe, gamedef);
+
+       if (isGroupRecipeStr(recipe_name))
+               hash_type = CRAFT_HASH_TYPE_COUNT;
+       else
+               hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 }
 
-void CraftDefinitionCooking::deSerializeBody(std::istream &is, int version)
+std::string CraftDefinitionCooking::dump() const
 {
-       if(version != 1) throw SerializationError(
-                       "unsupported CraftDefinitionCooking version");
-       output = deSerializeString(is);
-       recipe = deSerializeString(is);
-       cooktime = readF1000(is);
-       replacements.deSerialize(is);
+       std::ostringstream os(std::ios::binary);
+       os << "(cooking, output=\"" << output
+               << "\", recipe=\"" << recipe
+               << "\", cooktime=" << cooktime << ")"
+               << ", replacements=" << replacements.dump() << ")";
+       return os.str();
 }
 
 /*
        CraftDefinitionFuel
 */
 
+CraftDefinitionFuel::CraftDefinitionFuel(
+               const std::string &recipe_,
+               float burntime_,
+               const CraftReplacements &replacements_):
+       recipe(recipe_), burntime(burntime_), replacements(replacements_)
+{
+       if (isGroupRecipeStr(recipe_name))
+               priority = PRIORITY_SHAPELESS_AND_GROUPS;
+       else
+               priority = PRIORITY_SHAPELESS;
+}
+
 std::string CraftDefinitionFuel::getName() const
 {
        return "fuel";
@@ -816,29 +818,28 @@ std::string CraftDefinitionFuel::getName() const
 
 bool CraftDefinitionFuel::check(const CraftInput &input, IGameDef *gamedef) const
 {
-       if(input.method != CRAFT_METHOD_FUEL)
+       if (input.method != CRAFT_METHOD_FUEL)
                return false;
 
        // Filter empty items out of input
        std::vector<std::string> input_filtered;
-       for(std::vector<ItemStack>::const_iterator
-                       i = input.items.begin();
-                       i != input.items.end(); i++)
-       {
-               if(i->name != "")
-                       input_filtered.push_back(i->name);
+       for (const auto &item : input.items) {
+               const std::string &name = item.name;
+               if (!name.empty())
+                       input_filtered.push_back(name);
        }
 
        // If there is a wrong number of items in input, no match
-       if(input_filtered.size() != 1){
+       if (input_filtered.size() != 1) {
                /*dstream<<"Number of input items ("<<input_filtered.size()
                                <<") does not match recipe size (1) "
                                <<"of fuel recipe with burntime="<<burntime<<std::endl;*/
                return false;
        }
-       
+
        // Check the single input item
-       return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
+       std::string rec_name = craftGetItemName(recipe, gamedef);
+       return inputItemMatchesRecipe(input_filtered[0], rec_name, gamedef->idef());
 }
 
 CraftOutput CraftDefinitionFuel::getOutput(const CraftInput &input, IGameDef *gamedef) const
@@ -853,34 +854,47 @@ CraftInput CraftDefinitionFuel::getInput(const CraftOutput &output, IGameDef *ga
        return CraftInput(CRAFT_METHOD_COOKING,(int)burntime,craftGetItems(rec,gamedef));
 }
 
-void CraftDefinitionFuel::decrementInput(CraftInput &input, IGameDef *gamedef) const
+void CraftDefinitionFuel::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
+       IGameDef *gamedef) const
 {
-       craftDecrementOrReplaceInput(input, replacements, gamedef);
+       craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 }
 
-std::string CraftDefinitionFuel::dump() const
+u64 CraftDefinitionFuel::getHash(CraftHashType type) const
 {
-       std::ostringstream os(std::ios::binary);
-       os<<"(fuel, recipe=\""<<recipe
-               <<"\", burntime="<<burntime<<")"
-               <<", replacements="<<replacements.dump()<<")";
-       return os.str();
+       if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
+               return getHashForString(recipe_name);
+       }
+
+       if (type == CRAFT_HASH_TYPE_COUNT) {
+               return 1;
+       }
+
+       // illegal hash type for this CraftDefinition (pre-condition)
+       assert(false);
+       return 0;
 }
 
-void CraftDefinitionFuel::serializeBody(std::ostream &os) const
+void CraftDefinitionFuel::initHash(IGameDef *gamedef)
 {
-       os<<serializeString(recipe);
-       writeF1000(os, burntime);
-       replacements.serialize(os);
+       if (hash_inited)
+               return;
+       hash_inited = true;
+       recipe_name = craftGetItemName(recipe, gamedef);
+
+       if (isGroupRecipeStr(recipe_name))
+               hash_type = CRAFT_HASH_TYPE_COUNT;
+       else
+               hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 }
 
-void CraftDefinitionFuel::deSerializeBody(std::istream &is, int version)
+std::string CraftDefinitionFuel::dump() const
 {
-       if(version != 1) throw SerializationError(
-                       "unsupported CraftDefinitionFuel version");
-       recipe = deSerializeString(is);
-       burntime = readF1000(is);
-       replacements.deSerialize(is);
+       std::ostringstream os(std::ios::binary);
+       os << "(fuel, recipe=\"" << recipe
+               << "\", burntime=" << burntime << ")"
+               << ", replacements=" << replacements.dump() << ")";
+       return os.str();
 }
 
 /*
@@ -890,168 +904,222 @@ void CraftDefinitionFuel::deSerializeBody(std::istream &is, int version)
 class CCraftDefManager: public IWritableCraftDefManager
 {
 public:
+       CCraftDefManager()
+       {
+               m_craft_defs.resize(craft_hash_type_max + 1);
+       }
+
        virtual ~CCraftDefManager()
        {
                clear();
        }
+
        virtual bool getCraftResult(CraftInput &input, CraftOutput &output,
-                       bool decrementInput, IGameDef *gamedef) const
+                       std::vector<ItemStack> &output_replacement, bool decrementInput,
+                       IGameDef *gamedef) const
        {
-               output.item = "";
-               output.time = 0;
-
-               // If all input items are empty, abort.
-               bool all_empty = true;
-               for(std::vector<ItemStack>::const_iterator
-                               i = input.items.begin();
-                               i != input.items.end(); i++)
-               {
-                       if(!i->empty())
-                       {
-                               all_empty = false;
-                               break;
-                       }
-               }
-               if(all_empty)
+               if (input.empty())
                        return false;
 
-               // Walk crafting definitions from back to front, so that later
-               // definitions can override earlier ones.
-               for(std::vector<CraftDefinition*>::const_reverse_iterator
-                               i = m_craft_definitions.rbegin();
-                               i != m_craft_definitions.rend(); i++)
-               {
-                       CraftDefinition *def = *i;
-
-                       /*infostream<<"Checking "<<input.dump()<<std::endl
-                                       <<" against "<<def->dump()<<std::endl;*/
-
-                       try {
-                               if(def->check(input, gamedef))
-                               {
-                                       // Get output, then decrement input (if requested)
-                                       output = def->getOutput(input, gamedef);
-                                       if(decrementInput)
-                                               def->decrementInput(input, gamedef);
-                                       return true;
+               std::vector<std::string> input_names;
+               input_names = craftGetItemNames(input.items, gamedef);
+               std::sort(input_names.begin(), input_names.end());
+
+               // Try hash types with increasing collision rate
+               // while remembering the latest, highest priority recipe.
+               CraftDefinition::RecipePriority priority_best =
+                       CraftDefinition::PRIORITY_NO_RECIPE;
+               CraftDefinition *def_best = nullptr;
+               for (int type = 0; type <= craft_hash_type_max; type++) {
+                       u64 hash = getHashForGrid((CraftHashType) type, input_names);
+
+                       /*errorstream << "Checking type " << type << " with hash " << hash << std::endl;*/
+
+                       // We'd like to do "const [...] hash_collisions = m_craft_defs[type][hash];"
+                       // but that doesn't compile for some reason. This does.
+                       auto col_iter = (m_craft_defs[type]).find(hash);
+
+                       if (col_iter == (m_craft_defs[type]).end())
+                               continue;
+
+                       const std::vector<CraftDefinition*> &hash_collisions = col_iter->second;
+                       // Walk crafting definitions from back to front, so that later
+                       // definitions can override earlier ones.
+                       for (std::vector<CraftDefinition*>::size_type
+                                       i = hash_collisions.size(); i > 0; i--) {
+                               CraftDefinition *def = hash_collisions[i - 1];
+
+                               /*errorstream << "Checking " << input.dump() << std::endl
+                                       << " against " << def->dump() << std::endl;*/
+
+                               CraftDefinition::RecipePriority priority = def->getPriority();
+                               if (priority > priority_best
+                                               && def->check(input, gamedef)) {
+                                       // Check if the crafted node/item exists
+                                       CraftOutput out = def->getOutput(input, gamedef);
+                                       ItemStack is;
+                                       is.deSerialize(out.item, gamedef->idef());
+                                       if (!is.isKnown(gamedef->idef())) {
+                                               infostream << "trying to craft non-existent "
+                                                       << out.item << ", ignoring recipe" << std::endl;
+                                               continue;
+                                       }
+
+                                       output = out;
+                                       priority_best = priority;
+                                       def_best = def;
                                }
                        }
-                       catch(SerializationError &e)
-                       {
-                               errorstream<<"getCraftResult: ERROR: "
-                                               <<"Serialization error in recipe "
-                                               <<def->dump()<<std::endl;
-                               // then go on with the next craft definition
-                       }
                }
-               return false;
+               if (priority_best == CraftDefinition::PRIORITY_NO_RECIPE)
+                       return false;
+               if (decrementInput)
+                       def_best->decrementInput(input, output_replacement, gamedef);
+               return true;
        }
-       virtual bool getCraftRecipe(CraftInput &input, CraftOutput &output,
-                       IGameDef *gamedef) const
+
+       virtual std::vector<CraftDefinition*> getCraftRecipes(CraftOutput &output,
+                       IGameDef *gamedef, unsigned limit=0) const
+       {
+               std::vector<CraftDefinition*> recipes;
+
+               auto vec_iter = m_output_craft_definitions.find(output.item);
+
+               if (vec_iter == m_output_craft_definitions.end())
+                       return recipes;
+
+               const std::vector<CraftDefinition*> &vec = vec_iter->second;
+
+               recipes.reserve(limit ? MYMIN(limit, vec.size()) : vec.size());
+
+               for (std::vector<CraftDefinition*>::size_type i = vec.size();
+                               i > 0; i--) {
+                       CraftDefinition *def = vec[i - 1];
+                       if (limit && recipes.size() >= limit)
+                               break;
+                       recipes.push_back(def);
+               }
+
+               return recipes;
+       }
+
+       virtual bool clearCraftsByOutput(const CraftOutput &output, IGameDef *gamedef)
        {
-               CraftOutput tmpout;
-               tmpout.item = "";
-               tmpout.time = 0;
+               auto to_clear = m_output_craft_definitions.find(output.item);
 
-               // If output item is empty, abort.
-               if(output.item.empty())
+               if (to_clear == m_output_craft_definitions.end())
                        return false;
 
-               // Walk crafting definitions from back to front, so that later
-               // definitions can override earlier ones.
-               for(std::vector<CraftDefinition*>::const_reverse_iterator
-                               i = m_craft_definitions.rbegin();
-                               i != m_craft_definitions.rend(); i++)
-               {
-                       CraftDefinition *def = *i;
-
-                       /*infostream<<"Checking "<<input.dump()<<std::endl
-                                       <<" against "<<def->dump()<<std::endl;*/
-
-                       try {
-                               tmpout = def->getOutput(input, gamedef);
-                               if(tmpout.item.substr(0,output.item.length()) == output.item)
-                               {
-                                       // Get output, then decrement input (if requested)
-                                       input = def->getInput(output, gamedef);
-                                       return true;
-                               }
-                       }
-                       catch(SerializationError &e)
-                       {
-                               errorstream<<"getCraftResult: ERROR: "
-                                               <<"Serialization error in recipe "
-                                               <<def->dump()<<std::endl;
-                               // then go on with the next craft definition
+               for (auto def : to_clear->second) {
+                       // Recipes are not yet hashed at this point
+                       std::vector<CraftDefinition *> &defs = m_craft_defs[(int)CRAFT_HASH_TYPE_UNHASHED][0];
+                       defs.erase(std::remove(defs.begin(), defs.end(), def), defs.end());
+                       delete def;
+               }
+               m_output_craft_definitions.erase(to_clear);
+               return true;
+       }
+
+       virtual bool clearCraftsByInput(const CraftInput &input, IGameDef *gamedef)
+       {
+               if (input.empty())
+                       return false;
+
+               // Recipes are not yet hashed at this point
+               std::vector<CraftDefinition *> &defs = m_craft_defs[(int)CRAFT_HASH_TYPE_UNHASHED][0];
+               std::unordered_set<const CraftDefinition *> defs_to_remove;
+               std::vector<CraftDefinition *> new_defs;
+
+               for (auto def : defs) {
+                       if (def->check(input, gamedef))
+                               defs_to_remove.insert(def);
+                       else
+                               new_defs.push_back(def);
+               }
+
+               if (!defs_to_remove.empty()) {
+                       for (auto def : defs_to_remove)
+                               delete def;
+
+                       defs.swap(new_defs);
+
+                       for (auto &output : m_output_craft_definitions) {
+                               std::vector<CraftDefinition *> &outdefs = output.second;
+                               outdefs.erase(std::remove_if(outdefs.begin(), outdefs.end(), [&](const CraftDefinition* def) {
+                                       return defs_to_remove.find(def) != defs_to_remove.end();
+                               }), outdefs.end());
                        }
                }
-               return false;
+
+               return !defs_to_remove.empty();
        }
+
        virtual std::string dump() const
        {
                std::ostringstream os(std::ios::binary);
-               os<<"Crafting definitions:\n";
-               for(std::vector<CraftDefinition*>::const_iterator
-                               i = m_craft_definitions.begin();
-                               i != m_craft_definitions.end(); i++)
-               {
-                       os<<(*i)->dump()<<"\n";
+               os << "Crafting definitions:\n";
+               for (int type = 0; type <= craft_hash_type_max; ++type) {
+                       for (auto it = m_craft_defs[type].begin();
+                                       it != m_craft_defs[type].end(); ++it) {
+                               for (std::vector<CraftDefinition*>::size_type i = 0;
+                                               i < it->second.size(); i++) {
+                                       os << "type " << type
+                                               << " hash " << it->first
+                                               << " def " << it->second[i]->dump()
+                                               << "\n";
+                               }
+                       }
                }
                return os.str();
        }
-       virtual void registerCraft(CraftDefinition *def)
+       virtual void registerCraft(CraftDefinition *def, IGameDef *gamedef)
        {
-               verbosestream<<"registerCraft: registering craft definition: "
-                               <<def->dump()<<std::endl;
-               m_craft_definitions.push_back(def);
+               TRACESTREAM(<< "registerCraft: registering craft definition: "
+                               << def->dump() << std::endl);
+               m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].push_back(def);
+
+               CraftInput input;
+               std::string output_name = craftGetItemName(
+                               def->getOutput(input, gamedef).item, gamedef);
+               m_output_craft_definitions[output_name].push_back(def);
        }
        virtual void clear()
        {
-               for(std::vector<CraftDefinition*>::iterator
-                               i = m_craft_definitions.begin();
-                               i != m_craft_definitions.end(); i++){
-                       delete *i;
-               }
-               m_craft_definitions.clear();
-       }
-       virtual void serialize(std::ostream &os) const
-       {
-               writeU8(os, 0); // version
-               u16 count = m_craft_definitions.size();
-               writeU16(os, count);
-               for(std::vector<CraftDefinition*>::const_iterator
-                               i = m_craft_definitions.begin();
-                               i != m_craft_definitions.end(); i++){
-                       CraftDefinition *def = *i;
-                       // Serialize wrapped in a string
-                       std::ostringstream tmp_os(std::ios::binary);
-                       def->serialize(tmp_os);
-                       os<<serializeString(tmp_os.str());
+               for (int type = 0; type <= craft_hash_type_max; ++type) {
+                       for (auto &it : m_craft_defs[type]) {
+                               for (auto &iit : it.second) {
+                                       delete iit;
+                               }
+                               it.second.clear();
+                       }
+                       m_craft_defs[type].clear();
                }
+               m_output_craft_definitions.clear();
        }
-       virtual void deSerialize(std::istream &is)
+       virtual void initHashes(IGameDef *gamedef)
        {
-               // Clear everything
-               clear();
-               // Deserialize
-               int version = readU8(is);
-               if(version != 0) throw SerializationError(
-                               "unsupported CraftDefManager version");
-               u16 count = readU16(is);
-               for(u16 i=0; i<count; i++){
-                       // Deserialize a string and grab a CraftDefinition from it
-                       std::istringstream tmp_is(deSerializeString(is), std::ios::binary);
-                       CraftDefinition *def = CraftDefinition::deSerialize(tmp_is);
-                       // Register
-                       registerCraft(def);
+               // Move the CraftDefs from the unhashed layer into layers higher up.
+               std::vector<CraftDefinition *> &unhashed =
+                       m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
+               for (auto def : unhashed) {
+                       // Initialize and get the definition's hash
+                       def->initHash(gamedef);
+                       CraftHashType type = def->getHashType();
+                       u64 hash = def->getHash(type);
+
+                       // Enter the definition
+                       m_craft_defs[type][hash].push_back(def);
                }
+               unhashed.clear();
        }
 private:
-       std::vector<CraftDefinition*> m_craft_definitions;
+       std::vector<std::unordered_map<u64, std::vector<CraftDefinition*> > >
+               m_craft_defs;
+       std::unordered_map<std::string, std::vector<CraftDefinition*> >
+               m_output_craft_definitions;
 };
 
 IWritableCraftDefManager* createCraftDefManager()
 {
        return new CCraftDefManager();
 }
-