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