master_lexer.cc 18.8 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// Copyright (C) 2012  Internet Systems Consortium, Inc. ("ISC")
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided that the above
// copyright notice and this permission notice appear in all copies.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

15 16
#include <exceptions/exceptions.h>

17
#include <dns/master_lexer.h>
18
#include <dns/master_lexer_inputsource.h>
19
#include <dns/master_lexer_state.h>
20

21
#include <boost/shared_ptr.hpp>
22
#include <boost/lexical_cast.hpp>
23

24
#include <bitset>
25 26
#include <cassert>
#include <string>
27 28 29 30 31
#include <vector>

namespace isc {
namespace dns {

32 33
namespace {
typedef boost::shared_ptr<master_lexer_internal::InputSource> InputSourcePtr;
34
} // end unnamed namespace
35 36
using namespace master_lexer_internal;

37

38
struct MasterLexer::MasterLexerImpl {
39
    MasterLexerImpl() : source_(NULL), token_(MasterToken::NOT_STARTED),
40
                        paren_count_(0), last_was_eol_(true),
41 42 43
                        has_previous_(false),
                        previous_paren_count_(0),
                        previous_was_eol_(false)
44 45 46 47 48 49 50 51 52 53
    {
        separators_.set('\r');
        separators_.set('\n');
        separators_.set(' ');
        separators_.set('\t');
        separators_.set('(');
        separators_.set(')');
        esc_separators_.set('\r');
        esc_separators_.set('\n');
    }
54

55 56 57 58
    // A helper method to skip possible comments toward the end of EOL or EOF.
    // commonly used by state classes.  It returns the corresponding "end-of"
    // character in case it's a comment; otherwise it simply returns the
    // current character.
59 60
    int skipComment(int c, bool escaped = false) {
        if (c == ';' && !escaped) {
61 62 63 64 65 66 67 68 69
            while (true) {
                c = source_->getChar();
                if (c == '\n' || c == InputSource::END_OF_STREAM) {
                    return (c);
                }
            }
        }
        return (c);
    }
70

71
    bool isTokenEnd(int c, bool escaped) {
72
        // Special case of EOF (end of stream); this is not in the bitmaps
73 74 75
        if (c == InputSource::END_OF_STREAM) {
            return (true);
        }
76 77 78
        // In this implementation we only ensure the behavior for unsigned
        // range of characters, so we restrict the range of the values up to
        // 0x7f = 127
79 80 81 82
        return (escaped ? esc_separators_.test(c & 0x7f) :
                separators_.test(c & 0x7f));
    }

83
    std::vector<InputSourcePtr> sources_;
84
    InputSource* source_;       // current source (NULL if sources_ is empty)
85
    MasterToken token_;         // currently recognized token (set by a state)
86
    std::vector<char> data_;    // placeholder for string data
87 88 89 90 91

    // These are used in states, and defined here only as a placeholder.
    // The main lexer class does not need these members.
    size_t paren_count_;        // nest count of the parentheses
    bool last_was_eol_; // whether the lexer just passed an end-of-line
92 93 94 95

    // Bitmaps that gives whether a given (positive) character should be
    // considered a separator of a string/number token.  The esc_ version
    // is a subset of the other, excluding characters that can be ignored
96
    // if escaped by a backslash.  See isTokenEnd() for the bitmap size.
97 98
    std::bitset<128> separators_;
    std::bitset<128> esc_separators_;
99 100 101 102 103

    // These are to allow restoring state before previous token.
    bool has_previous_;
    size_t previous_paren_count_;
    bool previous_was_eol_;
104 105 106 107 108 109 110 111 112
};

MasterLexer::MasterLexer() : impl_(new MasterLexerImpl) {
}

MasterLexer::~MasterLexer() {
    delete impl_;
}

113 114
bool
MasterLexer::pushSource(const char* filename, std::string* error) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
115
    if (filename == NULL) {
116 117
        isc_throw(InvalidParameter,
                  "NULL filename for MasterLexer::pushSource");
JINMEI Tatuya's avatar
JINMEI Tatuya committed
118
    }
119 120 121 122 123 124 125 126 127
    try {
        impl_->sources_.push_back(InputSourcePtr(new InputSource(filename)));
    } catch (const InputSource::OpenError& ex) {
        if (error != NULL) {
            *error = ex.what();
        }
        return (false);
    }

128
    impl_->source_ = impl_->sources_.back().get();
129
    impl_->has_previous_ = false;
130
    return (true);
131 132
}

133
void
134
MasterLexer::pushSource(std::istream& input) {
135
    impl_->sources_.push_back(InputSourcePtr(new InputSource(input)));
136
    impl_->source_ = impl_->sources_.back().get();
137
    impl_->has_previous_ = false;
138 139
}

140
void
141
MasterLexer::popSource() {
142
    if (impl_->sources_.empty()) {
143 144
        isc_throw(InvalidOperation,
                  "MasterLexer::popSource on an empty source");
145 146
    }
    impl_->sources_.pop_back();
147 148
    impl_->source_ = impl_->sources_.empty() ? NULL :
        impl_->sources_.back().get();
149
    impl_->has_previous_ = false;
150 151
}

152 153 154 155 156
size_t
MasterLexer::getSourceCount() const {
    return (impl_->sources_.size());
}

157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
std::string
MasterLexer::getSourceName() const {
    if (impl_->sources_.empty()) {
        return (std::string());
    }
    return (impl_->sources_.back()->getName());
}

size_t
MasterLexer::getSourceLine() const {
    if (impl_->sources_.empty()) {
        return (0);
    }
    return (impl_->sources_.back()->getCurrentLine());
}
172

173
const MasterToken&
174
MasterLexer::getNextToken(Options options) {
175
    if (impl_->source_ == NULL) {
176 177
        isc_throw(isc::InvalidOperation, "No source to read tokens from");
    }
178
    // Store the current state so we can restore it in ungetToken
179 180 181 182 183 184
    impl_->previous_paren_count_ = impl_->paren_count_;
    impl_->previous_was_eol_ = impl_->last_was_eol_;
    impl_->source_->mark();
    impl_->has_previous_ = true;
    // Reset the token now. This is to check a token was actually produced.
    // This is debugging aid.
185
    impl_->token_ = MasterToken(MasterToken::NO_TOKEN_PRODUCED);
186
    // And get the token
187 188

    // This actually handles EOF internally too.
189
    const State* state = State::start(*this, options);
190 191
    if (state != NULL) {
        state->handle(*this);
192
    }
193 194
    // Make sure a token was produced. Since this Can Not Happen, we assert
    // here instead of throwing.
195 196
    assert(impl_->token_.getType() != MasterToken::ERROR ||
           impl_->token_.getErrorCode() != MasterToken::NO_TOKEN_PRODUCED);
197
    return (impl_->token_);
198 199
}

200 201 202 203 204 205 206 207 208 209 210
namespace {
inline MasterLexer::Options
optionsForTokenType(MasterToken::Type expect) {
    switch (expect) {
    case MasterToken::STRING:
        return (MasterLexer::NONE);
    case MasterToken::QSTRING:
        return (MasterLexer::QSTRING);
    case MasterToken::NUMBER:
        return (MasterLexer::NUMBER);
    default:
211 212
        isc_throw(InvalidParameter,
                  "expected type for getNextToken not supported: " << expect);
213
    }
214 215
}
}
216

217 218
const MasterToken&
MasterLexer::getNextToken(MasterToken::Type expect, bool eol_ok) {
219 220
    // Get the next token, specifying an appropriate option corresponding to
    // the expected type.  The result should be set in impl_->token_.
221
    getNextToken(optionsForTokenType(expect));
222

223
    if (impl_->token_.getType() == MasterToken::ERROR) {
224 225 226
        if (impl_->token_.getErrorCode() == MasterToken::NUMBER_OUT_OF_RANGE) {
            ungetToken();
        }
227 228 229
        throw LexerError(__FILE__, __LINE__, impl_->token_);
    }

230 231 232 233 234 235 236 237 238 239 240 241
    const bool is_eol_like =
        (impl_->token_.getType() == MasterToken::END_OF_LINE ||
         impl_->token_.getType() == MasterToken::END_OF_FILE);
    if (eol_ok && is_eol_like) {
        return (impl_->token_);
    }
    if (impl_->token_.getType() == MasterToken::STRING &&
        expect == MasterToken::QSTRING) {
        return (impl_->token_);
    }
    if (impl_->token_.getType() != expect) {
        ungetToken();
242 243 244 245 246
        if (is_eol_like) {
            throw LexerError(__FILE__, __LINE__,
                             MasterToken(MasterToken::UNEXPECTED_END));
        }
        assert(expect == MasterToken::NUMBER);
247
        throw LexerError(__FILE__, __LINE__,
248
                         MasterToken(MasterToken::BAD_NUMBER));
249 250 251 252 253
    }

    return (impl_->token_);
}

254 255
void
MasterLexer::ungetToken() {
256 257 258 259 260 261 262 263
    if (impl_->has_previous_) {
        impl_->has_previous_ = false;
        impl_->source_->ungetAll();
        impl_->last_was_eol_ = impl_->previous_was_eol_;
        impl_->paren_count_ = impl_->previous_paren_count_;
    } else {
        isc_throw(isc::InvalidOperation, "No token to unget ready");
    }
264 265
}

266 267 268 269 270
namespace {
const char* const error_text[] = {
    "lexer not started",        // NOT_STARTED
    "unbalanced parentheses",   // UNBALANCED_PAREN
    "unexpected end of input",  // UNEXPECTED_END
271
    "unbalanced quotes",        // UNBALANCED_QUOTES
272
    "no token produced",        // NO_TOKEN_PRODUCED
273 274
    "number out of range",      // NUMBER_OUT_OF_RANGE
    "not a valid number"        // BAD_NUMBER
275 276
};
const size_t error_text_max_count = sizeof(error_text) / sizeof(error_text[0]);
277
} // end unnamed namespace
278 279

std::string
280
MasterToken::getErrorText() const {
281 282
    if (type_ != ERROR) {
        isc_throw(InvalidOperation,
283
                  "MasterToken::getErrorText() for non error type");
284 285 286 287 288 289 290
    }

    // The class integrity ensures the following:
    assert(val_.error_code_ < error_text_max_count);
    return (error_text[val_.error_code_]);
}

291
namespace master_lexer_internal {
292 293
// Below we implement state classes for state transitions of MasterLexer.
// Note that these need to be defined here so that they can refer to
294
// the details of MasterLexerImpl.
295

296
bool
297
State::wasLastEOL(const MasterLexer& lexer) const {
298 299 300
    return (lexer.impl_->last_was_eol_);
}

301
const MasterToken&
302
State::getToken(const MasterLexer& lexer) const {
303 304 305
    return (lexer.impl_->token_);
}

306 307 308 309 310
size_t
State::getParenCount(const MasterLexer& lexer) const {
    return (lexer.impl_->paren_count_);
}

311
namespace {
312 313 314
class CRLF : public State {
public:
    CRLF() {}
315
    virtual ~CRLF() {}          // see the base class for the destructor
316
    virtual void handle(MasterLexer& lexer) const {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
317 318 319 320 321 322 323 324 325 326 327 328 329 330
        // We've just seen '\r'.  If this is part of a sequence of '\r\n',
        // we combine them as a single END-OF-LINE.  Otherwise we treat the
        // single '\r' as an EOL and continue tokeniziation from the character
        // immediately after '\r'.  One tricky case is that there's a comment
        // between '\r' and '\n'.  This implementation combines these
        // characters and treats them as a single EOL (the behavior derived
        // from BIND 9).  Technically this may not be correct, but in practice
        // the caller wouldn't distinguish this case from the case it has
        // two EOLs, so we simplify the process.
        const int c = getLexerImpl(lexer)->skipComment(
            getLexerImpl(lexer)->source_->getChar());
        if (c != '\n') {
            getLexerImpl(lexer)->source_->ungetChar();
        }
331
        getLexerImpl(lexer)->token_ = MasterToken(MasterToken::END_OF_LINE);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
332
        getLexerImpl(lexer)->last_was_eol_ = true;
333 334 335
    }
};

336 337 338
class String : public State {
public:
    String() {}
339
    virtual ~String() {}      // see the base class for the destructor
340
    virtual void handle(MasterLexer& lexer) const;
341 342
};

343 344 345 346
class QString : public State {
public:
    QString() {}
    virtual ~QString() {}      // see the base class for the destructor
347
    virtual void handle(MasterLexer& lexer) const;
348 349
};

Jelte Jansen's avatar
Jelte Jansen committed
350 351 352 353
class Number : public State {
public:
    Number() {}
    virtual ~Number() {}
354
    virtual void handle(MasterLexer& lexer) const;
Jelte Jansen's avatar
Jelte Jansen committed
355 356
};

357 358 359 360 361
// We use a common instance of a each state in a singleton-like way to save
// construction overhead.  They are not singletons in its strict sense as
// we don't prohibit direct construction of these objects.  But that doesn't
// matter much anyway, because the definitions are completely hidden within
// this file.
JINMEI Tatuya's avatar
JINMEI Tatuya committed
362
const CRLF CRLF_STATE;
363
const String STRING_STATE;
364
const QString QSTRING_STATE;
Jelte Jansen's avatar
Jelte Jansen committed
365
const Number NUMBER_STATE;
366
} // end unnamed namespace
367 368

const State&
369 370 371 372 373
State::getInstance(ID state_id) {
    switch (state_id) {
    case CRLF:
        return (CRLF_STATE);
    case String:
374
        return (STRING_STATE);
375 376
    case QString:
        return (QSTRING_STATE);
Jelte Jansen's avatar
Jelte Jansen committed
377 378
    case Number:
        return (NUMBER_STATE);
379
    }
380 381 382 383 384 385

    // This is a bug of the caller, and this method is only expected to be
    // used by tests, so we just forcefully make it fail by asserting the
    // condition.
    assert(false);
    return (STRING_STATE); // a dummy return, to silence some compilers.
386 387
}

JINMEI Tatuya's avatar
JINMEI Tatuya committed
388
const State*
389 390 391 392
State::start(MasterLexer& lexer, MasterLexer::Options options) {
    // define some shortcuts
    MasterLexer::MasterLexerImpl& lexerimpl = *lexer.impl_;
    size_t& paren_count = lexerimpl.paren_count_;
393

394 395 396
    // Note: the if-else in the loop is getting complicated.  When we complete
    // #2374, revisit the organization to see if we need a fundamental
    // refactoring.
JINMEI Tatuya's avatar
JINMEI Tatuya committed
397
    while (true) {
398
        const int c = lexerimpl.skipComment(lexerimpl.source_->getChar());
399
        if (c == InputSource::END_OF_STREAM) {
400
            lexerimpl.last_was_eol_ = false;
401
            if (paren_count != 0) {
402
                lexerimpl.token_ = MasterToken(MasterToken::UNBALANCED_PAREN);
403 404 405
                paren_count = 0; // reset to 0; this helps in lenient mode.
                return (NULL);
            }
406
            lexerimpl.token_ = MasterToken(MasterToken::END_OF_FILE);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
407 408
            return (NULL);
        } else if (c == ' ' || c == '\t') {
409
            // If requested and we are not in (), recognize the initial space.
410
            if (lexerimpl.last_was_eol_ && paren_count == 0 &&
JINMEI Tatuya's avatar
JINMEI Tatuya committed
411
                (options & MasterLexer::INITIAL_WS) != 0) {
412
                lexerimpl.last_was_eol_ = false;
413
                lexerimpl.token_ = MasterToken(MasterToken::INITIAL_WS);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
414 415 416
                return (NULL);
            }
        } else if (c == '\n') {
417
            lexerimpl.last_was_eol_ = true;
418
            if (paren_count == 0) { // we don't recognize EOL if we are in ()
419
                lexerimpl.token_ = MasterToken(MasterToken::END_OF_LINE);
420 421
                return (NULL);
            }
JINMEI Tatuya's avatar
JINMEI Tatuya committed
422
        } else if (c == '\r') {
423
            if (paren_count == 0) { // check if we are in () (see above)
JINMEI Tatuya's avatar
JINMEI Tatuya committed
424 425
                return (&CRLF_STATE);
            }
426 427 428
        } else if (c == '"' && (options & MasterLexer::QSTRING) != 0) {
            lexerimpl.last_was_eol_ = false;
            return (&QSTRING_STATE);
429
        } else if (c == '(') {
430
            lexerimpl.last_was_eol_ = false;
431
            ++paren_count;
432
        } else if (c == ')') {
433
            lexerimpl.last_was_eol_ = false;
434
            if (paren_count == 0) {
435
                lexerimpl.token_ = MasterToken(MasterToken::UNBALANCED_PAREN);
436 437
                return (NULL);
            }
438
            --paren_count;
Jelte Jansen's avatar
Jelte Jansen committed
439
        } else if ((options & MasterLexer::NUMBER) != 0 &&isdigit(c)) {
Jelte Jansen's avatar
Jelte Jansen committed
440 441 442 443
            lexerimpl.last_was_eol_ = false;
            // this character will be handled in the number state
            lexerimpl.source_->ungetChar();
            return (&NUMBER_STATE);
444
        } else {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
445
            // this character will be handled in the string state
446
            lexerimpl.source_->ungetChar();
JINMEI Tatuya's avatar
JINMEI Tatuya committed
447
            lexerimpl.last_was_eol_ = false;
448
            return (&STRING_STATE);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
449
        }
450
        // no code should be here; we just continue the loop.
JINMEI Tatuya's avatar
JINMEI Tatuya committed
451 452
    }
}
453

454
void
455 456 457 458
String::handle(MasterLexer& lexer) const {
    std::vector<char>& data = getLexerImpl(lexer)->data_;
    data.clear();

459
    bool escaped = false;
460
    while (true) {
461 462
        const int c = getLexerImpl(lexer)->skipComment(
            getLexerImpl(lexer)->source_->getChar(), escaped);
463

464
        if (getLexerImpl(lexer)->isTokenEnd(c, escaped)) {
465
            getLexerImpl(lexer)->source_->ungetChar();
466 467 468
            // make sure it nul-terminated as a c-str (excluded from token
            // data).
            data.push_back('\0');
469
            getLexerImpl(lexer)->token_ =
470
                MasterToken(&data.at(0), data.size() - 1);
471
            return;
472
        }
473
        escaped = (c == '\\' && !escaped);
474 475 476 477
        data.push_back(c);
    }
}

478
void
479
QString::handle(MasterLexer& lexer) const {
480
    MasterToken& token = getLexerImpl(lexer)->token_;
481 482 483 484 485 486 487
    std::vector<char>& data = getLexerImpl(lexer)->data_;
    data.clear();

    bool escaped = false;
    while (true) {
        const int c = getLexerImpl(lexer)->source_->getChar();
        if (c == InputSource::END_OF_STREAM) {
488
            token = MasterToken(MasterToken::UNEXPECTED_END);
489
            return;
490 491 492 493 494 495 496
        } else if (c == '"') {
            if (escaped) {
                // found escaped '"'. overwrite the preceding backslash.
                assert(!data.empty());
                escaped = false;
                data.back() = '"';
            } else {
497 498 499 500
                // make sure it nul-terminated as a c-str (excluded from token
                // data).  This also simplifies the case of an empty string.
                data.push_back('\0');
                token = MasterToken(&data.at(0), data.size() - 1, true);
501
                return;
502 503 504
            }
        } else if (c == '\n' && !escaped) {
            getLexerImpl(lexer)->source_->ungetChar();
505
            token = MasterToken(MasterToken::UNBALANCED_QUOTES);
506
            return;
507 508 509 510 511 512 513
        } else {
            escaped = (c == '\\' && !escaped);
            data.push_back(c);
        }
    }
}

514
void
Jelte Jansen's avatar
Jelte Jansen committed
515
Number::handle(MasterLexer& lexer) const {
516
    MasterToken& token = getLexerImpl(lexer)->token_;
Jelte Jansen's avatar
Jelte Jansen committed
517 518 519 520 521 522 523 524 525

    // It may yet turn out to be a string, so we first
    // collect all the data
    bool digits_only = true;
    std::vector<char>& data = getLexerImpl(lexer)->data_;
    data.clear();
    bool escaped = false;

    while (true) {
526 527
        const int c = getLexerImpl(lexer)->skipComment(
            getLexerImpl(lexer)->source_->getChar(), escaped);
Jelte Jansen's avatar
Jelte Jansen committed
528 529
        if (getLexerImpl(lexer)->isTokenEnd(c, escaped)) {
            getLexerImpl(lexer)->source_->ungetChar();
530 531 532
            // We need to close the string whether it's digits-only (for
            // lexical_cast) or not (see String::handle()).
            data.push_back('\0');
Jelte Jansen's avatar
Jelte Jansen committed
533
            if (digits_only) {
534 535
                try {
                    const uint32_t number32 =
Jelte Jansen's avatar
Jelte Jansen committed
536
                        boost::lexical_cast<uint32_t, const char*>(&data[0]);
537
                    token = MasterToken(number32);
538 539 540
                } catch (const boost::bad_lexical_cast&) {
                    // Since we already know we have only digits,
                    // range should be the only possible problem.
541
                    token = MasterToken(MasterToken::NUMBER_OUT_OF_RANGE);
542
                }
Jelte Jansen's avatar
Jelte Jansen committed
543
            } else {
544
                token = MasterToken(&data.at(0), data.size() - 1);
Jelte Jansen's avatar
Jelte Jansen committed
545
            }
546
            return;
Jelte Jansen's avatar
Jelte Jansen committed
547 548 549 550 551 552 553 554 555
        }
        if (!isdigit(c)) {
            digits_only = false;
        }
        escaped = (c == '\\' && !escaped);
        data.push_back(c);
    }
}

556 557
} // namespace master_lexer_internal

558 559
} // end of namespace dns
} // end of namespace isc