bool
CGRecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD,
                                             const ASTRecordLayout &Layout) {
  const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();

  // If we have a primary base, lay it out first.
  if (PrimaryBase) {
    if (!Layout.isPrimaryBaseVirtual()) {
      if (!LayoutNonVirtualBase(PrimaryBase, CharUnits::Zero()))
        return false;
    } else {
      if (!LayoutVirtualBase(PrimaryBase, CharUnits::Zero()))
        return false;
    }

  // Otherwise, add a vtable / vf-table if the layout says to do so.
  } else if (Layout.hasOwnVFPtr()) {
    llvm::Type *FunctionType =
      llvm::FunctionType::get(llvm::Type::getInt32Ty(Types.getLLVMContext()),
                              /*isVarArg=*/true);
    llvm::Type *VTableTy = FunctionType->getPointerTo();

    if (getTypeAlignment(VTableTy) > Alignment) {
      // FIXME: Should we allow this to happen in Sema?
      assert(!Packed && "Alignment is wrong even with packed struct!");
      return false;
    }

    assert(NextFieldOffset.isZero() &&
           "VTable pointer must come first!");
    AppendField(CharUnits::Zero(), VTableTy->getPointerTo());
  }

  // Layout the non-virtual bases.
  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
       E = RD->bases_end(); I != E; ++I) {
    if (I->isVirtual())
      continue;

    const CXXRecordDecl *BaseDecl = 
      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());

    // We've already laid out the primary base.
    if (BaseDecl == PrimaryBase && !Layout.isPrimaryBaseVirtual())
      continue;

    if (!LayoutNonVirtualBase(BaseDecl, Layout.getBaseClassOffset(BaseDecl)))
      return false;
  }

  // Add a vb-table pointer if the layout insists.
    if (Layout.hasOwnVBPtr()) {
    CharUnits VBPtrOffset = Layout.getVBPtrOffset();
    llvm::Type *Vbptr = llvm::Type::getInt32PtrTy(Types.getLLVMContext());
    AppendPadding(VBPtrOffset, getTypeAlignment(Vbptr));
    AppendField(VBPtrOffset, Vbptr);
  }

  return true;
}

// CanUseSingleInheritance - Return whether the given record decl has a "single, 
// public, non-virtual base at offset zero (i.e. the derived class is dynamic 
// iff the base is)", according to Itanium C++ ABI, 2.95p6b.
static bool CanUseSingleInheritance(const CXXRecordDecl *RD) {
  // Check the number of bases.
  if (RD->getNumBases() != 1)
    return false;
  
  // Get the base.
  CXXRecordDecl::base_class_const_iterator Base = RD->bases_begin();
  
  // Check that the base is not virtual.
  if (Base->isVirtual())
    return false;
  
  // Check that the base is public.
  if (Base->getAccessSpecifier() != AS_public)
    return false;
  
  // Check that the class is dynamic iff the base is.
  const CXXRecordDecl *BaseDecl = 
    cast<CXXRecordDecl>(Base->getType()->getAs<RecordType>()->getDecl());
  if (!BaseDecl->isEmpty() && 
      BaseDecl->isDynamicClass() != RD->isDynamicClass())
    return false;
  
  return true;
}

void
ASTRecordLayoutBuilder::SelectPrimaryVBase(const CXXRecordDecl *RD,
                                           const CXXRecordDecl *&FirstPrimary) {
  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
         e = RD->bases_end(); i != e; ++i) {
    assert(!i->getType()->isDependentType() &&
           "Cannot layout class with dependent bases.");
    const CXXRecordDecl *Base =
      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
    if (!i->isVirtual()) {
      SelectPrimaryVBase(Base, FirstPrimary);
      if (PrimaryBase.getBase())
        return;
      continue;
    }
    if (IsNearlyEmpty(Base)) {
      if (FirstPrimary==0)
        FirstPrimary = Base;
      if (!IndirectPrimaryBases.count(Base)) {
        setPrimaryBase(Base, /*IsVirtual=*/true);
        return;
      }
    }
    assert(i->isVirtual());
    SelectPrimaryVBase(Base, FirstPrimary);
    if (PrimaryBase.getBase())
      return;
  }
}

/// LayoutVirtualBases - layout the non-virtual bases of a record decl.
bool
CGRecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD,
                                          const ASTRecordLayout &Layout) {
  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
       E = RD->bases_end(); I != E; ++I) {
    const CXXRecordDecl *BaseDecl = 
      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());

    // We only want to lay out virtual bases that aren't indirect primary bases
    // of some other base.
    if (I->isVirtual() && !IndirectPrimaryBases.count(BaseDecl)) {
      // Only lay out the base once.
      if (!LaidOutVirtualBases.insert(BaseDecl))
        continue;

      CharUnits vbaseOffset = Layout.getVBaseClassOffset(BaseDecl);
      if (!LayoutVirtualBase(BaseDecl, vbaseOffset))
        return false;
    }

    if (!BaseDecl->getNumVBases()) {
      // This base isn't interesting since it doesn't have any virtual bases.
      continue;
    }
    
    if (!LayoutVirtualBases(BaseDecl, Layout))
      return false;
  }
  return true;
}

void VTTBuilder::LayoutVirtualVTTs(const CXXRecordDecl *RD,
                                   VisitedVirtualBasesSetTy &VBases) {
  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
       E = RD->bases_end(); I != E; ++I) {
    const CXXRecordDecl *BaseDecl = 
      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
    
    // Check if this is a virtual base.
    if (I->isVirtual()) {
      // Check if we've seen this base before.
      if (!VBases.insert(BaseDecl))
        continue;
    
      CharUnits BaseOffset = 
        MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
      
      LayoutVTT(BaseSubobject(BaseDecl, BaseOffset), /*BaseIsVirtual=*/true);
    }
    
    // We only need to layout virtual VTTs for this base if it actually has
    // virtual bases.
    if (BaseDecl->getNumVBases())
      LayoutVirtualVTTs(BaseDecl, VBases);
  }
}

void ASTRecordLayoutBuilder::UpdateEmptyClassOffsets(const CXXRecordDecl *RD,
                                                     uint64_t Offset) {
  if (RD->isEmpty())
    EmptyClassOffsets.insert(std::make_pair(Offset, RD));
  
  const ASTRecordLayout &Info = Ctx.getASTRecordLayout(RD);

  // Update bases.
  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
       E = RD->bases_end(); I != E; ++I) {
    assert(!I->getType()->isDependentType() &&
           "Cannot layout class with dependent bases.");
    if (I->isVirtual())
      continue;
    
    const CXXRecordDecl *Base =
      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
    
    uint64_t BaseClassOffset = Info.getBaseClassOffset(Base);
    UpdateEmptyClassOffsets(Base, Offset + BaseClassOffset);
  }
  
  // Update fields.
  unsigned FieldNo = 0;
  for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end(); 
       I != E; ++I, ++FieldNo) {
    const FieldDecl *FD = *I;
    
    uint64_t FieldOffset = Info.getFieldOffset(FieldNo);
    UpdateEmptyClassOffsets(FD, Offset + FieldOffset);
  }
  
  // FIXME: Update virtual bases.
}

void ASTRecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD,
                                                const CXXRecordDecl *PB,
                                                int64_t Offset,
                                 llvm::SmallSet<const CXXRecordDecl*, 32> &mark,
                    llvm::SmallSet<const CXXRecordDecl*, 32> &IndirectPrimary) {
  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
         e = RD->bases_end(); i != e; ++i) {
    const CXXRecordDecl *Base = 
      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
#if 0
    const ASTRecordLayout &L = Ctx.getASTRecordLayout(Base);
    const CXXRecordDecl *PB = L.getPrimaryBase();
    if (PB && L.getPrimaryBaseWasVirtual()
        && IndirectPrimary.count(PB)) {
      int64_t BaseOffset;
      // FIXME: calculate this.
      BaseOffset = (1<<63) | (1<<31);
      VBases.push_back(PB);
      VBaseOffsets.push_back(BaseOffset);
    }
#endif
    int64_t BaseOffset = Offset;;
    // FIXME: Calculate BaseOffset.
    if (i->isVirtual()) {
      if (Base == PB) {
        // Only lay things out once.
        if (mark.count(Base))
          continue;
        // Mark it so we don't lay it out twice.
        mark.insert(Base);
        assert (IndirectPrimary.count(Base) && "IndirectPrimary was wrong");
        VBases.push_back(Base);
        VBaseOffsets.push_back(Offset);
      } else if (IndirectPrimary.count(Base)) {
        // Someone else will eventually lay this out.
        ;
      } else {
        // Only lay things out once.
        if (mark.count(Base))
          continue;
        // Mark it so we don't lay it out twice.
        mark.insert(Base);
        LayoutVirtualBase(Base);
        BaseOffset = *(VBaseOffsets.end()-1);
      }
    }
    if (Base->getNumVBases()) {
      const ASTRecordLayout &L = Ctx.getASTRecordLayout(Base);
      const CXXRecordDecl *PB = L.getPrimaryBase();
      LayoutVirtualBases(Base, PB, BaseOffset, mark, IndirectPrimary);
    }
  }
}

void 
ASTRecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD) {
  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
       e = RD->bases_end(); i != e; ++i) {
    if (!i->isVirtual()) {
      const CXXRecordDecl *Base = 
        cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
      // Skip the PrimaryBase here, as it is laid down first.
      if (Base != PrimaryBase || PrimaryBaseWasVirtual)
        LayoutBaseNonVirtually(Base, false);
    }
  }
}

void ASTRecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *Class,
                                                const CXXRecordDecl *RD,
                                                const CXXRecordDecl *PB,
                                                uint64_t Offset,
                                 llvm::SmallSet<const CXXRecordDecl*, 32> &mark,
                    llvm::SmallSet<const CXXRecordDecl*, 32> &IndirectPrimary) {
  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
         e = RD->bases_end(); i != e; ++i) {
    assert(!i->getType()->isDependentType() &&
           "Cannot layout class with dependent bases.");
    const CXXRecordDecl *Base =
      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
    uint64_t BaseOffset = Offset;
    if (i->isVirtual()) {
      if (Base == PB) {
        // Only lay things out once.
        if (mark.count(Base))
          continue;
        // Mark it so we don't lay it out twice.
        mark.insert(Base);
        assert (IndirectPrimary.count(Base) && "IndirectPrimary was wrong");
        VBases.push_back(std::make_pair(Base, Offset));
      } else if (IndirectPrimary.count(Base)) {
        // Someone else will eventually lay this out.
        ;
      } else {
        // Only lay things out once.
        if (mark.count(Base))
          continue;
        // Mark it so we don't lay it out twice.
        mark.insert(Base);
        LayoutVirtualBase(Base);
        BaseOffset = VBases.back().second;
      }
    } else {
      if (RD == Class)
        BaseOffset = getBaseOffset(Base);
      else {
        const ASTRecordLayout &Layout = Ctx.getASTRecordLayout(RD);
        BaseOffset = Offset + Layout.getBaseClassOffset(Base);
      }
    }
    
    if (Base->getNumVBases()) {
      const ASTRecordLayout &Layout = Ctx.getASTRecordLayout(Base);
      const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBaseInfo().getBase();
      LayoutVirtualBases(Class, Base, PrimaryBase, BaseOffset, mark, 
                         IndirectPrimary);
    }
  }
}

/// Returns true if \p Base is an immediate base class of \p Child
static bool isImmediateBase(const CXXRecordDecl *Child,
                            const CXXRecordDecl *Base) {
  // Note that we do NOT canonicalize the base class here, because
  // ASTRecordLayout doesn't either. If that leads us down the wrong path,
  // so be it; at least we won't crash.
  for (CXXRecordDecl::base_class_const_iterator I = Child->bases_begin(),
                                                E = Child->bases_end();
       I != E; ++I) {
    if (I->getType()->getAsCXXRecordDecl() == Base)
      return true;
  }

  return false;
}

bool RemoveBaseClass::isDirectlyDerivedFrom(const CXXRecordDecl *SubC, 
                                            const CXXRecordDecl *Base)
{
  for (CXXRecordDecl::base_class_const_iterator I = SubC->bases_begin(),
       E = SubC->bases_end(); I != E; ++I) {
    if (I->getType()->isDependentType())
      continue;

    const CXXRecordDecl *BaseDecl =
      dyn_cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
    if (Base->getCanonicalDecl() == BaseDecl->getCanonicalDecl())
      return true;
  }
  return false;
}

void InheritanceHierarchyWriter::WriteNode(QualType Type, bool FromVirtual) {
  QualType CanonType = Context.getCanonicalType(Type);

  if (FromVirtual) {
    if (KnownVirtualBases.find(CanonType) != KnownVirtualBases.end())
      return;

    // We haven't seen this virtual base before, so display it and
    // its bases.
    KnownVirtualBases.insert(CanonType);
  }

  // Declare the node itself.
  Out << "  ";
  WriteNodeReference(Type, FromVirtual);

  // Give the node a label based on the name of the class.
  std::string TypeName = Type.getAsString();
  Out << " [ shape=\"box\", label=\"" << DOT::EscapeString(TypeName);

  // If the name of the class was a typedef or something different
  // from the "real" class name, show the real class name in
  // parentheses so we don't confuse ourselves.
  if (TypeName != CanonType.getAsString()) {
    Out << "\\n(" << CanonType.getAsString() << ")";
  }

  // Finished describing the node.
  Out << " \"];\n";

  // Display the base classes.
  const CXXRecordDecl *Decl
    = static_cast<const CXXRecordDecl *>(Type->getAs<RecordType>()->getDecl());
  for (CXXRecordDecl::base_class_const_iterator Base = Decl->bases_begin();
       Base != Decl->bases_end(); ++Base) {
    QualType CanonBaseType = Context.getCanonicalType(Base->getType());

    // If this is not virtual inheritance, bump the direct base
    // count for the type.
    if (!Base->isVirtual())
      ++DirectBaseCount[CanonBaseType];

    // Write out the node (if we need to).
    WriteNode(Base->getType(), Base->isVirtual());

    // Write out the edge.
    Out << "  ";
    WriteNodeReference(Type, FromVirtual);
    Out << " -> ";
    WriteNodeReference(Base->getType(), Base->isVirtual());

    // Write out edge attributes to show the kind of inheritance.
    if (Base->isVirtual()) {
      Out << " [ style=\"dashed\" ]";
    }
    Out << ";";
  }
}

bool ASTRecordLayoutBuilder::canPlaceRecordAtOffset(const CXXRecordDecl *RD, 
                                                    uint64_t Offset) const {
  // Look for an empty class with the same type at the same offset.
  for (EmptyClassOffsetsTy::const_iterator I = 
        EmptyClassOffsets.lower_bound(Offset), 
       E = EmptyClassOffsets.upper_bound(Offset); I != E; ++I) {
    
    if (I->second == RD)
      return false;
  }
  
  const ASTRecordLayout &Info = Ctx.getASTRecordLayout(RD);

  // Check bases.
  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
       E = RD->bases_end(); I != E; ++I) {
    assert(!I->getType()->isDependentType() &&
           "Cannot layout class with dependent bases.");
    if (I->isVirtual())
      continue;
    
    const CXXRecordDecl *Base =
      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());

    uint64_t BaseClassOffset = Info.getBaseClassOffset(Base);
    
    if (!canPlaceRecordAtOffset(Base, Offset + BaseClassOffset))
      return false;
  }
  
  // Check fields.
  unsigned FieldNo = 0;
  for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end(); 
       I != E; ++I, ++FieldNo) {
    const FieldDecl *FD = *I;
    
    uint64_t FieldOffset = Info.getFieldOffset(FieldNo);
    
    if (!canPlaceFieldAtOffset(FD, Offset + FieldOffset))
      return false;
  }

  // FIXME: virtual bases.
  return true;
}

void VBTableInfo::EmitVBTableDefinition(
    CodeGenModule &CGM, const CXXRecordDecl *RD,
    llvm::GlobalVariable::LinkageTypes Linkage) const {
  assert(RD->getNumVBases() && ReusingBase->getNumVBases() &&
         "should only emit vbtables for classes with vbtables");

  const ASTRecordLayout &BaseLayout =
    CGM.getContext().getASTRecordLayout(VBPtrSubobject.getBase());
  const ASTRecordLayout &DerivedLayout =
    CGM.getContext().getASTRecordLayout(RD);

  SmallVector<llvm::Constant *, 4> Offsets;

  // The offset from ReusingBase's vbptr to itself always leads.
  CharUnits VBPtrOffset = BaseLayout.getVBPtrOffset();
  Offsets.push_back(
      llvm::ConstantInt::get(CGM.IntTy, -VBPtrOffset.getQuantity()));

  // These are laid out in the same order as in Itanium, which is the same as
  // the order of the vbase iterator.
  for (CXXRecordDecl::base_class_const_iterator I = ReusingBase->vbases_begin(),
       E = ReusingBase->vbases_end(); I != E; ++I) {
    const CXXRecordDecl *VBase = I->getType()->getAsCXXRecordDecl();
    CharUnits Offset = DerivedLayout.getVBaseClassOffset(VBase);
    assert(!Offset.isNegative());
    // Make it relative to the subobject vbptr.
    Offset -= VBPtrSubobject.getBaseOffset() + VBPtrOffset;
    Offsets.push_back(llvm::ConstantInt::get(CGM.IntTy, Offset.getQuantity()));
  }

  assert(Offsets.size() ==
         cast<llvm::ArrayType>(cast<llvm::PointerType>(GV->getType())
                               ->getElementType())->getNumElements());
  llvm::ArrayType *VBTableType =
    llvm::ArrayType::get(CGM.IntTy, Offsets.size());
  llvm::Constant *Init = llvm::ConstantArray::get(VBTableType, Offsets);
  GV->setInitializer(Init);

  // Set the correct linkage.
  GV->setLinkage(Linkage);

  // Set the right visibility.
  CGM.setTypeVisibility(GV, RD, CodeGenModule::TVK_ForVTable);
}

/// SelectPrimaryBase - Selects the primary base for the given class and
/// record that with setPrimaryBase.  We also calculate the IndirectPrimaries.
void ASTRecordLayoutBuilder::SelectPrimaryBase(const CXXRecordDecl *RD,
                    llvm::SmallSet<const CXXRecordDecl*, 32> &IndirectPrimary) {
  // We compute all the primary virtual bases for all of our direct and
  // indirect bases, and record all their primary virtual base classes.
  const CXXRecordDecl *FirstPrimary = 0;
  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
       e = RD->bases_end(); i != e; ++i) {
    const CXXRecordDecl *Base = 
      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
    SelectPrimaryForBase(Base, IndirectPrimary);
  }

  // The primary base is the first non-virtual indirect or direct base class,
  // if one exists.
  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
       e = RD->bases_end(); i != e; ++i) {
    if (!i->isVirtual()) {
      const CXXRecordDecl *Base = 
        cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
      if (Base->isDynamicClass()) {
        setPrimaryBase(Base, false);
        return;
      }
    }
  }

  setPrimaryBase(0, false);

  // Otherwise, it is the first nearly empty virtual base that is not an
  // indirect primary virtual base class, if one exists.

  // If we have no virtual bases at this point, bail out as the searching below
  // is expensive.
  if (RD->getNumVBases() == 0)
    return;

  // Then we can search for the first nearly empty virtual base itself.
  SelectPrimaryVBase(RD, FirstPrimary, IndirectPrimary);

  // Otherwise if is the first nearly empty virtual base, if one exists,
  // otherwise there is no primary base class.
  setPrimaryBase(FirstPrimary, true);
  return;
}

void ASTRecordLayoutBuilder::SelectPrimaryForBase(const CXXRecordDecl *RD,
                    llvm::SmallSet<const CXXRecordDecl*, 32> &IndirectPrimary) {
  const ASTRecordLayout &Layout = Ctx.getASTRecordLayout(RD);
  const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
  const bool PrimaryBaseWasVirtual = Layout.getPrimaryBaseWasVirtual();

  if (PrimaryBaseWasVirtual)
    IndirectPrimary.insert(PrimaryBase);

  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
       e = RD->bases_end(); i != e; ++i) {
    const CXXRecordDecl *Base = 
      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
    // Only bases with virtual bases participate in computing the
    // indirect primary virtual base classes.
    if (Base->getNumVBases())
      SelectPrimaryForBase(Base, IndirectPrimary);
  }
}

bool CXXRecordDecl::forallBases(ForallBasesCallback *BaseMatches,
                                void *OpaqueData,
                                bool AllowShortCircuit) const {
  SmallVector<const CXXRecordDecl*, 8> Queue;

  const CXXRecordDecl *Record = this;
  bool AllMatches = true;
  while (true) {
    for (CXXRecordDecl::base_class_const_iterator
           I = Record->bases_begin(), E = Record->bases_end(); I != E; ++I) {
      const RecordType *Ty = I->getType()->getAs<RecordType>();
      if (!Ty) {
        if (AllowShortCircuit) return false;
        AllMatches = false;
        continue;
      }

      CXXRecordDecl *Base = 
            cast_or_null<CXXRecordDecl>(Ty->getDecl()->getDefinition());
      if (!Base ||
          (Base->isDependentContext() &&
           !Base->isCurrentInstantiation(Record))) {
        if (AllowShortCircuit) return false;
        AllMatches = false;
        continue;
      }
      
      Queue.push_back(Base);
      if (!BaseMatches(Base, OpaqueData)) {
        if (AllowShortCircuit) return false;
        AllMatches = false;
        continue;
      }
    }

    if (Queue.empty()) break;
    Record = Queue.back(); // not actually a queue.
    Queue.pop_back();
  }

  return AllMatches;
}

/// Checks whether one class is derived from another, inclusively.
/// Properly indicates when it couldn't be determined due to
/// dependence.
///
/// This should probably be donated to AST or at least Sema.
static AccessResult IsDerivedFromInclusive(const CXXRecordDecl *Derived,
                                           const CXXRecordDecl *Target) {
  assert(Derived->getCanonicalDecl() == Derived);
  assert(Target->getCanonicalDecl() == Target);

  if (Derived == Target) return AR_accessible;

  AccessResult OnFailure = AR_inaccessible;
  llvm::SmallVector<const CXXRecordDecl*, 8> Queue; // actually a stack

  while (true) {
    for (CXXRecordDecl::base_class_const_iterator
           I = Derived->bases_begin(), E = Derived->bases_end(); I != E; ++I) {

      const CXXRecordDecl *RD;

      QualType T = I->getType();
      if (const RecordType *RT = T->getAs<RecordType>()) {
        RD = cast<CXXRecordDecl>(RT->getDecl());
      } else {
        // It's possible for a base class to be the current
        // instantiation of some enclosing template, but I'm guessing
        // nobody will ever care that we just dependently delay here.
        assert(T->isDependentType() && "non-dependent base wasn't a record?");
        OnFailure = AR_dependent;
        continue;
      }

      RD = RD->getCanonicalDecl();
      if (RD == Target) return AR_accessible;
      Queue.push_back(RD);
    }

    if (Queue.empty()) break;

    Derived = Queue.back();
    Queue.pop_back();
  }

  return OnFailure;
}

void 
CXXRecordDecl::getIndirectPrimaryBases(CXXIndirectPrimaryBaseSet& Bases) const {
  ASTContext &Context = getASTContext();

  if (!getNumVBases())
    return;

  for (CXXRecordDecl::base_class_const_iterator I = bases_begin(),
       E = bases_end(); I != E; ++I) {
    assert(!I->getType()->isDependentType() &&
           "Cannot get indirect primary bases for class with dependent bases.");

    const CXXRecordDecl *BaseDecl =
      cast<CXXRecordDecl>(I->getType()->castAs<RecordType>()->getDecl());

    // Only bases with virtual bases participate in computing the
    // indirect primary virtual base classes.
    if (BaseDecl->getNumVBases())
      AddIndirectPrimaryBases(BaseDecl, Context, Bases);
  }
}

/// Checks whether \p BaseClass is a valid virtual or direct non-virtual base
/// class of the type of \p Super.
static bool isValidBaseClass(const CXXRecordDecl *BaseClass,
                             const TypedValueRegion *Super,
                             bool IsVirtual) {
  BaseClass = BaseClass->getCanonicalDecl();

  const CXXRecordDecl *Class = Super->getValueType()->getAsCXXRecordDecl();
  if (!Class)
    return true;

  if (IsVirtual)
    return Class->isVirtuallyDerivedFrom(BaseClass);

  for (CXXRecordDecl::base_class_const_iterator I = Class->bases_begin(),
                                                E = Class->bases_end();
       I != E; ++I) {
    if (I->getType()->getAsCXXRecordDecl()->getCanonicalDecl() == BaseClass)
      return true;
  }

  return false;
}