src/mathed/MathExtern.C

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