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) 2009-2012 Pentaho and others
008// All Rights Reserved.
009*/
010package mondrian.olap.fun;
011
012import mondrian.calc.*;
013import mondrian.calc.impl.AbstractListCalc;
014import mondrian.calc.impl.DelegatingTupleList;
015import mondrian.mdx.*;
016import mondrian.olap.*;
017import mondrian.olap.type.Type;
018import mondrian.resource.MondrianResource;
019
020import org.apache.log4j.Logger;
021
022import org.olap4j.impl.Olap4jUtil;
023
024import java.util.*;
025
026import static mondrian.olap.fun.NativizeSetFunDef.NativeElementType.*;
027
028/**
029 * Definition of the <code>NativizeSet</code> MDX function.
030 *
031 * @author jrand
032 * @since Oct 14, 2009
033 */
034public class NativizeSetFunDef extends FunDefBase {
035    /*
036     * Static final fields.
037     */
038    protected static final Logger LOGGER =
039        Logger.getLogger(NativizeSetFunDef.class);
040
041    private static final String SENTINEL_PREFIX = "_Nativized_Sentinel_";
042    private static final String MEMBER_NAME_PREFIX = "_Nativized_Member_";
043    private static final String SET_NAME_PREFIX = "_Nativized_Set_";
044    private static final List<Class<? extends FunDef>> functionWhitelist =
045        Arrays.<Class<? extends FunDef>>asList(
046            CacheFunDef.class,
047            SetFunDef.class,
048            CrossJoinFunDef.class,
049            NativizeSetFunDef.class);
050
051    static final ReflectiveMultiResolver Resolver = new ReflectiveMultiResolver(
052        "NativizeSet",
053        "NativizeSet(<Set>)",
054        "Tries to natively evaluate <Set>.",
055        new String[] {"fxx"},
056        NativizeSetFunDef.class);
057
058    /*
059     * Instance final fields.
060     */
061    private final SubstitutionMap substitutionMap = new SubstitutionMap();
062    private final HashSet<Dimension> dimensions =
063        new LinkedHashSet<Dimension>();
064
065    private boolean isFirstCompileCall = true;
066
067    /*
068     * Instance non-final fields.
069     */
070    private Exp originalExp;
071    private static final String ESTIMATE_MESSAGE =
072        "isHighCardinality=%b: estimate=%,d threshold=%,d";
073    private static final String PARTIAL_ESTIMATE_MESSAGE =
074        "isHighCardinality=%b: partial estimate=%,d threshold=%,d";
075
076    public NativizeSetFunDef(FunDef dummyFunDef) {
077        super(dummyFunDef);
078        LOGGER.debug("---- NativizeSetFunDef constructor");
079    }
080
081    public Exp createCall(Validator validator, Exp[] args) {
082        LOGGER.debug("NativizeSetFunDef createCall");
083        ResolvedFunCall call =
084            (ResolvedFunCall) super.createCall(validator, args);
085        call.accept(new FindLevelsVisitor(substitutionMap, dimensions));
086        return call;
087    }
088
089    public Calc compileCall(ResolvedFunCall call, ExpCompiler compiler) {
090        LOGGER.debug("NativizeSetFunDef compileCall");
091        Exp funArg = call.getArg(0);
092
093        if (MondrianProperties.instance().UseAggregates.get()
094            || MondrianProperties.instance().ReadAggregates.get())
095        {
096            return funArg.accept(compiler);
097        }
098
099        final Calc[] calcs = {compiler.compileList(funArg, true)};
100
101        final int arity = calcs[0].getType().getArity();
102        assert arity >= 0;
103        if (arity == 1 || substitutionMap.isEmpty()) {
104            IterCalc calc = (IterCalc) funArg.accept(compiler);
105            final boolean highCardinality =
106                arity == 1
107                && isHighCardinality(funArg, compiler.getEvaluator());
108            if (calc == null) {
109                // This can happen under JDK1.4: caller wants iterator
110                // implementation, but compiler can only provide list.
111                // Fall through and use native.
112            } else if (calc instanceof ListCalc) {
113                return new NonNativeListCalc((ListCalc) calc, highCardinality);
114            } else {
115                return new NonNativeIterCalc(calc, highCardinality);
116            }
117        }
118        if (isFirstCompileCall) {
119            isFirstCompileCall = false;
120            originalExp = funArg.clone();
121            Query query = compiler.getEvaluator().getQuery();
122            call.accept(
123                new AddFormulasVisitor(query, substitutionMap, dimensions));
124            call.accept(new TransformToFormulasVisitor(query));
125            query.resolve();
126        }
127        return new NativeListCalc(
128            call, calcs, compiler, substitutionMap, originalExp);
129    }
130
131    private boolean isHighCardinality(Exp funArg, Evaluator evaluator) {
132        Level level = findLevel(funArg);
133        if (level != null) {
134            int cardinality =
135                evaluator.getSchemaReader()
136                    .getLevelCardinality(level, false, true);
137            final int minThreshold = MondrianProperties.instance()
138                .NativizeMinThreshold.get();
139            final boolean isHighCard = cardinality > minThreshold;
140            logHighCardinality(
141                ESTIMATE_MESSAGE, minThreshold, cardinality, isHighCard);
142            return isHighCard;
143        }
144        return false;
145    }
146
147    private Level findLevel(Exp exp) {
148        exp.accept(new FindLevelsVisitor(substitutionMap, dimensions));
149        final Collection<Level> levels = substitutionMap.values();
150        if (levels.size() == 1) {
151            return levels.iterator().next();
152        }
153        return null;
154    }
155
156    private static void logHighCardinality(
157        final String estimateMessage,
158        long nativizeMinThreshold,
159        long estimatedCardinality,
160        boolean highCardinality)
161    {
162        LOGGER.debug(
163            String.format(
164                estimateMessage,
165                highCardinality,
166                estimatedCardinality,
167                nativizeMinThreshold));
168    }
169
170    static class NonNativeCalc implements Calc {
171        final Calc parent;
172        final boolean nativeEnabled;
173
174        protected NonNativeCalc(Calc parent, final boolean nativeEnabled) {
175            assert parent != null;
176            this.parent = parent;
177            this.nativeEnabled = nativeEnabled;
178        }
179
180        public Object evaluate(final Evaluator evaluator) {
181            evaluator.setNativeEnabled(nativeEnabled);
182            return parent.evaluate(evaluator);
183        }
184
185        public boolean dependsOn(final Hierarchy hierarchy) {
186            return parent.dependsOn(hierarchy);
187        }
188
189        public Type getType() {
190            return parent.getType();
191        }
192
193        public void accept(final CalcWriter calcWriter) {
194            parent.accept(calcWriter);
195        }
196
197        public ResultStyle getResultStyle() {
198            return parent.getResultStyle();
199        }
200
201        /**
202         * {@inheritDoc}
203         *
204         * Default implementation just does 'instanceof TargetClass'. Subtypes
205         * that are wrappers should override.
206         */
207        public boolean isWrapperFor(Class<?> iface) {
208            return iface.isInstance(this);
209        }
210
211        /**
212         * {@inheritDoc}
213         *
214         * Default implementation just casts to TargetClass.
215         * Subtypes that are wrappers should override.
216         */
217        public <T> T unwrap(Class<T> iface) {
218            return iface.cast(this);
219        }
220    }
221
222    static class NonNativeIterCalc
223        extends NonNativeCalc
224        implements IterCalc
225    {
226        protected NonNativeIterCalc(IterCalc parent, boolean highCardinality) {
227            super(parent, highCardinality);
228        }
229
230        IterCalc parent() {
231            return (IterCalc) parent;
232        }
233
234        public TupleIterable evaluateIterable(Evaluator evaluator) {
235            evaluator.setNativeEnabled(nativeEnabled);
236            return parent().evaluateIterable(evaluator);
237        }
238    }
239
240    static class NonNativeListCalc
241        extends NonNativeCalc
242        implements ListCalc
243    {
244        protected NonNativeListCalc(ListCalc parent, boolean highCardinality) {
245            super(parent, highCardinality);
246        }
247
248        ListCalc parent() {
249            return (ListCalc) parent;
250        }
251
252        public TupleList evaluateList(Evaluator evaluator) {
253            evaluator.setNativeEnabled(nativeEnabled);
254            return parent().evaluateList(evaluator);
255        }
256
257        public TupleIterable evaluateIterable(Evaluator evaluator) {
258            return evaluateList(evaluator);
259        }
260    }
261
262    public static class NativeListCalc extends AbstractListCalc {
263        private final SubstitutionMap substitutionMap;
264        private final ListCalc simpleCalc;
265        private final ExpCompiler compiler;
266
267        private final Exp originalExp;
268
269        protected NativeListCalc(
270            ResolvedFunCall call,
271            Calc[] calcs,
272            ExpCompiler compiler,
273            SubstitutionMap substitutionMap,
274            Exp originalExp)
275        {
276            super(call, calcs);
277            LOGGER.debug("---- NativeListCalc constructor");
278            this.substitutionMap = substitutionMap;
279            this.simpleCalc = (ListCalc) calcs[0];
280            this.compiler = compiler;
281            this.originalExp = originalExp;
282        }
283
284        public TupleList evaluateList(Evaluator evaluator) {
285            return computeTuples(evaluator);
286        }
287
288        public TupleList computeTuples(Evaluator evaluator) {
289            TupleList simplifiedList = evaluateSimplifiedList(evaluator);
290            if (simplifiedList.isEmpty()) {
291                return simplifiedList;
292            }
293            if (!isHighCardinality(evaluator, simplifiedList)) {
294                return evaluateNonNative(evaluator);
295            }
296            return evaluateNative(evaluator, simplifiedList);
297        }
298
299        private TupleList evaluateSimplifiedList(Evaluator evaluator) {
300            final int savepoint = evaluator.savepoint();
301            try {
302                evaluator.setNonEmpty(false);
303                evaluator.setNativeEnabled(false);
304                TupleList simplifiedList =
305                        simpleCalc.evaluateList(evaluator);
306                dumpListToLog("simplified list", simplifiedList);
307                return simplifiedList;
308            } finally {
309                evaluator.restore(savepoint);
310            }
311        }
312
313        private TupleList evaluateNonNative(Evaluator evaluator) {
314            LOGGER.debug(
315                "Disabling native evaluation. originalExp="
316                    + originalExp);
317            ListCalc calc =
318                compiler.compileList(getOriginalExp(evaluator.getQuery()));
319            final int savepoint = evaluator.savepoint();
320            try {
321                evaluator.setNonEmpty(true);
322                evaluator.setNativeEnabled(false);
323                TupleList members = calc.evaluateList(evaluator);
324                return members;
325            } finally {
326                evaluator.restore(savepoint);
327            }
328        }
329
330        private TupleList evaluateNative(
331            Evaluator evaluator, TupleList simplifiedList)
332        {
333            CrossJoinAnalyzer analyzer =
334                new CrossJoinAnalyzer(simplifiedList, substitutionMap);
335            String crossJoin = analyzer.getCrossJoinExpression();
336
337            // If the crossjoin expression is empty, then the simplified list
338            // already contains the fully evaluated tuple list, so we can
339            // return it now without any additional work.
340            if (crossJoin.length() == 0) {
341                return simplifiedList;
342            }
343
344            // Force non-empty to true to create the native list.
345            LOGGER.debug(
346                "crossjoin reconstituted from simplified list: "
347                + String.format(
348                    "%n"
349                    + crossJoin.replaceAll(",", "%n, ")));
350            final int savepoint = evaluator.savepoint();
351            try {
352                evaluator.setNonEmpty(true);
353                evaluator.setNativeEnabled(true);
354
355                TupleList members = analyzer.mergeCalcMembers(
356                    evaluateJoinExpression(evaluator, crossJoin));
357                return members;
358            } finally {
359                evaluator.restore(savepoint);
360            }
361        }
362
363        private Exp getOriginalExp(final Query query) {
364            originalExp.accept(
365                new TransformFromFormulasVisitor(query, compiler));
366            if (originalExp instanceof NamedSetExpr) {
367                //named sets get their evaluator cached in RolapResult.
368                //We do not want to use the cached evaluator, so pass along the
369                //expression instead.
370                return ((NamedSetExpr) originalExp).getNamedSet().getExp();
371            }
372            return originalExp;
373        }
374
375        private boolean isHighCardinality(
376            Evaluator evaluator, TupleList simplifiedList)
377        {
378            Util.assertTrue(!simplifiedList.isEmpty());
379
380            SchemaReader schema = evaluator.getSchemaReader();
381            List<Member> tuple = simplifiedList.get(0);
382            long nativizeMinThreshold =
383                MondrianProperties.instance().NativizeMinThreshold.get();
384            long estimatedCardinality = simplifiedList.size();
385
386            for (Member member : tuple) {
387                String memberName = member.getName();
388                if (memberName.startsWith(MEMBER_NAME_PREFIX)) {
389                    Level level = member.getLevel();
390                    Dimension dimension = level.getDimension();
391                    Hierarchy hierarchy = dimension.getHierarchy();
392
393                    String levelName = getLevelNameFromMemberName(memberName);
394                    Level hierarchyLevel =
395                        Util.lookupHierarchyLevel(hierarchy, levelName);
396                    long levelCardinality =
397                        getLevelCardinality(schema, hierarchyLevel);
398                    estimatedCardinality *= levelCardinality;
399                    if (estimatedCardinality >= nativizeMinThreshold) {
400                        logHighCardinality(
401                            PARTIAL_ESTIMATE_MESSAGE,
402                            nativizeMinThreshold,
403                            estimatedCardinality,
404                            true);
405                        return true;
406                    }
407                }
408            }
409
410            boolean isHighCardinality =
411                (estimatedCardinality >= nativizeMinThreshold);
412
413            logHighCardinality(
414                ESTIMATE_MESSAGE,
415                nativizeMinThreshold,
416                estimatedCardinality,
417                isHighCardinality);
418            return isHighCardinality;
419        }
420
421        private long getLevelCardinality(SchemaReader schema, Level level) {
422            if (cardinalityIsKnown(level)) {
423                return level.getApproxRowCount();
424            }
425            return schema.getLevelCardinality(level, false, true);
426        }
427
428        private boolean cardinalityIsKnown(Level level) {
429            return level.getApproxRowCount() > 0;
430        }
431
432        private TupleList evaluateJoinExpression(
433            Evaluator evaluator, String crossJoinExpression)
434        {
435            Exp unresolved =
436                evaluator.getQuery().getConnection()
437                    .parseExpression(crossJoinExpression);
438            Exp resolved = compiler.getValidator().validate(unresolved, false);
439            ListCalc calc = compiler.compileList(resolved);
440            return calc.evaluateList(evaluator);
441        }
442    }
443
444    static class FindLevelsVisitor extends MdxVisitorImpl {
445        private final SubstitutionMap substitutionMap;
446        private final Set<Dimension> dimensions;
447
448        public FindLevelsVisitor(
449            SubstitutionMap substitutionMap, HashSet<Dimension> dimensions)
450        {
451            this.substitutionMap = substitutionMap;
452            this.dimensions = dimensions;
453        }
454
455        @Override
456        public Object visit(ResolvedFunCall call) {
457            if (call.getFunDef() instanceof LevelMembersFunDef) {
458                if (call.getArg(0) instanceof LevelExpr) {
459                    Level level = ((LevelExpr) call.getArg(0)).getLevel();
460                    substitutionMap.put(createMemberId(level), level);
461                    dimensions.add(level.getDimension());
462                }
463            } else if (
464                functionWhitelist.contains(call.getFunDef().getClass()))
465            {
466                for (Exp arg : call.getArgs()) {
467                    arg.accept(this);
468                }
469            }
470            turnOffVisitChildren();
471            return null;
472        }
473
474
475        @Override
476        public Object visit(MemberExpr member) {
477            dimensions.add(member.getMember().getDimension());
478            return null;
479        }
480    }
481
482    static class AddFormulasVisitor extends MdxVisitorImpl {
483        private final Query query;
484        private final Collection<Level> levels;
485        private final Set<Dimension> dimensions;
486
487        public AddFormulasVisitor(
488            Query query,
489            SubstitutionMap substitutionMap,
490            Set<Dimension> dimensions)
491        {
492            LOGGER.debug("---- AddFormulasVisitor constructor");
493            this.query = query;
494            this.levels = substitutionMap.values();
495            this.dimensions = dimensions;
496        }
497
498        @Override
499        public Object visit(ResolvedFunCall call) {
500            if (call.getFunDef() instanceof NativizeSetFunDef) {
501                addFormulasToQuery();
502            }
503            turnOffVisitChildren();
504            return null;
505        }
506
507        private void addFormulasToQuery() {
508            LOGGER.debug("FormulaResolvingVisitor addFormulas");
509            List<Formula> formulas = new ArrayList<Formula>();
510
511            for (Level level : levels) {
512                Formula memberFormula = createDefaultMemberFormula(level);
513                formulas.add(memberFormula);
514                formulas.add(createNamedSetFormula(level, memberFormula));
515            }
516
517            for (Dimension dim : dimensions) {
518                Level level = dim.getHierarchy().getLevels()[0];
519                formulas.add(createSentinelFormula(level));
520            }
521
522            query.addFormulas(formulas.toArray(new Formula[formulas.size()]));
523        }
524
525        private Formula createSentinelFormula(Level level) {
526            Id memberId = createSentinelId(level);
527            Exp memberExpr = query.getConnection()
528                .parseExpression("101010");
529
530            LOGGER.debug(
531                "createSentinelFormula memberId="
532                + memberId
533                + " memberExpr="
534                + memberExpr);
535            return new Formula(memberId, memberExpr, new MemberProperty[0]);
536        }
537
538        private Formula createDefaultMemberFormula(Level level) {
539            Id memberId = createMemberId(level);
540            Exp memberExpr =
541                new UnresolvedFunCall(
542                    "DEFAULTMEMBER",
543                    Syntax.Property,
544                    new Exp[] {hierarchyId(level)});
545
546            LOGGER.debug(
547                "createLevelMembersFormulas memberId="
548                + memberId
549                + " memberExpr="
550                + memberExpr);
551            return new Formula(memberId, memberExpr, new MemberProperty[0]);
552        }
553
554        private Formula createNamedSetFormula(
555            Level level, Formula memberFormula)
556        {
557            Id setId = createSetId(level);
558            Exp setExpr = query.getConnection()
559                .parseExpression(
560                    "{"
561                    + memberFormula.getIdentifier().toString()
562                    + "}");
563
564            LOGGER.debug(
565                "createNamedSetFormula setId="
566                + setId
567                + " setExpr="
568                + setExpr);
569            return new Formula(setId, setExpr);
570        }
571    }
572
573    static class TransformToFormulasVisitor extends MdxVisitorImpl {
574        private final Query query;
575
576        public TransformToFormulasVisitor(Query query) {
577            LOGGER.debug("---- TransformToFormulasVisitor constructor");
578            this.query = query;
579        }
580
581        @Override
582        public Object visit(ResolvedFunCall call) {
583            LOGGER.debug("visit " + call);
584            Object result = null;
585            if (call.getFunDef() instanceof LevelMembersFunDef) {
586                result = replaceLevelMembersReferences(call);
587            } else if (
588                functionWhitelist.contains(call.getFunDef().getClass()))
589            {
590                result = visitCallArguments(call);
591            }
592            turnOffVisitChildren();
593            return result;
594        }
595
596        private Object replaceLevelMembersReferences(ResolvedFunCall call) {
597            LOGGER.debug("replaceLevelMembersReferences " + call);
598            Level level = ((LevelExpr) call.getArg(0)).getLevel();
599            Id setId = createSetId(level);
600            Formula formula = query.findFormula(setId.toString());
601            Exp exp = Util.createExpr(formula.getNamedSet());
602            return query.createValidator().validate(exp, false);
603        }
604
605        private Object visitCallArguments(ResolvedFunCall call) {
606            Exp[] exps = call.getArgs();
607            LOGGER.debug("visitCallArguments " + call);
608
609            for (int i = 0; i < exps.length; i++) {
610                Exp transformedExp = (Exp) exps[i].accept(this);
611                if (transformedExp != null) {
612                    exps[i] = transformedExp;
613                }
614            }
615
616            if (exps.length > 1
617                && call.getFunDef() instanceof SetFunDef)
618            {
619                return flattenSetFunDef(call);
620            }
621            return null;
622        }
623
624        private Object flattenSetFunDef(ResolvedFunCall call) {
625            List<Exp> newArgs = new ArrayList<Exp>();
626            flattenSetMembers(newArgs, call.getArgs());
627            addSentinelMembers(newArgs);
628            if (newArgs.size() != call.getArgCount()) {
629                return new ResolvedFunCall(
630                    call.getFunDef(),
631                    newArgs.toArray(new Exp[newArgs.size()]),
632                    call.getType());
633            }
634            return null;
635        }
636
637        private void flattenSetMembers(List<Exp> result, Exp[] args) {
638            for (Exp arg : args) {
639                if (arg instanceof ResolvedFunCall
640                    && ((ResolvedFunCall)arg).getFunDef() instanceof SetFunDef)
641                {
642                    flattenSetMembers(result, ((ResolvedFunCall)arg).getArgs());
643                } else {
644                    result.add(arg);
645                }
646            }
647        }
648
649        private void addSentinelMembers(List<Exp> args) {
650            Exp prev = args.get(0);
651            for (int i = 1; i < args.size(); i++) {
652                Exp curr = args.get(i);
653                if (prev.toString().equals(curr.toString())) {
654                    OlapElement element = null;
655                    if (curr instanceof NamedSetExpr) {
656                        element = ((NamedSetExpr) curr).getNamedSet();
657                    } else if (curr instanceof MemberExpr) {
658                        element = ((MemberExpr) curr).getMember();
659                    }
660                    if (element != null) {
661                        Level level = element.getHierarchy().getLevels()[0];
662                        Id memberId = createSentinelId(level);
663                        Formula formula =
664                            query.findFormula(memberId.toString());
665                        args.add(i++, Util.createExpr(formula.getMdxMember()));
666                    }
667                }
668                prev = curr;
669            }
670        }
671    }
672
673    static class TransformFromFormulasVisitor extends MdxVisitorImpl {
674        private final Query query;
675        private final ExpCompiler compiler;
676
677        public TransformFromFormulasVisitor(Query query, ExpCompiler compiler) {
678            LOGGER.debug("---- TransformFromFormulasVisitor constructor");
679            this.query = query;
680            this.compiler = compiler;
681        }
682
683        @Override
684        public Object visit(ResolvedFunCall call) {
685            LOGGER.debug("visit " + call);
686            Object result;
687            result = visitCallArguments(call);
688            turnOffVisitChildren();
689            return result;
690        }
691
692        @Override
693        public Object visit(NamedSetExpr namedSetExpr) {
694            String exprName = namedSetExpr.getNamedSet().getName();
695            Exp membersExpr;
696
697            if (exprName.contains(SET_NAME_PREFIX)) {
698                String levelMembers = exprName.replaceAll(
699                    SET_NAME_PREFIX, "\\[")
700                    .replaceAll("_$", "\\]")
701                    .replaceAll("_", "\\]\\.\\[")
702                    + ".members";
703                membersExpr =
704                    query.getConnection().parseExpression(levelMembers);
705                membersExpr =
706                    compiler.getValidator().validate(membersExpr, false);
707            } else {
708                membersExpr = namedSetExpr.getNamedSet().getExp();
709            }
710            return membersExpr;
711        }
712
713
714        private Object visitCallArguments(ResolvedFunCall call) {
715            Exp[] exps = call.getArgs();
716            LOGGER.debug("visitCallArguments " + call);
717
718            for (int i = 0; i < exps.length; i++) {
719                Exp transformedExp = (Exp) exps[i].accept(this);
720                if (transformedExp != null) {
721                    exps[i] = transformedExp;
722                }
723            }
724            return null;
725        }
726    }
727
728    private static class SubstitutionMap {
729        private final Map<String, Level> map = new HashMap<String, Level>();
730
731        public boolean isEmpty() {
732            return map.isEmpty();
733        }
734
735        public boolean contains(Member member) {
736            return map.containsKey(toKey(member));
737        }
738
739        public Level get(Member member) {
740            return map.get(toKey(member));
741        }
742
743        public Level put(Id id, Level level) {
744            return map.put(toKey(id), level);
745        }
746
747        public Collection<Level> values() {
748            return map.values();
749        }
750
751        @Override
752        public String toString() {
753            return map.toString();
754        }
755
756        private String toKey(Id id) {
757            return id.toString();
758        }
759
760        private String toKey(Member member) {
761            return member.getUniqueName();
762        }
763    }
764
765    public static class CrossJoinAnalyzer {
766
767        private final int arity;
768        private final Member[] tempTuple;
769        private final List<Member> tempTupleAsList;
770        private final int[] nativeIndices;
771        private final int resultLimit;
772
773        private final List<Collection<String>> nativeMembers;
774        private final ReassemblyGuide reassemblyGuide;
775        private final TupleList resultList;
776
777        public CrossJoinAnalyzer(
778            TupleList simplifiedList, SubstitutionMap substitutionMap)
779        {
780            long nativizeMaxResults =
781                MondrianProperties.instance().NativizeMaxResults.get();
782            arity = simplifiedList.getArity();
783            tempTuple = new Member[arity];
784            tempTupleAsList = Arrays.asList(tempTuple);
785            resultLimit = nativizeMaxResults <= 0
786                    ? Integer.MAX_VALUE
787                    : (int) Math.min(nativizeMaxResults, Integer.MAX_VALUE);
788
789            resultList = TupleCollections.createList(arity);
790
791            reassemblyGuide = classifyMembers(simplifiedList, substitutionMap);
792            nativeMembers = findNativeMembers();
793            nativeIndices = findNativeIndices();
794        }
795
796        public ReassemblyGuide classifyMembers(
797            TupleList simplifiedList,
798            SubstitutionMap substitutionMap)
799        {
800            ReassemblyGuide guide = new ReassemblyGuide(0);
801
802            List<ReassemblyCommand> cmdTuple =
803                new ArrayList<ReassemblyCommand>(arity);
804            for (List<Member> srcTuple : simplifiedList) {
805                cmdTuple.clear();
806                for (Member mbr : srcTuple) {
807                    cmdTuple.add(zz(substitutionMap, mbr));
808                }
809                guide.addCommandTuple(cmdTuple);
810            }
811            return guide;
812        }
813
814        private ReassemblyCommand zz(
815            SubstitutionMap substitutionMap, Member mbr)
816        {
817            ReassemblyCommand c;
818            if (substitutionMap.contains(mbr)) {
819                c =
820                    new ReassemblyCommand(
821                        substitutionMap.get(mbr), LEVEL_MEMBERS);
822            } else if (mbr.getName().startsWith(SENTINEL_PREFIX)) {
823                c =
824                    new ReassemblyCommand(mbr, SENTINEL);
825            } else {
826                NativeElementType nativeType = !isNativeCompatible(mbr)
827                    ? NON_NATIVE
828                    : mbr.getMemberType() == Member.MemberType.REGULAR
829                    ? ENUMERATED_VALUE
830                    : OTHER_NATIVE;
831                c = new ReassemblyCommand(mbr, nativeType);
832            }
833            return c;
834        }
835
836        private List<Collection<String>> findNativeMembers() {
837            List<Collection<String>> nativeMembers =
838                new ArrayList<Collection<String>>(arity);
839
840            for (int i = 0; i < arity; i++) {
841                nativeMembers.add(new LinkedHashSet<String>());
842            }
843
844            findNativeMembers(reassemblyGuide, nativeMembers);
845            return nativeMembers;
846        }
847
848        private void findNativeMembers(
849            ReassemblyGuide guide,
850            List<Collection<String>> nativeMembers)
851        {
852            List<ReassemblyCommand> commands = guide.getCommands();
853            Set<NativeElementType> typesToAdd =
854                ReassemblyCommand.getMemberTypes(commands);
855
856            if (typesToAdd.contains(LEVEL_MEMBERS)) {
857                typesToAdd.remove(ENUMERATED_VALUE);
858            }
859
860            int index = guide.getIndex();
861            for (ReassemblyCommand command : commands) {
862                NativeElementType type = command.getMemberType();
863                if (type.isNativeCompatible() && typesToAdd.contains(type)) {
864                    nativeMembers.get(index).add(command.getElementName());
865                }
866
867                if (command.hasNextGuide()) {
868                    findNativeMembers(command.forNextCol(), nativeMembers);
869                }
870            }
871        }
872
873        private int[] findNativeIndices() {
874            int[] indices = new int[arity];
875            int nativeColCount = 0;
876
877            for (int i = 0; i < arity; i++) {
878                Collection<String> natives = nativeMembers.get(i);
879                if (!natives.isEmpty()) {
880                    indices[nativeColCount++] = i;
881                }
882            }
883
884            if (nativeColCount == arity) {
885                return indices;
886            }
887
888            int[] result = new int[nativeColCount];
889            System.arraycopy(indices, 0, result, 0, nativeColCount);
890            return result;
891        }
892
893        private boolean isNativeCompatible(Member member) {
894            return member.isParentChildLeaf()
895                || (!member.isMeasure()
896                && !member.isCalculated() && !member.isAll());
897        }
898
899        private String getCrossJoinExpression() {
900            return formatCrossJoin(nativeMembers);
901        }
902
903        private String formatCrossJoin(List<Collection<String>> memberLists) {
904            StringBuilder buf = new StringBuilder();
905
906            String left = toCsv(memberLists.get(0));
907            String right =
908                memberLists.size() == 1
909                ? ""
910                : formatCrossJoin(memberLists.subList(1, memberLists.size()));
911
912            if (left.length() == 0) {
913                buf.append(right);
914            } else {
915                if (right.length() == 0) {
916                    buf.append("{").append(left).append("}");
917                } else {
918                    buf.append("CrossJoin(")
919                        .append("{").append(left).append("},")
920                        .append(right).append(")");
921                }
922            }
923
924            return buf.toString();
925        }
926
927        private TupleList mergeCalcMembers(TupleList nativeValues) {
928            TupleList nativeList =
929                adaptList(nativeValues, arity, nativeIndices);
930
931            dumpListToLog("native list", nativeList);
932            mergeCalcMembers(reassemblyGuide, new Range(nativeList), null);
933            dumpListToLog("result list", resultList);
934            return resultList;
935        }
936
937        private void mergeCalcMembers(
938            ReassemblyGuide guide, Range range, Set<List<Member>> history)
939        {
940            int col = guide.getIndex();
941            if (col == arity - 1) {
942                if (history == null) {
943                    appendMembers(guide, range);
944                } else {
945                    appendMembers(guide, range, history);
946                }
947                return;
948            }
949
950            for (ReassemblyCommand command : guide.getCommands()) {
951                ReassemblyGuide nextGuide = command.forNextCol();
952                tempTuple[col] = null;
953
954                switch (command.getMemberType()) {
955                case NON_NATIVE:
956                    tempTuple[col] = command.getMember();
957                    mergeCalcMembers(
958                        nextGuide,
959                        range,
960                        (history == null
961                            ? new HashSet<List<Member>>()
962                            : history));
963                    break;
964                case ENUMERATED_VALUE:
965                    Member value = command.getMember();
966                    Range valueRange = range.subRangeForValue(value, col);
967                    if (!valueRange.isEmpty()) {
968                        mergeCalcMembers(nextGuide, valueRange, history);
969                    }
970                    break;
971                case LEVEL_MEMBERS:
972                    Level level = command.getLevel();
973                    Range levelRange = range.subRangeForValue(level, col);
974                    for (Range subRange : levelRange.subRanges(col)) {
975                        mergeCalcMembers(nextGuide, subRange, history);
976                    }
977                    break;
978                case OTHER_NATIVE:
979                    for (Range subRange : range.subRanges(col)) {
980                        mergeCalcMembers(nextGuide, subRange, history);
981                    }
982                    break;
983                default:
984                    throw Util.unexpected(command.getMemberType());
985                }
986            }
987        }
988
989        private void appendMembers(ReassemblyGuide guide, Range range) {
990            int col = guide.getIndex();
991
992            for (ReassemblyCommand command : guide.getCommands()) {
993                switch (command.getMemberType()) {
994                case NON_NATIVE:
995                    tempTuple[col] = command.getMember();
996                    appendTuple(range.getTuple(), tempTupleAsList);
997                    break;
998                case ENUMERATED_VALUE:
999                    Member value = command.getMember();
1000                    Range valueRange = range.subRangeForValue(value, col);
1001                    if (!valueRange.isEmpty()) {
1002                        appendTuple(valueRange.getTuple());
1003                    }
1004                    break;
1005                case LEVEL_MEMBERS:
1006                case OTHER_NATIVE:
1007                    for (List<Member> tuple : range.getTuples()) {
1008                        appendTuple(tuple);
1009                    }
1010                    break;
1011                default:
1012                    throw Util.unexpected(command.getMemberType());
1013                }
1014            }
1015        }
1016
1017        private void appendMembers(
1018            ReassemblyGuide guide, Range range, Set<List<Member>> history)
1019        {
1020            int col = guide.getIndex();
1021
1022            for (ReassemblyCommand command : guide.getCommands()) {
1023                switch (command.getMemberType()) {
1024                case NON_NATIVE:
1025                    tempTuple[col] = command.getMember();
1026                    if (range.isEmpty()) {
1027                        appendTuple(tempTupleAsList, history);
1028                    } else {
1029                        appendTuple(range.getTuple(), tempTupleAsList, history);
1030                    }
1031                    break;
1032                case ENUMERATED_VALUE:
1033                    Member value = command.getMember();
1034                    Range valueRange = range.subRangeForValue(value, col);
1035                    if (!valueRange.isEmpty()) {
1036                        appendTuple(
1037                            valueRange.getTuple(), tempTupleAsList, history);
1038                    }
1039                    break;
1040                case LEVEL_MEMBERS:
1041                case OTHER_NATIVE:
1042                    tempTuple[col] = null;
1043                    for (List<Member> tuple : range.getTuples()) {
1044                        appendTuple(tuple, tempTupleAsList, history);
1045                    }
1046                    break;
1047                default:
1048                    throw Util.unexpected(command.getMemberType());
1049                }
1050            }
1051        }
1052
1053        private void appendTuple(
1054            List<Member> nonNatives,
1055            Set<List<Member>> history)
1056        {
1057            if (history.add(nonNatives)) {
1058                appendTuple(nonNatives);
1059            }
1060        }
1061
1062        private void appendTuple(
1063            List<Member> natives,
1064            List<Member> nonNatives,
1065            Set<List<Member>> history)
1066        {
1067            List<Member> copy = copyOfTuple(natives, nonNatives);
1068            if (history.add(copy)) {
1069                appendTuple(copy);
1070            }
1071        }
1072
1073        private void appendTuple(
1074            List<Member> natives,
1075            List<Member> nonNatives)
1076        {
1077            appendTuple(copyOfTuple(natives, nonNatives));
1078        }
1079
1080        private void appendTuple(List<Member> tuple) {
1081            resultList.add(tuple);
1082            checkNativeResultLimit(resultList.size());
1083        }
1084
1085        private List<Member> copyOfTuple(
1086            List<Member> natives,
1087            List<Member> nonNatives)
1088        {
1089            Member[] copy = new Member[arity];
1090            for (int i = 0; i < arity; i++) {
1091                copy[i] =
1092                    (nonNatives.get(i) == null)
1093                        ? natives.get(i)
1094                        : nonNatives.get(i);
1095            }
1096            return Arrays.asList(copy);
1097        }
1098
1099        /**
1100         * Check the resultSize against the result limit setting. Throws
1101         * LimitExceededDuringCrossjoin exception if limit exceeded.
1102         * <p/>
1103         * It didn't seem appropriate to use the existing Mondrian
1104         * ResultLimit property, since the meaning and use of that
1105         * property seems to be a bit ambiguous, otherwise we could
1106         * simply call Util.checkCJResultLimit.
1107         *
1108         * @param resultSize Result limit
1109         * @throws mondrian.olap.ResourceLimitExceededException
1110         *
1111         */
1112        private void checkNativeResultLimit(int resultSize) {
1113            // Throw an exeption if the size of the crossjoin exceeds the result
1114            // limit.
1115            if (resultLimit < resultSize) {
1116                throw MondrianResource.instance()
1117                    .LimitExceededDuringCrossjoin.ex(resultSize, resultLimit);
1118            }
1119        }
1120
1121        public TupleList adaptList(
1122            final TupleList sourceList,
1123            final int destSize,
1124            final int[] destIndices)
1125        {
1126            if (sourceList.isEmpty()) {
1127                return TupleCollections.emptyList(destIndices.length);
1128            }
1129
1130            checkNativeResultLimit(sourceList.size());
1131
1132            TupleList destList =
1133                new DelegatingTupleList(
1134                    destSize,
1135                    new AbstractList<List<Member>>() {
1136                        @Override
1137                        public List<Member> get(int index) {
1138                            final List<Member> sourceTuple =
1139                                sourceList.get(index);
1140                            final Member[] members = new Member[destSize];
1141                            for (int i = 0; i < destIndices.length; i++) {
1142                                members[destIndices[i]] = sourceTuple.get(i);
1143                            }
1144                            return Arrays.asList(members);
1145                        }
1146
1147                        @Override
1148                        public int size() {
1149                            return sourceList.size();
1150                        }
1151                    }
1152                );
1153
1154            // The mergeCalcMembers method in this file assumes that the
1155            // resultList is random access - that calls to get(n) are constant
1156            // cost, regardless of n. Unfortunately, the TraversalList objects
1157            // created by HighCardSqlTupleReader are implemented using linked
1158            // lists, leading to pathologically long run times.
1159            // This presumes that the ResultStyle is LIST
1160            if (LOGGER.isDebugEnabled()) {
1161                String sourceListType =
1162                    sourceList.getClass().getSimpleName();
1163                String sourceElementType =
1164                    String.format("Member[%d]", destSize);
1165                LOGGER.debug(
1166                    String.format(
1167                        "returning native %s<%s> without copying to new list.",
1168                        sourceListType,
1169                        sourceElementType));
1170            }
1171            return destList;
1172        }
1173    }
1174
1175    // REVIEW: Can we remove this class, and simply use TupleList?
1176    static class Range {
1177        private final TupleList list;
1178        private final int from;
1179        private final int to;
1180
1181        public Range(TupleList list)
1182        {
1183            this(list, 0, list.size());
1184        }
1185
1186        private Range(TupleList list, int from, int to) {
1187            if (from < 0) {
1188                throw new IllegalArgumentException("from is must be >= 0");
1189            }
1190            if (to > list.size()) {
1191                throw new IllegalArgumentException(
1192                    "to must be <= to list size");
1193            }
1194            if (from > to) {
1195                throw new IllegalArgumentException("from must be <= to");
1196            }
1197
1198            this.list = list;
1199            this.from = from;
1200            this.to = to;
1201        }
1202
1203        public boolean isEmpty() {
1204            return size() == 0;
1205        }
1206
1207        public int size() {
1208            return to - from;
1209        }
1210
1211        public List<Member> getTuple() {
1212            if (from >= list.size()) {
1213                throw new NoSuchElementException();
1214            }
1215            return list.get(from);
1216        }
1217
1218        public List<List<Member>> getTuples() {
1219            if (from == 0 && to == list.size()) {
1220                return list;
1221            }
1222            return list.subList(from, to);
1223        }
1224
1225        public Member getMember(int cursor, int col) {
1226            return list.get(cursor).get(col);
1227        }
1228
1229        public String toString() {
1230            return "[" + from + " : " + to + "]";
1231        }
1232
1233        private Range subRange(int fromRow, int toRow) {
1234            return new Range(list, fromRow, toRow);
1235        }
1236
1237        public Range subRangeForValue(Member value, int col) {
1238            int startAt = nextMatching(value, from, col);
1239            int endAt = nextNonMatching(value, startAt + 1, col);
1240            return subRange(startAt, endAt);
1241        }
1242
1243        public Range subRangeForValue(Level level, int col) {
1244            int startAt = nextMatching(level, from, col);
1245            int endAt = nextNonMatching(level, startAt + 1, col);
1246            return subRange(startAt, endAt);
1247        }
1248
1249        public Range subRangeStartingAt(int startAt, int col) {
1250            Member value = list.get(startAt).get(col);
1251            int endAt = nextNonMatching(value, startAt + 1, col);
1252            return subRange(startAt, endAt);
1253        }
1254
1255        private int nextMatching(Member value, int startAt, int col) {
1256            for (int cursor = startAt; cursor < to; cursor++) {
1257                if (value.equals(list.get(cursor).get(col))) {
1258                    return cursor;
1259                }
1260            }
1261            return to;
1262        }
1263
1264        private int nextMatching(Level level, int startAt, int col) {
1265            for (int cursor = startAt; cursor < to; cursor++) {
1266                if (level.equals(list.get(cursor).get(col).getLevel())) {
1267                    return cursor;
1268                }
1269            }
1270            return to;
1271        }
1272
1273        private int nextNonMatching(Member value, int startAt, int col) {
1274            if (value == null) {
1275                return nextNonNull(startAt, col);
1276            }
1277            for (int cursor = startAt; cursor < to; cursor++) {
1278                if (!value.equals(list.get(cursor).get(col))) {
1279                    return cursor;
1280                }
1281            }
1282            return to;
1283        }
1284
1285        private int nextNonMatching(Level level, int startAt, int col) {
1286            if (level == null) {
1287                return nextNonNull(startAt, col);
1288            }
1289            for (int cursor = startAt; cursor < to; cursor++) {
1290                if (!level.equals(list.get(cursor).get(col).getLevel())) {
1291                    return cursor;
1292                }
1293            }
1294            return to;
1295        }
1296
1297        private int nextNonNull(int startAt, int col) {
1298            for (int cursor = startAt; cursor < to; cursor++) {
1299                if (list.get(cursor).get(col) != null) {
1300                    return cursor;
1301                }
1302            }
1303            return to;
1304        }
1305
1306        public Iterable<Range> subRanges(final int col) {
1307            final Range parent = this;
1308
1309            return new Iterable<Range>() {
1310                final int rangeCol = col;
1311
1312                public Iterator<Range> iterator() {
1313                    return new RangeIterator(parent, rangeCol);
1314                }
1315            };
1316        }
1317
1318        public Iterable<Member> getMembers(final int col) {
1319            return new Iterable<Member>() {
1320                public Iterator<Member> iterator() {
1321                    return new Iterator<Member>() {
1322                        private int cursor = from;
1323
1324                        public boolean hasNext() {
1325                            return cursor < to;
1326                        }
1327
1328                        public Member next() {
1329                            if (!hasNext()) {
1330                                throw new NoSuchElementException();
1331                            }
1332                            return getMember(cursor++, col);
1333                        }
1334
1335                        public void remove() {
1336                            throw new UnsupportedOperationException();
1337                        }
1338                    };
1339                }
1340            };
1341        }
1342    }
1343
1344    public static class RangeIterator
1345        implements Iterator<Range>
1346    {
1347        private final Range parent;
1348        private final int col;
1349        private Range precomputed;
1350
1351        public RangeIterator(Range parent, int col) {
1352            this.parent = parent;
1353            this.col = col;
1354            precomputed = next(parent.from);
1355        }
1356
1357        public boolean hasNext() {
1358            return precomputed != null;
1359        }
1360
1361        private Range next(int cursor) {
1362            return (cursor >= parent.to)
1363                ? null
1364                : parent.subRangeStartingAt(cursor, col);
1365        }
1366
1367        public Range next() {
1368            if (precomputed == null) {
1369                throw new NoSuchElementException();
1370            }
1371            Range it = precomputed;
1372            precomputed = next(precomputed.to);
1373            return it;
1374        }
1375
1376        public void remove() {
1377            throw new UnsupportedOperationException();
1378        }
1379    }
1380
1381    private static class ReassemblyGuide {
1382        private final int index;
1383        private final List<ReassemblyCommand> commands =
1384            new ArrayList<ReassemblyCommand>();
1385
1386        public ReassemblyGuide(int index) {
1387            this.index = index;
1388        }
1389
1390        public int getIndex() {
1391            return index;
1392        }
1393
1394        public List<ReassemblyCommand> getCommands() {
1395            return Collections.unmodifiableList(commands);
1396        }
1397
1398        private void addCommandTuple(List<ReassemblyCommand> commandTuple) {
1399            ReassemblyCommand curr = currentCommand(commandTuple);
1400
1401            if (index < commandTuple.size() - 1) {
1402                curr.forNextCol(index + 1).addCommandTuple(commandTuple);
1403            }
1404        }
1405
1406        private ReassemblyCommand currentCommand(
1407            List<ReassemblyCommand> commandTuple)
1408        {
1409            ReassemblyCommand curr = commandTuple.get(index);
1410            ReassemblyCommand prev = commands.isEmpty()
1411                ? null : commands.get(commands.size() - 1);
1412
1413            if (prev != null && prev.getMemberType() == SENTINEL) {
1414                commands.set(commands.size() - 1, curr);
1415            } else if (prev == null
1416                || !prev.getElement().equals(curr.getElement()))
1417            {
1418                commands.add(curr);
1419            } else {
1420                curr = prev;
1421            }
1422            return curr;
1423        }
1424
1425        public String toString() {
1426            return "" + index + ":" + commands.toString()
1427                    .replaceAll("=null", "").replaceAll("=", " ") + " ";
1428        }
1429    }
1430
1431    private static class ReassemblyCommand {
1432        private final OlapElement element;
1433        private final String elementName;
1434        private final NativeElementType memberType;
1435        private ReassemblyGuide nextColGuide;
1436
1437        public ReassemblyCommand(
1438            Member member,
1439            NativeElementType memberType)
1440        {
1441            this.element = member;
1442            this.memberType = memberType;
1443            this.elementName = member.toString();
1444        }
1445
1446        public ReassemblyCommand(
1447            Level level,
1448            NativeElementType memberType)
1449        {
1450            this.element = level;
1451            this.memberType = memberType;
1452            this.elementName = level.toString() + ".members";
1453        }
1454
1455        public OlapElement getElement() {
1456            return element;
1457        }
1458
1459        public String getElementName() {
1460            return elementName;
1461        }
1462
1463        public Member getMember() {
1464            return (Member) element;
1465        }
1466
1467        public Level getLevel() {
1468            return (Level) element;
1469        }
1470
1471        public boolean hasNextGuide() {
1472            return nextColGuide != null;
1473        }
1474
1475        public ReassemblyGuide forNextCol() {
1476            return nextColGuide;
1477        }
1478
1479        public ReassemblyGuide forNextCol(int index) {
1480            if (nextColGuide == null) {
1481                nextColGuide = new ReassemblyGuide(index);
1482            }
1483            return nextColGuide;
1484        }
1485
1486        public NativeElementType getMemberType() {
1487            return memberType;
1488        }
1489
1490        public static Set<NativeElementType> getMemberTypes(
1491            Collection<ReassemblyCommand> commands)
1492        {
1493            Set<NativeElementType> types =
1494                Olap4jUtil.enumSetNoneOf(NativeElementType.class);
1495            for (ReassemblyCommand command : commands) {
1496                types.add(command.getMemberType());
1497            }
1498            return types;
1499        }
1500
1501        @Override
1502        public String toString() {
1503            return memberType.toString() + ": " + getElementName();
1504        }
1505    }
1506
1507    enum NativeElementType {
1508        LEVEL_MEMBERS(true),
1509        ENUMERATED_VALUE(true),
1510        OTHER_NATIVE(true),
1511        NON_NATIVE(false),
1512        SENTINEL(false);
1513
1514        private final boolean isNativeCompatible;
1515        private NativeElementType(boolean isNativeCompatible) {
1516            this.isNativeCompatible = isNativeCompatible;
1517        }
1518
1519        public boolean isNativeCompatible() {
1520            return isNativeCompatible;
1521        }
1522    }
1523
1524    private static Id createSentinelId(Level level) {
1525        return hierarchyId(level)
1526            .append(q(createMangledName(level, SENTINEL_PREFIX)));
1527    }
1528
1529    private static Id createMemberId(Level level) {
1530        return hierarchyId(level)
1531            .append(q(createMangledName(level, MEMBER_NAME_PREFIX)));
1532    }
1533
1534    private static Id createSetId(Level level) {
1535        return new Id(
1536            q(createMangledName(level, SET_NAME_PREFIX)));
1537    }
1538
1539    private static Id hierarchyId(Level level) {
1540        Id id = new Id(q(level.getDimension().getName()));
1541        if (MondrianProperties.instance().SsasCompatibleNaming.get()) {
1542            id = id.append(q(level.getHierarchy().getName()));
1543        }
1544        return id;
1545    }
1546
1547    private static Id.Segment q(String s) {
1548        return new Id.NameSegment(s);
1549    }
1550
1551    private static String createMangledName(Level level, String prefix) {
1552        return prefix
1553            + level.getUniqueName().replaceAll("[\\[\\]]", "")
1554            .replaceAll("\\.", "_")
1555            + "_";
1556    }
1557
1558    private static void dumpListToLog(
1559        String heading, TupleList list)
1560    {
1561        if (LOGGER.isDebugEnabled()) {
1562            LOGGER.debug(
1563                String.format(
1564                    "%s created with %,d rows.", heading, list.size()));
1565            StringBuilder buf = new StringBuilder(Util.nl);
1566            for (List<Member> element : list) {
1567                buf.append(Util.nl);
1568                buf.append(element);
1569            }
1570            LOGGER.debug(buf.toString());
1571        }
1572    }
1573
1574    private static <T> String toCsv(Collection<T> list) {
1575        StringBuilder buf = new StringBuilder();
1576        String sep = "";
1577        for (T element : list) {
1578            buf.append(sep).append(element);
1579            sep = ", ";
1580        }
1581        return buf.toString();
1582    }
1583
1584    private static String getLevelNameFromMemberName(String memberName) {
1585        // we assume that the last token is the level name
1586        String tokens[] = memberName.split("_");
1587        return tokens[tokens.length - 1];
1588    }
1589}
1590
1591// End NativizeSetFunDef.java