summaryrefslogtreecommitdiff
path: root/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@351636 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Refactor and simplify SimpleConstraintManagerDominic Chen2017-02-251-222/+8
| | | | | | | | | | | | Summary: SimpleConstraintManager is difficult to use, and makes assumptions about capabilities of the constraint manager. This patch refactors out those portions into a new RangedConstraintManager, and also fixes some issues with camel case, formatting, and confusing naming. Reviewers: zaks.anna, dcoughlin Subscribers: mgorny, xazax.hun, NoQ, rgov, cfe-commits Differential Revision: https://reviews.llvm.org/D26061 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@296242 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix for PR15623 (corrected r290413 reverted at 290415). The patch eliminates ↵Anton Yartsev2016-12-251-1/+13
| | | | | | | | | unwanted ProgramState checker data propagation from an operand of the logical operation to operation result. The patch also simplifies an assume of a constraint of the form: "(exp comparison_op expr) != 0" to true into an assume of "exp comparison_op expr" to true. (And similarly, an assume of the form "(exp comparison_op expr) == 0" to true as an assume of exp comparison_op expr to false.) which improves precision overall. https://reviews.llvm.org/D22862 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@290505 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert changes made by r290413 until regression is fixed.Anton Yartsev2016-12-231-15/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@290415 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix for PR15623. The patch eliminates unwanted ProgramState checker data ↵Anton Yartsev2016-12-231-1/+15
| | | | | | | | | propagation from an operand of the logical operation to operation result. The patch also simplifies an assume of a constraint of the form: "(exp comparison_op expr) != 0" to true into an assume of "exp comparison_op expr" to true. (And similarly, an assume of the form "(exp comparison_op expr) == 0" to true as an assume of exp comparison_op expr to false.) which improves precision overall. https://reviews.llvm.org/D22862 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@290413 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Add a new SVal to support pointer-to-member operations.Devin Coughlin2016-12-151-0/+6
| | | | | | | | | | | Add a new type of NonLoc SVal for C++ pointer-to-member operations. This SVal supports both pointers to member functions and pointers to member data. A patch by Kirill Romanenkov! Differential Revision: https://reviews.llvm.org/D25475 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@289873 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Run clang-format and fix styleDominic Chen2016-12-131-67/+62
| | | | | | | | | | | | Summary: Split out formatting and style changes from D26061 Reviewers: zaks.anna, dcoughlin Subscribers: cfe-commits Differential Revision: https://reviews.llvm.org/D26691 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@289511 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Rename assumeWithinInclusiveRange*()Dominic Chen2016-11-151-2/+2
| | | | | | | | | | | | Summary: The name is slightly confusing, since the constraint is not necessarily within the range unless `Assumption` is true. Split out renaming for ConstraintManager.h from D26061 Reviewers: zaks.anna, dcoughlin Subscribers: cfe-commits Differential Revision: https://reviews.llvm.org/D26644 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@286927 91177308-0d34-0410-b5e6-96231b3b80d8
* Roll-back r250822.Angel Garcia Gomez2015-10-201-1/+1
| | | | | | | | | | Summary: It breaks the build for the ASTMatchers Subscribers: klimek, cfe-commits Differential Revision: http://reviews.llvm.org/D13893 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@250827 91177308-0d34-0410-b5e6-96231b3b80d8
* Apply modernize-use-default to clang.Angel Garcia Gomez2015-10-201-1/+1
| | | | | | | | | | | | Summary: Replace empty bodies of default constructors and destructors with '= default'. Reviewers: bkramer, klimek Subscribers: klimek, alexfh, cfe-commits Differential Revision: http://reviews.llvm.org/D13890 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@250822 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Create one state for a range switch case instead of multiple.Devin Coughlin2015-09-221-0/+67
| | | | | | | | | | | | | This fixes PR16833, in which the analyzer was using large amounts of memory for switch statements with large case ranges. rdar://problem/14685772 A patch by Aleksei Sidorin! Differential Revision: http://reviews.llvm.org/D5102 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@248318 91177308-0d34-0410-b5e6-96231b3b80d8
* [C++11] Use 'nullptr'. StaticAnalyzer edition.Craig Topper2014-05-271-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@209642 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Add support for testing the presence of weak functions.Jordan Rose2013-08-281-45/+14
| | | | | | | | | | | | | | | | | | | | | | | | When casting the address of a FunctionTextRegion to bool, or when adding constraints to such an address, use a stand-in symbol to represent the presence or absence of the function if the function is weakly linked. This is groundwork for possible simple availability testing checks, and can already catch mistakes involving inverted null checks for weakly-linked functions. Currently, the implementation reuses the "extent" symbols, originally created for tracking the size of a malloc region. Since FunctionTextRegions cannot be dereferenced, the extent symbol will never be used for anything else. Still, this probably deserves a refactoring in the future. This patch does not attempt to support testing the presence of weak /variables/ (global variables), which would likely require much more of a change and a generalization of "region structure metadata", like the current "extents", vs. "region contents metadata", like CStringChecker's "string length". Patch by Richard <tarka.t.otter@googlemail.com>! git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@189492 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Ensure BugReporterTracking works on regions with pointer arithmeticAnna Zaks2013-04-201-13/+8
| | | | | | | | | | Introduce a new helper function, which computes the first symbolic region in the base region chain. The corresponding symbol has been used for assuming that a pointer is null. Now, it will also be used for checking if it is null. This ensures that we are tracking a null pointer correctly in the BugReporter. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@179916 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Replace isIntegerType() with isIntegerOrEnumerationType().Jordan Rose2013-04-091-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | Previously, the analyzer used isIntegerType() everywhere, which uses the C definition of "integer". The C++ predicate with the same behavior is isIntegerOrUnscopedEnumerationType(). However, the analyzer is /really/ using this to ask if it's some sort of "integrally representable" type, i.e. it should include C++11 scoped enumerations as well. hasIntegerRepresentation() sounds like the right predicate, but that includes vectors, which the analyzer represents by its elements. This commit audits all uses of isIntegerType() and replaces them with the general isIntegerOrEnumerationType(), except in some specific cases where it makes sense to exclude scoped enumerations, or any enumerations. These cases now use isIntegerOrUnscopedEnumerationType() and getAs<BuiltinType>() plus BuiltinType::isInteger(). isIntegerType() is hereby banned in the analyzer - lib/StaticAnalysis and include/clang/StaticAnalysis. :-) Fixes real assertion failures. PR15703 / <rdar://problem/12350701> git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@179081 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Teach ConstraintManager to ignore NonLoc <> NonLoc comparisons.Jordan Rose2013-03-241-2/+7
| | | | | | | | | These aren't generated by default, but they are needed when either side of the comparison is tainted. Should fix our internal buildbot. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177846 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Teach constraint managers about unsigned comparisons.Jordan Rose2013-03-231-2/+6
| | | | | | | | | | | In C, comparisons between signed and unsigned numbers are always done in unsigned-space. Thus, we should know that "i >= 0U" is always true, even if 'i' is signed. Similarly, "u >= 0" is also always true, even though '0' is signed. Part of <rdar://problem/13239003> (false positives related to std::vector) git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177806 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Also transform "a < b" to "(b - a) > 0" in the constraint manager.Jordan Rose2013-03-231-15/+17
| | | | | | | | | | | | We can support the full range of comparison operations between two locations by canonicalizing them as subtraction, as in the previous commit. This won't work (well) if either location includes an offset, or (again) if the comparisons are not consistent about which region comes first. <rdar://problem/13239003> git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177803 91177308-0d34-0410-b5e6-96231b3b80d8
* Add reverseComparisonOp and negateComparisonOp to BinaryOperator.Jordan Rose2013-03-231-16/+1
| | | | | | ...and adopt them in the analyzer. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177802 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Translate "a != b" to "(b - a) != 0" in the constraint manager.Jordan Rose2013-03-231-16/+36
| | | | | | | | | | | | | | | | | | | | | | | Canonicalizing these two forms allows us to better model containers like std::vector, which use "m_start != m_finish" to implement empty() but "m_finish - m_start" to implement size(). The analyzer should have a consistent interpretation of these two symbolic expressions, even though it's not properly reasoning about either one yet. The other unfortunate thing is that while the size() expression will only ever be written "m_finish - m_start", the comparison may be written "m_finish == m_start" or "m_start == m_finish". Right now the analyzer does not attempt to canonicalize those two expressions, since it doesn't know which length expression to pick. Doing this correctly will probably require implementing unary minus as a new SymExpr kind (<rdar://problem/12351075>). For now, the analyzer inverts the order of arguments in the comparison to build the subtraction, on the assumption that "begin() != end()" is written more often than "end() != begin()". This is purely speculation. <rdar://problem/13239003> git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@177801 91177308-0d34-0410-b5e6-96231b3b80d8
* Include llvm::Optional in clang/Basic/LLVM.hDavid Blaikie2013-02-201-2/+2
| | | | | | Post-commit CR feedback from Jordan Rose regarding r175594. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@175679 91177308-0d34-0410-b5e6-96231b3b80d8
* Replace SVal llvm::cast support to be well-defined.David Blaikie2013-02-201-10/+9
| | | | | | See r175462 for another example/more details. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@175594 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Make ProgramStateManager's SubEngine parameter optional.Jordan Rose2012-10-011-4/+4
| | | | | | | | | It is possible and valid to have a state manager and associated objects without having a SubEngine or checkers. Patch by Olaf Krzikalla! git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@164947 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove unnecessary ASTContext& parameter from SymExpr::getType().Ted Kremenek2012-09-261-6/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@164661 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer]Prevent infinite recursion(assume->checker:evalAssume->assume)Anna Zaks2012-09-241-1/+3
| | | | | | (Unfortunately, I do not have a good reduced test case for this.) git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@164541 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove ProgramState::getSymVal(). It was being misused by Checkers,Ted Kremenek2012-09-071-1/+3
| | | | | | | | | | | | | | | | | | | | with at least one subtle bug in MacOSXKeyChainAPIChecker where the calling the method was a substitute for assuming a symbolic value was null (which is not the case). We still keep ConstraintManager::getSymVal(), but we use that as an optimization in SValBuilder and ProgramState::getSVal() to constant-fold SVals. This is only if the ConstraintManager can provide us with that information, which is no longer a requirement. As part of this, introduce a default implementation of ConstraintManager::getSymVal() which returns null. For Checkers, introduce ConstraintManager::isNull(), which queries the state to see if the symbolic value is constrained to be a null value. It does this without assuming it has been implicitly constant folded. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@163428 91177308-0d34-0410-b5e6-96231b3b80d8
* Despite me asking Jordan to do r162313, revert it. We can provideTed Kremenek2012-08-221-29/+19
| | | | | | another way to whitelist these special cases. This is an intermediate patch. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@162386 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Push "references are non-null" knowledge up to the common parent.Jordan Rose2012-08-211-19/+29
| | | | | | | | | | This reduces duplication across the Basic and Range constraint managers, and keeps their internals free of dealing with the semantics of C++. It's still a little unfortunate that the constraint manager is dealing with this at all, but this is pretty much the only place to put it so that it will apply to all symbolic values, even when embedded in larger expressions. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@162313 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Exit early if constraint solver is given a non-integer symbolAnna Zaks2012-05-101-0/+5
| | | | | | | | | | | to reason about. As part of taint propagation, we now allow creation of non-integer symbolic expressions like a cast from int to float. Addresses PR12511 (radar://11215362). git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@156578 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Rework both constraint managers to handle mixed-type comparisons.Jordy Rose2012-05-081-62/+36
| | | | | | | | | | | | | | | | | | This involves keeping track of three separate types: the symbol type, the adjustment type, and the comparison type. For example, in "$x + 5 > 0ULL", if the type of $x is 'signed char', the adjustment type is 'int' and the comparison type is 'unsigned long long'. Most of the time these three types will be the same, but we should still do the right thing when the comparison value is out of range, and wraparound should be calculated in the adjustment type. This also re-disables an out-of-bounds test; we were extracting the symbol from non-additive SymIntExprs, but then throwing away the integer. Sorry for the large patch; both the basic and range constraint managers needed to be updated together, since they share code in SimpleConstraintManager. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@156361 91177308-0d34-0410-b5e6-96231b3b80d8
* Change references to 'const ProgramState *' to typedef 'ProgramStateRef'.Ted Kremenek2012-01-261-8/+8
| | | | | | | | At this point this is largely cosmetic, but it opens the door to replace ProgramStateRef with a smart pointer that more eagerly acts in the role of reclaiming unused ProgramState objects. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@149081 91177308-0d34-0410-b5e6-96231b3b80d8
* More dead code removal (using -Wunreachable-code)David Blaikie2012-01-201-4/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@148577 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Unify SymbolVal and SymExprVal under a single SymbolValAnna Zaks2011-12-051-28/+25
| | | | | | | | | | | | | | | | class. We are going into the direction of handling SymbolData and other SymExpr uniformly, so it makes less sense to keep two different SVal classes. For example, the checkers would have to take an extra step to reason about each type separately. The classes have the same members, we were just using the SVal kind field for easy differentiation in 3 switch statements. The switch statements look more ugly now, but we can make the code more readable in other ways, for example, moving some code into separate functions. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@145833 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Remove all uses of ConstraintManager::canResonAbout() fromAnna Zaks2011-12-051-42/+43
| | | | | | | | | | | | ExprEngine. Teach SimpleConstraintManager::assumeSymRel() to propagate constraints to symbolic expressions. + One extra warning (real bug) is now generated due to enhanced assumeSymRel(). git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@145832 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] First step toward removingAnna Zaks2011-12-051-15/+25
| | | | | | | | | | | | | | ConstraintManager::canReasonAbout() from the ExprEngine. ExprEngine should not care if the constraint solver can reason about something or not. The solver should be able to handle all the SymExprs. To do this, the solver should be able to keep track of not only the SymbolData but of all SymExprs. This is why we change SymbolRef to be an alias of SymExpr*. When encountering an expression it cannot simplify, the solver should just add the constraints to it. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@145831 91177308-0d34-0410-b5e6-96231b3b80d8
* Switch assert(0/false) llvm_unreachable.David Blaikie2011-09-231-2/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@140367 91177308-0d34-0410-b5e6-96231b3b80d8
* Rename GRState to ProgramState, and cleanup some code formatting along the way.Ted Kremenek2011-08-151-8/+8
| | | | git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@137665 91177308-0d34-0410-b5e6-96231b3b80d8
* A few more is(Un)signedIntegerType/is(Un)signedOrEnumerationType cleanups.Douglas Gregor2011-05-211-1/+2
| | | | git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@131793 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Remove Checker V1.Argyrios Kyrtzidis2011-03-011-1/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@126725 91177308-0d34-0410-b5e6-96231b3b80d8
* Makes most methods in SVals.h conform to the naming guide. ReviewedZhanyong Wan2011-02-161-2/+2
| | | | | | | by kremenek. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@125687 91177308-0d34-0410-b5e6-96231b3b80d8
* Split 'include/clang/StaticAnalyzer' into ↵Ted Kremenek2011-02-101-3/+3
| | | | | | | | 'include/clang/StaticAnalyzer/Core' and 'include/clang/StaticAnalyzer/Checkers'. This layout matches lib/StaticAnalyzer, which corresponds to two StaticAnalyzer libraries. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@125251 91177308-0d34-0410-b5e6-96231b3b80d8
* [analyzer] Move the files in lib/StaticAnalyzer to lib/StaticAnalyzer/Core.Argyrios Kyrtzidis2011-02-081-0/+303
Eventually there will also be a lib/StaticAnalyzer/Frontend that will handle initialization and checker registration. Yet another library to avoid cyclic dependencies between Core and Checkers. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@125124 91177308-0d34-0410-b5e6-96231b3b80d8
View Lorry Controller Status