実装の課題:訪問者パターンの再検討

言語としての C++ は、古典的な「Java スタイル」のオブジェクト指向プログラミングから離れつつあります。 階層。これらはスタンドアロン クラス、フリー関数、および型消去に置き換えられました。

その利点は明らかです。参照セマンティクスの代わりに、C++ にとってより単純で自然な値セマンティクスを使用できます。侵入的なインターフェイス継承の代わりに、外部ダックタイピングが可能です。

この運動の精神に則り、1 つの OOP パターンを見て、このスタイルに適用できるかどうかを見てみましょう:ビジター パターンです。

訪問者パターン

訪問者のパターンに慣れていない場合は、簡単におさらいしてください。

何らかの形式のマークアップ言語を設計しているとします。入力を解析し、さまざまな出力形式に変換します。そのために、パーサーは抽象構文木 (AST) を作成し、出力は AST を取得して変換します。

OOP パラダイムに従って、AST はクラス階層に実装されます。10 があります。 基本クラス、次に 24 などの派生クラス 、 334852 など。いくつかのクラスは、67 のように、子ノードのコンテナーです。 、 78 のようにそうでないものもあります .

class node { … };

class document final : public node
{
public:
    …

private:
    std::vector<std::unique_ptr<node>> children_;
};

class text final : public node
{
public:
    …

private:
    std::string content_;
};

…

パーサーは比較的単純です。テキストを解析し、対応するノードを構築します。

ただし、出力形式を生成するには、ノードの正確なタイプを知り、それに応じて異なるアクションを実行する必要があります。従来の OOP 設計では、これは 87 を使用して行われます。 C++ の関数:99 があります 関数 100 ノードを取り、113 を返す

class node
{ 
public:
    virtual std::string render_html() const = 0;
};

class document final : public node
{
public:
    std::string render_html() const override
    {
        std::string result = "<head>…</head>\n<body>\n";
        for (auto& child : children_)
            result += child->render_html(); 
        result += "</body>\n";
        return result;
    }
};

class text final : public node
{
public:
    std::string render_html() const override
    {
        return sanitize_html(content_);
    }
};

…

ここまでは簡単です。

ただし、CommonMark でレンダリングする必要があるため、127 を追加します。 また、プレーンテキストが必要なため、 137 を追加します 関数を使用して、すべてのクラスでオーバーライドします。XML、LaTeX、149 、…

151 の間 関数にはユースケースがありますが、ここにも欠点があります:

  • 新しい操作を追加するのは難しい:すべてのクラスを更新する必要がある.
  • 操作は複数のファイルに分散されています。「AST を取得して HTML としてレンダリングする」操作は 1 つの操作ですが、クラスごとに個別に定義されているため、すべてのクラスにサニテーションなどの一般的な HTML 変換ルーチンを含める必要があります。
  • すべてのクラスは、それらに必要なすべての操作について知る必要があります。

ビジター パターンは、この問題の解決策です。基本的に設計をひっくり返します。操作を追加しにくく、新しいクラスを追加しやすくするのではなく、操作を追加しやすく、新しいクラスを追加しにくいように設計されています。新しい操作が新しいクラスよりも一般的に追加される状況向け。

一般的な実装は次のようになります。基本クラスですべての操作を定義する代わりに、操作ごとに 1 つのクラス (ビジター) を定義します。すべての派生クラスを処理するための異なる関数を提供します。基本クラスの階層では、 を 1 つだけ定義します。 160 関数 - 通常は 175 と呼ばれます または 188 -それは要素とその中のすべてのエンティティを訪問します.しかし、192 関数はテンプレート化できません。ビジター自体が基本クラスを持ち、206 をオーバーライドする必要があります 関数。

// base class for all visitors
class base_visitor
{
public:
    // called before all children
    virtual void visit_document_begin(const document& doc) = 0;
    // called after all children
    virtual void visit_document_end(const document& doc) = 0;

    virtual void visit_text(const text& t) = 0;

    … // for all other classes in the hierachy
};

class node
{
public:
    virtual void visit(base_visitor& visitor) const = 0;
};

class document final : public node
{
public:
    void visit(base_visitor& visitor) const override
    {
        visitor.visit_document_begin(*this);
        for (auto& child : children_)
            child->visit(visitor);
        visitor.visit_document_end(*this);
    }
};

class text final : public node
{
public:
    void visit(base_visitor& visitor) const override
    {
        visitor.visit_text(*this);
    }
};

… // other classes

struct html_renderer final : base_visitor
{
    std::string result;

    void visit_document_begin(const document& doc) override
    {
        result = "<head>…</head>\n<body>\n";
    }

    void visit_document_end(const document& doc) override
    {
        result += "</body>\n";
    }

    void visit_text(const text& t) override
    {
        result += sanitize_html(t.content());
    }
};

このアプローチは、上記の問題を解決します:

    <リ>

    他の出力形式のサポートを追加するのは簡単です — 新しいビジターを追加するだけです.そのために既存のクラスを更新する必要はありません.

    <リ>

    アルゴリズムはすべて 1 か所にあり、分散していません。

    <リ>

    階層内のクラスは、アクセス方法を知るだけで済みます。

ただし、他にも問題があります。

訪問者パターンの問題

    <リ>

    たくさんです の定型文:書くのに必要なコードの量を比較してください!

    <リ>

    実行時のオーバーヘッドが大きくなります:2 2 つのポリモーフィック階層があるため、仮想呼び出しが必要です。

    <リ>

    あなたのビジターを知っているクラス階層内のものだけを訪問することができます:210 を書くことはできません フリー機能として機能します。

    <リ>

    クラスのセット全体を事前に把握しておく必要があります。新しいクラスを追加するには、すべての訪問者を更新する必要があります。

最後のポイントについてもう少し話しましょう。プレーン テキストの出力形式を書きたいとします。プレーン テキストには多くの書式設定オプションが用意されていないため、AST のほとんどのノードでは、それを渡すだけです。レンダリングできるノードができるまで。

強調用の HTML ビジターは次のようになります:

void visit_emphasis_begin(const emphasis&) override
{
    result += "<em>";
}

void visit_emphasis_end(const emphasis&) override
{
    result += "</em>";
}

しかし、プレーン テキスト レンダラーは、プレーン テキストでは表現できないため、それが強調であるという事実を無視します:

void visit_emphasis_begin(const emphasis&) override {}
void visit_emphasis_end(const emphasis&) override {}

そしてたくさんあります しかし、平文レンダラーは、自分にとって重要ではない派手なクラスのすべてを知る必要があります。228 を追加すると ノードでは、何もしない 2 つの新しい関数を更新する必要があります!

そこで、侵入的ではなく、階層の一部のみの訪問を許可するビジターを導入することで、これらの問題のいくつかを修正してみましょう.

ステップ 1:ビジター内の visit() 関数を 1 つだけ

ベースの訪問者を取得して変換しましょう:236 を持つ代わりに 関数はすべてのクラスに適用されますが、実際の訪問者が関心を持っているクラスにのみ必要です。

しかし、基底クラスは、後で気にするクラスを認識していません — できません.

243 が理想的です すべてを受け入れるためのテンプレート しかし、これは C++ では実行できないため、C テンプレートを使用します:254 .型情報を保持するために、264 を使用します。 であるため、後でキャストして戻すことができます。

また、NVI パターンに従ってみましょう:

class base_visitor
{
public:
    template <typename T>
    void operator()(const T& obj)
    {
        do_visit(&obj, typeid(obj));
    }

protected:
    ~base_visitor() {}
 
private:
    virtual void do_visit(const void* ptr,
                          const std::type_info& type) = 0;
};

派生ビジターが 274 をオーバーライドするという考え方です。 関数を呼び出して、対象となるすべての型の型チェックを行い、一致する型にポインターをキャストして、visit を実行します。

ただし、そこにはわずかなバグがあります。クラス階層の基底クラスにアクセスすると、. 285292 動的型を正しく返します。ただし、301 実際の派生クラスではなく、基底クラスへのポインタです。312 基本クラスへのポインターは、派生クラスにキャストしてはなりません。

実際には、まだ機能します — 基本クラスのアドレスと派生クラスのアドレスは同じです — 多重継承がない限り。それをサポートしたい場合は、基本クラスのポインターを変換し、それを動的型へのポインターに変換する方法を見つける必要があります。

おそらくあまり知られていない事実:328 できる 330 まで

ただし、340 は使用できません ポリモーフィックではない型については、小さなヘルパー関数が必要です:

template <typename T>
const void* get_most_derived(const T& obj)
{
    // if constexpr FTW!
    if constexpr (!std::is_polymorphic_v<T> || std::is_final_v<T>)
        return &obj;
    else
        return dynamic_cast<const void*>(&obj);
}

…

template <typename T>
void base_visitor::visit(const T& obj)
{
    do_visit(get_most_derived(obj), typeid(obj));
}

その訪問者では、353 には何も必要ありません 364 と書くだけです。 :

struct html_renderer final : base_visitor
{
    std::string result;

private:
    void do_visit(const void* ptr, const std::type_info& type) override
    {
        if (type == typeinfo(document))
        {
            auto& doc = *static_cast<const document*>(ptr);
            …
        }
        else if (type == typeinfo(text))
        {
            auto& t = *static_cast<const text*>(ptr);
            …
        }
        else
            throw missing_type(type);
    }
};

このビジター デザインは、私が前に挙げたすべての問題をすでに解決しています:

  • 邪魔にならない:何でもアクセスできる ノードから 375 まで
  • 関心のある型について知る必要があるだけです。プレーン テキストのビジターは、新しい型が追加されたときに更新する必要はありません。

ただし、2 つの問題があります:

  • まず、タイプ スイッチはちょっと見苦しく、そもそも仮想関数で回避したかった問題です。
  • 第二に、ドキュメントの子に自動的にアクセスしなくなりました。

より楽しいので、最初の問題に最初に取り組みましょう。

ステップ 2:ラムダ ベースの訪問

実際の訪問を行うには、定型文がまだ多すぎます。さらに、そのタイプの切り替えは間違いやすいです — もともと、この例ではコピーと貼り付けのエラーがありました。それで、自動化しましょう。

C++Weekly に従っている場合は、バリアントを参照するのに役立つラムダ オーバーロードのトリックに慣れているかもしれません。アイデアは、次のような関数を使用しています:

template <typename... Functions>
auto overload(Functions... functions)
{
    struct lambda : Functions...
    {
        lambda(Functions... functions)
        : Functions(std::move(functions))... {}

        using Functions::operator()...;
    };

    return lambda(std::move(functions)...);
}

そして、複数のラムダを 1 つに結合できるようになりました:

// taken from: http://en.cppreference.com/w/cpp/utility/variant/visit
std::variant<int, long, double, std::string> v = …;

std::visit(overload([](auto arg) { std::cout << arg << ' '; },
    [](double arg) { std::cout << std::fixed << arg << ' '; },
    [](const std::string& arg) { std::cout << std::quoted(arg) << ' '; }),
    v);

訪問もそのように機能するようにしましょう。

383 を自動生成するだけです。 -398 -指定されたタイプのリストをチェーンし、関数を呼び出します:

template <typename Function, typename ... Types>
class lambda_visitor : public base_visitor
{
public:
    explicit lambda_visitor(Function f)
    : f_(std::move(f)) {}

private:
    template <typename T> 
    bool try_visit(const void* ptr, const std::type_info& type)
    {
        if (type == typeid(T))
        {
            f_(*static_cast<const T*>(ptr));
            return true;
        }
        else
            return false;
    }

    void do_visit(const void* ptr, const std::type_info& type) override
    {
        (try_visit<Types>(ptr, type) || ...);
    }

    Function f_;
};

401 の 1 ブロック -419 -チェーンは 426 で実現されます function:単一の型をチェックし、関数を呼び出して 433 を返します タイプが一致する場合、そうでない場合は 443 を返します .次に、C++17 の折り畳み式を使用して指定されたすべての型に対してそれを呼び出します。

型が一致しない場合は無視されます。これは、プレーン テキスト レンダラーに必要な動作です。

残っているのは、上に少しの砂糖だけです:

template <typename ... Types>
struct type_list {};

template <typename ... Types, typename ... Functions>
auto make_visitor(type_list<Types...>, Functions... funcs)
{
    auto overloaded = overload(std::move(funcs)...);
    return lambda_visitor<decltype(overloaded), Types...>(std::move(overloaded));
}

次に、HTML レンダラーは次のようになります。

std::string result;
auto visitor = make_visitor(type_list<document, text, …>{},
                            [&](const document& doc) { … },
                            [&](const text& t) { … });
visitor(node);

最も派生したものを渡す必要がある型として、基本クラスを渡してすべての子を訪問することはできないことに注意してください。 code>457 、 463 など

これにより冗長性の問題は解決されますが、まだ子を自動的に訪問することはできません。

ステップ 3:子どもたちの訪問

474 を個別に持つことはできません と 486 、そのため、この 2 つを区別する別の方法が必要です。498 を追加しましょう :

enum class visit_event
{
    container_begin, // before the children of a container
    container_end,   // after the children of a container
    leaf,            // no container
};

これはラムダにも渡され、訪問者が 2 つを区別できるようになります。

コンテナ訪問の実装は邪魔にはなりません — それをカスタマイズする何らかの方法が必要です.簡単にするために、 502 で行きましょう 関数:

class container_visitable
{
protected:
    ~container_visitable() = default;

private:
    // whether or not the entity is actually a container
    virtual bool is_container() const { return true; }

    // visits all children of a container
    virtual void visit_children(base_visitor& visitor) const = 0;

    friend base_visitor;
};

次に 515 522530 から継承された型を処理するように適合されています :

template <typename T>
void visit(const T& obj)
{
    if constexpr (std::is_base_of_v<container_visitable, T>)
    {
        if (static_cast<const container_visitable&>(obj).is_container())
        {
            do_visit(visit_event::container_begin, get_most_derived(obj), typeid(obj));
            static_cast<const container_visitable&>(obj).visit_children(*this);
            do_visit(visit_event::container_end, get_most_derived(obj), typeid(obj));
        }
        else
            do_visit(visit_event::leaf, get_most_derived(obj), typeid(obj));
    }
    else
        do_visit(visit_event::leaf, get_most_derived(obj), typeid(obj));
}

次に、クラス階層を少し調整する必要があります:

class node : public container_visitable
{
protected:
    // treat all as non-container for simplicity
    bool is_container() const override { return false; }

    void visit_children(base_visitor&) const override {}
};

class document final : public node
{
private:
    bool is_container() const override { return true; }

    void visit_children(base_visitor& visitor) const override
    {
        for (auto& child : children_)
            visitor(*child);
    }
};

class text final : public node
{
public:
    // no need here, it is not a container
};

ステップ 4:機能があると便利

アプローチをさらに拡張するのは簡単です。

たとえば、545 では 559 と書く必要があります 569 として 575 です 訪問者はノードのみを受け入れます。ただし、581 でそれらを自動的にアンラップできます。 594 のオーバーロード 同様に、条件付きで 602 にアクセスできます .

他の機能は、私たちが知らないものにアクセスした場合の包括的なタイプです。

投稿の長さを考えると、それらは読者の演習として残されています.

結論

私たちは、訪問されたクラス階層への影響が少なく、部分的な訪問を可能にする訪問者パターンの一般的な実装を開発しました。

もちろん、このアプローチは完璧ではありません:

ほとんどのテンプレート メタ プログラミング戦略と同様に、エラー メッセージは… いいものではありません。たとえば、型リストを更新するとテキストの壁が大きくなり、ラムダを追加するのを忘れます。

また、エラーが発生しやすくなります。たとえば、タイプ リストを更新する必要があります。自動的に計算されるわけではありません。

今のところ、コード全体はこちらにあります:https://gist.github.com/foonathan/daad3fffaf5dd7cd7a5bbabd6ccd8c1b

より洗練された実装に興味がある場合は、それに取り組むかもしれませんので、お知らせください!

付録:RTTI を取り除く

RTTI が気に入らなくても、簡単に削除できるので心配する必要はありません。欠点は、基本クラスにアクセスするときに技術的に UB があり、多重継承階層の基本クラスにアクセスすると実際に問題が発生することです。 RTTI が好きではないので、おそらく使用しないでしょう。

612 を使用せずに型を識別子に変換する方法が必要です .しかし、常に同じ型に対して同じ識別子を持つ必要はないので、これは非常に簡単です.

まず、強力な typedef を使用して ID タイプを定義しましょう:

struct type_id_t 
: type_safe::strong_typedef<type_id_t, std::uint64_t>,
  type_safe::strong_typedef_op::equality_comparison<type_id_t>,
  type_safe::strong_typedef_op::relational_comparison<type_id_t>
{
    using strong_typedef::strong_typedef;
};

次に、627 という事実を使用できます。 変数は、一意の ID を生成するためにテンプレートのインスタンス化ごとに異なります:

extern std::uint64_t next_id;

template <typename T>
type_id_t type_id_impl() noexcept
{
    static_assert(std::is_class_v<T> || std::is_fundamental_v<T>);
    static_assert(!std::is_const_v<T> && !std::is_volatile_v<T>);
    static auto result = type_id_t(++next_id);
    return result;
}

template <typename T>
const type_id_t type_id =
        type_id_impl<std::remove_cv_t<std::remove_pointer_t<std::decay_t<T>>>>();

新しいタイプでインスタンス化するたびに、カウンターが 1 つ増え、新しい ID が取得されます。

これで TI は解決されますが、RTTI はまだありません。そのために 632 を使用できます。 再び機能:

class rtti_base
{
protected:
    ~rtti_base() = default;

private:
    virtual type_id_t do_get_id() const noexcept = 0;

    template <typename T>
    friend type_id_t runtime_type_id(const T& obj);
};

#define MAKE_RTTI \
    type_id_t do_get_id() const noexcept override \
    {                                             \
        return type_id<decltype(*this)>;          \
    }

RTTI を提供するには、645 から継承する必要があります 653 を入れます クラスのプライベート部分のマクロ。

最後の部分は、オブジェクトからタイプ ID を取得する関数です:

template <typename T>
type_id_t runtime_type_id(const T& obj)
{
    if constexpr (std::is_final_v<T>)
          return type_id<T>;
    else if constexpr (std::is_base_of_v<rtti_base, T>)
          return static_cast<const rtti_base&>(obj).do_get_id();
    else
          return type_id<T>;
}

これは 667 と同様に機能します 関数:最終的なものであるか、RTTI を提供しない場合は、静的型情報を返します。それ以外の場合は、仮想関数を使用してランタイム情報を取得します。

このアプローチは RTTI を使用しませんが、エラーが発生しやすくなります。さらに、676 を使用すると 階層のベースで実行する必要があります。それ以外の場合は 681 再び機能しません。