Merged revisions 332756 via svnmerge from
[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 neither the <literal>h</literal> nor <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 neither the <literal>h</literal> nor <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         /*! \note Only used by ast_merge_contexts_and_delete */
925         AST_LIST_ENTRY(ast_state_cb) entry;
926 };
927
928 /*!
929  * \brief Structure for dial plan hints
930  *
931  * \note Hints are pointers from an extension in the dialplan to
932  * one or more devices (tech/name)
933  *
934  * See \ref AstExtState
935  */
936 struct ast_hint {
937         /*!
938          * \brief Hint extension
939          *
940          * \note
941          * Will never be NULL while the hint is in the hints container.
942          */
943         struct ast_exten *exten;
944         struct ao2_container *callbacks; /*!< Callback container for this extension */
945         int laststate;                  /*!< Last known state */
946         char context_name[AST_MAX_CONTEXT];/*!< Context of destroyed hint extension. */
947         char exten_name[AST_MAX_EXTENSION];/*!< Extension of destroyed hint extension. */
948 };
949
950
951 #define HINTDEVICE_DATA_LENGTH 16
952 AST_THREADSTORAGE(hintdevice_data);
953
954 /* --- Hash tables of various objects --------*/
955 #ifdef LOW_MEMORY
956 static const int HASH_EXTENHINT_SIZE = 17;
957 #else
958 static const int HASH_EXTENHINT_SIZE = 563;
959 #endif
960
961
962 /*! \brief Container for hint devices */
963 static struct ao2_container *hintdevices;
964
965 /*!
966  * \brief Structure for dial plan hint devices
967  * \note hintdevice is one device pointing to a hint.
968  */
969 struct ast_hintdevice {
970         /*!
971          * \brief Hint this hintdevice belongs to.
972          * \note Holds a reference to the hint object.
973          */
974         struct ast_hint *hint;
975         /*! Name of the hint device. */
976         char hintdevice[1];
977 };
978
979
980 /*!
981  * \note Using the device for hash
982  */
983 static int hintdevice_hash_cb(const void *obj, const int flags)
984 {
985         const struct ast_hintdevice *ext = obj;
986
987         return ast_str_case_hash(ext->hintdevice);
988 }
989 /*!
990  * \note Devices on hints are not unique so no CMP_STOP is returned
991  * Dont use ao2_find against hintdevices container cause there always
992  * could be more than one result.
993  */
994 static int hintdevice_cmp_multiple(void *obj, void *arg, int flags)
995 {
996         struct ast_hintdevice *ext = obj, *ext2 = arg;
997
998         return !strcasecmp(ext->hintdevice, ext2->hintdevice) ? CMP_MATCH  : 0;
999 }
1000
1001 /*
1002  * \details This is used with ao2_callback to remove old devices
1003  * when they are linked to the hint
1004 */
1005 static int hintdevice_remove_cb(void *deviceobj, void *arg, int flags)
1006 {
1007         struct ast_hintdevice *device = deviceobj;
1008         struct ast_hint *hint = arg;
1009
1010         return (device->hint == hint) ? CMP_MATCH : 0;
1011 }
1012
1013 static int remove_hintdevice(struct ast_hint *hint)
1014 {
1015         /* iterate through all devices and remove the devices which are linked to this hint */
1016         ao2_t_callback(hintdevices, OBJ_NODATA | OBJ_MULTIPLE | OBJ_UNLINK,
1017                 hintdevice_remove_cb, hint,
1018                 "callback to remove all devices which are linked to a hint");
1019         return 0;
1020 }
1021
1022 /*!
1023  * \internal
1024  * \brief Destroy the given hintdevice object.
1025  *
1026  * \param obj Hint device to destroy.
1027  *
1028  * \return Nothing
1029  */
1030 static void hintdevice_destroy(void *obj)
1031 {
1032         struct ast_hintdevice *doomed = obj;
1033
1034         if (doomed->hint) {
1035                 ao2_ref(doomed->hint, -1);
1036                 doomed->hint = NULL;
1037         }
1038 }
1039
1040 /*! \brief add hintdevice structure and link it into the container.
1041  */
1042 static int add_hintdevice(struct ast_hint *hint, const char *devicelist)
1043 {
1044         struct ast_str *str;
1045         char *parse;
1046         char *cur;
1047         struct ast_hintdevice *device;
1048         int devicelength;
1049
1050         if (!hint || !devicelist) {
1051                 /* Trying to add garbage? Don't bother. */
1052                 return 0;
1053         }
1054         if (!(str = ast_str_thread_get(&hintdevice_data, 16))) {
1055                 return -1;
1056         }
1057         ast_str_set(&str, 0, "%s", devicelist);
1058         parse = ast_str_buffer(str);
1059
1060         while ((cur = strsep(&parse, "&"))) {
1061                 devicelength = strlen(cur);
1062                 device = ao2_t_alloc(sizeof(*device) + devicelength, hintdevice_destroy,
1063                         "allocating a hintdevice structure");
1064                 if (!device) {
1065                         return -1;
1066                 }
1067                 strcpy(device->hintdevice, cur);
1068                 ao2_ref(hint, +1);
1069                 device->hint = hint;
1070                 ao2_t_link(hintdevices, device, "Linking device into hintdevice container.");
1071                 ao2_t_ref(device, -1, "hintdevice is linked so we can unref");
1072         }
1073
1074         return 0;
1075 }
1076
1077
1078 static const struct cfextension_states {
1079         int extension_state;
1080         const char * const text;
1081 } extension_states[] = {
1082         { AST_EXTENSION_NOT_INUSE,                     "Idle" },
1083         { AST_EXTENSION_INUSE,                         "InUse" },
1084         { AST_EXTENSION_BUSY,                          "Busy" },
1085         { AST_EXTENSION_UNAVAILABLE,                   "Unavailable" },
1086         { AST_EXTENSION_RINGING,                       "Ringing" },
1087         { AST_EXTENSION_INUSE | AST_EXTENSION_RINGING, "InUse&Ringing" },
1088         { AST_EXTENSION_ONHOLD,                        "Hold" },
1089         { AST_EXTENSION_INUSE | AST_EXTENSION_ONHOLD,  "InUse&Hold" }
1090 };
1091
1092 struct statechange {
1093         AST_LIST_ENTRY(statechange) entry;
1094         char dev[0];
1095 };
1096
1097 struct pbx_exception {
1098         AST_DECLARE_STRING_FIELDS(
1099                 AST_STRING_FIELD(context);      /*!< Context associated with this exception */
1100                 AST_STRING_FIELD(exten);        /*!< Exten associated with this exception */
1101                 AST_STRING_FIELD(reason);               /*!< The exception reason */
1102         );
1103
1104         int priority;                           /*!< Priority associated with this exception */
1105 };
1106
1107 static int pbx_builtin_answer(struct ast_channel *, const char *);
1108 static int pbx_builtin_goto(struct ast_channel *, const char *);
1109 static int pbx_builtin_hangup(struct ast_channel *, const char *);
1110 static int pbx_builtin_background(struct ast_channel *, const char *);
1111 static int pbx_builtin_wait(struct ast_channel *, const char *);
1112 static int pbx_builtin_waitexten(struct ast_channel *, const char *);
1113 static int pbx_builtin_incomplete(struct ast_channel *, const char *);
1114 static int pbx_builtin_resetcdr(struct ast_channel *, const char *);
1115 static int pbx_builtin_setamaflags(struct ast_channel *, const char *);
1116 static int pbx_builtin_ringing(struct ast_channel *, const char *);
1117 static int pbx_builtin_proceeding(struct ast_channel *, const char *);
1118 static int pbx_builtin_progress(struct ast_channel *, const char *);
1119 static int pbx_builtin_congestion(struct ast_channel *, const char *);
1120 static int pbx_builtin_busy(struct ast_channel *, const char *);
1121 static int pbx_builtin_noop(struct ast_channel *, const char *);
1122 static int pbx_builtin_gotoif(struct ast_channel *, const char *);
1123 static int pbx_builtin_gotoiftime(struct ast_channel *, const char *);
1124 static int pbx_builtin_execiftime(struct ast_channel *, const char *);
1125 static int pbx_builtin_saynumber(struct ast_channel *, const char *);
1126 static int pbx_builtin_saydigits(struct ast_channel *, const char *);
1127 static int pbx_builtin_saycharacters(struct ast_channel *, const char *);
1128 static int pbx_builtin_sayphonetic(struct ast_channel *, const char *);
1129 static int matchcid(const char *cidpattern, const char *callerid);
1130 #ifdef NEED_DEBUG
1131 static void log_match_char_tree(struct match_char *node, char *prefix); /* for use anywhere */
1132 #endif
1133 static int pbx_builtin_importvar(struct ast_channel *, const char *);
1134 static void set_ext_pri(struct ast_channel *c, const char *exten, int pri);
1135 static void new_find_extension(const char *str, struct scoreboard *score,
1136                 struct match_char *tree, int length, int spec, const char *callerid,
1137                 const char *label, enum ext_match_t action);
1138 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern);
1139 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con,
1140                 struct ast_exten *e1, int findonly);
1141 static struct match_char *add_pattern_node(struct ast_context *con,
1142                 struct match_char *current, char *pattern, int is_pattern,
1143                 int already, int specificity, struct match_char **parent);
1144 static void create_match_char_tree(struct ast_context *con);
1145 static struct ast_exten *get_canmatch_exten(struct match_char *node);
1146 static void destroy_pattern_tree(struct match_char *pattern_tree);
1147 static int hashtab_compare_extens(const void *ha_a, const void *ah_b);
1148 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b);
1149 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b);
1150 static unsigned int hashtab_hash_extens(const void *obj);
1151 static unsigned int hashtab_hash_priority(const void *obj);
1152 static unsigned int hashtab_hash_labels(const void *obj);
1153 static void __ast_internal_context_destroy( struct ast_context *con);
1154 static int ast_add_extension_nolock(const char *context, int replace, const char *extension,
1155         int priority, const char *label, const char *callerid,
1156         const char *application, void *data, void (*datad)(void *), const char *registrar);
1157 static int ast_add_extension2_lockopt(struct ast_context *con,
1158         int replace, const char *extension, int priority, const char *label, const char *callerid,
1159         const char *application, void *data, void (*datad)(void *),
1160         const char *registrar, int lock_context);
1161 static struct ast_context *find_context_locked(const char *context);
1162 static struct ast_context *find_context(const char *context);
1163
1164 /* a func for qsort to use to sort a char array */
1165 static int compare_char(const void *a, const void *b)
1166 {
1167         const char *ac = a;
1168         const char *bc = b;
1169         if ((*ac) < (*bc))
1170                 return -1;
1171         else if ((*ac) == (*bc))
1172                 return 0;
1173         else
1174                 return 1;
1175 }
1176
1177 /* labels, contexts are case sensitive  priority numbers are ints */
1178 int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b)
1179 {
1180         const struct ast_context *ac = ah_a;
1181         const struct ast_context *bc = ah_b;
1182         if (!ac || !bc) /* safety valve, but it might prevent a crash you'd rather have happen */
1183                 return 1;
1184         /* assume context names are registered in a string table! */
1185         return strcmp(ac->name, bc->name);
1186 }
1187
1188 static int hashtab_compare_extens(const void *ah_a, const void *ah_b)
1189 {
1190         const struct ast_exten *ac = ah_a;
1191         const struct ast_exten *bc = ah_b;
1192         int x = strcmp(ac->exten, bc->exten);
1193         if (x) { /* if exten names are diff, then return */
1194                 return x;
1195         }
1196
1197         /* but if they are the same, do the cidmatch values match? */
1198         if (ac->matchcid && bc->matchcid) {
1199                 return strcmp(ac->cidmatch,bc->cidmatch);
1200         } else if (!ac->matchcid && !bc->matchcid) {
1201                 return 0; /* if there's no matchcid on either side, then this is a match */
1202         } else {
1203                 return 1; /* if there's matchcid on one but not the other, they are different */
1204         }
1205 }
1206
1207 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b)
1208 {
1209         const struct ast_exten *ac = ah_a;
1210         const struct ast_exten *bc = ah_b;
1211         return ac->priority != bc->priority;
1212 }
1213
1214 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b)
1215 {
1216         const struct ast_exten *ac = ah_a;
1217         const struct ast_exten *bc = ah_b;
1218         return strcmp(S_OR(ac->label, ""), S_OR(bc->label, ""));
1219 }
1220
1221 unsigned int ast_hashtab_hash_contexts(const void *obj)
1222 {
1223         const struct ast_context *ac = obj;
1224         return ast_hashtab_hash_string(ac->name);
1225 }
1226
1227 static unsigned int hashtab_hash_extens(const void *obj)
1228 {
1229         const struct ast_exten *ac = obj;
1230         unsigned int x = ast_hashtab_hash_string(ac->exten);
1231         unsigned int y = 0;
1232         if (ac->matchcid)
1233                 y = ast_hashtab_hash_string(ac->cidmatch);
1234         return x+y;
1235 }
1236
1237 static unsigned int hashtab_hash_priority(const void *obj)
1238 {
1239         const struct ast_exten *ac = obj;
1240         return ast_hashtab_hash_int(ac->priority);
1241 }
1242
1243 static unsigned int hashtab_hash_labels(const void *obj)
1244 {
1245         const struct ast_exten *ac = obj;
1246         return ast_hashtab_hash_string(S_OR(ac->label, ""));
1247 }
1248
1249
1250 AST_RWLOCK_DEFINE_STATIC(globalslock);
1251 static struct varshead globals = AST_LIST_HEAD_NOLOCK_INIT_VALUE;
1252
1253 static int autofallthrough = 1;
1254 static int extenpatternmatchnew = 0;
1255 static char *overrideswitch = NULL;
1256
1257 /*! \brief Subscription for device state change events */
1258 static struct ast_event_sub *device_state_sub;
1259
1260 AST_MUTEX_DEFINE_STATIC(maxcalllock);
1261 static int countcalls;
1262 static int totalcalls;
1263
1264 static AST_RWLIST_HEAD_STATIC(acf_root, ast_custom_function);
1265
1266 /*! \brief Declaration of builtin applications */
1267 static struct pbx_builtin {
1268         char name[AST_MAX_APP];
1269         int (*execute)(struct ast_channel *chan, const char *data);
1270 } builtins[] =
1271 {
1272         /* These applications are built into the PBX core and do not
1273            need separate modules */
1274
1275         { "Answer",         pbx_builtin_answer },
1276         { "BackGround",     pbx_builtin_background },
1277         { "Busy",           pbx_builtin_busy },
1278         { "Congestion",     pbx_builtin_congestion },
1279         { "ExecIfTime",     pbx_builtin_execiftime },
1280         { "Goto",           pbx_builtin_goto },
1281         { "GotoIf",         pbx_builtin_gotoif },
1282         { "GotoIfTime",     pbx_builtin_gotoiftime },
1283         { "ImportVar",      pbx_builtin_importvar },
1284         { "Hangup",         pbx_builtin_hangup },
1285         { "Incomplete",     pbx_builtin_incomplete },
1286         { "NoOp",           pbx_builtin_noop },
1287         { "Proceeding",     pbx_builtin_proceeding },
1288         { "Progress",       pbx_builtin_progress },
1289         { "RaiseException", pbx_builtin_raise_exception },
1290         { "ResetCDR",       pbx_builtin_resetcdr },
1291         { "Ringing",        pbx_builtin_ringing },
1292         { "SayAlpha",       pbx_builtin_saycharacters },
1293         { "SayDigits",      pbx_builtin_saydigits },
1294         { "SayNumber",      pbx_builtin_saynumber },
1295         { "SayPhonetic",    pbx_builtin_sayphonetic },
1296         { "Set",            pbx_builtin_setvar },
1297         { "MSet",           pbx_builtin_setvar_multiple },
1298         { "SetAMAFlags",    pbx_builtin_setamaflags },
1299         { "Wait",           pbx_builtin_wait },
1300         { "WaitExten",      pbx_builtin_waitexten }
1301 };
1302
1303 static struct ast_context *contexts;
1304 static struct ast_hashtab *contexts_table = NULL;
1305
1306 /*!
1307  * \brief Lock for the ast_context list
1308  * \note
1309  * This lock MUST be recursive, or a deadlock on reload may result.  See
1310  * https://issues.asterisk.org/view.php?id=17643
1311  */
1312 AST_MUTEX_DEFINE_STATIC(conlock);
1313
1314 /*!
1315  * \brief Lock to hold off restructuring of hints by ast_merge_contexts_and_delete.
1316  */
1317 AST_MUTEX_DEFINE_STATIC(context_merge_lock);
1318
1319 static AST_RWLIST_HEAD_STATIC(apps, ast_app);
1320
1321 static AST_RWLIST_HEAD_STATIC(switches, ast_switch);
1322
1323 static int stateid = 1;
1324 /*!
1325  * \note When holding this container's lock, do _not_ do
1326  * anything that will cause conlock to be taken, unless you
1327  * _already_ hold it.  The ast_merge_contexts_and_delete function
1328  * will take the locks in conlock/hints order, so any other
1329  * paths that require both locks must also take them in that
1330  * order.
1331  */
1332 static struct ao2_container *hints;
1333
1334 static struct ao2_container *statecbs;
1335
1336 #ifdef CONTEXT_DEBUG
1337
1338 /* these routines are provided for doing run-time checks
1339    on the extension structures, in case you are having
1340    problems, this routine might help you localize where
1341    the problem is occurring. It's kinda like a debug memory
1342    allocator's arena checker... It'll eat up your cpu cycles!
1343    but you'll see, if you call it in the right places,
1344    right where your problems began...
1345 */
1346
1347 /* you can break on the check_contexts_trouble()
1348 routine in your debugger to stop at the moment
1349 there's a problem */
1350 void check_contexts_trouble(void);
1351
1352 void check_contexts_trouble(void)
1353 {
1354         int x = 1;
1355         x = 2;
1356 }
1357
1358 int check_contexts(char *, int);
1359
1360 int check_contexts(char *file, int line )
1361 {
1362         struct ast_hashtab_iter *t1;
1363         struct ast_context *c1, *c2;
1364         int found = 0;
1365         struct ast_exten *e1, *e2, *e3;
1366         struct ast_exten ex;
1367
1368         /* try to find inconsistencies */
1369         /* is every context in the context table in the context list and vice-versa ? */
1370
1371         if (!contexts_table) {
1372                 ast_log(LOG_NOTICE,"Called from: %s:%d: No contexts_table!\n", file, line);
1373                 usleep(500000);
1374         }
1375
1376         t1 = ast_hashtab_start_traversal(contexts_table);
1377         while( (c1 = ast_hashtab_next(t1))) {
1378                 for(c2=contexts;c2;c2=c2->next) {
1379                         if (!strcmp(c1->name, c2->name)) {
1380                                 found = 1;
1381                                 break;
1382                         }
1383                 }
1384                 if (!found) {
1385                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the linked list\n", file, line, c1->name);
1386                         check_contexts_trouble();
1387                 }
1388         }
1389         ast_hashtab_end_traversal(t1);
1390         for(c2=contexts;c2;c2=c2->next) {
1391                 c1 = find_context_locked(c2->name);
1392                 if (!c1) {
1393                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the hashtab\n", file, line, c2->name);
1394                         check_contexts_trouble();
1395                 } else
1396                         ast_unlock_contexts();
1397         }
1398
1399         /* loop thru all contexts, and verify the exten structure compares to the 
1400            hashtab structure */
1401         for(c2=contexts;c2;c2=c2->next) {
1402                 c1 = find_context_locked(c2->name);
1403                 if (c1) {
1404                         ast_unlock_contexts();
1405
1406                         /* is every entry in the root list also in the root_table? */
1407                         for(e1 = c1->root; e1; e1=e1->next)
1408                         {
1409                                 char dummy_name[1024];
1410                                 ex.exten = dummy_name;
1411                                 ex.matchcid = e1->matchcid;
1412                                 ex.cidmatch = e1->cidmatch;
1413                                 ast_copy_string(dummy_name, e1->exten, sizeof(dummy_name));
1414                                 e2 = ast_hashtab_lookup(c1->root_table, &ex);
1415                                 if (!e2) {
1416                                         if (e1->matchcid) {
1417                                                 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 );
1418                                         } else {
1419                                                 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 );
1420                                         }
1421                                         check_contexts_trouble();
1422                                 }
1423                         }
1424
1425                         /* is every entry in the root_table also in the root list? */ 
1426                         if (!c2->root_table) {
1427                                 if (c2->root) {
1428                                         ast_log(LOG_NOTICE,"Called from: %s:%d: No c2->root_table for context %s!\n", file, line, c2->name);
1429                                         usleep(500000);
1430                                 }
1431                         } else {
1432                                 t1 = ast_hashtab_start_traversal(c2->root_table);
1433                                 while( (e2 = ast_hashtab_next(t1)) ) {
1434                                         for(e1=c2->root;e1;e1=e1->next) {
1435                                                 if (!strcmp(e1->exten, e2->exten)) {
1436                                                         found = 1;
1437                                                         break;
1438                                                 }
1439                                         }
1440                                         if (!found) {
1441                                                 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);
1442                                                 check_contexts_trouble();
1443                                         }
1444
1445                                 }
1446                                 ast_hashtab_end_traversal(t1);
1447                         }
1448                 }
1449                 /* is every priority reflected in the peer_table at the head of the list? */
1450
1451                 /* is every entry in the root list also in the root_table? */
1452                 /* are the per-extension peer_tables in the right place? */
1453
1454                 for(e1 = c2->root; e1; e1 = e1->next) {
1455
1456                         for(e2=e1;e2;e2=e2->peer) {
1457                                 ex.priority = e2->priority;
1458                                 if (e2 != e1 && e2->peer_table) {
1459                                         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 );
1460                                         check_contexts_trouble();
1461                                 }
1462
1463                                 if (e2 != e1 && e2->peer_label_table) {
1464                                         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 );
1465                                         check_contexts_trouble();
1466                                 }
1467
1468                                 if (e2 == e1 && !e2->peer_table){
1469                                         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 );
1470                                         check_contexts_trouble();
1471                                 }
1472
1473                                 if (e2 == e1 && !e2->peer_label_table) {
1474                                         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 );
1475                                         check_contexts_trouble();
1476                                 }
1477
1478
1479                                 e3 = ast_hashtab_lookup(e1->peer_table, &ex);
1480                                 if (!e3) {
1481                                         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 );
1482                                         check_contexts_trouble();
1483                                 }
1484                         }
1485
1486                         if (!e1->peer_table){
1487                                 ast_log(LOG_NOTICE,"Called from: %s:%d: No e1->peer_table!\n", file, line);
1488                                 usleep(500000);
1489                         }
1490
1491                         /* is every entry in the peer_table also in the peer list? */
1492                         t1 = ast_hashtab_start_traversal(e1->peer_table);
1493                         while( (e2 = ast_hashtab_next(t1)) ) {
1494                                 for(e3=e1;e3;e3=e3->peer) {
1495                                         if (e3->priority == e2->priority) {
1496                                                 found = 1;
1497                                                 break;
1498                                         }
1499                                 }
1500                                 if (!found) {
1501                                         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 );
1502                                         check_contexts_trouble();
1503                                 }
1504                         }
1505                         ast_hashtab_end_traversal(t1);
1506                 }
1507         }
1508         return 0;
1509 }
1510 #endif
1511
1512 /*
1513    \note This function is special. It saves the stack so that no matter
1514    how many times it is called, it returns to the same place */
1515 int pbx_exec(struct ast_channel *c,     /*!< Channel */
1516              struct ast_app *app,       /*!< Application */
1517              const char *data)          /*!< Data for execution */
1518 {
1519         int res;
1520         struct ast_module_user *u = NULL;
1521         const char *saved_c_appl;
1522         const char *saved_c_data;
1523
1524         if (c->cdr && !ast_check_hangup(c))
1525                 ast_cdr_setapp(c->cdr, app->name, data);
1526
1527         /* save channel values */
1528         saved_c_appl= c->appl;
1529         saved_c_data= c->data;
1530
1531         c->appl = app->name;
1532         c->data = data;
1533         ast_cel_report_event(c, AST_CEL_APP_START, NULL, NULL, NULL);
1534
1535         if (app->module)
1536                 u = __ast_module_user_add(app->module, c);
1537         if (strcasecmp(app->name, "system") && !ast_strlen_zero(data) &&
1538                         strchr(data, '|') && !strchr(data, ',') && !ast_opt_dont_warn) {
1539                 ast_log(LOG_WARNING, "The application delimiter is now the comma, not "
1540                         "the pipe.  Did you forget to convert your dialplan?  (%s(%s))\n",
1541                         app->name, (char *) data);
1542         }
1543         res = app->execute(c, S_OR(data, ""));
1544         if (app->module && u)
1545                 __ast_module_user_remove(app->module, u);
1546         ast_cel_report_event(c, AST_CEL_APP_END, NULL, NULL, NULL);
1547         /* restore channel values */
1548         c->appl = saved_c_appl;
1549         c->data = saved_c_data;
1550         return res;
1551 }
1552
1553
1554 /*! Go no deeper than this through includes (not counting loops) */
1555 #define AST_PBX_MAX_STACK       128
1556
1557 /*! \brief Find application handle in linked list
1558  */
1559 struct ast_app *pbx_findapp(const char *app)
1560 {
1561         struct ast_app *tmp;
1562
1563         AST_RWLIST_RDLOCK(&apps);
1564         AST_RWLIST_TRAVERSE(&apps, tmp, list) {
1565                 if (!strcasecmp(tmp->name, app))
1566                         break;
1567         }
1568         AST_RWLIST_UNLOCK(&apps);
1569
1570         return tmp;
1571 }
1572
1573 static struct ast_switch *pbx_findswitch(const char *sw)
1574 {
1575         struct ast_switch *asw;
1576
1577         AST_RWLIST_RDLOCK(&switches);
1578         AST_RWLIST_TRAVERSE(&switches, asw, list) {
1579                 if (!strcasecmp(asw->name, sw))
1580                         break;
1581         }
1582         AST_RWLIST_UNLOCK(&switches);
1583
1584         return asw;
1585 }
1586
1587 static inline int include_valid(struct ast_include *i)
1588 {
1589         if (!i->hastime)
1590                 return 1;
1591
1592         return ast_check_timing(&(i->timing));
1593 }
1594
1595 static void pbx_destroy(struct ast_pbx *p)
1596 {
1597         ast_free(p);
1598 }
1599
1600 /* form a tree that fully describes all the patterns in a context's extensions
1601  * in this tree, a "node" represents an individual character or character set
1602  * meant to match the corresponding character in a dial string. The tree
1603  * consists of a series of match_char structs linked in a chain
1604  * via the alt_char pointers. More than one pattern can share the same parts of the
1605  * tree as other extensions with the same pattern to that point.
1606  * My first attempt to duplicate the finding of the 'best' pattern was flawed in that
1607  * I misunderstood the general algorithm. I thought that the 'best' pattern
1608  * was the one with lowest total score. This was not true. Thus, if you have
1609  * patterns "1XXXXX" and "X11111", you would be tempted to say that "X11111" is
1610  * the "best" match because it has fewer X's, and is therefore more specific,
1611  * but this is not how the old algorithm works. It sorts matching patterns
1612  * in a similar collating sequence as sorting alphabetic strings, from left to
1613  * right. Thus, "1XXXXX" comes before "X11111", and would be the "better" match,
1614  * because "1" is more specific than "X".
1615  * So, to accomodate this philosophy, I sort the tree branches along the alt_char
1616  * line so they are lowest to highest in specificity numbers. This way, as soon
1617  * as we encounter our first complete match, we automatically have the "best"
1618  * match and can stop the traversal immediately. Same for CANMATCH/MATCHMORE.
1619  * If anyone would like to resurrect the "wrong" pattern trie searching algorithm,
1620  * they are welcome to revert pbx to before 1 Apr 2008.
1621  * As an example, consider these 4 extensions:
1622  * (a) NXXNXXXXXX
1623  * (b) 307754XXXX
1624  * (c) fax
1625  * (d) NXXXXXXXXX
1626  *
1627  * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
1628  * most numbers. For all numbers beginning with 307754, (b) should always win.
1629  *
1630  * These pattern should form a (sorted) tree that looks like this:
1631  *   { "3" }  --next-->  { "0" }  --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
1632  *      |
1633  *      |alt
1634  *      |
1635  *   { "f" }  --next-->  { "a" }  --next--> { "x"  exten_match: (c) }
1636  *   { "N" }  --next-->  { "X" }  --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
1637  *      |                                                        |
1638  *      |                                                        |alt
1639  *      |alt                                                     |
1640  *      |                                                     { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
1641  *      |
1642  *     NULL
1643  *
1644  *   In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
1645  *   fewer CPU cycles than a call to strchr("23456789",*z), where *z is the char to match...
1646  *
1647  *   traversal is pretty simple: one routine merely traverses the alt list, and for each matching char in the pattern,  it calls itself
1648  *   on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
1649  *   We pass a pointer to a scoreboard down through, also.
1650  *   The scoreboard isn't as necessary to the revised algorithm, but I kept it as a handy way to return the matched extension.
1651  *   The first complete match ends the traversal, which should make this version of the pattern matcher faster
1652  *   the previous. The same goes for "CANMATCH" or "MATCHMORE"; the first such match ends the traversal. In both
1653  *   these cases, the reason we can stop immediately, is because the first pattern match found will be the "best"
1654  *   according to the sort criteria.
1655  *   Hope the limit on stack depth won't be a problem... this routine should
1656  *   be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
1657  *
1658  *   In the above example, with the number "3077549999" as the pattern, the traversor could match extensions a, b and d.  All are
1659  *   of length 10; they have total specificities of  24580, 10246, and 25090, respectively, not that this matters
1660  *   at all. (b) wins purely because the first character "3" is much more specific (lower specificity) than "N". I have
1661  *   left the specificity totals in the code as an artifact; at some point, I will strip it out.
1662  *
1663  *   Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown,
1664  *   because it's a function of how many extensions are stored in a context. With thousands of extensions, the speedup
1665  *   can be very noticeable. The new matching algorithm can run several hundreds of times faster, if not a thousand or
1666  *   more times faster in extreme cases.
1667  *
1668  *   MatchCID patterns are also supported, and stored in the tree just as the extension pattern is. Thus, you
1669  *   can have patterns in your CID field as well.
1670  *
1671  * */
1672
1673
1674 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)
1675 {
1676         /* if this extension is marked as deleted, then skip this -- if it never shows
1677            on the scoreboard, it will never be found, nor will halt the traversal. */
1678         if (deleted)
1679                 return;
1680         board->total_specificity = spec;
1681         board->total_length = length;
1682         board->exten = exten;
1683         board->last_char = last;
1684         board->node = node;
1685 #ifdef NEED_DEBUG_HERE
1686         ast_log(LOG_NOTICE,"Scoreboarding (LONGER) %s, len=%d, score=%d\n", exten->exten, length, spec);
1687 #endif
1688 }
1689
1690 #ifdef NEED_DEBUG
1691 static void log_match_char_tree(struct match_char *node, char *prefix)
1692 {
1693         char extenstr[40];
1694         struct ast_str *my_prefix = ast_str_alloca(1024);
1695
1696         extenstr[0] = '\0';
1697
1698         if (node && node->exten)
1699                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1700
1701         if (strlen(node->x) > 1) {
1702                 ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1703                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1704                         node->exten ? node->exten->exten : "", extenstr);
1705         } else {
1706                 ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1707                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1708                         node->exten ? node->exten->exten : "", extenstr);
1709         }
1710
1711         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1712
1713         if (node->next_char)
1714                 log_match_char_tree(node->next_char, ast_str_buffer(my_prefix));
1715
1716         if (node->alt_char)
1717                 log_match_char_tree(node->alt_char, prefix);
1718 }
1719 #endif
1720
1721 static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
1722 {
1723         char extenstr[40];
1724         struct ast_str *my_prefix = ast_str_alloca(1024);
1725
1726         extenstr[0] = '\0';
1727
1728         if (node && node->exten)
1729                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1730
1731         if (strlen(node->x) > 1) {
1732                 ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1733                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1734                         node->exten ? node->exten->exten : "", extenstr);
1735         } else {
1736                 ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1737                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1738                         node->exten ? node->exten->exten : "", extenstr);
1739         }
1740
1741         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1742
1743         if (node->next_char)
1744                 cli_match_char_tree(node->next_char, ast_str_buffer(my_prefix), fd);
1745
1746         if (node->alt_char)
1747                 cli_match_char_tree(node->alt_char, prefix, fd);
1748 }
1749
1750 static struct ast_exten *get_canmatch_exten(struct match_char *node)
1751 {
1752         /* find the exten at the end of the rope */
1753         struct match_char *node2 = node;
1754
1755         for (node2 = node; node2; node2 = node2->next_char) {
1756                 if (node2->exten) {
1757 #ifdef NEED_DEBUG_HERE
1758                         ast_log(LOG_NOTICE,"CanMatch_exten returns exten %s(%p)\n", node2->exten->exten, node2->exten);
1759 #endif
1760                         return node2->exten;
1761                 }
1762         }
1763 #ifdef NEED_DEBUG_HERE
1764         ast_log(LOG_NOTICE,"CanMatch_exten returns NULL, match_char=%s\n", node->x);
1765 #endif
1766         return 0;
1767 }
1768
1769 static struct ast_exten *trie_find_next_match(struct match_char *node)
1770 {
1771         struct match_char *m3;
1772         struct match_char *m4;
1773         struct ast_exten *e3;
1774
1775         if (node && node->x[0] == '.' && !node->x[1]) { /* dot and ! will ALWAYS be next match in a matchmore */
1776                 return node->exten;
1777         }
1778
1779         if (node && node->x[0] == '!' && !node->x[1]) {
1780                 return node->exten;
1781         }
1782
1783         if (!node || !node->next_char) {
1784                 return NULL;
1785         }
1786
1787         m3 = node->next_char;
1788
1789         if (m3->exten) {
1790                 return m3->exten;
1791         }
1792         for (m4 = m3->alt_char; m4; m4 = m4->alt_char) {
1793                 if (m4->exten) {
1794                         return m4->exten;
1795                 }
1796         }
1797         for (m4 = m3; m4; m4 = m4->alt_char) {
1798                 e3 = trie_find_next_match(m3);
1799                 if (e3) {
1800                         return e3;
1801                 }
1802         }
1803
1804         return NULL;
1805 }
1806
1807 #ifdef DEBUG_THIS
1808 static char *action2str(enum ext_match_t action)
1809 {
1810         switch (action) {
1811         case E_MATCH:
1812                 return "MATCH";
1813         case E_CANMATCH:
1814                 return "CANMATCH";
1815         case E_MATCHMORE:
1816                 return "MATCHMORE";
1817         case E_FINDLABEL:
1818                 return "FINDLABEL";
1819         case E_SPAWN:
1820                 return "SPAWN";
1821         default:
1822                 return "?ACTION?";
1823         }
1824 }
1825
1826 #endif
1827
1828 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)
1829 {
1830         struct match_char *p; /* note minimal stack storage requirements */
1831         struct ast_exten pattern = { .label = label };
1832 #ifdef DEBUG_THIS
1833         if (tree)
1834                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
1835         else
1836                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
1837 #endif
1838         for (p = tree; p; p = p->alt_char) {
1839                 if (p->is_pattern) {
1840                         if (p->x[0] == 'N') {
1841                                 if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
1842 #define NEW_MATCHER_CHK_MATCH          \
1843                                         if (p->exten && !(*(str + 1))) { /* if a shorter pattern matches along the way, might as well report it */             \
1844                                                 if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */   \
1845                                                         update_scoreboard(score, length + 1, spec + p->specificity, p->exten, 0, callerid, p->deleted, p);                 \
1846                                                         if (!p->deleted) {                                                                                           \
1847                                                                 if (action == E_FINDLABEL) {                                                                             \
1848                                                                         if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) {                                  \
1849                                                                                 ast_debug(4, "Found label in preferred extension\n");                                            \
1850                                                                                 return;                                                                                          \
1851                                                                         }                                                                                                    \
1852                                                                 } else {                                                                                                 \
1853                                                                         ast_debug(4, "returning an exact match-- first found-- %s\n", p->exten->exten);                       \
1854                                                                         return; /* the first match, by definition, will be the best, because of the sorted tree */           \
1855                                                                 }                                                                                                        \
1856                                                         }                                                                                                            \
1857                                                 }                                                                                                                \
1858                                         }
1859
1860 #define NEW_MATCHER_RECURSE                \
1861                                         if (p->next_char && (*(str + 1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)                 \
1862                                                        || p->next_char->x[0] == '!')) {                                          \
1863                                                 if (*(str + 1) || p->next_char->x[0] == '!') {                                                         \
1864                                                         new_find_extension(str + 1, score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
1865                                                         if (score->exten)  {                                                                             \
1866                                                         ast_debug(4 ,"returning an exact match-- %s\n", score->exten->exten);                         \
1867                                                                 return; /* the first match is all we need */                                                 \
1868                                                         }                                                                                                                                                \
1869                                                 } else {                                                                                             \
1870                                                         new_find_extension("/", score, p->next_char, length + 1, spec + p->specificity, callerid, label, action);        \
1871                                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {      \
1872                                                         ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->exten :     \
1873                                                "NULL");                                                                        \
1874                                                                 return; /* the first match is all we need */                                                 \
1875                                                         }                                                                                                                                                \
1876                                                 }                                                                                                    \
1877                                         } else if (p->next_char && !*(str + 1)) {                                                                  \
1878                                                 score->canmatch = 1;                                                                                 \
1879                                                 score->canmatch_exten = get_canmatch_exten(p);                                                       \
1880                                                 if (action == E_CANMATCH || action == E_MATCHMORE) {                                                 \
1881                                                 ast_debug(4, "returning a canmatch/matchmore--- str=%s\n", str);                                  \
1882                                                         return;                                                                                          \
1883                                                 }                                                                                                                                                    \
1884                                         }
1885
1886                                         NEW_MATCHER_CHK_MATCH;
1887                                         NEW_MATCHER_RECURSE;
1888                                 }
1889                         } else if (p->x[0] == 'Z') {
1890                                 if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
1891                                         NEW_MATCHER_CHK_MATCH;
1892                                         NEW_MATCHER_RECURSE;
1893                                 }
1894                         } else if (p->x[0] == 'X') {
1895                                 if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1896                                         NEW_MATCHER_CHK_MATCH;
1897                                         NEW_MATCHER_RECURSE;
1898                                 }
1899                         } else if (p->x[0] == '.' && p->x[1] == 0) {
1900                                 /* how many chars will the . match against? */
1901                                 int i = 0;
1902                                 const char *str2 = str;
1903                                 while (*str2 && *str2 != '/') {
1904                                         str2++;
1905                                         i++;
1906                                 }
1907                                 if (p->exten && *str2 != '/') {
1908                                         update_scoreboard(score, length + i, spec + (i * p->specificity), p->exten, '.', callerid, p->deleted, p);
1909                                         if (score->exten) {
1910                                                 ast_debug(4,"return because scoreboard has a match with '/'--- %s\n", score->exten->exten);
1911                                                 return; /* the first match is all we need */
1912                                         }
1913                                 }
1914                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1915                                         new_find_extension("/", score, p->next_char, length + i, spec+(p->specificity*i), callerid, label, action);
1916                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1917                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set--- %s\n", score->exten ? score->exten->exten : "NULL");
1918                                                 return; /* the first match is all we need */
1919                                         }
1920                                 }
1921                         } else if (p->x[0] == '!' && p->x[1] == 0) {
1922                                 /* how many chars will the . match against? */
1923                                 int i = 1;
1924                                 const char *str2 = str;
1925                                 while (*str2 && *str2 != '/') {
1926                                         str2++;
1927                                         i++;
1928                                 }
1929                                 if (p->exten && *str2 != '/') {
1930                                         update_scoreboard(score, length + 1, spec + (p->specificity * i), p->exten, '!', callerid, p->deleted, p);
1931                                         if (score->exten) {
1932                                                 ast_debug(4, "return because scoreboard has a '!' match--- %s\n", score->exten->exten);
1933                                                 return; /* the first match is all we need */
1934                                         }
1935                                 }
1936                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1937                                         new_find_extension("/", score, p->next_char, length + i, spec + (p->specificity * i), callerid, label, action);
1938                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1939                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n", score->exten ? score->exten->exten : "NULL");
1940                                                 return; /* the first match is all we need */
1941                                         }
1942                                 }
1943                         } else if (p->x[0] == '/' && p->x[1] == 0) {
1944                                 /* the pattern in the tree includes the cid match! */
1945                                 if (p->next_char && callerid && *callerid) {
1946                                         new_find_extension(callerid, score, p->next_char, length + 1, spec, callerid, label, action);
1947                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1948                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n", score->exten ? score->exten->exten : "NULL");
1949                                                 return; /* the first match is all we need */
1950                                         }
1951                                 }
1952                         } else if (strchr(p->x, *str)) {
1953                                 ast_debug(4, "Nothing strange about this match\n");
1954                                 NEW_MATCHER_CHK_MATCH;
1955                                 NEW_MATCHER_RECURSE;
1956                         }
1957                 } else if (strchr(p->x, *str)) {
1958                         ast_debug(4, "Nothing strange about this match\n");
1959                         NEW_MATCHER_CHK_MATCH;
1960                         NEW_MATCHER_RECURSE;
1961                 }
1962         }
1963         ast_debug(4, "return at end of func\n");
1964 }
1965
1966 /* the algorithm for forming the extension pattern tree is also a bit simple; you
1967  * traverse all the extensions in a context, and for each char of the extension,
1968  * you see if it exists in the tree; if it doesn't, you add it at the appropriate
1969  * spot. What more can I say? At the end of each exten, you cap it off by adding the
1970  * address of the extension involved. Duplicate patterns will be complained about.
1971  *
1972  * Ideally, this would be done for each context after it is created and fully
1973  * filled. It could be done as a finishing step after extensions.conf or .ael is
1974  * loaded, or it could be done when the first search is encountered. It should only
1975  * have to be done once, until the next unload or reload.
1976  *
1977  * I guess forming this pattern tree would be analogous to compiling a regex. Except
1978  * that a regex only handles 1 pattern, really. This trie holds any number
1979  * of patterns. Well, really, it **could** be considered a single pattern,
1980  * where the "|" (or) operator is allowed, I guess, in a way, sort of...
1981  */
1982
1983 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern)
1984 {
1985         struct match_char *t;
1986
1987         if (!current) {
1988                 return 0;
1989         }
1990
1991         for (t = current; t; t = t->alt_char) {
1992                 if (is_pattern == t->is_pattern && !strcmp(pat, t->x)) {/* uh, we may want to sort exploded [] contents to make matching easy */
1993                         return t;
1994                 }
1995         }
1996
1997         return 0;
1998 }
1999
2000 /* The first arg is the location of the tree ptr, or the
2001    address of the next_char ptr in the node, so we can mess
2002    with it, if we need to insert at the beginning of the list */
2003
2004 static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, struct match_char *node)
2005 {
2006         struct match_char *curr, *lcurr;
2007
2008         /* insert node into the tree at "current", so the alt_char list from current is
2009            sorted in increasing value as you go to the leaves */
2010         if (!(*parent_ptr)) {
2011                 *parent_ptr = node;
2012                 return;
2013         }
2014
2015         if ((*parent_ptr)->specificity > node->specificity) {
2016                 /* insert at head */
2017                 node->alt_char = (*parent_ptr);
2018                 *parent_ptr = node;
2019                 return;
2020         } 
2021
2022         lcurr = *parent_ptr;
2023         for (curr = (*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
2024                 if (curr->specificity > node->specificity) {
2025                         node->alt_char = curr;
2026                         lcurr->alt_char = node;
2027                         break;
2028                 }
2029                 lcurr = curr;
2030         }
2031
2032         if (!curr) {
2033                 lcurr->alt_char = node;
2034         }
2035
2036 }
2037
2038 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)
2039 {
2040         struct match_char *m;
2041         
2042         if (!(m = ast_calloc(1, sizeof(*m) + strlen(pattern)))) {
2043                 return NULL;
2044         }
2045
2046         /* strcpy is safe here since we know its size and have allocated
2047          * just enough space for when we allocated m
2048          */
2049         strcpy(m->x, pattern);
2050
2051         /* the specificity scores are the same as used in the old
2052            pattern matcher. */
2053         m->is_pattern = is_pattern;
2054         if (specificity == 1 && is_pattern && pattern[0] == 'N')
2055                 m->specificity = 0x0832;
2056         else if (specificity == 1 && is_pattern && pattern[0] == 'Z')
2057                 m->specificity = 0x0931;
2058         else if (specificity == 1 && is_pattern && pattern[0] == 'X')
2059                 m->specificity = 0x0a30;
2060         else if (specificity == 1 && is_pattern && pattern[0] == '.')
2061                 m->specificity = 0x18000;
2062         else if (specificity == 1 && is_pattern && pattern[0] == '!')
2063                 m->specificity = 0x28000;
2064         else
2065                 m->specificity = specificity;
2066
2067         if (!con->pattern_tree) {
2068                 insert_in_next_chars_alt_char_list(&con->pattern_tree, m);
2069         } else {
2070                 if (already) { /* switch to the new regime (traversing vs appending)*/
2071                         insert_in_next_chars_alt_char_list(nextcharptr, m);
2072                 } else {
2073                         insert_in_next_chars_alt_char_list(&current->next_char, m);
2074                 }
2075         }
2076
2077         return m;
2078 }
2079
2080 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
2081 {
2082         struct match_char *m1 = NULL, *m2 = NULL, **m0;
2083         int specif;
2084         int already;
2085         int pattern = 0;
2086         char buf[256];
2087         char extenbuf[512];
2088         char *s1 = extenbuf;
2089         int l1 = strlen(e1->exten) + strlen(e1->cidmatch) + 2;
2090
2091
2092         ast_copy_string(extenbuf, e1->exten, sizeof(extenbuf));
2093
2094         if (e1->matchcid &&  l1 <= sizeof(extenbuf)) {
2095                 strcat(extenbuf, "/");
2096                 strcat(extenbuf, e1->cidmatch);
2097         } else if (l1 > sizeof(extenbuf)) {
2098                 ast_log(LOG_ERROR, "The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n", e1->exten, e1->cidmatch);
2099                 return 0;
2100         }
2101 #ifdef NEED_DEBUG
2102         ast_debug(1, "Adding exten %s%c%s to tree\n", s1, e1->matchcid ? '/' : ' ', e1->matchcid ? e1->cidmatch : "");
2103 #endif
2104         m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
2105         m0 = &con->pattern_tree;
2106         already = 1;
2107
2108         if ( *s1 == '_') {
2109                 pattern = 1;
2110                 s1++;
2111         }
2112         while (*s1) {
2113                 if (pattern && *s1 == '[' && *(s1 - 1) != '\\') {
2114                         char *s2 = buf;
2115                         buf[0] = 0;
2116                         s1++; /* get past the '[' */
2117                         while (*s1 != ']' && *(s1 - 1) != '\\') {
2118                                 if (*s1 == '\\') {
2119                                         if (*(s1 + 1) == ']') {
2120                                                 *s2++ = ']';
2121                                                 s1 += 2;
2122                                         } else if (*(s1 + 1) == '\\') {
2123                                                 *s2++ = '\\';
2124                                                 s1 += 2;
2125                                         } else if (*(s1 + 1) == '-') {
2126                                                 *s2++ = '-';
2127                                                 s1 += 2;
2128                                         } else if (*(s1 + 1) == '[') {
2129                                                 *s2++ = '[';
2130                                                 s1 += 2;
2131                                         }
2132                                 } else if (*s1 == '-') { /* remember to add some error checking to all this! */
2133                                         char s3 = *(s1 - 1);
2134                                         char s4 = *(s1 + 1);
2135                                         for (s3++; s3 <= s4; s3++) {
2136                                                 *s2++ = s3;
2137                                         }
2138                                         s1 += 2;
2139                                 } else if (*s1 == '\0') {
2140                                         ast_log(LOG_WARNING, "A matching ']' was not found for '[' in pattern string '%s'\n", extenbuf);
2141                                         break;
2142                                 } else {
2143                                         *s2++ = *s1++;
2144                                 }
2145                         }
2146                         *s2 = 0; /* null terminate the exploded range */
2147                         /* sort the characters */
2148
2149                         specif = strlen(buf);
2150                         qsort(buf, specif, 1, compare_char);
2151                         specif <<= 8;
2152                         specif += buf[0];
2153                 } else if (*s1 == '-') {
2154                         /* Skip dashes in patterns */
2155                         s1++;
2156                         continue;
2157                 } else {
2158                         if (*s1 == '\\') {
2159                                 s1++;
2160                                 buf[0] = *s1;
2161                         } else {
2162                                 if (pattern) {
2163                                         if (*s1 == 'n') { /* make sure n,x,z patterns are canonicalized to N,X,Z */
2164                                                 *s1 = 'N';
2165                                         } else if (*s1 == 'x') {
2166                                                 *s1 = 'X';
2167                                         } else if (*s1 == 'z') {
2168                                                 *s1 = 'Z';
2169                                         }
2170                                 }
2171                                 buf[0] = *s1;
2172                         }
2173                         buf[1] = 0;
2174                         specif = 1;
2175                 }
2176                 m2 = 0;
2177                 if (already && (m2 = already_in_tree(m1, buf, pattern)) && m2->next_char) {
2178                         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...
2179                                                                 a shorter pattern might win if the longer one doesn't match */
2180                                 if (m2->exten) {
2181                                         ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n", m2->exten->exten, e1->exten);
2182                                 }
2183                                 m2->exten = e1;
2184                                 m2->deleted = 0;
2185                         }
2186                         m1 = m2->next_char; /* m1 points to the node to compare against */
2187                         m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
2188                 } else { /* not already OR not m2 OR nor m2->next_char */
2189                         if (m2) {
2190                                 if (findonly) {
2191                                         return m2;
2192                                 }
2193                                 m1 = m2; /* while m0 stays the same */
2194                         } else {
2195                                 if (findonly) {
2196                                         return m1;
2197                                 }
2198                                 if (!(m1 = add_pattern_node(con, m1, buf, pattern, already,specif, m0))) { /* m1 is the node just added */
2199                                         return NULL;
2200                                 }
2201                                 m0 = &m1->next_char;
2202                         }
2203                         if (!(*(s1 + 1))) {
2204                                 if (m2 && m2->exten) {
2205                                         ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n", m2->exten->exten, e1->exten);
2206                                 }
2207                                 m1->deleted = 0;
2208                                 m1->exten = e1;
2209                         }
2210
2211                         /* The 'already' variable is a mini-optimization designed to make it so that we
2212                          * don't have to call already_in_tree when we know it will return false.
2213                          */
2214                         already = 0;
2215                 }
2216                 s1++; /* advance to next char */
2217         }
2218         return m1;
2219 }
2220
2221 static void create_match_char_tree(struct ast_context *con)
2222 {
2223         struct ast_hashtab_iter *t1;
2224         struct ast_exten *e1;
2225 #ifdef NEED_DEBUG
2226         int biggest_bucket, resizes, numobjs, numbucks;
2227
2228         ast_debug(1, "Creating Extension Trie for context %s(%p)\n", con->name, con);
2229         ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
2230         ast_debug(1, "This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
2231                         numobjs, numbucks, biggest_bucket, resizes);
2232 #endif
2233         t1 = ast_hashtab_start_traversal(con->root_table);
2234         while ((e1 = ast_hashtab_next(t1))) {
2235                 if (e1->exten) {
2236                         add_exten_to_pattern_tree(con, e1, 0);
2237                 } else {
2238                         ast_log(LOG_ERROR, "Attempt to create extension with no extension name.\n");
2239                 }
2240         }
2241         ast_hashtab_end_traversal(t1);
2242 }
2243
2244 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! */
2245 {
2246         /* destroy all the alternates */
2247         if (pattern_tree->alt_char) {
2248                 destroy_pattern_tree(pattern_tree->alt_char);
2249                 pattern_tree->alt_char = 0;
2250         }
2251         /* destroy all the nexts */
2252         if (pattern_tree->next_char) {
2253                 destroy_pattern_tree(pattern_tree->next_char);
2254                 pattern_tree->next_char = 0;
2255         }
2256         pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
2257         ast_free(pattern_tree);
2258 }
2259
2260 /*
2261  * Special characters used in patterns:
2262  *      '_'     underscore is the leading character of a pattern.
2263  *              In other position it is treated as a regular char.
2264  *      .       one or more of any character. Only allowed at the end of
2265  *              a pattern.
2266  *      !       zero or more of anything. Also impacts the result of CANMATCH
2267  *              and MATCHMORE. Only allowed at the end of a pattern.
2268  *              In the core routine, ! causes a match with a return code of 2.
2269  *              In turn, depending on the search mode: (XXX check if it is implemented)
2270  *              - E_MATCH retuns 1 (does match)
2271  *              - E_MATCHMORE returns 0 (no match)
2272  *              - E_CANMATCH returns 1 (does match)
2273  *
2274  *      /       should not appear as it is considered the separator of the CID info.
2275  *              XXX at the moment we may stop on this char.
2276  *
2277  *      X Z N   match ranges 0-9, 1-9, 2-9 respectively.
2278  *      [       denotes the start of a set of character. Everything inside
2279  *              is considered literally. We can have ranges a-d and individual
2280  *              characters. A '[' and '-' can be considered literally if they
2281  *              are just before ']'.
2282  *              XXX currently there is no way to specify ']' in a range, nor \ is
2283  *              considered specially.
2284  *
2285  * When we compare a pattern with a specific extension, all characters in the extension
2286  * itself are considered literally.
2287  * XXX do we want to consider space as a separator as well ?
2288  * XXX do we want to consider the separators in non-patterns as well ?
2289  */
2290
2291 /*!
2292  * \brief helper functions to sort extensions and patterns in the desired way,
2293  * so that more specific patterns appear first.
2294  *
2295  * ext_cmp1 compares individual characters (or sets of), returning
2296  * an int where bits 0-7 are the ASCII code of the first char in the set,
2297  * while bit 8-15 are the cardinality of the set minus 1.
2298  * This way more specific patterns (smaller cardinality) appear first.
2299  * Wildcards have a special value, so that we can directly compare them to
2300  * sets by subtracting the two values. In particular:
2301  *  0x000xx             one character, xx
2302  *  0x0yyxx             yy character set starting with xx
2303  *  0x10000             '.' (one or more of anything)
2304  *  0x20000             '!' (zero or more of anything)
2305  *  0x30000             NUL (end of string)
2306  *  0x40000             error in set.
2307  * The pointer to the string is advanced according to needs.
2308  * NOTES:
2309  *      1. the empty set is equivalent to NUL.
2310  *      2. given that a full set has always 0 as the first element,
2311  *         we could encode the special cases as 0xffXX where XX
2312  *         is 1, 2, 3, 4 as used above.
2313  */
2314 static int ext_cmp1(const char **p, unsigned char *bitwise)
2315 {
2316         int c, cmin = 0xff, count = 0;
2317         const char *end;
2318
2319         /* load value and advance pointer */
2320         c = *(*p)++;
2321
2322         /* always return unless we have a set of chars */
2323         switch (toupper(c)) {
2324         default:        /* ordinary character */
2325                 bitwise[c / 8] = 1 << (c % 8);
2326                 return 0x0100 | (c & 0xff);
2327
2328         case 'N':       /* 2..9 */
2329                 bitwise[6] = 0xfc;
2330                 bitwise[7] = 0x03;
2331                 return 0x0800 | '2';
2332
2333         case 'X':       /* 0..9 */
2334                 bitwise[6] = 0xff;
2335                 bitwise[7] = 0x03;
2336                 return 0x0A00 | '0';
2337
2338         case 'Z':       /* 1..9 */
2339                 bitwise[6] = 0xfe;
2340                 bitwise[7] = 0x03;
2341                 return 0x0900 | '1';
2342
2343         case '.':       /* wildcard */
2344                 return 0x18000;
2345
2346         case '!':       /* earlymatch */
2347                 return 0x28000; /* less specific than NULL */
2348
2349         case '\0':      /* empty string */
2350                 *p = NULL;
2351                 return 0x30000;
2352
2353         case '[':       /* pattern */
2354                 break;
2355         }
2356         /* locate end of set */
2357         end = strchr(*p, ']');
2358
2359         if (end == NULL) {
2360                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2361                 return 0x40000; /* XXX make this entry go last... */
2362         }
2363
2364         for (; *p < end  ; (*p)++) {
2365                 unsigned char c1, c2;   /* first-last char in range */
2366                 c1 = (unsigned char)((*p)[0]);
2367                 if (*p + 2 < end && (*p)[1] == '-') { /* this is a range */
2368                         c2 = (unsigned char)((*p)[2]);
2369                         *p += 2;    /* skip a total of 3 chars */
2370                 } else {        /* individual character */
2371                         c2 = c1;
2372                 }
2373                 if (c1 < cmin) {
2374                         cmin = c1;
2375                 }
2376                 for (; c1 <= c2; c1++) {
2377                         unsigned char mask = 1 << (c1 % 8);
2378                         /*!\note If two patterns score the same, the one with the lowest
2379                          * ascii values will compare as coming first. */
2380                         /* Flag the character as included (used) and count it. */
2381                         if (!(bitwise[ c1 / 8 ] & mask)) {
2382                                 bitwise[ c1 / 8 ] |= mask;
2383                                 count += 0x100;
2384                         }
2385                 }
2386         }
2387         (*p)++;
2388         return count == 0 ? 0x30000 : (count | cmin);
2389 }
2390
2391 /*!
2392  * \brief the full routine to compare extensions in rules.
2393  */
2394 static int ext_cmp(const char *a, const char *b)
2395 {
2396         /* make sure non-patterns come first.
2397          * If a is not a pattern, it either comes first or
2398          * we do a more complex pattern comparison.
2399          */
2400         int ret = 0;
2401
2402         if (a[0] != '_')
2403                 return (b[0] == '_') ? -1 : strcmp(a, b);
2404
2405         /* Now we know a is a pattern; if b is not, a comes first */
2406         if (b[0] != '_')
2407                 return 1;
2408
2409         /* ok we need full pattern sorting routine.
2410          * skip past the underscores */
2411         ++a; ++b;
2412         do {
2413                 unsigned char bitwise[2][32] = { { 0, } };
2414                 ret = ext_cmp1(&a, bitwise[0]) - ext_cmp1(&b, bitwise[1]);
2415                 if (ret == 0) {
2416                         /* Are the classes different, even though they score the same? */
2417                         ret = memcmp(bitwise[0], bitwise[1], 32);
2418                 }
2419         } while (!ret && a && b);
2420         if (ret == 0) {
2421                 return 0;
2422         } else {
2423                 return (ret > 0) ? 1 : -1;
2424         }
2425 }
2426
2427 int ast_extension_cmp(const char *a, const char *b)
2428 {
2429         return ext_cmp(a, b);
2430 }
2431
2432 /*!
2433  * \internal
2434  * \brief used ast_extension_{match|close}
2435  * mode is as follows:
2436  *      E_MATCH         success only on exact match
2437  *      E_MATCHMORE     success only on partial match (i.e. leftover digits in pattern)
2438  *      E_CANMATCH      either of the above.
2439  * \retval 0 on no-match
2440  * \retval 1 on match
2441  * \retval 2 on early match.
2442  */
2443
2444 static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2445 {
2446         mode &= E_MATCH_MASK;   /* only consider the relevant bits */
2447
2448 #ifdef NEED_DEBUG_HERE
2449         ast_log(LOG_NOTICE,"match core: pat: '%s', dat: '%s', mode=%d\n", pattern, data, (int)mode);
2450 #endif
2451
2452         if ( (mode == E_MATCH) && (pattern[0] == '_') && (!strcasecmp(pattern,data)) ) { /* note: if this test is left out, then _x. will not match _x. !!! */
2453 #ifdef NEED_DEBUG_HERE
2454                 ast_log(LOG_NOTICE,"return (1) - pattern matches pattern\n");
2455 #endif
2456                 return 1;
2457         }
2458
2459         if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
2460                 int ld = strlen(data), lp = strlen(pattern);
2461
2462                 if (lp < ld) {          /* pattern too short, cannot match */
2463 #ifdef NEED_DEBUG_HERE
2464                         ast_log(LOG_NOTICE,"return (0) - pattern too short, cannot match\n");
2465 #endif
2466                         return 0;
2467                 }
2468                 /* depending on the mode, accept full or partial match or both */
2469                 if (mode == E_MATCH) {
2470 #ifdef NEED_DEBUG_HERE
2471                         ast_log(LOG_NOTICE,"return (!strcmp(%s,%s) when mode== E_MATCH)\n", pattern, data);
2472 #endif
2473                         return !strcmp(pattern, data); /* 1 on match, 0 on fail */
2474                 }
2475                 if (ld == 0 || !strncasecmp(pattern, data, ld)) { /* partial or full match */
2476 #ifdef NEED_DEBUG_HERE
2477                         ast_log(LOG_NOTICE,"return (mode(%d) == E_MATCHMORE ? lp(%d) > ld(%d) : 1)\n", mode, lp, ld);
2478 #endif
2479                         return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
2480                 } else {
2481 #ifdef NEED_DEBUG_HERE
2482                         ast_log(LOG_NOTICE,"return (0) when ld(%d) > 0 && pattern(%s) != data(%s)\n", ld, pattern, data);
2483 #endif
2484                         return 0;
2485                 }
2486         }
2487         pattern++; /* skip leading _ */
2488         /*
2489          * XXX below we stop at '/' which is a separator for the CID info. However we should
2490          * not store '/' in the pattern at all. When we insure it, we can remove the checks.
2491          */
2492         while (*data && *pattern && *pattern != '/') {
2493                 const char *end;
2494
2495                 if (*data == '-') { /* skip '-' in data (just a separator) */
2496                         data++;
2497                         continue;
2498                 }
2499                 switch (toupper(*pattern)) {
2500                 case '[':       /* a range */
2501                         end = strchr(pattern+1, ']'); /* XXX should deal with escapes ? */
2502                         if (end == NULL) {
2503                                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2504                                 return 0;       /* unconditional failure */
2505                         }
2506                         for (pattern++; pattern != end; pattern++) {
2507                                 if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
2508                                         if (*data >= pattern[0] && *data <= pattern[2])
2509                                                 break;  /* match found */
2510                                         else {
2511                                                 pattern += 2; /* skip a total of 3 chars */
2512                                                 continue;
2513                                         }
2514                                 } else if (*data == pattern[0])
2515                                         break;  /* match found */
2516                         }
2517                         if (pattern == end) {
2518 #ifdef NEED_DEBUG_HERE
2519                                 ast_log(LOG_NOTICE,"return (0) when pattern==end\n");
2520 #endif
2521                                 return 0;
2522                         }
2523                         pattern = end;  /* skip and continue */
2524                         break;
2525                 case 'N':
2526                         if (*data < '2' || *data > '9') {
2527 #ifdef NEED_DEBUG_HERE
2528                                 ast_log(LOG_NOTICE,"return (0) N is matched\n");
2529 #endif
2530                                 return 0;
2531                         }
2532                         break;
2533                 case 'X':
2534                         if (*data < '0' || *data > '9') {
2535 #ifdef NEED_DEBUG_HERE
2536                                 ast_log(LOG_NOTICE,"return (0) X is matched\n");
2537 #endif
2538                                 return 0;
2539                         }
2540                         break;
2541                 case 'Z':
2542                         if (*data < '1' || *data > '9') {
2543 #ifdef NEED_DEBUG_HERE
2544                                 ast_log(LOG_NOTICE,"return (0) Z is matched\n");
2545 #endif
2546                                 return 0;
2547                         }
2548                         break;
2549                 case '.':       /* Must match, even with more digits */
2550 #ifdef NEED_DEBUG_HERE
2551                         ast_log(LOG_NOTICE, "return (1) when '.' is matched\n");
2552 #endif
2553                         return 1;
2554                 case '!':       /* Early match */
2555 #ifdef NEED_DEBUG_HERE
2556                         ast_log(LOG_NOTICE, "return (2) when '!' is matched\n");
2557 #endif
2558                         return 2;
2559                 case ' ':
2560                 case '-':       /* Ignore these in patterns */
2561                         data--; /* compensate the final data++ */
2562                         break;
2563                 default:
2564                         if (*data != *pattern) {
2565 #ifdef NEED_DEBUG_HERE
2566                                 ast_log(LOG_NOTICE, "return (0) when *data(%c) != *pattern(%c)\n", *data, *pattern);
2567 #endif
2568                                 return 0;
2569                         }
2570                 }
2571                 data++;
2572                 pattern++;
2573         }
2574         if (*data)                      /* data longer than pattern, no match */ {
2575 #ifdef NEED_DEBUG_HERE
2576                 ast_log(LOG_NOTICE, "return (0) when data longer than pattern\n");
2577 #endif
2578                 return 0;
2579         }
2580
2581         /*
2582          * match so far, but ran off the end of the data.
2583          * Depending on what is next, determine match or not.
2584          */
2585         if (*pattern == '\0' || *pattern == '/') {      /* exact match */
2586 #ifdef NEED_DEBUG_HERE
2587                 ast_log(LOG_NOTICE, "at end, return (%d) in 'exact match'\n", (mode==E_MATCHMORE) ? 0 : 1);
2588 #endif
2589                 return (mode == E_MATCHMORE) ? 0 : 1;   /* this is a failure for E_MATCHMORE */
2590         } else if (*pattern == '!')     {               /* early match */
2591 #ifdef NEED_DEBUG_HERE
2592                 ast_log(LOG_NOTICE, "at end, return (2) when '!' is matched\n");
2593 #endif
2594                 return 2;
2595         } else {                                                /* partial match */
2596 #ifdef NEED_DEBUG_HERE
2597                 ast_log(LOG_NOTICE, "at end, return (%d) which deps on E_MATCH\n", (mode == E_MATCH) ? 0 : 1);
2598 #endif
2599                 return (mode == E_MATCH) ? 0 : 1;       /* this is a failure for E_MATCH */
2600         }
2601 }
2602
2603 /*
2604  * Wrapper around _extension_match_core() to do performance measurement
2605  * using the profiling code.
2606  */
2607 static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2608 {
2609         int i;
2610         static int prof_id = -2;        /* marker for 'unallocated' id */
2611         if (prof_id == -2) {
2612                 prof_id = ast_add_profile("ext_match", 0);
2613         }
2614         ast_mark(prof_id, 1);
2615         i = _extension_match_core(pattern, data, mode);
2616         ast_mark(prof_id, 0);
2617         return i;
2618 }
2619
2620 int ast_extension_match(const char *pattern, const char *data)
2621 {
2622         return extension_match_core(pattern, data, E_MATCH);
2623 }
2624
2625 int ast_extension_close(const char *pattern, const char *data, int needmore)
2626 {
2627         if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
2628                 ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
2629         return extension_match_core(pattern, data, needmore);
2630 }
2631
2632 struct fake_context /* this struct is purely for matching in the hashtab */
2633 {
2634         ast_rwlock_t lock;
2635         struct ast_exten *root;
2636         struct ast_hashtab *root_table;
2637         struct match_char *pattern_tree;
2638         struct ast_context *next;
2639         struct ast_include *includes;
2640         struct ast_ignorepat *ignorepats;
2641         const char *registrar;
2642         int refcount;
2643         AST_LIST_HEAD_NOLOCK(, ast_sw) alts;
2644         ast_mutex_t macrolock;
2645         char name[256];
2646 };
2647
2648 struct ast_context *ast_context_find(const char *name)
2649 {
2650         struct ast_context *tmp;
2651         struct fake_context item;
2652
2653         if (!name) {
2654                 return NULL;
2655         }
2656         ast_rdlock_contexts();
2657         if (contexts_table) {
2658                 ast_copy_string(item.name, name, sizeof(item.name));
2659                 tmp = ast_hashtab_lookup(contexts_table, &item);
2660         } else {
2661                 tmp = NULL;
2662                 while ((tmp = ast_walk_contexts(tmp))) {
2663                         if (!strcasecmp(name, tmp->name)) {
2664                                 break;
2665                         }
2666                 }
2667         }
2668         ast_unlock_contexts();
2669         return tmp;
2670 }
2671
2672 #define STATUS_NO_CONTEXT       1
2673 #define STATUS_NO_EXTENSION     2
2674 #define STATUS_NO_PRIORITY      3
2675 #define STATUS_NO_LABEL         4
2676 #define STATUS_SUCCESS          5
2677
2678 static int matchcid(const char *cidpattern, const char *callerid)
2679 {
2680         /* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
2681            failing to get a number should count as a match, otherwise not */
2682
2683         if (ast_strlen_zero(callerid)) {
2684                 return ast_strlen_zero(cidpattern) ? 1 : 0;
2685         }
2686
2687         return ast_extension_match(cidpattern, callerid);
2688 }
2689
2690 struct ast_exten *pbx_find_extension(struct ast_channel *chan,
2691         struct ast_context *bypass, struct pbx_find_info *q,
2692         const char *context, const char *exten, int priority,
2693         const char *label, const char *callerid, enum ext_match_t action)
2694 {
2695         int x, res;
2696         struct ast_context *tmp = NULL;
2697         struct ast_exten *e = NULL, *eroot = NULL;
2698         struct ast_include *i = NULL;
2699         struct ast_sw *sw = NULL;
2700         struct ast_exten pattern = {NULL, };
2701         struct scoreboard score = {0, };
2702         struct ast_str *tmpdata = NULL;
2703
2704         pattern.label = label;
2705         pattern.priority = priority;
2706 #ifdef NEED_DEBUG_HERE
2707         ast_log(LOG_NOTICE, "Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int) action);
2708 #endif
2709
2710         /* Initialize status if appropriate */
2711         if (q->stacklen == 0) {
2712                 q->status = STATUS_NO_CONTEXT;
2713                 q->swo = NULL;
2714                 q->data = NULL;
2715                 q->foundcontext = NULL;
2716         } else if (q->stacklen >= AST_PBX_MAX_STACK) {
2717                 ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
2718                 return NULL;
2719         }
2720
2721         /* Check first to see if we've already been checked */
2722         for (x = 0; x < q->stacklen; x++) {
2723                 if (!strcasecmp(q->incstack[x], context))
2724                         return NULL;
2725         }
2726
2727         if (bypass) { /* bypass means we only look there */
2728                 tmp = bypass;
2729         } else {      /* look in contexts */
2730                 tmp = find_context(context);
2731                 if (!tmp) {
2732                         return NULL;
2733                 }
2734         }
2735
2736         if (q->status < STATUS_NO_EXTENSION)
2737                 q->status = STATUS_NO_EXTENSION;
2738
2739         /* Do a search for matching extension */
2740
2741         eroot = NULL;
2742         score.total_specificity = 0;
2743         score.exten = 0;
2744         score.total_length = 0;
2745         if (!tmp->pattern_tree && tmp->root_table) {
2746                 create_match_char_tree(tmp);
2747 #ifdef NEED_DEBUG
2748                 ast_debug(1, "Tree Created in context %s:\n", context);
2749                 log_match_char_tree(tmp->pattern_tree," ");
2750 #endif
2751         }
2752 #ifdef NEED_DEBUG
2753         ast_log(LOG_NOTICE, "The Trie we are searching in:\n");
2754         log_match_char_tree(tmp->pattern_tree, "::  ");
2755 #endif
2756
2757         do {
2758                 if (!ast_strlen_zero(overrideswitch)) {
2759                         char *osw = ast_strdupa(overrideswitch), *name;
2760                         struct ast_switch *asw;
2761                         ast_switch_f *aswf = NULL;
2762                         char *datap;
2763                         int eval = 0;
2764
2765                         name = strsep(&osw, "/");
2766                         asw = pbx_findswitch(name);
2767
2768                         if (!asw) {
2769                                 ast_log(LOG_WARNING, "No such switch '%s'\n", name);
2770                                 break;
2771                         }
2772
2773                         if (osw && strchr(osw, '$')) {
2774                                 eval = 1;
2775                         }
2776
2777                         if (eval && !(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2778                                 ast_log(LOG_WARNING, "Can't evaluate overrideswitch?!");
2779                                 break;
2780                         } else if (eval) {
2781                                 /* Substitute variables now */
2782                                 pbx_substitute_variables_helper(chan, osw, ast_str_buffer(tmpdata), ast_str_size(tmpdata));
2783                                 datap = ast_str_buffer(tmpdata);
2784                         } else {
2785                                 datap = osw;
2786                         }
2787
2788                         /* equivalent of extension_match_core() at the switch level */
2789                         if (action == E_CANMATCH)
2790                                 aswf = asw->canmatch;
2791                         else if (action == E_MATCHMORE)
2792                                 aswf = asw->matchmore;
2793                         else /* action == E_MATCH */
2794                                 aswf = asw->exists;
2795                         if (!aswf) {
2796                                 res = 0;
2797                         } else {
2798                                 if (chan) {
2799                                         ast_autoservice_start(chan);
2800                                 }
2801                                 res = aswf(chan, context, exten, priority, callerid, datap);
2802                                 if (chan) {
2803                                         ast_autoservice_stop(chan);
2804                                 }
2805                         }
2806                         if (res) {      /* Got a match */
2807                                 q->swo = asw;
2808                                 q->data = datap;
2809                                 q->foundcontext = context;
2810                                 /* XXX keep status = STATUS_NO_CONTEXT ? */
2811                                 return NULL;
2812                         }
2813                 }
2814         } while (0);
2815
2816         if (extenpatternmatchnew) {
2817                 new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid, label, action);
2818                 eroot = score.exten;
2819
2820                 if (score.last_char == '!' && action == E_MATCHMORE) {
2821                         /* We match an extension ending in '!'.
2822                          * The decision in this case is final and is NULL (no match).
2823                          */
2824 #ifdef NEED_DEBUG_HERE
2825                         ast_log(LOG_NOTICE,"Returning MATCHMORE NULL with exclamation point.\n");
2826 #endif
2827                         return NULL;
2828                 }
2829
2830                 if (!eroot && (action == E_CANMATCH || action == E_MATCHMORE) && score.canmatch_exten) {
2831                         q->status = STATUS_SUCCESS;
2832 #ifdef NEED_DEBUG_HERE
2833                         ast_log(LOG_NOTICE,"Returning CANMATCH exten %s\n", score.canmatch_exten->exten);
2834 #endif
2835                         return score.canmatch_exten;
2836                 }
2837
2838                 if ((action == E_MATCHMORE || action == E_CANMATCH)  && eroot) {
2839                         if (score.node) {
2840                                 struct ast_exten *z = trie_find_next_match(score.node);
2841                                 if (z) {
2842 #ifdef NEED_DEBUG_HERE
2843                                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten %s\n", z->exten);
2844 #endif
2845                                 } else {
2846                                         if (score.canmatch_exten) {
2847 #ifdef NEED_DEBUG_HERE
2848                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE canmatchmatch exten %s(%p)\n", score.canmatch_exten->exten, score.canmatch_exten);
2849 #endif
2850                                                 return score.canmatch_exten;
2851                                         } else {
2852 #ifdef NEED_DEBUG_HERE
2853                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten NULL\n");
2854 #endif
2855                                         }
2856                                 }
2857                                 return z;
2858                         }
2859 #ifdef NEED_DEBUG_HERE
2860                         ast_log(LOG_NOTICE, "Returning CANMATCH/MATCHMORE NULL (no next_match)\n");
2861 #endif
2862                         return NULL;  /* according to the code, complete matches are null matches in MATCHMORE mode */
2863                 }
2864
2865                 if (eroot) {
2866                         /* found entry, now look for the right priority */
2867                         if (q->status < STATUS_NO_PRIORITY)
2868                                 q->status = STATUS_NO_PRIORITY;
2869                         e = NULL;
2870                         if (action == E_FINDLABEL && label ) {
2871                                 if (q->status < STATUS_NO_LABEL)
2872                                         q->status = STATUS_NO_LABEL;
2873                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2874                         } else {
2875                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2876                         }
2877                         if (e) {        /* found a valid match */
2878                                 q->status = STATUS_SUCCESS;
2879                                 q->foundcontext = context;
2880 #ifdef NEED_DEBUG_HERE
2881                                 ast_log(LOG_NOTICE,"Returning complete match of exten %s\n", e->exten);
2882 #endif
2883                                 return e;
2884                         }
2885                 }
2886         } else {   /* the old/current default exten pattern match algorithm */
2887
2888                 /* scan the list trying to match extension and CID */
2889                 eroot = NULL;
2890                 while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
2891                         int match = extension_match_core(eroot->exten, exten, action);
2892                         /* 0 on fail, 1 on match, 2 on earlymatch */
2893
2894                         if (!match || (eroot->matchcid && !matchcid(eroot->cidmatch, callerid)))
2895                                 continue;       /* keep trying */
2896                         if (match == 2 && action == E_MATCHMORE) {
2897                                 /* We match an extension ending in '!'.
2898                              &