tests/test_output_index.py (4)

8-64: Consider adding a helper function for creating rule mocks.

The fixtures have repetitive mock setup code. Consider extracting a helper function to reduce duplication:

def create_rule_mock(mocker, products, name=None):
    mock_products = [
        mocker.Mock(constant_prefix=lambda: prefix, constant_suffix=lambda: suffix)
        for prefix, suffix in products
    ]
    return mocker.Mock(products=lambda: mock_products, name=name)

This would simplify the fixtures:

@pytest.fixture()
def rule_0(mocker):
    return create_rule_mock(
        mocker,
        products=[
            ("test", "-something.txt"),
            ("test", "-something.csv")
        ],
        name="rule_0"
    )

---

92-98: Remove debug print statement.

The print statement on line 96 appears to be for debugging purposes and should be removed.

def test_match_with_empty_components(
    request, rule_empty_suffix, rule_empty_prefix, target, expected_rules
):
    output_index = OutputIndex([rule_empty_suffix, rule_empty_prefix])
-    print(output_index._entries)
    expected = {request.getfixturevalue(rule) for rule in expected_rules}
    assert output_index.match(target) == expected

---

66-81: Add docstring to parameterized test.

The test_match function would benefit from a docstring explaining the test cases:

@pytest.mark.parametrize(
    "target,expected_rules",
    [
        ("test-{wildcard}-something.txt", {"rule_0"}),
        ("test-{wildcard}-something.csv", {"rule_0"}),
        ("test-something.txt", {"rule_0"}),
        ("other/file--something.csv", {"rule_1"}),
        ("other/file-something.csv", {"rule_1"}),
        ("other/not-file-something.csv", set()),
        ("other/file-dupe-something.csv", {"rule_1", "rule_2"}),
    ],
)
def test_match(request, output_index, target, expected_rules):
+    """
+    Test the OutputIndex.match method with various patterns:
+    - Patterns with wildcards
+    - Exact matches
+    - Non-matching patterns
+    - Multiple matching rules
+    """
    expected = {request.getfixturevalue(rule) for rule in expected_rules}
    assert output_index.match(target) == expected

---

137-158: Add edge cases to parametrized tests.

Consider adding more edge cases to test_parametrized_matches:

@pytest.mark.parametrize(
    "target,expected_match",
    [
        ("test.txt", True),
        ("testing.txt", True),
        ("test.doc", False),
        ("other.txt", False),
        ("", False),
        ("test", False),
        ("bad.txt", False),
+        # Add edge cases
+        ("test" * 1000 + ".txt", True),  # Very long filename
+        ("test\n.txt", False),  # Invalid characters
+        ("test/.txt", False),  # Path separator
+        ("TEST.TXT", False),  # Case sensitivity
    ],
)

snakemake/path_modifier.py (1)

28-30: Ensure Consistent Sorting of Prefix Replacements

The use of sorted(replace_prefix.items()) correctly sorts the prefix-replacement pairs based on the prefix. However, since you're using bisect, which requires the list to be sorted, ensure that the prefixes are consistently sorted according to the expected order, especially if prefixes can have varying lengths or characters.

Consider specifying a sorting key for clarity:

self._prefix_replacements = (
-    sorted(replace_prefix.items()) if replace_prefix else None
+    sorted(replace_prefix.items(), key=lambda item: item[0]) if replace_prefix else None
)

Configuration used: CodeRabbit UI
Review profile: CHILL

@pytest.fixture()
def large_ruleset(mocker):
    # Create 1000+ rules to test performance
    return [
        create_rule_mock(
            mocker,
            products=[("prefix" + str(i), "suffix" + str(i))],
            name=f"rule_{i}"
        )
        for i in range(1000)
    ]

#!/bin/bash
# Description: Verify the correctness of prefix matching logic.

# Test: Check the matched prefixes for a sample path.
# Expected: The script should output the correctly matched prefix.

python -c '
prefix_replacements = [("a/b", "x/y"), ("a", "x"), ("a/b/c", "x/y/z")]
path = "a/b/c/d/e"
from bisect import bisect_right

sorted_prefixes = sorted(prefix_replacements, key=lambda x: x[0])
stop_idx = bisect_right(sorted_prefixes, path, key=lambda x: x[0])
prefixes = []
for index in range(stop_idx - 1, -1, -1):
    prefix = sorted_prefixes[index][0]
    if path.startswith(prefix):
        prefixes.append(prefix)
    elif index != stop_idx - 1:
        break
print("Matched prefixes:", prefixes)
'

#!/bin/bash
# Let's analyze the implementation details of the prefix matching logic in the codebase

# First, let's find where this prefix matching logic is used
rg -A 5 "_prefix_replacements" 

# Also check for any tests related to this functionality
fd "test.*\.py" --exec rg -l "prefix.*replacement"

#!/bin/bash
# Let's check the test files specifically for this class and its prefix matching functionality
rg -B 5 -A 10 "class PathModifier" 

# Also look for any test cases that might exercise this functionality
rg -B 2 -A 5 "modify.*path" tests/

snakemake/common/prefix_lookup.py (3)

7-10: Add class and constructor documentation.

While the implementation is clean, adding docstrings would improve code maintainability:

• Document the class purpose and use cases
• Document constructor parameters and sorting behavior

Consider adding:

 class PrefixLookup:
+    """A data structure for efficient prefix-based lookups.
+    
+    This class provides an alternative to trie-based implementations, optimized
+    for prefix matching operations using binary search.
+    """
     def __init__(self, entries: Sequence[tuple[str, V]]) -> None:
+        """Initialize the prefix lookup structure.
+        
+        Args:
+            entries: Sequence of (string, value) pairs. Entries are sorted by
+                    the string component for efficient prefix matching.
+        """
         self._entries = sorted(entries, key=lambda x: x[0])

---

11-12: Add method documentation.

While the implementation is correct, adding a docstring would clarify the return type behavior:

Consider adding:

     def match(self, key: str) -> set[V]:
+        """Return a set of all values whose prefixes match the given key.
+        
+        Args:
+            key: The string to match prefixes against.
+            
+        Returns:
+            A set of values associated with matching prefixes, eliminating duplicates.
+        """
         return set(self.match_iter(key))

---

1-28: Solid implementation that aligns with PR objectives.

This implementation effectively replaces the datrie dependency with a maintainable solution using standard library components. The trade-offs are well-considered:

Advantages:

• No external dependencies
• More maintainable
• Memory efficient for sparse prefixes
• Good performance characteristics (O(log n) binary search)

Considerations:

• Different performance characteristics compared to trie (might be slower for large datasets)
• Memory usage patterns differ from trie structure

The implementation aligns well with the PR's goal of removing the datrie dependency while maintaining functionality.

snakemake/output_index.py (1)

17-18: Consider enhancing the docstring with implementation details.

The docstring could be more informative by including details about:

• The underlying data structure (PrefixLookup)
• Performance characteristics with different rule set sizes
• Usage recommendations for large rule sets

-    """Look up structure for rules, that can be queried by the output products which they create."""
+    """Look up structure for rules, that can be queried by the output products which they create.
+    
+    This implementation uses a prefix-based lookup structure optimized for moderate-sized rule sets.
+    Performance characteristics may vary based on the number of rules and complexity of output patterns.
+    """

tests/test_prefix_lookup.py (2)

4-39: LGTM with suggestions for additional test cases.

The basic functionality tests are well-structured and cover important scenarios including basic matching, multiple matches, no matches, and empty lookup cases.

Consider adding tests for:

1. Invalid input types (e.g., passing None, integers, or other non-string types to match())
2. Very long strings to verify performance characteristics

Here's a suggested additional test:

def test_invalid_inputs():
    lookup = PrefixLookup([("a", 1)])
    with pytest.raises(TypeError):
        lookup.match(None)
    with pytest.raises(TypeError):
        lookup.match(42)

---

1-130: Document performance characteristics in docstring.

Consider adding a module-level docstring that describes:

1. The performance characteristics of the new implementation compared to datrie
2. Any memory usage differences
3. Known limitations or trade-offs

This will help users understand the implications of the change.

Example docstring:

"""Unit tests for PrefixLookup class.

This implementation replaces the previous datrie-based solution with the following characteristics:
- Time complexity: O(X) vs previous O(Y)
- Memory usage: O(X) vs previous O(Y)
- Known limitations: Performance degradation with >1000 prefixes

For large-scale usage (>1000 prefixes), consider [alternative recommendations].
"""

tests/test_output_index.py (1)

8-64: Add docstrings to fixtures for better maintainability.

The fixtures are well-structured and cover various test scenarios. However, adding docstrings would make their purpose and test coverage more explicit.

Example improvement:

 @pytest.fixture()
 def rule_0(mocker):
+    """
+    Creates a mock rule with two products:
+    1. prefix='test', suffix='-something.txt'
+    2. prefix='test', suffix='-something.csv'
+    Used to test multiple products with same prefix but different suffixes.
+    """
     mock_products_rule_0 = [

snakemake/path_modifier.py (1)

Line range hint 69-83: Consider explicit empty prefixes check

The logic for handling prefix matches looks good, but there's a potential edge case in the code flow. When prefixes is empty, the code will still reach the elif prefixes: block and try to access prefixes[0].

Consider this minor improvement for better clarity:

 if len(prefixes) > 1:
     # ambiguous prefixes
     raise WorkflowError(
         "Multiple prefixes ({}) match the path {}. Make sure that the replace_prefix statement "
         "in your module definition does not yield ambiguous matches.".format(
             ", ".join(prefix[0] for prefix in prefixes), path
         )
     )
-elif prefixes:
+elif len(prefixes) == 1:
     # replace prefix
     prefix, replacement = prefixes[0]
     return replacement + path[len(prefix):]
 else:
     # no matching prefix
     return path

Configuration used: CodeRabbit UI
Review profile: CHILL

     def match_iter(self, key: str) -> Generator[V, None, None]:
         """Returns all entries which are prefixes of the given key.
 
         E.g. if "abc" is the key then "abc", "ab", "a", and "" are considered valid prefixes.
+        
+        Args:
+            key: The string to match prefixes against.
+            
+        Returns:
+            Generator yielding values associated with matching prefixes in
+            descending order of prefix length.
+            
+        Time Complexity: O(log n) for binary search + O(k) for yielding k matches
+        Space Complexity: O(1) auxiliary space
+        
+        Raises:
+            TypeError: If key is not a string
         """
+        if not isinstance(key, str):
+            raise TypeError("key must be a string")
+
         stop_idx = bisect.bisect_right(self._entries, key, key=lambda x: x[0])

#!/bin/bash
# Description: Verify test coverage of early stopping optimization

# Check if there are tests verifying the early stopping behavior
rg -A 5 "test.*early.*stop" "tests/test_prefix_lookup.py" || \
rg -A 5 "def test.*prefix.*lookup" "tests/test_prefix_lookup.py"

#!/bin/bash
# Let's first check if the test file exists and see its content
fd "test_prefix_lookup.py" --type f --exec cat {}

#!/bin/bash
# Description: Analyze the performance impact of the new implementation

# Look for existing performance tests or benchmarks
rg -l "benchmark|performance|test.*match" --type py

# Check for any existing performance-related issues
ast-grep --pattern 'def test_$_performance($_) { $$$ }'

#!/bin/bash
# Check test implementations for output_index and prefix_lookup
cat tests/test_output_index.py tests/test_prefix_lookup.py

# Look for any performance-related test cases or benchmarks specifically for matching
rg "def test.*match|performance.*match" tests/test_output_index.py tests/test_prefix_lookup.py -A 5

#!/bin/bash
# Search for existing PrefixLookup usage patterns in the codebase
echo "Searching for existing PrefixLookup usage..."
rg -l "PrefixLookup" --type py

# Search for datrie usage to ensure complete migration
echo "Checking for remaining datrie usage..."
rg -l "datrie" --type py

#!/bin/bash
# Check actual usage patterns of PrefixLookup in the codebase
echo "=== PrefixLookup usage in output_index.py ==="
rg "PrefixLookup" -B 2 -A 2 snakemake/output_index.py

echo -e "\n=== PrefixLookup usage in path_modifier.py ==="
rg "PrefixLookup" -B 2 -A 2 snakemake/path_modifier.py

echo -e "\n=== PrefixLookup implementation ==="
cat snakemake/common/prefix_lookup.py

snakemake/common/prefix_lookup.py (3)

8-10: Enhance docstring with performance characteristics.

Since this class replaces the datrie implementation, it would be helpful to document:

• Time complexity for initialization and lookups
• Space complexity
• Performance characteristics compared to the previous implementation

Example addition:

 class PrefixLookup:
-    """A data structure for efficiently looking up entries by their prefix."""
+    """A data structure for efficiently looking up entries by their prefix.
+    
+    Time Complexity:
+        - Initialization: O(n log n) where n is the number of entries
+        - Lookup: O(m log n) where m is the number of matching prefixes
+    Space Complexity: O(n)
+    
+    Note: This implementation uses Python's built-in data structures as an alternative
+    to the previous trie-based implementation. While it may have different performance
+    characteristics, it eliminates external dependencies.
+    """

---

11-15: Add input validation for empty strings and None values.

While the implementation is correct, it would be more robust with input validation.

Consider adding validation:

 def __init__(self, entries: Sequence[tuple[str, V]]) -> None:
+    if not entries:
+        self._entries = []
+        return
+    
+    # Validate inputs
+    for key, _ in entries:
+        if not isinstance(key, str):
+            raise TypeError(f"Keys must be strings, got {type(key)}")
+        if key is None:
+            raise ValueError("Keys cannot be None")
+
     grouped = defaultdict(list)
     for key, value in entries:
         grouped[key].append(value)
     self._entries = sorted(grouped.items(), key=lambda x: x[0])

---

21-36: Add detailed algorithm explanation in comments.

The implementation is efficient with clever optimizations, but the algorithm's details could be better documented.

Consider adding more detailed comments:

 def match_iter(self, query: str) -> Generator[V, None, None]:
     """Yields all entries which are prefixes of the given key.
 
     E.g. if "abc" is the key then "abc", "ab", "a", and "" are considered valid prefixes.
+    
+    Algorithm:
+    1. Use binary search to find the insertion point for the query
+    2. Iterate backwards from this point, as longer prefixes come later
+    3. For each potential prefix:
+       - If it's a valid prefix, yield its entries
+       - Track the length of the last matched prefix
+       - Stop if we find a non-matching prefix shorter than last match
+       (as all remaining prefixes would be non-matching)
+    
+    This approach ensures O(m log n) complexity where:
+    - n is the total number of unique prefixes
+    - m is the number of matching prefixes
     """

snakemake/output_index.py (1)

17-18: Consider enhancing the docstring.

While the docstring explains the purpose, it could be enhanced with details about:

• The underlying data structure used (PrefixLookup)
• Performance characteristics
• Usage examples

tests/test_prefix_lookup.py (1)

4-28: Add docstrings to test functions for better documentation.

The test implementations are well-structured and cover essential scenarios. Consider adding docstrings to explain the purpose of each test function, making it easier for other developers to understand the test coverage.

Example for test_basic_match:

def test_basic_match():
    """
    Test basic prefix matching functionality.
    Verifies that single prefix matches return the correct associated value.
    """

Configuration used: CodeRabbit UI
Review profile: CHILL

#!/bin/bash
# Search for test files that might contain performance tests
echo "Searching for existing performance tests..."
rg -l "performance|benchmark" tests/

# Look for actual usage patterns to understand typical dataset sizes
echo "Analyzing typical usage patterns..."
rg -A 5 "PrefixLookup\(" 

# Check if there are any TODO comments about performance
echo "Checking for performance-related TODOs..."
rg -i "todo.*performance|performance.*todo"

#!/bin/bash
# Let's analyze the implementation details and usage patterns more thoroughly

# Check the test file for performance-critical test cases
echo "Analyzing test coverage..."
cat tests/test_prefix_lookup.py

# Look for actual rule processing to understand real-world usage
echo "Checking rule processing implementation..."
rg -A 10 "def match.*Rule" snakemake/output_index.py

# Check for any performance-related comments or documentation
echo "Checking documentation and comments..."
rg -i "performance|efficient|optimization" snakemake/common/prefix_lookup.py

#!/bin/bash
# Description: Find and analyze test files to understand the scale of rules being processed

# Look for test files with rule definitions
echo "Test files with rule definitions:"
rg -l "class.*Rule" tests/

# Look for actual usage patterns
echo "\nTypical usage patterns:"
rg -A 5 "OutputIndex\(" 

#!/bin/bash
# Let's analyze the test cases to understand the scale and patterns being tested

# Look at the test file content to understand test coverage
echo "Test file content:"
cat tests/test_output_index.py

# Look for Rule class definition to understand what products() returns
echo "\nRule class definition:"
rg -A 10 "class.*Rule.*:" snakemake/

#!/bin/bash
# Search for previous test files related to trie implementation
rg -l "trie|datrie" "tests/"

# Compare test patterns between old and new implementations
for f in $(rg -l "trie|datrie" "tests/"); do
  echo "=== $f ==="
  rg "def test_" "$f"
done

#!/bin/bash
# Let's try a different approach to find the old implementation and its tests
# First, let's check git history for files related to trie or datrie
git log -p --all | rg -l "trie|datrie"

# Also search for any deleted test files in git history
git log --diff-filter=D --summary | rg "delete.*test.*trie"

# Search for imports of datrie in the codebase
rg "import.*datrie" 

# Look for any references to trie or datrie in the entire codebase
rg -i "trie|datrie" -A 2 -B 2

#!/bin/bash
# Let's check the current implementation of PrefixLookup
fd "prefix_lookup.py" --type f

# Once found, let's examine its content to understand the implementation
fd "prefix_lookup.py" --type f --exec cat {}

# Let's also check for any related documentation or implementation notes
rg -i "prefix.*lookup" -A 3 -B 3

snakemake/common/prefix_lookup.py (1)

46-56: Enhance docstring with edge case examples.

The implementation is correct, but the docstring could be more helpful with examples.

Consider updating the docstring:

-    """Utility function that gives the common prefix of two strings.
-
-    Except, if the strings are identical, returns the string minus one letter.
-    Behaviour is undefined if either string is empty.
-    """
+    """Returns the common prefix of two strings.
+
+    Examples:
+        >>> _common_prefix("abc", "abd")
+        "ab"
+        >>> _common_prefix("abc", "abc")  # Special case: identical strings
+        "ab"
+
+    Note:
+        Behavior is undefined if either string is empty.
+    """

🧰 Tools

🪛 Ruff (0.8.2)

52-52: Loop control variable i not used within loop body

(B007)

Configuration used: CodeRabbit UI
Review profile: CHILL
Plan: Pro

Learnt from: leoschwarz
PR: snakemake/snakemake#3176
File: snakemake/output_index.py:20-28
Timestamp: 2024-11-12T11:27:07.572Z
Learning: In `snakemake/output_index.py`, the current matching logic in `OutputIndex.match` with binary search and backward iteration is acceptable, and suggestions to replace it with a simple iteration over all entries are not necessary.

snakemake/common/prefix_lookup.py (3)

17-19: Consider clarifying that duplicates are removed in the return value

The method returns a set, which automatically removes duplicates. This might be worth mentioning in the docstring for clarity.

-    def match(self, query: str) -> set[V]:
-        """Returns a set of all entry values which are attached to prefixes of the given key."""
+    def match(self, query: str) -> set[V]:
+        """Returns a set of all entry values which are attached to prefixes of the given key.
+        
+        Note: Duplicate values are automatically removed as this returns a set.
+        """

---

21-28: Docstring should clarify what's actually yielded

There's a discrepancy between the docstring and the implementation. The docstring states that it "Yields entries as (key, value) tuples" but the implementation in line 38 yields (k, entry) pairs.

-        """Yields all entries which are prefixes of the given key.
-
-        E.g. if "abc" is the key then "abc", "ab", "a", and "" are considered
-        valid prefixes.
-
-        Yields entries as (key, value) tuples as supplied to __init__()
+        """Yields all entries which are prefixes of the given key.
+
+        E.g. if "abc" is the key then "abc", "ab", "a", and "" are considered
+        valid prefixes.
+
+        Yields tuples of (prefix, value) where prefix is the matching prefix string
+        and value is the associated value from the original entries.

---

46-56: Handle edge cases in _common_prefix method

The current implementation doesn't handle the case where strings are identical, despite the docstring mentioning it should return the string minus one letter. Also, it doesn't explicitly handle empty strings.

     def _common_prefix(self, s1: str, s2: str) -> str:
         """Utility function that gives the common prefix of two strings.
 
         Except, if the strings are identical, returns the string minus one letter.
         Behaviour is undefined if either string is empty.
         """
+        # Handle identical strings case
+        if s1 == s2:
+            return s1[:-1] if s1 else ""
+            
         for i, (l1, l2) in enumerate(zip(s1, s2)):
             if l1 != l2:
                 break
 
         return s1[:i]

The static analysis warning about the loop variable i not being used within the loop body can be ignored, as it's correctly used after the loop.

🧰 Tools

🪛 Ruff (0.8.2)

52-52: Loop control variable i not used within loop body

(B007)

Configuration used: CodeRabbit UI
Review profile: CHILL
Plan: Pro