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