Programming in Scala, First Edition: Chapter 28

28. Object Equality
  2つの値が同じかどうか比較するのは見た目以上に難しく間違いやすい。
  同一性の詳細と同一判定の実装方法について考察する。

28.1 Equality in Scala
  Javaの同一判定とscalaの同一判定の定義は異なる。Section 11.2
  Javaの同一判定は二つある。
    ==演算子
      値型に対しては自然な値の同一性
      参照型に対してはオブジェクトの同一性(型非依存)
    equals method
      参照型に対するユーザ定義(型依存)の本質的な同一性
    ==演算子が参照型に対して自然な値の同一性で判定しない事が分かり難い。
      x, yがstringで同じ文字列であっても、x == yがfalseになる。
  scalaの同一判定
    eq method
      参照型に対するオブジェクトの同一性(Javaの==と同様)
    ==
      値型に対しては自然な値の同一性(Javaの==と同じ)
      参照型に対してはequals methodと同じ
        equals methodをoverrideして==の振る舞いを変える。
      ==を直接書き換える事は出来ない。
        class Anyでfinal methodとして定義されているため。
  equals method
    class Anyで定義されて全ての型に継承されている。
    Anyでdefaultとしてeqと同等に定義されている。
      overrideしなければJavaの==と同じ。
    overrideする事で==の振る舞いを型毎に定義する事が出来る。
      ** 自然な同一性を表すように定義するのが一般的。

28.2 Writing an equality method
  equals methodを正しく実装するのはオブジェクト指向言語ではとても難しい。
    2007年に行われた大規規模なJava codeの調査では殆ど間違った実装になっていた。
  同等性は多くの事の基盤になっているため。
    例えばcollection colにelem1を入れた場合
      "elem1 equals elem2"なら"col contains elem2"もtrueを返す必要がある。
  4つの落とし穴がある。
    1. Defining equals with the wrong signature.
    2. Changing equals without also changing hashCode.
    3. Defining equals in terms of mutable fields.
    4. Failing to define equals as an equivalence relation.
  Pitfall #1: Defining equals with the wrong signature.
    class Anyで定義されているequals
      def equals(x$1: Any): Boolean
    signatureが合わなければ当然overrideにならないが、間違えやすい。
      class Point (val x: Int, val y: Int) {
        def equals(other: Point): Boolean = x == other.x && y == other.y }}
      上記でも一見OKに見えるが、otherの方がAnyではないのでoverrideならない。
        overloadになってしまう。
        override修飾子も必要。
      正しくは下記でpattern matching等で型判定も必要。
      class Point (val x: Int, val y: Int) {
        override def equals(other: Any): Boolean = other match {
          case that: Point => x == that.x && y == that.y
          case _ => false }}
      ** overrideをつければsignatureが違いでコンパイルエラーになる。
  Pitfall #2: Changing equals without also changing hashCode
    hashCode methodもequals methodに合わせて再定義する必要がある。
    hashCodeもclass Anyで定義されている。
      def hashCode(): Int
    hashCodeはhashSetやhashMap等でobjectを検索する際に使われる。
　  o1 equals o2 なら hashCode(o1) == hashCode(o2) である必要がある。
      同一のものは必ず同じhash bucketに入る必要がある。
        hashを使って検索する際に同じhash bucket内しかチェックしないから。
    hashCode(o1) == hashCode(o2) でも o1 equals o2 である必要はない。
      同じhash bucketに複数の要素があっても良い。
        シノニムがあっても解決できると言う事。
    JavaでもequalsとhashCodeを合わせて再定義する様に要求している。
  Pitfall #3: Defining equals in terms of mutable fields
    hashCodeの生成ネタにはimmutableな値のみにする必要がある。
    mutableな値にするとhashSet等に格納後に値を変更した場合問題になる。
      fieldの更新によりhashCodeが変更になってもhash bucketの移動はされない。
      間違ったhash bucketに格納されている事になってしまう。
        contain等のmethodが正常に働かくなる。
    mutableな値を使って同一性判定をしたい場合はequals以外の名前のmethodを作る。
      例えばequalContentsとか。
      equalsとhashCodeはdefaultのobjectのidベースにしても良い。
      ==をこの意味では使えなくなってしまうが、ここはtrade off。
  Pitfall #4: Failing to define equals as an equivalence relation
    scala.Anyで定義されているequals methodは同値関係を満たす必要がある。
      反射律
        x.equals(x)が真。
      対称律
        x.equals(y)とy.equals(x)の真偽が一致する。
      推移律
        x.equals(y)が真かつy.equals(z)が真ならx.equals(z)も真。
    一貫性も必要。
       x.equals(y)の結果が何度呼び出しても同じである事。
          equalsの判定に使われる情報が変更されない限り。
    nullとの同等にならない事も必要。
      xがnon-nullならx.equals(null)は偽
    sub classとsuper classを混ぜてequalsで比較する場合が難しい。
      対称律、推移律を満たすのが難しい。
    sub classのequalsでsuper classには無いfieldも評価するか?
      評価する場合はsub classとsuper classは同一に出来ない。
      評価する場合はsub classとsuper classは同一にした方が便利。
    canEquals methodを使ってsub class側でどのsuper classと同一にするか決める。
      override def canEqual(other: Any) = other.isInstanceOf[super class]
      同一に出来る最上位のsuper classのinstanceなら真を返すようにする。
      super classとは同一に出来ない場合はsuper class=自分のclassとする。
    The Liskov Substitution Principle (LSP)
      superclass instance要求される所ではsub classのinstanceを使える様にすべき。
      sub classとsuper classは同一に出来ない事がLSP違反になるか?
        違反しないと解釈している。
          ?? 同一判定がfalseになっても使えない訳ではないから ??
          ?? 使える必要があっても全く同じ振る舞いをする事は要求されていない??
        ?? 違反すると言っている人たちもいる ??

28.3 Defining equality for parameterized types
  型パラメータを持つclassのequals methodを実装する場合。
    override def equals(other: Any) = other match {
      case that: Branch[_] => ... }
    override def canEqual(other: Any) = other.isInstanceOf[Branch[_]]
  型パラメータをwild cardにしてequalsやcanEqualを実装する必要ある。
    erasureによって実行時は型パラメータの情報は消去されている。
    pattern matchingやisInstanceOf等のrun-time型チェックには使えない。
  型パラメータが異なる場合はequalsはfalseを返すべき。
　  型パラメータチェックできなくても要素を比較した際にfalseになるはず。
    equalsの実装に要素の比較が含まれていれば問題ない。

28.4 Recipes for equals and hashCode
  equals
    super classでfinalになっていないならequalsのoverrideを検討すべき。
    non-final classではcanEqualの実装も検討すべき。
    引数の型はAnyにする。
    pattern matchingで自分の型と一致するかをチェックする。
    canEqualで比較可能かチェックする。
    super classのequalsをチェックする。
    追加したfieldが同一かチェックする。
    型が違い場合はfalseを返す。
  canEqual
    isInstanceOfで同一になりえる型かどうかをチェックする。
    通常は自分のclass
  hashCode
    JavaのhashCodeの生成方法と同じ。
    equalsで参照されているfieldを計算に含める。
    1番目のfieldのhashCodeを求めて41を足す。
    上記に41を掛けて2番目のfieldのhashCodeを足す。
    上記2行を全てのfield分繰り返す。
      override def hashCode: Int =
        41 * (41 * (41 + a.hashCode) + b.hashCode) + c.hashCode
    Int, Short, Byte, CharのhashCodeはそれ自身なので、hashCodeの呼び出しは不要。
    41は奇数の素数
      overflowによる情報ロスを最小にするためには奇数の素数を掛けた方が良い。
      最初の計算値が0になり難い様に41を足している。
        fieldの値が0である事よりも-41である事の方が少ないと仮定。
    super.hashCodeから計算を始めても良い。
    fieldがcollectionの場合もfieldのhashCodeを使えばよい。
      Arrayの場合はhashCodeに要素が取り入れられていないので注意が必要。
        Arrayの要素をhashのネタにしたい場合は要素を個別に扱う必要あり。
    hashCodeをcacheしても良い。
      immutableならdefではなくてvalでoverrideするだけでこれが出来る。
      cacheの分メモリ消費が増えるので注意。

28.5 Conclusion
  正しいequalsの実装は驚くほど難しい。
  case classとして実装すればcompilerが自動的に正しいequals等を実装してくれる。