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

inference improvements #158

Closed

Conversation

samuelpilz
Copy link
Contributor

Fixes #157. The mutation of the snippet given in the issue used to compile but now fails to compile. This PR reverts to the previously use strategy, with slight alterations.

Background

We have 2 functions:

// does not work in old approach
#[mutate]
fn test1(mut ret: i64) -> i64 {
    1 + 2
}
// does not typecheck in new approach
#[mutate]
fn test1(mut ret: i64) -> i64 {
    let x = 1;
    x + 1
}

The first snippet did not typecheck correctly in the previous version. This led me to implementing a different approach based on detecting if the left side of an arithmetic operation is a integer literal or derived from some integer literal. This made the first one compile but was not smart enough to detect the second case. I thought I could extend it further, but it turned out that there is not enough information to solve this problem in all cases.

Previously, the trick was to rewrite a + b into if false {a+b} else { <mutator-code>}.
I underestimated the potential of the if false trick, which is an error on my part.

This PR switches to a modified version of the if false trick: a+b is transformed to {let _tmp = a; if false {_tmp+b} else {<mutator-code based on _tmp and b>}}. This makes both versions compile and also passed several other test cases.

This PR is a work in progress. Feedback is welcome.

@llogiq
Copy link
Owner

llogiq commented Jan 24, 2020

Why do you need the temporary? Does this work if the addition doesn't consume a? In that case moving a into a temporary could break code borrowing it later on.

@samuelpilz
Copy link
Contributor Author

samuelpilz commented Jan 25, 2020

The temporary variable is necessary. Without it, the mutation of first snippet would not compile.

Example (Playground)
We want to transform the expression 1+2. The naive transformation replaces the+ by some form of add function that contains the appropriate information to activate some mutation conditionally. The transformed code would look like add(1,2). However, we know that this fails to typecheck since the first 1 is defaulted to i32. This is known and you proposed the if false trick to fix the problem. The output of the if false for the statement 1+2 trick is if false {1+2} else {add(1,2)}. This does not fix the original problem: The type of the literal 1 is still defaulted to i32. The underlying issue is that the first and second 1 do not have the same type, which was one of the intentions of the if false trick. So I figured that a temporary variable will solve exactly that.

I added some test cases and performed some smoke testing. It seems that the transformation is still valid in the face of non-copy types. Informally, this makes sense since a is consumed by the addition, by definition of the Add trait.

@llogiq
Copy link
Owner

llogiq commented Jan 25, 2020

I'm on mobile right now, but you can implement Add on references.

@llogiq
Copy link
Owner

llogiq commented Jan 25, 2020

It just occurred to me that we might create our own type to add. With rebalanced coherence we may be able to make the first example 1 + MutateAdd(..) + 2.

@samuelpilz
Copy link
Contributor Author

I do like the idea of inserting a custom type in the middle of the add operation. However, this requires to write impl<T> Add<MutagenAdd> for T, which is not allowed due to orphan rules.

Implementing Add on referencs is no issue here. If impl Add for &Foo then, foo + foo would not compile with or without mutation. &foo + &foo works in both cases.

I suggest merging this approach (which is a slight modification of your original idea).

@samuelpilz
Copy link
Contributor Author

I also implemented the approach outlined above to mutators for bit-operations and negation

@elichai
Copy link

elichai commented Feb 3, 2020

I do like the idea of inserting a custom type in the middle of the add operation. However, this requires to write impl<T> Add<MutagenAdd> for T, which is not allowed due to orphan rules.

Well you can manually impl it for all primitives: https://play.rust-lang.org/?gist=132755b74337dc5ca1dd0c7e9179c26b

@samuelpilz
Copy link
Contributor Author

Well you can manually impl it for all primitives: https://play.rust-lang.org/?gist=132755b74337dc5ca1dd0c7e9179c26b

I did not know that. However, the transformation has to be valid for all type combinations, e.g. string + "foo" and for custom types.

The more general issue is that the compiler has a special case for type inference in the case of integer expressions. Any expression like MutagenAdd + 1 + 2 or MutagenAdd(1) + 2 will fall short in type inference. The if false approach tricks the compiler to do the special casing for us.

@samuelpilz samuelpilz changed the title [WIP] Int inference improvements Int inference improvements Feb 6, 2020
@samuelpilz samuelpilz changed the title Int inference improvements inference improvements Feb 6, 2020
@samuelpilz
Copy link
Contributor Author

I would consider this PR ready for merging. I have added some more testcases that show that the improvements fix a all cases I could think of.

Hints to any code that still breaks in this new system is welcome.

@samuelpilz
Copy link
Contributor Author

Relevant parts of this PR were merged together with #160

@samuelpilz samuelpilz closed this Mar 11, 2020
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.

Mutation incorrectly infers integer literals
3 participants