1 /*++ 2 Copyright (c) 2006 Microsoft Corporation 3 4 Module Name: 5 6 dl_relation_manager.h 7 8 Abstract: 9 10 <abstract> 11 12 Author: 13 14 Krystof Hoder (t-khoder) 2010-09-24. 15 16 Revision History: 17 18 --*/ 19 #pragma once 20 21 22 #include "util/map.h" 23 #include "util/vector.h" 24 #include "muz/rel/dl_base.h" 25 26 namespace datalog { 27 28 class context; 29 class dl_decl_util; 30 class table_relation; 31 class table_relation_plugin; 32 class finite_product_relation; 33 class finite_product_relation_plugin; 34 class sieve_relation; 35 class sieve_relation_plugin; 36 class rule_set; 37 38 39 class relation_manager { 40 class empty_signature_relation_join_fn; 41 class default_relation_join_project_fn; 42 class default_relation_select_equal_and_project_fn; 43 class default_relation_intersection_filter_fn; 44 class default_relation_filter_interpreted_and_project_fn; 45 class default_relation_apply_sequential_fn; 46 47 class auxiliary_table_transformer_fn; 48 class auxiliary_table_filter_fn; 49 50 class default_table_join_fn; 51 class default_table_project_fn; 52 class null_signature_table_project_fn; 53 class default_table_join_project_fn; 54 class default_table_rename_fn; 55 class default_table_union_fn; 56 class default_table_filter_equal_fn; 57 class default_table_filter_identical_fn; 58 class default_table_filter_interpreted_fn; 59 class default_table_filter_interpreted_and_project_fn; 60 class default_table_negation_filter_fn; 61 class default_table_filter_not_equal_fn; 62 class default_table_select_equal_and_project_fn; 63 class default_table_map_fn; 64 class default_table_project_with_reduce_fn; 65 66 typedef obj_map<func_decl, family_id> decl2kind_map; 67 68 typedef u_map<relation_plugin *> kind2plugin_map; 69 70 typedef map<const table_plugin *, table_relation_plugin *, ptr_hash<const table_plugin>, 71 ptr_eq<const table_plugin> > tp2trp_map; 72 typedef map<const relation_plugin *, finite_product_relation_plugin *, ptr_hash<const relation_plugin>, 73 ptr_eq<const relation_plugin> > rp2fprp_map; 74 75 typedef obj_map<func_decl, relation_base *> relation_map; 76 typedef ptr_vector<table_plugin> table_plugin_vector; 77 typedef ptr_vector<relation_plugin> relation_plugin_vector; 78 79 context & m_context; 80 table_plugin_vector m_table_plugins; 81 relation_plugin_vector m_relation_plugins; 82 //table_relation_plugins corresponding to table_plugins 83 tp2trp_map m_table_relation_plugins; 84 rp2fprp_map m_finite_product_relation_plugins; 85 86 kind2plugin_map m_kind2plugin; 87 88 table_plugin * m_favourite_table_plugin; 89 90 relation_plugin * m_favourite_relation_plugin; 91 92 relation_map m_relations; 93 94 decl_set m_saturated_rels; 95 96 family_id m_next_table_fid; 97 family_id m_next_relation_fid; 98 99 /** 100 Map specifying what kind of relation should be used to represent particular predicate. 101 */ 102 decl2kind_map m_pred_kinds; 103 104 void register_relation_plugin_impl(relation_plugin * plugin); 105 106 relation_manager(const relation_manager &); //private and undefined copy constructor 107 relation_manager & operator=(const relation_manager &); //private and undefined operator= 108 public: relation_manager(context & ctx)109 relation_manager(context & ctx) : 110 m_context(ctx), 111 m_favourite_table_plugin(nullptr), 112 m_favourite_relation_plugin(nullptr), 113 m_next_table_fid(0), 114 m_next_relation_fid(0) {} 115 116 virtual ~relation_manager(); 117 118 void reset(); 119 void reset_relations(); 120 get_context()121 context & get_context() const { return m_context; } 122 dl_decl_util & get_decl_util() const; 123 get_next_table_fid()124 family_id get_next_table_fid() { return m_next_table_fid++; } 125 family_id get_next_relation_fid(relation_plugin & claimer); 126 127 128 /** 129 Set what kind of relation is going to be used to represent the predicate \c pred. 130 131 This function can be called only before the relation object for \c pred is created 132 (i.e. before the \c get_relation function is called with \c pred as argument for the 133 first time). 134 */ 135 void set_predicate_kind(func_decl * pred, family_id kind); 136 /** 137 Return the relation kind that was requested to represent the predicate \c pred by 138 \c set_predicate_kind. If there was no such request, return \c null_family_id. 139 */ 140 family_id get_requested_predicate_kind(func_decl * pred); 141 relation_base & get_relation(func_decl * pred); 142 relation_base * try_get_relation(func_decl * pred) const; 143 /** 144 \brief Store the relation \c rel under the predicate \c pred. The \c relation_manager 145 takes over the relation object. 146 */ 147 void store_relation(func_decl * pred, relation_base * rel); 148 is_saturated(func_decl * pred)149 bool is_saturated(func_decl * pred) const { return m_saturated_rels.contains(pred); } mark_saturated(func_decl * pred)150 void mark_saturated(func_decl * pred) { m_saturated_rels.insert(pred); } reset_saturated_marks()151 void reset_saturated_marks() { 152 if(!m_saturated_rels.empty()) { 153 m_saturated_rels.reset(); 154 } 155 } 156 157 decl_set collect_predicates() const; 158 void collect_non_empty_predicates(decl_set & res) const; 159 void restrict_predicates(const decl_set & preds); 160 161 void register_plugin(table_plugin * plugin); 162 /** 163 table_relation_plugins should not be passed to this function since they are 164 created automatically when registering a table plugin. 165 */ register_plugin(relation_plugin * plugin)166 void register_plugin(relation_plugin * plugin) { 167 SASSERT(!plugin->from_table()); 168 register_relation_plugin_impl(plugin); 169 } 170 171 table_plugin & get_appropriate_plugin(const table_signature & t); 172 relation_plugin & get_appropriate_plugin(const relation_signature & t); 173 table_plugin * try_get_appropriate_plugin(const table_signature & t); 174 relation_plugin * try_get_appropriate_plugin(const relation_signature & t); 175 176 table_plugin * get_table_plugin(symbol const& s); 177 relation_plugin * get_relation_plugin(symbol const& s); 178 relation_plugin & get_relation_plugin(family_id kind); set_favourite_plugin(relation_plugin * p)179 void set_favourite_plugin(relation_plugin* p) { m_favourite_relation_plugin = p; } 180 table_relation_plugin & get_table_relation_plugin(table_plugin & tp); 181 bool try_get_finite_product_relation_plugin(const relation_plugin & inner, 182 finite_product_relation_plugin * & res); 183 184 table_base * mk_empty_table(const table_signature & s); 185 relation_base * mk_implicit_relation(const relation_signature & s, app * expr); 186 187 relation_base * mk_empty_relation(const relation_signature & s, family_id kind); 188 relation_base * mk_empty_relation(const relation_signature & s, func_decl* pred); 189 190 relation_base * mk_full_relation(const relation_signature & s, func_decl* pred, family_id kind); 191 relation_base * mk_full_relation(const relation_signature & s, func_decl* pred); 192 193 relation_base * mk_table_relation(const relation_signature & s, table_base * table); 194 bool mk_empty_table_relation(const relation_signature & s, relation_base * & result); 195 196 bool is_non_explanation(relation_signature const& s) const; 197 198 199 /** 200 \brief Convert relation value to table one. 201 202 This function can be called only for the relation sorts that have a table counterpart. 203 */ 204 void relation_to_table(const relation_sort & sort, const relation_element & from, table_element & to); 205 206 void table_to_relation(const relation_sort & sort, const table_element & from, relation_element & to); 207 void table_to_relation(const relation_sort & sort, const table_element & from, 208 const relation_fact::el_proxy & to); 209 void table_to_relation(const relation_sort & sort, const table_element & from, 210 relation_element_ref & to); 211 212 bool relation_sort_to_table(const relation_sort & from, table_sort & to); 213 void from_predicate(func_decl * pred, unsigned arg_index, relation_sort & result); 214 void from_predicate(func_decl * pred, relation_signature & result); 215 216 /** 217 \brief Convert relation signature to table signature and return true if successful. If false 218 is returned, the value of \c to is undefined. 219 */ 220 bool relation_signature_to_table(const relation_signature & from, table_signature & to); 221 222 void relation_fact_to_table(const relation_signature & s, const relation_fact & from, 223 table_fact & to); 224 void table_fact_to_relation(const relation_signature & s, const table_fact & from, 225 relation_fact & to); 226 227 228 229 // ----------------------------------- 230 // 231 // relation operations 232 // 233 // ----------------------------------- 234 235 //TODO: If multiple operation implementations are available, we may want to do something to 236 //select the best one here. 237 238 /** 239 If \c allow_product_relation is true, we will create a join that builds a product relation, 240 if there is no other way to do the join. If \c allow_product_relation is false, we will return 241 zero in that case. 242 */ 243 relation_join_fn * mk_join_fn(const relation_base & t1, const relation_base & t2, 244 unsigned col_cnt, const unsigned * cols1, const unsigned * cols2, bool allow_product_relation=true); 245 246 relation_join_fn * mk_join_fn(const relation_base & t1, const relation_base & t2, 247 const unsigned_vector & cols1, const unsigned_vector & cols2, bool allow_product_relation=true) { 248 SASSERT(cols1.size()==cols2.size()); 249 return mk_join_fn(t1, t2, cols1.size(), cols1.data(), cols2.data(), allow_product_relation); 250 } 251 252 /** 253 \brief Return functor that transforms a table into one that lacks columns listed in 254 \c removed_cols array. 255 256 The \c removed_cols contains columns of table \c t in strictly ascending order. 257 */ 258 relation_transformer_fn * mk_project_fn(const relation_base & t, unsigned col_cnt, 259 const unsigned * removed_cols); 260 mk_project_fn(const relation_base & t,const unsigned_vector & removed_cols)261 relation_transformer_fn * mk_project_fn(const relation_base & t, const unsigned_vector & removed_cols) { 262 return mk_project_fn(t, removed_cols.size(), removed_cols.data()); 263 } 264 265 /** 266 \brief Return an operation that is a composition of a join and a project operation. 267 */ 268 relation_join_fn * mk_join_project_fn(const relation_base & t1, const relation_base & t2, 269 unsigned joined_col_cnt, const unsigned * cols1, const unsigned * cols2, 270 unsigned removed_col_cnt, const unsigned * removed_cols, bool allow_product_relation_join=true); 271 272 relation_join_fn * mk_join_project_fn(const relation_base & t1, const relation_base & t2, 273 const unsigned_vector & cols1, const unsigned_vector & cols2, 274 const unsigned_vector & removed_cols, bool allow_product_relation_join=true) { 275 return mk_join_project_fn(t1, t2, cols1.size(), cols1.data(), cols2.data(), removed_cols.size(), 276 removed_cols.data(), allow_product_relation_join); 277 } 278 279 relation_transformer_fn * mk_rename_fn(const relation_base & t, unsigned permutation_cycle_len, 280 const unsigned * permutation_cycle); mk_rename_fn(const relation_base & t,const unsigned_vector & permutation_cycle)281 relation_transformer_fn * mk_rename_fn(const relation_base & t, const unsigned_vector & permutation_cycle) { 282 return mk_rename_fn(t, permutation_cycle.size(), permutation_cycle.data()); 283 } 284 285 /** 286 Like \c mk_rename_fn, only the permutation is not specified by cycle, but by a permutated array 287 of column number. 288 */ 289 relation_transformer_fn * mk_permutation_rename_fn(const relation_base & t, 290 const unsigned * permutation); mk_permutation_rename_fn(const relation_base & t,const unsigned_vector & permutation)291 relation_transformer_fn * mk_permutation_rename_fn(const relation_base & t, 292 const unsigned_vector & permutation) { 293 SASSERT(t.get_signature().size()==permutation.size()); 294 return mk_permutation_rename_fn(t, permutation.data()); 295 } 296 297 298 /** 299 The post-condition for an ideal union operation is be 300 301 Union(tgt, src, delta): 302 tgt_1==tgt_0 \union src 303 delta_1== delta_0 \union ( tgt_1 \setminus tgt_0 ) 304 305 A required post-condition is 306 307 Union(tgt, src, delta): 308 tgt_1==tgt_0 \union src 309 tgt_1==tgt_0 => delta_1==delta_0 310 delta_0 \subset delta_1 311 delta_1 \subset (delta_0 \union tgt_1) 312 ( tgt_1 \setminus tgt_0 ) \subset delta_1 313 314 So that a sufficient implementation is 315 316 Union(tgt, src, delta) { 317 oldTgt:=tgt.clone(); 318 tgt:=tgt \union src 319 if(tgt!=oldTgt) { 320 delta:=delta \union src //also ?delta \union tgt? would work 321 } 322 } 323 324 If rules are compiled with all_or_nothing_deltas parameter set to true, a sufficient 325 post-condition is 326 Union(tgt, src, delta): 327 tgt_1==tgt_0 \union src 328 (tgt_1==tgt_0 || delta_0 is non-empty) <=> delta_1 is non-empty 329 */ 330 relation_union_fn * mk_union_fn(const relation_base & tgt, const relation_base & src, 331 const relation_base * delta); 332 mk_union_fn(const relation_base & tgt,const relation_base & src)333 relation_union_fn * mk_union_fn(const relation_base & tgt, const relation_base & src) { 334 return mk_union_fn(tgt, src, static_cast<relation_base *>(nullptr)); 335 } 336 337 /** 338 Similar to union, but this one should be used inside loops to allow for abstract 339 domain convergence. 340 */ 341 relation_union_fn * mk_widen_fn(const relation_base & tgt, const relation_base & src, 342 const relation_base * delta); 343 344 relation_mutator_fn * mk_filter_identical_fn(const relation_base & t, unsigned col_cnt, 345 const unsigned * identical_cols); mk_filter_identical_fn(const relation_base & t,const unsigned_vector & identical_cols)346 relation_mutator_fn * mk_filter_identical_fn(const relation_base & t, const unsigned_vector & identical_cols) { 347 return mk_filter_identical_fn(t, identical_cols.size(), identical_cols.data()); 348 } 349 350 relation_mutator_fn * mk_filter_equal_fn(const relation_base & t, const relation_element & value, 351 unsigned col); 352 353 relation_mutator_fn * mk_filter_interpreted_fn(const relation_base & t, app * condition); 354 355 356 relation_transformer_fn * mk_filter_interpreted_and_project_fn(const relation_base & t, app * condition, 357 unsigned removed_col_cnt, const unsigned * removed_cols); 358 359 relation_mutator_fn * mk_apply_sequential_fn(unsigned n, relation_mutator_fn* * mutators); 360 361 362 /** 363 \brief Operations that returns all rows of \c t for which is column \c col equal to \c value 364 with the column \c col removed. 365 366 This operation can often be efficiently implemented and is useful for evaluating rules 367 of the form 368 369 F(x):-P("c",x). 370 */ 371 relation_transformer_fn * mk_select_equal_and_project_fn(const relation_base & t, 372 const relation_element & value, unsigned col); 373 374 375 relation_intersection_filter_fn * mk_filter_by_intersection_fn(const relation_base & tgt, 376 const relation_base & src, unsigned joined_col_cnt, 377 const unsigned * tgt_cols, const unsigned * src_cols); mk_filter_by_intersection_fn(const relation_base & tgt,const relation_base & src,const unsigned_vector & tgt_cols,const unsigned_vector & src_cols)378 relation_intersection_filter_fn * mk_filter_by_intersection_fn(const relation_base & tgt, 379 const relation_base & src, const unsigned_vector & tgt_cols, const unsigned_vector & src_cols) { 380 SASSERT(tgt_cols.size()==src_cols.size()); 381 return mk_filter_by_intersection_fn(tgt, src, tgt_cols.size(), tgt_cols.data(), src_cols.data()); 382 } 383 relation_intersection_filter_fn * mk_filter_by_intersection_fn(const relation_base & tgt, 384 const relation_base & src); 385 386 /** 387 The filter_by_negation postcondition: 388 filter_by_negation(tgt, neg, columns in tgt: c1,...,cN, 389 corresponding columns in neg: d1,...,dN): 390 tgt_1:={x: x\in tgt_0 && ! \exists y: ( y \in neg & pi_c1(x)= pi_d1(y) & ... & pi_cN(x)= pi_dN(y) ) } 391 */ 392 relation_intersection_filter_fn * mk_filter_by_negation_fn(const relation_base & t, 393 const relation_base & negated_obj, unsigned joined_col_cnt, 394 const unsigned * t_cols, const unsigned * negated_cols); mk_filter_by_negation_fn(const relation_base & t,const relation_base & negated_obj,const unsigned_vector & t_cols,const unsigned_vector & negated_cols)395 relation_intersection_filter_fn * mk_filter_by_negation_fn(const relation_base & t, 396 const relation_base & negated_obj, const unsigned_vector & t_cols, 397 const unsigned_vector & negated_cols) { 398 SASSERT(t_cols.size()==negated_cols.size()); 399 return mk_filter_by_negation_fn(t, negated_obj, t_cols.size(), t_cols.data(), negated_cols.data()); 400 } 401 402 403 // ----------------------------------- 404 // 405 // table operations 406 // 407 // ----------------------------------- 408 409 410 table_join_fn * mk_join_fn(const table_base & t1, const table_base & t2, 411 unsigned col_cnt, const unsigned * cols1, const unsigned * cols2); 412 mk_join_fn(const table_base & t1,const table_base & t2,const unsigned_vector & cols1,const unsigned_vector & cols2)413 table_join_fn * mk_join_fn(const table_base & t1, const table_base & t2, 414 const unsigned_vector & cols1, const unsigned_vector & cols2) { 415 SASSERT(cols1.size()==cols2.size()); 416 return mk_join_fn(t1, t2, cols1.size(), cols1.data(), cols2.data()); 417 } 418 419 /** 420 \brief Return functor that transforms a table into one that lacks columns listed in 421 \c removed_cols array. 422 423 The \c removed_cols contains columns of table \c t in strictly ascending order. 424 425 If a project operation removes a non-functional column, all functional columns become 426 non-functional (so that none of the values in functional columns are lost) 427 */ 428 table_transformer_fn * mk_project_fn(const table_base & t, unsigned col_cnt, 429 const unsigned * removed_cols); 430 mk_project_fn(const table_base & t,const unsigned_vector & removed_cols)431 table_transformer_fn * mk_project_fn(const table_base & t, const unsigned_vector & removed_cols) { 432 return mk_project_fn(t, removed_cols.size(), removed_cols.data()); 433 } 434 435 /** 436 \brief Return an operation that is a composition of a join and a project operation. 437 438 This operation is equivalent to the two operations performed separately, unless functional 439 columns are involved. 440 441 The ordinary project would make all of the functional columns into non-functional if any 442 non-functional column was removed. In function, however, we group columns into equivalence 443 classes (according to the equalities in \c cols1 and \c cols2) and make everything non-functional 444 only if some equivalence class of non-functional columns would have no non-functional columns 445 remain after the removal. 446 447 This behavior is implemented in the \c table_signature::from_join_project function. 448 */ 449 table_join_fn * mk_join_project_fn(const table_base & t1, const table_base & t2, 450 unsigned joined_col_cnt, const unsigned * cols1, const unsigned * cols2, 451 unsigned removed_col_cnt, const unsigned * removed_cols); 452 mk_join_project_fn(const table_base & t1,const table_base & t2,const unsigned_vector & cols1,const unsigned_vector & cols2,const unsigned_vector & removed_cols)453 table_join_fn * mk_join_project_fn(const table_base & t1, const table_base & t2, 454 const unsigned_vector & cols1, const unsigned_vector & cols2, 455 const unsigned_vector & removed_cols) { 456 return mk_join_project_fn(t1, t2, cols1.size(), cols1.data(), cols2.data(), removed_cols.size(), 457 removed_cols.data()); 458 } 459 460 table_transformer_fn * mk_rename_fn(const table_base & t, unsigned permutation_cycle_len, 461 const unsigned * permutation_cycle); mk_rename_fn(const table_base & t,const unsigned_vector & permutation_cycle)462 table_transformer_fn * mk_rename_fn(const table_base & t, const unsigned_vector & permutation_cycle) { 463 return mk_rename_fn(t, permutation_cycle.size(), permutation_cycle.data()); 464 } 465 466 /** 467 Like \c mk_rename_fn, only the permutation is not specified by cycle, but by a permutated array 468 of column number. 469 */ 470 table_transformer_fn * mk_permutation_rename_fn(const table_base & t, const unsigned * permutation); mk_permutation_rename_fn(const table_base & t,const unsigned_vector & permutation)471 table_transformer_fn * mk_permutation_rename_fn(const table_base & t, const unsigned_vector & permutation) { 472 SASSERT(t.get_signature().size()==permutation.size()); 473 return mk_permutation_rename_fn(t, permutation.data()); 474 } 475 476 477 /** 478 The post-condition for an ideal union operation is be 479 480 Union(tgt, src, delta): 481 tgt_1==tgt_0 \union src 482 delta_1== delta_0 \union ( tgt_1 \setminus tgt_0 ) 483 484 A required post-condition is 485 486 Union(tgt, src, delta): 487 tgt_1==tgt_0 \union src 488 tgt_1==tgt_0 => delta_1==delta_0 489 delta_0 \subset delta_1 490 delta_1 \subset (delta_0 \union tgt_1) 491 ( tgt_1 \setminus tgt_0 ) \subset delta_1 492 493 So that a sufficient implementation is 494 495 Union(tgt, src, delta) { 496 oldTgt:=tgt.clone(); 497 tgt:=tgt \union src 498 if(tgt!=oldTgt) { 499 delta:=delta \union src //also ?delta \union tgt? would work 500 } 501 } 502 503 If rules are compiled with all_or_nothing_deltas parameter set to true, a sufficient 504 post-condition is 505 Union(tgt, src, delta): 506 tgt_1==tgt_0 \union src 507 (tgt_1==tgt_0 || delta_0 is non-empty) <=> delta_1 is non-empty 508 */ 509 table_union_fn * mk_union_fn(const table_base & tgt, const table_base & src, 510 const table_base * delta); 511 mk_union_fn(const table_base & tgt,const table_base & src)512 table_union_fn * mk_union_fn(const table_base & tgt, const table_base & src) { 513 return mk_union_fn(tgt, src, static_cast<table_base *>(nullptr)); 514 } 515 516 /** 517 Similar to union, but this one should be used inside loops to allow for abstract 518 domain convergence. 519 */ 520 table_union_fn * mk_widen_fn(const table_base & tgt, const table_base & src, 521 const table_base * delta); 522 523 table_mutator_fn * mk_filter_identical_fn(const table_base & t, unsigned col_cnt, 524 const unsigned * identical_cols); mk_filter_identical_fn(const table_base & t,const unsigned_vector & identical_cols)525 table_mutator_fn * mk_filter_identical_fn(const table_base & t, const unsigned_vector & identical_cols) { 526 return mk_filter_identical_fn(t, identical_cols.size(), identical_cols.data()); 527 } 528 529 table_mutator_fn * mk_filter_equal_fn(const table_base & t, const table_element & value, 530 unsigned col); 531 532 table_mutator_fn * mk_filter_interpreted_fn(const table_base & t, app * condition); 533 534 table_transformer_fn * mk_filter_interpreted_and_project_fn(const table_base & t, app * condition, 535 unsigned removed_col_cnt, const unsigned * removed_cols); 536 537 /** 538 \brief Operations that returns all rows of \c t for which is column \c col equal to \c value 539 with the column \c col removed. 540 541 This operation can often be efficiently implemented and is useful for evaluating rules 542 of the form 543 544 F(x):-P("c",x). 545 */ 546 table_transformer_fn * mk_select_equal_and_project_fn(const table_base & t, 547 const table_element & value, unsigned col); 548 549 table_intersection_filter_fn * mk_filter_by_intersection_fn(const table_base & t, 550 const table_base & src, unsigned joined_col_cnt, const unsigned * t_cols, const unsigned * src_cols); mk_filter_by_intersection_fn(const table_base & t,const table_base & src,const unsigned_vector & t_cols,const unsigned_vector & src_cols)551 table_intersection_filter_fn * mk_filter_by_intersection_fn(const table_base & t, 552 const table_base & src, const unsigned_vector & t_cols, const unsigned_vector & src_cols) { 553 SASSERT(t_cols.size()==src_cols.size()); 554 return mk_filter_by_intersection_fn(t, src, t_cols.size(), t_cols.data(), src_cols.data()); 555 } 556 557 /** 558 The filter_by_negation postcondition: 559 filter_by_negation(tgt, neg, columns in tgt: c1,...,cN, 560 corresponding columns in neg: d1,...,dN): 561 tgt_1:={x: x\in tgt_0 && ! \exists y: ( y \in neg & pi_c1(x)= pi_d1(y) & ... & pi_cN(x)= pi_dN(y) ) } 562 */ 563 table_intersection_filter_fn * mk_filter_by_negation_fn(const table_base & t, const table_base & negated_obj, 564 unsigned joined_col_cnt, const unsigned * t_cols, const unsigned * negated_cols); mk_filter_by_negation_fn(const table_base & t,const table_base & negated_obj,const unsigned_vector & t_cols,const unsigned_vector & negated_cols)565 table_intersection_filter_fn * mk_filter_by_negation_fn(const table_base & t, const table_base & negated_obj, 566 const unsigned_vector & t_cols, const unsigned_vector & negated_cols) { 567 SASSERT(t_cols.size()==negated_cols.size()); 568 return mk_filter_by_negation_fn(t, negated_obj, t_cols.size(), t_cols.data(), negated_cols.data()); 569 } 570 571 /** 572 combined filter by negation with a join. 573 */ 574 table_intersection_join_filter_fn* mk_filter_by_negated_join_fn( 575 const table_base & t, 576 const table_base & src1, 577 const table_base & src2, 578 unsigned_vector const& t_cols, 579 unsigned_vector const& src_cols, 580 unsigned_vector const& src1_cols, 581 unsigned_vector const& src2_cols); 582 583 584 /** 585 \c t must contain at least one functional column. 586 587 Created object takes ownership of the \c mapper object. 588 */ 589 virtual table_mutator_fn * mk_map_fn(const table_base & t, table_row_mutator_fn * mapper); 590 591 /** 592 \c t must contain at least one functional column. 593 594 Created object takes ownership of the \c mapper object. 595 */ 596 virtual table_transformer_fn * mk_project_with_reduce_fn(const table_base & t, unsigned col_cnt, 597 const unsigned * removed_cols, table_row_pair_reduce_fn * reducer); 598 599 600 601 602 // ----------------------------------- 603 // 604 // output functions 605 // 606 // ----------------------------------- 607 608 609 std::string to_nice_string(const relation_element & el) const; 610 /** 611 This one may give a nicer representation of \c el than the 612 \c to_nice_string(const relation_element & el) function, by using the information about the sort 613 of the element. 614 */ 615 std::string to_nice_string(const relation_sort & s, const relation_element & el) const; 616 std::string to_nice_string(const relation_sort & s) const; 617 std::string to_nice_string(const relation_signature & s) const; 618 619 void display(std::ostream & out) const; 620 void display_relation_sizes(std::ostream & out) const; 621 void display_output_tables(rule_set const& rules, std::ostream & out) const; 622 623 private: 624 relation_intersection_filter_fn * try_mk_default_filter_by_intersection_fn(const relation_base & t, 625 const relation_base & src, unsigned joined_col_cnt, 626 const unsigned * t_cols, const unsigned * src_cols); 627 628 }; 629 630 /** 631 This is a helper class for relation_plugins whose relations can be of various kinds. 632 */ 633 template<class Spec, class Hash, class Eq=vector_eq_proc<Spec> > 634 class rel_spec_store { 635 typedef relation_signature::hash r_hash; 636 typedef relation_signature::eq r_eq; 637 638 typedef map<Spec, unsigned, Hash, Eq > family_id_idx_store; 639 typedef map<relation_signature, family_id_idx_store *, r_hash, r_eq> sig2store; 640 641 typedef u_map<Spec> family_id2spec; 642 typedef map<relation_signature, family_id2spec *, r_hash, r_eq> sig2spec_store; 643 644 relation_plugin & m_parent; 645 svector<family_id> m_allocated_kinds; 646 sig2store m_kind_assignment; 647 sig2spec_store m_kind_specs; 648 649 get_manager()650 relation_manager & get_manager() { return m_parent.get_manager(); } 651 add_new_kind()652 void add_new_kind() { 653 add_available_kind(get_manager().get_next_relation_fid(m_parent)); 654 } 655 656 public: rel_spec_store(relation_plugin & parent)657 rel_spec_store(relation_plugin & parent) : m_parent(parent) {} 658 ~rel_spec_store()659 ~rel_spec_store() { 660 reset_dealloc_values(m_kind_assignment); 661 reset_dealloc_values(m_kind_specs); 662 } 663 add_available_kind(family_id k)664 void add_available_kind(family_id k) { 665 m_allocated_kinds.push_back(k); 666 } 667 contains_signature(relation_signature const & sig)668 bool contains_signature(relation_signature const& sig) const { 669 return m_kind_assignment.contains(sig); 670 } 671 get_relation_kind(const relation_signature & sig,const Spec & spec)672 family_id get_relation_kind(const relation_signature & sig, const Spec & spec) { 673 typename sig2store::entry * e = m_kind_assignment.find_core(sig); 674 if(!e) { 675 e = m_kind_assignment.insert_if_not_there3(sig, alloc(family_id_idx_store)); 676 m_kind_specs.insert(sig, alloc(family_id2spec)); 677 } 678 family_id_idx_store & ids = *e->get_data().m_value; 679 680 unsigned res_idx; 681 if(!ids.find(spec, res_idx)) { 682 res_idx = ids.size(); 683 if(res_idx==m_allocated_kinds.size()) { 684 add_new_kind(); 685 } 686 SASSERT(res_idx<m_allocated_kinds.size()); 687 ids.insert(spec, res_idx); 688 689 family_id2spec * idspecs = m_kind_specs.find(sig); 690 idspecs->insert(m_allocated_kinds[res_idx], spec); 691 } 692 return m_allocated_kinds[res_idx]; 693 } 694 get_relation_spec(const relation_signature & sig,family_id kind,Spec & spec)695 void get_relation_spec(const relation_signature & sig, family_id kind, Spec & spec) { 696 family_id2spec * idspecs = m_kind_specs.find(sig); 697 spec = idspecs->find(kind); 698 } 699 700 }; 701 702 }; 703 704 705