Search prefix list for prefixes matching `query`.

            * `auth` [BaseAuth]
                AAA options.
            * `query` [dict_to_sql]
                How the search should be performed.
            * `search_options` [options_dict]
                Search options, see below.

            Returns a list of dicts.

            The `query` argument passed to this function is designed to be
            able to express quite advanced search filters. It is internally
            expanded to an SQL WHERE-clause.

            The `query` is a dict with three elements, where one specifies the
            operation to perform and the two other specifies its arguments. The
            arguments can themselves be `query` dicts, i.e. nested, to build
            more complex queries.

            The :attr:`operator` key specifies what operator should be used for the
            comparison. Currently the following operators are supported:

            * :data:`and` - Logical AND
            * :data:`or` - Logical OR
            * :data:`equals_any` - Equality of any element in array
            * :data:`equals` - Equality; =
            * :data:`not_equals` - Inequality; !=
            * :data:`less` - Less than; <
            * :data:`less_or_equal` - Less than or equal to; <=
            * :data:`greater` - Greater than; >
            * :data:`greater_or_equal` - Greater than or equal to; >=
            * :data:`like` - SQL LIKE
            * :data:`regex_match` - Regular expression match
            * :data:`regex_not_match` - Regular expression not match
            * :data:`contains` - IP prefix contains
            * :data:`contains_equals` - IP prefix contains or is equal to
            * :data:`contained_within` - IP prefix is contained within
            * :data:`contained_within_equals` - IP prefix is contained within or equals

            The :attr:`val1` and :attr:`val2` keys specifies the values which
            are subjected to the comparison. :attr:`val1` can be either any
            prefix attribute or a query dict. :attr:`val2` can be either the
            value you want to compare the prefix attribute to, or a `query`
            dict.

            Example 1 - Find the prefixes which contains 192.0.2.0/24::

                query = {
                    'operator': 'contains',
                    'val1': 'prefix',
                    'val2': '192.0.2.0/24'
                }

            This will be expanded to the pseudo-SQL query::

                SELECT * FROM prefix WHERE prefix contains '192.0.2.0/24'

            Example 2 - Find for all assignments in prefix 192.0.2.0/24::

                query = {
                    'operator': 'and',
                    'val1': {
                        'operator': 'equals',
                        'val1': 'type',
                        'val2': 'assignment'
                    },
                    'val2': {
                        'operator': 'contained_within',
                        'val1': 'prefix',
                        'val2': '192.0.2.0/24'
                    }
                }

            This will be expanded to the pseudo-SQL query::

                SELECT * FROM prefix WHERE (type == 'assignment') AND (prefix contained within '192.0.2.0/24')

            If you want to combine more than two expressions together with a
            boolean expression you need to nest them. For example, to match on
            three values, in this case the tag 'foobar' and a prefix-length
            between /10 and /24, the following could be used::

                query = {
                    'operator': 'and',
                    'val1': {
                        'operator': 'and',
                        'val1': {
                            'operator': 'greater',
                            'val1': 'prefix_length',
                            'val2': 9
                        },
                        'val2': {
                            'operator': 'less_or_equal',
                            'val1': 'prefix_length',
                            'val2': 24
                        }
                    },
                    'val2': {
                        'operator': 'equals_any',
                        'val1': 'tags',
                        'val2': 'foobar'
                    }
                }


            The `options` argument provides a way to alter the search result to
            assist in client implementations. Most options regard parent and
            children prefixes, that is the prefixes which contain the prefix(es)
            matching the search terms (parents) or the prefixes which are
            contained by the prefix(es) matching the search terms. The search
            options can also be used to limit the number of rows returned.

            The following options are available:
                * :attr:`parents_depth` - How many levels of parents to return. Set to :data:`-1` to include all parents.
                * :attr:`children_depth` - How many levels of children to return. Set to :data:`-1` to include all children.
                * :attr:`include_all_parents` - Include all parents, no matter what depth is specified.
                * :attr:`include_all_children` - Include all children, no matter what depth is specified.
                * :attr:`max_result` - The maximum number of prefixes to return (default :data:`50`).
                * :attr:`offset` - Offset the result list this many prefixes (default :data:`0`).

            The options above gives the possibility to specify how many levels
            of parent and child prefixes to return in addition to the prefixes
            that actually matched the search terms. This is done by setting the
            :attr:`parents_depth` and :attr:`children depth` keys in the
            `search_options` dict to an integer value.  In addition to this it
            is possible to get all all parents and/or children included in the
            result set even though they are outside the limits set with
            :attr:`*_depth`.  The extra prefixes included will have the
            attribute :attr:`display` set to :data:`false` while the other ones
            (the actual search result togther with the ones included due to
            given depth) :attr:`display` set to :data:`true`. This feature is
            usable obtain search results with some context given around them,
            useful for example when displaying prefixes in a tree without the
            need to implement client side IP address logic.

            This is the documentation of the internal backend function. It's
            exposed over XML-RPC, please also see the XML-RPC documentation for
            :py:func:`nipap.xmlrpc.NipapXMLRPC.search_prefix` for full
            understanding.

def search_prefix(self, auth, query, search_options=None):
        """ Search prefix list for prefixes matching `query`.

            * `auth` [BaseAuth]
                AAA options.
            * `query` [dict_to_sql]
                How the search should be performed.
            * `search_options` [options_dict]
                Search options, see below.

            Returns a list of dicts.

            The `query` argument passed to this function is designed to be
            able to express quite advanced search filters. It is internally
            expanded to an SQL WHERE-clause.

            The `query` is a dict with three elements, where one specifies the
            operation to perform and the two other specifies its arguments. The
            arguments can themselves be `query` dicts, i.e. nested, to build
            more complex queries.

            The :attr:`operator` key specifies what operator should be used for the
            comparison. Currently the following operators are supported:

            * :data:`and` - Logical AND
            * :data:`or` - Logical OR
            * :data:`equals_any` - Equality of any element in array
            * :data:`equals` - Equality; =
            * :data:`not_equals` - Inequality; !=
            * :data:`less` - Less than; <
            * :data:`less_or_equal` - Less than or equal to; <=
            * :data:`greater` - Greater than; >
            * :data:`greater_or_equal` - Greater than or equal to; >=
            * :data:`like` - SQL LIKE
            * :data:`regex_match` - Regular expression match
            * :data:`regex_not_match` - Regular expression not match
            * :data:`contains` - IP prefix contains
            * :data:`contains_equals` - IP prefix contains or is equal to
            * :data:`contained_within` - IP prefix is contained within
            * :data:`contained_within_equals` - IP prefix is contained within or equals

            The :attr:`val1` and :attr:`val2` keys specifies the values which
            are subjected to the comparison. :attr:`val1` can be either any
            prefix attribute or a query dict. :attr:`val2` can be either the
            value you want to compare the prefix attribute to, or a `query`
            dict.

            Example 1 - Find the prefixes which contains 192.0.2.0/24::

                query = {
                    'operator': 'contains',
                    'val1': 'prefix',
                    'val2': '192.0.2.0/24'
                }

            This will be expanded to the pseudo-SQL query::

                SELECT * FROM prefix WHERE prefix contains '192.0.2.0/24'

            Example 2 - Find for all assignments in prefix 192.0.2.0/24::

                query = {
                    'operator': 'and',
                    'val1': {
                        'operator': 'equals',
                        'val1': 'type',
                        'val2': 'assignment'
                    },
                    'val2': {
                        'operator': 'contained_within',
                        'val1': 'prefix',
                        'val2': '192.0.2.0/24'
                    }
                }

            This will be expanded to the pseudo-SQL query::

                SELECT * FROM prefix WHERE (type == 'assignment') AND (prefix contained within '192.0.2.0/24')

            If you want to combine more than two expressions together with a
            boolean expression you need to nest them. For example, to match on
            three values, in this case the tag 'foobar' and a prefix-length
            between /10 and /24, the following could be used::

                query = {
                    'operator': 'and',
                    'val1': {
                        'operator': 'and',
                        'val1': {
                            'operator': 'greater',
                            'val1': 'prefix_length',
                            'val2': 9
                        },
                        'val2': {
                            'operator': 'less_or_equal',
                            'val1': 'prefix_length',
                            'val2': 24
                        }
                    },
                    'val2': {
                        'operator': 'equals_any',
                        'val1': 'tags',
                        'val2': 'foobar'
                    }
                }


            The `options` argument provides a way to alter the search result to
            assist in client implementations. Most options regard parent and
            children prefixes, that is the prefixes which contain the prefix(es)
            matching the search terms (parents) or the prefixes which are
            contained by the prefix(es) matching the search terms. The search
            options can also be used to limit the number of rows returned.

            The following options are available:
                * :attr:`parents_depth` - How many levels of parents to return. Set to :data:`-1` to include all parents.
                * :attr:`children_depth` - How many levels of children to return. Set to :data:`-1` to include all children.
                * :attr:`include_all_parents` - Include all parents, no matter what depth is specified.
                * :attr:`include_all_children` - Include all children, no matter what depth is specified.
                * :attr:`max_result` - The maximum number of prefixes to return (default :data:`50`).
                * :attr:`offset` - Offset the result list this many prefixes (default :data:`0`).

            The options above gives the possibility to specify how many levels
            of parent and child prefixes to return in addition to the prefixes
            that actually matched the search terms. This is done by setting the
            :attr:`parents_depth` and :attr:`children depth` keys in the
            `search_options` dict to an integer value.  In addition to this it
            is possible to get all all parents and/or children included in the
            result set even though they are outside the limits set with
            :attr:`*_depth`.  The extra prefixes included will have the
            attribute :attr:`display` set to :data:`false` while the other ones
            (the actual search result togther with the ones included due to
            given depth) :attr:`display` set to :data:`true`. This feature is
            usable obtain search results with some context given around them,
            useful for example when displaying prefixes in a tree without the
            need to implement client side IP address logic.

            This is the documentation of the internal backend function. It's
            exposed over XML-RPC, please also see the XML-RPC documentation for
            :py:func:`nipap.xmlrpc.NipapXMLRPC.search_prefix` for full
            understanding.
        """

        if search_options is None:
            search_options = {}

        #
        # sanitize search options and set default if option missing
        #

        # include_parents
        if 'include_all_parents' not in search_options:
            search_options['include_all_parents'] = False
        else:
            if search_options['include_all_parents'] not in (True, False):
                raise NipapValueError('Invalid value for option ' +
                    "'include_all_parents'. Only true and false valid. Supplied value :'%s'" % unicode(search_options['include_all_parents']))

        # include_children
        if 'include_all_children' not in search_options:
            search_options['include_all_children'] = False
        else:
            if search_options['include_all_children'] not in (True, False):
                raise NipapValueError('Invalid value for option ' +
                    "'include_all_children'. Only true and false valid. Supplied value: '%s'" % unicode(search_options['include_all_children']))

        # parents_depth
        if 'parents_depth' not in search_options:
            search_options['parents_depth'] = 0
        else:
            try:
                search_options['parents_depth'] = int(search_options['parents_depth'])
            except (ValueError, TypeError):
                raise NipapValueError('Invalid value for option' +
                    ''' 'parent_depth'. Only integer values allowed.''')

        # children_depth
        if 'children_depth' not in search_options:
            search_options['children_depth'] = 0
        else:
            try:
                search_options['children_depth'] = int(search_options['children_depth'])
            except (ValueError, TypeError):
                raise NipapValueError('Invalid value for option' +
                    ''' 'children_depth'. Only integer values allowed.''')

        # include_neighbors
        if 'include_neighbors' not in search_options:
            search_options['include_neighbors'] = False
        else:
            if search_options['include_neighbors'] not in (True, False):
                raise NipapValueError('Invalid value for option ' +
                    "'include_neighbors'. Only true and false valid. Supplied value: '%s'" % unicode(search_options['include_neighbors']))

        # max_result
        if 'max_result' not in search_options:
            search_options['max_result'] = 50
        else:
            if search_options['max_result'] in (False, None):
                search_options['max_result'] = None
            else:
                try:
                    search_options['max_result'] = int(search_options['max_result'])
                except (ValueError, TypeError):
                    raise NipapValueError('Invalid value for option' +
                        ''' 'max_result'. Only integer values allowed.''')

        # offset
        if 'offset' not in search_options:
            search_options['offset'] = 0
        else:
            try:
                search_options['offset'] = int(search_options['offset'])
            except (ValueError, TypeError):
                raise NipapValueError('Invalid value for option' +
                    ''' 'offset'. Only integer values allowed.''')

        # parent_prefix
        if ('parent_prefix' not in search_options or
                search_options['parent_prefix'] is None):
            search_options['parent_prefix'] = None
        else:
            try:
                _ = int(search_options['parent_prefix'])
            except ValueError:
                raise NipapValueError(
                    "Invalid value '%s' for option 'parent_prefix'. Must be the ID of a prefix."
                        % search_options['parent_prefix'])
            try:
                parent_prefix = self.list_prefix(auth, { 'id': search_options['parent_prefix'] })[0]
            except IndexError:
                raise NipapNonExistentError("Parent prefix %s can not be found" % search_options['parent_prefix'])

        self._logger.debug('search_prefix search_options: %s' % unicode(search_options))

        # translate search options to SQL

        if search_options['include_all_parents'] or search_options['parents_depth'] == -1:
            where_parents = ''
        elif search_options['parents_depth'] >= 0:
            where_parents = 'AND p1.indent BETWEEN p2.indent - %d AND p1.indent' % search_options['parents_depth']
        else:
            raise NipapValueError("Invalid value for option 'parents_depth'. Only integer values > -1 allowed.")

        if search_options['include_all_children'] or search_options['children_depth'] == -1:
            where_children = ''
        elif search_options['children_depth'] >= 0:
            where_children = 'AND p1.indent BETWEEN p2.indent AND p2.indent + %d' % search_options['children_depth']
        else:
            raise NipapValueError("Invalid value for option 'children_depth'. Only integer values > -1 allowed.")

        if search_options['include_neighbors']:
            include_neighbors = 'true'
        else:
            include_neighbors = 'false'

        if search_options['parent_prefix']:
            vrf_id = 0
            if parent_prefix['vrf_id']:
                vrf_id = parent_prefix['vrf_id']
            where_parent_prefix = " WHERE (p1.vrf_id = %s AND iprange(p1.prefix) <<= iprange('%s') AND p1.indent <= %s) " % (vrf_id, parent_prefix['prefix'], parent_prefix['indent'] + 1)
            left_join = 'LEFT OUTER'
        else:
            where_parent_prefix = ''
            left_join = ''

        if search_options['max_result'] is None:
            limit_string = ""
        else:
            limit_string = "LIMIT %d" % (search_options['max_result'] + search_options['offset'])

        display = '(p1.prefix << p2.display_prefix OR p2.prefix <<= p1.prefix %s) OR (p2.prefix >>= p1.prefix %s)' % (where_parents, where_children)

        where, opt = self._expand_prefix_query(query)
        sql = """
    SELECT
        id,
        vrf_id,
        vrf_rt,
        vrf_name,
        family,
        display,
        match,
        prefix,
        prefix_length,
        display_prefix::text AS display_prefix,
        description,
        comment,
        inherited_tags,
        tags,
        node,
        pool_id,
        pool_name,
        type,
        status,
        indent,
        country,
        order_id,
        customer_id,
        external_key,
        authoritative_source,
        alarm_priority,
        monitor,
        vlan,
        added,
        last_modified,
        children,
        total_addresses,
        used_addresses,
        free_addresses,
        avps,
        expires
    FROM (
        SELECT DISTINCT ON(vrf_rt_order(vrf.rt), p1.prefix) p1.id,
            p1.prefix,
            p1.display_prefix,
            p1.description,
            p1.comment,
            COALESCE(p1.inherited_tags, '{}') AS inherited_tags,
            COALESCE(p1.tags, '{}') AS tags,
            p1.node,
            pool.id AS pool_id,
            pool.name AS pool_name,
            p1.type,
            p1.indent,
            p1.country,
            p1.order_id,
            p1.customer_id,
            p1.external_key,
            p1.authoritative_source,
            p1.alarm_priority,
            p1.monitor,
            p1.vlan,
            p1.added,
            p1.last_modified,
            p1.children,
            p1.total_addresses,
            p1.used_addresses,
            p1.free_addresses,
            p1.status,
            p1.avps,
            p1.expires,
            vrf.id AS vrf_id,
            vrf.rt AS vrf_rt,
            vrf.name AS vrf_name,
            masklen(p1.prefix) AS prefix_length,
            family(p1.prefix) AS family,
            (""" + display + """) AS display,
            CASE WHEN p1.prefix = p2.prefix THEN true ELSE false END AS match
            FROM ip_net_plan AS p1
            -- possible set LEFT OUTER JOIN, if we are doing a parent_prefix operation
            """ + left_join + """ JOIN ip_net_plan AS p2 ON
            (
                (
                    (p1.vrf_id = p2.vrf_id)
                    AND
                    (
                        -- Join in the parents (p1) of matching prefixes (p2)
                        (iprange(p1.prefix) >>= iprange(p2.prefix) """ + where_parents + """)
                        OR
                        -- Join in the children (p1) of matching prefixes (p2)
                        (iprange(p1.prefix) << iprange(p2.prefix) """ + where_children + """)
                        OR
                        -- Join in all neighbors (p1) of matching prefixes (p2)
                        (true = """ + include_neighbors + """ AND iprange(p1.prefix) << iprange(p2.display_prefix::cidr) AND p1.indent = p2.indent)
                    )
                )
                -- set match conditions for p2
                AND p2.id IN (
                    SELECT inp.id FROM ip_net_plan AS inp JOIN ip_net_vrf AS vrf ON inp.vrf_id = vrf.id LEFT JOIN ip_net_pool AS pool ON inp.pool_id = pool.id
                        WHERE """ + where + """
                    ORDER BY vrf_rt_order(vrf.rt) NULLS FIRST, prefix
                    """ + limit_string + """
                )
            )
            JOIN ip_net_vrf AS vrf ON (p1.vrf_id = vrf.id)
            LEFT JOIN ip_net_pool AS pool ON (p1.pool_id = pool.id)
            -- possible set where conditions, if we are doing a parent_prefix operation
            """ + where_parent_prefix + """
            ORDER BY vrf_rt_order(vrf.rt) NULLS FIRST, p1.prefix, CASE WHEN p1.prefix = p2.prefix THEN 0 ELSE 1 END OFFSET """  + unicode(search_options['offset']) + ") AS a ORDER BY vrf_rt_order(vrf_rt) NULLS FIRST, prefix"


        self._execute(sql, opt)

        result = list()
        for row in self._curs_pg:
            result.append(dict(row))
            # This is a SQL LIMIT clause implemented in Python. It is performed
            # here to avoid a silly planner missestimate in PostgreSQL. For too
            # low values of LIMIT, the planner will prefer plans with very low
            # startup costs which will in turn lead to the slow plan. We avoid
            # the low value (or any value really) of LIMIT by performing the
            # LIMIT in Python. There is still a LIMIT on the inner query which
            # together with the OFFSET, which is still performed in PostgreSQL,
            # yields a rather small result set and thus high speed.
            if search_options['max_result'] not in (False, None):
                if len(result) >= int(search_options['max_result']):
                    break

        return { 'search_options': search_options, 'result': result }