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