This is an automated email from the ASF dual-hosted git repository. matthiasblaesing pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/netbeans.git
The following commit(s) were added to refs/heads/master by this push: new 6a5ba4b Improve handling of recursive JS structures new c94c756 Merge pull request #3696 from matthiasblaesing/3669_recursive_js_models 6a5ba4b is described below commit 6a5ba4bfa24b870f82f2bbafaae176e98d2d18c4 Author: Matthias Bläsing <mblaes...@doppel-helix.eu> AuthorDate: Fri Mar 4 23:01:12 2022 +0100 Improve handling of recursive JS structures JS structures, that reference themselves can cause unlimited recursion in several places. In this changeset the JsIndexer and OccurrencesSupport are modified, so that recursive structures can be scanned without causing a StackOverflowError. Closes: #3669 --- .../javascript2/editor/index/JsIndexer.java | 35 +++++++-- .../editor/navigation/OccurrencesSupport.java | 41 ++++++---- .../testfiles/indexer/SelfreferencingFunction.js | 25 ++++++ .../indexer/SelfreferencingFunction.js.indexed | 74 ++++++++++++++++++ .../testfiles/indexer/SelfreferencingObject.js | 24 ++++++ .../indexer/SelfreferencingObject.js.indexed | 45 +++++++++++ .../modules/javascript2/editor/JsTestBase.java | 11 ++- .../editor/index/RecursiveStructuresTest.java | 88 ++++++++++++++++++++++ 8 files changed, 319 insertions(+), 24 deletions(-) diff --git a/webcommon/javascript2.editor/src/org/netbeans/modules/javascript2/editor/index/JsIndexer.java b/webcommon/javascript2.editor/src/org/netbeans/modules/javascript2/editor/index/JsIndexer.java index 3d4332e..d75680e 100644 --- a/webcommon/javascript2.editor/src/org/netbeans/modules/javascript2/editor/index/JsIndexer.java +++ b/webcommon/javascript2.editor/src/org/netbeans/modules/javascript2/editor/index/JsIndexer.java @@ -22,6 +22,7 @@ import org.netbeans.modules.javascript2.model.api.IndexedElement; import java.io.IOException; import java.net.URL; import java.util.Collection; +import java.util.IdentityHashMap; import java.util.Iterator; import java.util.LinkedList; import java.util.logging.Level; @@ -96,14 +97,16 @@ public class JsIndexer extends EmbeddingIndexer { JsObject globalObject = model.getGlobalObject(); for (JsObject object : globalObject.getProperties().values()) { if (object.getParent() != null) { - storeObject(object, object.getName(), support, indexable); + IdentityHashMap<JsObject,Integer> visited = new IdentityHashMap<>(); + storeObject(object, object.getName(), support, indexable, visited); } } IndexDocument document = support.createDocument(indexable); for (JsObject object : globalObject.getProperties().values()) { if (object.getParent() != null) { - storeUsages(object, object.getName(), document); + IdentityHashMap<JsObject,Integer> visited = new IdentityHashMap<>(); + storeUsages(object, object.getName(), document, visited); } } support.addDocument(document); @@ -214,7 +217,15 @@ public class JsIndexer extends EmbeddingIndexer { return elementDocument; } - private void storeObject(JsObject object, String fqn, IndexingSupport support, Indexable indexable) { + private void storeObject(JsObject object, String fqn, IndexingSupport support, Indexable indexable, IdentityHashMap<JsObject,Integer> visited) { + // @todo: This prevents unlimited recursion when self referencing strucures + // are scanned. It is necessary to rework the index users so that + // this is not necessary + if(visited.containsKey(object)) { + return; + } + IdentityHashMap<JsObject,Integer> childVisited = new IdentityHashMap<>(visited); + childVisited.compute(object, (k, v) -> v == null ? 1 : v+1); if (!isInvisibleFunction(object) && object != null && object.getName() != null) { if (object.isDeclared() || ModelUtils.PROTOTYPE.equals(object.getName())) { // if it's delcared, then store in the index as new document. @@ -226,7 +237,7 @@ public class JsIndexer extends EmbeddingIndexer { // there can be declared it's properties or methods for (JsObject property : object.getProperties().values()) { if (!(property instanceof JsReference && !((JsReference)property).getOriginal().isAnonymous())) { - storeObject(property, fqn + '.' + property.getName(), support, indexable); + storeObject(property, fqn + '.' + property.getName(), support, indexable, childVisited); } else { IndexDocument document = createDocumentForReference((JsReference)property, fqn + '.' + property.getName(), support, indexable); //// IndexDocument document = IndexedElement.createDocument(property, fqn + '.' + property.getName(), support, indexable); @@ -236,7 +247,7 @@ public class JsIndexer extends EmbeddingIndexer { if (object instanceof JsFunction) { // store parameters for (JsObject parameter : ((JsFunction)object).getParameters()) { - storeObject(parameter, fqn + '.' + parameter.getName(), support, indexable); + storeObject(parameter, fqn + '.' + parameter.getName(), support, indexable, childVisited); } } } @@ -286,7 +297,15 @@ public class JsIndexer extends EmbeddingIndexer { return result.toString(); } - private void storeUsages(JsObject object, String name, IndexDocument document) { + private void storeUsages(JsObject object, String name, IndexDocument document, IdentityHashMap<JsObject,Integer> visited) { + // @todo: This prevents unlimited recursion when self referencing strucures + // are scanned. It is necessary to rework the index users so that + // this is not necessary + if(visited.containsKey(object)) { + return; + } + IdentityHashMap<JsObject,Integer> childVisited = new IdentityHashMap<>(visited); + childVisited.compute(object, (k, v) -> v == null ? 1 : v+1); StringBuilder sb = new StringBuilder(); sb.append(object.getName()); for (JsObject property : object.getProperties().values()) { @@ -304,12 +323,12 @@ public class JsIndexer extends EmbeddingIndexer { if (object instanceof JsFunction) { // store parameters for (JsObject parameter : ((JsFunction) object).getParameters()) { - storeUsages(parameter, parameter.getName(), document); + storeUsages(parameter, parameter.getName(), document, childVisited); } } for (JsObject property : object.getProperties().values()) { if (storeUsage(property) && (!(property instanceof JsReference && !((JsReference)property).getOriginal().isAnonymous()))) { - storeUsages(property, property.getName(), document); + storeUsages(property, property.getName(), document, childVisited); } } } diff --git a/webcommon/javascript2.editor/src/org/netbeans/modules/javascript2/editor/navigation/OccurrencesSupport.java b/webcommon/javascript2.editor/src/org/netbeans/modules/javascript2/editor/navigation/OccurrencesSupport.java index ca15ff5..6b2d4ac 100644 --- a/webcommon/javascript2.editor/src/org/netbeans/modules/javascript2/editor/navigation/OccurrencesSupport.java +++ b/webcommon/javascript2.editor/src/org/netbeans/modules/javascript2/editor/navigation/OccurrencesSupport.java @@ -18,6 +18,7 @@ */ package org.netbeans.modules.javascript2.editor.navigation; +import java.util.IdentityHashMap; import java.util.logging.Level; import java.util.logging.Logger; import org.netbeans.modules.javascript2.model.api.JsElement; @@ -35,27 +36,34 @@ import org.netbeans.modules.javascript2.model.api.Occurrence; public class OccurrencesSupport { private static final Logger LOGGER = Logger.getLogger(OccurrencesSupport.class.getName()); - + private final Model model; public OccurrencesSupport(Model model) { this.model = model; } - + public Occurrence getOccurrence(int offset) { Occurrence result; long start = System.currentTimeMillis(); JsObject object = model.getGlobalObject(); - result = findOccurrence(object, offset); + IdentityHashMap<JsObject,Void> scannedElements = new IdentityHashMap<>(); + result = findOccurrence(object, offset, scannedElements); + scannedElements.clear(); if (result == null) { - result = findDeclaration(object, offset); + result = findDeclaration(object, offset, scannedElements); } long end = System.currentTimeMillis(); LOGGER.log(Level.FINE, "Computing getOccurences({0}) took {1}ms. Returns {2}", new Object[]{offset, end - start, result}); return result; } - - private Occurrence findOccurrence(JsObject object, int offset) { + + private Occurrence findOccurrence(JsObject object, int offset, IdentityHashMap<JsObject,Void> scannedElements) { + if(scannedElements.containsKey(object)) { + return null; + } else { + scannedElements.put(object, null); + } Occurrence result = null; JsElement.Kind kind = object.getJSKind(); for(Occurrence occurrence: object.getOccurrences()) { @@ -65,10 +73,10 @@ public class OccurrencesSupport { } if (kind.isFunction() || kind == JsElement.Kind.CATCH_BLOCK) { for(JsObject param : ((JsFunction)object).getParameters()) { - result = findOccurrence(param, offset); + result = findOccurrence(param, offset, scannedElements); if (result != null) { break; - } + } } if (result != null) { return result; @@ -77,7 +85,7 @@ public class OccurrencesSupport { if (!(object instanceof JsReference && ModelUtils.isDescendant(object, ((JsReference)object).getOriginal()))) { for(JsObject property: object.getProperties().values()) { if (!(property instanceof JsReference && !((JsReference)property).getOriginal().isAnonymous())) { - result = findOccurrence(property, offset); + result = findOccurrence(property, offset, scannedElements); if (result != null) { break; } @@ -92,8 +100,13 @@ public class OccurrencesSupport { } return result; } - - private Occurrence findDeclaration (JsObject object, int offset) { + + private Occurrence findDeclaration (JsObject object, int offset, IdentityHashMap<JsObject,Void> scannedElements) { + if(scannedElements.containsKey(object)) { + return null; + } else { + scannedElements.put(object, null); + } Occurrence result = null; JsElement.Kind kind = object.getJSKind(); if (kind != JsElement.Kind.ANONYMOUS_OBJECT && kind != JsElement.Kind.WITH_OBJECT @@ -105,9 +118,9 @@ public class OccurrencesSupport { propertyName = propertyName.substring(propertyName.lastIndexOf(' ') + 1); JsObject property = object.getParent().getProperty(propertyName); if (property != null) { - return new Occurrence(property.getDeclarationName().getOffsetRange(), property); + return new Occurrence(property.getDeclarationName().getOffsetRange(), property); } - } + } result = new Occurrence(object.getDeclarationName().getOffsetRange(), object); } @@ -122,7 +135,7 @@ public class OccurrencesSupport { if (result == null) { for(JsObject property: object.getProperties().values()) { if (!(property instanceof JsReference)) { - result = findDeclaration(property, offset); + result = findDeclaration(property, offset, scannedElements); if (result != null) { break; } diff --git a/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingFunction.js b/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingFunction.js new file mode 100644 index 0000000..e80c75d --- /dev/null +++ b/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingFunction.js @@ -0,0 +1,25 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +function mod(actions) { + return actions.map((action) => { + action = { action }; + return action; + }); +}; \ No newline at end of file diff --git a/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingFunction.js.indexed b/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingFunction.js.indexed new file mode 100644 index 0000000..88f9cf1 --- /dev/null +++ b/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingFunction.js.indexed @@ -0,0 +1,74 @@ + + +Document 0 +Searchable Keys: + bn : SelfreferencingFunctionmod#=>#21 + bni : selfreferencingfunctionmod#=>#21 + fqn : mod.SelfreferencingFunctionmod#=>#21A + offset : 870 + +Not Searchable Keys: + assign : + flag : 4289 + param : action: + return : + + +Document 1 +Searchable Keys: + bn : action + bni : action + fqn : mod.SelfreferencingFunctionmod#=>#21.actionP + offset : 871 + +Not Searchable Keys: + assign : + flag : 131138 + + +Document 2 +Searchable Keys: + bn : actions + bni : actions + fqn : mod.actionsP + offset : 836 + +Not Searchable Keys: + assign : + flag : 131138 + + +Document 3 +Searchable Keys: + bn : mod + bni : mod + fqn : modO + offset : 832 + +Not Searchable Keys: + assign : + flag : 8258 + param : actions: + return : 0|,928,@pro;actions@call;map + + +Document 4 +Searchable Keys: + bn : param + bni : param + fqn : mod.actions.map.paramP + offset : 0 + +Not Searchable Keys: + assign : + flag : 131138 + + +Document 5 +Searchable Keys: + usage : actions:map#F + usage : map + usage : mod + usage : param + +Not Searchable Keys: diff --git a/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingObject.js b/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingObject.js new file mode 100644 index 0000000..55eff95 --- /dev/null +++ b/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingObject.js @@ -0,0 +1,24 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ + +a = { + height: 1 +}; + +a.a = {a}; \ No newline at end of file diff --git a/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingObject.js.indexed b/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingObject.js.indexed new file mode 100644 index 0000000..6815790 --- /dev/null +++ b/webcommon/javascript2.editor/test/unit/data/testfiles/indexer/SelfreferencingObject.js.indexed @@ -0,0 +1,45 @@ + + +Document 0 +Searchable Keys: + bn : a + bni : a + fqn : a.aO + offset : 849 + +Not Searchable Keys: + assign : + flag : 2097218 + + +Document 1 +Searchable Keys: + bn : a + bni : a + fqn : aO + offset : 823 + +Not Searchable Keys: + assign : + flag : 2097218 + + +Document 2 +Searchable Keys: + bn : height + bni : height + fqn : a.heightO + offset : 833 + +Not Searchable Keys: + assign : Number:-1:1| + flag : 578 + + +Document 3 +Searchable Keys: + usage : a:a#P + usage : a:height#P:a#P + usage : height + +Not Searchable Keys: diff --git a/webcommon/javascript2.editor/test/unit/src/org/netbeans/modules/javascript2/editor/JsTestBase.java b/webcommon/javascript2.editor/test/unit/src/org/netbeans/modules/javascript2/editor/JsTestBase.java index 679e9b7..9ecd78e 100644 --- a/webcommon/javascript2.editor/test/unit/src/org/netbeans/modules/javascript2/editor/JsTestBase.java +++ b/webcommon/javascript2.editor/test/unit/src/org/netbeans/modules/javascript2/editor/JsTestBase.java @@ -25,9 +25,11 @@ import java.util.Set; import org.netbeans.lib.lexer.test.TestLanguageProvider; import org.netbeans.modules.csl.api.test.CslTestBase; import org.netbeans.modules.csl.spi.DefaultLanguageConfig; +import org.netbeans.modules.javascript2.editor.index.JsIndexer; import org.netbeans.modules.javascript2.lexer.api.JsTokenId; import org.netbeans.modules.parsing.impl.indexing.IndexingUtils; import org.netbeans.modules.parsing.impl.indexing.RepositoryUpdater; +import org.netbeans.modules.parsing.spi.indexing.EmbeddingIndexerFactory; /** * @author Tor Norbye @@ -50,12 +52,17 @@ public abstract class JsTestBase extends CslTestBase { protected DefaultLanguageConfig getPreferredLanguage() { return new TestJsLanguage(); } - + @Override protected String getPreferredMimeType() { return JsTokenId.JAVASCRIPT_MIME_TYPE; } - + + @Override + public EmbeddingIndexerFactory getIndexerFactory() { + return new JsIndexer.Factory(); + } + public static class TestJsLanguage extends JsLanguage { public TestJsLanguage() { diff --git a/webcommon/javascript2.editor/test/unit/src/org/netbeans/modules/javascript2/editor/index/RecursiveStructuresTest.java b/webcommon/javascript2.editor/test/unit/src/org/netbeans/modules/javascript2/editor/index/RecursiveStructuresTest.java new file mode 100644 index 0000000..1e45243 --- /dev/null +++ b/webcommon/javascript2.editor/test/unit/src/org/netbeans/modules/javascript2/editor/index/RecursiveStructuresTest.java @@ -0,0 +1,88 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.netbeans.modules.javascript2.editor.index; + +import java.lang.reflect.Field; +import java.util.Collections; +import java.util.concurrent.atomic.AtomicBoolean; +import org.netbeans.modules.javascript2.editor.JsTestBase; +import org.netbeans.modules.javascript2.editor.navigation.OccurrencesSupport; +import org.netbeans.modules.javascript2.model.api.Model; +import org.netbeans.modules.javascript2.types.spi.ParserResult; +import org.netbeans.modules.parsing.api.ParserManager; +import org.netbeans.modules.parsing.api.ResultIterator; +import org.netbeans.modules.parsing.api.Source; +import org.netbeans.modules.parsing.api.UserTask; + +/** + * The JS support functions need to guard against self referential models. If + * there is no guard, unlimited recursion can occur, leading to a stack + * overflow. + */ +public class RecursiveStructuresTest extends JsTestBase { + + public RecursiveStructuresTest(String testName) { + super(testName); + } + + @Override + protected void setUp() throws Exception { + super.setUp(); + // org.netbeans.modules.javascript2.model.api.Model has an assert + // detecting cycles. This must be deactivated for tests + Field f = Model.class.getDeclaredField("assertFired"); + f.setAccessible(true); + ((AtomicBoolean) f.get(null)).set(true); + } + + public void testIndexingSelfreferencingObject() throws Exception { + checkIndexer("/testfiles/indexer/SelfreferencingObject.js"); + } + + public void testIndexingSelfreferencingFunction() throws Exception { + checkIndexer("/testfiles/indexer/SelfreferencingFunction.js"); + } + + public void testOccurrencesSelfreferencingObject() throws Exception { + Model m = getModel("/testfiles/indexer/SelfreferencingObject.js"); + OccurrencesSupport os = new OccurrencesSupport(m); + os.getOccurrence(0); + } + + public void testOccurrencesSelfreferencingFunction() throws Exception { + Model m = getModel("/testfiles/indexer/SelfreferencingFunction.js"); + OccurrencesSupport os = new OccurrencesSupport(m); + os.getOccurrence(0); + } + + public Model getModel(String file) throws Exception { + final Model[] globals = new Model[1]; + Source source = getTestSource(getTestFile(file)); + + ParserManager.parse(Collections.singleton(source), new UserTask() { + public @Override + void run(ResultIterator resultIterator) throws Exception { + ParserResult parameter = (ParserResult) resultIterator.getParserResult(); + Model model = Model.getModel(parameter, false); + globals[0] = model; + } + }); + return globals[0]; + } +} --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@netbeans.apache.org For additional commands, e-mail: commits-h...@netbeans.apache.org For further information about the NetBeans mailing lists, visit: https://cwiki.apache.org/confluence/display/NETBEANS/Mailing+lists