ExpressionParserTypes.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreTypes.h"
#include "ExpressionParserTypesFwd.h" // IWYU pragma: export
#include "Templates/UnrealTemplate.h"
#include "Containers/Array.h"
#include "Containers/UnrealString.h"
#include "Templates/Function.h"
#include "Containers/Set.h"
#include "Containers/Map.h"
#include "Misc/Optional.h"
#include "Internationalization/Text.h"
#include "Internationalization/Internationalization.h"
#include "Misc/Guid.h"
#include "Templates/ValueOrError.h"
#include <type_traits>
 
namespace Impl
{
    struct IExpressionNodeStorage;
}
 
struct FExpressionError
{
    FExpressionError(const FText& InText)
        : Text(InText)
    {
    }
 
    FText Text;
};
 
template <typename CharType>
class TStringToken
{
public:
    TStringToken() = default;
 
    TString<CharType> GetString() const
    {
        return TString<CharType>::ConstructFromPtrSize(TokenStart, (int32)(TokenEnd - TokenStart));
    }
 
    bool IsValid() const
    {
        return TokenEnd != TokenStart;
    }
 
    const CharType* GetTokenStartPos() const
    {
        return TokenStart;
    }
 
    const CharType* GetTokenEndPos() const
    {
        return TokenEnd;
    }
 
    int32 GetCharacterIndex() const
    {
        return CharacterIndex;
    }
 
    int32 GetLineNumber() const
    {
        return LineNumber;
    }
    
    void Accumulate(const TStringToken& InToken)
    {
        if (InToken.TokenEnd > TokenEnd)
        {
            TokenEnd = InToken.TokenEnd;
        }
    }
 
protected:
    friend class TTokenStream<CharType>;
 
    explicit TStringToken(const CharType* InStart, int32 Line = 0, int32 Character = 0)
        : TokenStart(InStart)
        , TokenEnd(InStart)
        , LineNumber(Line)
        , CharacterIndex(Character)
    {
    }
 
    const CharType* TokenStart = nullptr;
    const CharType* TokenEnd = nullptr;
    int32 LineNumber = 0;
    int32 CharacterIndex = 0;
};
 
enum class EParseState
{
    Continue,
    StopAfter,
    StopBefore, 
    Cancel,
};
 
template <typename CharType>
class TTokenStream
{
public:
    CORE_API TOptional<TStringToken<CharType>> ParseToken(TFunctionRef<EParseState(CharType)> Pred, TStringToken<CharType>* Accumulate = nullptr) const;
 
    CORE_API TOptional<TStringToken<CharType>> ParseToken(const CharType* Symbol, TStringToken<CharType>* Accumulate = nullptr) const;
    CORE_API TOptional<TStringToken<CharType>> ParseTokenIgnoreCase(const CharType* Symbol, TStringToken<CharType>* Accumulate = nullptr) const;
 
    CORE_API TOptional<TStringToken<CharType>> ParseSymbol(TStringToken<CharType>* Accumulate = nullptr) const;
 
    CORE_API TOptional<TStringToken<CharType>> ParseSymbol(CharType Symbol, TStringToken<CharType>* Accumulate = nullptr) const;
 
    CORE_API TOptional<TStringToken<CharType>> ParseWhitespace(TStringToken<CharType>* Accumulate = nullptr) const;
 
    CORE_API TOptional<TStringToken<CharType>> GenerateToken(int32 NumChars, TStringToken<CharType>* Accumulate = nullptr) const;
 
public:
    CORE_API explicit TTokenStream(const CharType* In);
    
    CORE_API CharType PeekChar(int32 Offset = 0) const;
 
    CORE_API int32 CharsRemaining() const;
 
    CORE_API bool IsReadPosValid(const CharType* InPos, int32 MinNumChars = 1) const;
 
    CORE_API bool IsEmpty() const;
 
    CORE_API int32 GetPosition() const;
 
    const CharType* GetStart() const
    {
        return Start;
    }
    const CharType* GetRead() const
    {
        return ReadPos;
    }
    const CharType* GetEnd() const
    {
        return End;
    }
 
    CORE_API FString GetErrorContext() const;
 
    CORE_API void SetReadPos(const TStringToken<CharType>& Token);
 
private:
    const CharType* Start;
    const CharType* End;
    const CharType* ReadPos;
};
 
#define DEFINE_EXPRESSION_NODE_TYPE(TYPE, ...) \
template<> struct TGetExpressionNodeTypeId<TYPE>\
{\
    static const FGuid& GetTypeId()\
    {\
        static FGuid Global(__VA_ARGS__);\
        return Global;\
    }\
};
template<typename T> struct TGetExpressionNodeTypeId;
 
DEFINE_EXPRESSION_NODE_TYPE(bool,   0xCACBC715, 0x505A6B4A, 0x8808809F, 0x897AA5F6)
DEFINE_EXPRESSION_NODE_TYPE(double, 0x8444A8A3, 0x19AE4E13, 0xBCFA75EE, 0x39982BD6)
 
class FExpressionNode
{
public:
    FExpressionNode() = default;
 
    template <
        typename T
        UE_REQUIRES(!std::is_convertible_v<T*, FExpressionNode*>)
    >
    FExpressionNode(T In);
 
    CORE_API ~FExpressionNode();
 
    // Movable, but non copyable
    CORE_API FExpressionNode(FExpressionNode&& In);
    FExpressionNode(const FExpressionNode&) = delete;
    CORE_API FExpressionNode& operator=(FExpressionNode&& In);
    FExpressionNode& operator=(const FExpressionNode&) = delete;
 
    CORE_API const FGuid& GetTypeId() const;
 
    template<typename T>
    const T* Cast() const;
 
    CORE_API FExpressionNode Copy() const;
 
private:
    static constexpr uint32 MaxStackAllocationSize = 64 - sizeof(FGuid);
 
    CORE_API Impl::IExpressionNodeStorage* GetData();
    CORE_API const Impl::IExpressionNodeStorage* GetData() const;
 
    FGuid TypeId;
    alignas(__STDCPP_DEFAULT_NEW_ALIGNMENT__) uint8 InlineBytes[MaxStackAllocationSize];
};
 
template <typename CharType>
class TExpressionToken
{
public:
    explicit TExpressionToken(const TStringToken<CharType>& InContext, FExpressionNode InNode)
        : Node(MoveTemp(InNode))
        , Context(InContext)
    {
    }
 
    FExpressionNode Node;
    TStringToken<CharType> Context;
};
 
template <typename CharType>
struct TCompiledToken : TExpressionToken<CharType>
{
    // Todo: add callable types here?
    enum EType { Operand, PreUnaryOperator, PostUnaryOperator, BinaryOperator, ShortCircuit, Benign };
 
    explicit TCompiledToken(EType InType, TExpressionToken<CharType> InToken, TOptional<int32> InShortCircuitIndex = TOptional<int32>())
        : TExpressionToken<CharType>(MoveTemp(InToken))
        , Type(InType)
        , ShortCircuitIndex(InShortCircuitIndex)
    {
    }
 
    EType Type;
    TOptional<int32> ShortCircuitIndex;
};
 
struct FOperatorFunctionID
{
    FGuid OperatorType;
    FGuid LeftOperandType;
    FGuid RightOperandType;
 
    friend bool operator==(const FOperatorFunctionID& A, const FOperatorFunctionID& B)
    {
        return A.OperatorType == B.OperatorType &&
            A.LeftOperandType == B.LeftOperandType &&
            A.RightOperandType == B.RightOperandType;
    }
 
    friend uint32 GetTypeHash(const FOperatorFunctionID& In)
    {
        const uint32 Hash = HashCombine(GetTypeHash(In.OperatorType), GetTypeHash(In.LeftOperandType));
        return HashCombine(GetTypeHash(In.RightOperandType), Hash);
    }
};
 
template <typename ContextType, typename CharType>
struct TOperatorJumpTable
{
    FExpressionResult ExecPreUnary(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& R, const ContextType* Context) const;
    FExpressionResult ExecPostUnary(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& L, const ContextType* Context) const;
    FExpressionResult ExecBinary(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& L, const TExpressionToken<CharType>& R, const ContextType* Context) const;
    bool ShouldShortCircuit(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& L, const ContextType* Context) const;
 
    template<typename OperatorType, typename FuncType>
    void MapPreUnary(FuncType InFunc);
 
    template<typename OperatorType, typename FuncType>
    void MapPostUnary(FuncType InFunc);
 
    template<typename OperatorType, typename FuncType>
    void MapBinary(FuncType InFunc);
 
    template<typename OperatorType, typename FuncType>
    void MapShortCircuit(FuncType InFunc);
 
public:
    using FUnaryFunction = TFunction<FExpressionResult(const FExpressionNode&, const ContextType* Context)>;
    using FBinaryFunction = TFunction<FExpressionResult(const FExpressionNode&, const FExpressionNode&, const ContextType* Context)>;
    using FShortCircuit = TFunction<bool(const FExpressionNode&, const ContextType* Context)>;
 
private:
    TMap<FOperatorFunctionID, FUnaryFunction>  PreUnaryOps;
    TMap<FOperatorFunctionID, FUnaryFunction>  PostUnaryOps;
    TMap<FOperatorFunctionID, FBinaryFunction> BinaryOps;
    TMap<FOperatorFunctionID, FShortCircuit>   BinaryShortCircuits;
};
 
template <typename CharType>
struct TIOperatorEvaluationEnvironment
{
    virtual FExpressionResult ExecPreUnary(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& R) const = 0;
    virtual FExpressionResult ExecPostUnary(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& L) const = 0;
    virtual FExpressionResult ExecBinary(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& L, const TExpressionToken<CharType>& R) const = 0;
    virtual bool ShouldShortCircuit(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& L) const = 0;
};
template <typename ContextType, typename CharType>
struct TOperatorEvaluationEnvironment : TIOperatorEvaluationEnvironment<CharType>
{
    explicit TOperatorEvaluationEnvironment(const TOperatorJumpTable<ContextType, CharType>& InOperators, const ContextType* InContext)
        : Operators(InOperators)
        , Context(InContext)
    {
    }
 
    virtual FExpressionResult ExecPreUnary(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& R) const override
    {
        return Operators.ExecPreUnary(Operator, R, Context);
    }
    virtual FExpressionResult ExecPostUnary(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& L) const override
    {
        return Operators.ExecPostUnary(Operator, L, Context);
    }
    virtual FExpressionResult ExecBinary(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& L, const TExpressionToken<CharType>& R) const override
    {
        return Operators.ExecBinary(Operator, L, R, Context);
    }
    virtual bool ShouldShortCircuit(const TExpressionToken<CharType>& Operator, const TExpressionToken<CharType>& L) const override
    {
        return Operators.ShouldShortCircuit(Operator, L, Context);
    }
 
private:
    const TOperatorJumpTable<ContextType>& Operators;
    const ContextType* Context;
};
 
template <typename CharType>
class TExpressionTokenConsumer
{
public:
    CORE_API explicit TExpressionTokenConsumer(const CharType* InExpression);
 
    // Non-copyable
    TExpressionTokenConsumer(TExpressionTokenConsumer&&) = delete;
    TExpressionTokenConsumer(const TExpressionTokenConsumer&) = delete;
    TExpressionTokenConsumer& operator=(TExpressionTokenConsumer&&) = delete;
    TExpressionTokenConsumer& operator=(const TExpressionTokenConsumer&) = delete;
    ~TExpressionTokenConsumer() = default;
 
    CORE_API TArray<TExpressionToken<CharType>> Extract();
 
    CORE_API void Add(const TStringToken<CharType>& SourceToken, FExpressionNode&& Node);
 
    CORE_API TTokenStream<CharType>& GetStream();
 
private:
    TArray<TExpressionToken<CharType>> Tokens;
 
    TTokenStream<CharType> Stream;
};
 
template <typename CharType>
using TExpressionDefinition = TOptional<FExpressionError>(TExpressionTokenConsumer<CharType>&);
 
 
template <typename CharType>
class TTokenDefinitions
{
public:
    TTokenDefinitions() = default;
 
    CORE_API void IgnoreWhitespace();
 
    CORE_API void DefineToken(TFunction<TExpressionDefinition<CharType>>&& Definition);
 
    CORE_API bool DoesIgnoreWhitespace();
 
    CORE_API TOptional<FExpressionError> ConsumeTokens(TExpressionTokenConsumer<CharType>& Consumer) const;
 
private:
    CORE_API TOptional<FExpressionError> ConsumeToken(TExpressionTokenConsumer<CharType>& Consumer) const;
 
private:
    bool bIgnoreWhitespace = false;
    TArray<TFunction<TExpressionDefinition<CharType>>> Definitions;
};
 
 
enum class EAssociativity : uint8
{
    RightToLeft,
    LeftToRight
};
 
struct FOpParameters
{
    int32           Precedence;
 
    EAssociativity  Associativity;
 
    bool bCanShortCircuit;
 
    FOpParameters(int32 InPrecedence, EAssociativity InAssociativity, bool bInCanShortCircuit)
        : Precedence(InPrecedence)
        , Associativity(InAssociativity)
        , bCanShortCircuit(bInCanShortCircuit)
    {
    }
};
 
class FExpressionGrammar
{
public:
    template<typename StartGroupType, typename EndGroupType>
    void DefineGrouping()
    {
        Groupings.Add(TGetExpressionNodeTypeId<StartGroupType>::GetTypeId(), TGetExpressionNodeTypeId<EndGroupType>::GetTypeId());
    }
 
    template<typename ExpressionNodeType>
    void DefinePreUnaryOperator()
    {
        PreUnaryOperators.Add(TGetExpressionNodeTypeId<ExpressionNodeType>::GetTypeId());
    }
 
    template<typename ExpressionNodeType>
    void DefinePostUnaryOperator()
    {
        PostUnaryOperators.Add(TGetExpressionNodeTypeId<ExpressionNodeType>::GetTypeId());
    }
 
    template<typename ExpressionNodeType>
    void DefineBinaryOperator(int32 InPrecedence, EAssociativity InAssociativity=EAssociativity::RightToLeft, bool bCanShortCircuit = false)
    {
#if DO_CHECK
        for (TMap<FGuid, FOpParameters>::TConstIterator It(BinaryOperators); It; ++It)
        {
            const FOpParameters& CurValue = It.Value();
 
            if (CurValue.Precedence == InPrecedence)
            {
                // Operators of the same precedence, must all have the same associativity
                check(CurValue.Associativity == InAssociativity);
            }
        }
#endif
 
        BinaryOperators.Add(TGetExpressionNodeTypeId<ExpressionNodeType>::GetTypeId(), FOpParameters(InPrecedence, InAssociativity, bCanShortCircuit));
    }
 
public:
 
    CORE_API const FGuid* GetGrouping(const FGuid& TypeId) const;
 
    CORE_API bool HasPreUnaryOperator(const FGuid& TypeId) const;
 
    CORE_API bool HasPostUnaryOperator(const FGuid& TypeId) const;
 
    CORE_API const FOpParameters* GetBinaryOperatorDefParameters(const FGuid& TypeId) const;
 
private:
 
    TMap<FGuid, FGuid>          Groupings;
    TSet<FGuid>                 PreUnaryOperators;
    TSet<FGuid>                 PostUnaryOperators;
    TMap<FGuid, FOpParameters>  BinaryOperators;
};
 
extern template class TTokenStream<ANSICHAR>;
extern template class TTokenStream<UTF8CHAR>;
extern template class TTokenStream<WIDECHAR>;
 
extern template class TExpressionTokenConsumer<ANSICHAR>;
extern template class TExpressionTokenConsumer<UTF8CHAR>;
extern template class TExpressionTokenConsumer<WIDECHAR>;
 
extern template class TTokenDefinitions<ANSICHAR>;
extern template class TTokenDefinitions<WIDECHAR>;
extern template class TTokenDefinitions<UTF8CHAR>;
 
#if UE_ENABLE_INCLUDE_ORDER_DEPRECATED_IN_5_6
#include "Templates/PointerIsConvertibleFromTo.h"
#endif
 
#include "Misc/ExpressionParserTypes.inl" // IWYU pragma: export