1 //===- CallDescription.h - function/method call matching       --*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file This file defines a generic mechanism for matching for function and
10 /// method calls of C, C++, and Objective-C languages. Instances of these
11 /// classes are frequently used together with the CallEvent classes.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CALLDESCRIPTION_H
16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CALLDESCRIPTION_H
17 
18 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
19 #include "llvm/ADT/ArrayRef.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/Support/Compiler.h"
22 #include <vector>
23 
24 namespace clang {
25 class IdentifierInfo;
26 } // namespace clang
27 
28 namespace clang {
29 namespace ento {
30 
31 enum CallDescriptionFlags : unsigned {
32   CDF_None = 0,
33 
34   /// Describes a C standard function that is sometimes implemented as a macro
35   /// that expands to a compiler builtin with some __builtin prefix.
36   /// The builtin may as well have a few extra arguments on top of the requested
37   /// number of arguments.
38   CDF_MaybeBuiltin = 1 << 0,
39 };
40 
41 /// This class represents a description of a function call using the number of
42 /// arguments and the name of the function.
43 class CallDescription {
44   friend class CallEvent;
45   using MaybeCount = Optional<unsigned>;
46 
47   mutable Optional<const IdentifierInfo *> II;
48   // The list of the qualified names used to identify the specified CallEvent,
49   // e.g. "{a, b}" represent the qualified names, like "a::b".
50   std::vector<std::string> QualifiedName;
51   MaybeCount RequiredArgs;
52   MaybeCount RequiredParams;
53   int Flags;
54 
55 public:
56   /// Constructs a CallDescription object.
57   ///
58   /// @param QualifiedName The list of the name qualifiers of the function that
59   /// will be matched. The user is allowed to skip any of the qualifiers.
60   /// For example, {"std", "basic_string", "c_str"} would match both
61   /// std::basic_string<...>::c_str() and std::__1::basic_string<...>::c_str().
62   ///
63   /// @param RequiredArgs The number of arguments that is expected to match a
64   /// call. Omit this parameter to match every occurrence of call with a given
65   /// name regardless the number of arguments.
66   CallDescription(CallDescriptionFlags Flags,
67                   ArrayRef<const char *> QualifiedName,
68                   MaybeCount RequiredArgs = None,
69                   MaybeCount RequiredParams = None);
70 
71   /// Construct a CallDescription with default flags.
72   CallDescription(ArrayRef<const char *> QualifiedName,
73                   MaybeCount RequiredArgs = None,
74                   MaybeCount RequiredParams = None);
75 
76   CallDescription(std::nullptr_t) = delete;
77 
78   /// Get the name of the function that this object matches.
79   StringRef getFunctionName() const { return QualifiedName.back(); }
80 
81   /// Get the qualified name parts in reversed order.
82   /// E.g. { "std", "vector", "data" } -> "vector", "std"
83   auto begin_qualified_name_parts() const {
84     return std::next(QualifiedName.rbegin());
85   }
86   auto end_qualified_name_parts() const { return QualifiedName.rend(); }
87 
88   /// It's false, if and only if we expect a single identifier, such as
89   /// `getenv`. It's true for `std::swap`, or `my::detail::container::data`.
90   bool hasQualifiedNameParts() const { return QualifiedName.size() > 1; }
91 
92   /// @name Matching CallDescriptions against a CallEvent
93   /// @{
94 
95   /// Returns true if the CallEvent is a call to a function that matches
96   /// the CallDescription.
97   ///
98   /// \note This function is not intended to be used to match Obj-C method
99   /// calls.
100   bool matches(const CallEvent &Call) const;
101 
102   /// Returns true whether the CallEvent matches on any of the CallDescriptions
103   /// supplied.
104   ///
105   /// \note This function is not intended to be used to match Obj-C method
106   /// calls.
107   friend bool matchesAny(const CallEvent &Call, const CallDescription &CD1) {
108     return CD1.matches(Call);
109   }
110 
111   /// \copydoc clang::ento::matchesAny(const CallEvent &, const CallDescription &)
112   template <typename... Ts>
113   friend bool matchesAny(const CallEvent &Call, const CallDescription &CD1,
114                          const Ts &...CDs) {
115     return CD1.matches(Call) || matchesAny(Call, CDs...);
116   }
117   /// @}
118 };
119 
120 /// An immutable map from CallDescriptions to arbitrary data. Provides a unified
121 /// way for checkers to react on function calls.
122 template <typename T> class CallDescriptionMap {
123   friend class CallDescriptionSet;
124 
125   // Some call descriptions aren't easily hashable (eg., the ones with qualified
126   // names in which some sections are omitted), so let's put them
127   // in a simple vector and use linear lookup.
128   // TODO: Implement an actual map for fast lookup for "hashable" call
129   // descriptions (eg., the ones for C functions that just match the name).
130   std::vector<std::pair<CallDescription, T>> LinearMap;
131 
132 public:
133   CallDescriptionMap(
134       std::initializer_list<std::pair<CallDescription, T>> &&List)
135       : LinearMap(List) {}
136 
137   template <typename InputIt>
138   CallDescriptionMap(InputIt First, InputIt Last) : LinearMap(First, Last) {}
139 
140   ~CallDescriptionMap() = default;
141 
142   // These maps are usually stored once per checker, so let's make sure
143   // we don't do redundant copies.
144   CallDescriptionMap(const CallDescriptionMap &) = delete;
145   CallDescriptionMap &operator=(const CallDescription &) = delete;
146 
147   CallDescriptionMap(CallDescriptionMap &&) = default;
148   CallDescriptionMap &operator=(CallDescriptionMap &&) = default;
149 
150   LLVM_NODISCARD const T *lookup(const CallEvent &Call) const {
151     // Slow path: linear lookup.
152     // TODO: Implement some sort of fast path.
153     for (const std::pair<CallDescription, T> &I : LinearMap)
154       if (I.first.matches(Call))
155         return &I.second;
156 
157     return nullptr;
158   }
159 };
160 
161 /// An immutable set of CallDescriptions.
162 /// Checkers can efficiently decide if a given CallEvent matches any
163 /// CallDescription in the set.
164 class CallDescriptionSet {
165   CallDescriptionMap<bool /*unused*/> Impl = {};
166 
167 public:
168   CallDescriptionSet(std::initializer_list<CallDescription> &&List);
169 
170   CallDescriptionSet(const CallDescriptionSet &) = delete;
171   CallDescriptionSet &operator=(const CallDescription &) = delete;
172 
173   LLVM_NODISCARD bool contains(const CallEvent &Call) const;
174 };
175 
176 } // namespace ento
177 } // namespace clang
178 
179 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_CALLDESCRIPTION_H
180