https://bz.apache.org/SpamAssassin/show_bug.cgi?id=7735
Loren Wilton <lwilton@earthlink.net> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |lwilton@earthlink.net
--- Comment #8 from Loren Wilton <lwilton@earthlink.net> ---
Just thinking off the top of my head, I think I'd consider something along the
following lines.
1. Conceptually build four prioritized tree-lists of rules:
a. non-net, non-meta
b. non-net, meta
c. net, non-meta
d. net, meta
The tree nodes are the priority order, for each priority where rules exist
there is a list of rules of that priority. The rules are evaluated in tree
order and branch order, in the order given above.
While I've described this as four trees of lists, it could equally be done with
one partitioned tree, where each partition is assigned a base rule priority
higher than any rule priority that can be manually assigned, for instance 0-99,
100-199, etc. The goal is to create the above-described rule evaluation order
constraints.
Non-meta rules are trivially assigned a priority, as it is a given for each
rule.
Meta rules may have been given priorities, but that needs to be considered as a
minimum priority, and can only be used to delay the meta evaluation.
As an implementation I think I'd initially throw all meta rules into a
bucket/list of some sort, remembering their priorities, but not assigning them
to the trees until all non-meta rules are assigned to the correct tree nodes.
Then I would pull meta rules out of the bucket and look up each referenced
rule. I would remember the highest tree node of any referenced rule.
If all referenced rules are found for a meta, it does not depend on any other
meta rules, and can be assigned to the meta tree at either the level of the
highest dependency rule found, or the level given for the meta, only if that is
higher than the highest dependency rule.
If not all dependencies are found, I would throw it at the back of the
unprocessed meta list, with a flag saying it had been seen once. (Alternately,
into a reprocessing meta list separate from the current list.)
When the current meta list is depleted, it can be replaced with the postponed
meta list, and that list again processed exactly as above. A flag can be set if
at least one meta is removed from the list into a tree. Any metas still with
unresolved dependencies can again be thrown back into an alternate pool. As
long as at least one meta is removed from the unprocessed list the reprocessing
can be repeated. If all remaining metas are passed and none are placed into the
tree, the remaining metas are either circular or depend on undefined rules. I
would throw them out as errors at that point.
Obviously there are faster ways to perform the above evaluation, but since it
only needs to be done once, simplicity may be a virtue in the implementation.
In any case, the end result is an ordered list if rules to evaluate in the
order they are found in the list. The non-net stuff gets done quickly, and the
net rules queued quickly.
Metas that depend on async net rules are a pain because the net results are
returned out of order. I can't think of a clever way to deal with this, but a
simple brute-force approach is easy. Each net rule needs a list of the metas
that depend on it. Each net meta needs a count of dependencies required to
complete, and a counter initialized to zero. As each net rule completes, it
walks it's dependent list and increments the count for the dependency. If the
incremented count matches the total dependency count the meta rule can be run.
Overall I think that will handle getting things into the right evaluation order
fairly easily and also evaluating them in the correct order without too much
pain.
(Of course I don't recall what the short-circuit flag does exactly. It probably
throws a wrench in the above evaluation mechanism.)
--
You are receiving this mail because:
You are the assignee for the bug.
Loren Wilton <lwilton@earthlink.net> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |lwilton@earthlink.net
--- Comment #8 from Loren Wilton <lwilton@earthlink.net> ---
Just thinking off the top of my head, I think I'd consider something along the
following lines.
1. Conceptually build four prioritized tree-lists of rules:
a. non-net, non-meta
b. non-net, meta
c. net, non-meta
d. net, meta
The tree nodes are the priority order, for each priority where rules exist
there is a list of rules of that priority. The rules are evaluated in tree
order and branch order, in the order given above.
While I've described this as four trees of lists, it could equally be done with
one partitioned tree, where each partition is assigned a base rule priority
higher than any rule priority that can be manually assigned, for instance 0-99,
100-199, etc. The goal is to create the above-described rule evaluation order
constraints.
Non-meta rules are trivially assigned a priority, as it is a given for each
rule.
Meta rules may have been given priorities, but that needs to be considered as a
minimum priority, and can only be used to delay the meta evaluation.
As an implementation I think I'd initially throw all meta rules into a
bucket/list of some sort, remembering their priorities, but not assigning them
to the trees until all non-meta rules are assigned to the correct tree nodes.
Then I would pull meta rules out of the bucket and look up each referenced
rule. I would remember the highest tree node of any referenced rule.
If all referenced rules are found for a meta, it does not depend on any other
meta rules, and can be assigned to the meta tree at either the level of the
highest dependency rule found, or the level given for the meta, only if that is
higher than the highest dependency rule.
If not all dependencies are found, I would throw it at the back of the
unprocessed meta list, with a flag saying it had been seen once. (Alternately,
into a reprocessing meta list separate from the current list.)
When the current meta list is depleted, it can be replaced with the postponed
meta list, and that list again processed exactly as above. A flag can be set if
at least one meta is removed from the list into a tree. Any metas still with
unresolved dependencies can again be thrown back into an alternate pool. As
long as at least one meta is removed from the unprocessed list the reprocessing
can be repeated. If all remaining metas are passed and none are placed into the
tree, the remaining metas are either circular or depend on undefined rules. I
would throw them out as errors at that point.
Obviously there are faster ways to perform the above evaluation, but since it
only needs to be done once, simplicity may be a virtue in the implementation.
In any case, the end result is an ordered list if rules to evaluate in the
order they are found in the list. The non-net stuff gets done quickly, and the
net rules queued quickly.
Metas that depend on async net rules are a pain because the net results are
returned out of order. I can't think of a clever way to deal with this, but a
simple brute-force approach is easy. Each net rule needs a list of the metas
that depend on it. Each net meta needs a count of dependencies required to
complete, and a counter initialized to zero. As each net rule completes, it
walks it's dependent list and increments the count for the dependency. If the
incremented count matches the total dependency count the meta rule can be run.
Overall I think that will handle getting things into the right evaluation order
fairly easily and also evaluating them in the correct order without too much
pain.
(Of course I don't recall what the short-circuit flag does exactly. It probably
throws a wrench in the above evaluation mechanism.)
--
You are receiving this mail because:
You are the assignee for the bug.