1 /* Part of SWI-Prolog 2 3 Author: Jan Wielemaker 4 E-mail: J.Wielemaker@vu.nl 5 WWW: http://www.swi-prolog.org 6 Copyright (c) 2016-2020, VU University Amsterdam 7 CWI, Amsterdam 8 All rights reserved. 9 10 Redistribution and use in source and binary forms, with or without 11 modification, are permitted provided that the following conditions 12 are met: 13 14 1. Redistributions of source code must retain the above copyright 15 notice, this list of conditions and the following disclaimer. 16 17 2. Redistributions in binary form must reproduce the above copyright 18 notice, this list of conditions and the following disclaimer in 19 the documentation and/or other materials provided with the 20 distribution. 21 22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 25 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 26 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 27 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 28 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 29 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 30 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 32 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 33 POSSIBILITY OF SUCH DAMAGE. 34 */ 35 36 #ifndef _PL_TABLING_H 37 #define _PL_TABLING_H 38 #include "pl-trie.h" 39 40 typedef enum 41 { CLUSTER_ANSWERS, 42 CLUSTER_SUSPENSIONS 43 } cluster_type; 44 45 #define DELAY_MAGIC 0x67e9124d 46 #define WORKLIST_MAGIC 0x67e9124e 47 #define COMPONENT_MAGIC 0x67e9124f 48 49 50 /******************************* 51 * GLOBAL ENTRY POINTS * 52 *******************************/ 53 54 typedef struct worklist_set 55 { buffer members; 56 } worklist_set; 57 58 typedef struct component_set 59 { buffer members; 60 } component_set; 61 62 typedef enum 63 { SCC_ACTIVE=0, 64 SCC_MERGED, 65 SCC_COMPLETED 66 } scc_status; 67 68 typedef enum 69 { SCC_NEG_NONE=0, /* no negative nodes */ 70 SCC_NEG_DELAY, 71 SCC_NEG_SIMPLIFY 72 } scc_neg_status; 73 74 typedef struct tbl_component 75 { int magic; /* COMPONENT_MAGIC */ 76 scc_status status; /* SCC_* */ 77 scc_neg_status neg_status; /* SCC_NEG_* */ 78 size_t simplifications; /* # simplifications */ 79 struct tbl_component *parent; 80 component_set *children; /* Child components */ 81 component_set *merged; /* Child components */ 82 worklist_set *worklist; /* Worklist of current query */ 83 worklist_set *created_worklists; /* Worklists created */ 84 worklist_set *delay_worklists; /* Worklists in need for delays */ 85 trie *leader; /* Leading variant */ 86 } tbl_component; 87 88 typedef struct tbl_status 89 { tbl_component *scc; 90 int hsc; 91 int iac; 92 } tbl_status; 93 94 void save_tabling_status(tbl_status *stat); 95 void restore_tabling_status(tbl_status *stat); 96 97 98 /******************************* 99 * TABLE WORKLIST * 100 *******************************/ 101 102 typedef struct cluster 103 { cluster_type type; 104 struct cluster *next; 105 struct cluster *prev; 106 buffer members; 107 } cluster; 108 109 typedef struct worklist 110 { cluster *head; /* answer and dependency clusters */ 111 cluster *tail; 112 cluster *riac; /* rightmost inner answer cluster */ 113 cluster *free_clusters; /* clusters to reuse */ 114 int magic; /* WORKLIST_MAGIC */ 115 unsigned ground : 1; /* Ground call (early completion) */ 116 unsigned executing : 1; /* $tbl_wkl_work/3 in progress */ 117 unsigned in_global_wl : 1; /* already in global worklist */ 118 unsigned negative : 1; /* this is a suspended negation */ 119 unsigned neg_delayed : 1; /* Negative node was delayed */ 120 unsigned has_answers : 1; /* At least one unconditional answer */ 121 unsigned answer_completed : 1; /* Is answer completed */ 122 unsigned depend_abolish : 1; /* Scheduled for depending abolish */ 123 size_t undefined; /* #undefined answers */ 124 125 tbl_component*component; /* component I belong to */ 126 trie *table; /* My answer table */ 127 Definition predicate; /* Predicate we are associated with */ 128 129 buffer delays; /* Delayed answers */ 130 buffer pos_undefined; /* Positive undefined */ 131 } worklist; 132 133 134 /******************************* 135 * DELAY LISTS * 136 *******************************/ 137 138 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 139 A `delay_list` represents a conjunction of conditions. Each condition is 140 either a negative literal <~L> or a positive literal with an answer 141 <L,A>. 142 143 Delay lists are associated with an answer. An answer can have a set of 144 delay lists (`delay_list_set`) and are combined in a `delay_info` struct 145 that provides information about the variant for which this is a 146 condition. 147 148 A `worklist` points at the delay list elements for which it is a 149 condition. After resolving a worklist (answer for positive literals) we 150 should go over the places where its associated variant is used as a 151 condition and 152 153 - Delete the condition from the delay list if the condition is 154 satified. If all conditions are satified propagate using the 155 resolved answer. 156 - Delete the answer from the answer trie and propage that. 157 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ 158 159 typedef struct delay_usage 160 { buffer answers; /* trie_node * to conditional answers */ 161 } delay_usage; 162 163 typedef struct delay 164 { trie *variant; /* Answer trie */ 165 trie_node *answer; /* Answer in there (NULL for negative) */ 166 } delay; 167 168 typedef struct delay_set 169 { unsigned offset; /* offset in delays */ 170 unsigned size; /* size of the conjunction */ 171 unsigned active; /* active members of conjunction */ 172 } delay_set; 173 174 typedef struct delay_info 175 { trie_node *variant; /* Variant trie node */ 176 unsigned has_share_records; /* We have variable sharing records */ 177 buffer delay_sets; /* The disjunctive conditions */ 178 buffer delays; /* Store for the delays */ 179 } delay_info; 180 181 182 /******************************* 183 * IDG * 184 *******************************/ 185 186 typedef struct idg_node 187 { Table affected; /* parent nodes */ 188 Table dependent; /* childs */ 189 trie *atrie; /* answer trie */ 190 size_t answer_count; /* #answers in previous complete state */ 191 unsigned new_answer : 1; /* Update generated a new answer */ 192 unsigned reevaluating : 1; /* currently re-evaluating */ 193 unsigned aborted : 1; /* re-evaluation was aborted */ 194 int falsecount; /* Invalidate count */ 195 #ifdef O_TRIE_STATS 196 struct 197 { uint64_t invalidated; /* # times it was invalidated */ 198 uint64_t reevaluated; /* # times it was re-evaluated */ 199 } stats; 200 #endif 201 } idg_node; 202 203 204 typedef struct trie_array 205 { trie **blocks[MAX_BLOCKS]; 206 trie *preallocated[7]; 207 } trie_array; 208 209 210 /******************************* 211 * PREDICATE PROPERTIES * 212 *******************************/ 213 214 typedef struct table_props 215 { size_t abstract; /* IDG abstraction */ 216 size_t subgoal_abstract; /* Subgoal abstraction */ 217 size_t answer_abstract; /* Answer abstraction */ 218 size_t max_answers; /* Answer count limit */ 219 } table_props; 220 221 222 /******************************* 223 * PROTOTYPES * 224 *******************************/ 225 226 COMMON(void) clearThreadTablingData(PL_local_data_t *ld); 227 COMMON(term_t) init_delay_list(void); 228 COMMON(void) tbl_push_delay(atom_t atrie, Word wrapper, 229 trie_node *answer ARG_LD); 230 COMMON(int) answer_is_conditional(trie_node *answer); 231 COMMON(void) untable_from_clause(Clause cl); 232 COMMON(void) initTabling(void); 233 COMMON(int) idg_add_dyncall(Definition def, trie *ctrie, 234 term_t variant ARG_LD); 235 COMMON(int) tbl_is_predicate_attribute(atom_t key); 236 COMMON(void) tbl_reset_tabling_attributes(Definition def); 237 COMMON(int) tbl_get_predicate_attribute(Definition def, 238 atom_t att, size_t *value); 239 COMMON(int) tbl_set_predicate_attribute(Definition def, 240 atom_t att, size_t value); 241 COMMON(int) tbl_is_restraint_flag(atom_t key); 242 COMMON(int) tbl_get_restraint_flag(term_t t, atom_t key ARG_LD); 243 COMMON(int) tbl_set_restraint_flag(term_t t, atom_t key ARG_LD); 244 #endif /*_PL_TABLING_H*/ 245