2
\$\begingroup\$

Preamble

I was inspired by this review request to create my own quasi JVM Byte Code Struct, Parser and to top it a bit I also wrote two a quasi executors. Currently, they just print the instructions but the executors are flexible and in the future can take a JavaVirtualMachine class instead of std::cout and act on it instead.

Requirements

The key requirements of this request still hold. But I have a few more:

  1. NO MACROS:
  2. The core data structures must be able to do on the fly parsing/execution/serialization as well as parse the entire codefirst and then execute it.

Key Questions

  1. How to make the code more readable
  2. Any C++ safety mistakes I have committed.
  3. Any way I can provide better compile time errors.

Layout

Namespaces are omitted to make the code simpler to review. In production, I will add them but the filesystem layout would be the same.

The code consists of bunch of headers:

  1. utils.h : Generic code like printing a std::tuple, etc.
  2. insructions.h : This is where you define instructions. All Insructions are standalone classes but expect the interface (shown below) so they can interop with the rest of the code. It also collects all the instructions in a variant and defines different helper functions.
struct InstructionInterface {
    using Operands = std::tuple<T...>;
    Operands operands;
    static constexpr std::string_view mnemonic = "MNEMONIC_STRING";
}
  1. serializeToByteCode.h, byteCodeInstructionParser.h, serializeToHumandReadable.h, : Are implementations for different serializers/parsers
  2. execute.h, countingExecutor.h: Are executors. execute.h is the vanilla executor, whereas countingExecutor.h provides an example for creating complicated executors by wrapping execute. Another one I want to write but haven't is a ProfilingExecutor, but I reckon would be similar to CountingExecutor.
  3. main.c : Test code.

For the sake of brevity and ease of review, I have included all the files in the same snippet below. The files are demarcated by \*------<fileName.ext>----------*\

Code

I have added the entire code here for posterity. You can either copy the snippe into your favorite editor and build it with c++17 or just open the godbolt.org link.

// C++17 no dependencies
// compiles on gnu systems using
// g++ <filename>.cpp -std=c++17

#include <array>
#include <cstdint>
#include <cstddef>
#include <iostream>
#include <sstream>
#include <tuple>
#include <variant>
#include <vector>

/**---------------------------------util.h--------------------------------------**/

template<typename T>
struct VariantIndexVisitor{};

template<typename... ValueT>
struct VariantIndexVisitor<std::variant<ValueT...>>{

    template<typename Callable, typename... Arg>
    constexpr auto operator()(
        size_t const opCode, Callable c, Arg&&... arg
    ) const {    

        constexpr std::array functionMap = {
            (
                +[](Callable callable, Arg&&... arg)
                    -> decltype(callable.template operator()<ValueT>(
                        std::forward<Arg>(arg)...)
                    ){
                   return callable.template operator()<ValueT>(std::forward<Arg>(arg)...);
                }
            )...
        };

        if(std::variant_size_v<std::variant<ValueT...>> <= opCode)
            throw std::runtime_error("");
        
        return functionMap[opCode](c, std::forward<Arg>(arg)...);
    }
};

template <typename T, size_t N>
class UniformTuple {
private:
    template <typename = std::make_index_sequence<N>>
    struct Impl;

    template <size_t... Is>
    struct Impl<std::index_sequence<Is...>> {
        template <size_t >
        using Wrap = T;

        using Type = std::tuple<Wrap<Is>...>;
    };

public:
    using Type = typename Impl<>::Type;
};

template <typename T, size_t N>
using UniformTupleT = typename UniformTuple<T, N>::Type;

template <typename... T, size_t... Is>
void print(std::ostream & os, std::tuple<T...> const & tuple, std::index_sequence<Is...>){
    std::cout << "(";
    // Delibrataly casting to int. os << U8 just prints the ascii code. Not the human readable value
    ((std::cout << int(std::get<Is>(tuple)) << ','), ...);
    std::cout << ")";
}

template <typename... T>
void print(std::ostream & os, std::tuple<T...> const & tuple){
    print(os, tuple, std::make_index_sequence<sizeof...(T)>{});
}

/**------------------------------instructions.h-----------------------------------------**/

using OpCode = std::uint8_t;

//TODO: Wrap for easy ostream shift operators if assumption that types have integral human readable
// representation is wrong
using U8 = std::uint8_t;
using U16 = std::uint16_t;
using U32 = std::uint32_t;
using S8 = std::int8_t;
using S16 = std::int16_t;
using S32 = std::int32_t;

struct UnassignedTag {};

template<size_t I>
struct Unassigned : UnassignedTag{
    using Operands = std::tuple<>;
    Operands operands;
    static constexpr std::string_view mnemonic = "UNASSIGNED";
};

struct Nop {
    using Operands = std::tuple<>;
    Operands operands;
    static constexpr std::string_view mnemonic = "NOP";
};

struct Ret {
    using Operands = std::tuple<U16>;
    Operands operands;
    static constexpr std::string_view mnemonic = "RET";
};

struct BiPush {
    using Operands = std::tuple<U8, U16>;
    Operands operands;
    static constexpr std::string_view mnemonic = "BIPUSH";
};

struct TablePush {
    using Operands = std::tuple<U16, U16>;
    Operands operands;
    static constexpr std::string_view mnemonic = "TABLESWITCH";
};

//TODO: Add other JVM instructions below

// Assumption: The index in the variant is same as the binary representation of the
// opCode. This may not be true.
// TODO: Incase the assumption fails and we miss a few op codes use the Unassigned<i>.
// template to generate a unique Unassigned opcode. Since we are using variants, a non
// unique reserve will fail to compile
using Instruction = std::variant<
    Nop,
    Ret,
    BiPush,
    TablePush,
    Unassigned<1> // Example: Add Unassigned keyword
    // TODO: Populate this when new instructions are added.
>;

using OpCodeFactory = VariantIndexVisitor<Instruction>;

template<typename InstructionT>
constexpr OpCode loopUpOpCode(){
    return Instruction(InstructionT()).index();
}

template<typename InstructionT>
constexpr bool isUnassigned = std::is_base_of_v<UnassignedTag, InstructionT>;

/**-------------------------serializeToByteCode.h--------------------------------------**/

template<typename InstructionT, typename... OperandT>
void serializeOperandsToByteCode(std::ostream & os, std::tuple<OperandT...> const & operand){

    auto writeOperand = [offset = size_t{0}, &operand](std::ostream& os,size_t operandSize) mutable {
        os.write(reinterpret_cast<char const * const>(&operand) + offset, operandSize);
        offset += operandSize;
    };
    
    (writeOperand(os, sizeof(OperandT)),...);
}

template<typename InstructionT>
void serializeInstructionToByteCode(InstructionT const & instruction, std::ostream & os){
    
    os << loopUpOpCode<InstructionT>();
    serializeOperandsToByteCode<InstructionT>(os, instruction.operands);
}

/**-----------------------------byteCodeInstructionParser.h----------------------------**/

struct ByteCodeInstructionParser {

    template<typename InstructionT>
    Instruction operator()(std::istream & is){

        if constexpr (isUnassigned<InstructionT>){
            throw std::runtime_error("Unassigned Instruction encountered");
        } else {

            typename InstructionT::Operands operands;       // Operands are uninitialized.
            populateOperands<InstructionT>(is, operands);   // They are populated based on the instruction here

            return InstructionT{operands};
        }
    }

private:

    template<typename InstructionT, typename... OperandT>
    void populateOperands(std::istream & is, std::tuple<OperandT...> & operand){

        auto readOperand = [offset = size_t{0}, &operand](std::istream& is,size_t operandSize) mutable {
            is.read(reinterpret_cast<char*>(&operand) + offset, operandSize);
            offset += operandSize;
        };
        
        (readOperand(is, sizeof(OperandT)),...);
    }

};

Instruction parseByteCodeToInstruction(std::istream & is){
    
    OpCode opCode;
    is.read(reinterpret_cast<char*>(&opCode), sizeof opCode);
    
    constexpr auto makeInstruction = OpCodeFactory();

    return makeInstruction(opCode, ByteCodeInstructionParser{}, is);
}

/**----------------------------serializeToHumandReadable.h----------------------------**/

template<typename InstructionT, typename OperandT, size_t... Is>
void serializeOperandsToHumanReadableCode(std::ostream & os, OperandT const & operand, std::index_sequence<Is...>){
    // Delibrataly casting to int. os << U8 just prints the ascii code. Not the human readable value
    ((os << " " << static_cast<int>(std::get<Is>(operand)),...));
}

template<typename InstructionT>
void serializeInstructionToHumanReadableCode(std::ostream & os, InstructionT const & instruction){
    
    os << InstructionT::mnemonic;

    serializeOperandsToHumanReadableCode<InstructionT>(
        os,
        instruction.operands,
        std::make_index_sequence<std::tuple_size<typename InstructionT::Operands>{}>{}
    );
}

void parseByteCodeAndSerializeToHumanReadableCode(std::istream & is, std::ostream & os){

    while(is.peek() != EOF){

        auto instruction = parseByteCodeToInstruction(is);
        std::visit([&](auto instruction){ serializeInstructionToHumanReadableCode(os, instruction);}, instruction);
        os << '\n';
    }
}

std::vector<Instruction> parseByteCode(std::istream & is){

    auto instructions = std::vector<Instruction>{};
    while(is.peek() != EOF){
        instructions.emplace_back(parseByteCodeToInstruction(is));
    }

    return instructions;
} 


/**----------------------------------------------- execute.cpp -------------------------------- **/

void execute(Nop const & nop, std::ostream & os){
    os << "Executing NOP " << std::endl;
}

void execute(Ret const & ret, std::ostream & os){
    auto & [index] = ret.operands;
    os << "Executing RET " << index << " " << std::endl;
}

void execute(BiPush const & biPush, std::ostream & os){
    auto & [bytes, offset] = biPush.operands;
    os << "Executing BIPUSH " << size_t{bytes} << " " << offset << std::endl;
}

void execute(TablePush const & t, std::ostream & os) {

    os << "Executing TABLESWITCH " << std::get<0>(t.operands) << " " << std::get<1>(t.operands) << std::endl;
}

template<size_t I>
void execute(Unassigned<I> const &, std::ostream & os){
    os << "Skipping Unassigned" << std::endl;
};

/**-------------------------------------------- countingExecutor.cpp ----------------------------------- **/

class CountingExecutor {
public:

    using Counters = UniformTupleT<size_t, std::variant_size_v<Instruction>>;

    template<typename Instruction, typename... Args>
    void operator()(Instruction const & instruction, Args&&... args){

        execute(instruction, std::forward<Args>(args)...);

        auto & counter = std::get<loopUpOpCode<Instruction>()>(mCounters);
        ++counter;
    }

    [[nodiscard]] auto const & counters() const noexcept {
        return mCounters;
    }

    void reset(){
        mCounters = Counters{};
    }

private:

    Counters mCounters = {};
};

/**------------------------------------------------main.cpp-------------------------------------------**/

auto makeProgram(){

    std::stringstream ss;

    serializeInstructionToByteCode(Nop{}, ss);
    serializeInstructionToByteCode(Nop{}, ss);
    serializeInstructionToByteCode(Nop{}, ss);
    serializeInstructionToByteCode(Ret{{69}}, ss);
    serializeInstructionToByteCode(BiPush{{42, 420}}, ss);
    serializeInstructionToByteCode(TablePush{{69, 42420}}, ss);

    return ss;
}

void exampleHumanReadable(){

    std::cout << "------ Human Readable  --------" << std::endl;
    auto byteCode = makeProgram();
    std::cout << "Parsing And Serializing Program" << std::endl;
    parseByteCodeAndSerializeToHumanReadableCode(byteCode, std::cout);
}

void exampleExecute(){

    std::cout << "------ Execute  --------" << std::endl;

    auto byteCode = makeProgram();

    std::cout << "Parsing Entire Program" << std::endl;
    auto const instructions = parseByteCode(byteCode);
    for(auto const & instruction : instructions){
        std::visit(
            [](auto const & instruction) { execute(instruction, std::cout); },
            instruction
        );
    }
}

void exampleExecuteOnTheFly(){

    std::cout << "------ Execute On The Fly  --------" << std::endl;

    auto byteCode = makeProgram();

    while(byteCode.peek() != EOF){

        std::cout << "Parsing Next Instruction" << std::endl;
        auto const instruction = parseByteCodeToInstruction(byteCode);
        std::visit(
            [](auto const & instruction) { execute(instruction, std::cout); },
            instruction
        );
    }
}

void exampleCountingExecutor(){

    std::cout << "------ Counting Executor --------" << std::endl;

    auto byteCode = makeProgram();
    auto countingExecutor = CountingExecutor{};
    std::cout << "Parsing Entire Program" << std::endl;
    auto const instructions = parseByteCode(byteCode);
    for(auto const & instruction : instructions){
        std::visit(
            [&](auto const & instruction) { countingExecutor(instruction, std::cout); },
            instruction
        );
    }

    std::cout << "Instruction Count: ";
    print(std::cout, countingExecutor.counters());
    std::cout << std::endl;
}

void throwOnUnassigned(){
    
    std::cout << "------ Throw on Unassigned --------" << std::endl;

    std::stringstream byteCode;
    serializeInstructionToByteCode(Unassigned<1>{}, byteCode);
    
    try {
        std::cout << "Parsing Instruction" << std::endl;
        auto const _ = parseByteCodeToInstruction(byteCode);
        std::cout << "Instruction Parsed" << std::endl;
    } catch (std::runtime_error const & e) {
        std::cout << "Caught: " << e.what() << std::endl;
    }
}

int main(int argc, char ** argv) {

    exampleHumanReadable();
    exampleExecute();
    exampleExecuteOnTheFly();
    exampleCountingExecutor();
    throwOnUnassigned();
}

Edit: Forgot to add #include<array>. For some reason, the code compiles with the include in gcc 10 but fails everywhere else.

\$\endgroup\$
4
  • \$\begingroup\$ Micro-review: you've misspelt std::size_t in a few places. \$\endgroup\$ Jul 8, 2023 at 15:28
  • \$\begingroup\$ @TobySpeight Are you refering to my use of size_t instead of std::size_t? \$\endgroup\$ Jul 8, 2023 at 15:58
  • \$\begingroup\$ Yes, exactly. You're probably using a platform where <cstdlib> (and other headers) declare both, but using the unqualified form is non-portable. \$\endgroup\$ Jul 8, 2023 at 16:02
  • \$\begingroup\$ I didn't know that. Wow. Thanks. Will add that to my linter configs. \$\endgroup\$ Jul 8, 2023 at 16:15

1 Answer 1

1
\$\begingroup\$

No macros, yay!

Reduce the amount of code duplication

The macros in your previous version had the advantage that you could greatly reduce the amount of things you had to repeat in your code. Now you have to write a struct for each operation, each taking 5 lines, like in:

struct Ret {
    using Operands = std::tuple<U16>;
    Operands operands;
    static constexpr std::string_view mnemonic = "RET";
};

Wouldn't it be nice if you could do it in one line? With some tricks you can write it like so:

struct Ret: Instr<"RET", U16> {};

So we inherit from a templated class, and we pass all the static, compile-time information as template parameters. Op looks like:

template<FixedString Name, typename... OperandTypes>
struct Instr {
    using Operands = std::tuple<OperandTypes...>;
    Operands operands;
    static constexpr std::string_view mnemonic = Name;
};

Passing a string literal as a template parameter is still not trivial in C++, but we worked around here using a helper class FixedString:

template<unsigned N>
struct FixedString 
{
    char buf[N + 1]{};

    constexpr FixedString(char const* s) 
    {
        for (unsigned i = 0; i != N; ++i)
            buf[i] = s[i];
    }

    constexpr operator std::string_view() const {
        return buf;
    }
};

template<unsigned N> FixedString(char const (&)[N]) -> FixedString<N - 1>;

You need to make a few changes to code that constructs instruction objects though. For the same reason you had to use double curly braces for instructions that take multiple operands, you now have to use three curly braces:

serializeInstructionToByteCode(BiPush{{{42, 420}}}, ss);
serializeInstructionToByteCode(TablePush{{{69, 42420}}}, ss);

You can work around that by providing a constructor for Instr, but then you need to ensure that constructor is made visible in each instruction class as well, so in the end it will just move the problem around. Another solution would be to use a helper function to construct instruction objects:

template<typename InstructionT, typename... Args>
auto makeInstr(Args&&... args) {
    return InstructionT{{{std::forward<Args>(args)...}}};
}

So you can write:

serializeInstructionToByteCode(makeInstr<BiPush>(42, 420), ss);
serializeInstructionToByteCode(makeInstr<TablePush>(69, 42420), ss);

Not great either, it's main benefit is that you don't have to remember the number of curly braces anymore.

Use std::apply() to iterate over tuple members

I see you use helper template functions and std::index_sequence to loop over tuple members, but you can use std::apply() instead. For example:

template<typename Tuple>
void print(std::ostream & os, Tuple const & tuple){
    std::cout << "(";
    std::apply([&](auto&... operands) {
        ((std::cout << int(operands) << ','), ...);
    }, tuple);
    std::cout << ")";
}

Opcode numbering

One issue with your code is that the opcode number is now implicit in the std::variant Instruction. It's easy to make a mistake and list instructions in the wrong order, or to forget one, and then the numbers used will be wrong.

Before you had an explicit mapping between opcode name and opcode number in the macro ITERATE_OPCODES. It might be nice to make it explicit in your code as well. Consider that you can add a static constexpr U8 opcode field to each instruction struct (or to my struct Instr). This makes serializing trivial (no need for loopUpOpCode()), and you can still build the functionMap at compile time with some work.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.