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