Vcsn  2.2a
Be Rational
expressionset.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <set>
4 #include <string>
5 
9 #include <vcsn/ctx/context.hh>
12 #include <vcsn/labelset/oneset.hh>
13 #include <vcsn/misc/raise.hh>
14 #include <vcsn/misc/star-status.hh>
15 #include <vcsn/weightset/b.hh>
16 #include <vcsn/weightset/nmin.hh>
17 #include <vcsn/weightset/q.hh>
18 #include <vcsn/weightset/r.hh>
19 #include <vcsn/weightset/z.hh>
20 #include <vcsn/weightset/zmin.hh>
21 
22 namespace vcsn
23 {
24  namespace rat
25  {
28  template <typename Context>
30  {
31  public:
33  using context_t = Context;
37  using labelset_ptr = typename context_t::labelset_ptr;
38  using weightset_ptr = typename context_t::weightset_ptr;
40  using weight_t = typename weightset_t::value_t;
43 
45  //
46  // See http://stackoverflow.com/questions/15537023 to know why we
47  // add the vcsn::rat:: part: GCC wants it, Clang does not care,
48  // both are right.
49 #define DEFINE(Type) \
50  using Type ## _t = vcsn::rat::Type<context_t>
69 #undef DEFINE
70 
72  using value_t = typename node_t::value_t;
74  using type_t = typename node_t::type_t;
76  using values_t = typename node_t::values_t;
77 
78  template <type_t Type>
80  template <type_t Type>
82 
83  using word_t = value_t;
84  using letter_t = value_t;
85 
86  public:
88  static symbol sname();
90  static self_t make(std::istream& is);
91 
96 
100  bool open(bool o) const;
101 
103  const context_t& context() const;
104 
106  identities_t identities() const;
107 
109  const labelset_ptr& labelset() const;
111  const weightset_ptr& weightset() const;
112 
114  static value_t special()
115  {
116  return atom(labelset_t::special());
117  }
118 
120  static bool is_special(const value_t& v)
121  {
122  return equal(special(), v);
123  }
124 
126  bool is_letter(value_t) const
127  {
128  return false;
129  }
130 
134  bool is_zero(const value_t& v) const ATTRIBUTE_PURE;
135 
139  static bool is_one(const value_t& v) ATTRIBUTE_PURE;
140 
142  bool is_universal(const value_t& v) const ATTRIBUTE_PURE;
143 
145  static constexpr bool is_letterized()
146  {
147  return false;
148  }
149 
151  static constexpr bool is_commutative()
152  {
153  return false;
154  }
155 
157  static constexpr bool is_idempotent()
158  {
159  // FIXME: well, the truth is that we are idempotent if the
160  // weightset is, _and_ we apply ACI to addition.
161  return weightset_t::is_idempotent();
162  }
163 
165  static constexpr bool show_one()
166  {
167  return false;
168  }
169 
171  static constexpr bool has_lightening_weights()
172  {
173  return weightset_t::has_lightening_weights();
174  }
175 
177  static constexpr bool has_one()
178  {
179  return true;
180  }
181 
183  static constexpr bool is_expressionset()
184  {
185  return true;
186  }
187 
189  static constexpr bool is_free()
190  {
191  return false;
192  }
193 
195  static constexpr star_status_t star_status()
196  {
198  }
199 
200  template <typename GenSet>
201  auto conv(const letterset<GenSet>& ls,
202  typename letterset<GenSet>::value_t v) const -> value_t;
203  auto conv(b, typename b::value_t v) const -> value_t;
204  auto conv(const z& ws, typename z::value_t v) const -> value_t;
205  auto conv(const q& ws, typename q::value_t v) const -> value_t;
206  auto conv(const r& ws, typename r::value_t v) const -> value_t;
207  auto conv(const nmin& ws, typename nmin::value_t v) const -> value_t;
208  auto conv(const zmin& ws, typename zmin::value_t v) const -> value_t;
209  template <typename Ctx2>
210  auto conv(const expressionset<Ctx2>& ws,
211  typename expressionset<Ctx2>::value_t v) const -> value_t;
212 
214  static size_t size(const value_t& v);
215 
217  static bool less(const value_t& l, const value_t& r);
218 
223  static bool less_linear(const value_t& l, const value_t& r);
224 
226  static bool equal(const value_t& l, const value_t& r);
227 
229  static size_t hash(const value_t& v);
230 
232  static auto atom(const label_t& v)
233  -> value_t;
234 
235  // Concrete type implementation.
236  auto zero() const -> value_t;
237  static auto one() -> value_t;
238  auto add(const value_t& l, const value_t& r) const -> value_t;
239  auto mul(const value_t& l, const value_t& r) const -> value_t;
240 
250  auto concat(const value_t& l, const value_t& r) const -> value_t;
251 
252  auto conjunction(const value_t& l, const value_t& r) const -> value_t;
253  auto infiltration(const value_t& l, const value_t& r) const -> value_t;
254  auto shuffle(const value_t& l, const value_t& r) const -> value_t;
255  template <typename... Value>
256  auto tuple(Value&&... v) const -> value_t;
258  auto power(const value_t& e, unsigned n) const -> value_t;
259  auto ldiv(const value_t& l, const value_t& r) const -> value_t;
260  auto rdiv(const value_t& l, const value_t& r) const -> value_t;
261  auto star(const value_t& e) const -> value_t;
263  auto complement(const value_t& e) const -> value_t;
265  auto transposition(const value_t& e) const -> value_t;
267  auto rmul(const value_t& e, const weight_t& w) const -> value_t;
269  auto lmul(const weight_t& w, const value_t& e) const -> value_t;
271  auto transpose(const value_t& e) const -> value_t;
272 
274  auto word(label_t l) const -> word_t
275  {
276  return l;
277  }
278 
280  template <typename... Args>
281  auto letter_class(Args&&... chars) const -> value_t;
282 
284  auto conv(std::istream& is, bool = true) const -> value_t;
285 
287  auto conv(const self_t&, const value_t& v) const -> value_t;
288 
290  template <typename Fun>
291  static void convs(std::istream&, Fun)
292  {
293  raise(sname(), ": ranges not implemented");
294  }
295 
296  auto print(const value_t& v, std::ostream& o, format fmt = {}) const
297  -> std::ostream&;
298 
300  auto print_set(std::ostream& o, format fmt = {}) const
301  -> std::ostream&;
302 
304  template <unsigned Tape, typename Ctx = context_t>
305  using project_t
307 
308 
309  template <typename Sequence>
311 
312  template <size_t... I>
313  struct as_tupleset_impl<detail::index_sequence<I...>>
314  {
317 
318  static type value(const self_t& self)
319  {
320  return {detail::project<I>(self)...};
321  }
322  };
323 
325  template <typename Ctx = context_t>
326  using as_tupleset_t
328 
330  template <typename Ctx = context_t>
331  auto as_tupleset() const
332  -> std::enable_if_t<Ctx::is_lat, as_tupleset_t<Ctx>>
333  {
335  }
336 
337  private:
348  const self_t& self() const { return static_cast<const self_t&>(*this); }
349 
352  auto add_(values_t&& vs) const -> value_t;
353 
354  auto add_linear_(const sum_t& addends, const value_t& r) const -> value_t;
355  auto add_linear_(const sum_t& s1, const sum_t& s2) const -> value_t;
356 
360  auto add_linear_(const value_t& l, const value_t& r) const -> value_t;
361 
364  static auto unwrap_possible_lweight_(const value_t& e) -> value_t;
367  static type_t type_ignoring_lweight_(const value_t& e);
370  static weight_t possibly_implicit_lweight_(const value_t& e);
371 
375  template <type_t Type>
376  void gather_(values_t& res, const value_t& v) const;
377 
382  template <type_t Type>
383  values_t gather_(const value_t& l, const value_t& r) const;
384 
386  auto concat_(const value_t& l, const value_t& r, std::true_type) const -> value_t;
388  auto concat_(const value_t& l, const value_t& r, std::false_type) const -> value_t;
389 
391  template <typename LabelSet_, typename... Args>
392  auto letter_class_(const Args&&... chars, std::true_type) const -> value_t;
393 
395  template <typename LabelSet_>
396  value_t
397  letter_class_(std::set<std::pair<typename LabelSet_::letter_t,
398  typename LabelSet_::letter_t>> chars,
399  bool accept,
400  std::false_type) const;
401 
403  template <typename Dummy = void>
405  {
407  static bool is_label(const tuple_t& v)
408  {
409  return is_label_(v, labelset_t::indices);
410  }
411 
414  static label_t as_label(const tuple_t& v)
415  {
416  return as_label_(v, labelset_t::indices);
417  }
418 
419  template <size_t... I>
421  {
422  for (auto b: {(std::get<I>(v.sub())->type() == type_t::atom
423  || (std::get<I>(v.sub())->type() == type_t::one
424  && labelset_t::template valueset_t<I>::has_one()))...})
425  if (!b)
426  return false;
427  return true;
428  }
429 
430  template <size_t... I>
432  {
433  return label_t{as_label_<I>(v)...};
434  }
435 
436  template <size_t I>
437  static typename project_t<I>::label_t as_label_(const tuple_t& v)
438  {
439  if (std::get<I>(v.sub())->type() == type_t::one)
440  return detail::label_one<typename labelset_t::template valueset_t<I>>();
441  else
442  return std::dynamic_pointer_cast<const typename project_t<I>::atom_t>
443  (std::get<I>(v.sub()))->value();
444  }
445  };
446 
447  private:
452  };
453  } // rat::
454 
455  namespace detail
456  {
458  template <typename Ctx>
460  {
462  static type value(const type& ls)
463  {
464  return ls;
465  }
466  };
467 
469  template <typename Ctx>
471  {
473  static type value(const type& ls)
474  {
475  return ls;
476  }
477  };
478 
480  template <typename Ctx1, typename Ctx2>
481  struct join_impl<expressionset<Ctx1>, expressionset<Ctx2>>
482  {
484 
485  static type join(const expressionset<Ctx1>& lhs,
486  const expressionset<Ctx2>& rhs)
487  {
488  return {vcsn::join(lhs.context(), rhs.context()),
489  vcsn::join(lhs.identities(), rhs.identities())};
490  }
491  };
492 
494  // FIXME: what about the other labelsets?
495  template <typename GenSet1, typename Ctx2>
496  struct join_impl<letterset<GenSet1>, expressionset<Ctx2>>
497  {
501 
502  static type join(const letterset<GenSet1>& a,
503  const expressionset<Ctx2>& b)
504  {
505  return {context_t{vcsn::join(a, *b.labelset()), *b.weightset()},
506  b.identities()};
507  }
508  };
509 
510  // B. FIXME: screams for refactoring!
511  template <typename Context>
512  struct join_impl<b, expressionset<Context>>
513  {
515  static type join(const b&, const expressionset<Context>& rhs)
516  {
517  return rhs;
518  }
519  };
520 
521  template <typename W1, typename W2>
523 
524  template <typename WeightSet, typename Context>
526  {
530  static type join(const WeightSet& ws, const expressionset<Context>& rs)
531  {
532  return {context_t{*rs.labelset(), vcsn::join(ws, *rs.weightset())},
533  rs.identities()};
534  }
535  };
536 #define JOIN_IMPL_SIMPLE(WS) \
537  template <typename Context> \
538  struct join_impl<WS, expressionset<Context>> \
539  : public join_impl_simple<WS, expressionset<Context>> \
540  {};
541 
542 
547 
548 #undef JOIN_IMPL_SIMPLE
549 
550  }
551 
553  template <typename Context>
556  {
557  return {ctx, identities};
558  }
559 
561  template <typename Ctx1, typename Ctx2>
562  inline
563  auto
566  {
567  return {meet(a.context(), b.context()),
568  meet(a.identities(), b.identities())};
569  }
570 
571 } // namespace vcsn
572 
574 
575 // This is ugly, yet I don't know how to address this circular
576 // dependency another way: expressionset.hxx uses is-valid-expression.hh,
577 // which, of course, also uses expressionset.hh.
578 //
579 // So let's have expressionset.hh first accept a forward declaration (via
580 // algos/fwd.hh), then provide here the needed definition. Do not
581 // leave this inside the CPP guard.
582 
static constexpr bool is_letterized()
When used as a labelset.
identities_t identities() const
Accessor to the identities set.
std::istringstream is
The input stream: the specification to translate.
Definition: translate.cc:380
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
bool is_universal(const value_t &v) const ATTRIBUTE_PURE
Whether v is the 0{c}.
static type join(const expressionset< Ctx1 > &lhs, const expressionset< Ctx2 > &rhs)
auto print_set(std::ostream &o, format fmt={}) const -> std::ostream &
Format the description of this expressionset.
The smallest nullableset which includes LabelSet.
Definition: labelset.hh:148
A structure that implements the computation of join(V1, V2).
Definition: join.hh:18
void gather_(values_t &res, const value_t &v) const
Push v in res, applying associativity if possible.
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:54
weightset_t_of< context_t > weightset_t
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
typename node_t::value_t value_t
An expression (a shared pointer to a tree).
An inner node implementing a weight.
Definition: expression.hh:264
context_t ctx_
The context of the expressions.
rat::identities identities(const expression &exp)
Bridge.
Definition: identities.hh:19
static bool is_special(const value_t &v)
When used as a LabelSet.
auto lmul(const weight_t &w, const value_t &e) const -> value_t
Left-multiplication by a weight.
static type join(const b &, const expressionset< Context > &rhs)
static bool equal(const value_t &l, const value_t &r)
Whether l == r.
std::shared_ptr< const node_t > value_t
An expression usable with value semantics.
Definition: expression.hh:88
star_status_t
Definition: star-status.hh:5
static constexpr bool has_lightening_weights()
When used as WeightSet.
The LAW from a LAL.
Definition: labelset.hh:259
#define DEFINE(Type)
Type of expressions.
auto rmul(const value_t &e, const weight_t &w) const -> value_t
Right-multiplication by a weight.
auto conv(const letterset< GenSet > &ls, typename letterset< GenSet >::value_t v) const -> value_t
static label_t as_label_(const tuple_t &v, detail::index_sequence< I... >)
expressionset< Context > make_expressionset(const Context &ctx, rat::identities identities={})
Shorthand to expressionset constructor.
static bool is_label_(const tuple_t &v, detail::index_sequence< I... >)
static size_t hash(const value_t &v)
Hash v.
static bool less_linear(const value_t &l, const value_t &r)
Whether l < r, ignoring lweight.
auto concat(const value_t &l, const value_t &r) const -> value_t
Similar to mul, but in the case of LAW, merge the labels.
The abstract parameterized, root for all rational expression types.
Definition: expression.hh:80
static void convs(std::istream &, Fun)
Read a range of expressions.
typename weightset_t::value_t weight_t
std::string type(const automaton &a)
The implementation type of a.
Definition: others.cc:206
auto concat_(const value_t &l, const value_t &r, std::true_type) const -> value_t
If labelset is wordset.
static self_t make(std::istream &is)
Build from the description in is.
static size_t size(const value_t &v)
The size of v.
static project_t< I >::label_t as_label_(const tuple_t &v)
labelset_t_of< context_t > labelset_t
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
Definition: pair.hh:251
A typed expression set.
auto rs
Definition: lift.hh:151
auto word(label_t l) const -> word_t
Make a `word' out of an expression.
Turn a tuple of expressions that are labels into a multi-tape label.
Implementation of labels are letters.
Definition: fwd.hh:11
static constexpr star_status_t star_status()
When used as WeightSet.
auto rdiv(const value_t &l, const value_t &r) const -> value_t
static auto unwrap_possible_lweight_(const value_t &e) -> value_t
If e is an lweight, then its child, otherwise e.
The root from which to derive the final node types.
Definition: expression.hh:302
auto as_tupleset() const -> std::enable_if_t< Ctx::is_lat, as_tupleset_t< Ctx >>
If we are multitape, ourself as a tupleset.
auto letter_class_(const Args &&...chars, std::true_type) const -> value_t
If labelset is oneset.
auto zero() const -> value_t
static value_t special()
When used as a LabelSet.
typename node_t::values_t values_t
A list (vector) of expressions.
rat::type_t type_t
The possible types of expressions.
Definition: expression.hh:26
const labelset_ptr & labelset() const
Accessor to the labelset.
static symbol sname()
Static description key.
static type join(const letterset< GenSet1 > &a, const expressionset< Ctx2 > &b)
expressionset< Context > self_t
static constexpr bool is_expressionset()
When used as WeightSet.
std::vector< value_t > values_t
Definition: expression.hh:89
auto add_linear_(const sum_t &addends, const value_t &r) const -> value_t
auto join(const ValueSet &vs) -> ValueSet
The join of a single valueset.
Definition: join.hh:44
auto power(const value_t &e, unsigned n) const -> value_t
Add a power operator.
static bool is_label(const tuple_t &v)
Are all the components labels?
label_t_of< context_t > label_t
auto mul(const value_t &l, const value_t &r) const -> value_t
expressionset_impl(const context_t &ctx, identities_t ids={})
Constructor.
static auto atom(const label_t &v) -> value_t
Build a label.
static constexpr bool has_one()
When used as WeightSet.
Implementation of nodes of tuple of rational expressions.
Definition: expression.hh:182
letter_t value_t
Definition: letterset.hh:32
auto print(const value_t &v, std::ostream &o, format fmt={}) const -> std::ostream &
const values_t sub() const
Definition: expression.hh:219
static constexpr bool is_idempotent()
When used as WeightSet.
decltype(join(std::declval< ValueSets >()...)) join_t
The type of the join of the ValueSets.
Definition: join.hh:78
STL namespace.
static constexpr bool show_one()
When used as WeightSet.
static label_t as_label(const tuple_t &v)
All the components are (single-tape) labels: make this a multitape label.
static type join(const WeightSet &ws, const expressionset< Context > &rs)
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
static constexpr bool is_free()
When used as WeightSet.
auto add(const value_t &l, const value_t &r) const -> value_t
type_t
The possible types of expressions.
Definition: fwd.hh:39
auto add_(values_t &&vs) const -> value_t
From a list of values, build a sum, taking care of the empty and singleton cases. ...
An inner node with multiple children.
Definition: expression.hh:118
const weightset_ptr & weightset() const
Accessor to the weightset.
const context_t & context() const
Accessor to the context.
An inner node.
Definition: expression.hh:101
expressionset< detail::project_context< Tape, Ctx >> project_t
The type of the expressionset for the Tape-th tape.
typename node_t::type_t type_t
Type tag for AST classes.
static identities ids(const driver &d)
Get the identities of the driver.
Definition: parse.cc:89
typename context_t::labelset_ptr labelset_ptr
auto label_one() -> std::enable_if_t< LabelSet::has_one(), typename LabelSet::value_t >
This LabelSet's one(), if supported.
Definition: labelset.hh:45
bool is_zero(const value_t &v) const ATTRIBUTE_PURE
Whether v is the \z.
const identities_t ids_
The set of rewriting rules to apply.
typename as_tupleset_impl< typename labelset_t_of< Ctx >::indices_t::type >::type as_tupleset_t
If we are multitape, our type as a tupleset.
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82
static type_t type_ignoring_lweight_(const value_t &e)
The type of e, or the type of its child if e is a lweight.
vcsn::rat::sum< context_t > sum_t
auto letter_class(Args &&...chars) const -> value_t
An expression matching one character amongst chars.
identities meet(identities i1, identities i2)
Definition: identities.cc:72
static weight_t possibly_implicit_lweight_(const value_t &e)
The weight of e if it's an lweight, otherwise the weight one().
bool open(bool o) const
Whether unknown letters should be added, or rejected.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
static bool less(const value_t &l, const value_t &r)
Whether l < r.
bool is_letter(value_t) const
When used as a LabelSet.
always valid.
Definition: star-status.hh:17
typename context_t::weightset_ptr weightset_ptr
static bool is_one(const value_t &v) ATTRIBUTE_PURE
Whether v is the \e.
static constexpr bool is_commutative()
When used as WeightSet.
auto transpose(const value_t &e) const -> value_t
The transposed of this rational expression.
An expressionset can implement several different sets of identities on expressions.
Definition: identities.hh:21
An input/output format for valuesets.
Definition: format.hh:11
#define JOIN_IMPL_SIMPLE(WS)
Definition: a-star.hh:8