[analyzer] When invalidating symbolic offset regions, take fields into account.

Previously, RegionStore was being VERY conservative in saying that because
p[i].x and p[i].y have a concrete base region of 'p', they might overlap.
Now, we check the chain of fields back up to the base object and check if
they match.

This only kicks in when dealing with symbolic offset regions because
RegionStore's "base+offset" representation of concrete offset regions loses
all information about fields. In cases where all offsets are concrete
(s.x and s.y), RegionStore will already do the right thing, but mixing
concrete and symbolic offsets can cause bindings to be invalidated that
are known to not overlap (e.g. p[0].x and p[i].y).
This additional refinement is tracked by <rdar://problem/12676180>.

<rdar://problem/12530149>

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@167654 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 107 insertions, 0 deletions

diff --git a/test/Analysis/array-struct-region.c b/test/Analysis/array-struct-region.c
index e8b1fb30e1..d628c47cb0 100644
--- a/test/Analysis/array-struct-region.c
+++ b/test/Analysis/array-struct-region.c
@@ -183,3 +183,110 @@ int testConcreteInvalidationDoubleStruct(int index) {
 }
 
 
+int testNonOverlappingStructFieldsSimple() {
+  S val;
+
+  val.x = 1;
+  val.y = 2;
+  clang_analyzer_eval(val.x == 1); // expected-warning{{TRUE}}
+  clang_analyzer_eval(val.y == 2); // expected-warning{{TRUE}}
+
+  return val.z; // expected-warning{{garbage}}
+}
+
+int testNonOverlappingStructFieldsSymbolicBase(int index, int anotherIndex) {
+  SS vals;
+
+  vals.a[index].x = 42;
+  vals.a[index].y = 42;
+  clang_analyzer_eval(vals.a[index].x == 42); // expected-warning{{TRUE}}
+  clang_analyzer_eval(vals.a[index].y == 42); // expected-warning{{TRUE}}
+
+  vals.a[anotherIndex].x = 42;
+  clang_analyzer_eval(vals.a[index].x == 42); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(vals.a[index].y == 42); // expected-warning{{TRUE}}
+
+  // FIXME: False negative. No bind ever set a field 'z'.
+  return vals.a[index].z; // no-warning
+}
+
+int testStructFieldChains(int index, int anotherIndex) {
+  SS vals[4];
+
+  vals[index].a[0].x = 42;
+  vals[anotherIndex].a[1].y = 42;
+  clang_analyzer_eval(vals[index].a[0].x == 42); // expected-warning{{TRUE}}
+  clang_analyzer_eval(vals[anotherIndex].a[1].y == 42); // expected-warning{{TRUE}}
+
+  // This doesn't affect anything in the 'a' array field.
+  vals[anotherIndex].b[1].x = 42;
+  clang_analyzer_eval(vals[index].a[0].x == 42); // expected-warning{{TRUE}}
+  clang_analyzer_eval(vals[anotherIndex].a[1].y == 42); // expected-warning{{TRUE}}
+  clang_analyzer_eval(vals[anotherIndex].b[1].x == 42); // expected-warning{{TRUE}}
+
+  // This doesn't affect anything in the 'b' array field.
+  vals[index].a[anotherIndex].x = 42;
+  clang_analyzer_eval(vals[index].a[0].x == 42); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(vals[anotherIndex].a[0].x == 42); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(vals[anotherIndex].a[1].y == 42); // expected-warning{{TRUE}}
+  clang_analyzer_eval(vals[anotherIndex].b[1].x == 42); // expected-warning{{TRUE}}
+
+  // FIXME: False negative. No bind ever set a field 'z'.
+  return vals[index].a[0].z; // no-warning
+}
+
+int testStructFieldChainsNested(int index, int anotherIndex) {
+  SS vals[4];
+
+  vals[index].a[0].x = 42;
+  clang_analyzer_eval(vals[index].a[0].x == 42); // expected-warning{{TRUE}}
+
+  vals[index].b[0] = makeS();
+  clang_analyzer_eval(vals[index].a[0].x == 42); // expected-warning{{TRUE}}
+
+  vals[index].a[0] = makeS();
+  clang_analyzer_eval(vals[index].a[0].x == 42); // expected-warning{{UNKNOWN}}
+
+  vals[index].a[0].x = 42;
+  clang_analyzer_eval(vals[index].a[0].x == 42); // expected-warning{{TRUE}}
+
+  return 0;
+}
+
+
+// --------------------
+// False positives
+// --------------------
+
+int testMixSymbolicAndConcrete(int index, int anotherIndex) {
+  SS vals;
+
+  vals.a[index].x = 42;
+  vals.a[0].y = 42;
+
+  // FIXME: Should be TRUE.
+  clang_analyzer_eval(vals.a[index].x == 42); // expected-warning{{UNKNOWN}}
+  // Should be TRUE; we set this explicitly.
+  clang_analyzer_eval(vals.a[0].y == 42); // expected-warning{{TRUE}}
+
+  vals.a[anotherIndex].y = 42;
+
+  // Should be UNKNOWN; we set an 'x'.
+  clang_analyzer_eval(vals.a[index].x == 42); // expected-warning{{UNKNOWN}}
+  // FIXME: Should be TRUE.
+  clang_analyzer_eval(vals.a[0].y == 42); // expected-warning{{UNKNOWN}}
+
+  return vals.a[0].x; // no-warning
+}
+
+void testFieldChainIsNotEnough(int index) {
+  SS vals[4];
+
+  vals[index].a[0].x = 42;
+  clang_analyzer_eval(vals[index].a[0].x == 42); // expected-warning{{TRUE}}
+
+  vals[index].a[1] = makeS();
+  // FIXME: Should be TRUE.
+  clang_analyzer_eval(vals[index].a[0].x == 42); // expected-warning{{UNKNOWN}}
+}
+