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