[analyzer][NFC] Factor out SymbolManager::get<*> (#121781)

Replace the family of `SymbolManager::get*Symbol(...)` member functions
with a single generic `SymbolManager::get<*>` member function.

[analyzer][Solver][NFC] Cleanup const-correctness inside range-based solver (#112891)

[analyzer][Solver] Teach SymbolicRangeInferrer about commutativity (2/2) (#112887)

This patch should not introduce much overhead as it only does one more
constraint map lookup, which is really quic

[analyzer][Solver] Teach SymbolicRangeInferrer about commutativity (2/2) (#112887)

This patch should not introduce much overhead as it only does one more
constraint map lookup, which is really quick.

Depends on #112583

show more ...

[analyzer][Solver] Improve getSymVal and friends (1/2) (#112583)

[clang][NFC] declare internal linkage function static (#108759)

Detected by `misc-use-internal-linkage`

[clang][StaticAnalyzer] Avoid 'raw_string_ostream::str' (NFC)

Since `raw_string_ostream` doesn't own the string buffer, it is
desirable (in terms of memory safety) for users to directly reference
th

[clang][StaticAnalyzer] Avoid 'raw_string_ostream::str' (NFC)

Since `raw_string_ostream` doesn't own the string buffer, it is
desirable (in terms of memory safety) for users to directly reference
the string buffer rather than use `raw_string_ostream::str()`.

Work towards TODO comment to remove `raw_string_ostream::str()`.

show more ...

[clang][analyzer] use unqualified canonical type during merging equivalence class (#95729)

Fixes: #95658
Unqualified canonical type should be used instead of normal QualType for
type equality comp

[clang][analyzer] use unqualified canonical type during merging equivalence class (#95729)

Fixes: #95658
Unqualified canonical type should be used instead of normal QualType for
type equality comparison

show more ...

[clang][NFC] Trim license header comments to 81 characters (#82919)

clang-format would format these headers poorly by splitting it into
multiple lines.

[analyzer] Avoid a crash in a debug printout function (#79446)

Previously the function `RangeConstraintManager::printValue()` crashed
when it encountered an empty rangeset (because `RangeSet::getBi

[analyzer] Avoid a crash in a debug printout function (#79446)

Previously the function `RangeConstraintManager::printValue()` crashed
when it encountered an empty rangeset (because `RangeSet::getBitwidth()`
and `RangeSet::isUnsigned()` assert that the rangeset is not empty).
This commit adds a special case that avoids this behavior.

As `printValue()` is only used by the checker debug.ExprInspection (and
during manual debugging), the impacts of this commit are very limited.

---------

Co-authored-by: Balazs Benics <benicsbalazs@gmail.com>

show more ...

[analyzer] Let the checkers query upper and lower bounds on symbols (#74141)

This commit extends the class `SValBuilder` with the methods
`getMinValue()` and `getMaxValue()` to that work like
`SVa

[analyzer] Let the checkers query upper and lower bounds on symbols (#74141)

This commit extends the class `SValBuilder` with the methods
`getMinValue()` and `getMaxValue()` to that work like
`SValBuilder::getKnownValue()` but return the minimal/maximal possible
value the `SVal` is not perfectly constrained.

This extension of the ConstraintManager API is discussed at:
https://discourse.llvm.org/t/expose-the-inferred-range-information-in-warning-messages/75192

As a simple proof-of-concept application of this new API, this commit
extends a message from `core.BitwiseShift` with some range information
that reports the assumptions of the analyzer.

My main motivation for adding these methods is that I'll also want to
use them in `ArrayBoundCheckerV2` to make the error messages less
awkward, but I'm starting with this simpler and less important usecase
because I want to avoid merge conflicts with my other commit
https://github.com/llvm/llvm-project/pull/72107 which is currently under
review.

The testcase `too_large_right_operand_compound()` shows a situation
where querying the range information does not work (and the extra
information is not added to the error message). This also affects the
debug utility `clang_analyzer_value()`, so the problem isn't in the
fresh code. I'll do some investigations to resolve this, but I think
that this commit is a step forward even with this limitation.

show more ...

[clang] Replace None with std::nullopt in comments (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue

[clang] Replace None with std::nullopt in comments (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[analyzer] Remove unjustified assert from EquivalenceClass::simplify

One might think that by merging the equivalence classes (eqclasses) of
`Sym1` and `Sym2` symbols we would end up with a `State` i

[analyzer] Remove unjustified assert from EquivalenceClass::simplify

One might think that by merging the equivalence classes (eqclasses) of
`Sym1` and `Sym2` symbols we would end up with a `State` in which the
eqclass of `Sym1` and `Sym2` should now be the same. Surprisingly, it's
not //always// true.

Such an example triggered the assertion enforcing this _unjustified_
invariant in https://github.com/llvm/llvm-project/issues/58677.
```lang=C++
unsigned a, b;
#define assert(cond) if (!(cond)) return

void f(unsigned c) {
/*(1)*/ assert(c == b);
/*(2)*/ assert((c | a) != a);
/*(3)*/ assert(a);
// a = 0 => c | 0 != 0 => c != 0 => b != 0
}
```

I believe, that this assertion hold for reasonable cases - where both
`MemberSym` and `SimplifiedMemberSym` refer to live symbols.
It can only fail if `SimplifiedMemberSym` refers to an already dead
symbol. See the reasoning at the very end.
In this context, I don't know any way of determining if a symbol is
alive/dead, so I cannot refine the assertion in that way.
So, I'm proposing to drop this unjustified assertion.

---

Let me elaborate on why I think the assertion is wrong in its current
shape.

Here is a quick reminder about equivalence classes in CSA.
We have 4 mappings:
1) `ClassMap`: map, associating `Symbols` with an `EquivalenceClass`.
2) `ClassMembers`: map, associating `EquivalenceClasses` with its
members - basically an enumeration of the `Symbols` which are known
to be equal.
3) `ConstraintRange`: map, associating `EquivalenceClasses` with the
range constraint which should hold for all the members of the
eqclass.
4) `DisequalityMap`: I'm omitting this, as it's irrelevant for our
purposes now.

Whenever we encounter/assume that two `SymbolRefs` are equal, we update
the `ClassMap` so that now both `SymbolRefs` are referring to the same
eqclass. This operation is known as `merge` or `union`.
Each eqclass is uniquely identified by the `representative` symbol, but
it could have been just a unique number or anything else - the point
is that an eqclass is identified by something unique.
Initially, all Symbols form - by itself - a trivial eqclass, as there
are no other Symbols to which it is assumed to be equal. A trivial
eqclass has //notionally// exactly one member, the representative symbol.
I'm emphasizing that //notionally// because for such cases we don't store
an entry in the `ClassMap` nor in the `ClassMembers` map, because it
could be deduced.

By `merging` two eqclasses, we essentially do what you would think it
does. An important thing to highlight is that the representative symbol
of the resulting eqclass will be the same as one of the two eqclasses.
This operation should be commutative, so that `merge(eq1,eq2)` and
`merge(eq2,eq1)` should result in the same eqclass - except for the
representative symbol, which is just a unique identifier of the class,
a name if you will. Using the representative symbol of `eq1` or `eq2`
should have no visible effect on the analysis overall.

When merging `eq1` into `eq2`, we take each of the `ClassMembers` of
`eq1` and add them to the `ClassMembers` of `eq2` while we also redirect
all the `Symbol` members of `eq1` to map to the `eq2` eqclass in the
`ClassMap`. This way all members of `eq1` will refer to the correct
eqclass. After these, `eq1` key is unreachable in the `ClassMembers`,
hence we can drop it.

---

Let's get back to the example.
Note that when I refer to symbols `a`, `b`, `c`, I'm referring to the
`SymbolRegionValue{VarRegion{.}}` - the value of that variable.

After `(1)`, we will have a constraint `c == b : [1,1]` and an eqclass
`c,b` with the `c` representative symbol.
After `(2)`, we will have an additional constraint `c|b != a : [1,1]`
with the same eqclass. We will also have disequality info about that
`c|a` is disequal to `a` - and the other way around.
However, after the full-expression, `c` will become dead. This kicks in
the garbage collection, which transforms the state into this:
- We no longer have any constraints, because only `a` is alive, for
which we don't have any constraints.
- We have a single (non-trivial) eqclass with a single element `b` and
representative symbol `c`. (Dead symbols can be representative
symbols.)
- We have the same disequality info as before.

At `(3)` within the false branch, `a` get perfectly constrained to zero.
This kicks in the simplification, so we try to substitute (simplify) the
variable in each SymExpr-tree. In our case, it means that the
`c|a != a : [1,1]` constraint gets re-evaluated as `c|0 != 0 : [1,1]`,
which is `c != 0 : [1,1]`.
Under the hood, it means that we will call `merge(c|a, c)`. where `c` is
the result of `simplifyToSVal(State, MemberSym).getAsSymbol()` inside
`EquivalenceClass::simplify()`.
Note that the result of `simplifyToSVal()` was a dead symbol. We
shouldn't have acquired an already dead symbol. AFAIK, this is the only
way we can get one at this point.
Since `c` is dead, we no longer have a mapping in `ClassMap` for it;
hence when we try to `find()` the eqclass of `c`, it will report that
it's a trivial eqclass with the representative symbol `c`.

After `merge(c|a, c)`, we will have a single (non-trivial) eqclass of
`b, c|a` with the representative symbol `c|a` - because we merged the
eqclass of `c` into the eqclass of `c|a`.

This means that `find(c|a)` will result in the eqclass with the
representative symbol `c|a`. So, we ended up having different eqclasses
for `find(c|a)` and `find(c)` after `merge(c|a, c)`, firing the
assertion.

I believe, that this assertion hold for reasonable cases - where both
`MemberSym` and `SimplifiedMemberSym` refer to live symbols.
`MemberSym` should be live in all cases here, because it is from
`ClassMembers` which is pruned in `removeDeadBindings()` so these must
be alive. In this context, I don't know any way of determining if a
symbol is alive/dead, so I cannot refine the assertion in that way.
So, I'm proposing to drop this unjustified assertion.

I'd like to thank @martong for helping me to conclude the investigation.
It was really difficult to track down.

PS: I mentioned that `merge(eq1, eq2)` should be commutative. We
actually exploit this for merging the smaller eqclass into the bigger
one within `EquivalenceClass::merge()`.
Yea, for some reason, if you swap the operands, 3 tests break (only
failures, no crashes) aside from the test which checks the state dumps.
But I believe, that is a different bug and orthogonal to this one. I
just wanted to mention that.
- `Analysis/solver-sym-simplification-adjustment.c`
- `Analysis/symbol-simplification-fixpoint-iteration-unreachable-code.cpp`
- `Analysis/symbol-simplification-reassume.cpp`

Fixes #58677

Reviewed By: vabridgers

Differential Revision: https://reviews.llvm.org/D138037

show more ...

[analyzer][solver] Improve reasoning for not equal to operator

This patch fixes certain cases where solver was not able to infer
disequality due to overlapping of values in rangeset. This case was
c

[analyzer][solver] Improve reasoning for not equal to operator

This patch fixes certain cases where solver was not able to infer
disequality due to overlapping of values in rangeset. This case was
casting from lower signed type to bigger unsigned type.

Reviewed By: steakhal

Differential Revision: https://reviews.llvm.org/D140086

show more ...

[clang] Use std::optional instead of llvm::Optional (NFC)

This patch replaces (llvm::|)Optional< with std::optional<. I'll post
a separate patch to remove #include "llvm/ADT/Optional.h".

This is p

[clang] Use std::optional instead of llvm::Optional (NFC)

This patch replaces (llvm::|)Optional< with std::optional<. I'll post
a separate patch to remove #include "llvm/ADT/Optional.h".

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[clang] Add #include <optional> (NFC)

This patch adds #include <optional> to those files containing
llvm::Optional<...> or Optional<...>.

I'll post a separate patch to actually replace llvm::Option

[clang] Add #include <optional> (NFC)

This patch adds #include <optional> to those files containing
llvm::Optional<...> or Optional<...>.

I'll post a separate patch to actually replace llvm::Optional with
std::optional.

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[analyzer] Fix crash inside RangeConstraintManager.cpp introduced by D112621

It seems like `LHS` and `RHS` could be empty range sets.
This caused an assertion failure inside RangeConstraintManager.

[analyzer] Fix crash inside RangeConstraintManager.cpp introduced by D112621

It seems like `LHS` and `RHS` could be empty range sets.
This caused an assertion failure inside RangeConstraintManager.

I'm hoisting out the check from the function into the call-site.
This way we could assert that we only want to deal with non-empty range
sets.

The relevant part of the trace:
```
#6 0x00007fe6ff5f81a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
#7 0x00007fe6ff5f8252 (/lib64/libc.so.6+0x2f252)
#8 0x00000000049caed2 (anonymous namespace)::SymbolicRangeInferrer::VisitBinaryOperator(clang::ento::RangeSet, clang::BinaryOperatorKind, clang::ento::RangeSet, clang::QualType) RangeConstraintManager.cpp:0:0
#9 0x00000000049c9867 (anonymous namespace)::SymbolicRangeInferrer::infer(clang::ento::SymExpr const*) RangeConstraintManager.cpp:0:0
#10 0x00000000049bebf5 (anonymous namespace)::RangeConstraintManager::assumeSymNE(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*, llvm::APSInt const&, llvm::APSInt const&) RangeConstraintManager.cpp:0:0
#11 0x00000000049d368c clang::ento::RangedConstraintManager::assumeSymUnsupported(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*, bool) (../../main-github/llvm/build-all/bin/clang+0x49d368c)
#12 0x00000000049f0b09 clang::ento::SimpleConstraintManager::assumeAux(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::NonLoc, bool) (../../main-github/llvm/build-all/bin/clang+0x49f0b09)
#13 0x00000000049f096a clang::ento::SimpleConstraintManager::assume(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::NonLoc, bool) (../../main-github/llvm/build-all/bin/clang+0x49f096a)
#14 0x00000000049f086d clang::ento::SimpleConstraintManager::assumeInternal(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::DefinedSVal, bool) (../../main-github/llvm/build-all/bin/clang+0x49f086d)
#15 0x000000000492d3e3 clang::ento::ConstraintManager::assumeDual(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::DefinedSVal) (../../main-github/llvm/build-all/bin/clang+0x492d3e3)
#16 0x0000000004955b6d clang::ento::ExprEngine::evalEagerlyAssumeBinOpBifurcation(clang::ento::ExplodedNodeSet&, clang::ento::ExplodedNodeSet&, clang::Expr const*) (../../main-github/llvm/build-all/bin/clang+0x4955b6d)
#17 0x00000000049514b6 clang::ento::ExprEngine::Visit(clang::Stmt const*, clang::ento::ExplodedNode*, clang::ento::ExplodedNodeSet&) (../../main-github/llvm/build-all/bin/clang+0x49514b6)
#18 0x000000000494c73e clang::ento::ExprEngine::ProcessStmt(clang::Stmt const*, clang::ento::ExplodedNode*) (../../main-github/llvm/build-all/bin/clang+0x494c73e)
#19 0x000000000494c459 clang::ento::ExprEngine::processCFGElement(clang::CFGElement, clang::ento::ExplodedNode*, unsigned int, clang::ento::NodeBuilderContext*) (../../main-github/llvm/build-all/bin/clang+0x494c459)
#20 0x000000000492f3d0 clang::ento::CoreEngine::HandlePostStmt(clang::CFGBlock const*, unsigned int, clang::ento::ExplodedNode*) (../../main-github/llvm/build-all/bin/clang+0x492f3d0)
#21 0x000000000492e1f6 clang::ento::CoreEngine::ExecuteWorkList(clang::LocationContext const*, unsigned int, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>) (../../main-github/llvm/build-all/bin/clang+0x492e1f6)
```

Differential Revision: https://reviews.llvm.org/D112621

show more ...

[analyzer][solver] Introduce reasoning for not equal to operator

With this patch, the solver can infer results for not equal (!=) operator
over Ranges as well. This also fixes the issue of compariso

[analyzer][solver] Introduce reasoning for not equal to operator

With this patch, the solver can infer results for not equal (!=) operator
over Ranges as well. This also fixes the issue of comparison between
different types, by first converting the RangeSets to the resulting type,
which then can be used for comparisons.

Patch by Manas.

Reviewed By: steakhal

Differential Revision: https://reviews.llvm.org/D112621

show more ...

[clang] Use std::nullopt instead of None in comments (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasval

[clang] Use std::nullopt instead of None in comments (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[clang] Use std::nullopt instead of None in comments (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasval

[clang] Use std::nullopt instead of None in comments (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[StaticAnalyzer] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the am

[StaticAnalyzer] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount of manual work required in migrating from Optional to
std::optional.

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[clang][clang-tools-extra] LLVM_NODISCARD => [[nodiscard]]. NFC

[analyzer] Add new function `clang_analyzer_value` to ExprInspectionChecker

Summary: Introduce a new function 'clang_analyzer_value'. It emits a report that in turn prints a RangeSet or APSInt assoc

[analyzer] Add new function `clang_analyzer_value` to ExprInspectionChecker

Summary: Introduce a new function 'clang_analyzer_value'. It emits a report that in turn prints a RangeSet or APSInt associated with SVal. If there is no associated value, prints "n/a".

show more ...

[analyzer][NFC] Tidy up handler-functions in SymbolicRangeInferrer

Summary: Sorted some handler-functions into more appropriate visitor functions of the SymbolicRangeInferrer.
- Spread `getRangeForN

[analyzer][NFC] Tidy up handler-functions in SymbolicRangeInferrer

Summary: Sorted some handler-functions into more appropriate visitor functions of the SymbolicRangeInferrer.
- Spread `getRangeForNegatedSub` body over several visitor functions: `VisitSymExpr`, `VisitSymIntExpr`, `VisitSymSymExpr`.
- Moved `getRangeForComparisonSymbol` from `infer` to `VisitSymSymExpr`.

Differential Revision: https://reviews.llvm.org/D129678

show more ...

[analyzer][NFC] Move overconstrained check from reAssume to assumeDualImpl

Depends on D126406. Checking of the overconstrained property is much
better suited here.

Differential Revision: https://re

[analyzer][NFC] Move overconstrained check from reAssume to assumeDualImpl

Depends on D126406. Checking of the overconstrained property is much
better suited here.

Differential Revision: https://reviews.llvm.org/D126707

show more ...

[analyzer][solver] Handle UnarySymExpr in RangeConstraintSolver

Fixes https://github.com/llvm/llvm-project/issues/55241

Differential Revision: https://reviews.llvm.org/D125395