Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fix ModBuiltin not able to handle n=0 #1935

Open
wants to merge 2 commits into
base: main
Choose a base branch
from

Conversation

ClementWalter
Copy link

@ClementWalter ClementWalter commented Feb 4, 2025

TITLE

Description

Fixes a bug where fill_memory would return an error if the number of elements to fill is 0.

See also the python implementation of fill_memory in cairo-lang: https://github.com/starkware-libs/cairo-lang/blob/8276ac35830148a397e1143389f23253c8b80e93/src/starkware/cairo/lang/builtins/modulo/mod_builtin_runner.py#L349-L352

Resolves #1934

Checklist

  • Linked to Github Issue
  • Unit tests added
  • Integration tests added.
  • This change requires new documentation.
    • Documentation has been added/updated.
    • CHANGELOG has been updated.

@FrancoGiachetta
Copy link
Contributor

Hi there!
The PR requires the changelog to be updated in order to pass that check.

@JulianGCalderon
Copy link
Contributor

Hi @ClementWalter! Thanks for the contribution. Could you add a test with the failing case that you mentioned?

@ClementWalter
Copy link
Author

I don’t see where to actually add tests. It seems like the function is currently not tested at all

I also see that in the places where you actually test the mod builtins, you left relevant TODOs

// TODO: Import directly from common library once released
from cairo_programs.mod_builtin_feature.common.modulo import ModBuiltin, UInt384, run_mod_p_circuit

Which would actually have shown the issue. Should I update this?

@gabrielbosio
Copy link
Collaborator

@ClementWalter:

I don’t see where to actually add tests. It seems like the function is currently not tested at all

The function mod_builtin_fill_memory is covered in the following tests:

  • tests::cairo_run_test::cairo_run_apply_poly
  • tests::cairo_run_test::cairo_run_mod_builtin
  • tests::cairo_run_test::cairo_run_mod_builtin_failure
  • tests::cairo_run_test::cairo_run_apply_poly_proof
  • tests::cairo_run_test::cairo_run_mod_builtin_large_batch_size
  • tests::cairo_run_test::cairo_run_mod_builtin_large_batch_size_failure
  • tests::cairo_run_test::cairo_run_mod_builtin_proof
  • tests::cairo_run_test::cairo_run_mod_builtin_large_batch_size_proof
  • vm::runners::builtin_runner::modulo::tests::test_air_private_input_all_cairo
  • math_utils::tests::mul_inv_x_by_x_is_1
  • tests::cairo_run_test::cairo_run_apply_poly
  • tests::cairo_run_test::cairo_run_inv_mod_p_uint512
  • tests::cairo_run_test::cairo_run_mod_builtin
  • program_hash::tests::test_compute_program_hash_chain::case_2_field_arithmetic
  • tests::cairo_run_test::cairo_run_mod_builtin_large_batch_size
  • tests::cairo_run_test::cairo_run_overflowing_dict
  • vm::runners::builtin_runner::output::tests::get_allocated_memory_units

A quick way of testing this is by adding a test case in vm_core that forces add_mod_ptr_n or mul_mod_ptr_n to be 0. With forcing I mean overriding one of the args. This would be enough to keep coverage at a reasonable value.

I also see that in the places where you actually test the mod builtins, you left relevant TODOs

// TODO: Import directly from common library once released
from cairo_programs.mod_builtin_feature.common.modulo import ModBuiltin, UInt384, run_mod_p_circuit
Which would actually have shown the issue. Should I update this?

I tried uncommenting those imports on main and tests passed.
For example, in cairo_programs/mod_builtin_feature/apply_poly.cairo:

// TODO: Import directly from common library once released
from cairo_programs.mod_builtin_feature.common.modulo import ModBuiltin, UInt384, run_mod_p_circuit
// from starkware.cairo.common.modulo import run_mod_p_circuit
// from starkware.cairo.common.cairo_builtins import ModBuiltin, UInt384

I tried leaving it like this:

// TODO: Import directly from common library once released
// from cairo_programs.mod_builtin_feature.common.modulo import ModBuiltin, UInt384, run_mod_p_circuit
from starkware.cairo.common.modulo import run_mod_p_circuit
from starkware.cairo.common.cairo_builtins import ModBuiltin, UInt384

And the related tests passed without errors.

Given this, I think it's not necessary to uncomment those imports for now but I will keep you updated when it would be necessary.

@JulianGCalderon
Copy link
Contributor

Hi @ClementWalter! I'm not sure that the fix in the right place.

  • Right now the n==0 logic is in the fetch_builtin_params closure, which only fetches the BuiltinRunner given the BuiltinName.
  • I think its better to move the n==0 logic to the fill_memory function, so that its analogous to the python implementation:
    pub fn fill_memory(
    memory: &mut Memory,
    add_mod: Option<(Relocatable, &ModBuiltinRunner, usize)>,
    mul_mod: Option<(Relocatable, &ModBuiltinRunner, usize)>,
    ) -> Result<(), RunnerError> {

Would this change also fix the issue?

@ClementWalter
Copy link
Author

@JulianGCalderon it will probably work as well, as you prefer. I however don't manage to do neither make deps nor make deps-macos locally so I'm unable to push this to merge because I don't manage to run the tests locally, and so to add some

@JulianGCalderon
Copy link
Contributor

@ClementWalter could you share the error message you get when running make deps-macos? We may be able to help you with that.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

The ModBuiltins runner is not able to manage empty add or mul
4 participants