cli.h

/*
 * Copyright (c) 2020 Raspberry Pi (Trading) Ltd.
 *
 * SPDX-License-Identifier: BSD-3-Clause
 */

#ifndef _CLI_H
#define _CLI_H

#include <algorithm>
#include <exception>
#include <functional>
#include <map>
#include <memory>
#include <string>
#include <vector>
#include <cassert>
#include <iostream>
#include <numeric>
#include <sstream>
#include <limits>
#include <cstdint>
#include <iterator>

/**
 * Note this is a hastily hacked together command line parser.
 *
 * I like the syntax of clipp; but it seemed really buggy, and writing something less functional
 * with similar syntax seemed like the quickest way to go.
 *
 * Ironically this is probably just as buggy off the happy path as clipp appeared to be, but
 * in this case the happy path is ours!
 */
namespace cli {

    typedef std::string string;
    template<typename T> using vector = std::vector<T>;
    template<typename A, typename B> using map = std::map<A, B>;
    template<typename A, typename B> using pair = std::pair<A, B>;
    template<typename T> using shared_ptr = std::shared_ptr<T>;

    auto join = [](const vector<string> &range, const string &separator) {
        if (range.empty()) return string();

        return accumulate(
                next(begin(range)), // there is at least 1 element, so OK.
                end(range),

                range[0], // the initial value

                [&separator](auto result, const auto &value) {
                    return result + separator + value;
                });
    };

    struct parse_error : public std::exception {
        explicit parse_error(string what) : _what(std::move(what)) {}

        const char *what() const noexcept override {
            return _what.c_str();
        }

    private:
        string _what;
    };

    struct group;
    template<typename T>
    struct matchable_derived;

    template <typename K, typename V> struct map_and_order {
        map<K,V> _map;
        vector<K> _order;

        V& operator[](const K& key) {
            auto i = _map.find(key);
            if (i == _map.end()) {
                _order.push_back(key);
            }
            return _map[key];
        }

        vector<K> ordered_keys() {
            return _order;
        }
    };

    struct option_map {
        typedef map_and_order<string, map_and_order<string, vector<pair<string, string>>>> container;

        void add(const string& major_group, const string& minor_group, const string& option, const string& description) {
            auto &v = contents[major_group][minor_group];
            // we don't want to repeat the same option
            if (std::find_if(v.begin(), v.end(), [&](const auto &x) { return x.first == option; }) == v.end()) {
                v.emplace_back(option, description);
            }
        }

        container contents;
    };

    struct matchable;

    enum struct match_type {
        not_yet,
        match,
        error,
        no_match,
    };

    struct opaque_settings {
        virtual shared_ptr<opaque_settings> copy() = 0;
        virtual void save_into() = 0;
        virtual void apply_from() = 0;
    };

    struct settings_holder {
        explicit settings_holder(shared_ptr<opaque_settings> settings) : settings(settings) {}
        settings_holder(const settings_holder &other) {
            settings = other.settings->copy();
        }
        settings_holder& operator=(const settings_holder&) = default;
        void save_into() {
            settings->save_into();
        }
        void apply_from() {
            settings->apply_from();
        }
        shared_ptr<opaque_settings> settings;
    };

    struct match_state {
        vector<string> remaining_args;
        string error_message;
        int match_count = 0;
        int error_count = 0;
        // if we are an error for something mising; we should rather report on an up next
        // unsupported option than our error message
        bool prefer_unknown_option_message = false;
        std::map<const matchable *, int> matchable_counts;
        settings_holder settings;

        match_state(const settings_holder& settings) : settings(settings) {}

        void apply_settings_from() {
            settings.apply_from();
        }
        void save_settings_into() {
            settings.save_into();
        }

        match_type match_value(const matchable *matchable, std::function<bool(const string&)> filter);

        match_type check_min_max(const matchable *matchable);

        int get_match_count(const std::shared_ptr<matchable>& element) {
            return matchable_counts[element.get()];
        }

        match_type update_stats(match_type type, const matchable *matchable) {
            assert(type != match_type::not_yet);
            if (type == match_type::match) {
                match_count++;
                matchable_counts[matchable]++;
            } else if (type == match_type::error) {
                error_count++;
                matchable_counts[matchable]++;
            }
            return type;
        }

        match_type match_if_equal(const matchable *matchable, const string& s);
    };

    struct matcher {
    };

    struct matchable {
        matchable() = default;
        virtual ~matchable() = default;

        explicit matchable(string name) : _name(std::move(name)) {}

        std::function<string(string)> action = [](const string&) { return ""; };

        std::function<string()> missing;

        virtual match_type match(match_state& m) const { return match_type::no_match; }

        string name() const {
            return _name;
        }

        virtual std::vector<string> synopsys() const {
            return {_name};
        }

        virtual string option_label() const {
            return synopsys()[0];
        }

        virtual bool is_optional() const {
            return !_min;
        }

        bool doc_non_optional() const {
            return _doc_non_optional;
        }

        bool synopsis_non_optional() const {
            return _synopsis_non_optional;
        }

        bool force_expand_help() const {
            return _force_expand_help;
        }

        string collapse_synopsys() const {
            return _collapse_synopsys;
        }

        string doc() const {
            return _doc;
        }

        virtual bool get_option_help(string major_group, string minor_group, option_map &options) const {
            return false;
        }

        int min() const {
            return _min;
        }

        int max() const {
            return _max;
        }

    protected:
        string _name;
        string _doc;
        int _min = 1;
        int _max = 1;
        bool _doc_non_optional = false;
        bool _synopsis_non_optional = false;
        bool _force_expand_help = false;
        string _collapse_synopsys = "";
    };

    template<typename D>
    struct matchable_derived : public matchable {
        matchable_derived() = default;
        explicit matchable_derived(string name) : matchable(std::move(name)) {}

        D &on_action(std::function<string(const string&)> action) {
            this->action = action;
            return *static_cast<D *>(this);
        }

        D &if_missing(std::function<string()> missing) {
            this->missing = missing;
            return *static_cast<D *>(this);
        }

        D &operator%(const string& doc) {
            _doc = doc;
            return *static_cast<D *>(this);
        }

        D &required() {
            _min = 1;
            _max = std::max(_min, _max);
            return *static_cast<D *>(this);
        }

        D &repeatable() {
            _max = std::numeric_limits<int>::max();
            return *static_cast<D *>(this);
        }

        D &min(int v) {
            _min = v;
            return *static_cast<D *>(this);
        }

        D &doc_non_optional(bool v) {
            _doc_non_optional = v;
            return *static_cast<D *>(this);
        }

        D &synopsis_non_optional(bool v) {
            _synopsis_non_optional = v;
            return *static_cast<D *>(this);
        }

        D &force_expand_help(bool v) {
            _force_expand_help = v;
            return *static_cast<D *>(this);
        }

        D &collapse_synopsys(string v) {
            _collapse_synopsys = v;
            return *static_cast<D *>(this);
        }

        D &max(int v) {
            _max = v;
            return *static_cast<D *>(this);
        }
        std::shared_ptr<matchable> to_ptr() const {
            return std::shared_ptr<matchable>(new D(*static_cast<const D *>(this)));
        }

        template<typename T>
        group operator&(const matchable_derived<T> &m);
        template<typename T>
        group operator|(const matchable_derived<T> &m);
        template<typename T>
        group operator+(const matchable_derived<T> &m);
    };

    template<typename D>
    struct value_base : public matchable_derived<D> {
        std::function<bool(const string&)> exclusion_filter = [](const string &x){return false;};

        explicit value_base(string name) : matchable_derived<D>(std::move(name)) {
            this->_min = 1;
            this->_max = 1;
        }

        vector<string> synopsys() const override {
            string s = string("<") + this->_name + ">";
            if (this->_max > 1) s += "..";
            return {s};
        }

        bool get_option_help(string major_group, string minor_group, option_map &options) const override {
            if (this->doc().empty()) {
                return false;
            }
            options.add(major_group, minor_group, string("<") + this->_name + ">", this->doc());
            return true;
        }

        match_type match(match_state& ms) const override {
            match_type rc = ms.check_min_max(this);
            if (rc == match_type::not_yet) {
                rc = ms.match_value(this, exclusion_filter);
            }
            return rc;
        }

        D &with_exclusion_filter(std::function<bool(const string&)> exclusion_filter) {
            this->exclusion_filter = exclusion_filter;
            return *static_cast<D *>(this);
        }
    };

    struct option : public matchable_derived<option> {
        explicit option(char short_opt) : option(short_opt, "") {}

        explicit option(string _long_opt) : option(0, std::move(_long_opt)) {}

        option(char _short_opt, string _long_opt) {
            _min = 0;
            short_opt = _short_opt ? "-" + string(1, _short_opt) : "";
            long_opt = std::move(_long_opt);
            _name = short_opt.empty() ? long_opt : short_opt;
        }

        string option_label() const override {
            string label = short_opt.empty() ? "" : _name;
            if (!long_opt.empty()) {
                if (!label.empty()) label += ", ";
                label += long_opt;
            }
            return label;
        }

        bool get_option_help(string major_group, string minor_group, option_map &options) const override {
            if (doc().empty()) return false;
            options.add(major_group, minor_group, option_label(), doc());
            return true;
        }

        template<typename T>
        option &set(T &t) {
            // note we cannot capture "this"
            on_action([&t](const string& value) {
                t = true;
                return "";
            });
            return *this;
        }

        template<typename T>
        option &clear(T &t) {
            // note we cannot capture "this"
            on_action([&t](const string& value) {
                t = false;
                return "";
            });
            return *this;
        }

        match_type match(match_state &ms) const override {
            match_type rc = ms.match_if_equal(this, short_opt);
            if (rc == match_type::no_match) {
                rc = ms.match_if_equal(this, long_opt);
            }
            return rc;
        }

    private:
        string short_opt;
        string long_opt;
    };

    struct value : public value_base<value> {
        explicit value(string name) : value_base(std::move(name)) {}

        template<typename T>
        value &set(T &t) {
            on_action([&](const string& value) {
                t = value;
                return "";
            });
            return *this;
        }
        template<typename T> value &add_to(T &t) {
            // note we cannot capture "this"
            on_action([&t](const string& value) {
                t.push_back(value);
                return "";
            });
            return *this;
        }
    };

    // Number format policies for integer_base; they say how a value is parsed, and how
    // values are worded/rendered in error messages
    struct integer_format {
        static constexpr int64_t radix = 0; // 0 means work the base out from the 0x/0b prefix
        static constexpr uint64_t value_mask = std::numeric_limits<uint64_t>::max();
        static const char *name() { return "integer"; }
        static const char *too_big_error() { return " is too big"; }
        static string format(int64_t value) { return std::to_string(value); }
    };

    struct hex_format {
        static constexpr int64_t radix = 16; // always base 16; an 0x prefix is optional
        static constexpr uint64_t value_mask = 0xffffffffu; // 32 bit values only
        static const char *name() { return "hex value"; }
        static const char *too_big_error() { return " is not a valid 32 bit value"; }
        static string format(int64_t value) {
            std::stringstream ss;
            ss << "0x" << std::hex << value;
            return ss.str();
        }
    };

    // Shared implementation for numeric values; D is the derived type (e.g. integer, hex),
    // and FORMAT is one of the number format policies above
    template<typename D, typename FORMAT = integer_format>
    struct integer_base : public value_base<D> {
        explicit integer_base(string name) : value_base<D>(std::move(name)) {}

        // comparisons against a limit which do the right thing whether T is signed or not
        template<typename T>
        static bool less_than(T value, int64_t limit) {
            if (std::is_signed<T>()) return (int64_t)value < limit;
            else return limit > 0 && (uint64_t)value < (uint64_t)limit;
        }

        template<typename T>
        static bool greater_than(T value, int64_t limit) {
            if (std::is_signed<T>()) return (int64_t)value > limit;
            else return limit < 0 || (uint64_t)value > (uint64_t)limit;
        }

        // is the parsed value representable in the target type?
        template<typename T>
        static bool fits(uint64_t lvalue) {
            if (std::is_signed<T>()) {
                return (int64_t)lvalue >= (int64_t)std::numeric_limits<T>::min() &&
                       (int64_t)lvalue <= (int64_t)std::numeric_limits<T>::max();
            } else {
                return lvalue <= (uint64_t)std::numeric_limits<T>::max();
            }
        }

        template<typename T>
        static std::string parse_string(std::string value, T& out) {
            auto ovalue = value;
            if (!std::is_signed<T>() && value.find('-') == 0) {
                // stoull would silently wrap this round
                return ovalue + " must not be negative";
            }
            int64_t base = FORMAT::radix;
            if ((!base || base == 16) && value.find("0x") == 0) {
                value = value.substr(2);
                base = 16;
            } else if ((!base || base == 2) && value.find("0b") == 0) {
                value = value.substr(2);
                base = 2;
            }
            if (!base) base = 10;
            size_t pos = 0;
            uint64_t lvalue = std::numeric_limits<uint64_t>::max();
            try {
                if (std::is_signed<T>()) {
                    lvalue = std::stoll(value, &pos, base);
                } else {
                    lvalue = std::stoull(value, &pos, base);
                }
                if (pos != value.length()) {
                    return string("Garbage after ") + FORMAT::name() + ": " + value.substr(pos);
                }
            } catch (std::invalid_argument&) {
                return ovalue + " is not a valid " + FORMAT::name();
            } catch (std::out_of_range&) {
                return ovalue + " is out of range";
            }
            if ((lvalue & ~FORMAT::value_mask) || !fits<T>(lvalue)) {
                return ovalue + FORMAT::too_big_error();
            }
            out = (T)lvalue;
            return "";
        }

        // the bounds to check a parsed value against; copied into the action lambda, as we
        // cannot capture "this"
        struct bounds {
            int64_t min;
            int64_t max;
            bool has_max; // if not, the target type's own range is the only upper bound
            int64_t invalid_bits;
            string invalid_bits_error;
            string nm;

            template<typename T>
            std::string check(T value) const {
                if (less_than(value, min)) {
                    return nm + " must be >= " + FORMAT::format(min);
                }
                if (has_max && greater_than(value, max)) {
                    return nm + " must be <= " + FORMAT::format(max);
                }
                if ((uint64_t)value & (uint64_t)invalid_bits) {
                    return nm + " " + invalid_bits_error;
                }
                return "";
            }
        };

        template<typename T>
        D &set(T &t) {
            bounds b = get_bounds();
            // note we cannot capture "this"
            this->on_action([&t, b](const string& value) {
                T tmp = 0;
                std::string err = parse_string(value, tmp);
                t = tmp;
                if (!err.empty()) return err;
                return b.check(tmp);
            });
            return *static_cast<D *>(this);
        }

        template<typename T>
        D &add_to(T &t) {
            bounds b = get_bounds();
            // note we cannot capture "this"
            this->on_action([&t, b](const string& value) {
                typename T::value_type tmp = 0;
                std::string err = parse_string(value, tmp);
                if (!err.empty()) return err;
                err = b.check(tmp);
                if (!err.empty()) return err;
                t.push_back(tmp);
                return string("");
            });
            return *static_cast<D *>(this);
        }

        D& min_value(int64_t v) {
            _min_value = v;
            return *static_cast<D *>(this);
        }

        D& max_value(int64_t v) {
            _max_value = v;
            _has_max_value = true;
            return *static_cast<D *>(this);
        }

        D& invalid_bits(int64_t bits, std::string error) {
            _invalid_bits = bits;
            _invalid_bits_error = error;
            return *static_cast<D *>(this);
        }

        int64_t _min_value = 0;
        int64_t _max_value = std::numeric_limits<int64_t>::max();
        bool _has_max_value = false;
        std::string _invalid_bits_error;
        int64_t _invalid_bits = 0;

    private:
        bounds get_bounds() const {
            return bounds{_min_value, _max_value, _has_max_value, _invalid_bits,
                          _invalid_bits_error, "<" + this->name() + ">"};
        }
    };

    struct integer : public integer_base<integer> {
        explicit integer(string name) : integer_base(std::move(name)) {}
    };

    struct hex : public integer_base<hex, hex_format> {
        explicit hex(string name) : integer_base(std::move(name)) {}
    };

    struct group : public matchable_derived<group> {
        enum group_type {
            sequence,
            set,
            exclusive,
            collapse,
        };

    public:
        group() : type(set) {}

        template<typename T>
        explicit group(const T &t) : type(set), elements{t.to_ptr()} {}

        template<class Matchable, class... Matchables>
        group(Matchable m, Matchable ms...) : type(set), elements{m, ms} {}

        group &set_type(group_type t) {
            type = t;
            return *this;
        }

        group &major_group(string g) {
            _major_group = std::move(g);
            return *this;
        }

        // Instead of expanding this group's options in place, point the reader at
        // "picotool help <topic>" for the details (see the "help_topic" command dispatch).
        group &help_topic(string topic) {
            _help_topic = std::move(topic);
            return *this;
        }

        static string decorate(const matchable &e, string s) {
            if (e.is_optional() && !e.doc_non_optional() && !e.synopsis_non_optional()) {
                return string("[") + s + "]";
            } else {
                return s;
            }
        }

        string option_label() const override {
            if (type != set && type != sequence) {
                return matchable::option_label();
            }
            vector<string> parts;
            for (auto &x : elements) {
                parts.push_back(decorate(*x, x->option_label()));
            }
            return join(parts, " ");
        }

        vector<string> synopsys() const override {
            vector<string> rc;
            switch (type) {
                case set:
                case sequence: {
                    std::vector<std::vector<string>> tmp{{}};
                    if (_collapse_synopsys.empty()) {
                        for (auto &x : elements) {
                            auto xs = x->synopsys();
                            if (xs.size() == 1) {
                                for (auto &s : tmp) {
                                    s.push_back(decorate(*x, xs[0]));
                                }
                            } else {
                                auto save = tmp;
                                tmp.clear();
                                for (auto &v : save) {
                                    for (auto &s : xs) {
                                        auto nv = v;
                                        nv.push_back(decorate(*x, s));
                                        tmp.push_back(nv);
                                    }
                                }
                            }
                        }
                    } else {
                        std::vector<std::string> xs = {"[" + _collapse_synopsys + "]"};
                        for (auto &s : tmp) {
                            s.push_back(xs[0]);
                        }
                    }
                    for (const auto &v : tmp) {
                        rc.push_back(join(v, " "));
                    }
                    break;
                }
                case exclusive:
                    for (auto &x : elements) {
                        auto xs = x->synopsys();
                        std::transform(xs.begin(), xs.end(), std::back_inserter(rc), [&](const auto &s) {
                            return decorate(*x, s);
                        });
                    }
                    break;
                default:
                    assert(false);
                    break;
            }
            return rc;
        }

//        group operator|(const group &g) {
//            return matchable_derived::operator|(g);
//        }
//
//        group operator&(const group &g) {
//            return matchable_derived::operator&(g);
//        }
//
//        group operator+(const group &g) {
//            return matchable_derived::operator+(g);
//        }

        bool no_match_beats_error() const {
            return _no_match_beats_error;
        }

        group &no_match_beats_error(bool v) {
            _no_match_beats_error = v;
            return *this;
        }

        template<typename T>
        group operator&(const matchable_derived<T> &m) {
            if (type == sequence) {
                elements.push_back(m.to_ptr());
                return *this;
            }
            return matchable_derived::operator&(m);
        }

        template<typename T>
        group operator|(const matchable_derived<T> &m) {
            if (type == exclusive) {
                elements.push_back(m.to_ptr());
                return *this;
            }
            return matchable_derived::operator|(m);
        }

        template<typename T>
        group operator+(const matchable_derived<T> &m) {
            if (type == set) {
                elements.push_back(m.to_ptr());
                return *this;
            }
            return matchable_derived::operator+(m);
        }

        bool get_option_help(string major_group, string minor_group, option_map &options) const override {
            // todo beware.. this check is necessary as is, but I'm not sure what removing it breaks in terms of formatting  :-(
            if (is_optional() && !this->_doc_non_optional && !this->_force_expand_help) {
                options.add(major_group, minor_group, option_label(), doc());
                return true;
            }
            if (!doc().empty()) {
                minor_group = doc();
            }
            if (!_major_group.empty()) {
                major_group = _major_group;
            }
            if (!_help_topic.empty() && !this->_force_expand_help) {
                options.add(major_group, minor_group, "", "See \"picotool help " + _help_topic + "\" for available options");
                return true;
            }
            for (const auto &e : elements) {
                e->get_option_help(major_group, minor_group, options);
            }
            return true;
        }

        match_type match(match_state& ms) const override {
            match_type rc = ms.check_min_max(this);
            if (rc == match_type::no_match) return rc;
            assert(rc == match_type::not_yet);
            switch(type) {
                case sequence:
                    rc = match_sequence(ms);
                    break;
                case set:
                    rc = match_set(ms);
                    break;
                default:
                    rc = match_exclusive(ms);
                    break;
            }
            return ms.update_stats(rc, this);
        }

        match_type match_sequence(match_state& ms) const {
            match_type rc = match_type::no_match;
            for(const auto& e : elements) {
                rc = e->match(ms);
                assert(rc != match_type::not_yet);
                if (rc != match_type::match) {
                    break;
                }
            }
            return rc;
        }

        match_type match_set(match_state& ms) const {
            // because of repeatability, we keep matching until there is nothing left to match
//            vector<match_type> types(elements.size(), match_type::not_yet);
            bool had_any_matches = false;
            bool final_pass = false;
            do {
                bool matches_this_time = false;
                bool errors_this_time = false;
                bool not_min_this_time = false;
                for (size_t i=0;i<elements.size();i++) {
//                    if (types[i] == match_type::not_yet) {
                        auto ms_prime = ms;
                        ms_prime.apply_settings_from();
                        match_type t = elements[i]->match(ms_prime);
                        assert(t != match_type::not_yet);
                        if (t == match_type::match) {
                            // we got a match, so record in ms and try again
                            // (if the matchable isn't repeatable it will no match next time)
//                            types[i] = match_type::not_yet;
                            ms_prime.save_settings_into();
                            ms = ms_prime;
                            had_any_matches = true;
                            matches_this_time = true;
                        } else if (t == match_type::error) {
                            if (final_pass) {
                                ms_prime.save_settings_into();
                                ms = ms_prime;
                                return t;
                            }
                            errors_this_time = true;
                        } else {
                            if (ms.get_match_count(elements[i]) < elements[i]->min()) {
                                if (final_pass) {
                                    ms.error_message = elements[i]->missing ? elements[i]->missing() : "missing required argument";
                                    return match_type::error;
                                }
                                not_min_this_time = true;
                            }
                        }
//                    }
                }
                if (final_pass) break;
                if (!matches_this_time) {
                    if (errors_this_time || not_min_this_time) {
                        final_pass = true;
                    } else {
                        break;
                    }
                }
            } while (true);
            return had_any_matches ? match_type::match : match_type::no_match;
        }

        match_type match_exclusive(match_state& ms) const {
            vector<match_state> matches(elements.size(), ms);
            vector<match_type> types(elements.size(), match_type::no_match);
            int elements_with_errors = 0;
            int elements_with_no_match = 0;
            int error_at = -1;
            int error_match_count = -1;
            for (size_t i=0;i<elements.size();i++) {
                match_type t;
                matches[i].apply_settings_from();
                do {
                    t = elements[i]->match(matches[i]);
                    assert(t != match_type::not_yet);
                    if (t != match_type::no_match) {
                        types[i] = t;
                    }
                } while (t == match_type::match);
                matches[i].save_settings_into();
                if (types[i] == match_type::match) {
                    ms = matches[i];
                    return match_type::match;
                } else if (types[i] == match_type::error) {
                    if (matches[i].match_count > error_match_count) {
                        error_match_count = matches[i].match_count;
                        error_at = i;
                    }
                    elements_with_errors++;
                } else if (types[i] == match_type::no_match) {
                    elements_with_no_match++;
                }
            }
            if (elements_with_no_match && (!elements_with_errors || no_match_beats_error())) {
                return match_type::no_match;
            }
            if (elements_with_errors) {
                ms = matches[error_at];
                ms.apply_settings_from(); // todo perhaps want to apply the previous settings instead?
                return match_type::error;
            } else {
                // back out any modified settings
                ms.apply_settings_from();
                return match_type::no_match;
            }
        }

    private:
        string _major_group;
        string _help_topic;
        group_type type;
        vector<std::shared_ptr<matchable>> elements;
        bool _no_match_beats_error = true;
    };

    template<typename D>
    template<typename T>
    group matchable_derived<D>::operator|(const matchable_derived<T> &m) {
        return group{this->to_ptr(), m.to_ptr()}.set_type(group::exclusive);
    }

    template<typename D>
    template<typename T>
    group matchable_derived<D>::operator&(const matchable_derived<T> &m) {
        int _min = matchable::min();
        int _max = matchable::max();
        min(1);
        max(1);
        return group{this->to_ptr(), m.to_ptr()}.set_type(group::sequence).min(_min).max(_max);
    }

    template<typename D>
    template<typename T>
    group matchable_derived<D>::operator+(const matchable_derived<T> &m) {
        return group{this->to_ptr(), m.to_ptr()};
    }

    vector<string> make_args(int argc, char **argv) {
        vector<string> args;
        for (int i = 1; i < argc; i++) {
            string arg(argv[i]);
            if (arg.length() > 2 && arg[0] == '-' && arg[1] != '-') {
                // expand collapsed args (unconditionally for now)
                for (auto c = arg.begin() + 1; c != arg.end(); c++) {
                    args.push_back("-" + string(1, *c));
                }
            } else {
                args.push_back(arg);
            }
        }
        return args;
    }

    match_type match_state::check_min_max(const matchable *matchable) {
        if (matchable_counts[matchable] < matchable->min()) {
            return match_type::not_yet;
        }
        if (matchable_counts[matchable] >= matchable->max()) {
            return match_type::no_match;
        }
        return match_type::not_yet;
    }

    match_type match_state::match_if_equal(const matchable *matchable, const string& s) {
        if (remaining_args.empty()) return match_type::no_match;
        if (remaining_args[0] == s) {
            auto message = matchable->action(s);
            assert(message.empty());
            remaining_args.erase(remaining_args.begin());
            return update_stats(match_type::match, matchable);
        }
        return match_type::no_match;
    }

    match_type match_state::match_value(const matchable *matchable, std::function<bool(const string&)> exclusion_filter) {
        // treat an excluded value as missing
        bool empty = remaining_args.empty() || exclusion_filter(remaining_args[0]);
        if (empty) {
            if (matchable_counts[matchable] < matchable->min()) {
                prefer_unknown_option_message = !remaining_args.empty();
                error_message = matchable->missing ? matchable->missing() : "missing <" + matchable->name() +">";
                return update_stats(match_type::error, matchable);
            }
            return match_type::no_match;
        }
        auto message = matchable->action(remaining_args[0]);
        if (!message.empty()) {
            error_message = message;
            return update_stats(match_type::error, matchable);
        }
        remaining_args.erase(remaining_args.begin());
        return update_stats(match_type::match, matchable);
    }

    template<typename S> struct typed_settings final : public opaque_settings {
        explicit typed_settings(S& settings) : root_settings(settings), settings(settings) {
        }

        shared_ptr<cli::opaque_settings> copy() override {
            auto c = std::make_shared<typed_settings<S>>(*this);
            c->settings = settings;
            return c;
        }

        void save_into() override {
            settings = root_settings;
        }

        void apply_from() override {
            root_settings = settings;
        }

        S& root_settings;
        S settings;
    };

    template<typename S> void match(S& settings, const group& g, std::vector<string> args) {
        auto holder = settings_holder(std::make_shared<typed_settings<S>>(settings));
        match_state ms(holder);
        ms.remaining_args = std::move(args);
        auto t = g.match(ms);
        if (!ms.prefer_unknown_option_message) {
            if (t == match_type::error) {
                throw parse_error(ms.error_message);
            }
        }
        if (!ms.remaining_args.empty()) {
            if (ms.remaining_args[0].find('-')==0) {
                throw parse_error("unexpected option: "+ms.remaining_args[0]);
            } else {
                throw parse_error("unexpected argument: "+ms.remaining_args[0]);
            }
        }
        if (ms.prefer_unknown_option_message) {
            if (t == match_type::error) {
                throw parse_error(ms.error_message);
            }
        }
    }
}

#endif