Add Reference type

Add Reference placeholder which keeps Type, FQName and Location.
This type is necessary for adding forward reference support:
it stores FQName until lookup happens, then stores resolved Type;
it stores Location, as all type-related checks are to be moved outside
of the parsing, so we need to keep Location for future error messages.

Reference type has overwritten operators to make it work as Type*,
providing additional checks that Type is resolved before being using.

Reference type is also useful for adding forward reference support as
it checks that every Type member call appears after lookup.

ConstantExpression is to support Reference (and to not be evaluated
during parsing) in future CL.

Test: links, compiles, hidl_test

Change-Id: I7a031b541e678032af1190209e9d2aaf4999bf1b

22 files changed, 375 insertions, 168 deletions

diff --git a/AST.cpp b/AST.cpp
index e33fbbf..b9c3b9c 100644
--- a/AST.cpp
+++ b/AST.cpp
@@ -175,19 +175,7 @@ void AST::addImportedAST(AST *ast) {
     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 @@ struct AST {
     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 @@ struct AST {
     // 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/Android.bp b/Android.bp
index ef388fc..354bd37 100644
--- a/Android.bp
+++ b/Android.bp
@@ -80,6 +80,7 @@ cc_library_host_shared {
         "NamedType.cpp",
         "PointerType.cpp",
         "FmqType.cpp",
+        "Reference.cpp",
         "RefType.cpp",
         "ScalarType.cpp",
         "Scope.cpp",
diff --git a/ArrayType.cpp b/ArrayType.cpp
index 382665b..ccbccb6 100644
--- a/ArrayType.cpp
+++ b/ArrayType.cpp
@@ -29,8 +29,9 @@ ArrayType::ArrayType(ArrayType *srcArray, ConstantExpression *size)
     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 @@ bool ArrayType::canCheckEquality() const {
     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 @@ struct ArrayType : public Type {
     // 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 @@ struct ArrayType : public Type {
 
     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 @@ void CompoundType::getAlignmentAndSize(size_t *align, size_t *size) const {
 
 ////////////////////////////////////////////////////////////////////////////////
 
-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 @@ std::string CompoundField::name() const {
 }
 
 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 @@ private:
 };
 
 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 @@ std::string EnumType::getVtsType() const {
     return "TYPE_ENUM";
 }
 
-BitFieldType *EnumType::getBitfieldType() const {
+BitFieldType* EnumType::getBitfieldType() const {
     return mBitfieldType;
 }
 
@@ -722,7 +724,7 @@ std::string BitFieldType::typeName() const {
     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 @@ status_t BitFieldType::emitVtsAttributeType(Formatter &out) const {
     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 @@ void BitFieldType::emitReaderWriter(
             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 EnumValue;
 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 @@ private:
             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 @@ enum {
 };
 
 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 @@ bool Interface::addMethod(Method *method) {
 
     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 @@ bool Interface::addAllReservedMethods() {
     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 @@ std::vector<const Interface *> Interface::typeChain() const {
     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 @@ bool Interface::isJavaCompatible() const {
         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 @@ struct Interface : public Scope {
     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 @@ struct Interface : public Scope {
 
     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 @@ struct InterfaceAndMethod {
           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 @@ inline std::ostream& operator<< (std::ostream& ostr, const Position& pos) {
 }
 
 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); }
+
+    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; }
 
-    inline static Location startOf(const std::string &path) {
+    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 @@ const TypedVar* Method::canElideCallback() const {
 
 ////////////////////////////////////////////////////////////////////////////////
 
-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 @@ private:
 };
 
 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 @@ struct TypedVar {
 
 private:
     std::string mName;
-    Type *mType;
+    Reference<Type> mType;
 
     DISALLOW_COPY_AND_ASSIGN(TypedVar);
 };
diff --git a/Reference.cpp b/Reference.cpp
new file mode 100644
index 0000000..4b53da7
--- /dev/null
+++ b/Reference.cpp
@@ -0,0 +1,39 @@
+/*
+ * 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.
+ */
+
+/* TODO(b/31827278)
+ * There would be no necessity to have cast specializations as all of them
+ * will occure only during parsing (before looking up).
+ */
+
+#include "Reference.h"
+
+#include "Interface.h"
+#include "Type.h"
+
+namespace android {
+
+template <>
+template <>
+Reference<Interface>::Reference(const Reference<Type>& ref)
+    : mFqName(ref.mFqName), mLocation(ref.mLocation) {
+    if (ref.isResolved()) {
+        CHECK(ref->isInterface());
+        mResolved = static_cast<Interface*>(ref.get());
+    }
+}
+
+}  // namespace android
diff --git a/Reference.h b/Reference.h
new file mode 100644
index 0000000..e83004a
--- /dev/null
+++ b/Reference.h
@@ -0,0 +1,108 @@
+/*
+ * 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 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 @@ status_t Type::emitExportedHeader(
 
 ////////////////////////////////////////
 
-TemplatedType::TemplatedType() : mElementType(nullptr) {
-}
+TemplatedType::TemplatedType() {}
+
+void TemplatedType::setElementType(const Reference<Type>& elementType) {
+    // can only be set once.
+    CHECK(mElementType.isEmptyReference());
+    CHECK(!elementType.isEmptyReference());
 
-void TemplatedType::setElementType(Type *elementType) {
-    CHECK(mElementType == nullptr); // can only be set once.
     CHECK(isCompatibleElementType(elementType));
     mElementType = elementType;
 }
 
-Type *TemplatedType::getElementType() const {
+Type* TemplatedType::getElementType() const {
     return mElementType;
 }
 
@@ -512,5 +514,6 @@ status_t TemplatedType::emitVtsAttributeType(Formatter &out) const {
     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 @@ private:
 
 /* 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 @@ const ScalarType *TypeDef::resolveToScalarType() const {
     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 @@ struct TypeDef : public NamedType {
 
     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 @@ bool VectorType::isJavaCompatible() const {
     }
 
     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 d67638e..daee8d2 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 "RefType.h"
 #include "Scope.h"
+#include "TypeDef.h"
 #include "VectorType.h"
-#include "RefType.h"
 
 #include "hidl-gen_y.h"
 
@@ -257,13 +258,13 @@ bool isValidTypeName(const std::string& identifier, std::string *errorMsg) {
 %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 @@ bool isValidTypeName(const std::string& identifier, std::string *errorMsg) {
 
 %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 @@ fqname
 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 @@ fqtype
 
               YYERROR;
           }
+
+          $$->set(type);
       }
     | TYPE
+      {
+          $$ = new Reference<Type>($1, convertYYLoc(@1));
+      }
     ;
 
 package
@@ -543,17 +553,28 @@ imports
     ;
 
 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;
+          }
+          $$ = new Reference<Interface>(*$2);
+      }
 
 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 +598,7 @@ interface_declarations
                 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 +619,7 @@ type_declarations
 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 +644,18 @@ type_declaration_body
 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,16 +663,13 @@ interface_declaration
                             << "\n";
                   YYERROR;
               }
-              if (parent == nullptr) {
-                parent = ast->lookupType(gIBaseFqName, *scope);
-              }
-          }
-
-          if (parent != NULL && !parent->isInterface()) {
-              std::cerr << "ERROR: You can only extend interfaces. at " << @3
-                        << "\n";
 
-              YYERROR;
+              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 ($2[0] != 'I') {
@@ -660,8 +687,7 @@ interface_declaration
           }
 
           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 +723,18 @@ interface_declaration
 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 +765,13 @@ const_expr
                       *(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 +851,7 @@ typed_vars
       }
     ;
 
-typed_var : type valid_identifier { $$ = new TypedVar($2, $1); }
+typed_var : type valid_identifier { $$ = new TypedVar($2, *$1); }
     ;
 
 
@@ -869,7 +902,8 @@ field_declarations
       {
           $$ = $1;
 
-          if ($2 != NULL) {
+          // Compound declaration or error
+          if ($2 != nullptr) {
               $$->push_back($2);
           }
       }
@@ -887,27 +921,28 @@ field_declaration
                       << @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 +958,9 @@ enum_storage_type
       {
           $$ = $2;
 
-          if ($$ != NULL && !$$->isValidEnumStorageType()) {
+          if ($$ != NULL && !(*$$)->isValidEnumStorageType()) {
               std::cerr << "ERROR: Invalid enum storage type ("
-                        << $2->typeName()
+                        << (*$2)->typeName()
                         << ") specified. at "
                         << @2 << "\n";
 
@@ -942,7 +977,7 @@ opt_comma
 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 +1038,50 @@ array_type_base
     : 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 +1093,25 @@ array_type
 
 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);
       }
-    }
     ;
 
 %%