Комментарии / Профиль Acaunt / Хабр

Александр@Acaunt

Пользователь

Я написал компилятор на C++ при помощи LLVM

Я просто высказал своё мнение. И это нормально, что наши мнения не совпадают, так как каждому удобно по разному воспринимать информацию.

А про то что вы не поняли это ни как не связано со статьёй, так как он использует готовый фреймворк для написания языка программирования, а я свой с полного нуля, очень грубо говоря свой фреймворк.

Я лишь хотел поделиться своими наработками.

А дать определение модульного парсера к сожалению не могу так как это лишь идея проекта без какой либо конкретики. И вот из-за того что я не совсем понимаю как эту конкретику сформулировать я пока остановился.

И да согласен, что от порядка сканеров лексика может нарушиться. Но в моем представлении лексер выглядит модульным.

-2

Я написал компилятор на C++ при помощи LLVM

Acaunt 18 янв в 19:53

Наверняка статья очень интересная, но пока к сожалению столь длинное чтиво читать не очень хочется. Может быть потом прочитаю.

Можно было бы наверное разделить на несколько статей где подробно рассказывается отдельно лексер, отдельно парсер, отдельно синтаксическое дерево и т.д.. Так оно и психологически проще читать было бы.

А так я сюда спустился для того чтобы просто поделиться своей маленькой наработкой над которой работал недавно, но забросил пока из-за нехватки знаний.

Я тоже ради интереса писал свой C подобный язык программирования. Но смог реализовать пока лишь лексер. У меня была задумка модульности написания, так чтобы можно было добавлять в язык новые возможности постепенно без полного переписывания кода. Для этого я реализовал префиксное дерево для быстрого поиска ключевых слов. А для лексера сканеры. И у меня получилось нечто подобное:

Скрытый текст

#include <unordered_map>
#include <optional>
#include <string_view>
#include <iostream>
#include <deque>
#include <utility>
#include <memory>
#include <vector>

/*=============== Trie ===============*/
template<class Char, class T>
class Trie {
private:
    using string = std::basic_string<Char>;
    using string_view = std::basic_string_view<Char>;
    
    template<class String>
    class Result_impl;
    
    using Result = Result_impl<string>;
    using Result_view = Result_impl<string_view>;
    
    struct Node {
        std::unordered_map<Char, Node> nodes;
        std::optional<T> value;
    };
    
public:
    Trie() = default;
    Trie(Trie&&) = default;
    Trie(const Trie&) = default;
    
    Trie(std::initializer_list<std::pair<string_view, T>> ilist) {
        for (auto& [key, value] : ilist) {
            emplace(key, value);
        }
    }
    
    Trie& operator=(Trie&&) = default;
    Trie& operator=(const Trie&) = default;
    
public:
    const std::optional<T>& find(string_view key) const {
        const Node* current = &root;
        
        for (auto& ch : key) {
            auto it = current->nodes.find(ch);
            if (it == current->nodes.end()) {
                static const std::optional<T> empty;
                return empty;
            }
            
            current = &it->second;
        }
        
        return current->value;
    }
    
public:
    std::deque<Result_view> find_prefix_of(string_view word) const {
        std::deque<Result_view> results;
        const Node* current = &root;

        if (current->value) {
            results.emplace_back({}, &*current->value);
        }

        for (size_t i = 0; i < word.size(); ++i) {
            auto it = current->nodes.find(word[i]);
            if (it == current->nodes.end()) {
                break;
            }

            current = &it->second;

            if (current->value) {
                results.emplace_back(word.substr(0, i + 1), &*current->value);
            }
        }

        return results;
    }
    
    std::deque<Result> find_by_prefix(string_view prefix) const {
        std::deque<Result> results;
        const Node* current = &root;

        for (Char ch : prefix) {
            auto it = current->nodes.find(ch);
            if (it == current->nodes.end()) {
                return results;
            }
            current = &it->second;
        }

        string key(prefix);
        collect(*current, key, results);
    
        return results;
    }
    
public:
    Result_view find_first_prefix(string_view word) const {
        const Node* current = &root;
        
        if (current->value) {
            return { {}, &*current->value };
        }
        
        for (size_t i = 0; i < word.length(); ++i) {
            auto it = current->nodes.find(word[i]);
            if (it == current->nodes.end()) {
                return {};
            }
            
            current = &it->second;
            
            if (current->value) {
                return { word.substr(0, i + 1), &*current->value };
            }
        }
            
        return {};
    }
    
    Result_view find_last_prefix(string_view word) const {
        const Node* current = &root;
        Result_view result;
        size_t length = 0;
        
        if (current->value) {
            result._value = &*current->value;
        }
        
        for (size_t i = 0; i < word.length(); ++i) {
            auto it = current->nodes.find(word[i]);
            if (it == current->nodes.end()) {
                break;
            }
            
            current = &it->second;
            
            if (current->value) {
                result._value = &*current->value;
                length = i + 1;
            }
        }
        
        result._key = word.substr(0, length);
        
        return result;
    }
    
public:
    void insert(string_view key, T&& value) {
        emplace(key, std::move(value));
    }
    
    void insert(string_view key, const T& value) {
        emplace(key, value);
    }
    
    template<class ... Args>
    void emplace(string_view key, Args&& ... args) {
        Node* current = &root;
        
        for (auto& ch : key) {
            current = &current->nodes[ch];
        }
        
        current->value.emplace(std::forward<Args>(args) ...);
    }
    
public:
    void clear() {
        root.nodes.clear();
        root.value.reset();
    }
    
    void erase(string_view key) {
        erase_impl(root, key, 0);
    }
    
private:
    static void collect(Node& node, string& key, std::deque<Result>& results) {
        if (node.value) {
            results.emplace_back(key, &*node.value);
        }

        for (const auto& [ch, child] : node.nodes) {
            key.push_back(ch);
            collect(child, key, results);
            key.pop_back();
        }
    }
    
    bool erase_impl(Node& node, const string_view& key, size_t index) {
        if (index == key.size()) {
            if (!node.value) {
                return false;
            }
            node.value.reset();
            return node.nodes.empty();
        }

        auto it = node.nodes.find(key[index]);
        if (it == node.nodes.end()) {
            return false;
        }

        if (erase_impl(it->second, key, index + 1)) {
            node.nodes.erase(it);
        }

        return node.nodes.empty() && !node.value;
    }
    
private:
    Node root;
};

template<class Char, class T>
template<class String>
class Trie<Char, T>::Result_impl {
public:
    friend Trie;
    
public:
    Result_impl()
        : _value(nullptr) {
    }
    
    Result_impl(Result_impl&& other)
        : _key(std::move(other._key))
        , _value(std::exchange(other._value, nullptr)) {
    }
    
    Result_impl(const Result_impl& other)
        : _key(other._key)
        , _value(other._value) {
    }
    
    Result_impl(String key, const T* value)
        : _key(key)
        , _value(value) {
    }
    
    Result_impl& operator=(Result_impl&& other) {
        if (this != &other) {
            _key = std::move(other._key);
            _value = std::exchange(other._value, nullptr);
        }
        
        return *this;
    }
    
    Result_impl& operator=(const Result_impl& other) {
        if (this != &other) {
            _key = other._key;
            _value = other._value;
        }
        
        return *this;
    }
    
public:
    const String& key() const {
        return _key;
    }
    
    const T& value() const {
        if (_value == nullptr) {
            throw std::logic_error("Result not have value");
        }
        
        return *_value;
    }
    
    const T& value_or(const T& value) const {
        return _value ? *_value : value;
    }
    
public:
    operator bool() const {
        return _value;
    }

private:
    String _key;
    const T* _value;
};

/*=============== Token ===============*/
enum Token_type {
    KEYWORD,
    
    IDENTIFIER,
    
    OPERATOR,
    
    BINARY,
    
    OCTE,
    
    HEX,
    
    INT,
    
    FLOAT,
    
    DOUBLE,
    
    CHAR,
    
    STRING,
    
    PUNCTUATOR,
    
    WHITESPACE,
    
    COMMENT,
    
    ERROR = 404
};

template<class Char>
struct Token {
    Token() = default;
    Token(Token&&) = default;
    Token(const Token&) = default;
    
    Token(Token_type token, std::basic_string<Char> lexeme, size_t line, size_t column)
        : token(token)
        , lexeme(std::move(lexeme))
        , line(line)
        , column(column) {
    }
    
    Token_type token;
    std::basic_string<Char> lexeme;
    size_t line;
    size_t column;
};

/*=============== Lexer ===============*/
template<class Char>
struct Lexer_data {
    Lexer_data(std::basic_string_view<Char> code)
        : code(code) {
    }
    
    void new_line() {
        ++line;
        column = 1;
    }
    
    void advance(size_t step) {
        column += step;
        code = code.substr(step);
    }
    
    std::deque<Token<Char>> tokens;
    
    void emplace(Token_type token, std::basic_string_view<Char> value) {
        tokens.emplace_back(token, std::basic_string<Char>(value), line, column);
    }
    
    std::basic_string_view<Char> code;
    
private:
    size_t line = 1;
    size_t column = 1;
};

template<class Char>
struct Scanner {
    virtual bool read(Lexer_data<Char>& data) const = 0;
};

template<class Char>
struct Lexer {
    std::deque<Token<Char>> tokenize(std::basic_string_view<Char> code) const {
        Lexer_data<Char> data(code);
        
        while (!data.code.empty()) {
            size_t size = data.code.size();
            
            for (auto& scanner : scanners) {
                if (scanner->read(data)) break;
            }
            
            if (size == data.code.size()) {
                data.emplace(Token_type::ERROR, data.code.substr(0,1));
                data.advance(1);
            }
        }
        
        return std::move(data.tokens);
    }
    
    template<class Scanner_t, class ... Args>
    void register_scanner(Args&& ... args) {
        scanners.emplace_back(std::make_unique<Scanner_t>(std::forward<Args>(args) ...));
    }
    
    template<class Scanner_t>
    void register_scanner(std::unique_ptr<Scanner_t> scanner) {
        if (scanner) {
            scanners.emplace_back(std::move(scanner));
        }
    }
private:
    std::vector<std::unique_ptr<Scanner<Char>>> scanners;
};

/*=============== Scanners ===============*/
template<class Char>
bool is_number(Char ch) {
    return (ch >='0' && ch <= '9');
}

template<class Char>
bool is_letter(Char ch) {
    return (
        (ch >= 'a' && ch <= 'z')
        ||
        (ch >= 'A' && ch <= 'Z')
    );
}

template<class Char>
struct Whitespace : Scanner<Char> {
    bool read(Lexer_data<Char>& data) const override {
        switch(data.code.front()) {
        case ' ':
        case '\t':
            data.advance(1);
            break;
        case '\n':
        case '\r':
            data.advance(1);
            data.new_line();
            break;
        default:
            return false;
        }
        
        return true;
    }
};

template<class Char>
struct Keyword : Scanner<Char> {
    Keyword(std::initializer_list<const Char*> ilist) {
        for (auto& key : ilist) {
            keywords.emplace(key, Token_type::KEYWORD);
        }
    }
    
    bool read(Lexer_data<Char>& data) const override {
        auto result = keywords.find_last_prefix(data.code);
        
        if (result == false) return false;
        
        auto& lexeme = result.key();
        size_t i = lexeme.size();
        
        if (i < data.code.size() && (is_letter(data.code[i]) || is_number(data.code[i]) || data.code[i] == '_')) return false;
        
        data.emplace(Token_type::KEYWORD, lexeme);
        data.advance(i);
        
        return true;
    }
    
    Trie<Char, Token_type> keywords;
};

template<class Char>
struct Identifier : Scanner<Char> {
    bool read(Lexer_data<Char>& data) const override {
        if (
            !is_letter(data.code.front())
            &&
            data.code.front() != '_'
        ) return false;
        
        size_t i = 1;
        
        while (
            i < data.code.size()
            &&
            (
                is_letter(data.code[i])
                ||
                is_number(data.code[i])
                ||
                data.code[i] == '_'
            )
        ) {
            ++i;
        }
        
        data.emplace(Token_type::IDENTIFIER, data.code.substr(0, i));
        data.advance(i);
        
        return true;
    }
};

template<class Char>
struct Operator : Scanner<Char> {
    Operator(std::initializer_list<const Char*> ilist) {
        for (auto& key : ilist) {
            operators.emplace(key, Token_type::KEYWORD);
        }
    }
    
    bool read(Lexer_data<Char>& data) const override {
        auto result = operators.find_last_prefix(data.code);
        
        if (result == false) return false;
        
        auto& lexeme = result.key();
        size_t i = lexeme.size();
        
        data.emplace(Token_type::OPERATOR, lexeme);
        data.advance(i);
        
        return true;
    }
    
    Trie<Char, Token_type> operators;
};

template<class Char>
struct Number : Scanner<Char> {
    bool read(Lexer_data<Char>& data) const override {
        switch (
            start_number
            .find_last_prefix(data.code)
            .value_or(Token_type::ERROR)
        ) {
        case Token_type::INT:
            if (is_decimal(data)) return true;
            break;
        case Token_type::DOUBLE:
            if (is_double(data)) return true;
            break;
        case Token_type::BINARY:
            if (is_binary(data)) return true;
            break;
        case Token_type::OCTE:
            if (is_octe(data)) return true;
            break;
        case Token_type::HEX:
            if (is_hex(data)) return true;
            break;
        default:
            return false;
        };
        
        return false;
    }
    
    static bool is_binary(Lexer_data<Char>& data) {
        size_t i = 2;
        
        Token_type token = Token_type::ERROR;
        while (i < data.code.size()) {
            auto& ch = data.code[i];
            if (ch == '0' || ch == '1') {
                token = Token_type::BINARY;
            }
            else if (ch != '\'') {
                break;
            }
            ++i;
        }
        
        data.emplace(token, data.code.substr(0, i));
        data.advance(i);
        
        return true;
    }
    static bool is_octe(Lexer_data<Char>& data) {
        size_t i = 1;
        
        Token_type token = Token_type::ERROR;
        while (i < data.code.size()) {
            auto& ch = data.code[i];
            if (ch >= '0' && ch <= '7') {
                token = Token_type::OCTE;
            }
            else if (ch != '\'') {
                break;
            }
            ++i;
        }
        
        data.emplace(token, data.code.substr(0, i));
        data.advance(i);
        
        return true;
    }
    
    static bool is_hex(Lexer_data<Char>& data) {
        size_t i = 2;
        
        Token_type token = Token_type::ERROR;
        while (i < data.code.size()) {
            auto& ch = data.code[i];
            if (
                (ch >= '0' && ch <= '9')
                ||
                (ch >= 'A' && ch <= 'F')
                ||
                (ch >= 'a' && ch <= 'f')
            ) {
                token = Token_type::HEX;
            }
            else if (ch != '\'') {
                break;
            }
            ++i;
        }
        
        data.emplace(token, data.code.substr(0, i));
        data.advance(i);
        
        return true;
    }
    
    static bool is_decimal(Lexer_data<Char>& data) {
        return false;
    }
    
    static bool is_double(Lexer_data<Char>& data) {
        return false;
    }
    
    static const Trie<Char, Token_type> start_number;
};

template<class Char>
const Trie<Char, Token_type> Number<Char>::start_number {
    {"1", Token_type::INT},
    {"2", Token_type::INT},
    {"3", Token_type::INT},
    {"4", Token_type::INT},
    {"5", Token_type::INT},
    {"6", Token_type::INT},
    {"7", Token_type::INT},
    {"8", Token_type::INT},
    {"9", Token_type::INT},
    
    {"0.", Token_type::DOUBLE},
    {"0e", Token_type::DOUBLE},
    
    {"0b", Token_type::BINARY},
    {"0B", Token_type::BINARY},
    
    {"0", Token_type::OCTE},
    
    {"0x", Token_type::HEX},
    {"0X", Token_type::INT},
};

template<class Char>
struct String : Scanner<Char> {
    bool read(Lexer_data<Char>& data) const override {
        if (data.code.empty() || data.code.front() != '"') {
            return false;
        }
        
        size_t i = 1;
        bool escape = false;
        
        while (i < data.code.size()) {
            Char c = data.code[i];
            
            if (!escape && (c == '\n' || c == '\r')) {
                data.emplace(Token_type::ERROR, data.code.substr(0, i));
                data.advance(i);
                if (c == '\n') {
                    data.new_line();
                }
                return true;
            }
            
            if (escape) {
                escape = false;
            } else if (c == '\\') {
                escape = true;
            } else if (c == '"') {
                i++; 
                data.emplace(Token_type::STRING, data.code.substr(0, i));
                data.advance(i);
                return true;
            }
            
            i++;
        }
        
        data.emplace(Token_type::ERROR, data.code.substr(0, i));
        data.advance(i);
        return true;
    }
};

template<class Char_>
struct Char : Scanner<Char_> {
    bool read(Lexer_data<Char_>& data) const override {
        if (data.code.empty() || data.code.front() != '\'') {
            return false;
        }
        
        if (data.code.size() < 2) {
            data.emplace(Token_type::ERROR, data.code.substr(0, 1));
            data.advance(1);
            return true;
        }
        
        size_t i = 1;
        auto& c = data.code[i];
        
        if (c == '\\') {
            if (data.code.size() < 3) {
                data.emplace(Token_type::ERROR, data.code.substr(0, 2));
                data.advance(2);
                return true;
            }
            
            i++;
            auto& escape_char = data.code[i];
            
            switch (escape_char) {
                case '\'': case '\"': case '\\': case '0': 
                case 'n': case 't': case 'r': case 'b': case 'f': case 'v':
                case 'a': case '?':
                    break;
                default:
                    data.emplace(Token_type::ERROR, data.code.substr(0, i + 1));
                    data.advance(i + 1);
                    return true;
            }
        } else if (c == '\n' || c == '\r') {
            data.emplace(Token_type::ERROR, data.code.substr(0, i));
            data.advance(i);
            if (c == '\n') data.new_line();
            return true;
        } else if (c == '\'') {
            data.emplace(Token_type::ERROR, data.code.substr(0, i));
            data.advance(i);
            return true;
        }
        
        i++;
        if (i >= data.code.size() || data.code[i] != '\'') {
            data.emplace(Token_type::ERROR, data.code.substr(0, i));
            data.advance(i);
            return true;
        }
        
        i++;
        
        data.emplace(Token_type::CHAR, data.code.substr(0, i));
        data.advance(i);
        return true;
    }
};




/*=============== keywords ===============*/

std::initializer_list<const char*> keywords {
    "int",
    "float",
    "double",
    "bool",
    "char",
    "void",
    "auto",
    
    "if",
    "else",
    "for",
    "do",
    "while",
    "continue",
    "break",
    "return",
    
    "true",
    "false",
    
    "module",
    "export",
    "import",
};

/*=============== operators ===============*/

std::initializer_list<const char*> operators {
    "+",
    "-",
    "*",
    "/",
    "%",
    
    "=",
    "+=",
    "-=",
    "*=",
    "/=",
    "%="
};

/*=============== punctuators ===============*/

std::initializer_list<const char*> punctuators {
    "(",
    ")",
    
    "{",
    "}",
    
    "[",
    "]",
    
    ";",
    ".",
    ",",
    "::",
    "..."
};

std::string_view code = R"(
import std;

bool is_even(int num) {
    return num % 2 == 0;
}

int main() {
    for (int i = 0; i < 10; ++i) {
        if (is_even(i)) {
            std::print("is even number: ", i, '\n');
        }
    }
    
    return 0;
}
)";

int main() {
    std::cout << code;
    Lexer<char> lexer;
    
    //lexer.register_scanner<Comment<char>>();
    lexer.register_scanner<Whitespace<char>>();
    lexer.register_scanner<Keyword<char>>(keywords);
    lexer.register_scanner<Identifier<char>>();
    lexer.register_scanner<Operator<char>>(operators);
    lexer.register_scanner<Number<char>>();
    //lexer.register_scanner<Punctuator<char>>();
    lexer.register_scanner<String<char>>();
    lexer.register_scanner<Char<char>>();
    
    auto tokens = lexer.tokenize(code);
    
    for (auto& token : tokens) {
        std::cout << "Token: " << token.lexeme 
                  << " Type: " << token.token 
                  << " Line: " << token.line 
                  << " Column: " << token.column 
                  << std::endl;
    }
    
    return 0;
}

А потом я просто столкнулся с тем, что не понимаю как реализовать модульный парсер. Поэтому пока забросил

std::vector::erase. Что-то здесь не так

Acaunt 6 фев 2025 в 13:45

std::vector контейнер предназначенный для выделения блока памяти вот смотри:

[1][2][3][4][5]
       ^
ты хочешь удалить этот объект
что происходит в векторе:
1шаг: 4 элемент перемещаем в 3
обычно при этом в объекте ктороый перемещают затирается его старая информация
[1][2][4][0][5]
тепрь старый 4 элемент пустой но он ещё существует
2шаг: 5 элемент перемещаем в 4 элемент
[1][2][4][5][0]
теперь старый 5 элемент обнулен но всё ещё находится в памяти
3шаг: вызываем деструктор у последнего элемента
[1][2][4][5][NULL]
последний элемент удалён но нужно помнить что в векторе память уже была выделена память под 5 элементов
поэтому последний элемент всё ещё занимает память но он не инециализирован

если тебя смущает это то тебе необходимо использовать std::list или std::forward_list

list
       --> --> --> --> -->
NULL [1] [2] [3] [4] [5] NULL
   <-- <-- <-- <-- <--

тут например каждый элемент имеет связь со своими соседями, но при этом они находятся в разных участках памяти

удаление происходит так:

list
       --> --> --> -->
NULL [1] [2] [4] [5] NULL
   <-- <-- <-- <--

тоесть соседи у удаляемого объекта забывают про него и знакомятся с новым соседом

а std::forward почти как std::list но объекты не имеют связи с предыдущими соседями тоесть:

forward_list
  --> --> --> --> -->
[1] [2] [3] [4] [5] NULL

Но из-за такого распределения памяти выходит проблематичным получение произвольного объекта по индексу

Лучше изучите стандартные контейнеры STL

std::vector::erase. Что-то здесь не так

Acaunt 6 фев 2025 в 12:49

Добавь к классу Object ещё конструкторы и операторы копирования, перемещения с выводом в консоль запусти свой код ещё раз и посмотри результат.

П.С. при использовании метода erase все последующие объекты применяют методы перемещения чтобы занять место в памяти у удаляемого объекта. И так получается, что на место последнего никого нет, но память нужно освободить. Вот и вызывается деструктор у последнего.

Судоку: моя попытка в новый алгоритм решения. Часть 1 (надеюсь)…

Acaunt 5 фев 2025 в 06:30

А понял. Да пробовал решалось. Так как в моем алгоритме используется перебор когда больше нет единственного варианта.

Ах да ещё не забудь проверить работоспособность свой алгоритм в случае если судоку выдан с ошибкой, изначально.

Судоку: моя попытка в новый алгоритм решения. Часть 1 (надеюсь)…

Acaunt 5 фев 2025 в 03:58

В каком смысле на Эвересте?

П.С. я для тестов алгоритма брал из интернета самые сложные варианты судоку.

Судоку: моя попытка в новый алгоритм решения. Часть 1 (надеюсь)…

Acaunt 4 фев 2025 в 20:02

Вряд ли смогу точно сказать, но по-моему меньше 5 секунд для 25х25. А для 36х36 я просто ждал около минуты ничего не происходило, ну и выключал программу

Судоку: моя попытка в новый алгоритм решения. Часть 1 (надеюсь)…

Acaunt 31 янв 2025 в 21:13

Читал, читал и как то не понял прикола с опорными точками. Ты типо собираешься относительно опорных точек подбирать значения?

Я как то давно делал авторешатель судоку. (Только я работал с кодом на C++, но это не важно).

У меня было несколько этапов:

1) сбор полной информации о всех свободных клеток (при этом собирал я их в разные массивы: общий где абсолютно все клетки, клетки находящиеся в одном большом квадрате, по горизонтали, по вертикали. получились 4 блока для анализа)

2) для каждой свободной клетки я собирал массив из возможных вариантов (для этой цели я использовал массив битов, для того чтобы хоть как-то сэкономить на памяти, то есть соответственно 0 бит отвечал за число 1, 2 бит за число 3 ну и так далее)

3) я проводил анализ каждого блока (из 1 этапа) для массива, где хранятся все свободные клетки, я искал клетки у которых имеется единственное возможное значение после чего записывал его и удалял клетку из всех блоков. Для остальных блоков была задача на поиск единственного возможного значения, которого нет в других клетках, ну и снова записывал его и удалял из всех блоков.

4) провожу проверку на то что решено (индикатором являлся размер 1 блока)

5) проверяю на ошибки (в возможных вариантах клетки отсутствуют варианты, это единственный способ проверки мне тогда пришел в голову)

6) если в 3 этапе была совершена хотя бы 1 запись то возвращался к 3 этапу, в противном случае я искал клетку с минимально возможным количеством вариантов. (Самый желанный вариант это клетка с 2 возможными значениями) Копировал всё данные и в копию подставлял возможный вариант и отправлял копированные данные на 3 этап и так далее пока не решится или не обнаружится ошибка.

В принципе мой алгоритм справлялся с судоку размером 25х25, но с 36х36 уже слишком долго выполняется.

Сейчас у меня есть пара мыслей как можно оптимизировать алгоритм, но если честно просто лень

constexpr Game of Life

Acaunt 22 ноя 2024 в 07:06

Статья понравилась, жалко у меня не хватает кармы, чтобы повысить вам карму.

Узнал немного нового о compile time. Даже появилась идея, как возможно можно решить одну старую задумку, которая у меня до этого не получалась.

Когда-то давно тоже делал игру в жизнь, но с возможностью менять правила жизни мира в процессе выполнения.

П.С. Спасибо за статью)

Logger C++

Acaunt 27 авг 2024 в 05:17

Прикольно, но хотелось бы больше получить информации о реализации внутренней структуры кода. (Да я увидел ссылку на гитхаб, но мне бы хотелось узнать мысли о том как пришёл к такому решению) хотя наверное это не совсем статья это больше самореклама.

Ещё я так понял у тебя логгер поддерживает только строки, что не всегда удобно, если например нужно для отладки отправить числа какие-нибудь с сообщением что конкретно происходит. Это конечно можно решить с помощью конкатенации строк и чисел, но всё равно не совсем удобно.

Я например делал свой логгер, пару месяцев назад (ещё не доделал) вот пример моей реализации:

Скрытый текст

#include <iostream>

#include <condition_variable>
#include <unordered_map>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <thread>
#include <atomic>
#include <mutex>
#include <queue>
using namespace std;

class Logger {
private:
    enum Level_log : uint8_t {
        info,
        debug,
        warning,
        error
    };
    
private:
    template<uint8_t>
    struct Level {};
    
public:
    using Info = Level<Level_log::info>;
    using Debug = Level<Level_log::debug>;
    using Warning = Level<Level_log::warning>;
    using Error = Level<Level_log::error>;
    
public:
    class Message {
    private:
        uint8_t level_log;
        ostringstream message;
        
    public:
        template<uint8_t lvl>
        Message(const Level<lvl>& id)
            : level_log(lvl) {
        }
        
        Message(Message&&) = default;
        
        ~Message() {
           if (message.tellp() != 0) {
               Logger::get_instance().add_to_queue(level_log, move(message.str()));
            }
        }
        
    public:
        template<class Text>
        Message& operator<<(const Text& text) {
            message << text;
            return *this;
        }

        Message& operator<<(ostream& (*manip)(ostream&)) {
            message << manip;
            return *this;
        }
    };
    
private:
    queue<pair<uint8_t, string>> queue_messages;
    unordered_map<uint8_t, ofstream> files;
    atomic<bool> is_work;
    thread printer;
    mutex mtx;
    condition_variable status_queue;
    
private:
    Logger()
        : is_work(true)
        , printer(&Logger::print, this) {
        auto open_file = [this](uint8_t key, string_view name) {
            auto* file = &files[key];
            
            file->open(name.data());
            
            if (file->is_open() == false) {
                files.erase(key);
            }
        };
        
        open_file(Level_log::info, "info.log");
        open_file(Level_log::debug, "debug.log");
        open_file(Level_log::warning, "warning.log");
        open_file(Level_log::error, "error.log");
    }
    
    Logger(Logger&&) = delete;
    Logger(const Logger&) = delete;
    Logger& operator=(Logger&&) = delete;
    Logger& operator=(const Logger&) = delete;
    
    ~Logger() {
        terminate();
    }
    
public:
    static Logger& get_instance() {
        static Logger instance;
        return instance;
    }

    static void terminate() {
        Logger& logger = get_instance();
        
        logger.is_work = false;
        logger.status_queue.notify_one();
        
        if (logger.printer.joinable()) {
            logger.printer.join();
        }
        
        for (auto& it : logger.files) {
            it.second.close();
        }
    }

public:
    template<class Text>
    Message operator<<(const Text& text) {
        return move(Message(Info()) << text);
    }

    Message operator<<(ostream& (*manip)(ostream&)) {
        return move(Message(Info()) << manip);
    }
    
    template<uint8_t lvl>
    Message operator<<(const Level<lvl>& id) {
        return Message(id);
    }

private:
    void print() {
        auto print_in_file = [this](uint8_t key, const string& message) {
            auto it = files.find(key);
            
            if (it != files.end()) {
                it->second << message;
            }
        };
        
        while (is_work == true || queue_messages.empty() == false) {
            unique_lock<mutex> lock(mtx);
            status_queue.wait(lock, [this] { return !queue_messages.empty() || !is_work; });
            
            while (!queue_messages.empty()) {
                auto [key, message] = move(queue_messages.front());
                queue_messages.pop();
                
                lock.unlock();
                
                cout << message;
                
                switch (key) {
                case Level_log::debug:
                case Level_log::warning:
                case Level_log::error:
                    print_in_file(key, message);
                    
                default:
                    print_in_file(Level_log::info, message);
                }
                
                lock.lock();
            }
        }
    }
    
    void add_to_queue(uint8_t level_log, string&& message) {
        lock_guard<std::mutex> lock(mtx);
        queue_messages.push({level_log, move(message)});
        status_queue.notify_one();
    }
};

Logger& logg = Logger::get_instance();

string time_now() {
    ostringstream oss;
    
    auto now = chrono::system_clock::now();
    
    time_t time = chrono::system_clock::to_time_t(now);
    tm* ltm = localtime(&time);
    oss << "[" << setfill('0') << setw(2) << ltm->tm_hour << ":" << setfill('0') << setw(2) << ltm->tm_min << ":" << setfill('0') << setw(2) << ltm->tm_sec << "]";

    return oss.str();
}

#define INFO Logger::Info()

#define DEBUG Logger::Debug() << time_now() << '[' << __FILE__ << "][" << __FUNCTION__ << "] "

#define WARNING Logger::Warning() << '[' << __FILE__ << "][" << __FUNCTION__ << "] "

#define ERROR Logger::Error() << time_now() << '[' << __FILE__ << "][" << __FUNCTION__ << "][line send message: " << __LINE__ << "] "

void read_file(string_view name) {
    ifstream file(name.data());
    
    if (file.is_open() == false) { return; }
    
    cout << endl << endl;
    
    for (size_t i = 0; i < 40; ++i) {
        cout << '-';
    }
    
    cout << endl << "this is text from file -> " << name << endl << endl;
    string text;
    while (file.eof() == false) {
        getline(file, text);
        cout << text << endl;
    }
    
    file.close();
}

int main() {
    logg << "Starting application" << endl;
    logg << INFO << "This is an info message" << endl;
    logg << DEBUG << "Debugging information" << endl;
    logg << WARNING << "This is a warning" << endl;
    logg << ERROR << "An error has occurred" << endl;
    
    Logger::terminate();
    
    read_file("info.log");
    read_file("debug.log");
    read_file("warning.log");
    read_file("error.log");
    
    return 0;
}

В моем случае я пытался сохранить привычный синтаксис std::cout. Да я знаю, что использовать define DEBUG не лучшая идея, но это просто временная реализация для тестов. пока не совсем придумал, как лучше сделать.