8000 complete working example · Z80coder/datalog-cpp@5d805c0 · GitHub
[go: up one dir, main page]
Skip to content

Commit 5d805c0

Browse files
author
wright
committed
complete working example
1 parent 0688960 commit 5d805c0

File tree

2 files changed

+112
-90
lines changed

2 files changed

+112
-90
lines changed

‎src/Datalog.h‎

Lines changed: 70 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,8 @@
1212
#include <cassert>
1313
#include <iostream>
1414

15+
//#define TRACE_ON
16+
1517
namespace datalog
1618
{
1719

@@ -193,7 +195,6 @@ static bool bind(ATOM_TYPE &atom, const GROUND_TYPE &fact, index_sequence<Is...>
193195
template <typename RELATION_TYPE>
194196
static bool bind(typename RELATION_TYPE::Atom &atom, const RELATION_TYPE &fact)
195197
{
196-
//unbind<RELATION_TYPE>(atom);
197198
constexpr size_t tupleSize = tuple_size<typename RELATION_TYPE::TupleType>::value;
198199
return bind<typename RELATION_TYPE::Atom, typename RELATION_TYPE::TupleType>(atom, fact, make_index_sequence<tupleSize>{});
199200
}
@@ -205,9 +206,11 @@ struct Rule
205206
typedef HEAD_RELATION HeadRelationType;
206207
typedef typename HEAD_RELATION::Atom HeadType;
207208
HeadType head;
208-
typedef tuple<BODY_RELATIONs...> BodyRelations;
209209
typedef tuple<typename BODY_RELATIONs::Atom...> BodyType;
210210
BodyType body;
211+
typedef tuple<BODY_RELATIONs...> BodyRelations;
212+
typedef tuple<typename BODY_RELATIONs::Set::const_iterator...> BodyRelationsIteratorType;
213+
typedef tuple<const BODY_RELATIONs *...> SliceType;
211214

212215
// TODO:
213216
// You must sub-class to define rules
@@ -237,8 +240,6 @@ struct State
237240
{
238241
typedef tuple<Set<RELATIONs>...> SetsOfRelationsType;
239242
SetsOfRelationsType relations;
240-
typedef tuple<const RELATIONs *...> SliceType;
241-
typedef tuple<typename RELATIONs::Set::const_iterator...> IteratorsArrayType;
242243

243244
size_t size() const {
244245
size_t totalSize = 0;
@@ -267,29 +268,35 @@ struct State
267268
return out;
268269
}
269270

270-
static ostream &
271-
print(ostream &out, const SliceType &slice)
272-
{
273-
apply([&out](auto &&... args) { ((print(out, args), ...)); }, slice);
274-
return out;
275-
}
276-
271+
template<typename RULE_TYPE>
277272
struct Iterator
278273
{
274+
typedef typename RULE_TYPE::SliceType SliceType;
275+
typedef typename RULE_TYPE::BodyRelationsIteratorType RelationsIteratorType;
276+
279277
Iterator(const SetsOfRelationsType &relations) : relations(relations), iterators(initIterators(relations))
280278
{
281279
}
282280

281+
static ostream &
282+
print(ostream &out, const SliceType &slice)
283+
{
284+
apply([&out](auto &&... args) { ((print(out, args), ...)); }, slice);
285+
return out;
286+
}
287+
283288
private:
284-
template <size_t I, typename RELATION_TYPE>
285-
void pick(const typename RELATION_TYPE::Set &relation,
286-
const RELATION_TYPE *&sliceElement)
289+
template <size_t I>
290+
void pick(const SetsOfRelationsType &relations, SliceType &slice)
287291
{
292+
typedef typename tuple_element<I, typename RULE_TYPE::BodyRelations>::type RelationType;
288293
const auto &it = get<I>(iterators);
289-
if (it != relation.end())
294+
auto& sliceElement = get<I>(slice);
295+
const auto& relation = get<Set<RelationType>>(relations);
296+
if (it != relation.set.end())
290297
{
291298
// TODO: avoid cast if possible
292-
sliceElement = reinterpret_cast<const RELATION_TYPE *>(&*it);
299+
sliceElement = reinterpret_cast<const RelationType *>(&*it);
293300
}
294301
else
295302
{
@@ -301,27 +308,26 @@ struct State
301308
void pick(const SetsOfRelationsType &relations, SliceType &slice,
302309
index_sequence<Is...>)
303310
{
304-
//cout << "[" << endl;
305-
//((pick<Is>(get<Is>(relations), get<Is>(slice))), ...);
306-
((pick<Is>(get<Is>(relations).set, get<Is>(slice))), ...);
307-
//cout << "]" << endl;
311+
((pick<Is>(relations, slice)), ...);
308312
}
309313

310314
template <size_t I>
311-
bool next(const SetsOfRelationsType &relations, IteratorsArrayType &iterators,
315+
bool next(const SetsOfRelationsType &relations, RelationsIteratorType &iterators,
312316
bool &stop)
313317
{
318+
typedef typename tuple_element<I, typename RULE_TYPE::BodyRelations>::type RelationType;
319+
314320
bool iterationFinished = false;
315321
if (not stop)
316322
{
317323
auto &it = get<I>(iterators);
318-
const auto &end = get<I>(relations).set.end();
324+
const auto &end = get<Set<RelationType>>(relations).set.end();
319325
if (it != end)
320326
it++;
321327
if (it == end)
322328
{
323-
it = get<I>(relations).set.begin();
324-
if (I == tuple_size<SetsOfRelationsType>::value - 1)
329+
it = get<Set<RelationType>>(relations).set.begin();
330+
if (I == tuple_size<RelationsIteratorType>::value - 1)
325331
{
326332
iterationFinished = true;
327333
}
@@ -335,7 +341,7 @@ struct State
335341
}
336342

337343
template <size_t... Is>
338-
bool next(const SetsOfRelationsType &relations, IteratorsArrayType &iterators,
344+
bool next(const SetsOfRelationsType &relations, RelationsIteratorType &iterators,
339345
index_sequence<Is...>)
340346
{
341347
bool stop = false;
@@ -351,7 +357,7 @@ struct State
351357
SliceType next()
352358
{
353359
SliceType slice;
354-
auto indexSequence = make_index_sequence<tuple_size<SetsOfRelationsType>::value>{};
360+
auto indexSequence = make_index_sequence<tuple_size<RelationsIteratorType>::value>{};
355361
pick(relations, slice, indexSequence);
356362
iterationFinished = next(relations, iterators, indexSequence);
357363
#if 0
@@ -366,35 +372,38 @@ struct State
366372

367373
private:
368374
const SetsOfRelationsType &relations;
369-
IteratorsArrayType iterators;
375+
RelationsIteratorType iterators;
370376
bool iterationFinished = false;
371377

372-
// RELATION_TYPE is really the set
373-
template <typename RELATION_TYPE, typename ITERATOR_TYPE>
374-
static void initIterator(const RELATION_TYPE &relation, ITERATOR_TYPE &iterator)
378+
template <size_t I>
379+
static void initIterator(const SetsOfRelationsType &relations, RelationsIteratorType &iterators)
375380
{
376-
iterator = relation.begin();
381+
typedef typename tuple_element<I, typename RULE_TYPE::BodyRelations>::type RelationType;
382+
auto& it = get<I>(iterators);
383+
const auto& relation = get<Set<RelationType>>(relations);
384+
it = relation.set.begin();
377385
}
378386

379387
template <size_t... Is>
380388
static void initIterators(const SetsOfRelationsType &relations,
381-
IteratorsArrayType &iterators, index_sequence<Is...>)
389+
RelationsIteratorType &iterators, index_sequence<Is...>)
382390
{
383-
((initIterator(get<Is>(relations).set, get<Is>(iterators))), ...);
391+
((initIterator<Is>(relations, iterators)), ...);
384392
}
385393

386-
static IteratorsArrayType initIterators(const SetsOfRelationsType &relations)
394+
static RelationsIteratorType initIterators(const SetsOfRelationsType &relations)
387395
{
388-
IteratorsArrayType iterators;
396+
RelationsIteratorType iterators;
389397
initIterators(relations, iterators,
390-
make_index_sequence<tuple_size<IteratorsArrayType>::value>{});
398+
make_index_sequence<tuple_size<RelationsIteratorType>::value>{});
391399
return iterators;
392400
}
393401
};
394402

395-
Iterator iterator() const
403+
template <typename RULE_TYPE>
404+
Iterator<RULE_TYPE> it() const
396405
{
397-
Iterator it{relations};
406+
Iterator<RULE_TYPE> it{relations};
398407
return it;
399408
}
400409
};
@@ -413,42 +422,38 @@ static void unbind(const typename RULE_TYPE::BodyType &atoms)
413422
make_index_sequence<tuple_size<typename RULE_TYPE::BodyType>::value>{});
414423
}
415424

416-
template <size_t I, typename RULE_TYPE, typename... RELATIONs>
417-
static bool bind(typename RULE_TYPE::BodyType &atoms, // typedef tuple<typename BODY_RELATIONs::Atom...> BodyType;
418-
const tuple<RELATIONs const *...> &slice)
425+
template <size_t I, typename RULE_TYPE>
426+
static bool bindBodyAtomsToSlice(typename RULE_TYPE::BodyType &atoms,
427+
const typename RULE_TYPE::SliceType &slice)
419428
{
420-
// get the fact in the slice that can potentially bind
421-
typedef typename tuple_element<I, typename RULE_TYPE::BodyRelations>::type BodyRelationI;
422-
auto factPtr = get<BodyRelationI const *>(slice);
429+
auto factPtr = get<I>(slice);
423430
bool success = false;
424431
if (factPtr)
425432
{
426-
const BodyRelationI &fact = *factPtr;
433+
const auto &fact = *factPtr;
427434
// get the atom
428-
typename BodyRelationI::Atom &atom = get<I>(atoms);
435+
auto &atom = get<I>(atoms);
429436
// try to bind the atom with the fact
430437
success = bind(atom, fact);
431438
}
432439
return success;
433440
}
434441

435-
template <typename RULE_TYPE, typename... RELATIONs, size_t... Is>
436-
static bool bind(typename RULE_TYPE::BodyType &atoms,
437-
const tuple<RELATIONs const *...> &slice, index_sequence<Is...>)
442+
template <typename RULE_TYPE, size_t... Is>
443+
static bool bindBodyAtomsToSlice(typename RULE_TYPE::BodyType &atoms,
444+
const typename RULE_TYPE::SliceType &slice, index_sequence<Is...>)
438445
{
439-
return ((bind<Is, RULE_TYPE, RELATIONs...>(atoms, slice)) and ...);
446+
return ((bindBodyAtomsToSlice<Is, RULE_TYPE>(atoms, slice)) and ...);
440447
}
441448

442449
// bind n atoms (of multiple relation types) with 1 slice (of multiple relation types)
443-
template <typename RULE_TYPE, typename... RELATIONs>
444-
static bool bind(typename RULE_TYPE::BodyType &atoms,
445-
const tuple<RELATIONs const *...> &slice)
450+
template <typename RULE_TYPE>
451+
static bool bindBodyAtomsToSlice(typename RULE_TYPE::BodyType &atoms, const typename RULE_TYPE::SliceType &slice)
446452
{
447453
// unbind all the Variables
448454
unbind<RULE_TYPE>(atoms);
449455
// for each atom, bind with corresponding relation type in slice
450-
return bind<RULE_TYPE, RELATIONs...>(atoms, slice,
451-
make_index_sequence<tuple_size<typename RULE_TYPE::BodyType>::value>{});
456+
return bindBodyAtomsToSlice<RULE_TYPE>(atoms, slice, make_index_sequence<tuple_size<typename RULE_TYPE::BodyType>::value>{});
452457
}
453458

454459
template <typename VALUE_TYPE>
@@ -480,24 +485,23 @@ static RELATION_TYPE ground(const typename RELATION_TYPE::Atom &atom)
480485
return groundAtom;
481486
}
482487

483-
484488
template <typename RULE_TYPE, typename STATE_TYPE>
485489
static Set<typename RULE_TYPE::HeadRelationType> applyRule(RULE_TYPE &rule, const STATE_TYPE &state)
486490
{
487491
typedef typename RULE_TYPE::HeadRelationType HeadRelationType;
488492
Set<HeadRelationType> derivedFacts;
489-
auto it = state.iterator();
493+
auto it = state.template it<RULE_TYPE>();
490494
while (it.hasNext())
491495
{
492496
auto slice = it.next();
493-
if (bind<RULE_TYPE>(rule.body, slice))
497+
if (bindBodyAtomsToSlice<RULE_TYPE>(rule.body, slice))
494498
{
495499
// successful bind, therefore add (grounded) head atom to new state
496500
//cout << "successful bind of body" << endl;
497501
auto derivedFact = ground<HeadRelationType>(rule.head);
498-
#if 1
502+
#ifdef TRACE_ON
499503
{
500-
cout << "adding: ";
504+
cout << "adding: " << typeid(HeadRelationType).name() << " ";
501505
datalog::print<typename HeadRelationType::TupleType>(cout, derivedFact); // TODO: avoid need for type
502506
cout << endl;
503507
}
@@ -556,8 +560,14 @@ static State<RELATIONs...> fixPoint(RuleSet<RULE_TYPEs...> &ruleSet, const State
556560
size_t outStateSize = 0;
557561
do {
558562
inStateSize = newState.size();
563+
#ifdef TRACE_ON
564+
cout << "in size = " << inStateSize << endl;
565+
#endif
559566
newState = applyRuleSet(ruleSet, newState);
560567
outStateSize = newState.size();
568+
#ifdef TRACE_ON
569+
cout << "out size = " << outStateSize << endl;
570+
#endif
561571
} while (inStateSize != outStateSize);
562572
return newState;
563573
}

0 commit comments

Comments
 (0)
0