Repository: griptape-ai/griptape

Issue:
maximum recursion depth exceeded using MarkdownChunker.chunk with certain inputs
If [`BaseChunker.chunk`](https://github.com/griptape-ai/griptape/blob/bdc19214501a80006d5ff44ff4c90707c04086b1/griptape/chunkers/base_chunker.py#L35-L39) ends up having to split using the ` ` separator, and there are multiple ` ` characters in the chunk, then `BaseChunker._chunk_recursively` can end up being called indefinitely until the maximum recursion depth is reached.

I originally hit the issue chunking [an mdx doc of size 929 tokens](https://github.com/EnterpriseDB/docs/blob/6d3e3ec278f9f4af09647ec6f372ea51391c5024/product_docs/docs/pgd/5/cli/command_ref/pgd_show-raft.mdx) using a `max_tokens` of 384 but the simplest possible reproduction I could come up with is:

```python
#!/usr/bin/env python

from griptape.chunkers import MarkdownChunker

chunker = MarkdownChunker(max_tokens=3)

assert len(chunker.chunk("foo bar baz")) == 1
assert len(chunker.chunk("foo bar baz ")) == 2

# This should also yield two chunks but instead hits the recursion max depth
assert len(chunker.chunk("foo  bar baz")) == 2
```

Hints from issue comments:
@collindutter: Thanks again for the great repro @mikewallace1979, I'm on it!@collindutter: @mikewallace1979 this has been released in [1.4.3](https://github.com/griptape-ai/griptape/releases/tag/v1.4.3).@mikewallace1979: @collindutter thanks again for the quick response - confirming I can now chunk the document which triggered the issue :)

Solution patch:
diff --git a/griptape/chunkers/base_chunker.py b/griptape/chunkers/base_chunker.py
index 6f4f9c06..683aa588 100644
--- a/griptape/chunkers/base_chunker.py
+++ b/griptape/chunkers/base_chunker.py
@@ -62,7 +62,7 @@ class BaseChunker(ABC):
 
                 if len(non_empty_subchunks) > 1:
                     # Find what combination of subchunks results in the most balanced split of the chunk.
-                    midpoint_index = self.__find_midpoint_index(subchunks, half_token_count)
+                    midpoint_index = self.__find_midpoint_index(separator, subchunks, half_token_count)
 
                     # Create the two subchunks based on the best separator.
                     first_subchunk, second_subchunk = self.__get_subchunks(separator, subchunks, midpoint_index)
@@ -98,12 +98,12 @@ class BaseChunker(ABC):
 
         return first_subchunk, second_subchunk
 
-    def __find_midpoint_index(self, subchunks: list[str], half_token_count: int) -> int:
+    def __find_midpoint_index(self, separator: ChunkSeparator, subchunks: list[str], half_token_count: int) -> int:
         midpoint_index = -1
         best_midpoint_distance = float("inf")
 
         for index, _ in enumerate(subchunks):
-            subchunk_tokens_count = self.tokenizer.count_tokens("".join(subchunks[: index + 1]))
+            subchunk_tokens_count = self.tokenizer.count_tokens(separator.value.join(subchunks[: index + 1]))
 
             midpoint_distance = abs(subchunk_tokens_count - half_token_count)
             if midpoint_distance < best_midpoint_distance:


Test patch:
diff --git a/tests/unit/chunkers/test_markdown_chunker.py b/tests/unit/chunkers/test_markdown_chunker.py
index 4518f3c3..0862e0e4 100644
--- a/tests/unit/chunkers/test_markdown_chunker.py
+++ b/tests/unit/chunkers/test_markdown_chunker.py
@@ -24,7 +24,7 @@ class TestTextChunker:
         ]
         chunks = chunker.chunk("".join(text))
 
-        assert len(chunks) == 6
+        assert len(chunks) == 7
 
         for chunk in chunks:
             assert chunker.tokenizer.count_tokens(chunk.value) <= MAX_TOKENS
@@ -33,12 +33,14 @@ class TestTextChunker:
         assert chunks[1].value.startswith("## Header 2\nfoo-0")
         assert chunks[2].value.startswith("foo-0.")
         assert chunks[3].value.startswith("## Header 3\nfoo-0")
-        assert chunks[4].value.startswith("foo-10.")
-        assert chunks[5].value.startswith("foo-16.")
+        assert chunks[4].value.startswith("foo-5.")
+        assert chunks[5].value.startswith("foo-12.")
+        assert chunks[6].value.startswith("foo-19.")
 
         assert chunks[0].value.endswith(". foo-5.")
         assert chunks[1].value.endswith(". foo-5.")
         assert chunks[2].value.endswith(". foo-5.")
-        assert chunks[3].value.endswith(". foo-9.")
-        assert chunks[4].value.endswith(". foo-15.")
-        assert chunks[5].value.endswith(". foo-24.")
+        assert chunks[3].value.endswith(". foo-4.")
+        assert chunks[4].value.endswith(". foo-11.")
+        assert chunks[5].value.endswith(". foo-18.")
+        assert chunks[6].value.endswith(". foo-24.")
diff --git a/tests/unit/chunkers/test_text_chunker.py b/tests/unit/chunkers/test_text_chunker.py
index db4d16f8..44edd9ee 100644
--- a/tests/unit/chunkers/test_text_chunker.py
+++ b/tests/unit/chunkers/test_text_chunker.py
@@ -56,12 +56,12 @@ class TestTextChunker:
             assert chunker.tokenizer.count_tokens(chunk.value) <= MAX_TOKENS
 
         assert chunks[0].value.startswith("foo-0!")
-        assert chunks[1].value.startswith("foo-11!")
-        assert chunks[2].value.startswith("foo-17!")
+        assert chunks[1].value.startswith("foo-7!")
+        assert chunks[2].value.startswith("foo-13!")
         assert chunks[3].value.startswith("foo-0.")
 
-        assert chunks[0].value.endswith("! foo-10!")
-        assert chunks[1].value.endswith("! foo-16!")
+        assert chunks[0].value.endswith("! foo-6!")
+        assert chunks[1].value.endswith("! foo-12!")
         assert chunks[2].value.endswith("! foo-24!")
         assert chunks[3].value.endswith(". foo-11.")
 
@@ -92,19 +92,19 @@ class TestTextChunker:
             assert chunker.tokenizer.count_tokens(chunk.value) <= MAX_TOKENS
 
         assert chunks[0].value.startswith("foo-0!")
-        assert chunks[1].value.startswith("foo-11!")
-        assert chunks[2].value.startswith("foo-17!")
+        assert chunks[1].value.startswith("foo-7!")
+        assert chunks[2].value.startswith("foo-13!")
         assert chunks[3].value.startswith("foo-0.")
         assert chunks[4].value.startswith("foo-0?")
-        assert chunks[5].value.startswith("foo-9?")
+        assert chunks[5].value.startswith("foo-7?")
         assert chunks[6].value.startswith("foo-0")
         assert chunks[7].value.startswith("foo-8")
 
-        assert chunks[0].value.endswith("! foo-10!")
-        assert chunks[1].value.endswith("! foo-16!")
+        assert chunks[0].value.endswith("! foo-6!")
+        assert chunks[1].value.endswith("! foo-12!")
         assert chunks[2].value.endswith("! foo-24!")
         assert chunks[3].value.endswith(". foo-11.")
-        assert chunks[4].value.endswith("? foo-8?")
+        assert chunks[4].value.endswith("? foo-6?")
         assert chunks[5].value.endswith("? foo-12?")
         assert chunks[6].value.endswith(" foo-7")
         assert chunks[7].value.endswith(" foo-16")
@@ -138,3 +138,15 @@ class TestTextChunker:
 
         for chunk in chunks:
             assert chunk.reference is None
+
+    def test_midpoint_index_empty_subchunks(self, chunker):
+        # This tests that a midpoint index is correctly found when there are some empty subchunks
+        # Previously ["foo", '', "bar", 'baz'] would be token counted as 'foobarbaz' rather than 'foo  bar baz'
+        #  when calculating the midpoint index.
+        # https://github.com/griptape-ai/griptape/issues/1796
+        chunker.max_tokens = 3
+
+        assert len(chunker.chunk("foo bar baz")) == 1
+        assert len(chunker.chunk("foo bar baz ")) == 2
+
+        assert len(chunker.chunk("foo  bar baz")) == 2