src/craftdef.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "craftdef.h"
  21
  22 #include "irrlichttypes.h"
  23 #include "log.h"
  24 #include <sstream>
  25 #include <set>
  26 #include <algorithm>
  27 #include "gamedef.h"
  28 #include "inventory.h"
  29 #include "util/serialize.h"
  30 #include "util/string.h"
  31 #include "util/numeric.h"
  32 #include "util/strfnd.h"
  33 #include "exceptions.h"
  34
  35 inline bool isGroupRecipeStr(const std::string &rec_name)
  36 {
  37         return str_starts_with(rec_name, std::string("group:"));
  38 }
  39
  40 inline u64 getHashForString(const std::string &recipe_str)
  41 {
  42         /*errorstream << "Hashing craft string  \"" << recipe_str << '"';*/
  43         return murmur_hash_64_ua(recipe_str.data(), recipe_str.length(), 0xdeadbeef);
  44 }
  45
  46 static u64 getHashForGrid(CraftHashType type, const std::vector<std::string> &grid_names)
  47 {
  48         switch (type) {
  49                 case CRAFT_HASH_TYPE_ITEM_NAMES: {
  50                         std::ostringstream os;
  51                         bool is_first = true;
  52                         for (const std::string &grid_name : grid_names) {
  53                                 if (!grid_name.empty()) {
  54                                         os << (is_first ? "" : "\n") << grid_name;
  55                                         is_first = false;
  56                                 }
  57                         }
  58                         return getHashForString(os.str());
  59                 } case CRAFT_HASH_TYPE_COUNT: {
  60                         u64 cnt = 0;
  61                         for (const std::string &grid_name : grid_names)
  62                                 if (!grid_name.empty())
  63                                         cnt++;
  64                         return cnt;
  65                 } case CRAFT_HASH_TYPE_UNHASHED:
  66                         return 0;
  67         }
  68         // invalid CraftHashType
  69         assert(false);
  70         return 0;
  71 }
  72
  73 // Check if input matches recipe
  74 // Takes recipe groups into account
  75 static bool inputItemMatchesRecipe(const std::string &inp_name,
  76                 const std::string &rec_name, IItemDefManager *idef)
  77 {
  78         // Exact name
  79         if (inp_name == rec_name)
  80                 return true;
  81
  82         // Group
  83         if (isGroupRecipeStr(rec_name) && idef->isKnown(inp_name)) {
  84                 const struct ItemDefinition &def = idef->get(inp_name);
  85                 Strfnd f(rec_name.substr(6));
  86                 bool all_groups_match = true;
  87                 do {
  88                         std::string check_group = f.next(",");
  89                         if (itemgroup_get(def.groups, check_group) == 0) {
  90                                 all_groups_match = false;
  91                                 break;
  92                         }
  93                 } while (!f.at_end());
  94                 if (all_groups_match)
  95                         return true;
  96         }
  97
  98         // Didn't match
  99         return false;
 100 }
 101
 102 // Deserialize an itemstring then return the name of the item
 103 static std::string craftGetItemName(const std::string &itemstring, IGameDef *gamedef)
 104 {
 105         ItemStack item;
 106         item.deSerialize(itemstring, gamedef->idef());
 107         return item.name;
 108 }
 109
 110 // (mapcar craftGetItemName itemstrings)
 111 static std::vector<std::string> craftGetItemNames(
 112                 const std::vector<std::string> &itemstrings, IGameDef *gamedef)
 113 {
 114         std::vector<std::string> result;
 115         result.reserve(itemstrings.size());
 116         for (const auto &itemstring : itemstrings) {
 117                 result.push_back(craftGetItemName(itemstring, gamedef));
 118         }
 119         return result;
 120 }
 121
 122 // Get name of each item, and return them as a new list.
 123 static std::vector<std::string> craftGetItemNames(
 124                 const std::vector<ItemStack> &items, IGameDef *gamedef)
 125 {
 126         std::vector<std::string> result;
 127         result.reserve(items.size());
 128         for (const auto &item : items) {
 129                 result.push_back(item.name);
 130         }
 131         return result;
 132 }
 133
 134 // convert a list of item names, to ItemStacks.
 135 static std::vector<ItemStack> craftGetItems(
 136                 const std::vector<std::string> &items, IGameDef *gamedef)
 137 {
 138         std::vector<ItemStack> result;
 139         result.reserve(items.size());
 140         for (const auto &item : items) {
 141                 result.emplace_back(std::string(item), (u16)1,
 142                         (u16)0, gamedef->getItemDefManager());
 143         }
 144         return result;
 145 }
 146
 147 // Compute bounding rectangle given a matrix of items
 148 // Returns false if every item is ""
 149 static bool craftGetBounds(const std::vector<std::string> &items, unsigned int width,
 150                 unsigned int &min_x, unsigned int &max_x,
 151                 unsigned int &min_y, unsigned int &max_y)
 152 {
 153         bool success = false;
 154         unsigned int x = 0;
 155         unsigned int y = 0;
 156         for (const std::string &item : items) {
 157                 // Is this an actual item?
 158                 if (!item.empty()) {
 159                         if (!success) {
 160                                 // This is the first nonempty item
 161                                 min_x = max_x = x;
 162                                 min_y = max_y = y;
 163                                 success = true;
 164                         } else {
 165                                 if (x < min_x) min_x = x;
 166                                 if (x > max_x) max_x = x;
 167                                 if (y < min_y) min_y = y;
 168                                 if (y > max_y) max_y = y;
 169                         }
 170                 }
 171
 172                 // Step coordinate
 173                 x++;
 174                 if (x == width) {
 175                         x = 0;
 176                         y++;
 177                 }
 178         }
 179         return success;
 180 }
 181
 182 // Removes 1 from each item stack
 183 static void craftDecrementInput(CraftInput &input, IGameDef *gamedef)
 184 {
 185         for (auto &item : input.items) {
 186                 if (item.count != 0)
 187                         item.remove(1);
 188         }
 189 }
 190
 191 // Removes 1 from each item stack with replacement support
 192 // Example: if replacements contains the pair ("bucket:bucket_water", "bucket:bucket_empty"),
 193 //   a water bucket will not be removed but replaced by an empty bucket.
 194 static void craftDecrementOrReplaceInput(CraftInput &input,
 195                 std::vector<ItemStack> &output_replacements,
 196                 const CraftReplacements &replacements,
 197                 IGameDef *gamedef)
 198 {
 199         if (replacements.pairs.empty()) {
 200                 craftDecrementInput(input, gamedef);
 201                 return;
 202         }
 203
 204         // Make a copy of the replacements pair list
 205         std::vector<std::pair<std::string, std::string> > pairs = replacements.pairs;
 206
 207         for (auto &item : input.items) {
 208                 // Find an appropriate replacement
 209                 bool found_replacement = false;
 210                 for (auto j = pairs.begin(); j != pairs.end(); ++j) {
 211                         if (inputItemMatchesRecipe(item.name, j->first, gamedef->idef())) {
 212                                 if (item.count == 1) {
 213                                         item.deSerialize(j->second, gamedef->idef());
 214                                         found_replacement = true;
 215                                         pairs.erase(j);
 216                                         break;
 217                                 }
 218
 219                                 ItemStack rep;
 220                                 rep.deSerialize(j->second, gamedef->idef());
 221                                 item.remove(1);
 222                                 found_replacement = true;
 223                                 output_replacements.push_back(rep);
 224                                 break;
 225
 226                         }
 227                 }
 228                 // No replacement was found, simply decrement count by one
 229                 if (!found_replacement && item.count > 0)
 230                         item.remove(1);
 231         }
 232 }
 233
 234 // Dump an itemstring matrix
 235 static std::string craftDumpMatrix(const std::vector<std::string> &items,
 236                 unsigned int width)
 237 {
 238         std::ostringstream os(std::ios::binary);
 239         os << "{ ";
 240         unsigned int x = 0;
 241         for(std::vector<std::string>::size_type i = 0;
 242                         i < items.size(); i++, x++) {
 243                 if (x == width) {
 244                         os << "; ";
 245                         x = 0;
 246                 } else if (x != 0) {
 247                         os << ",";
 248                 }
 249                 os << '"' << items[i] << '"';
 250         }
 251         os << " }";
 252         return os.str();
 253 }
 254
 255 // Dump an item matrix
 256 std::string craftDumpMatrix(const std::vector<ItemStack> &items,
 257                 unsigned int width)
 258 {
 259         std::ostringstream os(std::ios::binary);
 260         os << "{ ";
 261         unsigned int x = 0;
 262         for (std::vector<ItemStack>::size_type i = 0;
 263                         i < items.size(); i++, x++) {
 264                 if (x == width) {
 265                         os << "; ";
 266                         x = 0;
 267                 } else if (x != 0) {
 268                         os << ",";
 269                 }
 270                 os << '"' << (items[i].getItemString()) << '"';
 271         }
 272         os << " }";
 273         return os.str();
 274 }
 275
 276
 277 /*
 278         CraftInput
 279 */
 280
 281 std::string CraftInput::dump() const
 282 {
 283         std::ostringstream os(std::ios::binary);
 284         os << "(method=" << ((int)method) << ", items="
 285                 << craftDumpMatrix(items, width) << ")";
 286         return os.str();
 287 }
 288
 289 /*
 290         CraftOutput
 291 */
 292
 293 std::string CraftOutput::dump() const
 294 {
 295         std::ostringstream os(std::ios::binary);
 296         os << "(item=\"" << item << "\", time=" << time << ")";
 297         return os.str();
 298 }
 299
 300 /*
 301         CraftReplacements
 302 */
 303
 304 std::string CraftReplacements::dump() const
 305 {
 306         std::ostringstream os(std::ios::binary);
 307         os<<"{";
 308         const char *sep = "";
 309         for (const auto &repl_p : pairs) {
 310                 os << sep
 311                         << '"' << (repl_p.first)
 312                         << "\"=>\"" << (repl_p.second) << '"';
 313                 sep = ",";
 314         }
 315         os << "}";
 316         return os.str();
 317 }
 318
 319 /*
 320         CraftDefinitionShaped
 321 */
 322
 323 std::string CraftDefinitionShaped::getName() const
 324 {
 325         return "shaped";
 326 }
 327
 328 bool CraftDefinitionShaped::check(const CraftInput &input, IGameDef *gamedef) const
 329 {
 330         if (input.method != CRAFT_METHOD_NORMAL)
 331                 return false;
 332
 333         // Get input item matrix
 334         std::vector<std::string> inp_names = craftGetItemNames(input.items, gamedef);
 335         unsigned int inp_width = input.width;
 336         if (inp_width == 0)
 337                 return false;
 338         while (inp_names.size() % inp_width != 0)
 339                 inp_names.emplace_back("");
 340
 341         // Get input bounds
 342         unsigned int inp_min_x = 0, inp_max_x = 0, inp_min_y = 0, inp_max_y = 0;
 343         if (!craftGetBounds(inp_names, inp_width, inp_min_x, inp_max_x,
 344                         inp_min_y, inp_max_y))
 345                 return false;  // it was empty
 346
 347         std::vector<std::string> rec_names;
 348         if (hash_inited)
 349                 rec_names = recipe_names;
 350         else
 351                 rec_names = craftGetItemNames(recipe, gamedef);
 352
 353         // Get recipe item matrix
 354         unsigned int rec_width = width;
 355         if (rec_width == 0)
 356                 return false;
 357         while (rec_names.size() % rec_width != 0)
 358                 rec_names.emplace_back("");
 359
 360         // Get recipe bounds
 361         unsigned int rec_min_x=0, rec_max_x=0, rec_min_y=0, rec_max_y=0;
 362         if (!craftGetBounds(rec_names, rec_width, rec_min_x, rec_max_x,
 363                         rec_min_y, rec_max_y))
 364                 return false;  // it was empty
 365
 366         // Different sizes?
 367         if (inp_max_x - inp_min_x != rec_max_x - rec_min_x ||
 368                         inp_max_y - inp_min_y != rec_max_y - rec_min_y)
 369                 return false;
 370
 371         // Verify that all item names in the bounding box are equal
 372         unsigned int w = inp_max_x - inp_min_x + 1;
 373         unsigned int h = inp_max_y - inp_min_y + 1;
 374
 375         for (unsigned int y=0; y < h; y++) {
 376                 unsigned int inp_y = (inp_min_y + y) * inp_width;
 377                 unsigned int rec_y = (rec_min_y + y) * rec_width;
 378
 379                 for (unsigned int x=0; x < w; x++) {
 380                         unsigned int inp_x = inp_min_x + x;
 381                         unsigned int rec_x = rec_min_x + x;
 382
 383                         if (!inputItemMatchesRecipe(
 384                                         inp_names[inp_y + inp_x],
 385                                         rec_names[rec_y + rec_x], gamedef->idef())) {
 386                                 return false;
 387                         }
 388                 }
 389         }
 390
 391         return true;
 392 }
 393
 394 CraftOutput CraftDefinitionShaped::getOutput(const CraftInput &input, IGameDef *gamedef) const
 395 {
 396         return CraftOutput(output, 0);
 397 }
 398
 399 CraftInput CraftDefinitionShaped::getInput(const CraftOutput &output, IGameDef *gamedef) const
 400 {
 401         return CraftInput(CRAFT_METHOD_NORMAL,width,craftGetItems(recipe,gamedef));
 402 }
 403
 404 void CraftDefinitionShaped::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 405          IGameDef *gamedef) const
 406 {
 407         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 408 }
 409
 410 u64 CraftDefinitionShaped::getHash(CraftHashType type) const
 411 {
 412         assert(hash_inited); // Pre-condition
 413         assert((type == CRAFT_HASH_TYPE_ITEM_NAMES)
 414                 || (type == CRAFT_HASH_TYPE_COUNT)); // Pre-condition
 415
 416         std::vector<std::string> rec_names = recipe_names;
 417         std::sort(rec_names.begin(), rec_names.end());
 418         return getHashForGrid(type, rec_names);
 419 }
 420
 421 void CraftDefinitionShaped::initHash(IGameDef *gamedef)
 422 {
 423         if (hash_inited)
 424                 return;
 425         hash_inited = true;
 426         recipe_names = craftGetItemNames(recipe, gamedef);
 427
 428         bool has_group = false;
 429         for (const auto &recipe_name : recipe_names) {
 430                 if (isGroupRecipeStr(recipe_name)) {
 431                         has_group = true;
 432                         break;
 433                 }
 434         }
 435         if (has_group) {
 436                 hash_type = CRAFT_HASH_TYPE_COUNT;
 437                 priority = SHAPED_AND_GROUPS;
 438         } else {
 439                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 440                 priority = SHAPED;
 441         }
 442 }
 443
 444 std::string CraftDefinitionShaped::dump() const
 445 {
 446         std::ostringstream os(std::ios::binary);
 447         os << "(shaped, output=\"" << output
 448                 << "\", recipe=" << craftDumpMatrix(recipe, width)
 449                 << ", replacements=" << replacements.dump() << ")";
 450         return os.str();
 451 }
 452
 453 /*
 454         CraftDefinitionShapeless
 455 */
 456
 457 std::string CraftDefinitionShapeless::getName() const
 458 {
 459         return "shapeless";
 460 }
 461
 462 bool CraftDefinitionShapeless::check(const CraftInput &input, IGameDef *gamedef) const
 463 {
 464         if (input.method != CRAFT_METHOD_NORMAL)
 465                 return false;
 466
 467         // Filter empty items out of input
 468         std::vector<std::string> input_filtered;
 469         for (const auto &item : input.items) {
 470                 if (!item.name.empty())
 471                         input_filtered.push_back(item.name);
 472         }
 473
 474         // If there is a wrong number of items in input, no match
 475         if (input_filtered.size() != recipe.size()) {
 476                 /*dstream<<"Number of input items ("<<input_filtered.size()
 477                                 <<") does not match recipe size ("<<recipe.size()<<") "
 478                                 <<"of recipe with output="<<output<<std::endl;*/
 479                 return false;
 480         }
 481
 482         std::vector<std::string> recipe_copy;
 483         if (hash_inited)
 484                 recipe_copy = recipe_names;
 485         else {
 486                 recipe_copy = craftGetItemNames(recipe, gamedef);
 487                 std::sort(recipe_copy.begin(), recipe_copy.end());
 488         }
 489
 490         // Try with all permutations of the recipe,
 491         // start from the lexicographically first permutation (=sorted),
 492         // recipe_names is pre-sorted
 493         do {
 494                 // If all items match, the recipe matches
 495                 bool all_match = true;
 496                 //dstream<<"Testing recipe (output="<<output<<"):";
 497                 for (size_t i=0; i<recipe.size(); i++) {
 498                         //dstream<<" ("<<input_filtered[i]<<" == "<<recipe_copy[i]<<")";
 499                         if (!inputItemMatchesRecipe(input_filtered[i], recipe_copy[i],
 500                                         gamedef->idef())) {
 501                                 all_match = false;
 502                                 break;
 503                         }
 504                 }
 505                 //dstream<<" -> match="<<all_match<<std::endl;
 506                 if (all_match)
 507                         return true;
 508         } while (std::next_permutation(recipe_copy.begin(), recipe_copy.end()));
 509
 510         return false;
 511 }
 512
 513 CraftOutput CraftDefinitionShapeless::getOutput(const CraftInput &input, IGameDef *gamedef) const
 514 {
 515         return CraftOutput(output, 0);
 516 }
 517
 518 CraftInput CraftDefinitionShapeless::getInput(const CraftOutput &output, IGameDef *gamedef) const
 519 {
 520         return CraftInput(CRAFT_METHOD_NORMAL, 0, craftGetItems(recipe, gamedef));
 521 }
 522
 523 void CraftDefinitionShapeless::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 524         IGameDef *gamedef) const
 525 {
 526         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 527 }
 528
 529 u64 CraftDefinitionShapeless::getHash(CraftHashType type) const
 530 {
 531         assert(hash_inited); // Pre-condition
 532         assert(type == CRAFT_HASH_TYPE_ITEM_NAMES
 533                 || type == CRAFT_HASH_TYPE_COUNT); // Pre-condition
 534         return getHashForGrid(type, recipe_names);
 535 }
 536
 537 void CraftDefinitionShapeless::initHash(IGameDef *gamedef)
 538 {
 539         if (hash_inited)
 540                 return;
 541         hash_inited = true;
 542         recipe_names = craftGetItemNames(recipe, gamedef);
 543         std::sort(recipe_names.begin(), recipe_names.end());
 544
 545         bool has_group = false;
 546         for (const auto &recipe_name : recipe_names) {
 547                 if (isGroupRecipeStr(recipe_name)) {
 548                         has_group = true;
 549                         break;
 550                 }
 551         }
 552         if (has_group) {
 553                 hash_type = CRAFT_HASH_TYPE_COUNT;
 554                 priority = SHAPELESS_AND_GROUPS;
 555         } else {
 556                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 557                 priority = SHAPELESS;
 558         }
 559 }
 560
 561 std::string CraftDefinitionShapeless::dump() const
 562 {
 563         std::ostringstream os(std::ios::binary);
 564         os << "(shapeless, output=\"" << output
 565                 << "\", recipe=" << craftDumpMatrix(recipe, recipe.size())
 566                 << ", replacements=" << replacements.dump() << ")";
 567         return os.str();
 568 }
 569
 570 /*
 571         CraftDefinitionToolRepair
 572 */
 573
 574 static ItemStack craftToolRepair(
 575                 const ItemStack &item1,
 576                 const ItemStack &item2,
 577                 float additional_wear,
 578                 IGameDef *gamedef)
 579 {
 580         IItemDefManager *idef = gamedef->idef();
 581         if (item1.count != 1 || item2.count != 1 || item1.name != item2.name
 582                         || idef->get(item1.name).type != ITEM_TOOL
 583                         || itemgroup_get(idef->get(item1.name).groups, "disable_repair") == 1) {
 584                 // Failure
 585                 return ItemStack();
 586         }
 587
 588         s32 item1_uses = 65536 - (u32) item1.wear;
 589         s32 item2_uses = 65536 - (u32) item2.wear;
 590         s32 new_uses = item1_uses + item2_uses;
 591         s32 new_wear = 65536 - new_uses + floor(additional_wear * 65536 + 0.5);
 592         if (new_wear >= 65536)
 593                 return ItemStack();
 594         if (new_wear < 0)
 595                 new_wear = 0;
 596
 597         ItemStack repaired = item1;
 598         repaired.wear = new_wear;
 599         return repaired;
 600 }
 601
 602 std::string CraftDefinitionToolRepair::getName() const
 603 {
 604         return "toolrepair";
 605 }
 606
 607 bool CraftDefinitionToolRepair::check(const CraftInput &input, IGameDef *gamedef) const
 608 {
 609         if (input.method != CRAFT_METHOD_NORMAL)
 610                 return false;
 611
 612         ItemStack item1;
 613         ItemStack item2;
 614         for (const auto &item : input.items) {
 615                 if (!item.empty()) {
 616                         if (item1.empty())
 617                                 item1 = item;
 618                         else if (item2.empty())
 619                                 item2 = item;
 620                         else
 621                                 return false;
 622                 }
 623         }
 624         ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
 625         return !repaired.empty();
 626 }
 627
 628 CraftOutput CraftDefinitionToolRepair::getOutput(const CraftInput &input, IGameDef *gamedef) const
 629 {
 630         ItemStack item1;
 631         ItemStack item2;
 632         for (const auto &item : input.items) {
 633                 if (!item.empty()) {
 634                         if (item1.empty())
 635                                 item1 = item;
 636                         else if (item2.empty())
 637                                 item2 = item;
 638                 }
 639         }
 640         ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
 641         return CraftOutput(repaired.getItemString(), 0);
 642 }
 643
 644 CraftInput CraftDefinitionToolRepair::getInput(const CraftOutput &output, IGameDef *gamedef) const
 645 {
 646         std::vector<ItemStack> stack;
 647         stack.emplace_back();
 648         return CraftInput(CRAFT_METHOD_COOKING, additional_wear, stack);
 649 }
 650
 651 void CraftDefinitionToolRepair::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 652         IGameDef *gamedef) const
 653 {
 654         craftDecrementInput(input, gamedef);
 655 }
 656
 657 std::string CraftDefinitionToolRepair::dump() const
 658 {
 659         std::ostringstream os(std::ios::binary);
 660         os << "(toolrepair, additional_wear=" << additional_wear << ")";
 661         return os.str();
 662 }
 663
 664 /*
 665         CraftDefinitionCooking
 666 */
 667
 668 std::string CraftDefinitionCooking::getName() const
 669 {
 670         return "cooking";
 671 }
 672
 673 bool CraftDefinitionCooking::check(const CraftInput &input, IGameDef *gamedef) const
 674 {
 675         if (input.method != CRAFT_METHOD_COOKING)
 676                 return false;
 677
 678         // Filter empty items out of input
 679         std::vector<std::string> input_filtered;
 680         for (const auto &item : input.items) {
 681                 const std::string &name = item.name;
 682                 if (!name.empty())
 683                         input_filtered.push_back(name);
 684         }
 685
 686         // If there is a wrong number of items in input, no match
 687         if (input_filtered.size() != 1) {
 688                 /*dstream<<"Number of input items ("<<input_filtered.size()
 689                                 <<") does not match recipe size (1) "
 690                                 <<"of cooking recipe with output="<<output<<std::endl;*/
 691                 return false;
 692         }
 693
 694         // Check the single input item
 695         return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
 696 }
 697
 698 CraftOutput CraftDefinitionCooking::getOutput(const CraftInput &input, IGameDef *gamedef) const
 699 {
 700         return CraftOutput(output, cooktime);
 701 }
 702
 703 CraftInput CraftDefinitionCooking::getInput(const CraftOutput &output, IGameDef *gamedef) const
 704 {
 705         std::vector<std::string> rec;
 706         rec.push_back(recipe);
 707         return CraftInput(CRAFT_METHOD_COOKING,cooktime,craftGetItems(rec,gamedef));
 708 }
 709
 710 void CraftDefinitionCooking::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 711         IGameDef *gamedef) const
 712 {
 713         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 714 }
 715
 716 u64 CraftDefinitionCooking::getHash(CraftHashType type) const
 717 {
 718         if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
 719                 return getHashForString(recipe_name);
 720         }
 721
 722         if (type == CRAFT_HASH_TYPE_COUNT) {
 723                 return 1;
 724         }
 725
 726         // illegal hash type for this CraftDefinition (pre-condition)
 727         assert(false);
 728         return 0;
 729 }
 730
 731 void CraftDefinitionCooking::initHash(IGameDef *gamedef)
 732 {
 733         if (hash_inited)
 734                 return;
 735         hash_inited = true;
 736         recipe_name = craftGetItemName(recipe, gamedef);
 737
 738         if (isGroupRecipeStr(recipe_name)) {
 739                 hash_type = CRAFT_HASH_TYPE_COUNT;
 740                 priority = SHAPELESS_AND_GROUPS;
 741         } else {
 742                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 743                 priority = SHAPELESS;
 744         }
 745 }
 746
 747 std::string CraftDefinitionCooking::dump() const
 748 {
 749         std::ostringstream os(std::ios::binary);
 750         os << "(cooking, output=\"" << output
 751                 << "\", recipe=\"" << recipe
 752                 << "\", cooktime=" << cooktime << ")"
 753                 << ", replacements=" << replacements.dump() << ")";
 754         return os.str();
 755 }
 756
 757 /*
 758         CraftDefinitionFuel
 759 */
 760
 761 std::string CraftDefinitionFuel::getName() const
 762 {
 763         return "fuel";
 764 }
 765
 766 bool CraftDefinitionFuel::check(const CraftInput &input, IGameDef *gamedef) const
 767 {
 768         if (input.method != CRAFT_METHOD_FUEL)
 769                 return false;
 770
 771         // Filter empty items out of input
 772         std::vector<std::string> input_filtered;
 773         for (const auto &item : input.items) {
 774                 const std::string &name = item.name;
 775                 if (!name.empty())
 776                         input_filtered.push_back(name);
 777         }
 778
 779         // If there is a wrong number of items in input, no match
 780         if (input_filtered.size() != 1) {
 781                 /*dstream<<"Number of input items ("<<input_filtered.size()
 782                                 <<") does not match recipe size (1) "
 783                                 <<"of fuel recipe with burntime="<<burntime<<std::endl;*/
 784                 return false;
 785         }
 786
 787         // Check the single input item
 788         return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
 789 }
 790
 791 CraftOutput CraftDefinitionFuel::getOutput(const CraftInput &input, IGameDef *gamedef) const
 792 {
 793         return CraftOutput("", burntime);
 794 }
 795
 796 CraftInput CraftDefinitionFuel::getInput(const CraftOutput &output, IGameDef *gamedef) const
 797 {
 798         std::vector<std::string> rec;
 799         rec.push_back(recipe);
 800         return CraftInput(CRAFT_METHOD_COOKING,(int)burntime,craftGetItems(rec,gamedef));
 801 }
 802
 803 void CraftDefinitionFuel::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 804         IGameDef *gamedef) const
 805 {
 806         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 807 }
 808
 809 u64 CraftDefinitionFuel::getHash(CraftHashType type) const
 810 {
 811         if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
 812                 return getHashForString(recipe_name);
 813         }
 814
 815         if (type == CRAFT_HASH_TYPE_COUNT) {
 816                 return 1;
 817         }
 818
 819         // illegal hash type for this CraftDefinition (pre-condition)
 820         assert(false);
 821         return 0;
 822 }
 823
 824 void CraftDefinitionFuel::initHash(IGameDef *gamedef)
 825 {
 826         if (hash_inited)
 827                 return;
 828         hash_inited = true;
 829         recipe_name = craftGetItemName(recipe, gamedef);
 830
 831         if (isGroupRecipeStr(recipe_name)) {
 832                 hash_type = CRAFT_HASH_TYPE_COUNT;
 833                 priority = SHAPELESS_AND_GROUPS;
 834         } else {
 835                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 836                 priority = SHAPELESS;
 837         }
 838 }
 839
 840 std::string CraftDefinitionFuel::dump() const
 841 {
 842         std::ostringstream os(std::ios::binary);
 843         os << "(fuel, recipe=\"" << recipe
 844                 << "\", burntime=" << burntime << ")"
 845                 << ", replacements=" << replacements.dump() << ")";
 846         return os.str();
 847 }
 848
 849 /*
 850         Craft definition manager
 851 */
 852
 853 class CCraftDefManager: public IWritableCraftDefManager
 854 {
 855 public:
 856         CCraftDefManager()
 857         {
 858                 m_craft_defs.resize(craft_hash_type_max + 1);
 859         }
 860
 861         virtual ~CCraftDefManager()
 862         {
 863                 clear();
 864         }
 865
 866         virtual bool getCraftResult(CraftInput &input, CraftOutput &output,
 867                         std::vector<ItemStack> &output_replacement, bool decrementInput,
 868                         IGameDef *gamedef) const
 869         {
 870                 output.item = "";
 871                 output.time = 0;
 872
 873                 // If all input items are empty, abort.
 874                 bool all_empty = true;
 875                 for (const auto &item : input.items) {
 876                         if (!item.empty()) {
 877                                 all_empty = false;
 878                                 break;
 879                         }
 880                 }
 881                 if (all_empty)
 882                         return false;
 883
 884                 std::vector<std::string> input_names;
 885                 input_names = craftGetItemNames(input.items, gamedef);
 886                 std::sort(input_names.begin(), input_names.end());
 887
 888                 // Try hash types with increasing collision rate
 889                 // while remembering the latest, highest priority recipe.
 890                 CraftDefinition::RecipePriority priority_best =
 891                         CraftDefinition::NO_RECIPE;
 892                 CraftDefinition *def_best = nullptr;
 893                 for (int type = 0; type <= craft_hash_type_max; type++) {
 894                         u64 hash = getHashForGrid((CraftHashType) type, input_names);
 895
 896                         /*errorstream << "Checking type " << type << " with hash " << hash << std::endl;*/
 897
 898                         // We'd like to do "const [...] hash_collisions = m_craft_defs[type][hash];"
 899                         // but that doesn't compile for some reason. This does.
 900                         auto col_iter = (m_craft_defs[type]).find(hash);
 901
 902                         if (col_iter == (m_craft_defs[type]).end())
 903                                 continue;
 904
 905                         const std::vector<CraftDefinition*> &hash_collisions = col_iter->second;
 906                         // Walk crafting definitions from back to front, so that later
 907                         // definitions can override earlier ones.
 908                         for (std::vector<CraftDefinition*>::size_type
 909                                         i = hash_collisions.size(); i > 0; i--) {
 910                                 CraftDefinition *def = hash_collisions[i - 1];
 911
 912                                 /*errorstream << "Checking " << input.dump() << std::endl
 913                                         << " against " << def->dump() << std::endl;*/
 914
 915                                 CraftDefinition::RecipePriority priority = def->getPriority();
 916                                 if (priority > priority_best
 917                                                 && def->check(input, gamedef)) {
 918                                         // Check if the crafted node/item exists
 919                                         CraftOutput out = def->getOutput(input, gamedef);
 920                                         ItemStack is;
 921                                         is.deSerialize(out.item, gamedef->idef());
 922                                         if (!is.isKnown(gamedef->idef())) {
 923                                                 infostream << "trying to craft non-existent "
 924                                                         << out.item << ", ignoring recipe" << std::endl;
 925                                                 continue;
 926                                         }
 927
 928                                         output = out;
 929                                         priority_best = priority;
 930                                         def_best = def;
 931                                 }
 932                         }
 933                 }
 934                 if (priority_best == CraftDefinition::NO_RECIPE)
 935                         return false;
 936                 if (decrementInput)
 937                         def_best->decrementInput(input, output_replacement, gamedef);
 938                 return true;
 939         }
 940
 941         virtual std::vector<CraftDefinition*> getCraftRecipes(CraftOutput &output,
 942                         IGameDef *gamedef, unsigned limit=0) const
 943         {
 944                 std::vector<CraftDefinition*> recipes;
 945
 946                 auto vec_iter = m_output_craft_definitions.find(output.item);
 947
 948                 if (vec_iter == m_output_craft_definitions.end())
 949                         return recipes;
 950
 951                 const std::vector<CraftDefinition*> &vec = vec_iter->second;
 952
 953                 recipes.reserve(limit ? MYMIN(limit, vec.size()) : vec.size());
 954
 955                 for (std::vector<CraftDefinition*>::size_type i = vec.size();
 956                                 i > 0; i--) {
 957                         CraftDefinition *def = vec[i - 1];
 958                         if (limit && recipes.size() >= limit)
 959                                 break;
 960                         recipes.push_back(def);
 961                 }
 962
 963                 return recipes;
 964         }
 965
 966         virtual bool clearCraftRecipesByOutput(const CraftOutput &output, IGameDef *gamedef)
 967         {
 968                 auto vec_iter = m_output_craft_definitions.find(output.item);
 969
 970                 if (vec_iter == m_output_craft_definitions.end())
 971                         return false;
 972
 973                 std::vector<CraftDefinition*> &vec = vec_iter->second;
 974                 for (auto def : vec) {
 975                         // Recipes are not yet hashed at this point
 976                         std::vector<CraftDefinition*> &unhashed_inputs_vec = m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
 977                         std::vector<CraftDefinition*> new_vec_by_input;
 978                         /* We will preallocate necessary memory addresses, so we don't need to reallocate them later.
 979                                 This would save us some performance. */
 980                         new_vec_by_input.reserve(unhashed_inputs_vec.size());
 981                         for (auto &i2 : unhashed_inputs_vec) {
 982                                 if (def != i2) {
 983                                         new_vec_by_input.push_back(i2);
 984                                 }
 985                         }
 986                         m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].swap(new_vec_by_input);
 987                 }
 988                 m_output_craft_definitions.erase(output.item);
 989                 return true;
 990         }
 991
 992         virtual bool clearCraftRecipesByInput(CraftMethod craft_method, unsigned int craft_grid_width,
 993                 const std::vector<std::string> &recipe, IGameDef *gamedef)
 994         {
 995                 bool all_empty = true;
 996                 for (const auto &i : recipe) {
 997                         if (!i.empty()) {
 998                                 all_empty = false;
 999                                 break;
1000                         }
1001                 }
1002                 if (all_empty)
1003                         return false;
1004
1005                 CraftInput input(craft_method, craft_grid_width, craftGetItems(recipe, gamedef));
1006                 // Recipes are not yet hashed at this point
1007                 std::vector<CraftDefinition*> &unhashed_inputs_vec = m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
1008                 std::vector<CraftDefinition*> new_vec_by_input;
1009                 bool got_hit = false;
1010                 for (std::vector<CraftDefinition*>::size_type
1011                                 i = unhashed_inputs_vec.size(); i > 0; i--) {
1012                         CraftDefinition *def = unhashed_inputs_vec[i - 1];
1013                         /* If the input doesn't match the recipe definition, this recipe definition later
1014                                 will be added back in source map. */
1015                         if (!def->check(input, gamedef)) {
1016                                 new_vec_by_input.push_back(def);
1017                                 continue;
1018                         }
1019                         CraftOutput output = def->getOutput(input, gamedef);
1020                         got_hit = true;
1021                         auto vec_iter = m_output_craft_definitions.find(output.item);
1022                         if (vec_iter == m_output_craft_definitions.end())
1023                                 continue;
1024                         std::vector<CraftDefinition*> &vec = vec_iter->second;
1025                         std::vector<CraftDefinition*> new_vec_by_output;
1026                         /* We will preallocate necessary memory addresses, so we don't need
1027                                 to reallocate them later. This would save us some performance. */
1028                         new_vec_by_output.reserve(vec.size());
1029                         for (auto &vec_i : vec) {
1030                                 /* If pointers from map by input and output are not same,
1031                                         we will add 'CraftDefinition*' to a new vector. */
1032                                 if (def != vec_i) {
1033                                         /* Adding dereferenced iterator value (which are
1034                                                 'CraftDefinition' reference) to a new vector. */
1035                                         new_vec_by_output.push_back(vec_i);
1036                                 }
1037                         }
1038                         // Swaps assigned to current key value with new vector for output map.
1039                         m_output_craft_definitions[output.item].swap(new_vec_by_output);
1040                 }
1041                 if (got_hit)
1042                         // Swaps value with new vector for input map.
1043                         m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].swap(new_vec_by_input);
1044
1045                 return got_hit;
1046         }
1047
1048         virtual std::string dump() const
1049         {
1050                 std::ostringstream os(std::ios::binary);
1051                 os << "Crafting definitions:\n";
1052                 for (int type = 0; type <= craft_hash_type_max; ++type) {
1053                         for (auto it = m_craft_defs[type].begin();
1054                                         it != m_craft_defs[type].end(); ++it) {
1055                                 for (std::vector<CraftDefinition*>::size_type i = 0;
1056                                                 i < it->second.size(); i++) {
1057                                         os << "type " << type
1058                                                 << " hash " << it->first
1059                                                 << " def " << it->second[i]->dump()
1060                                                 << "\n";
1061                                 }
1062                         }
1063                 }
1064                 return os.str();
1065         }
1066         virtual void registerCraft(CraftDefinition *def, IGameDef *gamedef)
1067         {
1068                 verbosestream << "registerCraft: registering craft definition: "
1069                                 << def->dump() << std::endl;
1070                 m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].push_back(def);
1071
1072                 CraftInput input;
1073                 std::string output_name = craftGetItemName(
1074                                 def->getOutput(input, gamedef).item, gamedef);
1075                 m_output_craft_definitions[output_name].push_back(def);
1076         }
1077         virtual void clear()
1078         {
1079                 for (int type = 0; type <= craft_hash_type_max; ++type) {
1080                         for (auto &it : m_craft_defs[type]) {
1081                                 for (auto &iit : it.second) {
1082                                         delete iit;
1083                                 }
1084                                 it.second.clear();
1085                         }
1086                         m_craft_defs[type].clear();
1087                 }
1088                 m_output_craft_definitions.clear();
1089         }
1090         virtual void initHashes(IGameDef *gamedef)
1091         {
1092                 // Move the CraftDefs from the unhashed layer into layers higher up.
1093                 std::vector<CraftDefinition *> &unhashed =
1094                         m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
1095                 for (auto def : unhashed) {
1096                         // Initialize and get the definition's hash
1097                         def->initHash(gamedef);
1098                         CraftHashType type = def->getHashType();
1099                         u64 hash = def->getHash(type);
1100
1101                         // Enter the definition
1102                         m_craft_defs[type][hash].push_back(def);
1103                 }
1104                 unhashed.clear();
1105         }
1106 private:
1107         std::vector<std::unordered_map<u64, std::vector<CraftDefinition*> > >
1108                 m_craft_defs;
1109         std::unordered_map<std::string, std::vector<CraftDefinition*> >
1110                 m_output_craft_definitions;
1111 };
1112
1113 IWritableCraftDefManager* createCraftDefManager()
1114 {
1115         return new CCraftDefManager();
1116 }