Re: [gentoo-portage-dev] [PATCH] metascan-core

[Brian Harring]

Not intending to be harsh in this email, keep in mind 
this is _just_ technical angle here.  What you're attempting 
I think is needed, just seemajor  issues with form presented.


On Sat, Dec 10, 2005 at 05:11:07AM +0100, Marius Mauch wrote:
> Attached patch adds a new function metascan() in portage.py and aliases
> it to portdbapi.metascan() and vardbapi.metascan(). It's basically the
> same code as in metalib.py (in private/genone/scripts), just mildly
> tweaked to work inside portage.py.
> It provides the core functionality for my metascan script which is now
> basically just a cli wrapper for the function.

I'd rather not see this go into portage.py- I don't think the 
interface is up to snuff atm (design reasons tail end of the email, 
implementation issues following inline).


> --- pym/portage.py	2005-11-13 14:55:16.000000000 +0100
> +++ pym/portage.py	2005-12-09 18:39:44.000000000 +0100
> @@ -4387,6 +4387,110 @@
>  		return myslot
>
>
> +def __metascan_resolve_dep_strings(cpv, keys, values, mysettings):
<snip>
> +def __metascan_strip_atoms(keys, values, mysettings):

We're (mostly) all consenting adults, namespace mangling probably 
isn't required here (yes, I'm guilty of it occasionally also, 
just don't think it's required here).


> +def metascan(db, keys, values, negated, mysettings, scanlist=None, operator="or", resolveDepStrings=False, stripAtoms=False, partial=False, regex=False, catlimit=None, debug=0, verbose=False):
> +	"""
> +	Function to find all packages matching certain metadata criteria.
> +	"""

Doc string is pretty sparse.  No explanation of what 
keys/values/negated is supposed to be (list?  tuple? dict?)- should be 
knowable from docstring if this is going to be api.  Same with 
operator, although operator's string based args really dislike.

Basically... without reading over the function and your script for 
examples of the calls, this func's prototype/docstring really isn't 
usable without doing a lot of digging.

No comment on returns, either- basically, prototype seems like it's 
overgrown, like it needs to be chunked up and simplified, plus actual 
docstrings.


General code comments, trailing comments on design...

> +	if len(keys) != len(values) or len(keys) != len(negated):
> +		raise IndexError("argument length mismatch")
> +
> +	if scanlist == None:
> +		scanlist = {}
> +		plist = db.cp_all()
> +		for p in plist:
> +			scanlist[p] = []
> +			for pv in db.cp_list(p):
> +				scanlist[p].append(pv)

This is pretty icky; you're scanning the entire tree in a single run, 
building it *all* up in memory prior to even doing the actual 
matching.

Fex, no keys, and this will force a full scan for nothing.
Use a generator.

> +
> +	resultlist = []
> +
> +	for p in scanlist:
> +		if debug > 1:
> +			sys.stderr.write("Scanning package %s\n" % p)
> +		# check if we have a category restriction and if that's the case, skip this package if we don't have a match
> +		if catlimit != None and catsplit(p)[0] not in catlimit:
> +			if debug > 1:
> +				sys.stderr.write("Skipping package %s from category %s due to category limit (%s)\n" % (p, catsplit(p)[0], str(catlimit)))
> +			continue
> +		for pv in scanlist[p]:
> +			try:
> +				result = []
> +				# this is the slow part, also generates noise if portage cache out of date
> +				pvalues = db.aux_get(pv, keys)
> +
> +			except KeyError:
> +				sys.stderr.write("Error while scanning %s\n" % pv)

No lib code should *ever* be dumping to stderr on it's own for non 
fatal errors.  

Yes portage violates it, but portage code also sucks.

> +				continue
> +
> +			# save original values for debug
> +			if debug > 1:
> +				keys_uniq = []
> +				pvalues_orig = []
> +				for i in range(0, len(keys)):
> +					if not keys[i] in keys_uniq:
> +						keys_uniq.append(keys[i])
> +						pvalues_orig.append(pvalues[i])
Totally unnecessary here.  Do a *single* unique call of keys rather 
then doing it 20,000+ times for each cpv.  Same thing for the 
db.aux_get call above.


> +
> +			# remove conditional deps whose coditions aren't met
> +			if resolveDepStrings:
> +				pvalues = __metascan_resolve_dep_strings(pv, keys, pvalues, settings)
> +
> +			# we're only interested in the cat/pkg stuff from an atom here, so strip the rest
> +			if stripAtoms:
> +				pvalues = __metascan_strip_atoms(keys, pvalues, settings)
> +
> +			# report also partial matches, e.g. "foo" in "foomatic"
> +			if partial or regex:
> +				for i in range(0, len(pvalues)):

the 0 initial arg isn't needed.

> +					result.append((partial and pvalues[i].find(values[i]) >= 0) \
> +							or (regex and bool(re.match(values[i], pvalues[i]))))

Should be caching regex compilations instead of continual 
recompilation.  Speed up there...

> +
> +			# we're only interested in full matches in general
> +			else:
> +				result = [values[i] in pvalues[i].split() for i in range(0, len(pvalues))]
> +
> +			# some funky logic operations to invert the adjust the match if negations were requested
> +			result = [(negated[i] and not result[i]) or (not negated[i] and result[i]) for i in range(0, len(result))]
xor baby... xor.

> +
> +			# more logic stuff for conjunction or disjunction
> +			if (operator == "or" and True in result) or (operator == "and" and not False in result):
> +				if debug > 0:
> +					sys.stderr.write("Match found: %s\n" % pv)
> +				if debug > 1:
> +					for i in range(0, len(keys_uniq)):
> +						sys.stderr.write("%s from %s: %s\n" % (keys_uniq[i], pv, pvalues_orig[i]))
> +				if verbose:
> +					resultlist.append(pv)
> +				else:
> +					if not p in resultlist:
> +						resultlist.append(p)

No no no no no... use a set or a dict.  While it's easy/obvious code 
wise, don't do linear searches like that unless you know the set is 
going to be _small_ (sub 10, although timeit runs would bear out a 
more accurate figure).  Little stuff like this when removed provides a 
_lot_ of speedups- little stuff like this is why people piss and moan 
python is slow when it's usually bad algo's that are at fault...

> +	return resultlist

this should be a generator, and yielding.  Unless I've missed 
something obvious from above, this code doesn't have any reason to 
build up a list of returns like this instead of just yielding as it 
determines matches.  Plus side, decreased interim mem usage, and 
calling code can display to the user immediately on returns.
Con?  Have to change all your appends.  Your boolean logic 
implementations are going to get complex also, since you'll have to 
maintain a stack of potential matches.


General commentary... this isn't flexible enough.  Extension of the 
matching code is dependant on extension of the metascan func- adding 
an xor (fex) isn't viable without modifying the code.

Further, you can't do subclass matching without abusing scanlist- this 
is an indication (imo) that the interface needs an overhaul.

To pull off arbitrary matching, fex
( ( category = blah or package = blah ) and ( description = dar ) )
requires 3 seperate calls raiding from the returnlist and handing 
it back in as scanlist.  This I view as a general design failure; 
what's needed is a way to arbitrarily combine restrictions/search 
criteria.

This base functionality, wrapped in some serious voodoo classes could 
pull it off although maintaining it would be ugly.  Still would have 
all of the matching logic embedded in a central func though, which 
isn't extensible.

I think you're coming at this from the wrong angle- I'd advocate the 
restriction subsystem design that is sitting in saviour frankly.  
Encapsulate the individual restrictions, and encapsulate boolean 
matching logic within classes.

Go the route the restriction subsystem inherintely allows, you've got 
extensibility up the ying yang- can use either base classes provided, 
or provide your own nonstandard matching/restrictions and just slap it 
in.  The restriction subsystem _is_ pretty damn close to the pquery 
language you'd talk of a long while back, the only chunk missing from 
actually having your pquery language is a tokenizer that converts 
sql/pquery akin strings into restriction elements that can be used for 
matching.

Pros of the saviour restriction subsystem?
1) it covers *all* matching.  atom look ups included.  IOW, we don't 
have two methods of searching/lookup, we have a single point to 
optimize the hell out of.
2) arbitrary depths of boolean terms built in via the design, no dance 
required by callers to filter down lists, managing boolean logic 
itself.

Cons?
1) relies on an actual package agnostic class- iow, whatever the 
format the 'package' is, it would still work with it.  That said, 
format classes have to be have a basic common api/set of attributes.
2) query optimization can be a bitch.  You've got a tree of 
restrictions, an optimizer that is capable of identifying subset of 
categories/packages instead of just trying all nodes would be useful 
(speed things up by reducing the set of potential matches).
3) bound to repo design, which also binds config crap to per package.  
This is actually a pro from a design/maintenance angle, but is a con 
since it's not something easily retrofitted into stable (note I'm 
reversing my stance here, I think it's doable although it's going to 
require a helluva lot of work).

So... why am I whoring the restriction subsystem?  Well, it's the
culmination of our talks.  It *is* effectively a pquery implementation 
at it's core.  It's what we originally talked about as being 
desirable, best route to go- hell, even the string output is inline 
with your original pquery syntax (sql like).

Matching code being pushed into stable I'm for, but I'd rather see an 
api/framework pushed in that is designed for long term (ab)use.  The 
patch provided is usable for your script, but any code that wanted to 
do similar complex scans is forced to duplicate the boolean crap- 
that's a really bad thing, something portage already suffers horribly 
from.  

Any matching functionality pushed into portage is going to be used by 
porthole and other portage consumers- the api _does_ need to be pretty 
sane (even if we may redesign everything else down the line).  
Complex search query capabilities in the consumer will be invariably 
bound to the underlying portage implementation, although hopefully at 
least somewhat decoupled- hence my belief this particular area _needs_ 
to be right from the get go.

So... my 2 cents, which admittedly can be construed as biased since 
I've already made the plunge with the restriction subsystem.

Just think it's the proper way to go; centralized design route you're 
going here I think is going to lead to unmaintainable code the more 
power that's jimmied into it.
~harring