Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 1 | //===----- UninitializedObjectChecker.cpp ------------------------*- 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 file defines a checker that reports uninitialized fields in objects |
| 11 | // created after a constructor call. |
| 12 | // |
Kristof Umann | a3f7b58 | 2018-08-07 12:55:26 +0000 | [diff] [blame] | 13 | // This checker has several options: |
Kristof Umann | 9bd4439 | 2018-06-29 11:25:24 +0000 | [diff] [blame] | 14 | // - "Pedantic" (boolean). If its not set or is set to false, the checker |
| 15 | // won't emit warnings for objects that don't have at least one initialized |
| 16 | // field. This may be set with |
| 17 | // |
Kristof Umann | a3f7b58 | 2018-08-07 12:55:26 +0000 | [diff] [blame] | 18 | // `-analyzer-config alpha.cplusplus.UninitializedObject:Pedantic=true`. |
Kristof Umann | 9bd4439 | 2018-06-29 11:25:24 +0000 | [diff] [blame] | 19 | // |
| 20 | // - "NotesAsWarnings" (boolean). If set to true, the checker will emit a |
| 21 | // warning for each uninitalized field, as opposed to emitting one warning |
| 22 | // per constructor call, and listing the uninitialized fields that belongs |
| 23 | // to it in notes. Defaults to false. |
| 24 | // |
Kristof Umann | a3f7b58 | 2018-08-07 12:55:26 +0000 | [diff] [blame] | 25 | // `-analyzer-config \ |
| 26 | // alpha.cplusplus.UninitializedObject:NotesAsWarnings=true`. |
| 27 | // |
| 28 | // - "CheckPointeeInitialization" (boolean). If set to false, the checker will |
| 29 | // not analyze the pointee of pointer/reference fields, and will only check |
| 30 | // whether the object itself is initialized. Defaults to false. |
| 31 | // |
| 32 | // `-analyzer-config \ |
| 33 | // alpha.cplusplus.UninitializedObject:CheckPointeeInitialization=true`. |
| 34 | // |
| 35 | // TODO: With some clever heuristics, some pointers should be dereferenced |
| 36 | // by default. For example, if the pointee is constructed within the |
| 37 | // constructor call, it's reasonable to say that no external object |
| 38 | // references it, and we wouldn't generate multiple report on the same |
| 39 | // pointee. |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 40 | // |
| 41 | //===----------------------------------------------------------------------===// |
| 42 | |
| 43 | #include "ClangSACheckers.h" |
| 44 | #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" |
| 45 | #include "clang/StaticAnalyzer/Core/Checker.h" |
| 46 | #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 47 | #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h" |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 48 | |
| 49 | using namespace clang; |
| 50 | using namespace clang::ento; |
| 51 | |
| 52 | namespace { |
| 53 | |
| 54 | class UninitializedObjectChecker : public Checker<check::EndFunction> { |
| 55 | std::unique_ptr<BuiltinBug> BT_uninitField; |
| 56 | |
| 57 | public: |
Kristof Umann | 9bd4439 | 2018-06-29 11:25:24 +0000 | [diff] [blame] | 58 | // These fields will be initialized when registering the checker. |
| 59 | bool IsPedantic; |
| 60 | bool ShouldConvertNotesToWarnings; |
Kristof Umann | a3f7b58 | 2018-08-07 12:55:26 +0000 | [diff] [blame] | 61 | bool CheckPointeeInitialization; |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 62 | |
| 63 | UninitializedObjectChecker() |
| 64 | : BT_uninitField(new BuiltinBug(this, "Uninitialized fields")) {} |
Reka Kovacs | ed8c05c | 2018-07-16 20:47:45 +0000 | [diff] [blame] | 65 | void checkEndFunction(const ReturnStmt *RS, CheckerContext &C) const; |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 66 | }; |
| 67 | |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 68 | /// Represents a field chain. A field chain is a vector of fields where the |
| 69 | /// first element of the chain is the object under checking (not stored), and |
| 70 | /// every other element is a field, and the element that precedes it is the |
| 71 | /// object that contains it. |
| 72 | /// |
| 73 | /// Note that this class is immutable, and new fields may only be added through |
| 74 | /// constructor calls. |
| 75 | class FieldChainInfo { |
| 76 | using FieldChain = llvm::ImmutableList<const FieldRegion *>; |
| 77 | |
| 78 | FieldChain Chain; |
| 79 | |
| 80 | const bool IsDereferenced = false; |
| 81 | |
| 82 | public: |
| 83 | FieldChainInfo() = default; |
| 84 | |
| 85 | FieldChainInfo(const FieldChainInfo &Other, const bool IsDereferenced) |
| 86 | : Chain(Other.Chain), IsDereferenced(IsDereferenced) {} |
| 87 | |
| 88 | FieldChainInfo(const FieldChainInfo &Other, const FieldRegion *FR, |
| 89 | const bool IsDereferenced = false); |
| 90 | |
| 91 | bool contains(const FieldRegion *FR) const { return Chain.contains(FR); } |
| 92 | bool isPointer() const; |
| 93 | |
| 94 | /// If this is a fieldchain whose last element is an uninitialized region of a |
| 95 | /// pointer type, `IsDereferenced` will store whether the pointer itself or |
| 96 | /// the pointee is uninitialized. |
| 97 | bool isDereferenced() const; |
| 98 | const FieldDecl *getEndOfChain() const; |
| 99 | void print(llvm::raw_ostream &Out) const; |
| 100 | |
| 101 | private: |
| 102 | /// Prints every element except the last to `Out`. Since ImmutableLists store |
| 103 | /// elements in reverse order, and have no reverse iterators, we use a |
| 104 | /// recursive function to print the fieldchain correctly. The last element in |
| 105 | /// the chain is to be printed by `print`. |
| 106 | static void printTail(llvm::raw_ostream &Out, |
| 107 | const llvm::ImmutableListImpl<const FieldRegion *> *L); |
| 108 | friend struct FieldChainInfoComparator; |
| 109 | }; |
| 110 | |
| 111 | struct FieldChainInfoComparator { |
Steven Wu | b3684db | 2018-06-22 16:51:17 +0000 | [diff] [blame] | 112 | bool operator()(const FieldChainInfo &lhs, const FieldChainInfo &rhs) const { |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 113 | assert(!lhs.Chain.isEmpty() && !rhs.Chain.isEmpty() && |
| 114 | "Attempted to store an empty fieldchain!"); |
| 115 | return *lhs.Chain.begin() < *rhs.Chain.begin(); |
| 116 | } |
| 117 | }; |
| 118 | |
| 119 | using UninitFieldSet = std::set<FieldChainInfo, FieldChainInfoComparator>; |
| 120 | |
| 121 | /// Searches for and stores uninitialized fields in a non-union object. |
| 122 | class FindUninitializedFields { |
| 123 | ProgramStateRef State; |
| 124 | const TypedValueRegion *const ObjectR; |
| 125 | |
| 126 | const bool IsPedantic; |
Kristof Umann | a3f7b58 | 2018-08-07 12:55:26 +0000 | [diff] [blame] | 127 | const bool CheckPointeeInitialization; |
| 128 | |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 129 | bool IsAnyFieldInitialized = false; |
| 130 | |
| 131 | UninitFieldSet UninitFields; |
| 132 | |
| 133 | public: |
| 134 | FindUninitializedFields(ProgramStateRef State, |
Kristof Umann | a3f7b58 | 2018-08-07 12:55:26 +0000 | [diff] [blame] | 135 | const TypedValueRegion *const R, bool IsPedantic, |
| 136 | bool CheckPointeeInitialization); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 137 | const UninitFieldSet &getUninitFields(); |
| 138 | |
| 139 | private: |
| 140 | /// Adds a FieldChainInfo object to UninitFields. Return true if an insertion |
| 141 | /// took place. |
| 142 | bool addFieldToUninits(FieldChainInfo LocalChain); |
| 143 | |
| 144 | // For the purposes of this checker, we'll regard the object under checking as |
| 145 | // a directed tree, where |
| 146 | // * the root is the object under checking |
| 147 | // * every node is an object that is |
| 148 | // - a union |
| 149 | // - a non-union record |
| 150 | // - a pointer/reference |
| 151 | // - an array |
Kristof Umann | 7212cc0 | 2018-07-13 12:21:38 +0000 | [diff] [blame] | 152 | // - of a primitive type, which we'll define later in a helper function. |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 153 | // * the parent of each node is the object that contains it |
Kristof Umann | 7212cc0 | 2018-07-13 12:21:38 +0000 | [diff] [blame] | 154 | // * every leaf is an array, a primitive object, a nullptr or an undefined |
| 155 | // pointer. |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 156 | // |
| 157 | // Example: |
| 158 | // |
| 159 | // struct A { |
| 160 | // struct B { |
| 161 | // int x, y = 0; |
| 162 | // }; |
| 163 | // B b; |
| 164 | // int *iptr = new int; |
| 165 | // B* bptr; |
| 166 | // |
| 167 | // A() {} |
| 168 | // }; |
| 169 | // |
| 170 | // The directed tree: |
| 171 | // |
| 172 | // ->x |
| 173 | // / |
| 174 | // ->b--->y |
| 175 | // / |
| 176 | // A-->iptr->(int value) |
| 177 | // \ |
| 178 | // ->bptr |
| 179 | // |
| 180 | // From this we'll construct a vector of fieldchains, where each fieldchain |
| 181 | // represents an uninitialized field. An uninitialized field may be a |
Kristof Umann | 7212cc0 | 2018-07-13 12:21:38 +0000 | [diff] [blame] | 182 | // primitive object, a pointer, a pointee or a union without a single |
| 183 | // initialized field. |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 184 | // In the above example, for the default constructor call we'll end up with |
| 185 | // these fieldchains: |
| 186 | // |
| 187 | // this->b.x |
| 188 | // this->iptr (pointee uninit) |
| 189 | // this->bptr (pointer uninit) |
| 190 | // |
| 191 | // We'll traverse each node of the above graph with the appropiate one of |
| 192 | // these methods: |
| 193 | |
| 194 | /// This method checks a region of a union object, and returns true if no |
| 195 | /// field is initialized within the region. |
| 196 | bool isUnionUninit(const TypedValueRegion *R); |
| 197 | |
| 198 | /// This method checks a region of a non-union object, and returns true if |
| 199 | /// an uninitialized field is found within the region. |
| 200 | bool isNonUnionUninit(const TypedValueRegion *R, FieldChainInfo LocalChain); |
| 201 | |
| 202 | /// This method checks a region of a pointer or reference object, and returns |
| 203 | /// true if the ptr/ref object itself or any field within the pointee's region |
| 204 | /// is uninitialized. |
| 205 | bool isPointerOrReferenceUninit(const FieldRegion *FR, |
| 206 | FieldChainInfo LocalChain); |
| 207 | |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 208 | /// This method returns true if the value of a primitive object is |
| 209 | /// uninitialized. |
| 210 | bool isPrimitiveUninit(const SVal &V); |
| 211 | |
| 212 | // Note that we don't have a method for arrays -- the elements of an array are |
| 213 | // often left uninitialized intentionally even when it is of a C++ record |
| 214 | // type, so we'll assume that an array is always initialized. |
| 215 | // TODO: Add a support for nonloc::LocAsInteger. |
| 216 | }; |
| 217 | |
Kristof Umann | cc85244 | 2018-07-12 13:13:46 +0000 | [diff] [blame] | 218 | } // end of anonymous namespace |
| 219 | |
| 220 | // Static variable instantionations. |
| 221 | |
| 222 | static llvm::ImmutableListFactory<const FieldRegion *> Factory; |
| 223 | |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 224 | // Utility function declarations. |
| 225 | |
| 226 | /// Returns the object that was constructed by CtorDecl, or None if that isn't |
| 227 | /// possible. |
Kristof Umann | 0735cfb | 2018-08-08 12:23:02 +0000 | [diff] [blame] | 228 | // TODO: Refactor this function so that it returns the constructed object's |
| 229 | // region. |
Kristof Umann | cc85244 | 2018-07-12 13:13:46 +0000 | [diff] [blame] | 230 | static Optional<nonloc::LazyCompoundVal> |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 231 | getObjectVal(const CXXConstructorDecl *CtorDecl, CheckerContext &Context); |
| 232 | |
Kristof Umann | 0735cfb | 2018-08-08 12:23:02 +0000 | [diff] [blame] | 233 | /// Checks whether the object constructed by \p Ctor will be analyzed later |
| 234 | /// (e.g. if the object is a field of another object, in which case we'd check |
| 235 | /// it multiple times). |
| 236 | static bool willObjectBeAnalyzedLater(const CXXConstructorDecl *Ctor, |
| 237 | CheckerContext &Context); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 238 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 239 | /// Returns whether T can be (transitively) dereferenced to a void pointer type |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 240 | /// (void*, void**, ...). The type of the region behind a void pointer isn't |
| 241 | /// known, and thus FD can not be analyzed. |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 242 | static bool isVoidPointer(QualType T); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 243 | |
Kristof Umann | 7212cc0 | 2018-07-13 12:21:38 +0000 | [diff] [blame] | 244 | /// Returns true if T is a primitive type. We defined this type so that for |
| 245 | /// objects that we'd only like analyze as much as checking whether their |
| 246 | /// value is undefined or not, such as ints and doubles, can be analyzed with |
| 247 | /// ease. This also helps ensuring that every special field type is handled |
| 248 | /// correctly. |
Kristof Umann | cc85244 | 2018-07-12 13:13:46 +0000 | [diff] [blame] | 249 | static bool isPrimitiveType(const QualType &T) { |
Kristof Umann | 7212cc0 | 2018-07-13 12:21:38 +0000 | [diff] [blame] | 250 | return T->isBuiltinType() || T->isEnumeralType() || T->isMemberPointerType(); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 251 | } |
| 252 | |
Kristof Umann | 9bd4439 | 2018-06-29 11:25:24 +0000 | [diff] [blame] | 253 | /// Constructs a note message for a given FieldChainInfo object. |
Kristof Umann | cc85244 | 2018-07-12 13:13:46 +0000 | [diff] [blame] | 254 | static void printNoteMessage(llvm::raw_ostream &Out, |
| 255 | const FieldChainInfo &Chain); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 256 | |
Kristof Umann | 8c11909 | 2018-07-13 12:54:47 +0000 | [diff] [blame] | 257 | /// Returns with Field's name. This is a helper function to get the correct name |
| 258 | /// even if Field is a captured lambda variable. |
| 259 | static StringRef getVariableName(const FieldDecl *Field); |
| 260 | |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 261 | //===----------------------------------------------------------------------===// |
| 262 | // Methods for UninitializedObjectChecker. |
| 263 | //===----------------------------------------------------------------------===// |
| 264 | |
| 265 | void UninitializedObjectChecker::checkEndFunction( |
Reka Kovacs | ed8c05c | 2018-07-16 20:47:45 +0000 | [diff] [blame] | 266 | const ReturnStmt *RS, CheckerContext &Context) const { |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 267 | |
| 268 | const auto *CtorDecl = dyn_cast_or_null<CXXConstructorDecl>( |
| 269 | Context.getLocationContext()->getDecl()); |
| 270 | if (!CtorDecl) |
| 271 | return; |
| 272 | |
| 273 | if (!CtorDecl->isUserProvided()) |
| 274 | return; |
| 275 | |
| 276 | if (CtorDecl->getParent()->isUnion()) |
| 277 | return; |
| 278 | |
| 279 | // This avoids essentially the same error being reported multiple times. |
Kristof Umann | 0735cfb | 2018-08-08 12:23:02 +0000 | [diff] [blame] | 280 | if (willObjectBeAnalyzedLater(CtorDecl, Context)) |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 281 | return; |
| 282 | |
| 283 | Optional<nonloc::LazyCompoundVal> Object = getObjectVal(CtorDecl, Context); |
| 284 | if (!Object) |
| 285 | return; |
| 286 | |
Kristof Umann | a3f7b58 | 2018-08-07 12:55:26 +0000 | [diff] [blame] | 287 | FindUninitializedFields F(Context.getState(), Object->getRegion(), IsPedantic, |
| 288 | CheckPointeeInitialization); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 289 | |
| 290 | const UninitFieldSet &UninitFields = F.getUninitFields(); |
| 291 | |
| 292 | if (UninitFields.empty()) |
| 293 | return; |
| 294 | |
| 295 | // There are uninitialized fields in the record. |
| 296 | |
| 297 | ExplodedNode *Node = Context.generateNonFatalErrorNode(Context.getState()); |
| 298 | if (!Node) |
| 299 | return; |
| 300 | |
| 301 | PathDiagnosticLocation LocUsedForUniqueing; |
| 302 | const Stmt *CallSite = Context.getStackFrame()->getCallSite(); |
| 303 | if (CallSite) |
| 304 | LocUsedForUniqueing = PathDiagnosticLocation::createBegin( |
| 305 | CallSite, Context.getSourceManager(), Node->getLocationContext()); |
| 306 | |
Kristof Umann | 9bd4439 | 2018-06-29 11:25:24 +0000 | [diff] [blame] | 307 | // For Plist consumers that don't support notes just yet, we'll convert notes |
| 308 | // to warnings. |
| 309 | if (ShouldConvertNotesToWarnings) { |
| 310 | for (const auto &Chain : UninitFields) { |
| 311 | SmallString<100> WarningBuf; |
| 312 | llvm::raw_svector_ostream WarningOS(WarningBuf); |
| 313 | |
| 314 | printNoteMessage(WarningOS, Chain); |
| 315 | |
| 316 | auto Report = llvm::make_unique<BugReport>( |
| 317 | *BT_uninitField, WarningOS.str(), Node, LocUsedForUniqueing, |
| 318 | Node->getLocationContext()->getDecl()); |
| 319 | Context.emitReport(std::move(Report)); |
| 320 | } |
| 321 | return; |
| 322 | } |
| 323 | |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 324 | SmallString<100> WarningBuf; |
| 325 | llvm::raw_svector_ostream WarningOS(WarningBuf); |
| 326 | WarningOS << UninitFields.size() << " uninitialized field" |
| 327 | << (UninitFields.size() == 1 ? "" : "s") |
| 328 | << " at the end of the constructor call"; |
| 329 | |
| 330 | auto Report = llvm::make_unique<BugReport>( |
| 331 | *BT_uninitField, WarningOS.str(), Node, LocUsedForUniqueing, |
| 332 | Node->getLocationContext()->getDecl()); |
| 333 | |
Kristof Umann | 9bd4439 | 2018-06-29 11:25:24 +0000 | [diff] [blame] | 334 | for (const auto &Chain : UninitFields) { |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 335 | SmallString<200> NoteBuf; |
| 336 | llvm::raw_svector_ostream NoteOS(NoteBuf); |
| 337 | |
Kristof Umann | 9bd4439 | 2018-06-29 11:25:24 +0000 | [diff] [blame] | 338 | printNoteMessage(NoteOS, Chain); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 339 | |
| 340 | Report->addNote(NoteOS.str(), |
Kristof Umann | 9bd4439 | 2018-06-29 11:25:24 +0000 | [diff] [blame] | 341 | PathDiagnosticLocation::create(Chain.getEndOfChain(), |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 342 | Context.getSourceManager())); |
| 343 | } |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 344 | Context.emitReport(std::move(Report)); |
| 345 | } |
| 346 | |
| 347 | //===----------------------------------------------------------------------===// |
| 348 | // Methods for FindUninitializedFields. |
| 349 | //===----------------------------------------------------------------------===// |
| 350 | |
| 351 | FindUninitializedFields::FindUninitializedFields( |
Kristof Umann | a3f7b58 | 2018-08-07 12:55:26 +0000 | [diff] [blame] | 352 | ProgramStateRef State, const TypedValueRegion *const R, bool IsPedantic, |
| 353 | bool CheckPointeeInitialization) |
| 354 | : State(State), ObjectR(R), IsPedantic(IsPedantic), |
| 355 | CheckPointeeInitialization(CheckPointeeInitialization) {} |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 356 | |
| 357 | const UninitFieldSet &FindUninitializedFields::getUninitFields() { |
| 358 | isNonUnionUninit(ObjectR, FieldChainInfo()); |
| 359 | |
| 360 | if (!IsPedantic && !IsAnyFieldInitialized) |
| 361 | UninitFields.clear(); |
| 362 | |
| 363 | return UninitFields; |
| 364 | } |
| 365 | |
| 366 | bool FindUninitializedFields::addFieldToUninits(FieldChainInfo Chain) { |
| 367 | if (State->getStateManager().getContext().getSourceManager().isInSystemHeader( |
| 368 | Chain.getEndOfChain()->getLocation())) |
| 369 | return false; |
| 370 | |
| 371 | return UninitFields.insert(Chain).second; |
| 372 | } |
| 373 | |
| 374 | bool FindUninitializedFields::isNonUnionUninit(const TypedValueRegion *R, |
| 375 | FieldChainInfo LocalChain) { |
| 376 | assert(R->getValueType()->isRecordType() && |
| 377 | !R->getValueType()->isUnionType() && |
| 378 | "This method only checks non-union record objects!"); |
| 379 | |
| 380 | const RecordDecl *RD = |
| 381 | R->getValueType()->getAs<RecordType>()->getDecl()->getDefinition(); |
| 382 | assert(RD && "Referred record has no definition"); |
| 383 | |
| 384 | bool ContainsUninitField = false; |
| 385 | |
| 386 | // Are all of this non-union's fields initialized? |
| 387 | for (const FieldDecl *I : RD->fields()) { |
| 388 | |
| 389 | const auto FieldVal = |
| 390 | State->getLValue(I, loc::MemRegionVal(R)).castAs<loc::MemRegionVal>(); |
| 391 | const auto *FR = FieldVal.getRegionAs<FieldRegion>(); |
| 392 | QualType T = I->getType(); |
| 393 | |
| 394 | // If LocalChain already contains FR, then we encountered a cyclic |
| 395 | // reference. In this case, region FR is already under checking at an |
| 396 | // earlier node in the directed tree. |
| 397 | if (LocalChain.contains(FR)) |
| 398 | return false; |
| 399 | |
| 400 | if (T->isStructureOrClassType()) { |
| 401 | if (isNonUnionUninit(FR, {LocalChain, FR})) |
| 402 | ContainsUninitField = true; |
| 403 | continue; |
| 404 | } |
| 405 | |
| 406 | if (T->isUnionType()) { |
| 407 | if (isUnionUninit(FR)) { |
| 408 | if (addFieldToUninits({LocalChain, FR})) |
| 409 | ContainsUninitField = true; |
| 410 | } else |
| 411 | IsAnyFieldInitialized = true; |
| 412 | continue; |
| 413 | } |
| 414 | |
| 415 | if (T->isArrayType()) { |
| 416 | IsAnyFieldInitialized = true; |
| 417 | continue; |
| 418 | } |
| 419 | |
George Karpenkov | cf40ba8 | 2018-08-09 19:03:12 +0000 | [diff] [blame^] | 420 | if (T->isPointerType() || T->isReferenceType() || T->isBlockPointerType()) { |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 421 | if (isPointerOrReferenceUninit(FR, LocalChain)) |
| 422 | ContainsUninitField = true; |
| 423 | continue; |
| 424 | } |
| 425 | |
Kristof Umann | 20e85ba | 2018-06-19 08:35:02 +0000 | [diff] [blame] | 426 | if (isPrimitiveType(T)) { |
| 427 | SVal V = State->getSVal(FieldVal); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 428 | |
Kristof Umann | 20e85ba | 2018-06-19 08:35:02 +0000 | [diff] [blame] | 429 | if (isPrimitiveUninit(V)) { |
| 430 | if (addFieldToUninits({LocalChain, FR})) |
| 431 | ContainsUninitField = true; |
| 432 | } |
| 433 | continue; |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 434 | } |
Kristof Umann | 20e85ba | 2018-06-19 08:35:02 +0000 | [diff] [blame] | 435 | |
| 436 | llvm_unreachable("All cases are handled!"); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 437 | } |
| 438 | |
| 439 | // Checking bases. |
Kristof Umann | 0735cfb | 2018-08-08 12:23:02 +0000 | [diff] [blame] | 440 | // FIXME: As of now, because of `willObjectBeAnalyzedLater`, objects whose |
| 441 | // type is a descendant of another type will emit warnings for uninitalized |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 442 | // inherited members. |
| 443 | // This is not the only way to analyze bases of an object -- if we didn't |
| 444 | // filter them out, and didn't analyze the bases, this checker would run for |
| 445 | // each base of the object in order of base initailization and in theory would |
| 446 | // find every uninitalized field. This approach could also make handling |
| 447 | // diamond inheritances more easily. |
| 448 | // |
| 449 | // This rule (that a descendant type's cunstructor is responsible for |
| 450 | // initializing inherited data members) is not obvious, and should it should |
| 451 | // be. |
| 452 | const auto *CXXRD = dyn_cast<CXXRecordDecl>(RD); |
| 453 | if (!CXXRD) |
| 454 | return ContainsUninitField; |
| 455 | |
| 456 | for (const CXXBaseSpecifier &BaseSpec : CXXRD->bases()) { |
| 457 | const auto *BaseRegion = State->getLValue(BaseSpec, R) |
| 458 | .castAs<loc::MemRegionVal>() |
| 459 | .getRegionAs<TypedValueRegion>(); |
| 460 | |
| 461 | if (isNonUnionUninit(BaseRegion, LocalChain)) |
| 462 | ContainsUninitField = true; |
| 463 | } |
| 464 | |
| 465 | return ContainsUninitField; |
| 466 | } |
| 467 | |
| 468 | bool FindUninitializedFields::isUnionUninit(const TypedValueRegion *R) { |
| 469 | assert(R->getValueType()->isUnionType() && |
| 470 | "This method only checks union objects!"); |
| 471 | // TODO: Implement support for union fields. |
| 472 | return false; |
| 473 | } |
| 474 | |
| 475 | // Note that pointers/references don't contain fields themselves, so in this |
| 476 | // function we won't add anything to LocalChain. |
| 477 | bool FindUninitializedFields::isPointerOrReferenceUninit( |
| 478 | const FieldRegion *FR, FieldChainInfo LocalChain) { |
| 479 | |
| 480 | assert((FR->getDecl()->getType()->isPointerType() || |
George Karpenkov | cf40ba8 | 2018-08-09 19:03:12 +0000 | [diff] [blame^] | 481 | FR->getDecl()->getType()->isReferenceType() || |
| 482 | FR->getDecl()->getType()->isBlockPointerType()) && |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 483 | "This method only checks pointer/reference objects!"); |
| 484 | |
| 485 | SVal V = State->getSVal(FR); |
| 486 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 487 | if (V.isUnknown() || V.getAs<loc::ConcreteInt>()) { |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 488 | IsAnyFieldInitialized = true; |
| 489 | return false; |
| 490 | } |
| 491 | |
| 492 | if (V.isUndef()) { |
| 493 | return addFieldToUninits({LocalChain, FR}); |
| 494 | } |
| 495 | |
Kristof Umann | a3f7b58 | 2018-08-07 12:55:26 +0000 | [diff] [blame] | 496 | if (!CheckPointeeInitialization) { |
| 497 | IsAnyFieldInitialized = true; |
| 498 | return false; |
| 499 | } |
| 500 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 501 | assert(V.getAs<loc::MemRegionVal>() && |
| 502 | "At this point V must be loc::MemRegionVal!"); |
| 503 | auto L = V.castAs<loc::MemRegionVal>(); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 504 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 505 | // We can't reason about symbolic regions, assume its initialized. |
| 506 | // Note that this also avoids a potential infinite recursion, because |
| 507 | // constructors for list-like classes are checked without being called, and |
| 508 | // the Static Analyzer will construct a symbolic region for Node *next; or |
| 509 | // similar code snippets. |
| 510 | if (L.getRegion()->getSymbolicBase()) { |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 511 | IsAnyFieldInitialized = true; |
| 512 | return false; |
| 513 | } |
| 514 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 515 | DynamicTypeInfo DynTInfo = getDynamicTypeInfo(State, L.getRegion()); |
| 516 | if (!DynTInfo.isValid()) { |
| 517 | IsAnyFieldInitialized = true; |
| 518 | return false; |
| 519 | } |
| 520 | |
| 521 | QualType DynT = DynTInfo.getType(); |
| 522 | |
| 523 | if (isVoidPointer(DynT)) { |
| 524 | IsAnyFieldInitialized = true; |
| 525 | return false; |
| 526 | } |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 527 | |
| 528 | // At this point the pointer itself is initialized and points to a valid |
| 529 | // location, we'll now check the pointee. |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 530 | SVal DerefdV = State->getSVal(V.castAs<Loc>(), DynT); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 531 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 532 | // If DerefdV is still a pointer value, we'll dereference it again (e.g.: |
| 533 | // int** -> int*). |
| 534 | while (auto Tmp = DerefdV.getAs<loc::MemRegionVal>()) { |
| 535 | if (Tmp->getRegion()->getSymbolicBase()) { |
| 536 | IsAnyFieldInitialized = true; |
| 537 | return false; |
| 538 | } |
| 539 | |
| 540 | DynTInfo = getDynamicTypeInfo(State, Tmp->getRegion()); |
| 541 | if (!DynTInfo.isValid()) { |
| 542 | IsAnyFieldInitialized = true; |
| 543 | return false; |
| 544 | } |
| 545 | |
| 546 | DynT = DynTInfo.getType(); |
| 547 | if (isVoidPointer(DynT)) { |
| 548 | IsAnyFieldInitialized = true; |
| 549 | return false; |
| 550 | } |
| 551 | |
| 552 | DerefdV = State->getSVal(*Tmp, DynT); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 553 | } |
| 554 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 555 | // If FR is a pointer pointing to a non-primitive type. |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 556 | if (Optional<nonloc::LazyCompoundVal> RecordV = |
| 557 | DerefdV.getAs<nonloc::LazyCompoundVal>()) { |
| 558 | |
| 559 | const TypedValueRegion *R = RecordV->getRegion(); |
| 560 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 561 | if (DynT->getPointeeType()->isStructureOrClassType()) |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 562 | return isNonUnionUninit(R, {LocalChain, FR}); |
| 563 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 564 | if (DynT->getPointeeType()->isUnionType()) { |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 565 | if (isUnionUninit(R)) { |
| 566 | return addFieldToUninits({LocalChain, FR, /*IsDereferenced*/ true}); |
| 567 | } else { |
| 568 | IsAnyFieldInitialized = true; |
| 569 | return false; |
| 570 | } |
| 571 | } |
| 572 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 573 | if (DynT->getPointeeType()->isArrayType()) { |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 574 | IsAnyFieldInitialized = true; |
| 575 | return false; |
| 576 | } |
| 577 | |
| 578 | llvm_unreachable("All cases are handled!"); |
| 579 | } |
| 580 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 581 | assert((isPrimitiveType(DynT->getPointeeType()) || DynT->isPointerType() || |
| 582 | DynT->isReferenceType()) && |
| 583 | "At this point FR must either have a primitive dynamic type, or it " |
| 584 | "must be a null, undefined, unknown or concrete pointer!"); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 585 | |
| 586 | if (isPrimitiveUninit(DerefdV)) |
| 587 | return addFieldToUninits({LocalChain, FR, /*IsDereferenced*/ true}); |
| 588 | |
| 589 | IsAnyFieldInitialized = true; |
| 590 | return false; |
| 591 | } |
| 592 | |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 593 | bool FindUninitializedFields::isPrimitiveUninit(const SVal &V) { |
| 594 | if (V.isUndef()) |
| 595 | return true; |
| 596 | |
| 597 | IsAnyFieldInitialized = true; |
| 598 | return false; |
| 599 | } |
| 600 | |
| 601 | //===----------------------------------------------------------------------===// |
| 602 | // Methods for FieldChainInfo. |
| 603 | //===----------------------------------------------------------------------===// |
| 604 | |
| 605 | FieldChainInfo::FieldChainInfo(const FieldChainInfo &Other, |
| 606 | const FieldRegion *FR, const bool IsDereferenced) |
| 607 | : FieldChainInfo(Other, IsDereferenced) { |
| 608 | assert(!contains(FR) && "Can't add a field that is already a part of the " |
| 609 | "fieldchain! Is this a cyclic reference?"); |
| 610 | Chain = Factory.add(FR, Other.Chain); |
| 611 | } |
| 612 | |
| 613 | bool FieldChainInfo::isPointer() const { |
| 614 | assert(!Chain.isEmpty() && "Empty fieldchain!"); |
| 615 | return (*Chain.begin())->getDecl()->getType()->isPointerType(); |
| 616 | } |
| 617 | |
| 618 | bool FieldChainInfo::isDereferenced() const { |
| 619 | assert(isPointer() && "Only pointers may or may not be dereferenced!"); |
| 620 | return IsDereferenced; |
| 621 | } |
| 622 | |
| 623 | const FieldDecl *FieldChainInfo::getEndOfChain() const { |
| 624 | assert(!Chain.isEmpty() && "Empty fieldchain!"); |
| 625 | return (*Chain.begin())->getDecl(); |
| 626 | } |
| 627 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 628 | // TODO: This function constructs an incorrect string if a void pointer is a |
| 629 | // part of the chain: |
| 630 | // |
| 631 | // struct B { int x; } |
| 632 | // |
| 633 | // struct A { |
| 634 | // void *vptr; |
| 635 | // A(void* vptr) : vptr(vptr) {} |
| 636 | // }; |
| 637 | // |
| 638 | // void f() { |
| 639 | // B b; |
| 640 | // A a(&b); |
| 641 | // } |
| 642 | // |
| 643 | // The note message will be "uninitialized field 'this->vptr->x'", even though |
| 644 | // void pointers can't be dereferenced. This should be changed to "uninitialized |
| 645 | // field 'static_cast<B*>(this->vptr)->x'". |
| 646 | // |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 647 | // TODO: This function constructs an incorrect fieldchain string in the |
| 648 | // following case: |
| 649 | // |
| 650 | // struct Base { int x; }; |
| 651 | // struct D1 : Base {}; struct D2 : Base {}; |
| 652 | // |
| 653 | // struct MostDerived : D1, D2 { |
| 654 | // MostDerived() {} |
| 655 | // } |
| 656 | // |
| 657 | // A call to MostDerived::MostDerived() will cause two notes that say |
| 658 | // "uninitialized field 'this->x'", but we can't refer to 'x' directly, |
| 659 | // we need an explicit namespace resolution whether the uninit field was |
| 660 | // 'D1::x' or 'D2::x'. |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 661 | void FieldChainInfo::print(llvm::raw_ostream &Out) const { |
| 662 | if (Chain.isEmpty()) |
| 663 | return; |
| 664 | |
| 665 | const llvm::ImmutableListImpl<const FieldRegion *> *L = |
| 666 | Chain.getInternalPointer(); |
| 667 | printTail(Out, L->getTail()); |
Kristof Umann | 8c11909 | 2018-07-13 12:54:47 +0000 | [diff] [blame] | 668 | Out << getVariableName(L->getHead()->getDecl()); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 669 | } |
| 670 | |
| 671 | void FieldChainInfo::printTail( |
| 672 | llvm::raw_ostream &Out, |
| 673 | const llvm::ImmutableListImpl<const FieldRegion *> *L) { |
| 674 | if (!L) |
| 675 | return; |
| 676 | |
| 677 | printTail(Out, L->getTail()); |
| 678 | const FieldDecl *Field = L->getHead()->getDecl(); |
Kristof Umann | 8c11909 | 2018-07-13 12:54:47 +0000 | [diff] [blame] | 679 | Out << getVariableName(Field); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 680 | Out << (Field->getType()->isPointerType() ? "->" : "."); |
| 681 | } |
| 682 | |
| 683 | //===----------------------------------------------------------------------===// |
| 684 | // Utility functions. |
| 685 | //===----------------------------------------------------------------------===// |
| 686 | |
Kristof Umann | ef9af05 | 2018-08-08 13:18:53 +0000 | [diff] [blame] | 687 | static bool isVoidPointer(QualType T) { |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 688 | while (!T.isNull()) { |
| 689 | if (T->isVoidPointerType()) |
| 690 | return true; |
| 691 | T = T->getPointeeType(); |
| 692 | } |
| 693 | return false; |
| 694 | } |
| 695 | |
Kristof Umann | cc85244 | 2018-07-12 13:13:46 +0000 | [diff] [blame] | 696 | static Optional<nonloc::LazyCompoundVal> |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 697 | getObjectVal(const CXXConstructorDecl *CtorDecl, CheckerContext &Context) { |
| 698 | |
| 699 | Loc ThisLoc = Context.getSValBuilder().getCXXThis(CtorDecl->getParent(), |
| 700 | Context.getStackFrame()); |
| 701 | // Getting the value for 'this'. |
| 702 | SVal This = Context.getState()->getSVal(ThisLoc); |
| 703 | |
| 704 | // Getting the value for '*this'. |
| 705 | SVal Object = Context.getState()->getSVal(This.castAs<Loc>()); |
| 706 | |
| 707 | return Object.getAs<nonloc::LazyCompoundVal>(); |
| 708 | } |
| 709 | |
Kristof Umann | 0735cfb | 2018-08-08 12:23:02 +0000 | [diff] [blame] | 710 | static bool willObjectBeAnalyzedLater(const CXXConstructorDecl *Ctor, |
| 711 | CheckerContext &Context) { |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 712 | |
Kristof Umann | 0735cfb | 2018-08-08 12:23:02 +0000 | [diff] [blame] | 713 | Optional<nonloc::LazyCompoundVal> CurrentObject = getObjectVal(Ctor, Context); |
| 714 | if (!CurrentObject) |
| 715 | return false; |
| 716 | |
| 717 | const LocationContext *LC = Context.getLocationContext(); |
| 718 | while ((LC = LC->getParent())) { |
| 719 | |
| 720 | // If \p Ctor was called by another constructor. |
| 721 | const auto *OtherCtor = dyn_cast<CXXConstructorDecl>(LC->getDecl()); |
| 722 | if (!OtherCtor) |
| 723 | continue; |
| 724 | |
| 725 | Optional<nonloc::LazyCompoundVal> OtherObject = |
| 726 | getObjectVal(OtherCtor, Context); |
| 727 | if (!OtherObject) |
| 728 | continue; |
| 729 | |
| 730 | // If the CurrentObject is a subregion of OtherObject, it will be analyzed |
| 731 | // during the analysis of OtherObject. |
| 732 | if (CurrentObject->getRegion()->isSubRegionOf(OtherObject->getRegion())) |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 733 | return true; |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 734 | } |
Kristof Umann | 0735cfb | 2018-08-08 12:23:02 +0000 | [diff] [blame] | 735 | |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 736 | return false; |
| 737 | } |
| 738 | |
Kristof Umann | cc85244 | 2018-07-12 13:13:46 +0000 | [diff] [blame] | 739 | static void printNoteMessage(llvm::raw_ostream &Out, |
| 740 | const FieldChainInfo &Chain) { |
Kristof Umann | 9bd4439 | 2018-06-29 11:25:24 +0000 | [diff] [blame] | 741 | if (Chain.isPointer()) { |
| 742 | if (Chain.isDereferenced()) |
| 743 | Out << "uninitialized pointee 'this->"; |
| 744 | else |
| 745 | Out << "uninitialized pointer 'this->"; |
| 746 | } else |
| 747 | Out << "uninitialized field 'this->"; |
| 748 | Chain.print(Out); |
| 749 | Out << "'"; |
| 750 | } |
| 751 | |
Kristof Umann | 8c11909 | 2018-07-13 12:54:47 +0000 | [diff] [blame] | 752 | static StringRef getVariableName(const FieldDecl *Field) { |
| 753 | // If Field is a captured lambda variable, Field->getName() will return with |
| 754 | // an empty string. We can however acquire it's name from the lambda's |
| 755 | // captures. |
| 756 | const auto *CXXParent = dyn_cast<CXXRecordDecl>(Field->getParent()); |
| 757 | |
| 758 | if (CXXParent && CXXParent->isLambda()) { |
| 759 | assert(CXXParent->captures_begin()); |
| 760 | auto It = CXXParent->captures_begin() + Field->getFieldIndex(); |
| 761 | return It->getCapturedVar()->getName(); |
| 762 | } |
| 763 | |
| 764 | return Field->getName(); |
| 765 | } |
| 766 | |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 767 | void ento::registerUninitializedObjectChecker(CheckerManager &Mgr) { |
| 768 | auto Chk = Mgr.registerChecker<UninitializedObjectChecker>(); |
| 769 | Chk->IsPedantic = Mgr.getAnalyzerOptions().getBooleanOption( |
| 770 | "Pedantic", /*DefaultVal*/ false, Chk); |
Kristof Umann | 9bd4439 | 2018-06-29 11:25:24 +0000 | [diff] [blame] | 771 | Chk->ShouldConvertNotesToWarnings = Mgr.getAnalyzerOptions().getBooleanOption( |
| 772 | "NotesAsWarnings", /*DefaultVal*/ false, Chk); |
Kristof Umann | a3f7b58 | 2018-08-07 12:55:26 +0000 | [diff] [blame] | 773 | Chk->CheckPointeeInitialization = Mgr.getAnalyzerOptions().getBooleanOption( |
| 774 | "CheckPointeeInitialization", /*DefaultVal*/ false, Chk); |
Kristof Umann | 30f0865 | 2018-06-18 11:50:17 +0000 | [diff] [blame] | 775 | } |