rwhoisd/QueryProcessor.py

   1 # This file is part of python-rwhoisd
   2 #
   3 # Copyright (C) 2003, David E. Blacka
   4 #
   5 # This program is free software; you can redistribute it and/or modify
   6 # it under the terms of the GNU General Public License as published by
   7 # the Free Software Foundation; either version 2 of the License, or
   8 # (at your option) any later version.
   9 #
  10 # This program is distributed in the hope that it will be useful, but
  11 # WITHOUT ANY WARRANTY; without even the implied warranty of
  12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 # General Public License for more details.
  14 #
  15 # You should have received a copy of the GNU General Public License
  16 # along with this program; if not, write to the Free Software
  17 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  18 # USA
  19
  20 import sys, re
  21 import Cidr, Rwhois, QueryParser
  22
  23 class QueryProcessor:
  24
  25     def __init__(self, db):
  26         self.db = db
  27
  28     def _filter_obj_term(self, obj, term):
  29         """Given a rwhoisobject and a query term (a 3 element tuple:
  30         attr, operator, value), determine if the object satisfies the
  31         term.  Returns True if the object matches the term, False if
  32         not."""
  33
  34         attr, op, searchval = term
  35         res = False
  36
  37         # filter by named attribute
  38         if attr:
  39             vals = obj.get_attr(attr)
  40             if not vals:
  41                 res = False
  42             else:
  43                 res = match_values(searchval, vals)
  44             if op == "!=": return not res
  45             return res
  46         # filter by general term
  47         else:
  48             for val in obj.values():
  49                 if match_value(searchval, val):
  50                     return True
  51             return False
  52
  53     def _filter_obj(self, obj, terms):
  54         """Given a rwhoisobject and a list of query terms (i.e., a
  55         whole AND clause), return True if the object satisfies the
  56         terms."""
  57
  58         for term in terms:
  59             if not self._filter_obj_term(obj, term): return False
  60         return True
  61
  62     def _filter_results(self, reslist, terms):
  63         """Given list of result objects (not simply the ids returned
  64         from the search) and a list of query terms (i.e., a query
  65         clause), remove elements that do not satisfy the terms.
  66         Returns a list of objects that satisfy the filters."""
  67
  68         if not terms: return reslist
  69         return [ x for x in reslist if self._filter_obj(x, terms) ]
  70
  71     def process_query_clause(self, clause, max=0):
  72         """Process a query clause (a grouping of terms ANDed
  73         together).  This is where the indexed searches actually get
  74         done.  The technique used here is to search on one index and
  75         use the rest of the clause to filter the results.  Returns a
  76         QueryResult object"""
  77
  78         # the technique is to do an index search on the first (or
  79         # maybe best) indexed term (bare terms are always considered
  80         # indexed), and filter those results with the remaining terms.
  81
  82         # Note: this could be better if we found the "optimal" query
  83         # term.  One approach may be to create a cost function and
  84         # search for the minimum cost term.
  85
  86         # Note: another approach might be to actually do indexed
  87         # searches on all applicable terms (bare or using an indexed
  88         # attribute) and find the intersection of the results.
  89
  90         st  = None
  91         sti = 0
  92
  93         orig_clause = clause[:]
  94
  95         # find the first searchable term:
  96         for term, i in zip(clause, xrange(sys.maxint)):
  97             attr, op, value = term
  98             if op == "!=": continue
  99             if not attr or self.db.is_indexed_attr(attr):
 100                 st, sti = term, i
 101                 break
 102         if not st:
 103             raise Rwhois.RwhoisError, (351, "No indexed terms in query clause")
 104
 105         # remove the search term from the clause, what remains is the
 106         # filter.
 107         del clause[sti]
 108
 109         # if we have an attribute name, search on that.
 110         if st[0]:
 111             res = self.db.search_attr(st[0], st[2], max)
 112         else:
 113             if Cidr.valid_cidr(st[2].strip("*")):
 114                 res = self.db.search_cidr(st[2], max)
 115             else:
 116                 res = self.db.search_normal(st[2], max)
 117
 118         objs = self._filter_results(self.db.fetch_objects(res.list()), clause)
 119
 120         queryres = QueryResult(objs)
 121
 122         # look for referrals
 123         refs = self.process_referral_search(orig_clause)
 124         queryres.add_referrals(refs)
 125
 126         return queryres
 127
 128     def _is_in_autharea(self, value):
 129         """Returns True if value could be considered to be contained
 130         within an authority area.  That is, is a subnet of a
 131         network-type authority area or a subdomain of a domainname
 132         type authority area."""
 133
 134         aas = self.db.get_authareas()
 135
 136         if isinstance(value, Cidr.Cidr):
 137             for aa in aas:
 138                 cv = Cidr.valid_cidr(aa)
 139                 if cv and cv.is_supernet(value):
 140                     return True
 141         else:
 142             for aa in aas:
 143                 if is_domainname(aa) and is_subdomain(aa, value):
 144                     return True
 145         return False
 146
 147     def _referral_search_cidr(self, cv, value):
 148         """Return the IndexResult of a referral search for value, or
 149         None if the value doesn't qualify for a Cidr referral
 150         search."""
 151
 152         if not cv: return None
 153         if not self._is_in_autharea(cv): return None
 154         return self.db.search_referral(value)
 155
 156     def _referral_search_domain(self, value):
 157         """Return the IndexResult of a referral search for value, or
 158         None if the value doesn't qualify for a domain referral
 159         search."""
 160
 161         if not is_domainname(value): return None
 162         if not self._is_in_autharea(value): return None
 163         dn = value
 164         res = None
 165         while dn:
 166             res = self.db.search_referral(dn)
 167             if res.list(): break
 168             dn = reduce_domain(dn)
 169         return res
 170
 171     def _referral_search_term(self, value):
 172         """Return the IndexResult of a referral search for value, or
 173         None if the value didn't qualify for a referral search."""
 174
 175         cv = Cidr.valid_cidr(value)
 176         if cv:
 177             return self._referral_search_cidr(cv, value)
 178         elif is_domainname(value):
 179             return self._referral_search_domain(value)
 180         return None
 181
 182     def process_referral_search(self, clause):
 183         """Given a query clause, attempt to search for referrals
 184         associated with the terms.  Return a list of referral strings
 185         that matched terms in the clause (if any).  The only terms
 186         that actually get searched are the ones that look
 187         'heirarchical'.  For now, the attribute part of the term is
 188         essentially ignored, so a search for something like
 189         'name=127.0.0.1' might concievably generate a referral, when
 190         perhaps it shouldn't."""
 191
 192         # first check to see if the search is explictly for a referral
 193         for term in clause:
 194             if (term[0] == "class-name" and term[1] == "="
 195                 and term[2] == "referral") or term[0] == "referred-auth-area":
 196                 # in which case, we return nothing
 197                 return []
 198
 199         referrals = []
 200
 201         # look for heirarchical-looking terms.
 202         for attr, op, value in clause:
 203             if op == "!=": continue
 204             res = self._referral_search_term(value)
 205             if not res or not res.list():
 206                 continue
 207
 208             ref_objs = self.db.fetch_objects(res.list())
 209             ref_strs = [x for y in ref_objs for x in y.get_attr("referral")]
 210             referrals.extend(ref_strs)
 211
 212         return referrals
 213
 214
 215     def process_full_query(self, query, max=0):
 216         """Given a parsed query object, process it by unioning the
 217         results of the various ORed together clauses"""
 218
 219         # shortcut for the very common single clause case:
 220         if len(query.clauses) == 1:
 221             res = self.process_query_clause(query.clauses[0], max)
 222             return res
 223
 224         # otherwise, union the results from all the causes
 225         res = QueryResult()
 226         for clause in query.clauses:
 227             res.extend(self.process_query_clause(clause))
 228             if max and len(res) >= max:
 229                 res.truncate(max)
 230                 break
 231
 232         return res
 233
 234     def process_query(self, session, queryline):
 235         """Given a session config and a query line, parse the query,
 236         perform any searches, return any referrals."""
 237
 238         if not session.queryparser:
 239             session.queryparser = QueryParser.get_parser()
 240
 241         # parse the query
 242         try:
 243             query = QueryParser.parse(session.queryparser, queryline)
 244         except Rwhois.RwhoisError, x:
 245             session.wfile.write(Rwhois.error_message(x))
 246             return
 247
 248         max = session.limit
 249         if max: max += 1
 250
 251         try:
 252             query_result = self.process_full_query(query, max)
 253         except Rwhois.RwhoisError, x:
 254             session.wfile.write(Rwhois.error_message(x))
 255             return
 256
 257         objects   = query_result.objects()
 258         referrals = query_result.referrals()
 259
 260         if not objects and not referrals:
 261             session.wfile.write(Rwhois.error_message(230))
 262             # session.wfile.write("\r\n")
 263             return
 264
 265         limit_exceeded = False
 266         if session.limit and len(objects) > session.limit:
 267             del objects[session.limit:]
 268             limit_exceeded = True
 269
 270         for obj in objects:
 271             session.wfile.write(obj.to_wire_str())
 272             session.wfile.write("\r\n")
 273
 274         if referrals:
 275             if objects:
 276                 session.wfile.write("\r\n")
 277             session.wfile.write("\r\n".join(referrals))
 278             session.wfile.write("\r\n")
 279
 280         if limit_exceeded:
 281             session.wfile.write(Rwhois.error_message(330))
 282         else:
 283             session.wfile.write(Rwhois.ok())
 284
 285 class QueryResult:
 286
 287     def __init__(self, objs=[], referrals=[]):
 288         self.data  = objs
 289         self.ids   = [ x.getid() for x in objs ]
 290         self._dict = dict(zip(self.ids, self.ids))
 291         self.refs  = referrals
 292
 293     def extend(self, list):
 294         if isinstance(list, type(self)):
 295             list = list.objects()
 296         new_objs = [ x for x in list if not self._dict.has_key(x.getid()) ]
 297         new_ids = [ x.getid() for x in new_objs ]
 298         self.data.extend(new_objs)
 299         self.ids.extend(new_ids)
 300         self._dict.update(dict(zip(new_ids, new_ids)))
 301
 302     def add_referrals(self, referrals):
 303         self.refs.extend(referrals)
 304
 305     def objects(self):
 306         return self.data
 307
 308     def referrals(self):
 309         return self.refs
 310
 311     def ids(self):
 312         return self.ids
 313
 314     def truncate(self, n=0):
 315         to_del = self.ids[n:]
 316         for i in to_del: del self._dict[i]
 317         self.ids = self.ids[:n]
 318         self.data = self.data[:n]
 319
 320
 321 def match_value(searchval, val):
 322     """Determine if a search value matches a data value.  If both
 323     matching terms are valid CIDR objects, then they are matched
 324     according the CIDR wildcard rules (i.e., a single trailing * is a
 325     supernet search, ** is a subnet search).  If the search value is
 326     not wildcarded, then they are just tested for numeric equality.
 327     Otherwise, the terms are compared using string semantics
 328     (substring, prefix, suffix, and exact match."""
 329
 330     if match_cidr(searchval, val): return True
 331
 332     # normalize the values for comparison.
 333     searchval = searchval.lower()
 334     val = val.lower()
 335
 336     # the substring case
 337     if searchval.startswith("*") and searchval.endswith("*"):
 338         sv = searchval.strip("*");
 339         if val.find(sv) >= 0:
 340             return True
 341         else:
 342             return False
 343     # the suffix case
 344     elif searchval.startswith("*"):
 345         sv = searchval.lstrip("*")
 346         return val.endswith(sv)
 347     # the prefix case
 348     elif searchval.endswith("*"):
 349         sv = searchval.rstrip("*")
 350         return val.startswith(sv)
 351     # the exact match case
 352     else:
 353         return searchval == val
 354
 355 def match_values(searchval, val_list):
 356
 357     for val in val_list:
 358         if match_value(searchval, val): return True
 359     return False
 360
 361 def match_cidr(searchval, val):
 362     """If both terms are valid CIDR values (minus any trailing
 363     wildcards of the search value), compare according the CIDR
 364     wildcard rules: subnet, supernet, and exact match.  If both terms
 365     are not CIDR address, return False."""
 366
 367
 368     sv = Cidr.valid_cidr(searchval.rstrip("*"))
 369     rv = Cidr.valid_cidr(val)
 370
 371     if not sv or not rv: return False
 372
 373     if (searchval.endswith("**")):
 374         return rv.is_subnet(sv)
 375     elif (searchval.endswith("*")):
 376         return rv.is_supernet(sv)
 377     else:
 378         return rv == sv
 379
 380
 381 # this forms a pretty basic heuristic to see of a value looks like a
 382 # domain name.
 383 domain_regex = re.compile("[a-z0-9-]+\.[a-z0-9-.]+", re.I)
 384
 385 def is_domainname(value):
 386     if domain_regex.match(value):
 387         return True
 388     return False
 389
 390 def is_subdomain(domain, subdomain):
 391     domain = domain.lower();
 392     subdomain = subdomain.lower();
 393
 394     dlist = domain.split('.')
 395     sdlist = subdomain.split('.')
 396
 397     if len(dlist) > len(sdlist): return False
 398     if len(dlist) == len(sdlist): return domain == subdomain
 399
 400     dlist.reverse();
 401     sdlist.reverse()
 402
 403     return dlist == sdlist[:len(dlist)]
 404
 405 def reduce_domain(domain):
 406     dlist = domain.split('.')
 407     dlist.pop(0)
 408     return '.'.join(dlist)
 409
 410 def is_heirarchical(value):
 411     if cidr.valid_cidr(value): return True
 412     if is_domainname(value): return True
 413     return False
 414
 415 if __name__ == '__main__':
 416
 417     import MemDB, Session
 418
 419     db = MemDB.MemDB()
 420
 421     print "loading schema:", sys.argv[1]
 422     db.init_schema(sys.argv[1])
 423     for data_file in sys.argv[2:]:
 424         print "loading data file:", data_file
 425         db.load_data(data_file)
 426     db.index_data()
 427
 428     QueryParser.db = db
 429     processor = QueryProcessor(db)
 430
 431     session = Session.Context()
 432     session.wfile = sys.stdout
 433
 434     while 1:
 435         line = sys.stdin.readline().strip();
 436         if not line: break
 437         if line.startswith("#"): continue
 438
 439         print "parsing: '%s'" % line
 440         processor.process_query(session, line)
 441         session.wfile.write("\r\n");
 442         session.wfile.flush()