Statistics
| Branch: | Tag: | Revision:

root / pithos / backends / lib / sqlite / node.py @ 95d47e1a

History | View | Annotate | Download (28.9 kB)

1
# Copyright 2011 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
import re
35

    
36
from time import time
37

    
38
from dbworker import DBWorker
39

    
40

    
41
ROOTNODE  = 0
42

    
43
( SERIAL, NODE, HASH, SIZE, SOURCE, MTIME, MUSER, CLUSTER ) = range(8)
44

    
45
inf = float('inf')
46

    
47

    
48
def strnextling(prefix):
49
    """Return the first unicode string
50
       greater than but not starting with given prefix.
51
       strnextling('hello') -> 'hellp'
52
    """
53
    if not prefix:
54
        ## all strings start with the null string,
55
        ## therefore we have to approximate strnextling('')
56
        ## with the last unicode character supported by python
57
        ## 0x10ffff for wide (32-bit unicode) python builds
58
        ## 0x00ffff for narrow (16-bit unicode) python builds
59
        ## We will not autodetect. 0xffff is safe enough.
60
        return unichr(0xffff)
61
    s = prefix[:-1]
62
    c = ord(prefix[-1])
63
    if c >= 0xffff:
64
        raise RuntimeError
65
    s += unichr(c+1)
66
    return s
67

    
68
def strprevling(prefix):
69
    """Return an approximation of the last unicode string
70
       less than but not starting with given prefix.
71
       strprevling(u'hello') -> u'helln\\xffff'
72
    """
73
    if not prefix:
74
        ## There is no prevling for the null string
75
        return prefix
76
    s = prefix[:-1]
77
    c = ord(prefix[-1])
78
    if c > 0:
79
        s += unichr(c-1) + unichr(0xffff)
80
    return s
81

    
82

    
83
_regexfilter = re.compile('(!?)\s*([\w-]+)\s*(==|!=|<=|>=|<|>)?\s*(.*)$', re.UNICODE)
84

    
85
_propnames = {
86
    'serial'    : 0,
87
    'node'      : 1,
88
    'hash'      : 2,
89
    'size'      : 3,
90
    'source'    : 4,
91
    'mtime'     : 5,
92
    'muser'     : 6,
93
    'cluster'   : 7,
94
}
95

    
96

    
97
class Node(DBWorker):
98
    """Nodes store path organization and have multiple versions.
99
       Versions store object history and have multiple attributes.
100
       Attributes store metadata.
101
    """
102
    
103
    # TODO: Provide an interface for included and excluded clusters.
104
    
105
    def __init__(self, **params):
106
        DBWorker.__init__(self, **params)
107
        execute = self.execute
108
        
109
        execute(""" pragma foreign_keys = on """)
110
        
111
        execute(""" create table if not exists nodes
112
                          ( node       integer primary key,
113
                            parent     integer default 0,
114
                            path       text    not null default '',
115
                            foreign key (parent)
116
                            references nodes(node)
117
                            on update cascade
118
                            on delete cascade ) """)
119
        execute(""" create unique index if not exists idx_nodes_path
120
                    on nodes(path) """)
121
        
122
        execute(""" create table if not exists policy
123
                          ( node   integer,
124
                            key    text,
125
                            value  text,
126
                            primary key (node, key)
127
                            foreign key (node)
128
                            references nodes(node)
129
                            on update cascade
130
                            on delete cascade ) """)
131
        
132
        execute(""" create table if not exists statistics
133
                          ( node       integer,
134
                            population integer not null default 0,
135
                            size       integer not null default 0,
136
                            mtime      integer,
137
                            cluster    integer not null default 0,
138
                            primary key (node, cluster)
139
                            foreign key (node)
140
                            references nodes(node)
141
                            on update cascade
142
                            on delete cascade ) """)
143
        
144
        execute(""" create table if not exists versions
145
                          ( serial     integer primary key,
146
                            node       integer,
147
                            hash       text,
148
                            size       integer not null default 0,
149
                            source     integer,
150
                            mtime      integer,
151
                            muser      text    not null default '',
152
                            cluster    integer not null default 0,
153
                            foreign key (node)
154
                            references nodes(node)
155
                            on update cascade
156
                            on delete cascade ) """)
157
        execute(""" create index if not exists idx_versions_node_mtime
158
                    on versions(node, mtime) """)
159
        
160
        execute(""" create table if not exists attributes
161
                          ( serial integer,
162
                            key    text,
163
                            value  text,
164
                            primary key (serial, key)
165
                            foreign key (serial)
166
                            references versions(serial)
167
                            on update cascade
168
                            on delete cascade ) """)
169
        
170
        q = "insert or ignore into nodes(node, parent) values (?, ?)"
171
        execute(q, (ROOTNODE, ROOTNODE))
172
    
173
    def node_create(self, parent, path):
174
        """Create a new node from the given properties.
175
           Return the node identifier of the new node.
176
        """
177
        
178
        q = ("insert into nodes (parent, path) "
179
             "values (?, ?)")
180
        props = (parent, path)
181
        return self.execute(q, props).lastrowid
182
    
183
    def node_lookup(self, path):
184
        """Lookup the current node of the given path.
185
           Return None if the path is not found.
186
        """
187
        
188
        q = "select node from nodes where path = ?"
189
        self.execute(q, (path,))
190
        r = self.fetchone()
191
        if r is not None:
192
            return r[0]
193
        return None
194
    
195
    def node_get_properties(self, node):
196
        """Return the node's (parent, path).
197
           Return None if the node is not found.
198
        """
199
        
200
        q = "select parent, path from nodes where node = ?"
201
        self.execute(q, (node,))
202
        return self.fetchone()
203
    
204
    def node_get_versions(self, node, keys=(), propnames=_propnames):
205
        """Return the properties of all versions at node.
206
           If keys is empty, return all properties in the order
207
           (serial, node, size, source, mtime, muser, cluster).
208
        """
209
        
210
        q = ("select serial, node, hash, size, source, mtime, muser, cluster "
211
             "from versions "
212
             "where node = ?")
213
        self.execute(q, (node,))
214
        r = self.fetchall()
215
        if r is None:
216
            return r
217
        
218
        if not keys:
219
            return r
220
        return [[p[propnames[k]] for k in keys if k in propnames] for p in r]
221
    
222
    def node_count_children(self, node):
223
        """Return node's child count."""
224
        
225
        q = "select count(node) from nodes where parent = ? and node != 0"
226
        self.execute(q, (node,))
227
        r = self.fetchone()
228
        if r is None:
229
            return 0
230
        return r[0]
231
    
232
    def node_purge_children(self, parent, before=inf, cluster=0):
233
        """Delete all versions with the specified
234
           parent and cluster, and return
235
           the hashes of versions deleted.
236
           Clears out nodes with no remaining versions.
237
        """
238
        
239
        execute = self.execute
240
        q = ("select count(serial), sum(size) from versions "
241
             "where node in (select node "
242
                            "from nodes "
243
                            "where parent = ?) "
244
             "and cluster = ? "
245
             "and mtime <= ?")
246
        args = (parent, cluster, before)
247
        execute(q, args)
248
        nr, size = self.fetchone()
249
        if not nr:
250
            return ()
251
        mtime = time()
252
        self.statistics_update(parent, -nr, -size, mtime, cluster)
253
        self.statistics_update_ancestors(parent, -nr, -size, mtime, cluster)
254
        
255
        q = ("select hash from versions "
256
             "where node in (select node "
257
                            "from nodes "
258
                            "where parent = ?) "
259
             "and cluster = ? "
260
             "and mtime <= ?")
261
        execute(q, args)
262
        hashes = [r[0] for r in self.fetchall()]
263
        q = ("delete from versions "
264
             "where node in (select node "
265
                            "from nodes "
266
                            "where parent = ?) "
267
             "and cluster = ? "
268
             "and mtime <= ?")
269
        execute(q, args)
270
        q = ("delete from nodes "
271
             "where node in (select node from nodes n "
272
                            "where (select count(serial) "
273
                                   "from versions "
274
                                   "where node = n.node) = 0 "
275
                            "and parent = ?)")
276
        execute(q, (parent,))
277
        return hashes
278
    
279
    def node_purge(self, node, before=inf, cluster=0):
280
        """Delete all versions with the specified
281
           node and cluster, and return
282
           the hashes of versions deleted.
283
           Clears out the node if it has no remaining versions.
284
        """
285
        
286
        execute = self.execute
287
        q = ("select count(serial), sum(size) from versions "
288
             "where node = ? "
289
             "and cluster = ? "
290
             "and mtime <= ?")
291
        args = (node, cluster, before)
292
        execute(q, args)
293
        nr, size = self.fetchone()
294
        if not nr:
295
            return ()
296
        mtime = time()
297
        self.statistics_update_ancestors(node, -nr, -size, mtime, cluster)
298
        
299
        q = ("select hash from versions "
300
             "where node = ? "
301
             "and cluster = ? "
302
             "and mtime <= ?")
303
        execute(q, args)
304
        hashes = [r[0] for r in self.fetchall()]
305
        q = ("delete from versions "
306
             "where node = ? "
307
             "and cluster = ? "
308
             "and mtime <= ?")
309
        execute(q, args)
310
        q = ("delete from nodes "
311
             "where node in (select node from nodes n "
312
                            "where (select count(serial) "
313
                                   "from versions "
314
                                   "where node = n.node) = 0 "
315
                            "and node = ?)")
316
        execute(q, (node,))
317
        return hashes
318
    
319
    def node_remove(self, node):
320
        """Remove the node specified.
321
           Return false if the node has children or is not found.
322
        """
323
        
324
        if self.node_count_children(node):
325
            return False
326
        
327
        mtime = time()
328
        q = ("select count(serial), sum(size), cluster "
329
             "from versions "
330
             "where node = ? "
331
             "group by cluster")
332
        self.execute(q, (node,))
333
        for population, size, cluster in self.fetchall():
334
            self.statistics_update_ancestors(node, -population, -size, mtime, cluster)
335
        
336
        q = "delete from nodes where node = ?"
337
        self.execute(q, (node,))
338
        return True
339
    
340
    def policy_get(self, node):
341
        q = "select key, value from policy where node = ?"
342
        self.execute(q, (node,))
343
        return dict(self.fetchall())
344
    
345
    def policy_set(self, node, policy):
346
        q = "insert or replace into policy (node, key, value) values (?, ?, ?)"
347
        self.executemany(q, ((node, k, v) for k, v in policy.iteritems()))
348
    
349
    def statistics_get(self, node, cluster=0):
350
        """Return population, total size and last mtime
351
           for all versions under node that belong to the cluster.
352
        """
353
        
354
        q = ("select population, size, mtime from statistics "
355
             "where node = ? and cluster = ?")
356
        self.execute(q, (node, cluster))
357
        return self.fetchone()
358
    
359
    def statistics_update(self, node, population, size, mtime, cluster=0):
360
        """Update the statistics of the given node.
361
           Statistics keep track the population, total
362
           size of objects and mtime in the node's namespace.
363
           May be zero or positive or negative numbers.
364
        """
365
        
366
        qs = ("select population, size from statistics "
367
              "where node = ? and cluster = ?")
368
        qu = ("insert or replace into statistics (node, population, size, mtime, cluster) "
369
              "values (?, ?, ?, ?, ?)")
370
        self.execute(qs, (node, cluster))
371
        r = self.fetchone()
372
        if r is None:
373
            prepopulation, presize = (0, 0)
374
        else:
375
            prepopulation, presize = r
376
        population += prepopulation
377
        size += presize
378
        self.execute(qu, (node, population, size, mtime, cluster))
379
    
380
    def statistics_update_ancestors(self, node, population, size, mtime, cluster=0):
381
        """Update the statistics of the given node's parent.
382
           Then recursively update all parents up to the root.
383
           Population is not recursive.
384
        """
385
        
386
        while True:
387
            if node == 0:
388
                break
389
            props = self.node_get_properties(node)
390
            if props is None:
391
                break
392
            parent, path = props
393
            self.statistics_update(parent, population, size, mtime, cluster)
394
            node = parent
395
            population = 0 # Population isn't recursive
396
    
397
    def statistics_latest(self, node, before=inf, except_cluster=0):
398
        """Return population, total size and last mtime
399
           for all latest versions under node that
400
           do not belong to the cluster.
401
        """
402
        
403
        execute = self.execute
404
        fetchone = self.fetchone
405
        
406
        # The node.
407
        props = self.node_get_properties(node)
408
        if props is None:
409
            return None
410
        parent, path = props
411
        
412
        # The latest version.
413
        q = ("select serial, node, hash, size, source, mtime, muser, cluster "
414
             "from versions "
415
             "where serial = (select max(serial) "
416
                             "from versions "
417
                             "where node = ? and mtime < ?) "
418
             "and cluster != ?")
419
        execute(q, (node, before, except_cluster))
420
        props = fetchone()
421
        if props is None:
422
            return None
423
        mtime = props[MTIME]
424
        
425
        # First level, just under node (get population).
426
        q = ("select count(serial), sum(size), max(mtime) "
427
             "from versions v "
428
             "where serial = (select max(serial) "
429
                             "from versions "
430
                             "where node = v.node and mtime < ?) "
431
             "and cluster != ? "
432
             "and node in (select node "
433
                          "from nodes "
434
                          "where parent = ?)")
435
        execute(q, (before, except_cluster, node))
436
        r = fetchone()
437
        if r is None:
438
            return None
439
        count = r[0]
440
        mtime = max(mtime, r[2])
441
        if count == 0:
442
            return (0, 0, mtime)
443
        
444
        # All children (get size and mtime).
445
        # XXX: This is why the full path is stored.
446
        q = ("select count(serial), sum(size), max(mtime) "
447
             "from versions v "
448
             "where serial = (select max(serial) "
449
                             "from versions "
450
                             "where node = v.node and mtime < ?) "
451
             "and cluster != ? "
452
             "and node in (select node "
453
                          "from nodes "
454
                          "where path like ? escape '\\')")
455
        execute(q, (before, except_cluster, self.escape_like(path) + '%'))
456
        r = fetchone()
457
        if r is None:
458
            return None
459
        size = r[1] - props[SIZE]
460
        mtime = max(mtime, r[2])
461
        return (count, size, mtime)
462
    
463
    def version_create(self, node, hash, size, source, muser, cluster=0):
464
        """Create a new version from the given properties.
465
           Return the (serial, mtime) of the new version.
466
        """
467
        
468
        q = ("insert into versions (node, hash, size, source, mtime, muser, cluster) "
469
             "values (?, ?, ?, ?, ?, ?, ?)")
470
        mtime = time()
471
        props = (node, hash, size, source, mtime, muser, cluster)
472
        serial = self.execute(q, props).lastrowid
473
        self.statistics_update_ancestors(node, 1, size, mtime, cluster)
474
        return serial, mtime
475
    
476
    def version_lookup(self, node, before=inf, cluster=0):
477
        """Lookup the current version of the given node.
478
           Return a list with its properties:
479
           (serial, node, hash, size, source, mtime, muser, cluster)
480
           or None if the current version is not found in the given cluster.
481
        """
482
        
483
        q = ("select serial, node, hash, size, source, mtime, muser, cluster "
484
             "from versions "
485
             "where serial = (select max(serial) "
486
                             "from versions "
487
                             "where node = ? and mtime < ?) "
488
             "and cluster = ?")
489
        self.execute(q, (node, before, cluster))
490
        props = self.fetchone()
491
        if props is not None:
492
            return props
493
        return None
494
    
495
    def version_get_properties(self, serial, keys=(), propnames=_propnames):
496
        """Return a sequence of values for the properties of
497
           the version specified by serial and the keys, in the order given.
498
           If keys is empty, return all properties in the order
499
           (serial, node, hash, size, source, mtime, muser, cluster).
500
        """
501
        
502
        q = ("select serial, node, hash, size, source, mtime, muser, cluster "
503
             "from versions "
504
             "where serial = ?")
505
        self.execute(q, (serial,))
506
        r = self.fetchone()
507
        if r is None:
508
            return r
509
        
510
        if not keys:
511
            return r
512
        return [r[propnames[k]] for k in keys if k in propnames]
513
    
514
    def version_recluster(self, serial, cluster):
515
        """Move the version into another cluster."""
516
        
517
        props = self.version_get_properties(serial)
518
        if not props:
519
            return
520
        node = props[NODE]
521
        size = props[SIZE]
522
        oldcluster = props[CLUSTER]
523
        if cluster == oldcluster:
524
            return
525
        
526
        mtime = time()
527
        self.statistics_update_ancestors(node, -1, -size, mtime, oldcluster)
528
        self.statistics_update_ancestors(node, 1, size, mtime, cluster)
529
        
530
        q = "update versions set cluster = ? where serial = ?"
531
        self.execute(q, (cluster, serial))
532
    
533
    def version_remove(self, serial):
534
        """Remove the serial specified."""
535
        
536
        props = self.version_get_properties(serial)
537
        if not props:
538
            return
539
        node = props[NODE]
540
        hash = props[HASH]
541
        size = props[SIZE]
542
        cluster = props[CLUSTER]
543
        
544
        mtime = time()
545
        self.statistics_update_ancestors(node, -1, -size, mtime, cluster)
546
        
547
        q = "delete from versions where serial = ?"
548
        self.execute(q, (serial,))
549
        return hash
550
    
551
    def attribute_get(self, serial, keys=()):
552
        """Return a list of (key, value) pairs of the version specified by serial.
553
           If keys is empty, return all attributes.
554
           Othwerise, return only those specified.
555
        """
556
        
557
        execute = self.execute
558
        if keys:
559
            marks = ','.join('?' for k in keys)
560
            q = ("select key, value from attributes "
561
                 "where key in (%s) and serial = ?" % (marks,))
562
            execute(q, keys + (serial,))
563
        else:
564
            q = "select key, value from attributes where serial = ?"
565
            execute(q, (serial,))
566
        return self.fetchall()
567
    
568
    def attribute_set(self, serial, items):
569
        """Set the attributes of the version specified by serial.
570
           Receive attributes as an iterable of (key, value) pairs.
571
        """
572
        
573
        q = ("insert or replace into attributes (serial, key, value) "
574
             "values (?, ?, ?)")
575
        self.executemany(q, ((serial, k, v) for k, v in items))
576
    
577
    def attribute_del(self, serial, keys=()):
578
        """Delete attributes of the version specified by serial.
579
           If keys is empty, delete all attributes.
580
           Otherwise delete those specified.
581
        """
582
        
583
        if keys:
584
            q = "delete from attributes where serial = ? and key = ?"
585
            self.executemany(q, ((serial, key) for key in keys))
586
        else:
587
            q = "delete from attributes where serial = ?"
588
            self.execute(q, (serial,))
589
    
590
    def attribute_copy(self, source, dest):
591
        q = ("insert or replace into attributes "
592
             "select ?, key, value from attributes "
593
             "where serial = ?")
594
        self.execute(q, (dest, source))
595
    
596
    def _parse_filters(self, filterq):
597
        preterms = filterq.split(',')
598
        included = []
599
        excluded = []
600
        opers = []
601
        match = _regexfilter.match
602
        for term in preterms:
603
            m = match(term)
604
            if m is None:
605
                continue
606
            neg, key, op, value = m.groups()
607
            if neg:
608
                excluded.append(key)
609
            elif not value:
610
                included.append(key)
611
            elif op:
612
                opers.append((key, op, value))
613
        
614
        return included, excluded, opers
615
    
616
    def _construct_filters(self, filterq):
617
        if not filterq:
618
            return None, None
619
        
620
        subqlist = []
621
        append = subqlist.append
622
        included, excluded, opers = self._parse_filters(filterq)
623
        args = []
624
        
625
        if included:
626
            subq = "a.key in ("
627
            subq += ','.join(('?' for x in included)) + ")"
628
            args += included
629
            append(subq)
630
        
631
        if excluded:
632
            subq = "a.key not in ("
633
            subq += ','.join(('?' for x in excluded)) + ")"
634
            args += excluded
635
            append(subq)
636
        
637
        if opers:
638
            t = (("(key = ? and value %s ?)" % (o,)) for k, o, v in opers)
639
            subq = "(" + ' or '.join(t) + ")"
640
            for k, o, v in opers:
641
                args += (k, v)
642
            append(subq)
643
        
644
        if not subqlist:
645
            return None, None
646
        
647
        subq = ' ' + ' and '.join(subqlist)
648
        
649
        return subq, args
650
    
651
    def _construct_paths(self, pathq):
652
        if not pathq:
653
            return None, None
654
        
655
        subq = " and ("
656
        subq += ' or '.join(("n.path like ? escape '\\'" for x in pathq))
657
        subq += ")"
658
        args = tuple([self.escape_like(x) + '%' for x in pathq])
659
        
660
        return subq, args
661
    
662
    def latest_attribute_keys(self, parent, before=inf, except_cluster=0, pathq=[]):
663
        """Return a list with all keys pairs defined
664
           for all latest versions under parent that
665
           do not belong to the cluster.
666
        """
667
        
668
        # TODO: Use another table to store before=inf results.
669
        q = ("select distinct a.key "
670
             "from attributes a, versions v, nodes n "
671
             "where v.serial = (select max(serial) "
672
                              "from versions "
673
                              "where node = v.node and mtime < ?) "
674
             "and v.cluster != ? "
675
             "and v.node in (select node "
676
                           "from nodes "
677
                           "where parent = ?) "
678
             "and a.serial = v.serial "
679
             "and n.node = v.node")
680
        args = (before, except_cluster, parent)
681
        subq, subargs = self._construct_paths(pathq)
682
        if subq is not None:
683
            q += subq
684
            args += subargs
685
        self.execute(q, args)
686
        return [r[0] for r in self.fetchall()]
687
    
688
    def latest_version_list(self, parent, prefix='', delimiter=None,
689
                            start='', limit=10000, before=inf,
690
                            except_cluster=0, pathq=[], filterq=None):
691
        """Return a (list of (path, serial) tuples, list of common prefixes)
692
           for the current versions of the paths with the given parent,
693
           matching the following criteria.
694
           
695
           The property tuple for a version is returned if all
696
           of these conditions are true:
697
                
698
                a. parent matches
699
                
700
                b. path > start
701
                
702
                c. path starts with prefix (and paths in pathq)
703
                
704
                d. version is the max up to before
705
                
706
                e. version is not in cluster
707
                
708
                f. the path does not have the delimiter occuring
709
                   after the prefix, or ends with the delimiter
710
                
711
                g. serial matches the attribute filter query.
712
                   
713
                   A filter query is a comma-separated list of
714
                   terms in one of these three forms:
715
                   
716
                   key
717
                       an attribute with this key must exist
718
                   
719
                   !key
720
                       an attribute with this key must not exist
721
                   
722
                   key ?op value
723
                       the attribute with this key satisfies the value
724
                       where ?op is one of ==, != <=, >=, <, >.
725
           
726
           The list of common prefixes includes the prefixes
727
           matching up to the first delimiter after prefix,
728
           and are reported only once, as "virtual directories".
729
           The delimiter is included in the prefixes.
730
           
731
           If arguments are None, then the corresponding matching rule
732
           will always match.
733
           
734
           Limit applies to the first list of tuples returned.
735
        """
736
        
737
        execute = self.execute
738
        
739
        if not start or start < prefix:
740
            start = strprevling(prefix)
741
        nextling = strnextling(prefix)
742
        
743
        q = ("select distinct n.path, v.serial "
744
             "from attributes a, versions v, nodes n "
745
             "where v.serial = (select max(serial) "
746
                              "from versions "
747
                              "where node = v.node and mtime < ?) "
748
             "and v.cluster != ? "
749
             "and v.node in (select node "
750
                           "from nodes "
751
                           "where parent = ?) "
752
             "and a.serial = v.serial "
753
             "and n.node = v.node "
754
             "and n.path > ? and n.path < ?")
755
        args = [before, except_cluster, parent, start, nextling]
756
        
757
        subq, subargs = self._construct_paths(pathq)
758
        if subq is not None:
759
            q += subq
760
            args += subargs
761
        subq, subargs = self._construct_filters(filterq)
762
        if subq is not None:
763
            q += subq
764
            args += subargs
765
        else:
766
            q = q.replace("attributes a, ", "")
767
            q = q.replace("and a.serial = v.serial ", "")
768
        q += " order by n.path"
769
        
770
        if not delimiter:
771
            q += " limit ?"
772
            args.append(limit)
773
            execute(q, args)
774
            return self.fetchall(), ()
775
        
776
        pfz = len(prefix)
777
        dz = len(delimiter)
778
        count = 0
779
        fetchone = self.fetchone
780
        prefixes = []
781
        pappend = prefixes.append
782
        matches = []
783
        mappend = matches.append
784
        
785
        execute(q, args)
786
        while True:
787
            props = fetchone()
788
            if props is None:
789
                break
790
            path, serial = props
791
            idx = path.find(delimiter, pfz)
792
            
793
            if idx < 0:
794
                mappend(props)
795
                count += 1
796
                if count >= limit:
797
                    break
798
                continue
799
            
800
            if idx + dz == len(path):
801
                mappend(props)
802
                count += 1
803
                continue # Get one more, in case there is a path.
804
            pf = path[:idx + dz]
805
            pappend(pf)
806
            if count >= limit: 
807
                break
808
            
809
            args[3] = strnextling(pf) # New start.
810
            execute(q, args)
811
        
812
        return matches, prefixes