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