Merge pull request #3743 from ethereum/popStorageArray

pop() for storage arrays

5 files changed, 112 insertions, 3 deletions

diff --git a/libsolidity/ast/Types.cpp b/libsolidity/ast/Types.cpp
index 8620f283..7f5ec46a 100644
--- a/libsolidity/ast/Types.cpp
+++ b/libsolidity/ast/Types.cpp
@@ -1697,6 +1697,7 @@ MemberList::MemberMap ArrayType::nativeMembers(ContractDefinition const*) const
 	{
 		members.push_back({"length", make_shared<IntegerType>(256)});
 		if (isDynamicallySized() && location() == DataLocation::Storage)
+		{
 			members.push_back({"push", make_shared<FunctionType>(
 				TypePointers{baseType()},
 				TypePointers{make_shared<IntegerType>(256)},
@@ -1704,6 +1705,14 @@ MemberList::MemberMap ArrayType::nativeMembers(ContractDefinition const*) const
 				strings{string()},
 				isByteArray() ? FunctionType::Kind::ByteArrayPush : FunctionType::Kind::ArrayPush
 			)});
+			members.push_back({"pop", make_shared<FunctionType>(
+				TypePointers{},
+				TypePointers{},
+				strings{string()},
+				strings{string()},
+				FunctionType::Kind::ArrayPop
+			)});
+		}
 	}
 	return members;
 }
diff --git a/libsolidity/ast/Types.h b/libsolidity/ast/Types.h
index 7c6f179b..b2f34dee 100644
--- a/libsolidity/ast/Types.h
+++ b/libsolidity/ast/Types.h
@@ -914,6 +914,7 @@ public:
 		AddMod, ///< ADDMOD
 		MulMod, ///< MULMOD
 		ArrayPush, ///< .push() to a dynamically sized array in storage
+		ArrayPop, ///< .pop() from a dynamically sized array in storage
 		ByteArrayPush, ///< .push() to a dynamically sized byte array in storage
 		ObjectCreation, ///< array creation using new
 		Assert, ///< assert()
diff --git a/libsolidity/codegen/ArrayUtils.cpp b/libsolidity/codegen/ArrayUtils.cpp
index 0fe66d2d..14c887c3 100644
--- a/libsolidity/codegen/ArrayUtils.cpp
+++ b/libsolidity/codegen/ArrayUtils.cpp
@@ -823,6 +823,85 @@ void ArrayUtils::incrementDynamicArraySize(ArrayType const& _type) const
 		})", {"ref"});
 }
 
+void ArrayUtils::popStorageArrayElement(ArrayType const& _type) const
+{
+	solAssert(_type.location() == DataLocation::Storage, "");
+	solAssert(_type.isDynamicallySized(), "");
+	if (!_type.isByteArray() && _type.baseType()->storageBytes() < 32)
+		solAssert(_type.baseType()->isValueType(), "Invalid storage size for non-value type.");
+
+	if (_type.isByteArray())
+	{
+		m_context.appendInlineAssembly(R"({
+			let slot_value := sload(ref)
+			switch and(slot_value, 1)
+			case 0 {
+				// short byte array
+				let length := and(div(slot_value, 2), 0x1f)
+				if iszero(length) { invalid() }
+
+				// Zero-out the suffix including the least significant byte.
+				let mask := sub(exp(0x100, sub(33, length)), 1)
+				length := sub(length, 1)
+				slot_value := or(and(not(mask), slot_value), mul(length, 2))
+				sstore(ref, slot_value)
+			}
+			case 1 {
+				// long byte array
+				mstore(0, ref)
+				let length := div(slot_value, 2)
+				let slot := keccak256(0, 0x20)
+				switch length
+				case 32
+				{
+					let data := sload(slot)
+					sstore(slot, 0)
+					data := and(data, not(0xff))
+					sstore(ref, or(data, 62))
+				}
+				default
+				{
+					let offset_inside_slot := and(sub(length, 1), 0x1f)
+					slot := add(slot, div(sub(length, 1), 32))
+					let data := sload(slot)
+
+					// Zero-out the suffix of the byte array by masking it.
+					// ((1<<(8 * (32 - offset))) - 1)
+					let mask := sub(exp(0x100, sub(32, offset_inside_slot)), 1)
+					data := and(not(mask), data)
+					sstore(slot, data)
+
+					// Reduce the length by 1
+					slot_value := sub(slot_value, 2)
+					sstore(ref, slot_value)
+				}
+			}
+		})", {"ref"});
+		m_context << Instruction::POP;
+	}
+	else
+	{
+		// stack: ArrayReference
+		retrieveLength(_type);
+		// stack: ArrayReference oldLength
+		m_context << Instruction::DUP1;
+		// stack: ArrayReference oldLength oldLength
+		m_context << Instruction::ISZERO;
+		m_context.appendConditionalInvalid();
+
+		// Stack: ArrayReference oldLength
+		m_context << u256(1) << Instruction::SWAP1 << Instruction::SUB;
+		// Stack ArrayReference newLength
+		m_context << Instruction::DUP2 << Instruction::DUP2;
+		// Stack ArrayReference newLength ArrayReference newLength;
+		accessIndex(_type, false);
+		// Stack: ArrayReference newLength storage_slot byte_offset
+		StorageItem(m_context, *_type.baseType()).setToZero(SourceLocation(), true);
+		// Stack: ArrayReference newLength
+		m_context << Instruction::SWAP1 << Instruction::SSTORE;
+	}
+}
+
 void ArrayUtils::clearStorageLoop(TypePointer const& _type) const
 {
 	m_context.callLowLevelFunction(
diff --git a/libsolidity/codegen/ArrayUtils.h b/libsolidity/codegen/ArrayUtils.h
index 99786397..daf50bf5 100644
--- a/libsolidity/codegen/ArrayUtils.h
+++ b/libsolidity/codegen/ArrayUtils.h
@@ -73,6 +73,11 @@ public:
 	/// Stack pre: reference (excludes byte offset)
 	/// Stack post: new_length
 	void incrementDynamicArraySize(ArrayType const& _type) const;
+	/// Decrements the size of a dynamic array by one if length is nonzero. Causes an invalid instruction otherwise.
+	/// Clears the removed data element. In case of a byte array, this might move the data.
+	/// Stack pre: reference
+	/// Stack post:
+	void popStorageArrayElement(ArrayType const& _type) const;
 	/// Appends a loop that clears a sequence of storage slots of the given type (excluding end).
 	/// Stack pre: end_ref start_ref
 	/// Stack post: end_ref
diff --git a/libsolidity/codegen/ExpressionCompiler.cpp b/libsolidity/codegen/ExpressionCompiler.cpp
index 4bcc1fa9..93d440c8 100644
--- a/libsolidity/codegen/ExpressionCompiler.cpp
+++ b/libsolidity/codegen/ExpressionCompiler.cpp
@@ -866,6 +866,19 @@ bool ExpressionCompiler::visit(FunctionCall const& _functionCall)
 				StorageByteArrayElement(m_context).storeValue(*type, _functionCall.location(), true);
 			break;
 		}
+		case FunctionType::Kind::ArrayPop:
+		{
+			_functionCall.expression().accept(*this);
+			solAssert(function.parameterTypes().empty(), "");
+
+			ArrayType const& arrayType = dynamic_cast<ArrayType const&>(
+				*dynamic_cast<MemberAccess const&>(_functionCall.expression()).expression().annotation().type
+			);
+			solAssert(arrayType.dataStoredIn(DataLocation::Storage), "");
+
+			ArrayUtils(m_context).popStorageArrayElement(arrayType);
+			break;
+		}
 		case FunctionType::Kind::ObjectCreation:
 		{
 			ArrayType const& arrayType = dynamic_cast<ArrayType const&>(*_functionCall.annotation().type);
@@ -1345,11 +1358,13 @@ bool ExpressionCompiler::visit(MemberAccess const& _memberAccess)
 					break;
 				}
 		}
-		else if (member == "push")
+		else if (member == "push" || member == "pop")
 		{
 			solAssert(
-				type.isDynamicallySized() && type.location() == DataLocation::Storage,
-				"Tried to use .push() on a non-dynamically sized array"
+				type.isDynamicallySized() &&
+				type.location() == DataLocation::Storage &&
+				type.category() == Type::Category::Array,
+				"Tried to use ." + member + "() on a non-dynamically sized array"
 			);
 		}
 		else