Solidityで配列の任意のデータを削除できない理由

ethereumコミュニティーで、配列の途中のデータを削除して、全体を詰めたいのですがSolidityでどうやったらいいのですか？っていう質問があったので、いろいろと調べてみました。

結論としては、Solidityでは配列の要素を削除できません。

理由としてはgas代が予想できないほど膨れ上がる可能性があってなかなか難しいっていうのがわかりました。
ただ、gas代を無視すれば自分でそうした処理を書くことはできます。以降では実際に実装しながら理解したSolidityで配列の要素の削除が難しい理由を説明していきます。
なお、本記事で公開しているコードはいろいろな問題を含んでいますので実案件では利用しないでください。

1.普通に実装してみる

冒頭でも書きましたが、Solidity自体には配列の要素を削除するfunctionは用意されていません。ので自分で実装します。
一番単純なアルゴリズムとしては、削除したいindexより後ろの要素を１つずつ詰めていくっていうものですね。コードで書くと次の通りです。

pragma solidity ^0.4.18;


contract PackedArray {
  uint[] public arrays;
  
  function push(uint[] _args) public {
      arrays = _args;
  }
  
  function remove(uint index) public {
      require(arrays.length > index);
      uint[] memory copy = new uint[](arrays.length - 1);
      uint copyIndex = 0;
      for(uint i = 0; i < arrays.length; i++) {
          if(i != index) {
              copy[copyIndex] = arrays[i];
              copyIndex += 1;
          }
      }
      arrays = copy;
  }
}

問題点

冒頭でgas代を無視すれば。。。といった理由がこのループ処理です。対象とするarraysの要素数が多くなればそれだけループ回数が増えるので、gas代がバカになりません。

ということで、次はループを使わない方法で実装できないか考えてみます。

2. ループを使わずに配列の要素を削除する

アルゴリズム

アルゴリズムとしては単純で、削除する対象のindexを境にして、その前半部分と後半部分に分けてコピーすれば良いです。結果として生成された配列は対象の要素を取り除いた配列となります。

Solidityでの問題点

solidityで上記のアルゴリズムを実装しようとすると、通常の命令コード（高レベルコードというべき？）には配列の要素をまとめてコピーするものが存在しないため、assemblyで実装する必要ができます。ですが、assemblyで実装しようとしてもopcodeで扱えるbyte数が障壁となります。
メモリ上orストレージ上のデータを操作するため、今回使うopcodeには次の4つが該当すると思います。

• mload - メモリからデータをロードする
• mstore - メモリにデータを格納する
• sload - ストレージからデータをロードする
• sstore - ストレージにデータを格納する

まぁ、対象とするデータがストレージかメモリかで実質どっちかの２つを使うことになります。
で、これら4つのopcodeはなんと、一度に扱えるデータサイズが32byteと決まっています。
Solidity Opecodes

今回のアルゴリズムを実装する上での絶対条件は任意のbyte数をコピーすることです。どうしたものかなぁと思案していたところ任意のbyte数を指定してデータをコピーできるopcodeがあることを思い出しました。以下の２つが該当します。

• calldatacopy - function呼び出し時に指定された引数データをメモリ上にコピーする
• returndatacopy - call or delegatecall などで外部呼び出しをしたContractからの戻り値をメモリ上にコピーする

今回は、calldatacopyが使えそうなので早速実装してみました。

pragma solidity ^0.4.18;


contract PackedArray {
  uint[] public arrays;
  
  function set(uint[] _args) public {
      arrays = _args;
  }
  
  function remove(uint index) public {
      PackedArray(this).pack(arrays, index);
  }
  
  function pack(uint256[] _arrays, uint256 _deleteIndex) external {
      uint256 length = _arrays.length;
      uint256[] memory copy = new uint256[](length - 1);
      assembly {
          //find array data pos;
          let freep := mload(0x40)
          mstore(0x40, add(freep, 0x20))
          calldatacopy(freep, 0x4, 0x20)
          
          // array data first 32 byte is length. so slide to array body pos; 
          let arrayDataPos := add(mload(freep), 0x20)
          let size := mul(0x20, _deleteIndex)
          // method sig 4byte.
          calldatacopy(add(copy, 0x20), add(0x04, arrayDataPos), size)
          let afterpos := add(add(copy, 0x20), size)
          let alldatasize := mul(0x20, length)
          let aftersize := sub(alldatasize, add(size, 0x20))
          let afterindexPos := add(add(arrayDataPos, size), 0x20)
          calldatacopy(afterpos, add(0x04, afterindexPos), aftersize)
      }
      
      arrays = copy;
  }
}

問題点

callを呼び出さないといけない都合上、ストレージ上のデータを全てメモリ上に展開しないといけないため、その時点で結構大量のgas代が必要になります。なのでやはりこの実装でもgas代の問題が浮上します。

まとめ

Solidityで配列の要素を削除する機能が実装できない原因は結局のところgas代が予測できないことであり、その理由はevmで用意されたopcodeに適切なものがないためです。
現状用意されているopcodeで頑張って実装したとしても前述した２つの方法のどちらかを使うしかないのが現状なのかなぁと思います。

要素の削除がどうしても必要だ！ってなった場合は、自分でLinked Listを実装するのがgas代問題の発生しない一番簡単な方法なのかもしれませんね。