[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Phabricator via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rL363898: [analyzer] exploded-graph-rewriter: Implement a 
--diff mode. (authored by dergachev, committed by ).
Herald added a project: LLVM.
Herald added a subscriber: llvm-commits.

Changed prior to commit:
  https://reviews.llvm.org/D62761?vs=205443=205706#toc

Repository:
  rL LLVM

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761

Files:
  cfe/trunk/test/Analysis/exploded-graph-rewriter/environment_diff.dot
  cfe/trunk/test/Analysis/exploded-graph-rewriter/program_points.dot
  cfe/trunk/test/Analysis/exploded-graph-rewriter/store.dot
  cfe/trunk/test/Analysis/exploded-graph-rewriter/store_diff.dot
  cfe/trunk/utils/analyzer/exploded-graph-rewriter.py

Index: cfe/trunk/utils/analyzer/exploded-graph-rewriter.py
===
--- cfe/trunk/utils/analyzer/exploded-graph-rewriter.py
+++ cfe/trunk/utils/analyzer/exploded-graph-rewriter.py
@@ -18,6 +18,13 @@
 import re
 
 
+# A helper function for finding the difference between two dictionaries.
+def diff_dicts(curr, prev):
+removed = [k for k in prev if k not in curr or curr[k] != prev[k]]
+added = [k for k in curr if k not in prev or curr[k] != prev[k]]
+return (removed, added)
+
+
 # A deserialized source location.
 class SourceLocation(object):
 def __init__(self, json_loc):
@@ -47,13 +54,21 @@
 self.block_id = json_pp['block_id']
 
 
-# A value of a single expression in a deserialized Environment.
-class EnvironmentBinding(object):
-def __init__(self, json_eb):
-super(EnvironmentBinding, self).__init__()
-self.stmt_id = json_eb['stmt_id']
-self.pretty = json_eb['pretty']
-self.value = json_eb['value']
+# A single expression acting as a key in a deserialized Environment.
+class EnvironmentBindingKey(object):
+def __init__(self, json_ek):
+super(EnvironmentBindingKey, self).__init__()
+self.stmt_id = json_ek['stmt_id']
+self.pretty = json_ek['pretty']
+
+def _key(self):
+return self.stmt_id
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
 
 
 # Deserialized description of a location context.
@@ -65,6 +80,15 @@
 self.decl = json_frame['calling']
 self.line = json_frame['call_line']
 
+def _key(self):
+return self.lctx_id
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
+
 
 # A group of deserialized Environment bindings that correspond to a specific
 # location context.
@@ -72,8 +96,17 @@
 def __init__(self, json_frame):
 super(EnvironmentFrame, self).__init__()
 self.location_context = LocationContext(json_frame)
-self.bindings = [EnvironmentBinding(b) for b in json_frame['items']] \
-if json_frame['items'] is not None else []
+self.bindings = collections.OrderedDict(
+[(EnvironmentBindingKey(b),
+  b['value']) for b in json_frame['items']]
+if json_frame['items'] is not None else [])
+
+def diff_bindings(self, prev):
+return diff_dicts(self.bindings, prev.bindings)
+
+def is_different(self, prev):
+removed, added = self.diff_bindings(prev)
+return len(removed) != 0 or len(added) != 0
 
 
 # A deserialized Environment.
@@ -82,14 +115,46 @@
 super(Environment, self).__init__()
 self.frames = [EnvironmentFrame(f) for f in json_e]
 
+def diff_frames(self, prev):
+# TODO: It's difficult to display a good diff when frame numbers shift.
+if len(self.frames) != len(prev.frames):
+return None
+
+updated = []
+for i in range(len(self.frames)):
+f = self.frames[i]
+prev_f = prev.frames[i]
+if f.location_context == prev_f.location_context:
+if f.is_different(prev_f):
+updated.append(i)
+else:
+# We have the whole frame replaced with another frame.
+# TODO: Produce a nice diff.
+return None
+
+# TODO: Add support for added/removed.
+return updated
+
+def is_different(self, prev):
+updated = self.diff_frames(prev)
+return updated is None or len(updated) > 0
+
+
+# A single binding key in a deserialized RegionStore cluster.
+class StoreBindingKey(object):
+def __init__(self, json_sk):
+super(StoreBindingKey, self).__init__()
+self.kind = json_sk['kind']
+self.offset = json_sk['offset']
+
+def _key(self):
+return (self.kind, self.offset)
 
-# A single binding in a deserialized RegionStore cluster.
-class StoreBinding(object):
-def __init__(self, json_sb):
-super(StoreBinding, 

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ updated this revision to Diff 205443.
NoQ added a comment.

Don't try to sneak in an unrelated change.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761

Files:
  clang/test/Analysis/exploded-graph-rewriter/environment_diff.dot
  clang/test/Analysis/exploded-graph-rewriter/program_points.dot
  clang/test/Analysis/exploded-graph-rewriter/store.dot
  clang/test/Analysis/exploded-graph-rewriter/store_diff.dot
  clang/utils/analyzer/exploded-graph-rewriter.py

Index: clang/utils/analyzer/exploded-graph-rewriter.py
===
--- clang/utils/analyzer/exploded-graph-rewriter.py
+++ clang/utils/analyzer/exploded-graph-rewriter.py
@@ -18,6 +18,13 @@
 import re
 
 
+# A helper function for finding the difference between two dictionaries.
+def diff_dicts(curr, prev):
+removed = [k for k in prev if k not in curr or curr[k] != prev[k]]
+added = [k for k in curr if k not in prev or curr[k] != prev[k]]
+return (removed, added)
+
+
 # A deserialized source location.
 class SourceLocation(object):
 def __init__(self, json_loc):
@@ -47,13 +54,21 @@
 self.block_id = json_pp['block_id']
 
 
-# A value of a single expression in a deserialized Environment.
-class EnvironmentBinding(object):
-def __init__(self, json_eb):
-super(EnvironmentBinding, self).__init__()
-self.stmt_id = json_eb['stmt_id']
-self.pretty = json_eb['pretty']
-self.value = json_eb['value']
+# A single expression acting as a key in a deserialized Environment.
+class EnvironmentBindingKey(object):
+def __init__(self, json_ek):
+super(EnvironmentBindingKey, self).__init__()
+self.stmt_id = json_ek['stmt_id']
+self.pretty = json_ek['pretty']
+
+def _key(self):
+return self.stmt_id
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
 
 
 # Deserialized description of a location context.
@@ -65,6 +80,15 @@
 self.decl = json_frame['calling']
 self.line = json_frame['call_line']
 
+def _key(self):
+return self.lctx_id
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
+
 
 # A group of deserialized Environment bindings that correspond to a specific
 # location context.
@@ -72,8 +96,17 @@
 def __init__(self, json_frame):
 super(EnvironmentFrame, self).__init__()
 self.location_context = LocationContext(json_frame)
-self.bindings = [EnvironmentBinding(b) for b in json_frame['items']] \
-if json_frame['items'] is not None else []
+self.bindings = collections.OrderedDict(
+[(EnvironmentBindingKey(b),
+  b['value']) for b in json_frame['items']]
+if json_frame['items'] is not None else [])
+
+def diff_bindings(self, prev):
+return diff_dicts(self.bindings, prev.bindings)
+
+def is_different(self, prev):
+removed, added = self.diff_bindings(prev)
+return len(removed) != 0 or len(added) != 0
 
 
 # A deserialized Environment.
@@ -82,14 +115,46 @@
 super(Environment, self).__init__()
 self.frames = [EnvironmentFrame(f) for f in json_e]
 
+def diff_frames(self, prev):
+# TODO: It's difficult to display a good diff when frame numbers shift.
+if len(self.frames) != len(prev.frames):
+return None
+
+updated = []
+for i in range(len(self.frames)):
+f = self.frames[i]
+prev_f = prev.frames[i]
+if f.location_context == prev_f.location_context:
+if f.is_different(prev_f):
+updated.append(i)
+else:
+# We have the whole frame replaced with another frame.
+# TODO: Produce a nice diff.
+return None
+
+# TODO: Add support for added/removed.
+return updated
+
+def is_different(self, prev):
+updated = self.diff_frames(prev)
+return updated is None or len(updated) > 0
+
+
+# A single binding key in a deserialized RegionStore cluster.
+class StoreBindingKey(object):
+def __init__(self, json_sk):
+super(StoreBindingKey, self).__init__()
+self.kind = json_sk['kind']
+self.offset = json_sk['offset']
 
-# A single binding in a deserialized RegionStore cluster.
-class StoreBinding(object):
-def __init__(self, json_sb):
-super(StoreBinding, self).__init__()
-self.kind = json_sb['kind']
-self.offset = json_sb['offset']
-self.value = json_sb['value']
+def _key(self):
+return (self.kind, self.offset)
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
 
 
 # A single cluster of the 

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Csaba Dabis via Phabricator via cfe-commits]

Charusso accepted this revision.
Charusso marked an inline comment as done.
Charusso added a comment.

Thanks for the main development! Could I start to reduce the size with my 
SVG-magic? What do you think about make it more SVG-based on the styling side?




Comment at: clang/utils/analyzer/exploded-graph-rewriter.py:375
+def dump_binding(f, b, is_added=None):
+self._dump('%s'
+   'S%s'

Good catch!


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ marked an inline comment as done.
NoQ added inline comments.



Comment at: clang/utils/analyzer/exploded-graph-rewriter.py:287
 .replace('\\}', '}') \
+.replace('', '\\') \
 .replace('\\<', '<') \

Charusso wrote:
> Ugh, wait with that a little-bit. I have forgot to create a patch! We have to 
> escape the escapes.
> E.g. `"\x42"` -> `"\\x42"`.
Yay!


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Csaba Dabis via Phabricator via cfe-commits]

Charusso added inline comments.



Comment at: clang/utils/analyzer/exploded-graph-rewriter.py:287
 .replace('\\}', '}') \
+.replace('', '\\') \
 .replace('\\<', '<') \

Ugh, wait with that a little-bit. I have forgot to create a patch! We have to 
escape the escapes.
E.g. `"\x42"` -> `"\\x42"`.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ updated this revision to Diff 205177.
NoQ added a comment.

Add tests, rebase.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761

Files:
  clang/test/Analysis/exploded-graph-rewriter/environment_diff.dot
  clang/test/Analysis/exploded-graph-rewriter/program_points.dot
  clang/test/Analysis/exploded-graph-rewriter/store.dot
  clang/test/Analysis/exploded-graph-rewriter/store_diff.dot
  clang/utils/analyzer/exploded-graph-rewriter.py

Index: clang/utils/analyzer/exploded-graph-rewriter.py
===
--- clang/utils/analyzer/exploded-graph-rewriter.py
+++ clang/utils/analyzer/exploded-graph-rewriter.py
@@ -18,6 +18,13 @@
 import re
 
 
+# A helper function for finding the difference between two dictionaries.
+def diff_dicts(curr, prev):
+removed = [k for k in prev if k not in curr or curr[k] != prev[k]]
+added = [k for k in curr if k not in prev or curr[k] != prev[k]]
+return (removed, added)
+
+
 # A deserialized source location.
 class SourceLocation(object):
 def __init__(self, json_loc):
@@ -47,13 +54,21 @@
 self.block_id = json_pp['block_id']
 
 
-# A value of a single expression in a deserialized Environment.
-class EnvironmentBinding(object):
-def __init__(self, json_eb):
-super(EnvironmentBinding, self).__init__()
-self.stmt_id = json_eb['stmt_id']
-self.pretty = json_eb['pretty']
-self.value = json_eb['value']
+# A single expression acting as a key in a deserialized Environment.
+class EnvironmentBindingKey(object):
+def __init__(self, json_ek):
+super(EnvironmentBindingKey, self).__init__()
+self.stmt_id = json_ek['stmt_id']
+self.pretty = json_ek['pretty']
+
+def _key(self):
+return self.stmt_id
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
 
 
 # Deserialized description of a location context.
@@ -65,6 +80,15 @@
 self.decl = json_frame['calling']
 self.line = json_frame['call_line']
 
+def _key(self):
+return self.lctx_id
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
+
 
 # A group of deserialized Environment bindings that correspond to a specific
 # location context.
@@ -72,8 +96,17 @@
 def __init__(self, json_frame):
 super(EnvironmentFrame, self).__init__()
 self.location_context = LocationContext(json_frame)
-self.bindings = [EnvironmentBinding(b) for b in json_frame['items']] \
-if json_frame['items'] is not None else []
+self.bindings = collections.OrderedDict(
+[(EnvironmentBindingKey(b),
+  b['value']) for b in json_frame['items']]
+if json_frame['items'] is not None else [])
+
+def diff_bindings(self, prev):
+return diff_dicts(self.bindings, prev.bindings)
+
+def is_different(self, prev):
+removed, added = self.diff_bindings(prev)
+return len(removed) != 0 or len(added) != 0
 
 
 # A deserialized Environment.
@@ -82,14 +115,46 @@
 super(Environment, self).__init__()
 self.frames = [EnvironmentFrame(f) for f in json_e]
 
+def diff_frames(self, prev):
+# TODO: It's difficult to display a good diff when frame numbers shift.
+if len(self.frames) != len(prev.frames):
+return None
+
+updated = []
+for i in range(len(self.frames)):
+f = self.frames[i]
+prev_f = prev.frames[i]
+if f.location_context == prev_f.location_context:
+if f.is_different(prev_f):
+updated.append(i)
+else:
+# We have the whole frame replaced with another frame.
+# TODO: Produce a nice diff.
+return None
+
+# TODO: Add support for added/removed.
+return updated
+
+def is_different(self, prev):
+updated = self.diff_frames(prev)
+return updated is None or len(updated) > 0
+
+
+# A single binding key in a deserialized RegionStore cluster.
+class StoreBindingKey(object):
+def __init__(self, json_sk):
+super(StoreBindingKey, self).__init__()
+self.kind = json_sk['kind']
+self.offset = json_sk['offset']
 
-# A single binding in a deserialized RegionStore cluster.
-class StoreBinding(object):
-def __init__(self, json_sb):
-super(StoreBinding, self).__init__()
-self.kind = json_sb['kind']
-self.offset = json_sb['offset']
-self.value = json_sb['value']
+def _key(self):
+return (self.kind, self.offset)
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
 
 
 # A single cluster of the deserialized RegionStore.
@@ 

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Csaba Dabis via Phabricator via cfe-commits]

Charusso marked an inline comment as done.
Charusso added inline comments.



Comment at: clang/utils/analyzer/exploded-graph-rewriter.py:170-171
 super(Store, self).__init__()
-self.clusters = [StoreCluster(c) for c in json_s]
+self.clusters = collections.OrderedDict(
+[(c['cluster'], StoreCluster(c)) for c in json_s])
+

NoQ wrote:
> This is broken due to possible collisions in cluster keys (eg., two variables 
> with the same name but different scopes).
> I guess i'll have to add a unique key to the cluster dump, i.e., a 
> `MemRegion` pointer.
It is a good idea, thanks for fixing these errors!


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ marked an inline comment as done.
NoQ added inline comments.



Comment at: clang/utils/analyzer/exploded-graph-rewriter.py:170-171
 super(Store, self).__init__()
-self.clusters = [StoreCluster(c) for c in json_s]
+self.clusters = collections.OrderedDict(
+[(c['cluster'], StoreCluster(c)) for c in json_s])
+

This is broken due to possible collisions in cluster keys (eg., two variables 
with the same name but different scopes).
I guess i'll have to add a unique key to the cluster dump, i.e., a `MemRegion` 
pointer.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Csaba Dabis via Phabricator via cfe-commits]

Charusso added a comment.

In D62761#1539143 , @NoQ wrote:

> In D62761#1539137 , @Charusso wrote:
>
> > I asked for the new behavior, but I think it should be cool.
>
>
> The new behavior is on the original screenshot, i just uploaded the wrong 
> patch initially >.<


No problem, thanks for the screenshot and for the clarification!


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

In D62761#1539137 , @Charusso wrote:

> I asked for the new behavior, but I think it should be cool.


The new behavior is on the original screenshot, i just uploaded the wrong patch 
initially >.<


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Csaba Dabis via Phabricator via cfe-commits]

Charusso accepted this revision.
Charusso added a comment.
This revision is now accepted and ready to land.

I asked for the new behavior, but I think it should be cool.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

In D62761#1525923 , @Charusso wrote:

> In D62761#1525917 , @NoQ wrote:
>
> > Remove "-" from program point dumps because it resembles a removal marker 
> > in diffs.
>
>
> Could you add an image? I have not seen any problematic stuff, just that.


F9179567: Screen Shot 2019-06-11 at 4.52.59 PM.png 

The minus signs in "Program points: - one - two - three" are confusing.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Csaba Dabis via Phabricator via cfe-commits]

Charusso added a comment.

In D62761#1525917 , @NoQ wrote:

> Remove "-" from program point dumps because it resembles a removal marker in 
> diffs.


Could you add an image? I have not seen any problematic stuff, just that.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ updated this revision to Diff 202514.
NoQ added a comment.

Remove "-" from program point dumps because it resembles a removal marker in 
diffs.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761

Files:
  clang/utils/analyzer/exploded-graph-rewriter.py

Index: clang/utils/analyzer/exploded-graph-rewriter.py
===
--- clang/utils/analyzer/exploded-graph-rewriter.py
+++ clang/utils/analyzer/exploded-graph-rewriter.py
@@ -9,6 +9,13 @@
 import re
 
 
+# A helper function for finding the difference between two dictionaries.
+def diff_dicts(curr, prev):
+removed = [k for k in prev if k not in curr or curr[k] != prev[k]]
+added = [k for k in curr if k not in prev or curr[k] != prev[k]]
+return (removed, added)
+
+
 # A deserialized source location.
 class SourceLocation(object):
 def __init__(self, json_loc):
@@ -38,13 +45,21 @@
 self.block_id = json_pp['block_id']
 
 
-# A value of a single expression in a deserialized Environment.
-class EnvironmentBinding(object):
-def __init__(self, json_eb):
-super(EnvironmentBinding, self).__init__()
-self.stmt_id = json_eb['stmt_id']
-self.pretty = json_eb['pretty']
-self.value = json_eb['value']
+# A single expression acting as a key in a deserialized Environment.
+class EnvironmentBindingKey(object):
+def __init__(self, json_ek):
+super(EnvironmentBindingKey, self).__init__()
+self.stmt_id = json_ek['stmt_id']
+self.pretty = json_ek['pretty']
+
+def _key(self):
+return self.stmt_id
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
 
 
 # Deserialized description of a location context.
@@ -56,6 +71,15 @@
 self.decl = json_frame['calling']
 self.line = json_frame['call_line']
 
+def _key(self):
+return self.lctx_id
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
+
 
 # A group of deserialized Environment bindings that correspond to a specific
 # location context.
@@ -63,8 +87,17 @@
 def __init__(self, json_frame):
 super(EnvironmentFrame, self).__init__()
 self.location_context = LocationContext(json_frame)
-self.bindings = [EnvironmentBinding(b) for b in json_frame['items']] \
-if json_frame['items'] is not None else []
+self.bindings = collections.OrderedDict(
+[(EnvironmentBindingKey(b),
+  b['value']) for b in json_frame['items']]
+if json_frame['items'] is not None else [])
+
+def diff_bindings(self, prev):
+return diff_dicts(self.bindings, prev.bindings)
+
+def is_different(self, prev):
+removed, added = self.diff_bindings(prev)
+return len(removed) != 0 or len(added) != 0
 
 
 # A deserialized Environment.
@@ -73,29 +106,80 @@
 super(Environment, self).__init__()
 self.frames = [EnvironmentFrame(f) for f in json_e]
 
+def diff_frames(self, prev):
+# TODO: It's difficult to display a good diff when frame numbers shift.
+if len(self.frames) != len(prev.frames):
+return None
+
+updated = []
+for i in range(len(self.frames)):
+f = self.frames[i]
+prev_f = prev.frames[i]
+if f.location_context == prev_f.location_context:
+if f.is_different(prev_f):
+updated.append(i)
+else:
+# We have the whole frame replaced with another frame.
+# TODO: Produce a nice diff.
+return None
+
+# TODO: Add support for added/removed.
+return updated
+
+def is_different(self, prev):
+updated = self.diff_frames(prev)
+return updated is None or len(updated) > 0
+
+
+# A single binding key in a deserialized RegionStore cluster.
+class StoreBindingKey(object):
+def __init__(self, json_sk):
+super(StoreBindingKey, self).__init__()
+self.kind = json_sk['kind']
+self.offset = json_sk['offset']
 
-# A single binding in a deserialized RegionStore cluster.
-class StoreBinding(object):
-def __init__(self, json_sb):
-super(StoreBinding, self).__init__()
-self.kind = json_sb['kind']
-self.offset = json_sb['offset']
-self.value = json_sb['value']
+def _key(self):
+return (self.kind, self.offset)
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
 
 
 # A single cluster of the deserialized RegionStore.
 class StoreCluster(object):
 def __init__(self, json_sc):
 super(StoreCluster, self).__init__()
-self.base_region = json_sc['cluster']
-self.bindings = 

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

I'll add some tests as soon as i'm sure tests for this thing actually work (by 
landing D62638 ).


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D62761/new/

https://reviews.llvm.org/D62761



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D62761: [analyzer] exploded-graph-rewriter: Implement a --diff mode.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ created this revision.
NoQ added reviewers: dcoughlin, xazax.hun, a_sidorin, rnkovacs, Szelethus, 
baloghadamsoftware, Charusso.
Herald added subscribers: cfe-commits, dkrupp, donat.nagy, mikhail.ramalho, 
a.sidorin, szepet.
Herald added a project: clang.
NoQ added a comment.
NoQ added a parent revision: D62638: [analyzer] A Python script to prettify the 
ExplodedGraph dumps..

I'll add some tests as soon as i'm sure tests for this thing actually work (by 
landing D62638 ).


Implement a mode in which the rewriter prints differences between adjacent 
program states rather than the whole states. The whole state is still printed 
for nodes with multiple predecessors (because merge diffs were annoying to 
implement and it's still nice to have the full state occasionally) and for leaf 
nodes (because they're the important ones).

F8999355: Screen Shot 2019-05-31 at 4.57.55 PM.png 


The diffs are computed "semantically" as opposed to plain text diffs. I.e., the 
diff algorithm is hand-crafted separately for every state trait, taking the 
underlying data structures into account. This is especially nice for 
`Environment` because textual diffs would have been terrible. This, of course, 
produces quite some boilerplate, but i think it's isolated enough to not bother 
me that much.


Repository:
  rC Clang

https://reviews.llvm.org/D62761

Files:
  clang/utils/analyzer/exploded-graph-rewriter.py

Index: clang/utils/analyzer/exploded-graph-rewriter.py
===
--- clang/utils/analyzer/exploded-graph-rewriter.py
+++ clang/utils/analyzer/exploded-graph-rewriter.py
@@ -9,6 +9,13 @@
 import re
 
 
+# A helper function for finding the difference between two dictionaries.
+def diff_dicts(curr, prev):
+removed = [k for k in prev if k not in curr or curr[k] != prev[k]]
+added = [k for k in curr if k not in prev or curr[k] != prev[k]]
+return (removed, added)
+
+
 # A deserialized source location.
 class SourceLocation(object):
 def __init__(self, json_loc):
@@ -38,13 +45,21 @@
 self.block_id = json_pp['block_id']
 
 
-# A value of a single expression in a deserialized Environment.
-class EnvironmentBinding(object):
-def __init__(self, json_eb):
-super(EnvironmentBinding, self).__init__()
-self.stmt_id = json_eb['stmt_id']
-self.pretty = json_eb['pretty']
-self.value = json_eb['value']
+# A single expression acting as a key in a deserialized Environment.
+class EnvironmentBindingKey(object):
+def __init__(self, json_ek):
+super(EnvironmentBindingKey, self).__init__()
+self.stmt_id = json_ek['stmt_id']
+self.pretty = json_ek['pretty']
+
+def _key(self):
+return self.stmt_id
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
 
 
 # Deserialized description of a location context.
@@ -56,6 +71,15 @@
 self.decl = json_frame['calling']
 self.line = json_frame['call_line']
 
+def _key(self):
+return self.lctx_id
+
+def __eq__(self, other):
+return self._key() == other._key()
+
+def __hash__(self):
+return hash(self._key())
+
 
 # A group of deserialized Environment bindings that correspond to a specific
 # location context.
@@ -63,8 +87,17 @@
 def __init__(self, json_frame):
 super(EnvironmentFrame, self).__init__()
 self.location_context = LocationContext(json_frame)
-self.bindings = [EnvironmentBinding(b) for b in json_frame['items']] \
-if json_frame['items'] is not None else []
+self.bindings = collections.OrderedDict(
+[(EnvironmentBindingKey(b),
+  b['value']) for b in json_frame['items']]
+if json_frame['items'] is not None else [])
+
+def diff_bindings(self, prev):
+return diff_dicts(self.bindings, prev.bindings)
+
+def is_different(self, prev):
+removed, added = self.diff_bindings(prev)
+return len(removed) != 0 or len(added) != 0
 
 
 # A deserialized Environment.
@@ -73,29 +106,80 @@
 super(Environment, self).__init__()
 self.frames = [EnvironmentFrame(f) for f in json_e]
 
+def diff_frames(self, prev):
+# TODO: It's difficult to display a good diff when frame numbers shift.
+if len(self.frames) != len(prev.frames):
+return None
+
+updated = []
+for i in range(len(self.frames)):
+f = self.frames[i]
+prev_f = prev.frames[i]
+if f.location_context == prev_f.location_context:
+if f.is_different(prev_f):
+updated.append(i)
+else:
+# We have the whole frame replaced with another frame.
+# TODO: Produce a nice diff.
+return None
+
+# TODO: Add