Statistics
| Branch: | Tag: | Revision:

root / pithos / backends / lib / sqlite / node.py @ 4819d34f

History | View | Annotate | Download (28.7 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
from time import time
35

    
36
from dbworker import DBWorker
37

    
38
from pithos.lib.filter import parse_filters
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
_propnames = {
84
    'serial'    : 0,
85
    'node'      : 1,
86
    'hash'      : 2,
87
    'size'      : 3,
88
    'source'    : 4,
89
    'mtime'     : 5,
90
    'muser'     : 6,
91
    'cluster'   : 7,
92
}
93

    
94

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