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