aboutsummaryrefslogtreecommitdiff
path: root/src/profiler.cpp
blob: d05b7abfe36cafb0f5425d49c552969f7e7dec90 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
/*
Minetest
Copyright (C) 2015 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
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#include "profiler.h"
#include "porting.h"

static Profiler main_profiler;
Profiler *g_profiler = &main_profiler;
ScopeProfiler::ScopeProfiler(
		Profiler *profiler, const std::string &name, ScopeProfilerType type) :
		m_profiler(profiler),
		m_name(name), m_type(type)
{
	m_name.append(" [ms]");
	if (m_profiler)
		m_timer = new TimeTaker(m_name, nullptr, PRECISION_MILLI);
}

ScopeProfiler::~ScopeProfiler()
{
	if (!m_timer)
		return;

	float duration_ms = m_timer->stop(true);
	float duration = duration_ms;
	if (m_profiler) {
		switch (m_type) {
		case SPT_ADD:
			m_profiler->add(m_name, duration);
			break;
		case SPT_AVG:
			m_profiler->avg(m_name, duration);
			break;
		case SPT_GRAPH_ADD:
			m_profiler->graphAdd(m_name, duration);
			break;
		}
	}
	delete m_timer;
}

Profiler::Profiler()
{
	m_start_time = porting::getTimeMs();
}

void Profiler::add(const std::string &name, float value)
{
	MutexAutoLock lock(m_mutex);
	{
		/* No average shall have been used; mark add used as -2 */
		std::map<std::string, int>::iterator n = m_avgcounts.find(name);
		if (n == m_avgcounts.end()) {
			m_avgcounts[name] = -2;
		} else {
			if (n->second == -1)
				n->second = -2;
			assert(n->second == -2);
		}
	}
	{
		std::map<std::string, float>::iterator n = m_data.find(name);
		if (n == m_data.end())
			m_data[name] = value;
		else
			n->second += value;
	}
}

void Profiler::avg(const std::string &name, float value)
{
	MutexAutoLock lock(m_mutex);
	int &count = m_avgcounts[name];

	assert(count != -2);
	count = MYMAX(count, 0) + 1;
	m_data[name] += value;
}

void Profiler::clear()
{
	MutexAutoLock lock(m_mutex);
	for (auto &it : m_data) {
		it.second = 0;
	}
	m_avgcounts.clear();
	m_start_time = porting::getTimeMs();
}

float Profiler::getValue(const std::string &name) const
{
	auto numerator = m_data.find(name);
	if (numerator == m_data.end())
		return 0.f;

	auto denominator = m_avgcounts.find(name);
	if (denominator != m_avgcounts.end()) {
		if (denominator->second >= 1)
			return numerator->second / denominator->second;
	}

	return numerator->second;
}

int Profiler::getAvgCount(const std::string &name) const
{
	auto n = m_avgcounts.find(name);

	if (n != m_avgcounts.end() && n->second >= 1)
		return n->second;

	return 1;
}

u64 Profiler::getElapsedMs() const
{
	return porting::getTimeMs() - m_start_time;
}

int Profiler::print(std::ostream &o, u32 page, u32 pagecount)
{
	GraphValues values;
	getPage(values, page, pagecount);
	char num_buf[50];

	for (const auto &i : values) {
		o << "  " << i.first << " ";
		if (i.second == 0) {
			o << std::endl;
			continue;
		}

		s32 space = 44 - i.first.size();
		for (s32 j = 0; j < space; j++) {
			if ((j & 1) && j < space - 1)
				o << ".";
			else
				o << " ";
		}
		porting::mt_snprintf(num_buf, sizeof(num_buf), "% 4ix % 3g",
				getAvgCount(i.first), i.second);
		o << num_buf << std::endl;
	}
	return values.size();
}

void Profiler::getPage(GraphValues &o, u32 page, u32 pagecount)
{
	MutexAutoLock lock(m_mutex);

	u32 minindex, maxindex;
	paging(m_data.size(), page, pagecount, minindex, maxindex);

	for (const auto &i : m_data) {
		if (maxindex == 0)
			break;
		maxindex--;

		if (minindex != 0) {
			minindex--;
			continue;
		}

		o[i.first] = i.second / getAvgCount(i.first);
	}
}
84'>784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117
/*
Minetest
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
the Free Software Foundation; either version 2.1 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#include "craftdef.h"

#include "irrlichttypes.h"
#include "log.h"
#include <sstream>
#include <set>
#include <algorithm>
#include "gamedef.h"
#include "inventory.h"
#include "util/serialize.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
static bool inputItemMatchesRecipe(const std::string &inp_name,
		const std::string &rec_name, IItemDefManager *idef)
{
	// Exact name
	if (inp_name == rec_name)
		return true;

	// Group
	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 {
			std::string check_group = f.next(",");
			if (itemgroup_get(def.groups, check_group) == 0) {
				all_groups_match = false;
				break;
			}
		} while (!f.at_end());
		if (all_groups_match)
			return true;
	}

	// Didn't match
	return false;
}

// Deserialize an itemstring then return the name of the item
static std::string craftGetItemName(const std::string &itemstring, IGameDef *gamedef)
{
	ItemStack item;
	item.deSerialize(itemstring, gamedef->idef());
	return item.name;
}

// (mapcar craftGetItemName itemstrings)
static std::vector<std::string> craftGetItemNames(
		const std::vector<std::string> &itemstrings, IGameDef *gamedef)
{
	std::vector<std::string> result;
	result.reserve(itemstrings.size());
	for (const auto &itemstring : itemstrings) {
		result.push_back(craftGetItemName(itemstring, gamedef));
	}
	return result;
}

// Get name of each item, and return them as a new list.
static std::vector<std::string> craftGetItemNames(
		const std::vector<ItemStack> &items, IGameDef *gamedef)
{
	std::vector<std::string> result;
	result.reserve(items.size());
	for (const auto &item : items) {
		result.push_back(item.name);
	}
	return result;
}

// convert a list of item names, to ItemStacks.
static std::vector<ItemStack> craftGetItems(
		const std::vector<std::string> &items, IGameDef *gamedef)
{
	std::vector<ItemStack> result;
	result.reserve(items.size());
	for (const auto &item : items) {
		result.emplace_back(std::string(item), (u16)1,
			(u16)0, gamedef->getItemDefManager());
	}
	return result;
}

// Compute bounding rectangle given a matrix of items
// Returns false if every item is ""
static bool craftGetBounds(const std::vector<std::string> &items, unsigned int width,
		unsigned int &min_x, unsigned int &max_x,
		unsigned int &min_y, unsigned int &max_y)
{
	bool success = false;
	unsigned int x = 0;
	unsigned int y = 0;
	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;
			}
		}

		// Step coordinate
		x++;
		if (x == width) {
			x = 0;
			y++;
		}
	}
	return success;
}

// Removes 1 from each item stack
static void craftDecrementInput(CraftInput &input, IGameDef *gamedef)
{
	for (auto &item : input.items) {
		if (item.count != 0)
			item.remove(1);
	}
}

// Removes 1 from each item stack with replacement support
// 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()) {
		craftDecrementInput(input, gamedef);
		return;
	}

	// Make a copy of the replacements pair list
	std::vector<std::pair<std::string, std::string> > pairs = replacements.pairs;

	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;
				output_replacements.push_back(rep);
				break;

			}
		}
		// No replacement was found, simply decrement count by one
		if (!found_replacement && item.count > 0)
			item.remove(1);
	}
}

// Dump an itemstring matrix
static std::string craftDumpMatrix(const std::vector<std::string> &items,
		unsigned int width)
{
	std::ostringstream os(std::ios::binary);
	os << "{ ";
	unsigned int x = 0;
	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 << ",";
		}
		os << '"' << items[i] << '"';
	}
	os << " }";
	return os.str();
}

// Dump an item matrix
std::string craftDumpMatrix(const std::vector<ItemStack> &items,
		unsigned int width)
{
	std::ostringstream os(std::ios::binary);
	os << "{ ";
	unsigned int x = 0;
	for (std::vector<ItemStack>::size_type i = 0;
			i < items.size(); i++, x++) {
		if (x == width) {
			os << "; ";
			x = 0;
		} else if (x != 0) {
			os << ",";
		}
		os << '"' << (items[i].getItemString()) << '"';
	}
	os << " }";
	return os.str();
}


/*
	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) << ")";
	return os.str();
}

/*
	CraftOutput
*/

std::string CraftOutput::dump() const
{
	std::ostringstream os(std::ios::binary);
	os << "(item=\"" << item << "\", time=" << time << ")";
	return os.str();
}

/*
	CraftReplacements
*/

std::string CraftReplacements::dump() const
{
	std::ostringstream os(std::ios::binary);
	os<<"{";
	const char *sep = "";
	for (const auto &repl_p : pairs) {
		os << sep
			<< '"' << (repl_p.first)
			<< "\"=>\"" << (repl_p.second) << '"';
		sep = ",";
	}
	os << "}";
	return os.str();
}

/*
	CraftDefinitionShaped
*/

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_)
{
	if (hasGroupItem(recipe))
		priority = PRIORITY_SHAPED_AND_GROUPS;
	else
		priority = PRIORITY_SHAPED;
}

std::string CraftDefinitionShaped::getName() const
{
	return "shaped";
}

bool CraftDefinitionShaped::check(const CraftInput &input, IGameDef *gamedef) const
{
	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)
		return false;
	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))
		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
	unsigned int rec_width = width;
	if (rec_width == 0)
		return false;
	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))
		return false;  // it was empty

	// Different sizes?
	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++) {
		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;
			}
		}
	}

	return true;
}

CraftOutput CraftDefinitionShaped::getOutput(const CraftInput &input, IGameDef *gamedef) const
{
	return CraftOutput(output, 0);
}

CraftInput CraftDefinitionShaped::getInput(const CraftOutput &output, IGameDef *gamedef) const
{
	return CraftInput(CRAFT_METHOD_NORMAL,width,craftGetItems(recipe,gamedef));
}

void CraftDefinitionShaped::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
	 IGameDef *gamedef) const
{
	craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
}

u64 CraftDefinitionShaped::getHash(CraftHashType type) const
{
	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::initHash(IGameDef *gamedef)
{
	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;
}

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";
}

bool CraftDefinitionShapeless::check(const CraftInput &input, IGameDef *gamedef) const
{
	if (input.method != CRAFT_METHOD_NORMAL)
		return false;

	// Filter empty items out of input
	std::vector<std::string> input_filtered;
	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()) {
		/*dstream<<"Number of input items ("<<input_filtered.size()
				<<") does not match recipe size ("<<recipe.size()<<") "
				<<"of recipe with output="<<output<<std::endl;*/
		return false;
	}

	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++) {
			//dstream<<" ("<<input_filtered[i]<<" == "<<recipe_copy[i]<<")";
			if (!inputItemMatchesRecipe(input_filtered[i], recipe_copy[i],
					gamedef->idef())) {
				all_match = false;
				break;
			}
		}
		//dstream<<" -> match="<<all_match<<std::endl;
		if (all_match)
			return true;
	} while (std::next_permutation(recipe_copy.begin(), recipe_copy.end()));

	return false;
}

CraftOutput CraftDefinitionShapeless::getOutput(const CraftInput &input, IGameDef *gamedef) const
{
	return CraftOutput(output, 0);
}

CraftInput CraftDefinitionShapeless::getInput(const CraftOutput &output, IGameDef *gamedef) const
{
	return CraftInput(CRAFT_METHOD_NORMAL, 0, craftGetItems(recipe, gamedef));
}

void CraftDefinitionShapeless::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
	IGameDef *gamedef) const
{
	craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
}

u64 CraftDefinitionShapeless::getHash(CraftHashType type) const
{
	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::initHash(IGameDef *gamedef)
{
	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;
}

std::string CraftDefinitionShapeless::dump() const
{
	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,
		float additional_wear,
		IGameDef *gamedef)
{
	IItemDefManager *idef = gamedef->idef();
	if (item1.count != 1 || item2.count != 1 || item1.name != item2.name
			|| idef->get(item1.name).type != ITEM_TOOL
			|| itemgroup_get(idef->get(item1.name).groups, "disable_repair") == 1) {
		// Failure
		return ItemStack();
	}

	s32 item1_uses = 65536 - (u32) item1.wear;
	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)
		return ItemStack();
	if (new_wear < 0)
		new_wear = 0;

	ItemStack repaired = item1;
	repaired.wear = new_wear;
	return repaired;
}

std::string CraftDefinitionToolRepair::getName() const
{
	return "toolrepair";
}

bool CraftDefinitionToolRepair::check(const CraftInput &input, IGameDef *gamedef) const
{
	if (input.method != CRAFT_METHOD_NORMAL)
		return false;

	ItemStack item1;
	ItemStack item2;
	for (const auto &item : input.items) {
		if (!item.empty()) {
			if (item1.empty())
				item1 = item;
			else if (item2.empty())
				item2 = item;
			else
				return false;
		}
	}
	ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
	return !repaired.empty();
}

CraftOutput CraftDefinitionToolRepair::getOutput(const CraftInput &input, IGameDef *gamedef) const
{
	ItemStack item1;
	ItemStack item2;
	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);
	return CraftOutput(repaired.getItemString(), 0);
}

CraftInput CraftDefinitionToolRepair::getInput(const CraftOutput &output, IGameDef *gamedef) const
{
	std::vector<ItemStack> stack;
	stack.emplace_back();
	return CraftInput(CRAFT_METHOD_COOKING, additional_wear, stack);
}

void CraftDefinitionToolRepair::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
	IGameDef *gamedef) const
{
	craftDecrementInput(input, gamedef);
}

std::string CraftDefinitionToolRepair::dump() const
{
	std::ostringstream os(std::ios::binary);
	os << "(toolrepair, additional_wear=" << additional_wear << ")";
	return os.str();
}

/*
	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";
}

bool CraftDefinitionCooking::check(const CraftInput &input, IGameDef *gamedef) const
{
	if (input.method != CRAFT_METHOD_COOKING)
		return false;

	// Filter empty items out of input
	std::vector<std::string> input_filtered;
	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) {
		/*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());
}

CraftOutput CraftDefinitionCooking::getOutput(const CraftInput &input, IGameDef *gamedef) const
{
	return CraftOutput(output, cooktime);
}

CraftInput CraftDefinitionCooking::getInput(const CraftOutput &output, IGameDef *gamedef) const
{
	std::vector<std::string> rec;
	rec.push_back(recipe);
	return CraftInput(CRAFT_METHOD_COOKING,cooktime,craftGetItems(rec,gamedef));
}

void CraftDefinitionCooking::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
	IGameDef *gamedef) const
{
	craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
}

u64 CraftDefinitionCooking::getHash(CraftHashType type) const
{
	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::initHash(IGameDef *gamedef)
{
	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;
}

std::string CraftDefinitionCooking::dump() const
{
	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";
}

bool CraftDefinitionFuel::check(const CraftInput &input, IGameDef *gamedef) const
{
	if (input.method != CRAFT_METHOD_FUEL)
		return false;

	// Filter empty items out of input
	std::vector<std::string> input_filtered;
	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) {
		/*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());
}

CraftOutput CraftDefinitionFuel::getOutput(const CraftInput &input, IGameDef *gamedef) const
{
	return CraftOutput("", burntime);
}

CraftInput CraftDefinitionFuel::getInput(const CraftOutput &output, IGameDef *gamedef) const
{
	std::vector<std::string> rec;
	rec.push_back(recipe);
	return CraftInput(CRAFT_METHOD_COOKING,(int)burntime,craftGetItems(rec,gamedef));
}

void CraftDefinitionFuel::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
	IGameDef *gamedef) const
{
	craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
}

u64 CraftDefinitionFuel::getHash(CraftHashType type) const
{
	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::initHash(IGameDef *gamedef)
{
	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;
}

std::string CraftDefinitionFuel::dump() const
{
	std::ostringstream os(std::ios::binary);
	os << "(fuel, recipe=\"" << recipe
		<< "\", burntime=" << burntime << ")"
		<< ", replacements=" << replacements.dump() << ")";
	return os.str();
}

/*
	Craft definition manager
*/

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,
			std::vector<ItemStack> &output_replacement, bool decrementInput,
			IGameDef *gamedef) const
	{
		if (input.empty())
			return false;

		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;
				}
			}
		}
		if (priority_best == CraftDefinition::PRIORITY_NO_RECIPE)
			return false;
		if (decrementInput)
			def_best->decrementInput(input, output_replacement, gamedef);
		return true;
	}

	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)
	{
		auto to_clear = m_output_craft_definitions.find(output.item);

		if (to_clear == m_output_craft_definitions.end())
			return false;

		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::vector<CraftDefinition *> new_defs;
		bool got_hit = false;
		for (auto def : defs) {
			if (!def->check(input, gamedef)) {
				new_defs.push_back(def);
				continue;
			}
			got_hit = true;
			std::string output = def->getOutput(input, gamedef).item;
			delete def;
			auto it = m_output_craft_definitions.find(craftGetItemName(output, gamedef));
			if (it == m_output_craft_definitions.end())
				continue;
			std::vector<CraftDefinition *> &outdefs = it->second;
			outdefs.erase(std::remove(outdefs.begin(), outdefs.end(), def), outdefs.end());
		}
		if (got_hit)
			defs.swap(new_defs);

		return got_hit;
	}

	virtual std::string dump() const
	{
		std::ostringstream os(std::ios::binary);
		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, IGameDef *gamedef)
	{
		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 (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 initHashes(IGameDef *gamedef)
	{
		// 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<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();
}