feat: add source mapping for calibration expansion

kalzoo commented 6 months ago

This PR allows the (Rust package) user to do the following:

Expand a single instruction in a self-descriptive, recursive way. That is, expand an instruction using its calibrations, and alongside the newly expanded instructions, receive an object describing the calibration decisions made and which of the new instructions are a result of which calibration decisions.
Expand an entire program in the same way, receiving not only the expanded program but a source mapping explaining how every instruction in the new program was derived from the first one: either it was expanded (and it will show the expanded instruction as well as the DEFCAL [MEASURE]s used to expand it) or it was not (and it will yield the instruction index in both source and target program which contains it)

Reviewer:

Please consider the two comments suggesting a breaking change to the MeasureCalibrationDefinition and Calibration structs. This would make them somewhat more similar to DEFFRAME in that they would have identifiers that could be used to index them without respect to their instruction bodies. We could also take the chance to rename Calibration to CalibrationDefinition for consistency.
- I have made this change, but in a way that should not break some python consumers.
- All of the original @propertys are there, so this will only break users who construct and modify calibrations and measure calibrations. I could add additional setters to help migrate, but there's only one __new__ and it doesn't feel right to leave those behind.
Please take a look at the new tests and consider the SourceMap format. Do you see any shortcomings?
Please look at the CalibrationSet#_expand method and those nearby.
- I'd like to have this only construct a CalibrationExpansion when that is returned to the user; I first tried an expansion: Option<&mut CalibrationExpansion> argument, but that doesn't work well here because that doesn't have a sensible default.
- So instead I went with build_source_map which skips most of the work involved in calibration expansion source mapping while still technically constructing one which is then discarded prior to return from CalibrationSet.expand.
- Can you suggest a more elegant solution? I want to share logic between expand-with-source-map and expand-without-source-map while not doing any source mapping work if one isn't going to be returned.

TODOs:

[x] Fix the bug in program calibration expansion source mapping
[x] Restore the "fast path" to instruction calibration expansion when no source map is desired. In the current implementation, it's built in all cases and then thrown away in some in order to maintain the existing API.
[x] (maybe, at request) An ergonomic reverse-mapping to allow looking up the source instruction that resulted in a given target instruction. That can always be built by the user, but it might be nice to have one here since the source mapping structure takes a moment to grok even for an experienced Quil dev.
[ ] (maybe) implement source mapping for parsing. This could be done on an experimental branch just to validate that this PR has the right API to support that.

Closes #366

github-actions[bot] commented 6 months ago

PR Preview Action v1.4.8 :---: :rocket: Deployed preview to https://rigetti.github.io/quil-rs/pr-preview/pr-370/ on branch quil-py-docs at 2024-10-12 00:42 UTC

mhodson-rigetti commented 6 months ago

As much as I can read Rust, this is making sense to me. On the first point about a lurking bug, I wonder if impl SourceMapRange for CalibrationExpansion contains() is incomplete as containment is only by the index being valid, not that it also came from the same calibration? On the third point about reverse-mapping help, if I could see the pattern for this implemented using only the Python bindings as a recipe I think I'd be fine, but if doing that means you might as well codify on the Rust side, happy for that also!

kalzoo commented 6 months ago

As much as I can read Rust, this is making sense to me. On the first point about a lurking bug, I wonder if impl SourceMapRange for CalibrationExpansion contains() is incomplete as containment is only by the index being valid, not that it also came from the same calibration? On the third point about reverse-mapping help, if I could see the pattern for this implemented using only the Python bindings as a recipe I think I'd be fine, but if doing that means you might as well codify on the Rust side, happy for that also!

Hey, thanks @mhodson-rigetti . I've added python bindings and docs but no example (yet) - I'll have to think about how best to expose those direct mappings from source to target. Right now (following our chat a week ago) I made the structure recursive to model the recursive nature of calibration expansion, and that's the least intuitive part in practical use, because each level of expansion has its own index basis. There's an example describing that problem in the python docstrings now.

You were right about SourceMapRange for exactly that reason - two ranges might not share the same basis and the SourceMapRange doesn't have enough information to make that clear. I just removed SourceMapRange altogether in this iteration, I don't think this functionality needs to be so general-purpose just yet.

The lingering bug though was actually fixed in this commit and was something prompted by our chat a week ago - certain instructions being yoinked out of the instruction body and thus (necessarily) out the source map.

bramathon commented 1 month ago

Just wanted to check on the status of this - it's important for pulse plotting to work.

bramathon commented 1 month ago

I'm a little surprised by the extent of the changes in this PR. I was expecting something more along the lines of this:

from quil.program import Program
from typing import Tuple, List

def expand_with_source_mapping(program: Program) -> Tuple[Program, List[int]]:
    """
    Expand any instructions in the program which have a matching calibration, leaving the others
    unchanged. 

    :param program: A quil.Program.
    :return: A quil.Program with the instructions expanded and a source map.
    The source map is a list with the length of the expanded instructions, and indicates the index
    of the logical instruction in the original program from which the expanded instruction originated.
    """
    instructions = program.body_instructions
    calibrations = program.calibrations
    expanded_program = program.clone_without_body_instructions()

    source_map = []
    expanded_instructions = []
    for logical_index, inst in enumerate(instructions):
        expanded_instruction = calibrations.expand(inst, [])
        source_map += [logical_index]*len(expanded_instruction)
        expanded_instructions += expanded_instruction
    expanded_program.add_instructions(expanded_instructions)
    return expanded_program, source_map

expanded_program, source_map = expand_with_source_mapping(quil_program)
default_expanded_program = quil_program.expand_calibrations()
assert expanded_program == default_expanded_program

kalzoo commented 3 weeks ago

I'm a little surprised by the extent of the changes in this PR. I was expecting something more along the lines of this:

from quil.program import Program
from typing import Tuple, List

def expand_with_source_mapping(program: Program) -> Tuple[Program, List[int]]:
    """
    Expand any instructions in the program which have a matching calibration, leaving the others
    unchanged. 

    :param program: A quil.Program.
    :return: A quil.Program with the instructions expanded and a source map.
    The source map is a list with the length of the expanded instructions, and indicates the index
    of the logical instruction in the original program from which the expanded instruction originated.
    """
    instructions = program.body_instructions
    calibrations = program.calibrations
    expanded_program = program.clone_without_body_instructions()

    source_map = []
    expanded_instructions = []
    for logical_index, inst in enumerate(instructions):
        expanded_instruction = calibrations.expand(inst, [])
        source_map += [logical_index]*len(expanded_instruction)
        expanded_instructions += expanded_instruction
    expanded_program.add_instructions(expanded_instructions)
    return expanded_program, source_map

expanded_program, source_map = expand_with_source_mapping(quil_program)
default_expanded_program = quil_program.expand_calibrations()
assert expanded_program == default_expanded_program

@bramathon that snippet doesn't:

break out recursive calibrations
capture which calibration was used to do the expansion

Some of the diff, also, improves how calibrations are handled and matched

bramathon commented 3 weeks ago

Yup, that's true. I don't have any need for those things for my use case.

On Fri, Oct 11, 2024, 20:00 Kalan @.***> wrote:

I'm a little surprised by the extent of the changes in this PR. I was expecting something more along the lines of this:

from quil.program import Programfrom typing import Tuple, List def expand_with_source_mapping(program: Program) -> Tuple[Program, List[int]]: """ Expand any instructions in the program which have a matching calibration, leaving the others unchanged. :param program: A quil.Program. :return: A quil.Program with the instructions expanded and a source map. The source map is a list with the length of the expanded instructions, and indicates the index of the logical instruction in the original program from which the expanded instruction originated. """ instructions = program.body_instructions calibrations = program.calibrations expanded_program = program.clone_without_body_instructions()
source_map = []
expanded_instructions = []
for logical_index, inst in enumerate(instructions):
    expanded_instruction = calibrations.expand(inst, [])
    source_map += [logical_index]*len(expanded_instruction)
    expanded_instructions += expanded_instruction
expanded_program.add_instructions(expanded_instructions)
return expanded_program, source_map
expanded_program, source_map = expand_with_source_mapping(quil_program)default_expanded_program = quil_program.expand_calibrations()assert expanded_program == default_expanded_program

@bramathon https://github.com/bramathon that snippet doesn't:

break out recursive calibrations

capture which calibration was used to do the expansion

Some of the diff, also, improves how calibrations are handled and matched

— Reply to this email directly, view it on GitHub https://github.com/rigetti/quil-rs/pull/370#issuecomment-2407972352, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAEWA7XSPPA5YGRQB4JXV4DZ3AN5PAVCNFSM6AAAAABHGSS7PSVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDIMBXHE3TEMZVGI . You are receiving this because you were mentioned.Message ID: @.***>

kalzoo commented 3 weeks ago

Over to you now @bramathon

rigetti / quil-rs

feat: add source mapping for calibration expansion #370