================
@@ -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 think you could simplify this by using two stacks, one for operators and one
for operands, instead of the unified stack with specialized Operation struct.
Then it becomes a stack machine, in essence.
you could take this one step farther and change the serialization format to
post-fix and then you only need one stack, the operands. since I designed the
format for parsing convenience (vs readability), I think updating it makes
sense.
https://github.com/llvm/llvm-project/pull/175980
_______________________________________________
cfe-commits mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
