cs_iterator_adapter.hpp

Go to the documentation of this file.

/*
 *      Copyright (c) 2023, an unpublished work by CodeSecure, Inc.
 *                      ALL RIGHTS RESERVED
 *
 *      Copyright (c) 2013-2023, an unpublished work by GrammaTech, Inc.
 *                      ALL RIGHTS RESERVED
 *
 *      This software is furnished under a license and may be used and
 *      copied only in accordance with the terms of such license and the
 *      inclusion of the above copyright notice.  This software or any
 *      other copies thereof may not be provided or otherwise made
 *      available to any other person.  Title to and ownership of the
 *      software is retained by CodeSecure, Inc.
 */

#ifndef CS_ITERATOR_ADAPTER_HPP
#define CS_ITERATOR_ADAPTER_HPP

/* Adapter for creating STL-style iterators from cs C API style
 * iterators. 
 */

#include "cs_result.h"
#include "cs_basic_types.h"
#include "cs_result.hpp"

namespace cs{

    template<typename policy> class iterator_adapter_mixin
    {
    protected:
        iterator_adapter_mixin(){}
    };

#ifndef CS_TEST_ITERATOR_ADAPTER_COUPLING
    template<typename elt> class mutable_set;
    template<typename elt> class immutable_set;
    template<typename T> class metric_manager;
    template<typename T> class metricclass_manager;
    class point;
    class symbol;
    class basic_block;
    class edge_label;
    class pdg_edge_label;
    class pdg_edge_kind;
    class project;
    class compunit;
    class procedure;
    class sfileinst;
    class sfile;
#endif

    template <typename policy>
    class iterator_adapter: public cs::iterator_adapter_mixin<policy>
    {
        friend class iterator_adapter_mixin<policy>;
        /* bridging the STL-style iterator with the first/next
         * interface turned out ugly.
         */
        typedef typename cglue<typename policy::key>::ctype ckey;
        typedef typename policy::key value_type;
        size_t position;
        /* This has to be a pointer for swap to work */
        mutable typename policy::iterator_impl *inner;
        /* This type should be a POD type, so we shouldn't run into
         * default ctor issues when we leave it uninitialized.
         */
        mutable cs_result last_r;
        /* EMPTY: The empty iterator, always "at_end()"
         * SINGLETON: Iterates over one value then finishes
         * INIT: Normal iterator, but hasn't actually started iterating yet
         * LAGGING: Has started iterating, but will need to invoke the
         * "next" function in order to get the current element.
         * LIVE: The current element is stashed in pending
         */
#ifndef SWIG
        mutable enum state_enum{EMPTY, SINGLETON, LAGGING, LIVE, INIT, INIT_LAGGING} state;
#endif
        mutable ckey pending;

        typename policy::ctype *container;
    private:
        void fetch(bool first) const
        {
            if( first )
            {
                assert( !inner );
                inner = new typename policy::iterator_impl;
                last_r = policy::iter_first(*container, &pending, inner);
            }
            else
            {
                last_r = policy::iter_next(*container, &pending, inner);
            }
        }
        
        void wake_up() const
        {
            state = LAGGING;
            for( size_t i = 0; i < position; i++ )
            {
                fetch( i == 0 );
                if( last_r != CS_SUCCESS )
                    return;
            }
        }
        
        void catch_up() const
        {
            if( state == INIT || state == INIT_LAGGING )
                wake_up();
            if( state == LAGGING )
            {
                state = LIVE;
                fetch( position == 0 );
            }
        }
        
        /* I have intentionally not defined the postfix ++ operator
         * since copying these iterators is so expensive. 
         */
        iterator_adapter operator++(int unused);
#ifdef SWIG
        iterator_adapter();
#endif
    public:
        typedef value_type                     *pointer;

        typedef const value_type               *const_pointer;

        typedef value_type                     &reference;

        typedef const value_type               &const_reference;

        typedef std::forward_iterator_tag       iterator_category;
        
    private:
        typedef typename policy::ctype          container_type;

    public:

        typedef cs_ssize_t                      difference_type;

        /* Start in an "INIT" state so that any initial copy
         * constructor calls are cheap.
         */
#ifndef SWIG
#ifndef CS_TEST_ITERATOR_ADAPTER_COUPLING
        /* These classes need to be able to invoke the next three
         * constructors, but user code shouldn't be able to do that.
         * So be friends with the classes that should be able to
         * construct us. We could use a client-attourney pattern here
         * to avoid giving full access to all these classes, but I
         * worry about stupid compilers not doing RVO.  You can define
         * CS_TEST_ITERATOR_ADAPTER_COUPLING to check if any private
         * fields are being inappropriately accessed by API code.
         */
    private:
        friend class sfileinst_color_map_iterator_policy;
        friend class ast_iterator_policy;
        friend class sfileinst_children_iterator_policy;
        friend class sfileinst;
        friend class ast;
        friend class procedure;
        friend class sfile;
        friend class project;
        friend class compunit;
        friend class directory;
        friend class amc;
        friend class amc_analysis;
        friend class point;
        friend class symbol;
        template <typename T>
        friend class mutable_set;
        template <typename T>
        friend class immutable_set;
        template <typename T>
        friend class metric_manager;
        template <typename T>
        friend class metricclass_manager;
#endif
        iterator_adapter(const container_type &s)
            : position(0)
            , inner(NULL)
            , last_r(CS_SUCCESS)
            , state(INIT)
            , container(new container_type(s))
        {
        }
        iterator_adapter()
            : position(0)
            , inner(NULL)
            , last_r(CS_OUT_OF_ELEMENTS)
            , state(EMPTY)
            , container(NULL)
        {
        }
        iterator_adapter(const ckey &value)
            : position(0)
            , inner(NULL)
            , last_r(CS_SUCCESS)
            , state(SINGLETON)
            , pending(value)
            , container(NULL)
        {
        }
    public:
        /* The C iterators don't really offer up an interface that
         * supports this well, so we end up doing something fairly
         * ugly.  We create a second iterator and then advance it the
         * appropriate number of times, assuming determinism.
         */
        iterator_adapter(const iterator_adapter &other)
            : position(other.position)
            , inner(NULL)
            , last_r(other.last_r)
            , state(other.state)
            , pending(other.pending)
            , container(NULL)
        {
            if( state == LIVE )
                state = INIT;
            else if( state == LAGGING )
                state = INIT_LAGGING;
            if( other.container )
                container = new container_type(*other.container);
        }
#endif
        ~iterator_adapter()
        { 
            if( inner )
            {
                policy::iter_close(inner);
                delete inner;
            }
            if( container )
                delete container;
        }
        
        bool at_end() const
        {
            /* If state is INIT and position != 0, then last_r is
             * dependable.
             */
            if( state != INIT || position == 0 )
                catch_up();
            return ( last_r == CS_OUT_OF_ELEMENTS );
        }
        
        void swap(iterator_adapter &other)
        {
            std::swap(inner, other.inner);
            std::swap(pending, other.pending);
            std::swap(last_r, other.last_r);
            std::swap(state, other.state);
            std::swap(position, other.position);
            std::swap(container, other.container);
        }

        iterator_adapter&
        operator=(iterator_adapter other)
        {
            swap(other);
            return *this;
        }
        
#if !defined(SWIGPYTHON) || !defined(SWIG)

        typename policy::key operator *() const
        {
            catch_up();
            check(last_r);
            return value_type::;
        }
#endif

        bool operator ==(const iterator_adapter& other) const
        {
            /* The most important thing to get right is that they are
             * equal if they are both at the end.
             */
            if( at_end() )
                return other.at_end();
            if( other.at_end() )
                return false;
            state_enum s1 = state;
            state_enum s2 = other.state;
            if( s1 != EMPTY && s1 != SINGLETON )
                s1 = LIVE;
            if( s2 != EMPTY && s2 != SINGLETON )
                s2 = LIVE;
            return s1 == s2
                && position == other.position;
        }

        bool operator !=(const iterator_adapter& other) const
        { return !(*this == other); }
        
#if !defined(SWIGPYTHON) || !defined(SWIG)

        void advance()
        {
            catch_up();
            if( last_r == CS_OUT_OF_ELEMENTS )
                return;
            if( state == SINGLETON )
                last_r = CS_OUT_OF_ELEMENTS;
            else
            {
                assert( state == LIVE );
                check(last_r);
                state = LAGGING;
            }
            position++;
        }
#endif

#ifndef SWIG
        /* I think SWIG will happily assume this returns a brand new
         * instance, and then cause use after free issues later.
         */

        iterator_adapter& operator++()
        {
            advance();
            return *this;
        }
#endif

#if defined(SWIGPYTHON) && defined(SWIG)
        /* SWIG has some trouble understanding the return type of next
         * if we implement these using %extend... so do this. */
        %extend{      
            /* Do this in python so swig doesn't get confused about
             * ownership... 
             */
            %pythoncode{
                 def __iter__(self): return self }
        }

        %extend{
             policy::key __next__()
             { 
                 try{
                     policy::key rv(**$self); /* this line may throw */
                     $self->advance();
                     return rv;
                 } catch(cs::result r) {
                     if( r == cs::result::OUT_OF_ELEMENTS )
                         /* python needs this instead */
                         throw swig::stop_iteration();
                     throw;
                 }
             }
        }
#endif
    private:
        std::string state_string() const
        {
            switch( state )
            {
            case SINGLETON:
                return " singleton";
            case EMPTY:
                return " end";
            default:
                if( position == 0 )
                    return " begin";
                return "";
            }
        }
    public:
        std::string as_string() const
        {
            return CS_AS_REPR_PREFIX
                + std::string(policy::name())
                + state_string()
                + CS_AS_REPR_SUFFIX;
        }

        std::string as_repr() const
        { return as_string(); }
    };

    template<typename policy>
    inline std::ostream &operator<<( 
        std::ostream &out, 
        const iterator_adapter<policy> &a )
    { return out << a.as_string(); }

}

namespace std{
    template<typename _Policy>
    inline void
    swap(cs::iterator_adapter<_Policy>& __x, cs::iterator_adapter<_Policy>& __y)
    { __x.swap(__y); }
}

#endif /* CS_ITERATOR_ADAPTER_HPP */