]> git.lyx.org Git - lyx.git/blob - src/mathed/MathExtern.cpp
#include cosmetics
[lyx.git] / src / mathed / MathExtern.cpp
1 /**
2  * \file MathExtern.cpp
3  * This file is part of LyX, the document processor.
4  * Licence details can be found in the file COPYING.
5  *
6  * \author André Pönitz
7  *
8  * Full author contact details are available in file CREDITS.
9  */
10
11 // This file contains most of the magic that extracts "context
12 // information" from the unstructered layout-oriented stuff in
13 // MathData.
14
15 #include <config.h>
16
17 #include "MathExtern.h"
18
19 #include "debug.h"
20 #include "InsetMathArray.h"
21 #include "InsetMathChar.h"
22 #include "InsetMathDelim.h"
23 #include "InsetMathDiff.h"
24 #include "InsetMathExFunc.h"
25 #include "InsetMathExInt.h"
26 #include "InsetMathFont.h"
27 #include "InsetMathFrac.h"
28 #include "InsetMathLim.h"
29 #include "InsetMathMatrix.h"
30 #include "InsetMathNumber.h"
31 #include "InsetMathScript.h"
32 #include "InsetMathString.h"
33 #include "InsetMathSymbol.h"
34 #include "MathData.h"
35 #include "MathParser.h"
36 #include "MathStream.h"
37
38 #include "support/docstream.h"
39 #include "support/filetools.h"
40 #include "support/lstrings.h"
41 #include "support/lyxlib.h"
42
43 #include <algorithm>
44 #include <sstream>
45 #include <fstream>
46
47
48 namespace lyx {
49
50 using support::cmd_ret;
51 using support::getVectorFromString;
52 using support::libFileSearch;
53 using support::runCommand;
54 using support::FileName;
55 using support::quoteName;
56 using support::tempName;
57 using support::unlink;
58 using support::subst;
59
60 using std::auto_ptr;
61 using std::endl;
62 using std::find_if;
63 using std::istringstream;
64 using std::ostream;
65 using std::swap;
66 using std::string;
67 using std::vector;
68
69 static char const * function_names[] = {
70         "arccos", "arcsin", "arctan", "arg", "bmod",
71         "cos", "cosh", "cot", "coth", "csc", "deg",
72         "det", "dim", "exp", "gcd", "hom", "inf", "ker",
73         "lg", "lim", "liminf", "limsup", "ln", "log",
74         "max", "min", "sec", "sin", "sinh", "sup",
75         "tan", "tanh", "Pr", 0
76 };
77
78 static size_t const npos = lyx::docstring::npos;
79
80 // define a function for tests
81 typedef bool TestItemFunc(MathAtom const &);
82
83 // define a function for replacing subexpressions
84 typedef MathAtom ReplaceArgumentFunc(const MathData & ar);
85
86
87
88 // try to extract a super/subscript
89 // modify iterator position to point behind the thing
90 bool extractScript(MathData & ar,
91         MathData::iterator & pos, MathData::iterator last, bool superscript)
92 {
93         // nothing to get here
94         if (pos == last)
95                 return false;
96
97         // is this a scriptinset?
98         if (!(*pos)->asScriptInset())
99                 return false;
100
101         // do we want superscripts only?
102         if (superscript && !(*pos)->asScriptInset()->hasUp())
103                 return false;
104
105         // it is a scriptinset, use it.
106         ar.push_back(*pos);
107         ++pos;
108         return true;
109 }
110
111
112 // try to extract an "argument" to some function.
113 // returns position behind the argument
114 MathData::iterator extractArgument(MathData & ar,
115         MathData::iterator pos, MathData::iterator last, bool function = false)
116 {
117         // nothing to get here
118         if (pos == last)
119                 return pos;
120
121         // something delimited _is_ an argument
122         if ((*pos)->asDelimInset()) {
123                 // leave out delimiters if this is a function argument
124                 if (function) {
125                         MathData const & arg = (*pos)->asDelimInset()->cell(0);
126                         MathData::const_iterator cur = arg.begin();
127                         MathData::const_iterator end = arg.end();
128                         while (cur != end)
129                                 ar.push_back(*cur++);
130                 } else
131                         ar.push_back(*pos);
132                 ++pos;
133                 if (pos == last)
134                         return pos;
135                 // if there's one, get following superscript only if this
136                 // isn't a function argument
137                 if (!function)
138                         extractScript(ar, pos, last, true);
139                 return pos;
140         }
141
142         // always take the first thing, no matter what it is
143         ar.push_back(*pos);
144
145         // go ahead if possible
146         ++pos;
147         if (pos == last)
148                 return pos;
149
150         // if the next item is a super/subscript, it most certainly belongs
151         // to the thing we have
152         extractScript(ar, pos, last, false);
153         if (pos == last)
154                 return pos;
155
156         // but it might be more than that.
157         // FIXME: not implemented
158         //for (MathData::iterator it = pos + 1; it != last; ++it) {
159         //      // always take the first thing, no matter
160         //      if (it == pos) {
161         //              ar.push_back(*it);
162         //              continue;
163         //      }
164         //}
165         return pos;
166 }
167
168
169 // returns sequence of char with same code starting at it up to end
170 // it might be less, though...
171 docstring charSequence
172         (MathData::const_iterator it, MathData::const_iterator end)
173 {
174         docstring s;
175         for (; it != end && (*it)->asCharInset(); ++it)
176                 s += (*it)->getChar();
177         return s;
178 }
179
180
181 void extractStrings(MathData & ar)
182 {
183         //lyxerr << "\nStrings from: " << ar << endl;
184         for (size_t i = 0; i < ar.size(); ++i) {
185                 if (!ar[i]->asCharInset())
186                         continue;
187                 docstring s = charSequence(ar.begin() + i, ar.end());
188                 ar[i] = MathAtom(new InsetMathString(s));
189                 ar.erase(i + 1, i + s.size());
190         }
191         //lyxerr << "\nStrings to: " << ar << endl;
192 }
193
194
195 void extractMatrices(MathData & ar)
196 {
197         //lyxerr << "\nMatrices from: " << ar << endl;
198         // first pass for explicitly delimited stuff
199         for (size_t i = 0; i < ar.size(); ++i) {
200                 if (!ar[i]->asDelimInset())
201                         continue;
202                 MathData const & arr = ar[i]->asDelimInset()->cell(0);
203                 if (arr.size() != 1)
204                         continue;
205                 if (!arr.front()->asGridInset())
206                         continue;
207                 ar[i] = MathAtom(new InsetMathMatrix(*(arr.front()->asGridInset())));
208         }
209
210         // second pass for AMS "pmatrix" etc
211         for (size_t i = 0; i < ar.size(); ++i)
212                 if (ar[i]->asAMSArrayInset())
213                         ar[i] = MathAtom(new InsetMathMatrix(*(ar[i]->asGridInset())));
214         //lyxerr << "\nMatrices to: " << ar << endl;
215 }
216
217
218 // convert this inset somehow to a string
219 bool extractString(MathAtom const & at, docstring & str)
220 {
221         if (at->getChar()) {
222                 str = docstring(1, at->getChar());
223                 return true;
224         }
225         if (at->asStringInset()) {
226                 str = at->asStringInset()->str();
227                 return true;
228         }
229         return false;
230 }
231
232
233 // is this a known function?
234 bool isKnownFunction(docstring const & str)
235 {
236         for (int i = 0; function_names[i]; ++i) {
237                 if (str == function_names[i])
238                         return true;
239         }
240         return false;
241 }
242
243
244 // extract a function name from this inset
245 bool extractFunctionName(MathAtom const & at, docstring & str)
246 {
247         if (at->asSymbolInset()) {
248                 str = at->asSymbolInset()->name();
249                 return isKnownFunction(str);
250         }
251         if (at->asUnknownInset()) {
252                 // assume it is well known...
253                 str = at->name();
254                 return true;
255         }
256         if (at->asFontInset() && at->name() == "mathrm") {
257                 // assume it is well known...
258                 MathData const & ar = at->asFontInset()->cell(0);
259                 str = charSequence(ar.begin(), ar.end());
260                 return ar.size() == str.size();
261         }
262         return false;
263 }
264
265
266 // convert this inset somehow to a number
267 bool extractNumber(MathData const & ar, int & i)
268 {
269         idocstringstream is(charSequence(ar.begin(), ar.end()));
270         is >> i;
271         return is;
272 }
273
274
275 bool extractNumber(MathData const & ar, double & d)
276 {
277         idocstringstream is(charSequence(ar.begin(), ar.end()));
278         is >> d;
279         return is;
280 }
281
282
283 bool testString(MathAtom const & at, docstring const & str)
284 {
285         docstring s;
286         return extractString(at, s) && str == s;
287 }
288
289
290 bool testString(MathAtom const & at, char const * const str)
291 {
292         return testString(at, from_ascii(str));
293 }
294
295 // search end of nested sequence
296 MathData::iterator endNestSearch(
297         MathData::iterator it,
298         MathData::iterator last,
299         TestItemFunc testOpen,
300         TestItemFunc testClose
301 )
302 {
303         for (int level = 0; it != last; ++it) {
304                 if (testOpen(*it))
305                         ++level;
306                 if (testClose(*it))
307                         --level;
308                 if (level == 0)
309                         break;
310         }
311         return it;
312 }
313
314
315 // replace nested sequences by a real Insets
316 void replaceNested(
317         MathData & ar,
318         TestItemFunc testOpen,
319         TestItemFunc testClose,
320         ReplaceArgumentFunc replaceArg
321 )
322 {
323         // use indices rather than iterators for the loop  because we are going
324         // to modify the array.
325         for (size_t i = 0; i < ar.size(); ++i) {
326                 // check whether this is the begin of the sequence
327                 if (!testOpen(ar[i]))
328                         continue;
329
330                 // search end of sequence
331                 MathData::iterator it = ar.begin() + i;
332                 MathData::iterator jt = endNestSearch(it, ar.end(), testOpen, testClose);
333                 if (jt == ar.end())
334                         continue;
335
336                 // replace the original stuff by the new inset
337                 ar[i] = replaceArg(MathData(it + 1, jt));
338                 ar.erase(it + 1, jt + 1);
339         }
340 }
341
342
343
344 //
345 // split scripts into seperate super- and subscript insets. sub goes in
346 // front of super...
347 //
348
349 void splitScripts(MathData & ar)
350 {
351         //lyxerr << "\nScripts from: " << ar << endl;
352         for (size_t i = 0; i < ar.size(); ++i) {
353                 InsetMathScript const * script = ar[i]->asScriptInset();
354
355                 // is this a script inset and do we also have a superscript?
356                 if (!script || !script->hasUp())
357                         continue;
358
359                 // we must have a nucleus if we only have a superscript
360                 if (!script->hasDown() && script->nuc().size() == 0)
361                         continue;
362
363                 if (script->nuc().size() == 1) {
364                         // leave alone sums and integrals
365                         InsetMathSymbol const * sym =
366                                 script->nuc().front()->asSymbolInset();
367                         if (sym && (sym->name() == "sum" || sym->name() == "int"))
368                                 continue;
369                 }
370
371                 // create extra script inset and move superscript over
372                 InsetMathScript * p = ar[i].nucleus()->asScriptInset();
373                 std::auto_ptr<InsetMathScript> q(new InsetMathScript(true));
374                 swap(q->up(), p->up());
375                 p->removeScript(true);
376
377                 // if we don't have a subscript, get rid of the ScriptInset
378                 if (!script->hasDown()) {
379                         MathData arg(p->nuc());
380                         MathData::const_iterator it = arg.begin();
381                         MathData::const_iterator et = arg.end();
382                         ar.erase(i);
383                         while (it != et)
384                                 ar.insert(i++, *it++);
385                 } else
386                         ++i;
387
388                 // insert new inset behind
389                 ar.insert(i, MathAtom(q.release()));
390         }
391         //lyxerr << "\nScripts to: " << ar << endl;
392 }
393
394
395 //
396 // extract exp(...)
397 //
398
399 void extractExps(MathData & ar)
400 {
401         //lyxerr << "\nExps from: " << ar << endl;
402         for (size_t i = 0; i + 1 < ar.size(); ++i) {
403                 // is this 'e'?
404                 if (ar[i]->getChar() != 'e')
405                         continue;
406
407                 // we need an exponent but no subscript
408                 InsetMathScript const * sup = ar[i + 1]->asScriptInset();
409                 if (!sup || sup->hasDown())
410                         continue;
411
412                 // create a proper exp-inset as replacement
413                 ar[i] = MathAtom(new InsetMathExFunc(from_ascii("exp"), sup->cell(1)));
414                 ar.erase(i + 1);
415         }
416         //lyxerr << "\nExps to: " << ar << endl;
417 }
418
419
420 //
421 // extract det(...)  from |matrix|
422 //
423 void extractDets(MathData & ar)
424 {
425         //lyxerr << "\ndet from: " << ar << endl;
426         for (MathData::iterator it = ar.begin(); it != ar.end(); ++it) {
427                 InsetMathDelim const * del = (*it)->asDelimInset();
428                 if (!del)
429                         continue;
430                 if (!del->isAbs())
431                         continue;
432                 *it = MathAtom(new InsetMathExFunc(from_ascii("det"), del->cell(0)));
433         }
434         //lyxerr << "\ndet to: " << ar << endl;
435 }
436
437
438 //
439 // search numbers
440 //
441
442 bool isDigitOrSimilar(char_type c)
443 {
444         return ('0' <= c && c <= '9') || c == '.';
445 }
446
447
448 // returns sequence of digits
449 docstring digitSequence
450         (MathData::const_iterator it, MathData::const_iterator end)
451 {
452         docstring s;
453         for (; it != end && (*it)->asCharInset(); ++it) {
454                 if (!isDigitOrSimilar((*it)->getChar()))
455                         break;
456                 s += (*it)->getChar();
457         }
458         return s;
459 }
460
461
462 void extractNumbers(MathData & ar)
463 {
464         //lyxerr << "\nNumbers from: " << ar << endl;
465         for (size_t i = 0; i < ar.size(); ++i) {
466                 if (!ar[i]->asCharInset())
467                         continue;
468                 if (!isDigitOrSimilar(ar[i]->asCharInset()->getChar()))
469                         continue;
470
471                 docstring s = digitSequence(ar.begin() + i, ar.end());
472
473                 ar[i] = MathAtom(new InsetMathNumber(s));
474                 ar.erase(i + 1, i + s.size());
475         }
476         //lyxerr << "\nNumbers to: " << ar << endl;
477 }
478
479
480
481 //
482 // search delimiters
483 //
484
485 bool testOpenParen(MathAtom const & at)
486 {
487         return testString(at, "(");
488 }
489
490
491 bool testCloseParen(MathAtom const & at)
492 {
493         return testString(at, ")");
494 }
495
496
497 MathAtom replaceParenDelims(const MathData & ar)
498 {
499         return MathAtom(new InsetMathDelim(from_ascii("("), from_ascii(")"), ar));
500 }
501
502
503 bool testOpenBracket(MathAtom const & at)
504 {
505         return testString(at, "[");
506 }
507
508
509 bool testCloseBracket(MathAtom const & at)
510 {
511         return testString(at, "]");
512 }
513
514
515 MathAtom replaceBracketDelims(const MathData & ar)
516 {
517         return MathAtom(new InsetMathDelim(from_ascii("["), from_ascii("]"), ar));
518 }
519
520
521 // replace '('...')' and '['...']' sequences by a real InsetMathDelim
522 void extractDelims(MathData & ar)
523 {
524         //lyxerr << "\nDelims from: " << ar << endl;
525         replaceNested(ar, testOpenParen, testCloseParen, replaceParenDelims);
526         replaceNested(ar, testOpenBracket, testCloseBracket, replaceBracketDelims);
527         //lyxerr << "\nDelims to: " << ar << endl;
528 }
529
530
531
532 //
533 // search well-known functions
534 //
535
536
537 // replace 'f' '(...)' and 'f' '^n' '(...)' sequences by a real InsetMathExFunc
538 // assume 'extractDelims' ran before
539 void extractFunctions(MathData & ar)
540 {
541         // we need at least two items...
542         if (ar.size() < 2)
543                 return;
544
545         //lyxerr << "\nFunctions from: " << ar << endl;
546         for (size_t i = 0; i + 1 < ar.size(); ++i) {
547                 MathData::iterator it = ar.begin() + i;
548                 MathData::iterator jt = it + 1;
549
550                 docstring name;
551                 // is it a function?
552                 // it certainly is if it is well known...
553                 if (!extractFunctionName(*it, name)) {
554                         // is this a user defined function?
555                         // it it probably not, if it doesn't have a name.
556                         if (!extractString(*it, name))
557                                 continue;
558                         // it is not if it has no argument
559                         if (jt == ar.end())
560                                 continue;
561                         // guess so, if this is followed by
562                         // a DelimInset with a single item in the cell
563                         InsetMathDelim const * del = (*jt)->asDelimInset();
564                         if (!del || del->cell(0).size() != 1)
565                                 continue;
566                         // fall trough into main branch
567                 }
568
569                 // do we have an exponent like in
570                 // 'sin' '^2' 'x' -> 'sin(x)' '^2'
571                 MathData exp;
572                 extractScript(exp, jt, ar.end(), true);
573
574                 // create a proper inset as replacement
575                 std::auto_ptr<InsetMathExFunc> p(new InsetMathExFunc(name));
576
577                 // jt points to the "argument". Get hold of this.
578                 MathData::iterator st = extractArgument(p->cell(0), jt, ar.end(), true);
579
580                 // replace the function name by a real function inset
581                 *it = MathAtom(p.release());
582
583                 // remove the source of the argument from the array
584                 ar.erase(it + 1, st);
585
586                 // re-insert exponent
587                 ar.insert(i + 1, exp);
588                 //lyxerr << "\nFunctions to: " << ar << endl;
589         }
590 }
591
592
593 //
594 // search integrals
595 //
596
597 bool testSymbol(MathAtom const & at, docstring const & name)
598 {
599         return at->asSymbolInset() && at->asSymbolInset()->name() == name;
600 }
601
602
603 bool testSymbol(MathAtom const & at, char const * const name)
604 {
605         return at->asSymbolInset() && at->asSymbolInset()->name() == from_ascii(name);
606 }
607
608
609 bool testIntSymbol(MathAtom const & at)
610 {
611         return testSymbol(at, from_ascii("int"));
612 }
613
614
615 bool testIntegral(MathAtom const & at)
616 {
617         return
618          testIntSymbol(at) ||
619                 ( at->asScriptInset()
620                   && at->asScriptInset()->nuc().size()
621                         && testIntSymbol(at->asScriptInset()->nuc().back()) );
622 }
623
624
625
626 bool testIntDiff(MathAtom const & at)
627 {
628         return testString(at, "d");
629 }
630
631
632 // replace '\int' ['_^'] x 'd''x'(...)' sequences by a real InsetMathExInt
633 // assume 'extractDelims' ran before
634 void extractIntegrals(MathData & ar)
635 {
636         // we need at least three items...
637         if (ar.size() < 3)
638                 return;
639
640         //lyxerr << "\nIntegrals from: " << ar << endl;
641         for (size_t i = 0; i + 1 < ar.size(); ++i) {
642                 MathData::iterator it = ar.begin() + i;
643
644                 // search 'd'
645                 MathData::iterator jt =
646                         endNestSearch(it, ar.end(), testIntegral, testIntDiff);
647
648                 // something sensible found?
649                 if (jt == ar.end())
650                         continue;
651
652                 // is this a integral name?
653                 if (!testIntegral(*it))
654                         continue;
655
656                 // core ist part from behind the scripts to the 'd'
657                 auto_ptr<InsetMathExInt> p(new InsetMathExInt(from_ascii("int")));
658
659                 // handle scripts if available
660                 if (!testIntSymbol(*it)) {
661                         p->cell(2) = (*it)->asScriptInset()->down();
662                         p->cell(3) = (*it)->asScriptInset()->up();
663                 }
664                 p->cell(0) = MathData(it + 1, jt);
665
666                 // use the "thing" behind the 'd' as differential
667                 MathData::iterator tt = extractArgument(p->cell(1), jt + 1, ar.end());
668
669                 // remove used parts
670                 ar.erase(it + 1, tt);
671                 *it = MathAtom(p.release());
672         }
673         //lyxerr << "\nIntegrals to: " << ar << endl;
674 }
675
676
677 bool testTermDelimiter(MathAtom const & at)
678 {
679         return testString(at, "+") || testString(at, "-");
680 }
681
682
683 // try to extract a "term", i.e., something delimited by '+' or '-'.
684 // returns position behind the term
685 MathData::iterator extractTerm(MathData & ar,
686         MathData::iterator pos, MathData::iterator last)
687 {
688         while (pos != last && !testTermDelimiter(*pos)) {
689                 ar.push_back(*pos);
690                 ++pos;
691         }
692         return pos;
693 }
694
695
696 //
697 // search sums
698 //
699
700
701 bool testEqualSign(MathAtom const & at)
702 {
703         return testString(at, "=");
704 }
705
706
707 bool testSumSymbol(MathAtom const & p)
708 {
709         return testSymbol(p, from_ascii("sum"));
710 }
711
712
713 bool testSum(MathAtom const & at)
714 {
715         return
716          testSumSymbol(at) ||
717                 ( at->asScriptInset()
718                   && at->asScriptInset()->nuc().size()
719                         && testSumSymbol(at->asScriptInset()->nuc().back()) );
720 }
721
722
723 // replace '\sum' ['_^'] f(x) sequences by a real InsetMathExInt
724 // assume 'extractDelims' ran before
725 void extractSums(MathData & ar)
726 {
727         // we need at least two items...
728         if (ar.size() < 2)
729                 return;
730
731         //lyxerr << "\nSums from: " << ar << endl;
732         for (size_t i = 0; i + 1 < ar.size(); ++i) {
733                 MathData::iterator it = ar.begin() + i;
734
735                 // is this a sum name?
736                 if (!testSum(ar[i]))
737                         continue;
738
739                 // create a proper inset as replacement
740                 auto_ptr<InsetMathExInt> p(new InsetMathExInt(from_ascii("sum")));
741
742                 // collect lower bound and summation index
743                 InsetMathScript const * sub = ar[i]->asScriptInset();
744                 if (sub && sub->hasDown()) {
745                         // try to figure out the summation index from the subscript
746                         MathData const & ar = sub->down();
747                         MathData::const_iterator xt =
748                                 find_if(ar.begin(), ar.end(), &testEqualSign);
749                         if (xt != ar.end()) {
750                                 // we found a '=', use everything in front of that as index,
751                                 // and everything behind as lower index
752                                 p->cell(1) = MathData(ar.begin(), xt);
753                                 p->cell(2) = MathData(xt + 1, ar.end());
754                         } else {
755                                 // use everything as summation index, don't use scripts.
756                                 p->cell(1) = ar;
757                         }
758                 }
759
760                 // collect upper bound
761                 if (sub && sub->hasUp())
762                         p->cell(3) = sub->up();
763
764                 // use something  behind the script as core
765                 MathData::iterator tt = extractTerm(p->cell(0), it + 1, ar.end());
766
767                 // cleanup
768                 ar.erase(it + 1, tt);
769                 *it = MathAtom(p.release());
770         }
771         //lyxerr << "\nSums to: " << ar << endl;
772 }
773
774
775 //
776 // search differential stuff
777 //
778
779 // tests for 'd' or '\partial'
780 bool testDiffItem(MathAtom const & at)
781 {
782         if (testString(at, "d") || testSymbol(at, "partial"))
783                 return true;
784
785         // we may have d^n .../d and splitScripts() has not yet seen it
786         InsetMathScript const * sup = at->asScriptInset();
787         if (sup && !sup->hasDown() && sup->hasUp() && sup->nuc().size() == 1) {
788                 MathAtom const & ma = sup->nuc().front();
789                 return testString(ma, "d") || testSymbol(ma, "partial");
790         }
791         return false;
792 }
793
794
795 bool testDiffArray(MathData const & ar)
796 {
797         return ar.size() && testDiffItem(ar.front());
798 }
799
800
801 bool testDiffFrac(MathAtom const & at)
802 {
803         return
804                 at->asFracInset()
805                         && testDiffArray(at->asFracInset()->cell(0))
806                         && testDiffArray(at->asFracInset()->cell(1));
807 }
808
809
810 void extractDiff(MathData & ar)
811 {
812         //lyxerr << "\nDiffs from: " << ar << endl;
813         for (size_t i = 0; i < ar.size(); ++i) {
814                 MathData::iterator it = ar.begin() + i;
815
816                 // is this a "differential fraction"?
817                 if (!testDiffFrac(*it))
818                         continue;
819
820                 InsetMathFrac const * f = (*it)->asFracInset();
821                 if (!f) {
822                         lyxerr << "should not happen" << endl;
823                         continue;
824                 }
825
826                 // create a proper diff inset
827                 std::auto_ptr<InsetMathDiff> diff(new InsetMathDiff);
828
829                 // collect function, let jt point behind last used item
830                 MathData::iterator jt = it + 1;
831                 //int n = 1;
832                 MathData numer(f->cell(0));
833                 splitScripts(numer);
834                 if (numer.size() > 1 && numer[1]->asScriptInset()) {
835                         // this is something like  d^n f(x) / d... or  d^n / d...
836                         // FIXME
837                         //n = 1;
838                         if (numer.size() > 2)
839                                 diff->cell(0) = MathData(numer.begin() + 2, numer.end());
840                         else
841                                 jt = extractTerm(diff->cell(0), jt, ar.end());
842                 } else {
843                         // simply d f(x) / d... or  d/d...
844                         if (numer.size() > 1)
845                                 diff->cell(0) = MathData(numer.begin() + 1, numer.end());
846                         else
847                                 jt = extractTerm(diff->cell(0), jt, ar.end());
848                 }
849
850                 // collect denominator parts
851                 MathData denom(f->cell(1));
852                 splitScripts(denom);
853                 for (MathData::iterator dt = denom.begin(); dt != denom.end();) {
854                         // find the next 'd'
855                         MathData::iterator et
856                                 = find_if(dt + 1, denom.end(), &testDiffItem);
857
858                         // point before this
859                         MathData::iterator st = et - 1;
860                         InsetMathScript const * script = (*st)->asScriptInset();
861                         if (script && script->hasUp()) {
862                                 // things like   d.../dx^n
863                                 int mult = 1;
864                                 if (extractNumber(script->up(), mult)) {
865                                         //lyxerr << "mult: " << mult << endl;
866                                         for (int i = 0; i < mult; ++i)
867                                                 diff->addDer(MathData(dt + 1, st));
868                                 }
869                         } else {
870                                 // just  d.../dx
871                                 diff->addDer(MathData(dt + 1, et));
872                         }
873                         dt = et;
874                 }
875
876                 // cleanup
877                 ar.erase(it + 1, jt);
878                 *it = MathAtom(diff.release());
879         }
880         //lyxerr << "\nDiffs to: " << ar << endl;
881 }
882
883
884 //
885 // search limits
886 //
887
888
889 bool testRightArrow(MathAtom const & at)
890 {
891         return testSymbol(at, "to") || testSymbol(at, "rightarrow");
892 }
893
894
895
896 // replace '\lim_{x->x0} f(x)' sequences by a real InsetMathLim
897 // assume 'extractDelims' ran before
898 void extractLims(MathData & ar)
899 {
900         //lyxerr << "\nLimits from: " << ar << endl;
901         for (size_t i = 0; i < ar.size(); ++i) {
902                 MathData::iterator it = ar.begin() + i;
903
904                 // must be a script inset with a subscript (without superscript)
905                 InsetMathScript const * sub = (*it)->asScriptInset();
906                 if (!sub || !sub->hasDown() || sub->hasUp() || sub->nuc().size() != 1)
907                         continue;
908
909                 // is this a limit function?
910                 if (!testSymbol(sub->nuc().front(), "lim"))
911                         continue;
912
913                 // subscript must contain a -> symbol
914                 MathData const & s = sub->down();
915                 MathData::const_iterator st = find_if(s.begin(), s.end(), &testRightArrow);
916                 if (st == s.end())
917                         continue;
918
919                 // the -> splits the subscript int x and x0
920                 MathData x  = MathData(s.begin(), st);
921                 MathData x0 = MathData(st + 1, s.end());
922
923                 // use something behind the script as core
924                 MathData f;
925                 MathData::iterator tt = extractTerm(f, it + 1, ar.end());
926
927                 // cleanup
928                 ar.erase(it + 1, tt);
929
930                 // create a proper inset as replacement
931                 *it = MathAtom(new InsetMathLim(f, x, x0));
932         }
933         //lyxerr << "\nLimits to: " << ar << endl;
934 }
935
936
937 //
938 // combine searches
939 //
940
941 void extractStructure(MathData & ar)
942 {
943         //lyxerr << "\nStructure from: " << ar << endl;
944         splitScripts(ar);
945         extractDelims(ar);
946         extractIntegrals(ar);
947         extractSums(ar);
948         extractNumbers(ar);
949         extractMatrices(ar);
950         extractFunctions(ar);
951         extractDets(ar);
952         extractDiff(ar);
953         extractExps(ar);
954         extractLims(ar);
955         extractStrings(ar);
956         //lyxerr << "\nStructure to: " << ar << endl;
957 }
958
959
960 void write(MathData const & dat, WriteStream & wi)
961 {
962         MathData ar = dat;
963         extractStrings(ar);
964         wi.firstitem() = true;
965         for (MathData::const_iterator it = ar.begin(); it != ar.end(); ++it) {
966                 (*it)->write(wi);
967                 wi.firstitem() = false;
968         }
969 }
970
971
972 void normalize(MathData const & ar, NormalStream & os)
973 {
974         for (MathData::const_iterator it = ar.begin(); it != ar.end(); ++it)
975                 (*it)->normalize(os);
976 }
977
978
979 void octave(MathData const & dat, OctaveStream & os)
980 {
981         MathData ar = dat;
982         extractStructure(ar);
983         for (MathData::const_iterator it = ar.begin(); it != ar.end(); ++it)
984                 (*it)->octave(os);
985 }
986
987
988 void maple(MathData const & dat, MapleStream & os)
989 {
990         MathData ar = dat;
991         extractStructure(ar);
992         for (MathData::const_iterator it = ar.begin(); it != ar.end(); ++it)
993                 (*it)->maple(os);
994 }
995
996
997 void maxima(MathData const & dat, MaximaStream & os)
998 {
999         MathData ar = dat;
1000         extractStructure(ar);
1001         for (MathData::const_iterator it = ar.begin(); it != ar.end(); ++it)
1002                 (*it)->maxima(os);
1003 }
1004
1005
1006 void mathematica(MathData const & dat, MathematicaStream & os)
1007 {
1008         MathData ar = dat;
1009         extractStructure(ar);
1010         for (MathData::const_iterator it = ar.begin(); it != ar.end(); ++it)
1011                 (*it)->mathematica(os);
1012 }
1013
1014
1015 void mathmlize(MathData const & dat, MathStream & os)
1016 {
1017         MathData ar = dat;
1018         extractStructure(ar);
1019         if (ar.size() == 0)
1020                 os << "<mrow/>";
1021         else if (ar.size() == 1)
1022                 os << ar.front();
1023         else {
1024                 os << MTag("mrow");
1025                 for (MathData::const_iterator it = ar.begin(); it != ar.end(); ++it)
1026                         (*it)->mathmlize(os);
1027                 os << ETag("mrow");
1028         }
1029 }
1030
1031
1032
1033
1034 namespace {
1035
1036         std::string captureOutput(std::string const & cmd, std::string const & data)
1037         {
1038                 // In order to avoid parsing problems with command interpreters
1039                 // we pass input data through a file
1040                 FileName const cas_tmpfile(tempName(FileName(), "casinput"));
1041                 if (cas_tmpfile.empty()) {
1042                         lyxerr << "Warning: cannot create temporary file."
1043                                << endl;
1044                         return std::string();
1045                 }
1046                 std::ofstream os(cas_tmpfile.toFilesystemEncoding().c_str());
1047                 os << data << endl;
1048                 os.close();
1049                 std::string command =  cmd + " < "
1050                         + quoteName(cas_tmpfile.toFilesystemEncoding());
1051                 lyxerr << "calling: " << cmd
1052                        << "\ninput: '" << data << "'" << endl;
1053                 cmd_ret const ret = runCommand(command);
1054                 unlink(cas_tmpfile);
1055                 return ret.second;
1056         }
1057
1058         size_t get_matching_brace(std::string const & str, size_t i)
1059         {
1060                 int count = 1;
1061                 size_t n = str.size();
1062                 while (i < n) {
1063                         i = str.find_first_of("{}", i+1);
1064                         if (i == npos)
1065                                 return i;
1066                         if (str[i] == '{')
1067                                 ++count;
1068                         else
1069                                 --count;
1070                         if (count == 0)
1071                                 return i;
1072                 }
1073                 return npos;
1074         }
1075
1076         size_t get_matching_brace_back(std::string const & str, size_t i)
1077         {
1078                 int count = 1;
1079                 while (i > 0) {
1080                         i = str.find_last_of("{}", i-1);
1081                         if (i == npos)
1082                                 return i;
1083                         if (str[i] == '}')
1084                                 ++count;
1085                         else
1086                                 --count;
1087                         if (count == 0)
1088                                 return i;
1089                 }
1090                 return npos;
1091         }
1092
1093         MathData pipeThroughMaxima(docstring const &, MathData const & ar)
1094         {
1095                 odocstringstream os;
1096                 MaximaStream ms(os);
1097                 ms << ar;
1098                 docstring expr = os.str();
1099                 docstring const header = from_ascii("simpsum:true;");
1100
1101                 std::string out;
1102                 for (int i = 0; i < 100; ++i) { // at most 100 attempts
1103                         // try to fix missing '*' the hard way
1104                         //
1105                         // > echo "2x;" | maxima
1106                         // ...
1107                         // (C1) Incorrect syntax: x is not an infix operator
1108                         // 2x;
1109                         //  ^
1110                         //
1111                         lyxerr << "checking expr: '" << to_utf8(expr) << "'" << endl;
1112                         docstring full = header + "tex(" + expr + ");";
1113                         out = captureOutput("maxima", to_utf8(full));
1114
1115                         // leave loop if expression syntax is probably ok
1116                         if (out.find("Incorrect syntax") == npos)
1117                                 break;
1118
1119                         // search line with "Incorrect syntax"
1120                         istringstream is(out);
1121                         std::string line;
1122                         while (is) {
1123                                 getline(is, line);
1124                                 if (line.find("Incorrect syntax") != npos)
1125                                         break;
1126                         }
1127
1128                         // 2nd next line is the one with caret
1129                         getline(is, line);
1130                         getline(is, line);
1131                         size_t pos = line.find('^');
1132                         lyxerr << "found caret at pos: '" << pos << "'" << endl;
1133                         if (pos == npos || pos < 4)
1134                                 break; // caret position not found
1135                         pos -= 4; // skip the "tex(" part
1136                         if (expr[pos] == '*')
1137                                 break; // two '*' in a row are definitely bad
1138                         expr.insert(pos, from_ascii("*"));
1139                 }
1140
1141                 vector<std::string> tmp = getVectorFromString(out, "$$");
1142                 if (tmp.size() < 2)
1143                         return MathData();
1144
1145                 out = subst(tmp[1], "\\>", std::string());
1146                 lyxerr << "output: '" << out << "'" << endl;
1147
1148                 // Ugly code that tries to make the result prettier
1149                 size_t i = out.find("\\mathchoice");
1150                 while (i != npos) {
1151                         size_t j = get_matching_brace(out, i + 12);
1152                         size_t k = get_matching_brace(out, j + 1);
1153                         k = get_matching_brace(out, k + 1);
1154                         k = get_matching_brace(out, k + 1);
1155                         std::string mid = out.substr(i + 13, j - i - 13);
1156                         if (mid.find("\\over") != npos)
1157                                 mid = '{' + mid + '}';
1158                         out = out.substr(0,i)
1159                                 + mid
1160                                 + out.substr(k + 1);
1161                         //lyxerr << "output: " << out << endl;
1162                         i = out.find("\\mathchoice", i);
1163                         break;
1164                 }
1165
1166                 i = out.find("\\over");
1167                 while (i != npos) {
1168                         size_t j = get_matching_brace_back(out, i - 1);
1169                         if (j == npos || j == 0)
1170                                 break;
1171                         size_t k = get_matching_brace(out, i + 5);
1172                         if (k == npos || k + 1 == out.size())
1173                                 break;
1174                         out = out.substr(0,j - 1)
1175                                 + "\\frac"
1176                                 + out.substr(j,i - j)
1177                                 + out.substr(i + 5,k - i - 4)
1178                                 + out.substr(k + 2);
1179                         //lyxerr << "output: " << out << endl;
1180                         i = out.find("\\over", i + 4);
1181                 }
1182                 MathData res;
1183                 mathed_parse_cell(res, from_utf8(out));
1184                 return res;
1185         }
1186
1187
1188         MathData pipeThroughMaple(docstring const & extra, MathData const & ar)
1189         {
1190                 std::string header = "readlib(latex):\n";
1191
1192                 // remove the \\it for variable names
1193                 //"#`latex/csname_font` := `\\it `:"
1194                 header +=
1195                         "`latex/csname_font` := ``:\n";
1196
1197                 // export matrices in (...) instead of [...]
1198                 header +=
1199                         "`latex/latex/matrix` := "
1200                                 "subs(`[`=`(`, `]`=`)`,"
1201                                         "eval(`latex/latex/matrix`)):\n";
1202
1203                 // replace \\cdots with proper '*'
1204                 header +=
1205                         "`latex/latex/*` := "
1206                                 "subs(`\\,`=`\\cdot `,"
1207                                         "eval(`latex/latex/*`)):\n";
1208
1209                 // remove spurious \\noalign{\\medskip} in matrix output
1210                 header +=
1211                         "`latex/latex/matrix`:= "
1212                                 "subs(`\\\\\\\\\\\\noalign{\\\\medskip}` = `\\\\\\\\`,"
1213                                         "eval(`latex/latex/matrix`)):\n";
1214
1215                 //"#`latex/latex/symbol` "
1216                 //      " := subs((\\'_\\' = \\'`\\_`\\',eval(`latex/latex/symbol`)): ";
1217
1218                 std::string trailer = "quit;";
1219                 odocstringstream os;
1220                 MapleStream ms(os);
1221                 ms << ar;
1222                 std::string expr = to_utf8(os.str());
1223                 lyxerr << "ar: '" << ar << "'\n"
1224                        << "ms: '" << expr << "'" << endl;
1225
1226                 for (int i = 0; i < 100; ++i) { // at most 100 attempts
1227                         // try to fix missing '*' the hard way by using mint
1228                         //
1229                         // ... > echo "1A;" | mint -i 1 -S -s -q
1230                         // on line     1: 1A;
1231                         //                 ^ syntax error -
1232                         //                   Probably missing an operator such as * p
1233                         //
1234                         lyxerr << "checking expr: '" << expr << "'" << endl;
1235                         string out = captureOutput("mint -i 1 -S -s -q -q", expr + ';');
1236                         if (out.empty())
1237                                 break; // expression syntax is ok
1238                         istringstream is(out);
1239                         string line;
1240                         getline(is, line);
1241                         if (line.find("on line") != 0)
1242                                 break; // error message not identified
1243                         getline(is, line);
1244                         size_t pos = line.find('^');
1245                         if (pos == string::npos || pos < 15)
1246                                 break; // caret position not found
1247                         pos -= 15; // skip the "on line ..." part
1248                         if (expr[pos] == '*' || (pos > 0 && expr[pos - 1] == '*'))
1249                                 break; // two '*' in a row are definitely bad
1250                         expr.insert(pos, 1, '*');
1251                 }
1252
1253                 // FIXME UNICODE Is utf8 encoding correct?
1254                 string full = "latex(" + to_utf8(extra) + '(' + expr + "));";
1255                 string out = captureOutput("maple -q", header + full + trailer);
1256
1257                 // change \_ into _
1258
1259                 //
1260                 MathData res;
1261                 mathed_parse_cell(res, from_utf8(out));
1262                 return res;
1263         }
1264
1265
1266         MathData pipeThroughOctave(docstring const &, MathData const & ar)
1267         {
1268                 odocstringstream os;
1269                 OctaveStream vs(os);
1270                 vs << ar;
1271                 string expr = to_utf8(os.str());
1272                 string out;
1273
1274                 lyxerr << "pipe: ar: '" << ar << "'\n"
1275                        << "pipe: expr: '" << expr << "'" << endl;
1276
1277                 for (int i = 0; i < 100; ++i) { // at most 100 attempts
1278                         //
1279                         // try to fix missing '*' the hard way
1280                         // parse error:
1281                         // >>> ([[1 2 3 ];[2 3 1 ];[3 1 2 ]])([[1 2 3 ];[2 3 1 ];[3 1 2 ]])
1282                         //                                   ^
1283                         //
1284                         lyxerr << "checking expr: '" << expr << "'" << endl;
1285                         out = captureOutput("octave -q 2>&1", expr);
1286                         lyxerr << "output: '" << out << "'" << endl;
1287
1288                         // leave loop if expression syntax is probably ok
1289                         if (out.find("parse error:") == string::npos)
1290                                 break;
1291
1292                         // search line with single caret
1293                         istringstream is(out);
1294                         string line;
1295                         while (is) {
1296                                 getline(is, line);
1297                                 lyxerr << "skipping line: '" << line << "'" << endl;
1298                                 if (line.find(">>> ") != string::npos)
1299                                         break;
1300                         }
1301
1302                         // found line with error, next line is the one with caret
1303                         getline(is, line);
1304                         size_t pos = line.find('^');
1305                         lyxerr << "caret line: '" << line << "'" << endl;
1306                         lyxerr << "found caret at pos: '" << pos << "'" << endl;
1307                         if (pos == string::npos || pos < 4)
1308                                 break; // caret position not found
1309                         pos -= 4; // skip the ">>> " part
1310                         if (expr[pos] == '*')
1311                                 break; // two '*' in a row are definitely bad
1312                         expr.insert(pos, 1, '*');
1313                 }
1314
1315                 // remove 'ans = ' taking into account that there may be an
1316                 // ansi control sequence before, such as '\033[?1034hans = '
1317                 size_t i = out.find("ans = ");
1318                 if (i == string::npos)
1319                         return MathData();
1320                 out = out.substr(i + 6);
1321
1322                 // parse output as matrix or single number
1323                 MathAtom at(new InsetMathArray(from_ascii("array"), from_utf8(out)));
1324                 InsetMathArray const * mat = at->asArrayInset();
1325                 MathData res;
1326                 if (mat->ncols() == 1 && mat->nrows() == 1)
1327                         res.append(mat->cell(0));
1328                 else {
1329                         res.push_back(MathAtom(new InsetMathDelim(from_ascii("("), from_ascii(")"))));
1330                         res.back().nucleus()->cell(0).push_back(at);
1331                 }
1332                 return res;
1333         }
1334
1335
1336         string fromMathematicaName(string const & name)
1337         {
1338                 if (name == "Sin")    return "sin";
1339                 if (name == "Sinh")   return "sinh";
1340                 if (name == "ArcSin") return "arcsin";
1341                 if (name == "Cos")    return "cos";
1342                 if (name == "Cosh")   return "cosh";
1343                 if (name == "ArcCos") return "arccos";
1344                 if (name == "Tan")    return "tan";
1345                 if (name == "Tanh")   return "tanh";
1346                 if (name == "ArcTan") return "arctan";
1347                 if (name == "Cot")    return "cot";
1348                 if (name == "Coth")   return "coth";
1349                 if (name == "Csc")    return "csc";
1350                 if (name == "Sec")    return "sec";
1351                 if (name == "Exp")    return "exp";
1352                 if (name == "Log")    return "log";
1353                 if (name == "Arg" )   return "arg";
1354                 if (name == "Det" )   return "det";
1355                 if (name == "GCD" )   return "gcd";
1356                 if (name == "Max" )   return "max";
1357                 if (name == "Min" )   return "min";
1358                 if (name == "Erf" )   return "erf";
1359                 if (name == "Erfc" )  return "erfc";
1360                 return name;
1361         }
1362
1363
1364         void prettifyMathematicaOutput(string & out, string const & macroName,
1365                         bool roman, bool translate)
1366         {
1367                 string const macro = "\\" + macroName + "{";
1368                 size_t const len = macro.length();
1369                 size_t i = out.find(macro);
1370
1371                 while (i != npos) {
1372                         size_t const j = get_matching_brace(out, i + len);
1373                         string const name = out.substr(i + len, j - i - len);
1374                         out = out.substr(0, i)
1375                                 + (roman ? "\\mathrm{" : "")
1376                                 + (translate ? fromMathematicaName(name) : name)
1377                                 + out.substr(roman ? j : j + 1);
1378                         //lyxerr << "output: " << out << endl;
1379                         i = out.find(macro, i);
1380                 }
1381         }
1382
1383
1384         MathData pipeThroughMathematica(docstring const &, MathData const & ar)
1385         {
1386                 odocstringstream os;
1387                 MathematicaStream ms(os);
1388                 ms << ar;
1389                 // FIXME UNICODE Is utf8 encoding correct?
1390                 string const expr = to_utf8(os.str());
1391                 string out;
1392
1393                 lyxerr << "expr: '" << expr << "'" << endl;
1394
1395                 string const full = "TeXForm[" + expr + "]";
1396                 out = captureOutput("math", full);
1397                 lyxerr << "output: '" << out << "'" << endl;
1398
1399                 size_t pos1 = out.find("Out[1]//TeXForm= ");
1400                 size_t pos2 = out.find("In[2]:=");
1401
1402                 if (pos1 == string::npos || pos2 == string::npos)
1403                         return MathData();
1404
1405                 // get everything from pos1+17 to pos2
1406                 out = out.substr(pos1 + 17, pos2 - pos1 - 17);
1407                 out = subst(subst(out, '\r', ' '), '\n', ' ');
1408
1409                 // tries to make the result prettier
1410                 prettifyMathematicaOutput(out, "Mfunction", true, true);
1411                 prettifyMathematicaOutput(out, "Muserfunction", true, false);
1412                 prettifyMathematicaOutput(out, "Mvariable", false, false);
1413
1414                 MathData res;
1415                 mathed_parse_cell(res, from_utf8(out));
1416                 return res;
1417         }
1418
1419 }
1420
1421
1422 MathData pipeThroughExtern(string const & lang, docstring const & extra,
1423         MathData const & ar)
1424 {
1425         if (lang == "octave")
1426                 return pipeThroughOctave(extra, ar);
1427
1428         if (lang == "maxima")
1429                 return pipeThroughMaxima(extra, ar);
1430
1431         if (lang == "maple")
1432                 return pipeThroughMaple(extra, ar);
1433
1434         if (lang == "mathematica")
1435                 return pipeThroughMathematica(extra, ar);
1436
1437         // create normalized expression
1438         odocstringstream os;
1439         NormalStream ns(os);
1440         os << '[' << extra << ' ';
1441         ns << ar;
1442         os << ']';
1443         // FIXME UNICODE Is utf8 encoding correct?
1444         string data = to_utf8(os.str());
1445
1446         // search external script
1447         support::FileName const file = libFileSearch("mathed", "extern_" + lang);
1448         if (file.empty()) {
1449                 lyxerr << "converter to '" << lang << "' not found" << endl;
1450                 return MathData();
1451         }
1452
1453         // run external sript
1454         string out = captureOutput(file.absFilename(), data);
1455         MathData res;
1456         mathed_parse_cell(res, from_utf8(out));
1457         return res;
1458 }
1459
1460
1461 } // namespace lyx