DRMacIver / shrinkray

Shrinkray is a modern multi-format test-case reducer
MIT License
86 stars 2 forks source link

Experience report + wishlist from Shrinkray + Hypothesis + Crosshair #8

Closed Zac-HD closed 3 weeks ago

Zac-HD commented 1 month ago

I've been hacking on https://github.com/HypothesisWorks/hypothesis/pull/4034 for a few weeks now, and since that involves taking a test and cutting it down to a minimal example which behaves differently depending on the backend, you can see where Shrinkray comes in 😁

As I write, Shrinkray has been running on something extracted from this CI run, trying to minimize the Lark class to whatever kernel actually induces our failure:

proposed_source = open("tmp.py").read()
exec(proposed_source)  # uninteresting if this fails, doesn't define the class that test_repro calls, etc.
try:
    test_repro()
except FlakyReplay as err:
    msg = "on backend='crosshair' but passed under backend='hypothesis'"
    if msg in str(err):
        sys.exit(0)
sys.exit(1)

This has worked remarkably well, though with a ~1s interestingness test it does take tens of minutes per round. My basic workflow is to let it run until the code sample is pretty small (~500 -> ~20 lines, around 20 minutes), then inline one of the remaining imports (pre-processed with this script) and repeat.

wishlist of mostly bad ideas that would make me even happier - Rip through some initial junk as quickly as possible - if it looks like Python code, delete comments, docstrings, and type annotations; remove unused imports; try deleting the entire body of any function. All very crude but they'd speed up the rest of the passes considerably - Pass ordering seems kinda weird for Python; I'm seeing a lot of initial time in debracket and then later split-on-\n-and-delete-chunks makes way more progress. Maybe a more exploratory early-adaptive phase when e.g. debracket is making progress slowly? - Probably doesn't make sense to put it in shrinkray, but a reduction-pump that could inline non-stdlib imports would be really neat. Does require some reasonable judgement about the import graph though. - Utterly cursed, but... allow the user to propose edits while shrinkray is running, and incorporate them if sucessful? - It'd be somewhere between a fun minigame while you're waiting, and actually pretty nice as a way to get occasional speedups - I often see that some pass has caused an undefined name and thus the whole function body can be deleted. - If the interface is a generic "we shell out to $tool and try the patch" you could use an editor, or tools like isort/autoflake etc.
DRMacIver commented 1 month ago

(Some of) your wish is my command! If you update to the latest version you'll have:

Inlining is possible in principle but inlining Python in general is a nightmare. A less nightmarish solution that I've been meaning to implement at some point is to support multi-file reduction. Shrink Ray is more or less designed to be able to do this I just haven't yet.

I think allowing the user to edit the file as shrink ray runs is another nightmare. The current interface for that is to press q, edit the file, and try again, and I think this is probably better than most user interfaces I can try.

Zac-HD commented 1 month ago

Current HEAD is delightfully faster to make progress! (I think mostly due to pass ordering so far)

One thing I noticed is that pressing q prints Reduction completed! \n Test case was already maximally reduced. and restores to the original state; fortunately I had the file open in an editor and was able to restore the mostly-reduced version. IIRC this happened on yesterday's version too; not a big deal because I can just ctrl-c out.

update: same thing happened on run to completion! Happily still restorable via editor history.

DRMacIver commented 1 month ago

Huh. That's a terrible bug. I'll see if I can reproduce and fix tomorrow.

Zac-HD commented 1 month ago

Two things I noticed skimming the code:

...and I might try to add an interactive shrink pass at some point, we'll see.

DRMacIver commented 1 month ago

Huh. That's a terrible bug. I'll see if I can reproduce and fix tomorrow.

This should be fixed now (I found it annoyingly hard to write an actual test for it, but I found the guilty code and have manually verified a fix)

there are a few time-based decisions, e.g. code here or design here, and it seems likely that they're poorly tuned for shrinking with a ~8s interestingness test (it fails much faster for most bad reductions, at least). Works well overall anyway though, so I wouldn't prioritize fixing this.

Yeah, I think the decisions of which operations to run when are currently the weakest part of shrink ray, although I think this is also something of an open research problem.

It's actually not clear that these numbers should scale with the length of the interestingness test though because the point of them is to avoid long stalls, and long stalls are long even if they're short in terms of number of calls to the interestingness test.

I think that design doc is out of date though (sorry). The current patching logic isn't time based and should work with any speed of interestingness test. https://github.com/DRMacIver/shrinkray/blob/5757fea7c46d48d657fecfa9d5970177fdee0cae/src/shrinkray/passes/patching.py#L94

Zac-HD commented 1 month ago

Got a traceback from inside libcst,

Traceback (most recent call last):
  File "/home/zac/.local/bin/shrinkray", line 8, in <module>
    sys.exit(main())
             ^^^^^^
  File ".../click/core.py", line 1157, in __call__
    return self.main(*args, **kwargs)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../click/core.py", line 1078, in main
    rv = self.invoke(ctx)
         ^^^^^^^^^^^^^^^^
  File ".../click/core.py", line 1434, in invoke
    return ctx.invoke(self.callback, **ctx.params)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../click/core.py", line 783, in invoke
    return __callback(*args, **kwargs)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../shrinkray/__main__.py", line 500, in main
    @trio.run
     ^^^^^^^^
  File ".../trio/_core/_run.py", line 2093, in run
    raise runner.main_task_outcome.error
  File ".../shrinkray/__main__.py", line 554, in _
    async with trio.open_nursery() as nursery:
  File ".../trio/_core/_run.py", line 881, in __aexit__
    raise combined_error_from_nursery
  File ".../shrinkray/__main__.py", line 775, in _
    await reducer.run()
  File ".../shrinkray/reducer.py", line 320, in run
    await self.initial_cut()
  File ".../shrinkray/reducer.py", line 301, in initial_cut
    await self.run_pass(rp)
  File ".../shrinkray/reducer.py", line 207, in run_pass
    await rp(self.target)
  File ".../shrinkray/passes/python.py", line 104, in lift_indented_constructs
    await libcst_transform(
  File ".../shrinkray/passes/python.py", line 98, in libcst_transform
    i = await problem.work.find_first_value(range(i, n), can_apply)
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../shrinkray/work.py", line 98, in find_first_value
    async for x in filtered:
  File ".../shrinkray/work.py", line 85, in filter
    async for x, v in results:
  File ".../shrinkray/work.py", line 56, in map
    yield await f(x)
          ^^^^^^^^^^
  File ".../shrinkray/work.py", line 82, in apply
    return (x, await f(x))
               ^^^^^^^^^^
  File ".../shrinkray/passes/python.py", line 74, in can_apply
    transformed = codemod_i.transform_module(module)
                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/codemod/_command.py", line 71, in transform_module
    tree = super().transform_module(tree)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/codemod/_codemod.py", line 108, in transform_module
    return self.transform_module_impl(tree_with_metadata)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/codemod/_visitor.py", line 32, in transform_module_impl
    return tree.visit(self)
           ^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/module.py", line 89, in visit
    result = super(Module, self).visit(visitor)
             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/base.py", line 227, in visit
    _CSTNodeSelfT, self._visit_and_replace_children(visitor)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/module.py", line 74, in _visit_and_replace_children
    body=visit_body_sequence(self, "body", self.body, visitor),
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 227, in visit_body_sequence
    return tuple(visit_body_iterable(parent, fieldname, children, visitor))
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 193, in visit_body_iterable
    new_child = child.visit(visitor)
                ^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/base.py", line 227, in visit
    _CSTNodeSelfT, self._visit_and_replace_children(visitor)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/statement.py", line 1985, in _visit_and_replace_children
    body=visit_required(self, "body", self.body, visitor),
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 81, in visit_required
    result = node.visit(visitor)
             ^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/base.py", line 227, in visit
    _CSTNodeSelfT, self._visit_and_replace_children(visitor)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/statement.py", line 698, in _visit_and_replace_children
    body=visit_body_sequence(self, "body", self.body, visitor),
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 227, in visit_body_sequence
    return tuple(visit_body_iterable(parent, fieldname, children, visitor))
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 193, in visit_body_iterable
    new_child = child.visit(visitor)
                ^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/base.py", line 227, in visit
    _CSTNodeSelfT, self._visit_and_replace_children(visitor)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/statement.py", line 1814, in _visit_and_replace_children
    body=visit_required(self, "body", self.body, visitor),
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 81, in visit_required
    result = node.visit(visitor)
             ^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/base.py", line 227, in visit
    _CSTNodeSelfT, self._visit_and_replace_children(visitor)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/statement.py", line 698, in _visit_and_replace_children
    body=visit_body_sequence(self, "body", self.body, visitor),
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 227, in visit_body_sequence
    return tuple(visit_body_iterable(parent, fieldname, children, visitor))
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 193, in visit_body_iterable
    new_child = child.visit(visitor)
                ^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/base.py", line 227, in visit
    _CSTNodeSelfT, self._visit_and_replace_children(visitor)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/statement.py", line 616, in _visit_and_replace_children
    body=visit_required(self, "body", self.body, visitor),
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 81, in visit_required
    result = node.visit(visitor)
             ^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/base.py", line 227, in visit
    _CSTNodeSelfT, self._visit_and_replace_children(visitor)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/statement.py", line 698, in _visit_and_replace_children
    body=visit_body_sequence(self, "body", self.body, visitor),
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 227, in visit_body_sequence
    return tuple(visit_body_iterable(parent, fieldname, children, visitor))
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 193, in visit_body_iterable
    new_child = child.visit(visitor)
                ^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/base.py", line 227, in visit
    _CSTNodeSelfT, self._visit_and_replace_children(visitor)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/statement.py", line 617, in _visit_and_replace_children
    orelse=visit_optional(self, "orelse", self.orelse, visitor),
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 110, in visit_optional
    result = node.visit(visitor)
             ^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/base.py", line 227, in visit
    _CSTNodeSelfT, self._visit_and_replace_children(visitor)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/statement.py", line 617, in _visit_and_replace_children
    orelse=visit_optional(self, "orelse", self.orelse, visitor),
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File ".../libcst/_nodes/internal.py", line 112, in visit_optional
    raise TypeError(
TypeError: We got a FlattenSentinel while visiting a If. This node's parent does not allow for it to be it to be replaced with a sequence.

unfortunately, of course the input that causes this is fairly large... so I'm currently running croshair-in-hypothesis-in-shrinkray-in-shrinkray. Results soonish.

DRMacIver commented 1 month ago

Got a traceback from inside libcst.

Should be fixed now. Slightly odd behaviour from libcst here (and a bug in the error message) that I wasn't handling correctly.

Zac-HD commented 3 weeks ago

Closing this as ~complete; I might revisit interactive shrinking at some point but don't wait for my PR 😁

and thanks again for shrinkray!