[binutils-gdb] Don't recursively look for a symbol in all imports of imported modules.

[Iain Buclaw <ibuclaw at sourceware dot org>]

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=38899f16e1560ce3020bab8a6a0b3a0c017d7925

commit 38899f16e1560ce3020bab8a6a0b3a0c017d7925
Author: Iain Buclaw <ibuclaw@gdcproject.org>
Date:   Sun Feb 28 10:25:55 2016 +0100

    Don't recursively look for a symbol in all imports of imported modules.
    
    Given two or more modules that import each other's scope, the current symbol
    lookup routines would go round in circles looking through each import from
    each module, possibly checking the same module twice or more until all possible
    paths are marked as "searched".
    
    Given enough modules, this causes an exponential slowdown in time taken to find
    symbols that do exist, and infinite recursion when they don't.
    
    gdb/ChangeLog:
    	* d-namespace.c (d_lookup_symbol_imports): Avoid recursive lookups from
    	cyclic imports.
    
    gdb/testsuite/ChangeLog:
    	* gdb.dlang/circular.c: New file.
    	* gdb.dlang/circular.exp: New file.

Diff:
---
 gdb/ChangeLog                        |   5 ++
 gdb/d-namespace.c                    |  10 +--
 gdb/testsuite/ChangeLog              |   5 ++
 gdb/testsuite/gdb.dlang/circular.c   |  33 ++++++++
 gdb/testsuite/gdb.dlang/circular.exp | 149 +++++++++++++++++++++++++++++++++++
 5 files changed, 197 insertions(+), 5 deletions(-)

diff --git a/gdb/ChangeLog b/gdb/ChangeLog
index bcbaacf..bc6a713 100644
--- a/gdb/ChangeLog
+++ b/gdb/ChangeLog
@@ -1,3 +1,8 @@
+2016-02-28  Iain Buclaw  <ibuclaw@gdcproject.org>
+
+	* d-namespace.c (d_lookup_symbol_imports): Avoid recursive lookups from
+	cyclic imports.
+
 2016-02-26  Keith Seitz  <keiths@redhat.com>
 
 	* rs6000-tdep.c (rs6000_frame_cache): Explicitly cast return result
diff --git a/gdb/d-namespace.c b/gdb/d-namespace.c
index 6399ef0..8b8c3cc 100644
--- a/gdb/d-namespace.c
+++ b/gdb/d-namespace.c
@@ -483,9 +483,9 @@ d_lookup_symbol_imports (const char *scope, const char *name,
 		    {
 		      /* Skip the '.'  */
 		      name_scope++;
-		      sym = d_lookup_symbol_imports (current->import_src,
-						     name + name_scope,
-						     block, domain);
+		      sym = d_lookup_symbol_in_module (current->import_src,
+						       name + name_scope,
+						       block, domain, 1);
 		    }
 		}
 	    }
@@ -494,8 +494,8 @@ d_lookup_symbol_imports (const char *scope, const char *name,
 	      /* If this import statement creates no alias, pass
 		 current->import_src as MODULE to direct the search
 		 towards the imported module.  */
-	      sym = d_lookup_symbol_imports (current->import_src,
-					     name, block, domain);
+	      sym = d_lookup_symbol_in_module (current->import_src,
+					       name, block, domain, 1);
 	    }
 	  current->searched = 0;
 	  discard_cleanups (searched_cleanup);
diff --git a/gdb/testsuite/ChangeLog b/gdb/testsuite/ChangeLog
index 23489ae..6aa0713 100644
--- a/gdb/testsuite/ChangeLog
+++ b/gdb/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2016-02-28  Iain Buclaw  <ibuclaw@gdcproject.org>
+
+	* gdb.dlang/circular.c: New file.
+	* gdb.dlang/circular.exp: New file.
+
 2016-02-26  Yao Qi  <yao.qi@linaro.org>
 
 	* gdb.reverse/insn-reverse.c [__arm__] (ext_reg_load): New.
diff --git a/gdb/testsuite/gdb.dlang/circular.c b/gdb/testsuite/gdb.dlang/circular.c
new file mode 100644
index 0000000..a946e3f
--- /dev/null
+++ b/gdb/testsuite/gdb.dlang/circular.c
@@ -0,0 +1,33 @@
+/* Copyright 2016 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+asm ("circular1_found_start: .globl circular1_found_start");
+
+/* DWARF will describe this function as being inside a D module.  */
+
+void
+found (void)
+{
+}
+
+asm ("circular1_found_end: .globl circular1_found_end");
+
+int
+main (void)
+{
+  found ();
+  return 0;
+}
+
diff --git a/gdb/testsuite/gdb.dlang/circular.exp b/gdb/testsuite/gdb.dlang/circular.exp
new file mode 100644
index 0000000..c6eb789
--- /dev/null
+++ b/gdb/testsuite/gdb.dlang/circular.exp
@@ -0,0 +1,149 @@
+# Copyright (C) 2016 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+# Test symbol lookup when there are multiple circular imports.
+
+load_lib "d-support.exp"
+load_lib "dwarf.exp"
+
+if { [skip_d_tests] } { continue }
+
+# This test can only be run on targets which support DWARF-2 and use gas.
+if {![dwarf2_support]} {
+    return 0
+}
+
+standard_testfile circular.c circular-dw.S
+
+# Make some DWARF for the test.
+set asm_file [standard_output_file $srcfile2]
+Dwarf::assemble $asm_file {
+    cu {} {
+	compile_unit {
+	    {language @DW_LANG_D}
+	} {
+	    declare_labels circular1_label circular2_label circular3_label
+	    declare_labels circular4_label circular5_label
+
+	    extern circular1_found_start circular1_found_end
+
+	    circular1_label: module {
+		{name circular1}
+	    } {
+		imported_module {
+		    {import :$circular2_label}
+		}
+		imported_module {
+		    {import :$circular3_label}
+		}
+		imported_module {
+		    {import :$circular4_label}
+		}
+		imported_module {
+		    {import :$circular5_label}
+		}
+
+		subprogram {
+		    {name found}
+		    {external 1 flag_present}
+		    {low_pc circular1_found_start addr}
+		    {high_pc circular1_found_end addr}
+		}
+	    }
+
+	    circular2_label: module {
+		{name circular2}
+	    } {
+		imported_module {
+		    {import :$circular1_label}
+		}
+		imported_module {
+		    {import :$circular3_label}
+		}
+		imported_module {
+		    {import :$circular4_label}
+		}
+		imported_module {
+		    {import :$circular5_label}
+		}
+	    }
+
+	    circular3_label: module {
+		{name circular3}
+	    } {
+		imported_module {
+		    {import :$circular1_label}
+		}
+		imported_module {
+		    {import :$circular2_label}
+		}
+		imported_module {
+		    {import :$circular4_label}
+		}
+		imported_module {
+		    {import :$circular5_label}
+		}
+	    }
+
+	    circular4_label: module {
+		{name circular4}
+	    } {
+		imported_module {
+		    {import :$circular1_label}
+		}
+		imported_module {
+		    {import :$circular2_label}
+		}
+		imported_module {
+		    {import :$circular3_label}
+		}
+		imported_module {
+		    {import :$circular5_label}
+		}
+	    }
+
+	    circular5_label: module {
+		{name circular5}
+	    } {
+		imported_module {
+		    {import :$circular1_label}
+		}
+		imported_module {
+		    {import :$circular2_label}
+		}
+		imported_module {
+		    {import :$circular3_label}
+		}
+		imported_module {
+		    {import :$circular4_label}
+		}
+	    }
+	}
+    }
+}
+
+if { [prepare_for_testing ${testfile}.exp ${testfile} \
+          [list $srcfile $asm_file] {nodebug}] } {
+    return -1
+}
+
+gdb_test_no_output "set language d"
+
+if {![runto "circular1.found"]} {
+    return -1
+}
+
+# This last test shouldn't timeout.
+gdb_test "print notfound" "No symbol \"notfound\" in current context."