Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/booleans/circuit_propagator.h	Lines:	29	29	100.0 %
Date:	2021-08-01	Branches:	52	100	52.0 %


/******************************************************************************
 * Top contributors (to current version):
 *   Morgan Deters, Aina Niemetz, Gereon Kremer
 *
 * This file is part of the cvc5 project.
 *
 * Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
 * in the top-level source directory and their institutional affiliations.
 * All rights reserved.  See the file COPYING in the top-level source
 * directory for licensing information.
 * ****************************************************************************
 *
 * A non-clausal circuit propagator for Boolean simplification.
 */

#include "cvc5_private.h"

#ifndef CVC5__THEORY__BOOLEANS__CIRCUIT_PROPAGATOR_H
#define CVC5__THEORY__BOOLEANS__CIRCUIT_PROPAGATOR_H

#include <memory>
#include <unordered_map>
#include <vector>

#include "context/cdhashmap.h"
#include "context/cdhashset.h"
#include "context/cdo.h"
#include "context/context.h"
#include "expr/node.h"
#include "proof/lazy_proof_chain.h"
#include "proof/trust_node.h"

namespace cvc5 {

class ProofGenerator;
class ProofNode;
class EagerProofGenerator;

namespace theory {
namespace booleans {

/**
 * The main purpose of the CircuitPropagator class is to maintain the
 * state of the circuit for subsequent calls to propagate(), so that
 * the same fact is not output twice, so that the same edge in the
 * circuit isn't propagated twice, etc.
 */
class CircuitPropagator
{
 public:
  /**
   * Value of a particular node
   */
  enum AssignmentStatus
  {
    /** Node is currently unassigned */
    UNASSIGNED = 0,
    /** Node is assigned to true */
    ASSIGNED_TO_TRUE,
    /** Node is assigned to false */
    ASSIGNED_TO_FALSE,
  };

  typedef std::unordered_map<Node, std::vector<Node>> BackEdgesMap;

  /**
   * Construct a new CircuitPropagator.
   */
  CircuitPropagator(bool enableForward = true, bool enableBackward = true);

  /** Get Node assignment in circuit.  Assert-fails if Node is unassigned. */
  bool getAssignment(TNode n) const
  {
    AssignmentMap::iterator i = d_state.find(n);
    Assert(i != d_state.end() && (*i).second != UNASSIGNED);
    return (*i).second == ASSIGNED_TO_TRUE;
  }

  // Use custom context to ensure propagator is reset after use
  void initialize() { d_context.push(); }

  void setNeedsFinish(bool value) { d_needsFinish = value; }

  bool getNeedsFinish() { return d_needsFinish; }

  std::vector<TrustNode>& getLearnedLiterals() { return d_learnedLiterals; }

  /** Finish the computation and pop the internal context */
  void finish();

  /** Assert for propagation */
  void assertTrue(TNode assertion);

  /**
   * Propagate through the asserted circuit propagator. New information
   * discovered by the propagator are put in the substitutions vector used in
   * construction.
   *
   * @return a trust node encapsulating the proof for a conflict as a lemma that
   * proves false, or the null trust node otherwise
   */
  TrustNode propagate() CVC5_WARN_UNUSED_RESULT;

  /**
   * Get the back edges of this circuit.
   */
  const BackEdgesMap& getBackEdges() const { return d_backEdges; }

  /** Invert a set value */
  static inline AssignmentStatus neg(AssignmentStatus value)
  {
    Assert(value != UNASSIGNED);
    if (value == ASSIGNED_TO_TRUE)
      return ASSIGNED_TO_FALSE;
    else
      return ASSIGNED_TO_TRUE;
  }

  /** True iff Node is assigned in circuit (either true or false). */
  bool isAssigned(TNode n) const
  {
    AssignmentMap::const_iterator i = d_state.find(n);
    return i != d_state.end() && ((*i).second != UNASSIGNED);
  }

  /** True iff Node is assigned to the value. */
  bool isAssignedTo(TNode n, bool value) const
  {
    AssignmentMap::const_iterator i = d_state.find(n);
    if (i == d_state.end()) return false;
    if (value && ((*i).second == ASSIGNED_TO_TRUE)) return true;
    if (!value && ((*i).second == ASSIGNED_TO_FALSE)) return true;
    return false;
  }
  /**
   * Set proof node manager, context and parent proof generator.
   *
   * If parent is non-null, then it is responsible for the proofs provided
   * to this class.
   */
  void setProof(ProofNodeManager* pnm,
                context::Context* ctx,
                ProofGenerator* defParent);

 private:
  /** A context-notify object that clears out stale data. */
  template <class T>
  class DataClearer : context::ContextNotifyObj
  {
   public:
    DataClearer(context::Context* context, T& data)
        : context::ContextNotifyObj(context), d_data(data)
    {
    }

   protected:
    void contextNotifyPop() override
    {
      Trace("circuit-prop")
          << "CircuitPropagator::DataClearer: clearing data "
          << "(size was " << d_data.size() << ")" << std::endl;
      d_data.clear();
    }

   private:
    T& d_data;
  }; /* class DataClearer<T> */

  /**
   * Assignment status of each node.
   */
  typedef context::CDHashMap<TNode, AssignmentStatus> AssignmentMap;

  /**
   * Assign Node in circuit with the value and add it to the queue; note
   * conflicts.
   */
  void assignAndEnqueue(TNode n,
                        bool value,
                        std::shared_ptr<ProofNode> proof = nullptr);

  /**
   * Store a conflict for the case that we have derived both n and n.negate()
   * to be true.
   */
  void makeConflict(Node n);

  /**
   * Compute the map from nodes to the nodes that use it.
   */
  void computeBackEdges(TNode node);

  /**
   * Propagate new information forward in circuit to
   * the parents of "in".
   */
  void propagateForward(TNode child, bool assignment);

  /**
   * Propagate new information backward in circuit to
   * the children of "in".
   */
  void propagateBackward(TNode parent, bool assignment);

  /** Are proofs enabled? */
  bool isProofEnabled() const;

  context::Context d_context;

  /** The propagation queue */
  std::vector<TNode> d_propagationQueue;

  /**
   * We have a propagation queue "clearer" object for when the user
   * context pops.  Normally the propagation queue should be empty,
   * but this keeps us safe in case there's still some rubbish around
   * on the queue.
   */
  DataClearer<std::vector<TNode>> d_propagationQueueClearer;

  /** Are we in conflict? */
  context::CDO<TrustNode> d_conflict;

  /** Map of substitutions */
  std::vector<TrustNode> d_learnedLiterals;

  /**
   * Similar data clearer for learned literals.
   */
  DataClearer<std::vector<TrustNode>> d_learnedLiteralClearer;

  /**
   * Back edges from nodes to where they are used.
   */
  BackEdgesMap d_backEdges;

  /**
   * Similar data clearer for back edges.
   */
  DataClearer<BackEdgesMap> d_backEdgesClearer;

  /** Nodes that have been attached already (computed forward edges for) */
  // All the nodes we've visited so far
  context::CDHashSet<Node> d_seen;

  AssignmentMap d_state;

  /** Whether to perform forward propagation */
  const bool d_forwardPropagation;

  /** Whether to perform backward propagation */
  const bool d_backwardPropagation;

  /* Does the current state require a call to finish()? */
  bool d_needsFinish;

  /** Adds a new proof for f, or drops it if we already have a proof */
  void addProof(TNode f, std::shared_ptr<ProofNode> pf);

  /** A pointer to the proof manager */
  ProofNodeManager* d_pnm;
  /** Eager proof generator that actually stores the proofs */
  std::unique_ptr<EagerProofGenerator> d_epg;
  /** Connects the proofs to subproofs internally */
  std::unique_ptr<LazyCDProofChain> d_proofInternal;
  /** Connects the proofs to assumptions externally */
  std::unique_ptr<LazyCDProofChain> d_proofExternal;
}; /* class CircuitPropagator */

}  // namespace booleans
}  // namespace theory
}  // namespace cvc5

#endif /* CVC5__THEORY__BOOLEANS__CIRCUIT_PROPAGATOR_H */


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Morgan Deters, Aina Niemetz, Gereon Kremer
4		*
5		* This file is part of the cvc5 project.
6		*
7		* Copyright (c) 2009-2021 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		* A non-clausal circuit propagator for Boolean simplification.
14		*/
15
16		#include "cvc5_private.h"
17
18		#ifndef CVC5__THEORY__BOOLEANS__CIRCUIT_PROPAGATOR_H
19		#define CVC5__THEORY__BOOLEANS__CIRCUIT_PROPAGATOR_H
20
21		#include <memory>
22		#include <unordered_map>
23		#include <vector>
24
25		#include "context/cdhashmap.h"
26		#include "context/cdhashset.h"
27		#include "context/cdo.h"
28		#include "context/context.h"
29		#include "expr/node.h"
30		#include "proof/lazy_proof_chain.h"
31		#include "proof/trust_node.h"
32
33		namespace cvc5 {
34
35		class ProofGenerator;
36		class ProofNode;
37		class EagerProofGenerator;
38
39		namespace theory {
40		namespace booleans {
41
42		/**
43		* The main purpose of the CircuitPropagator class is to maintain the
44		* state of the circuit for subsequent calls to propagate(), so that
45		* the same fact is not output twice, so that the same edge in the
46		* circuit isn't propagated twice, etc.
47		*/
48	10480	class CircuitPropagator
49		{
50		public:
51		/**
52		* Value of a particular node
53		*/
54		enum AssignmentStatus
55		{
56		/** Node is currently unassigned */
57		UNASSIGNED = 0,
58		/** Node is assigned to true */
59		ASSIGNED_TO_TRUE,
60		/** Node is assigned to false */
61		ASSIGNED_TO_FALSE,
62		};
63
64		typedef std::unordered_map<Node, std::vector<Node>> BackEdgesMap;
65
66		/**
67		* Construct a new CircuitPropagator.
68		*/
69		CircuitPropagator(bool enableForward = true, bool enableBackward = true);
70
71		/** Get Node assignment in circuit. Assert-fails if Node is unassigned. */
72	702013	bool getAssignment(TNode n) const
73		{
74	702013	AssignmentMap::iterator i = d_state.find(n);
75	702013	Assert(i != d_state.end() && (*i).second != UNASSIGNED);
76	702013	return (*i).second == ASSIGNED_TO_TRUE;
77		}
78
79		// Use custom context to ensure propagator is reset after use
80	11009	void initialize() { d_context.push(); }
81
82	22018	void setNeedsFinish(bool value) { d_needsFinish = value; }
83
84	21489	bool getNeedsFinish() { return d_needsFinish; }
85
86	23655	std::vector<TrustNode>& getLearnedLiterals() { return d_learnedLiterals; }
87
88		/** Finish the computation and pop the internal context */
89		void finish();
90
91		/** Assert for propagation */
92		void assertTrue(TNode assertion);
93
94		/**
95		* Propagate through the asserted circuit propagator. New information
96		* discovered by the propagator are put in the substitutions vector used in
97		* construction.
98		*
99		* @return a trust node encapsulating the proof for a conflict as a lemma that
100		* proves false, or the null trust node otherwise
101		*/
102		TrustNode propagate() CVC5_WARN_UNUSED_RESULT;
103
104		/**
105		* Get the back edges of this circuit.
106		*/
107	8	const BackEdgesMap& getBackEdges() const { return d_backEdges; }
108
109		/** Invert a set value */
110		static inline AssignmentStatus neg(AssignmentStatus value)
111		{
112		Assert(value != UNASSIGNED);
113		if (value == ASSIGNED_TO_TRUE)
114		return ASSIGNED_TO_FALSE;
115		else
116		return ASSIGNED_TO_TRUE;
117		}
118
119		/** True iff Node is assigned in circuit (either true or false). */
120	16699	bool isAssigned(TNode n) const
121		{
122	16699	AssignmentMap::const_iterator i = d_state.find(n);
123	16699	return i != d_state.end() && ((*i).second != UNASSIGNED);
124		}
125
126		/** True iff Node is assigned to the value. */
127	21515629	bool isAssignedTo(TNode n, bool value) const
128		{
129	21515629	AssignmentMap::const_iterator i = d_state.find(n);
130	21515629	if (i == d_state.end()) return false;
131	20388779	if (value && ((*i).second == ASSIGNED_TO_TRUE)) return true;
132	838439	if (!value && ((*i).second == ASSIGNED_TO_FALSE)) return true;
133	127970	return false;
134		}
135		/**
136		* Set proof node manager, context and parent proof generator.
137		*
138		* If parent is non-null, then it is responsible for the proofs provided
139		* to this class.
140		*/
141		void setProof(ProofNodeManager* pnm,
142		context::Context* ctx,
143		ProofGenerator* defParent);
144
145		private:
146		/** A context-notify object that clears out stale data. */
147		template <class T>
148	31440	class DataClearer : context::ContextNotifyObj
149		{
150		public:
151	31440	DataClearer(context::Context* context, T& data)
152	31440	: context::ContextNotifyObj(context), d_data(data)
153		{
154	31440	}
155
156		protected:
157	33027	void contextNotifyPop() override
158		{
159	99081	Trace("circuit-prop")
160	33027	<< "CircuitPropagator::DataClearer: clearing data "
161	66054	<< "(size was " << d_data.size() << ")" << std::endl;
162	33027	d_data.clear();
163	33027	}
164
165		private:
166		T& d_data;
167		}; /* class DataClearer<T> */
168
169		/**
170		* Assignment status of each node.
171		*/
172		typedef context::CDHashMap<TNode, AssignmentStatus> AssignmentMap;
173
174		/**
175		* Assign Node in circuit with the value and add it to the queue; note
176		* conflicts.
177		*/
178		void assignAndEnqueue(TNode n,
179		bool value,
180		std::shared_ptr<ProofNode> proof = nullptr);
181
182		/**
183		* Store a conflict for the case that we have derived both n and n.negate()
184		* to be true.
185		*/
186		void makeConflict(Node n);
187
188		/**
189		* Compute the map from nodes to the nodes that use it.
190		*/
191		void computeBackEdges(TNode node);
192
193		/**
194		* Propagate new information forward in circuit to
195		* the parents of "in".
196		*/
197		void propagateForward(TNode child, bool assignment);
198
199		/**
200		* Propagate new information backward in circuit to
201		* the children of "in".
202		*/
203		void propagateBackward(TNode parent, bool assignment);
204
205		/** Are proofs enabled? */
206		bool isProofEnabled() const;
207
208		context::Context d_context;
209
210		/** The propagation queue */
211		std::vector<TNode> d_propagationQueue;
212
213		/**
214		* We have a propagation queue "clearer" object for when the user
215		* context pops. Normally the propagation queue should be empty,
216		* but this keeps us safe in case there's still some rubbish around
217		* on the queue.
218		*/
219		DataClearer<std::vector<TNode>> d_propagationQueueClearer;
220
221		/** Are we in conflict? */
222		context::CDO<TrustNode> d_conflict;
223
224		/** Map of substitutions */
225		std::vector<TrustNode> d_learnedLiterals;
226
227		/**
228		* Similar data clearer for learned literals.
229		*/
230		DataClearer<std::vector<TrustNode>> d_learnedLiteralClearer;
231
232		/**
233		* Back edges from nodes to where they are used.
234		*/
235		BackEdgesMap d_backEdges;
236
237		/**
238		* Similar data clearer for back edges.
239		*/
240		DataClearer<BackEdgesMap> d_backEdgesClearer;
241
242		/** Nodes that have been attached already (computed forward edges for) */
243		// All the nodes we've visited so far
244		context::CDHashSet<Node> d_seen;
245
246		AssignmentMap d_state;
247
248		/** Whether to perform forward propagation */
249		const bool d_forwardPropagation;
250
251		/** Whether to perform backward propagation */
252		const bool d_backwardPropagation;
253
254		/* Does the current state require a call to finish()? */
255		bool d_needsFinish;
256
257		/** Adds a new proof for f, or drops it if we already have a proof */
258		void addProof(TNode f, std::shared_ptr<ProofNode> pf);
259
260		/** A pointer to the proof manager */
261		ProofNodeManager* d_pnm;
262		/** Eager proof generator that actually stores the proofs */
263		std::unique_ptr<EagerProofGenerator> d_epg;
264		/** Connects the proofs to subproofs internally */
265		std::unique_ptr<LazyCDProofChain> d_proofInternal;
266		/** Connects the proofs to assumptions externally */
267		std::unique_ptr<LazyCDProofChain> d_proofExternal;
268		}; /* class CircuitPropagator */
269
270		} // namespace booleans
271		} // namespace theory
272		} // namespace cvc5
273
274		#endif /* CVC5__THEORY__BOOLEANS__CIRCUIT_PROPAGATOR_H */