bitbake/
[bitbake.git] / lib / bb / __init__.py
1 #!/usr/bin/python
2 # ex:ts=4:sw=4:sts=4:et
3 # -*- tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*-
4 """
5 BitBake Build System Python Library
6
7 Copyright (C) 2003  Holger Schurig
8 Copyright (C) 2003, 2004  Chris Larson
9
10 Based on Gentoo's portage.py.
11
12 This program is free software; you can redistribute it and/or modify it under
13 the terms of the GNU General Public License as published by the Free Software
14 Foundation; either version 2 of the License, or (at your option) any later
15 version.
16
17 This program is distributed in the hope that it will be useful, but WITHOUT
18 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
19 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
20
21 You should have received a copy of the GNU General Public License along with
22 this program; if not, write to the Free Software Foundation, Inc., 59 Temple
23 Place, Suite 330, Boston, MA 02111-1307 USA.
24 """
25
26 __version__ = "1.4.0"
27
28 __all__ = [
29
30     "debug",
31     "note",
32     "error",
33     "fatal",
34
35     "mkdirhier",
36     "movefile",
37
38     "tokenize",
39     "evaluate",
40     "flatten",
41     "relparse",
42     "ververify",
43     "isjustname",
44     "isspecific",
45     "pkgsplit",
46     "catpkgsplit",
47     "vercmp",
48     "pkgcmp",
49     "dep_parenreduce",
50     "dep_opconvert",
51     "digraph",
52
53 # fetch
54     "decodeurl",
55     "encodeurl",
56
57 # modules
58     "parse",
59     "data",
60     "event",
61     "build",
62     "fetch",
63     "manifest",
64     "methodpool",
65     "cache",
66  ]
67
68 whitespace = '\t\n\x0b\x0c\r '
69 lowercase = 'abcdefghijklmnopqrstuvwxyz'
70
71 import sys, os, types, re, string
72
73 #projectdir = os.path.dirname(os.path.dirname(os.path.abspath(sys.argv[0])))
74 projectdir = os.getcwd()
75
76 debug_level = 0
77
78 if "BBDEBUG" in os.environ:
79     level = int(os.environ["BBDEBUG"])
80     if level:
81         debug_level = level
82     else:
83         debug_level = 0
84
85 class VarExpandError(Exception):
86     pass
87
88 class MalformedUrl(Exception):
89     """Exception raised when encountering an invalid url"""
90
91
92 #######################################################################
93 #######################################################################
94 #
95 # SECTION: Debug
96 #
97 # PURPOSE: little functions to make yourself known
98 #
99 #######################################################################
100 #######################################################################
101
102 debug_prepend = ''
103
104
105 def debug(lvl, *args):
106     if debug_level >= lvl:
107         print debug_prepend + 'DEBUG:', ''.join(args)
108
109 def note(*args):
110     print debug_prepend + 'NOTE:', ''.join(args)
111
112 def error(*args):
113     print debug_prepend + 'ERROR:', ''.join(args)
114
115 def fatal(*args):
116     print debug_prepend + 'ERROR:', ''.join(args)
117     sys.exit(1)
118
119
120 #######################################################################
121 #######################################################################
122 #
123 # SECTION: File
124 #
125 # PURPOSE: Basic file and directory tree related functions
126 #
127 #######################################################################
128 #######################################################################
129
130 def mkdirhier(dir):
131     """Create a directory like 'mkdir -p', but does not complain if
132     directory already exists like os.makedirs
133     """
134
135     debug(3, "mkdirhier(%s)" % dir)
136     try:
137         os.makedirs(dir)
138         debug(2, "created " + dir)
139     except OSError, e:
140         if e.errno != 17: raise e
141
142
143 #######################################################################
144
145 import stat
146
147 def movefile(src,dest,newmtime=None,sstat=None):
148     """Moves a file from src to dest, preserving all permissions and
149     attributes; mtime will be preserved even when moving across
150     filesystems.  Returns true on success and false on failure. Move is
151     atomic.
152     """
153
154     #print "movefile("+src+","+dest+","+str(newmtime)+","+str(sstat)+")"
155     try:
156         if not sstat:
157             sstat=os.lstat(src)
158     except Exception, e:
159         print "!!! Stating source file failed... movefile()"
160         print "!!!",e
161         return None
162
163     destexists=1
164     try:
165         dstat=os.lstat(dest)
166     except:
167         dstat=os.lstat(os.path.dirname(dest))
168         destexists=0
169
170     if destexists:
171         if stat.S_ISLNK(dstat[stat.ST_MODE]):
172             try:
173                 os.unlink(dest)
174                 destexists=0
175             except Exception, e:
176                 pass
177
178     if stat.S_ISLNK(sstat[stat.ST_MODE]):
179         try:
180             target=os.readlink(src)
181             if destexists and not stat.S_ISDIR(dstat[stat.ST_MODE]):
182                 os.unlink(dest)
183             os.symlink(target,dest)
184 #            os.lchown(dest,sstat[stat.ST_UID],sstat[stat.ST_GID])
185             os.unlink(src)
186             return os.lstat(dest)
187         except Exception, e:
188             print "!!! failed to properly create symlink:"
189             print "!!!",dest,"->",target
190             print "!!!",e
191             return None
192
193     renamefailed=1
194     if sstat[stat.ST_DEV]==dstat[stat.ST_DEV]:
195         try:
196             ret=os.rename(src,dest)
197             renamefailed=0
198         except Exception, e:
199             import errno
200             if e[0]!=errno.EXDEV:
201                 # Some random error.
202                 print "!!! Failed to move",src,"to",dest
203                 print "!!!",e
204                 return None
205             # Invalid cross-device-link 'bind' mounted or actually Cross-Device
206
207     if renamefailed:
208         didcopy=0
209         if stat.S_ISREG(sstat[stat.ST_MODE]):
210             try: # For safety copy then move it over.
211                 shutil.copyfile(src,dest+"#new")
212                 os.rename(dest+"#new",dest)
213                 didcopy=1
214             except Exception, e:
215                 print '!!! copy',src,'->',dest,'failed.'
216                 print "!!!",e
217                 return None
218         else:
219             #we don't yet handle special, so we need to fall back to /bin/mv
220             a=getstatusoutput("/bin/mv -f "+"'"+src+"' '"+dest+"'")
221             if a[0]!=0:
222                 print "!!! Failed to move special file:"
223                 print "!!! '"+src+"' to '"+dest+"'"
224                 print "!!!",a
225                 return None # failure
226         try:
227             if didcopy:
228                 missingos.lchown(dest,sstat[stat.ST_UID],sstat[stat.ST_GID])
229                 os.chmod(dest, stat.S_IMODE(sstat[stat.ST_MODE])) # Sticky is reset on chown
230                 os.unlink(src)
231         except Exception, e:
232             print "!!! Failed to chown/chmod/unlink in movefile()"
233             print "!!!",dest
234             print "!!!",e
235             return None
236
237     if newmtime:
238         os.utime(dest,(newmtime,newmtime))
239     else:
240         os.utime(dest, (sstat[stat.ST_ATIME], sstat[stat.ST_MTIME]))
241         newmtime=sstat[stat.ST_MTIME]
242     return newmtime
243
244
245
246 #######################################################################
247 #######################################################################
248 #
249 # SECTION: Download
250 #
251 # PURPOSE: Download via HTTP, FTP, CVS, BITKEEPER, handling of MD5-signatures
252 #          and mirrors
253 #
254 #######################################################################
255 #######################################################################
256
257 def decodeurl(url):
258     """Decodes an URL into the tokens (scheme, network location, path,
259     user, password, parameters).
260
261     >>> decodeurl("http://www.google.com/index.html")
262     ('http', 'www.google.com', '/index.html', '', '', {})
263
264     CVS url with username, host and cvsroot. The cvs module to check out is in the
265     parameters:
266
267     >>> decodeurl("cvs://anoncvs@cvs.handhelds.org/cvs;module=familiar/dist/ipkg")
268     ('cvs', 'cvs.handhelds.org', '/cvs', 'anoncvs', '', {'module': 'familiar/dist/ipkg'})
269
270     Dito, but this time the username has a password part. And we also request a special tag
271     to check out.
272
273     >>> decodeurl("cvs://anoncvs:anonymous@cvs.handhelds.org/cvs;module=familiar/dist/ipkg;tag=V0-99-81")
274     ('cvs', 'cvs.handhelds.org', '/cvs', 'anoncvs', 'anonymous', {'tag': 'V0-99-81', 'module': 'familiar/dist/ipkg'})
275     """
276
277     m = re.compile('(?P<type>[^:]*)://((?P<user>.+)@)?(?P<location>[^;]+)(;(?P<parm>.*))?').match(url)
278     if not m:
279         raise MalformedUrl(url)
280
281     type = m.group('type')
282     location = m.group('location')
283     if not location:
284         raise MalformedUrl(url)
285     user = m.group('user')
286     parm = m.group('parm')
287     m = re.compile('(?P<host>[^/;]+)(?P<path>/[^;]+)').match(location)
288     if m:
289         host = m.group('host')
290         path = m.group('path')
291     else:
292         host = ""
293         path = location
294     if user:
295         m = re.compile('(?P<user>[^:]+)(:?(?P<pswd>.*))').match(user)
296         if m:
297             user = m.group('user')
298             pswd = m.group('pswd')
299     else:
300         user = ''
301         pswd = ''
302
303     p = {}
304     if parm:
305         for s in parm.split(';'):
306             s1,s2 = s.split('=')
307             p[s1] = s2
308
309     return (type, host, path, user, pswd, p)
310
311 #######################################################################
312
313 def encodeurl(decoded):
314     """Encodes a URL from tokens (scheme, network location, path,
315     user, password, parameters).
316
317     >>> encodeurl(['http', 'www.google.com', '/index.html', '', '', {}])
318     'http://www.google.com/index.html'
319
320     CVS with username, host and cvsroot. The cvs module to check out is in the
321     parameters:
322
323     >>> encodeurl(['cvs', 'cvs.handhelds.org', '/cvs', 'anoncvs', '', {'module': 'familiar/dist/ipkg'}])
324     'cvs://anoncvs@cvs.handhelds.org/cvs;module=familiar/dist/ipkg'
325
326     Dito, but this time the username has a password part. And we also request a special tag
327     to check out.
328
329     >>> encodeurl(['cvs', 'cvs.handhelds.org', '/cvs', 'anoncvs', 'anonymous', {'tag': 'V0-99-81', 'module': 'familiar/dist/ipkg'}])
330     'cvs://anoncvs:anonymous@cvs.handhelds.org/cvs;tag=V0-99-81;module=familiar/dist/ipkg'
331     """
332
333     (type, host, path, user, pswd, p) = decoded
334
335     if not type or not path:
336         fatal("invalid or missing parameters for url encoding")
337     url = '%s://' % type
338     if user:
339         url += "%s" % user
340         if pswd:
341             url += ":%s" % pswd
342         url += "@"
343     if host:
344         url += "%s" % host
345     url += "%s" % path
346     if p:
347         for parm in p.keys():
348             url += ";%s=%s" % (parm, p[parm])
349
350     return url
351
352 #######################################################################
353
354 def which(path, item, direction = 0):
355     """Useful function for locating a file in a PATH"""
356     found = ""
357     for p in (path or "").split(':'):
358         if os.path.exists(os.path.join(p, item)):
359             found = os.path.join(p, item)
360             if direction == 0:
361                 break
362     return found
363
364 #######################################################################
365
366
367
368
369 #######################################################################
370 #######################################################################
371 #
372 # SECTION: Dependency
373 #
374 # PURPOSE: Compare build & run dependencies
375 #
376 #######################################################################
377 #######################################################################
378
379 def tokenize(mystring):
380     """Breaks a string like 'foo? (bar) oni? (blah (blah))' into (possibly embedded) lists:
381
382     >>> tokenize("x")
383     ['x']
384     >>> tokenize("x y")
385     ['x', 'y']
386     >>> tokenize("(x y)")
387     [['x', 'y']]
388     >>> tokenize("(x y) b c")
389     [['x', 'y'], 'b', 'c']
390     >>> tokenize("foo? (bar) oni? (blah (blah))")
391     ['foo?', ['bar'], 'oni?', ['blah', ['blah']]]
392     >>> tokenize("sys-apps/linux-headers nls? (sys-devel/gettext)")
393     ['sys-apps/linux-headers', 'nls?', ['sys-devel/gettext']]
394     """
395
396     newtokens = []
397     curlist   = newtokens
398     prevlists = []
399     level     = 0
400     accum     = ""
401     for x in mystring:
402         if x=="(":
403             if accum:
404                 curlist.append(accum)
405                 accum=""
406             prevlists.append(curlist)
407             curlist=[]
408             level=level+1
409         elif x==")":
410             if accum:
411                 curlist.append(accum)
412                 accum=""
413             if level==0:
414                 print "!!! tokenizer: Unmatched left parenthesis in:\n'"+mystring+"'"
415                 return None
416             newlist=curlist
417             curlist=prevlists.pop()
418             curlist.append(newlist)
419             level=level-1
420         elif x in whitespace:
421             if accum:
422                 curlist.append(accum)
423                 accum=""
424         else:
425             accum=accum+x
426     if accum:
427         curlist.append(accum)
428     if (level!=0):
429         print "!!! tokenizer: Exiting with unterminated parenthesis in:\n'"+mystring+"'"
430         return None
431     return newtokens
432
433
434 #######################################################################
435
436 def evaluate(tokens,mydefines,allon=0):
437     """Removes tokens based on whether conditional definitions exist or not.
438     Recognizes !
439
440     >>> evaluate(['sys-apps/linux-headers', 'nls?', ['sys-devel/gettext']], {})
441     ['sys-apps/linux-headers']
442
443     Negate the flag:
444
445     >>> evaluate(['sys-apps/linux-headers', '!nls?', ['sys-devel/gettext']], {})
446     ['sys-apps/linux-headers', ['sys-devel/gettext']]
447
448     Define 'nls':
449
450     >>> evaluate(['sys-apps/linux-headers', 'nls?', ['sys-devel/gettext']], {"nls":1})
451     ['sys-apps/linux-headers', ['sys-devel/gettext']]
452
453     Turn allon on:
454
455     >>> evaluate(['sys-apps/linux-headers', 'nls?', ['sys-devel/gettext']], {}, True)
456     ['sys-apps/linux-headers', ['sys-devel/gettext']]
457     """
458
459     if tokens == None:
460         return None
461     mytokens = tokens + []        # this copies the list
462     pos = 0
463     while pos < len(mytokens):
464         if type(mytokens[pos]) == types.ListType:
465             evaluate(mytokens[pos], mydefines)
466             if not len(mytokens[pos]):
467                 del mytokens[pos]
468                 continue
469         elif mytokens[pos][-1] == "?":
470             cur = mytokens[pos][:-1]
471             del mytokens[pos]
472             if allon:
473                 if cur[0] == "!":
474                     del mytokens[pos]
475             else:
476                 if cur[0] == "!":
477                     if (cur[1:] in mydefines) and (pos < len(mytokens)):
478                         del mytokens[pos]
479                         continue
480                 elif (cur not in mydefines) and (pos < len(mytokens)):
481                     del mytokens[pos]
482                     continue
483         pos = pos + 1
484     return mytokens
485
486
487 #######################################################################
488
489 def flatten(mytokens):
490     """Converts nested arrays into a flat arrays:
491
492     >>> flatten([1,[2,3]])
493     [1, 2, 3]
494     >>> flatten(['sys-apps/linux-headers', ['sys-devel/gettext']])
495     ['sys-apps/linux-headers', 'sys-devel/gettext']
496     """
497
498     newlist=[]
499     for x in mytokens:
500         if type(x)==types.ListType:
501             newlist.extend(flatten(x))
502         else:
503             newlist.append(x)
504     return newlist
505
506
507 #######################################################################
508
509 _package_weights_ = {"pre":-2,"p":0,"alpha":-4,"beta":-3,"rc":-1}    # dicts are unordered
510 _package_ends_    = ["pre", "p", "alpha", "beta", "rc", "cvs", "bk", "HEAD" ]            # so we need ordered list
511
512 def relparse(myver):
513     """Parses the last elements of a version number into a triplet, that can
514     later be compared:
515
516     >>> relparse('1.2_pre3')
517     [1.2, -2, 3.0]
518     >>> relparse('1.2b')
519     [1.2, 98, 0]
520     >>> relparse('1.2')
521     [1.2, 0, 0]
522     """
523
524     number   = 0
525     p1       = 0
526     p2       = 0
527     mynewver = myver.split('_')
528     if len(mynewver)==2:
529         # an _package_weights_
530         number = float(mynewver[0])
531         match = 0
532         for x in _package_ends_:
533             elen = len(x)
534             if mynewver[1][:elen] == x:
535                 match = 1
536                 p1 = _package_weights_[x]
537                 try:
538                     p2 = float(mynewver[1][elen:])
539                 except:
540                     p2 = 0
541                 break
542         if not match:
543             # normal number or number with letter at end
544             divider = len(myver)-1
545             if myver[divider:] not in "1234567890":
546                 # letter at end
547                 p1 = ord(myver[divider:])
548                 number = float(myver[0:divider])
549             else:
550                 number = float(myver)
551     else:
552         # normal number or number with letter at end
553         divider = len(myver)-1
554         if myver[divider:] not in "1234567890":
555             #letter at end
556             p1     = ord(myver[divider:])
557             number = float(myver[0:divider])
558         else:
559             number = float(myver)
560     return [number,p1,p2]
561
562
563 #######################################################################
564
565 __ververify_cache__ = {}
566
567 def ververify(myorigval,silent=1):
568     """Returns 1 if given a valid version string, els 0. Valid versions are in the format
569
570     <v1>.<v2>...<vx>[a-z,_{_package_weights_}[vy]]
571
572     >>> ververify('2.4.20')
573     1
574     >>> ververify('2.4..20')        # two dots
575     0
576     >>> ververify('2.x.20')            # 'x' is not numeric
577     0
578     >>> ververify('2.4.20a')
579     1
580     >>> ververify('2.4.20cvs')        # only one trailing letter
581     0
582     >>> ververify('1a')
583     1
584     >>> ververify('test_a')            # no version at all
585     0
586     >>> ververify('2.4.20_beta1')
587     1
588     >>> ververify('2.4.20_beta')
589     1
590     >>> ververify('2.4.20_wrongext')    # _wrongext is no valid trailer
591     0
592     """
593
594     # Lookup the cache first
595     try:
596         return __ververify_cache__[myorigval]
597     except KeyError:
598         pass
599
600     if len(myorigval) == 0:
601         if not silent:
602             error("package version is empty")
603         __ververify_cache__[myorigval] = 0
604         return 0
605     myval = myorigval.split('.')
606     if len(myval)==0:
607         if not silent:
608             error("package name has empty version string")
609         __ververify_cache__[myorigval] = 0
610         return 0
611     # all but the last version must be a numeric
612     for x in myval[:-1]:
613         if not len(x):
614             if not silent:
615                 error("package version has two points in a row")
616             __ververify_cache__[myorigval] = 0
617             return 0
618         try:
619             foo = int(x)
620         except:
621             if not silent:
622                 error("package version contains non-numeric '"+x+"'")
623             __ververify_cache__[myorigval] = 0
624             return 0
625     if not len(myval[-1]):
626             if not silent:
627                 error("package version has trailing dot")
628             __ververify_cache__[myorigval] = 0
629             return 0
630     try:
631         foo = int(myval[-1])
632         __ververify_cache__[myorigval] = 1
633         return 1
634     except:
635         pass
636
637     # ok, our last component is not a plain number or blank, let's continue
638     if myval[-1][-1] in lowercase:
639         try:
640             foo = int(myval[-1][:-1])
641             return 1
642             __ververify_cache__[myorigval] = 1
643             # 1a, 2.0b, etc.
644         except:
645             pass
646     # ok, maybe we have a 1_alpha or 1_beta2; let's see
647     ep=string.split(myval[-1],"_")
648     if len(ep)!= 2:
649         if not silent:
650             error("package version has more than one letter at then end")
651         __ververify_cache__[myorigval] = 0
652         return 0
653     try:
654         foo = string.atoi(ep[0])
655     except:
656         # this needs to be numeric, i.e. the "1" in "1_alpha"
657         if not silent:
658             error("package version must have numeric part before the '_'")
659         __ververify_cache__[myorigval] = 0
660         return 0
661
662     for mye in _package_ends_:
663         if ep[1][0:len(mye)] == mye:
664             if len(mye) == len(ep[1]):
665                 # no trailing numeric is ok
666                 __ververify_cache__[myorigval] = 1
667                 return 1
668             else:
669                 try:
670                     foo = string.atoi(ep[1][len(mye):])
671                     __ververify_cache__[myorigval] = 1
672                     return 1
673                 except:
674                     # if no _package_weights_ work, *then* we return 0
675                     pass
676     if not silent:
677         error("package version extension after '_' is invalid")
678     __ververify_cache__[myorigval] = 0
679     return 0
680
681
682 def isjustname(mypkg):
683     myparts = string.split(mypkg,'-')
684     for x in myparts:
685         if ververify(x):
686             return 0
687     return 1
688
689
690 _isspecific_cache_={}
691
692 def isspecific(mypkg):
693     "now supports packages with no category"
694     try:
695         return __isspecific_cache__[mypkg]
696     except:
697         pass
698
699     mysplit = string.split(mypkg,"/")
700     if not isjustname(mysplit[-1]):
701             __isspecific_cache__[mypkg] = 1
702             return 1
703     __isspecific_cache__[mypkg] = 0
704     return 0
705
706
707 #######################################################################
708
709 __pkgsplit_cache__={}
710
711 def pkgsplit(mypkg, silent=1):
712
713     """This function can be used as a package verification function. If
714     it is a valid name, pkgsplit will return a list containing:
715     [pkgname, pkgversion(norev), pkgrev ].
716
717     >>> pkgsplit('')
718     >>> pkgsplit('x')
719     >>> pkgsplit('x-')
720     >>> pkgsplit('-1')
721     >>> pkgsplit('glibc-1.2-8.9-r7')
722     >>> pkgsplit('glibc-2.2.5-r7')
723     ['glibc', '2.2.5', 'r7']
724     >>> pkgsplit('foo-1.2-1')
725     >>> pkgsplit('Mesa-3.0')
726     ['Mesa', '3.0', 'r0']
727     """
728
729     try:
730         return __pkgsplit_cache__[mypkg]
731     except KeyError:
732         pass
733
734     myparts = string.split(mypkg,'-')
735     if len(myparts) < 2:
736         if not silent:
737             error("package name without name or version part")
738         __pkgsplit_cache__[mypkg] = None
739         return None
740     for x in myparts:
741         if len(x) == 0:
742             if not silent:
743                 error("package name with empty name or version part")
744             __pkgsplit_cache__[mypkg] = None
745             return None
746     # verify rev
747     revok = 0
748     myrev = myparts[-1]
749     ververify(myrev, silent)
750     if len(myrev) and myrev[0] == "r":
751         try:
752             string.atoi(myrev[1:])
753             revok = 1
754         except:
755             pass
756     if revok:
757         if ververify(myparts[-2]):
758             if len(myparts) == 2:
759                 __pkgsplit_cache__[mypkg] = None
760                 return None
761             else:
762                 for x in myparts[:-2]:
763                     if ververify(x):
764                         __pkgsplit_cache__[mypkg]=None
765                         return None
766                         # names can't have versiony looking parts
767                 myval=[string.join(myparts[:-2],"-"),myparts[-2],myparts[-1]]
768                 __pkgsplit_cache__[mypkg]=myval
769                 return myval
770         else:
771             __pkgsplit_cache__[mypkg] = None
772             return None
773
774     elif ververify(myparts[-1],silent):
775         if len(myparts)==1:
776             if not silent:
777                 print "!!! Name error in",mypkg+": missing name part."
778             __pkgsplit_cache__[mypkg]=None
779             return None
780         else:
781             for x in myparts[:-1]:
782                 if ververify(x):
783                     if not silent: error("package name has multiple version parts")
784                     __pkgsplit_cache__[mypkg] = None
785                     return None
786             myval = [string.join(myparts[:-1],"-"), myparts[-1],"r0"]
787             __pkgsplit_cache__[mypkg] = myval
788             return myval
789     else:
790         __pkgsplit_cache__[mypkg] = None
791         return None
792
793
794 #######################################################################
795
796 __catpkgsplit_cache__ = {}
797
798 def catpkgsplit(mydata,silent=1):
799     """returns [cat, pkgname, version, rev ]
800
801     >>> catpkgsplit('sys-libs/glibc-1.2-r7')
802     ['sys-libs', 'glibc', '1.2', 'r7']
803     >>> catpkgsplit('glibc-1.2-r7')
804     [None, 'glibc', '1.2', 'r7']
805     """
806
807     try:
808         return __catpkgsplit_cache__[mydata]
809     except KeyError:
810         pass
811
812     cat = os.path.basename(os.path.dirname(mydata))
813     mydata = os.path.join(cat, os.path.basename(mydata))
814     if mydata[-3:] == '.bb':
815         mydata = mydata[:-3]
816
817     mysplit = mydata.split("/")
818     p_split = None
819     splitlen = len(mysplit)
820     if splitlen == 1:
821         retval = [None]
822         p_split = pkgsplit(mydata,silent)
823     else:
824         retval = [mysplit[splitlen - 2]]
825         p_split = pkgsplit(mysplit[splitlen - 1],silent)
826     if not p_split:
827         __catpkgsplit_cache__[mydata] = None
828         return None
829     retval.extend(p_split)
830     __catpkgsplit_cache__[mydata] = retval
831     return retval
832
833
834 #######################################################################
835
836 __vercmp_cache__ = {}
837
838 def vercmp(val1,val2):
839     """This takes two version strings and returns an integer to tell you whether
840     the versions are the same, val1>val2 or val2>val1.
841
842     >>> vercmp('1', '2')
843     -1.0
844     >>> vercmp('2', '1')
845     1.0
846     >>> vercmp('1', '1.0')
847     0
848     >>> vercmp('1', '1.1')
849     -1.0
850     >>> vercmp('1.1', '1_p2')
851     1.0
852     """
853
854     # quick short-circuit
855     if val1 == val2:
856         return 0
857     valkey = val1+" "+val2
858
859     # cache lookup
860     try:
861         return __vercmp_cache__[valkey]
862         try:
863             return - __vercmp_cache__[val2+" "+val1]
864         except KeyError:
865             pass
866     except KeyError:
867         pass
868
869     # consider 1_p2 vc 1.1
870     # after expansion will become (1_p2,0) vc (1,1)
871     # then 1_p2 is compared with 1 before 0 is compared with 1
872     # to solve the bug we need to convert it to (1,0_p2)
873     # by splitting _prepart part and adding it back _after_expansion
874
875     val1_prepart = val2_prepart = ''
876     if val1.count('_'):
877         val1, val1_prepart = val1.split('_', 1)
878     if val2.count('_'):
879         val2, val2_prepart = val2.split('_', 1)
880
881     # replace '-' by '.'
882     # FIXME: Is it needed? can val1/2 contain '-'?
883
884     val1 = string.split(val1,'-')
885     if len(val1) == 2:
886         val1[0] = val1[0] +"."+ val1[1]
887     val2 = string.split(val2,'-')
888     if len(val2) == 2:
889         val2[0] = val2[0] +"."+ val2[1]
890
891     val1 = string.split(val1[0],'.')
892     val2 = string.split(val2[0],'.')
893
894     # add back decimal point so that .03 does not become "3" !
895     for x in range(1,len(val1)):
896         if val1[x][0] == '0' :
897             val1[x] = '.' + val1[x]
898     for x in range(1,len(val2)):
899         if val2[x][0] == '0' :
900             val2[x] = '.' + val2[x]
901
902     # extend varion numbers
903     if len(val2) < len(val1):
904         val2.extend(["0"]*(len(val1)-len(val2)))
905     elif len(val1) < len(val2):
906         val1.extend(["0"]*(len(val2)-len(val1)))
907
908     # add back _prepart tails
909     if val1_prepart:
910         val1[-1] += '_' + val1_prepart
911     if val2_prepart:
912         val2[-1] += '_' + val2_prepart
913     # The above code will extend version numbers out so they
914     # have the same number of digits.
915     for x in range(0,len(val1)):
916         cmp1 = relparse(val1[x])
917         cmp2 = relparse(val2[x])
918         for y in range(0,3):
919             myret = cmp1[y] - cmp2[y]
920             if myret != 0:
921                 __vercmp_cache__[valkey] = myret
922                 return myret
923     __vercmp_cache__[valkey] = 0
924     return 0
925
926
927 #######################################################################
928
929 def pkgcmp(pkg1,pkg2):
930     """ Compares two packages, which should have been split via
931     pkgsplit(). if the return value val is less than zero, then pkg2 is
932     newer than pkg1, zero if equal and positive if older.
933
934     >>> pkgcmp(['glibc', '2.2.5', 'r7'], ['glibc', '2.2.5', 'r7'])
935     0
936     >>> pkgcmp(['glibc', '2.2.5', 'r4'], ['glibc', '2.2.5', 'r7'])
937     -1
938     >>> pkgcmp(['glibc', '2.2.5', 'r7'], ['glibc', '2.2.5', 'r2'])
939     1
940     """
941
942     mycmp = vercmp(pkg1[1],pkg2[1])
943     if mycmp > 0:
944         return 1
945     if mycmp < 0:
946         return -1
947     r1=string.atoi(pkg1[2][1:])
948     r2=string.atoi(pkg2[2][1:])
949     if r1 > r2:
950         return 1
951     if r2 > r1:
952         return -1
953     return 0
954
955
956 #######################################################################
957
958 def dep_parenreduce(mysplit, mypos=0):
959     """Accepts a list of strings, and converts '(' and ')' surrounded items to sub-lists:
960
961     >>> dep_parenreduce([''])
962     ['']
963     >>> dep_parenreduce(['1', '2', '3'])
964     ['1', '2', '3']
965     >>> dep_parenreduce(['1', '(', '2', '3', ')', '4'])
966     ['1', ['2', '3'], '4']
967     """
968
969     while mypos < len(mysplit):
970         if mysplit[mypos] == "(":
971             firstpos = mypos
972             mypos = mypos + 1
973             while mypos < len(mysplit):
974                 if mysplit[mypos] == ")":
975                     mysplit[firstpos:mypos+1] = [mysplit[firstpos+1:mypos]]
976                     mypos = firstpos
977                     break
978                 elif mysplit[mypos] == "(":
979                     # recurse
980                     mysplit = dep_parenreduce(mysplit,mypos)
981                 mypos = mypos + 1
982         mypos = mypos + 1
983     return mysplit
984
985
986 def dep_opconvert(mysplit, myuse):
987     "Does dependency operator conversion"
988
989     mypos   = 0
990     newsplit = []
991     while mypos < len(mysplit):
992         if type(mysplit[mypos]) == types.ListType:
993             newsplit.append(dep_opconvert(mysplit[mypos],myuse))
994             mypos += 1
995         elif mysplit[mypos] == ")":
996             # mismatched paren, error
997             return None
998         elif mysplit[mypos]=="||":
999             if ((mypos+1)>=len(mysplit)) or (type(mysplit[mypos+1])!=types.ListType):
1000                 # || must be followed by paren'd list
1001                 return None
1002             try:
1003                 mynew = dep_opconvert(mysplit[mypos+1],myuse)
1004             except Exception, e:
1005                 error("unable to satisfy OR dependancy: " + string.join(mysplit," || "))
1006                 raise e
1007             mynew[0:0] = ["||"]
1008             newsplit.append(mynew)
1009             mypos += 2
1010         elif mysplit[mypos][-1] == "?":
1011             # use clause, i.e "gnome? ( foo bar )"
1012             # this is a quick and dirty hack so that repoman can enable all USE vars:
1013             if (len(myuse) == 1) and (myuse[0] == "*"):
1014                 # enable it even if it's ! (for repoman) but kill it if it's
1015                 # an arch variable that isn't for this arch. XXX Sparc64?
1016                 if (mysplit[mypos][:-1] not in settings.usemask) or \
1017                         (mysplit[mypos][:-1]==settings["ARCH"]):
1018                     enabled=1
1019                 else:
1020                     enabled=0
1021             else:
1022                 if mysplit[mypos][0] == "!":
1023                     myusevar = mysplit[mypos][1:-1]
1024                     enabled = not myusevar in myuse
1025                     #if myusevar in myuse:
1026                     #    enabled = 0
1027                     #else:
1028                     #    enabled = 1
1029                 else:
1030                     myusevar=mysplit[mypos][:-1]
1031                     enabled = myusevar in myuse
1032                     #if myusevar in myuse:
1033                     #    enabled=1
1034                     #else:
1035                     #    enabled=0
1036             if (mypos +2 < len(mysplit)) and (mysplit[mypos+2] == ":"):
1037                 # colon mode
1038                 if enabled:
1039                     # choose the first option
1040                     if type(mysplit[mypos+1]) == types.ListType:
1041                         newsplit.append(dep_opconvert(mysplit[mypos+1],myuse))
1042                     else:
1043                         newsplit.append(mysplit[mypos+1])
1044                 else:
1045                     # choose the alternate option
1046                     if type(mysplit[mypos+1]) == types.ListType:
1047                         newsplit.append(dep_opconvert(mysplit[mypos+3],myuse))
1048                     else:
1049                         newsplit.append(mysplit[mypos+3])
1050                 mypos += 4
1051             else:
1052                 # normal use mode
1053                 if enabled:
1054                     if type(mysplit[mypos+1]) == types.ListType:
1055                         newsplit.append(dep_opconvert(mysplit[mypos+1],myuse))
1056                     else:
1057                         newsplit.append(mysplit[mypos+1])
1058                 # otherwise, continue
1059                 mypos += 2
1060         else:
1061             # normal item
1062             newsplit.append(mysplit[mypos])
1063             mypos += 1
1064     return newsplit
1065
1066 class digraph:
1067     """beautiful directed graph object"""
1068
1069     def __init__(self):
1070         self.dict={}
1071         #okeys = keys, in order they were added (to optimize firstzero() ordering)
1072         self.okeys=[]
1073         self.__callback_cache=[]
1074
1075     def __str__(self):
1076         str = ""
1077         for key in self.okeys:
1078             str += "%s:\t%s\n" % (key, self.dict[key][1])
1079         return str
1080
1081     def addnode(self,mykey,myparent):
1082         if not mykey in self.dict:
1083             self.okeys.append(mykey)
1084             if myparent==None:
1085                 self.dict[mykey]=[0,[]]
1086             else:
1087                 self.dict[mykey]=[0,[myparent]]
1088                 self.dict[myparent][0]=self.dict[myparent][0]+1
1089             return
1090         if myparent and (not myparent in self.dict[mykey][1]):
1091             self.dict[mykey][1].append(myparent)
1092             self.dict[myparent][0]=self.dict[myparent][0]+1
1093
1094     def delnode(self,mykey, ref = 1):
1095         """Delete a node
1096
1097         If ref is 1, remove references to this node from other nodes.
1098         If ref is 2, remove nodes that reference this node."""
1099         if not mykey in self.dict:
1100             return
1101         for x in self.dict[mykey][1]:
1102             self.dict[x][0]=self.dict[x][0]-1
1103         del self.dict[mykey]
1104         while 1:
1105             try:
1106                 self.okeys.remove(mykey)
1107             except ValueError:
1108                 break
1109         if ref:
1110             __kill = []
1111             for k in self.okeys:
1112                 if mykey in self.dict[k][1]:
1113                     if ref == 1 or ref == 2:
1114                         self.dict[k][1].remove(mykey)
1115                     if ref == 2:
1116                         __kill.append(k)
1117             for l in __kill:
1118                 self.delnode(l, ref)
1119
1120     def allnodes(self):
1121         "returns all nodes in the dictionary"
1122         return self.dict.keys()
1123
1124     def firstzero(self):
1125         "returns first node with zero references, or NULL if no such node exists"
1126         for x in self.okeys:
1127             if self.dict[x][0]==0:
1128                 return x
1129         return None
1130
1131     def firstnonzero(self):
1132         "returns first node with nonzero references, or NULL if no such node exists"
1133         for x in self.okeys:
1134             if self.dict[x][0]!=0:
1135                 return x
1136         return None
1137
1138
1139     def allzeros(self):
1140         "returns all nodes with zero references, or NULL if no such node exists"
1141         zerolist = []
1142         for x in self.dict.keys():
1143             if self.dict[x][0]==0:
1144                 zerolist.append(x)
1145         return zerolist
1146
1147     def hasallzeros(self):
1148         "returns 0/1, Are all nodes zeros? 1 : 0"
1149         zerolist = []
1150         for x in self.dict.keys():
1151             if self.dict[x][0]!=0:
1152                 return 0
1153         return 1
1154
1155     def empty(self):
1156         if len(self.dict)==0:
1157             return 1
1158         return 0
1159
1160     def hasnode(self,mynode):
1161         return mynode in self.dict
1162
1163     def getparents(self, item):
1164         if not self.hasnode(item):
1165             return []
1166         return self.dict[item][1]
1167
1168     def getchildren(self, item):
1169         if not self.hasnode(item):
1170             return []
1171         children = [i for i in self.okeys if item in self.getparents(i)]
1172         return children
1173
1174     def walkdown(self, item, callback, debug = None, usecache = False):
1175         if not self.hasnode(item):
1176             return 0
1177
1178         if usecache:
1179             if self.__callback_cache.count(item):
1180                 if debug:
1181                     print "hit cache for item: %s" % item
1182                 return 1
1183
1184         parents = self.getparents(item)
1185         children = self.getchildren(item)
1186         for p in parents:
1187             if p in children:
1188 #                print "%s is both parent and child of %s" % (p, item)
1189                 if usecache:
1190                     self.__callback_cache.append(p)
1191                 ret = callback(self, p)
1192                 if ret == 0:
1193                     return 0
1194                 continue
1195             if item == p:
1196                 print "eek, i'm my own parent!"
1197                 return 0
1198             if debug:
1199                 print "item: %s, p: %s" % (item, p)
1200             ret = self.walkdown(p, callback, debug, usecache)
1201             if ret == 0:
1202                 return 0
1203         if usecache:
1204             self.__callback_cache.append(item)
1205         return callback(self, item)
1206
1207     def walkup(self, item, callback):
1208         if not self.hasnode(item):
1209             return 0
1210
1211         parents = self.getparents(item)
1212         children = self.getchildren(item)
1213         for c in children:
1214             if c in parents:
1215                 ret = callback(self, item)
1216                 if ret == 0:
1217                     return 0
1218                 continue
1219             if item == c:
1220                 print "eek, i'm my own child!"
1221                 return 0
1222             ret = self.walkup(c, callback)
1223             if ret == 0:
1224                 return 0
1225         return callback(self, item)
1226
1227     def copy(self):
1228         mygraph=digraph()
1229         for x in self.dict.keys():
1230             mygraph.dict[x]=self.dict[x][:]
1231             mygraph.okeys=self.okeys[:]
1232         return mygraph
1233
1234 if __name__ == "__main__":
1235     import doctest, bb
1236     doctest.testmod(bb)