/* NSC -- new Scala compiler
 * Copyright 2005-2011 LAMP/EPFL
 * @author  Martin Odersky
 */


package scala.tools.nsc
package backend.icode
package analysis

/** A complete lattice.
 */
trait SemiLattice {
  type Elem <: AnyRef

  /** Hold together local variable and stack state. The
   *  equals method uses reference equality for top and bottom,
   *  and structural equality for other values.
   */
  final case class IState[V, S](vars: V, stack: S) {
    override def hashCode = vars.hashCode + stack.hashCode    
    override def equals(other: Any): Boolean = other match {
      case x: IState[_, _]  =>
        if ((this eq bottom) || (this eq top) || (x eq bottom) || (x eq top)) this eq x
        else stack == x.stack && vars == x.vars
      case _ =>
        false
    }
  }

  /** Return the least upper bound of a and b. */
  def lub2(exceptional: Boolean)(a: Elem, b: Elem): Elem

  /** Return the top element. */
  def top: Elem

  /** Return the bottom element. */
  def bottom: Elem

  /** Compute the least upper bound of a list of elements. */
  def lub(xs: List[Elem], exceptional: Boolean): Elem = 
    if (xs.isEmpty) bottom
    else try xs reduceLeft lub2(exceptional)
    catch { case e: LubException  => Console.println("Lub on blocks: " + xs) ; throw e }
}