[cfe-dev] Help with APValue comparisons

[Andy Gibbs]

Hi Jordan,

Thanks for your pointers.  I've implemented an "isEqual" function as below. 
If you have time, would you mind having a quick skim through please to see 
if I've caught the right idea.  At the moment, it holds up to the testing I 
have performed so far, but I'm always working on more test-cases!

At this point, my concern is not that isEqual may not fully distinguish two 
APValues that *are* equal, more that it should never say two APValues are 
equal when they aren't.  False negatives are much less of an issue than 
false positives!

I haven't implemented equality checking for member pointers, yet.  Again, 
this is due to a lack of understand on exactly how to implement this check 
(it seems even the dump / printPretty functions have not been fully 
implemented for this type).

If you think my approach is valid, then I will post a tentative patch for 
http://llvm.org/bugs/show_bug.cgi?id=12850.

Many, many thanks

Andy


// static member function of APValue
bool APValue::isEqual(const APValue &A, const APValue &B) {
  if (A.getKind() != B.getKind())
    return false;

  switch (A.getKind()) {
    case Uninitialized:
      return true;

    case Int:
      return (A.getInt() == B.getInt());

    case Float:
      return A.getFloat().bitwiseIsEqual(B.getFloat());

    case ComplexInt:
      return (A.getComplexIntReal() == B.getComplexIntReal()) &&
             (A.getComplexIntImag() == B.getComplexIntImag());

    case ComplexFloat:
      return A.getComplexFloatReal().bitwiseIsEqual(B.getComplexFloatReal()) 
&&
             A.getComplexFloatImag().bitwiseIsEqual(B.getComplexFloatImag());

    case Vector: {
      unsigned len = A.getVectorLength();
      if (len != B.getVectorLength()) return false;
      for (unsigned i = 0; i != len; ++i) {
        if (!isEqual(A.getVectorElt(i), B.getVectorElt(i)))
          return false;
      }
      return true;
    }

    case Array: {
      unsigned len = A.getArraySize();
      if (len != B.getArraySize()) return false;

      APValue FillerA, FillerB;
      if (A.hasArrayFiller()) FillerA = A.getArrayFiller();
      if (B.hasArrayFiller()) FillerB = B.getArrayFiller();

      // Two arrays are equal if their initialised elements are equal,
      // but also where one array is more initialised than another, where
      // those additional initialised elements are equal to the filler
      // of the other.  If they both contain uninitialised elements, the
      // fillers must also match.
      for (unsigned i = 0, a = A.getArrayInitializedElts(),
                           b = B.getArrayInitializedElts(); i != len; ++i) {
        if (!isEqual(
              (i < a) ? A.getArrayInitializedElt(i) : FillerA,
              (i < b) ? B.getArrayInitializedElt(i) : FillerB))
          return false;
        if (i >= a && i >= b) // all the initialised elements *and* the
          break;              // fillers have been compared; we're equal!
      }
      return true;
    }

    case Struct: {
      unsigned bases = A.getStructNumBases();
      if (bases != B.getStructNumBases()) return false;

      unsigned fields = A.getStructNumFields();
      if (fields != B.getStructNumFields()) return false;

      for (unsigned i = 0; i != bases; ++i) {
        if (!isEqual(A.getStructBase(i), B.getStructBase(i)))
          return false;
      }

      for (unsigned i = 0; i != fields; ++i) {
        if (!isEqual(A.getStructField(i), B.getStructField(i)))
          return false;
      }

      return true;
    }

    case Union:
      return (A.getUnionField() == B.getUnionField()) &&
             (isEqual(A.getUnionValue(), B.getUnionValue()));

    case AddrLabelDiff:
      return (A.getAddrLabelDiffLHS() == B.getAddrLabelDiffLHS()) &&
             (A.getAddrLabelDiffRHS() == B.getAddrLabelDiffRHS());

    case LValue: {
      LValueBase BaseA = A.getLValueBase();
      LValueBase BaseB = B.getLValueBase();

      // null pointers are not comparable
      if (!BaseA || !BaseB || BaseA.isNull() || BaseB.isNull()) return 
false;

      bool IsValueDecl = BaseA.is<const ValueDecl*>();
      if (IsValueDecl != BaseB.is<const ValueDecl*>()) return false;

      QualType ElemTy;
      if (IsValueDecl) {
        const ValueDecl *VD = BaseA.get<const ValueDecl*>();
        ElemTy = VD->getType();
        if (VD != BaseB.get<const ValueDecl*>()) return false;
      } else {
        const Expr *E = BaseA.get<const Expr*>();
        ElemTy = E->getType();
        if (E != BaseB.get<const Expr*>()) return false;
      }

      bool HasPath = A.hasLValuePath();
      if (HasPath != B.hasLValuePath()) return false;

      if (!HasPath) {
        return A.getLValueOffset() == B.getLValueOffset();
      }

      ArrayRef<LValuePathEntry> PathA = A.getLValuePath();
      ArrayRef<LValuePathEntry> PathB = B.getLValuePath();
      if (PathA.size() != PathB.size()) return false;

      for (unsigned I = 0, N = PathA.size(); I != N; ++I) {
        if (ElemTy->getAs<RecordType>()) {
          const Decl *BaseOrMemberA = 
BaseOrMemberType::getFromOpaqueValue(PathA[I].BaseOrMember).getPointer();
          const Decl *BaseOrMemberB = 
BaseOrMemberType::getFromOpaqueValue(PathB[I].BaseOrMember).getPointer();

          if (BaseOrMemberA != BaseOrMemberB) return false;
          if (const CXXRecordDecl *RD = 
dyn_cast<CXXRecordDecl>(BaseOrMemberA)) {
            const Type *T = RD->getTypeForDecl();
            assert(T && "getTypeForDecl did not return a valid value");
            ElemTy = QualType(T, 0);
          } else {
            const ValueDecl *VD = cast<ValueDecl>(BaseOrMemberA);
            ElemTy = VD->getType();
          }
        } else {
          if (PathA[I].ArrayIndex != PathB[I].ArrayIndex) return false;

          assert(dyn_cast<ArrayType>(ElemTy) && "Unexpected ElemTy");
          ElemTy = dyn_cast<ArrayType>(ElemTy)->getElementType();
        }
      }

      return true;
    }

    case MemberPointer:
      llvm_unreachable("isEqual unimplemented for this APValue kind!");
      return false;
  }
  llvm_unreachable("Unknown APValue kind!");
  return false;
}