================
@@ -42,104 +43,164 @@ static char compactSigil(Formula::Kind K) {
llvm_unreachable("unhandled formula kind");
}
+// Avoids recursion to avoid stack overflows from very large formulas.
void serializeFormula(const Formula &F, llvm::raw_ostream &OS) {
- switch (Formula::numOperands(F.kind())) {
- case 0:
- switch (F.kind()) {
- case Formula::AtomRef:
- OS << F.getAtom();
+ std::stack<const Formula *> WorkList;
+ WorkList.push(&F);
+ while (!WorkList.empty()) {
+ const Formula *Current = WorkList.top();
+ WorkList.pop();
+ switch (Formula::numOperands(Current->kind())) {
+ case 0:
+ switch (Current->kind()) {
+ case Formula::AtomRef:
+ OS << Current->getAtom();
+ break;
+ case Formula::Literal:
+ OS << (Current->literal() ? 'T' : 'F');
+ break;
+ default:
+ llvm_unreachable("unhandled formula kind");
+ }
break;
- case Formula::Literal:
- OS << (F.literal() ? 'T' : 'F');
+ case 1:
+ OS << compactSigil(Current->kind());
+ WorkList.push(Current->operands()[0]);
+ break;
+ case 2:
+ OS << compactSigil(Current->kind());
+ WorkList.push(Current->operands()[1]);
+ WorkList.push(Current->operands()[0]);
break;
default:
- llvm_unreachable("unhandled formula kind");
+ llvm_unreachable("unhandled formula arity");
}
- break;
- case 1:
- OS << compactSigil(F.kind());
- serializeFormula(*F.operands()[0], OS);
- break;
- case 2:
- OS << compactSigil(F.kind());
- serializeFormula(*F.operands()[0], OS);
- serializeFormula(*F.operands()[1], OS);
- break;
- default:
- llvm_unreachable("unhandled formula arity");
}
}
-static llvm::Expected<const Formula *>
-parsePrefix(llvm::StringRef &Str, Arena &A,
- llvm::DenseMap<unsigned, Atom> &AtomMap) {
- if (Str.empty())
- return llvm::createStringError(llvm::inconvertibleErrorCode(),
- "unexpected end of input");
-
- char Prefix = Str[0];
- Str = Str.drop_front();
-
- switch (Prefix) {
- case 'T':
- return &A.makeLiteral(true);
- case 'F':
- return &A.makeLiteral(false);
- case 'V': {
- unsigned AtomID;
- if (Str.consumeInteger(10, AtomID))
- return llvm::createStringError(llvm::inconvertibleErrorCode(),
- "expected atom id");
- auto [It, Inserted] = AtomMap.try_emplace(AtomID, Atom());
- if (Inserted)
- It->second = A.makeAtom();
- return &A.makeAtomRef(It->second);
- }
- case '!': {
- auto OperandOrErr = parsePrefix(Str, A, AtomMap);
- if (!OperandOrErr)
- return OperandOrErr.takeError();
- return &A.makeNot(**OperandOrErr);
- }
- case '&':
- case '|':
- case '>':
- case '=': {
- auto LeftOrErr = parsePrefix(Str, A, AtomMap);
- if (!LeftOrErr)
- return LeftOrErr.takeError();
+struct Operation {
+ Operation(Formula::Kind Kind) : Kind(Kind) {}
+ const Formula::Kind Kind;
+ const unsigned ExpectedNumOperands = Formula::numOperands(Kind);
+ std::vector<const Formula *> Operands;
+};
- auto RightOrErr = parsePrefix(Str, A, AtomMap);
- if (!RightOrErr)
- return RightOrErr.takeError();
+// Avoids recursion to avoid stack overflows from very large formulas.
+static llvm::Expected<const Formula *>
+parseFormulaInternal(llvm::StringRef &Str, Arena &A,
+ llvm::DenseMap<unsigned, Atom> &AtomMap) {
+ std::stack<Operation> ActiveOperations;
----------------
bazuzi wrote:
I actually find one stack simpler to read and reason about than two,
particularly for malformed cases where there are the wrong number of operands.
I think the two-stack approach wouldn't recognize the malformation as quickly.
And may not at all if there were multiple operators with the wrong numbers of
operands?
I'd rather not change the serialization format at the same time as
restructuring so much of the parsing and serialization code.
https://github.com/llvm/llvm-project/pull/175980
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
