include/dlvhex2/LiberalSafetyChecker.h

Go to the documentation of this file.

/* dlvhex -- Answer-Set Programming with external interfaces.
 * Copyright (C) 2005-2007 Roman Schindlauer
 * Copyright (C) 2006-2015 Thomas Krennwallner
 * Copyright (C) 2009-2016 Peter Schüller
 * Copyright (C) 2011-2016 Christoph Redl
 * Copyright (C) 2015-2016 Tobias Kaminski
 * Copyright (C) 2015-2016 Antonius Weinzierl
 *
 * This file is part of dlvhex.
 *
 * dlvhex is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 2.1 of
 * the License, or (at your option) any later version.
 *
 * dlvhex is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with dlvhex; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
 * 02110-1301 USA.
 */

#ifndef LIBERALSAFETYCHECKER_H_
#define LIBERALSAFETYCHECKER_H_

#include "dlvhex2/PlatformDefinitions.h"
#include "dlvhex2/fwd.h"
#include "dlvhex2/Logger.h"
#include "dlvhex2/ID.h"

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/foreach.hpp>
#include <boost/intrusive/unordered_set.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/hashed_index.hpp>

DLVHEX_NAMESPACE_BEGIN

class LiberalSafetyChecker;

/*
 * Base class for safety plugins which may integrate application-specific safety criteria.
 */
class DLVHEX_EXPORT LiberalSafetyPlugin
{
    protected:
        LiberalSafetyChecker& lsc;

    public:
        LiberalSafetyPlugin(LiberalSafetyChecker& lsc) : lsc(lsc){}

        virtual void run() = 0;

        typedef boost::shared_ptr<LiberalSafetyPlugin> Ptr;
};
typedef LiberalSafetyPlugin::Ptr LiberalSafetyPluginPtr;

/*
 * Factory for safety plugins.
 */
class DLVHEX_EXPORT LiberalSafetyPluginFactory
{
    public:
        virtual LiberalSafetyPluginPtr create(LiberalSafetyChecker& lsc) = 0;
        typedef boost::shared_ptr<LiberalSafetyPluginFactory> Ptr;
};
typedef LiberalSafetyPluginFactory::Ptr LiberalSafetyPluginFactoryPtr;

class DLVHEX_EXPORT LiberalSafetyChecker
{
    public:
        struct Attribute : private ostream_printable<Attribute>
        {
            enum Type
            {
                Ordinary,
                External
            };
            RegistryPtr reg;
            Type type;
            ID eatomID;
            ID predicate;
            std::vector<ID> inputList;
            ID ruleID;
            bool input;
            int argIndex;

            bool operator==(const Attribute& at2) const;
            bool operator<(const Attribute& at2) const;
            std::ostream& print(std::ostream& o) const;
        };

        typedef boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, Attribute > Graph;
        typedef boost::graph_traits<Graph> Traits;

        typedef Graph::vertex_descriptor Node;
        typedef Graph::edge_descriptor Dependency;
        typedef Traits::vertex_iterator NodeIterator;
        typedef Traits::edge_iterator DependencyIterator;
        typedef Traits::out_edge_iterator PredecessorIterator;
        typedef Traits::in_edge_iterator SuccessorIterator;

                                 // stores rule ID and variable ID
        typedef std::pair<ID, ID> VariableLocation;
                                 // stores rule ID and atom ID
        typedef std::pair<ID, ID> AtomLocation;

        RegistryPtr reg;
        const std::vector<ID>& idb;

    private:
        Graph ag;
        boost::unordered_map<ID, std::vector<Attribute> > attributesOfPredicate;
        struct NodeInfoTag {};
        struct NodeMappingInfo
        {
            Attribute at;
            Node node;
            NodeMappingInfo(Attribute at, Node node): at(at), node(node) {}
        };
        typedef boost::multi_index_container<
            NodeMappingInfo,
            boost::multi_index::indexed_by<
            boost::multi_index::hashed_unique<
            boost::multi_index::tag<NodeInfoTag>,
            BOOST_MULTI_INDEX_MEMBER(NodeMappingInfo,Attribute,at)
            >
            >
            > NodeMapping;
        NodeMapping nm;
        typedef NodeMapping::index<NodeInfoTag>::type NodeNodeInfoIndex;
        std::vector<std::vector<Attribute> > depSCC;

        // some indices
        typedef std::pair<std::set<VariableLocation>, boost::unordered_set<Attribute> > SafetyPreconditions;

        boost::unordered_map<Attribute, SafetyPreconditions> safetyPreconditions;

        boost::unordered_map<VariableLocation, boost::unordered_set<Attribute> > attributesSafeByVariable;
        boost::unordered_map<Attribute, boost::unordered_set<Attribute> > attributesSafeByAttribute;

        boost::unordered_map<Attribute, std::set<AtomLocation> > attributeOccursIn;
        boost::unordered_map<VariableLocation, std::set<AtomLocation> > variableOccursIn;

        // output
        boost::unordered_map<ID, int> predicateArity;
        std::set<Node> cyclicAttributes;
        boost::unordered_set<VariableLocation> boundedVariables;
        boost::unordered_set<Attribute> domainExpansionSafeAttributes;
        boost::unordered_set<IDAddress> necessaryExternalAtoms;
        boost::unordered_set<std::pair<ID, VariableLocation> > boundedByExternals;

    public:
        Attribute getAttribute(ID eatomID, ID predicate, std::vector<ID> inputList, ID ruleID, bool inputAttribute, int argumentIndex);
        Attribute getAttribute(ID predicate, int argumentIndex);

    private:
        Node getNode(Attribute at);

        // helper
        bool hasInformationFlow(boost::unordered_map<ID, boost::unordered_set<ID> >& builtinflow, ID from, ID to);
        bool isNewlySafe(Attribute at);

    public:
        // trigger functions
        void addExternallyBoundedVariable(ID extAtom, VariableLocation vl);
        void addBoundedVariable(VariableLocation vl);
        void addDomainExpansionSafeAttribute(Attribute at);

        const std::vector<ID>& getIdb();
        const Graph& getAttributeGraph();
        const std::vector<std::vector<Attribute> >& getDepSCC();
        const boost::unordered_set<Attribute>& getDomainExpansionSafeAttributes();
        const boost::unordered_set<VariableLocation>& getBoundedVariables();
        void getReachableAttributes(Attribute start, std::set<Node>& output);
        int getPredicateArity(ID predicate) const;

    private:
        // initialization
        void computeBuiltinInformationFlow(const Rule& rule, boost::unordered_map<ID, boost::unordered_set<ID> >& builtinflow);

        void createDependencyGraph();
        void createPreconditionsAndLocationIndices();
        void computeCyclicAttributes();

        // computation
        void ensureOrdinarySafety();

        void computeDomainExpansionSafety();

        std::vector<LiberalSafetyPluginPtr> safetyPlugins;
    public:
        LiberalSafetyChecker(RegistryPtr reg, const std::vector<ID>& idb, std::vector<LiberalSafetyPluginFactoryPtr> customSafetyPlugins);

        bool isDomainExpansionSafe() const;
        bool isExternalAtomNecessaryForDomainExpansionSafety(ID eatomID) const;

        virtual void writeGraphViz(std::ostream& o, bool verbose) const;
};

DLVHEX_EXPORT std::size_t hash_value(const LiberalSafetyChecker::Attribute& at);
DLVHEX_EXPORT std::size_t hash_value(const LiberalSafetyChecker::VariableLocation& vl);

typedef boost::shared_ptr<LiberalSafetyChecker> LiberalSafetyCheckerPtr;
typedef boost::shared_ptr<const LiberalSafetyChecker> LiberalSafetyCheckerConstPtr;

DLVHEX_NAMESPACE_END
#endif

// vim:expandtab:ts=4:sw=4:
// mode: C++
// End: