vector/Query.c

   1 #include <stdarg.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <Query.h>
   5 #include <QueryCallbacks.h>
   6
   7 /* ==================== AssignmentQuery ==================== */
   8
   9 /**
  10  * AssignmentQuery represents an assignment of values to names.
  11  * \extends Query
  12  * \related Query
  13  */
  14 typedef struct {
  15     struct QueryCallbacks *def;
  16     int arity;
  17     Tuple *names;
  18     Tuple *values;
  19     Tuple *saved;
  20 } AssignmentQuery;
  21
  22 // Release any memory.
  23 static void AssignmentQuery_reclaim(Query *this) {
  24     AssignmentQuery *q = (AssignmentQuery*) this;
  25     free( q->saved );
  26     free( this );
  27 }
  28
  29 static int AssignmentQuery_check(int arity,Tuple *a,Tuple *b) {
  30     int i;
  31     for ( i = 0; i < arity; i++ ) {
  32         char *value = a->elements[i];
  33         char *current = b->elements[i];
  34         if ( value && current && current != value &&
  35              strcmp( current, value ) != 0 ) {
  36             return 0;
  37         }
  38     }
  39     return 1;
  40 }
  41
  42 static void AssignmentQuery_assign(
  43     BindingTable *bt,int n,Tuple *names,Tuple *values,int all)
  44 {
  45     int i;
  46     for ( i = 0; i < n; i++ ) {
  47         if ( all || values->elements[i] ) {
  48             BindingTable_set( bt, names->elements[i], values->elements[i] );
  49         }
  50     }
  51 }
  52
  53 // Make names have given values and return 1. If any name has a
  54 // different value then return 0. Values are strings.
  55 static int AssignmentQuery_next(
  56     Query *this,BindingTable *bt,enum NextState state) {
  57     AssignmentQuery *q = (AssignmentQuery*) this;
  58     switch ( state ) {
  59     case initial:
  60         if ( q->saved == 0 ) {
  61             q->saved = Tuple_clone( q->arity, q->names );
  62         } else {
  63             memcpy( q->saved, q->names, q->arity * sizeof( void* ) );
  64         }
  65         BindingTable_deref( bt, q->arity, q->saved );
  66         // Check with new values
  67         if ( AssignmentQuery_check( q->arity, q->values, q->saved ) ) {
  68             AssignmentQuery_assign( bt, q->arity, q->names, q->values, 0 );
  69             return 1;
  70         }
  71         // Fall through
  72     case subsequent:
  73     case restore:
  74         if ( q->saved ) {
  75             AssignmentQuery_assign( bt, q->arity, q->names, q->saved, 1 );
  76             free( q->saved );
  77             q->saved = 0;
  78         }
  79         return 0;
  80     }
  81     return 0;
  82 }
  83
  84 static struct QueryCallbacks AssignmentQuery_def = {
  85     .reclaim = AssignmentQuery_reclaim,
  86     .next = AssignmentQuery_next
  87 };
  88
  89 /**
  90  * Return a Query object representing an assignment of one or more
  91  * variables.
  92  */
  93 Query *Query_assign(int arity,Tuple *names,Tuple *values) {
  94     AssignmentQuery *q = (AssignmentQuery*)
  95         malloc( sizeof( AssignmentQuery ) );
  96     (*q) = (AssignmentQuery) {
  97         .def = &AssignmentQuery_def,
  98         .arity = arity,
  99         .names = names,
 100         .values = values,
 101         .saved = 0
 102     };
 103     return (Query*) q;
 104 }
 105
 106 /* ==================== conjunction ==================== */
 107
 108 /**
 109  * ConjunctionQuery represents a conjunction of sub queries.
 110  * \extends Query
 111  * \related Query
 112  */
 113 typedef struct {
 114     struct QueryCallbacks *def;
 115     int active;
 116     int size;
 117     Query **conjuncts;
 118 } ConjunctionQuery;
 119
 120 static void ConjunctionQuery_reclaim(Query *this) {
 121     ConjunctionQuery *q = (ConjunctionQuery*) this;
 122     int i;
 123     for ( i = 0; i < q->size; i++ ) {
 124         q->conjuncts[i]->def->reclaim( q->conjuncts[i] );
 125     }
 126     free( q->conjuncts );
 127     free( this );
 128 }
 129
 130 static int ConjunctionQuery_next(
 131     Query *this,BindingTable *bt,enum NextState state)
 132 {
 133     ConjunctionQuery *q = (ConjunctionQuery*) this;
 134     int i = q->size - 1;
 135     enum NextState s = subsequent;
 136     switch ( state ) {
 137     case initial:
 138         q->active = 1;
 139         i = 0;
 140         s = initial;
 141         // Fall through?
 142     case subsequent:
 143         while ( i < q->size ) {
 144             if ( q->conjuncts[i]->def->next( q->conjuncts[i], bt, s ) ) {
 145                 continue;
 146             }
 147             q->conjuncts[i]->def->next( q->conjuncts[i], bt, restore );
 148             if ( i-- == 0 ) {
 149                 // The first conjunct now exhausted
 150                 q->active = 0;
 151                 return 0;
 152             }
 153             s = subsequent;
 154         }
 155         return 1;
 156     case restore:
 157         if ( q->active ) {
 158             for ( ; i >= 0; i-- ) {
 159                 q->conjuncts[i]->def->next( q->conjuncts[i], bt, restore );
 160             }
 161         }
 162         q->active = 0;
 163         return 0;
 164     }
 165     return 0;
 166 }
 167
 168 static struct QueryCallbacks ConjunctionQuery_def = {
 169     .reclaim = ConjunctionQuery_reclaim,
 170     .next = ConjunctionQuery_next
 171 };
 172
 173 Query *Query_and(int n,...) {
 174     va_list args;
 175     ConjunctionQuery *q = (ConjunctionQuery *)
 176         malloc( sizeof( ConjunctionQuery ) );
 177     (*q) = (ConjunctionQuery) {
 178         .def = &ConjunctionQuery_def,
 179         .active = 0,
 180         .size = n,
 181         .conjuncts = (Query**) malloc( n * sizeof( Query* ) )
 182     };
 183     int i;
 184     va_start( args, n );
 185     for ( i = 0; i < n; i++ ) {
 186         q->conjuncts[i] = va_arg( args, Query* );
 187     }
 188     va_end( args );
 189     return (Query*) q;
 190 }
 191
 192 /* ==================== disjunction ==================== */
 193
 194 /**
 195  * DisjunctionQuery represents a disjunction of sub queries.
 196  * \extends Query
 197  * \related Query
 198  */
 199 typedef struct {
 200     struct QueryCallbacks *def;
 201     int index;
 202     int size;
 203     Query **disjuncts;
 204 } DisjunctionQuery;
 205
 206 static void DisjunctionQuery_reclaim(Query *this) {
 207     DisjunctionQuery *q = (DisjunctionQuery*) this;
 208     int i;
 209     for ( i = 0; i < q->size; i++ ) {
 210         q->disjuncts[i]->def->reclaim( q->disjuncts[i] );
 211     }
 212     free( q->disjuncts );
 213     free( this );
 214 }
 215
 216 static int DisjunctionQuery_next(
 217     Query *this,BindingTable *bt,enum NextState state) {
 218     DisjunctionQuery *q = (DisjunctionQuery*) this;
 219     int i = q->index;
 220     enum NextState s = subsequent;
 221     switch ( state ) {
 222     case initial:
 223         i = 0;
 224         s = initial;
 225     case subsequent:
 226         for ( ; i < q->size; i++ ) {
 227             if ( q->disjuncts[i]->def->next( q->disjuncts[i], bt, s ) ) {
 228                 q->index = i;
 229                 return 1;
 230             }
 231             q->disjuncts[i]->def->next( q->disjuncts[i], bt, restore );
 232             s = initial;
 233         }
 234         q->index = -1;
 235         return 0;
 236     case restore:
 237         if ( i >= 0 ) {
 238             q->disjuncts[i]->def->next( q->disjuncts[i], bt, restore );
 239             q->index = -1;
 240         }
 241         return 0;
 242     }
 243     return 0;
 244 }
 245
 246 static struct QueryCallbacks DisjunctionQuery_def = {
 247     .reclaim = DisjunctionQuery_reclaim,
 248     .next = DisjunctionQuery_next,
 249 };
 250
 251 Query *Query_or(int n,...) {
 252     va_list args;
 253     DisjunctionQuery *q = (DisjunctionQuery *)
 254         malloc( sizeof( DisjunctionQuery ) );
 255     (*q) = (DisjunctionQuery) {
 256         .def = &DisjunctionQuery_def,
 257         .index = -1,
 258         .size = n,
 259         .disjuncts = (Query**) malloc( n * sizeof( Query* ) ),
 260     };
 261     int i;
 262     va_start( args, n );
 263     for ( i = 0; i < n; i++ ) {
 264         q->disjuncts[i] = va_arg( args, Query* );
 265     }
 266     va_end( args );
 267     return (Query*) q;
 268 }
 269
 270 /* ==================== Relation access ==================== */
 271
 272 /**
 273  * RelationQuery represents a ground query on a relation.
 274  * \extends Query
 275  * \related Query
 276  */
 277 typedef struct {
 278     struct QueryCallbacks *def;
 279     Relation *rel;
 280     VectorIndex index;
 281     Tuple *names;
 282     Tuple *values;
 283     Tuple *saved;
 284 } RelationQuery;
 285
 286 // Release any memory.
 287 static void RelationQuery_reclaim(Query *this) {
 288     RelationQuery *q = (RelationQuery*) this;
 289     free( q->saved );
 290     free( this );
 291 }
 292
 293 // Make names have given values and return 1. If any name has a
 294 // different value then return 0. Values are strings.
 295 static int RelationQuery_next(
 296     Query *this,BindingTable *bt,enum NextState state) {
 297     RelationQuery *q = (RelationQuery*) this;
 298     int arity = ((TupleSchema*) q->rel->content.type)->arity;
 299     VectorIndex index = q->index + 1;
 300     switch ( state ) {
 301     case initial:
 302         if ( q->saved == 0 ) {
 303             q->saved = Tuple_clone( arity, q->names );
 304         } else {
 305             memcpy( q->saved, q->names, arity * sizeof( void* ) );
 306         }
 307         BindingTable_deref( bt, arity, q->saved );
 308         index = 0;
 309         // Fall through
 310     case subsequent:
 311         for ( ; index < q->rel->content.table.size; index++ ) {
 312             Tuple *values = Relation_next( q->rel, &index, q->values );
 313             if ( values ) {
 314                 q->index = index;
 315                 AssignmentQuery_assign( bt, arity, q->names, values, 1 );
 316                 return 1;
 317             }
 318         }
 319     case restore:
 320         if ( q->saved ) {
 321             AssignmentQuery_assign( bt, arity, q->names, q->saved, 1 );
 322             free( q->saved );
 323             q->saved = 0;
 324         }
 325         return 0;
 326     }
 327     return 0;
 328 }
 329
 330 static struct QueryCallbacks RelationQuery_def = {
 331     .reclaim = RelationQuery_reclaim,
 332     .next = RelationQuery_next
 333 };
 334
 335 /**
 336  * Return a Query object representing an Relation of one or more
 337  * variables.
 338  */
 339 Query *Query_Relation(Relation *r,Tuple *names,Tuple *values) {
 340     RelationQuery *q = (RelationQuery*) malloc( sizeof( RelationQuery ) );
 341     (*q) = (RelationQuery) {
 342         .def = &RelationQuery_def,
 343         .rel = r,
 344         .names = names,
 345         .values = values,
 346         .saved = 0
 347     };
 348     return (Query*) q;
 349 }
 350
 351 void Query_rule(
 352     Query *q,BindingTable *bt,
 353     int (*consequent)(BindingTable *bt,void *data),
 354     void *data )
 355 {
 356     if ( q->def->next( q, bt, initial ) && consequent( bt, data ) ) {
 357         while ( q->def->next( q, bt, subsequent ) && consequent( bt, data ) );
 358     }
 359     (void) q->def->next( q, bt, restore );
 360 }