================
@@ -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;
----------------
ymand wrote:
> I'd rather not change the serialization format at the same time as
> restructuring so much of the parsing and serialization code.
good point
> 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'm don't see a difference for malformedness - the two approaches should be
isomorphic, just a matter of how the data is structured. But, regardless, I
think the real win comes from post-fix, so sticking with what you have works
for me.
https://github.com/llvm/llvm-project/pull/175980
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
