Improve performance of the glob matching

4 files changed, 135 insertions, 23 deletions

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?"));
+    }
+}