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