    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    }