fts0ast.cc

Go to the documentation of this file.

/*****************************************************************************

Copyright (c) 2007, 2013, Oracle and/or its affiliates. All Rights Reserved.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation; version 2 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with
this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA

*****************************************************************************/

/**************************************************/
#include "mem0mem.h"
#include "fts0ast.h"
#include "fts0pars.h"
#include "fts0fts.h"

/* The FTS ast visit pass. */
enum fts_ast_visit_pass_t {
        FTS_PASS_FIRST,         
        FTS_PASS_EXIST,         
        FTS_PASS_IGNORE         
};

/******************************************************************/
static
fts_ast_node_t*
fts_ast_node_create(void)
/*=====================*/
{
        fts_ast_node_t* node;

        node = (fts_ast_node_t*) ut_malloc(sizeof(*node));
        memset(node, 0x0, sizeof(*node));

        return(node);
}

/******************************************************************/
UNIV_INTERN
fts_ast_node_t*
fts_ast_create_node_oper(
/*=====================*/
        void*           arg,                    
        fts_ast_oper_t  oper)                   
{
        fts_ast_node_t* node = fts_ast_node_create();

        node->type = FTS_AST_OPER;
        node->oper = oper;

        fts_ast_state_add_node((fts_ast_state_t*) arg, node);

        return(node);
}

/******************************************************************/
UNIV_INTERN
fts_ast_node_t*
fts_ast_create_node_term(
/*=====================*/
        void*           arg,                    
        const char*     ptr)                    
{
        fts_ast_state_t*        state = static_cast<fts_ast_state_t*>(arg);
        ulint                   len = strlen(ptr);
        ulint                   cur_pos = 0;
        fts_ast_node_t*         node = NULL;
        fts_ast_node_t*         node_list = NULL;
        fts_ast_node_t*         first_node = NULL;

        /* Scan the incoming string and filter out any "non-word" characters */
        while (cur_pos < len) {
                fts_string_t    str;
                ulint           offset;
                ulint           cur_len;

                cur_len = innobase_mysql_fts_get_token(
                        state->charset,
                        reinterpret_cast<const byte*>(ptr) + cur_pos,
                        reinterpret_cast<const byte*>(ptr) + len, &str, &offset);

                if (cur_len == 0) {
                        break;
                }

                cur_pos += cur_len;

                if (str.f_n_char > 0) {
                        /* If the subsequent term (after the first one)'s size
                        is less than fts_min_token_size, we shall ignore
                        that. This is to make consistent with MyISAM behavior */
                        if (first_node && (str.f_n_char < fts_min_token_size)) {
                                continue;
                        }

                        node = fts_ast_node_create();

                        node->type = FTS_AST_TERM;

                        node->term.ptr = static_cast<byte*>(ut_malloc(
                                str.f_len + 1));
                        memcpy(node->term.ptr, str.f_str, str.f_len);
                        node->term.ptr[str.f_len] = '\0';

                        fts_ast_state_add_node(
                                static_cast<fts_ast_state_t*>(arg), node);

                        if (first_node) {
                                /* There is more than one word, create
                                a list to organize them */
                                if (!node_list) {
                                        node_list = fts_ast_create_node_list(
                                                static_cast<fts_ast_state_t*>(
                                                        arg),
                                                 first_node);
                                }

                                fts_ast_add_node(node_list, node);
                        } else {
                                first_node = node;
                        }
                }
        }

        return((node_list != NULL) ? node_list : first_node);
}

/******************************************************************/
UNIV_INTERN
fts_ast_node_t*
fts_ast_create_node_text(
/*=====================*/
        void*           arg,                    
        const char*     ptr)                    
{
        ulint           len = strlen(ptr);
        fts_ast_node_t* node = NULL;


        ut_ad(len >= 1);

        if (len <= 2) {
                /* There is a way to directly supply null terminator
                in the query string (by using 0x220022) and get here,
                and certainly it would not make a valid query text */
                ut_ad(ptr[0] == '\"');

                if (len == 2) {
                        ut_ad(ptr[1] == '\"');
                }

                return(NULL);
        }

        node = fts_ast_node_create();

        len -= 2;

        node->type = FTS_AST_TEXT;
        node->text.ptr = static_cast<byte*>(ut_malloc(len + 1));

        memcpy(node->text.ptr, ptr + 1, len);
        node->text.ptr[len] = 0;
        node->text.distance = ULINT_UNDEFINED;

        fts_ast_state_add_node((fts_ast_state_t*) arg, node);

        return(node);
}

/******************************************************************/
UNIV_INTERN
fts_ast_node_t*
fts_ast_create_node_list(
/*=====================*/
        void*           arg,                    
        fts_ast_node_t* expr)                   
{
        fts_ast_node_t* node = fts_ast_node_create();

        node->type = FTS_AST_LIST;
        node->list.head = node->list.tail = expr;

        fts_ast_state_add_node((fts_ast_state_t*) arg, node);

        return(node);
}

/******************************************************************/
UNIV_INTERN
fts_ast_node_t*
fts_ast_create_node_subexp_list(
/*============================*/
        void*           arg,                    
        fts_ast_node_t* expr)                   
{
        fts_ast_node_t* node = fts_ast_node_create();

        node->type = FTS_AST_SUBEXP_LIST;
        node->list.head = node->list.tail = expr;

        fts_ast_state_add_node((fts_ast_state_t*) arg, node);

        return(node);
}

/******************************************************************/
static
void
fts_ast_free_list(
/*==============*/
        fts_ast_node_t* node)                   
{
        ut_a(node->type == FTS_AST_LIST
             || node->type == FTS_AST_SUBEXP_LIST);

        for (node = node->list.head;
             node != NULL;
             node = fts_ast_free_node(node)) {

        }
}

/********************************************************************/
UNIV_INTERN
fts_ast_node_t*
fts_ast_free_node(
/*==============*/
        fts_ast_node_t* node)                   
{
        fts_ast_node_t* next_node;

        switch (node->type) {
        case FTS_AST_TEXT:
                if (node->text.ptr) {
                        ut_free(node->text.ptr);
                        node->text.ptr = NULL;
                }
                break;

        case FTS_AST_TERM:
                if (node->term.ptr) {
                        ut_free(node->term.ptr);
                        node->term.ptr = NULL;
                }
                break;

        case FTS_AST_LIST:
        case FTS_AST_SUBEXP_LIST:
                fts_ast_free_list(node);
                node->list.head = node->list.tail = NULL;
                break;

        case FTS_AST_OPER:
                break;

        default:
                ut_error;
        }

        next_node = node->next;

        ut_free(node);

        return(next_node);
}

/******************************************************************/
UNIV_INTERN
fts_ast_node_t*
fts_ast_add_node(
/*=============*/
        fts_ast_node_t* node,                   
        fts_ast_node_t* elem)                   
{
        if (!elem) {
                return(NULL);
        }

        ut_a(!elem->next);
        ut_a(node->type == FTS_AST_LIST
             || node->type == FTS_AST_SUBEXP_LIST);

        if (!node->list.head) {
                ut_a(!node->list.tail);

                node->list.head = node->list.tail = elem;
        } else {
                ut_a(node->list.tail);

                node->list.tail->next = elem;
                node->list.tail = elem;
        }

        return(node);
}

/******************************************************************/
UNIV_INTERN
void
fts_ast_state_add_node(
/*===================*/
        fts_ast_state_t*state,                  
        fts_ast_node_t* node)                   
{
        if (!state->list.head) {
                ut_a(!state->list.tail);

                state->list.head = state->list.tail = node;
        } else {
                state->list.tail->next_alloc = node;
                state->list.tail = node;
        }
}

/******************************************************************/
UNIV_INTERN
void
fts_ast_term_set_wildcard(
/*======================*/
        fts_ast_node_t* node)                   
{
        if (!node) {
                return;
        }

        /* If it's a node list, the wildcard should be set to the tail node*/
        if (node->type == FTS_AST_LIST) {
                ut_ad(node->list.tail != NULL);
                node = node->list.tail;
        }

        ut_a(node->type == FTS_AST_TERM);
        ut_a(!node->term.wildcard);

        node->term.wildcard = TRUE;
}

/******************************************************************/
UNIV_INTERN
void
fts_ast_term_set_distance(
/*======================*/
        fts_ast_node_t* node,                   
        ulint           distance)               
{
        ut_a(node->type == FTS_AST_TEXT);
        ut_a(node->text.distance == ULINT_UNDEFINED);

        node->text.distance = distance;
}

/******************************************************************/
UNIV_INTERN
void
fts_ast_state_free(
/*===============*/
        fts_ast_state_t*state)                  
{
        fts_ast_node_t* node = state->list.head;

        /* Free the nodes that were allocated during parsing. */
        while (node) {
                fts_ast_node_t* next = node->next_alloc;

                if (node->type == FTS_AST_TEXT && node->text.ptr) {
                        ut_free(node->text.ptr);
                        node->text.ptr = NULL;
                } else if (node->type == FTS_AST_TERM && node->term.ptr) {
                        ut_free(node->term.ptr);
                        node->term.ptr = NULL;
                }

                ut_free(node);
                node = next;
        }

        state->root = state->list.head = state->list.tail = NULL;
}

/******************************************************************/
UNIV_INTERN
void
fts_ast_node_print(
/*===============*/
        fts_ast_node_t* node)                   
{
        switch (node->type) {
        case FTS_AST_TEXT:
                printf("TEXT: %s\n", node->text.ptr);
                break;

        case FTS_AST_TERM:
                printf("TERM: %s\n", node->term.ptr);
                break;

        case FTS_AST_LIST:
                printf("LIST: ");
                node = node->list.head;

                while (node) {
                        fts_ast_node_print(node);
                        node = node->next;
                }
                break;

        case FTS_AST_SUBEXP_LIST:
                printf("SUBEXP_LIST: ");
                node = node->list.head;

                while (node) {
                        fts_ast_node_print(node);
                        node = node->next;
                }
        case FTS_AST_OPER:
                printf("OPER: %d\n", node->oper);
                break;

        default:
                ut_error;
        }
}

/******************************************************************/
UNIV_INTERN
dberr_t
fts_ast_visit(
/*==========*/
        fts_ast_oper_t          oper,           
        fts_ast_node_t*         node,           
        fts_ast_callback        visitor,        
        void*                   arg,            
        bool*                   has_ignore)     
{
        dberr_t                 error = DB_SUCCESS;
        fts_ast_node_t*         oper_node = NULL;
        fts_ast_node_t*         start_node;
        bool                    revisit = false;
        bool                    will_be_ignored = false;
        fts_ast_visit_pass_t    visit_pass = FTS_PASS_FIRST;

        start_node = node->list.head;

        ut_a(node->type == FTS_AST_LIST
             || node->type == FTS_AST_SUBEXP_LIST);

        if (oper == FTS_EXIST_SKIP) {
                visit_pass = FTS_PASS_EXIST;
        } else if (oper == FTS_IGNORE_SKIP) {
                visit_pass = FTS_PASS_IGNORE;
        }

        /* In the first pass of the tree, at the leaf level of the
        tree, FTS_EXIST and FTS_IGNORE operation will be ignored.
        It will be repeated at the level above the leaf level.

        The basic idea here is that when we encounter FTS_EXIST or
        FTS_IGNORE, we will change the operator node into FTS_EXIST_SKIP
        or FTS_IGNORE_SKIP, and term node & text node with the operators
        is ignored in the first pass. We have two passes during the revisit:
        We process nodes with FTS_EXIST_SKIP in the exist pass, and then
        process nodes with FTS_IGNORE_SKIP in the ignore pass.

        The order should be restrictly followed, or we will get wrong results.
        For example, we have a query 'a +b -c d +e -f'.
        first pass: process 'a' and 'd' by union;
        exist pass: process '+b' and '+e' by intersection;
        ignore pass: process '-c' and '-f' by difference. */

        for (node = node->list.head;
             node && (error == DB_SUCCESS);
             node = node->next) {

                switch(node->type) {
                case FTS_AST_LIST:
                        if (visit_pass != FTS_PASS_FIRST) {
                                break;
                        }

                        error = fts_ast_visit(oper, node, visitor,
                                              arg, &will_be_ignored);

                        /* If will_be_ignored is set to true, then
                        we encountered and ignored a FTS_EXIST or FTS_IGNORE
                        operator. */
                        if (will_be_ignored) {
                                revisit = true;
                                /* Remember oper for list in case '-abc&def',
                                ignored oper is from previous node of list.*/
                                node->oper = oper;
                        }

                        break;

                case FTS_AST_SUBEXP_LIST:
                        if (visit_pass != FTS_PASS_FIRST) {
                                break;
                        }

                        error = fts_ast_visit_sub_exp(node, visitor, arg);
                        break;

                case FTS_AST_OPER:
                        oper = node->oper;
                        oper_node = node;

                        /* Change the operator for revisit */
                        if (oper == FTS_EXIST) {
                                oper_node->oper = FTS_EXIST_SKIP;
                        } else if (oper == FTS_IGNORE) {
                                oper_node->oper = FTS_IGNORE_SKIP;
                        }

                        break;

                default:
                        if (node->visited) {
                                continue;
                        }

                        ut_a(oper == FTS_NONE || !oper_node
                             || oper_node->oper == oper
                             || oper_node->oper == FTS_EXIST_SKIP
                             || oper_node->oper == FTS_IGNORE_SKIP);

                        if (oper== FTS_EXIST || oper == FTS_IGNORE) {
                                *has_ignore = true;
                                continue;
                        }

                        /* Process leaf node accroding to its pass.*/
                        if (oper == FTS_EXIST_SKIP
                            && visit_pass == FTS_PASS_EXIST) {
                                error = visitor(FTS_EXIST, node, arg);
                                node->visited = true;
                        } else if (oper == FTS_IGNORE_SKIP
                                   && visit_pass == FTS_PASS_IGNORE) {
                                error = visitor(FTS_IGNORE, node, arg);
                                node->visited = true;
                        } else if (visit_pass == FTS_PASS_FIRST) {
                                error = visitor(oper, node, arg);
                                node->visited = true;
                        }
                }
        }

        if (revisit) {
                /* Exist pass processes the skipped FTS_EXIST operation. */
                for (node = start_node;
                     node && error == DB_SUCCESS;
                     node = node->next) {

                        if (node->type == FTS_AST_LIST
                            && node->oper != FTS_IGNORE) {
                                error = fts_ast_visit(FTS_EXIST_SKIP, node,
                                        visitor, arg, &will_be_ignored);
                        }
                }

                /* Ignore pass processes the skipped FTS_IGNORE operation. */
                for (node = start_node;
                     node && error == DB_SUCCESS;
                     node = node->next) {

                        if (node->type == FTS_AST_LIST) {
                                error = fts_ast_visit(FTS_IGNORE_SKIP, node,
                                        visitor, arg, &will_be_ignored);
                        }
                }
        }

        return(error);
}