Chromium Code Reviews| OLD | NEW |
|---|---|
| 1 // Copyright 2008 the V8 project authors. All rights reserved. | 1 // Copyright 2008 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
| 4 // met: | 4 // met: |
| 5 // | 5 // |
| 6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
| (...skipping 20 matching lines...) Expand all Loading... | |
| 31 #include "v8.h" | 31 #include "v8.h" |
| 32 #include "utils.h" | 32 #include "utils.h" |
| 33 #include "ast.h" | 33 #include "ast.h" |
| 34 #include "bytecodes-re2k.h" | 34 #include "bytecodes-re2k.h" |
| 35 #include "interpreter-re2k.h" | 35 #include "interpreter-re2k.h" |
| 36 | 36 |
| 37 | 37 |
| 38 namespace v8 { namespace internal { | 38 namespace v8 { namespace internal { |
| 39 | 39 |
| 40 | 40 |
| 41 #ifdef DEBUG | |
| 42 # define BYTECODE(name) break; \ | |
| 43 case BC_##name: \ | |
| 44 if (FLAG_trace_regexp_bytecodes) { \ | |
| 45 PrintF("pc = %d, current = %d, bc = " \ | |
| 46 #name "\n", pc - code_base, current); \ | |
| 47 } | |
| 48 #else | |
| 49 # define BYTECODE(name) break; case BC_##name: | |
| 50 #endif | |
| 51 | |
| 52 | |
| 53 | |
| 41 template <typename Char> | 54 template <typename Char> |
| 42 static bool RawMatch(const byte* code_base, | 55 static bool RawMatch(const byte* code_base, |
| 43 Vector<const Char> subject, | 56 Vector<const Char> subject, |
| 44 int* registers, | 57 int* registers, |
| 45 int current) { | 58 int current) { |
| 46 const byte* pc = code_base; | 59 const byte* pc = code_base; |
| 47 int backtrack_stack[1000]; | 60 int backtrack_stack[1000]; |
| 48 int backtrack_stack_space = 1000; | 61 int backtrack_stack_space = 1000; |
| 49 int* backtrack_sp = backtrack_stack; | 62 int* backtrack_sp = backtrack_stack; |
| 50 int current_char = -1; | 63 int current_char = -1; |
| 64 #ifdef DEBUG | |
| 65 if (FLAG_trace_regexp_bytecodes) { | |
| 66 PrintF("\n\nStart bytecode interpreter\n\n"); | |
| 67 } | |
| 68 #endif | |
| 51 while (true) { | 69 while (true) { |
| 52 switch (*pc) { | 70 switch (*pc) { |
| 53 case BC_BREAK: | 71 BYTECODE(BREAK) |
| 54 UNREACHABLE(); | 72 UNREACHABLE(); |
| 55 return false; | 73 return false; |
| 56 case BC_PUSH_CP: | 74 BYTECODE(PUSH_CP) |
| 57 if (--backtrack_stack_space < 0) { | 75 if (--backtrack_stack_space < 0) { |
| 58 return false; // No match on backtrack stack overflow. | 76 return false; // No match on backtrack stack overflow. |
| 59 } | 77 } |
| 60 *backtrack_sp++ = current + Load32(pc + 1); | 78 *backtrack_sp++ = current + Load32(pc + 1); |
| 61 pc += 5; | 79 pc += 5; |
| 62 break; | 80 BYTECODE(PUSH_BT) |
| 63 case BC_PUSH_BT: | |
| 64 if (--backtrack_stack_space < 0) { | 81 if (--backtrack_stack_space < 0) { |
| 65 return false; // No match on backtrack stack overflow. | 82 return false; // No match on backtrack stack overflow. |
| 66 } | 83 } |
| 67 *backtrack_sp++ = Load32(pc + 1); | 84 *backtrack_sp++ = Load32(pc + 1); |
| 68 pc += 5; | 85 pc += 5; |
| 69 break; | 86 BYTECODE(PUSH_REGISTER) |
| 70 case BC_PUSH_REGISTER: | |
| 71 if (--backtrack_stack_space < 0) { | 87 if (--backtrack_stack_space < 0) { |
| 72 return false; // No match on backtrack stack overflow. | 88 return false; // No match on backtrack stack overflow. |
| 73 } | 89 } |
| 74 *backtrack_sp++ = registers[pc[1]]; | 90 *backtrack_sp++ = registers[pc[1]]; |
| 75 pc += 2; | 91 pc += 2; |
| 76 break; | 92 BYTECODE(SET_REGISTER) |
| 77 case BC_SET_REGISTER: | 93 registers[pc[1]] = Load32(pc + 2); |
| 94 pc += 6; | |
| 95 BYTECODE(SET_REGISTER_TO_CP) | |
| 78 registers[pc[1]] = current + Load32(pc + 2); | 96 registers[pc[1]] = current + Load32(pc + 2); |
| 79 pc += 6; | 97 pc += 6; |
| 80 break; | 98 BYTECODE(POP_CP) |
| 81 case BC_POP_CP: | |
| 82 backtrack_stack_space++; | 99 backtrack_stack_space++; |
| 83 --backtrack_sp; | 100 --backtrack_sp; |
| 84 current = *backtrack_sp; | 101 current = *backtrack_sp; |
| 85 pc += 1; | 102 pc += 1; |
| 86 break; | 103 BYTECODE(POP_BT) |
| 87 case BC_POP_BT: | |
| 88 backtrack_stack_space++; | 104 backtrack_stack_space++; |
| 89 --backtrack_sp; | 105 --backtrack_sp; |
| 90 pc = code_base + *backtrack_sp; | 106 pc = code_base + *backtrack_sp; |
| 91 break; | 107 BYTECODE(POP_REGISTER) |
| 92 case BC_POP_REGISTER: | |
| 93 backtrack_stack_space++; | 108 backtrack_stack_space++; |
| 94 --backtrack_sp; | 109 --backtrack_sp; |
| 95 registers[pc[1]] = *backtrack_sp; | 110 registers[pc[1]] = *backtrack_sp; |
| 96 pc += 2; | 111 pc += 2; |
| 97 break; | 112 BYTECODE(FAIL) |
| 98 case BC_FAIL: | |
| 99 return false; | 113 return false; |
| 100 case BC_FAIL_IF_WITHIN: | 114 BYTECODE(FAIL_IF_WITHIN) |
| 101 if (current + Load32(pc + 1) >= subject.length()) { | 115 if (current + Load32(pc + 1) >= subject.length()) { |
| 102 return false; | 116 return false; |
| 103 } | 117 } |
| 104 pc += 5; | 118 pc += 5; |
| 105 break; | 119 BYTECODE(SUCCEED) |
| 106 case BC_SUCCEED: | |
| 107 return true; | 120 return true; |
| 108 case BC_ADVANCE_CP: | 121 BYTECODE(ADVANCE_CP) |
| 109 current += Load32(pc + 1); | 122 current += Load32(pc + 1); |
| 110 pc += 5; | 123 pc += 5; |
| 111 break; | 124 BYTECODE(GOTO) |
| 112 case BC_GOTO: | |
| 113 pc = code_base + Load32(pc + 1); | 125 pc = code_base + Load32(pc + 1); |
| 114 break; | 126 BYTECODE(LOAD_CURRENT_CHAR) { |
| 115 case BC_LOAD_CURRENT_CHAR: { | |
| 116 int pos = current + Load32(pc + 1); | 127 int pos = current + Load32(pc + 1); |
| 117 if (pos >= subject.length()) { | 128 if (pos >= subject.length()) { |
| 118 current_char = -1; | 129 current_char = -1; |
| 119 } else { | 130 } else { |
| 120 current_char = subject[pos]; | 131 current_char = subject[pos]; |
| 121 } | 132 } |
| 122 pc += 5; | 133 pc += 5; |
| 123 break; | |
| 124 } | 134 } |
| 125 case BC_CHECK_CHAR: { | 135 BYTECODE(CHECK_CHAR) { |
| 126 int c = Load16(pc + 1); | 136 int c = Load16(pc + 1); |
| 127 if (c != current_char) { | 137 if (c != current_char) { |
| 128 pc = code_base + Load32(pc + 3); | 138 pc = code_base + Load32(pc + 3); |
| 129 } else { | 139 } else { |
| 130 pc += 7; | 140 pc += 7; |
| 131 } | 141 } |
| 132 break; | |
| 133 } | 142 } |
| 134 case BC_CHECK_NOT_CHAR: { | 143 BYTECODE(CHECK_NOT_CHAR) { |
| 135 int c = Load16(pc + 1); | 144 int c = Load16(pc + 1); |
| 136 if (c == current_char || current_char == -1) { | 145 if (c == current_char) { |
| 137 pc = code_base + Load32(pc + 3); | 146 pc = code_base + Load32(pc + 3); |
| 138 } else { | 147 } else { |
| 139 pc += 7; | 148 pc += 7; |
| 140 } | 149 } |
| 141 break; | |
| 142 } | 150 } |
| 143 case BC_CHECK_RANGE: { | 151 BYTECODE(CHECK_END) { |
| 152 if (current_char != -1) { | |
| 153 pc = code_base + Load32(pc + 1); | |
| 154 } else { | |
| 155 pc += 5; | |
| 156 } | |
| 157 } | |
| 158 BYTECODE(CHECK_NOT_END) { | |
| 159 if (current_char == -1) { | |
| 160 pc = code_base + Load32(pc + 1); | |
| 161 } else { | |
| 162 pc += 5; | |
| 163 } | |
| 164 } | |
| 165 BYTECODE(CHECK_RANGE) { | |
| 144 int start = Load16(pc + 1); | 166 int start = Load16(pc + 1); |
| 145 int end = Load16(pc + 3); | 167 int end = Load16(pc + 3); |
| 146 if (current_char >= start && current_char <= end) { | 168 if (current_char >= start && current_char <= end) { |
| 147 pc = code_base + Load32(pc + 5); | 169 pc = code_base + Load32(pc + 5); |
| 148 } else { | 170 } else { |
| 149 pc += 9; | 171 pc += 9; |
| 150 } | 172 } |
| 151 break; | |
| 152 } | 173 } |
| 153 case BC_CHECK_NOT_RANGE: { | 174 BYTECODE(CHECK_NOT_RANGE) { |
| 154 int start = Load16(pc + 1); | 175 int start = Load16(pc + 1); |
| 155 int end = Load16(pc + 3); | 176 int end = Load16(pc + 3); |
| 156 if (current_char < start || current_char > end || current_char == -1) { | 177 if (current_char < start || current_char > end || current_char == -1) { |
| 157 pc = code_base + Load32(pc + 5); | 178 pc = code_base + Load32(pc + 5); |
| 158 } else { | 179 } else { |
| 159 pc += 9; | 180 pc += 9; |
| 160 } | 181 } |
| 161 break; | |
| 162 } | 182 } |
| 163 case BC_CHECK_REGISTER_EQ: | 183 BYTECODE(CHECK_REGISTER_LT) |
| 164 if (registers[pc[1]] == Load16(pc + 2)) { | |
| 165 pc = code_base + Load32(pc + 4); | |
| 166 } else { | |
| 167 pc += 8; | |
| 168 } | |
| 169 break; | |
| 170 case BC_CHECK_REGISTER_LE: | |
| 171 if (registers[pc[1]] <= Load16(pc + 2)) { | |
| 172 pc = code_base + Load32(pc + 4); | |
| 173 } else { | |
| 174 pc += 8; | |
| 175 } | |
| 176 break; | |
| 177 case BC_CHECK_REGISTER_LT: | |
| 178 if (registers[pc[1]] < Load16(pc + 2)) { | 184 if (registers[pc[1]] < Load16(pc + 2)) { |
| 179 pc = code_base + Load32(pc + 4); | 185 pc = code_base + Load32(pc + 4); |
| 180 } else { | 186 } else { |
| 181 pc += 8; | 187 pc += 8; |
| 182 } | 188 } |
| 183 break; | 189 BYTECODE(CHECK_REGISTER_GE) |
| 184 case BC_CHECK_REGISTER_GE: | |
| 185 if (registers[pc[1]] >= Load16(pc + 2)) { | 190 if (registers[pc[1]] >= Load16(pc + 2)) { |
| 186 pc = code_base + Load32(pc + 4); | 191 pc = code_base + Load32(pc + 4); |
| 187 } else { | 192 } else { |
| 188 pc += 8; | 193 pc += 8; |
| 189 } | 194 } |
| 190 break; | 195 BYTECODE(CHECK_BACKREF) |
| 191 case BC_CHECK_REGISTER_GT: | 196 UNREACHABLE(); |
| 192 if (registers[pc[1]] > Load16(pc + 2)) { | 197 BYTECODE(CHECK_NOT_BACKREF) |
| 193 pc = code_base + Load32(pc + 4); | 198 UNREACHABLE(); |
| 194 } else { | 199 BYTECODE(CHECK_BITMAP) |
| 195 pc += 8; | 200 UNREACHABLE(); |
| 196 } | 201 BYTECODE(CHECK_NOT_BITMAP) |
| 197 break; | 202 UNREACHABLE(); |
|
Lasse Reichstein
2008/11/07 10:57:35
Remember a "break;" after the last BYTECODE macro
| |
| 198 case BC_CHECK_REGISTER_NE: | |
| 199 if (registers[pc[1]] != Load16(pc + 2)) { | |
| 200 pc = code_base + Load32(pc + 4); | |
| 201 } else { | |
| 202 pc += 8; | |
| 203 } | |
| 204 break; | |
| 205 case BC_CHECK_BACKREF: | |
| 206 case BC_CHECK_NOT_BACKREF: | |
| 207 case BC_CHECK_BITMAP: | |
| 208 case BC_CHECK_NOT_BITMAP: | |
| 209 default: | 203 default: |
| 210 UNREACHABLE(); | 204 UNREACHABLE(); |
| 211 break; | 205 break; |
| 212 } | 206 } |
| 213 } | 207 } |
| 214 } | 208 } |
| 215 | 209 |
| 216 | 210 |
| 217 bool Re2kInterpreter::Match(ByteArray* code_array, | 211 bool Re2kInterpreter::Match(ByteArray* code_array, |
| 218 String* subject, | 212 String* subject, |
| 219 int* registers, | 213 int* registers, |
| 220 int start_position) { | 214 int start_position) { |
| 221 const byte* code_base = code_array->GetDataStartAddress(); | 215 const byte* code_base = code_array->GetDataStartAddress(); |
| 222 StringShape shape(subject); | 216 StringShape shape(subject); |
| 223 ASSERT(subject->IsFlat(shape)); | 217 ASSERT(subject->IsFlat(shape)); |
| 224 if (shape.IsAsciiRepresentation()) { | 218 if (shape.IsAsciiRepresentation()) { |
| 225 return RawMatch(code_base, | 219 return RawMatch(code_base, |
| 226 subject->ToAsciiVector(), | 220 subject->ToAsciiVector(), |
| 227 registers, | 221 registers, |
| 228 start_position); | 222 start_position); |
| 229 } else { | 223 } else { |
| 230 return RawMatch(code_base, | 224 return RawMatch(code_base, |
| 231 subject->ToUC16Vector(), | 225 subject->ToUC16Vector(), |
| 232 registers, | 226 registers, |
| 233 start_position); | 227 start_position); |
| 234 } | 228 } |
| 235 } | 229 } |
| 236 | 230 |
| 237 } } // namespace v8::internal | 231 } } // namespace v8::internal |
| OLD | NEW |