text:
#ifndef TIGHTDB_COLUMN_HPP
#define TIGHTDB_COLUMN_HPP

#include <stdint.h> // unint8_t etc
#include <cstdlib> // std::size_t

#include <tightdb/util/unique_ptr.hpp>
#include <tightdb/array.hpp>
#include <tightdb/column_type.hpp>
#include <tightdb/spec.hpp>
#include <tightdb/impl/output_stream.hpp>
#include <tightdb/query_conditions.hpp>

namespace tightdb {

// Pre-definitions
class Column;

struct ColumnTemplateBase
{
    virtual int compare_values(size_t row1, size_t row2) const = 0;
};

template <class T> struct ColumnTemplate : public ColumnTemplateBase
{
    // Overridden in column_string.* because == operator of StringData isn't yet locale aware; todo
    virtual int compare_values(size_t row1, size_t row2) const
    {
        T a = get_val(row1);
        T b = get_val(row2);
        return a == b ? 0 : a < b ? 1 : -1;
    }

    // We cannot use already-existing get() methods because ColumnStringEnum and LinkList inherit from
    // Column and overload get() with different return type than int64_t. Todo, find a way to simplify
    virtual T get_val(size_t row) const = 0;
};

/// Base class for all column types.
class ColumnBase {
public:
    /// Get the number of entries in this column. This operation is relatively
    /// slow.
    std::size_t size() const TIGHTDB_NOEXCEPT;

    /// \throw LogicError Thrown if this column is not string valued.
    virtual void set_string(std::size_t row_ndx, StringData value);

    /// Insert the specified number of default values into this column starting
    /// at the specified row index. Set `is_append` to true if, and only if
    /// `row_ndx` is equal to the size of the column (before insertion).
    virtual void insert(std::size_t row_ndx, std::size_t num_rows, bool is_append) = 0;

    /// Remove all entries from this column.
    virtual void clear() = 0;

    /// Remove the specified entry from this column. Set \a is_last to
    /// true when deleting the last element. This is important to
    /// avoid conversion to to general form of inner nodes of the
    /// B+-tree.
    virtual void erase(std::size_t ndx, bool is_last) = 0;

    /// Move the last element to the specified target index. This reduces the
    /// number of elements by one. The specified last row index must always be
    /// one less than the number of rows in the column. The target index must
    /// always be strictly less that the last index.
    virtual void move_last_over(std::size_t target_row_ndx, std::size_t last_row_ndx) = 0;

    virtual bool IsIntColumn() const TIGHTDB_NOEXCEPT { return false; }

    // Returns true if, and only if this column is an AdaptiveStringColumn.
    virtual bool is_string_col() const TIGHTDB_NOEXCEPT;

    virtual void destroy() TIGHTDB_NOEXCEPT;

    virtual ~ColumnBase() TIGHTDB_NOEXCEPT {};

    // Search index
    virtual bool has_search_index() const TIGHTDB_NOEXCEPT;
    virtual void set_search_index_ref(ref_type, ArrayParent*, std::size_t ndx_in_parent,
                                      bool allow_duplicate_values);
    virtual void set_search_index_allow_duplicate_values(bool) TIGHTDB_NOEXCEPT;

    Allocator& get_alloc() const TIGHTDB_NOEXCEPT { return m_array->get_alloc(); }

    /// Returns the 'ref' of the root array.
    ref_type get_ref() const TIGHTDB_NOEXCEPT { return m_array->get_ref(); }

    //@{
    /// Returns the array node at the root of this column, but note
    /// that there is no guarantee that this node is an inner B+-tree
    /// node or a leaf. This is the case for a MixedColumn in
    /// particular.
    Array* get_root_array() TIGHTDB_NOEXCEPT { return m_array; }
    const Array* get_root_array() const TIGHTDB_NOEXCEPT { return m_array; }
    //@}

    /// Provides access to the leaf that contains the element at the
    /// specified index. Upon return \a ndx_in_leaf will be set to the
    /// corresponding index relative to the beginning of the leaf.
    ///
    /// When the root is a leaf, this function returns a pointer to
    /// the array accessor cached inside this column
    /// accessor. Otherwise this function attaches the specified
    /// fallback accessor to the identified leaf, and returns a
    /// pointer to the fallback accessor.
    ///
    /// This function cannot be used for modifying operations as it
    /// does not ensure the presence of an unbroken chain of parent
    /// accessors. For this reason, the identified leaf should always
    /// be accessed through the returned const-qualified reference,
    /// and never directly through the specfied fallback accessor.
    const Array& get_leaf(std::size_t ndx, std::size_t& ndx_in_leaf,
                          Array& fallback) const TIGHTDB_NOEXCEPT;

    // FIXME: Is almost identical to get_leaf(), but uses ill-defined
    // aspects of the Array API. Should be eliminated.
    const Array* GetBlock(std::size_t ndx, Array& arr, std::size_t& off,
                          bool use_retval = false) const TIGHTDB_NOEXCEPT;

    inline void detach(void);
    inline bool is_attached(void) const TIGHTDB_NOEXCEPT;

    static std::size_t get_size_from_type_and_ref(ColumnType, ref_type, Allocator&) TIGHTDB_NOEXCEPT;

    // These assume that the right column compile-time type has been
    // figured out.
    static std::size_t get_size_from_ref(ref_type root_ref, Allocator&);
    static std::size_t get_size_from_ref(ref_type spec_ref, ref_type columns_ref, Allocator&);

    /// Write a slice of this column to the specified output stream.
    virtual ref_type write(std::size_t slice_offset, std::size_t slice_size,
                           std::size_t table_size, _impl::OutputStream&) const = 0;

    void set_parent(ArrayParent*, std::size_t ndx_in_parent) TIGHTDB_NOEXCEPT;

    /// Called in the context of Group::commit() and
    /// SharedGroup::commit_and_continue_as_read()() to ensure that attached
    /// table and link list accessors stay valid across a commit.
    virtual void update_from_parent(std::size_t old_baseline) TIGHTDB_NOEXCEPT;

    void discard_child_accessors() TIGHTDB_NOEXCEPT;

    /// For columns that are able to contain subtables, this function returns
    /// the pointer to the subtable accessor at the specified row index if it
    /// exists, otherwise it returns null. For other column types, this function
    /// returns null.
    virtual Table* get_subtable_accessor(std::size_t row_ndx) const TIGHTDB_NOEXCEPT;

    /// Detach and remove the subtable accessor at the specified row if it
    /// exists. For column types that are unable to contain subtable, this
    /// function does nothing.
    virtual void discard_subtable_accessor(std::size_t row_ndx) TIGHTDB_NOEXCEPT;

    virtual void adj_accessors_insert_rows(std::size_t row_ndx,
                                           std::size_t num_rows) TIGHTDB_NOEXCEPT;
    virtual void adj_accessors_erase_row(std::size_t row_ndx) TIGHTDB_NOEXCEPT;

    // This function assumes that a row has moved from \a origin_ndx to \a target_ndx,
    // and it updates the column accessor, and all its subordinate accessors (subtables, rows)
    // accordingly.
    // Subordinate accessors that are already associated with \a target_ndx will be detached.
    // Link-adjacent table accessors will be marked (dirty).
    //
    // It is used as part of Table::refresh_accessor_tree() to bring the state of the accessors
    // from Minimal Consistency into Structural Correspondence, so it must be able to execute
    // without accessing the underlying array nodes.
    virtual void adj_accessors_move(std::size_t target_row_ndx,
                                    std::size_t source_row_ndx) TIGHTDB_NOEXCEPT;
    virtual void adj_acc_clear_root_table() TIGHTDB_NOEXCEPT;

    enum {
        mark_Recursive   = 0x01,
        mark_LinkTargets = 0x02,
        mark_LinkOrigins = 0x04
    };

    virtual void mark(int type) TIGHTDB_NOEXCEPT;

    virtual void bump_link_origin_table_version() TIGHTDB_NOEXCEPT;

    /// Refresh the dirty part of the accessor subtree rooted at this column
    /// accessor.
    ///
    /// The following conditions are necessary and sufficient for the proper
    /// operation of this function:
    ///
    ///  - The parent table accessor (excluding its column accessors) is in a
    ///    valid state (already refreshed).
    ///
    ///  - Every subtable accessor in the subtree is marked dirty if it needs to
    ///    be refreshed, or if it has a descendant accessor that needs to be
    ///    refreshed.
    ///
    ///  - This column accessor, as well as all its descendant accessors, are in
    ///    structural correspondence with the underlying node hierarchy whose
    ///    root ref is stored in the parent (`Table::m_columns`) (see
    ///    AccessorConsistencyLevels).
    ///
    ///  - The 'index in parent' property of the cached root array
    ///    (`m_array->m_ndx_in_parent`) is valid.
    virtual void refresh_accessor_tree(std::size_t new_col_ndx, const Spec&) = 0;

#ifdef TIGHTDB_DEBUG
    // Must be upper case to avoid conflict with macro in Objective-C
    virtual void Verify() const = 0;
    virtual void Verify(const Table&, std::size_t col_ndx) const;
    virtual void to_dot(std::ostream&, StringData title = StringData()) const = 0;
    void dump_node_structure() const; // To std::cerr (for GDB)
    virtual void do_dump_node_structure(std::ostream&, int level) const = 0;
#endif

protected:
    // FIXME: This should not be mutable, the problem is again the
    // const-violating moving copy constructor.
    mutable Array* m_array;

    ColumnBase(Array* root = 0) TIGHTDB_NOEXCEPT;

    virtual std::size_t do_get_size() const TIGHTDB_NOEXCEPT = 0;

    // Must not assume more than minimal consistency (see
    // AccessorConsistencyLevels).
    virtual void do_discard_child_accessors() TIGHTDB_NOEXCEPT {}

    //@{
    /// \tparam L Any type with an appropriate `value_type`, %size(),
    /// and %get() members.
    template<class L, class T>
    std::size_t lower_bound(const L& list, T value) const TIGHTDB_NOEXCEPT;
    template<class L, class T>
    std::size_t upper_bound(const L& list, T value) const TIGHTDB_NOEXCEPT;
    //@}

    // Node functions
    bool root_is_leaf() const TIGHTDB_NOEXCEPT { return !m_array->is_inner_bptree_node(); }

    template <class T, class R, Action action, class condition>
    R aggregate(T target, std::size_t start, std::size_t end, size_t limit = size_t(-1),
                size_t* return_ndx = null_ptr) const;

    /// Introduce a new root node which increments the height of the
    /// tree by one.
    void introduce_new_root(ref_type new_sibling_ref, Array::TreeInsertBase& state,
                            bool is_append);

    class EraseHandlerBase;

    class CreateHandler {
    public:
        virtual ref_type create_leaf(std::size_t size) = 0;
        ~CreateHandler() TIGHTDB_NOEXCEPT {}
    };

    static ref_type create(Allocator&, std::size_t size, CreateHandler&);

    class SliceHandler {
    public:
        virtual MemRef slice_leaf(MemRef leaf_mem, std::size_t offset, std::size_t size,
                                  Allocator& target_alloc) = 0;
        ~SliceHandler() TIGHTDB_NOEXCEPT {}
    };

    static ref_type write(const Array* root, std::size_t slice_offset, std::size_t slice_size,
                          std::size_t table_size, SliceHandler&, _impl::OutputStream&);

#ifdef TIGHTDB_DEBUG
    class LeafToDot;
    virtual void leaf_to_dot(MemRef, ArrayParent*, std::size_t ndx_in_parent,
                             std::ostream&) const = 0;
    void tree_to_dot(std::ostream&) const;
#endif

private:
    class WriteSliceHandler;

    static ref_type build(std::size_t* rest_size_ptr, std::size_t fixed_height,
                          Allocator&, CreateHandler&);

    friend class StringIndex;
};

class ColumnBase::EraseHandlerBase: public Array::EraseHandler {
protected:
    EraseHandlerBase(ColumnBase& column) TIGHTDB_NOEXCEPT: m_column(column) {}
    ~EraseHandlerBase() TIGHTDB_NOEXCEPT TIGHTDB_OVERRIDE {}
    Allocator& get_alloc() TIGHTDB_NOEXCEPT;
    void replace_root(Array* leaf); // Ownership passed
private:
    ColumnBase& m_column;
};

/// An integer column (Column) is a single B+-tree, and the root of
/// the column is the root of the B+-tree. All leaf nodes are single
/// arrays of type Array.
///
/// FIXME: Rename Column to IntegerColumn.
class Column: public ColumnBase, public ColumnTemplate<int64_t> {
public:
    typedef int64_t value_type;

    int64_t get_val(size_t row) const { return get(row); }

    Column(Allocator&, ref_type);
    inline bool has_search_index() const TIGHTDB_NOEXCEPT;
    struct unattached_root_tag {};
    Column(unattached_root_tag, Allocator&);

    struct move_tag {};
    Column(move_tag, Column&) TIGHTDB_NOEXCEPT;

    ~Column() TIGHTDB_NOEXCEPT TIGHTDB_OVERRIDE;
    void destroy() TIGHTDB_NOEXCEPT;
    void move_assign(Column&);
    bool IsIntColumn() const TIGHTDB_NOEXCEPT { return true; }

    std::size_t size() const TIGHTDB_NOEXCEPT;
    bool is_empty() const TIGHTDB_NOEXCEPT { return size() == 0; }

    // Getting and setting values
    int_fast64_t get(std::size_t ndx) const TIGHTDB_NOEXCEPT;
    ref_type get_as_ref(std::size_t ndx) const TIGHTDB_NOEXCEPT;
    int_fast64_t back() const TIGHTDB_NOEXCEPT { return get(size()-1); }
    void set(std::size_t ndx, int_fast64_t value);
    void adjust(std::size_t ndx, int_fast64_t diff);
    void add(int_fast64_t value = 0);
    void insert(std::size_t ndx, int_fast64_t value = 0);

    std::size_t count(int64_t target) const;
    int64_t sum(std::size_t start = 0, std::size_t end = -1, size_t limit = size_t(-1),
                size_t* return_ndx = null_ptr) const;

    int64_t maximum(std::size_t start = 0, std::size_t end = -1, size_t limit = size_t(-1),
                    size_t* return_ndx = null_ptr) const;

    int64_t minimum(std::size_t start = 0, std::size_t end = -1, size_t limit = size_t(-1),
                    size_t* return_ndx = null_ptr) const;

    double  average(std::size_t start = 0, std::size_t end = -1, size_t limit = size_t(-1),
                    size_t* return_ndx = null_ptr) const;

    /// If any element points to an array node, this function recursively
    /// destroys that array node. Note that the same is **not** true for
    /// Column::erase() and Column::move_last_over().
    ///
    /// FIXME: Be careful, clear() currently forgets if the leaf type is
    /// Array::type_HasRefs.
    void clear() TIGHTDB_OVERRIDE;

    void insert(std::size_t, std::size_t, bool) TIGHTDB_OVERRIDE;
    void erase(std::size_t ndx, bool is_last) TIGHTDB_OVERRIDE;
    void move_last_over(std::size_t, std::size_t) TIGHTDB_OVERRIDE;
    void destroy_subtree(size_t ndx, bool clear_value);

    void adjust(int_fast64_t diff);
    void adjust_ge(int_fast64_t limit, int_fast64_t diff);

    size_t find_first(int64_t value, std::size_t begin = 0, std::size_t end = npos) const;
    void find_all(Column& result, int64_t value,
                  std::size_t begin = 0, std::size_t end = npos) const;

    void set_search_index_ref(ref_type ref, ArrayParent* parent, size_t ndx_in_parent, bool allow_duplicate_valaues);
    void create_search_index();
    void* get_search_index() TIGHTDB_NOEXCEPT;

    //@{
    /// Find the lower/upper bound for the specified value assuming
    /// that the elements are already sorted in ascending order
    /// according to ordinary integer comparison.
    std::size_t lower_bound_int(int64_t value) const TIGHTDB_NOEXCEPT;
    std::size_t upper_bound_int(int64_t value) const TIGHTDB_NOEXCEPT;
    //@}

    // return first element E for which E >= target or return -1 if none. Array must be sorted
    size_t find_gte(int64_t target, size_t start) const;

    /// Compare two columns for equality.
    bool compare_int(const Column&) const TIGHTDB_NOEXCEPT;

    static ref_type create(Allocator&, Array::Type leaf_type = Array::type_Normal,
                           std::size_t size = 0, int_fast64_t value = 0);

    // Overrriding method in ColumnBase
    ref_type write(std::size_t, std::size_t, std::size_t,
                   _impl::OutputStream&) const TIGHTDB_OVERRIDE;

    /// \param row_ndx Must be `tightdb::npos` if appending.
    void do_insert(std::size_t row_ndx, int_fast64_t value, std::size_t num_rows);

    void refresh_accessor_tree(std::size_t, const Spec&) TIGHTDB_OVERRIDE;

#ifdef TIGHTDB_DEBUG
    void Verify() const TIGHTDB_OVERRIDE;
    using ColumnBase::Verify;
    void to_dot(std::ostream&, StringData title) const TIGHTDB_OVERRIDE;
    MemStats stats() const;
    void do_dump_node_structure(std::ostream&, int) const TIGHTDB_OVERRIDE;
#endif

    // todo, make private, and correct type
    void* m_search_index;

protected:
    Column(Array* root = 0) TIGHTDB_NOEXCEPT;

    std::size_t do_get_size() const TIGHTDB_NOEXCEPT TIGHTDB_OVERRIDE { return size(); }

#ifdef TIGHTDB_DEBUG
    void leaf_to_dot(MemRef, ArrayParent*, std::size_t ndx_in_parent,
                     std::ostream&) const TIGHTDB_OVERRIDE;
    static void dump_node_structure(const Array& root, std::ostream&, int level);
#endif

private:
    Column(const Column&); // not allowed
    Column &operator=(const Column&); // not allowed

    // Called by Array::bptree_insert().
    static ref_type leaf_insert(MemRef leaf_mem, ArrayParent&, std::size_t ndx_in_parent,
                                Allocator&, std::size_t insert_ndx, Array::TreeInsert<Column>&);

    class EraseLeafElem;
    class CreateHandler;
    class SliceHandler;

    friend class Array;
    friend class ColumnBase;
};

// Implementation:

inline std::size_t ColumnBase::size() const TIGHTDB_NOEXCEPT
{
    return do_get_size();
}

inline ColumnBase::ColumnBase(Array* root) TIGHTDB_NOEXCEPT:
    m_array(root)
{
}

inline void ColumnBase::detach()
{
    m_array->detach();
}

inline bool ColumnBase::is_attached() const TIGHTDB_NOEXCEPT
{
    return m_array->is_attached();
}

inline bool ColumnBase::is_string_col() const TIGHTDB_NOEXCEPT
{
    return false;
}

inline void ColumnBase::destroy() TIGHTDB_NOEXCEPT
{
    if (m_array)
        m_array->destroy_deep();
}

inline bool ColumnBase::has_search_index() const TIGHTDB_NOEXCEPT
{
    return false;
}

inline void ColumnBase::set_search_index_ref(ref_type, ArrayParent*, std::size_t, bool)
{
}

inline void ColumnBase::set_search_index_allow_duplicate_values(bool) TIGHTDB_NOEXCEPT
{
}

inline void ColumnBase::discard_child_accessors() TIGHTDB_NOEXCEPT
{
    do_discard_child_accessors();
}

inline Table* ColumnBase::get_subtable_accessor(std::size_t) const TIGHTDB_NOEXCEPT
{
    return 0;
}

inline void ColumnBase::discard_subtable_accessor(std::size_t) TIGHTDB_NOEXCEPT
{
    // Noop
}

inline void ColumnBase::adj_accessors_insert_rows(std::size_t, std::size_t) TIGHTDB_NOEXCEPT
{
    // Noop
}

inline void ColumnBase::adj_accessors_erase_row(std::size_t) TIGHTDB_NOEXCEPT
{
    // Noop
}

inline void ColumnBase::adj_accessors_move(std::size_t, std::size_t) TIGHTDB_NOEXCEPT
{
    // Noop
}

inline void ColumnBase::adj_acc_clear_root_table() TIGHTDB_NOEXCEPT
{
    // Noop
}

inline void ColumnBase::mark(int) TIGHTDB_NOEXCEPT
{
    // Noop
}

inline void ColumnBase::bump_link_origin_table_version() TIGHTDB_NOEXCEPT
{
    // Noop
}

inline void ColumnBase::set_parent(ArrayParent* parent, std::size_t ndx_in_parent) TIGHTDB_NOEXCEPT
{
    m_array->set_parent(parent, ndx_in_parent);
}

inline const Array& ColumnBase::get_leaf(std::size_t ndx, std::size_t& ndx_in_leaf,
                                         Array& fallback) const TIGHTDB_NOEXCEPT
{
    if (!m_array->is_inner_bptree_node()) {
        ndx_in_leaf = ndx;
        return *m_array;
    }
    std::pair<MemRef, std::size_t> p = m_array->get_bptree_leaf(ndx);
    fallback.init_from_mem(p.first);
    ndx_in_leaf = p.second;
    return fallback;
}

inline const Array* ColumnBase::GetBlock(std::size_t ndx, Array& arr, std::size_t& off,
                                         bool use_retval) const TIGHTDB_NOEXCEPT
{
    return m_array->GetBlock(ndx, arr, off, use_retval);
}

inline std::size_t ColumnBase::get_size_from_ref(ref_type root_ref, Allocator& alloc)
{
    const char* root_header = alloc.translate(root_ref);
    bool root_is_leaf = !Array::get_is_inner_bptree_node_from_header(root_header);
    if (root_is_leaf)
        return Array::get_size_from_header(root_header);
    return Array::get_bptree_size_from_header(root_header);
}

template<class L, class T>
std::size_t ColumnBase::lower_bound(const L& list, T value) const TIGHTDB_NOEXCEPT
{
    std::size_t i = 0;
    std::size_t size = list.size();
    while (0 < size) {
        std::size_t half = size / 2;
        std::size_t mid = i + half;
        typename L::value_type probe = list.get(mid);
        if (probe < value) {
            i = mid + 1;
            size -= half + 1;
        }
        else {
            size = half;
        }
    }
    return i;
}

template<class L, class T>
std::size_t ColumnBase::upper_bound(const L& list, T value) const TIGHTDB_NOEXCEPT
{
    size_t i = 0;
    size_t size = list.size();
    while (0 < size) {
        size_t half = size / 2;
        size_t mid = i + half;
        typename L::value_type probe = list.get(mid);
        if (!(value < probe)) {
            i = mid + 1;
            size -= half + 1;
        }
        else {
            size = half;
        }
    }
    return i;
}

inline Allocator& ColumnBase::EraseHandlerBase::get_alloc() TIGHTDB_NOEXCEPT
{
    return m_column.m_array->get_alloc();
}

inline void ColumnBase::EraseHandlerBase::replace_root(Array* leaf)
{
    util::UniquePtr<Array> leaf_2(leaf);
    ArrayParent* parent = m_column.m_array->get_parent();
    std::size_t ndx_in_parent = m_column.m_array->get_ndx_in_parent();
    leaf_2->set_parent(parent, ndx_in_parent);
    leaf_2->update_parent(); // Throws
    delete m_column.m_array;
    m_column.m_array = leaf_2.release();
}

inline ref_type ColumnBase::create(Allocator& alloc, std::size_t size, CreateHandler& handler)
{
    std::size_t rest_size = size;
    std::size_t fixed_height = 0; // Not fixed
    return build(&rest_size, fixed_height, alloc, handler);
}

inline bool Column::has_search_index() const TIGHTDB_NOEXCEPT
{
    return m_search_index;
}

// fixme, must m_search_index be copied here?
inline Column::Column(Allocator& alloc, ref_type ref) : m_search_index(null_ptr)
{
    m_array = new Array(alloc); // Throws
    m_array->init_from_ref(ref);
}

inline Column::Column(unattached_root_tag, Allocator& alloc) : m_search_index(null_ptr)
{
    m_array = new Array(alloc); // Throws

}

inline Column::Column(move_tag, Column& col) TIGHTDB_NOEXCEPT
{
    m_array = col.m_array;
    col.m_array = 0;
    m_search_index = col.m_search_index;
    col.m_search_index = 0;
}

inline Column::Column(Array* root) TIGHTDB_NOEXCEPT:
    ColumnBase(root), m_search_index(null_ptr)
{
}

inline std::size_t Column::size() const TIGHTDB_NOEXCEPT
{
    if (root_is_leaf())
        return m_array->size();
    return m_array->get_bptree_size();
}

inline int_fast64_t Column::get(std::size_t ndx) const TIGHTDB_NOEXCEPT
{
    TIGHTDB_ASSERT(ndx < size());
    if (!m_array->is_inner_bptree_node())
        return m_array->get(ndx);

    std::pair<MemRef, std::size_t> p = m_array->get_bptree_leaf(ndx);
    const char* leaf_header = p.first.m_addr;
    std::size_t ndx_in_leaf = p.second;
    return Array::get(leaf_header, ndx_in_leaf);
}

inline ref_type Column::get_as_ref(std::size_t ndx) const TIGHTDB_NOEXCEPT
{
    return to_ref(get(ndx));
}

inline void Column::add(int_fast64_t value)
{
    std::size_t row_ndx = tightdb::npos;
    std::size_t num_rows = 1;
    do_insert(row_ndx, value, num_rows); // Throws
}

inline void Column::insert(std::size_t row_ndx, int_fast64_t value)
{
    std::size_t size = this->size(); // Slow
    TIGHTDB_ASSERT(row_ndx <= size);
    std::size_t row_ndx_2 = row_ndx == size ? tightdb::npos : row_ndx;
    std::size_t num_rows = 1;
    do_insert(row_ndx_2, value, num_rows); // Throws
}

// Implementing pure virtual method of ColumnBase.
inline void Column::insert(std::size_t row_ndx, std::size_t num_rows, bool is_append)
{
    std::size_t row_ndx_2 = is_append ? tightdb::npos : row_ndx;
    int_fast64_t value = 0;
    do_insert(row_ndx_2, value, num_rows); // Throws
}

TIGHTDB_FORCEINLINE
ref_type Column::leaf_insert(MemRef leaf_mem, ArrayParent& parent, std::size_t ndx_in_parent,
                             Allocator& alloc, std::size_t insert_ndx,
                             Array::TreeInsert<Column>& state)
{
    Array leaf(alloc);
    leaf.init_from_mem(leaf_mem);
    leaf.set_parent(&parent, ndx_in_parent);
    return leaf.bptree_leaf_insert(insert_ndx, state.m_value, state); // Throws
}

inline std::size_t Column::lower_bound_int(int64_t value) const TIGHTDB_NOEXCEPT
{
    if (root_is_leaf()) {
        return m_array->lower_bound_int(value);
    }
    return ColumnBase::lower_bound(*this, value);
}

inline std::size_t Column::upper_bound_int(int64_t value) const TIGHTDB_NOEXCEPT
{
    if (root_is_leaf()) {
        return m_array->upper_bound_int(value);
    }
    return ColumnBase::upper_bound(*this, value);
}

// For a *sorted* Column, return first element E for which E >= target or return -1 if none
inline size_t Column::find_gte(int64_t target, size_t start) const
{
    // fixme: slow reference implementation. See Array::FindGTE for faster version
    size_t ref = 0;
    size_t idx;
    for (idx = start; idx < size(); ++idx) {
        if (get(idx) >= target) {
            ref = idx;
            break;
        }
    }
    if (idx == size())
        ref = not_found;

    return ref;
}

} // namespace tightdb

// Templates
#include <tightdb/column_tpl.hpp>

#endif // TIGHTDB_COLUMN_HPP


text:
<?php

namespace Oro\Bundle\CalendarBundle\Manager;

use Oro\Bundle\CalendarBundle\Provider\CalendarPropertyProvider;
use Oro\Bundle\CalendarBundle\Provider\CalendarProviderInterface;
use Oro\Bundle\UIBundle\Tools\ArrayUtils;

class CalendarManager
{
    /** @var CalendarPropertyProvider */
    protected $calendarPropertyProvider;

    /** @var CalendarProviderInterface[] */
    protected $providers = [];

    /**
     * @param CalendarPropertyProvider $calendarPropertyProvider
     */
    public function __construct(CalendarPropertyProvider $calendarPropertyProvider)
    {
        $this->calendarPropertyProvider = $calendarPropertyProvider;
    }

    /**
     * Registers the given provider in the chain
     *
     * @param string                    $alias
     * @param CalendarProviderInterface $provider
     */
    public function addProvider($alias, CalendarProviderInterface $provider)
    {
        $this->providers[$alias] = $provider;
    }

    /**
     * Gets calendars connected to the given calendar
     *
     * @param int $organizationId The id of an organization for which this information is requested
     * @param int $userId         The id of an user requested this information
     * @param int $calendarId     The target calendar id
     *
     * @return array
     */
    public function getCalendars($organizationId, $userId, $calendarId)
    {
        // make sure input parameters have proper types
        $userId     = (int)$userId;
        $calendarId = (int)$calendarId;

        $result = $this->calendarPropertyProvider->getItems($calendarId);

        $existing = [];
        foreach ($result as $key => $item) {
            $existing[$item['calendarAlias']][$item['calendar']] = $key;
        }

        foreach ($this->providers as $alias => $provider) {
            $calendarIds           = isset($existing[$alias]) ? array_keys($existing[$alias]) : [];
            $calendarDefaultValues = $provider->getCalendarDefaultValues(
                $organizationId,
                $userId,
                $calendarId,
                $calendarIds
            );
            foreach ($calendarDefaultValues as $id => $values) {
                if (isset($existing[$alias][$id])) {
                    $key = $existing[$alias][$id];
                    if ($values !== null) {
                        $calendar = $result[$key];
                        $this->applyCalendarDefaultValues($calendar, $values);
                        $result[$key] = $calendar;
                    } else {
                        unset($result[$key]);
                    }
                } else {
                    $values['targetCalendar'] = $calendarId;
                    $values['calendarAlias']  = $alias;
                    $values['calendar']       = $id;
                    $result[]                 = $values;
                }
            }
        }

        $this->normalizeCalendarData($result);

        return $result;
    }

    /**
     * Gets the list of calendar events
     *
     * @param int       $organizationId The id of an organization for which this information is requested
     * @param int       $userId         The id of an user requested this information
     * @param int       $calendarId     The target calendar id
     * @param \DateTime $start          A date/time specifies the begin of a time interval
     * @param \DateTime $end            A date/time specifies the end of a time interval
     * @param bool      $subordinate    Determines whether events from connected calendars should be included or not
     * @param array     $extraFields
     *
     * @return array
     */
    public function getCalendarEvents(
        $organizationId,
        $userId,
        $calendarId,
        $start,
        $end,
        $subordinate,
        $extraFields = []
    ) {
        // make sure input parameters have proper types
        $calendarId = (int)$calendarId;
        $subordinate = (bool)$subordinate;

        $allConnections = $this->calendarPropertyProvider->getItemsVisibility($calendarId, $subordinate);

        $result = [];

        foreach ($this->providers as $alias => $provider) {
            $connections = [];
            foreach ($allConnections as $c) {
                if ($c['calendarAlias'] === $alias) {
                    $connections[$c['calendar']] = $c['visible'];
                }
            }
            $events = $provider->getCalendarEvents(
                $organizationId,
                $userId,
                $calendarId,
                $start,
                $end,
                $connections,
                $extraFields
            );
            if (!empty($events)) {
                foreach ($events as &$event) {
                    $event['calendarAlias'] = $alias;
                    if (!isset($event['editable'])) {
                        $event['editable'] = true;
                    }
                    if (!isset($event['removable'])) {
                        $event['removable'] = true;
                    }
                    if (!isset($event['notifiable'])) {
                        $event['notifiable'] = false;
                    }
                }
                $result = array_merge($result, $events);
            }
        }

        return $result;
    }

    /**
     * @param array $calendars
     */
    protected function normalizeCalendarData(array &$calendars)
    {
        // apply default values and remove redundant properties
        $defaultValues = $this->getCalendarDefaultValues();
        foreach ($calendars as &$calendar) {
            $this->applyCalendarDefaultValues($calendar, $defaultValues);
        }

        ArrayUtils::sortBy($calendars, false, 'position');
    }

    /**
     * @param array $calendar
     * @param array $defaultValues
     */
    protected function applyCalendarDefaultValues(array &$calendar, array $defaultValues)
    {
        foreach ($defaultValues as $fieldName => $val) {
            // set default value for a field if the field does not exists or it's value is null
            if (!isset($calendar[$fieldName])) {
                $calendar[$fieldName] = is_callable($val)
                    ? call_user_func($val, $fieldName)
                    : $val;
            }
        }
    }

    /**
     * @return array
     */
    protected function getCalendarDefaultValues()
    {
        $result = $this->calendarPropertyProvider->getDefaultValues();

        $result['calendarName'] = null;
        $result['removable']    = true;

        return $result;
    }
}

redpajama_set_name: RedPajamaGithub


text: No. Currently VBS supports only backup and restoration within a region but not across regions.


text:
package org.wso2.carbon.identity.mgt.config;

public abstract class AbstractConfigManager implements ConfigManager {

    protected abstract void createConfig();

}


text:
using System.IO;

namespace LiteDB
{
    /// <summary>
    /// The LiteDB database. Used for create a LiteDB instance and use all storage resoures. It's the database connection
    /// </summary>
    public partial class LiteDatabase
    {
#if NETSTANDARD
        static LiteDatabase()
        {
            if (LitePlatform.Platform == null)
            {
                LitePlatform.Initialize(new Platform.LitePlatformDotNetStandardDefault());
            }
        }
#endif

        public const int PAGE_SIZE = BasePage.PAGE_SIZE;

        private LazyLoad<DbEngine> _engine;

        private BsonMapper _mapper;

        private Logger _log = new Logger();

        /// <summary>
        /// Get logger class instance
        /// </summary>
        public Logger Log { get { return _log; } }

        /// <summary>
        /// Get current instance of BsonMapper used in this database instance (can be BsonMapper.Global)
        /// </summary>
        public BsonMapper Mapper { get { return _mapper; } }

        /// <summary>
        /// Starts LiteDB database using a connection string for filesystem database
        /// </summary>
        public LiteDatabase(string connectionString, BsonMapper mapper = null)
        {
            LitePlatform.ThrowIfNotInitialized();

            var conn = new ConnectionString(connectionString);

            _mapper = mapper ?? BsonMapper.Global;

            var encrypted = !StringExtensions.IsNullOrWhiteSpace(conn.GetValue<string>("password", null));

            _engine = new LazyLoad<DbEngine>(() => new DbEngine(encrypted ? new EncryptedDiskService(conn, _log) : new FileDiskService(conn, _log), _log));
        }

        /// <summary>
        /// Starts LiteDB database using a custom IDiskService
        /// </summary>
        public LiteDatabase(IDiskService diskService, BsonMapper mapper = null)
        {
            LitePlatform.ThrowIfNotInitialized();

            _mapper = mapper ?? BsonMapper.Global;
            _engine = new LazyLoad<DbEngine>(() => new DbEngine(diskService, _log));
        }

        /// <summary>
        /// Initialize database using any read/write Stream (like MemoryStream)
        /// </summary>
        public LiteDatabase(Stream stream, BsonMapper mapper = null)
        {
            LitePlatform.ThrowIfNotInitialized();

            _mapper = mapper ?? BsonMapper.Global;
            _engine = new LazyLoad<DbEngine>(() => new DbEngine(new StreamDiskService(stream), _log));
        }

        /// <summary>
        /// Get/Set database version
        /// </summary>
        public ushort DbVersion
        {
            get { return _engine.Value.ReadDbVersion(); }
            set { _engine.Value.WriteDbVersion(value); }
        }

        public void Dispose()
        {
            if (_engine.IsValueCreated) _engine.Value.Dispose();
        }
    }
}


text:
<?php

/**
 * @see Zend_Json_Server_Request
 */
// require_once 'Zend/Json/Server/Request.php';

/**
 * @category   Zend
 * @package    Zend_Json
 * @copyright  Copyright (c) 2005-2015 Zend Technologies USA Inc. (http://www.zend.com)
 * @license    http://framework.zend.com/license/new-bsd     New BSD License
 */
class Zend_Json_Server_Request_Http extends Zend_Json_Server_Request
{
    /**
     * Raw JSON pulled from POST body
     * @var string
     */
    protected $_rawJson;

    /**
     * Constructor
     *
     * Pull JSON request from raw POST body and use to populate request.
     *
     * @return void
     */
    public function __construct()
    {
        $json = file_get_contents('php://input');
        $this->_rawJson = $json;
        if (!empty($json)) {
            $this->loadJson($json);
        }
    }

    /**
     * Get JSON from raw POST body
     *
     * @return string
     */
    public function getRawJson()
    {
        return $this->_rawJson;
    }
}


text:
@interface MHUser (Internal)

- (void)invalidateOwnedCollections;
- (void)invalidateFollowing;

@end


text:
All notable changes to this project will be documented in this file.
On 2020-05-31, two tags were deleted from origin, `v1.0.0` and `v1.0.1` and replaced with `v0.4.0` and `v0.4.1` respectively.
If you cloned/forked the repository before 2020-05-31, you should delete `v1.0.0` and `v1.0.1` and pull tags.

## [Unreleased]
### API Changes
- Add support for setting an instrument's transposition at the start of the score. [#116]

### Internal Changes
- Change the default-constructed value of `DynamicsEnum` to `mf` instead of `otherDynamics`. [#106]/[8a5cd6b]
- Change the spelling of `KindValue` enums from, e.g. `dominant11Th` to `dominant11th`. [#105]
- Break up `Strings.h` into multiple `.h` files, one for each type [#107]. (Related to codegen, [#58]).
- Rewrite `Integers.h` and `Integers.cpp`. Changed `NonNegativeInteger` to default to 0, and changed the tests that had locked-in that behavior. [#109]. (Related to codegen, [#58]).
- Rewrite `Decimals.h` and `Decimals.cpp`. [#111]. (Related to codegen, [#58]).
- Rewrite `Enums`, `Integers` and `Decimals`. Add try parse and return bool from parse methods. [#112]. (Related to codegen, [#58]).
- Rewrite union types `FontSize` and `YesNoNumber`. Also reformat a bunch of documentation. [#113]. (Related to codegen, [#58]).

[#105]: https://github.com/webern/mx/pull/105
[#106]: https://github.com/webern/mx/pull/106
[#107]: https://github.com/webern/mx/pull/107
[#109]: https://github.com/webern/mx/pull/109
[#111]: https://github.com/webern/mx/pull/111
[#112]: https://github.com/webern/mx/pull/112
[#113]: https://github.com/webern/mx/pull/113
[#116]: https://github.com/webern/mx/pull/116
[#58]: https://github.com/webern/mx/issues/58
[8a5cd6b]: https://github.com/webern/mx/commit/8a5cd6b

## [v0.5.1] - 2020-06-13
- Fix xcode build, new headers were missing from frameworks.

## [v0.5.0] - 2020-06-13
### Breaking Changes
- Add support for `new-page` attributes and page layout [#94]
- The `LayoutData layout` field of `ScoreData` has been renamed to `DefaultsData defaults` [#94]
  - What used to be the `LayoutData` class has been renamed to `DefaultsData`.
  - This name change freed up the name `LayoutsData` to be used for a new class that better fits the name.
- The `std::set<SystemData> systems` field of `ScoreData` has been replaced by `std::map<MeasureIndex, LayoutData>`. [#94]
  - `LayoutData` is a new class (not to be confused with `DefaultsData` which previously held the name).
  - `LayoutData` holds a `SystemData` and a `PageData` (new) to specify system and page layout.
- Some recurring data patterns were factored out into new classes. [#94]
  - The existing classes affected by these changes are:
    - `DefaultsData` (which used to be called `LayoutData`).
    - `SystemData`
  - The new classes are:
    - `LeftRight`
    - `MarginsData`
    - `PageLayoutData`
    - `PageMarginsData`
    - `SizeData`
    - `SystemLayoutData`

### Other Changes
- Bump C++ standard to 17 [#93]
- Support non-traditional key signatures in `mx::api`. [#81]
- Add a constructor for `PitchData`. [#90]
- Provide a hint in the exception message when a zip file is attempted. [#67]
- Update the readme fairly substantially. [#91]
- Add a changelog. [#97]
- Hide the independence of the XML parser to reduce confusion about dependency management. [#79]
- The introduction of `std::optional` as a pattern for specifying optional data. [#94]

[#67]: https://github.com/webern/mx/pull/67
[#79]: https://github.com/webern/mx/pull/79
[#81]: https://github.com/webern/mx/pull/81
[#90]: https://github.com/webern/mx/pull/90
[#91]: https://github.com/webern/mx/pull/91
[#93]: https://github.com/webern/mx/pull/93
[#94]: https://github.com/webern/mx/pull/94
[#97]: https://github.com/webern/mx/pull/97

## [v0.4.1] - 2019-11-23
- Mostly internal changes related to the xml parser.

## [v0.4.0] - 2019-04-08
- A simplified data model, called `mx::api`.

## [v0.3.0] - 2017-11-20
- MusicXML files can be parsed into the C++ classes.

## [v0.2.0] - 2016-08-21
- MusicXML 3.0 represented in C++ classes, mostly generated from XSD using custom Ruby scripts.
- MusicXML DOM classes can serialize to XML.

## [v0.1.0] - 2016-06-20
- Initial Commit

[v0.1.0]: https://github.com/webern/mx/commit/5d46609
[v0.2.0]: https://github.com/webern/mx/compare/5d46609..v0.2.0
[v0.3.0]: https://github.com/webern/mx/compare/v0.2.0..v0.3.0
[v0.4.0]: https://github.com/webern/mx/compare/v0.3.0..v0.4.0
[v0.4.1]: https://github.com/webern/mx/compare/v0.4.0..v0.4.1
[v0.5.0]: https://github.com/webern/mx/compare/v0.4.1..v0.5.0
[v0.5.1]: https://github.com/webern/mx/compare/v0.5.0..v0.5.1
[Unreleased]: https://github.com/webern/mx/compare/v0.5.1...HEAD

#### Historical Notes

**Historical Note: April 7, 2019** Trying to button up a '1.0' 'release' by tying up some of the loose ends with the build, continuous integration, testing, and header leakage.
The use of the semver `1.0` implies that we hope there won't be many breaking changes.
I suppose the way I will use semver is as follows: a patch release may cause slight compilation annoyances, but nothing that would cause any rewriting of code.
A minor release may similarly require some tweaks but hopefully nothing too major.
A major release could be anything up-to a complete re-write.

**Historical Note: October 6, 2016:** Significant progress has been made on the `api` namespace, which is a simplified set of data structures to represent a MusicXML document.
These are being implemented as mostly-POD structs.
Currently the importing of data into these structures is well-underway, but the exporting from these data structures has not been implemented.

**Historical Note: August 16, 2016:** All tests are passing (core, xml and import).
The remaining items to do on the ximport feature are
- search for all `\\TODO's` and fix those that can be fixed
- Standardize the code file copyrights and bump to version 0.2
- Rename XElement functions to better names
- Update the readme including information about the XDoc XElement classes and how to implement those interfaces.

**Historical Note: August 11, 2016:** The feature to import MusicXML files is essentially complete with most "round-trip" integration tests passing.

**Historical Note: June 27, 2016:** An "integration" tester has been added to the MxTest executable.
This exists in ImportTest.cpp, and ImportTestImpl.h/cpp.
A top level directory "Resources" has been added to hold test input (i.e. "golden") files.
The input files are gathered from Recordare, Lilypond and MuseScore and to this I have added a few of my own scores as exported by Finale Dolet.

Each of these test input files has been "scrubbed" using the XDoc classes (i.e. it has been round-tripped through pugixml and has been updated to a normalized MusicXML 3.0 header format.
The resultant scrubbed files are in Resources/expected.
During the test run, a csv file is written in Resources/testOutput recording a row for each test (Pass/Fail, duration of test, messages, etc).
Each time a test failure is encountered the expected file and the error file will be saved to the Resources/testOutput directory to allow for visual inspection.

Currently this tester is a "wire-up".
All 263 of these round-trip import/export tests fail because the implementation does not yet exist in mx::core.
The next body of work will be the mx::core implementation.

**Historical Note: June 20, 2016:** A simple interface to for XML DOM has been added in the ::ezxml:: namespace.
The key classes (pure virtual) are XDoc, XElement, XAttribute, XElementIterator, XAttributeIterator.
These are implemented by concrete classes PugiDoc, PugiElement, etc. which serve as a wrapper for the pugixml library (http://pugixml.org/).
Although this is a static library, a class XFactory can be used to create a Pugi instance of the XDoc interface.

The idea behind using a pure virtual interface is that the client of the Music XML Class Library can, in theory choose a different XML DOM library (Xerces, TinyXML, etc) and wrap with instances of the XDoc interfaces and the Music XML core classes will not know the difference.

**Historical Note: June 20, 2016:** The GitHub repo was bloated and has been entirely wiped-out and restarted.


text:
//! This module contains tests for macro expansion. Effectively, it covers `tt`,
//! `mbe`, `proc_macro_api` and `hir_expand` crates. This might seem like a
//! wrong architecture at the first glance, but is intentional.
//!
//! Physically, macro expansion process is intertwined with name resolution. You
//! can not expand *just* the syntax. So, to be able to write integration tests
//! of the "expand this code please" form, we have to do it after name
//! resolution. That is, in this crate. We *could* fake some dependencies and
//! write unit-tests (in fact, we used to do that), but that makes tests brittle
//! and harder to understand.

mod mbe;
mod builtin_fn_macro;
mod builtin_derive_macro;
mod proc_macros;

use std::{iter, ops::Range, sync::Arc};

use ::mbe::TokenMap;
use base_db::{fixture::WithFixture, ProcMacro, SourceDatabase};
use expect_test::Expect;
use hir_expand::{
    db::{AstDatabase, TokenExpander},
    AstId, InFile, MacroDefId, MacroDefKind, MacroFile,
};
use stdx::format_to;
use syntax::{
    ast::{self, edit::IndentLevel},
    AstNode, SyntaxElement,
    SyntaxKind::{self, COMMENT, EOF, IDENT, LIFETIME_IDENT},
    SyntaxNode, TextRange, T,
};
use tt::{Subtree, TokenId};

use crate::{
    db::DefDatabase, macro_id_to_def_id, nameres::ModuleSource, resolver::HasResolver,
    src::HasSource, test_db::TestDB, AdtId, AsMacroCall, Lookup, ModuleDefId,
};

#[track_caller]
fn check(ra_fixture: &str, mut expect: Expect) {
    let extra_proc_macros = vec![(
        r#"
#[proc_macro_attribute]
pub fn identity_when_valid(_attr: TokenStream, item: TokenStream) -> TokenStream {
    item
}
"#
        .into(),
        ProcMacro {
            name: "identity_when_valid".into(),
            kind: base_db::ProcMacroKind::Attr,
            expander: Arc::new(IdentityWhenValidProcMacroExpander),
        },
    )];
    let db = TestDB::with_files_extra_proc_macros(ra_fixture, extra_proc_macros);
    let krate = db.crate_graph().iter().next().unwrap();
    let def_map = db.crate_def_map(krate);
    let local_id = def_map.root();
    let module = def_map.module_id(local_id);
    let resolver = module.resolver(&db);
    let source = def_map[local_id].definition_source(&db);
    let source_file = match source.value {
        ModuleSource::SourceFile(it) => it,
        ModuleSource::Module(_) | ModuleSource::BlockExpr(_) => panic!(),
    };

    // What we want to do is to replace all macros (fn-like, derive, attr) with
    // their expansions. Turns out, we don't actually store enough information
    // to do this precisely though! Specifically, if a macro expands to nothing,
    // it leaves zero traces in def-map, so we can't get its expansion after the
    // fact.
    //
    // This is the usual
    // <https://github.com/rust-lang/rust-analyzer/issues/3407>
    // resolve/record tension!
    //
    // So here we try to do a resolve, which is necessary a heuristic. For macro
    // calls, we use `as_call_id_with_errors`. For derives, we look at the impls
    // in the module and assume that, if impls's source is a different
    // `HirFileId`, than it came from macro expansion.

    let mut text_edits = Vec::new();
    let mut expansions = Vec::new();

    for macro_ in source_file.syntax().descendants().filter_map(ast::Macro::cast) {
        let mut show_token_ids = false;
        for comment in macro_.syntax().children_with_tokens().filter(|it| it.kind() == COMMENT) {
            show_token_ids |= comment.to_string().contains("+tokenids");
        }
        if !show_token_ids {
            continue;
        }

        let call_offset = macro_.syntax().text_range().start().into();
        let file_ast_id = db.ast_id_map(source.file_id).ast_id(&macro_);
        let ast_id = AstId::new(source.file_id, file_ast_id.upcast());
        let kind = MacroDefKind::Declarative(ast_id);

        let macro_def = db.macro_def(MacroDefId { krate, kind, local_inner: false }).unwrap();
        if let TokenExpander::DeclarativeMacro { mac, def_site_token_map } = &*macro_def {
            let tt = match &macro_ {
                ast::Macro::MacroRules(mac) => mac.token_tree().unwrap(),
                ast::Macro::MacroDef(_) => unimplemented!(""),
            };

            let tt_start = tt.syntax().text_range().start();
            tt.syntax().descendants_with_tokens().filter_map(SyntaxElement::into_token).for_each(
                |token| {
                    let range = token.text_range().checked_sub(tt_start).unwrap();
                    if let Some(id) = def_site_token_map.token_by_range(range) {
                        let offset = (range.end() + tt_start).into();
                        text_edits.push((offset..offset, format!("#{}", id.0)));
                    }
                },
            );
            text_edits.push((
                call_offset..call_offset,
                format!("// call ids will be shifted by {:?}\n", mac.shift()),
            ));
        }
    }

    for macro_call in source_file.syntax().descendants().filter_map(ast::MacroCall::cast) {
        let macro_call = InFile::new(source.file_id, &macro_call);
        let mut error = None;
        let macro_call_id = macro_call
            .as_call_id_with_errors(
                &db,
                krate,
                |path| {
                    resolver.resolve_path_as_macro(&db, &path).map(|it| macro_id_to_def_id(&db, it))
                },
                &mut |err| error = Some(err),
            )
            .unwrap()
            .unwrap();
        let macro_file = MacroFile { macro_call_id };
        let mut expansion_result = db.parse_macro_expansion(macro_file);
        expansion_result.err = expansion_result.err.or(error);
        expansions.push((macro_call.value.clone(), expansion_result, db.macro_arg(macro_call_id)));
    }

    for (call, exp, arg) in expansions.into_iter().rev() {
        let mut tree = false;
        let mut expect_errors = false;
        let mut show_token_ids = false;
        for comment in call.syntax().children_with_tokens().filter(|it| it.kind() == COMMENT) {
            tree |= comment.to_string().contains("+tree");
            expect_errors |= comment.to_string().contains("+errors");
            show_token_ids |= comment.to_string().contains("+tokenids");
        }

        let mut expn_text = String::new();
        if let Some(err) = exp.err {
            format_to!(expn_text, "/* error: {} */", err);
        }
        if let Some((parse, token_map)) = exp.value {
            if expect_errors {
                assert!(!parse.errors().is_empty(), "no parse errors in expansion");
                for e in parse.errors() {
                    format_to!(expn_text, "/* parse error: {} */\n", e);
                }
            } else {
                assert!(
                    parse.errors().is_empty(),
                    "parse errors in expansion: \n{:#?}",
                    parse.errors()
                );
            }
            let pp = pretty_print_macro_expansion(
                parse.syntax_node(),
                show_token_ids.then(|| &*token_map),
            );
            let indent = IndentLevel::from_node(call.syntax());
            let pp = reindent(indent, pp);
            format_to!(expn_text, "{}", pp);

            if tree {
                let tree = format!("{:#?}", parse.syntax_node())
                    .split_inclusive('\n')
                    .map(|line| format!("// {}", line))
                    .collect::<String>();
                format_to!(expn_text, "\n{}", tree)
            }
        }
        let range = call.syntax().text_range();
        let range: Range<usize> = range.into();

        if show_token_ids {
            if let Some((tree, map, _)) = arg.as_deref() {
                let tt_range = call.token_tree().unwrap().syntax().text_range();
                let mut ranges = Vec::new();
                extract_id_ranges(&mut ranges, map, tree);
                for (range, id) in ranges {
                    let idx = (tt_range.start() + range.end()).into();
                    text_edits.push((idx..idx, format!("#{}", id.0)));
                }
            }
            text_edits.push((range.start..range.start, "// ".into()));
            call.to_string().match_indices('\n').for_each(|(offset, _)| {
                let offset = offset + 1 + range.start;
                text_edits.push((offset..offset, "// ".into()));
            });
            text_edits.push((range.end..range.end, "\n".into()));
            text_edits.push((range.end..range.end, expn_text));
        } else {
            text_edits.push((range, expn_text));
        }
    }

    text_edits.sort_by_key(|(range, _)| range.start);
    text_edits.reverse();
    let mut expanded_text = source_file.to_string();
    for (range, text) in text_edits {
        expanded_text.replace_range(range, &text);
    }

    for decl_id in def_map[local_id].scope.declarations() {
        // FIXME: I'm sure there's already better way to do this
        let src = match decl_id {
            ModuleDefId::AdtId(AdtId::StructId(struct_id)) => {
                Some(struct_id.lookup(&db).source(&db).syntax().cloned())
            }
            ModuleDefId::FunctionId(function_id) => {
                Some(function_id.lookup(&db).source(&db).syntax().cloned())
            }
            _ => None,
        };
        if let Some(src) = src {
            if src.file_id.is_attr_macro(&db) || src.file_id.is_custom_derive(&db) {
                let pp = pretty_print_macro_expansion(src.value, None);
                format_to!(expanded_text, "\n{}", pp)
            }
        }
    }

    for impl_id in def_map[local_id].scope.impls() {
        let src = impl_id.lookup(&db).source(&db);
        if src.file_id.is_builtin_derive(&db).is_some() {
            let pp = pretty_print_macro_expansion(src.value.syntax().clone(), None);
            format_to!(expanded_text, "\n{}", pp)
        }
    }

    expect.indent(false);
    expect.assert_eq(&expanded_text);
}

fn extract_id_ranges(ranges: &mut Vec<(TextRange, TokenId)>, map: &TokenMap, tree: &Subtree) {
    tree.token_trees.iter().for_each(|tree| match tree {
        tt::TokenTree::Leaf(leaf) => {
            let id = match leaf {
                tt::Leaf::Literal(it) => it.id,
                tt::Leaf::Punct(it) => it.id,
                tt::Leaf::Ident(it) => it.id,
            };
            ranges.extend(map.ranges_by_token(id, SyntaxKind::ERROR).map(|range| (range, id)));
        }
        tt::TokenTree::Subtree(tree) => extract_id_ranges(ranges, map, tree),
    });
}

fn reindent(indent: IndentLevel, pp: String) -> String {
    if !pp.contains('\n') {
        return pp;
    }
    let mut lines = pp.split_inclusive('\n');
    let mut res = lines.next().unwrap().to_string();
    for line in lines {
        if line.trim().is_empty() {
            res.push_str(line)
        } else {
            format_to!(res, "{}{}", indent, line)
        }
    }
    res
}

fn pretty_print_macro_expansion(expn: SyntaxNode, map: Option<&TokenMap>) -> String {
    let mut res = String::new();
    let mut prev_kind = EOF;
    let mut indent_level = 0;
    for token in iter::successors(expn.first_token(), |t| t.next_token()) {
        let curr_kind = token.kind();
        let space = match (prev_kind, curr_kind) {
            _ if prev_kind.is_trivia() || curr_kind.is_trivia() => "",
            (T!['{'], T!['}']) => "",
            (T![=], _) | (_, T![=]) => " ",
            (_, T!['{']) => " ",
            (T![;] | T!['{'] | T!['}'], _) => "\n",
            (_, T!['}']) => "\n",
            (IDENT | LIFETIME_IDENT, IDENT | LIFETIME_IDENT) => " ",
            _ if prev_kind.is_keyword() && curr_kind.is_keyword() => " ",
            (IDENT, _) if curr_kind.is_keyword() => " ",
            (_, IDENT) if prev_kind.is_keyword() => " ",
            (T![>], IDENT) => " ",
            (T![>], _) if curr_kind.is_keyword() => " ",
            (T![->], _) | (_, T![->]) => " ",
            (T![&&], _) | (_, T![&&]) => " ",
            (T![,], _) => " ",
            (T![:], IDENT | T!['(']) => " ",
            (T![:], _) if curr_kind.is_keyword() => " ",
            (T![fn], T!['(']) => "",
            (T![']'], _) if curr_kind.is_keyword() => " ",
            (T![']'], T![#]) => "\n",
            (T![Self], T![::]) => "",
            _ if prev_kind.is_keyword() => " ",
            _ => "",
        };

        match prev_kind {
            T!['{'] => indent_level += 1,
            T!['}'] => indent_level -= 1,
            _ => (),
        }

        res.push_str(space);
        if space == "\n" {
            let level = if curr_kind == T!['}'] { indent_level - 1 } else { indent_level };
            res.push_str(&"    ".repeat(level));
        }
        prev_kind = curr_kind;
        format_to!(res, "{}", token);
        if let Some(map) = map {
            if let Some(id) = map.token_by_range(token.text_range()) {
                format_to!(res, "#{}", id.0);
            }
        }
    }
    res
}

// Identity mapping, but only works when the input is syntactically valid. This
// simulates common proc macros that unnecessarily parse their input and return
// compile errors.
#[derive(Debug)]
struct IdentityWhenValidProcMacroExpander;
impl base_db::ProcMacroExpander for IdentityWhenValidProcMacroExpander {
    fn expand(
        &self,
        subtree: &Subtree,
        _: Option<&Subtree>,
        _: &base_db::Env,
    ) -> Result<Subtree, base_db::ProcMacroExpansionError> {
        let (parse, _) =
            ::mbe::token_tree_to_syntax_node(subtree, ::mbe::TopEntryPoint::MacroItems);
        if parse.errors().is_empty() {
            Ok(subtree.clone())
        } else {
            panic!("got invalid macro input: {:?}", parse.errors());
        }
    }
}


text:
//** Introduction
// This file contains the code to perform the various self-test functions.
//
// NOTE: In this implementation, large local variables are made static to minimize
// stack usage, which is critical for stack-constrained platforms.

//** Includes and Defines
#include    "Tpm.h"

#define     SELF_TEST_DATA

#if SELF_TEST

// These includes pull in the data structures. They contain data definitions for the
// various tests.
#include    "SelfTest.h"
#include    "SymmetricTest.h"
#include    "RsaTestData.h"
#include    "EccTestData.h"
#include    "HashTestData.h"
#include    "KdfTestData.h"

#define TEST_DEFAULT_TEST_HASH(vector)                                              \
            if(TEST_BIT(DEFAULT_TEST_HASH, g_toTest))                               \
                TestHash(DEFAULT_TEST_HASH, vector);

// Make sure that the algorithm has been tested
#define CLEAR_BOTH(alg)     {   CLEAR_BIT(alg, *toTest);                            \
                                if(toTest != &g_toTest)                             \
                                    CLEAR_BIT(alg, g_toTest); }

#define SET_BOTH(alg)     {   SET_BIT(alg, *toTest);                                \
                                if(toTest != &g_toTest)                             \
                                    SET_BIT(alg, g_toTest); }

#define TEST_BOTH(alg)       ((toTest != &g_toTest)                                 \
                            ? TEST_BIT(alg, *toTest) || TEST_BIT(alg, g_toTest)     \
                            : TEST_BIT(alg, *toTest))

// Can only cancel if doing a list.
#define CHECK_CANCELED                                                              \
    if(_plat__IsCanceled() && toTest != &g_toTest)                                  \
        return TPM_RC_CANCELED;

//** Hash Tests

//*** Description
// The hash test does a known-value HMAC using the specified hash algorithm.

//*** TestHash()
// The hash test function.
static TPM_RC
TestHash(
    TPM_ALG_ID          hashAlg,
    ALGORITHM_VECTOR    *toTest
    )
{
    static TPM2B_DIGEST      computed;  // value computed
    static HMAC_STATE        state;
    UINT16                   digestSize;
    const TPM2B             *testDigest = NULL;
//    TPM2B_TYPE(HMAC_BLOCK, DEFAULT_TEST_HASH_BLOCK_SIZE);

    pAssert(hashAlg != ALG_NULL_VALUE);
    switch(hashAlg)
    {
#if ALG_SHA1
        case ALG_SHA1_VALUE:
            testDigest = &c_SHA1_digest.b;
            break;
#endif
#if ALG_SHA256
        case ALG_SHA256_VALUE:
            testDigest = &c_SHA256_digest.b;
            break;
#endif
#if ALG_SHA384
        case ALG_SHA384_VALUE:
            testDigest = &c_SHA384_digest.b;
            break;
#endif
#if ALG_SHA512
        case ALG_SHA512_VALUE:
            testDigest = &c_SHA512_digest.b;
            break;
#endif
#if ALG_SM3_256
        case ALG_SM3_256_VALUE:
            testDigest = &c_SM3_256_digest.b;
            break;
#endif
        default:
            FAIL(FATAL_ERROR_INTERNAL);
    }
    // Clear the to-test bits
    CLEAR_BOTH(hashAlg);

    // Set the HMAC key to twice the digest size
    digestSize = CryptHashGetDigestSize(hashAlg);
    CryptHmacStart(&state, hashAlg, digestSize * 2,
                   (BYTE *)c_hashTestKey.t.buffer);
    CryptDigestUpdate(&state.hashState, 2 * CryptHashGetBlockSize(hashAlg),
                      (BYTE *)c_hashTestData.t.buffer);
    computed.t.size = digestSize;
    CryptHmacEnd(&state, digestSize, computed.t.buffer);
    if((testDigest->size != computed.t.size)
       || (memcmp(testDigest->buffer, computed.t.buffer, computed.b.size) != 0))
        SELF_TEST_FAILURE;
    return TPM_RC_SUCCESS;
}

//** Symmetric Test Functions

//*** MakeIv()
// Internal function to make the appropriate IV depending on the mode.
static UINT32
MakeIv(
    TPM_ALG_ID    mode,     // IN: symmetric mode
    UINT32        size,     // IN: block size of the algorithm
    BYTE         *iv        // OUT: IV to fill in
    )
{
    BYTE          i;

    if(mode == ALG_ECB_VALUE)
        return 0;
    if(mode == ALG_CTR_VALUE)
    {
        // The test uses an IV that has 0xff in the last byte
        for(i = 1; i <= size; i++)
            *iv++ = 0xff - (BYTE)(size - i);
    }
    else
    {
        for(i = 0; i < size; i++)
            *iv++ = i;
    }
    return size;
}

//*** TestSymmetricAlgorithm()
// Function to test a specific algorithm, key size, and mode.
static void
TestSymmetricAlgorithm(
    const SYMMETRIC_TEST_VECTOR     *test,          //
    TPM_ALG_ID                       mode           //
    )
{
    static BYTE                 encrypted[MAX_SYM_BLOCK_SIZE * 2];
    static BYTE                 decrypted[MAX_SYM_BLOCK_SIZE * 2];
    static TPM2B_IV             iv;
//
    // Get the appropriate IV
    iv.t.size = (UINT16)MakeIv(mode, test->ivSize, iv.t.buffer);

    // Encrypt known data
    CryptSymmetricEncrypt(encrypted, test->alg, test->keyBits, test->key, &iv,
                          mode, test->dataInOutSize, test->dataIn);
    // Check that it matches the expected value
    if(!MemoryEqual(encrypted, test->dataOut[mode - ALG_CTR_VALUE],
                    test->dataInOutSize))
        SELF_TEST_FAILURE;
    // Reinitialize the iv for decryption
    MakeIv(mode, test->ivSize, iv.t.buffer);
    CryptSymmetricDecrypt(decrypted, test->alg, test->keyBits, test->key, &iv,
                          mode, test->dataInOutSize,
                          test->dataOut[mode - ALG_CTR_VALUE]);
    // Make sure that it matches what we started with
    if(!MemoryEqual(decrypted, test->dataIn, test->dataInOutSize))
        SELF_TEST_FAILURE;
}

//*** AllSymsAreDone()
// Checks if both symmetric algorithms have been tested. This is put here
// so that addition of a symmetric algorithm will be relatively easy to handle
//  Return Type: BOOL
//      TRUE(1)         all symmetric algorithms tested
//      FALSE(0)        not all symmetric algorithms tested
static BOOL
AllSymsAreDone(
    ALGORITHM_VECTOR        *toTest
    )
{
    return (!TEST_BOTH(ALG_AES_VALUE) && !TEST_BOTH(ALG_SM4_VALUE));
}

//*** AllModesAreDone()
// Checks if all the modes have been tested
//  Return Type: BOOL
//      TRUE(1)         all modes tested
//      FALSE(0)        all modes not tested
static BOOL
AllModesAreDone(
    ALGORITHM_VECTOR            *toTest
    )
{
    TPM_ALG_ID                  alg;
    for(alg = TPM_SYM_MODE_FIRST; alg <= TPM_SYM_MODE_LAST; alg++)
        if(TEST_BOTH(alg))
            return FALSE;
    return TRUE;
}

//*** TestSymmetric()
// If 'alg' is a symmetric block cipher, then all of the modes that are selected are
// tested. If 'alg' is a mode, then all algorithms of that mode are tested.
static TPM_RC
TestSymmetric(
    TPM_ALG_ID                   alg,
    ALGORITHM_VECTOR            *toTest
    )
{
    SYM_INDEX                    index;
    TPM_ALG_ID                   mode;
//
    if(!TEST_BIT(alg, *toTest))
        return TPM_RC_SUCCESS;
    if(alg == ALG_AES_VALUE || alg == ALG_SM4_VALUE || alg == ALG_CAMELLIA_VALUE)
    {
        // Will test the algorithm for all modes and key sizes
        CLEAR_BOTH(alg);

        // A test this algorithm for all modes
        for(index = 0; index < NUM_SYMS; index++)
        {
            if(c_symTestValues[index].alg == alg)
            {
                for(mode = TPM_SYM_MODE_FIRST;
                mode <= TPM_SYM_MODE_LAST;
                    mode++)
                {
                    if(TEST_BIT(mode, *toTest))
                        TestSymmetricAlgorithm(&c_symTestValues[index], mode);
                }
            }
        }
        // if all the symmetric tests are done
        if(AllSymsAreDone(toTest))
        {
            // all symmetric algorithms tested so no modes should be set
            for(alg = TPM_SYM_MODE_FIRST; alg <= TPM_SYM_MODE_LAST; alg++)
                CLEAR_BOTH(alg);
        }
    }
    else if(TPM_SYM_MODE_FIRST <= alg && alg <= TPM_SYM_MODE_LAST)
    {
        // Test this mode for all key sizes and algorithms
        for(index = 0; index < NUM_SYMS; index++)
        {
            // The mode testing only comes into play when doing self tests
            // by command. When doing self tests by command, the block ciphers are
            // tested first. That means that all of their modes would have been
            // tested for all key sizes. If there is no block cipher left to
            // test, then clear this mode bit.
            if(!TEST_BIT(ALG_AES_VALUE, *toTest)
               && !TEST_BIT(ALG_SM4_VALUE, *toTest))
            {
                CLEAR_BOTH(alg);
            }
            else
            {
                for(index = 0; index < NUM_SYMS; index++)
                {
                    if(TEST_BIT(c_symTestValues[index].alg, *toTest))
                        TestSymmetricAlgorithm(&c_symTestValues[index], alg);
                }
                // have tested this mode for all algorithms
                CLEAR_BOTH(alg);
            }
        }
        if(AllModesAreDone(toTest))
        {
            CLEAR_BOTH(ALG_AES_VALUE);
            CLEAR_BOTH(ALG_SM4_VALUE);
        }
    }
    else
        pAssert(alg == 0 && alg != 0);
    return TPM_RC_SUCCESS;
}

//** RSA Tests
#if ALG_RSA

//*** Introduction
// The tests are for public key only operations and for private key operations.
// Signature verification and encryption are public key operations. They are tested
// by using a KVT. For signature verification, this means that a known good
// signature is checked by CryptRsaValidateSignature(). If it fails, then the
// TPM enters failure mode. For encryption, the TPM encrypts known values using
// the selected scheme and checks that the returned value matches the expected
// value.
//
// For private key operations, a full scheme check is used. For a signing key, a
// known key is used to sign a known message. Then that signature is verified.
// since the signature may involve use of random values, the signature will be
// different each time and we can't always check that the signature matches a
// known value. The same technique is used for decryption (RSADP/RSAEP).
//
// When an operation uses the public key and the verification has not been
// tested, the TPM will do a KVT.
//
// The test for the signing algorithm is built into the call for the algorithm

//*** RsaKeyInitialize()
// The test key is defined by a public modulus and a private prime. The TPM's RSA
// code computes the second prime and the private exponent.
static void
RsaKeyInitialize(
    OBJECT          *testObject
    )
{
    MemoryCopy2B(&testObject->publicArea.unique.rsa.b, (P2B)&c_rsaPublicModulus,
                 sizeof(c_rsaPublicModulus));
    MemoryCopy2B(&testObject->sensitive.sensitive.rsa.b, (P2B)&c_rsaPrivatePrime,
                 sizeof(testObject->sensitive.sensitive.rsa.t.buffer));
    testObject->publicArea.parameters.rsaDetail.keyBits = RSA_TEST_KEY_SIZE * 8;
    // Use the default exponent
    testObject->publicArea.parameters.rsaDetail.exponent = 0;
}

//*** TestRsaEncryptDecrypt()
// These tests are for a public key encryption that uses a random value.
static TPM_RC
TestRsaEncryptDecrypt(
    TPM_ALG_ID           scheme,            // IN: the scheme
    ALGORITHM_VECTOR    *toTest             //
    )
{
    static TPM2B_PUBLIC_KEY_RSA      testInput;
    static TPM2B_PUBLIC_KEY_RSA      testOutput;
    static OBJECT                    testObject;
    const TPM2B_RSA_TEST_KEY        *kvtValue = NULL;
    TPM_RC                           result = TPM_RC_SUCCESS;
    const TPM2B                     *testLabel = NULL;
    TPMT_RSA_DECRYPT                 rsaScheme;
//
    // Don't need to initialize much of the test object
    RsaKeyInitialize(&testObject);
    rsaScheme.scheme = scheme;
    rsaScheme.details.anySig.hashAlg = DEFAULT_TEST_HASH;
    CLEAR_BOTH(scheme);
    CLEAR_BOTH(ALG_NULL_VALUE);
    if(scheme == ALG_NULL_VALUE)
    {
        // This is an encryption scheme using the private key without any encoding.
        memcpy(testInput.t.buffer, c_RsaTestValue, sizeof(c_RsaTestValue));
        testInput.t.size = sizeof(c_RsaTestValue);
        if(TPM_RC_SUCCESS != CryptRsaEncrypt(&testOutput, &testInput.b,
                                             &testObject, &rsaScheme, NULL, NULL))
            SELF_TEST_FAILURE;
        if(!MemoryEqual(testOutput.t.buffer, c_RsaepKvt.buffer, c_RsaepKvt.size))
            SELF_TEST_FAILURE;
        MemoryCopy2B(&testInput.b, &testOutput.b, sizeof(testInput.t.buffer));
        if(TPM_RC_SUCCESS != CryptRsaDecrypt(&testOutput.b, &testInput.b,
                                             &testObject, &rsaScheme, NULL))
            SELF_TEST_FAILURE;
        if(!MemoryEqual(testOutput.t.buffer, c_RsaTestValue,
                        sizeof(c_RsaTestValue)))
            SELF_TEST_FAILURE;
    }
    else
    {
        // ALG_RSAES_VALUE:
        // This is an decryption scheme using padding according to
        // PKCS#1v2.1, 7.2. This padding uses random bits. To test a public
        // key encryption that uses random data, encrypt a value and then
        // decrypt the value and see that we get the encrypted data back.
        // The hash is not used by this encryption so it can be TMP_ALG_NULL

        // ALG_OAEP_VALUE:
        // This is also an decryption scheme and it also uses a
        // pseudo-random
        // value. However, this also uses a hash algorithm. So, we may need
        // to test that algorithm before use.
        if(scheme == ALG_OAEP_VALUE)
        {
            TEST_DEFAULT_TEST_HASH(toTest);
            kvtValue = &c_OaepKvt;
            testLabel = OAEP_TEST_STRING;
        }
        else if(scheme == ALG_RSAES_VALUE)
        {
            kvtValue = &c_RsaesKvt;
            testLabel = NULL;
        }
        else
            SELF_TEST_FAILURE;
        // Only use a digest-size portion of the test value
        memcpy(testInput.t.buffer, c_RsaTestValue, DEFAULT_TEST_DIGEST_SIZE);
        testInput.t.size = DEFAULT_TEST_DIGEST_SIZE;

        // See if the encryption works
        if(TPM_RC_SUCCESS != CryptRsaEncrypt(&testOutput, &testInput.b,
                                             &testObject, &rsaScheme, testLabel,
                                             NULL))
            SELF_TEST_FAILURE;
        MemoryCopy2B(&testInput.b, &testOutput.b, sizeof(testInput.t.buffer));
        // see if we can decrypt this value and get the original data back
        if(TPM_RC_SUCCESS != CryptRsaDecrypt(&testOutput.b, &testInput.b,
                                             &testObject, &rsaScheme, testLabel))
            SELF_TEST_FAILURE;
        // See if the results compare
        if(testOutput.t.size != DEFAULT_TEST_DIGEST_SIZE
           || !MemoryEqual(testOutput.t.buffer, c_RsaTestValue,
                           DEFAULT_TEST_DIGEST_SIZE))
            SELF_TEST_FAILURE;
        // Now check that the decryption works on a known value
        MemoryCopy2B(&testInput.b, (P2B)kvtValue,
                     sizeof(testInput.t.buffer));
        if(TPM_RC_SUCCESS != CryptRsaDecrypt(&testOutput.b, &testInput.b,
                                             &testObject, &rsaScheme, testLabel))
            SELF_TEST_FAILURE;
        if(testOutput.t.size != DEFAULT_TEST_DIGEST_SIZE
           || !MemoryEqual(testOutput.t.buffer, c_RsaTestValue,
                           DEFAULT_TEST_DIGEST_SIZE))
            SELF_TEST_FAILURE;
    }
    return result;
}

//*** TestRsaSignAndVerify()
// This function does the testing of the RSA sign and verification functions. This
// test does a KVT.
static TPM_RC
TestRsaSignAndVerify(
    TPM_ALG_ID               scheme,
    ALGORITHM_VECTOR        *toTest
    )
{
    TPM_RC                      result = TPM_RC_SUCCESS;
    static OBJECT               testObject;
    static TPM2B_DIGEST         testDigest;
    static TPMT_SIGNATURE       testSig;

    // Do a sign and signature verification.
    // RSASSA:
    // This is a signing scheme according to PKCS#1-v2.1 8.2. It does not
    // use random data so there is a KVT for the signing operation. On
    // first use of the scheme for signing, use the TPM's RSA key to
    // sign a portion of c_RsaTestData and compare the results to c_RsassaKvt. Then
    // decrypt the data to see that it matches the starting value. This verifies
    // the signature with a KVT

    // Clear the bits indicating that the function has not been checked. This is to
    // prevent looping
    CLEAR_BOTH(scheme);
    CLEAR_BOTH(ALG_NULL_VALUE);
    CLEAR_BOTH(ALG_RSA_VALUE);

    RsaKeyInitialize(&testObject);
    memcpy(testDigest.t.buffer, (BYTE *)c_RsaTestValue, DEFAULT_TEST_DIGEST_SIZE);
    testDigest.t.size = DEFAULT_TEST_DIGEST_SIZE;
    testSig.sigAlg = scheme;
    testSig.signature.rsapss.hash = DEFAULT_TEST_HASH;

    // RSAPSS:
    // This is a signing scheme a according to PKCS#1-v2.2 8.1 it uses
    // random data in the signature so there is no KVT for the signing
    // operation. To test signing, the TPM will use the TPM's RSA key
    // to sign a portion of c_RsaTestValue and then it will verify the
    // signature. For verification, c_RsapssKvt is verified before the
    // user signature blob is verified. The worst case for testing of this
    // algorithm is two private and one public key operation.

    // The process is to sign known data. If RSASSA is being done, verify that the
    // signature matches the precomputed value. For both, use the signed value and
    // see that the verification says that it is a good signature. Then
    // if testing RSAPSS, do a verify of a known good signature. This ensures that
    // the validation function works.

    if(TPM_RC_SUCCESS != CryptRsaSign(&testSig, &testObject, &testDigest, NULL))
        SELF_TEST_FAILURE;
    // For RSASSA, make sure the results is what we are looking for
    if(testSig.sigAlg == ALG_RSASSA_VALUE)
    {
        if(testSig.signature.rsassa.sig.t.size != RSA_TEST_KEY_SIZE
           || !MemoryEqual(c_RsassaKvt.buffer,
                           testSig.signature.rsassa.sig.t.buffer,
                           RSA_TEST_KEY_SIZE))
            SELF_TEST_FAILURE;
    }
    // See if the TPM will validate its own signatures
    if(TPM_RC_SUCCESS != CryptRsaValidateSignature(&testSig, &testObject,
                                                   &testDigest))
        SELF_TEST_FAILURE;
    // If this is RSAPSS, check the verification with known signature
    // Have to copy because  CrytpRsaValidateSignature() eats the signature
    if(ALG_RSAPSS_VALUE == scheme)
    {
        MemoryCopy2B(&testSig.signature.rsapss.sig.b, (P2B)&c_RsapssKvt,
                     sizeof(testSig.signature.rsapss.sig.t.buffer));
        if(TPM_RC_SUCCESS != CryptRsaValidateSignature(&testSig, &testObject,
                                                       &testDigest))
            SELF_TEST_FAILURE;
    }
    return result;
}

//*** TestRSA()
// Function uses the provided vector to indicate which tests to run. It will clear
// the vector after each test is run and also clear g_toTest
static TPM_RC
TestRsa(
    TPM_ALG_ID               alg,
    ALGORITHM_VECTOR        *toTest
    )
{
    TPM_RC                  result = TPM_RC_SUCCESS;
//
    switch(alg)
    {
        case ALG_NULL_VALUE:
        // This is the RSAEP/RSADP function. If we are processing a list, don't
        // need to test these now because any other test will validate
        // RSAEP/RSADP. Can tell this is list of test by checking to see if
        // 'toTest' is pointing at g_toTest. If so, this is an isolated test
        // an need to go ahead and do the test;
            if((toTest == &g_toTest)
               || (!TEST_BIT(ALG_RSASSA_VALUE, *toTest)
                   && !TEST_BIT(ALG_RSAES_VALUE, *toTest)
                   && !TEST_BIT(ALG_RSAPSS_VALUE, *toTest)
                   && !TEST_BIT(ALG_OAEP_VALUE, *toTest)))
               // Not running a list of tests or no other tests on the list
               // so run the test now
                result = TestRsaEncryptDecrypt(alg, toTest);
            // if not running the test now, leave the bit on, just in case things
            // get interrupted
            break;
        case ALG_OAEP_VALUE:
        case ALG_RSAES_VALUE:
            result = TestRsaEncryptDecrypt(alg, toTest);
            break;
        case ALG_RSAPSS_VALUE:
        case ALG_RSASSA_VALUE:
            result = TestRsaSignAndVerify(alg, toTest);
            break;
        default:
            SELF_TEST_FAILURE;
    }
    return result;
}

#endif // ALG_RSA

//** ECC Tests

#if ALG_ECC

//*** LoadEccParameter()
// This function is mostly for readability and type checking
static void
LoadEccParameter(
    TPM2B_ECC_PARAMETER          *to,       // target
    const TPM2B_EC_TEST          *from      // source
    )
{
    MemoryCopy2B(&to->b, &from->b, sizeof(to->t.buffer));
}

//*** LoadEccPoint()
static void
LoadEccPoint(
    TPMS_ECC_POINT               *point,    // target
    const TPM2B_EC_TEST          *x,        // source
    const TPM2B_EC_TEST          *y
    )
{
    MemoryCopy2B(&point->x.b, (TPM2B *)x, sizeof(point->x.t.buffer));
    MemoryCopy2B(&point->y.b, (TPM2B *)y, sizeof(point->y.t.buffer));
}

//*** TestECDH()
// This test does a KVT on a point multiply.
static TPM_RC
TestECDH(
    TPM_ALG_ID          scheme,         // IN: for consistency
    ALGORITHM_VECTOR    *toTest         // IN/OUT: modified after test is run
    )
{
    static TPMS_ECC_POINT       Z;
    static TPMS_ECC_POINT       Qe;
    static TPM2B_ECC_PARAMETER  ds;
    TPM_RC                      result = TPM_RC_SUCCESS;
//
    NOT_REFERENCED(scheme);
    CLEAR_BOTH(ALG_ECDH_VALUE);
    LoadEccParameter(&ds, &c_ecTestKey_ds);
    LoadEccPoint(&Qe, &c_ecTestKey_QeX, &c_ecTestKey_QeY);
    if(TPM_RC_SUCCESS != CryptEccPointMultiply(&Z, c_testCurve, &Qe, &ds,
                                               NULL, NULL))
        SELF_TEST_FAILURE;
    if(!MemoryEqual2B(&c_ecTestEcdh_X.b, &Z.x.b)
       || !MemoryEqual2B(&c_ecTestEcdh_Y.b, &Z.y.b))
        SELF_TEST_FAILURE;
    return result;
}

//*** TestEccSignAndVerify()
static TPM_RC
TestEccSignAndVerify(
    TPM_ALG_ID                   scheme,
    ALGORITHM_VECTOR            *toTest
    )
{
    static OBJECT                testObject;
    static TPMT_SIGNATURE        testSig;
    static TPMT_ECC_SCHEME       eccScheme;

    testSig.sigAlg = scheme;
    testSig.signature.ecdsa.hash = DEFAULT_TEST_HASH;

    eccScheme.scheme = scheme;
    eccScheme.details.anySig.hashAlg = DEFAULT_TEST_HASH;

    CLEAR_BOTH(scheme);
    CLEAR_BOTH(ALG_ECDH_VALUE);

    // ECC signature verification testing uses a KVT.
    switch(scheme)
    {
        case ALG_ECDSA_VALUE:
            LoadEccParameter(&testSig.signature.ecdsa.signatureR, &c_TestEcDsa_r);
            LoadEccParameter(&testSig.signature.ecdsa.signatureS, &c_TestEcDsa_s);
            break;
        case ALG_ECSCHNORR_VALUE:
            LoadEccParameter(&testSig.signature.ecschnorr.signatureR,
                             &c_TestEcSchnorr_r);
            LoadEccParameter(&testSig.signature.ecschnorr.signatureS,
                             &c_TestEcSchnorr_s);
            break;
        case ALG_SM2_VALUE:
            // don't have a test for SM2
            return TPM_RC_SUCCESS;
        default:
            SELF_TEST_FAILURE;
            break;
    }
    TEST_DEFAULT_TEST_HASH(toTest);

    // Have to copy the key. This is because the size used in the test vectors
    // is the size of the ECC parameter for the test key while the size of a point
    // is TPM dependent
    MemoryCopy2B(&testObject.sensitive.sensitive.ecc.b, &c_ecTestKey_ds.b,
                 sizeof(testObject.sensitive.sensitive.ecc.t.buffer));
    LoadEccPoint(&testObject.publicArea.unique.ecc, &c_ecTestKey_QsX,
                 &c_ecTestKey_QsY);
    testObject.publicArea.parameters.eccDetail.curveID = c_testCurve;

    if(TPM_RC_SUCCESS != CryptEccValidateSignature(&testSig, &testObject,
                                                   (TPM2B_DIGEST *)&c_ecTestValue.b))
    {
        SELF_TEST_FAILURE;
    }
    CHECK_CANCELED;

    // Now sign and verify some data
    if(TPM_RC_SUCCESS != CryptEccSign(&testSig, &testObject,
                                      (TPM2B_DIGEST *)&c_ecTestValue,
                                      &eccScheme, NULL))
        SELF_TEST_FAILURE;

    CHECK_CANCELED;

    if(TPM_RC_SUCCESS != CryptEccValidateSignature(&testSig, &testObject,
                                                   (TPM2B_DIGEST *)&c_ecTestValue))
        SELF_TEST_FAILURE;

    CHECK_CANCELED;

    return TPM_RC_SUCCESS;
}

//*** TestKDFa()
static TPM_RC
TestKDFa(
    ALGORITHM_VECTOR        *toTest
    )
{
    static TPM2B_KDF_TEST_KEY   keyOut;
    UINT32                      counter = 0;
//
    CLEAR_BOTH(ALG_KDF1_SP800_108_VALUE);

    keyOut.t.size = CryptKDFa(KDF_TEST_ALG, &c_kdfTestKeyIn.b, &c_kdfTestLabel.b,
                              &c_kdfTestContextU.b, &c_kdfTestContextV.b,
                              TEST_KDF_KEY_SIZE * 8, keyOut.t.buffer,
                              &counter, FALSE);
    if (   keyOut.t.size != TEST_KDF_KEY_SIZE
        || !MemoryEqual(keyOut.t.buffer, c_kdfTestKeyOut.t.buffer,
                        TEST_KDF_KEY_SIZE))
        SELF_TEST_FAILURE;

    return TPM_RC_SUCCESS;
}

//*** TestEcc()
static TPM_RC
TestEcc(
    TPM_ALG_ID              alg,
    ALGORITHM_VECTOR        *toTest
    )
{
    TPM_RC                  result = TPM_RC_SUCCESS;
    NOT_REFERENCED(toTest);
    switch(alg)
    {
        case ALG_ECC_VALUE:
        case ALG_ECDH_VALUE:
            // If this is in a loop then see if another test is going to deal with
            // this.
            // If toTest is not a self-test list
            if((toTest == &g_toTest)
                // or this is the only ECC test in the list
               || !(TEST_BIT(ALG_ECDSA_VALUE, *toTest)
                    || TEST_BIT(ALG_ECSCHNORR, *toTest)
                    || TEST_BIT(ALG_SM2_VALUE, *toTest)))
            {
                result = TestECDH(alg, toTest);
            }
            break;
        case ALG_ECDSA_VALUE:
        case ALG_ECSCHNORR_VALUE:
        case ALG_SM2_VALUE:
            result = TestEccSignAndVerify(alg, toTest);
            break;
        default:
            SELF_TEST_FAILURE;
            break;
    }
    return result;
}

#endif // ALG_ECC

//*** TestAlgorithm()
// Dispatches to the correct test function for the algorithm or gets a list of
// testable algorithms.
//
// If 'toTest' is not NULL, then the test decisions are based on the algorithm
// selections in 'toTest'. Otherwise, 'g_toTest' is used. When bits are clear in
// 'g_toTest' they will also be cleared 'toTest'.
//
// If there doesn't happen to be a test for the algorithm, its associated bit is
// quietly cleared.
//
// If 'alg' is zero (TPM_ALG_ERROR), then the toTest vector is cleared of any bits
// for which there is no test (i.e. no tests are actually run but the vector is
// cleared).
//
// Note: 'toTest' will only ever have bits set for implemented algorithms but 'alg'
// can be anything.
//  Return Type: TPM_RC
//      TPM_RC_CANCELED     test was canceled
LIB_EXPORT
TPM_RC
TestAlgorithm(
    TPM_ALG_ID               alg,
    ALGORITHM_VECTOR        *toTest
    )
{
    TPM_ALG_ID              first = (alg == ALG_ERROR_VALUE) ? ALG_FIRST_VALUE : alg;
    TPM_ALG_ID              last = (alg == ALG_ERROR_VALUE) ? ALG_LAST_VALUE : alg;
    BOOL                    doTest = (alg != ALG_ERROR_VALUE);
    TPM_RC                  result = TPM_RC_SUCCESS;

    if(toTest == NULL)
        toTest = &g_toTest;

    // This is kind of strange. This function will either run a test of the selected
    // algorithm or just clear a bit if there is no test for the algorithm. So,
    // either this loop will be executed once for the selected algorithm or once for
    // each of the possible algorithms. If it is executed more than once ('alg' ==
    // ALG_ERROR), then no test will be run but bits will be cleared for
    // unimplemented algorithms. This was done this way so that there is only one
    // case statement with all of the algorithms. It was easier to have one case
    // statement than to have multiple ones to manage whenever an algorithm ID is
    // added.
    for(alg = first; (alg <= last); alg++)
    {
        // if 'alg' was TPM_ALG_ERROR, then we will be cycling through
        // values, some of which may not be implemented. If the bit in toTest
        // happens to be set, then we could either generated an assert, or just
        // silently CLEAR it. Decided to just clear.
        if(!TEST_BIT(alg, g_implementedAlgorithms))
        {
            CLEAR_BIT(alg, *toTest);
            continue;
        }
        // Process whatever is left.
        // NOTE: since this switch will only be called if the algorithm is
        // implemented, it is not necessary to modify this list except to comment
        // out the algorithms for which there is no test
        switch(alg)
        {
        // Symmetric block ciphers
#if ALG_AES
            case ALG_AES_VALUE:
#endif  // ALG_AES
#if ALG_SM4
            // if SM4 is implemented, its test is like other block ciphers but there
            // aren't any test vectors for it yet
//            case ALG_SM4_VALUE:
#endif  // ALG_SM4
#if ALG_CAMELLIA
            // no test vectors for camellia
//            case ALG_CAMELLIA_VALUE:
#endif
        // Symmetric modes
#if     !ALG_CFB
#   error   CFB is required in all TPM implementations
#endif // !ALG_CFB
            case ALG_CFB_VALUE:
                if(doTest)
                    result = TestSymmetric(alg, toTest);
                break;
#if ALG_CTR
            case ALG_CTR_VALUE:
#endif // ALG_CRT
#if ALG_OFB
            case ALG_OFB_VALUE:
#endif // ALG_OFB
#if ALG_CBC
            case ALG_CBC_VALUE:
#endif // ALG_CBC
#if ALG_ECB
            case ALG_ECB_VALUE:
#endif
                if(doTest)
                    result = TestSymmetric(alg, toTest);
                else
                    // If doing the initialization of g_toTest vector, only need
                    // to test one of the modes for the symmetric algorithms. If
                    // initializing for a SelfTest(FULL_TEST), allow all the modes.
                    if(toTest == &g_toTest)
                        CLEAR_BIT(alg, *toTest);
                break;
#if     !ALG_HMAC
#   error   HMAC is required in all TPM implementations
#endif
            case ALG_HMAC_VALUE:
                // Clear the bit that indicates that HMAC is required because
                // HMAC is used as the basic test for all hash algorithms.
                CLEAR_BOTH(alg);
                // Testing HMAC means test the default hash
                if(doTest)
                    TestHash(DEFAULT_TEST_HASH, toTest);
                else
                    // If not testing, then indicate that the hash needs to be
                    // tested because this uses HMAC
                    SET_BOTH(DEFAULT_TEST_HASH);
                break;
#if ALG_SHA1
            case ALG_SHA1_VALUE:
#endif // ALG_SHA1
#if ALG_SHA256
            case ALG_SHA256_VALUE:
#endif // ALG_SHA256
#if ALG_SHA384
            case ALG_SHA384_VALUE:
#endif // ALG_SHA384
#if ALG_SHA512
            case ALG_SHA512_VALUE:
#endif // ALG_SHA512
            // if SM3 is implemented its test is like any other hash, but there
            // aren't any test vectors yet.
#if ALG_SM3_256
//            case ALG_SM3_256_VALUE:
#endif // ALG_SM3_256
                if(doTest)
                    result = TestHash(alg, toTest);
                break;
    // RSA-dependent
#if ALG_RSA
            case ALG_RSA_VALUE:
                CLEAR_BOTH(alg);
                if(doTest)
                    result = TestRsa(ALG_NULL_VALUE, toTest);
                else
                    SET_BOTH(ALG_NULL_VALUE);
                break;
            case ALG_RSASSA_VALUE:
            case ALG_RSAES_VALUE:
            case ALG_RSAPSS_VALUE:
            case ALG_OAEP_VALUE:
            case ALG_NULL_VALUE:    // used or RSADP
                if(doTest)
                    result = TestRsa(alg, toTest);
                break;
#endif // ALG_RSA
#if ALG_KDF1_SP800_108
            case ALG_KDF1_SP800_108_VALUE:
                if(doTest)
                    result = TestKDFa(toTest);
                break;
#endif // ALG_KDF1_SP800_108
#if ALG_ECC
    // ECC dependent but no tests
    //        case ALG_ECDAA_VALUE:
    //        case ALG_ECMQV_VALUE:
    //        case ALG_KDF1_SP800_56a_VALUE:
    //        case ALG_KDF2_VALUE:
    //        case ALG_MGF1_VALUE:
            case ALG_ECC_VALUE:
                CLEAR_BOTH(alg);
                if(doTest)
                    result = TestEcc(ALG_ECDH_VALUE, toTest);
                else
                    SET_BOTH(ALG_ECDH_VALUE);
                break;
            case ALG_ECDSA_VALUE:
            case ALG_ECDH_VALUE:
            case ALG_ECSCHNORR_VALUE:
//            case ALG_SM2_VALUE:
                if(doTest)
                    result = TestEcc(alg, toTest);
                break;
#endif // ALG_ECC
            default:
                CLEAR_BIT(alg, *toTest);
                break;
        }
        if(result != TPM_RC_SUCCESS)
            break;
    }
    return result;
}

#endif // SELF_TESTS