Branch data     Line data    Source code

       1                 :            : /******************************************************************************
       2                 :            :  * Top contributors (to current version):
       3                 :            :  *   Morgan Deters, Clark Barrett, Andres Noetzli
       4                 :            :  *
       5                 :            :  * This file is part of the cvc5 project.
       6                 :            :  *
       7                 :            :  * Copyright (c) 2009-2024 by the authors listed in the file AUTHORS
       8                 :            :  * in the top-level source directory and their institutional affiliations.
       9                 :            :  * All rights reserved.  See the file COPYING in the top-level source
      10                 :            :  * directory for licensing information.
      11                 :            :  * ****************************************************************************
      12                 :            :  *
      13                 :            :  * Contains additional classes to store context dependent information
      14                 :            :  * for each term of type array.
      15                 :            :  */
      16                 :            : 
      17                 :            : #include "cvc5_private.h"
      18                 :            : 
      19                 :            : #ifndef CVC5__THEORY__ARRAYS__ARRAY_INFO_H
      20                 :            : #define CVC5__THEORY__ARRAYS__ARRAY_INFO_H
      21                 :            : 
      22                 :            : #include <tuple>
      23                 :            : #include <unordered_map>
      24                 :            : 
      25                 :            : #include "context/cdlist.h"
      26                 :            : #include "context/cdo.h"
      27                 :            : #include "expr/node.h"
      28                 :            : #include "util/statistics_stats.h"
      29                 :            : 
      30                 :            : namespace cvc5::internal {
      31                 :            : namespace theory {
      32                 :            : namespace arrays {
      33                 :            : 
      34                 :            : typedef context::CDList<TNode> CTNodeList;
      35                 :            : using RowLemmaType = std::tuple<TNode, TNode, TNode, TNode>;
      36                 :            : 
      37                 :            : struct RowLemmaTypeHashFunction {
      38                 :     149642 :   size_t operator()(const RowLemmaType& q) const {
      39                 :     299284 :     TNode n1, n2, n3, n4;
      40                 :     149642 :     std::tie(n1, n2, n3, n4) = q;
      41                 :     149642 :     return (size_t) (n1.getId()*0x9e3779b9 + n2.getId()*0x30000059 +
      42                 :     299284 :         n3.getId()*0x60000005 + n4.getId()*0x07FFFFFF);
      43                 :            : 
      44                 :            :   }
      45                 :            : };/* struct RowLemmaTypeHashFunction */
      46                 :            : 
      47                 :            : void printList (CTNodeList* list);
      48                 :            : 
      49                 :            : bool inList(const CTNodeList* l, const TNode el);
      50                 :            : 
      51                 :            : /**
      52                 :            :  * Small class encapsulating the information
      53                 :            :  * in the map. It's a class and not a struct to
      54                 :            :  * call the destructor.
      55                 :            :  */
      56                 :            : 
      57                 :            : class Info {
      58                 :            : public:
      59                 :            :  context::CDO<bool> isNonLinear;
      60                 :            :  context::CDO<bool> rIntro1Applied;
      61                 :            :  context::CDO<TNode> modelRep;
      62                 :            :  context::CDO<TNode> constArr;
      63                 :            :  context::CDO<TNode> weakEquivPointer;
      64                 :            :  context::CDO<TNode> weakEquivIndex;
      65                 :            :  context::CDO<TNode> weakEquivSecondary;
      66                 :            :  context::CDO<TNode> weakEquivSecondaryReason;
      67                 :            :  CTNodeList* indices;
      68                 :            :  CTNodeList* stores;
      69                 :            :  CTNodeList* in_stores;
      70                 :            : 
      71                 :            :  Info(context::Context* c);
      72                 :            :  ~Info();
      73                 :            : 
      74                 :            :  /**
      75                 :            :   * prints the information
      76                 :            :   */
      77                 :        187 :  void print() const
      78                 :            :  {
      79 [ +  - ][ +  - ]:        374 :    Assert(indices != NULL && stores != NULL && in_stores != NULL);
         [ +  - ][ -  + ]
                 [ -  - ]
      80         [ +  - ]:        187 :    Trace("arrays-info") << "  indices   ";
      81                 :        187 :    printList(indices);
      82         [ +  - ]:        187 :    Trace("arrays-info") << "  stores ";
      83                 :        187 :    printList(stores);
      84         [ +  - ]:        187 :    Trace("arrays-info") << "  in_stores ";
      85                 :        187 :    printList(in_stores);
      86                 :        187 :  }
      87                 :            : };/* class Info */
      88                 :            : 
      89                 :            : typedef std::unordered_map<Node, Info*> CNodeInfoMap;
      90                 :            : 
      91                 :            : /**
      92                 :            :  * Class keeping track of the following information for canonical
      93                 :            :  * representatives of type array [a] :
      94                 :            :  *    indices at which it is being read (all i for which there is a
      95                 :            :  *            term of the form SELECT a i)
      96                 :            :  *    all store terms in the congruence class
      97                 :            :  *    stores in which it appears (terms of the form STORE a _ _ )
      98                 :            :  *
      99                 :            :  */
     100                 :            : class ArrayInfo {
     101                 :            : private:
     102                 :            :  context::Context* ct;
     103                 :            :  CNodeInfoMap info_map;
     104                 :            : 
     105                 :            :  CTNodeList* emptyList;
     106                 :            : 
     107                 :            :  /* == STATISTICS == */
     108                 :            : 
     109                 :            :  /** time spent in preregisterTerm() */
     110                 :            :  TimerStat d_mergeInfoTimer;
     111                 :            :  AverageStat d_avgIndexListLength;
     112                 :            :  AverageStat d_avgStoresListLength;
     113                 :            :  AverageStat d_avgInStoresListLength;
     114                 :            :  IntStat d_listsCount;
     115                 :            :  IntStat d_callsMergeInfo;
     116                 :            :  IntStat d_maxList;
     117                 :            :  SizeStat<CNodeInfoMap> d_tableSize;
     118                 :            : 
     119                 :            :  /**
     120                 :            :   * checks if a certain element is in the list l
     121                 :            :   * FIXME: better way to check for duplicates?
     122                 :            :   */
     123                 :            : 
     124                 :            :  /**
     125                 :            :   * helper method that merges two lists into the first
     126                 :            :   * without adding duplicates
     127                 :            :   */
     128                 :            :  void mergeLists(CTNodeList* la, const CTNodeList* lb) const;
     129                 :            : 
     130                 :            : public:
     131                 :            :   const Info* emptyInfo;
     132                 :            : 
     133                 :            :   ArrayInfo(StatisticsRegistry& sr,
     134                 :            :             context::Context* c,
     135                 :            :             std::string statisticsPrefix = "");
     136                 :            : 
     137                 :            :   ~ArrayInfo();
     138                 :            : 
     139                 :            :   /**
     140                 :            :    * adds the node a to the map if it does not exist
     141                 :            :    * and it initializes the info. checks for duplicate i's
     142                 :            :    */
     143                 :            :   void addIndex(const Node a, const TNode i);
     144                 :            :   void addStore(const Node a, const TNode st);
     145                 :            :   void addInStore(const TNode a, const TNode st);
     146                 :            : 
     147                 :            :   void setNonLinear(const TNode a);
     148                 :            :   void setRIntro1Applied(const TNode a);
     149                 :            :   void setModelRep(const TNode a, const TNode rep);
     150                 :            : 
     151                 :            :   void setConstArr(const TNode a, const TNode constArr);
     152                 :            :   void setWeakEquivPointer(const TNode a, const TNode pointer);
     153                 :            :   void setWeakEquivIndex(const TNode a, const TNode index);
     154                 :            :   void setWeakEquivSecondary(const TNode a, const TNode secondary);
     155                 :            :   void setWeakEquivSecondaryReason(const TNode a, const TNode reason);
     156                 :            :   /**
     157                 :            :    * Returns the information associated with TNode a
     158                 :            :    */
     159                 :            : 
     160                 :            :   const Info* getInfo(const TNode a) const;
     161                 :            : 
     162                 :            :   const bool isNonLinear(const TNode a) const;
     163                 :            : 
     164                 :            :   const bool rIntro1Applied(const TNode a) const;
     165                 :            : 
     166                 :            :   const TNode getModelRep(const TNode a) const;
     167                 :            : 
     168                 :            :   const TNode getConstArr(const TNode a) const;
     169                 :            :   const TNode getWeakEquivPointer(const TNode a) const;
     170                 :            :   const TNode getWeakEquivIndex(const TNode a) const;
     171                 :            :   const TNode getWeakEquivSecondary(const TNode a) const;
     172                 :            :   const TNode getWeakEquivSecondaryReason(const TNode a) const;
     173                 :            : 
     174                 :            :   const CTNodeList* getIndices(const TNode a) const;
     175                 :            : 
     176                 :            :   const CTNodeList* getStores(const TNode a) const;
     177                 :            : 
     178                 :            :   const CTNodeList* getInStores(const TNode a) const;
     179                 :            : 
     180                 :            :   /**
     181                 :            :    * merges the information of  nodes a and b
     182                 :            :    * the nodes do not have to actually be in the map.
     183                 :            :    * pre-condition
     184                 :            :    *  a should be the canonical representative of b
     185                 :            :    */
     186                 :            :   void mergeInfo(const TNode a, const TNode b);
     187                 :            : };/* class ArrayInfo */
     188                 :            : 
     189                 :            : }  // namespace arrays
     190                 :            : }  // namespace theory
     191                 :            : }  // namespace cvc5::internal
     192                 :            : 
     193                 :            : #endif /* CVC5__THEORY__ARRAYS__ARRAY_INFO_H */