//===--- TypeJoinMeet.cpp - Swift Type "Join" and "Meet"  -----------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
//  This file implements the "meet" operation for types (and, eventually,
//  "join").
//
//===----------------------------------------------------------------------===//
#include "swift/AST/ASTContext.h"
#include "swift/AST/Type.h"
#include "swift/AST/Types.h"
#include "llvm/ADT/SmallPtrSet.h"
using namespace swift;

Type Type::meet(Type type1, Type type2) {
  assert(!type1->hasTypeVariable() && !type2->hasTypeVariable() &&
         "Cannot compute meet of types involving type variables");

  // FIXME: This algorithm is woefully incomplete, and is only currently used
  // for optimizing away extra exploratory work in the constraint solver. It
  // should eventually encompass all of the subtyping rules of the language.

  // If the types are equivalent, the meet is obvious.
  if (type1->isEqual(type2))
    return type1;

  // If both are class types or opaque types that potentially have superclasses,
  // find the common superclass.
  if (type1->mayHaveSuperclass() && type2->mayHaveSuperclass()) {
    ASTContext &ctx = type1->getASTContext();
    LazyResolver *resolver = ctx.getLazyResolver();

    /// Walk the superclasses of type1 looking for type2. Record them for our
    /// second step.
    llvm::SmallPtrSet<CanType, 8> superclassesOfType1;
    CanType canType2 = type2->getCanonicalType();
    for (Type super1 = type1; super1; super1 = super1->getSuperclass(resolver)){
      CanType canSuper1 = super1->getCanonicalType();

      // If we have found the second type, we're done.
      if (canSuper1 == canType2) return super1;

      superclassesOfType1.insert(canSuper1);
    }

    // Look through the superclasses of type2 to determine if any were also
    // superclasses of type1.
    for (Type super2 = type2; super2; super2 = super2->getSuperclass(resolver)){
      CanType canSuper2 = super2->getCanonicalType();

      // If we found the first type, we're done.
      if (superclassesOfType1.count(canSuper2)) return super2;
    }

    // There is no common superclass; we're done.
    return nullptr;
  }

  // The meet can only be an existential.
  return nullptr;
}