Add acyclic check pass to hidl-gen
Adds recursive tree pass that checks that directed graph of
definitions and references is acyclic.
It prints nice error message, which shows the whole found cycle.
To be really tested, it requires lookups to be moved outside of parsing.
Test: hidl_test
Bug: 31827278
Change-Id: I9e96fa8206cfb84a56298991c526f71befae1478
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(