Index access for calldata arrays.

8 files changed, 214 insertions, 50 deletions

diff --git a/AST.cpp b/AST.cpp
index aba35576..3a0aed11 100644
--- a/AST.cpp
+++ b/AST.cpp
@@ -671,8 +671,11 @@ void IndexAccess::checkTypeRequirements()
 		if (!m_index)
 			BOOST_THROW_EXCEPTION(createTypeError("Index expression cannot be omitted."));
 		m_index->expectType(IntegerType(256));
-		m_type = type.getBaseType();
-		m_isLValue = true;
+		if (type.isByteArray())
+			m_type = make_shared<IntegerType>(8, IntegerType::Modifier::Hash);
+		else
+			m_type = type.getBaseType();
+		m_isLValue = type.getLocation() != ArrayType::Location::CallData;
 		break;
 	}
 	case Type::Category::Mapping:
diff --git a/ArrayUtils.cpp b/ArrayUtils.cpp
index 43cc6fd4..0dea5345 100644
--- a/ArrayUtils.cpp
+++ b/ArrayUtils.cpp
@@ -70,22 +70,25 @@ void ArrayUtils::copyArrayToStorage(ArrayType const& _targetType, ArrayType cons
 		m_context << eth::Instruction::ISZERO;
 		eth::AssemblyItem copyLoopEnd = m_context.newTag();
 		m_context.appendConditionalJumpTo(copyLoopEnd);
+		// add length to source offset
+		m_context << eth::Instruction::DUP5 << eth::Instruction::DUP5 << eth::Instruction::ADD;
+		// stack now: source_offset source_len target_ref target_data_end target_data_ref source_end
 		// store start offset
-		m_context << eth::Instruction::DUP5;
-		// stack now: source_offset source_len target_ref target_data_end target_data_ref calldata_offset
+		m_context << eth::Instruction::DUP6;
+		// stack now: source_offset source_len target_ref target_data_end target_data_ref source_end calldata_offset
 		eth::AssemblyItem copyLoopStart = m_context.newTag();
 		m_context << copyLoopStart
 				  // copy from calldata and store
 				  << eth::Instruction::DUP1 << eth::Instruction::CALLDATALOAD
-				  << eth::Instruction::DUP3 << eth::Instruction::SSTORE
+				  << eth::Instruction::DUP4 << eth::Instruction::SSTORE
 				  // increment target_data_ref by 1
-				  << eth::Instruction::SWAP1 << u256(1) << eth::Instruction::ADD
+				  << eth::Instruction::SWAP2 << u256(1) << eth::Instruction::ADD
 				  // increment calldata_offset by 32
-				  << eth::Instruction::SWAP1 << u256(32) << eth::Instruction::ADD
+				  << eth::Instruction::SWAP2 << u256(32) << eth::Instruction::ADD
 				  // check for loop condition
-				  << eth::Instruction::DUP1 << eth::Instruction::DUP6 << eth::Instruction::GT;
+				  << eth::Instruction::DUP1 << eth::Instruction::DUP3 << eth::Instruction::GT;
 		m_context.appendConditionalJumpTo(copyLoopStart);
-		m_context << eth::Instruction::POP;
+		m_context << eth::Instruction::POP << eth::Instruction::POP;
 		m_context << copyLoopEnd;
 
 		// now clear leftover bytes of the old value
@@ -179,6 +182,7 @@ void ArrayUtils::clearArray(ArrayType const& _type) const
 		m_context << eth::Instruction::POP;
 	else if (_type.getLength() < 5) // unroll loop for small arrays @todo choose a good value
 	{
+		solAssert(!_type.isByteArray(), "");
 		for (unsigned i = 1; i < _type.getLength(); ++i)
 		{
 			StorageItem(m_context, *_type.getBaseType()).setToZero(SourceLocation(), false);
@@ -188,6 +192,7 @@ void ArrayUtils::clearArray(ArrayType const& _type) const
 	}
 	else
 	{
+		solAssert(!_type.isByteArray(), "");
 		m_context
 			<< eth::Instruction::DUP1 << u256(_type.getLength())
 			<< u256(_type.getBaseType()->getStorageSize())
@@ -296,9 +301,23 @@ void ArrayUtils::convertLengthToSize(ArrayType const& _arrayType) const
 
 void ArrayUtils::retrieveLength(ArrayType const& _arrayType) const
 {
-	if (_arrayType.isDynamicallySized())
-		m_context << eth::Instruction::DUP1 << eth::Instruction::SLOAD;
-	else
+	if (!_arrayType.isDynamicallySized())
 		m_context << _arrayType.getLength();
+	else
+	{
+		m_context << eth::Instruction::DUP1;
+		switch (_arrayType.getLocation())
+		{
+		case ArrayType::Location::CallData:
+			// length is stored on the stack
+			break;
+		case ArrayType::Location::Memory:
+			m_context << eth::Instruction::MLOAD;
+			break;
+		case ArrayType::Location::Storage:
+			m_context << eth::Instruction::SLOAD;
+			break;
+		}
+	}
 }
 
diff --git a/Compiler.cpp b/Compiler.cpp
index acc30cf3..c880d49d 100644
--- a/Compiler.cpp
+++ b/Compiler.cpp
@@ -260,7 +260,7 @@ void Compiler::appendReturnValuePacker(TypePointers const& _typeParameters)
 
 	for (TypePointer const& type: _typeParameters)
 	{
-		CompilerUtils(m_context).copyToStackTop(stackDepth, *type);
+		CompilerUtils(m_context).copyToStackTop(stackDepth, type->getSizeOnStack());
 		ExpressionCompiler(m_context, m_optimize).appendTypeConversion(*type, *type, true);
 		bool const c_padToWords = true;
 		dataOffset += CompilerUtils(m_context).storeInMemory(dataOffset, *type, c_padToWords);
diff --git a/CompilerUtils.cpp b/CompilerUtils.cpp
index 826651e6..acb6412f 100644
--- a/CompilerUtils.cpp
+++ b/CompilerUtils.cpp
@@ -41,18 +41,22 @@ unsigned CompilerUtils::loadFromMemory(unsigned _offset, Type const& _type,
 	return loadFromMemoryHelper(_type, _fromCalldata, _padToWordBoundaries);
 }
 
-void CompilerUtils::loadFromMemoryDynamic(Type const& _type, bool _fromCalldata, bool _padToWordBoundaries)
+void CompilerUtils::loadFromMemoryDynamic(
+	Type const& _type, bool _fromCalldata, bool _padToWordBoundaries, bool _keepUpdatedMemoryOffset)
 {
 	solAssert(_type.getCategory() != Type::Category::Array, "Arrays not yet implemented.");
-	m_context << eth::Instruction::DUP1;
+	if (_keepUpdatedMemoryOffset)
+		m_context << eth::Instruction::DUP1;
 	unsigned numBytes = loadFromMemoryHelper(_type, _fromCalldata, _padToWordBoundaries);
-	// update memory counter
-	for (unsigned i = 0; i < _type.getSizeOnStack(); ++i)
-		m_context << eth::swapInstruction(1 + i);
-	m_context << u256(numBytes) << eth::Instruction::ADD;
+	if (_keepUpdatedMemoryOffset)
+	{
+		// update memory counter
+		for (unsigned i = 0; i < _type.getSizeOnStack(); ++i)
+			m_context << eth::swapInstruction(1 + i);
+		m_context << u256(numBytes) << eth::Instruction::ADD;
+	}
 }
 
-
 unsigned CompilerUtils::storeInMemory(unsigned _offset, Type const& _type, bool _padToWordBoundaries)
 {
 	solAssert(_type.getCategory() != Type::Category::Array, "Unable to statically store dynamic type.");
@@ -134,12 +138,11 @@ void CompilerUtils::moveToStackVariable(VariableDeclaration const& _variable)
 		m_context << eth::swapInstruction(stackPosition - size + 1) << eth::Instruction::POP;
 }
 
-void CompilerUtils::copyToStackTop(unsigned _stackDepth, Type const& _type)
+void CompilerUtils::copyToStackTop(unsigned _stackDepth, unsigned _itemSize)
 {
 	if (_stackDepth > 16)
 		BOOST_THROW_EXCEPTION(CompilerError() << errinfo_comment("Stack too deep."));
-	unsigned const size = _type.getSizeOnStack();
-	for (unsigned i = 0; i < size; ++i)
+	for (unsigned i = 0; i < _itemSize; ++i)
 		m_context << eth::dupInstruction(_stackDepth);
 }
 
diff --git a/CompilerUtils.h b/CompilerUtils.h
index 2df85f11..b06f2c7a 100644
--- a/CompilerUtils.h
+++ b/CompilerUtils.h
@@ -46,7 +46,8 @@ public:
 	/// Dynamic version of @see loadFromMemory, expects the memory offset on the stack.
 	/// Stack pre: memory_offset
 	/// Stack post: value... (memory_offset+length)
-	void loadFromMemoryDynamic(Type const& _type, bool _fromCalldata = false, bool _padToWordBoundaries = true);
+	void loadFromMemoryDynamic(Type const& _type, bool _fromCalldata = false,
+		bool _padToWordBoundaries = true, bool _keepUpdatedMemoryOffset = true);
 	/// Stores data from stack in memory.
 	/// @param _offset offset in memory
 	/// @param _type type of the data on the stack
@@ -65,8 +66,9 @@ public:
 
 	/// Moves the value that is at the top of the stack to a stack variable.
 	void moveToStackVariable(VariableDeclaration const& _variable);
-	/// Copies a variable of type @a _type from a stack depth of @a _stackDepth to the top of the stack.
-	void copyToStackTop(unsigned _stackDepth, Type const& _type);
+	/// Copies an item that occupies @a _itemSize stack slots from a stack depth of @a _stackDepth
+	/// to the top of the stack.
+	void copyToStackTop(unsigned _stackDepth, unsigned _itemSize);
 	/// Removes the current value from the top of the stack.
 	void popStackElement(Type const& _type);
 
diff --git a/ExpressionCompiler.cpp b/ExpressionCompiler.cpp
index 619b0673..793bd55e 100644
--- a/ExpressionCompiler.cpp
+++ b/ExpressionCompiler.cpp
@@ -215,12 +215,20 @@ bool ExpressionCompiler::visit(Assignment const& _assignment)
 	if (op != Token::Assign) // compound assignment
 	{
 		solAssert(_assignment.getType()->isValueType(), "Compound operators not implemented for non-value types.");
-		if (m_currentLValue->storesReferenceOnStack())
-			m_context << eth::Instruction::SWAP1 << eth::Instruction::DUP2;
+		unsigned lvalueSize = m_currentLValue->sizeOnStack();
+		unsigned itemSize = _assignment.getType()->getSizeOnStack();
+		if (lvalueSize > 0)
+		{
+			CompilerUtils(m_context).copyToStackTop(lvalueSize + itemSize, itemSize);
+			CompilerUtils(m_context).copyToStackTop(itemSize + lvalueSize, lvalueSize);
+			// value lvalue_ref value lvalue_ref
+		}
 		m_currentLValue->retrieveValue(_assignment.getLocation(), true);
 		appendOrdinaryBinaryOperatorCode(Token::AssignmentToBinaryOp(op), *_assignment.getType());
-		if (m_currentLValue->storesReferenceOnStack())
-			m_context << eth::Instruction::SWAP1;
+		if (lvalueSize > 0)
+			// value [lvalue_ref] updated_value
+			for (unsigned i = 0; i < itemSize; ++i)
+				m_context << eth::swapInstruction(itemSize + lvalueSize) << eth::Instruction::POP;
 	}
 	m_currentLValue->storeValue(*_assignment.getRightHandSide().getType(), _assignment.getLocation());
 	m_currentLValue.reset();
@@ -259,9 +267,10 @@ bool ExpressionCompiler::visit(UnaryOperation const& _unaryOperation)
 	case Token::Dec: // -- (pre- or postfix)
 		solAssert(!!m_currentLValue, "LValue not retrieved.");
 		m_currentLValue->retrieveValue(_unaryOperation.getLocation());
+		solAssert(m_currentLValue->sizeOnStack() <= 1, "Not implemented.");
 		if (!_unaryOperation.isPrefixOperation())
 		{
-			if (m_currentLValue->storesReferenceOnStack())
+			if (m_currentLValue->sizeOnStack() == 1)
 				m_context << eth::Instruction::SWAP1 << eth::Instruction::DUP2;
 			else
 				m_context << eth::Instruction::DUP1;
@@ -273,7 +282,7 @@ bool ExpressionCompiler::visit(UnaryOperation const& _unaryOperation)
 			m_context << eth::Instruction::SWAP1 << eth::Instruction::SUB; // @todo avoid the swap
 		// Stack for prefix: [ref] (*ref)+-1
 		// Stack for postfix: *ref [ref] (*ref)+-1
-		if (m_currentLValue->storesReferenceOnStack())
+		if (m_currentLValue->sizeOnStack() == 1)
 			m_context << eth::Instruction::SWAP1;
 		m_currentLValue->storeValue(
 			*_unaryOperation.getType(), _unaryOperation.getLocation(),
@@ -714,18 +723,24 @@ bool ExpressionCompiler::visit(IndexAccess const& _indexAccess)
 	}
 	else if (baseType.getCategory() == Type::Category::Array)
 	{
+		// stack layout: <base_ref> [<length>] <index>
 		ArrayType const& arrayType = dynamic_cast<ArrayType const&>(baseType);
-		solAssert(arrayType.getLocation() == ArrayType::Location::Storage,
-			"TODO: Index acces only implemented for storage arrays.");
-		solAssert(!arrayType.isByteArray(), "TODO: Index acces not implemented for byte arrays.");
 		solAssert(_indexAccess.getIndexExpression(), "Index expression expected.");
+		ArrayType::Location location = arrayType.getLocation();
+		eth::Instruction load =
+			location == ArrayType::Location::Storage ? eth::Instruction::SLOAD :
+			location == ArrayType::Location::Memory ? eth::Instruction::MLOAD :
+			eth::Instruction::CALLDATALOAD;
 
 		_indexAccess.getIndexExpression()->accept(*this);
 		// retrieve length
-		if (arrayType.isDynamicallySized())
-			m_context << eth::Instruction::DUP2 << eth::Instruction::SLOAD;
-		else
+		if (!arrayType.isDynamicallySized())
 			m_context << arrayType.getLength();
+		else if (location == ArrayType::Location::CallData)
+			// length is stored on the stack
+			m_context << eth::Instruction::SWAP1;
+		else
+			m_context << eth::Instruction::DUP2 << load;
 		// stack: <base_ref> <index> <length>
 		// check out-of-bounds access
 		m_context << eth::Instruction::DUP2 << eth::Instruction::LT;
@@ -735,14 +750,64 @@ bool ExpressionCompiler::visit(IndexAccess const& _indexAccess)
 
 		m_context << legalAccess;
 		// stack: <base_ref> <index>
-		m_context << arrayType.getBaseType()->getStorageSize() << eth::Instruction::MUL;
-		if (arrayType.isDynamicallySized())
+		if (arrayType.isByteArray())
+			// byte array is packed differently, especially in storage
+			switch (location)
+			{
+			case ArrayType::Location::Storage:
+				// byte array index storage lvalue on stack (goal):
+				// <ref> <byte_number> = <base_ref + index / 32> <index % 32>
+				m_context << u256(32) << eth::Instruction::SWAP2;
+				CompilerUtils(m_context).computeHashStatic();
+				// stack: 32 index data_ref
+				m_context
+					<< eth::Instruction::DUP3 << eth::Instruction::DUP3
+					<< eth::Instruction::DIV << eth::Instruction::ADD
+				// stack: 32 index (data_ref + index / 32)
+					<< eth::Instruction::SWAP2 << eth::Instruction::SWAP1 << eth::Instruction::MOD;
+				setLValue<StorageByteArrayElement>(_indexAccess);
+				break;
+			case ArrayType::Location::CallData:
+				// no lvalue, just retrieve the value
+				m_context
+					<< eth::Instruction::ADD << eth::Instruction::CALLDATALOAD
+					<< u256(0) << eth::Instruction::BYTE;
+				break;
+			case ArrayType::Location::Memory:
+				solAssert(false, "Memory lvalues not yet implemented.");
+			}
+		else
 		{
-			m_context << eth::Instruction::SWAP1;
-			CompilerUtils(m_context).computeHashStatic();
+			u256 elementSize =
+				location == ArrayType::Location::Storage ? arrayType.getBaseType()->getStorageSize() :
+				CompilerUtils::getPaddedSize(arrayType.getBaseType()->getCalldataEncodedSize());
+			solAssert(elementSize != 0, "Invalid element size.");
+			if (elementSize > 1)
+				m_context << elementSize << eth::Instruction::MUL;
+			if (arrayType.isDynamicallySized())
+			{
+				if (location == ArrayType::Location::Storage)
+				{
+					m_context << eth::Instruction::SWAP1;
+					CompilerUtils(m_context).computeHashStatic();
+				}
+				else if (location == ArrayType::Location::Memory)
+					m_context << u256(32) << eth::Instruction::ADD;
+			}
+			m_context << eth::Instruction::ADD;
+			switch (location)
+			{
+			case ArrayType::Location::CallData:
+				// no lvalue
+				CompilerUtils(m_context).loadFromMemoryDynamic(*arrayType.getBaseType(), true, true, false);
+				break;
+			case ArrayType::Location::Storage:
+				setLValueToStorageItem(_indexAccess);
+				break;
+			case ArrayType::Location::Memory:
+				solAssert(false, "Memory lvalues not yet implemented.");
+			}
 		}
-		m_context << eth::Instruction::ADD;
-		setLValueToStorageItem(_indexAccess);
 	}
 	else
 		solAssert(false, "Index access only allowed for mappings or arrays.");
diff --git a/LValue.cpp b/LValue.cpp
index 452ca1c7..f5730020 100644
--- a/LValue.cpp
+++ b/LValue.cpp
@@ -232,6 +232,64 @@ void StorageItem::setToZero(SourceLocation const&, bool _removeReference) const
 	}
 }
 
+/// Used in StorageByteArrayElement
+static IntegerType byteType(8, IntegerType::Modifier::Hash);
+
+StorageByteArrayElement::StorageByteArrayElement(CompilerContext& _compilerContext):
+	LValue(_compilerContext, byteType)
+{
+}
+
+void StorageByteArrayElement::retrieveValue(SourceLocation const&, bool _remove) const
+{
+	// stack: ref bytenr
+	if (_remove)
+		m_context << eth::Instruction::SWAP1 << eth::Instruction::SLOAD
+			<< eth::Instruction::SWAP1 << eth::Instruction::BYTE;
+	else
+		m_context << eth::Instruction::DUP2 << eth::Instruction::SLOAD
+			<< eth::Instruction::DUP2 << eth::Instruction::BYTE;
+}
+
+void StorageByteArrayElement::storeValue(Type const&, SourceLocation const&, bool _move) const
+{
+	//@todo optimize this
+
+	// stack: value ref bytenr
+	m_context << u256(31) << eth::Instruction::SUB << u256(0x100) << eth::Instruction::EXP;
+	// stack: value ref (1<<(8*(31-bytenr)))
+	m_context << eth::Instruction::DUP2 << eth::Instruction::SLOAD;
+	// stack: value ref (1<<(8*(31-bytenr))) old_full_value
+	// clear byte in old value
+	m_context << eth::Instruction::DUP2 << u256(0xff) << eth::Instruction::MUL
+		<< eth::Instruction::NOT << eth::Instruction::AND;
+	// stack: value ref (1<<(32-bytenr)) old_full_value_with_cleared_byte
+	m_context << eth::Instruction::SWAP1 << eth::Instruction::DUP4 << eth::Instruction::MUL
+		<< eth::Instruction::OR;
+	// stack: value ref new_full_value
+	m_context << eth::Instruction::SWAP1 << eth::Instruction::SSTORE;
+	if (_move)
+		m_context << eth::Instruction::POP;
+}
+
+void StorageByteArrayElement::setToZero(SourceLocation const&, bool _removeReference) const
+{
+	// stack: ref bytenr
+	if (!_removeReference)
+		m_context << eth::Instruction::SWAP1 << eth::Instruction::DUP2;
+	m_context << u256(31) << eth::Instruction::SUB << u256(0x100) << eth::Instruction::EXP;
+	// stack: ref (1<<(8*(31-bytenr)))
+	m_context << eth::Instruction::DUP2 << eth::Instruction::SLOAD;
+	// stack: ref (1<<(8*(31-bytenr))) old_full_value
+	// clear byte in old value
+	m_context << eth::Instruction::SWAP1 << u256(0xff) << eth::Instruction::MUL << eth::Instruction::AND;
+	// stack: ref old_full_value_with_cleared_byte
+	m_context << eth::Instruction::SWAP1 << eth::Instruction::SSTORE;
+	if (!_removeReference)
+		m_context << eth::Instruction::SWAP1;
+	else
+		m_context << eth::Instruction::POP;
+}
 
 StorageArrayLength::StorageArrayLength(CompilerContext& _compilerContext, const ArrayType& _arrayType):
 	LValue(_compilerContext, *_arrayType.getMemberType("length")),
@@ -262,4 +320,3 @@ void StorageArrayLength::setToZero(SourceLocation const&, bool _removeReference)
 		m_context << eth::Instruction::DUP1;
 	ArrayUtils(m_context).clearDynamicArray(m_arrayType);
 }
-
diff --git a/LValue.h b/LValue.h
index 1ed0ae01..0ada4f88 100644
--- a/LValue.h
+++ b/LValue.h
@@ -46,8 +46,8 @@ protected:
 		m_context(_compilerContext), m_dataType(_dataType) {}
 
 public:
-	/// @returns true if this lvalue reference type occupies a slot on the stack.
-	virtual bool storesReferenceOnStack() const = 0;
+	/// @returns the number of stack slots occupied by the lvalue reference
+	virtual unsigned sizeOnStack() const { return 1; }
 	/// Copies the value of the current lvalue to the top of the stack and, if @a _remove is true,
 	/// also removes the reference from the stack.
 	/// @a _location source location of the current expression, used for error reporting.
@@ -76,7 +76,7 @@ class StackVariable: public LValue
 public:
 	StackVariable(CompilerContext& _compilerContext, Declaration const& _declaration);
 
-	virtual bool storesReferenceOnStack() const { return false; }
+	virtual unsigned sizeOnStack() const override { return 0; }
 	virtual void retrieveValue(SourceLocation const& _location, bool _remove = false) const override;
 	virtual void storeValue(Type const& _sourceType,
 		SourceLocation const& _location = SourceLocation(), bool _move = false) const override;
@@ -100,7 +100,6 @@ public:
 	StorageItem(CompilerContext& _compilerContext, Declaration const& _declaration);
 	/// Constructs the LValue and assumes that the storage reference is already on the stack.
 	StorageItem(CompilerContext& _compilerContext, Type const& _type);
-	virtual bool storesReferenceOnStack() const { return true; }
 	virtual void retrieveValue(SourceLocation const& _location, bool _remove = false) const override;
 	virtual void storeValue(Type const& _sourceType,
 		SourceLocation const& _location = SourceLocation(), bool _move = false) const override;
@@ -114,6 +113,23 @@ private:
 };
 
 /**
+ * Reference to a single byte inside a storage byte array.
+ * Stack: <storage_ref> <byte_number>
+ */
+class StorageByteArrayElement: public LValue
+{
+public:
+	/// Constructs the LValue and assumes that the storage reference is already on the stack.
+	StorageByteArrayElement(CompilerContext& _compilerContext);
+	virtual unsigned sizeOnStack() const override { return 2; }
+	virtual void retrieveValue(SourceLocation const& _location, bool _remove = false) const override;
+	virtual void storeValue(Type const& _sourceType,
+		SourceLocation const& _location = SourceLocation(), bool _move = false) const override;
+	virtual void setToZero(
+		SourceLocation const& _location = SourceLocation(), bool _removeReference = true) const override;
+};
+
+/**
  * Reference to the "length" member of a dynamically-sized array. This is an LValue with special
  * semantics since assignments to it might reduce its length and thus arrays members have to be
  * deleted.
@@ -123,7 +139,6 @@ class StorageArrayLength: public LValue
 public:
 	/// Constructs the LValue, assumes that the reference to the array head is already on the stack.
 	StorageArrayLength(CompilerContext& _compilerContext, ArrayType const& _arrayType);
-	virtual bool storesReferenceOnStack() const { return true; }
 	virtual void retrieveValue(SourceLocation const& _location, bool _remove = false) const override;
 	virtual void storeValue(Type const& _sourceType,
 		SourceLocation const& _location = SourceLocation(), bool _move = false) const override;