Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

filtergraph.py filtering is nondeterministic #26

Open
Notgnoshi opened this issue Jul 26, 2022 · 0 comments
Open

filtergraph.py filtering is nondeterministic #26

Notgnoshi opened this issue Jul 26, 2022 · 0 comments
Labels
bug Something isn't working

Comments

@Notgnoshi
Copy link
Owner 

(includegraph) nots@bedlam ~/Documents/includegraph (ag/filter) $ ./filtergraph.py -i foo.tgf -f '*bar*' >/dev/null
2022-07-26 13:36:09,880 - filtergraph - INFO - Parsed 1123 nodes
2022-07-26 13:36:09,880 - filtergraph - INFO - Filtering graph...
2022-07-26 13:36:09,906 - filtergraph - INFO - Removed 798 nodes
(includegraph) nots@bedlam ~/Documents/includegraph (ag/filter) $ ./filtergraph.py -i foo.tgf -f '*bar*' >/dev/null
2022-07-26 13:36:30,296 - filtergraph - INFO - Parsed 1123 nodes
2022-07-26 13:36:30,296 - filtergraph - INFO - Filtering graph...
2022-07-26 13:36:30,322 - filtergraph - INFO - Removed 829 nodes
(includegraph) nots@bedlam ~/Documents/includegraph (ag/filter) $ ./filtergraph.py -i foo.tgf -f '*bar*' >/dev/null
2022-07-26 13:36:49,054 - filtergraph - INFO - Parsed 1123 nodes
2022-07-26 13:36:49,054 - filtergraph - INFO - Filtering graph...
2022-07-26 13:36:49,079 - filtergraph - INFO - Removed 819 nodes
(includegraph) nots@bedlam ~/Documents/includegraph (ag/filter) $ ./filtergraph.py -i foo.tgf -f '*bar*' >/dev/null
2022-07-26 13:36:50,459 - filtergraph - INFO - Parsed 1123 nodes
2022-07-26 13:36:50,459 - filtergraph - INFO - Filtering graph...
2022-07-26 13:36:50,483 - filtergraph - INFO - Removed 833 nodes
(includegraph) nots@bedlam ~/Documents/includegraph (ag/filter) $ ./filtergraph.py -i foo.tgf -f '*bar*' >/dev/null
2022-07-26 13:36:51,887 - filtergraph - INFO - Parsed 1123 nodes
2022-07-26 13:36:51,887 - filtergraph - INFO - Filtering graph...
2022-07-26 13:36:51,912 - filtergraph - INFO - Removed 824 nodes

This is because set iteration order is nondeterministic, so each BFS searches starting at a random node.

But even with random iteration order, the number of nodes filtered should be the same.
Notgnoshi added a commit that referenced this issue Jul 26, 2022
@Notgnoshi
Only exclude nodes if they don't match the pattern
91cc046 
Given the following graph

    a.cpp
      |  \
      |   \
     a.h  a_impl.h
        \   |
        a_iface.h

and the pattern 'a*.h', we would previouslly fail to remove a_iface.h
because there were two in-edges. But the number of in-edges exclusion
only matters if the node _doesn't_ match the filter pattern.

This _helps_ #26, but doesn't fix it altogether.

Interestingly, if you run filtergraph.py on a work project several
times, the differences that _aren't_ fixed is the random existence of
the two nodes

    "/usr/include/assert.h"         "is_source_file=False, is_system_header=True, is_first_level_system_header=True"
    "/usr/include/c++/11/cctype"    "is_source_file=False, is_system_header=True, is_first_level_system_header=True"

even though no other node includes them (after filtering)
Notgnoshi added a commit that referenced this issue Jul 26, 2022
@Notgnoshi
Only exclude nodes if they don't match the pattern
9f35180 
Given the following graph

    a.cpp
      |  \
      |   \
     a.h  a_impl.h
        \   |
        a_iface.h

and the pattern 'a*.h', we would previouslly fail to remove a_iface.h
because there were two in-edges. But the number of in-edges exclusion
only matters if the node _doesn't_ match the filter pattern.

This _helps_ #26, but doesn't fix it altogether.

Interestingly, if you run filtergraph.py on a work project several
times, the differences that _aren't_ fixed is the random existence of
the two nodes

    "/usr/include/assert.h"         "is_source_file=False, is_system_header=True, is_first_level_system_header=True"
    "/usr/include/c++/11/cctype"    "is_source_file=False, is_system_header=True, is_first_level_system_header=True"

even though no other node includes them (after filtering)
@Notgnoshi Notgnoshi added the bug Something isn't working label Jul 27, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@Notgnoshi