#ifndef __Parser_TPTP__
#define __Parser_TPTP__
#include <filesystem>
#include <unordered_set>
#include "Forwards.hpp"
#include "Lib/Array.hpp"
#include "Lib/Stack.hpp"
#include "Lib/Exception.hpp"
#include "Kernel/Theory.hpp"
#include "Kernel/Inference.hpp"
#include "Kernel/RobSubstitution.hpp"
namespace Parse {
using namespace Kernel;
class TPTP
{
public:
enum Tag {
T_EOF,
T_NAME,
T_VAR,
T_LPAR,
T_RPAR,
T_LBRA,
T_RBRA,
T_COMMA,
T_COLON,
T_NOT,
T_AND,
T_EQUAL,
T_STRING,
T_NEQ,
T_FORALL,
T_EXISTS,
T_PI,
T_SIGMA,
T_IMPLY,
T_XOR,
T_IFF,
T_REVERSE_IMP,
T_DOT,
T_REAL,
T_RAT,
T_INT,
T_OR,
T_ASS,
T_LAMBDA,
T_APP,
T_STAR,
T_UNION,
T_ARROW,
T_SUBTYPE,
T_NOT_OR,
T_NOT_AND,
T_SEQUENT,
T_TYPE_QUANT,
T_THF_QUANT_SOME,
T_CHOICE,
T_DEF_DESC,
T_POLY_CHOICE,
T_POLY_DEF_DESC,
T_TRUE,
T_FALSE,
T_TTYPE,
T_BOOL_TYPE,
T_DEFAULT_TYPE,
T_INTEGER_TYPE,
T_RATIONAL_TYPE,
T_REAL_TYPE,
T_TUPLE,
T_THEORY_FUNCTION,
T_THEORY_SORT,
T_FOT,
T_FOF,
T_TFF,
T_THF,
T_DOLLARS,
T_ITE,
T_LET
};
enum State {
UNIT_LIST,
CNF,
FOF,
VAMPIRE,
FORMULA,
END_FOF,
SIMPLE_FORMULA,
END_FORMULA,
FORMULA_INSIDE_TERM,
TERM_INFIX,
END_FORMULA_INSIDE_TERM,
END_TERM_AS_FORMULA,
VAR_LIST,
FUN_APP,
FORMULA_INFIX,
ARGS,
TERM,
END_TERM,
TAG,
INCLUDE,
END_EQ,
HOL_FORMULA,
END_HOL_FORMULA,
HOL_TERM,
END_APP,
TFF,
THF,
TYPE,
END_TFF,
END_TYPE,
SIMPLE_TYPE,
UNBIND_VARIABLES,
END_ITE,
END_TUPLE,
END_ARGS,
MID_EQ,
END_LET,
LET_TYPE,
END_LET_TYPES,
DEFINITION,
MID_DEFINITION,
END_DEFINITION,
SYMBOL_DEFINITION,
TUPLE_DEFINITION,
END_THEORY_FUNCTION
};
enum LastPushed {
FORM,
TM,
};
static const int HOL_CONSTANTS_LOWER_BOUND;
static const int LAMBDA;
static const int APP;
static const int PI;
static const int SIGMA;
struct Token {
Tag tag;
std::string content;
std::string toString() const;
};
class ParseErrorException
: public ParsingRelatedException
{
public:
ParseErrorException(std::string message, std::filesystem::path path, unsigned ln)
: _message(message), _path(path), _ln(ln) {}
ParseErrorException(std::string message, Token& tok, std::filesystem::path path, unsigned ln)
: ParseErrorException(message + " (text: " + tok.toString() + ')', path, ln) {}
void cry(std::ostream&) const override;
~ParseErrorException() override {}
protected:
std::string _message;
std::filesystem::path _path;
unsigned _ln = 0;
};
#define PARSE_ERROR_TOK(msg,tok) \
throw ParseErrorException(msg,tok,currentFile.path,currentFile.lineNumber)
#define PARSE_ERROR(msg) \
throw ParseErrorException(msg,currentFile.path,currentFile.lineNumber)
TPTP(std::istream &in, UnitList::FIFO unitBuffer = UnitList::FIFO());
~TPTP();
void parse();
static UnitList* parse(std::istream& str);
static Unit* parseFormulaFromString(const std::string& str);
UnitList* units() const { return _units.list(); }
UnitList::FIFO unitBuffer() const { return _units; }
bool containsConjecture() const { return _containsConjecture; }
static bool findAxiomName(const Unit* unit, std::string& result);
static void assignAxiomName(const Unit* unit, std::string& name);
unsigned lineNumber(){ return currentFile.lineNumber; }
std::string currentPath(){ return currentFile.path; }
static Map<unsigned,std::string>* findQuestionVars(unsigned questionNumber) {
return _questionVariableNames.findPtr(questionNumber);
}
static bool seenQuestions() {
return !_questionVariableNames.isEmpty();
}
private:
void parseImpl(State initialState = State::UNIT_LIST);
const char* input() { return _chars.content(); }
enum TypeTag {
TT_ATOMIC,
TT_PRODUCT,
TT_ARROW,
TT_QUANTIFIED
};
class Type {
public:
explicit Type(TypeTag tag) : _tag(tag) {}
TypeTag tag() const {return _tag;}
protected:
TypeTag _tag;
};
class AtomicType
: public Type
{
public:
explicit AtomicType(TermList sort)
: Type(TT_ATOMIC), _sort(sort)
{}
TermList sort() const {return _sort;}
private:
TermList _sort;
};
class ArrowType
: public Type
{
public:
ArrowType(Type* lhs,Type* rhs)
: Type(TT_ARROW), _lhs(lhs), _rhs(rhs)
{}
Type* argumentType() const {return _lhs;}
Type* returnType() const {return _rhs;}
private:
Type* _lhs;
Type* _rhs;
};
class ProductType
: public Type
{
public:
ProductType(Type* lhs,Type* rhs)
: Type(TT_PRODUCT), _lhs(lhs), _rhs(rhs)
{}
Type* lhs() const {return _lhs;}
Type* rhs() const {return _rhs;}
private:
Type* _lhs;
Type* _rhs;
};
class QuantifiedType
: public Type
{
public:
QuantifiedType(Type* t, VList* vars)
: Type(TT_QUANTIFIED), _type(t), _vars(vars)
{}
VList* vars() const {return _vars;}
Type* qtype() const {return _type;}
private:
Type* _type;
VList* _vars;
};
enum TheorySort {
TS_ARRAY,
};
static bool findTheorySort(const std::string name, TheorySort &ts) {
static const std::string theorySortNames[] = {
"$array"
};
static const unsigned theorySorts = sizeof(theorySortNames)/sizeof(std::string);
for (unsigned sort = 0; sort < theorySorts; sort++) {
if (theorySortNames[sort] == name) {
ts = static_cast<TheorySort>(sort);
return true;
}
}
return false;
}
static bool isTheorySort(const std::string name) {
static TheorySort dummy;
return findTheorySort(name, dummy);
}
static TheorySort getTheorySort(const Token tok) {
ASS_REP(tok.tag == T_THEORY_SORT, tok.content);
TheorySort ts;
if (!findTheorySort(tok.content, ts)) {
ASSERTION_VIOLATION_REP(tok.content);
}
return ts;
}
enum TheoryFunction {
TF_SELECT, TF_STORE
};
static bool findTheoryFunction(const std::string name, TheoryFunction &tf) {
static const std::string theoryFunctionNames[] = {
"$select", "$store"
};
static const unsigned theoryFunctions = sizeof(theoryFunctionNames)/sizeof(std::string);
for (unsigned fun = 0; fun < theoryFunctions; fun++) {
if (theoryFunctionNames[fun] == name) {
tf = static_cast<TheoryFunction>(fun);
return true;
}
}
return false;
}
static bool isTheoryFunction(const std::string name) {
static TheoryFunction dummy;
return findTheoryFunction(name, dummy);
}
static TheoryFunction getTheoryFunction(const Token tok) {
ASS_REP(tok.tag == T_THEORY_FUNCTION, tok.content);
TheoryFunction tf;
if (!findTheoryFunction(tok.content, tf)) {
ASSERTION_VIOLATION_REP(tok.content);
}
return tf;
}
TermList* nLastTermLists(unsigned n)
{ return n == 0 ? nullptr : &_termLists[_termLists.size() - n]; }
bool _containsConjecture;
struct FileState {
std::istream *in = nullptr;
std::unordered_set<std::string> allowedNames;
std::filesystem::path path;
unsigned lineNumber;
} currentFile;
std::vector<FileState> restoreFiles;
Array<char> _chars;
int _cend;
Array<Token> _tokens;
int _tend;
UnitList::FIFO _units;
Stack<State> _states;
UnitInputType _lastInputType;
bool _isQuestion = false;
bool _isThf;
bool _containsPolymorphism;
Stack<std::string> _strings;
Stack<int> _connectives;
Stack<bool> _bools;
Stack<int> _ints;
Stack<VList*> _varLists;
Stack<SList*> _sortLists;
Stack<VList*> _bindLists;
Stack<Tag> _tags;
Stack<Formula*> _formulas;
Stack<Literal*> _literals;
Stack<TermList> _termLists;
Map<std::string, unsigned> _vars;
Map<unsigned,std::string> _curQuestionVarNames;
Stack<Type*> _types;
Stack<TypeTag> _typeTags;
Stack<TheoryFunction> _theoryFunctions;
Map<unsigned,SList*> _variableSorts;
Color _currentColor;
RobSubstitution _substScratchpad;
typedef std::pair<std::string, unsigned> LetSymbolName;
struct LetSymbolReference {
unsigned symbol;
bool isPredicate;
TermStack iTypeArgs;
};
#define SYMBOL(ref) (ref.symbol)
#define IS_PREDICATE(ref) (ref.isPredicate)
typedef std::pair<LetSymbolName, LetSymbolReference> LetSymbol;
typedef Stack<LetSymbol> LetSymbols;
Stack<LetSymbols> _letSymbols;
Stack<LetSymbols> _letTypedSymbols;
LastPushed _lastPushed;
static Substitution getTypeSub(const LetSymbolReference& ref);
bool findLetSymbol(LetSymbolName symbolName, LetSymbolReference& symbolReference);
bool findLetSymbol(LetSymbolName symbolName, LetSymbols scope, LetSymbolReference& symbolReference);
typedef Stack<LetSymbolReference> LetDefinitions;
Stack<LetDefinitions> _letDefinitions;
bool _modelDefinition;
unsigned _insideEqualityArgument;
inline char getChar(int pos)
{
while (_cend <= pos) {
int c = currentFile.in->get();
_chars[_cend++] = c == -1 ? 0 : c;
}
return _chars[pos];
}
inline void shiftChars(int n)
{
ASS(n > 0);
ASS(n <= _cend);
for (int i = 0;i < _cend-n;i++) {
_chars[i] = _chars[n+i];
}
_cend -= n;
}
inline void resetChars()
{
_cend = 0;
}
inline Token& getTok(int pos)
{
while (_tend <= pos) {
Token& tok = _tokens[_tend++];
readToken(tok);
}
return _tokens[pos];
}
inline void shiftToks(int n)
{
ASS(n > 0);
ASS(n <= _tend);
for (int i = 0;i < _tend-n;i++) {
_tokens[i] = _tokens[n+i];
}
_tend -= n;
}
inline void resetToks()
{
_tend = 0;
}
bool readToken(Token& t);
void skipWhiteSpacesAndComments();
void readName(Token&);
void readReserved(Token&);
void readString(Token&);
void readAtom(Token&);
Tag readNumber(Token&);
int decimal(int pos);
int positiveDecimal(int pos);
static std::string toString(Tag);
static Formula* makeJunction(Connective c,Formula* lhs,Formula* rhs);
void unitList();
void fof(bool fo);
void tff();
void vampire();
void consumeToken(Tag);
std::string name();
void formula();
void funApp();
void simpleFormula();
void simpleType();
void args();
void varList();
void symbolDefinition();
void tupleDefinition();
void term();
void termInfix();
void endTerm();
void endArgs();
Literal* createEquality(bool polarity,TermList& lhs,TermList& rhs);
Formula* createPredicateApplication(std::string name,unsigned arity);
TermList createFunctionApplication(std::string name,unsigned arity);
TermList createTypeConApplication(std::string name,unsigned arity);
void insertImplicitLetTypeArguments(const LetSymbolReference& ref, unsigned& arity);
void endEquality();
void midEquality();
void formulaInfix();
void endFormula();
void formulaInsideTerm();
void endFormulaInsideTerm();
void endTermAsFormula();
void endType();
void tag();
void endFof();
void endTff();
std::filesystem::path resolveInclude(const std::filesystem::path included);
void include();
void type();
void endIte();
void letType();
void endLetTypes();
void definition();
void midDefinition();
void endDefinition();
void endLet();
void endTheoryFunction();
void endTuple();
void addTagState(Tag);
TermList readSort();
unsigned getConstructorArity();
void endApp();
void holFormula();
void endHolFormula();
void holTerm();
void foldl(TermStack*);
TermList readArrowSort();
void readTypeArgs(unsigned arity);
void bindVariable(unsigned var,TermList sort);
void unbindVariables();
void skipToRPAR();
void skipToRBRA();
unsigned addFunction(std::string name,int arity,bool& added,TermList& someArgument);
int addPredicate(std::string name,int arity,bool& added,TermList& someArgument);
unsigned addOverloadedFunction(std::string name,int arity,int symbolArity,bool& added,TermList& arg,
Theory::Interpretation integer,Theory::Interpretation rational,
Theory::Interpretation real);
unsigned addOverloadedPredicate(std::string name,int arity,int symbolArity,bool& added,TermList& arg,
Theory::Interpretation integer,Theory::Interpretation rational,
Theory::Interpretation real);
TermList sortOf(TermList term);
static bool higherPrecedence(int c1,int c2);
std::string convert(Tag t);
bool findInterpretedPredicate(std::string name, unsigned arity);
OperatorType* constructOperatorType(Type* t, VList* vars = 0, DHSet<unsigned>* ivars = nullptr);
public:
template<class Numeral>
static unsigned addNumeralConstant(const std::string& name)
{
if (auto n = Numeral::parse(name)) {
return env.signature->addNumeralConstant(*n);
} else {
throw UserErrorException("not a valid ", Numeral::getSort(), " literal: ", name);
}
}
static unsigned addUninterpretedConstant(const std::string& name, bool& added);
static Unit* processClaimFormula(Unit* unit, Formula* f, const std::string& nm);
struct SourceRecord{
virtual bool isFile() = 0;
};
struct FileSourceRecord : SourceRecord {
const std::string fileName;
const std::string nameInFile;
bool isFile() override{ return true; }
FileSourceRecord(std::string fN, std::string nF) : fileName(fN), nameInFile(nF) {}
};
struct InferenceSourceRecord : SourceRecord{
const std::string name;
Stack<std::string> premises;
bool isFile() override{ return false; }
InferenceSourceRecord(std::string n) : name(n) {}
};
void setUnitSourceMap(DHMap<Unit*,SourceRecord*>* m){
_unitSources = m;
}
SourceRecord* getSource();
void setFilterReserved(){ _filterReserved=true; }
private:
DHMap<Unit*,SourceRecord*>* _unitSources;
static DHMap<unsigned, std::string> _axiomNames;
static DHMap<unsigned, Map<unsigned,std::string>> _questionVariableNames;
DHMap<std::string, unsigned> _typeArities;
DHMap<std::string, unsigned> _typeConstructorArities;
bool _filterReserved;
bool _seenConjecture;
#if VDEBUG
void printStates(std::string extra);
void printInts(std::string extra);
const char* toString(State s);
#endif
#ifdef DEBUG_SHOW_STATE
void printStacks();
#endif
};
}
#endif