Debian Codegraph @

Source/Reasoner/Kernel/Algorithm/CSatisfiableExpanderCacheHandler.cpp

raw
1 /*
2 * Copyright (C) 2013-2015, 2019 by the Konclude Developer Team.
3 *
4 * This file is part of the reasoning system Konclude.
5 * For details and support, see <http://konclude.com/>.
6 *
7 * Konclude is free software: you can redistribute it and/or modify
8 * it under the terms of version 3 of the GNU Lesser General Public
9 * License (LGPLv3) as published by the Free Software Foundation.
10 *
11 * Konclude is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU (Lesser) General Public License for more details.
15 *
16 * You should have received a copy of the GNU (Lesser) General Public
17 * License along with Konclude. If not, see <http://www.gnu.org/licenses/>.
18 *
19 */
20
21 #include "CSatisfiableExpanderCacheHandler.h"
22
23
24 namespace Konclude {
25
26 namespace Reasoner {
27
28 namespace Kernel {
29
30 namespace Algorithm {
31
32 CSatisfiableExpanderCacheHandler::CSatisfiableExpanderCacheHandler(CSignatureSatisfiableExpanderCacheReader* satCacheReader, CSignatureSatisfiableExpanderCacheWriter* satCacheWriter) {
33 mSatCacheReader = satCacheReader;
34 mSatCacheWriter = satCacheWriter;
35
36 mTmpContext = nullptr;
37 mMemAllocMan = nullptr;
38 mWriteData = nullptr;
39 }
40
41
42 CSatisfiableExpanderCacheHandler::~CSatisfiableExpanderCacheHandler() {
43 }
44
45
46
47
48 bool CSatisfiableExpanderCacheHandler::isIndividualNodeExpandCached(CIndividualProcessNode* individualNode, bool* satisfiable, CSignatureSatisfiableExpanderCacheEntry** entry, CCalculationAlgorithmContext* calcAlgContext) {
49 CReapplyConceptLabelSet* conSet = individualNode->getReapplyConceptLabelSet(false);
50 if (conSet && !conSet->getConceptStructure()->hasBindingPropagationConcepts() && !conSet->getConceptStructure()->hasDynamicCreatedConcepts()) {
51 cint64 conSig = conSet->getConceptSignatureValue();
52 CSignatureSatisfiableExpanderCacheEntry* cachedEntry = mSatCacheReader->getCacheEntry(conSig);
53 if (cachedEntry) {
54
55 cint64 conSetCount = conSet->getConceptCount();
56 cint64 expCount = cachedEntry->getExpanderCacheValueCount();
57 if (expCount < conSetCount) {
58 return false;
59 }
60
61 if (!compareIndividualNodeCompatibility(individualNode,cachedEntry,calcAlgContext)) {
62 return false;
63 }
64
65 if (entry) {
66 *entry = cachedEntry;
67 }
68 if (satisfiable) {
69 *satisfiable = cachedEntry->isSatisfiable();
70 }
71 return true;
72 }
73 }
74 return false;
75 }
76
77
78
79 bool CSatisfiableExpanderCacheHandler::compareIndividualNodeCompatibility(CIndividualProcessNode* individualNode, CSignatureSatisfiableExpanderCacheEntry* cachedEntry, CCalculationAlgorithmContext* calcAlgContext) {
80 CReapplyConceptLabelSet* conSet = individualNode->getReapplyConceptLabelSet(false);
81 cint64 conSetCount = conSet->getConceptCount();
82 CExpanderCacheValueLinker* expCacheValueLinker = cachedEntry->getExpanderCacheValueLinker();
83 cint64 conNr = 0;
84 while (expCacheValueLinker && conNr++ < conSetCount) {
85
86 CCacheValue* cacheValue = expCacheValueLinker->getCacheValue();
87 CConcept* concept = (CConcept*)cacheValue->getIdentification();
88
89 CConceptDescriptor* conDes = nullptr;
90 CDependencyTrackPoint* depTrackPoint = nullptr;
91
92 if (conSet->getConceptDescriptor(concept,conDes,depTrackPoint)) {
93 bool conNegated = conDes->isNegated();
94 bool cacheNegated = cacheValue->getCacheValueIdentifier() == CCacheValue::CACHEVALTAGANDNEGATEDCONCEPT;
95 if (conNegated != cacheNegated || conDes->getConcept() != concept) {
96 return false;
97 }
98 } else {
99 return false;
100 }
101
102 expCacheValueLinker = expCacheValueLinker->getNext();
103 }
104 return true;
105
106 }
107
108
109
110
111
112
113
114
115
116
117
118
119 bool CSatisfiableExpanderCacheHandler::cacheIndividualNodeSatisfiable(CIndividualProcessNode* individualNode, CCalculationAlgorithmContext* calcAlgContext) {
120 STATINC(SATEXPCACHEWRITINGREQUESTCOUNT,calcAlgContext);
121 STATINC(SATEXPCACHESATISFIABLEWRITINGREQUESTCOUNT,calcAlgContext);
122
123
124 CReapplyConceptLabelSet* conSet = individualNode->getReapplyConceptLabelSet(false);
125 if (conSet) {
126 if (conSet->getConceptStructure()->hasBindingPropagationConcepts() || conSet->getConceptStructure()->hasDynamicCreatedConcepts()) {
127 return false;
128 }
129 mTestConSet = conSet;
130 cint64 conSetSignature = conSet->getConceptSignatureValue();
131 CIndividualNodeSatisfiableExpandingCacheStoringData* satStorData = (CIndividualNodeSatisfiableExpandingCacheStoringData*)individualNode->getIndividualSatisfiableCacheStoringData(false);
132 if (satStorData) {
133 if (satStorData->hasCachingError()) {
134 return false;
135 }
136 if (satStorData->hasPreviousSatisfiableCached()) {
137 if (satStorData->getLastCachedSignature() == conSetSignature) {
138 return false;
139 }
140 }
141 }
142
143 bool localizedSatStorData = false;
144
145 CMemoryAllocationManager* memMan = calcAlgContext->getUsedTemporaryMemoryAllocationManager();
146 CMemoryAllocationManager* taskMemMan = calcAlgContext->getUsedProcessTaskMemoryAllocationManager();
147 CIndividualNodeSatisfiableExpandingCacheStoringData* locSatStorData = (CIndividualNodeSatisfiableExpandingCacheStoringData*)individualNode->getIndividualSatisfiableCacheStoringData(true);
148 if (locSatStorData && !satStorData) {
149 // is probably caching by another thread
150 return false;
151 }
152 if (!locSatStorData) {
153 locSatStorData = CObjectAllocator<CIndividualNodeSatisfiableExpandingCacheStoringData>::allocateAndConstruct(taskMemMan);
154 locSatStorData->initSatisfiableExpandingCacheRetrievalData(satStorData);
155 satStorData = locSatStorData;
156 individualNode->setIndividualSatisfiableCacheStoringData(locSatStorData);
157 localizedSatStorData = true;
158 }
159
160 CConceptDescriptor* lastAddedConDes = conSet->getAddingSortedConceptDescriptionLinker();
161
162 CSignatureSatisfiableExpanderCacheEntry* cachedEntry = mSatCacheReader->getCacheEntry(conSetSignature);
163 if (cachedEntry) {
164 STATINC(SATEXPCACHEWRITINGSIGNATUREALREADYCACHEDCOUNT,calcAlgContext);
165
166 if (!compareIndividualNodeCompatibility(individualNode,cachedEntry,calcAlgContext)) {
167 STATINC(SATEXPCACHEWRITINGSIGNATUREALREADYCACHEDINCOMPATIBLECOUNT,calcAlgContext);
168 STATINC(SATEXPCACHEWRITINGERRORCOUNT,calcAlgContext);
169 satStorData->setCachingError(true);
170 return false;
171 } else {
172
173 if (!cachedEntry->isSatisfiable()) {
174 // write only satisfiability
175 STATINC(SATEXPCACHEWRITINGSIGNATUREALREADYCACHEDSATADDEDCOUNT,calcAlgContext);
176
177 prepareCacheMessages(calcAlgContext);
178
179 CTaskMemoryPoolAllocationManager* satCacheMemMan = mMemAllocMan;
180 CContextBase* tmpContext = mTmpContext;
181 CCACHINGLIST<CCacheValue>* cacheValueList = CObjectParameterizingAllocator< CCACHINGLIST<CCacheValue>,CContext* >::allocateAndConstructAndParameterize(satCacheMemMan,tmpContext);
182 CCACHINGLIST<CCacheValue>* branchedList = CObjectParameterizingAllocator< CCACHINGLIST<CCacheValue>,CContext* >::allocateAndConstructAndParameterize(satCacheMemMan,tmpContext);
183
184 CConceptDescriptor* conDesIt = lastAddedConDes;
185 while (conDesIt) {
186 CConceptDescriptor* conDes = conDesIt;
187 cint64 conTag = conDes->getConceptTag();
188
189 CCacheValue::CACHEVALUEIDENTIFIER cacheValueIdentifier = CCacheValue::CACHEVALTAGANDCONCEPT;
190 if (conDes->getNegation()) {
191 cacheValueIdentifier = CCacheValue::CACHEVALTAGANDNEGATEDCONCEPT;
192 }
193 CCacheValue cacheValue;
194 cacheValue.initCacheValue(conTag,(cint64)conDes->getConcept(),cacheValueIdentifier);
195 cacheValueList->prepend(cacheValue);
196
197 if (isCardinalityRestrictionCriticalForSatisfiable(individualNode,conDes,calcAlgContext)) {
198 branchedList->append(cacheValue);
199 }
200
201
202 conDesIt = conDesIt->getNextConceptDesciptor();
203 }
204
205 CSignatureSatisfiableExpanderCacheEntrySatisfiableBranchWriteData* satBranchWriteData = CObjectAllocator< CSignatureSatisfiableExpanderCacheEntrySatisfiableBranchWriteData >::allocateAndConstruct(satCacheMemMan);
206 satBranchWriteData->initSatisfiableBranchWriteData(conSetSignature,cacheValueList,branchedList);
207 addCacheMessages(satBranchWriteData,calcAlgContext);
208
209 }
210
211 satStorData->setLastCachedConceptDescriptor(lastAddedConDes);
212 satStorData->setPreviousCached(true);
213 satStorData->setPreviousSatisfiableCached(true);
214 satStorData->setLastCachedSignature(conSetSignature);
215 return true;
216 }
217 }
218
219
220 CConceptDescriptor* lastCachedConceptDes = satStorData->getLastCachedConceptDescriptor();
221
222 CPROCESSINGLIST<CConceptDescriptor*> reverseConDesList(calcAlgContext->getUsedTaskProcessorContext());
223
224 // check whether to restart caching
225 bool directBranched = false;
226 bool dependencyToAncestor = false;
227 cint64 lastBranchingTag = -1;
228 CConceptDescriptor* conDesIt = lastAddedConDes;
229 while (conDesIt != lastCachedConceptDes) {
230 CConceptDescriptor* conDes = conDesIt;
231 CDependencyTrackPoint* depTrackPoint = conDesIt->getDependencyTrackPoint();
232 if (hasDependencyToAncestor(individualNode,depTrackPoint,&directBranched,calcAlgContext)) {
233 dependencyToAncestor = true;
234 }
235 reverseConDesList.prepend(conDes);
236 conDesIt = conDesIt->getNextConceptDesciptor();
237 }
238 if (dependencyToAncestor) {
239 satStorData->setPreviousCached(false);
240 satStorData->setPreviousSatisfiableCached(false);
241 satStorData->setLastCachedSignature(0);
242 satStorData->setLastCachedConceptDescriptor(nullptr);
243 lastCachedConceptDes = nullptr;
244 }
245 if (directBranched) {
246 satStorData->setIndividualNodeOrSuccessorBranchedConcept(true);
247 }
248
249 while (conDesIt) {
250 CConceptDescriptor* conDes = conDesIt;
251 reverseConDesList.prepend(conDes);
252 conDesIt = conDesIt->getNextConceptDesciptor();
253 }
254
255
256 cint64 lastConSetSignature = satStorData->getLastCachedSignature();
257 if (!satStorData->hasPreviousCached() && lastCachedConceptDes && lastConSetSignature != 0 && lastConSetSignature != conSetSignature) {
258 cacheIndividualNodeExpansion(individualNode,satStorData,lastCachedConceptDes,nullptr,lastConSetSignature,0,calcAlgContext);
259 }
260
261
262
263 // try satisfiable caching
264
265 prepareCacheMessages(calcAlgContext);
266 CTaskMemoryPoolAllocationManager* satCacheMemMan = mMemAllocMan;
267 CTaskMemoryPoolAllocationManager* expCacheMemMan = mMemAllocMan;
268 CContextBase* tmpSatBranchContext = mTmpContext;
269 CContextBase* tmpExpContext = mTmpContext;
270
271 CCACHINGHASH<cint64,cint64>* depHash = CObjectParameterizingAllocator< CCACHINGHASH<cint64,cint64>,CContext* >::allocateAndConstructAndParameterize(expCacheMemMan,tmpExpContext);
272 CCACHINGLIST<CCacheValue>* expValueList = CObjectParameterizingAllocator< CCACHINGLIST<CCacheValue>,CContext* >::allocateAndConstructAndParameterize(expCacheMemMan,tmpExpContext);
273
274 CCACHINGLIST<CCacheValue>* satValueList = CObjectParameterizingAllocator< CCACHINGLIST<CCacheValue>,CContext* >::allocateAndConstructAndParameterize(satCacheMemMan,tmpSatBranchContext);
275 CCACHINGLIST<CCacheValue>* branchedList = CObjectParameterizingAllocator< CCACHINGLIST<CCacheValue>,CContext* >::allocateAndConstructAndParameterize(satCacheMemMan,tmpSatBranchContext);
276
277 if (!satStorData->hasPreviousCached()) {
278 lastCachedConceptDes = nullptr;
279 lastConSetSignature = 0;
280 }
281
282 bool lastCachedConDesReached = false;
283 bool cachingError = false;
284 CPROCESSINGSET<cint64> notBranchConceptsSet(calcAlgContext->getUsedTaskProcessorContext());
285
286 for (CPROCESSINGLIST<CConceptDescriptor*>::const_iterator it = reverseConDesList.constBegin(), itEnd = reverseConDesList.constEnd(); it != itEnd; ++it) {
287 CConceptDescriptor* conDesIt = *it;
288
289 CConceptDescriptor* conDes = conDesIt;
290 CDependencyTrackPoint* depTrackPoint = nullptr;
291 bool conceptDepInNodeOrSuccesssorBranched = false;
292 cint64 conTag = conDes->getConceptTag();
293
294
295 if (lastCachedConDesReached) {
296 CConceptDescriptor* conDes = conDesIt;
297 CDependencyTrackPoint* depTrackPoint = conDes->getDependencyTrackPoint();
298
299 if (!simpleDependencyTracking(individualNode,conTag,depTrackPoint,depHash,&notBranchConceptsSet,&conceptDepInNodeOrSuccesssorBranched,calcAlgContext)) {
300 CPROCESSINGSET<CDepthDependencyPair> depSet(calcAlgContext->getTaskProcessorContext());
301 CPROCESSINGLIST<CDepthDependencyPair> depList(calcAlgContext->getTaskProcessorContext());
302
303 cint64 baseAncDepth = individualNode->getIndividualAncestorDepth();
304
305 depSet.insert(CDepthDependencyPair(baseAncDepth,depTrackPoint));
306 depList.append(CDepthDependencyPair(baseAncDepth,depTrackPoint));
307
308 if (!complexDependencyTracking(individualNode,conTag,&depSet,&depList,depHash,&notBranchConceptsSet,&conceptDepInNodeOrSuccesssorBranched,calcAlgContext)) {
309 // error
310 cachingError = true;
311 }
312 }
313 }
314
315 bool addConceptToSatBranchedList = false;
316 if (conceptDepInNodeOrSuccesssorBranched) {
317 if (isConceptRelevantForSatisfiableBranch(individualNode,conDes,calcAlgContext)) {
318 addConceptToSatBranchedList = true;
319 }
320 } else {
321 notBranchConceptsSet.insert(conDes->getConceptTag());
322 if (isCardinalityRestrictionCriticalForSatisfiable(individualNode,conDes,calcAlgContext)) {
323 addConceptToSatBranchedList = true;
324 }
325
326 CCacheValue::CACHEVALUEIDENTIFIER cacheValueIdentifier = CCacheValue::CACHEVALTAGANDCONCEPT;
327 if (conDes->getNegation()) {
328 cacheValueIdentifier = CCacheValue::CACHEVALTAGANDNEGATEDCONCEPT;
329 }
330 expValueList->append(CCacheValue(conTag,(cint64)conDes->getConcept(),cacheValueIdentifier));
331 satValueList->append(CCacheValue(conTag,(cint64)conDes->getConcept(),cacheValueIdentifier));
332 }
333
334
335 if (addConceptToSatBranchedList) {
336 STATINC(SATEXPCACHEWRITINGSIGSATCRITICALBRANCHCONCEPTADDEDCOUNT,calcAlgContext);
337 CCacheValue::CACHEVALUEIDENTIFIER cacheValueIdentifier = CCacheValue::CACHEVALTAGANDCONCEPT;
338 if (conDes->getNegation()) {
339 cacheValueIdentifier = CCacheValue::CACHEVALTAGANDNEGATEDCONCEPT;
340 }
341 branchedList->append(CCacheValue(conTag,(cint64)conDes->getConcept(),cacheValueIdentifier));
342 }
343
344 directBranched |= conceptDepInNodeOrSuccesssorBranched;
345
346
347
348 if (!lastCachedConDesReached) {
349 if (conDesIt == lastCachedConceptDes) {
350 lastCachedConDesReached = true;
351 }
352 }
353 }
354
355
356
357 if (cachingError) {
358 STATINC(SATEXPCACHEWRITINGERRORCOUNT,calcAlgContext);
359 satStorData->setCachingError(true);
360 } else {
361
362 cint64 lastSig = lastConSetSignature;
363 if (!satStorData->hasPreviousSatisfiableCached() && lastConSetSignature == conSetSignature) {
364 lastSig = 0;
365 }
366 cint64 newSig = conSetSignature;
367
368 STATINC(SATEXPCACHEWRITINGSIGNATUREEXPANSIONCOUNT,calcAlgContext);
369 CSignatureSatisfiableExpanderCacheEntryExpandWriteData* expandWriteData = CObjectAllocator< CSignatureSatisfiableExpanderCacheEntryExpandWriteData >::allocateAndConstruct(expCacheMemMan);
370 expandWriteData->initExpandWriteData(lastSig,newSig,expValueList,depHash);
371
372
373 STATINC(SATEXPCACHEWRITINGSIGNATURESATISFIABLECOUNT,calcAlgContext);
374 CSignatureSatisfiableExpanderCacheEntrySatisfiableBranchWriteData* satBranchWriteData = CObjectAllocator< CSignatureSatisfiableExpanderCacheEntrySatisfiableBranchWriteData >::allocateAndConstruct(satCacheMemMan);
375 satBranchWriteData->initSatisfiableBranchWriteData(newSig,satValueList,branchedList);
376 satBranchWriteData->setNext(expandWriteData);
377 addCacheMessages(satBranchWriteData,calcAlgContext);
378
379
380 satStorData->setPreviousCached(true);
381 satStorData->setPreviousSatisfiableCached(true);
382 satStorData->setLastCachedSignature(newSig);
383 satStorData->setLastCachedConceptDescriptor(lastAddedConDes);
384 satStorData->setIndividualNodeOrSuccessorBranchedConcept(directBranched);
385 return true;
386 }
387 }
388 return false;
389 }
390
391
392
393
394
395
396
397
398
399 bool CSatisfiableExpanderCacheHandler::cacheIndividualNodeExpansion(CIndividualProcessNode* individualNode, CCalculationAlgorithmContext* calcAlgContext) {
400 STATINC(SATEXPCACHEWRITINGREQUESTCOUNT,calcAlgContext);
401 STATINC(SATEXPCACHESATISFIABLEWRITINGREQUESTCOUNT,calcAlgContext);
402 CReapplyConceptLabelSet* conSet = individualNode->getReapplyConceptLabelSet(false);
403 mTestConSet = conSet;
404 cint64 conSetSignature = conSet->getConceptSignatureValue();
405 CIndividualNodeSatisfiableExpandingCacheStoringData* satStorData = (CIndividualNodeSatisfiableExpandingCacheStoringData*)individualNode->getIndividualSatisfiableCacheStoringData(false);
406 if (satStorData) {
407 if (satStorData->hasCachingError()) {
408 return false;
409 }
410 if (satStorData->hasIndividualNodeOrSuccessorBranchedConcept()) {
411 return false;
412 }
413 if (satStorData->getLastCachedSignature() == conSetSignature) {
414 return false;
415 }
416 }
417
418 CMemoryAllocationManager* memMan = calcAlgContext->getUsedTemporaryMemoryAllocationManager();
419 CMemoryAllocationManager* taskMemMan = calcAlgContext->getUsedProcessTaskMemoryAllocationManager();
420 CIndividualNodeSatisfiableExpandingCacheStoringData* locSatStorData = (CIndividualNodeSatisfiableExpandingCacheStoringData*)individualNode->getIndividualSatisfiableCacheStoringData(true);
421 if (locSatStorData && !satStorData) {
422 // is probably caching by another thread
423 return false;
424 }
425 if (!locSatStorData) {
426 locSatStorData = CObjectAllocator<CIndividualNodeSatisfiableExpandingCacheStoringData>::allocateAndConstruct(taskMemMan);
427 locSatStorData->initSatisfiableExpandingCacheRetrievalData(satStorData);
428 satStorData = locSatStorData;
429 individualNode->setIndividualSatisfiableCacheStoringData(locSatStorData);
430 }
431
432
433 CConceptDescriptor* lastAddedConDes = conSet->getAddingSortedConceptDescriptionLinker();
434 CConceptDescriptor* lastCachedConceptDes = satStorData->getLastCachedConceptDescriptor();
435 if (!satStorData->hasPreviousCached() && !lastCachedConceptDes) {
436 satStorData->setLastCachedConceptDescriptor(lastAddedConDes);
437 satStorData->setLastCachedSignature(conSetSignature);
438 STATINC(SATEXPCACHEWRITINGEXPANSIONDELAYEDCOUNT,calcAlgContext);
439 return true;
440 }
441
442
443
444 CSignatureSatisfiableExpanderCacheEntry* cachedEntry = mSatCacheReader->getCacheEntry(conSetSignature);
445 if (cachedEntry) {
446 STATINC(SATEXPCACHEWRITINGSIGNATUREALREADYCACHEDCOUNT,calcAlgContext);
447
448 cint64 conSetCount = conSet->getConceptCount();
449 cint64 expCount = cachedEntry->getExpanderCacheValueCount();
450 if (expCount < conSetCount) {
451 return false;
452 }
453
454 if (!compareIndividualNodeCompatibility(individualNode,cachedEntry,calcAlgContext)) {
455 STATINC(SATEXPCACHEWRITINGSIGNATUREALREADYCACHEDINCOMPATIBLECOUNT,calcAlgContext);
456 STATINC(SATEXPCACHEWRITINGERRORCOUNT,calcAlgContext);
457 satStorData->setCachingError(true);
458 return false;
459 } else {
460 satStorData->setLastCachedConceptDescriptor(lastAddedConDes);
461 satStorData->setPreviousCached(true);
462 satStorData->setLastCachedSignature(conSetSignature);
463 return true;
464 }
465 }
466
467
468
469 //CConceptDescriptor* testConDesIt = lastAddedConDes;
470 //while (testConDesIt && testConDesIt->hasNext() && testConDesIt->getNextConceptDesciptor()->hasNext()) {
471 // testConDesIt = testConDesIt->getNextConceptDesciptor();
472 //}
473 //QString conString;
474 //if (testConDesIt) {
475 // conString = CIRIName::getRecentIRIName(testConDesIt->getConcept()->getClassNameLinker());
476 // if (conString == "http://www.owllink.org/testsuite/galen#Diabetes" || conString == "http://www.owllink.org/testsuite/galen#ProperHepaticArtery") {
477 // bool bug = true;
478 // }
479 //}
480
481
482 // check whether to restart caching
483 bool directBranched = false;
484 bool dependencyToAncestor = false;
485 CConceptDescriptor* conDesIt = lastAddedConDes;
486 while (conDesIt != lastCachedConceptDes) {
487 CConceptDescriptor* conDes = conDesIt;
488 CDependencyTrackPoint* depTrackPoint = conDes->getDependencyTrackPoint();
489 if (hasDependencyToAncestor(individualNode,depTrackPoint,&directBranched,calcAlgContext)) {
490 dependencyToAncestor = true;
491 }
492 conDesIt = conDesIt->getNextConceptDesciptor();
493 }
494
495 if (dependencyToAncestor) {
496 satStorData->setPreviousCached(false);
497 satStorData->setPreviousSatisfiableCached(false);
498 satStorData->setLastCachedSignature(conSetSignature);
499 satStorData->setLastCachedConceptDescriptor(lastAddedConDes);
500 return true;
501 }
502 if (directBranched) {
503 satStorData->setIndividualNodeOrSuccessorBranchedConcept(true);
504 return false;
505 }
506
507 cint64 lastConSetSignature = satStorData->getLastCachedSignature();
508 if (!satStorData->hasPreviousCached() && lastCachedConceptDes && lastConSetSignature != 0) {
509 cacheIndividualNodeExpansion(individualNode,satStorData,lastCachedConceptDes,nullptr,lastConSetSignature,0,calcAlgContext);
510 }
511 if (!satStorData->hasCachingError() && !satStorData->hasIndividualNodeOrSuccessorBranchedConcept()) {
512 cacheIndividualNodeExpansion(individualNode,satStorData,lastAddedConDes,lastCachedConceptDes,conSetSignature,lastConSetSignature,calcAlgContext);
513 }
514
515 //commitCacheMessages(calcAlgContext);
516
517 return false;
518 }
519
520
521
522
523
524
525
526 bool CSatisfiableExpanderCacheHandler::cacheIndividualNodeExpansion(CIndividualProcessNode* individualNode, CIndividualNodeSatisfiableExpandingCacheStoringData* satStorData, CConceptDescriptor* lastAddedConDes, CConceptDescriptor* lastCachedConceptDes, cint64 lastSignature, cint64 lastCachedSignature, CCalculationAlgorithmContext* calcAlgContext) {
527 CReapplyConceptLabelSet* conSet = individualNode->getReapplyConceptLabelSet(false);
528
529
530 // try caching
531 prepareCacheMessages(calcAlgContext);
532 CTaskMemoryPoolAllocationManager* satCacheMemMan = mMemAllocMan;
533 CContextBase* tmpContext = mTmpContext;
534 CCACHINGHASH<cint64,cint64>* depHash = CObjectParameterizingAllocator< CCACHINGHASH<cint64,cint64>,CContext* >::allocateAndConstructAndParameterize(satCacheMemMan,tmpContext);
535 CCACHINGLIST<CCacheValue>* cacheValueList = CObjectParameterizingAllocator< CCACHINGLIST<CCacheValue>,CContext* >::allocateAndConstructAndParameterize(satCacheMemMan,tmpContext);
536
537 CConceptDescriptor* conDesIt = lastAddedConDes;
538 bool directBranched = false;
539 bool cachingError = false;
540 if (lastCachedConceptDes) {
541 while (conDesIt != lastCachedConceptDes && !directBranched && !cachingError) {
542 CConceptDescriptor* conDes = conDesIt;
543 CDependencyTrackPoint* depTrackPoint = conDes->getDependencyTrackPoint();
544
545 cint64 conTag = conDes->getConceptTag();
546
547 if (!simpleDependencyTracking(individualNode,conTag,depTrackPoint,depHash,nullptr,&directBranched,calcAlgContext)) {
548 CPROCESSINGSET<CDepthDependencyPair> depSet(calcAlgContext->getTaskProcessorContext());
549 CPROCESSINGLIST<CDepthDependencyPair> depList(calcAlgContext->getTaskProcessorContext());
550
551 cint64 baseAncDepth = individualNode->getIndividualAncestorDepth();
552
553 depSet.insert(CDepthDependencyPair(baseAncDepth,depTrackPoint));
554 depList.append(CDepthDependencyPair(baseAncDepth,depTrackPoint));
555
556 if (!complexDependencyTracking(individualNode,conTag,&depSet,&depList,depHash,nullptr,&directBranched,calcAlgContext)) {
557 // error
558 cachingError = true;
559 }
560 }
561
562 CCacheValue::CACHEVALUEIDENTIFIER cacheValueIdentifier = CCacheValue::CACHEVALTAGANDCONCEPT;
563 if (conDes->getNegation()) {
564 cacheValueIdentifier = CCacheValue::CACHEVALTAGANDNEGATEDCONCEPT;
565 }
566 cacheValueList->prepend(CCacheValue(conTag,(cint64)conDes->getConcept(),cacheValueIdentifier));
567
568 conDesIt = conDesIt->getNextConceptDesciptor();
569 }
570 }
571
572
573 if (directBranched || cachingError) {
574 if (directBranched) {
575 satStorData->setIndividualNodeOrSuccessorBranchedConcept(true);
576 }
577 if (cachingError) {
578 STATINC(SATEXPCACHEWRITINGERRORCOUNT,calcAlgContext);
579 satStorData->setCachingError(true);
580 }
581 } else {
582
583 while (conDesIt) {
584 CConceptDescriptor* conDes = conDesIt;
585 cint64 conTag = conDes->getConceptTag();
586
587 CCacheValue::CACHEVALUEIDENTIFIER cacheValueIdentifier = CCacheValue::CACHEVALTAGANDCONCEPT;
588 if (conDes->getNegation()) {
589 cacheValueIdentifier = CCacheValue::CACHEVALTAGANDNEGATEDCONCEPT;
590 }
591 cacheValueList->prepend(CCacheValue(conTag,(cint64)conDes->getConcept(),cacheValueIdentifier));
592
593 conDesIt = conDesIt->getNextConceptDesciptor();
594 }
595
596 cint64 lastSig = lastCachedSignature;
597 cint64 newSig = lastSignature;
598
599 STATINC(SATEXPCACHEWRITINGSIGNATUREEXPANSIONCOUNT,calcAlgContext);
600 CSignatureSatisfiableExpanderCacheEntryExpandWriteData* expandWriteData = CObjectAllocator< CSignatureSatisfiableExpanderCacheEntryExpandWriteData >::allocateAndConstruct(satCacheMemMan);
601 expandWriteData->initExpandWriteData(lastSig,newSig,cacheValueList,depHash);
602 addCacheMessages(expandWriteData,calcAlgContext);
603
604 satStorData->setPreviousCached(true);
605 satStorData->setLastCachedSignature(newSig);
606 satStorData->setLastCachedConceptDescriptor(lastAddedConDes);
607 return true;
608 }
609 return false;
610 }
611
612
613
614
615
616
617
618
619 bool CSatisfiableExpanderCacheHandler::prepareCacheMessages(CCalculationAlgorithmContext* calcAlgContext) {
620 if (!mMemAllocMan) {
621 CTaskMemoryPoolAllocationManager satCacheMemManCreaterMemMan(&mMemPoolCon,calcAlgContext->getTemporaryMemoryAllocationManager());
622 mMemAllocMan = CObjectAllocator<CTaskMemoryPoolAllocationManager>::allocateAndConstruct(&satCacheMemManCreaterMemMan);
623 mMemAllocMan->initTaskMemoryPoolAllocationManager(&mMemPoolCon,calcAlgContext->getTemporaryMemoryAllocationManager());
624 mTmpContext = CObjectParameterizingAllocator< CContextBase,CMemoryAllocationManager* >::allocateAndConstructAndParameterize(mMemAllocMan,mMemAllocMan);
625 return true;
626 }
627 return false;
628 }
629
630 bool CSatisfiableExpanderCacheHandler::commitCacheMessages(CCalculationAlgorithmContext* calcAlgContext) {
631 if (mWriteData) {
632 CSignatureSatisfiableExpanderCacheEntryWriteData* commitWriteData = nullptr;
633 CSignatureSatisfiableExpanderCacheEntryWriteData* writeDataIt = mWriteData;
634 while (writeDataIt) {
635 CSignatureSatisfiableExpanderCacheEntryWriteData* tmpWriteData = writeDataIt;
636 writeDataIt = (CSignatureSatisfiableExpanderCacheEntryWriteData*)writeDataIt->getNext();
637 tmpWriteData->clearNext();
638 if (commitWriteData) {
639 commitWriteData = (CSignatureSatisfiableExpanderCacheEntryWriteData*)tmpWriteData->append(commitWriteData);
640 } else {
641 commitWriteData = tmpWriteData;
642 }
643 }
644 mSatCacheWriter->writeCachedData(commitWriteData,mMemPoolCon.takeMemoryPools());
645 mWriteData = nullptr;
646 mMemAllocMan = nullptr;
647 mTmpContext = nullptr;
648 return true;
649 }
650 return false;
651 }
652
653
654
655 bool CSatisfiableExpanderCacheHandler::addCacheMessages(CSignatureSatisfiableExpanderCacheEntryWriteData* expandWriteData, CCalculationAlgorithmContext* calcAlgContext) {
656 if (mWriteData) {
657 mWriteData = (CSignatureSatisfiableExpanderCacheEntryWriteData*)expandWriteData->append(mWriteData);
658 } else {
659 mWriteData = expandWriteData;
660 }
661 //commitCacheMessages(calcAlgContext);
662 return true;
663 }
664
665
666
667
668
669 bool CSatisfiableExpanderCacheHandler::isCardinalityRestrictionCriticalForSatisfiable(CIndividualProcessNode* individualNode, CConceptDescriptor* conDes, CCalculationAlgorithmContext* calcAlgContext) {
670 CConcept* concept = conDes->getConcept();
671 bool conNeg = conDes->getNegation();
672
673 cint64 conCode = concept->getOperatorCode();
674 if (!conNeg && (conCode == CCATMOST) || conNeg && (conCode == CCATLEAST)) {
675 cint64 cardinality = concept->getParameter() - 1*conNeg;
676 if (cardinality > 1) {
677 CRole* role = concept->getRole();
678 if (role) {
679 cint64 succCount = individualNode->getRoleSuccessorCount(role);
680 if (succCount >= cardinality) {
681 return hasInverseSubRole(role,calcAlgContext);
682 }
683 }
684 }
685 }
686 return false;
687 }
688
689
690
691 bool CSatisfiableExpanderCacheHandler::hasInverseSubRole(CRole* role, CCalculationAlgorithmContext* calcAlgContext) {
692 return true;
693 }
694
695 bool CSatisfiableExpanderCacheHandler::hasInverseSuperRole(CRole* role, CCalculationAlgorithmContext* calcAlgContext) {
696 return true;
697 }
698
699
700 bool CSatisfiableExpanderCacheHandler::isConceptRelevantForSatisfiableBranch(CIndividualProcessNode* individualNode, CConceptDescriptor* conDes, CCalculationAlgorithmContext* calcAlgContext) {
701 CConcept* concept = conDes->getConcept();
702 bool conNeg = conDes->getNegation();
703
704 cint64 conCode = concept->getOperatorCode();
705 CConceptOperator* conOperator = concept->getConceptOperator();
706 if (!conNeg && (conOperator->hasPartialOperatorCodeFlag(CConceptOperator::CCFS_ALL_AQALL_TYPE)) || conNeg && (conCode == CCSOME)) {
707 CRole* role = concept->getRole();
708 if (role) {
709 return hasInverseSubRole(role,calcAlgContext);
710 }
711 }
712 if (!conNeg && (conCode == CCATMOST) || conNeg && (conCode == CCATLEAST)) {
713 CRole* role = concept->getRole();
714 if (role) {
715 if (hasInverseSubRole(role,calcAlgContext)) {
716 cint64 cardinality = concept->getParameter() - 1*conNeg;
717 cint64 succCount = individualNode->getRoleSuccessorCount(role);
718 if (succCount >= cardinality) {
719 return true;
720 }
721 return false;
722 } else {
723 return false;
724 }
725 }
726 }
727 if (!conNeg && (conCode == CCSOME || conCode == CCAQSOME || conCode == CCATLEAST) || conNeg && (conCode == CCALL || conCode == CCATMOST)) {
728 CRole* role = concept->getRole();
729 if (role) {
730 // test has ATMOST restriction for some super role
731 CSortedNegLinker<CRole*>* superRoleIt = role->getIndirectSuperRoleList();
732 while (superRoleIt) {
733 if (!superRoleIt->isNegated()) {
734 CRole* superRole = superRoleIt->getData();
735 CReapplyQueueIterator reapplyIt = individualNode->getRoleReapplyIterator(superRole,false);
736 while (reapplyIt.hasNext()) {
737 CReapplyConceptDescriptor* reapplyDes = reapplyIt.next();
738 CConceptDescriptor* reapplyConDes = reapplyDes->getConceptDescriptor();
739 CConcept* reapplyConcept = reapplyConDes->getConcept();
740 CRole* reapplyRole = reapplyConcept->getRole();
741 bool reapplyConNeg = reapplyConDes->getNegation();
742 cint64 reapplyConOpCode = reapplyConcept->getOperatorCode();
743 if (reapplyConNeg && reapplyConOpCode == CCATLEAST || !reapplyConNeg && reapplyConOpCode == CCATMOST) {
744 cint64 cardinality = reapplyConcept->getParameter() - 1*reapplyConNeg;
745 cint64 succCount = individualNode->getRoleSuccessorCount(role);
746 if (succCount >= cardinality) {
747 return hasInverseSubRole(reapplyRole,calcAlgContext);
748 }
749 }
750 }
751 }
752 superRoleIt = superRoleIt->getNext();
753 }
754 return false;
755 }
756 }
757 if (!conNeg && (conOperator->hasPartialOperatorCodeFlag(CConceptOperator::CCFS_AQAND_TYPE))) {
758 return isAutomatConceptRelevantForSatisfiableBranch(individualNode,concept,conNeg,calcAlgContext);
759 }
760 return false;
761 }
762
763
764
765 bool CSatisfiableExpanderCacheHandler::isAutomatConceptRelevantForSatisfiableBranch(CIndividualProcessNode* individualNode, CConcept* concept, bool conNegation, CCalculationAlgorithmContext* calcAlgContext) {
766 cint64 conCode = concept->getOperatorCode();
767 CConceptOperator* conOperator = concept->getConceptOperator();
768 if (conOperator->hasPartialOperatorCodeFlag(CConceptOperator::CCFS_AQALL_TYPE)) {
769 CRole* role = concept->getRole();
770 if (role) {
771 CSortedNegLinker<CRole*>* superRoleIt = role->getIndirectSuperRoleList();
772 while (superRoleIt) {
773 if (superRoleIt->isNegated()) {
774 return true;
775 }
776 superRoleIt = superRoleIt->getNext();
777 }
778 }
779 } else if (conOperator->hasPartialOperatorCodeFlag(CConceptOperator::CCFS_AQAND_TYPE)) {
780 CSortedNegLinker<CConcept*>* opConLinkerIt = concept->getOperandList();
781 while (opConLinkerIt) {
782 CConcept* opCon = opConLinkerIt->getData();
783 bool opNeg = opConLinkerIt->isNegated();
784 if (isAutomatConceptRelevantForSatisfiableBranch(individualNode,opCon,opNeg,calcAlgContext)) {
785 return true;
786 }
787 opConLinkerIt = opConLinkerIt->getNext();
788 }
789 }
790 return false;
791 }
792
793
794
795 bool CSatisfiableExpanderCacheHandler::simpleDependencyTracking(CIndividualProcessNode* individualNode, cint64 conTag, CDependencyTrackPoint* depTrackPoint, CCACHINGHASH<cint64,cint64>* depHash, CPROCESSINGSET<cint64>* notBranchConceptsSet, bool* branchedFlag, CCalculationAlgorithmContext* calcAlgContext) {
796 if (branchedFlag && !depTrackPoint->isPointingToDeterministicDependencyNode()) {
797 *branchedFlag = true;
798 return true;
799 }
800 if (depTrackPoint->isPointingToIndependentDependencyNode()) {
801 return true;
802 }
803 CDependencyNode* depNode = depTrackPoint->getDependencyNode();
804 if (depNode->hasAdditionalDependencies()) {
805 return false;
806 }
807 if (depNode->hasAppropriateIndividualNode()) {
808 CIndividualProcessNode* appIndiNode = depNode->getAppropriateIndividualNode();
809 cint64 appIndiDepth = appIndiNode->getIndividualAncestorDepth();
810 cint64 baseDepth = individualNode->getIndividualAncestorDepth();
811 if (appIndiDepth != baseDepth) {
812 return false;
813 }
814 }
815 CConceptDescriptor* conDes = depNode->getConceptDescriptor();
816 if (conDes) {
817 cint64 depConTag = conDes->getConceptTag();
818
819 if (branchedFlag && notBranchConceptsSet && !notBranchConceptsSet->contains(conDes->getConceptTag())) {
820 *branchedFlag = true;
821 return true;
822 }
823 depHash->insertMulti(conTag,depConTag);
824
825
826
827 //CConceptDescriptor* cD = nullptr;
828 //CDependencyTrackPoint* dTP = nullptr;
829 //if (individualNode->getReapplyConceptLabelSet(false)->getConceptDescriptor(conTag,cD,dTP)) {
830 // if (cD->isNegated() && cD->getConcept()->getOperatorCode() == CCSUB) {
831 // if (conDes->isNegated() && conDes->getConcept()->getOperatorCode() == CCSUB) {
832 // bool bug = true;
833 // }
834 // }
835 //}
836
837
838 //CConceptDescriptor* cD = nullptr;
839 //CDependencyTrackPoint* dTP = nullptr;
840 //if (!individualNode->getReapplyConceptLabelSet(false)->getConceptDescriptor(depConTag,cD,dTP)) {
841 // bool bug = true;
842 //} else {
843 // CConceptDescriptor* conDesIt = cD;
844 // while (conDesIt) {
845 // if (conDesIt->getConceptTag() == conTag) {
846 // bool bug = true;
847 // }
848 // conDesIt = conDesIt->getNext();
849 // }
850
851 // bool foundDepTag = false;
852 // conDesIt = conDes;
853 // while (conDesIt) {
854 // if (conDesIt->getConceptTag() == depConTag) {
855 // foundDepTag = true;
856 // }
857 // conDesIt = conDesIt->getNext();
858 // }
859 // if (!foundDepTag) {
860 // bool bug = true;
861 // }
862 //}
863
864 return true;
865 }
866 return false;
867 }
868
869
870
871 bool CSatisfiableExpanderCacheHandler::complexDependencyTracking(CIndividualProcessNode* individualNode, cint64 conTag, CPROCESSINGSET<CDepthDependencyPair>* depSet, CPROCESSINGLIST<CDepthDependencyPair>* depList, CCACHINGHASH<cint64,cint64>* depHash, CPROCESSINGSET<cint64>* notBranchConceptsSet, bool* branchedFlag, CCalculationAlgorithmContext* calcAlgContext) {
872 cint64 baseAncDepth = individualNode->getIndividualAncestorDepth();
873 while (!depList->isEmpty()) {
874 CDepthDependencyPair depthDepPair(depList->takeFirst());
875 cint64 ancDepth = depthDepPair.first;
876 CDependencyTrackPoint* depTrackPoint = depthDepPair.second;
877
878 if (branchedFlag && !depTrackPoint->isPointingToDeterministicDependencyNode()) {
879 *branchedFlag = true;
880 return true;
881 }
882
883 CDependencyNode* depNode = depTrackPoint->getDependencyNode();
884 CIndividualProcessNode* appIndiNode = depNode->getAppropriateIndividualNode();
885 cint64 newAncDepth = ancDepth;
886 bool continueDepLoading = true;
887 if (appIndiNode) {
888 newAncDepth = appIndiNode->getIndividualAncestorDepth();
889 }
890 if (newAncDepth == baseAncDepth) {
891 CConceptDescriptor* conDes = depNode->getConceptDescriptor();
892 if (conDes) {
893 if (branchedFlag && notBranchConceptsSet) {
894 if (!notBranchConceptsSet->contains(conDes->getConceptTag())) {
895 *branchedFlag = true;
896 return true;
897 }
898 }
899 continueDepLoading = false;
900 cint64 depConTag = conDes->getConceptTag();
901 if (depConTag != conTag) {
902 depHash->insertMulti(conTag,depConTag);
903
904
905 //CConceptDescriptor* cD = nullptr;
906 //CDependencyTrackPoint* dTP = nullptr;
907 //if (individualNode->getReapplyConceptLabelSet(false)->getConceptDescriptor(conTag,cD,dTP)) {
908 // if (cD->isNegated() && cD->getConcept()->getOperatorCode() == CCSUB) {
909 // if (conDes->isNegated() && conDes->getConcept()->getOperatorCode() == CCSUB) {
910 // bool bug = true;
911 // }
912 // }
913 //}
914
915
916 //CConceptDescriptor* cD = nullptr;
917 //CDependencyTrackPoint* dTP = nullptr;
918 //if (!individualNode->getReapplyConceptLabelSet(false)->getConceptDescriptor(depConTag,cD,dTP)) {
919 // bool bug = true;
920 //} else {
921 // CConceptDescriptor* conDesIt = cD;
922 // while (conDesIt) {
923 // if (conDesIt->getConceptTag() == conTag) {
924 // bool bug = true;
925 // }
926 // conDesIt = conDesIt->getNext();
927 // }
928
929 // bool foundDepTag = false;
930 // conDesIt = conDes;
931 // while (conDesIt) {
932 // if (conDesIt->getConceptTag() == depConTag) {
933 // foundDepTag = true;
934 // }
935 // conDesIt = conDesIt->getNext();
936 // }
937 // if (!foundDepTag) {
938 // bool bug = true;
939 // }
940
941 //}
942 }
943 }
944 }
945 if (newAncDepth < baseAncDepth) {
946 return false;
947 }
948 if (continueDepLoading) {
949 CDependencyTrackPoint* prevDepTrackPoint = depNode->getPreviousDependencyTrackPoint();
950 cint64 nextAncDepth = newAncDepth;
951 CDependencyNode* nextDepNode = prevDepTrackPoint->getDependencyNode();
952 if (nextDepNode && nextDepNode->hasAppropriateIndividualNode()) {
953 nextAncDepth = nextDepNode->getAppropriateIndividualNode()->getIndividualAncestorDepth();
954 }
955 if (!depSet->contains(CDepthDependencyPair(nextAncDepth,prevDepTrackPoint))) {
956 depSet->insert(CDepthDependencyPair(nextAncDepth,prevDepTrackPoint));
957 depList->append(CDepthDependencyPair(nextAncDepth,prevDepTrackPoint));
958 }
959 }
960
961 CDependencyIterator depIt = depNode->getAdditionalDependencyIterator();
962 while (depIt.hasNext()) {
963 CDependency* dependency = depIt.nextDependency();
964 // load additional dependencies
965 CDependencyTrackPoint* prevDepTrackPoint = dependency->getPreviousDependencyTrackPoint();
966 cint64 nextAncDepth = ancDepth;
967 CDependencyNode* nextDepNode = prevDepTrackPoint->getDependencyNode();
968 if (nextDepNode && nextDepNode->hasAppropriateIndividualNode()) {
969 nextAncDepth = nextDepNode->getAppropriateIndividualNode()->getIndividualAncestorDepth();
970 }
971 if (!depSet->contains(CDepthDependencyPair(ancDepth,prevDepTrackPoint))) {
972 depSet->insert(CDepthDependencyPair(ancDepth,prevDepTrackPoint));
973 depList->append(CDepthDependencyPair(ancDepth,prevDepTrackPoint));
974 }
975 }
976 }
977 return true;
978 }
979
980
981
982 bool CSatisfiableExpanderCacheHandler::hasDependencyToAncestor(CIndividualProcessNode* individualNode, CDependencyTrackPoint* depTrackPoint, bool* branchedFlag, CCalculationAlgorithmContext* calcAlgContext) {
983 cint64 ancDepth = individualNode->getIndividualAncestorDepth();
984 bool dependencyToAncestor = false;
985 if (ancDepth <= 0) {
986 dependencyToAncestor = depTrackPoint->isPointingToIndependentDependencyNode();
987 } else {
988 CDependencyNode* depNode = depTrackPoint->getDependencyNode();
989 if (depNode->hasAppropriateIndividualNode()) {
990 CIndividualProcessNode* appIndiNode = depNode->getAppropriateIndividualNode();
991 cint64 appIndiAncDepth = appIndiNode->getIndividualAncestorDepth();
992 dependencyToAncestor = appIndiAncDepth < ancDepth;
993 } else {
994 CDependencyNode::DEPENDENCNODEYTYPE depType = depNode->getDependencyType();
995 if (depType == CDependencyNode::DNTMERGEDCONCEPT) {
996 dependencyToAncestor = hasDependencyToAncestor(individualNode,depNode->getPreviousDependencyTrackPoint(),branchedFlag,calcAlgContext);
997 }
998 }
999 }
1000 if (!dependencyToAncestor && branchedFlag) {
1001 if (!depTrackPoint->isPointingToDeterministicDependencyNode()) {
1002 *branchedFlag = true;
1003 }
1004 }
1005 return dependencyToAncestor;
1006 }
1007
1008
1009
1010
1011 }; // end namespace Algorithm
1012
1013 }; // end namespace Kernel
1014
1015 }; // end namespace Reasoner
1016
1017 }; // end namespace Konclude