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