Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/theory/booleans/circuit_propagator.h	Lines:	29	29	100.0 %
Date:	2021-05-24	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/lazy_proof_chain.h"
#include "expr/node.h"
#include "theory/trust_node.h"

namespace cvc5 {

class ProofGenerator;
class ProofNode;

namespace theory {

class EagerProofGenerator;

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