Statistics
| Branch: | Tag: | Revision:

root / snf-pithos-backend / pithos / backends / lib / sqlite / node.py @ 73673127

History | View | Annotate | Download (31.5 kB)

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()