Environment.h revision d4ce811ae08398e357c8ce3e707ba5f2aa0041a5
1d4931632946fe86fc2b09496f2b62443440a7da4Ted Kremenek//== Environment.h - Map from Stmt* to Locations/Values ---------*- C++ -*--==//
28133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek//
38133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek//                     The LLVM Compiler Infrastructure
48133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek//
58133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek// This file is distributed under the University of Illinois Open Source
68133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek// License. See LICENSE.TXT for details.
78133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek//
88133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek//===----------------------------------------------------------------------===//
98133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek//
108133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek//  This file defined the Environment and EnvironmentManager classes.
118133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek//
128133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek//===----------------------------------------------------------------------===//
138133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek
145a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis#ifndef LLVM_CLANG_GR_ENVIRONMENT_H
155a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis#define LLVM_CLANG_GR_ENVIRONMENT_H
168133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek
175eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek#include "clang/Analysis/AnalysisContext.h"
189b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
195e2d2c2ee3cf410643e0f9a5701708e51409d973Benjamin Kramer#include "llvm/ADT/ImmutableMap.h"
208133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek
218133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremeneknamespace clang {
228133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek
235a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidisclass LiveVariables;
245a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis
259ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremeneknamespace ento {
265a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis
278133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenekclass EnvironmentManager;
28c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenekclass SValBuilder;
29df9cdf8fce5bb43b335994f946f7c8e3a3bca7faTed Kremenek
305eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek/// An entry in the environment consists of a Stmt and an LocationContext.
315eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek/// This allows the environment to manage context-sensitive bindings,
325eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek/// which is essentially for modeling recursive function analysis, among
335eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek/// other things.
345eca482fe895ea57bc82410222e6426c09e63284Ted Kremenekclass EnvironmentEntry : public std::pair<const Stmt*,
355eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek                                          const StackFrameContext *> {
36d4ce811ae08398e357c8ce3e707ba5f2aa0041a5Jordan Rose  friend class EnvironmentManager;
37d4ce811ae08398e357c8ce3e707ba5f2aa0041a5Jordan Rose  EnvironmentEntry makeLocation() const;
38d4ce811ae08398e357c8ce3e707ba5f2aa0041a5Jordan Rose
395eca482fe895ea57bc82410222e6426c09e63284Ted Kremenekpublic:
40d4ce811ae08398e357c8ce3e707ba5f2aa0041a5Jordan Rose  EnvironmentEntry(const Stmt *s, const LocationContext *L);
415eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek
425eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  const Stmt *getStmt() const { return first; }
435eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  const LocationContext *getLocationContext() const { return second; }
445eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek
455eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  /// Profile an EnvironmentEntry for inclusion in a FoldingSet.
465eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  static void Profile(llvm::FoldingSetNodeID &ID,
475eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek                      const EnvironmentEntry &E) {
485eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek    ID.AddPointer(E.getStmt());
495eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek    ID.AddPointer(E.getLocationContext());
505eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  }
515eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek
525eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  void Profile(llvm::FoldingSetNodeID &ID) const {
535eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek    Profile(ID, *this);
545eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  }
555eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek};
565eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek
575eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek/// An immutable map from EnvironemntEntries to SVals.
58fdf6a56339b3df94d46a49c4977e0a21e8922cf3Ted Kremenekclass Environment {
598133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenekprivate:
608133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  friend class EnvironmentManager;
611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
628133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  // Type definitions.
635eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  typedef llvm::ImmutableMap<EnvironmentEntry, SVal> BindingsTy;
648133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek
658133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  // Data.
660fb0bc4067d6c9d7c0e655300ef309b05d3adfc9Ted Kremenek  BindingsTy ExprBindings;
671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
68c179a7fbb294fe3ff6cf5479f6239a10f39628c7Zhongxing Xu  Environment(BindingsTy eb)
69c179a7fbb294fe3ff6cf5479f6239a10f39628c7Zhongxing Xu    : ExprBindings(eb) {}
701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
715eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  SVal lookupExpr(const EnvironmentEntry &E) const;
72465846324f412055dd1ce270d757bfeead0811dcTed Kremenek
731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumppublic:
740fb0bc4067d6c9d7c0e655300ef309b05d3adfc9Ted Kremenek  typedef BindingsTy::iterator iterator;
750fb0bc4067d6c9d7c0e655300ef309b05d3adfc9Ted Kremenek  iterator begin() const { return ExprBindings.begin(); }
760fb0bc4067d6c9d7c0e655300ef309b05d3adfc9Ted Kremenek  iterator end() const { return ExprBindings.end(); }
771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
785eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  /// Fetches the current binding of the expression in the
795eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  /// Environment.
80e5a934d3c840872d58724383a83443ed38f1d831Jordan Rose  SVal getSVal(const EnvironmentEntry &E, SValBuilder &svalBuilder) const;
811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
828133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  /// Profile - Profile the contents of an Environment object for use
838133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  ///  in a FoldingSet.
84c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek  static void Profile(llvm::FoldingSetNodeID& ID, const Environment* env) {
85c8413fd03f73084a5c93028f8b4db619fc388087Ted Kremenek    env->ExprBindings.Profile(ID);
868133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  }
871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
888133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  /// Profile - Used to profile the contents of this object for inclusion
898133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  ///  in a FoldingSet.
908133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  void Profile(llvm::FoldingSetNodeID& ID) const {
918133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek    Profile(ID, this);
92d72ee907f76000446c706471e93d1f299104f9a7Ted Kremenek  }
931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
94d72ee907f76000446c706471e93d1f299104f9a7Ted Kremenek  bool operator==(const Environment& RHS) const {
950fb0bc4067d6c9d7c0e655300ef309b05d3adfc9Ted Kremenek    return ExprBindings == RHS.ExprBindings;
96d72ee907f76000446c706471e93d1f299104f9a7Ted Kremenek  }
975eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek
985eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  void print(raw_ostream &Out, const char *NL, const char *Sep) const;
995eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek
1005eca482fe895ea57bc82410222e6426c09e63284Ted Kremenekprivate:
1015eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  void printAux(raw_ostream &Out, bool printLocations,
1025eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek                const char *NL, const char *Sep) const;
1038133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek};
1041eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
1058133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenekclass EnvironmentManager {
1068133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenekprivate:
1078133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  typedef Environment::BindingsTy::Factory FactoryTy;
1088133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  FactoryTy F;
1091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
1101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumppublic:
1118133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  EnvironmentManager(llvm::BumpPtrAllocator& Allocator) : F(Allocator) {}
1128133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  ~EnvironmentManager() {}
1131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
114c179a7fbb294fe3ff6cf5479f6239a10f39628c7Zhongxing Xu  Environment getInitialEnvironment() {
1153baf672378f105602d2b12f03f00277ae1936fe9Ted Kremenek    return Environment(F.getEmptyMap());
1168133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek  }
1171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
1185eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  /// Bind a symbolic value to the given environment entry.
1195eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  Environment bindExpr(Environment Env, const EnvironmentEntry &E, SVal V,
1200fb0bc4067d6c9d7c0e655300ef309b05d3adfc9Ted Kremenek                       bool Invalidate);
1216d4c022695c2d780ccb63ce43a50588412b80813Ted Kremenek
1225eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  /// Bind the location 'location' and value 'V' to the specified
1235eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  /// environment entry.
1245eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek  Environment bindExprAndLocation(Environment Env,
1255eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek                                  const EnvironmentEntry &E,
1265eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek                                  SVal location,
1276d4c022695c2d780ccb63ce43a50588412b80813Ted Kremenek                                  SVal V);
128241677a13cc46647a8f5098b3e3239bd9480dca2Ted Kremenek
129db0594bfc013131f88429add4eb653c285fa94fbTed Kremenek  Environment removeDeadBindings(Environment Env,
1305eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek                                 SymbolReaper &SymReaper,
1318bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek                                 ProgramStateRef state);
1328133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek};
1331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump
1345a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis} // end GR namespace
1355a4f98ff943e6a501b0fe47ade007c9bbf96cb88Argyrios Kyrtzidis
1368133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek} // end clang namespace
1378133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek
1388133a26c166be89fb4f0a339db1e2fe923c51a70Ted Kremenek#endif
139