blob: de6da4f8c3776381c0128cb7ac63cf21fc7a82dd [file] [log] [blame]
Ted Kremenekdd54de82011-03-12 02:49:15 +00001//=== IteratorsChecker.cpp - Check for Invalidated Iterators ------*- C++ -*----
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This defines IteratorsChecker, a number of small checks for conditions
11// leading to invalid iterators being used.
12// FIXME: Currently only supports 'vector' and 'deque'
13//
14//===----------------------------------------------------------------------===//
15
16#include "clang/AST/DeclTemplate.h"
17#include "clang/Basic/SourceManager.h"
18#include "ClangSACheckers.h"
19#include "clang/StaticAnalyzer/Core/Checker.h"
20#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
21#include "clang/StaticAnalyzer/Core/CheckerManager.h"
22#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h"
24#include "clang/AST/DeclCXX.h"
25#include "clang/AST/Decl.h"
26#include "clang/AST/Type.h"
27#include "clang/AST/PrettyPrinter.h"
28#include "llvm/ADT/SmallPtrSet.h"
29#include "llvm/ADT/StringSwitch.h"
30
31
32using namespace clang;
33using namespace ento;
34
35// This is the state associated with each iterator which includes both the
36// kind of state and the instance used to initialize it.
37// FIXME: add location where invalidated for better error reporting.
38namespace {
39class RefState {
40 enum Kind { BeginValid, EndValid, Invalid, Undefined, Unknown } K;
41 const void *VR;
42
43public:
44 RefState(Kind k, const void *vr) : K(k), VR(vr) {}
45
46 bool isValid() const { return K == BeginValid || K == EndValid; }
47 bool isInvalid() const { return K == Invalid; }
48 bool isUndefined() const { return K == Undefined; }
49 bool isUnknown() const { return K == Unknown; }
50 const MemRegion *getMemRegion() const {
51 if (K == BeginValid || K == EndValid)
52 return(const MemRegion *)VR;
53 return 0;
54 }
55 const MemberExpr *getMemberExpr() const {
56 if (K == Invalid)
57 return(const MemberExpr *)VR;
58 return 0;
59 }
60
61 bool operator==(const RefState &X) const {
62 return K == X.K && VR == X.VR;
63 }
64
65 static RefState getBeginValid(const MemRegion *vr) {
66 assert(vr);
67 return RefState(BeginValid, vr);
68 }
69 static RefState getEndValid(const MemRegion *vr) {
70 assert(vr);
71 return RefState(EndValid, vr);
72 }
73 static RefState getInvalid( const MemberExpr *ME ) {
74 return RefState(Invalid, ME);
75 }
76 static RefState getUndefined( void ) {
77 return RefState(Undefined, 0);
78 }
79 static RefState getUnknown( void ) {
80 return RefState(Unknown, 0);
81 }
82
83 void Profile(llvm::FoldingSetNodeID &ID) const {
84 ID.AddInteger(K);
85 ID.AddPointer(VR);
86 }
87};
88
89enum RefKind { NoKind, VectorKind, VectorIteratorKind };
90
91class IteratorsChecker :
92 public Checker<check::PreStmt<CXXOperatorCallExpr>,
93 check::PreStmt<DeclStmt>,
94 check::PreStmt<CXXMemberCallExpr>,
95 check::PreStmt<CallExpr> >
96 {
97 // Used when parsing iterators and vectors and deques.
98 BuiltinBug *BT_Invalid, *BT_Undefined, *BT_Incompatible;
99
100public:
101 IteratorsChecker() :
102 BT_Invalid(0), BT_Undefined(0), BT_Incompatible(0)
103 {}
104 static void *getTag() { static int tag; return &tag; }
105
106 // Checker entry points.
107 void checkPreStmt(const CXXOperatorCallExpr *OCE,
108 CheckerContext &C) const;
109
110 void checkPreStmt(const DeclStmt *DS,
111 CheckerContext &C) const;
112
113 void checkPreStmt(const CXXMemberCallExpr *MCE,
114 CheckerContext &C) const;
115
116 void checkPreStmt(const CallExpr *CE,
117 CheckerContext &C) const;
118
119private:
120 const GRState *handleAssign(const GRState *state, const Expr *lexp,
121 const Expr *rexp, const LocationContext *LC) const;
122 const GRState *handleAssign(const GRState *state, const MemRegion *MR,
123 const Expr *rexp, const LocationContext *LC) const;
124 const GRState *invalidateIterators(const GRState *state, const MemRegion *MR,
125 const MemberExpr *ME) const;
126 void checkExpr(CheckerContext &C, const Expr *E) const;
127 void checkArgs(CheckerContext &C, const CallExpr *CE) const;
128 const MemRegion *getRegion(const GRState *state, const Expr *E,
129 const LocationContext *LC) const;
130 const DeclRefExpr *getDeclRefExpr(const Expr *E) const;
131};
132
133class IteratorState {
134public:
135 typedef llvm::ImmutableMap<const MemRegion *, RefState> EntryMap;
136};
137} //end anonymous namespace
138
139namespace clang {
140 namespace ento {
141 template <>
142 struct GRStateTrait<IteratorState>
143 : public GRStatePartialTrait<IteratorState::EntryMap> {
144 static void *GDMIndex() { return IteratorsChecker::getTag(); }
145 };
146 }
147}
148
149void ento::registerIteratorsChecker(CheckerManager &mgr) {
150 mgr.registerChecker<IteratorsChecker>();
151}
152
153// ===============================================
154// Utility functions used by visitor functions
155// ===============================================
156
157// check a templated type for std::vector or std::deque
158static RefKind getTemplateKind(const NamedDecl *td) {
159 const DeclContext *dc = td->getDeclContext();
160 const NamespaceDecl *nameSpace = dyn_cast<NamespaceDecl>(dc);
161 if (!nameSpace || !isa<TranslationUnitDecl>(nameSpace->getDeclContext())
162 || nameSpace->getName() != "std")
163 return NoKind;
164
165 llvm::StringRef name = td->getName();
166 return llvm::StringSwitch<RefKind>(name)
167 .Cases("vector", "deque", VectorKind)
168 .Default(NoKind);
169}
170
171static RefKind getTemplateKind(const DeclContext *dc) {
172 if (const ClassTemplateSpecializationDecl *td =
173 dyn_cast<ClassTemplateSpecializationDecl>(dc))
174 return getTemplateKind(cast<NamedDecl>(td));
175 return NoKind;
176}
177
178static RefKind getTemplateKind(const TypedefType *tdt) {
Richard Smith162e1c12011-04-15 14:24:37 +0000179 const TypedefNameDecl *td = tdt->getDecl();
Ted Kremenekdd54de82011-03-12 02:49:15 +0000180 RefKind parentKind = getTemplateKind(td->getDeclContext());
181 if (parentKind == VectorKind) {
182 return llvm::StringSwitch<RefKind>(td->getName())
183 .Cases("iterator",
184 "const_iterator",
185 "reverse_iterator", VectorIteratorKind)
186 .Default(NoKind);
187 }
188 return NoKind;
189}
190
191static RefKind getTemplateKind(const TemplateSpecializationType *tsp) {
192 const TemplateName &tname = tsp->getTemplateName();
193 TemplateDecl *td = tname.getAsTemplateDecl();
194 if (!td)
195 return NoKind;
196 return getTemplateKind(td);
197}
198
199static RefKind getTemplateKind(QualType T) {
200 if (const TemplateSpecializationType *tsp =
201 T->getAs<TemplateSpecializationType>()) {
202 return getTemplateKind(tsp);
203 }
204 if (const ElaboratedType *ET = dyn_cast<ElaboratedType>(T)) {
205 QualType namedType = ET->getNamedType();
206 if (const TypedefType *tdt = namedType->getAs<TypedefType>())
207 return getTemplateKind(tdt);
208 if (const TemplateSpecializationType *tsp =
209 namedType->getAs<TemplateSpecializationType>()) {
210 return getTemplateKind(tsp);
211 }
212 }
213 return NoKind;
214}
215
216// Iterate through our map and invalidate any iterators that were
217// initialized fromt the specified instance MemRegion.
218const GRState *IteratorsChecker::invalidateIterators(const GRState *state,
219 const MemRegion *MR, const MemberExpr *ME) const {
220 IteratorState::EntryMap Map = state->get<IteratorState>();
221 if (Map.isEmpty())
222 return state;
223
224 // Loop over the entries in the current state.
225 // The key doesn't change, so the map iterators won't change.
226 for (IteratorState::EntryMap::iterator I = Map.begin(), E = Map.end();
227 I != E; ++I) {
228 RefState RS = I.getData();
229 if (RS.getMemRegion() == MR)
230 state = state->set<IteratorState>(I.getKey(), RefState::getInvalid(ME));
231 }
232
233 return state;
234}
235
236// Handle assigning to an iterator where we don't have the LValue MemRegion.
237const GRState *IteratorsChecker::handleAssign(const GRState *state,
238 const Expr *lexp, const Expr *rexp, const LocationContext *LC) const {
239 // Skip the cast if present.
Douglas Gregor03e80032011-06-21 17:03:29 +0000240 if (const MaterializeTemporaryExpr *M
241 = dyn_cast<MaterializeTemporaryExpr>(lexp))
242 lexp = M->GetTemporaryExpr();
243 if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(lexp))
244 lexp = ICE->getSubExpr();
Ted Kremenekdd54de82011-03-12 02:49:15 +0000245 SVal sv = state->getSVal(lexp);
246 const MemRegion *MR = sv.getAsRegion();
247 if (!MR)
248 return state;
249 RefKind kind = getTemplateKind(lexp->getType());
250
251 // If assigning to a vector, invalidate any iterators currently associated.
252 if (kind == VectorKind)
253 return invalidateIterators(state, MR, 0);
254
255 // Make sure that we are assigning to an iterator.
256 if (getTemplateKind(lexp->getType()) != VectorIteratorKind)
257 return state;
258 return handleAssign(state, MR, rexp, LC);
259}
260
261// handle assigning to an iterator
262const GRState *IteratorsChecker::handleAssign(const GRState *state,
263 const MemRegion *MR, const Expr *rexp, const LocationContext *LC) const {
264 // Assume unknown until we find something definite.
265 state = state->set<IteratorState>(MR, RefState::getUnknown());
Douglas Gregor03e80032011-06-21 17:03:29 +0000266 if (const MaterializeTemporaryExpr *M
267 = dyn_cast<MaterializeTemporaryExpr>(rexp))
268 rexp = M->GetTemporaryExpr();
269 if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(rexp))
270 rexp = ICE->getSubExpr();
Ted Kremenekdd54de82011-03-12 02:49:15 +0000271 // Need to handle three cases: MemberCall, copy, copy with addition.
272 if (const CallExpr *CE = dyn_cast<CallExpr>(rexp)) {
273 // Handle MemberCall.
274 if (const MemberExpr *ME = dyn_cast<MemberExpr>(CE->getCallee())) {
275 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(ME->getBase());
276 if (!DRE)
277 return state;
278 // Verify that the type is std::vector<T>.
279 if (getTemplateKind(DRE->getType()) != VectorKind)
280 return state;
281 // Now get the MemRegion associated with the instance.
282 const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl());
283 if (!VD)
284 return state;
285 const MemRegion *IMR = state->getRegion(VD, LC);
286 if (!IMR)
287 return state;
288 // Finally, see if it is one of the calls that will create
289 // a valid iterator and mark it if so, else mark as Unknown.
290 llvm::StringRef mName = ME->getMemberDecl()->getName();
Ted Kremenek7084da32011-03-12 04:08:07 +0000291
292 if (llvm::StringSwitch<bool>(mName)
293 .Cases("begin", "insert", "erase", true).Default(false)) {
294 return state->set<IteratorState>(MR, RefState::getBeginValid(IMR));
295 }
296 if (mName == "end")
297 return state->set<IteratorState>(MR, RefState::getEndValid(IMR));
298
299 return state->set<IteratorState>(MR, RefState::getUnknown());
Ted Kremenekdd54de82011-03-12 02:49:15 +0000300 }
301 }
302 // Handle straight copy from another iterator.
303 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(rexp)) {
304 if (getTemplateKind(DRE->getType()) != VectorIteratorKind)
305 return state;
306 // Now get the MemRegion associated with the instance.
307 const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl());
308 if (!VD)
309 return state;
310 const MemRegion *IMR = state->getRegion(VD, LC);
311 if (!IMR)
312 return state;
313 // Get the RefState of the iterator being copied.
314 const RefState *RS = state->get<IteratorState>(IMR);
315 if (!RS)
316 return state;
317 // Use it to set the state of the LValue.
318 return state->set<IteratorState>(MR, *RS);
319 }
320 // If we have operator+ or operator- ...
321 if (const CXXOperatorCallExpr *OCE = dyn_cast<CXXOperatorCallExpr>(rexp)) {
322 OverloadedOperatorKind Kind = OCE->getOperator();
323 if (Kind == OO_Plus || Kind == OO_Minus) {
324 // Check left side of tree for a valid value.
325 state = handleAssign( state, MR, OCE->getArg(0), LC);
326 const RefState *RS = state->get<IteratorState>(MR);
327 // If found, return it.
328 if (!RS->isUnknown())
329 return state;
330 // Otherwise return what we find in the right side.
331 return handleAssign(state, MR, OCE->getArg(1), LC);
332 }
333 }
334 // Fall through if nothing matched.
335 return state;
336}
337
338// Iterate through the arguments looking for an Invalid or Undefined iterator.
339void IteratorsChecker::checkArgs(CheckerContext &C, const CallExpr *CE) const {
340 for (CallExpr::const_arg_iterator I = CE->arg_begin(), E = CE->arg_end();
341 I != E; ++I) {
342 checkExpr(C, *I);
343 }
344}
345
346// Get the DeclRefExpr associated with the expression.
347const DeclRefExpr *IteratorsChecker::getDeclRefExpr(const Expr *E) const {
348 // If it is a CXXConstructExpr, need to get the subexpression.
349 if (const CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(E)) {
350 if (CE->getNumArgs()== 1) {
351 CXXConstructorDecl *CD = CE->getConstructor();
352 if (CD->isTrivial())
353 E = CE->getArg(0);
354 }
355 }
Douglas Gregor03e80032011-06-21 17:03:29 +0000356 if (const MaterializeTemporaryExpr *M = dyn_cast<MaterializeTemporaryExpr>(E))
357 E = M->GetTemporaryExpr();
358 if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
359 E = ICE->getSubExpr();
Ted Kremenekdd54de82011-03-12 02:49:15 +0000360 // If it isn't one of our types, don't do anything.
361 if (getTemplateKind(E->getType()) != VectorIteratorKind)
362 return NULL;
363 return dyn_cast<DeclRefExpr>(E);
364}
365
366// Get the MemRegion associated with the expresssion.
367const MemRegion *IteratorsChecker::getRegion(const GRState *state,
368 const Expr *E, const LocationContext *LC) const {
369 const DeclRefExpr *DRE = getDeclRefExpr(E);
370 if (!DRE)
371 return NULL;
372 const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl());
373 if (!VD)
374 return NULL;
375 // return the MemRegion associated with the iterator
376 return state->getRegion(VD, LC);
377}
378
379// Check the expression and if it is an iterator, generate a diagnostic
380// if the iterator is not valid.
381// FIXME: this method can generate new nodes, and subsequent logic should
382// use those nodes. We also cannot create multiple nodes at one ProgramPoint
383// with the same tag.
384void IteratorsChecker::checkExpr(CheckerContext &C, const Expr *E) const {
385 const GRState *state = C.getState();
386 const MemRegion *MR = getRegion(state, E,
387 C.getPredecessor()->getLocationContext());
388 if (!MR)
389 return;
390
391 // Get the state associated with the iterator.
392 const RefState *RS = state->get<IteratorState>(MR);
393 if (!RS)
394 return;
395 if (RS->isInvalid()) {
396 if (ExplodedNode *N = C.generateNode()) {
397 if (!BT_Invalid)
398 // FIXME: We are eluding constness here.
399 const_cast<IteratorsChecker*>(this)->BT_Invalid = new BuiltinBug("");
400
401 std::string msg;
402 const MemberExpr *ME = RS->getMemberExpr();
403 if (ME) {
404 std::string name = ME->getMemberNameInfo().getAsString();
405 msg = "Attempt to use an iterator made invalid by call to '" +
406 name + "'";
407 }
408 else {
409 msg = "Attempt to use an iterator made invalid by copying another "
410 "container to its container";
411 }
412
413 EnhancedBugReport *R = new EnhancedBugReport(*BT_Invalid, msg, N);
414 R->addRange(getDeclRefExpr(E)->getSourceRange());
415 C.EmitReport(R);
416 }
417 }
418 else if (RS->isUndefined()) {
419 if (ExplodedNode *N = C.generateNode()) {
420 if (!BT_Undefined)
421 // FIXME: We are eluding constness here.
422 const_cast<IteratorsChecker*>(this)->BT_Undefined =
423 new BuiltinBug("Use of iterator that is not defined");
424
425 EnhancedBugReport *R = new EnhancedBugReport(*BT_Undefined,
426 BT_Undefined->getDescription(), N);
427 R->addRange(getDeclRefExpr(E)->getSourceRange());
428 C.EmitReport(R);
429 }
430 }
431}
432
433// ===============================================
434// Path analysis visitor functions
435// ===============================================
436
437// For a generic Call, just check the args for bad iterators.
438void IteratorsChecker::checkPreStmt(const CallExpr *CE,
439 CheckerContext &C) const{
440
441 // FIXME: These checks are to currently work around a bug
442 // in CheckerManager.
443 if (isa<CXXOperatorCallExpr>(CE))
444 return;
445 if (isa<CXXMemberCallExpr>(CE))
446 return;
447
448 checkArgs(C, CE);
449}
450
451// Handle operator calls. First, if it is operator=, check the argument,
452// and handle assigning and set target state appropriately. Otherwise, for
453// other operators, check the args for bad iterators and handle comparisons.
454void IteratorsChecker::checkPreStmt(const CXXOperatorCallExpr *OCE,
455 CheckerContext &C) const
456{
457 const LocationContext *LC = C.getPredecessor()->getLocationContext();
458 const GRState *state = C.getState();
459 OverloadedOperatorKind Kind = OCE->getOperator();
460 if (Kind == OO_Equal) {
461 checkExpr(C, OCE->getArg(1));
462 state = handleAssign(state, OCE->getArg(0), OCE->getArg(1), LC);
463 C.addTransition(state);
464 return;
465 }
466 else {
467 checkArgs(C, OCE);
468 // If it is a compare and both are iterators, ensure that they are for
469 // the same container.
470 if (Kind == OO_EqualEqual || Kind == OO_ExclaimEqual ||
471 Kind == OO_Less || Kind == OO_LessEqual ||
472 Kind == OO_Greater || Kind == OO_GreaterEqual) {
473 const MemRegion *MR0, *MR1;
474 MR0 = getRegion(state, OCE->getArg(0), LC);
475 if (!MR0)
476 return;
477 MR1 = getRegion(state, OCE->getArg(1), LC);
478 if (!MR1)
479 return;
480 const RefState *RS0, *RS1;
481 RS0 = state->get<IteratorState>(MR0);
482 if (!RS0)
483 return;
484 RS1 = state->get<IteratorState>(MR1);
485 if (!RS1)
486 return;
487 if (RS0->getMemRegion() != RS1->getMemRegion()) {
488 if (ExplodedNode *N = C.generateNode()) {
489 if (!BT_Incompatible)
490 const_cast<IteratorsChecker*>(this)->BT_Incompatible =
491 new BuiltinBug(
492 "Cannot compare iterators from different containers");
493
494 EnhancedBugReport *R = new EnhancedBugReport(*BT_Incompatible,
495 BT_Incompatible->getDescription(), N);
496 R->addRange(OCE->getSourceRange());
497 C.EmitReport(R);
498 }
499 }
500 }
501 }
502}
503
504// Need to handle DeclStmts to pick up initializing of iterators and to mark
505// uninitialized ones as Undefined.
506void IteratorsChecker::checkPreStmt(const DeclStmt *DS,
507 CheckerContext &C) const {
508 const Decl* D = *DS->decl_begin();
509 const VarDecl* VD = dyn_cast<VarDecl>(D);
510 // Only care about iterators.
511 if (getTemplateKind(VD->getType()) != VectorIteratorKind)
512 return;
513
514 // Get the MemRegion associated with the iterator and mark it as Undefined.
515 const GRState *state = C.getState();
516 Loc VarLoc = state->getLValue(VD, C.getPredecessor()->getLocationContext());
517 const MemRegion *MR = VarLoc.getAsRegion();
518 if (!MR)
519 return;
520 state = state->set<IteratorState>(MR, RefState::getUndefined());
521
522 // if there is an initializer, handle marking Valid if a proper initializer
523 const Expr* InitEx = VD->getInit();
524 if (InitEx) {
525 // FIXME: This is too syntactic. Since 'InitEx' will be analyzed first
526 // it should resolve to an SVal that we can check for validity
527 // *semantically* instead of walking through the AST.
528 if (const CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(InitEx)) {
529 if (CE->getNumArgs() == 1) {
530 const Expr *E = CE->getArg(0);
Douglas Gregor03e80032011-06-21 17:03:29 +0000531 if (const MaterializeTemporaryExpr *M
532 = dyn_cast<MaterializeTemporaryExpr>(E))
533 E = M->GetTemporaryExpr();
534 if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
535 InitEx = ICE->getSubExpr();
Ted Kremenekdd54de82011-03-12 02:49:15 +0000536 state = handleAssign(state, MR, InitEx,
537 C.getPredecessor()->getLocationContext());
538 }
539 }
540 }
541 C.addTransition(state);
542}
543
544
545namespace { struct CalledReserved {}; }
546namespace clang { namespace ento {
547template<> struct GRStateTrait<CalledReserved>
548 : public GRStatePartialTrait<llvm::ImmutableSet<const MemRegion*> > {
549 static void *GDMIndex() { static int index = 0; return &index; }
550};
551}}
552
553// on a member call, first check the args for any bad iterators
554// then, check to see if it is a call to a function that will invalidate
555// the iterators
556void IteratorsChecker::checkPreStmt(const CXXMemberCallExpr *MCE,
557 CheckerContext &C) const {
558 // Check the arguments.
559 checkArgs(C, MCE);
560 const MemberExpr *ME = dyn_cast<MemberExpr>(MCE->getCallee());
561 if (!ME)
562 return;
563 // Make sure we have the right kind of container.
564 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(ME->getBase());
565 if (!DRE || getTemplateKind(DRE->getType()) != VectorKind)
566 return;
567 SVal tsv = C.getState()->getSVal(DRE);
568 // Get the MemRegion associated with the container instance.
569 const MemRegion *MR = tsv.getAsRegion();
570 if (!MR)
571 return;
572 // If we are calling a function that invalidates iterators, mark them
573 // appropriately by finding matching instances.
574 const GRState *state = C.getState();
575 llvm::StringRef mName = ME->getMemberDecl()->getName();
576 if (llvm::StringSwitch<bool>(mName)
577 .Cases("insert", "reserve", "push_back", true)
578 .Cases("erase", "pop_back", "clear", "resize", true)
579 .Default(false)) {
580 // If there was a 'reserve' call, assume iterators are good.
581 if (!state->contains<CalledReserved>(MR))
582 state = invalidateIterators(state, MR, ME);
583 }
584 // Keep track of instances that have called 'reserve'
585 // note: do this after we invalidate any iterators by calling
586 // 'reserve' itself.
587 if (mName == "reserve")
588 state = state->add<CalledReserved>(MR);
589
590 if (state != C.getState())
591 C.addTransition(state);
592}
593