1 /*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef LIBTEXTCLASSIFIER_UTILS_GRAMMAR_PARSING_CHART_H_
18 #define LIBTEXTCLASSIFIER_UTILS_GRAMMAR_PARSING_CHART_H_
19
20 #include <array>
21
22 #include "annotator/types.h"
23 #include "utils/grammar/parsing/derivation.h"
24 #include "utils/grammar/parsing/parse-tree.h"
25
26 namespace libtextclassifier3::grammar {
27
28 // Chart is a hashtable container for use with a CYK style parser.
29 // The hashtable contains all matches, indexed by their end positions.
30 template <int NumBuckets = 1 << 8>
31 class Chart {
32 public:
Chart()33 explicit Chart() { std::fill(chart_.begin(), chart_.end(), nullptr); }
34
35 // Iterator that allows iterating through recorded matches that end at a given
36 // match offset.
37 class Iterator {
38 public:
Iterator(const int match_offset,const ParseTree * value)39 explicit Iterator(const int match_offset, const ParseTree* value)
40 : match_offset_(match_offset), value_(value) {}
41
Done()42 bool Done() const {
43 return value_ == nullptr ||
44 (value_->codepoint_span.second < match_offset_);
45 }
Item()46 const ParseTree* Item() const { return value_; }
Next()47 void Next() {
48 TC3_DCHECK(!Done());
49 value_ = value_->next;
50 }
51
52 private:
53 const int match_offset_;
54 const ParseTree* value_;
55 };
56
57 // Returns whether the chart contains a match for a given nonterminal.
58 bool HasMatch(const Nonterm nonterm, const CodepointSpan& span) const;
59
60 // Adds a match to the chart.
Add(ParseTree * item)61 void Add(ParseTree* item) {
62 item->next = chart_[item->codepoint_span.second & kChartHashTableBitmask];
63 chart_[item->codepoint_span.second & kChartHashTableBitmask] = item;
64 }
65
66 // Records a derivation of a root rule.
AddDerivation(const Derivation & derivation)67 void AddDerivation(const Derivation& derivation) {
68 root_derivations_.push_back(derivation);
69 }
70
71 // Returns an iterator through all matches ending at `match_offset`.
MatchesEndingAt(const int match_offset)72 Iterator MatchesEndingAt(const int match_offset) const {
73 const ParseTree* value = chart_[match_offset & kChartHashTableBitmask];
74 // The chain of items is in decreasing `end` order.
75 // Find the ones that have prev->end == item->begin.
76 while (value != nullptr && (value->codepoint_span.second > match_offset)) {
77 value = value->next;
78 }
79 return Iterator(match_offset, value);
80 }
81
derivations()82 const std::vector<Derivation> derivations() const {
83 return root_derivations_;
84 }
85
86 private:
87 static constexpr int kChartHashTableBitmask = NumBuckets - 1;
88 std::array<ParseTree*, NumBuckets> chart_;
89 std::vector<Derivation> root_derivations_;
90 };
91
92 template <int NumBuckets>
HasMatch(const Nonterm nonterm,const CodepointSpan & span)93 bool Chart<NumBuckets>::HasMatch(const Nonterm nonterm,
94 const CodepointSpan& span) const {
95 // Lookup by end.
96 for (Chart<NumBuckets>::Iterator it = MatchesEndingAt(span.second);
97 !it.Done(); it.Next()) {
98 if (it.Item()->lhs == nonterm &&
99 it.Item()->codepoint_span.first == span.first) {
100 return true;
101 }
102 }
103 return false;
104 }
105
106 } // namespace libtextclassifier3::grammar
107
108 #endif // LIBTEXTCLASSIFIER_UTILS_GRAMMAR_PARSING_CHART_H_
109