001 package com.hammurapi.reasoning.impl;
002
003 import java.lang.ref.Reference;
004 import java.lang.ref.WeakReference;
005 import java.lang.reflect.Method;
006 import java.util.ArrayList;
007 import java.util.Collection;
008 import java.util.Collections;
009 import java.util.HashMap;
010 import java.util.HashSet;
011 import java.util.Iterator;
012 import java.util.List;
013 import java.util.Map;
014 import java.util.Set;
015 import java.util.WeakHashMap;
016 import java.util.Map.Entry;
017 import java.util.concurrent.Executor;
018 import java.util.concurrent.atomic.AtomicInteger;
019 import java.util.concurrent.locks.Lock;
020 import java.util.concurrent.locks.ReadWriteLock;
021 import java.util.concurrent.locks.ReentrantReadWriteLock;
022 import java.util.logging.Level;
023 import java.util.logging.Logger;
024
025 import com.hammurapi.reasoning.Derivation;
026 import com.hammurapi.reasoning.ExceptionHandler;
027 import com.hammurapi.reasoning.Handle;
028 import com.hammurapi.reasoning.InferenceListener;
029 import com.hammurapi.reasoning.ReasoningException;
030
031 /**
032 * Knowledge base which uses in-memory collecitons.
033 * @author Pavel Vlasov
034 */
035 public class InMemoryKnowledgeBase<F> implements KnowledgeBase<F> {
036
037 private static final Logger logger = Logger.getLogger(InMemoryKnowledgeBase.class.getName());
038
039 private String name;
040 private String description;
041 private Executor executor;
042
043 /**
044 * @param executor Executor for delegation of execution of undo tasks.
045 */
046 public void setExecutor(Executor executor) {
047 this.executor = executor;
048 }
049
050 public Executor getExecutor() {
051 return executor;
052 }
053
054 private boolean isFine;
055
056 /**
057 * Creates a new simple knowledge base.
058 * @param weak If true, a weak hash map is used for fact storage.
059 * It can be useful for long running sessions with inference listener.
060 * Use of weak hash map ensures that the session will not run out of memory.
061 * When a weak hash map is used, some derivations may become invalid when
062 * source facts of conclusions get garbage collected.
063 */
064 public InMemoryKnowledgeBase(String name, String description, boolean weak) {
065 this.name = name;
066 this.description = description;
067 storage = weak ? new WeakHashMap<F, HandleImpl<F>>() : new HashMap<F, HandleImpl<F>>();
068 isFine = logger.isLoggable(Level.FINE);
069 }
070
071 private Map<String, Reference<Collection<?>>> collections = new HashMap<String, Reference<Collection<?>>>();
072
073 // Handle collections shall also support array types, or there should be handlearray collections.
074 /**
075 * Lists of handles are array lists, for other element types lists are facades for handle lists.
076 */
077 @SuppressWarnings("unchecked")
078 @Override
079 public <T> List<T> getList(String id, Class<T> elementType) {
080 synchronized (collections) {
081 Reference<Collection<?>> ref = collections.get(id);
082 List<T> ret = (List<T>) (ref==null ? null : ref.get());
083 if (ret==null) {
084 if (doNotWrap(elementType)) {
085 ret = new ArrayList<T>();
086 } else if (elementType.isArray()) {
087 throw new UnsupportedOperationException("Collections of arrays are not supported yet");
088 } else {
089 ret = new HandleList<T>((KnowledgeBase<T>) this, new ArrayList<Handle<T>>()); // Cast is a hack around generics.
090 }
091 collections.put(id, new WeakReference<Collection<?>>(ret));
092 }
093 return ret;
094 }
095 }
096
097 private <T> boolean doNotWrap(Class<T> elementType) {
098 return Handle.class.isAssignableFrom(elementType)
099 || InferenceToken.class.isAssignableFrom(elementType)
100 || (elementType.isArray() && doNotWrap(elementType.getComponentType()))
101 || Collection.class.isAssignableFrom(elementType);
102 }
103
104 /**
105 * Sets of handles are hash sets, for other element types sets are facades for handle sets.
106 */
107 @SuppressWarnings("unchecked")
108 @Override
109 public <T> Set<? extends T> getSet(String id, Class<T> elementType) {
110 synchronized (collections) {
111 Reference<Collection<?>> ref = collections.get(id);
112 Set<T> ret = (Set<T>) (ref==null ? null : ref.get());
113 if (ret==null) {
114 if (doNotWrap(elementType)) {
115 ret = new HashSet<T>();
116 } else if (elementType.isArray()) {
117 throw new UnsupportedOperationException("Collections of arrays are not supported yet");
118 } else {
119 ret = new HandleSet<T>((KnowledgeBase<T>) this, new HashSet<Handle<T>>()); // Cast is a hack around generics.
120 }
121 collections.put(id, new WeakReference<Collection<?>>(ret));
122 }
123 return ret;
124 }
125 }
126
127 private ReadWriteLock storageLock = new ReentrantReadWriteLock();
128 private Map<F, HandleImpl<F>> storage;
129
130 @Override
131 public Handle<F> put(F fact) throws ReasoningException {
132 Lock lock = storageLock.writeLock();
133 lock.lock();
134 try {
135 HandleImpl<F> ret = storage.get(fact);
136 if (ret==null) {
137 ret = new HandleImpl<F>(fact);
138 storage.put(fact, ret);
139 }
140 ret.derived.set(false);
141 ret.removed.set(false);
142 if (listener!=null) {
143 listener.onPut(fact, ret);
144 }
145 return ret;
146 } finally {
147 lock.unlock();
148 }
149 }
150
151 @Override
152 public Collection<Derivation<F>> getDerivations(F obj) throws ReasoningException {
153 Lock lock = storageLock.readLock();
154 lock.lock();
155 try {
156 HandleImpl<F> handle = storage.get(obj);
157 if (handle==null) {
158 return Collections.emptyList();
159 }
160 return getDerivations(handle);
161 } finally {
162 lock.unlock();
163 }
164 }
165
166 @Override
167 public Collection<Derivation<F>> getDerivations(Handle<F> handle) throws ReasoningException {
168 if (handle==null) {
169 return Collections.emptyList();
170 }
171 Collection<Derivation<F>> ret = new ArrayList<Derivation<F>>();
172 Set<Derivation<F>> derivations = ((HandleImpl<F>) handle).derivations;
173 ReadWriteLock dLock = ((HandleImpl<F>) handle).derivationsLock;
174 Lock lock = dLock.readLock();
175 lock.lock();
176 try {
177 Iterator<Derivation<F>> dit = derivations.iterator();
178 while (dit.hasNext()) {
179 Derivation<F> next = dit.next();
180 if (next.isValid()) {
181 ret.add(next);
182 // We don't remove invalid derivations to avoid having to use write lock.
183 // } else {
184 // dit.remove();
185 }
186 }
187 } finally {
188 lock.unlock();
189 }
190 return Collections.unmodifiableCollection(ret);
191 }
192
193 @Override
194 public F get(Handle<F> handle) throws ReasoningException {
195 if (handle==null) {
196 return null;
197 }
198 return ((HandleImpl<F>) handle).get();
199 }
200
201 @Override
202 public Collection<F> getObjects() throws ReasoningException {
203 List<F> ret = new ArrayList<F>();
204 Lock lock = storageLock.readLock();
205 lock.lock();
206 try {
207 for (HandleImpl<F> hImpl: storage.values()) {
208 F o = hImpl.get();
209 if (o!=null) {
210 ret.add(o);
211 }
212 }
213 } finally {
214 lock.unlock();
215 }
216 return Collections.unmodifiableCollection(ret);
217 }
218
219 @Override
220 public void remove(F obj, boolean strict) throws ReasoningException {
221 Lock lock = storageLock.writeLock();
222 lock.lock();
223 try {
224 HandleImpl<F> handle = strict ? storage.remove(obj) : storage.get(obj);
225 if (strict) {
226 handle.clear();
227 }
228 if (handle!=null) {
229 remove(handle, strict);
230 }
231 } finally {
232 lock.unlock();
233 }
234 }
235
236 @Override
237 public void remove(Handle<F> handle, boolean strict) throws ReasoningException {
238 if (handle!=null) {
239 HandleImpl<F> hImpl = (HandleImpl<F>) handle;
240 if (strict) {
241 hImpl.removed.set(true);
242 F obj = hImpl.get();
243 if (obj!=null) {
244 Lock lock = storageLock.writeLock();
245 lock.lock();
246 try {
247 storage.remove(obj);
248 } finally {
249 lock.unlock();
250 }
251 if (listener!=null) {
252 listener.onRemove(obj, hImpl);
253 }
254 hImpl.onRemove(executor);
255 }
256 } else {
257 hImpl.removed.set(true); // Temporarily for derivation validation.
258 boolean hasValidDerivation = false;
259 Set<Derivation<F>> derivations = hImpl.derivations;
260 Lock lock = hImpl.derivationsLock.readLock();
261 lock.lock();
262 try {
263 Iterator<Derivation<F>> dit = derivations.iterator();
264 while (dit.hasNext()) {
265 Derivation<F> next = dit.next();
266 if (next.isValid()) {
267 hasValidDerivation = true;
268 break;
269 // We don't remove invalid derivations to avoid having to use write lock.
270 // } else {
271 // dit.remove();
272 }
273 }
274 } finally {
275 lock.unlock();
276 }
277 if (hasValidDerivation) {
278 hImpl.removed.set(false);
279 // This fact is not known to be true by the external world. So its validity is based
280 // on validity of derivations.
281 hImpl.derived.set(true);
282 } else {
283 remove(handle, true);
284 }
285 }
286 }
287 }
288
289 @Override
290 public String getDescription() {
291 return description;
292 }
293
294 @Override
295 public String getName() {
296 return name;
297 }
298
299 @Override
300 public void close() throws ReasoningException {
301 // NOP
302 }
303
304 @Override
305 public void reset() throws ReasoningException {
306 Lock lock = storageLock.writeLock();
307 lock.lock();
308 try {
309 storage.clear();
310 } finally {
311 lock.unlock();
312 }
313
314 synchronized (collections) {
315 Iterator<Reference<Collection<?>>> cit = collections.values().iterator();
316 while (cit.hasNext()) {
317 Reference<Collection<?>> next = cit.next();
318 Collection<?> c = next.get();
319 if (c==null) {
320 cit.remove();
321 } else {
322 if (c instanceof ReadWriteLock) {
323 Lock lck = ((ReadWriteLock) c).writeLock();
324 lck.lock();
325 try {
326 c.clear();
327 } finally {
328 lck.unlock();
329 }
330 } else {
331 synchronized (c) {
332 c.clear();
333 }
334 }
335 }
336 }
337 }
338
339 }
340
341 @Override
342 public void executeRules() throws ReasoningException {
343 throw new UnsupportedOperationException("This method shall not be invoked on knowledge base.");
344 }
345
346 private InferenceListener<F> listener;
347 private ExceptionHandler exceptionHandler;
348
349 @Override
350 public InferenceListener<F> getInferenceListener() throws ReasoningException {
351 return listener;
352 }
353
354 @Override
355 public void setInferenceListener(InferenceListener<F> listener) throws ReasoningException {
356 this.listener = listener;
357 }
358
359 private AtomicInteger duplicateDerivationCounter = new AtomicInteger();
360
361 private class PutDerivedResultImpl implements PutDerivedResult<F> {
362
363 PutDerivedResultImpl(Handle<F> handle, boolean isNew) {
364 super();
365 this.handle = handle;
366 this.isNew = isNew;
367 }
368
369 private boolean isNew;
370 private Handle<F> handle;
371
372 @Override
373 public Handle<F> getHandle() {
374 return handle;
375 }
376
377 @Override
378 public boolean isNew() {
379 return isNew;
380 }
381
382 }
383
384 @Override
385 public PutDerivedResult<F> putConclusion(F conclusion, Object rule, String ruleName, String ruleDescription, Method method, List<Handle<F>> handleList) {
386 Lock lock = storageLock.writeLock();
387 lock.lock();
388
389 try {
390 HandleImpl<F> hImpl = storage.get(conclusion);
391 boolean isNew = false;
392
393 if (hImpl==null) {
394 isNew = true;
395 hImpl = new HandleImpl<F>(conclusion);
396 hImpl.derived.set(true);
397 storage.put(conclusion, hImpl);
398 if (listener!=null) {
399 listener.onPut(conclusion, hImpl);
400 }
401 } else {
402 // Check circular inference
403 for (Handle<F> h: handleList) {
404 if (h.equals(hImpl)) {
405 logger.fine(conclusion + " - discarded, self-inference");
406 return new PutDerivedResultImpl(hImpl, false);
407 }
408
409 try {
410 for (Derivation<F> d: getDerivations(h)) {
411 if (d.isDerivedFrom(conclusion)) {
412 logger.fine(conclusion + " - discarded, inference loop");
413 return new PutDerivedResultImpl(hImpl, false);
414 }
415 }
416 } catch (ReasoningException e) {
417 throw new RuntimeReasoningException(e);
418 }
419 }
420 }
421
422 Derivation<F> derivation = new DerivationImpl<F>(rule, ruleName, ruleDescription, method, handleList, this);
423
424 Lock lck = hImpl.derivationsLock.writeLock();
425 lck.lock();
426 try {
427 if (!hImpl.derivations.add(derivation)) {
428 // Duplicate derivation
429 if (isFine) {
430 Derivation<F> existingDerivation = null;
431 for (Derivation<F> d: hImpl.derivations) {
432 if (d.equals(derivation)) {
433 existingDerivation = d;
434 }
435 }
436 logger.info("Duplicate derivation #"+duplicateDerivationCounter.incrementAndGet()+" of "+conclusion
437 +Constants.LINE_SEPARATOR+" --- New derivation ---"+Constants.LINE_SEPARATOR
438 +derivation
439 +Constants.LINE_SEPARATOR+" --- Existing derivation ---"+Constants.LINE_SEPARATOR
440 +existingDerivation);
441 }
442 }
443 } finally {
444 lck.unlock();
445 }
446 hImpl.removed.set(false);
447 return new PutDerivedResultImpl(hImpl, isNew);
448 } finally {
449 lock.unlock();
450 }
451 }
452
453 @Override
454 public Handle<F> getHandle(Object fact) {
455 Lock lock = storageLock.readLock();
456 lock.lock();
457 try {
458 HandleImpl<F> ret = storage.get(fact);
459 return ret==null || ret.get()==null ? null : ret;
460 } finally {
461 lock.unlock();
462 }
463 }
464
465 /**
466 * Removes invalid entries. Similar to garbage collection.
467 * Can be used with long running sessions with significant
468 * rate of removals.
469 * @throws ReasoningException
470 */
471 @SuppressWarnings("unchecked")
472 public void cleanup() throws ReasoningException {
473 Lock lock = storageLock.writeLock();
474 lock.lock();
475 try {
476 Iterator<Entry<F, HandleImpl<F>>> eit = storage.entrySet().iterator();
477 while (eit.hasNext()) {
478 Entry<F, HandleImpl<F>> entry = eit.next();
479 if (entry.getValue().get()==null) {
480 eit.remove();
481 }
482 }
483 } finally {
484 lock.unlock();
485 }
486
487 synchronized (collections) {
488 Iterator<Reference<Collection<?>>> cit = collections.values().iterator();
489 while (cit.hasNext()) {
490 Reference<Collection<?>> next = cit.next();
491 Collection<?> c = next.get();
492 if (c==null) {
493 cit.remove();
494 } else {
495 if (c instanceof ReadWriteLock) {
496 Lock lck = ((ReadWriteLock) c).writeLock();
497 lck.lock();
498 try {
499 Iterator<?> it = c.iterator();
500 while (it.hasNext()) {
501 Object nxt = it.next();
502 if (nxt==null || (nxt instanceof Handle<?> && get((Handle<F>) nxt)==null)) {
503 it.remove();
504 }
505 }
506 } finally {
507 lck.unlock();
508 }
509 } else {
510 synchronized (c) {
511 Iterator<?> it = c.iterator();
512 while (it.hasNext()) {
513 Object nxt = it.next();
514 if (nxt==null || (nxt instanceof Handle<?> && get((Handle<F>) nxt)==null)) {
515 it.remove();
516 }
517 }
518 }
519 }
520 }
521 }
522 }
523 }
524
525 @Override
526 public boolean contains(Object fact) throws ReasoningException {
527 Lock lock = storageLock.readLock();
528 lock.lock();
529 try {
530 HandleImpl<?> h = storage.get(fact);
531 return h!=null && h.get()!=null;
532 } finally {
533 lock.unlock();
534 }
535 }
536
537 @Override
538 public ExceptionHandler getExceptionHandler() throws ReasoningException {
539 return exceptionHandler;
540 }
541
542 @Override
543 public void setExceptionHandler(ExceptionHandler handler) throws ReasoningException {
544 this.exceptionHandler = handler;
545 }
546
547 @Override
548 public boolean contains(Handle<F> handle) throws ReasoningException {
549 F obj = ((HandleImpl<F>) handle).get();
550 return obj==null ? false : contains(obj);
551 }
552
553 @Override
554 public Collection<Handle<F>> getHandles() throws ReasoningException {
555 List<Handle<F>> ret = new ArrayList<Handle<F>>();
556 Lock lock = storageLock.readLock();
557 lock.lock();
558 try {
559 for (HandleImpl<F> hImpl: storage.values()) {
560 F o = hImpl.get();
561 if (o!=null) {
562 ret.add(hImpl);
563 }
564 }
565 } finally {
566 lock.unlock();
567 }
568 return Collections.unmodifiableCollection(ret);
569 }
570
571 @Override
572 public List<Handle<F>> putAll(List<? extends F> facts) throws ReasoningException {
573 List<Handle<F>> ret = new ArrayList<Handle<F>>();
574 for (F fact: facts) {
575 ret.add(put(fact));
576 }
577 return ret;
578 }
579
580 @SuppressWarnings("unchecked")
581 @Override
582 public Handle<F>[] putAll(F... facts) throws ReasoningException {
583 Handle<F>[] ret = new Handle[facts.length];
584 for (int i=0; i<ret.length; ++i) {
585 ret[i]=put(facts[i]);
586 }
587 return ret;
588 }
589
590 @Override
591 public void updateObject(Handle<F> handle, F fact) throws ReasoningException {
592 Lock lock = storageLock.writeLock();
593 lock.lock();
594 try {
595 remove(handle, true);
596 ((HandleImpl<F>) handle).init(fact);;
597 storage.put(fact, (HandleImpl<F>) handle);
598 if (listener!=null) {
599 listener.onPut(fact, handle);
600 }
601 } finally {
602 lock.unlock();
603 }
604 }
605
606 @Override
607 public Map<Class<F>, Set<Class<F>>> getConclusionMap() {
608 throw new UnsupportedOperationException("Knowledge base doesn't implement this operation");
609 }
610 }