# Can I revert mutations if error is raised inside a function?

**URL:** <https://discourse.julialang.org/t/can-i-revert-mutations-if-error-is-raised-inside-a-function/104452>\
**Category:** General Usage\
**Tags:** question\
**Created:** [October 1, 2023, 4:55am UTC](https://discourse.julialang.org/t/can-i-revert-mutations-if-error-is-raised-inside-a-function/104452 "2023-10-01T04:55:56Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![bguillen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bguillen/32/202173_2.png) [@bguillen](https://discourse.julialang.org/u/bguillen)\
**Post date:** [October 1, 2023, 4:55am UTC](https://discourse.julialang.org/t/can-i-revert-mutations-if-error-is-raised-inside-a-function/104452/1 "2023-10-01T04:55:56Z")

</div>

I am writing a few functions for fast median calculation (mostly replicating [Alexandrescu’s paper](http://erdani.org/research/sea2017.pdf) on fast deterministic selection).

One of the methods includes assertions that certain assumptions are not violated, however, those assertions happen when the input has already been (partially) mutated. Is there a (simple) way to revert those changes if `AssertionError` is raised?

(as a side note, [I’m using this project](https://gitlab.com/bernatguillen/FastMedians.jl) as a way to get back into Julia, with Documenter.jl, tests, coverage, etc. Is this forum the right venue to ask for optimization and development advice?)

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [October 1, 2023, 11:14am UTC](https://discourse.julialang.org/t/can-i-revert-mutations-if-error-is-raised-inside-a-function/104452/2 "2023-10-01T11:14:42Z")

</div>

The straightforward(?) way would be to record the minimal information for the original state at the beginning, use it to revert those changes if some critical condition is false, then throw the `AssertionError`. I’m not sure if it’s better to throw it explicitly or use `@assert false "..."`, the docstring for `@assert` warns that asserts are disabled at some optimization levels but I don’t know if that refers to just the macro or all thrown `AssertionError`.

---

<div class="post-metadata">

**Author:** ![bguillen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bguillen/32/202173_2.png) [@bguillen](https://discourse.julialang.org/u/bguillen)\
**Post date:** [October 1, 2023, 2:08pm UTC](https://discourse.julialang.org/t/can-i-revert-mutations-if-error-is-raised-inside-a-function/104452/3 "2023-10-01T14:08:09Z")

</div>

That’s the approach I was considering too; but it feels like I’m “going against the grain” and maybe it’s better to rethink those functions. Perhaps I could store the transpositions that have to take place and sacrifice a bit of memory in exchange for a more predictable behavior… hmm. In any case it seems like I wasn’t missing something obvious, so thanks for your response, I’ll mark it as the solution!

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [October 1, 2023, 2:43pm UTC](https://discourse.julialang.org/t/can-i-revert-mutations-if-error-is-raised-inside-a-function/104452/4 "2023-10-01T14:43:31Z")

</div>

It’s a pretty natural approach knowing that mutations don’t naturally leave traces to reverse. But are you sure you want to close this so soon? It’s very possible that people can contribute more ideas. If you’re considering refactoring, sharing a (possibly reduced) example of the algorithm would help too. It’s hard to have ideas when we don’t know what the assertion is and how often you need to check it (for example, do you need to check it once before a loop, or is it an easily violated condition that must be checked between steps). It’s not even clear if throwing an `AssertionError` is appropriate for the use-case.

---

<div class="post-metadata">

**Author:** ![bguillen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bguillen/32/202173_2.png) [@bguillen](https://discourse.julialang.org/u/bguillen)\
**Post date:** [October 1, 2023, 4:34pm UTC](https://discourse.julialang.org/t/can-i-revert-mutations-if-error-is-raised-inside-a-function/104452/5 "2023-10-01T16:34:59Z")

</div>

Oh, that’s very kind. I was trying to keep it contained to just the original question.

The function is basically Hoare’s partition but knowing that there’s an internal subarray that is already partitioned. So basically we have an array `r`, an index we want to partition around `p`, and two indices `low`, `high` such that we assume: `r[low:p] .<= r[p]` and `r[p:high] .>= r[p]`. The algorithm is basically swapping everything that needs to be swapped outside of this subarray and then clean up if needed one side. This works for speeding up a selection algorithm similar to median of medians (called median of ninthers) because the chunk of the array that is already properly partitioned grows. I’m a bit worried about recursion but I’ll check the quick sort implementation.

I could just assert these assumptions at the beginning honestly… I was just porting line by line the D implementation and I think now that I understand better what’s happening I can change a few things.

Here’s a simplified version of it (`partitionrightside!` and `partitionleftside!` modify input array and return new index of pivot, and assert one half of the assumptions in them):

```julia
function hoarepartitionwithassumptions!(
    arr::AbstractVector,
    low::Integer,
    pivot::Integer,
    high::Integer
)
    @assert (low <= pivot && pivot <= high) "Wrong indices provided."
    right_index = length(arr)
    left_index = 1
    while true
        while arr[left_index] <= arr[pivot]
            if left_index == low
                # Here I wanted to assert other half of assumptions
                return pivot + partitionrightside!(@view(arr[pivot:right_index]), high - pivot + 1) - 1
            end
            left_index += 1
        end
        while arr[right_index] >= arr[pivot]
            if right_index == high
                # Here I wanted to assert
                return left_index + partitionleftside!(@view(arr[left_index:pivot]), low - left_index + 1) - 1
            end
            right_index -= 1
        end
        arr[left_index], arr[right_index] = arr[right_index], arr[left_index]
        left_index += 1
        right_index -= 1
    end
end

```

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [October 1, 2023, 11:20pm UTC](https://discourse.julialang.org/t/can-i-revert-mutations-if-error-is-raised-inside-a-function/104452/6 "2023-10-01T23:20:45Z")

</div>

Admittedly, I don’t know the full algorithm, but it’s not clear to me what you want to assert in the lines “# Here I wanted to assert other half of assumptions” and “# Here I wanted to assert” and where (replacing the comments? inside the partition methods?), there’s no descriptions. That part at least seems relevant to the question at hand.

On another note, you said that you assume `r[low:p] .<= r[p]` and `r[p:high] .>= r[p]`, but it looks to me like you’re not assuming it. You check for those conditions in `arr[left_index] <= arr[pivot]` and `arr[right_index] >= arr[pivot]`, and if neither is met and thus `arr[left_index] > arr[pivot] > arr[right_index]`, you swap the elements so both become true.

---

<div class="post-metadata">

**Author:** ![bguillen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bguillen/32/202173_2.png) [@bguillen](https://discourse.julialang.org/u/bguillen)\
**Post date:** [October 2, 2023, 8:41am UTC](https://discourse.julialang.org/t/can-i-revert-mutations-if-error-is-raised-inside-a-function/104452/7 "2023-10-02T08:41:30Z")

</div>

Hm, so first of all sorry for the lack of clarity there. It was late evening and it had been a long day.

Regarding the comment: the `partitionrightside!` function has inside an assertion:

```julia
for i = 1:high
    @assert arr[i] >= arr[1] "Assumption broken"
end

```

block. Note that we send to it a view `arr[pivot:right_index]` and an index `high` (which we translate from the original `high` by `pivot-1` units to the left). What that function does is basically move everything between `(high+1):end` that is smaller or equal than the pivot to the beginning, and move the pivot to the right place, so we end with a well partitioned vector.

Therefore, the “other half of assumptions” I would want to assert would replace the comment and be:

```julia
for i = low:pivot
    @assert arr[i] <= arr[pivot] "Assumption broken"
end

```

The `partitionleftside!` function does the opposite checks and works with the other side of the array, but the idea is the same. Honestly, I am considering either doing all the assertions at the beginning (I end up doing them all anyway) or not exporting the method and ignoring the assertions to avoid having to do O(N) comparisons.

Note that the `while` loops guarantee that `left_index < low` and `right_index > high` so those swaps happen _outside_ the region that we assumed is already well partitioned.

I’ve been looking at the [implementation of the sort algorithms](https://github.com/JuliaLang/julia/blob/bed2cd540a11544ed4be381d471bbf590f0b745e/base/sort.jl#L2011) (there’s a partition algorithm there too, I think it’s also Hoare’s partition) and found some other potential optimizations like using `@inbounds` macro. I’ve also seen how the `Ordering` type is used, and I think I’ll try to adapt my code to that as eventually what I’m implementing are `QuickSelect` algorithms so maybe I could do a PR to the sort module…

I hope this was clearer!

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [October 2, 2023, 9:16am UTC](https://discourse.julialang.org/t/can-i-revert-mutations-if-error-is-raised-inside-a-function/104452/8 "2023-10-02T09:16:51Z")

</div>

> [@bguillen](#):
>
> Honestly, I am considering either doing all the assertions at the beginning (I end up doing them all anyway)

This is sensible, saves unnecessary work. Ideally you can do all the validation without changing anything then do all the mutations without a care, but algorithms aren’t always that convenient.