INSTALL_MASK: index patterns anchored with leading slash (bug 675826)

For scalability, use a tree structure to index patterns that are
anchored with a leading slash.

Patterns anchored with leading slash are indexed by leading non-glob
components, making it possible to minimize the number of fnmatch
calls. For example:

  /foo*/bar -> {'.': ['/foo*/bar']}

  /foo/bar* -> {'foo': {'.': ['/foo/bar*']}}

  /foo/bar/ -> {'foo': {'bar': {'.': ['/foo/bar/']}}}

Bug: https://bugs.gentoo.org/675826
Signed-off-by: Zac Medico <zmedico@gentoo.org>

1 files changed, 36 insertions, 0 deletions

diff --git a/lib/portage/tests/util/test_install_mask.py b/lib/portage/tests/util/test_install_mask.py
index f651eb4b7..6a29db79a 100644
--- a/lib/portage/tests/util/test_install_mask.py
+++ b/lib/portage/tests/util/test_install_mask.py
@@ -119,6 +119,42 @@ class InstallMaskTestCase(TestCase):
 					),
 				)
 			),
+			(
+				'/usr/share/locale '
+				'-/usr/share/locale/en* '
+				'-/usr/share/locale/kf5_all_languages '
+				'-/usr/share/locale/locale.alias',
+				(
+					(
+						'usr/share/locale/en',
+						False,
+					),
+					(
+						'usr/share/locale/en_GB',
+						False,
+					),
+					(
+						'usr/share/locale/en/kf5_all_languages',
+						False,
+					),
+					(
+						'usr/share/locale/locale.alias',
+						False,
+					),
+					(
+						'usr/share/locale/es',
+						True,
+					),
+					(
+						'usr/share/locale/fr',
+						True,
+					),
+					(
+						'usr/share/locale',
+						True,
+					),
+				)
+			),
 		)
 
 		for install_mask_str, paths in cases: