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