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