opshin icon indicating copy to clipboard operation
opshin copied to clipboard
verified publisher icon OpShin

Fix mutual recursion support in type inference

Open Copilot opened this issue 5 months ago • 4 comments

This PR fixes mutual recursion support in OpShin by implementing a two-pass type inference approach that works for all function scopes.

Problem

Previously, mutual recursion would fail to compile because the type inference system processed functions sequentially. When an earlier function tried to call a later-defined function, the later function wasn't yet in scope:

def even(n: int) -> bool:
    if n == 0:
        return True
    else:
        return odd(n - 1)  # ERROR: 'odd' not yet defined
        
def odd(n: int) -> bool:
    if n == 0:
        return False
    else:
        return even(n - 1)  # This would work since 'even' is already defined

def validator(a: int) -> int:
    return 42

Solution

Implemented a two-pass approach in AggressiveTypeInferencer.visit_sequence():

  1. Pass 1: Extract all function signatures from type annotations and add them to scope, along with processing classes to ensure they're available for function annotations
  2. Pass 2: Process function bodies normally with all function signatures available

This ensures that all function names are available before any function bodies are processed, enabling mutual recursion at any scope level.

Key Features

  • General scope handling: Works for functions at module level, nested functions, and functions inside other constructs
  • Class integration: Handles cases where user-defined classes are defined between mutually recursive functions
  • Robust error handling: If signature extraction fails in the first pass (e.g., due to forward references to classes), it gracefully falls back to second-pass processing
  • Backward compatibility: All existing functionality is preserved
  • Support for various recursion patterns: 2-way, 3-way, and mixed self/mutual recursion

Test Coverage

Added comprehensive test cases covering:

  • Basic mutual recursion (even/odd functions)
  • Three-way mutual recursion patterns
  • Nested function mutual recursion (functions inside other functions)
  • Mutual recursion with classes defined between functions
  • Edge cases with different argument types and counts

The fix handles various mutual recursion scenarios while maintaining full backward compatibility with existing code.

Fixes #524.

💡 You can make Copilot smarter by setting up custom instructions, customizing its development environment and configuring Model Context Protocol (MCP) servers. Learn more Copilot coding agent tips in the docs.

Copilot avatar Sep 17 '25 10:09 Copilot

✅ Binary Size Check Passed

Binary Size Comparison Report 
Loading baseline measurements...
Measuring current binary sizes...
Measuring liquidity_pool...
Failed to compile examples/smart_contracts/liquidity_pool.py with O0: /home/runner/.cache/pypoetry/virtualenvs/opshin-CZi3rn_I-py3.12/lib/python3.12/site-packages/uplc/lexer.py:48: SyntaxWarning: invalid escape sequence 's'
  self.lexer.ignore("s+")
Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/liquidity_pool.py", line 1
    """
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O0: FAILED
Failed to compile examples/smart_contracts/liquidity_pool.py with O1: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/liquidity_pool.py", line 1
    """
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O1: FAILED
Failed to compile examples/smart_contracts/liquidity_pool.py with O2: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/liquidity_pool.py", line 1
    """
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O2: FAILED
Failed to compile examples/smart_contracts/liquidity_pool.py with O3: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/liquidity_pool.py", line 1
    """
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O3: FAILED
Measuring assert_sum...
Failed to compile examples/smart_contracts/assert_sum.py with O0: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/assert_sum.py", line 1
    #!opshin
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O0: FAILED
Failed to compile examples/smart_contracts/assert_sum.py with O1: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/assert_sum.py", line 1
    #!opshin
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O1: FAILED
Failed to compile examples/smart_contracts/assert_sum.py with O2: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/assert_sum.py", line 1
    #!opshin
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O2: FAILED
Failed to compile examples/smart_contracts/assert_sum.py with O3: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/assert_sum.py", line 1
    #!opshin
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O3: FAILED
Measuring marketplace...
Failed to compile examples/smart_contracts/marketplace.py with O0: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/marketplace.py", line 1
    #!/usr/bin/env -S opshin eval spending
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O0: FAILED
Failed to compile examples/smart_contracts/marketplace.py with O1: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/marketplace.py", line 1
    #!/usr/bin/env -S opshin eval spending
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O1: FAILED
Failed to compile examples/smart_contracts/marketplace.py with O2: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/marketplace.py", line 1
    #!/usr/bin/env -S opshin eval spending
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O2: FAILED
Failed to compile examples/smart_contracts/marketplace.py with O3: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/marketplace.py", line 1
    #!/usr/bin/env -S opshin eval spending
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O3: FAILED
Measuring gift...
Failed to compile examples/smart_contracts/gift.py with O0: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/gift.py", line 1
    #!/usr/bin/env -S opshin eval spending
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O0: FAILED
Failed to compile examples/smart_contracts/gift.py with O1: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/gift.py", line 1
    #!/usr/bin/env -S opshin eval spending
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O1: FAILED
Failed to compile examples/smart_contracts/gift.py with O2: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/gift.py", line 1
    #!/usr/bin/env -S opshin eval spending
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O2: FAILED
Failed to compile examples/smart_contracts/gift.py with O3: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/gift.py", line 1
    #!/usr/bin/env -S opshin eval spending
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O3: FAILED
Measuring wrapped_token...
Failed to compile examples/smart_contracts/wrapped_token.py with O0: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/wrapped_token.py", line 1
    #!opshin
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O0: FAILED
Failed to compile examples/smart_contracts/wrapped_token.py with O1: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/wrapped_token.py", line 1
    #!opshin
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O1: FAILED
Failed to compile examples/smart_contracts/wrapped_token.py with O2: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/wrapped_token.py", line 1
    #!opshin
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O2: FAILED
Failed to compile examples/smart_contracts/wrapped_token.py with O3: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/wrapped_token.py", line 1
    #!opshin
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O3: FAILED
Measuring micropayments...
Failed to compile examples/smart_contracts/micropayments.py with O0: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/micropayments.py", line 1
    from opshin.ledger.api_v2 import *
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O0: FAILED
Failed to compile examples/smart_contracts/micropayments.py with O1: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/micropayments.py", line 1
    from opshin.ledger.api_v2 import *
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O1: FAILED
Failed to compile examples/smart_contracts/micropayments.py with O2: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/micropayments.py", line 1
    from opshin.ledger.api_v2 import *
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O2: FAILED
Failed to compile examples/smart_contracts/micropayments.py with O3: Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 539, in main
    perform_command(args)
  File "/home/runner/work/opshin/opshin/opshin/__main__.py", line 369, in perform_command
    raise err from None
  File "examples/smart_contracts/micropayments.py", line 1
    from opshin.ledger.api_v2 import *
SyntaxError: TypeInferenceError: Variable 'PubKeyHash' not initialized at access. You need to define it before using it the first time.
Note that opshin errors may be overly restrictive as they aim to prevent code with unintended consequences.


  O3: FAILED

============================================================
BINARY SIZE COMPARISON REPORT
============================================================

Contract: liquidity_pool
Description: Simple DEX pool
----------------------------------------
  O0: MISSING DATA
  O1: MISSING DATA
  O2: MISSING DATA
  O3: MISSING DATA

Contract: assert_sum
Description: Simple spending validator with assertion
----------------------------------------
  O0: MISSING DATA
  O1: MISSING DATA
  O2: MISSING DATA
  O3: MISSING DATA

Contract: marketplace
Description: Marketplace contract with complex data structures
----------------------------------------
  O0: MISSING DATA
  O1: MISSING DATA
  O2: MISSING DATA
  O3: MISSING DATA

Contract: gift
Description: Gift contract with simple logic
----------------------------------------
  O0: MISSING DATA
  O1: MISSING DATA
  O2: MISSING DATA
  O3: MISSING DATA

Contract: wrapped_token
Description: Dual-use contract to generate a wrapped token
----------------------------------------
  O0: MISSING DATA
  O1: MISSING DATA
  O2: MISSING DATA
  O3: MISSING DATA

Contract: micropayments
Description: Channel for fee-less micropayments
----------------------------------------
  O0: MISSING DATA
  O1: MISSING DATA
  O2: MISSING DATA
  O3: MISSING DATA

Total size change across all contracts: +0 bytes

✅ No significant binary size changes detected
============================================================

No significant binary size changes were detected in this PR.

This report compares the binary sizes of compiled contracts against the baseline from the latest release.

github-actions[bot] avatar Sep 17 '25 11:09 github-actions[bot]

Note that a proper fix for #522 requires this fix too.

nielstron avatar Sep 17 '25 11:09 nielstron

@copilot can you look at my changes and take it from there?

nielstron avatar Sep 21 '25 09:09 nielstron

Overall, the approach looks sounds. But it needs to be more general to handle all possible settings.

Formatting seems invalid too. Run black to format the files correctly.

Addressed the generality concerns by accepting @nielstron's refactor to visit_sequence() and added test cases for nested functions and classes. Fixed formatting and removed unrelated changes in commit f7d9d20.

Copilot avatar Sep 21 '25 09:09 Copilot