Line data Source code
1 : // Author(s): Jan Friso Groote, Maurice Laveaux, Wieger Wesselink.
2 : // Copyright: see the accompanying file COPYING or copy at
3 : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4 : //
5 : // Distributed under the Boost Software License, Version 1.0.
6 : // (See accompanying file LICENSE_1_0.txt or copy at
7 : // http://www.boost.org/LICENSE_1_0.txt)
8 : //
9 :
10 : #ifndef MCRL2_ATERMPP_ATERM_H
11 : #define MCRL2_ATERMPP_ATERM_H
12 :
13 : #include <algorithm>
14 : #include <assert.h>
15 : #include <sstream>
16 : #include "mcrl2/atermpp/detail/aterm.h"
17 : #include "mcrl2/atermpp/type_traits.h"
18 :
19 : /// \brief The main namespace for the aterm++ library.
20 : namespace atermpp
21 : {
22 :
23 : typedef void(*term_callback)(const aterm&);
24 :
25 : extern void add_deletion_hook(const function_symbol&, term_callback);
26 :
27 : // Forward declaration
28 : namespace detail
29 : {
30 : class thread_aterm_pool;
31 : }
32 :
33 : /// \brief An unprotected term does not change the reference count of the
34 : /// shared term when it is copied or moved.
35 : class unprotected_aterm
36 : {
37 : friend detail::_aterm* detail::address(const unprotected_aterm& t);
38 :
39 : protected:
40 : const detail::_aterm* m_term;
41 :
42 : public:
43 :
44 : /// \brief Default constuctor.
45 10813437739 : unprotected_aterm() noexcept
46 10813437739 : : m_term(nullptr)
47 10813437739 : {}
48 :
49 : /// \brief Constructor.
50 : /// \param term The term from which the new term is constructed.
51 11402276468 : unprotected_aterm(const detail::_aterm* term) noexcept
52 11402276468 : : m_term(term)
53 11402276468 : {}
54 :
55 : /// \brief Dynamic check whether the term is an aterm_appl.
56 : /// \return True iff this term is an term_appl.
57 : /// \details This function has constant complexity.
58 : /// It is defined as !type_is_int() && !type_is_list().
59 19641731626 : bool type_is_appl() const noexcept
60 : {
61 19641731626 : return !type_is_int() && !type_is_list();
62 : }
63 :
64 : /// \brief Dynamic check whether the term is an aterm_int.
65 : /// \return True iff this term has internal structure of an aterm_int.
66 : /// \details This function has constant complexity.
67 20183089263 : bool type_is_int() const noexcept
68 : {
69 20183089263 : const function_symbol& f=m_term->function();
70 20183089263 : return f == detail::g_as_int;
71 : }
72 :
73 : /// \brief Dynamic check whether the term is an aterm_list.
74 : /// \returns True iff this term has the structure of an term_list
75 : /// \details This function has constant complexity.
76 20945663357 : bool type_is_list() const noexcept
77 : {
78 20945663357 : const function_symbol& f=m_term->function();
79 20945663357 : return f == detail::g_as_list || f == detail::g_as_empty_list;
80 : }
81 :
82 : /// \brief Comparison operator.
83 : /// \details Terms are stored in a maximally shared way. This
84 : /// means that this equality operator can be calculated
85 : /// in constant time.
86 : /// \return true iff t is equal to the current term.
87 3304784997 : bool operator ==(const unprotected_aterm& t) const
88 : {
89 3304784997 : return m_term == t.m_term;
90 : }
91 :
92 : /// \brief Inequality operator on two unprotected aterms.
93 : /// \details See note at the == operator. This operator requires constant time.
94 : /// \param t A term to which the current term is compared.
95 : /// \return false iff t is equal to the current term.
96 10760115200 : bool operator !=(const unprotected_aterm& t) const
97 : {
98 10760115200 : return m_term!=t.m_term;
99 : }
100 :
101 : /// \brief Comparison operator for two unprotected aterms.
102 : /// \details This operator requires constant time. It compares
103 : /// the addresses where terms are stored. That means
104 : /// that the outcome of this operator is only stable
105 : /// as long as aterms are not garbage collected.
106 : /// \param t A term to which the current term is compared.
107 : /// \return True iff the current term is smaller than the argument.
108 292025518 : bool operator <(const unprotected_aterm& t) const
109 : {
110 292025518 : return m_term<t.m_term;
111 : }
112 :
113 : /// \brief Comparison operator for two unprotected aterms.
114 : /// \details This operator requires constant time. See note at the operator <.
115 : /// \param t A term to which the current term is compared.
116 : /// \return True iff the current term is larger than the argument.
117 17881 : bool operator >(const unprotected_aterm& t) const
118 : {
119 17881 : return m_term>t.m_term;
120 : }
121 :
122 : /// \brief Comparison operator for two unprotected aterms.
123 : /// \details This operator requires constant time. See note at the operator <.
124 : /// \param t A term to which the current term is compared.
125 : /// \return True iff the current term is smaller or equal than the argument.
126 5 : bool operator <=(const unprotected_aterm& t) const
127 : {
128 5 : return m_term<=t.m_term;
129 : }
130 :
131 : /// \brief Comparison operator for two unprotected aterms.
132 : /// \details This operator requires constant time. See note at the operator <.
133 : /// \param t A term to which the current term is compared.
134 : /// \return True iff the current term is larger or equalthan the argument.
135 : bool operator >=(const unprotected_aterm& t) const
136 : {
137 : return m_term>=t.m_term;
138 : }
139 :
140 : /// \brief Returns true if this term is not equal to the term assigned by
141 : /// the default constructor of aterms, term_appl<T>'s and aterm_int.
142 : /// \details The default constructor of a term_list<T> is the empty list, on which
143 : /// the operator defined yields true. This operation is more efficient
144 : /// than comparing the current term with an aterm(), term_appl<T>() or an
145 : /// aterm_int().
146 : /// \return A boolean indicating whether this term equals the default constructor.
147 56223663 : bool defined() const
148 : {
149 56223663 : return m_term != nullptr;
150 : }
151 :
152 : /// \brief Swaps this term with its argument.
153 : /// \details This operation is more efficient than exchanging terms by an assignment,
154 : /// as swapping does not require to change the protection of terms.
155 : /// \param t The term with which this term is swapped.
156 1714 : void swap(unprotected_aterm& t) noexcept
157 : {
158 1714 : std::swap(m_term, t.m_term);
159 1714 : }
160 :
161 : /// \brief Yields the function symbol in an aterm.
162 : /// \returns The function symbol of the term, which can also be an AS_EMPTY_LIST,
163 : /// AS_INT and AS_LIST.
164 : /// \details This is for internal use only.
165 222197885 : const function_symbol& function() const
166 : {
167 222197885 : return m_term->function();
168 : }
169 : };
170 :
171 : /// \brief The aterm base class that provides protection of the underlying shared terms.
172 : /// \details Terms are protected using one of the following two invariants:
173 : /// (1) A term that can be accessed is a subterm of a term with a reference count
174 : /// larger than 0 (when reference counting is used). Or,
175 : /// (2) A term that can be accessed if it is a subterm of a term that occurs at
176 : /// an address which exist in the protection set of a process, or which sits
177 : /// in an atermpp container, which automatically is a container protection set.
178 : /// Furthermore, every address in a protection set contains a valid term.
179 : /// During garbage collection or rehashing, this situation is stable in the sense
180 : /// that all terms that are protected remain protected until the end of the
181 : /// garbage collection or rehashing phase by the same address or term. This means
182 : /// that during garbage collection no terms can be deleted, for instance in an
183 : /// assignment, or in a destruct.
184 : //
185 : class aterm : public unprotected_aterm
186 : {
187 : public:
188 :
189 : /// \brief Default constructor.
190 : aterm() noexcept;
191 :
192 : /// \brief Standard destructor.
193 : ~aterm() noexcept;
194 :
195 : /// \brief Constructor based on an internal term data structure. This is not for public use.
196 : /// \details Takes ownership of the passed underlying term.
197 : /// \param t A pointer to an internal aterm data structure.
198 : /// \todo Should be protected, but this cannot yet be done due to a problem
199 : /// in the compiling rewriter.
200 : explicit aterm(const detail::_aterm *t) noexcept;
201 :
202 : /// \brief Copy constructor.
203 : /// \param other The aterm that is copied.
204 : /// \details This class has a non-trivial destructor so explicitly define the copy and move operators.
205 : aterm(const aterm& other) noexcept;
206 :
207 : /// \brief Move constructor.
208 : /// \param other The aterm that is moved into the new term. This term may have changed after this operation.
209 : /// \details This operation does not employ increments and decrements of reference counts and is therefore more
210 : /// efficient than the standard copy construct.
211 : aterm(aterm&& other) noexcept;
212 :
213 : /// \brief Assignment operator.
214 : /// \param other The aterm that will be assigned.
215 : /// \return A reference to the assigned term.
216 : aterm& operator=(const aterm& other) noexcept;
217 :
218 : /// \brief Assignment operator, to be used if busy and forbidden flags are explicitly available.
219 : // \detail This can be used as an optimisation, because it avoids getting access to thread local variables,
220 : // which is as it stands relatively expensive. The effect is equal to the assignment operator =.
221 : /// \param other The aterm that will be assigned.
222 : aterm& assign(const aterm& other,
223 : detail::thread_aterm_pool& pool) noexcept;
224 :
225 : /// \brief Assignment operator, to be used when the busy flags do not need to be set.
226 : /// \details This is only safe in the parallel context when the busy flag is already
227 : /// known to be set. This is also checked by an assert. This can be used for
228 : /// instance in a lambda function that is passed in a make_.... function, as
229 : /// this unprotected assign will only be called when a term is constructed.
230 : /// \param other The aterm that will be assigned.
231 : template <bool CHECK_BUSY_FLAG=true>
232 : aterm& unprotected_assign(const aterm& other) noexcept;
233 :
234 : /// \brief Move assignment operator.
235 : /// \param other The aterm that will be assigned.
236 : /// \return A reference to the assigned term.
237 : aterm& operator=(aterm&& other) noexcept;
238 : };
239 :
240 : template <class Term1, class Term2>
241 : struct is_convertible : public
242 : std::conditional<std::is_base_of<aterm, Term1>::value &&
243 : std::is_base_of<aterm, Term2>::value && (
244 : std::is_convertible<Term1, Term2>::value ||
245 : std::is_convertible<Term2, Term1>::value),
246 : std::true_type, std::false_type>::type
247 : { };
248 :
249 : /// \brief A cheap cast from one aterm based type to another
250 : /// When casting one aterm based type into another, generally a new aterm is constructed,
251 : /// and the old one is destroyed. This can cause undesired overhead, for instance due to
252 : /// increasing and decreasing of reference counts. This cast changes the type, without
253 : /// changing the aterm itself. It can only be used if Base and Derived inherit from aterm,
254 : /// and contain no additional information than a
255 : /// single aterm.
256 : /// \param t A term of a type inheriting from an aterm.
257 : /// \return A term of type const Derived&.
258 : template <class Derived, class Base>
259 10650928157 : const Derived& down_cast(const Base& t,
260 : typename std::enable_if<is_convertible<Base, Derived>::value &&
261 : !std::is_base_of<Derived, Base>::value>::type* = nullptr)
262 : {
263 : static_assert(sizeof(Derived) == sizeof(aterm),
264 : "aterm cast can only be applied ot types derived from aterms where no extra fields are added");
265 10650928157 : assert(Derived(static_cast<const aterm&>(t)) != aterm());
266 10650928157 : return reinterpret_cast<const Derived&>(t);
267 : }
268 :
269 : /// \brief A cast from one aterm based type to another, as a reference, allowing to assign to it.
270 : // This can be useful when assigning to a term type that contains the derived term type.
271 : /// \param t A term of a type inheriting from an aterm.
272 : /// \return A term of type Derived&.
273 : template <class Derived, class Base>
274 31756 : Derived& reference_cast(Base& t,
275 : typename std::enable_if<is_convertible<Base, Derived>::value &&
276 : !std::is_base_of<Derived, Base>::value >::type* = nullptr)
277 : {
278 : static_assert(sizeof(Base) == sizeof(aterm),
279 : "aterm cast can only be applied to terms directly derived from aterms");
280 : static_assert(sizeof(Derived) == sizeof(aterm),
281 : "aterm cast can only be applied to types derived from aterms where no extra fields are added");
282 : // We do not check types as the content of the term t is likely to be overwritten shortly.
283 31756 : return reinterpret_cast<Derived&>(t);
284 : }
285 :
286 : /// \brief A cast from one aterm based type to another, as a reference, allowing to assign to it.
287 : // This can be useful when assigning to a term type that contains the derived term type.
288 : // In case Derived and Base are equal, nothing needs to be done.
289 : /// \param t A term of a type inheriting from an aterm.
290 : /// \return A term of type Derived&.
291 : template <class Derived>
292 29 : Derived& reference_cast(Derived& t)
293 : {
294 : static_assert(sizeof(Derived) == sizeof(aterm),
295 : "aterm cast can only be applied to terms directly derived from aterms");
296 : // We do not check types as the content of the term t is likely to be overwritten shortly.
297 29 : return t;
298 : }
299 :
300 : template < typename DerivedCont, typename Base, template <typename Elem> class Cont >
301 5563 : const DerivedCont& container_cast(const Cont<Base>& t,
302 : typename std::enable_if_t<
303 : is_container<DerivedCont, aterm>::value &&
304 : std::is_same_v<Cont<typename DerivedCont::value_type>, DerivedCont> &&
305 : !std::is_base_of_v<DerivedCont, Cont<Base> > &&
306 : is_convertible<Base, typename DerivedCont::value_type>::value
307 : >* = nullptr)
308 : {
309 : static_assert(sizeof(typename DerivedCont::value_type) == sizeof(aterm),
310 : "aterm cast cannot be applied types derived from aterms where extra fields are added");
311 35608 : assert(std::all_of(t.begin(),t.end(),[](const Base& u){ return typename DerivedCont::value_type(static_cast<const aterm&>(u)) != aterm();} ));
312 5563 : return reinterpret_cast<const DerivedCont&>(t);
313 : }
314 :
315 : /// \brief A cast form an aterm derived class to a class that inherits in possibly multiple steps from this class.
316 : /// \details The derived class is not allowed to contain extra fields. This conversion does not require runtime computation
317 : /// effort. Also see down_cast.
318 : /// \param t The term that is converted.
319 : /// \return A term of type Derived.
320 : template <class Derived, class Base>
321 215 : const Derived& vertical_cast(const Base& t,
322 : typename std::enable_if<is_convertible<Base, Derived>::value>::type* = nullptr)
323 : {
324 : static_assert(sizeof(Derived) == sizeof(aterm),
325 : "aterm cast cannot be applied types derived from aterms where extra fields are added");
326 215 : assert(Derived(static_cast<const aterm&>(t)) != aterm());
327 215 : return reinterpret_cast<const Derived&>(t);
328 : }
329 :
330 : template < typename DerivedCont, typename Base, template <typename Elem> class Cont >
331 : const DerivedCont& vertical_cast(const Cont<Base>& t,
332 : typename std::enable_if_t<
333 : is_container<DerivedCont, aterm>::value &&
334 : std::is_same_v<Cont<typename DerivedCont::value_type>, DerivedCont> &&
335 : is_convertible<Base, typename DerivedCont::value_type>::value
336 : >* = nullptr)
337 : {
338 : static_assert(sizeof(typename DerivedCont::value_type) == sizeof(aterm),
339 : "aterm cast cannot be applied types derived from aterms where extra fields are added");
340 : assert(std::all_of(t.begin(),t.end(),[](const Base& u){ return typename DerivedCont::value_type(static_cast<const aterm&>(u)) != aterm();} ));
341 : return reinterpret_cast<const DerivedCont&>(t);
342 : }
343 :
344 : namespace detail
345 : {
346 : /// \returns A pointer to the underlying aterm.
347 5042791931 : inline _aterm* address(const unprotected_aterm& t)
348 : {
349 5042791931 : return const_cast<_aterm*>(t.m_term);
350 : }
351 : }
352 :
353 : /// \brief Send the term in textual form to the ostream.
354 : /// \param out The stream to which the term is sent.
355 : /// \param t The term that is printed to the stream.
356 : /// \return The stream to which the term is written.
357 : std::ostream& operator<<(std::ostream& out, const atermpp::aterm& t);
358 :
359 : /// \brief Transform an aterm to an ascii string.
360 : /// \param t The input aterm.
361 : /// \return A string representation of the given term derived from an aterm.
362 10031 : inline std::string pp(const atermpp::aterm& t)
363 : {
364 10031 : std::ostringstream oss;
365 10031 : oss << t;
366 20062 : return oss.str();
367 10031 : }
368 :
369 : } // namespace atermpp
370 :
371 : namespace std
372 : {
373 :
374 : /// \brief Swaps two aterms.
375 : /// \details This operation is more efficient than exchanging terms by an assignment,
376 : /// as swapping does not require to change the protection of terms.
377 : /// In order to be used in the standard containers, the declaration must
378 : /// be preceded by an empty template declaration. This swap function is
379 : /// not used for classes that derive from the aterm class. A specific
380 : /// swap function must be provided for derived classes.
381 : /// \param t1 The first term
382 : /// \param t2 The second term
383 : template <>
384 : inline void swap(atermpp::unprotected_aterm& t1, atermpp::unprotected_aterm& t2) noexcept
385 : {
386 : t1.swap(t2);
387 : }
388 : } // namespace std
389 :
390 : #endif // MCRL2_ATERMPP_ATERM_H
|
