001/*
002// This software is subject to the terms of the Eclipse Public License v1.0
003// Agreement, available at the following URL:
004// http://www.eclipse.org/legal/epl-v10.html.
005// You must accept the terms of that agreement to use this software.
006//
007// Copyright (C) 2001-2005 Julian Hyde
008// Copyright (C) 2005-2013 Pentaho and others
009// All Rights Reserved.
010*/
011package mondrian.olap;
012
013import mondrian.mdx.*;
014import mondrian.olap.fun.FunUtil;
015import mondrian.olap.fun.Resolver;
016import mondrian.olap.type.Type;
017import mondrian.resource.MondrianResource;
018import mondrian.rolap.*;
019import mondrian.spi.UserDefinedFunction;
020import mondrian.util.*;
021
022import org.apache.commons.collections.keyvalue.AbstractMapEntry;
023import org.apache.commons.vfs.*;
024import org.apache.commons.vfs.provider.http.HttpFileObject;
025import org.apache.log4j.Logger;
026
027import org.eigenbase.xom.XOMUtil;
028
029import org.olap4j.impl.Olap4jUtil;
030import org.olap4j.mdx.*;
031
032import java.io.*;
033import java.lang.ref.Reference;
034import java.lang.reflect.*;
035import java.lang.reflect.Array;
036import java.math.BigDecimal;
037import java.net.MalformedURLException;
038import java.net.URL;
039import java.security.MessageDigest;
040import java.security.NoSuchAlgorithmException;
041import java.sql.*;
042import java.sql.Connection;
043import java.util.*;
044import java.util.concurrent.*;
045import java.util.concurrent.atomic.AtomicInteger;
046import java.util.regex.Matcher;
047import java.util.regex.Pattern;
048
049/**
050 * Utility functions used throughout mondrian. All methods are static.
051 *
052 * @author jhyde
053 * @since 6 August, 2001
054 */
055public class Util extends XOMUtil {
056
057    public static final String nl = System.getProperty("line.separator");
058
059    private static final Logger LOGGER = Logger.getLogger(Util.class);
060
061    /**
062     * Placeholder which indicates a value NULL.
063     */
064    public static final Object nullValue = new Double(FunUtil.DoubleNull);
065
066    /**
067     * Placeholder which indicates an EMPTY value.
068     */
069    public static final Object EmptyValue = new Double(FunUtil.DoubleEmpty);
070
071    /**
072     * Cumulative time spent accessing the database.
073     */
074    private static long databaseMillis = 0;
075
076    /**
077     * Random number generator to provide seed for other random number
078     * generators.
079     */
080    private static final Random metaRandom =
081            createRandom(MondrianProperties.instance().TestSeed.get());
082
083    /** Unique id for this JVM instance. Part of a key that ensures that if
084     * two JVMs in the same cluster have a data-source with the same
085     * identity-hash-code, they will be treated as different data-sources,
086     * and therefore caches will not be incorrectly shared. */
087    public static final UUID JVM_INSTANCE_UUID = UUID.randomUUID();
088
089    /**
090     * Whether we are running a version of Java before 1.5.
091     *
092     * <p>If (but not only if) this variable is true, {@link #Retrowoven} will
093     * also be true.
094     */
095    public static final boolean PreJdk15 =
096        System.getProperty("java.version").startsWith("1.4");
097
098    /**
099     * Whether we are running a version of Java before 1.6.
100     */
101    public static final boolean PreJdk16 =
102        PreJdk15
103        || System.getProperty("java.version").startsWith("1.5");
104
105    /**
106     * Whether this is an IBM JVM.
107     */
108    public static final boolean IBM_JVM =
109        System.getProperties().getProperty("java.vendor").equals(
110            "IBM Corporation");
111
112    /**
113     * What version of JDBC?
114     * Returns:<ul>
115     *     <li>0x0401 in JDK 1.7 and higher</li>
116     *     <li>0x0400 in JDK 1.6</li>
117     *     <li>0x0300 otherwise</li>
118     * </ul>
119     */
120    public static final int JdbcVersion =
121        System.getProperty("java.version").compareTo("1.7") >= 0
122            ? 0x0401
123            : System.getProperty("java.version").compareTo("1.6") >= 0
124            ? 0x0400
125            : 0x0300;
126
127    /**
128     * Whether the code base has re-engineered using retroweaver.
129     * If this is the case, some functionality is not available, but a lot of
130     * things are available via {@link mondrian.util.UtilCompatible}.
131     * Retroweaver has some problems involving {@link java.util.EnumSet}.
132     */
133    public static final boolean Retrowoven =
134        Access.class.getSuperclass().getName().equals(
135            "net.sourceforge.retroweaver.runtime.java.lang.Enum");
136
137    private static final UtilCompatible compatible;
138
139    /**
140     * Flag to control expensive debugging. (More expensive than merely
141     * enabling assertions: as we know, a lot of people run with assertions
142     * enabled.)
143     */
144    public static final boolean DEBUG = false;
145
146    static {
147        String className;
148        if (PreJdk15 || Retrowoven) {
149            className = "mondrian.util.UtilCompatibleJdk14";
150        } else if (PreJdk16) {
151            className = "mondrian.util.UtilCompatibleJdk15";
152        } else {
153            className = "mondrian.util.UtilCompatibleJdk16";
154        }
155        compatible = ClassResolver.INSTANCE.instantiateSafe(className);
156    }
157
158    public static boolean isNull(Object o) {
159        return o == null || o == nullValue;
160    }
161
162    /**
163     * Returns whether a list is strictly sorted.
164     *
165     * @param list List
166     * @return whether list is sorted
167     */
168    public static <T> boolean isSorted(List<T> list) {
169        T prev = null;
170        for (T t : list) {
171            if (prev != null
172                && ((Comparable<T>) prev).compareTo(t) >= 0)
173            {
174                return false;
175            }
176            prev = t;
177        }
178        return true;
179    }
180
181    /**
182     * Parses a string and returns a SHA-256 checksum of it.
183     *
184     * @param value The source string to parse.
185     * @return A checksum of the source string.
186     */
187    public static byte[] digestSha256(String value) {
188        final MessageDigest algorithm;
189        try {
190            algorithm = MessageDigest.getInstance("SHA-256");
191        } catch (NoSuchAlgorithmException e) {
192            throw new RuntimeException(e);
193        }
194        return algorithm.digest(value.getBytes());
195    }
196
197    /**
198     * Creates an MD5 hash of a String.
199     *
200     * @param value String to create one way hash upon.
201     * @return MD5 hash.
202     */
203    public static byte[] digestMd5(final String value) {
204        final MessageDigest algorithm;
205        try {
206            algorithm = MessageDigest.getInstance("MD5");
207        } catch (NoSuchAlgorithmException e) {
208            throw new RuntimeException(e);
209        }
210        return algorithm.digest(value.getBytes());
211    }
212
213    /**
214     * Creates an {@link ExecutorService} object backed by a thread pool.
215     * @param maximumPoolSize Maximum number of concurrent
216     * threads.
217     * @param corePoolSize Minimum number of concurrent
218     * threads to maintain in the pool, even if they are
219     * idle.
220     * @param keepAliveTime Time, in seconds, for which to
221     * keep alive unused threads.
222     * @param name The name of the threads.
223     * @param rejectionPolicy The rejection policy to enforce.
224     * @return An executor service preconfigured.
225     */
226    public static ExecutorService getExecutorService(
227        int maximumPoolSize,
228        int corePoolSize,
229        long keepAliveTime,
230        final String name,
231        RejectedExecutionHandler rejectionPolicy)
232    {
233        if (Util.PreJdk16) {
234            // On JDK1.5, if you specify corePoolSize=0, nothing gets executed.
235            // Bummer.
236            corePoolSize = Math.max(corePoolSize, 1);
237        }
238
239        // We must create a factory where the threads
240        // have the right name and are marked as daemon threads.
241        final ThreadFactory factory =
242            new ThreadFactory() {
243                private final AtomicInteger counter = new AtomicInteger(0);
244                public Thread newThread(Runnable r) {
245                    final Thread t =
246                        Executors.defaultThreadFactory().newThread(r);
247                    t.setDaemon(true);
248                    t.setName(name + '_' + counter.incrementAndGet());
249                    return t;
250                }
251            };
252
253        // Ok, create the executor
254        final ThreadPoolExecutor executor =
255            new ThreadPoolExecutor(
256                corePoolSize,
257                maximumPoolSize > 0
258                    ? maximumPoolSize
259                    : Integer.MAX_VALUE,
260                keepAliveTime,
261                TimeUnit.SECONDS,
262                // we use a sync queue. any other type of queue
263                // will prevent the tasks from running concurrently
264                // because the executors API requires blocking queues.
265                // Important to pass true here. This makes the
266                // order of tasks deterministic.
267                // TODO Write a non-blocking queue which implements
268                // the blocking queue API so we can pass that to the
269                // executor.
270                new SynchronousQueue<Runnable>(true),
271                factory);
272
273        // Set the rejection policy if required.
274        if (rejectionPolicy != null) {
275            executor.setRejectedExecutionHandler(
276                rejectionPolicy);
277        }
278
279        // Done
280        return executor;
281    }
282
283    /**
284     * Creates an {@link ScheduledExecutorService} object backed by a
285     * thread pool with a fixed number of threads..
286     * @param maxNbThreads Maximum number of concurrent
287     * threads.
288     * @param name The name of the threads.
289     * @return An scheduled executor service preconfigured.
290     */
291    public static ScheduledExecutorService getScheduledExecutorService(
292        final int maxNbThreads,
293        final String name)
294    {
295        return Executors.newScheduledThreadPool(
296            maxNbThreads,
297            new ThreadFactory() {
298                final AtomicInteger counter = new AtomicInteger(0);
299                public Thread newThread(Runnable r) {
300                    final Thread thread =
301                        Executors.defaultThreadFactory().newThread(r);
302                    thread.setDaemon(true);
303                    thread.setName(name + '_' + counter.incrementAndGet());
304                    return thread;
305                }
306            }
307        );
308    }
309
310    /**
311     * Encodes string for MDX (escapes ] as ]] inside a name).
312     *
313     * @deprecated Will be removed in 4.0
314     */
315    public static String mdxEncodeString(String st) {
316        StringBuilder retString = new StringBuilder(st.length() + 20);
317        for (int i = 0; i < st.length(); i++) {
318            char c = st.charAt(i);
319            if ((c == ']')
320                && ((i + 1) < st.length())
321                && (st.charAt(i + 1) != '.'))
322            {
323                retString.append(']'); // escaping character
324            }
325            retString.append(c);
326        }
327        return retString.toString();
328    }
329
330    /**
331     * Converts a string into a double-quoted string.
332     */
333    public static String quoteForMdx(String val) {
334        StringBuilder buf = new StringBuilder(val.length() + 20);
335        quoteForMdx(buf, val);
336        return buf.toString();
337    }
338
339    /**
340     * Appends a double-quoted string to a string builder.
341     */
342    public static StringBuilder quoteForMdx(StringBuilder buf, String val) {
343        buf.append("\"");
344        String s0 = replace(val, "\"", "\"\"");
345        buf.append(s0);
346        buf.append("\"");
347        return buf;
348    }
349
350    /**
351     * Return string quoted in [...].  For example, "San Francisco" becomes
352     * "[San Francisco]"; "a [bracketed] string" becomes
353     * "[a [bracketed]] string]".
354     */
355    public static String quoteMdxIdentifier(String id) {
356        StringBuilder buf = new StringBuilder(id.length() + 20);
357        quoteMdxIdentifier(id, buf);
358        return buf.toString();
359    }
360
361    public static void quoteMdxIdentifier(String id, StringBuilder buf) {
362        buf.append('[');
363        int start = buf.length();
364        buf.append(id);
365        replace(buf, start, "]", "]]");
366        buf.append(']');
367    }
368
369    /**
370     * Return identifiers quoted in [...].[...].  For example, {"Store", "USA",
371     * "California"} becomes "[Store].[USA].[California]".
372     */
373    public static String quoteMdxIdentifier(List<Id.Segment> ids) {
374        StringBuilder sb = new StringBuilder(64);
375        quoteMdxIdentifier(ids, sb);
376        return sb.toString();
377    }
378
379    public static void quoteMdxIdentifier(
380        List<Id.Segment> ids,
381        StringBuilder sb)
382    {
383        for (int i = 0; i < ids.size(); i++) {
384            if (i > 0) {
385                sb.append('.');
386            }
387            ids.get(i).toString(sb);
388        }
389    }
390
391    /**
392     * Quotes a string literal for Java or JavaScript.
393     *
394     * @param s Unquoted literal
395     * @return Quoted string literal
396     */
397    public static String quoteJavaString(String s) {
398        return s == null
399            ? "null"
400            : "\""
401              + s.replaceAll("\\\\", "\\\\\\\\")
402                .replaceAll("\\\"", "\\\\\"")
403              + "\"";
404    }
405
406    /**
407     * Returns true if two objects are equal, or are both null.
408     *
409     * @param s First object
410     * @param t Second object
411     * @return Whether objects are equal or both null
412     */
413    public static boolean equals(Object s, Object t) {
414        if (s == t) {
415            return true;
416        }
417        if (s == null || t == null) {
418            return false;
419        }
420        return s.equals(t);
421    }
422
423    /**
424     * Returns true if two strings are equal, or are both null.
425     *
426     * <p>The result is not affected by
427     * {@link MondrianProperties#CaseSensitive the case sensitive option}; if
428     * you wish to compare names, use {@link #equalName(String, String)}.
429     */
430    public static boolean equals(String s, String t) {
431        return equals((Object) s, (Object) t);
432    }
433
434    /**
435     * Returns whether two names are equal.
436     * Takes into account the
437     * {@link MondrianProperties#CaseSensitive case sensitive option}.
438     * Names may be null.
439     */
440    public static boolean equalName(String s, String t) {
441        if (s == null) {
442            return t == null;
443        }
444        boolean caseSensitive =
445            MondrianProperties.instance().CaseSensitive.get();
446        return caseSensitive ? s.equals(t) : s.equalsIgnoreCase(t);
447    }
448
449    /**
450     * Tests two strings for equality, optionally ignoring case.
451     *
452     * @param s First string
453     * @param t Second string
454     * @param matchCase Whether to perform case-sensitive match
455     * @return Whether strings are equal
456     */
457    public static boolean equal(String s, String t, boolean matchCase) {
458        return matchCase ? s.equals(t) : s.equalsIgnoreCase(t);
459    }
460
461    /**
462     * Compares two names.  if case sensitive flag is false,
463     * apply finer grain difference with case sensitive
464     * Takes into account the {@link MondrianProperties#CaseSensitive case
465     * sensitive option}.
466     * Names must not be null.
467     */
468    public static int caseSensitiveCompareName(String s, String t) {
469        boolean caseSensitive =
470            MondrianProperties.instance().CaseSensitive.get();
471        if (caseSensitive) {
472            return s.compareTo(t);
473        } else {
474            int v = s.compareToIgnoreCase(t);
475            // if ignore case returns 0 compare in a case sensitive manner
476            // this was introduced to solve an issue with Member.equals()
477            // and Member.compareTo() not agreeing with each other
478            return v == 0 ? s.compareTo(t) : v;
479        }
480    }
481
482    /**
483     * Compares two names.
484     * Takes into account the {@link MondrianProperties#CaseSensitive case
485     * sensitive option}.
486     * Names must not be null.
487     */
488    public static int compareName(String s, String t) {
489        boolean caseSensitive =
490            MondrianProperties.instance().CaseSensitive.get();
491        return caseSensitive ? s.compareTo(t) : s.compareToIgnoreCase(t);
492    }
493
494    /**
495     * Generates a normalized form of a name, for use as a key into a map.
496     * Returns the upper case name if
497     * {@link MondrianProperties#CaseSensitive} is true, the name unchanged
498     * otherwise.
499     */
500    public static String normalizeName(String s) {
501        return MondrianProperties.instance().CaseSensitive.get()
502            ? s
503            : s.toUpperCase();
504    }
505
506    /**
507     * Returns the result of ((Comparable) k1).compareTo(k2), with
508     * special-casing for the fact that Boolean only became
509     * comparable in JDK 1.5.
510     *
511     * @see Comparable#compareTo
512     */
513    public static int compareKey(Object k1, Object k2) {
514        if (k1 instanceof Boolean) {
515            // Luckily, "F" comes before "T" in the alphabet.
516            k1 = k1.toString();
517            k2 = k2.toString();
518        }
519        return ((Comparable) k1).compareTo(k2);
520    }
521
522    /**
523     * Compares integer values.
524     *
525     * @param i0 First integer
526     * @param i1 Second integer
527     * @return Comparison of integers
528     */
529    public static int compare(int i0, int i1) {
530        return i0 < i1 ? -1 : (i0 == i1 ? 0 : 1);
531    }
532
533    /**
534     * Returns a string with every occurrence of a seek string replaced with
535     * another.
536     */
537    public static String replace(String s, String find, String replace) {
538        // let's be optimistic
539        int found = s.indexOf(find);
540        if (found == -1) {
541            return s;
542        }
543        StringBuilder sb = new StringBuilder(s.length() + 20);
544        int start = 0;
545        char[] chars = s.toCharArray();
546        final int step = find.length();
547        if (step == 0) {
548            // Special case where find is "".
549            sb.append(s);
550            replace(sb, 0, find, replace);
551        } else {
552            for (;;) {
553                sb.append(chars, start, found - start);
554                if (found == s.length()) {
555                    break;
556                }
557                sb.append(replace);
558                start = found + step;
559                found = s.indexOf(find, start);
560                if (found == -1) {
561                    found = s.length();
562                }
563            }
564        }
565        return sb.toString();
566    }
567
568    /**
569     * Replaces all occurrences of a string in a buffer with another.
570     *
571     * @param buf String buffer to act on
572     * @param start Ordinal within <code>find</code> to start searching
573     * @param find String to find
574     * @param replace String to replace it with
575     * @return The string buffer
576     */
577    public static StringBuilder replace(
578        StringBuilder buf,
579        int start,
580        String find,
581        String replace)
582    {
583        // Search and replace from the end towards the start, to avoid O(n ^ 2)
584        // copying if the string occurs very commonly.
585        int findLength = find.length();
586        if (findLength == 0) {
587            // Special case where the seek string is empty.
588            for (int j = buf.length(); j >= 0; --j) {
589                buf.insert(j, replace);
590            }
591            return buf;
592        }
593        int k = buf.length();
594        while (k > 0) {
595            int i = buf.lastIndexOf(find, k);
596            if (i < start) {
597                break;
598            }
599            buf.replace(i, i + find.length(), replace);
600            // Step back far enough to ensure that the beginning of the section
601            // we just replaced does not cause a match.
602            k = i - findLength;
603        }
604        return buf;
605    }
606
607    /**
608     * Parses an MDX identifier such as <code>[Foo].[Bar].Baz.&Key&Key2</code>
609     * and returns the result as a list of segments.
610     *
611     * @param s MDX identifier
612     * @return List of segments
613     */
614    public static List<Id.Segment> parseIdentifier(String s)  {
615        return convert(
616            org.olap4j.impl.IdentifierParser.parseIdentifier(s));
617    }
618
619    /**
620     * Converts an array of name parts {"part1", "part2"} into a single string
621     * "[part1].[part2]". If the names contain "]" they are escaped as "]]".
622     */
623    public static String implode(List<Id.Segment> names) {
624        StringBuilder sb = new StringBuilder(64);
625        for (int i = 0; i < names.size(); i++) {
626            if (i > 0) {
627                sb.append(".");
628            }
629            // FIXME: should be:
630            //   names.get(i).toString(sb);
631            // but that causes some tests to fail
632            Id.Segment segment = names.get(i);
633            switch (segment.getQuoting()) {
634            case UNQUOTED:
635                segment = new Id.NameSegment(((Id.NameSegment) segment).name);
636            }
637            segment.toString(sb);
638        }
639        return sb.toString();
640    }
641
642    public static String makeFqName(String name) {
643        return quoteMdxIdentifier(name);
644    }
645
646    public static String makeFqName(OlapElement parent, String name) {
647        if (parent == null) {
648            return Util.quoteMdxIdentifier(name);
649        } else {
650            StringBuilder buf = new StringBuilder(64);
651            buf.append(parent.getUniqueName());
652            buf.append('.');
653            Util.quoteMdxIdentifier(name, buf);
654            return buf.toString();
655        }
656    }
657
658    public static String makeFqName(String parentUniqueName, String name) {
659        if (parentUniqueName == null) {
660            return quoteMdxIdentifier(name);
661        } else {
662            StringBuilder buf = new StringBuilder(64);
663            buf.append(parentUniqueName);
664            buf.append('.');
665            Util.quoteMdxIdentifier(name, buf);
666            return buf.toString();
667        }
668    }
669
670    public static OlapElement lookupCompound(
671        SchemaReader schemaReader,
672        OlapElement parent,
673        List<Id.Segment> names,
674        boolean failIfNotFound,
675        int category)
676    {
677        return lookupCompound(
678            schemaReader, parent, names, failIfNotFound, category,
679            MatchType.EXACT);
680    }
681
682    /**
683     * Resolves a name such as
684     * '[Products]&#46;[Product Department]&#46;[Produce]' by resolving the
685     * components ('Products', and so forth) one at a time.
686     *
687     * @param schemaReader Schema reader, supplies access-control context
688     * @param parent Parent element to search in
689     * @param names Exploded compound name, such as {"Products",
690     *   "Product Department", "Produce"}
691     * @param failIfNotFound If the element is not found, determines whether
692     *   to return null or throw an error
693     * @param category Type of returned element, a {@link Category} value;
694     *   {@link Category#Unknown} if it doesn't matter.
695     *
696     * @pre parent != null
697     * @post !(failIfNotFound && return == null)
698     *
699     * @see #parseIdentifier(String)
700     */
701    public static OlapElement lookupCompound(
702        SchemaReader schemaReader,
703        OlapElement parent,
704        List<Id.Segment> names,
705        boolean failIfNotFound,
706        int category,
707        MatchType matchType)
708    {
709        Util.assertPrecondition(parent != null, "parent != null");
710
711        if (LOGGER.isDebugEnabled()) {
712            StringBuilder buf = new StringBuilder(64);
713            buf.append("Util.lookupCompound: ");
714            buf.append("parent.name=");
715            buf.append(parent.getName());
716            buf.append(", category=");
717            buf.append(Category.instance.getName(category));
718            buf.append(", names=");
719            quoteMdxIdentifier(names, buf);
720            LOGGER.debug(buf.toString());
721        }
722
723        // First look up a member from the cache of calculated members
724        // (cubes and queries both have them).
725        switch (category) {
726        case Category.Member:
727        case Category.Unknown:
728            Member member = schemaReader.getCalculatedMember(names);
729            if (member != null) {
730                return member;
731            }
732        }
733        // Likewise named set.
734        switch (category) {
735        case Category.Set:
736        case Category.Unknown:
737            NamedSet namedSet = schemaReader.getNamedSet(names);
738            if (namedSet != null) {
739                return namedSet;
740            }
741        }
742
743        // Now resolve the name one part at a time.
744        for (int i = 0; i < names.size(); i++) {
745            OlapElement child;
746            Id.NameSegment name;
747            if (names.get(i) instanceof Id.NameSegment) {
748                name = (Id.NameSegment) names.get(i);
749                child = schemaReader.getElementChild(parent, name, matchType);
750            } else if (parent instanceof RolapLevel
751                       && names.get(i) instanceof Id.KeySegment
752                       && names.get(i).getKeyParts().size() == 1)
753            {
754                // The following code is for SsasCompatibleNaming=false.
755                // Continues the very limited support for key segments in
756                // mondrian-3.x. To be removed in mondrian-4, when
757                // SsasCompatibleNaming=true is the only option.
758                final Id.KeySegment keySegment = (Id.KeySegment) names.get(i);
759                name = keySegment.getKeyParts().get(0);
760                final List<Member> levelMembers =
761                    schemaReader.getLevelMembers(
762                        (Level) parent, false);
763                child = null;
764                for (Member member : levelMembers) {
765                    if (((RolapMember) member).getKey().toString().equals(
766                            name.getName()))
767                    {
768                        child = member;
769                        break;
770                    }
771                }
772            } else {
773                name = null;
774                child = schemaReader.getElementChild(parent, name, matchType);
775            }
776            // if we're doing a non-exact match, and we find a non-exact
777            // match, then for an after match, return the first child
778            // of each subsequent level; for a before match, return the
779            // last child
780            if (child instanceof Member
781                && !matchType.isExact()
782                && !Util.equalName(child.getName(), name.getName()))
783            {
784                Member bestChild = (Member) child;
785                for (int j = i + 1; j < names.size(); j++) {
786                    List<Member> childrenList =
787                        schemaReader.getMemberChildren(bestChild);
788                    FunUtil.hierarchizeMemberList(childrenList, false);
789                    if (matchType == MatchType.AFTER) {
790                        bestChild = childrenList.get(0);
791                    } else {
792                        bestChild =
793                            childrenList.get(childrenList.size() - 1);
794                    }
795                    if (bestChild == null) {
796                        child = null;
797                        break;
798                    }
799                }
800                parent = bestChild;
801                break;
802            }
803            if (child == null) {
804                if (LOGGER.isDebugEnabled()) {
805                    LOGGER.debug(
806                        "Util.lookupCompound: "
807                        + "parent.name="
808                        + parent.getName()
809                        + " has no child with name="
810                        + name);
811                }
812
813                if (!failIfNotFound) {
814                    return null;
815                } else if (category == Category.Member) {
816                    throw MondrianResource.instance().MemberNotFound.ex(
817                        quoteMdxIdentifier(names));
818                } else {
819                    throw MondrianResource.instance().MdxChildObjectNotFound
820                        .ex(name.toString(), parent.getQualifiedName());
821                }
822            }
823            parent = child;
824            if (matchType == MatchType.EXACT_SCHEMA) {
825                matchType = MatchType.EXACT;
826            }
827        }
828        if (LOGGER.isDebugEnabled()) {
829            LOGGER.debug(
830                "Util.lookupCompound: "
831                + "found child.name="
832                + parent.getName()
833                + ", child.class="
834                + parent.getClass().getName());
835        }
836
837        switch (category) {
838        case Category.Dimension:
839            if (parent instanceof Dimension) {
840                return parent;
841            } else if (parent instanceof Hierarchy) {
842                return parent.getDimension();
843            } else if (failIfNotFound) {
844                throw Util.newError(
845                    "Can not find dimension '" + implode(names) + "'");
846            } else {
847                return null;
848            }
849        case Category.Hierarchy:
850            if (parent instanceof Hierarchy) {
851                return parent;
852            } else if (parent instanceof Dimension) {
853                return parent.getHierarchy();
854            } else if (failIfNotFound) {
855                throw Util.newError(
856                    "Can not find hierarchy '" + implode(names) + "'");
857            } else {
858                return null;
859            }
860        case Category.Level:
861            if (parent instanceof Level) {
862                return parent;
863            } else if (failIfNotFound) {
864                throw Util.newError(
865                    "Can not find level '" + implode(names) + "'");
866            } else {
867                return null;
868            }
869        case Category.Member:
870            if (parent instanceof Member) {
871                return parent;
872            } else if (failIfNotFound) {
873                throw MondrianResource.instance().MdxCantFindMember.ex(
874                    implode(names));
875            } else {
876                return null;
877            }
878        case Category.Unknown:
879            assertPostcondition(parent != null, "return != null");
880            return parent;
881        default:
882            throw newInternal("Bad switch " + category);
883        }
884    }
885
886    public static OlapElement lookup(Query q, List<Id.Segment> nameParts) {
887        final Exp exp = lookup(q, nameParts, false);
888        if (exp instanceof MemberExpr) {
889            MemberExpr memberExpr = (MemberExpr) exp;
890            return memberExpr.getMember();
891        } else if (exp instanceof LevelExpr) {
892            LevelExpr levelExpr = (LevelExpr) exp;
893            return levelExpr.getLevel();
894        } else if (exp instanceof HierarchyExpr) {
895            HierarchyExpr hierarchyExpr = (HierarchyExpr) exp;
896            return hierarchyExpr.getHierarchy();
897        } else if (exp instanceof DimensionExpr) {
898            DimensionExpr dimensionExpr = (DimensionExpr) exp;
899            return dimensionExpr.getDimension();
900        } else {
901            throw Util.newInternal("Not an olap element: " + exp);
902        }
903    }
904
905    /**
906     * Converts an identifier into an expression by resolving its parts into
907     * an OLAP object (dimension, hierarchy, level or member) within the
908     * context of a query.
909     *
910     * <p>If <code>allowProp</code> is true, also allows property references
911     * from valid members, for example
912     * <code>[Measures].[Unit Sales].FORMATTED_VALUE</code>.
913     * In this case, the result will be a {@link mondrian.mdx.ResolvedFunCall}.
914     *
915     * @param q Query expression belongs to
916     * @param nameParts Parts of the identifier
917     * @param allowProp Whether to allow property references
918     * @return OLAP object or property reference
919     */
920    public static Exp lookup(
921        Query q,
922        List<Id.Segment> nameParts,
923        boolean allowProp)
924    {
925        return lookup(q, q.getSchemaReader(true), nameParts, allowProp);
926    }
927
928    /**
929     * Converts an identifier into an expression by resolving its parts into
930     * an OLAP object (dimension, hierarchy, level or member) within the
931     * context of a query.
932     *
933     * <p>If <code>allowProp</code> is true, also allows property references
934     * from valid members, for example
935     * <code>[Measures].[Unit Sales].FORMATTED_VALUE</code>.
936     * In this case, the result will be a {@link ResolvedFunCall}.
937     *
938     * @param q Query expression belongs to
939     * @param schemaReader Schema reader
940     * @param segments Parts of the identifier
941     * @param allowProp Whether to allow property references
942     * @return OLAP object or property reference
943     */
944    public static Exp lookup(
945        Query q,
946        SchemaReader schemaReader,
947        List<Id.Segment> segments,
948        boolean allowProp)
949    {
950        // First, look for a calculated member defined in the query.
951        final String fullName = quoteMdxIdentifier(segments);
952        // Look for any kind of object (member, level, hierarchy,
953        // dimension) in the cube. Use a schema reader without restrictions.
954        final SchemaReader schemaReaderSansAc =
955            schemaReader.withoutAccessControl().withLocus();
956        final Cube cube = q.getCube();
957        OlapElement olapElement =
958            schemaReaderSansAc.lookupCompound(
959                cube, segments, false, Category.Unknown);
960        if (olapElement != null) {
961            Role role = schemaReader.getRole();
962            if (!role.canAccess(olapElement)) {
963                olapElement = null;
964            }
965            if (olapElement instanceof Member) {
966                olapElement =
967                    schemaReader.substitute((Member) olapElement);
968            }
969        }
970        if (olapElement == null) {
971            if (allowProp && segments.size() > 1) {
972                List<Id.Segment> segmentsButOne =
973                    segments.subList(0, segments.size() - 1);
974                final Id.Segment lastSegment = last(segments);
975                final String propertyName =
976                    lastSegment instanceof Id.NameSegment
977                        ? ((Id.NameSegment) lastSegment).getName()
978                        : null;
979                final Member member =
980                    (Member) schemaReaderSansAc.lookupCompound(
981                        cube, segmentsButOne, false, Category.Member);
982                if (member != null
983                    && propertyName != null
984                    && isValidProperty(propertyName, member.getLevel()))
985                {
986                    return new UnresolvedFunCall(
987                        propertyName, Syntax.Property, new Exp[] {
988                            createExpr(member)});
989                }
990                final Level level =
991                    (Level) schemaReaderSansAc.lookupCompound(
992                        cube, segmentsButOne, false, Category.Level);
993                if (level != null
994                    && propertyName != null
995                    && isValidProperty(propertyName, level))
996                {
997                    return new UnresolvedFunCall(
998                        propertyName, Syntax.Property, new Exp[] {
999                            createExpr(level)});
1000                }
1001            }
1002            // if we're in the middle of loading the schema, the property has
1003            // been set to ignore invalid members, and the member is
1004            // non-existent, return the null member corresponding to the
1005            // hierarchy of the element we're looking for; locate the
1006            // hierarchy by incrementally truncating the name of the element
1007            if (q.ignoreInvalidMembers()) {
1008                int nameLen = segments.size() - 1;
1009                olapElement = null;
1010                while (nameLen > 0 && olapElement == null) {
1011                    List<Id.Segment> partialName =
1012                        segments.subList(0, nameLen);
1013                    olapElement = schemaReaderSansAc.lookupCompound(
1014                        cube, partialName, false, Category.Unknown);
1015                    nameLen--;
1016                }
1017                if (olapElement != null) {
1018                    olapElement = olapElement.getHierarchy().getNullMember();
1019                } else {
1020                    throw MondrianResource.instance().MdxChildObjectNotFound.ex(
1021                        fullName, cube.getQualifiedName());
1022                }
1023            } else {
1024                throw MondrianResource.instance().MdxChildObjectNotFound.ex(
1025                    fullName, cube.getQualifiedName());
1026            }
1027        }
1028        // keep track of any measure members referenced; these will be used
1029        // later to determine if cross joins on virtual cubes can be
1030        // processed natively
1031        q.addMeasuresMembers(olapElement);
1032        return createExpr(olapElement);
1033    }
1034
1035    /**
1036     * Looks up a cube in a schema reader.
1037     *
1038     * @param cubeName Cube name
1039     * @param fail Whether to fail if not found.
1040     * @return Cube, or null if not found
1041     */
1042    static Cube lookupCube(
1043        SchemaReader schemaReader,
1044        String cubeName,
1045        boolean fail)
1046    {
1047        for (Cube cube : schemaReader.getCubes()) {
1048            if (Util.compareName(cube.getName(), cubeName) == 0) {
1049                return cube;
1050            }
1051        }
1052        if (fail) {
1053            throw MondrianResource.instance().MdxCubeNotFound.ex(cubeName);
1054        }
1055        return null;
1056    }
1057
1058    /**
1059     * Converts an olap element (dimension, hierarchy, level or member) into
1060     * an expression representing a usage of that element in an MDX statement.
1061     */
1062    public static Exp createExpr(OlapElement element)
1063    {
1064        if (element instanceof Member) {
1065            Member member = (Member) element;
1066            return new MemberExpr(member);
1067        } else if (element instanceof Level) {
1068            Level level = (Level) element;
1069            return new LevelExpr(level);
1070        } else if (element instanceof Hierarchy) {
1071            Hierarchy hierarchy = (Hierarchy) element;
1072            return new HierarchyExpr(hierarchy);
1073        } else if (element instanceof Dimension) {
1074            Dimension dimension = (Dimension) element;
1075            return new DimensionExpr(dimension);
1076        } else if (element instanceof NamedSet) {
1077            NamedSet namedSet = (NamedSet) element;
1078            return new NamedSetExpr(namedSet);
1079        } else {
1080            throw Util.newInternal("Unexpected element type: " + element);
1081        }
1082    }
1083
1084    public static Member lookupHierarchyRootMember(
1085        SchemaReader reader, Hierarchy hierarchy, Id.NameSegment memberName)
1086    {
1087        return lookupHierarchyRootMember(
1088            reader, hierarchy, memberName, MatchType.EXACT);
1089    }
1090
1091    /**
1092     * Finds a root member of a hierarchy with a given name.
1093     *
1094     * @param hierarchy Hierarchy
1095     * @param memberName Name of root member
1096     * @return Member, or null if not found
1097     */
1098    public static Member lookupHierarchyRootMember(
1099        SchemaReader reader,
1100        Hierarchy hierarchy,
1101        Id.NameSegment memberName,
1102        MatchType matchType)
1103    {
1104        // Lookup member at first level.
1105        //
1106        // Don't use access control. Suppose we cannot see the 'nation' level,
1107        // we still want to be able to resolve '[Customer].[USA].[CA]'.
1108        List<Member> rootMembers = reader.getHierarchyRootMembers(hierarchy);
1109
1110        // if doing an inexact search on a non-all hierarchy, create
1111        // a member corresponding to the name we're searching for so
1112        // we can use it in a hierarchical search
1113        Member searchMember = null;
1114        if (!matchType.isExact()
1115            && !hierarchy.hasAll()
1116            && !rootMembers.isEmpty())
1117        {
1118            searchMember =
1119                hierarchy.createMember(
1120                    null,
1121                    rootMembers.get(0).getLevel(),
1122                    memberName.name,
1123                    null);
1124        }
1125
1126        int bestMatch = -1;
1127        int k = -1;
1128        for (Member rootMember : rootMembers) {
1129            ++k;
1130            int rc;
1131            // when searching on the ALL hierarchy, match must be exact
1132            if (matchType.isExact() || hierarchy.hasAll()) {
1133                rc = rootMember.getName().compareToIgnoreCase(memberName.name);
1134            } else {
1135                rc = FunUtil.compareSiblingMembers(
1136                    rootMember,
1137                    searchMember);
1138            }
1139            if (rc == 0) {
1140                return rootMember;
1141            }
1142            if (!hierarchy.hasAll()) {
1143                if (matchType == MatchType.BEFORE) {
1144                    if (rc < 0
1145                        && (bestMatch == -1
1146                            || FunUtil.compareSiblingMembers(
1147                                rootMember,
1148                                rootMembers.get(bestMatch)) > 0))
1149                    {
1150                        bestMatch = k;
1151                    }
1152                } else if (matchType == MatchType.AFTER) {
1153                    if (rc > 0
1154                        && (bestMatch == -1
1155                            || FunUtil.compareSiblingMembers(
1156                                rootMember,
1157                                rootMembers.get(bestMatch)) < 0))
1158                    {
1159                        bestMatch = k;
1160                    }
1161                }
1162            }
1163        }
1164
1165        if (matchType == MatchType.EXACT_SCHEMA) {
1166            return null;
1167        }
1168
1169        if (matchType != MatchType.EXACT && bestMatch != -1) {
1170            return rootMembers.get(bestMatch);
1171        }
1172        // If the first level is 'all', lookup member at second level. For
1173        // example, they could say '[USA]' instead of '[(All
1174        // Customers)].[USA]'.
1175        return (rootMembers.size() > 0 && rootMembers.get(0).isAll())
1176            ? reader.lookupMemberChildByName(
1177                rootMembers.get(0),
1178                memberName,
1179                matchType)
1180            : null;
1181    }
1182
1183    /**
1184     * Finds a named level in this hierarchy. Returns null if there is no
1185     * such level.
1186     */
1187    public static Level lookupHierarchyLevel(Hierarchy hierarchy, String s) {
1188        final Level[] levels = hierarchy.getLevels();
1189        for (Level level : levels) {
1190            if (level.getName().equalsIgnoreCase(s)) {
1191                return level;
1192            }
1193        }
1194        return null;
1195    }
1196
1197
1198
1199    /**
1200     * Finds the zero based ordinal of a Member among its siblings.
1201     */
1202    public static int getMemberOrdinalInParent(
1203        SchemaReader reader,
1204        Member member)
1205    {
1206        Member parent = member.getParentMember();
1207        List<Member> siblings =
1208            (parent == null)
1209            ? reader.getHierarchyRootMembers(member.getHierarchy())
1210            : reader.getMemberChildren(parent);
1211
1212        for (int i = 0; i < siblings.size(); i++) {
1213            if (siblings.get(i).equals(member)) {
1214                return i;
1215            }
1216        }
1217        throw Util.newInternal(
1218            "could not find member " + member + " amongst its siblings");
1219    }
1220
1221    /**
1222     * returns the first descendant on the level underneath parent.
1223     * If parent = [Time].[1997] and level = [Time].[Month], then
1224     * the member [Time].[1997].[Q1].[1] will be returned
1225     */
1226    public static Member getFirstDescendantOnLevel(
1227        SchemaReader reader,
1228        Member parent,
1229        Level level)
1230    {
1231        Member m = parent;
1232        while (m.getLevel() != level) {
1233            List<Member> children = reader.getMemberChildren(m);
1234            m = children.get(0);
1235        }
1236        return m;
1237    }
1238
1239    /**
1240     * Returns whether a string is null or empty.
1241     */
1242    public static boolean isEmpty(String s) {
1243        return (s == null) || (s.length() == 0);
1244    }
1245
1246    /**
1247     * Encloses a value in single-quotes, to make a SQL string value. Examples:
1248     * <code>singleQuoteForSql(null)</code> yields <code>NULL</code>;
1249     * <code>singleQuoteForSql("don't")</code> yields <code>'don''t'</code>.
1250     */
1251    public static String singleQuoteString(String val) {
1252        StringBuilder buf = new StringBuilder(64);
1253        singleQuoteString(val, buf);
1254        return buf.toString();
1255    }
1256
1257    /**
1258     * Encloses a value in single-quotes, to make a SQL string value. Examples:
1259     * <code>singleQuoteForSql(null)</code> yields <code>NULL</code>;
1260     * <code>singleQuoteForSql("don't")</code> yields <code>'don''t'</code>.
1261     */
1262    public static void singleQuoteString(String val, StringBuilder buf) {
1263        buf.append('\'');
1264
1265        String s0 = replace(val, "'", "''");
1266        buf.append(s0);
1267
1268        buf.append('\'');
1269    }
1270
1271    /**
1272     * Creates a random number generator.
1273     *
1274     * @param seed Seed for random number generator.
1275     *   If 0, generate a seed from the system clock and print the value
1276     *   chosen. (This is effectively non-deterministic.)
1277     *   If -1, generate a seed from an internal random number generator.
1278     *   (This is deterministic, but ensures that different tests have
1279     *   different seeds.)
1280     *
1281     * @return A random number generator.
1282     */
1283    public static Random createRandom(long seed) {
1284        if (seed == 0) {
1285            seed = new Random().nextLong();
1286            System.out.println("random: seed=" + seed);
1287        } else if (seed == -1 && metaRandom != null) {
1288            seed = metaRandom.nextLong();
1289        }
1290        return new Random(seed);
1291    }
1292
1293    /**
1294     * Returns whether a property is valid for a member of a given level.
1295     * It is valid if the property is defined at the level or at
1296     * an ancestor level, or if the property is a standard property such as
1297     * "FORMATTED_VALUE".
1298     *
1299     * @param propertyName Property name
1300     * @param level Level
1301     * @return Whether property is valid
1302     */
1303    public static boolean isValidProperty(
1304        String propertyName,
1305        Level level)
1306    {
1307        return lookupProperty(level, propertyName) != null;
1308    }
1309
1310    /**
1311     * Finds a member property called <code>propertyName</code> at, or above,
1312     * <code>level</code>.
1313     */
1314    public static Property lookupProperty(
1315        Level level,
1316        String propertyName)
1317    {
1318        do {
1319            Property[] properties = level.getProperties();
1320            for (Property property : properties) {
1321                if (property.getName().equals(propertyName)) {
1322                    return property;
1323                }
1324            }
1325            level = level.getParentLevel();
1326        } while (level != null);
1327        // Now try a standard property.
1328        boolean caseSensitive =
1329            MondrianProperties.instance().CaseSensitive.get();
1330        final Property property = Property.lookup(propertyName, caseSensitive);
1331        if (property != null
1332            && property.isMemberProperty()
1333            && property.isStandard())
1334        {
1335            return property;
1336        }
1337        return null;
1338    }
1339
1340    /**
1341     * Insert a call to this method if you want to flag a piece of
1342     * undesirable code.
1343     *
1344     * @deprecated
1345     */
1346    public static <T> T deprecated(T reason) {
1347        throw new UnsupportedOperationException(reason.toString());
1348    }
1349
1350    /**
1351     * Insert a call to this method if you want to flag a piece of
1352     * undesirable code.
1353     *
1354     * @deprecated
1355     */
1356    public static <T> T deprecated(T reason, boolean fail) {
1357        if (fail) {
1358            throw new UnsupportedOperationException(reason.toString());
1359        } else {
1360            return reason;
1361        }
1362    }
1363
1364    public static List<Member> addLevelCalculatedMembers(
1365        SchemaReader reader,
1366        Level level,
1367        List<Member> members)
1368    {
1369        List<Member> calcMembers =
1370            reader.getCalculatedMembers(level.getHierarchy());
1371        List<Member> calcMembersInThisLevel = new ArrayList<Member>();
1372        for (Member calcMember : calcMembers) {
1373            if (calcMember.getLevel().equals(level)) {
1374                calcMembersInThisLevel.add(calcMember);
1375            }
1376        }
1377        if (!calcMembersInThisLevel.isEmpty()) {
1378            List<Member> newMemberList =
1379                new ConcatenableList<Member>();
1380            newMemberList.addAll(members);
1381            newMemberList.addAll(calcMembersInThisLevel);
1382            return newMemberList;
1383        }
1384        return members;
1385    }
1386
1387    /**
1388     * Returns an exception which indicates that a particular piece of
1389     * functionality should work, but a developer has not implemented it yet.
1390     */
1391    public static RuntimeException needToImplement(Object o) {
1392        throw new UnsupportedOperationException("need to implement " + o);
1393    }
1394
1395    /**
1396     * Returns an exception indicating that we didn't expect to find this value
1397     * here.
1398     */
1399    public static <T extends Enum<T>> RuntimeException badValue(
1400        Enum<T> anEnum)
1401    {
1402        return Util.newInternal(
1403            "Was not expecting value '" + anEnum
1404            + "' for enumeration '" + anEnum.getDeclaringClass().getName()
1405            + "' in this context");
1406    }
1407
1408    /**
1409     * Converts a list of SQL-style patterns into a Java regular expression.
1410     *
1411     * <p>For example, {"Foo_", "Bar%BAZ"} becomes "Foo.|Bar.*BAZ".
1412     *
1413     * @param wildcards List of SQL-style wildcard expressions
1414     * @return Regular expression
1415     */
1416    public static String wildcardToRegexp(List<String> wildcards) {
1417        StringBuilder buf = new StringBuilder();
1418        for (String value : wildcards) {
1419            if (buf.length() > 0) {
1420                buf.append('|');
1421            }
1422            int i = 0;
1423            while (true) {
1424                int percent = value.indexOf('%', i);
1425                int underscore = value.indexOf('_', i);
1426                if (percent == -1 && underscore == -1) {
1427                    if (i < value.length()) {
1428                        buf.append(quotePattern(value.substring(i)));
1429                    }
1430                    break;
1431                }
1432                if (underscore >= 0 && (underscore < percent || percent < 0)) {
1433                    if (i < underscore) {
1434                        buf.append(
1435                            quotePattern(value.substring(i, underscore)));
1436                    }
1437                    buf.append('.');
1438                    i = underscore + 1;
1439                } else if (percent >= 0
1440                    && (percent < underscore || underscore < 0))
1441                {
1442                    if (i < percent) {
1443                    buf.append(
1444                        quotePattern(value.substring(i, percent)));
1445                    }
1446                    buf.append(".*");
1447                    i = percent + 1;
1448                } else {
1449                    throw new IllegalArgumentException();
1450                }
1451            }
1452        }
1453        return buf.toString();
1454    }
1455
1456    /**
1457     * Converts a camel-case name to an upper-case name with underscores.
1458     *
1459     * <p>For example, <code>camelToUpper("FooBar")</code> returns "FOO_BAR".
1460     *
1461     * @param s Camel-case string
1462     * @return  Upper-case string
1463     */
1464    public static String camelToUpper(String s) {
1465        StringBuilder buf = new StringBuilder(s.length() + 10);
1466        int prevUpper = -1;
1467        for (int i = 0; i < s.length(); ++i) {
1468            char c = s.charAt(i);
1469            if (Character.isUpperCase(c)) {
1470                if (i > prevUpper + 1) {
1471                    buf.append('_');
1472                }
1473                prevUpper = i;
1474            } else {
1475                c = Character.toUpperCase(c);
1476            }
1477            buf.append(c);
1478        }
1479        return buf.toString();
1480    }
1481
1482    /**
1483     * Parses a comma-separated list.
1484     *
1485     * <p>If a value contains a comma, escape it with a second comma. For
1486     * example, <code>parseCommaList("x,y,,z")</code> returns
1487     * <code>{"x", "y,z"}</code>.
1488     *
1489     * @param nameCommaList List of names separated by commas
1490     * @return List of names
1491     */
1492    public static List<String> parseCommaList(String nameCommaList) {
1493        if (nameCommaList.equals("")) {
1494            return Collections.emptyList();
1495        }
1496        if (nameCommaList.endsWith(",")) {
1497            // Special treatment for list ending in ",", because split ignores
1498            // entries after separator.
1499            final String zzz = "zzz";
1500            final List<String> list = parseCommaList(nameCommaList + zzz);
1501            String last = list.get(list.size() - 1);
1502            if (last.equals(zzz)) {
1503                list.remove(list.size() - 1);
1504            } else {
1505                list.set(
1506                    list.size() - 1,
1507                    last.substring(0, last.length() - zzz.length()));
1508            }
1509            return list;
1510        }
1511        List<String> names = new ArrayList<String>();
1512        final String[] strings = nameCommaList.split(",");
1513        for (String string : strings) {
1514            final int count = names.size();
1515            if (count > 0
1516                && names.get(count - 1).equals(""))
1517            {
1518                if (count == 1) {
1519                    if (string.equals("")) {
1520                        names.add("");
1521                    } else {
1522                        names.set(
1523                            0,
1524                            "," + string);
1525                    }
1526                } else {
1527                    names.set(
1528                        count - 2,
1529                        names.get(count - 2) + "," + string);
1530                    names.remove(count - 1);
1531                }
1532            } else {
1533                names.add(string);
1534            }
1535        }
1536        return names;
1537    }
1538
1539    /**
1540     * Returns an annotation of a particular class on a method. Returns the
1541     * default value if the annotation is not present, or in JDK 1.4.
1542     *
1543     * @param method Method containing annotation
1544     * @param annotationClassName Name of annotation class to find
1545     * @param defaultValue Value to return if annotation is not present
1546     * @return value of annotation
1547     */
1548    public static <T> T getAnnotation(
1549        Method method,
1550        String annotationClassName,
1551        T defaultValue)
1552    {
1553        return compatible.getAnnotation(
1554            method, annotationClassName, defaultValue);
1555    }
1556
1557    /**
1558     * Closes and cancels a {@link Statement} using the correct methods
1559     * available on the current Java runtime.
1560     * <p>If errors are encountered while canceling a statement,
1561     * the message is logged in {@link Util}.
1562     * @param stmt The statement to cancel.
1563     */
1564    public static void cancelStatement(Statement stmt) {
1565        compatible.cancelStatement(stmt);
1566    }
1567
1568    public static MemoryInfo getMemoryInfo() {
1569        return compatible.getMemoryInfo();
1570    }
1571
1572    /**
1573     * Converts a list of a string.
1574     *
1575     * For example,
1576     * <code>commaList("foo", Arrays.asList({"a", "b"}))</code>
1577     * returns "foo(a, b)".
1578     *
1579     * @param s Prefix
1580     * @param list List
1581     * @return String representation of string
1582     */
1583    public static <T> String commaList(
1584        String s,
1585        List<T> list)
1586    {
1587        final StringBuilder buf = new StringBuilder(s);
1588        buf.append("(");
1589        int k = -1;
1590        for (T t : list) {
1591            if (++k > 0) {
1592                buf.append(", ");
1593            }
1594            buf.append(t);
1595        }
1596        buf.append(")");
1597        return buf.toString();
1598    }
1599
1600    /**
1601     * Makes a name distinct from other names which have already been used
1602     * and shorter than a length limit, adds it to the list, and returns it.
1603     *
1604     * @param name Suggested name, may not be unique
1605     * @param maxLength Maximum length of generated name
1606     * @param nameList Collection of names already used
1607     *
1608     * @return Unique name
1609     */
1610    public static String uniquify(
1611        String name,
1612        int maxLength,
1613        Collection<String> nameList)
1614    {
1615        assert name != null;
1616        if (name.length() > maxLength) {
1617            name = name.substring(0, maxLength);
1618        }
1619        if (nameList.contains(name)) {
1620            String aliasBase = name;
1621            int j = 0;
1622            while (true) {
1623                name = aliasBase + j;
1624                if (name.length() > maxLength) {
1625                    aliasBase = aliasBase.substring(0, aliasBase.length() - 1);
1626                    continue;
1627                }
1628                if (!nameList.contains(name)) {
1629                    break;
1630                }
1631                j++;
1632            }
1633        }
1634        nameList.add(name);
1635        return name;
1636    }
1637
1638    /**
1639     * Returns whether a collection contains precisely one distinct element.
1640     * Returns false if the collection is empty, or if it contains elements
1641     * that are not the same as each other.
1642     *
1643     * @param collection Collection
1644     * @return boolean true if all values are same
1645     */
1646    public static <T> boolean areOccurencesEqual(
1647        Collection<T> collection)
1648    {
1649        Iterator<T> it = collection.iterator();
1650        if (!it.hasNext()) {
1651            // Collection is empty
1652            return false;
1653        }
1654        T first = it.next();
1655        while (it.hasNext()) {
1656            T t = it.next();
1657            if (!t.equals(first)) {
1658                return false;
1659            }
1660        }
1661        return true;
1662    }
1663
1664    /**
1665     * Creates a memory-, CPU- and cache-efficient immutable list.
1666     *
1667     * @param t Array of members of list
1668     * @param <T> Element type
1669     * @return List containing the given members
1670     */
1671    public static <T> List<T> flatList(T... t) {
1672        return _flatList(t, false);
1673    }
1674
1675    /**
1676     * Creates a memory-, CPU- and cache-efficient immutable list,
1677     * always copying the contents.
1678     *
1679     * @param t Array of members of list
1680     * @param <T> Element type
1681     * @return List containing the given members
1682     */
1683    public static <T> List<T> flatListCopy(T... t) {
1684        return _flatList(t, true);
1685    }
1686
1687    /**
1688     * Creates a memory-, CPU- and cache-efficient immutable list, optionally
1689     * copying the list.
1690     *
1691     * @param copy Whether to always copy the list
1692     * @param t Array of members of list
1693     * @return List containing the given members
1694     */
1695    private static <T> List<T> _flatList(T[] t, boolean copy) {
1696        switch (t.length) {
1697        case 0:
1698            return Collections.emptyList();
1699        case 1:
1700            return Collections.singletonList(t[0]);
1701        case 2:
1702            return new Flat2List<T>(t[0], t[1]);
1703        case 3:
1704            return new Flat3List<T>(t[0], t[1], t[2]);
1705        default:
1706            // REVIEW: AbstractList contains a modCount field; we could
1707            //   write our own implementation and reduce creation overhead a
1708            //   bit.
1709            if (copy) {
1710                return Arrays.asList(t.clone());
1711            } else {
1712                return Arrays.asList(t);
1713            }
1714        }
1715    }
1716
1717    /**
1718     * Creates a memory-, CPU- and cache-efficient immutable list from an
1719     * existing list. The list is always copied.
1720     *
1721     * @param t Array of members of list
1722     * @param <T> Element type
1723     * @return List containing the given members
1724     */
1725    public static <T> List<T> flatList(List<T> t) {
1726        switch (t.size()) {
1727        case 0:
1728            return Collections.emptyList();
1729        case 1:
1730            return Collections.singletonList(t.get(0));
1731        case 2:
1732            return new Flat2List<T>(t.get(0), t.get(1));
1733        case 3:
1734            return new Flat3List<T>(t.get(0), t.get(1), t.get(2));
1735        default:
1736            // REVIEW: AbstractList contains a modCount field; we could
1737            //   write our own implementation and reduce creation overhead a
1738            //   bit.
1739            //noinspection unchecked
1740            return (List<T>) Arrays.asList(t.toArray());
1741        }
1742    }
1743
1744    /**
1745     * Parses a locale string.
1746     *
1747     * <p>The inverse operation of {@link java.util.Locale#toString()}.
1748     *
1749     * @param localeString Locale string, e.g. "en" or "en_US"
1750     * @return Java locale object
1751     */
1752    public static Locale parseLocale(String localeString) {
1753        String[] strings = localeString.split("_");
1754        switch (strings.length) {
1755        case 1:
1756            return new Locale(strings[0]);
1757        case 2:
1758            return new Locale(strings[0], strings[1]);
1759        case 3:
1760            return new Locale(strings[0], strings[1], strings[2]);
1761        default:
1762            throw newInternal(
1763                "bad locale string '" + localeString + "'");
1764        }
1765    }
1766
1767    private static final Map<String, String> TIME_UNITS =
1768        Olap4jUtil.mapOf(
1769            "ns", "NANOSECONDS",
1770            "us", "MICROSECONDS",
1771            "ms", "MILLISECONDS",
1772            "s", "SECONDS",
1773            "m", "MINUTES",
1774            "h", "HOURS",
1775            "d", "DAYS");
1776
1777    /**
1778     * Parses an interval.
1779     *
1780     * <p>For example, "30s" becomes (30, {@link TimeUnit#SECONDS});
1781     * "2us" becomes (2, {@link TimeUnit#MICROSECONDS}).</p>
1782     *
1783     * <p>Units m (minutes), h (hours) and d (days) are only available
1784     * in JDK 1.6 or later, because the corresponding constants are missing
1785     * from {@link TimeUnit} in JDK 1.5.</p>
1786     *
1787     * @param s String to parse
1788     * @param unit Default time unit; may be null
1789     *
1790     * @return Pair of value and time unit. Neither pair or its components are
1791     * null
1792     *
1793     * @throws NumberFormatException if unit is not present and there is no
1794     * default, or if number is not valid
1795     */
1796    public static Pair<Long, TimeUnit> parseInterval(
1797        String s,
1798        TimeUnit unit)
1799        throws NumberFormatException
1800    {
1801        final String original = s;
1802        for (Map.Entry<String, String> entry : TIME_UNITS.entrySet()) {
1803            final String abbrev = entry.getKey();
1804            if (s.endsWith(abbrev)) {
1805                final String full = entry.getValue();
1806                try {
1807                    unit = TimeUnit.valueOf(full);
1808                    s = s.substring(0, s.length() - abbrev.length());
1809                    break;
1810                } catch (IllegalArgumentException e) {
1811                    // ignore - MINUTES, HOURS, DAYS are not defined in JDK1.5
1812                }
1813            }
1814        }
1815        if (unit == null) {
1816            throw new NumberFormatException(
1817                "Invalid time interval '" + original + "'. Does not contain a "
1818                + "time unit. (Suffix may be ns (nanoseconds), "
1819                + "us (microseconds), ms (milliseconds), s (seconds), "
1820                + "h (hours), d (days). For example, '20s' means 20 seconds.)");
1821        }
1822        try {
1823            return Pair.of(new BigDecimal(s).longValue(), unit);
1824        } catch (NumberFormatException e) {
1825            throw new NumberFormatException(
1826                "Invalid time interval '" + original + "'");
1827        }
1828    }
1829
1830    /**
1831     * Converts a list of olap4j-style segments to a list of mondrian-style
1832     * segments.
1833     *
1834     * @param olap4jSegmentList List of olap4j segments
1835     * @return List of mondrian segments
1836     */
1837    public static List<Id.Segment> convert(
1838        List<IdentifierSegment> olap4jSegmentList)
1839    {
1840        final List<Id.Segment> list = new ArrayList<Id.Segment>();
1841        for (IdentifierSegment olap4jSegment : olap4jSegmentList) {
1842            list.add(convert(olap4jSegment));
1843        }
1844        return list;
1845    }
1846
1847    /**
1848     * Converts an olap4j-style segment to a mondrian-style segment.
1849     *
1850     * @param olap4jSegment olap4j segment
1851     * @return mondrian segment
1852     */
1853    public static Id.Segment convert(IdentifierSegment olap4jSegment) {
1854        if (olap4jSegment instanceof NameSegment) {
1855            return convert((NameSegment) olap4jSegment);
1856        } else {
1857            return convert((KeySegment) olap4jSegment);
1858        }
1859    }
1860
1861    private static Id.KeySegment convert(final KeySegment keySegment) {
1862        return new Id.KeySegment(
1863            new AbstractList<Id.NameSegment>() {
1864                public Id.NameSegment get(int index) {
1865                    return convert(keySegment.getKeyParts().get(index));
1866                }
1867
1868                public int size() {
1869                    return keySegment.getKeyParts().size();
1870                }
1871            });
1872    }
1873
1874    private static Id.NameSegment convert(NameSegment nameSegment) {
1875        return new Id.NameSegment(
1876            nameSegment.getName(),
1877            convert(nameSegment.getQuoting()));
1878    }
1879
1880    private static Id.Quoting convert(Quoting quoting) {
1881        switch (quoting) {
1882        case QUOTED:
1883            return Id.Quoting.QUOTED;
1884        case UNQUOTED:
1885            return Id.Quoting.UNQUOTED;
1886        case KEY:
1887            return Id.Quoting.KEY;
1888        default:
1889            throw Util.unexpected(quoting);
1890        }
1891    }
1892
1893    /**
1894     * Applies a collection of filters to an iterable.
1895     *
1896     * @param iterable Iterable
1897     * @param conds Zero or more conditions
1898     * @param <T>
1899     * @return Iterable that returns only members of underlying iterable for
1900     *     for which all conditions evaluate to true
1901     */
1902    public static <T> Iterable<T> filter(
1903        final Iterable<T> iterable,
1904        final Functor1<Boolean, T>... conds)
1905    {
1906        final Functor1<Boolean, T>[] conds2 = optimizeConditions(conds);
1907        if (conds2.length == 0) {
1908            return iterable;
1909        }
1910        return new Iterable<T>() {
1911            public Iterator<T> iterator() {
1912                return new Iterator<T>() {
1913                    final Iterator<T> iterator = iterable.iterator();
1914                    T next;
1915                    boolean hasNext = moveToNext();
1916
1917                    private boolean moveToNext() {
1918                        outer:
1919                        while (iterator.hasNext()) {
1920                            next = iterator.next();
1921                            for (Functor1<Boolean, T> cond : conds2) {
1922                                if (!cond.apply(next)) {
1923                                    continue outer;
1924                                }
1925                            }
1926                            return true;
1927                        }
1928                        return false;
1929                    }
1930
1931                    public boolean hasNext() {
1932                        return hasNext;
1933                    }
1934
1935                    public T next() {
1936                        T t = next;
1937                        hasNext = moveToNext();
1938                        return t;
1939                    }
1940
1941                    public void remove() {
1942                        throw new UnsupportedOperationException();
1943                    }
1944                };
1945            }
1946        };
1947    }
1948
1949    private static <T> Functor1<Boolean, T>[] optimizeConditions(
1950        Functor1<Boolean, T>[] conds)
1951    {
1952        final List<Functor1<Boolean, T>> functor1List =
1953            new ArrayList<Functor1<Boolean, T>>(Arrays.asList(conds));
1954        for (Iterator<Functor1<Boolean, T>> funcIter =
1955            functor1List.iterator(); funcIter.hasNext();)
1956        {
1957            Functor1<Boolean, T> booleanTFunctor1 = funcIter.next();
1958            if (booleanTFunctor1 == trueFunctor()) {
1959                funcIter.remove();
1960            }
1961        }
1962        if (functor1List.size() < conds.length) {
1963            //noinspection unchecked
1964            return functor1List.toArray(new Functor1[functor1List.size()]);
1965        } else {
1966            return conds;
1967        }
1968    }
1969
1970    /**
1971     * Sorts a collection of {@link Comparable} objects and returns a list.
1972     *
1973     * @param collection Collection
1974     * @param <T> Element type
1975     * @return Sorted list
1976     */
1977    public static <T extends Comparable> List<T> sort(
1978        Collection<T> collection)
1979    {
1980        Object[] a = collection.toArray(new Object[collection.size()]);
1981        Arrays.sort(a);
1982        return cast(Arrays.asList(a));
1983    }
1984
1985    /**
1986     * Sorts a collection of objects using a {@link java.util.Comparator} and returns a
1987     * list.
1988     *
1989     * @param collection Collection
1990     * @param comparator Comparator
1991     * @param <T> Element type
1992     * @return Sorted list
1993     */
1994    public static <T> List<T> sort(
1995        Collection<T> collection,
1996        Comparator<T> comparator)
1997    {
1998        Object[] a = collection.toArray(new Object[collection.size()]);
1999        //noinspection unchecked
2000        Arrays.sort(a, (Comparator<? super Object>) comparator);
2001        return cast(Arrays.asList(a));
2002    }
2003
2004    public static List<IdentifierSegment> toOlap4j(
2005        final List<Id.Segment> segments)
2006    {
2007        return new AbstractList<IdentifierSegment>() {
2008            public IdentifierSegment get(int index) {
2009                return toOlap4j(segments.get(index));
2010            }
2011
2012            public int size() {
2013                return segments.size();
2014            }
2015        };
2016    }
2017
2018    public static IdentifierSegment toOlap4j(Id.Segment segment) {
2019        switch (segment.quoting) {
2020        case KEY:
2021            return toOlap4j((Id.KeySegment) segment);
2022        default:
2023            return toOlap4j((Id.NameSegment) segment);
2024        }
2025    }
2026
2027    private static KeySegment toOlap4j(final Id.KeySegment keySegment) {
2028        return new KeySegment(
2029            new AbstractList<NameSegment>() {
2030                public NameSegment get(int index) {
2031                    return toOlap4j(keySegment.subSegmentList.get(index));
2032                }
2033
2034                public int size() {
2035                    return keySegment.subSegmentList.size();
2036                }
2037            });
2038    }
2039
2040    private static NameSegment toOlap4j(Id.NameSegment nameSegment) {
2041        return new NameSegment(
2042            null,
2043            nameSegment.name,
2044            toOlap4j(nameSegment.quoting));
2045    }
2046
2047    public static Quoting toOlap4j(Id.Quoting quoting) {
2048        return Quoting.valueOf(quoting.name());
2049    }
2050
2051    // TODO: move to IdentifierSegment
2052    public static boolean matches(IdentifierSegment segment, String name) {
2053        switch (segment.getQuoting()) {
2054        case KEY:
2055            return false; // FIXME
2056        case QUOTED:
2057            return equalName(segment.getName(), name);
2058        case UNQUOTED:
2059            return segment.getName().equalsIgnoreCase(name);
2060        default:
2061            throw unexpected(segment.getQuoting());
2062        }
2063    }
2064
2065    public static RuntimeException newElementNotFoundException(
2066        int category,
2067        IdentifierNode identifierNode)
2068    {
2069        String type;
2070        switch (category) {
2071        case Category.Member:
2072            return MondrianResource.instance().MemberNotFound.ex(
2073                identifierNode.toString());
2074        case Category.Unknown:
2075            type = "Element";
2076            break;
2077        default:
2078            type = Category.instance().getDescription(category);
2079        }
2080        return newError(type + " '" + identifierNode + "' not found");
2081    }
2082
2083    /**
2084     * Calls {@link java.util.concurrent.Future#get()} and converts any
2085     * throwable into a non-checked exception.
2086     *
2087     * @param future Future
2088     * @param message Message to qualify wrapped exception
2089     * @param <T> Result type
2090     * @return Result
2091     */
2092    public static <T> T safeGet(Future<T> future, String message) {
2093        try {
2094            return future.get();
2095        } catch (InterruptedException e) {
2096            throw newError(e, message);
2097        } catch (ExecutionException e) {
2098            final Throwable cause = e.getCause();
2099            if (cause instanceof RuntimeException) {
2100                throw (RuntimeException) cause;
2101            } else if (cause instanceof Error) {
2102                throw (Error) cause;
2103            } else {
2104                throw newError(cause, message);
2105            }
2106        }
2107    }
2108
2109    public static <T> Set<T> newIdentityHashSetFake() {
2110        final HashMap<T, Boolean> map = new HashMap<T, Boolean>();
2111        return new Set<T>() {
2112            public int size() {
2113                return map.size();
2114            }
2115
2116            public boolean isEmpty() {
2117                return map.isEmpty();
2118            }
2119
2120            public boolean contains(Object o) {
2121                return map.containsKey(o);
2122            }
2123
2124            public Iterator<T> iterator() {
2125                return map.keySet().iterator();
2126            }
2127
2128            public Object[] toArray() {
2129                return map.keySet().toArray();
2130            }
2131
2132            public <T> T[] toArray(T[] a) {
2133                return map.keySet().toArray(a);
2134            }
2135
2136            public boolean add(T t) {
2137                return map.put(t, Boolean.TRUE) == null;
2138            }
2139
2140            public boolean remove(Object o) {
2141                return map.remove(o) == Boolean.TRUE;
2142            }
2143
2144            public boolean containsAll(Collection<?> c) {
2145                return map.keySet().containsAll(c);
2146            }
2147
2148            public boolean addAll(Collection<? extends T> c) {
2149                throw new UnsupportedOperationException();
2150            }
2151
2152            public boolean retainAll(Collection<?> c) {
2153                throw new UnsupportedOperationException();
2154            }
2155
2156            public boolean removeAll(Collection<?> c) {
2157                throw new UnsupportedOperationException();
2158            }
2159
2160            public void clear() {
2161                map.clear();
2162            }
2163        };
2164    }
2165
2166    /**
2167     * Equivalent to {@link Timer#Timer(String, boolean)}.
2168     * (Introduced in JDK 1.5.)
2169     *
2170     * @param name the name of the associated thread
2171     * @param isDaemon true if the associated thread should run as a daemon
2172     * @return timer
2173     */
2174    public static Timer newTimer(String name, boolean isDaemon) {
2175        return compatible.newTimer(name, isDaemon);
2176    }
2177
2178    /**
2179     * As Arrays#binarySearch(Object[], int, int, Object), but
2180     * available pre-JDK 1.6.
2181     */
2182    public static <T extends Comparable<T>> int binarySearch(
2183        T[] ts, int start, int end, T t)
2184    {
2185        return compatible.binarySearch(ts, start, end, t);
2186    }
2187
2188    /**
2189     * Returns the intersection of two sorted sets. Does not modify either set.
2190     *
2191     * <p>Optimized for the case that both sets are {@link ArraySortedSet}.</p>
2192     *
2193     * @param set1 First set
2194     * @param set2 Second set
2195     * @return Intersection of the sets
2196     */
2197    public static <E extends Comparable> SortedSet<E> intersect(
2198        SortedSet<E> set1,
2199        SortedSet<E> set2)
2200    {
2201        if (set1.isEmpty()) {
2202            return set1;
2203        }
2204        if (set2.isEmpty()) {
2205            return set2;
2206        }
2207        if (!(set1 instanceof ArraySortedSet)
2208            || !(set2 instanceof ArraySortedSet))
2209        {
2210            final TreeSet<E> set = new TreeSet<E>(set1);
2211            set.retainAll(set2);
2212            return set;
2213        }
2214        final Comparable<?>[] result =
2215            new Comparable[Math.min(set1.size(), set2.size())];
2216        final Iterator<E> it1 = set1.iterator();
2217        final Iterator<E> it2 = set2.iterator();
2218        int i = 0;
2219        E e1 = it1.next();
2220        E e2 = it2.next();
2221        for (;;) {
2222            final int compare = e1.compareTo(e2);
2223            if (compare == 0) {
2224                result[i++] = e1;
2225                if (!it1.hasNext() || !it2.hasNext()) {
2226                    break;
2227                }
2228                e1 = it1.next();
2229                e2 = it2.next();
2230            } else if (compare == 1) {
2231                if (!it2.hasNext()) {
2232                    break;
2233                }
2234                e2 = it2.next();
2235            } else {
2236                if (!it1.hasNext()) {
2237                    break;
2238                }
2239                e1 = it1.next();
2240            }
2241        }
2242        return new ArraySortedSet(result, 0, i);
2243    }
2244
2245    /**
2246     * Compares two integers using the same algorithm as
2247     * {@link Integer#compareTo(Integer)}.
2248     *
2249     * @param i0 First integer
2250     * @param i1 Second integer
2251     * @return Comparison
2252     */
2253    public static int compareIntegers(int i0, int i1) {
2254        return (i0 < i1 ? -1 : (i0 == i1 ? 0 : 1));
2255    }
2256
2257    /**
2258     * Returns the last item in a list.
2259     *
2260     * @param list List
2261     * @param <T> Element type
2262     * @return Last item in the list
2263     * @throws IndexOutOfBoundsException if list is empty
2264     */
2265    public static <T> T last(List<T> list) {
2266        return list.get(list.size() - 1);
2267    }
2268
2269    /**
2270     * Returns the sole item in a list.
2271     *
2272     * <p>If the list has 0 or more than one element, throws.</p>
2273     *
2274     * @param list List
2275     * @param <T> Element type
2276     * @return Sole item in the list
2277     * @throws IndexOutOfBoundsException if list is empty or has more than 1 elt
2278     */
2279    public static <T> T only(List<T> list) {
2280        if (list.size() != 1) {
2281            throw new IndexOutOfBoundsException(
2282                "list " + list + " has " + list.size()
2283                + " elements, expected 1");
2284        }
2285        return list.get(0);
2286    }
2287
2288    /**
2289     * Closes a JDBC result set, statement, and connection, ignoring any errors.
2290     * If any of them are null, that's fine.
2291     *
2292     * <p>If any of them throws a {@link SQLException}, returns the first
2293     * such exception, but always executes all closes.</p>
2294     *
2295     * @param resultSet Result set
2296     * @param statement Statement
2297     * @param connection Connection
2298     */
2299    public static SQLException close(
2300        ResultSet resultSet,
2301        Statement statement,
2302        Connection connection)
2303    {
2304        SQLException firstException = null;
2305        if (resultSet != null) {
2306            try {
2307                if (statement == null) {
2308                    statement = resultSet.getStatement();
2309                }
2310                resultSet.close();
2311            } catch (Throwable t) {
2312                firstException = new SQLException();
2313                firstException.initCause(t);
2314            }
2315        }
2316        if (statement != null) {
2317            try {
2318                statement.close();
2319            } catch (Throwable t) {
2320                if (firstException == null) {
2321                    firstException = new SQLException();
2322                    firstException.initCause(t);
2323                }
2324            }
2325        }
2326        if (connection != null) {
2327            try {
2328                connection.close();
2329            } catch (Throwable t) {
2330                if (firstException == null) {
2331                    firstException = new SQLException();
2332                    firstException.initCause(t);
2333                }
2334            }
2335        }
2336        return firstException;
2337    }
2338
2339    /**
2340     * Creates a bitset with bits from {@code fromIndex} (inclusive) to
2341     * specified {@code toIndex} (exclusive) set to {@code true}.
2342     *
2343     * <p>For example, {@code bitSetBetween(0, 3)} returns a bit set with bits
2344     * {0, 1, 2} set.
2345     *
2346     * @param fromIndex Index of the first bit to be set.
2347     * @param toIndex   Index after the last bit to be set.
2348     * @return Bit set
2349     */
2350    public static BitSet bitSetBetween(int fromIndex, int toIndex) {
2351        final BitSet bitSet = new BitSet();
2352        if (toIndex > fromIndex) {
2353            // Avoid http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6222207
2354            // "BitSet internal invariants may be violated"
2355            bitSet.set(fromIndex, toIndex);
2356        }
2357        return bitSet;
2358    }
2359
2360    public static class ErrorCellValue {
2361        public String toString() {
2362            return "#ERR";
2363        }
2364    }
2365
2366    @SuppressWarnings({"unchecked"})
2367    public static <T> T[] genericArray(Class<T> clazz, int size) {
2368        return (T[]) Array.newInstance(clazz, size);
2369    }
2370
2371    /**
2372     * Throws an internal error if condition is not true. It would be called
2373     * <code>assert</code>, but that is a keyword as of JDK 1.4.
2374     */
2375    public static void assertTrue(boolean b) {
2376        if (!b) {
2377            throw newInternal("assert failed");
2378        }
2379    }
2380
2381    /**
2382     * Throws an internal error with the given messagee if condition is not
2383     * true. It would be called <code>assert</code>, but that is a keyword as
2384     * of JDK 1.4.
2385     */
2386    public static void assertTrue(boolean b, String message) {
2387        if (!b) {
2388            throw newInternal("assert failed: " + message);
2389        }
2390    }
2391
2392    /**
2393     * Creates an internal error with a given message.
2394     */
2395    public static RuntimeException newInternal(String message) {
2396        return MondrianResource.instance().Internal.ex(message);
2397    }
2398
2399    /**
2400     * Creates an internal error with a given message and cause.
2401     */
2402    public static RuntimeException newInternal(Throwable e, String message) {
2403        return MondrianResource.instance().Internal.ex(message, e);
2404    }
2405
2406    /**
2407     * Creates a non-internal error. Currently implemented in terms of
2408     * internal errors, but later we will create resourced messages.
2409     */
2410    public static RuntimeException newError(String message) {
2411        return newInternal(message);
2412    }
2413
2414    /**
2415     * Creates a non-internal error. Currently implemented in terms of
2416     * internal errors, but later we will create resourced messages.
2417     */
2418    public static RuntimeException newError(Throwable e, String message) {
2419        return newInternal(e, message);
2420    }
2421
2422    /**
2423     * Returns an exception indicating that we didn't expect to find this value
2424     * here.
2425     *
2426     * @param value Value
2427     */
2428    public static RuntimeException unexpected(Enum value) {
2429        return Util.newInternal(
2430            "Was not expecting value '" + value
2431            + "' for enumeration '" + value.getClass().getName()
2432            + "' in this context");
2433    }
2434
2435    /**
2436     * Checks that a precondition (declared using the javadoc <code>@pre</code>
2437     * tag) is satisfied.
2438     *
2439     * @param b The value of executing the condition
2440     */
2441    public static void assertPrecondition(boolean b) {
2442        assertTrue(b);
2443    }
2444
2445    /**
2446     * Checks that a precondition (declared using the javadoc <code>@pre</code>
2447     * tag) is satisfied. For example,
2448     *
2449     * <blockquote><pre>void f(String s) {
2450     *    Util.assertPrecondition(s != null, "s != null");
2451     *    ...
2452     * }</pre></blockquote>
2453     *
2454     * @param b The value of executing the condition
2455     * @param condition The text of the condition
2456     */
2457    public static void assertPrecondition(boolean b, String condition) {
2458        assertTrue(b, condition);
2459    }
2460
2461    /**
2462     * Checks that a postcondition (declared using the javadoc
2463     * <code>@post</code> tag) is satisfied.
2464     *
2465     * @param b The value of executing the condition
2466     */
2467    public static void assertPostcondition(boolean b) {
2468        assertTrue(b);
2469    }
2470
2471    /**
2472     * Checks that a postcondition (declared using the javadoc
2473     * <code>@post</code> tag) is satisfied.
2474     *
2475     * @param b The value of executing the condition
2476     */
2477    public static void assertPostcondition(boolean b, String condition) {
2478        assertTrue(b, condition);
2479    }
2480
2481    /**
2482     * Converts an error into an array of strings, the most recent error first.
2483     *
2484     * @param e the error; may be null. Errors are chained according to their
2485     *    {@link Throwable#getCause cause}.
2486     */
2487    public static String[] convertStackToString(Throwable e) {
2488        List<String> list = new ArrayList<String>();
2489        while (e != null) {
2490            String sMsg = getErrorMessage(e);
2491            list.add(sMsg);
2492            e = e.getCause();
2493        }
2494        return list.toArray(new String[list.size()]);
2495    }
2496
2497    /**
2498     * Constructs the message associated with an arbitrary Java error, making
2499     * up one based on the stack trace if there is none. As
2500     * {@link #getErrorMessage(Throwable,boolean)}, but does not print the
2501     * class name if the exception is derived from {@link java.sql.SQLException}
2502     * or is exactly a {@link java.lang.Exception}.
2503     */
2504    public static String getErrorMessage(Throwable err) {
2505        boolean prependClassName =
2506            !(err instanceof java.sql.SQLException
2507              || err.getClass() == java.lang.Exception.class);
2508        return getErrorMessage(err, prependClassName);
2509    }
2510
2511    /**
2512     * Constructs the message associated with an arbitrary Java error, making
2513     * up one based on the stack trace if there is none.
2514     *
2515     * @param err the error
2516     * @param prependClassName should the error be preceded by the
2517     *   class name of the Java exception?  defaults to false, unless the error
2518     *   is derived from {@link java.sql.SQLException} or is exactly a {@link
2519     *   java.lang.Exception}
2520     */
2521    public static String getErrorMessage(
2522        Throwable err,
2523        boolean prependClassName)
2524    {
2525        String errMsg = err.getMessage();
2526        if ((errMsg == null) || (err instanceof RuntimeException)) {
2527            StringWriter sw = new StringWriter();
2528            PrintWriter pw = new PrintWriter(sw);
2529            err.printStackTrace(pw);
2530            return sw.toString();
2531        } else {
2532            return (prependClassName)
2533                ? err.getClass().getName() + ": " + errMsg
2534                : errMsg;
2535        }
2536    }
2537
2538    /**
2539     * If one of the causes of an exception is of a particular class, returns
2540     * that cause. Otherwise returns null.
2541     *
2542     * @param e Exception
2543     * @param clazz Desired class
2544     * @param <T> Class
2545     * @return Cause of given class, or null
2546     */
2547    public static <T extends Throwable>
2548    T getMatchingCause(Throwable e, Class<T> clazz) {
2549        for (;;) {
2550            if (clazz.isInstance(e)) {
2551                return clazz.cast(e);
2552            }
2553            final Throwable cause = e.getCause();
2554            if (cause == null || cause == e) {
2555                return null;
2556            }
2557            e = cause;
2558        }
2559    }
2560
2561    /**
2562     * Converts an expression to a string.
2563     */
2564    public static String unparse(Exp exp) {
2565        StringWriter sw = new StringWriter();
2566        PrintWriter pw = new PrintWriter(sw);
2567        exp.unparse(pw);
2568        return sw.toString();
2569    }
2570
2571    /**
2572     * Converts an query to a string.
2573     */
2574    public static String unparse(Query query) {
2575        StringWriter sw = new StringWriter();
2576        PrintWriter pw = new QueryPrintWriter(sw);
2577        query.unparse(pw);
2578        return sw.toString();
2579    }
2580
2581    /**
2582     * Creates a file-protocol URL for the given file.
2583     */
2584    public static URL toURL(File file) throws MalformedURLException {
2585        String path = file.getAbsolutePath();
2586        // This is a bunch of weird code that is required to
2587        // make a valid URL on the Windows platform, due
2588        // to inconsistencies in what getAbsolutePath returns.
2589        String fs = System.getProperty("file.separator");
2590        if (fs.length() == 1) {
2591            char sep = fs.charAt(0);
2592            if (sep != '/') {
2593                path = path.replace(sep, '/');
2594            }
2595            if (path.charAt(0) != '/') {
2596                path = '/' + path;
2597            }
2598        }
2599        path = "file://" + path;
2600        return new URL(path);
2601    }
2602
2603    /**
2604     * <code>PropertyList</code> is an order-preserving list of key-value
2605     * pairs. Lookup is case-insensitive, but the case of keys is preserved.
2606     */
2607    public static class PropertyList
2608        implements Iterable<Pair<String, String>>, Serializable
2609    {
2610        List<Pair<String, String>> list =
2611            new ArrayList<Pair<String, String>>();
2612
2613        public PropertyList() {
2614            this.list = new ArrayList<Pair<String, String>>();
2615        }
2616
2617        private PropertyList(List<Pair<String, String>> list) {
2618            this.list = list;
2619        }
2620
2621        @SuppressWarnings({"CloneDoesntCallSuperClone"})
2622        @Override
2623        public PropertyList clone() {
2624            return new PropertyList(new ArrayList<Pair<String, String>>(list));
2625        }
2626
2627        public String get(String key) {
2628            return get(key, null);
2629        }
2630
2631        public String get(String key, String defaultValue) {
2632            for (int i = 0, n = list.size(); i < n; i++) {
2633                Pair<String, String> pair = list.get(i);
2634                if (pair.left.equalsIgnoreCase(key)) {
2635                    return pair.right;
2636                }
2637            }
2638            return defaultValue;
2639        }
2640
2641        public String put(String key, String value) {
2642            for (int i = 0, n = list.size(); i < n; i++) {
2643                Pair<String, String> pair = list.get(i);
2644                if (pair.left.equalsIgnoreCase(key)) {
2645                    String old = pair.right;
2646                    if (key.equalsIgnoreCase("Provider")) {
2647                        // Unlike all other properties, later values of
2648                        // "Provider" do not supersede
2649                    } else {
2650                        pair.right = value;
2651                    }
2652                    return old;
2653                }
2654            }
2655            list.add(new Pair<String, String>(key, value));
2656            return null;
2657        }
2658
2659        public boolean remove(String key) {
2660            boolean found = false;
2661            for (int i = 0; i < list.size(); i++) {
2662                Pair<String, String> pair = list.get(i);
2663                if (pair.getKey().equalsIgnoreCase(key)) {
2664                    list.remove(i);
2665                    found = true;
2666                    --i;
2667                }
2668            }
2669            return found;
2670        }
2671
2672        public String toString() {
2673            StringBuilder sb = new StringBuilder(64);
2674            for (int i = 0, n = list.size(); i < n; i++) {
2675                Pair<String, String> pair = list.get(i);
2676                if (i > 0) {
2677                    sb.append("; ");
2678                }
2679                sb.append(pair.left);
2680                sb.append('=');
2681
2682                final String right = pair.right;
2683                if (right == null) {
2684                    sb.append("'null'");
2685                } else {
2686                    // Quote a property value if is has a semi colon in it
2687                    // 'xxx;yyy'. Escape any single-quotes by doubling them.
2688                    final int needsQuote = right.indexOf(';');
2689                    if (needsQuote >= 0) {
2690                        // REVIEW: This logic leaves off the leading/trailing
2691                        //   quote if the property value already has a
2692                        //   leading/trailing quote. Doesn't seem right to me.
2693                        if (right.charAt(0) != '\'') {
2694                            sb.append("'");
2695                        }
2696                        sb.append(replace(right, "'", "''"));
2697                        if (right.charAt(right.length() - 1) != '\'') {
2698                            sb.append("'");
2699                        }
2700                    } else {
2701                        sb.append(right);
2702                    }
2703                }
2704            }
2705            return sb.toString();
2706        }
2707
2708        public Iterator<Pair<String, String>> iterator() {
2709            return list.iterator();
2710        }
2711    }
2712
2713    /**
2714     * Converts an OLE DB connect string into a {@link PropertyList}.
2715     *
2716     * <p> For example, <code>"Provider=MSOLAP; DataSource=LOCALHOST;"</code>
2717     * becomes the set of (key, value) pairs <code>{("Provider","MSOLAP"),
2718     * ("DataSource", "LOCALHOST")}</code>. Another example is
2719     * <code>Provider='sqloledb';Data Source='MySqlServer';Initial
2720     * Catalog='Pubs';Integrated Security='SSPI';</code>.
2721     *
2722     * <p> This method implements as much as possible of the <a
2723     * href="http://msdn.microsoft.com/library/en-us/oledb/htm/oledbconnectionstringsyntax.asp"
2724     * target="_blank">OLE DB connect string syntax
2725     * specification</a>. To find what it <em>actually</em> does, take
2726     * a look at the <code>mondrian.olap.UtilTestCase</code> test case.
2727     */
2728    public static PropertyList parseConnectString(String s) {
2729        return new ConnectStringParser(s).parse();
2730    }
2731
2732    private static class ConnectStringParser {
2733        private final String s;
2734        private final int n;
2735        private int i;
2736        private final StringBuilder nameBuf;
2737        private final StringBuilder valueBuf;
2738
2739        private ConnectStringParser(String s) {
2740            this.s = s;
2741            this.i = 0;
2742            this.n = s.length();
2743            this.nameBuf = new StringBuilder(64);
2744            this.valueBuf = new StringBuilder(64);
2745        }
2746
2747        PropertyList parse() {
2748            PropertyList list = new PropertyList();
2749            while (i < n) {
2750                parsePair(list);
2751            }
2752            return list;
2753        }
2754        /**
2755         * Reads "name=value;" or "name=value<EOF>".
2756         */
2757        void parsePair(PropertyList list) {
2758            String name = parseName();
2759            if (name == null) {
2760                return;
2761            }
2762            String value;
2763            if (i >= n) {
2764                value = "";
2765            } else if (s.charAt(i) == ';') {
2766                i++;
2767                value = "";
2768            } else {
2769                value = parseValue();
2770            }
2771            list.put(name, value);
2772        }
2773
2774        /**
2775         * Reads "name=". Name can contain equals sign if equals sign is
2776         * doubled. Returns null if there is no name to read.
2777         */
2778        String parseName() {
2779            nameBuf.setLength(0);
2780            while (true) {
2781                char c = s.charAt(i);
2782                switch (c) {
2783                case '=':
2784                    i++;
2785                    if (i < n && (c = s.charAt(i)) == '=') {
2786                        // doubled equals sign; take one of them, and carry on
2787                        i++;
2788                        nameBuf.append(c);
2789                        break;
2790                    }
2791                    String name = nameBuf.toString();
2792                    name = name.trim();
2793                    return name;
2794                case ' ':
2795                    if (nameBuf.length() == 0) {
2796                        // ignore preceding spaces
2797                        i++;
2798                        if (i >= n) {
2799                            // there is no name, e.g. trailing spaces after
2800                            // semicolon, 'x=1; y=2; '
2801                            return null;
2802                        }
2803                        break;
2804                    } else {
2805                        // fall through
2806                    }
2807                default:
2808                    nameBuf.append(c);
2809                    i++;
2810                    if (i >= n) {
2811                        return nameBuf.toString().trim();
2812                    }
2813                }
2814            }
2815        }
2816
2817        /**
2818         * Reads "value;" or "value<EOF>"
2819         */
2820        String parseValue() {
2821            char c;
2822            // skip over leading white space
2823            while ((c = s.charAt(i)) == ' ') {
2824                i++;
2825                if (i >= n) {
2826                    return "";
2827                }
2828            }
2829            if (c == '"' || c == '\'') {
2830                String value = parseQuoted(c);
2831                // skip over trailing white space
2832                while (i < n && (c = s.charAt(i)) == ' ') {
2833                    i++;
2834                }
2835                if (i >= n) {
2836                    return value;
2837                } else if (s.charAt(i) == ';') {
2838                    i++;
2839                    return value;
2840                } else {
2841                    throw new RuntimeException(
2842                        "quoted value ended too soon, at position " + i
2843                        + " in '" + s + "'");
2844                }
2845            } else {
2846                String value;
2847                int semi = s.indexOf(';', i);
2848                if (semi >= 0) {
2849                    value = s.substring(i, semi);
2850                    i = semi + 1;
2851                } else {
2852                    value = s.substring(i);
2853                    i = n;
2854                }
2855                return value.trim();
2856            }
2857        }
2858        /**
2859         * Reads a string quoted by a given character. Occurrences of the
2860         * quoting character must be doubled. For example,
2861         * <code>parseQuoted('"')</code> reads <code>"a ""new"" string"</code>
2862         * and returns <code>a "new" string</code>.
2863         */
2864        String parseQuoted(char q) {
2865            char c = s.charAt(i++);
2866            Util.assertTrue(c == q);
2867            valueBuf.setLength(0);
2868            while (i < n) {
2869                c = s.charAt(i);
2870                if (c == q) {
2871                    i++;
2872                    if (i < n) {
2873                        c = s.charAt(i);
2874                        if (c == q) {
2875                            valueBuf.append(c);
2876                            i++;
2877                            continue;
2878                        }
2879                    }
2880                    return valueBuf.toString();
2881                } else {
2882                    valueBuf.append(c);
2883                    i++;
2884                }
2885            }
2886            throw new RuntimeException(
2887                "Connect string '" + s
2888                + "' contains unterminated quoted value '" + valueBuf.toString()
2889                + "'");
2890        }
2891    }
2892
2893    /**
2894     * Combines two integers into a hash code.
2895     */
2896    public static int hash(int i, int j) {
2897        return (i << 4) ^ j;
2898    }
2899
2900    /**
2901     * Computes a hash code from an existing hash code and an object (which
2902     * may be null).
2903     */
2904    public static int hash(int h, Object o) {
2905        int k = (o == null) ? 0 : o.hashCode();
2906        return ((h << 4) | h) ^ k;
2907    }
2908
2909    /**
2910     * Computes a hash code from an existing hash code and an array of objects
2911     * (which may be null).
2912     */
2913    public static int hashArray(int h, Object [] a) {
2914        // The hashcode for a null array and an empty array should be different
2915        // than h, so use magic numbers.
2916        if (a == null) {
2917            return hash(h, 19690429);
2918        }
2919        if (a.length == 0) {
2920            return hash(h, 19690721);
2921        }
2922        for (Object anA : a) {
2923            h = hash(h, anA);
2924        }
2925        return h;
2926    }
2927
2928    /**
2929     * Concatenates one or more arrays.
2930     *
2931     * <p>Resulting array has same element type as first array. Each arrays may
2932     * be empty, but must not be null.
2933     *
2934     * @param a0 First array
2935     * @param as Zero or more subsequent arrays
2936     * @return Array containing all elements
2937     */
2938    public static <T> T[] appendArrays(
2939        T[] a0,
2940        T[]... as)
2941    {
2942        int n = a0.length;
2943        for (T[] a : as) {
2944            n += a.length;
2945        }
2946        T[] copy = Util.copyOf(a0, n);
2947        n = a0.length;
2948        for (T[] a : as) {
2949            System.arraycopy(a, 0, copy, n, a.length);
2950            n += a.length;
2951        }
2952        return copy;
2953    }
2954
2955    /**
2956     * Adds an object to the end of an array.  The resulting array is of the
2957     * same type (e.g. <code>String[]</code>) as the input array.
2958     *
2959     * @param a Array
2960     * @param o Element
2961     * @return New array containing original array plus element
2962     *
2963     * @see #appendArrays
2964     */
2965    public static <T> T[] append(T[] a, T o) {
2966        T[] a2 = Util.copyOf(a, a.length + 1);
2967        a2[a.length] = o;
2968        return a2;
2969    }
2970
2971    /**
2972     * Like <code>{@link java.util.Arrays}.copyOf(double[], int)</code>, but
2973     * exists prior to JDK 1.6.
2974     *
2975     * @param original the array to be copied
2976     * @param newLength the length of the copy to be returned
2977     * @return a copy of the original array, truncated or padded with zeros
2978     *     to obtain the specified length
2979     */
2980    public static double[] copyOf(double[] original, int newLength) {
2981        double[] copy = new double[newLength];
2982        System.arraycopy(
2983            original, 0, copy, 0, Math.min(original.length, newLength));
2984        return copy;
2985    }
2986
2987    /**
2988     * Like <code>{@link java.util.Arrays}.copyOf(int[], int)</code>, but
2989     * exists prior to JDK 1.6.
2990     *
2991     * @param original the array to be copied
2992     * @param newLength the length of the copy to be returned
2993     * @return a copy of the original array, truncated or padded with zeros
2994     *     to obtain the specified length
2995     */
2996    public static int[] copyOf(int[] original, int newLength) {
2997        int[] copy = new int[newLength];
2998        System.arraycopy(
2999            original, 0, copy, 0, Math.min(original.length, newLength));
3000        return copy;
3001    }
3002
3003    /**
3004     * Like <code>{@link java.util.Arrays}.copyOf(long[], int)</code>, but
3005     * exists prior to JDK 1.6.
3006     *
3007     * @param original the array to be copied
3008     * @param newLength the length of the copy to be returned
3009     * @return a copy of the original array, truncated or padded with zeros
3010     *     to obtain the specified length
3011     */
3012    public static long[] copyOf(long[] original, int newLength) {
3013        long[] copy = new long[newLength];
3014        System.arraycopy(
3015            original, 0, copy, 0, Math.min(original.length, newLength));
3016        return copy;
3017    }
3018
3019    /**
3020     * Like <code>{@link java.util.Arrays}.copyOf(Object[], int)</code>, but
3021     * exists prior to JDK 1.6.
3022     *
3023     * @param original the array to be copied
3024     * @param newLength the length of the copy to be returned
3025     * @return a copy of the original array, truncated or padded with zeros
3026     *     to obtain the specified length
3027     */
3028    public static <T> T[] copyOf(T[] original, int newLength) {
3029        //noinspection unchecked
3030        return (T[]) copyOf(original, newLength, original.getClass());
3031    }
3032
3033    /**
3034     * Copies the specified array.
3035     *
3036     * @param original the array to be copied
3037     * @param newLength the length of the copy to be returned
3038     * @param newType the class of the copy to be returned
3039     * @return a copy of the original array, truncated or padded with nulls
3040     *     to obtain the specified length
3041     */
3042    public static <T, U> T[] copyOf(
3043        U[] original, int newLength, Class<? extends T[]> newType)
3044    {
3045        @SuppressWarnings({"unchecked", "RedundantCast"})
3046        T[] copy = ((Object)newType == (Object)Object[].class)
3047            ? (T[]) new Object[newLength]
3048            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
3049        //noinspection SuspiciousSystemArraycopy
3050        System.arraycopy(
3051            original, 0, copy, 0,
3052            Math.min(original.length, newLength));
3053        return copy;
3054    }
3055
3056    /**
3057     * Returns the cumulative amount of time spent accessing the database.
3058     *
3059     * @deprecated Use {@link mondrian.server.monitor.Monitor#getServer()} and
3060     *  {@link mondrian.server.monitor.ServerInfo#sqlStatementExecuteNanos};
3061     *  will be removed in 4.0.
3062     */
3063    public static long dbTimeMillis() {
3064        return databaseMillis;
3065    }
3066
3067    /**
3068     * Adds to the cumulative amount of time spent accessing the database.
3069     *
3070     * @deprecated Will be removed in 4.0.
3071     */
3072    public static void addDatabaseTime(long millis) {
3073        databaseMillis += millis;
3074    }
3075
3076    /**
3077     * Returns the system time less the time spent accessing the database.
3078     * Use this method to figure out how long an operation took: call this
3079     * method before an operation and after an operation, and the difference
3080     * is the amount of non-database time spent.
3081     *
3082     * @deprecated Will be removed in 4.0.
3083     */
3084    public static long nonDbTimeMillis() {
3085        final long systemMillis = System.currentTimeMillis();
3086        return systemMillis - databaseMillis;
3087    }
3088
3089    /**
3090     * Creates a very simple implementation of {@link Validator}. (Only
3091     * useful for resolving trivial expressions.)
3092     */
3093    public static Validator createSimpleValidator(final FunTable funTable) {
3094        return new Validator() {
3095            public Query getQuery() {
3096                return null;
3097            }
3098
3099            public SchemaReader getSchemaReader() {
3100                throw new UnsupportedOperationException();
3101            }
3102
3103            public Exp validate(Exp exp, boolean scalar) {
3104                return exp;
3105            }
3106
3107            public void validate(ParameterExpr parameterExpr) {
3108            }
3109
3110            public void validate(MemberProperty memberProperty) {
3111            }
3112
3113            public void validate(QueryAxis axis) {
3114            }
3115
3116            public void validate(Formula formula) {
3117            }
3118
3119            public FunDef getDef(Exp[] args, String name, Syntax syntax) {
3120                // Very simple resolution. Assumes that there is precisely
3121                // one resolver (i.e. no overloading) and no argument
3122                // conversions are necessary.
3123                List<Resolver> resolvers = funTable.getResolvers(name, syntax);
3124                final Resolver resolver = resolvers.get(0);
3125                final List<Resolver.Conversion> conversionList =
3126                    new ArrayList<Resolver.Conversion>();
3127                final FunDef def =
3128                    resolver.resolve(args, this, conversionList);
3129                assert conversionList.isEmpty();
3130                return def;
3131            }
3132
3133            public boolean alwaysResolveFunDef() {
3134                return false;
3135            }
3136
3137            public boolean canConvert(
3138                int ordinal, Exp fromExp,
3139                int to,
3140                List<Resolver.Conversion> conversions)
3141            {
3142                return true;
3143            }
3144
3145            public boolean requiresExpression() {
3146                return false;
3147            }
3148
3149            public FunTable getFunTable() {
3150                return funTable;
3151            }
3152
3153            public Parameter createOrLookupParam(
3154                boolean definition,
3155                String name,
3156                Type type,
3157                Exp defaultExp,
3158                String description)
3159            {
3160                return null;
3161            }
3162        };
3163    }
3164
3165    /**
3166     * Reads a Reader until it returns EOF and returns the contents as a String.
3167     *
3168     * @param rdr  Reader to Read.
3169     * @param bufferSize size of buffer to allocate for reading.
3170     * @return content of Reader as String
3171     * @throws IOException on I/O error
3172     */
3173    public static String readFully(final Reader rdr, final int bufferSize)
3174        throws IOException
3175    {
3176        if (bufferSize <= 0) {
3177            throw new IllegalArgumentException(
3178                "Buffer size must be greater than 0");
3179        }
3180
3181        final char[] buffer = new char[bufferSize];
3182        final StringBuilder buf = new StringBuilder(bufferSize);
3183
3184        int len;
3185        while ((len = rdr.read(buffer)) != -1) {
3186            buf.append(buffer, 0, len);
3187        }
3188        return buf.toString();
3189    }
3190
3191    /**
3192     * Reads an input stream until it returns EOF and returns the contents as an
3193     * array of bytes.
3194     *
3195     * @param in  Input stream
3196     * @param bufferSize size of buffer to allocate for reading.
3197     * @return content of stream as an array of bytes
3198     * @throws IOException on I/O error
3199     */
3200    public static byte[] readFully(final InputStream in, final int bufferSize)
3201        throws IOException
3202    {
3203        if (bufferSize <= 0) {
3204            throw new IllegalArgumentException(
3205                "Buffer size must be greater than 0");
3206        }
3207
3208        final byte[] buffer = new byte[bufferSize];
3209        final ByteArrayOutputStream baos =
3210            new ByteArrayOutputStream(bufferSize);
3211
3212        int len;
3213        while ((len = in.read(buffer)) != -1) {
3214            baos.write(buffer, 0, len);
3215        }
3216        return baos.toByteArray();
3217    }
3218
3219    /**
3220     * Returns the contents of a URL, substituting tokens.
3221     *
3222     * <p>Replaces the tokens "${key}" if the map is not null and "key" occurs
3223     * in the key-value map.
3224     *
3225     * <p>If the URL string starts with "inline:" the contents are the
3226     * rest of the URL.
3227     *
3228     * @param urlStr  URL string
3229     * @param map Key/value map
3230     * @return Contents of URL with tokens substituted
3231     * @throws IOException on I/O error
3232     */
3233    public static String readURL(final String urlStr, Map<String, String> map)
3234        throws IOException
3235    {
3236        if (urlStr.startsWith("inline:")) {
3237            String content = urlStr.substring("inline:".length());
3238            if (map != null) {
3239                content = Util.replaceProperties(content, map);
3240            }
3241            return content;
3242        } else {
3243            final URL url = new URL(urlStr);
3244            return readURL(url, map);
3245        }
3246    }
3247
3248    /**
3249     * Returns the contents of a URL.
3250     *
3251     * @param url URL
3252     * @return Contents of URL
3253     * @throws IOException on I/O error
3254     */
3255    public static String readURL(final URL url) throws IOException {
3256        return readURL(url, null);
3257    }
3258
3259    /**
3260     * Returns the contents of a URL, substituting tokens.
3261     *
3262     * <p>Replaces the tokens "${key}" if the map is not null and "key" occurs
3263     * in the key-value map.
3264     *
3265     * @param url URL
3266     * @param map Key/value map
3267     * @return Contents of URL with tokens substituted
3268     * @throws IOException on I/O error
3269     */
3270    public static String readURL(
3271        final URL url,
3272        Map<String, String> map)
3273        throws IOException
3274    {
3275        final Reader r =
3276            new BufferedReader(new InputStreamReader(url.openStream()));
3277        final int BUF_SIZE = 8096;
3278        try {
3279            String xmlCatalog = readFully(r, BUF_SIZE);
3280            xmlCatalog = Util.replaceProperties(xmlCatalog, map);
3281            return xmlCatalog;
3282        } finally {
3283            r.close();
3284        }
3285    }
3286
3287    /**
3288     * Gets content via Apache VFS. File must exist and have content
3289     *
3290     * @param url String
3291     * @return Apache VFS FileContent for further processing
3292     * @throws FileSystemException on error
3293     */
3294    public static InputStream readVirtualFile(String url)
3295        throws FileSystemException
3296    {
3297        // Treat catalogUrl as an Apache VFS (Virtual File System) URL.
3298        // VFS handles all of the usual protocols (http:, file:)
3299        // and then some.
3300        FileSystemManager fsManager = VFS.getManager();
3301        if (fsManager == null) {
3302            throw newError("Cannot get virtual file system manager");
3303        }
3304
3305        // Workaround VFS bug.
3306        if (url.startsWith("file://localhost")) {
3307            url = url.substring("file://localhost".length());
3308        }
3309        if (url.startsWith("file:")) {
3310            url = url.substring("file:".length());
3311        }
3312
3313        // work around for VFS bug not closing http sockets
3314        // (Mondrian-585)
3315        if (url.startsWith("http")) {
3316            try {
3317                return new URL(url).openStream();
3318            } catch (IOException e) {
3319                throw newError(
3320                    "Could not read URL: " + url);
3321            }
3322        }
3323
3324        File userDir = new File("").getAbsoluteFile();
3325        FileObject file = fsManager.resolveFile(userDir, url);
3326        FileContent fileContent = null;
3327        try {
3328            // Because of VFS caching, make sure we refresh to get the latest
3329            // file content. This refresh may possibly solve the following
3330            // workaround for defect MONDRIAN-508, but cannot be tested, so we
3331            // will leave the work around for now.
3332            file.refresh();
3333
3334            // Workaround to defect MONDRIAN-508. For HttpFileObjects, verifies
3335            // the URL of the file retrieved matches the URL passed in.  A VFS
3336            // cache bug can cause it to treat URLs with different parameters
3337            // as the same file (e.g. http://blah.com?param=A,
3338            // http://blah.com?param=B)
3339            if (file instanceof HttpFileObject
3340                && !file.getName().getURI().equals(url))
3341            {
3342                fsManager.getFilesCache().removeFile(
3343                    file.getFileSystem(),  file.getName());
3344
3345                file = fsManager.resolveFile(userDir, url);
3346            }
3347
3348            if (!file.isReadable()) {
3349                throw newError(
3350                    "Virtual file is not readable: " + url);
3351            }
3352
3353            fileContent = file.getContent();
3354        } finally {
3355            file.close();
3356        }
3357
3358        if (fileContent == null) {
3359            throw newError(
3360                "Cannot get virtual file content: " + url);
3361        }
3362
3363        return fileContent.getInputStream();
3364    }
3365
3366    public static String readVirtualFileAsString(
3367        String catalogUrl)
3368        throws IOException
3369    {
3370        InputStream in = readVirtualFile(catalogUrl);
3371        try {
3372            final byte[] bytes = Util.readFully(in, 1024);
3373            final char[] chars = new char[bytes.length];
3374            for (int i = 0; i < chars.length; i++) {
3375                chars[i] = (char) bytes[i];
3376            }
3377            return new String(chars);
3378        } finally {
3379            if (in != null) {
3380                in.close();
3381            }
3382        }
3383    }
3384
3385    /**
3386     * Converts a {@link Properties} object to a string-to-string {@link Map}.
3387     *
3388     * @param properties Properties
3389     * @return String-to-string map
3390     */
3391    public static Map<String, String> toMap(final Properties properties) {
3392        return new AbstractMap<String, String>() {
3393            @SuppressWarnings({"unchecked"})
3394            public Set<Entry<String, String>> entrySet() {
3395                return (Set) properties.entrySet();
3396            }
3397        };
3398    }
3399    /**
3400     * Replaces tokens in a string.
3401     *
3402     * <p>Replaces the tokens "${key}" if "key" occurs in the key-value map.
3403     * Otherwise "${key}" is left in the string unchanged.
3404     *
3405     * @param text Source string
3406     * @param env Map of key-value pairs
3407     * @return String with tokens substituted
3408     */
3409    public static String replaceProperties(
3410        String text,
3411        Map<String, String> env)
3412    {
3413        // As of JDK 1.5, cannot use StringBuilder - appendReplacement requires
3414        // the antediluvian StringBuffer.
3415        StringBuffer buf = new StringBuffer(text.length() + 200);
3416
3417        Pattern pattern = Pattern.compile("\\$\\{([^${}]+)\\}");
3418        Matcher matcher = pattern.matcher(text);
3419        while (matcher.find()) {
3420            String varName = matcher.group(1);
3421            String varValue = env.get(varName);
3422            if (varValue != null) {
3423                matcher.appendReplacement(buf, varValue);
3424            } else {
3425                matcher.appendReplacement(buf, "\\${$1}");
3426            }
3427        }
3428        matcher.appendTail(buf);
3429
3430        return buf.toString();
3431    }
3432
3433    public static String printMemory() {
3434        return printMemory(null);
3435    }
3436
3437    public static String printMemory(String msg) {
3438        final Runtime rt = Runtime.getRuntime();
3439        final long freeMemory = rt.freeMemory();
3440        final long totalMemory = rt.totalMemory();
3441        final StringBuilder buf = new StringBuilder(64);
3442
3443        buf.append("FREE_MEMORY:");
3444        if (msg != null) {
3445            buf.append(msg);
3446            buf.append(':');
3447        }
3448        buf.append(' ');
3449        buf.append(freeMemory / 1024);
3450        buf.append("kb ");
3451
3452        long hundredths = (freeMemory * 10000) / totalMemory;
3453
3454        buf.append(hundredths / 100);
3455        hundredths %= 100;
3456        if (hundredths >= 10) {
3457            buf.append('.');
3458        } else {
3459            buf.append(".0");
3460        }
3461        buf.append(hundredths);
3462        buf.append('%');
3463
3464        return buf.toString();
3465    }
3466
3467    /**
3468     * Casts a Set to a Set with a different element type.
3469     *
3470     * @param set Set
3471     * @return Set of desired type
3472     */
3473    @SuppressWarnings({"unchecked"})
3474    public static <T> Set<T> cast(Set<?> set) {
3475        return (Set<T>) set;
3476    }
3477
3478    /**
3479     * Casts a List to a List with a different element type.
3480     *
3481     * @param list List
3482     * @return List of desired type
3483     */
3484    @SuppressWarnings({"unchecked"})
3485    public static <T> List<T> cast(List<?> list) {
3486        return (List<T>) list;
3487    }
3488
3489    /**
3490     * Returns whether it is safe to cast a collection to a collection with a
3491     * given element type.
3492     *
3493     * @param collection Collection
3494     * @param clazz Target element type
3495     * @param <T> Element type
3496     * @return Whether all not-null elements of the collection are instances of
3497     *   element type
3498     */
3499    public static <T> boolean canCast(
3500        Collection<?> collection,
3501        Class<T> clazz)
3502    {
3503        for (Object o : collection) {
3504            if (o != null && !clazz.isInstance(o)) {
3505                return false;
3506            }
3507        }
3508        return true;
3509    }
3510
3511    /**
3512     * Casts a collection to iterable.
3513     *
3514     * Under JDK 1.4, {@link Collection} objects do not implement
3515     * {@link Iterable}, so this method inserts a casting wrapper. (Since
3516     * Iterable does not exist under JDK 1.4, they will have been compiled
3517     * under JDK 1.5 or later, then retrowoven to 1.4 class format. References
3518     * to Iterable will have been replaced with references to
3519     * <code>com.rc.retroweaver.runtime.Retroweaver_</code>.
3520     *
3521     * <p>Under later JDKs this method is trivial. This method can be deleted
3522     * when we discontinue support for JDK 1.4.
3523     *
3524     * @param iterable Object which ought to be iterable
3525     * @param <T> Element type
3526     * @return Object cast to Iterable
3527     */
3528    public static <T> Iterable<T> castToIterable(
3529        final Object iterable)
3530    {
3531        if (Util.Retrowoven
3532            && !(iterable instanceof Iterable))
3533        {
3534            return new Iterable<T>() {
3535                public Iterator<T> iterator() {
3536                    return ((Collection<T>) iterable).iterator();
3537                }
3538            };
3539        }
3540        return (Iterable<T>) iterable;
3541    }
3542
3543    /**
3544     * Looks up an enumeration by name, returning null if null or not valid.
3545     *
3546     * @param clazz Enumerated type
3547     * @param name Name of constant
3548     */
3549    public static <E extends Enum<E>> E lookup(Class<E> clazz, String name) {
3550        return lookup(clazz, name, null);
3551    }
3552
3553    /**
3554     * Looks up an enumeration by name, returning a given default value if null
3555     * or not valid.
3556     *
3557     * @param clazz Enumerated type
3558     * @param name Name of constant
3559     * @param defaultValue Default value if constant is not found
3560     * @return Value, or null if name is null or value does not exist
3561     */
3562    public static <E extends Enum<E>> E lookup(
3563        Class<E> clazz, String name, E defaultValue)
3564    {
3565        if (name == null) {
3566            return defaultValue;
3567        }
3568        try {
3569            return Enum.valueOf(clazz, name);
3570        } catch (IllegalArgumentException e) {
3571            return defaultValue;
3572        }
3573    }
3574
3575    /**
3576     * Make a BigDecimal from a double. On JDK 1.5 or later, the BigDecimal
3577     * precision reflects the precision of the double while with JDK 1.4
3578     * this is not the case.
3579     *
3580     * @param d the input double
3581     * @return the BigDecimal
3582     */
3583    public static BigDecimal makeBigDecimalFromDouble(double d) {
3584        return compatible.makeBigDecimalFromDouble(d);
3585    }
3586
3587    /**
3588     * Returns a literal pattern String for the specified String.
3589     *
3590     * <p>Specification as for {@link Pattern#quote(String)}, which was
3591     * introduced in JDK 1.5.
3592     *
3593     * @param s The string to be literalized
3594     * @return A literal string replacement
3595     */
3596    public static String quotePattern(String s) {
3597        return compatible.quotePattern(s);
3598    }
3599
3600    /**
3601     * Generates a unique id.
3602     *
3603     * <p>From JDK 1.5 onwards, uses a {@code UUID}.
3604     *
3605     * @return A unique id
3606     */
3607    public static String generateUuidString() {
3608        return compatible.generateUuidString();
3609    }
3610
3611    /**
3612     * Compiles a script to yield a Java interface.
3613     *
3614     * <p>Only valid JDK 1.6 and higher; fails on JDK 1.5 and earlier.</p>
3615     *
3616     * @param iface Interface script should implement
3617     * @param script Script code
3618     * @param engineName Name of engine (e.g. "JavaScript")
3619     * @param <T> Interface
3620     * @return Object that implements given interface
3621     */
3622    public static <T> T compileScript(
3623        Class<T> iface,
3624        String script,
3625        String engineName)
3626    {
3627        return compatible.compileScript(iface, script, engineName);
3628    }
3629
3630    /**
3631     * Removes a thread local from the current thread.
3632     *
3633     * <p>From JDK 1.5 onwards, calls {@link ThreadLocal#remove()}; before
3634     * that, no-ops.</p>
3635     *
3636     * @param threadLocal Thread local
3637     * @param <T> Type
3638     */
3639    public static <T> void threadLocalRemove(ThreadLocal<T> threadLocal) {
3640        compatible.threadLocalRemove(threadLocal);
3641    }
3642
3643    /**
3644     * Creates a hash set that, like {@link java.util.IdentityHashMap},
3645     * compares keys using identity.
3646     *
3647     * @param <T> Element type
3648     * @return Set
3649     */
3650    public static <T> Set<T> newIdentityHashSet() {
3651        return compatible.newIdentityHashSet();
3652    }
3653
3654    /**
3655     * Creates a new udf instance from the given udf class.
3656     *
3657     * @param udfClass the class to create new instance for
3658     * @param functionName Function name, or null
3659     * @return an instance of UserDefinedFunction
3660     */
3661    public static UserDefinedFunction createUdf(
3662        Class<? extends UserDefinedFunction> udfClass,
3663        String functionName)
3664    {
3665        // Instantiate class with default constructor.
3666        UserDefinedFunction udf;
3667        String className = udfClass.getName();
3668        String functionNameOrEmpty =
3669            functionName == null
3670                ? ""
3671                : functionName;
3672
3673        // Find a constructor.
3674        Constructor<?> constructor;
3675        Object[] args = {};
3676
3677        // 0. Check that class is public and top-level or static.
3678        // Before JDK 1.5, inner classes are impossible; retroweaver cannot
3679        // handle the getEnclosingClass method, so skip the check.
3680        if (!Modifier.isPublic(udfClass.getModifiers())
3681            || (!PreJdk15
3682                && udfClass.getEnclosingClass() != null
3683                && !Modifier.isStatic(udfClass.getModifiers())))
3684        {
3685            throw MondrianResource.instance().UdfClassMustBePublicAndStatic.ex(
3686                functionName,
3687                className);
3688        }
3689
3690        // 1. Look for a constructor "public Udf(String name)".
3691        try {
3692            constructor = udfClass.getConstructor(String.class);
3693            if (Modifier.isPublic(constructor.getModifiers())) {
3694                args = new Object[] {functionName};
3695            } else {
3696                constructor = null;
3697            }
3698        } catch (NoSuchMethodException e) {
3699            constructor = null;
3700        }
3701        // 2. Otherwise, look for a constructor "public Udf()".
3702        if (constructor == null) {
3703            try {
3704                constructor = udfClass.getConstructor();
3705                if (Modifier.isPublic(constructor.getModifiers())) {
3706                    args = new Object[] {};
3707                } else {
3708                    constructor = null;
3709                }
3710            } catch (NoSuchMethodException e) {
3711                constructor = null;
3712            }
3713        }
3714        // 3. Else, no constructor suitable.
3715        if (constructor == null) {
3716            throw MondrianResource.instance().UdfClassWrongIface.ex(
3717                functionNameOrEmpty,
3718                className,
3719                UserDefinedFunction.class.getName());
3720        }
3721        // Instantiate class.
3722        try {
3723            udf = (UserDefinedFunction) constructor.newInstance(args);
3724        } catch (InstantiationException e) {
3725            throw MondrianResource.instance().UdfClassWrongIface.ex(
3726                functionNameOrEmpty,
3727                className, UserDefinedFunction.class.getName());
3728        } catch (IllegalAccessException e) {
3729            throw MondrianResource.instance().UdfClassWrongIface.ex(
3730                functionName,
3731                className,
3732                UserDefinedFunction.class.getName());
3733        } catch (ClassCastException e) {
3734            throw MondrianResource.instance().UdfClassWrongIface.ex(
3735                functionNameOrEmpty,
3736                className,
3737                UserDefinedFunction.class.getName());
3738        } catch (InvocationTargetException e) {
3739            throw MondrianResource.instance().UdfClassWrongIface.ex(
3740                functionName,
3741                className,
3742                UserDefinedFunction.class.getName());
3743        }
3744
3745        return udf;
3746    }
3747
3748    /**
3749     * Check the resultSize against the result limit setting. Throws
3750     * LimitExceededDuringCrossjoin exception if limit exceeded.
3751     *
3752     * When it is called from RolapNativeSet.checkCrossJoin(), it is only
3753     * possible to check the known input size, because the final CJ result
3754     * will come from the DB(and will be checked against the limit when
3755     * fetching from the JDBC result set, in SqlTupleReader.prepareTuples())
3756     *
3757     * @param resultSize Result limit
3758     * @throws ResourceLimitExceededException
3759     */
3760    public static void checkCJResultLimit(long resultSize) {
3761        int resultLimit = MondrianProperties.instance().ResultLimit.get();
3762
3763        // Throw an exeption, if the size of the crossjoin exceeds the result
3764        // limit.
3765        if (resultLimit > 0 && resultLimit < resultSize) {
3766            throw MondrianResource.instance().LimitExceededDuringCrossjoin.ex(
3767                resultSize, resultLimit);
3768        }
3769
3770        // Throw an exception if the crossjoin exceeds a reasonable limit.
3771        // (Yes, 4 billion is a reasonable limit.)
3772        if (resultSize > Integer.MAX_VALUE) {
3773            throw MondrianResource.instance().LimitExceededDuringCrossjoin.ex(
3774                resultSize, Integer.MAX_VALUE);
3775        }
3776    }
3777
3778    /**
3779     * Converts an olap4j connect string into a legacy mondrian connect string.
3780     *
3781     * <p>For example,
3782     * "jdbc:mondrian:Datasource=jdbc/SampleData;Catalog=foodmart/FoodMart.xml;"
3783     * becomes
3784     * "Provider=Mondrian;
3785     * Datasource=jdbc/SampleData;Catalog=foodmart/FoodMart.xml;"
3786     *
3787     * <p>This method is intended to allow legacy applications (such as JPivot
3788     * and Mondrian's XMLA server) to continue to create connections using
3789     * Mondrian's legacy connection API even when they are handed an olap4j
3790     * connect string.
3791     *
3792     * @param url olap4j connect string
3793     * @return mondrian connect string, or null if cannot be converted
3794     */
3795    public static String convertOlap4jConnectStringToNativeMondrian(
3796        String url)
3797    {
3798        if (url.startsWith("jdbc:mondrian:")) {
3799            return "Provider=Mondrian; "
3800                + url.substring("jdbc:mondrian:".length());
3801        }
3802        return null;
3803    }
3804
3805    /**
3806     * Checks if a String is whitespace, empty ("") or null.</p>
3807     *
3808     * <pre>
3809     * StringUtils.isBlank(null) = true
3810     * StringUtils.isBlank("") = true
3811     * StringUtils.isBlank(" ") = true
3812     * StringUtils.isBlank("bob") = false
3813     * StringUtils.isBlank(" bob ") = false
3814     * </pre>
3815     *
3816     * <p>(Copied from commons-lang.)
3817     *
3818     * @param str the String to check, may be null
3819     * @return <code>true</code> if the String is null, empty or whitespace
3820     */
3821    public static boolean isBlank(String str) {
3822        final int strLen;
3823        if (str == null || (strLen = str.length()) == 0) {
3824            return true;
3825        }
3826        for (int i = 0; i < strLen; i++) {
3827            if (!Character.isWhitespace(str.charAt(i))) {
3828                return false;
3829            }
3830        }
3831        return true;
3832    }
3833
3834    /**
3835     * Returns a role which has access to everything.
3836     * @param schema A schema to bind this role to.
3837     * @return A role with root access to the schema.
3838     */
3839    public static Role createRootRole(Schema schema) {
3840        RoleImpl role = new RoleImpl();
3841        role.grant(schema, Access.ALL);
3842        role.makeImmutable();
3843        return role;
3844    }
3845
3846    /**
3847     * Tries to find the cube from which a dimension is taken.
3848     * It considers private dimensions, shared dimensions and virtual
3849     * dimensions. If it can't determine with certitude the origin
3850     * of the dimension, it returns null.
3851     */
3852    public static Cube getDimensionCube(Dimension dimension) {
3853        final Cube[] cubes = dimension.getSchema().getCubes();
3854        for (Cube cube : cubes) {
3855            for (Dimension dimension1 : cube.getDimensions()) {
3856                // If the dimensions have the same identity,
3857                // we found an access rule.
3858                if (dimension == dimension1) {
3859                    return cube;
3860                }
3861                // If the passed dimension argument is of class
3862                // RolapCubeDimension, we must validate the cube
3863                // assignment and make sure the cubes are the same.
3864                // If not, skip to the next grant.
3865                if (dimension instanceof RolapCubeDimension
3866                    && dimension.equals(dimension1)
3867                    && !((RolapCubeDimension)dimension1)
3868                    .getCube()
3869                    .equals(cube))
3870                {
3871                    continue;
3872                }
3873                // Last thing is to allow for equality correspondences
3874                // to work with virtual cubes.
3875                if (cube instanceof RolapCube
3876                    && ((RolapCube)cube).isVirtual()
3877                    && dimension.equals(dimension1))
3878                {
3879                    return cube;
3880                }
3881            }
3882        }
3883        return null;
3884    }
3885
3886    /**
3887     * Similar to {@link ClassLoader#getResource(String)}, except the lookup
3888     *  is in reverse order.<br>
3889     *  i.e. returns the resource from the supplied classLoader or the
3890     *  one closest to it in the hierarchy, instead of the closest to the root
3891     *  class loader
3892     * @param classLoader The class loader to fetch from
3893     * @param name The resource name
3894     * @return A URL object for reading the resource, or null if the resource
3895     * could not be found or the invoker doesn't have adequate privileges to get
3896     * the resource.
3897     * @see ClassLoader#getResource(String)
3898     * @see ClassLoader#getResources(String)
3899     */
3900    public static URL getClosestResource(ClassLoader classLoader, String name) {
3901        URL resource = null;
3902        try {
3903            // The last resource will be from the nearest ClassLoader.
3904            Enumeration<URL> resourceCandidates =
3905                classLoader.getResources(name);
3906            while (resourceCandidates.hasMoreElements()) {
3907                resource = resourceCandidates.nextElement();
3908            }
3909        } catch (IOException ioe) {
3910            // ignore exception - it's OK if file is not found
3911            // just keep getResource contract and return null
3912            Util.discard(ioe);
3913        }
3914        return resource;
3915    }
3916
3917    public static abstract class AbstractFlatList<T>
3918        implements List<T>, RandomAccess
3919    {
3920        protected final List<T> asArrayList() {
3921            //noinspection unchecked
3922            return Arrays.asList((T[]) toArray());
3923        }
3924
3925        public Iterator<T> iterator() {
3926            return asArrayList().iterator();
3927        }
3928
3929        public ListIterator<T> listIterator() {
3930            return asArrayList().listIterator();
3931        }
3932
3933        public boolean isEmpty() {
3934            return false;
3935        }
3936
3937        public boolean add(Object t) {
3938            throw new UnsupportedOperationException();
3939        }
3940
3941        public boolean addAll(Collection<? extends T> c) {
3942            throw new UnsupportedOperationException();
3943        }
3944
3945        public boolean addAll(int index, Collection<? extends T> c) {
3946            throw new UnsupportedOperationException();
3947        }
3948
3949        public boolean removeAll(Collection<?> c) {
3950            throw new UnsupportedOperationException();
3951        }
3952
3953        public boolean retainAll(Collection<?> c) {
3954            throw new UnsupportedOperationException();
3955        }
3956
3957        public void clear() {
3958            throw new UnsupportedOperationException();
3959        }
3960
3961        public T set(int index, Object element) {
3962            throw new UnsupportedOperationException();
3963        }
3964
3965        public void add(int index, Object element) {
3966            throw new UnsupportedOperationException();
3967        }
3968
3969        public T remove(int index) {
3970            throw new UnsupportedOperationException();
3971        }
3972
3973        public ListIterator<T> listIterator(int index) {
3974            return asArrayList().listIterator(index);
3975        }
3976
3977        public List<T> subList(int fromIndex, int toIndex) {
3978            return asArrayList().subList(fromIndex, toIndex);
3979        }
3980
3981        public boolean contains(Object o) {
3982            return indexOf(o) >= 0;
3983        }
3984
3985        public boolean containsAll(Collection<?> c) {
3986            Iterator<?> e = c.iterator();
3987            while (e.hasNext()) {
3988                if (!contains(e.next())) {
3989                    return false;
3990                }
3991            }
3992            return true;
3993        }
3994
3995        public boolean remove(Object o) {
3996            throw new UnsupportedOperationException();
3997        }
3998    }
3999
4000    /**
4001     * List that stores its two elements in the two members of the class.
4002     * Unlike {@link java.util.ArrayList} or
4003     * {@link java.util.Arrays#asList(Object[])} there is
4004     * no array, only one piece of memory allocated, therefore is very compact
4005     * and cache and CPU efficient.
4006     *
4007     * <p>The list is read-only, cannot be modified or resized, and neither
4008     * of the elements can be null.
4009     *
4010     * <p>The list is created via {@link Util#flatList(Object[])}.
4011     *
4012     * @see mondrian.olap.Util.Flat3List
4013     * @param <T>
4014     */
4015    protected static class Flat2List<T> extends AbstractFlatList<T> {
4016        private final T t0;
4017        private final T t1;
4018
4019        Flat2List(T t0, T t1) {
4020            this.t0 = t0;
4021            this.t1 = t1;
4022            assert t0 != null;
4023            assert t1 != null;
4024        }
4025
4026        public String toString() {
4027            return "[" + t0 + ", " + t1 + "]";
4028        }
4029
4030        public T get(int index) {
4031            switch (index) {
4032            case 0:
4033                return t0;
4034            case 1:
4035                return t1;
4036            default:
4037                throw new IndexOutOfBoundsException("index " + index);
4038            }
4039        }
4040
4041        public int size() {
4042            return 2;
4043        }
4044
4045        public boolean equals(Object o) {
4046            if (o instanceof Flat2List) {
4047                Flat2List that = (Flat2List) o;
4048                return Util.equals(this.t0, that.t0)
4049                    && Util.equals(this.t1, that.t1);
4050            }
4051            return Arrays.asList(t0, t1).equals(o);
4052        }
4053
4054        public int hashCode() {
4055            int h = 1;
4056            h = h * 31 + t0.hashCode();
4057            h = h * 31 + t1.hashCode();
4058            return h;
4059        }
4060
4061        public int indexOf(Object o) {
4062            if (t0.equals(o)) {
4063                return 0;
4064            }
4065            if (t1.equals(o)) {
4066                return 1;
4067            }
4068            return -1;
4069        }
4070
4071        public int lastIndexOf(Object o) {
4072            if (t1.equals(o)) {
4073                return 1;
4074            }
4075            if (t0.equals(o)) {
4076                return 0;
4077            }
4078            return -1;
4079        }
4080
4081        @SuppressWarnings({"unchecked"})
4082        public <T2> T2[] toArray(T2[] a) {
4083            a[0] = (T2) t0;
4084            a[1] = (T2) t1;
4085            return a;
4086        }
4087
4088        public Object[] toArray() {
4089            return new Object[] {t0, t1};
4090        }
4091    }
4092
4093    /**
4094     * List that stores its three elements in the three members of the class.
4095     * Unlike {@link java.util.ArrayList} or
4096     * {@link java.util.Arrays#asList(Object[])} there is
4097     * no array, only one piece of memory allocated, therefore is very compact
4098     * and cache and CPU efficient.
4099     *
4100     * <p>The list is read-only, cannot be modified or resized, and none
4101     * of the elements can be null.
4102     *
4103     * <p>The list is created via {@link Util#flatList(Object[])}.
4104     *
4105     * @see mondrian.olap.Util.Flat2List
4106     * @param <T>
4107     */
4108    protected static class Flat3List<T> extends AbstractFlatList<T> {
4109        private final T t0;
4110        private final T t1;
4111        private final T t2;
4112
4113        Flat3List(T t0, T t1, T t2) {
4114            this.t0 = t0;
4115            this.t1 = t1;
4116            this.t2 = t2;
4117            assert t0 != null;
4118            assert t1 != null;
4119            assert t2 != null;
4120        }
4121
4122        public String toString() {
4123            return "[" + t0 + ", " + t1 + ", " + t2 + "]";
4124        }
4125
4126        public T get(int index) {
4127            switch (index) {
4128            case 0:
4129                return t0;
4130            case 1:
4131                return t1;
4132            case 2:
4133                return t2;
4134            default:
4135                throw new IndexOutOfBoundsException("index " + index);
4136            }
4137        }
4138
4139        public int size() {
4140            return 3;
4141        }
4142
4143        public boolean equals(Object o) {
4144            if (o instanceof Flat3List) {
4145                Flat3List that = (Flat3List) o;
4146                return Util.equals(this.t0, that.t0)
4147                    && Util.equals(this.t1, that.t1)
4148                    && Util.equals(this.t2, that.t2);
4149            }
4150            return o.equals(this);
4151        }
4152
4153        public int hashCode() {
4154            int h = 1;
4155            h = h * 31 + t0.hashCode();
4156            h = h * 31 + t1.hashCode();
4157            h = h * 31 + t2.hashCode();
4158            return h;
4159        }
4160
4161        public int indexOf(Object o) {
4162            if (t0.equals(o)) {
4163                return 0;
4164            }
4165            if (t1.equals(o)) {
4166                return 1;
4167            }
4168            if (t2.equals(o)) {
4169                return 2;
4170            }
4171            return -1;
4172        }
4173
4174        public int lastIndexOf(Object o) {
4175            if (t2.equals(o)) {
4176                return 2;
4177            }
4178            if (t1.equals(o)) {
4179                return 1;
4180            }
4181            if (t0.equals(o)) {
4182                return 0;
4183            }
4184            return -1;
4185        }
4186
4187        @SuppressWarnings({"unchecked"})
4188        public <T2> T2[] toArray(T2[] a) {
4189            a[0] = (T2) t0;
4190            a[1] = (T2) t1;
4191            a[2] = (T2) t2;
4192            return a;
4193        }
4194
4195        public Object[] toArray() {
4196            return new Object[] {t0, t1, t2};
4197        }
4198    }
4199
4200    /**
4201     * Garbage-collecting iterator. Iterates over a collection of references,
4202     * and if any of the references has been garbage-collected, removes it from
4203     * the collection.
4204     *
4205     * @param <T> Element type
4206     */
4207    public static class GcIterator<T> implements Iterator<T> {
4208        private final Iterator<? extends Reference<T>> iterator;
4209        private boolean hasNext;
4210        private T next;
4211
4212        public GcIterator(Iterator<? extends Reference<T>> iterator) {
4213            this.iterator = iterator;
4214            this.hasNext = true;
4215            moveToNext();
4216        }
4217
4218        /**
4219         * Creates an iterator over a collection of references.
4220         *
4221         * @param referenceIterable Collection of references
4222         * @param <T2> element type
4223         * @return iterable over collection
4224         */
4225        public static <T2> Iterable<T2> over(
4226            final Iterable<? extends Reference<T2>> referenceIterable)
4227        {
4228            return new Iterable<T2>() {
4229                public Iterator<T2> iterator() {
4230                    return new GcIterator<T2>(referenceIterable.iterator());
4231                }
4232            };
4233        }
4234
4235        private void moveToNext() {
4236            while (iterator.hasNext()) {
4237                final Reference<T> ref = iterator.next();
4238                next = ref.get();
4239                if (next != null) {
4240                    return;
4241                }
4242                iterator.remove();
4243            }
4244            hasNext = false;
4245        }
4246
4247        public boolean hasNext() {
4248            return hasNext;
4249        }
4250
4251        public T next() {
4252            final T next1 = next;
4253            moveToNext();
4254            return next1;
4255        }
4256
4257        public void remove() {
4258            throw new UnsupportedOperationException();
4259        }
4260    }
4261
4262    public static interface Functor1<RT, PT> {
4263        RT apply(PT param);
4264    }
4265
4266    public static <T> Functor1<T, T> identityFunctor() {
4267        //noinspection unchecked
4268        return (Functor1) IDENTITY_FUNCTOR;
4269    }
4270
4271    private static final Functor1 IDENTITY_FUNCTOR =
4272        new Functor1<Object, Object>() {
4273            public Object apply(Object param) {
4274                return param;
4275            }
4276        };
4277
4278    public static <PT> Functor1<Boolean, PT> trueFunctor() {
4279        //noinspection unchecked
4280        return (Functor1) TRUE_FUNCTOR;
4281    }
4282
4283    public static <PT> Functor1<Boolean, PT> falseFunctor() {
4284        //noinspection unchecked
4285        return (Functor1) FALSE_FUNCTOR;
4286    }
4287
4288    private static final Functor1 TRUE_FUNCTOR =
4289        new Functor1<Boolean, Object>() {
4290            public Boolean apply(Object param) {
4291                return true;
4292            }
4293        };
4294
4295    private static final Functor1 FALSE_FUNCTOR =
4296        new Functor1<Boolean, Object>() {
4297            public Boolean apply(Object param) {
4298                return false;
4299            }
4300        };
4301
4302    /**
4303     * Information about memory usage.
4304     *
4305     * @see mondrian.olap.Util#getMemoryInfo()
4306     */
4307    public interface MemoryInfo {
4308        Usage get();
4309
4310        public interface Usage {
4311            long getUsed();
4312            long getCommitted();
4313            long getMax();
4314        }
4315    }
4316
4317    /**
4318     * A {@link Comparator} implementation which can deal
4319     * correctly with {@link RolapUtil#sqlNullValue}.
4320     */
4321    public static class SqlNullSafeComparator
4322        implements Comparator<Comparable>
4323    {
4324        public static final SqlNullSafeComparator instance =
4325            new SqlNullSafeComparator();
4326
4327        private SqlNullSafeComparator() {
4328        }
4329
4330        public int compare(Comparable o1, Comparable o2) {
4331            if (o1 == RolapUtil.sqlNullValue) {
4332                return -1;
4333            }
4334            if (o2 == RolapUtil.sqlNullValue) {
4335                return 1;
4336            }
4337            return o1.compareTo(o2);
4338        }
4339    }
4340
4341    /**
4342     * This class implements the Knuth-Morris-Pratt algorithm
4343     * to search within a byte array for a token byte array.
4344     */
4345    public static class ByteMatcher {
4346        private final int[] matcher;
4347        public final byte[] key;
4348        public ByteMatcher(byte[] key) {
4349            this.key = key;
4350            this.matcher = compile(key);
4351        }
4352        /**
4353         * Matches the pre-compiled byte array token against a
4354         * byte array variable and returns the index of the key
4355         * within the array.
4356         * @param a An array of bytes to search for.
4357         * @return -1 if not found, or the index (0 based) of the match.
4358         */
4359        public int match(byte[] a) {
4360            int j = 0;
4361            for (int i = 0; i < a.length; i++) {
4362                while (j > 0 && key[j] != a[i]) {
4363                    j = matcher[j - 1];
4364                }
4365                if (a[i] == key[j]) {
4366                    j++;
4367                }
4368                if (key.length == j) {
4369                    return
4370                        i - key.length + 1;
4371                }
4372            }
4373            return -1;
4374        }
4375        private int[] compile(byte[] key) {
4376            int[] matcher = new int[key.length];
4377            int j = 0;
4378            for (int i = 1; i < key.length; i++) {
4379                while (j > 0 && key[j] != key[i]) {
4380                    j = matcher[j - 1];
4381                }
4382                if (key[i] == key[j]) {
4383                    j++;
4384                }
4385                matcher[i] = j;
4386            }
4387            return matcher;
4388        }
4389    }
4390
4391    /**
4392     * Transforms a list into a map for which all the keys return
4393     * a null value associated to it.
4394     *
4395     * <p>The list passed as an argument will be used to back
4396     * the map returned and as many methods are overridden as
4397     * possible to make sure that we don't iterate over the backing
4398     * list when creating it and when performing operations like
4399     * .size(), entrySet() and contains().
4400     *
4401     * <p>The returned map is to be considered immutable. It will
4402     * throw an {@link UnsupportedOperationException} if attempts to
4403     * modify it are made.
4404     */
4405    public static <K, V> Map<K, V> toNullValuesMap(List<K> list) {
4406        return new NullValuesMap<K, V>(list);
4407    }
4408
4409    private static class NullValuesMap<K, V> extends AbstractMap<K, V> {
4410        private final List<K> list;
4411        private NullValuesMap(List<K> list) {
4412            super();
4413            this.list = Collections.unmodifiableList(list);
4414        }
4415        public Set<Entry<K, V>> entrySet() {
4416            return new AbstractSet<Entry<K, V>>() {
4417                public Iterator<Entry<K, V>>
4418                    iterator()
4419                {
4420                    return new Iterator<Entry<K, V>>() {
4421                        private int pt = -1;
4422                        public void remove() {
4423                            throw new UnsupportedOperationException();
4424                        }
4425                        @SuppressWarnings("unchecked")
4426                        public Entry<K, V> next() {
4427                            return new AbstractMapEntry(
4428                                list.get(++pt), null) {};
4429                        }
4430                        public boolean hasNext() {
4431                            return pt < list.size();
4432                        }
4433                    };
4434                }
4435                public int size() {
4436                    return list.size();
4437                }
4438                public boolean contains(Object o) {
4439                    if (o instanceof Entry) {
4440                        if (list.contains(((Entry) o).getKey())) {
4441                            return true;
4442                        }
4443                    }
4444                    return false;
4445                }
4446            };
4447        }
4448        public Set<K> keySet() {
4449            return new AbstractSet<K>() {
4450                public Iterator<K> iterator() {
4451                    return new Iterator<K>() {
4452                        private int pt = -1;
4453                        public void remove() {
4454                            throw new UnsupportedOperationException();
4455                        }
4456                        public K next() {
4457                            return list.get(++pt);
4458                        }
4459                        public boolean hasNext() {
4460                            return pt < list.size();
4461                        }
4462                    };
4463                }
4464                public int size() {
4465                    return list.size();
4466                }
4467                public boolean contains(Object o) {
4468                    return list.contains(o);
4469                }
4470            };
4471        }
4472        public Collection<V> values() {
4473            return new AbstractList<V>() {
4474                public V get(int index) {
4475                    return null;
4476                }
4477                public int size() {
4478                    return list.size();
4479                }
4480                public boolean contains(Object o) {
4481                    if (o == null && size() > 0) {
4482                        return true;
4483                    } else {
4484                        return false;
4485                    }
4486                }
4487            };
4488        }
4489        public V get(Object key) {
4490            return null;
4491        }
4492        public boolean containsKey(Object key) {
4493            return list.contains(key);
4494        }
4495        public boolean containsValue(Object o) {
4496            if (o == null && size() > 0) {
4497                return true;
4498            } else {
4499                return false;
4500            }
4501        }
4502    }
4503}
4504
4505// End Util.java