loplugin:methodcycles more graph theory for the win

implemeent a reduction approach, which is good at finding virtual
methods that only themselves or their virtual partners.

The accessibility GetVisArea stuff is dead since
    commit 891e41fac81fbd8d5cdb277b26639abfd25a7143
    Date:   Wed Apr 4 11:23:22 2018 +0200
    dead code in AccessibleTextHelper_Impl::UpdateVisibleChildren

Change-Id: I78d9d8bca585ecec8394f2c3fe2baa93db0e58f5
Reviewed-on: https://gerrit.libreoffice.org/60912
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>

3 files changed, 177 insertions, 77 deletions

diff --git a/compilerplugins/clang/methodcycles.partition.results b/compilerplugins/clang/methodcycles.partition.results
new file mode 100644
index 000000000000..91537c8ec813
--- /dev/null
+++ b/compilerplugins/clang/methodcycles.partition.results
@@ -0,0 +1,98 @@
+callDict size 32
+
+
+void writerfilter::ooxml::OOXMLFastContextHandler::setParent(writerfilter::ooxml::OOXMLFastContextHandler *)
+writerfilter/source/ooxml/OOXMLFastContextHandler.hxx:122
+
+int SdrMarkView::GetMarkedPointCount() const
+include/svx/svdmrkv.hxx:314
+
+void SvxTextForwarder::SetUpdateModeForAcc(bool)
+include/editeng/unoedsrc.hxx:218
+
+bool psp::PrinterInfoManager::writePrinterConfig()
+vcl/inc/printerinfomanager.hxx:172
+
+void sdr::overlay::OverlayManager::restoreBackground(const vcl::Region &) const
+include/svx/sdr/overlay/overlaymanager.hxx:107
+
+bool psp::PrinterInfoManager::setDefaultPrinter(const rtl::OUString &)
+vcl/inc/printerinfomanager.hxx:176
+
+SdrUndoAction * SdrUndoFactory::CreateUndoMoveLayer(unsigned short,SdrLayerAdmin &,SdrModel &,unsigned short)
+include/svx/svdundo.hxx:758
+
+void writerfilter::dmapper::TableManager::cellPropsByCell(unsigned int,const tools::SvRef<writerfilter::dmapper::TablePropertyMap> &)
+writerfilter/source/dmapper/TableManager.hxx:452
+
+double LwpVirtualLayout::GetColWidth(unsigned short)
+lotuswordpro/source/filter/lwplayout.hxx:102
+
+double slideshow::internal::ShapeAttributeLayer::getCharRotationAngle() const
+slideshow/source/inc/shapeattributelayer.hxx:385
+
+bool SwDrawBase::KeyInput(const KeyEvent &)
+sw/source/uibase/inc/drawbase.hxx:53
+
+void SdrObject::ReformatText()
+include/svx/svdobj.hxx:685
+
+void FormatterBase::SetLocale(const com::sun::star::lang::Locale &)
+include/vcl/field.hxx:78
+
+std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > writerfilter::ooxml::OOXMLFastContextHandler::getType() const
+writerfilter/source/ooxml/OOXMLFastContextHandler.hxx:88
+
+bool sdr::contact::ObjectContact::isDrawModeBlackWhite() const
+include/svx/sdr/contact/objectcontact.hxx:154
+
+void ScVbaCondition::setFormula1(const com::sun::star::uno::Any &)
+sc/source/ui/vba/vbacondition.hxx:42
+
+void sax_fastparser::FastSaxSerializer::ForMerge::print()
+sax/source/tools/fastserializer.hxx:184
+
+bool SvxTextForwarder::GetUpdateModeForAcc() const
+include/editeng/unoedsrc.hxx:219
+
+rtl::OUString SdrObject::GetMacroPopupComment(const SdrObjMacroHitRec &) const
+include/svx/svdobj.hxx:695
+
+bool psp::PrinterInfoManager::removePrinter(const rtl::OUString &,bool)
+vcl/inc/printerinfomanager.hxx:168
+
+bool sdr::contact::ObjectContact::isOutputToWindow() const
+include/svx/sdr/contact/objectcontact.hxx:139
+
+void SfxStyleSheetBase::Load(SvStream &,unsigned short)
+include/svl/style.hxx:135
+
+void SfxObjectShell::PrepareReload()
+include/sfx2/objsh.hxx:440
+
+void SfxObjectShell::InPlaceActivate(bool)
+include/sfx2/objsh.hxx:583
+
+bool sdr::contact::ObjectContact::IsAreaVisible(const basegfx::B2DRange &) const
+include/svx/sdr/contact/objectcontact.hxx:116
+
+void sfx2::sidebar::Deck::PrintWindowSubTree(vcl::Window *,int)
+include/sfx2/sidebar/Deck.hxx:70
+
+void pdfi::PageElement::updateParagraphGeometry(pdfi::Element *)
+sdext/source/pdfimport/inc/genericelements.hxx:257
+
+bool sdr::contact::ObjectContact::isOutputToVirtualDevice() const
+include/svx/sdr/contact/objectcontact.hxx:142
+
+tools::Rectangle SvxViewForwarder::GetVisArea() const
+include/editeng/unoedsrc.hxx:470
+
+bool psp::PrinterInfoManager::addPrinter(const rtl::OUString &,const rtl::OUString &)
+vcl/inc/printerinfomanager.hxx:161
+
+SdrUndoAction * SdrUndoFactory::CreateUndoMoveObject(SdrObject &)
+include/svx/svdundo.hxx:733
+
+SdrObject * SdrObjList::NbcReplaceObject(SdrObject *,unsigned long)
+include/svx/svdpage.hxx:126
diff --git a/compilerplugins/clang/methodcycles.py b/compilerplugins/clang/methodcycles.py
index 8ff814da8bd5..d57c85ff963d 100755
--- a/compilerplugins/clang/methodcycles.py
+++ b/compilerplugins/clang/methodcycles.py
@@ -81,7 +81,7 @@ def sort_set_by_natural_key(s):
 # --------------------------------------------------------------------------------------------
 
 # follow caller-callee chains, removing all methods reachable from a root method
-def remove_reachable(startCaller):
+def remove_reachable(callDict, startCaller):
     worklist = list()
     worklist.append(startCaller)
     while len(worklist) > 0:
@@ -151,12 +151,18 @@ for caller in callDict:
                 to_be_removed.add(caller)
 # remove everything reachable from the found entry points
 for caller in to_be_removed:
-    remove_reachable(caller)
+    remove_reachable(callDict, caller)
 for caller in callDict:
     callDict[caller] -= to_be_removed
 
+# create a reverse call graph
+inverseCallDict = defaultdict(set) # map of from_method_name -> set(method_name)
+for caller in callDict:
+    for callee in callDict[caller]:
+        inverseCallDict[callee].add(caller)
+
 print_tree_recurse_set = set() # protect against cycles
-def print_tree(f, caller, depth):
+def print_tree(f, callDict, caller, depth):
     if depth == 0:
         f.write("\n") # add an empty line before each tree
         print_tree_recurse_set.clear()
@@ -172,13 +178,7 @@ def print_tree(f, caller, depth):
     f.write("  " * depth + definitionToSourceLocationMap[caller] + "\n")
     calleeSet = callDict[caller]
     for c in calleeSet:
-        print_tree(f, c, depth+1)
-
-# create a reverse call graph
-inverseCallDict = defaultdict(set) # map of from_method_name -> set(method_name)
-for caller in callDict:
-    for callee in callDict[caller]:
-        inverseCallDict[callee].add(caller)
+        print_tree(f, callDict, c, depth+1)
 
 # find possible roots (ie. entrypoints) by looking for methods that are not called
 def dump_possible_roots():
@@ -201,42 +201,75 @@ def dump_possible_roots():
             count = count + 1
             #if count>1000: break
 
-
 # Look for cycles in a directed graph
 # Adapted from:
 # https://codereview.stackexchange.com/questions/86021/check-if-a-directed-graph-contains-a-cycle
-with open("compilerplugins/clang/methodcycles.results", "wt") as f:
-    path = set()
-    visited = set()
-
-    def printPath(path):
-        if len(path) < 2:
-            return
-        # we may have found a cycle, but if the cycle is called from outside the cycle
-        # the code is still in use.
-        for p in path:
-            for caller in inverseCallDict[p]:
-                if not caller in path:
-                    return
-        f.write("found cycle\n")
-        for p in path:
-            f.write("    " + p + "\n")
-            f.write("    " + definitionToSourceLocationMap[p] + "\n")
-            f.write("\n")
-
-    def checkCyclic(vertex):
-        if vertex in visited:
-            return
-        visited.add(vertex)
-        path.add(vertex)
-        if vertex in callDict:
-            for neighbour in callDict[vertex]:
-                if neighbour in path:
-                    printPath(path)
-                    break
-                else:
-                    checkCyclic(neighbour)
-        path.remove(vertex)
+def print_cycles():
+    with open("compilerplugins/clang/methodcycles.results", "wt") as f:
+        path = set()
+        visited = set()
 
-    for caller in callDict:
-        checkCyclic(caller)
+        def printPath(path):
+            if len(path) < 2:
+                return
+            # we may have found a cycle, but if the cycle is called from outside the cycle
+            # the code is still in use.
+            for p in path:
+                for caller in inverseCallDict[p]:
+                    if not caller in path:
+                        return
+            f.write("found cycle\n")
+            for p in path:
+                f.write("    " + p + "\n")
+                f.write("    " + definitionToSourceLocationMap[p] + "\n")
+                f.write("\n")
+
+        def checkCyclic(vertex):
+            if vertex in visited:
+                return
+            visited.add(vertex)
+            path.add(vertex)
+            if vertex in callDict:
+                for neighbour in callDict[vertex]:
+                    if neighbour in path:
+                        printPath(path)
+                        break
+                    else:
+                        checkCyclic(neighbour)
+            path.remove(vertex)
+
+        for caller in callDict:
+            checkCyclic(caller)
+
+print_cycles()
+
+# print partioned sub-graphs
+def print_partitions():
+    callDict2 = callDict
+    # Remove anything with no callees, and that is itself not called.
+    # After this stage, we should only be left with closed sub-graphs ie. partitions
+    while True:
+        to_be_removed.clear()
+        for caller in callDict2:
+            if len(callDict2[caller]) == 0 \
+                or not caller in inverseCallDict[caller]:
+                to_be_removed.add(caller)
+        if len(to_be_removed) == 0:
+            break
+        for caller in to_be_removed:
+            remove_reachable(callDict2, caller)
+        for caller in callDict2:
+            callDict2[caller] -= to_be_removed
+
+    count = 0
+    with open("compilerplugins/clang/methodcycles.partition.results", "wt") as f:
+        f.write("callDict size " + str(len(callDict2)) + "\n")
+        f.write("\n")
+        while len(callDict2) > 0:
+            print_tree(f, callDict2, next(iter(callDict2)), 0)
+            for c in print_tree_recurse_set:
+                callDict2.pop(c, None)
+            count = count + 1
+            if count>1000: break
+
+print_partitions()
\ No newline at end of file
diff --git a/compilerplugins/clang/methodcycles.results b/compilerplugins/clang/methodcycles.results
index 403178b25a10..19e874c77d27 100644
--- a/compilerplugins/clang/methodcycles.results
+++ b/compilerplugins/clang/methodcycles.results
@@ -1,11 +1,4 @@
 found cycle
-    bool connectivity::OSQLParseTreeIterator::impl_getColumnTableRange(const connectivity::OSQLParseNode *,rtl::OUString &) const
-    include/connectivity/sqliterator.hxx:272
-
-    bool connectivity::OSQLParseTreeIterator::getColumnTableRange(const connectivity::OSQLParseNode *,rtl::OUString &) const
-    include/connectivity/sqliterator.hxx:259
-
-found cycle
     void (anonymous namespace)::traceValue(_typelib_TypeDescriptionReference *,void *)
     cppu/source/LogBridge/LogBridge.cxx:132
 
@@ -16,40 +9,16 @@ found cycle
     cppu/source/LogBridge/LogBridge.cxx:192
 
 found cycle
-    rtl::OUString lcl_dbg_out(SwNodes &)
-    sw/source/core/doc/dbgoutsw.cxx:743
-
-    void lcl_dbg_nodes_inner(rtl::OUString &,SwNodes &,unsigned long &)
-    sw/source/core/doc/dbgoutsw.cxx:694
-
-    const char * dbg_out(SwNodes &)
-    sw/inc/dbgoutsw.hxx:67
-
-found cycle
-    void OutputDevice::DrawPixel(const tools::Polygon &,const Color &)
-    include/vcl/outdev.hxx:710
-
-    void OutputDevice::DrawPixel(const tools::Polygon &,const Color *)
-    include/vcl/outdev.hxx:709
-
-found cycle
     void SbxVariable::Dump(SvStream &,bool)
     include/basic/sbxvar.hxx:260
 
     void SbxObject::Dump(SvStream &,bool)
-    include/basic/sbxobj.hxx:81
+    include/basic/sbxobj.hxx:80
 
     void SbRtl_DumpAllObjects(StarBASIC *,SbxArray &,bool)
     basic/source/inc/rtlproto.hxx:293
 
 found cycle
-    SbxVariable * SbxArray::FindUserData(unsigned int)
-    include/basic/sbx.hxx:138
-
-    SbxVariable * SbxObject::FindUserData(unsigned int)
-    include/basic/sbxobj.hxx:60
-
-found cycle
     unsigned long slideshow::internal::hash::operator()(const type-parameter-?-? &) const
     slideshow/source/inc/tools.hxx:83