code.grnet.gr Git - pithos/blob - snf-pithos-backend/pithos/backends/lib/sqlite/node.py

   1 # Copyright 2011-2012 GRNET S.A. All rights reserved.
   2 #
   3 # Redistribution and use in source and binary forms, with or
   4 # without modification, are permitted provided that the following
   5 # conditions are met:
   6 #
   7 #   1. Redistributions of source code must retain the above
   8 #      copyright notice, this list of conditions and the following
   9 #      disclaimer.
  10 #
  11 #   2. Redistributions in binary form must reproduce the above
  12 #      copyright notice, this list of conditions and the following
  13 #      disclaimer in the documentation and/or other materials
  14 #      provided with the distribution.
  15 #
  16 # THIS SOFTWARE IS PROVIDED BY GRNET S.A. ``AS IS'' AND ANY EXPRESS
  17 # OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18 # WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19 # PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL GRNET S.A OR
  20 # CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  23 # USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  24 # AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25 # LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  26 # ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27 # POSSIBILITY OF SUCH DAMAGE.
  28 #
  29 # The views and conclusions contained in the software and
  30 # documentation are those of the authors and should not be
  31 # interpreted as representing official policies, either expressed
  32 # or implied, of GRNET S.A.
  33
  34 from time import time
  35
  36 from dbworker import DBWorker
  37
  38 from pithos.backends.filter import parse_filters
  39
  40
  41 ROOTNODE  = 0
  42
  43 ( SERIAL, NODE, HASH, SIZE, TYPE, SOURCE, MTIME, MUSER, UUID, CHECKSUM, CLUSTER ) = range(11)
  44
  45 ( MATCH_PREFIX, MATCH_EXACT ) = range(2)
  46
  47 inf = float('inf')
  48
  49
  50 def strnextling(prefix):
  51     """Return the first unicode string
  52        greater than but not starting with given prefix.
  53        strnextling('hello') -> 'hellp'
  54     """
  55     if not prefix:
  56         ## all strings start with the null string,
  57         ## therefore we have to approximate strnextling('')
  58         ## with the last unicode character supported by python
  59         ## 0x10ffff for wide (32-bit unicode) python builds
  60         ## 0x00ffff for narrow (16-bit unicode) python builds
  61         ## We will not autodetect. 0xffff is safe enough.
  62         return unichr(0xffff)
  63     s = prefix[:-1]
  64     c = ord(prefix[-1])
  65     if c >= 0xffff:
  66         raise RuntimeError
  67     s += unichr(c+1)
  68     return s
  69
  70 def strprevling(prefix):
  71     """Return an approximation of the last unicode string
  72        less than but not starting with given prefix.
  73        strprevling(u'hello') -> u'helln\\xffff'
  74     """
  75     if not prefix:
  76         ## There is no prevling for the null string
  77         return prefix
  78     s = prefix[:-1]
  79     c = ord(prefix[-1])
  80     if c > 0:
  81         s += unichr(c-1) + unichr(0xffff)
  82     return s
  83
  84
  85 _propnames = {
  86     'serial'    : 0,
  87     'node'      : 1,
  88     'hash'      : 2,
  89     'size'      : 3,
  90     'type'      : 4,
  91     'source'    : 5,
  92     'mtime'     : 6,
  93     'muser'     : 7,
  94     'uuid'      : 8,
  95     'checksum'  : 9,
  96     'cluster'   : 10
  97 }
  98
  99
 100 class Node(DBWorker):
 101     """Nodes store path organization and have multiple versions.
 102        Versions store object history and have multiple attributes.
 103        Attributes store metadata.
 104     """
 105
 106     # TODO: Provide an interface for included and excluded clusters.
 107
 108     def __init__(self, **params):
 109         DBWorker.__init__(self, **params)
 110         execute = self.execute
 111
 112         execute(""" pragma foreign_keys = on """)
 113
 114         execute(""" create table if not exists nodes
 115                           ( node       integer primary key,
 116                             parent     integer default 0,
 117                             path       text    not null default '',
 118                             foreign key (parent)
 119                             references nodes(node)
 120                             on update cascade
 121                             on delete cascade ) """)
 122         execute(""" create unique index if not exists idx_nodes_path
 123                     on nodes(path) """)
 124
 125         execute(""" create table if not exists policy
 126                           ( node   integer,
 127                             key    text,
 128                             value  text,
 129                             primary key (node, key)
 130                             foreign key (node)
 131                             references nodes(node)
 132                             on update cascade
 133                             on delete cascade ) """)
 134
 135         execute(""" create table if not exists statistics
 136                           ( node       integer,
 137                             population integer not null default 0,
 138                             size       integer not null default 0,
 139                             mtime      integer,
 140                             cluster    integer not null default 0,
 141                             primary key (node, cluster)
 142                             foreign key (node)
 143                             references nodes(node)
 144                             on update cascade
 145                             on delete cascade ) """)
 146
 147         execute(""" create table if not exists versions
 148                           ( serial     integer primary key,
 149                             node       integer,
 150                             hash       text,
 151                             size       integer not null default 0,
 152                             type       text    not null default '',
 153                             source     integer,
 154                             mtime      integer,
 155                             muser      text    not null default '',
 156                             uuid       text    not null default '',
 157                             checksum   text    not null default '',
 158                             cluster    integer not null default 0,
 159                             foreign key (node)
 160                             references nodes(node)
 161                             on update cascade
 162                             on delete cascade ) """)
 163         execute(""" create index if not exists idx_versions_node_mtime
 164                     on versions(node, mtime) """)
 165         execute(""" create index if not exists idx_versions_node_uuid
 166                     on versions(uuid) """)
 167
 168         execute(""" create table if not exists attributes
 169                           ( serial integer,
 170                             domain text,
 171                             key    text,
 172                             value  text,
 173                             primary key (serial, domain, key)
 174                             foreign key (serial)
 175                             references versions(serial)
 176                             on update cascade
 177                             on delete cascade ) """)
 178
 179         q = "insert or ignore into nodes(node, parent) values (?, ?)"
 180         execute(q, (ROOTNODE, ROOTNODE))
 181
 182     def node_create(self, parent, path):
 183         """Create a new node from the given properties.
 184            Return the node identifier of the new node.
 185         """
 186
 187         q = ("insert into nodes (parent, path) "
 188              "values (?, ?)")
 189         props = (parent, path)
 190         return self.execute(q, props).lastrowid
 191
 192     def node_lookup(self, path):
 193         """Lookup the current node of the given path.
 194            Return None if the path is not found.
 195         """
 196
 197         q = "select node from nodes where path = ?"
 198         self.execute(q, (path,))
 199         r = self.fetchone()
 200         if r is not None:
 201             return r[0]
 202         return None
 203
 204     def node_get_properties(self, node):
 205         """Return the node's (parent, path).
 206            Return None if the node is not found.
 207         """
 208
 209         q = "select parent, path from nodes where node = ?"
 210         self.execute(q, (node,))
 211         return self.fetchone()
 212
 213     def node_get_versions(self, node, keys=(), propnames=_propnames):
 214         """Return the properties of all versions at node.
 215            If keys is empty, return all properties in the order
 216            (serial, node, hash, size, type, source, mtime, muser, uuid, checksum, cluster).
 217         """
 218
 219         q = ("select serial, node, hash, size, type, source, mtime, muser, uuid, checksum, cluster "
 220              "from versions "
 221              "where node = ?")
 222         self.execute(q, (node,))
 223         r = self.fetchall()
 224         if r is None:
 225             return r
 226
 227         if not keys:
 228             return r
 229         return [[p[propnames[k]] for k in keys if k in propnames] for p in r]
 230
 231     def node_count_children(self, node):
 232         """Return node's child count."""
 233
 234         q = "select count(node) from nodes where parent = ? and node != 0"
 235         self.execute(q, (node,))
 236         r = self.fetchone()
 237         if r is None:
 238             return 0
 239         return r[0]
 240
 241     def node_purge_children(self, parent, before=inf, cluster=0):
 242         """Delete all versions with the specified
 243            parent and cluster, and return
 244            the hashes and size of versions deleted.
 245            Clears out nodes with no remaining versions.
 246         """
 247
 248         execute = self.execute
 249         q = ("select count(serial), sum(size) from versions "
 250              "where node in (select node "
 251                             "from nodes "
 252                             "where parent = ?) "
 253              "and cluster = ? "
 254              "and mtime <= ?")
 255         args = (parent, cluster, before)
 256         execute(q, args)
 257         nr, size = self.fetchone()
 258         if not nr:
 259             return (), 0
 260         mtime = time()
 261         self.statistics_update(parent, -nr, -size, mtime, cluster)
 262         self.statistics_update_ancestors(parent, -nr, -size, mtime, cluster)
 263
 264         q = ("select hash from versions "
 265              "where node in (select node "
 266                             "from nodes "
 267                             "where parent = ?) "
 268              "and cluster = ? "
 269              "and mtime <= ?")
 270         execute(q, args)
 271         hashes = [r[0] for r in self.fetchall()]
 272         q = ("delete from versions "
 273              "where node in (select node "
 274                             "from nodes "
 275                             "where parent = ?) "
 276              "and cluster = ? "
 277              "and mtime <= ?")
 278         execute(q, args)
 279         q = ("delete from nodes "
 280              "where node in (select node from nodes n "
 281                             "where (select count(serial) "
 282                                    "from versions "
 283                                    "where node = n.node) = 0 "
 284                             "and parent = ?)")
 285         execute(q, (parent,))
 286         return hashes, size
 287
 288     def node_purge(self, node, before=inf, cluster=0):
 289         """Delete all versions with the specified
 290            node and cluster, and return
 291            the hashes and size of versions deleted.
 292            Clears out the node if it has no remaining versions.
 293         """
 294
 295         execute = self.execute
 296         q = ("select count(serial), sum(size) from versions "
 297              "where node = ? "
 298              "and cluster = ? "
 299              "and mtime <= ?")
 300         args = (node, cluster, before)
 301         execute(q, args)
 302         nr, size = self.fetchone()
 303         if not nr:
 304             return (), 0
 305         mtime = time()
 306         self.statistics_update_ancestors(node, -nr, -size, mtime, cluster)
 307
 308         q = ("select hash from versions "
 309              "where node = ? "
 310              "and cluster = ? "
 311              "and mtime <= ?")
 312         execute(q, args)
 313         hashes = [r[0] for r in self.fetchall()]
 314         q = ("delete from versions "
 315              "where node = ? "
 316              "and cluster = ? "
 317              "and mtime <= ?")
 318         execute(q, args)
 319         q = ("delete from nodes "
 320              "where node in (select node from nodes n "
 321                             "where (select count(serial) "
 322                                    "from versions "
 323                                    "where node = n.node) = 0 "
 324                             "and node = ?)")
 325         execute(q, (node,))
 326         return hashes, size
 327
 328     def node_remove(self, node):
 329         """Remove the node specified.
 330            Return false if the node has children or is not found.
 331         """
 332
 333         if self.node_count_children(node):
 334             return False
 335
 336         mtime = time()
 337         q = ("select count(serial), sum(size), cluster "
 338              "from versions "
 339              "where node = ? "
 340              "group by cluster")
 341         self.execute(q, (node,))
 342         for population, size, cluster in self.fetchall():
 343             self.statistics_update_ancestors(node, -population, -size, mtime, cluster)
 344
 345         q = "delete from nodes where node = ?"
 346         self.execute(q, (node,))
 347         return True
 348
 349     def policy_get(self, node):
 350         q = "select key, value from policy where node = ?"
 351         self.execute(q, (node,))
 352         return dict(self.fetchall())
 353
 354     def policy_set(self, node, policy):
 355         q = "insert or replace into policy (node, key, value) values (?, ?, ?)"
 356         self.executemany(q, ((node, k, v) for k, v in policy.iteritems()))
 357
 358     def statistics_get(self, node, cluster=0):
 359         """Return population, total size and last mtime
 360            for all versions under node that belong to the cluster.
 361         """
 362
 363         q = ("select population, size, mtime from statistics "
 364              "where node = ? and cluster = ?")
 365         self.execute(q, (node, cluster))
 366         return self.fetchone()
 367
 368     def statistics_update(self, node, population, size, mtime, cluster=0):
 369         """Update the statistics of the given node.
 370            Statistics keep track the population, total
 371            size of objects and mtime in the node's namespace.
 372            May be zero or positive or negative numbers.
 373         """
 374
 375         qs = ("select population, size from statistics "
 376               "where node = ? and cluster = ?")
 377         qu = ("insert or replace into statistics (node, population, size, mtime, cluster) "
 378               "values (?, ?, ?, ?, ?)")
 379         self.execute(qs, (node, cluster))
 380         r = self.fetchone()
 381         if r is None:
 382             prepopulation, presize = (0, 0)
 383         else:
 384             prepopulation, presize = r
 385         population += prepopulation
 386         size += presize
 387         self.execute(qu, (node, population, size, mtime, cluster))
 388
 389     def statistics_update_ancestors(self, node, population, size, mtime, cluster=0):
 390         """Update the statistics of the given node's parent.
 391            Then recursively update all parents up to the root.
 392            Population is not recursive.
 393         """
 394
 395         while True:
 396             if node == 0:
 397                 break
 398             props = self.node_get_properties(node)
 399             if props is None:
 400                 break
 401             parent, path = props
 402             self.statistics_update(parent, population, size, mtime, cluster)
 403             node = parent
 404             population = 0 # Population isn't recursive
 405
 406     def statistics_latest(self, node, before=inf, except_cluster=0):
 407         """Return population, total size and last mtime
 408            for all latest versions under node that
 409            do not belong to the cluster.
 410         """
 411
 412         execute = self.execute
 413         fetchone = self.fetchone
 414
 415         # The node.
 416         props = self.node_get_properties(node)
 417         if props is None:
 418             return None
 419         parent, path = props
 420
 421         # The latest version.
 422         q = ("select serial, node, hash, size, type, source, mtime, muser, uuid, checksum, cluster "
 423              "from versions "
 424              "where serial = (select max(serial) "
 425                              "from versions "
 426                              "where node = ? and mtime < ?) "
 427              "and cluster != ?")
 428         execute(q, (node, before, except_cluster))
 429         props = fetchone()
 430         if props is None:
 431             return None
 432         mtime = props[MTIME]
 433
 434         # First level, just under node (get population).
 435         q = ("select count(serial), sum(size), max(mtime) "
 436              "from versions v "
 437              "where serial = (select max(serial) "
 438                              "from versions "
 439                              "where node = v.node and mtime < ?) "
 440              "and cluster != ? "
 441              "and node in (select node "
 442                           "from nodes "
 443                           "where parent = ?)")
 444         execute(q, (before, except_cluster, node))
 445         r = fetchone()
 446         if r is None:
 447             return None
 448         count = r[0]
 449         mtime = max(mtime, r[2])
 450         if count == 0:
 451             return (0, 0, mtime)
 452
 453         # All children (get size and mtime).
 454         # This is why the full path is stored.
 455         q = ("select count(serial), sum(size), max(mtime) "
 456              "from versions v "
 457              "where serial = (select max(serial) "
 458                              "from versions "
 459                              "where node = v.node and mtime < ?) "
 460              "and cluster != ? "
 461              "and node in (select node "
 462                           "from nodes "
 463                           "where path like ? escape '\\')")
 464         execute(q, (before, except_cluster, self.escape_like(path) + '%'))
 465         r = fetchone()
 466         if r is None:
 467             return None
 468         size = r[1] - props[SIZE]
 469         mtime = max(mtime, r[2])
 470         return (count, size, mtime)
 471
 472     def version_create(self, node, hash, size, type, source, muser, uuid, checksum, cluster=0):
 473         """Create a new version from the given properties.
 474            Return the (serial, mtime) of the new version.
 475         """
 476
 477         q = ("insert into versions (node, hash, size, type, source, mtime, muser, uuid, checksum, cluster) "
 478              "values (?, ?, ?, ?, ?, ?, ?, ?, ?, ?)")
 479         mtime = time()
 480         props = (node, hash, size, type, source, mtime, muser, uuid, checksum, cluster)
 481         serial = self.execute(q, props).lastrowid
 482         self.statistics_update_ancestors(node, 1, size, mtime, cluster)
 483         return serial, mtime
 484
 485     def version_lookup(self, node, before=inf, cluster=0):
 486         """Lookup the current version of the given node.
 487            Return a list with its properties:
 488            (serial, node, hash, size, type, source, mtime, muser, uuid, checksum, cluster)
 489            or None if the current version is not found in the given cluster.
 490         """
 491
 492         q = ("select serial, node, hash, size, type, source, mtime, muser, uuid, checksum, cluster "
 493              "from versions "
 494              "where serial = (select max(serial) "
 495                              "from versions "
 496                              "where node = ? and mtime < ?) "
 497              "and cluster = ?")
 498         self.execute(q, (node, before, cluster))
 499         props = self.fetchone()
 500         if props is not None:
 501             return props
 502         return None
 503
 504     def version_get_properties(self, serial, keys=(), propnames=_propnames):
 505         """Return a sequence of values for the properties of
 506            the version specified by serial and the keys, in the order given.
 507            If keys is empty, return all properties in the order
 508            (serial, node, hash, size, type, source, mtime, muser, uuid, checksum, cluster).
 509         """
 510
 511         q = ("select serial, node, hash, size, type, source, mtime, muser, uuid, checksum, cluster "
 512              "from versions "
 513              "where serial = ?")
 514         self.execute(q, (serial,))
 515         r = self.fetchone()
 516         if r is None:
 517             return r
 518
 519         if not keys:
 520             return r
 521         return [r[propnames[k]] for k in keys if k in propnames]
 522
 523     def version_put_property(self, serial, key, value):
 524         """Set value for the property of version specified by key."""
 525
 526         if key not in _propnames:
 527             return
 528         q = "update versions set %s = ? where serial = ?" % key
 529         self.execute(q, (value, serial))
 530
 531     def version_recluster(self, serial, cluster):
 532         """Move the version into another cluster."""
 533
 534         props = self.version_get_properties(serial)
 535         if not props:
 536             return
 537         node = props[NODE]
 538         size = props[SIZE]
 539         oldcluster = props[CLUSTER]
 540         if cluster == oldcluster:
 541             return
 542
 543         mtime = time()
 544         self.statistics_update_ancestors(node, -1, -size, mtime, oldcluster)
 545         self.statistics_update_ancestors(node, 1, size, mtime, cluster)
 546
 547         q = "update versions set cluster = ? where serial = ?"
 548         self.execute(q, (cluster, serial))
 549
 550     def version_remove(self, serial):
 551         """Remove the serial specified."""
 552
 553         props = self.version_get_properties(serial)
 554         if not props:
 555             return
 556         node = props[NODE]
 557         hash = props[HASH]
 558         size = props[SIZE]
 559         cluster = props[CLUSTER]
 560
 561         mtime = time()
 562         self.statistics_update_ancestors(node, -1, -size, mtime, cluster)
 563
 564         q = "delete from versions where serial = ?"
 565         self.execute(q, (serial,))
 566         return hash, size
 567
 568     def attribute_get(self, serial, domain, keys=()):
 569         """Return a list of (key, value) pairs of the version specified by serial.
 570            If keys is empty, return all attributes.
 571            Othwerise, return only those specified.
 572         """
 573
 574         execute = self.execute
 575         if keys:
 576             marks = ','.join('?' for k in keys)
 577             q = ("select key, value from attributes "
 578                  "where key in (%s) and serial = ? and domain = ?" % (marks,))
 579             execute(q, keys + (serial, domain))
 580         else:
 581             q = "select key, value from attributes where serial = ? and domain = ?"
 582             execute(q, (serial, domain))
 583         return self.fetchall()
 584
 585     def attribute_set(self, serial, domain, items):
 586         """Set the attributes of the version specified by serial.
 587            Receive attributes as an iterable of (key, value) pairs.
 588         """
 589
 590         q = ("insert or replace into attributes (serial, domain, key, value) "
 591              "values (?, ?, ?, ?)")
 592         self.executemany(q, ((serial, domain, k, v) for k, v in items))
 593
 594     def attribute_del(self, serial, domain, keys=()):
 595         """Delete attributes of the version specified by serial.
 596            If keys is empty, delete all attributes.
 597            Otherwise delete those specified.
 598         """
 599
 600         if keys:
 601             q = "delete from attributes where serial = ? and domain = ? and key = ?"
 602             self.executemany(q, ((serial, domain, key) for key in keys))
 603         else:
 604             q = "delete from attributes where serial = ? and domain = ?"
 605             self.execute(q, (serial, domain))
 606
 607     def attribute_copy(self, source, dest):
 608         q = ("insert or replace into attributes "
 609              "select ?, domain, key, value from attributes "
 610              "where serial = ?")
 611         self.execute(q, (dest, source))
 612
 613     def _construct_filters(self, domain, filterq):
 614         if not domain or not filterq:
 615             return None, None
 616
 617         subqlist = []
 618         append = subqlist.append
 619         included, excluded, opers = parse_filters(filterq)
 620         args = []
 621
 622         if included:
 623             subq = "exists (select 1 from attributes where serial = v.serial and domain = ? and "
 624             subq += "(" + ' or '.join(('key = ?' for x in included)) + ")"
 625             subq += ")"
 626             args += [domain]
 627             args += included
 628             append(subq)
 629
 630         if excluded:
 631             subq = "not exists (select 1 from attributes where serial = v.serial and domain = ? and "
 632             subq += "(" + ' or '.join(('key = ?' for x in excluded)) + ")"
 633             subq += ")"
 634             args += [domain]
 635             args += excluded
 636             append(subq)
 637
 638         if opers:
 639             for k, o, v in opers:
 640                 subq = "exists (select 1 from attributes where serial = v.serial and domain = ? and "
 641                 subq += "key = ? and value %s ?" % (o,)
 642                 subq += ")"
 643                 args += [domain, k, v]
 644                 append(subq)
 645
 646         if not subqlist:
 647             return None, None
 648
 649         subq = ' and ' + ' and '.join(subqlist)
 650
 651         return subq, args
 652
 653     def _construct_paths(self, pathq):
 654         if not pathq:
 655             return None, None
 656
 657         subqlist = []
 658         args = []
 659         print pathq
 660         for path, match in pathq:
 661             if match == MATCH_PREFIX:
 662                 subqlist.append("n.path like ? escape '\\'")
 663                 args.append(self.escape_like(path) + '%')
 664             elif match == MATCH_EXACT:
 665                 subqlist.append("n.path = ?")
 666                 args.append(path)
 667
 668         subq = ' and (' + ' or '.join(subqlist) + ')'
 669         args = tuple(args)
 670
 671         return subq, args
 672
 673     def _construct_size(self, sizeq):
 674         if not sizeq or len(sizeq) != 2:
 675             return None, None
 676
 677         subq = ''
 678         args = []
 679         if sizeq[0]:
 680             subq += " and v.size >= ?"
 681             args += [sizeq[0]]
 682         if sizeq[1]:
 683             subq += " and v.size < ?"
 684             args += [sizeq[1]]
 685
 686         return subq, args
 687
 688     def latest_attribute_keys(self, parent, domain, before=inf, except_cluster=0, pathq=[]):
 689         """Return a list with all keys pairs defined
 690            for all latest versions under parent that
 691            do not belong to the cluster.
 692         """
 693
 694         # TODO: Use another table to store before=inf results.
 695         q = ("select distinct a.key "
 696              "from attributes a, versions v, nodes n "
 697              "where v.serial = (select max(serial) "
 698                                "from versions "
 699                                "where node = v.node and mtime < ?) "
 700              "and v.cluster != ? "
 701              "and v.node in (select node "
 702                             "from nodes "
 703                             "where parent = ?) "
 704              "and a.serial = v.serial "
 705              "and a.domain = ? "
 706              "and n.node = v.node")
 707         args = (before, except_cluster, parent, domain)
 708         subq, subargs = self._construct_paths(pathq)
 709         if subq is not None:
 710             q += subq
 711             args += subargs
 712         self.execute(q, args)
 713         return [r[0] for r in self.fetchall()]
 714
 715     def latest_version_list(self, parent, prefix='', delimiter=None,
 716                             start='', limit=10000, before=inf,
 717                             except_cluster=0, pathq=[], domain=None,
 718                             filterq=[], sizeq=None, all_props=False):
 719         """Return a (list of (path, serial) tuples, list of common prefixes)
 720            for the current versions of the paths with the given parent,
 721            matching the following criteria.
 722
 723            The property tuple for a version is returned if all
 724            of these conditions are true:
 725
 726                 a. parent matches
 727
 728                 b. path > start
 729
 730                 c. path starts with prefix (and paths in pathq)
 731
 732                 d. version is the max up to before
 733
 734                 e. version is not in cluster
 735
 736                 f. the path does not have the delimiter occuring
 737                    after the prefix, or ends with the delimiter
 738
 739                 g. serial matches the attribute filter query.
 740
 741                    A filter query is a comma-separated list of
 742                    terms in one of these three forms:
 743
 744                    key
 745                        an attribute with this key must exist
 746
 747                    !key
 748                        an attribute with this key must not exist
 749
 750                    key ?op value
 751                        the attribute with this key satisfies the value
 752                        where ?op is one of =, != <=, >=, <, >.
 753
 754                 h. the size is in the range set by sizeq
 755
 756            The list of common prefixes includes the prefixes
 757            matching up to the first delimiter after prefix,
 758            and are reported only once, as "virtual directories".
 759            The delimiter is included in the prefixes.
 760
 761            If arguments are None, then the corresponding matching rule
 762            will always match.
 763
 764            Limit applies to the first list of tuples returned.
 765
 766            If all_props is True, return all properties after path, not just serial.
 767         """
 768
 769         execute = self.execute
 770
 771         if not start or start < prefix:
 772             start = strprevling(prefix)
 773         nextling = strnextling(prefix)
 774
 775         q = ("select distinct n.path, %s "
 776              "from versions v, nodes n "
 777              "where v.serial = (select max(serial) "
 778                                "from versions "
 779                                "where node = v.node and mtime < ?) "
 780              "and v.cluster != ? "
 781              "and v.node in (select node "
 782                             "from nodes "
 783                             "where parent = ?) "
 784              "and n.node = v.node "
 785              "and n.path > ? and n.path < ?")
 786         if not all_props:
 787             q = q % "v.serial"
 788         else:
 789             q = q % "v.serial, v.node, v.hash, v.size, v.type, v.source, v.mtime, v.muser, v.uuid, v.checksum, v.cluster"
 790         args = [before, except_cluster, parent, start, nextling]
 791
 792         subq, subargs = self._construct_paths(pathq)
 793         if subq is not None:
 794             q += subq
 795             args += subargs
 796         subq, subargs = self._construct_size(sizeq)
 797         if subq is not None:
 798             q += subq
 799             args += subargs
 800         subq, subargs = self._construct_filters(domain, filterq)
 801         if subq is not None:
 802             q += subq
 803             args += subargs
 804         else:
 805             q = q.replace("attributes a, ", "")
 806             q = q.replace("and a.serial = v.serial ", "")
 807         q += " order by n.path"
 808
 809         if not delimiter:
 810             q += " limit ?"
 811             args.append(limit)
 812             execute(q, args)
 813             return self.fetchall(), ()
 814
 815         pfz = len(prefix)
 816         dz = len(delimiter)
 817         count = 0
 818         fetchone = self.fetchone
 819         prefixes = []
 820         pappend = prefixes.append
 821         matches = []
 822         mappend = matches.append
 823
 824         execute(q, args)
 825         while True:
 826             props = fetchone()
 827             if props is None:
 828                 break
 829             path = props[0]
 830             serial = props[1]
 831             idx = path.find(delimiter, pfz)
 832
 833             if idx < 0:
 834                 mappend(props)
 835                 count += 1
 836                 if count >= limit:
 837                     break
 838                 continue
 839
 840             if idx + dz == len(path):
 841                 mappend(props)
 842                 count += 1
 843                 continue # Get one more, in case there is a path.
 844             pf = path[:idx + dz]
 845             pappend(pf)
 846             if count >= limit:
 847                 break
 848
 849             args[3] = strnextling(pf) # New start.
 850             execute(q, args)
 851
 852         return matches, prefixes
 853
 854     def latest_uuid(self, uuid):
 855         """Return a (path, serial) tuple, for the latest version of the given uuid."""
 856
 857         q = ("select n.path, v.serial "
 858              "from versions v, nodes n "
 859              "where v.serial = (select max(serial) "
 860                                "from versions "
 861                                "where uuid = ?) "
 862              "and n.node = v.node")
 863         self.execute(q, (uuid,))
 864         return self.fetchone()