File cnf.c¶
File List > cubrid > src > parser > cnf.c
Go to the documentation of this file
/*
* Copyright 2008 Search Solution Corporation
* Copyright 2016 CUBRID Corporation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
*/
/*
* cnf.c - convert arbitrary boolean expressions to conjunctive normal form
*/
#ident "$Id$"
#include <stdarg.h>
#include <ctype.h>
#include <assert.h>
#include "error_manager.h"
#include "parser.h"
enum cnf_mode
{
TRANSFORM_CNF_OR_COMPACT = 0,
TRANSFORM_CNF_OR_PRUNE = 1, /* -- not used */
TRANSFORM_CNF_AND_OR = 2
};
typedef enum cnf_mode CNF_MODE;
typedef struct find_id_info FIND_ID_INFO;
struct find_id_info
{
UINTPTR id;
UINTPTR join_spec;
PT_NODE *in_query;
bool found;
bool tag_subqueries;
};
typedef struct similarity_context SIMILARITY_CONTEXT;
struct similarity_context
{
int max_number_of_nodes; /* the max number of nodes */
int number_of_nodes; /* the number of nodes */
unsigned int accumulated_opcode; /* the accumulated value of op type */
unsigned int accumulated_node_type; /* the accumulated value of node type */
};
static PT_NODE *pt_and_or_form (PARSER_CONTEXT * parser, PT_NODE * node);
static PT_NODE *pt_negate_expr (PARSER_CONTEXT * parser, PT_NODE * node);
#if defined(ENABLE_UNUSED_FUNCTION)
static PT_NODE *pt_aof_to_cnf (PARSER_CONTEXT * parser, PT_NODE * node);
static PT_NODE *pt_distributes_disjunction (PARSER_CONTEXT * parser, PT_NODE * node_1, PT_NODE * node_2);
static PT_NODE *pt_flatten_and_or (PARSER_CONTEXT * parser, PT_NODE * node);
#endif /* ENABLE_UNUSED_FUNCTION */
static int count_and_or (PARSER_CONTEXT * parser, const PT_NODE * node);
static PT_NODE *pt_transform_cnf_pre (PARSER_CONTEXT * parser, PT_NODE * node, void *arg, int *continue_walk);
static PT_NODE *pt_transform_cnf_post (PARSER_CONTEXT * parser, PT_NODE * node, void *arg, int *continue_walk);
static PT_NODE *pt_find_name_id_pre (PARSER_CONTEXT * parser, PT_NODE * tree, void *arg, int *continue_walk);
static PT_NODE *pt_find_name_id_post (PARSER_CONTEXT * parser, PT_NODE * tree, void *arg, int *continue_walk);
static void pt_tag_term_with_id (PARSER_CONTEXT * parser, PT_NODE * term, UINTPTR id, UINTPTR join_spec,
bool tag_subqueries);
static void pt_tag_terms_with_id (PARSER_CONTEXT * parser, PT_NODE * terms, UINTPTR id, UINTPTR join_spec);
static void pt_tag_terms_with_specs (PARSER_CONTEXT * parser, PT_NODE * terms, PT_NODE * join_spec, UINTPTR join_id);
static PT_NODE *pt_tag_start_of_cnf_post (PARSER_CONTEXT * parser, PT_NODE * node, void *arg, int *continue_walk);
static PT_NODE *pt_calculate_similarity (PARSER_CONTEXT * parser, PT_NODE * node, void *arg, int *continue_walk);
/*
* pt_tag_start_of_cnf_post() - labels the node as CNF start if it has
* logical descendants (next / or_next)
* and removes their is_cnf_start label.
* This way, only the actual cnf start
* node gets to keep its label.
*/
static PT_NODE *
pt_tag_start_of_cnf_post (PARSER_CONTEXT * parser, PT_NODE * node, void *arg, int *continue_walk)
{
if (node == NULL || node->type_enum != PT_TYPE_LOGICAL)
{
return node;
}
if (node->next && node->next->type_enum == PT_TYPE_LOGICAL)
{
node->next->flag.is_cnf_start = false;
}
if (node->or_next && node->or_next->type_enum == PT_TYPE_LOGICAL)
{
node->or_next->flag.is_cnf_start = false;
}
node->flag.is_cnf_start = true;
return node;
}
/*
* pt_and_or_form () - Converts a parse tree of boolean expressions into
* an equivalent tree which is in and-or form. the basic algorithm is to
* recursively push in negation.
* return: a pointer to a node of type PT_EXPR
* parser(in):
* node(in/out): a parse tree node of type PT_EXPR
*/
static PT_NODE *
pt_and_or_form (PARSER_CONTEXT * parser, PT_NODE * node)
{
PT_NODE *arg1, *temp;
PT_OP_TYPE neg_op_type;
switch (node->info.expr.op)
{
case PT_NOT:
/* unfold NOT expression */
arg1 = node->info.expr.arg1;
switch (arg1->info.expr.op)
{
case PT_NOT:
/* NOT (NOT expr) == expr */
node = pt_and_or_form (parser, arg1->info.expr.arg1);
/* free NOT node(arg1) */
arg1->info.expr.arg1 = NULL;
arg1->next = NULL;
arg1->or_next = NULL;
parser_free_tree (parser, arg1);
break;
case PT_AND:
/* NOT (expr AND expr) == (NOT expr) OR (NOT expr) */
node->info.expr.op = PT_OR;
temp = pt_negate_expr (parser, arg1->info.expr.arg1);
node->info.expr.arg1 = pt_and_or_form (parser, temp);
temp = pt_negate_expr (parser, arg1->info.expr.arg2);
node->info.expr.arg2 = pt_and_or_form (parser, temp);
break;
case PT_OR:
/* NOT (expr OR expr) == (NOT expr) AND (NOT expr) */
node->info.expr.op = PT_AND;
temp = pt_negate_expr (parser, arg1->info.expr.arg1);
node->info.expr.arg1 = pt_and_or_form (parser, temp);
temp = pt_negate_expr (parser, arg1->info.expr.arg2);
node->info.expr.arg2 = pt_and_or_form (parser, temp);
break;
default:
neg_op_type = pt_negate_op (arg1->info.expr.op);
if (neg_op_type != 0)
{
arg1->info.expr.op = neg_op_type;
/* free NOT node(node) */
node->info.expr.arg1 = NULL;
node->next = NULL;
node->or_next = NULL;
parser_free_tree (parser, node);
node = arg1;
}
break;
} /* switch (arg1->info.expr.op) */
break;
case PT_AND:
case PT_OR:
node->info.expr.arg1 = pt_and_or_form (parser, node->info.expr.arg1);
node->info.expr.arg2 = pt_and_or_form (parser, node->info.expr.arg2);
break;
default:
break;
} /* switch (node->info.expr.op) */
return node;
}
/*
* pt_negate_expr () - Converts a parse tree of boolean expressions into
* an equivalent tree which is in conjunctive normal form
* return: returns a pointer to a node of type PT_EXPR which itself is
* an expression of type PT_TYPE_LOGICAL except that it is negated.
* parser(in):
* node(in): a parse tree node of type PT_EXPR
*
* Note :
* the expression is created by creating a new node of type PT_EXPR and
* assigning new_node->arg1 the original node which was input,
* and assigning new_node->op the enum value PT_NOT
*/
static PT_NODE *
pt_negate_expr (PARSER_CONTEXT * parser, PT_NODE * node)
{
PT_NODE *temp;
PT_OP_TYPE neg_op_type;
neg_op_type = pt_negate_op (node->info.expr.op);
if (neg_op_type == 0)
{
if (node->info.expr.op == PT_NOT)
{
/* special case; negating 'NOT expr' */
temp = node->info.expr.arg1;
node->info.expr.arg1 = NULL;
node->next = NULL;
node->or_next = NULL;
parser_free_tree (parser, node);
node = temp;
}
else
{
/* making 'NOT expr' */
temp = parser_new_node (parser, PT_EXPR);
temp->type_enum = PT_TYPE_LOGICAL;
temp->info.expr.paren_type = node->info.expr.paren_type;
temp->info.expr.op = PT_NOT;
temp->info.expr.arg1 = node;
temp->info.expr.location = node->info.expr.location;
node = temp;
}
}
else
{
/* making 'arg1 <negated op> arg2' */
node->info.expr.op = neg_op_type;
}
return node;
}
#if defined(ENABLE_UNUSED_FUNCTION)
/*
* pt_aof_to_cnf () - Converts a parse tree of boolean expressions already in
* and-or-form into an equivalent tree which is in conjunctive normal form
* return: returns a pointer to a node of type PT_EXPR which itself
* is an expression of type PT_TYPE_LOGICAL.
* parser(in):
* node(in): a parse tree node of type PT_EXPR
*/
static PT_NODE *
pt_aof_to_cnf (PARSER_CONTEXT * parser, PT_NODE * node)
{
PT_NODE *result = node;
if (node->node_type != PT_EXPR && node->node_type != PT_VALUE)
{
PT_INTERNAL_ERROR (parser, "cnf");
}
switch (node->info.expr.op)
{
case PT_AND:
result->info.expr.arg1 = pt_aof_to_cnf (parser, node->info.expr.arg1);
result->info.expr.arg2 = pt_aof_to_cnf (parser, node->info.expr.arg2);
break;
case PT_OR:
result =
pt_distributes_disjunction (parser, pt_aof_to_cnf (parser, node->info.expr.arg1),
pt_aof_to_cnf (parser, node->info.expr.arg2));
break;
default:
break;
}
result->spec_ident = 0;
return result;
}
/*
* pt_distributes_disjunction () - distributes disjunction such that (P and Q)
* or R == (P or R) and (Q or R). If the two nodes are atoms or
* disjunctions, then a disjunctive expression is returned
* return: returns a pointer to a node of type PT_EXPR
* parser(in):
* node_1(in): a parse tree node of type PT_EXPR
* node_2(in): a parse tree node of type PT_EXPR
*/
static PT_NODE *
pt_distributes_disjunction (PARSER_CONTEXT * parser, PT_NODE * node_1, PT_NODE * node_2)
{
PT_NODE *new_node, *temp_1, *temp_2;
new_node = parser_new_node (parser, PT_EXPR);
if (new_node == NULL)
{
return NULL;
}
if (node_1->info.expr.op == PT_AND)
{
temp_1 = parser_new_node (parser, PT_EXPR);
if (temp_1 == NULL)
{
return NULL;
}
temp_1->type_enum = PT_TYPE_LOGICAL;
temp_1->info.expr.paren_type = 1;
temp_1->info.expr.op = PT_OR;
temp_1->info.expr.arg1 = node_1->info.expr.arg1;
temp_1->info.expr.arg2 = node_2;
temp_1->info.expr.location = node_1->info.expr.location;
temp_2 = parser_new_node (parser, PT_EXPR);
if (temp_2 == NULL)
{
return NULL;
}
temp_2->type_enum = PT_TYPE_LOGICAL;
temp_2->info.expr.paren_type = 1;
temp_2->info.expr.op = PT_OR;
temp_2->info.expr.arg1 = node_1->info.expr.arg2;
/* need to keep it a tree -- so copy */
temp_2->info.expr.arg2 = parser_copy_tree (parser, node_2);
temp_2->info.expr.location = node_1->info.expr.location;
new_node->type_enum = PT_TYPE_LOGICAL;
new_node->info.expr.paren_type = node_1->info.expr.paren_type;
new_node->info.expr.op = PT_AND;
new_node->info.expr.arg1 = pt_aof_to_cnf (parser, temp_1);
new_node->info.expr.arg2 = pt_aof_to_cnf (parser, temp_2);
new_node->info.expr.location = node_1->info.expr.location;
}
else if (node_2->info.expr.op == PT_AND)
{
temp_1 = parser_new_node (parser, PT_EXPR);
if (temp_1 == NULL)
{
return NULL;
}
temp_1->type_enum = PT_TYPE_LOGICAL;
temp_1->info.expr.paren_type = 1;
temp_1->info.expr.op = PT_OR;
temp_1->info.expr.arg1 = node_2->info.expr.arg1;
temp_1->info.expr.arg2 = node_1;
temp_1->info.expr.location = node_2->info.expr.location;
temp_2 = parser_new_node (parser, PT_EXPR);
if (temp_2 == NULL)
{
return NULL;
}
temp_2->type_enum = PT_TYPE_LOGICAL;
temp_2->info.expr.paren_type = 1;
temp_2->info.expr.op = PT_OR;
temp_2->info.expr.arg1 = node_2->info.expr.arg2;
/* need to keep it a tree -- so copy */
temp_2->info.expr.arg2 = parser_copy_tree (parser, node_1);
temp_2->info.expr.location = node_2->info.expr.location;
new_node->type_enum = PT_TYPE_LOGICAL;
new_node->info.expr.paren_type = node_2->info.expr.paren_type;
new_node->info.expr.op = PT_AND;
new_node->info.expr.arg1 = pt_aof_to_cnf (parser, temp_1);
new_node->info.expr.arg2 = pt_aof_to_cnf (parser, temp_2);
new_node->info.expr.location = node_2->info.expr.location;
}
else
{
new_node->type_enum = PT_TYPE_LOGICAL;
new_node->info.expr.paren_type = 1;
new_node->info.expr.op = PT_OR;
new_node->info.expr.arg1 = node_1;
new_node->info.expr.arg2 = node_2;
new_node->info.expr.location = node_1->info.expr.location;
}
return new_node;
}
/*
* pt_flatten_and_or () -
* return: a list of conjuncts which are implicitly anded together
* parser(in):
* node(in/out): a parse tree node of type PT_EXPR
*/
static PT_NODE *
pt_flatten_and_or (PARSER_CONTEXT * parser, PT_NODE * node)
{
PT_NODE *list;
assert (parser != NULL && node != NULL);
if (node->node_type != PT_EXPR && node->node_type != PT_VALUE)
{
PT_INTERNAL_ERROR (parser, "cnf");
}
list = node;
if (node->info.expr.op == PT_AND)
{
/* convert left part of AND into CNF */
list = pt_flatten_and_or (parser, node->info.expr.arg1);
/* convert right part of AND into CNF */
list = parser_append_node (pt_flatten_and_or (parser, node->info.expr.arg2), list);
/* free the AND node */
node->info.expr.arg1 = NULL;
node->info.expr.arg2 = NULL;
node->next = NULL;
node->or_next = NULL;
parser_free_tree (parser, node);
}
else if (node->info.expr.op == PT_OR)
{
/* convert left part of OR into CNF */
list = pt_flatten_and_or (parser, node->info.expr.arg1);
/* convert right part of OR into CNF */
list = parser_append_node_or (pt_flatten_and_or (parser, node->info.expr.arg2), list);
/* free the OR node */
node->info.expr.arg1 = NULL;
node->info.expr.arg2 = NULL;
node->next = NULL;
node->or_next = NULL;
parser_free_tree (parser, node);
}
return list;
}
#endif /* ENABLE_UNUSED_FUNCTION */
/*
* count_and_or () -
* return:
* parser(in):
* node(in):
*/
static int
count_and_or (PARSER_CONTEXT * parser, const PT_NODE * node)
{
int cnf_cnt, left, right;
switch (node->info.expr.op)
{
case PT_AND:
left = count_and_or (parser, node->info.expr.arg1);
if (left > 100) /* pruning */
{
return left;
}
right = count_and_or (parser, node->info.expr.arg2);
cnf_cnt = left + right;
break;
case PT_OR:
left = count_and_or (parser, node->info.expr.arg1);
if (left > 100) /* pruning */
{
return left;
}
right = count_and_or (parser, node->info.expr.arg2);
cnf_cnt = left * right;
break;
default:
cnf_cnt = 1;
break;
}
return cnf_cnt;
}
/*
* pt_transform_cnf_pre () -
* return:
* parser(in):
* node(in):
* arg(in):
* continue_walk(in/out):
*/
static PT_NODE *
pt_transform_cnf_pre (PARSER_CONTEXT * parser, PT_NODE * node, void *arg, int *continue_walk)
{
CNF_MODE *mode = (CNF_MODE *) arg;
if (!node || node->node_type != PT_EXPR)
{
if (node && node->node_type == PT_SELECT)
{
/* meet subquery in search condition. prune and go ahead */
*continue_walk = PT_STOP_WALK;
}
return node;
}
switch (node->info.expr.op)
{
case PT_AND:
break;
case PT_OR:
/* OR-tree prune mode */
if (*mode == TRANSFORM_CNF_OR_PRUNE)
{
*continue_walk = PT_STOP_WALK;
}
break;
default:
break;
}
return node;
}
/*
* pt_calculate_similarity () - calculate the similarity of the pt_node
* for quick comparision.
* return: PT_NODE
* parser(in):
* node(in):
* arg(in):
* continue_walk(in/out)
*/
static PT_NODE *
pt_calculate_similarity (PARSER_CONTEXT * parser, PT_NODE * node, void *arg, int *continue_walk)
{
SIMILARITY_CONTEXT *ctx = (SIMILARITY_CONTEXT *) arg;
ctx->number_of_nodes++;
if (ctx->max_number_of_nodes != -1 && ctx->number_of_nodes > ctx->max_number_of_nodes)
{
*continue_walk = PT_STOP_WALK;
return node;
}
ctx->accumulated_node_type *= PT_LAST_NODE_NUMBER;
ctx->accumulated_node_type += node->node_type;
if (node->node_type == PT_EXPR)
{
ctx->accumulated_opcode *= PT_LAST_OPCODE;
ctx->accumulated_opcode += node->info.expr.op;
}
if (node->flag.is_cnf_start)
{
*continue_walk = PT_CONTINUE_WALK;
}
else
{
*continue_walk = PT_LEAF_WALK;
}
return node;
}
/*
* pt_transform_cnf_post () -
* return: CNF/DNF list
* parser(in):
* node(in):
* arg(in):
* continue_walk(in/out):
*/
static PT_NODE *
pt_transform_cnf_post (PARSER_CONTEXT * parser, PT_NODE * node, void *arg, int *continue_walk)
{
PT_NODE *list, *lhs, *rhs, *last, *conj, *temp, *lhs_next, *rhs_next;
CNF_MODE *mode = (CNF_MODE *) arg;
unsigned int save_custom;
char *lhs_str, *rhs_str;
SIMILARITY_CONTEXT lhs_ctx, rhs_ctx;
PT_NODE *common_list, *lhs_prev, *rhs_prev, *arg1, *arg2;
bool common_found;
int num_markers;
int lhs_count, rhs_count;
if (!node || node->node_type != PT_EXPR)
{
if (node && node->node_type == PT_SELECT)
{
/* meet subquery in search condition. prune and go ahead */
*continue_walk = PT_CONTINUE_WALK;
}
return node;
}
switch (node->info.expr.op)
{
case PT_AND:
/* LHS CNF/DNF list AND RHS CNF/DNF list ==> LHS -(next)-> RHS */
/* append RHS list to LHS list */
list = node->info.expr.arg1;
for (last = list; last->next; last = last->next)
{
;
}
last->next = node->info.expr.arg2;
/* free AND node excluding LHS list and RHS list */
node->info.expr.arg1 = node->info.expr.arg2 = NULL;
/* AND node should not have 'next' and 'or_next' node->next = node->or_next = NULL */
parser_free_tree (parser, node);
break;
case PT_OR:
/* OR-tree prune mode */
if (*mode == TRANSFORM_CNF_OR_PRUNE)
{
list = node;
/* '*continue_walk' was changed to PT_STOP_WALK by pt_transform_cnf_pre() to prune OR-tree */
*continue_walk = PT_CONTINUE_WALK;
break;
}
save_custom = parser->custom_print;
parser->custom_print |= PT_CONVERT_RANGE;
common_list = NULL;
for (lhs = node->info.expr.arg1, lhs_count = 0; lhs; lhs = lhs->next)
{
++lhs_count;
}
for (rhs = node->info.expr.arg2, rhs_count = 0; rhs; rhs = rhs->next)
{
++rhs_count;
}
/* traverse LHS list */
lhs_prev = NULL;
for (lhs = node->info.expr.arg1; lhs; lhs = lhs_next)
{
lhs_next = lhs->next;
num_markers = 0;
(void) parser_walk_tree (parser, lhs, pt_count_input_markers, &num_markers, NULL, NULL);
if (num_markers > 0)
{ /* found input marker, give up */
lhs_prev = lhs;
continue;
}
common_found = false;
lhs_str = NULL;
lhs_ctx.max_number_of_nodes = -1;
lhs_ctx.number_of_nodes = 0;
lhs_ctx.accumulated_opcode = 0;
lhs_ctx.accumulated_node_type = 0;
(void) parser_walk_tree (parser, lhs, pt_calculate_similarity, &lhs_ctx, NULL, NULL);
/* traverse RHS list */
rhs_prev = NULL;
for (rhs = node->info.expr.arg2; rhs; rhs = rhs_next)
{
rhs_next = rhs->next;
rhs_ctx.max_number_of_nodes = lhs_ctx.number_of_nodes;
rhs_ctx.number_of_nodes = 0;
rhs_ctx.accumulated_opcode = 0;
rhs_ctx.accumulated_node_type = 0;
(void) parser_walk_tree (parser, rhs, pt_calculate_similarity, &rhs_ctx, NULL, NULL);
/*
* Because the cost of parser_print_tree() is very high. we use
* a simple way to test whether lhs and rhs node are similar.
* Only when they are similar, we call parser_print_tree().
*/
if (lhs_ctx.number_of_nodes == rhs_ctx.number_of_nodes
&& lhs_ctx.accumulated_node_type == rhs_ctx.accumulated_node_type
&& lhs_ctx.accumulated_opcode == rhs_ctx.accumulated_opcode)
{
if (lhs_str == NULL)
{
/* get parse tree string */
lhs_str = parser_print_tree (parser, lhs);
}
/* get parse tree string */
rhs_str = parser_print_tree (parser, rhs);
if (!pt_str_compare (lhs_str, rhs_str, CASE_SENSITIVE))
{ /* found common cnf */
common_found = true;
break;
}
}
rhs_prev = rhs;
}
if (common_found)
{
common_list = parser_append_node (parser_copy_tree (parser, lhs), common_list);
/* delete from lhs list */
if (lhs_prev == NULL)
{
node->info.expr.arg1 = lhs_next;
}
else
{
lhs_prev->next = lhs_next;
}
/* free compacted node */
lhs->next = NULL;
parser_free_tree (parser, lhs);
/* delete from rhs list */
if (rhs_prev == NULL)
{
node->info.expr.arg2 = rhs_next;
}
else
{
rhs_prev->next = rhs_next;
}
/* free compacted node */
rhs->next = NULL;
parser_free_tree (parser, rhs);
continue;
}
lhs_prev = lhs;
}
parser->custom_print = save_custom; /* restore */
lhs = node->info.expr.arg1;
rhs = node->info.expr.arg2;
/* fully compacted */
if (lhs == NULL || rhs == NULL)
{
/* free OR node excluding LHS list and RHS list */
node->info.expr.arg1 = node->info.expr.arg2 = NULL;
/* OR node should not have 'next' and 'or_next' node->next = node->or_next = NULL */
parser_free_tree (parser, node);
/* A and B or B ==> B and (A or true) ==> B */
list = common_list;
break;
}
/* OR-tree compact mode */
if (*mode == TRANSFORM_CNF_OR_COMPACT)
{
arg1 = arg2 = NULL; /* init */
/* rollback to AND-OR tree */
if (lhs)
{ /* build AND-tree */
lhs_next = lhs->next;
lhs->next = NULL;
arg1 = lhs;
for (lhs = lhs_next; lhs; lhs = lhs_next)
{
lhs_next = lhs->next;
lhs->next = NULL;
arg1 = pt_and (parser, arg1, lhs);
}
if (arg1 && arg1->info.expr.op == PT_AND)
{
arg1->info.expr.paren_type = 1;
}
}
if (rhs)
{ /* build AND-tree */
rhs_next = rhs->next;
rhs->next = NULL;
arg2 = rhs;
for (rhs = rhs_next; rhs; rhs = rhs_next)
{
rhs_next = rhs->next;
rhs->next = NULL;
arg2 = pt_and (parser, arg2, rhs);
}
if (arg2 && arg2->info.expr.op == PT_AND)
{
arg2->info.expr.paren_type = 1;
}
}
if (arg1 && arg2)
{ /* build OR-tree */
list = pt_and (parser, arg1, arg2);
list->info.expr.op = PT_OR;
}
else
{
/* A and B or B ==> B and (A or true) ==> B */
list = NULL;
}
if (list != NULL && list->info.expr.op == PT_OR)
{
list->info.expr.paren_type = 1;
}
list = parser_append_node (list, common_list);
break;
}
/* redo cnf transformation */
lhs = node->info.expr.arg1;
rhs = node->info.expr.arg2;
if (lhs->next == NULL && rhs->next == NULL)
{
/* special case; one LHS node OR one RHS node ==> LHS -(or_next)-> RHS */
/* append RHS node to LHS node */
list = node->info.expr.arg1;
for (temp = list; temp->or_next; temp = temp->or_next)
{
;
}
temp->or_next = node->info.expr.arg2;
/* free OR node excluding LHS list and RHS list */
node->info.expr.arg1 = node->info.expr.arg2 = NULL;
/* OR node should not have 'next' and 'or_next' node->next = node->or_next = NULL */
parser_free_tree (parser, node);
}
else
{
list = last = NULL;
/* traverse LHS list */
for (lhs = node->info.expr.arg1; lhs; lhs = lhs_next)
{
lhs_next = lhs->next;
lhs->next = NULL; /* cut off link temporarily */
/* traverse RHS list */
for (rhs = node->info.expr.arg2; rhs; rhs = rhs_next)
{
rhs_next = rhs->next;
rhs->next = NULL; /* cut off link temporarily */
/* clone LHS node (conjunctive) if RHS is the last node, this LHS is the last one to be used; so
* point to directly without cloning */
if (rhs_next == NULL)
conj = lhs;
else
conj = parser_copy_tree_list (parser, lhs);
/* append RHS node clone to LHS node clone */
for (temp = conj; temp->or_next; temp = temp->or_next)
{
;
}
/* if LHS is the last node, this RHS is the last one to be used; so point to directly without cloning
*/
if (lhs_next == NULL)
{
temp->or_next = rhs;
}
else
{
temp->or_next = parser_copy_tree_list (parser, rhs);
rhs->next = rhs_next; /* relink RHS list */
}
/* and then link the conjunctive to the CNF list */
if (last)
last->next = conj;
else
list = last = conj;
for (last = conj; last->next; last = last->next)
{
;
}
} /* for (rhs = ...) */
} /* for (lhs = ...) */
/* free OR node excluding LHS list and RHS list */
node->info.expr.arg1 = node->info.expr.arg2 = NULL;
/* OR node should not have 'next' and 'or_next' node->next = node->or_next = NULL */
parser_free_tree (parser, node);
}
list = parser_append_node (list, common_list);
break;
default:
list = node;
break;
} /* switch (node->info.expr.op) */
/* return CNF/DNF list */
return list;
}
/*
* pt_cnf () -
* return:
* parser(in):
* node(in/out):
*/
PT_NODE *
pt_cnf (PARSER_CONTEXT * parser, PT_NODE * node)
{
PT_NODE *list, *cnf, *next, *last;
CNF_MODE mode;
if (node == NULL)
{
return node;
}
list = last = NULL;
do
{
/* isolate this node */
next = node->next;
node->next = NULL;
if (node->node_type == PT_VALUE || PT_EXPR_INFO_IS_FLAGED (node, PT_EXPR_INFO_CNF_DONE))
{
/* if it is a value, it should be a const value which was a const expression and folded as a const value. if
* the case, skip this node and go ahead. */
/* if it is already in CNF */
cnf = node;
/* and then link it to the CNF list */
if (last)
{
last->next = cnf;
}
else
{
list = last = cnf;
}
/* adjust last pointer */
for (last = cnf; last->next; last = last->next)
{
;
}
}
else
{
/* transform the tree to AND-OR form which does not have NOT expression */
node = pt_and_or_form (parser, node);
/* if the number of result nodes of CNF list to be made is too big, do CNF transformation in OR-tree prune
* mode */
mode = (count_and_or (parser, node) > 100) ? TRANSFORM_CNF_OR_COMPACT : TRANSFORM_CNF_AND_OR;
/* transform the tree to CNF list */
cnf = parser_walk_tree (parser, node, pt_transform_cnf_pre, &mode, pt_transform_cnf_post, &mode);
/* and then link it to the CNF list */
if (last)
{
last->next = cnf;
}
else
{
list = last = cnf;
}
/* adjust last pointer and mark that they have been transformed */
for (last = cnf; last->next; last = last->next)
{
PT_EXPR_INFO_SET_FLAG (last, PT_EXPR_INFO_CNF_DONE);
}
PT_EXPR_INFO_SET_FLAG (last, PT_EXPR_INFO_CNF_DONE);
}
/* next node */
node = next;
}
while (next);
list = parser_walk_tree (parser, list, NULL, NULL, pt_tag_start_of_cnf_post, NULL);
return list;
}
/*
* pt_find_name_id_pre () -
* return: true if node is a name with the given spec id
* parser(in):
* tree(in):
* arg(in/out):
* continue_walk(in/out):
*/
static PT_NODE *
pt_find_name_id_pre (PARSER_CONTEXT * parser, PT_NODE * tree, void *arg, int *continue_walk)
{
FIND_ID_INFO *info = (FIND_ID_INFO *) arg;
*continue_walk = PT_CONTINUE_WALK;
if (tree->node_type == PT_NAME && tree->info.name.spec_id == info->id)
{
info->found = true;
}
else
{
if (PT_IS_QUERY_NODE_TYPE (tree->node_type))
{
if (tree->info.query.correlation_level == 1 && info->tag_subqueries && !info->in_query)
{
info->in_query = tree;
/* if this subquery is correlated 1, test it for tagging */
pt_tag_term_with_id (parser, tree, info->id, info->join_spec, false);
}
else if (tree->info.query.correlation_level == 0)
{
*continue_walk = PT_LIST_WALK;
}
}
}
return tree;
}
/*
* pt_find_name_id_post () - Resets the query node to zero on the way back up
* return:
* parser(in):
* tree(in):
* arg(in/out):
* continue_walk(in/out):
*/
static PT_NODE *
pt_find_name_id_post (PARSER_CONTEXT * parser, PT_NODE * tree, void *arg, int *continue_walk)
{
FIND_ID_INFO *info = (FIND_ID_INFO *) arg;
*continue_walk = PT_CONTINUE_WALK;
if (info->in_query == tree)
{
info->in_query = NULL;
}
return tree;
}
/*
* pt_tag_term_with_id () -
* return:
* parser(in):
* term(in/out): CNF tree
* id(in): spec id to test and tag term with
* join_spec(in):
* tag_subqueries(in):
*/
static void
pt_tag_term_with_id (PARSER_CONTEXT * parser, PT_NODE * term, UINTPTR id, UINTPTR join_spec, bool tag_subqueries)
{
FIND_ID_INFO info;
info.found = 0;
info.id = id;
info.join_spec = join_spec;
info.tag_subqueries = tag_subqueries;
info.in_query = NULL;
parser_walk_leaves (parser, term, pt_find_name_id_pre, &info, pt_find_name_id_post, &info);
if (info.found)
{
term->spec_ident = join_spec;
}
}
/*
* pt_tag_terms_with_id () -
* return:
* parser(in):
* terms(in/out): CNF tree
* id(in): spec id to test and tag term with
* join_spec(in):
*/
static void
pt_tag_terms_with_id (PARSER_CONTEXT * parser, PT_NODE * terms, UINTPTR id, UINTPTR join_spec)
{
while (terms)
{
if (terms->node_type == PT_EXPR && terms->info.expr.op == PT_AND)
{
pt_tag_terms_with_id (parser, terms->info.expr.arg1, id, join_spec);
pt_tag_terms_with_id (parser, terms->info.expr.arg2, id, join_spec);
}
else
{
pt_tag_term_with_id (parser, terms, id, join_spec, true);
}
terms = terms->next;
}
}
/*
* pt_tag_terms_with_specs () - test each term in the CNF predicate for
* membership of the spec id equivalence class, and tag the term if found
* return:
* parser(in):
* terms(in/out): CNF tree
* join_spec(in): specs to walk and tag terms of
* join_id(in):
*
* Note :
* The tag goes in the "etc" field.
* Specs visited last will override tags of earlier specs.
* In thi manner it is guaranteed that a predicate will be tagged
* the same left to right order (subpaths visited after node, and before
* rest of list) that the unoptimised query generation path will use.
* A term tagged with spec A will be guaranteed not to depend on
* a later join spec, B, or suppath spec C of A.
*
* WHACKED SPECS (specs representing selector variables) should not
* be used to tag terms since they will go away during XASL generation.
*/
static void
pt_tag_terms_with_specs (PARSER_CONTEXT * parser, PT_NODE * terms, PT_NODE * join_spec, UINTPTR join_id)
{
PT_NODE *specs = join_spec->info.spec.path_entities;
if (join_spec->info.spec.derived_table_type == PT_IS_WHACKED_SPEC)
{
return;
}
pt_tag_terms_with_id (parser, terms, join_spec->info.spec.id, join_id);
while (specs)
{
pt_tag_terms_with_specs (parser, terms, specs, join_id);
specs = specs->next;
}
}
/*
* pt_do_cnf () - apply pt_cnf to search conditions
* return:
* parser(in): the parser context used to derive the node
* node(in/out): parse tree node of a sql statement
* dummy(in): not used but required by parser_walk_tree functions
* continue_walk(in): used for pruning fruitless subtree walks
*/
PT_NODE *
pt_do_cnf (PARSER_CONTEXT * parser, PT_NODE * node, void *arg, int *continue_walk)
{
PT_NODE *list, *spec;
/* only do CNF conversion if it is SELECT */
if (node->node_type != PT_SELECT)
{
return node;
}
/* do CNF conversion if it has WHERE */
list = node->info.query.q.select.where;
if (list)
{
/* to make pt_cnf() work */
for (; list; list = list->next)
{
PT_EXPR_INFO_CLEAR_FLAG (list, PT_EXPR_INFO_CNF_DONE);
}
/* do CNF transformation */
node->info.query.q.select.where = pt_cnf (parser, node->info.query.q.select.where);
/* test each term in the CNF predicate for membership of the spec id */
for (spec = node->info.query.q.select.from; spec; spec = spec->next)
{
pt_tag_terms_with_specs (parser, node->info.query.q.select.where, spec, spec->info.spec.id);
}
}
/* do CNF conversion if it has HAVING */
list = node->info.query.q.select.having;
if (list)
{
/* to make pt_cnf() work */
for (; list; list = list->next)
{
PT_EXPR_INFO_CLEAR_FLAG (list, PT_EXPR_INFO_CNF_DONE);
}
/* do CNF transformation */
node->info.query.q.select.having = pt_cnf (parser, node->info.query.q.select.having);
}
return node;
}