Computer Laboratory

Automaton.h
Go to the documentation of this file.
1 
2 /*
3  * Copyright (c) 2013 Jonathan Anderson
4  * All rights reserved.
5  *
6  * This software was developed by SRI International and the University of
7  * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
8  * ("CTSRD"), as part of the DARPA CRASH research programme.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  * notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in the
17  * documentation and/or other materials provided with the distribution.
18  *
19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29  * SUCH DAMAGE.
30  */
31 
32 #ifndef AUTOMATON_H
33 #define AUTOMATON_H
34 
35 #include "llvm/ADT/ArrayRef.h"
36 #include "llvm/ADT/StringRef.h"
37 
38 #include "Transition.h"
39 
40 #include <map>
41 
42 
43 namespace tesla {
44 
45 // TESLA IR classes
46 class AutomatonDescription;
47 class BooleanExpr;
48 class Expression;
49 class FieldAssignment;
50 class FunctionEvent;
51 class Identifier;
52 class NowEvent;
53 class Sequence;
54 
55 // Automata classes
56 class State;
57 
58 namespace internal {
59  class DFABuilder;
60  class NFAParser;
61 }
62 
63 typedef std::map<Identifier,const AutomatonDescription*> AutomataMap;
64 
74 class Automaton {
75  friend class internal::DFABuilder;
76 public:
78  enum Type {
84 
87 
90  };
91 
92  typedef llvm::SmallVector<State*,10> StateVector;
93 
94 
95  virtual ~Automaton() {}
96  virtual bool IsRealisable() const;
97 
98  size_t ID() const { return id; }
99  const AutomatonDescription& getAssertion() const { return assertion; }
100  const Usage* Use() const { return use; }
101  size_t StateCount() const { return States.size(); }
102  size_t TransitionCount() const { return Transitions.size(); }
103 
104  std::string Name() const { return name; }
105  std::string String() const;
106  std::string Dot() const;
107 
109  TransitionSets::const_iterator begin() const { return Transitions.begin(); }
110  TransitionSets::const_iterator end() const { return Transitions.end(); }
111 
112 protected:
113  Automaton(size_t id, const AutomatonDescription&,
114  const Usage*, llvm::StringRef Name,
115  llvm::ArrayRef<State*>, const TransitionSets&);
116 
117  const size_t id;
119  const Usage *use;
120  const std::string name;
121 
124 };
125 
126 
127 
140 class NFA : public Automaton {
141  friend class DFA;
142 
143 public:
144  static NFA* Parse(const AutomatonDescription*, const Usage*, unsigned int id);
145 
152  NFA* Link(const AutomataMap& Desc);
153 
154 private:
155  NFA(size_t id, const AutomatonDescription& A,
156  const Usage*, llvm::StringRef Name,
157  llvm::ArrayRef<State*>, const TransitionSets&);
158 
159  friend class internal::NFAParser;
160 };
161 
162 
168 class DFA : public Automaton {
169  friend class internal::DFABuilder;
170 
171 public:
172  static DFA* Convert(const NFA*);
173  bool IsRealisable() const { return true; }
174 
175 private:
176  DFA(size_t id, AutomatonDescription& A,
177  const Usage*, llvm::StringRef Name,
178  llvm::ArrayRef<State*>, const TransitionSets&);
179 };
180 
181 } // namespace tesla
182 
183 #endif // AUTOMATON_H
184