Unlock outgoing dial lock on off nominal path
[asterisk/asterisk.git] / main / pbx.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 1999 - 2008, Digium, Inc.
5  *
6  * Mark Spencer <markster@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18
19 /*! \file
20  *
21  * \brief Core PBX routines.
22  *
23  * \author Mark Spencer <markster@digium.com>
24  */
25
26 /*** MODULEINFO
27         <support_level>core</support_level>
28  ***/
29
30 #include "asterisk.h"
31
32 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
33
34 #include "asterisk/_private.h"
35 #include "asterisk/paths.h"     /* use ast_config_AST_SYSTEM_NAME */
36 #include <ctype.h>
37 #include <time.h>
38 #include <sys/time.h>
39 #if defined(HAVE_SYSINFO)
40 #include <sys/sysinfo.h>
41 #endif
42 #if defined(SOLARIS)
43 #include <sys/loadavg.h>
44 #endif
45
46 #include "asterisk/lock.h"
47 #include "asterisk/cli.h"
48 #include "asterisk/pbx.h"
49 #include "asterisk/channel.h"
50 #include "asterisk/file.h"
51 #include "asterisk/callerid.h"
52 #include "asterisk/cdr.h"
53 #include "asterisk/config.h"
54 #include "asterisk/term.h"
55 #include "asterisk/time.h"
56 #include "asterisk/manager.h"
57 #include "asterisk/ast_expr.h"
58 #include "asterisk/linkedlists.h"
59 #define SAY_STUBS       /* generate declarations and stubs for say methods */
60 #include "asterisk/say.h"
61 #include "asterisk/utils.h"
62 #include "asterisk/causes.h"
63 #include "asterisk/musiconhold.h"
64 #include "asterisk/app.h"
65 #include "asterisk/devicestate.h"
66 #include "asterisk/presencestate.h"
67 #include "asterisk/event.h"
68 #include "asterisk/hashtab.h"
69 #include "asterisk/module.h"
70 #include "asterisk/indications.h"
71 #include "asterisk/taskprocessor.h"
72 #include "asterisk/xmldoc.h"
73 #include "asterisk/astobj2.h"
74 #include "asterisk/stasis_channels.h"
75 #include "asterisk/dial.h"
76
77 /*!
78  * \note I M P O R T A N T :
79  *
80  *              The speed of extension handling will likely be among the most important
81  * aspects of this PBX.  The switching scheme as it exists right now isn't
82  * terribly bad (it's O(N+M), where N is the # of extensions and M is the avg #
83  * of priorities, but a constant search time here would be great ;-)
84  *
85  * A new algorithm to do searching based on a 'compiled' pattern tree is introduced
86  * here, and shows a fairly flat (constant) search time, even for over
87  * 10000 patterns.
88  *
89  * Also, using a hash table for context/priority name lookup can help prevent
90  * the find_extension routines from absorbing exponential cpu cycles as the number
91  * of contexts/priorities grow. I've previously tested find_extension with red-black trees,
92  * which have O(log2(n)) speed. Right now, I'm using hash tables, which do
93  * searches (ideally) in O(1) time. While these techniques do not yield much
94  * speed in small dialplans, they are worth the trouble in large dialplans.
95  *
96  */
97
98 /*** DOCUMENTATION
99         <application name="Answer" language="en_US">
100                 <synopsis>
101                         Answer a channel if ringing.
102                 </synopsis>
103                 <syntax>
104                         <parameter name="delay">
105                                 <para>Asterisk will wait this number of milliseconds before returning to
106                                 the dialplan after answering the call.</para>
107                         </parameter>
108                         <parameter name="nocdr">
109                                 <para>Asterisk will send an answer signal to the calling phone, but will not
110                                 set the disposition or answer time in the CDR for this call.</para>
111                         </parameter>
112                 </syntax>
113                 <description>
114                         <para>If the call has not been answered, this application will
115                         answer it. Otherwise, it has no effect on the call.</para>
116                 </description>
117                 <see-also>
118                         <ref type="application">Hangup</ref>
119                 </see-also>
120         </application>
121         <application name="BackGround" language="en_US">
122                 <synopsis>
123                         Play an audio file while waiting for digits of an extension to go to.
124                 </synopsis>
125                 <syntax>
126                         <parameter name="filenames" required="true" argsep="&amp;">
127                                 <argument name="filename1" required="true" />
128                                 <argument name="filename2" multiple="true" />
129                         </parameter>
130                         <parameter name="options">
131                                 <optionlist>
132                                         <option name="s">
133                                                 <para>Causes the playback of the message to be skipped
134                                                 if the channel is not in the <literal>up</literal> state (i.e. it
135                                                 hasn't been answered yet). If this happens, the
136                                                 application will return immediately.</para>
137                                         </option>
138                                         <option name="n">
139                                                 <para>Don't answer the channel before playing the files.</para>
140                                         </option>
141                                         <option name="m">
142                                                 <para>Only break if a digit hit matches a one digit
143                                                 extension in the destination context.</para>
144                                         </option>
145                                 </optionlist>
146                         </parameter>
147                         <parameter name="langoverride">
148                                 <para>Explicitly specifies which language to attempt to use for the requested sound files.</para>
149                         </parameter>
150                         <parameter name="context">
151                                 <para>This is the dialplan context that this application will use when exiting
152                                 to a dialed extension.</para>
153                         </parameter>
154                 </syntax>
155                 <description>
156                         <para>This application will play the given list of files <emphasis>(do not put extension)</emphasis>
157                         while waiting for an extension to be dialed by the calling channel. To continue waiting
158                         for digits after this application has finished playing files, the <literal>WaitExten</literal>
159                         application should be used.</para>
160                         <para>If one of the requested sound files does not exist, call processing will be terminated.</para>
161                         <para>This application sets the following channel variable upon completion:</para>
162                         <variablelist>
163                                 <variable name="BACKGROUNDSTATUS">
164                                         <para>The status of the background attempt as a text string.</para>
165                                         <value name="SUCCESS" />
166                                         <value name="FAILED" />
167                                 </variable>
168                         </variablelist>
169                 </description>
170                 <see-also>
171                         <ref type="application">ControlPlayback</ref>
172                         <ref type="application">WaitExten</ref>
173                         <ref type="application">BackgroundDetect</ref>
174                         <ref type="function">TIMEOUT</ref>
175                 </see-also>
176         </application>
177         <application name="Busy" language="en_US">
178                 <synopsis>
179                         Indicate the Busy condition.
180                 </synopsis>
181                 <syntax>
182                         <parameter name="timeout">
183                                 <para>If specified, the calling channel will be hung up after the specified number of seconds.
184                                 Otherwise, this application will wait until the calling channel hangs up.</para>
185                         </parameter>
186                 </syntax>
187                 <description>
188                         <para>This application will indicate the busy condition to the calling channel.</para>
189                 </description>
190                 <see-also>
191                         <ref type="application">Congestion</ref>
192                         <ref type="application">Progress</ref>
193                         <ref type="application">Playtones</ref>
194                         <ref type="application">Hangup</ref>
195                 </see-also>
196         </application>
197         <application name="Congestion" language="en_US">
198                 <synopsis>
199                         Indicate the Congestion condition.
200                 </synopsis>
201                 <syntax>
202                         <parameter name="timeout">
203                                 <para>If specified, the calling channel will be hung up after the specified number of seconds.
204                                 Otherwise, this application will wait until the calling channel hangs up.</para>
205                         </parameter>
206                 </syntax>
207                 <description>
208                         <para>This application will indicate the congestion condition to the calling channel.</para>
209                 </description>
210                 <see-also>
211                         <ref type="application">Busy</ref>
212                         <ref type="application">Progress</ref>
213                         <ref type="application">Playtones</ref>
214                         <ref type="application">Hangup</ref>
215                 </see-also>
216         </application>
217         <application name="ExecIfTime" language="en_US">
218                 <synopsis>
219                         Conditional application execution based on the current time.
220                 </synopsis>
221                 <syntax argsep="?">
222                         <parameter name="day_condition" required="true">
223                                 <argument name="times" required="true" />
224                                 <argument name="weekdays" required="true" />
225                                 <argument name="mdays" required="true" />
226                                 <argument name="months" required="true" />
227                                 <argument name="timezone" required="false" />
228                         </parameter>
229                         <parameter name="appname" required="true" hasparams="optional">
230                                 <argument name="appargs" required="true" />
231                         </parameter>
232                 </syntax>
233                 <description>
234                         <para>This application will execute the specified dialplan application, with optional
235                         arguments, if the current time matches the given time specification.</para>
236                 </description>
237                 <see-also>
238                         <ref type="application">Exec</ref>
239                         <ref type="application">ExecIf</ref>
240                         <ref type="application">TryExec</ref>
241                         <ref type="application">GotoIfTime</ref>
242                 </see-also>
243         </application>
244         <application name="Goto" language="en_US">
245                 <synopsis>
246                         Jump to a particular priority, extension, or context.
247                 </synopsis>
248                 <syntax>
249                         <parameter name="context" />
250                         <parameter name="extensions" />
251                         <parameter name="priority" required="true" />
252                 </syntax>
253                 <description>
254                         <para>This application will set the current context, extension, and priority in the channel structure.
255                         After it completes, the pbx engine will continue dialplan execution at the specified location.
256                         If no specific <replaceable>extension</replaceable>, or <replaceable>extension</replaceable> and
257                         <replaceable>context</replaceable>, are specified, then this application will
258                         just set the specified <replaceable>priority</replaceable> of the current extension.</para>
259                         <para>At least a <replaceable>priority</replaceable> is required as an argument, or the goto will
260                         return a <literal>-1</literal>, and the channel and call will be terminated.</para>
261                         <para>If the location that is put into the channel information is bogus, and asterisk cannot
262                         find that location in the dialplan, then the execution engine will try to find and execute the code in
263                         the <literal>i</literal> (invalid) extension in the current context. If that does not exist, it will try to execute the
264                         <literal>h</literal> extension. If neither the <literal>h</literal> nor <literal>i</literal> extensions
265                         have been defined, the channel is hung up, and the execution of instructions on the channel is terminated.
266                         What this means is that, for example, you specify a context that does not exist, then
267                         it will not be possible to find the <literal>h</literal> or <literal>i</literal> extensions,
268                         and the call will terminate!</para>
269                 </description>
270                 <see-also>
271                         <ref type="application">GotoIf</ref>
272                         <ref type="application">GotoIfTime</ref>
273                         <ref type="application">Gosub</ref>
274                         <ref type="application">Macro</ref>
275                 </see-also>
276         </application>
277         <application name="GotoIf" language="en_US">
278                 <synopsis>
279                         Conditional goto.
280                 </synopsis>
281                 <syntax argsep="?">
282                         <parameter name="condition" required="true" />
283                         <parameter name="destination" required="true" argsep=":">
284                                 <argument name="labeliftrue">
285                                         <para>Continue at <replaceable>labeliftrue</replaceable> if the condition is true.
286                                         Takes the form similar to Goto() of [[context,]extension,]priority.</para>
287                                 </argument>
288                                 <argument name="labeliffalse">
289                                         <para>Continue at <replaceable>labeliffalse</replaceable> if the condition is false.
290                                         Takes the form similar to Goto() of [[context,]extension,]priority.</para>
291                                 </argument>
292                         </parameter>
293                 </syntax>
294                 <description>
295                         <para>This application will set the current context, extension, and priority in the channel structure
296                         based on the evaluation of the given condition. After this application completes, the
297                         pbx engine will continue dialplan execution at the specified location in the dialplan.
298                         The labels are specified with the same syntax as used within the Goto application.
299                         If the label chosen by the condition is omitted, no jump is performed, and the execution passes to the
300                         next instruction. If the target location is bogus, and does not exist, the execution engine will try
301                         to find and execute the code in the <literal>i</literal> (invalid) extension in the current context.
302                         If that does not exist, it will try to execute the <literal>h</literal> extension.
303                         If neither the <literal>h</literal> nor <literal>i</literal> extensions have been defined,
304                         the channel is hung up, and the execution of instructions on the channel is terminated.
305                         Remember that this command can set the current context, and if the context specified
306                         does not exist, then it will not be able to find any 'h' or 'i' extensions there, and
307                         the channel and call will both be terminated!.</para>
308                 </description>
309                 <see-also>
310                         <ref type="application">Goto</ref>
311                         <ref type="application">GotoIfTime</ref>
312                         <ref type="application">GosubIf</ref>
313                         <ref type="application">MacroIf</ref>
314                 </see-also>
315         </application>
316         <application name="GotoIfTime" language="en_US">
317                 <synopsis>
318                         Conditional Goto based on the current time.
319                 </synopsis>
320                 <syntax argsep="?">
321                         <parameter name="condition" required="true">
322                                 <argument name="times" required="true" />
323                                 <argument name="weekdays" required="true" />
324                                 <argument name="mdays" required="true" />
325                                 <argument name="months" required="true" />
326                                 <argument name="timezone" required="false" />
327                         </parameter>
328                         <parameter name="destination" required="true" argsep=":">
329                                 <argument name="labeliftrue">
330                                         <para>Continue at <replaceable>labeliftrue</replaceable> if the condition is true.
331                                         Takes the form similar to Goto() of [[context,]extension,]priority.</para>
332                                 </argument>
333                                 <argument name="labeliffalse">
334                                         <para>Continue at <replaceable>labeliffalse</replaceable> if the condition is false.
335                                         Takes the form similar to Goto() of [[context,]extension,]priority.</para>
336                                 </argument>
337                         </parameter>
338                 </syntax>
339                 <description>
340                         <para>This application will set the context, extension, and priority in the channel structure
341                         based on the evaluation of the given time specification. After this application completes,
342                         the pbx engine will continue dialplan execution at the specified location in the dialplan.
343                         If the current time is within the given time specification, the channel will continue at
344                         <replaceable>labeliftrue</replaceable>. Otherwise the channel will continue at <replaceable>labeliffalse</replaceable>.
345                         If the label chosen by the condition is omitted, no jump is performed, and execution passes to the next
346                         instruction. If the target jump location is bogus, the same actions would be taken as for <literal>Goto</literal>.
347                         Further information on the time specification can be found in examples
348                         illustrating how to do time-based context includes in the dialplan.</para>
349                 </description>
350                 <see-also>
351                         <ref type="application">GotoIf</ref>
352                         <ref type="application">Goto</ref>
353                         <ref type="function">IFTIME</ref>
354                         <ref type="function">TESTTIME</ref>
355                 </see-also>
356         </application>
357         <application name="ImportVar" language="en_US">
358                 <synopsis>
359                         Import a variable from a channel into a new variable.
360                 </synopsis>
361                 <syntax argsep="=">
362                         <parameter name="newvar" required="true" />
363                         <parameter name="vardata" required="true">
364                                 <argument name="channelname" required="true" />
365                                 <argument name="variable" required="true" />
366                         </parameter>
367                 </syntax>
368                 <description>
369                         <para>This application imports a <replaceable>variable</replaceable> from the specified
370                         <replaceable>channel</replaceable> (as opposed to the current one) and stores it as a variable
371                         (<replaceable>newvar</replaceable>) in the current channel (the channel that is calling this
372                         application). Variables created by this application have the same inheritance properties as those
373                         created with the <literal>Set</literal> application.</para>
374                 </description>
375                 <see-also>
376                         <ref type="application">Set</ref>
377                 </see-also>
378         </application>
379         <application name="Hangup" language="en_US">
380                 <synopsis>
381                         Hang up the calling channel.
382                 </synopsis>
383                 <syntax>
384                         <parameter name="causecode">
385                                 <para>If a <replaceable>causecode</replaceable> is given the channel's
386                                 hangup cause will be set to the given value.</para>
387                         </parameter>
388                 </syntax>
389                 <description>
390                         <para>This application will hang up the calling channel.</para>
391                 </description>
392                 <see-also>
393                         <ref type="application">Answer</ref>
394                         <ref type="application">Busy</ref>
395                         <ref type="application">Congestion</ref>
396                 </see-also>
397         </application>
398         <application name="Incomplete" language="en_US">
399                 <synopsis>
400                         Returns AST_PBX_INCOMPLETE value.
401                 </synopsis>
402                 <syntax>
403                         <parameter name="n">
404                                 <para>If specified, then Incomplete will not attempt to answer the channel first.</para>
405                                 <note><para>Most channel types need to be in Answer state in order to receive DTMF.</para></note>
406                         </parameter>
407                 </syntax>
408                 <description>
409                         <para>Signals the PBX routines that the previous matched extension is incomplete
410                         and that further input should be allowed before matching can be considered
411                         to be complete.  Can be used within a pattern match when certain criteria warrants
412                         a longer match.</para>
413                 </description>
414         </application>
415         <application name="NoOp" language="en_US">
416                 <synopsis>
417                         Do Nothing (No Operation).
418                 </synopsis>
419                 <syntax>
420                         <parameter name="text">
421                                 <para>Any text provided can be viewed at the Asterisk CLI.</para>
422                         </parameter>
423                 </syntax>
424                 <description>
425                         <para>This application does nothing. However, it is useful for debugging purposes.</para>
426                         <para>This method can be used to see the evaluations of variables or functions without having any effect.</para>
427                 </description>
428                 <see-also>
429                         <ref type="application">Verbose</ref>
430                         <ref type="application">Log</ref>
431                 </see-also>
432         </application>
433         <application name="Proceeding" language="en_US">
434                 <synopsis>
435                         Indicate proceeding.
436                 </synopsis>
437                 <syntax />
438                 <description>
439                         <para>This application will request that a proceeding message be provided to the calling channel.</para>
440                 </description>
441         </application>
442         <application name="Progress" language="en_US">
443                 <synopsis>
444                         Indicate progress.
445                 </synopsis>
446                 <syntax />
447                 <description>
448                         <para>This application will request that in-band progress information be provided to the calling channel.</para>
449                 </description>
450                 <see-also>
451                         <ref type="application">Busy</ref>
452                         <ref type="application">Congestion</ref>
453                         <ref type="application">Ringing</ref>
454                         <ref type="application">Playtones</ref>
455                 </see-also>
456         </application>
457         <application name="RaiseException" language="en_US">
458                 <synopsis>
459                         Handle an exceptional condition.
460                 </synopsis>
461                 <syntax>
462                         <parameter name="reason" required="true" />
463                 </syntax>
464                 <description>
465                         <para>This application will jump to the <literal>e</literal> extension in the current context, setting the
466                         dialplan function EXCEPTION(). If the <literal>e</literal> extension does not exist, the call will hangup.</para>
467                 </description>
468                 <see-also>
469                         <ref type="function">Exception</ref>
470                 </see-also>
471         </application>
472         <application name="Ringing" language="en_US">
473                 <synopsis>
474                         Indicate ringing tone.
475                 </synopsis>
476                 <syntax />
477                 <description>
478                         <para>This application will request that the channel indicate a ringing tone to the user.</para>
479                 </description>
480                 <see-also>
481                         <ref type="application">Busy</ref>
482                         <ref type="application">Congestion</ref>
483                         <ref type="application">Progress</ref>
484                         <ref type="application">Playtones</ref>
485                 </see-also>
486         </application>
487         <application name="SayAlpha" language="en_US">
488                 <synopsis>
489                         Say Alpha.
490                 </synopsis>
491                 <syntax>
492                         <parameter name="string" required="true" />
493                 </syntax>
494                 <description>
495                         <para>This application will play the sounds that correspond to the letters of the
496                         given <replaceable>string</replaceable>.</para>
497                 </description>
498                 <see-also>
499                         <ref type="application">SayDigits</ref>
500                         <ref type="application">SayNumber</ref>
501                         <ref type="application">SayPhonetic</ref>
502                         <ref type="function">CHANNEL</ref>
503                 </see-also>
504         </application>
505         <application name="SayDigits" language="en_US">
506                 <synopsis>
507                         Say Digits.
508                 </synopsis>
509                 <syntax>
510                         <parameter name="digits" required="true" />
511                 </syntax>
512                 <description>
513                         <para>This application will play the sounds that correspond to the digits of
514                         the given number. This will use the language that is currently set for the channel.</para>
515                 </description>
516                 <see-also>
517                         <ref type="application">SayAlpha</ref>
518                         <ref type="application">SayNumber</ref>
519                         <ref type="application">SayPhonetic</ref>
520                         <ref type="function">CHANNEL</ref>
521                 </see-also>
522         </application>
523         <application name="SayNumber" language="en_US">
524                 <synopsis>
525                         Say Number.
526                 </synopsis>
527                 <syntax>
528                         <parameter name="digits" required="true" />
529                         <parameter name="gender" />
530                 </syntax>
531                 <description>
532                         <para>This application will play the sounds that correspond to the given <replaceable>digits</replaceable>.
533                         Optionally, a <replaceable>gender</replaceable> may be specified. This will use the language that is currently
534                         set for the channel. See the CHANNEL() function for more information on setting the language for the channel.</para>
535                 </description>
536                 <see-also>
537                         <ref type="application">SayAlpha</ref>
538                         <ref type="application">SayDigits</ref>
539                         <ref type="application">SayPhonetic</ref>
540                         <ref type="function">CHANNEL</ref>
541                 </see-also>
542         </application>
543         <application name="SayPhonetic" language="en_US">
544                 <synopsis>
545                         Say Phonetic.
546                 </synopsis>
547                 <syntax>
548                         <parameter name="string" required="true" />
549                 </syntax>
550                 <description>
551                         <para>This application will play the sounds from the phonetic alphabet that correspond to the
552                         letters in the given <replaceable>string</replaceable>.</para>
553                 </description>
554                 <see-also>
555                         <ref type="application">SayAlpha</ref>
556                         <ref type="application">SayDigits</ref>
557                         <ref type="application">SayNumber</ref>
558                 </see-also>
559         </application>
560         <application name="Set" language="en_US">
561                 <synopsis>
562                         Set channel variable or function value.
563                 </synopsis>
564                 <syntax argsep="=">
565                         <parameter name="name" required="true" />
566                         <parameter name="value" required="true" />
567                 </syntax>
568                 <description>
569                         <para>This function can be used to set the value of channel variables or dialplan functions.
570                         When setting variables, if the variable name is prefixed with <literal>_</literal>,
571                         the variable will be inherited into channels created from the current channel.
572                         If the variable name is prefixed with <literal>__</literal>, the variable will be
573                         inherited into channels created from the current channel and all children channels.</para>
574                         <note><para>If (and only if), in <filename>/etc/asterisk/asterisk.conf</filename>, you have
575                         a <literal>[compat]</literal> category, and you have <literal>app_set = 1.4</literal> under that, then
576                         the behavior of this app changes, and strips surrounding quotes from the right hand side as
577                         it did previously in 1.4.
578                         The advantages of not stripping out quoting, and not caring about the separator characters (comma and vertical bar)
579                         were sufficient to make these changes in 1.6. Confusion about how many backslashes would be needed to properly
580                         protect separators and quotes in various database access strings has been greatly
581                         reduced by these changes.</para></note>
582                 </description>
583                 <see-also>
584                         <ref type="application">MSet</ref>
585                         <ref type="function">GLOBAL</ref>
586                         <ref type="function">SET</ref>
587                         <ref type="function">ENV</ref>
588                 </see-also>
589         </application>
590         <application name="MSet" language="en_US">
591                 <synopsis>
592                         Set channel variable(s) or function value(s).
593                 </synopsis>
594                 <syntax>
595                         <parameter name="set1" required="true" argsep="=">
596                                 <argument name="name1" required="true" />
597                                 <argument name="value1" required="true" />
598                         </parameter>
599                         <parameter name="set2" multiple="true" argsep="=">
600                                 <argument name="name2" required="true" />
601                                 <argument name="value2" required="true" />
602                         </parameter>
603                 </syntax>
604                 <description>
605                         <para>This function can be used to set the value of channel variables or dialplan functions.
606                         When setting variables, if the variable name is prefixed with <literal>_</literal>,
607                         the variable will be inherited into channels created from the current channel
608                         If the variable name is prefixed with <literal>__</literal>, the variable will be
609                         inherited into channels created from the current channel and all children channels.
610                         MSet behaves in a similar fashion to the way Set worked in 1.2/1.4 and is thus
611                         prone to doing things that you may not expect. For example, it strips surrounding
612                         double-quotes from the right-hand side (value). If you need to put a separator
613                         character (comma or vert-bar), you will need to escape them by inserting a backslash
614                         before them. Avoid its use if possible.</para>
615                 </description>
616                 <see-also>
617                         <ref type="application">Set</ref>
618                 </see-also>
619         </application>
620         <application name="SetAMAFlags" language="en_US">
621                 <synopsis>
622                         Set the AMA Flags.
623                 </synopsis>
624                 <syntax>
625                         <parameter name="flag" />
626                 </syntax>
627                 <description>
628                         <para>This application will set the channel's AMA Flags for billing purposes.</para>
629                         <warning><para>This application is deprecated. Please use the CHANNEL function instead.</para></warning>
630                 </description>
631                 <see-also>
632                         <ref type="function">CDR</ref>
633                         <ref type="function">CHANNEL</ref>
634                 </see-also>
635         </application>
636         <application name="Wait" language="en_US">
637                 <synopsis>
638                         Waits for some time.
639                 </synopsis>
640                 <syntax>
641                         <parameter name="seconds" required="true">
642                                 <para>Can be passed with fractions of a second. For example, <literal>1.5</literal> will ask the
643                                 application to wait for 1.5 seconds.</para>
644                         </parameter>
645                 </syntax>
646                 <description>
647                         <para>This application waits for a specified number of <replaceable>seconds</replaceable>.</para>
648                 </description>
649         </application>
650         <application name="WaitExten" language="en_US">
651                 <synopsis>
652                         Waits for an extension to be entered.
653                 </synopsis>
654                 <syntax>
655                         <parameter name="seconds">
656                                 <para>Can be passed with fractions of a second. For example, <literal>1.5</literal> will ask the
657                                 application to wait for 1.5 seconds.</para>
658                         </parameter>
659                         <parameter name="options">
660                                 <optionlist>
661                                         <option name="m">
662                                                 <para>Provide music on hold to the caller while waiting for an extension.</para>
663                                                 <argument name="x">
664                                                         <para>Specify the class for music on hold. <emphasis>CHANNEL(musicclass) will
665                                                         be used instead if set</emphasis></para>
666                                                 </argument>
667                                         </option>
668                                 </optionlist>
669                         </parameter>
670                 </syntax>
671                 <description>
672                         <para>This application waits for the user to enter a new extension for a specified number
673                         of <replaceable>seconds</replaceable>.</para>
674                         <xi:include xpointer="xpointer(/docs/application[@name='Macro']/description/warning[2])" />
675                 </description>
676                 <see-also>
677                         <ref type="application">Background</ref>
678                         <ref type="function">TIMEOUT</ref>
679                 </see-also>
680         </application>
681         <function name="EXCEPTION" language="en_US">
682                 <synopsis>
683                         Retrieve the details of the current dialplan exception.
684                 </synopsis>
685                 <syntax>
686                         <parameter name="field" required="true">
687                                 <para>The following fields are available for retrieval:</para>
688                                 <enumlist>
689                                         <enum name="reason">
690                                                 <para>INVALID, ERROR, RESPONSETIMEOUT, ABSOLUTETIMEOUT, or custom
691                                                 value set by the RaiseException() application</para>
692                                         </enum>
693                                         <enum name="context">
694                                                 <para>The context executing when the exception occurred.</para>
695                                         </enum>
696                                         <enum name="exten">
697                                                 <para>The extension executing when the exception occurred.</para>
698                                         </enum>
699                                         <enum name="priority">
700                                                 <para>The numeric priority executing when the exception occurred.</para>
701                                         </enum>
702                                 </enumlist>
703                         </parameter>
704                 </syntax>
705                 <description>
706                         <para>Retrieve the details (specified <replaceable>field</replaceable>) of the current dialplan exception.</para>
707                 </description>
708                 <see-also>
709                         <ref type="application">RaiseException</ref>
710                 </see-also>
711         </function>
712         <function name="TESTTIME" language="en_US">
713                 <synopsis>
714                         Sets a time to be used with the channel to test logical conditions.
715                 </synopsis>
716                 <syntax>
717                         <parameter name="date" required="true" argsep=" ">
718                                 <para>Date in ISO 8601 format</para>
719                         </parameter>
720                         <parameter name="time" required="true" argsep=" ">
721                                 <para>Time in HH:MM:SS format (24-hour time)</para>
722                         </parameter>
723                         <parameter name="zone" required="false">
724                                 <para>Timezone name</para>
725                         </parameter>
726                 </syntax>
727                 <description>
728                         <para>To test dialplan timing conditions at times other than the current time, use
729                         this function to set an alternate date and time.  For example, you may wish to evaluate
730                         whether a location will correctly identify to callers that the area is closed on Christmas
731                         Day, when Christmas would otherwise fall on a day when the office is normally open.</para>
732                 </description>
733                 <see-also>
734                         <ref type="application">GotoIfTime</ref>
735                 </see-also>
736         </function>
737         <manager name="ShowDialPlan" language="en_US">
738                 <synopsis>
739                         Show dialplan contexts and extensions
740                 </synopsis>
741                 <syntax>
742                         <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
743                         <parameter name="Extension">
744                                 <para>Show a specific extension.</para>
745                         </parameter>
746                         <parameter name="Context">
747                                 <para>Show a specific context.</para>
748                         </parameter>
749                 </syntax>
750                 <description>
751                         <para>Show dialplan contexts and extensions. Be aware that showing the full dialplan
752                         may take a lot of capacity.</para>
753                 </description>
754         </manager>
755  ***/
756
757 #ifdef LOW_MEMORY
758 #define EXT_DATA_SIZE 256
759 #else
760 #define EXT_DATA_SIZE 8192
761 #endif
762
763 #define SWITCH_DATA_LENGTH 256
764
765 #define VAR_BUF_SIZE 4096
766
767 #define VAR_NORMAL              1
768 #define VAR_SOFTTRAN    2
769 #define VAR_HARDTRAN    3
770
771 #define BACKGROUND_SKIP         (1 << 0)
772 #define BACKGROUND_NOANSWER     (1 << 1)
773 #define BACKGROUND_MATCHEXTEN   (1 << 2)
774 #define BACKGROUND_PLAYBACK     (1 << 3)
775
776 AST_APP_OPTIONS(background_opts, {
777         AST_APP_OPTION('s', BACKGROUND_SKIP),
778         AST_APP_OPTION('n', BACKGROUND_NOANSWER),
779         AST_APP_OPTION('m', BACKGROUND_MATCHEXTEN),
780         AST_APP_OPTION('p', BACKGROUND_PLAYBACK),
781 });
782
783 #define WAITEXTEN_MOH           (1 << 0)
784 #define WAITEXTEN_DIALTONE      (1 << 1)
785
786 AST_APP_OPTIONS(waitexten_opts, {
787         AST_APP_OPTION_ARG('m', WAITEXTEN_MOH, 0),
788         AST_APP_OPTION_ARG('d', WAITEXTEN_DIALTONE, 0),
789 });
790
791 struct ast_context;
792 struct ast_app;
793
794 AST_THREADSTORAGE(switch_data);
795 AST_THREADSTORAGE(extensionstate_buf);
796
797 /*!
798    \brief ast_exten: An extension
799         The dialplan is saved as a linked list with each context
800         having it's own linked list of extensions - one item per
801         priority.
802 */
803 struct ast_exten {
804         char *exten;                    /*!< Extension name */
805         int matchcid;                   /*!< Match caller id ? */
806         const char *cidmatch;           /*!< Caller id to match for this extension */
807         int priority;                   /*!< Priority */
808         const char *label;              /*!< Label */
809         struct ast_context *parent;     /*!< The context this extension belongs to  */
810         const char *app;                /*!< Application to execute */
811         struct ast_app *cached_app;     /*!< Cached location of application */
812         void *data;                     /*!< Data to use (arguments) */
813         void (*datad)(void *);          /*!< Data destructor */
814         struct ast_exten *peer;         /*!< Next higher priority with our extension */
815         struct ast_hashtab *peer_table;    /*!< Priorities list in hashtab form -- only on the head of the peer list */
816         struct ast_hashtab *peer_label_table; /*!< labeled priorities in the peers -- only on the head of the peer list */
817         const char *registrar;          /*!< Registrar */
818         struct ast_exten *next;         /*!< Extension with a greater ID */
819         char stuff[0];
820 };
821
822 /*! \brief ast_include: include= support in extensions.conf */
823 struct ast_include {
824         const char *name;
825         const char *rname;                      /*!< Context to include */
826         const char *registrar;                  /*!< Registrar */
827         int hastime;                            /*!< If time construct exists */
828         struct ast_timing timing;               /*!< time construct */
829         struct ast_include *next;               /*!< Link them together */
830         char stuff[0];
831 };
832
833 /*! \brief ast_sw: Switch statement in extensions.conf */
834 struct ast_sw {
835         char *name;
836         const char *registrar;                  /*!< Registrar */
837         char *data;                             /*!< Data load */
838         int eval;
839         AST_LIST_ENTRY(ast_sw) list;
840         char stuff[0];
841 };
842
843 /*! \brief ast_ignorepat: Ignore patterns in dial plan */
844 struct ast_ignorepat {
845         const char *registrar;
846         struct ast_ignorepat *next;
847         const char pattern[0];
848 };
849
850 /*! \brief match_char: forms a syntax tree for quick matching of extension patterns */
851 struct match_char
852 {
853         int is_pattern; /* the pattern started with '_' */
854         int deleted;    /* if this is set, then... don't return it */
855         int specificity; /* simply the strlen of x, or 10 for X, 9 for Z, and 8 for N; and '.' and '!' will add 11 ? */
856         struct match_char *alt_char;
857         struct match_char *next_char;
858         struct ast_exten *exten; /* attached to last char of a pattern for exten */
859         char x[1];       /* the pattern itself-- matches a single char */
860 };
861
862 struct scoreboard  /* make sure all fields are 0 before calling new_find_extension */
863 {
864         int total_specificity;
865         int total_length;
866         char last_char;   /* set to ! or . if they are the end of the pattern */
867         int canmatch;     /* if the string to match was just too short */
868         struct match_char *node;
869         struct ast_exten *canmatch_exten;
870         struct ast_exten *exten;
871 };
872
873 /*! \brief ast_context: An extension context */
874 struct ast_context {
875         ast_rwlock_t lock;                      /*!< A lock to prevent multiple threads from clobbering the context */
876         struct ast_exten *root;                 /*!< The root of the list of extensions */
877         struct ast_hashtab *root_table;            /*!< For exact matches on the extensions in the pattern tree, and for traversals of the pattern_tree  */
878         struct match_char *pattern_tree;        /*!< A tree to speed up extension pattern matching */
879         struct ast_context *next;               /*!< Link them together */
880         struct ast_include *includes;           /*!< Include other contexts */
881         struct ast_ignorepat *ignorepats;       /*!< Patterns for which to continue playing dialtone */
882         char *registrar;                        /*!< Registrar -- make sure you malloc this, as the registrar may have to survive module unloads */
883         int refcount;                   /*!< each module that would have created this context should inc/dec this as appropriate */
884         AST_LIST_HEAD_NOLOCK(, ast_sw) alts;    /*!< Alternative switches */
885         ast_mutex_t macrolock;                  /*!< A lock to implement "exclusive" macros - held whilst a call is executing in the macro */
886         char name[0];                           /*!< Name of the context */
887 };
888
889 /*! \brief ast_app: A registered application */
890 struct ast_app {
891         int (*execute)(struct ast_channel *chan, const char *data);
892         AST_DECLARE_STRING_FIELDS(
893                 AST_STRING_FIELD(synopsis);     /*!< Synopsis text for 'show applications' */
894                 AST_STRING_FIELD(description);  /*!< Description (help text) for 'show application &lt;name&gt;' */
895                 AST_STRING_FIELD(syntax);       /*!< Syntax text for 'core show applications' */
896                 AST_STRING_FIELD(arguments);    /*!< Arguments description */
897                 AST_STRING_FIELD(seealso);      /*!< See also */
898         );
899 #ifdef AST_XML_DOCS
900         enum ast_doc_src docsrc;                /*!< Where the documentation come from. */
901 #endif
902         AST_RWLIST_ENTRY(ast_app) list;         /*!< Next app in list */
903         struct ast_module *module;              /*!< Module this app belongs to */
904         char name[0];                           /*!< Name of the application */
905 };
906
907 /*! \brief ast_state_cb: An extension state notify register item */
908 struct ast_state_cb {
909         /*! Watcher ID returned when registered. */
910         int id;
911         /*! Arbitrary data passed for callbacks. */
912         void *data;
913         /*! Flag if this callback is an extended callback containing detailed device status */
914         int extended;
915         /*! Callback when state changes. */
916         ast_state_cb_type change_cb;
917         /*! Callback when destroyed so any resources given by the registerer can be freed. */
918         ast_state_cb_destroy_type destroy_cb;
919         /*! \note Only used by ast_merge_contexts_and_delete */
920         AST_LIST_ENTRY(ast_state_cb) entry;
921 };
922
923 /*!
924  * \brief Structure for dial plan hints
925  *
926  * \note Hints are pointers from an extension in the dialplan to
927  * one or more devices (tech/name)
928  *
929  * See \ref AstExtState
930  */
931 struct ast_hint {
932         /*!
933          * \brief Hint extension
934          *
935          * \note
936          * Will never be NULL while the hint is in the hints container.
937          */
938         struct ast_exten *exten;
939         struct ao2_container *callbacks; /*!< Device state callback container for this extension */
940
941         /*! Dev state variables */
942         int laststate;                  /*!< Last known device state */
943
944         /*! Presence state variables */
945         int last_presence_state;     /*!< Last known presence state */
946         char *last_presence_subtype; /*!< Last known presence subtype string */
947         char *last_presence_message; /*!< Last known presence message string */
948
949         char context_name[AST_MAX_CONTEXT];/*!< Context of destroyed hint extension. */
950         char exten_name[AST_MAX_EXTENSION];/*!< Extension of destroyed hint extension. */
951 };
952
953
954 #define HINTDEVICE_DATA_LENGTH 16
955 AST_THREADSTORAGE(hintdevice_data);
956
957 /* --- Hash tables of various objects --------*/
958 #ifdef LOW_MEMORY
959 #define HASH_EXTENHINT_SIZE 17
960 #else
961 #define HASH_EXTENHINT_SIZE 563
962 #endif
963
964
965 /*! \brief Container for hint devices */
966 static struct ao2_container *hintdevices;
967
968 /*!
969  * \brief Structure for dial plan hint devices
970  * \note hintdevice is one device pointing to a hint.
971  */
972 struct ast_hintdevice {
973         /*!
974          * \brief Hint this hintdevice belongs to.
975          * \note Holds a reference to the hint object.
976          */
977         struct ast_hint *hint;
978         /*! Name of the hint device. */
979         char hintdevice[1];
980 };
981
982
983 /*!
984  * \note Using the device for hash
985  */
986 static int hintdevice_hash_cb(const void *obj, const int flags)
987 {
988         const struct ast_hintdevice *ext = obj;
989
990         return ast_str_case_hash(ext->hintdevice);
991 }
992 /*!
993  * \note Devices on hints are not unique so no CMP_STOP is returned
994  * Dont use ao2_find against hintdevices container cause there always
995  * could be more than one result.
996  */
997 static int hintdevice_cmp_multiple(void *obj, void *arg, int flags)
998 {
999         struct ast_hintdevice *ext = obj, *ext2 = arg;
1000
1001         return !strcasecmp(ext->hintdevice, ext2->hintdevice) ? CMP_MATCH  : 0;
1002 }
1003
1004 /*
1005  * \details This is used with ao2_callback to remove old devices
1006  * when they are linked to the hint
1007 */
1008 static int hintdevice_remove_cb(void *deviceobj, void *arg, int flags)
1009 {
1010         struct ast_hintdevice *device = deviceobj;
1011         struct ast_hint *hint = arg;
1012
1013         return (device->hint == hint) ? CMP_MATCH : 0;
1014 }
1015
1016 static int remove_hintdevice(struct ast_hint *hint)
1017 {
1018         /* iterate through all devices and remove the devices which are linked to this hint */
1019         ao2_t_callback(hintdevices, OBJ_NODATA | OBJ_MULTIPLE | OBJ_UNLINK,
1020                 hintdevice_remove_cb, hint,
1021                 "callback to remove all devices which are linked to a hint");
1022         return 0;
1023 }
1024
1025 static char *parse_hint_device(struct ast_str *hint_args);
1026 /*!
1027  * \internal
1028  * \brief Destroy the given hintdevice object.
1029  *
1030  * \param obj Hint device to destroy.
1031  *
1032  * \return Nothing
1033  */
1034 static void hintdevice_destroy(void *obj)
1035 {
1036         struct ast_hintdevice *doomed = obj;
1037
1038         if (doomed->hint) {
1039                 ao2_ref(doomed->hint, -1);
1040                 doomed->hint = NULL;
1041         }
1042 }
1043
1044 /*! \brief add hintdevice structure and link it into the container.
1045  */
1046 static int add_hintdevice(struct ast_hint *hint, const char *devicelist)
1047 {
1048         struct ast_str *str;
1049         char *parse;
1050         char *cur;
1051         struct ast_hintdevice *device;
1052         int devicelength;
1053
1054         if (!hint || !devicelist) {
1055                 /* Trying to add garbage? Don't bother. */
1056                 return 0;
1057         }
1058         if (!(str = ast_str_thread_get(&hintdevice_data, 16))) {
1059                 return -1;
1060         }
1061         ast_str_set(&str, 0, "%s", devicelist);
1062         parse = parse_hint_device(str);
1063
1064         while ((cur = strsep(&parse, "&"))) {
1065                 devicelength = strlen(cur);
1066                 device = ao2_t_alloc(sizeof(*device) + devicelength, hintdevice_destroy,
1067                         "allocating a hintdevice structure");
1068                 if (!device) {
1069                         return -1;
1070                 }
1071                 strcpy(device->hintdevice, cur);
1072                 ao2_ref(hint, +1);
1073                 device->hint = hint;
1074                 ao2_t_link(hintdevices, device, "Linking device into hintdevice container.");
1075                 ao2_t_ref(device, -1, "hintdevice is linked so we can unref");
1076         }
1077
1078         return 0;
1079 }
1080
1081
1082 static const struct cfextension_states {
1083         int extension_state;
1084         const char * const text;
1085 } extension_states[] = {
1086         { AST_EXTENSION_NOT_INUSE,                     "Idle" },
1087         { AST_EXTENSION_INUSE,                         "InUse" },
1088         { AST_EXTENSION_BUSY,                          "Busy" },
1089         { AST_EXTENSION_UNAVAILABLE,                   "Unavailable" },
1090         { AST_EXTENSION_RINGING,                       "Ringing" },
1091         { AST_EXTENSION_INUSE | AST_EXTENSION_RINGING, "InUse&Ringing" },
1092         { AST_EXTENSION_ONHOLD,                        "Hold" },
1093         { AST_EXTENSION_INUSE | AST_EXTENSION_ONHOLD,  "InUse&Hold" }
1094 };
1095
1096 struct pbx_exception {
1097         AST_DECLARE_STRING_FIELDS(
1098                 AST_STRING_FIELD(context);      /*!< Context associated with this exception */
1099                 AST_STRING_FIELD(exten);        /*!< Exten associated with this exception */
1100                 AST_STRING_FIELD(reason);               /*!< The exception reason */
1101         );
1102
1103         int priority;                           /*!< Priority associated with this exception */
1104 };
1105
1106 static int pbx_builtin_answer(struct ast_channel *, const char *);
1107 static int pbx_builtin_goto(struct ast_channel *, const char *);
1108 static int pbx_builtin_hangup(struct ast_channel *, const char *);
1109 static int pbx_builtin_background(struct ast_channel *, const char *);
1110 static int pbx_builtin_wait(struct ast_channel *, const char *);
1111 static int pbx_builtin_waitexten(struct ast_channel *, const char *);
1112 static int pbx_builtin_incomplete(struct ast_channel *, const char *);
1113 static int pbx_builtin_setamaflags(struct ast_channel *, const char *);
1114 static int pbx_builtin_ringing(struct ast_channel *, const char *);
1115 static int pbx_builtin_proceeding(struct ast_channel *, const char *);
1116 static int pbx_builtin_progress(struct ast_channel *, const char *);
1117 static int pbx_builtin_congestion(struct ast_channel *, const char *);
1118 static int pbx_builtin_busy(struct ast_channel *, const char *);
1119 static int pbx_builtin_noop(struct ast_channel *, const char *);
1120 static int pbx_builtin_gotoif(struct ast_channel *, const char *);
1121 static int pbx_builtin_gotoiftime(struct ast_channel *, const char *);
1122 static int pbx_builtin_execiftime(struct ast_channel *, const char *);
1123 static int pbx_builtin_saynumber(struct ast_channel *, const char *);
1124 static int pbx_builtin_saydigits(struct ast_channel *, const char *);
1125 static int pbx_builtin_saycharacters(struct ast_channel *, const char *);
1126 static int pbx_builtin_sayphonetic(struct ast_channel *, const char *);
1127 static int matchcid(const char *cidpattern, const char *callerid);
1128 #ifdef NEED_DEBUG
1129 static void log_match_char_tree(struct match_char *node, char *prefix); /* for use anywhere */
1130 #endif
1131 static int pbx_builtin_importvar(struct ast_channel *, const char *);
1132 static void set_ext_pri(struct ast_channel *c, const char *exten, int pri);
1133 static void new_find_extension(const char *str, struct scoreboard *score,
1134                 struct match_char *tree, int length, int spec, const char *callerid,
1135                 const char *label, enum ext_match_t action);
1136 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern);
1137 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con,
1138                 struct ast_exten *e1, int findonly);
1139 static void create_match_char_tree(struct ast_context *con);
1140 static struct ast_exten *get_canmatch_exten(struct match_char *node);
1141 static void destroy_pattern_tree(struct match_char *pattern_tree);
1142 static int hashtab_compare_extens(const void *ha_a, const void *ah_b);
1143 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b);
1144 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b);
1145 static unsigned int hashtab_hash_extens(const void *obj);
1146 static unsigned int hashtab_hash_priority(const void *obj);
1147 static unsigned int hashtab_hash_labels(const void *obj);
1148 static void __ast_internal_context_destroy( struct ast_context *con);
1149 static int ast_add_extension_nolock(const char *context, int replace, const char *extension,
1150         int priority, const char *label, const char *callerid,
1151         const char *application, void *data, void (*datad)(void *), const char *registrar);
1152 static int ast_add_extension2_lockopt(struct ast_context *con,
1153         int replace, const char *extension, int priority, const char *label, const char *callerid,
1154         const char *application, void *data, void (*datad)(void *),
1155         const char *registrar, int lock_context);
1156 static struct ast_context *find_context_locked(const char *context);
1157 static struct ast_context *find_context(const char *context);
1158 static void get_device_state_causing_channels(struct ao2_container *c);
1159
1160 /*!
1161  * \internal
1162  * \brief Character array comparison function for qsort.
1163  *
1164  * \param a Left side object.
1165  * \param b Right side object.
1166  *
1167  * \retval <0 if a < b
1168  * \retval =0 if a = b
1169  * \retval >0 if a > b
1170  */
1171 static int compare_char(const void *a, const void *b)
1172 {
1173         const unsigned char *ac = a;
1174         const unsigned char *bc = b;
1175
1176         return *ac - *bc;
1177 }
1178
1179 /* labels, contexts are case sensitive  priority numbers are ints */
1180 int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b)
1181 {
1182         const struct ast_context *ac = ah_a;
1183         const struct ast_context *bc = ah_b;
1184         if (!ac || !bc) /* safety valve, but it might prevent a crash you'd rather have happen */
1185                 return 1;
1186         /* assume context names are registered in a string table! */
1187         return strcmp(ac->name, bc->name);
1188 }
1189
1190 static int hashtab_compare_extens(const void *ah_a, const void *ah_b)
1191 {
1192         const struct ast_exten *ac = ah_a;
1193         const struct ast_exten *bc = ah_b;
1194         int x = strcmp(ac->exten, bc->exten);
1195         if (x) { /* if exten names are diff, then return */
1196                 return x;
1197         }
1198
1199         /* but if they are the same, do the cidmatch values match? */
1200         if (ac->matchcid && bc->matchcid) {
1201                 return strcmp(ac->cidmatch,bc->cidmatch);
1202         } else if (!ac->matchcid && !bc->matchcid) {
1203                 return 0; /* if there's no matchcid on either side, then this is a match */
1204         } else {
1205                 return 1; /* if there's matchcid on one but not the other, they are different */
1206         }
1207 }
1208
1209 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b)
1210 {
1211         const struct ast_exten *ac = ah_a;
1212         const struct ast_exten *bc = ah_b;
1213         return ac->priority != bc->priority;
1214 }
1215
1216 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b)
1217 {
1218         const struct ast_exten *ac = ah_a;
1219         const struct ast_exten *bc = ah_b;
1220         return strcmp(S_OR(ac->label, ""), S_OR(bc->label, ""));
1221 }
1222
1223 unsigned int ast_hashtab_hash_contexts(const void *obj)
1224 {
1225         const struct ast_context *ac = obj;
1226         return ast_hashtab_hash_string(ac->name);
1227 }
1228
1229 static unsigned int hashtab_hash_extens(const void *obj)
1230 {
1231         const struct ast_exten *ac = obj;
1232         unsigned int x = ast_hashtab_hash_string(ac->exten);
1233         unsigned int y = 0;
1234         if (ac->matchcid)
1235                 y = ast_hashtab_hash_string(ac->cidmatch);
1236         return x+y;
1237 }
1238
1239 static unsigned int hashtab_hash_priority(const void *obj)
1240 {
1241         const struct ast_exten *ac = obj;
1242         return ast_hashtab_hash_int(ac->priority);
1243 }
1244
1245 static unsigned int hashtab_hash_labels(const void *obj)
1246 {
1247         const struct ast_exten *ac = obj;
1248         return ast_hashtab_hash_string(S_OR(ac->label, ""));
1249 }
1250
1251
1252 AST_RWLOCK_DEFINE_STATIC(globalslock);
1253 static struct varshead globals = AST_LIST_HEAD_NOLOCK_INIT_VALUE;
1254
1255 static int autofallthrough = 1;
1256 static int extenpatternmatchnew = 0;
1257 static char *overrideswitch = NULL;
1258
1259 /*! \brief Subscription for device state change events */
1260 static struct stasis_subscription *device_state_sub;
1261 /*! \brief Subscription for presence state change events */
1262 static struct stasis_subscription *presence_state_sub;
1263
1264 AST_MUTEX_DEFINE_STATIC(maxcalllock);
1265 static int countcalls;
1266 static int totalcalls;
1267
1268 /*!
1269  * \brief Registered functions container.
1270  *
1271  * It is sorted by function name.
1272  */
1273 static AST_RWLIST_HEAD_STATIC(acf_root, ast_custom_function);
1274
1275 /*! \brief Declaration of builtin applications */
1276 static struct pbx_builtin {
1277         char name[AST_MAX_APP];
1278         int (*execute)(struct ast_channel *chan, const char *data);
1279 } builtins[] =
1280 {
1281         /* These applications are built into the PBX core and do not
1282            need separate modules */
1283
1284         { "Answer",         pbx_builtin_answer },
1285         { "BackGround",     pbx_builtin_background },
1286         { "Busy",           pbx_builtin_busy },
1287         { "Congestion",     pbx_builtin_congestion },
1288         { "ExecIfTime",     pbx_builtin_execiftime },
1289         { "Goto",           pbx_builtin_goto },
1290         { "GotoIf",         pbx_builtin_gotoif },
1291         { "GotoIfTime",     pbx_builtin_gotoiftime },
1292         { "ImportVar",      pbx_builtin_importvar },
1293         { "Hangup",         pbx_builtin_hangup },
1294         { "Incomplete",     pbx_builtin_incomplete },
1295         { "NoOp",           pbx_builtin_noop },
1296         { "Proceeding",     pbx_builtin_proceeding },
1297         { "Progress",       pbx_builtin_progress },
1298         { "RaiseException", pbx_builtin_raise_exception },
1299         { "Ringing",        pbx_builtin_ringing },
1300         { "SayAlpha",       pbx_builtin_saycharacters },
1301         { "SayDigits",      pbx_builtin_saydigits },
1302         { "SayNumber",      pbx_builtin_saynumber },
1303         { "SayPhonetic",    pbx_builtin_sayphonetic },
1304         { "Set",            pbx_builtin_setvar },
1305         { "MSet",           pbx_builtin_setvar_multiple },
1306         { "SetAMAFlags",    pbx_builtin_setamaflags },
1307         { "Wait",           pbx_builtin_wait },
1308         { "WaitExten",      pbx_builtin_waitexten }
1309 };
1310
1311 static struct ast_context *contexts;
1312 static struct ast_hashtab *contexts_table = NULL;
1313
1314 /*!
1315  * \brief Lock for the ast_context list
1316  * \note
1317  * This lock MUST be recursive, or a deadlock on reload may result.  See
1318  * https://issues.asterisk.org/view.php?id=17643
1319  */
1320 AST_MUTEX_DEFINE_STATIC(conlock);
1321
1322 /*!
1323  * \brief Lock to hold off restructuring of hints by ast_merge_contexts_and_delete.
1324  */
1325 AST_MUTEX_DEFINE_STATIC(context_merge_lock);
1326
1327 /*!
1328  * \brief Registered applications container.
1329  *
1330  * It is sorted by application name.
1331  */
1332 static AST_RWLIST_HEAD_STATIC(apps, ast_app);
1333
1334 static AST_RWLIST_HEAD_STATIC(switches, ast_switch);
1335
1336 static int stateid = 1;
1337 /*!
1338  * \note When holding this container's lock, do _not_ do
1339  * anything that will cause conlock to be taken, unless you
1340  * _already_ hold it.  The ast_merge_contexts_and_delete function
1341  * will take the locks in conlock/hints order, so any other
1342  * paths that require both locks must also take them in that
1343  * order.
1344  */
1345 static struct ao2_container *hints;
1346
1347 static struct ao2_container *statecbs;
1348
1349 #ifdef CONTEXT_DEBUG
1350
1351 /* these routines are provided for doing run-time checks
1352    on the extension structures, in case you are having
1353    problems, this routine might help you localize where
1354    the problem is occurring. It's kinda like a debug memory
1355    allocator's arena checker... It'll eat up your cpu cycles!
1356    but you'll see, if you call it in the right places,
1357    right where your problems began...
1358 */
1359
1360 /* you can break on the check_contexts_trouble()
1361 routine in your debugger to stop at the moment
1362 there's a problem */
1363 void check_contexts_trouble(void);
1364
1365 void check_contexts_trouble(void)
1366 {
1367         int x = 1;
1368         x = 2;
1369 }
1370
1371 int check_contexts(char *, int);
1372
1373 int check_contexts(char *file, int line )
1374 {
1375         struct ast_hashtab_iter *t1;
1376         struct ast_context *c1, *c2;
1377         int found = 0;
1378         struct ast_exten *e1, *e2, *e3;
1379         struct ast_exten ex;
1380
1381         /* try to find inconsistencies */
1382         /* is every context in the context table in the context list and vice-versa ? */
1383
1384         if (!contexts_table) {
1385                 ast_log(LOG_NOTICE,"Called from: %s:%d: No contexts_table!\n", file, line);
1386                 usleep(500000);
1387         }
1388
1389         t1 = ast_hashtab_start_traversal(contexts_table);
1390         while( (c1 = ast_hashtab_next(t1))) {
1391                 for(c2=contexts;c2;c2=c2->next) {
1392                         if (!strcmp(c1->name, c2->name)) {
1393                                 found = 1;
1394                                 break;
1395                         }
1396                 }
1397                 if (!found) {
1398                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the linked list\n", file, line, c1->name);
1399                         check_contexts_trouble();
1400                 }
1401         }
1402         ast_hashtab_end_traversal(t1);
1403         for(c2=contexts;c2;c2=c2->next) {
1404                 c1 = find_context_locked(c2->name);
1405                 if (!c1) {
1406                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the hashtab\n", file, line, c2->name);
1407                         check_contexts_trouble();
1408                 } else
1409                         ast_unlock_contexts();
1410         }
1411
1412         /* loop thru all contexts, and verify the exten structure compares to the
1413            hashtab structure */
1414         for(c2=contexts;c2;c2=c2->next) {
1415                 c1 = find_context_locked(c2->name);
1416                 if (c1) {
1417                         ast_unlock_contexts();
1418
1419                         /* is every entry in the root list also in the root_table? */
1420                         for(e1 = c1->root; e1; e1=e1->next)
1421                         {
1422                                 char dummy_name[1024];
1423                                 ex.exten = dummy_name;
1424                                 ex.matchcid = e1->matchcid;
1425                                 ex.cidmatch = e1->cidmatch;
1426                                 ast_copy_string(dummy_name, e1->exten, sizeof(dummy_name));
1427                                 e2 = ast_hashtab_lookup(c1->root_table, &ex);
1428                                 if (!e2) {
1429                                         if (e1->matchcid) {
1430                                                 ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context records the exten %s (CID match: %s) but it is not in its root_table\n", file, line, c2->name, dummy_name, e1->cidmatch );
1431                                         } else {
1432                                                 ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context records the exten %s but it is not in its root_table\n", file, line, c2->name, dummy_name );
1433                                         }
1434                                         check_contexts_trouble();
1435                                 }
1436                         }
1437
1438                         /* is every entry in the root_table also in the root list? */
1439                         if (!c2->root_table) {
1440                                 if (c2->root) {
1441                                         ast_log(LOG_NOTICE,"Called from: %s:%d: No c2->root_table for context %s!\n", file, line, c2->name);
1442                                         usleep(500000);
1443                                 }
1444                         } else {
1445                                 t1 = ast_hashtab_start_traversal(c2->root_table);
1446                                 while( (e2 = ast_hashtab_next(t1)) ) {
1447                                         for(e1=c2->root;e1;e1=e1->next) {
1448                                                 if (!strcmp(e1->exten, e2->exten)) {
1449                                                         found = 1;
1450                                                         break;
1451                                                 }
1452                                         }
1453                                         if (!found) {
1454                                                 ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context records the exten %s but it is not in its root_table\n", file, line, c2->name, e2->exten);
1455                                                 check_contexts_trouble();
1456                                         }
1457
1458                                 }
1459                                 ast_hashtab_end_traversal(t1);
1460                         }
1461                 }
1462                 /* is every priority reflected in the peer_table at the head of the list? */
1463
1464                 /* is every entry in the root list also in the root_table? */
1465                 /* are the per-extension peer_tables in the right place? */
1466
1467                 for(e1 = c2->root; e1; e1 = e1->next) {
1468
1469                         for(e2=e1;e2;e2=e2->peer) {
1470                                 ex.priority = e2->priority;
1471                                 if (e2 != e1 && e2->peer_table) {
1472                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority has a peer_table entry, and shouldn't!\n", file, line, c2->name, e1->exten, e2->priority );
1473                                         check_contexts_trouble();
1474                                 }
1475
1476                                 if (e2 != e1 && e2->peer_label_table) {
1477                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority has a peer_label_table entry, and shouldn't!\n", file, line, c2->name, e1->exten, e2->priority );
1478                                         check_contexts_trouble();
1479                                 }
1480
1481                                 if (e2 == e1 && !e2->peer_table){
1482                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority doesn't have a peer_table!\n", file, line, c2->name, e1->exten, e2->priority );
1483                                         check_contexts_trouble();
1484                                 }
1485
1486                                 if (e2 == e1 && !e2->peer_label_table) {
1487                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority doesn't have a peer_label_table!\n", file, line, c2->name, e1->exten, e2->priority );
1488                                         check_contexts_trouble();
1489                                 }
1490
1491
1492                                 e3 = ast_hashtab_lookup(e1->peer_table, &ex);
1493                                 if (!e3) {
1494                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority is not reflected in the peer_table\n", file, line, c2->name, e1->exten, e2->priority );
1495                                         check_contexts_trouble();
1496                                 }
1497                         }
1498
1499                         if (!e1->peer_table){
1500                                 ast_log(LOG_NOTICE,"Called from: %s:%d: No e1->peer_table!\n", file, line);
1501                                 usleep(500000);
1502                         }
1503
1504                         /* is every entry in the peer_table also in the peer list? */
1505                         t1 = ast_hashtab_start_traversal(e1->peer_table);
1506                         while( (e2 = ast_hashtab_next(t1)) ) {
1507                                 for(e3=e1;e3;e3=e3->peer) {
1508                                         if (e3->priority == e2->priority) {
1509                                                 found = 1;
1510                                                 break;
1511                                         }
1512                                 }
1513                                 if (!found) {
1514                                         ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority is not reflected in the peer list\n", file, line, c2->name, e1->exten, e2->priority );
1515                                         check_contexts_trouble();
1516                                 }
1517                         }
1518                         ast_hashtab_end_traversal(t1);
1519                 }
1520         }
1521         return 0;
1522 }
1523 #endif
1524
1525 /*
1526    \note This function is special. It saves the stack so that no matter
1527    how many times it is called, it returns to the same place */
1528 int pbx_exec(struct ast_channel *c,     /*!< Channel */
1529              struct ast_app *app,       /*!< Application */
1530              const char *data)          /*!< Data for execution */
1531 {
1532         int res;
1533         struct ast_module_user *u = NULL;
1534         const char *saved_c_appl;
1535         const char *saved_c_data;
1536
1537         /* save channel values */
1538         saved_c_appl= ast_channel_appl(c);
1539         saved_c_data= ast_channel_data(c);
1540
1541         ast_channel_appl_set(c, app->name);
1542         ast_channel_data_set(c, data);
1543         ast_channel_publish_snapshot(c);
1544
1545         if (app->module)
1546                 u = __ast_module_user_add(app->module, c);
1547         res = app->execute(c, S_OR(data, ""));
1548         if (app->module && u)
1549                 __ast_module_user_remove(app->module, u);
1550         /* restore channel values */
1551         ast_channel_appl_set(c, saved_c_appl);
1552         ast_channel_data_set(c, saved_c_data);
1553         return res;
1554 }
1555
1556
1557 /*! Go no deeper than this through includes (not counting loops) */
1558 #define AST_PBX_MAX_STACK       128
1559
1560 static struct ast_app *pbx_findapp_nolock(const char *name)
1561 {
1562         struct ast_app *cur;
1563         int cmp;
1564
1565         AST_RWLIST_TRAVERSE(&apps, cur, list) {
1566                 cmp = strcasecmp(name, cur->name);
1567                 if (cmp > 0) {
1568                         continue;
1569                 }
1570                 if (!cmp) {
1571                         /* Found it. */
1572                         break;
1573                 }
1574                 /* Not in container. */
1575                 cur = NULL;
1576                 break;
1577         }
1578
1579         return cur;
1580 }
1581
1582 struct ast_app *pbx_findapp(const char *app)
1583 {
1584         struct ast_app *ret;
1585
1586         AST_RWLIST_RDLOCK(&apps);
1587         ret = pbx_findapp_nolock(app);
1588         AST_RWLIST_UNLOCK(&apps);
1589
1590         return ret;
1591 }
1592
1593 static struct ast_switch *pbx_findswitch(const char *sw)
1594 {
1595         struct ast_switch *asw;
1596
1597         AST_RWLIST_RDLOCK(&switches);
1598         AST_RWLIST_TRAVERSE(&switches, asw, list) {
1599                 if (!strcasecmp(asw->name, sw))
1600                         break;
1601         }
1602         AST_RWLIST_UNLOCK(&switches);
1603
1604         return asw;
1605 }
1606
1607 static inline int include_valid(struct ast_include *i)
1608 {
1609         if (!i->hastime)
1610                 return 1;
1611
1612         return ast_check_timing(&(i->timing));
1613 }
1614
1615 static void pbx_destroy(struct ast_pbx *p)
1616 {
1617         ast_free(p);
1618 }
1619
1620 /* form a tree that fully describes all the patterns in a context's extensions
1621  * in this tree, a "node" represents an individual character or character set
1622  * meant to match the corresponding character in a dial string. The tree
1623  * consists of a series of match_char structs linked in a chain
1624  * via the alt_char pointers. More than one pattern can share the same parts of the
1625  * tree as other extensions with the same pattern to that point.
1626  * My first attempt to duplicate the finding of the 'best' pattern was flawed in that
1627  * I misunderstood the general algorithm. I thought that the 'best' pattern
1628  * was the one with lowest total score. This was not true. Thus, if you have
1629  * patterns "1XXXXX" and "X11111", you would be tempted to say that "X11111" is
1630  * the "best" match because it has fewer X's, and is therefore more specific,
1631  * but this is not how the old algorithm works. It sorts matching patterns
1632  * in a similar collating sequence as sorting alphabetic strings, from left to
1633  * right. Thus, "1XXXXX" comes before "X11111", and would be the "better" match,
1634  * because "1" is more specific than "X".
1635  * So, to accomodate this philosophy, I sort the tree branches along the alt_char
1636  * line so they are lowest to highest in specificity numbers. This way, as soon
1637  * as we encounter our first complete match, we automatically have the "best"
1638  * match and can stop the traversal immediately. Same for CANMATCH/MATCHMORE.
1639  * If anyone would like to resurrect the "wrong" pattern trie searching algorithm,
1640  * they are welcome to revert pbx to before 1 Apr 2008.
1641  * As an example, consider these 4 extensions:
1642  * (a) NXXNXXXXXX
1643  * (b) 307754XXXX
1644  * (c) fax
1645  * (d) NXXXXXXXXX
1646  *
1647  * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
1648  * most numbers. For all numbers beginning with 307754, (b) should always win.
1649  *
1650  * These pattern should form a (sorted) tree that looks like this:
1651  *   { "3" }  --next-->  { "0" }  --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
1652  *      |
1653  *      |alt
1654  *      |
1655  *   { "f" }  --next-->  { "a" }  --next--> { "x"  exten_match: (c) }
1656  *   { "N" }  --next-->  { "X" }  --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
1657  *      |                                                        |
1658  *      |                                                        |alt
1659  *      |alt                                                     |
1660  *      |                                                     { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
1661  *      |
1662  *     NULL
1663  *
1664  *   In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
1665  *   fewer CPU cycles than a call to strchr("23456789",*z), where *z is the char to match...
1666  *
1667  *   traversal is pretty simple: one routine merely traverses the alt list, and for each matching char in the pattern,  it calls itself
1668  *   on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
1669  *   We pass a pointer to a scoreboard down through, also.
1670  *   The scoreboard isn't as necessary to the revised algorithm, but I kept it as a handy way to return the matched extension.
1671  *   The first complete match ends the traversal, which should make this version of the pattern matcher faster
1672  *   the previous. The same goes for "CANMATCH" or "MATCHMORE"; the first such match ends the traversal. In both
1673  *   these cases, the reason we can stop immediately, is because the first pattern match found will be the "best"
1674  *   according to the sort criteria.
1675  *   Hope the limit on stack depth won't be a problem... this routine should
1676  *   be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
1677  *
1678  *   In the above example, with the number "3077549999" as the pattern, the traversor could match extensions a, b and d.  All are
1679  *   of length 10; they have total specificities of  24580, 10246, and 25090, respectively, not that this matters
1680  *   at all. (b) wins purely because the first character "3" is much more specific (lower specificity) than "N". I have
1681  *   left the specificity totals in the code as an artifact; at some point, I will strip it out.
1682  *
1683  *   Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown,
1684  *   because it's a function of how many extensions are stored in a context. With thousands of extensions, the speedup
1685  *   can be very noticeable. The new matching algorithm can run several hundreds of times faster, if not a thousand or
1686  *   more times faster in extreme cases.
1687  *
1688  *   MatchCID patterns are also supported, and stored in the tree just as the extension pattern is. Thus, you
1689  *   can have patterns in your CID field as well.
1690  *
1691  * */
1692
1693
1694 static void update_scoreboard(struct scoreboard *board, int length, int spec, struct ast_exten *exten, char last, const char *callerid, int deleted, struct match_char *node)
1695 {
1696         /* if this extension is marked as deleted, then skip this -- if it never shows
1697            on the scoreboard, it will never be found, nor will halt the traversal. */
1698         if (deleted)
1699                 return;
1700         board->total_specificity = spec;
1701         board->total_length = length;
1702         board->exten = exten;
1703         board->last_char = last;
1704         board->node = node;
1705 #ifdef NEED_DEBUG_HERE
1706         ast_log(LOG_NOTICE,"Scoreboarding (LONGER) %s, len=%d, score=%d\n", exten->exten, length, spec);
1707 #endif
1708 }
1709
1710 #ifdef NEED_DEBUG
1711 static void log_match_char_tree(struct match_char *node, char *prefix)
1712 {
1713         char extenstr[40];
1714         struct ast_str *my_prefix = ast_str_alloca(1024);
1715
1716         extenstr[0] = '\0';
1717
1718         if (node && node->exten)
1719                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1720
1721         if (strlen(node->x) > 1) {
1722                 ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1723                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1724                         node->exten ? node->exten->exten : "", extenstr);
1725         } else {
1726                 ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1727                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1728                         node->exten ? node->exten->exten : "", extenstr);
1729         }
1730
1731         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1732
1733         if (node->next_char)
1734                 log_match_char_tree(node->next_char, ast_str_buffer(my_prefix));
1735
1736         if (node->alt_char)
1737                 log_match_char_tree(node->alt_char, prefix);
1738 }
1739 #endif
1740
1741 static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
1742 {
1743         char extenstr[40];
1744         struct ast_str *my_prefix = ast_str_alloca(1024);
1745
1746         extenstr[0] = '\0';
1747
1748         if (node->exten) {
1749                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1750         }
1751
1752         if (strlen(node->x) > 1) {
1753                 ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1754                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1755                         node->exten ? node->exten->exten : "", extenstr);
1756         } else {
1757                 ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1758                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1759                         node->exten ? node->exten->exten : "", extenstr);
1760         }
1761
1762         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1763
1764         if (node->next_char)
1765                 cli_match_char_tree(node->next_char, ast_str_buffer(my_prefix), fd);
1766
1767         if (node->alt_char)
1768                 cli_match_char_tree(node->alt_char, prefix, fd);
1769 }
1770
1771 static struct ast_exten *get_canmatch_exten(struct match_char *node)
1772 {
1773         /* find the exten at the end of the rope */
1774         struct match_char *node2 = node;
1775
1776         for (node2 = node; node2; node2 = node2->next_char) {
1777                 if (node2->exten) {
1778 #ifdef NEED_DEBUG_HERE
1779                         ast_log(LOG_NOTICE,"CanMatch_exten returns exten %s(%p)\n", node2->exten->exten, node2->exten);
1780 #endif
1781                         return node2->exten;
1782                 }
1783         }
1784 #ifdef NEED_DEBUG_HERE
1785         ast_log(LOG_NOTICE,"CanMatch_exten returns NULL, match_char=%s\n", node->x);
1786 #endif
1787         return 0;
1788 }
1789
1790 static struct ast_exten *trie_find_next_match(struct match_char *node)
1791 {
1792         struct match_char *m3;
1793         struct match_char *m4;
1794         struct ast_exten *e3;
1795
1796         if (node && node->x[0] == '.' && !node->x[1]) { /* dot and ! will ALWAYS be next match in a matchmore */
1797                 return node->exten;
1798         }
1799
1800         if (node && node->x[0] == '!' && !node->x[1]) {
1801                 return node->exten;
1802         }
1803
1804         if (!node || !node->next_char) {
1805                 return NULL;
1806         }
1807
1808         m3 = node->next_char;
1809
1810         if (m3->exten) {
1811                 return m3->exten;
1812         }
1813         for (m4 = m3->alt_char; m4; m4 = m4->alt_char) {
1814                 if (m4->exten) {
1815                         return m4->exten;
1816                 }
1817         }
1818         for (m4 = m3; m4; m4 = m4->alt_char) {
1819                 e3 = trie_find_next_match(m3);
1820                 if (e3) {
1821                         return e3;
1822                 }
1823         }
1824
1825         return NULL;
1826 }
1827
1828 #ifdef DEBUG_THIS
1829 static char *action2str(enum ext_match_t action)
1830 {
1831         switch (action) {
1832         case E_MATCH:
1833                 return "MATCH";
1834         case E_CANMATCH:
1835                 return "CANMATCH";
1836         case E_MATCHMORE:
1837                 return "MATCHMORE";
1838         case E_FINDLABEL:
1839                 return "FINDLABEL";
1840         case E_SPAWN:
1841                 return "SPAWN";
1842         default:
1843                 return "?ACTION?";
1844         }
1845 }
1846
1847 #endif
1848
1849 static void new_find_extension(const char *str, struct scoreboard *score, struct match_char *tree, int length, int spec, const char *callerid, const char *label, enum ext_match_t action)
1850 {
1851         struct match_char *p; /* note minimal stack storage requirements */
1852         struct ast_exten pattern = { .label = label };
1853 #ifdef DEBUG_THIS
1854         if (tree)
1855                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
1856         else
1857                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
1858 #endif
1859         for (p = tree; p; p = p->alt_char) {
1860                 if (p->is_pattern) {
1861                         if (p->x[0] == 'N') {
1862                                 if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
1863 #define NEW_MATCHER_CHK_MATCH          \
1864                                         if (p->exten && !(*(str + 1))) { /* if a shorter pattern matches along the way, might as well report it */             \
1865                                                 if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */   \
1866                                                         update_scoreboard(score, length + 1, spec + p->specificity, p->exten, 0, callerid, p->deleted, p);                 \
1867                                                         if (!p->deleted) {                                                                                           \
1868                                                                 if (action == E_FINDLABEL) {                                                                             \
1869                                                                         if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) {                                  \
1870                                                                                 ast_debug(4, "Found label in preferred extension\n");                                            \
1871                                                                                 return;                                                                                          \
1872                                                                         }                                                                                                    \
1873                                                                 } else {                                                                                                 \
1874                                                                         ast_debug(4, "returning an exact match-- first found-- %s\n", p->exten->exten);                       \
1875                                                                         return; /* the first match, by definition, will be the best, because of the sorted tree */           \
1876                                                                 }                                                                                                        \
1877                                                         }                                                                                                            \
1878                                                 }                                                                                                                \
1879                                         }
1880
1881 #define NEW_MATCHER_RECURSE                \
1882                                         if (p->next_char && (*(str + 1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)                 \
1883                                                        || p->next_char->x[0] == '!')) {                                          \
1884                                                 if (*(str + 1) || p->next_char->x[0] == '!') {                                                         \
1885                                                         new_find_extension(str + 1, score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
1886                                                         if (score->exten)  {                                                                             \
1887                                                         ast_debug(4 ,"returning an exact match-- %s\n", score->exten->exten);                         \
1888                                                                 return; /* the first match is all we need */                                                 \
1889                                                         }                                                                                                                                                \
1890                                                 } else {                                                                                             \
1891                                                         new_find_extension("/", score, p->next_char, length + 1, spec + p->specificity, callerid, label, action);        \
1892                                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {      \
1893                                                         ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->exten :     \
1894                                                "NULL");                                                                        \
1895                                                                 return; /* the first match is all we need */                                                 \
1896                                                         }                                                                                                                                                \
1897                                                 }                                                                                                    \
1898                                         } else if ((p->next_char || action == E_CANMATCH) && !*(str + 1)) {                                                                  \
1899                                                 score->canmatch = 1;                                                                                 \
1900                                                 score->canmatch_exten = get_canmatch_exten(p);                                                       \
1901                                                 if (action == E_CANMATCH || action == E_MATCHMORE) {                                                 \
1902                                                 ast_debug(4, "returning a canmatch/matchmore--- str=%s\n", str);                                  \
1903                                                         return;                                                                                          \
1904                                                 }                                                                                                                                                    \
1905                                         }
1906
1907                                         NEW_MATCHER_CHK_MATCH;
1908                                         NEW_MATCHER_RECURSE;
1909                                 }
1910                         } else if (p->x[0] == 'Z') {
1911                                 if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
1912                                         NEW_MATCHER_CHK_MATCH;
1913                                         NEW_MATCHER_RECURSE;
1914                                 }
1915                         } else if (p->x[0] == 'X') {
1916                                 if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1917                                         NEW_MATCHER_CHK_MATCH;
1918                                         NEW_MATCHER_RECURSE;
1919                                 }
1920                         } else if (p->x[0] == '.' && p->x[1] == 0) {
1921                                 /* how many chars will the . match against? */
1922                                 int i = 0;
1923                                 const char *str2 = str;
1924                                 while (*str2 && *str2 != '/') {
1925                                         str2++;
1926                                         i++;
1927                                 }
1928                                 if (p->exten && *str2 != '/') {
1929                                         update_scoreboard(score, length + i, spec + (i * p->specificity), p->exten, '.', callerid, p->deleted, p);
1930                                         if (score->exten) {
1931                                                 ast_debug(4,"return because scoreboard has a match with '/'--- %s\n", score->exten->exten);
1932                                                 return; /* the first match is all we need */
1933                                         }
1934                                 }
1935                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1936                                         new_find_extension("/", score, p->next_char, length + i, spec+(p->specificity*i), callerid, label, action);
1937                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1938                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set--- %s\n", score->exten ? score->exten->exten : "NULL");
1939                                                 return; /* the first match is all we need */
1940                                         }
1941                                 }
1942                         } else if (p->x[0] == '!' && p->x[1] == 0) {
1943                                 /* how many chars will the . match against? */
1944                                 int i = 1;
1945                                 const char *str2 = str;
1946                                 while (*str2 && *str2 != '/') {
1947                                         str2++;
1948                                         i++;
1949                                 }
1950                                 if (p->exten && *str2 != '/') {
1951                                         update_scoreboard(score, length + 1, spec + (p->specificity * i), p->exten, '!', callerid, p->deleted, p);
1952                                         if (score->exten) {
1953                                                 ast_debug(4, "return because scoreboard has a '!' match--- %s\n", score->exten->exten);
1954                                                 return; /* the first match is all we need */
1955                                         }
1956                                 }
1957                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1958                                         new_find_extension("/", score, p->next_char, length + i, spec + (p->specificity * i), callerid, label, action);
1959                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1960                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n", score->exten ? score->exten->exten : "NULL");
1961                                                 return; /* the first match is all we need */
1962                                         }
1963                                 }
1964                         } else if (p->x[0] == '/' && p->x[1] == 0) {
1965                                 /* the pattern in the tree includes the cid match! */
1966                                 if (p->next_char && callerid && *callerid) {
1967                                         new_find_extension(callerid, score, p->next_char, length + 1, spec, callerid, label, action);
1968                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1969                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n", score->exten ? score->exten->exten : "NULL");
1970                                                 return; /* the first match is all we need */
1971                                         }
1972                                 }
1973                         } else if (strchr(p->x, *str)) {
1974                                 ast_debug(4, "Nothing strange about this match\n");
1975                                 NEW_MATCHER_CHK_MATCH;
1976                                 NEW_MATCHER_RECURSE;
1977                         }
1978                 } else if (strchr(p->x, *str)) {
1979                         ast_debug(4, "Nothing strange about this match\n");
1980                         NEW_MATCHER_CHK_MATCH;
1981                         NEW_MATCHER_RECURSE;
1982                 }
1983         }
1984         ast_debug(4, "return at end of func\n");
1985 }
1986
1987 /* the algorithm for forming the extension pattern tree is also a bit simple; you
1988  * traverse all the extensions in a context, and for each char of the extension,
1989  * you see if it exists in the tree; if it doesn't, you add it at the appropriate
1990  * spot. What more can I say? At the end of each exten, you cap it off by adding the
1991  * address of the extension involved. Duplicate patterns will be complained about.
1992  *
1993  * Ideally, this would be done for each context after it is created and fully
1994  * filled. It could be done as a finishing step after extensions.conf or .ael is
1995  * loaded, or it could be done when the first search is encountered. It should only
1996  * have to be done once, until the next unload or reload.
1997  *
1998  * I guess forming this pattern tree would be analogous to compiling a regex. Except
1999  * that a regex only handles 1 pattern, really. This trie holds any number
2000  * of patterns. Well, really, it **could** be considered a single pattern,
2001  * where the "|" (or) operator is allowed, I guess, in a way, sort of...
2002  */
2003
2004 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern)
2005 {
2006         struct match_char *t;
2007
2008         if (!current) {
2009                 return 0;
2010         }
2011
2012         for (t = current; t; t = t->alt_char) {
2013                 if (is_pattern == t->is_pattern && !strcmp(pat, t->x)) {/* uh, we may want to sort exploded [] contents to make matching easy */
2014                         return t;
2015                 }
2016         }
2017
2018         return 0;
2019 }
2020
2021 /* The first arg is the location of the tree ptr, or the
2022    address of the next_char ptr in the node, so we can mess
2023    with it, if we need to insert at the beginning of the list */
2024
2025 static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, struct match_char *node)
2026 {
2027         struct match_char *curr, *lcurr;
2028
2029         /* insert node into the tree at "current", so the alt_char list from current is
2030            sorted in increasing value as you go to the leaves */
2031         if (!(*parent_ptr)) {
2032                 *parent_ptr = node;
2033                 return;
2034         }
2035
2036         if ((*parent_ptr)->specificity > node->specificity) {
2037                 /* insert at head */
2038                 node->alt_char = (*parent_ptr);
2039                 *parent_ptr = node;
2040                 return;
2041         }
2042
2043         lcurr = *parent_ptr;
2044         for (curr = (*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
2045                 if (curr->specificity > node->specificity) {
2046                         node->alt_char = curr;
2047                         lcurr->alt_char = node;
2048                         break;
2049                 }
2050                 lcurr = curr;
2051         }
2052
2053         if (!curr) {
2054                 lcurr->alt_char = node;
2055         }
2056
2057 }
2058
2059 struct pattern_node {
2060         /*! Pattern node specificity */
2061         int specif;
2062         /*! Pattern node match characters. */
2063         char buf[256];
2064 };
2065
2066 static struct match_char *add_pattern_node(struct ast_context *con, struct match_char *current, const struct pattern_node *pattern, int is_pattern, int already, struct match_char **nextcharptr)
2067 {
2068         struct match_char *m;
2069
2070         if (!(m = ast_calloc(1, sizeof(*m) + strlen(pattern->buf)))) {
2071                 return NULL;
2072         }
2073
2074         /* strcpy is safe here since we know its size and have allocated
2075          * just enough space for when we allocated m
2076          */
2077         strcpy(m->x, pattern->buf);
2078
2079         /* the specificity scores are the same as used in the old
2080            pattern matcher. */
2081         m->is_pattern = is_pattern;
2082         if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'N') {
2083                 m->specificity = 0x0832;
2084         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'Z') {
2085                 m->specificity = 0x0931;
2086         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'X') {
2087                 m->specificity = 0x0a30;
2088         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '.') {
2089                 m->specificity = 0x18000;
2090         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '!') {
2091                 m->specificity = 0x28000;
2092         } else {
2093                 m->specificity = pattern->specif;
2094         }
2095
2096         if (!con->pattern_tree) {
2097                 insert_in_next_chars_alt_char_list(&con->pattern_tree, m);
2098         } else {
2099                 if (already) { /* switch to the new regime (traversing vs appending)*/
2100                         insert_in_next_chars_alt_char_list(nextcharptr, m);
2101                 } else {
2102                         insert_in_next_chars_alt_char_list(&current->next_char, m);
2103                 }
2104         }
2105
2106         return m;
2107 }
2108
2109 /*!
2110  * \internal
2111  * \brief Extract the next exten pattern node.
2112  *
2113  * \param node Pattern node to fill.
2114  * \param src Next source character to read.
2115  * \param pattern TRUE if the exten is a pattern.
2116  * \param extenbuf Original exten buffer to use in diagnostic messages.
2117  *
2118  * \retval Ptr to next extenbuf pos to read.
2119  */
2120 static const char *get_pattern_node(struct pattern_node *node, const char *src, int pattern, const char *extenbuf)
2121 {
2122 #define INC_DST_OVERFLOW_CHECK                                                  \
2123         do {                                                                                            \
2124                 if (dst - node->buf < sizeof(node->buf) - 1) {  \
2125                         ++dst;                                                                          \
2126                 } else {                                                                                \
2127                         overflow = 1;                                                           \
2128                 }                                                                                               \
2129         } while (0)
2130
2131         node->specif = 0;
2132         node->buf[0] = '\0';
2133         while (*src) {
2134                 if (*src == '[' && pattern) {
2135                         char *dst = node->buf;
2136                         const char *src_next;
2137                         int length;
2138                         int overflow = 0;
2139
2140                         /* get past the '[' */
2141                         ++src;
2142                         for (;;) {
2143                                 if (*src == '\\') {
2144                                         /* Escaped character. */
2145                                         ++src;
2146                                         if (*src == '[' || *src == '\\' || *src == '-' || *src == ']') {
2147                                                 *dst = *src++;
2148                                                 INC_DST_OVERFLOW_CHECK;
2149                                         }
2150                                 } else if (*src == '-') {
2151                                         unsigned char first;
2152                                         unsigned char last;
2153
2154                                         src_next = src;
2155                                         first = *(src_next - 1);
2156                                         last = *++src_next;
2157
2158                                         if (last == '\\') {
2159                                                 /* Escaped character. */
2160                                                 last = *++src_next;
2161                                         }
2162
2163                                         /* Possible char range. */
2164                                         if (node->buf[0] && last) {
2165                                                 /* Expand the char range. */
2166                                                 while (++first <= last) {
2167                                                         *dst = first;
2168                                                         INC_DST_OVERFLOW_CHECK;
2169                                                 }
2170                                                 src = src_next + 1;
2171                                         } else {
2172                                                 /*
2173                                                  * There was no left or right char for the range.
2174                                                  * It is just a '-'.
2175                                                  */
2176                                                 *dst = *src++;
2177                                                 INC_DST_OVERFLOW_CHECK;
2178                                         }
2179                                 } else if (*src == '\0') {
2180                                         ast_log(LOG_WARNING,
2181                                                 "A matching ']' was not found for '[' in exten pattern '%s'\n",
2182                                                 extenbuf);
2183                                         break;
2184                                 } else if (*src == ']') {
2185                                         ++src;
2186                                         break;
2187                                 } else {
2188                                         *dst = *src++;
2189                                         INC_DST_OVERFLOW_CHECK;
2190                                 }
2191                         }
2192                         /* null terminate the exploded range */
2193                         *dst = '\0';
2194
2195                         if (overflow) {
2196                                 ast_log(LOG_ERROR,
2197                                         "Expanded character set too large to deal with in exten pattern '%s'. Ignoring character set.\n",
2198                                         extenbuf);
2199                                 node->buf[0] = '\0';
2200                                 continue;
2201                         }
2202
2203                         /* Sort the characters in character set. */
2204                         length = strlen(node->buf);
2205                         if (!length) {
2206                                 ast_log(LOG_WARNING, "Empty character set in exten pattern '%s'. Ignoring.\n",
2207                                         extenbuf);
2208                                 node->buf[0] = '\0';
2209                                 continue;
2210                         }
2211                         qsort(node->buf, length, 1, compare_char);
2212
2213                         /* Remove duplicate characters from character set. */
2214                         dst = node->buf;
2215                         src_next = node->buf;
2216                         while (*src_next++) {
2217                                 if (*dst != *src_next) {
2218                                         *++dst = *src_next;
2219                                 }
2220                         }
2221
2222                         length = strlen(node->buf);
2223                         length <<= 8;
2224                         node->specif = length | (unsigned char) node->buf[0];
2225                         break;
2226                 } else if (*src == '-') {
2227                         /* Skip dashes in all extensions. */
2228                         ++src;
2229                 } else {
2230                         if (*src == '\\') {
2231                                 /*
2232                                  * XXX The escape character here does not remove any special
2233                                  * meaning to characters except the '[', '\\', and '-'
2234                                  * characters since they are special only in this function.
2235                                  */
2236                                 node->buf[0] = *++src;
2237                                 if (!node->buf[0]) {
2238                                         break;
2239                                 }
2240                         } else {
2241                                 node->buf[0] = *src;
2242                                 if (pattern) {
2243                                         /* make sure n,x,z patterns are canonicalized to N,X,Z */
2244                                         if (node->buf[0] == 'n') {
2245                                                 node->buf[0] = 'N';
2246                                         } else if (node->buf[0] == 'x') {
2247                                                 node->buf[0] = 'X';
2248                                         } else if (node->buf[0] == 'z') {
2249                                                 node->buf[0] = 'Z';
2250                                         }
2251                                 }
2252                         }
2253                         node->buf[1] = '\0';
2254                         node->specif = 1;
2255                         ++src;
2256                         break;
2257                 }
2258         }
2259         return src;
2260
2261 #undef INC_DST_OVERFLOW_CHECK
2262 }
2263
2264 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
2265 {
2266         struct match_char *m1 = NULL;
2267         struct match_char *m2 = NULL;
2268         struct match_char **m0;
2269         const char *pos;
2270         int already;
2271         int pattern = 0;
2272         int idx_cur;
2273         int idx_next;
2274         char extenbuf[512];
2275         struct pattern_node pat_node[2];
2276
2277         if (e1->matchcid) {
2278                 if (sizeof(extenbuf) < strlen(e1->exten) + strlen(e1->cidmatch) + 2) {
2279                         ast_log(LOG_ERROR,
2280                                 "The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n",
2281                                 e1->exten, e1->cidmatch);
2282                         return NULL;
2283                 }
2284                 sprintf(extenbuf, "%s/%s", e1->exten, e1->cidmatch);/* Safe.  We just checked. */
2285         } else {
2286                 ast_copy_string(extenbuf, e1->exten, sizeof(extenbuf));
2287         }
2288
2289 #ifdef NEED_DEBUG
2290         ast_debug(1, "Adding exten %s to tree\n", extenbuf);
2291 #endif
2292         m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
2293         m0 = &con->pattern_tree;
2294         already = 1;
2295
2296         pos = extenbuf;
2297         if (*pos == '_') {
2298                 pattern = 1;
2299                 ++pos;
2300         }
2301         idx_cur = 0;
2302         pos = get_pattern_node(&pat_node[idx_cur], pos, pattern, extenbuf);
2303         for (; pat_node[idx_cur].buf[0]; idx_cur = idx_next) {
2304                 idx_next = (idx_cur + 1) % ARRAY_LEN(pat_node);
2305                 pos = get_pattern_node(&pat_node[idx_next], pos, pattern, extenbuf);
2306
2307                 /* See about adding node to tree. */
2308                 m2 = NULL;
2309                 if (already && (m2 = already_in_tree(m1, pat_node[idx_cur].buf, pattern))
2310                         && m2->next_char) {
2311                         if (!pat_node[idx_next].buf[0]) {
2312                                 /*
2313                                  * This is the end of the pattern, but not the end of the tree.
2314                                  * Mark this node with the exten... a shorter pattern might win
2315                                  * if the longer one doesn't match.
2316                                  */
2317                                 if (findonly) {
2318                                         return m2;
2319                                 }
2320                                 if (m2->exten) {
2321                                         ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
2322                                                 m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten);
2323                                 }
2324                                 m2->exten = e1;
2325                                 m2->deleted = 0;
2326                         }
2327                         m1 = m2->next_char; /* m1 points to the node to compare against */
2328                         m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
2329                 } else { /* not already OR not m2 OR nor m2->next_char */
2330                         if (m2) {
2331                                 if (findonly) {
2332                                         return m2;
2333                                 }
2334                                 m1 = m2; /* while m0 stays the same */
2335                         } else {
2336                                 if (findonly) {
2337                                         return m1;
2338                                 }
2339                                 m1 = add_pattern_node(con, m1, &pat_node[idx_cur], pattern, already, m0);
2340                                 if (!m1) { /* m1 is the node just added */
2341                                         return NULL;
2342                                 }
2343                                 m0 = &m1->next_char;
2344                         }
2345                         if (!pat_node[idx_next].buf[0]) {
2346                                 if (m2 && m2->exten) {
2347                                         ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
2348                                                 m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten);
2349                                 }
2350                                 m1->deleted = 0;
2351                                 m1->exten = e1;
2352                         }
2353
2354                         /* The 'already' variable is a mini-optimization designed to make it so that we
2355                          * don't have to call already_in_tree when we know it will return false.
2356                          */
2357                         already = 0;
2358                 }
2359         }
2360         return m1;
2361 }
2362
2363 static void create_match_char_tree(struct ast_context *con)
2364 {
2365         struct ast_hashtab_iter *t1;
2366         struct ast_exten *e1;
2367 #ifdef NEED_DEBUG
2368         int biggest_bucket, resizes, numobjs, numbucks;
2369
2370         ast_debug(1, "Creating Extension Trie for context %s(%p)\n", con->name, con);
2371         ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
2372         ast_debug(1, "This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
2373                         numobjs, numbucks, biggest_bucket, resizes);
2374 #endif
2375         t1 = ast_hashtab_start_traversal(con->root_table);
2376         while ((e1 = ast_hashtab_next(t1))) {
2377                 if (e1->exten) {
2378                         add_exten_to_pattern_tree(con, e1, 0);
2379                 } else {
2380                         ast_log(LOG_ERROR, "Attempt to create extension with no extension name.\n");
2381                 }
2382         }
2383         ast_hashtab_end_traversal(t1);
2384 }
2385
2386 static void destroy_pattern_tree(struct match_char *pattern_tree) /* pattern tree is a simple binary tree, sort of, so the proper way to destroy it is... recursively! */
2387 {
2388         /* destroy all the alternates */
2389         if (pattern_tree->alt_char) {
2390                 destroy_pattern_tree(pattern_tree->alt_char);
2391                 pattern_tree->alt_char = 0;
2392         }
2393         /* destroy all the nexts */
2394         if (pattern_tree->next_char) {
2395                 destroy_pattern_tree(pattern_tree->next_char);
2396                 pattern_tree->next_char = 0;
2397         }
2398         pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
2399         ast_free(pattern_tree);
2400 }
2401
2402 /*!
2403  * \internal
2404  * \brief Get the length of the exten string.
2405  *
2406  * \param str Exten to get length.
2407  *
2408  * \retval strlen of exten.
2409  */
2410 static int ext_cmp_exten_strlen(const char *str)
2411 {
2412         int len;
2413
2414         len = 0;
2415         for (;;) {
2416                 /* Ignore '-' chars as eye candy fluff. */
2417                 while (*str == '-') {
2418                         ++str;
2419                 }
2420                 if (!*str) {
2421                         break;
2422                 }
2423                 ++str;
2424                 ++len;
2425         }
2426         return len;
2427 }
2428
2429 /*!
2430  * \internal
2431  * \brief Partial comparison of non-pattern extens.
2432  *
2433  * \param left Exten to compare.
2434  * \param right Exten to compare.  Also matches if this string ends first.
2435  *
2436  * \retval <0 if left < right
2437  * \retval =0 if left == right
2438  * \retval >0 if left > right
2439  */
2440 static int ext_cmp_exten_partial(const char *left, const char *right)
2441 {
2442         int cmp;
2443
2444         for (;;) {
2445                 /* Ignore '-' chars as eye candy fluff. */
2446                 while (*left == '-') {
2447                         ++left;
2448                 }
2449                 while (*right == '-') {
2450                         ++right;
2451                 }
2452
2453                 if (!*right) {
2454                         /*
2455                          * Right ended first for partial match or both ended at the same
2456                          * time for a match.
2457                          */
2458                         cmp = 0;
2459                         break;
2460                 }
2461
2462                 cmp = *left - *right;
2463                 if (cmp) {
2464                         break;
2465                 }
2466                 ++left;
2467                 ++right;
2468         }
2469         return cmp;
2470 }
2471
2472 /*!
2473  * \internal
2474  * \brief Comparison of non-pattern extens.
2475  *
2476  * \param left Exten to compare.
2477  * \param right Exten to compare.
2478  *
2479  * \retval <0 if left < right
2480  * \retval =0 if left == right
2481  * \retval >0 if left > right
2482  */
2483 static int ext_cmp_exten(const char *left, const char *right)
2484 {
2485         int cmp;
2486
2487         for (;;) {
2488                 /* Ignore '-' chars as eye candy fluff. */
2489                 while (*left == '-') {
2490                         ++left;
2491                 }
2492                 while (*right == '-') {
2493                         ++right;
2494                 }
2495
2496                 cmp = *left - *right;
2497                 if (cmp) {
2498                         break;
2499                 }
2500                 if (!*left) {
2501                         /*
2502                          * Get here only if both strings ended at the same time.  cmp
2503                          * would be non-zero if only one string ended.
2504                          */
2505                         break;
2506                 }
2507                 ++left;
2508                 ++right;
2509         }
2510         return cmp;
2511 }
2512
2513 /*
2514  * Special characters used in patterns:
2515  *      '_'     underscore is the leading character of a pattern.
2516  *              In other position it is treated as a regular char.
2517  *      '-' The '-' is a separator and ignored.  Why?  So patterns like NXX-XXX-XXXX work.
2518  *      .       one or more of any character. Only allowed at the end of
2519  *              a pattern.
2520  *      !       zero or more of anything. Also impacts the result of CANMATCH
2521  *              and MATCHMORE. Only allowed at the end of a pattern.
2522  *              In the core routine, ! causes a match with a return code of 2.
2523  *              In turn, depending on the search mode: (XXX check if it is implemented)
2524  *              - E_MATCH retuns 1 (does match)
2525  *              - E_MATCHMORE returns 0 (no match)
2526  *              - E_CANMATCH returns 1 (does match)
2527  *
2528  *      /       should not appear as it is considered the separator of the CID info.
2529  *              XXX at the moment we may stop on this char.
2530  *
2531  *      X Z N   match ranges 0-9, 1-9, 2-9 respectively.
2532  *      [       denotes the start of a set of character. Everything inside
2533  *              is considered literally. We can have ranges a-d and individual
2534  *              characters. A '[' and '-' can be considered literally if they
2535  *              are just before ']'.
2536  *              XXX currently there is no way to specify ']' in a range, nor \ is
2537  *              considered specially.
2538  *
2539  * When we compare a pattern with a specific extension, all characters in the extension
2540  * itself are considered literally.
2541  * XXX do we want to consider space as a separator as well ?
2542  * XXX do we want to consider the separators in non-patterns as well ?
2543  */
2544
2545 /*!
2546  * \brief helper functions to sort extension patterns in the desired way,
2547  * so that more specific patterns appear first.
2548  *
2549  * \details
2550  * The function compares individual characters (or sets of), returning
2551  * an int where bits 0-7 are the ASCII code of the first char in the set,
2552  * bits 8-15 are the number of characters in the set, and bits 16-20 are
2553  * for special cases.
2554  * This way more specific patterns (smaller character sets) appear first.
2555  * Wildcards have a special value, so that we can directly compare them to
2556  * sets by subtracting the two values. In particular:
2557  *  0x001xx     one character, character set starting with xx
2558  *  0x0yyxx     yy characters, character set starting with xx
2559  *  0x18000     '.' (one or more of anything)
2560  *  0x28000     '!' (zero or more of anything)
2561  *  0x30000     NUL (end of string)
2562  *  0x40000     error in set.
2563  * The pointer to the string is advanced according to needs.
2564  * NOTES:
2565  *  1. the empty set is ignored.
2566  *  2. given that a full set has always 0 as the first element,
2567  *     we could encode the special cases as 0xffXX where XX
2568  *     is 1, 2, 3, 4 as used above.
2569  */
2570 static int ext_cmp_pattern_pos(const char **p, unsigned char *bitwise)
2571 {
2572 #define BITS_PER        8       /* Number of bits per unit (byte). */
2573         unsigned char c;
2574         unsigned char cmin;
2575         int count;
2576         const char *end;
2577
2578         do {
2579                 /* Get character and advance. (Ignore '-' chars as eye candy fluff.) */
2580                 do {
2581                         c = *(*p)++;
2582                 } while (c == '-');
2583
2584                 /* always return unless we have a set of chars */
2585                 switch (c) {
2586                 default:
2587                         /* ordinary character */
2588                         bitwise[c / BITS_PER] = 1 << ((BITS_PER - 1) - (c % BITS_PER));
2589                         return 0x0100 | c;
2590
2591                 case 'n':
2592                 case 'N':
2593                         /* 2..9 */
2594                         bitwise[6] = 0x3f;
2595                         bitwise[7] = 0xc0;
2596                         return 0x0800 | '2';
2597
2598                 case 'x':
2599                 case 'X':
2600                         /* 0..9 */
2601                         bitwise[6] = 0xff;
2602                         bitwise[7] = 0xc0;
2603                         return 0x0A00 | '0';
2604
2605                 case 'z':
2606                 case 'Z':
2607                         /* 1..9 */
2608                         bitwise[6] = 0x7f;
2609                         bitwise[7] = 0xc0;
2610                         return 0x0900 | '1';
2611
2612                 case '.':
2613                         /* wildcard */
2614                         return 0x18000;
2615
2616                 case '!':
2617                         /* earlymatch */
2618                         return 0x28000; /* less specific than '.' */
2619
2620                 case '\0':
2621                         /* empty string */
2622                         *p = NULL;
2623                         return 0x30000;
2624
2625                 case '[':
2626                         /* char set */
2627                         break;
2628                 }
2629                 /* locate end of set */
2630                 end = strchr(*p, ']');
2631
2632                 if (!end) {
2633                         ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2634                         return 0x40000; /* XXX make this entry go last... */
2635                 }
2636
2637                 count = 0;
2638                 cmin = 0xFF;
2639                 for (; *p < end; ++*p) {
2640                         unsigned char c1;       /* first char in range */
2641                         unsigned char c2;       /* last char in range */
2642
2643                         c1 = (*p)[0];
2644                         if (*p + 2 < end && (*p)[1] == '-') { /* this is a range */
2645                                 c2 = (*p)[2];
2646                                 *p += 2;    /* skip a total of 3 chars */
2647                         } else {        /* individual character */
2648                                 c2 = c1;
2649                         }
2650                         if (c1 < cmin) {
2651                                 cmin = c1;
2652                         }
2653                         for (; c1 <= c2; ++c1) {
2654                                 unsigned char mask = 1 << ((BITS_PER - 1) - (c1 % BITS_PER));
2655
2656                                 /*
2657                                  * Note: If two character sets score the same, the one with the
2658                                  * lowest ASCII values will compare as coming first.  Must fill
2659                                  * in most significant bits for lower ASCII values to accomplish
2660                                  * the desired sort order.
2661                                  */
2662                                 if (!(bitwise[c1 / BITS_PER] & mask)) {
2663                                         /* Add the character to the set. */
2664                                         bitwise[c1 / BITS_PER] |= mask;
2665                                         count += 0x100;
2666                                 }
2667                         }
2668                 }
2669                 ++*p;
2670         } while (!count);/* While the char set was empty. */
2671         return count | cmin;
2672 }
2673
2674 /*!
2675  * \internal
2676  * \brief Comparison of exten patterns.
2677  *
2678  * \param left Pattern to compare.
2679  * \param right Pattern to compare.
2680  *
2681  * \retval <0 if left < right
2682  * \retval =0 if left == right
2683  * \retval >0 if left > right
2684  */
2685 static int ext_cmp_pattern(const char *left, const char *right)
2686 {
2687         int cmp;
2688         int left_pos;
2689         int right_pos;
2690
2691         for (;;) {
2692                 unsigned char left_bitwise[32] = { 0, };
2693                 unsigned char right_bitwise[32] = { 0, };
2694
2695                 left_pos = ext_cmp_pattern_pos(&left, left_bitwise);
2696                 right_pos = ext_cmp_pattern_pos(&right, right_bitwise);
2697                 cmp = left_pos - right_pos;
2698                 if (!cmp) {
2699                         /*
2700                          * Are the character sets different, even though they score the same?
2701                          *
2702                          * Note: Must swap left and right to get the sense of the
2703                          * comparison correct.  Otherwise, we would need to multiply by
2704                          * -1 instead.
2705                          */
2706                         cmp = memcmp(right_bitwise, left_bitwise, ARRAY_LEN(left_bitwise));
2707                 }
2708                 if (cmp) {
2709                         break;
2710                 }
2711                 if (!left) {
2712                         /*
2713                          * Get here only if both patterns ended at the same time.  cmp
2714                          * would be non-zero if only one pattern ended.
2715                          */
2716                         break;
2717                 }
2718         }
2719         return cmp;
2720 }
2721
2722 /*!
2723  * \internal
2724  * \brief Comparison of dialplan extens for sorting purposes.
2725  *
2726  * \param left Exten/pattern to compare.
2727  * \param right Exten/pattern to compare.
2728  *
2729  * \retval <0 if left < right
2730  * \retval =0 if left == right
2731  * \retval >0 if left > right
2732  */
2733 static int ext_cmp(const char *left, const char *right)
2734 {
2735         /* Make sure non-pattern extens come first. */
2736         if (left[0] != '_') {
2737                 if (right[0] == '_') {
2738                         return -1;
2739                 }
2740                 /* Compare two non-pattern extens. */
2741                 return ext_cmp_exten(left, right);
2742         }
2743         if (right[0] != '_') {
2744                 return 1;
2745         }
2746
2747         /*
2748          * OK, we need full pattern sorting routine.
2749          *
2750          * Skip past the underscores
2751          */
2752         return ext_cmp_pattern(left + 1, right + 1);
2753 }
2754
2755 int ast_extension_cmp(const char *a, const char *b)
2756 {
2757         int cmp;
2758
2759         cmp = ext_cmp(a, b);
2760         if (cmp < 0) {
2761                 return -1;
2762         }
2763         if (cmp > 0) {
2764                 return 1;
2765         }
2766         return 0;
2767 }
2768
2769 /*!
2770  * \internal
2771  * \brief used ast_extension_{match|close}
2772  * mode is as follows:
2773  *      E_MATCH         success only on exact match
2774  *      E_MATCHMORE     success only on partial match (i.e. leftover digits in pattern)
2775  *      E_CANMATCH      either of the above.
2776  * \retval 0 on no-match
2777  * \retval 1 on match
2778  * \retval 2 on early match.
2779  */
2780
2781 static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2782 {
2783         mode &= E_MATCH_MASK;   /* only consider the relevant bits */
2784
2785 #ifdef NEED_DEBUG_HERE
2786         ast_log(LOG_NOTICE,"match core: pat: '%s', dat: '%s', mode=%d\n", pattern, data, (int)mode);
2787 #endif
2788
2789         if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
2790                 int lp = ext_cmp_exten_strlen(pattern);
2791                 int ld = ext_cmp_exten_strlen(data);
2792
2793                 if (lp < ld) {          /* pattern too short, cannot match */
2794 #ifdef NEED_DEBUG_HERE
2795                         ast_log(LOG_NOTICE,"return (0) - pattern too short, cannot match\n");
2796 #endif
2797                         return 0;
2798                 }
2799                 /* depending on the mode, accept full or partial match or both */
2800                 if (mode == E_MATCH) {
2801 #ifdef NEED_DEBUG_HERE
2802                         ast_log(LOG_NOTICE,"return (!ext_cmp_exten(%s,%s) when mode== E_MATCH)\n", pattern, data);
2803 #endif
2804                         return !ext_cmp_exten(pattern, data); /* 1 on match, 0 on fail */
2805                 }
2806                 if (ld == 0 || !ext_cmp_exten_partial(pattern, data)) { /* partial or full match */
2807 #ifdef NEED_DEBUG_HERE
2808                         ast_log(LOG_NOTICE,"return (mode(%d) == E_MATCHMORE ? lp(%d) > ld(%d) : 1)\n", mode, lp, ld);
2809 #endif
2810                         return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
2811                 } else {
2812 #ifdef NEED_DEBUG_HERE
2813                         ast_log(LOG_NOTICE,"return (0) when ld(%d) > 0 && pattern(%s) != data(%s)\n", ld, pattern, data);
2814 #endif
2815                         return 0;
2816                 }
2817         }
2818         if (mode == E_MATCH && data[0] == '_') {
2819                 /*
2820                  * XXX It is bad design that we don't know if we should be
2821                  * comparing data and pattern as patterns or comparing data if
2822                  * it conforms to pattern when the function is called.  First,
2823                  * assume they are both patterns.  If they don't match then try
2824                  * to see if data conforms to the given pattern.
2825                  *
2826                  * note: if this test is left out, then _x. will not match _x. !!!
2827                  */
2828 #ifdef NEED_DEBUG_HERE
2829                 ast_log(LOG_NOTICE, "Comparing as patterns first. pattern:%s data:%s\n", pattern, data);
2830 #endif
2831                 if (!ext_cmp_pattern(pattern + 1, data + 1)) {
2832 #ifdef NEED_DEBUG_HERE
2833                         ast_log(LOG_NOTICE,"return (1) - pattern matches pattern\n");
2834 #endif
2835                         return 1;
2836                 }
2837         }
2838
2839         ++pattern; /* skip leading _ */
2840         /*
2841          * XXX below we stop at '/' which is a separator for the CID info. However we should
2842          * not store '/' in the pattern at all. When we insure it, we can remove the checks.
2843          */
2844         for (;;) {
2845                 const char *end;
2846
2847                 /* Ignore '-' chars as eye candy fluff. */
2848                 while (*data == '-') {
2849                         ++data;
2850                 }
2851                 while (*pattern == '-') {
2852                         ++pattern;
2853                 }
2854                 if (!*data || !*pattern || *pattern == '/') {
2855                         break;
2856                 }
2857
2858                 switch (*pattern) {
2859                 case '[':       /* a range */
2860                         ++pattern;
2861                         end = strchr(pattern, ']'); /* XXX should deal with escapes ? */
2862                         if (!end) {
2863                                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2864                                 return 0;       /* unconditional failure */
2865                         }
2866                         if (pattern == end) {
2867                                 /* Ignore empty character sets. */
2868                                 ++pattern;
2869                                 continue;
2870                         }
2871                         for (; pattern < end; ++pattern) {
2872                                 if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
2873                                         if (*data >= pattern[0] && *data <= pattern[2])
2874                                                 break;  /* match found */
2875                                         else {
2876                                                 pattern += 2; /* skip a total of 3 chars */
2877                                                 continue;
2878                                         }
2879                                 } else if (*data == pattern[0])
2880                                         break;  /* match found */
2881                         }
2882                         if (pattern >= end) {
2883 #ifdef NEED_DEBUG_HERE
2884                                 ast_log(LOG_NOTICE,"return (0) when pattern>=end\n");
2885 #endif
2886                                 return 0;
2887                         }
2888                         pattern = end;  /* skip and continue */
2889                         break;
2890                 case 'n':
2891                 case 'N':
2892                         if (*data < '2' || *data > '9') {
2893 #ifdef NEED_DEBUG_HERE
2894                                 ast_log(LOG_NOTICE,"return (0) N is not matched\n");
2895 #endif
2896                                 return 0;
2897                         }
2898                         break;
2899                 case 'x':
2900                 case 'X':
2901                         if (*data < '0' || *data > '9') {
2902 #ifdef NEED_DEBUG_HERE
2903                                 ast_log(LOG_NOTICE,"return (0) X is not matched\n");
2904 #endif
2905                                 return 0;
2906                         }
2907                         break;
2908                 case 'z':
2909                 case 'Z':
2910                         if (*data < '1' || *data > '9') {
2911 #ifdef NEED_DEBUG_HERE
2912                                 ast_log(LOG_NOTICE,"return (0) Z is not matched\n");
2913 #endif
2914                                 return 0;
2915                         }
2916                         break;
2917                 case '.':       /* Must match, even with more digits */
2918 #ifdef NEED_DEBUG_HERE
2919                         ast_log(LOG_NOTICE, "return (1) when '.' is matched\n");
2920 #endif
2921                         return 1;
2922                 case '!':       /* Early match */
2923 #ifdef NEED_DEBUG_HERE
2924                         ast_log(LOG_NOTICE, "return (2) when '!' is matched\n");
2925 #endif
2926                         return 2;
2927                 default:
2928                         if (*data != *pattern) {
2929 #ifdef NEED_DEBUG_HERE
2930                                 ast_log(LOG_NOTICE, "return (0) when *data(%c) != *pattern(%c)\n", *data, *pattern);
2931 #endif
2932                                 return 0;
2933                         }
2934                         break;
2935                 }
2936                 ++data;
2937                 ++pattern;
2938         }
2939         if (*data)                      /* data longer than pattern, no match */ {
2940 #ifdef NEED_DEBUG_HERE
2941                 ast_log(LOG_NOTICE, "return (0) when data longer than pattern\n");
2942 #endif
2943                 return 0;
2944         }
2945
2946         /*
2947          * match so far, but ran off the end of data.
2948          * Depending on what is next, determine match or not.
2949          */
2950         if (*pattern == '\0' || *pattern == '/') {      /* exact match */
2951 #ifdef NEED_DEBUG_HERE
2952                 ast_log(LOG_NOTICE, "at end, return (%d) in 'exact match'\n", (mode==E_MATCHMORE) ? 0 : 1);
2953 #endif
2954                 return (mode == E_MATCHMORE) ? 0 : 1;   /* this is a failure for E_MATCHMORE */
2955         } else if (*pattern == '!')     {               /* early match */
2956 #ifdef NEED_DEBUG_HERE
2957                 ast_log(LOG_NOTICE, "at end, return (2) when '!' is matched\n");
2958 #endif
2959                 return 2;
2960         } else {                                                /* partial match */
2961 #ifdef NEED_DEBUG_HERE
2962                 ast_log(LOG_NOTICE, "at end, return (%d) which deps on E_MATCH\n", (mode == E_MATCH) ? 0 : 1);
2963 #endif
2964                 return (mode == E_MATCH) ? 0 : 1;       /* this is a failure for E_MATCH */
2965         }
2966 }
2967
2968 /*
2969  * Wrapper around _extension_match_core() to do performance measurement
2970  * using the profiling code.
2971  */
2972 static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2973 {
2974         int i;
2975         static int prof_id = -2;        /* marker for 'unallocated' id */
2976         if (prof_id == -2) {
2977                 prof_id = ast_add_profile("ext_match", 0);
2978         }
2979         ast_mark(prof_id, 1);
2980         i = _extension_match_core(ast_strlen_zero(pattern) ? "" : pattern, ast_strlen_zero(data) ? "" : data, mode);
2981         ast_mark(prof_id, 0);
2982         return i;
2983 }
2984
2985 int ast_extension_match(const char *pattern, const char *data)
2986 {
2987         return extension_match_core(pattern, data, E_MATCH);
2988 }
2989
2990 int ast_extension_close(const char *pattern, const char *data, int needmore)
2991 {
2992         if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
2993                 ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
2994         return extension_match_core(pattern, data, needmore);
2995 }
2996
2997 struct fake_context /* this struct is purely for matching in the hashtab */
2998 {
2999         ast_rwlock_t lock;
3000         struct ast_exten *root;
3001         struct ast_hashtab *root_table;
3002         struct match_char *pattern_tree;
3003         struct ast_context *next;
3004         struct ast_include *includes;
3005         struct ast_ignorepat *ignorepats;
3006         const char *registrar;
3007         int refcount;
3008         AST_LIST_HEAD_NOLOCK(, ast_sw) alts;
3009         ast_mutex_t macrolock;
3010         char name[256];
3011 };
3012
3013 struct ast_context *ast_context_find(const char *name)
3014 {
3015         struct ast_context *tmp;
3016         struct fake_context item;
3017
3018         if (!name) {
3019                 return NULL;
3020         }
3021         ast_rdlock_contexts();
3022         if (contexts_table) {
3023                 ast_copy_string(item.name, name, sizeof(item.name));
3024                 tmp = ast_hashtab_lookup(contexts_table, &item);
3025         } else {
3026                 tmp = NULL;
3027                 while ((tmp = ast_walk_contexts(tmp))) {
3028                         if (!strcasecmp(name, tmp->name)) {
3029                                 break;
3030                         }
3031                 }
3032         }
3033         ast_unlock_contexts();
3034         return tmp;
3035 }
3036
3037 #define STATUS_NO_CONTEXT       1
3038 #define STATUS_NO_EXTENSION     2
3039 #define STATUS_NO_PRIORITY      3
3040 #define STATUS_NO_LABEL         4
3041 #define STATUS_SUCCESS          5
3042
3043 static int matchcid(const char *cidpattern, const char *callerid)
3044 {
3045         /* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
3046            failing to get a number should count as a match, otherwise not */
3047
3048         if (ast_strlen_zero(callerid)) {
3049                 return ast_strlen_zero(cidpattern) ? 1 : 0;
3050         }
3051
3052         return ast_extension_match(cidpattern, callerid);
3053 }
3054
3055 struct ast_exten *pbx_find_extension(struct ast_channel *chan,
3056         struct ast_context *bypass, struct pbx_find_info *q,
3057         const char *context, const char *exten, int priority,
3058         const char *label, const char *callerid, enum ext_match_t action)
3059 {
3060         int x, res;
3061         struct ast_context *tmp = NULL;
3062         struct ast_exten *e = NULL, *eroot = NULL;
3063         struct ast_include *i = NULL;
3064         struct ast_sw *sw = NULL;
3065         struct ast_exten pattern = {NULL, };
3066         struct scoreboard score = {0, };
3067         struct ast_str *tmpdata = NULL;
3068
3069         pattern.label = label;
3070         pattern.priority = priority;
3071 #ifdef NEED_DEBUG_HERE
3072         ast_log(LOG_NOTICE, "Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int) action);
3073 #endif
3074
3075         /* Initialize status if appropriate */
3076         if (q->stacklen == 0) {
3077                 q->status = STATUS_NO_CONTEXT;
3078                 q->swo = NULL;
3079                 q->data = NULL;
3080                 q->foundcontext = NULL;
3081         } else if (q->stacklen >= AST_PBX_MAX_STACK) {
3082                 ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
3083                 return NULL;
3084         }
3085
3086         /* Check first to see if we've already been checked */
3087         for (x = 0; x < q->stacklen; x++) {
3088                 if (!strcasecmp(q->incstack[x], context))
3089                         return NULL;
3090         }
3091
3092         if (bypass) { /* bypass means we only look there */
3093                 tmp = bypass;
3094         } else {      /* look in contexts */
3095                 tmp = find_context(context);
3096                 if (!tmp) {
3097                         return NULL;
3098                 }
3099         }
3100
3101         if (q->status < STATUS_NO_EXTENSION)
3102                 q->status = STATUS_NO_EXTENSION;
3103
3104         /* Do a search for matching extension */
3105
3106         eroot = NULL;
3107         score.total_specificity = 0;
3108         score.exten = 0;
3109         score.total_length = 0;
3110         if (!tmp->pattern_tree && tmp->root_table) {
3111                 create_match_char_tree(tmp);
3112 #ifdef NEED_DEBUG
3113                 ast_debug(1, "Tree Created in context %s:\n", context);
3114                 log_match_char_tree(tmp->pattern_tree," ");
3115 #endif
3116         }
3117 #ifdef NEED_DEBUG
3118         ast_log(LOG_NOTICE, "The Trie we are searching in:\n");
3119         log_match_char_tree(tmp->pattern_tree, "::  ");
3120 #endif
3121
3122         do {
3123                 if (!ast_strlen_zero(overrideswitch)) {
3124                         char *osw = ast_strdupa(overrideswitch), *name;
3125                         struct ast_switch *asw;
3126                         ast_switch_f *aswf = NULL;
3127                         char *datap;
3128                         int eval = 0;
3129
3130                         name = strsep(&osw, "/");
3131                         asw = pbx_findswitch(name);
3132
3133                         if (!asw) {
3134                                 ast_log(LOG_WARNING, "No such switch '%s'\n", name);
3135                                 break;
3136                         }
3137
3138                         if (osw && strchr(osw, '$')) {
3139                                 eval = 1;
3140                         }
3141
3142                         if (eval && !(tmpdata = ast_str_thread_get(&switch_data, 512))) {
3143                                 ast_log(LOG_WARNING, "Can't evaluate overrideswitch?!\n");
3144                                 break;
3145                         } else if (eval) {
3146                                 /* Substitute variables now */
3147                                 pbx_substitute_variables_helper(chan, osw, ast_str_buffer(tmpdata), ast_str_size(tmpdata));
3148                                 datap = ast_str_buffer(tmpdata);
3149                         } else {
3150                                 datap = osw;
3151                         }
3152
3153                         /* equivalent of extension_match_core() at the switch level */
3154                         if (action == E_CANMATCH)
3155                                 aswf = asw->canmatch;
3156                         else if (action == E_MATCHMORE)
3157                                 aswf = asw->matchmore;
3158                         else /* action == E_MATCH */
3159                                 aswf = asw->exists;
3160                         if (!aswf) {
3161                                 res = 0;
3162                         } else {
3163                                 if (chan) {
3164                                         ast_autoservice_start(chan);
3165                                 }
3166                                 res = aswf(chan, context, exten, priority, callerid, datap);
3167                                 if (chan) {
3168                                         ast_autoservice_stop(chan);
3169                                 }
3170                         }
3171                         if (res) {      /* Got a match */
3172                                 q->swo = asw;
3173                                 q->data = datap;
3174                                 q->foundcontext = context;
3175                                 /* XXX keep status = STATUS_NO_CONTEXT ? */
3176                                 return NULL;
3177                         }
3178                 }
3179         } while (0);
3180
3181         if (extenpatternmatchnew) {
3182                 new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid, label, action);
3183                 eroot = score.exten;
3184
3185                 if (score.last_char == '!' && action == E_MATCHMORE) {
3186                         /* We match an extension ending in '!'.
3187                          * The decision in this case is final and is NULL (no match).
3188                          */
3189 #ifdef NEED_DEBUG_HERE
3190                         ast_log(LOG_NOTICE,"Returning MATCHMORE NULL with exclamation point.\n");
3191 #endif
3192                         return NULL;
3193                 }
3194
3195                 if (!eroot && (action == E_CANMATCH || action == E_MATCHMORE) && score.canmatch_exten) {
3196                         q->status = STATUS_SUCCESS;
3197 #ifdef NEED_DEBUG_HERE
3198                         ast_log(LOG_NOTICE,"Returning CANMATCH exten %s\n", score.canmatch_exten->exten);
3199 #endif
3200                         return score.canmatch_exten;
3201                 }
3202
3203                 if ((action == E_MATCHMORE || action == E_CANMATCH)  && eroot) {
3204                         if (score.node) {
3205                                 struct ast_exten *z = trie_find_next_match(score.node);
3206                                 if (z) {
3207 #ifdef NEED_DEBUG_HERE
3208                                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten %s\n", z->exten);
3209 #endif
3210                                 } else {
3211                                         if (score.canmatch_exten) {
3212 #ifdef NEED_DEBUG_HERE
3213                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE canmatchmatch exten %s(%p)\n", score.canmatch_exten->exten, score.canmatch_exten);
3214 #endif
3215                                                 return score.canmatch_exten;
3216                                         } else {
3217 #ifdef NEED_DEBUG_HERE
3218                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten NULL\n");
3219 #endif
3220                                         }
3221                                 }
3222                                 return z;
3223                         }
3224 #ifdef NEED_DEBUG_HERE
3225                         ast_log(LOG_NOTICE, "Returning CANMATCH/MATCHMORE NULL (no next_match)\n");
3226 #endif
3227                         return NULL;  /* according to the code, complete matches are null matches in MATCHMORE mode */
3228                 }
3229
3230                 if (eroot) {
3231                         /* found entry, now look for the right priority */
3232                         if (q->status < STATUS_NO_PRIORITY)
3233                                 q->status = STATUS_NO_PRIORITY;
3234                         e = NULL;
3235                         if (action == E_FINDLABEL && label ) {
3236                                 if (q->status < STATUS_NO_LABEL)
3237                                         q->status = STATUS_NO_LABEL;
3238                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
3239                         } else {
3240                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
3241                         }
3242                         if (e) {        /* found a valid match */
3243                                 q->status = STATUS_SUCCESS;
3244                                 q->foundcontext = context;
3245 #ifdef NEED_DEBUG_HERE
3246                                 ast_log(LOG_NOTICE,"Returning complete match of exten %s\n", e->exten);
3247 #endif
3248                                 return e;
3249                         }
3250                 }
3251         } else {   /* the old/current default exten pattern match algorithm */
3252
3253                 /* scan the list trying to match extension and CID */
3254                 eroot = NULL;
3255                 while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
3256                         int match = extension_match_core(eroot->exten, exten, action);
3257                         /* 0 on fail, 1 on match, 2 on earlymatch */
3258
3259                         if (!match || (eroot->matchcid && !matchcid(eroot->cidmatch, callerid)))
3260                                 continue;       /* keep trying */
3261                         if (match == 2 && action == E_MATCHMORE) {
3262                                 /* We match an extension ending in '!'.
3263                                  * The decision in this case is final and is NULL (no match).
3264                                  */
3265                                 return NULL;
3266                         }
3267                         /* found entry, now look for the right priority */
3268                         if (q->status < STATUS_NO_PRIORITY)
3269                                 q->status = STATUS_NO_PRIORITY;
3270                         e = NULL;
3271                         if (action == E_FINDLABEL && label ) {
3272                                 if (q->status < STATUS_NO_LABEL)
3273                                         q->status = STATUS_NO_LABEL;
3274                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
3275                         } else {
3276                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
3277                         }
3278                         if (e) {        /* found a valid match */
3279                                 q->status = STATUS_SUCCESS;
3280                                 q->foundcontext = context;
3281                                 return e;
3282                         }
3283                 }
3284         }
3285
3286         /* Check alternative switches */
3287         AST_LIST_TRAVERSE(&tmp->alts, sw, list) {
3288                 struct ast_switch *asw = pbx_findswitch(sw->name);
3289                 ast_switch_f *aswf = NULL;
3290                 char *datap;
3291
3292                 if (!asw) {
3293                         ast_log(LOG_WARNING, "No such switch '%s'\n", sw->name);
3294                         continue;
3295                 }
3296
3297                 /* Substitute variables now */
3298                 if (sw->eval) {
3299                         if (!(tmpdata = ast_str_thread_get(&switch_data, 512))) {
3300                                 ast_log(LOG_WARNING, "Can't evaluate switch?!\n");
3301                                 continue;
3302                         }
3303                         pbx_substitute_variables_helper(chan, sw->data, ast_str_buffer(tmpdata), ast_str_size(tmpdata));
3304                 }
3305
3306                 /* equivalent of extension_match_core() at the switch level */
3307                 if (action == E_CANMATCH)
3308                         aswf = asw->canmatch;
3309                 else if (action == E_MATCHMORE)
3310                         aswf = asw->matchmore;
3311                 else /* action == E_MATCH */
3312                         aswf = asw->exists;
3313                 datap = sw->eval ? ast_str_buffer(tmpdata) : sw->data;
3314                 if (!aswf)