Empty list reaches unreachable!()

[agroce]

Compiling this file:

contract Ownable:
  _owner: address
  pub def renounceOwnership():
    self._owner < address([ ])

thread 'main' panicked at 'internal error: entered unreachable code', analyzer/src/traversal/expressions.rs:105:5
stack backtrace:
   0: rust_begin_unwind
             at /rustc/c0b64d97beebb09325b5587abed39f4f1621026f/library/std/src/panicking.rs:493:5
   1: core::panicking::panic_fmt
             at /rustc/c0b64d97beebb09325b5587abed39f4f1621026f/library/core/src/panicking.rs:92:14
   2: core::panicking::panic
             at /rustc/c0b64d97beebb09325b5587abed39f4f1621026f/library/core/src/panicking.rs:50:5
   3: fe_analyzer::traversal::expressions::expr
   4: fe_analyzer::traversal::expressions::assignable_expr
   5: fe_analyzer::traversal::expressions::call_arg
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
Aborted

On latest github master, built with

[profile.dev]
debug = true
panic = "abort"

for fuzzing. Using https://github.com/agroce/afl-compiler-fuzzer + afl.rs.

[cburgdorf]

@g-r-a-n-t I was looking into this today. The general problem here is that we currently do not support the empty array expression []. We do support something like [2] because the element allows us to infer the type u256[1] from that but that is not the case with an empty array. I would think that we need a way to express that [] is of type Array<T> so that it is valid in all scenarios that assume to deal with an array of any kind. I feel like we have talked about similar scenarios before but I haven't found any discussion. What are your thoughts about how to handle this?

[g-r-a-n-t]

This problem is basically identical to expression locations and I think we can handle it in a similar way.

For example, say we have the expression foo[42], where is it? If it's being used in the LHS of an assignment (e.g. foo[42] = 26), then it should be a memory pointer. But if it's being used in an arithmetic expression (e.g. 100 + foo[42]), then it should be on the stack (aka value), as we don't want to add a memory pointer to 100. The required location is not known immediately when analyzing an expression node, which is where the move_location field becomes relevant.

During analysis, the parent node of an expression is responsible for making sure values are in their expected location. There are a few convenience functions to help parent nodes with this task. If the default location of the value is what we want, then we should analyze the expression using expr. If the expression's actual value is what we want, then we analyze the expression using value_expr. If the assignable location for the type is what we want, then we analyze the expression using assignable_expression. All the value_expr and assignable_expr functions do is tack on a move_location to the expression if needed. So, if the expression is not in the correct location, we move it. If the value is already in the correct location, we leave it alone.

If there is a move_location on an expression, the mapper is responsible for wrapping the mapped Yul code in a function call that moves it to the correct location (i.e. we need to mloadn, sloadn, mcopym, or scopym the expression). This happens right here:

fe/compiler/src/yul/mappers/expressions.rs

Lines 56 to 62 in fd9f78e

	match (
	attributes.location.to_owned(),
	attributes.move_location.to_owned(),
	) {
	(from, Some(to)) => move_expression(expression, attributes.typ.to_owned(), from, to),
	(_, None) => Ok(expression),
	}

I think we could pretty much do the exact same thing here for type coercion (or casting, whatever we want to call it). So, we would start by adding a new attribute to ExpressionAttributes named coerced_type:

pub struct ExpressionAttributes {
    pub typ: Type,
    pub location: Location,
    pub move_location: Option<Location>,
    pub coerced_type: Option<Type>,
}

Then we would build into the analyzer a number of convenience functions for tacking coerced types onto expressions if possible. Then when our attributes are mapped by the compiler, we simply look at the required type conversion and wrap the expression inside of a call to a function that alters the values data and checks the validity of conversion (if needed).

So, with regard to the specific problem mentioned here, the expression [] would not have a concrete type when analyzed, but, the parent node would give it one via the coerced_type attribute. This of course applies to all types, not just arrays. Implementing this will be a bit more complex than move locations, but I think the general pattern is what we want.

[sbillig]

Another option might be to pass the expected type downward during analysis. (This would have to be an optional argument, since we won't always have an expected type.)

The analysis of [] has to return some type; if we don't know the expected type, we'd have to either allow for an unknown type and return something like Array { size: None, inner: Unknown }, or choose some default type like U256 and let the parent check whether the array is empty, change the type if it is, and emit an error otherwise.

If we pass the expected type from the parent down to the child, the analysis of the child can just return the expected type in the case of an empty array.

This also seems useful in cases like x: u8 = 500. If we want the analyzer to catch the overflow, either the analysis of the 500 expr will need to know that the expected type is u8, or the analysis of the vardecl statement will need to know that the assigned value is 500 (which would require us to also return an optional static value from the expression analysis fn). Or we could let the compiler catch this case, but it seems better to catch as much as possible in the analyzer.

I don't know which method would work better in practice.

Thinking about this a little more, maybe it would be useful to include an optional static value in the expression attributes, so cases like:

x: u8 = 200
y: u8 = x + 200

could be caught by the analyzer.