Debian Codegraph @

Source/Reasoner/Kernel/Algorithm/CUnsatisfiableCacheHandler.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 "CUnsatisfiableCacheHandler.h"
22
23
24 namespace Konclude {
25
26 namespace Reasoner {
27
28 namespace Kernel {
29
30 namespace Algorithm {
31
32 CUnsatisfiableCacheHandler::CUnsatisfiableCacheHandler(COccurrenceUnsatisfiableCacheReader* occurUnsatCacheReader, COccurrenceUnsatisfiableCacheWriter* occurUnsatCacheWriter) {
33 mOccurUnsatCacheReader = occurUnsatCacheReader;
34 mOccurUnsatCacheWriter = occurUnsatCacheWriter;
35 mConfConceptDataUnsatisfiablePrecheck = true;
36 }
37
38
39 CUnsatisfiableCacheHandler::~CUnsatisfiableCacheHandler() {
40 }
41
42
43 bool CUnsatisfiableCacheHandler::isIndividualNodeUnsatisfiableCached(CIndividualProcessNode* individualNode, CClashedDependencyDescriptor*& clashDescriptors, CCalculationAlgorithmContext* calcAlgContext) {
44 STATINC(UNSATCACHERETRIEVALCOUNT,calcAlgContext);
45 bool unsatisfiableChecked = false;
46 CConceptDescriptor* lastConDes = nullptr;
47 cint64 lastRetCachingTag = 0;
48
49 CReapplyConceptLabelSet* conSet = individualNode->getReapplyConceptLabelSet(false);
50 CConceptDescriptor* conDesLinker = conSet->getAddingSortedConceptDescriptionLinker();
51 cint64 currentCachingTag = mOccurUnsatCacheReader->getCurrentCachingTag();
52
53 CIndividualNodeUnsatisfiableOccurenceCacheRetrievalData* unsatRetData = (CIndividualNodeUnsatisfiableOccurenceCacheRetrievalData*)individualNode->getIndividualUnsatisfiableCacheRetrievalData(false);
54 if (unsatRetData) {
55 lastRetCachingTag = unsatRetData->getLastRetrievalCachingTag();
56 lastConDes = unsatRetData->getLastRetrievalConceptDescriptor();
57 // nothing has changed
58 if (lastRetCachingTag >= currentCachingTag && lastConDes == conDesLinker) {
59 return false;
60 }
61 }
62
63 if (lastConDes != conDesLinker) {
64 lastRetCachingTag = 0;
65 }
66
67 if (mConfConceptDataUnsatisfiablePrecheck) {
68 STATINC(UNSATCACHERETRIEVALPRECHECKCOUNT,calcAlgContext);
69 cint64 minMaxCachedTag = CINT64_MAX;
70 cint64 maxMinCachedTag = CINT64_MIN;
71 cint64 minUnsatCachedSize = CINT64_MAX;
72 cint64 possCachedCount = 0;
73 cint64 maxLastCachingTag = 0;
74 CConceptDescriptor* conDesIt = conDesLinker;
75 while (conDesIt && lastConDes != conDesIt) {
76 CConcept* concept = conDesIt->getConcept();
77 bool conNeg = conDesIt->getNegation();
78 CConceptProcessData* conProcData = (CConceptProcessData*)concept->getConceptData();
79 if (conProcData) {
80 CUnsatisfiableCachingTags* cachingTags = conProcData->getUnsatisfiableCachingTags(conNeg);
81 if (cachingTags) {
82 if (cachingTags->candidateTags(minMaxCachedTag,maxMinCachedTag,minUnsatCachedSize,lastRetCachingTag+1)) {
83 ++possCachedCount;
84 lastConDes = nullptr;
85 }
86 }
87 }
88 conDesIt = conDesIt->getNext();
89 }
90 if (possCachedCount < minUnsatCachedSize) {
91 STATINC(UNSATCACHERETRIEVALPRECHECKDIRECTFAILEDCOUNT,calcAlgContext);
92 unsatisfiableChecked = true;
93 } else if (minMaxCachedTag == maxMinCachedTag) {
94 // try to get unsatisfiable concepts
95 cint64 unsatLineCount = CINT64_MAX;
96 cint64 foundUnsatLineCount = 0;
97 CConceptDescriptor* conDesIt = conDesLinker;
98 while (conDesIt && lastConDes != conDesIt && foundUnsatLineCount <= unsatLineCount) {
99 CConcept* concept = conDesIt->getConcept();
100 bool conNeg = conDesIt->getNegation();
101 CConceptProcessData* conProcData = (CConceptProcessData*)concept->getConceptData();
102 if (conProcData) {
103 CUnsatisfiableCachingTags* cachingTags = conProcData->getUnsatisfiableCachingTags(conNeg);
104 if (cachingTags) {
105 if (cachingTags->hasCandidateTags(minMaxCachedTag,maxMinCachedTag,lastRetCachingTag+1)) {
106 ++foundUnsatLineCount;
107 cachingTags->candidateMinUnsatisfiableSize(unsatLineCount,maxMinCachedTag);
108 }
109 }
110 }
111 conDesIt = conDesIt->getNext();
112 }
113
114 if (foundUnsatLineCount == unsatLineCount) {
115 // found unsatisfiable concepts, try to extract clashes
116 cint64 clashLinkerGenCount = 0;
117 CClashedDependencyDescriptor* clashedDepDesLinker = nullptr;
118 CReapplyConceptLabelSetIterator conSetIt = conSet->getConceptLabelSetIterator(false,true,false);
119 while (conSetIt.hasNext()) {
120 CConceptDescriptor* conDes = conSetIt.getConceptDescriptor();
121 CDependencyTrackPoint* depTrackPoint = conSetIt.getDependencyTrackPoint();
122 CConcept* concept = conDes->getConcept();
123 bool conNeg = conDes->getNegation();
124
125 CConceptProcessData* conProcData = (CConceptProcessData*)concept->getConceptData();
126 if (conProcData) {
127 CUnsatisfiableCachingTags* cachingTags = conProcData->getUnsatisfiableCachingTags(conNeg);
128 if (cachingTags) {
129 if (cachingTags->hasCandidateTags(minMaxCachedTag,maxMinCachedTag,lastRetCachingTag+1)) {
130 ++clashLinkerGenCount;
131 clashedDepDesLinker = calcAlgContext->getUsedClashDescriptorFactory()->createClashedConceptDescriptor(clashedDepDesLinker,individualNode,conDes,depTrackPoint,calcAlgContext);
132 if (clashLinkerGenCount == unsatLineCount) {
133 clashDescriptors = clashedDepDesLinker->append(clashDescriptors);
134 STATINC(UNSATCACHERETRIEVALPRECHECKSUCCESSCOUNT,calcAlgContext);
135 return true;
136 }
137 }
138 }
139 }
140 conSetIt.moveNext();
141 }
142 STATINC(UNSATCACHERETRIEVALPRECHECKINSUFFICIENTCOUNT,calcAlgContext);
143 } else {
144 STATINC(UNSATCACHERETRIEVALPRECHECKINSUFFICIENTCOUNT,calcAlgContext);
145 }
146 }
147 }
148
149 CMemoryAllocationManager* memMan = calcAlgContext->getUsedTemporaryMemoryAllocationManager();
150
151 if (!unsatisfiableChecked) {
152 STATINC(UNSATCACHERETRIEVALHASHCOUNT,calcAlgContext);
153 CXLinker<CCacheValue*>* cacheTestLinker = nullptr;
154 CXLinker<CCacheValue*>* lastCacheTestLinker = nullptr;
155 // build concept linkers for cache testing
156 CReapplyConceptLabelSetIterator conSetIt = conSet->getConceptLabelSetIterator(true);
157 while (conSetIt.hasNext()) {
158 CConceptDescriptor* conDes = conSetIt.getConceptDescriptor();
159 CConcept* concept = conDes->getConcept();
160 bool conNeg = conDes->getNegation();
161 CConceptProcessData* conProcData = (CConceptProcessData*)concept->getConceptData();
162 if (conProcData) {
163 CUnsatisfiableCachingTags* cachingTags = conProcData->getUnsatisfiableCachingTags(conNeg);
164 if (cachingTags) {
165 CCacheValue* cacheValue = CObjectAllocator<CCacheValue>::allocateAndConstruct(memMan);
166 if (!conNeg) {
167 cacheValue->initCacheValue(concept->getConceptTag(),(cint64)concept,CCacheValue::CACHEVALTAGANDCONCEPT);
168 } else {
169 cacheValue->initCacheValue(concept->getConceptTag(),(cint64)concept,CCacheValue::CACHEVALTAGANDNEGATEDCONCEPT);
170 }
171 CXLinker<CCacheValue*>* nextCacheTestLinker = CObjectAllocator< CXLinker<CCacheValue*> >::allocateAndConstruct(memMan);
172 nextCacheTestLinker->initLinker(cacheValue);
173 if (!lastCacheTestLinker) {
174 cacheTestLinker = nextCacheTestLinker;
175 lastCacheTestLinker = nextCacheTestLinker;
176 } else {
177 lastCacheTestLinker->append(nextCacheTestLinker);
178 lastCacheTestLinker = nextCacheTestLinker;
179 }
180 }
181 }
182 conSetIt.moveNext();
183 }
184
185 if (cacheTestLinker) {
186 CXLinker<CCacheValue*>* unsatLinker = mOccurUnsatCacheReader->getUnsatisfiableItems(cacheTestLinker,memMan);
187 if (!unsatLinker) {
188 // not unsatisfiable
189 unsatisfiableChecked = true;
190 STATINC(UNSATCACHERETRIEVALHASHFAILEDCOUNT,calcAlgContext);
191 } else {
192 // found unsatisfiable cached concepts, extract clashes
193 CXLinker<CCacheValue*>* unsatLinkerIt = unsatLinker;
194 while (unsatLinkerIt) {
195 CCacheValue* cacheValue = unsatLinkerIt->getData();
196 CConcept* concept = (CConcept*)cacheValue->getIdentification();
197 CConceptDescriptor* conDes = nullptr;
198 CDependencyTrackPoint* depTrackPoint = nullptr;
199 conSet->getConceptDescriptor(concept,conDes,depTrackPoint);
200
201 clashDescriptors = calcAlgContext->getUsedClashDescriptorFactory()->createClashedConceptDescriptor(clashDescriptors,individualNode,conDes,depTrackPoint,calcAlgContext);
202
203 unsatLinkerIt = unsatLinkerIt->getNext();
204 STATINC(UNSATCACHERETRIEVALHASHSUCCESSCOUNT,calcAlgContext);
205 }
206 return true;
207 }
208 }
209 return false;
210 }
211
212 if (unsatisfiableChecked) {
213
214 CIndividualNodeUnsatisfiableOccurenceCacheRetrievalData* locUnsatRetData = (CIndividualNodeUnsatisfiableOccurenceCacheRetrievalData*)individualNode->getIndividualUnsatisfiableCacheRetrievalData(true);
215 if (!locUnsatRetData) {
216 CMemoryAllocationManager* taskMemMan = calcAlgContext->getUsedProcessTaskMemoryAllocationManager();
217 locUnsatRetData = CObjectAllocator<CIndividualNodeUnsatisfiableOccurenceCacheRetrievalData>::allocateAndConstruct(taskMemMan);
218 individualNode->setIndividualUnsatisfiableCacheRetrievalData(locUnsatRetData);
219 }
220 locUnsatRetData->setLastRetrievalCachingTag(currentCachingTag);
221 locUnsatRetData->setLastRetrievalConceptDescriptor(conDesLinker);
222 }
223
224 return false;
225 }
226
227
228
229 bool CUnsatisfiableCacheHandler::areClashedDescriptorsLastCached(CTrackedClashedDescriptor* trackedClashedDes, CCalculationAlgorithmContext* calcAlgContext) {
230 CTrackedClashedDescriptor* trackedClashedDesIt = trackedClashedDes;
231 for (QList<CCacheValue>::const_iterator it = mUnsatItemList.constBegin(), itEnd = mUnsatItemList.constEnd(); it != itEnd; ++it) {
232 if (!trackedClashedDesIt) {
233 return false;
234 }
235 CCacheValue cachedValueItem(*it);
236
237 CConceptDescriptor* conDes = trackedClashedDesIt->getConceptDescriptor();
238 CConcept* concept = conDes->getConcept();
239 bool conNeg = conDes->getNegation();
240
241 if (conNeg) {
242 if (cachedValueItem.getCacheValueIdentifier() != CCacheValue::CACHEVALTAGANDNEGATEDCONCEPT) {
243 return false;
244 }
245 } else {
246 if (cachedValueItem.getCacheValueIdentifier() != CCacheValue::CACHEVALTAGANDCONCEPT) {
247 return false;
248 }
249 }
250 if ((CConcept*)cachedValueItem.getIdentification() != concept) {
251 return false;
252 }
253
254 trackedClashedDesIt = trackedClashedDesIt->getNextDescriptor();
255
256 }
257 if (trackedClashedDesIt) {
258 return false;
259 }
260 return true;
261 }
262
263
264 bool CUnsatisfiableCacheHandler::areClashedDescriptorsAlreadyCached(CTrackedClashedDescriptor* trackedClashedDes, CCalculationAlgorithmContext* calcAlgContext) {
265 STATINC(UNSATCACHEWRITINGALREADYCACHEDTESTCOUNT,calcAlgContext);
266
267 if (areClashedDescriptorsLastCached(trackedClashedDes,calcAlgContext)) {
268 return true;
269 }
270
271 CTrackedClashedDescriptor* trackedClashedDesIt = trackedClashedDes;
272 while (trackedClashedDesIt) {
273 CConceptDescriptor* conDes = trackedClashedDesIt->getConceptDescriptor();
274 CConcept* concept = conDes->getConcept();
275 bool conNeg = conDes->getNegation();
276 CConceptProcessData* conProcData = (CConceptProcessData*)concept->getConceptData();
277 bool clashDesCached = false;
278 if (conProcData) {
279 CUnsatisfiableCachingTags* cachingTags = conProcData->getUnsatisfiableCachingTags(conNeg);
280 if (cachingTags) {
281 if (cachingTags->getLastCachingTag() > 0) {
282 clashDesCached = true;
283 }
284 }
285 }
286 if (!clashDesCached) {
287 STATINC(UNSATCACHEWRITINGALREADYCACHEDTESTPRECHECKFAILEDCOUNT,calcAlgContext);
288 return false;
289 }
290 trackedClashedDesIt = trackedClashedDesIt->getNextDescriptor();
291 }
292 CMemoryAllocationManager* memMan = calcAlgContext->getUsedTemporaryMemoryAllocationManager();
293 CXLinker<CCacheValue*>* cacheTestLinker = nullptr;
294 CXLinker<CCacheValue*>* lastCacheTestLinker = nullptr;
295 trackedClashedDesIt = trackedClashedDes;
296 CCacheValue* lastCacheValue = nullptr;
297 while (trackedClashedDesIt) {
298 CConceptDescriptor* conDes = trackedClashedDesIt->getConceptDescriptor();
299 CConcept* concept = conDes->getConcept();
300 bool conNeg = conDes->getNegation();
301
302 CCacheValue* cacheValue = CObjectAllocator<CCacheValue>::allocateAndConstruct(memMan);
303 if (!conNeg) {
304 cacheValue->initCacheValue(concept->getConceptTag(),(cint64)concept,CCacheValue::CACHEVALTAGANDCONCEPT);
305 } else {
306 cacheValue->initCacheValue(concept->getConceptTag(),(cint64)concept,CCacheValue::CACHEVALTAGANDNEGATEDCONCEPT);
307 }
308 if (!lastCacheValue || *lastCacheValue != *cacheValue) {
309 CXLinker<CCacheValue*>* nextCacheTestLinker = CObjectAllocator< CXLinker<CCacheValue*> >::allocateAndConstruct(memMan);
310 nextCacheTestLinker->initLinker(cacheValue);
311 if (!lastCacheTestLinker) {
312 cacheTestLinker = nextCacheTestLinker;
313 lastCacheTestLinker = nextCacheTestLinker;
314 } else {
315 lastCacheTestLinker->append(nextCacheTestLinker);
316 lastCacheTestLinker = nextCacheTestLinker;
317 }
318 lastCacheValue = cacheValue;
319 }
320 trackedClashedDesIt = trackedClashedDesIt->getNextDescriptor();
321 }
322 CXLinker<CCacheValue*>* unsatLinker = mOccurUnsatCacheReader->getUnsatisfiableItems(cacheTestLinker,memMan);
323 if (unsatLinker) {
324 STATINC(UNSATCACHEWRITINGALREADYCACHEDTESTHASHFAILEDCOUNT,calcAlgContext);
325 }
326 return unsatLinker != nullptr;
327 }
328
329
330 bool CUnsatisfiableCacheHandler::writeUnsatisfiableClashedDescriptors(CTrackedClashedDescriptor* trackedClashedDes, CCalculationAlgorithmContext* calcAlgContext) {
331 STATINC(UNSATCACHEWRITINGTRYINGCOUNT,calcAlgContext);
332 if (!areClashedDescriptorsAlreadyCached(trackedClashedDes,calcAlgContext)) {
333 mUnsatItemList.clear();
334 CTrackedClashedDescriptor* trackedClashedDesIt = trackedClashedDes;
335 while (trackedClashedDesIt) {
336 CConceptDescriptor* conDes = trackedClashedDesIt->getConceptDescriptor();
337 if (conDes->isNegated()) {
338 mUnsatItemList.append(CCacheValue(conDes->getConceptTag(),(cint64)conDes->getConcept(),CCacheValue::CACHEVALTAGANDNEGATEDCONCEPT));
339 } else {
340 mUnsatItemList.append(CCacheValue(conDes->getConceptTag(),(cint64)conDes->getConcept(),CCacheValue::CACHEVALTAGANDCONCEPT));
341 }
342 trackedClashedDesIt = trackedClashedDesIt->getNextDescriptor();
343 }
344 mOccurUnsatCacheWriter->setUnsatisfiable(mUnsatItemList);
345 STATINC(UNSATCACHEWRITINGCOUNT,calcAlgContext);
346 return true;
347 } else {
348 STATINC(UNSATCACHEWRITINGALREADYCACHEDCOUNT,calcAlgContext);
349 }
350 return false;
351 }
352
353
354 bool CUnsatisfiableCacheHandler::writeUnsatisfiableClashedConcept(CConcept* concept, CCalculationAlgorithmContext* calcAlgContext) {
355 STATINC(UNSATCACHEWRITINGTRYINGCOUNT,calcAlgContext);
356 if (true) {
357 mUnsatItemList.clear();
358 mUnsatItemList.append(CCacheValue(concept->getConceptTag(),(cint64)concept,CCacheValue::CACHEVALTAGANDCONCEPT));
359 mOccurUnsatCacheWriter->setUnsatisfiable(mUnsatItemList);
360 STATINC(UNSATCACHEWRITINGCOUNT,calcAlgContext);
361 return true;
362 } else {
363 STATINC(UNSATCACHEWRITINGALREADYCACHEDCOUNT,calcAlgContext);
364 }
365 return false;
366 }
367
368
369
370 }; // end namespace Algorithm
371
372 }; // end namespace Kernel
373
374 }; // end namespace Reasoner
375
376 }; // end namespace Konclude