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