[asterisk-dev] extensions.conf included contexts priorities

[Steve Murphy]

On Tue, 2007-04-24 at 12:36 -0400, Jared Smith wrote:
> On 4/24/07, Andrew Kohlsmith <akohlsmith-asterisk at benshaw.com> wrote:
> > I've been using Asterisk for several years now, and I've run across something
> > I am *positive* is unintended.  Testing against trunk and 1.4, the result is
> > the same, so it's something which has been going on for a long long time
> > now...
> 
> Actually, I think this *is* intentend.  As I understand it, here's how
> the extension matching works in Asterisk.  First, Asterisk tries to
> find a match in the current context. If it finds no match, it then
> looks for any switch statements to see if it can find a match there.
> If there is no match there, it then looks at any include statements.
> It should also be noted that for nested includes, Asterisk does a
> depth-first search through the includes.
> 
> As an example, lets modify your earlier example to look like this:
> 
> [bar]
> exten => 555,1,NoOp(exten 555, bar context)
> exten => _XXX,1,NoOp(wildcard match ${EXTEN}, bar context)
> include => baz-1
> 
> [foo]
> exten => 123,1,NoOp(exten 123, foo context)
> exten => 456,1,NoOp(exten 456, foo context)
> include => bar
> include => baz-2
> switch => IAX2/user:pass at otherbox/
> exten => 789,1,NoOp(exten 789, foo context)
> exten => _5XX,1,NoOp(wildcard match ${EXTEN}, foo context)
> 
> [baz-1]
> exten => 555,1,NoOp(exten 555, baz-1 context)
> exten => 333,1,NoOp(exten 333, baz-1 context)
> 
> [baz-2]
> exten => 555,1,NoOp(exten 555, baz-2 context)
> exten => 333,1,NoOp(exten 333, baz-2 context)
> 
> If extenion 555 was dialed in the [foo] context, it would match on the
> wildcard in that context.  If extension 333 was dialed, it would match
> the extension in the [baz-1] context.  In other words, Asterisk would
> go looking in this order:
> 
> 1) the [foo] context itself
> 2) The remote box named otherbox, thanks to the switch statement
> 3) The first included context ([bar] in this case)
> 4) Any includes in the [bar] context (which happens to be [baz-1]
> and, if it didn't find a match there:
> 5) the next included context in the [foo] context (which happens to be [baz-2])
> 
> In short, we can sum it all up like this: Asterisk checks all
> extensions before switches, and all switches before includes.  I hope
> that clears things up for you.  (If I've made a mistake in my
> explanation, please let me know.)
> 
> -Jared

I've been playing with this code, and I do believe Jared is exactly
correct.

But I have a question: I've been experimenting with speeding the pattern
matching up, especially when there's a lot of them, and I have a
choice...
(1). I can replicate current behavior.
(2). I can unify all the included extension patterns into the current
context's search tree.

Depending on the depth of the includes, etc. (2) can definitely speed up
the 
search, but it will tend to do as Andrew thought it (should). If an
included context contains the exact pattern of 555,  and the including
context has a wildcard pattern that would also match, the exact match
would win.

Trouble is, is this desired behavior? Or is having the contexts checked
level by level until a match of any kind is found, the better procedure?

I could see it go either way; but personally, I'd think the preferred
way would be to combine all the patterns and do the match in one pass,
and then go to the switches if that doesn't work. Why? because I'd have
to look at the code to see if the deepest match would be made first, or
the closest first (recursion before check, or after check). If I don't
know this detail before I write up my dialplan, then I'm not sure about
the results I'd get, and I'd only include stuff that wouldn't overlap,
to avoid finding out unpleasantly which way it'd go. If most folks are
including non-overlapping patterns, then (2) would not give them any
unpleasant surprises.

If you think choice (2) would be bad, I'd love to hear how you are
depending on the recursive behavior of the included patterns.

(BTW: It's kind-of-depth-first traversal; here's the relevant code:

  (search for exten in current context)
  (search switches)
  for (i = tmp->includes; i; i = i->next) {
    if (include_valid(i)) {
      if ((e = pbx_find_extension(chan, bypass, q, i->rname, exten,
priority, label, callerid, action)))
        return e;
      if (q->swo)
        return NULL;
    }
  }
  return NULL;

Since it's kinda-depth-first (all the extens in the current context are
searched before it recurses to the next level down), it's kinda hard to
describe exactly who gets searched first. This makes it kinda-hard to
use this behavior reliably.

Jared's example is excellently obtuse! The inclusion tree looks
something like this: 

foo +---+
 (123)  |
 (456)  |
 (789)  |
 (_5XX) |
        |
        +-- bar ----------+
        |    (555)        |
        |    (_XXX)       +--- baz-1
        |                        (555)
        |                        (333)
        +-- baz-2
             (555)
             (333)

Worse yet, if you entered 333, and bar didn't have the _XXX pattern,
which would match, the baz-1 version, or the baz-2?

Interestingly enough, it'd depend on whether the linked lists involved
are 
formed the quick-and-dirty way, which reverses the order, or the
clean-neat way,
which preserves the order, but adds complexity or time. And, I haven't
checked
yet to see which way it goes. There are few who would know this from
memory, and it's certainly not documented. Most folks using includes,
seeing this uncertainty, would simply arrange the dialplan so that it
doesn't matter.

Were the recursion breadth-first, then the rule would be simple: the
patterns at level n from the root of the tree would match before those
in level n+1; but doing breadth-first recursion is harder than
depth-first. I hardly ever have to do it, and then I'd only do it if
there is absolutely no other option.

(BTW: I just checked, the code adds new includes to the end of the list,
so
      baz-1's 333 would match first)

One last BTW: **IF** I were to implement (2), I'd most certainly print a
warning message when an obvious pattern collision was noticed. baz-1's
555 would be noted as a collision against bar's 555, and so would
baz-2's. baz-2's 333 would be noted as a collision against baz-1's. The
colliding patterns would be dropped.


murf

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 3239 bytes
Desc: not available
Url : http://lists.digium.com/pipermail/asterisk-dev/attachments/20070424/c6a2540b/smime.bin