From ec0f0061a11f725699295fea66887fae4c59ae5e Mon Sep 17 00:00:00 2001 From: ber Date: Mon, 8 Nov 2010 16:21:02 +0000 Subject: [PATCH] Multilinks can be filtered by combining elements with AND, OR and NOT operators now. A javascript gui was added for "keywords", see issue2550648. Developed by Sascha Teichmann; funded by Intevation. (Bernhard Reiter) git-svn-id: http://svn.roundup-tracker.org/svnroot/roundup/roundup/trunk@4575 57a73879-2fb5-44c3-a270-3262357dd7e2 --- CHANGES.txt | 3 + roundup/backends/back_anydbm.py | 89 +++++++++- roundup/backends/back_mysql.py | 5 + roundup/backends/rdbms_common.py | 165 +++++++++++++++++- roundup/cgi/templating.py | 5 + .../templates/classic/html/issue.search.html | 3 +- .../roundup/templates/classic/html/page.html | 16 ++ share/roundup/templates/devel/html/page.html | 14 ++ 8 files changed, 290 insertions(+), 10 deletions(-) diff --git a/CHANGES.txt b/CHANGES.txt index b65c841..b8a8325 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -8,6 +8,9 @@ Features: - Add explicit "Search" permissions, see Security Fix below. - Add "lookup" method to xmlrpc interface (Ralf Schlatterbeck) +- Multilinks can be filtered by combining elements with AND, OR and NOT + operators now. A javascript gui was added for "keywords", see issue2550648. + Developed by Sascha Teichmann; funded by Intevation. (Bernhard Reiter) Fixed: diff --git a/roundup/backends/back_anydbm.py b/roundup/backends/back_anydbm.py index 1d8c32f..4ea2a2d 100644 --- a/roundup/backends/back_anydbm.py +++ b/roundup/backends/back_anydbm.py @@ -49,6 +49,87 @@ def db_exists(config): def db_nuke(config): shutil.rmtree(config.DATABASE) +class Binary: + + def __init__(self, x, y): + self.x = x + self.y = y + + def visit(self, visitor): + self.x.visit(visitor) + self.y.visit(visitor) + +class Unary: + + def __init__(self, x): + self.x = x + + def generate(self, atom): + return atom(self) + + def visit(self, visitor): + self.x.visit(visitor) + +class Equals(Unary): + + def evaluate(self, v): + return self.x in v + + def visit(self, visitor): + visitor(self) + +class Not(Unary): + + def evaluate(self, v): + return not self.x.evaluate(v) + + def generate(self, atom): + return "NOT(%s)" % self.x.generate(atom) + +class Or(Binary): + + def evaluate(self, v): + return self.x.evaluate(v) or self.y.evaluate(v) + + def generate(self, atom): + return "(%s)OR(%s)" % ( + self.x.generate(atom), + self.y.generate(atom)) + +class And(Binary): + + def evaluate(self, v): + return self.x.evaluate(v) and self.y.evaluate(v) + + def generate(self, atom): + return "(%s)AND(%s)" % ( + self.x.generate(atom), + self.y.generate(atom)) + +def compile_expression(opcodes): + + stack = [] + push, pop = stack.append, stack.pop + for opcode in opcodes: + if opcode == -2: push(Not(pop())) + elif opcode == -3: push(And(pop(), pop())) + elif opcode == -4: push(Or(pop(), pop())) + else: push(Equals(opcode)) + + return pop() + +class Expression: + + def __init__(self, v): + try: + opcodes = [int(x) for x in v] + if min(opcodes) >= -1: raise ValueError() + + compiled = compile_expression(opcodes) + self.evaluate = lambda x: compiled.evaluate([int(y) for y in x]) + except: + self.evaluate = lambda x: bool(set(x) & set(v)) + # # Now the database # @@ -1702,12 +1783,10 @@ class Class(hyperdb.Class): if not v: match = not nv else: - # othewise, make sure this node has each of the + # otherwise, make sure this node has each of the # required values - for want in v: - if want in nv: - match = 1 - break + expr = Expression(v) + if expr.evaluate(nv): match = 1 elif t == STRING: if nv is None: nv = '' diff --git a/roundup/backends/back_mysql.py b/roundup/backends/back_mysql.py index 2bc4f13..875cc53 100644 --- a/roundup/backends/back_mysql.py +++ b/roundup/backends/back_mysql.py @@ -564,6 +564,11 @@ class Database(Database): raise class MysqlClass: + + def supports_subselects(self): + # TODO: AFAIK its version dependent for MySQL + return False + def _subselect(self, classname, multilink_table): ''' "I can't believe it's not a toy RDBMS" see, even toy RDBMSes like gadfly and sqlite can do sub-selects... diff --git a/roundup/backends/rdbms_common.py b/roundup/backends/rdbms_common.py index ae13ff2..72d0c69 100644 --- a/roundup/backends/rdbms_common.py +++ b/roundup/backends/rdbms_common.py @@ -71,6 +71,9 @@ except ImportError: from roundup.backends.sessions_rdbms import Sessions, OneTimeKeys from roundup.date import Range +from roundup.backends.back_anydbm import compile_expression + + # dummy value meaning "argument not passed" _marker = [] @@ -100,6 +103,54 @@ def connection_dict(config, dbnamestr=None): d[name] = config[cvar] return d + +class IdListOptimizer: + """ To prevent flooding the SQL parser of the underlaying + db engine with "x IN (1, 2, 3, ..., )" collapses + these cases to "x BETWEEN 1 AND ". + """ + + def __init__(self): + self.ranges = [] + self.singles = [] + + def append(self, nid): + """ Invariant: nid are ordered ascending """ + if self.ranges: + last = self.ranges[-1] + if last[1] == nid-1: + last[1] = nid + return + if self.singles: + last = self.singles[-1] + if last == nid-1: + self.singles.pop() + self.ranges.append([last, nid]) + return + self.singles.append(nid) + + def where(self, field, placeholder): + ranges = self.ranges + singles = self.singles + + if not singles and not ranges: return "(1=0)", [] + + if ranges: + between = '%s BETWEEN %s AND %s' % ( + field, placeholder, placeholder) + stmnt = [between] * len(ranges) + else: + stmnt = [] + if singles: + stmnt.append('%s in (%s)' % ( + field, ','.join([placeholder]*len(singles)))) + + return '(%s)' % ' OR '.join(stmnt), sum(ranges, []) + singles + + def __str__(self): + return "ranges: %r / singles: %r" % (self.ranges, self.singles) + + class Database(FileStorage, hyperdb.Database, roundupdb.Database): """ Wrapper around an SQL database that presents a hyperdb interface. @@ -170,6 +221,14 @@ class Database(FileStorage, hyperdb.Database, roundupdb.Database): """ return self.cursor.fetchall() + def sql_fetchiter(self): + """ Fetch all row as a generator + """ + while True: + row = self.cursor.fetchone() + if not row: break + yield row + def sql_stringquote(self, value): """ Quote the string so it's safe to put in the 'sql quotes' """ @@ -2134,6 +2193,95 @@ class Class(hyperdb.Class): # The format parameter is replaced with the attribute. order_by_null_values = None + def supports_subselects(self): + '''Assuming DBs can do subselects, overwrite if they cannot. + ''' + return True + + def _filter_multilink_expression_fallback( + self, classname, multilink_table, expr): + '''This is a fallback for database that do not support + subselects.''' + + is_valid = expr.evaluate + + last_id, kws = None, [] + + ids = IdListOptimizer() + append = ids.append + + # This join and the evaluation in program space + # can be expensive for larger databases! + # TODO: Find a faster way to collect the data needed + # to evalute the expression. + # Moving the expression evaluation into the database + # would be nice but this tricky: Think about the cases + # where the multilink table does not have join values + # needed in evaluation. + + stmnt = "SELECT c.id, m.linkid FROM _%s c " \ + "LEFT OUTER JOIN %s m " \ + "ON c.id = m.nodeid ORDER BY c.id" % ( + classname, multilink_table) + self.db.sql(stmnt) + + # collect all multilink items for a class item + for nid, kw in self.db.sql_fetchiter(): + if nid != last_id: + if last_id is None: + last_id = nid + else: + # we have all multilink items -> evaluate! + if is_valid(kws): append(last_id) + last_id, kws = nid, [] + if kw is not None: + kws.append(kw) + + if last_id is not None and is_valid(kws): + append(last_id) + + # we have ids of the classname table + return ids.where("_%s.id" % classname, self.db.arg) + + def _filter_multilink_expression(self, classname, multilink_table, v): + """ Filters out elements of the classname table that do not + match the given expression. + Returns tuple of 'WHERE' introns for the overall filter. + """ + try: + opcodes = [int(x) for x in v] + if min(opcodes) >= -1: raise ValueError() + + expr = compile_expression(opcodes) + + if not self.supports_subselects(): + # We heavily rely on subselects. If there is + # no decent support fall back to slower variant. + return self._filter_multilink_expression_fallback( + classname, multilink_table, expr) + + atom = \ + "%s IN(SELECT linkid FROM %s WHERE nodeid=a.id)" % ( + self.db.arg, + multilink_table) + + intron = \ + "_%(classname)s.id in (SELECT id " \ + "FROM _%(classname)s AS a WHERE %(condition)s) " % { + 'classname' : classname, + 'condition' : expr.generate(lambda n: atom) } + + values = [] + def collect_values(n): values.append(n.x) + expr.visit(collect_values) + + return intron, values + except: + # original behavior + where = "%s.linkid in (%s)" % ( + multilink_table, ','.join([self.db.arg] * len(v))) + return where, v, True # True to indicate original + def filter(self, search_matches, filterspec, sort=[], group=[]): """Return a list of the ids of the active nodes in this class that match the 'filter' spec, sorted by the group spec and then the @@ -2213,15 +2361,24 @@ class Class(hyperdb.Class): where.append(self._subselect(pcn, tn)) else: frum.append(tn) - where.append('_%s.id=%s.nodeid'%(pln,tn)) + gen_join = True + + if p.has_values and isinstance(v, type([])): + result = self._filter_multilink_expression(pln, tn, v) + # XXX: We dont need an id join if we used the filter + gen_join = len(result) == 3 + + if gen_join: + where.append('_%s.id=%s.nodeid'%(pln,tn)) + if p.children: frum.append('_%s as _%s' % (cn, ln)) where.append('%s.linkid=_%s.id'%(tn, ln)) + if p.has_values: if isinstance(v, type([])): - s = ','.join([a for x in v]) - where.append('%s.linkid in (%s)'%(tn, s)) - args = args + v + where.append(result[0]) + args += result[1] else: where.append('%s.linkid=%s'%(tn, a)) args.append(v) diff --git a/roundup/cgi/templating.py b/roundup/cgi/templating.py index 510aa61..a541f50 100644 --- a/roundup/cgi/templating.py +++ b/roundup/cgi/templating.py @@ -27,6 +27,8 @@ from roundup import hyperdb, date, support from roundup import i18n from roundup.i18n import _ +from KeywordsExpr import render_keywords_expression_editor + try: import cPickle as pickle except ImportError: @@ -2863,6 +2865,9 @@ class TemplatingUtils: raise AttributeError, name return self.client.instance.templating_utils[name] + def keywords_expressions(self, request): + return render_keywords_expression_editor(request) + def html_calendar(self, request): """Generate a HTML calendar. diff --git a/share/roundup/templates/classic/html/issue.search.html b/share/roundup/templates/classic/html/issue.search.html index cff5122..27e2bc7 100644 --- a/share/roundup/templates/classic/html/issue.search.html +++ b/share/roundup/templates/classic/html/issue.search.html @@ -23,6 +23,7 @@ sort_input templates/page/macros/sort_input; group_input templates/page/macros/group_input; search_select templates/page/macros/search_select; + search_select_keywords templates/page/macros/search_select_keywords; search_select_translated templates/page/macros/search_select_translated; search_multiselect templates/page/macros/search_multiselect;"> @@ -54,7 +55,7 @@ db_klass string:keyword; db_content string:name;"> Keyword: - + diff --git a/share/roundup/templates/classic/html/page.html b/share/roundup/templates/classic/html/page.html index 52b5bed..b06b8b5 100644 --- a/share/roundup/templates/classic/html/page.html +++ b/share/roundup/templates/classic/html/page.html @@ -247,6 +247,22 @@ See issue.search.html in the classic template for examples. + +
+ + (expr) +
+ + diff --git a/share/roundup/templates/devel/html/page.html b/share/roundup/templates/devel/html/page.html index 339c0bd..fcbf0af 100644 --- a/share/roundup/templates/devel/html/page.html +++ b/share/roundup/templates/devel/html/page.html @@ -307,6 +307,20 @@ See issue.search.html in the classic template for examples. + + + (edit) + + -- 2.30.2