src/mathed/MathExtern.cpp

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