diff --git a/AST.cpp b/AST.cpp
index 7f24520..b2f16c6 100644
--- a/AST.cpp
+++ b/AST.cpp
@@ -89,6 +89,8 @@
     if (err != OK) return err;
     err = validate();
     if (err != OK) return err;
+    err = checkAcyclic();
+    if (err != OK) return err;
 
     // Make future packages not to call passes
     // for processed types and expressions
@@ -139,6 +141,12 @@
     return mRootScope.recursivePass(&Type::validate, &visited);
 }
 
+status_t AST::checkAcyclic() const {
+    std::unordered_set<const Type*> visited;
+    std::unordered_set<const Type*> stack;
+    return mRootScope.checkAcyclic(&visited, &stack).status;
+}
+
 bool AST::addImport(const char *import) {
     FQName fqName(import);
     CHECK(fqName.isValid());
diff --git a/AST.h b/AST.h
index 951cd24..2627e32 100644
--- a/AST.h
+++ b/AST.h
@@ -88,6 +88,10 @@
     // syntax restrictions
     status_t validate() const;
 
+    // Recursive tree pass that ensures that type definitions and references
+    // are acyclic.
+    status_t checkAcyclic() const;
+
     status_t generateCpp(const std::string &outputPath) const;
     status_t generateCppHeaders(const std::string &outputPath) const;
     status_t generateCppSources(const std::string &outputPath) const;
diff --git a/Interface.cpp b/Interface.cpp
index 10fb89d..8eb5907 100644
--- a/Interface.cpp
+++ b/Interface.cpp
@@ -484,6 +484,21 @@
     return ret;
 }
 
+std::vector<Reference<Type>> Interface::getStrongReferences() const {
+    // Interface is a special case as a reference:
+    // its definiton must be completed for extension but
+    // not necessary for other references.
+    // As interface declaration appears only in global scope and
+    // method declaration appears only in interface, we may assume
+    // that all references in method definitions are acyclic.
+
+    std::vector<Reference<Type>> ret;
+    if (superType() != nullptr) {
+        ret.push_back(mSuperType);
+    }
+    return ret;
+}
+
 status_t Interface::resolveInheritance() {
     size_t serial = FIRST_CALL_TRANSACTION;
     for (const auto* ancestor : superTypeChain()) {
diff --git a/Interface.h b/Interface.h
index 7b7eb33..ebb75cc 100644
--- a/Interface.h
+++ b/Interface.h
@@ -87,6 +87,7 @@
     std::string getVtsType() const override;
 
     std::vector<Reference<Type>> getReferences() const override;
+    std::vector<Reference<Type>> getStrongReferences() const override;
 
     std::vector<ConstantExpression*> getConstantExpressions() const override;
 
diff --git a/RefType.cpp b/RefType.cpp
index b43c832..aa35455 100644
--- a/RefType.cpp
+++ b/RefType.cpp
@@ -31,6 +31,10 @@
     return "ref" + (mElementType == nullptr ? "" : (" of " + mElementType->typeName()));
 }
 
+std::vector<Reference<Type>> RefType::getStrongReferences() const {
+    return {};
+}
+
 std::string RefType::getVtsType() const {
     return "TYPE_REF";
 }
diff --git a/RefType.h b/RefType.h
index c44b8ad..bf5e7e6 100644
--- a/RefType.h
+++ b/RefType.h
@@ -18,6 +18,9 @@
 
 #define REF_TYPE_H_
 
+#include <vector>
+
+#include "Reference.h"
 #include "Type.h"
 
 namespace android {
@@ -28,6 +31,8 @@
     std::string typeName() const override;
     bool isCompatibleElementType(Type *elementType) const override;
 
+    std::vector<Reference<Type>> getStrongReferences() const override;
+
     std::string getCppType(StorageMode mode,
                            bool specifyNamespaces) const override;
 
diff --git a/Type.cpp b/Type.cpp
index 218848e..53edf8b 100644
--- a/Type.cpp
+++ b/Type.cpp
@@ -17,6 +17,7 @@
 #include "Type.h"
 
 #include "ConstantExpression.h"
+#include "NamedType.h"
 #include "ScalarType.h"
 
 #include <hidl-util/Formatter.h>
@@ -104,6 +105,10 @@
     return {};
 }
 
+std::vector<Reference<Type>> Type::getStrongReferences() const {
+    return getReferences();
+}
+
 status_t Type::recursivePass(const std::function<status_t(Type*)>& func,
                              std::unordered_set<const Type*>* visited) {
     if (mIsPostParseCompleted) return OK;
@@ -159,6 +164,61 @@
     return OK;
 }
 
+Type::CheckAcyclicStatus::CheckAcyclicStatus(status_t status, const Type* cycleEnd)
+    : status(status), cycleEnd(cycleEnd) {
+    CHECK(cycleEnd == nullptr || status != OK);
+}
+
+Type::CheckAcyclicStatus Type::checkAcyclic(std::unordered_set<const Type*>* visited,
+                                            std::unordered_set<const Type*>* stack) const {
+    if (stack->find(this) != stack->end()) {
+        std::cerr << "ERROR: Cyclic declaration:\n";
+        return CheckAcyclicStatus(UNKNOWN_ERROR, this);
+    }
+
+    if (visited->find(this) != visited->end()) return CheckAcyclicStatus(OK);
+    visited->insert(this);
+    stack->insert(this);
+
+    for (const Type* nextType : getDefinedTypes()) {
+        auto err = nextType->checkAcyclic(visited, stack);
+
+        if (err.status != OK) {
+            if (err.cycleEnd == nullptr) return err;
+
+            std::cerr << "  '" << typeName() << "'";
+            if (nextType->isNamedType()) {
+                std::cerr << " at " << static_cast<const NamedType*>(nextType)->location();
+            }
+            std::cerr << "\n";
+
+            if (err.cycleEnd == nextType) {
+                return CheckAcyclicStatus(err.status);
+            }
+            return err;
+        }
+    }
+
+    for (const Reference<Type>& nextType : getStrongReferences()) {
+        auto err = nextType->checkAcyclic(visited, stack);
+
+        if (err.status != OK) {
+            if (err.cycleEnd == nullptr) return err;
+
+            std::cerr << "  '" << nextType->typeName() << "' at " << nextType.location() << "\n";
+
+            if (err.cycleEnd == nextType) {
+                return CheckAcyclicStatus(err.status);
+            }
+            return err;
+        }
+    }
+
+    CHECK(stack->find(this) != stack->end());
+    stack->erase(this);
+    return CheckAcyclicStatus(OK);
+}
+
 const ScalarType *Type::resolveToScalarType() const {
     return NULL;
 }
diff --git a/Type.h b/Type.h
index 2ef8201..ddea9bd 100644
--- a/Type.h
+++ b/Type.h
@@ -64,6 +64,10 @@
     // All constant expressions referenced in this type.
     virtual std::vector<ConstantExpression*> getConstantExpressions() const;
 
+    // All types referenced in this type that must have completed
+    // definiton before being referenced.
+    virtual std::vector<Reference<Type>> getStrongReferences() const;
+
     // Proceeds recursive pass
     // Makes sure to visit each node only once.
     status_t recursivePass(const std::function<status_t(Type*)>& func,
@@ -79,6 +83,25 @@
     // syntax restrictions
     virtual status_t validate() const;
 
+    // Recursive tree pass checkAcyclic return type.
+    // Stores cycle end for nice error messages.
+    struct CheckAcyclicStatus {
+        CheckAcyclicStatus(status_t status, const Type* cycleEnd = nullptr);
+
+        status_t status;
+
+        // If a cycle is found, stores the end of cycle.
+        // While going back in recursion, this is used to stop printing the cycle.
+        const Type* cycleEnd;
+    };
+
+    // Recursive tree pass that ensures that type definitions and references
+    // are acyclic.
+    // If some cases allow using of incomplete types, these cases are to be
+    // declared in Type::getStrongReferences.
+    CheckAcyclicStatus checkAcyclic(std::unordered_set<const Type*>* visited,
+                                    std::unordered_set<const Type*>* stack) const;
+
     virtual const ScalarType *resolveToScalarType() const;
 
     virtual std::string typeName() const = 0;
diff --git a/VectorType.cpp b/VectorType.cpp
index 50ceef0..d09c226 100644
--- a/VectorType.cpp
+++ b/VectorType.cpp
@@ -81,6 +81,10 @@
     return mElementType->canCheckEquality();
 }
 
+std::vector<Reference<Type>> VectorType::getStrongReferences() const {
+    return {};
+}
+
 std::string VectorType::getCppType(StorageMode mode,
                                    bool specifyNamespaces) const {
     const std::string base =
diff --git a/VectorType.h b/VectorType.h
index e868355..a6acd0a 100644
--- a/VectorType.h
+++ b/VectorType.h
@@ -18,6 +18,9 @@
 
 #define VECTOR_TYPE_H_
 
+#include <vector>
+
+#include "Reference.h"
 #include "Type.h"
 
 namespace android {
@@ -30,6 +33,8 @@
     std::string typeName() const override;
     bool isCompatibleElementType(Type *elementType) const override;
 
+    std::vector<Reference<Type>> getStrongReferences() const override;
+
     bool canCheckEquality() const override;
 
     std::string getCppType(