Revert "Revert "Add Reference type""

This reverts commit 6f2f2c026b0b6e372194794e171208a91d74f852.

Reason for revert: mac build problem could be easily fixed

Mac build failure was caused by not declaring template specialization
in header file. Unfortunately, it cannot be easily declared there,
as that would cause cyclic declaration.

The reason why Reference<T>(Reference<O>) constructor could get only
unresolved references is because there is no way to check that the
requested conversion is valid (without specialization or rtti).

However, the appeared messy solution is to be deleted with moving
lookup calls outside of the parser.

Test: builds, hidl_test
Test: builds on mac

Change-Id: Icb24e2ad52563f659e758a186d90e414ab7f1c59
diff --git a/AST.cpp b/AST.cpp
index e33fbbf..b9c3b9c 100644
--- a/AST.cpp
+++ b/AST.cpp
@@ -175,19 +175,7 @@
     mImportedASTs.insert(ast);
 }
 
-bool AST::addTypeDef(const char* localName, Type* type, const Location& location,
-                     std::string* errorMsg, Scope* scope) {
-    // The reason we wrap the given type in a TypeDef is simply to suppress
-    // emitting any type definitions later on, since this is just an alias
-    // to a type defined elsewhere.
-    return addScopedTypeInternal(new TypeDef(localName, location, scope, type), errorMsg, scope);
-}
-
 bool AST::addScopedType(NamedType* type, std::string* errorMsg, Scope* scope) {
-    return addScopedTypeInternal(type, errorMsg, scope);
-}
-
-bool AST::addScopedTypeInternal(NamedType* type, std::string* errorMsg, Scope* scope) {
     bool success = scope->addType(type, errorMsg);
     if (!success) {
         return false;
diff --git a/AST.h b/AST.h
index 8a89a6f..c328434 100644
--- a/AST.h
+++ b/AST.h
@@ -51,10 +51,6 @@
     bool containsInterfaces() const;
 
     // Returns true iff successful.
-    bool addTypeDef(const char* localName, Type* type, const Location& location,
-                    std::string* errorMsg, Scope* scope);
-
-    // Returns true iff successful.
     bool addScopedType(NamedType* type, std::string* errorMsg, Scope* scope);
 
     const std::string &getFilename() const;
@@ -147,8 +143,6 @@
     // used by the parser.
     size_t mSyntaxErrors = 0;
 
-    bool addScopedTypeInternal(NamedType* type, std::string* errorMsg, Scope* scope);
-
     // Helper functions for lookupType.
     Type* lookupTypeLocally(const FQName& fqName, Scope* scope);
     status_t lookupAutofilledType(const FQName &fqName, Type **returnedType);
diff --git a/ArrayType.cpp b/ArrayType.cpp
index 382665b..ccbccb6 100644
--- a/ArrayType.cpp
+++ b/ArrayType.cpp
@@ -29,8 +29,9 @@
     prependDimension(size);
 }
 
-ArrayType::ArrayType(Type *elementType, ConstantExpression *size)
+ArrayType::ArrayType(const Reference<Type>& elementType, ConstantExpression* size)
     : mElementType(elementType) {
+    CHECK(!elementType.isEmptyReference());
     prependDimension(size);
 }
 
@@ -54,7 +55,7 @@
     return mElementType->canCheckEquality();
 }
 
-Type *ArrayType::getElementType() const {
+Type* ArrayType::getElementType() const {
     return mElementType;
 }
 
diff --git a/ArrayType.h b/ArrayType.h
index 05ba783..ab0590c 100644
--- a/ArrayType.h
+++ b/ArrayType.h
@@ -18,6 +18,7 @@
 
 #define ARRAY_TYPE_H_
 
+#include "Reference.h"
 #include "Type.h"
 
 #include <vector>
@@ -30,12 +31,12 @@
     // Extends existing array by adding another dimension.
     ArrayType(ArrayType *srcArray, ConstantExpression *size);
 
-    ArrayType(Type *elementType, ConstantExpression *size);
+    ArrayType(const Reference<Type>& elementType, ConstantExpression* size);
 
     bool isArray() const override;
     bool canCheckEquality() const override;
 
-    Type *getElementType() const;
+    Type* getElementType() const;
 
     void prependDimension(ConstantExpression *size);
     void appendDimension(ConstantExpression *size);
@@ -131,9 +132,9 @@
 
     void getAlignmentAndSize(size_t *align, size_t *size) const override;
 
-private:
-    Type *mElementType;
-    std::vector<ConstantExpression *> mSizes;
+   private:
+    Reference<Type> mElementType;
+    std::vector<ConstantExpression*> mSizes;
 
     size_t dimension() const;
 
diff --git a/CompoundType.cpp b/CompoundType.cpp
index b138d7b..da30747 100644
--- a/CompoundType.cpp
+++ b/CompoundType.cpp
@@ -1115,9 +1115,9 @@
 
 ////////////////////////////////////////////////////////////////////////////////
 
-CompoundField::CompoundField(const char *name, Type *type)
-    : mName(name),
-      mType(type) {
+CompoundField::CompoundField(const char* name, const Reference<Type>& type)
+    : mName(name), mType(type) {
+    CHECK(!type.isEmptyReference());
 }
 
 std::string CompoundField::name() const {
@@ -1125,7 +1125,7 @@
 }
 
 const Type &CompoundField::type() const {
-    return *mType;
+    return *(mType.get());
 }
 
 }  // namespace android
diff --git a/CompoundType.h b/CompoundType.h
index 4917dec..2674544 100644
--- a/CompoundType.h
+++ b/CompoundType.h
@@ -18,6 +18,7 @@
 
 #define COMPOUND_TYPE_H_
 
+#include "Reference.h"
 #include "Scope.h"
 
 #include <vector>
@@ -147,14 +148,14 @@
 };
 
 struct CompoundField {
-    CompoundField(const char *name, Type *type);
+    CompoundField(const char* name, const Reference<Type>& type);
 
     std::string name() const;
     const Type &type() const;
 
 private:
     std::string mName;
-    Type *mType;
+    Reference<Type> mType;
 
     DISALLOW_COPY_AND_ASSIGN(CompoundField);
 };
diff --git a/EnumType.cpp b/EnumType.cpp
index fb8545f..9f70287 100644
--- a/EnumType.cpp
+++ b/EnumType.cpp
@@ -17,6 +17,7 @@
 #include "EnumType.h"
 
 #include "Annotation.h"
+#include "Location.h"
 #include "ScalarType.h"
 
 #include <inttypes.h>
@@ -25,11 +26,12 @@
 
 namespace android {
 
-EnumType::EnumType(const char* localName, const Location& location, Type* storageType,
-                   Scope* parent)
+EnumType::EnumType(const char* localName, const Location& location,
+                   const Reference<Type>& storageType, Scope* parent)
     : Scope(localName, location, parent), mValues(), mStorageType(storageType) {
-    mBitfieldType = new BitFieldType();
-    mBitfieldType->setElementType(this);
+    BitFieldType* bitfieldType = new BitFieldType();
+    bitfieldType->setElementType(Reference<Type>(this, Location()));
+    mBitfieldType.set(bitfieldType);
 }
 
 const Type *EnumType::storageType() const {
@@ -99,7 +101,7 @@
     return "TYPE_ENUM";
 }
 
-BitFieldType *EnumType::getBitfieldType() const {
+BitFieldType* EnumType::getBitfieldType() const {
     return mBitfieldType;
 }
 
@@ -722,7 +724,7 @@
     return "mask" + (mElementType == nullptr ? "" : (" of " + mElementType->typeName()));
 }
 
-bool BitFieldType::isCompatibleElementType(Type *elementType) const {
+bool BitFieldType::isCompatibleElementType(Type* elementType) const {
     return elementType->isEnum();
 }
 
@@ -764,8 +766,8 @@
     out << "scalar_type: \""
         << mElementType->resolveToScalarType()->getVtsScalarType()
         << "\"\n";
-    out << "predefined_type: \""
-        << static_cast<NamedType *>(mElementType)->fullName() << "\"\n";
+    out << "predefined_type: \"" << static_cast<NamedType*>(mElementType.get())->fullName()
+        << "\"\n";
     return OK;
 }
 
@@ -790,9 +792,9 @@
             true /* needsCast */);
 }
 
-EnumType *BitFieldType::getEnumType() const {
+EnumType* BitFieldType::getEnumType() const {
     CHECK(mElementType->isEnum());
-    return static_cast<EnumType *>(mElementType);
+    return static_cast<EnumType*>(mElementType.get());
 }
 
 // a bitfield maps to the underlying scalar type in C++, so operator<< is
diff --git a/EnumType.h b/EnumType.h
index d829292..35db597 100644
--- a/EnumType.h
+++ b/EnumType.h
@@ -19,6 +19,7 @@
 #define ENUM_TYPE_H_
 
 #include "ConstantExpression.h"
+#include "Reference.h"
 #include "Scope.h"
 
 #include <vector>
@@ -29,7 +30,8 @@
 struct BitFieldType;
 
 struct EnumType : public Scope {
-    EnumType(const char* localName, const Location& location, Type* storageType, Scope* parent);
+    EnumType(const char* localName, const Location& location, const Reference<Type>& storageType,
+             Scope* parent);
 
     const Type *storageType() const;
     const std::vector<EnumValue *> &values() const;
@@ -112,8 +114,10 @@
             const std::string &op) const;
 
     std::vector<EnumValue *> mValues;
-    Type *mStorageType;
-    BitFieldType *mBitfieldType;
+    Reference<Type> mStorageType;
+    // TODO(b/64272670): Dot not store BitFieldType as it is not owned.
+    // It is kept here to avoid const-cast (BitFieldType owns non-const EnumType).
+    Reference<BitFieldType> mBitfieldType;
 
     DISALLOW_COPY_AND_ASSIGN(EnumType);
 };
diff --git a/Interface.cpp b/Interface.cpp
index 1adf92d..805d81c 100644
--- a/Interface.cpp
+++ b/Interface.cpp
@@ -68,8 +68,10 @@
 };
 
 Interface::Interface(const char* localName, const Location& location, Scope* parent,
-                     Interface* super)
-    : Scope(localName, location, parent), mSuperType(super), mIsJavaCompatibleInProgress(false) {}
+                     const Reference<Interface>& superType)
+    : Scope(localName, location, parent),
+      mSuperType(superType),
+      mIsJavaCompatibleInProgress(false) {}
 
 std::string Interface::typeName() const {
     return "interface " + localName();
@@ -461,7 +463,7 @@
 
     serial += userDefinedMethods().size();
 
-    const Interface *ancestor = mSuperType;
+    const Interface* ancestor = superType();
     while (ancestor != nullptr) {
         serial += ancestor->userDefinedMethods().size();
         ancestor = ancestor->superType();
@@ -510,8 +512,8 @@
     return true;
 }
 
-const Interface *Interface::superType() const {
-    return mSuperType;
+const Interface* Interface::superType() const {
+    return isIBase() ? nullptr : mSuperType;
 }
 
 std::vector<const Interface *> Interface::typeChain() const {
@@ -519,13 +521,13 @@
     const Interface *iface = this;
     while (iface != nullptr) {
         v.push_back(iface);
-        iface = iface->mSuperType;
+        iface = iface->superType();
     }
     return v;
 }
 
 std::vector<const Interface *> Interface::superTypeChain() const {
-    return superType()->typeChain(); // should work even if superType is nullptr
+    return isIBase() ? std::vector<const Interface*>() : superType()->typeChain();
 }
 
 bool Interface::isElidableType() const {
@@ -890,7 +892,7 @@
         return true;
     }
 
-    if (mSuperType != nullptr && !mSuperType->isJavaCompatible()) {
+    if (superType() != nullptr && !superType()->isJavaCompatible()) {
         mIsJavaCompatibleInProgress = false;
         return false;
     }
diff --git a/Interface.h b/Interface.h
index b37dc60..9d6e50d 100644
--- a/Interface.h
+++ b/Interface.h
@@ -18,16 +18,19 @@
 
 #define INTERFACE_H_
 
-#include "Scope.h"
 #include <vector>
 
+#include "Reference.h"
+#include "Scope.h"
+
 namespace android {
 
 struct Method;
 struct InterfaceAndMethod;
 
 struct Interface : public Scope {
-    Interface(const char* localName, const Location& location, Scope* parent, Interface* super);
+    Interface(const char* localName, const Location& location, Scope* parent,
+              const Reference<Interface>& superType);
 
     bool addMethod(Method *method);
     bool addAllReservedMethods();
@@ -35,11 +38,10 @@
     bool isElidableType() const override;
     bool isInterface() const override;
     bool isBinder() const override;
-    bool isRootType() const { return mSuperType == nullptr; }
     bool isIBase() const { return fqName() == gIBaseFqName; }
     std::string typeName() const override;
 
-    const Interface *superType() const;
+    const Interface* superType() const;
 
     Method *lookupMethod(std::string name) const;
     // Super type chain to root type.
@@ -109,21 +111,24 @@
 
     bool isJavaCompatible() const override;
 
-private:
-    Interface *mSuperType;
-    std::vector<Method *> mUserMethods;
-    std::vector<Method *> mReservedMethods;
+   private:
+    Reference<Interface> mSuperType;
+
+    std::vector<Method*> mUserMethods;
+    std::vector<Method*> mReservedMethods;
+
     mutable bool mIsJavaCompatibleInProgress;
-    bool fillPingMethod(Method *method) const;
-    bool fillDescriptorChainMethod(Method *method) const;
-    bool fillGetDescriptorMethod(Method *method) const;
-    bool fillHashChainMethod(Method *method) const;
-    bool fillSyspropsChangedMethod(Method *method) const;
-    bool fillLinkToDeathMethod(Method *method) const;
-    bool fillUnlinkToDeathMethod(Method *method) const;
-    bool fillSetHALInstrumentationMethod(Method *method) const;
-    bool fillGetDebugInfoMethod(Method *method) const;
-    bool fillDebugMethod(Method *method) const;
+
+    bool fillPingMethod(Method* method) const;
+    bool fillDescriptorChainMethod(Method* method) const;
+    bool fillGetDescriptorMethod(Method* method) const;
+    bool fillHashChainMethod(Method* method) const;
+    bool fillSyspropsChangedMethod(Method* method) const;
+    bool fillLinkToDeathMethod(Method* method) const;
+    bool fillUnlinkToDeathMethod(Method* method) const;
+    bool fillSetHALInstrumentationMethod(Method* method) const;
+    bool fillGetDebugInfoMethod(Method* method) const;
+    bool fillDebugMethod(Method* method) const;
 
     DISALLOW_COPY_AND_ASSIGN(Interface);
 };
@@ -135,7 +140,8 @@
           mMethod(method) {}
     Method *method() const { return mMethod; }
     const Interface *interface() const { return mInterface; }
-private:
+
+   private:
     // do not own these objects.
     const Interface *mInterface;
     Method *mMethod;
diff --git a/Location.h b/Location.h
index 84dfc0e..994b03e 100644
--- a/Location.h
+++ b/Location.h
@@ -17,27 +17,28 @@
 #ifndef LOCATION_H_
 #define LOCATION_H_
 
-#include <iostream>
 #include <stdint.h>
+#include <iostream>
 #include <string>
 
 // Mimics for yy::location and yy::position
 namespace android {
 
 struct Position {
+    Position() = default;
     Position(std::string f, size_t l, size_t c)
             : mFilename(f), mLine(l), mColumn(c) {}
     inline const std::string &filename() const { return mFilename; }
     inline size_t line() const { return mLine; }
     inline size_t column() const { return mColumn; }
 
-private:
+   private:
     // File name to which this position refers.
-    const std::string mFilename;
+    std::string mFilename;
     // Current line number.
-    const size_t mLine;
+    size_t mLine;
     // Current column number.
-    const size_t mColumn;
+    size_t mColumn;
 };
 
 inline std::ostream& operator<< (std::ostream& ostr, const Position& pos) {
@@ -48,20 +49,30 @@
 }
 
 struct Location {
-    Location (Position begin, Position end)
-            : mBegin(begin), mEnd(end) {}
-    inline const Position &begin() const { return mBegin; }
-    inline const Position &end() const { return mEnd; }
+    Location() = default;
+    Location(const Position& begin, const Position& end) { setLocation(begin, end); }
 
-    inline static Location startOf(const std::string &path) {
+    void setLocation(const Position& begin, const Position& end) {
+        mIsValid = true;
+        mBegin = begin;
+        mEnd = end;
+    }
+
+    bool isValid() const { return mIsValid; }
+    const Position& begin() const { return mBegin; }
+    const Position& end() const { return mEnd; }
+
+    static Location startOf(const std::string& path) {
         return Location(Position(path, 1, 1), Position(path, 1, 1));
     }
 
-private:
+   private:
+    bool mIsValid = false;
+
     // Beginning of the located region.
-    const Position mBegin;
+    Position mBegin;
     // End of the located region.
-    const Position mEnd;
+    Position mEnd;
 };
 
 inline std::ostream& operator<< (std::ostream& ostr, const Location& loc) {
diff --git a/Method.cpp b/Method.cpp
index 6c0ebf5..5a3e248 100644
--- a/Method.cpp
+++ b/Method.cpp
@@ -242,17 +242,14 @@
 
 ////////////////////////////////////////////////////////////////////////////////
 
-TypedVar::TypedVar(const char *name, Type *type)
-    : mName(name),
-      mType(type) {
-}
+TypedVar::TypedVar(const char* name, const Reference<Type>& type) : mName(name), mType(type) {}
 
 std::string TypedVar::name() const {
     return mName;
 }
 
 const Type &TypedVar::type() const {
-    return *mType;
+    return *(mType.get());
 }
 
 bool TypedVar::isJavaCompatible() const {
diff --git a/Method.h b/Method.h
index 6d7664b..b77c66f 100644
--- a/Method.h
+++ b/Method.h
@@ -26,6 +26,8 @@
 #include <string>
 #include <vector>
 
+#include "Reference.h"
+
 namespace android {
 
 struct Annotation;
@@ -114,7 +116,7 @@
 };
 
 struct TypedVar {
-    TypedVar(const char *name, Type *type);
+    TypedVar(const char* name, const Reference<Type>& type);
 
     std::string name() const;
     const Type &type() const;
@@ -123,7 +125,7 @@
 
 private:
     std::string mName;
-    Type *mType;
+    Reference<Type> mType;
 
     DISALLOW_COPY_AND_ASSIGN(TypedVar);
 };
diff --git a/Reference.h b/Reference.h
new file mode 100644
index 0000000..aab3b8f
--- /dev/null
+++ b/Reference.h
@@ -0,0 +1,110 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef REFERENCE_H_
+
+#define REFERENCE_H_
+
+#include <android-base/logging.h>
+#include <hidl-util/FQName.h>
+
+#include "Location.h"
+
+namespace android {
+
+/**
+ * Reference placeholder
+ */
+template <class T>
+struct Reference {
+    Reference() = default;
+
+    Reference(const FQName& fqName, const Location& location)
+        : mResolved(nullptr), mFqName(fqName), mLocation(location) {}
+
+    Reference(T* type, const Location& location) : mResolved(type), mLocation(location) {
+        CHECK(type != nullptr);
+    }
+
+    Reference(const Reference& ref)
+        : mResolved(ref.mResolved), mFqName(ref.mFqName), mLocation(ref.mLocation) {}
+
+    /* Storing type cast, valid only before resolving */
+    template <class OtherT>
+    Reference(const Reference<OtherT>& ref)
+        : mResolved(nullptr), mFqName(ref.mFqName), mLocation(ref.mLocation) {
+        CHECK(!ref.isResolved());
+    }
+
+    /* Returns true iff referred type is resolved
+       Referred type's field might be not resolved */
+    bool isResolved() const { return mResolved != nullptr; }
+
+    operator T*() const { return get(); }
+
+    T* operator->() const { return get(); }
+
+    T* get() const {
+        CHECK(mResolved != nullptr);
+        return mResolved;
+    }
+
+    void clearResolved() { mResolved = nullptr; }
+
+    void set(T* resolved) {
+        CHECK(!isResolved());
+        CHECK(resolved != nullptr);
+        mResolved = resolved;
+    }
+
+    /* Returns true iff this is reference to null:
+       not resolved and has not name for lookup */
+    bool isEmptyReference() const { return !isResolved() && !hasLookupFqName(); }
+
+    const FQName& getLookupFqName() const {
+        CHECK(hasLookupFqName());
+        return mFqName;
+    }
+
+    bool hasLocation() const { return mLocation.isValid(); }
+
+    const Location& getLocation() const {
+        CHECK(hasLocation());
+        return mLocation;
+    }
+
+   private:
+    /* Referred type */
+    T* mResolved = nullptr;
+    /* Reference name for lookup */
+    FQName mFqName;
+    /* Reference location is mainly used for printing errors */
+    Location mLocation;
+
+    bool hasLookupFqName() const {
+        // Valid only while not resolved to prevent confusion when
+        // ref.hasLookupFqName() is false while ref,get()->fqName is valid.
+        CHECK(!isResolved());
+        return mFqName.isValid();
+    }
+
+    template <class OtherT>
+    friend struct Reference;
+};
+
+}  // namespace android
+
+#endif  // REFERENCE_H_
diff --git a/Type.cpp b/Type.cpp
index ea8df98..6512fd7 100644
--- a/Type.cpp
+++ b/Type.cpp
@@ -470,16 +470,18 @@
 
 ////////////////////////////////////////
 
-TemplatedType::TemplatedType() : mElementType(nullptr) {
-}
+TemplatedType::TemplatedType() {}
 
-void TemplatedType::setElementType(Type *elementType) {
-    CHECK(mElementType == nullptr); // can only be set once.
+void TemplatedType::setElementType(const Reference<Type>& elementType) {
+    // can only be set once.
+    CHECK(mElementType.isEmptyReference());
+    CHECK(!elementType.isEmptyReference());
+
     CHECK(isCompatibleElementType(elementType));
     mElementType = elementType;
 }
 
-Type *TemplatedType::getElementType() const {
+Type* TemplatedType::getElementType() const {
     return mElementType;
 }
 
@@ -512,5 +514,6 @@
     out << "}\n";
     return OK;
 }
+
 }  // namespace android
 
diff --git a/Type.h b/Type.h
index 8e139d4..f4769ba 100644
--- a/Type.h
+++ b/Type.h
@@ -24,6 +24,8 @@
 #include <vector>
 #include <set>
 
+#include "Reference.h"
+
 namespace android {
 
 struct Annotation;
@@ -255,16 +257,17 @@
 
 /* Base type for VectorType and RefType. */
 struct TemplatedType : public Type {
-    void setElementType(Type *elementType);
-    Type *getElementType() const;
+    void setElementType(const Reference<Type>& elementType);
+    Type* getElementType() const;
     bool isTemplatedType() const override;
-    virtual bool isCompatibleElementType(Type *elementType) const = 0;
+    virtual bool isCompatibleElementType(Type* elementType) const = 0;
     status_t emitVtsTypeDeclarations(Formatter &out) const override;
     status_t emitVtsAttributeType(Formatter &out) const override;
 protected:
     TemplatedType();
-    Type *mElementType;
-private:
+    Reference<Type> mElementType;
+
+   private:
     DISALLOW_COPY_AND_ASSIGN(TemplatedType);
 };
 
diff --git a/TypeDef.cpp b/TypeDef.cpp
index f419efe..f470711 100644
--- a/TypeDef.cpp
+++ b/TypeDef.cpp
@@ -21,7 +21,8 @@
 
 namespace android {
 
-TypeDef::TypeDef(const char* localName, const Location& location, Scope* parent, Type* type)
+TypeDef::TypeDef(const char* localName, const Location& location, Scope* parent,
+                 const Reference<Type>& type)
     : NamedType(localName, location, parent), mReferencedType(type) {}
 
 const ScalarType *TypeDef::resolveToScalarType() const {
@@ -29,7 +30,7 @@
     return NULL;
 }
 
-Type *TypeDef::referencedType() const {
+Type* TypeDef::referencedType() const {
     return mReferencedType;
 }
 
diff --git a/TypeDef.h b/TypeDef.h
index 7914363..e6af502 100644
--- a/TypeDef.h
+++ b/TypeDef.h
@@ -23,13 +23,14 @@
 namespace android {
 
 struct TypeDef : public NamedType {
-    TypeDef(const char* localName, const Location& location, Scope* parent, Type* type);
+    TypeDef(const char* localName, const Location& location, Scope* parent,
+            const Reference<Type>& type);
 
     const ScalarType *resolveToScalarType() const override;
 
     std::string typeName() const override;
 
-    Type *referencedType() const;
+    Type* referencedType() const;
 
     bool isInterface() const override;
     bool isEnum() const override;
@@ -39,8 +40,8 @@
 
     status_t emitTypeDeclarations(Formatter &out) const override;
 
-private:
-    Type *mReferencedType;
+   private:
+    Reference<Type> mReferencedType;
 
     DISALLOW_COPY_AND_ASSIGN(TypeDef);
 };
diff --git a/VectorType.cpp b/VectorType.cpp
index 4d1dae8..50ceef0 100644
--- a/VectorType.cpp
+++ b/VectorType.cpp
@@ -725,7 +725,7 @@
     }
 
     if (mElementType->isArray()) {
-        return static_cast<ArrayType *>(mElementType)->countDimensions() == 1;
+        return static_cast<ArrayType*>(mElementType.get())->countDimensions() == 1;
     }
 
     if (mElementType->isVector()) {
diff --git a/hidl-gen_y.yy b/hidl-gen_y.yy
index 0e610df..805f671 100644
--- a/hidl-gen_y.yy
+++ b/hidl-gen_y.yy
@@ -16,8 +16,8 @@
 
 %{
 
-#include "Annotation.h"
 #include "AST.h"
+#include "Annotation.h"
 #include "ArrayType.h"
 #include "CompoundType.h"
 #include "ConstantExpression.h"
@@ -25,9 +25,10 @@
 #include "Interface.h"
 #include "Location.h"
 #include "Method.h"
-#include "Scope.h"
-#include "VectorType.h"
 #include "RefType.h"
+#include "Scope.h"
+#include "TypeDef.h"
+#include "VectorType.h"
 
 #include "hidl-gen_y.h"
 
@@ -257,13 +258,13 @@
 %type<str> error_stmt error
 %type<str> package
 %type<fqName> fqname
-%type<type> fqtype
+%type<referenceToType> fqtype
 %type<str> valid_identifier valid_type_name
 
-%type<type> type enum_storage_type
-%type<type> array_type_base
+%type<referenceToType> type enum_storage_type
+%type<referenceToType> array_type_base
 %type<arrayType> array_type
-%type<type> opt_extends
+%type<referenceToInterface> opt_extends
 %type<type> type_declaration type_declaration_body interface_declaration typedef_declaration
 %type<type> named_struct_or_union_declaration named_enum_declaration
 %type<type> compound_declaration annotated_compound_declaration
@@ -288,7 +289,9 @@
 
 %union {
     const char *str;
-    android::Type *type;
+    android::Type* type;
+    android::Reference<android::Type>* referenceToType;
+    android::Reference<android::Interface>* referenceToInterface;
     android::ArrayType *arrayType;
     android::TemplatedType *templatedType;
     android::FQName *fqName;
@@ -483,7 +486,9 @@
 fqtype
     : fqname
       {
-          $$ = ast->lookupType(*($1), *scope);
+          $$ = new Reference<Type>(*$1, convertYYLoc(@1));
+
+          Type* type = ast->lookupType($$->getLookupFqName(), *scope);
           if ($$ == NULL) {
               std::cerr << "ERROR: Failed to lookup type '" << $1->string() << "' at "
                         << @1
@@ -491,8 +496,13 @@
 
               YYERROR;
           }
+
+          $$->set(type);
       }
     | TYPE
+      {
+          $$ = new Reference<Type>($1, convertYYLoc(@1));
+      }
     ;
 
 package
@@ -543,17 +553,46 @@
     ;
 
 opt_extends
-    : /* empty */ { $$ = NULL; }
-    | EXTENDS fqtype { $$ = $2; }
+    : /* empty */
+      {
+          $$ = nullptr;
+      }
+    | EXTENDS fqtype
+      {
+          if (!(*$2)->isInterface()) {
+              std::cerr << "ERROR: You can only extend interfaces. at " << @2
+                        << "\n";
+
+              YYERROR;
+          }
+
+          // TODO(b/31827278)
+          // While deleting lookup calls, clear this messy conversion
+          $2->clearResolved();
+          $$ = new Reference<Interface>(*$2);
+
+          Type* type = ast->lookupType($$->getLookupFqName(), *scope);
+          if (type == nullptr) {
+              std::cerr << "ERROR: Failed to lookup type '" << $$->getLookupFqName().string() << "' at "
+                        << @2
+                        << "\n";
+              YYERROR;
+          }
+          if (!type->isInterface()) {
+              std::cerr << "ERROR: You can only extend interfaces. at " << @2
+                        << "\n";
+              YYERROR;
+          }
+          $$->set(static_cast<Interface*>(type));
+      }
 
 interface_declarations
     : /* empty */
     | interface_declarations type_declaration
       {
           std::string errorMsg;
-          if ($2 != nullptr &&
-              $2->isNamedType() &&
-              !isValidInterfaceField(static_cast<NamedType *>($2)->localName().c_str(),
+          if ($2 != nullptr && $2->isNamedType() &&
+              !isValidInterfaceField(static_cast<NamedType*>($2)->localName().c_str(),
                     &errorMsg)) {
               std::cerr << "ERROR: " << errorMsg << " at "
                         << @2 << "\n";
@@ -577,7 +616,7 @@
                 YYERROR;
             }
 
-            Interface *iface = static_cast<Interface *>(*scope);
+            Interface *iface = static_cast<Interface*>(*scope);
             if (!iface->addMethod($2)) {
                 std::cerr << "ERROR: Unable to add method '" << $2->name()
                           << "' at " << @2 << "\n";
@@ -598,7 +637,7 @@
 type_declaration
     : opt_annotations type_declaration_body
       {
-          if ($2 != nullptr) {
+          if (!$2->isTypeDef()) {
               $2->setAnnotations($1);
           } else if (!$1->empty()) {
               // Since typedefs are always resolved to their target it makes
@@ -623,9 +662,18 @@
 interface_declaration
     : INTERFACE valid_type_name opt_extends
       {
-          Type *parent = $3;
+          Reference<Interface>* superType = $3;
+          bool isIBase = ast->package().package() == gIBasePackageFqName.string();
 
-          if (ast->package().package() != gIBasePackageFqName.string()) {
+          if (isIBase) {
+              if (superType != nullptr) {
+                  std::cerr << "ERROR: IBase must not extend any interface. at " << @3
+                        << "\n";
+
+                  YYERROR;
+              }
+              superType = new Reference<Interface>();
+          } else {
               if (!ast->addImport(gIBaseFqName.string().c_str())) {
                   std::cerr << "ERROR: Unable to automatically import '"
                             << gIBaseFqName.string()
@@ -633,18 +681,15 @@
                             << "\n";
                   YYERROR;
               }
-              if (parent == nullptr) {
-                parent = ast->lookupType(gIBaseFqName, *scope);
+
+              if (superType == nullptr) {
+                  superType = new Reference<Interface>(gIBaseFqName, convertYYLoc(@$));
+                  Type* type = ast->lookupType(superType->getLookupFqName(), *scope);
+                  CHECK(type != nullptr && type->isInterface());
+                  superType->set(static_cast<Interface*>(type));
               }
           }
 
-          if (parent != NULL && !parent->isInterface()) {
-              std::cerr << "ERROR: You can only extend interfaces. at " << @3
-                        << "\n";
-
-              YYERROR;
-          }
-
           if ($2[0] != 'I') {
               std::cerr << "ERROR: All interface names must start with an 'I' "
                         << "prefix. at " << @2 << "\n";
@@ -660,8 +705,7 @@
           }
 
           Interface* iface = new Interface(
-              $2, convertYYLoc(@2), *scope,
-              static_cast<Interface *>(parent));
+              $2, convertYYLoc(@2), *scope, *superType);
 
           // Register interface immediately so it can be referenced inside
           // definition.
@@ -697,13 +741,18 @@
 typedef_declaration
     : TYPEDEF type valid_type_name
       {
+          // The reason we wrap the given type in a TypeDef is simply to suppress
+          // emitting any type definitions later on, since this is just an alias
+          // to a type defined elsewhere.
+          TypeDef* typeDef = new TypeDef($3, convertYYLoc(@2), *scope, *$2);
+
           std::string errorMsg;
-          if (!ast->addTypeDef($3, $2, convertYYLoc(@3), &errorMsg, *scope)) {
+          if (!ast->addScopedType(typeDef, &errorMsg, *scope)) {
               std::cerr << "ERROR: " << errorMsg << " at " << @3 << "\n";
               YYERROR;
           }
 
-          $$ = nullptr;
+          $$ = typeDef;
       }
     ;
 
@@ -734,11 +783,13 @@
                       *(static_cast<EnumValue *>(iden)->constExpr()), $1->string());
           } else {
               std::string errorMsg;
-              EnumValue *v = ast->lookupEnumValue(*($1), &errorMsg, *scope);
+              EnumValue* v = ast->lookupEnumValue(*$1, &errorMsg, *scope);
               if(v == nullptr) {
                   std::cerr << "ERROR: " << errorMsg << " at " << @1 << ".\n";
                   YYERROR;
               }
+
+              // TODO: Support Reference
               $$ = new ConstantExpression(*(v->constExpr()), $1->string());
           }
       }
@@ -818,7 +869,7 @@
       }
     ;
 
-typed_var : type valid_identifier { $$ = new TypedVar($2, $1); }
+typed_var : type valid_identifier { $$ = new TypedVar($2, *$1); }
     ;
 
 
@@ -869,7 +920,8 @@
       {
           $$ = $1;
 
-          if ($2 != NULL) {
+          // Compound declaration or error
+          if ($2 != nullptr) {
               $$->push_back($2);
           }
       }
@@ -887,27 +939,28 @@
                       << @2 << "\n";
             YYERROR;
         }
-        $$ = new CompoundField($2, $1);
+        $$ = new CompoundField($2, *$1);
       }
     | annotated_compound_declaration ';'
       {
         std::string errorMsg;
         if ((*scope)->isCompoundType() &&
             static_cast<CompoundType *>(*scope)->style() == CompoundType::STYLE_STRUCT &&
-            $1 != nullptr &&
-            $1->isNamedType() &&
-            !isValidStructField(static_cast<NamedType *>($1)->localName().c_str(), &errorMsg)) {
+            $1 != nullptr && $1->isNamedType() &&
+            !isValidStructField(static_cast<NamedType*>($1)->localName().c_str(), &errorMsg)) {
             std::cerr << "ERROR: " << errorMsg << " at "
                       << @2 << "\n";
             YYERROR;
         }
-        $$ = NULL;
+        // Returns fields only
+        $$ = nullptr;
       }
     ;
 
 annotated_compound_declaration
     : opt_annotations compound_declaration
       {
+          CHECK($2 != nullptr);
           $2->setAnnotations($1);
           $$ = $2;
       }
@@ -923,9 +976,9 @@
       {
           $$ = $2;
 
-          if ($$ != NULL && !$$->isValidEnumStorageType()) {
+          if ($$ != NULL && !(*$$)->isValidEnumStorageType()) {
               std::cerr << "ERROR: Invalid enum storage type ("
-                        << $2->typeName()
+                        << (*$2)->typeName()
                         << ") specified. at "
                         << @2 << "\n";
 
@@ -942,7 +995,7 @@
 named_enum_declaration
     : ENUM valid_type_name enum_storage_type
       {
-          enterScope(ast, scope, new EnumType($2, convertYYLoc(@2), $3, *scope));
+          enterScope(ast, scope, new EnumType($2, convertYYLoc(@2), *$3, *scope));
       }
       enum_declaration_body
       {
@@ -1003,48 +1056,50 @@
     : fqtype { $$ = $1; }
     | TEMPLATED '<' type '>'
       {
-          if (!$1->isCompatibleElementType($3)) {
-              std::cerr << "ERROR: " << $1->typeName() << " of " << $3->typeName()
+          if (!$1->isCompatibleElementType($3->get())) {
+              std::cerr << "ERROR: " << $1->typeName() << " of " << (*$3)->typeName()
                         << " is not supported. at " << @3 << "\n";
 
               YYERROR;
           }
-          $1->setElementType($3);
-          $$ = $1;
+          $1->setElementType(*$3);
+          $$ = new Reference<Type>($1, convertYYLoc(@1));
       }
     | TEMPLATED '<' TEMPLATED '<' type RSHIFT
       {
-          if (!$3->isCompatibleElementType($5)) {
-              std::cerr << "ERROR: " << $3->typeName() << " of " << $5->typeName()
-                        << " is not supported. at " << @3 << "\n";
+          if (!$3->isCompatibleElementType($5->get())) {
+              std::cerr << "ERROR: " << $3->typeName() << " of " << (*$5)->typeName()
+                        << " is not supported. at " << @5 << "\n";
 
               YYERROR;
           }
-          $3->setElementType($5);
+          $3->setElementType(*$5);
           if (!$1->isCompatibleElementType($3)) {
               std::cerr << "ERROR: " << $1->typeName() << " of " << $3->typeName()
                         << " is not supported. at " << @3 << "\n";
 
               YYERROR;
           }
-          $1->setElementType($3);
-          $$ = $1;
+          $1->setElementType(Reference<Type>($3, convertYYLoc(@3)));
+          $$ = new Reference<Type>($1, convertYYLoc(@1));
       }
     ;
 
 array_type
     : array_type_base '[' const_expr ']'
       {
-          if ($1->isBinder()) {
+          Reference<Type> type = *$1;
+
+          if (type->isBinder()) {
               std::cerr << "ERROR: Arrays of interface types are not supported."
                         << " at " << @1 << "\n";
 
               YYERROR;
           }
-          if ($1->isArray()) {
-              $$ = new ArrayType(static_cast<ArrayType *>($1), $3);
+          if (type.isResolved() && type->isArray()) {
+              $$ = new ArrayType(static_cast<ArrayType*>(type.get()), $3);
           } else {
-              $$ = new ArrayType($1, $3);
+              $$ = new ArrayType(type, $3);
           }
       }
     | array_type '[' const_expr ']'
@@ -1056,20 +1111,25 @@
 
 type
     : array_type_base { $$ = $1; }
-    | array_type { $$ = $1; }
-    | annotated_compound_declaration { $$ = $1; }
+    | array_type { $$ = new Reference<Type>($1, convertYYLoc(@1)); }
+    | annotated_compound_declaration
+      {
+          $$ = new Reference<Type>($1, convertYYLoc(@1));
+      }
     | INTERFACE
       {
           // "interface" is a synonym of android.hidl.base@1.0::IBase
-          $$ = ast->lookupType(gIBaseFqName, *scope);
-          if ($$ == nullptr) {
+          $$ = new Reference<Type>(gIBaseFqName, convertYYLoc(@1));
+          Type* type = ast->lookupType($$->getLookupFqName(), *scope);
+          if (type == nullptr) {
               std::cerr << "ERROR: Cannot find "
                         << gIBaseFqName.string()
                         << " at " << @1 << "\n";
 
               YYERROR;
+          }
+          $$->set(type);
       }
-    }
     ;
 
 %%