On Sun, 9 Jan 2011 18:07:51 +0100
<[email protected]> wrote:
> [...]
> Then what was your idea? Isolate the failing one?
Well, I don't know about Pavel Sanda's idea, but I've done some
thinking about it for some time. The conclusion is that isolating all
the failing insets would always be very ineffective performance-wise.
Fortunately, from the user perspective, isolating only the first one
of the failing insets should be enough. The user then fixes the problem
and the generation is triggered afterwards.
For this, the simple recursive bisection would work.
Something like the following (not knowing LyX internals,
I'm using some pseudo-Pythonish-language):
// INPUT: s, skip
// s - the array of insets to generate instant previews from
// skip - optional, indicates whether to skip the initial generation
// of all the insets, should be set to true *only* if it is
// certain that at least one inset from s fails to generate
// preview
//
// OUTPUT: (p, f)
// p - the array of generated previews (or null if it fails)
// f - the 'example' inset for which the generation of preview isn't
// possible (or null if there is none)
def generate(s, skip=false) : out (p, f)
// generate_all(s) is the current method of joining all insets
// in s into one big .tex file and generating all previews together,
// choosing the correct method (dvipng or legacy)
// the result is null iff both methods fail
if (!skip)
p = generate_all(s)
if (p != null) // if everything worked fine
return (p, null) // then give the result upstream
// <-- from this point on, it is certain
// some insets from s are failing
if size(s) == 1 // if single inset is giving troubles
return (null, s[0]) // then it has been found
// otherwise ...
// ... - divide, dive and conquer :)
s' = first half of s // check whether the problem occurs
(p, f) = generate(p) // within the first half of insets
if (f != null) // (via recursion)
return (null, f)
s' = second half of s // ... if not, it should be in the
(p, f) = generate(p, true) // second half ...
assert(f != null) // ... but it is better
// to be safe than sorry
return (null, f)
The best case is of course the one without failing insets and it
requires only a single call.
Assuming that size(s)==2^n, every other case is the worst case. It
should take exactly n+1 calls to generate_all() then, so the algorithm
as a whole is of complexity O(log(n)), assuming that generate_all is
O(1). For instance, for the insane amount of 1024 insets with some of
these failing, the number of calls is always only 11, and then the
'diagnostic' ends.
If we give up the 'skip' argument (for some strange corner cases,
when some previews are generated incorrectly together, but correctly
separately, then the assertion would actually prove useful to report
just that), then the number of the calls rises to 2*n+1 in the worst
case (which, this time, is the one with only the last inset being the
failing one), so the complexity class doesn't change. However, I'm not
really sure whether this variant is worth considering; these 'corner
cases' would have to be *very* strange.
It might look big and complicated, but actually it isn't - it
is just me trying to analyse it thoroughly. I hope that it is easy
enough to actually implement it, as it gives the user opportunity to
pinpoint the failing insets easily and without guessing.
As a bonus feature, something similar to 'visual instant warnings'
from some compilers (as in '(pre)compile-time warnings') would be
possible to obtain, just by strategically using preview insets. It would
prove useful, while creating some tricky ERTs. In fact, this usage
scenario is the main reason for me to actually write this post.
Just in case, I'd also like to suggest that:
1. There should be an option to use instant preview for "math only",
for the cases where the user knows about the failing preview insets, but
don't have time to fix these,
2. Math previews should always be created separately, as these
rarely trigger instant preview-related problems (well, I'm not an expert
in this area, so it is just an assumption of mine, please correct me if
I'm wrong).
Regards,
Michał Skrzypek
