001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.io;
003
004import java.io.BufferedInputStream;
005import java.io.ByteArrayInputStream;
006import java.io.ByteArrayOutputStream;
007import java.io.IOException;
008import java.io.InputStream;
009import java.util.ArrayList;
010import java.util.Arrays;
011import java.util.HashMap;
012import java.util.HashSet;
013import java.util.List;
014import java.util.Locale;
015import java.util.Map;
016import java.util.Set;
017
018import org.openstreetmap.josm.data.Bounds;
019import org.openstreetmap.josm.data.DataSource;
020import org.openstreetmap.josm.data.coor.LatLon;
021import org.openstreetmap.josm.data.osm.BBox;
022import org.openstreetmap.josm.data.osm.DataSet;
023import org.openstreetmap.josm.data.osm.NodeData;
024import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
025import org.openstreetmap.josm.data.osm.PrimitiveData;
026import org.openstreetmap.josm.data.osm.RelationData;
027import org.openstreetmap.josm.data.osm.RelationMemberData;
028import org.openstreetmap.josm.data.osm.Tagged;
029import org.openstreetmap.josm.data.osm.UploadPolicy;
030import org.openstreetmap.josm.data.osm.User;
031import org.openstreetmap.josm.data.osm.WayData;
032import org.openstreetmap.josm.data.osm.pbf.Blob;
033import org.openstreetmap.josm.data.osm.pbf.BlobHeader;
034import org.openstreetmap.josm.data.osm.pbf.HeaderBlock;
035import org.openstreetmap.josm.data.osm.pbf.Info;
036import org.openstreetmap.josm.data.protobuf.ProtobufPacked;
037import org.openstreetmap.josm.data.protobuf.ProtobufParser;
038import org.openstreetmap.josm.data.protobuf.ProtobufRecord;
039import org.openstreetmap.josm.data.protobuf.WireType;
040import org.openstreetmap.josm.gui.progress.NullProgressMonitor;
041import org.openstreetmap.josm.gui.progress.ProgressMonitor;
042import org.openstreetmap.josm.tools.Utils;
043
044import jakarta.annotation.Nonnull;
045import jakarta.annotation.Nullable;
046
047/**
048 * Read OSM data from an OSM PBF file
049 * @since 18695
050 */
051public final class OsmPbfReader extends AbstractReader {
052    /**
053     * This could be replaced by {@link org.apache.commons.io.input.BoundedInputStream} from Apache Commons IO.
054     * However, Commons IO is not <i>currently</i> (2024-05-13) a required JOSM dependency, so we should avoid using it
055     * for now. Commons IO is a <i>transitive</i> dependency, currently pulled in by <code>org.apache.commons.compress</code>
056     * (see {@link org.apache.commons.compress.utils.BoundedInputStream}).
057     */
058    private static final class BoundedInputStream extends InputStream {
059        private final InputStream source;
060        private long count;
061        private long mark;
062
063        BoundedInputStream(InputStream source) {
064            this.source = source;
065        }
066
067        @Override
068        public int read() throws IOException {
069            final int read = this.source.read();
070            if (read > 0) {
071                count++;
072            }
073            return read;
074        }
075
076        @Override
077        public int read(@Nonnull byte[] b, int off, int len) throws IOException {
078            final int read = this.source.read(b, off, len);
079            if (read > 0) {
080                this.count += read;
081            }
082            return read;
083        }
084
085        @Override
086        public long skip(long n) throws IOException {
087            long skipped = super.skip(n);
088            this.count += skipped;
089            return skipped;
090        }
091
092        @Override
093        public int available() throws IOException {
094            return this.source.available();
095        }
096
097        @Override
098        public void close() throws IOException {
099            this.source.close();
100        }
101
102        @Override
103        public synchronized void mark(int readlimit) {
104            this.source.mark(readlimit);
105            this.mark = this.count;
106        }
107
108        @Override
109        public synchronized void reset() throws IOException {
110            this.source.reset();
111            this.count = this.mark;
112        }
113
114        @Override
115        public boolean markSupported() {
116            return this.source.markSupported();
117        }
118
119        long getCount() {
120            return this.count;
121        }
122    }
123
124    private static final long[] EMPTY_LONG = new long[0];
125    /**
126     * Nano degrees
127     */
128    private static final double NANO_DEGREES = 1e-9;
129    /**
130     * The maximum BlobHeader size. BlobHeaders should (but not must) be less than half this
131     */
132    private static final int MAX_BLOBHEADER_SIZE = 64 * 1024;
133    /**
134     * The maximum Blob size. Blobs should (but not must) be less than half this
135     */
136    private static final int MAX_BLOB_SIZE = 32 * 1024 * 1024;
137
138    private OsmPbfReader() {
139        // Hide constructor
140    }
141
142    /**
143     * Parse the given input source and return the dataset.
144     *
145     * @param source          the source input stream. Must not be null.
146     * @param progressMonitor the progress monitor. If null, {@link NullProgressMonitor#INSTANCE} is assumed
147     * @return the dataset with the parsed data
148     * @throws IllegalDataException     if an error was found while parsing the data from the source
149     * @throws IllegalArgumentException if source is null
150     */
151    public static DataSet parseDataSet(InputStream source, ProgressMonitor progressMonitor) throws IllegalDataException {
152        return new OsmPbfReader().doParseDataSet(source, progressMonitor);
153    }
154
155    @Override
156    protected DataSet doParseDataSet(InputStream source, ProgressMonitor progressMonitor) throws IllegalDataException {
157        return doParseDataSet(source, progressMonitor, this::parse);
158    }
159
160    private void parse(InputStream source) throws IllegalDataException, IOException {
161        final BoundedInputStream inputStream;
162        if (source.markSupported()) {
163            inputStream = new BoundedInputStream(source);
164        } else {
165            inputStream = new BoundedInputStream(new BufferedInputStream(source));
166        }
167        try (ProtobufParser parser = new ProtobufParser(inputStream)) {
168            final ByteArrayOutputStream baos = new ByteArrayOutputStream();
169            HeaderBlock headerBlock = null;
170            BlobHeader blobHeader = null;
171            while (parser.hasNext() && !this.cancel) {
172                if (blobHeader == null) {
173                    blobHeader = parseBlobHeader(inputStream, baos, parser);
174                } else if ("OSMHeader".equals(blobHeader.type())) {
175                    if (headerBlock != null) {
176                        throw new IllegalDataException("Too many header blocks in protobuf");
177                    }
178                    // OSM PBF is fun -- it has *nested* pbf data
179                    final Blob blob = parseBlob(blobHeader, inputStream, parser, baos);
180                    headerBlock = parseHeaderBlock(blob, baos);
181                    checkRequiredFeatures(headerBlock);
182                    blobHeader = null;
183                } else if ("OSMData".equals(blobHeader.type())) {
184                    if (headerBlock == null) {
185                        throw new IllegalStateException("A header block must occur before the first data block");
186                    }
187                    final Blob blob = parseBlob(blobHeader, inputStream, parser, baos);
188                    parseDataBlock(baos, headerBlock, blob);
189                    blobHeader = null;
190                } // Other software *may* extend the FileBlocks (from just "OSMHeader" and "OSMData"), so don't throw an error.
191            }
192        }
193    }
194
195    /**
196     * Parse a blob header
197     *
198     * @param cis    A counting stream to ensure we don't read too much data
199     * @param baos   A reusable stream
200     * @param parser The parser to read from
201     * @return The BlobHeader message
202     * @throws IOException          if one of the streams has an issue
203     * @throws IllegalDataException If the OSM PBF is (probably) corrupted
204     */
205    @Nonnull
206    private static BlobHeader parseBlobHeader(BoundedInputStream cis, ByteArrayOutputStream baos, ProtobufParser parser)
207            throws IOException, IllegalDataException {
208        String type = null;
209        byte[] indexData = null;
210        int datasize = Integer.MIN_VALUE;
211        int length = 0;
212        long start = cis.getCount();
213        while (parser.hasNext() && (length == 0 || cis.getCount() - start < length)) {
214            final ProtobufRecord current = new ProtobufRecord(baos, parser);
215            switch (current.getField()) {
216                case 1:
217                    type = current.asString();
218                    break;
219                case 2:
220                    indexData = current.getBytes();
221                    break;
222                case 3:
223                    datasize = current.asUnsignedVarInt().intValue();
224                    break;
225                default:
226                    start = cis.getCount();
227                    length += current.asUnsignedVarInt().intValue();
228                    if (length > MAX_BLOBHEADER_SIZE) { // There is a hard limit of 64 KiB for the BlobHeader. It *should* be less than 32 KiB.
229                        throw new IllegalDataException("OSM PBF BlobHeader is too large. PBF is probably corrupted. (" +
230                                Utils.getSizeString(MAX_BLOBHEADER_SIZE, Locale.ENGLISH) + " < " + Utils.getSizeString(length, Locale.ENGLISH));
231                    }
232            }
233        }
234        if (type == null || Integer.MIN_VALUE == datasize) {
235            throw new IllegalDataException("OSM PBF BlobHeader could not be read. PBF is probably corrupted.");
236        } else if (datasize > MAX_BLOB_SIZE) { // There is a hard limit of 32 MiB for the blob size. It *should* be less than 16 MiB.
237            throw new IllegalDataException("OSM PBF Blob size is too large. PBF is probably corrupted. ("
238                    + Utils.getSizeString(MAX_BLOB_SIZE, Locale.ENGLISH) + " < " + Utils.getSizeString(datasize, Locale.ENGLISH));
239        }
240        return new BlobHeader(type, indexData, datasize);
241    }
242
243    /**
244     * Parse a blob from the PBF file
245     *
246     * @param header The header with the blob information (most critically, the length of the blob)
247     * @param cis    Used to ensure we don't read too much data
248     * @param parser The parser to read records from
249     * @param baos   The reusable output stream
250     * @return The blob to use elsewhere
251     * @throws IOException If one of the streams has an issue
252     */
253    @Nonnull
254    private static Blob parseBlob(BlobHeader header, BoundedInputStream cis, ProtobufParser parser, ByteArrayOutputStream baos)
255            throws IOException {
256        long start = cis.getCount();
257        int size = Integer.MIN_VALUE;
258        Blob.CompressionType type = null;
259        // Needed since size and compression type + compression data may be in a different order
260        byte[] bytes = null;
261        while (parser.hasNext() && cis.getCount() - start < header.dataSize()) {
262            try (ProtobufRecord current = new ProtobufRecord(baos, parser)) {
263                switch (current.getField()) {
264                    case 1:
265                        type = Blob.CompressionType.raw;
266                        bytes = current.getBytes();
267                        break;
268                    case 2:
269                        size = current.asUnsignedVarInt().intValue();
270                        break;
271                    case 3:
272                        type = Blob.CompressionType.zlib;
273                        bytes = current.getBytes();
274                        break;
275                    case 4:
276                        type = Blob.CompressionType.lzma;
277                        bytes = current.getBytes();
278                        break;
279                    case 5:
280                        type = Blob.CompressionType.bzip2;
281                        bytes = current.getBytes();
282                        break;
283                    case 6:
284                        type = Blob.CompressionType.lz4;
285                        bytes = current.getBytes();
286                        break;
287                    case 7:
288                        type = Blob.CompressionType.zstd;
289                        bytes = current.getBytes();
290                        break;
291                    default:
292                        throw new IllegalStateException("Unknown compression type: " + current.getField());
293                }
294            }
295        }
296        if (type == null) {
297            throw new IllegalStateException("Compression type not found, pbf may be malformed");
298        }
299        return new Blob(size, type, bytes);
300    }
301
302    /**
303     * Parse a header block. This assumes that the parser has hit a string with the text "OSMHeader".
304     *
305     * @param blob The blob with the header block data
306     * @param baos The reusable output stream to use
307     * @return The parsed HeaderBlock
308     * @throws IOException if one of the {@link InputStream}s has a problem
309     */
310    @Nonnull
311    private static HeaderBlock parseHeaderBlock(Blob blob, ByteArrayOutputStream baos) throws IOException {
312        try (InputStream blobInput = blob.inputStream();
313             ProtobufParser parser = new ProtobufParser(blobInput)) {
314            BBox bbox = null;
315            List<String> required = new ArrayList<>();
316            List<String> optional = new ArrayList<>();
317            String program = null;
318            String source = null;
319            Long osmosisReplicationTimestamp = null;
320            Long osmosisReplicationSequenceNumber = null;
321            String osmosisReplicationBaseUrl = null;
322            while (parser.hasNext()) {
323                final ProtobufRecord current = new ProtobufRecord(baos, parser);
324                switch (current.getField()) {
325                    case 1: // bbox
326                        bbox = parseBBox(baos, current);
327                        break;
328                    case 4: // repeated required features
329                        required.add(current.asString());
330                        break;
331                    case 5: // repeated optional features
332                        optional.add(current.asString());
333                        break;
334                    case 16: // writing program
335                        program = current.asString();
336                        break;
337                    case 17: // source
338                        source = current.asString();
339                        break;
340                    case 32: // osmosis replication timestamp
341                        osmosisReplicationTimestamp = current.asSignedVarInt().longValue();
342                        break;
343                    case 33: // osmosis replication sequence number
344                        osmosisReplicationSequenceNumber = current.asSignedVarInt().longValue();
345                        break;
346                    case 34: // osmosis replication base url
347                        osmosisReplicationBaseUrl = current.asString();
348                        break;
349                    default: // fall through -- unknown header block field
350                }
351            }
352            return new HeaderBlock(bbox, required.toArray(new String[0]), optional.toArray(new String[0]), program,
353                    source, osmosisReplicationTimestamp, osmosisReplicationSequenceNumber, osmosisReplicationBaseUrl);
354        }
355    }
356
357    /**
358     * Ensure that we support all the required features in the PBF
359     *
360     * @param headerBlock The HeaderBlock to check
361     * @throws IllegalDataException If there exists at least one feature that we do not support
362     */
363    private static void checkRequiredFeatures(HeaderBlock headerBlock) throws IllegalDataException {
364        Set<String> supportedFeatures = new HashSet<>(Arrays.asList("OsmSchema-V0.6", "DenseNodes", "HistoricalInformation"));
365        for (String requiredFeature : headerBlock.requiredFeatures()) {
366            if (!supportedFeatures.contains(requiredFeature)) {
367                throw new IllegalDataException("PBF Parser: Unknown required feature " + requiredFeature);
368            }
369        }
370    }
371
372    /**
373     * Parse a data blob (should be "OSMData")
374     *
375     * @param baos        The reusable stream
376     * @param headerBlock The header block with data source information
377     * @param blob        The blob to read OSM data from
378     * @throws IOException          if we don't support the compression type
379     * @throws IllegalDataException If an invalid OSM primitive was read
380     */
381    private void parseDataBlock(ByteArrayOutputStream baos, HeaderBlock headerBlock, Blob blob) throws IOException, IllegalDataException {
382        String[] stringTable = null; // field 1, note that stringTable[0] is a delimiter, so it is always blank and unused
383        // field 2 -- we cannot parse these live just in case the following fields come later
384        final List<ProtobufRecord> primitiveGroups = new ArrayList<>();
385        int granularity = 100; // field 17
386        long latOffset = 0; // field 19
387        long lonOffset = 0; // field 20
388        int dateGranularity = 1000; // field 18, default is milliseconds since the 1970 epoch
389        try (InputStream inputStream = blob.inputStream();
390             ProtobufParser parser = new ProtobufParser(inputStream)) {
391            while (parser.hasNext()) {
392                final ProtobufRecord protobufRecord = new ProtobufRecord(baos, parser);
393                switch (protobufRecord.getField()) {
394                    case 1:
395                        stringTable = parseStringTable(baos, protobufRecord.getBytes());
396                        break;
397                    case 2:
398                        primitiveGroups.add(protobufRecord);
399                        break;
400                    case 17:
401                        granularity = protobufRecord.asUnsignedVarInt().intValue();
402                        break;
403                    case 18:
404                        dateGranularity = protobufRecord.asUnsignedVarInt().intValue();
405                        break;
406                    case 19:
407                        latOffset = protobufRecord.asUnsignedVarInt().longValue();
408                        break;
409                    case 20:
410                        lonOffset = protobufRecord.asUnsignedVarInt().longValue();
411                        break;
412                    default: // Pass, since someone might have extended the format
413                }
414            }
415        }
416        final PrimitiveBlockRecord primitiveBlockRecord = new PrimitiveBlockRecord(stringTable, granularity, latOffset, lonOffset,
417                dateGranularity);
418        final DataSet ds = getDataSet();
419        if (!primitiveGroups.isEmpty() && headerBlock.bbox() != null) {
420            try {
421                ds.beginUpdate();
422                ds.addDataSource(new DataSource(new Bounds((LatLon) headerBlock.bbox().getMin(), (LatLon) headerBlock.bbox().getMax()),
423                        headerBlock.source()));
424            } finally {
425                ds.endUpdate();
426            }
427        }
428        for (ProtobufRecord primitiveGroup : primitiveGroups) {
429            try (primitiveGroup) {
430                ds.beginUpdate();
431                parsePrimitiveGroup(baos, primitiveGroup.getBytes(), primitiveBlockRecord);
432            } finally {
433                ds.endUpdate();
434            }
435        }
436    }
437
438    /**
439     * This parses a bbox from a record (HeaderBBox message)
440     *
441     * @param baos    The reusable {@link ByteArrayOutputStream} to avoid unnecessary allocations
442     * @param current The current record
443     * @return The <i>immutable</i> bbox, or {@code null}
444     * @throws IOException If something happens with the {@link InputStream}s (probably won't happen)
445     */
446    @Nullable
447    private static BBox parseBBox(ByteArrayOutputStream baos, ProtobufRecord current) throws IOException {
448        try (ByteArrayInputStream bboxInputStream = new ByteArrayInputStream(current.getBytes());
449             ProtobufParser bboxParser = new ProtobufParser(bboxInputStream)) {
450            double left = Double.NaN;
451            double right = Double.NaN;
452            double top = Double.NaN;
453            double bottom = Double.NaN;
454            while (bboxParser.hasNext()) {
455                final ProtobufRecord protobufRecord = new ProtobufRecord(baos, bboxParser);
456                if (protobufRecord.getType() == WireType.VARINT) {
457                    double value = protobufRecord.asSignedVarInt().longValue() * NANO_DEGREES;
458                    switch (protobufRecord.getField()) {
459                        case 1:
460                            left = value;
461                            break;
462                        case 2:
463                            right = value;
464                            break;
465                        case 3:
466                            top = value;
467                            break;
468                        case 4:
469                            bottom = value;
470                            break;
471                        default: // Fall through -- someone might have extended the format
472                    }
473                }
474            }
475            if (!Double.isNaN(left) && !Double.isNaN(top) && !Double.isNaN(right) && !Double.isNaN(bottom)) {
476                return new BBox(left, top, right, bottom).toImmutable();
477            }
478        }
479        return null;
480    }
481
482    /**
483     * Parse the string table
484     *
485     * @param baos  The reusable stream
486     * @param bytes The message bytes
487     * @return The parsed table (reminder: index 0 is empty, note that all strings are already interned by {@link String#intern()})
488     * @throws IOException if something happened while reading a {@link ByteArrayInputStream}
489     */
490    @Nonnull
491    private static String[] parseStringTable(ByteArrayOutputStream baos, byte[] bytes) throws IOException {
492        try (ByteArrayInputStream is = new ByteArrayInputStream(bytes);
493             ProtobufParser parser = new ProtobufParser(is)) {
494            final List<String> list = new ArrayList<>();
495            while (parser.hasNext()) {
496                final ProtobufRecord protobufRecord = new ProtobufRecord(baos, parser);
497                if (protobufRecord.getField() == 1) {
498                    list.add(protobufRecord.asString().intern()); // field is technically repeated bytes
499                }
500            }
501            return list.toArray(new String[0]);
502        }
503    }
504
505    /**
506     * Parse a PrimitiveGroup. Note: this parsing implementation doesn't check and make certain that all primitives in the group are the same
507     * type.
508     *
509     * @param baos                 The reusable stream
510     * @param bytes                The bytes to decode
511     * @param primitiveBlockRecord The record to use for creating the primitives
512     * @throws IllegalDataException if one of the primitive records was invalid
513     * @throws IOException          if something happened while reading a {@link ByteArrayInputStream}
514     */
515    private void parsePrimitiveGroup(ByteArrayOutputStream baos, byte[] bytes, PrimitiveBlockRecord primitiveBlockRecord)
516            throws IllegalDataException, IOException {
517        try (ByteArrayInputStream bais = new ByteArrayInputStream(bytes);
518             ProtobufParser parser = new ProtobufParser(bais)) {
519            while (parser.hasNext()) {
520                final ProtobufRecord protobufRecord = new ProtobufRecord(baos, parser);
521                switch (protobufRecord.getField()) {
522                    case 1: // Nodes, repeated
523                        parseNode(baos, protobufRecord.getBytes(), primitiveBlockRecord);
524                        break;
525                    case 2: // Dense nodes, not repeated
526                        parseDenseNodes(baos, protobufRecord.getBytes(), primitiveBlockRecord);
527                        break;
528                    case 3: // Ways, repeated
529                        parseWay(baos, protobufRecord.getBytes(), primitiveBlockRecord);
530                        break;
531                    case 4: // relations, repeated
532                        parseRelation(baos, protobufRecord.getBytes(), primitiveBlockRecord);
533                        break;
534                    case 5: // Changesets, repeated
535                        // Skip -- we don't have a good way to store changeset information in JOSM
536                    default: // OSM PBF could be extended
537                }
538            }
539        }
540    }
541
542    /**
543     * Parse a singular node
544     *
545     * @param baos                 The reusable stream
546     * @param bytes                The bytes to decode
547     * @param primitiveBlockRecord The record to use (mostly for tags and lat/lon calculations)
548     * @throws IllegalDataException if the PBF did not provide all the data necessary for node creation
549     * @throws IOException          if something happened while reading a {@link ByteArrayInputStream}
550     */
551    private void parseNode(ByteArrayOutputStream baos, byte[] bytes, PrimitiveBlockRecord primitiveBlockRecord)
552            throws IllegalDataException, IOException {
553        try (ByteArrayInputStream bais = new ByteArrayInputStream(bytes);
554             ProtobufParser parser = new ProtobufParser(bais)) {
555            long id = Long.MIN_VALUE;
556            final List<String> keys = new ArrayList<>();
557            final List<String> values = new ArrayList<>();
558            Info info = null;
559            long lat = Long.MIN_VALUE;
560            long lon = Long.MIN_VALUE;
561            while (parser.hasNext()) {
562                final ProtobufRecord protobufRecord = new ProtobufRecord(baos, parser);
563                switch (protobufRecord.getField()) {
564                    case 1:
565                        id = protobufRecord.asSignedVarInt().intValue();
566                        break;
567                    case 2:
568                        for (long number : new ProtobufPacked(protobufRecord.getBytes()).getArray()) {
569                            keys.add(primitiveBlockRecord.stringTable[(int) number]);
570                        }
571                        break;
572                    case 3:
573                        for (long number : new ProtobufPacked(protobufRecord.getBytes()).getArray()) {
574                            values.add(primitiveBlockRecord.stringTable[(int) number]);
575                        }
576                        break;
577                    case 4:
578                        info = parseInfo(baos, protobufRecord.getBytes());
579                        break;
580                    case 8:
581                        lat = protobufRecord.asSignedVarInt().longValue();
582                        break;
583                    case 9:
584                        lon = protobufRecord.asSignedVarInt().longValue();
585                        break;
586                    default: // Fall through -- PBF could be extended (unlikely)
587                }
588            }
589            if (id == Long.MIN_VALUE || lat == Long.MIN_VALUE || lon == Long.MIN_VALUE) {
590                throw new IllegalDataException("OSM PBF did not provide all the required node information");
591            }
592            final NodeData node = new NodeData(id);
593            node.setCoor(calculateLatLon(primitiveBlockRecord, lat, lon));
594            addTags(node, keys, values);
595            if (info != null) {
596                setOsmPrimitiveData(primitiveBlockRecord, node, info);
597            } else {
598                ds.setUploadPolicy(UploadPolicy.DISCOURAGED);
599            }
600            buildPrimitive(node);
601        }
602    }
603
604    /**
605     * Parse dense nodes from a record
606     *
607     * @param baos                 The reusable output stream
608     * @param bytes                The bytes for the dense node
609     * @param primitiveBlockRecord Used for data that is common between several different objects.
610     * @throws IllegalDataException if the nodes could not be parsed, or one of the nodes would be malformed
611     * @throws IOException          if something happened while reading a {@link ByteArrayInputStream}
612     */
613    private void parseDenseNodes(ByteArrayOutputStream baos, byte[] bytes, PrimitiveBlockRecord primitiveBlockRecord)
614            throws IllegalDataException, IOException {
615        long[] ids = EMPTY_LONG;
616        long[] lats = EMPTY_LONG;
617        long[] lons = EMPTY_LONG;
618        long[] keyVals = EMPTY_LONG; // technically can be int
619        Info[] denseInfo = null;
620        try (ByteArrayInputStream bais = new ByteArrayInputStream(bytes);
621             ProtobufParser parser = new ProtobufParser(bais)) {
622            while (parser.hasNext()) {
623                final ProtobufRecord protobufRecord = new ProtobufRecord(baos, parser);
624                switch (protobufRecord.getField()) {
625                    case 1: // packed node ids, DELTA encoded
626                        long[] tids = decodePackedSInt64(new ProtobufPacked(protobufRecord.getBytes()).getArray());
627                        ids = joinArrays(ids, tids);
628                        break;
629                    case 5: // DenseInfo
630                        denseInfo = parseDenseInfo(baos, protobufRecord.getBytes()); // not repeated or packed
631                        break;
632                    case 8: // packed lat, DELTA encoded
633                        long[] tlats = decodePackedSInt64(new ProtobufPacked(protobufRecord.getBytes()).getArray());
634                        lats = joinArrays(lats, tlats);
635                        break;
636                    case 9: // packed lon, DELTA encoded
637                        long[] tlons = decodePackedSInt64(new ProtobufPacked(protobufRecord.getBytes()).getArray());
638                        lons = joinArrays(lons, tlons);
639                        break;
640                    case 10: // key_val mappings, packed. '0' used as separator between nodes
641                        long[] tkeyVal = new ProtobufPacked(protobufRecord.getBytes()).getArray();
642                        keyVals = joinArrays(keyVals, tkeyVal);
643                        break;
644                    default: // Someone might have extended the PBF format
645                }
646            }
647        }
648
649        int keyValIndex = 0; // This index must not reset between nodes, and must always increment
650        if (ids.length == lats.length && lats.length == lons.length && (denseInfo == null || denseInfo.length == lons.length)) {
651            long id = 0;
652            long lat = 0;
653            long lon = 0;
654            for (int i = 0; i < ids.length; i++) {
655                final NodeData node;
656                id += ids[i];
657                node = new NodeData(id);
658                if (denseInfo != null) {
659                    final Info info = denseInfo[i];
660                    setOsmPrimitiveData(primitiveBlockRecord, node, info);
661                } else {
662                    ds.setUploadPolicy(UploadPolicy.DISCOURAGED);
663                }
664                lat += lats[i];
665                lon += lons[i];
666                // Not very efficient when Node doesn't store the LatLon. Hopefully not too much of an issue
667                node.setCoor(calculateLatLon(primitiveBlockRecord, lat, lon));
668                String key = null;
669                while (keyValIndex < keyVals.length) {
670                    int stringIndex = (int) keyVals[keyValIndex];
671                    // StringTable[0] is always an empty string, and acts as a separator between the tags of different nodes here
672                    if (stringIndex != 0) {
673                        if (key == null) {
674                            key = primitiveBlockRecord.stringTable[stringIndex];
675                        } else {
676                            node.put(key, primitiveBlockRecord.stringTable[stringIndex]);
677                            key = null;
678                        }
679                        keyValIndex++;
680                    } else {
681                        keyValIndex++;
682                        break;
683                    }
684                }
685                // Just add the nodes as we make them -- avoid creating another list that expands every time we parse a node
686                buildPrimitive(node);
687            }
688        } else {
689            throw new IllegalDataException("OSM PBF has mismatched DenseNode lengths");
690        }
691    }
692
693    /**
694     * Parse a way from the PBF
695     *
696     * @param baos                 The reusable stream
697     * @param bytes                The bytes for the way
698     * @param primitiveBlockRecord Used for common information, like tags
699     * @throws IllegalDataException if an invalid way could have been created
700     * @throws IOException          if something happened while reading a {@link ByteArrayInputStream}
701     */
702    private void parseWay(ByteArrayOutputStream baos, byte[] bytes, PrimitiveBlockRecord primitiveBlockRecord)
703            throws IllegalDataException, IOException {
704        long id = Long.MIN_VALUE;
705        List<String> keys = new ArrayList<>();
706        List<String> values = new ArrayList<>();
707        Info info = null;
708        long[] refs = EMPTY_LONG; // DELTA encoded
709        // We don't do live drawing, so we don't care about lats and lons (we essentially throw them away with the current parser)
710        // This is for the optional feature "LocationsOnWays"
711        try (ByteArrayInputStream bais = new ByteArrayInputStream(bytes);
712             ProtobufParser parser = new ProtobufParser(bais)) {
713            while (parser.hasNext()) {
714                final ProtobufRecord protobufRecord = new ProtobufRecord(baos, parser);
715                switch (protobufRecord.getField()) {
716                    case 1:
717                        id = protobufRecord.asUnsignedVarInt().longValue();
718                        break;
719                    case 2:
720                        for (long number : new ProtobufPacked(protobufRecord.getBytes()).getArray()) {
721                            keys.add(primitiveBlockRecord.stringTable[(int) number]);
722                        }
723                        break;
724                    case 3:
725                        for (long number : new ProtobufPacked(protobufRecord.getBytes()).getArray()) {
726                            values.add(primitiveBlockRecord.stringTable[(int) number]);
727                        }
728                        break;
729                    case 4:
730                        info = parseInfo(baos, protobufRecord.getBytes());
731                        break;
732                    case 8:
733                        long[] tRefs = decodePackedSInt64(new ProtobufPacked(protobufRecord.getBytes()).getArray());
734                        refs = joinArrays(refs, tRefs);
735                        break;
736                    // case 9 and 10 are for "LocationsOnWays" -- this is only usable if we can create the way geometry directly
737                    // if this is ever supported, lats = joinArrays(lats, decodePackedSInt64(...))
738                    default: // PBF could be expanded by other people
739                }
740            }
741        }
742        if (refs.length == 0 || id == Long.MIN_VALUE) {
743            throw new IllegalDataException("A way with either no id or no nodes was found");
744        }
745        final WayData wayData = new WayData(id);
746        final List<Long> nodeIds = new ArrayList<>(refs.length);
747        long ref = 0;
748        for (long tRef : refs) {
749            ref += tRef;
750            nodeIds.add(ref);
751        }
752        this.ways.put(wayData.getUniqueId(), nodeIds);
753        addTags(wayData, keys, values);
754        if (info != null) {
755            setOsmPrimitiveData(primitiveBlockRecord, wayData, info);
756        } else {
757            ds.setUploadPolicy(UploadPolicy.DISCOURAGED);
758        }
759        buildPrimitive(wayData);
760    }
761
762    /**
763     * Parse a relation from a PBF
764     *
765     * @param baos                 The reusable stream
766     * @param bytes                The bytes to use
767     * @param primitiveBlockRecord Mostly used for tags
768     * @throws IllegalDataException if the PBF had a bad relation definition
769     * @throws IOException          if something happened while reading a {@link ByteArrayInputStream}
770     */
771    private void parseRelation(ByteArrayOutputStream baos, byte[] bytes, PrimitiveBlockRecord primitiveBlockRecord)
772            throws IllegalDataException, IOException {
773        long id = Long.MIN_VALUE;
774        final List<String> keys = new ArrayList<>();
775        final List<String> values = new ArrayList<>();
776        Info info = null;
777        long[] rolesStringId = EMPTY_LONG; // Technically int
778        long[] memids = EMPTY_LONG;
779        long[] types = EMPTY_LONG; // Technically an enum
780        try (ByteArrayInputStream bais = new ByteArrayInputStream(bytes);
781             ProtobufParser parser = new ProtobufParser(bais)) {
782            while (parser.hasNext()) {
783                final ProtobufRecord protobufRecord = new ProtobufRecord(baos, parser);
784                switch (protobufRecord.getField()) {
785                    case 1:
786                        id = protobufRecord.asUnsignedVarInt().longValue();
787                        break;
788                    case 2:
789                        for (long number : new ProtobufPacked(protobufRecord.getBytes()).getArray()) {
790                            keys.add(primitiveBlockRecord.stringTable[(int) number]);
791                        }
792                        break;
793                    case 3:
794                        for (long number : new ProtobufPacked(protobufRecord.getBytes()).getArray()) {
795                            values.add(primitiveBlockRecord.stringTable[(int) number]);
796                        }
797                        break;
798                    case 4:
799                        info = parseInfo(baos, protobufRecord.getBytes());
800                        break;
801                    case 8:
802                        long[] tRoles = new ProtobufPacked(protobufRecord.getBytes()).getArray();
803                        rolesStringId = joinArrays(rolesStringId, tRoles);
804                        break;
805                    case 9:
806                        long[] tMemids = decodePackedSInt64(new ProtobufPacked(protobufRecord.getBytes()).getArray());
807                        memids = joinArrays(memids, tMemids);
808                        break;
809                    case 10:
810                        long[] tTypes = new ProtobufPacked(protobufRecord.getBytes()).getArray();
811                        types = joinArrays(types, tTypes);
812                        break;
813                    default: // Fall through for PBF extensions
814                }
815            }
816        }
817        if (keys.size() != values.size() || rolesStringId.length != memids.length || memids.length != types.length || id == Long.MIN_VALUE) {
818            throw new IllegalDataException("OSM PBF contains a bad relation definition");
819        }
820        final RelationData data = new RelationData(id);
821        if (info != null) {
822            setOsmPrimitiveData(primitiveBlockRecord, data, info);
823        } else {
824            ds.setUploadPolicy(UploadPolicy.DISCOURAGED);
825        }
826        addTags(data, keys, values);
827        OsmPrimitiveType[] valueTypes = OsmPrimitiveType.values();
828        List<RelationMemberData> members = new ArrayList<>(rolesStringId.length);
829        long memberId = 0;
830        for (int i = 0; i < rolesStringId.length; i++) {
831            String role = primitiveBlockRecord.stringTable[(int) rolesStringId[i]];
832            memberId += memids[i];
833            OsmPrimitiveType type = valueTypes[(int) types[i]];
834            members.add(new RelationMemberData(role, type, memberId));
835        }
836        this.relations.put(data.getUniqueId(), members);
837        buildPrimitive(data);
838    }
839
840    /**
841     * Parse info for an object
842     *
843     * @param baos  The reusable stream to use
844     * @param bytes The bytes to decode
845     * @return The info for an object
846     * @throws IOException if something happened while reading a {@link ByteArrayInputStream}
847     */
848    @Nonnull
849    private static Info parseInfo(ByteArrayOutputStream baos, byte[] bytes) throws IOException {
850        try (ByteArrayInputStream bais = new ByteArrayInputStream(bytes);
851             ProtobufParser parser = new ProtobufParser(bais)) {
852            int version = -1;
853            Long timestamp = null;
854            Long changeset = null;
855            Integer uid = null;
856            Integer userSid = null;
857            boolean visible = true;
858            while (parser.hasNext()) {
859                final ProtobufRecord protobufRecord = new ProtobufRecord(baos, parser);
860                switch (protobufRecord.getField()) {
861                    case 1:
862                        version = protobufRecord.asUnsignedVarInt().intValue();
863                        break;
864                    case 2:
865                        timestamp = protobufRecord.asUnsignedVarInt().longValue();
866                        break;
867                    case 3:
868                        changeset = protobufRecord.asUnsignedVarInt().longValue();
869                        break;
870                    case 4:
871                        uid = protobufRecord.asUnsignedVarInt().intValue();
872                        break;
873                    case 5:
874                        userSid = protobufRecord.asUnsignedVarInt().intValue();
875                        break;
876                    case 6:
877                        visible = protobufRecord.asUnsignedVarInt().byteValue() == 1;
878                        break;
879                    default: // Fall through, since the PBF format could be extended
880                }
881            }
882            return new Info(version, timestamp, changeset, uid, userSid, visible);
883        }
884    }
885
886    /**
887     * Calculate the actual lat lon
888     *
889     * @param primitiveBlockRecord The record with offset and granularity data
890     * @param lat                  The latitude from the PBF
891     * @param lon                  The longitude from the PBF
892     * @return The actual {@link LatLon}, accounting for PBF offset and granularity changes
893     */
894    @Nonnull
895    private static LatLon calculateLatLon(PrimitiveBlockRecord primitiveBlockRecord, long lat, long lon) {
896        return new LatLon(NANO_DEGREES * (primitiveBlockRecord.latOffset + (primitiveBlockRecord.granularity * lat)),
897                NANO_DEGREES * (primitiveBlockRecord.lonOffset + (primitiveBlockRecord.granularity * lon)));
898    }
899
900    /**
901     * Add a set of tags to a primitive
902     *
903     * @param primitive The primitive to add tags to
904     * @param keys      The keys (must match the size of the values)
905     * @param values    The values (must match the size of the keys)
906     */
907    private static void addTags(Tagged primitive, List<String> keys, List<String> values) {
908        if (keys.isEmpty()) {
909            return;
910        }
911        Map<String, String> tagMap = new HashMap<>(keys.size());
912        for (int i = 0; i < keys.size(); i++) {
913            tagMap.put(keys.get(i), values.get(i));
914        }
915        primitive.putAll(tagMap);
916    }
917
918    /**
919     * Set the primitive data for an object
920     *
921     * @param primitiveBlockRecord The record with data for the current primitive (currently uses {@link PrimitiveBlockRecord#stringTable} and
922     *                             {@link PrimitiveBlockRecord#dateGranularity}).
923     * @param primitive            The primitive to add the information to
924     * @param info                 The specific info for the primitive
925     */
926    private static void setOsmPrimitiveData(PrimitiveBlockRecord primitiveBlockRecord, PrimitiveData primitive, Info info) {
927        primitive.setVisible(info.isVisible());
928        if (info.timestamp() != null) {
929            primitive.setRawTimestamp(Math.toIntExact(info.timestamp() * primitiveBlockRecord.dateGranularity / 1000));
930        }
931        if (info.uid() != null && info.userSid() != null) {
932            primitive.setUser(User.createOsmUser(info.uid(), primitiveBlockRecord.stringTable[info.userSid()]));
933        } else if (info.uid() != null) {
934            primitive.setUser(User.getById(info.uid()));
935        }
936        if (info.version() > 0) {
937            primitive.setVersion(info.version());
938        }
939        if (info.changeset() != null) {
940            primitive.setChangesetId(Math.toIntExact(info.changeset()));
941        }
942    }
943
944    /**
945     * Convert an array of numbers to an array of longs, decoded from uint (zig zag decoded)
946     *
947     * @param numbers The numbers to convert
948     * @return The long array (the same array that was passed in)
949     */
950    @Nonnull
951    private static long[] decodePackedSInt64(long[] numbers) {
952        for (int i = 0; i < numbers.length; i++) {
953            numbers[i] = ProtobufParser.decodeZigZag(numbers[i]);
954        }
955        return numbers;
956    }
957
958    /**
959     * Join two different arrays
960     *
961     * @param array1 The first array
962     * @param array2 The second array
963     * @return The joined arrays -- may return one of the original arrays, if the other is empty
964     */
965    @Nonnull
966    private static long[] joinArrays(long[] array1, long[] array2) {
967        if (array1.length == 0) {
968            return array2;
969        }
970        if (array2.length == 0) {
971            return array1;
972        }
973        long[] result = Arrays.copyOf(array1, array1.length + array2.length);
974        System.arraycopy(array2, 0, result, array1.length, array2.length);
975        return result;
976    }
977
978    /**
979     * Parse dense info
980     *
981     * @param baos  The reusable stream
982     * @param bytes The bytes to decode
983     * @return The dense info array
984     * @throws IllegalDataException If the data has mismatched array lengths
985     * @throws IOException          if something happened while reading a {@link ByteArrayInputStream}
986     */
987    @Nonnull
988    private static Info[] parseDenseInfo(ByteArrayOutputStream baos, byte[] bytes) throws IllegalDataException, IOException {
989        long[] version = EMPTY_LONG; // technically ints
990        long[] timestamp = EMPTY_LONG;
991        long[] changeset = EMPTY_LONG;
992        long[] uid = EMPTY_LONG; // technically int
993        long[] userSid = EMPTY_LONG; // technically int
994        long[] visible = EMPTY_LONG; // optional, true if not set, technically booleans
995        try (ByteArrayInputStream bais = new ByteArrayInputStream(bytes);
996             ProtobufParser parser = new ProtobufParser(bais)) {
997            while (parser.hasNext()) {
998                final ProtobufRecord protobufRecord = new ProtobufRecord(baos, parser);
999                switch (protobufRecord.getField()) {
1000                    case 1:
1001                        long[] tVersion = new ProtobufPacked(protobufRecord.getBytes()).getArray();
1002                        version = joinArrays(version, tVersion);
1003                        break;
1004                    case 2:
1005                        long[] tTimestamp = decodePackedSInt64(new ProtobufPacked(protobufRecord.getBytes()).getArray());
1006                        timestamp = joinArrays(timestamp, tTimestamp);
1007                        break;
1008                    case 3:
1009                        long[] tChangeset = decodePackedSInt64(new ProtobufPacked(protobufRecord.getBytes()).getArray());
1010                        changeset = joinArrays(changeset, tChangeset);
1011                        break;
1012                    case 4:
1013                        long[] tUid = decodePackedSInt64(new ProtobufPacked(protobufRecord.getBytes()).getArray());
1014                        uid = joinArrays(uid, tUid);
1015                        break;
1016                    case 5:
1017                        long[] tUserSid = decodePackedSInt64(new ProtobufPacked(protobufRecord.getBytes()).getArray());
1018                        userSid = joinArrays(userSid, tUserSid);
1019                        break;
1020                    case 6:
1021                        long[] tVisible = new ProtobufPacked(protobufRecord.getBytes()).getArray();
1022                        visible = joinArrays(visible, tVisible);
1023                        break;
1024                    default: // Fall through
1025                }
1026            }
1027        }
1028        if (version.length > 0) {
1029            final Info[] infos = new Info[version.length];
1030            long lastTimestamp = 0; // delta encoded
1031            long lastChangeset = 0; // delta encoded
1032            long lastUid = 0; // delta encoded,
1033            long lastUserSid = 0; // delta encoded, string id for username
1034            for (int i = 0; i < version.length; i++) {
1035                if (timestamp.length > i)
1036                    lastTimestamp += timestamp[i];
1037                if (changeset.length > i)
1038                    lastChangeset += changeset[i];
1039                if (uid.length > i && userSid.length > i) {
1040                    lastUid += uid[i];
1041                    lastUserSid += userSid[i];
1042                }
1043                infos[i] = new Info((int) version[i], lastTimestamp, lastChangeset, (int) lastUid, (int) lastUserSid,
1044                        visible == EMPTY_LONG || visible[i] == 1);
1045            }
1046            return infos;
1047        }
1048        throw new IllegalDataException("OSM PBF has mismatched DenseInfo lengths");
1049    }
1050
1051    /**
1052     * A record class for passing PrimitiveBlock information to the PrimitiveGroup parser
1053     */
1054    private static final class PrimitiveBlockRecord {
1055        private final String[] stringTable;
1056        private final int granularity;
1057        private final long latOffset;
1058        private final long lonOffset;
1059        private final int dateGranularity;
1060
1061        /**
1062         * Create a new record
1063         *
1064         * @param stringTable     The string table (reminder: 0 index is empty, as it is used by DenseNode to separate node tags)
1065         * @param granularity     units of nanodegrees, used to store coordinates
1066         * @param latOffset       offset value between the output coordinates and the granularity grid in units of nanodegrees
1067         * @param lonOffset       offset value between the output coordinates and the granularity grid in units of nanodegrees
1068         * @param dateGranularity Granularity of dates, normally represented in units of milliseconds since the 1970 epoch
1069         */
1070        PrimitiveBlockRecord(String[] stringTable, int granularity, long latOffset, long lonOffset,
1071                             int dateGranularity) {
1072            this.stringTable = stringTable;
1073            this.granularity = granularity;
1074            this.latOffset = latOffset;
1075            this.lonOffset = lonOffset;
1076            this.dateGranularity = dateGranularity;
1077        }
1078
1079    }
1080}