From 65cc87b1383f37b4b423d4beb42dfe573c1ba3ea Mon Sep 17 00:00:00 2001 From: Linnea Gräf Date: Sun, 10 Nov 2024 23:36:59 +0100 Subject: Improve performance of the glob matching --- build.gradle | 8 +++ src/main/java/com/notnite/gloppers/GlobUtil.java | 70 ++++++++++++++++++++++ .../gloppers/mixin/HopperBlockEntityMixin.java | 46 +++++++------- .../java/com/notnite/gloppers/GlobUtilTest.java | 34 +++++++++++ 4 files changed, 135 insertions(+), 23 deletions(-) create mode 100644 src/main/java/com/notnite/gloppers/GlobUtil.java create mode 100644 src/test/java/com/notnite/gloppers/GlobUtilTest.java diff --git a/build.gradle b/build.gradle index 5c9a3c3..1996da3 100644 --- a/build.gradle +++ b/build.gradle @@ -18,6 +18,10 @@ dependencies { minecraft "com.mojang:minecraft:${project.minecraft_version}" mappings "net.fabricmc:yarn:${project.yarn_mappings}:v2" modImplementation "net.fabricmc:fabric-loader:${project.loader_version}" + + + testImplementation ("org.junit.jupiter:junit-jupiter:5.7.1") + testRuntimeOnly ("org.junit.platform:junit-platform-launcher") } processResources { @@ -32,6 +36,10 @@ tasks.withType(JavaCompile).configureEach { it.options.release = 21 } +tasks.withType(Test).configureEach { + useJUnitPlatform() +} + java { withSourcesJar() diff --git a/src/main/java/com/notnite/gloppers/GlobUtil.java b/src/main/java/com/notnite/gloppers/GlobUtil.java new file mode 100644 index 0000000..38d0e44 --- /dev/null +++ b/src/main/java/com/notnite/gloppers/GlobUtil.java @@ -0,0 +1,70 @@ +package com.notnite.gloppers; + +import java.util.BitSet; + +public class GlobUtil { + + /** + * Match a string against a glob. + */ + public static boolean matchGlob(String name, String glob) { + // While iterating over the name, every prefix of the glob that is matched has a bit set in this bitset + // For example: if we have iterated over the string "abb" and our glob is "*bb" the bits 1 and 2 would be set, + // since our current string matches both "*b" and "*bb". After we have iterated over the entirety of the string + // We can simply check if the highest bit is set, in which case our entire string matched the entire glob + // (since the entire glob is the longest prefix of the glob). + var bitSet = new BitSet(glob.length() + 1); + var swapBitSet = new BitSet(glob.length() + 1); + + // Set the first prefix of the glob (the empty prefix) as matched + bitSet.set(0); + + // Iterate over all chars + for (int i = 0; i < name.length(); i++) { + char c = name.charAt(i); + + int nextSetBit = -1; + + // Iterate over all existing matches and try to advance them by one glob char + while (true) { + nextSetBit = bitSet.nextSetBit(nextSetBit + 1); + if (nextSetBit == -1 || nextSetBit == glob.length()) break; + char globChar = glob.charAt(nextSetBit); + switch (globChar) { + case '?': // In case of a question mark (any single character matches) + // Set the next bit as matched + swapBitSet.set(nextSetBit + 1); + break; + case '*': // In case of a question mark (any number of characters matches) + // Set the current bit as matched (since we allow this character to be matched multiple times) + swapBitSet.set(nextSetBit); + // Set the next bit as matched + swapBitSet.set(nextSetBit + 1); + break; + default: // No special character + if (c == globChar) { // If the glob char is correct on its own + swapBitSet.set(nextSetBit + 1); + } + break; + } + } + // If there are no currently matched glob prefixes (including the empty one), there is no match. + if (swapBitSet.isEmpty()) return false; + // Swap the swap bit set for the main one and clear the new swap bit set so it can be filled again. + var temp = swapBitSet; + swapBitSet = bitSet; + bitSet = temp; + swapBitSet.clear(); + } + + // Since * globs can match 0 characters, we need to loop over the remaining bitset with pseudo "empty" + // characters, in order to allow the glob to end with a * + for (int i = glob.length() - 1; i >= 0; i--) { + char globChar = glob.charAt(i); + if (globChar != '*') break; + if (bitSet.get(i)) return true; + } + return bitSet.get(glob.length()); + } + +} diff --git a/src/main/java/com/notnite/gloppers/mixin/HopperBlockEntityMixin.java b/src/main/java/com/notnite/gloppers/mixin/HopperBlockEntityMixin.java index 1069e6d..06eb93e 100644 --- a/src/main/java/com/notnite/gloppers/mixin/HopperBlockEntityMixin.java +++ b/src/main/java/com/notnite/gloppers/mixin/HopperBlockEntityMixin.java @@ -3,49 +3,49 @@ package com.notnite.gloppers.mixin; import com.llamalad7.mixinextras.injector.wrapoperation.Operation; import com.llamalad7.mixinextras.injector.wrapoperation.WrapOperation; import com.llamalad7.mixinextras.sugar.Local; +import com.notnite.gloppers.GlobUtil; import net.minecraft.block.entity.Hopper; import net.minecraft.block.entity.HopperBlockEntity; import net.minecraft.entity.ItemEntity; import net.minecraft.inventory.Inventory; import net.minecraft.item.ItemStack; -import net.minecraft.util.math.BlockPos; +import net.minecraft.text.PlainTextContent; import net.minecraft.util.math.Direction; -import net.minecraft.world.World; import org.spongepowered.asm.mixin.Mixin; import org.spongepowered.asm.mixin.Unique; import org.spongepowered.asm.mixin.injection.At; import org.spongepowered.asm.mixin.injection.Inject; import org.spongepowered.asm.mixin.injection.callback.CallbackInfoReturnable; +import java.util.BitSet; + @Mixin(HopperBlockEntity.class) public abstract class HopperBlockEntityMixin { + @Unique private static boolean canTransfer(Inventory to, ItemStack stack) { - try { - if (to instanceof HopperBlockEntity) { - var hopperName = ((HopperBlockEntity) to).getName().copyContentOnly().getString(); - var itemRegistryEntry = stack.getRegistryEntry().getKey(); - if (itemRegistryEntry.isEmpty()) return false; - var itemName = itemRegistryEntry.get().getValue().getPath(); + // Check if destination inventory is a hopper + if (!(to instanceof HopperBlockEntity hopperBlockEntity)) return true; + + // Extract hopper name + // TODO: why use .getContent() (it used to be .copyContentOnly(), but i didn't see a point in that either) + var nameContent = hopperBlockEntity.getName().getContent(); + if (!(nameContent instanceof PlainTextContent plainTextContent)) return true; + var hopperName = plainTextContent.string(); + + // Check if hopper is a glopper + if (!hopperName.startsWith("!")) return true; + var glob = hopperName.substring(1); - if (hopperName.startsWith("!")) { - var globs = hopperName.substring(1).split(","); - for (var glob : globs) { - var strippedGlob = glob.replaceAll("[^a-zA-Z0-9_*?]", ""); - var regex = strippedGlob.replace(".", "\\.").replace("*", ".*").replace("?", "."); - if (itemName.matches(regex)) return true; - } + // Extract item stack name + var itemRegistryEntry = stack.getRegistryEntry().getKey(); + if (itemRegistryEntry.isEmpty()) return false; + var itemName = itemRegistryEntry.get().getValue().getPath(); - // No globs matched, so don't transfer - return false; - } - } - } catch (Exception e) { - // ignored - } + // Check if itemstack matches glob + if (!GlobUtil.matchGlob(itemName, glob)) return false; - // Doesn't have a glob (or exception), so transfer return true; } diff --git a/src/test/java/com/notnite/gloppers/GlobUtilTest.java b/src/test/java/com/notnite/gloppers/GlobUtilTest.java new file mode 100644 index 0000000..064ced1 --- /dev/null +++ b/src/test/java/com/notnite/gloppers/GlobUtilTest.java @@ -0,0 +1,34 @@ +package com.notnite.gloppers; + +import org.junit.jupiter.api.Test; + +import static org.junit.jupiter.api.Assertions.*; + +class GlobUtilTest { + @Test + public void testGlobBeginning() { + assertTrue(GlobUtil.matchGlob("test_id", "*_id")); + assertTrue(GlobUtil.matchGlob("test__id", "*_id")); + assertFalse(GlobUtil.matchGlob("testid", "*_id")); + } + + @Test + public void testRepeatedWildcards() { + assertTrue(GlobUtil.matchGlob("test_id", "*_*")); + assertTrue(GlobUtil.matchGlob("test_id", "**_*")); + assertTrue(GlobUtil.matchGlob("test_id", "*?_*")); + assertFalse(GlobUtil.matchGlob("testid", "*?_*")); + } + + @Test + public void testGlobEnd() { + assertTrue(GlobUtil.matchGlob("test_id", "test_*")); + assertTrue(GlobUtil.matchGlob("test_id", "test_i?")); + assertFalse(GlobUtil.matchGlob("test_id", "test_?")); + } + + @Test + public void testSinglePlaceholder() { + assertTrue(GlobUtil.matchGlob("test_id", "tes?_i?")); + } +} -- cgit