//===--- ProtocolInfo.h - Abstract protocol witness layout ------*- C++ -*-===//
//
// 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 defines types for representing the abstract layout of a
// protocol.
//
//===----------------------------------------------------------------------===//

#ifndef SWIFT_IRGEN_PROTOCOLINFO_H
#define SWIFT_IRGEN_PROTOCOLINFO_H

#include "swift/AST/Decl.h"

#include "ValueWitness.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/Support/TrailingObjects.h"

namespace swift {
  class CanType;
  class Decl;
  class ProtocolConformance;
  class ProtocolDecl;

namespace irgen {
  class ConformanceInfo; // private to GenProto.cpp
  class IRGenModule;
  class TypeInfo;

/// A class which encapsulates an index into a witness table.
class WitnessIndex {
  unsigned Value : 31;
  unsigned IsPrefix : 1;
public:
  WitnessIndex() = default;
  WitnessIndex(ValueWitness index) : Value(unsigned(index)) {}
  explicit WitnessIndex(unsigned index, bool isPrefix)
    : Value(index), IsPrefix(isPrefix) {}

  unsigned getValue() const { return Value; }

  bool isPrefix() const { return IsPrefix; }
};

/// A witness to a specific element of a protocol.  Every
/// ProtocolTypeInfo stores one of these for each declaration in the
/// protocol.
/// 
/// The structure of a witness varies by the type of declaration:
///   - a function requires a single witness, the function;
///   - a variable requires two witnesses, a getter and a setter;
///   - a subscript requires two witnesses, a getter and a setter;
///   - a type requires a pointer to the metadata for that type and
///     to witness tables for each of the protocols it obeys.
class WitnessTableEntry {
  Decl *Member;
  WitnessIndex BeginIndex;

 WitnessTableEntry(Decl *member, WitnessIndex begin)
   : Member(member), BeginIndex(begin) {}

public:
  WitnessTableEntry() = default;

  Decl *getMember() const {
    return Member;
  }

  static WitnessTableEntry forPrefixBase(ProtocolDecl *proto) {
    return WitnessTableEntry(proto, WitnessIndex(0, /*isPrefix=*/ true));
  }

  static WitnessTableEntry forOutOfLineBase(ProtocolDecl *proto,
                                            WitnessIndex index) {
    return WitnessTableEntry(proto, index);
  }

  /// Is this a base-protocol entry?
  bool isBase() const { return isa<ProtocolDecl>(Member); }

  /// Is the table for this base-protocol entry "out of line",
  /// i.e. there is a witness which indirectly points to it, or is
  /// it a prefix of the layout of this protocol?
  bool isOutOfLineBase() const {
    assert(isBase());
    return !BeginIndex.isPrefix();
  }

  /// Return the index at which to find the table for this
  /// base-protocol entry.
  WitnessIndex getOutOfLineBaseIndex() const {
    assert(isOutOfLineBase());
    return BeginIndex;
  }

  static WitnessTableEntry forFunction(AbstractFunctionDecl *func,
                                       WitnessIndex index) {
    return WitnessTableEntry(func, index);
  }
  
  bool isFunction() const { return isa<AbstractFunctionDecl>(Member); }

  WitnessIndex getFunctionIndex() const {
    assert(isFunction());
    return BeginIndex;
  }
  
  static WitnessTableEntry forAssociatedType(AssociatedTypeDecl *ty,
                                             WitnessIndex index) {
    return WitnessTableEntry(ty, index);
  }
  
  bool isAssociatedType() const { return isa<AssociatedTypeDecl>(Member); }
  
  WitnessIndex getAssociatedTypeIndex() const {
    assert(isAssociatedType());
    return BeginIndex;
  }

  WitnessIndex
  getAssociatedTypeWitnessTableIndex(ProtocolDecl *target) const {
    assert(!BeginIndex.isPrefix());
    auto index = BeginIndex.getValue() + 1;
    for (auto protocol :
           cast<AssociatedTypeDecl>(Member)->getConformingProtocols(nullptr)) {
      if (protocol == target) {
        return WitnessIndex(index, false);
      }
      index++;
    }
    llvm_unreachable("protocol not in direct conformance list?");
  }
};

/// An abstract description of a protocol.
class ProtocolInfo final :
    private llvm::TrailingObjects<ProtocolInfo, WitnessTableEntry> {
  friend TrailingObjects;

  /// A singly-linked-list of all the protocols that have been laid out.
  const ProtocolInfo *NextConverted;
  friend class TypeConverter;

  /// The number of witnesses in the protocol.
  unsigned NumWitnesses;

  /// The number of table entries in this protocol layout.
  unsigned NumTableEntries;

  /// A table of all the conformances we've needed so far for this
  /// protocol.  We expect this to be quite small for most protocols.
  mutable llvm::SmallDenseMap<const ProtocolConformance*, ConformanceInfo*, 2>
    Conformances;

  ProtocolInfo(unsigned numWitnesses, ArrayRef<WitnessTableEntry> table)
    : NumWitnesses(numWitnesses), NumTableEntries(table.size()) {
    std::uninitialized_copy(table.begin(), table.end(),
                            getTrailingObjects<WitnessTableEntry>());
  }

  static ProtocolInfo *create(unsigned numWitnesses,
                              ArrayRef<WitnessTableEntry> table);

public:
  const ConformanceInfo &getConformance(IRGenModule &IGM,
                                        ProtocolDecl *protocol,
                                        const ProtocolConformance *conf) const;

  /// The number of witness slots in a conformance to this protocol;
  /// in other words, the size of the table in words.
  unsigned getNumWitnesses() const {
    return NumWitnesses;
  }

  ArrayRef<WitnessTableEntry> getWitnessEntries() const {
    return {getTrailingObjects<WitnessTableEntry>(), NumTableEntries};
  }

  const WitnessTableEntry &getWitnessEntry(Decl *member) const {
    // FIXME: do a binary search if the number of witnesses is large
    // enough.
    for (auto &witness : getWitnessEntries())
      if (witness.getMember() == member)
        return witness;
    llvm_unreachable("didn't find entry for member!");
  }

  ~ProtocolInfo();
};

} // end namespace irgen
} // end namespace swift

#endif