001/*
002 * CDDL HEADER START
003 *
004 * The contents of this file are subject to the terms of the
005 * Common Development and Distribution License, Version 1.0 only
006 * (the "License").  You may not use this file except in compliance
007 * with the License.
008 *
009 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
010 * or http://forgerock.org/license/CDDLv1.0.html.
011 * See the License for the specific language governing permissions
012 * and limitations under the License.
013 *
014 * When distributing Covered Code, include this CDDL HEADER in each
015 * file and include the License file at legal-notices/CDDLv1_0.txt.
016 * If applicable, add the following below this CDDL HEADER, with the
017 * fields enclosed by brackets "[]" replaced with your own identifying
018 * information:
019 *      Portions Copyright [yyyy] [name of copyright owner]
020 *
021 * CDDL HEADER END
022 *
023 *      Copyright 2011-2015 ForgeRock AS
024 */
025
026package org.forgerock.opendj.ldif;
027
028import static com.forgerock.opendj.ldap.CoreMessages.*;
029
030import java.io.IOException;
031import java.util.ArrayList;
032import java.util.Collection;
033import java.util.Collections;
034import java.util.Comparator;
035import java.util.Iterator;
036import java.util.List;
037import java.util.Map;
038import java.util.NoSuchElementException;
039import java.util.SortedMap;
040import java.util.TreeMap;
041
042import org.forgerock.i18n.LocalizedIllegalArgumentException;
043import org.forgerock.opendj.io.ASN1;
044import org.forgerock.opendj.io.LDAP;
045import org.forgerock.opendj.ldap.AVA;
046import org.forgerock.opendj.ldap.Attribute;
047import org.forgerock.opendj.ldap.AttributeDescription;
048import org.forgerock.opendj.ldap.Attributes;
049import org.forgerock.opendj.ldap.ByteString;
050import org.forgerock.opendj.ldap.ByteStringBuilder;
051import org.forgerock.opendj.ldap.DN;
052import org.forgerock.opendj.ldap.DecodeException;
053import org.forgerock.opendj.ldap.DecodeOptions;
054import org.forgerock.opendj.ldap.Entry;
055import org.forgerock.opendj.ldap.LinkedHashMapEntry;
056import org.forgerock.opendj.ldap.Matcher;
057import org.forgerock.opendj.ldap.Modification;
058import org.forgerock.opendj.ldap.ModificationType;
059import org.forgerock.opendj.ldap.RDN;
060import org.forgerock.opendj.ldap.SearchScope;
061import org.forgerock.opendj.ldap.controls.SubtreeDeleteRequestControl;
062import org.forgerock.opendj.ldap.requests.AddRequest;
063import org.forgerock.opendj.ldap.requests.DeleteRequest;
064import org.forgerock.opendj.ldap.requests.ModifyDNRequest;
065import org.forgerock.opendj.ldap.requests.ModifyRequest;
066import org.forgerock.opendj.ldap.requests.Requests;
067import org.forgerock.opendj.ldap.requests.SearchRequest;
068import org.forgerock.opendj.ldap.schema.AttributeUsage;
069import org.forgerock.opendj.ldap.schema.Schema;
070import org.forgerock.util.Utils;
071
072/**
073 * This class contains common utility methods for creating and manipulating
074 * readers and writers.
075 */
076public final class LDIF {
077    // @formatter:off
078    private static final class EntryIteratorReader implements EntryReader {
079        private final Iterator<Entry> iterator;
080        private EntryIteratorReader(final Iterator<Entry> iterator) { this.iterator = iterator; }
081        public void close()      { }
082        public boolean hasNext() { return iterator.hasNext(); }
083        public Entry readEntry() { return iterator.next(); }
084    }
085    // @formatter:on
086
087    /**
088     * Comparator ordering the DN ASC.
089     */
090    private static final Comparator<byte[][]> DN_ORDER2 = new Comparator<byte[][]>() {
091        public int compare(byte[][] b1, byte[][] b2) {
092            return DN_ORDER.compare(b1[0], b2[0]);
093        }
094    };
095
096    /**
097     * Comparator ordering the DN ASC.
098     */
099    private static final Comparator<byte[]> DN_ORDER = new Comparator<byte[]>() {
100        public int compare(byte[] b1, byte[] b2) {
101            final ByteString bs = ByteString.valueOf(b1);
102            final ByteString bs2 = ByteString.valueOf(b2);
103            return bs.compareTo(bs2);
104        }
105    };
106
107    /**
108     * Copies the content of {@code input} to {@code output}. This method does
109     * not close {@code input} or {@code output}.
110     *
111     * @param input
112     *            The input change record reader.
113     * @param output
114     *            The output change record reader.
115     * @return The output change record reader.
116     * @throws IOException
117     *             If an unexpected IO error occurred.
118     */
119    public static ChangeRecordWriter copyTo(final ChangeRecordReader input,
120            final ChangeRecordWriter output) throws IOException {
121        while (input.hasNext()) {
122            output.writeChangeRecord(input.readChangeRecord());
123        }
124        return output;
125    }
126
127    /**
128     * Copies the content of {@code input} to {@code output}. This method does
129     * not close {@code input} or {@code output}.
130     *
131     * @param input
132     *            The input entry reader.
133     * @param output
134     *            The output entry reader.
135     * @return The output entry reader.
136     * @throws IOException
137     *             If an unexpected IO error occurred.
138     */
139    public static EntryWriter copyTo(final EntryReader input, final EntryWriter output)
140            throws IOException {
141        while (input.hasNext()) {
142            output.writeEntry(input.readEntry());
143        }
144        return output;
145    }
146
147    /**
148     * Compares the content of {@code source} to the content of {@code target}
149     * and returns the differences in a change record reader. Closing the
150     * returned reader will cause {@code source} and {@code target} to be closed
151     * as well.
152     * <p>
153     * <b>NOTE:</b> this method reads the content of {@code source} and
154     * {@code target} into memory before calculating the differences, and is
155     * therefore not suited for use in cases where a very large number of
156     * entries are to be compared.
157     *
158     * @param source
159     *            The entry reader containing the source entries to be compared.
160     * @param target
161     *            The entry reader containing the target entries to be compared.
162     * @return A change record reader containing the differences.
163     * @throws IOException
164     *             If an unexpected IO error occurred.
165     */
166    public static ChangeRecordReader diff(final EntryReader source, final EntryReader target)
167            throws IOException {
168
169        final List<byte[][]> source2 = readEntriesAsList(source);
170        final List<byte[][]> target2 = readEntriesAsList(target);
171        final Iterator<byte[][]> sourceIterator = source2.iterator();
172        final Iterator<byte[][]> targetIterator = target2.iterator();
173
174        return new ChangeRecordReader() {
175            private Entry sourceEntry = nextEntry(sourceIterator);
176            private Entry targetEntry = nextEntry(targetIterator);
177
178            @Override
179            public void close() throws IOException {
180                try {
181                    source.close();
182                } finally {
183                    target.close();
184                }
185            }
186
187            @Override
188            public boolean hasNext() {
189                return sourceEntry != null || targetEntry != null;
190            }
191
192            @Override
193            public ChangeRecord readChangeRecord() throws IOException {
194                if (sourceEntry != null && targetEntry != null) {
195                    final DN sourceDN = sourceEntry.getName();
196                    final DN targetDN = targetEntry.getName();
197                    final int cmp = sourceDN.compareTo(targetDN);
198
199                    if (cmp == 0) {
200                        // Modify record: entry in both source and target.
201                        final ModifyRequest request =
202                                Requests.newModifyRequest(sourceEntry, targetEntry);
203                        sourceEntry = nextEntry(sourceIterator);
204                        targetEntry = nextEntry(targetIterator);
205                        return request;
206                    } else if (cmp < 0) {
207                        // Delete record: entry in source but not in target.
208                        final DeleteRequest request =
209                                Requests.newDeleteRequest(sourceEntry.getName());
210                        sourceEntry = nextEntry(sourceIterator);
211                        return request;
212                    } else {
213                        // Add record: entry in target but not in source.
214                        final AddRequest request = Requests.newAddRequest(targetEntry);
215                        targetEntry = nextEntry(targetIterator);
216                        return request;
217                    }
218                } else if (sourceEntry != null) {
219                    // Delete remaining source records.
220                    final DeleteRequest request = Requests.newDeleteRequest(sourceEntry.getName());
221                    sourceEntry = nextEntry(sourceIterator);
222                    return request;
223                } else if (targetEntry != null) {
224                    // Add remaining target records.
225                    final AddRequest request = Requests.newAddRequest(targetEntry);
226                    targetEntry = nextEntry(targetIterator);
227                    return request;
228                } else {
229                    throw new NoSuchElementException();
230                }
231            }
232
233            private Entry nextEntry(final Iterator<byte[][]> i) {
234                if (i.hasNext()) {
235                    return decodeEntry(i.next()[1]);
236                }
237                return null;
238            }
239        };
240    }
241
242    /**
243     * Builds an entry from the provided lines of LDIF.
244     * <p>
245     * Sample usage:
246     * <pre>
247     * Entry john = makeEntry(
248     *   "dn: cn=John Smith,dc=example,dc=com",
249     *   "objectclass: inetorgperson",
250     *   "cn: John Smith",
251     *   "sn: Smith",
252     *   "givenname: John");
253     * </pre>
254     *
255     * @param ldifLines
256     *          LDIF lines that contains entry definition.
257     * @return an entry
258     * @throws LocalizedIllegalArgumentException
259     *            If {@code ldifLines} did not contain an LDIF entry, or
260     *            contained multiple entries, or contained malformed LDIF, or
261     *            if the entry could not be decoded using the default schema.
262     * @throws NullPointerException
263     *             If {@code ldifLines} was {@code null}.
264     */
265    public static Entry makeEntry(String... ldifLines) {
266        // returns a non-empty list
267        List<Entry> entries = makeEntries(ldifLines);
268        if (entries.size() > 1) {
269            throw new LocalizedIllegalArgumentException(
270                WARN_READ_LDIF_ENTRY_MULTIPLE_ENTRIES_FOUND.get(entries.size()));
271        }
272        return entries.get(0);
273    }
274
275    /**
276     * Builds an entry from the provided lines of LDIF.
277     *
278     * @param ldifLines
279     *            LDIF lines that contains entry definition.
280     * @return an entry
281     * @throws LocalizedIllegalArgumentException
282     *             If {@code ldifLines} did not contain an LDIF entry, or
283     *             contained multiple entries, or contained malformed LDIF, or
284     *             if the entry could not be decoded using the default schema.
285     * @throws NullPointerException
286     *             If {@code ldifLines} was {@code null}.
287     * @see LDIF#makeEntry(String...)
288     */
289    public static Entry makeEntry(List<String> ldifLines) {
290        return makeEntry(ldifLines.toArray(new String[ldifLines.size()]));
291    }
292
293    /**
294     * Builds a list of entries from the provided lines of LDIF.
295     * <p>
296     * Sample usage:
297     * <pre>
298     * List<Entry> smiths = TestCaseUtils.makeEntries(
299     *   "dn: cn=John Smith,dc=example,dc=com",
300     *   "objectclass: inetorgperson",
301     *   "cn: John Smith",
302     *   "sn: Smith",
303     *   "givenname: John",
304     *   "",
305     *   "dn: cn=Jane Smith,dc=example,dc=com",
306     *   "objectclass: inetorgperson",
307     *   "cn: Jane Smith",
308     *   "sn: Smith",
309     *   "givenname: Jane");
310     * </pre>
311     * @param ldifLines
312     *          LDIF lines that contains entries definition.
313     *          Entries are separated by an empty string: {@code ""}.
314     * @return a non empty list of entries
315     * @throws LocalizedIllegalArgumentException
316     *             If {@code ldifLines} did not contain LDIF entries,
317     *             or contained malformed LDIF, or if the entries
318     *             could not be decoded using the default schema.
319     * @throws NullPointerException
320     *             If {@code ldifLines} was {@code null}.
321     */
322    public static List<Entry> makeEntries(String... ldifLines) {
323        List<Entry> entries = new ArrayList<>();
324        LDIFEntryReader reader = new LDIFEntryReader(ldifLines);
325        try {
326            while (reader.hasNext()) {
327                entries.add(reader.readEntry());
328            }
329        } catch (final DecodeException e) {
330            // Badly formed LDIF.
331            throw new LocalizedIllegalArgumentException(e.getMessageObject());
332        } catch (final IOException e) {
333            // This should never happen for a String based reader.
334            throw new LocalizedIllegalArgumentException(WARN_READ_LDIF_RECORD_UNEXPECTED_IO_ERROR.get(e.getMessage()));
335        } finally {
336            Utils.closeSilently(reader);
337        }
338        if (entries.isEmpty()) {
339            throw new LocalizedIllegalArgumentException(WARN_READ_LDIF_ENTRY_NO_ENTRY_FOUND.get());
340        }
341        return entries;
342    }
343
344    /**
345     * Builds a list of entries from the provided lines of LDIF.
346     *
347     * @param ldifLines
348     *            LDIF lines that contains entries definition. Entries are
349     *            separated by an empty string: {@code ""}.
350     * @return a non empty list of entries
351     * @throws LocalizedIllegalArgumentException
352     *             If {@code ldifLines} did not contain LDIF entries, or
353     *             contained malformed LDIF, or if the entries could not be
354     *             decoded using the default schema.
355     * @throws NullPointerException
356     *             If {@code ldifLines} was {@code null}.
357     * @see LDIF#makeEntries(String...)
358     */
359    public static List<Entry> makeEntries(List<String> ldifLines) {
360        return makeEntries(ldifLines.toArray(new String[ldifLines.size()]));
361    }
362
363    /**
364     * Returns an entry reader over the provided entry collection.
365     *
366     * @param entries
367     *            The entry collection.
368     * @return An entry reader over the provided entry collection.
369     */
370    public static EntryReader newEntryCollectionReader(final Collection<Entry> entries) {
371        return new EntryIteratorReader(entries.iterator());
372    }
373
374    /**
375     * Returns an entry reader over the provided entry iterator.
376     *
377     * @param entries
378     *            The entry iterator.
379     * @return An entry reader over the provided entry iterator.
380     */
381    public static EntryReader newEntryIteratorReader(final Iterator<Entry> entries) {
382        return new EntryIteratorReader(entries);
383    }
384
385    /**
386     * Applies the set of changes contained in {@code patch} to the content of
387     * {@code input} and returns the result in an entry reader. This method
388     * ignores missing entries, and overwrites existing entries. Closing the
389     * returned reader will cause {@code input} and {@code patch} to be closed
390     * as well.
391     * <p>
392     * <b>NOTE:</b> this method reads the content of {@code input} into memory
393     * before applying the changes, and is therefore not suited for use in cases
394     * where a very large number of entries are to be patched.
395     * <p>
396     * <b>NOTE:</b> this method will not perform modifications required in order
397     * to maintain referential integrity. In particular, if an entry references
398     * another entry using a DN valued attribute and the referenced entry is
399     * deleted, then the DN reference will not be removed. The same applies to
400     * renamed entries and their references.
401     *
402     * @param input
403     *            The entry reader containing the set of entries to be patched.
404     * @param patch
405     *            The change record reader containing the set of changes to be
406     *            applied.
407     * @return An entry reader containing the patched entries.
408     * @throws IOException
409     *             If an unexpected IO error occurred.
410     */
411    public static EntryReader patch(final EntryReader input, final ChangeRecordReader patch)
412            throws IOException {
413        return patch(input, patch, RejectedChangeRecordListener.OVERWRITE);
414    }
415
416    /**
417     * Applies the set of changes contained in {@code patch} to the content of
418     * {@code input} and returns the result in an entry reader. Closing the
419     * returned reader will cause {@code input} and {@code patch} to be closed
420     * as well.
421     * <p>
422     * <b>NOTE:</b> this method reads the content of {@code input} into memory
423     * before applying the changes, and is therefore not suited for use in cases
424     * where a very large number of entries are to be patched.
425     * <p>
426     * <b>NOTE:</b> this method will not perform modifications required in order
427     * to maintain referential integrity. In particular, if an entry references
428     * another entry using a DN valued attribute and the referenced entry is
429     * deleted, then the DN reference will not be removed. The same applies to
430     * renamed entries and their references.
431     *
432     * @param input
433     *            The entry reader containing the set of entries to be patched.
434     * @param patch
435     *            The change record reader containing the set of changes to be
436     *            applied.
437     * @param listener
438     *            The rejected change listener.
439     * @return An entry reader containing the patched entries.
440     * @throws IOException
441     *             If an unexpected IO error occurred.
442     */
443    public static EntryReader patch(final EntryReader input, final ChangeRecordReader patch,
444            final RejectedChangeRecordListener listener) throws IOException {
445        final SortedMap<byte[], byte[]> entries = readEntriesAsMap(input);
446
447        while (patch.hasNext()) {
448            final ChangeRecord change = patch.readChangeRecord();
449            final DN changeDN = change.getName();
450            final byte[] changeNormDN = toNormalizedByteArray(change.getName());
451
452            final DecodeException de =
453                    change.accept(new ChangeRecordVisitor<DecodeException, Void>() {
454
455                        @Override
456                        public DecodeException visitChangeRecord(final Void p,
457                                final AddRequest change) {
458
459                            if (entries.get(changeNormDN) != null) {
460                                final Entry existingEntry = decodeEntry(entries.get(changeNormDN));
461                                try {
462                                    final Entry entry =
463                                            listener.handleDuplicateEntry(change, existingEntry);
464                                    entries.put(toNormalizedByteArray(entry.getName()), encodeEntry(entry)[1]);
465                                } catch (final DecodeException e) {
466                                    return e;
467                                }
468                            } else {
469                                entries.put(changeNormDN, encodeEntry(change)[1]);
470                            }
471                            return null;
472                        }
473
474                        @Override
475                        public DecodeException visitChangeRecord(final Void p,
476                                final DeleteRequest change) {
477                            if (entries.get(changeNormDN) == null) {
478                                try {
479                                    listener.handleRejectedChangeRecord(change,
480                                            REJECTED_CHANGE_FAIL_DELETE.get(change.getName()
481                                                    .toString()));
482                                } catch (final DecodeException e) {
483                                    return e;
484                                }
485                            } else {
486                                try {
487                                    if (change.getControl(SubtreeDeleteRequestControl.DECODER,
488                                            new DecodeOptions()) != null) {
489                                        entries.subMap(
490                                            toNormalizedByteArray(change.getName()),
491                                            toNormalizedByteArray(change.getName().child(RDN.maxValue()))).clear();
492                                    } else {
493                                        entries.remove(changeNormDN);
494                                    }
495                                } catch (final DecodeException e) {
496                                    return e;
497                                }
498
499                            }
500                            return null;
501                        }
502
503                        @Override
504                        public DecodeException visitChangeRecord(final Void p,
505                                final ModifyDNRequest change) {
506                            if (entries.get(changeNormDN) == null) {
507                                try {
508                                    listener.handleRejectedChangeRecord(change,
509                                            REJECTED_CHANGE_FAIL_MODIFYDN.get(change.getName()
510                                                    .toString()));
511                                } catch (final DecodeException e) {
512                                    return e;
513                                }
514                            } else {
515                                // Calculate the old and new DN.
516                                final DN oldDN = changeDN;
517
518                                DN newSuperior = change.getNewSuperior();
519                                if (newSuperior == null) {
520                                    newSuperior = change.getName().parent();
521                                    if (newSuperior == null) {
522                                        newSuperior = DN.rootDN();
523                                    }
524                                }
525                                final DN newDN = newSuperior.child(change.getNewRDN());
526
527                                // Move the renamed entries into a separate map
528                                // in order to avoid cases where the renamed subtree overlaps.
529                                final SortedMap<byte[], byte[]> renamedEntries = new TreeMap<>(DN_ORDER);
530
531                                // @formatter:off
532                                final Iterator<Map.Entry<byte[], byte[]>> i =
533                                    entries.subMap(changeNormDN,
534                                        toNormalizedByteArray(changeDN.child(RDN.maxValue()))).entrySet().iterator();
535                                // @formatter:on
536
537                                while (i.hasNext()) {
538                                    final Map.Entry<byte[], byte[]> e = i.next();
539                                    final Entry entry = decodeEntry(e.getValue());
540                                    final DN renamedDN = entry.getName().rename(oldDN, newDN);
541                                    entry.setName(renamedDN);
542                                    renamedEntries.put(toNormalizedByteArray(renamedDN), encodeEntry(entry)[1]);
543                                    i.remove();
544                                }
545
546                                // Modify target entry
547                                final Entry targetEntry =
548                                        decodeEntry(renamedEntries.values().iterator().next());
549
550                                if (change.isDeleteOldRDN()) {
551                                    for (final AVA ava : oldDN.rdn()) {
552                                        targetEntry.removeAttribute(ava.toAttribute(), null);
553                                    }
554                                }
555                                for (final AVA ava : newDN.rdn()) {
556                                    targetEntry.addAttribute(ava.toAttribute());
557                                }
558
559                                renamedEntries.remove(toNormalizedByteArray(targetEntry.getName()));
560                                renamedEntries.put(toNormalizedByteArray(targetEntry.getName()),
561                                        encodeEntry(targetEntry)[1]);
562
563                                // Add the renamed entries.
564                                final Iterator<byte[]> j = renamedEntries.values().iterator();
565                                while (j.hasNext()) {
566                                    final Entry renamedEntry = decodeEntry(j.next());
567                                    final byte[] existingEntryDn =
568                                            entries.get(toNormalizedByteArray(renamedEntry.getName()));
569
570                                    if (existingEntryDn != null) {
571                                        final Entry existingEntry = decodeEntry(existingEntryDn);
572                                        try {
573                                            final Entry tmp =
574                                                    listener.handleDuplicateEntry(change,
575                                                            existingEntry, renamedEntry);
576                                            entries.put(toNormalizedByteArray(tmp.getName()), encodeEntry(tmp)[1]);
577                                        } catch (final DecodeException e) {
578                                            return e;
579                                        }
580                                    } else {
581                                        entries.put(toNormalizedByteArray(renamedEntry.getName()),
582                                                encodeEntry(renamedEntry)[1]);
583                                    }
584                                }
585                                renamedEntries.clear();
586                            }
587                            return null;
588                        }
589
590                        @Override
591                        public DecodeException visitChangeRecord(final Void p,
592                                final ModifyRequest change) {
593                            if (entries.get(changeNormDN) == null) {
594                                try {
595                                    listener.handleRejectedChangeRecord(change,
596                                            REJECTED_CHANGE_FAIL_MODIFY.get(change.getName()
597                                                    .toString()));
598                                } catch (final DecodeException e) {
599                                    return e;
600                                }
601                            } else {
602                                final Entry entry = decodeEntry(entries.get(changeNormDN));
603                                for (final Modification modification : change.getModifications()) {
604                                    final ModificationType modType =
605                                            modification.getModificationType();
606                                    if (modType.equals(ModificationType.ADD)) {
607                                        entry.addAttribute(modification.getAttribute(), null);
608                                    } else if (modType.equals(ModificationType.DELETE)) {
609                                        entry.removeAttribute(modification.getAttribute(), null);
610                                    } else if (modType.equals(ModificationType.REPLACE)) {
611                                        entry.replaceAttribute(modification.getAttribute());
612                                    } else {
613                                        System.err.println("Unable to apply \"" + modType
614                                                + "\" modification to entry \"" + change.getName()
615                                                + "\": modification type not supported");
616                                    }
617                                }
618                                entries.put(changeNormDN, encodeEntry(entry)[1]);
619                            }
620                            return null;
621                        }
622
623                    }, null);
624
625            if (de != null) {
626                throw de;
627            }
628        }
629
630        return new EntryReader() {
631            private final Iterator<byte[]> iterator = entries.values().iterator();
632
633            @Override
634            public void close() throws IOException {
635                try {
636                    input.close();
637                } finally {
638                    patch.close();
639                }
640            }
641
642            @Override
643            public boolean hasNext() throws IOException {
644                return iterator.hasNext();
645            }
646
647            @Override
648            public Entry readEntry() throws IOException {
649                return decodeEntry(iterator.next());
650            }
651        };
652    }
653
654    /**
655     * Returns a filtered view of {@code input} containing only those entries
656     * which match the search base DN, scope, and filtered defined in
657     * {@code search}. In addition, returned entries will be filtered according
658     * to any attribute filtering criteria defined in the search request.
659     * <p>
660     * The filter and attribute descriptions will be decoded using the default
661     * schema.
662     *
663     * @param input
664     *            The entry reader containing the set of entries to be filtered.
665     * @param search
666     *            The search request defining the filtering criteria.
667     * @return A filtered view of {@code input} containing only those entries
668     *         which match the provided search request.
669     */
670    public static EntryReader search(final EntryReader input, final SearchRequest search) {
671        return search(input, search, Schema.getDefaultSchema());
672    }
673
674    /**
675     * Returns a filtered view of {@code input} containing only those entries
676     * which match the search base DN, scope, and filtered defined in
677     * {@code search}. In addition, returned entries will be filtered according
678     * to any attribute filtering criteria defined in the search request.
679     * <p>
680     * The filter and attribute descriptions will be decoded using the provided
681     * schema.
682     *
683     * @param input
684     *            The entry reader containing the set of entries to be filtered.
685     * @param search
686     *            The search request defining the filtering criteria.
687     * @param schema
688     *            The schema which should be used to decode the search filter
689     *            and attribute descriptions.
690     * @return A filtered view of {@code input} containing only those entries
691     *         which match the provided search request.
692     */
693    public static EntryReader search(final EntryReader input, final SearchRequest search,
694            final Schema schema) {
695        final Matcher matcher = search.getFilter().matcher(schema);
696
697        return new EntryReader() {
698            private Entry nextEntry = null;
699            private int entryCount = 0;
700
701            public void close() throws IOException {
702                input.close();
703            }
704
705            public boolean hasNext() throws IOException {
706                if (nextEntry == null) {
707                    final int sizeLimit = search.getSizeLimit();
708                    if (sizeLimit == 0 || entryCount < sizeLimit) {
709                        final DN baseDN = search.getName();
710                        final SearchScope scope = search.getScope();
711                        while (input.hasNext()) {
712                            final Entry entry = input.readEntry();
713                            if (entry.getName().isInScopeOf(baseDN, scope)
714                                    && matcher.matches(entry).toBoolean()) {
715                                nextEntry = filterEntry(entry);
716                                break;
717                            }
718                        }
719                    }
720                }
721                return nextEntry != null;
722            }
723
724            public Entry readEntry() throws IOException {
725                if (hasNext()) {
726                    final Entry entry = nextEntry;
727                    nextEntry = null;
728                    entryCount++;
729                    return entry;
730                } else {
731                    throw new NoSuchElementException();
732                }
733            }
734
735            private Entry filterEntry(final Entry entry) {
736                // TODO: rename attributes; move functionality to Entries.
737                if (search.getAttributes().isEmpty()) {
738                    if (search.isTypesOnly()) {
739                        final Entry filteredEntry = new LinkedHashMapEntry(entry.getName());
740                        for (final Attribute attribute : entry.getAllAttributes()) {
741                            filteredEntry.addAttribute(Attributes.emptyAttribute(attribute
742                                    .getAttributeDescription()));
743                        }
744                        return filteredEntry;
745                    } else {
746                        return entry;
747                    }
748                } else {
749                    final Entry filteredEntry = new LinkedHashMapEntry(entry.getName());
750                    for (final String atd : search.getAttributes()) {
751                        if ("*".equals(atd)) {
752                            for (final Attribute attribute : entry.getAllAttributes()) {
753                                if (attribute.getAttributeDescription().getAttributeType()
754                                        .getUsage() == AttributeUsage.USER_APPLICATIONS) {
755                                    if (search.isTypesOnly()) {
756                                        filteredEntry
757                                                .addAttribute(Attributes.emptyAttribute(attribute
758                                                        .getAttributeDescription()));
759                                    } else {
760                                        filteredEntry.addAttribute(attribute);
761                                    }
762                                }
763                            }
764                        } else if ("+".equals(atd)) {
765                            for (final Attribute attribute : entry.getAllAttributes()) {
766                                if (attribute.getAttributeDescription().getAttributeType()
767                                        .getUsage() != AttributeUsage.USER_APPLICATIONS) {
768                                    if (search.isTypesOnly()) {
769                                        filteredEntry
770                                                .addAttribute(Attributes.emptyAttribute(attribute
771                                                        .getAttributeDescription()));
772                                    } else {
773                                        filteredEntry.addAttribute(attribute);
774                                    }
775                                }
776                            }
777                        } else {
778                            final AttributeDescription ad =
779                                    AttributeDescription.valueOf(atd, schema);
780                            for (final Attribute attribute : entry.getAllAttributes(ad)) {
781                                if (search.isTypesOnly()) {
782                                    filteredEntry.addAttribute(Attributes.emptyAttribute(attribute
783                                            .getAttributeDescription()));
784                                } else {
785                                    filteredEntry.addAttribute(attribute);
786                                }
787                            }
788                        }
789                    }
790                    return filteredEntry;
791                }
792            }
793
794        };
795    }
796
797    private static List<byte[][]> readEntriesAsList(final EntryReader reader) throws IOException {
798        final List<byte[][]> entries = new ArrayList<>();
799
800        while (reader.hasNext()) {
801            final Entry entry = reader.readEntry();
802            entries.add(encodeEntry(entry));
803        }
804        // Sorting the list by DN
805        Collections.sort(entries, DN_ORDER2);
806
807        return entries;
808    }
809
810    private static TreeMap<byte[], byte[]> readEntriesAsMap(final EntryReader reader)
811            throws IOException {
812        final TreeMap<byte[], byte[]> entries = new TreeMap<>(DN_ORDER);
813
814        while (reader.hasNext()) {
815            final Entry entry = reader.readEntry();
816            final byte[][] bEntry = encodeEntry(entry);
817            entries.put(bEntry[0], bEntry[1]);
818        }
819
820        return entries;
821    }
822
823    private static Entry decodeEntry(final byte[] asn1EntryFormat) {
824        try {
825            return LDAP.readEntry(ASN1.getReader(asn1EntryFormat), new DecodeOptions());
826        } catch (IOException ex) {
827            throw new IllegalStateException(ex);
828        }
829    }
830
831    private static byte[] toNormalizedByteArray(DN dn) {
832        return dn.toNormalizedByteString().toByteArray();
833    }
834
835    private static byte[][] encodeEntry(final Entry entry) {
836        final byte[][] bEntry = new byte[2][];
837        // Store normalized DN
838        bEntry[0] = toNormalizedByteArray(entry.getName());
839        try {
840            // Store ASN1 representation of the entry.
841            final ByteStringBuilder bsb = new ByteStringBuilder();
842            LDAP.writeEntry(ASN1.getWriter(bsb), entry);
843            bEntry[1] = bsb.toByteArray();
844            return bEntry;
845        } catch (final IOException ioe) {
846            throw new IllegalStateException(ioe);
847        }
848    }
849
850    /** Prevent instantiation. */
851    private LDIF() {
852        // Do nothing.
853    }
854}