depgraph: avoid atom hash collisions in dep_check

Atoms are stored in the graph as (atom, id(atom)) tuples since each
atom is considered to be a unique entity. For example, atoms that
appear identical may behave differently in USE matching, depending on
their unevaluated form. Also, specially generated virtual atoms may
appear identical while having different _orig_atom attributes.

2 files changed, 24 insertions, 15 deletions

diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index e57176349..bec9ffd1b 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -2146,7 +2146,7 @@ class depgraph(object):
 		if parent is None:
 			selected_atoms = mycheck[1]
 		else:
-			chosen_atoms = frozenset(mycheck[1])
+			chosen_atom_ids = frozenset(id(atom) for atom in mycheck[1])
 			selected_atoms = OrderedDict()
 			node_stack = [(parent, None, None)]
 			traversed_nodes = set()
@@ -2169,13 +2169,14 @@ class depgraph(object):
 						depth=node.depth, parent=node_parent,
 						priority=node_priority, root=node.root)
 
-				child_atoms = atom_graph.child_nodes(node)
-				selected_atoms[k] = [atom for atom in \
-					child_atoms if atom in chosen_atoms]
-				for child_atom in child_atoms:
-					if child_atom not in chosen_atoms:
+				child_atoms = []
+				selected_atoms[k] = child_atoms
+				for atom_node in atom_graph.child_nodes(node):
+					child_atom = atom_node[0]
+					if id(child_atom) not in chosen_atom_ids:
 						continue
-					for child_node in atom_graph.child_nodes(child_atom):
+					child_atoms.append(child_atom)
+					for child_node in atom_graph.child_nodes(atom_node):
 						if child_node in traversed_nodes:
 							continue
 						if not portage.match_from_list(
diff --git a/pym/portage/dep/dep_check.py b/pym/portage/dep/dep_check.py
index 200f01699..4d26f51f4 100644
--- a/pym/portage/dep/dep_check.py
+++ b/pym/portage/dep/dep_check.py
@@ -28,6 +28,12 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
 	mytrees = trees[myroot]
 	portdb = mytrees["porttree"].dbapi
 	pkg_use_enabled = mytrees.get("pkg_use_enabled")
+	# Atoms are stored in the graph as (atom, id(atom)) tuples
+	# since each atom is considered to be a unique entity. For
+	# example, atoms that appear identical may behave differently
+	# in USE matching, depending on their unevaluated form. Also,
+	# specially generated virtual atoms may appear identical while
+	# having different _orig_atom attributes.
 	atom_graph = mytrees.get("atom_graph")
 	parent = mytrees.get("parent")
 	virt_parent = mytrees.get("virt_parent")
@@ -67,7 +73,7 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
 		if not mykey.startswith("virtual/"):
 			newsplit.append(x)
 			if atom_graph is not None:
-				atom_graph.add(x, graph_parent)
+				atom_graph.add((x, id(x)), graph_parent)
 			continue
 		mychoices = myvirtuals.get(mykey, [])
 		if x.blocker:
@@ -76,7 +82,7 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
 			# maintaining a cache of blocker atoms.
 			newsplit.append(x)
 			if atom_graph is not None:
-				atom_graph.add(x, graph_parent)
+				atom_graph.add((x, id(x)), graph_parent)
 			continue
 
 		if repoman or not hasattr(portdb, 'match_pkgs') or \
@@ -115,7 +121,7 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
 			# dependency that needs to be satisfied.
 			newsplit.append(x)
 			if atom_graph is not None:
-				atom_graph.add(x, graph_parent)
+				atom_graph.add((x, id(x)), graph_parent)
 			continue
 
 		a = []
@@ -174,8 +180,9 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
 			mycheck[1].append(virt_atom)
 			a.append(mycheck[1])
 			if atom_graph is not None:
-				atom_graph.add(virt_atom, graph_parent)
-				atom_graph.add(pkg, virt_atom)
+				virt_atom_node = (virt_atom, id(virt_atom))
+				atom_graph.add(virt_atom_node, graph_parent)
+				atom_graph.add(pkg, virt_atom_node)
 		# Plain old-style virtuals.  New-style virtuals are preferred.
 		if not pkgs:
 				for y in mychoices:
@@ -187,7 +194,8 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
 						portdb.aux_get(matches[-1], ['PROVIDE'])[0].split():
 						a.append(new_atom)
 						if atom_graph is not None:
-							atom_graph.add(new_atom, graph_parent)
+							atom_graph.add((new_atom, id(new_atom)),
+								graph_parent)
 
 		if not a and mychoices:
 			# Check for a virtual package.provided match.
@@ -197,12 +205,12 @@ def _expand_new_virtuals(mysplit, edebug, mydbapi, mysettings, myroot="/",
 					pprovideddict.get(new_atom.cp, [])):
 					a.append(new_atom)
 					if atom_graph is not None:
-						atom_graph.add(new_atom, graph_parent)
+						atom_graph.add((new_atom, id(new_atom)), graph_parent)
 
 		if not a:
 			newsplit.append(x)
 			if atom_graph is not None:
-				atom_graph.add(x, graph_parent)
+				atom_graph.add((x, id(x)), graph_parent)
 		elif len(a) == 1:
 			newsplit.append(a[0])
 		else: