Synnefo » Pithos

from sqlite3 import connect, IntegrityError

from time import time

ROOTNODE  = 0

( SERIAL, PARENT, PATH,

  SIZE, POPULATION, POPSIZE,

  SOURCE, MTIME, CLUSTER ) = range(9)

inf = float('inf')

def strnextling(prefix):

    """return the first unicode string

       greater than but not starting with given prefix.

       strnextling('hello') -> 'hellp'

    """

    if not prefix:

        ## all strings start with the null string,

        ## therefore we have to approximate strnextling('')

        ## with the last unicode character supported by python

        ## 0x10ffff for wide (32-bit unicode) python builds

        ## 0x00ffff for narrow (16-bit unicode) python builds

        ## We will not autodetect. 0xffff is safe enough.

        return unichr(0xffff)

    s = prefix[:-1]

    c = ord(prefix[-1])

    if c >= 0xffff:

        raise RuntimeError

    s += unichr(c+1)

    return s

def strprevling(prefix):

    """return an approximation of the last unicode string

       less than but not starting with given prefix.

       strprevling(u'hello') -> u'helln\\xffff'

    """

    if not prefix:

        ## There is no prevling for the null string

        return prefix

    s = prefix[:-1]

    c = ord(prefix[-1])

    if c > 0:

        s += unichr(c-1) + unichr(0xffff)

    return s

import re

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

_propnames = {

    'serial'    : 0,

    'parent'    : 1,

    'path'      : 2,

    'size'      : 3,

    'population': 4,

    'popsize'   : 5,

    'source'    : 6,

    'mtime'     : 7,

    'cluster'   : 8,

}

_mutables = ('source', 'mtime', 'cluster')

_mutablepropnames = dict((k, _propnames[k]) for k in _mutables)

class Noder(object):

    def __init__(self, **params):

        self.params = params

        self.noder_init()

    def noder_init(self):

        execute = self.execute

        executemany = self.executemany

        execute(""" create table if not exists nodes

                          ( serial     integer not null,

                            parent     integer not null default 0,

                            path       text    not null default '',

                            size       integer not null default 0,

                            population integer not null default 0,

                            popsize    integer not null default 0,

                            source     integer,

                            mtime      integer,

                            cluster    integer not null default 0,

                            primary key (serial)

                            foreign key (parent)

                            references nodes(serial)

                            on update cascade

                            on delete cascade ) """)

        execute(""" create index if not exists

                    paths on nodes(cluster, parent, path) """)

        execute(""" create unique index if not exists

                    mtimes on nodes(mtime) """)

        execute(""" create table if not exists attributes

                          ( serial integer,

                            key    text,

                            value  text,

                            primary key (serial, key, value)

                            foreign key (serial)

                            references nodes(serial)

                            on update cascade

                            on delete cascade ) """)

        #execute(""" create index if not exists keys 

        #                    on attributes(key, value, serial) """)

        execute(""" pragma foreign_keys = 1 """)

        q = "insert or ignore into nodes(serial, parent) values (?, ?)"

        vals = ((ROOTNODE, ROOTNODE),)

        executemany(q, vals)

    def node_create(self, parent, path, size, source, cluster=0):

        """Create a new node from the given properties.

           Return the (serial, mtime) of the new node.

        """

        serial = self.alloc_serial()

        mtime = time()

        props = (serial, parent, path, size, 0, 0, source, mtime, cluster)

        q = "insert into nodes values (?, ?, ?, ?, ?, ?, ?, ?, ?)"

        self.execute(q, props)

        self.node_update_ancestors(parent, 1, size)

        return serial, mtime

    def node_resize(self, serial, size):

        props = self.node_get_properties(serial)

        if props is None:

            return 0

        q = "update nodes set size = ? where serial = ?"

        self.execute(q, (size, serial))

        delta = size - props[3]

        parent = props[1]

        self.node_update_ancestors(parent, 0, delta)

        return 1

    def node_remove(self, serial, recursive=0):

        """Remove the node specified by serial.

           Return false if the node was not found,

           or true if found and removed.

        """

        node_get_properties = self.node_get_properties

        props = node_get_properties(serial)

        size = props[3]

        pop = props[4]

        popsize = props[5]

        if pop and not recursive:

            return 0

        q = "delete from nodes where serial = ?"

        self.execute(q, (serial,))

        self.node_update_ancestors(props[1], -pop-1, -size-popsize)

        return 1

    def node_get_properties(self, serial, keys=(), propnames=_propnames):

        """Return a sequence of values for the properties of

           the node specified by serial and the keys, in the order given.

           If keys is empty, return all properties in the order

           (serial, parent, path, size, population, popsize,

            source, mtime, cluster).

        """

        q = "select * from nodes where serial = ?"

        self.execute(q, (serial,))

        r = self.fetchone()

        if r is None:

            return r

        if not keys:

            return r

        return [r[propnames[k]] for k in keys if k in propnames]

    def node_set_properties(self, serial, items, propnames=_mutablepropnames):

        """Set the properties of a node specified by the node serial and

           the items iterable of (name, value) pairs.

           Mutable properties are %s.

           Invalid property names and 'serial' are not set.

        """ % (_mutables,)

        if not items:

            return

        keys, vals = zip(*items)

        keystr = ','.join(("%s = ?" % k) for k in keys if k in propnames)

        if not keystr:

            return

        q = "update nodes set %s where serial = ?" % keystr

        vals += (serial,)

        self.execute(q, vals)

    def node_update_ancestors(self, serial, population, popsize):

        """Update the population properties of the node specified by serial.

           Population properties keep track the population and totalsize

           of objects in the node's namespace.

           May be zero or positive or negative numbers.

        """

        qu = ("update nodes set population = population + ?,"

                               "popsize    = popsize    + ? "

              "where serial = ?")

        qp = "select parent from nodes where serial = ?"

        execute = self.execute

        fetchone = self.fetchone

        while 1:

            execute(qu, (population, popsize, serial))

            population = 0 # Population isn't recursive

            execute(qp, (serial,))

            r = fetchone()

            if r is None:

                break

            serial = r[0]

            if serial < 3:

                break

    def node_lookup(self, parent, path, before=inf, cluster=0):

        """Lookup the current version of the given path

           within the parent's namespace. Return a list with its properties:

           (serial, parent, path, size, population, popsize,

            source, mtime, cluster)

           or None if the version is not found.

        """

        q =("select max(serial), parent, path, size, "

                   "population, popsize, source, mtime, cluster "

            "from nodes "

            "where parent = ? and cluster = ? and path = ? and mtime < ?")

        self.execute(q, (parent, cluster, path, before))

        props = self.fetchone()

        if props is not None and props[SERIAL] is not None:

            return props

        return None

    def parse_filters(self, filterq):

        preterms = filterq.split(',')

        included = []

        excluded = []

        opers = []

        match = _regexfilter.match

        for term in preterms:

            m = match(term)

            if m is None:

                continue

            neg, key, op, value = m.groups()

            if neg:

                excluded.append(key)

            elif not value:

                included.append(key)

            elif op:

                opers.append((key, op, value))

        return included, excluded, opers

    def construct_filters(self, filterq):

        subqlist = []

        append = subqlist.append

        included, excluded, opers = self.parse_filters(filterq)

        args = []

        if included:

            subq = "key in ("

            subq += ','.join(('?' for x in included)) + ")"

            args += included

            append(subq)

        if excluded:

            subq = "key not in ("

            subq += ','.join(('?' for x in exluded)) + ")"

            args += excluded

            append(subq)

        if opers:

            t = (("(key = %s and value %s %s)" % (k, o, v)) for k, o, v in opers)

            subq = "(" + ' or '.join(t) + ")"

            args += opers

        if not subqlist:

            return None, None

        subq = " and serial in (select serial from attributes where "

        subq += ' and '.join(subqlist)

        subq += ")"

        return subq, args

    def node_list(self, parent, prefix='',

                   start='', delimiter=None,

                   after=0.0, before=inf,

                   filterq=None, versions=0,

                   cluster=0, limit=10000):

        """Return (a list of property tuples, a list of common prefixes)

           for the current versions of the paths with the given parent,

           matching the following criteria.

           The property tuple for a version is returned if all

           of these conditions are true:

                a. parent (and cluster) matches

                b. path > start

                c. path starts with prefix

                d. i  [versions=true]  version is in (after, before)

                   ii [versions=false] version is the max in (after, before)

                e. the path does not have the delimiter occuring

                   after the prefix.

                f. serial matches the attribute filter query.

                   A filter query is a comma-separated list of

                   terms in one of these three forms:

                   key

                       an attribute with this key must exist

                   !key

                       an attribute with this key must not exist

                   key ?op value

                       the attribute with this key satisfies the value

                       where ?op is one of ==, != <=, >=, <, >.

           matching up to the first delimiter after prefix,

           and are reported only once, as "virtual directories".

           The delimiter is included in the prefixes.

           Prefixes do appear from (e) even if no paths would match in (f).

           If arguments are None, then the corresponding matching rule

           will always match.

        """

        execute = self.execute

        if start < prefix:

            start = strprevling(prefix)

        nextling = strnextling(prefix)

        q = ("select * from nodes "

             "where parent = ? and path > ? and path < ? "

             "and mtime > ? and mtime < ? and cluster = ?")

        args = [parent, start, nextling, after, before, cluster]

        if filterq:

            subq, subargs = self.construct_filters(filterq)

            if subq is not None:

                q += subq

                args += subargs

        q += " order by path"

        if delimiter is None:

            q += " limit ?"

            args.append(limit)

            execute(q, args)

            return self.fetchall(), ()

        pfz = len(prefix)

        dz = len(delimiter)

        count = 0

        fetchone = self.fetchone

        prefixes = []

        pappend = prefixes.append

        matches = []

        mappend = matches.append

        execute(q, args)

        while 1:

            props = fetchone()

            if props is None or props[0] is None:

                break

            path = props[2]

            idx = path.find(delimiter, pfz)

            if idx < 0:

                mappend(props)

                count += 1

                if count >= limit:

                    break

                continue

            pf = path[:idx + dz]

            pappend(pf)

            count += 1

            ## XXX: if we break here due to limit,

            ##      but a path would also be matched below,

            ##      the path match would be lost since the

            ##      next call with start=path would skip both of them.

            ##      In this case, it is impossible to obey the limit,

            ##      therefore we will break later, at limit + 1.

            if idx + dz == len(path):

                mappend(props)

                count += 1

            if count >= limit: 

                break

            args[1] = strnextling(pf) # new start

            execute(q, args)

        return matches, prefixes

    def node_delete(self, parent, prefix,

                    start='', delimiter=None,

                    after=0.0, before=inf,

                    filterq=None, versions=0,

                    cluster=0, limit=10000):

        """Delete the matching version for each

           of the matching paths in the parent's namespace.

           Return empty if nothing is deleted, else return matches.

           The paths matching are those that would

           be returned by .node_list() with the same arguments.

           Note that only paths are deleted, not prefixes.

        """

        r = self.node_list(parent, prefix,

                           start=start, delimiter=delimiter,

                           after=after, before=before,

                           filterq=filterq, versions=versions,

                           cluster=cluster, limit=limit)

        matches, prefixes = r

        if not matches:

            return ()

        q = "delete from nodes where serial = ?"

        self.executemany(q, ((props[0],) for props in matches))

        return matches

    def node_purge(self, parent, path, after=0, before=inf, cluster=0):

        """Delete all nodes with the specified

           parent, cluster and path, and return

           the serials of nodes deleted.

        """

        execute = self.execute

        q = ("select count(serial), total(size), "

                    "total(population), total(popsize) "

             "from nodes "

             "where parent = ? and cluster = ? "

             "and path = ? and mtime between ? and ?")

        args = (parent, cluster, path, after, before)

        execute(q, args)

        nr, size, pop, popsize = self.fetchone()

        if not nr:

            return ()

        self.node_update_ancestors(parent, -pop-nr, -size-popsize)

        q = ("select serial from nodes "

             "where parent = ? and cluster = ? "

             "and path = ? and mtime between ? and ?")

        execute(q, args)

        serials = [r[0] for r in self.fetchall()]

        q = ("delete from nodes where "

             "parent = ? and cluster = ? "

             "and path = ? and mtime between ? and ?")

        execute(q, args)

        return serials

    def node_move(self, source, parent, path):

        """Move the source node into another path,

           possibly, in another parent's namespace.

           The node is moved with its namespace.

        """

        props = self.node_get_properties(source)

        oldparent = props[PARENT]

        size = props[SIZE]

        population = props[POPULATION]

        sizedelta = size + popsize

        popdelta = population + 1

        node_update_ancestors = self.node_update_ancestors

        node_update_ancestors(oldparent, -popdelta, -sizedelta)

        node_update_ancestors(parent, popdelta, sizedelta)

        q = "update nodes set parent = ?, path = ? where serial = ?"

        self.execute(q, (parent, path, source))

    def node_copy(self, source, parent=None, path=None):

        """Copy the node specified by serial into

           a new node under parent and path.

           Return the serial of the new node.

           The namespace of the node is not copied --

           only the node itself is.

        """

        newserial = self.alloc_serial()

        props = self.node_get_properties(source)

        if parent is None:

            parent = props[1]

        if path is None:

            path = props[2]

        size = props[3]

        cluster = props[8]

        return self.node_create(parent, path, size, source, cluster=cluster)

    def node_increment(self, serial, size=None):

        mtime = time()

        if size is not None:

            q = "update nodes set mtime = ?, size = ? where serial = ?"

            args = (mtime, size, serial)

        else:

            q = "update nodes set mtime = ? where serial = ?"

            args = (mtime, serial)

        self.execute(q, args)

        return mtime

    def node_attr_get(self, serial, keys=()):

        """Return a list of (key, value) pairs of the node specified by serial.

           If keys is empty, return all attributes.

           Othwerise, return only those specified.

        """

        execute = self.execute

        if keys:

            marks = ','.join('?' for k in keys)

            q = ("select key, value from attributes "

                 "where key in (%s) and serial = ?" % (marks,))

            execute(q, keys + (serial,))

        else:

            q = "select key, value from attributes where serial = ?"

            execute(q, (serial,))

        return self.fetchall()

    def node_attr_set(self, serial, items):

        """Set the attributes of the node specified by serial.

           Receive attributes as an iterable of (key, value) pairs.

        """

        q = ("insert or replace into attributes (serial, key, value) "

             "values (?, ?, ?)")

        self.executemany(q, ((serial, k, v) for k, v in items))

    def node_attr_del(self, serial, keys=()):

        """Delete attributes of the node specified by serial.

           If keys is empty, delete all attributes.

           Otherwise delete those specified.

        """

        if keys:

            q = "delete from attributes where serial = ? and key = ?"

            self.executemany(q, ((serial, key) for key in keys))

        else:

            q = "delete from attributes where serial = ?"

            self.execute(q, (serial,))

    def node_attr_create_key(self, serial, key):

        """Create and return a key with the given name

           in the namespace of the parent node.

        """

        key = self.alloc_serial()

        q = "insert or ignore into keys values (?, ?)"

        self.execute(q, (serial, key))

        return key

    def node_attr_list_keys(self, parent):

        """Return a list with all keys pairs defined

           for the namespace of the node specified.

        """

        #q = "select key from keys where serial = ?"

        q = ("select distinct key from attributes a, nodes n "

             "where a.serial = n.serial and n.parent = ?")

        self.execute(q, (parent,))

        return [r[0] for r in self.fetchall()]

    def node_attr_purge_key(self, parent, key, cluster=0):

        """Delete the key given and

           purge all attributes set with this key from all objects.

        """

        #q = "delete from keys where key = ?"

        q = ("delete from attributes where key = ? and serial in "

             "(select serial from nodes where parent = ? and cluster = ?)")

        self.execute(q, (key, parent, cluster))

    def node_attr_copy(self, source, dest):

        q = ("insert or replace into attributes "

             "select ?, key, value from attributes "

             "where serial = ?")

        self.execute(q, (dest, source))