/[gentoo-src]/portage/pym/portage_dep.py
Gentoo

Contents of /portage/pym/portage_dep.py

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.35 - (show annotations) (download) (as text)
Thu May 5 06:24:08 2005 UTC (9 years, 2 months ago) by jstubbs
Branch: MAIN
CVS Tags: HEAD
Branch point for: portage_2_1
Changes since 1.34: +61 -9 lines
File MIME type: text/x-python
Added some basic utility methods to StateGraph. Reworked the test script
into a functional equivalent of --pretend depclean.

1 # deps.py -- Portage dependency resolution functions
2 # Copyright 2003-2004 Gentoo Foundation
3 # Distributed under the terms of the GNU General Public License v2
4 # $Header: /var/cvsroot/gentoo-src/portage/pym/portage_dep.py,v 1.34 2005/05/05 05:08:26 jstubbs Exp $
5 cvs_id_string="$Id: portage_dep.py,v 1.34 2005/05/05 05:08:26 jstubbs Exp $"[5:-2]
6
7 # DEPEND SYNTAX:
8 #
9 # 'use?' only affects the immediately following word!
10 # Nesting is the only legal way to form multiple '[!]use?' requirements.
11 #
12 # Where: 'a' and 'b' are use flags, and 'z' is a depend atom.
13 #
14 # "a? z" -- If 'a' in [use], then b is valid.
15 # "a? ( z )" -- Syntax with parenthesis.
16 # "a? b? z" -- Deprecated.
17 # "a? ( b? z )" -- Valid
18 # "a? ( b? ( z ) ) -- Valid
19 #
20
21 import os,string,types,sys,copy
22 import portage_exception
23 import portage_versions
24 import portage_syntax
25
26 OPERATORS="*<=>~!"
27 ENDVERSION_KEYS = ["pre", "p", "alpha", "beta", "rc"]
28
29 def dep_getcpv(s):
30 return s.strip(OPERATORS)
31
32 def get_operator(mydep):
33 """
34 returns '~', '=', '>', '<', '=*', '>=', or '<='
35 """
36
37 if mydep[0] == "~":
38 operator = "~"
39 elif mydep[0] == "=":
40 if mydep[-1] == "*":
41 operator = "=*"
42 else:
43 operator = "="
44 elif mydep[0] in "><":
45 if len(mydep) > 1 and mydep[1] == "=":
46 operator = mydep[0:2]
47 else:
48 operator = mydep[0]
49 else:
50 operator = None
51 return operator
52
53 def isjustname(mypkg):
54 myparts=mypkg.split('-')
55 for x in myparts:
56 if portage_versions.ververify(x):
57 return 0
58 return 1
59
60
61 def isvalidatom(atom):
62 mycpv_cps = portage_versions.catpkgsplit(dep_getcpv(atom))
63 operator = get_operator(atom)
64 if operator:
65 if mycpv_cps and mycpv_cps[0] != "null":
66 # >=cat/pkg-1.0
67 return 1
68 else:
69 # >=cat/pkg or >=pkg-1.0 (no category)
70 return 0
71 if mycpv_cps:
72 # cat/pkg-1.0
73 return 0
74 if len(atom.split('/'))==2:
75 # cat/pkg
76 return 1
77 else:
78 return 0
79
80
81 def strip_empty(myarr):
82 for x in range(len(myarr)-1, -1, -1):
83 if not myarr[x]:
84 del myarr[x]
85 return myarr
86
87 def paren_reduce(mystr,tokenize=1):
88 "Accepts a list of strings, and converts '(' and ')' surrounded items to sub-lists"
89 mylist = []
90 while mystr:
91 if ("(" not in mystr) and (")" not in mystr):
92 freesec = mystr
93 subsec = None
94 tail = ""
95 elif mystr[0] == ")":
96 return [mylist,mystr[1:]]
97 elif ("(" in mystr) and (mystr.index("(") < mystr.index(")")):
98 freesec,subsec = mystr.split("(",1)
99 subsec,tail = paren_reduce(subsec,tokenize)
100 else:
101 subsec,tail = mystr.split(")",1)
102 if tokenize:
103 subsec = strip_empty(subsec.split(" "))
104 return [mylist+subsec,tail]
105 return [mylist+[subsec],tail]
106 mystr = tail
107 if freesec:
108 if tokenize:
109 mylist = mylist + strip_empty(freesec.split(" "))
110 else:
111 mylist = mylist + [freesec]
112 if subsec is not None:
113 mylist = mylist + [subsec]
114 return mylist
115
116 def use_reduce(deparray, uselist=[], masklist=[], matchall=0, excludeall=[]):
117 """Takes a paren_reduce'd array and reduces the use? conditionals out
118 leaving an array with subarrays
119 """
120 # Quick validity checks
121 for x in range(1,len(deparray)):
122 if deparray[x] in ["||","&&"]:
123 if len(deparray) == x:
124 # Operator is the last element
125 raise portage_exception.InvalidDependString("INVALID "+deparray[x]+" DEPEND STRING: "+str(deparray))
126 if type(deparray[x+1]) != types.ListType:
127 # Operator is not followed by a list
128 raise portage_exception.InvalidDependString("INVALID "+deparray[x]+" DEPEND STRING: "+str(deparray))
129 if deparray and deparray[-1] and deparray[-1][-1] == "?":
130 # Conditional with no target
131 raise portage_exception.InvalidDependString("INVALID "+deparray[x]+" DEPEND STRING: "+str(deparray))
132
133 #XXX: Compatibility -- Still required?
134 if ("*" in uselist):
135 matchall=1
136
137 mydeparray = deparray[:]
138 rlist = []
139 while mydeparray:
140 head = mydeparray.pop(0)
141
142 if type(head) == types.ListType:
143 rlist = rlist + [use_reduce(head, uselist, masklist, matchall, excludeall)]
144
145 else:
146 if head[-1] == "?": # Use reduce next group on fail.
147 # Pull any other use conditions and the following atom or list into a separate array
148 newdeparray = [head]
149 while isinstance(newdeparray[-1], str) and newdeparray[-1][-1] == "?":
150 if mydeparray:
151 newdeparray.append(mydeparray.pop(0))
152 else:
153 raise ValueError, "Conditional with no target."
154
155 # Deprecation checks
156 warned = 0
157 if len(newdeparray[-1]) == 0:
158 sys.stderr.write("Note: Empty target in string. (Deprecated)\n")
159 warned = 1
160 if len(newdeparray) != 2:
161 sys.stderr.write("Note: Nested use flags without parenthesis (Deprecated)\n")
162 warned = 1
163 if warned:
164 sys.stderr.write(" --> "+string.join(map(str,[head]+newdeparray))+"\n")
165
166 # Check that each flag matches
167 ismatch = True
168 for head in newdeparray[:-1]:
169 head = head[:-1]
170 if head[0] == "!":
171 head = head[1:]
172 if not matchall and head in uselist or head in excludeall:
173 ismatch = False
174 break
175 elif head not in masklist:
176 if not matchall and head not in uselist:
177 ismatch = False
178 break
179 else:
180 ismatch = False
181
182 # If they all match, process the target
183 if ismatch:
184 target = newdeparray[-1]
185 if isinstance(target, list):
186 rlist += [use_reduce(target, uselist, masklist, matchall, excludeall)]
187 else:
188 rlist += [target]
189
190 else:
191 rlist += [head]
192
193 return rlist
194
195
196 def dep_opconvert(deplist):
197 """Move || and && to the beginning of the following arrays"""
198 # Hack in management of the weird || for dep_wordreduce, etc.
199 # dep_opconvert: [stuff, ["||", list, of, things]]
200 # At this point: [stuff, "||", [list, of, things]]
201 retlist = []
202 x = 0
203 while x != len(deplist):
204 if isinstance(deplist[x], list):
205 retlist.append(dep_opconvert(deplist[x]))
206 elif deplist[x] == "||" or deplist[x] == "&&":
207 retlist.append([deplist[x]] + dep_opconvert(deplist[x+1]))
208 x += 1
209 else:
210 retlist.append(deplist[x])
211 x += 1
212 return retlist
213
214
215
216
217
218
219 class DependencyGraph(object):
220 """Self-contained directed graph of abstract nodes.
221
222 This is a enhanced version of the digraph class. It supports forward
223 and backward dependencies as well as primitive circular dependency
224 resolution. It is fully self contained and requires only that nodes
225 added to the graph are immutable.
226
227 There are no validity checks done on the values passed to any method,
228 but is written so that invalid data will either cause an exception to
229 be raised. For this reason, this should not be used as part of any
230 external API."""
231
232
233 def __init__(self):
234 """Create an empty graph."""
235 # The entire graph is stored inside this one dictionary.
236 # The keys represent each node within the graph. Each node
237 # is paired with a list of nodes depending on it and a list
238 # of nodes it depends on. The complete structure is:
239 # { node : ( [node], [node] ) }
240 self.graph = {}
241
242 # Strictly speaking, the graph shouldn't care about the order
243 # that packages are added to the graph, but using it ensures
244 # that system packages stay before world packages when pulling
245 # nodes one at a time.
246 self.order = []
247
248 def clone(self):
249 """Create an exact duplicate of this graph."""
250 clone = DependencyGraph()
251 # A manual copy should save a slight amount of time, but
252 # is dependent on whether python's deepcopy is implemented
253 # in python or not. It is at the moment.
254 for node in self.graph:
255 clone.graph[node] = (self.graph[node][0][:],
256 self.graph[node][1][:])
257 clone.order = self.order[:]
258 return clone
259
260 def has_node(self, node):
261 """Indicate the existance of a node in the graph."""
262 return self.graph.has_key(node)
263
264 def add_node(self, node):
265 """Add a node to the graph if it hasn't been already."""
266 if self.graph.has_key(node):
267 return
268 self.graph[node] = ([], [])
269 self.order.append(node)
270
271 def add_relationship(self, parent, child):
272 """Add a relationship between two pre-existing nodes."""
273 # This code needs to raise an exception if either the
274 # parent or child have not in fact been added prior.
275 if parent not in self.graph[child][0]:
276 self.graph[child][0].append(parent)
277 self.graph[parent][1].append(child)
278
279 def remove_relationship(self, parent, child):
280 """Remove an existing relationship between two nodes."""
281 self.graph[child][0].remove(parent)
282 self.graph[parent][1].remove(child)
283
284 def get_relationships(self, node):
285 """Retrieve parent and children lists of a node.
286
287 @rtype: ( [node], [node] )
288 """
289 # This code also needs to raise an exception if the node
290 # has not been added prior.
291 relationships = (self.graph[node][0][:],
292 self.graph[node][1][:])
293 return relationships
294
295 def remove_node(self, node):
296 """Remove a node from the graph, destroying any relationships.
297
298 Any relationships destroyed by removing this node are returned.
299
300 @rtype: ( [node], [node] )
301 """
302 # This code also needs to raise an exception if the node
303 # has not been added prior.
304
305 relationships = self.get_relationships(node)
306
307 # Ensuring that all relationships are destroyed keeps the
308 # graph in a sane state. A node must _never_ depend on another
309 # node that does not exist in the graph.
310 for parent in relationships[0]:
311 self.graph[parent][1].remove(node)
312 for child in relationships[1]:
313 self.graph[child][0].remove(node)
314
315 # Kill of the other side of the relationships in one shot.
316 del self.graph[node]
317
318 # Make sure to remove the node from the ordered list as well.
319 self.order.remove(node)
320
321 return relationships
322
323 def get_all_nodes(self):
324 """Return a list of every node in the graph.
325
326 @rtype: [node]
327 """
328 # Assuming our graph is in a sane state, self.order contains
329 # the same set of nodes as self.graph.keys().
330 return self.order[:]
331
332 def get_leaf_nodes(self):
333 """Return a list of all nodes that have no child dependencies.
334
335 If all nodes have child dependencies and the graph is not
336 empty, circular dependency resolution is attempted. In such a
337 circumstance, only one node is ever returned and is passed back
338 by way of an exception.
339
340 @rtype: [node]
341 """
342 # If the graph is empty, just return an empty list.
343 if not self.graph:
344 return []
345
346 # Iterate through the graph's nodes and add any that have no
347 # child dependencies. If we find such nodes, return them.
348 nodes = []
349 for node in self.order:
350 if not self.graph[node][1]:
351 nodes.append(node)
352 if nodes:
353 return nodes
354
355 # If we've got this far, then a circular dependency set that
356 # contains every node. However, there is usually a subset of
357 # nodes that are self-contained. We will find the subset with
358 # the most parents so that circular dependencies can be dealt
359 # with (and not have to be recalculated) as early as possible.
360
361 # Create a list of tuples containing the number of parents
362 # paired with the corresponding node.
363 counts = []
364 # We'll keep a record of the actual parents for later on.
365 parents = {}
366 for node in self.graph:
367 parents[node] = self.get_parent_nodes(node, depth=0)
368 if len(parents[node]) == len(self.graph):
369 # XXX: Every node in the graph depends on
370 # this node. Following the logic through will
371 # return this node or another that has equal
372 # number of parents, so shortcut it here.
373 return [node]
374 counts += [(len(parents[node]), node)]
375
376 # Reverse sort the generated list.
377 counts.sort()
378 counts.reverse()
379
380 # Find the first node that is in a circular dependency set.
381 for count in counts:
382 node = count[1]
383 children = self.get_child_nodes(node, depth=0)
384 if node in children:
385 break
386
387 # Now we'll order the nodes in the set by parent count.
388 counts = []
389 for node in children:
390 counts += [(len(parents[node]), node)]
391
392 # Reverse sort the generated list.
393 counts.sort()
394 counts.reverse()
395
396 # Return the first node in the list.
397 # XXX: This needs to be changed into an exception.
398 return [counts[0][1]]
399
400 def get_root_nodes(self):
401 """Return the smallest possible list of starting nodes.
402
403 Ordinarily, all nodes with no parent nodes are returned.
404 However, if there are any circular dependencies that can
405 not be reached through one of these nodes, they will be
406 resolved and a suitable starting node chosen.
407
408 @rtype: [node]
409 """
410 # Create a copy of our graph.
411 clone = self.clone()
412
413 # Keep processing the graph until it is empty.
414 roots = []
415 while clone.graph:
416
417 # Find all nodes that have no parent nodes.
418 newroots = []
419 for node in clone.order:
420 if not clone.graph[node][0]:
421 newroots.append(node)
422
423 # Remove them and all their descendents from the graph.
424 for node in newroots:
425 for child in clone.get_child_nodes(node, depth=0):
426 clone.remove_node(child)
427 clone.remove_node(node)
428
429 # And add them to our list of root nodes.
430 roots.extend(newroots)
431
432 # If the graph is empty, stop processing.
433 if not clone.graph:
434 break
435
436 # If the graph isn't empty, then we have a circular
437 # dependency. We'll just remove one leaf node and
438 # then look for parentless nodes again.
439 clone.remove_node(clone.get_leaf_nodes()[0])
440
441 # Sort the list of roots by the node addition order.
442 newroots = self.order[:]
443 for x in range(len(newroots)-1,-1,-1):
444 if newroots[x] not in roots:
445 del newroots[x]
446
447 # Return the sorted list.
448 return newroots
449
450 def get_parent_nodes(self, node, depth=1):
451 """Return a list of nodes that depend on a node.
452
453 The examined node will be included in the returned list
454 if the node exists in a circular dependency.
455
456 @param depth: Maximum depth to recurse to, or 0 for all.
457 @rtype: [node]
458 """
459 return self.__traverse_nodes(node, depth, 0)
460
461 def get_child_nodes(self, node, depth=1):
462 """Return a list of nodes depended on by node.
463
464 The examined node will be included in the returned list
465 if the node exists in a circular dependency.
466
467 @param depth: Maximum depth to recurse to, or 0 for all.
468 @rtype: [node]
469 """
470 return self.__traverse_nodes(node, depth, 1)
471
472 def __traverse_nodes(self, origin, depth, path):
473 # Set depth to the maximum if it is 0.
474 if not depth:
475 depth = len(self.graph)
476
477 traversed = {} # The list of nodes to be returned
478
479 # This function _needs_ to be fast, so we use a stack
480 # based implementation rather than recursive calls.
481 stack = [] # Stack of previous depths
482 node = origin # The current node we are checking
483 index = 0 # Progress through the node's relations
484 length = len(self.graph[node][path])
485
486 graph = self.graph # Faster access via local scope
487
488 # Repeat while the stack is not empty or there are more
489 # relations to be processed for the current node.
490 while stack or length != index:
491
492 # If we're finished at the current depth, move back up.
493 if index == length:
494 (depth, node, index, length) = stack.pop()
495
496 # Otherwise, process the next relation.
497 else:
498 relation = graph[node][path][index]
499 # Add the relation to our list if necessary...
500 if relation not in traversed:
501 traversed[relation] = None
502 # ...and then check if we can go deeper
503 if depth != 1:
504 # Add state to the stack.
505 stack += [(depth, node, index, length)]
506 # Reset state for the new node.
507 depth -= 1
508 node = relation
509 index = 0
510 length = len(graph[node][path])
511 # Restart the loop.
512 continue
513
514 # Move onto the next relation.
515 index += 1
516
517 # Return our list.
518 return traversed.keys()
519
520 def dep_getkey(mydep):
521 if not len(mydep):
522 return mydep
523 if mydep[0]=="*":
524 mydep=mydep[1:]
525 if mydep[-1]=="*":
526 mydep=mydep[:-1]
527 if mydep[0]=="!":
528 mydep=mydep[1:]
529 if mydep[:2] in [ ">=", "<=" ]:
530 mydep=mydep[2:]
531 elif mydep[:1] in "=<>~":
532 mydep=mydep[1:]
533 if isspecific(mydep):
534 mysplit=portage_versions.catpkgsplit(mydep)
535 if not mysplit:
536 return mydep
537 return mysplit[0]+"/"+mysplit[1]
538 else:
539 return mydep
540
541
542 iscache={}
543 def isspecific(mypkg):
544 "now supports packages with no category"
545 if mypkg in iscache:
546 return iscache[mypkg]
547 mysplit=mypkg.split("/")
548 if not isjustname(mysplit[-1]):
549 iscache[mypkg]=1
550 return 1
551 iscache[mypkg]=0
552 return 0
553
554 def match_to_list(mypkg,mylist):
555 """(pkgname,list)
556 Searches list for entries that matches the package.
557 """
558 matches=[]
559 for x in mylist:
560 if match_from_list(x,[mypkg]):
561 if x not in matches:
562 matches.append(x)
563 return matches
564
565 def best_match_to_list(mypkg,mylist):
566 """(pkgname,list)
567 Returns the most specific entry (assumed to be the longest one)
568 that matches the package given.
569 """
570 # XXX Assumption is wrong sometimes.
571 maxlen = 0
572 bestm = None
573 for x in match_to_list(mypkg,mylist):
574 if len(x) > maxlen:
575 maxlen = len(x)
576 bestm = x
577 return bestm
578
579
580
581 def match_from_list(mydep,candidate_list):
582 if mydep[0] == "!":
583 mydep = mydep[1:]
584
585 mycpv = dep_getcpv(mydep)
586 mycpv_cps = portage_versions.catpkgsplit(mycpv) # Can be None if not specific
587
588 if not mycpv_cps:
589 cat,pkg = portage_versions.catsplit(mycpv)
590 ver = None
591 rev = None
592 else:
593 cat,pkg,ver,rev = mycpv_cps
594 if mydep == mycpv:
595 raise KeyError, "Specific key requires an operator (%s) (try adding an '=')" % (mydep)
596
597 if ver and rev:
598 operator = get_operator(mydep)
599 if not operator:
600 writemsg("!!! Invanlid atom: %s\n" % mydep)
601 return []
602 else:
603 operator = None
604
605 mylist = []
606
607 if operator == None:
608 for x in candidate_list:
609 xs = portage_versions.pkgsplit(x)
610 if xs == None:
611 if x != mycpv:
612 continue
613 elif xs[0] != mycpv:
614 continue
615 mylist.append(x)
616
617 elif operator == "=": # Exact match
618 if mycpv in candidate_list:
619 mylist = [mycpv]
620
621 elif operator == "=*": # glob match
622 # The old verion ignored _tag suffixes... This one doesn't.
623 for x in candidate_list:
624 if x[0:len(mycpv)] == mycpv:
625 mylist.append(x)
626
627 elif operator == "~": # version, any revision, match
628 for x in candidate_list:
629 xs = portage_versions.catpkgsplit(x)
630 if xs[0:2] != mycpv_cps[0:2]:
631 continue
632 if xs[2] != ver:
633 continue
634 mylist.append(x)
635
636 elif operator in [">", ">=", "<", "<="]:
637 for x in candidate_list:
638 try:
639 result = portage_versions.pkgcmp(portage_versions.pkgsplit(x), [cat+"/"+pkg,ver,rev])
640 except SystemExit, e:
641 raise
642 except:
643 writemsg("\nInvalid package name: %s\n" % x)
644 sys.exit(73)
645 if result == None:
646 continue
647 elif operator == ">":
648 if result > 0:
649 mylist.append(x)
650 elif operator == ">=":
651 if result >= 0:
652 mylist.append(x)
653 elif operator == "<":
654 if result < 0:
655 mylist.append(x)
656 elif operator == "<=":
657 if result <= 0:
658 mylist.append(x)
659 else:
660 raise KeyError, "Unknown operator: %s" % mydep
661 else:
662 raise KeyError, "Unknown operator: %s" % mydep
663
664 return mylist
665
666
667 def prepare_prefdict(preferences):
668 myprefdict = {}
669 idx = 0
670 for atom in preferences:
671 if atom.cpv.key not in myprefdict:
672 myprefdict[atom.cpv.key] = []
673 myprefdict[atom.cpv.key].append((idx, atom))
674 idx += 1
675 myprefdict["____"] = idx
676 return myprefdict
677
678
679 def transform_dependspec(dependspec, prefdict):
680 def dotransform(dependspec, prefdict):
681 dependspec = copy.copy(dependspec)
682 elements = dependspec.elements
683 dependspec.elements = []
684 neworder = []
685 prio = prefdict["____"]
686 for element in elements[:]:
687 if isinstance(element, portage_syntax.DependSpec):
688 neworder.append(dotransform(element, prefdict))
689 elements.remove(element)
690 elif element.cpv.key in prefdict:
691 for (idx, pref) in prefdict[element.cpv.key]:
692 if pref.intersects(element):
693 if idx < prio:
694 prio = idx
695 if pref.encapsulates(element):
696 neworder.append((idx, element))
697 elements.remove(element)
698 else:
699 subdependspec = portage_syntax.DependSpec(element_class=portage_syntax.Atom)
700 if element.encapsulates(pref):
701 subsubdependspec = portage_syntax.DependSpec(element_class=portage_syntax.Atom)
702 subsubdependspec.add_element(pref)
703 subsubdependspec.add_element(element)
704 subdependspec.add_element(subsubdependspec)
705 else:
706 subdependspec.add_element(pref)
707 subdependspec.add_element(element)
708 subdependspec.preferential = True
709 neworder.append((idx, subdependspec))
710 elements.remove(element)
711 neworder.sort()
712 for element in neworder:
713 dependspec.add_element(element[1])
714 for element in elements:
715 dependspec.add_element(element)
716 return (prio, dependspec)
717 return dotransform(dependspec, prefdict)[1]
718
719
720 def transform_virtuals(pkg, dependspec, virtuals):
721 dependspec = copy.copy(dependspec)
722 elements = dependspec.elements
723 dependspec.elements = []
724 for element in elements:
725 if isinstance(element, portage_syntax.DependSpec):
726 dependspec.elements.append(transform_virtuals(pkg, element, virtuals))
727 elif element.cpv.key not in virtuals:
728 dependspec.elements.append(element)
729 else:
730 subdepspec = portage_syntax.DependSpec(element_class=portage_syntax.Atom)
731 subdepspec.preferential = True
732 for virtual in virtuals[element.cpv.key]:
733 atom = element.with_key(virtual)
734 if not atom.match(pkg):
735 subdepspec.add_element(element.with_key(virtual))
736 dependspec.elements.append(subdepspec)
737 return dependspec
738
739
740 class StateGraph(object):
741
742 def __init__(self):
743 # key : (bool, [GluePkg], [GluePkg], [Atom], [Atom])
744 self.pkgrec = {}
745 # key : [Atom]
746 self.unmatched_atoms = {}
747 # [Atom]
748 self.unmatched_preferentials = []
749 # key : [pkg, [[Atom]]]
750 self.preferential_atoms = {}
751 # key : [key]
752 self.reverse_preferentials = {}
753
754 def get_unmatched_atoms(self):
755 unmatched = []
756 for key in self.unmatched_atoms:
757 unmatched.append(self.unmatched_atoms[key][0])
758 return unmatched
759
760 def get_unmatched_preferentials(self):
761 return self.unmatched_preferentials[:]
762
763 def get_unneeded_packages(self):
764 unneeded = []
765 for key in self.pkgrec:
766 unneeded.extend(self.pkgrec[key][1])
767 return unneeded
768
769 def get_needed_packages(self):
770 needed = []
771 for key in self.pkgrec:
772 needed.extend(self.pkgrec[key][0])
773 return needed
774
775 def get_conflicts(self):
776 conflicts = []
777 for key in self.pkgrec:
778 slots = {}
779 in_conflict = False
780 for pkg in self.pkgrec[key][0]:
781 if pkg.slot in slots:
782 slots[pkg.slot].append(pkg)
783 in_conflict = True
784 else:
785 slots[pkg.slot] = [pkg]
786 if in_conflict:
787 for slot in slots:
788 if len(slots[slot]) > 1:
789 conflicts.append(slots[slot])
790 return conflicts
791
792 def add_package(self, pkg, keep=False):
793 key = pkg.key
794 if key not in self.pkgrec:
795 self.pkgrec[key] = ([], [pkg], [], [], [keep])
796 else:
797 if not self.pkgrec[key][4][0]:
798 self.pkgrec[key][4][0] = keep
799 self.pkgrec[key][1].append(pkg)
800 self._recheck(key)
801
802 def remove_package(self, pkg):
803 key = pkg.key
804 if pkg not in self.pkgrec[key][1]:
805 self._demote_pkg(pkg)
806 self.pkgrec[key][1].remove(pkg)
807 self._recheck(key)
808
809 def _recheck(self, key):
810 (used, unused, unmatched) = self._select_pkgs(key)
811 for pkg in used:
812 if pkg not in self.pkgrec[key][0]:
813 self._promote_pkg(pkg)
814 for pkg in unused:
815 if pkg not in self.pkgrec[key][1]:
816 self._demote_pkg(pkg)
817 if key in self.unmatched_atoms:
818 del self.unmatched_atoms[key]
819 for idx in range(len(self.unmatched_preferentials)-1, -1, -1):
820 if self.unmatched_preferentials[idx].cpv.key == key:
821 del self.unmatched_preferentials[idx]
822 if unmatched:
823 for atom in unmatched:
824 if atom in self.pkgrec[key][2]:
825 if key in self.unmatched_atoms:
826 self.unmatched_atoms[key].append(atom)
827 else:
828 self.unmatched_atoms[key] = [atom]
829 else:
830 self.unmatched_preferentials.append(atom)
831 if not self.pkgrec[key][0] and not self.pkgrec[key][1] and not self.pkgrec[key][2] and not self.pkgrec[key][3] and not self.pkgrec[key][4][0]:
832 del self.pkgrec[key]
833
834 def _select_pkgs(self, key):
835 allpkgs = self.pkgrec[key][0] + self.pkgrec[key][1]
836 used = []
837 unused = []
838 regular_atoms = []
839 unmatched = []
840 for atom in self.pkgrec[key][2] + self.pkgrec[key][3]:
841 if atom.blocks:
842 for pkg in allpkgs[:]:
843 if atom.match(pkg):
844 allpkgs.remove(pkg)
845 unused.append(pkg)
846 elif atom not in regular_atoms:
847 regular_atoms.append(atom)
848
849 if regular_atoms:
850 slots = {}
851 for pkg in allpkgs:
852 if pkg.slot not in slots:
853 slots[pkg.slot] = []
854 slots[pkg.slot].append(pkg)
855
856 used_slots = []
857 multislot_atoms = []
858 for atom in regular_atoms:
859 matched_slots = []
860 for slot in slots:
861 for pkg in slots[slot]:
862 if atom.match(pkg):
863 matched_slots.append(slot)
864 break
865 if len(matched_slots) > 1:
866 multislot_atoms.append(atom)
867 break
868 if atom in multislot_atoms:
869 continue
870 if not matched_slots:
871 unmatched.append(atom)
872 continue
873 slot = matched_slots[0]
874 if slot not in used_slots:
875 used_slots.append(slot)
876 for idx in range(len(slots[slot])-1, -1, -1):
877 if not atom.match(slots[slot][idx]):
878 unused.append(slots[slot][idx])
879 del slots[slot][idx]
880 used = []
881 uncertain = []
882 for slot in slots:
883 if slot in used_slots:
884 used.extend(slots[slot])
885 else:
886 uncertain.extend(slots[slot])
887 for atom in multislot_atoms:
888 matched = False
889 for pkg in used[:]:
890 if atom.match(pkg):
891 matched = True
892 break
893 if matched:
894 continue
895 for pkg in uncertain:
896 if atom.match(pkg):
897 uncertain.remove(pkg)
898 used.append(pkg)
899 matched = True
900 break
901 if not matched:
902 unmatched.append(atom)
903 unused.extend(uncertain)
904 elif self.pkgrec[key][4][0]:
905 used = allpkgs
906 else:
907 unused = allpkgs
908 return (used, unused, unmatched)
909
910 def _promote_pkg(self, pkg):
911 key = pkg.key
912 checks = {}
913 self.pkgrec[key][1].remove(pkg)
914 self.pkgrec[key][0].append(pkg)
915 if not pkg.rdeps.preferential:
916 for atom in pkg.rdeps.elements:
917 if atom.cpv.key not in self.pkgrec:
918 self.pkgrec[atom.cpv.key] = ([], [], [atom], [], [False])
919 else:
920 self.pkgrec[atom.cpv.key][2].append(atom)
921 if atom.cpv.key not in checks:
922 checks[atom.cpv.key] = True
923 else:
924 preflist = [pkg, []]
925 if isinstance(pkg.rdeps.elements[0], portage_syntax.Atom):
926 for atom in pkg.rdeps.elements:
927 preflist[1].append([atom])
928 else:
929 for option in pkg.rdeps.elements:
930 preflist[1].append([])
931 for atom in option.elements:
932 preflist[1][-1].append(atom)
933 for option in preflist[1]:
934 for atom in option:
935 if atom.cpv.key not in self.pkgrec:
936 self.pkgrec[atom.cpv.key] = ([], [], [], [atom], [False])
937 else:
938 self.pkgrec[atom.cpv.key][3].append(atom)
939 if atom.cpv.key not in self.reverse_preferentials:
940 self.reverse_preferentials[atom.cpv.key] = {}
941 if key not in self.reverse_preferentials[atom.cpv.key]:
942 self.reverse_preferentials[atom.cpv.key][key] = 1
943 else:
944 self.reverse_preferentials[atom.cpv.key][key] += 1
945 checks[atom.cpv.key] = True
946 if key not in self.preferential_atoms:
947 self.preferential_atoms[key] = [preflist]
948 else:
949 self.preferential_atoms[key].append(preflist)
950 self._check_preferentials(key)
951 if key in self.reverse_preferentials:
952 for parent in self.reverse_preferentials[key].keys():
953 self._check_preferentials(parent)
954 for key in checks:
955 if key in self.pkgrec:
956 self._recheck(key)
957
958 def _demote_pkg(self, pkg):
959 key = pkg.key
960 checks = {}
961 self.pkgrec[key][0].remove(pkg)
962 self.pkgrec[key][1].append(pkg)
963 if not pkg.rdeps.preferential:
964 for atom in pkg.rdeps.elements:
965 self.pkgrec[atom.cpv.key][2].remove(atom)
966 if not self.pkgrec[atom.cpv.key][0] and not self.pkgrec[atom.cpv.key][1] and not self.pkgrec[atom.cpv.key][2] and not self.pkgrec[atom.cpv.key][3]:
967 del self.pkgrec[atom.cpv.key]
968 if atom.cpv.key in self.unmatched_atoms:
969 del self.unmatched_atoms[atom.cpv.key]
970 else:
971 checks[atom.cpv.key] = True
972 else:
973 for idx in range(len(self.preferential_atoms[key])):
974 if self.preferential_atoms[key][idx][0] == pkg:
975 for atomlist in self.preferential_atoms[key][idx][1]:
976 for atom in atomlist:
977 self.pkgrec[atom.cpv.key][3].remove(atom)
978 self.reverse_preferentials[atom.cpv.key][key] -= 1
979 if not self.reverse_preferentials[atom.cpv.key][key]:
980 del self.reverse_preferentials[atom.cpv.key][key]
981 if not self.reverse_preferentials[atom.cpv.key]:
982 del self.reverse_preferentials[atom.cpv.key]
983 checks[atom.cpv.key] = True
984 del self.preferential_atoms[key][idx]
985 if not self.preferential_atoms[key]:
986 del self.preferential_atoms[key]
987 if key in self.reverse_preferentials:
988 for parent in self.reverse_preferentials[key].keys():
989 self._check_preferentials(parent)
990 for key in checks:
991 if key in self.pkgrec:
992 self._recheck(key)
993
994 def _check_preferentials(self, key):
995 checks = {}
996 for preflist in self.preferential_atoms[key]:
997 if len(preflist[1]) == 1:
998 all_matched = True
999 for atom in preflist[1][0]:
1000 matched = False
1001 for pkg in self.pkgrec[atom.cpv.key][0]:
1002 if atom.match(pkg):
1003 matched = True
1004 break
1005 if not matched:
1006 all_matched = False
1007 break
1008 if not all_matched:
1009 pkg = preflist[0]
1010 self._demote_pkg(pkg)
1011 self._promote_pkg(pkg)
1012 self._check_preferentials(key)
1013 return
1014 else:
1015 for idx in range(len(preflist[1])):
1016 all_matched = True
1017 for atom in preflist[1][idx]:
1018 matched = False
1019 for pkg in self.pkgrec[atom.cpv.key][0]:
1020 if atom.match(pkg):
1021 matched = True
1022 break
1023 if not matched:
1024 all_matched = False
1025 break
1026 if all_matched:
1027 removable = preflist[1][:idx] + preflist[1][idx+1:]
1028 preflist[1] = [preflist[1][idx]]
1029 for option in removable:
1030 for atom in option:
1031 self.pkgrec[atom.cpv.key][3].remove(atom)
1032 self.reverse_preferentials[atom.cpv.key][key] -= 1
1033 if not self.reverse_preferentials[atom.cpv.key][key]:
1034 del self.reverse_preferentials[atom.cpv.key][key]
1035 if not self.reverse_preferentials[atom.cpv.key]:
1036 del self.reverse_preferentials[atom.cpv.key]
1037 checks[atom.cpv.key] = True
1038 break
1039 for key in checks:
1040 self._recheck(key)

  ViewVC Help
Powered by ViewVC 1.1.20