Branch data     Line data    Source code

       1                 :            : /******************************************************************************
       2                 :            :  * Top contributors (to current version):
       3                 :            :  *   Andrew Reynolds, Morgan Deters, Aina Niemetz
       4                 :            :  *
       5                 :            :  * This file is part of the cvc5 project.
       6                 :            :  *
       7                 :            :  * Copyright (c) 2009-2025 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                 :            :  * Inst match trie class.
      14                 :            :  */
      15                 :            : 
      16                 :            : #include "cvc5_private.h"
      17                 :            : 
      18                 :            : #ifndef CVC5__THEORY__QUANTIFIERS__INST_MATCH_TRIE_H
      19                 :            : #define CVC5__THEORY__QUANTIFIERS__INST_MATCH_TRIE_H
      20                 :            : 
      21                 :            : #include <map>
      22                 :            : 
      23                 :            : #include "context/cdlist.h"
      24                 :            : #include "context/cdo.h"
      25                 :            : #include "expr/node.h"
      26                 :            : #include "smt/env_obj.h"
      27                 :            : 
      28                 :            : namespace cvc5::internal {
      29                 :            : namespace theory {
      30                 :            : namespace quantifiers {
      31                 :            : 
      32                 :            : class QuantifiersState;
      33                 :            : 
      34                 :            : /** trie for InstMatch objects
      35                 :            :  *
      36                 :            :  * This class is used for storing instantiations of a quantified formula q.
      37                 :            :  * It is a trie data structure for which entries can be added and removed.
      38                 :            :  * This class has interfaces for adding instantiations that are either
      39                 :            :  * represented by std::vectors or InstMatch objects (see inst_match.h).
      40                 :            :  */
      41                 :            : class InstMatchTrie
      42                 :            : {
      43                 :            :  public:
      44                 :            :   /** index ordering */
      45                 :            :   class ImtIndexOrder
      46                 :            :   {
      47                 :            :    public:
      48                 :            :     std::vector<unsigned> d_order;
      49                 :            :   };
      50                 :            : 
      51                 :            :  public:
      52                 :     213035 :   InstMatchTrie() {}
      53                 :     213323 :   ~InstMatchTrie() {}
      54                 :            :   /** exists inst match
      55                 :            :    *
      56                 :            :    * This method considers the entry given by m, starting at the given index.
      57                 :            :    * The domain of m is the bound variables of quantified formula q.
      58                 :            :    * It returns true if (the suffix) of m exists in this trie.
      59                 :            :    */
      60                 :            :   bool existsInstMatch(Node q,
      61                 :            :                        const std::vector<Node>& m,
      62                 :            :                        ImtIndexOrder* imtio = nullptr,
      63                 :            :                        unsigned index = 0);
      64                 :            :   /** add inst match
      65                 :            :    *
      66                 :            :    * This method adds (the suffix of) m starting at the given index to this
      67                 :            :    * trie, and returns true if and only if m did not already occur in this trie.
      68                 :            :    * The domain of m is the bound variables of quantified formula q.
      69                 :            :    */
      70                 :            :   bool addInstMatch(Node f,
      71                 :            :                     const std::vector<Node>& m,
      72                 :            :                     ImtIndexOrder* imtio = nullptr,
      73                 :            :                     bool onlyExist = false,
      74                 :            :                     unsigned index = 0);
      75                 :            :   /**
      76                 :            :    * Adds the instantiations for q into insts.
      77                 :            :    */
      78                 :            :   void getInstantiations(Node q, std::vector<std::vector<Node>>& insts) const;
      79                 :            : 
      80                 :            :   /** clear the data of this class */
      81                 :            :   void clear();
      82                 :            :   /** print this class */
      83                 :            :   void print(std::ostream& out, Node q) const;
      84                 :            :   /** the data */
      85                 :            :   std::map<Node, InstMatchTrie> d_data;
      86                 :            : 
      87                 :            :  private:
      88                 :            :   /** Helper for getInstantiations.*/
      89                 :            :   void getInstantiations(Node q,
      90                 :            :                          std::vector<std::vector<Node>>& insts,
      91                 :            :                          std::vector<Node>& terms) const;
      92                 :            :   /** helper for print
      93                 :            :    * terms accumulates the path we are on in the trie.
      94                 :            :    */
      95                 :            :   void print(std::ostream& out, Node q, std::vector<TNode>& terms) const;
      96                 :            : };
      97                 :            : 
      98                 :            : /** trie for InstMatch objects
      99                 :            :  *
     100                 :            :  * This is a context-dependent version of the above class.
     101                 :            :  */
     102                 :            : class CDInstMatchTrie
     103                 :            : {
     104                 :            :  public:
     105                 :      10335 :   CDInstMatchTrie(context::Context* c) : d_valid(c, false) {}
     106                 :            :   ~CDInstMatchTrie();
     107                 :            : 
     108                 :            :   /** exists inst match
     109                 :            :    *
     110                 :            :    * This method considers the entry given by m, starting at the given index.
     111                 :            :    * The domain of m is the bound variables of quantified formula q.
     112                 :            :    * It returns true if (the suffix) of m exists in this trie.
     113                 :            :    * It additionally takes a context c, for which the entry is valid in.
     114                 :            :    */
     115                 :            :   bool existsInstMatch(context::Context* context,
     116                 :            :                        Node q,
     117                 :            :                        const std::vector<Node>& m,
     118                 :            :                        unsigned index = 0);
     119                 :            :   /** add inst match
     120                 :            :    *
     121                 :            :    * This method adds (the suffix of) m starting at the given index to this
     122                 :            :    * trie, and returns true if and only if m did not already occur in this trie.
     123                 :            :    * The domain of m is the bound variables of quantified formula q.
     124                 :            :    * It additionally takes a context c, for which the entry is valid in.
     125                 :            :    */
     126                 :            :   bool addInstMatch(context::Context* context,
     127                 :            :                     Node q,
     128                 :            :                     const std::vector<Node>& m,
     129                 :            :                     unsigned index = 0,
     130                 :            :                     bool onlyExist = false);
     131                 :            :   /**
     132                 :            :    * Adds the instantiations for q into insts.
     133                 :            :    */
     134                 :            :   void getInstantiations(Node q, std::vector<std::vector<Node>>& insts) const;
     135                 :            : 
     136                 :            :   /** print this class */
     137                 :            :   void print(std::ostream& out, Node q) const;
     138                 :            : 
     139                 :            :  private:
     140                 :            :   /** Helper for getInstantiations.*/
     141                 :            :   void getInstantiations(Node q,
     142                 :            :                          std::vector<std::vector<Node>>& insts,
     143                 :            :                          std::vector<Node>& terms) const;
     144                 :            :   /** helper for print
     145                 :            :    * terms accumulates the path we are on in the trie.
     146                 :            :    */
     147                 :            :   void print(std::ostream& out, Node q, std::vector<TNode>& terms) const;
     148                 :            :   /** the data */
     149                 :            :   std::map<Node, CDInstMatchTrie*> d_data;
     150                 :            :   /** is valid */
     151                 :            :   context::CDO<bool> d_valid;
     152                 :            : };
     153                 :            : 
     154                 :            : /** inst match trie ordered
     155                 :            :  *
     156                 :            :  * This is an ordered version of the context-independent instantiation match
     157                 :            :  * trie. It stores a variable order and a base InstMatchTrie.
     158                 :            :  */
     159                 :            : class InstMatchTrieOrdered
     160                 :            : {
     161                 :            :  public:
     162                 :        190 :   InstMatchTrieOrdered(InstMatchTrie::ImtIndexOrder* imtio) : d_imtio(imtio) {}
     163                 :        478 :   ~InstMatchTrieOrdered() {}
     164                 :            :   /** get the ordering */
     165                 :       8051 :   InstMatchTrie::ImtIndexOrder* getOrdering() { return d_imtio; }
     166                 :            :   /** get the trie data */
     167                 :       5706 :   InstMatchTrie* getTrie() { return &d_imt; }
     168                 :            :   /** add match m for quantified formula q
     169                 :            :    *
     170                 :            :    * This method returns true if the match m was not previously added to this
     171                 :            :    * class.
     172                 :            :    */
     173                 :            :   bool addInstMatch(Node q, const std::vector<Node>& m);
     174                 :            :   /** returns true if this trie contains m
     175                 :            :    *
     176                 :            :    * This method returns true if the match m exists in this
     177                 :            :    * class.
     178                 :            :    */
     179                 :            :   bool existsInstMatch(Node q, const std::vector<Node>& m);
     180                 :            : 
     181                 :            :  private:
     182                 :            :   /** the ordering */
     183                 :            :   InstMatchTrie::ImtIndexOrder* d_imtio;
     184                 :            :   /** the data of this class */
     185                 :            :   InstMatchTrie d_imt;
     186                 :            : };
     187                 :            : 
     188                 :            : }  // namespace quantifiers
     189                 :            : }  // namespace theory
     190                 :            : }  // namespace cvc5::internal
     191                 :            : 
     192                 :            : #endif /* CVC5__THEORY__QUANTIFIERS__INST_MATCH_TRIE_H */