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